include/linux/rcu_segcblist.h

   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 <[email protected]>
  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 */