include/linux/list_bl.h

0001 /* SPDX-License-Identifier: GPL-2.0 */
0002 #ifndef _LINUX_LIST_BL_H
0003 #define _LINUX_LIST_BL_H
0004
0005 #include <linux/list.h>
0006 #include <linux/bit_spinlock.h>
0007
0008 /*
0009  * Special version of lists, where head of the list has a lock in the lowest
0010  * bit. This is useful for scalable hash tables without increasing memory
0011  * footprint overhead.
0012  *
0013  * For modification operations, the 0 bit of hlist_bl_head->first
0014  * pointer must be set.
0015  *
0016  * With some small modifications, this can easily be adapted to store several
0017  * arbitrary bits (not just a single lock bit), if the need arises to store
0018  * some fast and compact auxiliary data.
0019  */
0020
0021 #if defined(CONFIG_SMP) || defined(CONFIG_DEBUG_SPINLOCK)
0022 #define LIST_BL_LOCKMASK    1UL
0023 #else
0024 #define LIST_BL_LOCKMASK    0UL
0025 #endif
0026
0027 #ifdef CONFIG_DEBUG_LIST
0028 #define LIST_BL_BUG_ON(x) BUG_ON(x)
0029 #else
0030 #define LIST_BL_BUG_ON(x)
0031 #endif
0032
0033
0034 struct hlist_bl_head {
0035     struct hlist_bl_node *first;
0036 };
0037
0038 struct hlist_bl_node {
0039     struct hlist_bl_node *next, **pprev;
0040 };
0041 #define INIT_HLIST_BL_HEAD(ptr) \
0042     ((ptr)->first = NULL)
0043
0044 static inline void INIT_HLIST_BL_NODE(struct hlist_bl_node *h)
0045 {
0046     h->next = NULL;
0047     h->pprev = NULL;
0048 }
0049
0050 #define hlist_bl_entry(ptr, type, member) container_of(ptr,type,member)
0051
0052 static inline bool  hlist_bl_unhashed(const struct hlist_bl_node *h)
0053 {
0054     return !h->pprev;
0055 }
0056
0057 static inline struct hlist_bl_node *hlist_bl_first(struct hlist_bl_head *h)
0058 {
0059     return (struct hlist_bl_node *)
0060         ((unsigned long)h->first & ~LIST_BL_LOCKMASK);
0061 }
0062
0063 static inline void hlist_bl_set_first(struct hlist_bl_head *h,
0064                     struct hlist_bl_node *n)
0065 {
0066     LIST_BL_BUG_ON((unsigned long)n & LIST_BL_LOCKMASK);
0067     LIST_BL_BUG_ON(((unsigned long)h->first & LIST_BL_LOCKMASK) !=
0068                             LIST_BL_LOCKMASK);
0069     h->first = (struct hlist_bl_node *)((unsigned long)n | LIST_BL_LOCKMASK);
0070 }
0071
0072 static inline bool hlist_bl_empty(const struct hlist_bl_head *h)
0073 {
0074     return !((unsigned long)READ_ONCE(h->first) & ~LIST_BL_LOCKMASK);
0075 }
0076
0077 static inline void hlist_bl_add_head(struct hlist_bl_node *n,
0078                     struct hlist_bl_head *h)
0079 {
0080     struct hlist_bl_node *first = hlist_bl_first(h);
0081
0082     n->next = first;
0083     if (first)
0084         first->pprev = &n->next;
0085     n->pprev = &h->first;
0086     hlist_bl_set_first(h, n);
0087 }
0088
0089 static inline void hlist_bl_add_before(struct hlist_bl_node *n,
0090                        struct hlist_bl_node *next)
0091 {
0092     struct hlist_bl_node **pprev = next->pprev;
0093
0094     n->pprev = pprev;
0095     n->next = next;
0096     next->pprev = &n->next;
0097
0098     /* pprev may be `first`, so be careful not to lose the lock bit */
0099     WRITE_ONCE(*pprev,
0100            (struct hlist_bl_node *)
0101             ((uintptr_t)n | ((uintptr_t)*pprev & LIST_BL_LOCKMASK)));
0102 }
0103
0104 static inline void hlist_bl_add_behind(struct hlist_bl_node *n,
0105                        struct hlist_bl_node *prev)
0106 {
0107     n->next = prev->next;
0108     n->pprev = &prev->next;
0109     prev->next = n;
0110
0111     if (n->next)
0112         n->next->pprev = &n->next;
0113 }
0114
0115 static inline void __hlist_bl_del(struct hlist_bl_node *n)
0116 {
0117     struct hlist_bl_node *next = n->next;
0118     struct hlist_bl_node **pprev = n->pprev;
0119
0120     LIST_BL_BUG_ON((unsigned long)n & LIST_BL_LOCKMASK);
0121
0122     /* pprev may be `first`, so be careful not to lose the lock bit */
0123     WRITE_ONCE(*pprev,
0124            (struct hlist_bl_node *)
0125             ((unsigned long)next |
0126              ((unsigned long)*pprev & LIST_BL_LOCKMASK)));
0127     if (next)
0128         next->pprev = pprev;
0129 }
0130
0131 static inline void hlist_bl_del(struct hlist_bl_node *n)
0132 {
0133     __hlist_bl_del(n);
0134     n->next = LIST_POISON1;
0135     n->pprev = LIST_POISON2;
0136 }
0137
0138 static inline void hlist_bl_del_init(struct hlist_bl_node *n)
0139 {
0140     if (!hlist_bl_unhashed(n)) {
0141         __hlist_bl_del(n);
0142         INIT_HLIST_BL_NODE(n);
0143     }
0144 }
0145
0146 static inline void hlist_bl_lock(struct hlist_bl_head *b)
0147 {
0148     bit_spin_lock(0, (unsigned long *)b);
0149 }
0150
0151 static inline void hlist_bl_unlock(struct hlist_bl_head *b)
0152 {
0153     __bit_spin_unlock(0, (unsigned long *)b);
0154 }
0155
0156 static inline bool hlist_bl_is_locked(struct hlist_bl_head *b)
0157 {
0158     return bit_spin_is_locked(0, (unsigned long *)b);
0159 }
0160
0161 /**
0162  * hlist_bl_for_each_entry  - iterate over list of given type
0163  * @tpos:   the type * to use as a loop cursor.
0164  * @pos:    the &struct hlist_node to use as a loop cursor.
0165  * @head:   the head for your list.
0166  * @member: the name of the hlist_node within the struct.
0167  *
0168  */
0169 #define hlist_bl_for_each_entry(tpos, pos, head, member)        \
0170     for (pos = hlist_bl_first(head);                \
0171          pos &&                         \
0172         ({ tpos = hlist_bl_entry(pos, typeof(*tpos), member); 1;}); \
0173          pos = pos->next)
0174
0175 /**
0176  * hlist_bl_for_each_entry_safe - iterate over list of given type safe against removal of list entry
0177  * @tpos:   the type * to use as a loop cursor.
0178  * @pos:    the &struct hlist_node to use as a loop cursor.
0179  * @n:      another &struct hlist_node to use as temporary storage
0180  * @head:   the head for your list.
0181  * @member: the name of the hlist_node within the struct.
0182  */
0183 #define hlist_bl_for_each_entry_safe(tpos, pos, n, head, member)     \
0184     for (pos = hlist_bl_first(head);                 \
0185          pos && ({ n = pos->next; 1; }) &&               \
0186         ({ tpos = hlist_bl_entry(pos, typeof(*tpos), member); 1;}); \
0187          pos = n)
0188
0189 #endif