Changeset 56789125 in mainline


Ignore:
Timestamp:
2006-05-22T09:36:48Z (19 years ago)
Author:
Jakub Jermar <jakub@…>
Branches:
lfn, master, serial, ticket/834-toolchain-update, topic/msim-upgrade, topic/simplify-dev-export
Children:
8182031
Parents:
040542aa
Message:

Fixes of the used_space management code.
Switch as_area_destroy() and as_area_resize() to use the used_space map.
as_area_steal() not switched as it will undergo further changes.

File:
1 edited

Legend:

Unmodified
Added
Removed

  • generic/src/mm/as.c

    r040542aa r56789125  
    9393static as_area_t *find_area_and_lock(as_t *as, __address va);
    9494static bool check_area_conflicts(as_t *as, __address va, size_t size, as_area_t *avoid_area);
    95 int used_space_insert(as_area_t *a, __address page, count_t count);
    96 int used_space_remove(as_area_t *a, __address page, count_t count);
     95static int used_space_insert(as_area_t *a, __address page, count_t count);
     96static int used_space_remove(as_area_t *a, __address page, count_t count);
    9797
    9898/** Initialize address space subsystem. */
    … …  
    245245       
    246246        if (pages < area->pages) {
    247                 int i;
     247                bool cond;
     248                __address start_free = area->base + pages*PAGE_SIZE;
    248249
    249250                /*
    … …  
    251252                 * No need to check for overlaps.
    252253                 */
    253                 for (i = pages; i < area->pages; i++) {
    254                         pte_t *pte;
     254
     255                /*
     256                 * Remove frames belonging to used space starting from
     257                 * the highest addresses downwards until an overlap with
     258                 * the resized address space area is found. Note that this
     259                 * is also the right way to remove part of the used_space
     260                 * B+tree leaf list.
     261                 */             
     262                for (cond = true; cond;) {
     263                        btree_node_t *node;
     264               
     265                        ASSERT(!list_empty(&area->used_space.leaf_head));
     266                        node = list_get_instance(area->used_space.leaf_head.prev, btree_node_t, leaf_link);
     267                        if ((cond = (bool) node->keys)) {
     268                                __address b = node->key[node->keys - 1];
     269                                count_t c = (count_t) node->value[node->keys - 1];
     270                                int i = 0;
    255271                       
    256                         /*
    257                          * Releasing physical memory.
    258                          * This depends on the fact that the memory was allocated using frame_alloc().
    259                          */
    260                         page_table_lock(as, false);
    261                         pte = page_mapping_find(as, area->base + i*PAGE_SIZE);
    262                         if (pte && PTE_VALID(pte)) {
    263                                 __address frame;
    264 
    265                                 ASSERT(PTE_PRESENT(pte));
    266                                 frame = PTE_GET_FRAME(pte);
    267                                 page_mapping_remove(as, area->base + i*PAGE_SIZE);
    268                                 page_table_unlock(as, false);
    269 
    270                                 frame_free(ADDR2PFN(frame));
    271                         } else {
    272                                 page_table_unlock(as, false);
     272                                if (overlaps(b, c*PAGE_SIZE, area->base, pages*PAGE_SIZE)) {
     273                                       
     274                                        if (b + c*PAGE_SIZE <= start_free) {
     275                                                /*
     276                                                 * The whole interval fits completely
     277                                                 * in the resized address space area.
     278                                                 */
     279                                                break;
     280                                        }
     281               
     282                                        /*
     283                                         * Part of the interval corresponding to b and c
     284                                         * overlaps with the resized address space area.
     285                                         */
     286               
     287                                        cond = false;   /* we are almost done */
     288                                        i = (start_free - b) >> PAGE_WIDTH;
     289                                        if (!used_space_remove(area, start_free, c - i))
     290                                                panic("Could not remove used space.");
     291                                } else {
     292                                        /*
     293                                         * The interval of used space can be completely removed.
     294                                         */
     295                                        if (!used_space_remove(area, b, c))
     296                                                panic("Could not remove used space.\n");
     297                                }
     298                       
     299                                for (; i < c; i++) {
     300                                        pte_t *pte;
     301                       
     302                                        page_table_lock(as, false);
     303                                        pte = page_mapping_find(as, b + i*PAGE_SIZE);
     304                                        ASSERT(pte && PTE_VALID(pte) && PTE_PRESENT(pte));
     305                                        frame_free(ADDR2PFN(PTE_GET_FRAME(pte)));
     306                                        page_mapping_remove(as, b + i*PAGE_SIZE);
     307                                        page_table_unlock(as, false);
     308                                }
    273309                        }
    274310                }
    … …  
    313349        __address base;
    314350        ipl_t ipl;
    315         int i;
    316351
    317352        ipl = interrupts_disable();
    … …  
    325360        }
    326361
    327         base = area->base;     
    328         for (i = 0; i < area->pages; i++) {
    329                 pte_t *pte;
    330 
     362        base = area->base;
     363        if (!(area->flags & AS_AREA_DEVICE)) {
     364                bool cond;     
     365       
    331366                /*
    332367                 * Releasing physical memory.
    … …  
    334369                 * areas backing frame_alloc()'ed memory.
    335370                 */
    336                 page_table_lock(as, false);
    337                 pte = page_mapping_find(as, area->base + i*PAGE_SIZE);
    338                 if (pte && PTE_VALID(pte)) {
    339                         ASSERT(PTE_PRESENT(pte));
    340                         page_mapping_remove(as, area->base + i*PAGE_SIZE);
    341                         if (area->flags & AS_AREA_DEVICE) {
    342                                 __address frame;
    343                                 frame = PTE_GET_FRAME(pte);
    344                                 frame_free(ADDR2PFN(frame));
     371
     372                /*
     373                 * Visit only the pages mapped by used_space B+tree.
     374                 * Note that we must be very careful when walking the tree
     375                 * leaf list and removing used space as the leaf list changes
     376                 * unpredictibly after each remove. The solution is to actually
     377                 * not walk the tree at all, but to remove items from the head
     378                 * of the leaf list until there are some keys left.
     379                 */
     380                for (cond = true; cond;) {
     381                        btree_node_t *node;
     382               
     383                        ASSERT(!list_empty(&area->used_space.leaf_head));
     384                        node = list_get_instance(area->used_space.leaf_head.next, btree_node_t, leaf_link);
     385                        if ((cond = (bool) node->keys)) {
     386                                __address b = node->key[0];
     387                                count_t i;
     388                                pte_t *pte;
     389                       
     390                                for (i = 0; i < (count_t) node->value[0]; i++) {
     391                                        page_table_lock(as, false);
     392                                        pte = page_mapping_find(as, b + i*PAGE_SIZE);
     393                                        ASSERT(pte && PTE_VALID(pte) && PTE_PRESENT(pte));
     394                                        frame_free(ADDR2PFN(PTE_GET_FRAME(pte)));
     395                                        page_mapping_remove(as, b + i*PAGE_SIZE);
     396                                        page_table_unlock(as, false);
     397                                }
     398                                if (!used_space_remove(area, b, i))
     399                                        panic("Could not remove used space.\n");
    345400                        }
    346                         page_table_unlock(as, false);
    347                 } else {
    348                         page_table_unlock(as, false);
    349                 }
    350         }
     401                }
     402        }
     403        btree_destroy(&area->used_space);
     404
    351405        /*
    352406         * Invalidate TLB's.
    … …  
    419473        mutex_unlock(&src_area->lock);
    420474        mutex_unlock(&src_as->lock);
    421 
    422475
    423476        if (src_size != acc_size) {
    … …  
    513566        area = find_area_and_lock(as, page);
    514567        if (!area) {
    515                 panic("page not part of any as_area\n");
     568                panic("Page not part of any as_area.\n");
    516569        }
    517570
    518571        page_mapping_insert(as, page, frame, get_area_flags(area));
     572        if (!used_space_insert(area, page, 1))
     573                panic("Could not insert used space.\n");
    519574       
    520575        mutex_unlock(&area->lock);
    … …  
    606661         */
    607662        page_mapping_insert(AS, page, frame, get_area_flags(area));
     663        if (!used_space_insert(area, ALIGN_DOWN(page, PAGE_SIZE), 1))
     664                panic("Could not insert used space.\n");
    608665        page_table_unlock(AS, false);
    609666       
    … …  
    9971054                } else if ((page == left_pg + left_cnt*PAGE_SIZE) && (page + count*PAGE_SIZE == right_pg)) {
    9981055                        /* The interval can be added by merging the two already present intervals. */
    999                         node->value[node->keys - 1] += (count_t) count + right_cnt;
     1056                        node->value[node->keys - 1] += count + right_cnt;
    10001057                        btree_remove(&a->used_space, right_pg, leaf);
    10011058                        return 1;
    10021059                } else if (page == left_pg + left_cnt*PAGE_SIZE) {
    10031060                        /* The interval can be added by simply growing the left interval. */
    1004                         node->value[node->keys - 1] += (count_t) count;
     1061                        node->value[node->keys - 1] += count;
    10051062                        return 1;
    10061063                } else if (page + count*PAGE_SIZE == right_pg) {
    … …  
    10091066                         * interval down and increasing its size accordingly.
    10101067                         */
    1011                         leaf->value[0] += (count_t) count;
     1068                        leaf->value[0] += count;
    10121069                        leaf->key[0] = page;
    10131070                        return 1;
    … …  
    10381095                         */
    10391096                        leaf->key[0] = page;
    1040                         leaf->value[0] += (count_t) count;
     1097                        leaf->value[0] += count;
    10411098                        return 1;
    10421099                } else {
    … …  
    10711128                } else if ((page == left_pg + left_cnt*PAGE_SIZE) && (page + count*PAGE_SIZE == right_pg)) {
    10721129                        /* The interval can be added by merging the two already present intervals. */
    1073                         leaf->value[leaf->keys - 1] += (count_t) count + right_cnt;
     1130                        leaf->value[leaf->keys - 1] += count + right_cnt;
    10741131                        btree_remove(&a->used_space, right_pg, node);
    10751132                        return 1;
    10761133                } else if (page == left_pg + left_cnt*PAGE_SIZE) {
    10771134                        /* The interval can be added by simply growing the left interval. */
    1078                         leaf->value[leaf->keys - 1] += (count_t) count;
     1135                        leaf->value[leaf->keys - 1] += count;
    10791136                        return 1;
    10801137                } else if (page + count*PAGE_SIZE == right_pg) {
    … …  
    10831140                         * interval down and increasing its size accordingly.
    10841141                         */
    1085                         node->value[0] += (count_t) count;
     1142                        node->value[0] += count;
    10861143                        node->key[0] = page;
    10871144                        return 1;
    … …  
    11041161                 
    11051162                if (overlaps(page, count*PAGE_SIZE, left_pg, left_cnt*PAGE_SIZE)) {
    1106                         /* The interval intersects with the right interval. */
     1163                        /* The interval intersects with the left interval. */
    11071164                        return 0;
    11081165                } else if (left_pg + left_cnt*PAGE_SIZE == page) {
    11091166                        /* The interval can be added by growing the left interval. */
    1110                         leaf->value[leaf->keys - 1] += (count_t) count;
     1167                        leaf->value[leaf->keys - 1] += count;
    11111168                        return 1;
    11121169                } else {
    … …  
    11421199                        } else if ((page == left_pg + left_cnt*PAGE_SIZE) && (page + count*PAGE_SIZE == right_pg)) {
    11431200                                /* The interval can be added by merging the two already present intervals. */
    1144                                 leaf->value[i - 1] += (count_t) count + right_cnt;
     1201                                leaf->value[i - 1] += count + right_cnt;
    11451202                                btree_remove(&a->used_space, right_pg, leaf);
    11461203                                return 1;
    11471204                        } else if (page == left_pg + left_cnt*PAGE_SIZE) {
    11481205                                /* The interval can be added by simply growing the left interval. */
    1149                                 leaf->value[i - 1] += (count_t) count;
     1206                                leaf->value[i - 1] += count;
    11501207                                return 1;
    11511208                        } else if (page + count*PAGE_SIZE == right_pg) {
    … …  
    11541211                                 * interval down and increasing its size accordingly.
    11551212                                 */
    1156                                 leaf->value[i] += (count_t) count;
     1213                                leaf->value[i] += count;
    11571214                                leaf->key[i] = page;
    11581215                                return 1;
    … …  
    11991256                } else if (count == pages) {
    12001257                        btree_remove(&a->used_space, page, leaf);
     1258                        return 1;
    12011259                } else {
    12021260                        /*
    … …  
    12071265                                if (leaf->key[i] == page) {
    12081266                                        leaf->key[i] += count*PAGE_SIZE;
    1209                                         leaf->value[i] -= (count_t) count;
     1267                                        leaf->value[i] -= count;
    12101268                                        return 1;
    12111269                                }
    … …  
    12271285                                 * updating the size of the bigger interval.
    12281286                                 */
    1229                                 node->value[node->keys - 1] -= (count_t) count;
     1287                                node->value[node->keys - 1] -= count;
    12301288                                return 1;
    12311289                        } else if (page + count*PAGE_SIZE < left_pg + left_cnt*PAGE_SIZE) {
    1232                                 count_t new_cnt = (left_pg + left_cnt*PAGE_SIZE) - (page + count*PAGE_SIZE);
     1290                                count_t new_cnt;
    12331291                               
    12341292                                /*
    … …  
    12381296                                 * also inserting a new interval.
    12391297                                 */
    1240                                 node->value[node->keys - 1] -= (count_t) count + new_cnt;
     1298                                new_cnt = ((left_pg + left_cnt*PAGE_SIZE) - (page + count*PAGE_SIZE)) >> PAGE_WIDTH;
     1299                                node->value[node->keys - 1] -= count + new_cnt;
    12411300                                btree_insert(&a->used_space, page + count*PAGE_SIZE, (void *) new_cnt, leaf);
    12421301                                return 1;
    … …  
    12591318                                 * of the bigger interval.
    12601319                                 */
    1261                                 leaf->value[leaf->keys - 1] -= (count_t) count;
     1320                                leaf->value[leaf->keys - 1] -= count;
    12621321                                return 1;
    12631322                        } else if (page + count*PAGE_SIZE < left_pg + left_cnt*PAGE_SIZE) {
    1264                                 count_t new_cnt = (left_pg + left_cnt*PAGE_SIZE) - (page + count*PAGE_SIZE);
     1323                                count_t new_cnt;
    12651324                               
    12661325                                /*
    … …  
    12701329                                 * also inserting a new interval.
    12711330                                 */
    1272                                 leaf->value[leaf->keys - 1] -= (count_t) count + new_cnt;
     1331                                new_cnt = ((left_pg + left_cnt*PAGE_SIZE) - (page + count*PAGE_SIZE)) >> PAGE_WIDTH;
     1332                                leaf->value[leaf->keys - 1] -= count + new_cnt;
    12731333                                btree_insert(&a->used_space, page + count*PAGE_SIZE, (void *) new_cnt, leaf);
    12741334                                return 1;
    … …  
    12971357                                         * of the bigger interval.
    12981358                                         */
    1299                                         leaf->value[i - 1] -= (count_t) count;
     1359                                        leaf->value[i - 1] -= count;
    13001360                                        return 1;
    13011361                                } else if (page + count*PAGE_SIZE < left_pg + left_cnt*PAGE_SIZE) {
    1302                                         count_t new_cnt = (left_pg + left_cnt*PAGE_SIZE) - (page + count*PAGE_SIZE);
     1362                                        count_t new_cnt;
    13031363                               
    13041364                                        /*
    … …  
    13081368                                         * also inserting a new interval.
    13091369                                         */
    1310                                         leaf->value[i - 1] -= (count_t) count + new_cnt;
     1370                                        new_cnt = ((left_pg + left_cnt*PAGE_SIZE) - (page + count*PAGE_SIZE)) >> PAGE_WIDTH;
     1371                                        leaf->value[i - 1] -= count + new_cnt;
    13111372                                        btree_insert(&a->used_space, page + count*PAGE_SIZE, (void *) new_cnt, leaf);
    13121373                                        return 1;
Note: See TracChangeset for help on using the changeset viewer.