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 /* Flag bits stored in node pointers. */ 71 #define PCTRIE_ISLEAF 0x1 72 #define PCTRIE_FLAGS 0x1 73 #define PCTRIE_PAD PCTRIE_FLAGS 74 75 /* Returns one unit associated with specified level. */ 76 #define PCTRIE_UNITLEVEL(lev) \ 77 ((uint64_t)1 << ((lev) * PCTRIE_WIDTH)) 78 79 struct pctrie_node; 80 typedef SMR_POINTER(struct pctrie_node *) smr_pctnode_t; 81 82 struct pctrie_node { 83 uint64_t pn_owner; /* Owner of record. */ 84 uint16_t pn_count; /* Valid children. */ 85 uint8_t pn_clev; /* Current level. */ 86 int8_t pn_last; /* Zero last ptr. */ 87 smr_pctnode_t pn_child[PCTRIE_COUNT]; /* Child nodes. */ 88 }; 89 90 enum pctrie_access { PCTRIE_SMR, PCTRIE_LOCKED, PCTRIE_UNSERIALIZED }; 91 92 static __inline void pctrie_node_store(smr_pctnode_t *p, void *val, 93 enum pctrie_access access); 94 95 /* 96 * Allocate a node. Pre-allocation should ensure that the request 97 * will always be satisfied. 98 */ 99 static struct pctrie_node * 100 pctrie_node_get(struct pctrie *ptree, pctrie_alloc_t allocfn, uint64_t owner, 101 uint16_t count, uint16_t clevel) 102 { 103 struct pctrie_node *node; 104 105 node = allocfn(ptree); 106 if (node == NULL) 107 return (NULL); 108 109 /* 110 * We want to clear the last child pointer after the final section 111 * has exited so lookup can not return false negatives. It is done 112 * here because it will be cache-cold in the dtor callback. 113 */ 114 if (node->pn_last != 0) { 115 pctrie_node_store(&node->pn_child[node->pn_last - 1], NULL, 116 PCTRIE_UNSERIALIZED); 117 node->pn_last = 0; 118 } 119 node->pn_owner = owner; 120 node->pn_count = count; 121 node->pn_clev = clevel; 122 return (node); 123 } 124 125 /* 126 * Free radix node. 127 */ 128 static __inline void 129 pctrie_node_put(struct pctrie *ptree, struct pctrie_node *node, 130 pctrie_free_t freefn, int8_t last) 131 { 132 #ifdef INVARIANTS 133 int slot; 134 135 KASSERT(node->pn_count == 0, 136 ("pctrie_node_put: node %p has %d children", node, 137 node->pn_count)); 138 for (slot = 0; slot < PCTRIE_COUNT; slot++) { 139 if (slot == last) 140 continue; 141 KASSERT(smr_unserialized_load(&node->pn_child[slot], true) == 142 NULL, ("pctrie_node_put: node %p has a child", node)); 143 } 144 #endif 145 node->pn_last = last + 1; 146 freefn(ptree, node); 147 } 148 149 /* 150 * Return the position in the array for a given level. 151 */ 152 static __inline int 153 pctrie_slot(uint64_t index, uint16_t level) 154 { 155 156 return ((index >> (level * PCTRIE_WIDTH)) & PCTRIE_MASK); 157 } 158 159 /* Trims the key after the specified level. */ 160 static __inline uint64_t 161 pctrie_trimkey(uint64_t index, uint16_t level) 162 { 163 uint64_t ret; 164 165 ret = index; 166 if (level > 0) { 167 ret >>= level * PCTRIE_WIDTH; 168 ret <<= level * PCTRIE_WIDTH; 169 } 170 return (ret); 171 } 172 173 /* 174 * Fetch a node pointer from a slot. 175 */ 176 static __inline struct pctrie_node * 177 pctrie_node_load(smr_pctnode_t *p, smr_t smr, enum pctrie_access access) 178 { 179 switch (access) { 180 case PCTRIE_UNSERIALIZED: 181 return (smr_unserialized_load(p, true)); 182 case PCTRIE_LOCKED: 183 return (smr_serialized_load(p, true)); 184 case PCTRIE_SMR: 185 return (smr_entered_load(p, smr)); 186 } 187 __assert_unreachable(); 188 } 189 190 static __inline void 191 pctrie_node_store(smr_pctnode_t *p, void *v, enum pctrie_access access) 192 { 193 switch (access) { 194 case PCTRIE_UNSERIALIZED: 195 smr_unserialized_store(p, v, true); 196 break; 197 case PCTRIE_LOCKED: 198 smr_serialized_store(p, v, true); 199 break; 200 case PCTRIE_SMR: 201 panic("%s: Not supported in SMR section.", __func__); 202 break; 203 default: 204 __assert_unreachable(); 205 break; 206 } 207 } 208 209 /* 210 * Get the root node for a tree. 211 */ 212 static __inline struct pctrie_node * 213 pctrie_root_load(struct pctrie *ptree, smr_t smr, enum pctrie_access access) 214 { 215 return (pctrie_node_load((smr_pctnode_t *)&ptree->pt_root, smr, access)); 216 } 217 218 /* 219 * Set the root node for a tree. 220 */ 221 static __inline void 222 pctrie_root_store(struct pctrie *ptree, struct pctrie_node *node, 223 enum pctrie_access access) 224 { 225 pctrie_node_store((smr_pctnode_t *)&ptree->pt_root, node, access); 226 } 227 228 /* 229 * Returns TRUE if the specified node is a leaf and FALSE otherwise. 230 */ 231 static __inline bool 232 pctrie_isleaf(struct pctrie_node *node) 233 { 234 235 return (((uintptr_t)node & PCTRIE_ISLEAF) != 0); 236 } 237 238 /* 239 * Returns the associated val extracted from node. 240 */ 241 static __inline uint64_t * 242 pctrie_toval(struct pctrie_node *node) 243 { 244 245 return ((uint64_t *)((uintptr_t)node & ~PCTRIE_FLAGS)); 246 } 247 248 /* 249 * Adds the val as a child of the provided node. 250 */ 251 static __inline void 252 pctrie_addval(struct pctrie_node *node, uint64_t index, uint16_t clev, 253 uint64_t *val, enum pctrie_access access) 254 { 255 int slot; 256 257 slot = pctrie_slot(index, clev); 258 pctrie_node_store(&node->pn_child[slot], 259 (void *)((uintptr_t)val | PCTRIE_ISLEAF), access); 260 } 261 262 /* 263 * Returns the level where two keys differ. 264 * It cannot accept 2 equal keys. 265 */ 266 static __inline uint16_t 267 pctrie_keydiff(uint64_t index1, uint64_t index2) 268 { 269 270 KASSERT(index1 != index2, ("%s: passing the same key value %jx", 271 __func__, (uintmax_t)index1)); 272 CTASSERT(sizeof(long long) >= sizeof(uint64_t)); 273 274 /* 275 * From the highest-order bit where the indexes differ, 276 * compute the highest level in the trie where they differ. 277 */ 278 return ((flsll(index1 ^ index2) - 1) / PCTRIE_WIDTH); 279 } 280 281 /* 282 * Returns TRUE if it can be determined that key does not belong to the 283 * specified node. Otherwise, returns FALSE. 284 */ 285 static __inline bool 286 pctrie_keybarr(struct pctrie_node *node, uint64_t idx) 287 { 288 289 if (node->pn_clev < PCTRIE_LIMIT) { 290 idx = pctrie_trimkey(idx, node->pn_clev + 1); 291 return (idx != node->pn_owner); 292 } 293 return (false); 294 } 295 296 /* 297 * Internal helper for pctrie_reclaim_allnodes(). 298 * This function is recursive. 299 */ 300 static void 301 pctrie_reclaim_allnodes_int(struct pctrie *ptree, struct pctrie_node *node, 302 pctrie_free_t freefn) 303 { 304 struct pctrie_node *child; 305 int slot; 306 307 KASSERT(node->pn_count <= PCTRIE_COUNT, 308 ("pctrie_reclaim_allnodes_int: bad count in node %p", node)); 309 for (slot = 0; node->pn_count != 0; slot++) { 310 child = pctrie_node_load(&node->pn_child[slot], NULL, 311 PCTRIE_UNSERIALIZED); 312 if (child == NULL) 313 continue; 314 if (!pctrie_isleaf(child)) 315 pctrie_reclaim_allnodes_int(ptree, child, freefn); 316 pctrie_node_store(&node->pn_child[slot], NULL, 317 PCTRIE_UNSERIALIZED); 318 node->pn_count--; 319 } 320 pctrie_node_put(ptree, node, freefn, -1); 321 } 322 323 /* 324 * pctrie node zone initializer. 325 */ 326 int 327 pctrie_zone_init(void *mem, int size __unused, int flags __unused) 328 { 329 struct pctrie_node *node; 330 331 node = mem; 332 node->pn_last = 0; 333 memset(node->pn_child, 0, sizeof(node->pn_child)); 334 return (0); 335 } 336 337 size_t 338 pctrie_node_size(void) 339 { 340 341 return (sizeof(struct pctrie_node)); 342 } 343 344 /* 345 * Inserts the key-value pair into the trie. 346 * Panics if the key already exists. 347 */ 348 int 349 pctrie_insert(struct pctrie *ptree, uint64_t *val, pctrie_alloc_t allocfn) 350 { 351 uint64_t index, newind; 352 struct pctrie_node *node, *tmp; 353 smr_pctnode_t *parentp; 354 uint64_t *m; 355 int slot; 356 uint16_t clev; 357 358 index = *val; 359 360 /* 361 * The owner of record for root is not really important because it 362 * will never be used. 363 */ 364 node = pctrie_root_load(ptree, NULL, PCTRIE_LOCKED); 365 if (node == NULL) { 366 ptree->pt_root = (uintptr_t)val | PCTRIE_ISLEAF; 367 return (0); 368 } 369 parentp = (smr_pctnode_t *)&ptree->pt_root; 370 for (;;) { 371 if (pctrie_isleaf(node)) { 372 m = pctrie_toval(node); 373 if (*m == index) 374 panic("%s: key %jx is already present", 375 __func__, (uintmax_t)index); 376 clev = pctrie_keydiff(*m, index); 377 tmp = pctrie_node_get(ptree, allocfn, 378 pctrie_trimkey(index, clev + 1), 2, clev); 379 if (tmp == NULL) 380 return (ENOMEM); 381 /* These writes are not yet visible due to ordering. */ 382 pctrie_addval(tmp, index, clev, val, 383 PCTRIE_UNSERIALIZED); 384 pctrie_addval(tmp, *m, clev, m, PCTRIE_UNSERIALIZED); 385 /* Synchronize to make leaf visible. */ 386 pctrie_node_store(parentp, tmp, PCTRIE_LOCKED); 387 return (0); 388 } else if (pctrie_keybarr(node, index)) 389 break; 390 slot = pctrie_slot(index, node->pn_clev); 391 parentp = &node->pn_child[slot]; 392 tmp = pctrie_node_load(parentp, NULL, PCTRIE_LOCKED); 393 if (tmp == NULL) { 394 node->pn_count++; 395 pctrie_addval(node, index, node->pn_clev, val, 396 PCTRIE_LOCKED); 397 return (0); 398 } 399 node = tmp; 400 } 401 402 /* 403 * A new node is needed because the right insertion level is reached. 404 * Setup the new intermediate node and add the 2 children: the 405 * new object and the older edge. 406 */ 407 newind = node->pn_owner; 408 clev = pctrie_keydiff(newind, index); 409 tmp = pctrie_node_get(ptree, allocfn, 410 pctrie_trimkey(index, clev + 1), 2, clev); 411 if (tmp == NULL) 412 return (ENOMEM); 413 slot = pctrie_slot(newind, clev); 414 /* These writes are not yet visible due to ordering. */ 415 pctrie_addval(tmp, index, clev, val, PCTRIE_UNSERIALIZED); 416 pctrie_node_store(&tmp->pn_child[slot], node, PCTRIE_UNSERIALIZED); 417 /* Synchronize to make the above visible. */ 418 pctrie_node_store(parentp, tmp, PCTRIE_LOCKED); 419 420 return (0); 421 } 422 423 /* 424 * Returns the value stored at the index. If the index is not present, 425 * NULL is returned. 426 */ 427 static __always_inline uint64_t * 428 _pctrie_lookup(struct pctrie *ptree, uint64_t index, smr_t smr, 429 enum pctrie_access access) 430 { 431 struct pctrie_node *node; 432 uint64_t *m; 433 int slot; 434 435 node = pctrie_root_load(ptree, smr, access); 436 while (node != NULL) { 437 if (pctrie_isleaf(node)) { 438 m = pctrie_toval(node); 439 if (*m == index) 440 return (m); 441 break; 442 } 443 if (pctrie_keybarr(node, index)) 444 break; 445 slot = pctrie_slot(index, node->pn_clev); 446 node = pctrie_node_load(&node->pn_child[slot], smr, access); 447 } 448 return (NULL); 449 } 450 451 /* 452 * Returns the value stored at the index, assuming access is externally 453 * synchronized by a lock. 454 * 455 * If the index is not present, NULL is returned. 456 */ 457 uint64_t * 458 pctrie_lookup(struct pctrie *ptree, uint64_t index) 459 { 460 return (_pctrie_lookup(ptree, index, NULL, PCTRIE_LOCKED)); 461 } 462 463 /* 464 * Returns the value stored at the index without requiring an external lock. 465 * 466 * If the index is not present, NULL is returned. 467 */ 468 uint64_t * 469 pctrie_lookup_unlocked(struct pctrie *ptree, uint64_t index, smr_t smr) 470 { 471 uint64_t *res; 472 473 smr_enter(smr); 474 res = _pctrie_lookup(ptree, index, smr, PCTRIE_SMR); 475 smr_exit(smr); 476 return (res); 477 } 478 479 /* 480 * Look up the nearest entry at a position bigger than or equal to index, 481 * assuming access is externally synchronized by a lock. 482 */ 483 uint64_t * 484 pctrie_lookup_ge(struct pctrie *ptree, uint64_t index) 485 { 486 struct pctrie_node *stack[PCTRIE_LIMIT]; 487 uint64_t inc; 488 uint64_t *m; 489 struct pctrie_node *child, *node; 490 #ifdef INVARIANTS 491 int loops = 0; 492 #endif 493 unsigned tos; 494 int slot; 495 496 node = pctrie_root_load(ptree, NULL, PCTRIE_LOCKED); 497 if (node == NULL) 498 return (NULL); 499 else if (pctrie_isleaf(node)) { 500 m = pctrie_toval(node); 501 if (*m >= index) 502 return (m); 503 else 504 return (NULL); 505 } 506 tos = 0; 507 for (;;) { 508 /* 509 * If the keys differ before the current bisection node, 510 * then the search key might rollback to the earliest 511 * available bisection node or to the smallest key 512 * in the current node (if the owner is greater than the 513 * search key). 514 */ 515 if (pctrie_keybarr(node, index)) { 516 if (index > node->pn_owner) { 517 ascend: 518 KASSERT(++loops < 1000, 519 ("pctrie_lookup_ge: too many loops")); 520 521 /* 522 * Pop nodes from the stack until either the 523 * stack is empty or a node that could have a 524 * matching descendant is found. 525 */ 526 do { 527 if (tos == 0) 528 return (NULL); 529 node = stack[--tos]; 530 } while (pctrie_slot(index, 531 node->pn_clev) == (PCTRIE_COUNT - 1)); 532 533 /* 534 * The following computation cannot overflow 535 * because index's slot at the current level 536 * is less than PCTRIE_COUNT - 1. 537 */ 538 index = pctrie_trimkey(index, 539 node->pn_clev); 540 index += PCTRIE_UNITLEVEL(node->pn_clev); 541 } else 542 index = node->pn_owner; 543 KASSERT(!pctrie_keybarr(node, index), 544 ("pctrie_lookup_ge: keybarr failed")); 545 } 546 slot = pctrie_slot(index, node->pn_clev); 547 child = pctrie_node_load(&node->pn_child[slot], NULL, 548 PCTRIE_LOCKED); 549 if (pctrie_isleaf(child)) { 550 m = pctrie_toval(child); 551 if (*m >= index) 552 return (m); 553 } else if (child != NULL) 554 goto descend; 555 556 /* 557 * Look for an available edge or val within the current 558 * bisection node. 559 */ 560 if (slot < (PCTRIE_COUNT - 1)) { 561 inc = PCTRIE_UNITLEVEL(node->pn_clev); 562 index = pctrie_trimkey(index, node->pn_clev); 563 do { 564 index += inc; 565 slot++; 566 child = pctrie_node_load(&node->pn_child[slot], 567 NULL, PCTRIE_LOCKED); 568 if (pctrie_isleaf(child)) { 569 m = pctrie_toval(child); 570 if (*m >= index) 571 return (m); 572 } else if (child != NULL) 573 goto descend; 574 } while (slot < (PCTRIE_COUNT - 1)); 575 } 576 KASSERT(child == NULL || pctrie_isleaf(child), 577 ("pctrie_lookup_ge: child is radix node")); 578 579 /* 580 * If a value or edge greater than the search slot is not found 581 * in the current node, ascend to the next higher-level node. 582 */ 583 goto ascend; 584 descend: 585 KASSERT(node->pn_clev > 0, 586 ("pctrie_lookup_ge: pushing leaf's parent")); 587 KASSERT(tos < PCTRIE_LIMIT, 588 ("pctrie_lookup_ge: stack overflow")); 589 stack[tos++] = node; 590 node = child; 591 } 592 } 593 594 /* 595 * Look up the nearest entry at a position less than or equal to index, 596 * assuming access is externally synchronized by a lock. 597 */ 598 uint64_t * 599 pctrie_lookup_le(struct pctrie *ptree, uint64_t index) 600 { 601 struct pctrie_node *stack[PCTRIE_LIMIT]; 602 uint64_t inc; 603 uint64_t *m; 604 struct pctrie_node *child, *node; 605 #ifdef INVARIANTS 606 int loops = 0; 607 #endif 608 unsigned tos; 609 int slot; 610 611 node = pctrie_root_load(ptree, NULL, PCTRIE_LOCKED); 612 if (node == NULL) 613 return (NULL); 614 else if (pctrie_isleaf(node)) { 615 m = pctrie_toval(node); 616 if (*m <= index) 617 return (m); 618 else 619 return (NULL); 620 } 621 tos = 0; 622 for (;;) { 623 /* 624 * If the keys differ before the current bisection node, 625 * then the search key might rollback to the earliest 626 * available bisection node or to the largest key 627 * in the current node (if the owner is smaller than the 628 * search key). 629 */ 630 if (pctrie_keybarr(node, index)) { 631 if (index > node->pn_owner) { 632 index = node->pn_owner + PCTRIE_COUNT * 633 PCTRIE_UNITLEVEL(node->pn_clev); 634 } else { 635 ascend: 636 KASSERT(++loops < 1000, 637 ("pctrie_lookup_le: too many loops")); 638 639 /* 640 * Pop nodes from the stack until either the 641 * stack is empty or a node that could have a 642 * matching descendant is found. 643 */ 644 do { 645 if (tos == 0) 646 return (NULL); 647 node = stack[--tos]; 648 } while (pctrie_slot(index, 649 node->pn_clev) == 0); 650 651 /* 652 * The following computation cannot overflow 653 * because index's slot at the current level 654 * is greater than 0. 655 */ 656 index = pctrie_trimkey(index, 657 node->pn_clev); 658 } 659 index--; 660 KASSERT(!pctrie_keybarr(node, index), 661 ("pctrie_lookup_le: keybarr failed")); 662 } 663 slot = pctrie_slot(index, node->pn_clev); 664 child = pctrie_node_load(&node->pn_child[slot], NULL, 665 PCTRIE_LOCKED); 666 if (pctrie_isleaf(child)) { 667 m = pctrie_toval(child); 668 if (*m <= index) 669 return (m); 670 } else if (child != NULL) 671 goto descend; 672 673 /* 674 * Look for an available edge or value within the current 675 * bisection node. 676 */ 677 if (slot > 0) { 678 inc = PCTRIE_UNITLEVEL(node->pn_clev); 679 index |= inc - 1; 680 do { 681 index -= inc; 682 slot--; 683 child = pctrie_node_load(&node->pn_child[slot], 684 NULL, PCTRIE_LOCKED); 685 if (pctrie_isleaf(child)) { 686 m = pctrie_toval(child); 687 if (*m <= index) 688 return (m); 689 } else if (child != NULL) 690 goto descend; 691 } while (slot > 0); 692 } 693 KASSERT(child == NULL || pctrie_isleaf(child), 694 ("pctrie_lookup_le: child is radix node")); 695 696 /* 697 * If a value or edge smaller than the search slot is not found 698 * in the current node, ascend to the next higher-level node. 699 */ 700 goto ascend; 701 descend: 702 KASSERT(node->pn_clev > 0, 703 ("pctrie_lookup_le: pushing leaf's parent")); 704 KASSERT(tos < PCTRIE_LIMIT, 705 ("pctrie_lookup_le: stack overflow")); 706 stack[tos++] = node; 707 node = child; 708 } 709 } 710 711 /* 712 * Remove the specified index from the tree. 713 * Panics if the key is not present. 714 */ 715 void 716 pctrie_remove(struct pctrie *ptree, uint64_t index, pctrie_free_t freefn) 717 { 718 struct pctrie_node *node, *parent, *tmp; 719 uint64_t *m; 720 int i, slot; 721 722 node = pctrie_root_load(ptree, NULL, PCTRIE_LOCKED); 723 if (pctrie_isleaf(node)) { 724 m = pctrie_toval(node); 725 if (*m != index) 726 panic("%s: invalid key found", __func__); 727 pctrie_root_store(ptree, NULL, PCTRIE_LOCKED); 728 return; 729 } 730 parent = NULL; 731 for (;;) { 732 if (node == NULL) 733 panic("pctrie_remove: impossible to locate the key"); 734 slot = pctrie_slot(index, node->pn_clev); 735 tmp = pctrie_node_load(&node->pn_child[slot], NULL, 736 PCTRIE_LOCKED); 737 if (pctrie_isleaf(tmp)) { 738 m = pctrie_toval(tmp); 739 if (*m != index) 740 panic("%s: invalid key found", __func__); 741 pctrie_node_store(&node->pn_child[slot], NULL, 742 PCTRIE_LOCKED); 743 node->pn_count--; 744 if (node->pn_count > 1) 745 break; 746 for (i = 0; i < PCTRIE_COUNT; i++) { 747 tmp = pctrie_node_load(&node->pn_child[i], 748 NULL, PCTRIE_LOCKED); 749 if (tmp != NULL) 750 break; 751 } 752 KASSERT(i != PCTRIE_COUNT, 753 ("%s: invalid node configuration", __func__)); 754 if (parent == NULL) 755 pctrie_root_store(ptree, tmp, PCTRIE_LOCKED); 756 else { 757 slot = pctrie_slot(index, parent->pn_clev); 758 KASSERT(pctrie_node_load( 759 &parent->pn_child[slot], NULL, 760 PCTRIE_LOCKED) == node, 761 ("%s: invalid child value", __func__)); 762 pctrie_node_store(&parent->pn_child[slot], tmp, 763 PCTRIE_LOCKED); 764 } 765 /* 766 * The child is still valid and we can not zero the 767 * pointer until all SMR references are gone. 768 */ 769 node->pn_count--; 770 pctrie_node_put(ptree, node, freefn, i); 771 break; 772 } 773 parent = node; 774 node = tmp; 775 } 776 } 777 778 /* 779 * Remove and free all the nodes from the tree. 780 * This function is recursive but there is a tight control on it as the 781 * maximum depth of the tree is fixed. 782 */ 783 void 784 pctrie_reclaim_allnodes(struct pctrie *ptree, pctrie_free_t freefn) 785 { 786 struct pctrie_node *root; 787 788 root = pctrie_root_load(ptree, NULL, PCTRIE_LOCKED); 789 if (root == NULL) 790 return; 791 pctrie_root_store(ptree, NULL, PCTRIE_UNSERIALIZED); 792 if (!pctrie_isleaf(root)) 793 pctrie_reclaim_allnodes_int(ptree, root, freefn); 794 } 795 796 #ifdef DDB 797 /* 798 * Show details about the given node. 799 */ 800 DB_SHOW_COMMAND(pctrienode, db_show_pctrienode) 801 { 802 struct pctrie_node *node, *tmp; 803 int i; 804 805 if (!have_addr) 806 return; 807 node = (struct pctrie_node *)addr; 808 db_printf("node %p, owner %jx, children count %u, level %u:\n", 809 (void *)node, (uintmax_t)node->pn_owner, node->pn_count, 810 node->pn_clev); 811 for (i = 0; i < PCTRIE_COUNT; i++) { 812 tmp = pctrie_node_load(&node->pn_child[i], NULL, 813 PCTRIE_UNSERIALIZED); 814 if (tmp != NULL) 815 db_printf("slot: %d, val: %p, value: %p, clev: %d\n", 816 i, (void *)tmp, 817 pctrie_isleaf(tmp) ? pctrie_toval(tmp) : NULL, 818 node->pn_clev); 819 } 820 } 821 #endif /* DDB */ 822