1265b4d4dSPaul E. McKenney /* SPDX-License-Identifier: GPL-2.0+ */ 28660b7d8SPaul E. McKenney /* 38660b7d8SPaul E. McKenney * RCU segmented callback lists 48660b7d8SPaul E. McKenney * 5aaaad0bfSPaul E. McKenney * This seemingly RCU-private file must be available to SRCU users 6aaaad0bfSPaul E. McKenney * because the size of the TREE SRCU srcu_struct structure depends 7aaaad0bfSPaul E. McKenney * on these definitions. 8aaaad0bfSPaul E. McKenney * 98660b7d8SPaul E. McKenney * Copyright IBM Corporation, 2017 108660b7d8SPaul E. McKenney * 11265b4d4dSPaul E. McKenney * Authors: Paul E. McKenney <paulmck@linux.net.ibm.com> 128660b7d8SPaul E. McKenney */ 138660b7d8SPaul E. McKenney 1445753c5fSIngo Molnar #ifndef __INCLUDE_LINUX_RCU_SEGCBLIST_H 1545753c5fSIngo Molnar #define __INCLUDE_LINUX_RCU_SEGCBLIST_H 168660b7d8SPaul E. McKenney 171bb5f9b9SPaul E. McKenney #include <linux/types.h> 181bb5f9b9SPaul E. McKenney #include <linux/atomic.h> 191bb5f9b9SPaul E. McKenney 208660b7d8SPaul E. McKenney /* Simple unsegmented callback lists. */ 218660b7d8SPaul E. McKenney struct rcu_cblist { 228660b7d8SPaul E. McKenney struct rcu_head *head; 238660b7d8SPaul E. McKenney struct rcu_head **tail; 248660b7d8SPaul E. McKenney long len; 258660b7d8SPaul E. McKenney }; 268660b7d8SPaul E. McKenney 278660b7d8SPaul E. McKenney #define RCU_CBLIST_INITIALIZER(n) { .head = NULL, .tail = &n.head } 288660b7d8SPaul E. McKenney 298660b7d8SPaul E. McKenney /* Complicated segmented callback lists. ;-) */ 308660b7d8SPaul E. McKenney 318660b7d8SPaul E. McKenney /* 328660b7d8SPaul E. McKenney * Index values for segments in rcu_segcblist structure. 338660b7d8SPaul E. McKenney * 348660b7d8SPaul E. McKenney * The segments are as follows: 358660b7d8SPaul E. McKenney * 368660b7d8SPaul E. McKenney * [head, *tails[RCU_DONE_TAIL]): 378660b7d8SPaul E. McKenney * Callbacks whose grace period has elapsed, and thus can be invoked. 388660b7d8SPaul E. McKenney * [*tails[RCU_DONE_TAIL], *tails[RCU_WAIT_TAIL]): 398660b7d8SPaul E. McKenney * Callbacks waiting for the current GP from the current CPU's viewpoint. 408660b7d8SPaul E. McKenney * [*tails[RCU_WAIT_TAIL], *tails[RCU_NEXT_READY_TAIL]): 418660b7d8SPaul E. McKenney * Callbacks that arrived before the next GP started, again from 428660b7d8SPaul E. McKenney * the current CPU's viewpoint. These can be handled by the next GP. 438660b7d8SPaul E. McKenney * [*tails[RCU_NEXT_READY_TAIL], *tails[RCU_NEXT_TAIL]): 448660b7d8SPaul E. McKenney * Callbacks that might have arrived after the next GP started. 458660b7d8SPaul E. McKenney * There is some uncertainty as to when a given GP starts and 468660b7d8SPaul E. McKenney * ends, but a CPU knows the exact times if it is the one starting 478660b7d8SPaul E. McKenney * or ending the GP. Other CPUs know that the previous GP ends 488660b7d8SPaul E. McKenney * before the next one starts. 498660b7d8SPaul E. McKenney * 508660b7d8SPaul E. McKenney * Note that RCU_WAIT_TAIL cannot be empty unless RCU_NEXT_READY_TAIL is also 518660b7d8SPaul E. McKenney * empty. 528660b7d8SPaul E. McKenney * 538660b7d8SPaul E. McKenney * The ->gp_seq[] array contains the grace-period number at which the 548660b7d8SPaul E. McKenney * corresponding segment of callbacks will be ready to invoke. A given 558660b7d8SPaul E. McKenney * element of this array is meaningful only when the corresponding segment 568660b7d8SPaul E. McKenney * is non-empty, and it is never valid for RCU_DONE_TAIL (whose callbacks 578660b7d8SPaul E. McKenney * are already ready to invoke) or for RCU_NEXT_TAIL (whose callbacks have 588660b7d8SPaul E. McKenney * not yet been assigned a grace-period number). 598660b7d8SPaul E. McKenney */ 608660b7d8SPaul E. McKenney #define RCU_DONE_TAIL 0 /* Also RCU_WAIT head. */ 618660b7d8SPaul E. McKenney #define RCU_WAIT_TAIL 1 /* Also RCU_NEXT_READY head. */ 628660b7d8SPaul E. McKenney #define RCU_NEXT_READY_TAIL 2 /* Also RCU_NEXT head. */ 638660b7d8SPaul E. McKenney #define RCU_NEXT_TAIL 3 648660b7d8SPaul E. McKenney #define RCU_CBLIST_NSEGS 4 658660b7d8SPaul E. McKenney 668d346d43SFrederic Weisbecker 678d346d43SFrederic Weisbecker /* 688d346d43SFrederic Weisbecker * ==NOCB Offloading state machine== 698d346d43SFrederic Weisbecker * 708d346d43SFrederic Weisbecker * 718d346d43SFrederic Weisbecker * ---------------------------------------------------------------------------- 72213d56bfSFrederic Weisbecker * | SEGCBLIST_RCU_CORE | 738d346d43SFrederic Weisbecker * | | 748d346d43SFrederic Weisbecker * | Callbacks processed by rcu_core() from softirqs or local | 758d346d43SFrederic Weisbecker * | rcuc kthread, without holding nocb_lock. | 768d346d43SFrederic Weisbecker * ---------------------------------------------------------------------------- 778d346d43SFrederic Weisbecker * | 788d346d43SFrederic Weisbecker * v 798d346d43SFrederic Weisbecker * ---------------------------------------------------------------------------- 80213d56bfSFrederic Weisbecker * | SEGCBLIST_RCU_CORE | SEGCBLIST_LOCKING | SEGCBLIST_OFFLOADED | 818d346d43SFrederic Weisbecker * | | 828d346d43SFrederic Weisbecker * | Callbacks processed by rcu_core() from softirqs or local | 838d346d43SFrederic Weisbecker * | rcuc kthread, while holding nocb_lock. Waking up CB and GP kthreads, | 848d346d43SFrederic Weisbecker * | allowing nocb_timer to be armed. | 858d346d43SFrederic Weisbecker * ---------------------------------------------------------------------------- 868d346d43SFrederic Weisbecker * | 878d346d43SFrederic Weisbecker * v 888d346d43SFrederic Weisbecker * ----------------------------------- 898d346d43SFrederic Weisbecker * | | 908d346d43SFrederic Weisbecker * v v 918d346d43SFrederic Weisbecker * --------------------------------------- ----------------------------------| 92213d56bfSFrederic Weisbecker * | SEGCBLIST_RCU_CORE | | | SEGCBLIST_RCU_CORE | | 93213d56bfSFrederic Weisbecker * | SEGCBLIST_LOCKING | | | SEGCBLIST_LOCKING | | 948d346d43SFrederic Weisbecker * | SEGCBLIST_OFFLOADED | | | SEGCBLIST_OFFLOADED | | 958d346d43SFrederic Weisbecker * | SEGCBLIST_KTHREAD_CB | | SEGCBLIST_KTHREAD_GP | 968d346d43SFrederic Weisbecker * | | | | 978d346d43SFrederic Weisbecker * | | | | 988d346d43SFrederic Weisbecker * | CB kthread woke up and | | GP kthread woke up and | 998d346d43SFrederic Weisbecker * | acknowledged SEGCBLIST_OFFLOADED. | | acknowledged SEGCBLIST_OFFLOADED| 1008d346d43SFrederic Weisbecker * | Processes callbacks concurrently | | | 1018d346d43SFrederic Weisbecker * | with rcu_core(), holding | | | 1028d346d43SFrederic Weisbecker * | nocb_lock. | | | 1038d346d43SFrederic Weisbecker * --------------------------------------- ----------------------------------- 1048d346d43SFrederic Weisbecker * | | 1058d346d43SFrederic Weisbecker * ----------------------------------- 1068d346d43SFrederic Weisbecker * | 1078d346d43SFrederic Weisbecker * v 1088d346d43SFrederic Weisbecker * |--------------------------------------------------------------------------| 109213d56bfSFrederic Weisbecker * | SEGCBLIST_LOCKING | | 1108d346d43SFrederic Weisbecker * | SEGCBLIST_OFFLOADED | | 111213d56bfSFrederic Weisbecker * | SEGCBLIST_KTHREAD_GP | | 112213d56bfSFrederic Weisbecker * | SEGCBLIST_KTHREAD_CB | 1138d346d43SFrederic Weisbecker * | | 1148d346d43SFrederic Weisbecker * | Kthreads handle callbacks holding nocb_lock, local rcu_core() stops | 11576d00b49SFrederic Weisbecker * | handling callbacks. Enable bypass queueing. | 1168d346d43SFrederic Weisbecker * ---------------------------------------------------------------------------- 1178d346d43SFrederic Weisbecker */ 1188d346d43SFrederic Weisbecker 1198d346d43SFrederic Weisbecker 1208d346d43SFrederic Weisbecker 1218d346d43SFrederic Weisbecker /* 1228d346d43SFrederic Weisbecker * ==NOCB De-Offloading state machine== 1238d346d43SFrederic Weisbecker * 1248d346d43SFrederic Weisbecker * 1258d346d43SFrederic Weisbecker * |--------------------------------------------------------------------------| 126213d56bfSFrederic Weisbecker * | SEGCBLIST_LOCKING | | 1278d346d43SFrederic Weisbecker * | SEGCBLIST_OFFLOADED | | 1288d346d43SFrederic Weisbecker * | SEGCBLIST_KTHREAD_CB | | 1298d346d43SFrederic Weisbecker * | SEGCBLIST_KTHREAD_GP | 1308d346d43SFrederic Weisbecker * | | 1318d346d43SFrederic Weisbecker * | CB/GP kthreads handle callbacks holding nocb_lock, local rcu_core() | 13276d00b49SFrederic Weisbecker * | ignores callbacks. Bypass enqueue is enabled. | 1338d346d43SFrederic Weisbecker * ---------------------------------------------------------------------------- 1348d346d43SFrederic Weisbecker * | 1358d346d43SFrederic Weisbecker * v 1368d346d43SFrederic Weisbecker * |--------------------------------------------------------------------------| 137213d56bfSFrederic Weisbecker * | SEGCBLIST_RCU_CORE | | 138213d56bfSFrederic Weisbecker * | SEGCBLIST_LOCKING | | 139*fbb94cbdSFrederic Weisbecker * | SEGCBLIST_OFFLOADED | | 140*fbb94cbdSFrederic Weisbecker * | SEGCBLIST_KTHREAD_CB | | 141*fbb94cbdSFrederic Weisbecker * | SEGCBLIST_KTHREAD_GP | 142*fbb94cbdSFrederic Weisbecker * | | 143*fbb94cbdSFrederic Weisbecker * | CB/GP kthreads handle callbacks holding nocb_lock, local rcu_core() | 144*fbb94cbdSFrederic Weisbecker * | handles callbacks concurrently. Bypass enqueue is enabled. | 145*fbb94cbdSFrederic Weisbecker * | Invoke RCU core so we make sure not to preempt it in the middle with | 146*fbb94cbdSFrederic Weisbecker * | leaving some urgent work unattended within a jiffy. | 147*fbb94cbdSFrederic Weisbecker * ---------------------------------------------------------------------------- 148*fbb94cbdSFrederic Weisbecker * | 149*fbb94cbdSFrederic Weisbecker * v 150*fbb94cbdSFrederic Weisbecker * |--------------------------------------------------------------------------| 151*fbb94cbdSFrederic Weisbecker * | SEGCBLIST_RCU_CORE | | 152*fbb94cbdSFrederic Weisbecker * | SEGCBLIST_LOCKING | | 1538d346d43SFrederic Weisbecker * | SEGCBLIST_KTHREAD_CB | | 1548d346d43SFrederic Weisbecker * | SEGCBLIST_KTHREAD_GP | 1558d346d43SFrederic Weisbecker * | | 1568d346d43SFrederic Weisbecker * | CB/GP kthreads and local rcu_core() handle callbacks concurrently | 15776d00b49SFrederic Weisbecker * | holding nocb_lock. Wake up CB and GP kthreads if necessary. Disable | 15876d00b49SFrederic Weisbecker * | bypass enqueue. | 1598d346d43SFrederic Weisbecker * ---------------------------------------------------------------------------- 1608d346d43SFrederic Weisbecker * | 1618d346d43SFrederic Weisbecker * v 1628d346d43SFrederic Weisbecker * ----------------------------------- 1638d346d43SFrederic Weisbecker * | | 1648d346d43SFrederic Weisbecker * v v 1658d346d43SFrederic Weisbecker * ---------------------------------------------------------------------------| 166213d56bfSFrederic Weisbecker * | | | 167213d56bfSFrederic Weisbecker * | SEGCBLIST_RCU_CORE | | SEGCBLIST_RCU_CORE | | 168213d56bfSFrederic Weisbecker * | SEGCBLIST_LOCKING | | SEGCBLIST_LOCKING | | 1698d346d43SFrederic Weisbecker * | SEGCBLIST_KTHREAD_CB | SEGCBLIST_KTHREAD_GP | 1708d346d43SFrederic Weisbecker * | | | 1718d346d43SFrederic Weisbecker * | GP kthread woke up and | CB kthread woke up and | 1728d346d43SFrederic Weisbecker * | acknowledged the fact that | acknowledged the fact that | 1738d346d43SFrederic Weisbecker * | SEGCBLIST_OFFLOADED got cleared. | SEGCBLIST_OFFLOADED got cleared. | 1748d346d43SFrederic Weisbecker * | | The CB kthread goes to sleep | 1758d346d43SFrederic Weisbecker * | The callbacks from the target CPU | until it ever gets re-offloaded. | 1768d346d43SFrederic Weisbecker * | will be ignored from the GP kthread | | 1778d346d43SFrederic Weisbecker * | loop. | | 1788d346d43SFrederic Weisbecker * ---------------------------------------------------------------------------- 1798d346d43SFrederic Weisbecker * | | 1808d346d43SFrederic Weisbecker * ----------------------------------- 1818d346d43SFrederic Weisbecker * | 1828d346d43SFrederic Weisbecker * v 1838d346d43SFrederic Weisbecker * ---------------------------------------------------------------------------- 184213d56bfSFrederic Weisbecker * | SEGCBLIST_RCU_CORE | SEGCBLIST_LOCKING | 1858d346d43SFrederic Weisbecker * | | 1868d346d43SFrederic Weisbecker * | Callbacks processed by rcu_core() from softirqs or local | 1878d346d43SFrederic Weisbecker * | rcuc kthread, while holding nocb_lock. Forbid nocb_timer to be armed. | 1888d346d43SFrederic Weisbecker * | Flush pending nocb_timer. Flush nocb bypass callbacks. | 1898d346d43SFrederic Weisbecker * ---------------------------------------------------------------------------- 1908d346d43SFrederic Weisbecker * | 1918d346d43SFrederic Weisbecker * v 1928d346d43SFrederic Weisbecker * ---------------------------------------------------------------------------- 193213d56bfSFrederic Weisbecker * | SEGCBLIST_RCU_CORE | 1948d346d43SFrederic Weisbecker * | | 1958d346d43SFrederic Weisbecker * | Callbacks processed by rcu_core() from softirqs or local | 1968d346d43SFrederic Weisbecker * | rcuc kthread, without holding nocb_lock. | 1978d346d43SFrederic Weisbecker * ---------------------------------------------------------------------------- 1988d346d43SFrederic Weisbecker */ 19965e56032SFrederic Weisbecker #define SEGCBLIST_ENABLED BIT(0) 200213d56bfSFrederic Weisbecker #define SEGCBLIST_RCU_CORE BIT(1) 201213d56bfSFrederic Weisbecker #define SEGCBLIST_LOCKING BIT(2) 202213d56bfSFrederic Weisbecker #define SEGCBLIST_KTHREAD_CB BIT(3) 203213d56bfSFrederic Weisbecker #define SEGCBLIST_KTHREAD_GP BIT(4) 204213d56bfSFrederic Weisbecker #define SEGCBLIST_OFFLOADED BIT(5) 20565e56032SFrederic Weisbecker 2068660b7d8SPaul E. McKenney struct rcu_segcblist { 2078660b7d8SPaul E. McKenney struct rcu_head *head; 2088660b7d8SPaul E. McKenney struct rcu_head **tails[RCU_CBLIST_NSEGS]; 2098660b7d8SPaul E. McKenney unsigned long gp_seq[RCU_CBLIST_NSEGS]; 210eda669a6SPaul E. McKenney #ifdef CONFIG_RCU_NOCB_CPU 211eda669a6SPaul E. McKenney atomic_long_t len; 212eda669a6SPaul E. McKenney #else 2138660b7d8SPaul E. McKenney long len; 214eda669a6SPaul E. McKenney #endif 215ae5c2341SJoel Fernandes (Google) long seglen[RCU_CBLIST_NSEGS]; 21665e56032SFrederic Weisbecker u8 flags; 2178660b7d8SPaul E. McKenney }; 2188660b7d8SPaul E. McKenney 2198660b7d8SPaul E. McKenney #define RCU_SEGCBLIST_INITIALIZER(n) \ 2208660b7d8SPaul E. McKenney { \ 2218660b7d8SPaul E. McKenney .head = NULL, \ 2228660b7d8SPaul E. McKenney .tails[RCU_DONE_TAIL] = &n.head, \ 2238660b7d8SPaul E. McKenney .tails[RCU_WAIT_TAIL] = &n.head, \ 2248660b7d8SPaul E. McKenney .tails[RCU_NEXT_READY_TAIL] = &n.head, \ 2258660b7d8SPaul E. McKenney .tails[RCU_NEXT_TAIL] = &n.head, \ 2268660b7d8SPaul E. McKenney } 2278660b7d8SPaul E. McKenney 22845753c5fSIngo Molnar #endif /* __INCLUDE_LINUX_RCU_SEGCBLIST_H */ 229