...
| Code Block | ||||
|---|---|---|---|---|
| ||||
#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);
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
...
| Code Block | ||||
|---|---|---|---|---|
| ||||
#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)
...
| Code Block | ||||
|---|---|---|---|---|
| ||||
#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_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, null, 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;
}
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;
}
}
g_slice_free(Node, head);
return data;
}
|
Assume there are two threads (T1 and T2) operating simultaneously on the queue. The queue looks like this:
...
Compliant Solution (GNU Glib, Hazard Pointers)
According to [AA. Bibliography#Michael Michael 2004], the core idea is to associate a number (typically one or two) 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 may be written only by its owner thread but may be read by other threads.
...
| Code Block | ||||
|---|---|---|---|---|
| ||||
/* 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; /* Initially empty */
rcount: integer; /* Initially 0 */
/* The retired node routine */
RetiredNode(node:*NodeType) {
rlist.push(node);
rcount++;
if(rcount >= R)
Scan(HeadHPRec);
}
/* The scan routine */
Scan(head:*HPRecType) {
/* Stage 1: 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 while allowing memory reclamation.
In the BB. Definitions#implementation implementation, the pointer being removed is stored in the hazard pointer, preventing other threads from reusing it and thereby avoiding the ABA problem.
...
| Code Block | ||||
|---|---|---|---|---|
| ||||
#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 *head;
Node *tail;
Node *next;
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 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)
...
| Code Block | ||||
|---|---|---|---|---|
| ||||
#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 check the return code */
if (thrd_success != mtx_unlock(&(queue->mutex))) {
return -1; /* Indicate failure */
}
}
return 0;
}
gpointer queue_dequeue(Queue *q) {
Node *node;
Node *head;
Node *tail;
Node *next;
gpointer data;
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;
}
|
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 BB. Definitions#abnormal abnormal program termination or unintended information disclosure.
...
Related Vulnerabilities
Search for BB. Definitions#vulnerability vulnerabilities resulting from the violation of this rule on the CERT website.
Bibliography
...