Rev 1148 | Rev 1178 | Go to most recent revision | Show entire file | Ignore 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; |