README.md
1# Quiescent-State and Epoch based reclamation
2
3[](https://travis-ci.org/rmind/libqsbr)
4
5Epoch-Based Reclamation (EBR) and Quiescent-State-Based Reclamation (QSBR)
6are synchronisation mechanisms which can be used for efficient memory/object
7reclamation (garbage collection) in concurrent environment. Conceptually
8they are very similar to the read-copy-update (RCU) mechanism.
9
10EBR and QSBR are simpler, more lightweight and often faster than RCU.
11However, each thread must register itself when using these mechanisms.
12EBR allows user to mark the critical code paths without the need to
13periodically indicate the quiescent state. It is slightly slower than
14QSBR due to the need to issue a memory barrier on the reader side.
15QSBR is more lightweight, but each thread must manually indicate the
16quiescent state i.e. threads must periodically pass a checkpoint where
17they call a dedicated function. In many applications, such approach
18can be practical.
19
20A typical use case of the EBR or QSBR would be together with lock-free
21data structures. This library provides raw EBR and QSBR mechanisms as
22well as a higher level garbage collection (GC) interface based on EBR.
23
24The implementation is written in C11 and distributed under the
252-clause BSD license.
26
27References:
28
29 K. Fraser, Practical lock-freedom,
30 Technical Report UCAM-CL-TR-579, February 2004
31 https://www.cl.cam.ac.uk/techreports/UCAM-CL-TR-579.pdf
32
33 T. E. Hart, P. E. McKenney, A.D. Brown,
34 Making Lockless Synchronization Fast: Performance Implications of Memory Reclamation.
35 Parallel and Distributed Processing Symposium, April 2006.
36 http://csng.cs.toronto.edu/publication_files/0000/0165/ipdps06.pdf
37
38## EBR API
39
40* `ebr_t *ebr_create(void)`
41 * Construct a new EBR object.
42
43* `void ebr_destroy(ebr_t *ebr)`
44 * Destroy the EBR object.
45
46* `int ebr_register(ebr_t *ebr)`
47 * Register the current thread for EBR synchronisation. Returns 0 on
48 success and -1 on failure. Note: each reader thread (i.e. callers of
49 `ebr_enter/ebr_exit`) **must** register.
50
51* `void ebr_unregister(ebr_t *ebr)`
52 * Remove the current thread from the EBR synchronisation list. Each
53 registered thread must leave the list before the exit (this may be not
54 necessary if all threads exit together). It is the caller's responsibility
55 to synchronise the thread exit, if needed.
56
57* `void ebr_enter(ebr_t *ebr)`
58 * Mark the entrance to the critical path. Typically, this would be
59 used by the readers when accessing some shared data; reclamation of
60 objects is guaranteed to not occur in the critical path.
61 * Note: the EBR mechanism is not limited to the concept of "objects".
62 It can be any form of reference to the globally shared data.
63
64* `void ebr_exit(ebr_t *ebr)`
65 * Mark the exit of the critical path. Reclamation of the shared data
66 may occur after this point.
67
68* `bool ebr_sync(ebr_t *ebr, unsigned *gc_epoch)`
69 * Attempt to synchronise and announce a new epoch. Returns `true` if
70 a new epoch is announced and `false` otherwise. In either case, the
71 _epoch_ available for reclamation is returned. The number of epochs
72 is defined by the `EBR_EPOCHS` constant and the epoch value is
73 `0 <= epoch < EBR_EPOCHS`.
74 * The synchronisation points must be serialised (e.g. if there are
75 multiple G/C workers or other writers). Generally, calls to
76 `ebr_staging_epoch` and `ebr_gc_epoch` would be a part of the same
77 serialised path.
78
79* `unsigned ebr_staging_epoch(ebr_t *ebr)`
80 * Returns an _epoch_ where objects can be staged for reclamation.
81 This can be used as a reference value for the pending queue/tag, used
82 to postpone the reclamation until this epoch becomes available for G/C.
83 Note that this function would normally be serialised together with
84 the `ebr_sync` calls.
85
86* `unsigned ebr_gc_epoch(ebr_t *ebr)`
87 * Returns the _epoch_ available for reclamation, i.e. the epoch where
88 it is guaranteed that the objects are safe to be reclaimed/destroyed.
89 The _epoch_ value will be the same as returned by the last successful
90 `ebr_sync` call. Note that these two functions would require the same
91 form of serialisation.
92
93* `void ebr_full_sync(ebr_t *ebr, unsigned msec_retry)`
94 * Perform full synchronisation ensuring that all objects which are no
95 longer globally visible (and potentially staged for reclamation) at the
96 time of calling this routine will be safe to reclaim/destroy after this
97 synchronisation routine completes and returns. Note: the synchronisation
98 may take across multiple epochs.
99 * This function will block for `msec_retry` milliseconds before trying
100 again if there are objects which cannot be reclaimed immediately. If
101 this value is zero, then it will invoke `sched_yield(2)` before retrying.
102
103* `bool ebr_incrit_p(ebr_t *ebr)`
104 * Returns `true` if the current worker is in the critical path, i.e.
105 called `ebr_enter()`; otherwise, returns `false`. This routine should
106 generally only be used for diagnostic asserts.
107
108
109## G/C API
110
111* `gc_t *gc_create(unsigned entry_off, gc_func_t reclaim, void *arg)`
112 * Construct a new G/C management object. The `entry_off` argument is
113 an offset of the `gc_entry_t` structure, which must be embedded in the
114 object; typically, this value would be `offsetof(struct obj, gc_entry)`.
115 The entry structure may also be embedded at the beginning of the object
116 structure (offset being zero), should the caller need to support
117 different object types.
118 * A custom reclamation function can be used for object destruction.
119 This function must process a list of objects, since a chain of objects
120 may be passed for reclamation; the user can iterate the chain using
121 the `gc_entry_t::next` member. If _reclaim_ is NULL, then the default
122 logic invoked by the G/C mechanism will be calling the system `free(3)`
123 for each object. An arbitrary user pointer, specified by `arg`, can
124 be passed to the reclamation function.
125
126* `void gc_destroy(gc_t *gc)`
127 * Destroy the G/C management object.
128
129* `void gc_register(gc_t *gc)`
130 * Register the current thread as a user of the G/C mechanism.
131 All threads having critical paths to reference the objects must register.
132
133* `void gc_crit_enter(gc_t *gc)`
134 * Enter the critical path where objects may be actively referenced.
135 This prevents the G/C mechanism from reclaiming (destroying) the object.
136
137* `void gc_crit_exit(gc_t *gc)`
138 * Exit the critical path, indicating that the target objects no
139 longer have active references and the G/C mechanism may consider
140 them for reclamation.
141
142* `void gc_limbo(gc_t *gc, void *obj)`
143 * Insert the object into a "limbo" list, staging it for reclamation
144 (destruction). This is a request to reclaim the object once it is
145 guaranteed that there are no threads referencing it in the critical path.
146
147* `void gc_cycle(gc_t *gc)`
148 * Run a G/C cycle attempting to reclaim some objects which were
149 added to the limbo list. The objects which are no longer referenced
150 are not guaranteed to be reclaimed immediately after one cycle. This
151 function does not block and is expected to be called periodically for
152 an incremental object reclamation.
153
154* `void gc_full(gc_t *gc, unsigned msec_retry)`
155 * Run a full G/C in order to ensure that all staged objects have been
156 reclaimed. This function will block for `msec_retry` milliseconds before
157 trying again, if there are objects which cannot be reclaimed immediately.
158
159## Notes
160
161The implementation was extensively tested on a 24-core x86 machine,
162see [the stress test](src/t_stress.c) for the details on the technique.
163
164## Examples
165
166### G/C API example
167
168The G/C mechanism should be created by some master thread.
169```c
170typedef struct {
171 ...
172 gc_entry_t gc_entry;
173} obj_t;
174
175static gc_t * gc;
176
177void
178some_sysinit(void)
179{
180 gc = gc_create(offsetof(obj_t, gc_entry), NULL, NULL);
181 assert(gc != NULL);
182 ...
183}
184```
185
186An example code fragment of a reader thread:
187```c
188 gc_register(gc);
189
190 while (!exit) {
191 /*
192 * Some processing which references the object(s).
193 * The readers must indicate the critical path where
194 * they actively reference objects.
195 */
196 gc_crit_enter(gc);
197 obj = object_lookup();
198 process_object(obj);
199 gc_crit_exit(gc);
200 }
201```
202
203Here is an example code fragment in a writer thread which illustrates
204how the object would be staged for destruction (reclamation):
205```c
206 /*
207 * Remove the object from the lock-free container. The
208 * object is no longer globally visible. Not it can be
209 * staged for destruction -- add it to the limbo list.
210 */
211 obj = lockfree_remove(container, key);
212 gc_limbo(gc, obj);
213 ...
214
215 /*
216 * Checkpoint: run a G/C cycle attempting to reclaim *some*
217 * objects previously added to the limbo list. This should be
218 * called periodically for incremental object reclamation.
219 *
220 * WARNING: All gc_cycle() calls must be serialised (using a
221 * mutex or by running in a single-threaded manner).
222 */
223 gc_cycle(gc);
224 ...
225
226 /*
227 * Eventually, a full G/C might have to be performed to ensure
228 * that all objects have been reclaimed. This call can block.
229 */
230 gc_full(gc, 1); // sleep for 1 msec before re-checking
231```
232
233## Packages
234
235Just build the package, install it and link the library using the
236`-lqsbr` flag.
237* RPM (tested on RHEL/CentOS 7): `cd pkg && make rpm`
238* DEB (tested on Debian 9): `cd pkg && make deb`
239
){kind=link}