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 * Adds the val as a child of the provided node. 260 */ 261 static __inline void 262 pctrie_addval(struct pctrie_node *node, uint64_t index, uint16_t clev, 263 uint64_t *val, enum pctrie_access access) 264 { 265 int slot; 266 267 slot = pctrie_slot(index, clev); 268 pctrie_node_store(&node->pn_child[slot], 269 pctrie_toleaf(val), access); 270 node->pn_popmap ^= 1 << slot; 271 KASSERT((node->pn_popmap & (1 << slot)) != 0, 272 ("%s: bad popmap slot %d in node %p", __func__, slot, node)); 273 } 274 275 /* 276 * Returns the level where two keys differ. 277 * It cannot accept 2 equal keys. 278 */ 279 static __inline uint16_t 280 pctrie_keydiff(uint64_t index1, uint64_t index2) 281 { 282 283 KASSERT(index1 != index2, ("%s: passing the same key value %jx", 284 __func__, (uintmax_t)index1)); 285 CTASSERT(sizeof(long long) >= sizeof(uint64_t)); 286 287 /* 288 * From the highest-order bit where the indexes differ, 289 * compute the highest level in the trie where they differ. 290 */ 291 return ((flsll(index1 ^ index2) - 1) / PCTRIE_WIDTH); 292 } 293 294 /* 295 * Returns TRUE if it can be determined that key does not belong to the 296 * specified node. Otherwise, returns FALSE. 297 */ 298 static __inline bool 299 pctrie_keybarr(struct pctrie_node *node, uint64_t idx) 300 { 301 302 if (node->pn_clev < PCTRIE_LIMIT) { 303 idx = pctrie_trimkey(idx, node->pn_clev + 1); 304 return (idx != node->pn_owner); 305 } 306 return (false); 307 } 308 309 /* 310 * Internal helper for pctrie_reclaim_allnodes(). 311 * This function is recursive. 312 */ 313 static void 314 pctrie_reclaim_allnodes_int(struct pctrie *ptree, struct pctrie_node *node, 315 pctrie_free_t freefn) 316 { 317 struct pctrie_node *child; 318 int slot; 319 320 while (node->pn_popmap != 0) { 321 slot = ffs(node->pn_popmap) - 1; 322 child = pctrie_node_load(&node->pn_child[slot], NULL, 323 PCTRIE_UNSERIALIZED); 324 KASSERT(child != NULL, ("%s: bad popmap slot %d in node %p", 325 __func__, slot, node)); 326 if (!pctrie_isleaf(child)) 327 pctrie_reclaim_allnodes_int(ptree, child, freefn); 328 node->pn_popmap ^= 1 << slot; 329 pctrie_node_store(&node->pn_child[slot], NULL, 330 PCTRIE_UNSERIALIZED); 331 } 332 pctrie_node_put(ptree, node, freefn); 333 } 334 335 /* 336 * pctrie node zone initializer. 337 */ 338 int 339 pctrie_zone_init(void *mem, int size __unused, int flags __unused) 340 { 341 struct pctrie_node *node; 342 343 node = mem; 344 node->pn_popmap = 0; 345 memset(node->pn_child, 0, sizeof(node->pn_child)); 346 return (0); 347 } 348 349 size_t 350 pctrie_node_size(void) 351 { 352 353 return (sizeof(struct pctrie_node)); 354 } 355 356 /* 357 * Inserts the key-value pair into the trie. 358 * Panics if the key already exists. 359 */ 360 int 361 pctrie_insert(struct pctrie *ptree, uint64_t *val, pctrie_alloc_t allocfn) 362 { 363 uint64_t index, newind; 364 struct pctrie_node *node, *tmp; 365 smr_pctnode_t *parentp; 366 uint64_t *m; 367 int slot; 368 uint16_t clev; 369 370 index = *val; 371 372 /* 373 * The owner of record for root is not really important because it 374 * will never be used. 375 */ 376 node = pctrie_root_load(ptree, NULL, PCTRIE_LOCKED); 377 if (node == NULL) { 378 ptree->pt_root = (uintptr_t)pctrie_toleaf(val); 379 return (0); 380 } 381 parentp = (smr_pctnode_t *)&ptree->pt_root; 382 for (;;) { 383 if (pctrie_isleaf(node)) { 384 m = pctrie_toval(node); 385 if (*m == index) 386 panic("%s: key %jx is already present", 387 __func__, (uintmax_t)index); 388 clev = pctrie_keydiff(*m, index); 389 tmp = pctrie_node_get(ptree, allocfn, index, clev); 390 if (tmp == NULL) 391 return (ENOMEM); 392 /* These writes are not yet visible due to ordering. */ 393 pctrie_addval(tmp, index, clev, val, 394 PCTRIE_UNSERIALIZED); 395 pctrie_addval(tmp, *m, clev, m, PCTRIE_UNSERIALIZED); 396 /* Synchronize to make leaf visible. */ 397 pctrie_node_store(parentp, tmp, PCTRIE_LOCKED); 398 return (0); 399 } else if (pctrie_keybarr(node, index)) 400 break; 401 slot = pctrie_slot(index, node->pn_clev); 402 parentp = &node->pn_child[slot]; 403 tmp = pctrie_node_load(parentp, NULL, PCTRIE_LOCKED); 404 if (tmp == NULL) { 405 pctrie_addval(node, index, node->pn_clev, val, 406 PCTRIE_LOCKED); 407 return (0); 408 } 409 node = tmp; 410 } 411 412 /* 413 * A new node is needed because the right insertion level is reached. 414 * Setup the new intermediate node and add the 2 children: the 415 * new object and the older edge. 416 */ 417 newind = node->pn_owner; 418 clev = pctrie_keydiff(newind, index); 419 tmp = pctrie_node_get(ptree, allocfn, index, clev); 420 if (tmp == NULL) 421 return (ENOMEM); 422 slot = pctrie_slot(newind, clev); 423 /* These writes are not yet visible due to ordering. */ 424 pctrie_addval(tmp, index, clev, val, PCTRIE_UNSERIALIZED); 425 pctrie_node_store(&tmp->pn_child[slot], node, PCTRIE_UNSERIALIZED); 426 tmp->pn_popmap ^= 1 << slot; 427 /* Synchronize to make the above visible. */ 428 pctrie_node_store(parentp, tmp, PCTRIE_LOCKED); 429 430 return (0); 431 } 432 433 /* 434 * Returns the value stored at the index. If the index is not present, 435 * NULL is returned. 436 */ 437 static __always_inline uint64_t * 438 _pctrie_lookup(struct pctrie *ptree, uint64_t index, smr_t smr, 439 enum pctrie_access access) 440 { 441 struct pctrie_node *node; 442 uint64_t *m; 443 int slot; 444 445 node = pctrie_root_load(ptree, smr, access); 446 while (node != NULL) { 447 if (pctrie_isleaf(node)) { 448 m = pctrie_toval(node); 449 if (*m == index) 450 return (m); 451 break; 452 } 453 if (pctrie_keybarr(node, index)) 454 break; 455 slot = pctrie_slot(index, node->pn_clev); 456 node = pctrie_node_load(&node->pn_child[slot], smr, access); 457 } 458 return (NULL); 459 } 460 461 /* 462 * Returns the value stored at the index, assuming access is externally 463 * synchronized by a lock. 464 * 465 * If the index is not present, NULL is returned. 466 */ 467 uint64_t * 468 pctrie_lookup(struct pctrie *ptree, uint64_t index) 469 { 470 return (_pctrie_lookup(ptree, index, NULL, PCTRIE_LOCKED)); 471 } 472 473 /* 474 * Returns the value stored at the index without requiring an external lock. 475 * 476 * If the index is not present, NULL is returned. 477 */ 478 uint64_t * 479 pctrie_lookup_unlocked(struct pctrie *ptree, uint64_t index, smr_t smr) 480 { 481 uint64_t *res; 482 483 smr_enter(smr); 484 res = _pctrie_lookup(ptree, index, smr, PCTRIE_SMR); 485 smr_exit(smr); 486 return (res); 487 } 488 489 /* 490 * Look up the nearest entry at a position bigger than or equal to index, 491 * assuming access is externally synchronized by a lock. 492 */ 493 uint64_t * 494 pctrie_lookup_ge(struct pctrie *ptree, uint64_t index) 495 { 496 struct pctrie_node *stack[PCTRIE_LIMIT]; 497 uint64_t *m; 498 struct pctrie_node *child, *node; 499 #ifdef INVARIANTS 500 int loops = 0; 501 #endif 502 unsigned tos; 503 int slot; 504 505 node = pctrie_root_load(ptree, NULL, PCTRIE_LOCKED); 506 if (node == NULL) 507 return (NULL); 508 else if (pctrie_isleaf(node)) { 509 m = pctrie_toval(node); 510 if (*m >= index) 511 return (m); 512 else 513 return (NULL); 514 } 515 tos = 0; 516 for (;;) { 517 /* 518 * If the keys differ before the current bisection node, 519 * then the search key might rollback to the earliest 520 * available bisection node or to the smallest key 521 * in the current node (if the owner is greater than the 522 * search key). 523 */ 524 if (pctrie_keybarr(node, index)) { 525 if (index > node->pn_owner) { 526 ascend: 527 KASSERT(++loops < 1000, 528 ("pctrie_lookup_ge: too many loops")); 529 530 /* 531 * Pop nodes from the stack until either the 532 * stack is empty or a node that could have a 533 * matching descendant is found. 534 */ 535 do { 536 if (tos == 0) 537 return (NULL); 538 node = stack[--tos]; 539 } while (pctrie_slot(index, 540 node->pn_clev) == (PCTRIE_COUNT - 1)); 541 542 /* 543 * The following computation cannot overflow 544 * because index's slot at the current level 545 * is less than PCTRIE_COUNT - 1. 546 */ 547 index = pctrie_trimkey(index, 548 node->pn_clev); 549 index += PCTRIE_UNITLEVEL(node->pn_clev); 550 } else 551 index = node->pn_owner; 552 KASSERT(!pctrie_keybarr(node, index), 553 ("pctrie_lookup_ge: keybarr failed")); 554 } 555 slot = pctrie_slot(index, node->pn_clev); 556 child = pctrie_node_load(&node->pn_child[slot], NULL, 557 PCTRIE_LOCKED); 558 if (pctrie_isleaf(child)) { 559 m = pctrie_toval(child); 560 if (*m >= index) 561 return (m); 562 } else if (child != NULL) 563 goto descend; 564 565 /* Find the first set bit beyond the first slot+1 bits. */ 566 slot = ffs(node->pn_popmap & (-2 << slot)) - 1; 567 if (slot < 0) { 568 /* 569 * A value or edge greater than the search slot is not 570 * found in the current node; ascend to the next 571 * higher-level node. 572 */ 573 goto ascend; 574 } 575 child = pctrie_node_load(&node->pn_child[slot], 576 NULL, PCTRIE_LOCKED); 577 KASSERT(child != NULL, ("%s: bad popmap slot %d in node %p", 578 __func__, slot, node)); 579 if (pctrie_isleaf(child)) 580 return (pctrie_toval(child)); 581 index = pctrie_trimkey(index, node->pn_clev + 1) + 582 slot * PCTRIE_UNITLEVEL(node->pn_clev); 583 descend: 584 KASSERT(node->pn_clev > 0, 585 ("pctrie_lookup_ge: pushing leaf's parent")); 586 KASSERT(tos < PCTRIE_LIMIT, 587 ("pctrie_lookup_ge: stack overflow")); 588 stack[tos++] = node; 589 node = child; 590 } 591 } 592 593 /* 594 * Look up the nearest entry at a position less than or equal to index, 595 * assuming access is externally synchronized by a lock. 596 */ 597 uint64_t * 598 pctrie_lookup_le(struct pctrie *ptree, uint64_t index) 599 { 600 struct pctrie_node *stack[PCTRIE_LIMIT]; 601 uint64_t *m; 602 struct pctrie_node *child, *node; 603 #ifdef INVARIANTS 604 int loops = 0; 605 #endif 606 unsigned tos; 607 int slot; 608 609 node = pctrie_root_load(ptree, NULL, PCTRIE_LOCKED); 610 if (node == NULL) 611 return (NULL); 612 else if (pctrie_isleaf(node)) { 613 m = pctrie_toval(node); 614 if (*m <= index) 615 return (m); 616 else 617 return (NULL); 618 } 619 tos = 0; 620 for (;;) { 621 /* 622 * If the keys differ before the current bisection node, 623 * then the search key might rollback to the earliest 624 * available bisection node or to the largest key 625 * in the current node (if the owner is smaller than the 626 * search key). 627 */ 628 if (pctrie_keybarr(node, index)) { 629 if (index > node->pn_owner) { 630 index = node->pn_owner + PCTRIE_COUNT * 631 PCTRIE_UNITLEVEL(node->pn_clev); 632 } else { 633 ascend: 634 KASSERT(++loops < 1000, 635 ("pctrie_lookup_le: too many loops")); 636 637 /* 638 * Pop nodes from the stack until either the 639 * stack is empty or a node that could have a 640 * matching descendant is found. 641 */ 642 do { 643 if (tos == 0) 644 return (NULL); 645 node = stack[--tos]; 646 } while (pctrie_slot(index, 647 node->pn_clev) == 0); 648 649 /* 650 * The following computation cannot overflow 651 * because index's slot at the current level 652 * is greater than 0. 653 */ 654 index = pctrie_trimkey(index, 655 node->pn_clev); 656 } 657 index--; 658 KASSERT(!pctrie_keybarr(node, index), 659 ("pctrie_lookup_le: keybarr failed")); 660 } 661 slot = pctrie_slot(index, node->pn_clev); 662 child = pctrie_node_load(&node->pn_child[slot], NULL, 663 PCTRIE_LOCKED); 664 if (pctrie_isleaf(child)) { 665 m = pctrie_toval(child); 666 if (*m <= index) 667 return (m); 668 } else if (child != NULL) 669 goto descend; 670 671 /* Find the last set bit among the first slot bits. */ 672 slot = fls(node->pn_popmap & ((1 << slot) - 1)) - 1; 673 if (slot < 0) { 674 /* 675 * A value or edge smaller than the search slot is not 676 * found in the current node; ascend to the next 677 * higher-level node. 678 */ 679 goto ascend; 680 } 681 child = pctrie_node_load(&node->pn_child[slot], 682 NULL, PCTRIE_LOCKED); 683 if (pctrie_isleaf(child)) 684 return (pctrie_toval(child)); 685 index = pctrie_trimkey(index, node->pn_clev + 1) + 686 (slot + 1) * PCTRIE_UNITLEVEL(node->pn_clev) - 1; 687 descend: 688 KASSERT(node->pn_clev > 0, 689 ("pctrie_lookup_le: pushing leaf's parent")); 690 KASSERT(tos < PCTRIE_LIMIT, 691 ("pctrie_lookup_le: stack overflow")); 692 stack[tos++] = node; 693 node = child; 694 } 695 } 696 697 /* 698 * Remove the specified index from the tree. 699 * Panics if the key is not present. 700 */ 701 void 702 pctrie_remove(struct pctrie *ptree, uint64_t index, pctrie_free_t freefn) 703 { 704 struct pctrie_node *node, *parent, *tmp; 705 uint64_t *m; 706 int slot; 707 708 node = pctrie_root_load(ptree, NULL, PCTRIE_LOCKED); 709 if (pctrie_isleaf(node)) { 710 m = pctrie_toval(node); 711 if (*m != index) 712 panic("%s: invalid key found", __func__); 713 pctrie_root_store(ptree, NULL, PCTRIE_LOCKED); 714 return; 715 } 716 parent = NULL; 717 for (;;) { 718 if (node == NULL) 719 panic("pctrie_remove: impossible to locate the key"); 720 slot = pctrie_slot(index, node->pn_clev); 721 tmp = pctrie_node_load(&node->pn_child[slot], NULL, 722 PCTRIE_LOCKED); 723 if (pctrie_isleaf(tmp)) { 724 m = pctrie_toval(tmp); 725 if (*m != index) 726 panic("%s: invalid key found", __func__); 727 KASSERT((node->pn_popmap & (1 << slot)) != 0, 728 ("%s: bad popmap slot %d in node %p", 729 __func__, slot, node)); 730 node->pn_popmap ^= 1 << slot; 731 pctrie_node_store(&node->pn_child[slot], NULL, 732 PCTRIE_LOCKED); 733 if (!powerof2(node->pn_popmap)) 734 break; 735 KASSERT(node->pn_popmap != 0, 736 ("%s: bad popmap all zeroes", __func__)); 737 slot = ffs(node->pn_popmap) - 1; 738 tmp = pctrie_node_load(&node->pn_child[slot], 739 NULL, PCTRIE_LOCKED); 740 KASSERT(tmp != NULL, 741 ("%s: bad popmap slot %d in node %p", 742 __func__, slot, node)); 743 if (parent == NULL) 744 pctrie_root_store(ptree, tmp, PCTRIE_LOCKED); 745 else { 746 slot = pctrie_slot(index, parent->pn_clev); 747 KASSERT(pctrie_node_load( 748 &parent->pn_child[slot], NULL, 749 PCTRIE_LOCKED) == node, 750 ("%s: invalid child value", __func__)); 751 pctrie_node_store(&parent->pn_child[slot], tmp, 752 PCTRIE_LOCKED); 753 } 754 /* 755 * The child is still valid and we can not zero the 756 * pointer until all SMR references are gone. 757 */ 758 pctrie_node_put(ptree, node, freefn); 759 break; 760 } 761 parent = node; 762 node = tmp; 763 } 764 } 765 766 /* 767 * Remove and free all the nodes from the tree. 768 * This function is recursive but there is a tight control on it as the 769 * maximum depth of the tree is fixed. 770 */ 771 void 772 pctrie_reclaim_allnodes(struct pctrie *ptree, pctrie_free_t freefn) 773 { 774 struct pctrie_node *root; 775 776 root = pctrie_root_load(ptree, NULL, PCTRIE_LOCKED); 777 if (root == NULL) 778 return; 779 pctrie_root_store(ptree, NULL, PCTRIE_UNSERIALIZED); 780 if (!pctrie_isleaf(root)) 781 pctrie_reclaim_allnodes_int(ptree, root, freefn); 782 } 783 784 #ifdef DDB 785 /* 786 * Show details about the given node. 787 */ 788 DB_SHOW_COMMAND(pctrienode, db_show_pctrienode) 789 { 790 struct pctrie_node *node, *tmp; 791 int slot; 792 pn_popmap_t popmap; 793 794 if (!have_addr) 795 return; 796 node = (struct pctrie_node *)addr; 797 db_printf("node %p, owner %jx, children popmap %04x, level %u:\n", 798 (void *)node, (uintmax_t)node->pn_owner, node->pn_popmap, 799 node->pn_clev); 800 for (popmap = node->pn_popmap; popmap != 0; popmap ^= 1 << slot) { 801 slot = ffs(popmap) - 1; 802 tmp = pctrie_node_load(&node->pn_child[slot], NULL, 803 PCTRIE_UNSERIALIZED); 804 db_printf("slot: %d, val: %p, value: %p, clev: %d\n", 805 slot, (void *)tmp, 806 pctrie_isleaf(tmp) ? pctrie_toval(tmp) : NULL, 807 node->pn_clev); 808 } 809 } 810 #endif /* DDB */ 811