Commit | Line | Data |
---|---|---|
195e72d3 MD |
1 | /* |
2 | * rcuja/rcuja-hashtable.c | |
3 | * | |
4 | * Userspace RCU library - RCU Judy Array Shadow Node Hash Table | |
5 | * | |
6 | * Copyright 2012 - Mathieu Desnoyers <mathieu.desnoyers@efficios.com> | |
7 | * | |
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. | |
12 | * | |
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. | |
17 | * | |
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 | |
21 | */ | |
22 | ||
23 | #define _LGPL_SOURCE | |
24 | #include <stdint.h> | |
25 | #include <errno.h> | |
26 | #include <limits.h> | |
195e72d3 MD |
27 | #include <urcu/rcuja.h> |
28 | #include <urcu/compiler.h> | |
29 | #include <urcu/arch.h> | |
30 | #include <assert.h> | |
31 | #include <urcu-pointer.h> | |
d22c185b MD |
32 | #include <stdlib.h> |
33 | #include <time.h> | |
195e72d3 MD |
34 | |
35 | #include "rcuja-internal.h" | |
36 | #include "bitfield.h" | |
37 | ||
d22c185b MD |
38 | static unsigned long hash_seed; |
39 | ||
40 | /* | |
41 | * Hash function | |
42 | * Source: http://burtleburtle.net/bob/c/lookup3.c | |
43 | * Originally Public Domain | |
44 | */ | |
45 | ||
46 | #define rot(x, k) (((x) << (k)) | ((x) >> (32 - (k)))) | |
47 | ||
48 | #define mix(a, b, c) \ | |
49 | do { \ | |
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; \ | |
56 | } while (0) | |
57 | ||
58 | #define final(a, b, c) \ | |
59 | { \ | |
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); \ | |
67 | } | |
68 | ||
69 | static inline __attribute__((unused)) | |
70 | uint32_t hash_u32( | |
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 */ | |
74 | { | |
75 | uint32_t a, b, c; | |
76 | ||
77 | /* Set up the internal state */ | |
78 | a = b = c = 0xdeadbeef + (((uint32_t) length) << 2) + initval; | |
79 | ||
80 | /*----------------------------------------- handle most of the key */ | |
81 | while (length > 3) { | |
82 | a += k[0]; | |
83 | b += k[1]; | |
84 | c += k[2]; | |
85 | mix(a, b, c); | |
86 | length -= 3; | |
87 | k += 3; | |
88 | } | |
89 | ||
90 | /*----------------------------------- handle the last 3 uint32_t's */ | |
91 | switch (length) { /* all the case statements fall through */ | |
92 | case 3: c += k[2]; | |
93 | case 2: b += k[1]; | |
94 | case 1: a += k[0]; | |
95 | final(a, b, c); | |
96 | case 0: /* case 0: nothing left to add */ | |
97 | break; | |
98 | } | |
99 | /*---------------------------------------------- report the result */ | |
100 | return c; | |
101 | } | |
102 | ||
103 | static inline | |
104 | void hashword2( | |
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 */ | |
109 | { | |
110 | uint32_t a, b, c; | |
111 | ||
112 | /* Set up the internal state */ | |
113 | a = b = c = 0xdeadbeef + ((uint32_t) (length << 2)) + *pc; | |
114 | c += *pb; | |
115 | ||
116 | /*----------------------------------------- handle most of the key */ | |
117 | while (length > 3) { | |
118 | a += k[0]; | |
119 | b += k[1]; | |
120 | c += k[2]; | |
121 | mix(a, b, c); | |
122 | length -= 3; | |
123 | k += 3; | |
124 | } | |
125 | ||
126 | /*----------------------------------- handle the last 3 uint32_t's */ | |
127 | switch (length) { /* all the case statements fall through */ | |
128 | case 3: c += k[2]; | |
129 | case 2: b += k[1]; | |
130 | case 1: a += k[0]; | |
131 | final(a, b, c); | |
132 | case 0: /* case 0: nothing left to add */ | |
133 | break; | |
134 | } | |
135 | /*---------------------------------------------- report the result */ | |
136 | *pc = c; | |
137 | *pb = b; | |
138 | } | |
139 | ||
140 | #if (CAA_BITS_PER_LONG == 32) | |
141 | static | |
142 | unsigned long hash_pointer(const void *_key, unsigned long seed) | |
143 | { | |
144 | unsigned int key = (unsigned int) _key; | |
145 | ||
146 | return hash_u32(&key, 1, seed); | |
147 | } | |
148 | #else | |
149 | static | |
150 | unsigned long hash_pointer(const void *_key, unsigned long seed) | |
151 | { | |
152 | union { | |
153 | uint64_t v64; | |
154 | uint32_t v32[2]; | |
155 | } v; | |
156 | union { | |
157 | uint64_t v64; | |
158 | uint32_t v32[2]; | |
159 | } key; | |
160 | ||
161 | v.v64 = (uint64_t) seed; | |
162 | key.v64 = (uint64_t) _key; | |
163 | hashword2(key.v32, 2, &v.v32[0], &v.v32[1]); | |
164 | return v.v64; | |
165 | } | |
166 | #endif | |
167 | ||
168 | static | |
169 | int match_pointer(struct cds_lfht_node *node, const void *key) | |
170 | { | |
171 | struct rcu_ja_shadow_node *shadow = | |
172 | caa_container_of(node, struct rcu_ja_shadow_node, ht_node); | |
173 | ||
174 | return (key == shadow->node); | |
175 | } | |
176 | ||
177 | __attribute__((visibility("protected"))) | |
178 | struct rcu_ja_shadow_node *rcuja_shadow_lookup_lock(struct cds_lfht *ht, | |
179 | struct rcu_ja_node *node) | |
180 | { | |
181 | struct cds_lfht_iter iter; | |
182 | struct cds_lfht_node *lookup_node; | |
183 | struct rcu_ja_shadow_node *shadow_node; | |
5eb692c0 | 184 | const struct rcu_flavor_struct *flavor; |
d22c185b MD |
185 | int ret; |
186 | ||
5eb692c0 MD |
187 | flavor = cds_lfht_rcu_flavor(ht); |
188 | flavor->read_lock(); | |
d22c185b MD |
189 | cds_lfht_lookup(ht, hash_pointer(node, hash_seed), |
190 | match_pointer, node, &iter); | |
191 | ||
192 | lookup_node = cds_lfht_iter_get_node(&iter); | |
193 | if (!lookup_node) { | |
194 | shadow_node = NULL; | |
195 | goto rcu_unlock; | |
196 | } | |
197 | shadow_node = caa_container_of(lookup_node, | |
198 | struct rcu_ja_shadow_node, ht_node); | |
199 | ret = pthread_mutex_lock(&shadow_node->lock); | |
200 | assert(!ret); | |
201 | if (cds_lfht_is_node_deleted(lookup_node)) { | |
202 | ret = pthread_mutex_unlock(&shadow_node->lock); | |
203 | assert(!ret); | |
204 | shadow_node = NULL; | |
205 | } | |
206 | rcu_unlock: | |
5eb692c0 | 207 | flavor->read_unlock(); |
d22c185b MD |
208 | return shadow_node; |
209 | } | |
210 | ||
25fde237 | 211 | __attribute__((visibility("protected"))) |
d22c185b MD |
212 | void rcuja_shadow_unlock(struct rcu_ja_shadow_node *shadow_node) |
213 | { | |
214 | int ret; | |
215 | ||
216 | ret = pthread_mutex_unlock(&shadow_node->lock); | |
217 | assert(!ret); | |
218 | } | |
219 | ||
220 | __attribute__((visibility("protected"))) | |
221 | int rcuja_shadow_set(struct cds_lfht *ht, | |
222 | struct rcu_ja_node *node) | |
223 | { | |
224 | struct rcu_ja_shadow_node *shadow_node; | |
225 | struct cds_lfht_node *ret_node; | |
5eb692c0 | 226 | const struct rcu_flavor_struct *flavor; |
d22c185b MD |
227 | |
228 | shadow_node = calloc(sizeof(*shadow_node), 1); | |
229 | if (!shadow_node) | |
230 | return -ENOMEM; | |
231 | ||
232 | shadow_node->node = node; | |
233 | pthread_mutex_init(&shadow_node->lock, NULL); | |
234 | ||
5eb692c0 MD |
235 | flavor = cds_lfht_rcu_flavor(ht); |
236 | flavor->read_lock(); | |
d22c185b MD |
237 | ret_node = cds_lfht_add_unique(ht, |
238 | hash_pointer(node, hash_seed), | |
239 | match_pointer, | |
240 | node, | |
241 | &shadow_node->ht_node); | |
5eb692c0 | 242 | flavor->read_unlock(); |
d22c185b MD |
243 | |
244 | if (ret_node != &shadow_node->ht_node) { | |
245 | free(shadow_node); | |
246 | return -EEXIST; | |
247 | } | |
248 | return 0; | |
249 | } | |
250 | ||
251 | static | |
25fde237 | 252 | void free_shadow_node_and_node(struct rcu_head *head) |
d22c185b MD |
253 | { |
254 | struct rcu_ja_shadow_node *shadow_node = | |
255 | caa_container_of(head, struct rcu_ja_shadow_node, head); | |
25fde237 | 256 | free(shadow_node->node); |
d22c185b MD |
257 | free(shadow_node); |
258 | } | |
259 | ||
260 | __attribute__((visibility("protected"))) | |
25fde237 | 261 | int rcuja_shadow_clear_and_free_node(struct cds_lfht *ht, |
d22c185b MD |
262 | struct rcu_ja_node *node) |
263 | { | |
264 | struct cds_lfht_iter iter; | |
265 | struct cds_lfht_node *lookup_node; | |
266 | struct rcu_ja_shadow_node *shadow_node; | |
5eb692c0 | 267 | const struct rcu_flavor_struct *flavor; |
d22c185b MD |
268 | int ret, lockret; |
269 | ||
5eb692c0 MD |
270 | flavor = cds_lfht_rcu_flavor(ht); |
271 | flavor->read_lock(); | |
d22c185b MD |
272 | cds_lfht_lookup(ht, hash_pointer(node, hash_seed), |
273 | match_pointer, node, &iter); | |
274 | lookup_node = cds_lfht_iter_get_node(&iter); | |
275 | if (!lookup_node) { | |
276 | ret = -ENOENT; | |
277 | goto rcu_unlock; | |
278 | } | |
279 | shadow_node = caa_container_of(lookup_node, | |
280 | struct rcu_ja_shadow_node, ht_node); | |
281 | lockret = pthread_mutex_lock(&shadow_node->lock); | |
282 | assert(!lockret); | |
283 | ||
284 | /* | |
285 | * Holding the mutex across deletion, and by also re-checking if | |
286 | * the node is deleted with mutex held at lookup ensure that we | |
287 | * don't let RCU JA use a node being removed. | |
288 | */ | |
289 | ret = cds_lfht_del(ht, lookup_node); | |
290 | if (!ret) { | |
5eb692c0 | 291 | flavor->update_call_rcu(&shadow_node->head, free_shadow_node_and_node); |
d22c185b MD |
292 | } |
293 | lockret = pthread_mutex_unlock(&shadow_node->lock); | |
294 | assert(!lockret); | |
295 | rcu_unlock: | |
5eb692c0 | 296 | flavor->read_unlock(); |
d22c185b MD |
297 | |
298 | return ret; | |
299 | } | |
300 | ||
195e72d3 | 301 | __attribute__((visibility("protected"))) |
5eb692c0 | 302 | struct cds_lfht *rcuja_create_ht(const struct rcu_flavor_struct *flavor) |
195e72d3 | 303 | { |
5eb692c0 | 304 | return _cds_lfht_new(1, 1, 0, |
195e72d3 | 305 | CDS_LFHT_AUTO_RESIZE | CDS_LFHT_ACCOUNTING, |
5eb692c0 | 306 | NULL, flavor, NULL); |
195e72d3 MD |
307 | } |
308 | ||
309 | __attribute__((visibility("protected"))) | |
310 | void rcuja_delete_ht(struct cds_lfht *ht) | |
311 | { | |
312 | int ret; | |
313 | ||
314 | ret = cds_lfht_destroy(ht, NULL); | |
315 | assert(!ret); | |
316 | } | |
d22c185b MD |
317 | |
318 | __attribute__((constructor)) | |
319 | void rcuja_ht_init(void) | |
320 | { | |
321 | hash_seed = (unsigned long) time(NULL); | |
322 | } |