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