1*8a36da99SPedro F. Giffuni /*- 2*8a36da99SPedro F. Giffuni * SPDX-License-Identifier: BSD-2-Clause-FreeBSD 3*8a36da99SPedro 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 */ 169f2cc1285SJeff Roberson static __inline boolean_t 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 */ 221f2cc1285SJeff Roberson static __inline boolean_t 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 } 229f2cc1285SJeff Roberson 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 388f2cc1285SJeff Roberson int slot, tos; 389f2cc1285SJeff Roberson 390f2cc1285SJeff Roberson node = pctrie_getroot(ptree); 391f2cc1285SJeff Roberson if (node == NULL) 392f2cc1285SJeff Roberson return (NULL); 393f2cc1285SJeff Roberson else if (pctrie_isleaf(node)) { 394f2cc1285SJeff Roberson m = pctrie_toval(node); 395f2cc1285SJeff Roberson if (*m >= index) 396f2cc1285SJeff Roberson return (m); 397f2cc1285SJeff Roberson else 398f2cc1285SJeff Roberson return (NULL); 399f2cc1285SJeff Roberson } 400f2cc1285SJeff Roberson tos = 0; 401f2cc1285SJeff Roberson for (;;) { 402f2cc1285SJeff Roberson /* 403f2cc1285SJeff Roberson * If the keys differ before the current bisection node, 404f2cc1285SJeff Roberson * then the search key might rollback to the earliest 405f2cc1285SJeff Roberson * available bisection node or to the smallest key 406f2cc1285SJeff Roberson * in the current node (if the owner is bigger than the 407f2cc1285SJeff Roberson * search key). 408f2cc1285SJeff Roberson */ 409f2cc1285SJeff Roberson if (pctrie_keybarr(node, index)) { 410f2cc1285SJeff Roberson if (index > node->pn_owner) { 411f2cc1285SJeff Roberson ascend: 412f2cc1285SJeff Roberson KASSERT(++loops < 1000, 413f2cc1285SJeff Roberson ("pctrie_lookup_ge: too many loops")); 414f2cc1285SJeff Roberson 415f2cc1285SJeff Roberson /* 416f2cc1285SJeff Roberson * Pop nodes from the stack until either the 417f2cc1285SJeff Roberson * stack is empty or a node that could have a 418f2cc1285SJeff Roberson * matching descendant is found. 419f2cc1285SJeff Roberson */ 420f2cc1285SJeff Roberson do { 421f2cc1285SJeff Roberson if (tos == 0) 422f2cc1285SJeff Roberson return (NULL); 423f2cc1285SJeff Roberson node = stack[--tos]; 424f2cc1285SJeff Roberson } while (pctrie_slot(index, 425f2cc1285SJeff Roberson node->pn_clev) == (PCTRIE_COUNT - 1)); 426f2cc1285SJeff Roberson 427f2cc1285SJeff Roberson /* 428f2cc1285SJeff Roberson * The following computation cannot overflow 429f2cc1285SJeff Roberson * because index's slot at the current level 430f2cc1285SJeff Roberson * is less than PCTRIE_COUNT - 1. 431f2cc1285SJeff Roberson */ 432f2cc1285SJeff Roberson index = pctrie_trimkey(index, 433f2cc1285SJeff Roberson node->pn_clev); 434f2cc1285SJeff Roberson index += PCTRIE_UNITLEVEL(node->pn_clev); 435f2cc1285SJeff Roberson } else 436f2cc1285SJeff Roberson index = node->pn_owner; 437f2cc1285SJeff Roberson KASSERT(!pctrie_keybarr(node, index), 438f2cc1285SJeff Roberson ("pctrie_lookup_ge: keybarr failed")); 439f2cc1285SJeff Roberson } 440f2cc1285SJeff Roberson slot = pctrie_slot(index, node->pn_clev); 441f2cc1285SJeff Roberson child = node->pn_child[slot]; 442f2cc1285SJeff Roberson if (pctrie_isleaf(child)) { 443f2cc1285SJeff Roberson m = pctrie_toval(child); 444f2cc1285SJeff Roberson if (*m >= index) 445f2cc1285SJeff Roberson return (m); 446f2cc1285SJeff Roberson } else if (child != NULL) 447f2cc1285SJeff Roberson goto descend; 448f2cc1285SJeff Roberson 449f2cc1285SJeff Roberson /* 450f2cc1285SJeff Roberson * Look for an available edge or val within the current 451f2cc1285SJeff Roberson * bisection node. 452f2cc1285SJeff Roberson */ 453f2cc1285SJeff Roberson if (slot < (PCTRIE_COUNT - 1)) { 454f2cc1285SJeff Roberson inc = PCTRIE_UNITLEVEL(node->pn_clev); 455f2cc1285SJeff Roberson index = pctrie_trimkey(index, node->pn_clev); 456f2cc1285SJeff Roberson do { 457f2cc1285SJeff Roberson index += inc; 458f2cc1285SJeff Roberson slot++; 459f2cc1285SJeff Roberson child = node->pn_child[slot]; 460f2cc1285SJeff Roberson if (pctrie_isleaf(child)) { 461f2cc1285SJeff Roberson m = pctrie_toval(child); 462f2cc1285SJeff Roberson if (*m >= index) 463f2cc1285SJeff Roberson return (m); 464f2cc1285SJeff Roberson } else if (child != NULL) 465f2cc1285SJeff Roberson goto descend; 466f2cc1285SJeff Roberson } while (slot < (PCTRIE_COUNT - 1)); 467f2cc1285SJeff Roberson } 468f2cc1285SJeff Roberson KASSERT(child == NULL || pctrie_isleaf(child), 469f2cc1285SJeff Roberson ("pctrie_lookup_ge: child is radix node")); 470f2cc1285SJeff Roberson 471f2cc1285SJeff Roberson /* 472f2cc1285SJeff Roberson * If a value or edge bigger than the search slot is not found 473f2cc1285SJeff Roberson * in the current node, ascend to the next higher-level node. 474f2cc1285SJeff Roberson */ 475f2cc1285SJeff Roberson goto ascend; 476f2cc1285SJeff Roberson descend: 477f2cc1285SJeff Roberson KASSERT(node->pn_clev > 0, 478f2cc1285SJeff Roberson ("pctrie_lookup_ge: pushing leaf's parent")); 479f2cc1285SJeff Roberson KASSERT(tos < PCTRIE_LIMIT, 480f2cc1285SJeff Roberson ("pctrie_lookup_ge: stack overflow")); 481f2cc1285SJeff Roberson stack[tos++] = node; 482f2cc1285SJeff Roberson node = child; 483f2cc1285SJeff Roberson } 484f2cc1285SJeff Roberson } 485f2cc1285SJeff Roberson 486f2cc1285SJeff Roberson /* 487f2cc1285SJeff Roberson * Look up the nearest entry at a position less than or equal to index. 488f2cc1285SJeff Roberson */ 489f2cc1285SJeff Roberson uint64_t * 490f2cc1285SJeff Roberson pctrie_lookup_le(struct pctrie *ptree, uint64_t index) 491f2cc1285SJeff Roberson { 492f2cc1285SJeff Roberson struct pctrie_node *stack[PCTRIE_LIMIT]; 493f2cc1285SJeff Roberson uint64_t inc; 494f2cc1285SJeff Roberson uint64_t *m; 495f2cc1285SJeff Roberson struct pctrie_node *child, *node; 496f2cc1285SJeff Roberson #ifdef INVARIANTS 497f2cc1285SJeff Roberson int loops = 0; 498f2cc1285SJeff Roberson #endif 499f2cc1285SJeff Roberson int slot, tos; 500f2cc1285SJeff Roberson 501f2cc1285SJeff Roberson node = pctrie_getroot(ptree); 502f2cc1285SJeff Roberson if (node == NULL) 503f2cc1285SJeff Roberson return (NULL); 504f2cc1285SJeff Roberson else if (pctrie_isleaf(node)) { 505f2cc1285SJeff Roberson m = pctrie_toval(node); 506f2cc1285SJeff Roberson if (*m <= index) 507f2cc1285SJeff Roberson return (m); 508f2cc1285SJeff Roberson else 509f2cc1285SJeff Roberson return (NULL); 510f2cc1285SJeff Roberson } 511f2cc1285SJeff Roberson tos = 0; 512f2cc1285SJeff Roberson for (;;) { 513f2cc1285SJeff Roberson /* 514f2cc1285SJeff Roberson * If the keys differ before the current bisection node, 515f2cc1285SJeff Roberson * then the search key might rollback to the earliest 516f2cc1285SJeff Roberson * available bisection node or to the largest key 517f2cc1285SJeff Roberson * in the current node (if the owner is smaller than the 518f2cc1285SJeff Roberson * search key). 519f2cc1285SJeff Roberson */ 520f2cc1285SJeff Roberson if (pctrie_keybarr(node, index)) { 521f2cc1285SJeff Roberson if (index > node->pn_owner) { 522f2cc1285SJeff Roberson index = node->pn_owner + PCTRIE_COUNT * 523f2cc1285SJeff Roberson PCTRIE_UNITLEVEL(node->pn_clev); 524f2cc1285SJeff Roberson } else { 525f2cc1285SJeff Roberson ascend: 526f2cc1285SJeff Roberson KASSERT(++loops < 1000, 527f2cc1285SJeff Roberson ("pctrie_lookup_le: too many loops")); 528f2cc1285SJeff Roberson 529f2cc1285SJeff Roberson /* 530f2cc1285SJeff Roberson * Pop nodes from the stack until either the 531f2cc1285SJeff Roberson * stack is empty or a node that could have a 532f2cc1285SJeff Roberson * matching descendant is found. 533f2cc1285SJeff Roberson */ 534f2cc1285SJeff Roberson do { 535f2cc1285SJeff Roberson if (tos == 0) 536f2cc1285SJeff Roberson return (NULL); 537f2cc1285SJeff Roberson node = stack[--tos]; 538f2cc1285SJeff Roberson } while (pctrie_slot(index, 539f2cc1285SJeff Roberson node->pn_clev) == 0); 540f2cc1285SJeff Roberson 541f2cc1285SJeff Roberson /* 542f2cc1285SJeff Roberson * The following computation cannot overflow 543f2cc1285SJeff Roberson * because index's slot at the current level 544f2cc1285SJeff Roberson * is greater than 0. 545f2cc1285SJeff Roberson */ 546f2cc1285SJeff Roberson index = pctrie_trimkey(index, 547f2cc1285SJeff Roberson node->pn_clev); 548f2cc1285SJeff Roberson } 549f2cc1285SJeff Roberson index--; 550f2cc1285SJeff Roberson KASSERT(!pctrie_keybarr(node, index), 551f2cc1285SJeff Roberson ("pctrie_lookup_le: keybarr failed")); 552f2cc1285SJeff Roberson } 553f2cc1285SJeff Roberson slot = pctrie_slot(index, node->pn_clev); 554f2cc1285SJeff Roberson child = node->pn_child[slot]; 555f2cc1285SJeff Roberson if (pctrie_isleaf(child)) { 556f2cc1285SJeff Roberson m = pctrie_toval(child); 557f2cc1285SJeff Roberson if (*m <= index) 558f2cc1285SJeff Roberson return (m); 559f2cc1285SJeff Roberson } else if (child != NULL) 560f2cc1285SJeff Roberson goto descend; 561f2cc1285SJeff Roberson 562f2cc1285SJeff Roberson /* 563f2cc1285SJeff Roberson * Look for an available edge or value within the current 564f2cc1285SJeff Roberson * bisection node. 565f2cc1285SJeff Roberson */ 566f2cc1285SJeff Roberson if (slot > 0) { 567f2cc1285SJeff Roberson inc = PCTRIE_UNITLEVEL(node->pn_clev); 568f2cc1285SJeff Roberson index |= inc - 1; 569f2cc1285SJeff Roberson do { 570f2cc1285SJeff Roberson index -= inc; 571f2cc1285SJeff Roberson slot--; 572f2cc1285SJeff Roberson child = node->pn_child[slot]; 573f2cc1285SJeff Roberson if (pctrie_isleaf(child)) { 574f2cc1285SJeff Roberson m = pctrie_toval(child); 575f2cc1285SJeff Roberson if (*m <= index) 576f2cc1285SJeff Roberson return (m); 577f2cc1285SJeff Roberson } else if (child != NULL) 578f2cc1285SJeff Roberson goto descend; 579f2cc1285SJeff Roberson } while (slot > 0); 580f2cc1285SJeff Roberson } 581f2cc1285SJeff Roberson KASSERT(child == NULL || pctrie_isleaf(child), 582f2cc1285SJeff Roberson ("pctrie_lookup_le: child is radix node")); 583f2cc1285SJeff Roberson 584f2cc1285SJeff Roberson /* 585f2cc1285SJeff Roberson * If a value or edge smaller than the search slot is not found 586f2cc1285SJeff Roberson * in the current node, ascend to the next higher-level node. 587f2cc1285SJeff Roberson */ 588f2cc1285SJeff Roberson goto ascend; 589f2cc1285SJeff Roberson descend: 590f2cc1285SJeff Roberson KASSERT(node->pn_clev > 0, 591f2cc1285SJeff Roberson ("pctrie_lookup_le: pushing leaf's parent")); 592f2cc1285SJeff Roberson KASSERT(tos < PCTRIE_LIMIT, 593f2cc1285SJeff Roberson ("pctrie_lookup_le: stack overflow")); 594f2cc1285SJeff Roberson stack[tos++] = node; 595f2cc1285SJeff Roberson node = child; 596f2cc1285SJeff Roberson } 597f2cc1285SJeff Roberson } 598f2cc1285SJeff Roberson 599f2cc1285SJeff Roberson /* 600f2cc1285SJeff Roberson * Remove the specified index from the tree. 601f2cc1285SJeff Roberson * Panics if the key is not present. 602f2cc1285SJeff Roberson */ 603f2cc1285SJeff Roberson void 604f2cc1285SJeff Roberson pctrie_remove(struct pctrie *ptree, uint64_t index, pctrie_free_t freefn) 605f2cc1285SJeff Roberson { 606f2cc1285SJeff Roberson struct pctrie_node *node, *parent; 607f2cc1285SJeff Roberson uint64_t *m; 608f2cc1285SJeff Roberson int i, slot; 609f2cc1285SJeff Roberson 610f2cc1285SJeff Roberson node = pctrie_getroot(ptree); 611f2cc1285SJeff Roberson if (pctrie_isleaf(node)) { 612f2cc1285SJeff Roberson m = pctrie_toval(node); 613f2cc1285SJeff Roberson if (*m != index) 614f2cc1285SJeff Roberson panic("%s: invalid key found", __func__); 615f2cc1285SJeff Roberson pctrie_setroot(ptree, NULL); 616f2cc1285SJeff Roberson return; 617f2cc1285SJeff Roberson } 618f2cc1285SJeff Roberson parent = NULL; 619f2cc1285SJeff Roberson for (;;) { 620f2cc1285SJeff Roberson if (node == NULL) 621f2cc1285SJeff Roberson panic("pctrie_remove: impossible to locate the key"); 622f2cc1285SJeff Roberson slot = pctrie_slot(index, node->pn_clev); 623f2cc1285SJeff Roberson if (pctrie_isleaf(node->pn_child[slot])) { 624f2cc1285SJeff Roberson m = pctrie_toval(node->pn_child[slot]); 625f2cc1285SJeff Roberson if (*m != index) 626f2cc1285SJeff Roberson panic("%s: invalid key found", __func__); 627f2cc1285SJeff Roberson node->pn_child[slot] = NULL; 628f2cc1285SJeff Roberson node->pn_count--; 629f2cc1285SJeff Roberson if (node->pn_count > 1) 630f2cc1285SJeff Roberson break; 631f2cc1285SJeff Roberson for (i = 0; i < PCTRIE_COUNT; i++) 632f2cc1285SJeff Roberson if (node->pn_child[i] != NULL) 633f2cc1285SJeff Roberson break; 634f2cc1285SJeff Roberson KASSERT(i != PCTRIE_COUNT, 635f2cc1285SJeff Roberson ("%s: invalid node configuration", __func__)); 636f2cc1285SJeff Roberson if (parent == NULL) 637f2cc1285SJeff Roberson pctrie_setroot(ptree, node->pn_child[i]); 638f2cc1285SJeff Roberson else { 639f2cc1285SJeff Roberson slot = pctrie_slot(index, parent->pn_clev); 640f2cc1285SJeff Roberson KASSERT(parent->pn_child[slot] == node, 641f2cc1285SJeff Roberson ("%s: invalid child value", __func__)); 642f2cc1285SJeff Roberson parent->pn_child[slot] = node->pn_child[i]; 643f2cc1285SJeff Roberson } 644f2cc1285SJeff Roberson node->pn_count--; 645f2cc1285SJeff Roberson node->pn_child[i] = NULL; 646f2cc1285SJeff Roberson pctrie_node_put(ptree, node, freefn); 647f2cc1285SJeff Roberson break; 648f2cc1285SJeff Roberson } 649f2cc1285SJeff Roberson parent = node; 650f2cc1285SJeff Roberson node = node->pn_child[slot]; 651f2cc1285SJeff Roberson } 652f2cc1285SJeff Roberson } 653f2cc1285SJeff Roberson 654f2cc1285SJeff Roberson /* 655f2cc1285SJeff Roberson * Remove and free all the nodes from the tree. 656f2cc1285SJeff Roberson * This function is recursive but there is a tight control on it as the 657f2cc1285SJeff Roberson * maximum depth of the tree is fixed. 658f2cc1285SJeff Roberson */ 659f2cc1285SJeff Roberson void 660f2cc1285SJeff Roberson pctrie_reclaim_allnodes(struct pctrie *ptree, pctrie_free_t freefn) 661f2cc1285SJeff Roberson { 662f2cc1285SJeff Roberson struct pctrie_node *root; 663f2cc1285SJeff Roberson 664f2cc1285SJeff Roberson root = pctrie_getroot(ptree); 665f2cc1285SJeff Roberson if (root == NULL) 666f2cc1285SJeff Roberson return; 667f2cc1285SJeff Roberson pctrie_setroot(ptree, NULL); 668f2cc1285SJeff Roberson if (!pctrie_isleaf(root)) 669f2cc1285SJeff Roberson pctrie_reclaim_allnodes_int(ptree, root, freefn); 670f2cc1285SJeff Roberson } 671f2cc1285SJeff Roberson 672f2cc1285SJeff Roberson #ifdef DDB 673f2cc1285SJeff Roberson /* 674f2cc1285SJeff Roberson * Show details about the given node. 675f2cc1285SJeff Roberson */ 676f2cc1285SJeff Roberson DB_SHOW_COMMAND(pctrienode, db_show_pctrienode) 677f2cc1285SJeff Roberson { 678f2cc1285SJeff Roberson struct pctrie_node *node; 679f2cc1285SJeff Roberson int i; 680f2cc1285SJeff Roberson 681f2cc1285SJeff Roberson if (!have_addr) 682f2cc1285SJeff Roberson return; 683f2cc1285SJeff Roberson node = (struct pctrie_node *)addr; 684f2cc1285SJeff Roberson db_printf("node %p, owner %jx, children count %u, level %u:\n", 685f2cc1285SJeff Roberson (void *)node, (uintmax_t)node->pn_owner, node->pn_count, 686f2cc1285SJeff Roberson node->pn_clev); 687f2cc1285SJeff Roberson for (i = 0; i < PCTRIE_COUNT; i++) 688f2cc1285SJeff Roberson if (node->pn_child[i] != NULL) 689f2cc1285SJeff Roberson db_printf("slot: %d, val: %p, value: %p, clev: %d\n", 690f2cc1285SJeff Roberson i, (void *)node->pn_child[i], 691f2cc1285SJeff Roberson pctrie_isleaf(node->pn_child[i]) ? 692f2cc1285SJeff Roberson pctrie_toval(node->pn_child[i]) : NULL, 693f2cc1285SJeff Roberson node->pn_clev); 694f2cc1285SJeff Roberson } 695f2cc1285SJeff Roberson #endif /* DDB */ 696