QSBR and EBR library
Epoch-Based Reclamation (EBR) and Quiescent-State-Based Reclamation (QSBR) are synchronisation mechanisms which can be used for efficient memory/object reclamation (garbage collection) in concurrent environment. Conceptually they are very similar to the read-copy-update (RCU) mechanism.
EBR and QSBR are simpler, more lightweight and often faster than RCU. However, each thread must register itself when using these mechanisms. EBR allows user to mark the critical code paths without the need to periodically indicate the quiescent state. It is slightly slower than QSBR due to the need to issue a memory barrier on the reader side. QSBR is more lightweight, but each thread must manually indicate the quiescent state i.e. threads must periodically pass a checkpoint where they call a dedicated function. In many applications, such approach can be practical.
A typical use case of the EBR or QSBR would be together with lock-free data structures. This library provides raw EBR and QSBR mechanisms as well as a higher level garbage collection (GC) interface based on EBR.
The implementation is written in C11 and distributed under the 2-clause BSD license.
References:
K. Fraser, Practical lock-freedom,
Technical Report UCAM-CL-TR-579, February 2004
https://www.cl.cam.ac.uk/techreports/UCAM-CL-TR-579.pdf
T. E. Hart, P. E. McKenney, A.D. Brown,
Making Lockless Synchronization Fast: Performance Implications of Memory Reclamation.
Parallel and Distributed Processing Symposium, April 2006.
http://csng.cs.toronto.edu/publication_files/0000/0165/ipdps06.pdf
ebr_t *ebr_create(void)
void ebr_destroy(ebr_t *ebr)
int ebr_register(ebr_t *ebr)
ebr_enter/ebr_exit
) must register.void ebr_unregister(ebr_t *ebr)
void ebr_enter(ebr_t *ebr)
void ebr_exit(ebr_t *ebr)
bool ebr_sync(ebr_t *ebr, unsigned *gc_epoch)
true
if
a new epoch is announced and false
otherwise. In either case, the
epoch available for reclamation is returned. The number of epochs
is defined by the EBR_EPOCHS
constant and the epoch value is
0 <= epoch < EBR_EPOCHS
.ebr_staging_epoch
and ebr_gc_epoch
would be a part of the same
serialised path.unsigned ebr_staging_epoch(ebr_t *ebr)
ebr_sync
calls.unsigned ebr_gc_epoch(ebr_t *ebr)
ebr_sync
call. Note that these two functions would require the same
form of serialisation.void ebr_full_sync(ebr_t *ebr, unsigned msec_retry)
msec_retry
milliseconds before trying
again if there are objects which cannot be reclaimed immediately. If
this value is zero, then it will invoke sched_yield(2)
before retrying.bool ebr_incrit_p(ebr_t *ebr)
true
if the current worker is in the critical path, i.e.
called ebr_enter()
; otherwise, returns false
. This routine should
generally only be used for diagnostic asserts.gc_t *gc_create(unsigned entry_off, gc_func_t reclaim, void *arg)
entry_off
argument is
an offset of the gc_entry_t
structure, which must be embedded in the
object; typically, this value would be offsetof(struct obj, gc_entry)
.
The entry structure may also be embedded at the beginning of the object
structure (offset being zero), should the caller need to support
different object types.gc_entry_t::next
member. If reclaim is NULL, then the default
logic invoked by the G/C mechanism will be calling the system free(3)
for each object. An arbitrary user pointer, specified by arg
, can
be passed to the reclamation function.void gc_destroy(gc_t *gc)
void gc_register(gc_t *gc)
void gc_crit_enter(gc_t *gc)
void gc_crit_exit(gc_t *gc)
void gc_limbo(gc_t *gc, void *obj)
void gc_cycle(gc_t *gc)
void gc_full(gc_t *gc, unsigned msec_retry)
msec_retry
milliseconds before
trying again, if there are objects which cannot be reclaimed immediately.The implementation was extensively tested on a 24-core x86 machine, see the stress test for the details on the technique.
The G/C mechanism should be created by some master thread.
typedef struct {
...
gc_entry_t gc_entry;
} obj_t;
static gc_t * gc;
void
some_sysinit(void)
{
gc = gc_create(offsetof(obj_t, gc_entry), NULL, NULL);
assert(gc != NULL);
...
}
An example code fragment of a reader thread:
gc_register(gc);
while (!exit) {
/*
* Some processing which references the object(s).
* The readers must indicate the critical path where
* they actively reference objects.
*/
gc_crit_enter(gc);
obj = object_lookup();
process_object(obj);
gc_crit_exit(gc);
}
Here is an example code fragment in a writer thread which illustrates how the object would be staged for destruction (reclamation):
/*
* Remove the object from the lock-free container. The
* object is no longer globally visible. Not it can be
* staged for destruction -- add it to the limbo list.
*/
obj = lockfree_remove(container, key);
gc_limbo(gc, obj);
...
/*
* Checkpoint: run a G/C cycle attempting to reclaim *some*
* objects previously added to the limbo list. This should be
* called periodically for incremental object reclamation.
*
* WARNING: All gc_cycle() calls must be serialised (using a
* mutex or by running in a single-threaded manner).
*/
gc_cycle(gc);
...
/*
* Eventually, a full G/C might have to be performed to ensure
* that all objects have been reclaimed. This call can block.
*/
gc_full(gc, 1); // sleep for 1 msec before re-checking
Just build the package, install it and link the library using the
-lqsbr
flag.
cd pkg && make rpm
cd pkg && make deb