split-ordered hash table
[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>
e0ba718a 29
2ed95849 30#include <urcu.h>
abc490a1 31#include <urcu-call-rcu.h>
a42cc659
MD
32#include <urcu/arch.h>
33#include <urcu/uatomic.h>
674f7a69 34#include <urcu/jhash.h>
a42cc659 35#include <urcu/compiler.h>
abc490a1 36#include <urcu/rculfhash.h>
5e28c532 37#include <stdio.h>
464a1ec9 38#include <pthread.h>
44395fb7 39
abc490a1 40#define BUCKET_SIZE_RESIZE_THRESHOLD 5
2ed95849 41
abc490a1
MD
42#ifndef max
43#define max(a, b) ((a) > (b) ? (a) : (b))
44#endif
2ed95849 45
395270b6 46struct rcu_table {
abc490a1
MD
47 unsigned long size; /* always a power of 2 */
48 struct rcu_head head;
395270b6
MD
49 struct rcu_ht_node *tbl[0];
50};
51
2ed95849 52struct rcu_ht {
395270b6 53 struct rcu_table *t; /* shared */
2ed95849 54 ht_hash_fct hash_fct;
abc490a1 55 void *hashseed;
464a1ec9 56 pthread_mutex_t resize_mutex; /* resize mutex: add/del mutex */
abc490a1
MD
57 unsigned long target_size;
58 void (*ht_call_rcu)(struct rcu_head *head,
59 void (*func)(struct rcu_head *head));
2ed95849
MD
60};
61
abc490a1
MD
62struct rcu_resize_work {
63 struct rcu_head head;
2ed95849 64 struct rcu_ht *ht;
abc490a1 65};
2ed95849 66
abc490a1
MD
67static
68void ht_resize_lazy(struct rcu_ht *ht, int growth);
69
70static
71void check_resize(struct rcu_ht *ht, unsigned long chain_len)
72{
73 if (chain_len >= BUCKET_SIZE_RESIZE_THRESHOLD)
74 ht_resize_lazy(ht, chain_len / BUCKET_SIZE_RESIZE_THRESHOLD);
2ed95849
MD
75}
76
abc490a1
MD
77/*
78 * Algorithm to reverse bits in a word by lookup table, extended to
79 * 64-bit words.
80 * ref.
81 * http://graphics.stanford.edu/~seander/bithacks.html#BitReverseTable
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
133static
134struct rcu_ht_node *clear_flag(struct rcu_ht_node *node)
135{
136 return (struct rcu_ht_node *) (((unsigned long) node) & ~0x1);
137}
138
139static
140int is_removed(struct rcu_ht_node *node)
141{
142 return ((unsigned long) node) & 0x1;
143}
144
145static
146struct rcu_ht_node *flag_removed(struct rcu_ht_node *node)
147{
148 return (struct rcu_ht_node *) (((unsigned long) node) | 0x1);
149}
150
151static
152void _uatomic_max(unsigned long *ptr, unsigned long v)
153{
154 unsigned long old1, old2;
155
156 old1 = uatomic_read(ptr);
157 do {
158 old2 = old1;
159 if (old2 >= v)
160 break;
161 } while ((old1 = uatomic_cmpxchg(ptr, old2, v)) != old2);
162}
163
164static
165int _ht_add(struct rcu_ht *ht, struct rcu_table *t, struct rcu_ht_node *node)
166{
167 struct rcu_ht_node *iter_prev = NULL, *iter = NULL;
168
169 for (;;) {
170 unsigned long chain_len = 0;
171
172 iter_prev = rcu_dereference(t->tbl[node->hash & (t->size - 1)]);
173 assert(iter_prev);
174 assert(iter_prev->reverse_hash <= node->reverse_hash);
175 for (;;) {
176 iter = clear_flag(rcu_dereference(iter_prev->next));
177 if (unlikely(!iter))
178 break;
179 if (iter->reverse_hash < node->reverse_hash)
180 break;
181 iter_prev = iter;
182 check_resize(ht, ++chain_len);
183 }
184 /* add in iter_prev->next */
185 if (is_removed(iter))
186 continue;
187 node->next = iter;
188 if (uatomic_cmpxchg(&iter_prev->next, iter, node) != iter)
189 continue;
464a1ec9 190 }
abc490a1 191}
464a1ec9 192
abc490a1
MD
193static
194int _ht_remove(struct rcu_ht *ht, struct rcu_table *t, struct rcu_ht_node *node)
195{
196 struct rcu_ht_node *iter_prev, *iter, *next, *old;
197 unsigned long chain_len;
198 int found, ret = 0;
199 int flagged = 0;
5e28c532 200
abc490a1
MD
201retry:
202 chain_len = 0;
203 found = 0;
204 iter_prev = rcu_dereference(t->tbl[node->hash & (t->size - 1)]);
205 assert(iter_prev);
206 assert(iter_prev->reverse_hash <= node->reverse_hash);
2ed95849 207 for (;;) {
abc490a1
MD
208 iter = clear_flag(rcu_dereference(iter_prev->next));
209 if (unlikely(!iter))
210 break;
211 if (iter->reverse_hash < node->reverse_hash)
212 break;
213 if (iter == node) {
214 found = 1;
2ed95849
MD
215 break;
216 }
abc490a1
MD
217 iter_prev = iter;
218 }
219 if (!found) {
220 ret = -ENOENT;
221 goto end;
222 }
223 next = rcu_dereference(iter->next);
224 if (!flagged) {
225 if (is_removed(next)) {
226 ret = -ENOENT;
2ed95849
MD
227 goto end;
228 }
abc490a1
MD
229 /* set deletion flag */
230 if ((old = uatomic_cmpxchg(&iter->next, next, flag_removed(next))) != next) {
231 if (old == flag_removed(next)) {
232 ret = -ENOENT;
233 goto end;
234 } else {
235 goto retry;
236 }
237 }
238 flagged = 1;
2ed95849 239 }
abc490a1
MD
240 /*
241 * Remove the element from the list. Retry if there has been a
242 * concurrent add (there cannot be a concurrent delete, because
243 * we won the deletion flag cmpxchg).
244 */
245 if (uatomic_cmpxchg(&iter_prev->next, iter, clear_flag(next)) != iter)
246 goto retry;
2ed95849 247end:
2ed95849 248 return ret;
abc490a1 249}
2ed95849 250
abc490a1
MD
251static
252void init_table(struct rcu_ht *ht, struct rcu_table *t,
253 unsigned long first, unsigned long len)
254{
255 unsigned long i, end;
256
257 end = first + len;
258 for (i = first; i < end; i++) {
259 /* Update table size when power of two */
260 if (i != 0 && !(i & (i - 1)))
261 t->size = i;
262 t->tbl[i] = calloc(1, sizeof(struct rcu_ht_node));
263 t->tbl[i]->dummy = 1;
264 t->tbl[i]->hash = i;
265 t->tbl[i]->reverse_hash = bit_reverse_ulong(i);
266 _ht_add(ht, t, t->tbl[i]);
267 }
268 t->size = end;
2ed95849
MD
269}
270
abc490a1
MD
271struct rcu_ht *ht_new(ht_hash_fct hash_fct,
272 void *hashseed,
273 unsigned long init_size,
274 void (*ht_call_rcu)(struct rcu_head *head,
275 void (*func)(struct rcu_head *head)))
276{
277 struct rcu_ht *ht;
278
279 ht = calloc(1, sizeof(struct rcu_ht));
280 ht->hash_fct = hash_fct;
281 ht->hashseed = hashseed;
282 /* this mutex should not nest in read-side C.S. */
283 pthread_mutex_init(&ht->resize_mutex, NULL);
284 ht->t = calloc(1, sizeof(struct rcu_table)
285 + (max(init_size, 1) * sizeof(struct rcu_ht_node *)));
286 ht->t->size = 0;
287 init_table(ht, ht->t, 0, max(init_size, 1));
288 ht->target_size = ht->t->size;
289 ht->ht_call_rcu = ht_call_rcu;
290 return ht;
291}
292
293struct rcu_ht_node *ht_lookup(struct rcu_ht *ht, void *key)
2ed95849 294{
395270b6 295 struct rcu_table *t;
abc490a1
MD
296 struct rcu_ht_node *node;
297 unsigned long hash, reverse_hash;
2ed95849 298
abc490a1
MD
299 hash = ht->hash_fct(ht->hashseed, key);
300 reverse_hash = bit_reverse_ulong(hash);
464a1ec9 301
395270b6 302 t = rcu_dereference(ht->t);
abc490a1
MD
303 cmm_smp_read_barrier_depends(); /* read t before size and table */
304 node = rcu_dereference(t->tbl[hash & (t->size - 1)]);
2ed95849 305 for (;;) {
abc490a1
MD
306 if (unlikely(!node))
307 break;
308 if (node->reverse_hash > reverse_hash) {
309 node = NULL;
310 break;
2ed95849
MD
311 }
312 if (node->key == key) {
abc490a1
MD
313 if (is_removed(rcu_dereference(node->next)))
314 node = NULL;
2ed95849
MD
315 break;
316 }
abc490a1 317 node = clear_flag(rcu_dereference(node->next));
2ed95849 318 }
abc490a1
MD
319 return node;
320}
e0ba718a 321
abc490a1
MD
322int ht_add(struct rcu_ht *ht, struct rcu_ht_node *node)
323{
324 struct rcu_table *t;
ab7d5fc6 325
abc490a1
MD
326 node->hash = ht->hash_fct(ht->hashseed, node->key);
327 node->reverse_hash = bit_reverse_ulong((unsigned long) node->hash);
2ed95849 328
abc490a1
MD
329 t = rcu_dereference(ht->t);
330 cmm_smp_read_barrier_depends(); /* read t before size and table */
331 return _ht_add(ht, t, node);
2ed95849
MD
332}
333
abc490a1 334int ht_remove(struct rcu_ht *ht, struct rcu_ht_node *node)
2ed95849 335{
abc490a1
MD
336 struct rcu_table *t;
337
338 t = rcu_dereference(ht->t);
339 cmm_smp_read_barrier_depends(); /* read t before size and table */
340 return _ht_remove(ht, t, node);
2ed95849 341}
ab7d5fc6 342
abc490a1
MD
343static
344int ht_delete_dummy(struct rcu_ht *ht)
674f7a69 345{
395270b6 346 struct rcu_table *t;
abc490a1
MD
347 struct rcu_ht_node *node;
348 unsigned long i;
674f7a69 349
abc490a1
MD
350 t = ht->t;
351 /* Check that the table is empty */
352 node = t->tbl[0];
353 do {
354 if (!node->dummy)
355 return -EPERM;
356 node = node->next;
357 } while (node);
358 /* Internal sanity check: all nodes left should be dummy */
395270b6 359 for (i = 0; i < t->size; i++) {
abc490a1
MD
360 assert(t->tbl[i]->dummy);
361 free(t->tbl[i]);
674f7a69 362 }
abc490a1 363 return 0;
674f7a69
MD
364}
365
366/*
367 * Should only be called when no more concurrent readers nor writers can
368 * possibly access the table.
369 */
5e28c532 370int ht_destroy(struct rcu_ht *ht)
674f7a69 371{
5e28c532
MD
372 int ret;
373
abc490a1
MD
374 ret = ht_delete_dummy(ht);
375 if (ret)
376 return ret;
395270b6 377 free(ht->t);
674f7a69 378 free(ht);
5e28c532 379 return ret;
674f7a69
MD
380}
381
abc490a1
MD
382static
383void ht_free_table_cb(struct rcu_head *head)
384{
385 struct rcu_table *t =
386 caa_container_of(head, struct rcu_table, head);
387 free(t);
388}
389
390/* called with resize mutex held */
391static
392void _do_ht_resize(struct rcu_ht *ht)
464a1ec9 393{
abc490a1 394 unsigned long new_size, old_size;
395270b6 395 struct rcu_table *new_t, *old_t;
464a1ec9 396
395270b6
MD
397 old_t = ht->t;
398 old_size = old_t->size;
464a1ec9 399
abc490a1
MD
400 new_size = CMM_LOAD_SHARED(ht->target_size);
401 if (old_size == new_size)
464a1ec9 402 return;
abc490a1
MD
403 new_t = realloc(old_t, sizeof(struct rcu_table)
404 + (new_size * sizeof(struct rcu_ht_node *)));
405 if (new_size > old_size)
406 init_table(ht, new_t, old_size, new_size - old_size);
407 cmm_smp_wmb(); /* update content before updating reallocated size */
408 CMM_STORE_SHARED(new_t->size, new_size);
409 if (new_t != old_t) {
410 /* Changing table and size atomically wrt lookups */
411 rcu_assign_pointer(ht->t, new_t);
412 ht->ht_call_rcu(&old_t->head, ht_free_table_cb);
464a1ec9 413 }
464a1ec9
MD
414}
415
abc490a1
MD
416static
417void resize_target_update(struct rcu_ht *ht, int growth_order)
464a1ec9 418{
abc490a1
MD
419 _uatomic_max(&ht->target_size,
420 CMM_LOAD_SHARED(ht->target_size) << growth_order);
464a1ec9
MD
421}
422
464a1ec9
MD
423void ht_resize(struct rcu_ht *ht, int growth)
424{
abc490a1
MD
425 resize_target_update(ht, growth);
426 pthread_mutex_lock(&ht->resize_mutex);
427 _do_ht_resize(ht);
428 pthread_mutex_unlock(&ht->resize_mutex);
429}
464a1ec9 430
abc490a1
MD
431static
432void do_resize_cb(struct rcu_head *head)
433{
434 struct rcu_resize_work *work =
435 caa_container_of(head, struct rcu_resize_work, head);
436 struct rcu_ht *ht = work->ht;
437
438 pthread_mutex_lock(&ht->resize_mutex);
439 _do_ht_resize(ht);
440 pthread_mutex_unlock(&ht->resize_mutex);
441 free(work);
464a1ec9
MD
442}
443
abc490a1
MD
444static
445void ht_resize_lazy(struct rcu_ht *ht, int growth)
ab7d5fc6 446{
abc490a1
MD
447 struct rcu_resize_work *work;
448
449 work = malloc(sizeof(*work));
450 work->ht = ht;
451 resize_target_update(ht, growth);
452 ht->ht_call_rcu(&work->head, do_resize_cb);
ab7d5fc6 453}
This page took 0.077687 seconds and 4 git commands to generate.