rculfhash: add unique
[urcu.git] / rculfhash.c
1 /*
2 * rculfhash.c
3 *
4 * Userspace RCU library - Lock-Free Expandable RCU Hash Table
5 *
6 * Copyright 2010-2011 - Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
7 *
8 * This library is free software; you can redistribute it and/or
9 * modify it under the terms of the GNU Lesser General Public
10 * License as published by the Free Software Foundation; either
11 * version 2.1 of the License, or (at your option) any later version.
12 *
13 * This library is distributed in the hope that it will be useful,
14 * but WITHOUT ANY WARRANTY; without even the implied warranty of
15 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
16 * Lesser General Public License for more details.
17 *
18 * You should have received a copy of the GNU Lesser General Public
19 * License along with this library; if not, write to the Free Software
20 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
21 */
22
23 #define _LGPL_SOURCE
24 #include <stdlib.h>
25 #include <errno.h>
26 #include <assert.h>
27 #include <stdio.h>
28 #include <stdint.h>
29 #include <string.h>
30
31 #include <urcu.h>
32 #include <urcu-call-rcu.h>
33 #include <urcu/arch.h>
34 #include <urcu/uatomic.h>
35 #include <urcu/jhash.h>
36 #include <urcu/compiler.h>
37 #include <urcu/rculfhash.h>
38 #include <stdio.h>
39 #include <pthread.h>
40
41 #define DEBUG /* Test */
42
43 #ifdef DEBUG
44 #define dbg_printf(args...) printf(args)
45 #else
46 #define dbg_printf(args...)
47 #endif
48
49 #define CHAIN_LEN_TARGET 1
50 #define CHAIN_LEN_RESIZE_THRESHOLD 2
51
52 #ifndef max
53 #define max(a, b) ((a) > (b) ? (a) : (b))
54 #endif
55
56 struct rcu_table {
57 unsigned long size; /* always a power of 2 */
58 unsigned long resize_target;
59 int resize_initiated;
60 struct rcu_head head;
61 struct rcu_ht_node *tbl[0];
62 };
63
64 struct rcu_ht {
65 struct rcu_table *t; /* shared */
66 ht_hash_fct hash_fct;
67 ht_compare_fct compare_fct;
68 unsigned long hash_seed;
69 pthread_mutex_t resize_mutex; /* resize mutex: add/del mutex */
70 void (*ht_call_rcu)(struct rcu_head *head,
71 void (*func)(struct rcu_head *head));
72 };
73
74 struct rcu_resize_work {
75 struct rcu_head head;
76 struct rcu_ht *ht;
77 };
78
79 /*
80 * Algorithm to reverse bits in a word by lookup table, extended to
81 * 64-bit words.
82 * Source:
83 * http://graphics.stanford.edu/~seander/bithacks.html#BitReverseTable
84 * Originally from Public Domain.
85 */
86
87 static const uint8_t BitReverseTable256[256] =
88 {
89 #define R2(n) (n), (n) + 2*64, (n) + 1*64, (n) + 3*64
90 #define R4(n) R2(n), R2((n) + 2*16), R2((n) + 1*16), R2((n) + 3*16)
91 #define R6(n) R4(n), R4((n) + 2*4 ), R4((n) + 1*4 ), R4((n) + 3*4 )
92 R6(0), R6(2), R6(1), R6(3)
93 };
94 #undef R2
95 #undef R4
96 #undef R6
97
98 static
99 uint8_t bit_reverse_u8(uint8_t v)
100 {
101 return BitReverseTable256[v];
102 }
103
104 static __attribute__((unused))
105 uint32_t bit_reverse_u32(uint32_t v)
106 {
107 return ((uint32_t) bit_reverse_u8(v) << 24) |
108 ((uint32_t) bit_reverse_u8(v >> 8) << 16) |
109 ((uint32_t) bit_reverse_u8(v >> 16) << 8) |
110 ((uint32_t) bit_reverse_u8(v >> 24));
111 }
112
113 static __attribute__((unused))
114 uint64_t bit_reverse_u64(uint64_t v)
115 {
116 return ((uint64_t) bit_reverse_u8(v) << 56) |
117 ((uint64_t) bit_reverse_u8(v >> 8) << 48) |
118 ((uint64_t) bit_reverse_u8(v >> 16) << 40) |
119 ((uint64_t) bit_reverse_u8(v >> 24) << 32) |
120 ((uint64_t) bit_reverse_u8(v >> 32) << 24) |
121 ((uint64_t) bit_reverse_u8(v >> 40) << 16) |
122 ((uint64_t) bit_reverse_u8(v >> 48) << 8) |
123 ((uint64_t) bit_reverse_u8(v >> 56));
124 }
125
126 static
127 unsigned long bit_reverse_ulong(unsigned long v)
128 {
129 #if (CAA_BITS_PER_LONG == 32)
130 return bit_reverse_u32(v);
131 #else
132 return bit_reverse_u64(v);
133 #endif
134 }
135
136 /*
137 * Algorithm to find the log2 of a 32-bit unsigned integer.
138 * source: http://graphics.stanford.edu/~seander/bithacks.html#IntegerLogLookup
139 * Originally from Public Domain.
140 */
141 static const char LogTable256[256] =
142 {
143 #define LT(n) n, n, n, n, n, n, n, n, n, n, n, n, n, n, n, n
144 -1, 0, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3,
145 LT(4), LT(5), LT(5), LT(6), LT(6), LT(6), LT(6),
146 LT(7), LT(7), LT(7), LT(7), LT(7), LT(7), LT(7), LT(7)
147 };
148
149 uint32_t log2_u32(uint32_t v)
150 {
151 uint32_t t, tt;
152
153 if ((tt = (v >> 16)))
154 return (t = (tt >> 8))
155 ? 24 + LogTable256[t]
156 : 16 + LogTable256[tt];
157 else
158 return (t = (v >> 8))
159 ? 8 + LogTable256[t]
160 : LogTable256[v];
161 }
162
163 static
164 void ht_resize_lazy(struct rcu_ht *ht, struct rcu_table *t, int growth);
165
166 static
167 void check_resize(struct rcu_ht *ht, struct rcu_table *t,
168 uint32_t chain_len)
169 {
170 if (chain_len >= CHAIN_LEN_RESIZE_THRESHOLD)
171 ht_resize_lazy(ht, t,
172 log2_u32(chain_len - CHAIN_LEN_TARGET - 1));
173 }
174
175 static
176 struct rcu_ht_node *clear_flag(struct rcu_ht_node *node)
177 {
178 return (struct rcu_ht_node *) (((unsigned long) node) & ~0x1);
179 }
180
181 static
182 int is_removed(struct rcu_ht_node *node)
183 {
184 return ((unsigned long) node) & 0x1;
185 }
186
187 static
188 struct rcu_ht_node *flag_removed(struct rcu_ht_node *node)
189 {
190 return (struct rcu_ht_node *) (((unsigned long) node) | 0x1);
191 }
192
193 static
194 unsigned long _uatomic_max(unsigned long *ptr, unsigned long v)
195 {
196 unsigned long old1, old2;
197
198 old1 = uatomic_read(ptr);
199 do {
200 old2 = old1;
201 if (old2 >= v)
202 return old2;
203 } while ((old1 = uatomic_cmpxchg(ptr, old2, v)) != old2);
204 return v;
205 }
206
207 static
208 int _ht_add(struct rcu_ht *ht, struct rcu_table *t, struct rcu_ht_node *node,
209 int unique)
210 {
211 struct rcu_ht_node *iter_prev, *iter, *iter_prev_next, *next;
212
213 if (!t->size)
214 return 0;
215 for (;;) {
216 uint32_t chain_len = 0;
217
218 /*
219 * iter_prev points to the non-removed node prior to the
220 * insert location.
221 * iter iterates until it finds the next non-removed
222 * node.
223 */
224 iter_prev = rcu_dereference(t->tbl[node->hash & (t->size - 1)]);
225 /* We can always skip the dummy node initially */
226 iter_prev_next = next = rcu_dereference(iter_prev->next);
227 assert(iter_prev);
228 assert(iter_prev->reverse_hash <= node->reverse_hash);
229 for (;;) {
230 iter = next;
231 if (unlikely(!clear_flag(iter)))
232 break;
233 next = rcu_dereference(clear_flag(iter)->next);
234 if (unlikely(is_removed(next)))
235 continue;
236 if (unique
237 && !clear_flag(iter)->dummy
238 && !ht->compare_fct(node->key, node->key_len,
239 clear_flag(iter)->key,
240 clear_flag(iter)->key_len))
241 return -EEXIST;
242 if (clear_flag(iter)->reverse_hash > node->reverse_hash)
243 break;
244 /* Only account for identical reverse hash once */
245 if (iter_prev->reverse_hash != clear_flag(iter)->reverse_hash)
246 check_resize(ht, t, ++chain_len);
247 iter_prev = clear_flag(iter);
248 iter_prev_next = next;
249 }
250 assert(node != iter);
251 assert(!is_removed(iter_prev));
252 assert(iter_prev != node);
253 node->next = iter;
254 if (uatomic_cmpxchg(&iter_prev->next, iter_prev_next,
255 node) != iter_prev_next)
256 continue;
257 else
258 break;
259 }
260 return 0;
261 }
262
263 static
264 int _ht_remove(struct rcu_ht *ht, struct rcu_table *t, struct rcu_ht_node *node)
265 {
266 struct rcu_ht_node *iter_prev, *iter, *iter_prev_next, *next, *old;
267 unsigned long chain_len;
268 int found;
269 int flagged = 0;
270
271 retry:
272 chain_len = 0;
273 found = 0;
274 /*
275 * iter_prev points to the non-removed node prior to the remove
276 * location.
277 * node is the node to remove.
278 */
279 iter_prev = rcu_dereference(t->tbl[node->hash & (t->size - 1)]);
280 /* We can always skip the dummy node initially */
281 iter_prev_next = next = rcu_dereference(iter_prev->next);
282 assert(iter_prev);
283 assert(iter_prev->reverse_hash <= node->reverse_hash);
284 for (;;) {
285 iter = next;
286 if (unlikely(!clear_flag(iter)))
287 break;
288 next = rcu_dereference(clear_flag(iter)->next);
289 if (iter == node) {
290 found = 1;
291 break;
292 }
293 if (unlikely(is_removed(next)))
294 continue;
295 if (clear_flag(iter)->reverse_hash > node->reverse_hash)
296 break;
297 iter_prev = clear_flag(iter);
298 iter_prev_next = next;
299 }
300 if (!found)
301 goto end;
302 if (!flagged) {
303 if (is_removed(next))
304 goto end;
305 /* set deletion flag */
306 if ((old = uatomic_cmpxchg(&iter->next, next,
307 flag_removed(next))) != next) {
308 if (old == flag_removed(next))
309 goto end;
310 else
311 goto retry;
312 }
313 flagged = 1;
314 }
315 /*
316 * Remove the element from the list.
317 * - Retry if there has been a concurrent add before us.
318 * - Retry if the prev node has been deleted (its next removed
319 * flag would be set).
320 * - There cannot be a concurrent delete for our position, because
321 * we won the deletion flag cmpxchg.
322 * - If there is a concurrent add or remove after us while our
323 * removed flag is set, it will skip us and link directly after
324 * the prior non-removed node before us. In this case, the
325 * retry will not find the node in the list anymore.
326 */
327 if (uatomic_cmpxchg(&iter_prev->next, iter_prev_next,
328 clear_flag(next)) != iter_prev_next)
329 goto retry;
330 end:
331 /*
332 * Only the flagging action indicated that we (and no other)
333 * removed the node from the hash.
334 */
335 if (flagged)
336 return 0;
337 else
338 return -ENOENT;
339 }
340
341 static
342 void init_table(struct rcu_ht *ht, struct rcu_table *t,
343 unsigned long first, unsigned long len)
344 {
345 unsigned long i, end;
346
347 end = first + len;
348 for (i = first; i < end; i++) {
349 /* Update table size when power of two */
350 if (i != 0 && !(i & (i - 1)))
351 t->size = i;
352 t->tbl[i] = calloc(1, sizeof(struct rcu_ht_node));
353 t->tbl[i]->dummy = 1;
354 t->tbl[i]->hash = i;
355 t->tbl[i]->reverse_hash = bit_reverse_ulong(i);
356 (void) _ht_add(ht, t, t->tbl[i], 0);
357 }
358 t->resize_target = t->size = end;
359 t->resize_initiated = 0;
360 }
361
362 struct rcu_ht *ht_new(ht_hash_fct hash_fct,
363 ht_compare_fct compare_fct,
364 unsigned long hash_seed,
365 unsigned long init_size,
366 void (*ht_call_rcu)(struct rcu_head *head,
367 void (*func)(struct rcu_head *head)))
368 {
369 struct rcu_ht *ht;
370
371 ht = calloc(1, sizeof(struct rcu_ht));
372 ht->hash_fct = hash_fct;
373 ht->compare_fct = compare_fct;
374 ht->hash_seed = hash_seed;
375 ht->ht_call_rcu = ht_call_rcu;
376 /* this mutex should not nest in read-side C.S. */
377 pthread_mutex_init(&ht->resize_mutex, NULL);
378 ht->t = calloc(1, sizeof(struct rcu_table)
379 + (max(init_size, 1) * sizeof(struct rcu_ht_node *)));
380 ht->t->size = 0;
381 pthread_mutex_lock(&ht->resize_mutex);
382 init_table(ht, ht->t, 0, max(init_size, 1));
383 pthread_mutex_unlock(&ht->resize_mutex);
384 return ht;
385 }
386
387 struct rcu_ht_node *ht_lookup(struct rcu_ht *ht, void *key, size_t key_len)
388 {
389 struct rcu_table *t;
390 struct rcu_ht_node *node;
391 unsigned long hash, reverse_hash;
392
393 hash = ht->hash_fct(key, key_len, ht->hash_seed);
394 reverse_hash = bit_reverse_ulong(hash);
395
396 t = rcu_dereference(ht->t);
397 node = rcu_dereference(t->tbl[hash & (t->size - 1)]);
398 for (;;) {
399 if (unlikely(!node))
400 break;
401 if (unlikely(node->reverse_hash > reverse_hash)) {
402 node = NULL;
403 break;
404 }
405 if (!ht->compare_fct(node->key, node->key_len, key, key_len)) {
406 if (unlikely(is_removed(rcu_dereference(node->next))))
407 node = NULL;
408 break;
409 }
410 node = clear_flag(rcu_dereference(node->next));
411 }
412 return node;
413 }
414
415 void ht_add(struct rcu_ht *ht, struct rcu_ht_node *node)
416 {
417 struct rcu_table *t;
418
419 node->hash = ht->hash_fct(node->key, node->key_len, ht->hash_seed);
420 node->reverse_hash = bit_reverse_ulong((unsigned long) node->hash);
421
422 t = rcu_dereference(ht->t);
423 (void) _ht_add(ht, t, node, 0);
424 }
425
426 int ht_add_unique(struct rcu_ht *ht, struct rcu_ht_node *node)
427 {
428 struct rcu_table *t;
429
430 node->hash = ht->hash_fct(node->key, node->key_len, ht->hash_seed);
431 node->reverse_hash = bit_reverse_ulong((unsigned long) node->hash);
432
433 t = rcu_dereference(ht->t);
434 return _ht_add(ht, t, node, 1);
435 }
436
437 int ht_remove(struct rcu_ht *ht, struct rcu_ht_node *node)
438 {
439 struct rcu_table *t;
440
441 t = rcu_dereference(ht->t);
442 return _ht_remove(ht, t, node);
443 }
444
445 static
446 int ht_delete_dummy(struct rcu_ht *ht)
447 {
448 struct rcu_table *t;
449 struct rcu_ht_node *node;
450 unsigned long i;
451
452 t = ht->t;
453 /* Check that the table is empty */
454 node = t->tbl[0];
455 do {
456 if (!node->dummy)
457 return -EPERM;
458 node = node->next;
459 } while (node);
460 /* Internal sanity check: all nodes left should be dummy */
461 for (i = 0; i < t->size; i++) {
462 assert(t->tbl[i]->dummy);
463 free(t->tbl[i]);
464 }
465 return 0;
466 }
467
468 /*
469 * Should only be called when no more concurrent readers nor writers can
470 * possibly access the table.
471 */
472 int ht_destroy(struct rcu_ht *ht)
473 {
474 int ret;
475
476 ret = ht_delete_dummy(ht);
477 if (ret)
478 return ret;
479 free(ht->t);
480 free(ht);
481 return ret;
482 }
483
484 static
485 void ht_free_table_cb(struct rcu_head *head)
486 {
487 struct rcu_table *t =
488 caa_container_of(head, struct rcu_table, head);
489 free(t);
490 }
491
492 /* called with resize mutex held */
493 static
494 void _do_ht_resize(struct rcu_ht *ht)
495 {
496 unsigned long new_size, old_size;
497 struct rcu_table *new_t, *old_t;
498
499 old_t = ht->t;
500 old_size = old_t->size;
501
502 new_size = CMM_LOAD_SHARED(old_t->resize_target);
503 dbg_printf("rculfhash: resize from %lu to %lu buckets\n",
504 old_size, new_size);
505 if (old_size == new_size)
506 return;
507 new_t = malloc(sizeof(struct rcu_table)
508 + (new_size * sizeof(struct rcu_ht_node *)));
509 assert(new_size > old_size);
510 memcpy(&new_t->tbl, &old_t->tbl,
511 old_size * sizeof(struct rcu_ht_node *));
512 init_table(ht, new_t, old_size, new_size - old_size);
513 /* Changing table and size atomically wrt lookups */
514 rcu_assign_pointer(ht->t, new_t);
515 ht->ht_call_rcu(&old_t->head, ht_free_table_cb);
516 }
517
518 static
519 unsigned long resize_target_update(struct rcu_table *t,
520 int growth_order)
521 {
522 return _uatomic_max(&t->resize_target,
523 t->size << growth_order);
524 }
525
526 void ht_resize(struct rcu_ht *ht, int growth)
527 {
528 struct rcu_table *t = rcu_dereference(ht->t);
529 unsigned long target_size;
530
531 target_size = resize_target_update(t, growth);
532 if (t->size < target_size) {
533 CMM_STORE_SHARED(t->resize_initiated, 1);
534 pthread_mutex_lock(&ht->resize_mutex);
535 _do_ht_resize(ht);
536 pthread_mutex_unlock(&ht->resize_mutex);
537 }
538 }
539
540 static
541 void do_resize_cb(struct rcu_head *head)
542 {
543 struct rcu_resize_work *work =
544 caa_container_of(head, struct rcu_resize_work, head);
545 struct rcu_ht *ht = work->ht;
546
547 pthread_mutex_lock(&ht->resize_mutex);
548 _do_ht_resize(ht);
549 pthread_mutex_unlock(&ht->resize_mutex);
550 free(work);
551 }
552
553 static
554 void ht_resize_lazy(struct rcu_ht *ht, struct rcu_table *t, int growth)
555 {
556 struct rcu_resize_work *work;
557 unsigned long target_size;
558
559 target_size = resize_target_update(t, growth);
560 if (!CMM_LOAD_SHARED(t->resize_initiated) && t->size < target_size) {
561 work = malloc(sizeof(*work));
562 work->ht = ht;
563 ht->ht_call_rcu(&work->head, do_resize_cb);
564 CMM_STORE_SHARED(t->resize_initiated, 1);
565 }
566 }
This page took 0.061528 seconds and 4 git commands to generate.