rcu.cpp File Reference

#include <rcu.h>
#include <sync.h>
#include <algorithm>
#include <chrono>
#include <condition_variable>

Include dependency graph for rcu.cpp:

Go to the source code of this file.

Classes
class	RCUInfos::RCUCleanupGuard

Variables
static constexpr int	RCU_ACTIVE_LOOP_COUNT = 10
	How many time a busy loop runs before yelding. More...
static std::atomic< RCUInfos * >	threadInfos {nullptr}
	We maintain a linked list of all the RCUInfos for each active thread. More...
static RecursiveMutex	csThreadInfosDelete

Variable Documentation

csThreadInfosDelete

RecursiveMutex csThreadInfosDelete

static

Definition at line 105 of file rcu.cpp.

RCU_ACTIVE_LOOP_COUNT

constexpr int RCU_ACTIVE_LOOP_COUNT = 10

staticconstexpr

How many time a busy loop runs before yelding.

Definition at line 19 of file rcu.cpp.

threadInfos

std::atomic<RCUInfos *> threadInfos {nullptr}

static

We maintain a linked list of all the RCUInfos for each active thread.

Upon start, a new thread adds itself to the head of the liked list and the node is then removed when the threads shuts down.

Insertion is fairly straightforward. The first step is to set the next pointer of the node being inserted as the first node in the list as follow:

threadInfos -> Node -> ... ^ Nadded -|

The second step is to update threadInfos to point on the inserted node. This is done using compare and swap. If the head of the list changed during this process - for instance due to another insertion, CAS will fail and we can start again.

threadInfos Node -> ... | ^ -> Nadded -|

Deletion is a slightly more complex process. The general idea is to go over the list, find the parent of the item we want to remove and set it's next pointer to jump over it.

Nparent -> Ndelete -> Nchild

Nparent Ndelete -> Nchild | ^ -----------------—|

We run into problems when a nodes is deleted concurrently with another node being inserted. Hopefully, we can solve that problem with CAS as well.

threadInfos -> Ndelete -> Nchild ^ Nadded -|

The insertion will try to update threadInfos to point to Nadded, while the deletion will try to update it to point to Nchild. Whichever goes first will cause the other to fail its CAS and restart its process.

threadInfos Ndelete -> Nchild | ^ --> Nadded -|

After a successful insertion, threadInfos now points to Nadded, and the CAS to move it to Nchild will fail, causing the deletion process to restart from scratch.

 /----------------------|
 |                      V

threadInfos Ndelete -> Nchild ^ Nadded -|

After a successful deletion, threadInfos now points to NChild and the CAS to move it to Nadded will fail, causing the insertion process to fail.

We also run into problems when several nodes are deleted concurrently. Because it is not possible to read Ndelete->next and update Nparent->next atomically, we may end up setting Nparent->next to a stale value if Nchild is deleted.

          /----------------------|
          |                      V

Nparent Ndelete Nchild -> Ngrandchild | ^ -----------------—|

This would cause Nchild to be 'resurrected', which is obviously a problem. In order to avoid this problem, we make sure that no concurrent deletion takes places using a good old mutex. Using a mutex for deletion also ensures we are safe from the ABA problem.

Once a node is deleted from the list, we cannot destroy it right away. Readers do not hold the mutex and may still be using that node. We need to leverage RCU to make sure all the readers have finished their work before allowing the node to be destroyed. We need to keep the mutex during that process, because we just removed our thread from the list of thread to wait for. A concurrent deletion would not wait for us and may end up deleting data we rely on as a result.

Definition at line 104 of file rcu.cpp.