[PATCH 00/10] rcu: Cleanup RCU tree initialization

[PATCH 00/10] rcu: Cleanup RCU tree initialization

[Alexander Gordeev]

Hi Paul,

Here is cleanup of RCU tree initialization rebased on linux-rcu rcu/next
repo, as you requested. Please, note an extra patch #10 that was not
present in the first post.

The series successfully passes kernel build test with CONFIG_RCU_FANOUT
and CONFIG_RCU_FANOUT_LEAF equal to 5.

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


Alexander Gordeev (10):
  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
  rcu: Remove unnecessary grpnum field from rcu_node structure

 kernel/rcu/tree.c        | 102 ++++++++++++++++++++---------------------------
 kernel/rcu/tree.h        |  35 ++++++++--------
 kernel/rcu/tree_plugin.h |   4 +-
 3 files changed, 63 insertions(+), 78 deletions(-)

-- 
1.8.3.1

[PATCH 01/10] 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 cc2e9be..9308ec9 100644
--- a/kernel/rcu/tree.c
+++ b/kernel/rcu/tree.c
@@ -4043,16 +4043,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 02/10] 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 9308ec9..4045163 100644
--- a/kernel/rcu/tree.c
+++ b/kernel/rcu/tree.c
@@ -4009,7 +4009,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];
 
 	/*
@@ -4052,7 +4051,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) {
@@ -4062,10 +4061,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;
@@ -4076,7 +4076,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 03/10] 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 4045163..c7ad0a9 100644
--- a/kernel/rcu/tree.c
+++ b/kernel/rcu/tree.c
@@ -4008,7 +4008,6 @@ static void __init rcu_init_geometry(void)
 {
 	ulong d;
 	int i;
-	int j;
 	int rcu_capacity[MAX_RCU_LVLS + 1];
 
 	/*
@@ -4059,24 +4058,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 04/10] 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 c7ad0a9..98e36c3 100644
--- a/kernel/rcu/tree.c
+++ b/kernel/rcu/tree.c
@@ -4008,7 +4008,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.
@@ -4032,12 +4032,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;
 
 	/*
@@ -4050,7 +4048,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) {
@@ -4061,11 +4059,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 05/10] 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 dd5ce40..f358a83 100644
--- a/kernel/rcu/tree.h
+++ b/kernel/rcu/tree.h
@@ -421,7 +421,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 06/10] 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 98e36c3..dbcec66 100644
--- a/kernel/rcu/tree.c
+++ b/kernel/rcu/tree.c
@@ -3924,19 +3924,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)
@@ -4008,7 +4008,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.
@@ -4035,7 +4035,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;
 
 	/*
@@ -4048,7 +4048,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 f358a83..661d2d4 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 07/10] 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 | 27 +++++++++++++++------------
 kernel/rcu/tree.h |  2 --
 2 files changed, 15 insertions(+), 14 deletions(-)

diff --git a/kernel/rcu/tree.c b/kernel/rcu/tree.c
index dbcec66..cde1323 100644
--- a/kernel/rcu/tree.c
+++ b/kernel/rcu/tree.c
@@ -3893,22 +3893,22 @@ void rcu_scheduler_starting(void)
  * Compute the per-level fanout, either using the exact fanout specified
  * or balancing the tree, depending on 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;
 
 	if (IS_ENABLED(CONFIG_RCU_FANOUT_EXACT)) {
-		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 {
 		int ccur;
 		int cprv;
 
 		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;
 		}
 	}
@@ -3931,6 +3931,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;
@@ -3945,19 +3948,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]);
@@ -3977,10 +3980,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 661d2d4..55886d2 100644
--- a/kernel/rcu/tree.h
+++ b/kernel/rcu/tree.h
@@ -420,8 +420,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 08/10] 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 cde1323..1cc1286 100644
--- a/kernel/rcu/tree.c
+++ b/kernel/rcu/tree.c
@@ -118,13 +118,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. */
 
 /*
@@ -3920,16 +3915,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 55886d2..cdb98e5 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 09/10] 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 cdb98e5..f12fe83 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 2549f4b..cf1410f 100644
--- a/kernel/rcu/tree_plugin.h
+++ b/kernel/rcu/tree_plugin.h
@@ -84,8 +84,8 @@ static void __init rcu_bootup_announce_oddness(void)
 		pr_info("\tRCU torture testing starts during boot.\n");
 	if (IS_ENABLED(CONFIG_RCU_CPU_STALL_INFO))
 		pr_info("\tAdditional per-CPU info printed with stalls.\n");
-	if (NUM_RCU_LVL_4 != 0)
-		pr_info("\tFour-level hierarchy is enabled.\n");
+	if (RCU_NUM_LVLS >= 4)
+		pr_info("\tFour(or more)-level hierarchy is enabled.\n");
 	if (CONFIG_RCU_FANOUT_LEAF != 16)
 		pr_info("\tBuild-time adjustment of leaf fanout to %d.\n",
 			CONFIG_RCU_FANOUT_LEAF);
-- 
1.8.3.1

[PATCH 10/10] rcu: Remove unnecessary grpnum field from rcu_node structure

[Alexander Gordeev]

Field rcu_node::grpnum is used to set rcu_node::grpmask at init
and never accessed afterwards. There is no reason to have it.

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

diff --git a/kernel/rcu/tree.c b/kernel/rcu/tree.c
index 1cc1286..6afcf8f 100644
--- a/kernel/rcu/tree.c
+++ b/kernel/rcu/tree.c
@@ -3963,12 +3963,11 @@ static void __init rcu_init_one(struct rcu_state *rsp,
 			if (rnp->grphi >= nr_cpu_ids)
 				rnp->grphi = nr_cpu_ids - 1;
 			if (i == 0) {
-				rnp->grpnum = 0;
 				rnp->grpmask = 0;
 				rnp->parent = NULL;
 			} else {
-				rnp->grpnum = j % levelspread[i - 1];
-				rnp->grpmask = 1UL << rnp->grpnum;
+				int grpnum = j % levelspread[i - 1];
+				rnp->grpmask = 1UL << grpnum;
 				rnp->parent = rsp->level[i - 1] +
 					      j / levelspread[i - 1];
 			}
diff --git a/kernel/rcu/tree.h b/kernel/rcu/tree.h
index f12fe83..bd66e85 100644
--- a/kernel/rcu/tree.h
+++ b/kernel/rcu/tree.h
@@ -151,8 +151,7 @@ struct rcu_node {
 				/*  Only one bit will be set in this mask. */
 	int	grplo;		/* lowest-numbered CPU or group here. */
 	int	grphi;		/* highest-numbered CPU or group here. */
-	u8	grpnum;		/* CPU/group number for next level up. */
-	u8	level;		/* root is at level 0. */
+	int	level;		/* root is at level 0. */
 	bool	wait_blkd_tasks;/* Necessary to wait for blocked tasks to */
 				/*  exit RCU read-side critical sections */
 				/*  before propagating offline up the */
-- 
1.8.3.1

Re: [PATCH 00/10] rcu: Cleanup RCU tree initialization

[Alexander Gordeev]

On Mon, Mar 09, 2015 at 09:34:04AM +0100, Alexander Gordeev wrote:
> Hi Paul,
> 
> Here is cleanup of RCU tree initialization rebased on linux-rcu rcu/next
> repo, as you requested. Please, note an extra patch #10 that was not
> present in the first post.

Paul,

Please, ignore patch #10 for now. I missed to notice rcu_node::grpnum is
used in tracing, so the patch is incomplete. I am not sure why trailing
spaces in seq_printf(m, "%lx/%lx->%lx %c%c>%c %d:%d ^%d    ", ....) are
needed for, so not sure if "^%d" part should be removed (possibly with
the traling spaces) or replaced with three spaces.

Thanks!

-- 
Regards,
Alexander Gordeev
agordeev@redhat.com

Re: [PATCH 00/10] rcu: Cleanup RCU tree initialization

[Paul E. McKenney]

On Mon, Mar 09, 2015 at 09:36:52AM +0000, Alexander Gordeev wrote:
> On Mon, Mar 09, 2015 at 09:34:04AM +0100, Alexander Gordeev wrote:
> > Hi Paul,
> > 
> > Here is cleanup of RCU tree initialization rebased on linux-rcu rcu/next
> > repo, as you requested. Please, note an extra patch #10 that was not
> > present in the first post.
> 
> Paul,
> 
> Please, ignore patch #10 for now. I missed to notice rcu_node::grpnum is
> used in tracing, so the patch is incomplete. I am not sure why trailing
> spaces in seq_printf(m, "%lx/%lx->%lx %c%c>%c %d:%d ^%d    ", ....) are
> needed for, so not sure if "^%d" part should be removed (possibly with
> the traling spaces) or replaced with three spaces.

OK, dropping this one for the moment.

The original use of ->grpnum was for manual debugging purposes.  Yes, you
can get the same information out of ->grpmask, but the number is easier
to read.  And on the debugfs trace information, ->grpnum is printed,
but ->grpmask is not.

The trailing spaces on the seq_printf() allow the rcu_node data to be
printed on a single line, while still allowing the eye to pick out
where one rcu_node structure's data ends and the next one begins.

So here are the choices, as far as I can see:

1.	Leave ->grpnum as is.

2.	Remove ->grpnum, but regenerate it in print_one_rcu_state(),
	for example, by counting the number of rcu_node structures
	since the last ->level change.

3.	Drop ->grpnum and also remove it from the debugfs tracing.
	The reader can rely on the ->grplo and ->grphi fields to
	work out where this rcu_node structure fits in, but we
	lose the visual indication of any bugs in computing these
	quantities.

4.	Drop ->grpnum and replace it with ->grpmask.  This seems a
	bit obtuse to me.

5.	Redesign print_one_rcu_state()'s output from scratch.

#1 has certain advantages from a laziness viewpoint.  #2 would open up
some space in the rcu_node structure, but space really isn't an issue
for that structure given that huge systems have only 257 of them and
the really small systems use Tiny RCU instead.  #3 might be OK, but I
am not really convinced.  #4 seems a bit ugly.  I am not signing up
for #5, in part because not all that many people use RCU's debugfs
output, so I don't see the point in investing the time.

But what did you have in mind?

							Thanx, Paul

Re: [PATCH 00/10] rcu: Cleanup RCU tree initialization

[Paul E. McKenney]

On Mon, Mar 09, 2015 at 09:34:04AM +0100, Alexander Gordeev wrote:
> Hi Paul,
> 
> Here is cleanup of RCU tree initialization rebased on linux-rcu rcu/next
> repo, as you requested. Please, note an extra patch #10 that was not
> present in the first post.
> 
> The series successfully passes kernel build test with CONFIG_RCU_FANOUT
> and CONFIG_RCU_FANOUT_LEAF equal to 5.

I queued up 1-9, as discussed and have started testing.  I will let you
know how it goes.

							Thanx, Paul

> Cc: "Paul E. McKenney" <paulmck@linux.vnet.ibm.com>
> 
> 
> Alexander Gordeev (10):
>   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
>   rcu: Remove unnecessary grpnum field from rcu_node structure
> 
>  kernel/rcu/tree.c        | 102 ++++++++++++++++++++---------------------------
>  kernel/rcu/tree.h        |  35 ++++++++--------
>  kernel/rcu/tree_plugin.h |   4 +-
>  3 files changed, 63 insertions(+), 78 deletions(-)
> 
> -- 
> 1.8.3.1
> 

Re: [PATCH 00/10] rcu: Cleanup RCU tree initialization

[Paul E. McKenney]

On Mon, Mar 09, 2015 at 02:40:21PM -0700, Paul E. McKenney wrote:
> On Mon, Mar 09, 2015 at 09:34:04AM +0100, Alexander Gordeev wrote:
> > Hi Paul,
> > 
> > Here is cleanup of RCU tree initialization rebased on linux-rcu rcu/next
> > repo, as you requested. Please, note an extra patch #10 that was not
> > present in the first post.
> > 
> > The series successfully passes kernel build test with CONFIG_RCU_FANOUT
> > and CONFIG_RCU_FANOUT_LEAF equal to 5.
> 
> I queued up 1-9, as discussed and have started testing.  I will let you
> know how it goes.

Initial testing went well except for the following warning:

/home/paulmck/public_git/linux-rcu/kernel/rcu/tree.c: In function ‘rcu_init_one.isra.63’:
/home/paulmck/public_git/linux-rcu/kernel/rcu/tree.c:3961:3: warning: ‘levelcnt[0]’ may be used uninitialized in this function [-Wmaybe-uninitialized]
   for (j = 0; j < levelcnt[i]; j++, rnp++) {

This warning looks like a false positive to me, given that the loop
near the beginning of the function initializes levelcnt[0].  Am I
missing something here, and either way, what is the best way to shut
this warning up?

I am using gcc version 4.8.2.

This warning only appears for some configurations.
SRCU-N:  Four CPUs, single rcu_node structure.
SRCU-P:  Eight CPUs, single rcu_node structure.
TASKS01: Two CPUs, single rcu_node structure.
TASKS03: Two CPUs, single rcu_node structure.
TREE09:  Single CPU, single rcu_node structure.

All the other TREE0N configurations have multiple rcu_node structures.

TASKS02 didn't warn either despite having only one CPU, but that is
because it uses Tiny RCU instead of Tree RCU.

So this warning shows up only in the case where the compiler knows
that the rcu_node tree consists of only one rcu_node structure.

							Thanx, Paul

> > Cc: "Paul E. McKenney" <paulmck@linux.vnet.ibm.com>
> > 
> > 
> > Alexander Gordeev (10):
> >   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
> >   rcu: Remove unnecessary grpnum field from rcu_node structure
> > 
> >  kernel/rcu/tree.c        | 102 ++++++++++++++++++++---------------------------
> >  kernel/rcu/tree.h        |  35 ++++++++--------
> >  kernel/rcu/tree_plugin.h |   4 +-
> >  3 files changed, 63 insertions(+), 78 deletions(-)
> > 
> > -- 
> > 1.8.3.1
> > 

Re: [PATCH 00/10] rcu: Cleanup RCU tree initialization

[Paul E. McKenney]

On Mon, Mar 09, 2015 at 04:39:47PM -0700, Paul E. McKenney wrote:
> On Mon, Mar 09, 2015 at 02:40:21PM -0700, Paul E. McKenney wrote:
> > On Mon, Mar 09, 2015 at 09:34:04AM +0100, Alexander Gordeev wrote:
> > > Hi Paul,
> > > 
> > > Here is cleanup of RCU tree initialization rebased on linux-rcu rcu/next
> > > repo, as you requested. Please, note an extra patch #10 that was not
> > > present in the first post.
> > > 
> > > The series successfully passes kernel build test with CONFIG_RCU_FANOUT
> > > and CONFIG_RCU_FANOUT_LEAF equal to 5.
> > 
> > I queued up 1-9, as discussed and have started testing.  I will let you
> > know how it goes.
> 
> Initial testing went well except for the following warning:
> 
> /home/paulmck/public_git/linux-rcu/kernel/rcu/tree.c: In function ‘rcu_init_one.isra.63’:
> /home/paulmck/public_git/linux-rcu/kernel/rcu/tree.c:3961:3: warning: ‘levelcnt[0]’ may be used uninitialized in this function [-Wmaybe-uninitialized]
>    for (j = 0; j < levelcnt[i]; j++, rnp++) {
> 
> This warning looks like a false positive to me, given that the loop
> near the beginning of the function initializes levelcnt[0].  Am I
> missing something here, and either way, what is the best way to shut
> this warning up?

My suggestion is the following:

	if (rcu_num_lvls <= 0)
		panic("rcu_init_one: rcu_num_lvls underflow");

Just following the other panic() in rcu_init_one().

							Thanx, Paul

> I am using gcc version 4.8.2.
> 
> This warning only appears for some configurations.
> SRCU-N:  Four CPUs, single rcu_node structure.
> SRCU-P:  Eight CPUs, single rcu_node structure.
> TASKS01: Two CPUs, single rcu_node structure.
> TASKS03: Two CPUs, single rcu_node structure.
> TREE09:  Single CPU, single rcu_node structure.
> 
> All the other TREE0N configurations have multiple rcu_node structures.
> 
> TASKS02 didn't warn either despite having only one CPU, but that is
> because it uses Tiny RCU instead of Tree RCU.
> 
> So this warning shows up only in the case where the compiler knows
> that the rcu_node tree consists of only one rcu_node structure.
> 
> 							Thanx, Paul
> 
> > > Cc: "Paul E. McKenney" <paulmck@linux.vnet.ibm.com>
> > > 
> > > 
> > > Alexander Gordeev (10):
> > >   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
> > >   rcu: Remove unnecessary grpnum field from rcu_node structure
> > > 
> > >  kernel/rcu/tree.c        | 102 ++++++++++++++++++++---------------------------
> > >  kernel/rcu/tree.h        |  35 ++++++++--------
> > >  kernel/rcu/tree_plugin.h |   4 +-
> > >  3 files changed, 63 insertions(+), 78 deletions(-)
> > > 
> > > -- 
> > > 1.8.3.1
> > > 

Re: [PATCH 00/10] rcu: Cleanup RCU tree initialization

[Paul E. McKenney]

On Mon, Mar 09, 2015 at 04:49:43PM -0700, Paul E. McKenney wrote:
> On Mon, Mar 09, 2015 at 04:39:47PM -0700, Paul E. McKenney wrote:
> > On Mon, Mar 09, 2015 at 02:40:21PM -0700, Paul E. McKenney wrote:
> > > On Mon, Mar 09, 2015 at 09:34:04AM +0100, Alexander Gordeev wrote:
> > > > Hi Paul,
> > > > 
> > > > Here is cleanup of RCU tree initialization rebased on linux-rcu rcu/next
> > > > repo, as you requested. Please, note an extra patch #10 that was not
> > > > present in the first post.
> > > > 
> > > > The series successfully passes kernel build test with CONFIG_RCU_FANOUT
> > > > and CONFIG_RCU_FANOUT_LEAF equal to 5.
> > > 
> > > I queued up 1-9, as discussed and have started testing.  I will let you
> > > know how it goes.
> > 
> > Initial testing went well except for the following warning:
> > 
> > /home/paulmck/public_git/linux-rcu/kernel/rcu/tree.c: In function ‘rcu_init_one.isra.63’:
> > /home/paulmck/public_git/linux-rcu/kernel/rcu/tree.c:3961:3: warning: ‘levelcnt[0]’ may be used uninitialized in this function [-Wmaybe-uninitialized]
> >    for (j = 0; j < levelcnt[i]; j++, rnp++) {
> > 
> > This warning looks like a false positive to me, given that the loop
> > near the beginning of the function initializes levelcnt[0].  Am I
> > missing something here, and either way, what is the best way to shut
> > this warning up?
> 
> My suggestion is the following:
> 
> 	if (rcu_num_lvls <= 0)
> 		panic("rcu_init_one: rcu_num_lvls underflow");
> 
> Just following the other panic() in rcu_init_one().

As in the following patch.

							Thanx, Paul

------------------------------------------------------------------------

rcu: Shut up spurious gcc uninitialized-variable warning

Because gcc doesn't realize that rcu_num_lvls must be strictly greater
than zero, some versions give a spurious warning about levelcnt[0] being
uninitialized in rcu_init_one().  This commit adds a panic() in that
case in order to educate gcc on this point.

Signed-off-by: Paul E. McKenney <paulmck@linux.vnet.ibm.com>

diff --git a/kernel/rcu/tree.c b/kernel/rcu/tree.c
index bd5a9a1db048..5b42d94335e3 100644
--- a/kernel/rcu/tree.c
+++ b/kernel/rcu/tree.c
@@ -3942,6 +3942,8 @@ static void __init rcu_init_one(struct rcu_state *rsp,
 	/* Silence gcc 4.8 warning about array index out of range. */
 	if (rcu_num_lvls > RCU_NUM_LVLS)
 		panic("rcu_init_one: rcu_num_lvls overflow");
+	if (rcu_num_lvls <= 0)
+		panic("rcu_init_one: rcu_num_lvls underflow");
 
 	/* Initialize the level-tracking arrays. */
 

Re: [PATCH 00/10] rcu: Cleanup RCU tree initialization

[Alexander Gordeev]

On Mon, Mar 09, 2015 at 02:35:42PM -0700, Paul E. McKenney wrote:
> On Mon, Mar 09, 2015 at 09:36:52AM +0000, Alexander Gordeev wrote:
> > On Mon, Mar 09, 2015 at 09:34:04AM +0100, Alexander Gordeev wrote:
> > > Hi Paul,
> > > 
> > > Here is cleanup of RCU tree initialization rebased on linux-rcu rcu/next
> > > repo, as you requested. Please, note an extra patch #10 that was not
> > > present in the first post.
> > 
> > Paul,
> > 
> > Please, ignore patch #10 for now. I missed to notice rcu_node::grpnum is
> > used in tracing, so the patch is incomplete. I am not sure why trailing
> > spaces in seq_printf(m, "%lx/%lx->%lx %c%c>%c %d:%d ^%d    ", ....) are
> > needed for, so not sure if "^%d" part should be removed (possibly with
> > the traling spaces) or replaced with three spaces.
> 
> OK, dropping this one for the moment.
> 
> The original use of ->grpnum was for manual debugging purposes.  Yes, you
> can get the same information out of ->grpmask, but the number is easier
> to read.  And on the debugfs trace information, ->grpnum is printed,
> but ->grpmask is not.
> 
> The trailing spaces on the seq_printf() allow the rcu_node data to be
> printed on a single line, while still allowing the eye to pick out
> where one rcu_node structure's data ends and the next one begins.
> 
> So here are the choices, as far as I can see:
> 
> 1.	Leave ->grpnum as is.
> 
> 2.	Remove ->grpnum, but regenerate it in print_one_rcu_state(),
> 	for example, by counting the number of rcu_node structures
> 	since the last ->level change.
> 
> 3.	Drop ->grpnum and also remove it from the debugfs tracing.
> 	The reader can rely on the ->grplo and ->grphi fields to
> 	work out where this rcu_node structure fits in, but we
> 	lose the visual indication of any bugs in computing these
> 	quantities.
> 
> 4.	Drop ->grpnum and replace it with ->grpmask.  This seems a
> 	bit obtuse to me.
> 
> 5.	Redesign print_one_rcu_state()'s output from scratch.
> 
> #1 has certain advantages from a laziness viewpoint.  #2 would open up
> some space in the rcu_node structure, but space really isn't an issue
> for that structure given that huge systems have only 257 of them and
> the really small systems use Tiny RCU instead.  #3 might be OK, but I
> am not really convinced.  #4 seems a bit ugly.  I am not signing up
> for #5, in part because not all that many people use RCU's debugfs
> output, so I don't see the point in investing the time.
> 
> But what did you have in mind?

I probably should have marked this patch as an RFC. Given your summary
#1 seems as the best choice.

However, I have something else in mind, indeed. What is the reason to
have 'grpnum' and 'level' as u8 while, say 'grplo' and 'grphi' - as int?
IOW, do we conserve on memory for this structure or not?

Thanks!

> 							Thanx, Paul
> 

-- 
Regards,
Alexander Gordeev
agordeev@redhat.com

Re: [PATCH 00/10] rcu: Cleanup RCU tree initialization

[Alexander Gordeev]

On Mon, Mar 09, 2015 at 09:43:18PM -0700, Paul E. McKenney wrote:
> On Mon, Mar 09, 2015 at 04:49:43PM -0700, Paul E. McKenney wrote:
> > On Mon, Mar 09, 2015 at 04:39:47PM -0700, Paul E. McKenney wrote:
> > > On Mon, Mar 09, 2015 at 02:40:21PM -0700, Paul E. McKenney wrote:
> > > > On Mon, Mar 09, 2015 at 09:34:04AM +0100, Alexander Gordeev wrote:
> > > > > Hi Paul,
> > > > > 
> > > > > Here is cleanup of RCU tree initialization rebased on linux-rcu rcu/next
> > > > > repo, as you requested. Please, note an extra patch #10 that was not
> > > > > present in the first post.
> > > > > 
> > > > > The series successfully passes kernel build test with CONFIG_RCU_FANOUT
> > > > > and CONFIG_RCU_FANOUT_LEAF equal to 5.
> > > > 
> > > > I queued up 1-9, as discussed and have started testing.  I will let you
> > > > know how it goes.
> > > 
> > > Initial testing went well except for the following warning:
> > > 
> > > /home/paulmck/public_git/linux-rcu/kernel/rcu/tree.c: In function ‘rcu_init_one.isra.63’:
> > > /home/paulmck/public_git/linux-rcu/kernel/rcu/tree.c:3961:3: warning: ‘levelcnt[0]’ may be used uninitialized in this function [-Wmaybe-uninitialized]
> > >    for (j = 0; j < levelcnt[i]; j++, rnp++) {
> > > 
> > > This warning looks like a false positive to me, given that the loop
> > > near the beginning of the function initializes levelcnt[0].  Am I
> > > missing something here, and either way, what is the best way to shut
> > > this warning up?
> > 
> > My suggestion is the following:
> > 
> > 	if (rcu_num_lvls <= 0)
> > 		panic("rcu_init_one: rcu_num_lvls underflow");
> > 
> > Just following the other panic() in rcu_init_one().
> 
> As in the following patch.
> 
> 							Thanx, Paul
> 
> ------------------------------------------------------------------------
> 
> rcu: Shut up spurious gcc uninitialized-variable warning
> 
> Because gcc doesn't realize that rcu_num_lvls must be strictly greater
> than zero, some versions give a spurious warning about levelcnt[0] being
> uninitialized in rcu_init_one().  This commit adds a panic() in that
> case in order to educate gcc on this point.
> 
> Signed-off-by: Paul E. McKenney <paulmck@linux.vnet.ibm.com>
> 
> diff --git a/kernel/rcu/tree.c b/kernel/rcu/tree.c
> index bd5a9a1db048..5b42d94335e3 100644
> --- a/kernel/rcu/tree.c
> +++ b/kernel/rcu/tree.c
> @@ -3942,6 +3942,8 @@ static void __init rcu_init_one(struct rcu_state *rsp,
>  	/* Silence gcc 4.8 warning about array index out of range. */
>  	if (rcu_num_lvls > RCU_NUM_LVLS)
>  		panic("rcu_init_one: rcu_num_lvls overflow");
> +	if (rcu_num_lvls <= 0)
> +		panic("rcu_init_one: rcu_num_lvls underflow");

I believe '... else if (rcu_num_lvls <= 0)' is more appropriate here.

But do you think keeping two static strings just to shut the compiler
worth it? May be a single complain would be enough?

  	if (rcu_num_lvls <= 0 || rcu_num_lvls > RCU_NUM_LVLS)
  		panic("rcu_init_one: rcu_num_lvls is out of range");

>  	/* Initialize the level-tracking arrays. */
>  
> 

-- 
Regards,
Alexander Gordeev
agordeev@redhat.com

Re: [PATCH 00/10] rcu: Cleanup RCU tree initialization

[Paul E. McKenney]

On Tue, Mar 10, 2015 at 02:39:39PM +0000, Alexander Gordeev wrote:
> On Mon, Mar 09, 2015 at 09:43:18PM -0700, Paul E. McKenney wrote:
> > On Mon, Mar 09, 2015 at 04:49:43PM -0700, Paul E. McKenney wrote:
> > > On Mon, Mar 09, 2015 at 04:39:47PM -0700, Paul E. McKenney wrote:
> > > > On Mon, Mar 09, 2015 at 02:40:21PM -0700, Paul E. McKenney wrote:
> > > > > On Mon, Mar 09, 2015 at 09:34:04AM +0100, Alexander Gordeev wrote:
> > > > > > Hi Paul,
> > > > > > 
> > > > > > Here is cleanup of RCU tree initialization rebased on linux-rcu rcu/next
> > > > > > repo, as you requested. Please, note an extra patch #10 that was not
> > > > > > present in the first post.
> > > > > > 
> > > > > > The series successfully passes kernel build test with CONFIG_RCU_FANOUT
> > > > > > and CONFIG_RCU_FANOUT_LEAF equal to 5.
> > > > > 
> > > > > I queued up 1-9, as discussed and have started testing.  I will let you
> > > > > know how it goes.
> > > > 
> > > > Initial testing went well except for the following warning:
> > > > 
> > > > /home/paulmck/public_git/linux-rcu/kernel/rcu/tree.c: In function ‘rcu_init_one.isra.63’:
> > > > /home/paulmck/public_git/linux-rcu/kernel/rcu/tree.c:3961:3: warning: ‘levelcnt[0]’ may be used uninitialized in this function [-Wmaybe-uninitialized]
> > > >    for (j = 0; j < levelcnt[i]; j++, rnp++) {
> > > > 
> > > > This warning looks like a false positive to me, given that the loop
> > > > near the beginning of the function initializes levelcnt[0].  Am I
> > > > missing something here, and either way, what is the best way to shut
> > > > this warning up?
> > > 
> > > My suggestion is the following:
> > > 
> > > 	if (rcu_num_lvls <= 0)
> > > 		panic("rcu_init_one: rcu_num_lvls underflow");
> > > 
> > > Just following the other panic() in rcu_init_one().
> > 
> > As in the following patch.
> > 
> > 							Thanx, Paul
> > 
> > ------------------------------------------------------------------------
> > 
> > rcu: Shut up spurious gcc uninitialized-variable warning
> > 
> > Because gcc doesn't realize that rcu_num_lvls must be strictly greater
> > than zero, some versions give a spurious warning about levelcnt[0] being
> > uninitialized in rcu_init_one().  This commit adds a panic() in that
> > case in order to educate gcc on this point.
> > 
> > Signed-off-by: Paul E. McKenney <paulmck@linux.vnet.ibm.com>
> > 
> > diff --git a/kernel/rcu/tree.c b/kernel/rcu/tree.c
> > index bd5a9a1db048..5b42d94335e3 100644
> > --- a/kernel/rcu/tree.c
> > +++ b/kernel/rcu/tree.c
> > @@ -3942,6 +3942,8 @@ static void __init rcu_init_one(struct rcu_state *rsp,
> >  	/* Silence gcc 4.8 warning about array index out of range. */
> >  	if (rcu_num_lvls > RCU_NUM_LVLS)
> >  		panic("rcu_init_one: rcu_num_lvls overflow");
> > +	if (rcu_num_lvls <= 0)
> > +		panic("rcu_init_one: rcu_num_lvls underflow");
> 
> I believe '... else if (rcu_num_lvls <= 0)' is more appropriate here.

Good point.

> But do you think keeping two static strings just to shut the compiler
> worth it? May be a single complain would be enough?

As in the following?

	if (rcu_num_lvls <= 0 || rcu_num_lvls > RCU_NUM_LVLS)
		panic("rcu_init_one: rcu_num_lvls out of range");


For Tree RCU, I doubt that the memory size matters, but I do like
having two lines of code instead of four lines.  I took this approach.

							Thanx, Paul

>   	if (rcu_num_lvls <= 0 || rcu_num_lvls > RCU_NUM_LVLS)
>   		panic("rcu_init_one: rcu_num_lvls is out of range");
> 
> >  	/* Initialize the level-tracking arrays. */
> >  
> > 
> 
> -- 
> Regards,
> Alexander Gordeev
> agordeev@redhat.com
> 

Re: [PATCH 00/10] rcu: Cleanup RCU tree initialization

[Paul E. McKenney]

On Tue, Mar 10, 2015 at 02:33:37PM +0000, Alexander Gordeev wrote:
> On Mon, Mar 09, 2015 at 02:35:42PM -0700, Paul E. McKenney wrote:
> > On Mon, Mar 09, 2015 at 09:36:52AM +0000, Alexander Gordeev wrote:
> > > On Mon, Mar 09, 2015 at 09:34:04AM +0100, Alexander Gordeev wrote:
> > > > Hi Paul,
> > > > 
> > > > Here is cleanup of RCU tree initialization rebased on linux-rcu rcu/next
> > > > repo, as you requested. Please, note an extra patch #10 that was not
> > > > present in the first post.
> > > 
> > > Paul,
> > > 
> > > Please, ignore patch #10 for now. I missed to notice rcu_node::grpnum is
> > > used in tracing, so the patch is incomplete. I am not sure why trailing
> > > spaces in seq_printf(m, "%lx/%lx->%lx %c%c>%c %d:%d ^%d    ", ....) are
> > > needed for, so not sure if "^%d" part should be removed (possibly with
> > > the traling spaces) or replaced with three spaces.
> > 
> > OK, dropping this one for the moment.
> > 
> > The original use of ->grpnum was for manual debugging purposes.  Yes, you
> > can get the same information out of ->grpmask, but the number is easier
> > to read.  And on the debugfs trace information, ->grpnum is printed,
> > but ->grpmask is not.
> > 
> > The trailing spaces on the seq_printf() allow the rcu_node data to be
> > printed on a single line, while still allowing the eye to pick out
> > where one rcu_node structure's data ends and the next one begins.
> > 
> > So here are the choices, as far as I can see:
> > 
> > 1.	Leave ->grpnum as is.
> > 
> > 2.	Remove ->grpnum, but regenerate it in print_one_rcu_state(),
> > 	for example, by counting the number of rcu_node structures
> > 	since the last ->level change.
> > 
> > 3.	Drop ->grpnum and also remove it from the debugfs tracing.
> > 	The reader can rely on the ->grplo and ->grphi fields to
> > 	work out where this rcu_node structure fits in, but we
> > 	lose the visual indication of any bugs in computing these
> > 	quantities.
> > 
> > 4.	Drop ->grpnum and replace it with ->grpmask.  This seems a
> > 	bit obtuse to me.
> > 
> > 5.	Redesign print_one_rcu_state()'s output from scratch.
> > 
> > #1 has certain advantages from a laziness viewpoint.  #2 would open up
> > some space in the rcu_node structure, but space really isn't an issue
> > for that structure given that huge systems have only 257 of them and
> > the really small systems use Tiny RCU instead.  #3 might be OK, but I
> > am not really convinced.  #4 seems a bit ugly.  I am not signing up
> > for #5, in part because not all that many people use RCU's debugfs
> > output, so I don't see the point in investing the time.
> > 
> > But what did you have in mind?
> 
> I probably should have marked this patch as an RFC. Given your summary
> #1 seems as the best choice.
> 
> However, I have something else in mind, indeed. What is the reason to
> have 'grpnum' and 'level' as u8 while, say 'grplo' and 'grphi' - as int?
> IOW, do we conserve on memory for this structure or not?

The ->grplo and ->grphi fields must hold a CPU number.  Since CPU numbers
are int elsewhere, they are int here.  I considered making them a short,
but there are systems uncomfortably close to the limit.  There have
been 4096-CPU systems for quite some time, and I have heard rumors of
16384-CPU systems.  A limit of 32768 seems uncomfortably tight, especially
given that memory footprint is at best a minor requirement for Tree RCU.
Tiny RCU is of course another story -- memory savings is Job One there.

And yes, I do owe the community a writeup of the requirements on RCU.

							Thanx, Paul