hlist: implement cds_hlist_first_entry_rcu
[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 - 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 #include "bitfield.h"
37
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 cds_ja_shadow_node *shadow =
172 caa_container_of(node, struct cds_ja_shadow_node, ht_node);
173
174 return (key == shadow->node);
175 }
176
177 __attribute__((visibility("protected")))
178 struct cds_ja_shadow_node *rcuja_shadow_lookup_lock(struct cds_lfht *ht,
179 struct cds_ja_inode *node)
180 {
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;
185 int ret;
186
187 flavor = cds_lfht_rcu_flavor(ht);
188 flavor->read_lock();
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 cds_ja_shadow_node, ht_node);
199 dbg_printf("Lock %p\n", shadow_node->lock);
200 ret = pthread_mutex_lock(shadow_node->lock);
201 assert(!ret);
202 if (cds_lfht_is_node_deleted(lookup_node)) {
203 ret = pthread_mutex_unlock(shadow_node->lock);
204 assert(!ret);
205 shadow_node = NULL;
206 }
207 rcu_unlock:
208 flavor->read_unlock();
209 return shadow_node;
210 }
211
212 __attribute__((visibility("protected")))
213 void rcuja_shadow_unlock(struct cds_ja_shadow_node *shadow_node)
214 {
215 int ret;
216
217 dbg_printf("Unlock %p\n", shadow_node->lock);
218 ret = pthread_mutex_unlock(shadow_node->lock);
219 assert(!ret);
220 }
221
222 __attribute__((visibility("protected")))
223 struct cds_ja_shadow_node *rcuja_shadow_set(struct cds_lfht *ht,
224 struct cds_ja_inode *new_node,
225 struct cds_ja_shadow_node *inherit_from)
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 = new_node;
236 /*
237 * Lock can be inherited from previous node at this position.
238 */
239 if (inherit_from) {
240 shadow_node->lock = inherit_from->lock;
241 } else {
242 shadow_node->lock = calloc(sizeof(*shadow_node->lock), 1);
243 if (!shadow_node->lock) {
244 free(shadow_node);
245 return NULL;
246 }
247 pthread_mutex_init(shadow_node->lock, NULL);
248 }
249
250 flavor = cds_lfht_rcu_flavor(ht);
251 flavor->read_lock();
252 ret_node = cds_lfht_add_unique(ht,
253 hash_pointer(new_node, hash_seed),
254 match_pointer,
255 new_node,
256 &shadow_node->ht_node);
257 flavor->read_unlock();
258
259 if (ret_node != &shadow_node->ht_node) {
260 free(shadow_node);
261 return NULL;
262 }
263 return shadow_node;
264 }
265
266 static
267 void free_shadow_node(struct rcu_head *head)
268 {
269 struct cds_ja_shadow_node *shadow_node =
270 caa_container_of(head, struct cds_ja_shadow_node, head);
271 free(shadow_node);
272 }
273
274 static
275 void free_shadow_node_and_node(struct rcu_head *head)
276 {
277 struct cds_ja_shadow_node *shadow_node =
278 caa_container_of(head, struct cds_ja_shadow_node, head);
279 free(shadow_node->node);
280 free(shadow_node);
281 }
282
283 static
284 void free_shadow_node_and_lock(struct rcu_head *head)
285 {
286 struct cds_ja_shadow_node *shadow_node =
287 caa_container_of(head, struct cds_ja_shadow_node, head);
288 free(shadow_node->lock);
289 free(shadow_node);
290 }
291
292 static
293 void free_shadow_node_and_node_and_lock(struct rcu_head *head)
294 {
295 struct cds_ja_shadow_node *shadow_node =
296 caa_container_of(head, struct cds_ja_shadow_node, head);
297 assert(!shadow_node->is_root);
298 free(shadow_node->node);
299 free(shadow_node->lock);
300 free(shadow_node);
301 }
302
303 __attribute__((visibility("protected")))
304 int rcuja_shadow_clear(struct cds_lfht *ht,
305 struct cds_ja_inode *node,
306 struct cds_ja_shadow_node *shadow_node,
307 unsigned int flags)
308 {
309 struct cds_lfht_iter iter;
310 struct cds_lfht_node *lookup_node;
311 const struct rcu_flavor_struct *flavor;
312 int ret, lockret;
313 int lookup_shadow = 0;
314
315 flavor = cds_lfht_rcu_flavor(ht);
316 flavor->read_lock();
317
318 cds_lfht_lookup(ht, hash_pointer(node, hash_seed),
319 match_pointer, node, &iter);
320 lookup_node = cds_lfht_iter_get_node(&iter);
321 if (!lookup_node) {
322 ret = -ENOENT;
323 goto rcu_unlock;
324 }
325
326 if (!shadow_node) {
327 shadow_node = caa_container_of(lookup_node,
328 struct cds_ja_shadow_node, ht_node);
329 lockret = pthread_mutex_lock(shadow_node->lock);
330 assert(!lockret);
331 lookup_shadow = 1;
332 }
333
334 /*
335 * Holding the mutex across deletion, and by also re-checking if
336 * the node is deleted with mutex held at lookup ensure that we
337 * don't let RCU JA use a node being removed.
338 */
339 ret = cds_lfht_del(ht, lookup_node);
340 if (!ret) {
341 if ((flags & RCUJA_SHADOW_CLEAR_FREE_NODE)
342 && !shadow_node->is_root) {
343 if (flags & RCUJA_SHADOW_CLEAR_FREE_LOCK) {
344 flavor->update_call_rcu(&shadow_node->head,
345 free_shadow_node_and_node_and_lock);
346 } else {
347 flavor->update_call_rcu(&shadow_node->head,
348 free_shadow_node_and_node);
349 }
350 } else {
351 if (flags & RCUJA_SHADOW_CLEAR_FREE_LOCK) {
352 flavor->update_call_rcu(&shadow_node->head,
353 free_shadow_node_and_lock);
354 } else {
355 flavor->update_call_rcu(&shadow_node->head,
356 free_shadow_node);
357 }
358 }
359 }
360 if (lookup_shadow) {
361 lockret = pthread_mutex_unlock(shadow_node->lock);
362 assert(!lockret);
363 }
364 rcu_unlock:
365 flavor->read_unlock();
366
367 return ret;
368 }
369
370 /*
371 * Delete all shadow nodes and nodes from hash table, along with their
372 * associated lock.
373 */
374 __attribute__((visibility("protected")))
375 void rcuja_shadow_prune(struct cds_lfht *ht,
376 unsigned int flags)
377 {
378 const struct rcu_flavor_struct *flavor;
379 struct cds_ja_shadow_node *shadow_node;
380 struct cds_lfht_iter iter;
381 int ret, lockret;
382
383 flavor = cds_lfht_rcu_flavor(ht);
384 flavor->read_lock();
385 cds_lfht_for_each_entry(ht, &iter, shadow_node, ht_node) {
386 lockret = pthread_mutex_lock(shadow_node->lock);
387 assert(!lockret);
388
389 ret = cds_lfht_del(ht, &shadow_node->ht_node);
390 if (!ret) {
391 if ((flags & RCUJA_SHADOW_CLEAR_FREE_NODE)
392 && !shadow_node->is_root) {
393 if (flags & RCUJA_SHADOW_CLEAR_FREE_LOCK) {
394 flavor->update_call_rcu(&shadow_node->head,
395 free_shadow_node_and_node_and_lock);
396 } else {
397 flavor->update_call_rcu(&shadow_node->head,
398 free_shadow_node_and_node);
399 }
400 } else {
401 if (flags & RCUJA_SHADOW_CLEAR_FREE_LOCK) {
402 flavor->update_call_rcu(&shadow_node->head,
403 free_shadow_node_and_lock);
404 } else {
405 flavor->update_call_rcu(&shadow_node->head,
406 free_shadow_node);
407 }
408 }
409 }
410 lockret = pthread_mutex_unlock(shadow_node->lock);
411 assert(!lockret);
412 }
413 flavor->read_unlock();
414 }
415
416 __attribute__((visibility("protected")))
417 struct cds_lfht *rcuja_create_ht(const struct rcu_flavor_struct *flavor)
418 {
419 return _cds_lfht_new(1, 1, 0,
420 CDS_LFHT_AUTO_RESIZE | CDS_LFHT_ACCOUNTING,
421 NULL, flavor, NULL);
422 }
423
424 __attribute__((visibility("protected")))
425 int rcuja_delete_ht(struct cds_lfht *ht)
426 {
427 return cds_lfht_destroy(ht, NULL);
428 }
429
430 __attribute__((constructor))
431 void rcuja_ht_init(void)
432 {
433 hash_seed = (unsigned long) time(NULL);
434 }
This page took 0.053046 seconds and 5 git commands to generate.