source: mainline/kernel/generic/src/synch/rcu.c@ cc74cb5

lfn serial ticket/834-toolchain-update topic/msim-upgrade topic/simplify-dev-export
Last change on this file since cc74cb5 was 09ab0a9a, checked in by Jiri Svoboda <jiri@…>, 7 years ago

Fix vertical spacing with new Ccheck revision.

  • Property mode set to 100644
File size: 55.9 KB
RevLine 
[79d74fe]1/*
2 * Copyright (c) 2012 Adam Hraska
3 * All rights reserved.
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
7 * are met:
8 *
9 * - Redistributions of source code must retain the above copyright
10 * notice, this list of conditions and the following disclaimer.
11 * - Redistributions in binary form must reproduce the above copyright
12 * notice, this list of conditions and the following disclaimer in the
13 * documentation and/or other materials provided with the distribution.
14 * - The name of the author may not be used to endorse or promote products
15 * derived from this software without specific prior written permission.
16 *
17 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
18 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
19 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
20 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
21 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
22 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
23 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
24 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
25 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
26 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
27 */
[a35b458]28
[79d74fe]29/** @addtogroup sync
30 * @{
31 */
32
33/**
34 * @file
[181a746]35 * @brief Preemptible read-copy update. Usable from interrupt handlers.
[1b20da0]36 *
[fbe6b65]37 * @par Podzimek-preempt-RCU (RCU_PREEMPT_PODZIMEK)
[1b20da0]38 *
[fbe6b65]39 * Podzimek-preempt-RCU is a preemptible variant of Podzimek's non-preemptible
40 * RCU algorithm [1, 2]. Grace period (GP) detection is centralized into a
41 * single detector thread. The detector requests that each cpu announces
42 * that it passed a quiescent state (QS), ie a state when the cpu is
43 * outside of an rcu reader section (CS). Cpus check for QSs during context
[1b20da0]44 * switches and when entering and exiting rcu reader sections. Once all
45 * cpus announce a QS and if there were no threads preempted in a CS, the
[fbe6b65]46 * GP ends.
[1b20da0]47 *
48 * The detector increments the global GP counter, _rcu_cur_gp, in order
49 * to start a new GP. Readers notice the new GP by comparing the changed
[fbe6b65]50 * _rcu_cur_gp to a locally stored value last_seen_gp which denotes the
51 * the last GP number for which the cpu noted an explicit QS (and issued
52 * a memory barrier). Readers check for the change in the outer-most
[1b20da0]53 * (ie not nested) rcu_read_lock()/unlock() as these functions represent
54 * a QS. The reader first executes a memory barrier (MB) in order to contain
55 * memory references within a CS (and to make changes made by writers
56 * visible in the CS following rcu_read_lock()). Next, the reader notes
[fbe6b65]57 * that it reached a QS by updating the cpu local last_seen_gp to the
58 * global GP counter, _rcu_cur_gp. Cache coherency eventually makes
59 * the updated last_seen_gp visible to the detector cpu, much like it
60 * delivered the changed _rcu_cur_gp to all cpus.
[1b20da0]61 *
62 * The detector waits a while after starting a GP and then reads each
63 * cpu's last_seen_gp to see if it reached a QS. If a cpu did not record
[fbe6b65]64 * a QS (might be a long running thread without an RCU reader CS; or cache
65 * coherency has yet to make the most current last_seen_gp visible to
66 * the detector; or the cpu is still in a CS) the cpu is interrupted
67 * via an IPI. If the IPI handler finds the cpu still in a CS, it instructs
[82719589]68 * the cpu to notify the detector that it had exited the CS via a semaphore
[1b20da0]69 * (CPU->rcu.is_delaying_gp).
[fbe6b65]70 * The detector then waits on the semaphore for any cpus to exit their
[1b20da0]71 * CSs. Lastly, it waits for the last reader preempted in a CS to
[fbe6b65]72 * exit its CS if there were any and signals the end of the GP to
73 * separate reclaimer threads wired to each cpu. Reclaimers then
74 * execute the callbacks queued on each of the cpus.
[1b20da0]75 *
76 *
[fbe6b65]77 * @par A-RCU algorithm (RCU_PREEMPT_A)
[1b20da0]78 *
[fbe6b65]79 * A-RCU is based on the user space rcu algorithm in [3] utilizing signals
[1b20da0]80 * (urcu) and Podzimek's rcu [1]. Like in Podzimek's rcu, callbacks are
81 * executed by cpu-bound reclaimer threads. There is however no dedicated
82 * detector thread and the reclaimers take on the responsibilities of the
83 * detector when they need to start a new GP. A new GP is again announced
[fbe6b65]84 * and acknowledged with _rcu_cur_gp and the cpu local last_seen_gp. Unlike
[1b20da0]85 * Podzimek's rcu, cpus check explicitly for QS only during context switches.
[fbe6b65]86 * Like in urcu, rcu_read_lock()/unlock() only maintain the nesting count
87 * and never issue any memory barriers. This makes rcu_read_lock()/unlock()
88 * simple and fast.
[1b20da0]89 *
[fbe6b65]90 * If a new callback is queued for a reclaimer and no GP is in progress,
[1b20da0]91 * the reclaimer takes on the role of a detector. The detector increments
92 * _rcu_cur_gp in order to start a new GP. It waits a while to give cpus
[fbe6b65]93 * a chance to switch a context (a natural QS). Then, it examines each
94 * non-idle cpu that has yet to pass a QS via an IPI. The IPI handler
95 * sees the most current _rcu_cur_gp and last_seen_gp and notes a QS
96 * with a memory barrier and an update to last_seen_gp. If the handler
97 * finds the cpu in a CS it does nothing and let the detector poll/interrupt
98 * the cpu again after a short sleep.
[1b20da0]99 *
[fbe6b65]100 * @par Caveats
[1b20da0]101 *
[fbe6b65]102 * last_seen_gp and _rcu_cur_gp are always 64bit variables and they
103 * are read non-atomically on 32bit machines. Reading a clobbered
104 * value of last_seen_gp or _rcu_cur_gp or writing a clobbered value
105 * of _rcu_cur_gp to last_seen_gp will at worst force the detector
[1b20da0]106 * to unnecessarily interrupt a cpu. Interrupting a cpu makes the
[fbe6b65]107 * correct value of _rcu_cur_gp visible to the cpu and correctly
108 * resets last_seen_gp in both algorithms.
[1b20da0]109 *
110 *
111 *
[fbe6b65]112 * [1] Read-copy-update for opensolaris,
113 * 2010, Podzimek
114 * https://andrej.podzimek.org/thesis.pdf
[1b20da0]115 *
[fbe6b65]116 * [2] (podzimek-rcu) implementation file "rcu.patch"
117 * http://d3s.mff.cuni.cz/projects/operating_systems/rcu/rcu.patch
[1b20da0]118 *
[fbe6b65]119 * [3] User-level implementations of read-copy update,
120 * 2012, appendix
121 * http://www.rdrop.com/users/paulmck/RCU/urcu-supp-accepted.2011.08.30a.pdf
[1b20da0]122 *
[79d74fe]123 */
[63e27ef]124
125#include <assert.h>
[79d74fe]126#include <synch/rcu.h>
[181a746]127#include <synch/condvar.h>
128#include <synch/semaphore.h>
129#include <synch/spinlock.h>
[4ec9ea41]130#include <synch/mutex.h>
[181a746]131#include <proc/thread.h>
132#include <cpu/cpu_mask.h>
133#include <cpu.h>
134#include <smp/smp_call.h>
[05882233]135#include <barrier.h>
[181a746]136#include <atomic.h>
137#include <arch.h>
138#include <macros.h>
[79d74fe]139
[1b20da0]140/*
141 * Number of milliseconds to give to preexisting readers to finish
[181a746]142 * when non-expedited grace period detection is in progress.
143 */
[0cf813d]144#define DETECT_SLEEP_MS 10
[1b20da0]145/*
146 * Max number of pending callbacks in the local cpu's queue before
[181a746]147 * aggressively expediting the current grace period
148 */
[0cf813d]149#define EXPEDITE_THRESHOLD 2000
150/*
151 * Max number of callbacks to execute in one go with preemption
152 * enabled. If there are more callbacks to be executed they will
153 * be run with preemption disabled in order to prolong reclaimer's
154 * time slice and give it a chance to catch up with callback producers.
155 */
156#define CRITICAL_THRESHOLD 30000
[181a746]157/* Half the number of values a uint32 can hold. */
158#define UINT32_MAX_HALF 2147483648U
[79d74fe]159
[1b20da0]160/**
161 * The current grace period number. Increases monotonically.
[8e3ed06]162 * Lock rcu.gp_lock or rcu.preempt_lock to get a current value.
163 */
164rcu_gp_t _rcu_cur_gp;
[181a746]165
[0cf813d]166/** Global RCU data. */
[181a746]167typedef struct rcu_data {
168 /** Detector uses so signal reclaimers that a grace period ended. */
169 condvar_t gp_ended;
170 /** Reclaimers use to notify the detector to accelerate GP detection. */
171 condvar_t expedite_now;
[1b20da0]172 /**
[d4d36f9]173 * Protects: req_gp_end_cnt, req_expedited_cnt, completed_gp, _rcu_cur_gp;
174 * or: completed_gp, _rcu_cur_gp
[181a746]175 */
176 SPINLOCK_DECLARE(gp_lock);
177 /**
[1b20da0]178 * The number of the most recently completed grace period. At most
179 * one behind _rcu_cur_gp. If equal to _rcu_cur_gp, a grace period
[8e3ed06]180 * detection is not in progress and the detector is idle.
[181a746]181 */
182 rcu_gp_t completed_gp;
[a35b458]183
[0cf813d]184 /** Protects the following 3 fields. */
[181a746]185 IRQ_SPINLOCK_DECLARE(preempt_lock);
186 /** Preexisting readers that have been preempted. */
187 list_t cur_preempted;
188 /** Reader that have been preempted and might delay the next grace period.*/
189 list_t next_preempted;
[1b20da0]190 /**
191 * The detector is waiting for the last preempted reader
192 * in cur_preempted to announce that it exited its reader
[181a746]193 * section by up()ing remaining_readers.
194 */
195 bool preempt_blocking_det;
[a35b458]196
[d4d36f9]197#ifdef RCU_PREEMPT_A
[a35b458]198
[1b20da0]199 /**
200 * The detector waits on this semaphore for any preempted readers
[d4d36f9]201 * delaying the grace period once all cpus pass a quiescent state.
202 */
203 semaphore_t remaining_readers;
204
205#elif defined(RCU_PREEMPT_PODZIMEK)
[a35b458]206
[d4d36f9]207 /** Reclaimers notify the detector when they request more grace periods.*/
208 condvar_t req_gp_changed;
209 /** Number of grace period ends the detector was requested to announce. */
210 size_t req_gp_end_cnt;
211 /** Number of consecutive grace periods to detect quickly and aggressively.*/
212 size_t req_expedited_cnt;
[1b20da0]213 /**
[181a746]214 * Number of cpus with readers that are delaying the current GP.
215 * They will up() remaining_readers.
216 */
217 atomic_t delaying_cpu_cnt;
[1b20da0]218 /**
[d4d36f9]219 * The detector waits on this semaphore for any readers delaying the GP.
[1b20da0]220 *
221 * Each of the cpus with readers that are delaying the current GP
222 * must up() this sema once they reach a quiescent state. If there
223 * are any readers in cur_preempted (ie preempted preexisting) and
[d4d36f9]224 * they are already delaying GP detection, the last to unlock its
225 * reader section must up() this sema once.
226 */
227 semaphore_t remaining_readers;
228#endif
[a35b458]229
[4ec9ea41]230 /** Excludes simultaneous rcu_barrier() calls. */
231 mutex_t barrier_mtx;
232 /** Number of cpus that we are waiting for to complete rcu_barrier(). */
233 atomic_t barrier_wait_cnt;
234 /** rcu_barrier() waits for the completion of barrier callbacks on this wq.*/
235 waitq_t barrier_wq;
[a35b458]236
[0cf813d]237 /** Interruptible attached detector thread pointer. */
[181a746]238 thread_t *detector_thr;
[a35b458]239
[181a746]240 /* Some statistics. */
241 size_t stat_expedited_cnt;
242 size_t stat_delayed_cnt;
243 size_t stat_preempt_blocking_cnt;
244 /* Does not contain self/local calls. */
245 size_t stat_smp_call_cnt;
246} rcu_data_t;
247
248static rcu_data_t rcu;
249
250static void start_reclaimers(void);
251static void synch_complete(rcu_item_t *rcu_item);
[1b20da0]252static inline void rcu_call_impl(bool expedite, rcu_item_t *rcu_item,
[18b6a88]253 rcu_func_t func);
[4ec9ea41]254static void add_barrier_cb(void *arg);
255static void barrier_complete(rcu_item_t *barrier_item);
[181a746]256static bool arriving_cbs_empty(void);
257static bool next_cbs_empty(void);
258static bool cur_cbs_empty(void);
259static bool all_cbs_empty(void);
260static void reclaimer(void *arg);
261static bool wait_for_pending_cbs(void);
262static bool advance_cbs(void);
263static void exec_completed_cbs(rcu_gp_t last_completed_gp);
264static void exec_cbs(rcu_item_t **phead);
265static bool wait_for_cur_cbs_gp_end(bool expedite, rcu_gp_t *last_completed_gp);
[0cf813d]266static void upd_missed_gp_in_wait(rcu_gp_t completed_gp);
[d4d36f9]267
268#ifdef RCU_PREEMPT_PODZIMEK
269static void start_detector(void);
270static void read_unlock_impl(size_t *pnesting_cnt);
271static void req_detection(size_t req_cnt);
[181a746]272static bool cv_wait_for_gp(rcu_gp_t wait_on_gp);
273static void detector(void *);
274static bool wait_for_detect_req(void);
275static void end_cur_gp(void);
276static bool wait_for_readers(void);
277static bool gp_sleep(void);
278static void interrupt_delaying_cpus(cpu_mask_t *cpu_mask);
279static bool wait_for_delaying_cpus(void);
[d4d36f9]280#elif defined(RCU_PREEMPT_A)
281static bool wait_for_readers(bool expedite);
282static bool gp_sleep(bool *expedite);
283#endif
284
285static void start_new_gp(void);
286static void rm_quiescent_cpus(cpu_mask_t *cpu_mask);
287static void sample_cpus(cpu_mask_t *reader_cpus, void *arg);
288static void sample_local_cpu(void *);
[181a746]289static bool wait_for_preempt_reader(void);
[d4d36f9]290static void note_preempted_reader(void);
291static void rm_preempted_reader(void);
[82719589]292static void upd_max_cbs_in_slice(size_t arriving_cbs_cnt);
[181a746]293
294/** Initializes global RCU structures. */
295void rcu_init(void)
296{
297 condvar_initialize(&rcu.gp_ended);
298 condvar_initialize(&rcu.expedite_now);
[d4d36f9]299
[181a746]300 spinlock_initialize(&rcu.gp_lock, "rcu.gp_lock");
[8e3ed06]301 _rcu_cur_gp = 0;
[181a746]302 rcu.completed_gp = 0;
[a35b458]303
[181a746]304 irq_spinlock_initialize(&rcu.preempt_lock, "rcu.preempt_lock");
305 list_initialize(&rcu.cur_preempted);
306 list_initialize(&rcu.next_preempted);
307 rcu.preempt_blocking_det = false;
[a35b458]308
[4ec9ea41]309 mutex_initialize(&rcu.barrier_mtx, MUTEX_PASSIVE);
[e3306d04]310 atomic_store(&rcu.barrier_wait_cnt, 0);
[4ec9ea41]311 waitq_initialize(&rcu.barrier_wq);
[d4d36f9]312
313 semaphore_initialize(&rcu.remaining_readers, 0);
[a35b458]314
[d4d36f9]315#ifdef RCU_PREEMPT_PODZIMEK
316 condvar_initialize(&rcu.req_gp_changed);
[a35b458]317
[d4d36f9]318 rcu.req_gp_end_cnt = 0;
319 rcu.req_expedited_cnt = 0;
[e3306d04]320 atomic_store(&rcu.delaying_cpu_cnt, 0);
[d4d36f9]321#endif
[a35b458]322
[205832b]323 rcu.detector_thr = NULL;
[a35b458]324
[181a746]325 rcu.stat_expedited_cnt = 0;
326 rcu.stat_delayed_cnt = 0;
327 rcu.stat_preempt_blocking_cnt = 0;
328 rcu.stat_smp_call_cnt = 0;
329}
330
331/** Initializes per-CPU RCU data. If on the boot cpu inits global data too.*/
332void rcu_cpu_init(void)
333{
334 if (config.cpu_active == 1) {
335 rcu_init();
336 }
[d4d36f9]337
[181a746]338 CPU->rcu.last_seen_gp = 0;
[d4d36f9]339
340#ifdef RCU_PREEMPT_PODZIMEK
[5b03a72]341 CPU->rcu.nesting_cnt = 0;
[d4d36f9]342 CPU->rcu.is_delaying_gp = false;
343 CPU->rcu.signal_unlock = false;
344#endif
[a35b458]345
[205832b]346 CPU->rcu.cur_cbs = NULL;
[0cf813d]347 CPU->rcu.cur_cbs_cnt = 0;
[205832b]348 CPU->rcu.next_cbs = NULL;
[0cf813d]349 CPU->rcu.next_cbs_cnt = 0;
[205832b]350 CPU->rcu.arriving_cbs = NULL;
[181a746]351 CPU->rcu.parriving_cbs_tail = &CPU->rcu.arriving_cbs;
352 CPU->rcu.arriving_cbs_cnt = 0;
353
354 CPU->rcu.cur_cbs_gp = 0;
355 CPU->rcu.next_cbs_gp = 0;
[a35b458]356
[181a746]357 semaphore_initialize(&CPU->rcu.arrived_flag, 0);
[0cf813d]358
359 /* BSP creates reclaimer threads before AP's rcu_cpu_init() runs. */
360 if (config.cpu_active == 1)
[205832b]361 CPU->rcu.reclaimer_thr = NULL;
[a35b458]362
[181a746]363 CPU->rcu.stat_max_cbs = 0;
364 CPU->rcu.stat_avg_cbs = 0;
365 CPU->rcu.stat_missed_gps = 0;
[0cf813d]366 CPU->rcu.stat_missed_gp_in_wait = 0;
367 CPU->rcu.stat_max_slice_cbs = 0;
368 CPU->rcu.last_arriving_cnt = 0;
[181a746]369}
370
371/** Completes RCU init. Creates and runs the detector and reclaimer threads.*/
372void rcu_kinit_init(void)
373{
[d4d36f9]374#ifdef RCU_PREEMPT_PODZIMEK
[181a746]375 start_detector();
[d4d36f9]376#endif
[a35b458]377
[181a746]378 start_reclaimers();
379}
380
381/** Initializes any per-thread RCU structures. */
382void rcu_thread_init(thread_t *thread)
383{
384 thread->rcu.nesting_cnt = 0;
[d4d36f9]385
386#ifdef RCU_PREEMPT_PODZIMEK
[181a746]387 thread->rcu.was_preempted = false;
[d4d36f9]388#endif
[a35b458]389
[181a746]390 link_initialize(&thread->rcu.preempt_link);
391}
392
[1b20da0]393/** Cleans up global RCU resources and stops dispatching callbacks.
394 *
[181a746]395 * Call when shutting down the kernel. Outstanding callbacks will
396 * not be processed. Instead they will linger forever.
397 */
398void rcu_stop(void)
399{
400 /* Stop and wait for reclaimers. */
401 for (unsigned int cpu_id = 0; cpu_id < config.cpu_active; ++cpu_id) {
[63e27ef]402 assert(cpus[cpu_id].rcu.reclaimer_thr != NULL);
[a35b458]403
[181a746]404 if (cpus[cpu_id].rcu.reclaimer_thr) {
405 thread_interrupt(cpus[cpu_id].rcu.reclaimer_thr);
406 thread_join(cpus[cpu_id].rcu.reclaimer_thr);
407 thread_detach(cpus[cpu_id].rcu.reclaimer_thr);
[205832b]408 cpus[cpu_id].rcu.reclaimer_thr = NULL;
[181a746]409 }
410 }
411
[d4d36f9]412#ifdef RCU_PREEMPT_PODZIMEK
[181a746]413 /* Stop the detector and wait. */
414 if (rcu.detector_thr) {
415 thread_interrupt(rcu.detector_thr);
416 thread_join(rcu.detector_thr);
417 thread_detach(rcu.detector_thr);
[205832b]418 rcu.detector_thr = NULL;
[181a746]419 }
[d4d36f9]420#endif
[181a746]421}
[79d74fe]422
[d4d36f9]423/** Returns the number of elapsed grace periods since boot. */
424uint64_t rcu_completed_gps(void)
[181a746]425{
[d4d36f9]426 spinlock_lock(&rcu.gp_lock);
427 uint64_t completed = rcu.completed_gp;
428 spinlock_unlock(&rcu.gp_lock);
[a35b458]429
[d4d36f9]430 return completed;
[181a746]431}
432
433/** Creates and runs cpu-bound reclaimer threads. */
434static void start_reclaimers(void)
435{
436 for (unsigned int cpu_id = 0; cpu_id < config.cpu_count; ++cpu_id) {
[18b6a88]437 char name[THREAD_NAME_BUFLEN] = { 0 };
[a35b458]438
[181a746]439 snprintf(name, THREAD_NAME_BUFLEN - 1, "rcu-rec/%u", cpu_id);
[a35b458]440
[1b20da0]441 cpus[cpu_id].rcu.reclaimer_thr =
[18b6a88]442 thread_create(reclaimer, NULL, TASK, THREAD_FLAG_NONE, name);
[181a746]443
[1b20da0]444 if (!cpus[cpu_id].rcu.reclaimer_thr)
[181a746]445 panic("Failed to create RCU reclaimer thread on cpu%u.", cpu_id);
446
447 thread_wire(cpus[cpu_id].rcu.reclaimer_thr, &cpus[cpu_id]);
448 thread_ready(cpus[cpu_id].rcu.reclaimer_thr);
449 }
450}
451
[d4d36f9]452#ifdef RCU_PREEMPT_PODZIMEK
453
454/** Starts the detector thread. */
455static void start_detector(void)
[181a746]456{
[1b20da0]457 rcu.detector_thr =
[18b6a88]458 thread_create(detector, NULL, TASK, THREAD_FLAG_NONE, "rcu-det");
[a35b458]459
[1b20da0]460 if (!rcu.detector_thr)
[d4d36f9]461 panic("Failed to create RCU detector thread.");
[a35b458]462
[d4d36f9]463 thread_ready(rcu.detector_thr);
[181a746]464}
465
[4a6da62]466/** Returns true if in an rcu reader section. */
467bool rcu_read_locked(void)
468{
469 preemption_disable();
[5b03a72]470 bool locked = 0 < CPU->rcu.nesting_cnt;
[4a6da62]471 preemption_enable();
[a35b458]472
[4a6da62]473 return locked;
474}
475
[1b20da0]476/** Unlocks the local reader section using the given nesting count.
477 *
478 * Preemption or interrupts must be disabled.
479 *
480 * @param pnesting_cnt Either &CPU->rcu.tmp_nesting_cnt or
[181a746]481 * THREAD->rcu.nesting_cnt.
[79d74fe]482 */
[8e3ed06]483static void read_unlock_impl(size_t *pnesting_cnt)
[181a746]484{
[63e27ef]485 assert(PREEMPTION_DISABLED || interrupts_disabled());
[a35b458]486
[181a746]487 if (0 == --(*pnesting_cnt)) {
[8e3ed06]488 _rcu_record_qs();
[a35b458]489
[1b20da0]490 /*
491 * The thread was preempted while in a critical section or
492 * the detector is eagerly waiting for this cpu's reader
493 * to finish.
494 *
[205832b]495 * Note that THREAD may be NULL in scheduler() and not just during boot.
[181a746]496 */
497 if ((THREAD && THREAD->rcu.was_preempted) || CPU->rcu.is_delaying_gp) {
498 /* Rechecks with disabled interrupts. */
[8e3ed06]499 _rcu_signal_read_unlock();
[181a746]500 }
501 }
502}
503
504/** If necessary, signals the detector that we exited a reader section. */
[8e3ed06]505void _rcu_signal_read_unlock(void)
[181a746]506{
[63e27ef]507 assert(PREEMPTION_DISABLED || interrupts_disabled());
[a35b458]508
[181a746]509 /*
[82719589]510 * If an interrupt occurs here (even a NMI) it may beat us to
511 * resetting .is_delaying_gp or .was_preempted and up the semaphore
512 * for us.
[181a746]513 */
[a35b458]514
[1b20da0]515 /*
[181a746]516 * If the detector is eagerly waiting for this cpu's reader to unlock,
517 * notify it that the reader did so.
518 */
[82719589]519 if (local_atomic_exchange(&CPU->rcu.is_delaying_gp, false)) {
[181a746]520 semaphore_up(&rcu.remaining_readers);
521 }
[a35b458]522
[181a746]523 /*
524 * This reader was preempted while in a reader section.
525 * We might be holding up the current GP. Notify the
526 * detector if so.
527 */
[82719589]528 if (THREAD && local_atomic_exchange(&THREAD->rcu.was_preempted, false)) {
[63e27ef]529 assert(link_used(&THREAD->rcu.preempt_link));
[181a746]530
[d4d36f9]531 rm_preempted_reader();
[181a746]532 }
[a35b458]533
[f0fcb04]534 /* If there was something to signal to the detector we have done so. */
535 CPU->rcu.signal_unlock = false;
[181a746]536}
537
[d4d36f9]538#endif /* RCU_PREEMPT_PODZIMEK */
539
[181a746]540typedef struct synch_item {
541 waitq_t wq;
542 rcu_item_t rcu_item;
543} synch_item_t;
544
545/** Blocks until all preexisting readers exit their critical sections. */
[79d74fe]546void rcu_synchronize(void)
[4ec9ea41]547{
548 _rcu_synchronize(false);
549}
550
551/** Blocks until all preexisting readers exit their critical sections. */
552void rcu_synchronize_expedite(void)
553{
554 _rcu_synchronize(true);
555}
556
557/** Blocks until all preexisting readers exit their critical sections. */
558void _rcu_synchronize(bool expedite)
[79d74fe]559{
[181a746]560 /* Calling from a reader section will deadlock. */
[63e27ef]561 assert(!rcu_read_locked());
[a35b458]562
[1b20da0]563 synch_item_t completion;
[181a746]564
565 waitq_initialize(&completion.wq);
[4ec9ea41]566 _rcu_call(expedite, &completion.rcu_item, synch_complete);
[181a746]567 waitq_sleep(&completion.wq);
[79d74fe]568}
569
[181a746]570/** rcu_synchronize's callback. */
571static void synch_complete(rcu_item_t *rcu_item)
572{
573 synch_item_t *completion = member_to_inst(rcu_item, synch_item_t, rcu_item);
[63e27ef]574 assert(completion);
[181a746]575 waitq_wakeup(&completion->wq, WAKEUP_FIRST);
576}
[79d74fe]577
[4ec9ea41]578/** Waits for all outstanding rcu calls to complete. */
579void rcu_barrier(void)
580{
[1b20da0]581 /*
[4ec9ea41]582 * Serialize rcu_barrier() calls so we don't overwrite cpu.barrier_item
583 * currently in use by rcu_barrier().
584 */
585 mutex_lock(&rcu.barrier_mtx);
[a35b458]586
[1b20da0]587 /*
[4ec9ea41]588 * Ensure we queue a barrier callback on all cpus before the already
589 * enqueued barrier callbacks start signaling completion.
590 */
[e3306d04]591 atomic_store(&rcu.barrier_wait_cnt, 1);
[4ec9ea41]592
593 DEFINE_CPU_MASK(cpu_mask);
594 cpu_mask_active(cpu_mask);
[a35b458]595
[4ec9ea41]596 cpu_mask_for_each(*cpu_mask, cpu_id) {
[205832b]597 smp_call(cpu_id, add_barrier_cb, NULL);
[4ec9ea41]598 }
[a35b458]599
[4ec9ea41]600 if (0 < atomic_predec(&rcu.barrier_wait_cnt)) {
601 waitq_sleep(&rcu.barrier_wq);
602 }
[a35b458]603
[4ec9ea41]604 mutex_unlock(&rcu.barrier_mtx);
605}
606
[1b20da0]607/** Issues a rcu_barrier() callback on the local cpu.
608 *
609 * Executed with interrupts disabled.
[4ec9ea41]610 */
611static void add_barrier_cb(void *arg)
612{
[63e27ef]613 assert(interrupts_disabled() || PREEMPTION_DISABLED);
[4ec9ea41]614 atomic_inc(&rcu.barrier_wait_cnt);
615 rcu_call(&CPU->rcu.barrier_item, barrier_complete);
616}
617
618/** Local cpu's rcu_barrier() completion callback. */
619static void barrier_complete(rcu_item_t *barrier_item)
620{
621 /* Is this the last barrier callback completed? */
622 if (0 == atomic_predec(&rcu.barrier_wait_cnt)) {
623 /* Notify rcu_barrier() that we're done. */
624 waitq_wakeup(&rcu.barrier_wq, WAKEUP_FIRST);
625 }
626}
627
[1b20da0]628/** Adds a callback to invoke after all preexisting readers finish.
629 *
[181a746]630 * May be called from within interrupt handlers or RCU reader sections.
[1b20da0]631 *
[181a746]632 * @param rcu_item Used by RCU to track the call. Must remain
633 * until the user callback function is entered.
634 * @param func User callback function that will be invoked once a full
635 * grace period elapsed, ie at a time when all preexisting
636 * readers have finished. The callback should be short and must
637 * not block. If you must sleep, enqueue your work in the system
638 * work queue from the callback (ie workq_global_enqueue()).
[79d74fe]639 */
[181a746]640void rcu_call(rcu_item_t *rcu_item, rcu_func_t func)
[79d74fe]641{
[3648ea56]642 rcu_call_impl(false, rcu_item, func);
[79d74fe]643}
644
[181a746]645/** rcu_call() implementation. See rcu_call() for comments. */
646void _rcu_call(bool expedite, rcu_item_t *rcu_item, rcu_func_t func)
[3648ea56]647{
648 rcu_call_impl(expedite, rcu_item, func);
649}
650
651/** rcu_call() inline-able implementation. See rcu_call() for comments. */
[1b20da0]652static inline void rcu_call_impl(bool expedite, rcu_item_t *rcu_item,
[18b6a88]653 rcu_func_t func)
[181a746]654{
[63e27ef]655 assert(rcu_item);
[a35b458]656
[181a746]657 rcu_item->func = func;
[205832b]658 rcu_item->next = NULL;
[a35b458]659
[181a746]660 preemption_disable();
[79d74fe]661
[3648ea56]662 rcu_cpu_data_t *r = &CPU->rcu;
[82719589]663
[18b6a88]664 rcu_item_t **prev_tail =
665 local_atomic_exchange(&r->parriving_cbs_tail, &rcu_item->next);
[82719589]666 *prev_tail = rcu_item;
[a35b458]667
[82719589]668 /* Approximate the number of callbacks present. */
669 ++r->arriving_cbs_cnt;
[a35b458]670
[181a746]671 if (expedite) {
[3648ea56]672 r->expedite_arriving = true;
[181a746]673 }
[a35b458]674
[82719589]675 bool first_cb = (prev_tail == &CPU->rcu.arriving_cbs);
[a35b458]676
[181a746]677 /* Added first callback - notify the reclaimer. */
[82719589]678 if (first_cb && !semaphore_count_get(&r->arrived_flag)) {
[3648ea56]679 semaphore_up(&r->arrived_flag);
[181a746]680 }
[a35b458]681
[181a746]682 preemption_enable();
683}
684
685static bool cur_cbs_empty(void)
686{
[63e27ef]687 assert(THREAD && THREAD->wired);
[205832b]688 return NULL == CPU->rcu.cur_cbs;
[181a746]689}
690
691static bool next_cbs_empty(void)
692{
[63e27ef]693 assert(THREAD && THREAD->wired);
[205832b]694 return NULL == CPU->rcu.next_cbs;
[181a746]695}
696
697/** Disable interrupts to get an up-to-date result. */
698static bool arriving_cbs_empty(void)
699{
[63e27ef]700 assert(THREAD && THREAD->wired);
[1b20da0]701 /*
702 * Accessing with interrupts enabled may at worst lead to
[181a746]703 * a false negative if we race with a local interrupt handler.
704 */
[205832b]705 return NULL == CPU->rcu.arriving_cbs;
[181a746]706}
707
708static bool all_cbs_empty(void)
709{
710 return cur_cbs_empty() && next_cbs_empty() && arriving_cbs_empty();
711}
712
713/** Reclaimer thread dispatches locally queued callbacks once a GP ends. */
714static void reclaimer(void *arg)
715{
[63e27ef]716 assert(THREAD && THREAD->wired);
717 assert(THREAD == CPU->rcu.reclaimer_thr);
[181a746]718
719 rcu_gp_t last_compl_gp = 0;
720 bool ok = true;
[a35b458]721
[181a746]722 while (ok && wait_for_pending_cbs()) {
[63e27ef]723 assert(CPU->rcu.reclaimer_thr == THREAD);
[a35b458]724
[0cf813d]725 exec_completed_cbs(last_compl_gp);
726
[181a746]727 bool expedite = advance_cbs();
[a35b458]728
[181a746]729 ok = wait_for_cur_cbs_gp_end(expedite, &last_compl_gp);
730 }
731}
732
733/** Waits until there are callbacks waiting to be dispatched. */
734static bool wait_for_pending_cbs(void)
735{
[1b20da0]736 if (!all_cbs_empty())
[181a746]737 return true;
738
739 bool ok = true;
[a35b458]740
[181a746]741 while (arriving_cbs_empty() && ok) {
742 ok = semaphore_down_interruptable(&CPU->rcu.arrived_flag);
743 }
[a35b458]744
[181a746]745 return ok;
746}
747
[b68ae24]748static void upd_stat_missed_gp(rcu_gp_t compl)
[181a746]749{
[b68ae24]750 if (CPU->rcu.cur_cbs_gp < compl) {
751 CPU->rcu.stat_missed_gps += (size_t)(compl - CPU->rcu.cur_cbs_gp);
[181a746]752 }
753}
754
755/** Executes all callbacks for the given completed grace period. */
756static void exec_completed_cbs(rcu_gp_t last_completed_gp)
757{
[b68ae24]758 upd_stat_missed_gp(last_completed_gp);
[a35b458]759
[0cf813d]760 /* Both next_cbs and cur_cbs GP elapsed. */
[181a746]761 if (CPU->rcu.next_cbs_gp <= last_completed_gp) {
[63e27ef]762 assert(CPU->rcu.cur_cbs_gp <= CPU->rcu.next_cbs_gp);
[a35b458]763
[0cf813d]764 size_t exec_cnt = CPU->rcu.cur_cbs_cnt + CPU->rcu.next_cbs_cnt;
[a35b458]765
[0cf813d]766 if (exec_cnt < CRITICAL_THRESHOLD) {
767 exec_cbs(&CPU->rcu.cur_cbs);
[1b20da0]768 exec_cbs(&CPU->rcu.next_cbs);
[0cf813d]769 } else {
[1b20da0]770 /*
771 * Getting overwhelmed with too many callbacks to run.
772 * Disable preemption in order to prolong our time slice
[0cf813d]773 * and catch up with updaters posting new callbacks.
774 */
775 preemption_disable();
776 exec_cbs(&CPU->rcu.cur_cbs);
[1b20da0]777 exec_cbs(&CPU->rcu.next_cbs);
[0cf813d]778 preemption_enable();
779 }
[a35b458]780
[0cf813d]781 CPU->rcu.cur_cbs_cnt = 0;
782 CPU->rcu.next_cbs_cnt = 0;
783 } else if (CPU->rcu.cur_cbs_gp <= last_completed_gp) {
784
785 if (CPU->rcu.cur_cbs_cnt < CRITICAL_THRESHOLD) {
786 exec_cbs(&CPU->rcu.cur_cbs);
787 } else {
[1b20da0]788 /*
789 * Getting overwhelmed with too many callbacks to run.
790 * Disable preemption in order to prolong our time slice
[0cf813d]791 * and catch up with updaters posting new callbacks.
792 */
793 preemption_disable();
794 exec_cbs(&CPU->rcu.cur_cbs);
795 preemption_enable();
796 }
797
798 CPU->rcu.cur_cbs_cnt = 0;
[181a746]799 }
800}
801
802/** Executes callbacks in the single-linked list. The list is left empty. */
803static void exec_cbs(rcu_item_t **phead)
804{
805 rcu_item_t *rcu_item = *phead;
806
807 while (rcu_item) {
808 /* func() may free rcu_item. Get a local copy. */
809 rcu_item_t *next = rcu_item->next;
810 rcu_func_t func = rcu_item->func;
[a35b458]811
[181a746]812 func(rcu_item);
[a35b458]813
[181a746]814 rcu_item = next;
815 }
[a35b458]816
[205832b]817 *phead = NULL;
[181a746]818}
819
820static void upd_stat_cb_cnts(size_t arriving_cnt)
821{
822 CPU->rcu.stat_max_cbs = max(arriving_cnt, CPU->rcu.stat_max_cbs);
823 if (0 < arriving_cnt) {
[1b20da0]824 CPU->rcu.stat_avg_cbs =
[18b6a88]825 (99 * CPU->rcu.stat_avg_cbs + 1 * arriving_cnt) / 100;
[181a746]826 }
827}
828
829/** Prepares another batch of callbacks to dispatch at the nest grace period.
[1b20da0]830 *
[181a746]831 * @return True if the next batch of callbacks must be expedited quickly.
[79d74fe]832 */
[181a746]833static bool advance_cbs(void)
834{
835 /* Move next_cbs to cur_cbs. */
836 CPU->rcu.cur_cbs = CPU->rcu.next_cbs;
[0cf813d]837 CPU->rcu.cur_cbs_cnt = CPU->rcu.next_cbs_cnt;
[181a746]838 CPU->rcu.cur_cbs_gp = CPU->rcu.next_cbs_gp;
[a35b458]839
[82719589]840 /* Move arriving_cbs to next_cbs. */
[a35b458]841
[82719589]842 CPU->rcu.next_cbs_cnt = CPU->rcu.arriving_cbs_cnt;
843 CPU->rcu.arriving_cbs_cnt = 0;
[a35b458]844
[1b20da0]845 /*
[181a746]846 * Too many callbacks queued. Better speed up the detection
847 * or risk exhausting all system memory.
848 */
[18b6a88]849 bool expedite = (EXPEDITE_THRESHOLD < CPU->rcu.next_cbs_cnt) ||
850 CPU->rcu.expedite_arriving;
[181a746]851 CPU->rcu.expedite_arriving = false;
[82719589]852
853 /* Start moving the arriving_cbs list to next_cbs. */
[181a746]854 CPU->rcu.next_cbs = CPU->rcu.arriving_cbs;
[a35b458]855
[1b20da0]856 /*
[82719589]857 * At least one callback arrived. The tail therefore does not point
858 * to the head of arriving_cbs and we can safely reset it to NULL.
859 */
860 if (CPU->rcu.next_cbs) {
[63e27ef]861 assert(CPU->rcu.parriving_cbs_tail != &CPU->rcu.arriving_cbs);
[a35b458]862
[82719589]863 CPU->rcu.arriving_cbs = NULL;
864 /* Reset arriving_cbs before updating the tail pointer. */
865 compiler_barrier();
866 /* Updating the tail pointer completes the move of arriving_cbs. */
867 ACCESS_ONCE(CPU->rcu.parriving_cbs_tail) = &CPU->rcu.arriving_cbs;
868 } else {
[1b20da0]869 /*
870 * arriving_cbs was null and parriving_cbs_tail pointed to it
[82719589]871 * so leave it that way. Note that interrupt handlers may have
872 * added a callback in the meantime so it is not safe to reset
873 * arriving_cbs or parriving_cbs.
874 */
875 }
[0cf813d]876
877 /* Update statistics of arrived callbacks. */
878 upd_stat_cb_cnts(CPU->rcu.next_cbs_cnt);
[a35b458]879
[1b20da0]880 /*
881 * Make changes prior to queuing next_cbs visible to readers.
[181a746]882 * See comment in wait_for_readers().
883 */
884 memory_barrier(); /* MB A, B */
885
886 /* At the end of next_cbs_gp, exec next_cbs. Determine what GP that is. */
[a35b458]887
[181a746]888 if (!next_cbs_empty()) {
889 spinlock_lock(&rcu.gp_lock);
[a35b458]890
[181a746]891 /* Exec next_cbs at the end of the next GP. */
[8e3ed06]892 CPU->rcu.next_cbs_gp = _rcu_cur_gp + 1;
[a35b458]893
[1b20da0]894 /*
[181a746]895 * There are no callbacks to invoke before next_cbs. Instruct
896 * wait_for_cur_cbs_gp() to notify us of the nearest GP end.
[1b20da0]897 * That could be sooner than next_cbs_gp (if the current GP
[181a746]898 * had not yet completed), so we'll create a shorter batch
899 * of callbacks next time around.
900 */
901 if (cur_cbs_empty()) {
902 CPU->rcu.cur_cbs_gp = rcu.completed_gp + 1;
[1b20da0]903 }
[a35b458]904
[181a746]905 spinlock_unlock(&rcu.gp_lock);
906 } else {
907 CPU->rcu.next_cbs_gp = CPU->rcu.cur_cbs_gp;
908 }
[a35b458]909
[63e27ef]910 assert(CPU->rcu.cur_cbs_gp <= CPU->rcu.next_cbs_gp);
[a35b458]911
[1b20da0]912 return expedite;
[181a746]913}
914
[d4d36f9]915#ifdef RCU_PREEMPT_A
916
[1b20da0]917/** Waits for the grace period associated with callbacks cub_cbs to elapse.
918 *
919 * @param expedite Instructs the detector to aggressively speed up grace
[181a746]920 * period detection without any delay.
[1b20da0]921 * @param completed_gp Returns the most recent completed grace period
[181a746]922 * number.
923 * @return false if the thread was interrupted and should stop.
924 */
925static bool wait_for_cur_cbs_gp_end(bool expedite, rcu_gp_t *completed_gp)
926{
927 spinlock_lock(&rcu.gp_lock);
[d4d36f9]928
[63e27ef]929 assert(CPU->rcu.cur_cbs_gp <= CPU->rcu.next_cbs_gp);
930 assert(CPU->rcu.cur_cbs_gp <= _rcu_cur_gp + 1);
[a35b458]931
[d4d36f9]932 while (rcu.completed_gp < CPU->rcu.cur_cbs_gp) {
933 /* GP has not yet started - start a new one. */
934 if (rcu.completed_gp == _rcu_cur_gp) {
935 start_new_gp();
936 spinlock_unlock(&rcu.gp_lock);
[181a746]937
[d4d36f9]938 if (!wait_for_readers(expedite))
939 return false;
940
941 spinlock_lock(&rcu.gp_lock);
942 /* Notify any reclaimers this GP had ended. */
943 rcu.completed_gp = _rcu_cur_gp;
944 condvar_broadcast(&rcu.gp_ended);
945 } else {
[1b20da0]946 /* GP detection is in progress.*/
[a35b458]947
[1b20da0]948 if (expedite)
[d4d36f9]949 condvar_signal(&rcu.expedite_now);
[a35b458]950
[d4d36f9]951 /* Wait for the GP to complete. */
[1b20da0]952 errno_t ret = _condvar_wait_timeout_spinlock(&rcu.gp_ended, &rcu.gp_lock,
[18b6a88]953 SYNCH_NO_TIMEOUT, SYNCH_FLAGS_INTERRUPTIBLE);
[a35b458]954
[897fd8f1]955 if (ret == EINTR) {
[d4d36f9]956 spinlock_unlock(&rcu.gp_lock);
[1b20da0]957 return false;
[d4d36f9]958 }
959 }
960 }
[a35b458]961
[09737cc]962 upd_missed_gp_in_wait(rcu.completed_gp);
[a35b458]963
[181a746]964 *completed_gp = rcu.completed_gp;
[d4d36f9]965 spinlock_unlock(&rcu.gp_lock);
[a35b458]966
[d4d36f9]967 return true;
[181a746]968}
969
[d4d36f9]970static bool wait_for_readers(bool expedite)
[0cf813d]971{
[d4d36f9]972 DEFINE_CPU_MASK(reader_cpus);
[a35b458]973
[d4d36f9]974 cpu_mask_active(reader_cpus);
975 rm_quiescent_cpus(reader_cpus);
[a35b458]976
[d4d36f9]977 while (!cpu_mask_is_none(reader_cpus)) {
978 /* Give cpus a chance to context switch (a QS) and batch callbacks. */
[18b6a88]979 if (!gp_sleep(&expedite))
[d4d36f9]980 return false;
[a35b458]981
[d4d36f9]982 rm_quiescent_cpus(reader_cpus);
983 sample_cpus(reader_cpus, reader_cpus);
984 }
[a35b458]985
[d4d36f9]986 /* Update statistic. */
987 if (expedite) {
988 ++rcu.stat_expedited_cnt;
989 }
[a35b458]990
[1b20da0]991 /*
[d4d36f9]992 * All cpus have passed through a QS and see the most recent _rcu_cur_gp.
993 * As a result newly preempted readers will associate with next_preempted
994 * and the number of old readers in cur_preempted will monotonically
995 * decrease. Wait for those old/preexisting readers.
996 */
997 return wait_for_preempt_reader();
[0cf813d]998}
999
[d4d36f9]1000static bool gp_sleep(bool *expedite)
[181a746]1001{
[d4d36f9]1002 if (*expedite) {
1003 scheduler();
1004 return true;
1005 } else {
1006 spinlock_lock(&rcu.gp_lock);
[181a746]1007
[b7fd2a0]1008 errno_t ret = 0;
[d4d36f9]1009 ret = _condvar_wait_timeout_spinlock(&rcu.expedite_now, &rcu.gp_lock,
[18b6a88]1010 DETECT_SLEEP_MS * 1000, SYNCH_FLAGS_INTERRUPTIBLE);
[d4d36f9]1011
1012 /* rcu.expedite_now was signaled. */
[897fd8f1]1013 if (ret == EOK) {
[d4d36f9]1014 *expedite = true;
[181a746]1015 }
[d4d36f9]1016
1017 spinlock_unlock(&rcu.gp_lock);
1018
[897fd8f1]1019 return (ret != EINTR);
[181a746]1020 }
1021}
1022
[d4d36f9]1023static void sample_local_cpu(void *arg)
[181a746]1024{
[63e27ef]1025 assert(interrupts_disabled());
[d4d36f9]1026 cpu_mask_t *reader_cpus = (cpu_mask_t *)arg;
[a35b458]1027
[d4d36f9]1028 bool locked = RCU_CNT_INC <= THE->rcu_nesting;
[853d613]1029 /* smp_call machinery makes the most current _rcu_cur_gp visible. */
[d4d36f9]1030 bool passed_qs = (CPU->rcu.last_seen_gp == _rcu_cur_gp);
[a35b458]1031
[d4d36f9]1032 if (locked && !passed_qs) {
[1b20da0]1033 /*
[d4d36f9]1034 * This cpu has not yet passed a quiescent state during this grace
1035 * period and it is currently in a reader section. We'll have to
1036 * try to sample this cpu again later.
1037 */
1038 } else {
1039 /* Either not in a reader section or already passed a QS. */
1040 cpu_mask_reset(reader_cpus, CPU->id);
1041 /* Contain new reader sections and make prior changes visible to them.*/
1042 memory_barrier();
1043 CPU->rcu.last_seen_gp = _rcu_cur_gp;
1044 }
1045}
1046
1047/** Called by the scheduler() when switching away from the current thread. */
1048void rcu_after_thread_ran(void)
1049{
[63e27ef]1050 assert(interrupts_disabled());
[d4d36f9]1051
[1b20da0]1052 /*
1053 * In order not to worry about NMI seeing rcu_nesting change work
[853d613]1054 * with a local copy.
1055 */
[82719589]1056 size_t nesting_cnt = local_atomic_exchange(&THE->rcu_nesting, 0);
[a35b458]1057
[1b20da0]1058 /*
[82719589]1059 * Ensures NMIs see .rcu_nesting without the WAS_PREEMPTED mark and
1060 * do not accidentally call rm_preempted_reader() from unlock().
1061 */
1062 compiler_barrier();
[a35b458]1063
[d4d36f9]1064 /* Preempted a reader critical section for the first time. */
[853d613]1065 if (RCU_CNT_INC <= nesting_cnt && !(nesting_cnt & RCU_WAS_PREEMPTED)) {
1066 nesting_cnt |= RCU_WAS_PREEMPTED;
[d4d36f9]1067 note_preempted_reader();
1068 }
[a35b458]1069
[d4d36f9]1070 /* Save the thread's nesting count when it is not running. */
[853d613]1071 THREAD->rcu.nesting_cnt = nesting_cnt;
[d4d36f9]1072
1073 if (CPU->rcu.last_seen_gp != _rcu_cur_gp) {
[1b20da0]1074 /*
1075 * Contain any memory accesses of old readers before announcing a QS.
[d4d36f9]1076 * Also make changes from the previous GP visible to this cpu.
[1b20da0]1077 * Moreover it separates writing to last_seen_gp from
[853d613]1078 * note_preempted_reader().
[d4d36f9]1079 */
1080 memory_barrier();
[1b20da0]1081 /*
[853d613]1082 * The preempted reader has been noted globally. There are therefore
1083 * no readers running on this cpu so this is a quiescent state.
[1b20da0]1084 *
1085 * Reading the multiword _rcu_cur_gp non-atomically is benign.
[853d613]1086 * At worst, the read value will be different from the actual value.
1087 * As a result, both the detector and this cpu will believe
1088 * this cpu has not yet passed a QS although it really did.
[1b20da0]1089 *
[fbe6b65]1090 * Reloading _rcu_cur_gp is benign, because it cannot change
1091 * until this cpu acknowledges it passed a QS by writing to
1092 * last_seen_gp. Since interrupts are disabled, only this
1093 * code may to so (IPIs won't get through).
[853d613]1094 */
[d4d36f9]1095 CPU->rcu.last_seen_gp = _rcu_cur_gp;
1096 }
1097
[1b20da0]1098 /*
[853d613]1099 * Forcefully associate the reclaimer with the highest priority
[d4d36f9]1100 * even if preempted due to its time slice running out.
1101 */
1102 if (THREAD == CPU->rcu.reclaimer_thr) {
1103 THREAD->priority = -1;
[1b20da0]1104 }
[a35b458]1105
[82719589]1106 upd_max_cbs_in_slice(CPU->rcu.arriving_cbs_cnt);
[d4d36f9]1107}
1108
1109/** Called by the scheduler() when switching to a newly scheduled thread. */
1110void rcu_before_thread_runs(void)
1111{
[63e27ef]1112 assert(!rcu_read_locked());
[a35b458]1113
[d4d36f9]1114 /* Load the thread's saved nesting count from before it was preempted. */
1115 THE->rcu_nesting = THREAD->rcu.nesting_cnt;
1116}
1117
[1b20da0]1118/** Called from scheduler() when exiting the current thread.
1119 *
[d4d36f9]1120 * Preemption or interrupts are disabled and the scheduler() already
1121 * switched away from the current thread, calling rcu_after_thread_ran().
1122 */
1123void rcu_thread_exiting(void)
1124{
[63e27ef]1125 assert(THE->rcu_nesting == 0);
[a35b458]1126
[1b20da0]1127 /*
1128 * The thread forgot to exit its reader critical section.
[d4d36f9]1129 * It is a bug, but rather than letting the entire system lock up
[1b20da0]1130 * forcefully leave the reader section. The thread is not holding
[d4d36f9]1131 * any references anyway since it is exiting so it is safe.
1132 */
1133 if (RCU_CNT_INC <= THREAD->rcu.nesting_cnt) {
1134 /* Emulate _rcu_preempted_unlock() with the proper nesting count. */
1135 if (THREAD->rcu.nesting_cnt & RCU_WAS_PREEMPTED) {
1136 rm_preempted_reader();
1137 }
[fbe17545]1138
1139 printf("Bug: thread (id %" PRIu64 " \"%s\") exited while in RCU read"
[18b6a88]1140 " section.\n", THREAD->tid, THREAD->name);
[d4d36f9]1141 }
1142}
1143
1144/** Returns true if in an rcu reader section. */
1145bool rcu_read_locked(void)
1146{
1147 return RCU_CNT_INC <= THE->rcu_nesting;
1148}
1149
1150/** Invoked when a preempted reader finally exits its reader section. */
1151void _rcu_preempted_unlock(void)
1152{
[63e27ef]1153 assert(0 == THE->rcu_nesting || RCU_WAS_PREEMPTED == THE->rcu_nesting);
[a35b458]1154
[82719589]1155 size_t prev = local_atomic_exchange(&THE->rcu_nesting, 0);
1156 if (prev == RCU_WAS_PREEMPTED) {
[1b20da0]1157 /*
[fbe6b65]1158 * NMI handlers are never preempted but may call rm_preempted_reader()
1159 * if a NMI occurred in _rcu_preempted_unlock() of a preempted thread.
[82719589]1160 * The only other rcu code that may have been interrupted by the NMI
1161 * in _rcu_preempted_unlock() is: an IPI/sample_local_cpu() and
1162 * the initial part of rcu_after_thread_ran().
[1b20da0]1163 *
[fbe6b65]1164 * rm_preempted_reader() will not deadlock because none of the locks
[82719589]1165 * it uses are locked in this case. Neither _rcu_preempted_unlock()
1166 * nor sample_local_cpu() nor the initial part of rcu_after_thread_ran()
1167 * acquire any locks.
[fbe6b65]1168 */
[d4d36f9]1169 rm_preempted_reader();
1170 }
1171}
1172
1173#elif defined(RCU_PREEMPT_PODZIMEK)
1174
[1b20da0]1175/** Waits for the grace period associated with callbacks cub_cbs to elapse.
1176 *
1177 * @param expedite Instructs the detector to aggressively speed up grace
[d4d36f9]1178 * period detection without any delay.
[1b20da0]1179 * @param completed_gp Returns the most recent completed grace period
[d4d36f9]1180 * number.
1181 * @return false if the thread was interrupted and should stop.
1182 */
1183static bool wait_for_cur_cbs_gp_end(bool expedite, rcu_gp_t *completed_gp)
1184{
[1b20da0]1185 /*
[d4d36f9]1186 * Use a possibly outdated version of completed_gp to bypass checking
1187 * with the lock.
[1b20da0]1188 *
1189 * Note that loading and storing rcu.completed_gp is not atomic
1190 * (it is 64bit wide). Reading a clobbered value that is less than
1191 * rcu.completed_gp is harmless - we'll recheck with a lock. The
1192 * only way to read a clobbered value that is greater than the actual
1193 * value is if the detector increases the higher-order word first and
1194 * then decreases the lower-order word (or we see stores in that order),
1195 * eg when incrementing from 2^32 - 1 to 2^32. The loaded value
1196 * suddenly jumps by 2^32. It would take hours for such an increase
1197 * to occur so it is safe to discard the value. We allow increases
[d4d36f9]1198 * of up to half the maximum to generously accommodate for loading an
1199 * outdated lower word.
1200 */
1201 rcu_gp_t compl_gp = ACCESS_ONCE(rcu.completed_gp);
[18b6a88]1202 if (CPU->rcu.cur_cbs_gp <= compl_gp &&
1203 compl_gp <= CPU->rcu.cur_cbs_gp + UINT32_MAX_HALF) {
[d4d36f9]1204 *completed_gp = compl_gp;
1205 return true;
1206 }
[a35b458]1207
[d4d36f9]1208 spinlock_lock(&rcu.gp_lock);
[a35b458]1209
[d4d36f9]1210 if (CPU->rcu.cur_cbs_gp <= rcu.completed_gp) {
1211 *completed_gp = rcu.completed_gp;
1212 spinlock_unlock(&rcu.gp_lock);
1213 return true;
1214 }
[a35b458]1215
[63e27ef]1216 assert(CPU->rcu.cur_cbs_gp <= CPU->rcu.next_cbs_gp);
1217 assert(_rcu_cur_gp <= CPU->rcu.cur_cbs_gp);
[a35b458]1218
[1b20da0]1219 /*
1220 * Notify the detector of how many GP ends we intend to wait for, so
[d4d36f9]1221 * it can avoid going to sleep unnecessarily. Optimistically assume
1222 * new callbacks will arrive while we're waiting; hence +1.
1223 */
1224 size_t remaining_gp_ends = (size_t) (CPU->rcu.next_cbs_gp - _rcu_cur_gp);
1225 req_detection(remaining_gp_ends + (arriving_cbs_empty() ? 0 : 1));
[a35b458]1226
[1b20da0]1227 /*
1228 * Ask the detector to speed up GP detection if there are too many
[d4d36f9]1229 * pending callbacks and other reclaimers have not already done so.
1230 */
1231 if (expedite) {
[18b6a88]1232 if (0 == rcu.req_expedited_cnt)
[d4d36f9]1233 condvar_signal(&rcu.expedite_now);
[a35b458]1234
[1b20da0]1235 /*
1236 * Expedite only cub_cbs. If there really is a surge of callbacks
[d4d36f9]1237 * the arriving batch will expedite the GP for the huge number
1238 * of callbacks currently in next_cbs
1239 */
1240 rcu.req_expedited_cnt = 1;
1241 }
1242
1243 /* Wait for cur_cbs_gp to end. */
1244 bool interrupted = cv_wait_for_gp(CPU->rcu.cur_cbs_gp);
[a35b458]1245
[d4d36f9]1246 *completed_gp = rcu.completed_gp;
[1b20da0]1247 spinlock_unlock(&rcu.gp_lock);
[a35b458]1248
[09737cc]1249 if (!interrupted)
1250 upd_missed_gp_in_wait(*completed_gp);
[a35b458]1251
[d4d36f9]1252 return !interrupted;
1253}
1254
1255/** Waits for an announcement of the end of the grace period wait_on_gp. */
1256static bool cv_wait_for_gp(rcu_gp_t wait_on_gp)
1257{
[63e27ef]1258 assert(spinlock_locked(&rcu.gp_lock));
[a35b458]1259
[d4d36f9]1260 bool interrupted = false;
[a35b458]1261
[d4d36f9]1262 /* Wait until wait_on_gp ends. */
1263 while (rcu.completed_gp < wait_on_gp && !interrupted) {
[1b20da0]1264 int ret = _condvar_wait_timeout_spinlock(&rcu.gp_ended, &rcu.gp_lock,
[18b6a88]1265 SYNCH_NO_TIMEOUT, SYNCH_FLAGS_INTERRUPTIBLE);
[897fd8f1]1266 interrupted = (ret == EINTR);
[181a746]1267 }
[a35b458]1268
[181a746]1269 return interrupted;
1270}
1271
[d4d36f9]1272/** Requests the detector to detect at least req_cnt consecutive grace periods.*/
1273static void req_detection(size_t req_cnt)
1274{
1275 if (rcu.req_gp_end_cnt < req_cnt) {
1276 bool detector_idle = (0 == rcu.req_gp_end_cnt);
1277 rcu.req_gp_end_cnt = req_cnt;
1278
1279 if (detector_idle) {
[63e27ef]1280 assert(_rcu_cur_gp == rcu.completed_gp);
[d4d36f9]1281 condvar_signal(&rcu.req_gp_changed);
1282 }
1283 }
1284}
1285
[181a746]1286/** The detector thread detects and notifies reclaimers of grace period ends. */
1287static void detector(void *arg)
1288{
1289 spinlock_lock(&rcu.gp_lock);
[a35b458]1290
[181a746]1291 while (wait_for_detect_req()) {
[1b20da0]1292 /*
[181a746]1293 * Announce new GP started. Readers start lazily acknowledging that
1294 * they passed a QS.
1295 */
1296 start_new_gp();
[a35b458]1297
[181a746]1298 spinlock_unlock(&rcu.gp_lock);
[a35b458]1299
[1b20da0]1300 if (!wait_for_readers())
[181a746]1301 goto unlocked_out;
[a35b458]1302
[181a746]1303 spinlock_lock(&rcu.gp_lock);
1304
1305 /* Notify reclaimers that they may now invoke queued callbacks. */
1306 end_cur_gp();
1307 }
[a35b458]1308
[181a746]1309 spinlock_unlock(&rcu.gp_lock);
[a35b458]1310
[181a746]1311unlocked_out:
1312 return;
1313}
1314
1315/** Waits for a request from a reclaimer thread to detect a grace period. */
1316static bool wait_for_detect_req(void)
1317{
[63e27ef]1318 assert(spinlock_locked(&rcu.gp_lock));
[a35b458]1319
[181a746]1320 bool interrupted = false;
[a35b458]1321
[181a746]1322 while (0 == rcu.req_gp_end_cnt && !interrupted) {
[1b20da0]1323 int ret = _condvar_wait_timeout_spinlock(&rcu.req_gp_changed,
[18b6a88]1324 &rcu.gp_lock, SYNCH_NO_TIMEOUT, SYNCH_FLAGS_INTERRUPTIBLE);
[a35b458]1325
[897fd8f1]1326 interrupted = (ret == EINTR);
[181a746]1327 }
[a35b458]1328
[d4d36f9]1329 return !interrupted;
1330}
1331
1332static void end_cur_gp(void)
1333{
[63e27ef]1334 assert(spinlock_locked(&rcu.gp_lock));
[a35b458]1335
[d4d36f9]1336 rcu.completed_gp = _rcu_cur_gp;
1337 --rcu.req_gp_end_cnt;
[a35b458]1338
[d4d36f9]1339 condvar_broadcast(&rcu.gp_ended);
1340}
1341
1342/** Waits for readers that started before the current GP started to finish. */
1343static bool wait_for_readers(void)
1344{
1345 DEFINE_CPU_MASK(reading_cpus);
[a35b458]1346
[d4d36f9]1347 /* All running cpus have potential readers. */
1348 cpu_mask_active(reading_cpus);
1349
[1b20da0]1350 /*
1351 * Give readers time to pass through a QS. Also, batch arriving
[d4d36f9]1352 * callbacks in order to amortize detection overhead.
1353 */
1354 if (!gp_sleep())
1355 return false;
[a35b458]1356
[d4d36f9]1357 /* Non-intrusively determine which cpus have yet to pass a QS. */
1358 rm_quiescent_cpus(reading_cpus);
[a35b458]1359
[d4d36f9]1360 /* Actively interrupt cpus delaying the current GP and demand a QS. */
1361 interrupt_delaying_cpus(reading_cpus);
[a35b458]1362
[d4d36f9]1363 /* Wait for the interrupted cpus to notify us that they reached a QS. */
1364 if (!wait_for_delaying_cpus())
1365 return false;
1366 /*
1367 * All cpus recorded a QS or are still idle. Any new readers will be added
1368 * to next_preempt if preempted, ie the number of readers in cur_preempted
1369 * monotonically descreases.
1370 */
[a35b458]1371
[d4d36f9]1372 /* Wait for the last reader in cur_preempted to notify us it is done. */
1373 if (!wait_for_preempt_reader())
1374 return false;
[a35b458]1375
[d4d36f9]1376 return true;
1377}
1378
1379/** Sleeps a while if the current grace period is not to be expedited. */
1380static bool gp_sleep(void)
1381{
1382 spinlock_lock(&rcu.gp_lock);
1383
1384 int ret = 0;
1385 while (0 == rcu.req_expedited_cnt && 0 == ret) {
1386 /* minor bug: sleeps for the same duration if woken up spuriously. */
1387 ret = _condvar_wait_timeout_spinlock(&rcu.expedite_now, &rcu.gp_lock,
[18b6a88]1388 DETECT_SLEEP_MS * 1000, SYNCH_FLAGS_INTERRUPTIBLE);
[d4d36f9]1389 }
[a35b458]1390
[d4d36f9]1391 if (0 < rcu.req_expedited_cnt) {
1392 --rcu.req_expedited_cnt;
1393 /* Update statistic. */
1394 ++rcu.stat_expedited_cnt;
1395 }
[a35b458]1396
[d4d36f9]1397 spinlock_unlock(&rcu.gp_lock);
[a35b458]1398
[897fd8f1]1399 return (ret != EINTR);
[d4d36f9]1400}
1401
1402/** Actively interrupts and checks the offending cpus for quiescent states. */
1403static void interrupt_delaying_cpus(cpu_mask_t *cpu_mask)
1404{
[e3306d04]1405 atomic_store(&rcu.delaying_cpu_cnt, 0);
[a35b458]1406
[205832b]1407 sample_cpus(cpu_mask, NULL);
[d4d36f9]1408}
1409
[1b20da0]1410/** Invoked on a cpu delaying grace period detection.
1411 *
1412 * Induces a quiescent state for the cpu or it instructs remaining
[d4d36f9]1413 * readers to notify the detector once they finish.
1414 */
1415static void sample_local_cpu(void *arg)
1416{
[63e27ef]1417 assert(interrupts_disabled());
1418 assert(!CPU->rcu.is_delaying_gp);
[a35b458]1419
[d4d36f9]1420 /* Cpu did not pass a quiescent state yet. */
1421 if (CPU->rcu.last_seen_gp != _rcu_cur_gp) {
1422 /* Interrupted a reader in a reader critical section. */
1423 if (0 < CPU->rcu.nesting_cnt) {
[63e27ef]1424 assert(!CPU->idle);
[1b20da0]1425 /*
1426 * Note to notify the detector from rcu_read_unlock().
1427 *
[82719589]1428 * ACCESS_ONCE ensures the compiler writes to is_delaying_gp
1429 * only after it determines that we are in a reader CS.
[d4d36f9]1430 */
[82719589]1431 ACCESS_ONCE(CPU->rcu.is_delaying_gp) = true;
[d4d36f9]1432 CPU->rcu.signal_unlock = true;
[a35b458]1433
[d4d36f9]1434 atomic_inc(&rcu.delaying_cpu_cnt);
1435 } else {
[1b20da0]1436 /*
1437 * The cpu did not enter any rcu reader sections since
[d4d36f9]1438 * the start of the current GP. Record a quiescent state.
[1b20da0]1439 *
[d4d36f9]1440 * Or, we interrupted rcu_read_unlock_impl() right before
[1b20da0]1441 * it recorded a QS. Record a QS for it. The memory barrier
1442 * contains the reader section's mem accesses before
[d4d36f9]1443 * updating last_seen_gp.
[1b20da0]1444 *
[d4d36f9]1445 * Or, we interrupted rcu_read_lock() right after it recorded
1446 * a QS for the previous GP but before it got a chance to
1447 * increment its nesting count. The memory barrier again
1448 * stops the CS code from spilling out of the CS.
1449 */
1450 memory_barrier();
1451 CPU->rcu.last_seen_gp = _rcu_cur_gp;
1452 }
1453 } else {
[1b20da0]1454 /*
1455 * This cpu already acknowledged that it had passed through
1456 * a quiescent state since the start of cur_gp.
[d4d36f9]1457 */
1458 }
[a35b458]1459
[1b20da0]1460 /*
[d4d36f9]1461 * smp_call() makes sure any changes propagate back to the caller.
1462 * In particular, it makes the most current last_seen_gp visible
1463 * to the detector.
1464 */
1465}
1466
1467/** Waits for cpus delaying the current grace period if there are any. */
1468static bool wait_for_delaying_cpus(void)
1469{
[036e97c]1470 int delaying_cpu_cnt = atomic_load(&rcu.delaying_cpu_cnt);
[d4d36f9]1471
[18b6a88]1472 for (int i = 0; i < delaying_cpu_cnt; ++i) {
[d4d36f9]1473 if (!semaphore_down_interruptable(&rcu.remaining_readers))
1474 return false;
1475 }
[a35b458]1476
[d4d36f9]1477 /* Update statistic. */
1478 rcu.stat_delayed_cnt += delaying_cpu_cnt;
[a35b458]1479
[d4d36f9]1480 return true;
1481}
1482
1483/** Called by the scheduler() when switching away from the current thread. */
1484void rcu_after_thread_ran(void)
1485{
[63e27ef]1486 assert(interrupts_disabled());
[d4d36f9]1487
[1b20da0]1488 /*
[d4d36f9]1489 * Prevent NMI handlers from interfering. The detector will be notified
[1b20da0]1490 * in this function if CPU->rcu.is_delaying_gp. The current thread is
[82719589]1491 * no longer running so there is nothing else to signal to the detector.
[d4d36f9]1492 */
1493 CPU->rcu.signal_unlock = false;
[1b20da0]1494 /*
1495 * Separates clearing of .signal_unlock from accesses to
[82719589]1496 * THREAD->rcu.was_preempted and CPU->rcu.nesting_cnt.
1497 */
[d4d36f9]1498 compiler_barrier();
[a35b458]1499
[d4d36f9]1500 /* Save the thread's nesting count when it is not running. */
1501 THREAD->rcu.nesting_cnt = CPU->rcu.nesting_cnt;
[a35b458]1502
[d4d36f9]1503 /* Preempted a reader critical section for the first time. */
1504 if (0 < THREAD->rcu.nesting_cnt && !THREAD->rcu.was_preempted) {
1505 THREAD->rcu.was_preempted = true;
1506 note_preempted_reader();
1507 }
[a35b458]1508
[1b20da0]1509 /*
[d4d36f9]1510 * The preempted reader has been noted globally. There are therefore
1511 * no readers running on this cpu so this is a quiescent state.
1512 */
1513 _rcu_record_qs();
1514
[1b20da0]1515 /*
1516 * Interrupt handlers might use RCU while idle in scheduler().
1517 * The preempted reader has been noted globally, so the handlers
[82719589]1518 * may now start announcing quiescent states.
1519 */
1520 CPU->rcu.nesting_cnt = 0;
[a35b458]1521
[1b20da0]1522 /*
1523 * This cpu is holding up the current GP. Let the detector know
1524 * it has just passed a quiescent state.
1525 *
1526 * The detector waits separately for preempted readers, so we have
[d4d36f9]1527 * to notify the detector even if we have just preempted a reader.
1528 */
1529 if (CPU->rcu.is_delaying_gp) {
1530 CPU->rcu.is_delaying_gp = false;
1531 semaphore_up(&rcu.remaining_readers);
1532 }
1533
[1b20da0]1534 /*
[d4d36f9]1535 * Forcefully associate the detector with the highest priority
1536 * even if preempted due to its time slice running out.
[1b20da0]1537 *
[d4d36f9]1538 * todo: Replace with strict scheduler priority classes.
1539 */
1540 if (THREAD == rcu.detector_thr) {
1541 THREAD->priority = -1;
[18b6a88]1542 } else if (THREAD == CPU->rcu.reclaimer_thr) {
[d4d36f9]1543 THREAD->priority = -1;
[1b20da0]1544 }
[a35b458]1545
[82719589]1546 upd_max_cbs_in_slice(CPU->rcu.arriving_cbs_cnt);
[d4d36f9]1547}
1548
1549/** Called by the scheduler() when switching to a newly scheduled thread. */
1550void rcu_before_thread_runs(void)
1551{
[63e27ef]1552 assert(PREEMPTION_DISABLED || interrupts_disabled());
1553 assert(0 == CPU->rcu.nesting_cnt);
[a35b458]1554
[d4d36f9]1555 /* Load the thread's saved nesting count from before it was preempted. */
1556 CPU->rcu.nesting_cnt = THREAD->rcu.nesting_cnt;
[a35b458]1557
[1b20da0]1558 /*
[82719589]1559 * Ensures NMI see the proper nesting count before .signal_unlock.
1560 * Otherwise the NMI may incorrectly signal that a preempted reader
1561 * exited its reader section.
1562 */
1563 compiler_barrier();
[a35b458]1564
[1b20da0]1565 /*
1566 * In the unlikely event that a NMI occurs between the loading of the
1567 * variables and setting signal_unlock, the NMI handler may invoke
[d4d36f9]1568 * rcu_read_unlock() and clear signal_unlock. In that case we will
1569 * incorrectly overwrite signal_unlock from false to true. This event
[1b20da0]1570 * is benign and the next rcu_read_unlock() will at worst
[d4d36f9]1571 * needlessly invoke _rcu_signal_unlock().
1572 */
1573 CPU->rcu.signal_unlock = THREAD->rcu.was_preempted || CPU->rcu.is_delaying_gp;
1574}
1575
[1b20da0]1576/** Called from scheduler() when exiting the current thread.
1577 *
[d4d36f9]1578 * Preemption or interrupts are disabled and the scheduler() already
1579 * switched away from the current thread, calling rcu_after_thread_ran().
1580 */
1581void rcu_thread_exiting(void)
1582{
[63e27ef]1583 assert(THREAD != NULL);
1584 assert(THREAD->state == Exiting);
1585 assert(PREEMPTION_DISABLED || interrupts_disabled());
[a35b458]1586
[1b20da0]1587 /*
1588 * The thread forgot to exit its reader critical section.
[d4d36f9]1589 * It is a bug, but rather than letting the entire system lock up
[1b20da0]1590 * forcefully leave the reader section. The thread is not holding
[d4d36f9]1591 * any references anyway since it is exiting so it is safe.
1592 */
1593 if (0 < THREAD->rcu.nesting_cnt) {
1594 THREAD->rcu.nesting_cnt = 1;
1595 read_unlock_impl(&THREAD->rcu.nesting_cnt);
[fbe17545]1596
1597 printf("Bug: thread (id %" PRIu64 " \"%s\") exited while in RCU read"
[18b6a88]1598 " section.\n", THREAD->tid, THREAD->name);
[d4d36f9]1599 }
[181a746]1600}
1601
[d4d36f9]1602#endif /* RCU_PREEMPT_PODZIMEK */
1603
[181a746]1604/** Announces the start of a new grace period for preexisting readers to ack. */
1605static void start_new_gp(void)
1606{
[63e27ef]1607 assert(spinlock_locked(&rcu.gp_lock));
[a35b458]1608
[181a746]1609 irq_spinlock_lock(&rcu.preempt_lock, true);
[a35b458]1610
[181a746]1611 /* Start a new GP. Announce to readers that a quiescent state is needed. */
[8e3ed06]1612 ++_rcu_cur_gp;
[a35b458]1613
[1b20da0]1614 /*
[181a746]1615 * Readers preempted before the start of this GP (next_preempted)
[1b20da0]1616 * are preexisting readers now that a GP started and will hold up
[181a746]1617 * the current GP until they exit their reader sections.
[1b20da0]1618 *
1619 * Preempted readers from the previous GP have finished so
1620 * cur_preempted is empty, but see comment in _rcu_record_qs().
[181a746]1621 */
[c14762e]1622 list_concat(&rcu.cur_preempted, &rcu.next_preempted);
[a35b458]1623
[181a746]1624 irq_spinlock_unlock(&rcu.preempt_lock, true);
1625}
1626
[d4d36f9]1627/** Remove those cpus from the mask that have already passed a quiescent
1628 * state since the start of the current grace period.
1629 */
1630static void rm_quiescent_cpus(cpu_mask_t *cpu_mask)
[181a746]1631{
1632 /*
[1b20da0]1633 * Ensure the announcement of the start of a new GP (ie up-to-date
1634 * cur_gp) propagates to cpus that are just coming out of idle
[181a746]1635 * mode before we sample their idle state flag.
[1b20da0]1636 *
[181a746]1637 * Cpus guarantee that after they set CPU->idle = true they will not
1638 * execute any RCU reader sections without first setting idle to
1639 * false and issuing a memory barrier. Therefore, if rm_quiescent_cpus()
1640 * later on sees an idle cpu, but the cpu is just exiting its idle mode,
1641 * the cpu must not have yet executed its memory barrier (otherwise
1642 * it would pair up with this mem barrier and we would see idle == false).
1643 * That memory barrier will pair up with the one below and ensure
1644 * that a reader on the now-non-idle cpu will see the most current
1645 * cur_gp. As a result, such a reader will never attempt to semaphore_up(
1646 * pending_readers) during this GP, which allows the detector to
1647 * ignore that cpu (the detector thinks it is idle). Moreover, any
1648 * changes made by RCU updaters will have propagated to readers
1649 * on the previously idle cpu -- again thanks to issuing a memory
1650 * barrier after returning from idle mode.
[1b20da0]1651 *
[181a746]1652 * idle -> non-idle cpu | detector | reclaimer
1653 * ------------------------------------------------------
1654 * rcu reader 1 | | rcu_call()
1655 * MB X | |
[1b20da0]1656 * idle = true | | rcu_call()
1657 * (no rcu readers allowed ) | | MB A in advance_cbs()
[181a746]1658 * MB Y | (...) | (...)
[1b20da0]1659 * (no rcu readers allowed) | | MB B in advance_cbs()
[181a746]1660 * idle = false | ++cur_gp |
1661 * (no rcu readers allowed) | MB C |
1662 * MB Z | signal gp_end |
1663 * rcu reader 2 | | exec_cur_cbs()
[1b20da0]1664 *
1665 *
[181a746]1666 * MB Y orders visibility of changes to idle for detector's sake.
[1b20da0]1667 *
1668 * MB Z pairs up with MB C. The cpu making a transition from idle
[181a746]1669 * will see the most current value of cur_gp and will not attempt
1670 * to notify the detector even if preempted during this GP.
[1b20da0]1671 *
[181a746]1672 * MB Z pairs up with MB A from the previous batch. Updaters' changes
[1b20da0]1673 * are visible to reader 2 even when the detector thinks the cpu is idle
[181a746]1674 * but it is not anymore.
[1b20da0]1675 *
[181a746]1676 * MB X pairs up with MB B. Late mem accesses of reader 1 are contained
[1b20da0]1677 * and visible before idling and before any callbacks are executed
[181a746]1678 * by reclaimers.
[1b20da0]1679 *
[181a746]1680 * In summary, the detector does not know of or wait for reader 2, but
1681 * it does not have to since it is a new reader that will not access
1682 * data from previous GPs and will see any changes.
1683 */
1684 memory_barrier(); /* MB C */
[a35b458]1685
[181a746]1686 cpu_mask_for_each(*cpu_mask, cpu_id) {
[1b20da0]1687 /*
1688 * The cpu already checked for and passed through a quiescent
[181a746]1689 * state since the beginning of this GP.
[1b20da0]1690 *
1691 * _rcu_cur_gp is modified by local detector thread only.
1692 * Therefore, it is up-to-date even without a lock.
1693 *
[853d613]1694 * cpu.last_seen_gp may not be up-to-date. At worst, we will
[1b20da0]1695 * unnecessarily sample its last_seen_gp with a smp_call.
[181a746]1696 */
[8e3ed06]1697 bool cpu_acked_gp = (cpus[cpu_id].rcu.last_seen_gp == _rcu_cur_gp);
[a35b458]1698
[181a746]1699 /*
1700 * Either the cpu is idle or it is exiting away from idle mode
[8e3ed06]1701 * and already sees the most current _rcu_cur_gp. See comment
[181a746]1702 * in wait_for_readers().
1703 */
1704 bool cpu_idle = cpus[cpu_id].idle;
[a35b458]1705
[181a746]1706 if (cpu_acked_gp || cpu_idle) {
1707 cpu_mask_reset(cpu_mask, cpu_id);
1708 }
1709 }
1710}
1711
[853d613]1712/** Serially invokes sample_local_cpu(arg) on each cpu of reader_cpus. */
[d4d36f9]1713static void sample_cpus(cpu_mask_t *reader_cpus, void *arg)
[181a746]1714{
[d4d36f9]1715 cpu_mask_for_each(*reader_cpus, cpu_id) {
[853d613]1716 smp_call(cpu_id, sample_local_cpu, arg);
[181a746]1717
1718 /* Update statistic. */
1719 if (CPU->id != cpu_id)
1720 ++rcu.stat_smp_call_cnt;
1721 }
1722}
1723
[d4d36f9]1724static void upd_missed_gp_in_wait(rcu_gp_t completed_gp)
[181a746]1725{
[63e27ef]1726 assert(CPU->rcu.cur_cbs_gp <= completed_gp);
[a35b458]1727
[d4d36f9]1728 size_t delta = (size_t)(completed_gp - CPU->rcu.cur_cbs_gp);
1729 CPU->rcu.stat_missed_gp_in_wait += delta;
1730}
1731
1732/** Globally note that the current thread was preempted in a reader section. */
1733static void note_preempted_reader(void)
1734{
1735 irq_spinlock_lock(&rcu.preempt_lock, false);
1736
[8e3ed06]1737 if (CPU->rcu.last_seen_gp != _rcu_cur_gp) {
[d4d36f9]1738 /* The reader started before the GP started - we must wait for it.*/
1739 list_append(&THREAD->rcu.preempt_link, &rcu.cur_preempted);
[181a746]1740 } else {
[1b20da0]1741 /*
[d4d36f9]1742 * The reader started after the GP started and this cpu
1743 * already noted a quiescent state. We might block the next GP.
[181a746]1744 */
[d4d36f9]1745 list_append(&THREAD->rcu.preempt_link, &rcu.next_preempted);
[181a746]1746 }
[d4d36f9]1747
1748 irq_spinlock_unlock(&rcu.preempt_lock, false);
[181a746]1749}
1750
[d4d36f9]1751/** Remove the current thread from the global list of preempted readers. */
1752static void rm_preempted_reader(void)
[181a746]1753{
[82719589]1754 irq_spinlock_lock(&rcu.preempt_lock, true);
[a35b458]1755
[63e27ef]1756 assert(link_used(&THREAD->rcu.preempt_link));
[79d74fe]1757
[d4d36f9]1758 bool prev_empty = list_empty(&rcu.cur_preempted);
1759 list_remove(&THREAD->rcu.preempt_link);
1760 bool now_empty = list_empty(&rcu.cur_preempted);
1761
1762 /* This was the last reader in cur_preempted. */
1763 bool last_removed = now_empty && !prev_empty;
1764
[1b20da0]1765 /*
1766 * Preempted readers are blocking the detector and
1767 * this was the last reader blocking the current GP.
[d4d36f9]1768 */
1769 if (last_removed && rcu.preempt_blocking_det) {
1770 rcu.preempt_blocking_det = false;
1771 semaphore_up(&rcu.remaining_readers);
[181a746]1772 }
[d4d36f9]1773
[82719589]1774 irq_spinlock_unlock(&rcu.preempt_lock, true);
[181a746]1775}
1776
1777/** Waits for any preempted readers blocking this grace period to finish.*/
1778static bool wait_for_preempt_reader(void)
1779{
1780 irq_spinlock_lock(&rcu.preempt_lock, true);
1781
1782 bool reader_exists = !list_empty(&rcu.cur_preempted);
1783 rcu.preempt_blocking_det = reader_exists;
[a35b458]1784
[181a746]1785 irq_spinlock_unlock(&rcu.preempt_lock, true);
[a35b458]1786
[181a746]1787 if (reader_exists) {
1788 /* Update statistic. */
1789 ++rcu.stat_preempt_blocking_cnt;
[a35b458]1790
[181a746]1791 return semaphore_down_interruptable(&rcu.remaining_readers);
[1b20da0]1792 }
[a35b458]1793
[181a746]1794 return true;
1795}
1796
[82719589]1797static void upd_max_cbs_in_slice(size_t arriving_cbs_cnt)
[0cf813d]1798{
1799 rcu_cpu_data_t *cr = &CPU->rcu;
[a35b458]1800
[82719589]1801 if (arriving_cbs_cnt > cr->last_arriving_cnt) {
1802 size_t arrived_cnt = arriving_cbs_cnt - cr->last_arriving_cnt;
[0cf813d]1803 cr->stat_max_slice_cbs = max(arrived_cnt, cr->stat_max_slice_cbs);
1804 }
[a35b458]1805
[82719589]1806 cr->last_arriving_cnt = arriving_cbs_cnt;
[181a746]1807}
1808
1809/** Prints RCU run-time statistics. */
1810void rcu_print_stat(void)
1811{
[1b20da0]1812 /*
1813 * Don't take locks. Worst case is we get out-dated values.
1814 * CPU local values are updated without any locks, so there
[0cf813d]1815 * are no locks to lock in order to get up-to-date values.
1816 */
[a35b458]1817
[d4d36f9]1818#ifdef RCU_PREEMPT_PODZIMEK
1819 const char *algo = "podzimek-preempt-rcu";
1820#elif defined(RCU_PREEMPT_A)
1821 const char *algo = "a-preempt-rcu";
1822#endif
[a35b458]1823
[d4d36f9]1824 printf("Config: expedite_threshold=%d, critical_threshold=%d,"
[18b6a88]1825 " detect_sleep=%dms, %s\n",
1826 EXPEDITE_THRESHOLD, CRITICAL_THRESHOLD, DETECT_SLEEP_MS, algo);
[181a746]1827 printf("Completed GPs: %" PRIu64 "\n", rcu.completed_gp);
1828 printf("Expedited GPs: %zu\n", rcu.stat_expedited_cnt);
[1b20da0]1829 printf("Delayed GPs: %zu (cpus w/ still running readers after gp sleep)\n",
[18b6a88]1830 rcu.stat_delayed_cnt);
[181a746]1831 printf("Preempt blocked GPs: %zu (waited for preempted readers; "
[18b6a88]1832 "running or not)\n", rcu.stat_preempt_blocking_cnt);
[b68ae24]1833 printf("Smp calls: %zu\n", rcu.stat_smp_call_cnt);
[a35b458]1834
[0cf813d]1835 printf("Max arrived callbacks per GP and CPU:\n");
1836 for (unsigned int i = 0; i < config.cpu_count; ++i) {
[181a746]1837 printf(" %zu", cpus[i].rcu.stat_max_cbs);
1838 }
1839
[0cf813d]1840 printf("\nAvg arrived callbacks per GP and CPU (nonempty batches only):\n");
1841 for (unsigned int i = 0; i < config.cpu_count; ++i) {
[181a746]1842 printf(" %zu", cpus[i].rcu.stat_avg_cbs);
1843 }
[a35b458]1844
[0cf813d]1845 printf("\nMax arrived callbacks per time slice and CPU:\n");
1846 for (unsigned int i = 0; i < config.cpu_count; ++i) {
1847 printf(" %zu", cpus[i].rcu.stat_max_slice_cbs);
1848 }
1849
1850 printf("\nMissed GP notifications per CPU:\n");
1851 for (unsigned int i = 0; i < config.cpu_count; ++i) {
[181a746]1852 printf(" %zu", cpus[i].rcu.stat_missed_gps);
1853 }
[0cf813d]1854
1855 printf("\nMissed GP notifications per CPU while waking up:\n");
1856 for (unsigned int i = 0; i < config.cpu_count; ++i) {
1857 printf(" %zu", cpus[i].rcu.stat_missed_gp_in_wait);
1858 }
[181a746]1859 printf("\n");
1860}
1861
1862/** @}
1863 */
Note: See TracBrowser for help on using the repository browser.