Context Navigation

-              rf0fcb04
+              rd4d36f9
         /** 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
 …
         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.
 …
          */
         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. */
 …
 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);
 …
 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);
 …
+{
         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;
 …
         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;
 …
                 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;
 …
         CPU->rcu.next_cbs_gp = 0;
-        CPU->rcu.is_delaying_gp = false;
-        CPU->rcu.signal_unlock = false;
         semaphore_initialize(&CPU->rcu.arrived_flag, 0);
 …
 void rcu_kinit_init(void)
+{
+#ifdef RCU_PREEMPT_PODZIMEK
         start_detector();
+#endif
         start_reclaimers();
+}
 …
+{
         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.
 …
+        }
+#ifdef RCU_PREEMPT_PODZIMEK
         /* Stop the detector and wait. */
         if (rcu.detector_thr) {
 …
                 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
+}
 …
         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);
+}
 …
                 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();
+        }
 …
         interrupts_restore(ipl);
+}
+#endif /* RCU_PREEMPT_PODZIMEK */
 typedef struct synch_item {
 …
+{
         /* Calling from a reader section will deadlock. */
         ASSERT(0 == CPU->rcu.nesting_cnt);
+        ASSERT(!rcu_read_locked());
         synch_item_t completion;
 …
         return cur_cbs_empty() && next_cbs_empty() && arriving_cbs_empty();
+}
 /** Reclaimer thread dispatches locally queued callbacks once a GP ends. */
 …
+}
 /** Prepares another batch of callbacks to dispatch at the nest grace period.
+ *
 …
         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.
 …
+}
-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)
 …
         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. */
 …
+}
+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)
 …
+}
+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
 …
         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) {
                 /*
 …
+}
+/** 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;
 …
         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;
 …
+}
+/** 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);
+}
 …
+}
-/** 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)
+{
 …
+}
-/** 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)
 …
          */
+        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);

Note: See TracChangeset for help on using the changeset viewer.

Context Navigation

Changeset d4d36f9 in mainline for kernel/generic/src/synch/rcu.c

Legend:

kernel/generic/src/synch/rcu.c

Download in other formats: