92,8 → 92,8 |
static int get_area_flags(as_area_t *a); |
static as_area_t *find_area_and_lock(as_t *as, __address va); |
static bool check_area_conflicts(as_t *as, __address va, size_t size, as_area_t *avoid_area); |
static int used_space_insert(as_area_t *a, __address page, count_t count); |
static int used_space_remove(as_area_t *a, __address page, count_t count); |
int used_space_insert(as_area_t *a, __address page, count_t count); |
int used_space_remove(as_area_t *a, __address page, count_t count); |
|
/** Initialize address space subsystem. */ |
void as_init(void) |
244,70 → 244,34 |
} |
|
if (pages < area->pages) { |
bool cond; |
__address start_free = area->base + pages*PAGE_SIZE; |
int i; |
|
/* |
* Shrinking the area. |
* No need to check for overlaps. |
*/ |
for (i = pages; i < area->pages; i++) { |
pte_t *pte; |
|
/* |
* Remove frames belonging to used space starting from |
* the highest addresses downwards until an overlap with |
* the resized address space area is found. Note that this |
* is also the right way to remove part of the used_space |
* B+tree leaf list. |
* Releasing physical memory. |
* This depends on the fact that the memory was allocated using frame_alloc(). |
*/ |
for (cond = true; cond;) { |
btree_node_t *node; |
page_table_lock(as, false); |
pte = page_mapping_find(as, area->base + i*PAGE_SIZE); |
if (pte && PTE_VALID(pte)) { |
__address frame; |
|
ASSERT(!list_empty(&area->used_space.leaf_head)); |
node = list_get_instance(area->used_space.leaf_head.prev, btree_node_t, leaf_link); |
if ((cond = (bool) node->keys)) { |
__address b = node->key[node->keys - 1]; |
count_t c = (count_t) node->value[node->keys - 1]; |
int i = 0; |
ASSERT(PTE_PRESENT(pte)); |
frame = PTE_GET_FRAME(pte); |
page_mapping_remove(as, area->base + i*PAGE_SIZE); |
page_table_unlock(as, false); |
|
if (overlaps(b, c*PAGE_SIZE, area->base, pages*PAGE_SIZE)) { |
|
if (b + c*PAGE_SIZE <= start_free) { |
/* |
* The whole interval fits completely |
* in the resized address space area. |
*/ |
break; |
} |
|
/* |
* Part of the interval corresponding to b and c |
* overlaps with the resized address space area. |
*/ |
|
cond = false; /* we are almost done */ |
i = (start_free - b) >> PAGE_WIDTH; |
if (!used_space_remove(area, start_free, c - i)) |
panic("Could not remove used space."); |
frame_free(ADDR2PFN(frame)); |
} else { |
/* |
* The interval of used space can be completely removed. |
*/ |
if (!used_space_remove(area, b, c)) |
panic("Could not remove used space.\n"); |
} |
|
for (; i < c; i++) { |
pte_t *pte; |
|
page_table_lock(as, false); |
pte = page_mapping_find(as, b + i*PAGE_SIZE); |
ASSERT(pte && PTE_VALID(pte) && PTE_PRESENT(pte)); |
frame_free(ADDR2PFN(PTE_GET_FRAME(pte))); |
page_mapping_remove(as, b + i*PAGE_SIZE); |
page_table_unlock(as, false); |
} |
} |
} |
/* |
* Invalidate TLB's. |
*/ |
348,6 → 312,7 |
as_area_t *area; |
__address base; |
ipl_t ipl; |
int i; |
|
ipl = interrupts_disable(); |
mutex_lock(&as->lock); |
360,8 → 325,8 |
} |
|
base = area->base; |
if (!(area->flags & AS_AREA_DEVICE)) { |
bool cond; |
for (i = 0; i < area->pages; i++) { |
pte_t *pte; |
|
/* |
* Releasing physical memory. |
368,40 → 333,21 |
* Areas mapping memory-mapped devices are treated differently than |
* areas backing frame_alloc()'ed memory. |
*/ |
|
/* |
* Visit only the pages mapped by used_space B+tree. |
* Note that we must be very careful when walking the tree |
* leaf list and removing used space as the leaf list changes |
* unpredictibly after each remove. The solution is to actually |
* not walk the tree at all, but to remove items from the head |
* of the leaf list until there are some keys left. |
*/ |
for (cond = true; cond;) { |
btree_node_t *node; |
|
ASSERT(!list_empty(&area->used_space.leaf_head)); |
node = list_get_instance(area->used_space.leaf_head.next, btree_node_t, leaf_link); |
if ((cond = (bool) node->keys)) { |
__address b = node->key[0]; |
count_t i; |
pte_t *pte; |
|
for (i = 0; i < (count_t) node->value[0]; i++) { |
page_table_lock(as, false); |
pte = page_mapping_find(as, b + i*PAGE_SIZE); |
ASSERT(pte && PTE_VALID(pte) && PTE_PRESENT(pte)); |
frame_free(ADDR2PFN(PTE_GET_FRAME(pte))); |
page_mapping_remove(as, b + i*PAGE_SIZE); |
pte = page_mapping_find(as, area->base + i*PAGE_SIZE); |
if (pte && PTE_VALID(pte)) { |
ASSERT(PTE_PRESENT(pte)); |
page_mapping_remove(as, area->base + i*PAGE_SIZE); |
if (area->flags & AS_AREA_DEVICE) { |
__address frame; |
frame = PTE_GET_FRAME(pte); |
frame_free(ADDR2PFN(frame)); |
} |
page_table_unlock(as, false); |
} else { |
page_table_unlock(as, false); |
} |
if (!used_space_remove(area, b, i)) |
panic("Could not remove used space.\n"); |
} |
} |
} |
btree_destroy(&area->used_space); |
|
/* |
* Invalidate TLB's. |
*/ |
473,6 → 419,7 |
mutex_unlock(&src_area->lock); |
mutex_unlock(&src_as->lock); |
|
|
if (src_size != acc_size) { |
spinlock_unlock(&src_task->lock); |
interrupts_restore(ipl); |
565,12 → 512,10 |
|
area = find_area_and_lock(as, page); |
if (!area) { |
panic("Page not part of any as_area.\n"); |
panic("page not part of any as_area\n"); |
} |
|
page_mapping_insert(as, page, frame, get_area_flags(area)); |
if (!used_space_insert(area, page, 1)) |
panic("Could not insert used space.\n"); |
|
mutex_unlock(&area->lock); |
page_table_unlock(as, true); |
660,8 → 605,6 |
* inserted into page tables. |
*/ |
page_mapping_insert(AS, page, frame, get_area_flags(area)); |
if (!used_space_insert(area, ALIGN_DOWN(page, PAGE_SIZE), 1)) |
panic("Could not insert used space.\n"); |
page_table_unlock(AS, false); |
|
mutex_unlock(&area->lock); |
1053,12 → 996,12 |
return 0; |
} else if ((page == left_pg + left_cnt*PAGE_SIZE) && (page + count*PAGE_SIZE == right_pg)) { |
/* The interval can be added by merging the two already present intervals. */ |
node->value[node->keys - 1] += count + right_cnt; |
node->value[node->keys - 1] += (count_t) count + right_cnt; |
btree_remove(&a->used_space, right_pg, leaf); |
return 1; |
} else if (page == left_pg + left_cnt*PAGE_SIZE) { |
/* The interval can be added by simply growing the left interval. */ |
node->value[node->keys - 1] += count; |
node->value[node->keys - 1] += (count_t) count; |
return 1; |
} else if (page + count*PAGE_SIZE == right_pg) { |
/* |
1065,7 → 1008,7 |
* The interval can be addded by simply moving base of the right |
* interval down and increasing its size accordingly. |
*/ |
leaf->value[0] += count; |
leaf->value[0] += (count_t) count; |
leaf->key[0] = page; |
return 1; |
} else { |
1094,7 → 1037,7 |
* and increasing its size accordingly. |
*/ |
leaf->key[0] = page; |
leaf->value[0] += count; |
leaf->value[0] += (count_t) count; |
return 1; |
} else { |
/* |
1127,12 → 1070,12 |
return 0; |
} else if ((page == left_pg + left_cnt*PAGE_SIZE) && (page + count*PAGE_SIZE == right_pg)) { |
/* The interval can be added by merging the two already present intervals. */ |
leaf->value[leaf->keys - 1] += count + right_cnt; |
leaf->value[leaf->keys - 1] += (count_t) count + right_cnt; |
btree_remove(&a->used_space, right_pg, node); |
return 1; |
} else if (page == left_pg + left_cnt*PAGE_SIZE) { |
/* The interval can be added by simply growing the left interval. */ |
leaf->value[leaf->keys - 1] += count; |
leaf->value[leaf->keys - 1] += (count_t) count; |
return 1; |
} else if (page + count*PAGE_SIZE == right_pg) { |
/* |
1139,7 → 1082,7 |
* The interval can be addded by simply moving base of the right |
* interval down and increasing its size accordingly. |
*/ |
node->value[0] += count; |
node->value[0] += (count_t) count; |
node->key[0] = page; |
return 1; |
} else { |
1160,11 → 1103,11 |
*/ |
|
if (overlaps(page, count*PAGE_SIZE, left_pg, left_cnt*PAGE_SIZE)) { |
/* The interval intersects with the left interval. */ |
/* The interval intersects with the right interval. */ |
return 0; |
} else if (left_pg + left_cnt*PAGE_SIZE == page) { |
/* The interval can be added by growing the left interval. */ |
leaf->value[leaf->keys - 1] += count; |
leaf->value[leaf->keys - 1] += (count_t) count; |
return 1; |
} else { |
/* |
1198,12 → 1141,12 |
return 0; |
} else if ((page == left_pg + left_cnt*PAGE_SIZE) && (page + count*PAGE_SIZE == right_pg)) { |
/* The interval can be added by merging the two already present intervals. */ |
leaf->value[i - 1] += count + right_cnt; |
leaf->value[i - 1] += (count_t) count + right_cnt; |
btree_remove(&a->used_space, right_pg, leaf); |
return 1; |
} else if (page == left_pg + left_cnt*PAGE_SIZE) { |
/* The interval can be added by simply growing the left interval. */ |
leaf->value[i - 1] += count; |
leaf->value[i - 1] += (count_t) count; |
return 1; |
} else if (page + count*PAGE_SIZE == right_pg) { |
/* |
1210,7 → 1153,7 |
* The interval can be addded by simply moving base of the right |
* interval down and increasing its size accordingly. |
*/ |
leaf->value[i] += count; |
leaf->value[i] += (count_t) count; |
leaf->key[i] = page; |
return 1; |
} else { |
1255,7 → 1198,6 |
return 0; |
} else if (count == pages) { |
btree_remove(&a->used_space, page, leaf); |
return 1; |
} else { |
/* |
* Find the respective interval. |
1264,7 → 1206,7 |
for (i = 0; i < leaf->keys; i++) { |
if (leaf->key[i] == page) { |
leaf->key[i] += count*PAGE_SIZE; |
leaf->value[i] -= count; |
leaf->value[i] -= (count_t) count; |
return 1; |
} |
} |
1284,10 → 1226,10 |
* of the left neighbour and can be removed by |
* updating the size of the bigger interval. |
*/ |
node->value[node->keys - 1] -= count; |
node->value[node->keys - 1] -= (count_t) count; |
return 1; |
} else if (page + count*PAGE_SIZE < left_pg + left_cnt*PAGE_SIZE) { |
count_t new_cnt; |
count_t new_cnt = (left_pg + left_cnt*PAGE_SIZE) - (page + count*PAGE_SIZE); |
|
/* |
* The interval is contained in the rightmost interval |
1295,8 → 1237,7 |
* both updating the size of the original interval and |
* also inserting a new interval. |
*/ |
new_cnt = ((left_pg + left_cnt*PAGE_SIZE) - (page + count*PAGE_SIZE)) >> PAGE_WIDTH; |
node->value[node->keys - 1] -= count + new_cnt; |
node->value[node->keys - 1] -= (count_t) count + new_cnt; |
btree_insert(&a->used_space, page + count*PAGE_SIZE, (void *) new_cnt, leaf); |
return 1; |
} |
1317,10 → 1258,10 |
* of the leaf and can be removed by updating the size |
* of the bigger interval. |
*/ |
leaf->value[leaf->keys - 1] -= count; |
leaf->value[leaf->keys - 1] -= (count_t) count; |
return 1; |
} else if (page + count*PAGE_SIZE < left_pg + left_cnt*PAGE_SIZE) { |
count_t new_cnt; |
count_t new_cnt = (left_pg + left_cnt*PAGE_SIZE) - (page + count*PAGE_SIZE); |
|
/* |
* The interval is contained in the rightmost interval |
1328,8 → 1269,7 |
* the size of the original interval and |
* also inserting a new interval. |
*/ |
new_cnt = ((left_pg + left_cnt*PAGE_SIZE) - (page + count*PAGE_SIZE)) >> PAGE_WIDTH; |
leaf->value[leaf->keys - 1] -= count + new_cnt; |
leaf->value[leaf->keys - 1] -= (count_t) count + new_cnt; |
btree_insert(&a->used_space, page + count*PAGE_SIZE, (void *) new_cnt, leaf); |
return 1; |
} |
1356,10 → 1296,10 |
* of the leaf and can be removed by updating the size |
* of the bigger interval. |
*/ |
leaf->value[i - 1] -= count; |
leaf->value[i - 1] -= (count_t) count; |
return 1; |
} else if (page + count*PAGE_SIZE < left_pg + left_cnt*PAGE_SIZE) { |
count_t new_cnt; |
count_t new_cnt = (left_pg + left_cnt*PAGE_SIZE) - (page + count*PAGE_SIZE); |
|
/* |
* The interval is contained in the interval (i - 1) |
1367,8 → 1307,7 |
* the size of the original interval and |
* also inserting a new interval. |
*/ |
new_cnt = ((left_pg + left_cnt*PAGE_SIZE) - (page + count*PAGE_SIZE)) >> PAGE_WIDTH; |
leaf->value[i - 1] -= count + new_cnt; |
leaf->value[i - 1] -= (count_t) count + new_cnt; |
btree_insert(&a->used_space, page + count*PAGE_SIZE, (void *) new_cnt, leaf); |
return 1; |
} |