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> | |
e0ba718a MD |
8 | #include <errno.h> |
9 | #include <assert.h> | |
10 | #include <stdio.h> | |
11 | ||
2ed95849 | 12 | #include <urcu.h> |
e0ba718a | 13 | #include <urcu-defer.h> |
2ed95849 MD |
14 | #include <arch.h> |
15 | #include <arch_atomic.h> | |
2ed95849 | 16 | #include <compiler.h> |
674f7a69 | 17 | #include <urcu/jhash.h> |
5e28c532 | 18 | #include <stdio.h> |
464a1ec9 | 19 | #include <pthread.h> |
e0ba718a | 20 | #include <urcu-ht.h> |
2ed95849 | 21 | |
44395fb7 MD |
22 | /* |
23 | * Maximum number of hash table buckets: 256M on 64-bit. | |
24 | * Should take about 512MB max if we assume 1 node per 4 buckets. | |
25 | */ | |
26 | #define MAX_HT_BUCKETS ((256 << 10) / sizeof(void *)) | |
27 | ||
3df2df75 MD |
28 | /* node flags */ |
29 | #define NODE_STOLEN (1 << 0) | |
2ed95849 MD |
30 | |
31 | struct rcu_ht_node; | |
32 | ||
33 | struct rcu_ht_node { | |
34 | struct rcu_ht_node *next; | |
35 | void *key; | |
36 | void *data; | |
3df2df75 | 37 | unsigned int flags; |
2ed95849 MD |
38 | }; |
39 | ||
395270b6 MD |
40 | struct rcu_table { |
41 | unsigned long size; | |
42 | struct rcu_ht_node *tbl[0]; | |
43 | }; | |
44 | ||
2ed95849 | 45 | struct rcu_ht { |
395270b6 | 46 | struct rcu_table *t; /* shared */ |
2ed95849 MD |
47 | ht_hash_fct hash_fct; |
48 | void (*free_fct)(void *data); /* fct to free data */ | |
5e28c532 MD |
49 | uint32_t keylen; |
50 | uint32_t hashseed; | |
464a1ec9 MD |
51 | pthread_mutex_t resize_mutex; /* resize mutex: add/del mutex */ |
52 | int resize_ongoing; /* fast-path resize check */ | |
2ed95849 MD |
53 | }; |
54 | ||
674f7a69 | 55 | struct rcu_ht *ht_new(ht_hash_fct hash_fct, void (*free_fct)(void *data), |
5e28c532 MD |
56 | unsigned long init_size, uint32_t keylen, |
57 | uint32_t hashseed) | |
2ed95849 MD |
58 | { |
59 | struct rcu_ht *ht; | |
60 | ||
61 | ht = calloc(1, sizeof(struct rcu_ht)); | |
62 | ht->hash_fct = hash_fct; | |
63 | ht->free_fct = free_fct; | |
5e28c532 MD |
64 | ht->keylen = keylen; |
65 | ht->hashseed = hashseed; | |
464a1ec9 MD |
66 | /* this mutex should not nest in read-side C.S. */ |
67 | pthread_mutex_init(&ht->resize_mutex, NULL); | |
44395fb7 | 68 | ht->resize_ongoing = 0; /* shared */ |
395270b6 MD |
69 | ht->t = calloc(1, sizeof(struct rcu_table) |
70 | + (init_size * sizeof(struct rcu_ht_node *))); | |
71 | ht->t->size = init_size; | |
ab7d5fc6 | 72 | return ht; |
2ed95849 MD |
73 | } |
74 | ||
2ed95849 MD |
75 | void *ht_lookup(struct rcu_ht *ht, void *key) |
76 | { | |
395270b6 | 77 | struct rcu_table *t; |
2ed95849 MD |
78 | unsigned long hash; |
79 | struct rcu_ht_node *node; | |
80 | void *ret; | |
81 | ||
2ed95849 | 82 | rcu_read_lock(); |
395270b6 MD |
83 | t = rcu_dereference(ht->t); |
84 | smp_read_barrier_depends(); /* read t before size and table */ | |
85 | hash = ht->hash_fct(key, ht->keylen, ht->hashseed) % t->size; | |
86 | smp_read_barrier_depends(); /* read size before links */ | |
87 | node = rcu_dereference(t->tbl[hash]); | |
2ed95849 MD |
88 | for (;;) { |
89 | if (likely(!node)) { | |
90 | ret = NULL; | |
91 | break; | |
92 | } | |
93 | if (node->key == key) { | |
94 | ret = node->data; | |
95 | break; | |
96 | } | |
97 | node = rcu_dereference(node->next); | |
98 | } | |
99 | rcu_read_unlock(); | |
ab7d5fc6 MD |
100 | |
101 | return ret; | |
2ed95849 MD |
102 | } |
103 | ||
104 | /* | |
105 | * Will re-try until either: | |
106 | * - The key is already there (-EEXIST) | |
107 | * - We successfully add the key at the head of a table bucket. | |
108 | */ | |
109 | int ht_add(struct rcu_ht *ht, void *key, void *data) | |
110 | { | |
111 | struct rcu_ht_node *node, *old_head, *new_head; | |
395270b6 | 112 | struct rcu_table *t; |
2ed95849 MD |
113 | unsigned long hash; |
114 | int ret = 0; | |
115 | ||
116 | new_head = calloc(1, sizeof(struct rcu_ht_node)); | |
117 | new_head->key = key; | |
118 | new_head->data = data; | |
3df2df75 | 119 | new_head->flags = 0; |
2ed95849 MD |
120 | /* here comes the fun and tricky part. |
121 | * Add at the beginning with a cmpxchg. | |
122 | * Hold a read lock between the moment the first element is read | |
123 | * and the nodes traversal (to find duplicates). This ensures | |
124 | * the head pointer has not been reclaimed when cmpxchg is done. | |
125 | * Always adding at the head ensures that we would have to | |
126 | * re-try if a new item has been added concurrently. So we ensure that | |
127 | * we never add duplicates. */ | |
128 | retry: | |
129 | rcu_read_lock(); | |
130 | ||
44395fb7 | 131 | if (unlikely(LOAD_SHARED(ht->resize_ongoing))) { |
464a1ec9 MD |
132 | rcu_read_unlock(); |
133 | /* | |
134 | * Wait for resize to complete before continuing. | |
135 | */ | |
136 | ret = pthread_mutex_lock(&ht->resize_mutex); | |
137 | assert(!ret); | |
138 | ret = pthread_mutex_unlock(&ht->resize_mutex); | |
139 | assert(!ret); | |
140 | goto retry; | |
141 | } | |
142 | ||
395270b6 MD |
143 | t = rcu_dereference(ht->t); |
144 | /* no read barrier needed, because no concurrency with resize */ | |
145 | hash = ht->hash_fct(key, ht->keylen, ht->hashseed) % t->size; | |
5e28c532 | 146 | |
395270b6 | 147 | old_head = node = rcu_dereference(t->tbl[hash]); |
2ed95849 MD |
148 | for (;;) { |
149 | if (likely(!node)) { | |
150 | break; | |
151 | } | |
152 | if (node->key == key) { | |
153 | ret = -EEXIST; | |
154 | goto end; | |
155 | } | |
156 | node = rcu_dereference(node->next); | |
157 | } | |
5e28c532 | 158 | new_head->next = old_head; |
395270b6 | 159 | if (rcu_cmpxchg_pointer(&t->tbl[hash], old_head, new_head) != old_head) |
2ed95849 MD |
160 | goto restart; |
161 | end: | |
162 | rcu_read_unlock(); | |
2ed95849 MD |
163 | return ret; |
164 | ||
165 | /* restart loop, release and re-take the read lock to be kind to GP */ | |
166 | restart: | |
167 | rcu_read_unlock(); | |
168 | goto retry; | |
169 | } | |
170 | ||
171 | /* | |
172 | * Restart until we successfully remove the entry, or no entry is left | |
173 | * ((void *)(unsigned long)-ENOENT). | |
e0ba718a MD |
174 | * Deal with concurrent stealers by doing an extra verification pass to check |
175 | * that no element in the list are still pointing to the element stolen. | |
176 | * This could happen if two concurrent steal for consecutive objects are | |
177 | * executed. A pointer to an object being stolen could be saved by the | |
178 | * concurrent stealer for the previous object. | |
179 | * Also, given that in this precise scenario, another stealer can also want to | |
180 | * delete the doubly-referenced object; use a "stolen" flag to let only one | |
181 | * stealer delete the object. | |
2ed95849 | 182 | */ |
ab7d5fc6 | 183 | void *ht_steal(struct rcu_ht *ht, void *key) |
2ed95849 | 184 | { |
2e6070d0 | 185 | struct rcu_ht_node **prev, *node, *del_node = NULL; |
395270b6 | 186 | struct rcu_table *t; |
2ed95849 | 187 | unsigned long hash; |
ab7d5fc6 | 188 | void *data; |
464a1ec9 | 189 | int ret; |
2ed95849 | 190 | |
2ed95849 MD |
191 | retry: |
192 | rcu_read_lock(); | |
193 | ||
44395fb7 | 194 | if (unlikely(LOAD_SHARED(ht->resize_ongoing))) { |
464a1ec9 MD |
195 | rcu_read_unlock(); |
196 | /* | |
197 | * Wait for resize to complete before continuing. | |
198 | */ | |
199 | ret = pthread_mutex_lock(&ht->resize_mutex); | |
200 | assert(!ret); | |
201 | ret = pthread_mutex_unlock(&ht->resize_mutex); | |
202 | assert(!ret); | |
203 | goto retry; | |
204 | } | |
205 | ||
395270b6 MD |
206 | t = rcu_dereference(ht->t); |
207 | /* no read barrier needed, because no concurrency with resize */ | |
208 | hash = ht->hash_fct(key, ht->keylen, ht->hashseed) % t->size; | |
5e28c532 | 209 | |
395270b6 | 210 | prev = &t->tbl[hash]; |
2ed95849 MD |
211 | node = rcu_dereference(*prev); |
212 | for (;;) { | |
213 | if (likely(!node)) { | |
2e6070d0 MD |
214 | if (del_node) { |
215 | goto end; | |
216 | } else { | |
2e6070d0 MD |
217 | goto error; |
218 | } | |
2ed95849 MD |
219 | } |
220 | if (node->key == key) { | |
221 | break; | |
222 | } | |
223 | prev = &node->next; | |
224 | node = rcu_dereference(*prev); | |
225 | } | |
e0ba718a | 226 | |
85f6ba5f MD |
227 | if (!del_node) { |
228 | /* | |
229 | * Another concurrent thread stole it ? If so, let it deal with | |
3df2df75 MD |
230 | * this. Assume NODE_STOLEN is the only flag. If this changes, |
231 | * read flags before cmpxchg. | |
85f6ba5f | 232 | */ |
3df2df75 | 233 | if (cmpxchg(&node->flags, 0, NODE_STOLEN) != 0) |
85f6ba5f MD |
234 | goto error; |
235 | } | |
e0ba718a | 236 | |
2ed95849 | 237 | /* Found it ! pointer to object is in "prev" */ |
7ce4eb38 | 238 | if (rcu_cmpxchg_pointer(prev, node, node->next) == node) |
2e6070d0 MD |
239 | del_node = node; |
240 | goto restart; | |
5e28c532 | 241 | |
2e6070d0 MD |
242 | end: |
243 | /* | |
244 | * From that point, we own node. Note that there can still be concurrent | |
245 | * RCU readers using it. We can free it outside of read lock after a GP. | |
246 | */ | |
2ed95849 MD |
247 | rcu_read_unlock(); |
248 | ||
567d7550 MD |
249 | data = del_node->data; |
250 | call_rcu(free, del_node); | |
5e28c532 | 251 | return data; |
ab7d5fc6 | 252 | |
5e28c532 | 253 | error: |
e0ba718a | 254 | data = (void *)(unsigned long)-ENOENT; |
5e28c532 | 255 | rcu_read_unlock(); |
ab7d5fc6 | 256 | return data; |
2ed95849 MD |
257 | |
258 | /* restart loop, release and re-take the read lock to be kind to GP */ | |
259 | restart: | |
260 | rcu_read_unlock(); | |
261 | goto retry; | |
262 | } | |
263 | ||
264 | int ht_delete(struct rcu_ht *ht, void *key) | |
265 | { | |
ab7d5fc6 | 266 | void *data; |
2ed95849 | 267 | |
ab7d5fc6 | 268 | data = ht_steal(ht, key); |
5e28c532 MD |
269 | if (data && data != (void *)(unsigned long)-ENOENT) { |
270 | if (ht->free_fct) | |
ab7d5fc6 | 271 | call_rcu(ht->free_fct, data); |
2ed95849 MD |
272 | return 0; |
273 | } else { | |
274 | return -ENOENT; | |
275 | } | |
276 | } | |
ab7d5fc6 | 277 | |
674f7a69 | 278 | /* Delete all old elements. Allow concurrent writer accesses. */ |
5e28c532 | 279 | int ht_delete_all(struct rcu_ht *ht) |
674f7a69 MD |
280 | { |
281 | unsigned long i; | |
282 | struct rcu_ht_node **prev, *node, *inext; | |
395270b6 | 283 | struct rcu_table *t; |
5e28c532 | 284 | int cnt = 0; |
464a1ec9 MD |
285 | int ret; |
286 | ||
287 | /* | |
288 | * Mutual exclusion with resize operations, but leave add/steal execute | |
289 | * concurrently. This is OK because we operate only on the heads. | |
290 | */ | |
291 | ret = pthread_mutex_lock(&ht->resize_mutex); | |
292 | assert(!ret); | |
674f7a69 | 293 | |
395270b6 MD |
294 | t = rcu_dereference(ht->t); |
295 | /* no read barrier needed, because no concurrency with resize */ | |
296 | for (i = 0; i < t->size; i++) { | |
674f7a69 | 297 | rcu_read_lock(); |
395270b6 | 298 | prev = &t->tbl[i]; |
5e28c532 MD |
299 | /* |
300 | * Cut the head. After that, we own the first element. | |
301 | */ | |
302 | node = rcu_xchg_pointer(prev, NULL); | |
303 | if (!node) { | |
674f7a69 MD |
304 | rcu_read_unlock(); |
305 | continue; | |
306 | } | |
307 | /* | |
308 | * We manage a list shared with concurrent writers and readers. | |
309 | * Note that a concurrent add may or may not be deleted by us, | |
310 | * depending if it arrives before or after the head is cut. | |
311 | * "node" points to our first node. Remove first elements | |
312 | * iteratively. | |
313 | */ | |
314 | for (;;) { | |
5e28c532 | 315 | inext = NULL; |
674f7a69 | 316 | prev = &node->next; |
5e28c532 MD |
317 | if (prev) |
318 | inext = rcu_xchg_pointer(prev, NULL); | |
674f7a69 MD |
319 | /* |
320 | * "node" is the first element of the list we have cut. | |
321 | * We therefore own it, no concurrent writer may delete | |
322 | * it. There can only be concurrent lookups. Concurrent | |
323 | * add can only be done on a bucket head, but we've cut | |
324 | * it already. inext is also owned by us, because we | |
325 | * have exchanged it for "NULL". It will therefore be | |
326 | * safe to use it after a G.P. | |
327 | */ | |
328 | rcu_read_unlock(); | |
329 | if (node->data) | |
330 | call_rcu(ht->free_fct, node->data); | |
331 | call_rcu(free, node); | |
5e28c532 | 332 | cnt++; |
674f7a69 MD |
333 | if (likely(!inext)) |
334 | break; | |
335 | rcu_read_lock(); | |
336 | node = inext; | |
337 | } | |
338 | } | |
464a1ec9 MD |
339 | |
340 | ret = pthread_mutex_unlock(&ht->resize_mutex); | |
341 | assert(!ret); | |
5e28c532 | 342 | return cnt; |
674f7a69 MD |
343 | } |
344 | ||
345 | /* | |
346 | * Should only be called when no more concurrent readers nor writers can | |
347 | * possibly access the table. | |
348 | */ | |
5e28c532 | 349 | int ht_destroy(struct rcu_ht *ht) |
674f7a69 | 350 | { |
5e28c532 MD |
351 | int ret; |
352 | ||
353 | ret = ht_delete_all(ht); | |
395270b6 | 354 | free(ht->t); |
674f7a69 | 355 | free(ht); |
5e28c532 | 356 | return ret; |
674f7a69 MD |
357 | } |
358 | ||
464a1ec9 MD |
359 | static void ht_resize_grow(struct rcu_ht *ht) |
360 | { | |
361 | unsigned long i, new_size, old_size; | |
395270b6 | 362 | struct rcu_table *new_t, *old_t; |
464a1ec9 MD |
363 | struct rcu_ht_node *node, *new_node, *tmp; |
364 | unsigned long hash; | |
365 | ||
395270b6 MD |
366 | old_t = ht->t; |
367 | old_size = old_t->size; | |
464a1ec9 | 368 | |
44395fb7 | 369 | if (old_size == MAX_HT_BUCKETS) |
464a1ec9 MD |
370 | return; |
371 | ||
372 | new_size = old_size << 1; | |
395270b6 MD |
373 | new_t = calloc(1, sizeof(struct rcu_table) |
374 | + (new_size * sizeof(struct rcu_ht_node *))); | |
464a1ec9 MD |
375 | |
376 | for (i = 0; i < old_size; i++) { | |
377 | /* | |
378 | * Re-hash each entry, insert in new table. | |
379 | * It's important that a reader looking for a key _will_ find it | |
380 | * if it's in the table. | |
381 | * Copy each node. (just the node, not ->data) | |
382 | */ | |
395270b6 | 383 | node = old_t->tbl[i]; |
464a1ec9 MD |
384 | while (node) { |
385 | hash = ht->hash_fct(node->key, ht->keylen, ht->hashseed) | |
386 | % new_size; | |
387 | new_node = malloc(sizeof(struct rcu_ht_node)); | |
388 | new_node->key = node->key; | |
389 | new_node->data = node->data; | |
395270b6 MD |
390 | new_node->next = new_t->tbl[hash]; /* add to head */ |
391 | new_t->tbl[hash] = new_node; | |
464a1ec9 MD |
392 | node = node->next; |
393 | } | |
394 | } | |
395 | ||
395270b6 MD |
396 | smp_wmb(); /* write links before changing table */ |
397 | ht->t = new_t; /* Changing table and size atomically wrt lookups */ | |
464a1ec9 MD |
398 | |
399 | /* Ensure all concurrent lookups use new size and table */ | |
400 | synchronize_rcu(); | |
401 | ||
402 | for (i = 0; i < old_size; i++) { | |
395270b6 | 403 | node = old_t->tbl[i]; |
464a1ec9 MD |
404 | while (node) { |
405 | tmp = node->next; | |
406 | free(node); | |
407 | node = tmp; | |
408 | } | |
409 | } | |
395270b6 | 410 | free(old_t); |
464a1ec9 MD |
411 | } |
412 | ||
413 | static void ht_resize_shrink(struct rcu_ht *ht) | |
414 | { | |
415 | unsigned long i, new_size; | |
395270b6 | 416 | struct rcu_table *new_t, *old_t; |
464a1ec9 MD |
417 | struct rcu_ht_node **prev, *node; |
418 | ||
395270b6 MD |
419 | old_t = ht->t; |
420 | if (old_t->size == 1) | |
464a1ec9 MD |
421 | return; |
422 | ||
395270b6 | 423 | new_size = old_t->size >> 1; |
464a1ec9 MD |
424 | |
425 | for (i = 0; i < new_size; i++) { | |
44395fb7 | 426 | /* Link end with first entry of i + new_size */ |
395270b6 | 427 | prev = &old_t->tbl[i]; |
464a1ec9 MD |
428 | node = *prev; |
429 | while (node) { | |
430 | prev = &node->next; | |
431 | node = *prev; | |
432 | } | |
395270b6 | 433 | *prev = old_t->tbl[i + new_size]; |
464a1ec9 MD |
434 | } |
435 | smp_wmb(); /* write links before changing size */ | |
395270b6 | 436 | STORE_SHARED(old_t->size, new_size); |
464a1ec9 MD |
437 | |
438 | /* Ensure all concurrent lookups use new size */ | |
439 | synchronize_rcu(); | |
440 | ||
395270b6 MD |
441 | new_t = realloc(old_t, sizeof(struct rcu_table) |
442 | + (new_size * sizeof(struct rcu_ht_node *))); | |
464a1ec9 | 443 | /* shrinking, pointers should not move */ |
395270b6 | 444 | assert(new_t == old_t); |
464a1ec9 MD |
445 | } |
446 | ||
447 | /* | |
448 | * growth: >0: *2, <0: /2 | |
449 | */ | |
450 | void ht_resize(struct rcu_ht *ht, int growth) | |
451 | { | |
452 | int ret; | |
453 | ||
454 | ret = pthread_mutex_lock(&ht->resize_mutex); | |
455 | assert(!ret); | |
44395fb7 | 456 | STORE_SHARED(ht->resize_ongoing, 1); |
464a1ec9 MD |
457 | synchronize_rcu(); |
458 | /* All add/remove are waiting on the mutex. */ | |
459 | if (growth > 0) | |
460 | ht_resize_grow(ht); | |
461 | else if (growth < 0) | |
462 | ht_resize_shrink(ht); | |
463 | smp_mb(); | |
44395fb7 | 464 | STORE_SHARED(ht->resize_ongoing, 0); |
464a1ec9 MD |
465 | ret = pthread_mutex_unlock(&ht->resize_mutex); |
466 | assert(!ret); | |
467 | } | |
468 | ||
5e28c532 MD |
469 | /* |
470 | * Expects keys <= than pointer size to be encoded in the pointer itself. | |
471 | */ | |
674f7a69 | 472 | uint32_t ht_jhash(void *key, uint32_t length, uint32_t initval) |
ab7d5fc6 | 473 | { |
5e28c532 MD |
474 | uint32_t ret; |
475 | void *vkey; | |
476 | ||
0eb566f4 | 477 | if (length <= sizeof(void *)) |
5e28c532 MD |
478 | vkey = &key; |
479 | else | |
480 | vkey = key; | |
481 | ret = jhash(vkey, length, initval); | |
482 | return ret; | |
ab7d5fc6 | 483 | } |