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
16 #define RCU_POST_THRESHOLD 10
17 #define RCU_QUEUE_SCALE 20
26 static uint64_t rcu_[MAX_NUM_THREADS][MAX_NUM_THREADS] = {};
27 static uint64_t rcu_last_posted_[MAX_NUM_THREADS][MAX_NUM_THREADS] = {};
28 static fifo_t *pending_[MAX_NUM_THREADS] = {};
29 static int num_threads_ = 0;
31 static fifo_t *fifo_alloc(int scale) {
32 fifo_t *q = (fifo_t *)nbd_malloc(sizeof(fifo_t) + (1 << scale) * sizeof(void *));
33 memset(q, 0, sizeof(fifo_t));
40 static uint32_t fifo_index (fifo_t *q, uint32_t i) {
41 return i & MASK(q->scale);
44 static void fifo_enqueue (fifo_t *q, void *x) {
45 assert(fifo_index(q, q->head + 1) != fifo_index(q, q->tail));
46 uint32_t i = fifo_index(q, q->head++);
50 static void *fifo_dequeue (fifo_t *q) {
51 uint32_t i = fifo_index(q, q->tail++);
55 void rcu_thread_init (int id) {
56 assert(id < MAX_NUM_THREADS);
57 if (pending_[id] == NULL) {
58 pending_[id] = fifo_alloc(RCU_QUEUE_SCALE);
59 SYNC_ADD(&num_threads_, 1);
63 static void rcu_post (uint64_t x) {
64 LOCALIZE_THREAD_LOCAL(tid_, int);
65 if (x - rcu_last_posted_[tid_][tid_] < RCU_POST_THRESHOLD)
68 int next_thread_id = (tid_ + 1) % num_threads_;
70 TRACE("r0", "rcu_post: %llu", x, 0);
71 rcu_[next_thread_id][tid_] = rcu_last_posted_[tid_][tid_] = x;
74 void rcu_update (void) {
75 LOCALIZE_THREAD_LOCAL(tid_, int);
76 assert(tid_ < num_threads_);
77 int next_thread_id = (tid_ + 1) % num_threads_;
79 for (i = 0; i < num_threads_; ++i) {
83 // No need to post an update if the value hasn't changed
84 if (rcu_[tid_][i] == rcu_last_posted_[tid_][i])
87 uint64_t x = rcu_[tid_][i];
88 rcu_[next_thread_id][i] = rcu_last_posted_[tid_][i] = x;
92 while (pending_[tid_]->tail != rcu_[tid_][tid_]) {
93 nbd_free(fifo_dequeue(pending_[tid_]));
97 void nbd_defer_free (void *x) {
98 LOCALIZE_THREAD_LOCAL(tid_, int);
99 fifo_enqueue(pending_[tid_], x);
100 TRACE("r0", "nbd_defer_free: put %p on queue at position %llu", x, pending_[tid_]->head);
101 rcu_post(pending_[tid_]->head);