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" | |
195e72d3 | 36 | |
d22c185b MD |
37 | static unsigned long hash_seed; |
38 | ||
39 | /* | |
40 | * Hash function | |
41 | * Source: http://burtleburtle.net/bob/c/lookup3.c | |
42 | * Originally Public Domain | |
43 | */ | |
44 | ||
45 | #define rot(x, k) (((x) << (k)) | ((x) >> (32 - (k)))) | |
46 | ||
47 | #define mix(a, b, c) \ | |
48 | do { \ | |
49 | a -= c; a ^= rot(c, 4); c += b; \ | |
50 | b -= a; b ^= rot(a, 6); a += c; \ | |
51 | c -= b; c ^= rot(b, 8); b += a; \ | |
52 | a -= c; a ^= rot(c, 16); c += b; \ | |
53 | b -= a; b ^= rot(a, 19); a += c; \ | |
54 | c -= b; c ^= rot(b, 4); b += a; \ | |
55 | } while (0) | |
56 | ||
57 | #define final(a, b, c) \ | |
58 | { \ | |
59 | c ^= b; c -= rot(b, 14); \ | |
60 | a ^= c; a -= rot(c, 11); \ | |
61 | b ^= a; b -= rot(a, 25); \ | |
62 | c ^= b; c -= rot(b, 16); \ | |
63 | a ^= c; a -= rot(c, 4);\ | |
64 | b ^= a; b -= rot(a, 14); \ | |
65 | c ^= b; c -= rot(b, 24); \ | |
66 | } | |
67 | ||
68 | static inline __attribute__((unused)) | |
69 | uint32_t hash_u32( | |
70 | const uint32_t *k, /* the key, an array of uint32_t values */ | |
71 | size_t length, /* the length of the key, in uint32_ts */ | |
72 | uint32_t initval) /* the previous hash, or an arbitrary value */ | |
73 | { | |
74 | uint32_t a, b, c; | |
75 | ||
76 | /* Set up the internal state */ | |
77 | a = b = c = 0xdeadbeef + (((uint32_t) length) << 2) + initval; | |
78 | ||
79 | /*----------------------------------------- handle most of the key */ | |
80 | while (length > 3) { | |
81 | a += k[0]; | |
82 | b += k[1]; | |
83 | c += k[2]; | |
84 | mix(a, b, c); | |
85 | length -= 3; | |
86 | k += 3; | |
87 | } | |
88 | ||
89 | /*----------------------------------- handle the last 3 uint32_t's */ | |
90 | switch (length) { /* all the case statements fall through */ | |
91 | case 3: c += k[2]; | |
92 | case 2: b += k[1]; | |
93 | case 1: a += k[0]; | |
94 | final(a, b, c); | |
95 | case 0: /* case 0: nothing left to add */ | |
96 | break; | |
97 | } | |
98 | /*---------------------------------------------- report the result */ | |
99 | return c; | |
100 | } | |
101 | ||
102 | static inline | |
103 | void hashword2( | |
104 | const uint32_t *k, /* the key, an array of uint32_t values */ | |
105 | size_t length, /* the length of the key, in uint32_ts */ | |
106 | uint32_t *pc, /* IN: seed OUT: primary hash value */ | |
107 | uint32_t *pb) /* IN: more seed OUT: secondary hash value */ | |
108 | { | |
109 | uint32_t a, b, c; | |
110 | ||
111 | /* Set up the internal state */ | |
112 | a = b = c = 0xdeadbeef + ((uint32_t) (length << 2)) + *pc; | |
113 | c += *pb; | |
114 | ||
115 | /*----------------------------------------- handle most of the key */ | |
116 | while (length > 3) { | |
117 | a += k[0]; | |
118 | b += k[1]; | |
119 | c += k[2]; | |
120 | mix(a, b, c); | |
121 | length -= 3; | |
122 | k += 3; | |
123 | } | |
124 | ||
125 | /*----------------------------------- handle the last 3 uint32_t's */ | |
126 | switch (length) { /* all the case statements fall through */ | |
127 | case 3: c += k[2]; | |
128 | case 2: b += k[1]; | |
129 | case 1: a += k[0]; | |
130 | final(a, b, c); | |
131 | case 0: /* case 0: nothing left to add */ | |
132 | break; | |
133 | } | |
134 | /*---------------------------------------------- report the result */ | |
135 | *pc = c; | |
136 | *pb = b; | |
137 | } | |
138 | ||
139 | #if (CAA_BITS_PER_LONG == 32) | |
140 | static | |
141 | unsigned long hash_pointer(const void *_key, unsigned long seed) | |
142 | { | |
143 | unsigned int key = (unsigned int) _key; | |
144 | ||
145 | return hash_u32(&key, 1, seed); | |
146 | } | |
147 | #else | |
148 | static | |
149 | unsigned long hash_pointer(const void *_key, unsigned long seed) | |
150 | { | |
151 | union { | |
152 | uint64_t v64; | |
153 | uint32_t v32[2]; | |
154 | } v; | |
155 | union { | |
156 | uint64_t v64; | |
157 | uint32_t v32[2]; | |
158 | } key; | |
159 | ||
160 | v.v64 = (uint64_t) seed; | |
161 | key.v64 = (uint64_t) _key; | |
162 | hashword2(key.v32, 2, &v.v32[0], &v.v32[1]); | |
163 | return v.v64; | |
164 | } | |
165 | #endif | |
166 | ||
167 | static | |
168 | int match_pointer(struct cds_lfht_node *node, const void *key) | |
169 | { | |
d96bfb0d MD |
170 | struct cds_ja_shadow_node *shadow = |
171 | caa_container_of(node, struct cds_ja_shadow_node, ht_node); | |
d22c185b | 172 | |
3d8fe307 | 173 | return (key == shadow->node_flag); |
d22c185b MD |
174 | } |
175 | ||
176 | __attribute__((visibility("protected"))) | |
d96bfb0d | 177 | struct cds_ja_shadow_node *rcuja_shadow_lookup_lock(struct cds_lfht *ht, |
3d8fe307 | 178 | struct cds_ja_inode_flag *node_flag) |
d22c185b MD |
179 | { |
180 | struct cds_lfht_iter iter; | |
181 | struct cds_lfht_node *lookup_node; | |
d96bfb0d | 182 | struct cds_ja_shadow_node *shadow_node; |
5eb692c0 | 183 | const struct rcu_flavor_struct *flavor; |
d22c185b MD |
184 | int ret; |
185 | ||
5eb692c0 MD |
186 | flavor = cds_lfht_rcu_flavor(ht); |
187 | flavor->read_lock(); | |
3d8fe307 MD |
188 | cds_lfht_lookup(ht, hash_pointer(node_flag, hash_seed), |
189 | match_pointer, node_flag, &iter); | |
d22c185b MD |
190 | |
191 | lookup_node = cds_lfht_iter_get_node(&iter); | |
192 | if (!lookup_node) { | |
193 | shadow_node = NULL; | |
194 | goto rcu_unlock; | |
195 | } | |
196 | shadow_node = caa_container_of(lookup_node, | |
d96bfb0d | 197 | struct cds_ja_shadow_node, ht_node); |
a2a7ff59 | 198 | dbg_printf("Lock %p\n", shadow_node->lock); |
e1db2db5 | 199 | ret = pthread_mutex_lock(shadow_node->lock); |
d22c185b MD |
200 | assert(!ret); |
201 | if (cds_lfht_is_node_deleted(lookup_node)) { | |
e1db2db5 | 202 | ret = pthread_mutex_unlock(shadow_node->lock); |
d22c185b MD |
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"))) |
d96bfb0d | 212 | void rcuja_shadow_unlock(struct cds_ja_shadow_node *shadow_node) |
d22c185b MD |
213 | { |
214 | int ret; | |
215 | ||
a2a7ff59 | 216 | dbg_printf("Unlock %p\n", shadow_node->lock); |
e1db2db5 | 217 | ret = pthread_mutex_unlock(shadow_node->lock); |
d22c185b MD |
218 | assert(!ret); |
219 | } | |
220 | ||
221 | __attribute__((visibility("protected"))) | |
f07b240f | 222 | struct cds_ja_shadow_node *rcuja_shadow_set(struct cds_lfht *ht, |
3d8fe307 MD |
223 | struct cds_ja_inode_flag *new_node_flag, |
224 | struct cds_ja_shadow_node *inherit_from, | |
48cbe001 | 225 | struct cds_ja *ja, int level) |
d22c185b | 226 | { |
d96bfb0d | 227 | struct cds_ja_shadow_node *shadow_node; |
d22c185b | 228 | struct cds_lfht_node *ret_node; |
5eb692c0 | 229 | const struct rcu_flavor_struct *flavor; |
d22c185b MD |
230 | |
231 | shadow_node = calloc(sizeof(*shadow_node), 1); | |
232 | if (!shadow_node) | |
f07b240f | 233 | return NULL; |
d22c185b | 234 | |
3d8fe307 MD |
235 | shadow_node->node_flag = new_node_flag; |
236 | shadow_node->ja = ja; | |
e1db2db5 MD |
237 | /* |
238 | * Lock can be inherited from previous node at this position. | |
239 | */ | |
240 | if (inherit_from) { | |
241 | shadow_node->lock = inherit_from->lock; | |
48cbe001 | 242 | shadow_node->level = inherit_from->level; |
e1db2db5 MD |
243 | } else { |
244 | shadow_node->lock = calloc(sizeof(*shadow_node->lock), 1); | |
245 | if (!shadow_node->lock) { | |
246 | free(shadow_node); | |
f07b240f | 247 | return NULL; |
e1db2db5 MD |
248 | } |
249 | pthread_mutex_init(shadow_node->lock, NULL); | |
48cbe001 | 250 | shadow_node->level = level; |
e1db2db5 | 251 | } |
d22c185b | 252 | |
5eb692c0 MD |
253 | flavor = cds_lfht_rcu_flavor(ht); |
254 | flavor->read_lock(); | |
d22c185b | 255 | ret_node = cds_lfht_add_unique(ht, |
3d8fe307 | 256 | hash_pointer(new_node_flag, hash_seed), |
d22c185b | 257 | match_pointer, |
3d8fe307 | 258 | new_node_flag, |
d22c185b | 259 | &shadow_node->ht_node); |
5eb692c0 | 260 | flavor->read_unlock(); |
d22c185b MD |
261 | |
262 | if (ret_node != &shadow_node->ht_node) { | |
263 | free(shadow_node); | |
f07b240f | 264 | return NULL; |
d22c185b | 265 | } |
f07b240f | 266 | return shadow_node; |
d22c185b MD |
267 | } |
268 | ||
a2a7ff59 MD |
269 | static |
270 | void free_shadow_node(struct rcu_head *head) | |
271 | { | |
272 | struct cds_ja_shadow_node *shadow_node = | |
273 | caa_container_of(head, struct cds_ja_shadow_node, head); | |
274 | free(shadow_node); | |
275 | } | |
276 | ||
d22c185b | 277 | static |
25fde237 | 278 | void free_shadow_node_and_node(struct rcu_head *head) |
d22c185b | 279 | { |
d96bfb0d MD |
280 | struct cds_ja_shadow_node *shadow_node = |
281 | caa_container_of(head, struct cds_ja_shadow_node, head); | |
354981c2 | 282 | free_cds_ja_node(shadow_node->ja, ja_node_ptr(shadow_node->node_flag)); |
d22c185b MD |
283 | free(shadow_node); |
284 | } | |
285 | ||
a2a7ff59 MD |
286 | static |
287 | void free_shadow_node_and_lock(struct rcu_head *head) | |
288 | { | |
289 | struct cds_ja_shadow_node *shadow_node = | |
290 | caa_container_of(head, struct cds_ja_shadow_node, head); | |
291 | free(shadow_node->lock); | |
292 | free(shadow_node); | |
293 | } | |
294 | ||
e1db2db5 MD |
295 | static |
296 | void free_shadow_node_and_node_and_lock(struct rcu_head *head) | |
297 | { | |
d96bfb0d MD |
298 | struct cds_ja_shadow_node *shadow_node = |
299 | caa_container_of(head, struct cds_ja_shadow_node, head); | |
3d8fe307 | 300 | assert(shadow_node->level); |
354981c2 | 301 | free_cds_ja_node(shadow_node->ja, ja_node_ptr(shadow_node->node_flag)); |
e1db2db5 MD |
302 | free(shadow_node->lock); |
303 | free(shadow_node); | |
304 | } | |
305 | ||
d22c185b | 306 | __attribute__((visibility("protected"))) |
e1db2db5 | 307 | int rcuja_shadow_clear(struct cds_lfht *ht, |
3d8fe307 | 308 | struct cds_ja_inode_flag *node_flag, |
a2a7ff59 | 309 | struct cds_ja_shadow_node *shadow_node, |
e1db2db5 | 310 | unsigned int flags) |
d22c185b MD |
311 | { |
312 | struct cds_lfht_iter iter; | |
313 | struct cds_lfht_node *lookup_node; | |
5eb692c0 | 314 | const struct rcu_flavor_struct *flavor; |
d22c185b | 315 | int ret, lockret; |
a2a7ff59 | 316 | int lookup_shadow = 0; |
d22c185b | 317 | |
5eb692c0 MD |
318 | flavor = cds_lfht_rcu_flavor(ht); |
319 | flavor->read_lock(); | |
a2a7ff59 | 320 | |
3d8fe307 MD |
321 | cds_lfht_lookup(ht, hash_pointer(node_flag, hash_seed), |
322 | match_pointer, node_flag, &iter); | |
d22c185b MD |
323 | lookup_node = cds_lfht_iter_get_node(&iter); |
324 | if (!lookup_node) { | |
325 | ret = -ENOENT; | |
326 | goto rcu_unlock; | |
327 | } | |
a2a7ff59 MD |
328 | |
329 | if (!shadow_node) { | |
330 | shadow_node = caa_container_of(lookup_node, | |
331 | struct cds_ja_shadow_node, ht_node); | |
332 | lockret = pthread_mutex_lock(shadow_node->lock); | |
333 | assert(!lockret); | |
334 | lookup_shadow = 1; | |
335 | } | |
d22c185b MD |
336 | |
337 | /* | |
338 | * Holding the mutex across deletion, and by also re-checking if | |
339 | * the node is deleted with mutex held at lookup ensure that we | |
340 | * don't let RCU JA use a node being removed. | |
341 | */ | |
342 | ret = cds_lfht_del(ht, lookup_node); | |
dc0e9798 MD |
343 | if (ret) |
344 | goto unlock; | |
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); | |
e1db2db5 | 350 | } else { |
dc0e9798 MD |
351 | flavor->update_call_rcu(&shadow_node->head, |
352 | free_shadow_node_and_node); | |
353 | } | |
354 | } else { | |
355 | if (flags & RCUJA_SHADOW_CLEAR_FREE_LOCK) { | |
356 | flavor->update_call_rcu(&shadow_node->head, | |
357 | free_shadow_node_and_lock); | |
358 | } else { | |
359 | flavor->update_call_rcu(&shadow_node->head, | |
360 | free_shadow_node); | |
e1db2db5 | 361 | } |
d22c185b | 362 | } |
dc0e9798 | 363 | unlock: |
a2a7ff59 MD |
364 | if (lookup_shadow) { |
365 | lockret = pthread_mutex_unlock(shadow_node->lock); | |
366 | assert(!lockret); | |
367 | } | |
d22c185b | 368 | rcu_unlock: |
5eb692c0 | 369 | flavor->read_unlock(); |
d22c185b MD |
370 | |
371 | return ret; | |
372 | } | |
373 | ||
be9a7474 MD |
374 | /* |
375 | * Delete all shadow nodes and nodes from hash table, along with their | |
376 | * associated lock. | |
377 | */ | |
378 | __attribute__((visibility("protected"))) | |
379 | void rcuja_shadow_prune(struct cds_lfht *ht, | |
3d8fe307 | 380 | unsigned int flags, |
dc0e9798 | 381 | void (*free_node_cb)(struct cds_ja_node *node)) |
be9a7474 MD |
382 | { |
383 | const struct rcu_flavor_struct *flavor; | |
384 | struct cds_ja_shadow_node *shadow_node; | |
385 | struct cds_lfht_iter iter; | |
386 | int ret, lockret; | |
387 | ||
388 | flavor = cds_lfht_rcu_flavor(ht); | |
dc0e9798 MD |
389 | /* |
390 | * Read-side lock is needed to ensure hash table node existence | |
391 | * vs concurrent resize. | |
392 | */ | |
be9a7474 MD |
393 | flavor->read_lock(); |
394 | cds_lfht_for_each_entry(ht, &iter, shadow_node, ht_node) { | |
395 | lockret = pthread_mutex_lock(shadow_node->lock); | |
396 | assert(!lockret); | |
397 | ||
398 | ret = cds_lfht_del(ht, &shadow_node->ht_node); | |
dc0e9798 MD |
399 | if (ret) |
400 | goto unlock; | |
401 | if ((flags & RCUJA_SHADOW_CLEAR_FREE_NODE) | |
402 | && shadow_node->level) { | |
403 | if (shadow_node->level == shadow_node->ja->tree_depth - 1) { | |
404 | rcuja_free_all_children(shadow_node, | |
405 | shadow_node->node_flag, | |
406 | free_node_cb); | |
407 | } | |
408 | if (flags & RCUJA_SHADOW_CLEAR_FREE_LOCK) { | |
409 | flavor->update_call_rcu(&shadow_node->head, | |
410 | free_shadow_node_and_node_and_lock); | |
411 | } else { | |
412 | flavor->update_call_rcu(&shadow_node->head, | |
413 | free_shadow_node_and_node); | |
414 | } | |
415 | } else { | |
416 | if (flags & RCUJA_SHADOW_CLEAR_FREE_LOCK) { | |
417 | flavor->update_call_rcu(&shadow_node->head, | |
418 | free_shadow_node_and_lock); | |
582a6ade | 419 | } else { |
dc0e9798 MD |
420 | flavor->update_call_rcu(&shadow_node->head, |
421 | free_shadow_node); | |
582a6ade | 422 | } |
be9a7474 | 423 | } |
dc0e9798 | 424 | unlock: |
be9a7474 MD |
425 | lockret = pthread_mutex_unlock(shadow_node->lock); |
426 | assert(!lockret); | |
427 | } | |
428 | flavor->read_unlock(); | |
429 | } | |
430 | ||
195e72d3 | 431 | __attribute__((visibility("protected"))) |
5eb692c0 | 432 | struct cds_lfht *rcuja_create_ht(const struct rcu_flavor_struct *flavor) |
195e72d3 | 433 | { |
5eb692c0 | 434 | return _cds_lfht_new(1, 1, 0, |
195e72d3 | 435 | CDS_LFHT_AUTO_RESIZE | CDS_LFHT_ACCOUNTING, |
5eb692c0 | 436 | NULL, flavor, NULL); |
195e72d3 MD |
437 | } |
438 | ||
439 | __attribute__((visibility("protected"))) | |
be9a7474 | 440 | int rcuja_delete_ht(struct cds_lfht *ht) |
195e72d3 | 441 | { |
be9a7474 | 442 | return cds_lfht_destroy(ht, NULL); |
195e72d3 | 443 | } |
d22c185b MD |
444 | |
445 | __attribute__((constructor)) | |
446 | void rcuja_ht_init(void) | |
447 | { | |
448 | hash_seed = (unsigned long) time(NULL); | |
449 | } |