include/linux/rcu_node_tree.h

0001 /* SPDX-License-Identifier: GPL-2.0+ */
0002 /*
0003  * RCU node combining tree definitions.  These are used to compute
0004  * global attributes while avoiding common-case global contention.  A key
0005  * property that these computations rely on is a tournament-style approach
0006  * where only one of the tasks contending a lower level in the tree need
0007  * advance to the next higher level.  If properly configured, this allows
0008  * unlimited scalability while maintaining a constant level of contention
0009  * on the root node.
0010  *
0011  * This seemingly RCU-private file must be available to SRCU users
0012  * because the size of the TREE SRCU srcu_struct structure depends
0013  * on these definitions.
0014  *
0015  * Copyright IBM Corporation, 2017
0016  *
0017  * Author: Paul E. McKenney <paulmck@linux.ibm.com>
0018  */
0019
0020 #ifndef __LINUX_RCU_NODE_TREE_H
0021 #define __LINUX_RCU_NODE_TREE_H
0022
0023 #include <linux/math.h>
0024
0025 /*
0026  * Define shape of hierarchy based on NR_CPUS, CONFIG_RCU_FANOUT, and
0027  * CONFIG_RCU_FANOUT_LEAF.
0028  * In theory, it should be possible to add more levels straightforwardly.
0029  * In practice, this did work well going from three levels to four.
0030  * Of course, your mileage may vary.
0031  */
0032
0033 #ifdef CONFIG_RCU_FANOUT
0034 #define RCU_FANOUT CONFIG_RCU_FANOUT
0035 #else /* #ifdef CONFIG_RCU_FANOUT */
0036 # ifdef CONFIG_64BIT
0037 # define RCU_FANOUT 64
0038 # else
0039 # define RCU_FANOUT 32
0040 # endif
0041 #endif /* #else #ifdef CONFIG_RCU_FANOUT */
0042
0043 #ifdef CONFIG_RCU_FANOUT_LEAF
0044 #define RCU_FANOUT_LEAF CONFIG_RCU_FANOUT_LEAF
0045 #else /* #ifdef CONFIG_RCU_FANOUT_LEAF */
0046 #define RCU_FANOUT_LEAF 16
0047 #endif /* #else #ifdef CONFIG_RCU_FANOUT_LEAF */
0048
0049 #define RCU_FANOUT_1          (RCU_FANOUT_LEAF)
0050 #define RCU_FANOUT_2          (RCU_FANOUT_1 * RCU_FANOUT)
0051 #define RCU_FANOUT_3          (RCU_FANOUT_2 * RCU_FANOUT)
0052 #define RCU_FANOUT_4          (RCU_FANOUT_3 * RCU_FANOUT)
0053
0054 #if NR_CPUS <= RCU_FANOUT_1
0055 #  define RCU_NUM_LVLS        1
0056 #  define NUM_RCU_LVL_0       1
0057 #  define NUM_RCU_NODES       NUM_RCU_LVL_0
0058 #  define NUM_RCU_LVL_INIT    { NUM_RCU_LVL_0 }
0059 #  define RCU_NODE_NAME_INIT  { "rcu_node_0" }
0060 #  define RCU_FQS_NAME_INIT   { "rcu_node_fqs_0" }
0061 #elif NR_CPUS <= RCU_FANOUT_2
0062 #  define RCU_NUM_LVLS        2
0063 #  define NUM_RCU_LVL_0       1
0064 #  define NUM_RCU_LVL_1       DIV_ROUND_UP(NR_CPUS, RCU_FANOUT_1)
0065 #  define NUM_RCU_NODES       (NUM_RCU_LVL_0 + NUM_RCU_LVL_1)
0066 #  define NUM_RCU_LVL_INIT    { NUM_RCU_LVL_0, NUM_RCU_LVL_1 }
0067 #  define RCU_NODE_NAME_INIT  { "rcu_node_0", "rcu_node_1" }
0068 #  define RCU_FQS_NAME_INIT   { "rcu_node_fqs_0", "rcu_node_fqs_1" }
0069 #elif NR_CPUS <= RCU_FANOUT_3
0070 #  define RCU_NUM_LVLS        3
0071 #  define NUM_RCU_LVL_0       1
0072 #  define NUM_RCU_LVL_1       DIV_ROUND_UP(NR_CPUS, RCU_FANOUT_2)
0073 #  define NUM_RCU_LVL_2       DIV_ROUND_UP(NR_CPUS, RCU_FANOUT_1)
0074 #  define NUM_RCU_NODES       (NUM_RCU_LVL_0 + NUM_RCU_LVL_1 + NUM_RCU_LVL_2)
0075 #  define NUM_RCU_LVL_INIT    { NUM_RCU_LVL_0, NUM_RCU_LVL_1, NUM_RCU_LVL_2 }
0076 #  define RCU_NODE_NAME_INIT  { "rcu_node_0", "rcu_node_1", "rcu_node_2" }
0077 #  define RCU_FQS_NAME_INIT   { "rcu_node_fqs_0", "rcu_node_fqs_1", "rcu_node_fqs_2" }
0078 #elif NR_CPUS <= RCU_FANOUT_4
0079 #  define RCU_NUM_LVLS        4
0080 #  define NUM_RCU_LVL_0       1
0081 #  define NUM_RCU_LVL_1       DIV_ROUND_UP(NR_CPUS, RCU_FANOUT_3)
0082 #  define NUM_RCU_LVL_2       DIV_ROUND_UP(NR_CPUS, RCU_FANOUT_2)
0083 #  define NUM_RCU_LVL_3       DIV_ROUND_UP(NR_CPUS, RCU_FANOUT_1)
0084 #  define NUM_RCU_NODES       (NUM_RCU_LVL_0 + NUM_RCU_LVL_1 + NUM_RCU_LVL_2 + NUM_RCU_LVL_3)
0085 #  define NUM_RCU_LVL_INIT    { NUM_RCU_LVL_0, NUM_RCU_LVL_1, NUM_RCU_LVL_2, NUM_RCU_LVL_3 }
0086 #  define RCU_NODE_NAME_INIT  { "rcu_node_0", "rcu_node_1", "rcu_node_2", "rcu_node_3" }
0087 #  define RCU_FQS_NAME_INIT   { "rcu_node_fqs_0", "rcu_node_fqs_1", "rcu_node_fqs_2", "rcu_node_fqs_3" }
0088 #else
0089 # error "CONFIG_RCU_FANOUT insufficient for NR_CPUS"
0090 #endif /* #if (NR_CPUS) <= RCU_FANOUT_1 */
0091
0092 #endif /* __LINUX_RCU_NODE_TREE_H */