WebSVN – HelenOS-historic – Diff – /kernel/trunk/generic/src/mm/as.c

 static int area_flags_to_page_flags(int aflags);
 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);
-int used_space_insert(as_area_t *a, __address page, count_t count);
+static 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);
+static int used_space_remove(as_area_t *a, __address page, count_t count);
 /** Initialize address space subsystem. */
 void as_init(void)
+{
     as_arch_init();
         interrupts_restore(ipl);
         return EPERM;
+    }
     if (pages < area->pages) {
-        int i;
+        bool cond;
+        __address start_free = area->base + pages*PAGE_SIZE;
         /*
          * Shrinking the area.
          * No need to check for overlaps.
          */
-        for (i = pages; i < area->pages; i++) {
-            pte_t *pte;
-            /*
-             * Releasing physical memory.
-             * This depends on the fact that the memory was allocated using frame_alloc().
-             */
-            page_table_lock(as, false);
-            pte = page_mapping_find(as, area->base + i*PAGE_SIZE);
-            if (pte && PTE_VALID(pte)) {
-                __address frame;
-                ASSERT(PTE_PRESENT(pte));
-                frame = PTE_GET_FRAME(pte);
-                page_mapping_remove(as, area->base + i*PAGE_SIZE);
-                page_table_unlock(as, false);
+        /*
+         * 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.
+         */
+        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.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;
+                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 */
-                frame_free(ADDR2PFN(frame));
+                    i = (start_free - b) >> PAGE_WIDTH;
+                    if (!used_space_remove(area, start_free, c - i))
+                        panic("Could not remove used space.");
-            } else {
+                } 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);
+                    page_table_unlock(as, false);
+                }
+            }
+        }
         /*
          * Invalidate TLB's.
          */
 int as_area_destroy(as_t *as, __address address)
+{
     as_area_t *area;
     __address base;
     ipl_t ipl;
-    int i;
     ipl = interrupts_disable();
     mutex_lock(&as->lock);
     area = find_area_and_lock(as, address);
         mutex_unlock(&as->lock);
         interrupts_restore(ipl);
         return ENOENT;
+    }
     base = area->base;
-    for (i = 0; i < area->pages; i++) {
+    if (!(area->flags & AS_AREA_DEVICE)) {
-        pte_t *pte;
+        bool cond;
         /*
          * Releasing physical memory.
          * 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);
+                    page_table_lock(as, false);
-        pte = page_mapping_find(as, area->base + i*PAGE_SIZE);
+                    pte = page_mapping_find(as, b + i*PAGE_SIZE);
-        if (pte && PTE_VALID(pte)) {
+                    ASSERT(pte && PTE_VALID(pte) && PTE_PRESENT(pte));
-            ASSERT(PTE_PRESENT(pte));
+                    frame_free(ADDR2PFN(PTE_GET_FRAME(pte)));
-            page_mapping_remove(as, area->base + i*PAGE_SIZE);
+                    page_mapping_remove(as, b + i*PAGE_SIZE);
-            if (area->flags & AS_AREA_DEVICE) {
+                    page_table_unlock(as, false);
-                __address frame;
+                }
-                frame = PTE_GET_FRAME(pte);
+                if (!used_space_remove(area, b, i))
-                frame_free(ADDR2PFN(frame));
+                    panic("Could not remove used space.\n");
+            }
-            page_table_unlock(as, false);
-        } else {
-            page_table_unlock(as, false);
+        }
+    }
+    btree_destroy(&area->used_space);
     /*
      * Invalidate TLB's.
      */
     tlb_shootdown_start(TLB_INVL_PAGES, AS->asid, area->base, area->pages);
     tlb_invalidate_pages(AS->asid, area->base, area->pages);
     src_size = src_area->pages * PAGE_SIZE;
     src_flags = src_area->flags;
     mutex_unlock(&src_area->lock);
     mutex_unlock(&src_as->lock);
     if (src_size != acc_size) {
         spinlock_unlock(&src_task->lock);
         interrupts_restore(ipl);
         return EPERM;
+    }
     ipl = interrupts_disable();
     page_table_lock(as, true);
     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);
     interrupts_restore(ipl);
+}
      * Map 'page' to 'frame'.
      * Note that TLB shootdown is not attempted as only new information is being
      * 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);
     mutex_unlock(&AS->lock);
     return AS_PF_OK;
         } else if (overlaps(page, count*PAGE_SIZE, right_pg, right_cnt*PAGE_SIZE)) {
             /* The interval intersects with the right interval. */
             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_t) count + right_cnt;
+            node->value[node->keys - 1] += 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_t) count;
+            node->value[node->keys - 1] += count;
             return 1;
         } else if (page + count*PAGE_SIZE == right_pg) {
             /*
              * The interval can be addded by simply moving base of the right
              * interval down and increasing its size accordingly.
              */
-            leaf->value[0] += (count_t) count;
+            leaf->value[0] += count;
             leaf->key[0] = page;
             return 1;
         } else {
             /*
              * The interval is between both neigbouring intervals,
             /*
              * The interval can be added by moving the base of the right interval down
              * and increasing its size accordingly.
              */
             leaf->key[0] = page;
-            leaf->value[0] += (count_t) count;
+            leaf->value[0] += count;
             return 1;
         } else {
             /*
              * The interval doesn't adjoin with the right interval.
              * It must be added individually.
         } else if (overlaps(page, count*PAGE_SIZE, right_pg, right_cnt*PAGE_SIZE)) {
             /* The interval intersects with the right interval. */
             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_t) count + right_cnt;
+            leaf->value[leaf->keys - 1] += 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_t) count;
+            leaf->value[leaf->keys - 1] +=  count;
             return 1;
         } else if (page + count*PAGE_SIZE == right_pg) {
             /*
              * The interval can be addded by simply moving base of the right
              * interval down and increasing its size accordingly.
              */
-            node->value[0] += (count_t) count;
+            node->value[0] += count;
             node->key[0] = page;
             return 1;
         } else {
             /*
              * The interval is between both neigbouring intervals,
          * Investigate the border case in which the right neighbour does not
          * exist but the interval fits from the right.
          */
         if (overlaps(page, count*PAGE_SIZE, left_pg, left_cnt*PAGE_SIZE)) {
-            /* The interval intersects with the right interval. */
+            /* The interval intersects with the left 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_t) count;
+            leaf->value[leaf->keys - 1] += count;
             return 1;
         } else {
             /*
              * The interval doesn't adjoin with the left interval.
              * It must be added individually.
             } else if (overlaps(page, count*PAGE_SIZE, right_pg, right_cnt*PAGE_SIZE)) {
                 /* The interval intersects with the right interval. */
                 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_t) count + right_cnt;
+                leaf->value[i - 1] += 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_t) count;
+                leaf->value[i - 1] += count;
                 return 1;
             } else if (page + count*PAGE_SIZE == right_pg) {
                 /*
                      * The interval can be addded by simply moving base of the right
                  * interval down and increasing its size accordingly.
                  */
-                leaf->value[i] += (count_t) count;
+                leaf->value[i] += count;
                 leaf->key[i] = page;
                 return 1;
             } else {
                 /*
                  * The interval is between both neigbouring intervals,
          */
         if (count > pages) {
             return 0;
         } else if (count == pages) {
             btree_remove(&a->used_space, page, leaf);
+            return 1;
         } else {
             /*
              * Find the respective interval.
              * Decrease its size and relocate its start address.
              */
             for (i = 0; i < leaf->keys; i++) {
                 if (leaf->key[i] == page) {
                     leaf->key[i] += count*PAGE_SIZE;
-                    leaf->value[i] -= (count_t) count;
+                    leaf->value[i] -= count;
                     return 1;
+                }
+            }
             goto error;
+        }
                 /*
                  * The interval is contained in the rightmost interval
                  * of the left neighbour and can be removed by
                  * updating the size of the bigger interval.
                  */
-                node->value[node->keys - 1] -= (count_t) count;
+                node->value[node->keys - 1] -= count;
                 return 1;
             } else if (page + count*PAGE_SIZE < left_pg + left_cnt*PAGE_SIZE) {
-                count_t new_cnt = (left_pg + left_cnt*PAGE_SIZE) - (page + count*PAGE_SIZE);
+                count_t new_cnt;
                 /*
                  * The interval is contained in the rightmost interval
                  * of the left neighbour but its removal requires
                  * 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_t) count + new_cnt;
+                node->value[node->keys - 1] -= count + new_cnt;
                 btree_insert(&a->used_space, page + count*PAGE_SIZE, (void *) new_cnt, leaf);
                 return 1;
+            }
+        }
         return 0;
                 /*
                  * The interval is contained in the rightmost interval
                  * of the leaf and can be removed by updating the size
                  * of the bigger interval.
                  */
-                leaf->value[leaf->keys - 1] -= (count_t) count;
+                leaf->value[leaf->keys - 1] -= count;
                 return 1;
             } else if (page + count*PAGE_SIZE < left_pg + left_cnt*PAGE_SIZE) {
-                count_t new_cnt = (left_pg + left_cnt*PAGE_SIZE) - (page + count*PAGE_SIZE);
+                count_t new_cnt;
                 /*
                  * The interval is contained in the rightmost interval
                  * of the leaf but its removal requires 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;
-                leaf->value[leaf->keys - 1] -= (count_t) count + new_cnt;
+                leaf->value[leaf->keys - 1] -= count + new_cnt;
                 btree_insert(&a->used_space, page + count*PAGE_SIZE, (void *) new_cnt, leaf);
                 return 1;
+            }
+        }
         return 0;
                     /*
                     * The interval is contained in the interval (i - 1)
                      * of the leaf and can be removed by updating the size
                      * of the bigger interval.
                      */
-                    leaf->value[i - 1] -= (count_t) count;
+                    leaf->value[i - 1] -= count;
                     return 1;
                 } else if (page + count*PAGE_SIZE < left_pg + left_cnt*PAGE_SIZE) {
-                    count_t new_cnt = (left_pg + left_cnt*PAGE_SIZE) - (page + count*PAGE_SIZE);
+                    count_t new_cnt;
                     /*
                      * The interval is contained in the interval (i - 1)
                      * of the leaf but its removal requires 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;
-                    leaf->value[i - 1] -= (count_t) count + new_cnt;
+                    leaf->value[i - 1] -= count + new_cnt;
                     btree_insert(&a->used_space, page + count*PAGE_SIZE, (void *) new_cnt, leaf);
                     return 1;
+                }
+            }
             return 0;

Subversion Repositories HelenOS-historic

(root)/kernel/trunk/generic/src/mm/as.c – Rev 1387 → 1403