vm_radix.c revision 226645
1/* 2 * Copyright (c) 2008 Mayur Shardul <mayur.shardul@gmail.com> 3 * Copyright (c) 2011 Jeffrey Roberson <jeff@freebsd.org> 4 * All rights reserved. 5 * 6 * Redistribution and use in source and binary forms, with or without 7 * modification, are permitted provided that the following conditions 8 * are met: 9 * 1. Redistributions of source code must retain the above copyright 10 * notice, this list of conditions and the following disclaimer. 11 * 2. Redistributions in binary form must reproduce the above copyright 12 * notice, this list of conditions and the following disclaimer in the 13 * documentation and/or other materials provided with the distribution. 14 * 15 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND 16 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 17 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 18 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE 19 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 20 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 21 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 22 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 23 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 24 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 25 * SUCH DAMAGE. 26 * 27 */ 28 29 30/* 31 * Radix tree implementation. 32 */ 33 34#include <sys/cdefs.h> 35 36#include <sys/param.h> 37#include <sys/conf.h> 38#include <sys/systm.h> 39#include <sys/kernel.h> 40#include <sys/malloc.h> 41#include <sys/queue.h> 42#include <sys/param.h> 43#include <sys/lock.h> 44#include <sys/mutex.h> 45#include <sys/ktr.h> 46#include <vm/vm.h> 47#include <vm/vm_radix.h> 48#include <vm/vm_object.h> 49 50#include <sys/kdb.h> 51 52 53SLIST_HEAD(, vm_radix_node) res_rnodes_head = 54 SLIST_HEAD_INITIALIZER(res_rnodes_head); 55 56struct mtx rnode_lock; 57vm_offset_t rnode_start; 58vm_offset_t rnode_end; 59 60/* 61 * Allocate a radix node. Initializes all elements to 0. 62 */ 63static struct vm_radix_node * 64vm_radix_node_get(void) 65{ 66 struct vm_radix_node *rnode; 67 68 if (VM_OBJECT_LOCKED(kernel_object) || VM_OBJECT_LOCKED(kmem_object)){ 69 mtx_lock_spin(&rnode_lock); 70 if (!SLIST_EMPTY(&res_rnodes_head)) { 71 rnode = SLIST_FIRST(&res_rnodes_head); 72 SLIST_REMOVE_HEAD(&res_rnodes_head, next); 73 mtx_unlock_spin(&rnode_lock); 74 bzero((void *)rnode, sizeof(*rnode)); 75 goto out; 76 } 77 mtx_unlock_spin(&rnode_lock); 78 panic("No memory for kernel_object. . ."); 79 } 80 rnode = malloc(sizeof(struct vm_radix_node), M_TEMP, M_NOWAIT | M_ZERO); 81 if (rnode == NULL) { 82 panic("vm_radix_node_get: Can not allocate memory\n"); 83 return NULL; 84 } 85out: 86 87 return rnode; 88} 89 90/* 91 * Free radix node. 92 */ 93static void 94vm_radix_node_put(struct vm_radix_node *rnode) 95{ 96 97 KASSERT(rnode->rn_count == 0, 98 ("vm_radix_node_put: Freeing a node with %d children\n", 99 rnode->rn_count)); 100 if ((vm_offset_t)rnode >= rnode_start && 101 (vm_offset_t)rnode < rnode_end) { 102 mtx_lock_spin(&rnode_lock); 103 SLIST_INSERT_HEAD(&res_rnodes_head, rnode, next); 104 mtx_unlock_spin(&rnode_lock); 105 } else 106 free(rnode,M_TEMP); 107} 108 109/* 110 * Return the position in the array for a given level. 111 */ 112static inline int 113vm_radix_slot(vm_pindex_t index, int level) 114{ 115 116 return ((index >> (level * VM_RADIX_WIDTH)) & VM_RADIX_MASK); 117} 118 119/* 120 * Inserts the key-value pair in to the radix tree. Returns errno. 121 * Panics if the key already exists. 122 */ 123int 124vm_radix_insert(struct vm_radix *rtree, vm_pindex_t index, void *val) 125{ 126 struct vm_radix_node *rnode; 127 int slot; 128 int level; 129 130 CTR3(KTR_VM, 131 "insert: tree %p, index %p, val %p", rtree, (void *)index, val); 132 if (index == -1) 133 panic("vm_radix_insert: -1 is not a valid index.\n"); 134 /* 135 * Increase the height by adding nodes at the root until 136 * there is sufficient space. 137 */ 138 while (rtree->rt_height == 0 || 139 index > VM_RADIX_MAX(rtree->rt_height)) { 140 CTR3(KTR_VM, "insert: expanding %jd > %jd height %d", 141 index, VM_RADIX_MAX(rtree->rt_height), rtree->rt_height); 142 /* 143 * Only allocate tree nodes if they are needed. 144 */ 145 if (rtree->rt_root == NULL || rtree->rt_root->rn_count != 0) { 146 rnode = vm_radix_node_get(); 147 if (rnode == NULL) 148 return (ENOMEM); 149 if (rtree->rt_root) { 150 rnode->rn_child[0] = rtree->rt_root; 151 rnode->rn_count = 1; 152 } 153 rtree->rt_root = rnode; 154 } 155 rtree->rt_height++; 156 KASSERT(rtree->rt_height <= VM_RADIX_LIMIT, 157 ("vm_radix_insert: Tree %p height %d too tall", rtree, 158 rtree->rt_height)); 159 } 160 161 /* Now that the tree is tall enough, fill in the path to the index. */ 162 rnode = rtree->rt_root; 163 for (level = rtree->rt_height - 1; level > 0; level--) { 164 slot = vm_radix_slot(index, level); 165 /* Add the required intermidiate nodes. */ 166 if (rnode->rn_child[slot] == NULL) { 167 rnode->rn_child[slot] = vm_radix_node_get(); 168 if (rnode->rn_child[slot] == NULL) 169 return (ENOMEM); 170 rnode->rn_count++; 171 } 172 CTR5(KTR_VM, 173 "insert: tree %p, index %p, level %d, slot %d, child %p", 174 rtree, (void *)index, level, slot, rnode->rn_child[slot]); 175 rnode = rnode->rn_child[slot]; 176 } 177 178 slot = vm_radix_slot(index, level); 179 CTR5(KTR_VM, "insert: tree %p, index %p, level %d, slot %d, child %p", 180 rtree, (void *)index, level, slot, rnode->rn_child[slot]); 181 KASSERT(rnode->rn_child[slot] == NULL, 182 ("vm_radix_insert: Duplicate value %p at index: %lu\n", 183 rnode->rn_child[slot], (u_long)index)); 184 rnode->rn_child[slot] = val; 185 rnode->rn_count++; 186 187 return 0; 188} 189 190/* 191 * Returns the value stored at the index. If the index is not present 192 * NULL is returned. 193 */ 194void * 195vm_radix_lookup(struct vm_radix *rtree, vm_pindex_t index) 196{ 197 struct vm_radix_node *rnode; 198 int slot; 199 int level; 200 201 if (index > VM_RADIX_MAX(rtree->rt_height)) 202 return NULL; 203 level = rtree->rt_height - 1; 204 rnode = rtree->rt_root; 205 while (rnode) { 206 slot = vm_radix_slot(index, level); 207 CTR5(KTR_VM, 208 "lookup: tree %p, index %p, level %d, slot %d, child %p", 209 rtree, (void *)index, level, slot, rnode->rn_child[slot]); 210 if (level == 0) 211 return rnode->rn_child[slot]; 212 rnode = rnode->rn_child[slot]; 213 level--; 214 } 215 CTR2(KTR_VM, "lookup: tree %p, index %p failed", rtree, (void *)index); 216 217 return NULL; 218} 219 220/* 221 * Looks up as many as cnt values between start and end and stores them 222 * in the caller allocated array out. The next index can be used to 223 * restart the scan. This optimizes forward scans in the tree. 224 */ 225int 226vm_radix_lookupn(struct vm_radix *rtree, vm_pindex_t start, 227 vm_pindex_t end, void **out, int cnt, vm_pindex_t *next) 228{ 229 struct vm_radix_node *rnode; 230 struct vm_radix_node *child; 231 vm_pindex_t max; 232 vm_pindex_t inc; 233 int slot; 234 int level; 235 void *val; 236 int outidx; 237 int loops = 0; 238 239 CTR3(KTR_VM, "lookupn: tree %p, start %p, end %p", 240 rtree, (void *)start, (void *)end); 241 outidx = 0; 242 max = VM_RADIX_MAX(rtree->rt_height); 243 if (start > max) 244 return 0; 245 if (end > max + 1) 246 end = max + 1; 247 if (end == 0) 248 end = -1; 249restart: 250 loops++; 251 if (loops > 1000) 252 panic("vm_radix_lookupn: looping %d\n", loops); 253 /* 254 * Search the tree from the top for any leaf node holding an index 255 * between start and end. 256 */ 257 level = rtree->rt_height - 1; 258 rnode = rtree->rt_root; 259 while (rnode) { 260 slot = vm_radix_slot(start, level); 261 CTR5(KTR_VM, 262 "lookupn: tree %p, index %p, level %d, slot %d, child %p", 263 rtree, (void *)start, level, slot, rnode->rn_child[slot]); 264 if (level == 0) 265 break; 266 /* 267 * If we don't have an exact match we must start our search 268 * from the next leaf and adjust our index appropriately. 269 */ 270 if ((child = rnode->rn_child[slot]) == NULL) { 271 /* 272 * Calculate how much to increment our index by 273 * based on the tree level. We must truncate the 274 * lower bits to start from the begnning of the next 275 * leaf. 276 */ 277 inc = 1LL << (level * VM_RADIX_WIDTH); 278 start &= ~VM_RADIX_MAX(level); 279 start += inc; 280 slot++; 281 CTR5(KTR_VM, 282 "lookupn: start %p end %p inc %d mask 0x%lX slot %d", 283 (void *)start, (void *)end, inc, ~VM_RADIX_MAX(level), slot); 284 for (; slot < VM_RADIX_COUNT && start < end; 285 slot++, start += inc) { 286 child = rnode->rn_child[slot]; 287 if (child) 288 break; 289 } 290 } 291 rnode = child; 292 level--; 293 } 294 if (rnode == NULL) { 295 /* 296 * If we still have another range to search, start looking 297 * from the next node. Otherwise, return what we've already 298 * found. The loop above has already adjusted start to the 299 * beginning of the next node. 300 * 301 * Detect start wrapping back to 0 and return in this case. 302 */ 303 if (start < end && start != 0) 304 goto restart; 305 goto out; 306 } 307 for (; outidx < cnt && slot < VM_RADIX_COUNT && start < end; 308 slot++, start++) { 309 val = rnode->rn_child[slot]; 310 if (val == NULL) 311 continue; 312 out[outidx++] = val; 313 } 314 /* 315 * Go fetch the next page to fill the requested number of pages 316 * otherwise the caller will simply call us again to fulfill the 317 * same request after the structures are pushed out of cache. 318 */ 319 if (outidx < cnt && start < end) 320 goto restart; 321 322out: 323 *next = start; 324 325 return (outidx); 326} 327 328/* 329 * Look up any entry at a position greater or equal to index. 330 */ 331void * 332vm_radix_lookup_ge(struct vm_radix *rtree, vm_pindex_t index) 333{ 334 vm_pindex_t max; 335 void *val; 336 int n; 337 338 max = VM_RADIX_MAX(rtree->rt_height); 339 n = vm_radix_lookupn(rtree, index, max + 1, &val, 1, &max); 340 if (n) 341 return (val); 342 return (NULL); 343} 344 345/* 346 * Look up any entry at a position less than or equal to index. 347 */ 348void * 349vm_radix_lookup_le(struct vm_radix *rtree, vm_pindex_t index) 350{ 351 return NULL; 352} 353 354/* 355 * Remove the specified index from the tree. If possible the height of the 356 * tree is adjusted after deletion. The value stored at index is returned 357 * panics if the key is not present. 358 */ 359void * 360vm_radix_remove(struct vm_radix *rtree, vm_pindex_t index) 361{ 362 struct vm_radix_node *stack[VM_RADIX_LIMIT]; 363 struct vm_radix_node *rnode; 364 void *val; 365 int level; 366 int slot; 367 368 KASSERT(index <= VM_RADIX_MAX(rtree->rt_height), 369 ("vm_radix_remove: %p index %jd out of range %jd.", 370 rtree, index, VM_RADIX_MAX(rtree->rt_height))); 371 val = NULL; 372 rnode = rtree->rt_root; 373 level = rtree->rt_height - 1; 374 /* 375 * Find the node and record the path in stack. 376 */ 377 while (level && rnode) { 378 stack[level] = rnode; 379 slot = vm_radix_slot(index, level); 380 rnode = rnode->rn_child[slot]; 381 CTR5(KTR_VM, 382 "remove: tree %p, index %p, level %d, slot %d, child %p", 383 rtree, (void *)index, level, slot, rnode->rn_child[slot]); 384 level--; 385 } 386 slot = vm_radix_slot(index, 0); 387 KASSERT(rnode != NULL && rnode->rn_child[slot] != NULL, 388 ("vm_radix_remove: index %jd not present in the tree.\n", index)); 389 390 val = rnode->rn_child[slot]; 391 for (;;) { 392 rnode->rn_child[slot] = NULL; 393 rnode->rn_count--; 394 if (rnode->rn_count > 0) 395 break; 396 vm_radix_node_put(rnode); 397 if (rnode == rtree->rt_root) { 398 rtree->rt_root = NULL; 399 rtree->rt_height = 0; 400 break; 401 } 402 rnode = stack[++level]; 403 slot = vm_radix_slot(index, level); 404 405 } 406 return (val); 407} 408 409/* 410 * Attempts to reduce the height of the tree. 411 */ 412void 413vm_radix_shrink(struct vm_radix *rtree) 414{ 415 struct vm_radix_node *tmp; 416 417 if (rtree->rt_root == NULL) 418 return; 419 420 /* Adjust the height of the tree. */ 421 while (rtree->rt_root->rn_count == 1 && 422 rtree->rt_root->rn_child[0] != NULL) { 423 tmp = rtree->rt_root; 424 rtree->rt_root = tmp->rn_child[0]; 425 rtree->rt_height--; 426 tmp->rn_count--; 427 vm_radix_node_put(tmp); 428 } 429 /* Finally see if we have an empty tree. */ 430 if (rtree->rt_root->rn_count == 0) { 431 vm_radix_node_put(rtree->rt_root); 432 rtree->rt_root = NULL; 433 rtree->rt_height = 0; 434 } 435} 436