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: releng/12.0/sys/kern/subr_pctrie.c 326271 2017-11-27 15:20:12Z pfg $"); 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 59 #ifdef DDB 60 #include <ddb/ddb.h> 61 #endif 62 63 #define PCTRIE_MASK (PCTRIE_COUNT - 1) 64 #define PCTRIE_LIMIT (howmany(sizeof(uint64_t) * NBBY, PCTRIE_WIDTH) - 1) 65 66 /* Flag bits stored in node pointers. */ 67 #define PCTRIE_ISLEAF 0x1 68 #define PCTRIE_FLAGS 0x1 69 #define PCTRIE_PAD PCTRIE_FLAGS 70 71 /* Returns one unit associated with specified level. */ 72 #define PCTRIE_UNITLEVEL(lev) \ 73 ((uint64_t)1 << ((lev) * PCTRIE_WIDTH)) 74 75 struct pctrie_node { 76 uint64_t pn_owner; /* Owner of record. */ 77 uint16_t pn_count; /* Valid children. */ 78 uint16_t pn_clev; /* Current level. */ 79 void *pn_child[PCTRIE_COUNT]; /* Child nodes. */ 80 }; 81 82 /* 83 * Allocate a node. Pre-allocation should ensure that the request 84 * will always be satisfied. 85 */ 86 static __inline struct pctrie_node * 87 pctrie_node_get(struct pctrie *ptree, pctrie_alloc_t allocfn, uint64_t owner, 88 uint16_t count, uint16_t clevel) 89 { 90 struct pctrie_node *node; 91 92 node = allocfn(ptree); 93 if (node == NULL) 94 return (NULL); 95 node->pn_owner = owner; 96 node->pn_count = count; 97 node->pn_clev = clevel; 98 99 return (node); 100 } 101 102 /* 103 * Free radix node. 104 */ 105 static __inline void 106 pctrie_node_put(struct pctrie *ptree, struct pctrie_node *node, 107 pctrie_free_t freefn) 108 { 109 #ifdef INVARIANTS 110 int slot; 111 112 KASSERT(node->pn_count == 0, 113 ("pctrie_node_put: node %p has %d children", node, 114 node->pn_count)); 115 for (slot = 0; slot < PCTRIE_COUNT; slot++) 116 KASSERT(node->pn_child[slot] == NULL, 117 ("pctrie_node_put: node %p has a child", node)); 118 #endif 119 freefn(ptree, node); 120 } 121 122 /* 123 * Return the position in the array for a given level. 124 */ 125 static __inline int 126 pctrie_slot(uint64_t index, uint16_t level) 127 { 128 129 return ((index >> (level * PCTRIE_WIDTH)) & PCTRIE_MASK); 130 } 131 132 /* Trims the key after the specified level. */ 133 static __inline uint64_t 134 pctrie_trimkey(uint64_t index, uint16_t level) 135 { 136 uint64_t ret; 137 138 ret = index; 139 if (level > 0) { 140 ret >>= level * PCTRIE_WIDTH; 141 ret <<= level * PCTRIE_WIDTH; 142 } 143 return (ret); 144 } 145 146 /* 147 * Get the root node for a tree. 148 */ 149 static __inline struct pctrie_node * 150 pctrie_getroot(struct pctrie *ptree) 151 { 152 153 return ((struct pctrie_node *)ptree->pt_root); 154 } 155 156 /* 157 * Set the root node for a tree. 158 */ 159 static __inline void 160 pctrie_setroot(struct pctrie *ptree, struct pctrie_node *node) 161 { 162 163 ptree->pt_root = (uintptr_t)node; 164 } 165 166 /* 167 * Returns TRUE if the specified node is a leaf and FALSE otherwise. 168 */ 169 static __inline boolean_t 170 pctrie_isleaf(struct pctrie_node *node) 171 { 172 173 return (((uintptr_t)node & PCTRIE_ISLEAF) != 0); 174 } 175 176 /* 177 * Returns the associated val extracted from node. 178 */ 179 static __inline uint64_t * 180 pctrie_toval(struct pctrie_node *node) 181 { 182 183 return ((uint64_t *)((uintptr_t)node & ~PCTRIE_FLAGS)); 184 } 185 186 /* 187 * Adds the val as a child of the provided node. 188 */ 189 static __inline void 190 pctrie_addval(struct pctrie_node *node, uint64_t index, uint16_t clev, 191 uint64_t *val) 192 { 193 int slot; 194 195 slot = pctrie_slot(index, clev); 196 node->pn_child[slot] = (void *)((uintptr_t)val | PCTRIE_ISLEAF); 197 } 198 199 /* 200 * Returns the slot where two keys differ. 201 * It cannot accept 2 equal keys. 202 */ 203 static __inline uint16_t 204 pctrie_keydiff(uint64_t index1, uint64_t index2) 205 { 206 uint16_t clev; 207 208 KASSERT(index1 != index2, ("%s: passing the same key value %jx", 209 __func__, (uintmax_t)index1)); 210 211 index1 ^= index2; 212 for (clev = PCTRIE_LIMIT;; clev--) 213 if (pctrie_slot(index1, clev) != 0) 214 return (clev); 215 } 216 217 /* 218 * Returns TRUE if it can be determined that key does not belong to the 219 * specified node. Otherwise, returns FALSE. 220 */ 221 static __inline boolean_t 222 pctrie_keybarr(struct pctrie_node *node, uint64_t idx) 223 { 224 225 if (node->pn_clev < PCTRIE_LIMIT) { 226 idx = pctrie_trimkey(idx, node->pn_clev + 1); 227 return (idx != node->pn_owner); 228 } 229 return (FALSE); 230 } 231 232 /* 233 * Internal helper for pctrie_reclaim_allnodes(). 234 * This function is recursive. 235 */ 236 static void 237 pctrie_reclaim_allnodes_int(struct pctrie *ptree, struct pctrie_node *node, 238 pctrie_free_t freefn) 239 { 240 int slot; 241 242 KASSERT(node->pn_count <= PCTRIE_COUNT, 243 ("pctrie_reclaim_allnodes_int: bad count in node %p", node)); 244 for (slot = 0; node->pn_count != 0; slot++) { 245 if (node->pn_child[slot] == NULL) 246 continue; 247 if (!pctrie_isleaf(node->pn_child[slot])) 248 pctrie_reclaim_allnodes_int(ptree, 249 node->pn_child[slot], freefn); 250 node->pn_child[slot] = NULL; 251 node->pn_count--; 252 } 253 pctrie_node_put(ptree, node, freefn); 254 } 255 256 /* 257 * pctrie node zone initializer. 258 */ 259 int 260 pctrie_zone_init(void *mem, int size __unused, int flags __unused) 261 { 262 struct pctrie_node *node; 263 264 node = mem; 265 memset(node->pn_child, 0, sizeof(node->pn_child)); 266 return (0); 267 } 268 269 size_t 270 pctrie_node_size(void) 271 { 272 273 return (sizeof(struct pctrie_node)); 274 } 275 276 /* 277 * Inserts the key-value pair into the trie. 278 * Panics if the key already exists. 279 */ 280 int 281 pctrie_insert(struct pctrie *ptree, uint64_t *val, pctrie_alloc_t allocfn) 282 { 283 uint64_t index, newind; 284 void **parentp; 285 struct pctrie_node *node, *tmp; 286 uint64_t *m; 287 int slot; 288 uint16_t clev; 289 290 index = *val; 291 292 /* 293 * The owner of record for root is not really important because it 294 * will never be used. 295 */ 296 node = pctrie_getroot(ptree); 297 if (node == NULL) { 298 ptree->pt_root = (uintptr_t)val | PCTRIE_ISLEAF; 299 return (0); 300 } 301 parentp = (void **)&ptree->pt_root; 302 for (;;) { 303 if (pctrie_isleaf(node)) { 304 m = pctrie_toval(node); 305 if (*m == index) 306 panic("%s: key %jx is already present", 307 __func__, (uintmax_t)index); 308 clev = pctrie_keydiff(*m, index); 309 tmp = pctrie_node_get(ptree, allocfn, 310 pctrie_trimkey(index, clev + 1), 2, clev); 311 if (tmp == NULL) 312 return (ENOMEM); 313 *parentp = tmp; 314 pctrie_addval(tmp, index, clev, val); 315 pctrie_addval(tmp, *m, clev, m); 316 return (0); 317 } else if (pctrie_keybarr(node, index)) 318 break; 319 slot = pctrie_slot(index, node->pn_clev); 320 if (node->pn_child[slot] == NULL) { 321 node->pn_count++; 322 pctrie_addval(node, index, node->pn_clev, val); 323 return (0); 324 } 325 parentp = &node->pn_child[slot]; 326 node = node->pn_child[slot]; 327 } 328 329 /* 330 * A new node is needed because the right insertion level is reached. 331 * Setup the new intermediate node and add the 2 children: the 332 * new object and the older edge. 333 */ 334 newind = node->pn_owner; 335 clev = pctrie_keydiff(newind, index); 336 tmp = pctrie_node_get(ptree, allocfn, 337 pctrie_trimkey(index, clev + 1), 2, clev); 338 if (tmp == NULL) 339 return (ENOMEM); 340 *parentp = tmp; 341 pctrie_addval(tmp, index, clev, val); 342 slot = pctrie_slot(newind, clev); 343 tmp->pn_child[slot] = node; 344 345 return (0); 346 } 347 348 /* 349 * Returns the value stored at the index. If the index is not present, 350 * NULL is returned. 351 */ 352 uint64_t * 353 pctrie_lookup(struct pctrie *ptree, uint64_t index) 354 { 355 struct pctrie_node *node; 356 uint64_t *m; 357 int slot; 358 359 node = pctrie_getroot(ptree); 360 while (node != NULL) { 361 if (pctrie_isleaf(node)) { 362 m = pctrie_toval(node); 363 if (*m == index) 364 return (m); 365 else 366 break; 367 } else if (pctrie_keybarr(node, index)) 368 break; 369 slot = pctrie_slot(index, node->pn_clev); 370 node = node->pn_child[slot]; 371 } 372 return (NULL); 373 } 374 375 /* 376 * Look up the nearest entry at a position bigger than or equal to index. 377 */ 378 uint64_t * 379 pctrie_lookup_ge(struct pctrie *ptree, uint64_t index) 380 { 381 struct pctrie_node *stack[PCTRIE_LIMIT]; 382 uint64_t inc; 383 uint64_t *m; 384 struct pctrie_node *child, *node; 385 #ifdef INVARIANTS 386 int loops = 0; 387 #endif 388 int slot, tos; 389 390 node = pctrie_getroot(ptree); 391 if (node == NULL) 392 return (NULL); 393 else if (pctrie_isleaf(node)) { 394 m = pctrie_toval(node); 395 if (*m >= index) 396 return (m); 397 else 398 return (NULL); 399 } 400 tos = 0; 401 for (;;) { 402 /* 403 * If the keys differ before the current bisection node, 404 * then the search key might rollback to the earliest 405 * available bisection node or to the smallest key 406 * in the current node (if the owner is bigger than the 407 * search key). 408 */ 409 if (pctrie_keybarr(node, index)) { 410 if (index > node->pn_owner) { 411 ascend: 412 KASSERT(++loops < 1000, 413 ("pctrie_lookup_ge: too many loops")); 414 415 /* 416 * Pop nodes from the stack until either the 417 * stack is empty or a node that could have a 418 * matching descendant is found. 419 */ 420 do { 421 if (tos == 0) 422 return (NULL); 423 node = stack[--tos]; 424 } while (pctrie_slot(index, 425 node->pn_clev) == (PCTRIE_COUNT - 1)); 426 427 /* 428 * The following computation cannot overflow 429 * because index's slot at the current level 430 * is less than PCTRIE_COUNT - 1. 431 */ 432 index = pctrie_trimkey(index, 433 node->pn_clev); 434 index += PCTRIE_UNITLEVEL(node->pn_clev); 435 } else 436 index = node->pn_owner; 437 KASSERT(!pctrie_keybarr(node, index), 438 ("pctrie_lookup_ge: keybarr failed")); 439 } 440 slot = pctrie_slot(index, node->pn_clev); 441 child = node->pn_child[slot]; 442 if (pctrie_isleaf(child)) { 443 m = pctrie_toval(child); 444 if (*m >= index) 445 return (m); 446 } else if (child != NULL) 447 goto descend; 448 449 /* 450 * Look for an available edge or val within the current 451 * bisection node. 452 */ 453 if (slot < (PCTRIE_COUNT - 1)) { 454 inc = PCTRIE_UNITLEVEL(node->pn_clev); 455 index = pctrie_trimkey(index, node->pn_clev); 456 do { 457 index += inc; 458 slot++; 459 child = node->pn_child[slot]; 460 if (pctrie_isleaf(child)) { 461 m = pctrie_toval(child); 462 if (*m >= index) 463 return (m); 464 } else if (child != NULL) 465 goto descend; 466 } while (slot < (PCTRIE_COUNT - 1)); 467 } 468 KASSERT(child == NULL || pctrie_isleaf(child), 469 ("pctrie_lookup_ge: child is radix node")); 470 471 /* 472 * If a value or edge bigger than the search slot is not found 473 * in the current node, ascend to the next higher-level node. 474 */ 475 goto ascend; 476 descend: 477 KASSERT(node->pn_clev > 0, 478 ("pctrie_lookup_ge: pushing leaf's parent")); 479 KASSERT(tos < PCTRIE_LIMIT, 480 ("pctrie_lookup_ge: stack overflow")); 481 stack[tos++] = node; 482 node = child; 483 } 484 } 485 486 /* 487 * Look up the nearest entry at a position less than or equal to index. 488 */ 489 uint64_t * 490 pctrie_lookup_le(struct pctrie *ptree, uint64_t index) 491 { 492 struct pctrie_node *stack[PCTRIE_LIMIT]; 493 uint64_t inc; 494 uint64_t *m; 495 struct pctrie_node *child, *node; 496 #ifdef INVARIANTS 497 int loops = 0; 498 #endif 499 int slot, tos; 500 501 node = pctrie_getroot(ptree); 502 if (node == NULL) 503 return (NULL); 504 else if (pctrie_isleaf(node)) { 505 m = pctrie_toval(node); 506 if (*m <= index) 507 return (m); 508 else 509 return (NULL); 510 } 511 tos = 0; 512 for (;;) { 513 /* 514 * If the keys differ before the current bisection node, 515 * then the search key might rollback to the earliest 516 * available bisection node or to the largest key 517 * in the current node (if the owner is smaller than the 518 * search key). 519 */ 520 if (pctrie_keybarr(node, index)) { 521 if (index > node->pn_owner) { 522 index = node->pn_owner + PCTRIE_COUNT * 523 PCTRIE_UNITLEVEL(node->pn_clev); 524 } else { 525 ascend: 526 KASSERT(++loops < 1000, 527 ("pctrie_lookup_le: too many loops")); 528 529 /* 530 * Pop nodes from the stack until either the 531 * stack is empty or a node that could have a 532 * matching descendant is found. 533 */ 534 do { 535 if (tos == 0) 536 return (NULL); 537 node = stack[--tos]; 538 } while (pctrie_slot(index, 539 node->pn_clev) == 0); 540 541 /* 542 * The following computation cannot overflow 543 * because index's slot at the current level 544 * is greater than 0. 545 */ 546 index = pctrie_trimkey(index, 547 node->pn_clev); 548 } 549 index--; 550 KASSERT(!pctrie_keybarr(node, index), 551 ("pctrie_lookup_le: keybarr failed")); 552 } 553 slot = pctrie_slot(index, node->pn_clev); 554 child = node->pn_child[slot]; 555 if (pctrie_isleaf(child)) { 556 m = pctrie_toval(child); 557 if (*m <= index) 558 return (m); 559 } else if (child != NULL) 560 goto descend; 561 562 /* 563 * Look for an available edge or value within the current 564 * bisection node. 565 */ 566 if (slot > 0) { 567 inc = PCTRIE_UNITLEVEL(node->pn_clev); 568 index |= inc - 1; 569 do { 570 index -= inc; 571 slot--; 572 child = node->pn_child[slot]; 573 if (pctrie_isleaf(child)) { 574 m = pctrie_toval(child); 575 if (*m <= index) 576 return (m); 577 } else if (child != NULL) 578 goto descend; 579 } while (slot > 0); 580 } 581 KASSERT(child == NULL || pctrie_isleaf(child), 582 ("pctrie_lookup_le: child is radix node")); 583 584 /* 585 * If a value or edge smaller than the search slot is not found 586 * in the current node, ascend to the next higher-level node. 587 */ 588 goto ascend; 589 descend: 590 KASSERT(node->pn_clev > 0, 591 ("pctrie_lookup_le: pushing leaf's parent")); 592 KASSERT(tos < PCTRIE_LIMIT, 593 ("pctrie_lookup_le: stack overflow")); 594 stack[tos++] = node; 595 node = child; 596 } 597 } 598 599 /* 600 * Remove the specified index from the tree. 601 * Panics if the key is not present. 602 */ 603 void 604 pctrie_remove(struct pctrie *ptree, uint64_t index, pctrie_free_t freefn) 605 { 606 struct pctrie_node *node, *parent; 607 uint64_t *m; 608 int i, slot; 609 610 node = pctrie_getroot(ptree); 611 if (pctrie_isleaf(node)) { 612 m = pctrie_toval(node); 613 if (*m != index) 614 panic("%s: invalid key found", __func__); 615 pctrie_setroot(ptree, NULL); 616 return; 617 } 618 parent = NULL; 619 for (;;) { 620 if (node == NULL) 621 panic("pctrie_remove: impossible to locate the key"); 622 slot = pctrie_slot(index, node->pn_clev); 623 if (pctrie_isleaf(node->pn_child[slot])) { 624 m = pctrie_toval(node->pn_child[slot]); 625 if (*m != index) 626 panic("%s: invalid key found", __func__); 627 node->pn_child[slot] = NULL; 628 node->pn_count--; 629 if (node->pn_count > 1) 630 break; 631 for (i = 0; i < PCTRIE_COUNT; i++) 632 if (node->pn_child[i] != NULL) 633 break; 634 KASSERT(i != PCTRIE_COUNT, 635 ("%s: invalid node configuration", __func__)); 636 if (parent == NULL) 637 pctrie_setroot(ptree, node->pn_child[i]); 638 else { 639 slot = pctrie_slot(index, parent->pn_clev); 640 KASSERT(parent->pn_child[slot] == node, 641 ("%s: invalid child value", __func__)); 642 parent->pn_child[slot] = node->pn_child[i]; 643 } 644 node->pn_count--; 645 node->pn_child[i] = NULL; 646 pctrie_node_put(ptree, node, freefn); 647 break; 648 } 649 parent = node; 650 node = node->pn_child[slot]; 651 } 652 } 653 654 /* 655 * Remove and free all the nodes from the tree. 656 * This function is recursive but there is a tight control on it as the 657 * maximum depth of the tree is fixed. 658 */ 659 void 660 pctrie_reclaim_allnodes(struct pctrie *ptree, pctrie_free_t freefn) 661 { 662 struct pctrie_node *root; 663 664 root = pctrie_getroot(ptree); 665 if (root == NULL) 666 return; 667 pctrie_setroot(ptree, NULL); 668 if (!pctrie_isleaf(root)) 669 pctrie_reclaim_allnodes_int(ptree, root, freefn); 670 } 671 672 #ifdef DDB 673 /* 674 * Show details about the given node. 675 */ 676 DB_SHOW_COMMAND(pctrienode, db_show_pctrienode) 677 { 678 struct pctrie_node *node; 679 int i; 680 681 if (!have_addr) 682 return; 683 node = (struct pctrie_node *)addr; 684 db_printf("node %p, owner %jx, children count %u, level %u:\n", 685 (void *)node, (uintmax_t)node->pn_owner, node->pn_count, 686 node->pn_clev); 687 for (i = 0; i < PCTRIE_COUNT; i++) 688 if (node->pn_child[i] != NULL) 689 db_printf("slot: %d, val: %p, value: %p, clev: %d\n", 690 i, (void *)node->pn_child[i], 691 pctrie_isleaf(node->pn_child[i]) ? 692 pctrie_toval(node->pn_child[i]) : NULL, 693 node->pn_clev); 694 } 695 #endif /* DDB */
Cache object: 40807957d3be9f374f250d6a6717130e
[ source navigation ] [ diff markup ] [ identifier search ] [ freetext search ] [ file search ] [ list types ] [ track identifier ]