src/rcu.h

   1 // SPDX-License-Identifier: MIT
   2 /*
   3  * Copyright 2022 Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
   4  */
   5
   6 #ifndef _SIDE_RCU_H
   7 #define _SIDE_RCU_H
   8
   9 #include <sched.h>
  10 #include <stdint.h>
  11 #include <pthread.h>
  12 #include <stdbool.h>
  13 #include <poll.h>
  14 #include <rseq/rseq.h>
  15 #include <linux/futex.h>
  16 #include <sys/time.h>
  17 #include <unistd.h>
  18 #include <sys/syscall.h>
  19 #include <side/macros.h>
  20
  21 #define SIDE_CACHE_LINE_SIZE            256
  22
  23 struct side_rcu_percpu_count {
  24         uintptr_t begin;
  25         uintptr_t rseq_begin;
  26         uintptr_t end;
  27         uintptr_t rseq_end;
  28 }  __attribute__((__aligned__(SIDE_CACHE_LINE_SIZE)));
  29
  30 struct side_rcu_cpu_gp_state {
  31         struct side_rcu_percpu_count count[2];
  32 };
  33
  34 struct side_rcu_gp_state {
  35         struct side_rcu_cpu_gp_state *percpu_state;
  36         int nr_cpus;
  37         int32_t futex;
  38         unsigned int period;
  39         pthread_mutex_t gp_lock;
  40 };
  41
  42 extern unsigned int side_rcu_rseq_membarrier_available __attribute__((visibility("hidden")));
  43
  44 static inline
  45 int futex(int32_t *uaddr, int op, int32_t val,
  46         const struct timespec *timeout, int32_t *uaddr2, int32_t val3)
  47 {
  48         return syscall(__NR_futex, uaddr, op, val, timeout, uaddr2, val3);
  49 }
  50
  51 /*
  52  * Wake-up side_rcu_wait_grace_period. Called concurrently from many
  53  * threads.
  54  */
  55 static inline
  56 void side_rcu_wake_up_gp(struct side_rcu_gp_state *gp_state)
  57 {
  58         if (side_unlikely(__atomic_load_n(&gp_state->futex, __ATOMIC_RELAXED)) == -1) {
  59                 __atomic_store_n(&gp_state->futex, 0, __ATOMIC_RELAXED);
  60                 /* TODO: handle futex return values. */
  61                 (void) futex(&gp_state->futex, FUTEX_WAKE, 1, NULL, NULL, 0);
  62         }
  63 }
  64
  65 static inline
  66 unsigned int side_rcu_read_begin(struct side_rcu_gp_state *gp_state)
  67 {
  68         unsigned int period = __atomic_load_n(&gp_state->period, __ATOMIC_RELAXED);
  69         struct side_rcu_cpu_gp_state *cpu_gp_state;
  70         int cpu;
  71
  72         if (side_likely(side_rcu_rseq_membarrier_available)) {
  73                 cpu = rseq_cpu_start();
  74                 cpu_gp_state = &gp_state->percpu_state[cpu];
  75                 if (side_likely(!rseq_addv((intptr_t *)&cpu_gp_state->count[period].rseq_begin, 1, cpu))) {
  76                         /*
  77                          * This compiler barrier (A) is paired with membarrier() at (C),
  78                          * (D), (E). It effectively upgrades this compiler barrier to a
  79                          * SEQ_CST fence with respect to the paired barriers.
  80                          *
  81                          * This barrier (A) ensures that the contents of the read-side
  82                          * critical section does not leak before the "begin" counter
  83                          * increment. It pairs with memory barriers (D) and (E).
  84                          *
  85                          * This barrier (A) also ensures that the "begin" increment is
  86                          * before the "end" increment. It pairs with memory barrier (C).
  87                          * It is redundant with barrier (B) for that purpose.
  88                          */
  89                         rseq_barrier();
  90                         return period;
  91                 }
  92         }
  93         /* Fallback to atomic increment and SEQ_CST. */
  94         cpu = sched_getcpu();
  95         if (side_unlikely(cpu < 0))
  96                 cpu = 0;
  97         cpu_gp_state = &gp_state->percpu_state[cpu];
  98         (void) __atomic_add_fetch(&cpu_gp_state->count[period].begin, 1, __ATOMIC_SEQ_CST);
  99         return period;
 100 }
 101
 102 static inline
 103 void side_rcu_read_end(struct side_rcu_gp_state *gp_state, unsigned int period)
 104 {
 105         struct side_rcu_cpu_gp_state *cpu_gp_state;
 106         int cpu;
 107
 108         if (side_likely(side_rcu_rseq_membarrier_available)) {
 109                 /*
 110                  * This compiler barrier (B) is paired with membarrier() at (C),
 111                  * (D), (E). It effectively upgrades this compiler barrier to a
 112                  * SEQ_CST fence with respect to the paired barriers.
 113                  *
 114                  * This barrier (B) ensures that the contents of the read-side
 115                  * critical section does not leak after the "end" counter
 116                  * increment. It pairs with memory barriers (D) and (E).
 117                  *
 118                  * This barrier (B) also ensures that the "begin" increment is
 119                  * before the "end" increment. It pairs with memory barrier (C).
 120                  * It is redundant with barrier (A) for that purpose.
 121                  */
 122                 rseq_barrier();
 123                 cpu = rseq_cpu_start();
 124                 cpu_gp_state = &gp_state->percpu_state[cpu];
 125                 if (side_likely(!rseq_addv((intptr_t *)&cpu_gp_state->count[period].rseq_end, 1, cpu))) {
 126                         /*
 127                          * This barrier (F) is paired with membarrier()
 128                          * at (G). It orders increment of the begin/end
 129                          * counters before load/store to the futex.
 130                          */
 131                         rseq_barrier();
 132                         goto end;
 133                 }
 134         }
 135         /* Fallback to atomic increment and SEQ_CST. */
 136         cpu = sched_getcpu();
 137         if (side_unlikely(cpu < 0))
 138                 cpu = 0;
 139         cpu_gp_state = &gp_state->percpu_state[cpu];
 140         (void) __atomic_add_fetch(&cpu_gp_state->count[period].end, 1, __ATOMIC_SEQ_CST);
 141         /*
 142          * This barrier (F) is paired with SEQ_CST barrier or
 143          * membarrier() at (G). It orders increment of the begin/end
 144          * counters before load/store to the futex.
 145          */
 146         __atomic_thread_fence(__ATOMIC_SEQ_CST);
 147 end:
 148         side_rcu_wake_up_gp(gp_state);
 149 }
 150
 151 #define side_rcu_dereference(p) \
 152         __extension__ \
 153         ({ \
 154                 __typeof__(p) _____side_v = __atomic_load_n(&(p), __ATOMIC_CONSUME); \
 155                 (_____side_v); \
 156         })
 157
 158 #define side_rcu_assign_pointer(p, v)   __atomic_store_n(&(p), v, __ATOMIC_RELEASE); \
 159
 160 void side_rcu_wait_grace_period(struct side_rcu_gp_state *gp_state) __attribute__((visibility("hidden")));
 161 void side_rcu_gp_init(struct side_rcu_gp_state *rcu_gp) __attribute__((visibility("hidden")));
 162 void side_rcu_gp_exit(struct side_rcu_gp_state *rcu_gp) __attribute__((visibility("hidden")));
 163
 164 #endif /* _SIDE_RCU_H */