src/rcu.c

   1 // SPDX-License-Identifier: MIT
   2 /*
   3  * Copyright 2022 Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
   4  */
   5
   6 #include <sched.h>
   7 #include <string.h>
   8 #include <stdint.h>
   9 #include <pthread.h>
  10 #include <stdbool.h>
  11 #include <poll.h>
  12 #include <stdlib.h>
  13
  14 #include "rcu.h"
  15 #include "smp.h"
  16
  17 /* active_readers is an input/output parameter. */
  18 static
  19 void check_active_readers(struct side_rcu_gp_state *gp_state, bool *active_readers)
  20 {
  21         uintptr_t sum[2] = { 0, 0 };    /* begin - end */
  22         int i;
  23
  24         for (i = 0; i < gp_state->nr_cpus; i++) {
  25                 struct side_rcu_cpu_gp_state *cpu_state = &gp_state->percpu_state[i];
  26
  27                 if (active_readers[0]) {
  28                         sum[0] -= __atomic_load_n(&cpu_state->count[0].end, __ATOMIC_RELAXED);
  29                         sum[0] -= __atomic_load_n(&cpu_state->count[0].rseq_end, __ATOMIC_RELAXED);
  30                 }
  31                 if (active_readers[1]) {
  32                         sum[1] -= __atomic_load_n(&cpu_state->count[1].end, __ATOMIC_RELAXED);
  33                         sum[1] -= __atomic_load_n(&cpu_state->count[1].rseq_end, __ATOMIC_RELAXED);
  34                 }
  35         }
  36
  37         /*
  38          * This memory barrier (C) pairs with either of memory barriers
  39          * (A) or (B) (one is sufficient).
  40          *
  41          * Read end counts before begin counts. Reading "end" before
  42          * "begin" counts ensures we never see an "end" without having
  43          * seen its associated "begin", because "begin" is always
  44          * incremented before "end", as guaranteed by memory barriers
  45          * (A) or (B).
  46          */
  47         __atomic_thread_fence(__ATOMIC_SEQ_CST);
  48
  49         for (i = 0; i < gp_state->nr_cpus; i++) {
  50                 struct side_rcu_cpu_gp_state *cpu_state = &gp_state->percpu_state[i];
  51
  52                 if (active_readers[0]) {
  53                         sum[0] += __atomic_load_n(&cpu_state->count[0].begin, __ATOMIC_RELAXED);
  54                         sum[0] += __atomic_load_n(&cpu_state->count[0].rseq_begin, __ATOMIC_RELAXED);
  55                 }
  56                 if (active_readers[1]) {
  57                         sum[1] += __atomic_load_n(&cpu_state->count[1].begin, __ATOMIC_RELAXED);
  58                         sum[1] += __atomic_load_n(&cpu_state->count[1].rseq_begin, __ATOMIC_RELAXED);
  59                 }
  60         }
  61         if (active_readers[0])
  62                 active_readers[0] = sum[0];
  63         if (active_readers[1])
  64                 active_readers[1] = sum[1];
  65 }
  66
  67 /*
  68  * Wait for previous period to have no active readers.
  69  *
  70  * active_readers is an input/output parameter.
  71  */
  72 static
  73 void wait_for_prev_period_readers(struct side_rcu_gp_state *gp_state, bool *active_readers)
  74 {
  75         unsigned int prev_period = gp_state->period ^ 1;
  76
  77         /*
  78          * If a prior active readers scan already observed that no
  79          * readers are present for the previous period, there is no need
  80          * to scan again.
  81          */
  82         if (!active_readers[prev_period])
  83                 return;
  84         /*
  85          * Wait for the sum of CPU begin/end counts to match for the
  86          * previous period.
  87          */
  88         for (;;) {
  89                 check_active_readers(gp_state, active_readers);
  90                 if (!active_readers[prev_period])
  91                         break;
  92                 /* Retry after 10ms. */
  93                 poll(NULL, 0, 10);
  94         }
  95 }
  96
  97 /*
  98  * The grace period completes when it observes that there are no active
  99  * readers within each of the periods.
 100  *
 101  * The active_readers state is initially true for each period, until the
 102  * grace period observes that no readers are present for each given
 103  * period, at which point the active_readers state becomes false.
 104  */
 105 void side_rcu_wait_grace_period(struct side_rcu_gp_state *gp_state)
 106 {
 107         bool active_readers[2] = { true, true };
 108
 109         /*
 110          * This memory barrier (D) pairs with memory barriers (A) and
 111          * (B) on the read-side.
 112          *
 113          * It orders prior loads and stores before the "end"/"begin"
 114          * reader state loads. In other words, it orders prior loads and
 115          * stores before observation of active readers quiescence,
 116          * effectively ensuring that read-side critical sections which
 117          * exist after the grace period completes are ordered after
 118          * loads and stores performed before the grace period.
 119          */
 120         __atomic_thread_fence(__ATOMIC_SEQ_CST);
 121
 122         /*
 123          * First scan through all cpus, for both period. If no readers
 124          * are accounted for, we have observed quiescence and can
 125          * complete the grace period immediately.
 126          */
 127         check_active_readers(gp_state, active_readers);
 128         if (!active_readers[0] && !active_readers[1])
 129                 goto end;
 130
 131         pthread_mutex_lock(&gp_state->gp_lock);
 132
 133         wait_for_prev_period_readers(gp_state, active_readers);
 134         /*
 135          * If the reader scan detected that there are no readers in the
 136          * current period as well, we can complete the grace period
 137          * immediately.
 138          */
 139         if (!active_readers[gp_state->period])
 140                 goto unlock;
 141
 142         /* Flip period: 0 -> 1, 1 -> 0. */
 143         (void) __atomic_xor_fetch(&gp_state->period, 1, __ATOMIC_RELAXED);
 144
 145         wait_for_prev_period_readers(gp_state, active_readers);
 146 unlock:
 147         pthread_mutex_unlock(&gp_state->gp_lock);
 148 end:
 149         /*
 150          * This memory barrier (E) pairs with memory barriers (A) and
 151          * (B) on the read-side.
 152          *
 153          * It orders the "end"/"begin" reader state loads before
 154          * following loads and stores. In other words, it orders
 155          * observation of active readers quiescence before following
 156          * loads and stores, effectively ensuring that read-side
 157          * critical sections which existed prior to the grace period
 158          * are ordered before loads and stores performed after the grace
 159          * period.
 160          */
 161         __atomic_thread_fence(__ATOMIC_SEQ_CST);
 162 }
 163
 164 void side_rcu_gp_init(struct side_rcu_gp_state *rcu_gp)
 165 {
 166         memset(rcu_gp, 0, sizeof(*rcu_gp));
 167         rcu_gp->nr_cpus = get_possible_cpus_array_len();
 168         if (!rcu_gp->nr_cpus)
 169                 abort();
 170         pthread_mutex_init(&rcu_gp->gp_lock, NULL);
 171         rcu_gp->percpu_state = calloc(rcu_gp->nr_cpus, sizeof(struct side_rcu_cpu_gp_state));
 172         if (!rcu_gp->percpu_state)
 173                 abort();
 174 }
 175
 176 void side_rcu_gp_exit(struct side_rcu_gp_state *rcu_gp)
 177 {
 178         rseq_prepare_unload();
 179         pthread_mutex_destroy(&rcu_gp->gp_lock);
 180         free(rcu_gp->percpu_state);
 181 }