2 * rcuja/rcuja-hashtable.c
4 * Userspace RCU library - RCU Judy Array Shadow Node Hash Table
6 * Copyright 2012 - 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
27 #include <urcu/rcuja.h>
28 #include <urcu/compiler.h>
29 #include <urcu/arch.h>
31 #include <urcu-pointer.h>
35 #include "rcuja-internal.h"
38 static unsigned long hash_seed
;
42 * Source: http://burtleburtle.net/bob/c/lookup3.c
43 * Originally Public Domain
46 #define rot(x, k) (((x) << (k)) | ((x) >> (32 - (k))))
48 #define mix(a, b, c) \
50 a -= c; a ^= rot(c, 4); c += b; \
51 b -= a; b ^= rot(a, 6); a += c; \
52 c -= b; c ^= rot(b, 8); b += a; \
53 a -= c; a ^= rot(c, 16); c += b; \
54 b -= a; b ^= rot(a, 19); a += c; \
55 c -= b; c ^= rot(b, 4); b += a; \
58 #define final(a, b, c) \
60 c ^= b; c -= rot(b, 14); \
61 a ^= c; a -= rot(c, 11); \
62 b ^= a; b -= rot(a, 25); \
63 c ^= b; c -= rot(b, 16); \
64 a ^= c; a -= rot(c, 4);\
65 b ^= a; b -= rot(a, 14); \
66 c ^= b; c -= rot(b, 24); \
69 static inline __attribute__((unused
))
71 const uint32_t *k
, /* the key, an array of uint32_t values */
72 size_t length
, /* the length of the key, in uint32_ts */
73 uint32_t initval
) /* the previous hash, or an arbitrary value */
77 /* Set up the internal state */
78 a
= b
= c
= 0xdeadbeef + (((uint32_t) length
) << 2) + initval
;
80 /*----------------------------------------- handle most of the key */
90 /*----------------------------------- handle the last 3 uint32_t's */
91 switch (length
) { /* all the case statements fall through */
96 case 0: /* case 0: nothing left to add */
99 /*---------------------------------------------- report the result */
105 const uint32_t *k
, /* the key, an array of uint32_t values */
106 size_t length
, /* the length of the key, in uint32_ts */
107 uint32_t *pc
, /* IN: seed OUT: primary hash value */
108 uint32_t *pb
) /* IN: more seed OUT: secondary hash value */
112 /* Set up the internal state */
113 a
= b
= c
= 0xdeadbeef + ((uint32_t) (length
<< 2)) + *pc
;
116 /*----------------------------------------- handle most of the key */
126 /*----------------------------------- handle the last 3 uint32_t's */
127 switch (length
) { /* all the case statements fall through */
132 case 0: /* case 0: nothing left to add */
135 /*---------------------------------------------- report the result */
140 #if (CAA_BITS_PER_LONG == 32)
142 unsigned long hash_pointer(const void *_key
, unsigned long seed
)
144 unsigned int key
= (unsigned int) _key
;
146 return hash_u32(&key
, 1, seed
);
150 unsigned long hash_pointer(const void *_key
, unsigned long seed
)
161 v
.v64
= (uint64_t) seed
;
162 key
.v64
= (uint64_t) _key
;
163 hashword2(key
.v32
, 2, &v
.v32
[0], &v
.v32
[1]);
169 int match_pointer(struct cds_lfht_node
*node
, const void *key
)
171 struct cds_ja_shadow_node
*shadow
=
172 caa_container_of(node
, struct cds_ja_shadow_node
, ht_node
);
174 return (key
== shadow
->node_flag
);
177 __attribute__((visibility("protected")))
178 struct cds_ja_shadow_node
*rcuja_shadow_lookup_lock(struct cds_lfht
*ht
,
179 struct cds_ja_inode_flag
*node_flag
)
181 struct cds_lfht_iter iter
;
182 struct cds_lfht_node
*lookup_node
;
183 struct cds_ja_shadow_node
*shadow_node
;
184 const struct rcu_flavor_struct
*flavor
;
187 flavor
= cds_lfht_rcu_flavor(ht
);
189 cds_lfht_lookup(ht
, hash_pointer(node_flag
, hash_seed
),
190 match_pointer
, node_flag
, &iter
);
192 lookup_node
= cds_lfht_iter_get_node(&iter
);
197 shadow_node
= caa_container_of(lookup_node
,
198 struct cds_ja_shadow_node
, ht_node
);
199 dbg_printf("Lock %p\n", shadow_node
->lock
);
200 ret
= pthread_mutex_lock(shadow_node
->lock
);
202 if (cds_lfht_is_node_deleted(lookup_node
)) {
203 ret
= pthread_mutex_unlock(shadow_node
->lock
);
208 flavor
->read_unlock();
212 __attribute__((visibility("protected")))
213 void rcuja_shadow_unlock(struct cds_ja_shadow_node
*shadow_node
)
217 dbg_printf("Unlock %p\n", shadow_node
->lock
);
218 ret
= pthread_mutex_unlock(shadow_node
->lock
);
222 __attribute__((visibility("protected")))
223 struct cds_ja_shadow_node
*rcuja_shadow_set(struct cds_lfht
*ht
,
224 struct cds_ja_inode_flag
*new_node_flag
,
225 struct cds_ja_shadow_node
*inherit_from
,
228 struct cds_ja_shadow_node
*shadow_node
;
229 struct cds_lfht_node
*ret_node
;
230 const struct rcu_flavor_struct
*flavor
;
232 shadow_node
= calloc(sizeof(*shadow_node
), 1);
236 shadow_node
->node_flag
= new_node_flag
;
237 shadow_node
->ja
= ja
;
239 * Lock can be inherited from previous node at this position.
242 shadow_node
->lock
= inherit_from
->lock
;
244 shadow_node
->lock
= calloc(sizeof(*shadow_node
->lock
), 1);
245 if (!shadow_node
->lock
) {
249 pthread_mutex_init(shadow_node
->lock
, NULL
);
252 flavor
= cds_lfht_rcu_flavor(ht
);
254 ret_node
= cds_lfht_add_unique(ht
,
255 hash_pointer(new_node_flag
, hash_seed
),
258 &shadow_node
->ht_node
);
259 flavor
->read_unlock();
261 if (ret_node
!= &shadow_node
->ht_node
) {
269 void free_shadow_node(struct rcu_head
*head
)
271 struct cds_ja_shadow_node
*shadow_node
=
272 caa_container_of(head
, struct cds_ja_shadow_node
, head
);
277 void free_shadow_node_and_node(struct rcu_head
*head
)
279 struct cds_ja_shadow_node
*shadow_node
=
280 caa_container_of(head
, struct cds_ja_shadow_node
, head
);
281 free(ja_node_ptr(shadow_node
->node_flag
));
286 void free_shadow_node_and_lock(struct rcu_head
*head
)
288 struct cds_ja_shadow_node
*shadow_node
=
289 caa_container_of(head
, struct cds_ja_shadow_node
, head
);
290 free(shadow_node
->lock
);
295 void free_shadow_node_and_node_and_lock(struct rcu_head
*head
)
297 struct cds_ja_shadow_node
*shadow_node
=
298 caa_container_of(head
, struct cds_ja_shadow_node
, head
);
299 assert(shadow_node
->level
);
300 free(ja_node_ptr(shadow_node
->node_flag
));
301 free(shadow_node
->lock
);
305 __attribute__((visibility("protected")))
306 int rcuja_shadow_clear(struct cds_lfht
*ht
,
307 struct cds_ja_inode_flag
*node_flag
,
308 struct cds_ja_shadow_node
*shadow_node
,
311 struct cds_lfht_iter iter
;
312 struct cds_lfht_node
*lookup_node
;
313 const struct rcu_flavor_struct
*flavor
;
315 int lookup_shadow
= 0;
317 flavor
= cds_lfht_rcu_flavor(ht
);
320 cds_lfht_lookup(ht
, hash_pointer(node_flag
, hash_seed
),
321 match_pointer
, node_flag
, &iter
);
322 lookup_node
= cds_lfht_iter_get_node(&iter
);
329 shadow_node
= caa_container_of(lookup_node
,
330 struct cds_ja_shadow_node
, ht_node
);
331 lockret
= pthread_mutex_lock(shadow_node
->lock
);
337 * Holding the mutex across deletion, and by also re-checking if
338 * the node is deleted with mutex held at lookup ensure that we
339 * don't let RCU JA use a node being removed.
341 ret
= cds_lfht_del(ht
, lookup_node
);
343 if ((flags
& RCUJA_SHADOW_CLEAR_FREE_NODE
)
344 && shadow_node
->level
) {
345 if (flags
& RCUJA_SHADOW_CLEAR_FREE_LOCK
) {
346 flavor
->update_call_rcu(&shadow_node
->head
,
347 free_shadow_node_and_node_and_lock
);
349 flavor
->update_call_rcu(&shadow_node
->head
,
350 free_shadow_node_and_node
);
353 if (flags
& RCUJA_SHADOW_CLEAR_FREE_LOCK
) {
354 flavor
->update_call_rcu(&shadow_node
->head
,
355 free_shadow_node_and_lock
);
357 flavor
->update_call_rcu(&shadow_node
->head
,
363 lockret
= pthread_mutex_unlock(shadow_node
->lock
);
367 flavor
->read_unlock();
373 * Delete all shadow nodes and nodes from hash table, along with their
376 __attribute__((visibility("protected")))
377 void rcuja_shadow_prune(struct cds_lfht
*ht
,
379 void (*free_node_cb
)(struct rcu_head
*head
))
381 const struct rcu_flavor_struct
*flavor
;
382 struct cds_ja_shadow_node
*shadow_node
;
383 struct cds_lfht_iter iter
;
386 flavor
= cds_lfht_rcu_flavor(ht
);
388 cds_lfht_for_each_entry(ht
, &iter
, shadow_node
, ht_node
) {
389 lockret
= pthread_mutex_lock(shadow_node
->lock
);
392 ret
= cds_lfht_del(ht
, &shadow_node
->ht_node
);
394 if ((flags
& RCUJA_SHADOW_CLEAR_FREE_NODE
)
395 && shadow_node
->level
) {
396 if (shadow_node
->level
== shadow_node
->ja
->tree_depth
- 1) {
397 rcuja_free_all_children(shadow_node
,
398 shadow_node
->node_flag
,
401 if (flags
& RCUJA_SHADOW_CLEAR_FREE_LOCK
) {
402 flavor
->update_call_rcu(&shadow_node
->head
,
403 free_shadow_node_and_node_and_lock
);
405 flavor
->update_call_rcu(&shadow_node
->head
,
406 free_shadow_node_and_node
);
409 if (flags
& RCUJA_SHADOW_CLEAR_FREE_LOCK
) {
410 flavor
->update_call_rcu(&shadow_node
->head
,
411 free_shadow_node_and_lock
);
413 flavor
->update_call_rcu(&shadow_node
->head
,
418 lockret
= pthread_mutex_unlock(shadow_node
->lock
);
421 flavor
->read_unlock();
424 __attribute__((visibility("protected")))
425 struct cds_lfht
*rcuja_create_ht(const struct rcu_flavor_struct
*flavor
)
427 return _cds_lfht_new(1, 1, 0,
428 CDS_LFHT_AUTO_RESIZE
| CDS_LFHT_ACCOUNTING
,
432 __attribute__((visibility("protected")))
433 int rcuja_delete_ht(struct cds_lfht
*ht
)
435 return cds_lfht_destroy(ht
, NULL
);
438 __attribute__((constructor
))
439 void rcuja_ht_init(void)
441 hash_seed
= (unsigned long) time(NULL
);