2 * Written by Josh Dybnis and released to the public domain, as explained at
3 * http://creativecommons.org/licenses/publicdomain
5 * safe memory reclamation using a simple technique from rcu
7 * WARNING: not robust enough for real-world use
17 #define RCU_POST_THRESHOLD 10
18 #define RCU_QUEUE_SCALE 20
27 #define MOD_SCALE(x, b) ((x) & MASK(b))
28 static uint64_t rcu_[MAX_NUM_THREADS][MAX_NUM_THREADS] = {};
29 static uint64_t rcu_last_posted_[MAX_NUM_THREADS][MAX_NUM_THREADS] = {};
30 static fifo_t *pending_[MAX_NUM_THREADS] = {};
31 static int num_threads_ = 0;
33 static fifo_t *fifo_alloc(int scale) {
34 fifo_t *q = (fifo_t *)nbd_malloc(sizeof(fifo_t) + (1ULL << scale) * sizeof(void *));
35 memset(q, 0, sizeof(fifo_t));
42 void rcu_thread_init (void) {
43 int thread_index = GET_THREAD_INDEX();
44 if (pending_[thread_index] == NULL) {
45 pending_[thread_index] = fifo_alloc(RCU_QUEUE_SCALE);
46 (void)SYNC_ADD(&num_threads_, 1);
50 void rcu_update (void) {
51 int thread_index = GET_THREAD_INDEX();
52 int next_thread_index = (thread_index + 1) % num_threads_;
53 TRACE("r1", "rcu_update: updating thread %llu", next_thread_index, 0);
55 for (i = 0; i < num_threads_; ++i) {
56 if (i == thread_index)
59 // No need to post an update if the value hasn't changed
60 if (rcu_[thread_index][i] == rcu_last_posted_[thread_index][i])
63 uint64_t x = rcu_[thread_index][i];
64 rcu_[next_thread_index][i] = rcu_last_posted_[thread_index][i] = x;
65 TRACE("r2", "rcu_update: posted updated value (%llu) for thread %llu", x, i);
69 fifo_t *q = pending_[thread_index];
70 while (q->tail != rcu_[thread_index][thread_index]) {
71 uint32_t i = MOD_SCALE(q->tail, q->scale);
72 TRACE("r0", "rcu_update: freeing %p from queue at position %llu", q->x[i], q->tail);
78 void rcu_defer_free (void *x) {
80 int thread_index = GET_THREAD_INDEX();
81 fifo_t *q = pending_[thread_index];
82 assert(MOD_SCALE(q->head + 1, q->scale) != MOD_SCALE(q->tail, q->scale));
83 uint32_t i = MOD_SCALE(q->head, q->scale);
85 TRACE("r0", "rcu_defer_free: put %p on queue at position %llu", x, q->head);
88 if (pending_[thread_index]->head - rcu_last_posted_[thread_index][thread_index] >= RCU_POST_THRESHOLD) {
89 TRACE("r0", "rcu_defer_free: posting %llu", pending_[thread_index]->head, 0);
90 int next_thread_index = (thread_index + 1) % num_threads_;
91 rcu_[next_thread_index][thread_index] = pending_[thread_index]->head;
92 rcu_last_posted_[thread_index][thread_index] = pending_[thread_index]->head;