18a36da99SPedro F. Giffuni /*- 28a36da99SPedro F. Giffuni * SPDX-License-Identifier: BSD-2-Clause-FreeBSD 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> 57f2cc1285SJeff Roberson #include <sys/pctrie.h> 58f2cc1285SJeff Roberson 59f2cc1285SJeff Roberson #ifdef DDB 60f2cc1285SJeff Roberson #include <ddb/ddb.h> 61f2cc1285SJeff Roberson #endif 62f2cc1285SJeff Roberson 63f2cc1285SJeff Roberson #define PCTRIE_MASK (PCTRIE_COUNT - 1) 6455e0987aSPedro F. Giffuni #define PCTRIE_LIMIT (howmany(sizeof(uint64_t) * NBBY, PCTRIE_WIDTH) - 1) 65f2cc1285SJeff Roberson 66f2cc1285SJeff Roberson /* Flag bits stored in node pointers. */ 67f2cc1285SJeff Roberson #define PCTRIE_ISLEAF 0x1 68f2cc1285SJeff Roberson #define PCTRIE_FLAGS 0x1 69f2cc1285SJeff Roberson #define PCTRIE_PAD PCTRIE_FLAGS 70f2cc1285SJeff Roberson 71f2cc1285SJeff Roberson /* Returns one unit associated with specified level. */ 72f2cc1285SJeff Roberson #define PCTRIE_UNITLEVEL(lev) \ 73f2cc1285SJeff Roberson ((uint64_t)1 << ((lev) * PCTRIE_WIDTH)) 74f2cc1285SJeff Roberson 75f2cc1285SJeff Roberson struct pctrie_node { 76f2cc1285SJeff Roberson uint64_t pn_owner; /* Owner of record. */ 77f2cc1285SJeff Roberson uint16_t pn_count; /* Valid children. */ 78f2cc1285SJeff Roberson uint16_t pn_clev; /* Current level. */ 79f2cc1285SJeff Roberson void *pn_child[PCTRIE_COUNT]; /* Child nodes. */ 80f2cc1285SJeff Roberson }; 81f2cc1285SJeff Roberson 82f2cc1285SJeff Roberson /* 83f2cc1285SJeff Roberson * Allocate a node. Pre-allocation should ensure that the request 84f2cc1285SJeff Roberson * will always be satisfied. 85f2cc1285SJeff Roberson */ 86f2cc1285SJeff Roberson static __inline struct pctrie_node * 87f2cc1285SJeff Roberson pctrie_node_get(struct pctrie *ptree, pctrie_alloc_t allocfn, uint64_t owner, 88f2cc1285SJeff Roberson uint16_t count, uint16_t clevel) 89f2cc1285SJeff Roberson { 90f2cc1285SJeff Roberson struct pctrie_node *node; 91f2cc1285SJeff Roberson 92f2cc1285SJeff Roberson node = allocfn(ptree); 93f2cc1285SJeff Roberson if (node == NULL) 94f2cc1285SJeff Roberson return (NULL); 95f2cc1285SJeff Roberson node->pn_owner = owner; 96f2cc1285SJeff Roberson node->pn_count = count; 97f2cc1285SJeff Roberson node->pn_clev = clevel; 98f2cc1285SJeff Roberson 99f2cc1285SJeff Roberson return (node); 100f2cc1285SJeff Roberson } 101f2cc1285SJeff Roberson 102f2cc1285SJeff Roberson /* 103f2cc1285SJeff Roberson * Free radix node. 104f2cc1285SJeff Roberson */ 105f2cc1285SJeff Roberson static __inline void 106f2cc1285SJeff Roberson pctrie_node_put(struct pctrie *ptree, struct pctrie_node *node, 107f2cc1285SJeff Roberson pctrie_free_t freefn) 108f2cc1285SJeff Roberson { 109f2cc1285SJeff Roberson #ifdef INVARIANTS 110f2cc1285SJeff Roberson int slot; 111f2cc1285SJeff Roberson 112f2cc1285SJeff Roberson KASSERT(node->pn_count == 0, 113f2cc1285SJeff Roberson ("pctrie_node_put: node %p has %d children", node, 114f2cc1285SJeff Roberson node->pn_count)); 115f2cc1285SJeff Roberson for (slot = 0; slot < PCTRIE_COUNT; slot++) 116f2cc1285SJeff Roberson KASSERT(node->pn_child[slot] == NULL, 117f2cc1285SJeff Roberson ("pctrie_node_put: node %p has a child", node)); 118f2cc1285SJeff Roberson #endif 119f2cc1285SJeff Roberson freefn(ptree, node); 120f2cc1285SJeff Roberson } 121f2cc1285SJeff Roberson 122f2cc1285SJeff Roberson /* 123f2cc1285SJeff Roberson * Return the position in the array for a given level. 124f2cc1285SJeff Roberson */ 125f2cc1285SJeff Roberson static __inline int 126f2cc1285SJeff Roberson pctrie_slot(uint64_t index, uint16_t level) 127f2cc1285SJeff Roberson { 128f2cc1285SJeff Roberson 129f2cc1285SJeff Roberson return ((index >> (level * PCTRIE_WIDTH)) & PCTRIE_MASK); 130f2cc1285SJeff Roberson } 131f2cc1285SJeff Roberson 132f2cc1285SJeff Roberson /* Trims the key after the specified level. */ 133f2cc1285SJeff Roberson static __inline uint64_t 134f2cc1285SJeff Roberson pctrie_trimkey(uint64_t index, uint16_t level) 135f2cc1285SJeff Roberson { 136f2cc1285SJeff Roberson uint64_t ret; 137f2cc1285SJeff Roberson 138f2cc1285SJeff Roberson ret = index; 139f2cc1285SJeff Roberson if (level > 0) { 140f2cc1285SJeff Roberson ret >>= level * PCTRIE_WIDTH; 141f2cc1285SJeff Roberson ret <<= level * PCTRIE_WIDTH; 142f2cc1285SJeff Roberson } 143f2cc1285SJeff Roberson return (ret); 144f2cc1285SJeff Roberson } 145f2cc1285SJeff Roberson 146f2cc1285SJeff Roberson /* 147f2cc1285SJeff Roberson * Get the root node for a tree. 148f2cc1285SJeff Roberson */ 149f2cc1285SJeff Roberson static __inline struct pctrie_node * 150f2cc1285SJeff Roberson pctrie_getroot(struct pctrie *ptree) 151f2cc1285SJeff Roberson { 152f2cc1285SJeff Roberson 153f2cc1285SJeff Roberson return ((struct pctrie_node *)ptree->pt_root); 154f2cc1285SJeff Roberson } 155f2cc1285SJeff Roberson 156f2cc1285SJeff Roberson /* 157f2cc1285SJeff Roberson * Set the root node for a tree. 158f2cc1285SJeff Roberson */ 159f2cc1285SJeff Roberson static __inline void 160f2cc1285SJeff Roberson pctrie_setroot(struct pctrie *ptree, struct pctrie_node *node) 161f2cc1285SJeff Roberson { 162f2cc1285SJeff Roberson 163f2cc1285SJeff Roberson ptree->pt_root = (uintptr_t)node; 164f2cc1285SJeff Roberson } 165f2cc1285SJeff Roberson 166f2cc1285SJeff Roberson /* 167f2cc1285SJeff Roberson * Returns TRUE if the specified node is a leaf and FALSE otherwise. 168f2cc1285SJeff Roberson */ 16904f9afaeSConrad Meyer static __inline bool 170f2cc1285SJeff Roberson pctrie_isleaf(struct pctrie_node *node) 171f2cc1285SJeff Roberson { 172f2cc1285SJeff Roberson 173f2cc1285SJeff Roberson return (((uintptr_t)node & PCTRIE_ISLEAF) != 0); 174f2cc1285SJeff Roberson } 175f2cc1285SJeff Roberson 176f2cc1285SJeff Roberson /* 177f2cc1285SJeff Roberson * Returns the associated val extracted from node. 178f2cc1285SJeff Roberson */ 179f2cc1285SJeff Roberson static __inline uint64_t * 180f2cc1285SJeff Roberson pctrie_toval(struct pctrie_node *node) 181f2cc1285SJeff Roberson { 182f2cc1285SJeff Roberson 183f2cc1285SJeff Roberson return ((uint64_t *)((uintptr_t)node & ~PCTRIE_FLAGS)); 184f2cc1285SJeff Roberson } 185f2cc1285SJeff Roberson 186f2cc1285SJeff Roberson /* 187f2cc1285SJeff Roberson * Adds the val as a child of the provided node. 188f2cc1285SJeff Roberson */ 189f2cc1285SJeff Roberson static __inline void 190f2cc1285SJeff Roberson pctrie_addval(struct pctrie_node *node, uint64_t index, uint16_t clev, 191f2cc1285SJeff Roberson uint64_t *val) 192f2cc1285SJeff Roberson { 193f2cc1285SJeff Roberson int slot; 194f2cc1285SJeff Roberson 195f2cc1285SJeff Roberson slot = pctrie_slot(index, clev); 196f2cc1285SJeff Roberson node->pn_child[slot] = (void *)((uintptr_t)val | PCTRIE_ISLEAF); 197f2cc1285SJeff Roberson } 198f2cc1285SJeff Roberson 199f2cc1285SJeff Roberson /* 200f2cc1285SJeff Roberson * Returns the slot where two keys differ. 201f2cc1285SJeff Roberson * It cannot accept 2 equal keys. 202f2cc1285SJeff Roberson */ 203f2cc1285SJeff Roberson static __inline uint16_t 204f2cc1285SJeff Roberson pctrie_keydiff(uint64_t index1, uint64_t index2) 205f2cc1285SJeff Roberson { 206f2cc1285SJeff Roberson uint16_t clev; 207f2cc1285SJeff Roberson 208f2cc1285SJeff Roberson KASSERT(index1 != index2, ("%s: passing the same key value %jx", 209f2cc1285SJeff Roberson __func__, (uintmax_t)index1)); 210f2cc1285SJeff Roberson 211f2cc1285SJeff Roberson index1 ^= index2; 212f2cc1285SJeff Roberson for (clev = PCTRIE_LIMIT;; clev--) 213f2cc1285SJeff Roberson if (pctrie_slot(index1, clev) != 0) 214f2cc1285SJeff Roberson return (clev); 215f2cc1285SJeff Roberson } 216f2cc1285SJeff Roberson 217f2cc1285SJeff Roberson /* 218f2cc1285SJeff Roberson * Returns TRUE if it can be determined that key does not belong to the 219f2cc1285SJeff Roberson * specified node. Otherwise, returns FALSE. 220f2cc1285SJeff Roberson */ 22104f9afaeSConrad Meyer static __inline bool 222f2cc1285SJeff Roberson pctrie_keybarr(struct pctrie_node *node, uint64_t idx) 223f2cc1285SJeff Roberson { 224f2cc1285SJeff Roberson 225f2cc1285SJeff Roberson if (node->pn_clev < PCTRIE_LIMIT) { 226f2cc1285SJeff Roberson idx = pctrie_trimkey(idx, node->pn_clev + 1); 227f2cc1285SJeff Roberson return (idx != node->pn_owner); 228f2cc1285SJeff Roberson } 22904f9afaeSConrad Meyer return (false); 230f2cc1285SJeff Roberson } 231f2cc1285SJeff Roberson 232f2cc1285SJeff Roberson /* 233f2cc1285SJeff Roberson * Internal helper for pctrie_reclaim_allnodes(). 234f2cc1285SJeff Roberson * This function is recursive. 235f2cc1285SJeff Roberson */ 236f2cc1285SJeff Roberson static void 237f2cc1285SJeff Roberson pctrie_reclaim_allnodes_int(struct pctrie *ptree, struct pctrie_node *node, 238f2cc1285SJeff Roberson pctrie_free_t freefn) 239f2cc1285SJeff Roberson { 240f2cc1285SJeff Roberson int slot; 241f2cc1285SJeff Roberson 242f2cc1285SJeff Roberson KASSERT(node->pn_count <= PCTRIE_COUNT, 243f2cc1285SJeff Roberson ("pctrie_reclaim_allnodes_int: bad count in node %p", node)); 244f2cc1285SJeff Roberson for (slot = 0; node->pn_count != 0; slot++) { 245f2cc1285SJeff Roberson if (node->pn_child[slot] == NULL) 246f2cc1285SJeff Roberson continue; 247f2cc1285SJeff Roberson if (!pctrie_isleaf(node->pn_child[slot])) 248f2cc1285SJeff Roberson pctrie_reclaim_allnodes_int(ptree, 249f2cc1285SJeff Roberson node->pn_child[slot], freefn); 250f2cc1285SJeff Roberson node->pn_child[slot] = NULL; 251f2cc1285SJeff Roberson node->pn_count--; 252f2cc1285SJeff Roberson } 253f2cc1285SJeff Roberson pctrie_node_put(ptree, node, freefn); 254f2cc1285SJeff Roberson } 255f2cc1285SJeff Roberson 256f2cc1285SJeff Roberson /* 257f2cc1285SJeff Roberson * pctrie node zone initializer. 258f2cc1285SJeff Roberson */ 259f2cc1285SJeff Roberson int 260f2cc1285SJeff Roberson pctrie_zone_init(void *mem, int size __unused, int flags __unused) 261f2cc1285SJeff Roberson { 262f2cc1285SJeff Roberson struct pctrie_node *node; 263f2cc1285SJeff Roberson 264f2cc1285SJeff Roberson node = mem; 265f2cc1285SJeff Roberson memset(node->pn_child, 0, sizeof(node->pn_child)); 266f2cc1285SJeff Roberson return (0); 267f2cc1285SJeff Roberson } 268f2cc1285SJeff Roberson 269f2cc1285SJeff Roberson size_t 270f2cc1285SJeff Roberson pctrie_node_size(void) 271f2cc1285SJeff Roberson { 272f2cc1285SJeff Roberson 273f2cc1285SJeff Roberson return (sizeof(struct pctrie_node)); 274f2cc1285SJeff Roberson } 275f2cc1285SJeff Roberson 276f2cc1285SJeff Roberson /* 277f2cc1285SJeff Roberson * Inserts the key-value pair into the trie. 278f2cc1285SJeff Roberson * Panics if the key already exists. 279f2cc1285SJeff Roberson */ 280f2cc1285SJeff Roberson int 281f2cc1285SJeff Roberson pctrie_insert(struct pctrie *ptree, uint64_t *val, pctrie_alloc_t allocfn) 282f2cc1285SJeff Roberson { 283f2cc1285SJeff Roberson uint64_t index, newind; 284f2cc1285SJeff Roberson void **parentp; 285f2cc1285SJeff Roberson struct pctrie_node *node, *tmp; 286f2cc1285SJeff Roberson uint64_t *m; 287f2cc1285SJeff Roberson int slot; 288f2cc1285SJeff Roberson uint16_t clev; 289f2cc1285SJeff Roberson 290f2cc1285SJeff Roberson index = *val; 291f2cc1285SJeff Roberson 292f2cc1285SJeff Roberson /* 293f2cc1285SJeff Roberson * The owner of record for root is not really important because it 294f2cc1285SJeff Roberson * will never be used. 295f2cc1285SJeff Roberson */ 296f2cc1285SJeff Roberson node = pctrie_getroot(ptree); 297f2cc1285SJeff Roberson if (node == NULL) { 298f2cc1285SJeff Roberson ptree->pt_root = (uintptr_t)val | PCTRIE_ISLEAF; 299f2cc1285SJeff Roberson return (0); 300f2cc1285SJeff Roberson } 301f2cc1285SJeff Roberson parentp = (void **)&ptree->pt_root; 302f2cc1285SJeff Roberson for (;;) { 303f2cc1285SJeff Roberson if (pctrie_isleaf(node)) { 304f2cc1285SJeff Roberson m = pctrie_toval(node); 305f2cc1285SJeff Roberson if (*m == index) 306f2cc1285SJeff Roberson panic("%s: key %jx is already present", 307f2cc1285SJeff Roberson __func__, (uintmax_t)index); 308f2cc1285SJeff Roberson clev = pctrie_keydiff(*m, index); 309f2cc1285SJeff Roberson tmp = pctrie_node_get(ptree, allocfn, 310f2cc1285SJeff Roberson pctrie_trimkey(index, clev + 1), 2, clev); 311f2cc1285SJeff Roberson if (tmp == NULL) 312f2cc1285SJeff Roberson return (ENOMEM); 313f2cc1285SJeff Roberson *parentp = tmp; 314f2cc1285SJeff Roberson pctrie_addval(tmp, index, clev, val); 315f2cc1285SJeff Roberson pctrie_addval(tmp, *m, clev, m); 316f2cc1285SJeff Roberson return (0); 317f2cc1285SJeff Roberson } else if (pctrie_keybarr(node, index)) 318f2cc1285SJeff Roberson break; 319f2cc1285SJeff Roberson slot = pctrie_slot(index, node->pn_clev); 320f2cc1285SJeff Roberson if (node->pn_child[slot] == NULL) { 321f2cc1285SJeff Roberson node->pn_count++; 322f2cc1285SJeff Roberson pctrie_addval(node, index, node->pn_clev, val); 323f2cc1285SJeff Roberson return (0); 324f2cc1285SJeff Roberson } 325f2cc1285SJeff Roberson parentp = &node->pn_child[slot]; 326f2cc1285SJeff Roberson node = node->pn_child[slot]; 327f2cc1285SJeff Roberson } 328f2cc1285SJeff Roberson 329f2cc1285SJeff Roberson /* 330f2cc1285SJeff Roberson * A new node is needed because the right insertion level is reached. 331f2cc1285SJeff Roberson * Setup the new intermediate node and add the 2 children: the 332f2cc1285SJeff Roberson * new object and the older edge. 333f2cc1285SJeff Roberson */ 334f2cc1285SJeff Roberson newind = node->pn_owner; 335f2cc1285SJeff Roberson clev = pctrie_keydiff(newind, index); 336f2cc1285SJeff Roberson tmp = pctrie_node_get(ptree, allocfn, 337f2cc1285SJeff Roberson pctrie_trimkey(index, clev + 1), 2, clev); 338f2cc1285SJeff Roberson if (tmp == NULL) 339f2cc1285SJeff Roberson return (ENOMEM); 340f2cc1285SJeff Roberson *parentp = tmp; 341f2cc1285SJeff Roberson pctrie_addval(tmp, index, clev, val); 342f2cc1285SJeff Roberson slot = pctrie_slot(newind, clev); 343f2cc1285SJeff Roberson tmp->pn_child[slot] = node; 344f2cc1285SJeff Roberson 345f2cc1285SJeff Roberson return (0); 346f2cc1285SJeff Roberson } 347f2cc1285SJeff Roberson 348f2cc1285SJeff Roberson /* 349f2cc1285SJeff Roberson * Returns the value stored at the index. If the index is not present, 350f2cc1285SJeff Roberson * NULL is returned. 351f2cc1285SJeff Roberson */ 352f2cc1285SJeff Roberson uint64_t * 353f2cc1285SJeff Roberson pctrie_lookup(struct pctrie *ptree, uint64_t index) 354f2cc1285SJeff Roberson { 355f2cc1285SJeff Roberson struct pctrie_node *node; 356f2cc1285SJeff Roberson uint64_t *m; 357f2cc1285SJeff Roberson int slot; 358f2cc1285SJeff Roberson 359f2cc1285SJeff Roberson node = pctrie_getroot(ptree); 360f2cc1285SJeff Roberson while (node != NULL) { 361f2cc1285SJeff Roberson if (pctrie_isleaf(node)) { 362f2cc1285SJeff Roberson m = pctrie_toval(node); 363f2cc1285SJeff Roberson if (*m == index) 364f2cc1285SJeff Roberson return (m); 365f2cc1285SJeff Roberson else 366f2cc1285SJeff Roberson break; 367f2cc1285SJeff Roberson } else if (pctrie_keybarr(node, index)) 368f2cc1285SJeff Roberson break; 369f2cc1285SJeff Roberson slot = pctrie_slot(index, node->pn_clev); 370f2cc1285SJeff Roberson node = node->pn_child[slot]; 371f2cc1285SJeff Roberson } 372f2cc1285SJeff Roberson return (NULL); 373f2cc1285SJeff Roberson } 374f2cc1285SJeff Roberson 375f2cc1285SJeff Roberson /* 376f2cc1285SJeff Roberson * Look up the nearest entry at a position bigger than or equal to index. 377f2cc1285SJeff Roberson */ 378f2cc1285SJeff Roberson uint64_t * 379f2cc1285SJeff Roberson pctrie_lookup_ge(struct pctrie *ptree, uint64_t index) 380f2cc1285SJeff Roberson { 381f2cc1285SJeff Roberson struct pctrie_node *stack[PCTRIE_LIMIT]; 382f2cc1285SJeff Roberson uint64_t inc; 383f2cc1285SJeff Roberson uint64_t *m; 384f2cc1285SJeff Roberson struct pctrie_node *child, *node; 385f2cc1285SJeff Roberson #ifdef INVARIANTS 386f2cc1285SJeff Roberson int loops = 0; 387f2cc1285SJeff Roberson #endif 388*d1139b52SConrad Meyer unsigned tos; 389*d1139b52SConrad Meyer int slot; 390f2cc1285SJeff Roberson 391f2cc1285SJeff Roberson node = pctrie_getroot(ptree); 392f2cc1285SJeff Roberson if (node == NULL) 393f2cc1285SJeff Roberson return (NULL); 394f2cc1285SJeff Roberson else if (pctrie_isleaf(node)) { 395f2cc1285SJeff Roberson m = pctrie_toval(node); 396f2cc1285SJeff Roberson if (*m >= index) 397f2cc1285SJeff Roberson return (m); 398f2cc1285SJeff Roberson else 399f2cc1285SJeff Roberson return (NULL); 400f2cc1285SJeff Roberson } 401f2cc1285SJeff Roberson tos = 0; 402f2cc1285SJeff Roberson for (;;) { 403f2cc1285SJeff Roberson /* 404f2cc1285SJeff Roberson * If the keys differ before the current bisection node, 405f2cc1285SJeff Roberson * then the search key might rollback to the earliest 406f2cc1285SJeff Roberson * available bisection node or to the smallest key 407f2cc1285SJeff Roberson * in the current node (if the owner is bigger than the 408f2cc1285SJeff Roberson * search key). 409f2cc1285SJeff Roberson */ 410f2cc1285SJeff Roberson if (pctrie_keybarr(node, index)) { 411f2cc1285SJeff Roberson if (index > node->pn_owner) { 412f2cc1285SJeff Roberson ascend: 413f2cc1285SJeff Roberson KASSERT(++loops < 1000, 414f2cc1285SJeff Roberson ("pctrie_lookup_ge: too many loops")); 415f2cc1285SJeff Roberson 416f2cc1285SJeff Roberson /* 417f2cc1285SJeff Roberson * Pop nodes from the stack until either the 418f2cc1285SJeff Roberson * stack is empty or a node that could have a 419f2cc1285SJeff Roberson * matching descendant is found. 420f2cc1285SJeff Roberson */ 421f2cc1285SJeff Roberson do { 422f2cc1285SJeff Roberson if (tos == 0) 423f2cc1285SJeff Roberson return (NULL); 424f2cc1285SJeff Roberson node = stack[--tos]; 425f2cc1285SJeff Roberson } while (pctrie_slot(index, 426f2cc1285SJeff Roberson node->pn_clev) == (PCTRIE_COUNT - 1)); 427f2cc1285SJeff Roberson 428f2cc1285SJeff Roberson /* 429f2cc1285SJeff Roberson * The following computation cannot overflow 430f2cc1285SJeff Roberson * because index's slot at the current level 431f2cc1285SJeff Roberson * is less than PCTRIE_COUNT - 1. 432f2cc1285SJeff Roberson */ 433f2cc1285SJeff Roberson index = pctrie_trimkey(index, 434f2cc1285SJeff Roberson node->pn_clev); 435f2cc1285SJeff Roberson index += PCTRIE_UNITLEVEL(node->pn_clev); 436f2cc1285SJeff Roberson } else 437f2cc1285SJeff Roberson index = node->pn_owner; 438f2cc1285SJeff Roberson KASSERT(!pctrie_keybarr(node, index), 439f2cc1285SJeff Roberson ("pctrie_lookup_ge: keybarr failed")); 440f2cc1285SJeff Roberson } 441f2cc1285SJeff Roberson slot = pctrie_slot(index, node->pn_clev); 442f2cc1285SJeff Roberson child = node->pn_child[slot]; 443f2cc1285SJeff Roberson if (pctrie_isleaf(child)) { 444f2cc1285SJeff Roberson m = pctrie_toval(child); 445f2cc1285SJeff Roberson if (*m >= index) 446f2cc1285SJeff Roberson return (m); 447f2cc1285SJeff Roberson } else if (child != NULL) 448f2cc1285SJeff Roberson goto descend; 449f2cc1285SJeff Roberson 450f2cc1285SJeff Roberson /* 451f2cc1285SJeff Roberson * Look for an available edge or val within the current 452f2cc1285SJeff Roberson * bisection node. 453f2cc1285SJeff Roberson */ 454f2cc1285SJeff Roberson if (slot < (PCTRIE_COUNT - 1)) { 455f2cc1285SJeff Roberson inc = PCTRIE_UNITLEVEL(node->pn_clev); 456f2cc1285SJeff Roberson index = pctrie_trimkey(index, node->pn_clev); 457f2cc1285SJeff Roberson do { 458f2cc1285SJeff Roberson index += inc; 459f2cc1285SJeff Roberson slot++; 460f2cc1285SJeff Roberson child = node->pn_child[slot]; 461f2cc1285SJeff Roberson if (pctrie_isleaf(child)) { 462f2cc1285SJeff Roberson m = pctrie_toval(child); 463f2cc1285SJeff Roberson if (*m >= index) 464f2cc1285SJeff Roberson return (m); 465f2cc1285SJeff Roberson } else if (child != NULL) 466f2cc1285SJeff Roberson goto descend; 467f2cc1285SJeff Roberson } while (slot < (PCTRIE_COUNT - 1)); 468f2cc1285SJeff Roberson } 469f2cc1285SJeff Roberson KASSERT(child == NULL || pctrie_isleaf(child), 470f2cc1285SJeff Roberson ("pctrie_lookup_ge: child is radix node")); 471f2cc1285SJeff Roberson 472f2cc1285SJeff Roberson /* 473f2cc1285SJeff Roberson * If a value or edge bigger than the search slot is not found 474f2cc1285SJeff Roberson * in the current node, ascend to the next higher-level node. 475f2cc1285SJeff Roberson */ 476f2cc1285SJeff Roberson goto ascend; 477f2cc1285SJeff Roberson descend: 478f2cc1285SJeff Roberson KASSERT(node->pn_clev > 0, 479f2cc1285SJeff Roberson ("pctrie_lookup_ge: pushing leaf's parent")); 480f2cc1285SJeff Roberson KASSERT(tos < PCTRIE_LIMIT, 481f2cc1285SJeff Roberson ("pctrie_lookup_ge: stack overflow")); 482f2cc1285SJeff Roberson stack[tos++] = node; 483f2cc1285SJeff Roberson node = child; 484f2cc1285SJeff Roberson } 485f2cc1285SJeff Roberson } 486f2cc1285SJeff Roberson 487f2cc1285SJeff Roberson /* 488f2cc1285SJeff Roberson * Look up the nearest entry at a position less than or equal to index. 489f2cc1285SJeff Roberson */ 490f2cc1285SJeff Roberson uint64_t * 491f2cc1285SJeff Roberson pctrie_lookup_le(struct pctrie *ptree, uint64_t index) 492f2cc1285SJeff Roberson { 493f2cc1285SJeff Roberson struct pctrie_node *stack[PCTRIE_LIMIT]; 494f2cc1285SJeff Roberson uint64_t inc; 495f2cc1285SJeff Roberson uint64_t *m; 496f2cc1285SJeff Roberson struct pctrie_node *child, *node; 497f2cc1285SJeff Roberson #ifdef INVARIANTS 498f2cc1285SJeff Roberson int loops = 0; 499f2cc1285SJeff Roberson #endif 500*d1139b52SConrad Meyer unsigned tos; 501*d1139b52SConrad Meyer int slot; 502f2cc1285SJeff Roberson 503f2cc1285SJeff Roberson node = pctrie_getroot(ptree); 504f2cc1285SJeff Roberson if (node == NULL) 505f2cc1285SJeff Roberson return (NULL); 506f2cc1285SJeff Roberson else if (pctrie_isleaf(node)) { 507f2cc1285SJeff Roberson m = pctrie_toval(node); 508f2cc1285SJeff Roberson if (*m <= index) 509f2cc1285SJeff Roberson return (m); 510f2cc1285SJeff Roberson else 511f2cc1285SJeff Roberson return (NULL); 512f2cc1285SJeff Roberson } 513f2cc1285SJeff Roberson tos = 0; 514f2cc1285SJeff Roberson for (;;) { 515f2cc1285SJeff Roberson /* 516f2cc1285SJeff Roberson * If the keys differ before the current bisection node, 517f2cc1285SJeff Roberson * then the search key might rollback to the earliest 518f2cc1285SJeff Roberson * available bisection node or to the largest key 519f2cc1285SJeff Roberson * in the current node (if the owner is smaller than the 520f2cc1285SJeff Roberson * search key). 521f2cc1285SJeff Roberson */ 522f2cc1285SJeff Roberson if (pctrie_keybarr(node, index)) { 523f2cc1285SJeff Roberson if (index > node->pn_owner) { 524f2cc1285SJeff Roberson index = node->pn_owner + PCTRIE_COUNT * 525f2cc1285SJeff Roberson PCTRIE_UNITLEVEL(node->pn_clev); 526f2cc1285SJeff Roberson } else { 527f2cc1285SJeff Roberson ascend: 528f2cc1285SJeff Roberson KASSERT(++loops < 1000, 529f2cc1285SJeff Roberson ("pctrie_lookup_le: too many loops")); 530f2cc1285SJeff Roberson 531f2cc1285SJeff Roberson /* 532f2cc1285SJeff Roberson * Pop nodes from the stack until either the 533f2cc1285SJeff Roberson * stack is empty or a node that could have a 534f2cc1285SJeff Roberson * matching descendant is found. 535f2cc1285SJeff Roberson */ 536f2cc1285SJeff Roberson do { 537f2cc1285SJeff Roberson if (tos == 0) 538f2cc1285SJeff Roberson return (NULL); 539f2cc1285SJeff Roberson node = stack[--tos]; 540f2cc1285SJeff Roberson } while (pctrie_slot(index, 541f2cc1285SJeff Roberson node->pn_clev) == 0); 542f2cc1285SJeff Roberson 543f2cc1285SJeff Roberson /* 544f2cc1285SJeff Roberson * The following computation cannot overflow 545f2cc1285SJeff Roberson * because index's slot at the current level 546f2cc1285SJeff Roberson * is greater than 0. 547f2cc1285SJeff Roberson */ 548f2cc1285SJeff Roberson index = pctrie_trimkey(index, 549f2cc1285SJeff Roberson node->pn_clev); 550f2cc1285SJeff Roberson } 551f2cc1285SJeff Roberson index--; 552f2cc1285SJeff Roberson KASSERT(!pctrie_keybarr(node, index), 553f2cc1285SJeff Roberson ("pctrie_lookup_le: keybarr failed")); 554f2cc1285SJeff Roberson } 555f2cc1285SJeff Roberson slot = pctrie_slot(index, node->pn_clev); 556f2cc1285SJeff Roberson child = node->pn_child[slot]; 557f2cc1285SJeff Roberson if (pctrie_isleaf(child)) { 558f2cc1285SJeff Roberson m = pctrie_toval(child); 559f2cc1285SJeff Roberson if (*m <= index) 560f2cc1285SJeff Roberson return (m); 561f2cc1285SJeff Roberson } else if (child != NULL) 562f2cc1285SJeff Roberson goto descend; 563f2cc1285SJeff Roberson 564f2cc1285SJeff Roberson /* 565f2cc1285SJeff Roberson * Look for an available edge or value within the current 566f2cc1285SJeff Roberson * bisection node. 567f2cc1285SJeff Roberson */ 568f2cc1285SJeff Roberson if (slot > 0) { 569f2cc1285SJeff Roberson inc = PCTRIE_UNITLEVEL(node->pn_clev); 570f2cc1285SJeff Roberson index |= inc - 1; 571f2cc1285SJeff Roberson do { 572f2cc1285SJeff Roberson index -= inc; 573f2cc1285SJeff Roberson slot--; 574f2cc1285SJeff Roberson child = node->pn_child[slot]; 575f2cc1285SJeff Roberson if (pctrie_isleaf(child)) { 576f2cc1285SJeff Roberson m = pctrie_toval(child); 577f2cc1285SJeff Roberson if (*m <= index) 578f2cc1285SJeff Roberson return (m); 579f2cc1285SJeff Roberson } else if (child != NULL) 580f2cc1285SJeff Roberson goto descend; 581f2cc1285SJeff Roberson } while (slot > 0); 582f2cc1285SJeff Roberson } 583f2cc1285SJeff Roberson KASSERT(child == NULL || pctrie_isleaf(child), 584f2cc1285SJeff Roberson ("pctrie_lookup_le: child is radix node")); 585f2cc1285SJeff Roberson 586f2cc1285SJeff Roberson /* 587f2cc1285SJeff Roberson * If a value or edge smaller than the search slot is not found 588f2cc1285SJeff Roberson * in the current node, ascend to the next higher-level node. 589f2cc1285SJeff Roberson */ 590f2cc1285SJeff Roberson goto ascend; 591f2cc1285SJeff Roberson descend: 592f2cc1285SJeff Roberson KASSERT(node->pn_clev > 0, 593f2cc1285SJeff Roberson ("pctrie_lookup_le: pushing leaf's parent")); 594f2cc1285SJeff Roberson KASSERT(tos < PCTRIE_LIMIT, 595f2cc1285SJeff Roberson ("pctrie_lookup_le: stack overflow")); 596f2cc1285SJeff Roberson stack[tos++] = node; 597f2cc1285SJeff Roberson node = child; 598f2cc1285SJeff Roberson } 599f2cc1285SJeff Roberson } 600f2cc1285SJeff Roberson 601f2cc1285SJeff Roberson /* 602f2cc1285SJeff Roberson * Remove the specified index from the tree. 603f2cc1285SJeff Roberson * Panics if the key is not present. 604f2cc1285SJeff Roberson */ 605f2cc1285SJeff Roberson void 606f2cc1285SJeff Roberson pctrie_remove(struct pctrie *ptree, uint64_t index, pctrie_free_t freefn) 607f2cc1285SJeff Roberson { 608f2cc1285SJeff Roberson struct pctrie_node *node, *parent; 609f2cc1285SJeff Roberson uint64_t *m; 610f2cc1285SJeff Roberson int i, slot; 611f2cc1285SJeff Roberson 612f2cc1285SJeff Roberson node = pctrie_getroot(ptree); 613f2cc1285SJeff Roberson if (pctrie_isleaf(node)) { 614f2cc1285SJeff Roberson m = pctrie_toval(node); 615f2cc1285SJeff Roberson if (*m != index) 616f2cc1285SJeff Roberson panic("%s: invalid key found", __func__); 617f2cc1285SJeff Roberson pctrie_setroot(ptree, NULL); 618f2cc1285SJeff Roberson return; 619f2cc1285SJeff Roberson } 620f2cc1285SJeff Roberson parent = NULL; 621f2cc1285SJeff Roberson for (;;) { 622f2cc1285SJeff Roberson if (node == NULL) 623f2cc1285SJeff Roberson panic("pctrie_remove: impossible to locate the key"); 624f2cc1285SJeff Roberson slot = pctrie_slot(index, node->pn_clev); 625f2cc1285SJeff Roberson if (pctrie_isleaf(node->pn_child[slot])) { 626f2cc1285SJeff Roberson m = pctrie_toval(node->pn_child[slot]); 627f2cc1285SJeff Roberson if (*m != index) 628f2cc1285SJeff Roberson panic("%s: invalid key found", __func__); 629f2cc1285SJeff Roberson node->pn_child[slot] = NULL; 630f2cc1285SJeff Roberson node->pn_count--; 631f2cc1285SJeff Roberson if (node->pn_count > 1) 632f2cc1285SJeff Roberson break; 633f2cc1285SJeff Roberson for (i = 0; i < PCTRIE_COUNT; i++) 634f2cc1285SJeff Roberson if (node->pn_child[i] != NULL) 635f2cc1285SJeff Roberson break; 636f2cc1285SJeff Roberson KASSERT(i != PCTRIE_COUNT, 637f2cc1285SJeff Roberson ("%s: invalid node configuration", __func__)); 638f2cc1285SJeff Roberson if (parent == NULL) 639f2cc1285SJeff Roberson pctrie_setroot(ptree, node->pn_child[i]); 640f2cc1285SJeff Roberson else { 641f2cc1285SJeff Roberson slot = pctrie_slot(index, parent->pn_clev); 642f2cc1285SJeff Roberson KASSERT(parent->pn_child[slot] == node, 643f2cc1285SJeff Roberson ("%s: invalid child value", __func__)); 644f2cc1285SJeff Roberson parent->pn_child[slot] = node->pn_child[i]; 645f2cc1285SJeff Roberson } 646f2cc1285SJeff Roberson node->pn_count--; 647f2cc1285SJeff Roberson node->pn_child[i] = NULL; 648f2cc1285SJeff Roberson pctrie_node_put(ptree, node, freefn); 649f2cc1285SJeff Roberson break; 650f2cc1285SJeff Roberson } 651f2cc1285SJeff Roberson parent = node; 652f2cc1285SJeff Roberson node = node->pn_child[slot]; 653f2cc1285SJeff Roberson } 654f2cc1285SJeff Roberson } 655f2cc1285SJeff Roberson 656f2cc1285SJeff Roberson /* 657f2cc1285SJeff Roberson * Remove and free all the nodes from the tree. 658f2cc1285SJeff Roberson * This function is recursive but there is a tight control on it as the 659f2cc1285SJeff Roberson * maximum depth of the tree is fixed. 660f2cc1285SJeff Roberson */ 661f2cc1285SJeff Roberson void 662f2cc1285SJeff Roberson pctrie_reclaim_allnodes(struct pctrie *ptree, pctrie_free_t freefn) 663f2cc1285SJeff Roberson { 664f2cc1285SJeff Roberson struct pctrie_node *root; 665f2cc1285SJeff Roberson 666f2cc1285SJeff Roberson root = pctrie_getroot(ptree); 667f2cc1285SJeff Roberson if (root == NULL) 668f2cc1285SJeff Roberson return; 669f2cc1285SJeff Roberson pctrie_setroot(ptree, NULL); 670f2cc1285SJeff Roberson if (!pctrie_isleaf(root)) 671f2cc1285SJeff Roberson pctrie_reclaim_allnodes_int(ptree, root, freefn); 672f2cc1285SJeff Roberson } 673f2cc1285SJeff Roberson 674f2cc1285SJeff Roberson #ifdef DDB 675f2cc1285SJeff Roberson /* 676f2cc1285SJeff Roberson * Show details about the given node. 677f2cc1285SJeff Roberson */ 678f2cc1285SJeff Roberson DB_SHOW_COMMAND(pctrienode, db_show_pctrienode) 679f2cc1285SJeff Roberson { 680f2cc1285SJeff Roberson struct pctrie_node *node; 681f2cc1285SJeff Roberson int i; 682f2cc1285SJeff Roberson 683f2cc1285SJeff Roberson if (!have_addr) 684f2cc1285SJeff Roberson return; 685f2cc1285SJeff Roberson node = (struct pctrie_node *)addr; 686f2cc1285SJeff Roberson db_printf("node %p, owner %jx, children count %u, level %u:\n", 687f2cc1285SJeff Roberson (void *)node, (uintmax_t)node->pn_owner, node->pn_count, 688f2cc1285SJeff Roberson node->pn_clev); 689f2cc1285SJeff Roberson for (i = 0; i < PCTRIE_COUNT; i++) 690f2cc1285SJeff Roberson if (node->pn_child[i] != NULL) 691f2cc1285SJeff Roberson db_printf("slot: %d, val: %p, value: %p, clev: %d\n", 692f2cc1285SJeff Roberson i, (void *)node->pn_child[i], 693f2cc1285SJeff Roberson pctrie_isleaf(node->pn_child[i]) ? 694f2cc1285SJeff Roberson pctrie_toval(node->pn_child[i]) : NULL, 695f2cc1285SJeff Roberson node->pn_clev); 696f2cc1285SJeff Roberson } 697f2cc1285SJeff Roberson #endif /* DDB */ 698