1 /* SPDX-License-Identifier: GPL-2.0+ */ 2 /* 3 * RCU segmented callback lists 4 * 5 * This seemingly RCU-private file must be available to SRCU users 6 * because the size of the TREE SRCU srcu_struct structure depends 7 * on these definitions. 8 * 9 * Copyright IBM Corporation, 2017 10 * 11 * Authors: Paul E. McKenney <paulmck@linux.net.ibm.com> 12 */ 13 14 #ifndef __INCLUDE_LINUX_RCU_SEGCBLIST_H 15 #define __INCLUDE_LINUX_RCU_SEGCBLIST_H 16 17 #include <linux/types.h> 18 #include <linux/atomic.h> 19 20 /* Simple unsegmented callback lists. */ 21 struct rcu_cblist { 22 struct rcu_head *head; 23 struct rcu_head **tail; 24 long len; 25 }; 26 27 #define RCU_CBLIST_INITIALIZER(n) { .head = NULL, .tail = &n.head } 28 29 /* Complicated segmented callback lists. ;-) */ 30 31 /* 32 * Index values for segments in rcu_segcblist structure. 33 * 34 * The segments are as follows: 35 * 36 * [head, *tails[RCU_DONE_TAIL]): 37 * Callbacks whose grace period has elapsed, and thus can be invoked. 38 * [*tails[RCU_DONE_TAIL], *tails[RCU_WAIT_TAIL]): 39 * Callbacks waiting for the current GP from the current CPU's viewpoint. 40 * [*tails[RCU_WAIT_TAIL], *tails[RCU_NEXT_READY_TAIL]): 41 * Callbacks that arrived before the next GP started, again from 42 * the current CPU's viewpoint. These can be handled by the next GP. 43 * [*tails[RCU_NEXT_READY_TAIL], *tails[RCU_NEXT_TAIL]): 44 * Callbacks that might have arrived after the next GP started. 45 * There is some uncertainty as to when a given GP starts and 46 * ends, but a CPU knows the exact times if it is the one starting 47 * or ending the GP. Other CPUs know that the previous GP ends 48 * before the next one starts. 49 * 50 * Note that RCU_WAIT_TAIL cannot be empty unless RCU_NEXT_READY_TAIL is also 51 * empty. 52 * 53 * The ->gp_seq[] array contains the grace-period number at which the 54 * corresponding segment of callbacks will be ready to invoke. A given 55 * element of this array is meaningful only when the corresponding segment 56 * is non-empty, and it is never valid for RCU_DONE_TAIL (whose callbacks 57 * are already ready to invoke) or for RCU_NEXT_TAIL (whose callbacks have 58 * not yet been assigned a grace-period number). 59 */ 60 #define RCU_DONE_TAIL 0 /* Also RCU_WAIT head. */ 61 #define RCU_WAIT_TAIL 1 /* Also RCU_NEXT_READY head. */ 62 #define RCU_NEXT_READY_TAIL 2 /* Also RCU_NEXT head. */ 63 #define RCU_NEXT_TAIL 3 64 #define RCU_CBLIST_NSEGS 4 65 66 67 /* 68 * ==NOCB Offloading state machine== 69 * 70 * 71 * ---------------------------------------------------------------------------- 72 * | SEGCBLIST_RCU_CORE | 73 * | | 74 * | Callbacks processed by rcu_core() from softirqs or local | 75 * | rcuc kthread, without holding nocb_lock. | 76 * ---------------------------------------------------------------------------- 77 * | 78 * v 79 * ---------------------------------------------------------------------------- 80 * | SEGCBLIST_RCU_CORE | SEGCBLIST_LOCKING | SEGCBLIST_OFFLOADED | 81 * | | 82 * | Callbacks processed by rcu_core() from softirqs or local | 83 * | rcuc kthread, while holding nocb_lock. Waking up CB and GP kthreads, | 84 * | allowing nocb_timer to be armed. | 85 * ---------------------------------------------------------------------------- 86 * | 87 * v 88 * ----------------------------------- 89 * | | 90 * v v 91 * --------------------------------------- ----------------------------------| 92 * | SEGCBLIST_RCU_CORE | | | SEGCBLIST_RCU_CORE | | 93 * | SEGCBLIST_LOCKING | | | SEGCBLIST_LOCKING | | 94 * | SEGCBLIST_OFFLOADED | | | SEGCBLIST_OFFLOADED | | 95 * | SEGCBLIST_KTHREAD_CB | | SEGCBLIST_KTHREAD_GP | 96 * | | | | 97 * | | | | 98 * | CB kthread woke up and | | GP kthread woke up and | 99 * | acknowledged SEGCBLIST_OFFLOADED. | | acknowledged SEGCBLIST_OFFLOADED| 100 * | Processes callbacks concurrently | | | 101 * | with rcu_core(), holding | | | 102 * | nocb_lock. | | | 103 * --------------------------------------- ----------------------------------- 104 * | | 105 * ----------------------------------- 106 * | 107 * v 108 * |--------------------------------------------------------------------------| 109 * | SEGCBLIST_LOCKING | | 110 * | SEGCBLIST_OFFLOADED | | 111 * | SEGCBLIST_KTHREAD_GP | | 112 * | SEGCBLIST_KTHREAD_CB | 113 * | | 114 * | Kthreads handle callbacks holding nocb_lock, local rcu_core() stops | 115 * | handling callbacks. Enable bypass queueing. | 116 * ---------------------------------------------------------------------------- 117 */ 118 119 120 121 /* 122 * ==NOCB De-Offloading state machine== 123 * 124 * 125 * |--------------------------------------------------------------------------| 126 * | SEGCBLIST_LOCKING | | 127 * | SEGCBLIST_OFFLOADED | | 128 * | SEGCBLIST_KTHREAD_CB | | 129 * | SEGCBLIST_KTHREAD_GP | 130 * | | 131 * | CB/GP kthreads handle callbacks holding nocb_lock, local rcu_core() | 132 * | ignores callbacks. Bypass enqueue is enabled. | 133 * ---------------------------------------------------------------------------- 134 * | 135 * v 136 * |--------------------------------------------------------------------------| 137 * | SEGCBLIST_RCU_CORE | | 138 * | SEGCBLIST_LOCKING | | 139 * | SEGCBLIST_OFFLOADED | | 140 * | SEGCBLIST_KTHREAD_CB | | 141 * | SEGCBLIST_KTHREAD_GP | 142 * | | 143 * | CB/GP kthreads handle callbacks holding nocb_lock, local rcu_core() | 144 * | handles callbacks concurrently. Bypass enqueue is enabled. | 145 * | Invoke RCU core so we make sure not to preempt it in the middle with | 146 * | leaving some urgent work unattended within a jiffy. | 147 * ---------------------------------------------------------------------------- 148 * | 149 * v 150 * |--------------------------------------------------------------------------| 151 * | SEGCBLIST_RCU_CORE | | 152 * | SEGCBLIST_LOCKING | | 153 * | SEGCBLIST_KTHREAD_CB | | 154 * | SEGCBLIST_KTHREAD_GP | 155 * | | 156 * | CB/GP kthreads and local rcu_core() handle callbacks concurrently | 157 * | holding nocb_lock. Wake up CB and GP kthreads if necessary. Disable | 158 * | bypass enqueue. | 159 * ---------------------------------------------------------------------------- 160 * | 161 * v 162 * ----------------------------------- 163 * | | 164 * v v 165 * ---------------------------------------------------------------------------| 166 * | | | 167 * | SEGCBLIST_RCU_CORE | | SEGCBLIST_RCU_CORE | | 168 * | SEGCBLIST_LOCKING | | SEGCBLIST_LOCKING | | 169 * | SEGCBLIST_KTHREAD_CB | SEGCBLIST_KTHREAD_GP | 170 * | | | 171 * | GP kthread woke up and | CB kthread woke up and | 172 * | acknowledged the fact that | acknowledged the fact that | 173 * | SEGCBLIST_OFFLOADED got cleared. | SEGCBLIST_OFFLOADED got cleared. | 174 * | | The CB kthread goes to sleep | 175 * | The callbacks from the target CPU | until it ever gets re-offloaded. | 176 * | will be ignored from the GP kthread | | 177 * | loop. | | 178 * ---------------------------------------------------------------------------- 179 * | | 180 * ----------------------------------- 181 * | 182 * v 183 * ---------------------------------------------------------------------------- 184 * | SEGCBLIST_RCU_CORE | SEGCBLIST_LOCKING | 185 * | | 186 * | Callbacks processed by rcu_core() from softirqs or local | 187 * | rcuc kthread, while holding nocb_lock. Forbid nocb_timer to be armed. | 188 * | Flush pending nocb_timer. Flush nocb bypass callbacks. | 189 * ---------------------------------------------------------------------------- 190 * | 191 * v 192 * ---------------------------------------------------------------------------- 193 * | SEGCBLIST_RCU_CORE | 194 * | | 195 * | Callbacks processed by rcu_core() from softirqs or local | 196 * | rcuc kthread, without holding nocb_lock. | 197 * ---------------------------------------------------------------------------- 198 */ 199 #define SEGCBLIST_ENABLED BIT(0) 200 #define SEGCBLIST_RCU_CORE BIT(1) 201 #define SEGCBLIST_LOCKING BIT(2) 202 #define SEGCBLIST_KTHREAD_CB BIT(3) 203 #define SEGCBLIST_KTHREAD_GP BIT(4) 204 #define SEGCBLIST_OFFLOADED BIT(5) 205 206 struct rcu_segcblist { 207 struct rcu_head *head; 208 struct rcu_head **tails[RCU_CBLIST_NSEGS]; 209 unsigned long gp_seq[RCU_CBLIST_NSEGS]; 210 #ifdef CONFIG_RCU_NOCB_CPU 211 atomic_long_t len; 212 #else 213 long len; 214 #endif 215 long seglen[RCU_CBLIST_NSEGS]; 216 u8 flags; 217 }; 218 219 #define RCU_SEGCBLIST_INITIALIZER(n) \ 220 { \ 221 .head = NULL, \ 222 .tails[RCU_DONE_TAIL] = &n.head, \ 223 .tails[RCU_WAIT_TAIL] = &n.head, \ 224 .tails[RCU_NEXT_READY_TAIL] = &n.head, \ 225 .tails[RCU_NEXT_TAIL] = &n.head, \ 226 } 227 228 #endif /* __INCLUDE_LINUX_RCU_SEGCBLIST_H */ 229