1 /* $NetBSD: radixtree.c,v 1.23 2020/01/28 22:20:45 ad Exp $ */ 2 3 /*- 4 * Copyright (c)2011,2012,2013 YAMAMOTO Takashi, 5 * All rights reserved. 6 * 7 * Redistribution and use in source and binary forms, with or without 8 * modification, are permitted provided that the following conditions 9 * are met: 10 * 1. Redistributions of source code must retain the above copyright 11 * notice, this list of conditions and the following disclaimer. 12 * 2. Redistributions in binary form must reproduce the above copyright 13 * notice, this list of conditions and the following disclaimer in the 14 * documentation and/or other materials provided with the distribution. 15 * 16 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND 17 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 18 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 19 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE 20 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 21 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 22 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 23 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 24 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 25 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 26 * SUCH DAMAGE. 27 */ 28 29 /* 30 * radixtree.c 31 * 32 * Overview: 33 * 34 * This is an implementation of radix tree, whose keys are uint64_t and leafs 35 * are user provided pointers. 36 * 37 * Leaf nodes are just void * and this implementation doesn't care about 38 * what they actually point to. However, this implementation has an assumption 39 * about their alignment. Specifically, this implementation assumes that their 40 * 2 LSBs are always zero and uses them for internal accounting. 41 * 42 * Intermediate nodes and memory allocation: 43 * 44 * Intermediate nodes are automatically allocated and freed internally and 45 * basically users don't need to care about them. The allocation is done via 46 * pool_cache_get(9) for _KERNEL, malloc(3) for userland, and alloc() for 47 * _STANDALONE environment. Only radix_tree_insert_node function can allocate 48 * memory for intermediate nodes and thus can fail for ENOMEM. 49 * 50 * Memory Efficiency: 51 * 52 * It's designed to work efficiently with dense index distribution. 53 * The memory consumption (number of necessary intermediate nodes) heavily 54 * depends on the index distribution. Basically, more dense index distribution 55 * consumes less nodes per item. Approximately, 56 * 57 * - the best case: about RADIX_TREE_PTR_PER_NODE items per intermediate node. 58 * it would look like the following. 59 * 60 * root (t_height=1) 61 * | 62 * v 63 * [ | | | ] (intermediate node. RADIX_TREE_PTR_PER_NODE=4 in this fig) 64 * | | | | 65 * v v v v 66 * p p p p (items) 67 * 68 * - the worst case: RADIX_TREE_MAX_HEIGHT intermediate nodes per item. 69 * it would look like the following if RADIX_TREE_MAX_HEIGHT=3. 70 * 71 * root (t_height=3) 72 * | 73 * v 74 * [ | | | ] 75 * | 76 * v 77 * [ | | | ] 78 * | 79 * v 80 * [ | | | ] 81 * | 82 * v 83 * p 84 * 85 * The height of tree (t_height) is dynamic. It's smaller if only small 86 * index values are used. As an extreme case, if only index 0 is used, 87 * the corresponding value is directly stored in the root of the tree 88 * (struct radix_tree) without allocating any intermediate nodes. In that 89 * case, t_height=0. 90 * 91 * Gang lookup: 92 * 93 * This implementation provides a way to scan many nodes quickly via 94 * radix_tree_gang_lookup_node function and its varients. 95 * 96 * Tags: 97 * 98 * This implementation provides tagging functionality, which allows quick 99 * scanning of a subset of leaf nodes. Leaf nodes are untagged when inserted 100 * into the tree and can be tagged by radix_tree_set_tag function. 101 * radix_tree_gang_lookup_tagged_node function and its variants returns only 102 * leaf nodes with the given tag. To reduce amount of nodes to visit for 103 * these functions, this implementation keeps tagging information in internal 104 * intermediate nodes and quickly skips uninterested parts of a tree. 105 * 106 * A tree has RADIX_TREE_TAG_ID_MAX independent tag spaces, each of which are 107 * identified by an zero-origin numbers, tagid. For the current implementation, 108 * RADIX_TREE_TAG_ID_MAX is 2. A set of tags is described as a bitmask tagmask, 109 * which is a bitwise OR of (1 << tagid). 110 */ 111 112 #include <sys/cdefs.h> 113 114 #if defined(_KERNEL) || defined(_STANDALONE) 115 __KERNEL_RCSID(0, "$NetBSD: radixtree.c,v 1.23 2020/01/28 22:20:45 ad Exp $"); 116 #include <sys/param.h> 117 #include <sys/errno.h> 118 #include <sys/pool.h> 119 #include <sys/radixtree.h> 120 #include <lib/libkern/libkern.h> 121 #if defined(_STANDALONE) 122 #include <lib/libsa/stand.h> 123 #endif /* defined(_STANDALONE) */ 124 #else /* defined(_KERNEL) || defined(_STANDALONE) */ 125 __RCSID("$NetBSD: radixtree.c,v 1.23 2020/01/28 22:20:45 ad Exp $"); 126 #include <assert.h> 127 #include <errno.h> 128 #include <stdbool.h> 129 #include <stdlib.h> 130 #include <string.h> 131 #if 1 132 #define KASSERT assert 133 #else 134 #define KASSERT(a) /* nothing */ 135 #endif 136 #endif /* defined(_KERNEL) || defined(_STANDALONE) */ 137 138 #include <sys/radixtree.h> 139 140 #define RADIX_TREE_BITS_PER_HEIGHT 4 /* XXX tune */ 141 #define RADIX_TREE_PTR_PER_NODE (1 << RADIX_TREE_BITS_PER_HEIGHT) 142 #define RADIX_TREE_MAX_HEIGHT (64 / RADIX_TREE_BITS_PER_HEIGHT) 143 #define RADIX_TREE_INVALID_HEIGHT (RADIX_TREE_MAX_HEIGHT + 1) 144 __CTASSERT((64 % RADIX_TREE_BITS_PER_HEIGHT) == 0); 145 146 __CTASSERT(((1 << RADIX_TREE_TAG_ID_MAX) & (sizeof(int) - 1)) == 0); 147 #define RADIX_TREE_TAG_MASK ((1 << RADIX_TREE_TAG_ID_MAX) - 1) 148 149 static inline void * 150 entry_ptr(void *p) 151 { 152 153 return (void *)((uintptr_t)p & ~RADIX_TREE_TAG_MASK); 154 } 155 156 static inline unsigned int 157 entry_tagmask(void *p) 158 { 159 160 return (uintptr_t)p & RADIX_TREE_TAG_MASK; 161 } 162 163 static inline void * 164 entry_compose(void *p, unsigned int tagmask) 165 { 166 167 return (void *)((uintptr_t)p | tagmask); 168 } 169 170 static inline bool 171 entry_match_p(void *p, unsigned int tagmask) 172 { 173 174 KASSERT(entry_ptr(p) != NULL || entry_tagmask(p) == 0); 175 if (p == NULL) { 176 return false; 177 } 178 if (tagmask == 0) { 179 return true; 180 } 181 return (entry_tagmask(p) & tagmask) != 0; 182 } 183 184 /* 185 * radix_tree_node: an intermediate node 186 * 187 * we don't care the type of leaf nodes. they are just void *. 188 * 189 * we used to maintain a count of non-NULL nodes in this structure, but it 190 * prevented it from being aligned to a cache line boundary; the performance 191 * benefit from being cache friendly is greater than the benefit of having 192 * a dedicated count value, especially in multi-processor situations where 193 * we need to avoid intra-pool-page false sharing. 194 */ 195 196 struct radix_tree_node { 197 void *n_ptrs[RADIX_TREE_PTR_PER_NODE]; 198 }; 199 200 /* 201 * any_children_tagmask: 202 * 203 * return OR'ed tagmask of the given node's children. 204 */ 205 206 static unsigned int 207 any_children_tagmask(const struct radix_tree_node *n) 208 { 209 unsigned int mask; 210 int i; 211 212 mask = 0; 213 for (i = 0; i < RADIX_TREE_PTR_PER_NODE; i++) { 214 mask |= (unsigned int)(uintptr_t)n->n_ptrs[i]; 215 } 216 return mask & RADIX_TREE_TAG_MASK; 217 } 218 219 /* 220 * p_refs[0].pptr == &t->t_root 221 * : 222 * p_refs[n].pptr == &(*p_refs[n-1])->n_ptrs[x] 223 * : 224 * : 225 * p_refs[t->t_height].pptr == &leaf_pointer 226 */ 227 228 struct radix_tree_path { 229 struct radix_tree_node_ref { 230 void **pptr; 231 } p_refs[RADIX_TREE_MAX_HEIGHT + 1]; /* +1 for the root ptr */ 232 /* 233 * p_lastidx is either the index of the last valid element of p_refs[] 234 * or RADIX_TREE_INVALID_HEIGHT. 235 * RADIX_TREE_INVALID_HEIGHT means that radix_tree_lookup_ptr found 236 * that the height of the tree is not enough to cover the given index. 237 */ 238 unsigned int p_lastidx; 239 }; 240 241 static inline void ** 242 path_pptr(const struct radix_tree *t, const struct radix_tree_path *p, 243 unsigned int height) 244 { 245 246 KASSERT(height <= t->t_height); 247 return p->p_refs[height].pptr; 248 } 249 250 static inline struct radix_tree_node * 251 path_node(const struct radix_tree * t, const struct radix_tree_path *p, 252 unsigned int height) 253 { 254 255 KASSERT(height <= t->t_height); 256 return entry_ptr(*path_pptr(t, p, height)); 257 } 258 259 /* 260 * radix_tree_init_tree: 261 * 262 * Initialize a tree. 263 */ 264 265 void 266 radix_tree_init_tree(struct radix_tree *t) 267 { 268 269 t->t_height = 0; 270 t->t_root = NULL; 271 } 272 273 /* 274 * radix_tree_fini_tree: 275 * 276 * Finish using a tree. 277 */ 278 279 void 280 radix_tree_fini_tree(struct radix_tree *t) 281 { 282 283 KASSERT(t->t_root == NULL); 284 KASSERT(t->t_height == 0); 285 } 286 287 /* 288 * radix_tree_empty_tree_p: 289 * 290 * Return if the tree is empty. 291 */ 292 293 bool 294 radix_tree_empty_tree_p(struct radix_tree *t) 295 { 296 297 return t->t_root == NULL; 298 } 299 300 /* 301 * radix_tree_empty_tree_p: 302 * 303 * Return true if the tree has any nodes with the given tag. Otherwise 304 * return false. 305 * 306 * It's illegal to call this function with tagmask 0. 307 */ 308 309 bool 310 radix_tree_empty_tagged_tree_p(struct radix_tree *t, unsigned int tagmask) 311 { 312 313 KASSERT(tagmask != 0); 314 return (entry_tagmask(t->t_root) & tagmask) == 0; 315 } 316 317 static void 318 radix_tree_node_init(struct radix_tree_node *n) 319 { 320 321 memset(n, 0, sizeof(*n)); 322 } 323 324 #if defined(_KERNEL) 325 pool_cache_t radix_tree_node_cache __read_mostly; 326 327 static int 328 radix_tree_node_ctor(void *dummy, void *item, int flags) 329 { 330 struct radix_tree_node *n = item; 331 332 KASSERT(dummy == NULL); 333 radix_tree_node_init(n); 334 return 0; 335 } 336 337 /* 338 * radix_tree_init: 339 * 340 * initialize the subsystem. 341 */ 342 343 void 344 radix_tree_init(void) 345 { 346 347 radix_tree_node_cache = pool_cache_init(sizeof(struct radix_tree_node), 348 coherency_unit, 0, PR_LARGECACHE, "radixnode", NULL, IPL_NONE, 349 radix_tree_node_ctor, NULL, NULL); 350 KASSERT(radix_tree_node_cache != NULL); 351 } 352 353 /* 354 * radix_tree_await_memory: 355 * 356 * after an insert has failed with ENOMEM, wait for memory to become 357 * available, so the caller can retry. 358 */ 359 360 void 361 radix_tree_await_memory(void) 362 { 363 struct radix_tree_node *n; 364 365 n = pool_cache_get(radix_tree_node_cache, PR_WAITOK); 366 pool_cache_put(radix_tree_node_cache, n); 367 } 368 369 #endif /* defined(_KERNEL) */ 370 371 static bool __unused 372 radix_tree_node_clean_p(const struct radix_tree_node *n) 373 { 374 #if RADIX_TREE_PTR_PER_NODE > 16 375 unsigned int i; 376 377 for (i = 0; i < RADIX_TREE_PTR_PER_NODE; i++) { 378 if (n->n_ptrs[i] != NULL) { 379 return false; 380 } 381 } 382 return true; 383 #else /* RADIX_TREE_PTR_PER_NODE > 16 */ 384 uintptr_t sum; 385 386 /* 387 * Unrolling the above is much better than a tight loop with two 388 * test+branch pairs. On x86 with gcc 5.5.0 this compiles into 19 389 * deterministic instructions including the "return" and prologue & 390 * epilogue. 391 */ 392 sum = (uintptr_t)n->n_ptrs[0]; 393 sum |= (uintptr_t)n->n_ptrs[1]; 394 sum |= (uintptr_t)n->n_ptrs[2]; 395 sum |= (uintptr_t)n->n_ptrs[3]; 396 #if RADIX_TREE_PTR_PER_NODE > 4 397 sum |= (uintptr_t)n->n_ptrs[4]; 398 sum |= (uintptr_t)n->n_ptrs[5]; 399 sum |= (uintptr_t)n->n_ptrs[6]; 400 sum |= (uintptr_t)n->n_ptrs[7]; 401 #endif 402 #if RADIX_TREE_PTR_PER_NODE > 8 403 sum |= (uintptr_t)n->n_ptrs[8]; 404 sum |= (uintptr_t)n->n_ptrs[9]; 405 sum |= (uintptr_t)n->n_ptrs[10]; 406 sum |= (uintptr_t)n->n_ptrs[11]; 407 sum |= (uintptr_t)n->n_ptrs[12]; 408 sum |= (uintptr_t)n->n_ptrs[13]; 409 sum |= (uintptr_t)n->n_ptrs[14]; 410 sum |= (uintptr_t)n->n_ptrs[15]; 411 #endif 412 return sum == 0; 413 #endif /* RADIX_TREE_PTR_PER_NODE > 16 */ 414 } 415 416 static int __unused 417 radix_tree_node_count_ptrs(const struct radix_tree_node *n) 418 { 419 unsigned int i, c; 420 421 for (i = c = 0; i < RADIX_TREE_PTR_PER_NODE; i++) { 422 c += (n->n_ptrs[i] != NULL); 423 } 424 return c; 425 } 426 427 static struct radix_tree_node * 428 radix_tree_alloc_node(void) 429 { 430 struct radix_tree_node *n; 431 432 #if defined(_KERNEL) 433 /* 434 * note that pool_cache_get can block. 435 */ 436 n = pool_cache_get(radix_tree_node_cache, PR_NOWAIT); 437 #else /* defined(_KERNEL) */ 438 #if defined(_STANDALONE) 439 n = alloc(sizeof(*n)); 440 #else /* defined(_STANDALONE) */ 441 n = malloc(sizeof(*n)); 442 #endif /* defined(_STANDALONE) */ 443 if (n != NULL) { 444 radix_tree_node_init(n); 445 } 446 #endif /* defined(_KERNEL) */ 447 KASSERT(n == NULL || radix_tree_node_clean_p(n)); 448 return n; 449 } 450 451 static void 452 radix_tree_free_node(struct radix_tree_node *n) 453 { 454 455 KASSERT(radix_tree_node_clean_p(n)); 456 #if defined(_KERNEL) 457 pool_cache_put(radix_tree_node_cache, n); 458 #elif defined(_STANDALONE) 459 dealloc(n, sizeof(*n)); 460 #else 461 free(n); 462 #endif 463 } 464 465 static int 466 radix_tree_grow(struct radix_tree *t, unsigned int newheight) 467 { 468 const unsigned int tagmask = entry_tagmask(t->t_root); 469 470 KASSERT(newheight <= 64 / RADIX_TREE_BITS_PER_HEIGHT); 471 if (t->t_root == NULL) { 472 t->t_height = newheight; 473 return 0; 474 } 475 while (t->t_height < newheight) { 476 struct radix_tree_node *n; 477 478 n = radix_tree_alloc_node(); 479 if (n == NULL) { 480 /* 481 * don't bother to revert our changes. 482 * the caller will likely retry. 483 */ 484 return ENOMEM; 485 } 486 n->n_ptrs[0] = t->t_root; 487 t->t_root = entry_compose(n, tagmask); 488 t->t_height++; 489 } 490 return 0; 491 } 492 493 /* 494 * radix_tree_lookup_ptr: 495 * 496 * an internal helper function used for various exported functions. 497 * 498 * return the pointer to store the node for the given index. 499 * 500 * if alloc is true, try to allocate the storage. (note for _KERNEL: 501 * in that case, this function can block.) if the allocation failed or 502 * alloc is false, return NULL. 503 * 504 * if path is not NULL, fill it for the caller's investigation. 505 * 506 * if tagmask is not zero, search only for nodes with the tag set. 507 * note that, however, this function doesn't check the tagmask for the leaf 508 * pointer. it's a caller's responsibility to investigate the value which 509 * is pointed by the returned pointer if necessary. 510 * 511 * while this function is a bit large, as it's called with some constant 512 * arguments, inlining might have benefits. anyway, a compiler will decide. 513 */ 514 515 static inline void ** 516 radix_tree_lookup_ptr(struct radix_tree *t, uint64_t idx, 517 struct radix_tree_path *path, bool alloc, const unsigned int tagmask) 518 { 519 struct radix_tree_node *n; 520 int hshift = RADIX_TREE_BITS_PER_HEIGHT * t->t_height; 521 int shift; 522 void **vpp; 523 const uint64_t mask = (UINT64_C(1) << RADIX_TREE_BITS_PER_HEIGHT) - 1; 524 struct radix_tree_node_ref *refs = NULL; 525 526 /* 527 * check unsupported combinations 528 */ 529 KASSERT(tagmask == 0 || !alloc); 530 KASSERT(path == NULL || !alloc); 531 vpp = &t->t_root; 532 if (path != NULL) { 533 refs = path->p_refs; 534 refs->pptr = vpp; 535 } 536 n = NULL; 537 for (shift = 64 - RADIX_TREE_BITS_PER_HEIGHT; shift >= 0;) { 538 struct radix_tree_node *c; 539 void *entry; 540 const uint64_t i = (idx >> shift) & mask; 541 542 if (shift >= hshift) { 543 unsigned int newheight; 544 545 KASSERT(vpp == &t->t_root); 546 if (i == 0) { 547 shift -= RADIX_TREE_BITS_PER_HEIGHT; 548 continue; 549 } 550 if (!alloc) { 551 if (path != NULL) { 552 KASSERT((refs - path->p_refs) == 0); 553 path->p_lastidx = 554 RADIX_TREE_INVALID_HEIGHT; 555 } 556 return NULL; 557 } 558 newheight = shift / RADIX_TREE_BITS_PER_HEIGHT + 1; 559 if (radix_tree_grow(t, newheight)) { 560 return NULL; 561 } 562 hshift = RADIX_TREE_BITS_PER_HEIGHT * t->t_height; 563 } 564 entry = *vpp; 565 c = entry_ptr(entry); 566 if (c == NULL || 567 (tagmask != 0 && 568 (entry_tagmask(entry) & tagmask) == 0)) { 569 if (!alloc) { 570 if (path != NULL) { 571 path->p_lastidx = refs - path->p_refs; 572 } 573 return NULL; 574 } 575 c = radix_tree_alloc_node(); 576 if (c == NULL) { 577 return NULL; 578 } 579 *vpp = c; 580 } 581 n = c; 582 vpp = &n->n_ptrs[i]; 583 if (path != NULL) { 584 refs++; 585 refs->pptr = vpp; 586 } 587 shift -= RADIX_TREE_BITS_PER_HEIGHT; 588 } 589 if (alloc) { 590 KASSERT(*vpp == NULL); 591 } 592 if (path != NULL) { 593 path->p_lastidx = refs - path->p_refs; 594 } 595 return vpp; 596 } 597 598 /* 599 * radix_tree_insert_node: 600 * 601 * Insert the node at the given index. 602 * 603 * It's illegal to insert NULL. It's illegal to insert a non-aligned pointer. 604 * 605 * This function returns ENOMEM if necessary memory allocation failed. 606 * Otherwise, this function returns 0. 607 * 608 * Note that inserting a node can involves memory allocation for intermediate 609 * nodes. If _KERNEL, it's done with no-sleep IPL_NONE memory allocation. 610 * 611 * For the newly inserted node, all tags are cleared. 612 */ 613 614 int 615 radix_tree_insert_node(struct radix_tree *t, uint64_t idx, void *p) 616 { 617 void **vpp; 618 619 KASSERT(p != NULL); 620 KASSERT(entry_tagmask(entry_compose(p, 0)) == 0); 621 vpp = radix_tree_lookup_ptr(t, idx, NULL, true, 0); 622 if (vpp == NULL) { 623 return ENOMEM; 624 } 625 KASSERT(*vpp == NULL); 626 *vpp = p; 627 return 0; 628 } 629 630 /* 631 * radix_tree_replace_node: 632 * 633 * Replace a node at the given index with the given node and return the 634 * replaced one. 635 * 636 * It's illegal to try to replace a node which has not been inserted. 637 * 638 * This function keeps tags intact. 639 */ 640 641 void * 642 radix_tree_replace_node(struct radix_tree *t, uint64_t idx, void *p) 643 { 644 void **vpp; 645 void *oldp; 646 647 KASSERT(p != NULL); 648 KASSERT(entry_tagmask(entry_compose(p, 0)) == 0); 649 vpp = radix_tree_lookup_ptr(t, idx, NULL, false, 0); 650 KASSERT(vpp != NULL); 651 oldp = *vpp; 652 KASSERT(oldp != NULL); 653 *vpp = entry_compose(p, entry_tagmask(*vpp)); 654 return entry_ptr(oldp); 655 } 656 657 /* 658 * radix_tree_remove_node: 659 * 660 * Remove the node at the given index. 661 * 662 * It's illegal to try to remove a node which has not been inserted. 663 */ 664 665 void * 666 radix_tree_remove_node(struct radix_tree *t, uint64_t idx) 667 { 668 struct radix_tree_path path; 669 void **vpp; 670 void *oldp; 671 int i; 672 673 vpp = radix_tree_lookup_ptr(t, idx, &path, false, 0); 674 KASSERT(vpp != NULL); 675 oldp = *vpp; 676 KASSERT(oldp != NULL); 677 KASSERT(path.p_lastidx == t->t_height); 678 KASSERT(vpp == path_pptr(t, &path, path.p_lastidx)); 679 *vpp = NULL; 680 for (i = t->t_height - 1; i >= 0; i--) { 681 void *entry; 682 struct radix_tree_node ** const pptr = 683 (struct radix_tree_node **)path_pptr(t, &path, i); 684 struct radix_tree_node *n; 685 686 KASSERT(pptr != NULL); 687 entry = *pptr; 688 n = entry_ptr(entry); 689 KASSERT(n != NULL); 690 if (!radix_tree_node_clean_p(n)) { 691 break; 692 } 693 radix_tree_free_node(n); 694 *pptr = NULL; 695 } 696 /* 697 * fix up height 698 */ 699 if (i < 0) { 700 KASSERT(t->t_root == NULL); 701 t->t_height = 0; 702 } 703 /* 704 * update tags 705 */ 706 for (; i >= 0; i--) { 707 void *entry; 708 struct radix_tree_node ** const pptr = 709 (struct radix_tree_node **)path_pptr(t, &path, i); 710 struct radix_tree_node *n; 711 unsigned int newmask; 712 713 KASSERT(pptr != NULL); 714 entry = *pptr; 715 n = entry_ptr(entry); 716 KASSERT(n != NULL); 717 KASSERT(!radix_tree_node_clean_p(n)); 718 newmask = any_children_tagmask(n); 719 if (newmask == entry_tagmask(entry)) { 720 break; 721 } 722 *pptr = entry_compose(n, newmask); 723 } 724 /* 725 * XXX is it worth to try to reduce height? 726 * if we do that, make radix_tree_grow rollback its change as well. 727 */ 728 return entry_ptr(oldp); 729 } 730 731 /* 732 * radix_tree_lookup_node: 733 * 734 * Returns the node at the given index. 735 * Returns NULL if nothing is found at the given index. 736 */ 737 738 void * 739 radix_tree_lookup_node(struct radix_tree *t, uint64_t idx) 740 { 741 void **vpp; 742 743 vpp = radix_tree_lookup_ptr(t, idx, NULL, false, 0); 744 if (vpp == NULL) { 745 return NULL; 746 } 747 return entry_ptr(*vpp); 748 } 749 750 static inline void 751 gang_lookup_init(struct radix_tree *t, uint64_t idx, 752 struct radix_tree_path *path, const unsigned int tagmask) 753 { 754 void **vpp __unused; 755 756 vpp = radix_tree_lookup_ptr(t, idx, path, false, tagmask); 757 KASSERT(vpp == NULL || 758 vpp == path_pptr(t, path, path->p_lastidx)); 759 KASSERT(&t->t_root == path_pptr(t, path, 0)); 760 KASSERT(path->p_lastidx == RADIX_TREE_INVALID_HEIGHT || 761 path->p_lastidx == t->t_height || 762 !entry_match_p(*path_pptr(t, path, path->p_lastidx), tagmask)); 763 } 764 765 /* 766 * gang_lookup_scan: 767 * 768 * a helper routine for radix_tree_gang_lookup_node and its variants. 769 */ 770 771 static inline unsigned int 772 __attribute__((__always_inline__)) 773 gang_lookup_scan(struct radix_tree *t, struct radix_tree_path *path, 774 void **results, const unsigned int maxresults, const unsigned int tagmask, 775 const bool reverse, const bool dense) 776 { 777 778 /* 779 * we keep the path updated only for lastidx-1. 780 * vpp is what path_pptr(t, path, lastidx) would be. 781 */ 782 void **vpp; 783 unsigned int nfound; 784 unsigned int lastidx; 785 /* 786 * set up scan direction dependant constants so that we can iterate 787 * n_ptrs as the following. 788 * 789 * for (i = first; i != guard; i += step) 790 * visit n->n_ptrs[i]; 791 */ 792 const int step = reverse ? -1 : 1; 793 const unsigned int first = reverse ? RADIX_TREE_PTR_PER_NODE - 1 : 0; 794 const unsigned int last = reverse ? 0 : RADIX_TREE_PTR_PER_NODE - 1; 795 const unsigned int guard = last + step; 796 797 KASSERT(maxresults > 0); 798 KASSERT(&t->t_root == path_pptr(t, path, 0)); 799 lastidx = path->p_lastidx; 800 KASSERT(lastidx == RADIX_TREE_INVALID_HEIGHT || 801 lastidx == t->t_height || 802 !entry_match_p(*path_pptr(t, path, lastidx), tagmask)); 803 nfound = 0; 804 if (lastidx == RADIX_TREE_INVALID_HEIGHT) { 805 /* 806 * requested idx is beyond the right-most node. 807 */ 808 if (reverse && !dense) { 809 lastidx = 0; 810 vpp = path_pptr(t, path, lastidx); 811 goto descend; 812 } 813 return 0; 814 } 815 vpp = path_pptr(t, path, lastidx); 816 while (/*CONSTCOND*/true) { 817 struct radix_tree_node *n; 818 unsigned int i; 819 820 if (entry_match_p(*vpp, tagmask)) { 821 KASSERT(lastidx == t->t_height); 822 /* 823 * record the matching non-NULL leaf. 824 */ 825 results[nfound] = entry_ptr(*vpp); 826 nfound++; 827 if (nfound == maxresults) { 828 return nfound; 829 } 830 } else if (dense) { 831 return nfound; 832 } 833 scan_siblings: 834 /* 835 * try to find the next matching non-NULL sibling. 836 */ 837 if (lastidx == 0) { 838 /* 839 * the root has no siblings. 840 * we've done. 841 */ 842 KASSERT(vpp == &t->t_root); 843 break; 844 } 845 n = path_node(t, path, lastidx - 1); 846 for (i = vpp - n->n_ptrs + step; i != guard; i += step) { 847 KASSERT(i < RADIX_TREE_PTR_PER_NODE); 848 if (entry_match_p(n->n_ptrs[i], tagmask)) { 849 vpp = &n->n_ptrs[i]; 850 break; 851 } else if (dense) { 852 return nfound; 853 } 854 } 855 if (i == guard) { 856 /* 857 * not found. go to parent. 858 */ 859 lastidx--; 860 vpp = path_pptr(t, path, lastidx); 861 goto scan_siblings; 862 } 863 descend: 864 /* 865 * following the left-most (or right-most in the case of 866 * reverse scan) child node, decend until reaching the leaf or 867 * an non-matching entry. 868 */ 869 while (entry_match_p(*vpp, tagmask) && lastidx < t->t_height) { 870 /* 871 * save vpp in the path so that we can come back to this 872 * node after finishing visiting children. 873 */ 874 path->p_refs[lastidx].pptr = vpp; 875 n = entry_ptr(*vpp); 876 vpp = &n->n_ptrs[first]; 877 lastidx++; 878 } 879 } 880 return nfound; 881 } 882 883 /* 884 * radix_tree_gang_lookup_node: 885 * 886 * Scan the tree starting from the given index in the ascending order and 887 * return found nodes. 888 * 889 * results should be an array large enough to hold maxresults pointers. 890 * This function returns the number of nodes found, up to maxresults. 891 * Returning less than maxresults means there are no more nodes in the tree. 892 * 893 * If dense == true, this function stops scanning when it founds a hole of 894 * indexes. I.e. an index for which radix_tree_lookup_node would returns NULL. 895 * If dense == false, this function skips holes and continue scanning until 896 * maxresults nodes are found or it reaches the limit of the index range. 897 * 898 * The result of this function is semantically equivalent to what could be 899 * obtained by repeated calls of radix_tree_lookup_node with increasing index. 900 * but this function is expected to be computationally cheaper when looking up 901 * multiple nodes at once. Especially, it's expected to be much cheaper when 902 * node indexes are distributed sparsely. 903 * 904 * Note that this function doesn't return index values of found nodes. 905 * Thus, in the case of dense == false, if index values are important for 906 * a caller, it's the caller's responsibility to check them, typically 907 * by examinining the returned nodes using some caller-specific knowledge 908 * about them. 909 * In the case of dense == true, a node returned via results[N] is always for 910 * the index (idx + N). 911 */ 912 913 unsigned int 914 radix_tree_gang_lookup_node(struct radix_tree *t, uint64_t idx, 915 void **results, unsigned int maxresults, bool dense) 916 { 917 struct radix_tree_path path; 918 919 gang_lookup_init(t, idx, &path, 0); 920 return gang_lookup_scan(t, &path, results, maxresults, 0, false, dense); 921 } 922 923 /* 924 * radix_tree_gang_lookup_node_reverse: 925 * 926 * Same as radix_tree_gang_lookup_node except that this one scans the 927 * tree in the reverse order. I.e. descending index values. 928 */ 929 930 unsigned int 931 radix_tree_gang_lookup_node_reverse(struct radix_tree *t, uint64_t idx, 932 void **results, unsigned int maxresults, bool dense) 933 { 934 struct radix_tree_path path; 935 936 gang_lookup_init(t, idx, &path, 0); 937 return gang_lookup_scan(t, &path, results, maxresults, 0, true, dense); 938 } 939 940 /* 941 * radix_tree_gang_lookup_tagged_node: 942 * 943 * Same as radix_tree_gang_lookup_node except that this one only returns 944 * nodes tagged with tagid. 945 * 946 * It's illegal to call this function with tagmask 0. 947 */ 948 949 unsigned int 950 radix_tree_gang_lookup_tagged_node(struct radix_tree *t, uint64_t idx, 951 void **results, unsigned int maxresults, bool dense, unsigned int tagmask) 952 { 953 struct radix_tree_path path; 954 955 KASSERT(tagmask != 0); 956 gang_lookup_init(t, idx, &path, tagmask); 957 return gang_lookup_scan(t, &path, results, maxresults, tagmask, false, 958 dense); 959 } 960 961 /* 962 * radix_tree_gang_lookup_tagged_node_reverse: 963 * 964 * Same as radix_tree_gang_lookup_tagged_node except that this one scans the 965 * tree in the reverse order. I.e. descending index values. 966 */ 967 968 unsigned int 969 radix_tree_gang_lookup_tagged_node_reverse(struct radix_tree *t, uint64_t idx, 970 void **results, unsigned int maxresults, bool dense, unsigned int tagmask) 971 { 972 struct radix_tree_path path; 973 974 KASSERT(tagmask != 0); 975 gang_lookup_init(t, idx, &path, tagmask); 976 return gang_lookup_scan(t, &path, results, maxresults, tagmask, true, 977 dense); 978 } 979 980 /* 981 * radix_tree_get_tag: 982 * 983 * Return the tagmask for the node at the given index. 984 * 985 * It's illegal to call this function for a node which has not been inserted. 986 */ 987 988 unsigned int 989 radix_tree_get_tag(struct radix_tree *t, uint64_t idx, unsigned int tagmask) 990 { 991 /* 992 * the following two implementations should behave same. 993 * the former one was chosen because it seems faster. 994 */ 995 #if 1 996 void **vpp; 997 998 vpp = radix_tree_lookup_ptr(t, idx, NULL, false, tagmask); 999 if (vpp == NULL) { 1000 return false; 1001 } 1002 KASSERT(*vpp != NULL); 1003 return (entry_tagmask(*vpp) & tagmask); 1004 #else 1005 void **vpp; 1006 1007 vpp = radix_tree_lookup_ptr(t, idx, NULL, false, 0); 1008 KASSERT(vpp != NULL); 1009 return (entry_tagmask(*vpp) & tagmask); 1010 #endif 1011 } 1012 1013 /* 1014 * radix_tree_set_tag: 1015 * 1016 * Set the tag for the node at the given index. 1017 * 1018 * It's illegal to call this function for a node which has not been inserted. 1019 * It's illegal to call this function with tagmask 0. 1020 */ 1021 1022 void 1023 radix_tree_set_tag(struct radix_tree *t, uint64_t idx, unsigned int tagmask) 1024 { 1025 struct radix_tree_path path; 1026 void **vpp __unused; 1027 int i; 1028 1029 KASSERT(tagmask != 0); 1030 vpp = radix_tree_lookup_ptr(t, idx, &path, false, 0); 1031 KASSERT(vpp != NULL); 1032 KASSERT(*vpp != NULL); 1033 KASSERT(path.p_lastidx == t->t_height); 1034 KASSERT(vpp == path_pptr(t, &path, path.p_lastidx)); 1035 for (i = t->t_height; i >= 0; i--) { 1036 void ** const pptr = (void **)path_pptr(t, &path, i); 1037 void *entry; 1038 1039 KASSERT(pptr != NULL); 1040 entry = *pptr; 1041 if ((entry_tagmask(entry) & tagmask) != 0) { 1042 break; 1043 } 1044 *pptr = (void *)((uintptr_t)entry | tagmask); 1045 } 1046 } 1047 1048 /* 1049 * radix_tree_clear_tag: 1050 * 1051 * Clear the tag for the node at the given index. 1052 * 1053 * It's illegal to call this function for a node which has not been inserted. 1054 * It's illegal to call this function with tagmask 0. 1055 */ 1056 1057 void 1058 radix_tree_clear_tag(struct radix_tree *t, uint64_t idx, unsigned int tagmask) 1059 { 1060 struct radix_tree_path path; 1061 void **vpp; 1062 int i; 1063 1064 KASSERT(tagmask != 0); 1065 vpp = radix_tree_lookup_ptr(t, idx, &path, false, 0); 1066 KASSERT(vpp != NULL); 1067 KASSERT(*vpp != NULL); 1068 KASSERT(path.p_lastidx == t->t_height); 1069 KASSERT(vpp == path_pptr(t, &path, path.p_lastidx)); 1070 /* 1071 * if already cleared, nothing to do 1072 */ 1073 if ((entry_tagmask(*vpp) & tagmask) == 0) { 1074 return; 1075 } 1076 /* 1077 * clear the tag only if no children have the tag. 1078 */ 1079 for (i = t->t_height; i >= 0; i--) { 1080 void ** const pptr = (void **)path_pptr(t, &path, i); 1081 void *entry; 1082 1083 KASSERT(pptr != NULL); 1084 entry = *pptr; 1085 KASSERT((entry_tagmask(entry) & tagmask) != 0); 1086 *pptr = entry_compose(entry_ptr(entry), 1087 entry_tagmask(entry) & ~tagmask); 1088 /* 1089 * check if we should proceed to process the next level. 1090 */ 1091 if (0 < i) { 1092 struct radix_tree_node *n = path_node(t, &path, i - 1); 1093 1094 if ((any_children_tagmask(n) & tagmask) != 0) { 1095 break; 1096 } 1097 } 1098 } 1099 } 1100 1101 #if defined(UNITTEST) 1102 1103 #include <inttypes.h> 1104 #include <stdio.h> 1105 1106 static void 1107 radix_tree_dump_node(const struct radix_tree *t, void *vp, 1108 uint64_t offset, unsigned int height) 1109 { 1110 struct radix_tree_node *n; 1111 unsigned int i; 1112 1113 for (i = 0; i < t->t_height - height; i++) { 1114 printf(" "); 1115 } 1116 if (entry_tagmask(vp) == 0) { 1117 printf("[%" PRIu64 "] %p", offset, entry_ptr(vp)); 1118 } else { 1119 printf("[%" PRIu64 "] %p (tagmask=0x%x)", offset, entry_ptr(vp), 1120 entry_tagmask(vp)); 1121 } 1122 if (height == 0) { 1123 printf(" (leaf)\n"); 1124 return; 1125 } 1126 n = entry_ptr(vp); 1127 assert(any_children_tagmask(n) == entry_tagmask(vp)); 1128 printf(" (%u children)\n", radix_tree_node_count_ptrs(n)); 1129 for (i = 0; i < __arraycount(n->n_ptrs); i++) { 1130 void *c; 1131 1132 c = n->n_ptrs[i]; 1133 if (c == NULL) { 1134 continue; 1135 } 1136 radix_tree_dump_node(t, c, 1137 offset + i * (UINT64_C(1) << 1138 (RADIX_TREE_BITS_PER_HEIGHT * (height - 1))), height - 1); 1139 } 1140 } 1141 1142 void radix_tree_dump(const struct radix_tree *); 1143 1144 void 1145 radix_tree_dump(const struct radix_tree *t) 1146 { 1147 1148 printf("tree %p height=%u\n", t, t->t_height); 1149 radix_tree_dump_node(t, t->t_root, 0, t->t_height); 1150 } 1151 1152 static void 1153 test1(void) 1154 { 1155 struct radix_tree s; 1156 struct radix_tree *t = &s; 1157 void *results[3]; 1158 1159 radix_tree_init_tree(t); 1160 radix_tree_dump(t); 1161 assert(radix_tree_lookup_node(t, 0) == NULL); 1162 assert(radix_tree_lookup_node(t, 1000) == NULL); 1163 assert(radix_tree_gang_lookup_node(t, 0, results, 3, false) == 0); 1164 assert(radix_tree_gang_lookup_node(t, 0, results, 3, true) == 0); 1165 assert(radix_tree_gang_lookup_node(t, 1000, results, 3, false) == 0); 1166 assert(radix_tree_gang_lookup_node(t, 1000, results, 3, true) == 0); 1167 assert(radix_tree_gang_lookup_node_reverse(t, 0, results, 3, false) == 1168 0); 1169 assert(radix_tree_gang_lookup_node_reverse(t, 0, results, 3, true) == 1170 0); 1171 assert(radix_tree_gang_lookup_node_reverse(t, 1000, results, 3, false) 1172 == 0); 1173 assert(radix_tree_gang_lookup_node_reverse(t, 1000, results, 3, true) 1174 == 0); 1175 assert(radix_tree_gang_lookup_tagged_node(t, 0, results, 3, false, 1) 1176 == 0); 1177 assert(radix_tree_gang_lookup_tagged_node(t, 0, results, 3, true, 1) 1178 == 0); 1179 assert(radix_tree_gang_lookup_tagged_node(t, 1000, results, 3, false, 1) 1180 == 0); 1181 assert(radix_tree_gang_lookup_tagged_node(t, 1000, results, 3, true, 1) 1182 == 0); 1183 assert(radix_tree_gang_lookup_tagged_node_reverse(t, 0, results, 3, 1184 false, 1) == 0); 1185 assert(radix_tree_gang_lookup_tagged_node_reverse(t, 0, results, 3, 1186 true, 1) == 0); 1187 assert(radix_tree_gang_lookup_tagged_node_reverse(t, 1000, results, 3, 1188 false, 1) == 0); 1189 assert(radix_tree_gang_lookup_tagged_node_reverse(t, 1000, results, 3, 1190 true, 1) == 0); 1191 assert(radix_tree_empty_tree_p(t)); 1192 assert(radix_tree_empty_tagged_tree_p(t, 1)); 1193 assert(radix_tree_empty_tagged_tree_p(t, 2)); 1194 assert(radix_tree_insert_node(t, 0, (void *)0xdeadbea0) == 0); 1195 assert(!radix_tree_empty_tree_p(t)); 1196 assert(radix_tree_empty_tagged_tree_p(t, 1)); 1197 assert(radix_tree_empty_tagged_tree_p(t, 2)); 1198 assert(radix_tree_lookup_node(t, 0) == (void *)0xdeadbea0); 1199 assert(radix_tree_lookup_node(t, 1000) == NULL); 1200 memset(results, 0, sizeof(results)); 1201 assert(radix_tree_gang_lookup_node(t, 0, results, 3, false) == 1); 1202 assert(results[0] == (void *)0xdeadbea0); 1203 memset(results, 0, sizeof(results)); 1204 assert(radix_tree_gang_lookup_node(t, 0, results, 3, true) == 1); 1205 assert(results[0] == (void *)0xdeadbea0); 1206 assert(radix_tree_gang_lookup_node(t, 1000, results, 3, false) == 0); 1207 assert(radix_tree_gang_lookup_node(t, 1000, results, 3, true) == 0); 1208 memset(results, 0, sizeof(results)); 1209 assert(radix_tree_gang_lookup_node_reverse(t, 0, results, 3, false) == 1210 1); 1211 assert(results[0] == (void *)0xdeadbea0); 1212 memset(results, 0, sizeof(results)); 1213 assert(radix_tree_gang_lookup_node_reverse(t, 0, results, 3, true) == 1214 1); 1215 assert(results[0] == (void *)0xdeadbea0); 1216 memset(results, 0, sizeof(results)); 1217 assert(radix_tree_gang_lookup_node_reverse(t, 1000, results, 3, false) 1218 == 1); 1219 assert(results[0] == (void *)0xdeadbea0); 1220 assert(radix_tree_gang_lookup_node_reverse(t, 1000, results, 3, true) 1221 == 0); 1222 assert(radix_tree_gang_lookup_tagged_node(t, 0, results, 3, false, 1) 1223 == 0); 1224 assert(radix_tree_gang_lookup_tagged_node(t, 0, results, 3, true, 1) 1225 == 0); 1226 assert(radix_tree_gang_lookup_tagged_node_reverse(t, 0, results, 3, 1227 false, 1) == 0); 1228 assert(radix_tree_gang_lookup_tagged_node_reverse(t, 0, results, 3, 1229 true, 1) == 0); 1230 assert(radix_tree_insert_node(t, 1000, (void *)0xdeadbea0) == 0); 1231 assert(radix_tree_remove_node(t, 0) == (void *)0xdeadbea0); 1232 assert(!radix_tree_empty_tree_p(t)); 1233 radix_tree_dump(t); 1234 assert(radix_tree_lookup_node(t, 0) == NULL); 1235 assert(radix_tree_lookup_node(t, 1000) == (void *)0xdeadbea0); 1236 memset(results, 0, sizeof(results)); 1237 assert(radix_tree_gang_lookup_node(t, 0, results, 3, false) == 1); 1238 assert(results[0] == (void *)0xdeadbea0); 1239 assert(radix_tree_gang_lookup_node(t, 0, results, 3, true) == 0); 1240 memset(results, 0, sizeof(results)); 1241 assert(radix_tree_gang_lookup_node(t, 1000, results, 3, false) == 1); 1242 assert(results[0] == (void *)0xdeadbea0); 1243 memset(results, 0, sizeof(results)); 1244 assert(radix_tree_gang_lookup_node(t, 1000, results, 3, true) == 1); 1245 assert(results[0] == (void *)0xdeadbea0); 1246 assert(radix_tree_gang_lookup_node_reverse(t, 0, results, 3, false) 1247 == 0); 1248 assert(radix_tree_gang_lookup_node_reverse(t, 0, results, 3, true) 1249 == 0); 1250 memset(results, 0, sizeof(results)); 1251 assert(radix_tree_gang_lookup_node_reverse(t, 1000, results, 3, false) 1252 == 1); 1253 memset(results, 0, sizeof(results)); 1254 assert(radix_tree_gang_lookup_node_reverse(t, 1000, results, 3, true) 1255 == 1); 1256 assert(results[0] == (void *)0xdeadbea0); 1257 assert(radix_tree_gang_lookup_tagged_node(t, 0, results, 3, false, 1) 1258 == 0); 1259 assert(radix_tree_gang_lookup_tagged_node(t, 0, results, 3, true, 1) 1260 == 0); 1261 assert(radix_tree_gang_lookup_tagged_node_reverse(t, 0, results, 3, 1262 false, 1) == 0); 1263 assert(radix_tree_gang_lookup_tagged_node_reverse(t, 0, results, 3, 1264 true, 1) == 0); 1265 assert(!radix_tree_get_tag(t, 1000, 1)); 1266 assert(!radix_tree_get_tag(t, 1000, 2)); 1267 assert(radix_tree_get_tag(t, 1000, 2 | 1) == 0); 1268 assert(radix_tree_empty_tagged_tree_p(t, 1)); 1269 assert(radix_tree_empty_tagged_tree_p(t, 2)); 1270 radix_tree_set_tag(t, 1000, 2); 1271 assert(!radix_tree_get_tag(t, 1000, 1)); 1272 assert(radix_tree_get_tag(t, 1000, 2)); 1273 assert(radix_tree_get_tag(t, 1000, 2 | 1) == 2); 1274 assert(radix_tree_empty_tagged_tree_p(t, 1)); 1275 assert(!radix_tree_empty_tagged_tree_p(t, 2)); 1276 radix_tree_dump(t); 1277 assert(radix_tree_lookup_node(t, 1000) == (void *)0xdeadbea0); 1278 assert(radix_tree_insert_node(t, 0, (void *)0xbea0) == 0); 1279 radix_tree_dump(t); 1280 assert(radix_tree_lookup_node(t, 0) == (void *)0xbea0); 1281 assert(radix_tree_lookup_node(t, 1000) == (void *)0xdeadbea0); 1282 assert(radix_tree_insert_node(t, UINT64_C(10000000000), (void *)0xdea0) 1283 == 0); 1284 radix_tree_dump(t); 1285 assert(radix_tree_lookup_node(t, 0) == (void *)0xbea0); 1286 assert(radix_tree_lookup_node(t, 1000) == (void *)0xdeadbea0); 1287 assert(radix_tree_lookup_node(t, UINT64_C(10000000000)) == 1288 (void *)0xdea0); 1289 radix_tree_dump(t); 1290 assert(!radix_tree_get_tag(t, 0, 2)); 1291 assert(radix_tree_get_tag(t, 1000, 2)); 1292 assert(!radix_tree_get_tag(t, UINT64_C(10000000000), 1)); 1293 radix_tree_set_tag(t, 0, 2);; 1294 radix_tree_set_tag(t, UINT64_C(10000000000), 2); 1295 radix_tree_dump(t); 1296 assert(radix_tree_get_tag(t, 0, 2)); 1297 assert(radix_tree_get_tag(t, 1000, 2)); 1298 assert(radix_tree_get_tag(t, UINT64_C(10000000000), 2)); 1299 radix_tree_clear_tag(t, 0, 2);; 1300 radix_tree_clear_tag(t, UINT64_C(10000000000), 2); 1301 radix_tree_dump(t); 1302 assert(!radix_tree_get_tag(t, 0, 2)); 1303 assert(radix_tree_get_tag(t, 1000, 2)); 1304 assert(!radix_tree_get_tag(t, UINT64_C(10000000000), 2)); 1305 radix_tree_dump(t); 1306 assert(radix_tree_replace_node(t, 1000, (void *)0x12345678) == 1307 (void *)0xdeadbea0); 1308 assert(!radix_tree_get_tag(t, 1000, 1)); 1309 assert(radix_tree_get_tag(t, 1000, 2)); 1310 assert(radix_tree_get_tag(t, 1000, 2 | 1) == 2); 1311 memset(results, 0, sizeof(results)); 1312 assert(radix_tree_gang_lookup_node(t, 0, results, 3, false) == 3); 1313 assert(results[0] == (void *)0xbea0); 1314 assert(results[1] == (void *)0x12345678); 1315 assert(results[2] == (void *)0xdea0); 1316 memset(results, 0, sizeof(results)); 1317 assert(radix_tree_gang_lookup_node(t, 0, results, 3, true) == 1); 1318 assert(results[0] == (void *)0xbea0); 1319 memset(results, 0, sizeof(results)); 1320 assert(radix_tree_gang_lookup_node(t, 1, results, 3, false) == 2); 1321 assert(results[0] == (void *)0x12345678); 1322 assert(results[1] == (void *)0xdea0); 1323 assert(radix_tree_gang_lookup_node(t, 1, results, 3, true) == 0); 1324 memset(results, 0, sizeof(results)); 1325 assert(radix_tree_gang_lookup_node(t, 1001, results, 3, false) == 1); 1326 assert(results[0] == (void *)0xdea0); 1327 assert(radix_tree_gang_lookup_node(t, 1001, results, 3, true) == 0); 1328 assert(radix_tree_gang_lookup_node(t, UINT64_C(10000000001), results, 3, 1329 false) == 0); 1330 assert(radix_tree_gang_lookup_node(t, UINT64_C(10000000001), results, 3, 1331 true) == 0); 1332 assert(radix_tree_gang_lookup_node(t, UINT64_C(1000000000000), results, 1333 3, false) == 0); 1334 assert(radix_tree_gang_lookup_node(t, UINT64_C(1000000000000), results, 1335 3, true) == 0); 1336 memset(results, 0, sizeof(results)); 1337 assert(radix_tree_gang_lookup_tagged_node(t, 0, results, 100, false, 2) 1338 == 1); 1339 assert(results[0] == (void *)0x12345678); 1340 assert(radix_tree_gang_lookup_tagged_node(t, 0, results, 100, true, 2) 1341 == 0); 1342 assert(entry_tagmask(t->t_root) != 0); 1343 assert(radix_tree_remove_node(t, 1000) == (void *)0x12345678); 1344 assert(entry_tagmask(t->t_root) == 0); 1345 radix_tree_dump(t); 1346 assert(radix_tree_insert_node(t, UINT64_C(10000000001), (void *)0xfff0) 1347 == 0); 1348 memset(results, 0, sizeof(results)); 1349 assert(radix_tree_gang_lookup_node(t, UINT64_C(10000000000), results, 3, 1350 false) == 2); 1351 assert(results[0] == (void *)0xdea0); 1352 assert(results[1] == (void *)0xfff0); 1353 memset(results, 0, sizeof(results)); 1354 assert(radix_tree_gang_lookup_node(t, UINT64_C(10000000000), results, 3, 1355 true) == 2); 1356 assert(results[0] == (void *)0xdea0); 1357 assert(results[1] == (void *)0xfff0); 1358 memset(results, 0, sizeof(results)); 1359 assert(radix_tree_gang_lookup_node_reverse(t, UINT64_C(10000000001), 1360 results, 3, false) == 3); 1361 assert(results[0] == (void *)0xfff0); 1362 assert(results[1] == (void *)0xdea0); 1363 assert(results[2] == (void *)0xbea0); 1364 memset(results, 0, sizeof(results)); 1365 assert(radix_tree_gang_lookup_node_reverse(t, UINT64_C(10000000001), 1366 results, 3, true) == 2); 1367 assert(results[0] == (void *)0xfff0); 1368 assert(results[1] == (void *)0xdea0); 1369 assert(radix_tree_remove_node(t, UINT64_C(10000000000)) == 1370 (void *)0xdea0); 1371 assert(radix_tree_remove_node(t, UINT64_C(10000000001)) == 1372 (void *)0xfff0); 1373 radix_tree_dump(t); 1374 assert(radix_tree_remove_node(t, 0) == (void *)0xbea0); 1375 radix_tree_dump(t); 1376 radix_tree_fini_tree(t); 1377 } 1378 1379 #include <sys/time.h> 1380 1381 struct testnode { 1382 uint64_t idx; 1383 bool tagged[RADIX_TREE_TAG_ID_MAX]; 1384 }; 1385 1386 static void 1387 printops(const char *title, const char *name, int tag, unsigned int n, 1388 const struct timeval *stv, const struct timeval *etv) 1389 { 1390 uint64_t s = stv->tv_sec * 1000000 + stv->tv_usec; 1391 uint64_t e = etv->tv_sec * 1000000 + etv->tv_usec; 1392 1393 printf("RESULT %s %s %d %lf op/s\n", title, name, tag, 1394 (double)n / (e - s) * 1000000); 1395 } 1396 1397 #define TEST2_GANG_LOOKUP_NODES 16 1398 1399 static bool 1400 test2_should_tag(unsigned int i, unsigned int tagid) 1401 { 1402 1403 if (tagid == 0) { 1404 return (i % 4) == 0; /* 25% */ 1405 } else { 1406 return (i % 7) == 0; /* 14% */ 1407 } 1408 return 1; 1409 } 1410 1411 static void 1412 check_tag_count(const unsigned int *ntagged, unsigned int tagmask, 1413 unsigned int count) 1414 { 1415 unsigned int tag; 1416 1417 for (tag = 0; tag < RADIX_TREE_TAG_ID_MAX; tag++) { 1418 if ((tagmask & (1 << tag)) == 0) { 1419 continue; 1420 } 1421 if (((tagmask - 1) & tagmask) == 0) { 1422 assert(count == ntagged[tag]); 1423 } else { 1424 assert(count >= ntagged[tag]); 1425 } 1426 } 1427 } 1428 1429 static void 1430 test2(const char *title, bool dense) 1431 { 1432 struct radix_tree s; 1433 struct radix_tree *t = &s; 1434 struct testnode *n; 1435 unsigned int i; 1436 unsigned int nnodes = 100000; 1437 unsigned int removed; 1438 unsigned int tag; 1439 unsigned int tagmask; 1440 unsigned int ntagged[RADIX_TREE_TAG_ID_MAX]; 1441 struct testnode *nodes; 1442 struct timeval stv; 1443 struct timeval etv; 1444 1445 nodes = malloc(nnodes * sizeof(*nodes)); 1446 for (tag = 0; tag < RADIX_TREE_TAG_ID_MAX; tag++) { 1447 ntagged[tag] = 0; 1448 } 1449 radix_tree_init_tree(t); 1450 for (i = 0; i < nnodes; i++) { 1451 n = &nodes[i]; 1452 n->idx = random(); 1453 if (sizeof(long) == 4) { 1454 n->idx <<= 32; 1455 n->idx |= (uint32_t)random(); 1456 } 1457 if (dense) { 1458 n->idx %= nnodes * 2; 1459 } 1460 while (radix_tree_lookup_node(t, n->idx) != NULL) { 1461 n->idx++; 1462 } 1463 radix_tree_insert_node(t, n->idx, n); 1464 for (tag = 0; tag < RADIX_TREE_TAG_ID_MAX; tag++) { 1465 tagmask = 1 << tag; 1466 1467 n->tagged[tag] = test2_should_tag(i, tag); 1468 if (n->tagged[tag]) { 1469 radix_tree_set_tag(t, n->idx, tagmask); 1470 ntagged[tag]++; 1471 } 1472 assert((n->tagged[tag] ? tagmask : 0) == 1473 radix_tree_get_tag(t, n->idx, tagmask)); 1474 } 1475 } 1476 1477 gettimeofday(&stv, NULL); 1478 for (i = 0; i < nnodes; i++) { 1479 n = &nodes[i]; 1480 assert(radix_tree_lookup_node(t, n->idx) == n); 1481 } 1482 gettimeofday(&etv, NULL); 1483 printops(title, "lookup", 0, nnodes, &stv, &etv); 1484 1485 for (tagmask = 1; tagmask <= RADIX_TREE_TAG_MASK; tagmask ++) { 1486 unsigned int count = 0; 1487 1488 gettimeofday(&stv, NULL); 1489 for (i = 0; i < nnodes; i++) { 1490 unsigned int tagged; 1491 1492 n = &nodes[i]; 1493 tagged = radix_tree_get_tag(t, n->idx, tagmask); 1494 assert((tagged & ~tagmask) == 0); 1495 for (tag = 0; tag < RADIX_TREE_TAG_ID_MAX; tag++) { 1496 assert((tagmask & (1 << tag)) == 0 || 1497 n->tagged[tag] == !!(tagged & (1 << tag))); 1498 } 1499 if (tagged) { 1500 count++; 1501 } 1502 } 1503 gettimeofday(&etv, NULL); 1504 check_tag_count(ntagged, tagmask, count); 1505 printops(title, "get_tag", tagmask, nnodes, &stv, &etv); 1506 } 1507 1508 gettimeofday(&stv, NULL); 1509 for (i = 0; i < nnodes; i++) { 1510 n = &nodes[i]; 1511 radix_tree_remove_node(t, n->idx); 1512 } 1513 gettimeofday(&etv, NULL); 1514 printops(title, "remove", 0, nnodes, &stv, &etv); 1515 1516 gettimeofday(&stv, NULL); 1517 for (i = 0; i < nnodes; i++) { 1518 n = &nodes[i]; 1519 radix_tree_insert_node(t, n->idx, n); 1520 } 1521 gettimeofday(&etv, NULL); 1522 printops(title, "insert", 0, nnodes, &stv, &etv); 1523 1524 for (tag = 0; tag < RADIX_TREE_TAG_ID_MAX; tag++) { 1525 tagmask = 1 << tag; 1526 1527 ntagged[tag] = 0; 1528 gettimeofday(&stv, NULL); 1529 for (i = 0; i < nnodes; i++) { 1530 n = &nodes[i]; 1531 if (n->tagged[tag]) { 1532 radix_tree_set_tag(t, n->idx, tagmask); 1533 ntagged[tag]++; 1534 } 1535 } 1536 gettimeofday(&etv, NULL); 1537 printops(title, "set_tag", tag, ntagged[tag], &stv, &etv); 1538 } 1539 1540 gettimeofday(&stv, NULL); 1541 { 1542 struct testnode *results[TEST2_GANG_LOOKUP_NODES]; 1543 uint64_t nextidx; 1544 unsigned int nfound; 1545 unsigned int total; 1546 1547 nextidx = 0; 1548 total = 0; 1549 while ((nfound = radix_tree_gang_lookup_node(t, nextidx, 1550 (void *)results, __arraycount(results), false)) > 0) { 1551 nextidx = results[nfound - 1]->idx + 1; 1552 total += nfound; 1553 if (nextidx == 0) { 1554 break; 1555 } 1556 } 1557 assert(total == nnodes); 1558 } 1559 gettimeofday(&etv, NULL); 1560 printops(title, "ganglookup", 0, nnodes, &stv, &etv); 1561 1562 gettimeofday(&stv, NULL); 1563 { 1564 struct testnode *results[TEST2_GANG_LOOKUP_NODES]; 1565 uint64_t nextidx; 1566 unsigned int nfound; 1567 unsigned int total; 1568 1569 nextidx = UINT64_MAX; 1570 total = 0; 1571 while ((nfound = radix_tree_gang_lookup_node_reverse(t, nextidx, 1572 (void *)results, __arraycount(results), false)) > 0) { 1573 nextidx = results[nfound - 1]->idx - 1; 1574 total += nfound; 1575 if (nextidx == UINT64_MAX) { 1576 break; 1577 } 1578 } 1579 assert(total == nnodes); 1580 } 1581 gettimeofday(&etv, NULL); 1582 printops(title, "ganglookup_reverse", 0, nnodes, &stv, &etv); 1583 1584 for (tagmask = 1; tagmask <= RADIX_TREE_TAG_MASK; tagmask ++) { 1585 unsigned int total = 0; 1586 1587 gettimeofday(&stv, NULL); 1588 { 1589 struct testnode *results[TEST2_GANG_LOOKUP_NODES]; 1590 uint64_t nextidx; 1591 unsigned int nfound; 1592 1593 nextidx = 0; 1594 while ((nfound = radix_tree_gang_lookup_tagged_node(t, 1595 nextidx, (void *)results, __arraycount(results), 1596 false, tagmask)) > 0) { 1597 nextidx = results[nfound - 1]->idx + 1; 1598 total += nfound; 1599 } 1600 } 1601 gettimeofday(&etv, NULL); 1602 check_tag_count(ntagged, tagmask, total); 1603 assert(tagmask != 0 || total == 0); 1604 printops(title, "ganglookup_tag", tagmask, total, &stv, &etv); 1605 } 1606 1607 for (tagmask = 1; tagmask <= RADIX_TREE_TAG_MASK; tagmask ++) { 1608 unsigned int total = 0; 1609 1610 gettimeofday(&stv, NULL); 1611 { 1612 struct testnode *results[TEST2_GANG_LOOKUP_NODES]; 1613 uint64_t nextidx; 1614 unsigned int nfound; 1615 1616 nextidx = UINT64_MAX; 1617 while ((nfound = 1618 radix_tree_gang_lookup_tagged_node_reverse(t, 1619 nextidx, (void *)results, __arraycount(results), 1620 false, tagmask)) > 0) { 1621 nextidx = results[nfound - 1]->idx - 1; 1622 total += nfound; 1623 if (nextidx == UINT64_MAX) { 1624 break; 1625 } 1626 } 1627 } 1628 gettimeofday(&etv, NULL); 1629 check_tag_count(ntagged, tagmask, total); 1630 assert(tagmask != 0 || total == 0); 1631 printops(title, "ganglookup_tag_reverse", tagmask, total, 1632 &stv, &etv); 1633 } 1634 1635 removed = 0; 1636 for (tag = 0; tag < RADIX_TREE_TAG_ID_MAX; tag++) { 1637 unsigned int total; 1638 1639 total = 0; 1640 tagmask = 1 << tag; 1641 gettimeofday(&stv, NULL); 1642 { 1643 struct testnode *results[TEST2_GANG_LOOKUP_NODES]; 1644 uint64_t nextidx; 1645 unsigned int nfound; 1646 1647 nextidx = 0; 1648 while ((nfound = radix_tree_gang_lookup_tagged_node(t, 1649 nextidx, (void *)results, __arraycount(results), 1650 false, tagmask)) > 0) { 1651 for (i = 0; i < nfound; i++) { 1652 radix_tree_remove_node(t, 1653 results[i]->idx); 1654 } 1655 nextidx = results[nfound - 1]->idx + 1; 1656 total += nfound; 1657 if (nextidx == 0) { 1658 break; 1659 } 1660 } 1661 } 1662 gettimeofday(&etv, NULL); 1663 if (tag == 0) { 1664 check_tag_count(ntagged, tagmask, total); 1665 } else { 1666 assert(total <= ntagged[tag]); 1667 } 1668 printops(title, "ganglookup_tag+remove", tagmask, total, &stv, 1669 &etv); 1670 removed += total; 1671 } 1672 1673 gettimeofday(&stv, NULL); 1674 { 1675 struct testnode *results[TEST2_GANG_LOOKUP_NODES]; 1676 uint64_t nextidx; 1677 unsigned int nfound; 1678 unsigned int total; 1679 1680 nextidx = 0; 1681 total = 0; 1682 while ((nfound = radix_tree_gang_lookup_node(t, nextidx, 1683 (void *)results, __arraycount(results), false)) > 0) { 1684 for (i = 0; i < nfound; i++) { 1685 assert(results[i] == radix_tree_remove_node(t, 1686 results[i]->idx)); 1687 } 1688 nextidx = results[nfound - 1]->idx + 1; 1689 total += nfound; 1690 if (nextidx == 0) { 1691 break; 1692 } 1693 } 1694 assert(total == nnodes - removed); 1695 } 1696 gettimeofday(&etv, NULL); 1697 printops(title, "ganglookup+remove", 0, nnodes - removed, &stv, &etv); 1698 1699 assert(radix_tree_empty_tree_p(t)); 1700 for (tagmask = 1; tagmask <= RADIX_TREE_TAG_MASK; tagmask ++) { 1701 assert(radix_tree_empty_tagged_tree_p(t, tagmask)); 1702 } 1703 radix_tree_fini_tree(t); 1704 free(nodes); 1705 } 1706 1707 int 1708 main(int argc, char *argv[]) 1709 { 1710 1711 test1(); 1712 test2("dense", true); 1713 test2("sparse", false); 1714 return 0; 1715 } 1716 1717 #endif /* defined(UNITTEST) */ 1718