473aaa94373f981b835bd64bcd2212fbb0088b70
[userspace-rcu.git] / rcuja / rcuja-shadow-nodes.c
1 /*
2 * rcuja/rcuja-hashtable.c
3 *
4 * Userspace RCU library - RCU Judy Array Shadow Node Hash Table
5 *
6 * Copyright 2012-2013 - 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>
27 #include <urcu/rcuja.h>
28 #include <urcu/compiler.h>
29 #include <urcu/arch.h>
30 #include <assert.h>
31 #include <urcu-pointer.h>
32 #include <stdlib.h>
33 #include <time.h>
34
35 #include "rcuja-internal.h"
36
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 {
170 struct cds_ja_shadow_node *shadow =
171 caa_container_of(node, struct cds_ja_shadow_node, ht_node);
172
173 return (key == shadow->node_flag);
174 }
175
176 __attribute__((visibility("protected")))
177 struct cds_ja_shadow_node *rcuja_shadow_lookup_lock(struct cds_lfht *ht,
178 struct cds_ja_inode_flag *node_flag)
179 {
180 struct cds_lfht_iter iter;
181 struct cds_lfht_node *lookup_node;
182 struct cds_ja_shadow_node *shadow_node;
183 const struct rcu_flavor_struct *flavor;
184 int ret;
185
186 flavor = cds_lfht_rcu_flavor(ht);
187 flavor->read_lock();
188 cds_lfht_lookup(ht, hash_pointer(node_flag, hash_seed),
189 match_pointer, node_flag, &iter);
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,
197 struct cds_ja_shadow_node, ht_node);
198 dbg_printf("Lock %p\n", shadow_node->lock);
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:
207 flavor->read_unlock();
208 return shadow_node;
209 }
210
211 __attribute__((visibility("protected")))
212 void rcuja_shadow_unlock(struct cds_ja_shadow_node *shadow_node)
213 {
214 int ret;
215
216 dbg_printf("Unlock %p\n", shadow_node->lock);
217 ret = pthread_mutex_unlock(shadow_node->lock);
218 assert(!ret);
219 }
220
221 __attribute__((visibility("protected")))
222 struct cds_ja_shadow_node *rcuja_shadow_set(struct cds_lfht *ht,
223 struct cds_ja_inode_flag *new_node_flag,
224 struct cds_ja_shadow_node *inherit_from,
225 struct cds_ja *ja, int level)
226 {
227 struct cds_ja_shadow_node *shadow_node;
228 struct cds_lfht_node *ret_node;
229 const struct rcu_flavor_struct *flavor;
230
231 shadow_node = calloc(sizeof(*shadow_node), 1);
232 if (!shadow_node)
233 return NULL;
234
235 shadow_node->node_flag = new_node_flag;
236 shadow_node->ja = ja;
237 /*
238 * Lock can be inherited from previous node at this position.
239 */
240 if (inherit_from) {
241 shadow_node->lock = inherit_from->lock;
242 shadow_node->level = inherit_from->level;
243 } else {
244 shadow_node->lock = calloc(sizeof(*shadow_node->lock), 1);
245 if (!shadow_node->lock) {
246 free(shadow_node);
247 return NULL;
248 }
249 pthread_mutex_init(shadow_node->lock, NULL);
250 shadow_node->level = level;
251 }
252
253 flavor = cds_lfht_rcu_flavor(ht);
254 flavor->read_lock();
255 ret_node = cds_lfht_add_unique(ht,
256 hash_pointer(new_node_flag, hash_seed),
257 match_pointer,
258 new_node_flag,
259 &shadow_node->ht_node);
260 flavor->read_unlock();
261
262 if (ret_node != &shadow_node->ht_node) {
263 free(shadow_node);
264 return NULL;
265 }
266 return shadow_node;
267 }
268
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
277 static
278 void free_shadow_node_and_node(struct rcu_head *head)
279 {
280 struct cds_ja_shadow_node *shadow_node =
281 caa_container_of(head, struct cds_ja_shadow_node, head);
282 free_cds_ja_node(shadow_node->ja, ja_node_ptr(shadow_node->node_flag));
283 free(shadow_node);
284 }
285
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
295 static
296 void free_shadow_node_and_node_and_lock(struct rcu_head *head)
297 {
298 struct cds_ja_shadow_node *shadow_node =
299 caa_container_of(head, struct cds_ja_shadow_node, head);
300 assert(shadow_node->level);
301 free_cds_ja_node(shadow_node->ja, ja_node_ptr(shadow_node->node_flag));
302 free(shadow_node->lock);
303 free(shadow_node);
304 }
305
306 __attribute__((visibility("protected")))
307 int rcuja_shadow_clear(struct cds_lfht *ht,
308 struct cds_ja_inode_flag *node_flag,
309 struct cds_ja_shadow_node *shadow_node,
310 unsigned int flags)
311 {
312 struct cds_lfht_iter iter;
313 struct cds_lfht_node *lookup_node;
314 const struct rcu_flavor_struct *flavor;
315 int ret, lockret;
316 int lookup_shadow = 0;
317
318 flavor = cds_lfht_rcu_flavor(ht);
319 flavor->read_lock();
320
321 cds_lfht_lookup(ht, hash_pointer(node_flag, hash_seed),
322 match_pointer, node_flag, &iter);
323 lookup_node = cds_lfht_iter_get_node(&iter);
324 if (!lookup_node) {
325 ret = -ENOENT;
326 goto rcu_unlock;
327 }
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 }
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);
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);
350 } else {
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);
361 }
362 }
363 unlock:
364 if (lookup_shadow) {
365 lockret = pthread_mutex_unlock(shadow_node->lock);
366 assert(!lockret);
367 }
368 rcu_unlock:
369 flavor->read_unlock();
370
371 return ret;
372 }
373
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,
380 unsigned int flags)
381 {
382 const struct rcu_flavor_struct *flavor;
383 struct cds_ja_shadow_node *shadow_node;
384 struct cds_lfht_iter iter;
385 int ret, lockret;
386
387 flavor = cds_lfht_rcu_flavor(ht);
388 /*
389 * Read-side lock is needed to ensure hash table node existence
390 * vs concurrent resize.
391 */
392 flavor->read_lock();
393 cds_lfht_for_each_entry(ht, &iter, shadow_node, ht_node) {
394 lockret = pthread_mutex_lock(shadow_node->lock);
395 assert(!lockret);
396
397 ret = cds_lfht_del(ht, &shadow_node->ht_node);
398 if (ret)
399 goto unlock;
400 if ((flags & RCUJA_SHADOW_CLEAR_FREE_NODE)
401 && shadow_node->level) {
402 if (flags & RCUJA_SHADOW_CLEAR_FREE_LOCK) {
403 flavor->update_call_rcu(&shadow_node->head,
404 free_shadow_node_and_node_and_lock);
405 } else {
406 flavor->update_call_rcu(&shadow_node->head,
407 free_shadow_node_and_node);
408 }
409 } else {
410 if (flags & RCUJA_SHADOW_CLEAR_FREE_LOCK) {
411 flavor->update_call_rcu(&shadow_node->head,
412 free_shadow_node_and_lock);
413 } else {
414 flavor->update_call_rcu(&shadow_node->head,
415 free_shadow_node);
416 }
417 }
418 unlock:
419 lockret = pthread_mutex_unlock(shadow_node->lock);
420 assert(!lockret);
421 }
422 flavor->read_unlock();
423 }
424
425 __attribute__((visibility("protected")))
426 struct cds_lfht *rcuja_create_ht(const struct rcu_flavor_struct *flavor)
427 {
428 return _cds_lfht_new(1, 1, 0,
429 CDS_LFHT_AUTO_RESIZE | CDS_LFHT_ACCOUNTING,
430 NULL, flavor, NULL);
431 }
432
433 __attribute__((visibility("protected")))
434 int rcuja_delete_ht(struct cds_lfht *ht)
435 {
436 return cds_lfht_destroy(ht, NULL);
437 }
438
439 __attribute__((constructor))
440 void rcuja_ht_init(void)
441 {
442 hash_seed = (unsigned long) time(NULL);
443 }
This page took 0.03798 seconds and 4 git commands to generate.