rculist.h 29 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806
  1. /* SPDX-License-Identifier: GPL-2.0 */
  2. #ifndef _LINUX_RCULIST_H
  3. #define _LINUX_RCULIST_H
  4. #ifdef __KERNEL__
  5. /*
  6. * RCU-protected list version
  7. */
  8. #include <linux/list.h>
  9. #include <linux/rcupdate.h>
  10. /*
  11. * Why is there no list_empty_rcu()? Because list_empty() serves this
  12. * purpose. The list_empty() function fetches the RCU-protected pointer
  13. * and compares it to the address of the list head, but neither dereferences
  14. * this pointer itself nor provides this pointer to the caller. Therefore,
  15. * it is not necessary to use rcu_dereference(), so that list_empty() can
  16. * be used anywhere you would want to use a list_empty_rcu().
  17. */
  18. /*
  19. * INIT_LIST_HEAD_RCU - Initialize a list_head visible to RCU readers
  20. * @list: list to be initialized
  21. *
  22. * You should instead use INIT_LIST_HEAD() for normal initialization and
  23. * cleanup tasks, when readers have no access to the list being initialized.
  24. * However, if the list being initialized is visible to readers, you
  25. * need to keep the compiler from being too mischievous.
  26. */
  27. static inline void INIT_LIST_HEAD_RCU(struct list_head *list)
  28. {
  29. WRITE_ONCE(list->next, list);
  30. WRITE_ONCE(list->prev, list);
  31. }
  32. /*
  33. * return the ->next pointer of a list_head in an rcu safe
  34. * way, we must not access it directly
  35. */
  36. #define list_next_rcu(list) (*((struct list_head __rcu **)(&(list)->next)))
  37. /**
  38. * list_tail_rcu - returns the prev pointer of the head of the list
  39. * @head: the head of the list
  40. *
  41. * Note: This should only be used with the list header, and even then
  42. * only if list_del() and similar primitives are not also used on the
  43. * list header.
  44. */
  45. #define list_tail_rcu(head) (*((struct list_head __rcu **)(&(head)->prev)))
  46. /*
  47. * Check during list traversal that we are within an RCU reader
  48. */
  49. #define check_arg_count_one(dummy)
  50. #ifdef CONFIG_PROVE_RCU_LIST
  51. #define __list_check_rcu(dummy, cond, extra...) \
  52. ({ \
  53. check_arg_count_one(extra); \
  54. RCU_LOCKDEP_WARN(!(cond) && !rcu_read_lock_any_held(), \
  55. "RCU-list traversed in non-reader section!"); \
  56. })
  57. #define __list_check_srcu(cond) \
  58. ({ \
  59. RCU_LOCKDEP_WARN(!(cond), \
  60. "RCU-list traversed without holding the required lock!");\
  61. })
  62. #else
  63. #define __list_check_rcu(dummy, cond, extra...) \
  64. ({ check_arg_count_one(extra); })
  65. #define __list_check_srcu(cond) ({ })
  66. #endif
  67. /*
  68. * Insert a new entry between two known consecutive entries.
  69. *
  70. * This is only for internal list manipulation where we know
  71. * the prev/next entries already!
  72. */
  73. static inline void __list_add_rcu(struct list_head *new,
  74. struct list_head *prev, struct list_head *next)
  75. {
  76. if (!__list_add_valid(new, prev, next))
  77. return;
  78. new->next = next;
  79. new->prev = prev;
  80. rcu_assign_pointer(list_next_rcu(prev), new);
  81. next->prev = new;
  82. }
  83. /**
  84. * list_add_rcu - add a new entry to rcu-protected list
  85. * @new: new entry to be added
  86. * @head: list head to add it after
  87. *
  88. * Insert a new entry after the specified head.
  89. * This is good for implementing stacks.
  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_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. */
  99. static inline void list_add_rcu(struct list_head *new, struct list_head *head)
  100. {
  101. __list_add_rcu(new, head, head->next);
  102. }
  103. /**
  104. * list_add_tail_rcu - add a new entry to rcu-protected list
  105. * @new: new entry to be added
  106. * @head: list head to add it before
  107. *
  108. * Insert a new entry before the specified head.
  109. * This is useful for implementing queues.
  110. *
  111. * The caller must take whatever precautions are necessary
  112. * (such as holding appropriate locks) to avoid racing
  113. * with another list-mutation primitive, such as list_add_tail_rcu()
  114. * or list_del_rcu(), running on this same list.
  115. * However, it is perfectly legal to run concurrently with
  116. * the _rcu list-traversal primitives, such as
  117. * list_for_each_entry_rcu().
  118. */
  119. static inline void list_add_tail_rcu(struct list_head *new,
  120. struct list_head *head)
  121. {
  122. __list_add_rcu(new, head->prev, head);
  123. }
  124. /**
  125. * list_del_rcu - deletes entry from list without re-initialization
  126. * @entry: the element to delete from the list.
  127. *
  128. * Note: list_empty() on entry does not return true after this,
  129. * the entry is in an undefined state. It is useful for RCU based
  130. * lockfree traversal.
  131. *
  132. * In particular, it means that we can not poison the forward
  133. * pointers that may still be used for walking the list.
  134. *
  135. * The caller must take whatever precautions are necessary
  136. * (such as holding appropriate locks) to avoid racing
  137. * with another list-mutation primitive, such as list_del_rcu()
  138. * or list_add_rcu(), running on this same list.
  139. * However, it is perfectly legal to run concurrently with
  140. * the _rcu list-traversal primitives, such as
  141. * list_for_each_entry_rcu().
  142. *
  143. * Note that the caller is not permitted to immediately free
  144. * the newly deleted entry. Instead, either synchronize_rcu()
  145. * or call_rcu() must be used to defer freeing until an RCU
  146. * grace period has elapsed.
  147. */
  148. static inline void list_del_rcu(struct list_head *entry)
  149. {
  150. __list_del_entry(entry);
  151. entry->prev = LIST_POISON2;
  152. }
  153. /**
  154. * hlist_del_init_rcu - deletes entry from hash list with re-initialization
  155. * @n: the element to delete from the hash list.
  156. *
  157. * Note: list_unhashed() on the node return true after this. It is
  158. * useful for RCU based read lockfree traversal if the writer side
  159. * must know if the list entry is still hashed or already unhashed.
  160. *
  161. * In particular, it means that we can not poison the forward pointers
  162. * that may still be used for walking the hash list and we can only
  163. * zero the pprev pointer so list_unhashed() will return true after
  164. * this.
  165. *
  166. * The caller must take whatever precautions are necessary (such as
  167. * holding appropriate locks) to avoid racing with another
  168. * list-mutation primitive, such as hlist_add_head_rcu() or
  169. * hlist_del_rcu(), running on this same list. However, it is
  170. * perfectly legal to run concurrently with the _rcu list-traversal
  171. * primitives, such as hlist_for_each_entry_rcu().
  172. */
  173. static inline void hlist_del_init_rcu(struct hlist_node *n)
  174. {
  175. if (!hlist_unhashed(n)) {
  176. __hlist_del(n);
  177. WRITE_ONCE(n->pprev, NULL);
  178. }
  179. }
  180. /**
  181. * list_replace_rcu - replace old entry by new one
  182. * @old : the element to be replaced
  183. * @new : the new element to insert
  184. *
  185. * The @old entry will be replaced with the @new entry atomically.
  186. * Note: @old should not be empty.
  187. */
  188. static inline void list_replace_rcu(struct list_head *old,
  189. struct list_head *new)
  190. {
  191. new->next = old->next;
  192. new->prev = old->prev;
  193. rcu_assign_pointer(list_next_rcu(new->prev), new);
  194. new->next->prev = new;
  195. old->prev = LIST_POISON2;
  196. }
  197. /**
  198. * __list_splice_init_rcu - join an RCU-protected list into an existing list.
  199. * @list: the RCU-protected list to splice
  200. * @prev: points to the last element of the existing list
  201. * @next: points to the first element of the existing list
  202. * @sync: synchronize_rcu, synchronize_rcu_expedited, ...
  203. *
  204. * The list pointed to by @prev and @next can be RCU-read traversed
  205. * concurrently with this function.
  206. *
  207. * Note that this function blocks.
  208. *
  209. * Important note: the caller must take whatever action is necessary to prevent
  210. * any other updates to the existing list. In principle, it is possible to
  211. * modify the list as soon as sync() begins execution. If this sort of thing
  212. * becomes necessary, an alternative version based on call_rcu() could be
  213. * created. But only if -really- needed -- there is no shortage of RCU API
  214. * members.
  215. */
  216. static inline void __list_splice_init_rcu(struct list_head *list,
  217. struct list_head *prev,
  218. struct list_head *next,
  219. void (*sync)(void))
  220. {
  221. struct list_head *first = list->next;
  222. struct list_head *last = list->prev;
  223. /*
  224. * "first" and "last" tracking list, so initialize it. RCU readers
  225. * have access to this list, so we must use INIT_LIST_HEAD_RCU()
  226. * instead of INIT_LIST_HEAD().
  227. */
  228. INIT_LIST_HEAD_RCU(list);
  229. /*
  230. * At this point, the list body still points to the source list.
  231. * Wait for any readers to finish using the list before splicing
  232. * the list body into the new list. Any new readers will see
  233. * an empty list.
  234. */
  235. sync();
  236. ASSERT_EXCLUSIVE_ACCESS(*first);
  237. ASSERT_EXCLUSIVE_ACCESS(*last);
  238. /*
  239. * Readers are finished with the source list, so perform splice.
  240. * The order is important if the new list is global and accessible
  241. * to concurrent RCU readers. Note that RCU readers are not
  242. * permitted to traverse the prev pointers without excluding
  243. * this function.
  244. */
  245. last->next = next;
  246. rcu_assign_pointer(list_next_rcu(prev), first);
  247. first->prev = prev;
  248. next->prev = last;
  249. }
  250. /**
  251. * list_splice_init_rcu - splice an RCU-protected list into an existing list,
  252. * designed for stacks.
  253. * @list: the RCU-protected list to splice
  254. * @head: the place in the existing list to splice the first list into
  255. * @sync: synchronize_rcu, synchronize_rcu_expedited, ...
  256. */
  257. static inline void list_splice_init_rcu(struct list_head *list,
  258. struct list_head *head,
  259. void (*sync)(void))
  260. {
  261. if (!list_empty(list))
  262. __list_splice_init_rcu(list, head, head->next, sync);
  263. }
  264. /**
  265. * list_splice_tail_init_rcu - splice an RCU-protected list into an existing
  266. * list, designed for queues.
  267. * @list: the RCU-protected list to splice
  268. * @head: the place in the existing list to splice the first list into
  269. * @sync: synchronize_rcu, synchronize_rcu_expedited, ...
  270. */
  271. static inline void list_splice_tail_init_rcu(struct list_head *list,
  272. struct list_head *head,
  273. void (*sync)(void))
  274. {
  275. if (!list_empty(list))
  276. __list_splice_init_rcu(list, head->prev, head, sync);
  277. }
  278. /**
  279. * list_entry_rcu - get the struct for this entry
  280. * @ptr: the &struct list_head pointer.
  281. * @type: the type of the struct this is embedded in.
  282. * @member: the name of the list_head within the struct.
  283. *
  284. * This primitive may safely run concurrently with the _rcu list-mutation
  285. * primitives such as list_add_rcu() as long as it's guarded by rcu_read_lock().
  286. */
  287. #define list_entry_rcu(ptr, type, member) \
  288. container_of(READ_ONCE(ptr), type, member)
  289. /*
  290. * Where are list_empty_rcu() and list_first_entry_rcu()?
  291. *
  292. * Implementing those functions following their counterparts list_empty() and
  293. * list_first_entry() is not advisable because they lead to subtle race
  294. * conditions as the following snippet shows:
  295. *
  296. * if (!list_empty_rcu(mylist)) {
  297. * struct foo *bar = list_first_entry_rcu(mylist, struct foo, list_member);
  298. * do_something(bar);
  299. * }
  300. *
  301. * The list may not be empty when list_empty_rcu checks it, but it may be when
  302. * list_first_entry_rcu rereads the ->next pointer.
  303. *
  304. * Rereading the ->next pointer is not a problem for list_empty() and
  305. * list_first_entry() because they would be protected by a lock that blocks
  306. * writers.
  307. *
  308. * See list_first_or_null_rcu for an alternative.
  309. */
  310. /**
  311. * list_first_or_null_rcu - get the first element from a list
  312. * @ptr: the list head to take the element from.
  313. * @type: the type of the struct this is embedded in.
  314. * @member: the name of the list_head within the struct.
  315. *
  316. * Note that if the list is empty, it returns NULL.
  317. *
  318. * This primitive may safely run concurrently with the _rcu list-mutation
  319. * primitives such as list_add_rcu() as long as it's guarded by rcu_read_lock().
  320. */
  321. #define list_first_or_null_rcu(ptr, type, member) \
  322. ({ \
  323. struct list_head *__ptr = (ptr); \
  324. struct list_head *__next = READ_ONCE(__ptr->next); \
  325. likely(__ptr != __next) ? list_entry_rcu(__next, type, member) : NULL; \
  326. })
  327. /**
  328. * list_next_or_null_rcu - get the first element from a list
  329. * @head: the head for the list.
  330. * @ptr: the list head to take the next element from.
  331. * @type: the type of the struct this is embedded in.
  332. * @member: the name of the list_head within the struct.
  333. *
  334. * Note that if the ptr is at the end of the list, NULL is returned.
  335. *
  336. * This primitive may safely run concurrently with the _rcu list-mutation
  337. * primitives such as list_add_rcu() as long as it's guarded by rcu_read_lock().
  338. */
  339. #define list_next_or_null_rcu(head, ptr, type, member) \
  340. ({ \
  341. struct list_head *__head = (head); \
  342. struct list_head *__ptr = (ptr); \
  343. struct list_head *__next = READ_ONCE(__ptr->next); \
  344. likely(__next != __head) ? list_entry_rcu(__next, type, \
  345. member) : NULL; \
  346. })
  347. /**
  348. * list_for_each_entry_rcu - iterate over rcu list of given type
  349. * @pos: the type * to use as a loop cursor.
  350. * @head: the head for your list.
  351. * @member: the name of the list_head within the struct.
  352. * @cond: optional lockdep expression if called from non-RCU protection.
  353. *
  354. * This list-traversal primitive may safely run concurrently with
  355. * the _rcu list-mutation primitives such as list_add_rcu()
  356. * as long as the traversal is guarded by rcu_read_lock().
  357. */
  358. #define list_for_each_entry_rcu(pos, head, member, cond...) \
  359. for (__list_check_rcu(dummy, ## cond, 0), \
  360. pos = list_entry_rcu((head)->next, typeof(*pos), member); \
  361. &pos->member != (head); \
  362. pos = list_entry_rcu(pos->member.next, typeof(*pos), member))
  363. /**
  364. * list_for_each_entry_srcu - iterate over rcu list of given type
  365. * @pos: the type * to use as a loop cursor.
  366. * @head: the head for your list.
  367. * @member: the name of the list_head within the struct.
  368. * @cond: lockdep expression for the lock required to traverse the list.
  369. *
  370. * This list-traversal primitive may safely run concurrently with
  371. * the _rcu list-mutation primitives such as list_add_rcu()
  372. * as long as the traversal is guarded by srcu_read_lock().
  373. * The lockdep expression srcu_read_lock_held() can be passed as the
  374. * cond argument from read side.
  375. */
  376. #define list_for_each_entry_srcu(pos, head, member, cond) \
  377. for (__list_check_srcu(cond), \
  378. pos = list_entry_rcu((head)->next, typeof(*pos), member); \
  379. &pos->member != (head); \
  380. pos = list_entry_rcu(pos->member.next, typeof(*pos), member))
  381. /**
  382. * list_entry_lockless - get the struct for this entry
  383. * @ptr: the &struct list_head pointer.
  384. * @type: the type of the struct this is embedded in.
  385. * @member: the name of the list_head within the struct.
  386. *
  387. * This primitive may safely run concurrently with the _rcu
  388. * list-mutation primitives such as list_add_rcu(), but requires some
  389. * implicit RCU read-side guarding. One example is running within a special
  390. * exception-time environment where preemption is disabled and where lockdep
  391. * cannot be invoked. Another example is when items are added to the list,
  392. * but never deleted.
  393. */
  394. #define list_entry_lockless(ptr, type, member) \
  395. container_of((typeof(ptr))READ_ONCE(ptr), type, member)
  396. /**
  397. * list_for_each_entry_lockless - iterate over rcu list of given type
  398. * @pos: the type * to use as a loop cursor.
  399. * @head: the head for your list.
  400. * @member: the name of the list_struct within the struct.
  401. *
  402. * This primitive may safely run concurrently with the _rcu
  403. * list-mutation primitives such as list_add_rcu(), but requires some
  404. * implicit RCU read-side guarding. One example is running within a special
  405. * exception-time environment where preemption is disabled and where lockdep
  406. * cannot be invoked. Another example is when items are added to the list,
  407. * but never deleted.
  408. */
  409. #define list_for_each_entry_lockless(pos, head, member) \
  410. for (pos = list_entry_lockless((head)->next, typeof(*pos), member); \
  411. &pos->member != (head); \
  412. pos = list_entry_lockless(pos->member.next, typeof(*pos), member))
  413. /**
  414. * list_for_each_entry_continue_rcu - continue iteration over list of given type
  415. * @pos: the type * to use as a loop cursor.
  416. * @head: the head for your list.
  417. * @member: the name of the list_head within the struct.
  418. *
  419. * Continue to iterate over list of given type, continuing after
  420. * the current position which must have been in the list when the RCU read
  421. * lock was taken.
  422. * This would typically require either that you obtained the node from a
  423. * previous walk of the list in the same RCU read-side critical section, or
  424. * that you held some sort of non-RCU reference (such as a reference count)
  425. * to keep the node alive *and* in the list.
  426. *
  427. * This iterator is similar to list_for_each_entry_from_rcu() except
  428. * this starts after the given position and that one starts at the given
  429. * position.
  430. */
  431. #define list_for_each_entry_continue_rcu(pos, head, member) \
  432. for (pos = list_entry_rcu(pos->member.next, typeof(*pos), member); \
  433. &pos->member != (head); \
  434. pos = list_entry_rcu(pos->member.next, typeof(*pos), member))
  435. /**
  436. * list_for_each_entry_from_rcu - iterate over a list from current point
  437. * @pos: the type * to use as a loop cursor.
  438. * @head: the head for your list.
  439. * @member: the name of the list_node within the struct.
  440. *
  441. * Iterate over the tail of a list starting from a given position,
  442. * which must have been in the list when the RCU read lock was taken.
  443. * This would typically require either that you obtained the node from a
  444. * previous walk of the list in the same RCU read-side critical section, or
  445. * that you held some sort of non-RCU reference (such as a reference count)
  446. * to keep the node alive *and* in the list.
  447. *
  448. * This iterator is similar to list_for_each_entry_continue_rcu() except
  449. * this starts from the given position and that one starts from the position
  450. * after the given position.
  451. */
  452. #define list_for_each_entry_from_rcu(pos, head, member) \
  453. for (; &(pos)->member != (head); \
  454. pos = list_entry_rcu(pos->member.next, typeof(*(pos)), member))
  455. /**
  456. * hlist_del_rcu - deletes entry from hash list without re-initialization
  457. * @n: the element to delete from the hash list.
  458. *
  459. * Note: list_unhashed() on entry does not return true after this,
  460. * the entry is in an undefined state. It is useful for RCU based
  461. * lockfree traversal.
  462. *
  463. * In particular, it means that we can not poison the forward
  464. * pointers that may still be used for walking the hash list.
  465. *
  466. * The caller must take whatever precautions are necessary
  467. * (such as holding appropriate locks) to avoid racing
  468. * with another list-mutation primitive, such as hlist_add_head_rcu()
  469. * or hlist_del_rcu(), running on this same list.
  470. * However, it is perfectly legal to run concurrently with
  471. * the _rcu list-traversal primitives, such as
  472. * hlist_for_each_entry().
  473. */
  474. static inline void hlist_del_rcu(struct hlist_node *n)
  475. {
  476. __hlist_del(n);
  477. WRITE_ONCE(n->pprev, LIST_POISON2);
  478. }
  479. /**
  480. * hlist_replace_rcu - replace old entry by new one
  481. * @old : the element to be replaced
  482. * @new : the new element to insert
  483. *
  484. * The @old entry will be replaced with the @new entry atomically.
  485. */
  486. static inline void hlist_replace_rcu(struct hlist_node *old,
  487. struct hlist_node *new)
  488. {
  489. struct hlist_node *next = old->next;
  490. new->next = next;
  491. WRITE_ONCE(new->pprev, old->pprev);
  492. rcu_assign_pointer(*(struct hlist_node __rcu **)new->pprev, new);
  493. if (next)
  494. WRITE_ONCE(new->next->pprev, &new->next);
  495. WRITE_ONCE(old->pprev, LIST_POISON2);
  496. }
  497. /**
  498. * hlists_swap_heads_rcu - swap the lists the hlist heads point to
  499. * @left: The hlist head on the left
  500. * @right: The hlist head on the right
  501. *
  502. * The lists start out as [@left ][node1 ... ] and
  503. * [@right ][node2 ... ]
  504. * The lists end up as [@left ][node2 ... ]
  505. * [@right ][node1 ... ]
  506. */
  507. static inline void hlists_swap_heads_rcu(struct hlist_head *left, struct hlist_head *right)
  508. {
  509. struct hlist_node *node1 = left->first;
  510. struct hlist_node *node2 = right->first;
  511. rcu_assign_pointer(left->first, node2);
  512. rcu_assign_pointer(right->first, node1);
  513. WRITE_ONCE(node2->pprev, &left->first);
  514. WRITE_ONCE(node1->pprev, &right->first);
  515. }
  516. /*
  517. * return the first or the next element in an RCU protected hlist
  518. */
  519. #define hlist_first_rcu(head) (*((struct hlist_node __rcu **)(&(head)->first)))
  520. #define hlist_next_rcu(node) (*((struct hlist_node __rcu **)(&(node)->next)))
  521. #define hlist_pprev_rcu(node) (*((struct hlist_node __rcu **)((node)->pprev)))
  522. /**
  523. * hlist_add_head_rcu
  524. * @n: the element to add to the hash list.
  525. * @h: the list to add to.
  526. *
  527. * Description:
  528. * Adds the specified element to the specified hlist,
  529. * while permitting racing traversals.
  530. *
  531. * The caller must take whatever precautions are necessary
  532. * (such as holding appropriate locks) to avoid racing
  533. * with another list-mutation primitive, such as hlist_add_head_rcu()
  534. * or hlist_del_rcu(), running on this same list.
  535. * However, it is perfectly legal to run concurrently with
  536. * the _rcu list-traversal primitives, such as
  537. * hlist_for_each_entry_rcu(), used to prevent memory-consistency
  538. * problems on Alpha CPUs. Regardless of the type of CPU, the
  539. * list-traversal primitive must be guarded by rcu_read_lock().
  540. */
  541. static inline void hlist_add_head_rcu(struct hlist_node *n,
  542. struct hlist_head *h)
  543. {
  544. struct hlist_node *first = h->first;
  545. n->next = first;
  546. WRITE_ONCE(n->pprev, &h->first);
  547. rcu_assign_pointer(hlist_first_rcu(h), n);
  548. if (first)
  549. WRITE_ONCE(first->pprev, &n->next);
  550. }
  551. /**
  552. * hlist_add_tail_rcu
  553. * @n: the element to add to the hash list.
  554. * @h: the list to add to.
  555. *
  556. * Description:
  557. * Adds the specified element to the specified hlist,
  558. * while permitting racing traversals.
  559. *
  560. * The caller must take whatever precautions are necessary
  561. * (such as holding appropriate locks) to avoid racing
  562. * with another list-mutation primitive, such as hlist_add_head_rcu()
  563. * or hlist_del_rcu(), running on this same list.
  564. * However, it is perfectly legal to run concurrently with
  565. * the _rcu list-traversal primitives, such as
  566. * hlist_for_each_entry_rcu(), used to prevent memory-consistency
  567. * problems on Alpha CPUs. Regardless of the type of CPU, the
  568. * list-traversal primitive must be guarded by rcu_read_lock().
  569. */
  570. static inline void hlist_add_tail_rcu(struct hlist_node *n,
  571. struct hlist_head *h)
  572. {
  573. struct hlist_node *i, *last = NULL;
  574. /* Note: write side code, so rcu accessors are not needed. */
  575. for (i = h->first; i; i = i->next)
  576. last = i;
  577. if (last) {
  578. n->next = last->next;
  579. WRITE_ONCE(n->pprev, &last->next);
  580. rcu_assign_pointer(hlist_next_rcu(last), n);
  581. } else {
  582. hlist_add_head_rcu(n, h);
  583. }
  584. }
  585. /**
  586. * hlist_add_before_rcu
  587. * @n: the new element to add to the hash list.
  588. * @next: the existing element to add the new element before.
  589. *
  590. * Description:
  591. * Adds the specified element to the specified hlist
  592. * before the specified node while permitting racing traversals.
  593. *
  594. * The caller must take whatever precautions are necessary
  595. * (such as holding appropriate locks) to avoid racing
  596. * with another list-mutation primitive, such as hlist_add_head_rcu()
  597. * or hlist_del_rcu(), running on this same list.
  598. * However, it is perfectly legal to run concurrently with
  599. * the _rcu list-traversal primitives, such as
  600. * hlist_for_each_entry_rcu(), used to prevent memory-consistency
  601. * problems on Alpha CPUs.
  602. */
  603. static inline void hlist_add_before_rcu(struct hlist_node *n,
  604. struct hlist_node *next)
  605. {
  606. WRITE_ONCE(n->pprev, next->pprev);
  607. n->next = next;
  608. rcu_assign_pointer(hlist_pprev_rcu(n), n);
  609. WRITE_ONCE(next->pprev, &n->next);
  610. }
  611. /**
  612. * hlist_add_behind_rcu
  613. * @n: the new element to add to the hash list.
  614. * @prev: the existing element to add the new element after.
  615. *
  616. * Description:
  617. * Adds the specified element to the specified hlist
  618. * after the specified node while permitting racing traversals.
  619. *
  620. * The caller must take whatever precautions are necessary
  621. * (such as holding appropriate locks) to avoid racing
  622. * with another list-mutation primitive, such as hlist_add_head_rcu()
  623. * or hlist_del_rcu(), running on this same list.
  624. * However, it is perfectly legal to run concurrently with
  625. * the _rcu list-traversal primitives, such as
  626. * hlist_for_each_entry_rcu(), used to prevent memory-consistency
  627. * problems on Alpha CPUs.
  628. */
  629. static inline void hlist_add_behind_rcu(struct hlist_node *n,
  630. struct hlist_node *prev)
  631. {
  632. n->next = prev->next;
  633. WRITE_ONCE(n->pprev, &prev->next);
  634. rcu_assign_pointer(hlist_next_rcu(prev), n);
  635. if (n->next)
  636. WRITE_ONCE(n->next->pprev, &n->next);
  637. }
  638. #define __hlist_for_each_rcu(pos, head) \
  639. for (pos = rcu_dereference(hlist_first_rcu(head)); \
  640. pos; \
  641. pos = rcu_dereference(hlist_next_rcu(pos)))
  642. /**
  643. * hlist_for_each_entry_rcu - iterate over rcu list of given type
  644. * @pos: the type * to use as a loop cursor.
  645. * @head: the head for your list.
  646. * @member: the name of the hlist_node within the struct.
  647. * @cond: optional lockdep expression if called from non-RCU protection.
  648. *
  649. * This list-traversal primitive may safely run concurrently with
  650. * the _rcu list-mutation primitives such as hlist_add_head_rcu()
  651. * as long as the traversal is guarded by rcu_read_lock().
  652. */
  653. #define hlist_for_each_entry_rcu(pos, head, member, cond...) \
  654. for (__list_check_rcu(dummy, ## cond, 0), \
  655. pos = hlist_entry_safe(rcu_dereference_raw(hlist_first_rcu(head)),\
  656. typeof(*(pos)), member); \
  657. pos; \
  658. pos = hlist_entry_safe(rcu_dereference_raw(hlist_next_rcu(\
  659. &(pos)->member)), typeof(*(pos)), member))
  660. /**
  661. * hlist_for_each_entry_srcu - iterate over rcu list of given type
  662. * @pos: the type * to use as a loop cursor.
  663. * @head: the head for your list.
  664. * @member: the name of the hlist_node within the struct.
  665. * @cond: lockdep expression for the lock required to traverse the list.
  666. *
  667. * This list-traversal primitive may safely run concurrently with
  668. * the _rcu list-mutation primitives such as hlist_add_head_rcu()
  669. * as long as the traversal is guarded by srcu_read_lock().
  670. * The lockdep expression srcu_read_lock_held() can be passed as the
  671. * cond argument from read side.
  672. */
  673. #define hlist_for_each_entry_srcu(pos, head, member, cond) \
  674. for (__list_check_srcu(cond), \
  675. pos = hlist_entry_safe(rcu_dereference_raw(hlist_first_rcu(head)),\
  676. typeof(*(pos)), member); \
  677. pos; \
  678. pos = hlist_entry_safe(rcu_dereference_raw(hlist_next_rcu(\
  679. &(pos)->member)), typeof(*(pos)), member))
  680. /**
  681. * hlist_for_each_entry_rcu_notrace - iterate over rcu list of given type (for tracing)
  682. * @pos: the type * to use as a loop cursor.
  683. * @head: the head for your list.
  684. * @member: the name of the hlist_node within the struct.
  685. *
  686. * This list-traversal primitive may safely run concurrently with
  687. * the _rcu list-mutation primitives such as hlist_add_head_rcu()
  688. * as long as the traversal is guarded by rcu_read_lock().
  689. *
  690. * This is the same as hlist_for_each_entry_rcu() except that it does
  691. * not do any RCU debugging or tracing.
  692. */
  693. #define hlist_for_each_entry_rcu_notrace(pos, head, member) \
  694. for (pos = hlist_entry_safe(rcu_dereference_raw_check(hlist_first_rcu(head)),\
  695. typeof(*(pos)), member); \
  696. pos; \
  697. pos = hlist_entry_safe(rcu_dereference_raw_check(hlist_next_rcu(\
  698. &(pos)->member)), typeof(*(pos)), member))
  699. /**
  700. * hlist_for_each_entry_rcu_bh - iterate over rcu list of given type
  701. * @pos: the type * to use as a loop cursor.
  702. * @head: the head for your list.
  703. * @member: the name of the hlist_node within the struct.
  704. *
  705. * This list-traversal primitive may safely run concurrently with
  706. * the _rcu list-mutation primitives such as hlist_add_head_rcu()
  707. * as long as the traversal is guarded by rcu_read_lock().
  708. */
  709. #define hlist_for_each_entry_rcu_bh(pos, head, member) \
  710. for (pos = hlist_entry_safe(rcu_dereference_bh(hlist_first_rcu(head)),\
  711. typeof(*(pos)), member); \
  712. pos; \
  713. pos = hlist_entry_safe(rcu_dereference_bh(hlist_next_rcu(\
  714. &(pos)->member)), typeof(*(pos)), member))
  715. /**
  716. * hlist_for_each_entry_continue_rcu - iterate over a hlist continuing after current point
  717. * @pos: the type * to use as a loop cursor.
  718. * @member: the name of the hlist_node within the struct.
  719. */
  720. #define hlist_for_each_entry_continue_rcu(pos, member) \
  721. for (pos = hlist_entry_safe(rcu_dereference_raw(hlist_next_rcu( \
  722. &(pos)->member)), typeof(*(pos)), member); \
  723. pos; \
  724. pos = hlist_entry_safe(rcu_dereference_raw(hlist_next_rcu( \
  725. &(pos)->member)), typeof(*(pos)), member))
  726. /**
  727. * hlist_for_each_entry_continue_rcu_bh - iterate over a hlist continuing after current point
  728. * @pos: the type * to use as a loop cursor.
  729. * @member: the name of the hlist_node within the struct.
  730. */
  731. #define hlist_for_each_entry_continue_rcu_bh(pos, member) \
  732. for (pos = hlist_entry_safe(rcu_dereference_bh(hlist_next_rcu( \
  733. &(pos)->member)), typeof(*(pos)), member); \
  734. pos; \
  735. pos = hlist_entry_safe(rcu_dereference_bh(hlist_next_rcu( \
  736. &(pos)->member)), typeof(*(pos)), member))
  737. /**
  738. * hlist_for_each_entry_from_rcu - iterate over a hlist continuing from current point
  739. * @pos: the type * to use as a loop cursor.
  740. * @member: the name of the hlist_node within the struct.
  741. */
  742. #define hlist_for_each_entry_from_rcu(pos, member) \
  743. for (; pos; \
  744. pos = hlist_entry_safe(rcu_dereference_raw(hlist_next_rcu( \
  745. &(pos)->member)), typeof(*(pos)), member))
  746. #endif /* __KERNEL__ */
  747. #endif