Page History

...

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 nothing has changed.

Noncompliant Code Example

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

...

index may have changed.
value may have changed.
value may no longer be the maximum value in the array.

Compliant Solution

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.

Code Block

bgColor	#ccccff
lang	c

_Atomic int array[];
size_t index;
int value;
mtx_t array_mutex;
int result;
if ((result = mtx_lock(&array_mutex)) == thrd_error) {
  /* Handle error */
}
find_max_element( array, &index, &value);
/* ... */
if (!atomic_compare_exchange_weak( array[index], value, 0)) {
  /* Handle error */
}
if ((result = mtx_unlock(&array_mutex)) == thrd_error) {
  /* 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().

...

According to the sequence of events in this table, head will now point to memory that was freed. Also, if reclaimed memory is returned to the operating system (for example, using munmap()), access to such memory locations can result in fatal access 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)

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

...

Code Block

bgColor	#ccccff
lang	c

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)

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 Block

bgColor	#ccccff
lang	c

#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_new0( sizeof(Node));
  return q;
}

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

  // Lock the queue before accessing the contents
  mtx_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
  mtx_unlock(&(queue->mutex));
}

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

  mtx_lock(&(q->mutex));

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

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

  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.

Guideline	Severity	Likelihood	Remediation Cost	Priority	Level
CON39-C	Medium	unlikely	High	P2	L3

Bibliography

[Apiki 2006]	"Lock-Free Programming on AMD Multi-Core System"
[Asgher 2000]	"Practical Lock-Free Buffers"
[Michael 2004]	"Hazard Pointers"

...

Space shortcuts

Page tree

Versions Compared

Old Version 26

New Version 27

Key

Noncompliant Code Example

Compliant Solution

Noncompliant Code Example (GNU Glib)

Compliant Solution (GNU Glib, Hazard Pointers)

Compliant Solution (GNU Glib, Mutex)

Risk Assessment

Bibliography