1 /* $NetBSD: radixtree.c,v 1.3 2011/04/26 20:53:53 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.3 2011/04/26 20:53:53 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.3 2011/04/26 20:53:53 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 429 int 430 radix_tree_insert_node(struct radix_tree *t, uint64_t idx, void *p) 431 { 432 void **vpp; 433 434 KASSERT(p != NULL); 435 KASSERT(entry_compose(p, 0) == p); 436 vpp = radix_tree_lookup_ptr(t, idx, NULL, true, 0); 437 if (vpp == NULL) { 438 return ENOMEM; 439 } 440 KASSERT(*vpp == NULL); 441 *vpp = p; 442 return 0; 443 } 444 445 void * 446 radix_tree_replace_node(struct radix_tree *t, uint64_t idx, void *p) 447 { 448 void **vpp; 449 void *oldp; 450 451 KASSERT(p != NULL); 452 KASSERT(entry_compose(p, 0) == p); 453 vpp = radix_tree_lookup_ptr(t, idx, NULL, false, 0); 454 KASSERT(vpp != NULL); 455 oldp = *vpp; 456 KASSERT(oldp != NULL); 457 *vpp = entry_compose(p, entry_tagmask(*vpp)); 458 return entry_ptr(oldp); 459 } 460 461 /* 462 * radix_tree_remove_node: 463 * 464 * remove the node at idx. 465 * it's illegal to try to remove a node which has not been inserted. 466 */ 467 468 void * 469 radix_tree_remove_node(struct radix_tree *t, uint64_t idx) 470 { 471 struct radix_tree_path path; 472 void **vpp; 473 void *oldp; 474 int i; 475 476 vpp = radix_tree_lookup_ptr(t, idx, &path, false, 0); 477 KASSERT(vpp != NULL); 478 oldp = *vpp; 479 KASSERT(oldp != NULL); 480 KASSERT(path.p_lastidx == t->t_height); 481 KASSERT(vpp == path_pptr(t, &path, path.p_lastidx)); 482 *vpp = NULL; 483 for (i = t->t_height - 1; i >= 0; i--) { 484 void *entry; 485 struct radix_tree_node ** const pptr = 486 (struct radix_tree_node **)path_pptr(t, &path, i); 487 struct radix_tree_node *n; 488 489 KASSERT(pptr != NULL); 490 entry = *pptr; 491 n = entry_ptr(entry); 492 KASSERT(n != NULL); 493 KASSERT(n->n_nptrs > 0); 494 n->n_nptrs--; 495 if (n->n_nptrs > 0) { 496 break; 497 } 498 radix_tree_free_node(n); 499 *pptr = NULL; 500 } 501 /* 502 * fix up height 503 */ 504 if (i < 0) { 505 KASSERT(t->t_root == NULL); 506 t->t_height = 0; 507 } 508 /* 509 * update tags 510 */ 511 for (; i >= 0; i--) { 512 void *entry; 513 struct radix_tree_node ** const pptr = 514 (struct radix_tree_node **)path_pptr(t, &path, i); 515 struct radix_tree_node *n; 516 unsigned int newmask; 517 518 KASSERT(pptr != NULL); 519 entry = *pptr; 520 n = entry_ptr(entry); 521 KASSERT(n != NULL); 522 KASSERT(n->n_nptrs > 0); 523 newmask = any_children_tagmask(n); 524 if (newmask == entry_tagmask(entry)) { 525 break; 526 } 527 *pptr = entry_compose(n, newmask); 528 } 529 /* 530 * XXX is it worth to try to reduce height? 531 * if we do that, make radix_tree_grow rollback its change as well. 532 */ 533 return entry_ptr(oldp); 534 } 535 536 /* 537 * radix_tree_lookup_node: 538 * 539 * returns the node at idx. 540 * returns NULL if nothing is found at idx. 541 */ 542 543 void * 544 radix_tree_lookup_node(struct radix_tree *t, uint64_t idx) 545 { 546 void **vpp; 547 548 vpp = radix_tree_lookup_ptr(t, idx, NULL, false, 0); 549 if (vpp == NULL) { 550 return NULL; 551 } 552 return entry_ptr(*vpp); 553 } 554 555 static inline void 556 gang_lookup_init(struct radix_tree *t, uint64_t idx, 557 struct radix_tree_path *path, const unsigned int tagmask) 558 { 559 void **vpp; 560 561 vpp = radix_tree_lookup_ptr(t, idx, path, false, tagmask); 562 KASSERT(vpp == NULL || 563 vpp == path_pptr(t, path, path->p_lastidx)); 564 KASSERT(&t->t_root == path_pptr(t, path, 0)); 565 } 566 567 static inline unsigned int 568 gang_lookup_scan(struct radix_tree *t, struct radix_tree_path *path, 569 void **results, unsigned int maxresults, const unsigned int tagmask) 570 { 571 void **vpp; 572 int nfound; 573 unsigned int lastidx; 574 575 KASSERT(maxresults > 0); 576 lastidx = path->p_lastidx; 577 if (lastidx == 0) { 578 return 0; 579 } 580 nfound = 0; 581 vpp = path_pptr(t, path, lastidx); 582 while (/*CONSTCOND*/true) { 583 struct radix_tree_node *n; 584 int i; 585 586 if (entry_match_p(*vpp, tagmask)) { 587 KASSERT(lastidx == t->t_height); 588 /* 589 * record the non-NULL leaf. 590 */ 591 results[nfound] = entry_ptr(*vpp); 592 nfound++; 593 if (nfound == maxresults) { 594 return nfound; 595 } 596 } 597 scan_siblings: 598 /* 599 * try to find the next non-NULL sibling. 600 */ 601 n = path_node(t, path, lastidx - 1); 602 if (*vpp != NULL && n->n_nptrs == 1) { 603 /* 604 * optimization 605 */ 606 goto no_siblings; 607 } 608 for (i = path_idx(t, path, lastidx - 1) + 1; 609 i < RADIX_TREE_PTR_PER_NODE; 610 i++) { 611 if (entry_match_p(n->n_ptrs[i], tagmask)) { 612 vpp = &n->n_ptrs[i]; 613 path->p_refs[lastidx].pptr = vpp; 614 KASSERT(path_idx(t, path, lastidx - 1) 615 == i); 616 break; 617 } 618 } 619 if (i == RADIX_TREE_PTR_PER_NODE) { 620 no_siblings: 621 /* 622 * not found. go to parent. 623 */ 624 lastidx--; 625 if (lastidx == 0) { 626 return nfound; 627 } 628 vpp = path_pptr(t, path, lastidx); 629 goto scan_siblings; 630 } 631 /* 632 * descending the left-most child node, upto the leaf or NULL. 633 */ 634 while (entry_match_p(*vpp, tagmask) && lastidx < t->t_height) { 635 n = entry_ptr(*vpp); 636 vpp = &n->n_ptrs[0]; 637 lastidx++; 638 path->p_refs[lastidx].pptr = vpp; 639 } 640 } 641 } 642 643 /* 644 * radix_tree_gang_lookup_node: 645 * 646 * search nodes starting from idx in the ascending order. 647 * results should be an array large enough to hold maxresults pointers. 648 * returns the number of nodes found, up to maxresults. 649 * returning less than maxresults means there are no more nodes. 650 * 651 * the result of this function is semantically equivalent to what could be 652 * obtained by repeated calls of radix_tree_lookup_node with increasing index. 653 * but this function is much faster when node indexes are distributed sparsely. 654 * 655 * note that this function doesn't return exact values of node indexes of 656 * found nodes. if they are important for a caller, it's the caller's 657 * responsibility to check them, typically by examinining the returned nodes 658 * using some caller-specific knowledge about them. 659 */ 660 661 unsigned int 662 radix_tree_gang_lookup_node(struct radix_tree *t, uint64_t idx, 663 void **results, unsigned int maxresults) 664 { 665 struct radix_tree_path path; 666 667 gang_lookup_init(t, idx, &path, 0); 668 return gang_lookup_scan(t, &path, results, maxresults, 0); 669 } 670 671 /* 672 * radix_tree_gang_lookup_tagged_node: 673 * 674 * same as radix_tree_gang_lookup_node except that this one only returns 675 * nodes tagged with tagid. 676 */ 677 678 unsigned int 679 radix_tree_gang_lookup_tagged_node(struct radix_tree *t, uint64_t idx, 680 void **results, unsigned int maxresults, radix_tree_tagid_t tagid) 681 { 682 struct radix_tree_path path; 683 const unsigned int tagmask = tagid_to_mask(tagid); 684 685 gang_lookup_init(t, idx, &path, tagmask); 686 return gang_lookup_scan(t, &path, results, maxresults, tagmask); 687 } 688 689 bool 690 radix_tree_get_tag(struct radix_tree *t, uint64_t idx, 691 radix_tree_tagid_t tagid) 692 { 693 #if 1 694 const unsigned int tagmask = tagid_to_mask(tagid); 695 void **vpp; 696 697 vpp = radix_tree_lookup_ptr(t, idx, NULL, false, tagmask); 698 if (vpp == NULL) { 699 return false; 700 } 701 KASSERT(*vpp != NULL); 702 return (entry_tagmask(*vpp) & tagmask) != 0; 703 #else 704 const unsigned int tagmask = tagid_to_mask(tagid); 705 void **vpp; 706 707 vpp = radix_tree_lookup_ptr(t, idx, NULL, false, 0); 708 KASSERT(vpp != NULL); 709 return (entry_tagmask(*vpp) & tagmask) != 0; 710 #endif 711 } 712 713 void 714 radix_tree_set_tag(struct radix_tree *t, uint64_t idx, 715 radix_tree_tagid_t tagid) 716 { 717 struct radix_tree_path path; 718 const unsigned int tagmask = tagid_to_mask(tagid); 719 void **vpp; 720 int i; 721 722 vpp = radix_tree_lookup_ptr(t, idx, &path, false, 0); 723 KASSERT(vpp != NULL); 724 KASSERT(*vpp != NULL); 725 KASSERT(path.p_lastidx == t->t_height); 726 KASSERT(vpp == path_pptr(t, &path, path.p_lastidx)); 727 for (i = t->t_height; i >= 0; i--) { 728 void ** const pptr = (void **)path_pptr(t, &path, i); 729 void *entry; 730 731 KASSERT(pptr != NULL); 732 entry = *pptr; 733 if ((entry_tagmask(entry) & tagmask) != 0) { 734 break; 735 } 736 *pptr = (void *)((uintptr_t)entry | tagmask); 737 } 738 } 739 740 void 741 radix_tree_clear_tag(struct radix_tree *t, uint64_t idx, 742 radix_tree_tagid_t tagid) 743 { 744 struct radix_tree_path path; 745 const unsigned int tagmask = tagid_to_mask(tagid); 746 void **vpp; 747 int i; 748 749 vpp = radix_tree_lookup_ptr(t, idx, &path, false, 0); 750 KASSERT(vpp != NULL); 751 KASSERT(*vpp != NULL); 752 KASSERT(path.p_lastidx == t->t_height); 753 KASSERT(vpp == path_pptr(t, &path, path.p_lastidx)); 754 if ((entry_tagmask(*vpp) & tagmask) == 0) { 755 return; 756 } 757 for (i = t->t_height; i >= 0; i--) { 758 void ** const pptr = (void **)path_pptr(t, &path, i); 759 void *entry; 760 761 KASSERT(pptr != NULL); 762 entry = *pptr; 763 KASSERT((entry_tagmask(entry) & tagmask) != 0); 764 *pptr = entry_compose(entry_ptr(entry), 765 entry_tagmask(entry) & ~tagmask); 766 if (0 < i && i < t->t_height - 1) { 767 struct radix_tree_node *n = path_node(t, &path, i - 1); 768 769 if ((any_children_tagmask(n) & tagmask) != 0) { 770 break; 771 } 772 } 773 } 774 } 775 776 #if defined(UNITTEST) 777 778 #include <inttypes.h> 779 #include <stdio.h> 780 781 static void 782 radix_tree_dump_node(const struct radix_tree *t, void *vp, 783 uint64_t offset, unsigned int height) 784 { 785 struct radix_tree_node *n; 786 unsigned int i; 787 788 for (i = 0; i < t->t_height - height; i++) { 789 printf(" "); 790 } 791 if (entry_tagmask(vp) == 0) { 792 printf("[%" PRIu64 "] %p", offset, entry_ptr(vp)); 793 } else { 794 printf("[%" PRIu64 "] %p (tagmask=0x%x)", offset, entry_ptr(vp), 795 entry_tagmask(vp)); 796 } 797 if (height == 0) { 798 printf(" (leaf)\n"); 799 return; 800 } 801 n = entry_ptr(vp); 802 assert(any_children_tagmask(n) == entry_tagmask(vp)); 803 printf(" (%u children)\n", n->n_nptrs); 804 for (i = 0; i < __arraycount(n->n_ptrs); i++) { 805 void *c; 806 807 c = n->n_ptrs[i]; 808 if (c == NULL) { 809 continue; 810 } 811 radix_tree_dump_node(t, c, 812 offset + i * (UINT64_C(1) << 813 (RADIX_TREE_BITS_PER_HEIGHT * (height - 1))), height - 1); 814 } 815 } 816 817 void radix_tree_dump(const struct radix_tree *); 818 819 void 820 radix_tree_dump(const struct radix_tree *t) 821 { 822 823 printf("tree %p height=%u\n", t, t->t_height); 824 radix_tree_dump_node(t, t->t_root, 0, t->t_height); 825 } 826 827 static void 828 test1(void) 829 { 830 struct radix_tree s; 831 struct radix_tree *t = &s; 832 void *results[3]; 833 834 radix_tree_init_tree(t); 835 radix_tree_dump(t); 836 assert(radix_tree_lookup_node(t, 0) == NULL); 837 assert(radix_tree_lookup_node(t, 1000) == NULL); 838 assert(radix_tree_insert_node(t, 1000, (void *)0xdeadbea0) == 0); 839 radix_tree_dump(t); 840 assert(!radix_tree_get_tag(t, 1000, 0)); 841 assert(!radix_tree_get_tag(t, 1000, 1)); 842 radix_tree_set_tag(t, 1000, 1); 843 assert(!radix_tree_get_tag(t, 1000, 0)); 844 assert(radix_tree_get_tag(t, 1000, 1)); 845 radix_tree_dump(t); 846 assert(radix_tree_lookup_node(t, 1000) == (void *)0xdeadbea0); 847 assert(radix_tree_insert_node(t, 0, (void *)0xbea0) == 0); 848 radix_tree_dump(t); 849 assert(radix_tree_lookup_node(t, 0) == (void *)0xbea0); 850 assert(radix_tree_lookup_node(t, 1000) == (void *)0xdeadbea0); 851 assert(radix_tree_insert_node(t, UINT64_C(10000000000), (void *)0xdea0) 852 == 0); 853 radix_tree_dump(t); 854 assert(radix_tree_lookup_node(t, 0) == (void *)0xbea0); 855 assert(radix_tree_lookup_node(t, 1000) == (void *)0xdeadbea0); 856 assert(radix_tree_lookup_node(t, UINT64_C(10000000000)) == 857 (void *)0xdea0); 858 radix_tree_dump(t); 859 assert(!radix_tree_get_tag(t, 0, 1)); 860 assert(radix_tree_get_tag(t, 1000, 1)); 861 assert(!radix_tree_get_tag(t, UINT64_C(10000000000), 1)); 862 radix_tree_set_tag(t, 0, 1);; 863 radix_tree_set_tag(t, UINT64_C(10000000000), 1); 864 radix_tree_dump(t); 865 assert(radix_tree_get_tag(t, 0, 1)); 866 assert(radix_tree_get_tag(t, 1000, 1)); 867 assert(radix_tree_get_tag(t, UINT64_C(10000000000), 1)); 868 radix_tree_clear_tag(t, 0, 1);; 869 radix_tree_clear_tag(t, UINT64_C(10000000000), 1); 870 radix_tree_dump(t); 871 assert(!radix_tree_get_tag(t, 0, 1)); 872 assert(radix_tree_get_tag(t, 1000, 1)); 873 assert(!radix_tree_get_tag(t, UINT64_C(10000000000), 1)); 874 radix_tree_dump(t); 875 assert(radix_tree_replace_node(t, 1000, (void *)0x12345678) == 876 (void *)0xdeadbea0); 877 assert(!radix_tree_get_tag(t, 1000, 0)); 878 assert(radix_tree_get_tag(t, 1000, 1)); 879 assert(radix_tree_gang_lookup_node(t, 0, results, 3) == 3); 880 assert(results[0] == (void *)0xbea0); 881 assert(results[1] == (void *)0x12345678); 882 assert(results[2] == (void *)0xdea0); 883 assert(radix_tree_gang_lookup_node(t, 1, results, 3) == 2); 884 assert(results[0] == (void *)0x12345678); 885 assert(results[1] == (void *)0xdea0); 886 assert(radix_tree_gang_lookup_node(t, 1001, results, 3) == 1); 887 assert(results[0] == (void *)0xdea0); 888 assert(radix_tree_gang_lookup_node(t, UINT64_C(10000000001), results, 3) 889 == 0); 890 assert(radix_tree_gang_lookup_node(t, UINT64_C(1000000000000), results, 891 3) == 0); 892 assert(radix_tree_gang_lookup_tagged_node(t, 0, results, 100, 1) == 1); 893 assert(results[0] == (void *)0x12345678); 894 assert(entry_tagmask(t->t_root) != 0); 895 assert(radix_tree_remove_node(t, 1000) == (void *)0x12345678); 896 assert(entry_tagmask(t->t_root) == 0); 897 radix_tree_dump(t); 898 assert(radix_tree_remove_node(t, UINT64_C(10000000000)) == 899 (void *)0xdea0); 900 radix_tree_dump(t); 901 assert(radix_tree_remove_node(t, 0) == (void *)0xbea0); 902 radix_tree_dump(t); 903 radix_tree_fini_tree(t); 904 } 905 906 #include <sys/time.h> 907 908 struct testnode { 909 uint64_t idx; 910 }; 911 912 static void 913 printops(const char *name, unsigned int n, const struct timeval *stv, 914 const struct timeval *etv) 915 { 916 uint64_t s = stv->tv_sec * 1000000 + stv->tv_usec; 917 uint64_t e = etv->tv_sec * 1000000 + etv->tv_usec; 918 919 printf("%lf %s/s\n", (double)n / (e - s) * 1000000, name); 920 } 921 922 #define TEST2_GANG_LOOKUP_NODES 16 923 924 static bool 925 test2_should_tag(unsigned int i, radix_tree_tagid_t tagid) 926 { 927 928 if (tagid == 0) { 929 return (i & 0x3) == 0; 930 } else { 931 return (i % 7) == 0; 932 } 933 } 934 935 static void 936 test2(bool dense) 937 { 938 struct radix_tree s; 939 struct radix_tree *t = &s; 940 struct testnode *n; 941 unsigned int i; 942 unsigned int nnodes = 100000; 943 unsigned int removed; 944 radix_tree_tagid_t tag; 945 unsigned int ntagged[RADIX_TREE_TAG_ID_MAX]; 946 struct testnode *nodes; 947 struct timeval stv; 948 struct timeval etv; 949 950 nodes = malloc(nnodes * sizeof(*nodes)); 951 for (tag = 0; tag < RADIX_TREE_TAG_ID_MAX; tag++) { 952 ntagged[tag] = 0; 953 } 954 radix_tree_init_tree(t); 955 for (i = 0; i < nnodes; i++) { 956 n = &nodes[i]; 957 n->idx = random(); 958 if (sizeof(long) == 4) { 959 n->idx <<= 32; 960 n->idx |= (uint32_t)random(); 961 } 962 if (dense) { 963 n->idx %= nnodes * 2; 964 } 965 while (radix_tree_lookup_node(t, n->idx) != NULL) { 966 n->idx++; 967 } 968 radix_tree_insert_node(t, n->idx, n); 969 for (tag = 0; tag < RADIX_TREE_TAG_ID_MAX; tag++) { 970 if (test2_should_tag(i, tag)) { 971 radix_tree_set_tag(t, n->idx, tag); 972 ntagged[tag]++; 973 } 974 assert(test2_should_tag(i, tag) == 975 radix_tree_get_tag(t, n->idx, tag)); 976 } 977 } 978 979 gettimeofday(&stv, NULL); 980 for (i = 0; i < nnodes; i++) { 981 n = &nodes[i]; 982 assert(radix_tree_lookup_node(t, n->idx) == n); 983 } 984 gettimeofday(&etv, NULL); 985 printops("lookup", nnodes, &stv, &etv); 986 987 for (tag = 0; tag < RADIX_TREE_TAG_ID_MAX; tag++) { 988 gettimeofday(&stv, NULL); 989 for (i = 0; i < nnodes; i++) { 990 n = &nodes[i]; 991 assert(test2_should_tag(i, tag) == 992 radix_tree_get_tag(t, n->idx, tag)); 993 } 994 gettimeofday(&etv, NULL); 995 printops("get_tag", ntagged[tag], &stv, &etv); 996 } 997 998 gettimeofday(&stv, NULL); 999 for (i = 0; i < nnodes; i++) { 1000 n = &nodes[i]; 1001 radix_tree_remove_node(t, n->idx); 1002 } 1003 gettimeofday(&etv, NULL); 1004 printops("remove", nnodes, &stv, &etv); 1005 1006 gettimeofday(&stv, NULL); 1007 for (i = 0; i < nnodes; i++) { 1008 n = &nodes[i]; 1009 radix_tree_insert_node(t, n->idx, n); 1010 } 1011 gettimeofday(&etv, NULL); 1012 printops("insert", nnodes, &stv, &etv); 1013 1014 for (tag = 0; tag < RADIX_TREE_TAG_ID_MAX; tag++) { 1015 ntagged[tag] = 0; 1016 gettimeofday(&stv, NULL); 1017 for (i = 0; i < nnodes; i++) { 1018 n = &nodes[i]; 1019 if (test2_should_tag(i, tag)) { 1020 radix_tree_set_tag(t, n->idx, tag); 1021 ntagged[tag]++; 1022 } 1023 } 1024 gettimeofday(&etv, NULL); 1025 printops("set_tag", ntagged[tag], &stv, &etv); 1026 } 1027 1028 gettimeofday(&stv, NULL); 1029 { 1030 struct testnode *results[TEST2_GANG_LOOKUP_NODES]; 1031 uint64_t nextidx; 1032 unsigned int nfound; 1033 unsigned int total; 1034 1035 nextidx = 0; 1036 total = 0; 1037 while ((nfound = radix_tree_gang_lookup_node(t, nextidx, 1038 (void *)results, __arraycount(results))) > 0) { 1039 nextidx = results[nfound - 1]->idx + 1; 1040 total += nfound; 1041 } 1042 assert(total == nnodes); 1043 } 1044 gettimeofday(&etv, NULL); 1045 printops("ganglookup", nnodes, &stv, &etv); 1046 1047 for (tag = 0; tag < RADIX_TREE_TAG_ID_MAX; tag++) { 1048 gettimeofday(&stv, NULL); 1049 { 1050 struct testnode *results[TEST2_GANG_LOOKUP_NODES]; 1051 uint64_t nextidx; 1052 unsigned int nfound; 1053 unsigned int total; 1054 1055 nextidx = 0; 1056 total = 0; 1057 while ((nfound = radix_tree_gang_lookup_tagged_node(t, 1058 nextidx, (void *)results, __arraycount(results), 1059 tag)) > 0) { 1060 nextidx = results[nfound - 1]->idx + 1; 1061 total += nfound; 1062 } 1063 assert(total == ntagged[tag]); 1064 } 1065 gettimeofday(&etv, NULL); 1066 printops("ganglookup_tag", ntagged[tag], &stv, &etv); 1067 } 1068 1069 removed = 0; 1070 for (tag = 0; tag < RADIX_TREE_TAG_ID_MAX; tag++) { 1071 unsigned int total; 1072 1073 total = 0; 1074 gettimeofday(&stv, NULL); 1075 { 1076 struct testnode *results[TEST2_GANG_LOOKUP_NODES]; 1077 uint64_t nextidx; 1078 unsigned int nfound; 1079 1080 nextidx = 0; 1081 while ((nfound = radix_tree_gang_lookup_tagged_node(t, 1082 nextidx, (void *)results, __arraycount(results), 1083 tag)) > 0) { 1084 for (i = 0; i < nfound; i++) { 1085 radix_tree_remove_node(t, 1086 results[i]->idx); 1087 } 1088 nextidx = results[nfound - 1]->idx + 1; 1089 total += nfound; 1090 } 1091 assert(tag != 0 || total == ntagged[tag]); 1092 assert(total <= ntagged[tag]); 1093 } 1094 gettimeofday(&etv, NULL); 1095 printops("ganglookup_tag+remove", total, &stv, &etv); 1096 removed += total; 1097 } 1098 1099 gettimeofday(&stv, NULL); 1100 { 1101 struct testnode *results[TEST2_GANG_LOOKUP_NODES]; 1102 uint64_t nextidx; 1103 unsigned int nfound; 1104 unsigned int total; 1105 1106 nextidx = 0; 1107 total = 0; 1108 while ((nfound = radix_tree_gang_lookup_node(t, nextidx, 1109 (void *)results, __arraycount(results))) > 0) { 1110 for (i = 0; i < nfound; i++) { 1111 assert(results[i] == radix_tree_remove_node(t, 1112 results[i]->idx)); 1113 } 1114 nextidx = results[nfound - 1]->idx + 1; 1115 total += nfound; 1116 } 1117 assert(total == nnodes - removed); 1118 } 1119 gettimeofday(&etv, NULL); 1120 printops("ganglookup+remove", nnodes - removed, &stv, &etv); 1121 1122 radix_tree_fini_tree(t); 1123 free(nodes); 1124 } 1125 1126 int 1127 main(int argc, char *argv[]) 1128 { 1129 1130 test1(); 1131 printf("dense distribution:\n"); 1132 test2(true); 1133 printf("sparse distribution:\n"); 1134 test2(false); 1135 return 0; 1136 } 1137 1138 #endif /* defined(UNITTEST) */ 1139