Bug Summary

File:obj-scan-build/../kern/rdxtree.c
Location:line 516, column 33
Description:Assigned value is garbage or undefined

Annotated Source Code

1/*
2 * Copyright (c) 2011-2015 Richard Braun.
3 * All rights reserved.
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
7 * are met:
8 * 1. Redistributions of source code must retain the above copyright
9 * notice, this list of conditions and the following disclaimer.
10 * 2. Redistributions in binary form must reproduce the above copyright
11 * notice, this list of conditions and the following disclaimer in the
12 * documentation and/or other materials provided with the distribution.
13 *
14 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
15 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
16 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
17 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
18 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
19 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
20 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
21 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
22 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
23 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
24 *
25 *
26 * Upstream site with license notes :
27 * http://git.sceen.net/rbraun/librbraun.git/
28 */
29
30#include <kern/assert.h>
31#include <kern/slab.h>
32#include <mach/kern_return.h>
33#include <stddef.h>
34#include <string.h>
35
36#include "macros.h"
37#include "rdxtree.h"
38#include "rdxtree_i.h"
39
40/* XXX */
41#define CHAR_BIT8U 8U
42#define ERR_SUCCESS0 KERN_SUCCESS0
43#define ERR_BUSY4 KERN_INVALID_ARGUMENT4
44#define ERR_NOMEM6 KERN_RESOURCE_SHORTAGE6
45
46/*
47 * Mask applied on an entry to obtain its address.
48 */
49#define RDXTREE_ENTRY_ADDR_MASK(~0x3UL) (~0x3UL)
50
51/*
52 * Global properties used to shape radix trees.
53 */
54#define RDXTREE_RADIX6 6
55#define RDXTREE_RADIX_SIZE(1UL << 6) (1UL << RDXTREE_RADIX6)
56#define RDXTREE_RADIX_MASK((1UL << 6) - 1) (RDXTREE_RADIX_SIZE(1UL << 6) - 1)
57
58#if RDXTREE_RADIX6 < 6
59typedef unsigned long rdxtree_bm_t;
60#define rdxtree_ffs(x)__builtin_ffsll(x) __builtin_ffsl(x)
61#elif RDXTREE_RADIX6 == 6 /* RDXTREE_RADIX < 6 */
62typedef unsigned long long rdxtree_bm_t;
63#define rdxtree_ffs(x)__builtin_ffsll(x) __builtin_ffsll(x)
64#else /* RDXTREE_RADIX < 6 */
65#error "radix too high"
66#endif /* RDXTREE_RADIX < 6 */
67
68/*
69 * Allocation bitmap size in bits.
70 */
71#define RDXTREE_BM_SIZE(sizeof(rdxtree_bm_t) * 8U) (sizeof(rdxtree_bm_t) * CHAR_BIT8U)
72
73/*
74 * Empty/full allocation bitmap words.
75 */
76#define RDXTREE_BM_EMPTY((rdxtree_bm_t)0) ((rdxtree_bm_t)0)
77#define RDXTREE_BM_FULL((~(rdxtree_bm_t)0) >> ((sizeof(rdxtree_bm_t) * 8U) - (
1UL << 6))) \
78 ((~(rdxtree_bm_t)0) >> (RDXTREE_BM_SIZE(sizeof(rdxtree_bm_t) * 8U) - RDXTREE_RADIX_SIZE(1UL << 6)))
79
80/*
81 * These macros can be replaced by actual functions in an environment
82 * that provides lockless synchronization such as RCU.
83 */
84#define llsync_assign_ptr(ptr, value)((ptr) = (value)) ((ptr) = (value))
85#define llsync_read_ptr(ptr)(ptr) (ptr)
86
87/*
88 * Radix tree node.
89 *
90 * The height of a tree is the number of nodes to traverse until stored
91 * pointers are reached. A height of 0 means the entries of a node (or the
92 * tree root) directly point to stored pointers.
93 *
94 * The index is valid if and only if the parent isn't NULL.
95 *
96 * Concerning the allocation bitmap, a bit is set when the node it denotes,
97 * or one of its children, can be used to allocate an entry. Conversely, a bit
98 * is clear when the matching node and all of its children have no free entry.
99 *
100 * In order to support safe lockless lookups, in particular during a resize,
101 * each node includes the height of its subtree, which is invariant during
102 * the entire node lifetime. Since the tree height does vary, it can't be
103 * used to determine whether the tree root is a node or a stored pointer.
104 * This implementation assumes that all nodes and stored pointers are at least
105 * 4-byte aligned, and uses the least significant bit of entries to indicate
106 * the pointer type. This bit is set for internal nodes, and clear for stored
107 * pointers so that they can be accessed from slots without conversion.
108 */
109struct rdxtree_node {
110 struct rdxtree_node *parent;
111 unsigned int index;
112 unsigned int height;
113 unsigned int nr_entries;
114 rdxtree_bm_t alloc_bm;
115 void *entries[RDXTREE_RADIX_SIZE(1UL << 6)];
116};
117
118/*
119 * We allocate nodes using the slab allocator.
120 */
121static struct kmem_cache rdxtree_node_cache;
122
123void
124rdxtree_cache_init(void)
125{
126 kmem_cache_init(&rdxtree_node_cache, "rdxtree_node",
127 sizeof(struct rdxtree_node), 0, NULL((void *) 0), NULL((void *) 0), NULL((void *) 0), 0);
128}
129
130#ifdef RDXTREE_ENABLE_NODE_CREATION_FAILURES
131unsigned int rdxtree_fail_node_creation_threshold;
132unsigned int rdxtree_nr_node_creations;
133#endif /* RDXTREE_ENABLE_NODE_CREATION_FAILURES */
134
135static inline int
136rdxtree_check_alignment(const void *ptr)
137{
138 return ((unsigned long)ptr & ~RDXTREE_ENTRY_ADDR_MASK(~0x3UL)) == 0;
139}
140
141static inline void *
142rdxtree_entry_addr(void *entry)
143{
144 return (void *)((unsigned long)entry & RDXTREE_ENTRY_ADDR_MASK(~0x3UL));
145}
146
147static inline int
148rdxtree_entry_is_node(const void *entry)
149{
150 return ((unsigned long)entry & 1) != 0;
151}
152
153static inline void *
154rdxtree_node_to_entry(struct rdxtree_node *node)
155{
156 return (void *)((unsigned long)node | 1);
157}
158
159static int
160rdxtree_node_create(struct rdxtree_node **nodep, unsigned int height)
161{
162 struct rdxtree_node *node;
163
164#ifdef RDXTREE_ENABLE_NODE_CREATION_FAILURES
165 if (rdxtree_fail_node_creation_threshold != 0) {
166 rdxtree_nr_node_creations++;
167
168 if (rdxtree_nr_node_creations == rdxtree_fail_node_creation_threshold)
169 return ERR_NOMEM6;
170 }
171#endif /* RDXTREE_ENABLE_NODE_CREATION_FAILURES */
172
173 node = (struct rdxtree_node *) kmem_cache_alloc(&rdxtree_node_cache);
174
175 if (node == NULL((void *) 0))
176 return ERR_NOMEM6;
177
178 assert(rdxtree_check_alignment(node))((rdxtree_check_alignment(node)) ? (void) (0) : Assert ("rdxtree_check_alignment(node)"
, "../kern/rdxtree.c", 178));
179 node->parent = NULL((void *) 0);
180 node->height = height;
181 node->nr_entries = 0;
182 node->alloc_bm = RDXTREE_BM_FULL((~(rdxtree_bm_t)0) >> ((sizeof(rdxtree_bm_t) * 8U) - (
1UL << 6)));
183 memset(node->entries, 0, sizeof(node->entries));
184 *nodep = node;
185 return 0;
186}
187
188static void
189rdxtree_node_schedule_destruction(struct rdxtree_node *node)
190{
191 /*
192 * This function is intended to use the appropriate interface to defer
193 * destruction until all read-side references are dropped in an
194 * environment that provides lockless synchronization.
195 *
196 * Otherwise, it simply "schedules" destruction immediately.
197 */
198 kmem_cache_free(&rdxtree_node_cache, (vm_offset_t) node);
199}
200
201static inline void
202rdxtree_node_link(struct rdxtree_node *node, struct rdxtree_node *parent,
203 unsigned int index)
204{
205 node->parent = parent;
206 node->index = index;
207}
208
209static inline void
210rdxtree_node_unlink(struct rdxtree_node *node)
211{
212 assert(node->parent != NULL)((node->parent != ((void *) 0)) ? (void) (0) : Assert ("node->parent != NULL"
, "../kern/rdxtree.c", 212));
213 node->parent = NULL((void *) 0);
214}
215
216static inline int
217rdxtree_node_full(struct rdxtree_node *node)
218{
219 return (node->nr_entries == ARRAY_SIZE(node->entries)(sizeof(node->entries) / sizeof((node->entries)[0])));
220}
221
222static inline int
223rdxtree_node_empty(struct rdxtree_node *node)
224{
225 return (node->nr_entries == 0);
226}
227
228static inline void
229rdxtree_node_insert(struct rdxtree_node *node, unsigned int index,
230 void *entry)
231{
232 assert(index < ARRAY_SIZE(node->entries))((index < (sizeof(node->entries) / sizeof((node->entries
)[0]))) ? (void) (0) : Assert ("index < ARRAY_SIZE(node->entries)"
, "../kern/rdxtree.c", 232));
233 assert(node->entries[index] == NULL)((node->entries[index] == ((void *) 0)) ? (void) (0) : Assert
("node->entries[index] == NULL", "../kern/rdxtree.c", 233
));
234
235 node->nr_entries++;
236 llsync_assign_ptr(node->entries[index], entry)((node->entries[index]) = (entry));
237}
238
239static inline void
240rdxtree_node_insert_node(struct rdxtree_node *node, unsigned int index,
241 struct rdxtree_node *child)
242{
243 rdxtree_node_insert(node, index, rdxtree_node_to_entry(child));
244}
245
246static inline void
247rdxtree_node_remove(struct rdxtree_node *node, unsigned int index)
248{
249 assert(index < ARRAY_SIZE(node->entries))((index < (sizeof(node->entries) / sizeof((node->entries
)[0]))) ? (void) (0) : Assert ("index < ARRAY_SIZE(node->entries)"
, "../kern/rdxtree.c", 249));
250 assert(node->entries[index] != NULL)((node->entries[index] != ((void *) 0)) ? (void) (0) : Assert
("node->entries[index] != NULL", "../kern/rdxtree.c", 250
));
251
252 node->nr_entries--;
253 llsync_assign_ptr(node->entries[index], NULL)((node->entries[index]) = (((void *) 0)));
254}
255
256static inline void *
257rdxtree_node_find(struct rdxtree_node *node, unsigned int *indexp)
258{
259 unsigned int index;
260 void *ptr;
261
262 index = *indexp;
263
264 while (index < ARRAY_SIZE(node->entries)(sizeof(node->entries) / sizeof((node->entries)[0]))) {
265 ptr = rdxtree_entry_addr(llsync_read_ptr(node->entries[index])(node->entries[index]));
266
267 if (ptr != NULL((void *) 0)) {
268 *indexp = index;
269 return ptr;
270 }
271
272 index++;
273 }
274
275 return NULL((void *) 0);
276}
277
278static inline void
279rdxtree_node_bm_set(struct rdxtree_node *node, unsigned int index)
280{
281 node->alloc_bm |= (rdxtree_bm_t)1 << index;
282}
283
284static inline void
285rdxtree_node_bm_clear(struct rdxtree_node *node, unsigned int index)
286{
287 node->alloc_bm &= ~((rdxtree_bm_t)1 << index);
288}
289
290static inline int
291rdxtree_node_bm_is_set(struct rdxtree_node *node, unsigned int index)
292{
293 return (node->alloc_bm & ((rdxtree_bm_t)1 << index));
294}
295
296static inline int
297rdxtree_node_bm_empty(struct rdxtree_node *node)
298{
299 return (node->alloc_bm == RDXTREE_BM_EMPTY((rdxtree_bm_t)0));
300}
301
302static inline unsigned int
303rdxtree_node_bm_first(struct rdxtree_node *node)
304{
305 return rdxtree_ffs(node->alloc_bm)__builtin_ffsll(node->alloc_bm) - 1;
306}
307
308static inline rdxtree_key_t
309rdxtree_max_key(unsigned int height)
310{
311 size_t shift;
312
313 shift = RDXTREE_RADIX6 * height;
314
315 if (likely(shift < (sizeof(rdxtree_key_t) * CHAR_BIT))__builtin_expect(!!(shift < (sizeof(rdxtree_key_t) * 8U)),
1))
316 return ((rdxtree_key_t)1 << shift) - 1;
317 else
318 return ~((rdxtree_key_t)0);
319}
320
321static void
322rdxtree_shrink(struct rdxtree *tree)
323{
324 struct rdxtree_node *node;
325 void *entry;
326
327 while (tree->height > 0) {
328 node = rdxtree_entry_addr(tree->root);
329
330 if (node->nr_entries != 1)
331 break;
332
333 entry = node->entries[0];
334
335 if (entry == NULL((void *) 0))
336 break;
337
338 tree->height--;
339
340 if (tree->height > 0)
341 rdxtree_node_unlink(rdxtree_entry_addr(entry));
342
343 llsync_assign_ptr(tree->root, entry)((tree->root) = (entry));
344 rdxtree_node_schedule_destruction(node);
345 }
346}
347
348static int
349rdxtree_grow(struct rdxtree *tree, rdxtree_key_t key)
350{
351 struct rdxtree_node *root, *node;
352 unsigned int new_height;
353 int error;
354
355 new_height = tree->height + 1;
356
357 while (key > rdxtree_max_key(new_height))
358 new_height++;
359
360 if (tree->root == NULL((void *) 0)) {
361 tree->height = new_height;
362 return ERR_SUCCESS0;
363 }
364
365 root = rdxtree_entry_addr(tree->root);
366
367 do {
368 error = rdxtree_node_create(&node, tree->height);
369
370 if (error) {
371 rdxtree_shrink(tree);
372 return error;
373 }
374
375 if (tree->height == 0)
376 rdxtree_node_bm_clear(node, 0);
377 else {
378 rdxtree_node_link(root, node, 0);
379
380 if (rdxtree_node_bm_empty(root))
381 rdxtree_node_bm_clear(node, 0);
382 }
383
384 rdxtree_node_insert(node, 0, tree->root);
385 tree->height++;
386 llsync_assign_ptr(tree->root, rdxtree_node_to_entry(node))((tree->root) = (rdxtree_node_to_entry(node)));
387 root = node;
388 } while (new_height > tree->height);
389
390 return ERR_SUCCESS0;
391}
392
393static void
394rdxtree_cleanup(struct rdxtree *tree, struct rdxtree_node *node)
395{
396 struct rdxtree_node *prev;
397
398 for (;;) {
399 if (likely(!rdxtree_node_empty(node))__builtin_expect(!!(!rdxtree_node_empty(node)), 1)) {
400 if (unlikely(node->parent == NULL)__builtin_expect(!!(node->parent == ((void *) 0)), 0))
401 rdxtree_shrink(tree);
402
403 break;
404 }
405
406 if (node->parent == NULL((void *) 0)) {
407 tree->height = 0;
408 llsync_assign_ptr(tree->root, NULL)((tree->root) = (((void *) 0)));
409 rdxtree_node_schedule_destruction(node);
410 break;
411 }
412
413 prev = node;
414 node = node->parent;
415 rdxtree_node_unlink(prev);
416 rdxtree_node_remove(node, prev->index);
417 rdxtree_node_schedule_destruction(prev);
418 }
419}
420
421static void
422rdxtree_insert_bm_clear(struct rdxtree_node *node, unsigned int index)
423{
424 for (;;) {
425 rdxtree_node_bm_clear(node, index);
426
427 if (!rdxtree_node_full(node) || (node->parent == NULL((void *) 0)))
428 break;
429
430 index = node->index;
431 node = node->parent;
432 }
433}
434
435int
436rdxtree_insert_common(struct rdxtree *tree, rdxtree_key_t key,
437 void *ptr, void ***slotp)
438{
439 struct rdxtree_node *node, *prev;
440 unsigned int height, shift, index = index;
441 int error;
442
443 assert(ptr != NULL)((ptr != ((void *) 0)) ? (void) (0) : Assert ("ptr != NULL", "../kern/rdxtree.c"
, 443));
444 assert(rdxtree_check_alignment(ptr))((rdxtree_check_alignment(ptr)) ? (void) (0) : Assert ("rdxtree_check_alignment(ptr)"
, "../kern/rdxtree.c", 444));
445
446 if (unlikely(key > rdxtree_max_key(tree->height))__builtin_expect(!!(key > rdxtree_max_key(tree->height)
), 0)) {
447 error = rdxtree_grow(tree, key);
448
449 if (error)
450 return error;
451 }
452
453 height = tree->height;
454
455 if (unlikely(height == 0)__builtin_expect(!!(height == 0), 0)) {
456 if (tree->root != NULL((void *) 0))
457 return ERR_BUSY4;
458
459 llsync_assign_ptr(tree->root, ptr)((tree->root) = (ptr));
460
461 if (slotp != NULL((void *) 0))
462 *slotp = &tree->root;
463
464 return ERR_SUCCESS0;
465 }
466
467 node = rdxtree_entry_addr(tree->root);
468 shift = (height - 1) * RDXTREE_RADIX6;
469 prev = NULL((void *) 0);
470
471 do {
472 if (node == NULL((void *) 0)) {
473 error = rdxtree_node_create(&node, height - 1);
474
475 if (error) {
476 if (prev == NULL((void *) 0))
477 tree->height = 0;
478 else
479 rdxtree_cleanup(tree, prev);
480
481 return error;
482 }
483
484 if (prev == NULL((void *) 0))
485 llsync_assign_ptr(tree->root, rdxtree_node_to_entry(node))((tree->root) = (rdxtree_node_to_entry(node)));
486 else {
487 rdxtree_node_link(node, prev, index);
488 rdxtree_node_insert_node(prev, index, node);
489 }
490 }
491
492 prev = node;
493 index = (unsigned int)(key >> shift) & RDXTREE_RADIX_MASK((1UL << 6) - 1);
494 node = rdxtree_entry_addr(prev->entries[index]);
495 shift -= RDXTREE_RADIX6;
496 height--;
497 } while (height > 0);
498
499 if (unlikely(node != NULL)__builtin_expect(!!(node != ((void *) 0)), 0))
500 return ERR_BUSY4;
501
502 rdxtree_node_insert(prev, index, ptr);
503 rdxtree_insert_bm_clear(prev, index);
504
505 if (slotp != NULL((void *) 0))
506 *slotp = &prev->entries[index];
507
508 return ERR_SUCCESS0;
509}
510
511int
512rdxtree_insert_alloc_common(struct rdxtree *tree, void *ptr,
513 rdxtree_key_t *keyp, void ***slotp)
514{
515 struct rdxtree_node *node, *prev;
516 unsigned int height, shift, index = index;
Assigned value is garbage or undefined
517 rdxtree_key_t key;
518 int error;
519
520 assert(ptr != NULL)((ptr != ((void *) 0)) ? (void) (0) : Assert ("ptr != NULL", "../kern/rdxtree.c"
, 520));
521 assert(rdxtree_check_alignment(ptr))((rdxtree_check_alignment(ptr)) ? (void) (0) : Assert ("rdxtree_check_alignment(ptr)"
, "../kern/rdxtree.c", 521));
522
523 height = tree->height;
524
525 if (unlikely(height == 0)__builtin_expect(!!(height == 0), 0)) {
526 if (tree->root == NULL((void *) 0)) {
527 llsync_assign_ptr(tree->root, ptr)((tree->root) = (ptr));
528 *keyp = 0;
529
530 if (slotp != NULL((void *) 0))
531 *slotp = &tree->root;
532
533 return ERR_SUCCESS0;
534 }
535
536 goto grow;
537 }
538
539 node = rdxtree_entry_addr(tree->root);
540 key = 0;
541 shift = (height - 1) * RDXTREE_RADIX6;
542 prev = NULL((void *) 0);
543
544 do {
545 if (node == NULL((void *) 0)) {
546 error = rdxtree_node_create(&node, height - 1);
547
548 if (error) {
549 rdxtree_cleanup(tree, prev);
550 return error;
551 }
552
553 rdxtree_node_link(node, prev, index);
554 rdxtree_node_insert_node(prev, index, node);
555 }
556
557 prev = node;
558 index = rdxtree_node_bm_first(node);
559
560 if (index == (unsigned int)-1)
561 goto grow;
562
563 key |= (rdxtree_key_t)index << shift;
564 node = rdxtree_entry_addr(node->entries[index]);
565 shift -= RDXTREE_RADIX6;
566 height--;
567 } while (height > 0);
568
569 rdxtree_node_insert(prev, index, ptr);
570 rdxtree_insert_bm_clear(prev, index);
571
572 if (slotp != NULL((void *) 0))
573 *slotp = &prev->entries[index];
574
575 goto out;
576
577grow:
578 key = rdxtree_max_key(height) + 1;
579 error = rdxtree_insert_common(tree, key, ptr, slotp);
580
581 if (error)
582 return error;
583
584out:
585 *keyp = key;
586 return ERR_SUCCESS0;
587}
588
589static void
590rdxtree_remove_bm_set(struct rdxtree_node *node, unsigned int index)
591{
592 do {
593 rdxtree_node_bm_set(node, index);
594
595 if (node->parent == NULL((void *) 0))
596 break;
597
598 index = node->index;
599 node = node->parent;
600 } while (!rdxtree_node_bm_is_set(node, index));
601}
602
603void *
604rdxtree_remove(struct rdxtree *tree, rdxtree_key_t key)
605{
606 struct rdxtree_node *node, *prev;
607 unsigned int height, shift, index;
608
609 height = tree->height;
610
611 if (unlikely(key > rdxtree_max_key(height))__builtin_expect(!!(key > rdxtree_max_key(height)), 0))
612 return NULL((void *) 0);
613
614 node = rdxtree_entry_addr(tree->root);
615
616 if (unlikely(height == 0)__builtin_expect(!!(height == 0), 0)) {
617 llsync_assign_ptr(tree->root, NULL)((tree->root) = (((void *) 0)));
618 return node;
619 }
620
621 shift = (height - 1) * RDXTREE_RADIX6;
622
623 do {
624 if (node == NULL((void *) 0))
625 return NULL((void *) 0);
626
627 prev = node;
628 index = (unsigned int)(key >> shift) & RDXTREE_RADIX_MASK((1UL << 6) - 1);
629 node = rdxtree_entry_addr(node->entries[index]);
630 shift -= RDXTREE_RADIX6;
631 height--;
632 } while (height > 0);
633
634 if (node == NULL((void *) 0))
635 return NULL((void *) 0);
636
637 rdxtree_node_remove(prev, index);
638 rdxtree_remove_bm_set(prev, index);
639 rdxtree_cleanup(tree, prev);
640 return node;
641}
642
643void *
644rdxtree_lookup_common(const struct rdxtree *tree, rdxtree_key_t key,
645 int get_slot)
646{
647 struct rdxtree_node *node, *prev;
648 unsigned int height, shift, index;
649 void *entry;
650
651 entry = llsync_read_ptr(tree->root)(tree->root);
652
653 if (entry == NULL((void *) 0)) {
654 node = NULL((void *) 0);
655 height = 0;
656 } else {
657 node = rdxtree_entry_addr(entry);
658 height = rdxtree_entry_is_node(entry) ? node->height + 1 : 0;
659 }
660
661 if (key > rdxtree_max_key(height))
662 return NULL((void *) 0);
663
664 if (height == 0) {
665 if (node == NULL((void *) 0))
666 return NULL((void *) 0);
667
668 return get_slot ? (void *)&tree->root : node;
669 }
670
671 shift = (height - 1) * RDXTREE_RADIX6;
672
673 do {
674 if (node == NULL((void *) 0))
675 return NULL((void *) 0);
676
677 prev = node;
678 index = (unsigned int)(key >> shift) & RDXTREE_RADIX_MASK((1UL << 6) - 1);
679 entry = llsync_read_ptr(node->entries[index])(node->entries[index]);
680 node = rdxtree_entry_addr(entry);
681 shift -= RDXTREE_RADIX6;
682 height--;
683 } while (height > 0);
684
685 if (node == NULL((void *) 0))
686 return NULL((void *) 0);
687
688 return get_slot ? (void *)&prev->entries[index] : node;
689}
690
691void *
692rdxtree_replace_slot(void **slot, void *ptr)
693{
694 void *old;
695
696 assert(ptr != NULL)((ptr != ((void *) 0)) ? (void) (0) : Assert ("ptr != NULL", "../kern/rdxtree.c"
, 696));
697 assert(rdxtree_check_alignment(ptr))((rdxtree_check_alignment(ptr)) ? (void) (0) : Assert ("rdxtree_check_alignment(ptr)"
, "../kern/rdxtree.c", 697));
698
699 old = *slot;
700 assert(old != NULL)((old != ((void *) 0)) ? (void) (0) : Assert ("old != NULL", "../kern/rdxtree.c"
, 700));
701 assert(rdxtree_check_alignment(old))((rdxtree_check_alignment(old)) ? (void) (0) : Assert ("rdxtree_check_alignment(old)"
, "../kern/rdxtree.c", 701));
702 llsync_assign_ptr(*slot, ptr)((*slot) = (ptr));
703 return old;
704}
705
706static void *
707rdxtree_walk_next(struct rdxtree *tree, struct rdxtree_iter *iter)
708{
709 struct rdxtree_node *root, *node, *prev;
710 unsigned int height, shift, index, orig_index;
711 rdxtree_key_t key;
712 void *entry;
713
714 entry = llsync_read_ptr(tree->root)(tree->root);
715
716 if (entry == NULL((void *) 0))
717 return NULL((void *) 0);
718
719 if (!rdxtree_entry_is_node(entry)) {
720 if (iter->key != (rdxtree_key_t)-1)
721 return NULL((void *) 0);
722 else {
723 iter->key = 0;
724 return rdxtree_entry_addr(entry);
725 }
726 }
727
728 key = iter->key + 1;
729
730 if ((key == 0) && (iter->node != NULL((void *) 0)))
731 return NULL((void *) 0);
732
733 root = rdxtree_entry_addr(entry);
734
735restart:
736 node = root;
737 height = root->height + 1;
738
739 if (key > rdxtree_max_key(height))
740 return NULL((void *) 0);
741
742 shift = (height - 1) * RDXTREE_RADIX6;
743
744 do {
745 prev = node;
746 index = (key >> shift) & RDXTREE_RADIX_MASK((1UL << 6) - 1);
747 orig_index = index;
748 node = rdxtree_node_find(node, &index);
749
750 if (node == NULL((void *) 0)) {
751 shift += RDXTREE_RADIX6;
752 key = ((key >> shift) + 1) << shift;
753
754 if (key == 0)
755 return NULL((void *) 0);
756
757 goto restart;
758 }
759
760 if (orig_index != index)
761 key = ((key >> shift) + (index - orig_index)) << shift;
762
763 shift -= RDXTREE_RADIX6;
764 height--;
765 } while (height > 0);
766
767 iter->node = prev;
768 iter->key = key;
769 return node;
770}
771
772void *
773rdxtree_walk(struct rdxtree *tree, struct rdxtree_iter *iter)
774{
775 unsigned int index, orig_index;
776 void *ptr;
777
778 if (iter->node == NULL((void *) 0))
779 return rdxtree_walk_next(tree, iter);
780
781 index = (iter->key + 1) & RDXTREE_RADIX_MASK((1UL << 6) - 1);
782
783 if (index != 0) {
784 orig_index = index;
785 ptr = rdxtree_node_find(iter->node, &index);
786
787 if (ptr != NULL((void *) 0)) {
788 iter->key += (index - orig_index) + 1;
789 return ptr;
790 }
791 }
792
793 return rdxtree_walk_next(tree, iter);
794}
795
796void
797rdxtree_remove_all(struct rdxtree *tree)
798{
799 struct rdxtree_node *node, *parent;
800 struct rdxtree_iter iter;
801
802 if (tree->height == 0) {
803 if (tree->root != NULL((void *) 0))
804 llsync_assign_ptr(tree->root, NULL)((tree->root) = (((void *) 0)));
805
806 return;
807 }
808
809 for (;;) {
810 rdxtree_iter_init(&iter);
811 rdxtree_walk_next(tree, &iter);
812
813 if (iter.node == NULL((void *) 0))
814 break;
815
816 node = iter.node;
817 parent = node->parent;
818
819 if (parent == NULL((void *) 0))
820 rdxtree_init(tree);
821 else {
822 rdxtree_node_remove(parent, node->index);
823 rdxtree_remove_bm_set(parent, node->index);
824 rdxtree_cleanup(tree, parent);
825 node->parent = NULL((void *) 0);
826 }
827
828 rdxtree_node_schedule_destruction(node);
829 }
830}