Page History

...

-         Lock-Free Programming on AMD Multi-Core Systems 

-         API monitoring

Problem Associated with Lock-Free Approach(ABA):

...

Let us assume there are two threads (T1 and T2) operating simultaneously on the queue. The queue looks like this,

head -> A -> B -> C -> tail> tail

The following sequence of operation occurs.

...

Also  if reclaimed memory(B) is returned  to  the operating  system  (e.g., using  munmap), access to such memory locations can result in fatal access violation  errors.

Compliant Solution (using Hazard pointers)

The core idea is to associate a number (typically one or two)  of single-writer  multi-reader  shared pointers,  called hazard pointers.

...

In the above code, the pointer on being removed is stored in the hazard pointer and thus prevents other threads from reusing it and avoiding the ABA problem.

Compliant Solution (using Mutex)

Code:

 void queue_enqueue(Queue *q, gpointer data) {#include <glib.h>
#include <glib-object.h>

struct Node {
	void *data;
	Node *next;
};

struct Queue {
  Node *head;
  Node *tail;
  pthread_mutex_t mutex;
};

Queue*
queue_new(void){
  Queue *q = g_slice_new(sizeof(Queue));
  q->head = q->tail = g_slice_new0(sizeof(Node));
  return q;
}

void
queue_enqueue(Queue *q, gpointer data){

  Node *node, *tail, *next;
  // Lock the queue before accesing the contents
  pthread_mutex_lock(&(q->mutex));

  node = g_slice_new(Node);
  node->data = data;
  node->next = NULL;

  if(q->head == NULL){
    q->head = node;
    q->tail = node;
  }
  else {
    q->tail->next = node;
    q->tail = node;
  }
  //Unlock the mutex
  pthread_mutex_unlock(&(queue->mutex));
}

gpointer
queue_dequeue(Queue *q){
  Node *node, *tail, *next;

  pthread_mutex_lock(&(q->mutex));

  head = q->head;
  tail = q->tail;
  next = head->next;
  data = next->data;
  q->head = next;

  g_slice_free(Node, head);
  pthread_mutex_unlock(&(queue->mutex));

  return data;
}

In the above code, pthread_mutex_lock() is used to lock the queue.

When thread 1(T1) locks on the queue to perform any operation then thread 2 cannot perform any operation on the queue. Thus preventing the ABA problem.

Risk Assessment

The likelihood of having a race condition is low. Once the race condition occurs then reading memory that has already been freed can lead to abnormal program termination or unintended information disclosure.

Related Guidelines

[The CERT Oracle Secure Coding Standard for Java|java:The CERT Oracle Secure Coding Standard for Java]:
[THI04-J. Notify all waiting threads instead of a single thread|Java:THI04-J. Notify all waiting threads instead of a single thread].

Bibliography

Bibliography

Hazard Pointers : Michael, M.M. "Hazard pointers: Safe memory reclamation for lock-free objects,"IEEE Transactions on Parallel and Distributed Systems, vol. 15, no. 8, Aug. 2004.

Linux v2.5.53 : lock-free ipv4 route cache

AMD Developer Central: Articles & Whitepapers:

Lock-Free Programming on AMD Multi-Core System (http://developer.amd.com/documentation/articles/pages/125200689.aspx)[[Open Group|AA. Bibliography#OpenGroup04]] [pthread_cond_signal() pthread_cond_broadcast()|http://www.opengroup.org/onlinepubs/7990989775/xsh/pthread_cond_signal.html]

----
CON37-C. Do not use more than one mutex for concurrent waiting operations on a condition variable 14. Concurrency (CON) 49. Miscellaneous (MSC)