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