X-Git-Url: http://drtracing.org/?a=blobdiff_plain;f=src%2Frcu.h;h=4db3500566abc002042d9f63a6b617d4c24d76de;hb=873bbf16c6bcfe2c11fca7e76dd7284c5afbee99;hp=61a6fb0cc72ac5ba7daba2c81f9bf537b897b5a7;hpb=1f62b901b04dcaa710c2d2927960d4749fa4db4e;p=libside.git diff --git a/src/rcu.h b/src/rcu.h index 61a6fb0..4db3500 100644 --- a/src/rcu.h +++ b/src/rcu.h @@ -3,216 +3,165 @@ * Copyright 2022 Mathieu Desnoyers */ +#ifndef _SIDE_RCU_H +#define _SIDE_RCU_H + #include #include #include #include #include +#include +#include +#include +#include +#include +#include #define SIDE_CACHE_LINE_SIZE 256 struct side_rcu_percpu_count { uintptr_t begin; + uintptr_t rseq_begin; uintptr_t end; -} __attribute__((__aligned__(SIDE_CACHE_LINE_SIZE))); + uintptr_t rseq_end; +}; struct side_rcu_cpu_gp_state { struct side_rcu_percpu_count count[2]; -}; +} __attribute__((__aligned__(SIDE_CACHE_LINE_SIZE))); struct side_rcu_gp_state { struct side_rcu_cpu_gp_state *percpu_state; int nr_cpus; + int32_t futex; unsigned int period; pthread_mutex_t gp_lock; }; -//TODO: replace atomics by rseq (when available) -//TODO: replace acquire/release by membarrier+compiler barrier (when available) -//TODO: implement wait/wakeup for grace period using sys_futex -static inline -unsigned int side_rcu_read_begin(struct side_rcu_gp_state *gp_state) -{ - int cpu = sched_getcpu(); - unsigned int period = __atomic_load_n(&gp_state->period, __ATOMIC_RELAXED); +struct side_rcu_read_state { + struct side_rcu_percpu_count *percpu_count; + int cpu; +}; - if (cpu < 0) - cpu = 0; - /* - * This memory barrier (A) ensures that the contents of the - * read-side critical section does not leak before the "begin" - * counter increment. It pairs with memory barriers (D) and (E). - * - * This memory barrier (A) also ensures that the "begin" - * increment is before the "end" increment. It pairs with memory - * barrier (C). It is redundant with memory barrier (B) for that - * purpose. - */ - (void) __atomic_add_fetch(&gp_state->percpu_state[cpu].count[period].begin, 1, __ATOMIC_SEQ_CST); - return period; -} +extern unsigned int side_rcu_rseq_membarrier_available __attribute__((visibility("hidden"))); static inline -void side_rcu_read_end(struct side_rcu_gp_state *gp_state, unsigned int period) +int futex(int32_t *uaddr, int op, int32_t val, + const struct timespec *timeout, int32_t *uaddr2, int32_t val3) { - int cpu = sched_getcpu(); - - if (cpu < 0) - cpu = 0; - /* - * This memory barrier (B) ensures that the contents of the - * read-side critical section does not leak after the "end" - * counter increment. It pairs with memory barriers (D) and (E). - * - * This memory barrier (B) also ensures that the "begin" - * increment is before the "end" increment. It pairs with memory - * barrier (C). It is redundant with memory barrier (A) for that - * purpose. - */ - (void) __atomic_add_fetch(&gp_state->percpu_state[cpu].count[period].end, 1, __ATOMIC_SEQ_CST); + return syscall(__NR_futex, uaddr, op, val, timeout, uaddr2, val3); } -#define side_rcu_dereference(p) \ - __extension__ \ - ({ \ - (__typeof__(p) _____side_v = __atomic_load_n(&(p), __ATOMIC_CONSUME); \ - (_____side_v); \ - }) - -#define side_rcu_assign_pointer(p, v) __atomic_store_n(&(p), v, __ATOMIC_RELEASE); \ - -/* active_readers is an input/output parameter. */ +/* + * Wake-up side_rcu_wait_grace_period. Called concurrently from many + * threads. + */ static inline -void check_active_readers(struct side_rcu_gp_state *gp_state, bool *active_readers) +void side_rcu_wake_up_gp(struct side_rcu_gp_state *gp_state) { - uintptr_t sum[2] = { 0, 0 }; /* begin - end */ - int i; - - for (i = 0; i < gp_state->nr_cpus; i++) { - struct side_rcu_cpu_gp_state *cpu_state = &gp_state->percpu_state[i]; - - sum[0] -= __atomic_load_n(&cpu_state->count[0].end, __ATOMIC_RELAXED); - sum[1] -= __atomic_load_n(&cpu_state->count[1].end, __ATOMIC_RELAXED); - } - - /* - * This memory barrier (C) pairs with either of memory barriers - * (A) or (B) (one is sufficient). - * - * Read end counts before begin counts. Reading "end" before - * "begin" counts ensures we never see an "end" without having - * seen its associated "begin", because "begin" is always - * incremented before "end", as guaranteed by memory barriers - * (A) or (B). - */ - __atomic_thread_fence(__ATOMIC_SEQ_CST); - - for (i = 0; i < gp_state->nr_cpus; i++) { - struct side_rcu_cpu_gp_state *cpu_state = &gp_state->percpu_state[i]; - - sum[0] += __atomic_load_n(&cpu_state->count[0].begin, __ATOMIC_RELAXED); - sum[1] += __atomic_load_n(&cpu_state->count[1].begin, __ATOMIC_RELAXED); + if (side_unlikely(__atomic_load_n(&gp_state->futex, __ATOMIC_RELAXED) == -1)) { + __atomic_store_n(&gp_state->futex, 0, __ATOMIC_RELAXED); + /* TODO: handle futex return values. */ + (void) futex(&gp_state->futex, FUTEX_WAKE, 1, NULL, NULL, 0); } - if (active_readers[0]) - active_readers[0] = sum[0]; - if (active_readers[1]) - active_readers[1] = sum[1]; } -/* - * Wait for previous period to have no active readers. - * - * active_readers is an input/output parameter. - */ static inline -void wait_for_prev_period_readers(struct side_rcu_gp_state *gp_state, bool *active_readers) +void side_rcu_read_begin(struct side_rcu_gp_state *gp_state, struct side_rcu_read_state *read_state) { - unsigned int prev_period = gp_state->period ^ 1; - - /* - * If a prior active readers scan already observed that no - * readers are present for the previous period, there is no need - * to scan again. - */ - if (!active_readers[prev_period]) + struct side_rcu_percpu_count *begin_cpu_count; + struct side_rcu_cpu_gp_state *cpu_gp_state; + unsigned int period; + int cpu; + + cpu = rseq_cpu_start(); + period = __atomic_load_n(&gp_state->period, __ATOMIC_RELAXED); + cpu_gp_state = &gp_state->percpu_state[cpu]; + read_state->percpu_count = begin_cpu_count = &cpu_gp_state->count[period]; + read_state->cpu = cpu; + if (side_likely(side_rcu_rseq_membarrier_available && + !rseq_addv(RSEQ_MO_RELAXED, RSEQ_PERCPU_CPU_ID, + (intptr_t *)&begin_cpu_count->rseq_begin, 1, cpu))) { + /* + * This compiler barrier (A) is paired with membarrier() at (C), + * (D), (E). It effectively upgrades this compiler barrier to a + * SEQ_CST fence with respect to the paired barriers. + * + * This barrier (A) ensures that the contents of the read-side + * critical section does not leak before the "begin" counter + * increment. It pairs with memory barriers (D) and (E). + * + * This barrier (A) also ensures that the "begin" increment is + * before the "end" increment. It pairs with memory barrier (C). + * It is redundant with barrier (B) for that purpose. + */ + rseq_barrier(); return; - /* - * Wait for the sum of CPU begin/end counts to match for the - * previous period. - */ - for (;;) { - check_active_readers(gp_state, active_readers); - if (!active_readers[prev_period]) - break; - /* Retry after 10ms. */ - poll(NULL, 0, 10); } + /* Fallback to atomic increment and SEQ_CST. */ + cpu = sched_getcpu(); + if (side_unlikely(cpu < 0)) + cpu = 0; + read_state->cpu = cpu; + cpu_gp_state = &gp_state->percpu_state[cpu]; + read_state->percpu_count = begin_cpu_count = &cpu_gp_state->count[period]; + (void) __atomic_add_fetch(&begin_cpu_count->begin, 1, __ATOMIC_SEQ_CST); } -/* - * The grace period completes when it observes that there are no active - * readers within each of the periods. - * - * The active_readers state is initially true for each period, until the - * grace period observes that no readers are present for each given - * period, at which point the active_readers state becomes false. - */ static inline -void side_rcu_wait_grace_period(struct side_rcu_gp_state *gp_state) +void side_rcu_read_end(struct side_rcu_gp_state *gp_state, struct side_rcu_read_state *read_state) { - bool active_readers[2] = { true, true }; + struct side_rcu_percpu_count *begin_cpu_count = read_state->percpu_count; + int cpu = read_state->cpu; /* - * This memory barrier (D) pairs with memory barriers (A) and - * (B) on the read-side. + * This compiler barrier (B) is paired with membarrier() at (C), + * (D), (E). It effectively upgrades this compiler barrier to a + * SEQ_CST fence with respect to the paired barriers. + * + * This barrier (B) ensures that the contents of the read-side + * critical section does not leak after the "end" counter + * increment. It pairs with memory barriers (D) and (E). * - * It orders prior loads and stores before the "end"/"begin" - * reader state loads. In other words, it orders prior loads and - * stores before observation of active readers quiescence, - * effectively ensuring that read-side critical sections which - * exist after the grace period completes are ordered after - * loads and stores performed before the grace period. + * This barrier (B) also ensures that the "begin" increment is + * before the "end" increment. It pairs with memory barrier (C). + * It is redundant with barrier (A) for that purpose. */ - __atomic_thread_fence(__ATOMIC_SEQ_CST); - + rseq_barrier(); + if (side_likely(side_rcu_rseq_membarrier_available && + !rseq_addv(RSEQ_MO_RELAXED, RSEQ_PERCPU_CPU_ID, + (intptr_t *)&begin_cpu_count->rseq_end, 1, cpu))) { + /* + * This barrier (F) is paired with membarrier() + * at (G). It orders increment of the begin/end + * counters before load/store to the futex. + */ + rseq_barrier(); + goto end; + } + /* Fallback to atomic increment and SEQ_CST. */ + (void) __atomic_add_fetch(&begin_cpu_count->end, 1, __ATOMIC_SEQ_CST); /* - * First scan through all cpus, for both period. If no readers - * are accounted for, we have observed quiescence and can - * complete the grace period immediately. + * This barrier (F) implied by SEQ_CST is paired with SEQ_CST + * barrier or membarrier() at (G). It orders increment of the + * begin/end counters before load/store to the futex. */ - check_active_readers(gp_state, active_readers); - if (!active_readers[0] && !active_readers[1]) - goto end; +end: + side_rcu_wake_up_gp(gp_state); +} - pthread_mutex_lock(&gp_state->gp_lock); +#define side_rcu_dereference(p) \ + __extension__ \ + ({ \ + __typeof__(p) _____side_v = __atomic_load_n(&(p), __ATOMIC_CONSUME); \ + (_____side_v); \ + }) - wait_for_prev_period_readers(gp_state, active_readers); - /* - * If the reader scan detected that there are no readers in the - * current period as well, we can complete the grace period - * immediately. - */ - if (!active_readers[gp_state->period]) - goto unlock; +#define side_rcu_assign_pointer(p, v) __atomic_store_n(&(p), v, __ATOMIC_RELEASE); - /* Flip period: 0 -> 1, 1 -> 0. */ - (void) __atomic_xor_fetch(&gp_state->period, 1, __ATOMIC_RELAXED); +void side_rcu_wait_grace_period(struct side_rcu_gp_state *gp_state) __attribute__((visibility("hidden"))); +void side_rcu_gp_init(struct side_rcu_gp_state *rcu_gp) __attribute__((visibility("hidden"))); +void side_rcu_gp_exit(struct side_rcu_gp_state *rcu_gp) __attribute__((visibility("hidden"))); - wait_for_prev_period_readers(gp_state, active_readers); -unlock: - pthread_mutex_unlock(&gp_state->gp_lock); -end: - /* - * This memory barrier (E) pairs with memory barriers (A) and - * (B) on the read-side. - * - * It orders the "end"/"begin" reader state loads before - * following loads and stores. In other words, it orders - * observation of active readers quiescence before following - * loads and stores, effectively ensuring that read-side - * critical sections which existed prior to the grace period - * are ordered before loads and stores performed after the grace - * period. - */ - __atomic_thread_fence(__ATOMIC_SEQ_CST); -} +#endif /* _SIDE_RCU_H */