pd.if.org Git - nbds/blob - 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