Commit | Line | Data |
---|---|---|
2ed95849 | 1 | |
5e28c532 MD |
2 | /* |
3 | * TODO: keys are currently assumed <= sizeof(void *). Key target never freed. | |
4 | */ | |
5 | ||
2ed95849 MD |
6 | #define _LGPL_SOURCE |
7 | #include <stdlib.h> | |
8 | #include <urcu.h> | |
9 | #include <arch.h> | |
10 | #include <arch_atomic.h> | |
11 | #include <assert.h> | |
12 | #include <compiler.h> | |
13 | #include <urcu-defer.h> | |
14 | #include <errno.h> | |
ab7d5fc6 | 15 | #include <urcu-ht.h> |
674f7a69 | 16 | #include <urcu/jhash.h> |
5e28c532 | 17 | #include <stdio.h> |
2ed95849 MD |
18 | |
19 | struct rcu_ht_node; | |
20 | ||
21 | struct rcu_ht_node { | |
22 | struct rcu_ht_node *next; | |
23 | void *key; | |
24 | void *data; | |
25 | }; | |
26 | ||
27 | struct rcu_ht { | |
674f7a69 | 28 | struct rcu_ht_node **tbl; |
2ed95849 MD |
29 | ht_hash_fct hash_fct; |
30 | void (*free_fct)(void *data); /* fct to free data */ | |
5e28c532 MD |
31 | uint32_t keylen; |
32 | uint32_t hashseed; | |
674f7a69 MD |
33 | struct ht_size { |
34 | unsigned long add; | |
35 | unsigned long lookup; | |
36 | } size; | |
2ed95849 MD |
37 | }; |
38 | ||
674f7a69 | 39 | struct rcu_ht *ht_new(ht_hash_fct hash_fct, void (*free_fct)(void *data), |
5e28c532 MD |
40 | unsigned long init_size, uint32_t keylen, |
41 | uint32_t hashseed) | |
2ed95849 MD |
42 | { |
43 | struct rcu_ht *ht; | |
44 | ||
45 | ht = calloc(1, sizeof(struct rcu_ht)); | |
46 | ht->hash_fct = hash_fct; | |
47 | ht->free_fct = free_fct; | |
674f7a69 MD |
48 | ht->size.add = init_size; |
49 | ht->size.lookup = init_size; | |
5e28c532 MD |
50 | ht->keylen = keylen; |
51 | ht->hashseed = hashseed; | |
674f7a69 | 52 | ht->tbl = calloc(init_size, sizeof(struct rcu_ht_node *)); |
ab7d5fc6 | 53 | return ht; |
2ed95849 MD |
54 | } |
55 | ||
2ed95849 MD |
56 | void *ht_lookup(struct rcu_ht *ht, void *key) |
57 | { | |
58 | unsigned long hash; | |
59 | struct rcu_ht_node *node; | |
60 | void *ret; | |
61 | ||
5e28c532 | 62 | hash = ht->hash_fct(key, ht->keylen, ht->hashseed) % ht->size.lookup; |
2ed95849 MD |
63 | |
64 | rcu_read_lock(); | |
5e28c532 | 65 | node = rcu_dereference(ht->tbl[hash]); |
2ed95849 MD |
66 | for (;;) { |
67 | if (likely(!node)) { | |
68 | ret = NULL; | |
69 | break; | |
70 | } | |
71 | if (node->key == key) { | |
72 | ret = node->data; | |
73 | break; | |
74 | } | |
75 | node = rcu_dereference(node->next); | |
76 | } | |
77 | rcu_read_unlock(); | |
ab7d5fc6 MD |
78 | |
79 | return ret; | |
2ed95849 MD |
80 | } |
81 | ||
82 | /* | |
83 | * Will re-try until either: | |
84 | * - The key is already there (-EEXIST) | |
85 | * - We successfully add the key at the head of a table bucket. | |
86 | */ | |
87 | int ht_add(struct rcu_ht *ht, void *key, void *data) | |
88 | { | |
89 | struct rcu_ht_node *node, *old_head, *new_head; | |
90 | unsigned long hash; | |
91 | int ret = 0; | |
92 | ||
93 | new_head = calloc(1, sizeof(struct rcu_ht_node)); | |
94 | new_head->key = key; | |
95 | new_head->data = data; | |
2ed95849 MD |
96 | /* here comes the fun and tricky part. |
97 | * Add at the beginning with a cmpxchg. | |
98 | * Hold a read lock between the moment the first element is read | |
99 | * and the nodes traversal (to find duplicates). This ensures | |
100 | * the head pointer has not been reclaimed when cmpxchg is done. | |
101 | * Always adding at the head ensures that we would have to | |
102 | * re-try if a new item has been added concurrently. So we ensure that | |
103 | * we never add duplicates. */ | |
104 | retry: | |
105 | rcu_read_lock(); | |
106 | ||
5e28c532 MD |
107 | hash = ht->hash_fct(key, ht->keylen, ht->hashseed) % ht->size.add; |
108 | ||
109 | old_head = node = rcu_dereference(ht->tbl[hash]); | |
2ed95849 MD |
110 | for (;;) { |
111 | if (likely(!node)) { | |
112 | break; | |
113 | } | |
114 | if (node->key == key) { | |
115 | ret = -EEXIST; | |
116 | goto end; | |
117 | } | |
118 | node = rcu_dereference(node->next); | |
119 | } | |
5e28c532 MD |
120 | new_head->next = old_head; |
121 | if (rcu_cmpxchg_pointer(&ht->tbl[hash], old_head, new_head) != old_head) | |
2ed95849 MD |
122 | goto restart; |
123 | end: | |
124 | rcu_read_unlock(); | |
125 | ||
126 | return ret; | |
127 | ||
128 | /* restart loop, release and re-take the read lock to be kind to GP */ | |
129 | restart: | |
130 | rcu_read_unlock(); | |
131 | goto retry; | |
132 | } | |
133 | ||
134 | /* | |
135 | * Restart until we successfully remove the entry, or no entry is left | |
136 | * ((void *)(unsigned long)-ENOENT). | |
137 | */ | |
ab7d5fc6 | 138 | void *ht_steal(struct rcu_ht *ht, void *key) |
2ed95849 MD |
139 | { |
140 | struct rcu_ht_node **prev, *node; | |
141 | unsigned long hash; | |
ab7d5fc6 | 142 | void *data; |
2ed95849 | 143 | |
2ed95849 MD |
144 | retry: |
145 | rcu_read_lock(); | |
146 | ||
5e28c532 MD |
147 | hash = ht->hash_fct(key, ht->keylen, ht->hashseed) % ht->size.lookup; |
148 | ||
149 | prev = &ht->tbl[hash]; | |
2ed95849 MD |
150 | node = rcu_dereference(*prev); |
151 | for (;;) { | |
152 | if (likely(!node)) { | |
ab7d5fc6 | 153 | data = (void *)(unsigned long)-ENOENT; |
5e28c532 | 154 | goto error; |
2ed95849 MD |
155 | } |
156 | if (node->key == key) { | |
157 | break; | |
158 | } | |
159 | prev = &node->next; | |
160 | node = rcu_dereference(*prev); | |
161 | } | |
162 | /* Found it ! pointer to object is in "prev" */ | |
163 | if (rcu_cmpxchg_pointer(prev, node, node->next) != node) | |
164 | goto restart; | |
5e28c532 MD |
165 | |
166 | /* From that point, we own node. We can free it outside of read lock */ | |
2ed95849 MD |
167 | rcu_read_unlock(); |
168 | ||
ab7d5fc6 MD |
169 | data = node->data; |
170 | call_rcu(free, node); | |
5e28c532 | 171 | return data; |
ab7d5fc6 | 172 | |
5e28c532 MD |
173 | error: |
174 | rcu_read_unlock(); | |
ab7d5fc6 | 175 | return data; |
2ed95849 MD |
176 | |
177 | /* restart loop, release and re-take the read lock to be kind to GP */ | |
178 | restart: | |
179 | rcu_read_unlock(); | |
180 | goto retry; | |
181 | } | |
182 | ||
183 | int ht_delete(struct rcu_ht *ht, void *key) | |
184 | { | |
ab7d5fc6 | 185 | void *data; |
2ed95849 | 186 | |
ab7d5fc6 | 187 | data = ht_steal(ht, key); |
5e28c532 MD |
188 | if (data && data != (void *)(unsigned long)-ENOENT) { |
189 | if (ht->free_fct) | |
ab7d5fc6 | 190 | call_rcu(ht->free_fct, data); |
2ed95849 MD |
191 | return 0; |
192 | } else { | |
193 | return -ENOENT; | |
194 | } | |
195 | } | |
ab7d5fc6 | 196 | |
674f7a69 | 197 | /* Delete all old elements. Allow concurrent writer accesses. */ |
5e28c532 | 198 | int ht_delete_all(struct rcu_ht *ht) |
674f7a69 MD |
199 | { |
200 | unsigned long i; | |
201 | struct rcu_ht_node **prev, *node, *inext; | |
5e28c532 | 202 | int cnt = 0; |
674f7a69 MD |
203 | |
204 | for (i = 0; i < ht->size.lookup; i++) { | |
205 | rcu_read_lock(); | |
5e28c532 MD |
206 | prev = &ht->tbl[i]; |
207 | /* | |
208 | * Cut the head. After that, we own the first element. | |
209 | */ | |
210 | node = rcu_xchg_pointer(prev, NULL); | |
211 | if (!node) { | |
674f7a69 MD |
212 | rcu_read_unlock(); |
213 | continue; | |
214 | } | |
215 | /* | |
216 | * We manage a list shared with concurrent writers and readers. | |
217 | * Note that a concurrent add may or may not be deleted by us, | |
218 | * depending if it arrives before or after the head is cut. | |
219 | * "node" points to our first node. Remove first elements | |
220 | * iteratively. | |
221 | */ | |
222 | for (;;) { | |
5e28c532 | 223 | inext = NULL; |
674f7a69 | 224 | prev = &node->next; |
5e28c532 MD |
225 | if (prev) |
226 | inext = rcu_xchg_pointer(prev, NULL); | |
674f7a69 MD |
227 | /* |
228 | * "node" is the first element of the list we have cut. | |
229 | * We therefore own it, no concurrent writer may delete | |
230 | * it. There can only be concurrent lookups. Concurrent | |
231 | * add can only be done on a bucket head, but we've cut | |
232 | * it already. inext is also owned by us, because we | |
233 | * have exchanged it for "NULL". It will therefore be | |
234 | * safe to use it after a G.P. | |
235 | */ | |
236 | rcu_read_unlock(); | |
237 | if (node->data) | |
238 | call_rcu(ht->free_fct, node->data); | |
239 | call_rcu(free, node); | |
5e28c532 | 240 | cnt++; |
674f7a69 MD |
241 | if (likely(!inext)) |
242 | break; | |
243 | rcu_read_lock(); | |
244 | node = inext; | |
245 | } | |
246 | } | |
5e28c532 | 247 | return cnt; |
674f7a69 MD |
248 | } |
249 | ||
250 | /* | |
251 | * Should only be called when no more concurrent readers nor writers can | |
252 | * possibly access the table. | |
253 | */ | |
5e28c532 | 254 | int ht_destroy(struct rcu_ht *ht) |
674f7a69 | 255 | { |
5e28c532 MD |
256 | int ret; |
257 | ||
258 | ret = ht_delete_all(ht); | |
674f7a69 MD |
259 | free(ht->tbl); |
260 | free(ht); | |
5e28c532 | 261 | return ret; |
674f7a69 MD |
262 | } |
263 | ||
5e28c532 MD |
264 | /* |
265 | * Expects keys <= than pointer size to be encoded in the pointer itself. | |
266 | */ | |
674f7a69 | 267 | uint32_t ht_jhash(void *key, uint32_t length, uint32_t initval) |
ab7d5fc6 | 268 | { |
5e28c532 MD |
269 | uint32_t ret; |
270 | void *vkey; | |
271 | ||
272 | if (length <= sizeof(u32)) | |
273 | vkey = &key; | |
274 | else | |
275 | vkey = key; | |
276 | ret = jhash(vkey, length, initval); | |
277 | return ret; | |
ab7d5fc6 | 278 | } |