Comment list behavior wrt lock-freedom
[urcu.git] / rculfhash.c
CommitLineData
5e28c532 1/*
abc490a1
MD
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
5e28c532
MD
21 */
22
2ed95849
MD
23#define _LGPL_SOURCE
24#include <stdlib.h>
e0ba718a
MD
25#include <errno.h>
26#include <assert.h>
27#include <stdio.h>
abc490a1 28#include <stdint.h>
f000907d 29#include <string.h>
e0ba718a 30
2ed95849 31#include <urcu.h>
abc490a1 32#include <urcu-call-rcu.h>
a42cc659
MD
33#include <urcu/arch.h>
34#include <urcu/uatomic.h>
674f7a69 35#include <urcu/jhash.h>
a42cc659 36#include <urcu/compiler.h>
abc490a1 37#include <urcu/rculfhash.h>
5e28c532 38#include <stdio.h>
464a1ec9 39#include <pthread.h>
44395fb7 40
f9830efd
MD
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
3390d470
MD
49#define CHAIN_LEN_TARGET 4
50#define CHAIN_LEN_RESIZE_THRESHOLD 16
2ed95849 51
abc490a1
MD
52#ifndef max
53#define max(a, b) ((a) > (b) ? (a) : (b))
54#endif
2ed95849 55
395270b6 56struct rcu_table {
abc490a1 57 unsigned long size; /* always a power of 2 */
f9830efd 58 unsigned long resize_target;
abc490a1 59 struct rcu_head head;
395270b6
MD
60 struct rcu_ht_node *tbl[0];
61};
62
2ed95849 63struct rcu_ht {
395270b6 64 struct rcu_table *t; /* shared */
2ed95849 65 ht_hash_fct hash_fct;
732ad076
MD
66 ht_compare_fct compare_fct;
67 unsigned long hash_seed;
464a1ec9 68 pthread_mutex_t resize_mutex; /* resize mutex: add/del mutex */
abc490a1
MD
69 void (*ht_call_rcu)(struct rcu_head *head,
70 void (*func)(struct rcu_head *head));
2ed95849
MD
71};
72
abc490a1
MD
73struct rcu_resize_work {
74 struct rcu_head head;
2ed95849 75 struct rcu_ht *ht;
abc490a1 76};
2ed95849 77
abc490a1
MD
78/*
79 * Algorithm to reverse bits in a word by lookup table, extended to
80 * 64-bit words.
f9830efd 81 * Source:
abc490a1 82 * http://graphics.stanford.edu/~seander/bithacks.html#BitReverseTable
f9830efd 83 * Originally from Public Domain.
abc490a1
MD
84 */
85
86static const uint8_t BitReverseTable256[256] =
2ed95849 87{
abc490a1
MD
88#define R2(n) (n), (n) + 2*64, (n) + 1*64, (n) + 3*64
89#define R4(n) R2(n), R2((n) + 2*16), R2((n) + 1*16), R2((n) + 3*16)
90#define R6(n) R4(n), R4((n) + 2*4 ), R4((n) + 1*4 ), R4((n) + 3*4 )
91 R6(0), R6(2), R6(1), R6(3)
92};
93#undef R2
94#undef R4
95#undef R6
2ed95849 96
abc490a1
MD
97static
98uint8_t bit_reverse_u8(uint8_t v)
99{
100 return BitReverseTable256[v];
101}
ab7d5fc6 102
abc490a1
MD
103static __attribute__((unused))
104uint32_t bit_reverse_u32(uint32_t v)
105{
106 return ((uint32_t) bit_reverse_u8(v) << 24) |
107 ((uint32_t) bit_reverse_u8(v >> 8) << 16) |
108 ((uint32_t) bit_reverse_u8(v >> 16) << 8) |
109 ((uint32_t) bit_reverse_u8(v >> 24));
2ed95849
MD
110}
111
abc490a1
MD
112static __attribute__((unused))
113uint64_t bit_reverse_u64(uint64_t v)
2ed95849 114{
abc490a1
MD
115 return ((uint64_t) bit_reverse_u8(v) << 56) |
116 ((uint64_t) bit_reverse_u8(v >> 8) << 48) |
117 ((uint64_t) bit_reverse_u8(v >> 16) << 40) |
118 ((uint64_t) bit_reverse_u8(v >> 24) << 32) |
119 ((uint64_t) bit_reverse_u8(v >> 32) << 24) |
120 ((uint64_t) bit_reverse_u8(v >> 40) << 16) |
121 ((uint64_t) bit_reverse_u8(v >> 48) << 8) |
122 ((uint64_t) bit_reverse_u8(v >> 56));
123}
124
125static
126unsigned long bit_reverse_ulong(unsigned long v)
127{
128#if (CAA_BITS_PER_LONG == 32)
129 return bit_reverse_u32(v);
130#else
131 return bit_reverse_u64(v);
132#endif
133}
134
f9830efd
MD
135/*
136 * Algorithm to find the log2 of a 32-bit unsigned integer.
137 * source: http://graphics.stanford.edu/~seander/bithacks.html#IntegerLogLookup
138 * Originally from Public Domain.
139 */
140static const char LogTable256[256] =
141{
142#define LT(n) n, n, n, n, n, n, n, n, n, n, n, n, n, n, n, n
143 -1, 0, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3,
144 LT(4), LT(5), LT(5), LT(6), LT(6), LT(6), LT(6),
145 LT(7), LT(7), LT(7), LT(7), LT(7), LT(7), LT(7), LT(7)
146};
147
148uint32_t log2_u32(uint32_t v)
149{
150 uint32_t t, tt;
151
152 if ((tt = (v >> 16)))
153 return (t = (tt >> 8))
154 ? 24 + LogTable256[t]
155 : 16 + LogTable256[tt];
156 else
157 return (t = (v >> 8))
158 ? 8 + LogTable256[t]
159 : LogTable256[v];
160}
161
162static
163void ht_resize_lazy(struct rcu_ht *ht, struct rcu_table *t, int growth);
164
165static
166void check_resize(struct rcu_ht *ht, struct rcu_table *t,
167 uint32_t chain_len)
168{
3390d470
MD
169 if (chain_len >= CHAIN_LEN_RESIZE_THRESHOLD)
170 ht_resize_lazy(ht, t,
171 log2_u32(chain_len - CHAIN_LEN_TARGET));
f9830efd
MD
172}
173
abc490a1
MD
174static
175struct rcu_ht_node *clear_flag(struct rcu_ht_node *node)
176{
177 return (struct rcu_ht_node *) (((unsigned long) node) & ~0x1);
178}
179
180static
181int is_removed(struct rcu_ht_node *node)
182{
183 return ((unsigned long) node) & 0x1;
184}
185
186static
187struct rcu_ht_node *flag_removed(struct rcu_ht_node *node)
188{
189 return (struct rcu_ht_node *) (((unsigned long) node) | 0x1);
190}
191
192static
f9830efd 193unsigned long _uatomic_max(unsigned long *ptr, unsigned long v)
abc490a1
MD
194{
195 unsigned long old1, old2;
196
197 old1 = uatomic_read(ptr);
198 do {
199 old2 = old1;
200 if (old2 >= v)
f9830efd 201 return old2;
abc490a1 202 } while ((old1 = uatomic_cmpxchg(ptr, old2, v)) != old2);
f9830efd 203 return v;
abc490a1
MD
204}
205
206static
f000907d 207void _ht_add(struct rcu_ht *ht, struct rcu_table *t, struct rcu_ht_node *node)
abc490a1
MD
208{
209 struct rcu_ht_node *iter_prev = NULL, *iter = NULL;
210
f000907d
MD
211 if (!t->size)
212 return;
abc490a1 213 for (;;) {
f9830efd 214 uint32_t chain_len = 0;
abc490a1
MD
215
216 iter_prev = rcu_dereference(t->tbl[node->hash & (t->size - 1)]);
217 assert(iter_prev);
218 assert(iter_prev->reverse_hash <= node->reverse_hash);
219 for (;;) {
220 iter = clear_flag(rcu_dereference(iter_prev->next));
221 if (unlikely(!iter))
222 break;
dd4505e0 223 if (iter->reverse_hash > node->reverse_hash)
abc490a1
MD
224 break;
225 iter_prev = iter;
f000907d 226 check_resize(ht, t, ++chain_len);
abc490a1 227 }
98f969fc
MD
228 /*
229 * add in iter_prev->next: TODO: check for helping
230 * delete, for lock-freedom...
231 */
abc490a1
MD
232 if (is_removed(iter))
233 continue;
f000907d 234 assert(node != iter);
abc490a1 235 node->next = iter;
f000907d 236 assert(iter_prev != node);
abc490a1
MD
237 if (uatomic_cmpxchg(&iter_prev->next, iter, node) != iter)
238 continue;
f000907d 239 break;
464a1ec9 240 }
abc490a1 241}
464a1ec9 242
abc490a1
MD
243static
244int _ht_remove(struct rcu_ht *ht, struct rcu_table *t, struct rcu_ht_node *node)
245{
246 struct rcu_ht_node *iter_prev, *iter, *next, *old;
247 unsigned long chain_len;
248 int found, ret = 0;
249 int flagged = 0;
5e28c532 250
abc490a1
MD
251retry:
252 chain_len = 0;
253 found = 0;
254 iter_prev = rcu_dereference(t->tbl[node->hash & (t->size - 1)]);
255 assert(iter_prev);
256 assert(iter_prev->reverse_hash <= node->reverse_hash);
2ed95849 257 for (;;) {
abc490a1
MD
258 iter = clear_flag(rcu_dereference(iter_prev->next));
259 if (unlikely(!iter))
260 break;
dd4505e0 261 if (unlikely(iter->reverse_hash > node->reverse_hash))
abc490a1
MD
262 break;
263 if (iter == node) {
264 found = 1;
2ed95849
MD
265 break;
266 }
abc490a1
MD
267 iter_prev = iter;
268 }
269 if (!found) {
270 ret = -ENOENT;
271 goto end;
272 }
273 next = rcu_dereference(iter->next);
274 if (!flagged) {
275 if (is_removed(next)) {
276 ret = -ENOENT;
2ed95849
MD
277 goto end;
278 }
abc490a1 279 /* set deletion flag */
f000907d
MD
280 if ((old = uatomic_cmpxchg(&iter->next, next,
281 flag_removed(next))) != next) {
abc490a1
MD
282 if (old == flag_removed(next)) {
283 ret = -ENOENT;
284 goto end;
285 } else {
286 goto retry;
287 }
288 }
289 flagged = 1;
2ed95849 290 }
abc490a1 291 /*
98f969fc
MD
292 * Remove the element from the list.
293 * Retry if there has been a concurrent add before us.
294 * Retry if the prev node has been deleted.
295 * There cannot be a concurrent delete for our position, because
296 * we won the deletion flag cmpxchg.
297 * If there is a concurrent add after us, our deletion flag
298 * makes it busy-loop (FIXME: not lock-free).
abc490a1
MD
299 */
300 if (uatomic_cmpxchg(&iter_prev->next, iter, clear_flag(next)) != iter)
301 goto retry;
2ed95849 302end:
2ed95849 303 return ret;
abc490a1 304}
2ed95849 305
abc490a1
MD
306static
307void init_table(struct rcu_ht *ht, struct rcu_table *t,
308 unsigned long first, unsigned long len)
309{
310 unsigned long i, end;
311
312 end = first + len;
313 for (i = first; i < end; i++) {
314 /* Update table size when power of two */
315 if (i != 0 && !(i & (i - 1)))
316 t->size = i;
317 t->tbl[i] = calloc(1, sizeof(struct rcu_ht_node));
318 t->tbl[i]->dummy = 1;
319 t->tbl[i]->hash = i;
320 t->tbl[i]->reverse_hash = bit_reverse_ulong(i);
321 _ht_add(ht, t, t->tbl[i]);
322 }
f9830efd 323 t->resize_target = t->size = end;
2ed95849
MD
324}
325
abc490a1 326struct rcu_ht *ht_new(ht_hash_fct hash_fct,
732ad076
MD
327 ht_compare_fct compare_fct,
328 unsigned long hash_seed,
abc490a1
MD
329 unsigned long init_size,
330 void (*ht_call_rcu)(struct rcu_head *head,
331 void (*func)(struct rcu_head *head)))
332{
333 struct rcu_ht *ht;
334
335 ht = calloc(1, sizeof(struct rcu_ht));
336 ht->hash_fct = hash_fct;
732ad076
MD
337 ht->compare_fct = compare_fct;
338 ht->hash_seed = hash_seed;
f000907d 339 ht->ht_call_rcu = ht_call_rcu;
abc490a1
MD
340 /* this mutex should not nest in read-side C.S. */
341 pthread_mutex_init(&ht->resize_mutex, NULL);
342 ht->t = calloc(1, sizeof(struct rcu_table)
343 + (max(init_size, 1) * sizeof(struct rcu_ht_node *)));
344 ht->t->size = 0;
f000907d 345 pthread_mutex_lock(&ht->resize_mutex);
abc490a1 346 init_table(ht, ht->t, 0, max(init_size, 1));
f000907d 347 pthread_mutex_unlock(&ht->resize_mutex);
abc490a1
MD
348 return ht;
349}
350
732ad076 351struct rcu_ht_node *ht_lookup(struct rcu_ht *ht, void *key, size_t key_len)
2ed95849 352{
395270b6 353 struct rcu_table *t;
abc490a1
MD
354 struct rcu_ht_node *node;
355 unsigned long hash, reverse_hash;
2ed95849 356
732ad076 357 hash = ht->hash_fct(key, key_len, ht->hash_seed);
abc490a1 358 reverse_hash = bit_reverse_ulong(hash);
464a1ec9 359
395270b6 360 t = rcu_dereference(ht->t);
abc490a1 361 node = rcu_dereference(t->tbl[hash & (t->size - 1)]);
2ed95849 362 for (;;) {
abc490a1
MD
363 if (unlikely(!node))
364 break;
dd4505e0 365 if (unlikely(node->reverse_hash > reverse_hash)) {
abc490a1
MD
366 node = NULL;
367 break;
2ed95849 368 }
732ad076 369 if (!ht->compare_fct(node->key, node->key_len, key, key_len)) {
dd4505e0 370 if (unlikely(is_removed(rcu_dereference(node->next))))
abc490a1 371 node = NULL;
2ed95849
MD
372 break;
373 }
abc490a1 374 node = clear_flag(rcu_dereference(node->next));
2ed95849 375 }
abc490a1
MD
376 return node;
377}
e0ba718a 378
f000907d 379void ht_add(struct rcu_ht *ht, struct rcu_ht_node *node)
abc490a1
MD
380{
381 struct rcu_table *t;
ab7d5fc6 382
732ad076 383 node->hash = ht->hash_fct(node->key, node->key_len, ht->hash_seed);
abc490a1 384 node->reverse_hash = bit_reverse_ulong((unsigned long) node->hash);
2ed95849 385
abc490a1 386 t = rcu_dereference(ht->t);
f000907d 387 _ht_add(ht, t, node);
2ed95849
MD
388}
389
abc490a1 390int ht_remove(struct rcu_ht *ht, struct rcu_ht_node *node)
2ed95849 391{
abc490a1
MD
392 struct rcu_table *t;
393
394 t = rcu_dereference(ht->t);
abc490a1 395 return _ht_remove(ht, t, node);
2ed95849 396}
ab7d5fc6 397
abc490a1
MD
398static
399int ht_delete_dummy(struct rcu_ht *ht)
674f7a69 400{
395270b6 401 struct rcu_table *t;
abc490a1
MD
402 struct rcu_ht_node *node;
403 unsigned long i;
674f7a69 404
abc490a1
MD
405 t = ht->t;
406 /* Check that the table is empty */
407 node = t->tbl[0];
408 do {
409 if (!node->dummy)
410 return -EPERM;
411 node = node->next;
412 } while (node);
413 /* Internal sanity check: all nodes left should be dummy */
395270b6 414 for (i = 0; i < t->size; i++) {
abc490a1
MD
415 assert(t->tbl[i]->dummy);
416 free(t->tbl[i]);
674f7a69 417 }
abc490a1 418 return 0;
674f7a69
MD
419}
420
421/*
422 * Should only be called when no more concurrent readers nor writers can
423 * possibly access the table.
424 */
5e28c532 425int ht_destroy(struct rcu_ht *ht)
674f7a69 426{
5e28c532
MD
427 int ret;
428
abc490a1
MD
429 ret = ht_delete_dummy(ht);
430 if (ret)
431 return ret;
395270b6 432 free(ht->t);
674f7a69 433 free(ht);
5e28c532 434 return ret;
674f7a69
MD
435}
436
abc490a1
MD
437static
438void ht_free_table_cb(struct rcu_head *head)
439{
440 struct rcu_table *t =
441 caa_container_of(head, struct rcu_table, head);
442 free(t);
443}
444
445/* called with resize mutex held */
446static
447void _do_ht_resize(struct rcu_ht *ht)
464a1ec9 448{
abc490a1 449 unsigned long new_size, old_size;
395270b6 450 struct rcu_table *new_t, *old_t;
464a1ec9 451
395270b6
MD
452 old_t = ht->t;
453 old_size = old_t->size;
464a1ec9 454
f9830efd
MD
455 new_size = CMM_LOAD_SHARED(old_t->resize_target);
456 dbg_printf("rculfhash: resize from %lu to %lu buckets\n",
457 old_size, new_size);
abc490a1 458 if (old_size == new_size)
464a1ec9 459 return;
f000907d 460 new_t = malloc(sizeof(struct rcu_table)
abc490a1 461 + (new_size * sizeof(struct rcu_ht_node *)));
f000907d
MD
462 assert(new_size > old_size);
463 memcpy(&new_t->tbl, &old_t->tbl,
464 old_size * sizeof(struct rcu_ht_node *));
465 init_table(ht, new_t, old_size, new_size - old_size);
f000907d
MD
466 /* Changing table and size atomically wrt lookups */
467 rcu_assign_pointer(ht->t, new_t);
468 ht->ht_call_rcu(&old_t->head, ht_free_table_cb);
464a1ec9
MD
469}
470
abc490a1 471static
f9830efd
MD
472unsigned long resize_target_update(struct rcu_table *t,
473 int growth_order)
464a1ec9 474{
f9830efd
MD
475 return _uatomic_max(&t->resize_target,
476 t->size << growth_order);
464a1ec9
MD
477}
478
464a1ec9
MD
479void ht_resize(struct rcu_ht *ht, int growth)
480{
f9830efd
MD
481 struct rcu_table *t = rcu_dereference(ht->t);
482 unsigned long target_size;
483
484 target_size = resize_target_update(t, growth);
485 if (t->size < target_size) {
486 pthread_mutex_lock(&ht->resize_mutex);
487 _do_ht_resize(ht);
488 pthread_mutex_unlock(&ht->resize_mutex);
489 }
abc490a1 490}
464a1ec9 491
abc490a1
MD
492static
493void do_resize_cb(struct rcu_head *head)
494{
495 struct rcu_resize_work *work =
496 caa_container_of(head, struct rcu_resize_work, head);
497 struct rcu_ht *ht = work->ht;
498
499 pthread_mutex_lock(&ht->resize_mutex);
500 _do_ht_resize(ht);
501 pthread_mutex_unlock(&ht->resize_mutex);
502 free(work);
464a1ec9
MD
503}
504
abc490a1 505static
f000907d 506void ht_resize_lazy(struct rcu_ht *ht, struct rcu_table *t, int growth)
ab7d5fc6 507{
abc490a1 508 struct rcu_resize_work *work;
f9830efd 509 unsigned long target_size;
abc490a1 510
f9830efd
MD
511 target_size = resize_target_update(t, growth);
512 if (t->size < target_size) {
513 work = malloc(sizeof(*work));
514 work->ht = ht;
515 ht->ht_call_rcu(&work->head, do_resize_cb);
516 }
ab7d5fc6 517}
This page took 0.07318 seconds and 4 git commands to generate.