list.h 29 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837838839840841842843844845846847848849850851852853854855856857858859860861862863864865866867868869870871872873874875876877878879880881882883884885886887888889890891892893894895896897898899900901902903904905906907908909910911912913914915916917918919920921922923924925926927928929930931932933934935936937938939940941942943944945946947948949950951952953954955956957958959960961
  1. #ifndef _LINUX_LIST_H
  2. #define _LINUX_LIST_H
  3. #ifdef __KERNEL__
  4. #include <linux/stddef.h>
  5. #include <linux/poison.h>
  6. #include <linux/prefetch.h>
  7. #include <asm/system.h>
  8. /*
  9. * Simple doubly linked list implementation.
  10. *
  11. * Some of the internal functions ("__xxx") are useful when
  12. * manipulating whole lists rather than single entries, as
  13. * sometimes we already know the next/prev entries and we can
  14. * generate better code by using them directly rather than
  15. * using the generic single-entry routines.
  16. */
  17. struct list_head {
  18. struct list_head *next, *prev;
  19. };
  20. #define LIST_HEAD_INIT(name) { &(name), &(name) }
  21. #define LIST_HEAD(name) \
  22. struct list_head name = LIST_HEAD_INIT(name)
  23. static inline void INIT_LIST_HEAD(struct list_head *list)
  24. {
  25. list->next = list;
  26. list->prev = list;
  27. }
  28. /*
  29. * Insert a new entry between two known consecutive entries.
  30. *
  31. * This is only for internal list manipulation where we know
  32. * the prev/next entries already!
  33. */
  34. #ifndef CONFIG_DEBUG_LIST
  35. static inline void __list_add(struct list_head *new,
  36. struct list_head *prev,
  37. struct list_head *next)
  38. {
  39. next->prev = new;
  40. new->next = next;
  41. new->prev = prev;
  42. prev->next = new;
  43. }
  44. #else
  45. extern void __list_add(struct list_head *new,
  46. struct list_head *prev,
  47. struct list_head *next);
  48. #endif
  49. /**
  50. * list_add - add a new entry
  51. * @new: new entry to be added
  52. * @head: list head to add it after
  53. *
  54. * Insert a new entry after the specified head.
  55. * This is good for implementing stacks.
  56. */
  57. #ifndef CONFIG_DEBUG_LIST
  58. static inline void list_add(struct list_head *new, struct list_head *head)
  59. {
  60. __list_add(new, head, head->next);
  61. }
  62. #else
  63. extern void list_add(struct list_head *new, struct list_head *head);
  64. #endif
  65. /**
  66. * list_add_tail - add a new entry
  67. * @new: new entry to be added
  68. * @head: list head to add it before
  69. *
  70. * Insert a new entry before the specified head.
  71. * This is useful for implementing queues.
  72. */
  73. static inline void list_add_tail(struct list_head *new, struct list_head *head)
  74. {
  75. __list_add(new, head->prev, head);
  76. }
  77. /*
  78. * Insert a new entry between two known consecutive entries.
  79. *
  80. * This is only for internal list manipulation where we know
  81. * the prev/next entries already!
  82. */
  83. static inline void __list_add_rcu(struct list_head * new,
  84. struct list_head * prev, struct list_head * next)
  85. {
  86. new->next = next;
  87. new->prev = prev;
  88. smp_wmb();
  89. next->prev = new;
  90. prev->next = new;
  91. }
  92. /**
  93. * list_add_rcu - add a new entry to rcu-protected list
  94. * @new: new entry to be added
  95. * @head: list head to add it after
  96. *
  97. * Insert a new entry after the specified head.
  98. * This is good for implementing stacks.
  99. *
  100. * The caller must take whatever precautions are necessary
  101. * (such as holding appropriate locks) to avoid racing
  102. * with another list-mutation primitive, such as list_add_rcu()
  103. * or list_del_rcu(), running on this same list.
  104. * However, it is perfectly legal to run concurrently with
  105. * the _rcu list-traversal primitives, such as
  106. * list_for_each_entry_rcu().
  107. */
  108. static inline void list_add_rcu(struct list_head *new, struct list_head *head)
  109. {
  110. __list_add_rcu(new, head, head->next);
  111. }
  112. /**
  113. * list_add_tail_rcu - add a new entry to rcu-protected list
  114. * @new: new entry to be added
  115. * @head: list head to add it before
  116. *
  117. * Insert a new entry before the specified head.
  118. * This is useful for implementing queues.
  119. *
  120. * The caller must take whatever precautions are necessary
  121. * (such as holding appropriate locks) to avoid racing
  122. * with another list-mutation primitive, such as list_add_tail_rcu()
  123. * or list_del_rcu(), running on this same list.
  124. * However, it is perfectly legal to run concurrently with
  125. * the _rcu list-traversal primitives, such as
  126. * list_for_each_entry_rcu().
  127. */
  128. static inline void list_add_tail_rcu(struct list_head *new,
  129. struct list_head *head)
  130. {
  131. __list_add_rcu(new, head->prev, head);
  132. }
  133. /*
  134. * Delete a list entry by making the prev/next entries
  135. * point to each other.
  136. *
  137. * This is only for internal list manipulation where we know
  138. * the prev/next entries already!
  139. */
  140. static inline void __list_del(struct list_head * prev, struct list_head * next)
  141. {
  142. next->prev = prev;
  143. prev->next = next;
  144. }
  145. /**
  146. * list_del - deletes entry from list.
  147. * @entry: the element to delete from the list.
  148. * Note: list_empty() on entry does not return true after this, the entry is
  149. * in an undefined state.
  150. */
  151. #ifndef CONFIG_DEBUG_LIST
  152. static inline void list_del(struct list_head *entry)
  153. {
  154. __list_del(entry->prev, entry->next);
  155. entry->next = LIST_POISON1;
  156. entry->prev = LIST_POISON2;
  157. }
  158. #else
  159. extern void list_del(struct list_head *entry);
  160. #endif
  161. /**
  162. * list_del_rcu - deletes entry from list without re-initialization
  163. * @entry: the element to delete from the list.
  164. *
  165. * Note: list_empty() on entry does not return true after this,
  166. * the entry is in an undefined state. It is useful for RCU based
  167. * lockfree traversal.
  168. *
  169. * In particular, it means that we can not poison the forward
  170. * pointers that may still be used for walking the list.
  171. *
  172. * The caller must take whatever precautions are necessary
  173. * (such as holding appropriate locks) to avoid racing
  174. * with another list-mutation primitive, such as list_del_rcu()
  175. * or list_add_rcu(), running on this same list.
  176. * However, it is perfectly legal to run concurrently with
  177. * the _rcu list-traversal primitives, such as
  178. * list_for_each_entry_rcu().
  179. *
  180. * Note that the caller is not permitted to immediately free
  181. * the newly deleted entry. Instead, either synchronize_rcu()
  182. * or call_rcu() must be used to defer freeing until an RCU
  183. * grace period has elapsed.
  184. */
  185. static inline void list_del_rcu(struct list_head *entry)
  186. {
  187. __list_del(entry->prev, entry->next);
  188. entry->prev = LIST_POISON2;
  189. }
  190. /**
  191. * list_replace - replace old entry by new one
  192. * @old : the element to be replaced
  193. * @new : the new element to insert
  194. *
  195. * If @old was empty, it will be overwritten.
  196. */
  197. static inline void list_replace(struct list_head *old,
  198. struct list_head *new)
  199. {
  200. new->next = old->next;
  201. new->next->prev = new;
  202. new->prev = old->prev;
  203. new->prev->next = new;
  204. }
  205. static inline void list_replace_init(struct list_head *old,
  206. struct list_head *new)
  207. {
  208. list_replace(old, new);
  209. INIT_LIST_HEAD(old);
  210. }
  211. /**
  212. * list_replace_rcu - replace old entry by new one
  213. * @old : the element to be replaced
  214. * @new : the new element to insert
  215. *
  216. * The @old entry will be replaced with the @new entry atomically.
  217. * Note: @old should not be empty.
  218. */
  219. static inline void list_replace_rcu(struct list_head *old,
  220. struct list_head *new)
  221. {
  222. new->next = old->next;
  223. new->prev = old->prev;
  224. smp_wmb();
  225. new->next->prev = new;
  226. new->prev->next = new;
  227. old->prev = LIST_POISON2;
  228. }
  229. /**
  230. * list_del_init - deletes entry from list and reinitialize it.
  231. * @entry: the element to delete from the list.
  232. */
  233. static inline void list_del_init(struct list_head *entry)
  234. {
  235. __list_del(entry->prev, entry->next);
  236. INIT_LIST_HEAD(entry);
  237. }
  238. /**
  239. * list_move - delete from one list and add as another's head
  240. * @list: the entry to move
  241. * @head: the head that will precede our entry
  242. */
  243. static inline void list_move(struct list_head *list, struct list_head *head)
  244. {
  245. __list_del(list->prev, list->next);
  246. list_add(list, head);
  247. }
  248. /**
  249. * list_move_tail - delete from one list and add as another's tail
  250. * @list: the entry to move
  251. * @head: the head that will follow our entry
  252. */
  253. static inline void list_move_tail(struct list_head *list,
  254. struct list_head *head)
  255. {
  256. __list_del(list->prev, list->next);
  257. list_add_tail(list, head);
  258. }
  259. /**
  260. * list_is_last - tests whether @list is the last entry in list @head
  261. * @list: the entry to test
  262. * @head: the head of the list
  263. */
  264. static inline int list_is_last(const struct list_head *list,
  265. const struct list_head *head)
  266. {
  267. return list->next == head;
  268. }
  269. /**
  270. * list_empty - tests whether a list is empty
  271. * @head: the list to test.
  272. */
  273. static inline int list_empty(const struct list_head *head)
  274. {
  275. return head->next == head;
  276. }
  277. /**
  278. * list_empty_careful - tests whether a list is empty and not being modified
  279. * @head: the list to test
  280. *
  281. * Description:
  282. * tests whether a list is empty _and_ checks that no other CPU might be
  283. * in the process of modifying either member (next or prev)
  284. *
  285. * NOTE: using list_empty_careful() without synchronization
  286. * can only be safe if the only activity that can happen
  287. * to the list entry is list_del_init(). Eg. it cannot be used
  288. * if another CPU could re-list_add() it.
  289. */
  290. static inline int list_empty_careful(const struct list_head *head)
  291. {
  292. struct list_head *next = head->next;
  293. return (next == head) && (next == head->prev);
  294. }
  295. static inline void __list_splice(struct list_head *list,
  296. struct list_head *head)
  297. {
  298. struct list_head *first = list->next;
  299. struct list_head *last = list->prev;
  300. struct list_head *at = head->next;
  301. first->prev = head;
  302. head->next = first;
  303. last->next = at;
  304. at->prev = last;
  305. }
  306. /**
  307. * list_splice - join two lists
  308. * @list: the new list to add.
  309. * @head: the place to add it in the first list.
  310. */
  311. static inline void list_splice(struct list_head *list, struct list_head *head)
  312. {
  313. if (!list_empty(list))
  314. __list_splice(list, head);
  315. }
  316. /**
  317. * list_splice_init - join two lists and reinitialise the emptied list.
  318. * @list: the new list to add.
  319. * @head: the place to add it in the first list.
  320. *
  321. * The list at @list is reinitialised
  322. */
  323. static inline void list_splice_init(struct list_head *list,
  324. struct list_head *head)
  325. {
  326. if (!list_empty(list)) {
  327. __list_splice(list, head);
  328. INIT_LIST_HEAD(list);
  329. }
  330. }
  331. /**
  332. * list_splice_init_rcu - splice an RCU-protected list into an existing list.
  333. * @list: the RCU-protected list to splice
  334. * @head: the place in the list to splice the first list into
  335. * @sync: function to sync: synchronize_rcu(), synchronize_sched(), ...
  336. *
  337. * @head can be RCU-read traversed concurrently with this function.
  338. *
  339. * Note that this function blocks.
  340. *
  341. * Important note: the caller must take whatever action is necessary to
  342. * prevent any other updates to @head. In principle, it is possible
  343. * to modify the list as soon as sync() begins execution.
  344. * If this sort of thing becomes necessary, an alternative version
  345. * based on call_rcu() could be created. But only if -really-
  346. * needed -- there is no shortage of RCU API members.
  347. */
  348. static inline void list_splice_init_rcu(struct list_head *list,
  349. struct list_head *head,
  350. void (*sync)(void))
  351. {
  352. struct list_head *first = list->next;
  353. struct list_head *last = list->prev;
  354. struct list_head *at = head->next;
  355. if (list_empty(head))
  356. return;
  357. /* "first" and "last" tracking list, so initialize it. */
  358. INIT_LIST_HEAD(list);
  359. /*
  360. * At this point, the list body still points to the source list.
  361. * Wait for any readers to finish using the list before splicing
  362. * the list body into the new list. Any new readers will see
  363. * an empty list.
  364. */
  365. sync();
  366. /*
  367. * Readers are finished with the source list, so perform splice.
  368. * The order is important if the new list is global and accessible
  369. * to concurrent RCU readers. Note that RCU readers are not
  370. * permitted to traverse the prev pointers without excluding
  371. * this function.
  372. */
  373. last->next = at;
  374. smp_wmb();
  375. head->next = first;
  376. first->prev = head;
  377. at->prev = last;
  378. }
  379. /**
  380. * list_entry - get the struct for this entry
  381. * @ptr: the &struct list_head pointer.
  382. * @type: the type of the struct this is embedded in.
  383. * @member: the name of the list_struct within the struct.
  384. */
  385. #define list_entry(ptr, type, member) \
  386. container_of(ptr, type, member)
  387. /**
  388. * list_for_each - iterate over a list
  389. * @pos: the &struct list_head to use as a loop cursor.
  390. * @head: the head for your list.
  391. */
  392. #define list_for_each(pos, head) \
  393. for (pos = (head)->next; prefetch(pos->next), pos != (head); \
  394. pos = pos->next)
  395. /**
  396. * __list_for_each - iterate over a list
  397. * @pos: the &struct list_head to use as a loop cursor.
  398. * @head: the head for your list.
  399. *
  400. * This variant differs from list_for_each() in that it's the
  401. * simplest possible list iteration code, no prefetching is done.
  402. * Use this for code that knows the list to be very short (empty
  403. * or 1 entry) most of the time.
  404. */
  405. #define __list_for_each(pos, head) \
  406. for (pos = (head)->next; pos != (head); pos = pos->next)
  407. /**
  408. * list_for_each_prev - iterate over a list backwards
  409. * @pos: the &struct list_head to use as a loop cursor.
  410. * @head: the head for your list.
  411. */
  412. #define list_for_each_prev(pos, head) \
  413. for (pos = (head)->prev; prefetch(pos->prev), pos != (head); \
  414. pos = pos->prev)
  415. /**
  416. * list_for_each_safe - iterate over a list safe against removal of list entry
  417. * @pos: the &struct list_head to use as a loop cursor.
  418. * @n: another &struct list_head to use as temporary storage
  419. * @head: the head for your list.
  420. */
  421. #define list_for_each_safe(pos, n, head) \
  422. for (pos = (head)->next, n = pos->next; pos != (head); \
  423. pos = n, n = pos->next)
  424. /**
  425. * list_for_each_entry - iterate over list of given type
  426. * @pos: the type * to use as a loop cursor.
  427. * @head: the head for your list.
  428. * @member: the name of the list_struct within the struct.
  429. */
  430. #define list_for_each_entry(pos, head, member) \
  431. for (pos = list_entry((head)->next, typeof(*pos), member); \
  432. prefetch(pos->member.next), &pos->member != (head); \
  433. pos = list_entry(pos->member.next, typeof(*pos), member))
  434. /**
  435. * list_for_each_entry_reverse - iterate backwards over list of given type.
  436. * @pos: the type * to use as a loop cursor.
  437. * @head: the head for your list.
  438. * @member: the name of the list_struct within the struct.
  439. */
  440. #define list_for_each_entry_reverse(pos, head, member) \
  441. for (pos = list_entry((head)->prev, typeof(*pos), member); \
  442. prefetch(pos->member.prev), &pos->member != (head); \
  443. pos = list_entry(pos->member.prev, typeof(*pos), member))
  444. /**
  445. * list_prepare_entry - prepare a pos entry for use in list_for_each_entry_continue()
  446. * @pos: the type * to use as a start point
  447. * @head: the head of the list
  448. * @member: the name of the list_struct within the struct.
  449. *
  450. * Prepares a pos entry for use as a start point in list_for_each_entry_continue().
  451. */
  452. #define list_prepare_entry(pos, head, member) \
  453. ((pos) ? : list_entry(head, typeof(*pos), member))
  454. /**
  455. * list_for_each_entry_continue - continue iteration over list of given type
  456. * @pos: the type * to use as a loop cursor.
  457. * @head: the head for your list.
  458. * @member: the name of the list_struct within the struct.
  459. *
  460. * Continue to iterate over list of given type, continuing after
  461. * the current position.
  462. */
  463. #define list_for_each_entry_continue(pos, head, member) \
  464. for (pos = list_entry(pos->member.next, typeof(*pos), member); \
  465. prefetch(pos->member.next), &pos->member != (head); \
  466. pos = list_entry(pos->member.next, typeof(*pos), member))
  467. /**
  468. * list_for_each_entry_from - iterate over list of given type from the current point
  469. * @pos: the type * to use as a loop cursor.
  470. * @head: the head for your list.
  471. * @member: the name of the list_struct within the struct.
  472. *
  473. * Iterate over list of given type, continuing from current position.
  474. */
  475. #define list_for_each_entry_from(pos, head, member) \
  476. for (; prefetch(pos->member.next), &pos->member != (head); \
  477. pos = list_entry(pos->member.next, typeof(*pos), member))
  478. /**
  479. * list_for_each_entry_safe - iterate over list of given type safe against removal of list entry
  480. * @pos: the type * to use as a loop cursor.
  481. * @n: another type * to use as temporary storage
  482. * @head: the head for your list.
  483. * @member: the name of the list_struct within the struct.
  484. */
  485. #define list_for_each_entry_safe(pos, n, head, member) \
  486. for (pos = list_entry((head)->next, typeof(*pos), member), \
  487. n = list_entry(pos->member.next, typeof(*pos), member); \
  488. &pos->member != (head); \
  489. pos = n, n = list_entry(n->member.next, typeof(*n), member))
  490. /**
  491. * list_for_each_entry_safe_continue
  492. * @pos: the type * to use as a loop cursor.
  493. * @n: another type * to use as temporary storage
  494. * @head: the head for your list.
  495. * @member: the name of the list_struct within the struct.
  496. *
  497. * Iterate over list of given type, continuing after current point,
  498. * safe against removal of list entry.
  499. */
  500. #define list_for_each_entry_safe_continue(pos, n, head, member) \
  501. for (pos = list_entry(pos->member.next, typeof(*pos), member), \
  502. n = list_entry(pos->member.next, typeof(*pos), member); \
  503. &pos->member != (head); \
  504. pos = n, n = list_entry(n->member.next, typeof(*n), member))
  505. /**
  506. * list_for_each_entry_safe_from
  507. * @pos: the type * to use as a loop cursor.
  508. * @n: another type * to use as temporary storage
  509. * @head: the head for your list.
  510. * @member: the name of the list_struct within the struct.
  511. *
  512. * Iterate over list of given type from current point, safe against
  513. * removal of list entry.
  514. */
  515. #define list_for_each_entry_safe_from(pos, n, head, member) \
  516. for (n = list_entry(pos->member.next, typeof(*pos), member); \
  517. &pos->member != (head); \
  518. pos = n, n = list_entry(n->member.next, typeof(*n), member))
  519. /**
  520. * list_for_each_entry_safe_reverse
  521. * @pos: the type * to use as a loop cursor.
  522. * @n: another type * to use as temporary storage
  523. * @head: the head for your list.
  524. * @member: the name of the list_struct within the struct.
  525. *
  526. * Iterate backwards over list of given type, safe against removal
  527. * of list entry.
  528. */
  529. #define list_for_each_entry_safe_reverse(pos, n, head, member) \
  530. for (pos = list_entry((head)->prev, typeof(*pos), member), \
  531. n = list_entry(pos->member.prev, typeof(*pos), member); \
  532. &pos->member != (head); \
  533. pos = n, n = list_entry(n->member.prev, typeof(*n), member))
  534. /**
  535. * list_for_each_rcu - iterate over an rcu-protected list
  536. * @pos: the &struct list_head to use as a loop cursor.
  537. * @head: the head for your list.
  538. *
  539. * This list-traversal primitive may safely run concurrently with
  540. * the _rcu list-mutation primitives such as list_add_rcu()
  541. * as long as the traversal is guarded by rcu_read_lock().
  542. */
  543. #define list_for_each_rcu(pos, head) \
  544. for (pos = (head)->next; \
  545. prefetch(rcu_dereference(pos)->next), pos != (head); \
  546. pos = pos->next)
  547. #define __list_for_each_rcu(pos, head) \
  548. for (pos = (head)->next; \
  549. rcu_dereference(pos) != (head); \
  550. pos = pos->next)
  551. /**
  552. * list_for_each_safe_rcu
  553. * @pos: the &struct list_head to use as a loop cursor.
  554. * @n: another &struct list_head to use as temporary storage
  555. * @head: the head for your list.
  556. *
  557. * Iterate over an rcu-protected list, safe against removal of list entry.
  558. *
  559. * This list-traversal primitive may safely run concurrently with
  560. * the _rcu list-mutation primitives such as list_add_rcu()
  561. * as long as the traversal is guarded by rcu_read_lock().
  562. */
  563. #define list_for_each_safe_rcu(pos, n, head) \
  564. for (pos = (head)->next; \
  565. n = rcu_dereference(pos)->next, pos != (head); \
  566. pos = n)
  567. /**
  568. * list_for_each_entry_rcu - iterate over rcu list of given type
  569. * @pos: the type * to use as a loop cursor.
  570. * @head: the head for your list.
  571. * @member: the name of the list_struct within the struct.
  572. *
  573. * This list-traversal primitive may safely run concurrently with
  574. * the _rcu list-mutation primitives such as list_add_rcu()
  575. * as long as the traversal is guarded by rcu_read_lock().
  576. */
  577. #define list_for_each_entry_rcu(pos, head, member) \
  578. for (pos = list_entry((head)->next, typeof(*pos), member); \
  579. prefetch(rcu_dereference(pos)->member.next), \
  580. &pos->member != (head); \
  581. pos = list_entry(pos->member.next, typeof(*pos), member))
  582. /**
  583. * list_for_each_continue_rcu
  584. * @pos: the &struct list_head to use as a loop cursor.
  585. * @head: the head for your list.
  586. *
  587. * Iterate over an rcu-protected list, continuing after current point.
  588. *
  589. * This list-traversal primitive may safely run concurrently with
  590. * the _rcu list-mutation primitives such as list_add_rcu()
  591. * as long as the traversal is guarded by rcu_read_lock().
  592. */
  593. #define list_for_each_continue_rcu(pos, head) \
  594. for ((pos) = (pos)->next; \
  595. prefetch(rcu_dereference((pos))->next), (pos) != (head); \
  596. (pos) = (pos)->next)
  597. /*
  598. * Double linked lists with a single pointer list head.
  599. * Mostly useful for hash tables where the two pointer list head is
  600. * too wasteful.
  601. * You lose the ability to access the tail in O(1).
  602. */
  603. struct hlist_head {
  604. struct hlist_node *first;
  605. };
  606. struct hlist_node {
  607. struct hlist_node *next, **pprev;
  608. };
  609. #define HLIST_HEAD_INIT { .first = NULL }
  610. #define HLIST_HEAD(name) struct hlist_head name = { .first = NULL }
  611. #define INIT_HLIST_HEAD(ptr) ((ptr)->first = NULL)
  612. static inline void INIT_HLIST_NODE(struct hlist_node *h)
  613. {
  614. h->next = NULL;
  615. h->pprev = NULL;
  616. }
  617. static inline int hlist_unhashed(const struct hlist_node *h)
  618. {
  619. return !h->pprev;
  620. }
  621. static inline int hlist_empty(const struct hlist_head *h)
  622. {
  623. return !h->first;
  624. }
  625. static inline void __hlist_del(struct hlist_node *n)
  626. {
  627. struct hlist_node *next = n->next;
  628. struct hlist_node **pprev = n->pprev;
  629. *pprev = next;
  630. if (next)
  631. next->pprev = pprev;
  632. }
  633. static inline void hlist_del(struct hlist_node *n)
  634. {
  635. __hlist_del(n);
  636. n->next = LIST_POISON1;
  637. n->pprev = LIST_POISON2;
  638. }
  639. /**
  640. * hlist_del_rcu - deletes entry from hash list without re-initialization
  641. * @n: the element to delete from the hash list.
  642. *
  643. * Note: list_unhashed() on entry does not return true after this,
  644. * the entry is in an undefined state. It is useful for RCU based
  645. * lockfree traversal.
  646. *
  647. * In particular, it means that we can not poison the forward
  648. * pointers that may still be used for walking the hash list.
  649. *
  650. * The caller must take whatever precautions are necessary
  651. * (such as holding appropriate locks) to avoid racing
  652. * with another list-mutation primitive, such as hlist_add_head_rcu()
  653. * or hlist_del_rcu(), running on this same list.
  654. * However, it is perfectly legal to run concurrently with
  655. * the _rcu list-traversal primitives, such as
  656. * hlist_for_each_entry().
  657. */
  658. static inline void hlist_del_rcu(struct hlist_node *n)
  659. {
  660. __hlist_del(n);
  661. n->pprev = LIST_POISON2;
  662. }
  663. static inline void hlist_del_init(struct hlist_node *n)
  664. {
  665. if (!hlist_unhashed(n)) {
  666. __hlist_del(n);
  667. INIT_HLIST_NODE(n);
  668. }
  669. }
  670. /**
  671. * hlist_replace_rcu - replace old entry by new one
  672. * @old : the element to be replaced
  673. * @new : the new element to insert
  674. *
  675. * The @old entry will be replaced with the @new entry atomically.
  676. */
  677. static inline void hlist_replace_rcu(struct hlist_node *old,
  678. struct hlist_node *new)
  679. {
  680. struct hlist_node *next = old->next;
  681. new->next = next;
  682. new->pprev = old->pprev;
  683. smp_wmb();
  684. if (next)
  685. new->next->pprev = &new->next;
  686. *new->pprev = new;
  687. old->pprev = LIST_POISON2;
  688. }
  689. static inline void hlist_add_head(struct hlist_node *n, struct hlist_head *h)
  690. {
  691. struct hlist_node *first = h->first;
  692. n->next = first;
  693. if (first)
  694. first->pprev = &n->next;
  695. h->first = n;
  696. n->pprev = &h->first;
  697. }
  698. /**
  699. * hlist_add_head_rcu
  700. * @n: the element to add to the hash list.
  701. * @h: the list to add to.
  702. *
  703. * Description:
  704. * Adds the specified element to the specified hlist,
  705. * while permitting racing traversals.
  706. *
  707. * The caller must take whatever precautions are necessary
  708. * (such as holding appropriate locks) to avoid racing
  709. * with another list-mutation primitive, such as hlist_add_head_rcu()
  710. * or hlist_del_rcu(), running on this same list.
  711. * However, it is perfectly legal to run concurrently with
  712. * the _rcu list-traversal primitives, such as
  713. * hlist_for_each_entry_rcu(), used to prevent memory-consistency
  714. * problems on Alpha CPUs. Regardless of the type of CPU, the
  715. * list-traversal primitive must be guarded by rcu_read_lock().
  716. */
  717. static inline void hlist_add_head_rcu(struct hlist_node *n,
  718. struct hlist_head *h)
  719. {
  720. struct hlist_node *first = h->first;
  721. n->next = first;
  722. n->pprev = &h->first;
  723. smp_wmb();
  724. if (first)
  725. first->pprev = &n->next;
  726. h->first = n;
  727. }
  728. /* next must be != NULL */
  729. static inline void hlist_add_before(struct hlist_node *n,
  730. struct hlist_node *next)
  731. {
  732. n->pprev = next->pprev;
  733. n->next = next;
  734. next->pprev = &n->next;
  735. *(n->pprev) = n;
  736. }
  737. static inline void hlist_add_after(struct hlist_node *n,
  738. struct hlist_node *next)
  739. {
  740. next->next = n->next;
  741. n->next = next;
  742. next->pprev = &n->next;
  743. if(next->next)
  744. next->next->pprev = &next->next;
  745. }
  746. /**
  747. * hlist_add_before_rcu
  748. * @n: the new element to add to the hash list.
  749. * @next: the existing element to add the new element before.
  750. *
  751. * Description:
  752. * Adds the specified element to the specified hlist
  753. * before the specified node while permitting racing traversals.
  754. *
  755. * The caller must take whatever precautions are necessary
  756. * (such as holding appropriate locks) to avoid racing
  757. * with another list-mutation primitive, such as hlist_add_head_rcu()
  758. * or hlist_del_rcu(), running on this same list.
  759. * However, it is perfectly legal to run concurrently with
  760. * the _rcu list-traversal primitives, such as
  761. * hlist_for_each_entry_rcu(), used to prevent memory-consistency
  762. * problems on Alpha CPUs.
  763. */
  764. static inline void hlist_add_before_rcu(struct hlist_node *n,
  765. struct hlist_node *next)
  766. {
  767. n->pprev = next->pprev;
  768. n->next = next;
  769. smp_wmb();
  770. next->pprev = &n->next;
  771. *(n->pprev) = n;
  772. }
  773. /**
  774. * hlist_add_after_rcu
  775. * @prev: the existing element to add the new element after.
  776. * @n: the new element to add to the hash list.
  777. *
  778. * Description:
  779. * Adds the specified element to the specified hlist
  780. * after the specified node while permitting racing traversals.
  781. *
  782. * The caller must take whatever precautions are necessary
  783. * (such as holding appropriate locks) to avoid racing
  784. * with another list-mutation primitive, such as hlist_add_head_rcu()
  785. * or hlist_del_rcu(), running on this same list.
  786. * However, it is perfectly legal to run concurrently with
  787. * the _rcu list-traversal primitives, such as
  788. * hlist_for_each_entry_rcu(), used to prevent memory-consistency
  789. * problems on Alpha CPUs.
  790. */
  791. static inline void hlist_add_after_rcu(struct hlist_node *prev,
  792. struct hlist_node *n)
  793. {
  794. n->next = prev->next;
  795. n->pprev = &prev->next;
  796. smp_wmb();
  797. prev->next = n;
  798. if (n->next)
  799. n->next->pprev = &n->next;
  800. }
  801. #define hlist_entry(ptr, type, member) container_of(ptr,type,member)
  802. #define hlist_for_each(pos, head) \
  803. for (pos = (head)->first; pos && ({ prefetch(pos->next); 1; }); \
  804. pos = pos->next)
  805. #define hlist_for_each_safe(pos, n, head) \
  806. for (pos = (head)->first; pos && ({ n = pos->next; 1; }); \
  807. pos = n)
  808. /**
  809. * hlist_for_each_entry - iterate over list of given type
  810. * @tpos: the type * to use as a loop cursor.
  811. * @pos: the &struct hlist_node to use as a loop cursor.
  812. * @head: the head for your list.
  813. * @member: the name of the hlist_node within the struct.
  814. */
  815. #define hlist_for_each_entry(tpos, pos, head, member) \
  816. for (pos = (head)->first; \
  817. pos && ({ prefetch(pos->next); 1;}) && \
  818. ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
  819. pos = pos->next)
  820. /**
  821. * hlist_for_each_entry_continue - iterate over a hlist continuing after current point
  822. * @tpos: the type * to use as a loop cursor.
  823. * @pos: the &struct hlist_node to use as a loop cursor.
  824. * @member: the name of the hlist_node within the struct.
  825. */
  826. #define hlist_for_each_entry_continue(tpos, pos, member) \
  827. for (pos = (pos)->next; \
  828. pos && ({ prefetch(pos->next); 1;}) && \
  829. ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
  830. pos = pos->next)
  831. /**
  832. * hlist_for_each_entry_from - iterate over a hlist continuing from current point
  833. * @tpos: the type * to use as a loop cursor.
  834. * @pos: the &struct hlist_node to use as a loop cursor.
  835. * @member: the name of the hlist_node within the struct.
  836. */
  837. #define hlist_for_each_entry_from(tpos, pos, member) \
  838. for (; pos && ({ prefetch(pos->next); 1;}) && \
  839. ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
  840. pos = pos->next)
  841. /**
  842. * hlist_for_each_entry_safe - iterate over list of given type safe against removal of list entry
  843. * @tpos: the type * to use as a loop cursor.
  844. * @pos: the &struct hlist_node to use as a loop cursor.
  845. * @n: another &struct hlist_node to use as temporary storage
  846. * @head: the head for your list.
  847. * @member: the name of the hlist_node within the struct.
  848. */
  849. #define hlist_for_each_entry_safe(tpos, pos, n, head, member) \
  850. for (pos = (head)->first; \
  851. pos && ({ n = pos->next; 1; }) && \
  852. ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
  853. pos = n)
  854. /**
  855. * hlist_for_each_entry_rcu - iterate over rcu list of given type
  856. * @tpos: the type * to use as a loop cursor.
  857. * @pos: the &struct hlist_node to use as a loop cursor.
  858. * @head: the head for your list.
  859. * @member: the name of the hlist_node within the struct.
  860. *
  861. * This list-traversal primitive may safely run concurrently with
  862. * the _rcu list-mutation primitives such as hlist_add_head_rcu()
  863. * as long as the traversal is guarded by rcu_read_lock().
  864. */
  865. #define hlist_for_each_entry_rcu(tpos, pos, head, member) \
  866. for (pos = (head)->first; \
  867. rcu_dereference(pos) && ({ prefetch(pos->next); 1;}) && \
  868. ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
  869. pos = pos->next)
  870. #else
  871. #warning "don't include kernel headers in userspace"
  872. #endif /* __KERNEL__ */
  873. #endif