xref: /freebsd/sys/kern/subr_pctrie.c (revision 05963ea4d130c39b332ae8b69414e8a894ca81e0)
18a36da99SPedro F. Giffuni /*-
24d846d26SWarner Losh  * SPDX-License-Identifier: BSD-2-Clause
38a36da99SPedro F. Giffuni  *
4f2cc1285SJeff Roberson  * Copyright (c) 2013 EMC Corp.
5f2cc1285SJeff Roberson  * Copyright (c) 2011 Jeffrey Roberson <jeff@freebsd.org>
6f2cc1285SJeff Roberson  * Copyright (c) 2008 Mayur Shardul <mayur.shardul@gmail.com>
7f2cc1285SJeff Roberson  * All rights reserved.
8f2cc1285SJeff Roberson  *
9f2cc1285SJeff Roberson  * Redistribution and use in source and binary forms, with or without
10f2cc1285SJeff Roberson  * modification, are permitted provided that the following conditions
11f2cc1285SJeff Roberson  * are met:
12f2cc1285SJeff Roberson  * 1. Redistributions of source code must retain the above copyright
13f2cc1285SJeff Roberson  *    notice, this list of conditions and the following disclaimer.
14f2cc1285SJeff Roberson  * 2. Redistributions in binary form must reproduce the above copyright
15f2cc1285SJeff Roberson  *    notice, this list of conditions and the following disclaimer in the
16f2cc1285SJeff Roberson  *    documentation and/or other materials provided with the distribution.
17f2cc1285SJeff Roberson  *
18f2cc1285SJeff Roberson  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
19f2cc1285SJeff Roberson  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
20f2cc1285SJeff Roberson  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
21f2cc1285SJeff Roberson  * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
22f2cc1285SJeff Roberson  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
23f2cc1285SJeff Roberson  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
24f2cc1285SJeff Roberson  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
25f2cc1285SJeff Roberson  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
26f2cc1285SJeff Roberson  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
27f2cc1285SJeff Roberson  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
28f2cc1285SJeff Roberson  * SUCH DAMAGE.
29f2cc1285SJeff Roberson  *
30f2cc1285SJeff Roberson  */
31f2cc1285SJeff Roberson 
32f2cc1285SJeff Roberson /*
33f2cc1285SJeff Roberson  * Path-compressed radix trie implementation.
34f2cc1285SJeff Roberson  *
35f2cc1285SJeff Roberson  * The implementation takes into account the following rationale:
36f2cc1285SJeff Roberson  * - Size of the nodes should be as small as possible but still big enough
37f2cc1285SJeff Roberson  *   to avoid a large maximum depth for the trie.  This is a balance
38f2cc1285SJeff Roberson  *   between the necessity to not wire too much physical memory for the nodes
39f2cc1285SJeff Roberson  *   and the necessity to avoid too much cache pollution during the trie
40f2cc1285SJeff Roberson  *   operations.
41f2cc1285SJeff Roberson  * - There is not a huge bias toward the number of lookup operations over
42f2cc1285SJeff Roberson  *   the number of insert and remove operations.  This basically implies
43f2cc1285SJeff Roberson  *   that optimizations supposedly helping one operation but hurting the
44f2cc1285SJeff Roberson  *   other might be carefully evaluated.
45f2cc1285SJeff Roberson  * - On average not many nodes are expected to be fully populated, hence
46f2cc1285SJeff Roberson  *   level compression may just complicate things.
47f2cc1285SJeff Roberson  */
48f2cc1285SJeff Roberson 
49f2cc1285SJeff Roberson #include <sys/cdefs.h>
50f2cc1285SJeff Roberson __FBSDID("$FreeBSD$");
51f2cc1285SJeff Roberson 
52f2cc1285SJeff Roberson #include "opt_ddb.h"
53f2cc1285SJeff Roberson 
54f2cc1285SJeff Roberson #include <sys/param.h>
55f2cc1285SJeff Roberson #include <sys/systm.h>
56f2cc1285SJeff Roberson #include <sys/kernel.h>
57*05963ea4SDoug Moore #include <sys/libkern.h>
58f2cc1285SJeff Roberson #include <sys/pctrie.h>
593c30b235SConrad Meyer #include <sys/proc.h>	/* smr.h depends on struct thread. */
603c30b235SConrad Meyer #include <sys/smr.h>
613c30b235SConrad Meyer #include <sys/smr_types.h>
62f2cc1285SJeff Roberson 
63f2cc1285SJeff Roberson #ifdef DDB
64f2cc1285SJeff Roberson #include <ddb/ddb.h>
65f2cc1285SJeff Roberson #endif
66f2cc1285SJeff Roberson 
67f2cc1285SJeff Roberson #define	PCTRIE_MASK	(PCTRIE_COUNT - 1)
6855e0987aSPedro F. Giffuni #define	PCTRIE_LIMIT	(howmany(sizeof(uint64_t) * NBBY, PCTRIE_WIDTH) - 1)
69f2cc1285SJeff Roberson 
70f2cc1285SJeff Roberson /* Flag bits stored in node pointers. */
71f2cc1285SJeff Roberson #define	PCTRIE_ISLEAF	0x1
72f2cc1285SJeff Roberson #define	PCTRIE_FLAGS	0x1
73f2cc1285SJeff Roberson #define	PCTRIE_PAD	PCTRIE_FLAGS
74f2cc1285SJeff Roberson 
75f2cc1285SJeff Roberson /* Returns one unit associated with specified level. */
76f2cc1285SJeff Roberson #define	PCTRIE_UNITLEVEL(lev)						\
77f2cc1285SJeff Roberson 	((uint64_t)1 << ((lev) * PCTRIE_WIDTH))
78f2cc1285SJeff Roberson 
793c30b235SConrad Meyer struct pctrie_node;
803c30b235SConrad Meyer typedef SMR_POINTER(struct pctrie_node *) smr_pctnode_t;
813c30b235SConrad Meyer 
82f2cc1285SJeff Roberson struct pctrie_node {
83f2cc1285SJeff Roberson 	uint64_t	pn_owner;			/* Owner of record. */
84f2cc1285SJeff Roberson 	uint16_t	pn_count;			/* Valid children. */
853c30b235SConrad Meyer 	uint8_t		pn_clev;			/* Current level. */
863c30b235SConrad Meyer 	int8_t		pn_last;			/* Zero last ptr. */
873c30b235SConrad Meyer 	smr_pctnode_t	pn_child[PCTRIE_COUNT];		/* Child nodes. */
88f2cc1285SJeff Roberson };
89f2cc1285SJeff Roberson 
903c30b235SConrad Meyer enum pctrie_access { PCTRIE_SMR, PCTRIE_LOCKED, PCTRIE_UNSERIALIZED };
913c30b235SConrad Meyer 
923c30b235SConrad Meyer static __inline void pctrie_node_store(smr_pctnode_t *p, void *val,
933c30b235SConrad Meyer     enum pctrie_access access);
943c30b235SConrad Meyer 
95f2cc1285SJeff Roberson /*
96f2cc1285SJeff Roberson  * Allocate a node.  Pre-allocation should ensure that the request
97f2cc1285SJeff Roberson  * will always be satisfied.
98f2cc1285SJeff Roberson  */
993c30b235SConrad Meyer static struct pctrie_node *
100f2cc1285SJeff Roberson pctrie_node_get(struct pctrie *ptree, pctrie_alloc_t allocfn, uint64_t owner,
101f2cc1285SJeff Roberson     uint16_t count, uint16_t clevel)
102f2cc1285SJeff Roberson {
103f2cc1285SJeff Roberson 	struct pctrie_node *node;
104f2cc1285SJeff Roberson 
105f2cc1285SJeff Roberson 	node = allocfn(ptree);
106f2cc1285SJeff Roberson 	if (node == NULL)
107f2cc1285SJeff Roberson 		return (NULL);
1083c30b235SConrad Meyer 
1093c30b235SConrad Meyer 	/*
1103c30b235SConrad Meyer 	 * We want to clear the last child pointer after the final section
1113c30b235SConrad Meyer 	 * has exited so lookup can not return false negatives.  It is done
1123c30b235SConrad Meyer 	 * here because it will be cache-cold in the dtor callback.
1133c30b235SConrad Meyer 	 */
1143c30b235SConrad Meyer 	if (node->pn_last != 0) {
1153c30b235SConrad Meyer 		pctrie_node_store(&node->pn_child[node->pn_last - 1], NULL,
1163c30b235SConrad Meyer 		    PCTRIE_UNSERIALIZED);
1173c30b235SConrad Meyer 		node->pn_last = 0;
1183c30b235SConrad Meyer 	}
119f2cc1285SJeff Roberson 	node->pn_owner = owner;
120f2cc1285SJeff Roberson 	node->pn_count = count;
121f2cc1285SJeff Roberson 	node->pn_clev = clevel;
122f2cc1285SJeff Roberson 	return (node);
123f2cc1285SJeff Roberson }
124f2cc1285SJeff Roberson 
125f2cc1285SJeff Roberson /*
126f2cc1285SJeff Roberson  * Free radix node.
127f2cc1285SJeff Roberson  */
128f2cc1285SJeff Roberson static __inline void
129f2cc1285SJeff Roberson pctrie_node_put(struct pctrie *ptree, struct pctrie_node *node,
1303c30b235SConrad Meyer     pctrie_free_t freefn, int8_t last)
131f2cc1285SJeff Roberson {
132f2cc1285SJeff Roberson #ifdef INVARIANTS
133f2cc1285SJeff Roberson 	int slot;
134f2cc1285SJeff Roberson 
135f2cc1285SJeff Roberson 	KASSERT(node->pn_count == 0,
136f2cc1285SJeff Roberson 	    ("pctrie_node_put: node %p has %d children", node,
137f2cc1285SJeff Roberson 	    node->pn_count));
1383c30b235SConrad Meyer 	for (slot = 0; slot < PCTRIE_COUNT; slot++) {
1393c30b235SConrad Meyer 		if (slot == last)
1403c30b235SConrad Meyer 			continue;
1413c30b235SConrad Meyer 		KASSERT(smr_unserialized_load(&node->pn_child[slot], true) ==
1423c30b235SConrad Meyer 		    NULL, ("pctrie_node_put: node %p has a child", node));
1433c30b235SConrad Meyer 	}
144f2cc1285SJeff Roberson #endif
1453c30b235SConrad Meyer 	node->pn_last = last + 1;
146f2cc1285SJeff Roberson 	freefn(ptree, node);
147f2cc1285SJeff Roberson }
148f2cc1285SJeff Roberson 
149f2cc1285SJeff Roberson /*
150f2cc1285SJeff Roberson  * Return the position in the array for a given level.
151f2cc1285SJeff Roberson  */
152f2cc1285SJeff Roberson static __inline int
153f2cc1285SJeff Roberson pctrie_slot(uint64_t index, uint16_t level)
154f2cc1285SJeff Roberson {
155f2cc1285SJeff Roberson 
156f2cc1285SJeff Roberson 	return ((index >> (level * PCTRIE_WIDTH)) & PCTRIE_MASK);
157f2cc1285SJeff Roberson }
158f2cc1285SJeff Roberson 
159f2cc1285SJeff Roberson /* Trims the key after the specified level. */
160f2cc1285SJeff Roberson static __inline uint64_t
161f2cc1285SJeff Roberson pctrie_trimkey(uint64_t index, uint16_t level)
162f2cc1285SJeff Roberson {
163f2cc1285SJeff Roberson 	uint64_t ret;
164f2cc1285SJeff Roberson 
165f2cc1285SJeff Roberson 	ret = index;
166f2cc1285SJeff Roberson 	if (level > 0) {
167f2cc1285SJeff Roberson 		ret >>= level * PCTRIE_WIDTH;
168f2cc1285SJeff Roberson 		ret <<= level * PCTRIE_WIDTH;
169f2cc1285SJeff Roberson 	}
170f2cc1285SJeff Roberson 	return (ret);
171f2cc1285SJeff Roberson }
172f2cc1285SJeff Roberson 
173f2cc1285SJeff Roberson /*
1743c30b235SConrad Meyer  * Fetch a node pointer from a slot.
1753c30b235SConrad Meyer  */
1763c30b235SConrad Meyer static __inline struct pctrie_node *
1773c30b235SConrad Meyer pctrie_node_load(smr_pctnode_t *p, smr_t smr, enum pctrie_access access)
1783c30b235SConrad Meyer {
1793c30b235SConrad Meyer 	switch (access) {
1803c30b235SConrad Meyer 	case PCTRIE_UNSERIALIZED:
1813c30b235SConrad Meyer 		return (smr_unserialized_load(p, true));
1823c30b235SConrad Meyer 	case PCTRIE_LOCKED:
1833c30b235SConrad Meyer 		return (smr_serialized_load(p, true));
1843c30b235SConrad Meyer 	case PCTRIE_SMR:
1853c30b235SConrad Meyer 		return (smr_entered_load(p, smr));
1863c30b235SConrad Meyer 	}
1873c30b235SConrad Meyer 	__assert_unreachable();
1883c30b235SConrad Meyer }
1893c30b235SConrad Meyer 
1903c30b235SConrad Meyer static __inline void
1913c30b235SConrad Meyer pctrie_node_store(smr_pctnode_t *p, void *v, enum pctrie_access access)
1923c30b235SConrad Meyer {
1933c30b235SConrad Meyer 	switch (access) {
1943c30b235SConrad Meyer 	case PCTRIE_UNSERIALIZED:
1953c30b235SConrad Meyer 		smr_unserialized_store(p, v, true);
1963c30b235SConrad Meyer 		break;
1973c30b235SConrad Meyer 	case PCTRIE_LOCKED:
1983c30b235SConrad Meyer 		smr_serialized_store(p, v, true);
1993c30b235SConrad Meyer 		break;
2003c30b235SConrad Meyer 	case PCTRIE_SMR:
2013c30b235SConrad Meyer 		panic("%s: Not supported in SMR section.", __func__);
2023c30b235SConrad Meyer 		break;
2033c30b235SConrad Meyer 	default:
2043c30b235SConrad Meyer 		__assert_unreachable();
2053c30b235SConrad Meyer 		break;
2063c30b235SConrad Meyer 	}
2073c30b235SConrad Meyer }
2083c30b235SConrad Meyer 
2093c30b235SConrad Meyer /*
210f2cc1285SJeff Roberson  * Get the root node for a tree.
211f2cc1285SJeff Roberson  */
212f2cc1285SJeff Roberson static __inline struct pctrie_node *
2133c30b235SConrad Meyer pctrie_root_load(struct pctrie *ptree, smr_t smr, enum pctrie_access access)
214f2cc1285SJeff Roberson {
2153c30b235SConrad Meyer 	return (pctrie_node_load((smr_pctnode_t *)&ptree->pt_root, smr, access));
216f2cc1285SJeff Roberson }
217f2cc1285SJeff Roberson 
218f2cc1285SJeff Roberson /*
219f2cc1285SJeff Roberson  * Set the root node for a tree.
220f2cc1285SJeff Roberson  */
221f2cc1285SJeff Roberson static __inline void
2223c30b235SConrad Meyer pctrie_root_store(struct pctrie *ptree, struct pctrie_node *node,
2233c30b235SConrad Meyer     enum pctrie_access access)
224f2cc1285SJeff Roberson {
2253c30b235SConrad Meyer 	pctrie_node_store((smr_pctnode_t *)&ptree->pt_root, node, access);
226f2cc1285SJeff Roberson }
227f2cc1285SJeff Roberson 
228f2cc1285SJeff Roberson /*
229f2cc1285SJeff Roberson  * Returns TRUE if the specified node is a leaf and FALSE otherwise.
230f2cc1285SJeff Roberson  */
23104f9afaeSConrad Meyer static __inline bool
232f2cc1285SJeff Roberson pctrie_isleaf(struct pctrie_node *node)
233f2cc1285SJeff Roberson {
234f2cc1285SJeff Roberson 
235f2cc1285SJeff Roberson 	return (((uintptr_t)node & PCTRIE_ISLEAF) != 0);
236f2cc1285SJeff Roberson }
237f2cc1285SJeff Roberson 
238f2cc1285SJeff Roberson /*
239f2cc1285SJeff Roberson  * Returns the associated val extracted from node.
240f2cc1285SJeff Roberson  */
241f2cc1285SJeff Roberson static __inline uint64_t *
242f2cc1285SJeff Roberson pctrie_toval(struct pctrie_node *node)
243f2cc1285SJeff Roberson {
244f2cc1285SJeff Roberson 
245f2cc1285SJeff Roberson 	return ((uint64_t *)((uintptr_t)node & ~PCTRIE_FLAGS));
246f2cc1285SJeff Roberson }
247f2cc1285SJeff Roberson 
248f2cc1285SJeff Roberson /*
249f2cc1285SJeff Roberson  * Adds the val as a child of the provided node.
250f2cc1285SJeff Roberson  */
251f2cc1285SJeff Roberson static __inline void
252f2cc1285SJeff Roberson pctrie_addval(struct pctrie_node *node, uint64_t index, uint16_t clev,
2533c30b235SConrad Meyer     uint64_t *val, enum pctrie_access access)
254f2cc1285SJeff Roberson {
255f2cc1285SJeff Roberson 	int slot;
256f2cc1285SJeff Roberson 
257f2cc1285SJeff Roberson 	slot = pctrie_slot(index, clev);
2583c30b235SConrad Meyer 	pctrie_node_store(&node->pn_child[slot],
2593c30b235SConrad Meyer 	    (void *)((uintptr_t)val | PCTRIE_ISLEAF), access);
260f2cc1285SJeff Roberson }
261f2cc1285SJeff Roberson 
262f2cc1285SJeff Roberson /*
263*05963ea4SDoug Moore  * Returns the level where two keys differ.
264f2cc1285SJeff Roberson  * It cannot accept 2 equal keys.
265f2cc1285SJeff Roberson  */
266f2cc1285SJeff Roberson static __inline uint16_t
267f2cc1285SJeff Roberson pctrie_keydiff(uint64_t index1, uint64_t index2)
268f2cc1285SJeff Roberson {
269f2cc1285SJeff Roberson 
270f2cc1285SJeff Roberson 	KASSERT(index1 != index2, ("%s: passing the same key value %jx",
271f2cc1285SJeff Roberson 	    __func__, (uintmax_t)index1));
272*05963ea4SDoug Moore 	CTASSERT(sizeof(long long) >= sizeof(uint64_t));
273f2cc1285SJeff Roberson 
274*05963ea4SDoug Moore 	/*
275*05963ea4SDoug Moore 	 * From the highest-order bit where the indexes differ,
276*05963ea4SDoug Moore 	 * compute the highest level in the trie where they differ.
277*05963ea4SDoug Moore 	 */
278*05963ea4SDoug Moore 	return ((flsll(index1 ^ index2) - 1) / PCTRIE_WIDTH);
279f2cc1285SJeff Roberson }
280f2cc1285SJeff Roberson 
281f2cc1285SJeff Roberson /*
282f2cc1285SJeff Roberson  * Returns TRUE if it can be determined that key does not belong to the
283f2cc1285SJeff Roberson  * specified node.  Otherwise, returns FALSE.
284f2cc1285SJeff Roberson  */
28504f9afaeSConrad Meyer static __inline bool
286f2cc1285SJeff Roberson pctrie_keybarr(struct pctrie_node *node, uint64_t idx)
287f2cc1285SJeff Roberson {
288f2cc1285SJeff Roberson 
289f2cc1285SJeff Roberson 	if (node->pn_clev < PCTRIE_LIMIT) {
290f2cc1285SJeff Roberson 		idx = pctrie_trimkey(idx, node->pn_clev + 1);
291f2cc1285SJeff Roberson 		return (idx != node->pn_owner);
292f2cc1285SJeff Roberson 	}
29304f9afaeSConrad Meyer 	return (false);
294f2cc1285SJeff Roberson }
295f2cc1285SJeff Roberson 
296f2cc1285SJeff Roberson /*
297f2cc1285SJeff Roberson  * Internal helper for pctrie_reclaim_allnodes().
298f2cc1285SJeff Roberson  * This function is recursive.
299f2cc1285SJeff Roberson  */
300f2cc1285SJeff Roberson static void
301f2cc1285SJeff Roberson pctrie_reclaim_allnodes_int(struct pctrie *ptree, struct pctrie_node *node,
302f2cc1285SJeff Roberson     pctrie_free_t freefn)
303f2cc1285SJeff Roberson {
3043c30b235SConrad Meyer 	struct pctrie_node *child;
305f2cc1285SJeff Roberson 	int slot;
306f2cc1285SJeff Roberson 
307f2cc1285SJeff Roberson 	KASSERT(node->pn_count <= PCTRIE_COUNT,
308f2cc1285SJeff Roberson 	    ("pctrie_reclaim_allnodes_int: bad count in node %p", node));
309f2cc1285SJeff Roberson 	for (slot = 0; node->pn_count != 0; slot++) {
3103c30b235SConrad Meyer 		child = pctrie_node_load(&node->pn_child[slot], NULL,
3113c30b235SConrad Meyer 		    PCTRIE_UNSERIALIZED);
3123c30b235SConrad Meyer 		if (child == NULL)
313f2cc1285SJeff Roberson 			continue;
3143c30b235SConrad Meyer 		if (!pctrie_isleaf(child))
3153c30b235SConrad Meyer 			pctrie_reclaim_allnodes_int(ptree, child, freefn);
3163c30b235SConrad Meyer 		pctrie_node_store(&node->pn_child[slot], NULL,
3173c30b235SConrad Meyer 		    PCTRIE_UNSERIALIZED);
318f2cc1285SJeff Roberson 		node->pn_count--;
319f2cc1285SJeff Roberson 	}
3203c30b235SConrad Meyer 	pctrie_node_put(ptree, node, freefn, -1);
321f2cc1285SJeff Roberson }
322f2cc1285SJeff Roberson 
323f2cc1285SJeff Roberson /*
324f2cc1285SJeff Roberson  * pctrie node zone initializer.
325f2cc1285SJeff Roberson  */
326f2cc1285SJeff Roberson int
327f2cc1285SJeff Roberson pctrie_zone_init(void *mem, int size __unused, int flags __unused)
328f2cc1285SJeff Roberson {
329f2cc1285SJeff Roberson 	struct pctrie_node *node;
330f2cc1285SJeff Roberson 
331f2cc1285SJeff Roberson 	node = mem;
3323c30b235SConrad Meyer 	node->pn_last = 0;
333f2cc1285SJeff Roberson 	memset(node->pn_child, 0, sizeof(node->pn_child));
334f2cc1285SJeff Roberson 	return (0);
335f2cc1285SJeff Roberson }
336f2cc1285SJeff Roberson 
337f2cc1285SJeff Roberson size_t
338f2cc1285SJeff Roberson pctrie_node_size(void)
339f2cc1285SJeff Roberson {
340f2cc1285SJeff Roberson 
341f2cc1285SJeff Roberson 	return (sizeof(struct pctrie_node));
342f2cc1285SJeff Roberson }
343f2cc1285SJeff Roberson 
344f2cc1285SJeff Roberson /*
345f2cc1285SJeff Roberson  * Inserts the key-value pair into the trie.
346f2cc1285SJeff Roberson  * Panics if the key already exists.
347f2cc1285SJeff Roberson  */
348f2cc1285SJeff Roberson int
349f2cc1285SJeff Roberson pctrie_insert(struct pctrie *ptree, uint64_t *val, pctrie_alloc_t allocfn)
350f2cc1285SJeff Roberson {
351f2cc1285SJeff Roberson 	uint64_t index, newind;
352f2cc1285SJeff Roberson 	struct pctrie_node *node, *tmp;
3533c30b235SConrad Meyer 	smr_pctnode_t *parentp;
354f2cc1285SJeff Roberson 	uint64_t *m;
355f2cc1285SJeff Roberson 	int slot;
356f2cc1285SJeff Roberson 	uint16_t clev;
357f2cc1285SJeff Roberson 
358f2cc1285SJeff Roberson 	index = *val;
359f2cc1285SJeff Roberson 
360f2cc1285SJeff Roberson 	/*
361f2cc1285SJeff Roberson 	 * The owner of record for root is not really important because it
362f2cc1285SJeff Roberson 	 * will never be used.
363f2cc1285SJeff Roberson 	 */
3643c30b235SConrad Meyer 	node = pctrie_root_load(ptree, NULL, PCTRIE_LOCKED);
365f2cc1285SJeff Roberson 	if (node == NULL) {
366f2cc1285SJeff Roberson 		ptree->pt_root = (uintptr_t)val | PCTRIE_ISLEAF;
367f2cc1285SJeff Roberson 		return (0);
368f2cc1285SJeff Roberson 	}
3693c30b235SConrad Meyer 	parentp = (smr_pctnode_t *)&ptree->pt_root;
370f2cc1285SJeff Roberson 	for (;;) {
371f2cc1285SJeff Roberson 		if (pctrie_isleaf(node)) {
372f2cc1285SJeff Roberson 			m = pctrie_toval(node);
373f2cc1285SJeff Roberson 			if (*m == index)
374f2cc1285SJeff Roberson 				panic("%s: key %jx is already present",
375f2cc1285SJeff Roberson 				    __func__, (uintmax_t)index);
376f2cc1285SJeff Roberson 			clev = pctrie_keydiff(*m, index);
377f2cc1285SJeff Roberson 			tmp = pctrie_node_get(ptree, allocfn,
378f2cc1285SJeff Roberson 			    pctrie_trimkey(index, clev + 1), 2, clev);
379f2cc1285SJeff Roberson 			if (tmp == NULL)
380f2cc1285SJeff Roberson 				return (ENOMEM);
3813c30b235SConrad Meyer 			/* These writes are not yet visible due to ordering. */
3823c30b235SConrad Meyer 			pctrie_addval(tmp, index, clev, val,
3833c30b235SConrad Meyer 			    PCTRIE_UNSERIALIZED);
3843c30b235SConrad Meyer 			pctrie_addval(tmp, *m, clev, m, PCTRIE_UNSERIALIZED);
3853c30b235SConrad Meyer 			/* Synchronize to make leaf visible. */
3863c30b235SConrad Meyer 			pctrie_node_store(parentp, tmp, PCTRIE_LOCKED);
387f2cc1285SJeff Roberson 			return (0);
388f2cc1285SJeff Roberson 		} else if (pctrie_keybarr(node, index))
389f2cc1285SJeff Roberson 			break;
390f2cc1285SJeff Roberson 		slot = pctrie_slot(index, node->pn_clev);
3913c30b235SConrad Meyer 		parentp = &node->pn_child[slot];
3923c30b235SConrad Meyer 		tmp = pctrie_node_load(parentp, NULL, PCTRIE_LOCKED);
3933c30b235SConrad Meyer 		if (tmp == NULL) {
394f2cc1285SJeff Roberson 			node->pn_count++;
3953c30b235SConrad Meyer 			pctrie_addval(node, index, node->pn_clev, val,
3963c30b235SConrad Meyer 			    PCTRIE_LOCKED);
397f2cc1285SJeff Roberson 			return (0);
398f2cc1285SJeff Roberson 		}
3993c30b235SConrad Meyer 		node = tmp;
400f2cc1285SJeff Roberson 	}
401f2cc1285SJeff Roberson 
402f2cc1285SJeff Roberson 	/*
403f2cc1285SJeff Roberson 	 * A new node is needed because the right insertion level is reached.
404f2cc1285SJeff Roberson 	 * Setup the new intermediate node and add the 2 children: the
405f2cc1285SJeff Roberson 	 * new object and the older edge.
406f2cc1285SJeff Roberson 	 */
407f2cc1285SJeff Roberson 	newind = node->pn_owner;
408f2cc1285SJeff Roberson 	clev = pctrie_keydiff(newind, index);
409f2cc1285SJeff Roberson 	tmp = pctrie_node_get(ptree, allocfn,
410f2cc1285SJeff Roberson 	    pctrie_trimkey(index, clev + 1), 2, clev);
411f2cc1285SJeff Roberson 	if (tmp == NULL)
412f2cc1285SJeff Roberson 		return (ENOMEM);
413f2cc1285SJeff Roberson 	slot = pctrie_slot(newind, clev);
4143c30b235SConrad Meyer 	/* These writes are not yet visible due to ordering. */
4153c30b235SConrad Meyer 	pctrie_addval(tmp, index, clev, val, PCTRIE_UNSERIALIZED);
4163c30b235SConrad Meyer 	pctrie_node_store(&tmp->pn_child[slot], node, PCTRIE_UNSERIALIZED);
4173c30b235SConrad Meyer 	/* Synchronize to make the above visible. */
4183c30b235SConrad Meyer 	pctrie_node_store(parentp, tmp, PCTRIE_LOCKED);
419f2cc1285SJeff Roberson 
420f2cc1285SJeff Roberson 	return (0);
421f2cc1285SJeff Roberson }
422f2cc1285SJeff Roberson 
423f2cc1285SJeff Roberson /*
424f2cc1285SJeff Roberson  * Returns the value stored at the index.  If the index is not present,
425f2cc1285SJeff Roberson  * NULL is returned.
426f2cc1285SJeff Roberson  */
4273c30b235SConrad Meyer static __always_inline uint64_t *
4283c30b235SConrad Meyer _pctrie_lookup(struct pctrie *ptree, uint64_t index, smr_t smr,
4293c30b235SConrad Meyer     enum pctrie_access access)
430f2cc1285SJeff Roberson {
431f2cc1285SJeff Roberson 	struct pctrie_node *node;
432f2cc1285SJeff Roberson 	uint64_t *m;
433f2cc1285SJeff Roberson 	int slot;
434f2cc1285SJeff Roberson 
4353c30b235SConrad Meyer 	node = pctrie_root_load(ptree, smr, access);
436f2cc1285SJeff Roberson 	while (node != NULL) {
437f2cc1285SJeff Roberson 		if (pctrie_isleaf(node)) {
438f2cc1285SJeff Roberson 			m = pctrie_toval(node);
439f2cc1285SJeff Roberson 			if (*m == index)
440f2cc1285SJeff Roberson 				return (m);
441f2cc1285SJeff Roberson 			break;
4423c30b235SConrad Meyer 		}
4433c30b235SConrad Meyer 		if (pctrie_keybarr(node, index))
444f2cc1285SJeff Roberson 			break;
445f2cc1285SJeff Roberson 		slot = pctrie_slot(index, node->pn_clev);
4463c30b235SConrad Meyer 		node = pctrie_node_load(&node->pn_child[slot], smr, access);
447f2cc1285SJeff Roberson 	}
448f2cc1285SJeff Roberson 	return (NULL);
449f2cc1285SJeff Roberson }
450f2cc1285SJeff Roberson 
451f2cc1285SJeff Roberson /*
4523c30b235SConrad Meyer  * Returns the value stored at the index, assuming access is externally
4533c30b235SConrad Meyer  * synchronized by a lock.
4543c30b235SConrad Meyer  *
4553c30b235SConrad Meyer  * If the index is not present, NULL is returned.
4563c30b235SConrad Meyer  */
4573c30b235SConrad Meyer uint64_t *
4583c30b235SConrad Meyer pctrie_lookup(struct pctrie *ptree, uint64_t index)
4593c30b235SConrad Meyer {
4603c30b235SConrad Meyer 	return (_pctrie_lookup(ptree, index, NULL, PCTRIE_LOCKED));
4613c30b235SConrad Meyer }
4623c30b235SConrad Meyer 
4633c30b235SConrad Meyer /*
4643c30b235SConrad Meyer  * Returns the value stored at the index without requiring an external lock.
4653c30b235SConrad Meyer  *
4663c30b235SConrad Meyer  * If the index is not present, NULL is returned.
4673c30b235SConrad Meyer  */
4683c30b235SConrad Meyer uint64_t *
4693c30b235SConrad Meyer pctrie_lookup_unlocked(struct pctrie *ptree, uint64_t index, smr_t smr)
4703c30b235SConrad Meyer {
4713c30b235SConrad Meyer 	uint64_t *res;
4723c30b235SConrad Meyer 
4733c30b235SConrad Meyer 	smr_enter(smr);
4743c30b235SConrad Meyer 	res = _pctrie_lookup(ptree, index, smr, PCTRIE_SMR);
4753c30b235SConrad Meyer 	smr_exit(smr);
4763c30b235SConrad Meyer 	return (res);
4773c30b235SConrad Meyer }
4783c30b235SConrad Meyer 
4793c30b235SConrad Meyer /*
4803c30b235SConrad Meyer  * Look up the nearest entry at a position bigger than or equal to index,
4813c30b235SConrad Meyer  * assuming access is externally synchronized by a lock.
482f2cc1285SJeff Roberson  */
483f2cc1285SJeff Roberson uint64_t *
484f2cc1285SJeff Roberson pctrie_lookup_ge(struct pctrie *ptree, uint64_t index)
485f2cc1285SJeff Roberson {
486f2cc1285SJeff Roberson 	struct pctrie_node *stack[PCTRIE_LIMIT];
487f2cc1285SJeff Roberson 	uint64_t inc;
488f2cc1285SJeff Roberson 	uint64_t *m;
489f2cc1285SJeff Roberson 	struct pctrie_node *child, *node;
490f2cc1285SJeff Roberson #ifdef INVARIANTS
491f2cc1285SJeff Roberson 	int loops = 0;
492f2cc1285SJeff Roberson #endif
493d1139b52SConrad Meyer 	unsigned tos;
494d1139b52SConrad Meyer 	int slot;
495f2cc1285SJeff Roberson 
4963c30b235SConrad Meyer 	node = pctrie_root_load(ptree, NULL, PCTRIE_LOCKED);
497f2cc1285SJeff Roberson 	if (node == NULL)
498f2cc1285SJeff Roberson 		return (NULL);
499f2cc1285SJeff Roberson 	else if (pctrie_isleaf(node)) {
500f2cc1285SJeff Roberson 		m = pctrie_toval(node);
501f2cc1285SJeff Roberson 		if (*m >= index)
502f2cc1285SJeff Roberson 			return (m);
503f2cc1285SJeff Roberson 		else
504f2cc1285SJeff Roberson 			return (NULL);
505f2cc1285SJeff Roberson 	}
506f2cc1285SJeff Roberson 	tos = 0;
507f2cc1285SJeff Roberson 	for (;;) {
508f2cc1285SJeff Roberson 		/*
509f2cc1285SJeff Roberson 		 * If the keys differ before the current bisection node,
510f2cc1285SJeff Roberson 		 * then the search key might rollback to the earliest
511f2cc1285SJeff Roberson 		 * available bisection node or to the smallest key
5123c30b235SConrad Meyer 		 * in the current node (if the owner is greater than the
513f2cc1285SJeff Roberson 		 * search key).
514f2cc1285SJeff Roberson 		 */
515f2cc1285SJeff Roberson 		if (pctrie_keybarr(node, index)) {
516f2cc1285SJeff Roberson 			if (index > node->pn_owner) {
517f2cc1285SJeff Roberson ascend:
518f2cc1285SJeff Roberson 				KASSERT(++loops < 1000,
519f2cc1285SJeff Roberson 				    ("pctrie_lookup_ge: too many loops"));
520f2cc1285SJeff Roberson 
521f2cc1285SJeff Roberson 				/*
522f2cc1285SJeff Roberson 				 * Pop nodes from the stack until either the
523f2cc1285SJeff Roberson 				 * stack is empty or a node that could have a
524f2cc1285SJeff Roberson 				 * matching descendant is found.
525f2cc1285SJeff Roberson 				 */
526f2cc1285SJeff Roberson 				do {
527f2cc1285SJeff Roberson 					if (tos == 0)
528f2cc1285SJeff Roberson 						return (NULL);
529f2cc1285SJeff Roberson 					node = stack[--tos];
530f2cc1285SJeff Roberson 				} while (pctrie_slot(index,
531f2cc1285SJeff Roberson 				    node->pn_clev) == (PCTRIE_COUNT - 1));
532f2cc1285SJeff Roberson 
533f2cc1285SJeff Roberson 				/*
534f2cc1285SJeff Roberson 				 * The following computation cannot overflow
535f2cc1285SJeff Roberson 				 * because index's slot at the current level
536f2cc1285SJeff Roberson 				 * is less than PCTRIE_COUNT - 1.
537f2cc1285SJeff Roberson 				 */
538f2cc1285SJeff Roberson 				index = pctrie_trimkey(index,
539f2cc1285SJeff Roberson 				    node->pn_clev);
540f2cc1285SJeff Roberson 				index += PCTRIE_UNITLEVEL(node->pn_clev);
541f2cc1285SJeff Roberson 			} else
542f2cc1285SJeff Roberson 				index = node->pn_owner;
543f2cc1285SJeff Roberson 			KASSERT(!pctrie_keybarr(node, index),
544f2cc1285SJeff Roberson 			    ("pctrie_lookup_ge: keybarr failed"));
545f2cc1285SJeff Roberson 		}
546f2cc1285SJeff Roberson 		slot = pctrie_slot(index, node->pn_clev);
5473c30b235SConrad Meyer 		child = pctrie_node_load(&node->pn_child[slot], NULL,
5483c30b235SConrad Meyer 		    PCTRIE_LOCKED);
549f2cc1285SJeff Roberson 		if (pctrie_isleaf(child)) {
550f2cc1285SJeff Roberson 			m = pctrie_toval(child);
551f2cc1285SJeff Roberson 			if (*m >= index)
552f2cc1285SJeff Roberson 				return (m);
553f2cc1285SJeff Roberson 		} else if (child != NULL)
554f2cc1285SJeff Roberson 			goto descend;
555f2cc1285SJeff Roberson 
556f2cc1285SJeff Roberson 		/*
557f2cc1285SJeff Roberson 		 * Look for an available edge or val within the current
558f2cc1285SJeff Roberson 		 * bisection node.
559f2cc1285SJeff Roberson 		 */
560f2cc1285SJeff Roberson                 if (slot < (PCTRIE_COUNT - 1)) {
561f2cc1285SJeff Roberson 			inc = PCTRIE_UNITLEVEL(node->pn_clev);
562f2cc1285SJeff Roberson 			index = pctrie_trimkey(index, node->pn_clev);
563f2cc1285SJeff Roberson 			do {
564f2cc1285SJeff Roberson 				index += inc;
565f2cc1285SJeff Roberson 				slot++;
5663c30b235SConrad Meyer 				child = pctrie_node_load(&node->pn_child[slot],
5673c30b235SConrad Meyer 				    NULL, PCTRIE_LOCKED);
568f2cc1285SJeff Roberson 				if (pctrie_isleaf(child)) {
569f2cc1285SJeff Roberson 					m = pctrie_toval(child);
570f2cc1285SJeff Roberson 					if (*m >= index)
571f2cc1285SJeff Roberson 						return (m);
572f2cc1285SJeff Roberson 				} else if (child != NULL)
573f2cc1285SJeff Roberson 					goto descend;
574f2cc1285SJeff Roberson 			} while (slot < (PCTRIE_COUNT - 1));
575f2cc1285SJeff Roberson 		}
576f2cc1285SJeff Roberson 		KASSERT(child == NULL || pctrie_isleaf(child),
577f2cc1285SJeff Roberson 		    ("pctrie_lookup_ge: child is radix node"));
578f2cc1285SJeff Roberson 
579f2cc1285SJeff Roberson 		/*
5803c30b235SConrad Meyer 		 * If a value or edge greater than the search slot is not found
581f2cc1285SJeff Roberson 		 * in the current node, ascend to the next higher-level node.
582f2cc1285SJeff Roberson 		 */
583f2cc1285SJeff Roberson 		goto ascend;
584f2cc1285SJeff Roberson descend:
585f2cc1285SJeff Roberson 		KASSERT(node->pn_clev > 0,
586f2cc1285SJeff Roberson 		    ("pctrie_lookup_ge: pushing leaf's parent"));
587f2cc1285SJeff Roberson 		KASSERT(tos < PCTRIE_LIMIT,
588f2cc1285SJeff Roberson 		    ("pctrie_lookup_ge: stack overflow"));
589f2cc1285SJeff Roberson 		stack[tos++] = node;
590f2cc1285SJeff Roberson 		node = child;
591f2cc1285SJeff Roberson 	}
592f2cc1285SJeff Roberson }
593f2cc1285SJeff Roberson 
594f2cc1285SJeff Roberson /*
5953c30b235SConrad Meyer  * Look up the nearest entry at a position less than or equal to index,
5963c30b235SConrad Meyer  * assuming access is externally synchronized by a lock.
597f2cc1285SJeff Roberson  */
598f2cc1285SJeff Roberson uint64_t *
599f2cc1285SJeff Roberson pctrie_lookup_le(struct pctrie *ptree, uint64_t index)
600f2cc1285SJeff Roberson {
601f2cc1285SJeff Roberson 	struct pctrie_node *stack[PCTRIE_LIMIT];
602f2cc1285SJeff Roberson 	uint64_t inc;
603f2cc1285SJeff Roberson 	uint64_t *m;
604f2cc1285SJeff Roberson 	struct pctrie_node *child, *node;
605f2cc1285SJeff Roberson #ifdef INVARIANTS
606f2cc1285SJeff Roberson 	int loops = 0;
607f2cc1285SJeff Roberson #endif
608d1139b52SConrad Meyer 	unsigned tos;
609d1139b52SConrad Meyer 	int slot;
610f2cc1285SJeff Roberson 
6113c30b235SConrad Meyer 	node = pctrie_root_load(ptree, NULL, PCTRIE_LOCKED);
612f2cc1285SJeff Roberson 	if (node == NULL)
613f2cc1285SJeff Roberson 		return (NULL);
614f2cc1285SJeff Roberson 	else if (pctrie_isleaf(node)) {
615f2cc1285SJeff Roberson 		m = pctrie_toval(node);
616f2cc1285SJeff Roberson 		if (*m <= index)
617f2cc1285SJeff Roberson 			return (m);
618f2cc1285SJeff Roberson 		else
619f2cc1285SJeff Roberson 			return (NULL);
620f2cc1285SJeff Roberson 	}
621f2cc1285SJeff Roberson 	tos = 0;
622f2cc1285SJeff Roberson 	for (;;) {
623f2cc1285SJeff Roberson 		/*
624f2cc1285SJeff Roberson 		 * If the keys differ before the current bisection node,
625f2cc1285SJeff Roberson 		 * then the search key might rollback to the earliest
626f2cc1285SJeff Roberson 		 * available bisection node or to the largest key
627f2cc1285SJeff Roberson 		 * in the current node (if the owner is smaller than the
628f2cc1285SJeff Roberson 		 * search key).
629f2cc1285SJeff Roberson 		 */
630f2cc1285SJeff Roberson 		if (pctrie_keybarr(node, index)) {
631f2cc1285SJeff Roberson 			if (index > node->pn_owner) {
632f2cc1285SJeff Roberson 				index = node->pn_owner + PCTRIE_COUNT *
633f2cc1285SJeff Roberson 				    PCTRIE_UNITLEVEL(node->pn_clev);
634f2cc1285SJeff Roberson 			} else {
635f2cc1285SJeff Roberson ascend:
636f2cc1285SJeff Roberson 				KASSERT(++loops < 1000,
637f2cc1285SJeff Roberson 				    ("pctrie_lookup_le: too many loops"));
638f2cc1285SJeff Roberson 
639f2cc1285SJeff Roberson 				/*
640f2cc1285SJeff Roberson 				 * Pop nodes from the stack until either the
641f2cc1285SJeff Roberson 				 * stack is empty or a node that could have a
642f2cc1285SJeff Roberson 				 * matching descendant is found.
643f2cc1285SJeff Roberson 				 */
644f2cc1285SJeff Roberson 				do {
645f2cc1285SJeff Roberson 					if (tos == 0)
646f2cc1285SJeff Roberson 						return (NULL);
647f2cc1285SJeff Roberson 					node = stack[--tos];
648f2cc1285SJeff Roberson 				} while (pctrie_slot(index,
649f2cc1285SJeff Roberson 				    node->pn_clev) == 0);
650f2cc1285SJeff Roberson 
651f2cc1285SJeff Roberson 				/*
652f2cc1285SJeff Roberson 				 * The following computation cannot overflow
653f2cc1285SJeff Roberson 				 * because index's slot at the current level
654f2cc1285SJeff Roberson 				 * is greater than 0.
655f2cc1285SJeff Roberson 				 */
656f2cc1285SJeff Roberson 				index = pctrie_trimkey(index,
657f2cc1285SJeff Roberson 				    node->pn_clev);
658f2cc1285SJeff Roberson 			}
659f2cc1285SJeff Roberson 			index--;
660f2cc1285SJeff Roberson 			KASSERT(!pctrie_keybarr(node, index),
661f2cc1285SJeff Roberson 			    ("pctrie_lookup_le: keybarr failed"));
662f2cc1285SJeff Roberson 		}
663f2cc1285SJeff Roberson 		slot = pctrie_slot(index, node->pn_clev);
6643c30b235SConrad Meyer 		child = pctrie_node_load(&node->pn_child[slot], NULL,
6653c30b235SConrad Meyer 		    PCTRIE_LOCKED);
666f2cc1285SJeff Roberson 		if (pctrie_isleaf(child)) {
667f2cc1285SJeff Roberson 			m = pctrie_toval(child);
668f2cc1285SJeff Roberson 			if (*m <= index)
669f2cc1285SJeff Roberson 				return (m);
670f2cc1285SJeff Roberson 		} else if (child != NULL)
671f2cc1285SJeff Roberson 			goto descend;
672f2cc1285SJeff Roberson 
673f2cc1285SJeff Roberson 		/*
674f2cc1285SJeff Roberson 		 * Look for an available edge or value within the current
675f2cc1285SJeff Roberson 		 * bisection node.
676f2cc1285SJeff Roberson 		 */
677f2cc1285SJeff Roberson 		if (slot > 0) {
678f2cc1285SJeff Roberson 			inc = PCTRIE_UNITLEVEL(node->pn_clev);
679f2cc1285SJeff Roberson 			index |= inc - 1;
680f2cc1285SJeff Roberson 			do {
681f2cc1285SJeff Roberson 				index -= inc;
682f2cc1285SJeff Roberson 				slot--;
6833c30b235SConrad Meyer 				child = pctrie_node_load(&node->pn_child[slot],
6843c30b235SConrad Meyer 				    NULL, PCTRIE_LOCKED);
685f2cc1285SJeff Roberson 				if (pctrie_isleaf(child)) {
686f2cc1285SJeff Roberson 					m = pctrie_toval(child);
687f2cc1285SJeff Roberson 					if (*m <= index)
688f2cc1285SJeff Roberson 						return (m);
689f2cc1285SJeff Roberson 				} else if (child != NULL)
690f2cc1285SJeff Roberson 					goto descend;
691f2cc1285SJeff Roberson 			} while (slot > 0);
692f2cc1285SJeff Roberson 		}
693f2cc1285SJeff Roberson 		KASSERT(child == NULL || pctrie_isleaf(child),
694f2cc1285SJeff Roberson 		    ("pctrie_lookup_le: child is radix node"));
695f2cc1285SJeff Roberson 
696f2cc1285SJeff Roberson 		/*
697f2cc1285SJeff Roberson 		 * If a value or edge smaller than the search slot is not found
698f2cc1285SJeff Roberson 		 * in the current node, ascend to the next higher-level node.
699f2cc1285SJeff Roberson 		 */
700f2cc1285SJeff Roberson 		goto ascend;
701f2cc1285SJeff Roberson descend:
702f2cc1285SJeff Roberson 		KASSERT(node->pn_clev > 0,
703f2cc1285SJeff Roberson 		    ("pctrie_lookup_le: pushing leaf's parent"));
704f2cc1285SJeff Roberson 		KASSERT(tos < PCTRIE_LIMIT,
705f2cc1285SJeff Roberson 		    ("pctrie_lookup_le: stack overflow"));
706f2cc1285SJeff Roberson 		stack[tos++] = node;
707f2cc1285SJeff Roberson 		node = child;
708f2cc1285SJeff Roberson 	}
709f2cc1285SJeff Roberson }
710f2cc1285SJeff Roberson 
711f2cc1285SJeff Roberson /*
712f2cc1285SJeff Roberson  * Remove the specified index from the tree.
713f2cc1285SJeff Roberson  * Panics if the key is not present.
714f2cc1285SJeff Roberson  */
715f2cc1285SJeff Roberson void
716f2cc1285SJeff Roberson pctrie_remove(struct pctrie *ptree, uint64_t index, pctrie_free_t freefn)
717f2cc1285SJeff Roberson {
7183c30b235SConrad Meyer 	struct pctrie_node *node, *parent, *tmp;
719f2cc1285SJeff Roberson 	uint64_t *m;
720f2cc1285SJeff Roberson 	int i, slot;
721f2cc1285SJeff Roberson 
7223c30b235SConrad Meyer 	node = pctrie_root_load(ptree, NULL, PCTRIE_LOCKED);
723f2cc1285SJeff Roberson 	if (pctrie_isleaf(node)) {
724f2cc1285SJeff Roberson 		m = pctrie_toval(node);
725f2cc1285SJeff Roberson 		if (*m != index)
726f2cc1285SJeff Roberson 			panic("%s: invalid key found", __func__);
7273c30b235SConrad Meyer 		pctrie_root_store(ptree, NULL, PCTRIE_LOCKED);
728f2cc1285SJeff Roberson 		return;
729f2cc1285SJeff Roberson 	}
730f2cc1285SJeff Roberson 	parent = NULL;
731f2cc1285SJeff Roberson 	for (;;) {
732f2cc1285SJeff Roberson 		if (node == NULL)
733f2cc1285SJeff Roberson 			panic("pctrie_remove: impossible to locate the key");
734f2cc1285SJeff Roberson 		slot = pctrie_slot(index, node->pn_clev);
7353c30b235SConrad Meyer 		tmp = pctrie_node_load(&node->pn_child[slot], NULL,
7363c30b235SConrad Meyer 		    PCTRIE_LOCKED);
7373c30b235SConrad Meyer 		if (pctrie_isleaf(tmp)) {
7383c30b235SConrad Meyer 			m = pctrie_toval(tmp);
739f2cc1285SJeff Roberson 			if (*m != index)
740f2cc1285SJeff Roberson 				panic("%s: invalid key found", __func__);
7413c30b235SConrad Meyer 			pctrie_node_store(&node->pn_child[slot], NULL,
7423c30b235SConrad Meyer 			    PCTRIE_LOCKED);
743f2cc1285SJeff Roberson 			node->pn_count--;
744f2cc1285SJeff Roberson 			if (node->pn_count > 1)
745f2cc1285SJeff Roberson 				break;
7463c30b235SConrad Meyer 			for (i = 0; i < PCTRIE_COUNT; i++) {
7473c30b235SConrad Meyer 				tmp = pctrie_node_load(&node->pn_child[i],
7483c30b235SConrad Meyer 				    NULL, PCTRIE_LOCKED);
7493c30b235SConrad Meyer 				if (tmp != NULL)
750f2cc1285SJeff Roberson 					break;
7513c30b235SConrad Meyer 			}
752f2cc1285SJeff Roberson 			KASSERT(i != PCTRIE_COUNT,
753f2cc1285SJeff Roberson 			    ("%s: invalid node configuration", __func__));
754f2cc1285SJeff Roberson 			if (parent == NULL)
7553c30b235SConrad Meyer 				pctrie_root_store(ptree, tmp, PCTRIE_LOCKED);
756f2cc1285SJeff Roberson 			else {
757f2cc1285SJeff Roberson 				slot = pctrie_slot(index, parent->pn_clev);
7583c30b235SConrad Meyer 				KASSERT(pctrie_node_load(
7593c30b235SConrad Meyer 					&parent->pn_child[slot], NULL,
7603c30b235SConrad Meyer 					PCTRIE_LOCKED) == node,
761f2cc1285SJeff Roberson 				    ("%s: invalid child value", __func__));
7623c30b235SConrad Meyer 				pctrie_node_store(&parent->pn_child[slot], tmp,
7633c30b235SConrad Meyer 				    PCTRIE_LOCKED);
764f2cc1285SJeff Roberson 			}
7653c30b235SConrad Meyer 			/*
7663c30b235SConrad Meyer 			 * The child is still valid and we can not zero the
7673c30b235SConrad Meyer 			 * pointer until all SMR references are gone.
7683c30b235SConrad Meyer 			 */
769f2cc1285SJeff Roberson 			node->pn_count--;
7703c30b235SConrad Meyer 			pctrie_node_put(ptree, node, freefn, i);
771f2cc1285SJeff Roberson 			break;
772f2cc1285SJeff Roberson 		}
773f2cc1285SJeff Roberson 		parent = node;
7743c30b235SConrad Meyer 		node = tmp;
775f2cc1285SJeff Roberson 	}
776f2cc1285SJeff Roberson }
777f2cc1285SJeff Roberson 
778f2cc1285SJeff Roberson /*
779f2cc1285SJeff Roberson  * Remove and free all the nodes from the tree.
780f2cc1285SJeff Roberson  * This function is recursive but there is a tight control on it as the
781f2cc1285SJeff Roberson  * maximum depth of the tree is fixed.
782f2cc1285SJeff Roberson  */
783f2cc1285SJeff Roberson void
784f2cc1285SJeff Roberson pctrie_reclaim_allnodes(struct pctrie *ptree, pctrie_free_t freefn)
785f2cc1285SJeff Roberson {
786f2cc1285SJeff Roberson 	struct pctrie_node *root;
787f2cc1285SJeff Roberson 
7883c30b235SConrad Meyer 	root = pctrie_root_load(ptree, NULL, PCTRIE_LOCKED);
789f2cc1285SJeff Roberson 	if (root == NULL)
790f2cc1285SJeff Roberson 		return;
7913c30b235SConrad Meyer 	pctrie_root_store(ptree, NULL, PCTRIE_UNSERIALIZED);
792f2cc1285SJeff Roberson 	if (!pctrie_isleaf(root))
793f2cc1285SJeff Roberson 		pctrie_reclaim_allnodes_int(ptree, root, freefn);
794f2cc1285SJeff Roberson }
795f2cc1285SJeff Roberson 
796f2cc1285SJeff Roberson #ifdef DDB
797f2cc1285SJeff Roberson /*
798f2cc1285SJeff Roberson  * Show details about the given node.
799f2cc1285SJeff Roberson  */
800f2cc1285SJeff Roberson DB_SHOW_COMMAND(pctrienode, db_show_pctrienode)
801f2cc1285SJeff Roberson {
8023c30b235SConrad Meyer 	struct pctrie_node *node, *tmp;
803f2cc1285SJeff Roberson 	int i;
804f2cc1285SJeff Roberson 
805f2cc1285SJeff Roberson         if (!have_addr)
806f2cc1285SJeff Roberson                 return;
807f2cc1285SJeff Roberson 	node = (struct pctrie_node *)addr;
808f2cc1285SJeff Roberson 	db_printf("node %p, owner %jx, children count %u, level %u:\n",
809f2cc1285SJeff Roberson 	    (void *)node, (uintmax_t)node->pn_owner, node->pn_count,
810f2cc1285SJeff Roberson 	    node->pn_clev);
8113c30b235SConrad Meyer 	for (i = 0; i < PCTRIE_COUNT; i++) {
8123c30b235SConrad Meyer 		tmp = pctrie_node_load(&node->pn_child[i], NULL,
8133c30b235SConrad Meyer 		    PCTRIE_UNSERIALIZED);
8143c30b235SConrad Meyer 		if (tmp != NULL)
815f2cc1285SJeff Roberson 			db_printf("slot: %d, val: %p, value: %p, clev: %d\n",
8163c30b235SConrad Meyer 			    i, (void *)tmp,
8173c30b235SConrad Meyer 			    pctrie_isleaf(tmp) ? pctrie_toval(tmp) : NULL,
818f2cc1285SJeff Roberson 			    node->pn_clev);
819f2cc1285SJeff Roberson 	}
8203c30b235SConrad Meyer }
821f2cc1285SJeff Roberson #endif /* DDB */
822