1#ifndef _LINUX_RCULIST_H 2#define _LINUX_RCULIST_H 3 4#ifdef __KERNEL__ 5 6/* 7 * RCU-protected list version 8 */ 9#include <linux/list.h> 10#include <linux/rcupdate.h> 11 12/* 13 * Why is there no list_empty_rcu()? Because list_empty() serves this 14 * purpose. The list_empty() function fetches the RCU-protected pointer 15 * and compares it to the address of the list head, but neither dereferences 16 * this pointer itself nor provides this pointer to the caller. Therefore, 17 * it is not necessary to use rcu_dereference(), so that list_empty() can 18 * be used anywhere you would want to use a list_empty_rcu(). 19 */ 20 21/* 22 * INIT_LIST_HEAD_RCU - Initialize a list_head visible to RCU readers 23 * @list: list to be initialized 24 * 25 * You should instead use INIT_LIST_HEAD() for normal initialization and 26 * cleanup tasks, when readers have no access to the list being initialized. 27 * However, if the list being initialized is visible to readers, you 28 * need to keep the compiler from being too mischievous. 29 */ 30static inline void INIT_LIST_HEAD_RCU(struct list_head *list) 31{ 32 WRITE_ONCE(list->next, list); 33 WRITE_ONCE(list->prev, list); 34} 35 36/* 37 * return the ->next pointer of a list_head in an rcu safe 38 * way, we must not access it directly 39 */ 40#define list_next_rcu(list) (*((struct list_head __rcu **)(&(list)->next))) 41 42/* 43 * Insert a new entry between two known consecutive entries. 44 * 45 * This is only for internal list manipulation where we know 46 * the prev/next entries already! 47 */ 48#ifndef CONFIG_DEBUG_LIST 49static inline void __list_add_rcu(struct list_head *new, 50 struct list_head *prev, struct list_head *next) 51{ 52 new->next = next; 53 new->prev = prev; 54 rcu_assign_pointer(list_next_rcu(prev), new); 55 next->prev = new; 56} 57#else 58void __list_add_rcu(struct list_head *new, 59 struct list_head *prev, struct list_head *next); 60#endif 61 62/** 63 * list_add_rcu - add a new entry to rcu-protected list 64 * @new: new entry to be added 65 * @head: list head to add it after 66 * 67 * Insert a new entry after the specified head. 68 * This is good for implementing stacks. 69 * 70 * The caller must take whatever precautions are necessary 71 * (such as holding appropriate locks) to avoid racing 72 * with another list-mutation primitive, such as list_add_rcu() 73 * or list_del_rcu(), running on this same list. 74 * However, it is perfectly legal to run concurrently with 75 * the _rcu list-traversal primitives, such as 76 * list_for_each_entry_rcu(). 77 */ 78static inline void list_add_rcu(struct list_head *new, struct list_head *head) 79{ 80 __list_add_rcu(new, head, head->next); 81} 82 83/** 84 * list_add_tail_rcu - add a new entry to rcu-protected list 85 * @new: new entry to be added 86 * @head: list head to add it before 87 * 88 * Insert a new entry before the specified head. 89 * This is useful for implementing queues. 90 * 91 * The caller must take whatever precautions are necessary 92 * (such as holding appropriate locks) to avoid racing 93 * with another list-mutation primitive, such as list_add_tail_rcu() 94 * or list_del_rcu(), running on this same list. 95 * However, it is perfectly legal to run concurrently with 96 * the _rcu list-traversal primitives, such as 97 * list_for_each_entry_rcu(). 98 */ 99static inline void list_add_tail_rcu(struct list_head *new, 100 struct list_head *head) 101{ 102 __list_add_rcu(new, head->prev, head); 103} 104 105/** 106 * list_del_rcu - deletes entry from list without re-initialization 107 * @entry: the element to delete from the list. 108 * 109 * Note: list_empty() on entry does not return true after this, 110 * the entry is in an undefined state. It is useful for RCU based 111 * lockfree traversal. 112 * 113 * In particular, it means that we can not poison the forward 114 * pointers that may still be used for walking the list. 115 * 116 * The caller must take whatever precautions are necessary 117 * (such as holding appropriate locks) to avoid racing 118 * with another list-mutation primitive, such as list_del_rcu() 119 * or list_add_rcu(), running on this same list. 120 * However, it is perfectly legal to run concurrently with 121 * the _rcu list-traversal primitives, such as 122 * list_for_each_entry_rcu(). 123 * 124 * Note that the caller is not permitted to immediately free 125 * the newly deleted entry. Instead, either synchronize_rcu() 126 * or call_rcu() must be used to defer freeing until an RCU 127 * grace period has elapsed. 128 */ 129static inline void list_del_rcu(struct list_head *entry) 130{ 131 __list_del_entry(entry); 132 entry->prev = LIST_POISON2; 133} 134 135/** 136 * hlist_del_init_rcu - deletes entry from hash list with re-initialization 137 * @n: the element to delete from the hash list. 138 * 139 * Note: list_unhashed() on the node return true after this. It is 140 * useful for RCU based read lockfree traversal if the writer side 141 * must know if the list entry is still hashed or already unhashed. 142 * 143 * In particular, it means that we can not poison the forward pointers 144 * that may still be used for walking the hash list and we can only 145 * zero the pprev pointer so list_unhashed() will return true after 146 * this. 147 * 148 * The caller must take whatever precautions are necessary (such as 149 * holding appropriate locks) to avoid racing with another 150 * list-mutation primitive, such as hlist_add_head_rcu() or 151 * hlist_del_rcu(), running on this same list. However, it is 152 * perfectly legal to run concurrently with the _rcu list-traversal 153 * primitives, such as hlist_for_each_entry_rcu(). 154 */ 155static inline void hlist_del_init_rcu(struct hlist_node *n) 156{ 157 if (!hlist_unhashed(n)) { 158 __hlist_del(n); 159 n->pprev = NULL; 160 } 161} 162 163/** 164 * list_replace_rcu - replace old entry by new one 165 * @old : the element to be replaced 166 * @new : the new element to insert 167 * 168 * The @old entry will be replaced with the @new entry atomically. 169 * Note: @old should not be empty. 170 */ 171static inline void list_replace_rcu(struct list_head *old, 172 struct list_head *new) 173{ 174 new->next = old->next; 175 new->prev = old->prev; 176 rcu_assign_pointer(list_next_rcu(new->prev), new); 177 new->next->prev = new; 178 old->prev = LIST_POISON2; 179} 180 181/** 182 * list_splice_init_rcu - splice an RCU-protected list into an existing list. 183 * @list: the RCU-protected list to splice 184 * @head: the place in the list to splice the first list into 185 * @sync: function to sync: synchronize_rcu(), synchronize_sched(), ... 186 * 187 * @head can be RCU-read traversed concurrently with this function. 188 * 189 * Note that this function blocks. 190 * 191 * Important note: the caller must take whatever action is necessary to 192 * prevent any other updates to @head. In principle, it is possible 193 * to modify the list as soon as sync() begins execution. 194 * If this sort of thing becomes necessary, an alternative version 195 * based on call_rcu() could be created. But only if -really- 196 * needed -- there is no shortage of RCU API members. 197 */ 198static inline void list_splice_init_rcu(struct list_head *list, 199 struct list_head *head, 200 void (*sync)(void)) 201{ 202 struct list_head *first = list->next; 203 struct list_head *last = list->prev; 204 struct list_head *at = head->next; 205 206 if (list_empty(list)) 207 return; 208 209 /* 210 * "first" and "last" tracking list, so initialize it. RCU readers 211 * have access to this list, so we must use INIT_LIST_HEAD_RCU() 212 * instead of INIT_LIST_HEAD(). 213 */ 214 215 INIT_LIST_HEAD_RCU(list); 216 217 /* 218 * At this point, the list body still points to the source list. 219 * Wait for any readers to finish using the list before splicing 220 * the list body into the new list. Any new readers will see 221 * an empty list. 222 */ 223 224 sync(); 225 226 /* 227 * Readers are finished with the source list, so perform splice. 228 * The order is important if the new list is global and accessible 229 * to concurrent RCU readers. Note that RCU readers are not 230 * permitted to traverse the prev pointers without excluding 231 * this function. 232 */ 233 234 last->next = at; 235 rcu_assign_pointer(list_next_rcu(head), first); 236 first->prev = head; 237 at->prev = last; 238} 239 240/** 241 * list_entry_rcu - get the struct for this entry 242 * @ptr: the &struct list_head pointer. 243 * @type: the type of the struct this is embedded in. 244 * @member: the name of the list_head within the struct. 245 * 246 * This primitive may safely run concurrently with the _rcu list-mutation 247 * primitives such as list_add_rcu() as long as it's guarded by rcu_read_lock(). 248 */ 249#define list_entry_rcu(ptr, type, member) \ 250 container_of(lockless_dereference(ptr), type, member) 251 252/** 253 * Where are list_empty_rcu() and list_first_entry_rcu()? 254 * 255 * Implementing those functions following their counterparts list_empty() and 256 * list_first_entry() is not advisable because they lead to subtle race 257 * conditions as the following snippet shows: 258 * 259 * if (!list_empty_rcu(mylist)) { 260 * struct foo *bar = list_first_entry_rcu(mylist, struct foo, list_member); 261 * do_something(bar); 262 * } 263 * 264 * The list may not be empty when list_empty_rcu checks it, but it may be when 265 * list_first_entry_rcu rereads the ->next pointer. 266 * 267 * Rereading the ->next pointer is not a problem for list_empty() and 268 * list_first_entry() because they would be protected by a lock that blocks 269 * writers. 270 * 271 * See list_first_or_null_rcu for an alternative. 272 */ 273 274/** 275 * list_first_or_null_rcu - get the first element from a list 276 * @ptr: the list head to take the element from. 277 * @type: the type of the struct this is embedded in. 278 * @member: the name of the list_head within the struct. 279 * 280 * Note that if the list is empty, it returns NULL. 281 * 282 * This primitive may safely run concurrently with the _rcu list-mutation 283 * primitives such as list_add_rcu() as long as it's guarded by rcu_read_lock(). 284 */ 285#define list_first_or_null_rcu(ptr, type, member) \ 286({ \ 287 struct list_head *__ptr = (ptr); \ 288 struct list_head *__next = READ_ONCE(__ptr->next); \ 289 likely(__ptr != __next) ? list_entry_rcu(__next, type, member) : NULL; \ 290}) 291 292/** 293 * list_for_each_entry_rcu - iterate over rcu list of given type 294 * @pos: the type * to use as a loop cursor. 295 * @head: the head for your list. 296 * @member: the name of the list_head within the struct. 297 * 298 * This list-traversal primitive may safely run concurrently with 299 * the _rcu list-mutation primitives such as list_add_rcu() 300 * as long as the traversal is guarded by rcu_read_lock(). 301 */ 302#define list_for_each_entry_rcu(pos, head, member) \ 303 for (pos = list_entry_rcu((head)->next, typeof(*pos), member); \ 304 &pos->member != (head); \ 305 pos = list_entry_rcu(pos->member.next, typeof(*pos), member)) 306 307/** 308 * list_for_each_entry_continue_rcu - continue iteration over list of given type 309 * @pos: the type * to use as a loop cursor. 310 * @head: the head for your list. 311 * @member: the name of the list_head within the struct. 312 * 313 * Continue to iterate over list of given type, continuing after 314 * the current position. 315 */ 316#define list_for_each_entry_continue_rcu(pos, head, member) \ 317 for (pos = list_entry_rcu(pos->member.next, typeof(*pos), member); \ 318 &pos->member != (head); \ 319 pos = list_entry_rcu(pos->member.next, typeof(*pos), member)) 320 321/** 322 * hlist_del_rcu - deletes entry from hash list without re-initialization 323 * @n: the element to delete from the hash list. 324 * 325 * Note: list_unhashed() on entry does not return true after this, 326 * the entry is in an undefined state. It is useful for RCU based 327 * lockfree traversal. 328 * 329 * In particular, it means that we can not poison the forward 330 * pointers that may still be used for walking the hash list. 331 * 332 * The caller must take whatever precautions are necessary 333 * (such as holding appropriate locks) to avoid racing 334 * with another list-mutation primitive, such as hlist_add_head_rcu() 335 * or hlist_del_rcu(), running on this same list. 336 * However, it is perfectly legal to run concurrently with 337 * the _rcu list-traversal primitives, such as 338 * hlist_for_each_entry(). 339 */ 340static inline void hlist_del_rcu(struct hlist_node *n) 341{ 342 __hlist_del(n); 343 n->pprev = LIST_POISON2; 344} 345 346/** 347 * hlist_replace_rcu - replace old entry by new one 348 * @old : the element to be replaced 349 * @new : the new element to insert 350 * 351 * The @old entry will be replaced with the @new entry atomically. 352 */ 353static inline void hlist_replace_rcu(struct hlist_node *old, 354 struct hlist_node *new) 355{ 356 struct hlist_node *next = old->next; 357 358 new->next = next; 359 new->pprev = old->pprev; 360 rcu_assign_pointer(*(struct hlist_node __rcu **)new->pprev, new); 361 if (next) 362 new->next->pprev = &new->next; 363 old->pprev = LIST_POISON2; 364} 365 366/* 367 * return the first or the next element in an RCU protected hlist 368 */ 369#define hlist_first_rcu(head) (*((struct hlist_node __rcu **)(&(head)->first))) 370#define hlist_next_rcu(node) (*((struct hlist_node __rcu **)(&(node)->next))) 371#define hlist_pprev_rcu(node) (*((struct hlist_node __rcu **)((node)->pprev))) 372 373/** 374 * hlist_add_head_rcu 375 * @n: the element to add to the hash list. 376 * @h: the list to add to. 377 * 378 * Description: 379 * Adds the specified element to the specified hlist, 380 * while permitting racing traversals. 381 * 382 * The caller must take whatever precautions are necessary 383 * (such as holding appropriate locks) to avoid racing 384 * with another list-mutation primitive, such as hlist_add_head_rcu() 385 * or hlist_del_rcu(), running on this same list. 386 * However, it is perfectly legal to run concurrently with 387 * the _rcu list-traversal primitives, such as 388 * hlist_for_each_entry_rcu(), used to prevent memory-consistency 389 * problems on Alpha CPUs. Regardless of the type of CPU, the 390 * list-traversal primitive must be guarded by rcu_read_lock(). 391 */ 392static inline void hlist_add_head_rcu(struct hlist_node *n, 393 struct hlist_head *h) 394{ 395 struct hlist_node *first = h->first; 396 397 n->next = first; 398 n->pprev = &h->first; 399 rcu_assign_pointer(hlist_first_rcu(h), n); 400 if (first) 401 first->pprev = &n->next; 402} 403 404/** 405 * hlist_add_before_rcu 406 * @n: the new element to add to the hash list. 407 * @next: the existing element to add the new element before. 408 * 409 * Description: 410 * Adds the specified element to the specified hlist 411 * before the specified node while permitting racing traversals. 412 * 413 * The caller must take whatever precautions are necessary 414 * (such as holding appropriate locks) to avoid racing 415 * with another list-mutation primitive, such as hlist_add_head_rcu() 416 * or hlist_del_rcu(), running on this same list. 417 * However, it is perfectly legal to run concurrently with 418 * the _rcu list-traversal primitives, such as 419 * hlist_for_each_entry_rcu(), used to prevent memory-consistency 420 * problems on Alpha CPUs. 421 */ 422static inline void hlist_add_before_rcu(struct hlist_node *n, 423 struct hlist_node *next) 424{ 425 n->pprev = next->pprev; 426 n->next = next; 427 rcu_assign_pointer(hlist_pprev_rcu(n), n); 428 next->pprev = &n->next; 429} 430 431/** 432 * hlist_add_behind_rcu 433 * @n: the new element to add to the hash list. 434 * @prev: the existing element to add the new element after. 435 * 436 * Description: 437 * Adds the specified element to the specified hlist 438 * after the specified node while permitting racing traversals. 439 * 440 * The caller must take whatever precautions are necessary 441 * (such as holding appropriate locks) to avoid racing 442 * with another list-mutation primitive, such as hlist_add_head_rcu() 443 * or hlist_del_rcu(), running on this same list. 444 * However, it is perfectly legal to run concurrently with 445 * the _rcu list-traversal primitives, such as 446 * hlist_for_each_entry_rcu(), used to prevent memory-consistency 447 * problems on Alpha CPUs. 448 */ 449static inline void hlist_add_behind_rcu(struct hlist_node *n, 450 struct hlist_node *prev) 451{ 452 n->next = prev->next; 453 n->pprev = &prev->next; 454 rcu_assign_pointer(hlist_next_rcu(prev), n); 455 if (n->next) 456 n->next->pprev = &n->next; 457} 458 459#define __hlist_for_each_rcu(pos, head) \ 460 for (pos = rcu_dereference(hlist_first_rcu(head)); \ 461 pos; \ 462 pos = rcu_dereference(hlist_next_rcu(pos))) 463 464/** 465 * hlist_for_each_entry_rcu - iterate over rcu list of given type 466 * @pos: the type * to use as a loop cursor. 467 * @head: the head for your list. 468 * @member: the name of the hlist_node within the struct. 469 * 470 * This list-traversal primitive may safely run concurrently with 471 * the _rcu list-mutation primitives such as hlist_add_head_rcu() 472 * as long as the traversal is guarded by rcu_read_lock(). 473 */ 474#define hlist_for_each_entry_rcu(pos, head, member) \ 475 for (pos = hlist_entry_safe (rcu_dereference_raw(hlist_first_rcu(head)),\ 476 typeof(*(pos)), member); \ 477 pos; \ 478 pos = hlist_entry_safe(rcu_dereference_raw(hlist_next_rcu(\ 479 &(pos)->member)), typeof(*(pos)), member)) 480 481/** 482 * hlist_for_each_entry_rcu_notrace - iterate over rcu list of given type (for tracing) 483 * @pos: the type * to use as a loop cursor. 484 * @head: the head for your list. 485 * @member: the name of the hlist_node within the struct. 486 * 487 * This list-traversal primitive may safely run concurrently with 488 * the _rcu list-mutation primitives such as hlist_add_head_rcu() 489 * as long as the traversal is guarded by rcu_read_lock(). 490 * 491 * This is the same as hlist_for_each_entry_rcu() except that it does 492 * not do any RCU debugging or tracing. 493 */ 494#define hlist_for_each_entry_rcu_notrace(pos, head, member) \ 495 for (pos = hlist_entry_safe (rcu_dereference_raw_notrace(hlist_first_rcu(head)),\ 496 typeof(*(pos)), member); \ 497 pos; \ 498 pos = hlist_entry_safe(rcu_dereference_raw_notrace(hlist_next_rcu(\ 499 &(pos)->member)), typeof(*(pos)), member)) 500 501/** 502 * hlist_for_each_entry_rcu_bh - iterate over rcu list of given type 503 * @pos: the type * to use as a loop cursor. 504 * @head: the head for your list. 505 * @member: the name of the hlist_node within the struct. 506 * 507 * This list-traversal primitive may safely run concurrently with 508 * the _rcu list-mutation primitives such as hlist_add_head_rcu() 509 * as long as the traversal is guarded by rcu_read_lock(). 510 */ 511#define hlist_for_each_entry_rcu_bh(pos, head, member) \ 512 for (pos = hlist_entry_safe(rcu_dereference_bh(hlist_first_rcu(head)),\ 513 typeof(*(pos)), member); \ 514 pos; \ 515 pos = hlist_entry_safe(rcu_dereference_bh(hlist_next_rcu(\ 516 &(pos)->member)), typeof(*(pos)), member)) 517 518/** 519 * hlist_for_each_entry_continue_rcu - iterate over a hlist continuing after current point 520 * @pos: the type * to use as a loop cursor. 521 * @member: the name of the hlist_node within the struct. 522 */ 523#define hlist_for_each_entry_continue_rcu(pos, member) \ 524 for (pos = hlist_entry_safe(rcu_dereference_raw(hlist_next_rcu( \ 525 &(pos)->member)), typeof(*(pos)), member); \ 526 pos; \ 527 pos = hlist_entry_safe(rcu_dereference_raw(hlist_next_rcu( \ 528 &(pos)->member)), typeof(*(pos)), member)) 529 530/** 531 * hlist_for_each_entry_continue_rcu_bh - iterate over a hlist continuing after current point 532 * @pos: the type * to use as a loop cursor. 533 * @member: the name of the hlist_node within the struct. 534 */ 535#define hlist_for_each_entry_continue_rcu_bh(pos, member) \ 536 for (pos = hlist_entry_safe(rcu_dereference_bh(hlist_next_rcu( \ 537 &(pos)->member)), typeof(*(pos)), member); \ 538 pos; \ 539 pos = hlist_entry_safe(rcu_dereference_bh(hlist_next_rcu( \ 540 &(pos)->member)), typeof(*(pos)), member)) 541 542/** 543 * hlist_for_each_entry_from_rcu - iterate over a hlist continuing from current point 544 * @pos: the type * to use as a loop cursor. 545 * @member: the name of the hlist_node within the struct. 546 */ 547#define hlist_for_each_entry_from_rcu(pos, member) \ 548 for (; pos; \ 549 pos = hlist_entry_safe(rcu_dereference_raw(hlist_next_rcu( \ 550 &(pos)->member)), typeof(*(pos)), member)) 551 552#endif /* __KERNEL__ */ 553#endif 554