vm_radix.c revision 226646
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 inclusive, and stores 222 * them 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 || end == 0) 246 end = max; 247restart: 248 loops++; 249 if (loops > 1000) 250 panic("vm_radix_lookupn: looping %d\n", loops); 251 /* 252 * Search the tree from the top for any leaf node holding an index 253 * between start and end. 254 */ 255 level = rtree->rt_height - 1; 256 rnode = rtree->rt_root; 257 while (rnode) { 258 slot = vm_radix_slot(start, level); 259 CTR5(KTR_VM, 260 "lookupn: tree %p, index %p, level %d, slot %d, child %p", 261 rtree, (void *)start, level, slot, rnode->rn_child[slot]); 262 if (level == 0) 263 break; 264 /* 265 * If we don't have an exact match we must start our search 266 * from the next leaf and adjust our index appropriately. 267 */ 268 if ((child = rnode->rn_child[slot]) == NULL) { 269 /* 270 * Calculate how much to increment our index by 271 * based on the tree level. We must truncate the 272 * lower bits to start from the begnning of the next 273 * leaf. 274 */ 275 inc = 1LL << (level * VM_RADIX_WIDTH); 276 start &= ~VM_RADIX_MAX(level); 277 start += inc; 278 slot++; 279 CTR5(KTR_VM, 280 "lookupn: start %p end %p inc %d mask 0x%lX slot %d", 281 (void *)start, (void *)end, inc, ~VM_RADIX_MAX(level), slot); 282 for (; slot < VM_RADIX_COUNT && start <= end; 283 slot++, start += inc) { 284 child = rnode->rn_child[slot]; 285 if (child) 286 break; 287 } 288 } 289 rnode = child; 290 level--; 291 } 292 if (rnode == NULL) { 293 /* 294 * If we still have another range to search, start looking 295 * from the next node. Otherwise, return what we've already 296 * found. The loop above has already adjusted start to the 297 * beginning of the next node. 298 * 299 * Detect start wrapping back to 0 and return in this case. 300 */ 301 if (start <= end && start != 0) 302 goto restart; 303 goto out; 304 } 305 for (; outidx < cnt && slot < VM_RADIX_COUNT && start <= end; 306 slot++, start++) { 307 val = rnode->rn_child[slot]; 308 if (val == NULL) 309 continue; 310 out[outidx++] = val; 311 } 312 /* 313 * Go fetch the next page to fill the requested number of pages 314 * otherwise the caller will simply call us again to fulfill the 315 * same request after the structures are pushed out of cache. 316 */ 317 if (outidx < cnt && start <= end) 318 goto restart; 319 320out: 321 *next = start; 322 323 return (outidx); 324} 325 326/* 327 * Look up any entry at a position less than or equal to index. 328 */ 329void * 330vm_radix_lookup_le(struct vm_radix *rtree, vm_pindex_t index) 331{ 332 struct vm_radix_node *rnode; 333 struct vm_radix_node *child; 334 vm_pindex_t max; 335 vm_pindex_t inc; 336 int slot; 337 int level; 338 int loops = 0; 339 340 CTR2(KTR_VM, 341 "lookup_le: tree %p, index %p", rtree, (void *)index); 342 if (rtree->rt_root == NULL) 343 return (NULL); 344 max = VM_RADIX_MAX(rtree->rt_height); 345 if (index > max || index == 0) 346 index = max; 347restart: 348 loops++; 349 if (loops > 1000) 350 panic("vm_radix_looku_le: looping %d\n", loops); 351 /* 352 * Search the tree from the top for any leaf node holding an index 353 * lower than 'index'. 354 */ 355 level = rtree->rt_height - 1; 356 rnode = rtree->rt_root; 357 while (rnode) { 358 slot = vm_radix_slot(index, level); 359 CTR5(KTR_VM, 360 "lookup_le: tree %p, index %p, level %d, slot %d, child %p", 361 rtree, (void *)index, level, slot, rnode->rn_child[slot]); 362 if (level == 0) 363 break; 364 /* 365 * If we don't have an exact match we must start our search 366 * from the next leaf and adjust our index appropriately. 367 */ 368 if ((child = rnode->rn_child[slot]) == NULL) { 369 /* 370 * Calculate how much to decrement our index by 371 * based on the tree level. We must set the 372 * lower bits to start from the end of the next 373 * leaf. 374 */ 375 inc = 1LL << (level * VM_RADIX_WIDTH); 376 index |= VM_RADIX_MAX(level); 377 index -= inc; 378 slot--; 379 CTR4(KTR_VM, 380 "lookup_le: start %p inc %ld mask 0x%lX slot %d", 381 (void *)index, inc, VM_RADIX_MAX(level), slot); 382 for (; slot >= 0; slot--, index -= inc) { 383 child = rnode->rn_child[slot]; 384 if (child) 385 break; 386 } 387 } 388 rnode = child; 389 level--; 390 } 391 if (rnode) { 392 for (; slot >= 0; slot--, index--) { 393 if (rnode->rn_child[slot]) 394 return (rnode->rn_child[slot]); 395 } 396 } 397 if (index != -1) 398 goto restart; 399 return (NULL); 400} 401 402/* 403 * Remove the specified index from the tree. If possible the height of the 404 * tree is adjusted after deletion. The value stored at index is returned 405 * panics if the key is not present. 406 */ 407void * 408vm_radix_remove(struct vm_radix *rtree, vm_pindex_t index) 409{ 410 struct vm_radix_node *stack[VM_RADIX_LIMIT]; 411 struct vm_radix_node *rnode; 412 void *val; 413 int level; 414 int slot; 415 416 KASSERT(index <= VM_RADIX_MAX(rtree->rt_height), 417 ("vm_radix_remove: %p index %jd out of range %jd.", 418 rtree, index, VM_RADIX_MAX(rtree->rt_height))); 419 val = NULL; 420 rnode = rtree->rt_root; 421 level = rtree->rt_height - 1; 422 /* 423 * Find the node and record the path in stack. 424 */ 425 while (level && rnode) { 426 stack[level] = rnode; 427 slot = vm_radix_slot(index, level); 428 rnode = rnode->rn_child[slot]; 429 CTR5(KTR_VM, 430 "remove: tree %p, index %p, level %d, slot %d, child %p", 431 rtree, (void *)index, level, slot, rnode->rn_child[slot]); 432 level--; 433 } 434 slot = vm_radix_slot(index, 0); 435 KASSERT(rnode != NULL && rnode->rn_child[slot] != NULL, 436 ("vm_radix_remove: index %jd not present in the tree.\n", index)); 437 438 val = rnode->rn_child[slot]; 439 for (;;) { 440 rnode->rn_child[slot] = NULL; 441 rnode->rn_count--; 442 if (rnode->rn_count > 0) 443 break; 444 vm_radix_node_put(rnode); 445 if (rnode == rtree->rt_root) { 446 rtree->rt_root = NULL; 447 rtree->rt_height = 0; 448 break; 449 } 450 rnode = stack[++level]; 451 slot = vm_radix_slot(index, level); 452 453 } 454 return (val); 455} 456 457/* 458 * Attempts to reduce the height of the tree. 459 */ 460void 461vm_radix_shrink(struct vm_radix *rtree) 462{ 463 struct vm_radix_node *tmp; 464 465 if (rtree->rt_root == NULL) 466 return; 467 468 /* Adjust the height of the tree. */ 469 while (rtree->rt_root->rn_count == 1 && 470 rtree->rt_root->rn_child[0] != NULL) { 471 tmp = rtree->rt_root; 472 rtree->rt_root = tmp->rn_child[0]; 473 rtree->rt_height--; 474 tmp->rn_count--; 475 vm_radix_node_put(tmp); 476 } 477 /* Finally see if we have an empty tree. */ 478 if (rtree->rt_root->rn_count == 0) { 479 vm_radix_node_put(rtree->rt_root); 480 rtree->rt_root = NULL; 481 rtree->rt_height = 0; 482 } 483} 484