/* SPDX-License-Identifier: GPL-2.0+ */ /* * RCU segmented callback lists * * This seemingly RCU-private file must be available to SRCU users * because the size of the TREE SRCU srcu_struct structure depends * on these definitions. * * Copyright IBM Corporation, 2017 * * Authors: Paul E. McKenney <paulmck@linux.net.ibm.com> */ #ifndef __INCLUDE_LINUX_RCU_SEGCBLIST_H #define __INCLUDE_LINUX_RCU_SEGCBLIST_H #include <linux/types.h> #include <linux/atomic.h> /* Simple unsegmented callback lists. */ struct rcu_cblist { struct rcu_head *head; struct rcu_head **tail; long len; }; #define RCU_CBLIST_INITIALIZER(n) { .head = NULL, .tail = &n.head } /* Complicated segmented callback lists. ;-) */ /* * Index values for segments in rcu_segcblist structure. * * The segments are as follows: * * [head, *tails[RCU_DONE_TAIL]): * Callbacks whose grace period has elapsed, and thus can be invoked. * [*tails[RCU_DONE_TAIL], *tails[RCU_WAIT_TAIL]): * Callbacks waiting for the current GP from the current CPU's viewpoint. * [*tails[RCU_WAIT_TAIL], *tails[RCU_NEXT_READY_TAIL]): * Callbacks that arrived before the next GP started, again from * the current CPU's viewpoint. These can be handled by the next GP. * [*tails[RCU_NEXT_READY_TAIL], *tails[RCU_NEXT_TAIL]): * Callbacks that might have arrived after the next GP started. * There is some uncertainty as to when a given GP starts and * ends, but a CPU knows the exact times if it is the one starting * or ending the GP. Other CPUs know that the previous GP ends * before the next one starts. * * Note that RCU_WAIT_TAIL cannot be empty unless RCU_NEXT_READY_TAIL is also * empty. * * The ->gp_seq[] array contains the grace-period number at which the * corresponding segment of callbacks will be ready to invoke. A given * element of this array is meaningful only when the corresponding segment * is non-empty, and it is never valid for RCU_DONE_TAIL (whose callbacks * are already ready to invoke) or for RCU_NEXT_TAIL (whose callbacks have * not yet been assigned a grace-period number). */ #define RCU_DONE_TAIL 0 /* Also RCU_WAIT head. */ #define RCU_WAIT_TAIL 1 /* Also RCU_NEXT_READY head. */ #define RCU_NEXT_READY_TAIL 2 /* Also RCU_NEXT head. */ #define RCU_NEXT_TAIL 3 #define RCU_CBLIST_NSEGS 4 /* * ==NOCB Offloading state machine== * * * ---------------------------------------------------------------------------- * | SEGCBLIST_RCU_CORE | * | | * | Callbacks processed by rcu_core() from softirqs or local | * | rcuc kthread, without holding nocb_lock. | * ---------------------------------------------------------------------------- * | * v * ---------------------------------------------------------------------------- * | SEGCBLIST_RCU_CORE | SEGCBLIST_LOCKING | SEGCBLIST_OFFLOADED | * | | * | Callbacks processed by rcu_core() from softirqs or local | * | rcuc kthread, while holding nocb_lock. Waking up CB and GP kthreads, | * | allowing nocb_timer to be armed. | * ---------------------------------------------------------------------------- * | * v * ----------------------------------- * | | * v v * --------------------------------------- ----------------------------------| * | SEGCBLIST_RCU_CORE | | | SEGCBLIST_RCU_CORE | | * | SEGCBLIST_LOCKING | | | SEGCBLIST_LOCKING | | * | SEGCBLIST_OFFLOADED | | | SEGCBLIST_OFFLOADED | | * | SEGCBLIST_KTHREAD_CB | | SEGCBLIST_KTHREAD_GP | * | | | | * | | | | * | CB kthread woke up and | | GP kthread woke up and | * | acknowledged SEGCBLIST_OFFLOADED. | | acknowledged SEGCBLIST_OFFLOADED| * | Processes callbacks concurrently | | | * | with rcu_core(), holding | | | * | nocb_lock. | | | * --------------------------------------- ----------------------------------- * | | * ----------------------------------- * | * v * |--------------------------------------------------------------------------| * | SEGCBLIST_LOCKING | | * | SEGCBLIST_OFFLOADED | | * | SEGCBLIST_KTHREAD_GP | | * | SEGCBLIST_KTHREAD_CB | * | | * | Kthreads handle callbacks holding nocb_lock, local rcu_core() stops | * | handling callbacks. Enable bypass queueing. | * ---------------------------------------------------------------------------- */ /* * ==NOCB De-Offloading state machine== * * * |--------------------------------------------------------------------------| * | SEGCBLIST_LOCKING | | * | SEGCBLIST_OFFLOADED | | * | SEGCBLIST_KTHREAD_CB | | * | SEGCBLIST_KTHREAD_GP | * | | * | CB/GP kthreads handle callbacks holding nocb_lock, local rcu_core() | * | ignores callbacks. Bypass enqueue is enabled. | * ---------------------------------------------------------------------------- * | * v * |--------------------------------------------------------------------------| * | SEGCBLIST_RCU_CORE | | * | SEGCBLIST_LOCKING | | * | SEGCBLIST_OFFLOADED | | * | SEGCBLIST_KTHREAD_CB | | * | SEGCBLIST_KTHREAD_GP | * | | * | CB/GP kthreads handle callbacks holding nocb_lock, local rcu_core() | * | handles callbacks concurrently. Bypass enqueue is enabled. | * | Invoke RCU core so we make sure not to preempt it in the middle with | * | leaving some urgent work unattended within a jiffy. | * ---------------------------------------------------------------------------- * | * v * |--------------------------------------------------------------------------| * | SEGCBLIST_RCU_CORE | | * | SEGCBLIST_LOCKING | | * | SEGCBLIST_KTHREAD_CB | | * | SEGCBLIST_KTHREAD_GP | * | | * | CB/GP kthreads and local rcu_core() handle callbacks concurrently | * | holding nocb_lock. Wake up CB and GP kthreads if necessary. Disable | * | bypass enqueue. | * ---------------------------------------------------------------------------- * | * v * ----------------------------------- * | | * v v * ---------------------------------------------------------------------------| * | | | * | SEGCBLIST_RCU_CORE | | SEGCBLIST_RCU_CORE | | * | SEGCBLIST_LOCKING | | SEGCBLIST_LOCKING | | * | SEGCBLIST_KTHREAD_CB | SEGCBLIST_KTHREAD_GP | * | | | * | GP kthread woke up and | CB kthread woke up and | * | acknowledged the fact that | acknowledged the fact that | * | SEGCBLIST_OFFLOADED got cleared. | SEGCBLIST_OFFLOADED got cleared. | * | | The CB kthread goes to sleep | * | The callbacks from the target CPU | until it ever gets re-offloaded. | * | will be ignored from the GP kthread | | * | loop. | | * ---------------------------------------------------------------------------- * | | * ----------------------------------- * | * v * ---------------------------------------------------------------------------- * | SEGCBLIST_RCU_CORE | SEGCBLIST_LOCKING | * | | * | Callbacks processed by rcu_core() from softirqs or local | * | rcuc kthread, while holding nocb_lock. Forbid nocb_timer to be armed. | * | Flush pending nocb_timer. Flush nocb bypass callbacks. | * ---------------------------------------------------------------------------- * | * v * ---------------------------------------------------------------------------- * | SEGCBLIST_RCU_CORE | * | | * | Callbacks processed by rcu_core() from softirqs or local | * | rcuc kthread, without holding nocb_lock. | * ---------------------------------------------------------------------------- */ #define SEGCBLIST_ENABLED BIT(0) #define SEGCBLIST_RCU_CORE BIT(1) #define SEGCBLIST_LOCKING BIT(2) #define SEGCBLIST_KTHREAD_CB BIT(3) #define SEGCBLIST_KTHREAD_GP BIT(4) #define SEGCBLIST_OFFLOADED BIT(5) struct rcu_segcblist { struct rcu_head *head; struct rcu_head **tails[RCU_CBLIST_NSEGS]; unsigned long gp_seq[RCU_CBLIST_NSEGS]; #ifdef CONFIG_RCU_NOCB_CPU atomic_long_t len; #else long len; #endif long seglen[RCU_CBLIST_NSEGS]; u8 flags; }; #define RCU_SEGCBLIST_INITIALIZER(n) \ { \ .head = NULL, \ .tails[RCU_DONE_TAIL] = &n.head, \ .tails[RCU_WAIT_TAIL] = &n.head, \ .tails[RCU_NEXT_READY_TAIL] = &n.head, \ .tails[RCU_NEXT_TAIL] = &n.head, \ } #endif /* __INCLUDE_LINUX_RCU_SEGCBLIST_H */