Paul E. McKenney | 9f77da9 | 2009-08-22 13:56:45 -0700 | [diff] [blame] | 1 | /* |
| 2 | * Read-Copy Update mechanism for mutual exclusion (tree-based version) |
| 3 | * Internal non-public definitions. |
| 4 | * |
| 5 | * This program is free software; you can redistribute it and/or modify |
| 6 | * it under the terms of the GNU General Public License as published by |
| 7 | * the Free Software Foundation; either version 2 of the License, or |
| 8 | * (at your option) any later version. |
| 9 | * |
| 10 | * This program is distributed in the hope that it will be useful, |
| 11 | * but WITHOUT ANY WARRANTY; without even the implied warranty of |
| 12 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the |
| 13 | * GNU General Public License for more details. |
| 14 | * |
| 15 | * You should have received a copy of the GNU General Public License |
| 16 | * along with this program; if not, write to the Free Software |
| 17 | * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. |
| 18 | * |
| 19 | * Copyright IBM Corporation, 2008 |
| 20 | * |
| 21 | * Author: Ingo Molnar <mingo@elte.hu> |
| 22 | * Paul E. McKenney <paulmck@linux.vnet.ibm.com> |
| 23 | */ |
| 24 | |
| 25 | #include <linux/cache.h> |
| 26 | #include <linux/spinlock.h> |
| 27 | #include <linux/threads.h> |
| 28 | #include <linux/cpumask.h> |
| 29 | #include <linux/seqlock.h> |
| 30 | |
| 31 | /* |
| 32 | * Define shape of hierarchy based on NR_CPUS and CONFIG_RCU_FANOUT. |
| 33 | * In theory, it should be possible to add more levels straightforwardly. |
| 34 | * In practice, this has not been tested, so there is probably some |
| 35 | * bug somewhere. |
| 36 | */ |
| 37 | #define MAX_RCU_LVLS 3 |
| 38 | #define RCU_FANOUT (CONFIG_RCU_FANOUT) |
| 39 | #define RCU_FANOUT_SQ (RCU_FANOUT * RCU_FANOUT) |
| 40 | #define RCU_FANOUT_CUBE (RCU_FANOUT_SQ * RCU_FANOUT) |
| 41 | |
| 42 | #if NR_CPUS <= RCU_FANOUT |
| 43 | # define NUM_RCU_LVLS 1 |
| 44 | # define NUM_RCU_LVL_0 1 |
| 45 | # define NUM_RCU_LVL_1 (NR_CPUS) |
| 46 | # define NUM_RCU_LVL_2 0 |
| 47 | # define NUM_RCU_LVL_3 0 |
| 48 | #elif NR_CPUS <= RCU_FANOUT_SQ |
| 49 | # define NUM_RCU_LVLS 2 |
| 50 | # define NUM_RCU_LVL_0 1 |
| 51 | # define NUM_RCU_LVL_1 (((NR_CPUS) + RCU_FANOUT - 1) / RCU_FANOUT) |
| 52 | # define NUM_RCU_LVL_2 (NR_CPUS) |
| 53 | # define NUM_RCU_LVL_3 0 |
| 54 | #elif NR_CPUS <= RCU_FANOUT_CUBE |
| 55 | # define NUM_RCU_LVLS 3 |
| 56 | # define NUM_RCU_LVL_0 1 |
| 57 | # define NUM_RCU_LVL_1 (((NR_CPUS) + RCU_FANOUT_SQ - 1) / RCU_FANOUT_SQ) |
| 58 | # define NUM_RCU_LVL_2 (((NR_CPUS) + (RCU_FANOUT) - 1) / (RCU_FANOUT)) |
| 59 | # define NUM_RCU_LVL_3 NR_CPUS |
| 60 | #else |
| 61 | # error "CONFIG_RCU_FANOUT insufficient for NR_CPUS" |
| 62 | #endif /* #if (NR_CPUS) <= RCU_FANOUT */ |
| 63 | |
| 64 | #define RCU_SUM (NUM_RCU_LVL_0 + NUM_RCU_LVL_1 + NUM_RCU_LVL_2 + NUM_RCU_LVL_3) |
| 65 | #define NUM_RCU_NODES (RCU_SUM - NR_CPUS) |
| 66 | |
| 67 | /* |
| 68 | * Dynticks per-CPU state. |
| 69 | */ |
| 70 | struct rcu_dynticks { |
| 71 | int dynticks_nesting; /* Track nesting level, sort of. */ |
| 72 | int dynticks; /* Even value for dynticks-idle, else odd. */ |
| 73 | int dynticks_nmi; /* Even value for either dynticks-idle or */ |
| 74 | /* not in nmi handler, else odd. So this */ |
| 75 | /* remains even for nmi from irq handler. */ |
| 76 | }; |
| 77 | |
| 78 | /* |
| 79 | * Definition for node within the RCU grace-period-detection hierarchy. |
| 80 | */ |
| 81 | struct rcu_node { |
| 82 | spinlock_t lock; |
Paul E. McKenney | f41d911 | 2009-08-22 13:56:52 -0700 | [diff] [blame] | 83 | long gpnum; /* Current grace period for this node. */ |
Paul E. McKenney | 8684896 | 2009-08-27 15:00:12 -0700 | [diff] [blame] | 84 | /* This will either be equal to or one */ |
| 85 | /* behind the root rcu_node's gpnum. */ |
Paul E. McKenney | 9f77da9 | 2009-08-22 13:56:45 -0700 | [diff] [blame] | 86 | unsigned long qsmask; /* CPUs or groups that need to switch in */ |
| 87 | /* order for current grace period to proceed.*/ |
| 88 | unsigned long qsmaskinit; |
| 89 | /* Per-GP initialization for qsmask. */ |
| 90 | unsigned long grpmask; /* Mask to apply to parent qsmask. */ |
| 91 | int grplo; /* lowest-numbered CPU or group here. */ |
| 92 | int grphi; /* highest-numbered CPU or group here. */ |
| 93 | u8 grpnum; /* CPU/group number for next level up. */ |
| 94 | u8 level; /* root is at level 0. */ |
| 95 | struct rcu_node *parent; |
Paul E. McKenney | f41d911 | 2009-08-22 13:56:52 -0700 | [diff] [blame] | 96 | struct list_head blocked_tasks[2]; |
| 97 | /* Tasks blocked in RCU read-side critsect. */ |
Paul E. McKenney | 9f77da9 | 2009-08-22 13:56:45 -0700 | [diff] [blame] | 98 | } ____cacheline_internodealigned_in_smp; |
| 99 | |
| 100 | /* Index values for nxttail array in struct rcu_data. */ |
| 101 | #define RCU_DONE_TAIL 0 /* Also RCU_WAIT head. */ |
| 102 | #define RCU_WAIT_TAIL 1 /* Also RCU_NEXT_READY head. */ |
| 103 | #define RCU_NEXT_READY_TAIL 2 /* Also RCU_NEXT head. */ |
| 104 | #define RCU_NEXT_TAIL 3 |
| 105 | #define RCU_NEXT_SIZE 4 |
| 106 | |
| 107 | /* Per-CPU data for read-copy update. */ |
| 108 | struct rcu_data { |
| 109 | /* 1) quiescent-state and grace-period handling : */ |
| 110 | long completed; /* Track rsp->completed gp number */ |
| 111 | /* in order to detect GP end. */ |
| 112 | long gpnum; /* Highest gp number that this CPU */ |
| 113 | /* is aware of having started. */ |
| 114 | long passed_quiesc_completed; |
| 115 | /* Value of completed at time of qs. */ |
| 116 | bool passed_quiesc; /* User-mode/idle loop etc. */ |
| 117 | bool qs_pending; /* Core waits for quiesc state. */ |
| 118 | bool beenonline; /* CPU online at least once. */ |
Paul E. McKenney | f41d911 | 2009-08-22 13:56:52 -0700 | [diff] [blame] | 119 | bool preemptable; /* Preemptable RCU? */ |
Paul E. McKenney | 9f77da9 | 2009-08-22 13:56:45 -0700 | [diff] [blame] | 120 | struct rcu_node *mynode; /* This CPU's leaf of hierarchy */ |
| 121 | unsigned long grpmask; /* Mask to apply to leaf qsmask. */ |
| 122 | |
| 123 | /* 2) batch handling */ |
| 124 | /* |
| 125 | * If nxtlist is not NULL, it is partitioned as follows. |
| 126 | * Any of the partitions might be empty, in which case the |
| 127 | * pointer to that partition will be equal to the pointer for |
| 128 | * the following partition. When the list is empty, all of |
| 129 | * the nxttail elements point to nxtlist, which is NULL. |
| 130 | * |
| 131 | * [*nxttail[RCU_NEXT_READY_TAIL], NULL = *nxttail[RCU_NEXT_TAIL]): |
| 132 | * Entries that might have arrived after current GP ended |
| 133 | * [*nxttail[RCU_WAIT_TAIL], *nxttail[RCU_NEXT_READY_TAIL]): |
| 134 | * Entries known to have arrived before current GP ended |
| 135 | * [*nxttail[RCU_DONE_TAIL], *nxttail[RCU_WAIT_TAIL]): |
| 136 | * Entries that batch # <= ->completed - 1: waiting for current GP |
| 137 | * [nxtlist, *nxttail[RCU_DONE_TAIL]): |
| 138 | * Entries that batch # <= ->completed |
| 139 | * The grace period for these entries has completed, and |
| 140 | * the other grace-period-completed entries may be moved |
| 141 | * here temporarily in rcu_process_callbacks(). |
| 142 | */ |
| 143 | struct rcu_head *nxtlist; |
| 144 | struct rcu_head **nxttail[RCU_NEXT_SIZE]; |
Paul E. McKenney | a71fca5 | 2009-09-18 10:28:19 -0700 | [diff] [blame] | 145 | long qlen; /* # of queued callbacks */ |
Paul E. McKenney | 9f77da9 | 2009-08-22 13:56:45 -0700 | [diff] [blame] | 146 | long blimit; /* Upper limit on a processed batch */ |
| 147 | |
| 148 | #ifdef CONFIG_NO_HZ |
| 149 | /* 3) dynticks interface. */ |
| 150 | struct rcu_dynticks *dynticks; /* Shared per-CPU dynticks state. */ |
| 151 | int dynticks_snap; /* Per-GP tracking for dynticks. */ |
| 152 | int dynticks_nmi_snap; /* Per-GP tracking for dynticks_nmi. */ |
| 153 | #endif /* #ifdef CONFIG_NO_HZ */ |
| 154 | |
| 155 | /* 4) reasons this CPU needed to be kicked by force_quiescent_state */ |
| 156 | #ifdef CONFIG_NO_HZ |
| 157 | unsigned long dynticks_fqs; /* Kicked due to dynticks idle. */ |
| 158 | #endif /* #ifdef CONFIG_NO_HZ */ |
| 159 | unsigned long offline_fqs; /* Kicked due to being offline. */ |
| 160 | unsigned long resched_ipi; /* Sent a resched IPI. */ |
| 161 | |
| 162 | /* 5) __rcu_pending() statistics. */ |
| 163 | long n_rcu_pending; /* rcu_pending() calls since boot. */ |
| 164 | long n_rp_qs_pending; |
| 165 | long n_rp_cb_ready; |
| 166 | long n_rp_cpu_needs_gp; |
| 167 | long n_rp_gp_completed; |
| 168 | long n_rp_gp_started; |
| 169 | long n_rp_need_fqs; |
| 170 | long n_rp_need_nothing; |
| 171 | |
| 172 | int cpu; |
| 173 | }; |
| 174 | |
| 175 | /* Values for signaled field in struct rcu_state. */ |
| 176 | #define RCU_GP_INIT 0 /* Grace period being initialized. */ |
| 177 | #define RCU_SAVE_DYNTICK 1 /* Need to scan dyntick state. */ |
| 178 | #define RCU_FORCE_QS 2 /* Need to force quiescent state. */ |
| 179 | #ifdef CONFIG_NO_HZ |
| 180 | #define RCU_SIGNAL_INIT RCU_SAVE_DYNTICK |
| 181 | #else /* #ifdef CONFIG_NO_HZ */ |
| 182 | #define RCU_SIGNAL_INIT RCU_FORCE_QS |
| 183 | #endif /* #else #ifdef CONFIG_NO_HZ */ |
| 184 | |
| 185 | #define RCU_JIFFIES_TILL_FORCE_QS 3 /* for rsp->jiffies_force_qs */ |
| 186 | #ifdef CONFIG_RCU_CPU_STALL_DETECTOR |
| 187 | #define RCU_SECONDS_TILL_STALL_CHECK (10 * HZ) /* for rsp->jiffies_stall */ |
| 188 | #define RCU_SECONDS_TILL_STALL_RECHECK (30 * HZ) /* for rsp->jiffies_stall */ |
| 189 | #define RCU_STALL_RAT_DELAY 2 /* Allow other CPUs time */ |
| 190 | /* to take at least one */ |
| 191 | /* scheduling clock irq */ |
| 192 | /* before ratting on them. */ |
| 193 | |
| 194 | #endif /* #ifdef CONFIG_RCU_CPU_STALL_DETECTOR */ |
| 195 | |
| 196 | /* |
| 197 | * RCU global state, including node hierarchy. This hierarchy is |
| 198 | * represented in "heap" form in a dense array. The root (first level) |
| 199 | * of the hierarchy is in ->node[0] (referenced by ->level[0]), the second |
| 200 | * level in ->node[1] through ->node[m] (->node[1] referenced by ->level[1]), |
| 201 | * and the third level in ->node[m+1] and following (->node[m+1] referenced |
| 202 | * by ->level[2]). The number of levels is determined by the number of |
| 203 | * CPUs and by CONFIG_RCU_FANOUT. Small systems will have a "hierarchy" |
| 204 | * consisting of a single rcu_node. |
| 205 | */ |
| 206 | struct rcu_state { |
| 207 | struct rcu_node node[NUM_RCU_NODES]; /* Hierarchy. */ |
| 208 | struct rcu_node *level[NUM_RCU_LVLS]; /* Hierarchy levels. */ |
| 209 | u32 levelcnt[MAX_RCU_LVLS + 1]; /* # nodes in each level. */ |
| 210 | u8 levelspread[NUM_RCU_LVLS]; /* kids/node in each level. */ |
| 211 | struct rcu_data *rda[NR_CPUS]; /* array of rdp pointers. */ |
| 212 | |
| 213 | /* The following fields are guarded by the root rcu_node's lock. */ |
| 214 | |
| 215 | u8 signaled ____cacheline_internodealigned_in_smp; |
| 216 | /* Force QS state. */ |
| 217 | long gpnum; /* Current gp number. */ |
| 218 | long completed; /* # of last completed gp. */ |
| 219 | spinlock_t onofflock; /* exclude on/offline and */ |
| 220 | /* starting new GP. */ |
| 221 | spinlock_t fqslock; /* Only one task forcing */ |
| 222 | /* quiescent states. */ |
| 223 | unsigned long jiffies_force_qs; /* Time at which to invoke */ |
| 224 | /* force_quiescent_state(). */ |
| 225 | unsigned long n_force_qs; /* Number of calls to */ |
| 226 | /* force_quiescent_state(). */ |
| 227 | unsigned long n_force_qs_lh; /* ~Number of calls leaving */ |
| 228 | /* due to lock unavailable. */ |
| 229 | unsigned long n_force_qs_ngp; /* Number of calls leaving */ |
| 230 | /* due to no GP active. */ |
| 231 | #ifdef CONFIG_RCU_CPU_STALL_DETECTOR |
| 232 | unsigned long gp_start; /* Time at which GP started, */ |
| 233 | /* but in jiffies. */ |
| 234 | unsigned long jiffies_stall; /* Time at which to check */ |
| 235 | /* for CPU stalls. */ |
| 236 | #endif /* #ifdef CONFIG_RCU_CPU_STALL_DETECTOR */ |
| 237 | #ifdef CONFIG_NO_HZ |
| 238 | long dynticks_completed; /* Value of completed @ snap. */ |
| 239 | #endif /* #ifdef CONFIG_NO_HZ */ |
| 240 | }; |
| 241 | |
| 242 | #ifdef RCU_TREE_NONCORE |
Ingo Molnar | 6258c4f | 2009-03-25 16:42:24 +0100 | [diff] [blame] | 243 | |
| 244 | /* |
| 245 | * RCU implementation internal declarations: |
| 246 | */ |
Paul E. McKenney | d6714c2 | 2009-08-22 13:56:46 -0700 | [diff] [blame] | 247 | extern struct rcu_state rcu_sched_state; |
| 248 | DECLARE_PER_CPU(struct rcu_data, rcu_sched_data); |
Ingo Molnar | 6258c4f | 2009-03-25 16:42:24 +0100 | [diff] [blame] | 249 | |
| 250 | extern struct rcu_state rcu_bh_state; |
| 251 | DECLARE_PER_CPU(struct rcu_data, rcu_bh_data); |
| 252 | |
Paul E. McKenney | f41d911 | 2009-08-22 13:56:52 -0700 | [diff] [blame] | 253 | #ifdef CONFIG_TREE_PREEMPT_RCU |
| 254 | extern struct rcu_state rcu_preempt_state; |
| 255 | DECLARE_PER_CPU(struct rcu_data, rcu_preempt_data); |
| 256 | #endif /* #ifdef CONFIG_TREE_PREEMPT_RCU */ |
| 257 | |
Paul E. McKenney | 9f77da9 | 2009-08-22 13:56:45 -0700 | [diff] [blame] | 258 | #endif /* #ifdef RCU_TREE_NONCORE */ |
| 259 | |