1 /*- 2 * SPDX-License-Identifier: BSD-2-Clause 3 * 4 * Copyright (c) 2013 EMC Corp. 5 * Copyright (c) 2011 Jeffrey Roberson <jeff@freebsd.org> 6 * Copyright (c) 2008 Mayur Shardul <mayur.shardul@gmail.com> 7 * All rights reserved. 8 * 9 * Redistribution and use in source and binary forms, with or without 10 * modification, are permitted provided that the following conditions 11 * are met: 12 * 1. Redistributions of source code must retain the above copyright 13 * notice, this list of conditions and the following disclaimer. 14 * 2. Redistributions in binary form must reproduce the above copyright 15 * notice, this list of conditions and the following disclaimer in the 16 * documentation and/or other materials provided with the distribution. 17 * 18 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND 19 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 20 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 21 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE 22 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 23 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 24 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 25 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 26 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 27 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 28 * SUCH DAMAGE. 29 * 30 */ 31 32 /* 33 * Path-compressed radix trie implementation. 34 * 35 * The implementation takes into account the following rationale: 36 * - Size of the nodes should be as small as possible but still big enough 37 * to avoid a large maximum depth for the trie. This is a balance 38 * between the necessity to not wire too much physical memory for the nodes 39 * and the necessity to avoid too much cache pollution during the trie 40 * operations. 41 * - There is not a huge bias toward the number of lookup operations over 42 * the number of insert and remove operations. This basically implies 43 * that optimizations supposedly helping one operation but hurting the 44 * other might be carefully evaluated. 45 * - On average not many nodes are expected to be fully populated, hence 46 * level compression may just complicate things. 47 */ 48 49 #include <sys/cdefs.h> 50 __FBSDID("$FreeBSD$"); 51 52 #include "opt_ddb.h" 53 54 #include <sys/param.h> 55 #include <sys/systm.h> 56 #include <sys/kernel.h> 57 #include <sys/libkern.h> 58 #include <sys/pctrie.h> 59 #include <sys/proc.h> /* smr.h depends on struct thread. */ 60 #include <sys/smr.h> 61 #include <sys/smr_types.h> 62 63 #ifdef DDB 64 #include <ddb/ddb.h> 65 #endif 66 67 #define PCTRIE_MASK (PCTRIE_COUNT - 1) 68 #define PCTRIE_LIMIT (howmany(sizeof(uint64_t) * NBBY, PCTRIE_WIDTH) - 1) 69 70 #if PCTRIE_WIDTH == 3 71 typedef uint8_t pn_popmap_t; 72 #elif PCTRIE_WIDTH == 4 73 typedef uint16_t pn_popmap_t; 74 #elif PCTRIE_WIDTH == 5 75 typedef uint32_t pn_popmap_t; 76 #else 77 #error Unsupported width 78 #endif 79 _Static_assert(sizeof(pn_popmap_t) <= sizeof(int), 80 "pn_popmap_t too wide"); 81 82 /* Flag bits stored in node pointers. */ 83 #define PCTRIE_ISLEAF 0x1 84 #define PCTRIE_FLAGS 0x1 85 #define PCTRIE_PAD PCTRIE_FLAGS 86 87 /* Returns one unit associated with specified level. */ 88 #define PCTRIE_UNITLEVEL(lev) \ 89 ((uint64_t)1 << ((lev) * PCTRIE_WIDTH)) 90 91 struct pctrie_node; 92 typedef SMR_POINTER(struct pctrie_node *) smr_pctnode_t; 93 94 struct pctrie_node { 95 uint64_t pn_owner; /* Owner of record. */ 96 pn_popmap_t pn_popmap; /* Valid children. */ 97 uint8_t pn_clev; /* Current level. */ 98 smr_pctnode_t pn_child[PCTRIE_COUNT]; /* Child nodes. */ 99 }; 100 101 enum pctrie_access { PCTRIE_SMR, PCTRIE_LOCKED, PCTRIE_UNSERIALIZED }; 102 103 static __inline void pctrie_node_store(smr_pctnode_t *p, void *val, 104 enum pctrie_access access); 105 106 /* 107 * Return the position in the array for a given level. 108 */ 109 static __inline int 110 pctrie_slot(uint64_t index, uint16_t level) 111 { 112 return ((index >> (level * PCTRIE_WIDTH)) & PCTRIE_MASK); 113 } 114 115 /* Computes the key (index) with the low-order 'level' radix-digits zeroed. */ 116 static __inline uint64_t 117 pctrie_trimkey(uint64_t index, uint16_t level) 118 { 119 return (index & -PCTRIE_UNITLEVEL(level)); 120 } 121 122 /* 123 * Allocate a node. Pre-allocation should ensure that the request 124 * will always be satisfied. 125 */ 126 static struct pctrie_node * 127 pctrie_node_get(struct pctrie *ptree, pctrie_alloc_t allocfn, uint64_t index, 128 uint16_t clevel) 129 { 130 struct pctrie_node *node; 131 132 node = allocfn(ptree); 133 if (node == NULL) 134 return (NULL); 135 136 /* 137 * We want to clear the last child pointer after the final section 138 * has exited so lookup can not return false negatives. It is done 139 * here because it will be cache-cold in the dtor callback. 140 */ 141 if (node->pn_popmap != 0) { 142 pctrie_node_store(&node->pn_child[ffs(node->pn_popmap) - 1], 143 NULL, PCTRIE_UNSERIALIZED); 144 node->pn_popmap = 0; 145 } 146 node->pn_owner = pctrie_trimkey(index, clevel + 1); 147 node->pn_clev = clevel; 148 return (node); 149 } 150 151 /* 152 * Free radix node. 153 */ 154 static __inline void 155 pctrie_node_put(struct pctrie *ptree, struct pctrie_node *node, 156 pctrie_free_t freefn) 157 { 158 #ifdef INVARIANTS 159 int slot; 160 161 KASSERT(powerof2(node->pn_popmap), 162 ("pctrie_node_put: node %p has too many children %04x", node, 163 node->pn_popmap)); 164 for (slot = 0; slot < PCTRIE_COUNT; slot++) { 165 if ((node->pn_popmap & (1 << slot)) != 0) 166 continue; 167 KASSERT(smr_unserialized_load(&node->pn_child[slot], true) == 168 NULL, ("pctrie_node_put: node %p has a child", node)); 169 } 170 #endif 171 freefn(ptree, node); 172 } 173 174 /* 175 * Fetch a node pointer from a slot. 176 */ 177 static __inline struct pctrie_node * 178 pctrie_node_load(smr_pctnode_t *p, smr_t smr, enum pctrie_access access) 179 { 180 switch (access) { 181 case PCTRIE_UNSERIALIZED: 182 return (smr_unserialized_load(p, true)); 183 case PCTRIE_LOCKED: 184 return (smr_serialized_load(p, true)); 185 case PCTRIE_SMR: 186 return (smr_entered_load(p, smr)); 187 } 188 __assert_unreachable(); 189 } 190 191 static __inline void 192 pctrie_node_store(smr_pctnode_t *p, void *v, enum pctrie_access access) 193 { 194 switch (access) { 195 case PCTRIE_UNSERIALIZED: 196 smr_unserialized_store(p, v, true); 197 break; 198 case PCTRIE_LOCKED: 199 smr_serialized_store(p, v, true); 200 break; 201 case PCTRIE_SMR: 202 panic("%s: Not supported in SMR section.", __func__); 203 break; 204 default: 205 __assert_unreachable(); 206 break; 207 } 208 } 209 210 /* 211 * Get the root node for a tree. 212 */ 213 static __inline struct pctrie_node * 214 pctrie_root_load(struct pctrie *ptree, smr_t smr, enum pctrie_access access) 215 { 216 return (pctrie_node_load((smr_pctnode_t *)&ptree->pt_root, smr, access)); 217 } 218 219 /* 220 * Set the root node for a tree. 221 */ 222 static __inline void 223 pctrie_root_store(struct pctrie *ptree, struct pctrie_node *node, 224 enum pctrie_access access) 225 { 226 pctrie_node_store((smr_pctnode_t *)&ptree->pt_root, node, access); 227 } 228 229 /* 230 * Returns TRUE if the specified node is a leaf and FALSE otherwise. 231 */ 232 static __inline bool 233 pctrie_isleaf(struct pctrie_node *node) 234 { 235 236 return (((uintptr_t)node & PCTRIE_ISLEAF) != 0); 237 } 238 239 /* 240 * Returns val with leaf bit set. 241 */ 242 static __inline void * 243 pctrie_toleaf(uint64_t *val) 244 { 245 return ((void *)((uintptr_t)val | PCTRIE_ISLEAF)); 246 } 247 248 /* 249 * Returns the associated val extracted from node. 250 */ 251 static __inline uint64_t * 252 pctrie_toval(struct pctrie_node *node) 253 { 254 255 return ((uint64_t *)((uintptr_t)node & ~PCTRIE_FLAGS)); 256 } 257 258 /* 259 * Make 'child' a child of 'node'. 260 */ 261 static __inline void 262 pctrie_addnode(struct pctrie_node *node, uint64_t index, uint16_t clev, 263 struct pctrie_node *child, enum pctrie_access access) 264 { 265 int slot; 266 267 slot = pctrie_slot(index, clev); 268 pctrie_node_store(&node->pn_child[slot], child, access); 269 node->pn_popmap ^= 1 << slot; 270 KASSERT((node->pn_popmap & (1 << slot)) != 0, 271 ("%s: bad popmap slot %d in node %p", __func__, slot, node)); 272 } 273 274 /* 275 * Returns the level where two keys differ. 276 * It cannot accept 2 equal keys. 277 */ 278 static __inline uint16_t 279 pctrie_keydiff(uint64_t index1, uint64_t index2) 280 { 281 282 KASSERT(index1 != index2, ("%s: passing the same key value %jx", 283 __func__, (uintmax_t)index1)); 284 CTASSERT(sizeof(long long) >= sizeof(uint64_t)); 285 286 /* 287 * From the highest-order bit where the indexes differ, 288 * compute the highest level in the trie where they differ. 289 */ 290 return ((flsll(index1 ^ index2) - 1) / PCTRIE_WIDTH); 291 } 292 293 /* 294 * Returns TRUE if it can be determined that key does not belong to the 295 * specified node. Otherwise, returns FALSE. 296 */ 297 static __inline bool 298 pctrie_keybarr(struct pctrie_node *node, uint64_t idx) 299 { 300 301 if (node->pn_clev < PCTRIE_LIMIT) { 302 idx = pctrie_trimkey(idx, node->pn_clev + 1); 303 return (idx != node->pn_owner); 304 } 305 return (false); 306 } 307 308 /* 309 * Internal helper for pctrie_reclaim_allnodes(). 310 * This function is recursive. 311 */ 312 static void 313 pctrie_reclaim_allnodes_int(struct pctrie *ptree, struct pctrie_node *node, 314 pctrie_free_t freefn) 315 { 316 struct pctrie_node *child; 317 int slot; 318 319 while (node->pn_popmap != 0) { 320 slot = ffs(node->pn_popmap) - 1; 321 child = pctrie_node_load(&node->pn_child[slot], NULL, 322 PCTRIE_UNSERIALIZED); 323 KASSERT(child != NULL, ("%s: bad popmap slot %d in node %p", 324 __func__, slot, node)); 325 if (!pctrie_isleaf(child)) 326 pctrie_reclaim_allnodes_int(ptree, child, freefn); 327 node->pn_popmap ^= 1 << slot; 328 pctrie_node_store(&node->pn_child[slot], NULL, 329 PCTRIE_UNSERIALIZED); 330 } 331 pctrie_node_put(ptree, node, freefn); 332 } 333 334 /* 335 * pctrie node zone initializer. 336 */ 337 int 338 pctrie_zone_init(void *mem, int size __unused, int flags __unused) 339 { 340 struct pctrie_node *node; 341 342 node = mem; 343 node->pn_popmap = 0; 344 memset(node->pn_child, 0, sizeof(node->pn_child)); 345 return (0); 346 } 347 348 size_t 349 pctrie_node_size(void) 350 { 351 352 return (sizeof(struct pctrie_node)); 353 } 354 355 /* 356 * Inserts the key-value pair into the trie. 357 * Panics if the key already exists. 358 */ 359 int 360 pctrie_insert(struct pctrie *ptree, uint64_t *val, pctrie_alloc_t allocfn) 361 { 362 uint64_t index, newind; 363 struct pctrie_node *leaf, *node, *tmp; 364 smr_pctnode_t *parentp; 365 int slot; 366 uint16_t clev; 367 368 index = *val; 369 leaf = pctrie_toleaf(val); 370 371 /* 372 * The owner of record for root is not really important because it 373 * will never be used. 374 */ 375 node = pctrie_root_load(ptree, NULL, PCTRIE_LOCKED); 376 if (node == NULL) { 377 ptree->pt_root = (uintptr_t)leaf; 378 return (0); 379 } 380 for (parentp = (smr_pctnode_t *)&ptree->pt_root;; node = tmp) { 381 if (pctrie_isleaf(node)) { 382 newind = *pctrie_toval(node); 383 if (newind == index) 384 panic("%s: key %jx is already present", 385 __func__, (uintmax_t)index); 386 break; 387 } else if (pctrie_keybarr(node, index)) { 388 newind = node->pn_owner; 389 break; 390 } 391 slot = pctrie_slot(index, node->pn_clev); 392 parentp = &node->pn_child[slot]; 393 tmp = pctrie_node_load(parentp, NULL, PCTRIE_LOCKED); 394 if (tmp == NULL) { 395 pctrie_addnode(node, index, node->pn_clev, leaf, 396 PCTRIE_LOCKED); 397 return (0); 398 } 399 } 400 401 /* 402 * A new node is needed because the right insertion level is reached. 403 * Setup the new intermediate node and add the 2 children: the 404 * new object and the older edge or object. 405 */ 406 clev = pctrie_keydiff(newind, index); 407 tmp = pctrie_node_get(ptree, allocfn, index, clev); 408 if (tmp == NULL) 409 return (ENOMEM); 410 /* These writes are not yet visible due to ordering. */ 411 pctrie_addnode(tmp, index, clev, leaf, PCTRIE_UNSERIALIZED); 412 pctrie_addnode(tmp, newind, clev, node, PCTRIE_UNSERIALIZED); 413 /* Synchronize to make the above visible. */ 414 pctrie_node_store(parentp, tmp, PCTRIE_LOCKED); 415 return (0); 416 } 417 418 /* 419 * Returns the value stored at the index. If the index is not present, 420 * NULL is returned. 421 */ 422 static __always_inline uint64_t * 423 _pctrie_lookup(struct pctrie *ptree, uint64_t index, smr_t smr, 424 enum pctrie_access access) 425 { 426 struct pctrie_node *node; 427 uint64_t *m; 428 int slot; 429 430 node = pctrie_root_load(ptree, smr, access); 431 while (node != NULL) { 432 if (pctrie_isleaf(node)) { 433 m = pctrie_toval(node); 434 if (*m == index) 435 return (m); 436 break; 437 } 438 if (pctrie_keybarr(node, index)) 439 break; 440 slot = pctrie_slot(index, node->pn_clev); 441 node = pctrie_node_load(&node->pn_child[slot], smr, access); 442 } 443 return (NULL); 444 } 445 446 /* 447 * Returns the value stored at the index, assuming access is externally 448 * synchronized by a lock. 449 * 450 * If the index is not present, NULL is returned. 451 */ 452 uint64_t * 453 pctrie_lookup(struct pctrie *ptree, uint64_t index) 454 { 455 return (_pctrie_lookup(ptree, index, NULL, PCTRIE_LOCKED)); 456 } 457 458 /* 459 * Returns the value stored at the index without requiring an external lock. 460 * 461 * If the index is not present, NULL is returned. 462 */ 463 uint64_t * 464 pctrie_lookup_unlocked(struct pctrie *ptree, uint64_t index, smr_t smr) 465 { 466 uint64_t *res; 467 468 smr_enter(smr); 469 res = _pctrie_lookup(ptree, index, smr, PCTRIE_SMR); 470 smr_exit(smr); 471 return (res); 472 } 473 474 /* 475 * Look up the nearest entry at a position bigger than or equal to index, 476 * assuming access is externally synchronized by a lock. 477 */ 478 uint64_t * 479 pctrie_lookup_ge(struct pctrie *ptree, uint64_t index) 480 { 481 struct pctrie_node *stack[PCTRIE_LIMIT]; 482 uint64_t *m; 483 struct pctrie_node *child, *node; 484 #ifdef INVARIANTS 485 int loops = 0; 486 #endif 487 unsigned tos; 488 int slot; 489 490 node = pctrie_root_load(ptree, NULL, PCTRIE_LOCKED); 491 if (node == NULL) 492 return (NULL); 493 else if (pctrie_isleaf(node)) { 494 m = pctrie_toval(node); 495 if (*m >= index) 496 return (m); 497 else 498 return (NULL); 499 } 500 tos = 0; 501 for (;;) { 502 /* 503 * If the keys differ before the current bisection node, 504 * then the search key might rollback to the earliest 505 * available bisection node or to the smallest key 506 * in the current node (if the owner is greater than the 507 * search key). 508 */ 509 if (pctrie_keybarr(node, index)) { 510 if (index > node->pn_owner) { 511 ascend: 512 KASSERT(++loops < 1000, 513 ("pctrie_lookup_ge: too many loops")); 514 515 /* 516 * Pop nodes from the stack until either the 517 * stack is empty or a node that could have a 518 * matching descendant is found. 519 */ 520 do { 521 if (tos == 0) 522 return (NULL); 523 node = stack[--tos]; 524 } while (pctrie_slot(index, 525 node->pn_clev) == (PCTRIE_COUNT - 1)); 526 527 /* 528 * The following computation cannot overflow 529 * because index's slot at the current level 530 * is less than PCTRIE_COUNT - 1. 531 */ 532 index = pctrie_trimkey(index, 533 node->pn_clev); 534 index += PCTRIE_UNITLEVEL(node->pn_clev); 535 } else 536 index = node->pn_owner; 537 KASSERT(!pctrie_keybarr(node, index), 538 ("pctrie_lookup_ge: keybarr failed")); 539 } 540 slot = pctrie_slot(index, node->pn_clev); 541 child = pctrie_node_load(&node->pn_child[slot], NULL, 542 PCTRIE_LOCKED); 543 if (pctrie_isleaf(child)) { 544 m = pctrie_toval(child); 545 if (*m >= index) 546 return (m); 547 } else if (child != NULL) 548 goto descend; 549 550 /* Find the first set bit beyond the first slot+1 bits. */ 551 slot = ffs(node->pn_popmap & (-2 << slot)) - 1; 552 if (slot < 0) { 553 /* 554 * A value or edge greater than the search slot is not 555 * found in the current node; ascend to the next 556 * higher-level node. 557 */ 558 goto ascend; 559 } 560 child = pctrie_node_load(&node->pn_child[slot], 561 NULL, PCTRIE_LOCKED); 562 KASSERT(child != NULL, ("%s: bad popmap slot %d in node %p", 563 __func__, slot, node)); 564 if (pctrie_isleaf(child)) 565 return (pctrie_toval(child)); 566 index = pctrie_trimkey(index, node->pn_clev + 1) + 567 slot * PCTRIE_UNITLEVEL(node->pn_clev); 568 descend: 569 KASSERT(node->pn_clev > 0, 570 ("pctrie_lookup_ge: pushing leaf's parent")); 571 KASSERT(tos < PCTRIE_LIMIT, 572 ("pctrie_lookup_ge: stack overflow")); 573 stack[tos++] = node; 574 node = child; 575 } 576 } 577 578 /* 579 * Look up the nearest entry at a position less than or equal to index, 580 * assuming access is externally synchronized by a lock. 581 */ 582 uint64_t * 583 pctrie_lookup_le(struct pctrie *ptree, uint64_t index) 584 { 585 struct pctrie_node *stack[PCTRIE_LIMIT]; 586 uint64_t *m; 587 struct pctrie_node *child, *node; 588 #ifdef INVARIANTS 589 int loops = 0; 590 #endif 591 unsigned tos; 592 int slot; 593 594 node = pctrie_root_load(ptree, NULL, PCTRIE_LOCKED); 595 if (node == NULL) 596 return (NULL); 597 else if (pctrie_isleaf(node)) { 598 m = pctrie_toval(node); 599 if (*m <= index) 600 return (m); 601 else 602 return (NULL); 603 } 604 tos = 0; 605 for (;;) { 606 /* 607 * If the keys differ before the current bisection node, 608 * then the search key might rollback to the earliest 609 * available bisection node or to the largest key 610 * in the current node (if the owner is smaller than the 611 * search key). 612 */ 613 if (pctrie_keybarr(node, index)) { 614 if (index > node->pn_owner) { 615 index = node->pn_owner + PCTRIE_COUNT * 616 PCTRIE_UNITLEVEL(node->pn_clev); 617 } else { 618 ascend: 619 KASSERT(++loops < 1000, 620 ("pctrie_lookup_le: too many loops")); 621 622 /* 623 * Pop nodes from the stack until either the 624 * stack is empty or a node that could have a 625 * matching descendant is found. 626 */ 627 do { 628 if (tos == 0) 629 return (NULL); 630 node = stack[--tos]; 631 } while (pctrie_slot(index, 632 node->pn_clev) == 0); 633 634 /* 635 * The following computation cannot overflow 636 * because index's slot at the current level 637 * is greater than 0. 638 */ 639 index = pctrie_trimkey(index, 640 node->pn_clev); 641 } 642 index--; 643 KASSERT(!pctrie_keybarr(node, index), 644 ("pctrie_lookup_le: keybarr failed")); 645 } 646 slot = pctrie_slot(index, node->pn_clev); 647 child = pctrie_node_load(&node->pn_child[slot], NULL, 648 PCTRIE_LOCKED); 649 if (pctrie_isleaf(child)) { 650 m = pctrie_toval(child); 651 if (*m <= index) 652 return (m); 653 } else if (child != NULL) 654 goto descend; 655 656 /* Find the last set bit among the first slot bits. */ 657 slot = fls(node->pn_popmap & ((1 << slot) - 1)) - 1; 658 if (slot < 0) { 659 /* 660 * A value or edge smaller than the search slot is not 661 * found in the current node; ascend to the next 662 * higher-level node. 663 */ 664 goto ascend; 665 } 666 child = pctrie_node_load(&node->pn_child[slot], 667 NULL, PCTRIE_LOCKED); 668 if (pctrie_isleaf(child)) 669 return (pctrie_toval(child)); 670 index = pctrie_trimkey(index, node->pn_clev + 1) + 671 (slot + 1) * PCTRIE_UNITLEVEL(node->pn_clev) - 1; 672 descend: 673 KASSERT(node->pn_clev > 0, 674 ("pctrie_lookup_le: pushing leaf's parent")); 675 KASSERT(tos < PCTRIE_LIMIT, 676 ("pctrie_lookup_le: stack overflow")); 677 stack[tos++] = node; 678 node = child; 679 } 680 } 681 682 /* 683 * Remove the specified index from the tree. 684 * Panics if the key is not present. 685 */ 686 void 687 pctrie_remove(struct pctrie *ptree, uint64_t index, pctrie_free_t freefn) 688 { 689 struct pctrie_node *node, *parent, *tmp; 690 uint64_t *m; 691 int slot; 692 693 node = pctrie_root_load(ptree, NULL, PCTRIE_LOCKED); 694 if (pctrie_isleaf(node)) { 695 m = pctrie_toval(node); 696 if (*m != index) 697 panic("%s: invalid key found", __func__); 698 pctrie_root_store(ptree, NULL, PCTRIE_LOCKED); 699 return; 700 } 701 parent = NULL; 702 for (;;) { 703 if (node == NULL) 704 panic("pctrie_remove: impossible to locate the key"); 705 slot = pctrie_slot(index, node->pn_clev); 706 tmp = pctrie_node_load(&node->pn_child[slot], NULL, 707 PCTRIE_LOCKED); 708 if (pctrie_isleaf(tmp)) { 709 m = pctrie_toval(tmp); 710 if (*m != index) 711 panic("%s: invalid key found", __func__); 712 KASSERT((node->pn_popmap & (1 << slot)) != 0, 713 ("%s: bad popmap slot %d in node %p", 714 __func__, slot, node)); 715 node->pn_popmap ^= 1 << slot; 716 pctrie_node_store(&node->pn_child[slot], NULL, 717 PCTRIE_LOCKED); 718 if (!powerof2(node->pn_popmap)) 719 break; 720 KASSERT(node->pn_popmap != 0, 721 ("%s: bad popmap all zeroes", __func__)); 722 slot = ffs(node->pn_popmap) - 1; 723 tmp = pctrie_node_load(&node->pn_child[slot], 724 NULL, PCTRIE_LOCKED); 725 KASSERT(tmp != NULL, 726 ("%s: bad popmap slot %d in node %p", 727 __func__, slot, node)); 728 if (parent == NULL) 729 pctrie_root_store(ptree, tmp, PCTRIE_LOCKED); 730 else { 731 slot = pctrie_slot(index, parent->pn_clev); 732 KASSERT(pctrie_node_load( 733 &parent->pn_child[slot], NULL, 734 PCTRIE_LOCKED) == node, 735 ("%s: invalid child value", __func__)); 736 pctrie_node_store(&parent->pn_child[slot], tmp, 737 PCTRIE_LOCKED); 738 } 739 /* 740 * The child is still valid and we can not zero the 741 * pointer until all SMR references are gone. 742 */ 743 pctrie_node_put(ptree, node, freefn); 744 break; 745 } 746 parent = node; 747 node = tmp; 748 } 749 } 750 751 /* 752 * Remove and free all the nodes from the tree. 753 * This function is recursive but there is a tight control on it as the 754 * maximum depth of the tree is fixed. 755 */ 756 void 757 pctrie_reclaim_allnodes(struct pctrie *ptree, pctrie_free_t freefn) 758 { 759 struct pctrie_node *root; 760 761 root = pctrie_root_load(ptree, NULL, PCTRIE_LOCKED); 762 if (root == NULL) 763 return; 764 pctrie_root_store(ptree, NULL, PCTRIE_UNSERIALIZED); 765 if (!pctrie_isleaf(root)) 766 pctrie_reclaim_allnodes_int(ptree, root, freefn); 767 } 768 769 #ifdef DDB 770 /* 771 * Show details about the given node. 772 */ 773 DB_SHOW_COMMAND(pctrienode, db_show_pctrienode) 774 { 775 struct pctrie_node *node, *tmp; 776 int slot; 777 pn_popmap_t popmap; 778 779 if (!have_addr) 780 return; 781 node = (struct pctrie_node *)addr; 782 db_printf("node %p, owner %jx, children popmap %04x, level %u:\n", 783 (void *)node, (uintmax_t)node->pn_owner, node->pn_popmap, 784 node->pn_clev); 785 for (popmap = node->pn_popmap; popmap != 0; popmap ^= 1 << slot) { 786 slot = ffs(popmap) - 1; 787 tmp = pctrie_node_load(&node->pn_child[slot], NULL, 788 PCTRIE_UNSERIALIZED); 789 db_printf("slot: %d, val: %p, value: %p, clev: %d\n", 790 slot, (void *)tmp, 791 pctrie_isleaf(tmp) ? pctrie_toval(tmp) : NULL, 792 node->pn_clev); 793 } 794 } 795 #endif /* DDB */ 796