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
29 * The hash table used by judy array updates only for the shadow node
30 * mapping rely on standard urcu_mb flavor. It does not put any
31 * requirement on the RCU flavor used by applications using the judy
36 #include <urcu/rcuja.h>
37 #include <urcu/compiler.h>
38 #include <urcu/arch.h>
40 #include <urcu-pointer.h>
44 #include "rcuja-internal.h"
47 static unsigned long hash_seed
;
51 * Source: http://burtleburtle.net/bob/c/lookup3.c
52 * Originally Public Domain
55 #define rot(x, k) (((x) << (k)) | ((x) >> (32 - (k))))
57 #define mix(a, b, c) \
59 a -= c; a ^= rot(c, 4); c += b; \
60 b -= a; b ^= rot(a, 6); a += c; \
61 c -= b; c ^= rot(b, 8); b += a; \
62 a -= c; a ^= rot(c, 16); c += b; \
63 b -= a; b ^= rot(a, 19); a += c; \
64 c -= b; c ^= rot(b, 4); b += a; \
67 #define final(a, b, c) \
69 c ^= b; c -= rot(b, 14); \
70 a ^= c; a -= rot(c, 11); \
71 b ^= a; b -= rot(a, 25); \
72 c ^= b; c -= rot(b, 16); \
73 a ^= c; a -= rot(c, 4);\
74 b ^= a; b -= rot(a, 14); \
75 c ^= b; c -= rot(b, 24); \
78 static inline __attribute__((unused
))
80 const uint32_t *k
, /* the key, an array of uint32_t values */
81 size_t length
, /* the length of the key, in uint32_ts */
82 uint32_t initval
) /* the previous hash, or an arbitrary value */
86 /* Set up the internal state */
87 a
= b
= c
= 0xdeadbeef + (((uint32_t) length
) << 2) + initval
;
89 /*----------------------------------------- handle most of the key */
99 /*----------------------------------- handle the last 3 uint32_t's */
100 switch (length
) { /* all the case statements fall through */
105 case 0: /* case 0: nothing left to add */
108 /*---------------------------------------------- report the result */
114 const uint32_t *k
, /* the key, an array of uint32_t values */
115 size_t length
, /* the length of the key, in uint32_ts */
116 uint32_t *pc
, /* IN: seed OUT: primary hash value */
117 uint32_t *pb
) /* IN: more seed OUT: secondary hash value */
121 /* Set up the internal state */
122 a
= b
= c
= 0xdeadbeef + ((uint32_t) (length
<< 2)) + *pc
;
125 /*----------------------------------------- handle most of the key */
135 /*----------------------------------- handle the last 3 uint32_t's */
136 switch (length
) { /* all the case statements fall through */
141 case 0: /* case 0: nothing left to add */
144 /*---------------------------------------------- report the result */
149 #if (CAA_BITS_PER_LONG == 32)
151 unsigned long hash_pointer(const void *_key
, unsigned long seed
)
153 unsigned int key
= (unsigned int) _key
;
155 return hash_u32(&key
, 1, seed
);
159 unsigned long hash_pointer(const void *_key
, unsigned long seed
)
170 v
.v64
= (uint64_t) seed
;
171 key
.v64
= (uint64_t) _key
;
172 hashword2(key
.v32
, 2, &v
.v32
[0], &v
.v32
[1]);
178 int match_pointer(struct cds_lfht_node
*node
, const void *key
)
180 struct rcu_ja_shadow_node
*shadow
=
181 caa_container_of(node
, struct rcu_ja_shadow_node
, ht_node
);
183 return (key
== shadow
->node
);
186 __attribute__((visibility("protected")))
187 struct rcu_ja_shadow_node
*rcuja_shadow_lookup_lock(struct cds_lfht
*ht
,
188 struct rcu_ja_node
*node
)
190 struct cds_lfht_iter iter
;
191 struct cds_lfht_node
*lookup_node
;
192 struct rcu_ja_shadow_node
*shadow_node
;
196 cds_lfht_lookup(ht
, hash_pointer(node
, hash_seed
),
197 match_pointer
, node
, &iter
);
199 lookup_node
= cds_lfht_iter_get_node(&iter
);
204 shadow_node
= caa_container_of(lookup_node
,
205 struct rcu_ja_shadow_node
, ht_node
);
206 ret
= pthread_mutex_lock(&shadow_node
->lock
);
208 if (cds_lfht_is_node_deleted(lookup_node
)) {
209 ret
= pthread_mutex_unlock(&shadow_node
->lock
);
218 void rcuja_shadow_unlock(struct rcu_ja_shadow_node
*shadow_node
)
222 ret
= pthread_mutex_unlock(&shadow_node
->lock
);
226 __attribute__((visibility("protected")))
227 int rcuja_shadow_set(struct cds_lfht
*ht
,
228 struct rcu_ja_node
*node
)
230 struct rcu_ja_shadow_node
*shadow_node
;
231 struct cds_lfht_node
*ret_node
;
233 shadow_node
= calloc(sizeof(*shadow_node
), 1);
237 shadow_node
->node
= node
;
238 pthread_mutex_init(&shadow_node
->lock
, NULL
);
241 ret_node
= cds_lfht_add_unique(ht
,
242 hash_pointer(node
, hash_seed
),
245 &shadow_node
->ht_node
);
248 if (ret_node
!= &shadow_node
->ht_node
) {
256 void free_shadow_node(struct rcu_head
*head
)
258 struct rcu_ja_shadow_node
*shadow_node
=
259 caa_container_of(head
, struct rcu_ja_shadow_node
, head
);
263 __attribute__((visibility("protected")))
264 int rcuja_shadow_clear(struct cds_lfht
*ht
,
265 struct rcu_ja_node
*node
)
267 struct cds_lfht_iter iter
;
268 struct cds_lfht_node
*lookup_node
;
269 struct rcu_ja_shadow_node
*shadow_node
;
273 cds_lfht_lookup(ht
, hash_pointer(node
, hash_seed
),
274 match_pointer
, node
, &iter
);
275 lookup_node
= cds_lfht_iter_get_node(&iter
);
280 shadow_node
= caa_container_of(lookup_node
,
281 struct rcu_ja_shadow_node
, ht_node
);
282 lockret
= pthread_mutex_lock(&shadow_node
->lock
);
286 * Holding the mutex across deletion, and by also re-checking if
287 * the node is deleted with mutex held at lookup ensure that we
288 * don't let RCU JA use a node being removed.
290 ret
= cds_lfht_del(ht
, lookup_node
);
292 call_rcu(&shadow_node
->head
, free_shadow_node
);
294 lockret
= pthread_mutex_unlock(&shadow_node
->lock
);
302 __attribute__((visibility("protected")))
303 struct cds_lfht
*rcuja_create_ht(void)
305 return cds_lfht_new(1, 1, 0,
306 CDS_LFHT_AUTO_RESIZE
| CDS_LFHT_ACCOUNTING
,
310 __attribute__((visibility("protected")))
311 void rcuja_delete_ht(struct cds_lfht
*ht
)
315 ret
= cds_lfht_destroy(ht
, NULL
);
319 __attribute__((constructor
))
320 void rcuja_ht_init(void)
322 hash_seed
= (unsigned long) time(NULL
);
This page took 0.067447 seconds and 5 git commands to generate.