Index: HelenOS.config =================================================================== --- HelenOS.config (revision f0fcb040f13a5e81a4e704790bcd3b6fc4fe52cb) +++ HelenOS.config (revision d4d36f9fef8f29ad6987ffaad1de36b3e6939b97) @@ -385,4 +385,9 @@ ! [COMPILER=gcc_cross|COMPILER=gcc_native] CONFIG_LTO (n/y) +% Kernel RCU algorithm +@ "PREEMPT_PODZIMEK" Preemptible Podzimek-RCU +@ "PREEMPT_A" Preemptible A-RCU +! RCU (choice) + ## Hardware support Index: kernel/generic/include/arch.h =================================================================== --- kernel/generic/include/arch.h (revision f0fcb040f13a5e81a4e704790bcd3b6fc4fe52cb) +++ kernel/generic/include/arch.h (revision d4d36f9fef8f29ad6987ffaad1de36b3e6939b97) @@ -38,4 +38,5 @@ #include /* arch_pre_main() */ #include /* get_stack_base() */ +#include @@ -69,4 +70,7 @@ typedef struct { size_t preemption; /**< Preemption disabled counter and flag. */ +#ifdef RCU_PREEMPT_A + size_t rcu_nesting; /**< RCU nesting count and flag. */ +#endif struct thread *thread; /**< Current thread. */ struct task *task; /**< Current task. */ Index: kernel/generic/include/synch/rcu.h =================================================================== --- kernel/generic/include/synch/rcu.h (revision f0fcb040f13a5e81a4e704790bcd3b6fc4fe52cb) +++ kernel/generic/include/synch/rcu.h (revision d4d36f9fef8f29ad6987ffaad1de36b3e6939b97) @@ -123,4 +123,34 @@ extern void _rcu_synchronize(bool expedite); + +#ifdef RCU_PREEMPT_A + +#define RCU_CNT_INC (1 << 1) +#define RCU_WAS_PREEMPTED (1 << 0) + +/* Fwd. decl. because of inlining. */ +void _rcu_preempted_unlock(void); + +/** Delimits the start of an RCU reader critical section. + * + * Reader sections may be nested and are preemptable. You must not + * however block/sleep within reader sections. + */ +static inline void rcu_read_lock(void) +{ + THE->rcu_nesting += RCU_CNT_INC; +} + +/** Delimits the end of an RCU reader critical section. */ +static inline void rcu_read_unlock(void) +{ + THE->rcu_nesting -= RCU_CNT_INC; + + if (RCU_WAS_PREEMPTED == THE->rcu_nesting) { + _rcu_preempted_unlock(); + } +} + +#elif defined(RCU_PREEMPT_PODZIMEK) /* Fwd decl. required by the inlined implementation. Not part of public API. */ @@ -210,8 +240,8 @@ preemption_enable(); } - - #endif +#endif + /** @} */ Index: kernel/generic/include/synch/rcu_types.h =================================================================== --- kernel/generic/include/synch/rcu_types.h (revision f0fcb040f13a5e81a4e704790bcd3b6fc4fe52cb) +++ kernel/generic/include/synch/rcu_types.h (revision d4d36f9fef8f29ad6987ffaad1de36b3e6939b97) @@ -39,4 +39,9 @@ #include +#if !defined(RCU_PREEMPT_PODZIMEK) && !defined(RCU_PREEMPT_A) +#define RCU_PREEMPT_A +//#error You must select an RCU algorithm. +#endif + /* Fwd decl. */ @@ -58,7 +63,19 @@ /** RCU related per-cpu data. */ typedef struct rcu_cpu_data { - /** The cpu recorded a quiescent state last time during this grace period */ + /** The cpu recorded a quiescent state last time during this grace period.*/ rcu_gp_t last_seen_gp; + +#ifdef RCU_PREEMPT_PODZIMEK + /** This cpu has not yet passed a quiescent state and it is delaying the + * detector. Once it reaches a QS it must sema_up(rcu.remaining_readers). + */ + bool is_delaying_gp; + /** True if we should signal the detector that we exited a reader section. + * + * Equal to (THREAD->rcu.was_preempted || CPU->rcu.is_delaying_gp). + */ + bool signal_unlock; + /** The number of times an RCU reader section is nested on this cpu. * @@ -68,5 +85,6 @@ */ size_t nesting_cnt; - +#endif + /** Callbacks to invoke once the current grace period ends, ie cur_cbs_gp. * Accessed by the local reclaimer only. @@ -102,15 +120,4 @@ rcu_gp_t next_cbs_gp; - /** This cpu has not yet passed a quiescent state and it is delaying the - * detector. Once it reaches a QS it must sema_up(rcu.remaining_readers). - */ - bool is_delaying_gp; - - /** True if we should signal the detector that we exited a reader section. - * - * Equal to (THREAD->rcu.was_preempted || CPU->rcu.is_delaying_gp). - */ - bool signal_unlock; - /** Positive if there are callbacks pending in arriving_cbs. */ semaphore_t arrived_flag; @@ -142,4 +149,6 @@ */ size_t nesting_cnt; + +#ifdef RCU_PREEMPT_PODZIMEK /** True if the thread was preempted in a reader section. @@ -151,4 +160,6 @@ */ bool was_preempted; +#endif + /** Preempted threads link. Access with rcu.prempt_lock.*/ link_t preempt_link; Index: kernel/generic/src/proc/the.c =================================================================== --- kernel/generic/src/proc/the.c (revision f0fcb040f13a5e81a4e704790bcd3b6fc4fe52cb) +++ kernel/generic/src/proc/the.c (revision d4d36f9fef8f29ad6987ffaad1de36b3e6939b97) @@ -60,4 +60,7 @@ the->as = NULL; the->magic = MAGIC; +#ifdef RCU_PREEMPT_A + the->rcu_nesting = 0; +#endif } Index: kernel/generic/src/synch/rcu.c =================================================================== --- kernel/generic/src/synch/rcu.c (revision f0fcb040f13a5e81a4e704790bcd3b6fc4fe52cb) +++ kernel/generic/src/synch/rcu.c (revision d4d36f9fef8f29ad6987ffaad1de36b3e6939b97) @@ -81,25 +81,11 @@ /** Detector uses so signal reclaimers that a grace period ended. */ condvar_t gp_ended; - /** Reclaimers notify the detector when they request more grace periods.*/ - condvar_t req_gp_changed; /** Reclaimers use to notify the detector to accelerate GP detection. */ condvar_t expedite_now; /** - * The detector waits on this semaphore for any readers delaying the GP. - * - * Each of the cpus with readers that are delaying the current GP - * must up() this sema once they reach a quiescent state. If there - * are any readers in cur_preempted (ie preempted preexisting) and - * they are already delaying GP detection, the last to unlock its - * reader section must up() this sema once. - */ - semaphore_t remaining_readers; - - /** Protects the 4 fields below. */ + * Protects: req_gp_end_cnt, req_expedited_cnt, completed_gp, _rcu_cur_gp; + * or: completed_gp, _rcu_cur_gp + */ SPINLOCK_DECLARE(gp_lock); - /** Number of grace period ends the detector was requested to announce. */ - size_t req_gp_end_cnt; - /** Number of consecutive grace periods to detect quickly and aggressively.*/ - size_t req_expedited_cnt; /** * The number of the most recently completed grace period. At most @@ -122,4 +108,20 @@ bool preempt_blocking_det; +#ifdef RCU_PREEMPT_A + + /** + * The detector waits on this semaphore for any preempted readers + * delaying the grace period once all cpus pass a quiescent state. + */ + semaphore_t remaining_readers; + +#elif defined(RCU_PREEMPT_PODZIMEK) + + /** Reclaimers notify the detector when they request more grace periods.*/ + condvar_t req_gp_changed; + /** Number of grace period ends the detector was requested to announce. */ + size_t req_gp_end_cnt; + /** Number of consecutive grace periods to detect quickly and aggressively.*/ + size_t req_expedited_cnt; /** * Number of cpus with readers that are delaying the current GP. @@ -127,4 +129,15 @@ */ atomic_t delaying_cpu_cnt; + /** + * The detector waits on this semaphore for any readers delaying the GP. + * + * Each of the cpus with readers that are delaying the current GP + * must up() this sema once they reach a quiescent state. If there + * are any readers in cur_preempted (ie preempted preexisting) and + * they are already delaying GP detection, the last to unlock its + * reader section must up() this sema once. + */ + semaphore_t remaining_readers; +#endif /** Excludes simultaneous rcu_barrier() calls. */ @@ -149,7 +162,5 @@ static rcu_data_t rcu; -static void start_detector(void); static void start_reclaimers(void); -static void read_unlock_impl(size_t *pnesting_cnt); static void synch_complete(rcu_item_t *rcu_item); static void add_barrier_cb(void *arg); @@ -164,19 +175,31 @@ static void exec_completed_cbs(rcu_gp_t last_completed_gp); static void exec_cbs(rcu_item_t **phead); -static void req_detection(size_t req_cnt); static bool wait_for_cur_cbs_gp_end(bool expedite, rcu_gp_t *last_completed_gp); static void upd_missed_gp_in_wait(rcu_gp_t completed_gp); + +#ifdef RCU_PREEMPT_PODZIMEK +static void start_detector(void); +static void read_unlock_impl(size_t *pnesting_cnt); +static void req_detection(size_t req_cnt); static bool cv_wait_for_gp(rcu_gp_t wait_on_gp); static void detector(void *); static bool wait_for_detect_req(void); -static void start_new_gp(void); static void end_cur_gp(void); static bool wait_for_readers(void); -static void rm_quiescent_cpus(cpu_mask_t *cpu_mask); static bool gp_sleep(void); static void interrupt_delaying_cpus(cpu_mask_t *cpu_mask); +static bool wait_for_delaying_cpus(void); +#elif defined(RCU_PREEMPT_A) +static bool wait_for_readers(bool expedite); +static bool gp_sleep(bool *expedite); +#endif + +static void start_new_gp(void); +static void rm_quiescent_cpus(cpu_mask_t *cpu_mask); +static void sample_cpus(cpu_mask_t *reader_cpus, void *arg); static void sample_local_cpu(void *); -static bool wait_for_delaying_cpus(void); static bool wait_for_preempt_reader(void); +static void note_preempted_reader(void); +static void rm_preempted_reader(void); static void upd_max_cbs_in_slice(void); @@ -187,11 +210,7 @@ { condvar_initialize(&rcu.gp_ended); - condvar_initialize(&rcu.req_gp_changed); condvar_initialize(&rcu.expedite_now); - semaphore_initialize(&rcu.remaining_readers, 0); - + spinlock_initialize(&rcu.gp_lock, "rcu.gp_lock"); - rcu.req_gp_end_cnt = 0; - rcu.req_expedited_cnt = 0; _rcu_cur_gp = 0; rcu.completed_gp = 0; @@ -205,6 +224,14 @@ atomic_set(&rcu.barrier_wait_cnt, 0); waitq_initialize(&rcu.barrier_wq); - + + semaphore_initialize(&rcu.remaining_readers, 0); + +#ifdef RCU_PREEMPT_PODZIMEK + condvar_initialize(&rcu.req_gp_changed); + + rcu.req_gp_end_cnt = 0; + rcu.req_expedited_cnt = 0; atomic_set(&rcu.delaying_cpu_cnt, 0); +#endif rcu.detector_thr = 0; @@ -222,8 +249,12 @@ rcu_init(); } - + CPU->rcu.last_seen_gp = 0; - + +#ifdef RCU_PREEMPT_PODZIMEK CPU->rcu.nesting_cnt = 0; + CPU->rcu.is_delaying_gp = false; + CPU->rcu.signal_unlock = false; +#endif CPU->rcu.cur_cbs = 0; @@ -238,7 +269,4 @@ CPU->rcu.next_cbs_gp = 0; - CPU->rcu.is_delaying_gp = false; - CPU->rcu.signal_unlock = false; - semaphore_initialize(&CPU->rcu.arrived_flag, 0); @@ -258,5 +286,8 @@ void rcu_kinit_init(void) { +#ifdef RCU_PREEMPT_PODZIMEK start_detector(); +#endif + start_reclaimers(); } @@ -266,36 +297,12 @@ { thread->rcu.nesting_cnt = 0; + +#ifdef RCU_PREEMPT_PODZIMEK thread->rcu.was_preempted = false; +#endif + link_initialize(&thread->rcu.preempt_link); } -/** Called from scheduler() when exiting the current thread. - * - * Preemption or interrupts are disabled and the scheduler() already - * switched away from the current thread, calling rcu_after_thread_ran(). - */ -void rcu_thread_exiting(void) -{ - ASSERT(THREAD != 0); - ASSERT(THREAD->state == Exiting); - ASSERT(PREEMPTION_DISABLED || interrupts_disabled()); - /* - * The scheduler() must have already switched to a temporary - * nesting counter for interrupt handlers (we could be idle) - * so that interrupt handlers do not modify the exiting thread's - * reader section nesting count while we examine/process it. - */ - - /* - * The thread forgot to exit its reader critical section. - * It is a bug, but rather than letting the entire system lock up - * forcefully leave the reader section. The thread is not holding - * any references anyway since it is exiting so it is safe. - */ - if (0 < THREAD->rcu.nesting_cnt) { - THREAD->rcu.nesting_cnt = 1; - read_unlock_impl(&THREAD->rcu.nesting_cnt); - } -} /** Cleans up global RCU resources and stops dispatching callbacks. @@ -318,4 +325,5 @@ } +#ifdef RCU_PREEMPT_PODZIMEK /* Stop the detector and wait. */ if (rcu.detector_thr) { @@ -325,35 +333,5 @@ rcu.detector_thr = 0; } -} - -/** Starts the detector thread. */ -static void start_detector(void) -{ - rcu.detector_thr = - thread_create(detector, 0, TASK, THREAD_FLAG_NONE, "rcu-det"); - - if (!rcu.detector_thr) - panic("Failed to create RCU detector thread."); - - thread_ready(rcu.detector_thr); -} - -/** Creates and runs cpu-bound reclaimer threads. */ -static void start_reclaimers(void) -{ - for (unsigned int cpu_id = 0; cpu_id < config.cpu_count; ++cpu_id) { - char name[THREAD_NAME_BUFLEN] = {0}; - - snprintf(name, THREAD_NAME_BUFLEN - 1, "rcu-rec/%u", cpu_id); - - cpus[cpu_id].rcu.reclaimer_thr = - thread_create(reclaimer, 0, TASK, THREAD_FLAG_NONE, name); - - if (!cpus[cpu_id].rcu.reclaimer_thr) - panic("Failed to create RCU reclaimer thread on cpu%u.", cpu_id); - - thread_wire(cpus[cpu_id].rcu.reclaimer_thr, &cpus[cpu_id]); - thread_ready(cpus[cpu_id].rcu.reclaimer_thr); - } +#endif } @@ -366,4 +344,37 @@ return completed; +} + +/** Creates and runs cpu-bound reclaimer threads. */ +static void start_reclaimers(void) +{ + for (unsigned int cpu_id = 0; cpu_id < config.cpu_count; ++cpu_id) { + char name[THREAD_NAME_BUFLEN] = {0}; + + snprintf(name, THREAD_NAME_BUFLEN - 1, "rcu-rec/%u", cpu_id); + + cpus[cpu_id].rcu.reclaimer_thr = + thread_create(reclaimer, 0, TASK, THREAD_FLAG_NONE, name); + + if (!cpus[cpu_id].rcu.reclaimer_thr) + panic("Failed to create RCU reclaimer thread on cpu%u.", cpu_id); + + thread_wire(cpus[cpu_id].rcu.reclaimer_thr, &cpus[cpu_id]); + thread_ready(cpus[cpu_id].rcu.reclaimer_thr); + } +} + +#ifdef RCU_PREEMPT_PODZIMEK + +/** Starts the detector thread. */ +static void start_detector(void) +{ + rcu.detector_thr = + thread_create(detector, 0, TASK, THREAD_FLAG_NONE, "rcu-det"); + + if (!rcu.detector_thr) + panic("Failed to create RCU detector thread."); + + thread_ready(rcu.detector_thr); } @@ -440,23 +451,5 @@ THREAD->rcu.was_preempted = false; - irq_spinlock_lock(&rcu.preempt_lock, false); - - bool prev_empty = list_empty(&rcu.cur_preempted); - list_remove(&THREAD->rcu.preempt_link); - bool now_empty = list_empty(&rcu.cur_preempted); - - /* This was the last reader in cur_preempted. */ - bool last_removed = now_empty && !prev_empty; - - /* - * Preempted readers are blocking the detector and - * this was the last reader blocking the current GP. - */ - if (last_removed && rcu.preempt_blocking_det) { - rcu.preempt_blocking_det = false; - semaphore_up(&rcu.remaining_readers); - } - - irq_spinlock_unlock(&rcu.preempt_lock, false); + rm_preempted_reader(); } @@ -466,4 +459,6 @@ interrupts_restore(ipl); } + +#endif /* RCU_PREEMPT_PODZIMEK */ typedef struct synch_item { @@ -488,5 +483,5 @@ { /* Calling from a reader section will deadlock. */ - ASSERT(0 == CPU->rcu.nesting_cnt); + ASSERT(!rcu_read_locked()); synch_item_t completion; @@ -630,4 +625,5 @@ return cur_cbs_empty() && next_cbs_empty() && arriving_cbs_empty(); } + /** Reclaimer thread dispatches locally queued callbacks once a GP ends. */ @@ -747,5 +743,4 @@ } - /** Prepares another batch of callbacks to dispatch at the nest grace period. * @@ -817,4 +812,233 @@ return expedite; } + + +#ifdef RCU_PREEMPT_A + +/** Waits for the grace period associated with callbacks cub_cbs to elapse. + * + * @param expedite Instructs the detector to aggressively speed up grace + * period detection without any delay. + * @param completed_gp Returns the most recent completed grace period + * number. + * @return false if the thread was interrupted and should stop. + */ +static bool wait_for_cur_cbs_gp_end(bool expedite, rcu_gp_t *completed_gp) +{ + spinlock_lock(&rcu.gp_lock); + + ASSERT(CPU->rcu.cur_cbs_gp <= CPU->rcu.next_cbs_gp); + ASSERT(CPU->rcu.cur_cbs_gp <= _rcu_cur_gp + 1); + + while (rcu.completed_gp < CPU->rcu.cur_cbs_gp) { + /* GP has not yet started - start a new one. */ + if (rcu.completed_gp == _rcu_cur_gp) { + start_new_gp(); + spinlock_unlock(&rcu.gp_lock); + + if (!wait_for_readers(expedite)) + return false; + + spinlock_lock(&rcu.gp_lock); + /* Notify any reclaimers this GP had ended. */ + rcu.completed_gp = _rcu_cur_gp; + condvar_broadcast(&rcu.gp_ended); + } else { + /* GP detection is in progress.*/ + + if (expedite) + condvar_signal(&rcu.expedite_now); + + /* Wait for the GP to complete. */ + int ret = _condvar_wait_timeout_spinlock(&rcu.gp_ended, + &rcu.gp_lock, SYNCH_NO_TIMEOUT, SYNCH_FLAGS_INTERRUPTIBLE); + + if (ret == ESYNCH_INTERRUPTED) { + spinlock_unlock(&rcu.gp_lock); + return false; + } + + upd_missed_gp_in_wait(rcu.completed_gp); + } + } + + *completed_gp = rcu.completed_gp; + spinlock_unlock(&rcu.gp_lock); + + return true; +} + +static bool wait_for_readers(bool expedite) +{ + DEFINE_CPU_MASK(reader_cpus); + + cpu_mask_active(reader_cpus); + rm_quiescent_cpus(reader_cpus); + + while (!cpu_mask_is_none(reader_cpus)) { + /* Give cpus a chance to context switch (a QS) and batch callbacks. */ + if(!gp_sleep(&expedite)) + return false; + + rm_quiescent_cpus(reader_cpus); + sample_cpus(reader_cpus, reader_cpus); + } + + /* Update statistic. */ + if (expedite) { + ++rcu.stat_expedited_cnt; + } + + /* + * All cpus have passed through a QS and see the most recent _rcu_cur_gp. + * As a result newly preempted readers will associate with next_preempted + * and the number of old readers in cur_preempted will monotonically + * decrease. Wait for those old/preexisting readers. + */ + return wait_for_preempt_reader(); +} + +static bool gp_sleep(bool *expedite) +{ + if (*expedite) { + scheduler(); + return true; + } else { + spinlock_lock(&rcu.gp_lock); + + int ret = 0; + ret = _condvar_wait_timeout_spinlock(&rcu.expedite_now, &rcu.gp_lock, + DETECT_SLEEP_MS * 1000, SYNCH_FLAGS_INTERRUPTIBLE); + + /* rcu.expedite_now was signaled. */ + if (ret == ESYNCH_OK_BLOCKED) { + *expedite = true; + } + + spinlock_unlock(&rcu.gp_lock); + + return (ret != ESYNCH_INTERRUPTED); + } +} + +static void sample_local_cpu(void *arg) +{ + ASSERT(interrupts_disabled()); + cpu_mask_t *reader_cpus = (cpu_mask_t *)arg; + + bool locked = RCU_CNT_INC <= THE->rcu_nesting; + bool passed_qs = (CPU->rcu.last_seen_gp == _rcu_cur_gp); + + if (locked && !passed_qs) { + /* + * This cpu has not yet passed a quiescent state during this grace + * period and it is currently in a reader section. We'll have to + * try to sample this cpu again later. + */ + } else { + /* Either not in a reader section or already passed a QS. */ + cpu_mask_reset(reader_cpus, CPU->id); + /* Contain new reader sections and make prior changes visible to them.*/ + memory_barrier(); + CPU->rcu.last_seen_gp = _rcu_cur_gp; + } +} + +/** Called by the scheduler() when switching away from the current thread. */ +void rcu_after_thread_ran(void) +{ + ASSERT(interrupts_disabled()); + + /* Preempted a reader critical section for the first time. */ + if (rcu_read_locked() && !(THE->rcu_nesting & RCU_WAS_PREEMPTED)) { + THE->rcu_nesting |= RCU_WAS_PREEMPTED; + note_preempted_reader(); + } + + /* Save the thread's nesting count when it is not running. */ + THREAD->rcu.nesting_cnt = THE->rcu_nesting; + + /* Clear rcu_nesting only after noting that a thread was preempted. */ + compiler_barrier(); + THE->rcu_nesting = 0; + + if (CPU->rcu.last_seen_gp != _rcu_cur_gp) { + /* + * Contain any memory accesses of old readers before announcing a QS. + * Also make changes from the previous GP visible to this cpu. + */ + memory_barrier(); + /* + * The preempted reader has been noted globally. There are therefore + * no readers running on this cpu so this is a quiescent state. + */ + CPU->rcu.last_seen_gp = _rcu_cur_gp; + } + + /* + * Forcefully associate the reclaime with the highest priority + * even if preempted due to its time slice running out. + */ + if (THREAD == CPU->rcu.reclaimer_thr) { + THREAD->priority = -1; + } + + upd_max_cbs_in_slice(); +} + +/** Called by the scheduler() when switching to a newly scheduled thread. */ +void rcu_before_thread_runs(void) +{ + ASSERT(PREEMPTION_DISABLED || interrupts_disabled()); + ASSERT(!rcu_read_locked()); + + /* Load the thread's saved nesting count from before it was preempted. */ + THE->rcu_nesting = THREAD->rcu.nesting_cnt; +} + +/** Called from scheduler() when exiting the current thread. + * + * Preemption or interrupts are disabled and the scheduler() already + * switched away from the current thread, calling rcu_after_thread_ran(). + */ +void rcu_thread_exiting(void) +{ + ASSERT(PREEMPTION_DISABLED || interrupts_disabled()); + /* + * The thread forgot to exit its reader critical section. + * It is a bug, but rather than letting the entire system lock up + * forcefully leave the reader section. The thread is not holding + * any references anyway since it is exiting so it is safe. + */ + if (RCU_CNT_INC <= THREAD->rcu.nesting_cnt) { + /* Emulate _rcu_preempted_unlock() with the proper nesting count. */ + if (THREAD->rcu.nesting_cnt & RCU_WAS_PREEMPTED) { + ipl_t ipl = interrupts_disable(); + rm_preempted_reader(); + interrupts_restore(ipl); + } + } +} + +/** Returns true if in an rcu reader section. */ +bool rcu_read_locked(void) +{ + return RCU_CNT_INC <= THE->rcu_nesting; +} + +/** Invoked when a preempted reader finally exits its reader section. */ +void _rcu_preempted_unlock(void) +{ + ipl_t ipl = interrupts_disable(); + + if (THE->rcu_nesting == RCU_WAS_PREEMPTED) { + THE->rcu_nesting = 0; + rm_preempted_reader(); + } + + interrupts_restore(ipl); +} + +#elif defined(RCU_PREEMPT_PODZIMEK) /** Waits for the grace period associated with callbacks cub_cbs to elapse. @@ -897,27 +1121,4 @@ } -static void upd_missed_gp_in_wait(rcu_gp_t completed_gp) -{ - ASSERT(CPU->rcu.cur_cbs_gp <= completed_gp); - - size_t delta = (size_t)(completed_gp - CPU->rcu.cur_cbs_gp); - CPU->rcu.stat_missed_gp_in_wait += delta; -} - - -/** Requests the detector to detect at least req_cnt consecutive grace periods.*/ -static void req_detection(size_t req_cnt) -{ - if (rcu.req_gp_end_cnt < req_cnt) { - bool detector_idle = (0 == rcu.req_gp_end_cnt); - rcu.req_gp_end_cnt = req_cnt; - - if (detector_idle) { - ASSERT(_rcu_cur_gp == rcu.completed_gp); - condvar_signal(&rcu.req_gp_changed); - } - } -} - /** Waits for an announcement of the end of the grace period wait_on_gp. */ static bool cv_wait_for_gp(rcu_gp_t wait_on_gp) @@ -938,4 +1139,19 @@ return interrupted; } + +/** Requests the detector to detect at least req_cnt consecutive grace periods.*/ +static void req_detection(size_t req_cnt) +{ + if (rcu.req_gp_end_cnt < req_cnt) { + bool detector_idle = (0 == rcu.req_gp_end_cnt); + rcu.req_gp_end_cnt = req_cnt; + + if (detector_idle) { + ASSERT(_rcu_cur_gp == rcu.completed_gp); + condvar_signal(&rcu.req_gp_changed); + } + } +} + /** The detector thread detects and notifies reclaimers of grace period ends. */ @@ -985,4 +1201,261 @@ } + +static void end_cur_gp(void) +{ + ASSERT(spinlock_locked(&rcu.gp_lock)); + + rcu.completed_gp = _rcu_cur_gp; + --rcu.req_gp_end_cnt; + + condvar_broadcast(&rcu.gp_ended); +} + +/** Waits for readers that started before the current GP started to finish. */ +static bool wait_for_readers(void) +{ + DEFINE_CPU_MASK(reading_cpus); + + /* All running cpus have potential readers. */ + cpu_mask_active(reading_cpus); + + /* + * Give readers time to pass through a QS. Also, batch arriving + * callbacks in order to amortize detection overhead. + */ + if (!gp_sleep()) + return false; + + /* Non-intrusively determine which cpus have yet to pass a QS. */ + rm_quiescent_cpus(reading_cpus); + + /* Actively interrupt cpus delaying the current GP and demand a QS. */ + interrupt_delaying_cpus(reading_cpus); + + /* Wait for the interrupted cpus to notify us that they reached a QS. */ + if (!wait_for_delaying_cpus()) + return false; + /* + * All cpus recorded a QS or are still idle. Any new readers will be added + * to next_preempt if preempted, ie the number of readers in cur_preempted + * monotonically descreases. + */ + + /* Wait for the last reader in cur_preempted to notify us it is done. */ + if (!wait_for_preempt_reader()) + return false; + + return true; +} + +/** Sleeps a while if the current grace period is not to be expedited. */ +static bool gp_sleep(void) +{ + spinlock_lock(&rcu.gp_lock); + + int ret = 0; + while (0 == rcu.req_expedited_cnt && 0 == ret) { + /* minor bug: sleeps for the same duration if woken up spuriously. */ + ret = _condvar_wait_timeout_spinlock(&rcu.expedite_now, &rcu.gp_lock, + DETECT_SLEEP_MS * 1000, SYNCH_FLAGS_INTERRUPTIBLE); + } + + if (0 < rcu.req_expedited_cnt) { + --rcu.req_expedited_cnt; + /* Update statistic. */ + ++rcu.stat_expedited_cnt; + } + + spinlock_unlock(&rcu.gp_lock); + + return (ret != ESYNCH_INTERRUPTED); +} + +/** Actively interrupts and checks the offending cpus for quiescent states. */ +static void interrupt_delaying_cpus(cpu_mask_t *cpu_mask) +{ + atomic_set(&rcu.delaying_cpu_cnt, 0); + + sample_cpus(cpu_mask, 0); +} + +/** Invoked on a cpu delaying grace period detection. + * + * Induces a quiescent state for the cpu or it instructs remaining + * readers to notify the detector once they finish. + */ +static void sample_local_cpu(void *arg) +{ + ASSERT(interrupts_disabled()); + ASSERT(!CPU->rcu.is_delaying_gp); + + /* Cpu did not pass a quiescent state yet. */ + if (CPU->rcu.last_seen_gp != _rcu_cur_gp) { + /* Interrupted a reader in a reader critical section. */ + if (0 < CPU->rcu.nesting_cnt) { + ASSERT(!CPU->idle); + /* Note to notify the detector from rcu_read_unlock(). */ + CPU->rcu.is_delaying_gp = true; + /* + * Set signal_unlock only after setting is_delaying_gp so + * that NMI handlers do not accidentally clear it in unlock() + * before seeing and acting upon is_delaying_gp. + */ + compiler_barrier(); + CPU->rcu.signal_unlock = true; + + atomic_inc(&rcu.delaying_cpu_cnt); + } else { + /* + * The cpu did not enter any rcu reader sections since + * the start of the current GP. Record a quiescent state. + * + * Or, we interrupted rcu_read_unlock_impl() right before + * it recorded a QS. Record a QS for it. The memory barrier + * contains the reader section's mem accesses before + * updating last_seen_gp. + * + * Or, we interrupted rcu_read_lock() right after it recorded + * a QS for the previous GP but before it got a chance to + * increment its nesting count. The memory barrier again + * stops the CS code from spilling out of the CS. + */ + memory_barrier(); + CPU->rcu.last_seen_gp = _rcu_cur_gp; + } + } else { + /* + * This cpu already acknowledged that it had passed through + * a quiescent state since the start of cur_gp. + */ + } + + /* + * smp_call() makes sure any changes propagate back to the caller. + * In particular, it makes the most current last_seen_gp visible + * to the detector. + */ +} + +/** Waits for cpus delaying the current grace period if there are any. */ +static bool wait_for_delaying_cpus(void) +{ + int delaying_cpu_cnt = atomic_get(&rcu.delaying_cpu_cnt); + + for (int i = 0; i < delaying_cpu_cnt; ++i){ + if (!semaphore_down_interruptable(&rcu.remaining_readers)) + return false; + } + + /* Update statistic. */ + rcu.stat_delayed_cnt += delaying_cpu_cnt; + + return true; +} + +/** Called by the scheduler() when switching away from the current thread. */ +void rcu_after_thread_ran(void) +{ + ASSERT(interrupts_disabled()); + /* todo: make is_delaying_gp and was_preempted NMI safe via local atomics.*/ + + /* + * Prevent NMI handlers from interfering. The detector will be notified + * here if CPU->rcu.is_delaying_gp and the current thread is no longer + * running so there is nothing to signal to the detector. + */ + CPU->rcu.signal_unlock = false; + /* Separates clearing of .signal_unlock from CPU->rcu.nesting_cnt = 0. */ + compiler_barrier(); + + /* Save the thread's nesting count when it is not running. */ + THREAD->rcu.nesting_cnt = CPU->rcu.nesting_cnt; + /* Interrupt handlers might use RCU while idle in scheduler(). */ + CPU->rcu.nesting_cnt = 0; + + /* Preempted a reader critical section for the first time. */ + if (0 < THREAD->rcu.nesting_cnt && !THREAD->rcu.was_preempted) { + THREAD->rcu.was_preempted = true; + note_preempted_reader(); + } + + /* + * The preempted reader has been noted globally. There are therefore + * no readers running on this cpu so this is a quiescent state. + */ + _rcu_record_qs(); + + /* + * This cpu is holding up the current GP. Let the detector know + * it has just passed a quiescent state. + * + * The detector waits separately for preempted readers, so we have + * to notify the detector even if we have just preempted a reader. + */ + if (CPU->rcu.is_delaying_gp) { + CPU->rcu.is_delaying_gp = false; + semaphore_up(&rcu.remaining_readers); + } + + /* + * Forcefully associate the detector with the highest priority + * even if preempted due to its time slice running out. + * + * todo: Replace with strict scheduler priority classes. + */ + if (THREAD == rcu.detector_thr) { + THREAD->priority = -1; + } + else if (THREAD == CPU->rcu.reclaimer_thr) { + THREAD->priority = -1; + } + + upd_max_cbs_in_slice(); +} + +/** Called by the scheduler() when switching to a newly scheduled thread. */ +void rcu_before_thread_runs(void) +{ + ASSERT(PREEMPTION_DISABLED || interrupts_disabled()); + ASSERT(0 == CPU->rcu.nesting_cnt); + + /* Load the thread's saved nesting count from before it was preempted. */ + CPU->rcu.nesting_cnt = THREAD->rcu.nesting_cnt; + /* + * In the unlikely event that a NMI occurs between the loading of the + * variables and setting signal_unlock, the NMI handler may invoke + * rcu_read_unlock() and clear signal_unlock. In that case we will + * incorrectly overwrite signal_unlock from false to true. This event + * situation benign and the next rcu_read_unlock() will at worst + * needlessly invoke _rcu_signal_unlock(). + */ + CPU->rcu.signal_unlock = THREAD->rcu.was_preempted || CPU->rcu.is_delaying_gp; +} + +/** Called from scheduler() when exiting the current thread. + * + * Preemption or interrupts are disabled and the scheduler() already + * switched away from the current thread, calling rcu_after_thread_ran(). + */ +void rcu_thread_exiting(void) +{ + ASSERT(THREAD != 0); + ASSERT(THREAD->state == Exiting); + ASSERT(PREEMPTION_DISABLED || interrupts_disabled()); + /* + * The thread forgot to exit its reader critical section. + * It is a bug, but rather than letting the entire system lock up + * forcefully leave the reader section. The thread is not holding + * any references anyway since it is exiting so it is safe. + */ + if (0 < THREAD->rcu.nesting_cnt) { + THREAD->rcu.nesting_cnt = 1; + read_unlock_impl(&THREAD->rcu.nesting_cnt); + } +} + + +#endif /* RCU_PREEMPT_PODZIMEK */ + /** Announces the start of a new grace period for preexisting readers to ack. */ static void start_new_gp(void) @@ -1008,22 +1481,9 @@ } -static void end_cur_gp(void) -{ - ASSERT(spinlock_locked(&rcu.gp_lock)); - - rcu.completed_gp = _rcu_cur_gp; - --rcu.req_gp_end_cnt; - - condvar_broadcast(&rcu.gp_ended); -} - -/** Waits for readers that started before the current GP started to finish. */ -static bool wait_for_readers(void) -{ - DEFINE_CPU_MASK(reading_cpus); - - /* All running cpus have potential readers. */ - cpu_mask_active(reading_cpus); - +/** Remove those cpus from the mask that have already passed a quiescent + * state since the start of the current grace period. + */ +static void rm_quiescent_cpus(cpu_mask_t *cpu_mask) +{ /* * Ensure the announcement of the start of a new GP (ie up-to-date @@ -1080,38 +1540,4 @@ memory_barrier(); /* MB C */ - /* - * Give readers time to pass through a QS. Also, batch arriving - * callbacks in order to amortize detection overhead. - */ - if (!gp_sleep()) - return false; - - /* Non-intrusively determine which cpus have yet to pass a QS. */ - rm_quiescent_cpus(reading_cpus); - - /* Actively interrupt cpus delaying the current GP and demand a QS. */ - interrupt_delaying_cpus(reading_cpus); - - /* Wait for the interrupted cpus to notify us that they reached a QS. */ - if (!wait_for_delaying_cpus()) - return false; - /* - * All cpus recorded a QS or are still idle. Any new readers will be added - * to next_preempt if preempted, ie the number of readers in cur_preempted - * monotonically descreases. - */ - - /* Wait for the last reader in cur_preempted to notify us it is done. */ - if (!wait_for_preempt_reader()) - return false; - - return true; -} - -/** Remove those cpus from the mask that have already passed a quiescent - * state since the start of the current grace period. - */ -static void rm_quiescent_cpus(cpu_mask_t *cpu_mask) -{ cpu_mask_for_each(*cpu_mask, cpu_id) { /* @@ -1137,29 +1563,6 @@ } -/** Sleeps a while if the current grace period is not to be expedited. */ -static bool gp_sleep(void) -{ - spinlock_lock(&rcu.gp_lock); - - int ret = 0; - while (0 == rcu.req_expedited_cnt && 0 == ret) { - /* minor bug: sleeps for the same duration if woken up spuriously. */ - ret = _condvar_wait_timeout_spinlock(&rcu.expedite_now, &rcu.gp_lock, - DETECT_SLEEP_MS * 1000, SYNCH_FLAGS_INTERRUPTIBLE); - } - - if (0 < rcu.req_expedited_cnt) { - --rcu.req_expedited_cnt; - /* Update statistic. */ - ++rcu.stat_expedited_cnt; - } - - spinlock_unlock(&rcu.gp_lock); - - return (ret != ESYNCH_INTERRUPTED); -} - -/** Actively interrupts and checks the offending cpus for quiescent states. */ -static void interrupt_delaying_cpus(cpu_mask_t *cpu_mask) +/** Invokes sample_local_cpu(arg) on each cpu of reader_cpus. */ +static void sample_cpus(cpu_mask_t *reader_cpus, void *arg) { const size_t max_conconcurrent_calls = 16; @@ -1167,8 +1570,6 @@ size_t outstanding_calls = 0; - atomic_set(&rcu.delaying_cpu_cnt, 0); - - cpu_mask_for_each(*cpu_mask, cpu_id) { - smp_call_async(cpu_id, sample_local_cpu, 0, &call[outstanding_calls]); + cpu_mask_for_each(*reader_cpus, cpu_id) { + smp_call_async(cpu_id, sample_local_cpu, arg, &call[outstanding_calls]); ++outstanding_calls; @@ -1191,76 +1592,55 @@ } -/** Invoked on a cpu delaying grace period detection. - * - * Induces a quiescent state for the cpu or it instructs remaining - * readers to notify the detector once they finish. - */ -static void sample_local_cpu(void *arg) -{ - ASSERT(interrupts_disabled()); - ASSERT(!CPU->rcu.is_delaying_gp); - - /* Cpu did not pass a quiescent state yet. */ +static void upd_missed_gp_in_wait(rcu_gp_t completed_gp) +{ + ASSERT(CPU->rcu.cur_cbs_gp <= completed_gp); + + size_t delta = (size_t)(completed_gp - CPU->rcu.cur_cbs_gp); + CPU->rcu.stat_missed_gp_in_wait += delta; +} + +/** Globally note that the current thread was preempted in a reader section. */ +static void note_preempted_reader(void) +{ + irq_spinlock_lock(&rcu.preempt_lock, false); + if (CPU->rcu.last_seen_gp != _rcu_cur_gp) { - /* Interrupted a reader in a reader critical section. */ - if (0 < CPU->rcu.nesting_cnt) { - ASSERT(!CPU->idle); - /* Note to notify the detector from rcu_read_unlock(). */ - CPU->rcu.is_delaying_gp = true; - /* - * Set signal_unlock only after setting is_delaying_gp so - * that NMI handlers do not accidentally clear it in unlock() - * before seeing and acting upon is_delaying_gp. - */ - compiler_barrier(); - CPU->rcu.signal_unlock = true; - - atomic_inc(&rcu.delaying_cpu_cnt); - } else { - /* - * The cpu did not enter any rcu reader sections since - * the start of the current GP. Record a quiescent state. - * - * Or, we interrupted rcu_read_unlock_impl() right before - * it recorded a QS. Record a QS for it. The memory barrier - * contains the reader section's mem accesses before - * updating last_seen_gp. - * - * Or, we interrupted rcu_read_lock() right after it recorded - * a QS for the previous GP but before it got a chance to - * increment its nesting count. The memory barrier again - * stops the CS code from spilling out of the CS. - */ - memory_barrier(); - CPU->rcu.last_seen_gp = _rcu_cur_gp; - } + /* The reader started before the GP started - we must wait for it.*/ + list_append(&THREAD->rcu.preempt_link, &rcu.cur_preempted); } else { /* - * This cpu already acknowledged that it had passed through - * a quiescent state since the start of cur_gp. + * The reader started after the GP started and this cpu + * already noted a quiescent state. We might block the next GP. */ - } - - /* - * smp_call() makes sure any changes propagate back to the caller. - * In particular, it makes the most current last_seen_gp visible - * to the detector. - */ -} - -/** Waits for cpus delaying the current grace period if there are any. */ -static bool wait_for_delaying_cpus(void) -{ - int delaying_cpu_cnt = atomic_get(&rcu.delaying_cpu_cnt); - - for (int i = 0; i < delaying_cpu_cnt; ++i){ - if (!semaphore_down_interruptable(&rcu.remaining_readers)) - return false; - } - - /* Update statistic. */ - rcu.stat_delayed_cnt += delaying_cpu_cnt; - - return true; + list_append(&THREAD->rcu.preempt_link, &rcu.next_preempted); + } + + irq_spinlock_unlock(&rcu.preempt_lock, false); +} + +/** Remove the current thread from the global list of preempted readers. */ +static void rm_preempted_reader(void) +{ + irq_spinlock_lock(&rcu.preempt_lock, false); + + ASSERT(link_used(&THREAD->rcu.preempt_link)); + + bool prev_empty = list_empty(&rcu.cur_preempted); + list_remove(&THREAD->rcu.preempt_link); + bool now_empty = list_empty(&rcu.cur_preempted); + + /* This was the last reader in cur_preempted. */ + bool last_removed = now_empty && !prev_empty; + + /* + * Preempted readers are blocking the detector and + * this was the last reader blocking the current GP. + */ + if (last_removed && rcu.preempt_blocking_det) { + rcu.preempt_blocking_det = false; + semaphore_up(&rcu.remaining_readers); + } + + irq_spinlock_unlock(&rcu.preempt_lock, false); } @@ -1285,79 +1665,4 @@ } -/** Called by the scheduler() when switching away from the current thread. */ -void rcu_after_thread_ran(void) -{ - ASSERT(interrupts_disabled()); - /* todo: make is_delaying_gp and was_preempted NMI safe via local atomics.*/ - - /* - * Prevent NMI handlers from interfering. The detector will be notified - * here if CPU->rcu.is_delaying_gp and the current thread is no longer - * running so there is nothing to signal to the detector. - */ - CPU->rcu.signal_unlock = false; - /* Separates clearing of .signal_unlock from CPU->rcu.nesting_cnt = 0. */ - compiler_barrier(); - - /* Save the thread's nesting count when it is not running. */ - THREAD->rcu.nesting_cnt = CPU->rcu.nesting_cnt; - /* Interrupt handlers might use RCU while idle in scheduler(). */ - CPU->rcu.nesting_cnt = 0; - - /* Preempted a reader critical section for the first time. */ - if (0 < THREAD->rcu.nesting_cnt && !THREAD->rcu.was_preempted) { - THREAD->rcu.was_preempted = true; - - irq_spinlock_lock(&rcu.preempt_lock, false); - - if (CPU->rcu.last_seen_gp != _rcu_cur_gp) { - /* The reader started before the GP started - we must wait for it.*/ - list_append(&THREAD->rcu.preempt_link, &rcu.cur_preempted); - } else { - /* - * The reader started after the GP started and this cpu - * already noted a quiescent state. We might block the next GP. - */ - list_append(&THREAD->rcu.preempt_link, &rcu.next_preempted); - } - - irq_spinlock_unlock(&rcu.preempt_lock, false); - } - - - /* - * The preempted reader has been noted globally. There are therefore - * no readers running on this cpu so this is a quiescent state. - */ - _rcu_record_qs(); - - /* - * This cpu is holding up the current GP. Let the detector know - * it has just passed a quiescent state. - * - * The detector waits separately for preempted readers, so we have - * to notify the detector even if we have just preempted a reader. - */ - if (CPU->rcu.is_delaying_gp) { - CPU->rcu.is_delaying_gp = false; - semaphore_up(&rcu.remaining_readers); - } - - /* - * Forcefully associate the detector with the highest priority - * even if preempted due to its time slice running out. - * - * todo: Replace with strict scheduler priority classes. - */ - if (THREAD == rcu.detector_thr) { - THREAD->priority = -1; - } - else if (THREAD == CPU->rcu.reclaimer_thr) { - THREAD->priority = -1; - } - - upd_max_cbs_in_slice(); -} - static void upd_max_cbs_in_slice(void) { @@ -1372,24 +1677,4 @@ } -/** Called by the scheduler() when switching to a newly scheduled thread. */ -void rcu_before_thread_runs(void) -{ - ASSERT(PREEMPTION_DISABLED || interrupts_disabled()); - ASSERT(0 == CPU->rcu.nesting_cnt); - - /* Load the thread's saved nesting count from before it was preempted. */ - CPU->rcu.nesting_cnt = THREAD->rcu.nesting_cnt; - /* - * In the unlikely event that a NMI occurs between the loading of the - * variables and setting signal_unlock, the NMI handler may invoke - * rcu_read_unlock() and clear signal_unlock. In that case we will - * incorrectly overwrite signal_unlock from false to true. This event - * situation benign and the next rcu_read_unlock() will at worst - * needlessly invoke _rcu_signal_unlock(). - */ - CPU->rcu.signal_unlock = THREAD->rcu.was_preempted || CPU->rcu.is_delaying_gp; -} - - /** Prints RCU run-time statistics. */ void rcu_print_stat(void) @@ -1401,7 +1686,13 @@ */ - printf("Configuration: expedite_threshold=%d, critical_threshold=%d," - " detect_sleep=%dms\n", - EXPEDITE_THRESHOLD, CRITICAL_THRESHOLD, DETECT_SLEEP_MS); +#ifdef RCU_PREEMPT_PODZIMEK + const char *algo = "podzimek-preempt-rcu"; +#elif defined(RCU_PREEMPT_A) + const char *algo = "a-preempt-rcu"; +#endif + + printf("Config: expedite_threshold=%d, critical_threshold=%d," + " detect_sleep=%dms, %s\n", + EXPEDITE_THRESHOLD, CRITICAL_THRESHOLD, DETECT_SLEEP_MS, algo); printf("Completed GPs: %" PRIu64 "\n", rcu.completed_gp); printf("Expedited GPs: %zu\n", rcu.stat_expedited_cnt);