RCU Library

Lockless data structures provide scalability and determinism. They enable use cases where locking may not be allowed (for example real-time applications). In the following sections, the term “memory” refers to memory allocated by typical APIs like malloc() or anything that is representative of memory, for example an index of a free element array. Since these data structures are lockless, the writers and readers are accessing the data structures concurrently. Hence, while removing an element from a data structure, the writers cannot return the memory to the allocator, without knowing that the readers are not referencing that element/memory anymore. Hence, it is required to separate the operation of removing an element into two steps:
Delete: in this step, the writer removes the reference to the element from the data structure but does not return the associated memory to the allocator. This will ensure that new readers will not get a reference to the removed element. Removing the reference is an atomic operation.
Free (Reclaim): in this step, the writer returns the memory to the memory allocator only after knowing that all the readers have stopped referencing the deleted element. This library helps the writer determine when it is safe to free the memory by making use of thread Quiescent State (QS).

• 1、What is Quiescent State

  Quiescent State can be defined as “any point in the thread execution where the thread does not hold a reference to shared memory”. It is the responsibility of the application to determine its quiescent state.
  
  As shown in Fig. 7.1, reader thread 1 accesses data structures D1 and D2. When it is accessing D1, if the writer has to remove an element from D1, the writer cannot free the memory associated with that element immediately. The writer can return the memory to the allocator only after the reader stops referencing D1. In other words, reader thread RT1 has to enter a quiescent state.

  Similarly, since reader thread 2 is also accessing D1, the writer has to wait till thread 2 enters quiescent state as well.

  However, the writer does not need to wait for reader thread 3 to enter quiescent state. Reader thread 3 was not accessing D1 when the delete operation happened. So, reader thread 3 will not have a reference to the deleted entry.

  It can be noted that, the critical sections for D2 is a quiescent state for D1. i.e. for a given data structure Dx, any point in the thread execution that does not reference Dx is a quiescent state.

  Since memory is not freed immediately, there might be a need for provisioning of additional memory, depending on the application requirements.

• 2、Factors affecting the RCU mechanism

  It is important to make sure that this library keeps the overhead of identifying the end of grace period and subsequent freeing of memory, to a minimum. The following paras explain how grace period and critical section affect this overhead.
  Hence, we need the characteristics of a small grace period and large critical section。

• 3、RCU in DPDK

  If required, the application can create one QS variable per data structure to help it track the end of grace period for each data structure. This helps keep the length of grace period to a minimum.

• 4、How to use this library

• 5、Resource reclamation framework for DPDK

  Lock-free algorithms place additional burden of resource reclamation on the application. When a writer deletes an entry from a data structure, the writer:
  a、Has to start the grace period
  b、Has to store a reference to the deleted resources in a FIFO
  c、Should check if the readers have completed a grace period and free the resources.