Lock-free data structure — Concurrency Programming

There is a fancy technique in multi programming, which is called ‘Lock free’.

As you can guess from its name, you don’t need to use lock_guard when using this lock-free structure.

1. Lock-free stack

Instead of using STL library, let’s implement stack structure from scratch.

template<typename T>
class LockFreeStack
{
//I used linked-list data structure to implement stack.
	struct Node
	{
		Node(const T& value) : data(value) {}
		T data;
		Node* next; // next Node data that we use after popping out head.
	};
private:
 atomic<Node*> _head; //head is a pointer to point to current data location
//head always points to the top of stack
}

• Push Instead of using lock, we use busy waiting here.(you might remember this in related to spin lock.). As you can see, Even though we want to use lock-free data structure, It is inevitable to set some preventions. Because of this, it is more complex than using lock in general while there is no outstanding performance improvement.

public:
void Push(const T& value)
{
		Node* node = new Node(value);
		node->next = _head;
                while (_head.compare_exchange_weak(node->next, node) == false)
                  {
                   
                  }
 }

• TryPop Poppping data divided into several steps.

1. read head
2. read head→next
3. head = head→next
4. data load from head
5. delete node.

bool TryPop(T& value)
{
  Node* cur = _head;
// With compare and swap, we can prevent data race from step1 to step3
  // Because there is a possibility that _head is null, we do null check first before CAS
  while (cur && _head.compare_exchange_weak(cur, cur->next) == false)
  {
  } 
  
  //if head is null, return false
  if (cur == nullptr) return false;
  value = cur->data; 
  // delete is different problem.
  // Think about one thread is on step1 and the other thread on step 5(delete node)
  // If a thread on step 5 deletes memory, a thread on step1 will read non-exist memory.
  // delete cur;
  return true;
 }

how to handle ‘delete node’?

//1. separating node
	//2. count check
	//3. If only one thread popping, delete memory.
	void TryDelete (Node* oldHead)
	{
		//whether only one thread trying pop
		if (_popCount == 1)
		{ 
			Node* node = _pendingList.exchange(nullptr); // exchange method do swapping atomically at once
                        if (--_popCount == 0) //reduce pop count and check it is still alone.
   {
    DeleteNodes(node);
   }
   else if(node)
   {
    //There is some threads intervene while processing this function.
    //So restore _pendingList
    ChainPendingNodeList(node);
   }
   delete oldHead;
  }
  else
  {
   //There are other threads trying pop, then reserve deletion.
   ChainPendingNode(oldHead);
   --_popCount;
  }
 }
 
 // 1. link exists pendingList to tail of previous pendingList 
  //    which was exchanged into a node variable before.
 // 2. do CAS operation whether head of current pendingList is same with last->next
  //.   if so, swap it with first.
 void ChainPendingNodeList(Node* first, Node* last)
 {
  last->next = _pendingList;
  while (_pendingList.compare_exchange_weak(last->next, first) == false)
  {
  }
 }
 //helper function to call above function
 void ChainPendingNodeList(Node* node)
 {
  Node* last = node;
  while (last->next)
  {
   last->next = last;
  }
  ChainPendingNodeList(node, last);
 }
 //add only one node to pending list again
 void ChainPendingNode(Node* node)
 {
  ChainPendingNodeList(node, node);
 }
 static void DeleteNodes(Node* node)
 {
  while (node)
  {
   Node* next = node->next;
   delete node;
   node = next;
  }
 }

For your better understand, let’s take an example of chain pending list function.

First, we did exchange _pendingList with a node in ‘TryDelete’.

node : [] [] [] [] <- _pendingList
_pendingList : nullptr

After then, we realized that we need to restore pendingList again.

node : [](fisrt) [] [] [](last) [_pendingList]
_pendingList : [list of nodes added to here while try deleting]
check last->next(which is _pendingList) == _pendingList

You may think it is useless to check for same object. But Many threads can call ChainPendigList at the same time and that’s why we need to check whether the two pointer is same.

If check result is true, update _pendingList

node: [](fist) [] [] [](last) [_pendingList]
After update,
_pendingList: node (_pendingList points to 'first')

Lock-free stack (shared pointer ver)

Let’s change original types and related operations using shared_ptr.

For who doesn’t know about shared_ptr well (includes me 😢),

• To create a shared pointer, we use ‘make_shared<type>’ function.
• When you refer to a shared pointer, it increments a reference count If not, it decrement a ref count.

template<typename T>
class LockFreeStack
{
struct Node
{
	Node(const T& value) : data(make_shared<T>(value)), next(nullptr)
	{
        }
          shared_ptr<T> data;
          shared_ptr<Node> next;
};
public:
 void Push(const T& value)
 {
  shared_ptr<Node> node = make_shared<Node>(value);
  node->next = _head;
  while (std::atomic_compare_exchange_weak(&_head, &node->next, node) == false)
  {
  }
 }
private:
 shared_ptr<Node* > _head;
};

• TryPop

Below part of code also important. When you refer to a shared pointer, it doesn’t operate atomically, which means you need to use atomic operation to refer to a specific shared pointer either.

Get coderfromnineteen’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

Also, when you use CAS for shared_pointer, you need to pass a origin reference as a first parameter unlike you do it for atomic variables before.

shared_ptr<T> TryPop(T& value) 
{
	shared_ptr<Node> oldHead = std::atomic_load(&_head);
        while (oldHead && std::atomic_compare_exchange_weak(&_head, &oldHead, oldHead->next) == false)
        {
        }
        if (oldHead == nullptr)
        {
         return shared_ptr<T>();
        }
        return oldHead->data;
 }

To be honest, there is no guarantee whether the structure above will work as lock-free way.

If you run below code, you can check it.

int main()
{
	shared_ptr<int32> ptr;
	std::atomic_is_lock_free(&ptr);
}

In conclusion, it is not actual lock-free structure. but at least it works!

Lock-free stack(custom reference count)

There is a bit change from shared_ptr version.

1. I added countedNodePtr struct to count references and trace next node
2. Instead of having a ‘next’ member as Node type itself, i changed it to CountedNodePtr.

template<typename T>
class LockFreeStack
{
	struct Node;
        struct CountedNodePtr 
         {
          int32 externalCount = 0;
          Node* ptr = nullptr;
         };
         struct Node
         {
          Node(const T& value) : data(make_shared<T>(value)) {}
          shared_ptr<T> data;
          atomic<int32> internalCount = 0;
          CountedNodePtr next;
         };
        ...
}

• Push

1. create new node and assign it into node’s ptr
2. initialize externalCount as 1
3. To set new node as a head, Do CAS as we always did.

void Push(const T& value)
	{
		CountedNodePtr node;
		node.ptr = new Node();
		node.externalCount = 1;
		 
		node.ptr->next = _head;
		while (_head.compare_exchange_weak(node.ptr->next, node) == false)
		{
                }
          }

• TryPop

1. First of all, you need to get a reference chance by executing IncreaseHeadCount.

In infinite loop, i copied prevCounter to newCounter and incremented newCounter’s externalCount. At this moment, count of each prev and new is different because they are struct type here.

Also, there is a possibility to happen data race while a thread increasing external count.

That’s why i used CAS operation here to check whether two struct are same.

If so, i assigned count of new counter to prev counter so that it can gain reference chance.

void IncreaseHeadCount(CountedNodePtr& prevCounter)
	{
		while (true)
		{
			CountedNodePtr newCounter = prevCounter; //copy previous counter
			newCounter.externalCount++; //race condition possible
                        if (_head.compare_exchange_strong(prevCounter, newCounter))
   {
    //If compare is success
    prevCounter.externalCount = newCounter.externalCount;
    break;
   }
   
  }
 }

1. After gaining a reference, if it is null pointer, just return empty shared pointer.
2. If not, Now it’s second round. we need to get ownership of the pointer.(If you are familiar to rust programming language, it is quite a similar to concept of ownership in rust.)
3. Do CAS to check whether prevHead is same with _head. If so, exchange ptr→next with _head.
4. Delete process is kinda tricky, so i recommend you follow my comments to understand it.

shared_ptr<T> TryPop()
	{
		CountedNodePtr prevHead = _head;
		while (true)
		{
			//gain reference 
			IncreaseHeadCount(prevHead);
			//At this moment, external count is larger or equal than 2 => safe
			Node* ptr = prevHead.ptr;
                        if (ptr == nullptr)
                            return  shared_ptr<T>();
                           //gain ownership(winner is who exchanges ptr->next with _head)
                       if (_head.compare_exchange_strong(prevHead, ptr->next))
                       {
                        shared_ptr<T> res;
                        res.swap(ptr->data);
                        //external : 1 -> 2(+1) when only one reference occur
                        //internal : 0 -> 
                        //check whether winner only refer to ptr
                        const int32 countIncrease = prevHead.externalCount - 2;
                        //fetch_add return a state before operation done
                        if (ptr->internalCount.fetch_add(countIncrease) == -countIncrease)
                        { 
                         delete ptr;
                        }
                        //if there was more reference to ptr, just return res
                        return res;
                       }
                       else if(ptr->internalCount.fetch_sub(1) == 1) //loser decerements internalcount
                        //when it is 1, it means that the loser is last thread who referred to this pointer
                        //so it delete ptr and go out
                       {
                        //gain reference, but not ownership
                        delete ptr;
                       }
                      }
                }

When i learned about lock-free data strucutre at the first time, I was so overwhelmed by the complexity of logics.

But actually lock-free structure is still on researching, and it requires a lot of mathematical proofs to prove no flaws in the logic. In conclusion, when you want to choose lock-free way, you just need to read related papers and use it! (Keep in mind that there may be license about code usage :( )