Hazard pointer

In a multithreaded computing environment, hazard pointers are one approach to solving the problems posed by dynamic memory management of the nodes in a lock-free data structure. These problems generally arise only in environments that don't have automatic garbage collection.

Any lock-free data structure that uses the compare-and-swap primitive must deal with the ABA problem. For example, in a lock-free stack represented as an intrusively linked list, one thread may be attempting to pop an item from the front of the stack (A → B → C). It remembers the second-from-top value "B", and then performs <syntaxhighlight lang="c" inline>

compare_and_swap(target=&head, newvalue=B, expected=A)</syntaxhighlight>. Unfortunately, in the middle of this operation, another thread may have done two pops and then pushed A back on top, resulting in the stack (A → C). The compare-and-swap succeeds in swapping `head` with `B`, and the result is that the stack now contains garbage (a pointer to the freed element "B").

Furthermore, any lock-free algorithm containing code of the form

<syntaxhighlight lang="c">

Node* currentNode = this->head; // assume the load from "this->head" is atomic

Node* nextNode = currentNode->next; // assume this load is also atomic

</syntaxhighlight>

suffers from another major problem, in the absence of automatic garbage collection. In between those two lines, it is possible that another thread may pop the node pointed to by <code>this->head</code> and deallocate it, meaning that the memory access through <code>currentNode</code> on the second line reads deallocated memory (which may in fact already be in use by some other thread for a completely different purpose).

Hazard pointers can be used to address both of these problems. In a hazard-pointer system, each thread keeps a list of hazard pointers indicating which nodes the thread is currently accessing. (In many systems this "list" may be probably limited to only one or two elements.) Nodes on the hazard pointer list must not be modified or deallocated by any other thread.