llist.h 9.1 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254
  1. /* SPDX-License-Identifier: GPL-2.0-only */
  2. #ifndef LLIST_H
  3. #define LLIST_H
  4. /*
  5. * Lock-less NULL terminated single linked list
  6. *
  7. * Cases where locking is not needed:
  8. * If there are multiple producers and multiple consumers, llist_add can be
  9. * used in producers and llist_del_all can be used in consumers simultaneously
  10. * without locking. Also a single consumer can use llist_del_first while
  11. * multiple producers simultaneously use llist_add, without any locking.
  12. *
  13. * Cases where locking is needed:
  14. * If we have multiple consumers with llist_del_first used in one consumer, and
  15. * llist_del_first or llist_del_all used in other consumers, then a lock is
  16. * needed. This is because llist_del_first depends on list->first->next not
  17. * changing, but without lock protection, there's no way to be sure about that
  18. * if a preemption happens in the middle of the delete operation and on being
  19. * preempted back, the list->first is the same as before causing the cmpxchg in
  20. * llist_del_first to succeed. For example, while a llist_del_first operation
  21. * is in progress in one consumer, then a llist_del_first, llist_add,
  22. * llist_add (or llist_del_all, llist_add, llist_add) sequence in another
  23. * consumer may cause violations.
  24. *
  25. * This can be summarized as follows:
  26. *
  27. * | add | del_first | del_all
  28. * add | - | - | -
  29. * del_first | | L | L
  30. * del_all | | | -
  31. *
  32. * Where, a particular row's operation can happen concurrently with a column's
  33. * operation, with "-" being no lock needed, while "L" being lock is needed.
  34. *
  35. * The list entries deleted via llist_del_all can be traversed with
  36. * traversing function such as llist_for_each etc. But the list
  37. * entries can not be traversed safely before deleted from the list.
  38. * The order of deleted entries is from the newest to the oldest added
  39. * one. If you want to traverse from the oldest to the newest, you
  40. * must reverse the order by yourself before traversing.
  41. *
  42. * The basic atomic operation of this list is cmpxchg on long. On
  43. * architectures that don't have NMI-safe cmpxchg implementation, the
  44. * list can NOT be used in NMI handlers. So code that uses the list in
  45. * an NMI handler should depend on CONFIG_ARCH_HAVE_NMI_SAFE_CMPXCHG.
  46. *
  47. * Copyright 2010,2011 Intel Corp.
  48. * Author: Huang Ying <[email protected]>
  49. */
  50. #include <linux/atomic.h>
  51. #include <linux/container_of.h>
  52. #include <linux/stddef.h>
  53. #include <linux/types.h>
  54. struct llist_head {
  55. struct llist_node *first;
  56. };
  57. struct llist_node {
  58. struct llist_node *next;
  59. };
  60. #define LLIST_HEAD_INIT(name) { NULL }
  61. #define LLIST_HEAD(name) struct llist_head name = LLIST_HEAD_INIT(name)
  62. /**
  63. * init_llist_head - initialize lock-less list head
  64. * @head: the head for your lock-less list
  65. */
  66. static inline void init_llist_head(struct llist_head *list)
  67. {
  68. list->first = NULL;
  69. }
  70. /**
  71. * llist_entry - get the struct of this entry
  72. * @ptr: the &struct llist_node pointer.
  73. * @type: the type of the struct this is embedded in.
  74. * @member: the name of the llist_node within the struct.
  75. */
  76. #define llist_entry(ptr, type, member) \
  77. container_of(ptr, type, member)
  78. /**
  79. * member_address_is_nonnull - check whether the member address is not NULL
  80. * @ptr: the object pointer (struct type * that contains the llist_node)
  81. * @member: the name of the llist_node within the struct.
  82. *
  83. * This macro is conceptually the same as
  84. * &ptr->member != NULL
  85. * but it works around the fact that compilers can decide that taking a member
  86. * address is never a NULL pointer.
  87. *
  88. * Real objects that start at a high address and have a member at NULL are
  89. * unlikely to exist, but such pointers may be returned e.g. by the
  90. * container_of() macro.
  91. */
  92. #define member_address_is_nonnull(ptr, member) \
  93. ((uintptr_t)(ptr) + offsetof(typeof(*(ptr)), member) != 0)
  94. /**
  95. * llist_for_each - iterate over some deleted entries of a lock-less list
  96. * @pos: the &struct llist_node to use as a loop cursor
  97. * @node: the first entry of deleted list entries
  98. *
  99. * In general, some entries of the lock-less list can be traversed
  100. * safely only after being deleted from list, so start with an entry
  101. * instead of list head.
  102. *
  103. * If being used on entries deleted from lock-less list directly, the
  104. * traverse order is from the newest to the oldest added entry. If
  105. * you want to traverse from the oldest to the newest, you must
  106. * reverse the order by yourself before traversing.
  107. */
  108. #define llist_for_each(pos, node) \
  109. for ((pos) = (node); pos; (pos) = (pos)->next)
  110. /**
  111. * llist_for_each_safe - iterate over some deleted entries of a lock-less list
  112. * safe against removal of list entry
  113. * @pos: the &struct llist_node to use as a loop cursor
  114. * @n: another &struct llist_node to use as temporary storage
  115. * @node: the first entry of deleted list entries
  116. *
  117. * In general, some entries of the lock-less list can be traversed
  118. * safely only after being deleted from list, so start with an entry
  119. * instead of list head.
  120. *
  121. * If being used on entries deleted from lock-less list directly, the
  122. * traverse order is from the newest to the oldest added entry. If
  123. * you want to traverse from the oldest to the newest, you must
  124. * reverse the order by yourself before traversing.
  125. */
  126. #define llist_for_each_safe(pos, n, node) \
  127. for ((pos) = (node); (pos) && ((n) = (pos)->next, true); (pos) = (n))
  128. /**
  129. * llist_for_each_entry - iterate over some deleted entries of lock-less list of given type
  130. * @pos: the type * to use as a loop cursor.
  131. * @node: the fist entry of deleted list entries.
  132. * @member: the name of the llist_node with the struct.
  133. *
  134. * In general, some entries of the lock-less list can be traversed
  135. * safely only after being removed from list, so start with an entry
  136. * instead of list head.
  137. *
  138. * If being used on entries deleted from lock-less list directly, the
  139. * traverse order is from the newest to the oldest added entry. If
  140. * you want to traverse from the oldest to the newest, you must
  141. * reverse the order by yourself before traversing.
  142. */
  143. #define llist_for_each_entry(pos, node, member) \
  144. for ((pos) = llist_entry((node), typeof(*(pos)), member); \
  145. member_address_is_nonnull(pos, member); \
  146. (pos) = llist_entry((pos)->member.next, typeof(*(pos)), member))
  147. /**
  148. * llist_for_each_entry_safe - iterate over some deleted entries of lock-less list of given type
  149. * safe against removal of list entry
  150. * @pos: the type * to use as a loop cursor.
  151. * @n: another type * to use as temporary storage
  152. * @node: the first entry of deleted list entries.
  153. * @member: the name of the llist_node with the struct.
  154. *
  155. * In general, some entries of the lock-less list can be traversed
  156. * safely only after being removed from list, so start with an entry
  157. * instead of list head.
  158. *
  159. * If being used on entries deleted from lock-less list directly, the
  160. * traverse order is from the newest to the oldest added entry. If
  161. * you want to traverse from the oldest to the newest, you must
  162. * reverse the order by yourself before traversing.
  163. */
  164. #define llist_for_each_entry_safe(pos, n, node, member) \
  165. for (pos = llist_entry((node), typeof(*pos), member); \
  166. member_address_is_nonnull(pos, member) && \
  167. (n = llist_entry(pos->member.next, typeof(*n), member), true); \
  168. pos = n)
  169. /**
  170. * llist_empty - tests whether a lock-less list is empty
  171. * @head: the list to test
  172. *
  173. * Not guaranteed to be accurate or up to date. Just a quick way to
  174. * test whether the list is empty without deleting something from the
  175. * list.
  176. */
  177. static inline bool llist_empty(const struct llist_head *head)
  178. {
  179. return READ_ONCE(head->first) == NULL;
  180. }
  181. static inline struct llist_node *llist_next(struct llist_node *node)
  182. {
  183. return node->next;
  184. }
  185. extern bool llist_add_batch(struct llist_node *new_first,
  186. struct llist_node *new_last,
  187. struct llist_head *head);
  188. static inline bool __llist_add_batch(struct llist_node *new_first,
  189. struct llist_node *new_last,
  190. struct llist_head *head)
  191. {
  192. new_last->next = head->first;
  193. head->first = new_first;
  194. return new_last->next == NULL;
  195. }
  196. /**
  197. * llist_add - add a new entry
  198. * @new: new entry to be added
  199. * @head: the head for your lock-less list
  200. *
  201. * Returns true if the list was empty prior to adding this entry.
  202. */
  203. static inline bool llist_add(struct llist_node *new, struct llist_head *head)
  204. {
  205. return llist_add_batch(new, new, head);
  206. }
  207. static inline bool __llist_add(struct llist_node *new, struct llist_head *head)
  208. {
  209. return __llist_add_batch(new, new, head);
  210. }
  211. /**
  212. * llist_del_all - delete all entries from lock-less list
  213. * @head: the head of lock-less list to delete all entries
  214. *
  215. * If list is empty, return NULL, otherwise, delete all entries and
  216. * return the pointer to the first entry. The order of entries
  217. * deleted is from the newest to the oldest added one.
  218. */
  219. static inline struct llist_node *llist_del_all(struct llist_head *head)
  220. {
  221. return xchg(&head->first, NULL);
  222. }
  223. static inline struct llist_node *__llist_del_all(struct llist_head *head)
  224. {
  225. struct llist_node *first = head->first;
  226. head->first = NULL;
  227. return first;
  228. }
  229. extern struct llist_node *llist_del_first(struct llist_head *head);
  230. struct llist_node *llist_reverse_order(struct llist_node *head);
  231. #endif /* LLIST_H */