[PATCH 0/9] rcu: Cleanup RCU tree initialization

[PATCH 0/9] rcu: Cleanup RCU tree initialization

[Alexander Gordeev]

Hello,

This is an attempt to make RCU tree initialization bit more
clear and optimize memory footprint of data associated with
the tree.

Cc: "Paul E. McKenney" <paulmck@linux.vnet.ibm.com>

Alexander Gordeev (9):
  rcu: Panic if RCU tree can not accommodate all CPUs
  rcu: Remove superfluous local variable in rcu_init_geometry()
  rcu: Cleanup rcu_init_geometry() code and arithmetics
  rcu: Simplify rcu_init_geometry() capacity arithmetics
  rcu: Limit rcu_state::levelcnt[] to RCU_NUM_LVLS items
  rcu: Limit rcu_capacity[] size to RCU_NUM_LVLS items
  rcu: Remove unnecessary fields from rcu_state structure
  rcu: Limit count of static data to the number of RCU levels
  rcu: Simplify arithmetic to calculate number of RCU nodes

 kernel/rcu/tree.c        | 101 +++++++++++++++++++++--------------------------
 kernel/rcu/tree.h        |  32 +++++++--------
 kernel/rcu/tree_plugin.h |   4 +-
 3 files changed, 62 insertions(+), 75 deletions(-)

-- 
1.8.3.1

[PATCH 1/9] rcu: Panic if RCU tree can not accommodate all CPUs

[Alexander Gordeev]

Currently a condition when RCU tree is unable to accommodate
the configured number of CPUs is not permitted and causes
a fall back to compile-time values. However, the code has no
means to exceed the RCU tree capacity neither at compile-time
nor in run-time. Therefore, if the condition is met in run-
time then it indicates a serios problem elsewhere and should
be handled with a panic.

Cc: "Paul E. McKenney" <paulmck@linux.vnet.ibm.com>
Signed-off-by: Alexander Gordeev <agordeev@redhat.com>
---
 kernel/rcu/tree.c | 15 +++++++++------
 1 file changed, 9 insertions(+), 6 deletions(-)

diff --git a/kernel/rcu/tree.c b/kernel/rcu/tree.c
index 48d640c..7588c7f 100644
--- a/kernel/rcu/tree.c
+++ b/kernel/rcu/tree.c
@@ -3889,16 +3889,19 @@ static void __init rcu_init_geometry(void)
 		rcu_capacity[i] = rcu_capacity[i - 1] * CONFIG_RCU_FANOUT;
 
 	/*
+	 * The tree must be able to accommodate the configured number of CPUs.
+	 * If this limit is exceeded than we have a serious problem elsewhere.
+	 *
 	 * The boot-time rcu_fanout_leaf parameter is only permitted
 	 * to increase the leaf-level fanout, not decrease it.  Of course,
 	 * the leaf-level fanout cannot exceed the number of bits in
-	 * the rcu_node masks.  Finally, the tree must be able to accommodate
-	 * the configured number of CPUs.  Complain and fall back to the
-	 * compile-time values if these limits are exceeded.
+	 * the rcu_node masks.  Complain and fall back to the compile-
+	 * time values if these limits are exceeded.
 	 */
-	if (rcu_fanout_leaf < CONFIG_RCU_FANOUT_LEAF ||
-	    rcu_fanout_leaf > sizeof(unsigned long) * 8 ||
-	    n > rcu_capacity[MAX_RCU_LVLS]) {
+	if (n > rcu_capacity[MAX_RCU_LVLS])
+		panic("rcu_init_geometry: rcu_capacity[] is too small");
+	else if (rcu_fanout_leaf < CONFIG_RCU_FANOUT_LEAF ||
+		 rcu_fanout_leaf > sizeof(unsigned long) * 8) {
 		WARN_ON(1);
 		return;
 	}
-- 
1.8.3.1

[PATCH 2/9] rcu: Remove superfluous local variable in rcu_init_geometry()

[Alexander Gordeev]

Local variable 'n' mimics 'nr_cpu_ids' while the both are
used within one function. There is no reason for 'n' to
exist whatsoever.

Cc: "Paul E. McKenney" <paulmck@linux.vnet.ibm.com>
Signed-off-by: Alexander Gordeev <agordeev@redhat.com>
---
 kernel/rcu/tree.c | 14 +++++++-------
 1 file changed, 7 insertions(+), 7 deletions(-)

diff --git a/kernel/rcu/tree.c b/kernel/rcu/tree.c
index 7588c7f..fb89630 100644
--- a/kernel/rcu/tree.c
+++ b/kernel/rcu/tree.c
@@ -3855,7 +3855,6 @@ static void __init rcu_init_geometry(void)
 	ulong d;
 	int i;
 	int j;
-	int n = nr_cpu_ids;
 	int rcu_capacity[MAX_RCU_LVLS + 1];
 
 	/*
@@ -3898,7 +3897,7 @@ static void __init rcu_init_geometry(void)
 	 * the rcu_node masks.  Complain and fall back to the compile-
 	 * time values if these limits are exceeded.
 	 */
-	if (n > rcu_capacity[MAX_RCU_LVLS])
+	if (nr_cpu_ids > rcu_capacity[MAX_RCU_LVLS])
 		panic("rcu_init_geometry: rcu_capacity[] is too small");
 	else if (rcu_fanout_leaf < CONFIG_RCU_FANOUT_LEAF ||
 		 rcu_fanout_leaf > sizeof(unsigned long) * 8) {
@@ -3908,10 +3907,11 @@ static void __init rcu_init_geometry(void)
 
 	/* Calculate the number of rcu_nodes at each level of the tree. */
 	for (i = 1; i <= MAX_RCU_LVLS; i++)
-		if (n <= rcu_capacity[i]) {
-			for (j = 0; j <= i; j++)
-				num_rcu_lvl[j] =
-					DIV_ROUND_UP(n, rcu_capacity[i - j]);
+		if (nr_cpu_ids <= rcu_capacity[i]) {
+			for (j = 0; j <= i; j++) {
+				int cap = rcu_capacity[i - j];
+				num_rcu_lvl[j] = DIV_ROUND_UP(nr_cpu_ids, cap);
+			}
 			rcu_num_lvls = i;
 			for (j = i + 1; j <= MAX_RCU_LVLS; j++)
 				num_rcu_lvl[j] = 0;
@@ -3922,7 +3922,7 @@ static void __init rcu_init_geometry(void)
 	rcu_num_nodes = 0;
 	for (i = 0; i <= MAX_RCU_LVLS; i++)
 		rcu_num_nodes += num_rcu_lvl[i];
-	rcu_num_nodes -= n;
+	rcu_num_nodes -= nr_cpu_ids;
 }
 
 void __init rcu_init(void)
-- 
1.8.3.1

[PATCH 3/9] rcu: Cleanup rcu_init_geometry() code and arithmetics

[Alexander Gordeev]

This update simplifies rcu_init_geometry() code flow
and makes calculation of the total number of rcu_node
structures more easy to read.

The update relies on the fact num_rcu_lvl[] is never
accessed beyond rcu_num_lvls index by the rest of the
code. Therefore, there is no need initialize the whole
num_rcu_lvl[].

Cc: "Paul E. McKenney" <paulmck@linux.vnet.ibm.com>
Signed-off-by: Alexander Gordeev <agordeev@redhat.com>
---
 kernel/rcu/tree.c | 24 ++++++++++--------------
 1 file changed, 10 insertions(+), 14 deletions(-)

diff --git a/kernel/rcu/tree.c b/kernel/rcu/tree.c
index fb89630..f9ef1e0 100644
--- a/kernel/rcu/tree.c
+++ b/kernel/rcu/tree.c
@@ -3854,7 +3854,6 @@ static void __init rcu_init_geometry(void)
 {
 	ulong d;
 	int i;
-	int j;
 	int rcu_capacity[MAX_RCU_LVLS + 1];
 
 	/*
@@ -3905,24 +3904,21 @@ static void __init rcu_init_geometry(void)
 		return;
 	}
 
+	/* Calculate the number of levels in the tree. */
+	for (i = 0; nr_cpu_ids > rcu_capacity[i]; i++) {
+	}
+	rcu_num_lvls = i;
+
 	/* Calculate the number of rcu_nodes at each level of the tree. */
-	for (i = 1; i <= MAX_RCU_LVLS; i++)
-		if (nr_cpu_ids <= rcu_capacity[i]) {
-			for (j = 0; j <= i; j++) {
-				int cap = rcu_capacity[i - j];
-				num_rcu_lvl[j] = DIV_ROUND_UP(nr_cpu_ids, cap);
-			}
-			rcu_num_lvls = i;
-			for (j = i + 1; j <= MAX_RCU_LVLS; j++)
-				num_rcu_lvl[j] = 0;
-			break;
-		}
+	for (i = 0; i < rcu_num_lvls; i++) {
+		int cap = rcu_capacity[rcu_num_lvls - i];
+		num_rcu_lvl[i] = DIV_ROUND_UP(nr_cpu_ids, cap);
+	}
 
 	/* Calculate the total number of rcu_node structures. */
 	rcu_num_nodes = 0;
-	for (i = 0; i <= MAX_RCU_LVLS; i++)
+	for (i = 0; i < rcu_num_lvls; i++)
 		rcu_num_nodes += num_rcu_lvl[i];
-	rcu_num_nodes -= nr_cpu_ids;
 }
 
 void __init rcu_init(void)
-- 
1.8.3.1

[PATCH 4/9] rcu: Simplify rcu_init_geometry() capacity arithmetics

[Alexander Gordeev]

Current code suggests that introducing the extra level to
rcu_capacity[] array makes some of the arithmetic easier.
Well, in fact it appears rather confusing and unnecessary.

Cc: "Paul E. McKenney" <paulmck@linux.vnet.ibm.com>
Signed-off-by: Alexander Gordeev <agordeev@redhat.com>
---
 kernel/rcu/tree.c | 16 +++++++---------
 1 file changed, 7 insertions(+), 9 deletions(-)

diff --git a/kernel/rcu/tree.c b/kernel/rcu/tree.c
index f9ef1e0..eb8b8d7 100644
--- a/kernel/rcu/tree.c
+++ b/kernel/rcu/tree.c
@@ -3854,7 +3854,7 @@ static void __init rcu_init_geometry(void)
 {
 	ulong d;
 	int i;
-	int rcu_capacity[MAX_RCU_LVLS + 1];
+	int rcu_capacity[MAX_RCU_LVLS];
 
 	/*
 	 * Initialize any unspecified boot parameters.
@@ -3878,12 +3878,10 @@ static void __init rcu_init_geometry(void)
 
 	/*
 	 * Compute number of nodes that can be handled an rcu_node tree
-	 * with the given number of levels.  Setting rcu_capacity[0] makes
-	 * some of the arithmetic easier.
+	 * with the given number of levels.
 	 */
-	rcu_capacity[0] = 1;
-	rcu_capacity[1] = rcu_fanout_leaf;
-	for (i = 2; i <= MAX_RCU_LVLS; i++)
+	rcu_capacity[0] = rcu_fanout_leaf;
+	for (i = 1; i < MAX_RCU_LVLS; i++)
 		rcu_capacity[i] = rcu_capacity[i - 1] * CONFIG_RCU_FANOUT;
 
 	/*
@@ -3896,7 +3894,7 @@ static void __init rcu_init_geometry(void)
 	 * the rcu_node masks.  Complain and fall back to the compile-
 	 * time values if these limits are exceeded.
 	 */
-	if (nr_cpu_ids > rcu_capacity[MAX_RCU_LVLS])
+	if (nr_cpu_ids > rcu_capacity[MAX_RCU_LVLS - 1])
 		panic("rcu_init_geometry: rcu_capacity[] is too small");
 	else if (rcu_fanout_leaf < CONFIG_RCU_FANOUT_LEAF ||
 		 rcu_fanout_leaf > sizeof(unsigned long) * 8) {
@@ -3907,11 +3905,11 @@ static void __init rcu_init_geometry(void)
 	/* Calculate the number of levels in the tree. */
 	for (i = 0; nr_cpu_ids > rcu_capacity[i]; i++) {
 	}
-	rcu_num_lvls = i;
+	rcu_num_lvls = i + 1;
 
 	/* Calculate the number of rcu_nodes at each level of the tree. */
 	for (i = 0; i < rcu_num_lvls; i++) {
-		int cap = rcu_capacity[rcu_num_lvls - i];
+		int cap = rcu_capacity[(rcu_num_lvls - 1) - i];
 		num_rcu_lvl[i] = DIV_ROUND_UP(nr_cpu_ids, cap);
 	}
 
-- 
1.8.3.1

[PATCH 5/9] rcu: Limit rcu_state::levelcnt[] to RCU_NUM_LVLS items

[Alexander Gordeev]

Variable rcu_num_lvls is limited by RCU_NUM_LVLS macro.
In turn, rcu_state::levelcnt[] array is never accessed
beyond rcu_num_lvls. Thus, rcu_state::levelcnt[] is safe
to limit to RCU_NUM_LVLS items.

Since rcu_num_lvls could be changed during boot (as result
of rcutree.rcu_fanout_leaf kernel parameter update) one might
assume a new value could overflow the value of RCU_NUM_LVLS.
However, that is not the case, since leaf-level fanout is only
permitted to increase, resulting in rcu_num_lvls possibly to
decrease.

Cc: "Paul E. McKenney" <paulmck@linux.vnet.ibm.com>
Signed-off-by: Alexander Gordeev <agordeev@redhat.com>
---
 kernel/rcu/tree.h | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/kernel/rcu/tree.h b/kernel/rcu/tree.h
index 119de39..b39ab79 100644
--- a/kernel/rcu/tree.h
+++ b/kernel/rcu/tree.h
@@ -415,7 +415,7 @@ do {									\
 struct rcu_state {
 	struct rcu_node node[NUM_RCU_NODES];	/* Hierarchy. */
 	struct rcu_node *level[RCU_NUM_LVLS];	/* Hierarchy levels. */
-	u32 levelcnt[MAX_RCU_LVLS + 1];		/* # nodes in each level. */
+	u32 levelcnt[RCU_NUM_LVLS];		/* # nodes in each level. */
 	u8 levelspread[RCU_NUM_LVLS];		/* kids/node in each level. */
 	u8 flavor_mask;				/* bit in flavor mask. */
 	struct rcu_data __percpu *rda;		/* pointer of percu rcu_data. */
-- 
1.8.3.1

[PATCH 6/9] rcu: Limit rcu_capacity[] size to RCU_NUM_LVLS items

[Alexander Gordeev]

Number of items in rcu_capacity[] array is defined by macro
MAX_RCU_LVLS. However, that array is never accessed beyond
RCU_NUM_LVLS index. Therefore, we can limit the array to
RCU_NUM_LVLS items and eliminate MAX_RCU_LVLS. As result,
in most cases the memory is conserved.

Cc: "Paul E. McKenney" <paulmck@linux.vnet.ibm.com>
Signed-off-by: Alexander Gordeev <agordeev@redhat.com>
---
 kernel/rcu/tree.c | 12 ++++++------
 kernel/rcu/tree.h |  1 -
 2 files changed, 6 insertions(+), 7 deletions(-)

diff --git a/kernel/rcu/tree.c b/kernel/rcu/tree.c
index eb8b8d7..6856096 100644
--- a/kernel/rcu/tree.c
+++ b/kernel/rcu/tree.c
@@ -3769,19 +3769,19 @@ static void __init rcu_init_one(struct rcu_state *rsp,
 		"rcu_node_0",
 		"rcu_node_1",
 		"rcu_node_2",
-		"rcu_node_3" };  /* Match MAX_RCU_LVLS */
+		"rcu_node_3" };
 	static const char * const fqs[] = {
 		"rcu_node_fqs_0",
 		"rcu_node_fqs_1",
 		"rcu_node_fqs_2",
-		"rcu_node_fqs_3" };  /* Match MAX_RCU_LVLS */
+		"rcu_node_fqs_3" };
 	static u8 fl_mask = 0x1;
 	int cpustride = 1;
 	int i;
 	int j;
 	struct rcu_node *rnp;
 
-	BUILD_BUG_ON(MAX_RCU_LVLS > ARRAY_SIZE(buf));  /* Fix buf[] init! */
+	BUILD_BUG_ON(RCU_NUM_LVLS > ARRAY_SIZE(buf));  /* Fix buf[] init! */
 
 	/* Silence gcc 4.8 warning about array index out of range. */
 	if (rcu_num_lvls > RCU_NUM_LVLS)
@@ -3854,7 +3854,7 @@ static void __init rcu_init_geometry(void)
 {
 	ulong d;
 	int i;
-	int rcu_capacity[MAX_RCU_LVLS];
+	int rcu_capacity[RCU_NUM_LVLS];
 
 	/*
 	 * Initialize any unspecified boot parameters.
@@ -3881,7 +3881,7 @@ static void __init rcu_init_geometry(void)
 	 * with the given number of levels.
 	 */
 	rcu_capacity[0] = rcu_fanout_leaf;
-	for (i = 1; i < MAX_RCU_LVLS; i++)
+	for (i = 1; i < RCU_NUM_LVLS; i++)
 		rcu_capacity[i] = rcu_capacity[i - 1] * CONFIG_RCU_FANOUT;
 
 	/*
@@ -3894,7 +3894,7 @@ static void __init rcu_init_geometry(void)
 	 * the rcu_node masks.  Complain and fall back to the compile-
 	 * time values if these limits are exceeded.
 	 */
-	if (nr_cpu_ids > rcu_capacity[MAX_RCU_LVLS - 1])
+	if (nr_cpu_ids > rcu_capacity[RCU_NUM_LVLS - 1])
 		panic("rcu_init_geometry: rcu_capacity[] is too small");
 	else if (rcu_fanout_leaf < CONFIG_RCU_FANOUT_LEAF ||
 		 rcu_fanout_leaf > sizeof(unsigned long) * 8) {
diff --git a/kernel/rcu/tree.h b/kernel/rcu/tree.h
index b39ab79..0f7a469 100644
--- a/kernel/rcu/tree.h
+++ b/kernel/rcu/tree.h
@@ -35,7 +35,6 @@
  * In practice, this did work well going from three levels to four.
  * Of course, your mileage may vary.
  */
-#define MAX_RCU_LVLS 4
 #define RCU_FANOUT_1	      (CONFIG_RCU_FANOUT_LEAF)
 #define RCU_FANOUT_2	      (RCU_FANOUT_1 * CONFIG_RCU_FANOUT)
 #define RCU_FANOUT_3	      (RCU_FANOUT_2 * CONFIG_RCU_FANOUT)
-- 
1.8.3.1

[PATCH 7/9] rcu: Remove unnecessary fields from rcu_state structure

[Alexander Gordeev]

Members rcu_state::levelcnt[] and rcu_state::levelspread[]
are only used at init. There is no reason to keep them
afterwards.

Cc: "Paul E. McKenney" <paulmck@linux.vnet.ibm.com>
Signed-off-by: Alexander Gordeev <agordeev@redhat.com>
---
 kernel/rcu/tree.c | 29 ++++++++++++++++-------------
 kernel/rcu/tree.h |  2 --
 2 files changed, 16 insertions(+), 15 deletions(-)

diff --git a/kernel/rcu/tree.c b/kernel/rcu/tree.c
index 6856096..ccea2c7 100644
--- a/kernel/rcu/tree.c
+++ b/kernel/rcu/tree.c
@@ -3735,16 +3735,16 @@ void rcu_scheduler_starting(void)
  * or balancing the tree, depending on CONFIG_RCU_FANOUT_EXACT.
  */
 #ifdef CONFIG_RCU_FANOUT_EXACT
-static void __init rcu_init_levelspread(struct rcu_state *rsp)
+static void __init rcu_init_levelspread(int *levelspread, const int *levelcnt)
 {
 	int i;
 
-	rsp->levelspread[rcu_num_lvls - 1] = rcu_fanout_leaf;
+	levelspread[rcu_num_lvls - 1] = rcu_fanout_leaf;
 	for (i = rcu_num_lvls - 2; i >= 0; i--)
-		rsp->levelspread[i] = CONFIG_RCU_FANOUT;
+		levelspread[i] = CONFIG_RCU_FANOUT;
 }
 #else /* #ifdef CONFIG_RCU_FANOUT_EXACT */
-static void __init rcu_init_levelspread(struct rcu_state *rsp)
+static void __init rcu_init_levelspread(int *levelspread, const int *levelcnt)
 {
 	int ccur;
 	int cprv;
@@ -3752,8 +3752,8 @@ static void __init rcu_init_levelspread(struct rcu_state *rsp)
 
 	cprv = nr_cpu_ids;
 	for (i = rcu_num_lvls - 1; i >= 0; i--) {
-		ccur = rsp->levelcnt[i];
-		rsp->levelspread[i] = (cprv + ccur - 1) / ccur;
+		ccur = levelcnt[i];
+		levelspread[i] = (cprv + ccur - 1) / ccur;
 		cprv = ccur;
 	}
 }
@@ -3776,6 +3776,9 @@ static void __init rcu_init_one(struct rcu_state *rsp,
 		"rcu_node_fqs_2",
 		"rcu_node_fqs_3" };
 	static u8 fl_mask = 0x1;
+
+	int levelcnt[RCU_NUM_LVLS];		/* # nodes in each level. */
+	int levelspread[RCU_NUM_LVLS];		/* kids/node in each level. */
 	int cpustride = 1;
 	int i;
 	int j;
@@ -3790,19 +3793,19 @@ static void __init rcu_init_one(struct rcu_state *rsp,
 	/* Initialize the level-tracking arrays. */
 
 	for (i = 0; i < rcu_num_lvls; i++)
-		rsp->levelcnt[i] = num_rcu_lvl[i];
+		levelcnt[i] = num_rcu_lvl[i];
 	for (i = 1; i < rcu_num_lvls; i++)
-		rsp->level[i] = rsp->level[i - 1] + rsp->levelcnt[i - 1];
-	rcu_init_levelspread(rsp);
+		rsp->level[i] = rsp->level[i - 1] + levelcnt[i - 1];
+	rcu_init_levelspread(levelspread, levelcnt);
 	rsp->flavor_mask = fl_mask;
 	fl_mask <<= 1;
 
 	/* Initialize the elements themselves, starting from the leaves. */
 
 	for (i = rcu_num_lvls - 1; i >= 0; i--) {
-		cpustride *= rsp->levelspread[i];
+		cpustride *= levelspread[i];
 		rnp = rsp->level[i];
-		for (j = 0; j < rsp->levelcnt[i]; j++, rnp++) {
+		for (j = 0; j < levelcnt[i]; j++, rnp++) {
 			raw_spin_lock_init(&rnp->lock);
 			lockdep_set_class_and_name(&rnp->lock,
 						   &rcu_node_class[i], buf[i]);
@@ -3822,10 +3825,10 @@ static void __init rcu_init_one(struct rcu_state *rsp,
 				rnp->grpmask = 0;
 				rnp->parent = NULL;
 			} else {
-				rnp->grpnum = j % rsp->levelspread[i - 1];
+				rnp->grpnum = j % levelspread[i - 1];
 				rnp->grpmask = 1UL << rnp->grpnum;
 				rnp->parent = rsp->level[i - 1] +
-					      j / rsp->levelspread[i - 1];
+					      j / levelspread[i - 1];
 			}
 			rnp->level = i;
 			INIT_LIST_HEAD(&rnp->blkd_tasks);
diff --git a/kernel/rcu/tree.h b/kernel/rcu/tree.h
index 0f7a469..a3e4714 100644
--- a/kernel/rcu/tree.h
+++ b/kernel/rcu/tree.h
@@ -414,8 +414,6 @@ do {									\
 struct rcu_state {
 	struct rcu_node node[NUM_RCU_NODES];	/* Hierarchy. */
 	struct rcu_node *level[RCU_NUM_LVLS];	/* Hierarchy levels. */
-	u32 levelcnt[RCU_NUM_LVLS];		/* # nodes in each level. */
-	u8 levelspread[RCU_NUM_LVLS];		/* kids/node in each level. */
 	u8 flavor_mask;				/* bit in flavor mask. */
 	struct rcu_data __percpu *rda;		/* pointer of percu rcu_data. */
 	void (*call)(struct rcu_head *head,	/* call_rcu() flavor. */
-- 
1.8.3.1

[PATCH 8/9] rcu: Limit count of static data to the number of RCU levels

[Alexander Gordeev]

Although a number of RCU levels may be less than the current
maximum of four, some static data associated with each level
are allocated for all four levels. As result, the extra data
never get accessed and just wast memory. This update limits
count of allocated items to the number of used RCU levels.

Cc: "Paul E. McKenney" <paulmck@linux.vnet.ibm.com>
Signed-off-by: Alexander Gordeev <agordeev@redhat.com>
---
 kernel/rcu/tree.c | 21 ++++-----------------
 kernel/rcu/tree.h | 12 ++++++++++++
 2 files changed, 16 insertions(+), 17 deletions(-)

diff --git a/kernel/rcu/tree.c b/kernel/rcu/tree.c
index ccea2c7..c085d2c 100644
--- a/kernel/rcu/tree.c
+++ b/kernel/rcu/tree.c
@@ -117,13 +117,8 @@ LIST_HEAD(rcu_struct_flavors);
 static int rcu_fanout_leaf = CONFIG_RCU_FANOUT_LEAF;
 module_param(rcu_fanout_leaf, int, 0444);
 int rcu_num_lvls __read_mostly = RCU_NUM_LVLS;
-static int num_rcu_lvl[] = {  /* Number of rcu_nodes at specified level. */
-	NUM_RCU_LVL_0,
-	NUM_RCU_LVL_1,
-	NUM_RCU_LVL_2,
-	NUM_RCU_LVL_3,
-	NUM_RCU_LVL_4,
-};
+/* Number of rcu_nodes at specified level. */
+static int num_rcu_lvl[] = NUM_RCU_LVL_INIT;
 int rcu_num_nodes __read_mostly = NUM_RCU_NODES; /* Total # rcu_nodes in use. */
 
 /*
@@ -3765,16 +3760,8 @@ static void __init rcu_init_levelspread(int *levelspread, const int *levelcnt)
 static void __init rcu_init_one(struct rcu_state *rsp,
 		struct rcu_data __percpu *rda)
 {
-	static const char * const buf[] = {
-		"rcu_node_0",
-		"rcu_node_1",
-		"rcu_node_2",
-		"rcu_node_3" };
-	static const char * const fqs[] = {
-		"rcu_node_fqs_0",
-		"rcu_node_fqs_1",
-		"rcu_node_fqs_2",
-		"rcu_node_fqs_3" };
+	static const char * const buf[] = RCU_NODE_NAME_INIT;
+	static const char * const fqs[] = RCU_FQS_NAME_INIT;
 	static u8 fl_mask = 0x1;
 
 	int levelcnt[RCU_NUM_LVLS];		/* # nodes in each level. */
diff --git a/kernel/rcu/tree.h b/kernel/rcu/tree.h
index a3e4714..b2414d5 100644
--- a/kernel/rcu/tree.h
+++ b/kernel/rcu/tree.h
@@ -47,6 +47,9 @@
 #  define NUM_RCU_LVL_2	      0
 #  define NUM_RCU_LVL_3	      0
 #  define NUM_RCU_LVL_4	      0
+#  define NUM_RCU_LVL_INIT    { NUM_RCU_LVL_0 }
+#  define RCU_NODE_NAME_INIT  { "rcu_node_0" }
+#  define RCU_FQS_NAME_INIT   { "rcu_node_fqs_0" }
 #elif NR_CPUS <= RCU_FANOUT_2
 #  define RCU_NUM_LVLS	      2
 #  define NUM_RCU_LVL_0	      1
@@ -54,6 +57,9 @@
 #  define NUM_RCU_LVL_2	      (NR_CPUS)
 #  define NUM_RCU_LVL_3	      0
 #  define NUM_RCU_LVL_4	      0
+#  define NUM_RCU_LVL_INIT    { NUM_RCU_LVL_0, NUM_RCU_LVL_1 }
+#  define RCU_NODE_NAME_INIT  { "rcu_node_0", "rcu_node_1" }
+#  define RCU_FQS_NAME_INIT   { "rcu_node_fqs_0", "rcu_node_fqs_1" }
 #elif NR_CPUS <= RCU_FANOUT_3
 #  define RCU_NUM_LVLS	      3
 #  define NUM_RCU_LVL_0	      1
@@ -61,6 +67,9 @@
 #  define NUM_RCU_LVL_2	      DIV_ROUND_UP(NR_CPUS, RCU_FANOUT_1)
 #  define NUM_RCU_LVL_3	      (NR_CPUS)
 #  define NUM_RCU_LVL_4	      0
+#  define NUM_RCU_LVL_INIT    { NUM_RCU_LVL_0, NUM_RCU_LVL_1, NUM_RCU_LVL_2 }
+#  define RCU_NODE_NAME_INIT  { "rcu_node_0", "rcu_node_1", "rcu_node_2" }
+#  define RCU_FQS_NAME_INIT   { "rcu_node_fqs_0", "rcu_node_fqs_1", "rcu_node_fqs_2" }
 #elif NR_CPUS <= RCU_FANOUT_4
 #  define RCU_NUM_LVLS	      4
 #  define NUM_RCU_LVL_0	      1
@@ -68,6 +77,9 @@
 #  define NUM_RCU_LVL_2	      DIV_ROUND_UP(NR_CPUS, RCU_FANOUT_2)
 #  define NUM_RCU_LVL_3	      DIV_ROUND_UP(NR_CPUS, RCU_FANOUT_1)
 #  define NUM_RCU_LVL_4	      (NR_CPUS)
+#  define NUM_RCU_LVL_INIT    { NUM_RCU_LVL_0, NUM_RCU_LVL_1, NUM_RCU_LVL_2, NUM_RCU_LVL_3 }
+#  define RCU_NODE_NAME_INIT  { "rcu_node_0", "rcu_node_1", "rcu_node_2", "rcu_node_3" }
+#  define RCU_FQS_NAME_INIT   { "rcu_node_fqs_0", "rcu_node_fqs_1", "rcu_node_fqs_2", "rcu_node_fqs_3" }
 #else
 # error "CONFIG_RCU_FANOUT insufficient for NR_CPUS"
 #endif /* #if (NR_CPUS) <= RCU_FANOUT_1 */
-- 
1.8.3.1

[PATCH 9/9] rcu: Simplify arithmetic to calculate number of RCU nodes

[Alexander Gordeev]

This update makes arithmetic to calculate number of RCU nodes
more straight and easy to read.

Cc: "Paul E. McKenney" <paulmck@linux.vnet.ibm.com>
Signed-off-by: Alexander Gordeev <agordeev@redhat.com>
---
 kernel/rcu/tree.h        | 17 ++++-------------
 kernel/rcu/tree_plugin.h |  4 ++--
 2 files changed, 6 insertions(+), 15 deletions(-)

diff --git a/kernel/rcu/tree.h b/kernel/rcu/tree.h
index b2414d5..3b5c966 100644
--- a/kernel/rcu/tree.h
+++ b/kernel/rcu/tree.h
@@ -43,10 +43,7 @@
 #if NR_CPUS <= RCU_FANOUT_1
 #  define RCU_NUM_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
-#  define NUM_RCU_LVL_4	      0
+#  define NUM_RCU_NODES	      NUM_RCU_LVL_0
 #  define NUM_RCU_LVL_INIT    { NUM_RCU_LVL_0 }
 #  define RCU_NODE_NAME_INIT  { "rcu_node_0" }
 #  define RCU_FQS_NAME_INIT   { "rcu_node_fqs_0" }
@@ -54,9 +51,7 @@
 #  define RCU_NUM_LVLS	      2
 #  define NUM_RCU_LVL_0	      1
 #  define NUM_RCU_LVL_1	      DIV_ROUND_UP(NR_CPUS, RCU_FANOUT_1)
-#  define NUM_RCU_LVL_2	      (NR_CPUS)
-#  define NUM_RCU_LVL_3	      0
-#  define NUM_RCU_LVL_4	      0
+#  define NUM_RCU_NODES	      (NUM_RCU_LVL_0 + NUM_RCU_LVL_1)
 #  define NUM_RCU_LVL_INIT    { NUM_RCU_LVL_0, NUM_RCU_LVL_1 }
 #  define RCU_NODE_NAME_INIT  { "rcu_node_0", "rcu_node_1" }
 #  define RCU_FQS_NAME_INIT   { "rcu_node_fqs_0", "rcu_node_fqs_1" }
@@ -65,8 +60,7 @@
 #  define NUM_RCU_LVL_0	      1
 #  define NUM_RCU_LVL_1	      DIV_ROUND_UP(NR_CPUS, RCU_FANOUT_2)
 #  define NUM_RCU_LVL_2	      DIV_ROUND_UP(NR_CPUS, RCU_FANOUT_1)
-#  define NUM_RCU_LVL_3	      (NR_CPUS)
-#  define NUM_RCU_LVL_4	      0
+#  define NUM_RCU_NODES	      (NUM_RCU_LVL_0 + NUM_RCU_LVL_1 + NUM_RCU_LVL_2)
 #  define NUM_RCU_LVL_INIT    { NUM_RCU_LVL_0, NUM_RCU_LVL_1, NUM_RCU_LVL_2 }
 #  define RCU_NODE_NAME_INIT  { "rcu_node_0", "rcu_node_1", "rcu_node_2" }
 #  define RCU_FQS_NAME_INIT   { "rcu_node_fqs_0", "rcu_node_fqs_1", "rcu_node_fqs_2" }
@@ -76,7 +70,7 @@
 #  define NUM_RCU_LVL_1	      DIV_ROUND_UP(NR_CPUS, RCU_FANOUT_3)
 #  define NUM_RCU_LVL_2	      DIV_ROUND_UP(NR_CPUS, RCU_FANOUT_2)
 #  define NUM_RCU_LVL_3	      DIV_ROUND_UP(NR_CPUS, RCU_FANOUT_1)
-#  define NUM_RCU_LVL_4	      (NR_CPUS)
+#  define NUM_RCU_NODES	      (NUM_RCU_LVL_0 + NUM_RCU_LVL_1 + NUM_RCU_LVL_2 + NUM_RCU_LVL_3)
 #  define NUM_RCU_LVL_INIT    { NUM_RCU_LVL_0, NUM_RCU_LVL_1, NUM_RCU_LVL_2, NUM_RCU_LVL_3 }
 #  define RCU_NODE_NAME_INIT  { "rcu_node_0", "rcu_node_1", "rcu_node_2", "rcu_node_3" }
 #  define RCU_FQS_NAME_INIT   { "rcu_node_fqs_0", "rcu_node_fqs_1", "rcu_node_fqs_2", "rcu_node_fqs_3" }
@@ -84,9 +78,6 @@
 # error "CONFIG_RCU_FANOUT insufficient for NR_CPUS"
 #endif /* #if (NR_CPUS) <= RCU_FANOUT_1 */
 
-#define RCU_SUM (NUM_RCU_LVL_0 + NUM_RCU_LVL_1 + NUM_RCU_LVL_2 + NUM_RCU_LVL_3 + NUM_RCU_LVL_4)
-#define NUM_RCU_NODES (RCU_SUM - NR_CPUS)
-
 extern int rcu_num_lvls;
 extern int rcu_num_nodes;
 
diff --git a/kernel/rcu/tree_plugin.h b/kernel/rcu/tree_plugin.h
index 0a571e9..65145a8 100644
--- a/kernel/rcu/tree_plugin.h
+++ b/kernel/rcu/tree_plugin.h
@@ -80,8 +80,8 @@ static void __init rcu_bootup_announce_oddness(void)
 #if defined(CONFIG_RCU_CPU_STALL_INFO)
 	pr_info("\tAdditional per-CPU info printed with stalls.\n");
 #endif
-#if NUM_RCU_LVL_4 != 0
-	pr_info("\tFour-level hierarchy is enabled.\n");
+#if RCU_NUM_LVLS >= 4
+	pr_info("\tFour-level (or more) hierarchy is enabled.\n");
 #endif
 	if (rcu_fanout_leaf != CONFIG_RCU_FANOUT_LEAF)
 		pr_info("\tBoot-time adjustment of leaf fanout to %d.\n", rcu_fanout_leaf);
-- 
1.8.3.1

Re: [PATCH 1/9] rcu: Panic if RCU tree can not accommodate all CPUs

[Paul E. McKenney]

On Sat, Mar 07, 2015 at 06:03:36PM +0100, Alexander Gordeev wrote:
> Currently a condition when RCU tree is unable to accommodate
> the configured number of CPUs is not permitted and causes
> a fall back to compile-time values. However, the code has no
> means to exceed the RCU tree capacity neither at compile-time
> nor in run-time. Therefore, if the condition is met in run-
> time then it indicates a serios problem elsewhere and should
> be handled with a panic.
> 
> Cc: "Paul E. McKenney" <paulmck@linux.vnet.ibm.com>
> Signed-off-by: Alexander Gordeev <agordeev@redhat.com>

The place to put a check like this is in the code that calculates
nr_cpu_ids.  And at least some (perhaps all) are set up so that nr_cpu_ids
cannot exceed NR_CPUS, which would render this check redundant.

So I have to say "no" to this one.

							Thanx, Paul

> ---
>  kernel/rcu/tree.c | 15 +++++++++------
>  1 file changed, 9 insertions(+), 6 deletions(-)
> 
> diff --git a/kernel/rcu/tree.c b/kernel/rcu/tree.c
> index 48d640c..7588c7f 100644
> --- a/kernel/rcu/tree.c
> +++ b/kernel/rcu/tree.c
> @@ -3889,16 +3889,19 @@ static void __init rcu_init_geometry(void)
>  		rcu_capacity[i] = rcu_capacity[i - 1] * CONFIG_RCU_FANOUT;
> 
>  	/*
> +	 * The tree must be able to accommodate the configured number of CPUs.
> +	 * If this limit is exceeded than we have a serious problem elsewhere.
> +	 *
>  	 * The boot-time rcu_fanout_leaf parameter is only permitted
>  	 * to increase the leaf-level fanout, not decrease it.  Of course,
>  	 * the leaf-level fanout cannot exceed the number of bits in
> -	 * the rcu_node masks.  Finally, the tree must be able to accommodate
> -	 * the configured number of CPUs.  Complain and fall back to the
> -	 * compile-time values if these limits are exceeded.
> +	 * the rcu_node masks.  Complain and fall back to the compile-
> +	 * time values if these limits are exceeded.
>  	 */
> -	if (rcu_fanout_leaf < CONFIG_RCU_FANOUT_LEAF ||
> -	    rcu_fanout_leaf > sizeof(unsigned long) * 8 ||
> -	    n > rcu_capacity[MAX_RCU_LVLS]) {
> +	if (n > rcu_capacity[MAX_RCU_LVLS])
> +		panic("rcu_init_geometry: rcu_capacity[] is too small");
> +	else if (rcu_fanout_leaf < CONFIG_RCU_FANOUT_LEAF ||
> +		 rcu_fanout_leaf > sizeof(unsigned long) * 8) {
>  		WARN_ON(1);
>  		return;
>  	}
> -- 
> 1.8.3.1
> 

Re: [PATCH 2/9] rcu: Remove superfluous local variable in rcu_init_geometry()

[Paul E. McKenney]

On Sat, Mar 07, 2015 at 06:03:37PM +0100, Alexander Gordeev wrote:
> Local variable 'n' mimics 'nr_cpu_ids' while the both are
> used within one function. There is no reason for 'n' to
> exist whatsoever.
> 
> Cc: "Paul E. McKenney" <paulmck@linux.vnet.ibm.com>
> Signed-off-by: Alexander Gordeev <agordeev@redhat.com>

Good catch!  Could you please port this to branch rcu/next of
git://git.kernel.org/pub/scm/linux/kernel/git/paulmck/linux-rcu.git?

							Thanx, Paul

> ---
>  kernel/rcu/tree.c | 14 +++++++-------
>  1 file changed, 7 insertions(+), 7 deletions(-)
> 
> diff --git a/kernel/rcu/tree.c b/kernel/rcu/tree.c
> index 7588c7f..fb89630 100644
> --- a/kernel/rcu/tree.c
> +++ b/kernel/rcu/tree.c
> @@ -3855,7 +3855,6 @@ static void __init rcu_init_geometry(void)
>  	ulong d;
>  	int i;
>  	int j;
> -	int n = nr_cpu_ids;
>  	int rcu_capacity[MAX_RCU_LVLS + 1];
> 
>  	/*
> @@ -3898,7 +3897,7 @@ static void __init rcu_init_geometry(void)
>  	 * the rcu_node masks.  Complain and fall back to the compile-
>  	 * time values if these limits are exceeded.
>  	 */
> -	if (n > rcu_capacity[MAX_RCU_LVLS])
> +	if (nr_cpu_ids > rcu_capacity[MAX_RCU_LVLS])
>  		panic("rcu_init_geometry: rcu_capacity[] is too small");
>  	else if (rcu_fanout_leaf < CONFIG_RCU_FANOUT_LEAF ||
>  		 rcu_fanout_leaf > sizeof(unsigned long) * 8) {
> @@ -3908,10 +3907,11 @@ static void __init rcu_init_geometry(void)
> 
>  	/* Calculate the number of rcu_nodes at each level of the tree. */
>  	for (i = 1; i <= MAX_RCU_LVLS; i++)
> -		if (n <= rcu_capacity[i]) {
> -			for (j = 0; j <= i; j++)
> -				num_rcu_lvl[j] =
> -					DIV_ROUND_UP(n, rcu_capacity[i - j]);
> +		if (nr_cpu_ids <= rcu_capacity[i]) {
> +			for (j = 0; j <= i; j++) {
> +				int cap = rcu_capacity[i - j];
> +				num_rcu_lvl[j] = DIV_ROUND_UP(nr_cpu_ids, cap);
> +			}
>  			rcu_num_lvls = i;
>  			for (j = i + 1; j <= MAX_RCU_LVLS; j++)
>  				num_rcu_lvl[j] = 0;
> @@ -3922,7 +3922,7 @@ static void __init rcu_init_geometry(void)
>  	rcu_num_nodes = 0;
>  	for (i = 0; i <= MAX_RCU_LVLS; i++)
>  		rcu_num_nodes += num_rcu_lvl[i];
> -	rcu_num_nodes -= n;
> +	rcu_num_nodes -= nr_cpu_ids;
>  }
> 
>  void __init rcu_init(void)
> -- 
> 1.8.3.1
> 

Re: [PATCH 3/9] rcu: Cleanup rcu_init_geometry() code and arithmetics

[Paul E. McKenney]

On Sat, Mar 07, 2015 at 06:03:38PM +0100, Alexander Gordeev wrote:
> This update simplifies rcu_init_geometry() code flow
> and makes calculation of the total number of rcu_node
> structures more easy to read.
> 
> The update relies on the fact num_rcu_lvl[] is never
> accessed beyond rcu_num_lvls index by the rest of the
> code. Therefore, there is no need initialize the whole
> num_rcu_lvl[].
> 
> Cc: "Paul E. McKenney" <paulmck@linux.vnet.ibm.com>
> Signed-off-by: Alexander Gordeev <agordeev@redhat.com>

The rest of this series looks promising, but I do have to ask...  How have
you tested these?  The most straightforward approach would be to find
a KVM-capable system with at least 16 CPUs and type the following from
the top-level directory:

sh tools/testing/selftests/rcutorture/bin/kvm.sh --cpus 34 --duration 5

This will do a series of 16 build-boot-test cycles with various configs
(including various rcu_node tree shapes), and print a summary of the
outcome at the end.

For these sorts of changes, I usually also do some user-level testing.

							Thanx, Paul

> ---
>  kernel/rcu/tree.c | 24 ++++++++++--------------
>  1 file changed, 10 insertions(+), 14 deletions(-)
> 
> diff --git a/kernel/rcu/tree.c b/kernel/rcu/tree.c
> index fb89630..f9ef1e0 100644
> --- a/kernel/rcu/tree.c
> +++ b/kernel/rcu/tree.c
> @@ -3854,7 +3854,6 @@ static void __init rcu_init_geometry(void)
>  {
>  	ulong d;
>  	int i;
> -	int j;
>  	int rcu_capacity[MAX_RCU_LVLS + 1];
> 
>  	/*
> @@ -3905,24 +3904,21 @@ static void __init rcu_init_geometry(void)
>  		return;
>  	}
> 
> +	/* Calculate the number of levels in the tree. */
> +	for (i = 0; nr_cpu_ids > rcu_capacity[i]; i++) {
> +	}
> +	rcu_num_lvls = i;
> +
>  	/* Calculate the number of rcu_nodes at each level of the tree. */
> -	for (i = 1; i <= MAX_RCU_LVLS; i++)
> -		if (nr_cpu_ids <= rcu_capacity[i]) {
> -			for (j = 0; j <= i; j++) {
> -				int cap = rcu_capacity[i - j];
> -				num_rcu_lvl[j] = DIV_ROUND_UP(nr_cpu_ids, cap);
> -			}
> -			rcu_num_lvls = i;
> -			for (j = i + 1; j <= MAX_RCU_LVLS; j++)
> -				num_rcu_lvl[j] = 0;
> -			break;
> -		}
> +	for (i = 0; i < rcu_num_lvls; i++) {
> +		int cap = rcu_capacity[rcu_num_lvls - i];
> +		num_rcu_lvl[i] = DIV_ROUND_UP(nr_cpu_ids, cap);
> +	}
> 
>  	/* Calculate the total number of rcu_node structures. */
>  	rcu_num_nodes = 0;
> -	for (i = 0; i <= MAX_RCU_LVLS; i++)
> +	for (i = 0; i < rcu_num_lvls; i++)
>  		rcu_num_nodes += num_rcu_lvl[i];
> -	rcu_num_nodes -= nr_cpu_ids;
>  }
> 
>  void __init rcu_init(void)
> -- 
> 1.8.3.1
> 

Re: [PATCH 1/9] rcu: Panic if RCU tree can not accommodate all CPUs

[Alexander Gordeev]

On Sat, Mar 07, 2015 at 09:42:34AM -0800, Paul E. McKenney wrote:
> On Sat, Mar 07, 2015 at 06:03:36PM +0100, Alexander Gordeev wrote:
> > Currently a condition when RCU tree is unable to accommodate
> > the configured number of CPUs is not permitted and causes
> > a fall back to compile-time values. However, the code has no
> > means to exceed the RCU tree capacity neither at compile-time
> > nor in run-time. Therefore, if the condition is met in run-
> > time then it indicates a serios problem elsewhere and should
> > be handled with a panic.
> > 
> > Cc: "Paul E. McKenney" <paulmck@linux.vnet.ibm.com>
> > Signed-off-by: Alexander Gordeev <agordeev@redhat.com>
> 
> The place to put a check like this is in the code that calculates
> nr_cpu_ids.  And at least some (perhaps all) are set up so that nr_cpu_ids
> cannot exceed NR_CPUS, which would render this check redundant.

The emphasis here the existing check (... n > rcu_capacity[MAX_RCU_LVLS])
(below as [1]) should not cause the fall back to compiled-time values.
It either must panic or, as you say - redundant.

> So I have to say "no" to this one.
> 
> 							Thanx, Paul
> 
> > ---
> >  kernel/rcu/tree.c | 15 +++++++++------
> >  1 file changed, 9 insertions(+), 6 deletions(-)
> > 
> > diff --git a/kernel/rcu/tree.c b/kernel/rcu/tree.c
> > index 48d640c..7588c7f 100644
> > --- a/kernel/rcu/tree.c
> > +++ b/kernel/rcu/tree.c
> > @@ -3889,16 +3889,19 @@ static void __init rcu_init_geometry(void)
> >  		rcu_capacity[i] = rcu_capacity[i - 1] * CONFIG_RCU_FANOUT;
> > 
> >  	/*
> > +	 * The tree must be able to accommodate the configured number of CPUs.
> > +	 * If this limit is exceeded than we have a serious problem elsewhere.
> > +	 *
> >  	 * The boot-time rcu_fanout_leaf parameter is only permitted
> >  	 * to increase the leaf-level fanout, not decrease it.  Of course,
> >  	 * the leaf-level fanout cannot exceed the number of bits in
> > -	 * the rcu_node masks.  Finally, the tree must be able to accommodate
> > -	 * the configured number of CPUs.  Complain and fall back to the
> > -	 * compile-time values if these limits are exceeded.
> > +	 * the rcu_node masks.  Complain and fall back to the compile-
> > +	 * time values if these limits are exceeded.
> >  	 */
> > -	if (rcu_fanout_leaf < CONFIG_RCU_FANOUT_LEAF ||
> > -	    rcu_fanout_leaf > sizeof(unsigned long) * 8 ||
> > -	    n > rcu_capacity[MAX_RCU_LVLS]) {

            [1]

> > +	if (n > rcu_capacity[MAX_RCU_LVLS])
> > +		panic("rcu_init_geometry: rcu_capacity[] is too small");
> > +	else if (rcu_fanout_leaf < CONFIG_RCU_FANOUT_LEAF ||
> > +		 rcu_fanout_leaf > sizeof(unsigned long) * 8) {
> >  		WARN_ON(1);
> >  		return;
> >  	}
> > -- 
> > 1.8.3.1
> > 
> 

-- 
Regards,
Alexander Gordeev
agordeev@redhat.com

Re: [PATCH 3/9] rcu: Cleanup rcu_init_geometry() code and arithmetics

[Alexander Gordeev]

On Sat, Mar 07, 2015 at 10:08:21AM -0800, Paul E. McKenney wrote:
> The rest of this series looks promising, but I do have to ask...  How have
> you tested these?  The most straightforward approach would be to find

I tried trees with 1,2 and 3 levels on a 160-CPU machine + dozens of kernel
builds with 'make -j160'. I feel bit guilty I did not try the corner case
with 4 levels, but run-time-wise it is not really differ from what I done.

Do you expect the below is a better option?

> a KVM-capable system with at least 16 CPUs and type the following from
> the top-level directory:
> 
> sh tools/testing/selftests/rcutorture/bin/kvm.sh --cpus 34 --duration 5
> 
> This will do a series of 16 build-boot-test cycles with various configs
> (including various rcu_node tree shapes), and print a summary of the
> outcome at the end.
> 
> For these sorts of changes, I usually also do some user-level testing.


-- 
Regards,
Alexander Gordeev
agordeev@redhat.com

Re: [PATCH 3/9] rcu: Cleanup rcu_init_geometry() code and arithmetics

[Paul E. McKenney]

On Sat, Mar 07, 2015 at 06:59:54PM +0000, Alexander Gordeev wrote:
> On Sat, Mar 07, 2015 at 10:08:21AM -0800, Paul E. McKenney wrote:
> > The rest of this series looks promising, but I do have to ask...  How have
> > you tested these?  The most straightforward approach would be to find
> 
> I tried trees with 1,2 and 3 levels on a 160-CPU machine + dozens of kernel
> builds with 'make -j160'. I feel bit guilty I did not try the corner case
> with 4 levels, but run-time-wise it is not really differ from what I done.
> 
> Do you expect the below is a better option?

What you did is not bad, actually.  You can get four levels by building
with both CONFIG_RCU_FANOUT and CONFIG_RCU_FANOUT_LEAF equal to five,
and that will also test non-power-of-two choices.  You do that, and I
will give your series a shot.

What I need to do is to create a user-level test that does the full
exhaustive test, varying:

o	NR_CPUS from 1 to 4096
o	nr_cpu_ids from 1 to NR_CPUS
o	CONFIG_RCU_FANOUT from 2 to 64
o	CONFIG_RCU_FANOUT_LEAF from 2 to 64
o	CONFIG_RCU_FANOUT_EXACT from n to y

Unfortunately, if each test case took one millisecond, this would take
two years.  Not so good when a new version of Linux comes out every
couple of months.  Of course, this could be paralellized, but still...

So I should focus on the values actually used, especially for NR_CPUS:

o	NR_CPUS from 1 to 4096 by powers of two, for 13 combinations
o	nr_cpu_ids from 1 to NR_CPUS
o	CONFIG_RCU_FANOUT of 32 or 64
o	CONFIG_RCU_FANOUT_LEAF of 16, 32, or 64
o	CONFIG_RCU_FANOUT_EXACT of n or y

This is 268,435,452 test cases, which is about tree days at one
millisecond per case.  (My current single-use manual-inspection test
takes eight milliseconds, but then again it is printing out tons of
stuff.)  But I do need to add at least a few oddball values -- there
was a bug for some years that happened only with CONFIG_RCU_FANOUT and
CONFIG_RCU_FANOUT_LEAF not dividing evenly.

Or maybe I can use cbmc and make things faster.

Anyway, again, if you do the test with CONFIG_RCU_FANOUT and
CONFIG_RCU_FANOUT_LEAF equal to five, this user-level testing is my
problem rather than yours.

							Thanx, Paul

> > a KVM-capable system with at least 16 CPUs and type the following from
> > the top-level directory:
> > 
> > sh tools/testing/selftests/rcutorture/bin/kvm.sh --cpus 34 --duration 5
> > 
> > This will do a series of 16 build-boot-test cycles with various configs
> > (including various rcu_node tree shapes), and print a summary of the
> > outcome at the end.
> > 
> > For these sorts of changes, I usually also do some user-level testing.
> 
> 
> -- 
> Regards,
> Alexander Gordeev
> agordeev@redhat.com
> 

Re: [PATCH 1/9] rcu: Panic if RCU tree can not accommodate all CPUs

[Paul E. McKenney]

On Sat, Mar 07, 2015 at 06:48:21PM +0000, Alexander Gordeev wrote:
> On Sat, Mar 07, 2015 at 09:42:34AM -0800, Paul E. McKenney wrote:
> > On Sat, Mar 07, 2015 at 06:03:36PM +0100, Alexander Gordeev wrote:
> > > Currently a condition when RCU tree is unable to accommodate
> > > the configured number of CPUs is not permitted and causes
> > > a fall back to compile-time values. However, the code has no
> > > means to exceed the RCU tree capacity neither at compile-time
> > > nor in run-time. Therefore, if the condition is met in run-
> > > time then it indicates a serios problem elsewhere and should
> > > be handled with a panic.
> > > 
> > > Cc: "Paul E. McKenney" <paulmck@linux.vnet.ibm.com>
> > > Signed-off-by: Alexander Gordeev <agordeev@redhat.com>
> > 
> > The place to put a check like this is in the code that calculates
> > nr_cpu_ids.  And at least some (perhaps all) are set up so that nr_cpu_ids
> > cannot exceed NR_CPUS, which would render this check redundant.
> 
> The emphasis here the existing check (... n > rcu_capacity[MAX_RCU_LVLS])
> (below as [1]) should not cause the fall back to compiled-time values.
> It either must panic or, as you say - redundant.

You are right, I responded too early on a Saturday.  The point of the
check below is indeed to verify that RCU's calculations are correct.

So do the testing with CONFIG_RCU_FANOUT and CONFIG_RCU_FANOUT_LEAF both
equal to five, and rebase to the rcu/next branch of:

git://git.kernel.org/pub/scm/linux/kernel/git/paulmck/linux-rcu.git

And I will give them a spin.

							Thanx, Paul

> > So I have to say "no" to this one.
> > 
> > 							Thanx, Paul
> > 
> > > ---
> > >  kernel/rcu/tree.c | 15 +++++++++------
> > >  1 file changed, 9 insertions(+), 6 deletions(-)
> > > 
> > > diff --git a/kernel/rcu/tree.c b/kernel/rcu/tree.c
> > > index 48d640c..7588c7f 100644
> > > --- a/kernel/rcu/tree.c
> > > +++ b/kernel/rcu/tree.c
> > > @@ -3889,16 +3889,19 @@ static void __init rcu_init_geometry(void)
> > >  		rcu_capacity[i] = rcu_capacity[i - 1] * CONFIG_RCU_FANOUT;
> > > 
> > >  	/*
> > > +	 * The tree must be able to accommodate the configured number of CPUs.
> > > +	 * If this limit is exceeded than we have a serious problem elsewhere.
> > > +	 *
> > >  	 * The boot-time rcu_fanout_leaf parameter is only permitted
> > >  	 * to increase the leaf-level fanout, not decrease it.  Of course,
> > >  	 * the leaf-level fanout cannot exceed the number of bits in
> > > -	 * the rcu_node masks.  Finally, the tree must be able to accommodate
> > > -	 * the configured number of CPUs.  Complain and fall back to the
> > > -	 * compile-time values if these limits are exceeded.
> > > +	 * the rcu_node masks.  Complain and fall back to the compile-
> > > +	 * time values if these limits are exceeded.
> > >  	 */
> > > -	if (rcu_fanout_leaf < CONFIG_RCU_FANOUT_LEAF ||
> > > -	    rcu_fanout_leaf > sizeof(unsigned long) * 8 ||
> > > -	    n > rcu_capacity[MAX_RCU_LVLS]) {
> 
>             [1]
> 
> > > +	if (n > rcu_capacity[MAX_RCU_LVLS])
> > > +		panic("rcu_init_geometry: rcu_capacity[] is too small");
> > > +	else if (rcu_fanout_leaf < CONFIG_RCU_FANOUT_LEAF ||
> > > +		 rcu_fanout_leaf > sizeof(unsigned long) * 8) {
> > >  		WARN_ON(1);
> > >  		return;
> > >  	}
> > > -- 
> > > 1.8.3.1
> > > 
> > 
> 
> -- 
> Regards,
> Alexander Gordeev
> agordeev@redhat.com
>