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_node
*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 ret
= pthread_mutex_lock(shadow_node
->lock
);
201 if (cds_lfht_is_node_deleted(lookup_node
)) {
202 ret
= pthread_mutex_unlock(shadow_node
->lock
);
207 flavor
->read_unlock();
211 __attribute__((visibility("protected")))
212 void rcuja_shadow_unlock(struct cds_ja_shadow_node
*shadow_node
)
216 ret
= pthread_mutex_unlock(shadow_node
->lock
);
220 __attribute__((visibility("protected")))
221 int rcuja_shadow_set(struct cds_lfht
*ht
,
222 struct cds_ja_node
*new_node
,
223 struct cds_ja_shadow_node
*inherit_from
)
225 struct cds_ja_shadow_node
*shadow_node
;
226 struct cds_lfht_node
*ret_node
;
227 const struct rcu_flavor_struct
*flavor
;
229 shadow_node
= calloc(sizeof(*shadow_node
), 1);
233 shadow_node
->node
= new_node
;
235 * Lock can be inherited from previous node at this position.
238 shadow_node
->lock
= inherit_from
->lock
;
240 shadow_node
->lock
= calloc(sizeof(*shadow_node
->lock
), 1);
241 if (!shadow_node
->lock
) {
245 pthread_mutex_init(shadow_node
->lock
, NULL
);
248 flavor
= cds_lfht_rcu_flavor(ht
);
250 ret_node
= cds_lfht_add_unique(ht
,
251 hash_pointer(new_node
, hash_seed
),
254 &shadow_node
->ht_node
);
255 flavor
->read_unlock();
257 if (ret_node
!= &shadow_node
->ht_node
) {
265 void free_shadow_node_and_node(struct rcu_head
*head
)
267 struct cds_ja_shadow_node
*shadow_node
=
268 caa_container_of(head
, struct cds_ja_shadow_node
, head
);
269 free(shadow_node
->node
);
274 void free_shadow_node_and_node_and_lock(struct rcu_head
*head
)
276 struct cds_ja_shadow_node
*shadow_node
=
277 caa_container_of(head
, struct cds_ja_shadow_node
, head
);
278 free(shadow_node
->node
);
279 free(shadow_node
->lock
);
283 __attribute__((visibility("protected")))
284 int rcuja_shadow_clear(struct cds_lfht
*ht
,
285 struct cds_ja_node
*node
,
288 struct cds_lfht_iter iter
;
289 struct cds_lfht_node
*lookup_node
;
290 struct cds_ja_shadow_node
*shadow_node
;
291 const struct rcu_flavor_struct
*flavor
;
294 flavor
= cds_lfht_rcu_flavor(ht
);
296 cds_lfht_lookup(ht
, hash_pointer(node
, hash_seed
),
297 match_pointer
, node
, &iter
);
298 lookup_node
= cds_lfht_iter_get_node(&iter
);
303 shadow_node
= caa_container_of(lookup_node
,
304 struct cds_ja_shadow_node
, ht_node
);
305 lockret
= pthread_mutex_lock(shadow_node
->lock
);
309 * Holding the mutex across deletion, and by also re-checking if
310 * the node is deleted with mutex held at lookup ensure that we
311 * don't let RCU JA use a node being removed.
313 ret
= cds_lfht_del(ht
, lookup_node
);
315 assert(flags
& RCUJA_SHADOW_CLEAR_FREE_NODE
);
316 if (flags
& RCUJA_SHADOW_CLEAR_FREE_LOCK
) {
317 flavor
->update_call_rcu(&shadow_node
->head
,
318 free_shadow_node_and_node_and_lock
);
320 flavor
->update_call_rcu(&shadow_node
->head
,
321 free_shadow_node_and_node
);
324 lockret
= pthread_mutex_unlock(shadow_node
->lock
);
327 flavor
->read_unlock();
333 * Delete all shadow nodes and nodes from hash table, along with their
336 __attribute__((visibility("protected")))
337 void rcuja_shadow_prune(struct cds_lfht
*ht
,
340 const struct rcu_flavor_struct
*flavor
;
341 struct cds_ja_shadow_node
*shadow_node
;
342 struct cds_lfht_iter iter
;
345 flavor
= cds_lfht_rcu_flavor(ht
);
347 cds_lfht_for_each_entry(ht
, &iter
, shadow_node
, ht_node
) {
348 lockret
= pthread_mutex_lock(shadow_node
->lock
);
351 ret
= cds_lfht_del(ht
, &shadow_node
->ht_node
);
353 assert((flags
& RCUJA_SHADOW_CLEAR_FREE_NODE
)
354 && (flags
& RCUJA_SHADOW_CLEAR_FREE_LOCK
));
355 flavor
->update_call_rcu(&shadow_node
->head
,
356 free_shadow_node_and_node_and_lock
);
358 lockret
= pthread_mutex_unlock(shadow_node
->lock
);
361 flavor
->read_unlock();
364 __attribute__((visibility("protected")))
365 struct cds_lfht
*rcuja_create_ht(const struct rcu_flavor_struct
*flavor
)
367 return _cds_lfht_new(1, 1, 0,
368 CDS_LFHT_AUTO_RESIZE
| CDS_LFHT_ACCOUNTING
,
372 __attribute__((visibility("protected")))
373 int rcuja_delete_ht(struct cds_lfht
*ht
)
375 return cds_lfht_destroy(ht
, NULL
);
378 __attribute__((constructor
))
379 void rcuja_ht_init(void)
381 hash_seed
= (unsigned long) time(NULL
);