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 state at which the 54 * corresponding segment of callbacks will be ready to invoke. This tracks 55 * both normal and expedited grace periods, allowing callbacks to complete 56 * when either type of GP finishes. A given element of this array is 57 * meaningful only when the corresponding segment is non-empty, and it is 58 * never valid for RCU_DONE_TAIL (whose callbacks are already ready to 59 * invoke) or for RCU_NEXT_TAIL (whose callbacks have not yet been assigned 60 * a grace-period state). 61 */ 62 #define RCU_DONE_TAIL 0 /* Also RCU_WAIT head. */ 63 #define RCU_WAIT_TAIL 1 /* Also RCU_NEXT_READY head. */ 64 #define RCU_NEXT_READY_TAIL 2 /* Also RCU_NEXT head. */ 65 #define RCU_NEXT_TAIL 3 66 #define RCU_CBLIST_NSEGS 4 67 68 69 /* 70 * ==NOCB Offloading state machine== 71 * 72 * 73 * ---------------------------------------------------------------------------- 74 * | SEGCBLIST_RCU_CORE | 75 * | | 76 * | Callbacks processed by rcu_core() from softirqs or local | 77 * | rcuc kthread, without holding nocb_lock. | 78 * ---------------------------------------------------------------------------- 79 * | 80 * v 81 * ---------------------------------------------------------------------------- 82 * | SEGCBLIST_RCU_CORE | SEGCBLIST_LOCKING | SEGCBLIST_OFFLOADED | 83 * | | 84 * | Callbacks processed by rcu_core() from softirqs or local | 85 * | rcuc kthread, while holding nocb_lock. Waking up CB and GP kthreads. | 86 * ---------------------------------------------------------------------------- 87 * | 88 * v 89 * ---------------------------------------------------------------------------- 90 * | SEGCBLIST_RCU_CORE | SEGCBLIST_LOCKING | SEGCBLIST_OFFLOADED | 91 * | + unparked CB kthread | 92 * | | 93 * | CB kthread got unparked and processes callbacks concurrently with | 94 * | rcu_core(), holding nocb_lock. | 95 * --------------------------------------------------------------------------- 96 * | 97 * v 98 * ---------------------------------------------------------------------------| 99 * | SEGCBLIST_RCU_CORE | | 100 * | SEGCBLIST_LOCKING | | 101 * | SEGCBLIST_OFFLOADED | | 102 * | SEGCBLIST_KTHREAD_GP | 103 * | + unparked CB kthread | 104 * | | 105 * | GP kthread woke up and acknowledged nocb_lock. | 106 * ---------------------------------------- ----------------------------------- 107 * | 108 * v 109 * |--------------------------------------------------------------------------| 110 * | SEGCBLIST_LOCKING | | 111 * | SEGCBLIST_OFFLOADED | | 112 * | SEGCBLIST_KTHREAD_GP | | 113 * | + unparked CB kthread | 114 * | | 115 * | Kthreads handle callbacks holding nocb_lock, local rcu_core() stops | 116 * | handling callbacks. Enable bypass queueing. | 117 * ---------------------------------------------------------------------------- 118 */ 119 120 121 122 /* 123 * ==NOCB De-Offloading state machine== 124 * 125 * 126 * |--------------------------------------------------------------------------| 127 * | SEGCBLIST_LOCKING | | 128 * | SEGCBLIST_OFFLOADED | | 129 * | SEGCBLIST_KTHREAD_GP | 130 * | + unparked CB kthread | 131 * | | 132 * | CB/GP kthreads handle callbacks holding nocb_lock, local rcu_core() | 133 * | ignores callbacks. Bypass enqueue is enabled. | 134 * ---------------------------------------------------------------------------- 135 * | 136 * v 137 * |--------------------------------------------------------------------------| 138 * | SEGCBLIST_RCU_CORE | | 139 * | SEGCBLIST_LOCKING | | 140 * | SEGCBLIST_OFFLOADED | | 141 * | SEGCBLIST_KTHREAD_GP | 142 * | + unparked CB kthread | 143 * | | 144 * | CB/GP kthreads handle callbacks holding nocb_lock, local rcu_core() | 145 * | handles callbacks concurrently. Bypass enqueue is disabled. | 146 * | Invoke RCU core so we make sure not to preempt it in the middle with | 147 * | leaving some urgent work unattended within a jiffy. | 148 * ---------------------------------------------------------------------------- 149 * | 150 * v 151 * |--------------------------------------------------------------------------| 152 * | SEGCBLIST_RCU_CORE | | 153 * | SEGCBLIST_LOCKING | | 154 * | SEGCBLIST_KTHREAD_GP | 155 * | + unparked CB kthread | 156 * | | 157 * | CB/GP kthreads and local rcu_core() handle callbacks concurrently | 158 * | holding nocb_lock. Wake up GP kthread if necessary. | 159 * ---------------------------------------------------------------------------- 160 * | 161 * v 162 * |--------------------------------------------------------------------------| 163 * | SEGCBLIST_RCU_CORE | | 164 * | SEGCBLIST_LOCKING | | 165 * | + unparked CB kthread | 166 * | | 167 * | GP kthread woke up and acknowledged the fact that SEGCBLIST_OFFLOADED | 168 * | got cleared. The callbacks from the target CPU will be ignored from the| 169 * | GP kthread loop. | 170 * ---------------------------------------------------------------------------- 171 * | 172 * v 173 * ---------------------------------------------------------------------------- 174 * | SEGCBLIST_RCU_CORE | SEGCBLIST_LOCKING | 175 * | + parked CB kthread | 176 * | | 177 * | CB kthread is parked. Callbacks processed by rcu_core() from softirqs or | 178 * | local rcuc kthread, while holding nocb_lock. | 179 * ---------------------------------------------------------------------------- 180 * | 181 * v 182 * ---------------------------------------------------------------------------- 183 * | SEGCBLIST_RCU_CORE | 184 * | | 185 * | Callbacks processed by rcu_core() from softirqs or local | 186 * | rcuc kthread, without holding nocb_lock. | 187 * ---------------------------------------------------------------------------- 188 */ 189 #define SEGCBLIST_ENABLED BIT(0) 190 #define SEGCBLIST_OFFLOADED BIT(1) 191 192 struct rcu_segcblist { 193 struct rcu_head *head; 194 struct rcu_head **tails[RCU_CBLIST_NSEGS]; 195 struct rcu_gp_seq gp_seq[RCU_CBLIST_NSEGS]; 196 #ifdef CONFIG_RCU_NOCB_CPU 197 atomic_long_t len; 198 #else 199 long len; 200 #endif 201 long seglen[RCU_CBLIST_NSEGS]; 202 u8 flags; 203 }; 204 205 #define RCU_SEGCBLIST_INITIALIZER(n) \ 206 { \ 207 .head = NULL, \ 208 .tails[RCU_DONE_TAIL] = &n.head, \ 209 .tails[RCU_WAIT_TAIL] = &n.head, \ 210 .tails[RCU_NEXT_READY_TAIL] = &n.head, \ 211 .tails[RCU_NEXT_TAIL] = &n.head, \ 212 } 213 214 #endif /* __INCLUDE_LINUX_RCU_SEGCBLIST_H */ 215