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
);
177 __attribute__((visibility("protected")))
178 struct cds_ja_shadow_node
*rcuja_shadow_lookup_lock(struct cds_lfht
*ht
,
179 struct cds_ja_inode
*node
)
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
, hash_seed
),
190 match_pointer
, node
, &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
*new_node
,
225 struct cds_ja_shadow_node
*inherit_from
)
227 struct cds_ja_shadow_node
*shadow_node
;
228 struct cds_lfht_node
*ret_node
;
229 const struct rcu_flavor_struct
*flavor
;
231 shadow_node
= calloc(sizeof(*shadow_node
), 1);
235 shadow_node
->node
= new_node
;
237 * Lock can be inherited from previous node at this position.
240 shadow_node
->lock
= inherit_from
->lock
;
242 shadow_node
->lock
= calloc(sizeof(*shadow_node
->lock
), 1);
243 if (!shadow_node
->lock
) {
247 pthread_mutex_init(shadow_node
->lock
, NULL
);
250 flavor
= cds_lfht_rcu_flavor(ht
);
252 ret_node
= cds_lfht_add_unique(ht
,
253 hash_pointer(new_node
, hash_seed
),
256 &shadow_node
->ht_node
);
257 flavor
->read_unlock();
259 if (ret_node
!= &shadow_node
->ht_node
) {
267 void free_shadow_node(struct rcu_head
*head
)
269 struct cds_ja_shadow_node
*shadow_node
=
270 caa_container_of(head
, struct cds_ja_shadow_node
, head
);
275 void free_shadow_node_and_node(struct rcu_head
*head
)
277 struct cds_ja_shadow_node
*shadow_node
=
278 caa_container_of(head
, struct cds_ja_shadow_node
, head
);
279 free(shadow_node
->node
);
284 void free_shadow_node_and_lock(struct rcu_head
*head
)
286 struct cds_ja_shadow_node
*shadow_node
=
287 caa_container_of(head
, struct cds_ja_shadow_node
, head
);
288 free(shadow_node
->lock
);
293 void free_shadow_node_and_node_and_lock(struct rcu_head
*head
)
295 struct cds_ja_shadow_node
*shadow_node
=
296 caa_container_of(head
, struct cds_ja_shadow_node
, head
);
297 assert(!shadow_node
->is_root
);
298 free(shadow_node
->node
);
299 free(shadow_node
->lock
);
303 __attribute__((visibility("protected")))
304 int rcuja_shadow_clear(struct cds_lfht
*ht
,
305 struct cds_ja_inode
*node
,
306 struct cds_ja_shadow_node
*shadow_node
,
309 struct cds_lfht_iter iter
;
310 struct cds_lfht_node
*lookup_node
;
311 const struct rcu_flavor_struct
*flavor
;
313 int lookup_shadow
= 0;
315 flavor
= cds_lfht_rcu_flavor(ht
);
318 cds_lfht_lookup(ht
, hash_pointer(node
, hash_seed
),
319 match_pointer
, node
, &iter
);
320 lookup_node
= cds_lfht_iter_get_node(&iter
);
327 shadow_node
= caa_container_of(lookup_node
,
328 struct cds_ja_shadow_node
, ht_node
);
329 lockret
= pthread_mutex_lock(shadow_node
->lock
);
335 * Holding the mutex across deletion, and by also re-checking if
336 * the node is deleted with mutex held at lookup ensure that we
337 * don't let RCU JA use a node being removed.
339 ret
= cds_lfht_del(ht
, lookup_node
);
341 if ((flags
& RCUJA_SHADOW_CLEAR_FREE_NODE
)
342 && !shadow_node
->is_root
) {
343 if (flags
& RCUJA_SHADOW_CLEAR_FREE_LOCK
) {
344 flavor
->update_call_rcu(&shadow_node
->head
,
345 free_shadow_node_and_node_and_lock
);
347 flavor
->update_call_rcu(&shadow_node
->head
,
348 free_shadow_node_and_node
);
351 if (flags
& RCUJA_SHADOW_CLEAR_FREE_LOCK
) {
352 flavor
->update_call_rcu(&shadow_node
->head
,
353 free_shadow_node_and_lock
);
355 flavor
->update_call_rcu(&shadow_node
->head
,
361 lockret
= pthread_mutex_unlock(shadow_node
->lock
);
365 flavor
->read_unlock();
371 * Delete all shadow nodes and nodes from hash table, along with their
374 __attribute__((visibility("protected")))
375 void rcuja_shadow_prune(struct cds_lfht
*ht
,
378 const struct rcu_flavor_struct
*flavor
;
379 struct cds_ja_shadow_node
*shadow_node
;
380 struct cds_lfht_iter iter
;
383 flavor
= cds_lfht_rcu_flavor(ht
);
385 cds_lfht_for_each_entry(ht
, &iter
, shadow_node
, ht_node
) {
386 lockret
= pthread_mutex_lock(shadow_node
->lock
);
389 ret
= cds_lfht_del(ht
, &shadow_node
->ht_node
);
391 if ((flags
& RCUJA_SHADOW_CLEAR_FREE_NODE
)
392 && !shadow_node
->is_root
) {
393 if (flags
& RCUJA_SHADOW_CLEAR_FREE_LOCK
) {
394 flavor
->update_call_rcu(&shadow_node
->head
,
395 free_shadow_node_and_node_and_lock
);
397 flavor
->update_call_rcu(&shadow_node
->head
,
398 free_shadow_node_and_node
);
401 if (flags
& RCUJA_SHADOW_CLEAR_FREE_LOCK
) {
402 flavor
->update_call_rcu(&shadow_node
->head
,
403 free_shadow_node_and_lock
);
405 flavor
->update_call_rcu(&shadow_node
->head
,
410 lockret
= pthread_mutex_unlock(shadow_node
->lock
);
413 flavor
->read_unlock();
416 __attribute__((visibility("protected")))
417 struct cds_lfht
*rcuja_create_ht(const struct rcu_flavor_struct
*flavor
)
419 return _cds_lfht_new(1, 1, 0,
420 CDS_LFHT_AUTO_RESIZE
| CDS_LFHT_ACCOUNTING
,
424 __attribute__((visibility("protected")))
425 int rcuja_delete_ht(struct cds_lfht
*ht
)
427 return cds_lfht_destroy(ht
, NULL
);
430 __attribute__((constructor
))
431 void rcuja_ht_init(void)
433 hash_seed
= (unsigned long) time(NULL
);