use NULL instead of a sentinal node in skiplist and list
[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 "runtime_local.h"
12 #include "lwt.h"
13 #include "mem.h"
14 #include "tls.h"
15
16 #define RCU_POST_THRESHOLD 10
17 #define RCU_QUEUE_SCALE 20
18
19 typedef struct fifo {
20     uint32_t head;
21     uint32_t tail;
22     uint32_t scale;
23     void *x[0];
24 } fifo_t;
25
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;
30
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));
34     q->scale = scale;
35     q->head = 0;
36     q->tail = 0;
37     return q;
38 }
39
40 static uint32_t fifo_index (fifo_t *q, uint32_t i) {
41     return i & MASK(q->scale);
42 }
43
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++);
47     q->x[i] = x;
48 }
49
50 static void *fifo_dequeue (fifo_t *q) {
51     uint32_t i = fifo_index(q, q->tail++);
52     return q->x[i];
53 }
54
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);
60     }
61 }
62
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)
66         return;
67
68     int next_thread_id = (tid_ + 1) % num_threads_;
69
70     TRACE("r0", "rcu_post: %llu", x, 0);
71     rcu_[next_thread_id][tid_] = rcu_last_posted_[tid_][tid_] = x;
72 }
73
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_;
78     int i;
79     for (i = 0; i < num_threads_; ++i) {
80         if (i == tid_)
81             continue;
82
83         // No need to post an update if the value hasn't changed
84         if (rcu_[tid_][i] == rcu_last_posted_[tid_][i])
85             continue;
86
87         uint64_t x = rcu_[tid_][i];
88         rcu_[next_thread_id][i] = rcu_last_posted_[tid_][i] = x;
89     }
90
91     // free
92     while (pending_[tid_]->tail != rcu_[tid_][tid_]) {
93         nbd_free(fifo_dequeue(pending_[tid_]));
94     }
95 }
96
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);
102 }
103
104 #ifdef MAKE_rcu_test
105 #include <errno.h>
106 #include <stdio.h>
107 #include "runtime.h"
108
109 #define NUM_ITERATIONS 10000000
110
111 typedef struct node {
112     struct node *next;
113 } node_t;
114
115 typedef struct lifo {
116     node_t *head;
117 } lifo_t;
118
119 static volatile int wait_;
120 static lifo_t *stk_;
121
122 static lifo_t *lifo_alloc (void) {
123     lifo_t *stk = (lifo_t *)nbd_malloc(sizeof(lifo_t)); 
124     memset(stk, 0, sizeof(lifo_t));
125     return stk;
126 }
127
128 static void lifo_aba_push (lifo_t *stk, node_t *x) {
129     node_t *head;
130     do {
131         head = ((volatile lifo_t *)stk)->head;
132         ((volatile node_t *)x)->next = head;
133     } while (__sync_val_compare_and_swap(&stk->head, head, x) != head);
134 }
135
136 node_t *lifo_aba_pop (lifo_t *stk) {
137     node_t *head;
138     do {
139         head = ((volatile lifo_t *)stk)->head;
140         if (head == NULL)
141             return NULL;
142     } while (__sync_val_compare_and_swap(&stk->head, head, head->next) != head);
143     head->next = NULL;
144     return head;
145 }
146
147 node_t *node_alloc (void) {
148     node_t *node = (node_t *)nbd_malloc(sizeof(node_t));
149     memset(node, 0, sizeof(node_t));
150     return node;
151 }
152
153 void *worker (void *arg) {
154     int id = (int)(size_t)arg;
155     unsigned int rand_seed = (unsigned int)id + 1;
156
157     // Wait for all the worker threads to be ready.
158     __sync_fetch_and_add(&wait_, -1);
159     do {} while (wait_); 
160
161     int i;
162     for (i = 0; i < NUM_ITERATIONS; ++ i) {
163         int n = rand_r(&rand_seed);
164         if (n & 0x1) {
165             lifo_aba_push(stk_, node_alloc());
166         } else {
167             node_t *x = lifo_aba_pop(stk_);
168             if (x) {
169                 nbd_defer_free(x);
170             }
171         }
172         rcu_update();
173     }
174
175     return NULL;
176 }
177
178 int main (int argc, char **argv) {
179     nbd_init();
180     //lwt_set_trace_level("m0r0");
181
182     int num_threads = 2;
183     if (argc == 2)
184     {
185         errno = 0;
186         num_threads = strtol(argv[1], NULL, 10);
187         if (errno) {
188             fprintf(stderr, "%s: Invalid argument for number of threads\n", argv[0]);
189             return -1;
190         }
191         if (num_threads <= 0) {
192             fprintf(stderr, "%s: Number of threads must be at least 1\n", argv[0]);
193             return -1;
194         }
195     }
196
197     stk_ = lifo_alloc();
198     wait_ = num_threads;
199
200     pthread_t thread[num_threads];
201     for (int i = 0; i < num_threads; ++i) {
202         int rc = nbd_thread_create(thread + i, i, worker, (void *)(size_t)i);
203         if (rc != 0) { perror("pthread_create"); return rc; }
204     }
205     for (int i = 0; i < num_threads; ++i) {
206         pthread_join(thread[i], NULL);
207     }
208
209     return 0;
210 }
211 #endif//rcu_test