]> pd.if.org Git - nbds/blob - runtime/rcu.c
3e74986ff025819cf1ac838a6498b32d70978716
[nbds] / runtime / rcu.c
1 /* 
2  * Written by Josh Dybnis and released to the public domain, as explained at
3  * http://creativecommons.org/licenses/publicdomain
4  *
5  * safe memory reclamation using a simple technique from rcu
6  *
7  * WARNING: not robust enough for real-world use
8  */
9 #include <string.h>
10 #include "common.h"
11 #include "rlocal.h"
12 #include "lwt.h"
13 #include "mem.h"
14 #include "tls.h"
15 #include "rcu.h"
16
17 #define RCU_POST_THRESHOLD 10
18 #define RCU_QUEUE_SCALE 20
19
20 typedef struct fifo {
21     uint32_t head;
22     uint32_t tail;
23     uint32_t scale;
24     void *x[0];
25 } fifo_t;
26
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;
32
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));
36     q->scale = scale;
37     q->head = 0;
38     q->tail = 0;
39     return q;
40 }
41
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);
47     }
48 }
49
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_;
54     int i;
55     for (i = 0; i < num_threads_; ++i) {
56         if (i == tid_)
57             continue;
58
59         // No need to post an update if the value hasn't changed
60         if (rcu_[tid_][i] == rcu_last_posted_[tid_][i])
61             continue;
62
63         uint64_t x = rcu_[tid_][i];
64         rcu_[next_thread_id][i] = rcu_last_posted_[tid_][i] = x;
65     }
66
67     // free
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);
72         nbd_free(q->x[i]);
73         q->tail++;
74     }
75 }
76
77 void rcu_defer_free (void *x) {
78     assert(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);
83     q->x[i] = x;
84     TRACE("r0", "rcu_defer_free: put %p on queue at position %llu", x, q->head);
85     q->head++;
86
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;
91     }
92 }