Page History

Lock-free programming is a technique that allows concurrent updates of shared data structures without using explicit locks. This method ensures that no threads block for arbitrarily long times, and it thereby boosts performance.

AdvantagesLock-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:

...

A limitation of lock-free programming is that it requires use of special atomic processor instructions, such as CAS (compare and swap), LL/SC (load linked/store conditional), or the C11 atomic_compare_exchange 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, where : a memory location is read twice and has the same value for both reads. However, another thread has modified the value, did other work, then modified the value back between the two reads, thereby fooling the first thread into thinking that the value never changed.

...

This noncompliant code example tries to zero the maximum element of an array. We assume this example may run in a multithreaded environment, and all variables are accessible to other threads.

#include <stdatomic.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);

void func(void) {
  atomic_int array[];
  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 will set sets array[index] to 0 if and only if it is currently set to value. However, this behavior 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.

...

The following sequence of operation operations occurs:

...

The core idea is to associate a number (typically one or two) of single-writer, multireader shared pointers called hazard pointers. 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 may be written only by its owner thread but may be read by other threads.

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.

PSEUDOCODE

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

//* The retired node 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 != null) {
    for (i<-0 to K-1) {
      hptr<-hprec^HP[i];
      if (hptr!= null)
        plist.insert(hptr);
    }
    hprec<-hprec^Next;
  }

  //* Stage 2: search plist */
  tmplist<-rlist.popAll();
  rcount<-0;
  node<-tmplist.pop();
  while (node != null) {
    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 hazard pointer list for non-null values. Whenever a non-null value is encountered, it is inserted in a local list, plist, which can be implemented as a hash table. The second stage involves checking each node in rlist against the pointers in plist. If the lookup 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 is to determine when a retired node is safely eligible for reuse safely while allowing memory 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) {
  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 as 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 *tail;
  Node *next;

  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 as hazardous. */
    if (head != q->head) {
      continue;
    }
    if (next == NULL) {
      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.
                           */
  return data;
}

Compliant Solution (GNU Glib, Mutex)

...

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

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

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

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

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

  /*
   * Lock the queue before accessing the contents and
    * 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) {
      q->head = node;
      q->tail = node;
    } else {
      q->tail->next = node;
      q->tail = node;
    }
    /* Unlock the mutex and chech the return code. */
    if (thrd_success != mtx_unlock(&(queue->mutex))) {
      return -1;  /* Indicate failure */
    }
  }
  return 0;
}

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

  if (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);
    if (thrd_success != mtx_unlock(&(queue->mutex))) {
      return NULL;  /* Indicate failure */
    }
  }
  return data;
}

...

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 Vulnerabilities

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

...