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 ACCESS_ONCE(list->next) = list; 33 ACCESS_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_struct 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({ \ 251 typeof(*ptr) __rcu *__ptr = (typeof(*ptr) __rcu __force *)ptr; \ 252 container_of((typeof(ptr))rcu_dereference_raw(__ptr), type, member); \ 253}) 254 255/** 256 * Where are list_empty_rcu() and list_first_entry_rcu()? 257 * 258 * Implementing those functions following their counterparts list_empty() and 259 * list_first_entry() is not advisable because they lead to subtle race 260 * conditions as the following snippet shows: 261 * 262 * if (!list_empty_rcu(mylist)) { 263 * struct foo *bar = list_first_entry_rcu(mylist, struct foo, list_member); 264 * do_something(bar); 265 * } 266 * 267 * The list may not be empty when list_empty_rcu checks it, but it may be when 268 * list_first_entry_rcu rereads the ->next pointer. 269 * 270 * Rereading the ->next pointer is not a problem for list_empty() and 271 * list_first_entry() because they would be protected by a lock that blocks 272 * writers. 273 * 274 * See list_first_or_null_rcu for an alternative. 275 */ 276 277/** 278 * list_first_or_null_rcu - get the first element from a list 279 * @ptr: the list head to take the element from. 280 * @type: the type of the struct this is embedded in. 281 * @member: the name of the list_struct within the struct. 282 * 283 * Note that if the list is empty, it returns NULL. 284 * 285 * This primitive may safely run concurrently with the _rcu list-mutation 286 * primitives such as list_add_rcu() as long as it's guarded by rcu_read_lock(). 287 */ 288#define list_first_or_null_rcu(ptr, type, member) \ 289({ \ 290 struct list_head *__ptr = (ptr); \ 291 struct list_head *__next = ACCESS_ONCE(__ptr->next); \ 292 likely(__ptr != __next) ? list_entry_rcu(__next, type, member) : NULL; \ 293}) 294 295/** 296 * list_for_each_entry_rcu - iterate over rcu list of given type 297 * @pos: the type * to use as a loop cursor. 298 * @head: the head for your list. 299 * @member: the name of the list_struct within the struct. 300 * 301 * This list-traversal primitive may safely run concurrently with 302 * the _rcu list-mutation primitives such as list_add_rcu() 303 * as long as the traversal is guarded by rcu_read_lock(). 304 */ 305#define list_for_each_entry_rcu(pos, head, member) \ 306 for (pos = list_entry_rcu((head)->next, typeof(*pos), member); \ 307 &pos->member != (head); \ 308 pos = list_entry_rcu(pos->member.next, typeof(*pos), member)) 309 310/** 311 * list_for_each_entry_continue_rcu - continue iteration over list of given type 312 * @pos: the type * to use as a loop cursor. 313 * @head: the head for your list. 314 * @member: the name of the list_struct within the struct. 315 * 316 * Continue to iterate over list of given type, continuing after 317 * the current position. 318 */ 319#define list_for_each_entry_continue_rcu(pos, head, member) \ 320 for (pos = list_entry_rcu(pos->member.next, typeof(*pos), member); \ 321 &pos->member != (head); \ 322 pos = list_entry_rcu(pos->member.next, typeof(*pos), member)) 323 324/** 325 * hlist_del_rcu - deletes entry from hash list without re-initialization 326 * @n: the element to delete from the hash list. 327 * 328 * Note: list_unhashed() on entry does not return true after this, 329 * the entry is in an undefined state. It is useful for RCU based 330 * lockfree traversal. 331 * 332 * In particular, it means that we can not poison the forward 333 * pointers that may still be used for walking the hash list. 334 * 335 * The caller must take whatever precautions are necessary 336 * (such as holding appropriate locks) to avoid racing 337 * with another list-mutation primitive, such as hlist_add_head_rcu() 338 * or hlist_del_rcu(), running on this same list. 339 * However, it is perfectly legal to run concurrently with 340 * the _rcu list-traversal primitives, such as 341 * hlist_for_each_entry(). 342 */ 343static inline void hlist_del_rcu(struct hlist_node *n) 344{ 345 __hlist_del(n); 346 n->pprev = LIST_POISON2; 347} 348 349/** 350 * hlist_replace_rcu - replace old entry by new one 351 * @old : the element to be replaced 352 * @new : the new element to insert 353 * 354 * The @old entry will be replaced with the @new entry atomically. 355 */ 356static inline void hlist_replace_rcu(struct hlist_node *old, 357 struct hlist_node *new) 358{ 359 struct hlist_node *next = old->next; 360 361 new->next = next; 362 new->pprev = old->pprev; 363 rcu_assign_pointer(*(struct hlist_node __rcu **)new->pprev, new); 364 if (next) 365 new->next->pprev = &new->next; 366 old->pprev = LIST_POISON2; 367} 368 369/* 370 * return the first or the next element in an RCU protected hlist 371 */ 372#define hlist_first_rcu(head) (*((struct hlist_node __rcu **)(&(head)->first))) 373#define hlist_next_rcu(node) (*((struct hlist_node __rcu **)(&(node)->next))) 374#define hlist_pprev_rcu(node) (*((struct hlist_node __rcu **)((node)->pprev))) 375 376/** 377 * hlist_add_head_rcu 378 * @n: the element to add to the hash list. 379 * @h: the list to add to. 380 * 381 * Description: 382 * Adds the specified element to the specified hlist, 383 * while permitting racing traversals. 384 * 385 * The caller must take whatever precautions are necessary 386 * (such as holding appropriate locks) to avoid racing 387 * with another list-mutation primitive, such as hlist_add_head_rcu() 388 * or hlist_del_rcu(), running on this same list. 389 * However, it is perfectly legal to run concurrently with 390 * the _rcu list-traversal primitives, such as 391 * hlist_for_each_entry_rcu(), used to prevent memory-consistency 392 * problems on Alpha CPUs. Regardless of the type of CPU, the 393 * list-traversal primitive must be guarded by rcu_read_lock(). 394 */ 395static inline void hlist_add_head_rcu(struct hlist_node *n, 396 struct hlist_head *h) 397{ 398 struct hlist_node *first = h->first; 399 400 n->next = first; 401 n->pprev = &h->first; 402 rcu_assign_pointer(hlist_first_rcu(h), n); 403 if (first) 404 first->pprev = &n->next; 405} 406 407/** 408 * hlist_add_before_rcu 409 * @n: the new element to add to the hash list. 410 * @next: the existing element to add the new element before. 411 * 412 * Description: 413 * Adds the specified element to the specified hlist 414 * before the specified node while permitting racing traversals. 415 * 416 * The caller must take whatever precautions are necessary 417 * (such as holding appropriate locks) to avoid racing 418 * with another list-mutation primitive, such as hlist_add_head_rcu() 419 * or hlist_del_rcu(), running on this same list. 420 * However, it is perfectly legal to run concurrently with 421 * the _rcu list-traversal primitives, such as 422 * hlist_for_each_entry_rcu(), used to prevent memory-consistency 423 * problems on Alpha CPUs. 424 */ 425static inline void hlist_add_before_rcu(struct hlist_node *n, 426 struct hlist_node *next) 427{ 428 n->pprev = next->pprev; 429 n->next = next; 430 rcu_assign_pointer(hlist_pprev_rcu(n), n); 431 next->pprev = &n->next; 432} 433 434/** 435 * hlist_add_behind_rcu 436 * @n: the new element to add to the hash list. 437 * @prev: the existing element to add the new element after. 438 * 439 * Description: 440 * Adds the specified element to the specified hlist 441 * after the specified node while permitting racing traversals. 442 * 443 * The caller must take whatever precautions are necessary 444 * (such as holding appropriate locks) to avoid racing 445 * with another list-mutation primitive, such as hlist_add_head_rcu() 446 * or hlist_del_rcu(), running on this same list. 447 * However, it is perfectly legal to run concurrently with 448 * the _rcu list-traversal primitives, such as 449 * hlist_for_each_entry_rcu(), used to prevent memory-consistency 450 * problems on Alpha CPUs. 451 */ 452static inline void hlist_add_behind_rcu(struct hlist_node *n, 453 struct hlist_node *prev) 454{ 455 n->next = prev->next; 456 n->pprev = &prev->next; 457 rcu_assign_pointer(hlist_next_rcu(prev), n); 458 if (n->next) 459 n->next->pprev = &n->next; 460} 461 462#define __hlist_for_each_rcu(pos, head) \ 463 for (pos = rcu_dereference(hlist_first_rcu(head)); \ 464 pos; \ 465 pos = rcu_dereference(hlist_next_rcu(pos))) 466 467/** 468 * hlist_for_each_entry_rcu - iterate over rcu list of given type 469 * @pos: the type * to use as a loop cursor. 470 * @head: the head for your list. 471 * @member: the name of the hlist_node within the struct. 472 * 473 * This list-traversal primitive may safely run concurrently with 474 * the _rcu list-mutation primitives such as hlist_add_head_rcu() 475 * as long as the traversal is guarded by rcu_read_lock(). 476 */ 477#define hlist_for_each_entry_rcu(pos, head, member) \ 478 for (pos = hlist_entry_safe (rcu_dereference_raw(hlist_first_rcu(head)),\ 479 typeof(*(pos)), member); \ 480 pos; \ 481 pos = hlist_entry_safe(rcu_dereference_raw(hlist_next_rcu(\ 482 &(pos)->member)), typeof(*(pos)), member)) 483 484/** 485 * hlist_for_each_entry_rcu_notrace - iterate over rcu list of given type (for tracing) 486 * @pos: the type * to use as a loop cursor. 487 * @head: the head for your list. 488 * @member: the name of the hlist_node within the struct. 489 * 490 * This list-traversal primitive may safely run concurrently with 491 * the _rcu list-mutation primitives such as hlist_add_head_rcu() 492 * as long as the traversal is guarded by rcu_read_lock(). 493 * 494 * This is the same as hlist_for_each_entry_rcu() except that it does 495 * not do any RCU debugging or tracing. 496 */ 497#define hlist_for_each_entry_rcu_notrace(pos, head, member) \ 498 for (pos = hlist_entry_safe (rcu_dereference_raw_notrace(hlist_first_rcu(head)),\ 499 typeof(*(pos)), member); \ 500 pos; \ 501 pos = hlist_entry_safe(rcu_dereference_raw_notrace(hlist_next_rcu(\ 502 &(pos)->member)), typeof(*(pos)), member)) 503 504/** 505 * hlist_for_each_entry_rcu_bh - iterate over rcu list of given type 506 * @pos: the type * to use as a loop cursor. 507 * @head: the head for your list. 508 * @member: the name of the hlist_node within the struct. 509 * 510 * This list-traversal primitive may safely run concurrently with 511 * the _rcu list-mutation primitives such as hlist_add_head_rcu() 512 * as long as the traversal is guarded by rcu_read_lock(). 513 */ 514#define hlist_for_each_entry_rcu_bh(pos, head, member) \ 515 for (pos = hlist_entry_safe(rcu_dereference_bh(hlist_first_rcu(head)),\ 516 typeof(*(pos)), member); \ 517 pos; \ 518 pos = hlist_entry_safe(rcu_dereference_bh(hlist_next_rcu(\ 519 &(pos)->member)), typeof(*(pos)), member)) 520 521/** 522 * hlist_for_each_entry_continue_rcu - iterate over a hlist continuing after current point 523 * @pos: the type * to use as a loop cursor. 524 * @member: the name of the hlist_node within the struct. 525 */ 526#define hlist_for_each_entry_continue_rcu(pos, member) \ 527 for (pos = hlist_entry_safe(rcu_dereference((pos)->member.next),\ 528 typeof(*(pos)), member); \ 529 pos; \ 530 pos = hlist_entry_safe(rcu_dereference((pos)->member.next),\ 531 typeof(*(pos)), member)) 532 533/** 534 * hlist_for_each_entry_continue_rcu_bh - iterate over a hlist continuing after current point 535 * @pos: the type * to use as a loop cursor. 536 * @member: the name of the hlist_node within the struct. 537 */ 538#define hlist_for_each_entry_continue_rcu_bh(pos, member) \ 539 for (pos = hlist_entry_safe(rcu_dereference_bh((pos)->member.next),\ 540 typeof(*(pos)), member); \ 541 pos; \ 542 pos = hlist_entry_safe(rcu_dereference_bh((pos)->member.next),\ 543 typeof(*(pos)), member)) 544 545 546#endif /* __KERNEL__ */ 547#endif 548