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