Home

Awesome

Quiescent-State and Epoch based reclamation

Build Status

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 API

G/C API

Notes

The implementation was extensively tested on a 24-core x86 machine, see the stress test for the details on the technique.

Examples

G/C API example

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

Packages

Just build the package, install it and link the library using the -lqsbr flag.