1226645Sattilio/* 2246726Sattilio * Copyright (c) 2013 EMC Corp. 3226930Sjeff * Copyright (c) 2011 Jeffrey Roberson <jeff@freebsd.org> 4226645Sattilio * Copyright (c) 2008 Mayur Shardul <mayur.shardul@gmail.com> 5226645Sattilio * All rights reserved. 6226645Sattilio * 7226645Sattilio * Redistribution and use in source and binary forms, with or without 8226645Sattilio * modification, are permitted provided that the following conditions 9226645Sattilio * are met: 10226645Sattilio * 1. Redistributions of source code must retain the above copyright 11226645Sattilio * notice, this list of conditions and the following disclaimer. 12226645Sattilio * 2. Redistributions in binary form must reproduce the above copyright 13226645Sattilio * notice, this list of conditions and the following disclaimer in the 14226645Sattilio * documentation and/or other materials provided with the distribution. 15226645Sattilio * 16226645Sattilio * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND 17226645Sattilio * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 18226645Sattilio * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 19226645Sattilio * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE 20226645Sattilio * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 21226645Sattilio * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 22226645Sattilio * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 23226645Sattilio * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 24226645Sattilio * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 25226645Sattilio * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 26226645Sattilio * SUCH DAMAGE. 27226645Sattilio * 28226645Sattilio */ 29226645Sattilio 30226645Sattilio/* 31246726Sattilio * Path-compressed radix trie implementation. 32246726Sattilio * The following code is not generalized into a general purpose library 33246726Sattilio * because there are way too many parameters embedded that should really 34246726Sattilio * be decided by the library consumers. At the same time, consumers 35246726Sattilio * of this code must achieve highest possible performance. 36246726Sattilio * 37246726Sattilio * The implementation takes into account the following rationale: 38248424Sattilio * - Size of the nodes should be as small as possible but still big enough 39248424Sattilio * to avoid a large maximum depth for the trie. This is a balance 40248424Sattilio * between the necessity to not wire too much physical memory for the nodes 41248424Sattilio * and the necessity to avoid too much cache pollution during the trie 42248424Sattilio * operations. 43248424Sattilio * - There is not a huge bias toward the number of lookup operations over 44248424Sattilio * the number of insert and remove operations. This basically implies 45248424Sattilio * that optimizations supposedly helping one operation but hurting the 46248424Sattilio * other might be carefully evaluated. 47248424Sattilio * - On average not many nodes are expected to be fully populated, hence 48248424Sattilio * level compression may just complicate things. 49226645Sattilio */ 50226645Sattilio 51226645Sattilio#include <sys/cdefs.h> 52248448Sattilio__FBSDID("$FreeBSD$"); 53226645Sattilio 54246726Sattilio#include "opt_ddb.h" 55246726Sattilio 56226645Sattilio#include <sys/param.h> 57226645Sattilio#include <sys/systm.h> 58226645Sattilio#include <sys/kernel.h> 59246840Sattilio#include <sys/vmmeter.h> 60246726Sattilio 61226873Sattilio#include <vm/uma.h> 62226645Sattilio#include <vm/vm.h> 63226876Sjeff#include <vm/vm_param.h> 64226873Sattilio#include <vm/vm_page.h> 65226645Sattilio#include <vm/vm_radix.h> 66226645Sattilio 67246726Sattilio#ifdef DDB 68246726Sattilio#include <ddb/ddb.h> 69246726Sattilio#endif 70226645Sattilio 71233034Sattilio/* 72247771Salc * These widths should allow the pointers to a node's children to fit within 73247771Salc * a single cache line. The extra levels from a narrow width should not be 74247771Salc * a problem thanks to path compression. 75233034Sattilio */ 76246726Sattilio#ifdef __LP64__ 77246726Sattilio#define VM_RADIX_WIDTH 4 78233034Sattilio#else 79246726Sattilio#define VM_RADIX_WIDTH 3 80233034Sattilio#endif 81233034Sattilio 82232326Sattilio#define VM_RADIX_COUNT (1 << VM_RADIX_WIDTH) 83232326Sattilio#define VM_RADIX_MASK (VM_RADIX_COUNT - 1) 84246726Sattilio#define VM_RADIX_LIMIT \ 85246726Sattilio (howmany((sizeof(vm_pindex_t) * NBBY), VM_RADIX_WIDTH) - 1) 86232326Sattilio 87232326Sattilio/* Flag bits stored in node pointers. */ 88246726Sattilio#define VM_RADIX_ISLEAF 0x1 89246726Sattilio#define VM_RADIX_FLAGS 0x1 90246726Sattilio#define VM_RADIX_PAD VM_RADIX_FLAGS 91232326Sattilio 92246726Sattilio/* Returns one unit associated with specified level. */ 93246726Sattilio#define VM_RADIX_UNITLEVEL(lev) \ 94250520Salc ((vm_pindex_t)1 << ((lev) * VM_RADIX_WIDTH)) 95232326Sattilio 96232326Sattiliostruct vm_radix_node { 97246726Sattilio vm_pindex_t rn_owner; /* Owner of record. */ 98246726Sattilio uint16_t rn_count; /* Valid children. */ 99246726Sattilio uint16_t rn_clev; /* Current level. */ 100249221Salc void *rn_child[VM_RADIX_COUNT]; /* Child nodes. */ 101232326Sattilio}; 102232326Sattilio 103226873Sattiliostatic uma_zone_t vm_radix_node_zone; 104226645Sattilio 105246794Sattilio/* 106254141Sattilio * Allocate a radix node. 107246726Sattilio */ 108246726Sattiliostatic __inline struct vm_radix_node * 109246726Sattiliovm_radix_node_get(vm_pindex_t owner, uint16_t count, uint16_t clevel) 110226873Sattilio{ 111246726Sattilio struct vm_radix_node *rnode; 112226645Sattilio 113254141Sattilio rnode = uma_zalloc(vm_radix_node_zone, M_NOWAIT | M_ZERO); 114247742Sattilio if (rnode == NULL) 115254141Sattilio return (NULL); 116246726Sattilio rnode->rn_owner = owner; 117246726Sattilio rnode->rn_count = count; 118246726Sattilio rnode->rn_clev = clevel; 119246726Sattilio return (rnode); 120246726Sattilio} 121226873Sattilio 122246726Sattilio/* 123246726Sattilio * Free radix node. 124246726Sattilio */ 125246726Sattiliostatic __inline void 126246726Sattiliovm_radix_node_put(struct vm_radix_node *rnode) 127246726Sattilio{ 128246726Sattilio 129246726Sattilio uma_zfree(vm_radix_node_zone, rnode); 130226873Sattilio} 131226873Sattilio 132246726Sattilio/* 133246726Sattilio * Return the position in the array for a given level. 134246726Sattilio */ 135246726Sattiliostatic __inline int 136246726Sattiliovm_radix_slot(vm_pindex_t index, uint16_t level) 137226873Sattilio{ 138226873Sattilio 139250520Salc return ((index >> (level * VM_RADIX_WIDTH)) & VM_RADIX_MASK); 140226873Sattilio} 141226873Sattilio 142246726Sattilio/* Trims the key after the specified level. */ 143246726Sattiliostatic __inline vm_pindex_t 144246726Sattiliovm_radix_trimkey(vm_pindex_t index, uint16_t level) 145226873Sattilio{ 146246726Sattilio vm_pindex_t ret; 147226873Sattilio 148246726Sattilio ret = index; 149250520Salc if (level > 0) { 150250520Salc ret >>= level * VM_RADIX_WIDTH; 151250520Salc ret <<= level * VM_RADIX_WIDTH; 152246726Sattilio } 153246726Sattilio return (ret); 154226873Sattilio} 155226873Sattilio 156226645Sattilio/* 157246726Sattilio * Get the root node for a radix tree. 158226873Sattilio */ 159246726Sattiliostatic __inline struct vm_radix_node * 160246726Sattiliovm_radix_getroot(struct vm_radix *rtree) 161226873Sattilio{ 162226873Sattilio 163249221Salc return ((struct vm_radix_node *)rtree->rt_root); 164226873Sattilio} 165226873Sattilio 166226873Sattilio/* 167246726Sattilio * Set the root node for a radix tree. 168226645Sattilio */ 169246726Sattiliostatic __inline void 170246726Sattiliovm_radix_setroot(struct vm_radix *rtree, struct vm_radix_node *rnode) 171226645Sattilio{ 172226645Sattilio 173246726Sattilio rtree->rt_root = (uintptr_t)rnode; 174226645Sattilio} 175226645Sattilio 176226645Sattilio/* 177248728Salc * Returns TRUE if the specified radix node is a leaf and FALSE otherwise. 178248728Salc */ 179248728Salcstatic __inline boolean_t 180248728Salcvm_radix_isleaf(struct vm_radix_node *rnode) 181248728Salc{ 182248728Salc 183248728Salc return (((uintptr_t)rnode & VM_RADIX_ISLEAF) != 0); 184248728Salc} 185248728Salc 186248728Salc/* 187249038Salc * Returns the associated page extracted from rnode. 188226645Sattilio */ 189246726Sattiliostatic __inline vm_page_t 190249038Salcvm_radix_topage(struct vm_radix_node *rnode) 191226645Sattilio{ 192226645Sattilio 193249038Salc return ((vm_page_t)((uintptr_t)rnode & ~VM_RADIX_FLAGS)); 194226645Sattilio} 195226645Sattilio 196226645Sattilio/* 197247771Salc * Adds the page as a child of the provided node. 198226645Sattilio */ 199246726Sattiliostatic __inline void 200246726Sattiliovm_radix_addpage(struct vm_radix_node *rnode, vm_pindex_t index, uint16_t clev, 201246726Sattilio vm_page_t page) 202226645Sattilio{ 203246726Sattilio int slot; 204226645Sattilio 205246726Sattilio slot = vm_radix_slot(index, clev); 206246726Sattilio rnode->rn_child[slot] = (void *)((uintptr_t)page | VM_RADIX_ISLEAF); 207226645Sattilio} 208226645Sattilio 209233034Sattilio/* 210246726Sattilio * Returns the slot where two keys differ. 211246726Sattilio * It cannot accept 2 equal keys. 212233034Sattilio */ 213246726Sattiliostatic __inline uint16_t 214246726Sattiliovm_radix_keydiff(vm_pindex_t index1, vm_pindex_t index2) 215226873Sattilio{ 216246726Sattilio uint16_t clev; 217226873Sattilio 218246726Sattilio KASSERT(index1 != index2, ("%s: passing the same key value %jx", 219246726Sattilio __func__, (uintmax_t)index1)); 220233034Sattilio 221246726Sattilio index1 ^= index2; 222250520Salc for (clev = VM_RADIX_LIMIT;; clev--) 223250334Salc if (vm_radix_slot(index1, clev) != 0) 224246726Sattilio return (clev); 225226873Sattilio} 226226873Sattilio 227226645Sattilio/* 228246726Sattilio * Returns TRUE if it can be determined that key does not belong to the 229247771Salc * specified rnode. Otherwise, returns FALSE. 230226876Sjeff */ 231246726Sattiliostatic __inline boolean_t 232246726Sattiliovm_radix_keybarr(struct vm_radix_node *rnode, vm_pindex_t idx) 233226876Sjeff{ 234226876Sjeff 235250520Salc if (rnode->rn_clev < VM_RADIX_LIMIT) { 236250520Salc idx = vm_radix_trimkey(idx, rnode->rn_clev + 1); 237249211Salc return (idx != rnode->rn_owner); 238246726Sattilio } 239246726Sattilio return (FALSE); 240226876Sjeff} 241226876Sjeff 242226876Sjeff/* 243247773Salc * Internal helper for vm_radix_reclaim_allnodes(). 244247769Salc * This function is recursive. 245246726Sattilio */ 246226980Sattiliostatic void 247246726Sattiliovm_radix_reclaim_allnodes_int(struct vm_radix_node *rnode) 248226980Sattilio{ 249226980Sattilio int slot; 250226980Sattilio 251248684Salc KASSERT(rnode->rn_count <= VM_RADIX_COUNT, 252248684Salc ("vm_radix_reclaim_allnodes_int: bad count in rnode %p", rnode)); 253248684Salc for (slot = 0; rnode->rn_count != 0; slot++) { 254226980Sattilio if (rnode->rn_child[slot] == NULL) 255226980Sattilio continue; 256248728Salc if (!vm_radix_isleaf(rnode->rn_child[slot])) 257246726Sattilio vm_radix_reclaim_allnodes_int(rnode->rn_child[slot]); 258248431Salc rnode->rn_child[slot] = NULL; 259226980Sattilio rnode->rn_count--; 260226980Sattilio } 261226980Sattilio vm_radix_node_put(rnode); 262226980Sattilio} 263226980Sattilio 264246836Sattilio#ifdef INVARIANTS 265226876Sjeff/* 266246836Sattilio * Radix node zone destructor. 267246836Sattilio */ 268246836Sattiliostatic void 269246836Sattiliovm_radix_node_zone_dtor(void *mem, int size __unused, void *arg __unused) 270246836Sattilio{ 271246836Sattilio struct vm_radix_node *rnode; 272248431Salc int slot; 273246836Sattilio 274246836Sattilio rnode = mem; 275246836Sattilio KASSERT(rnode->rn_count == 0, 276248431Salc ("vm_radix_node_put: rnode %p has %d children", rnode, 277246836Sattilio rnode->rn_count)); 278248431Salc for (slot = 0; slot < VM_RADIX_COUNT; slot++) 279248431Salc KASSERT(rnode->rn_child[slot] == NULL, 280248431Salc ("vm_radix_node_put: rnode %p has a child", rnode)); 281246836Sattilio} 282246836Sattilio#endif 283246836Sattilio 284254141Sattilio#ifndef UMA_MD_SMALL_ALLOC 285246836Sattilio/* 286254141Sattilio * Reserve the KVA necessary to satisfy the node allocation. 287254141Sattilio * This is mandatory in architectures not supporting direct 288254141Sattilio * mapping as they will need otherwise to carve into the kernel maps for 289254141Sattilio * every node allocation, resulting into deadlocks for consumers already 290254141Sattilio * working with kernel maps. 291248431Salc */ 292246794Sattiliostatic void 293254141Sattiliovm_radix_reserve_kva(void *arg __unused) 294246726Sattilio{ 295246726Sattilio 296249605Salc /* 297249605Salc * Calculate the number of reserved nodes, discounting the pages that 298249605Salc * are needed to store them. 299249605Salc */ 300254141Sattilio if (!uma_zone_reserve_kva(vm_radix_node_zone, 301254141Sattilio ((vm_paddr_t)cnt.v_page_count * PAGE_SIZE) / (PAGE_SIZE + 302254141Sattilio sizeof(struct vm_radix_node)))) 303254141Sattilio panic("%s: unable to reserve KVA", __func__); 304247742Sattilio} 305254141SattilioSYSINIT(vm_radix_reserve_kva, SI_SUB_KMEM, SI_ORDER_SECOND, 306254141Sattilio vm_radix_reserve_kva, NULL); 307254141Sattilio#endif 308247742Sattilio 309247742Sattilio/* 310247742Sattilio * Initialize the UMA slab zone. 311247742Sattilio * Until vm_radix_prealloc() is called, the zone will be served by the 312247742Sattilio * UMA boot-time pre-allocated pool of pages. 313247742Sattilio */ 314247742Sattiliovoid 315247742Sattiliovm_radix_init(void) 316247742Sattilio{ 317247742Sattilio 318246726Sattilio vm_radix_node_zone = uma_zcreate("RADIX NODE", 319246726Sattilio sizeof(struct vm_radix_node), NULL, 320246726Sattilio#ifdef INVARIANTS 321246726Sattilio vm_radix_node_zone_dtor, 322246726Sattilio#else 323246726Sattilio NULL, 324246726Sattilio#endif 325254141Sattilio NULL, NULL, VM_RADIX_PAD, UMA_ZONE_VM); 326246726Sattilio} 327246726Sattilio 328246726Sattilio/* 329247771Salc * Inserts the key-value pair into the trie. 330226645Sattilio * Panics if the key already exists. 331226645Sattilio */ 332254141Sattilioint 333248428Salcvm_radix_insert(struct vm_radix *rtree, vm_page_t page) 334226645Sattilio{ 335248428Salc vm_pindex_t index, newind; 336249502Salc void **parentp; 337249502Salc struct vm_radix_node *rnode, *tmp; 338246726Sattilio vm_page_t m; 339236763Sattilio int slot; 340246726Sattilio uint16_t clev; 341226645Sattilio 342248428Salc index = page->pindex; 343248222Sattilio 344254141Sattiliorestart: 345254141Sattilio 346226645Sattilio /* 347246726Sattilio * The owner of record for root is not really important because it 348246726Sattilio * will never be used. 349226645Sattilio */ 350246726Sattilio rnode = vm_radix_getroot(rtree); 351246726Sattilio if (rnode == NULL) { 352249502Salc rtree->rt_root = (uintptr_t)page | VM_RADIX_ISLEAF; 353254141Sattilio return (0); 354246726Sattilio } 355249502Salc parentp = (void **)&rtree->rt_root; 356249502Salc for (;;) { 357249502Salc if (vm_radix_isleaf(rnode)) { 358249502Salc m = vm_radix_topage(rnode); 359246726Sattilio if (m->pindex == index) 360246726Sattilio panic("%s: key %jx is already present", 361246726Sattilio __func__, (uintmax_t)index); 362246726Sattilio clev = vm_radix_keydiff(m->pindex, index); 363254141Sattilio 364254141Sattilio /* 365254141Sattilio * During node allocation the trie that is being 366254141Sattilio * walked can be modified because of recursing radix 367254141Sattilio * trie operations. 368254141Sattilio * If this is the case, the recursing functions signal 369254141Sattilio * such situation and the insert operation must 370254141Sattilio * start from scratch again. 371254141Sattilio * The freed radix node will then be in the UMA 372254141Sattilio * caches very likely to avoid the same situation 373254141Sattilio * to happen. 374254141Sattilio */ 375254141Sattilio rtree->rt_flags |= RT_INSERT_INPROG; 376246726Sattilio tmp = vm_radix_node_get(vm_radix_trimkey(index, 377250520Salc clev + 1), 2, clev); 378254141Sattilio rtree->rt_flags &= ~RT_INSERT_INPROG; 379254141Sattilio if (tmp == NULL) { 380254141Sattilio rtree->rt_flags &= ~RT_TRIE_MODIFIED; 381254141Sattilio return (ENOMEM); 382254141Sattilio } 383254141Sattilio if ((rtree->rt_flags & RT_TRIE_MODIFIED) != 0) { 384254141Sattilio rtree->rt_flags &= ~RT_TRIE_MODIFIED; 385254141Sattilio tmp->rn_count = 0; 386254141Sattilio vm_radix_node_put(tmp); 387254141Sattilio goto restart; 388254141Sattilio } 389249502Salc *parentp = tmp; 390246726Sattilio vm_radix_addpage(tmp, index, clev, page); 391246726Sattilio vm_radix_addpage(tmp, m->pindex, clev, m); 392254141Sattilio return (0); 393249502Salc } else if (vm_radix_keybarr(rnode, index)) 394249502Salc break; 395249502Salc slot = vm_radix_slot(index, rnode->rn_clev); 396226645Sattilio if (rnode->rn_child[slot] == NULL) { 397236760Sattilio rnode->rn_count++; 398246726Sattilio vm_radix_addpage(rnode, index, rnode->rn_clev, page); 399254141Sattilio return (0); 400246726Sattilio } 401249502Salc parentp = &rnode->rn_child[slot]; 402226645Sattilio rnode = rnode->rn_child[slot]; 403249502Salc } 404226645Sattilio 405246726Sattilio /* 406246726Sattilio * A new node is needed because the right insertion level is reached. 407246726Sattilio * Setup the new intermediate node and add the 2 children: the 408246726Sattilio * new object and the older edge. 409246726Sattilio */ 410249182Salc newind = rnode->rn_owner; 411249182Salc clev = vm_radix_keydiff(newind, index); 412254141Sattilio 413254141Sattilio /* See the comments above. */ 414254141Sattilio rtree->rt_flags |= RT_INSERT_INPROG; 415254141Sattilio tmp = vm_radix_node_get(vm_radix_trimkey(index, clev + 1), 2, clev); 416254141Sattilio rtree->rt_flags &= ~RT_INSERT_INPROG; 417254141Sattilio if (tmp == NULL) { 418254141Sattilio rtree->rt_flags &= ~RT_TRIE_MODIFIED; 419254141Sattilio return (ENOMEM); 420254141Sattilio } 421254141Sattilio if ((rtree->rt_flags & RT_TRIE_MODIFIED) != 0) { 422254141Sattilio rtree->rt_flags &= ~RT_TRIE_MODIFIED; 423254141Sattilio tmp->rn_count = 0; 424254141Sattilio vm_radix_node_put(tmp); 425254141Sattilio goto restart; 426254141Sattilio } 427249502Salc *parentp = tmp; 428249182Salc vm_radix_addpage(tmp, index, clev, page); 429246726Sattilio slot = vm_radix_slot(newind, clev); 430249182Salc tmp->rn_child[slot] = rnode; 431254141Sattilio return (0); 432226645Sattilio} 433226645Sattilio 434226645Sattilio/* 435254719Salc * Returns TRUE if the specified radix tree contains a single leaf and FALSE 436254719Salc * otherwise. 437254719Salc */ 438254719Salcboolean_t 439254719Salcvm_radix_is_singleton(struct vm_radix *rtree) 440254719Salc{ 441254719Salc struct vm_radix_node *rnode; 442254719Salc 443254719Salc rnode = vm_radix_getroot(rtree); 444254719Salc if (rnode == NULL) 445254719Salc return (FALSE); 446254719Salc return (vm_radix_isleaf(rnode)); 447254719Salc} 448254719Salc 449254719Salc/* 450247771Salc * Returns the value stored at the index. If the index is not present, 451226645Sattilio * NULL is returned. 452226645Sattilio */ 453246430Sattiliovm_page_t 454238245Sattiliovm_radix_lookup(struct vm_radix *rtree, vm_pindex_t index) 455226645Sattilio{ 456226645Sattilio struct vm_radix_node *rnode; 457246726Sattilio vm_page_t m; 458226645Sattilio int slot; 459226645Sattilio 460246726Sattilio rnode = vm_radix_getroot(rtree); 461246795Sattilio while (rnode != NULL) { 462249038Salc if (vm_radix_isleaf(rnode)) { 463249038Salc m = vm_radix_topage(rnode); 464246726Sattilio if (m->pindex == index) 465246726Sattilio return (m); 466246726Sattilio else 467249427Salc break; 468249427Salc } else if (vm_radix_keybarr(rnode, index)) 469249427Salc break; 470249427Salc slot = vm_radix_slot(index, rnode->rn_clev); 471249427Salc rnode = rnode->rn_child[slot]; 472226645Sattilio } 473246726Sattilio return (NULL); 474226645Sattilio} 475226645Sattilio 476226645Sattilio/* 477247771Salc * Look up the nearest entry at a position bigger than or equal to index. 478226645Sattilio */ 479246726Sattiliovm_page_t 480246726Sattiliovm_radix_lookup_ge(struct vm_radix *rtree, vm_pindex_t index) 481226645Sattilio{ 482250259Salc struct vm_radix_node *stack[VM_RADIX_LIMIT]; 483246726Sattilio vm_pindex_t inc; 484246726Sattilio vm_page_t m; 485249038Salc struct vm_radix_node *child, *rnode; 486246726Sattilio#ifdef INVARIANTS 487246726Sattilio int loops = 0; 488246726Sattilio#endif 489250259Salc int slot, tos; 490226645Sattilio 491249427Salc rnode = vm_radix_getroot(rtree); 492249427Salc if (rnode == NULL) 493249427Salc return (NULL); 494249427Salc else if (vm_radix_isleaf(rnode)) { 495249427Salc m = vm_radix_topage(rnode); 496249427Salc if (m->pindex >= index) 497249427Salc return (m); 498249427Salc else 499249427Salc return (NULL); 500249427Salc } 501250259Salc tos = 0; 502249427Salc for (;;) { 503246726Sattilio /* 504249986Salc * If the keys differ before the current bisection node, 505249986Salc * then the search key might rollback to the earliest 506249986Salc * available bisection node or to the smallest key 507249986Salc * in the current node (if the owner is bigger than the 508246726Sattilio * search key). 509246726Sattilio */ 510247770Salc if (vm_radix_keybarr(rnode, index)) { 511246726Sattilio if (index > rnode->rn_owner) { 512250259Salcascend: 513250259Salc KASSERT(++loops < 1000, 514250259Salc ("vm_radix_lookup_ge: too many loops")); 515250259Salc 516250259Salc /* 517250259Salc * Pop nodes from the stack until either the 518250259Salc * stack is empty or a node that could have a 519250259Salc * matching descendant is found. 520250259Salc */ 521250259Salc do { 522250259Salc if (tos == 0) 523250259Salc return (NULL); 524250259Salc rnode = stack[--tos]; 525250259Salc } while (vm_radix_slot(index, 526250259Salc rnode->rn_clev) == (VM_RADIX_COUNT - 1)); 527250259Salc 528250259Salc /* 529250259Salc * The following computation cannot overflow 530250259Salc * because index's slot at the current level 531250259Salc * is less than VM_RADIX_COUNT - 1. 532250259Salc */ 533250259Salc index = vm_radix_trimkey(index, 534250259Salc rnode->rn_clev); 535250259Salc index += VM_RADIX_UNITLEVEL(rnode->rn_clev); 536246726Sattilio } else 537249986Salc index = rnode->rn_owner; 538250259Salc KASSERT(!vm_radix_keybarr(rnode, index), 539250259Salc ("vm_radix_lookup_ge: keybarr failed")); 540246726Sattilio } 541246726Sattilio slot = vm_radix_slot(index, rnode->rn_clev); 542249038Salc child = rnode->rn_child[slot]; 543249038Salc if (vm_radix_isleaf(child)) { 544249038Salc m = vm_radix_topage(child); 545249038Salc if (m->pindex >= index) 546249038Salc return (m); 547249038Salc } else if (child != NULL) 548249038Salc goto descend; 549246726Sattilio 550226645Sattilio /* 551246726Sattilio * Look for an available edge or page within the current 552246726Sattilio * bisection node. 553246726Sattilio */ 554246726Sattilio if (slot < (VM_RADIX_COUNT - 1)) { 555246726Sattilio inc = VM_RADIX_UNITLEVEL(rnode->rn_clev); 556246726Sattilio index = vm_radix_trimkey(index, rnode->rn_clev); 557249038Salc do { 558249038Salc index += inc; 559249038Salc slot++; 560249038Salc child = rnode->rn_child[slot]; 561249038Salc if (vm_radix_isleaf(child)) { 562249038Salc m = vm_radix_topage(child); 563249038Salc if (m->pindex >= index) 564249038Salc return (m); 565249038Salc } else if (child != NULL) 566249038Salc goto descend; 567249038Salc } while (slot < (VM_RADIX_COUNT - 1)); 568246726Sattilio } 569249038Salc KASSERT(child == NULL || vm_radix_isleaf(child), 570249038Salc ("vm_radix_lookup_ge: child is radix node")); 571230750Sattilio 572246726Sattilio /* 573250259Salc * If a page or edge bigger than the search slot is not found 574250259Salc * in the current node, ascend to the next higher-level node. 575246726Sattilio */ 576250259Salc goto ascend; 577249038Salcdescend: 578250520Salc KASSERT(rnode->rn_clev > 0, 579250259Salc ("vm_radix_lookup_ge: pushing leaf's parent")); 580250259Salc KASSERT(tos < VM_RADIX_LIMIT, 581250259Salc ("vm_radix_lookup_ge: stack overflow")); 582250259Salc stack[tos++] = rnode; 583249038Salc rnode = child; 584226645Sattilio } 585226645Sattilio} 586226645Sattilio 587226645Sattilio/* 588247771Salc * Look up the nearest entry at a position less than or equal to index. 589226645Sattilio */ 590246430Sattiliovm_page_t 591238245Sattiliovm_radix_lookup_le(struct vm_radix *rtree, vm_pindex_t index) 592226645Sattilio{ 593250259Salc struct vm_radix_node *stack[VM_RADIX_LIMIT]; 594246726Sattilio vm_pindex_t inc; 595246726Sattilio vm_page_t m; 596249038Salc struct vm_radix_node *child, *rnode; 597246726Sattilio#ifdef INVARIANTS 598246726Sattilio int loops = 0; 599246726Sattilio#endif 600250259Salc int slot, tos; 601226645Sattilio 602249427Salc rnode = vm_radix_getroot(rtree); 603249427Salc if (rnode == NULL) 604249427Salc return (NULL); 605249427Salc else if (vm_radix_isleaf(rnode)) { 606249427Salc m = vm_radix_topage(rnode); 607249427Salc if (m->pindex <= index) 608249427Salc return (m); 609249427Salc else 610249427Salc return (NULL); 611249427Salc } 612250259Salc tos = 0; 613249427Salc for (;;) { 614226646Sjeff /* 615249986Salc * If the keys differ before the current bisection node, 616249986Salc * then the search key might rollback to the earliest 617249986Salc * available bisection node or to the largest key 618249986Salc * in the current node (if the owner is smaller than the 619246726Sattilio * search key). 620226646Sjeff */ 621247770Salc if (vm_radix_keybarr(rnode, index)) { 622246726Sattilio if (index > rnode->rn_owner) { 623249986Salc index = rnode->rn_owner + VM_RADIX_COUNT * 624250259Salc VM_RADIX_UNITLEVEL(rnode->rn_clev); 625249986Salc } else { 626250259Salcascend: 627250259Salc KASSERT(++loops < 1000, 628250259Salc ("vm_radix_lookup_le: too many loops")); 629250259Salc 630250259Salc /* 631250259Salc * Pop nodes from the stack until either the 632250259Salc * stack is empty or a node that could have a 633250259Salc * matching descendant is found. 634250259Salc */ 635250259Salc do { 636250259Salc if (tos == 0) 637250259Salc return (NULL); 638250259Salc rnode = stack[--tos]; 639250259Salc } while (vm_radix_slot(index, 640250259Salc rnode->rn_clev) == 0); 641250259Salc 642250259Salc /* 643250259Salc * The following computation cannot overflow 644250259Salc * because index's slot at the current level 645250259Salc * is greater than 0. 646250259Salc */ 647250259Salc index = vm_radix_trimkey(index, 648250259Salc rnode->rn_clev); 649249986Salc } 650250259Salc index--; 651250259Salc KASSERT(!vm_radix_keybarr(rnode, index), 652250259Salc ("vm_radix_lookup_le: keybarr failed")); 653246726Sattilio } 654246726Sattilio slot = vm_radix_slot(index, rnode->rn_clev); 655249038Salc child = rnode->rn_child[slot]; 656249038Salc if (vm_radix_isleaf(child)) { 657249038Salc m = vm_radix_topage(child); 658249038Salc if (m->pindex <= index) 659249038Salc return (m); 660249038Salc } else if (child != NULL) 661249038Salc goto descend; 662246726Sattilio 663246726Sattilio /* 664246726Sattilio * Look for an available edge or page within the current 665246726Sattilio * bisection node. 666246726Sattilio */ 667246726Sattilio if (slot > 0) { 668246726Sattilio inc = VM_RADIX_UNITLEVEL(rnode->rn_clev); 669246726Sattilio index |= inc - 1; 670249038Salc do { 671249038Salc index -= inc; 672249038Salc slot--; 673249038Salc child = rnode->rn_child[slot]; 674249038Salc if (vm_radix_isleaf(child)) { 675249038Salc m = vm_radix_topage(child); 676249038Salc if (m->pindex <= index) 677249038Salc return (m); 678249038Salc } else if (child != NULL) 679249038Salc goto descend; 680249038Salc } while (slot > 0); 681226646Sjeff } 682249038Salc KASSERT(child == NULL || vm_radix_isleaf(child), 683249038Salc ("vm_radix_lookup_le: child is radix node")); 684246726Sattilio 685246726Sattilio /* 686250259Salc * If a page or edge smaller than the search slot is not found 687250259Salc * in the current node, ascend to the next higher-level node. 688246726Sattilio */ 689250259Salc goto ascend; 690249038Salcdescend: 691250520Salc KASSERT(rnode->rn_clev > 0, 692250259Salc ("vm_radix_lookup_le: pushing leaf's parent")); 693250259Salc KASSERT(tos < VM_RADIX_LIMIT, 694250259Salc ("vm_radix_lookup_le: stack overflow")); 695250259Salc stack[tos++] = rnode; 696249038Salc rnode = child; 697226646Sjeff } 698226645Sattilio} 699226645Sattilio 700226645Sattilio/* 701246726Sattilio * Remove the specified index from the tree. 702246726Sattilio * Panics if the key is not present. 703226645Sattilio */ 704236763Sattiliovoid 705238245Sattiliovm_radix_remove(struct vm_radix *rtree, vm_pindex_t index) 706226645Sattilio{ 707246726Sattilio struct vm_radix_node *rnode, *parent; 708246726Sattilio vm_page_t m; 709246726Sattilio int i, slot; 710226645Sattilio 711254141Sattilio /* 712254141Sattilio * Detect if a page is going to be removed from a trie which is 713254141Sattilio * already undergoing another trie operation. 714254141Sattilio * Right now this is only possible for vm_radix_remove() recursing 715254141Sattilio * into vm_radix_insert(). 716254141Sattilio * If this is the case, the caller must be notified about this 717254141Sattilio * situation. It will also takecare to update the RT_TRIE_MODIFIED 718254141Sattilio * accordingly. 719254141Sattilio * The RT_TRIE_MODIFIED bit is set here because the remove operation 720254141Sattilio * will always succeed. 721254141Sattilio */ 722254141Sattilio if ((rtree->rt_flags & RT_INSERT_INPROG) != 0) 723254141Sattilio rtree->rt_flags |= RT_TRIE_MODIFIED; 724254141Sattilio 725249502Salc rnode = vm_radix_getroot(rtree); 726249502Salc if (vm_radix_isleaf(rnode)) { 727249502Salc m = vm_radix_topage(rnode); 728249502Salc if (m->pindex != index) 729249502Salc panic("%s: invalid key found", __func__); 730249502Salc vm_radix_setroot(rtree, NULL); 731249502Salc return; 732249502Salc } 733246726Sattilio parent = NULL; 734236760Sattilio for (;;) { 735246726Sattilio if (rnode == NULL) 736246726Sattilio panic("vm_radix_remove: impossible to locate the key"); 737246726Sattilio slot = vm_radix_slot(index, rnode->rn_clev); 738249038Salc if (vm_radix_isleaf(rnode->rn_child[slot])) { 739249038Salc m = vm_radix_topage(rnode->rn_child[slot]); 740249038Salc if (m->pindex != index) 741249038Salc panic("%s: invalid key found", __func__); 742246726Sattilio rnode->rn_child[slot] = NULL; 743246726Sattilio rnode->rn_count--; 744246726Sattilio if (rnode->rn_count > 1) 745246726Sattilio break; 746246726Sattilio for (i = 0; i < VM_RADIX_COUNT; i++) 747246726Sattilio if (rnode->rn_child[i] != NULL) 748246726Sattilio break; 749246726Sattilio KASSERT(i != VM_RADIX_COUNT, 750246726Sattilio ("%s: invalid node configuration", __func__)); 751249502Salc if (parent == NULL) 752249502Salc vm_radix_setroot(rtree, rnode->rn_child[i]); 753249502Salc else { 754249502Salc slot = vm_radix_slot(index, parent->rn_clev); 755249502Salc KASSERT(parent->rn_child[slot] == rnode, 756249502Salc ("%s: invalid child value", __func__)); 757249502Salc parent->rn_child[slot] = rnode->rn_child[i]; 758249502Salc } 759246726Sattilio rnode->rn_count--; 760246726Sattilio rnode->rn_child[i] = NULL; 761246726Sattilio vm_radix_node_put(rnode); 762236760Sattilio break; 763236760Sattilio } 764246726Sattilio parent = rnode; 765246726Sattilio rnode = rnode->rn_child[slot]; 766236760Sattilio } 767226645Sattilio} 768226645Sattilio 769226645Sattilio/* 770226980Sattilio * Remove and free all the nodes from the radix tree. 771247771Salc * This function is recursive but there is a tight control on it as the 772226980Sattilio * maximum depth of the tree is fixed. 773226980Sattilio */ 774226980Sattiliovoid 775226980Sattiliovm_radix_reclaim_allnodes(struct vm_radix *rtree) 776226980Sattilio{ 777226980Sattilio struct vm_radix_node *root; 778226980Sattilio 779254141Sattilio KASSERT((rtree->rt_flags & RT_INSERT_INPROG) == 0, 780254141Sattilio ("vm_radix_reclaim_allnodes: unexpected trie recursion")); 781254141Sattilio 782246726Sattilio root = vm_radix_getroot(rtree); 783246726Sattilio if (root == NULL) 784226980Sattilio return; 785248684Salc vm_radix_setroot(rtree, NULL); 786249502Salc if (!vm_radix_isleaf(root)) 787249502Salc vm_radix_reclaim_allnodes_int(root); 788226980Sattilio} 789246726Sattilio 790254141Sattilio/* 791266591Salc * Replace an existing page in the trie with another one. 792266591Salc * Panics if there is not an old page in the trie at the new page's index. 793254141Sattilio */ 794254141Sattiliovm_page_t 795266591Salcvm_radix_replace(struct vm_radix *rtree, vm_page_t newpage) 796254141Sattilio{ 797254141Sattilio struct vm_radix_node *rnode; 798254141Sattilio vm_page_t m; 799266591Salc vm_pindex_t index; 800254141Sattilio int slot; 801254141Sattilio 802266591Salc index = newpage->pindex; 803254141Sattilio rnode = vm_radix_getroot(rtree); 804254141Sattilio if (rnode == NULL) 805254141Sattilio panic("%s: replacing page on an empty trie", __func__); 806254141Sattilio if (vm_radix_isleaf(rnode)) { 807254141Sattilio m = vm_radix_topage(rnode); 808254141Sattilio if (m->pindex != index) 809254141Sattilio panic("%s: original replacing root key not found", 810254141Sattilio __func__); 811254141Sattilio rtree->rt_root = (uintptr_t)newpage | VM_RADIX_ISLEAF; 812254141Sattilio return (m); 813254141Sattilio } 814254141Sattilio for (;;) { 815254141Sattilio slot = vm_radix_slot(index, rnode->rn_clev); 816254141Sattilio if (vm_radix_isleaf(rnode->rn_child[slot])) { 817254141Sattilio m = vm_radix_topage(rnode->rn_child[slot]); 818254141Sattilio if (m->pindex == index) { 819254141Sattilio rnode->rn_child[slot] = 820254141Sattilio (void *)((uintptr_t)newpage | 821254141Sattilio VM_RADIX_ISLEAF); 822254141Sattilio return (m); 823254141Sattilio } else 824254141Sattilio break; 825254141Sattilio } else if (rnode->rn_child[slot] == NULL || 826254141Sattilio vm_radix_keybarr(rnode->rn_child[slot], index)) 827254141Sattilio break; 828254141Sattilio rnode = rnode->rn_child[slot]; 829254141Sattilio } 830254141Sattilio panic("%s: original replacing page not found", __func__); 831254141Sattilio} 832254141Sattilio 833246726Sattilio#ifdef DDB 834246726Sattilio/* 835246837Sattilio * Show details about the given radix node. 836246726Sattilio */ 837246726SattilioDB_SHOW_COMMAND(radixnode, db_show_radixnode) 838246726Sattilio{ 839246726Sattilio struct vm_radix_node *rnode; 840246726Sattilio int i; 841246726Sattilio 842246726Sattilio if (!have_addr) 843246726Sattilio return; 844246726Sattilio rnode = (struct vm_radix_node *)addr; 845246726Sattilio db_printf("radixnode %p, owner %jx, children count %u, level %u:\n", 846246726Sattilio (void *)rnode, (uintmax_t)rnode->rn_owner, rnode->rn_count, 847246726Sattilio rnode->rn_clev); 848246726Sattilio for (i = 0; i < VM_RADIX_COUNT; i++) 849246726Sattilio if (rnode->rn_child[i] != NULL) 850246726Sattilio db_printf("slot: %d, val: %p, page: %p, clev: %d\n", 851246726Sattilio i, (void *)rnode->rn_child[i], 852249038Salc vm_radix_isleaf(rnode->rn_child[i]) ? 853249038Salc vm_radix_topage(rnode->rn_child[i]) : NULL, 854246726Sattilio rnode->rn_clev); 855246726Sattilio} 856246726Sattilio#endif /* DDB */ 857