4 * Userspace RCU library - Lock-Free Expandable RCU Hash Table
6 * Copyright 2010-2011 - Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
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.
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.
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
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>
41 #define DEBUG /* Test */
44 #define dbg_printf(args...) printf(args)
46 #define dbg_printf(args...)
49 #define CHAIN_LEN_TARGET 1
50 #define CHAIN_LEN_RESIZE_THRESHOLD 2
53 #define max(a, b) ((a) > (b) ? (a) : (b))
56 #define REMOVED_FLAG (1UL << 0)
57 #define DUMMY_FLAG (1UL << 1)
58 #define FLAGS_MASK ((1UL << 2) - 1)
61 unsigned long size
; /* always a power of 2 */
62 unsigned long resize_target
;
65 struct rcu_ht_node
*tbl
[0];
69 struct rcu_table
*t
; /* shared */
71 ht_compare_fct compare_fct
;
72 unsigned long hash_seed
;
73 pthread_mutex_t resize_mutex
; /* resize mutex: add/del mutex */
74 unsigned int in_progress_resize
;
75 void (*ht_call_rcu
)(struct rcu_head
*head
,
76 void (*func
)(struct rcu_head
*head
));
79 struct rcu_resize_work
{
85 * Algorithm to reverse bits in a word by lookup table, extended to
88 * http://graphics.stanford.edu/~seander/bithacks.html#BitReverseTable
89 * Originally from Public Domain.
92 static const uint8_t BitReverseTable256
[256] =
94 #define R2(n) (n), (n) + 2*64, (n) + 1*64, (n) + 3*64
95 #define R4(n) R2(n), R2((n) + 2*16), R2((n) + 1*16), R2((n) + 3*16)
96 #define R6(n) R4(n), R4((n) + 2*4 ), R4((n) + 1*4 ), R4((n) + 3*4 )
97 R6(0), R6(2), R6(1), R6(3)
104 uint8_t bit_reverse_u8(uint8_t v
)
106 return BitReverseTable256
[v
];
109 static __attribute__((unused
))
110 uint32_t bit_reverse_u32(uint32_t v
)
112 return ((uint32_t) bit_reverse_u8(v
) << 24) |
113 ((uint32_t) bit_reverse_u8(v
>> 8) << 16) |
114 ((uint32_t) bit_reverse_u8(v
>> 16) << 8) |
115 ((uint32_t) bit_reverse_u8(v
>> 24));
118 static __attribute__((unused
))
119 uint64_t bit_reverse_u64(uint64_t v
)
121 return ((uint64_t) bit_reverse_u8(v
) << 56) |
122 ((uint64_t) bit_reverse_u8(v
>> 8) << 48) |
123 ((uint64_t) bit_reverse_u8(v
>> 16) << 40) |
124 ((uint64_t) bit_reverse_u8(v
>> 24) << 32) |
125 ((uint64_t) bit_reverse_u8(v
>> 32) << 24) |
126 ((uint64_t) bit_reverse_u8(v
>> 40) << 16) |
127 ((uint64_t) bit_reverse_u8(v
>> 48) << 8) |
128 ((uint64_t) bit_reverse_u8(v
>> 56));
132 unsigned long bit_reverse_ulong(unsigned long v
)
134 #if (CAA_BITS_PER_LONG == 32)
135 return bit_reverse_u32(v
);
137 return bit_reverse_u64(v
);
142 * Algorithm to find the log2 of a 32-bit unsigned integer.
143 * source: http://graphics.stanford.edu/~seander/bithacks.html#IntegerLogLookup
144 * Originally from Public Domain.
146 static const char LogTable256
[256] =
148 #define LT(n) n, n, n, n, n, n, n, n, n, n, n, n, n, n, n, n
149 -1, 0, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3,
150 LT(4), LT(5), LT(5), LT(6), LT(6), LT(6), LT(6),
151 LT(7), LT(7), LT(7), LT(7), LT(7), LT(7), LT(7), LT(7)
154 uint32_t log2_u32(uint32_t v
)
158 if ((tt
= (v
>> 16)))
159 return (t
= (tt
>> 8))
160 ? 24 + LogTable256
[t
]
161 : 16 + LogTable256
[tt
];
163 return (t
= (v
>> 8))
169 void ht_resize_lazy(struct rcu_ht
*ht
, struct rcu_table
*t
, int growth
);
172 void check_resize(struct rcu_ht
*ht
, struct rcu_table
*t
,
175 if (chain_len
>= CHAIN_LEN_RESIZE_THRESHOLD
)
176 ht_resize_lazy(ht
, t
,
177 log2_u32(chain_len
- CHAIN_LEN_TARGET
- 1));
181 struct rcu_ht_node
*clear_flag(struct rcu_ht_node
*node
)
183 return (struct rcu_ht_node
*) (((unsigned long) node
) & ~FLAGS_MASK
);
187 int is_removed(struct rcu_ht_node
*node
)
189 return ((unsigned long) node
) & REMOVED_FLAG
;
193 struct rcu_ht_node
*flag_removed(struct rcu_ht_node
*node
)
195 return (struct rcu_ht_node
*) (((unsigned long) node
) | REMOVED_FLAG
);
199 int is_dummy(struct rcu_ht_node
*node
)
201 return ((unsigned long) node
) & DUMMY_FLAG
;
205 struct rcu_ht_node
*flag_dummy(struct rcu_ht_node
*node
)
207 return (struct rcu_ht_node
*) (((unsigned long) node
) | DUMMY_FLAG
);
211 unsigned long _uatomic_max(unsigned long *ptr
, unsigned long v
)
213 unsigned long old1
, old2
;
215 old1
= uatomic_read(ptr
);
220 } while ((old1
= uatomic_cmpxchg(ptr
, old2
, v
)) != old2
);
225 * Remove all logically deleted nodes from a bucket up to a certain node key.
228 void _ht_gc_bucket(struct rcu_ht_node
*dummy
, struct rcu_ht_node
*node
)
230 struct rcu_ht_node
*iter_prev
, *iter
, *next
, *new_next
;
234 /* We can always skip the dummy node initially */
235 iter
= rcu_dereference(iter_prev
->p
.next
);
236 assert(iter_prev
->p
.reverse_hash
<= node
->p
.reverse_hash
);
238 if (unlikely(!clear_flag(iter
)))
240 if (clear_flag(iter
)->p
.reverse_hash
> node
->p
.reverse_hash
)
242 next
= rcu_dereference(clear_flag(iter
)->p
.next
);
243 if (is_removed(next
))
248 assert(!is_removed(iter
));
250 new_next
= flag_dummy(clear_flag(next
));
252 new_next
= clear_flag(next
);
253 (void) uatomic_cmpxchg(&iter_prev
->p
.next
, iter
, new_next
);
258 struct rcu_ht_node
*_ht_add(struct rcu_ht
*ht
, struct rcu_table
*t
,
259 struct rcu_ht_node
*node
, int unique
, int dummy
)
261 struct rcu_ht_node
*iter_prev
, *iter
, *next
, *new_node
, *new_next
,
266 assert(node
->p
.dummy
);
268 node
->p
.next
= flag_dummy(NULL
);
269 return node
; /* Initial first add (head) */
271 hash
= bit_reverse_ulong(node
->p
.reverse_hash
);
273 uint32_t chain_len
= 0;
276 * iter_prev points to the non-removed node prior to the
279 iter_prev
= rcu_dereference(t
->tbl
[hash
& (t
->size
- 1)]);
280 /* We can always skip the dummy node initially */
281 iter
= rcu_dereference(iter_prev
->p
.next
);
282 assert(iter_prev
->p
.reverse_hash
<= node
->p
.reverse_hash
);
284 if (unlikely(!clear_flag(iter
)))
286 if (clear_flag(iter
)->p
.reverse_hash
> node
->p
.reverse_hash
)
288 next
= rcu_dereference(clear_flag(iter
)->p
.next
);
289 if (is_removed(next
))
292 && !clear_flag(iter
)->p
.dummy
293 && !ht
->compare_fct(node
->key
, node
->key_len
,
294 clear_flag(iter
)->key
,
295 clear_flag(iter
)->key_len
))
296 return clear_flag(iter
);
297 /* Only account for identical reverse hash once */
298 if (iter_prev
->p
.reverse_hash
!= clear_flag(iter
)->p
.reverse_hash
)
299 check_resize(ht
, t
, ++chain_len
);
300 iter_prev
= clear_flag(iter
);
304 assert(node
!= clear_flag(iter
));
305 assert(!is_removed(iter_prev
));
306 assert(iter_prev
!= node
);
310 node
->p
.next
= flag_dummy(iter
);
312 new_node
= flag_dummy(node
);
315 if (uatomic_cmpxchg(&iter_prev
->p
.next
, iter
,
317 continue; /* retry */
321 assert(!is_removed(iter
));
323 new_next
= flag_dummy(clear_flag(next
));
325 new_next
= clear_flag(next
);
326 (void) uatomic_cmpxchg(&iter_prev
->p
.next
, iter
, new_next
);
330 /* Garbage collect logically removed nodes in the bucket */
331 dummy_node
= rcu_dereference(t
->tbl
[hash
& (t
->size
- 1)]);
332 _ht_gc_bucket(dummy_node
, node
);
337 int _ht_remove(struct rcu_ht
*ht
, struct rcu_table
*t
, struct rcu_ht_node
*node
)
339 struct rcu_ht_node
*dummy
, *next
, *old
;
343 /* logically delete the node */
344 old
= rcu_dereference(node
->p
.next
);
347 if (is_removed(next
))
349 assert(!node
->p
.dummy
);
350 old
= uatomic_cmpxchg(&node
->p
.next
, next
,
352 } while (old
!= next
);
354 /* We performed the (logical) deletion. */
358 * Ensure that the node is not visible to readers anymore: lookup for
359 * the node, and remove it (along with any other logically removed node)
362 hash
= bit_reverse_ulong(node
->p
.reverse_hash
);
363 dummy
= rcu_dereference(t
->tbl
[hash
& (t
->size
- 1)]);
364 _ht_gc_bucket(dummy
, node
);
367 * Only the flagging action indicated that we (and no other)
368 * removed the node from the hash.
371 assert(is_removed(rcu_dereference(node
->p
.next
)));
378 void init_table(struct rcu_ht
*ht
, struct rcu_table
*t
,
379 unsigned long first
, unsigned long len
)
381 unsigned long i
, end
;
384 for (i
= first
; i
< end
; i
++) {
385 /* Update table size when power of two */
386 if (i
!= 0 && !(i
& (i
- 1)))
388 t
->tbl
[i
] = calloc(1, sizeof(struct _rcu_ht_node
));
389 t
->tbl
[i
]->p
.dummy
= 1;
390 t
->tbl
[i
]->p
.reverse_hash
= bit_reverse_ulong(i
);
391 (void) _ht_add(ht
, t
, t
->tbl
[i
], 0, 1);
393 t
->resize_target
= t
->size
= end
;
394 t
->resize_initiated
= 0;
397 struct rcu_ht
*ht_new(ht_hash_fct hash_fct
,
398 ht_compare_fct compare_fct
,
399 unsigned long hash_seed
,
400 unsigned long init_size
,
401 void (*ht_call_rcu
)(struct rcu_head
*head
,
402 void (*func
)(struct rcu_head
*head
)))
406 ht
= calloc(1, sizeof(struct rcu_ht
));
407 ht
->hash_fct
= hash_fct
;
408 ht
->compare_fct
= compare_fct
;
409 ht
->hash_seed
= hash_seed
;
410 ht
->ht_call_rcu
= ht_call_rcu
;
411 ht
->in_progress_resize
= 0;
412 /* this mutex should not nest in read-side C.S. */
413 pthread_mutex_init(&ht
->resize_mutex
, NULL
);
414 ht
->t
= calloc(1, sizeof(struct rcu_table
)
415 + (max(init_size
, 1) * sizeof(struct rcu_ht_node
*)));
417 pthread_mutex_lock(&ht
->resize_mutex
);
418 init_table(ht
, ht
->t
, 0, max(init_size
, 1));
419 pthread_mutex_unlock(&ht
->resize_mutex
);
423 struct rcu_ht_node
*ht_lookup(struct rcu_ht
*ht
, void *key
, size_t key_len
)
426 struct rcu_ht_node
*node
;
427 unsigned long hash
, reverse_hash
;
429 hash
= ht
->hash_fct(key
, key_len
, ht
->hash_seed
);
430 reverse_hash
= bit_reverse_ulong(hash
);
432 t
= rcu_dereference(ht
->t
);
433 node
= rcu_dereference(t
->tbl
[hash
& (t
->size
- 1)]);
437 if (unlikely(node
->p
.reverse_hash
> reverse_hash
)) {
441 if (likely(!is_removed(rcu_dereference(node
->p
.next
)))
443 && likely(!ht
->compare_fct(node
->key
, node
->key_len
, key
, key_len
))) {
446 node
= clear_flag(rcu_dereference(node
->p
.next
));
448 assert(!node
|| !node
->p
.dummy
);
452 void ht_add(struct rcu_ht
*ht
, struct rcu_ht_node
*node
)
457 hash
= ht
->hash_fct(node
->key
, node
->key_len
, ht
->hash_seed
);
458 node
->p
.reverse_hash
= bit_reverse_ulong((unsigned long) hash
);
460 t
= rcu_dereference(ht
->t
);
461 (void) _ht_add(ht
, t
, node
, 0, 0);
464 struct rcu_ht_node
*ht_add_unique(struct rcu_ht
*ht
, struct rcu_ht_node
*node
)
469 hash
= ht
->hash_fct(node
->key
, node
->key_len
, ht
->hash_seed
);
470 node
->p
.reverse_hash
= bit_reverse_ulong((unsigned long) hash
);
472 t
= rcu_dereference(ht
->t
);
473 return _ht_add(ht
, t
, node
, 1, 0);
476 int ht_remove(struct rcu_ht
*ht
, struct rcu_ht_node
*node
)
480 t
= rcu_dereference(ht
->t
);
481 return _ht_remove(ht
, t
, node
);
485 int ht_delete_dummy(struct rcu_ht
*ht
)
488 struct rcu_ht_node
*node
;
492 /* Check that the table is empty */
498 assert(!is_removed(node
));
499 } while (clear_flag(node
));
500 /* Internal sanity check: all nodes left should be dummy */
501 for (i
= 0; i
< t
->size
; i
++) {
502 assert(t
->tbl
[i
]->p
.dummy
);
509 * Should only be called when no more concurrent readers nor writers can
510 * possibly access the table.
512 int ht_destroy(struct rcu_ht
*ht
)
516 /* Wait for in-flight resize operations to complete */
517 while (uatomic_read(&ht
->in_progress_resize
))
518 poll(NULL
, 0, 100); /* wait for 100ms */
519 ret
= ht_delete_dummy(ht
);
527 void ht_count_nodes(struct rcu_ht
*ht
,
528 unsigned long *count
,
529 unsigned long *removed
)
532 struct rcu_ht_node
*node
, *next
;
537 t
= rcu_dereference(ht
->t
);
538 /* Check that the table is empty */
539 node
= rcu_dereference(t
->tbl
[0]);
541 next
= rcu_dereference(node
->p
.next
);
542 if (is_removed(next
)) {
543 assert(!node
->p
.dummy
);
545 } else if (!node
->p
.dummy
)
547 node
= clear_flag(next
);
552 void ht_free_table_cb(struct rcu_head
*head
)
554 struct rcu_table
*t
=
555 caa_container_of(head
, struct rcu_table
, head
);
559 /* called with resize mutex held */
561 void _do_ht_resize(struct rcu_ht
*ht
)
563 unsigned long new_size
, old_size
;
564 struct rcu_table
*new_t
, *old_t
;
567 old_size
= old_t
->size
;
569 new_size
= CMM_LOAD_SHARED(old_t
->resize_target
);
570 dbg_printf("rculfhash: resize from %lu to %lu buckets\n",
572 if (old_size
== new_size
)
574 new_t
= malloc(sizeof(struct rcu_table
)
575 + (new_size
* sizeof(struct rcu_ht_node
*)));
576 assert(new_size
> old_size
);
577 memcpy(&new_t
->tbl
, &old_t
->tbl
,
578 old_size
* sizeof(struct rcu_ht_node
*));
579 init_table(ht
, new_t
, old_size
, new_size
- old_size
);
580 /* Changing table and size atomically wrt lookups */
581 rcu_assign_pointer(ht
->t
, new_t
);
582 ht
->ht_call_rcu(&old_t
->head
, ht_free_table_cb
);
586 unsigned long resize_target_update(struct rcu_table
*t
,
589 return _uatomic_max(&t
->resize_target
,
590 t
->size
<< growth_order
);
593 void ht_resize(struct rcu_ht
*ht
, int growth
)
595 struct rcu_table
*t
= rcu_dereference(ht
->t
);
596 unsigned long target_size
;
598 target_size
= resize_target_update(t
, growth
);
599 if (t
->size
< target_size
) {
600 CMM_STORE_SHARED(t
->resize_initiated
, 1);
601 pthread_mutex_lock(&ht
->resize_mutex
);
603 pthread_mutex_unlock(&ht
->resize_mutex
);
608 void do_resize_cb(struct rcu_head
*head
)
610 struct rcu_resize_work
*work
=
611 caa_container_of(head
, struct rcu_resize_work
, head
);
612 struct rcu_ht
*ht
= work
->ht
;
614 pthread_mutex_lock(&ht
->resize_mutex
);
616 pthread_mutex_unlock(&ht
->resize_mutex
);
618 cmm_smp_mb(); /* finish resize before decrement */
619 uatomic_dec(&ht
->in_progress_resize
);
623 void ht_resize_lazy(struct rcu_ht
*ht
, struct rcu_table
*t
, int growth
)
625 struct rcu_resize_work
*work
;
626 unsigned long target_size
;
628 target_size
= resize_target_update(t
, growth
);
629 if (!CMM_LOAD_SHARED(t
->resize_initiated
) && t
->size
< target_size
) {
630 uatomic_inc(&ht
->in_progress_resize
);
631 cmm_smp_mb(); /* increment resize count before calling it */
632 work
= malloc(sizeof(*work
));
634 ht
->ht_call_rcu(&work
->head
, do_resize_cb
);
635 CMM_STORE_SHARED(t
->resize_initiated
, 1);