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