Branch data Line data Source code
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 : 331367 : static inline void INIT_HLIST_BL_NODE(struct hlist_bl_node *h)
45 : : {
46 : 331367 : h->next = NULL;
47 : 331367 : h->pprev = NULL;
48 : 0 : }
49 : :
50 : : #define hlist_bl_entry(ptr, type, member) container_of(ptr,type,member)
51 : :
52 : 2702527 : static inline bool hlist_bl_unhashed(const struct hlist_bl_node *h)
53 : : {
54 [ + + + + : 2702021 : return !h->pprev;
+ + + - +
- + - + +
- - - + -
+ - + - +
+ + - - +
+ + + + +
- - - - ]
55 : : }
56 : :
57 : 909421 : static inline struct hlist_bl_node *hlist_bl_first(struct hlist_bl_head *h)
58 : : {
59 : 909421 : return (struct hlist_bl_node *)
60 [ + + + + : 909421 : ((unsigned long)h->first & ~LIST_BL_LOCKMASK);
- - ]
61 : : }
62 : :
63 : 0 : static inline void hlist_bl_set_first(struct hlist_bl_head *h,
64 : : struct hlist_bl_node *n)
65 : : {
66 : 0 : LIST_BL_BUG_ON((unsigned long)n & LIST_BL_LOCKMASK);
67 : : LIST_BL_BUG_ON(((unsigned long)h->first & LIST_BL_LOCKMASK) !=
68 : 0 : LIST_BL_LOCKMASK);
69 : 0 : h->first = (struct hlist_bl_node *)((unsigned long)n | LIST_BL_LOCKMASK);
70 : : }
71 : :
72 : 0 : static inline bool hlist_bl_empty(const struct hlist_bl_head *h)
73 : : {
74 [ # # ]: 0 : return !((unsigned long)READ_ONCE(h->first) & ~LIST_BL_LOCKMASK);
75 : : }
76 : :
77 : 0 : static inline void hlist_bl_add_head(struct hlist_bl_node *n,
78 : : struct hlist_bl_head *h)
79 : : {
80 : 0 : struct hlist_bl_node *first = hlist_bl_first(h);
81 : :
82 : 0 : n->next = first;
83 [ # # ]: 0 : if (first)
84 : 0 : first->pprev = &n->next;
85 : 0 : n->pprev = &h->first;
86 : 0 : 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 : 395502 : static inline void __hlist_bl_del(struct hlist_bl_node *n)
116 : : {
117 : 395502 : struct hlist_bl_node *next = n->next;
118 : 395502 : struct hlist_bl_node **pprev = n->pprev;
119 : :
120 : 395502 : 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 [ + + + + ]: 395502 : WRITE_ONCE(*pprev,
124 : : (struct hlist_bl_node *)
125 : : ((unsigned long)next |
126 : : ((unsigned long)*pprev & LIST_BL_LOCKMASK)));
127 [ + + + + : 395502 : if (next)
# # ]
128 : 7756 : 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 : 0 : static inline void hlist_bl_del_init(struct hlist_bl_node *n)
139 : : {
140 [ # # ]: 0 : if (!hlist_bl_unhashed(n)) {
141 [ # # # # : 0 : __hlist_bl_del(n);
# # ]
142 : 0 : INIT_HLIST_BL_NODE(n);
143 : : }
144 : : }
145 : :
146 : 996031 : static inline void hlist_bl_lock(struct hlist_bl_head *b)
147 : : {
148 : 996031 : bit_spin_lock(0, (unsigned long *)b);
149 : : }
150 : :
151 : 996031 : static inline void hlist_bl_unlock(struct hlist_bl_head *b)
152 : : {
153 : 996031 : __bit_spin_unlock(0, (unsigned long *)b);
154 : 0 : }
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
|
