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