Deleted Added
sdiff udiff text old ( 226930 ) new ( 226952 )
full compact
vm_radix.c (226930) vm_radix.c (226952)
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:

--- 350 unchanged lines hidden (view full) ---

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/*
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:

--- 350 unchanged lines hidden (view full) ---

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.
367 * Find the first leaf with a valid node between *startp and end. Return
368 * the index of the first valid item in the leaf in *startp.
370 */
369 */
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)
370static struct vm_radix_node *
371vm_radix_leaf(struct vm_radix *rtree, vm_pindex_t *startp, vm_pindex_t end)
374{
375 struct vm_radix_node *rnode;
372{
373 struct vm_radix_node *rnode;
374 vm_pindex_t start;
376 vm_pindex_t inc;
377 int slot;
378 int level;
375 vm_pindex_t inc;
376 int slot;
377 int level;
379 void *val;
380 int outidx;
381
378
382 CTR3(KTR_VM, "lookupn: tree %p, start %p, end %p",
383 rtree, (void *)start, (void *)end);
384 outidx = 0;
379 start = *startp;
385restart:
386 level = vm_radix_height(rtree, &rnode);
380restart:
381 level = vm_radix_height(rtree, &rnode);
387 if (rnode == NULL || start > VM_RADIX_MAX(level))
382 if (start > VM_RADIX_MAX(level) || (end && start >= end)) {
383 rnode = NULL;
388 goto out;
384 goto out;
389 if (end && start >= end)
390 goto out;
385 }
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,
386 /*
387 * Search the tree from the top for any leaf node holding an index
388 * between start and end.
389 */
390 for (level--; level; level--) {
391 slot = vm_radix_slot(start, level);
392 CTR5(KTR_VM,
398 "lookupn: tree %p, index %p, level %d, slot %d, child %p",
393 "leaf: 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,
394 rtree, (void *)start, level, slot, rnode->rn_child[slot]);
395 if (rnode->rn_child[slot] != NULL) {
396 rnode = rnode->rn_child[slot];
397 continue;
398 }
399 /*
400 * Calculate how much to increment our index by
401 * based on the tree level. We must truncate the
402 * lower bits to start from the begnning of the
403 * next leaf.
404 */
405 inc = 1LL << (level * VM_RADIX_WIDTH);
406 start &= ~VM_RADIX_MAX(level);
407 start += inc;
408 slot++;
409 CTR5(KTR_VM,
415 "lookupn: start %p end %p inc %d mask 0x%lX slot %d",
410 "leaf: 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) {
411 (void *)start, (void *)end, inc,
412 ~VM_RADIX_MAX(level), slot);
413 for (; slot < VM_RADIX_COUNT; slot++, start += inc) {
419 if (end != 0 && start >= end)
414 if (end != 0 && start >= end) {
415 rnode = NULL;
420 goto out;
416 goto out;
417 }
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 }
418 if (rnode->rn_child[slot]) {
419 rnode = rnode->rn_child[slot];
420 break;
421 }
422 }
423 if (slot == VM_RADIX_COUNT)
424 goto restart;
425 }
429 slot = vm_radix_slot(start, 0);
430 for (; slot < VM_RADIX_COUNT; slot++, start++) {
426
427out:
428 *startp = start;
429 return (rnode);
430}
431
432
433
434/*
435 * Looks up as many as cnt values between start and end, and stores
436 * them in the caller allocated array out. The next index can be used
437 * to restart the scan. This optimizes forward scans in the tree.
438 */
439int
440vm_radix_lookupn(struct vm_radix *rtree, vm_pindex_t start,
441 vm_pindex_t end, int color, void **out, int cnt, vm_pindex_t *next)
442{
443 struct vm_radix_node *rnode;
444 void *val;
445 int slot;
446 int outidx;
447
448 CTR3(KTR_VM, "lookupn: tree %p, start %p, end %p",
449 rtree, (void *)start, (void *)end);
450 if (rtree->rt_root == 0)
451 return (0);
452 outidx = 0;
453 while ((rnode = vm_radix_leaf(rtree, &start, end)) != NULL) {
454 slot = vm_radix_slot(start, 0);
455 for (; slot < VM_RADIX_COUNT; slot++, start++) {
456 if (end != 0 && start >= end)
457 goto out;
458 val = vm_radix_match(rnode->rn_child[slot], color);
459 if (val == NULL)
460 continue;
461 CTR4(KTR_VM,
462 "lookupn: tree %p index %p slot %d found child %p",
463 rtree, (void *)start, slot, val);
464 out[outidx] = val;
465 if (++outidx == cnt)
466 goto out;
467 }
431 if (end != 0 && start >= end)
468 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;
469 break;
442 }
470 }
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;
471out:
472 *next = start;
452
453 return (outidx);
454}
455
473 return (outidx);
474}
475
476void
477vm_radix_foreach(struct vm_radix *rtree, vm_pindex_t start, vm_pindex_t end,
478 int color, void (*iter)(void *))
479{
480 struct vm_radix_node *rnode;
481 void *val;
482 int slot;
483
484 if (rtree->rt_root == 0)
485 return;
486 while ((rnode = vm_radix_leaf(rtree, &start, end)) != NULL) {
487 slot = vm_radix_slot(start, 0);
488 for (; slot < VM_RADIX_COUNT; slot++, start++) {
489 if (end != 0 && start >= end)
490 return;
491 val = vm_radix_match(rnode->rn_child[slot], color);
492 if (val)
493 iter(val);
494 }
495 if (end != 0 && start >= end)
496 return;
497 }
498}
499
500
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;

--- 162 unchanged lines hidden --- 		501/*
502 * Look up any entry at a position less than or equal to index.
503 */
504void *
505vm_radix_lookup_le(struct vm_radix *rtree, vm_pindex_t index, int color)
506{
507 struct vm_radix_node *rnode;
508 struct vm_radix_node *child;

--- 162 unchanged lines hidden ---