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 acquire MO pairs with the release fence at the end of
  43          * side_rcu_wait_grace_period().
  44          */
  45         (void) __atomic_add_fetch(&gp_state->percpu_state[cpu].count[period].begin, 1, __ATOMIC_SEQ_CST);
  46         return period;
  47 }
  48
  49 static inline
  50 void side_rcu_read_end(struct side_rcu_gp_state *gp_state, unsigned int period)
  51 {
  52         int cpu = sched_getcpu();
  53
  54         if (cpu < 0)
  55                 cpu = 0;
  56         /*
  57          * This release MO pairs with the acquire fence at the beginning
  58          * of side_rcu_wait_grace_period().
  59          */
  60         (void) __atomic_add_fetch(&gp_state->percpu_state[cpu].count[period].end, 1, __ATOMIC_SEQ_CST);
  61 }
  62
  63 #define side_rcu_dereference(p) \
  64         __extension__ \
  65         ({ \
  66                 (__typeof__(p) _____side_v = __atomic_load_n(&(p), __ATOMIC_CONSUME); \
  67                 (_____side_v); \
  68         })
  69
  70 #define side_rcu_assign_pointer(p, v)   __atomic_store_n(&(p), v, __ATOMIC_RELEASE); \
  71
  72 /* active_readers is an input/output parameter. */
  73 static inline
  74 void check_active_readers(struct side_rcu_gp_state *gp_state, bool *active_readers)
  75 {
  76         uintptr_t sum[2] = { 0, 0 };    /* begin - end */
  77         int i;
  78
  79         for (i = 0; i < gp_state->nr_cpus; i++) {
  80                 struct side_rcu_cpu_gp_state *cpu_state = &gp_state->percpu_state[i];
  81
  82                 sum[0] -= __atomic_load_n(&cpu_state->count[0].end, __ATOMIC_RELAXED);
  83                 sum[1] -= __atomic_load_n(&cpu_state->count[1].end, __ATOMIC_RELAXED);
  84         }
  85
  86         /*
  87          * Read end counts before begin counts. Reading end
  88          * before begin count ensures we never see an end
  89          * without having seen its associated begin, in case of
  90          * a thread migration during the traversal over each
  91          * cpu.
  92          */
  93         __atomic_thread_fence(__ATOMIC_SEQ_CST);
  94
  95         for (i = 0; i < gp_state->nr_cpus; i++) {
  96                 struct side_rcu_cpu_gp_state *cpu_state = &gp_state->percpu_state[i];
  97
  98                 sum[0] += __atomic_load_n(&cpu_state->count[0].begin, __ATOMIC_RELAXED);
  99                 sum[1] += __atomic_load_n(&cpu_state->count[1].begin, __ATOMIC_RELAXED);
 100         }
 101         if (active_readers[0])
 102                 active_readers[0] = sum[0];
 103         if (active_readers[1])
 104                 active_readers[1] = sum[1];
 105 }
 106
 107 /*
 108  * Wait for previous period to have no active readers.
 109  *
 110  * active_readers is an input/output parameter.
 111  */
 112 static inline
 113 void wait_for_prev_period_readers(struct side_rcu_gp_state *gp_state, bool *active_readers)
 114 {
 115         unsigned int prev_period = gp_state->period ^ 1;
 116
 117         /*
 118          * If a prior active readers scan already observed that no
 119          * readers are present for the previous period, there is no need
 120          * to scan again.
 121          */
 122         if (!active_readers[prev_period])
 123                 return;
 124         /*
 125          * Wait for the sum of CPU begin/end counts to match for the
 126          * previous period.
 127          */
 128         for (;;) {
 129                 check_active_readers(gp_state, active_readers);
 130                 if (!active_readers[prev_period])
 131                         break;
 132                 /* Retry after 10ms. */
 133                 poll(NULL, 0, 10);
 134         }
 135 }
 136
 137 /*
 138  * The grace period completes when it observes that there are no active
 139  * readers within each of the periods.
 140  *
 141  * The active_readers state is initially true for each period, until the
 142  * grace period observes that no readers are present for each given
 143  * period, at which point the active_readers state becomes false.
 144  */
 145 static inline
 146 void side_rcu_wait_grace_period(struct side_rcu_gp_state *gp_state)
 147 {
 148         bool active_readers[2] = { true, true };
 149
 150         /*
 151          * This fence pairs with the __atomic_add_fetch __ATOMIC_SEQ_CST in
 152          * side_rcu_read_end().
 153          */
 154         __atomic_thread_fence(__ATOMIC_SEQ_CST);
 155
 156         /*
 157          * First scan through all cpus, for both period. If no readers
 158          * are accounted for, we have observed quiescence and can
 159          * complete the grace period immediately.
 160          */
 161         check_active_readers(gp_state, active_readers);
 162         if (!active_readers[0] && !active_readers[1])
 163                 goto end;
 164
 165         pthread_mutex_lock(&gp_state->gp_lock);
 166
 167         wait_for_prev_period_readers(gp_state, active_readers);
 168         /*
 169          * If the reader scan detected that there are no readers in the
 170          * current period as well, we can complete the grace period
 171          * immediately.
 172          */
 173         if (!active_readers[gp_state->period])
 174                 goto unlock;
 175
 176         /* Flip period: 0 -> 1, 1 -> 0. */
 177         (void) __atomic_xor_fetch(&gp_state->period, 1, __ATOMIC_RELAXED);
 178
 179         wait_for_prev_period_readers(gp_state, active_readers);
 180 unlock:
 181         pthread_mutex_unlock(&gp_state->gp_lock);
 182 end:
 183         /*
 184          * This fence pairs with the __atomic_add_fetch __ATOMIC_SEQ_CST in
 185          * side_rcu_read_begin().
 186          */
 187         __atomic_thread_fence(__ATOMIC_SEQ_CST);
 188 }