Rev 1148 | Rev 1178 | Go to most recent revision | Show entire file | Regard whitespace | Details | Blame | Last modification | View Log | RSS feed
Rev 1148 | Rev 1150 | ||
---|---|---|---|
Line 523... | Line 523... | ||
523 | spinlock_lock(&a->lock); |
523 | spinlock_lock(&a->lock); |
524 | return a; |
524 | return a; |
525 | } |
525 | } |
526 | 526 | ||
527 | /* |
527 | /* |
528 | * Search the leaf node and the righmost record of its left sibling |
528 | * Search the leaf node and the righmost record of its left neighbour |
529 | * to find out whether this is a miss or va belongs to an address |
529 | * to find out whether this is a miss or va belongs to an address |
530 | * space area found there. |
530 | * space area found there. |
531 | */ |
531 | */ |
532 | 532 | ||
533 | /* First, search the leaf node itself. */ |
533 | /* First, search the leaf node itself. */ |
Line 539... | Line 539... | ||
539 | } |
539 | } |
540 | spinlock_unlock(&a->lock); |
540 | spinlock_unlock(&a->lock); |
541 | } |
541 | } |
542 | 542 | ||
543 | /* |
543 | /* |
544 | * Second, locate the left sibling and test its last record. |
544 | * Second, locate the left neighbour and test its last record. |
545 | * Because of its position in the B+tree, it must have base < va. |
545 | * Because of its position in the B+tree, it must have base < va. |
546 | */ |
546 | */ |
547 | if ((lnode = btree_node_left_sibling(&as->as_area_btree, leaf))) { |
547 | if ((lnode = btree_leaf_node_left_neighbour(&as->as_area_btree, leaf))) { |
548 | a = (as_area_t *) lnode->value[lnode->keys - 1]; |
548 | a = (as_area_t *) lnode->value[lnode->keys - 1]; |
549 | spinlock_lock(&a->lock); |
549 | spinlock_lock(&a->lock); |
550 | if (va < a->base + a->pages * PAGE_SIZE) { |
550 | if (va < a->base + a->pages * PAGE_SIZE) { |
551 | return a; |
551 | return a; |
552 | } |
552 | } |
Line 581... | Line 581... | ||
581 | 581 | ||
582 | /* |
582 | /* |
583 | * The leaf node is found in O(log n), where n is proportional to |
583 | * The leaf node is found in O(log n), where n is proportional to |
584 | * the number of address space areas belonging to as. |
584 | * the number of address space areas belonging to as. |
585 | * The check for conflicts is then attempted on the rightmost |
585 | * The check for conflicts is then attempted on the rightmost |
586 | * record in the left sibling, the leftmost record in the right |
586 | * record in the left neighbour, the leftmost record in the right |
587 | * sibling and all records in the leaf node itself. |
587 | * neighbour and all records in the leaf node itself. |
588 | */ |
588 | */ |
589 | 589 | ||
590 | if ((a = (as_area_t *) btree_search(&as->as_area_btree, va, &leaf))) { |
590 | if ((a = (as_area_t *) btree_search(&as->as_area_btree, va, &leaf))) { |
591 | if (a != avoid_area) |
591 | if (a != avoid_area) |
592 | return false; |
592 | return false; |
593 | } |
593 | } |
594 | 594 | ||
595 | /* First, check the two border cases. */ |
595 | /* First, check the two border cases. */ |
596 | if ((node = btree_node_left_sibling(&as->as_area_btree, leaf))) { |
596 | if ((node = btree_leaf_node_left_neighbour(&as->as_area_btree, leaf))) { |
597 | a = (as_area_t *) node->value[node->keys - 1]; |
597 | a = (as_area_t *) node->value[node->keys - 1]; |
598 | spinlock_lock(&a->lock); |
598 | spinlock_lock(&a->lock); |
599 | if (overlaps(va, size, a->base, a->pages * PAGE_SIZE)) { |
599 | if (overlaps(va, size, a->base, a->pages * PAGE_SIZE)) { |
600 | spinlock_unlock(&a->lock); |
600 | spinlock_unlock(&a->lock); |
601 | return false; |
601 | return false; |
602 | } |
602 | } |
603 | spinlock_unlock(&a->lock); |
603 | spinlock_unlock(&a->lock); |
604 | } |
604 | } |
605 | if ((node = btree_node_right_sibling(&as->as_area_btree, leaf))) { |
605 | if ((node = btree_leaf_node_right_neighbour(&as->as_area_btree, leaf))) { |
606 | a = (as_area_t *) node->value[0]; |
606 | a = (as_area_t *) node->value[0]; |
607 | spinlock_lock(&a->lock); |
607 | spinlock_lock(&a->lock); |
608 | if (overlaps(va, size, a->base, a->pages * PAGE_SIZE)) { |
608 | if (overlaps(va, size, a->base, a->pages * PAGE_SIZE)) { |
609 | spinlock_unlock(&a->lock); |
609 | spinlock_unlock(&a->lock); |
610 | return false; |
610 | return false; |