diff options
author | Nick Piggin <npiggin@kernel.dk> | 2011-01-07 01:50:03 -0500 |
---|---|---|
committer | Nick Piggin <npiggin@kernel.dk> | 2011-01-07 01:50:31 -0500 |
commit | 4e35e6070b1ceed89c3bba2af4216c286fb1dafd (patch) | |
tree | 94bd18604a978380c1fde46a3f188f1639067960 /include/linux/list_bl.h | |
parent | 880566e17c4fce0d998d92610d32fcb9506aa6dd (diff) |
kernel: add bl_list
Introduce a type of hlist that can support the use of the lowest bit in the
hlist_head. This will be subsequently used to implement per-bucket bit spinlock
for inode and dentry hashes, and may be useful in other cases such as network
hashes.
Reviewed-by: Paul E. McKenney <paulmck@linux.vnet.ibm.com>
Signed-off-by: Nick Piggin <npiggin@kernel.dk>
Diffstat (limited to 'include/linux/list_bl.h')
-rw-r--r-- | include/linux/list_bl.h | 144 |
1 files changed, 144 insertions, 0 deletions
diff --git a/include/linux/list_bl.h b/include/linux/list_bl.h new file mode 100644 index 000000000000..9ee97e7f2be4 --- /dev/null +++ b/include/linux/list_bl.h | |||
@@ -0,0 +1,144 @@ | |||
1 | #ifndef _LINUX_LIST_BL_H | ||
2 | #define _LINUX_LIST_BL_H | ||
3 | |||
4 | #include <linux/list.h> | ||
5 | |||
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 | |||
19 | #if defined(CONFIG_SMP) || defined(CONFIG_DEBUG_SPINLOCK) | ||
20 | #define LIST_BL_LOCKMASK 1UL | ||
21 | #else | ||
22 | #define LIST_BL_LOCKMASK 0UL | ||
23 | #endif | ||
24 | |||
25 | #ifdef CONFIG_DEBUG_LIST | ||
26 | #define LIST_BL_BUG_ON(x) BUG_ON(x) | ||
27 | #else | ||
28 | #define LIST_BL_BUG_ON(x) | ||
29 | #endif | ||
30 | |||
31 | |||
32 | struct hlist_bl_head { | ||
33 | struct hlist_bl_node *first; | ||
34 | }; | ||
35 | |||
36 | struct hlist_bl_node { | ||
37 | struct hlist_bl_node *next, **pprev; | ||
38 | }; | ||
39 | #define INIT_HLIST_BL_HEAD(ptr) \ | ||
40 | ((ptr)->first = NULL) | ||
41 | |||
42 | static inline void INIT_HLIST_BL_NODE(struct hlist_bl_node *h) | ||
43 | { | ||
44 | h->next = NULL; | ||
45 | h->pprev = NULL; | ||
46 | } | ||
47 | |||
48 | #define hlist_bl_entry(ptr, type, member) container_of(ptr,type,member) | ||
49 | |||
50 | static inline int hlist_bl_unhashed(const struct hlist_bl_node *h) | ||
51 | { | ||
52 | return !h->pprev; | ||
53 | } | ||
54 | |||
55 | static inline struct hlist_bl_node *hlist_bl_first(struct hlist_bl_head *h) | ||
56 | { | ||
57 | return (struct hlist_bl_node *) | ||
58 | ((unsigned long)h->first & ~LIST_BL_LOCKMASK); | ||
59 | } | ||
60 | |||
61 | static inline void hlist_bl_set_first(struct hlist_bl_head *h, | ||
62 | struct hlist_bl_node *n) | ||
63 | { | ||
64 | LIST_BL_BUG_ON((unsigned long)n & LIST_BL_LOCKMASK); | ||
65 | LIST_BL_BUG_ON(!((unsigned long)h->first & LIST_BL_LOCKMASK)); | ||
66 | h->first = (struct hlist_bl_node *)((unsigned long)n | LIST_BL_LOCKMASK); | ||
67 | } | ||
68 | |||
69 | static inline int hlist_bl_empty(const struct hlist_bl_head *h) | ||
70 | { | ||
71 | return !((unsigned long)h->first & ~LIST_BL_LOCKMASK); | ||
72 | } | ||
73 | |||
74 | static inline void hlist_bl_add_head(struct hlist_bl_node *n, | ||
75 | struct hlist_bl_head *h) | ||
76 | { | ||
77 | struct hlist_bl_node *first = hlist_bl_first(h); | ||
78 | |||
79 | n->next = first; | ||
80 | if (first) | ||
81 | first->pprev = &n->next; | ||
82 | n->pprev = &h->first; | ||
83 | hlist_bl_set_first(h, n); | ||
84 | } | ||
85 | |||
86 | static inline void __hlist_bl_del(struct hlist_bl_node *n) | ||
87 | { | ||
88 | struct hlist_bl_node *next = n->next; | ||
89 | struct hlist_bl_node **pprev = n->pprev; | ||
90 | |||
91 | LIST_BL_BUG_ON((unsigned long)n & LIST_BL_LOCKMASK); | ||
92 | |||
93 | /* pprev may be `first`, so be careful not to lose the lock bit */ | ||
94 | *pprev = (struct hlist_bl_node *) | ||
95 | ((unsigned long)next | | ||
96 | ((unsigned long)*pprev & LIST_BL_LOCKMASK)); | ||
97 | if (next) | ||
98 | next->pprev = pprev; | ||
99 | } | ||
100 | |||
101 | static inline void hlist_bl_del(struct hlist_bl_node *n) | ||
102 | { | ||
103 | __hlist_bl_del(n); | ||
104 | n->next = LIST_POISON1; | ||
105 | n->pprev = LIST_POISON2; | ||
106 | } | ||
107 | |||
108 | static inline void hlist_bl_del_init(struct hlist_bl_node *n) | ||
109 | { | ||
110 | if (!hlist_bl_unhashed(n)) { | ||
111 | __hlist_bl_del(n); | ||
112 | INIT_HLIST_BL_NODE(n); | ||
113 | } | ||
114 | } | ||
115 | |||
116 | /** | ||
117 | * hlist_bl_for_each_entry - iterate over list of given type | ||
118 | * @tpos: the type * to use as a loop cursor. | ||
119 | * @pos: the &struct hlist_node to use as a loop cursor. | ||
120 | * @head: the head for your list. | ||
121 | * @member: the name of the hlist_node within the struct. | ||
122 | * | ||
123 | */ | ||
124 | #define hlist_bl_for_each_entry(tpos, pos, head, member) \ | ||
125 | for (pos = hlist_bl_first(head); \ | ||
126 | pos && \ | ||
127 | ({ tpos = hlist_bl_entry(pos, typeof(*tpos), member); 1;}); \ | ||
128 | pos = pos->next) | ||
129 | |||
130 | /** | ||
131 | * hlist_bl_for_each_entry_safe - iterate over list of given type safe against removal of list entry | ||
132 | * @tpos: the type * to use as a loop cursor. | ||
133 | * @pos: the &struct hlist_node to use as a loop cursor. | ||
134 | * @n: another &struct hlist_node to use as temporary storage | ||
135 | * @head: the head for your list. | ||
136 | * @member: the name of the hlist_node within the struct. | ||
137 | */ | ||
138 | #define hlist_bl_for_each_entry_safe(tpos, pos, n, head, member) \ | ||
139 | for (pos = hlist_bl_first(head); \ | ||
140 | pos && ({ n = pos->next; 1; }) && \ | ||
141 | ({ tpos = hlist_bl_entry(pos, typeof(*tpos), member); 1;}); \ | ||
142 | pos = n) | ||
143 | |||
144 | #endif | ||