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