2 * Written by Josh Dybnis and released to the public domain, as explained at
3 * http://creativecommons.org/licenses/publicdomain
5 * safe memory reclemation using a simple technique from rcu
9 #include "runtime_local.h"
14 #define RCU_POST_THRESHOLD 10
15 #define RCU_QUEUE_SCALE 20
24 static uint64_t rcu_[MAX_NUM_THREADS][MAX_NUM_THREADS] = {};
25 static uint64_t rcu_last_posted_[MAX_NUM_THREADS][MAX_NUM_THREADS] = {};
26 static fifo_t *pending_[MAX_NUM_THREADS] = {};
27 static int num_threads_ = 0;
29 static fifo_t *fifo_alloc(int scale) {
30 fifo_t *q = (fifo_t *)nbd_malloc(sizeof(fifo_t) + (1 << scale) * sizeof(void *));
31 memset(q, 0, sizeof(fifo_t));
38 static uint32_t fifo_index (fifo_t *q, uint32_t i) {
39 return i & MASK(q->scale);
42 static void fifo_enqueue (fifo_t *q, void *x) {
43 assert(fifo_index(q, q->head + 1) != fifo_index(q, q->tail));
44 uint32_t i = fifo_index(q, q->head++);
48 static void *fifo_dequeue (fifo_t *q) {
49 uint32_t i = fifo_index(q, q->tail++);
53 void rcu_thread_init (int id) {
54 assert(id < MAX_NUM_THREADS);
55 if (pending_[id] == NULL) {
56 pending_[id] = fifo_alloc(RCU_QUEUE_SCALE);
57 SYNC_ADD(&num_threads_, 1);
61 static void rcu_post (uint64_t x) {
62 LOCALIZE_THREAD_LOCAL(tid_, int);
63 if (x - rcu_last_posted_[tid_][tid_] < RCU_POST_THRESHOLD)
66 int next_thread_id = (tid_ + 1) % num_threads_;
68 TRACE("r0", "rcu_post: %llu", x, 0);
69 rcu_[next_thread_id][tid_] = rcu_last_posted_[tid_][tid_] = x;
72 void rcu_update (void) {
73 LOCALIZE_THREAD_LOCAL(tid_, int);
74 assert(tid_ < num_threads_);
75 int next_thread_id = (tid_ + 1) % num_threads_;
77 for (i = 0; i < num_threads_; ++i) {
81 // No need to post an update if the value hasn't changed
82 if (rcu_[tid_][i] == rcu_last_posted_[tid_][i])
85 uint64_t x = rcu_[tid_][i];
86 rcu_[next_thread_id][i] = rcu_last_posted_[tid_][i] = x;
90 while (pending_[tid_]->tail != rcu_[tid_][tid_]) {
91 nbd_free(fifo_dequeue(pending_[tid_]));
95 void nbd_defer_free (void *x) {
96 LOCALIZE_THREAD_LOCAL(tid_, int);
97 fifo_enqueue(pending_[tid_], x);
98 TRACE("r0", "nbd_defer_free: put %p on queue at position %llu", x, pending_[tid_]->head);
99 rcu_post(pending_[tid_]->head);
107 #define NUM_ITERATIONS 10000000
109 typedef struct node {
113 typedef struct lifo {
117 static volatile int wait_;
120 static lifo_t *lifo_alloc (void) {
121 lifo_t *stk = (lifo_t *)nbd_malloc(sizeof(lifo_t));
122 memset(stk, 0, sizeof(lifo_t));
126 static void lifo_aba_push (lifo_t *stk, node_t *x) {
129 head = ((volatile lifo_t *)stk)->head;
130 ((volatile node_t *)x)->next = head;
131 } while (__sync_val_compare_and_swap(&stk->head, head, x) != head);
134 node_t *lifo_aba_pop (lifo_t *stk) {
137 head = ((volatile lifo_t *)stk)->head;
140 } while (__sync_val_compare_and_swap(&stk->head, head, head->next) != head);
145 node_t *node_alloc (void) {
146 node_t *node = (node_t *)nbd_malloc(sizeof(node_t));
147 memset(node, 0, sizeof(node_t));
151 void *worker (void *arg) {
152 int id = (int)(size_t)arg;
153 unsigned int rand_seed = (unsigned int)id + 1;
155 // Wait for all the worker threads to be ready.
156 __sync_fetch_and_add(&wait_, -1);
160 for (i = 0; i < NUM_ITERATIONS; ++ i) {
161 int n = rand_r(&rand_seed);
163 lifo_aba_push(stk_, node_alloc());
165 node_t *x = lifo_aba_pop(stk_);
176 int main (int argc, char **argv) {
178 //lwt_set_trace_level("m0r0");
184 num_threads = strtol(argv[1], NULL, 10);
186 fprintf(stderr, "%s: Invalid argument for number of threads\n", argv[0]);
189 if (num_threads <= 0) {
190 fprintf(stderr, "%s: Number of threads must be at least 1\n", argv[0]);
198 pthread_t thread[num_threads];
199 for (int i = 0; i < num_threads; ++i) {
200 int rc = nbd_thread_create(thread + i, i, worker, (void *)(size_t)i);
201 if (rc != 0) { perror("pthread_create"); return rc; }
203 for (int i = 0; i < num_threads; ++i) {
204 pthread_join(thread[i], NULL);