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 * ---------------------------------------------------------------------------- 85 * | 86 * v 87 * ---------------------------------------------------------------------------- 88 * | SEGCBLIST_RCU_CORE | SEGCBLIST_LOCKING | SEGCBLIST_OFFLOADED | 89 * | + unparked CB kthread | 90 * | | 91 * | CB kthread got unparked and processes callbacks concurrently with | 92 * | rcu_core(), holding nocb_lock. | 93 * --------------------------------------------------------------------------- 94 * | 95 * v 96 * ---------------------------------------------------------------------------| 97 * | SEGCBLIST_RCU_CORE | | 98 * | SEGCBLIST_LOCKING | | 99 * | SEGCBLIST_OFFLOADED | | 100 * | SEGCBLIST_KTHREAD_GP | 101 * | + unparked CB kthread | 102 * | | 103 * | GP kthread woke up and acknowledged nocb_lock. | 104 * ---------------------------------------- ----------------------------------- 105 * | 106 * v 107 * |--------------------------------------------------------------------------| 108 * | SEGCBLIST_LOCKING | | 109 * | SEGCBLIST_OFFLOADED | | 110 * | SEGCBLIST_KTHREAD_GP | | 111 * | + unparked CB kthread | 112 * | | 113 * | Kthreads handle callbacks holding nocb_lock, local rcu_core() stops | 114 * | handling callbacks. Enable bypass queueing. | 115 * ---------------------------------------------------------------------------- 116 */ 117 118 119 120 /* 121 * ==NOCB De-Offloading state machine== 122 * 123 * 124 * |--------------------------------------------------------------------------| 125 * | SEGCBLIST_LOCKING | | 126 * | SEGCBLIST_OFFLOADED | | 127 * | SEGCBLIST_KTHREAD_GP | 128 * | + unparked CB kthread | 129 * | | 130 * | CB/GP kthreads handle callbacks holding nocb_lock, local rcu_core() | 131 * | ignores callbacks. Bypass enqueue is enabled. | 132 * ---------------------------------------------------------------------------- 133 * | 134 * v 135 * |--------------------------------------------------------------------------| 136 * | SEGCBLIST_RCU_CORE | | 137 * | SEGCBLIST_LOCKING | | 138 * | SEGCBLIST_OFFLOADED | | 139 * | SEGCBLIST_KTHREAD_GP | 140 * | + unparked CB kthread | 141 * | | 142 * | CB/GP kthreads handle callbacks holding nocb_lock, local rcu_core() | 143 * | handles callbacks concurrently. Bypass enqueue is disabled. | 144 * | Invoke RCU core so we make sure not to preempt it in the middle with | 145 * | leaving some urgent work unattended within a jiffy. | 146 * ---------------------------------------------------------------------------- 147 * | 148 * v 149 * |--------------------------------------------------------------------------| 150 * | SEGCBLIST_RCU_CORE | | 151 * | SEGCBLIST_LOCKING | | 152 * | SEGCBLIST_KTHREAD_GP | 153 * | + unparked CB kthread | 154 * | | 155 * | CB/GP kthreads and local rcu_core() handle callbacks concurrently | 156 * | holding nocb_lock. Wake up GP kthread if necessary. | 157 * ---------------------------------------------------------------------------- 158 * | 159 * v 160 * |--------------------------------------------------------------------------| 161 * | SEGCBLIST_RCU_CORE | | 162 * | SEGCBLIST_LOCKING | | 163 * | + unparked CB kthread | 164 * | | 165 * | GP kthread woke up and acknowledged the fact that SEGCBLIST_OFFLOADED | 166 * | got cleared. The callbacks from the target CPU will be ignored from the| 167 * | GP kthread loop. | 168 * ---------------------------------------------------------------------------- 169 * | 170 * v 171 * ---------------------------------------------------------------------------- 172 * | SEGCBLIST_RCU_CORE | SEGCBLIST_LOCKING | 173 * | + parked CB kthread | 174 * | | 175 * | CB kthread is parked. Callbacks processed by rcu_core() from softirqs or | 176 * | local rcuc kthread, while holding nocb_lock. | 177 * ---------------------------------------------------------------------------- 178 * | 179 * v 180 * ---------------------------------------------------------------------------- 181 * | SEGCBLIST_RCU_CORE | 182 * | | 183 * | Callbacks processed by rcu_core() from softirqs or local | 184 * | rcuc kthread, without holding nocb_lock. | 185 * ---------------------------------------------------------------------------- 186 */ 187 #define SEGCBLIST_ENABLED BIT(0) 188 #define SEGCBLIST_OFFLOADED BIT(1) 189 190 struct rcu_segcblist { 191 struct rcu_head *head; 192 struct rcu_head **tails[RCU_CBLIST_NSEGS]; 193 unsigned long gp_seq[RCU_CBLIST_NSEGS]; 194 #ifdef CONFIG_RCU_NOCB_CPU 195 atomic_long_t len; 196 #else 197 long len; 198 #endif 199 long seglen[RCU_CBLIST_NSEGS]; 200 u8 flags; 201 }; 202 203 #define RCU_SEGCBLIST_INITIALIZER(n) \ 204 { \ 205 .head = NULL, \ 206 .tails[RCU_DONE_TAIL] = &n.head, \ 207 .tails[RCU_WAIT_TAIL] = &n.head, \ 208 .tails[RCU_NEXT_READY_TAIL] = &n.head, \ 209 .tails[RCU_NEXT_TAIL] = &n.head, \ 210 } 211 212 #endif /* __INCLUDE_LINUX_RCU_SEGCBLIST_H */ 213