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) + (1 << scale) * sizeof(void *));
35 memset(q, 0, sizeof(fifo_t));
42 void rcu_thread_init (int id) {
43 assert(id < MAX_NUM_THREADS);
44 if (pending_[id] == NULL) {
45 pending_[id] = fifo_alloc(RCU_QUEUE_SCALE);
46 SYNC_ADD(&num_threads_, 1);
50 void rcu_update (void) {
51 LOCALIZE_THREAD_LOCAL(tid_, int);
52 assert(tid_ < num_threads_);
53 int next_thread_id = (tid_ + 1) % num_threads_;
55 for (i = 0; i < num_threads_; ++i) {
59 // No need to post an update if the value hasn't changed
60 if (rcu_[tid_][i] == rcu_last_posted_[tid_][i])
63 uint64_t x = rcu_[tid_][i];
64 rcu_[next_thread_id][i] = rcu_last_posted_[tid_][i] = x;
68 fifo_t *q = pending_[tid_];
69 while (q->tail != rcu_[tid_][tid_]) {
70 uint32_t i = MOD_SCALE(q->tail, q->scale);
71 TRACE("r0", "rcu_update: freeing %p from queue at position %llu", q->x[i], q->tail);
77 void rcu_defer_free (void *x) {
79 LOCALIZE_THREAD_LOCAL(tid_, int);
80 fifo_t *q = pending_[tid_];
81 assert(MOD_SCALE(q->head + 1, q->scale) != MOD_SCALE(q->tail, q->scale));
82 uint32_t i = MOD_SCALE(q->head, q->scale);
84 TRACE("r0", "rcu_defer_free: put %p on queue at position %llu", x, q->head);
87 if (pending_[tid_]->head - rcu_last_posted_[tid_][tid_] >= RCU_POST_THRESHOLD) {
88 TRACE("r0", "rcu_defer_free: posting %llu", pending_[tid_]->head, 0);
89 int next_thread_id = (tid_ + 1) % num_threads_;
90 rcu_[next_thread_id][tid_] = rcu_last_posted_[tid_][tid_] = pending_[tid_]->head;