list_bl.h 4.8 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189
  1. /* SPDX-License-Identifier: GPL-2.0 */
  2. #ifndef _LINUX_LIST_BL_H
  3. #define _LINUX_LIST_BL_H
  4. #include <linux/list.h>
  5. #include <linux/bit_spinlock.h>
  6. /*
  7. * Special version of lists, where head of the list has a lock in the lowest
  8. * bit. This is useful for scalable hash tables without increasing memory
  9. * footprint overhead.
  10. *
  11. * For modification operations, the 0 bit of hlist_bl_head->first
  12. * pointer must be set.
  13. *
  14. * With some small modifications, this can easily be adapted to store several
  15. * arbitrary bits (not just a single lock bit), if the need arises to store
  16. * some fast and compact auxiliary data.
  17. */
  18. #if defined(CONFIG_SMP) || defined(CONFIG_DEBUG_SPINLOCK)
  19. #define LIST_BL_LOCKMASK 1UL
  20. #else
  21. #define LIST_BL_LOCKMASK 0UL
  22. #endif
  23. #ifdef CONFIG_DEBUG_LIST
  24. #define LIST_BL_BUG_ON(x) BUG_ON(x)
  25. #else
  26. #define LIST_BL_BUG_ON(x)
  27. #endif
  28. struct hlist_bl_head {
  29. struct hlist_bl_node *first;
  30. };
  31. struct hlist_bl_node {
  32. struct hlist_bl_node *next, **pprev;
  33. };
  34. #define INIT_HLIST_BL_HEAD(ptr) \
  35. ((ptr)->first = NULL)
  36. static inline void INIT_HLIST_BL_NODE(struct hlist_bl_node *h)
  37. {
  38. h->next = NULL;
  39. h->pprev = NULL;
  40. }
  41. #define hlist_bl_entry(ptr, type, member) container_of(ptr,type,member)
  42. static inline bool hlist_bl_unhashed(const struct hlist_bl_node *h)
  43. {
  44. return !h->pprev;
  45. }
  46. static inline struct hlist_bl_node *hlist_bl_first(struct hlist_bl_head *h)
  47. {
  48. return (struct hlist_bl_node *)
  49. ((unsigned long)h->first & ~LIST_BL_LOCKMASK);
  50. }
  51. static inline void hlist_bl_set_first(struct hlist_bl_head *h,
  52. struct hlist_bl_node *n)
  53. {
  54. LIST_BL_BUG_ON((unsigned long)n & LIST_BL_LOCKMASK);
  55. LIST_BL_BUG_ON(((unsigned long)h->first & LIST_BL_LOCKMASK) !=
  56. LIST_BL_LOCKMASK);
  57. h->first = (struct hlist_bl_node *)((unsigned long)n | LIST_BL_LOCKMASK);
  58. }
  59. static inline bool hlist_bl_empty(const struct hlist_bl_head *h)
  60. {
  61. return !((unsigned long)READ_ONCE(h->first) & ~LIST_BL_LOCKMASK);
  62. }
  63. static inline void hlist_bl_add_head(struct hlist_bl_node *n,
  64. struct hlist_bl_head *h)
  65. {
  66. struct hlist_bl_node *first = hlist_bl_first(h);
  67. n->next = first;
  68. if (first)
  69. first->pprev = &n->next;
  70. n->pprev = &h->first;
  71. hlist_bl_set_first(h, n);
  72. }
  73. static inline void hlist_bl_add_before(struct hlist_bl_node *n,
  74. struct hlist_bl_node *next)
  75. {
  76. struct hlist_bl_node **pprev = next->pprev;
  77. n->pprev = pprev;
  78. n->next = next;
  79. next->pprev = &n->next;
  80. /* pprev may be `first`, so be careful not to lose the lock bit */
  81. WRITE_ONCE(*pprev,
  82. (struct hlist_bl_node *)
  83. ((uintptr_t)n | ((uintptr_t)*pprev & LIST_BL_LOCKMASK)));
  84. }
  85. static inline void hlist_bl_add_behind(struct hlist_bl_node *n,
  86. struct hlist_bl_node *prev)
  87. {
  88. n->next = prev->next;
  89. n->pprev = &prev->next;
  90. prev->next = n;
  91. if (n->next)
  92. n->next->pprev = &n->next;
  93. }
  94. static inline void __hlist_bl_del(struct hlist_bl_node *n)
  95. {
  96. struct hlist_bl_node *next = n->next;
  97. struct hlist_bl_node **pprev = n->pprev;
  98. LIST_BL_BUG_ON((unsigned long)n & LIST_BL_LOCKMASK);
  99. /* pprev may be `first`, so be careful not to lose the lock bit */
  100. WRITE_ONCE(*pprev,
  101. (struct hlist_bl_node *)
  102. ((unsigned long)next |
  103. ((unsigned long)*pprev & LIST_BL_LOCKMASK)));
  104. if (next)
  105. next->pprev = pprev;
  106. }
  107. static inline void hlist_bl_del(struct hlist_bl_node *n)
  108. {
  109. __hlist_bl_del(n);
  110. n->next = LIST_POISON1;
  111. n->pprev = LIST_POISON2;
  112. }
  113. static inline void hlist_bl_del_init(struct hlist_bl_node *n)
  114. {
  115. if (!hlist_bl_unhashed(n)) {
  116. __hlist_bl_del(n);
  117. INIT_HLIST_BL_NODE(n);
  118. }
  119. }
  120. static inline void hlist_bl_lock(struct hlist_bl_head *b)
  121. {
  122. bit_spin_lock(0, (unsigned long *)b);
  123. }
  124. static inline void hlist_bl_unlock(struct hlist_bl_head *b)
  125. {
  126. __bit_spin_unlock(0, (unsigned long *)b);
  127. }
  128. static inline bool hlist_bl_is_locked(struct hlist_bl_head *b)
  129. {
  130. return bit_spin_is_locked(0, (unsigned long *)b);
  131. }
  132. /**
  133. * hlist_bl_for_each_entry - iterate over list of given type
  134. * @tpos: the type * to use as a loop cursor.
  135. * @pos: the &struct hlist_node to use as a loop cursor.
  136. * @head: the head for your list.
  137. * @member: the name of the hlist_node within the struct.
  138. *
  139. */
  140. #define hlist_bl_for_each_entry(tpos, pos, head, member) \
  141. for (pos = hlist_bl_first(head); \
  142. pos && \
  143. ({ tpos = hlist_bl_entry(pos, typeof(*tpos), member); 1;}); \
  144. pos = pos->next)
  145. /**
  146. * hlist_bl_for_each_entry_safe - iterate over list of given type safe against removal of list entry
  147. * @tpos: the type * to use as a loop cursor.
  148. * @pos: the &struct hlist_node to use as a loop cursor.
  149. * @n: another &struct hlist_node to use as temporary storage
  150. * @head: the head for your list.
  151. * @member: the name of the hlist_node within the struct.
  152. */
  153. #define hlist_bl_for_each_entry_safe(tpos, pos, n, head, member) \
  154. for (pos = hlist_bl_first(head); \
  155. pos && ({ n = pos->next; 1; }) && \
  156. ({ tpos = hlist_bl_entry(pos, typeof(*tpos), member); 1;}); \
  157. pos = n)
  158. #endif