1/* |
2 * Copyright (c) 2011 Jeffrey Roberson <jeff@freebsd.org> |
3 * Copyright (c) 2008 Mayur Shardul <mayur.shardul@gmail.com> |
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 --- 194 unchanged lines hidden (view full) --- 206 int height) 207{ 208 uintptr_t root; 209 210 root = (uintptr_t)rnode | height; 211 rtree->rt_root = root; 212} 213 |
214static inline void * 215vm_radix_match(void *child, int color) 216{ 217 uintptr_t c; 218 219 c = (uintptr_t)child; 220 221 if ((c & color) == 0) 222 return (NULL); 223 return ((void *)(c & ~VM_RADIX_FLAGS)); 224} 225 |
226/* 227 * Inserts the key-value pair in to the radix tree. Returns errno. 228 * Panics if the key already exists. 229 */ 230int 231vm_radix_insert(struct vm_radix *rtree, vm_pindex_t index, void *val) 232{ 233 struct vm_radix_node *rnode; --- 50 unchanged lines hidden (view full) --- 284 rnode->rn_count++; 285 } 286 CTR5(KTR_VM, 287 "insert: tree %p, index %p, level %d, slot %d, child %p", 288 rtree, (void *)index, level, slot, rnode->rn_child[slot]); 289 rnode = rnode->rn_child[slot]; 290 } 291 |
292 slot = vm_radix_slot(index, 0); |
293 CTR5(KTR_VM, "insert: tree %p, index %p, level %d, slot %d, child %p", 294 rtree, (void *)index, level, slot, rnode->rn_child[slot]); 295 KASSERT(rnode->rn_child[slot] == NULL, 296 ("vm_radix_insert: Duplicate value %p at index: %lu\n", 297 rnode->rn_child[slot], (u_long)index)); |
298 val = (void *)((uintptr_t)val | VM_RADIX_BLACK); |
299 rnode->rn_child[slot] = val; |
300 atomic_add_int((volatile int *)&rnode->rn_count, 1); |
301 302 return 0; 303} 304 305/* 306 * Returns the value stored at the index. If the index is not present 307 * NULL is returned. 308 */ 309void * |
310vm_radix_lookup(struct vm_radix *rtree, vm_pindex_t index, int color) |
311{ 312 struct vm_radix_node *rnode; 313 int slot; 314 int level; 315 316 level = vm_radix_height(rtree, &rnode); 317 if (index > VM_RADIX_MAX(level)) 318 return NULL; 319 level--; 320 while (rnode) { 321 slot = vm_radix_slot(index, level); 322 CTR5(KTR_VM, 323 "lookup: tree %p, index %p, level %d, slot %d, child %p", 324 rtree, (void *)index, level, slot, rnode->rn_child[slot]); 325 if (level == 0) |
326 return vm_radix_match(rnode->rn_child[slot], color); |
327 rnode = rnode->rn_child[slot]; 328 level--; 329 } 330 CTR2(KTR_VM, "lookup: tree %p, index %p failed", rtree, (void *)index); 331 332 return NULL; 333} 334 |
335void * 336vm_radix_color(struct vm_radix *rtree, vm_pindex_t index, int color) 337{ 338 struct vm_radix_node *rnode; 339 uintptr_t child; 340 int slot; 341 int level; 342 343 level = vm_radix_height(rtree, &rnode); 344 if (index > VM_RADIX_MAX(level)) 345 return NULL; 346 level--; 347 while (rnode) { 348 slot = vm_radix_slot(index, level); 349 CTR5(KTR_VM, 350 "color: tree %p, index %p, level %d, slot %d, child %p", 351 rtree, (void *)index, level, slot, rnode->rn_child[slot]); 352 if (level == 0) 353 break; 354 rnode = rnode->rn_child[slot]; 355 level--; 356 } 357 if (rnode == NULL || rnode->rn_child[slot] == NULL) 358 return (NULL); 359 child = (uintptr_t)rnode->rn_child[slot]; 360 child &= ~VM_RADIX_FLAGS; 361 rnode->rn_child[slot] = (void *)(child | color); 362 363 return (void *)child; 364} 365 |
366/* |
367 * Looks up as many as cnt values between start and end, and stores 368 * them in the caller allocated array out. The next index can be used 369 * to restart the scan. This optimizes forward scans in the tree. |
370 */ 371int 372vm_radix_lookupn(struct vm_radix *rtree, vm_pindex_t start, |
373 vm_pindex_t end, int color, void **out, int cnt, vm_pindex_t *next) |
374{ 375 struct vm_radix_node *rnode; |
376 vm_pindex_t inc; 377 int slot; 378 int level; 379 void *val; 380 int outidx; |
381 382 CTR3(KTR_VM, "lookupn: tree %p, start %p, end %p", 383 rtree, (void *)start, (void *)end); 384 outidx = 0; 385restart: 386 level = vm_radix_height(rtree, &rnode); |
387 if (rnode == NULL || start > VM_RADIX_MAX(level)) |
388 goto out; |
389 if (end && start >= end) 390 goto out; |
391 /* 392 * Search the tree from the top for any leaf node holding an index 393 * between start and end. 394 */ |
395 for (level--; level; level--) { |
396 slot = vm_radix_slot(start, level); 397 CTR5(KTR_VM, 398 "lookupn: tree %p, index %p, level %d, slot %d, child %p", 399 rtree, (void *)start, level, slot, rnode->rn_child[slot]); |
400 if (rnode->rn_child[slot] != NULL) { 401 rnode = rnode->rn_child[slot]; 402 continue; 403 } |
404 /* |
405 * Calculate how much to increment our index by 406 * based on the tree level. We must truncate the 407 * lower bits to start from the begnning of the 408 * next leaf. 409 */ 410 inc = 1LL << (level * VM_RADIX_WIDTH); 411 start &= ~VM_RADIX_MAX(level); 412 start += inc; 413 slot++; 414 CTR5(KTR_VM, 415 "lookupn: start %p end %p inc %d mask 0x%lX slot %d", 416 (void *)start, (void *)end, inc, 417 ~VM_RADIX_MAX(level), slot); 418 for (; slot < VM_RADIX_COUNT; slot++, start += inc) { 419 if (end != 0 && start >= end) 420 goto out; 421 if (rnode->rn_child[slot]) { 422 rnode = rnode->rn_child[slot]; 423 break; |
424 } 425 } |
426 if (slot == VM_RADIX_COUNT) |
427 goto restart; |
428 } |
429 slot = vm_radix_slot(start, 0); 430 for (; slot < VM_RADIX_COUNT; slot++, start++) { 431 if (end != 0 && start >= end) 432 goto out; 433 val = vm_radix_match(rnode->rn_child[slot], color); |
434 if (val == NULL) 435 continue; |
436 CTR4(KTR_VM, 437 "lookupn: tree %p index %p slot %d found child %p", 438 rtree, (void *)start, slot, val); |
439 out[outidx++] = val; |
440 if (outidx == cnt) 441 goto out; |
442 } 443 /* 444 * Go fetch the next page to fill the requested number of pages 445 * otherwise the caller will simply call us again to fulfill the 446 * same request after the structures are pushed out of cache. 447 */ |
448 if ((end == 0 || start < end)) |
449 goto restart; |
450out: 451 *next = start; 452 453 return (outidx); 454} 455 456/* 457 * Look up any entry at a position less than or equal to index. 458 */ 459void * |
460vm_radix_lookup_le(struct vm_radix *rtree, vm_pindex_t index, int color) |
461{ 462 struct vm_radix_node *rnode; 463 struct vm_radix_node *child; 464 vm_pindex_t max; 465 vm_pindex_t inc; |
466 void *val; |
467 int slot; 468 int level; |
469 470 CTR2(KTR_VM, 471 "lookup_le: tree %p, index %p", rtree, (void *)index); 472restart: 473 level = vm_radix_height(rtree, &rnode); 474 if (rnode == NULL) 475 return (NULL); 476 max = VM_RADIX_MAX(level); 477 if (index > max || index == 0) 478 index = max; |
479 /* 480 * Search the tree from the top for any leaf node holding an index 481 * lower than 'index'. 482 */ 483 level--; 484 while (rnode) { 485 slot = vm_radix_slot(index, level); 486 CTR5(KTR_VM, --- 25 unchanged lines hidden (view full) --- 512 break; 513 } 514 } 515 rnode = child; 516 level--; 517 } 518 if (rnode) { 519 for (; slot >= 0; slot--, index--) { |
520 val = vm_radix_match(rnode->rn_child[slot], color); 521 if (val) 522 return (val); |
523 } 524 } 525 if (index != -1) 526 goto restart; 527 return (NULL); 528} 529 530/* 531 * Remove the specified index from the tree. If possible the height of the 532 * tree is adjusted after deletion. The value stored at index is returned 533 * panics if the key is not present. 534 */ 535void * |
536vm_radix_remove(struct vm_radix *rtree, vm_pindex_t index, int color) |
537{ 538 struct vm_radix_node *stack[VM_RADIX_LIMIT]; 539 struct vm_radix_node *rnode, *root; 540 void *val; 541 int level; 542 int slot; 543 544 level = vm_radix_height(rtree, &root); --- 10 unchanged lines hidden (view full) --- 555 stack[level] = rnode; 556 slot = vm_radix_slot(index, level); 557 rnode = rnode->rn_child[slot]; 558 CTR5(KTR_VM, 559 "remove: tree %p, index %p, level %d, slot %d, child %p", 560 rtree, (void *)index, level, slot, rnode->rn_child[slot]); 561 level--; 562 } |
563 KASSERT(rnode != NULL, 564 ("vm_radix_remove: index %jd not present in the tree.\n", index)); |
565 slot = vm_radix_slot(index, 0); |
566 val = vm_radix_match(rnode->rn_child[slot], color); 567 KASSERT(val != NULL, |
568 ("vm_radix_remove: index %jd not present in the tree.\n", index)); 569 |
570 for (;;) { 571 rnode->rn_child[slot] = NULL; |
572 /* 573 * Use atomics for the last level since red and black 574 * will both adjust it. 575 */ 576 if (level == 0) 577 atomic_add_int((volatile int *)&rnode->rn_count, -1); 578 else 579 rnode->rn_count--; 580 /* 581 * Only allow black removes to prune the tree. 582 */ 583 if ((color & VM_RADIX_BLACK) == 0 || rnode->rn_count > 0) |
584 break; 585 vm_radix_node_put(rnode); 586 if (rnode == root) { 587 vm_radix_setroot(rtree, NULL, 0); 588 break; 589 } 590 rnode = stack[++level]; 591 slot = vm_radix_slot(index, level); --- 34 unchanged lines hidden --- |