vm_radix.c (226876) | vm_radix.c (226930) |
---|---|
1/* | 1/* |
2 * Copyright (c) 2008 Mayur Shardul <mayur.shardul@gmail.com> | |
3 * Copyright (c) 2011 Jeffrey Roberson <jeff@freebsd.org> | 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 | 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 |
|
214/* 215 * Inserts the key-value pair in to the radix tree. Returns errno. 216 * Panics if the key already exists. 217 */ 218int 219vm_radix_insert(struct vm_radix *rtree, vm_pindex_t index, void *val) 220{ 221 struct vm_radix_node *rnode; --- 50 unchanged lines hidden (view full) --- 272 rnode->rn_count++; 273 } 274 CTR5(KTR_VM, 275 "insert: tree %p, index %p, level %d, slot %d, child %p", 276 rtree, (void *)index, level, slot, rnode->rn_child[slot]); 277 rnode = rnode->rn_child[slot]; 278 } 279 | 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 |
280 slot = vm_radix_slot(index, level); | 292 slot = vm_radix_slot(index, 0); |
281 CTR5(KTR_VM, "insert: tree %p, index %p, level %d, slot %d, child %p", 282 rtree, (void *)index, level, slot, rnode->rn_child[slot]); 283 KASSERT(rnode->rn_child[slot] == NULL, 284 ("vm_radix_insert: Duplicate value %p at index: %lu\n", 285 rnode->rn_child[slot], (u_long)index)); | 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); |
|
286 rnode->rn_child[slot] = val; | 299 rnode->rn_child[slot] = val; |
287 rnode->rn_count++; | 300 atomic_add_int((volatile int *)&rnode->rn_count, 1); |
288 289 return 0; 290} 291 292/* 293 * Returns the value stored at the index. If the index is not present 294 * NULL is returned. 295 */ 296void * | 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 * |
297vm_radix_lookup(struct vm_radix *rtree, vm_pindex_t index) | 310vm_radix_lookup(struct vm_radix *rtree, vm_pindex_t index, int color) |
298{ 299 struct vm_radix_node *rnode; 300 int slot; 301 int level; 302 303 level = vm_radix_height(rtree, &rnode); 304 if (index > VM_RADIX_MAX(level)) 305 return NULL; 306 level--; 307 while (rnode) { 308 slot = vm_radix_slot(index, level); 309 CTR5(KTR_VM, 310 "lookup: tree %p, index %p, level %d, slot %d, child %p", 311 rtree, (void *)index, level, slot, rnode->rn_child[slot]); 312 if (level == 0) | 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) |
313 return rnode->rn_child[slot]; | 326 return vm_radix_match(rnode->rn_child[slot], color); |
314 rnode = rnode->rn_child[slot]; 315 level--; 316 } 317 CTR2(KTR_VM, "lookup: tree %p, index %p failed", rtree, (void *)index); 318 319 return NULL; 320} 321 | 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 |
|
322/* | 366/* |
323 * Looks up as many as cnt values between start and end inclusive, and stores 324 * them in the caller allocated array out. The next index can be used to 325 * restart the scan. This optimizes forward scans in the tree. | 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. |
326 */ 327int 328vm_radix_lookupn(struct vm_radix *rtree, vm_pindex_t start, | 370 */ 371int 372vm_radix_lookupn(struct vm_radix *rtree, vm_pindex_t start, |
329 vm_pindex_t end, void **out, int cnt, vm_pindex_t *next) | 373 vm_pindex_t end, int color, void **out, int cnt, vm_pindex_t *next) |
330{ 331 struct vm_radix_node *rnode; | 374{ 375 struct vm_radix_node *rnode; |
332 struct vm_radix_node *child; 333 vm_pindex_t max; | |
334 vm_pindex_t inc; 335 int slot; 336 int level; 337 void *val; 338 int outidx; | 376 vm_pindex_t inc; 377 int slot; 378 int level; 379 void *val; 380 int outidx; |
339 int loops = 0; | |
340 341 CTR3(KTR_VM, "lookupn: tree %p, start %p, end %p", 342 rtree, (void *)start, (void *)end); 343 outidx = 0; 344restart: 345 level = vm_radix_height(rtree, &rnode); | 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); |
346 max = VM_RADIX_MAX(level); 347 if (start > max) | 387 if (rnode == NULL || start > VM_RADIX_MAX(level)) |
348 goto out; | 388 goto out; |
349 if (end > max || end == 0) 350 end = max; 351 loops++; 352 if (loops > 1000) 353 panic("vm_radix_lookupn: looping %d\n", loops); | 389 if (end && start >= end) 390 goto out; |
354 /* 355 * Search the tree from the top for any leaf node holding an index 356 * between start and end. 357 */ | 391 /* 392 * Search the tree from the top for any leaf node holding an index 393 * between start and end. 394 */ |
358 level--; 359 while (rnode) { | 395 for (level--; level; level--) { |
360 slot = vm_radix_slot(start, level); 361 CTR5(KTR_VM, 362 "lookupn: tree %p, index %p, level %d, slot %d, child %p", 363 rtree, (void *)start, level, slot, rnode->rn_child[slot]); | 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]); |
364 if (level == 0) 365 break; | 400 if (rnode->rn_child[slot] != NULL) { 401 rnode = rnode->rn_child[slot]; 402 continue; 403 } |
366 /* | 404 /* |
367 * If we don't have an exact match we must start our search 368 * from the next leaf and adjust our index appropriately. 369 */ 370 if ((child = rnode->rn_child[slot]) == NULL) { 371 /* 372 * Calculate how much to increment our index by 373 * based on the tree level. We must truncate the 374 * lower bits to start from the begnning of the next 375 * leaf. 376 */ 377 inc = 1LL << (level * VM_RADIX_WIDTH); 378 start &= ~VM_RADIX_MAX(level); 379 start += inc; 380 slot++; 381 CTR5(KTR_VM, 382 "lookupn: start %p end %p inc %d mask 0x%lX slot %d", 383 (void *)start, (void *)end, inc, ~VM_RADIX_MAX(level), slot); 384 for (; slot < VM_RADIX_COUNT && start <= end; 385 slot++, start += inc) { 386 child = rnode->rn_child[slot]; 387 if (child) 388 break; | 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; |
389 } 390 } | 424 } 425 } |
391 rnode = child; 392 level--; 393 } 394 if (rnode == NULL) { 395 /* 396 * If we still have another range to search, start looking 397 * from the next node. Otherwise, return what we've already 398 * found. The loop above has already adjusted start to the 399 * beginning of the next node. 400 * 401 * Detect start wrapping back to 0 and return in this case. 402 */ 403 if (start <= end && start != 0) | 426 if (slot == VM_RADIX_COUNT) |
404 goto restart; | 427 goto restart; |
405 goto out; | |
406 } | 428 } |
407 for (; outidx < cnt && slot < VM_RADIX_COUNT && start <= end; 408 slot++, start++) { 409 val = rnode->rn_child[slot]; | 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); |
410 if (val == NULL) 411 continue; | 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); |
|
412 out[outidx++] = val; | 439 out[outidx++] = val; |
440 if (outidx == cnt) 441 goto out; |
|
413 } 414 /* 415 * Go fetch the next page to fill the requested number of pages 416 * otherwise the caller will simply call us again to fulfill the 417 * same request after the structures are pushed out of cache. 418 */ | 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 */ |
419 if (outidx < cnt && start <= end) | 448 if ((end == 0 || start < end)) |
420 goto restart; | 449 goto restart; |
421 | |
422out: 423 *next = start; 424 425 return (outidx); 426} 427 428/* 429 * Look up any entry at a position less than or equal to index. 430 */ 431void * | 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 * |
432vm_radix_lookup_le(struct vm_radix *rtree, vm_pindex_t index) | 460vm_radix_lookup_le(struct vm_radix *rtree, vm_pindex_t index, int color) |
433{ 434 struct vm_radix_node *rnode; 435 struct vm_radix_node *child; 436 vm_pindex_t max; 437 vm_pindex_t inc; | 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; |
|
438 int slot; 439 int level; | 467 int slot; 468 int level; |
440 int loops = 0; | |
441 442 CTR2(KTR_VM, 443 "lookup_le: tree %p, index %p", rtree, (void *)index); 444restart: 445 level = vm_radix_height(rtree, &rnode); 446 if (rnode == NULL) 447 return (NULL); 448 max = VM_RADIX_MAX(level); 449 if (index > max || index == 0) 450 index = max; | 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; |
451 loops++; 452 if (loops > 1000) 453 panic("vm_radix_looku_le: looping %d\n", loops); | |
454 /* 455 * Search the tree from the top for any leaf node holding an index 456 * lower than 'index'. 457 */ 458 level--; 459 while (rnode) { 460 slot = vm_radix_slot(index, level); 461 CTR5(KTR_VM, --- 25 unchanged lines hidden (view full) --- 487 break; 488 } 489 } 490 rnode = child; 491 level--; 492 } 493 if (rnode) { 494 for (; slot >= 0; slot--, index--) { | 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--) { |
495 if (rnode->rn_child[slot]) 496 return (rnode->rn_child[slot]); | 520 val = vm_radix_match(rnode->rn_child[slot], color); 521 if (val) 522 return (val); |
497 } 498 } 499 if (index != -1) 500 goto restart; 501 return (NULL); 502} 503 504/* 505 * Remove the specified index from the tree. If possible the height of the 506 * tree is adjusted after deletion. The value stored at index is returned 507 * panics if the key is not present. 508 */ 509void * | 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 * |
510vm_radix_remove(struct vm_radix *rtree, vm_pindex_t index) | 536vm_radix_remove(struct vm_radix *rtree, vm_pindex_t index, int color) |
511{ 512 struct vm_radix_node *stack[VM_RADIX_LIMIT]; 513 struct vm_radix_node *rnode, *root; 514 void *val; 515 int level; 516 int slot; 517 518 level = vm_radix_height(rtree, &root); --- 10 unchanged lines hidden (view full) --- 529 stack[level] = rnode; 530 slot = vm_radix_slot(index, level); 531 rnode = rnode->rn_child[slot]; 532 CTR5(KTR_VM, 533 "remove: tree %p, index %p, level %d, slot %d, child %p", 534 rtree, (void *)index, level, slot, rnode->rn_child[slot]); 535 level--; 536 } | 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)); |
|
537 slot = vm_radix_slot(index, 0); | 565 slot = vm_radix_slot(index, 0); |
538 KASSERT(rnode != NULL && rnode->rn_child[slot] != NULL, | 566 val = vm_radix_match(rnode->rn_child[slot], color); 567 KASSERT(val != NULL, |
539 ("vm_radix_remove: index %jd not present in the tree.\n", index)); 540 | 568 ("vm_radix_remove: index %jd not present in the tree.\n", index)); 569 |
541 val = rnode->rn_child[slot]; | |
542 for (;;) { 543 rnode->rn_child[slot] = NULL; | 570 for (;;) { 571 rnode->rn_child[slot] = NULL; |
544 rnode->rn_count--; 545 if (rnode->rn_count > 0) | 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) |
546 break; 547 vm_radix_node_put(rnode); 548 if (rnode == root) { 549 vm_radix_setroot(rtree, NULL, 0); 550 break; 551 } 552 rnode = stack[++level]; 553 slot = vm_radix_slot(index, level); --- 34 unchanged lines hidden --- | 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 --- |