rcu: Implement RCU
authorBarret Rhoden <brho@cs.berkeley.edu>
Thu, 26 Apr 2018 19:57:09 +0000 (15:57 -0400)
committerBarret Rhoden <brho@cs.berkeley.edu>
Mon, 30 Apr 2018 18:41:01 +0000 (14:41 -0400)
Our RCU is similar to Linux's rcu_sched - we don't do the same things they
do with CONFIG_PREEMPT.

A lot of the changes to the Linux headers were me removing things I'm
fairly sure we won't need, so don't worry about that.  The bulk of this
commit is rcu.c, which implements call_rcu() and rcu_barrier() - which is
the heart of any RCU implementation.

Though note the locations in the rest of the kernel where we call
rcu_report_qs() - those are the locations where we know we aren't in a
read-side critical section.

The big difference between our RCU and Linux's implementation is that we do
not interfere with the CG cores.  We do not use softirq processing or timer
ticks for either callbacks or reporting quiescent states.

call_rcu() callbacks from CG cores do not run on the cores where they were
queued up.  There is a penalty for cache misses for this, but it prevents
us from interfering with the app.  Otherwise, once a grace period elapses,
we'd either have to wait for the user to enter the kernel or we'd have to
force them to.  You could imagine a middle ground where we let a callback
sit for a while or try to work-steal it.

We can check from a management core (core 0) to see if a CG core is in
userspace or idle.  This is similar to what Linux does with dynticks, I
think.  We also expedite the grace periods, though we can change that.

We use Linux's tree structure for tracking quiescent states, but all cores
use the global gpnum to find out which gpnum we're dealing with.  If that
turns out to be a scalability problem, then we can deal with it later.  I
didn't want to deal with certain cores having old gps.

As far as the timing parameters, I went with 25 msec since it wasn't a
multiple of the kernel scheduler tick.  If it is having an effect on FTQ
numbers, being at another frequency will make it stand out.

This hasn't been tested heavily; there are mostly likely bugs and almost
surely memory barrier problems that might require another architectures.

Signed-off-by: Barret Rhoden <brho@cs.berkeley.edu>
14 files changed:
kern/include/linux_compat.h
kern/include/rbtree.h
kern/include/rcu.h
kern/include/rcu_helper.h
kern/include/rculist.h
kern/include/rcupdate.h
kern/src/Kbuild
kern/src/init.c
kern/src/process.c
kern/src/rcu.c [new file with mode: 0644]
kern/src/rcu_tree_helper.c
kern/src/smp.c
kern/src/syscall.c
kern/src/trap.c

index 781915c..d4ca975 100644 (file)
 //#define CONFIG_INET 1        // will deal with this manually
 #define CONFIG_PCI_MSI 1
 
-#define __rcu
-#define rcu_read_lock()
-#define rcu_read_unlock()
-#define rcu_dereference(x) (x)
-#define rcu_dereference_protected(x, y) (x)
-#ifndef rcu_assign_pointer
-#define rcu_assign_pointer(dst, src) (dst) = (src)
-#endif
-#define RCU_INIT_POINTER(dst, src) rcu_assign_pointer(dst, src)
-#define synchronize_rcu()
-#define synchronize_sched()
+static inline void synchronize_sched(void)
+{
+       synchronize_rcu();
+}
 
 #define atomic_cmpxchg(_addr, _old, _new)                                      \
 ({                                                                             \
index 1e1a512..4d50e62 100644 (file)
 
 #pragma once
 
-/* TODO: eventually we'll support some form of RCU and concurrent rb-tree
- * usage.  When we do that, we'll need to grab these functions from Linux. */
-#ifndef rcu_assign_pointer
-#define rcu_assign_pointer(d, s) (d) = (s)
-#endif
+#include <rcu.h>
 
 struct rb_node {
        unsigned long  __rb_parent_color;
index cbd7c8b..578a303 100644 (file)
@@ -2,35 +2,92 @@
  * Barret Rhoden <brho@cs.berkeley.edu>
  * See LICENSE for details.
  *
- * Junk, racy implementation of RCU
+ * RCU.  See rcu.c for notes.
  */
 
 #pragma once
 
-#include <trap.h>
+#include <arch/membar.h>
+#include <arch/topology.h>
+#include <percpu.h>
+#include <list.h>
+
+struct rcu_head;
+typedef void (*rcu_callback_t)(struct rcu_head *head);
+typedef void (*call_rcu_func_t)(struct rcu_head *head, rcu_callback_t func);
 
 struct rcu_head {
+       struct list_head                        link;
+       rcu_callback_t                          func;
+       unsigned long                           gpnum;
+};
+
+#include <rcupdate.h>
+
+/* This is a little nasty.  We can't undef it, since NUM_RCU_NODES is used in a
+ * few places.  We could get this from Kconfig, like Linux does. */
+#define NR_CPUS 4096
+
+#include <rcu_helper.h>
+#include <rculist.h>
+#include <rendez.h>
+
+struct rcu_node {
+       struct rcu_node                         *parent;
+       unsigned long                           qsmask; /* cores that need to check in */
+       unsigned long                           qsmaskinit;
+       unsigned int                            level;
+       unsigned int                            grplo;  /* lowest nr CPU here */
+       unsigned int                            grphi;  /* highest nr CPU here */
+       unsigned int                            grpnum; /* our number in our parent */
+       unsigned long                           grpmask;/* our bit in our parent */
 };
 
-static void __call_rcu_kmsg(uint32_t srcid, long a0, long a1, long a2)
-{
-       void (*f)(struct rcu_head *) = (void*)a0;
+struct rcu_state {
+       struct rcu_node                         node[NUM_RCU_NODES];
+       struct rcu_node                         *level[RCU_NUM_LVLS];
 
-       f((void*)a1);
-}
+       /* These are read by everyone but only written by the GP kthread */
+       unsigned long                           gpnum;
+       unsigned long                           completed;
+
+       /* These are written by anyone trying to wake the gp kthread, which can be
+        * any core whose CB list is long or does an rcu_barrier() */
+       /* TODO: make a ktask struct and use a read-only pointer. */
+       struct rendez                           gp_ktask_rv;
+       int                                                     gp_ktask_ctl;
+};
+
+struct rcu_pcpui {
+       struct rcu_state                        *rsp;
+       struct rcu_node                         *my_node;
+       int                                                     coreid;
+       unsigned int                            grpnum;
+       unsigned long                           grpmask;
+       bool                                            booted;
+
+       spinlock_t                                      lock;
+       struct list_head                        cbs;
+       unsigned int                            nr_cbs;
+       unsigned long                           gp_acked;
+
+       struct rendez                           mgmt_ktask_rv;
+       int                                                     mgmt_ktask_ctl;
+};
+DECLARE_PERCPU(struct rcu_pcpui, rcu_pcpui);
 
-static void call_rcu(struct rcu_head *head, void (*func)(struct rcu_head *head))
-{
-       send_kernel_message(core_id(), __call_rcu_kmsg, (long)func, (long)head, 0,
-                           KMSG_ROUTINE);
-}
+void rcu_init(void);
+void rcu_report_qs(void);
+void rcu_barrier(void);
+void rcu_force_quiescent_state(void);
+unsigned long get_state_synchronize_rcu(void);
+void cond_synchronize_rcu(unsigned long oldstate);
+void kfree_call_rcu(struct rcu_head *head, rcu_callback_t off);
 
-#define hlist_for_each_entry_rcu hlist_for_each_entry
-#define hlist_add_head_rcu hlist_add_head
-#define hlist_del_rcu hlist_del
+/* Internal Helpers (rcu.c) */
+void rcu_init_pcpui(struct rcu_state *rsp, struct rcu_pcpui *rpi, int coreid);
 
-#define rcu_read_lock()
-#define rcu_read_unlock()
-#define synchronize_rcu()
-#define rcu_dereference(x) (x)
-#define rcu_barrier() kthread_usleep(10000)
+/* Internal Helpers (rcu_tree_helper.c) */
+void rcu_init_one(struct rcu_state *rsp);
+void rcu_init_geometry(void);
+void rcu_dump_rcu_node_tree(struct rcu_state *rsp);
index 808b8c8..40f0cd0 100644 (file)
 #ifndef __LINUX_RCU_H
 #define __LINUX_RCU_H
 
-#include <trace/events/rcu.h>
-#ifdef CONFIG_RCU_TRACE
-#define RCU_TRACE(stmt) stmt
-#else /* #ifdef CONFIG_RCU_TRACE */
-#define RCU_TRACE(stmt)
-#endif /* #else #ifdef CONFIG_RCU_TRACE */
-
-/*
- * Process-level increment to ->dynticks_nesting field.  This allows for
- * architectures that use half-interrupts and half-exceptions from
- * process context.
- *
- * DYNTICK_TASK_NEST_MASK defines a field of width DYNTICK_TASK_NEST_WIDTH
- * that counts the number of process-based reasons why RCU cannot
- * consider the corresponding CPU to be idle, and DYNTICK_TASK_NEST_VALUE
- * is the value used to increment or decrement this field.
- *
- * The rest of the bits could in principle be used to count interrupts,
- * but this would mean that a negative-one value in the interrupt
- * field could incorrectly zero out the DYNTICK_TASK_NEST_MASK field.
- * We therefore provide a two-bit guard field defined by DYNTICK_TASK_MASK
- * that is set to DYNTICK_TASK_FLAG upon initial exit from idle.
- * The DYNTICK_TASK_EXIT_IDLE value is thus the combined value used upon
- * initial exit from idle.
- */
-#define DYNTICK_TASK_NEST_WIDTH 7
-#define DYNTICK_TASK_NEST_VALUE ((LLONG_MAX >> DYNTICK_TASK_NEST_WIDTH) + 1)
-#define DYNTICK_TASK_NEST_MASK  (LLONG_MAX - DYNTICK_TASK_NEST_VALUE + 1)
-#define DYNTICK_TASK_FLAG         ((DYNTICK_TASK_NEST_VALUE / 8) * 2)
-#define DYNTICK_TASK_MASK         ((DYNTICK_TASK_NEST_VALUE / 8) * 3)
-#define DYNTICK_TASK_EXIT_IDLE    (DYNTICK_TASK_NEST_VALUE + \
-                                   DYNTICK_TASK_FLAG)
-
-
 /*
  * Grace-period counter management.
  */
@@ -88,7 +54,7 @@ static inline int rcu_seq_state(unsigned long s)
  */
 static inline void rcu_seq_set_state(unsigned long *sp, int newstate)
 {
-       WARN_ON_ONCE(newstate & ~RCU_SEQ_STATE_MASK);
+       warn_on_once(newstate & ~RCU_SEQ_STATE_MASK);
        WRITE_ONCE(*sp, (*sp & ~RCU_SEQ_STATE_MASK) + newstate);
 }
 
@@ -96,15 +62,15 @@ static inline void rcu_seq_set_state(unsigned long *sp, int newstate)
 static inline void rcu_seq_start(unsigned long *sp)
 {
        WRITE_ONCE(*sp, *sp + 1);
-       smp_mb(); /* Ensure update-side operation after counter increment. */
-       WARN_ON_ONCE(rcu_seq_state(*sp) != 1);
+       mb(); /* Ensure update-side operation after counter increment. */
+       warn_on_once(rcu_seq_state(*sp) != 1);
 }
 
 /* Adjust sequence number for end of update-side operation. */
 static inline void rcu_seq_end(unsigned long *sp)
 {
-       smp_mb(); /* Ensure update-side operation before counter increment. */
-       WARN_ON_ONCE(!rcu_seq_state(*sp));
+       mb(); /* Ensure update-side operation before counter increment. */
+       warn_on_once(!rcu_seq_state(*sp));
        WRITE_ONCE(*sp, (*sp | RCU_SEQ_STATE_MASK) + 1);
 }
 
@@ -114,7 +80,7 @@ static inline unsigned long rcu_seq_snap(unsigned long *sp)
        unsigned long s;
 
        s = (READ_ONCE(*sp) + 2 * RCU_SEQ_STATE_MASK + 1) & ~RCU_SEQ_STATE_MASK;
-       smp_mb(); /* Above access must not bleed into critical section. */
+       mb(); /* Above access must not bleed into critical section. */
        return s;
 }
 
@@ -133,115 +99,14 @@ static inline bool rcu_seq_done(unsigned long *sp, unsigned long s)
        return ULONG_CMP_GE(READ_ONCE(*sp), s);
 }
 
-/*
- * debug_rcu_head_queue()/debug_rcu_head_unqueue() are used internally
- * by call_rcu() and rcu callback execution, and are therefore not part of the
- * RCU API. Leaving in rcupdate.h because they are used by all RCU flavors.
- */
-
-#ifdef CONFIG_DEBUG_OBJECTS_RCU_HEAD
-# define STATE_RCU_HEAD_READY  0
-# define STATE_RCU_HEAD_QUEUED 1
-
-extern struct debug_obj_descr rcuhead_debug_descr;
-
-static inline int debug_rcu_head_queue(struct rcu_head *head)
-{
-       int r1;
-
-       r1 = debug_object_activate(head, &rcuhead_debug_descr);
-       debug_object_active_state(head, &rcuhead_debug_descr,
-                                 STATE_RCU_HEAD_READY,
-                                 STATE_RCU_HEAD_QUEUED);
-       return r1;
-}
-
-static inline void debug_rcu_head_unqueue(struct rcu_head *head)
-{
-       debug_object_active_state(head, &rcuhead_debug_descr,
-                                 STATE_RCU_HEAD_QUEUED,
-                                 STATE_RCU_HEAD_READY);
-       debug_object_deactivate(head, &rcuhead_debug_descr);
-}
-#else  /* !CONFIG_DEBUG_OBJECTS_RCU_HEAD */
-static inline int debug_rcu_head_queue(struct rcu_head *head)
-{
-       return 0;
-}
-
-static inline void debug_rcu_head_unqueue(struct rcu_head *head)
-{
-}
-#endif /* #else !CONFIG_DEBUG_OBJECTS_RCU_HEAD */
-
-void kfree(const void *);
-
-/*
- * Reclaim the specified callback, either by invoking it (non-lazy case)
- * or freeing it directly (lazy case).  Return true if lazy, false otherwise.
- */
-static inline bool __rcu_reclaim(const char *rn, struct rcu_head *head)
-{
-       unsigned long offset = (unsigned long)head->func;
-
-       rcu_lock_acquire(&rcu_callback_map);
-       if (__is_kfree_rcu_offset(offset)) {
-               RCU_TRACE(trace_rcu_invoke_kfree_callback(rn, head, offset);)
-               kfree((void *)head - offset);
-               rcu_lock_release(&rcu_callback_map);
-               return true;
-       } else {
-               RCU_TRACE(trace_rcu_invoke_callback(rn, head);)
-               head->func(head);
-               rcu_lock_release(&rcu_callback_map);
-               return false;
-       }
-}
-
-#ifdef CONFIG_RCU_STALL_COMMON
-
-extern int rcu_cpu_stall_suppress;
-int rcu_jiffies_till_stall_check(void);
-
-#endif /* #ifdef CONFIG_RCU_STALL_COMMON */
-
-/*
- * Strings used in tracepoints need to be exported via the
- * tracing system such that tools like perf and trace-cmd can
- * translate the string address pointers to actual text.
- */
-#define TPS(x)  tracepoint_string(x)
-
-/*
- * Dump the ftrace buffer, but only one time per callsite per boot.
- */
-#define rcu_ftrace_dump(oops_dump_mode) \
-do { \
-       static atomic_t ___rfd_beenhere = ATOMIC_INIT(0); \
-       \
-       if (!atomic_read(&___rfd_beenhere) && \
-           !atomic_xchg(&___rfd_beenhere, 1)) \
-               ftrace_dump(oops_dump_mode); \
-} while (0)
-
-void rcu_early_boot_tests(void);
-void rcu_test_sync_prims(void);
-
-/*
- * This function really isn't for public consumption, but RCU is special in
- * that context switches can allow the state machine to make progress.
- */
-extern void resched_cpu(int cpu);
-
-#if defined(SRCU) || !defined(TINY_RCU)
-
-#include <linux/rcu_node_tree.h>
+#include <rcu_node_tree.h>
 
 extern int rcu_num_lvls;
 extern int num_rcu_lvl[];
 extern int rcu_num_nodes;
-static bool rcu_fanout_exact;
-static int rcu_fanout_leaf;
+extern bool rcu_fanout_exact;
+extern int rcu_fanout_leaf;
+extern int rcu_num_cores;
 
 /*
  * Compute the per-level fanout, either using the exact fanout specified
@@ -259,7 +124,7 @@ static inline void rcu_init_levelspread(int *levelspread, const int *levelcnt)
                int ccur;
                int cprv;
 
-               cprv = nr_cpu_ids;
+               cprv = rcu_num_cores;
                for (i = rcu_num_lvls - 1; i >= 0; i--) {
                        ccur = levelcnt[i];
                        levelspread[i] = (cprv + ccur - 1) / ccur;
@@ -352,44 +217,10 @@ do {                                                                      \
        ___locked;                                                      \
 })
 
-#endif /* #if defined(SRCU) || !defined(TINY_RCU) */
-
-#ifdef CONFIG_TINY_RCU
-/* Tiny RCU doesn't expedite, as its purpose in life is instead to be tiny. */
-static inline bool rcu_gp_is_normal(void)  /* Internal RCU use. */
-{
-       return true;
-}
-static inline bool rcu_gp_is_expedited(void)  /* Internal RCU use. */
-{
-       return false;
-}
-
-static inline void rcu_expedite_gp(void)
-{
-}
-
-static inline void rcu_unexpedite_gp(void)
-{
-}
-#else /* #ifdef CONFIG_TINY_RCU */
-bool rcu_gp_is_normal(void);     /* Internal RCU use. */
-bool rcu_gp_is_expedited(void);  /* Internal RCU use. */
-void rcu_expedite_gp(void);
-void rcu_unexpedite_gp(void);
-void rcupdate_announce_bootup_oddness(void);
-#endif /* #else #ifdef CONFIG_TINY_RCU */
-
 #define RCU_SCHEDULER_INACTIVE 0
 #define RCU_SCHEDULER_INIT     1
 #define RCU_SCHEDULER_RUNNING  2
 
-#ifdef CONFIG_TINY_RCU
-static inline void rcu_request_urgent_qs_task(struct task_struct *t) { }
-#else /* #ifdef CONFIG_TINY_RCU */
-void rcu_request_urgent_qs_task(struct task_struct *t);
-#endif /* #else #ifdef CONFIG_TINY_RCU */
-
 enum rcutorture_type {
        RCU_FLAVOR,
        RCU_BH_FLAVOR,
@@ -399,7 +230,6 @@ enum rcutorture_type {
        INVALID_RCU_FLAVOR
 };
 
-#if defined(CONFIG_TREE_RCU) || defined(CONFIG_PREEMPT_RCU)
 void rcutorture_get_gp_data(enum rcutorture_type test_type, int *flags,
                            unsigned long *gpnum, unsigned long *completed);
 void rcutorture_record_test_transition(void);
@@ -409,165 +239,5 @@ void do_trace_rcu_torture_read(const char *rcutorturename,
                               unsigned long secs,
                               unsigned long c_old,
                               unsigned long c);
-#else
-static inline void rcutorture_get_gp_data(enum rcutorture_type test_type,
-                                         int *flags,
-                                         unsigned long *gpnum,
-                                         unsigned long *completed)
-{
-       *flags = 0;
-       *gpnum = 0;
-       *completed = 0;
-}
-static inline void rcutorture_record_test_transition(void)
-{
-}
-static inline void rcutorture_record_progress(unsigned long vernum)
-{
-}
-#ifdef CONFIG_RCU_TRACE
-void do_trace_rcu_torture_read(const char *rcutorturename,
-                              struct rcu_head *rhp,
-                              unsigned long secs,
-                              unsigned long c_old,
-                              unsigned long c);
-#else
-#define do_trace_rcu_torture_read(rcutorturename, rhp, secs, c_old, c) \
-       do { } while (0)
-#endif
-#endif
-
-#ifdef CONFIG_TINY_SRCU
-
-static inline void srcutorture_get_gp_data(enum rcutorture_type test_type,
-                                          struct srcu_struct *sp, int *flags,
-                                          unsigned long *gpnum,
-                                          unsigned long *completed)
-{
-       if (test_type != SRCU_FLAVOR)
-               return;
-       *flags = 0;
-       *completed = sp->srcu_idx;
-       *gpnum = *completed;
-}
-
-#elif defined(CONFIG_TREE_SRCU)
-
-void srcutorture_get_gp_data(enum rcutorture_type test_type,
-                            struct srcu_struct *sp, int *flags,
-                            unsigned long *gpnum, unsigned long *completed);
-
-#endif
-
-#ifdef CONFIG_TINY_RCU
-
-/*
- * Return the number of grace periods started.
- */
-static inline unsigned long rcu_batches_started(void)
-{
-       return 0;
-}
-
-/*
- * Return the number of bottom-half grace periods started.
- */
-static inline unsigned long rcu_batches_started_bh(void)
-{
-       return 0;
-}
-
-/*
- * Return the number of sched grace periods started.
- */
-static inline unsigned long rcu_batches_started_sched(void)
-{
-       return 0;
-}
-
-/*
- * Return the number of grace periods completed.
- */
-static inline unsigned long rcu_batches_completed(void)
-{
-       return 0;
-}
-
-/*
- * Return the number of bottom-half grace periods completed.
- */
-static inline unsigned long rcu_batches_completed_bh(void)
-{
-       return 0;
-}
-
-/*
- * Return the number of sched grace periods completed.
- */
-static inline unsigned long rcu_batches_completed_sched(void)
-{
-       return 0;
-}
-
-/*
- * Return the number of expedited grace periods completed.
- */
-static inline unsigned long rcu_exp_batches_completed(void)
-{
-       return 0;
-}
-
-/*
- * Return the number of expedited sched grace periods completed.
- */
-static inline unsigned long rcu_exp_batches_completed_sched(void)
-{
-       return 0;
-}
-
-static inline unsigned long srcu_batches_completed(struct srcu_struct *sp)
-{
-       return 0;
-}
-
-static inline void rcu_force_quiescent_state(void)
-{
-}
-
-static inline void rcu_bh_force_quiescent_state(void)
-{
-}
-
-static inline void rcu_sched_force_quiescent_state(void)
-{
-}
-
-static inline void show_rcu_gp_kthreads(void)
-{
-}
-
-#else /* #ifdef CONFIG_TINY_RCU */
-extern unsigned long rcutorture_testseq;
-extern unsigned long rcutorture_vernum;
-unsigned long rcu_batches_started(void);
-unsigned long rcu_batches_started_bh(void);
-unsigned long rcu_batches_started_sched(void);
-unsigned long rcu_batches_completed(void);
-unsigned long rcu_batches_completed_bh(void);
-unsigned long rcu_batches_completed_sched(void);
-unsigned long rcu_exp_batches_completed(void);
-unsigned long rcu_exp_batches_completed_sched(void);
-unsigned long srcu_batches_completed(struct srcu_struct *sp);
-void show_rcu_gp_kthreads(void);
-void rcu_force_quiescent_state(void);
-void rcu_bh_force_quiescent_state(void);
-void rcu_sched_force_quiescent_state(void);
-#endif /* #else #ifdef CONFIG_TINY_RCU */
-
-#ifdef CONFIG_RCU_NOCB_CPU
-bool rcu_is_nocb_cpu(int cpu);
-#else
-static inline bool rcu_is_nocb_cpu(int cpu) { return false; }
-#endif
 
 #endif /* __LINUX_RCU_H */
index b1fd8bf..d1bc49a 100644 (file)
@@ -6,8 +6,7 @@
 /*
  * RCU-protected list version
  */
-#include <linux/list.h>
-#include <linux/rcupdate.h>
+#include <list.h>
 
 /*
  * Why is there no list_empty_rcu()?  Because list_empty() serves this
index f816fc7..62d1ffe 100644 (file)
 #ifndef __LINUX_RCUPDATE_H
 #define __LINUX_RCUPDATE_H
 
-#include <linux/types.h>
-#include <linux/compiler.h>
-#include <linux/atomic.h>
-#include <linux/irqflags.h>
-#include <linux/preempt.h>
-#include <linux/bottom_half.h>
-#include <linux/lockdep.h>
-#include <asm/processor.h>
-#include <linux/cpumask.h>
-
 #define ULONG_CMP_GE(a, b)     (ULONG_MAX / 2 >= (a) - (b))
 #define ULONG_CMP_LT(a, b)     (ULONG_MAX / 2 < (a) - (b))
 #define ulong2long(a)          (*(long *)(&(a)))
 
-/* Exported common interfaces */
-
-#ifdef CONFIG_PREEMPT_RCU
 void call_rcu(struct rcu_head *head, rcu_callback_t func);
-#else /* #ifdef CONFIG_PREEMPT_RCU */
-#define        call_rcu        call_rcu_sched
-#endif /* #else #ifdef CONFIG_PREEMPT_RCU */
-
-void call_rcu_bh(struct rcu_head *head, rcu_callback_t func);
-void call_rcu_sched(struct rcu_head *head, rcu_callback_t func);
-void synchronize_sched(void);
-void call_rcu_tasks(struct rcu_head *head, rcu_callback_t func);
-void synchronize_rcu_tasks(void);
-void rcu_barrier_tasks(void);
-
-#ifdef CONFIG_PREEMPT_RCU
-
-void __rcu_read_lock(void);
-void __rcu_read_unlock(void);
-void rcu_read_unlock_special(struct task_struct *t);
-void synchronize_rcu(void);
-
-/*
- * Defined as a macro as it is a very low level header included from
- * areas that don't even know about current.  This gives the rcu_read_lock()
- * nesting depth, but makes sense only if CONFIG_PREEMPT_RCU -- in other
- * types of kernel builds, the rcu_read_lock() nesting depth is unknowable.
- */
-#define rcu_preempt_depth() (current->rcu_read_lock_nesting)
-
-#else /* #ifdef CONFIG_PREEMPT_RCU */
-
-static inline void __rcu_read_lock(void)
-{
-       if (IS_ENABLED(CONFIG_PREEMPT_COUNT))
-               preempt_disable();
-}
-
-static inline void __rcu_read_unlock(void)
-{
-       if (IS_ENABLED(CONFIG_PREEMPT_COUNT))
-               preempt_enable();
-}
 
-static inline void synchronize_rcu(void)
-{
-       synchronize_sched();
-}
-
-static inline int rcu_preempt_depth(void)
-{
-       return 0;
-}
-
-#endif /* #else #ifdef CONFIG_PREEMPT_RCU */
-
-/* Internal to kernel */
-void rcu_init(void);
-void rcu_sched_qs(void);
-void rcu_bh_qs(void);
-void rcu_check_callbacks(int user);
-void rcu_report_dead(unsigned int cpu);
-void rcu_cpu_starting(unsigned int cpu);
-
-#ifdef CONFIG_RCU_STALL_COMMON
-void rcu_sysrq_start(void);
-void rcu_sysrq_end(void);
-#else /* #ifdef CONFIG_RCU_STALL_COMMON */
-static inline void rcu_sysrq_start(void) { }
-static inline void rcu_sysrq_end(void) { }
-#endif /* #else #ifdef CONFIG_RCU_STALL_COMMON */
-
-#ifdef CONFIG_NO_HZ_FULL
-void rcu_user_enter(void);
-void rcu_user_exit(void);
-#else
-static inline void rcu_user_enter(void) { }
-static inline void rcu_user_exit(void) { }
-#endif /* CONFIG_NO_HZ_FULL */
-
-#ifdef CONFIG_RCU_NOCB_CPU
-void rcu_init_nohz(void);
-#else /* #ifdef CONFIG_RCU_NOCB_CPU */
-static inline void rcu_init_nohz(void) { }
-#endif /* #else #ifdef CONFIG_RCU_NOCB_CPU */
-
-/**
- * RCU_NONIDLE - Indicate idle-loop code that needs RCU readers
- * @a: Code that RCU needs to pay attention to.
- *
- * RCU, RCU-bh, and RCU-sched read-side critical sections are forbidden
- * in the inner idle loop, that is, between the rcu_idle_enter() and
- * the rcu_idle_exit() -- RCU will happily ignore any such read-side
- * critical sections.  However, things like powertop need tracepoints
- * in the inner idle loop.
- *
- * This macro provides the way out:  RCU_NONIDLE(do_something_with_RCU())
- * will tell RCU that it needs to pay attention, invoke its argument
- * (in this example, calling the do_something_with_RCU() function),
- * and then tell RCU to go back to ignoring this CPU.  It is permissible
- * to nest RCU_NONIDLE() wrappers, but not indefinitely (but the limit is
- * on the order of a million or so, even on 32-bit systems).  It is
- * not legal to block within RCU_NONIDLE(), nor is it permissible to
- * transfer control either into or out of RCU_NONIDLE()'s statement.
- */
-#define RCU_NONIDLE(a) \
-       do { \
-               rcu_irq_enter_irqson(); \
-               do { a; } while (0); \
-               rcu_irq_exit_irqson(); \
-       } while (0)
-
-/*
- * Note a voluntary context switch for RCU-tasks benefit.  This is a
- * macro rather than an inline function to avoid #include hell.
- */
-#ifdef CONFIG_TASKS_RCU
-#define TASKS_RCU(x) x
-extern struct srcu_struct tasks_rcu_exit_srcu;
-#define rcu_note_voluntary_context_switch_lite(t) \
-       do { \
-               if (READ_ONCE((t)->rcu_tasks_holdout)) \
-                       WRITE_ONCE((t)->rcu_tasks_holdout, false); \
-       } while (0)
-#define rcu_note_voluntary_context_switch(t) \
-       do { \
-               rcu_all_qs(); \
-               rcu_note_voluntary_context_switch_lite(t); \
-       } while (0)
-#else /* #ifdef CONFIG_TASKS_RCU */
-#define TASKS_RCU(x) do { } while (0)
-#define rcu_note_voluntary_context_switch_lite(t)      do { } while (0)
-#define rcu_note_voluntary_context_switch(t)           rcu_all_qs()
-#endif /* #else #ifdef CONFIG_TASKS_RCU */
-
-/**
- * cond_resched_rcu_qs - Report potential quiescent states to RCU
- *
- * This macro resembles cond_resched(), except that it is defined to
- * report potential quiescent states to RCU-tasks even if the cond_resched()
- * machinery were to be shut off, as some advocate for PREEMPT kernels.
- */
-#define cond_resched_rcu_qs() \
-do { \
-       if (!cond_resched()) \
-               rcu_note_voluntary_context_switch(current); \
-} while (0)
-
-/*
- * Infrastructure to implement the synchronize_() primitives in
- * TREE_RCU and rcu_barrier_() primitives in TINY_RCU.
- */
-
-#if defined(CONFIG_TREE_RCU) || defined(CONFIG_PREEMPT_RCU)
-#include <linux/rcutree.h>
-#elif defined(CONFIG_TINY_RCU)
-#include <linux/rcutiny.h>
-#else
-#error "Unknown RCU implementation specified to kernel configuration"
-#endif
+void synchronize_rcu(void);
 
 /*
  * init_rcu_head_on_stack()/destroy_rcu_head_on_stack() are needed for dynamic
@@ -226,111 +59,21 @@ static inline void init_rcu_head_on_stack(struct rcu_head *head) { }
 static inline void destroy_rcu_head_on_stack(struct rcu_head *head) { }
 #endif /* #else !CONFIG_DEBUG_OBJECTS_RCU_HEAD */
 
-#if defined(CONFIG_HOTPLUG_CPU) && defined(CONFIG_PROVE_RCU)
-bool rcu_lockdep_current_cpu_online(void);
-#else /* #if defined(CONFIG_HOTPLUG_CPU) && defined(CONFIG_PROVE_RCU) */
-static inline bool rcu_lockdep_current_cpu_online(void) { return true; }
-#endif /* #else #if defined(CONFIG_HOTPLUG_CPU) && defined(CONFIG_PROVE_RCU) */
-
-#ifdef CONFIG_DEBUG_LOCK_ALLOC
-
-static inline void rcu_lock_acquire(struct lockdep_map *map)
-{
-       lock_acquire(map, 0, 0, 2, 0, NULL, _THIS_IP_);
-}
-
-static inline void rcu_lock_release(struct lockdep_map *map)
-{
-       lock_release(map, 1, _THIS_IP_);
-}
-
-extern struct lockdep_map rcu_lock_map;
-extern struct lockdep_map rcu_bh_lock_map;
-extern struct lockdep_map rcu_sched_lock_map;
-extern struct lockdep_map rcu_callback_map;
-int debug_lockdep_rcu_enabled(void);
-int rcu_read_lock_held(void);
-int rcu_read_lock_bh_held(void);
-int rcu_read_lock_sched_held(void);
-
-#else /* #ifdef CONFIG_DEBUG_LOCK_ALLOC */
-
-# define rcu_lock_acquire(a)           do { } while (0)
-# define rcu_lock_release(a)           do { } while (0)
-
-static inline int rcu_read_lock_held(void)
-{
-       return 1;
-}
-
-static inline int rcu_read_lock_bh_held(void)
-{
-       return 1;
-}
+#define RCU_LOCKDEP_WARN(c, s) do { } while (0)
+#define rcu_sleep_check() do { } while (0)
+#define rcu_lock_acquire(a)            do { } while (0)
+#define rcu_lock_release(a)            do { } while (0)
+#define rcu_dereference_sparse(p, space)
 
-static inline int rcu_read_lock_sched_held(void)
+static inline void __rcu_read_lock(void)
 {
-       return !preemptible();
+       cmb();
 }
-#endif /* #else #ifdef CONFIG_DEBUG_LOCK_ALLOC */
-
-#ifdef CONFIG_PROVE_RCU
-
-/**
- * RCU_LOCKDEP_WARN - emit lockdep splat if specified condition is met
- * @c: condition to check
- * @s: informative message
- */
-#define RCU_LOCKDEP_WARN(c, s)                                         \
-       do {                                                            \
-               static bool __section(.data.unlikely) __warned;         \
-               if (debug_lockdep_rcu_enabled() && !__warned && (c)) {  \
-                       __warned = true;                                \
-                       lockdep_rcu_suspicious(__FILE__, __LINE__, s);  \
-               }                                                       \
-       } while (0)
 
-#if defined(CONFIG_PROVE_RCU) && !defined(CONFIG_PREEMPT_RCU)
-static inline void rcu_preempt_sleep_check(void)
+static inline void __rcu_read_unlock(void)
 {
-       RCU_LOCKDEP_WARN(lock_is_held(&rcu_lock_map),
-                        "Illegal context switch in RCU read-side critical section");
+       cmb();
 }
-#else /* #ifdef CONFIG_PROVE_RCU */
-static inline void rcu_preempt_sleep_check(void) { }
-#endif /* #else #ifdef CONFIG_PROVE_RCU */
-
-#define rcu_sleep_check()                                              \
-       do {                                                            \
-               rcu_preempt_sleep_check();                              \
-               RCU_LOCKDEP_WARN(lock_is_held(&rcu_bh_lock_map),        \
-                                "Illegal context switch in RCU-bh read-side critical section"); \
-               RCU_LOCKDEP_WARN(lock_is_held(&rcu_sched_lock_map),     \
-                                "Illegal context switch in RCU-sched read-side critical section"); \
-       } while (0)
-
-#else /* #ifdef CONFIG_PROVE_RCU */
-
-#define RCU_LOCKDEP_WARN(c, s) do { } while (0)
-#define rcu_sleep_check() do { } while (0)
-
-#endif /* #else #ifdef CONFIG_PROVE_RCU */
-
-/*
- * Helper functions for rcu_dereference_check(), rcu_dereference_protected()
- * and rcu_assign_pointer().  Some of these could be folded into their
- * callers, but they are left separate in order to ease introduction of
- * multiple flavors of pointers to match the multiple flavors of RCU
- * (e.g., __rcu_bh, * __rcu_sched, and __srcu), should this make sense in
- * the future.
- */
-
-#ifdef __CHECKER__
-#define rcu_dereference_sparse(p, space) \
-       ((void)(((typeof(*p) space *)p) == p))
-#else /* #ifdef __CHECKER__ */
-#define rcu_dereference_sparse(p, space)
-#endif /* #else #ifdef __CHECKER__ */
 
 #define __rcu_access_pointer(p, space) \
 ({ \
@@ -666,96 +409,6 @@ static inline void rcu_read_unlock(void)
 }
 
 /**
- * rcu_read_lock_bh() - mark the beginning of an RCU-bh critical section
- *
- * This is equivalent of rcu_read_lock(), but to be used when updates
- * are being done using call_rcu_bh() or synchronize_rcu_bh(). Since
- * both call_rcu_bh() and synchronize_rcu_bh() consider completion of a
- * softirq handler to be a quiescent state, a process in RCU read-side
- * critical section must be protected by disabling softirqs. Read-side
- * critical sections in interrupt context can use just rcu_read_lock(),
- * though this should at least be commented to avoid confusing people
- * reading the code.
- *
- * Note that rcu_read_lock_bh() and the matching rcu_read_unlock_bh()
- * must occur in the same context, for example, it is illegal to invoke
- * rcu_read_unlock_bh() from one task if the matching rcu_read_lock_bh()
- * was invoked from some other task.
- */
-static inline void rcu_read_lock_bh(void)
-{
-       local_bh_disable();
-       __acquire(RCU_BH);
-       rcu_lock_acquire(&rcu_bh_lock_map);
-       RCU_LOCKDEP_WARN(!rcu_is_watching(),
-                        "rcu_read_lock_bh() used illegally while idle");
-}
-
-/*
- * rcu_read_unlock_bh - marks the end of a softirq-only RCU critical section
- *
- * See rcu_read_lock_bh() for more information.
- */
-static inline void rcu_read_unlock_bh(void)
-{
-       RCU_LOCKDEP_WARN(!rcu_is_watching(),
-                        "rcu_read_unlock_bh() used illegally while idle");
-       rcu_lock_release(&rcu_bh_lock_map);
-       __release(RCU_BH);
-       local_bh_enable();
-}
-
-/**
- * rcu_read_lock_sched() - mark the beginning of a RCU-sched critical section
- *
- * This is equivalent of rcu_read_lock(), but to be used when updates
- * are being done using call_rcu_sched() or synchronize_rcu_sched().
- * Read-side critical sections can also be introduced by anything that
- * disables preemption, including local_irq_disable() and friends.
- *
- * Note that rcu_read_lock_sched() and the matching rcu_read_unlock_sched()
- * must occur in the same context, for example, it is illegal to invoke
- * rcu_read_unlock_sched() from process context if the matching
- * rcu_read_lock_sched() was invoked from an NMI handler.
- */
-static inline void rcu_read_lock_sched(void)
-{
-       preempt_disable();
-       __acquire(RCU_SCHED);
-       rcu_lock_acquire(&rcu_sched_lock_map);
-       RCU_LOCKDEP_WARN(!rcu_is_watching(),
-                        "rcu_read_lock_sched() used illegally while idle");
-}
-
-/* Used by lockdep and tracing: cannot be traced, cannot call lockdep. */
-static inline notrace void rcu_read_lock_sched_notrace(void)
-{
-       preempt_disable_notrace();
-       __acquire(RCU_SCHED);
-}
-
-/*
- * rcu_read_unlock_sched - marks the end of a RCU-classic critical section
- *
- * See rcu_read_lock_sched for more information.
- */
-static inline void rcu_read_unlock_sched(void)
-{
-       RCU_LOCKDEP_WARN(!rcu_is_watching(),
-                        "rcu_read_unlock_sched() used illegally while idle");
-       rcu_lock_release(&rcu_sched_lock_map);
-       __release(RCU_SCHED);
-       preempt_enable();
-}
-
-/* Used by lockdep and tracing: cannot be traced, cannot call lockdep. */
-static inline notrace void rcu_read_unlock_sched_notrace(void)
-{
-       __release(RCU_SCHED);
-       preempt_enable_notrace();
-}
-
-/**
  * RCU_INIT_POINTER() - initialize an RCU protected pointer
  *
  * Initialize an RCU-protected pointer in special cases where readers
@@ -815,7 +468,7 @@ static inline notrace void rcu_read_unlock_sched_notrace(void)
  */
 #define __kfree_rcu(head, offset) \
        do { \
-               BUILD_BUG_ON(!__is_kfree_rcu_offset(offset)); \
+               static_assert(__is_kfree_rcu_offset(offset)); \
                kfree_call_rcu(head, (rcu_callback_t)(unsigned long)(offset)); \
        } while (0)
 
index 9202163..9e5e008 100644 (file)
@@ -71,6 +71,8 @@ obj-y                                         += process.o
 obj-y                                          += radix.o
 obj-y                                          += readline.o
 obj-y                                          += rendez.o
+obj-y                                          += rcu.o
+obj-y                                          += rcu_tree_helper.o
 obj-y                                          += rwlock.o
 obj-y                                          += scatterlist.o
 obj-y                                          += schedule.o
index 5d9446d..0f450e6 100644 (file)
@@ -38,6 +38,7 @@
 #include <net/ip.h>
 #include <acpi.h>
 #include <coreboot_tables.h>
+#include <rcu.h>
 
 #define MAX_BOOT_CMDLINE_SIZE 4096
 
@@ -155,6 +156,7 @@ static void __kernel_init_part_deux(void *arg)
        timer_init();
        time_init();
        arch_init();
+       rcu_init();
        enable_irq();
        run_linker_funcs();
        /* reset/init devtab after linker funcs 3 and 4.  these run NIC and medium
index a87e2cd..1a6808b 100644 (file)
@@ -25,6 +25,7 @@
 #include <kmalloc.h>
 #include <ros/procinfo.h>
 #include <init.h>
+#include <rcu.h>
 
 struct kmem_cache *proc_cache;
 
@@ -803,6 +804,7 @@ void proc_restartcore(void)
                smp_idle();
        }
        assert(pcpui->cur_ctx);
+       rcu_report_qs();
        __proc_startcore(pcpui->owning_proc, pcpui->cur_ctx);
 }
 
diff --git a/kern/src/rcu.c b/kern/src/rcu.c
new file mode 100644 (file)
index 0000000..9a4bc36
--- /dev/null
@@ -0,0 +1,602 @@
+/* Copyright (c) 2018 Google Inc
+ * Barret Rhoden <brho@cs.berkeley.edu>
+ * See LICENSE for details.
+ *
+ * RCU.  We borrow a few things from Linux - mostly the header bits and the
+ * tree-rcu structure.
+ *
+ * Acronyms/definitions:
+ * - CB: RCU callbacks (call_rcu)
+ * - QS: quiescent state - a time when we know a core isn't in an RCU read-side
+ *   critical section.
+ * - GP: grace period.  Some quotes from Linux/Paul:
+ *   - "A time period during which all such pre-existing readers complete is
+ *   called a 'grace period'."
+ *   - "Anything outside of an RCU read-side critical section is a quiescent
+ *   state, and a grace period is any time period in which every CPU (or task,
+ *   for
+ * - gpnum: number of the current grace period we are working on
+ * - completed: number of the grace periods completed
+ *
+ * We differ in a few ways from Linux's implementation:
+ *
+ * - Callbacks run on management cores (a.k.a, LL cores, e.g. core 0).  This way
+ *   we don't have to kick idle or user space cores to run their CBs, and those
+ *   CBs don't interfere with a possibly unrelated process.
+ *
+ * - Our RCU is most similar to rcu_sched (classic RCU), and not the preemptible
+ *   RCU.  Our kthreads don't get preempted, so we don't need to worry about
+ *   read side critical sections being interrupted.
+ *
+ * - There is no softirq processing to note the passing of GPs or to run CBs.
+ *
+ * - Our tree uses atomic ops to trace grace periods within the rcu_nodes.
+ *   Linux's tree-rcu uses locks.  They need the locks since under some
+ *   circumstances, a QS would be marked during a read-side critical section,
+ *   and the QS marking needed to track the gpnum to keep the QS matched to the
+ *   GP.  See
+ *   https://www.kernel.org/doc/Documentation/RCU/Design/Data-Structures/Data-Structures.html
+ *   and grep "Come on".  We don't need to worry about this since we only mark a
+ *   QS under two situations:
+ *
+ *   - The core knows it is does not hold an rcu_read_lock, so we can always
+ *   mark QS.
+ *   - The GP kthread saw the core either idle or in userspace after the gp
+ *   started.  That means we know that core had a QS after the GP started.
+ *
+ *   So any time we mark a QS is actually a QS.  I think Linux has times where
+ *   they note a QS for an older GP, and set a note to mark that QS *for that
+ *   GP* in the future.  Their locks make sure they are marking for the right
+ *   gpnum.  There might be some element of the rnps not knowing about the
+ *   latest GP yet too.
+ *
+ * - We do use locking at the per-core level to decide whether or not to start
+ *   mark a QS for a given GP.  (lock, compare gp_acked to gpnum, etc).  This
+ *   ensures only one thread (the core or the GP kth) marks the core for a given
+ *   GP.  We actually could handle it if the both did, (make the trickle-up
+ *   idempotent, which we do for the interior nodes) but we could run into
+ *   situations where a core checks in for a GP before the global gpnum was set.
+ *   This could happen when the GP kth is resetting the tree for the next GP.
+ *   I think it'd be OK, but not worth the hassle and confusion.
+ *
+ * - We have a kthread for GP management, like Linux.  Callbacks are enqueued
+ *   locally (on the core that calls call_rcu), like Linux.  We have a kthread
+ *   per management core to process the callbacks, and these threads will handle
+ *   the callbacks of *all* cores.  Each core has a specific mgmt kthread that
+ *   will run its callbacks.  It is important that a particular core's callbacks
+ *   are processed by the same thread - I rely on this to implement rcu_barrier
+ *   easily.  In that case, we just need to schedule a CB on every core that has
+ *   CBs, and when those N CBs are done, our barrier passed.  This relies on CBs
+ *   being processed in order for a given core.  We could do the barrier in
+ *   other ways, but it doesn't seem like a big deal.
+ *
+ * - I kept around some seq counter and locking stuff in rcu_helper.h.  We might
+ *   use that in the future.
+ */
+
+#include <rcu.h>
+#include <kthread.h>
+#include <smp.h>
+#include <kmalloc.h>
+
+/* How many CBs to queue up before we trigger a GP */
+#define RCU_CB_THRESH 10
+/* How long (usec) we wait between running a GP if we weren't triggered. */
+#define RCU_GP_MIN_PERIOD 25000
+/* How long (usec) we wait for cores to check in. */
+#define RCU_GP_TARDY_PERIOD 1000
+
+/* In rcu_tree_helper.c */
+extern int rcu_num_cores;
+extern int rcu_num_lvls;
+
+/* Controls whether we skip cores when we expedite, which forces tardy cores. */
+static bool rcu_debug_tardy;
+
+/* Externed in rcu_tree_helper.c */
+struct rcu_state rcu_state;
+
+
+DEFINE_PERCPU(struct rcu_pcpui, rcu_pcpui);
+
+struct sync_cb_blob {
+       struct rcu_head h;
+       struct semaphore *sem;
+};
+
+static void __sync_cb(struct rcu_head *head)
+{
+       struct sync_cb_blob *b = container_of(head, struct sync_cb_blob, h);
+
+       sem_up(b->sem);
+}
+
+void synchronize_rcu(void)
+{
+       struct sync_cb_blob b[1];
+       struct semaphore sem[1];
+
+       sem_init(sem, 0);
+       init_rcu_head_on_stack(&b->h);
+       b->sem = sem;
+       call_rcu(&b->h, __sync_cb);
+       sem_down(sem);
+}
+
+static inline bool gp_in_progress(struct rcu_state *rsp)
+{
+       unsigned long completed = READ_ONCE(rsp->completed);
+       unsigned long gpnum = READ_ONCE(rsp->gpnum);
+
+       assert(gpnum - completed <= 1);
+       return completed != gpnum;
+}
+
+/* Wakes the kthread to run a grace period if it isn't already running.
+ *
+ * If 'force', we'll make sure it runs a fresh GP, which will catch all CBs
+ * registered before this call.  That's not 100% true.  It might be possible on
+ * some non-x86 architectures for the writes that wake the ktask are reordered
+ * before the read of gpnum that our caller made.  Thus the caller could have a
+ * CB in a later GP.  Worst case, they'll wait an extra GP timeout.  Not too
+ * concerned, though I probably should be. */
+static void wake_gp_ktask(struct rcu_state *rsp, bool force)
+{
+       if (!force && gp_in_progress(rsp))
+               return;
+       rsp->gp_ktask_ctl = 1;
+       rendez_wakeup(&rsp->gp_ktask_rv);
+}
+
+static void rcu_exec_cb(struct rcu_head *head)
+{
+       if (__is_kfree_rcu_offset((unsigned long)head->func))
+               kfree((void*)head - (unsigned long)head->func);
+       else
+               head->func(head);
+}
+
+static void __early_call_rcu_kmsg(uint32_t srcid, long a0, long a1, long a2)
+{
+       rcu_exec_cb((struct rcu_head*)a0);
+}
+
+void __early_call_rcu(struct rcu_head *head)
+{
+       extern bool booting;
+
+       assert(booting);
+       assert(core_id() == 0);
+       send_kernel_message(0, __early_call_rcu_kmsg, (long)head, 0, 0,
+                           KMSG_ROUTINE);
+}
+
+/* This could be called from a remote core, e.g. rcu_barrier().  Returns the
+ * number of enqueued CBs, including the one we pass in. */
+static int __call_rcu_rpi(struct rcu_state *rsp, struct rcu_pcpui *rpi,
+                           struct rcu_head *head, rcu_callback_t func)
+{
+       unsigned int nr_cbs;
+
+       head->func = func;
+
+       if (!rpi->booted) {
+               __early_call_rcu(head);
+               return 0;
+       }
+       /* rsp->gpnum is the one we're either working on (if > completed) or the one
+        * we already did.  Either way, it's a GP that may have already been ACKed
+        * during a core's QS, and that core could have started a read-side critical
+        * section that must complete before CB runs.  That requires another GP. */
+       head->gpnum = READ_ONCE(rsp->gpnum) + 1;
+       spin_lock_irqsave(&rpi->lock);
+       list_add_tail(&head->link, &rpi->cbs);
+       nr_cbs = ++rpi->nr_cbs;
+       spin_unlock_irqsave(&rpi->lock);
+       /* rcu_barrier requires that the write to ->nr_cbs be visible before any
+        * future writes.  unlock orders the write inside, but doesn't prevent other
+        * writes from moving in.  Technically, our lock implementations do that,
+        * but it's not part of our definition.  Maybe it should be.  Til then: */
+       wmb();
+       return nr_cbs;
+}
+
+/* Minus the kfree offset check */
+static void __call_rcu(struct rcu_head *head, rcu_callback_t func)
+{
+       struct rcu_pcpui *rpi = PERCPU_VARPTR(rcu_pcpui);
+       struct rcu_state *rsp = rpi->rsp;
+       unsigned int thresh;
+
+       thresh = __call_rcu_rpi(rsp, rpi, head, func);
+       if (thresh > RCU_CB_THRESH)
+               wake_gp_ktask(rpi->rsp, false);
+}
+
+void call_rcu(struct rcu_head *head, rcu_callback_t func)
+{
+       assert(!__is_kfree_rcu_offset((unsigned long)func));
+       __call_rcu(head, func);
+}
+
+void rcu_barrier(void)
+{
+       struct rcu_state *rsp = PERCPU_VAR(rcu_pcpui).rsp;
+       struct rcu_pcpui *rpi;
+       struct semaphore sem[1];
+       struct sync_cb_blob *b;
+       int nr_sent = 0;
+
+       /* TODO: if we have concurrent rcu_barriers, we might be able to share the
+        * CBs.  Say we have 1 CB on a core, then N rcu_barriers.  We'll have N
+        * call_rcus in flight, though we could share.  Linux does this with a mtx
+        * and some accounting, I think. */
+
+       b = kzmalloc(sizeof(struct sync_cb_blob) * num_cores, MEM_WAIT);
+       /* Remember, you block when sem is <= 0.  We'll get nr_sent ups, and we'll
+        * down 1 for each.  This is just like the synchronize_rcu() case; there,
+        * nr_sent == 1. */
+       sem_init(sem, 0);
+       /* Order any signal we received from someone who called call_rcu() before
+        * our rpi->nr_cbs reads. */
+       rmb();
+       for_each_core(i) {
+               rpi = _PERCPU_VARPTR(rcu_pcpui, i);
+               /* Lockless peek at nr_cbs.  Two things to note here:
+                * - We look at nr_cbs and not the list, since there could be CBs on the
+                *   stack-local work list or that have blocked.
+                * - The guarantee is that we wait for any CBs from call_rcus that can
+                *   be proved to happen before rcu_barrier.  That means call_rcu had to
+                *   return, which means it had to set the nr_cbs. */
+               if (!rpi->nr_cbs)
+                       continue;
+               init_rcu_head_on_stack(&b[i].h);
+               b[i].sem = sem;
+               __call_rcu_rpi(rsp, rpi, &b[i].h, __sync_cb);
+               nr_sent++;
+       }
+       if (!nr_sent) {
+               kfree(b);
+               return;
+       }
+       wake_gp_ktask(rpi->rsp, true);
+       /* sem_down_bulk is currently slow.  Even with some fixes, we actually want
+        * a barrier, which you could imagine doing with a tree.  sem_down_bulk()
+        * doesn't have the info that we have: that the wakeups are coming from N
+        * cores on the leaves of the tree. */
+       sem_down_bulk(sem, nr_sent);
+       kfree(b);
+}
+
+void rcu_force_quiescent_state(void)
+{
+       /* It's unclear if we want to block until the QS has passed */
+       wake_gp_ktask(PERCPU_VAR(rcu_pcpui).rsp, true);
+}
+
+void kfree_call_rcu(struct rcu_head *head, rcu_callback_t off)
+{
+       __call_rcu(head, off);
+}
+
+/* Clears the bits core(s) in grpmask present in rnp, trickling up to the root.
+ * Note that a 1 in qsmask means you haven't checked in - like a todo list.
+ * Last one out kicks the GP kthread. */
+static void __mark_qs(struct rcu_state *rsp, struct rcu_node *rnp,
+                      unsigned long grpmask)
+{
+       unsigned long new_qsm;
+
+       new_qsm = __sync_and_and_fetch(&rnp->qsmask, ~grpmask);
+       /* I don't fully understand this, but we need some form of transitive
+        * barrier across the entire tree.  Linux does this when they lock/unlock.
+        * Our equivalent is the atomic op. */
+       smp_mb__after_unlock_lock();
+       /* Only one thread will get 0 back - the last one to check in */
+       if (new_qsm)
+               return;
+       if (rnp->parent)
+               __mark_qs(rsp, rnp->parent, rnp->grpmask);
+       else
+               rendez_wakeup(&rsp->gp_ktask_rv);
+}
+
+static void rcu_report_qs_rpi(struct rcu_state *rsp, struct rcu_pcpui *rpi)
+{
+       /* Note we don't check ->completed == ->gpnum (gp_in_progress()).  We only
+        * care if our core hasn't reported in for a GP.  This time is a subset of
+        * gp_in_progress. */
+       if (rpi->gp_acked == READ_ONCE(rsp->gpnum)) {
+               /* If a GP starts right afterwards, oh well.  Catch it next time. */
+               return;
+       }
+       /* Lock ensures we only report a QS once per GP. */
+       spin_lock_irqsave(&rpi->lock);
+       if (rpi->gp_acked == READ_ONCE(rsp->gpnum)) {
+               spin_unlock_irqsave(&rpi->lock);
+               return;
+       }
+       /* A gp can start concurrently, but once started, we should never be behind
+        * by more than 1. */
+       assert(rpi->gp_acked + 1 == READ_ONCE(rsp->gpnum));
+       /* Up our gp_acked before actually marking it.  I don't want to hold the
+        * lock too long (e.g. some debug code in rendez_wakeup() calls call_rcu).
+        * So we've unlocked, but haven't actually checked in yet - that's fine.  No
+        * one else will attempt to check in until the next GP, which can't happen
+        * until after we check in for this GP. */
+       rpi->gp_acked++;
+       spin_unlock_irqsave(&rpi->lock);
+       __mark_qs(rsp, rpi->my_node, rpi->grpmask);
+}
+
+/* Cores advertise when they are in QSs.  If the core already reported in, or if
+ * we're not in a GP, this is a quick check (given a global read of ->gpnum). */
+void rcu_report_qs(void)
+{
+       rcu_report_qs_rpi(&rcu_state, PERCPU_VARPTR(rcu_pcpui));
+}
+
+/* For debugging checks on large trees.  Keep this in sync with
+ * rcu_init_fake_cores(). */
+static void rcu_report_qs_fake_cores(struct rcu_state *rsp)
+{
+       struct rcu_node *rnp;
+
+       rnp = rsp->level[rcu_num_lvls - 1];
+       for (int i = num_cores; i < rcu_num_cores; i++) {
+               while (i > rnp->grphi)
+                       rnp++;
+               if (rcu_debug_tardy && (i % 2))
+                       continue;
+               __mark_qs(rsp, rnp, 1 << (i - rnp->grplo));
+       }
+}
+
+static void rcu_report_qs_remote_core(struct rcu_state *rsp, int coreid)
+{
+       int cpu_state = READ_ONCE(pcpui_var(coreid, cpu_state));
+       struct rcu_pcpui *rpi = _PERCPU_VARPTR(rcu_pcpui, coreid);
+
+       /* Lockless peek.  If we ever saw them idle/user after a GP started, we
+        * know they had a QS, and we know we're still in the original GP. */
+       if (cpu_state == CPU_STATE_IDLE || cpu_state == CPU_STATE_USER)
+               rcu_report_qs_rpi(rsp, rpi);
+}
+
+/* Checks every core, remotely via the cpu state, to see if it is in a QS.
+ * This is like an expedited grace period. */
+static void rcu_report_qs_remote_cores(struct rcu_state *rsp)
+{
+       for_each_core(i) {
+               if (rcu_debug_tardy && (i % 2))
+                       continue;
+               rcu_report_qs_remote_core(rsp, i);
+       }
+}
+
+static void rcu_report_qs_tardy_cores(struct rcu_state *rsp)
+{
+       struct rcu_node *rnp;
+       unsigned long qsmask;
+       int i;
+
+       rcu_for_each_leaf_node(rsp, rnp) {
+               qsmask = READ_ONCE(rnp->qsmask);
+               if (!qsmask)
+                       continue;
+               for_each_set_bit(i, &qsmask, BITS_PER_LONG) {
+                       /* Fake cores */
+                       if (i + rnp->grplo >= num_cores) {
+                               __mark_qs(rsp, rnp, 1 << i);
+                               continue;
+                       }
+                       rcu_report_qs_remote_core(rsp, i + rnp->grplo);
+               }
+       }
+}
+
+static int root_qsmask_empty(void *arg)
+{
+       struct rcu_state *rsp = arg;
+
+       return READ_ONCE(rsp->node[0].qsmask) == 0 ? 1 : 0;
+}
+
+static void rcu_run_gp(struct rcu_state *rsp)
+{
+       struct rcu_node *rnp;
+
+       assert(rsp->gpnum == rsp->completed);
+       /* Initialize the tree for accumulating QSs.  We know there are no users on
+        * the tree.  The only time a core looks at the tree is when reporting a QS
+        * for a GP.  The previous GP is done, thus all cores reported their GP
+        * already (for the previous GP), and they won't try again until we
+        * advertise the next GP. */
+       rcu_for_each_node_breadth_first(rsp, rnp)
+               rnp->qsmask = rnp->qsmaskinit;
+       /* Need the tree set for reporting QSs before advertising the GP */
+       wmb();
+       WRITE_ONCE(rsp->gpnum, rsp->gpnum + 1);
+       /* At this point, the cores can start reporting in. */
+       /* Fake cores help test a tree larger than num_cores. */
+       rcu_report_qs_fake_cores(rsp);
+       /* Expediting aggressively.  We could also wait briefly and then check the
+        * tardy cores. */
+       rcu_report_qs_remote_cores(rsp);
+       /* Note that even when we expedite the GP by checking remote cores, there's
+        * a race where a core halted but we didn't see it.  (they report QS, decide
+        * to halt, pause, we start GP, see they haven't halted, etc.  They could
+        * report the QS after setting the state, but I didn't want to . */
+       do {
+               rendez_sleep_timeout(&rsp->gp_ktask_rv, root_qsmask_empty, rsp,
+                                    RCU_GP_TARDY_PERIOD);
+               rcu_report_qs_tardy_cores(rsp);
+       } while (!root_qsmask_empty(rsp));
+       /* Not sure if we need any barriers here.  Once we post 'completed', the CBs
+        * can start running.  But no one should touch the tree til gpnum is
+        * incremented. */
+       WRITE_ONCE(rsp->completed, rsp->gpnum);
+}
+
+static int should_wake_ctl(void *arg)
+{
+       int *ctl = arg;
+
+       return *ctl != 0 ? 1 : 0;
+}
+
+static void wake_mgmt_ktasks(struct rcu_state *rsp)
+{
+       struct rcu_pcpui *rpi;
+
+       /* TODO: For each mgmt core */
+       rpi = _PERCPU_VARPTR(rcu_pcpui, 0);
+       rpi->mgmt_ktask_ctl = 1;
+       rendez_wakeup(&rpi->mgmt_ktask_rv);
+}
+
+static void rcu_gp_ktask(void *arg)
+{
+       struct rcu_state *rsp = arg;
+
+       while (1) {
+               rendez_sleep_timeout(&rsp->gp_ktask_rv, should_wake_ctl,
+                                    &rsp->gp_ktask_ctl, RCU_GP_MIN_PERIOD);
+               rsp->gp_ktask_ctl = 0;
+               /* Our write of 0 must happen before starting the GP.  If rcu_barrier's
+                * CBs miss the start of the GP (and thus are in an unscheduled GP),
+                * their write of 1 must happen after our write of 0 so that we rerun.
+                * This is the post-and-poke pattern.  It's not a huge deal, since we'll
+                * catch it after the GP period timeout. */
+               wmb();
+               rcu_run_gp(rsp);
+               wake_mgmt_ktasks(rsp);
+       };
+}
+
+static void run_rcu_cbs(struct rcu_state *rsp, int coreid)
+{
+       struct rcu_pcpui *rpi = _PERCPU_VARPTR(rcu_pcpui, coreid);
+       struct list_head work = LIST_HEAD_INIT(work);
+       struct rcu_head *head, *temp, *last_for_gp = NULL;
+       int nr_cbs = 0;
+       unsigned long completed;
+
+       /* We'll run the CBs for any GP completed so far, but not any GP that could
+        * be completed concurrently.  "CBs for a GP" means callbacks that must wait
+        * for that GP to complete. */
+       completed = READ_ONCE(rsp->completed);
+
+       /* This lockless peek is an optimization.  We're guaranteed to not miss the
+        * CB for the given GP: If the core had a CB for this GP, it must have
+        * put it on the list before checking in, before the GP completes, and
+        * before we run. */
+       if (list_empty(&rpi->cbs))
+               return;
+
+       spin_lock_irqsave(&rpi->lock);
+       list_for_each_entry(head, &rpi->cbs, link) {
+               if (ULONG_CMP_LT(completed, head->gpnum))
+                       break;
+               nr_cbs++;
+               last_for_gp = head;
+       }
+       if (last_for_gp)
+               list_cut_position(&work, &rpi->cbs, &last_for_gp->link);
+       spin_unlock_irqsave(&rpi->lock);
+
+       if (!nr_cbs) {
+               assert(list_empty(&work));
+               return;
+       }
+       list_for_each_entry_safe(head, temp, &work, link) {
+               list_del(&head->link);
+               rcu_exec_cb(head);
+       }
+
+       /* We kept nr_cbs in place until the CBs, which could block, completed.
+        * This allows other readers (rcu_barrier()) of our pcpui to tell if we have
+        * any CBs pending.  This relies on us being the only consumer/runner of CBs
+        * for this core. */
+       spin_lock_irqsave(&rpi->lock);
+       rpi->nr_cbs -= nr_cbs;
+       spin_unlock_irqsave(&rpi->lock);
+}
+
+static void rcu_mgmt_ktask(void *arg)
+{
+       struct rcu_pcpui *rpi = arg;
+       struct rcu_state *rsp = rpi->rsp;
+
+       while (1) {
+               rendez_sleep(&rpi->mgmt_ktask_rv, should_wake_ctl,
+                            &rpi->mgmt_ktask_ctl);
+               rpi->mgmt_ktask_ctl = 0;
+               /* TODO: given the number of mgmt kthreads, we need to assign cores */
+               for_each_core(i)
+                       run_rcu_cbs(rsp, i);
+       };
+}
+
+void rcu_init_pcpui(struct rcu_state *rsp, struct rcu_pcpui *rpi, int coreid)
+{
+       struct rcu_node *rnp = rpi->my_node;
+
+       rpi->rsp = rsp;
+       assert(rnp->grplo <= coreid);
+       assert(coreid <= rnp->grphi);
+       rpi->coreid = coreid;
+       rpi->grpnum = coreid - rnp->grplo;
+       rpi->grpmask = 1 << rpi->grpnum;
+       rpi->booted = false;
+
+       /* We're single threaded now, so this is OK. */
+       rnp->qsmaskinit |= rpi->grpmask;
+
+       spinlock_init_irqsave(&rpi->lock);
+       INIT_LIST_HEAD(&rpi->cbs);
+       rpi->nr_cbs = 0;
+       rpi->gp_acked = rsp->completed;
+
+       /* TODO: For each mgmt core only */
+       if (coreid == 0) {
+               rendez_init(&rpi->mgmt_ktask_rv);
+               rpi->mgmt_ktask_ctl = 0;
+       }
+}
+
+/* Initializes the fake cores.  Works with rcu_report_qs_fake_cores() */
+static void rcu_init_fake_cores(struct rcu_state *rsp)
+{
+       struct rcu_node *rnp;
+
+       rnp = rsp->level[rcu_num_lvls - 1];
+       for (int i = num_cores; i < rcu_num_cores; i++) {
+               while (i > rnp->grphi)
+                       rnp++;
+               rnp->qsmaskinit |= 1 << (i - rnp->grplo);
+       }
+}
+
+void rcu_init(void)
+{
+       struct rcu_state *rsp = &rcu_state;
+       struct rcu_pcpui *rpi;
+
+       rcu_init_geometry();
+       rcu_init_one(rsp);
+       rcu_init_fake_cores(rsp);
+       rcu_dump_rcu_node_tree(rsp);
+
+       ktask("rcu_gp", rcu_gp_ktask, rsp);
+       /* TODO: For each mgmt core */
+       ktask("rcu_mgmt_0", rcu_mgmt_ktask, _PERCPU_VARPTR(rcu_pcpui, 0));
+
+       /* If we have a call_rcu before percpu_init, we might be using the spot in
+        * the actual __percpu .section.  We'd be core 0, so that'd be OK, since all
+        * we're using it for is reading 'booted'. */
+       for_each_core(i) {
+               rpi = _PERCPU_VARPTR(rcu_pcpui, i);
+               rpi->booted = true;
+       }
+}
index e6f6c54..4ba1db0 100644 (file)
  */
 
 
-/* Dump rcu_node combining tree at boot to verify correct setup. */
-static bool dump_tree;
-module_param(dump_tree, bool, 0444);
+#include <rcu.h>
+#include <assert.h>
+#include <smp.h>
+
 /* Control rcu_node-tree auto-balancing at boot time. */
-static bool rcu_fanout_exact;
-module_param(rcu_fanout_exact, bool, 0444);
+bool rcu_fanout_exact;
 /* Increase (but not decrease) the RCU_FANOUT_LEAF at boot time. */
-static int rcu_fanout_leaf = RCU_FANOUT_LEAF;
-module_param(rcu_fanout_leaf, int, 0444);
-int rcu_num_lvls __read_mostly = RCU_NUM_LVLS;
+int rcu_fanout_leaf = RCU_FANOUT_LEAF;
+int rcu_num_lvls = RCU_NUM_LVLS;
 /* Number of rcu_nodes at specified level. */
 int num_rcu_lvl[] = NUM_RCU_LVL_INIT;
-int rcu_num_nodes __read_mostly = NUM_RCU_NODES; /* Total # rcu_nodes in use. */
-/* panic() on RCU Stall sysctl. */
-int sysctl_panic_on_rcu_stall __read_mostly;
+int rcu_num_nodes = NUM_RCU_NODES; /* Total # rcu_nodes in use. */
+/* Number of cores RCU thinks exist.  Set to 0 or nothing to use 'num_cores'.
+ * The extra cores are called 'fake cores' in rcu.c, and are used for testing
+ * the tree. */
+int rcu_num_cores;
 
+/* in rcu.c */
+extern struct rcu_state rcu_state;
 
 /**
  * get_state_synchronize_rcu - Snapshot current RCU state
@@ -61,16 +64,15 @@ unsigned long get_state_synchronize_rcu(void)
         * Any prior manipulation of RCU-protected data must happen
         * before the load from ->gpnum.
         */
-       smp_mb();  /* ^^^ */
+       mb();  /* ^^^ */
 
        /*
         * Make sure this load happens before the purportedly
         * time-consuming work between get_state_synchronize_rcu()
         * and cond_synchronize_rcu().
         */
-       return smp_load_acquire(&rcu_state_p->gpnum);
+       return smp_load_acquire(&rcu_state.gpnum);
 }
-EXPORT_SYMBOL_GPL(get_state_synchronize_rcu);
 
 /**
  * cond_synchronize_rcu - Conditionally wait for an RCU grace period
@@ -94,31 +96,29 @@ void cond_synchronize_rcu(unsigned long oldstate)
         * Ensure that this load happens before any RCU-destructive
         * actions the caller might carry out after we return.
         */
-       newstate = smp_load_acquire(&rcu_state_p->completed);
+       newstate = smp_load_acquire(&rcu_state.completed);
        if (ULONG_CMP_GE(oldstate, newstate))
                synchronize_rcu();
 }
-EXPORT_SYMBOL_GPL(cond_synchronize_rcu);
-
 
 
 /*
  * Helper function for rcu_init() that initializes one rcu_state structure.
  */
-static void __init rcu_init_one(struct rcu_state *rsp)
+void rcu_init_one(struct rcu_state *rsp)
 {
-       static const char * const buf[] = RCU_NODE_NAME_INIT;
-       static const char * const fqs[] = RCU_FQS_NAME_INIT;
-       static struct lock_class_key rcu_node_class[RCU_NUM_LVLS];
-       static struct lock_class_key rcu_fqs_class[RCU_NUM_LVLS];
-
        int levelspread[RCU_NUM_LVLS];          /* kids/node in each level. */
        int cpustride = 1;
        int i;
        int j;
        struct rcu_node *rnp;
+       struct rcu_pcpui *rpi;
 
-       BUILD_BUG_ON(RCU_NUM_LVLS > ARRAY_SIZE(buf));  /* Fix buf[] init! */
+       rendez_init(&rsp->gp_ktask_rv);
+       rsp->gp_ktask_ctl = 0;
+       /* To test wraparound early */
+       rsp->gpnum = ULONG_MAX - 20;
+       rsp->completed = ULONG_MAX - 20;
 
        /* Silence gcc 4.8 false positive about array index out of range. */
        if (rcu_num_lvls <= 0 || rcu_num_lvls > RCU_NUM_LVLS)
@@ -126,6 +126,7 @@ static void __init rcu_init_one(struct rcu_state *rsp)
 
        /* Initialize the level-tracking arrays. */
 
+       rsp->level[0] = &rsp->node[0];
        for (i = 1; i < rcu_num_lvls; i++)
                rsp->level[i] = rsp->level[i - 1] + num_rcu_lvl[i - 1];
        rcu_init_levelspread(levelspread, num_rcu_lvl);
@@ -136,20 +137,12 @@ static void __init rcu_init_one(struct rcu_state *rsp)
                cpustride *= levelspread[i];
                rnp = rsp->level[i];
                for (j = 0; j < num_rcu_lvl[i]; j++, rnp++) {
-                       raw_spin_lock_init(&ACCESS_PRIVATE(rnp, lock));
-                       lockdep_set_class_and_name(&ACCESS_PRIVATE(rnp, lock),
-                                                  &rcu_node_class[i], buf[i]);
-                       raw_spin_lock_init(&rnp->fqslock);
-                       lockdep_set_class_and_name(&rnp->fqslock,
-                                                  &rcu_fqs_class[i], fqs[i]);
-                       rnp->gpnum = rsp->gpnum;
-                       rnp->completed = rsp->completed;
                        rnp->qsmask = 0;
                        rnp->qsmaskinit = 0;
                        rnp->grplo = j * cpustride;
                        rnp->grphi = (j + 1) * cpustride - 1;
-                       if (rnp->grphi >= nr_cpu_ids)
-                               rnp->grphi = nr_cpu_ids - 1;
+                       if (rnp->grphi >= rcu_num_cores)
+                               rnp->grphi = rcu_num_cores - 1;
                        if (i == 0) {
                                rnp->grpnum = 0;
                                rnp->grpmask = 0;
@@ -161,26 +154,21 @@ static void __init rcu_init_one(struct rcu_state *rsp)
                                                  j / levelspread[i - 1];
                        }
                        rnp->level = i;
-                       INIT_LIST_HEAD(&rnp->blkd_tasks);
-                       rcu_init_one_nocb(rnp);
-                       init_waitqueue_head(&rnp->exp_wq[0]);
-                       init_waitqueue_head(&rnp->exp_wq[1]);
-                       init_waitqueue_head(&rnp->exp_wq[2]);
-                       init_waitqueue_head(&rnp->exp_wq[3]);
-                       spin_lock_init(&rnp->exp_lock);
                }
        }
 
-       init_swait_queue_head(&rsp->gp_wq);
-       init_swait_queue_head(&rsp->expedited_wq);
        rnp = rsp->level[rcu_num_lvls - 1];
-       for_each_possible_cpu(i) {
+       for_each_core(i) {
                while (i > rnp->grphi)
                        rnp++;
-               per_cpu_ptr(rsp->rda, i)->mynode = rnp;
-               rcu_boot_init_percpu_data(i, rsp);
+               rpi = _PERCPU_VARPTR(rcu_pcpui, i);
+               rpi->my_node = rnp;
+               rcu_init_pcpui(rsp, rpi, i);
        }
-       list_add(&rsp->flavors, &rcu_struct_flavors);
+       /* Akaros has static rnps, so we can init these once. */
+       rcu_for_each_node_breadth_first(rsp, rnp)
+               if (rnp->parent)
+                       rnp->parent->qsmaskinit |= rnp->grpmask;
 }
 
 /*
@@ -188,30 +176,20 @@ static void __init rcu_init_one(struct rcu_state *rsp)
  * replace the definitions in tree.h because those are needed to size
  * the ->node array in the rcu_state structure.
  */
-static void __init rcu_init_geometry(void)
+void rcu_init_geometry(void)
 {
-       ulong d;
        int i;
        int rcu_capacity[RCU_NUM_LVLS];
+       int nr_cpu_ids;
 
-       /*
-        * Initialize any unspecified boot parameters.
-        * The default values of jiffies_till_first_fqs and
-        * jiffies_till_next_fqs are set to the RCU_JIFFIES_TILL_FORCE_QS
-        * value, which is a function of HZ, then adding one for each
-        * RCU_JIFFIES_FQS_DIV CPUs that might be on the system.
-        */
-       d = RCU_JIFFIES_TILL_FORCE_QS + nr_cpu_ids / RCU_JIFFIES_FQS_DIV;
-       if (jiffies_till_first_fqs == ULONG_MAX)
-               jiffies_till_first_fqs = d;
-       if (jiffies_till_next_fqs == ULONG_MAX)
-               jiffies_till_next_fqs = d;
-
+       if (!rcu_num_cores)
+               rcu_num_cores = num_cores;
+       nr_cpu_ids = rcu_num_cores;
        /* If the compile-time values are accurate, just leave. */
        if (rcu_fanout_leaf == RCU_FANOUT_LEAF &&
                nr_cpu_ids == NR_CPUS)
                return;
-       pr_info("RCU: Adjusting geometry for rcu_fanout_leaf=%d, nr_cpu_ids=%d\n",
+       printk("RCU: Adjusting geometry for rcu_fanout_leaf=%d, nr_cpu_ids=%d\n",
                rcu_fanout_leaf, nr_cpu_ids);
 
        /*
@@ -223,7 +201,7 @@ static void __init rcu_init_geometry(void)
        if (rcu_fanout_leaf < 2 ||
                rcu_fanout_leaf > sizeof(unsigned long) * 8) {
                rcu_fanout_leaf = RCU_FANOUT_LEAF;
-               WARN_ON(1);
+               warn_on(1);
                return;
        }
 
@@ -241,7 +219,7 @@ static void __init rcu_init_geometry(void)
         */
        if (nr_cpu_ids > rcu_capacity[RCU_NUM_LVLS - 1]) {
                rcu_fanout_leaf = RCU_FANOUT_LEAF;
-               WARN_ON(1);
+               warn_on(1);
                return;
        }
 
@@ -266,20 +244,20 @@ static void __init rcu_init_geometry(void)
  * Dump out the structure of the rcu_node combining tree associated
  * with the rcu_state structure referenced by rsp.
  */
-static void __init rcu_dump_rcu_node_tree(struct rcu_state *rsp)
+void rcu_dump_rcu_node_tree(struct rcu_state *rsp)
 {
        int level = 0;
        struct rcu_node *rnp;
 
-       pr_info("rcu_node tree layout dump\n");
-       pr_info(" ");
+       printk("rcu_node tree layout dump\n");
+       printk(" ");
        rcu_for_each_node_breadth_first(rsp, rnp) {
                if (rnp->level != level) {
-                       pr_cont("\n");
-                       pr_info(" ");
+                       printk("\n");
+                       printk(" ");
                        level = rnp->level;
                }
-               pr_cont("%d:%d ^%d  ", rnp->grplo, rnp->grphi, rnp->grpnum);
+               printk("%d:%d ^%d ", rnp->grplo, rnp->grphi, rnp->grpnum);
        }
-       pr_cont("\n");
+       printk("\n");
 }
index d08bf1d..886c7e4 100644 (file)
@@ -20,6 +20,7 @@
 #include <kmalloc.h>
 #include <core_set.h>
 #include <completion.h>
+#include <rcu.h>
 
 struct all_cpu_work {
        struct completion comp;
@@ -71,6 +72,7 @@ static void __attribute__((noreturn)) __smp_idle(void *arg)
                process_routine_kmsg();
                try_run_proc();
                cpu_bored();            /* call out to the ksched */
+               rcu_report_qs();
                /* cpu_halt() atomically turns on interrupts and halts the core.
                 * Important to do this, since we could have a RKM come in via an
                 * interrupt right while PRKM is returning, and we wouldn't catch
index 4e2753a..a3173ef 100644 (file)
@@ -32,6 +32,7 @@
 #include <termios.h>
 #include <manager.h>
 #include <ros/procinfo.h>
+#include <rcu.h>
 
 static int execargs_stringer(struct proc *p, char *d, size_t slen,
                             char *path, size_t path_l,
@@ -1543,6 +1544,7 @@ static int sys_halt_core(struct proc *p, unsigned long usec)
        /* The user can only halt CG cores!  (ones it owns) */
        if (management_core())
                return -1;
+       rcu_report_qs();
        disable_irq();
        /* both for accounting and possible RKM optimizations */
        __set_cpu_state(pcpui, CPU_STATE_IDLE);
index 5e3824d..c29ad8e 100644 (file)
@@ -12,6 +12,7 @@
 #include <assert.h>
 #include <kdebug.h>
 #include <kmalloc.h>
+#include <rcu.h>
 
 static void print_unhandled_trap(struct proc *p, struct user_context *ctx,
                                  unsigned int trap_nr, unsigned int err,
@@ -239,6 +240,10 @@ void process_routine_kmsg(void)
                 * then smp_idle() will deal with the flags.  The default state includes
                 * 'not a ktask'. */
                pcpui->cur_kthread->flags = KTH_DEFAULT_FLAGS;
+               /* PRKM is like a cooperative ksched, and our 'thread' just yielded.  If
+                * this is too much, we can do something more limited, e.g. wait for
+                * idle, check a pcpui bit that means 'check in', etc. */
+               rcu_report_qs();
                /* If we aren't still in early RKM, it is because the KMSG blocked
                 * (thus leaving early RKM, finishing in default context) and then
                 * returned.  This is a 'detached' RKM.  Must idle in this scenario,