2 * Copyright (c) 2013 EMC Corp.
3 * Copyright (c) 2011 Jeffrey Roberson <jeff@freebsd.org>
4 * Copyright (c) 2008 Mayur Shardul <mayur.shardul@gmail.com>
7 * Redistribution and use in source and binary forms, with or without
8 * modification, are permitted provided that the following conditions
10 * 1. Redistributions of source code must retain the above copyright
11 * notice, this list of conditions and the following disclaimer.
12 * 2. Redistributions in binary form must reproduce the above copyright
13 * notice, this list of conditions and the following disclaimer in the
14 * documentation and/or other materials provided with the distribution.
16 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
17 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
18 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
19 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
20 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
21 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
22 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
23 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
24 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
25 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
31 * Path-compressed radix trie implementation.
33 * The implementation takes into account the following rationale:
34 * - Size of the nodes should be as small as possible but still big enough
35 * to avoid a large maximum depth for the trie. This is a balance
36 * between the necessity to not wire too much physical memory for the nodes
37 * and the necessity to avoid too much cache pollution during the trie
39 * - There is not a huge bias toward the number of lookup operations over
40 * the number of insert and remove operations. This basically implies
41 * that optimizations supposedly helping one operation but hurting the
42 * other might be carefully evaluated.
43 * - On average not many nodes are expected to be fully populated, hence
44 * level compression may just complicate things.
47 #include <sys/cdefs.h>
48 __FBSDID("$FreeBSD$");
52 #include <sys/param.h>
53 #include <sys/systm.h>
54 #include <sys/kernel.h>
55 #include <sys/pctrie.h>
62 * These widths should allow the pointers to a node's children to fit within
63 * a single cache line. The extra levels from a narrow width should not be
64 * a problem thanks to path compression.
67 #define PCTRIE_WIDTH 4
69 #define PCTRIE_WIDTH 3
72 #define PCTRIE_COUNT (1 << PCTRIE_WIDTH)
73 #define PCTRIE_MASK (PCTRIE_COUNT - 1)
74 #define PCTRIE_LIMIT (howmany((sizeof(uint64_t) * NBBY), PCTRIE_WIDTH) - 1)
76 /* Flag bits stored in node pointers. */
77 #define PCTRIE_ISLEAF 0x1
78 #define PCTRIE_FLAGS 0x1
79 #define PCTRIE_PAD PCTRIE_FLAGS
81 /* Returns one unit associated with specified level. */
82 #define PCTRIE_UNITLEVEL(lev) \
83 ((uint64_t)1 << ((lev) * PCTRIE_WIDTH))
86 uint64_t pn_owner; /* Owner of record. */
87 uint16_t pn_count; /* Valid children. */
88 uint16_t pn_clev; /* Current level. */
89 void *pn_child[PCTRIE_COUNT]; /* Child nodes. */
93 * Allocate a node. Pre-allocation should ensure that the request
94 * will always be satisfied.
96 static __inline struct pctrie_node *
97 pctrie_node_get(struct pctrie *ptree, pctrie_alloc_t allocfn, uint64_t owner,
98 uint16_t count, uint16_t clevel)
100 struct pctrie_node *node;
102 node = allocfn(ptree);
105 node->pn_owner = owner;
106 node->pn_count = count;
107 node->pn_clev = clevel;
116 pctrie_node_put(struct pctrie *ptree, struct pctrie_node *node,
117 pctrie_free_t freefn)
122 KASSERT(node->pn_count == 0,
123 ("pctrie_node_put: node %p has %d children", node,
125 for (slot = 0; slot < PCTRIE_COUNT; slot++)
126 KASSERT(node->pn_child[slot] == NULL,
127 ("pctrie_node_put: node %p has a child", node));
133 * Return the position in the array for a given level.
136 pctrie_slot(uint64_t index, uint16_t level)
139 return ((index >> (level * PCTRIE_WIDTH)) & PCTRIE_MASK);
142 /* Trims the key after the specified level. */
143 static __inline uint64_t
144 pctrie_trimkey(uint64_t index, uint16_t level)
150 ret >>= level * PCTRIE_WIDTH;
151 ret <<= level * PCTRIE_WIDTH;
157 * Get the root node for a tree.
159 static __inline struct pctrie_node *
160 pctrie_getroot(struct pctrie *ptree)
163 return ((struct pctrie_node *)ptree->pt_root);
167 * Set the root node for a tree.
170 pctrie_setroot(struct pctrie *ptree, struct pctrie_node *node)
173 ptree->pt_root = (uintptr_t)node;
177 * Returns TRUE if the specified node is a leaf and FALSE otherwise.
179 static __inline boolean_t
180 pctrie_isleaf(struct pctrie_node *node)
183 return (((uintptr_t)node & PCTRIE_ISLEAF) != 0);
187 * Returns the associated val extracted from node.
189 static __inline uint64_t *
190 pctrie_toval(struct pctrie_node *node)
193 return ((uint64_t *)((uintptr_t)node & ~PCTRIE_FLAGS));
197 * Adds the val as a child of the provided node.
200 pctrie_addval(struct pctrie_node *node, uint64_t index, uint16_t clev,
205 slot = pctrie_slot(index, clev);
206 node->pn_child[slot] = (void *)((uintptr_t)val | PCTRIE_ISLEAF);
210 * Returns the slot where two keys differ.
211 * It cannot accept 2 equal keys.
213 static __inline uint16_t
214 pctrie_keydiff(uint64_t index1, uint64_t index2)
218 KASSERT(index1 != index2, ("%s: passing the same key value %jx",
219 __func__, (uintmax_t)index1));
222 for (clev = PCTRIE_LIMIT;; clev--)
223 if (pctrie_slot(index1, clev) != 0)
228 * Returns TRUE if it can be determined that key does not belong to the
229 * specified node. Otherwise, returns FALSE.
231 static __inline boolean_t
232 pctrie_keybarr(struct pctrie_node *node, uint64_t idx)
235 if (node->pn_clev < PCTRIE_LIMIT) {
236 idx = pctrie_trimkey(idx, node->pn_clev + 1);
237 return (idx != node->pn_owner);
243 * Internal helper for pctrie_reclaim_allnodes().
244 * This function is recursive.
247 pctrie_reclaim_allnodes_int(struct pctrie *ptree, struct pctrie_node *node,
248 pctrie_free_t freefn)
252 KASSERT(node->pn_count <= PCTRIE_COUNT,
253 ("pctrie_reclaim_allnodes_int: bad count in node %p", node));
254 for (slot = 0; node->pn_count != 0; slot++) {
255 if (node->pn_child[slot] == NULL)
257 if (!pctrie_isleaf(node->pn_child[slot]))
258 pctrie_reclaim_allnodes_int(ptree,
259 node->pn_child[slot], freefn);
260 node->pn_child[slot] = NULL;
263 pctrie_node_put(ptree, node, freefn);
267 * pctrie node zone initializer.
270 pctrie_zone_init(void *mem, int size __unused, int flags __unused)
272 struct pctrie_node *node;
275 memset(node->pn_child, 0, sizeof(node->pn_child));
280 pctrie_node_size(void)
283 return (sizeof(struct pctrie_node));
287 * Inserts the key-value pair into the trie.
288 * Panics if the key already exists.
291 pctrie_insert(struct pctrie *ptree, uint64_t *val, pctrie_alloc_t allocfn)
293 uint64_t index, newind;
295 struct pctrie_node *node, *tmp;
303 * The owner of record for root is not really important because it
304 * will never be used.
306 node = pctrie_getroot(ptree);
308 ptree->pt_root = (uintptr_t)val | PCTRIE_ISLEAF;
311 parentp = (void **)&ptree->pt_root;
313 if (pctrie_isleaf(node)) {
314 m = pctrie_toval(node);
316 panic("%s: key %jx is already present",
317 __func__, (uintmax_t)index);
318 clev = pctrie_keydiff(*m, index);
319 tmp = pctrie_node_get(ptree, allocfn,
320 pctrie_trimkey(index, clev + 1), 2, clev);
324 pctrie_addval(tmp, index, clev, val);
325 pctrie_addval(tmp, *m, clev, m);
327 } else if (pctrie_keybarr(node, index))
329 slot = pctrie_slot(index, node->pn_clev);
330 if (node->pn_child[slot] == NULL) {
332 pctrie_addval(node, index, node->pn_clev, val);
335 parentp = &node->pn_child[slot];
336 node = node->pn_child[slot];
340 * A new node is needed because the right insertion level is reached.
341 * Setup the new intermediate node and add the 2 children: the
342 * new object and the older edge.
344 newind = node->pn_owner;
345 clev = pctrie_keydiff(newind, index);
346 tmp = pctrie_node_get(ptree, allocfn,
347 pctrie_trimkey(index, clev + 1), 2, clev);
351 pctrie_addval(tmp, index, clev, val);
352 slot = pctrie_slot(newind, clev);
353 tmp->pn_child[slot] = node;
359 * Returns the value stored at the index. If the index is not present,
363 pctrie_lookup(struct pctrie *ptree, uint64_t index)
365 struct pctrie_node *node;
369 node = pctrie_getroot(ptree);
370 while (node != NULL) {
371 if (pctrie_isleaf(node)) {
372 m = pctrie_toval(node);
377 } else if (pctrie_keybarr(node, index))
379 slot = pctrie_slot(index, node->pn_clev);
380 node = node->pn_child[slot];
386 * Look up the nearest entry at a position bigger than or equal to index.
389 pctrie_lookup_ge(struct pctrie *ptree, uint64_t index)
391 struct pctrie_node *stack[PCTRIE_LIMIT];
394 struct pctrie_node *child, *node;
400 node = pctrie_getroot(ptree);
403 else if (pctrie_isleaf(node)) {
404 m = pctrie_toval(node);
413 * If the keys differ before the current bisection node,
414 * then the search key might rollback to the earliest
415 * available bisection node or to the smallest key
416 * in the current node (if the owner is bigger than the
419 if (pctrie_keybarr(node, index)) {
420 if (index > node->pn_owner) {
422 KASSERT(++loops < 1000,
423 ("pctrie_lookup_ge: too many loops"));
426 * Pop nodes from the stack until either the
427 * stack is empty or a node that could have a
428 * matching descendant is found.
434 } while (pctrie_slot(index,
435 node->pn_clev) == (PCTRIE_COUNT - 1));
438 * The following computation cannot overflow
439 * because index's slot at the current level
440 * is less than PCTRIE_COUNT - 1.
442 index = pctrie_trimkey(index,
444 index += PCTRIE_UNITLEVEL(node->pn_clev);
446 index = node->pn_owner;
447 KASSERT(!pctrie_keybarr(node, index),
448 ("pctrie_lookup_ge: keybarr failed"));
450 slot = pctrie_slot(index, node->pn_clev);
451 child = node->pn_child[slot];
452 if (pctrie_isleaf(child)) {
453 m = pctrie_toval(child);
456 } else if (child != NULL)
460 * Look for an available edge or val within the current
463 if (slot < (PCTRIE_COUNT - 1)) {
464 inc = PCTRIE_UNITLEVEL(node->pn_clev);
465 index = pctrie_trimkey(index, node->pn_clev);
469 child = node->pn_child[slot];
470 if (pctrie_isleaf(child)) {
471 m = pctrie_toval(child);
474 } else if (child != NULL)
476 } while (slot < (PCTRIE_COUNT - 1));
478 KASSERT(child == NULL || pctrie_isleaf(child),
479 ("pctrie_lookup_ge: child is radix node"));
482 * If a value or edge bigger than the search slot is not found
483 * in the current node, ascend to the next higher-level node.
487 KASSERT(node->pn_clev > 0,
488 ("pctrie_lookup_ge: pushing leaf's parent"));
489 KASSERT(tos < PCTRIE_LIMIT,
490 ("pctrie_lookup_ge: stack overflow"));
497 * Look up the nearest entry at a position less than or equal to index.
500 pctrie_lookup_le(struct pctrie *ptree, uint64_t index)
502 struct pctrie_node *stack[PCTRIE_LIMIT];
505 struct pctrie_node *child, *node;
511 node = pctrie_getroot(ptree);
514 else if (pctrie_isleaf(node)) {
515 m = pctrie_toval(node);
524 * If the keys differ before the current bisection node,
525 * then the search key might rollback to the earliest
526 * available bisection node or to the largest key
527 * in the current node (if the owner is smaller than the
530 if (pctrie_keybarr(node, index)) {
531 if (index > node->pn_owner) {
532 index = node->pn_owner + PCTRIE_COUNT *
533 PCTRIE_UNITLEVEL(node->pn_clev);
536 KASSERT(++loops < 1000,
537 ("pctrie_lookup_le: too many loops"));
540 * Pop nodes from the stack until either the
541 * stack is empty or a node that could have a
542 * matching descendant is found.
548 } while (pctrie_slot(index,
549 node->pn_clev) == 0);
552 * The following computation cannot overflow
553 * because index's slot at the current level
556 index = pctrie_trimkey(index,
560 KASSERT(!pctrie_keybarr(node, index),
561 ("pctrie_lookup_le: keybarr failed"));
563 slot = pctrie_slot(index, node->pn_clev);
564 child = node->pn_child[slot];
565 if (pctrie_isleaf(child)) {
566 m = pctrie_toval(child);
569 } else if (child != NULL)
573 * Look for an available edge or value within the current
577 inc = PCTRIE_UNITLEVEL(node->pn_clev);
582 child = node->pn_child[slot];
583 if (pctrie_isleaf(child)) {
584 m = pctrie_toval(child);
587 } else if (child != NULL)
591 KASSERT(child == NULL || pctrie_isleaf(child),
592 ("pctrie_lookup_le: child is radix node"));
595 * If a value or edge smaller than the search slot is not found
596 * in the current node, ascend to the next higher-level node.
600 KASSERT(node->pn_clev > 0,
601 ("pctrie_lookup_le: pushing leaf's parent"));
602 KASSERT(tos < PCTRIE_LIMIT,
603 ("pctrie_lookup_le: stack overflow"));
610 * Remove the specified index from the tree.
611 * Panics if the key is not present.
614 pctrie_remove(struct pctrie *ptree, uint64_t index, pctrie_free_t freefn)
616 struct pctrie_node *node, *parent;
620 node = pctrie_getroot(ptree);
621 if (pctrie_isleaf(node)) {
622 m = pctrie_toval(node);
624 panic("%s: invalid key found", __func__);
625 pctrie_setroot(ptree, NULL);
631 panic("pctrie_remove: impossible to locate the key");
632 slot = pctrie_slot(index, node->pn_clev);
633 if (pctrie_isleaf(node->pn_child[slot])) {
634 m = pctrie_toval(node->pn_child[slot]);
636 panic("%s: invalid key found", __func__);
637 node->pn_child[slot] = NULL;
639 if (node->pn_count > 1)
641 for (i = 0; i < PCTRIE_COUNT; i++)
642 if (node->pn_child[i] != NULL)
644 KASSERT(i != PCTRIE_COUNT,
645 ("%s: invalid node configuration", __func__));
647 pctrie_setroot(ptree, node->pn_child[i]);
649 slot = pctrie_slot(index, parent->pn_clev);
650 KASSERT(parent->pn_child[slot] == node,
651 ("%s: invalid child value", __func__));
652 parent->pn_child[slot] = node->pn_child[i];
655 node->pn_child[i] = NULL;
656 pctrie_node_put(ptree, node, freefn);
660 node = node->pn_child[slot];
665 * Remove and free all the nodes from the tree.
666 * This function is recursive but there is a tight control on it as the
667 * maximum depth of the tree is fixed.
670 pctrie_reclaim_allnodes(struct pctrie *ptree, pctrie_free_t freefn)
672 struct pctrie_node *root;
674 root = pctrie_getroot(ptree);
677 pctrie_setroot(ptree, NULL);
678 if (!pctrie_isleaf(root))
679 pctrie_reclaim_allnodes_int(ptree, root, freefn);
684 * Show details about the given node.
686 DB_SHOW_COMMAND(pctrienode, db_show_pctrienode)
688 struct pctrie_node *node;
693 node = (struct pctrie_node *)addr;
694 db_printf("node %p, owner %jx, children count %u, level %u:\n",
695 (void *)node, (uintmax_t)node->pn_owner, node->pn_count,
697 for (i = 0; i < PCTRIE_COUNT; i++)
698 if (node->pn_child[i] != NULL)
699 db_printf("slot: %d, val: %p, value: %p, clev: %d\n",
700 i, (void *)node->pn_child[i],
701 pctrie_isleaf(node->pn_child[i]) ?
702 pctrie_toval(node->pn_child[i]) : NULL,