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.
169 static __inline boolean_t
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.
221 static __inline boolean_t
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;
390 node = pctrie_getroot(ptree);
393 else if (pctrie_isleaf(node)) {
394 m = pctrie_toval(node);
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
409 if (pctrie_keybarr(node, index)) {
410 if (index > node->pn_owner) {
412 KASSERT(++loops < 1000,
413 ("pctrie_lookup_ge: too many loops"));
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.
424 } while (pctrie_slot(index,
425 node->pn_clev) == (PCTRIE_COUNT - 1));
428 * The following computation cannot overflow
429 * because index's slot at the current level
430 * is less than PCTRIE_COUNT - 1.
432 index = pctrie_trimkey(index,
434 index += PCTRIE_UNITLEVEL(node->pn_clev);
436 index = node->pn_owner;
437 KASSERT(!pctrie_keybarr(node, index),
438 ("pctrie_lookup_ge: keybarr failed"));
440 slot = pctrie_slot(index, node->pn_clev);
441 child = node->pn_child[slot];
442 if (pctrie_isleaf(child)) {
443 m = pctrie_toval(child);
446 } else if (child != NULL)
450 * Look for an available edge or val within the current
453 if (slot < (PCTRIE_COUNT - 1)) {
454 inc = PCTRIE_UNITLEVEL(node->pn_clev);
455 index = pctrie_trimkey(index, node->pn_clev);
459 child = node->pn_child[slot];
460 if (pctrie_isleaf(child)) {
461 m = pctrie_toval(child);
464 } else if (child != NULL)
466 } while (slot < (PCTRIE_COUNT - 1));
468 KASSERT(child == NULL || pctrie_isleaf(child),
469 ("pctrie_lookup_ge: child is radix node"));
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.
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"));
487 * Look up the nearest entry at a position less than or equal to index.
490 pctrie_lookup_le(struct pctrie *ptree, uint64_t index)
492 struct pctrie_node *stack[PCTRIE_LIMIT];
495 struct pctrie_node *child, *node;
501 node = pctrie_getroot(ptree);
504 else if (pctrie_isleaf(node)) {
505 m = pctrie_toval(node);
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
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);
526 KASSERT(++loops < 1000,
527 ("pctrie_lookup_le: too many loops"));
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.
538 } while (pctrie_slot(index,
539 node->pn_clev) == 0);
542 * The following computation cannot overflow
543 * because index's slot at the current level
546 index = pctrie_trimkey(index,
550 KASSERT(!pctrie_keybarr(node, index),
551 ("pctrie_lookup_le: keybarr failed"));
553 slot = pctrie_slot(index, node->pn_clev);
554 child = node->pn_child[slot];
555 if (pctrie_isleaf(child)) {
556 m = pctrie_toval(child);
559 } else if (child != NULL)
563 * Look for an available edge or value within the current
567 inc = PCTRIE_UNITLEVEL(node->pn_clev);
572 child = node->pn_child[slot];
573 if (pctrie_isleaf(child)) {
574 m = pctrie_toval(child);
577 } else if (child != NULL)
581 KASSERT(child == NULL || pctrie_isleaf(child),
582 ("pctrie_lookup_le: child is radix node"));
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.
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"));
600 * Remove the specified index from the tree.
601 * Panics if the key is not present.
604 pctrie_remove(struct pctrie *ptree, uint64_t index, pctrie_free_t freefn)
606 struct pctrie_node *node, *parent;
610 node = pctrie_getroot(ptree);
611 if (pctrie_isleaf(node)) {
612 m = pctrie_toval(node);
614 panic("%s: invalid key found", __func__);
615 pctrie_setroot(ptree, 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]);
626 panic("%s: invalid key found", __func__);
627 node->pn_child[slot] = NULL;
629 if (node->pn_count > 1)
631 for (i = 0; i < PCTRIE_COUNT; i++)
632 if (node->pn_child[i] != NULL)
634 KASSERT(i != PCTRIE_COUNT,
635 ("%s: invalid node configuration", __func__));
637 pctrie_setroot(ptree, node->pn_child[i]);
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];
645 node->pn_child[i] = NULL;
646 pctrie_node_put(ptree, node, freefn);
650 node = node->pn_child[slot];
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.
660 pctrie_reclaim_allnodes(struct pctrie *ptree, pctrie_free_t freefn)
662 struct pctrie_node *root;
664 root = pctrie_getroot(ptree);
667 pctrie_setroot(ptree, NULL);
668 if (!pctrie_isleaf(root))
669 pctrie_reclaim_allnodes_int(ptree, root, freefn);
674 * Show details about the given node.
676 DB_SHOW_COMMAND(pctrienode, db_show_pctrienode)
678 struct pctrie_node *node;
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,
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,