radixtree.c revision 1.4
1 /* $NetBSD: radixtree.c,v 1.4 2011/05/19 09:58:28 yamt Exp $ */ 2 3 /*- 4 * Copyright (c)2011 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 * radix tree 31 * 32 * it's designed to work efficiently with dense index distribution. 33 * the memory consumption (number of necessary intermediate nodes) 34 * heavily depends on index distribution. basically, more dense index 35 * distribution consumes less nodes per item. 36 * approximately, 37 * the best case: about RADIX_TREE_PTR_PER_NODE items per node. 38 * the worst case: RADIX_TREE_MAX_HEIGHT nodes per item. 39 */ 40 41 #include <sys/cdefs.h> 42 43 #if defined(_KERNEL) || defined(_STANDALONE) 44 __KERNEL_RCSID(0, "$NetBSD: radixtree.c,v 1.4 2011/05/19 09:58:28 yamt Exp $"); 45 #include <sys/param.h> 46 #include <sys/errno.h> 47 #include <sys/pool.h> 48 #include <sys/radixtree.h> 49 #include <lib/libkern/libkern.h> 50 #if defined(_STANDALONE) 51 #include <lib/libsa/stand.h> 52 #endif /* defined(_STANDALONE) */ 53 #else /* defined(_KERNEL) || defined(_STANDALONE) */ 54 __RCSID("$NetBSD: radixtree.c,v 1.4 2011/05/19 09:58:28 yamt Exp $"); 55 #include <assert.h> 56 #include <errno.h> 57 #include <stdbool.h> 58 #include <stdlib.h> 59 #if 1 60 #define KASSERT assert 61 #else 62 #define KASSERT(a) /* nothing */ 63 #endif 64 #endif /* defined(_KERNEL) || defined(_STANDALONE) */ 65 66 #include <sys/radixtree.h> 67 68 #define RADIX_TREE_BITS_PER_HEIGHT 4 /* XXX tune */ 69 #define RADIX_TREE_PTR_PER_NODE (1 << RADIX_TREE_BITS_PER_HEIGHT) 70 #define RADIX_TREE_MAX_HEIGHT (64 / RADIX_TREE_BITS_PER_HEIGHT) 71 __CTASSERT((64 % RADIX_TREE_BITS_PER_HEIGHT) == 0); 72 73 __CTASSERT(((1 << RADIX_TREE_TAG_ID_MAX) & (sizeof(int) - 1)) == 0); 74 #define RADIX_TREE_TAG_MASK ((1 << RADIX_TREE_TAG_ID_MAX) - 1) 75 76 static inline void * 77 entry_ptr(void *p) 78 { 79 80 return (void *)((uintptr_t)p & ~RADIX_TREE_TAG_MASK); 81 } 82 83 static inline unsigned int 84 entry_tagmask(void *p) 85 { 86 87 return (uintptr_t)p & RADIX_TREE_TAG_MASK; 88 } 89 90 static inline void * 91 entry_compose(void *p, unsigned int tagmask) 92 { 93 94 return (void *)((uintptr_t)p | tagmask); 95 } 96 97 static inline bool 98 entry_match_p(void *p, unsigned int tagmask) 99 { 100 101 KASSERT(entry_ptr(p) != NULL || entry_tagmask(p) == 0); 102 if (p == NULL) { 103 return false; 104 } 105 if (tagmask == 0) { 106 return true; 107 } 108 return (entry_tagmask(p) & tagmask) != 0; 109 } 110 111 static inline unsigned int 112 tagid_to_mask(radix_tree_tagid_t id) 113 { 114 115 return 1U << id; 116 } 117 118 /* 119 * radix_tree_node: an intermediate node 120 * 121 * we don't care the type of leaf nodes. they are just void *. 122 */ 123 124 struct radix_tree_node { 125 void *n_ptrs[RADIX_TREE_PTR_PER_NODE]; 126 unsigned int n_nptrs; /* # of non-NULL pointers in n_ptrs */ 127 }; 128 129 static unsigned int 130 any_children_tagmask(struct radix_tree_node *n) 131 { 132 unsigned int mask; 133 int i; 134 135 mask = 0; 136 for (i = 0; i < RADIX_TREE_PTR_PER_NODE; i++) { 137 mask |= (unsigned int)(uintptr_t)n->n_ptrs[i]; 138 } 139 return mask & RADIX_TREE_TAG_MASK; 140 } 141 142 /* 143 * p_refs[0].pptr == &t->t_root 144 * : 145 * p_refs[n].pptr == &(*p_refs[n-1])->n_ptrs[x] 146 * : 147 * : 148 * p_refs[t->t_height].pptr == &leaf_pointer 149 */ 150 151 struct radix_tree_path { 152 struct radix_tree_node_ref { 153 void **pptr; 154 } p_refs[RADIX_TREE_MAX_HEIGHT + 1]; /* +1 for the root ptr */ 155 int p_lastidx; 156 }; 157 158 static inline void ** 159 path_pptr(struct radix_tree *t, struct radix_tree_path *p, 160 unsigned int height) 161 { 162 163 KASSERT(height <= t->t_height); 164 return p->p_refs[height].pptr; 165 } 166 167 static inline struct radix_tree_node * 168 path_node(struct radix_tree * t, struct radix_tree_path *p, unsigned int height) 169 { 170 171 KASSERT(height <= t->t_height); 172 return entry_ptr(*path_pptr(t, p, height)); 173 } 174 175 static inline unsigned int 176 path_idx(struct radix_tree * t, struct radix_tree_path *p, unsigned int height) 177 { 178 179 KASSERT(height <= t->t_height); 180 return path_pptr(t, p, height + 1) - path_node(t, p, height)->n_ptrs; 181 } 182 183 /* 184 * radix_tree_init_tree: 185 * 186 * initialize a tree. 187 */ 188 189 void 190 radix_tree_init_tree(struct radix_tree *t) 191 { 192 193 t->t_height = 0; 194 t->t_root = NULL; 195 } 196 197 /* 198 * radix_tree_init_tree: 199 * 200 * clean up a tree. 201 */ 202 203 void 204 radix_tree_fini_tree(struct radix_tree *t) 205 { 206 207 KASSERT(t->t_root == NULL); 208 KASSERT(t->t_height == 0); 209 } 210 211 static void 212 radix_tree_node_init(struct radix_tree_node *n) 213 { 214 215 memset(n, 0, sizeof(*n)); 216 } 217 218 #if defined(_KERNEL) 219 pool_cache_t radix_tree_node_cache __read_mostly; 220 221 static int 222 radix_tree_node_ctor(void *dummy, void *item, int flags) 223 { 224 struct radix_tree_node *n = item; 225 226 KASSERT(dummy == NULL); 227 radix_tree_node_init(n); 228 return 0; 229 } 230 231 /* 232 * radix_tree_init: 233 * 234 * initialize the subsystem. 235 */ 236 237 void 238 radix_tree_init(void) 239 { 240 241 radix_tree_node_cache = pool_cache_init(sizeof(struct radix_tree_node), 242 0, 0, 0, "radix_tree_node", NULL, IPL_NONE, radix_tree_node_ctor, 243 NULL, NULL); 244 KASSERT(radix_tree_node_cache != NULL); 245 } 246 #endif /* defined(_KERNEL) */ 247 248 static bool __unused 249 radix_tree_node_clean_p(const struct radix_tree_node *n) 250 { 251 unsigned int i; 252 253 if (n->n_nptrs != 0) { 254 return false; 255 } 256 for (i = 0; i < RADIX_TREE_PTR_PER_NODE; i++) { 257 if (n->n_ptrs[i] != NULL) { 258 return false; 259 } 260 } 261 return true; 262 } 263 264 static struct radix_tree_node * 265 radix_tree_alloc_node(void) 266 { 267 struct radix_tree_node *n; 268 269 #if defined(_KERNEL) 270 n = pool_cache_get(radix_tree_node_cache, PR_NOWAIT); 271 #else /* defined(_KERNEL) */ 272 #if defined(_STANDALONE) 273 n = alloc(sizeof(*n)); 274 #else /* defined(_STANDALONE) */ 275 n = malloc(sizeof(*n)); 276 #endif /* defined(_STANDALONE) */ 277 if (n != NULL) { 278 radix_tree_node_init(n); 279 } 280 #endif /* defined(_KERNEL) */ 281 KASSERT(n == NULL || radix_tree_node_clean_p(n)); 282 return n; 283 } 284 285 static void 286 radix_tree_free_node(struct radix_tree_node *n) 287 { 288 289 KASSERT(radix_tree_node_clean_p(n)); 290 #if defined(_KERNEL) 291 pool_cache_put(radix_tree_node_cache, n); 292 #elif defined(_STANDALONE) 293 dealloc(n, sizeof(*n)); 294 #else 295 free(n); 296 #endif 297 } 298 299 static int 300 radix_tree_grow(struct radix_tree *t, unsigned int newheight) 301 { 302 const unsigned int tagmask = entry_tagmask(t->t_root); 303 304 KASSERT(newheight <= 64 / RADIX_TREE_BITS_PER_HEIGHT); 305 if (t->t_root == NULL) { 306 t->t_height = newheight; 307 return 0; 308 } 309 while (t->t_height < newheight) { 310 struct radix_tree_node *n; 311 312 n = radix_tree_alloc_node(); 313 if (n == NULL) { 314 /* 315 * don't bother to revert our changes. 316 * the caller will likely retry. 317 */ 318 return ENOMEM; 319 } 320 n->n_nptrs = 1; 321 n->n_ptrs[0] = t->t_root; 322 t->t_root = entry_compose(n, tagmask); 323 t->t_height++; 324 } 325 return 0; 326 } 327 328 static inline void ** 329 radix_tree_lookup_ptr(struct radix_tree *t, uint64_t idx, 330 struct radix_tree_path *path, bool alloc, const unsigned int tagmask) 331 { 332 struct radix_tree_node *n; 333 int hshift = RADIX_TREE_BITS_PER_HEIGHT * t->t_height; 334 int shift; 335 void **vpp; 336 const uint64_t mask = (UINT64_C(1) << RADIX_TREE_BITS_PER_HEIGHT) - 1; 337 struct radix_tree_node_ref *refs = NULL; 338 339 KASSERT(tagmask == 0 || !alloc); 340 KASSERT(path == NULL || !alloc); 341 vpp = &t->t_root; 342 if (path != NULL) { 343 refs = path->p_refs; 344 refs->pptr = vpp; 345 } 346 n = NULL; 347 for (shift = 64 - RADIX_TREE_BITS_PER_HEIGHT; shift >= 0;) { 348 struct radix_tree_node *c; 349 void *entry; 350 const uint64_t i = (idx >> shift) & mask; 351 352 if (shift >= hshift) { 353 unsigned int newheight; 354 355 KASSERT(vpp == &t->t_root); 356 if (i == 0) { 357 shift -= RADIX_TREE_BITS_PER_HEIGHT; 358 continue; 359 } 360 if (!alloc) { 361 if (path != NULL) { 362 KASSERT((refs - path->p_refs) == 0); 363 path->p_lastidx = 0; 364 } 365 return NULL; 366 } 367 newheight = shift / RADIX_TREE_BITS_PER_HEIGHT + 1; 368 if (radix_tree_grow(t, newheight)) { 369 return NULL; 370 } 371 hshift = RADIX_TREE_BITS_PER_HEIGHT * t->t_height; 372 } 373 entry = *vpp; 374 c = entry_ptr(entry); 375 if (c == NULL || 376 (tagmask != 0 && 377 (entry_tagmask(entry) & tagmask) == 0)) { 378 if (!alloc) { 379 if (path != NULL) { 380 path->p_lastidx = refs - path->p_refs; 381 } 382 return NULL; 383 } 384 c = radix_tree_alloc_node(); 385 if (c == NULL) { 386 return NULL; 387 } 388 *vpp = c; 389 if (n != NULL) { 390 KASSERT(n->n_nptrs < RADIX_TREE_PTR_PER_NODE); 391 n->n_nptrs++; 392 } 393 } 394 n = c; 395 vpp = &n->n_ptrs[i]; 396 if (path != NULL) { 397 refs++; 398 refs->pptr = vpp; 399 } 400 shift -= RADIX_TREE_BITS_PER_HEIGHT; 401 } 402 if (alloc) { 403 KASSERT(*vpp == NULL); 404 if (n != NULL) { 405 KASSERT(n->n_nptrs < RADIX_TREE_PTR_PER_NODE); 406 n->n_nptrs++; 407 } 408 } 409 if (path != NULL) { 410 path->p_lastidx = refs - path->p_refs; 411 } 412 return vpp; 413 } 414 415 /* 416 * radix_tree_insert_node: 417 * 418 * insert the node at idx. 419 * it's illegal to insert NULL. 420 * it's illegal to insert a non-aligned pointer. 421 * 422 * this function returns ENOMEM if necessary memory allocation failed. 423 * otherwise, this function returns 0. 424 * 425 * note that inserting a node can involves memory allocation for intermediate 426 * nodes. if _KERNEL, it's done with non-blocking IPL_NONE memory allocation. 427 * 428 * for the newly inserted node, all tags are cleared. 429 */ 430 431 int 432 radix_tree_insert_node(struct radix_tree *t, uint64_t idx, void *p) 433 { 434 void **vpp; 435 436 KASSERT(p != NULL); 437 KASSERT(entry_compose(p, 0) == p); 438 vpp = radix_tree_lookup_ptr(t, idx, NULL, true, 0); 439 if (vpp == NULL) { 440 return ENOMEM; 441 } 442 KASSERT(*vpp == NULL); 443 *vpp = p; 444 return 0; 445 } 446 447 /* 448 * radix_tree_replace_node: 449 * 450 * replace a node at the given index with the given node. 451 * return the old node. 452 * it's illegal to try to replace a node which has not been inserted. 453 * 454 * this function doesn't change tags. 455 */ 456 457 void * 458 radix_tree_replace_node(struct radix_tree *t, uint64_t idx, void *p) 459 { 460 void **vpp; 461 void *oldp; 462 463 KASSERT(p != NULL); 464 KASSERT(entry_compose(p, 0) == p); 465 vpp = radix_tree_lookup_ptr(t, idx, NULL, false, 0); 466 KASSERT(vpp != NULL); 467 oldp = *vpp; 468 KASSERT(oldp != NULL); 469 *vpp = entry_compose(p, entry_tagmask(*vpp)); 470 return entry_ptr(oldp); 471 } 472 473 /* 474 * radix_tree_remove_node: 475 * 476 * remove the node at idx. 477 * it's illegal to try to remove a node which has not been inserted. 478 */ 479 480 void * 481 radix_tree_remove_node(struct radix_tree *t, uint64_t idx) 482 { 483 struct radix_tree_path path; 484 void **vpp; 485 void *oldp; 486 int i; 487 488 vpp = radix_tree_lookup_ptr(t, idx, &path, false, 0); 489 KASSERT(vpp != NULL); 490 oldp = *vpp; 491 KASSERT(oldp != NULL); 492 KASSERT(path.p_lastidx == t->t_height); 493 KASSERT(vpp == path_pptr(t, &path, path.p_lastidx)); 494 *vpp = NULL; 495 for (i = t->t_height - 1; i >= 0; i--) { 496 void *entry; 497 struct radix_tree_node ** const pptr = 498 (struct radix_tree_node **)path_pptr(t, &path, i); 499 struct radix_tree_node *n; 500 501 KASSERT(pptr != NULL); 502 entry = *pptr; 503 n = entry_ptr(entry); 504 KASSERT(n != NULL); 505 KASSERT(n->n_nptrs > 0); 506 n->n_nptrs--; 507 if (n->n_nptrs > 0) { 508 break; 509 } 510 radix_tree_free_node(n); 511 *pptr = NULL; 512 } 513 /* 514 * fix up height 515 */ 516 if (i < 0) { 517 KASSERT(t->t_root == NULL); 518 t->t_height = 0; 519 } 520 /* 521 * update tags 522 */ 523 for (; i >= 0; i--) { 524 void *entry; 525 struct radix_tree_node ** const pptr = 526 (struct radix_tree_node **)path_pptr(t, &path, i); 527 struct radix_tree_node *n; 528 unsigned int newmask; 529 530 KASSERT(pptr != NULL); 531 entry = *pptr; 532 n = entry_ptr(entry); 533 KASSERT(n != NULL); 534 KASSERT(n->n_nptrs > 0); 535 newmask = any_children_tagmask(n); 536 if (newmask == entry_tagmask(entry)) { 537 break; 538 } 539 *pptr = entry_compose(n, newmask); 540 } 541 /* 542 * XXX is it worth to try to reduce height? 543 * if we do that, make radix_tree_grow rollback its change as well. 544 */ 545 return entry_ptr(oldp); 546 } 547 548 /* 549 * radix_tree_lookup_node: 550 * 551 * returns the node at idx. 552 * returns NULL if nothing is found at idx. 553 */ 554 555 void * 556 radix_tree_lookup_node(struct radix_tree *t, uint64_t idx) 557 { 558 void **vpp; 559 560 vpp = radix_tree_lookup_ptr(t, idx, NULL, false, 0); 561 if (vpp == NULL) { 562 return NULL; 563 } 564 return entry_ptr(*vpp); 565 } 566 567 static inline void 568 gang_lookup_init(struct radix_tree *t, uint64_t idx, 569 struct radix_tree_path *path, const unsigned int tagmask) 570 { 571 void **vpp; 572 573 vpp = radix_tree_lookup_ptr(t, idx, path, false, tagmask); 574 KASSERT(vpp == NULL || 575 vpp == path_pptr(t, path, path->p_lastidx)); 576 KASSERT(&t->t_root == path_pptr(t, path, 0)); 577 } 578 579 static inline unsigned int 580 gang_lookup_scan(struct radix_tree *t, struct radix_tree_path *path, 581 void **results, unsigned int maxresults, const unsigned int tagmask) 582 { 583 void **vpp; 584 int nfound; 585 unsigned int lastidx; 586 587 KASSERT(maxresults > 0); 588 lastidx = path->p_lastidx; 589 if (lastidx == 0) { 590 return 0; 591 } 592 nfound = 0; 593 vpp = path_pptr(t, path, lastidx); 594 while (/*CONSTCOND*/true) { 595 struct radix_tree_node *n; 596 int i; 597 598 if (entry_match_p(*vpp, tagmask)) { 599 KASSERT(lastidx == t->t_height); 600 /* 601 * record the non-NULL leaf. 602 */ 603 results[nfound] = entry_ptr(*vpp); 604 nfound++; 605 if (nfound == maxresults) { 606 return nfound; 607 } 608 } 609 scan_siblings: 610 /* 611 * try to find the next non-NULL sibling. 612 */ 613 n = path_node(t, path, lastidx - 1); 614 if (*vpp != NULL && n->n_nptrs == 1) { 615 /* 616 * optimization 617 */ 618 goto no_siblings; 619 } 620 for (i = path_idx(t, path, lastidx - 1) + 1; 621 i < RADIX_TREE_PTR_PER_NODE; 622 i++) { 623 if (entry_match_p(n->n_ptrs[i], tagmask)) { 624 vpp = &n->n_ptrs[i]; 625 path->p_refs[lastidx].pptr = vpp; 626 KASSERT(path_idx(t, path, lastidx - 1) 627 == i); 628 break; 629 } 630 } 631 if (i == RADIX_TREE_PTR_PER_NODE) { 632 no_siblings: 633 /* 634 * not found. go to parent. 635 */ 636 lastidx--; 637 if (lastidx == 0) { 638 return nfound; 639 } 640 vpp = path_pptr(t, path, lastidx); 641 goto scan_siblings; 642 } 643 /* 644 * descending the left-most child node, upto the leaf or NULL. 645 */ 646 while (entry_match_p(*vpp, tagmask) && lastidx < t->t_height) { 647 n = entry_ptr(*vpp); 648 vpp = &n->n_ptrs[0]; 649 lastidx++; 650 path->p_refs[lastidx].pptr = vpp; 651 } 652 } 653 } 654 655 /* 656 * radix_tree_gang_lookup_node: 657 * 658 * search nodes starting from idx in the ascending order. 659 * results should be an array large enough to hold maxresults pointers. 660 * returns the number of nodes found, up to maxresults. 661 * returning less than maxresults means there are no more nodes. 662 * 663 * the result of this function is semantically equivalent to what could be 664 * obtained by repeated calls of radix_tree_lookup_node with increasing index. 665 * but this function is much faster when node indexes are distributed sparsely. 666 * 667 * note that this function doesn't return exact values of node indexes of 668 * found nodes. if they are important for a caller, it's the caller's 669 * responsibility to check them, typically by examinining the returned nodes 670 * using some caller-specific knowledge about them. 671 */ 672 673 unsigned int 674 radix_tree_gang_lookup_node(struct radix_tree *t, uint64_t idx, 675 void **results, unsigned int maxresults) 676 { 677 struct radix_tree_path path; 678 679 gang_lookup_init(t, idx, &path, 0); 680 return gang_lookup_scan(t, &path, results, maxresults, 0); 681 } 682 683 /* 684 * radix_tree_gang_lookup_tagged_node: 685 * 686 * same as radix_tree_gang_lookup_node except that this one only returns 687 * nodes tagged with tagid. 688 */ 689 690 unsigned int 691 radix_tree_gang_lookup_tagged_node(struct radix_tree *t, uint64_t idx, 692 void **results, unsigned int maxresults, radix_tree_tagid_t tagid) 693 { 694 struct radix_tree_path path; 695 const unsigned int tagmask = tagid_to_mask(tagid); 696 697 gang_lookup_init(t, idx, &path, tagmask); 698 return gang_lookup_scan(t, &path, results, maxresults, tagmask); 699 } 700 701 /* 702 * radix_tree_get_tag: 703 * 704 * return if the tag is set for the node at the given index. (true if set) 705 * it's illegal to call this function for a node which has not been inserted. 706 */ 707 708 bool 709 radix_tree_get_tag(struct radix_tree *t, uint64_t idx, 710 radix_tree_tagid_t tagid) 711 { 712 #if 1 713 const unsigned int tagmask = tagid_to_mask(tagid); 714 void **vpp; 715 716 vpp = radix_tree_lookup_ptr(t, idx, NULL, false, tagmask); 717 if (vpp == NULL) { 718 return false; 719 } 720 KASSERT(*vpp != NULL); 721 return (entry_tagmask(*vpp) & tagmask) != 0; 722 #else 723 const unsigned int tagmask = tagid_to_mask(tagid); 724 void **vpp; 725 726 vpp = radix_tree_lookup_ptr(t, idx, NULL, false, 0); 727 KASSERT(vpp != NULL); 728 return (entry_tagmask(*vpp) & tagmask) != 0; 729 #endif 730 } 731 732 /* 733 * radix_tree_set_tag: 734 * 735 * set the tag for the node at the given index. 736 * it's illegal to call this function for a node which has not been inserted. 737 */ 738 739 void 740 radix_tree_set_tag(struct radix_tree *t, uint64_t idx, 741 radix_tree_tagid_t tagid) 742 { 743 struct radix_tree_path path; 744 const unsigned int tagmask = tagid_to_mask(tagid); 745 void **vpp; 746 int i; 747 748 vpp = radix_tree_lookup_ptr(t, idx, &path, false, 0); 749 KASSERT(vpp != NULL); 750 KASSERT(*vpp != NULL); 751 KASSERT(path.p_lastidx == t->t_height); 752 KASSERT(vpp == path_pptr(t, &path, path.p_lastidx)); 753 for (i = t->t_height; i >= 0; i--) { 754 void ** const pptr = (void **)path_pptr(t, &path, i); 755 void *entry; 756 757 KASSERT(pptr != NULL); 758 entry = *pptr; 759 if ((entry_tagmask(entry) & tagmask) != 0) { 760 break; 761 } 762 *pptr = (void *)((uintptr_t)entry | tagmask); 763 } 764 } 765 766 /* 767 * radix_tree_clear_tag: 768 * 769 * clear the tag for the node at the given index. 770 * it's illegal to call this function for a node which has not been inserted. 771 */ 772 773 void 774 radix_tree_clear_tag(struct radix_tree *t, uint64_t idx, 775 radix_tree_tagid_t tagid) 776 { 777 struct radix_tree_path path; 778 const unsigned int tagmask = tagid_to_mask(tagid); 779 void **vpp; 780 int i; 781 782 vpp = radix_tree_lookup_ptr(t, idx, &path, false, 0); 783 KASSERT(vpp != NULL); 784 KASSERT(*vpp != NULL); 785 KASSERT(path.p_lastidx == t->t_height); 786 KASSERT(vpp == path_pptr(t, &path, path.p_lastidx)); 787 if ((entry_tagmask(*vpp) & tagmask) == 0) { 788 return; 789 } 790 for (i = t->t_height; i >= 0; i--) { 791 void ** const pptr = (void **)path_pptr(t, &path, i); 792 void *entry; 793 794 KASSERT(pptr != NULL); 795 entry = *pptr; 796 KASSERT((entry_tagmask(entry) & tagmask) != 0); 797 *pptr = entry_compose(entry_ptr(entry), 798 entry_tagmask(entry) & ~tagmask); 799 if (0 < i && i < t->t_height - 1) { 800 struct radix_tree_node *n = path_node(t, &path, i - 1); 801 802 if ((any_children_tagmask(n) & tagmask) != 0) { 803 break; 804 } 805 } 806 } 807 } 808 809 #if defined(UNITTEST) 810 811 #include <inttypes.h> 812 #include <stdio.h> 813 814 static void 815 radix_tree_dump_node(const struct radix_tree *t, void *vp, 816 uint64_t offset, unsigned int height) 817 { 818 struct radix_tree_node *n; 819 unsigned int i; 820 821 for (i = 0; i < t->t_height - height; i++) { 822 printf(" "); 823 } 824 if (entry_tagmask(vp) == 0) { 825 printf("[%" PRIu64 "] %p", offset, entry_ptr(vp)); 826 } else { 827 printf("[%" PRIu64 "] %p (tagmask=0x%x)", offset, entry_ptr(vp), 828 entry_tagmask(vp)); 829 } 830 if (height == 0) { 831 printf(" (leaf)\n"); 832 return; 833 } 834 n = entry_ptr(vp); 835 assert(any_children_tagmask(n) == entry_tagmask(vp)); 836 printf(" (%u children)\n", n->n_nptrs); 837 for (i = 0; i < __arraycount(n->n_ptrs); i++) { 838 void *c; 839 840 c = n->n_ptrs[i]; 841 if (c == NULL) { 842 continue; 843 } 844 radix_tree_dump_node(t, c, 845 offset + i * (UINT64_C(1) << 846 (RADIX_TREE_BITS_PER_HEIGHT * (height - 1))), height - 1); 847 } 848 } 849 850 void radix_tree_dump(const struct radix_tree *); 851 852 void 853 radix_tree_dump(const struct radix_tree *t) 854 { 855 856 printf("tree %p height=%u\n", t, t->t_height); 857 radix_tree_dump_node(t, t->t_root, 0, t->t_height); 858 } 859 860 static void 861 test1(void) 862 { 863 struct radix_tree s; 864 struct radix_tree *t = &s; 865 void *results[3]; 866 867 radix_tree_init_tree(t); 868 radix_tree_dump(t); 869 assert(radix_tree_lookup_node(t, 0) == NULL); 870 assert(radix_tree_lookup_node(t, 1000) == NULL); 871 assert(radix_tree_insert_node(t, 1000, (void *)0xdeadbea0) == 0); 872 radix_tree_dump(t); 873 assert(!radix_tree_get_tag(t, 1000, 0)); 874 assert(!radix_tree_get_tag(t, 1000, 1)); 875 radix_tree_set_tag(t, 1000, 1); 876 assert(!radix_tree_get_tag(t, 1000, 0)); 877 assert(radix_tree_get_tag(t, 1000, 1)); 878 radix_tree_dump(t); 879 assert(radix_tree_lookup_node(t, 1000) == (void *)0xdeadbea0); 880 assert(radix_tree_insert_node(t, 0, (void *)0xbea0) == 0); 881 radix_tree_dump(t); 882 assert(radix_tree_lookup_node(t, 0) == (void *)0xbea0); 883 assert(radix_tree_lookup_node(t, 1000) == (void *)0xdeadbea0); 884 assert(radix_tree_insert_node(t, UINT64_C(10000000000), (void *)0xdea0) 885 == 0); 886 radix_tree_dump(t); 887 assert(radix_tree_lookup_node(t, 0) == (void *)0xbea0); 888 assert(radix_tree_lookup_node(t, 1000) == (void *)0xdeadbea0); 889 assert(radix_tree_lookup_node(t, UINT64_C(10000000000)) == 890 (void *)0xdea0); 891 radix_tree_dump(t); 892 assert(!radix_tree_get_tag(t, 0, 1)); 893 assert(radix_tree_get_tag(t, 1000, 1)); 894 assert(!radix_tree_get_tag(t, UINT64_C(10000000000), 1)); 895 radix_tree_set_tag(t, 0, 1);; 896 radix_tree_set_tag(t, UINT64_C(10000000000), 1); 897 radix_tree_dump(t); 898 assert(radix_tree_get_tag(t, 0, 1)); 899 assert(radix_tree_get_tag(t, 1000, 1)); 900 assert(radix_tree_get_tag(t, UINT64_C(10000000000), 1)); 901 radix_tree_clear_tag(t, 0, 1);; 902 radix_tree_clear_tag(t, UINT64_C(10000000000), 1); 903 radix_tree_dump(t); 904 assert(!radix_tree_get_tag(t, 0, 1)); 905 assert(radix_tree_get_tag(t, 1000, 1)); 906 assert(!radix_tree_get_tag(t, UINT64_C(10000000000), 1)); 907 radix_tree_dump(t); 908 assert(radix_tree_replace_node(t, 1000, (void *)0x12345678) == 909 (void *)0xdeadbea0); 910 assert(!radix_tree_get_tag(t, 1000, 0)); 911 assert(radix_tree_get_tag(t, 1000, 1)); 912 assert(radix_tree_gang_lookup_node(t, 0, results, 3) == 3); 913 assert(results[0] == (void *)0xbea0); 914 assert(results[1] == (void *)0x12345678); 915 assert(results[2] == (void *)0xdea0); 916 assert(radix_tree_gang_lookup_node(t, 1, results, 3) == 2); 917 assert(results[0] == (void *)0x12345678); 918 assert(results[1] == (void *)0xdea0); 919 assert(radix_tree_gang_lookup_node(t, 1001, results, 3) == 1); 920 assert(results[0] == (void *)0xdea0); 921 assert(radix_tree_gang_lookup_node(t, UINT64_C(10000000001), results, 3) 922 == 0); 923 assert(radix_tree_gang_lookup_node(t, UINT64_C(1000000000000), results, 924 3) == 0); 925 assert(radix_tree_gang_lookup_tagged_node(t, 0, results, 100, 1) == 1); 926 assert(results[0] == (void *)0x12345678); 927 assert(entry_tagmask(t->t_root) != 0); 928 assert(radix_tree_remove_node(t, 1000) == (void *)0x12345678); 929 assert(entry_tagmask(t->t_root) == 0); 930 radix_tree_dump(t); 931 assert(radix_tree_remove_node(t, UINT64_C(10000000000)) == 932 (void *)0xdea0); 933 radix_tree_dump(t); 934 assert(radix_tree_remove_node(t, 0) == (void *)0xbea0); 935 radix_tree_dump(t); 936 radix_tree_fini_tree(t); 937 } 938 939 #include <sys/time.h> 940 941 struct testnode { 942 uint64_t idx; 943 }; 944 945 static void 946 printops(const char *name, unsigned int n, const struct timeval *stv, 947 const struct timeval *etv) 948 { 949 uint64_t s = stv->tv_sec * 1000000 + stv->tv_usec; 950 uint64_t e = etv->tv_sec * 1000000 + etv->tv_usec; 951 952 printf("%lf %s/s\n", (double)n / (e - s) * 1000000, name); 953 } 954 955 #define TEST2_GANG_LOOKUP_NODES 16 956 957 static bool 958 test2_should_tag(unsigned int i, radix_tree_tagid_t tagid) 959 { 960 961 if (tagid == 0) { 962 return (i & 0x3) == 0; 963 } else { 964 return (i % 7) == 0; 965 } 966 } 967 968 static void 969 test2(bool dense) 970 { 971 struct radix_tree s; 972 struct radix_tree *t = &s; 973 struct testnode *n; 974 unsigned int i; 975 unsigned int nnodes = 100000; 976 unsigned int removed; 977 radix_tree_tagid_t tag; 978 unsigned int ntagged[RADIX_TREE_TAG_ID_MAX]; 979 struct testnode *nodes; 980 struct timeval stv; 981 struct timeval etv; 982 983 nodes = malloc(nnodes * sizeof(*nodes)); 984 for (tag = 0; tag < RADIX_TREE_TAG_ID_MAX; tag++) { 985 ntagged[tag] = 0; 986 } 987 radix_tree_init_tree(t); 988 for (i = 0; i < nnodes; i++) { 989 n = &nodes[i]; 990 n->idx = random(); 991 if (sizeof(long) == 4) { 992 n->idx <<= 32; 993 n->idx |= (uint32_t)random(); 994 } 995 if (dense) { 996 n->idx %= nnodes * 2; 997 } 998 while (radix_tree_lookup_node(t, n->idx) != NULL) { 999 n->idx++; 1000 } 1001 radix_tree_insert_node(t, n->idx, n); 1002 for (tag = 0; tag < RADIX_TREE_TAG_ID_MAX; tag++) { 1003 if (test2_should_tag(i, tag)) { 1004 radix_tree_set_tag(t, n->idx, tag); 1005 ntagged[tag]++; 1006 } 1007 assert(test2_should_tag(i, tag) == 1008 radix_tree_get_tag(t, n->idx, tag)); 1009 } 1010 } 1011 1012 gettimeofday(&stv, NULL); 1013 for (i = 0; i < nnodes; i++) { 1014 n = &nodes[i]; 1015 assert(radix_tree_lookup_node(t, n->idx) == n); 1016 } 1017 gettimeofday(&etv, NULL); 1018 printops("lookup", nnodes, &stv, &etv); 1019 1020 for (tag = 0; tag < RADIX_TREE_TAG_ID_MAX; tag++) { 1021 gettimeofday(&stv, NULL); 1022 for (i = 0; i < nnodes; i++) { 1023 n = &nodes[i]; 1024 assert(test2_should_tag(i, tag) == 1025 radix_tree_get_tag(t, n->idx, tag)); 1026 } 1027 gettimeofday(&etv, NULL); 1028 printops("get_tag", ntagged[tag], &stv, &etv); 1029 } 1030 1031 gettimeofday(&stv, NULL); 1032 for (i = 0; i < nnodes; i++) { 1033 n = &nodes[i]; 1034 radix_tree_remove_node(t, n->idx); 1035 } 1036 gettimeofday(&etv, NULL); 1037 printops("remove", nnodes, &stv, &etv); 1038 1039 gettimeofday(&stv, NULL); 1040 for (i = 0; i < nnodes; i++) { 1041 n = &nodes[i]; 1042 radix_tree_insert_node(t, n->idx, n); 1043 } 1044 gettimeofday(&etv, NULL); 1045 printops("insert", nnodes, &stv, &etv); 1046 1047 for (tag = 0; tag < RADIX_TREE_TAG_ID_MAX; tag++) { 1048 ntagged[tag] = 0; 1049 gettimeofday(&stv, NULL); 1050 for (i = 0; i < nnodes; i++) { 1051 n = &nodes[i]; 1052 if (test2_should_tag(i, tag)) { 1053 radix_tree_set_tag(t, n->idx, tag); 1054 ntagged[tag]++; 1055 } 1056 } 1057 gettimeofday(&etv, NULL); 1058 printops("set_tag", ntagged[tag], &stv, &etv); 1059 } 1060 1061 gettimeofday(&stv, NULL); 1062 { 1063 struct testnode *results[TEST2_GANG_LOOKUP_NODES]; 1064 uint64_t nextidx; 1065 unsigned int nfound; 1066 unsigned int total; 1067 1068 nextidx = 0; 1069 total = 0; 1070 while ((nfound = radix_tree_gang_lookup_node(t, nextidx, 1071 (void *)results, __arraycount(results))) > 0) { 1072 nextidx = results[nfound - 1]->idx + 1; 1073 total += nfound; 1074 } 1075 assert(total == nnodes); 1076 } 1077 gettimeofday(&etv, NULL); 1078 printops("ganglookup", nnodes, &stv, &etv); 1079 1080 for (tag = 0; tag < RADIX_TREE_TAG_ID_MAX; tag++) { 1081 gettimeofday(&stv, NULL); 1082 { 1083 struct testnode *results[TEST2_GANG_LOOKUP_NODES]; 1084 uint64_t nextidx; 1085 unsigned int nfound; 1086 unsigned int total; 1087 1088 nextidx = 0; 1089 total = 0; 1090 while ((nfound = radix_tree_gang_lookup_tagged_node(t, 1091 nextidx, (void *)results, __arraycount(results), 1092 tag)) > 0) { 1093 nextidx = results[nfound - 1]->idx + 1; 1094 total += nfound; 1095 } 1096 assert(total == ntagged[tag]); 1097 } 1098 gettimeofday(&etv, NULL); 1099 printops("ganglookup_tag", ntagged[tag], &stv, &etv); 1100 } 1101 1102 removed = 0; 1103 for (tag = 0; tag < RADIX_TREE_TAG_ID_MAX; tag++) { 1104 unsigned int total; 1105 1106 total = 0; 1107 gettimeofday(&stv, NULL); 1108 { 1109 struct testnode *results[TEST2_GANG_LOOKUP_NODES]; 1110 uint64_t nextidx; 1111 unsigned int nfound; 1112 1113 nextidx = 0; 1114 while ((nfound = radix_tree_gang_lookup_tagged_node(t, 1115 nextidx, (void *)results, __arraycount(results), 1116 tag)) > 0) { 1117 for (i = 0; i < nfound; i++) { 1118 radix_tree_remove_node(t, 1119 results[i]->idx); 1120 } 1121 nextidx = results[nfound - 1]->idx + 1; 1122 total += nfound; 1123 } 1124 assert(tag != 0 || total == ntagged[tag]); 1125 assert(total <= ntagged[tag]); 1126 } 1127 gettimeofday(&etv, NULL); 1128 printops("ganglookup_tag+remove", total, &stv, &etv); 1129 removed += total; 1130 } 1131 1132 gettimeofday(&stv, NULL); 1133 { 1134 struct testnode *results[TEST2_GANG_LOOKUP_NODES]; 1135 uint64_t nextidx; 1136 unsigned int nfound; 1137 unsigned int total; 1138 1139 nextidx = 0; 1140 total = 0; 1141 while ((nfound = radix_tree_gang_lookup_node(t, nextidx, 1142 (void *)results, __arraycount(results))) > 0) { 1143 for (i = 0; i < nfound; i++) { 1144 assert(results[i] == radix_tree_remove_node(t, 1145 results[i]->idx)); 1146 } 1147 nextidx = results[nfound - 1]->idx + 1; 1148 total += nfound; 1149 } 1150 assert(total == nnodes - removed); 1151 } 1152 gettimeofday(&etv, NULL); 1153 printops("ganglookup+remove", nnodes - removed, &stv, &etv); 1154 1155 radix_tree_fini_tree(t); 1156 free(nodes); 1157 } 1158 1159 int 1160 main(int argc, char *argv[]) 1161 { 1162 1163 test1(); 1164 printf("dense distribution:\n"); 1165 test2(true); 1166 printf("sparse distribution:\n"); 1167 test2(false); 1168 return 0; 1169 } 1170 1171 #endif /* defined(UNITTEST) */ 1172
Indexes created Mon Sep 22 05:09:51 GMT 2025