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 "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) + (1ULL << 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 (void) {
  43     int thread_index = GET_THREAD_INDEX();
  44     if (pending_[thread_index] == NULL) {
  45         pending_[thread_index] = fifo_alloc(RCU_QUEUE_SCALE);
  46         (void)SYNC_ADD(&num_threads_, 1);
  47     }
  48 }
  49
  50 void rcu_update (void) {
  51     int thread_index = GET_THREAD_INDEX();
  52     int next_thread_index = (thread_index + 1) % num_threads_;
  53     TRACE("r1", "rcu_update: updating thread %llu", next_thread_index, 0);
  54     int i;
  55     for (i = 0; i < num_threads_; ++i) {
  56         if (i == thread_index)
  57             continue;
  58
  59         // No need to post an update if the value hasn't changed
  60         if (rcu_[thread_index][i] == rcu_last_posted_[thread_index][i])
  61             continue;
  62
  63         uint64_t x = rcu_[thread_index][i];
  64         rcu_[next_thread_index][i] = rcu_last_posted_[thread_index][i] = x;
  65         TRACE("r2", "rcu_update: posted updated value (%llu) for thread %llu", x, i);
  66     }
  67
  68     // free
  69     fifo_t *q = pending_[thread_index];
  70     while (q->tail != rcu_[thread_index][thread_index]) {
  71         uint32_t i = MOD_SCALE(q->tail, q->scale);
  72         TRACE("r0", "rcu_update: freeing %p from queue at position %llu", q->x[i], q->tail);
  73         nbd_free(q->x[i]);
  74         q->tail++;
  75     }
  76 }
  77
  78 void rcu_defer_free (void *x) {
  79     assert(x);
  80     int thread_index = GET_THREAD_INDEX();
  81     fifo_t *q = pending_[thread_index];
  82     assert(MOD_SCALE(q->head + 1, q->scale) != MOD_SCALE(q->tail, q->scale));
  83     uint32_t i = MOD_SCALE(q->head, q->scale);
  84     q->x[i] = x;
  85     TRACE("r0", "rcu_defer_free: put %p on queue at position %llu", x, q->head);
  86     q->head++;
  87
  88     if (pending_[thread_index]->head - rcu_last_posted_[thread_index][thread_index] >= RCU_POST_THRESHOLD) {
  89         TRACE("r0", "rcu_defer_free: posting %llu", pending_[thread_index]->head, 0);
  90         int next_thread_index = (thread_index + 1) % num_threads_;
  91         rcu_[next_thread_index][thread_index] = pending_[thread_index]->head;
  92         rcu_last_posted_[thread_index][thread_index] = pending_[thread_index]->head;
  93     }
  94 }