...
The ABA problem 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 (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().
...
Thread | Queue Before | Operation | Queue After |
|---|---|---|---|
| head -> A -> B -> C -> tail | Enters | head -> A -> B -> C -> tail |
| head -> A -> B -> C -> tail | removes Removes node A | head -> B -> C -> tail |
| head -> B -> C -> tail | removes Removes node B | head -> C -> tail |
| head -> C -> tail | enqueues Enqueues node A back into the queue | head -> A -> C -> tail |
| head -> A -> C -> tail | removes Removes node C | head -> A -> tail |
| head -> A -> tail | enqueues Enqueues a new node D | head -> A -> D -> tail |
| head -> A -> D -> tail | Thread 1 starts execution | undefined {} |
...
Also, if reclaimed memory is returned to the operating system (e.g., using munmap()), access to such memory locations can result in fatal access violation errors.
Compliant Solution (GNU Glib, Hazard Pointers)
The core idea is to associate a number (typically one or two) of single-writer multi-reader shared pointers, called hazard pointers.
...
| Code Block | ||
|---|---|---|
| ||
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 has 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 has 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, pthread_mutex_lock() is used to lock the queue.
...
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.
AMD Developer Central: Articles & Whitepapers: http://developer.amd.com/documentation/articles/pages/125200689.aspx Lock-Free Programming on AMD Multi-Core System
Asgher, Sarmad. http://www.drdobbs.com/go-parallel/article/showArticle.jhtml;jsessionid=IBA5HITYQUKK1QE1GHRSKH4ATMY32JVN?articleID=219500200 Practical Lock-Free Buffers, Dr. Dobbs Go-Parallel, August 26, 200
[http://www.fireeye.com/products/index.html} FireEye Anti-Malware and Anti-Botnet Security tool is an example.
...
CON37-C. Do not use more than one mutex for concurrent waiting operations on a condition variable 14. Concurrency (CON) 49. Miscellaneous (MSC)