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

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

472 return NULL;
473}
474
475/*
476 * Find the first leaf with a valid node between *startp and end. Return
477 * the index of the first valid item in the leaf in *startp.
478 */
479static struct vm_radix_node *
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:

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

472 return NULL;
473}
474
475/*
476 * Find the first leaf with a valid node between *startp and end. Return
477 * the index of the first valid item in the leaf in *startp.
478 */
479static struct vm_radix_node *
480vm_radix_leaf(struct vm_radix *rtree, vm_pindex_t *startp, vm_pindex_t end)
480vm_radix_leaf(struct vm_radix *rtree, vm_pindex_t *startp)
481{
482 struct vm_radix_node *rnode;
483 vm_pindex_t start;
484 vm_pindex_t inc;
485 int slot;
486 int level;
487
488 start = *startp;
489restart:
490 level = vm_radix_height(rtree, &rnode);
481{
482 struct vm_radix_node *rnode;
483 vm_pindex_t start;
484 vm_pindex_t inc;
485 int slot;
486 int level;
487
488 start = *startp;
489restart:
490 level = vm_radix_height(rtree, &rnode);
491 if (start > VM_RADIX_MAX(level) || (end && start >= end)) {
491 if (start > VM_RADIX_MAX(level)) {
492 rnode = NULL;
493 goto out;
494 }
495 /*
496 * Search the tree from the top for any leaf node holding an index
492 rnode = NULL;
493 goto out;
494 }
495 /*
496 * Search the tree from the top for any leaf node holding an index
497 * between start and end.
497 * between start and maxval.
498 */
499 for (level--; level; level--) {
500 slot = vm_radix_slot(start, level);
501 CTR6(KTR_VM,
502 "leaf: tree %p, " KFRMT64(start) ", level %d, slot %d, rnode %p",
503 rtree, KSPLT64L(start), KSPLT64H(start), level, slot,
504 rnode);
505 CTR2(KTR_VM, "leaf: rnode %p, child %p", rnode,

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

519
520 /* Avoid start address wrapping up. */
521 if ((VM_RADIX_MAXVAL - start) < inc) {
522 rnode = NULL;
523 goto out;
524 }
525 start += inc;
526 slot++;
498 */
499 for (level--; level; level--) {
500 slot = vm_radix_slot(start, level);
501 CTR6(KTR_VM,
502 "leaf: tree %p, " KFRMT64(start) ", level %d, slot %d, rnode %p",
503 rtree, KSPLT64L(start), KSPLT64H(start), level, slot,
504 rnode);
505 CTR2(KTR_VM, "leaf: rnode %p, child %p", rnode,

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

519
520 /* Avoid start address wrapping up. */
521 if ((VM_RADIX_MAXVAL - start) < inc) {
522 rnode = NULL;
523 goto out;
524 }
525 start += inc;
526 slot++;
527 CTR6(KTR_VM,
528 "leaf: " KFRMT64(start) ", " KFRMT64(end) ", " KFRMT64(inc),
529 KSPLT64L(start), KSPLT64H(start), KSPLT64L(end),
530 KSPLT64H(end), KSPLT64L(inc), KSPLT64H(inc));
527 CTR4(KTR_VM,
528 "leaf: " KFRMT64(start) ", " KFRMT64(inc),
529 KSPLT64L(start), KSPLT64H(start), KSPLT64L(inc),
530 KSPLT64H(inc));
531 CTR2(KTR_VM, "leaf: level %d, slot %d", level, slot);
532 for (; slot < VM_RADIX_COUNT; slot++, start += inc) {
531 CTR2(KTR_VM, "leaf: level %d, slot %d", level, slot);
532 for (; slot < VM_RADIX_COUNT; slot++, start += inc) {
533 if (end != 0 && start >= end) {
534 rnode = NULL;
535 goto out;
536 }
537 if (rnode->rn_child[slot]) {
538 rnode = rnode->rn_child[slot];
539 break;
540 }
541 if ((VM_RADIX_MAXVAL - start) < inc) {
542 rnode = NULL;
543 goto out;
544 }
545 }
546 if (slot == VM_RADIX_COUNT)
547 goto restart;
548 }
549
550out:
551 *startp = start;
552 return (rnode);
553}
554
533 if (rnode->rn_child[slot]) {
534 rnode = rnode->rn_child[slot];
535 break;
536 }
537 if ((VM_RADIX_MAXVAL - start) < inc) {
538 rnode = NULL;
539 goto out;
540 }
541 }
542 if (slot == VM_RADIX_COUNT)
543 goto restart;
544 }
545
546out:
547 *startp = start;
548 return (rnode);
549}
550
555
556
557/*
551/*
558 * Looks up as many as cnt values between start and end, and stores
559 * them in the caller allocated array out. The next index can be used
560 * to restart the scan. This optimizes forward scans in the tree.
552 * Look up any entry at a position bigger than or equal to index.
561 */
553 */
562int
563vm_radix_lookupn(struct vm_radix *rtree, vm_pindex_t start,
564 vm_pindex_t end, void **out, int cnt, vm_pindex_t *next, u_int *exhausted)
554void *
555vm_radix_lookup_ge(struct vm_radix *rtree, vm_pindex_t start)
565{
566 struct vm_radix_node *rnode;
567 void *val;
568 int slot;
556{
557 struct vm_radix_node *rnode;
558 void *val;
559 int slot;
569 int outidx;
570
560
571 CTR5(KTR_VM, "lookupn: tree %p, " KFRMT64(start) ", " KFRMT64(end),
572 rtree, KSPLT64L(start), KSPLT64H(start), KSPLT64L(end),
573 KSPLT64H(end));
574 if (end == 0)
575 *exhausted = 0;
561 CTR3(KTR_VM, "lookupn: tree %p, " KFRMT64(start), rtree,
562 KSPLT64L(start), KSPLT64H(start));
576 if (rtree->rt_root == 0)
563 if (rtree->rt_root == 0)
577 return (0);
578 outidx = 0;
579 while ((rnode = vm_radix_leaf(rtree, &start, end)) != NULL) {
564 return (NULL);
565 while ((rnode = vm_radix_leaf(rtree, &start)) != NULL) {
580 slot = vm_radix_slot(start, 0);
581 for (; slot < VM_RADIX_COUNT; slot++, start++) {
566 slot = vm_radix_slot(start, 0);
567 for (; slot < VM_RADIX_COUNT; slot++, start++) {
582 if (end != 0 && start >= end)
583 goto out;
584 val = vm_radix_match(rnode->rn_child[slot]);
585 if (val == NULL) {
586
587 /*
588 * The start address can wrap at the
589 * VM_RADIX_MAXVAL value.
590 * We need to make sure that start address
591 * point to the next chunk (even if wrapping)
592 * to stay consistent with default scanning
593 * behaviour. Also, because of the nature
594 * of the wrapping, the wrap up checks must
595 * be done after all the necessary controls
596 * on start are completed.
597 */
568 val = vm_radix_match(rnode->rn_child[slot]);
569 if (val == NULL) {
570
571 /*
572 * The start address can wrap at the
573 * VM_RADIX_MAXVAL value.
574 * We need to make sure that start address
575 * point to the next chunk (even if wrapping)
576 * to stay consistent with default scanning
577 * behaviour. Also, because of the nature
578 * of the wrapping, the wrap up checks must
579 * be done after all the necessary controls
580 * on start are completed.
581 */
598 if ((VM_RADIX_MAXVAL - start) == 0) {
599 start++;
600 if (end == 0)
601 *exhausted = 1;
602 goto out;
603 }
582 if ((VM_RADIX_MAXVAL - start) == 0)
583 return (NULL);
604 continue;
605 }
606 CTR5(KTR_VM,
607 "lookupn: tree %p " KFRMT64(index) " slot %d found child %p",
608 rtree, KSPLT64L(start), KSPLT64H(start), slot, val);
584 continue;
585 }
586 CTR5(KTR_VM,
587 "lookupn: tree %p " KFRMT64(index) " slot %d found child %p",
588 rtree, KSPLT64L(start), KSPLT64H(start), slot, val);
609 out[outidx] = val;
610 if (++outidx == cnt ||
611 (VM_RADIX_MAXVAL - start) == 0) {
612 start++;
613 if ((VM_RADIX_MAXVAL - start) == 0 && end == 0)
614 *exhausted = 1;
615 goto out;
616 }
589 return (val);
617 }
618 MPASS((VM_RADIX_MAXVAL - start) != 0);
590 }
591 MPASS((VM_RADIX_MAXVAL - start) != 0);
619 if (end != 0 && start >= end)
620 break;
621 }
592 }
622out:
623 *next = start;
624 return (outidx);
593 return (NULL);
625}
626
627/*
628 * Look up any entry at a position less than or equal to index.
629 */
630void *
631vm_radix_lookup_le(struct vm_radix *rtree, vm_pindex_t index)
632{

--- 161 unchanged lines hidden --- 		594}
595
596/*
597 * Look up any entry at a position less than or equal to index.
598 */
599void *
600vm_radix_lookup_le(struct vm_radix *rtree, vm_pindex_t index)
601{

--- 161 unchanged lines hidden ---