template<class T>
class MarkablePointer< T >
Bit-stealing Atomic Markable Pointer.
- Template Parameters
-
| T | Type of the pointed class/struct. Must not be unaligned types like char (unless you make sure the pointed address is aligned). |
Marked For Death
This is a common technique to implement lock-free data structures in C/C++ [HERLIHY]. Because pointers to struct/class in C++ is without doubt an even integer, the last bit of the pointer is always 0. We use the last bit to store additional flag in the 8 byte pointer. We can then use the value for 8-byte atomic operations efficiently.
- Note
- To address a common misunderstanding of lock-free list/queue: the "mark for death" bit in the pointer is NOT marking the pointed object (e.g., "next") for death. It's often marking the object that holds the pointer for death because it is what we want to atomically guarantee when we link/delink on the next pointer. So, x->next.is_marked() means x is marked for death, not x->next.
ABA Counter
As described in Chap 10.6 of [HERLIHY], there is the ABA problem. When we new/delete classes/structs, they reuse the same memory area. Hence, we need to make sure the same pointer is differentiable. The common solution is to implant some counter in the 64bit pointer like the mark for death. Intel64/AMD64 so far uses only 48 bits (http://en.wikipedia.org/wiki/X86-64), so we steal the most significant 16 bits to store a stamp value. 16 bits is not perfect for avoiding ABA problems, but double-word CAS is quite environment dependant. So, we pick this approach. If 16 bits are not enough, garbage collector should a coordinated object reclamation like what Chap 10.6 of [HERLIHY] recommends.
Atomic Functions and Non-Atomic Functions
Methods whose name start with "atomic_" provide atomic semantics. Other method are NOT atomic. So, appropriately use memory barriers to protect your access. However, other methods are regular, meaning you will not see an utter garbage but only see either the old value or new value (some valid value other thread set). This is possible because this class contains only 8 bytes information. In x86_64, an aligned 8 byte access is always regular though not atomic.
When you want to call more than one non-atomic methods of MarkablePointer, it's a good idea to copy a shared MarkablePointer variable to a local MarkablePointer variable then access the local one. For example,
bool marked = some_shared_markable_pointer.is_marked();
... many lines in-between
aba_stamp stamp = some_shared_markable_pointer.get_aba_stamp();
bool marked = copied.is_marked();
... many lines in-between
The copy/assignment operators of this class use the ACCESS_ONCE semantics to prohibit compiler from doing something dangerous for this purpose.
Still, CPU might do something and this is not atomic either. In case it matters, use the atomic_cas().
Dependency
This tiny class is completely header-only. To use, just include w_markable_pointer.h.
- See also
- http://stackoverflow.com/questions/19389243/stealing-bits-from-a-pointer
-
http://www.1024cores.net/home/lock-free-algorithms/tricks/pointer-packing
