include/linux/list_bl.h

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