src/rcu.h

   1 // SPDX-License-Identifier: MIT
   2 /*
   3  * Copyright 2022 Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
   4  */
   5
   6 #include <sched.h>
   7 #include <stdint.h>
   8 #include <pthread.h>
   9 #include <stdbool.h>
  10 #include <poll.h>
  11
  12 #define SIDE_CACHE_LINE_SIZE            256
  13
  14 struct side_rcu_percpu_count {
  15         uintptr_t begin;
  16         uintptr_t end;
  17 }  __attribute__((__aligned__(SIDE_CACHE_LINE_SIZE)));
  18
  19 struct side_rcu_cpu_gp_state {
  20         struct side_rcu_percpu_count count[2];
  21 };
  22
  23 struct side_rcu_gp_state {
  24         struct side_rcu_cpu_gp_state *percpu_state;
  25         int nr_cpus;
  26         unsigned int period;
  27         pthread_mutex_t gp_lock;
  28 };
  29
  30 //TODO: replace atomics by rseq (when available)
  31 //TODO: replace acquire/release by membarrier+compiler barrier (when available)
  32 //TODO: implement wait/wakeup for grace period using sys_futex
  33 static inline
  34 unsigned int side_rcu_read_begin(struct side_rcu_gp_state *gp_state)
  35 {
  36         int cpu = sched_getcpu();
  37         unsigned int period = __atomic_load_n(&gp_state->period, __ATOMIC_RELAXED);
  38
  39         if (cpu < 0)
  40                 cpu = 0;
  41         /*
  42          * This memory barrier (A) ensures that the contents of the
  43          * read-side critical section does not leak before the "begin"
  44          * counter increment. It pairs with memory barriers (D) and (E).
  45          *
  46          * This memory barrier (A) also ensures that the "begin"
  47          * increment is before the "end" increment. It pairs with memory
  48          * barrier (C). It is redundant with memory barrier (B) for that
  49          * purpose.
  50          */
  51         (void) __atomic_add_fetch(&gp_state->percpu_state[cpu].count[period].begin, 1, __ATOMIC_SEQ_CST);
  52         return period;
  53 }
  54
  55 static inline
  56 void side_rcu_read_end(struct side_rcu_gp_state *gp_state, unsigned int period)
  57 {
  58         int cpu = sched_getcpu();
  59
  60         if (cpu < 0)
  61                 cpu = 0;
  62         /*
  63          * This memory barrier (B) ensures that the contents of the
  64          * read-side critical section does not leak after the "end"
  65          * counter increment. It pairs with memory barriers (D) and (E).
  66          *
  67          * This memory barrier (B) also ensures that the "begin"
  68          * increment is before the "end" increment. It pairs with memory
  69          * barrier (C). It is redundant with memory barrier (A) for that
  70          * purpose.
  71          */
  72         (void) __atomic_add_fetch(&gp_state->percpu_state[cpu].count[period].end, 1, __ATOMIC_SEQ_CST);
  73 }
  74
  75 #define side_rcu_dereference(p) \
  76         __extension__ \
  77         ({ \
  78                 (__typeof__(p) _____side_v = __atomic_load_n(&(p), __ATOMIC_CONSUME); \
  79                 (_____side_v); \
  80         })
  81
  82 #define side_rcu_assign_pointer(p, v)   __atomic_store_n(&(p), v, __ATOMIC_RELEASE); \
  83
  84 /* active_readers is an input/output parameter. */
  85 static inline
  86 void check_active_readers(struct side_rcu_gp_state *gp_state, bool *active_readers)
  87 {
  88         uintptr_t sum[2] = { 0, 0 };    /* begin - end */
  89         int i;
  90
  91         for (i = 0; i < gp_state->nr_cpus; i++) {
  92                 struct side_rcu_cpu_gp_state *cpu_state = &gp_state->percpu_state[i];
  93
  94                 if (active_readers[0])
  95                         sum[0] -= __atomic_load_n(&cpu_state->count[0].end, __ATOMIC_RELAXED);
  96                 if (active_readers[1])
  97                         sum[1] -= __atomic_load_n(&cpu_state->count[1].end, __ATOMIC_RELAXED);
  98         }
  99
 100         /*
 101          * This memory barrier (C) pairs with either of memory barriers
 102          * (A) or (B) (one is sufficient).
 103          *
 104          * Read end counts before begin counts. Reading "end" before
 105          * "begin" counts ensures we never see an "end" without having
 106          * seen its associated "begin", because "begin" is always
 107          * incremented before "end", as guaranteed by memory barriers
 108          * (A) or (B).
 109          */
 110         __atomic_thread_fence(__ATOMIC_SEQ_CST);
 111
 112         for (i = 0; i < gp_state->nr_cpus; i++) {
 113                 struct side_rcu_cpu_gp_state *cpu_state = &gp_state->percpu_state[i];
 114
 115                 if (active_readers[0])
 116                         sum[0] += __atomic_load_n(&cpu_state->count[0].begin, __ATOMIC_RELAXED);
 117                 if (active_readers[1])
 118                         sum[1] += __atomic_load_n(&cpu_state->count[1].begin, __ATOMIC_RELAXED);
 119         }
 120         if (active_readers[0])
 121                 active_readers[0] = sum[0];
 122         if (active_readers[1])
 123                 active_readers[1] = sum[1];
 124 }
 125
 126 /*
 127  * Wait for previous period to have no active readers.
 128  *
 129  * active_readers is an input/output parameter.
 130  */
 131 static inline
 132 void wait_for_prev_period_readers(struct side_rcu_gp_state *gp_state, bool *active_readers)
 133 {
 134         unsigned int prev_period = gp_state->period ^ 1;
 135
 136         /*
 137          * If a prior active readers scan already observed that no
 138          * readers are present for the previous period, there is no need
 139          * to scan again.
 140          */
 141         if (!active_readers[prev_period])
 142                 return;
 143         /*
 144          * Wait for the sum of CPU begin/end counts to match for the
 145          * previous period.
 146          */
 147         for (;;) {
 148                 check_active_readers(gp_state, active_readers);
 149                 if (!active_readers[prev_period])
 150                         break;
 151                 /* Retry after 10ms. */
 152                 poll(NULL, 0, 10);
 153         }
 154 }
 155
 156 /*
 157  * The grace period completes when it observes that there are no active
 158  * readers within each of the periods.
 159  *
 160  * The active_readers state is initially true for each period, until the
 161  * grace period observes that no readers are present for each given
 162  * period, at which point the active_readers state becomes false.
 163  */
 164 static inline
 165 void side_rcu_wait_grace_period(struct side_rcu_gp_state *gp_state)
 166 {
 167         bool active_readers[2] = { true, true };
 168
 169         /*
 170          * This memory barrier (D) pairs with memory barriers (A) and
 171          * (B) on the read-side.
 172          *
 173          * It orders prior loads and stores before the "end"/"begin"
 174          * reader state loads. In other words, it orders prior loads and
 175          * stores before observation of active readers quiescence,
 176          * effectively ensuring that read-side critical sections which
 177          * exist after the grace period completes are ordered after
 178          * loads and stores performed before the grace period.
 179          */
 180         __atomic_thread_fence(__ATOMIC_SEQ_CST);
 181
 182         /*
 183          * First scan through all cpus, for both period. If no readers
 184          * are accounted for, we have observed quiescence and can
 185          * complete the grace period immediately.
 186          */
 187         check_active_readers(gp_state, active_readers);
 188         if (!active_readers[0] && !active_readers[1])
 189                 goto end;
 190
 191         pthread_mutex_lock(&gp_state->gp_lock);
 192
 193         wait_for_prev_period_readers(gp_state, active_readers);
 194         /*
 195          * If the reader scan detected that there are no readers in the
 196          * current period as well, we can complete the grace period
 197          * immediately.
 198          */
 199         if (!active_readers[gp_state->period])
 200                 goto unlock;
 201
 202         /* Flip period: 0 -> 1, 1 -> 0. */
 203         (void) __atomic_xor_fetch(&gp_state->period, 1, __ATOMIC_RELAXED);
 204
 205         wait_for_prev_period_readers(gp_state, active_readers);
 206 unlock:
 207         pthread_mutex_unlock(&gp_state->gp_lock);
 208 end:
 209         /*
 210          * This memory barrier (E) pairs with memory barriers (A) and
 211          * (B) on the read-side.
 212          *
 213          * It orders the "end"/"begin" reader state loads before
 214          * following loads and stores. In other words, it orders
 215          * observation of active readers quiescence before following
 216          * loads and stores, effectively ensuring that read-side
 217          * critical sections which existed prior to the grace period
 218          * are ordered before loads and stores performed after the grace
 219          * period.
 220          */
 221         __atomic_thread_fence(__ATOMIC_SEQ_CST);
 222 }