scalable classic RCU implementation

include/linux/rcuclassic.h +23 -0

+#define MAX_RCU_LEVELS 3
+#if NR_CPUS <= CONFIG_RCU_FANOUT
+#define NUM_RCU_LEVELS 1
+#define NUM_RCU_LEVEL_1 1
+#define NUM_RCU_LEVEL_2 NR_CPUS
+#define NUM_RCU_LEVEL_3 0
+#define NUM_RCU_LEVEL_4 0
+#define NUM_RCU_NODES NUM_RCU_LEVEL_1
+#elif NR_CPUS <= CONFIG_RCU_FANOUT * CONFIG_RCU_FANOUT
+#define NUM_RCU_LEVELS 2
+#define NUM_RCU_LEVEL_1 1
+#define NUM_RCU_LEVEL_2 \
+	(((NR_CPUS) + (CONFIG_RCU_FANOUT) - 1) / (CONFIG_RCU_FANOUT))
+#define NUM_RCU_LEVEL_3 NR_CPUS
+#define NUM_RCU_LEVEL_4 0
+#define NUM_RCU_NODES \
+	((NUM_RCU_LEVEL_1) + (NUM_RCU_LEVEL_2))
+#elif NR_CPUS <= CONFIG_RCU_FANOUT * CONFIG_RCU_FANOUT * CONFIG_RCU_FANOUT
+#define NUM_RCU_LEVELS 3
+#define RCU_FANOUT_SQ ((CONFIG_RCU_FANOUT) * (CONFIG_RCU_FANOUT))
+#define NUM_RCU_LEVEL_1 1
+#define NUM_RCU_LEVEL_2 \
+	(((NR_CPUS) + (RCU_FANOUT_SQ) - 1) / (RCU_FANOUT_SQ))

Quoted 29 lines · Paul E. McKenney

include/linux/rcuclassic.h +29 -0

+#define MAX_RCU_LEVELS 3
+#if NR_CPUS <= CONFIG_RCU_FANOUT
+#define NUM_RCU_LEVELS 1
+#define NUM_RCU_LEVEL_1 1
+#define NUM_RCU_LEVEL_2 NR_CPUS
+#define NUM_RCU_LEVEL_3 0
+#define NUM_RCU_LEVEL_4 0
+#define NUM_RCU_NODES NUM_RCU_LEVEL_1
+#elif NR_CPUS <= CONFIG_RCU_FANOUT * CONFIG_RCU_FANOUT
+#define NUM_RCU_LEVELS 2
+#define NUM_RCU_LEVEL_1 1
+#define NUM_RCU_LEVEL_2 \
+	(((NR_CPUS) + (CONFIG_RCU_FANOUT) - 1) / (CONFIG_RCU_FANOUT))
+#define NUM_RCU_LEVEL_3 NR_CPUS
+#define NUM_RCU_LEVEL_4 0
+#define NUM_RCU_NODES \
+	((NUM_RCU_LEVEL_1) + (NUM_RCU_LEVEL_2))
+#elif NR_CPUS <= CONFIG_RCU_FANOUT * CONFIG_RCU_FANOUT * CONFIG_RCU_FANOUT
+#define NUM_RCU_LEVELS 3
+#define RCU_FANOUT_SQ ((CONFIG_RCU_FANOUT) * (CONFIG_RCU_FANOUT))
+#define NUM_RCU_LEVEL_1 1
+#define NUM_RCU_LEVEL_2 \
+	(((NR_CPUS) + (RCU_FANOUT_SQ) - 1) / (RCU_FANOUT_SQ))
+#define NUM_RCU_LEVEL_3 \
+	((NR_CPUS) + (CONFIG_RCU_FANOUT) - 1) / (CONFIG_RCU_FANOUT)
+#define NUM_RCU_LEVEL_4 NR_CPUS
+#define NUM_RCU_NODES \
+	((NUM_RCU_LEVEL_1) + \
+	 (NUM_RCU_LEVEL_2) + \

include/linux/rcuclassic.h line 83

Quoted 4 lines

include/linux/rcuclassic.h +4 -0

+	 (NUM_RCU_LEVEL_3))
+#else
+#error "CONFIG_RCU_FANOUT insufficient for NR_CPUS"
+#endif

just a quick stylistic suggestion: if feasible then such sizing ugliness should be hidden in a Kconfig file. (if Kconfig is capable enough for this that is)

Quoted 32 lines · Ingo Molnar

Quoted 29 lines · Paul E. McKenney

include/linux/rcuclassic.h +29 -0

+#define MAX_RCU_LEVELS 3
+#if NR_CPUS <= CONFIG_RCU_FANOUT
+#define NUM_RCU_LEVELS 1
+#define NUM_RCU_LEVEL_1 1
+#define NUM_RCU_LEVEL_2 NR_CPUS
+#define NUM_RCU_LEVEL_3 0
+#define NUM_RCU_LEVEL_4 0
+#define NUM_RCU_NODES NUM_RCU_LEVEL_1
+#elif NR_CPUS <= CONFIG_RCU_FANOUT * CONFIG_RCU_FANOUT
+#define NUM_RCU_LEVELS 2
+#define NUM_RCU_LEVEL_1 1
+#define NUM_RCU_LEVEL_2 \
+	(((NR_CPUS) + (CONFIG_RCU_FANOUT) - 1) / (CONFIG_RCU_FANOUT))
+#define NUM_RCU_LEVEL_3 NR_CPUS
+#define NUM_RCU_LEVEL_4 0
+#define NUM_RCU_NODES \
+	((NUM_RCU_LEVEL_1) + (NUM_RCU_LEVEL_2))
+#elif NR_CPUS <= CONFIG_RCU_FANOUT * CONFIG_RCU_FANOUT * CONFIG_RCU_FANOUT
+#define NUM_RCU_LEVELS 3
+#define RCU_FANOUT_SQ ((CONFIG_RCU_FANOUT) * (CONFIG_RCU_FANOUT))
+#define NUM_RCU_LEVEL_1 1
+#define NUM_RCU_LEVEL_2 \
+	(((NR_CPUS) + (RCU_FANOUT_SQ) - 1) / (RCU_FANOUT_SQ))
+#define NUM_RCU_LEVEL_3 \
+	((NR_CPUS) + (CONFIG_RCU_FANOUT) - 1) / (CONFIG_RCU_FANOUT)
+#define NUM_RCU_LEVEL_4 NR_CPUS
+#define NUM_RCU_NODES \
+	((NUM_RCU_LEVEL_1) + \
+	 (NUM_RCU_LEVEL_2) + \

Quoted 8 lines

include/linux/rcuclassic.h line 83

Quoted 4 lines

include/linux/rcuclassic.h +4 -0

+	 (NUM_RCU_LEVEL_3))
+#else
+#error "CONFIG_RCU_FANOUT insufficient for NR_CPUS"
+#endif

just a quick stylistic suggestion: if feasible then such sizing ugliness should be hidden in a Kconfig file. (if Kconfig is capable enough for this that is)

I have no idea if Kconfig can do it, but I will check.

Quoted 42 lines · Paul E. McKenney

Quoted 32 lines · Ingo Molnar

Quoted 29 lines · Paul E. McKenney

include/linux/rcuclassic.h +29 -0

+#define MAX_RCU_LEVELS 3
+#if NR_CPUS <= CONFIG_RCU_FANOUT
+#define NUM_RCU_LEVELS 1
+#define NUM_RCU_LEVEL_1 1
+#define NUM_RCU_LEVEL_2 NR_CPUS
+#define NUM_RCU_LEVEL_3 0
+#define NUM_RCU_LEVEL_4 0
+#define NUM_RCU_NODES NUM_RCU_LEVEL_1
+#elif NR_CPUS <= CONFIG_RCU_FANOUT * CONFIG_RCU_FANOUT
+#define NUM_RCU_LEVELS 2
+#define NUM_RCU_LEVEL_1 1
+#define NUM_RCU_LEVEL_2 \
+	(((NR_CPUS) + (CONFIG_RCU_FANOUT) - 1) / (CONFIG_RCU_FANOUT))
+#define NUM_RCU_LEVEL_3 NR_CPUS
+#define NUM_RCU_LEVEL_4 0
+#define NUM_RCU_NODES \
+	((NUM_RCU_LEVEL_1) + (NUM_RCU_LEVEL_2))
+#elif NR_CPUS <= CONFIG_RCU_FANOUT * CONFIG_RCU_FANOUT * CONFIG_RCU_FANOUT
+#define NUM_RCU_LEVELS 3
+#define RCU_FANOUT_SQ ((CONFIG_RCU_FANOUT) * (CONFIG_RCU_FANOUT))
+#define NUM_RCU_LEVEL_1 1
+#define NUM_RCU_LEVEL_2 \
+	(((NR_CPUS) + (RCU_FANOUT_SQ) - 1) / (RCU_FANOUT_SQ))
+#define NUM_RCU_LEVEL_3 \
+	((NR_CPUS) + (CONFIG_RCU_FANOUT) - 1) / (CONFIG_RCU_FANOUT)
+#define NUM_RCU_LEVEL_4 NR_CPUS
+#define NUM_RCU_NODES \
+	((NUM_RCU_LEVEL_1) + \
+	 (NUM_RCU_LEVEL_2) + \

Quoted 8 lines

include/linux/rcuclassic.h line 83

Quoted 4 lines

include/linux/rcuclassic.h +4 -0

+	 (NUM_RCU_LEVEL_3))
+#else
+#error "CONFIG_RCU_FANOUT insufficient for NR_CPUS"
+#endif

just a quick stylistic suggestion: if feasible then such sizing ugliness should be hidden in a Kconfig file. (if Kconfig is capable enough for this that is)

Quoted 1 line

I have no idea if Kconfig can do it, but I will check.

OK, Kconfig does not currently support arithmetic, based on zconf.y:

expr: symbol { $$ = expr_alloc_symbol($1); }

	| symbol T_EQUAL symbol			{ $$ = expr_alloc_comp(E_EQUAL, $1, $3); }
	| symbol T_UNEQUAL symbol		{ $$ = expr_alloc_comp(E_UNEQUAL, $1, $3); }
	| T_OPEN_PAREN expr T_CLOSE_PAREN	{ $$ = $2; }
	| T_NOT expr				{ $$ = expr_alloc_one(E_NOT, $2); }
	| expr T_OR expr			{ $$ = expr_alloc_two(E_OR, $1, $3); }
	| expr T_AND expr			{ $$ = expr_alloc_two(E_AND, $1, $3); }

;

All we currently get is basic comparison and logical operators. It would not be all -that- hard to add general arithmetic (famous last words), but when I tried mapping out what the sizing code would look like in such an augmented Kconfig, it was even uglier than the above.

So I took a hard look at the current mess, and prettied it as shown below. Is this a sufficient improvement?

Another alternative I am considering is moving this to a separate include file.

#define MAX_RCU_LEVELS 3
#define RCU_FANOUT (CONFIG_RCU_FANOUT) #define RCU_FANOUT_SQ (RCU_FANOUT * RCU_FANOUT) #define RCU_FANOUT_CUBE (RCU_FANOUT_SQ * RCU_FANOUT)

#if (NR_CPUS) <= RCU_FANOUT

#  define NUM_RCU_LVLS 1
#  define NUM_RCU_LVL_0 1
#  define NUM_RCU_LVL_1 (NR_CPUS)
#  define NUM_RCU_LVL_2 0
#  define NUM_RCU_LVL_3 0
#elif (NR_CPUS) <= RCU_FANOUT_SQ
#  define NUM_RCU_LVLS 2
#  define NUM_RCU_LVL_0 1
#  define NUM_RCU_LVL_1 (((NR_CPUS) + RCU_FANOUT - 1) / RCU_FANOUT)
#  define NUM_RCU_LVL_2 (NR_CPUS)
#  define NUM_RCU_LVL_3 0
#elif (NR_CPUS) <= RCU_FANOUT_CUBE
#  define NUM_RCU_LVLS 3
#  define NUM_RCU_LVL_0 1
#  define NUM_RCU_LVL_1 (((NR_CPUS) + RCU_FANOUT_SQ - 1) / RCU_FANOUT_SQ)
#  define NUM_RCU_LVL_2 (((NR_CPUS) + (RCU_FANOUT) - 1) / (RCU_FANOUT))
#  define NUM_RCU_LVL_3 NR_CPUS
#else
# error "CONFIG_RCU_FANOUT insufficient for NR_CPUS"
#endif /* #if (NR_CPUS) <= RCU_FANOUT */

#define RCU_SUM (NUM_RCU_LVL_0 + NUM_RCU_LVL_1 + NUM_RCU_LVL_2 + NUM_RCU_LVL_3) #define NUM_RCU_NODES (RCU_SUM - NR_CPUS)

Is this a sufficient improvement?

#define MAX_RCU_LEVELS 3
#define RCU_FANOUT (CONFIG_RCU_FANOUT) #define RCU_FANOUT_SQ (RCU_FANOUT * RCU_FANOUT) #define RCU_FANOUT_CUBE (RCU_FANOUT_SQ * RCU_FANOUT)

#define MAX_RCU_LEVELS 3
#define RCU_FANOUT (CONFIG_RCU_FANOUT)
#define RCU_FANOUT_SQ (RCU_FANOUT * RCU_FANOUT)
#define RCU_FANOUT_CUBE (RCU_FANOUT_SQ * RCU_FANOUT)

#if (NR_CPUS) <= RCU_FANOUT

#  define NUM_RCU_LVLS	1
#  define NUM_RCU_LVL_0	1
#  define NUM_RCU_LVL_1	(NR_CPUS)
#  define NUM_RCU_LVL_2	0
#  define NUM_RCU_LVL_3	0
#elif (NR_CPUS) <= RCU_FANOUT_SQ
#  define NUM_RCU_LVLS	2
#  define NUM_RCU_LVL_0	1
#  define NUM_RCU_LVL_1	(((NR_CPUS) + RCU_FANOUT - 1) / RCU_FANOUT)
#  define NUM_RCU_LVL_2	(NR_CPUS)
#  define NUM_RCU_LVL_3	0

#elif (NR_CPUS) <= RCU_FANOUT_CUBE

#  define NUM_RCU_LVLS	3
#  define NUM_RCU_LVL_0	1
#  define NUM_RCU_LVL_1	(((NR_CPUS) + RCU_FANOUT_SQ - 1) / RCU_FANOUT_SQ)
#  define NUM_RCU_LVL_2	(((NR_CPUS) + (RCU_FANOUT) - 1) / (RCU_FANOUT))
#  define NUM_RCU_LVL_3	NR_CPUS
#else
# error "CONFIG_RCU_FANOUT insufficient for NR_CPUS"
#endif /* #if (NR_CPUS) <= RCU_FANOUT */

Quoted 1 line · Paul E. McKenney

Is this a sufficient improvement?

yeah - looks much better. This was the block that meets the eye for the first time in the patch so it stuck out.

just one more small pet peeve of mine: please use vertical alignment too to improve readability. Instead of:

Quoted 4 lines

#define MAX_RCU_LEVELS 3
#define RCU_FANOUT (CONFIG_RCU_FANOUT) #define RCU_FANOUT_SQ (RCU_FANOUT * RCU_FANOUT) #define RCU_FANOUT_CUBE (RCU_FANOUT_SQ * RCU_FANOUT)

this looks a bit more structured IMO:

Quoted 4 lines

#define MAX_RCU_LEVELS 3
#define RCU_FANOUT (CONFIG_RCU_FANOUT)
#define RCU_FANOUT_SQ (RCU_FANOUT * RCU_FANOUT)
#define RCU_FANOUT_CUBE (RCU_FANOUT_SQ * RCU_FANOUT)

maybe even this:

Quoted 13 lines

#if (NR_CPUS) <= RCU_FANOUT

#  define NUM_RCU_LVLS	1
#  define NUM_RCU_LVL_0	1
#  define NUM_RCU_LVL_1	(NR_CPUS)
#  define NUM_RCU_LVL_2	0
#  define NUM_RCU_LVL_3	0
#elif (NR_CPUS) <= RCU_FANOUT_SQ
#  define NUM_RCU_LVLS	2
#  define NUM_RCU_LVL_0	1
#  define NUM_RCU_LVL_1	(((NR_CPUS) + RCU_FANOUT - 1) / RCU_FANOUT)
#  define NUM_RCU_LVL_2	(NR_CPUS)
#  define NUM_RCU_LVL_3	0

#elif (NR_CPUS) <= RCU_FANOUT_CUBE

Quoted 8 lines

#  define NUM_RCU_LVLS	3
#  define NUM_RCU_LVL_0	1
#  define NUM_RCU_LVL_1	(((NR_CPUS) + RCU_FANOUT_SQ - 1) / RCU_FANOUT_SQ)
#  define NUM_RCU_LVL_2	(((NR_CPUS) + (RCU_FANOUT) - 1) / (RCU_FANOUT))
#  define NUM_RCU_LVL_3	NR_CPUS
#else
# error "CONFIG_RCU_FANOUT insufficient for NR_CPUS"
#endif /* #if (NR_CPUS) <= RCU_FANOUT */

but no strong feelings on that one. (maybe inserting a space at the right places helps too, no need for a full tab)

Hello!

Experimental, not for inclusion.

Attached is a patch to Classic RCU that applies a hierarchy, greatly reducing the contention on the top-level lock for large machines. This passes mild rcutorture testing on x86 and ppc64, but is most definitely not ready for inclusion. It is OK for experimental work assuming sufficiently brave experimenters. See also Manfred Spraul's patch at http://lkml.org/lkml/2008/8/21/336 (or his earlier work from 2004 at http://marc.info/?l=linux-kernel&m=108546384711797&w=2).
We will converge onto a common patch in the fullness of time, but are currently exploring different regions of the design space.

This patch provides CONFIG_RCU_FANOUT, which controls the bushiness of the RCU hierarchy. Defaults to 32 on 32-bit machines and 64 on 64-bit machines. If CONFIG_NR_CPUS is less than CONFIG_RCU_FANOUT, there is no hierarchy. By default, the RCU initialization code will adjust CONFIG_RCU_FANOUT to balance the hierarchy, so strongly NUMA architectures may choose to set CONFIG_RCU_FANOUT_EXACT to disable this balancing, allowing the hierarchy to be exactly aligned to the underlying hardware. Up to two levels of hierarchy are permitted (in addition to the root node), allowing up to 16,384 CPUs on 32-bit systems and up to 262,144 CPUs on 64-bit systems. I just know that I am going to regret saying this, but this seems more than sufficient for the foreseeable future. (Some architectures might wish to set CONFIG_RCU_FANOUT=4, which would limit such architectures to 64 CPUs. If this becomes a real problem, additional levels can be added, but I doubt that it will make a significant difference on real hardware.)

In the common case, a given CPU will manipulate its private rcu_data structure and the rcu_node structure that it shares with its immediate neighbors. This can reduce both lock and memory contention by multiple orders of magnitude, which should eliminate the need for the strange manipulations that are reported to be required when running Linux on very large systems.

Some shortcomings:

o The interface to dynticks is clumsy at best. Improvements
on the way.

o CPU onlining and offlining is probably broken. Will be tested.

o The check-CPU-stalls code is busted. Will be fixed.

o There are probably hangs, rcutorture failures, &c.

o There is not yet a human-readable design document. Will be fixed.

o The largest machine I can get my hands on at the moment only
has 8 CPUs, which really doesn't stress this algorithm much.

If you want to use this against a Linus kernel, the following will work:

Start with 2.6.27-rc3.

Apply http://www.rdrop.com/users/paulmck/patches/paulmck-rcu.2008.08.20a.patch
which catches you up to a recent linux-2.6-tip tip/core/rcu commit.

Apply http://www.rdrop.com/users/paulmck/patches/2.6.27-rc3-hierRCU-6.patch
which gets you the current hierarchical RCU implementation.

Thoughts?

Signed-off-by Paul E. McKenney <[email protected]>

---

 include/linux/rcuclassic.h |  154 ++++--
 kernel/Kconfig.preempt     |   31 +
 kernel/Makefile            |    3 
 kernel/rcuclassic.c        | 1095 +++++++++++++++++++++++++++++----------------
 kernel/rcuclassic_trace.c  |  219 +++++++++
 5 files changed, 1076 insertions(+), 426 deletions(-)

include/linux/rcuclassic.h +0 -0

index 1658995..97e646a 100644

include/linux/rcuclassic.h +27 -10

 #ifndef __LINUX_RCUCLASSIC_H

@@ -40,69 +43,136 @@
 #include <linux/cpumask.h>
 #include <linux/seqlock.h>
 
+/*
+ * Define the shape of the rcu_node hierarchy based on NR_CPUS and
+ * CONFIG_RCU_FANOUT.
+ */
 
-/* Global control variables for rcupdate callback mechanism. */
-struct rcu_ctrlblk {
-	long	cur;		/* Current batch number.                      */
-	long	completed;	/* Number of the last completed batch         */
-	long	pending;	/* Number of the last pending batch           */
-#ifdef CONFIG_DEBUG_RCU_STALL
-	unsigned long gp_check;	/* Time grace period should end, in seconds.  */
-#endif /* #ifdef CONFIG_DEBUG_RCU_STALL */
-
-	int	signaled;
+#define MAX_RCU_LEVELS 3
+#if NR_CPUS <= CONFIG_RCU_FANOUT
+#define NUM_RCU_LEVELS 1
+#define NUM_RCU_LEVEL_1 1
+#define NUM_RCU_LEVEL_2 NR_CPUS
+#define NUM_RCU_LEVEL_3 0
+#define NUM_RCU_LEVEL_4 0
+#define NUM_RCU_NODES NUM_RCU_LEVEL_1
+#elif NR_CPUS <= CONFIG_RCU_FANOUT * CONFIG_RCU_FANOUT
+#define NUM_RCU_LEVELS 2
+#define NUM_RCU_LEVEL_1 1
+#define NUM_RCU_LEVEL_2 \
+	(((NR_CPUS) + (CONFIG_RCU_FANOUT) - 1) / (CONFIG_RCU_FANOUT))
+#define NUM_RCU_LEVEL_3 NR_CPUS
+#define NUM_RCU_LEVEL_4 0
+#define NUM_RCU_NODES \
+	((NUM_RCU_LEVEL_1) + (NUM_RCU_LEVEL_2))
+#elif NR_CPUS <= CONFIG_RCU_FANOUT * CONFIG_RCU_FANOUT * CONFIG_RCU_FANOUT
+#define NUM_RCU_LEVELS 3
+#define RCU_FANOUT_SQ ((CONFIG_RCU_FANOUT) * (CONFIG_RCU_FANOUT))
+#define NUM_RCU_LEVEL_1 1
+#define NUM_RCU_LEVEL_2 \
+	(((NR_CPUS) + (RCU_FANOUT_SQ) - 1) / (RCU_FANOUT_SQ))

include/linux/rcuclassic.h +3 -3

-	spinlock_t	lock	____cacheline_internodealigned_in_smp;
-	cpumask_t	cpumask; /* CPUs that need to switch in order    */
-				 /* for current batch to proceed.        */
+/*
+ * Definition for node within the RCU grace-period-detection hierarchy.
+ */

include/linux/rcuclassic.h +6 -5

+	struct rcu_node *parent;
 } ____cacheline_internodealigned_in_smp;
 
-/* Is batch a before batch b ? */
-static inline int rcu_batch_before(long a, long b)
-{
-	return (a - b) < 0;
-}
+/*
+ * RCU global state, including node hierarchy.  This hierarchy is
+ * represented in "heap" form in a dense array.  The root (first level)
+ * of the hierarchy is in ->node[0] (referenced by ->level[0]), the second
+ * level in ->node[1] through ->node[m] (->node[1] referenced by ->level[1]),

include/linux/rcuclassic.h +10 -6

+	long	gpnum;				/* Current gp number. */
+	long	completed;			/* # of last completed gp. */
+	spinlock_t onofflock;			/* exclude on/offline and */
+						/*  starting new GP. */
+};
 
-/* Is batch a after batch b ? */
-static inline int rcu_batch_after(long a, long b)
-{
-	return (a - b) > 0;
-}
+#define RCU_DONE_TAIL		0	/* Also RCU_WAIT head. */
+#define RCU_WAIT_TAIL		1	/* Also RCU_NEXT_READY head. */
+#define RCU_NEXT_READY_TAIL	2	/* Also RCU_NEXT head. */
+#define RCU_NEXT_TAIL		3
+#define RCU_NEXT_SIZE		4
 
 /* Per-CPU data for Read-Copy UPdate. */
 struct rcu_data {
-	/* 1) quiescent state handling : */

include/linux/rcuclassic.h +13 -7

+	struct rcu_node *mynode;	/* This CPU's leaf of hierarchy */
 
 	/* 2) batch handling */
 	/*
-	 * if nxtlist is not NULL, then:
-	 * batch:
-	 *	The batch # for the last entry of nxtlist
-	 * [*nxttail[1], NULL = *nxttail[2]):
-	 *	Entries that batch # <= batch
+	 * If nxtlist is not NULL, it is partitioned as follows.
+	 * Any of the partitions might be empty, in which case the
+	 * pointer to that partition will be equal to the pointer for
+	 * the following partition.  When the list is empty, all of
+	 * the nxttail elements point to nxtlist, which is NULL.
+	 *
+	 * [*nxttail[2], NULL = *nxttail[3]):
+	 *	Entries that might have arrived after current GP ended
+	 * [*nxttail[1], *nxttail[2]):
+	 *	Entries known to have arrived before current GP ended
 	 * [*nxttail[0], *nxttail[1]):
-	 *	Entries that batch # <= batch - 1
+	 *	Entries that batch # <= ->completed - 1: waiting for current GP
 	 * [nxtlist, *nxttail[0]):
-	 *	Entries that batch # <= batch - 2
+	 *	Entries that batch # <= ->completed
 	 *	The grace period for these entries has completed, and
 	 *	the other grace-period-completed entries may be moved
 	 *	here temporarily in rcu_process_callbacks().
 	 */

kernel/Kconfig.preempt +6 -0

 	select DEBUG_FS
 	default y
 	help

@@ -77,3 +76,33 @@ config RCU_TRACE
 
 	  Say Y here if you want to enable RCU tracing
 	  Say N if you are unsure.
+
+config RCU_FANOUT
+	int "Hierarchical RCU fanout value"
+	range 2 64 if 64BIT
+	range 2 32 if !64BIT
+	depends on CLASSIC_RCU

kernel/Kconfig.preempt +1 -0

+	  Say n if unsure.

kernel/Makefile +0 -0

index 4e1d7df..d838fbd 100644

#ifdef CONFIG_SMP

kernel/rcuclassic.c +1 -2

-static void force_quiescent_state(struct rcu_data *rdp,
-			struct rcu_ctrlblk *rcp)
+static void force_quiescent_state(struct rcu_state *rsp)
 {

Quoted 60 lines · Paul E. McKenney

Hello!

Experimental, not for inclusion.

Attached is a patch to Classic RCU that applies a hierarchy, greatly reducing the contention on the top-level lock for large machines. This passes mild rcutorture testing on x86 and ppc64, but is most definitely not ready for inclusion. It is OK for experimental work assuming sufficiently brave experimenters. See also Manfred Spraul's patch at http://lkml.org/lkml/2008/8/21/336 (or his earlier work from 2004 at http://marc.info/?l=linux-kernel&m=108546384711797&w=2).
We will converge onto a common patch in the fullness of time, but are currently exploring different regions of the design space.

This patch provides CONFIG_RCU_FANOUT, which controls the bushiness of the RCU hierarchy. Defaults to 32 on 32-bit machines and 64 on 64-bit machines. If CONFIG_NR_CPUS is less than CONFIG_RCU_FANOUT, there is no hierarchy. By default, the RCU initialization code will adjust CONFIG_RCU_FANOUT to balance the hierarchy, so strongly NUMA architectures may choose to set CONFIG_RCU_FANOUT_EXACT to disable this balancing, allowing the hierarchy to be exactly aligned to the underlying hardware. Up to two levels of hierarchy are permitted (in addition to the root node), allowing up to 16,384 CPUs on 32-bit systems and up to 262,144 CPUs on 64-bit systems. I just know that I am going to regret saying this, but this seems more than sufficient for the foreseeable future. (Some architectures might wish to set CONFIG_RCU_FANOUT=4, which would limit such architectures to 64 CPUs. If this becomes a real problem, additional levels can be added, but I doubt that it will make a significant difference on real hardware.)

In the common case, a given CPU will manipulate its private rcu_data structure and the rcu_node structure that it shares with its immediate neighbors. This can reduce both lock and memory contention by multiple orders of magnitude, which should eliminate the need for the strange manipulations that are reported to be required when running Linux on very large systems.

Some shortcomings:

o The interface to dynticks is clumsy at best. Improvements
on the way.

o CPU onlining and offlining is probably broken. Will be tested.

o The check-CPU-stalls code is busted. Will be fixed.

o There are probably hangs, rcutorture failures, &c.

o There is not yet a human-readable design document. Will be fixed.

o The largest machine I can get my hands on at the moment only
has 8 CPUs, which really doesn't stress this algorithm much.

If you want to use this against a Linus kernel, the following will work:

Start with 2.6.27-rc3.

Apply http://www.rdrop.com/users/paulmck/patches/paulmck-rcu.2008.08.20a.patch
which catches you up to a recent linux-2.6-tip tip/core/rcu commit.

Quoted 4 lines

Apply http://www.rdrop.com/users/paulmck/patches/2.6.27-rc3-hierRCU-6.patch
which gets you the current hierarchical RCU implementation.

Thoughts?

Looks great. A few comments below.

Quoted 10 lines

Signed-off-by Paul E. McKenney <[email protected]>

---

 include/linux/rcuclassic.h |  154 ++++--
 kernel/Kconfig.preempt     |   31 +
 kernel/Makefile            |    3 
 kernel/rcuclassic.c        | 1095 +++++++++++++++++++++++++++++----------------
 kernel/rcuclassic_trace.c  |  219 +++++++++
 5 files changed, 1076 insertions(+), 426 deletions(-)

include/linux/rcuclassic.h line 18

Quoted 6 lines

include/linux/rcuclassic.h +0 -0

index 1658995..97e646a 100644
@@ -18,6 +18,7 @@
  * Copyright IBM Corporation, 2001

", 2008", here and elsewhere?

Quoted 10 lines

include/linux/rcuclassic.h +3 -2

  * and inputs from Rusty Russell, Andrea Arcangeli and Andi Kleen.

@@ -26,8 +27,10 @@
  * http://lse.sourceforge.net/locking/rclock_OLS.2001.05.01c.sc.pdf (OLS2001)
  *
  * For detailed explanation of Read-Copy Update mechanism see -
- * 		Documentation/RCU
- *
+ * 	Documentation/RCU
+ * 	http://lwn.net/Articles/262464/ (What is RCU, Fundamentally?)
+ * 	http://lwn.net/Articles/263130/ (What is RCU's Usage?)

include/linux/rcuclassic.h line 34

Quoted 2 lines

include/linux/rcuclassic.h +1 -0

+ * 	http://lwn.net/Articles/264090/ (What is RCU's API? + references)
  */

Why put these references here rather than in Documentation/RCU? It seems easier to keep documentation up to date in one place. If you think these represent a good "getting started" set of documents, how about a Documentation/RCU/ReadTheseFirst with links to them, or how about linking to them from whatisRCU.txt?

Quoted 47 lines

include/linux/rcuclassic.h +31 -10

 #ifndef __LINUX_RCUCLASSIC_H

@@ -40,69 +43,136 @@
 #include <linux/cpumask.h>
 #include <linux/seqlock.h>
 
+/*
+ * Define the shape of the rcu_node hierarchy based on NR_CPUS and
+ * CONFIG_RCU_FANOUT.
+ */
 
-/* Global control variables for rcupdate callback mechanism. */
-struct rcu_ctrlblk {
-	long	cur;		/* Current batch number.                      */
-	long	completed;	/* Number of the last completed batch         */
-	long	pending;	/* Number of the last pending batch           */
-#ifdef CONFIG_DEBUG_RCU_STALL
-	unsigned long gp_check;	/* Time grace period should end, in seconds.  */
-#endif /* #ifdef CONFIG_DEBUG_RCU_STALL */
-
-	int	signaled;
+#define MAX_RCU_LEVELS 3
+#if NR_CPUS <= CONFIG_RCU_FANOUT
+#define NUM_RCU_LEVELS 1
+#define NUM_RCU_LEVEL_1 1
+#define NUM_RCU_LEVEL_2 NR_CPUS
+#define NUM_RCU_LEVEL_3 0
+#define NUM_RCU_LEVEL_4 0
+#define NUM_RCU_NODES NUM_RCU_LEVEL_1
+#elif NR_CPUS <= CONFIG_RCU_FANOUT * CONFIG_RCU_FANOUT
+#define NUM_RCU_LEVELS 2
+#define NUM_RCU_LEVEL_1 1
+#define NUM_RCU_LEVEL_2 \
+	(((NR_CPUS) + (CONFIG_RCU_FANOUT) - 1) / (CONFIG_RCU_FANOUT))
+#define NUM_RCU_LEVEL_3 NR_CPUS
+#define NUM_RCU_LEVEL_4 0
+#define NUM_RCU_NODES \
+	((NUM_RCU_LEVEL_1) + (NUM_RCU_LEVEL_2))
+#elif NR_CPUS <= CONFIG_RCU_FANOUT * CONFIG_RCU_FANOUT * CONFIG_RCU_FANOUT
+#define NUM_RCU_LEVELS 3
+#define RCU_FANOUT_SQ ((CONFIG_RCU_FANOUT) * (CONFIG_RCU_FANOUT))
+#define NUM_RCU_LEVEL_1 1
+#define NUM_RCU_LEVEL_2 \
+	(((NR_CPUS) + (RCU_FANOUT_SQ) - 1) / (RCU_FANOUT_SQ))
+#define NUM_RCU_LEVEL_3 \
+	((NR_CPUS) + (CONFIG_RCU_FANOUT) - 1) / (CONFIG_RCU_FANOUT)
+#define NUM_RCU_LEVEL_4 NR_CPUS
+#define NUM_RCU_NODES \

include/linux/rcuclassic.h line 83

Quoted 6 lines

include/linux/rcuclassic.h +6 -0

+	((NUM_RCU_LEVEL_1) + \
+	 (NUM_RCU_LEVEL_2) + \
+	 (NUM_RCU_LEVEL_3))
+#else
+#error "CONFIG_RCU_FANOUT insufficient for NR_CPUS"
+#endif

This should get replaced by the revised version you followed up with.

Quoted 10 lines

include/linux/rcuclassic.h +7 -3

-	spinlock_t	lock	____cacheline_internodealigned_in_smp;
-	cpumask_t	cpumask; /* CPUs that need to switch in order    */
-				 /* for current batch to proceed.        */
+/*
+ * Definition for node within the RCU grace-period-detection hierarchy.
+ */
+struct rcu_node {
+	spinlock_t lock;
+	unsigned long	qsmask;	/* CPUs or groups that need to switch in      */
+				/*  order for current grace period to proceed.*/

include/linux/rcuclassic.h line 97

Quoted 6 lines

include/linux/rcuclassic.h +6 -0

+	unsigned long	qsmaskinit;
+				/* Per-GP initialization for qsmask.	      */
+	int	grplo;		/* lowest-numbered CPU or group here.	      */
+	int	grphi;		/* highest-numbered CPU or group here.	      */
+	char	grpnum;		/* CPU/group number for next level up.	      */
+	char	level;		/* root is at level 0.			      */

These four fields should use sized types, and preferably unsigned types.

Quoted 17 lines

include/linux/rcuclassic.h +10 -5

+	struct rcu_node *parent;
 } ____cacheline_internodealigned_in_smp;
 
-/* Is batch a before batch b ? */
-static inline int rcu_batch_before(long a, long b)
-{
-	return (a - b) < 0;
-}
+/*
+ * RCU global state, including node hierarchy.  This hierarchy is
+ * represented in "heap" form in a dense array.  The root (first level)
+ * of the hierarchy is in ->node[0] (referenced by ->level[0]), the second
+ * level in ->node[1] through ->node[m] (->node[1] referenced by ->level[1]),
+ * and the third level in ->node[m+1] and following (->node[m+1] referenced
+ * by ->level[2]).  The number of levels is determined by the number of
+ * CPUs and by CONFIG_RCU_FANOUT.  Small systems will have a "hierarchy"
+ * consisting of a single rcu_node.

include/linux/rcuclassic.h line 115

Quoted 6 lines

include/linux/rcuclassic.h +6 -0

+ */
+struct rcu_state {
+	struct rcu_node node[NUM_RCU_NODES];	/* Hierarchy. */
+	struct rcu_node *level[NUM_RCU_LEVELS];	/* Hierarchy levels. */
+	int levelcnt[MAX_RCU_LEVELS + 1];	/* # nodes in each level. */
+	int levelspread[NUM_RCU_LEVELS];	/* kids/node in each level. */

These two should use sized types.

include/linux/rcuclassic.h line 120

Quoted 5 lines

include/linux/rcuclassic.h +5 -0

+
+	/* The following fields are guarded by the root rcu_node's lock. */
+
+	char	signaled ____cacheline_internodealigned_in_smp;
+						/* sent GP-kick IPIs? */

u8 or bool, depending on semantics. If just a simple flag, how about bool?

Quoted 17 lines

include/linux/rcuclassic.h +10 -5

+	long	gpnum;				/* Current gp number. */
+	long	completed;			/* # of last completed gp. */
+	spinlock_t onofflock;			/* exclude on/offline and */
+						/*  starting new GP. */
+};
 
-/* Is batch a after batch b ? */
-static inline int rcu_batch_after(long a, long b)
-{
-	return (a - b) > 0;
-}
+#define RCU_DONE_TAIL		0	/* Also RCU_WAIT head. */
+#define RCU_WAIT_TAIL		1	/* Also RCU_NEXT_READY head. */
+#define RCU_NEXT_READY_TAIL	2	/* Also RCU_NEXT head. */
+#define RCU_NEXT_TAIL		3
+#define RCU_NEXT_SIZE		4
 

include/linux/rcuclassic.h line 141

Quoted 13 lines

include/linux/rcuclassic.h +7 -4

 /* Per-CPU data for Read-Copy UPdate. */
 struct rcu_data {
-	/* 1) quiescent state handling : */
-	long		quiescbatch;     /* Batch # for grace period */
-	int		passed_quiesc;	 /* User-mode/idle loop etc. */
-	int		qs_pending;	 /* core waits for quiesc state */
+	/* 1) quiescent-state and grace-period handling : */
+	long		completed;	/* Track rsp->completed gp number */
+					/*  in order to detect GP end. */
+	long		gpnum;		/* Highest gp number that this CPU */
+					/*  is aware of having started. */
+	int		passed_quiesc;	/* User-mode/idle loop etc. */
+	int		qs_pending;	/* Core waits for quiesc state. */

Looks like several whitespace changes occurred here; several of these lines didn't actually change except in whitespace.

The same comment about sized types applies here, but these fields didn't actually change in this patch.

Quoted 34 lines

include/linux/rcuclassic.h +13 -11

+	struct rcu_node *mynode;	/* This CPU's leaf of hierarchy */
 
 	/* 2) batch handling */
 	/*
-	 * if nxtlist is not NULL, then:
-	 * batch:
-	 *	The batch # for the last entry of nxtlist
-	 * [*nxttail[1], NULL = *nxttail[2]):
-	 *	Entries that batch # <= batch
+	 * If nxtlist is not NULL, it is partitioned as follows.
+	 * Any of the partitions might be empty, in which case the
+	 * pointer to that partition will be equal to the pointer for
+	 * the following partition.  When the list is empty, all of
+	 * the nxttail elements point to nxtlist, which is NULL.
+	 *
+	 * [*nxttail[2], NULL = *nxttail[3]):
+	 *	Entries that might have arrived after current GP ended
+	 * [*nxttail[1], *nxttail[2]):
+	 *	Entries known to have arrived before current GP ended
 	 * [*nxttail[0], *nxttail[1]):
-	 *	Entries that batch # <= batch - 1
+	 *	Entries that batch # <= ->completed - 1: waiting for current GP
 	 * [nxtlist, *nxttail[0]):
-	 *	Entries that batch # <= batch - 2
+	 *	Entries that batch # <= ->completed
 	 *	The grace period for these entries has completed, and
 	 *	the other grace-period-completed entries may be moved
 	 *	here temporarily in rcu_process_callbacks().
 	 */
-	long  	       	batch;
 	struct rcu_head *nxtlist;
-	struct rcu_head **nxttail[3];
-	long            qlen; 	 	 /* # of queued callbacks */
-	struct rcu_head *donelist;

include/linux/rcuclassic.h line 167

Quoted 5 lines

include/linux/rcuclassic.h +3 -2

-	struct rcu_head **donetail;
-	long		blimit;		 /* Upper limit on a processed batch */
+	struct rcu_head **nxttail[RCU_NEXT_SIZE];
+	long            qlen; 	 	/* # of queued callbacks */
+	long		blimit;		/* Upper limit on a processed batch */

Some whitespace changes again here; several of these lines didn't change except in whitespace.

include/linux/rcuclassic.h line 176

Quoted 9 lines

include/linux/rcuclassic.h +3 -0

 	int cpu;
 	struct rcu_head barrier;
 };
 
+extern struct rcu_state rcu_state;
 DECLARE_PER_CPU(struct rcu_data, rcu_data);
+
+extern struct rcu_state rcu_bh_state;
 DECLARE_PER_CPU(struct rcu_data, rcu_bh_data);

Why extern and in the header? I don't see anything else using them.

Quoted 7 lines

include/linux/rcuclassic.h +0 -0

 /*

kernel/Kconfig.preempt +0 -0

index 9fdba03..43062bf 100644
@@ -68,7 +68,6 @@ config PREEMPT_RCU
 

kernel/Kconfig.preempt config PREEMPT_RCU · line 71

Quoted 3 lines

kernel/Kconfig.preempt +0 -1

 config RCU_TRACE
 	bool "Enable tracing for RCU - currently stats in debugfs"
-	depends on PREEMPT_RCU

Might want to document in the commit message that you have tracing information through RCU_TRACE, and that it applies to non-preemptible RCU as well now.

Quoted 17 lines

kernel/Kconfig.preempt +10 -0

 	select DEBUG_FS
 	default y
 	help

@@ -77,3 +76,33 @@ config RCU_TRACE
 
 	  Say Y here if you want to enable RCU tracing
 	  Say N if you are unsure.
+
+config RCU_FANOUT
+	int "Hierarchical RCU fanout value"
+	range 2 64 if 64BIT
+	range 2 32 if !64BIT
+	depends on CLASSIC_RCU
+	default 64 if 64BIT
+	default 32 if !64BIT
+	help
+	  This option controls the fanout of hierarchical implementations

kernel/Kconfig.preempt config RCU_TRACE · line 94

Quoted 6 lines

kernel/Kconfig.preempt +6 -0

+	  of RCU, allowing RCU to work efficiently on machines with
+	  large numbers of CPUs.  This value must be at least the cube
+	  root of NR_CPUS, which allows NR_CPUS up to 32,768 for 32-bit
+	  systems and up to 262,144 for 64-bit systems.
+
+	  Select a specific number if testing RCU itself.

...or if attempting to tune for a specific NUMA system.

Quoted 8 lines

kernel/Kconfig.preempt +8 -0

+	  Take the default if unsure.
+
+config RCU_FANOUT_EXACT
+	bool "Disable hierarchical RCU auto-balancing"
+	depends on CLASSIC_RCU
+	default n
+	help
+	  This option forces use of the exact RCU_FANOUT value specified,

kernel/Kconfig.preempt config RCU_TRACE · line 106

Quoted 4 lines

kernel/Kconfig.preempt +4 -0

+	  regardless of imbalances in the hierarchy.  This can be useful
+	  on systems with strong NUMA behavior.
+
+	  Without RCU_FANOUT_EXACT, the code will balance the hierarchy.

You might want to give a specific example of a NUMA machine, the appropriate value to use on that machine, and the result with and without RCU_FANOUT_EXACT.

Quoted 6 lines

kernel/Kconfig.preempt +1 -0

+	  Say n if unsure.

kernel/Makefile +0 -0

index 4e1d7df..d838fbd 100644

kernel/Makefile obj-$(CONFIG_SECCOMP) += seccomp.o · line 83

Quoted 9 lines

kernel/Makefile +3 -0

@@ -75,6 +75,9 @@ obj-$(CONFIG_SECCOMP) += seccomp.o
 obj-$(CONFIG_RCU_TORTURE_TEST) += rcutorture.o
 obj-$(CONFIG_CLASSIC_RCU) += rcuclassic.o
 obj-$(CONFIG_PREEMPT_RCU) += rcupreempt.o
+ifeq ($(CONFIG_CLASSIC_RCU),y)
+obj-$(CONFIG_RCU_TRACE) += rcuclassic_trace.o
+endif
 ifeq ($(CONFIG_PREEMPT_RCU),y)
 obj-$(CONFIG_RCU_TRACE) += rcupreempt_trace.o
 endif

It might actually make sense here to do this instead:

ifeq ($(CONFIG_RCU_TRACE),y)
obj-$(CONFIG_CLASSIC_RCU) += rcuclassic_trace.o
obj-$(CONFIG_PREEMPT_RCU) += rcupreempt_trace.o
endif

Quoted 8 lines

kernel/rcuclassic.c +0 -0

index 01e761a..5584b22 100644
@@ -27,7 +28,10 @@
  * http://lse.sourceforge.net/locking/rclock_OLS.2001.05.01c.sc.pdf (OLS2001)
  *
  * For detailed explanation of Read-Copy Update mechanism see -

kernel/rcuclassic.c line 34

Quoted 5 lines

kernel/rcuclassic.c +4 -1

- * 		Documentation/RCU
+ * 	Documentation/RCU
+ * 	http://lwn.net/Articles/262464/ (What is RCU, Fundamentally?)
+ * 	http://lwn.net/Articles/263130/ (What is RCU's Usage?)
+ * 	http://lwn.net/Articles/264090/ (What is RCU's API? + references)

Same comment as before; maintaining these in a single place seems easier.

kernel/rcuclassic.c struct lockdep_map rcu_lock_map = · line 83

Quoted 5 lines

kernel/rcuclassic.c +3 -0

+struct rcu_state rcu_state = RCU_STATE_INITIALIZER(rcu_state);
 DEFINE_PER_CPU(struct rcu_data, rcu_data) = { 0L };
+
+struct rcu_state rcu_bh_state = RCU_STATE_INITIALIZER(rcu_bh_state);
 DEFINE_PER_CPU(struct rcu_data, rcu_bh_data) = { 0L };

How about making these state structures static, along with removing the extern in the header?

kernel/rcuclassic.c struct lockdep_map rcu_lock_map = · line 87

Quoted 6 lines

kernel/rcuclassic.c +3 -3

-static int blimit = 10;
-static int qhimark = 10000;
-static int qlowmark = 100;
+static int blimit = 10;		/* Maximum callbacks per softirq. */
+static int qhimark = 10000;	/* If this many pending, ignore blimit. */
+static int qlowmark = 100;	/* Once only this many pending, use blimit. */

Indentation mismatch on the comments?

Quoted 9 lines

#ifdef CONFIG_SMP

kernel/rcuclassic.c +1 -3

-static void force_quiescent_state(struct rcu_data *rdp,
-			struct rcu_ctrlblk *rcp)
+static void force_quiescent_state(struct rcu_state *rsp)
 {
 	int cpu;
-	cpumask_t cpumask;
 	unsigned long flags;

kernel/rcuclassic.c struct lockdep_map rcu_lock_map = · line 97

Quoted 6 lines

kernel/rcuclassic.c +2 -3

 	set_need_resched();
-	spin_lock_irqsave(&rcp->lock, flags);
-	if (unlikely(!rcp->signaled)) {
-		rcp->signaled = 1;
+	if (!spin_trylock_irqsave(&rsp->onofflock, flags))
+		return;

This seems to make force_quiescent_state rather less forceful.

Quoted 4 lines

kernel/rcuclassic.c +4 -0

+/*
+ * Does the current CPU require a yet-as-unscheduled grace period?
+ */
+static inline int

kernel/rcuclassic.c static void check_cpu_stall(struct rcu_ctrlblk *rcp, struct rcu_data *rdp) · line 242

Quoted 5 lines

kernel/rcuclassic.c +5 -0

+cpu_needs_another_gp(struct rcu_state *rsp, struct rcu_data *rdp)
+{
+	return *rdp->nxttail[RCU_DONE_TAIL] &&
+	       ACCESS_ONCE(rsp->completed) == ACCESS_ONCE(rsp->gpnum);
+}

ACCESS_ONCE, like memory barriers, benefits from an accompanying explanation.

kernel/rcuclassic.c static void rcu_check_quiescent_state(struct rcu_ctrlblk *rcp, · line 632

Quoted 8 lines

kernel/rcuclassic.c +3 -2

-#else
+#else /* #ifdef CONFIG_HOTPLUG_CPU */
 
-static void rcu_offline_cpu(int cpu)
+static inline void
+rcu_offline_cpu(int cpu)
 {
 }

No need to explicitly say "inline"; GCC should do the right thing here. Same comment applies a couple of other places in your patch.

kernel/rcuclassic.c int rcu_needs_cpu(int cpu) · line 811

Quoted 8 lines

kernel/rcuclassic.c +3 -1

@@ -658,14 +806,19 @@ int rcu_needs_cpu(int cpu)
 	struct rcu_data *rdp = &per_cpu(rcu_data, cpu);
 	struct rcu_data *rdp_bh = &per_cpu(rcu_bh_data, cpu);
 
-	return !!rdp->nxtlist || !!rdp_bh->nxtlist || rcu_pending(cpu);
+	return !!*rdp->nxttail[RCU_DONE_TAIL] ||
+	       !!*rdp_bh->nxttail[RCU_DONE_TAIL] ||
+	       rcu_pending(cpu);

!! seems unnecessary here.

Quoted 10 lines

kernel/rcuclassic.c +10 -0

+void call_rcu_bh(struct rcu_head *head,
+				void (*func)(struct rcu_head *rcu))
+{
+	unsigned long flags;
+
+	head->func = func;
+	head->next = NULL;
+	local_irq_save(flags);
+	__call_rcu(head, &rcu_bh_state, &__get_cpu_var(rcu_bh_data));
+	local_irq_restore(flags);

kernel/rcuclassic.c int rcu_needs_cpu(int cpu) · line 823

Quoted 2 lines

kernel/rcuclassic.c +2 -0

+}
+EXPORT_SYMBOL_GPL(call_rcu_bh);

This comment applies to the original code, but:
You only call __call_rcu twice, in call_rcu and call_rcu_bh. Both times, you set head first, then wrap the call with local_irq_save. How about moving both into __call_rcu, making call_rcu and call_rcu_bh one-liners?

kernel/rcuclassic_trace.c

Quoted 4 lines

kernel/rcuclassic_trace.c new file +1 -0

 
+static struct mutex rcuclassic_trace_mutex;

static DEFINE_MUTEX(rcuclassic_trace_mutex);
Then you don't need mutex_init later in your init function.

kernel/rcuclassic_trace.c line 47

Quoted 2 lines

kernel/rcuclassic_trace.c new file +2 -0

+static char *rcuclassic_trace_buf;
+#define RCUPREEMPT_TRACE_BUF_SIZE 4096

Did you perhaps want PAGE_SIZE?

Quoted 11 lines · Josh Triplett

Quoted 10 lines · Paul E. McKenney

include/linux/rcuclassic.h +7 -3

-	spinlock_t	lock	____cacheline_internodealigned_in_smp;
-	cpumask_t	cpumask; /* CPUs that need to switch in order    */
-				 /* for current batch to proceed.        */
+/*
+ * Definition for node within the RCU grace-period-detection hierarchy.
+ */
+struct rcu_node {
+	spinlock_t lock;
+	unsigned long	qsmask;	/* CPUs or groups that need to switch in      */
+				/*  order for current grace period to proceed.*/

Quoted 8 lines

include/linux/rcuclassic.h line 97

Quoted 6 lines

include/linux/rcuclassic.h +6 -0

+	unsigned long	qsmaskinit;
+				/* Per-GP initialization for qsmask.	      */
+	int	grplo;		/* lowest-numbered CPU or group here.	      */
+	int	grphi;		/* highest-numbered CPU or group here.	      */
+	char	grpnum;		/* CPU/group number for next level up.	      */
+	char	level;		/* root is at level 0.			      */

These four fields should use sized types, and preferably unsigned types.

OK for grpnum and level, but grphi and grplo need to be "int" to match the various CPU-manipulation primitives.

Quoted 17 lines

Quoted 17 lines

include/linux/rcuclassic.h +10 -5

+	struct rcu_node *parent;
 } ____cacheline_internodealigned_in_smp;
 
-/* Is batch a before batch b ? */
-static inline int rcu_batch_before(long a, long b)
-{
-	return (a - b) < 0;
-}
+/*
+ * RCU global state, including node hierarchy.  This hierarchy is
+ * represented in "heap" form in a dense array.  The root (first level)
+ * of the hierarchy is in ->node[0] (referenced by ->level[0]), the second
+ * level in ->node[1] through ->node[m] (->node[1] referenced by ->level[1]),
+ * and the third level in ->node[m+1] and following (->node[m+1] referenced
+ * by ->level[2]).  The number of levels is determined by the number of
+ * CPUs and by CONFIG_RCU_FANOUT.  Small systems will have a "hierarchy"
+ * consisting of a single rcu_node.

Quoted 8 lines

include/linux/rcuclassic.h line 115

Quoted 6 lines

+ */

include/linux/rcuclassic.h +5 -0

+struct rcu_state {
+	struct rcu_node node[NUM_RCU_NODES];	/* Hierarchy. */
+	struct rcu_node *level[NUM_RCU_LEVELS];	/* Hierarchy levels. */
+	int levelcnt[MAX_RCU_LEVELS + 1];	/* # nodes in each level. */
+	int levelspread[NUM_RCU_LEVELS];	/* kids/node in each level. */

These two should use sized types.

Fair enough. And can be 8 bits, for that matter.

Quoted 8 lines

include/linux/rcuclassic.h line 120

Quoted 5 lines

include/linux/rcuclassic.h +5 -0

+
+	/* The following fields are guarded by the root rcu_node's lock. */
+
+	char	signaled ____cacheline_internodealigned_in_smp;
+						/* sent GP-kick IPIs? */

u8 or bool, depending on semantics. If just a simple flag, how about bool?

This will need to be a non-bool shortly.

OK, so what the heck -are- the official type names??? u8 seems to be defined in a powerpc-specific file. OK, it also appears in include/asm-generic/int-l64.h. s8, u8, s16, u16, s32, u32, s64, and u64, then?

Quoted 11 lines

include/linux/rcuclassic.h line 176

Quoted 9 lines

include/linux/rcuclassic.h +3 -0

 	int cpu;
 	struct rcu_head barrier;
 };
 
+extern struct rcu_state rcu_state;
 DECLARE_PER_CPU(struct rcu_data, rcu_data);
+
+extern struct rcu_state rcu_bh_state;
 DECLARE_PER_CPU(struct rcu_data, rcu_bh_data);

Why extern and in the header? I don't see anything else using them.

kernel/rcuclassic_trace.c, right?

Quoted 17 lines

Quoted 17 lines

kernel/Kconfig.preempt +10 -0

 	select DEBUG_FS
 	default y
 	help

@@ -77,3 +76,33 @@ config RCU_TRACE
 
 	  Say Y here if you want to enable RCU tracing
 	  Say N if you are unsure.
+
+config RCU_FANOUT
+	int "Hierarchical RCU fanout value"
+	range 2 64 if 64BIT
+	range 2 32 if !64BIT
+	depends on CLASSIC_RCU
+	default 64 if 64BIT
+	default 32 if !64BIT
+	help
+	  This option controls the fanout of hierarchical implementations

Quoted 8 lines

kernel/Kconfig.preempt config RCU_TRACE · line 94

Quoted 6 lines

kernel/Kconfig.preempt +6 -0

+	  of RCU, allowing RCU to work efficiently on machines with
+	  large numbers of CPUs.  This value must be at least the cube
+	  root of NR_CPUS, which allows NR_CPUS up to 32,768 for 32-bit
+	  systems and up to 262,144 for 64-bit systems.
+
+	  Select a specific number if testing RCU itself.

...or if attempting to tune for a specific NUMA system.

Indeed. But I need to see an actual example before I document it. It would be easy to make things slower by following the NUMA hardware layout.

Quoted 8 lines

Quoted 8 lines

kernel/Kconfig.preempt +8 -0

+	  Take the default if unsure.
+
+config RCU_FANOUT_EXACT
+	bool "Disable hierarchical RCU auto-balancing"
+	depends on CLASSIC_RCU
+	default n
+	help
+	  This option forces use of the exact RCU_FANOUT value specified,

Quoted 8 lines

kernel/Kconfig.preempt config RCU_TRACE · line 106

Quoted 4 lines

kernel/Kconfig.preempt +4 -0

+	  regardless of imbalances in the hierarchy.  This can be useful
+	  on systems with strong NUMA behavior.
+
+	  Without RCU_FANOUT_EXACT, the code will balance the hierarchy.

You might want to give a specific example of a NUMA machine, the appropriate value to use on that machine, and the result with and without RCU_FANOUT_EXACT.

Or change "can" to "might". ;-)

Quoted 8 lines

kernel/rcuclassic.c struct lockdep_map rcu_lock_map = · line 87

Quoted 6 lines

kernel/rcuclassic.c +3 -3

-static int blimit = 10;
-static int qhimark = 10000;
-static int qlowmark = 100;
+static int blimit = 10;		/* Maximum callbacks per softirq. */
+static int qhimark = 10000;	/* If this many pending, ignore blimit. */
+static int qlowmark = 100;	/* Once only this many pending, use blimit. */

Indentation mismatch on the comments?

Looks fine in the source -- context diff-ism.

Quoted 9 lines

Quoted 9 lines

#ifdef CONFIG_SMP

kernel/rcuclassic.c +1 -3

-static void force_quiescent_state(struct rcu_data *rdp,
-			struct rcu_ctrlblk *rcp)
+static void force_quiescent_state(struct rcu_state *rsp)
 {
 	int cpu;
-	cpumask_t cpumask;
 	unsigned long flags;

Quoted 8 lines

kernel/rcuclassic.c struct lockdep_map rcu_lock_map = · line 97

Quoted 6 lines

kernel/rcuclassic.c +2 -3

 	set_need_resched();
-	spin_lock_irqsave(&rcp->lock, flags);
-	if (unlikely(!rcp->signaled)) {
-		rcp->signaled = 1;
+	if (!spin_trylock_irqsave(&rsp->onofflock, flags))
+		return;

This seems to make force_quiescent_state rather less forceful.

It will try again on the next scheduling-clock interrupt. The reason I did this is because ->onofflock is a global lock acquired when beginning a quiescent state or when onlining/offlining. Can't let force_quiescent_state() monopolize things, and would like to exclude online/offline while doing force_quiescent_state(). Hence make force_quiescent_state() back off if the lock is held.

There is probably a better way to do this...

Quoted 11 lines

kernel/rcuclassic.c static void rcu_check_quiescent_state(struct rcu_ctrlblk *rcp, · line 632

Quoted 8 lines

kernel/rcuclassic.c +3 -2

-#else
+#else /* #ifdef CONFIG_HOTPLUG_CPU */
 
-static void rcu_offline_cpu(int cpu)
+static inline void
+rcu_offline_cpu(int cpu)
 {
 }

No need to explicitly say "inline"; GCC should do the right thing here. Same comment applies a couple of other places in your patch.

OK, I will get rid of these. You can do the other 26,000 of them. ;-)

Quoted 10 lines

kernel/rcuclassic.c int rcu_needs_cpu(int cpu) · line 811

Quoted 8 lines

kernel/rcuclassic.c +3 -1

@@ -658,14 +806,19 @@ int rcu_needs_cpu(int cpu)
 	struct rcu_data *rdp = &per_cpu(rcu_data, cpu);
 	struct rcu_data *rdp_bh = &per_cpu(rcu_bh_data, cpu);
 
-	return !!rdp->nxtlist || !!rdp_bh->nxtlist || rcu_pending(cpu);
+	return !!*rdp->nxttail[RCU_DONE_TAIL] ||
+	       !!*rdp_bh->nxttail[RCU_DONE_TAIL] ||
+	       rcu_pending(cpu);

!! seems unnecessary here.

Someone once told me why this was necessary, but I forget. It was in the original, and I didn't put it there. Some weirdness about conversion to 32-bit integer when the lower 32 bits of the pointer was zero or some such. So if your pointer value was 0x100000000, for example, so that conversion to int gives zero.

Quoted 10 lines

Quoted 10 lines

kernel/rcuclassic.c +10 -0

+void call_rcu_bh(struct rcu_head *head,
+				void (*func)(struct rcu_head *rcu))
+{
+	unsigned long flags;
+
+	head->func = func;
+	head->next = NULL;
+	local_irq_save(flags);
+	__call_rcu(head, &rcu_bh_state, &__get_cpu_var(rcu_bh_data));
+	local_irq_restore(flags);

Quoted 8 lines

Review int rcu_needs_cpu(int cpu) · line 823

Quoted 2 lines

(quoted diff) +2 -0

+}
+EXPORT_SYMBOL_GPL(call_rcu_bh);

This comment applies to the original code, but:
You only call __call_rcu twice, in call_rcu and call_rcu_bh. Both times, you set head first, then wrap the call with local_irq_save. How about moving both into __call_rcu, making call_rcu and call_rcu_bh one-liners?

I can't pass "rcu_data" to a function (or at least I don't know how to do so, short of passing __per_cpu_rcu_data and doing the per-CPU stuff by hand). I could make __call_rcu() be a macro, but that seemed more ugly than it seemed worthwhile.

Is there some other approach that would work?

Quoted 4 lines

kernel/rcuclassic_trace.c line 47

Quoted 2 lines

kernel/rcuclassic_trace.c new file +2 -0

+static char *rcuclassic_trace_buf;
+#define RCUPREEMPT_TRACE_BUF_SIZE 4096

Did you perhaps want PAGE_SIZE?

I really want some way of gracefully handling arbitrarily long output to debugfs. I am sure that some such exists, but haven't found it. What I do instead is to arbitrarily truncate output to 4096 bytes, which will be stunningly less than useful on a 4,096-CPU machine. :-/

Suggestions welcome!

Quoted 21 lines · Paul E. McKenney

Quoted 19 lines · Josh Triplett

Quoted 6 lines · Paul E. McKenney

include/linux/rcuclassic.h +3 -3

-	spinlock_t	lock	____cacheline_internodealigned_in_smp;
-	cpumask_t	cpumask; /* CPUs that need to switch in order    */
-				 /* for current batch to proceed.        */
+/*
+ * Definition for node within the RCU grace-period-detection hierarchy.
+ */

include/linux/rcuclassic.h line 97

Quoted 10 lines

include/linux/rcuclassic.h +10 -0

+struct rcu_node {
+	spinlock_t lock;
+	unsigned long	qsmask;	/* CPUs or groups that need to switch in      */
+				/*  order for current grace period to proceed.*/
+	unsigned long	qsmaskinit;
+				/* Per-GP initialization for qsmask.	      */
+	int	grplo;		/* lowest-numbered CPU or group here.	      */
+	int	grphi;		/* highest-numbered CPU or group here.	      */
+	char	grpnum;		/* CPU/group number for next level up.	      */
+	char	level;		/* root is at level 0.			      */

These four fields should use sized types, and preferably unsigned types.

Quoted 2 lines

OK for grpnum and level, but grphi and grplo need to be "int" to match the various CPU-manipulation primitives.

Fair enough; the CPU-manipulation primitives do indeed use "int". Odd that they use a signed type.

Quoted 26 lines

Quoted 25 lines

Quoted 13 lines

include/linux/rcuclassic.h +6 -5

+	struct rcu_node *parent;
 } ____cacheline_internodealigned_in_smp;
 
-/* Is batch a before batch b ? */
-static inline int rcu_batch_before(long a, long b)
-{
-	return (a - b) < 0;
-}
+/*
+ * RCU global state, including node hierarchy.  This hierarchy is
+ * represented in "heap" form in a dense array.  The root (first level)
+ * of the hierarchy is in ->node[0] (referenced by ->level[0]), the second
+ * level in ->node[1] through ->node[m] (->node[1] referenced by ->level[1]),

include/linux/rcuclassic.h line 115

Quoted 10 lines

include/linux/rcuclassic.h +10 -0

+ * and the third level in ->node[m+1] and following (->node[m+1] referenced
+ * by ->level[2]).  The number of levels is determined by the number of
+ * CPUs and by CONFIG_RCU_FANOUT.  Small systems will have a "hierarchy"
+ * consisting of a single rcu_node.
+ */
+struct rcu_state {
+	struct rcu_node node[NUM_RCU_NODES];	/* Hierarchy. */
+	struct rcu_node *level[NUM_RCU_LEVELS];	/* Hierarchy levels. */
+	int levelcnt[MAX_RCU_LEVELS + 1];	/* # nodes in each level. */
+	int levelspread[NUM_RCU_LEVELS];	/* kids/node in each level. */

These two should use sized types.

Quoted 1 line

Fair enough. And can be 8 bits, for that matter.

levelspread can, since it will never exceed 64, but levelcnt cannot. That would lead to a bug on systems with more than 256 CPUs.

Quoted 10 lines

Quoted 8 lines

include/linux/rcuclassic.h line 120

Quoted 5 lines

include/linux/rcuclassic.h +5 -0

+
+	/* The following fields are guarded by the root rcu_node's lock. */
+
+	char	signaled ____cacheline_internodealigned_in_smp;
+						/* sent GP-kick IPIs? */

u8 or bool, depending on semantics. If just a simple flag, how about bool?

This will need to be a non-bool shortly.

OK.

Quoted 4 lines

OK, so what the heck -are- the official type names??? u8 seems to be defined in a powerpc-specific file. OK, it also appears in include/asm-generic/int-l64.h. s8, u8, s16, u16, s32, u32, s64, and u64, then?

Yes. {s,u}{8,16,32,64}, defined in include/asm-generic/int-{l,ll}64.h, depending on architecture.

Quoted 12 lines

Quoted 11 lines

include/linux/rcuclassic.h line 176

Quoted 9 lines

include/linux/rcuclassic.h +3 -0

 	int cpu;
 	struct rcu_head barrier;
 };
 
+extern struct rcu_state rcu_state;
 DECLARE_PER_CPU(struct rcu_data, rcu_data);
+
+extern struct rcu_state rcu_bh_state;
 DECLARE_PER_CPU(struct rcu_data, rcu_bh_data);

Why extern and in the header? I don't see anything else using them.

Quoted 1 line

kernel/rcuclassic_trace.c, right?

Hmmm, true. Unfortunate, particularly if only for the benefit of tracing code which doesn't even get compiled under normal circumstances.

Quoted 26 lines

Quoted 17 lines

Quoted 17 lines

kernel/Kconfig.preempt +10 -0

 	select DEBUG_FS
 	default y
 	help

@@ -77,3 +76,33 @@ config RCU_TRACE
 
 	  Say Y here if you want to enable RCU tracing
 	  Say N if you are unsure.
+
+config RCU_FANOUT
+	int "Hierarchical RCU fanout value"
+	range 2 64 if 64BIT
+	range 2 32 if !64BIT
+	depends on CLASSIC_RCU
+	default 64 if 64BIT
+	default 32 if !64BIT
+	help
+	  This option controls the fanout of hierarchical implementations

Quoted 8 lines

kernel/Kconfig.preempt config RCU_TRACE · line 94

Quoted 6 lines

kernel/Kconfig.preempt +6 -0

+	  of RCU, allowing RCU to work efficiently on machines with
+	  large numbers of CPUs.  This value must be at least the cube
+	  root of NR_CPUS, which allows NR_CPUS up to 32,768 for 32-bit
+	  systems and up to 262,144 for 64-bit systems.
+
+	  Select a specific number if testing RCU itself.

...or if attempting to tune for a specific NUMA system.

Quoted 3 lines

Indeed. But I need to see an actual example before I document it. It would be easy to make things slower by following the NUMA hardware layout.

Fair enough.

Quoted 17 lines

Quoted 16 lines

kernel/Kconfig.preempt config RCU_TRACE · line 106

Quoted 12 lines

kernel/Kconfig.preempt +12 -0

+	  Take the default if unsure.
+
+config RCU_FANOUT_EXACT
+	bool "Disable hierarchical RCU auto-balancing"
+	depends on CLASSIC_RCU
+	default n
+	help
+	  This option forces use of the exact RCU_FANOUT value specified,
+	  regardless of imbalances in the hierarchy.  This can be useful
+	  on systems with strong NUMA behavior.
+
+	  Without RCU_FANOUT_EXACT, the code will balance the hierarchy.

You might want to give a specific example of a NUMA machine, the appropriate value to use on that machine, and the result with and without RCU_FANOUT_EXACT.

Quoted 1 line

Or change "can" to "might". ;-)

:)

Right, my comment only applies if such an example actually exists. :)

Quoted 10 lines

Quoted 8 lines

kernel/rcuclassic.c struct lockdep_map rcu_lock_map = · line 87

Quoted 6 lines

kernel/rcuclassic.c +3 -3

-static int blimit = 10;
-static int qhimark = 10000;
-static int qlowmark = 100;
+static int blimit = 10;		/* Maximum callbacks per softirq. */
+static int qhimark = 10000;	/* If this many pending, ignore blimit. */
+static int qlowmark = 100;	/* Once only this many pending, use blimit. */

Indentation mismatch on the comments?

Looks fine in the source -- context diff-ism.

Sigh. Yay for tabs.

Quoted 25 lines

Quoted 9 lines

Quoted 9 lines

#ifdef CONFIG_SMP

kernel/rcuclassic.c +1 -3

-static void force_quiescent_state(struct rcu_data *rdp,
-			struct rcu_ctrlblk *rcp)
+static void force_quiescent_state(struct rcu_state *rsp)
 {
 	int cpu;
-	cpumask_t cpumask;
 	unsigned long flags;

Quoted 8 lines

kernel/rcuclassic.c struct lockdep_map rcu_lock_map = · line 97

Quoted 6 lines

kernel/rcuclassic.c +2 -3

 	set_need_resched();
-	spin_lock_irqsave(&rcp->lock, flags);
-	if (unlikely(!rcp->signaled)) {
-		rcp->signaled = 1;
+	if (!spin_trylock_irqsave(&rsp->onofflock, flags))
+		return;

This seems to make force_quiescent_state rather less forceful.

It will try again on the next scheduling-clock interrupt. The reason I did this is because ->onofflock is a global lock acquired when beginning a quiescent state or when onlining/offlining. Can't let force_quiescent_state() monopolize things, and would like to exclude online/offline while doing force_quiescent_state(). Hence make force_quiescent_state() back off if the lock is held.

Quoted 1 line

There is probably a better way to do this...

Primarily concerned about the possibility of perpetual failure. Then again, eventually a grace period will occur "naturally". Just wondering whether the inability to force might cause a problem.

Quoted 12 lines

Quoted 11 lines

kernel/rcuclassic.c static void rcu_check_quiescent_state(struct rcu_ctrlblk *rcp, · line 632

Quoted 8 lines

kernel/rcuclassic.c +3 -2

-#else
+#else /* #ifdef CONFIG_HOTPLUG_CPU */
 
-static void rcu_offline_cpu(int cpu)
+static inline void
+rcu_offline_cpu(int cpu)
 {
 }

No need to explicitly say "inline"; GCC should do the right thing here. Same comment applies a couple of other places in your patch.

Quoted 1 line

OK, I will get rid of these. You can do the other 26,000 of them. ;-)

:)

Quoted 11 lines

Quoted 10 lines

kernel/rcuclassic.c int rcu_needs_cpu(int cpu) · line 811

Quoted 8 lines

kernel/rcuclassic.c +3 -1

@@ -658,14 +806,19 @@ int rcu_needs_cpu(int cpu)
 	struct rcu_data *rdp = &per_cpu(rcu_data, cpu);
 	struct rcu_data *rdp_bh = &per_cpu(rcu_bh_data, cpu);
 
-	return !!rdp->nxtlist || !!rdp_bh->nxtlist || rcu_pending(cpu);
+	return !!*rdp->nxttail[RCU_DONE_TAIL] ||
+	       !!*rdp_bh->nxttail[RCU_DONE_TAIL] ||
+	       rcu_pending(cpu);

!! seems unnecessary here.

Quoted 5 lines

Someone once told me why this was necessary, but I forget. It was in the original, and I didn't put it there. Some weirdness about conversion to 32-bit integer when the lower 32 bits of the pointer was zero or some such. So if your pointer value was 0x100000000, for example, so that conversion to int gives zero.

Good point! That doesn't apply if you use ||, though. If you just did "return somepointer" that could potentially cause the problem you describe. In any case, it can't *hurt* to have it; GCC should do the sane thing.

Quoted 19 lines

Quoted 18 lines

kernel/rcuclassic.c void rcu_check_callbacks(int cpu, int user) · line 937

Quoted 12 lines

kernel/rcuclassic.c +12 -0

+void call_rcu_bh(struct rcu_head *head,
+				void (*func)(struct rcu_head *rcu))
+{
+	unsigned long flags;
+
+	head->func = func;
+	head->next = NULL;
+	local_irq_save(flags);
+	__call_rcu(head, &rcu_bh_state, &__get_cpu_var(rcu_bh_data));
+	local_irq_restore(flags);
+}
+EXPORT_SYMBOL_GPL(call_rcu_bh);

This comment applies to the original code, but:
You only call __call_rcu twice, in call_rcu and call_rcu_bh. Both times, you set head first, then wrap the call with local_irq_save. How about moving both into __call_rcu, making call_rcu and call_rcu_bh one-liners?

Quoted 6 lines

I can't pass "rcu_data" to a function (or at least I don't know how to do so, short of passing __per_cpu_rcu_data and doing the per-CPU stuff by hand). I could make __call_rcu() be a macro, but that seemed more ugly than it seemed worthwhile.

Is there some other approach that would work?

Hmmm. No, not that I know of. Sigh.

Quoted 11 lines

Quoted 4 lines

kernel/rcuclassic_trace.c line 47

Quoted 2 lines

kernel/rcuclassic_trace.c new file +2 -0

+static char *rcuclassic_trace_buf;
+#define RCUPREEMPT_TRACE_BUF_SIZE 4096

Did you perhaps want PAGE_SIZE?

I really want some way of gracefully handling arbitrarily long output to debugfs. I am sure that some such exists, but haven't found it. What I do instead is to arbitrarily truncate output to 4096 bytes, which will be stunningly less than useful on a 4,096-CPU machine. :-/

Suggestions welcome!

I can see two possibilities, depending on how much complexity you want.

The complicated way: do one pass calling snprintf everywhere and adding up the total length used, and if you run out of memory during that pass, reallocate the buffer to at least the total length you accumulated. Or something like that.

The simple hack:
#define RCUPREEMPT_TRACE_BUF_SIZE (NR_CPUS * something)

:)

Quoted 20 lines · Josh Triplett

Quoted 13 lines · Paul E. McKenney

Quoted 11 lines · Josh Triplett

kernel/rcuclassic.c int rcu_needs_cpu(int cpu) · line 811

Quoted 8 lines · Paul E. McKenney

kernel/rcuclassic.c +3 -1

@@ -658,14 +806,19 @@ int rcu_needs_cpu(int cpu)
 	struct rcu_data *rdp = &per_cpu(rcu_data, cpu);
 	struct rcu_data *rdp_bh = &per_cpu(rcu_bh_data, cpu);
 
-	return !!rdp->nxtlist || !!rdp_bh->nxtlist || rcu_pending(cpu);
+	return !!*rdp->nxttail[RCU_DONE_TAIL] ||
+	       !!*rdp_bh->nxttail[RCU_DONE_TAIL] ||
+	       rcu_pending(cpu);

!! seems unnecessary here.

Quoted 5 lines

Someone once told me why this was necessary, but I forget. It was in the original, and I didn't put it there. Some weirdness about conversion to 32-bit integer when the lower 32 bits of the pointer was zero or some such. So if your pointer value was 0x100000000, for example, so that conversion to int gives zero.

Quoted 4 lines

Good point! That doesn't apply if you use ||, though. If you just did "return somepointer" that could potentially cause the problem you describe. In any case, it can't *hurt* to have it; GCC should do the sane thing.

OK. I will review this towards the end, leaving it there to remind me in the meantime.

So, would I need the !! on the left-hand operand of the first || due to short-circuiting?

Quoted 26 lines · Paul E. McKenney

Quoted 24 lines · Josh Triplett

Quoted 13 lines · Paul E. McKenney

Quoted 11 lines · Josh Triplett

kernel/rcuclassic.c int rcu_needs_cpu(int cpu) · line 811

Quoted 8 lines · Paul E. McKenney

kernel/rcuclassic.c +3 -1

@@ -658,14 +806,19 @@ int rcu_needs_cpu(int cpu)
 	struct rcu_data *rdp = &per_cpu(rcu_data, cpu);
 	struct rcu_data *rdp_bh = &per_cpu(rcu_bh_data, cpu);
 
-	return !!rdp->nxtlist || !!rdp_bh->nxtlist || rcu_pending(cpu);
+	return !!*rdp->nxttail[RCU_DONE_TAIL] ||
+	       !!*rdp_bh->nxttail[RCU_DONE_TAIL] ||
+	       rcu_pending(cpu);

!! seems unnecessary here.

Quoted 5 lines

Someone once told me why this was necessary, but I forget. It was in the original, and I didn't put it there. Some weirdness about conversion to 32-bit integer when the lower 32 bits of the pointer was zero or some such. So if your pointer value was 0x100000000, for example, so that conversion to int gives zero.

Good point! That doesn't apply if you use ||, though. If you just did "return somepointer" that could potentially cause the problem you describe. In any case, it can't *hurt* to have it; GCC should do the sane thing.

Quoted 5 lines

OK. I will review this towards the end, leaving it there to remind me in the meantime.

So, would I need the !! on the left-hand operand of the first || due to short-circuiting?

No. || will always return 1 or 0. You only need the !! if you want to directly return the boolean value of a potentially 64-bit pointer.

Quoted 30 lines · Josh Triplett

Quoted 29 lines · Paul E. McKenney

Quoted 20 lines · Josh Triplett

Quoted 13 lines · Paul E. McKenney

Quoted 11 lines · Josh Triplett

Review int rcu_needs_cpu(int cpu) · line 811

Quoted 8 lines · Paul E. McKenney

(quoted diff) +3 -1

@@ -658,14 +806,19 @@ int rcu_needs_cpu(int cpu)
 	struct rcu_data *rdp = &per_cpu(rcu_data, cpu);
 	struct rcu_data *rdp_bh = &per_cpu(rcu_bh_data, cpu);
 
-	return !!rdp->nxtlist || !!rdp_bh->nxtlist || rcu_pending(cpu);
+	return !!*rdp->nxttail[RCU_DONE_TAIL] ||
+	       !!*rdp_bh->nxttail[RCU_DONE_TAIL] ||
+	       rcu_pending(cpu);

!! seems unnecessary here.

Quoted 5 lines

Someone once told me why this was necessary, but I forget. It was in the original, and I didn't put it there. Some weirdness about conversion to 32-bit integer when the lower 32 bits of the pointer was zero or some such. So if your pointer value was 0x100000000, for example, so that conversion to int gives zero.

Quoted 4 lines

Good point! That doesn't apply if you use ||, though. If you just did "return somepointer" that could potentially cause the problem you describe. In any case, it can't *hurt* to have it; GCC should do the sane thing.

OK. I will review this towards the end, leaving it there to remind me in the meantime.

Quoted 5 lines

Quoted 2 lines

So, would I need the !! on the left-hand operand of the first || due to short-circuiting?

No. || will always return 1 or 0. You only need the !! if you want to directly return the boolean value of a potentially 64-bit pointer.

Even if one argument of || is long and the other int or some fool thing like that? (What, me paranoid???)

Quoted 34 lines · Paul E. McKenney

Quoted 33 lines · Josh Triplett

Quoted 31 lines · Paul E. McKenney

Quoted 20 lines · Josh Triplett

Quoted 13 lines · Paul E. McKenney

Quoted 11 lines · Josh Triplett

Review int rcu_needs_cpu(int cpu) · line 811

Quoted 8 lines · Paul E. McKenney

(quoted diff) +3 -1

@@ -658,14 +806,19 @@ int rcu_needs_cpu(int cpu)
 	struct rcu_data *rdp = &per_cpu(rcu_data, cpu);
 	struct rcu_data *rdp_bh = &per_cpu(rcu_bh_data, cpu);
 
-	return !!rdp->nxtlist || !!rdp_bh->nxtlist || rcu_pending(cpu);
+	return !!*rdp->nxttail[RCU_DONE_TAIL] ||
+	       !!*rdp_bh->nxttail[RCU_DONE_TAIL] ||
+	       rcu_pending(cpu);

!! seems unnecessary here.

Quoted 5 lines

Someone once told me why this was necessary, but I forget. It was in the original, and I didn't put it there. Some weirdness about conversion to 32-bit integer when the lower 32 bits of the pointer was zero or some such. So if your pointer value was 0x100000000, for example, so that conversion to int gives zero.

Quoted 4 lines

Good point! That doesn't apply if you use ||, though. If you just did "return somepointer" that could potentially cause the problem you describe. In any case, it can't *hurt* to have it; GCC should do the sane thing.

OK. I will review this towards the end, leaving it there to remind me in the meantime.

So, would I need the !! on the left-hand operand of the first || due to short-circuiting?

Quoted 5 lines

Quoted 2 lines

No. || will always return 1 or 0. You only need the !! if you want to directly return the boolean value of a potentially 64-bit pointer.

Even if one argument of || is long and the other int or some fool thing like that? (What, me paranoid???)

What, you don't know exactly how C behaves in every strange corner case? ;)

|| always produces a result of type int, and it compares each of its two arguments to 0 independently; to the best of my knowledge the size of those arguments never matters.

Quoted 9 lines

include/linux/rcuclassic.h +3 -2

@@ -26,8 +27,10 @@
  * http://lse.sourceforge.net/locking/rclock_OLS.2001.05.01c.sc.pdf (OLS2001)
  *
  * For detailed explanation of Read-Copy Update mechanism see -
- * 		Documentation/RCU
- *
+ * 	Documentation/RCU
+ * 	http://lwn.net/Articles/262464/ (What is RCU, Fundamentally?)
+ * 	http://lwn.net/Articles/263130/ (What is RCU's Usage?)

Review line 34

Quoted 2 lines

(quoted diff) +1 -0

+ * 	http://lwn.net/Articles/264090/ (What is RCU's API? + references)
  */

Why put these references here rather than in Documentation/RCU? It seems easier to keep documentation up to date in one place. If you think these represent a good "getting started" set of documents, how about a Documentation/RCU/ReadTheseFirst with links to them, or how about linking to them from whatisRCU.txt?

Quoted 9 lines · Josh Triplett

Quoted 9 lines

include/linux/rcuclassic.h +3 -2

@@ -26,8 +27,10 @@
  * http://lse.sourceforge.net/locking/rclock_OLS.2001.05.01c.sc.pdf (OLS2001)
  *
  * For detailed explanation of Read-Copy Update mechanism see -
- * 		Documentation/RCU
- *
+ * 	Documentation/RCU
+ * 	http://lwn.net/Articles/262464/ (What is RCU, Fundamentally?)
+ * 	http://lwn.net/Articles/263130/ (What is RCU's Usage?)

Quoted 8 lines

Review line 34

Quoted 2 lines

(quoted diff) +1 -0

+ * 	http://lwn.net/Articles/264090/ (What is RCU's API? + references)
  */

Why put these references here rather than in Documentation/RCU? It seems easier to keep documentation up to date in one place. If you think these represent a good "getting started" set of documents, how about a Documentation/RCU/ReadTheseFirst with links to them, or how about linking to them from whatisRCU.txt?

I actually like in code comments and 'documentation' more than Documentation/ stuff. Mostly because Documentation/ is:
- far away from the code
- therefore, more easily bitrotted
- and easily forgotten

Quoted 20 lines · Peter Zijlstra

Quoted 9 lines · Josh Triplett

Quoted 9 lines

include/linux/rcuclassic.h +3 -2

@@ -26,8 +27,10 @@
  * http://lse.sourceforge.net/locking/rclock_OLS.2001.05.01c.sc.pdf (OLS2001)
  *
  * For detailed explanation of Read-Copy Update mechanism see -
- * 		Documentation/RCU
- *
+ * 	Documentation/RCU
+ * 	http://lwn.net/Articles/262464/ (What is RCU, Fundamentally?)
+ * 	http://lwn.net/Articles/263130/ (What is RCU's Usage?)

Quoted 8 lines

Review line 34

Quoted 2 lines

(quoted diff) +1 -0

+ * 	http://lwn.net/Articles/264090/ (What is RCU's API? + references)
  */

Why put these references here rather than in Documentation/RCU? It seems easier to keep documentation up to date in one place. If you think these represent a good "getting started" set of documents, how about a Documentation/RCU/ReadTheseFirst with links to them, or how about linking to them from whatisRCU.txt?

Quoted 5 lines

I actually like in code comments and 'documentation' more than Documentation/ stuff. Mostly because Documentation/ is:
- far away from the code
- therefore, more easily bitrotted
- and easily forgotten

I know!!!

#ifdef JOSH_TRIPLETT
* Documentation/RCU
* http://lwn.net/Articles/262464/ (What is RCU, Fundamentally?)
* http://lwn.net/Articles/263130/ (What is RCU's Usage?)
* http://lwn.net/Articles/264090/ (What is RCU's API? + references)
#elif PETER_ZIJLSTRA
* Documentation/RCU
#endif

(Sorry, couldn't resist!!!)

Seriously, I know where all the documentation is, as I wrote most of it. These comments are for you guys. So, any thoughts on how I should resolve this? My default is, as always, a coin flip. ;-)

Quoted 38 lines · Paul E. McKenney

Quoted 20 lines · Peter Zijlstra

Quoted 9 lines · Josh Triplett

Quoted 9 lines

include/linux/rcuclassic.h +3 -2

@@ -26,8 +27,10 @@
  * http://lse.sourceforge.net/locking/rclock_OLS.2001.05.01c.sc.pdf (OLS2001)
  *
  * For detailed explanation of Read-Copy Update mechanism see -
- * 		Documentation/RCU
- *
+ * 	Documentation/RCU
+ * 	http://lwn.net/Articles/262464/ (What is RCU, Fundamentally?)
+ * 	http://lwn.net/Articles/263130/ (What is RCU's Usage?)

Quoted 8 lines

Review line 34

Quoted 2 lines

(quoted diff) +1 -0

+ * 	http://lwn.net/Articles/264090/ (What is RCU's API? + references)
  */

Why put these references here rather than in Documentation/RCU? It seems easier to keep documentation up to date in one place. If you think these represent a good "getting started" set of documents, how about a Documentation/RCU/ReadTheseFirst with links to them, or how about linking to them from whatisRCU.txt?

Quoted 5 lines

I actually like in code comments and 'documentation' more than Documentation/ stuff. Mostly because Documentation/ is:
- far away from the code
- therefore, more easily bitrotted
- and easily forgotten

I know!!!

#ifdef JOSH_TRIPLETT
* Documentation/RCU
* http://lwn.net/Articles/262464/ (What is RCU, Fundamentally?)
* http://lwn.net/Articles/263130/ (What is RCU's Usage?)
* http://lwn.net/Articles/264090/ (What is RCU's API? + references)
#elif PETER_ZIJLSTRA
* Documentation/RCU
#endif

Quoted 1 line

(Sorry, couldn't resist!!!)

But but but, you got the cases the wrong way around.. ;-)

Quoted 3 lines

Seriously, I know where all the documentation is, as I wrote most of it. These comments are for you guys. So, any thoughts on how I should resolve this? My default is, as always, a coin flip. ;-)

I guess we could do the 'this is how the concept works and can be used like so and so' documentation in Documentation/

And the stuff that says 'this code does like so and so, because blah' should stay near the code.

And in any case of doubt - stay near the code :-)

I always view Documentation/ as end user stuff (be that a kernel programmer that needs to learn a new API, or userland folks or people wanting to know what a certain feature is about).

kernel/rcuclassic.c +3 -0

+	/*
+	 * Extract the list of ready callbacks, disabling to prevent
+	 * races with call_rcu() from interrupt handlers.

kernel/rcuclassic.c +3 -0

+/*
+ * Do softirq processing for the current CPU.
+ */

Paul E. McKenney wrote:

include/linux/rcuclassic.h line 93

Quoted 9 lines

+ * Definition for node within the RCU grace-period-detection hierarchy.
+ */

include/linux/rcuclassic.h +6 -0

+struct rcu_node {
+	spinlock_t lock;
+	unsigned long	qsmask;	/* CPUs or groups that need to switch in      */
+				/*  order for current grace period to proceed.*/
+	unsigned long	qsmaskinit;
+				/* Per-GP initialization for qsmask.	      */

I'm not sure if a bitmap is the right storage. If I understand the code correctly, it contains two information:
1) If the bitmap is clear, then all cpus have completed whatever they need to do.

A counter is more efficient than a bitmap. Especially: It would allow to choose the optimal fan-out, independent from 32/64 bits.
2) The information if the current cpu must do something to complete the current period.non
This is a local information, usually (always?) only the current cpu needs to know if it must do something.
But this doesn't need to be stored in a shared structure, the information could be stored in a per-cpu structure.

Quoted 4 lines

kernel/rcuclassic.c +3 -0

+	/*
+	 * Extract the list of ready callbacks, disabling to prevent
+	 * races with call_rcu() from interrupt handlers.

kernel/rcuclassic.c static void rcu_check_quiescent_state(struct rcu_ctrlblk *rcp, · line 662

Quoted 10 lines

kernel/rcuclassic.c +10 -0

+	 */
+	local_irq_save(flags);
+	list = rdp->nxtlist;
+	rdp->nxtlist = *rdp->nxttail[RCU_DONE_TAIL];
+	*rdp->nxttail[RCU_DONE_TAIL] = NULL;
+	tail = rdp->nxttail[RCU_DONE_TAIL];
+	for (count = RCU_NEXT_SIZE - 1; count >= 0; count--)
+		if (rdp->nxttail[count] == rdp->nxttail[RCU_DONE_TAIL])
+			rdp->nxttail[count] = &rdp->nxtlist;
+	local_irq_restore(flags);

Do you have a description of the events between call_rcu() and the rcu callback?
Is the following description correct?

__call_rcu() queues in RCU_NEXT_TAIL.
In the middle of the current grace period: rcu_check_quiescent_state() calls rcu_next_callbacks_are_ready().
Entry now in RCU_NEXT_READY_TAIL
** 0.5 cycles: wait until all cpus have completed the current cycle. rcu_process_gp_end() moves from NEXT_READY_TAIL to WAIT_TAIL

** full grace period
rcu_process_gp_end() moves from WAIT_TAIL to DONE_TAIL rcu_do_batch() finds the entries in DONE_TAIL and calls the callback.

Quoted 9 lines

kernel/rcuclassic.c +4 -1

+/*
+ * Do softirq processing for the current CPU.
+ */
 static void rcu_process_callbacks(struct softirq_action *unused)
 {
 	/*
 	 * Memory references from any prior RCU read-side critical sections
-	 * executed by the interrupted code must be see before any RCU
+	 * executed by the interrupted code must be seen before any RCU

kernel/rcuclassic.c static void rcu_check_quiescent_state(struct rcu_ctrlblk *rcp, · line 737

Quoted 4 lines

kernel/rcuclassic.c +0 -0

 	 * grace-period manupulations below.
 	 */
  	smp_mb(); /* See above block comment. */

Why this mb()? There was a grace period between the last read side critical section that might have accessed the pointer.
The rcu internal code already does spin_lock()+spin_unlock(). Isn't that sufficient?

kernel/rcuclassic.c static void rcu_check_quiescent_state(struct rcu_ctrlblk *rcp, · line 740

Quoted 5 lines

- __rcu_process_callbacks(&rcu_ctrlblk, &__get_cpu_var(rcu_data));

kernel/rcuclassic.c +2 -1

-	__rcu_process_callbacks(&rcu_bh_ctrlblk, &__get_cpu_var(rcu_bh_data));
+	__rcu_process_callbacks(&rcu_state, &__get_cpu_var(rcu_data));
+	__rcu_process_callbacks(&rcu_bh_state, &__get_cpu_var(rcu_bh_data));

Have you considered merging RCU_DONE_TAIL for rcu_data and rcu_bh_data?

Quoted 8 lines

kernel/rcuclassic.c +8 -0

+
+/**
+ * call_rcu - Queue an RCU callback for invocation after a grace period.
+ * @head: structure to be used for queueing the RCU updates.
+ * @func: actual update function to be invoked after the grace period
+ *
+ * The update function will be invoked some time after a full grace
+ * period elapses, in other words after all currently executing RCU

Quoted 5 lines

+ * read-side critical sections have completed. RCU read-side critical
+ * sections are delimited by rcu_read_lock() and rcu_read_unlock(),
+ * and may be nested.
+ */

The docbook entry is duplicated: They are in include/linux/rcupdate.h and here.
What about removing one of them?

I would go one step further:
Even add call_rcu_sched() into rcupdate.h. Add a Kconfig bool "RCU_NEEDS_SCHED" and automatically define either the extern or the #define.

Quoted 7 lines

Quoted 7 lines

+ */

include/linux/rcuclassic.h +6 -0

+struct rcu_node {
+	spinlock_t lock;
+	unsigned long	qsmask;	/* CPUs or groups that need to switch in      */
+				/*  order for current grace period to proceed.*/
+	unsigned long	qsmaskinit;
+				/* Per-GP initialization for qsmask.	      */

Quoted 9 lines

Quoted 2 lines

I'm not sure if a bitmap is the right storage. If I understand the code correctly, it contains two information:
1) If the bitmap is clear, then all cpus have completed whatever they need to do.
A counter is more efficient than a bitmap. Especially: It would allow to choose the optimal fan-out, independent from 32/64 bits.
2) The information if the current cpu must do something to complete the current period.non
This is a local information, usually (always?) only the current cpu needs to know if it must do something. But this doesn't need to be stored in a shared structure, the information could be stored in a per-cpu structure.

I am using the bitmap in force_quiescent_state() to work out who to check dynticks and who to send reschedule IPIs to. I could scan all of the per-CPU rcu_data structures, but am assuming that after a few jiffies there would typically be relatively few CPUs still needing to do a quiescent state. Given this assumption, on systems with large numbers of CPUs, scanning the bitmask greatly reduces the number of cache misses compared to scanning the rcu_data structures.

Quoted 21 lines · Paul E. McKenney

Quoted 12 lines

include/linux/rcuclassic.h line 93

Quoted 8 lines

+ */

include/linux/rcuclassic.h +6 -0

+struct rcu_node {
+	spinlock_t lock;
+	unsigned long	qsmask;	/* CPUs or groups that need to switch in      */
+				/*  order for current grace period to proceed.*/
+	unsigned long	qsmaskinit;
+				/* Per-GP initialization for qsmask.	      */

I'm not sure if a bitmap is the right storage. If I understand the code correctly, it contains two information:
1) If the bitmap is clear, then all cpus have completed whatever they need to do.

Quoted 8 lines

A counter is more efficient than a bitmap. Especially: It would allow to choose the optimal fan-out, independent from 32/64 bits.
2) The information if the current cpu must do something to complete the current period.non
This is a local information, usually (always?) only the current cpu needs to know if it must do something.
But this doesn't need to be stored in a shared structure, the information could be stored in a per-cpu structure.

Quoted 8 lines

I am using the bitmap in force_quiescent_state() to work out who to check dynticks and who to send reschedule IPIs to. I could scan all of the per-CPU rcu_data structures, but am assuming that after a few jiffies there would typically be relatively few CPUs still needing to do a quiescent state. Given this assumption, on systems with large numbers of CPUs, scanning the bitmask greatly reduces the number of cache misses compared to scanning the rcu_data structures.

It's an optimization question: What is rarer? force_quiescent_state() or "normal" cpu_quiet calls.
You have optimized for force_quiescent_state(), I have optimized for "normal" cpu_quiet calls. [ok, I admit: force_quiescent_state() is still missing in my code].

Do you have any statistics?

Some shortcomings:

o Entering and leaving dynticks idle mode is a quiescent state,
but the current patch doesn't take advantage of this (noted by Manfred). It appears that it should be possible to make nmi_enter() and nmi_exit() provide an in_nmi(), which would make it possible for rcu_irq_enter() and rcu_irq_exit() to figure out whether it is safe to tell RCU about the quiescent state -- and also greatly simplify the code.

Quoted 9 lines · Paul E. McKenney

Some shortcomings:

o Entering and leaving dynticks idle mode is a quiescent state,
but the current patch doesn't take advantage of this (noted by Manfred). It appears that it should be possible to make nmi_enter() and nmi_exit() provide an in_nmi(), which would make it possible for rcu_irq_enter() and rcu_irq_exit() to figure out whether it is safe to tell RCU about the quiescent state -- and also greatly simplify the code.

Already done and available in the -tip tree, curtesy of Mathieu.

Quoted 12 lines · Peter Zijlstra

Quoted 9 lines · Paul E. McKenney

Some shortcomings:

o Entering and leaving dynticks idle mode is a quiescent state,
but the current patch doesn't take advantage of this (noted by Manfred). It appears that it should be possible to make nmi_enter() and nmi_exit() provide an in_nmi(), which would make it possible for rcu_irq_enter() and rcu_irq_exit() to figure out whether it is safe to tell RCU about the quiescent state -- and also greatly simplify the code.

Quoted 1 line

Already done and available in the -tip tree, curtesy of Mathieu.

Very cool!!! I see one of his patches at http://lkml.org/lkml/2008/4/17/342,
but how do I find out which branch of -tip this is on? (I am learning git, but it is a slow process...)

This would also simplify preemptable RCU's dyntick interface, removing the need for proofs.