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
,
226 struct cds_ja
*ja
, int level
)
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
;
243 shadow_node
->level
= inherit_from
->level
;
245 shadow_node
->lock
= calloc(sizeof(*shadow_node
->lock
), 1);
246 if (!shadow_node
->lock
) {
250 pthread_mutex_init(shadow_node
->lock
, NULL
);
251 shadow_node
->level
= level
;
254 flavor
= cds_lfht_rcu_flavor(ht
);
256 ret_node
= cds_lfht_add_unique(ht
,
257 hash_pointer(new_node_flag
, hash_seed
),
260 &shadow_node
->ht_node
);
261 flavor
->read_unlock();
263 if (ret_node
!= &shadow_node
->ht_node
) {
271 void free_shadow_node(struct rcu_head
*head
)
273 struct cds_ja_shadow_node
*shadow_node
=
274 caa_container_of(head
, struct cds_ja_shadow_node
, head
);
279 void free_shadow_node_and_node(struct rcu_head
*head
)
281 struct cds_ja_shadow_node
*shadow_node
=
282 caa_container_of(head
, struct cds_ja_shadow_node
, head
);
283 free_cds_ja_node(ja_node_ptr(shadow_node
->node_flag
));
288 void free_shadow_node_and_lock(struct rcu_head
*head
)
290 struct cds_ja_shadow_node
*shadow_node
=
291 caa_container_of(head
, struct cds_ja_shadow_node
, head
);
292 free(shadow_node
->lock
);
297 void free_shadow_node_and_node_and_lock(struct rcu_head
*head
)
299 struct cds_ja_shadow_node
*shadow_node
=
300 caa_container_of(head
, struct cds_ja_shadow_node
, head
);
301 assert(shadow_node
->level
);
302 free_cds_ja_node(ja_node_ptr(shadow_node
->node_flag
));
303 free(shadow_node
->lock
);
307 __attribute__((visibility("protected")))
308 int rcuja_shadow_clear(struct cds_lfht
*ht
,
309 struct cds_ja_inode_flag
*node_flag
,
310 struct cds_ja_shadow_node
*shadow_node
,
313 struct cds_lfht_iter iter
;
314 struct cds_lfht_node
*lookup_node
;
315 const struct rcu_flavor_struct
*flavor
;
317 int lookup_shadow
= 0;
319 flavor
= cds_lfht_rcu_flavor(ht
);
322 cds_lfht_lookup(ht
, hash_pointer(node_flag
, hash_seed
),
323 match_pointer
, node_flag
, &iter
);
324 lookup_node
= cds_lfht_iter_get_node(&iter
);
331 shadow_node
= caa_container_of(lookup_node
,
332 struct cds_ja_shadow_node
, ht_node
);
333 lockret
= pthread_mutex_lock(shadow_node
->lock
);
339 * Holding the mutex across deletion, and by also re-checking if
340 * the node is deleted with mutex held at lookup ensure that we
341 * don't let RCU JA use a node being removed.
343 ret
= cds_lfht_del(ht
, lookup_node
);
345 if ((flags
& RCUJA_SHADOW_CLEAR_FREE_NODE
)
346 && shadow_node
->level
) {
347 if (flags
& RCUJA_SHADOW_CLEAR_FREE_LOCK
) {
348 flavor
->update_call_rcu(&shadow_node
->head
,
349 free_shadow_node_and_node_and_lock
);
351 flavor
->update_call_rcu(&shadow_node
->head
,
352 free_shadow_node_and_node
);
355 if (flags
& RCUJA_SHADOW_CLEAR_FREE_LOCK
) {
356 flavor
->update_call_rcu(&shadow_node
->head
,
357 free_shadow_node_and_lock
);
359 flavor
->update_call_rcu(&shadow_node
->head
,
365 lockret
= pthread_mutex_unlock(shadow_node
->lock
);
369 flavor
->read_unlock();
375 * Delete all shadow nodes and nodes from hash table, along with their
378 __attribute__((visibility("protected")))
379 void rcuja_shadow_prune(struct cds_lfht
*ht
,
381 void (*free_node_cb
)(struct rcu_head
*head
))
383 const struct rcu_flavor_struct
*flavor
;
384 struct cds_ja_shadow_node
*shadow_node
;
385 struct cds_lfht_iter iter
;
388 flavor
= cds_lfht_rcu_flavor(ht
);
390 cds_lfht_for_each_entry(ht
, &iter
, shadow_node
, ht_node
) {
391 lockret
= pthread_mutex_lock(shadow_node
->lock
);
394 ret
= cds_lfht_del(ht
, &shadow_node
->ht_node
);
396 if ((flags
& RCUJA_SHADOW_CLEAR_FREE_NODE
)
397 && shadow_node
->level
) {
398 if (shadow_node
->level
== shadow_node
->ja
->tree_depth
- 1) {
399 rcuja_free_all_children(shadow_node
,
400 shadow_node
->node_flag
,
403 if (flags
& RCUJA_SHADOW_CLEAR_FREE_LOCK
) {
404 flavor
->update_call_rcu(&shadow_node
->head
,
405 free_shadow_node_and_node_and_lock
);
407 flavor
->update_call_rcu(&shadow_node
->head
,
408 free_shadow_node_and_node
);
411 if (flags
& RCUJA_SHADOW_CLEAR_FREE_LOCK
) {
412 flavor
->update_call_rcu(&shadow_node
->head
,
413 free_shadow_node_and_lock
);
415 flavor
->update_call_rcu(&shadow_node
->head
,
420 lockret
= pthread_mutex_unlock(shadow_node
->lock
);
423 flavor
->read_unlock();
426 __attribute__((visibility("protected")))
427 struct cds_lfht
*rcuja_create_ht(const struct rcu_flavor_struct
*flavor
)
429 return _cds_lfht_new(1, 1, 0,
430 CDS_LFHT_AUTO_RESIZE
| CDS_LFHT_ACCOUNTING
,
434 __attribute__((visibility("protected")))
435 int rcuja_delete_ht(struct cds_lfht
*ht
)
437 return cds_lfht_destroy(ht
, NULL
);
440 __attribute__((constructor
))
441 void rcuja_ht_init(void)
443 hash_seed
= (unsigned long) time(NULL
);