click_rcu< T > Class Template Reference

#include <multithread.hh>

Public Member Functions
	click_rcu (T v)
void	initialize (T v)
const T &	read_begin (int &rcu_current_local)
void	read_end (const int &rcu_current_local)
T	read ()
T &	write_begin ()
void	write_commit ()
void	write_abort ()
void	write (const T &v)

Protected Attributes
atomic_uint32_t	refcnt [2]
T	storage [2]
volatile int	rcu_current

Detailed Description

template<typename T>
class click_rcu< T >

click_rcu is the ultimate version of the RCU series, the more protected one which will always work but also the slowest one.

The problem of unprotected_rcu* is solved by keeping a reference count of the amount of readers using any current bucket. The writer will wait for all readers to finish before overwriting the next available slot.

Here, the writers exclude each other by setting the refcnt to -1 atomically, if the value was 0. They will spinloop around the refcnt until each other writer has finished.

It is not as bad as a critical section/interrupt like in kernel, but those lock operation still have a non-negligeable cost.

It may be difficult to see that writer cannot overwrite a bucket that is currently being accessed, here is a helping example : A reads index B write and advance C write and advance, check refcnt[A], CAS 0 -> -1 A writes refcnt[A] -> CAS fail

The ring has 2 values, so one writer can update one bucket while readers may still read the other bucket.

Member Function Documentation

read_begin()

template<typename T >

const T & click_rcu< T >::read_begin ( int &  rcu_current_local )

inline

A loop is needed to avoid a race condition where thread A reads rcu_current, then writer B does a full write, start a second write before A update the refcnt. A would then inc the refcnt, and get a reference while B is in fact writing that bucket.

The solution is the following one: When the refcnt for the next bucket is 0, the writer is writing -1 as the refcnt. This is done atomicly using a CAS instruction.

In the reader, we check if the refcnt is -1 (current write), and if not we CAS refcnt+1. We loop until the CAS worked so we know that we made a "refcnt++" without any writer starting to write in the bucket.

Also, the same rcu_current_local must be passed to read_end as we need to down the actual refcnt we incremented, and rcu_current may be incremented by 1 before we finish our reading.

write_begin()

template<typename T >

T & click_rcu< T >::write_begin ( )

inline

No need for lock of writers anymore. We atomicly set the refcnt to -1 if the value is 0, if another writer is writing, it would have done the same. If no readers are reading, the refcnt would not be 0.

---

The documentation for this class was generated from the following file:

• include/click/multithread.hh