kernel/rcu/rcu_segcblist.c

   1 // SPDX-License-Identifier: GPL-2.0+
   2 /*
   3  * RCU segmented callback lists, function definitions
   4  *
   5  * Copyright IBM Corporation, 2017
   6  *
   7  * Authors: Paul E. McKenney <paulmck@linux.ibm.com>
   8  */
   9
  10 #include <linux/types.h>
  11 #include <linux/kernel.h>
  12 #include <linux/interrupt.h>
  13 #include <linux/rcupdate.h>
  14
  15 #include "rcu_segcblist.h"
  16
  17 /* Initialize simple callback list. */
  18 void rcu_cblist_init(struct rcu_cblist *rclp)
  19 {
  20         rclp->head = NULL;
  21         rclp->tail = &rclp->head;
  22         rclp->len = 0;
  23         rclp->len_lazy = 0;
  24 }
  25
  26 /*
  27  * Dequeue the oldest rcu_head structure from the specified callback
  28  * list.  This function assumes that the callback is non-lazy, but
  29  * the caller can later invoke rcu_cblist_dequeued_lazy() if it
  30  * finds otherwise (and if it cares about laziness).  This allows
  31  * different users to have different ways of determining laziness.
  32  */
  33 struct rcu_head *rcu_cblist_dequeue(struct rcu_cblist *rclp)
  34 {
  35         struct rcu_head *rhp;
  36
  37         rhp = rclp->head;
  38         if (!rhp)
  39                 return NULL;
  40         rclp->len--;
  41         rclp->head = rhp->next;
  42         if (!rclp->head)
  43                 rclp->tail = &rclp->head;
  44         return rhp;
  45 }
  46
  47 /*
  48  * Initialize an rcu_segcblist structure.
  49  */
  50 void rcu_segcblist_init(struct rcu_segcblist *rsclp)
  51 {
  52         int i;
  53
  54         BUILD_BUG_ON(RCU_NEXT_TAIL + 1 != ARRAY_SIZE(rsclp->gp_seq));
  55         BUILD_BUG_ON(ARRAY_SIZE(rsclp->tails) != ARRAY_SIZE(rsclp->gp_seq));
  56         rsclp->head = NULL;
  57         for (i = 0; i < RCU_CBLIST_NSEGS; i++)
  58                 rsclp->tails[i] = &rsclp->head;
  59         rsclp->len = 0;
  60         rsclp->len_lazy = 0;
  61 }
  62
  63 /*
  64  * Disable the specified rcu_segcblist structure, so that callbacks can
  65  * no longer be posted to it.  This structure must be empty.
  66  */
  67 void rcu_segcblist_disable(struct rcu_segcblist *rsclp)
  68 {
  69         WARN_ON_ONCE(!rcu_segcblist_empty(rsclp));
  70         WARN_ON_ONCE(rcu_segcblist_n_cbs(rsclp));
  71         WARN_ON_ONCE(rcu_segcblist_n_lazy_cbs(rsclp));
  72         rsclp->tails[RCU_NEXT_TAIL] = NULL;
  73 }
  74
  75 /*
  76  * Does the specified rcu_segcblist structure contain callbacks that
  77  * are ready to be invoked?
  78  */
  79 bool rcu_segcblist_ready_cbs(struct rcu_segcblist *rsclp)
  80 {
  81         return rcu_segcblist_is_enabled(rsclp) &&
  82                &rsclp->head != rsclp->tails[RCU_DONE_TAIL];
  83 }
  84
  85 /*
  86  * Does the specified rcu_segcblist structure contain callbacks that
  87  * are still pending, that is, not yet ready to be invoked?
  88  */
  89 bool rcu_segcblist_pend_cbs(struct rcu_segcblist *rsclp)
  90 {
  91         return rcu_segcblist_is_enabled(rsclp) &&
  92                !rcu_segcblist_restempty(rsclp, RCU_DONE_TAIL);
  93 }
  94
  95 /*
  96  * Return a pointer to the first callback in the specified rcu_segcblist
  97  * structure.  This is useful for diagnostics.
  98  */
  99 struct rcu_head *rcu_segcblist_first_cb(struct rcu_segcblist *rsclp)
 100 {
 101         if (rcu_segcblist_is_enabled(rsclp))
 102                 return rsclp->head;
 103         return NULL;
 104 }
 105
 106 /*
 107  * Return a pointer to the first pending callback in the specified
 108  * rcu_segcblist structure.  This is useful just after posting a given
 109  * callback -- if that callback is the first pending callback, then
 110  * you cannot rely on someone else having already started up the required
 111  * grace period.
 112  */
 113 struct rcu_head *rcu_segcblist_first_pend_cb(struct rcu_segcblist *rsclp)
 114 {
 115         if (rcu_segcblist_is_enabled(rsclp))
 116                 return *rsclp->tails[RCU_DONE_TAIL];
 117         return NULL;
 118 }
 119
 120 /*
 121  * Enqueue the specified callback onto the specified rcu_segcblist
 122  * structure, updating accounting as needed.  Note that the ->len
 123  * field may be accessed locklessly, hence the WRITE_ONCE().
 124  * The ->len field is used by rcu_barrier() and friends to determine
 125  * if it must post a callback on this structure, and it is OK
 126  * for rcu_barrier() to sometimes post callbacks needlessly, but
 127  * absolutely not OK for it to ever miss posting a callback.
 128  */
 129 void rcu_segcblist_enqueue(struct rcu_segcblist *rsclp,
 130                            struct rcu_head *rhp, bool lazy)
 131 {
 132         WRITE_ONCE(rsclp->len, rsclp->len + 1); /* ->len sampled locklessly. */
 133         if (lazy)
 134                 rsclp->len_lazy++;
 135         smp_mb(); /* Ensure counts are updated before callback is enqueued. */
 136         rhp->next = NULL;
 137         *rsclp->tails[RCU_NEXT_TAIL] = rhp;
 138         rsclp->tails[RCU_NEXT_TAIL] = &rhp->next;
 139 }
 140
 141 /*
 142  * Entrain the specified callback onto the specified rcu_segcblist at
 143  * the end of the last non-empty segment.  If the entire rcu_segcblist
 144  * is empty, make no change, but return false.
 145  *
 146  * This is intended for use by rcu_barrier()-like primitives, -not-
 147  * for normal grace-period use.  IMPORTANT:  The callback you enqueue
 148  * will wait for all prior callbacks, NOT necessarily for a grace
 149  * period.  You have been warned.
 150  */
 151 bool rcu_segcblist_entrain(struct rcu_segcblist *rsclp,
 152                            struct rcu_head *rhp, bool lazy)
 153 {
 154         int i;
 155
 156         if (rcu_segcblist_n_cbs(rsclp) == 0)
 157                 return false;
 158         WRITE_ONCE(rsclp->len, rsclp->len + 1);
 159         if (lazy)
 160                 rsclp->len_lazy++;
 161         smp_mb(); /* Ensure counts are updated before callback is entrained. */
 162         rhp->next = NULL;
 163         for (i = RCU_NEXT_TAIL; i > RCU_DONE_TAIL; i--)
 164                 if (rsclp->tails[i] != rsclp->tails[i - 1])
 165                         break;
 166         *rsclp->tails[i] = rhp;
 167         for (; i <= RCU_NEXT_TAIL; i++)
 168                 rsclp->tails[i] = &rhp->next;
 169         return true;
 170 }
 171
 172 /*
 173  * Extract only the counts from the specified rcu_segcblist structure,
 174  * and place them in the specified rcu_cblist structure.  This function
 175  * supports both callback orphaning and invocation, hence the separation
 176  * of counts and callbacks.  (Callbacks ready for invocation must be
 177  * orphaned and adopted separately from pending callbacks, but counts
 178  * apply to all callbacks.  Locking must be used to make sure that
 179  * both orphaned-callbacks lists are consistent.)
 180  */
 181 void rcu_segcblist_extract_count(struct rcu_segcblist *rsclp,
 182                                                struct rcu_cblist *rclp)
 183 {
 184         rclp->len_lazy += rsclp->len_lazy;
 185         rclp->len += rsclp->len;
 186         rsclp->len_lazy = 0;
 187         WRITE_ONCE(rsclp->len, 0); /* ->len sampled locklessly. */
 188 }
 189
 190 /*
 191  * Extract only those callbacks ready to be invoked from the specified
 192  * rcu_segcblist structure and place them in the specified rcu_cblist
 193  * structure.
 194  */
 195 void rcu_segcblist_extract_done_cbs(struct rcu_segcblist *rsclp,
 196                                     struct rcu_cblist *rclp)
 197 {
 198         int i;
 199
 200         if (!rcu_segcblist_ready_cbs(rsclp))
 201                 return; /* Nothing to do. */
 202         *rclp->tail = rsclp->head;
 203         rsclp->head = *rsclp->tails[RCU_DONE_TAIL];
 204         *rsclp->tails[RCU_DONE_TAIL] = NULL;
 205         rclp->tail = rsclp->tails[RCU_DONE_TAIL];
 206         for (i = RCU_CBLIST_NSEGS - 1; i >= RCU_DONE_TAIL; i--)
 207                 if (rsclp->tails[i] == rsclp->tails[RCU_DONE_TAIL])
 208                         rsclp->tails[i] = &rsclp->head;
 209 }
 210
 211 /*
 212  * Extract only those callbacks still pending (not yet ready to be
 213  * invoked) from the specified rcu_segcblist structure and place them in
 214  * the specified rcu_cblist structure.  Note that this loses information
 215  * about any callbacks that might have been partway done waiting for
 216  * their grace period.  Too bad!  They will have to start over.
 217  */
 218 void rcu_segcblist_extract_pend_cbs(struct rcu_segcblist *rsclp,
 219                                     struct rcu_cblist *rclp)
 220 {
 221         int i;
 222
 223         if (!rcu_segcblist_pend_cbs(rsclp))
 224                 return; /* Nothing to do. */
 225         *rclp->tail = *rsclp->tails[RCU_DONE_TAIL];
 226         rclp->tail = rsclp->tails[RCU_NEXT_TAIL];
 227         *rsclp->tails[RCU_DONE_TAIL] = NULL;
 228         for (i = RCU_DONE_TAIL + 1; i < RCU_CBLIST_NSEGS; i++)
 229                 rsclp->tails[i] = rsclp->tails[RCU_DONE_TAIL];
 230 }
 231
 232 /*
 233  * Insert counts from the specified rcu_cblist structure in the
 234  * specified rcu_segcblist structure.
 235  */
 236 void rcu_segcblist_insert_count(struct rcu_segcblist *rsclp,
 237                                 struct rcu_cblist *rclp)
 238 {
 239         rsclp->len_lazy += rclp->len_lazy;
 240         /* ->len sampled locklessly. */
 241         WRITE_ONCE(rsclp->len, rsclp->len + rclp->len);
 242         rclp->len_lazy = 0;
 243         rclp->len = 0;
 244 }
 245
 246 /*
 247  * Move callbacks from the specified rcu_cblist to the beginning of the
 248  * done-callbacks segment of the specified rcu_segcblist.
 249  */
 250 void rcu_segcblist_insert_done_cbs(struct rcu_segcblist *rsclp,
 251                                    struct rcu_cblist *rclp)
 252 {
 253         int i;
 254
 255         if (!rclp->head)
 256                 return; /* No callbacks to move. */
 257         *rclp->tail = rsclp->head;
 258         rsclp->head = rclp->head;
 259         for (i = RCU_DONE_TAIL; i < RCU_CBLIST_NSEGS; i++)
 260                 if (&rsclp->head == rsclp->tails[i])
 261                         rsclp->tails[i] = rclp->tail;
 262                 else
 263                         break;
 264         rclp->head = NULL;
 265         rclp->tail = &rclp->head;
 266 }
 267
 268 /*
 269  * Move callbacks from the specified rcu_cblist to the end of the
 270  * new-callbacks segment of the specified rcu_segcblist.
 271  */
 272 void rcu_segcblist_insert_pend_cbs(struct rcu_segcblist *rsclp,
 273                                    struct rcu_cblist *rclp)
 274 {
 275         if (!rclp->head)
 276                 return; /* Nothing to do. */
 277         *rsclp->tails[RCU_NEXT_TAIL] = rclp->head;
 278         rsclp->tails[RCU_NEXT_TAIL] = rclp->tail;
 279         rclp->head = NULL;
 280         rclp->tail = &rclp->head;
 281 }
 282
 283 /*
 284  * Advance the callbacks in the specified rcu_segcblist structure based
 285  * on the current value passed in for the grace-period counter.
 286  */
 287 void rcu_segcblist_advance(struct rcu_segcblist *rsclp, unsigned long seq)
 288 {
 289         int i, j;
 290
 291         WARN_ON_ONCE(!rcu_segcblist_is_enabled(rsclp));
 292         if (rcu_segcblist_restempty(rsclp, RCU_DONE_TAIL))
 293                 return;
 294
 295         /*
 296          * Find all callbacks whose ->gp_seq numbers indicate that they
 297          * are ready to invoke, and put them into the RCU_DONE_TAIL segment.
 298          */
 299         for (i = RCU_WAIT_TAIL; i < RCU_NEXT_TAIL; i++) {
 300                 if (ULONG_CMP_LT(seq, rsclp->gp_seq[i]))
 301                         break;
 302                 rsclp->tails[RCU_DONE_TAIL] = rsclp->tails[i];
 303         }
 304
 305         /* If no callbacks moved, nothing more need be done. */
 306         if (i == RCU_WAIT_TAIL)
 307                 return;
 308
 309         /* Clean up tail pointers that might have been misordered above. */
 310         for (j = RCU_WAIT_TAIL; j < i; j++)
 311                 rsclp->tails[j] = rsclp->tails[RCU_DONE_TAIL];
 312
 313         /*
 314          * Callbacks moved, so clean up the misordered ->tails[] pointers
 315          * that now point into the middle of the list of ready-to-invoke
 316          * callbacks.  The overall effect is to copy down the later pointers
 317          * into the gap that was created by the now-ready segments.
 318          */
 319         for (j = RCU_WAIT_TAIL; i < RCU_NEXT_TAIL; i++, j++) {
 320                 if (rsclp->tails[j] == rsclp->tails[RCU_NEXT_TAIL])
 321                         break;  /* No more callbacks. */
 322                 rsclp->tails[j] = rsclp->tails[i];
 323                 rsclp->gp_seq[j] = rsclp->gp_seq[i];
 324         }
 325 }
 326
 327 /*
 328  * "Accelerate" callbacks based on more-accurate grace-period information.
 329  * The reason for this is that RCU does not synchronize the beginnings and
 330  * ends of grace periods, and that callbacks are posted locally.  This in
 331  * turn means that the callbacks must be labelled conservatively early
 332  * on, as getting exact information would degrade both performance and
 333  * scalability.  When more accurate grace-period information becomes
 334  * available, previously posted callbacks can be "accelerated", marking
 335  * them to complete at the end of the earlier grace period.
 336  *
 337  * This function operates on an rcu_segcblist structure, and also the
 338  * grace-period sequence number seq at which new callbacks would become
 339  * ready to invoke.  Returns true if there are callbacks that won't be
 340  * ready to invoke until seq, false otherwise.
 341  */
 342 bool rcu_segcblist_accelerate(struct rcu_segcblist *rsclp, unsigned long seq)
 343 {
 344         int i;
 345
 346         WARN_ON_ONCE(!rcu_segcblist_is_enabled(rsclp));
 347         if (rcu_segcblist_restempty(rsclp, RCU_DONE_TAIL))
 348                 return false;
 349
 350         /*
 351          * Find the segment preceding the oldest segment of callbacks
 352          * whose ->gp_seq[] completion is at or after that passed in via
 353          * "seq", skipping any empty segments.  This oldest segment, along
 354          * with any later segments, can be merged in with any newly arrived
 355          * callbacks in the RCU_NEXT_TAIL segment, and assigned "seq"
 356          * as their ->gp_seq[] grace-period completion sequence number.
 357          */
 358         for (i = RCU_NEXT_READY_TAIL; i > RCU_DONE_TAIL; i--)
 359                 if (rsclp->tails[i] != rsclp->tails[i - 1] &&
 360                     ULONG_CMP_LT(rsclp->gp_seq[i], seq))
 361                         break;
 362
 363         /*
 364          * If all the segments contain callbacks that correspond to
 365          * earlier grace-period sequence numbers than "seq", leave.
 366          * Assuming that the rcu_segcblist structure has enough
 367          * segments in its arrays, this can only happen if some of
 368          * the non-done segments contain callbacks that really are
 369          * ready to invoke.  This situation will get straightened
 370          * out by the next call to rcu_segcblist_advance().
 371          *
 372          * Also advance to the oldest segment of callbacks whose
 373          * ->gp_seq[] completion is at or after that passed in via "seq",
 374          * skipping any empty segments.
 375          */
 376         if (++i >= RCU_NEXT_TAIL)
 377                 return false;
 378
 379         /*
 380          * Merge all later callbacks, including newly arrived callbacks,
 381          * into the segment located by the for-loop above.  Assign "seq"
 382          * as the ->gp_seq[] value in order to correctly handle the case
 383          * where there were no pending callbacks in the rcu_segcblist
 384          * structure other than in the RCU_NEXT_TAIL segment.
 385          */
 386         for (; i < RCU_NEXT_TAIL; i++) {
 387                 rsclp->tails[i] = rsclp->tails[RCU_NEXT_TAIL];
 388                 rsclp->gp_seq[i] = seq;
 389         }
 390         return true;
 391 }
 392
 393 /*
 394  * Merge the source rcu_segcblist structure into the destination
 395  * rcu_segcblist structure, then initialize the source.  Any pending
 396  * callbacks from the source get to start over.  It is best to
 397  * advance and accelerate both the destination and the source
 398  * before merging.
 399  */
 400 void rcu_segcblist_merge(struct rcu_segcblist *dst_rsclp,
 401                          struct rcu_segcblist *src_rsclp)
 402 {
 403         struct rcu_cblist donecbs;
 404         struct rcu_cblist pendcbs;
 405
 406         rcu_cblist_init(&donecbs);
 407         rcu_cblist_init(&pendcbs);
 408         rcu_segcblist_extract_count(src_rsclp, &donecbs);
 409         rcu_segcblist_extract_done_cbs(src_rsclp, &donecbs);
 410         rcu_segcblist_extract_pend_cbs(src_rsclp, &pendcbs);
 411         rcu_segcblist_insert_count(dst_rsclp, &donecbs);
 412         rcu_segcblist_insert_done_cbs(dst_rsclp, &donecbs);
 413         rcu_segcblist_insert_pend_cbs(dst_rsclp, &pendcbs);
 414         rcu_segcblist_init(src_rsclp);
 415 }