2 * SPDX-License-Identifier: BSD-2-Clause-FreeBSD
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>
9 * Redistribution and use in source and binary forms, with or without
10 * modification, are permitted provided that the following conditions
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.
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
33 * Path-compressed radix trie implementation.
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
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.
49 #include <sys/cdefs.h>
50 __FBSDID("$FreeBSD$");
54 #include <sys/param.h>
55 #include <sys/systm.h>
56 #include <sys/kernel.h>
57 #include <sys/pctrie.h>
63 #define PCTRIE_MASK (PCTRIE_COUNT - 1)
64 #define PCTRIE_LIMIT (howmany(sizeof(uint64_t) * NBBY, PCTRIE_WIDTH) - 1)
66 /* Flag bits stored in node pointers. */
67 #define PCTRIE_ISLEAF 0x1
68 #define PCTRIE_FLAGS 0x1
69 #define PCTRIE_PAD PCTRIE_FLAGS
71 /* Returns one unit associated with specified level. */
72 #define PCTRIE_UNITLEVEL(lev) \
73 ((uint64_t)1 << ((lev) * PCTRIE_WIDTH))
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. */
83 * Allocate a node. Pre-allocation should ensure that the request
84 * will always be satisfied.
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)
90 struct pctrie_node *node;
92 node = allocfn(ptree);
95 node->pn_owner = owner;
96 node->pn_count = count;
97 node->pn_clev = clevel;
106 pctrie_node_put(struct pctrie *ptree, struct pctrie_node *node,
107 pctrie_free_t freefn)
112 KASSERT(node->pn_count == 0,
113 ("pctrie_node_put: node %p has %d children", node,
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));
123 * Return the position in the array for a given level.
126 pctrie_slot(uint64_t index, uint16_t level)
129 return ((index >> (level * PCTRIE_WIDTH)) & PCTRIE_MASK);
132 /* Trims the key after the specified level. */
133 static __inline uint64_t
134 pctrie_trimkey(uint64_t index, uint16_t level)
140 ret >>= level * PCTRIE_WIDTH;
141 ret <<= level * PCTRIE_WIDTH;
147 * Get the root node for a tree.
149 static __inline struct pctrie_node *
150 pctrie_getroot(struct pctrie *ptree)
153 return ((struct pctrie_node *)ptree->pt_root);
157 * Set the root node for a tree.
160 pctrie_setroot(struct pctrie *ptree, struct pctrie_node *node)
163 ptree->pt_root = (uintptr_t)node;
167 * Returns TRUE if the specified node is a leaf and FALSE otherwise.
170 pctrie_isleaf(struct pctrie_node *node)
173 return (((uintptr_t)node & PCTRIE_ISLEAF) != 0);
177 * Returns the associated val extracted from node.
179 static __inline uint64_t *
180 pctrie_toval(struct pctrie_node *node)
183 return ((uint64_t *)((uintptr_t)node & ~PCTRIE_FLAGS));
187 * Adds the val as a child of the provided node.
190 pctrie_addval(struct pctrie_node *node, uint64_t index, uint16_t clev,
195 slot = pctrie_slot(index, clev);
196 node->pn_child[slot] = (void *)((uintptr_t)val | PCTRIE_ISLEAF);
200 * Returns the slot where two keys differ.
201 * It cannot accept 2 equal keys.
203 static __inline uint16_t
204 pctrie_keydiff(uint64_t index1, uint64_t index2)
208 KASSERT(index1 != index2, ("%s: passing the same key value %jx",
209 __func__, (uintmax_t)index1));
212 for (clev = PCTRIE_LIMIT;; clev--)
213 if (pctrie_slot(index1, clev) != 0)
218 * Returns TRUE if it can be determined that key does not belong to the
219 * specified node. Otherwise, returns FALSE.
222 pctrie_keybarr(struct pctrie_node *node, uint64_t idx)
225 if (node->pn_clev < PCTRIE_LIMIT) {
226 idx = pctrie_trimkey(idx, node->pn_clev + 1);
227 return (idx != node->pn_owner);
233 * Internal helper for pctrie_reclaim_allnodes().
234 * This function is recursive.
237 pctrie_reclaim_allnodes_int(struct pctrie *ptree, struct pctrie_node *node,
238 pctrie_free_t freefn)
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)
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;
253 pctrie_node_put(ptree, node, freefn);
257 * pctrie node zone initializer.
260 pctrie_zone_init(void *mem, int size __unused, int flags __unused)
262 struct pctrie_node *node;
265 memset(node->pn_child, 0, sizeof(node->pn_child));
270 pctrie_node_size(void)
273 return (sizeof(struct pctrie_node));
277 * Inserts the key-value pair into the trie.
278 * Panics if the key already exists.
281 pctrie_insert(struct pctrie *ptree, uint64_t *val, pctrie_alloc_t allocfn)
283 uint64_t index, newind;
285 struct pctrie_node *node, *tmp;
293 * The owner of record for root is not really important because it
294 * will never be used.
296 node = pctrie_getroot(ptree);
298 ptree->pt_root = (uintptr_t)val | PCTRIE_ISLEAF;
301 parentp = (void **)&ptree->pt_root;
303 if (pctrie_isleaf(node)) {
304 m = pctrie_toval(node);
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);
314 pctrie_addval(tmp, index, clev, val);
315 pctrie_addval(tmp, *m, clev, m);
317 } else if (pctrie_keybarr(node, index))
319 slot = pctrie_slot(index, node->pn_clev);
320 if (node->pn_child[slot] == NULL) {
322 pctrie_addval(node, index, node->pn_clev, val);
325 parentp = &node->pn_child[slot];
326 node = node->pn_child[slot];
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.
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);
341 pctrie_addval(tmp, index, clev, val);
342 slot = pctrie_slot(newind, clev);
343 tmp->pn_child[slot] = node;
349 * Returns the value stored at the index. If the index is not present,
353 pctrie_lookup(struct pctrie *ptree, uint64_t index)
355 struct pctrie_node *node;
359 node = pctrie_getroot(ptree);
360 while (node != NULL) {
361 if (pctrie_isleaf(node)) {
362 m = pctrie_toval(node);
367 } else if (pctrie_keybarr(node, index))
369 slot = pctrie_slot(index, node->pn_clev);
370 node = node->pn_child[slot];
376 * Look up the nearest entry at a position bigger than or equal to index.
379 pctrie_lookup_ge(struct pctrie *ptree, uint64_t index)
381 struct pctrie_node *stack[PCTRIE_LIMIT];
384 struct pctrie_node *child, *node;
391 node = pctrie_getroot(ptree);
394 else if (pctrie_isleaf(node)) {
395 m = pctrie_toval(node);
404 * If the keys differ before the current bisection node,
405 * then the search key might rollback to the earliest
406 * available bisection node or to the smallest key
407 * in the current node (if the owner is bigger than the
410 if (pctrie_keybarr(node, index)) {
411 if (index > node->pn_owner) {
413 KASSERT(++loops < 1000,
414 ("pctrie_lookup_ge: too many loops"));
417 * Pop nodes from the stack until either the
418 * stack is empty or a node that could have a
419 * matching descendant is found.
425 } while (pctrie_slot(index,
426 node->pn_clev) == (PCTRIE_COUNT - 1));
429 * The following computation cannot overflow
430 * because index's slot at the current level
431 * is less than PCTRIE_COUNT - 1.
433 index = pctrie_trimkey(index,
435 index += PCTRIE_UNITLEVEL(node->pn_clev);
437 index = node->pn_owner;
438 KASSERT(!pctrie_keybarr(node, index),
439 ("pctrie_lookup_ge: keybarr failed"));
441 slot = pctrie_slot(index, node->pn_clev);
442 child = node->pn_child[slot];
443 if (pctrie_isleaf(child)) {
444 m = pctrie_toval(child);
447 } else if (child != NULL)
451 * Look for an available edge or val within the current
454 if (slot < (PCTRIE_COUNT - 1)) {
455 inc = PCTRIE_UNITLEVEL(node->pn_clev);
456 index = pctrie_trimkey(index, node->pn_clev);
460 child = node->pn_child[slot];
461 if (pctrie_isleaf(child)) {
462 m = pctrie_toval(child);
465 } else if (child != NULL)
467 } while (slot < (PCTRIE_COUNT - 1));
469 KASSERT(child == NULL || pctrie_isleaf(child),
470 ("pctrie_lookup_ge: child is radix node"));
473 * If a value or edge bigger than the search slot is not found
474 * in the current node, ascend to the next higher-level node.
478 KASSERT(node->pn_clev > 0,
479 ("pctrie_lookup_ge: pushing leaf's parent"));
480 KASSERT(tos < PCTRIE_LIMIT,
481 ("pctrie_lookup_ge: stack overflow"));
488 * Look up the nearest entry at a position less than or equal to index.
491 pctrie_lookup_le(struct pctrie *ptree, uint64_t index)
493 struct pctrie_node *stack[PCTRIE_LIMIT];
496 struct pctrie_node *child, *node;
503 node = pctrie_getroot(ptree);
506 else if (pctrie_isleaf(node)) {
507 m = pctrie_toval(node);
516 * If the keys differ before the current bisection node,
517 * then the search key might rollback to the earliest
518 * available bisection node or to the largest key
519 * in the current node (if the owner is smaller than the
522 if (pctrie_keybarr(node, index)) {
523 if (index > node->pn_owner) {
524 index = node->pn_owner + PCTRIE_COUNT *
525 PCTRIE_UNITLEVEL(node->pn_clev);
528 KASSERT(++loops < 1000,
529 ("pctrie_lookup_le: too many loops"));
532 * Pop nodes from the stack until either the
533 * stack is empty or a node that could have a
534 * matching descendant is found.
540 } while (pctrie_slot(index,
541 node->pn_clev) == 0);
544 * The following computation cannot overflow
545 * because index's slot at the current level
548 index = pctrie_trimkey(index,
552 KASSERT(!pctrie_keybarr(node, index),
553 ("pctrie_lookup_le: keybarr failed"));
555 slot = pctrie_slot(index, node->pn_clev);
556 child = node->pn_child[slot];
557 if (pctrie_isleaf(child)) {
558 m = pctrie_toval(child);
561 } else if (child != NULL)
565 * Look for an available edge or value within the current
569 inc = PCTRIE_UNITLEVEL(node->pn_clev);
574 child = node->pn_child[slot];
575 if (pctrie_isleaf(child)) {
576 m = pctrie_toval(child);
579 } else if (child != NULL)
583 KASSERT(child == NULL || pctrie_isleaf(child),
584 ("pctrie_lookup_le: child is radix node"));
587 * If a value or edge smaller than the search slot is not found
588 * in the current node, ascend to the next higher-level node.
592 KASSERT(node->pn_clev > 0,
593 ("pctrie_lookup_le: pushing leaf's parent"));
594 KASSERT(tos < PCTRIE_LIMIT,
595 ("pctrie_lookup_le: stack overflow"));
602 * Remove the specified index from the tree.
603 * Panics if the key is not present.
606 pctrie_remove(struct pctrie *ptree, uint64_t index, pctrie_free_t freefn)
608 struct pctrie_node *node, *parent;
612 node = pctrie_getroot(ptree);
613 if (pctrie_isleaf(node)) {
614 m = pctrie_toval(node);
616 panic("%s: invalid key found", __func__);
617 pctrie_setroot(ptree, NULL);
623 panic("pctrie_remove: impossible to locate the key");
624 slot = pctrie_slot(index, node->pn_clev);
625 if (pctrie_isleaf(node->pn_child[slot])) {
626 m = pctrie_toval(node->pn_child[slot]);
628 panic("%s: invalid key found", __func__);
629 node->pn_child[slot] = NULL;
631 if (node->pn_count > 1)
633 for (i = 0; i < PCTRIE_COUNT; i++)
634 if (node->pn_child[i] != NULL)
636 KASSERT(i != PCTRIE_COUNT,
637 ("%s: invalid node configuration", __func__));
639 pctrie_setroot(ptree, node->pn_child[i]);
641 slot = pctrie_slot(index, parent->pn_clev);
642 KASSERT(parent->pn_child[slot] == node,
643 ("%s: invalid child value", __func__));
644 parent->pn_child[slot] = node->pn_child[i];
647 node->pn_child[i] = NULL;
648 pctrie_node_put(ptree, node, freefn);
652 node = node->pn_child[slot];
657 * Remove and free all the nodes from the tree.
658 * This function is recursive but there is a tight control on it as the
659 * maximum depth of the tree is fixed.
662 pctrie_reclaim_allnodes(struct pctrie *ptree, pctrie_free_t freefn)
664 struct pctrie_node *root;
666 root = pctrie_getroot(ptree);
669 pctrie_setroot(ptree, NULL);
670 if (!pctrie_isleaf(root))
671 pctrie_reclaim_allnodes_int(ptree, root, freefn);
676 * Show details about the given node.
678 DB_SHOW_COMMAND(pctrienode, db_show_pctrienode)
680 struct pctrie_node *node;
685 node = (struct pctrie_node *)addr;
686 db_printf("node %p, owner %jx, children count %u, level %u:\n",
687 (void *)node, (uintmax_t)node->pn_owner, node->pn_count,
689 for (i = 0; i < PCTRIE_COUNT; i++)
690 if (node->pn_child[i] != NULL)
691 db_printf("slot: %d, val: %p, value: %p, clev: %d\n",
692 i, (void *)node->pn_child[i],
693 pctrie_isleaf(node->pn_child[i]) ?
694 pctrie_toval(node->pn_child[i]) : NULL,