Page History

Lock-Free Programming free programming is a technique that allows concurrent update updates of shared data structures without using explicit locks.   This method ensures system wide progress.

Advantages:

...

that no threads block for arbitrarily long times, and it thereby boosts performance.

Lock-free programming has the following advantages:

• Can be used in places

...

• where locks

...

• must be avoided

...

• , such as interrupt handlers
• Efficiency benefits compared to lock-based algorithms

...

• for some workloads, including potential scalability benefits on multiprocessor machines

...

• Avoidance of priority inversion in real-time systems

Limitations:

-         use Lock-free programming requires the use of special atomic processor instructions, such as CAS (compare and swap) or , LL/SC (load linked/store conditional)

Applications:

...

, or the C Standard atomic_compare_exchange generic functions.

Applications for lock-free programming include

• Read-copy-

...

• update€ (RCU) in Linux 2.5 kernel

...

• Lock-

...

• free programming on AMD

...

• multicore systems

The ABA problem occurs during synchronization: a memory

...

-         API monitoring

Problem Associated with Lock-Free Approach(ABA):

ABA problem occurs during synchronization, when a location is read twice , and has the same value for both reads. However, another thread can execute between the two reads and change the has modified the value, do performed other work, then change modified the value back, thus fooling back between the two reads, thereby tricking the first thread in to thinking "nothing has changed" even though the second thread did work that violates that assumption.

ABA occurs due to the internal reuse of nodes that have been popped off the list or by the reclamation of memory occupied by removed nodes.

Noncompliant Code Example (Queue)

into thinking that the value never changed.

Noncompliant Code Example

This noncompliant code example attempts to zero the maximum element of an array. The example is assumed to run in a multithreaded environment, where all variables are accessed by other threadsA queue data structure implementation using lock free method.

#include <glib<stdatomic.h>#include <glib.h>
 
/*
 * Sets index to point to index of maximum element in array
 * and value to contain maximum array value.
 */
void find_max_element(atomic_int array[], size_t *index, int *value);

static atomic_int array[];

void func(void) {
  size_t index;
  int value;
  find_max_element(array, &index, &value);
  /* ... */
  if (!atomic_compare_exchange_strong(array[index], &value, 0)) {
    /* Handle error */
  }
}

The compare-and-swap operation sets array[index] to 0 if and only if it is currently set to value. However, this code does not necessarily zero out the maximum value of the array because

• index may have changed.
• value may have changed (that is, the value of the value variable).
• value may no longer be the maximum value in the array.

Compliant Solution (Mutex)

This compliant solution uses a mutex to prevent the data from being modified during the operation. Although this code is thread-safe, it is no longer lock-free.

#include <stdatomic.h>
#include <threads.h>
 
static atomic_int array[];
static mtx_t array_mutex;

void func(void) {
  size_t index;
  int value;
  if (thrd_success != mtx_lock(&array_mutex)) {
    /* Handle error */
  }
  find_max_element(array, &index, &value);
  /* ... */
  if (!atomic_compare_exchange_strong(array[index], &value, 0)) {
    /* Handle error */
  }
  if (thrd_success != mtx_unlock(&array_mutex)) {
    /* Handle error */
  }
}

Noncompliant Code Example (GNU Glib)

This code implements a queue data structure using lock-free programming. It is implemented using glib. The function CAS() internally uses g_atomic_pointer_compare_and_exchange().

#include <glib.h>
#include <glib-object.h>

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

typedef struct queue_s {
  Node *head;
  Node *tail;
} Queue;

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

void queue_enqueue(Queue *q, gpointer data) {
  Node *node;
  Node *tail;
  Node *next;

  node = g#include <glib-object.h>
#include <glib-object.h>
struct Node {
  void *data;
  Node *next;
};

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

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;
  node = g_slice_new(Node);
  node->data = data;
  node->next = NULL;
  while (TRUE) {
    tail = q->tail;
    next = tail->next;
    if (tail != q->tail) {
      continue;
    }
    if (next != NULL) {
      CAS(&q->tail, tail, next);
      continue;
    }
    if (CAS(&tail->next, nullNULL, node)) {
      break;
    }
  }
  CAS(&q->tail, tail, node);
}



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

  while (TRUE) {
    head = q->head;
    tail = q->tail;
    next = head->next;
    if (head != q->head) {
      continue;
    continue;}
    if (next == NULL) {
      return NULL; /* Empty */
    Empty}
    if (head == tail) {
      CAS(&q->tail, tail, next);
      continue;
    }
    data = next->data;
    if (CAS(&q->head, head, next)) {
      break;
    }
  }
  g_slice_free(Node, head);
  return data;
}

The above implementation works with glib. The function CAS uses g_atomic_pointer_compare_and_exchange() internallyLet's consider the following example: 

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

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

The following sequence of operation operations occurs.:

According to the above sequence of events now in this table, head will be pointing now point to a memory which that was removedfreed. Also  if , if reclaimed memory (B) is returned  to  the operating  system  (e.g., using  munmapis returned to the operating system (for example, using munmap()), access to such memory locations can result in fatal access violation  violation errors. The ABA problem occurred because of the internal reuse of nodes that have been popped off the list or the reclamation of memory occupied by removed nodes.

Compliant Solution (

...

GNU Glib, Hazard Pointers)

According to [Michael 2004], the The core idea is to associate a number (typically one or two)   of single-writer  multi-reader  shared pointers,  called hazard pointers.A of single-writer, multi-reader shared pointers, called hazard pointers, with each thread that intends to access lock-free dynamic objects. A hazard pointer either has a null value or points to a node that may be accessed later by that thread without further validation that the reference to the node is still valid. Each hazard pointer can may be written only by its owner thread , but can may be read by other threads.

This methodology communicates In this solution, communication with the associated algorithms is accomplished only through hazard pointers and a procedure RetireNode() that is called by threads to pass the addresses of retired nodes.Pseudo Code:

PSEUDOCODE

//* Hazard Pointerspointers Typestypes and Strucutrestructure */
 structure HPRecType {
     { HP[K]:*Nodetype;
  Next:*HPRecType;
}
 
//* The header of the HPRec list */
 HeadHPRec: *HPRecType;
//* Per-thread private variables */
 rlist: listType; //initially* Initially empty */
 rcount: integer; //initially* Initially 0

 */

//* The Retiredretired Nodenode routine */
RetiredNode(node:*NodeType) {
  rlist.push(node);
  rcount++;
  if(rcount >= R)
    Scan(HeadHPRec);
}


//* The scan routine */
Scan(head:*HPRecType) {
  //* Stage Stage11: Scan HP list and insert non -null values in plist */
  plist.init();
  hprec<-head;
  while (hprec != nullNULL) {
    for (i<-0 to K-1) {
      hptr<-hprec^HP[i];
      if (hptr!= nullNULL)
        plist.insert(hptr);
    }
    hprec<-hprec^Next;
  }


  //* Stage 2: search plist */
  tmplist<-rlist.popAll();
  rcount<-0;
  node<-tmplist.pop();
  while (node != nullNULL) {
    if (plist.lookup(node)) {
      rlist.push(node);
      rcount++;
    }
    else {
      PrepareForReuse(node);
    }
    node<-tmplist.pop();
  }
  plist.free();
}

The scan consists of two stages.   The  first  stage  involves  scanning  the  HP  list  for nonThe first stage involves scanning the hazard pointer list for non-null values. Whenever a nonnull non-null value is encountered, it is inserted in a local list, plist, which can be implemented as a hash table. The second stage of Scan involves checking each checking each node in rlist against the pointers in plist. If the lookup yields  no  match,  the  node  is  identified  to  be  ready  yields no match, the node is identified to be ready for arbitrary reuse. Otherwise, it is retained in rlist until the next scan by the current thread. Insertion and lookup in plist take constant expected time.  The  task  of  the  memory  reclamation  method  The task of the memory reclamation method is to determine when a retired node is safely eligible for reuse safely while allowing memory reclamation.Code:reclamation.

In the implementation, the pointer being removed is stored in the hazard pointer, preventing other threads from reusing it and thereby avoiding the ABA problem.

CODE

#include <glib.h>
#include <glib-object.h>
 

 void queue_enqueue(Queue *q, gpointer data) {void queue_enqueue(Queue *q, gpointer data) {
  Node *node,;
  Node *tail,;
  Node *next;

  node = g_slice_new(Node);
  node->data = data;
  node->next = NULL;
  while (TRUE) {
    tail = q->tail;
    HAZARD_SET(0, tail);              //* Mark tail hasas hazardous */
    if (tail != q->tail)  {           ///* Check tail hasn't changed */
      continue;
    }
    next = tail->next;
    if (tail != q->tail) {
      continue;
    }
    if (next != NULL) {
      CAS(&q->tail, tail, next);
      continue;
    }
    if (CAS(&tail->next, null, node) {
      break;
    }
  }
  CAS(&q->tail, tail, node);
}


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

  while (TRUE) {
    head = q->head;
    LF_HAZARD_SET(0, head);    //* Mark head as hazardous */
    if (head != q->head)     {  //* Check head hasn't changed */
      continue;
    }
    tail = q->tail;
    next = head->next;
    LF_HAZARD_SET(1, next);    //* Mark next hasas hazardous */
    if (head != q->head) {
      continue;
    }
    if (next == NULL) {
      return NULL; /* Empty */
 return NULL; // Empty}
    if (head == tail) {
      CAS(&q->tail, tail, next);
      continue;
    }
    data = next->data;
    if (CAS(&q->head, head, next)) {
      break;
    }
  }
  LF_HAZARD_UNSET(head);  /*
                 //          * Retire head, and perform
                           * reclamation if needed.
                       // reclamation if needed. */
  return data;
}
5 Node *node, *tail, *next;
7 node = g_slice_new(Node);

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)

Compliant Solution (GNU Glib, Mutex)

In this compliant solution, mtx_lock() is used to lock the queue. When thread 1 locks on the queue to perform any operation, thread 2 cannot perform any operation on the queue, which prevents the ABA problem.Code:

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

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

typedef struct Queuequeue_s {
  Node *head;
  Node *tail;
  pthread_mutexmtx_t mutex;
} Queue;

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

void
int queue_enqueue(Queue *q, gpointer data) {

  Node *node,;
  Node *tail,;
  Node *next;

  /*
   //* Lock the queue before accesingaccessing the contents and
    pthread_mutex* check the return code for success.
   */
  if (thrd_success != mtx_lock(&(q->mutex));

))) {
    return -1;  /* Indicate failure */
  } else {
    node = g_slice_new(Node);
    node->data = data;
    node->next = NULL;

    if(q->head == NULL)== NULL) {
      q->head = node;
      q->tail = node;
    } else {
      q->head>tail->next = node;
      q->tail = node;
    }
  else    /* Unlock the mutex and check the return code */
    if (thrd_success != mtx_unlock(&(queue->mutex))) {
     q->tail->next =return node-1;
  /* Indicate  q->tail = node;
failure */
    }
  //Unlock}
 the mutex
  pthread_mutex_unlock(&(queue->mutex))return 0;
}

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

  if pthread_mutex(thrd_success != mtx_lock(&(q->mutex));

 {
    return NULL;  /* Indicate failure */
  } else {
    head = q->head;
    tail = q->tail;
    next = head->next;
    data = next->data;
    q->head = next;

    g_slice_free(Node, head);
  pthread_mutex  if (thrd_success != mtx_unlock(&(queue->mutex)));
 {
      return NULL;  /* Indicate failure */
    }
  }
  return data;
}

Risk Assessment

The likelihood of having a race condition is low. Once the race condition occurs, the 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

Automated Detection

Related Vulnerabilities

Search for vulnerabilities resulting from the violation of this rule on the CERT website.

Bibliography

...

Image Added Image Added Image Added[[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)