Rev 1108 | Rev 1148 | Go to most recent revision | Show entire file | Ignore whitespace | Details | Blame | Last modification | View Log | RSS feed
Rev 1108 | Rev 1147 | ||
---|---|---|---|
Line 46... | Line 46... | ||
46 | #include <arch/types.h> |
46 | #include <arch/types.h> |
47 | #include <typedefs.h> |
47 | #include <typedefs.h> |
48 | #include <synch/spinlock.h> |
48 | #include <synch/spinlock.h> |
49 | #include <config.h> |
49 | #include <config.h> |
50 | #include <adt/list.h> |
50 | #include <adt/list.h> |
- | 51 | #include <adt/btree.h> |
|
51 | #include <panic.h> |
52 | #include <panic.h> |
52 | #include <arch/asm.h> |
53 | #include <arch/asm.h> |
53 | #include <debug.h> |
54 | #include <debug.h> |
54 | #include <memstr.h> |
55 | #include <memstr.h> |
55 | #include <macros.h> |
56 | #include <macros.h> |
Line 92... | Line 93... | ||
92 | as_t *as; |
93 | as_t *as; |
93 | 94 | ||
94 | as = (as_t *) malloc(sizeof(as_t), 0); |
95 | as = (as_t *) malloc(sizeof(as_t), 0); |
95 | link_initialize(&as->inactive_as_with_asid_link); |
96 | link_initialize(&as->inactive_as_with_asid_link); |
96 | spinlock_initialize(&as->lock, "as_lock"); |
97 | spinlock_initialize(&as->lock, "as_lock"); |
97 | list_initialize(&as->as_area_head); |
98 | btree_create(&as->as_area_btree); |
98 | 99 | ||
99 | if (flags & FLAG_AS_KERNEL) |
100 | if (flags & FLAG_AS_KERNEL) |
100 | as->asid = ASID_KERNEL; |
101 | as->asid = ASID_KERNEL; |
101 | else |
102 | else |
102 | as->asid = ASID_INVALID; |
103 | as->asid = ASID_INVALID; |
Line 151... | Line 152... | ||
151 | 152 | ||
152 | a = (as_area_t *) malloc(sizeof(as_area_t), 0); |
153 | a = (as_area_t *) malloc(sizeof(as_area_t), 0); |
153 | 154 | ||
154 | spinlock_initialize(&a->lock, "as_area_lock"); |
155 | spinlock_initialize(&a->lock, "as_area_lock"); |
155 | 156 | ||
156 | link_initialize(&a->link); |
- | |
157 | a->flags = flags; |
157 | a->flags = flags; |
158 | a->pages = SIZE2FRAMES(size); |
158 | a->pages = SIZE2FRAMES(size); |
159 | a->base = base; |
159 | a->base = base; |
160 | 160 | ||
161 | list_append(&a->link, &as->as_area_head); |
161 | btree_insert(&as->as_area_btree, base, (void *) a, NULL); |
162 | 162 | ||
163 | spinlock_unlock(&as->lock); |
163 | spinlock_unlock(&as->lock); |
164 | interrupts_restore(ipl); |
164 | interrupts_restore(ipl); |
165 | 165 | ||
166 | return a; |
166 | return a; |
Line 443... | Line 443... | ||
443 | interrupts_restore(ipl); |
443 | interrupts_restore(ipl); |
444 | return (__address) -1; |
444 | return (__address) -1; |
445 | } |
445 | } |
446 | 446 | ||
447 | pages = SIZE2FRAMES((address - area->base) + size); |
447 | pages = SIZE2FRAMES((address - area->base) + size); |
448 | if (!check_area_conflicts(as, address, pages * PAGE_SIZE, area)) { |
- | |
449 | spinlock_unlock(&area->lock); |
- | |
450 | spinlock_unlock(&as->lock); |
- | |
451 | interrupts_restore(ipl); |
- | |
452 | return (__address) -1; |
- | |
453 | } |
- | |
454 | - | ||
455 | if (pages < area->pages) { |
448 | if (pages < area->pages) { |
456 | int i; |
449 | int i; |
457 | 450 | ||
458 | /* |
451 | /* |
459 | * Shrinking the area. |
452 | * Shrinking the area. |
- | 453 | * No need to check for overlaps. |
|
460 | */ |
454 | */ |
461 | for (i = pages; i < area->pages; i++) { |
455 | for (i = pages; i < area->pages; i++) { |
462 | pte_t *pte; |
456 | pte_t *pte; |
463 | 457 | ||
464 | /* |
458 | /* |
Line 484... | Line 478... | ||
484 | * Invalidate TLB's. |
478 | * Invalidate TLB's. |
485 | */ |
479 | */ |
486 | tlb_shootdown_start(TLB_INVL_PAGES, AS->asid, area->base + pages*PAGE_SIZE, area->pages - pages); |
480 | tlb_shootdown_start(TLB_INVL_PAGES, AS->asid, area->base + pages*PAGE_SIZE, area->pages - pages); |
487 | tlb_invalidate_pages(AS->asid, area->base + pages*PAGE_SIZE, area->pages - pages); |
481 | tlb_invalidate_pages(AS->asid, area->base + pages*PAGE_SIZE, area->pages - pages); |
488 | tlb_shootdown_finalize(); |
482 | tlb_shootdown_finalize(); |
- | 483 | } else { |
|
- | 484 | /* |
|
- | 485 | * Growing the area. |
|
- | 486 | * Check for overlaps with other address space areas. |
|
- | 487 | */ |
|
- | 488 | if (!check_area_conflicts(as, address, pages * PAGE_SIZE, area)) { |
|
- | 489 | spinlock_unlock(&area->lock); |
|
- | 490 | spinlock_unlock(&as->lock); |
|
- | 491 | interrupts_restore(ipl); |
|
- | 492 | return (__address) -1; |
|
- | 493 | } |
|
489 | } |
494 | } |
490 | 495 | ||
491 | area->pages = pages; |
496 | area->pages = pages; |
492 | 497 | ||
493 | spinlock_unlock(&area->lock); |
498 | spinlock_unlock(&area->lock); |
Line 506... | Line 511... | ||
506 | * |
511 | * |
507 | * @return Locked address space area containing va on success or NULL on failure. |
512 | * @return Locked address space area containing va on success or NULL on failure. |
508 | */ |
513 | */ |
509 | as_area_t *find_area_and_lock(as_t *as, __address va) |
514 | as_area_t *find_area_and_lock(as_t *as, __address va) |
510 | { |
515 | { |
511 | link_t *cur; |
- | |
512 | as_area_t *a; |
516 | as_area_t *a; |
- | 517 | btree_node_t *leaf, *lnode; |
|
- | 518 | int i; |
|
- | 519 | ||
- | 520 | a = (as_area_t *) btree_search(&as->as_area_btree, va, &leaf); |
|
- | 521 | if (a) { |
|
- | 522 | /* va is the base address of an address space area */ |
|
- | 523 | spinlock_lock(&a->lock); |
|
- | 524 | return a; |
|
- | 525 | } |
|
513 | 526 | ||
- | 527 | /* |
|
514 | for (cur = as->as_area_head.next; cur != &as->as_area_head; cur = cur->next) { |
528 | * Search the leaf node and the righmost record of its left sibling |
- | 529 | * to find out whether this is a miss or va belongs to an address |
|
- | 530 | * space area found there. |
|
- | 531 | */ |
|
- | 532 | ||
- | 533 | /* First, search the leaf node itself. */ |
|
- | 534 | for (i = 0; i < leaf->keys; i++) { |
|
515 | a = list_get_instance(cur, as_area_t, link); |
535 | a = (as_area_t *) leaf->value[i]; |
516 | spinlock_lock(&a->lock); |
536 | spinlock_lock(&a->lock); |
- | 537 | if ((a->base <= va) && (va < a->base + a->pages * PAGE_SIZE)) { |
|
- | 538 | return a; |
|
- | 539 | } |
|
- | 540 | spinlock_unlock(&a->lock); |
|
- | 541 | } |
|
517 | 542 | ||
- | 543 | /* |
|
- | 544 | * Second, locate the left sibling and test its last record. |
|
- | 545 | * Because of its position in the B+-tree, it must have base < va. |
|
- | 546 | */ |
|
- | 547 | if ((lnode = btree_node_left_sibling(&as->as_area_btree, leaf))) { |
|
- | 548 | a = (as_area_t *) lnode->value[lnode->keys - 1]; |
|
- | 549 | spinlock_lock(&a->lock); |
|
518 | if ((va >= a->base) && (va < a->base + a->pages * PAGE_SIZE)) |
550 | if (va < a->base + a->pages * PAGE_SIZE) { |
519 | return a; |
551 | return a; |
520 | 552 | } |
|
521 | spinlock_unlock(&a->lock); |
553 | spinlock_unlock(&a->lock); |
522 | } |
554 | } |
523 | 555 | ||
524 | return NULL; |
556 | return NULL; |
525 | } |
557 | } |
Line 535... | Line 567... | ||
535 | * |
567 | * |
536 | * @return True if there is no conflict, false otherwise. |
568 | * @return True if there is no conflict, false otherwise. |
537 | */ |
569 | */ |
538 | bool check_area_conflicts(as_t *as, __address va, size_t size, as_area_t *avoid_area) |
570 | bool check_area_conflicts(as_t *as, __address va, size_t size, as_area_t *avoid_area) |
539 | { |
571 | { |
540 | link_t *cur; |
- | |
541 | as_area_t *a; |
572 | as_area_t *a; |
- | 573 | btree_node_t *leaf, *node; |
|
- | 574 | int i; |
|
542 | 575 | ||
543 | /* |
576 | /* |
544 | * We don't want any area to have conflicts with NULL page. |
577 | * We don't want any area to have conflicts with NULL page. |
545 | */ |
578 | */ |
546 | if (overlaps(va, size, NULL, PAGE_SIZE)) |
579 | if (overlaps(va, size, NULL, PAGE_SIZE)) |
547 | return false; |
580 | return false; |
548 | 581 | ||
- | 582 | /* |
|
- | 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. |
|
- | 585 | * The check for conflicts is then attempted on the rightmost |
|
- | 586 | * record in the left sibling, the leftmost record in the right |
|
- | 587 | * sibling and all records in the leaf node itself. |
|
- | 588 | */ |
|
- | 589 | ||
549 | for (cur = as->as_area_head.next; cur != &as->as_area_head; cur = cur->next) { |
590 | if ((a = (as_area_t *) btree_search(&as->as_area_btree, va, &leaf))) { |
- | 591 | if (a != avoid_area) |
|
- | 592 | return false; |
|
- | 593 | } |
|
- | 594 | ||
- | 595 | /* First, check the two border cases. */ |
|
- | 596 | if ((node = btree_node_left_sibling(&as->as_area_btree, leaf))) { |
|
- | 597 | a = (as_area_t *) node->value[node->keys - 1]; |
|
- | 598 | spinlock_lock(&a->lock); |
|
- | 599 | if (overlaps(va, size, a->base, a->pages * PAGE_SIZE)) { |
|
- | 600 | spinlock_unlock(&a->lock); |
|
550 | __address a_start; |
601 | return false; |
- | 602 | } |
|
- | 603 | spinlock_unlock(&a->lock); |
|
- | 604 | } |
|
- | 605 | if ((node = btree_node_right_sibling(&as->as_area_btree, leaf))) { |
|
- | 606 | a = (as_area_t *) node->value[0]; |
|
- | 607 | spinlock_lock(&a->lock); |
|
- | 608 | if (overlaps(va, size, a->base, a->pages * PAGE_SIZE)) { |
|
- | 609 | spinlock_unlock(&a->lock); |
|
551 | size_t a_size; |
610 | return false; |
- | 611 | } |
|
- | 612 | spinlock_unlock(&a->lock); |
|
- | 613 | } |
|
- | 614 | ||
- | 615 | /* Second, check the leaf node. */ |
|
- | 616 | for (i = 0; i < leaf->keys; i++) { |
|
- | 617 | a = (as_area_t *) leaf->value[i]; |
|
552 | 618 | ||
553 | a = list_get_instance(cur, as_area_t, link); |
- | |
554 | if (a == avoid_area) |
619 | if (a == avoid_area) |
555 | continue; |
620 | continue; |
556 | 621 | ||
557 | spinlock_lock(&a->lock); |
622 | spinlock_lock(&a->lock); |
558 | - | ||
- | 623 | if (overlaps(va, size, a->base, a->pages * PAGE_SIZE)) { |
|
559 | a_start = a->base; |
624 | spinlock_unlock(&a->lock); |
560 | a_size = a->pages * PAGE_SIZE; |
625 | return false; |
561 | 626 | } |
|
562 | spinlock_unlock(&a->lock); |
627 | spinlock_unlock(&a->lock); |
563 | - | ||
564 | if (overlaps(va, size, a_start, a_size)) |
- | |
565 | return false; |
- | |
566 | - | ||
567 | } |
628 | } |
568 | 629 | ||
569 | /* |
630 | /* |
570 | * So far, the area does not conflict with other areas. |
631 | * So far, the area does not conflict with other areas. |
571 | * Check if it doesn't conflict with kernel address space. |
632 | * Check if it doesn't conflict with kernel address space. |