bool CompareAndSwap(Value* addr, Value oldVal, Value newVal){
if(*addr == oldVal){
*addr = newVal;
return true;
}else{
return false;
}
}

• Lock-free algorithms are not always practical.
• Writing lock-free code is difficult.
• Writing correct lock-free code is extremely difficult.

template
class LockFreeStack{
struct Node{
Entry* entry;
Node* next;
};

Node* m_head;

void Push(Entry* e){
Node* n = new Node;
n->entry = e;
do{
n->next = m_head;
}while(!CompareAndSwap(&m_head, n->next, n));
}

Entry* Pop(){
Node* old_head;
Entry* result;
do{
old_head = m_head;
if(old_head == NULL){
return NULL;
}
}while(!CompareAndSwap(&m_head, old_head, old_head->next));

result = old_head->entry;
delete old_head;
return result;
}
}

Segfault

Corruption

• Thread 1 calls pop, and on line 22 reads m_head (A), on line 26 reads old_head->next (C), and then blocks just before calling CompareAndSwap.
• Thread 2 calls pop, and removes node A.
• Thread 2 calls push, and pushes a new node B.
• Thread 2 calls push again, and this time pushes a new node occupying the reclaimed memory from A.
• Thread 1 wakes up, and calls CompareAndSwap.

Not lock-free

Data races

Memory reordering

How to write a correct lock-free stack

Segfault

Corruption

Not lock-free

Data races

Memory reordering

• Thread 1, in preparation for a Pop operation, reads the head of the stack.
• Thread 1 writes the current head to its hazard pointer (using only release semantics, which are weaker than sequentially consistent semantics).
• Thread 1 reads the head of the stack again.
• Thread 2 removes head from the stack, and passes it to the garbage collector thread (using sequentially consistent memory semantics).
• The garbage collector scans the hazard pointers,\ and (because the assignment was not done with sequentially consistent memory semantics) is not guaranteed to see thread 1’s hazard pointer pointing to the node.
• The garbage collector deletes the node
• Thread 1 dereferences the node, and segfaults.

Performance

Results

Conclusion

Code

class LockFreeStack{
#include
#include

template
class LockedStack{
public:
void Push(T* entry){
std::lock_guard lock(m_mutex);
m_stack.push(entry);
}

// For compatability with the LockFreeStack interface,
// add an unused int parameter.
//
T* Pop(int){
std::lock_guard lock(m_mutex);
if(m_stack.empty()){
return nullptr;
}
T* ret = m_stack.top();
m_stack.pop();
return ret;
}

private:
std::stack<T*> m_stack;
std::mutex m_mutex;
};

class LockFreeStack{
public:
// The elements we wish to store should inherit Node
//
struct Node{
boost::atomic<Node*> next;
};

// Unfortunately, there is no platform independent way to
// define this class. The following definition works in
// gcc on x86_64 architectures
//
class TaggedPointer{
public:
TaggedPointer(): m_node(nullptr), m_counter(0) {}

Node* GetNode(){
return m_node.load(boost::memory_order_acquire);
}

uint64_t GetCounter(){
return m_counter.load(boost::memory_order_acquire);
}

bool CompareAndSwap(Node* oldNode, uint64_t oldCounter, Node* newNode, uint64_t newCounter){
bool cas_result;
__asm__ __volatile__
(
"lock;" // This makes the following instruction atomic (it is non-blocking)
"cmpxchg16b %0;" // cmpxchg16b sets ZF on success
"setz %3;" // if ZF set, set cas_result to 1

: "+m" (*this), "+a" (oldNode), "+d" (oldCounter), "=q" (cas_result)
: "b" (newNode), "c" (newCounter)
: "cc", "memory"
);
return cas_result;
}
private:
boost::atomic<Node*> m_node;
boost::atomic m_counter;
}
// 16-byte alignment is required for double-width
// compare and swap
//
__attribute__((aligned(16)));

bool TryPushStack(Node* entry){
Node* oldHead;
uint64_t oldCounter;

oldHead = m_head.GetNode();
oldCounter = m_head.GetCounter();
entry->next.store(oldHead, boost::memory_order_relaxed);
return m_head.CompareAndSwap(oldHead, oldCounter, entry, oldCounter + 1);
}

bool TryPopStack(Node*& oldHead, int threadId){
oldHead = m_head.GetNode();
uint64_t oldCounter = m_head.GetCounter();
if(oldHead == nullptr){
return true;
}
m_hazard[threadId*8].store(oldHead, boost::memory_order_seq_cst);
if(m_head.GetNode() != oldHead){
return false;
}
return m_head.CompareAndSwap(oldHead, oldCounter, oldHead->next.load(boost::memory_order_acquire), oldCounter + 1);
}

void Push(Node* entry){
while(true){
if(TryPushStack(entry)){
return;
}
usleep(250);
}
}

Node* Pop(int threadId){
Node* res;
while(true){
if(TryPopStack(res, threadId)){
return res;
}
usleep(250);
}
}

private:
TaggedPointer m_head;
// Hazard pointers are separated into different cache lines to avoid contention
//
boost::atomic<Node*> m_hazard[MAX_THREADS*8];
};