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 static inline
  73 void check_active_readers(struct side_rcu_gp_state *gp_state, bool *active_readers)
  74 {
  75         uintptr_t sum[2] = { 0, 0 };    /* begin - end */
  76         int i;
  77
  78         for (i = 0; i < gp_state->nr_cpus; i++) {
  79                 struct side_rcu_cpu_gp_state *cpu_state = &gp_state->percpu_state[i];
  80
  81                 sum[0] -= __atomic_load_n(&cpu_state->count[0].end, __ATOMIC_RELAXED);
  82                 sum[1] -= __atomic_load_n(&cpu_state->count[1].end, __ATOMIC_RELAXED);
  83         }
  84
  85         /*
  86          * Read end counts before begin counts. Reading end
  87          * before begin count ensures we never see an end
  88          * without having seen its associated begin, in case of
  89          * a thread migration during the traversal over each
  90          * cpu.
  91          */
  92         __atomic_thread_fence(__ATOMIC_SEQ_CST);
  93
  94         for (i = 0; i < gp_state->nr_cpus; i++) {
  95                 struct side_rcu_cpu_gp_state *cpu_state = &gp_state->percpu_state[i];
  96
  97                 sum[0] += __atomic_load_n(&cpu_state->count[0].begin, __ATOMIC_RELAXED);
  98                 sum[1] += __atomic_load_n(&cpu_state->count[1].begin, __ATOMIC_RELAXED);
  99         }
 100         active_readers[0] = sum[0];
 101         active_readers[1] = sum[1];
 102 }
 103
 104 static inline
 105 void wait_for_prev_period_readers(struct side_rcu_gp_state *gp_state)
 106 {
 107         unsigned int prev_period = gp_state->period ^ 1;
 108         bool active_readers[2];
 109
 110         /*
 111          * Wait for the sum of CPU begin/end counts to match for the
 112          * previous period.
 113          */
 114         for (;;) {
 115                 check_active_readers(gp_state, active_readers);
 116                 if (!active_readers[prev_period])
 117                         break;
 118                 /* Retry after 10ms. */
 119                 poll(NULL, 0, 10);
 120         }
 121 }
 122
 123 static inline
 124 void side_rcu_wait_grace_period(struct side_rcu_gp_state *gp_state)
 125 {
 126         bool active_readers[2];
 127
 128         /*
 129          * This fence pairs with the __atomic_add_fetch __ATOMIC_SEQ_CST in
 130          * side_rcu_read_end().
 131          */
 132         __atomic_thread_fence(__ATOMIC_SEQ_CST);
 133
 134         /*
 135          * First scan through all cpus, for both period. If no readers
 136          * are accounted for, we have observed quiescence and can
 137          * complete the grace period immediately.
 138          */
 139         check_active_readers(gp_state, active_readers);
 140         if (!active_readers[0] && !active_readers[1])
 141                 goto end;
 142
 143         pthread_mutex_lock(&gp_state->gp_lock);
 144
 145         wait_for_prev_period_readers(gp_state);
 146
 147         /* Flip period: 0 -> 1, 1 -> 0. */
 148         (void) __atomic_xor_fetch(&gp_state->period, 1, __ATOMIC_RELAXED);
 149
 150         wait_for_prev_period_readers(gp_state);
 151
 152         pthread_mutex_unlock(&gp_state->gp_lock);
 153
 154 end:
 155         /*
 156          * This fence pairs with the __atomic_add_fetch __ATOMIC_SEQ_CST in
 157          * side_rcu_read_begin().
 158          */
 159         __atomic_thread_fence(__ATOMIC_SEQ_CST);
 160 }