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) + (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 }