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
  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 }