Changeset 25bf215 in mainline

Timestamp:

2006-05-21T15:15:30Z (19 years ago)

Author:

Jakub Jermar <jakub@…>

Branches:

lfn, master, serial, ticket/834-toolchain-update, topic/msim-upgrade, topic/simplify-dev-export

Children:

2a1803eb

Parents:

7ca8b36b

Message:

Add used_space_insert() and used_space_remove().
These are the alpha versions of functions that
will help to map used and unused portions of address
space areas. Currently unused, but many as_area operations
will be more efficient when the used space B+tree map
is used.

Location:

generic

Files:

• include/mm/as.h (modified) (2 diffs)
• src/mm/as.c (modified) (4 diffs)

generic/include/mm/as.h

@@ -35 +35 @@
 #define AS_AREA_EXEC    4
 #define AS_AREA_DEVICE  8
-
 
 #ifdef KERNEL
@@ -84 +83 @@
         count_t pages;          /**< Size of this area in multiples of PAGE_SIZE. */
         __address base;         /**< Base address of this area. */
+        btree_t used_space;     /**< Map of used space. */
 };
 

generic/src/mm/as.c

@@ -69 +69 @@
 #include <errno.h>
 #include <config.h>
+#include <align.h>
 #include <arch/types.h>
 #include <typedefs.h>
@@ -92 +93 @@
 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);
+int used_space_remove(as_area_t *a, __address page, count_t count);
 
 /** Initialize address space subsystem. */
@@ -181 +184 @@
         a->pages = SIZE2FRAMES(size);
         a->base = base;
+        btree_create(&a->used_space);
         
         btree_insert(&as->as_area_btree, base, (void *) a, NULL);
@@ -945 +949 @@
 }
 
+/** Mark portion of address space area as used.
+ *
+ * The address space area must be already locked.
+ *
+ * @param a Address space area.
+ * @param page First page to be marked.
+ * @param count Number of page to be marked.
+ *
+ * @return 0 on failure and 1 on success.
+ */
+int used_space_insert(as_area_t *a, __address page, count_t count)
+{
+        btree_node_t *leaf, *node;
+        count_t pages;
+        int i;
+
+        ASSERT(page == ALIGN_DOWN(page, PAGE_SIZE));
+        ASSERT(count);
+
+        pages = (count_t) btree_search(&a->used_space, page, &leaf);
+        if (pages) {
+                /*
+                 * We hit the beginning of some used space.
+                 */
+                return 0;
+        }
+
+        node = btree_leaf_node_left_neighbour(&a->used_space, leaf);
+        if (node) {
+                __address left_pg = node->key[node->keys - 1], right_pg = leaf->key[0];
+                count_t left_cnt = (count_t) node->value[node->keys - 1], right_cnt = (count_t) leaf->value[0];
+                
+                /*
+                 * Examine the possibility that the interval fits
+                 * somewhere between the rightmost interval of
+                 * the left neigbour and the first interval of the leaf.
+                 */
+                 
+                if (page >= right_pg) {
+                        /* Do nothing. */
+                } else if (overlaps(page, count*PAGE_SIZE, left_pg, left_cnt*PAGE_SIZE)) {
+                        /* The interval intersects with the left interval. */
+                        return 0;
+                } 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;
+                        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;
+                        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->key[0] = page;
+                        return 1;
+                } else {
+                        /*
+                         * The interval is between both neigbouring intervals,
+                         * but cannot be merged with any of them.
+                         */
+                        btree_insert(&a->used_space, page, (void *) count, leaf);
+                        return 1;
+                }
+        } else if (page < leaf->key[0]) {
+                __address right_pg = leaf->key[0];
+                count_t right_cnt = (count_t) leaf->value[0];
+        
+                /*
+                 * Investigate the border case in which the left neighbour does not
+                 * exist but the interval fits from the left.
+                 */
+                 
+                if (overlaps(page, count*PAGE_SIZE, right_pg, right_cnt*PAGE_SIZE)) {
+                        /* The interval intersects with the right interval. */
+                        return 0;
+                } else if (page + count*PAGE_SIZE == right_pg) {
+                        /*
+                         * 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;
+                        return 1;
+                } else {
+                        /*
+                         * The interval doesn't adjoin with the right interval.
+                         * It must be added individually.
+                         */
+                        btree_insert(&a->used_space, page, (void *) count, leaf);
+                        return 1;
+                }
+        }
+
+        node = btree_leaf_node_right_neighbour(&a->used_space, leaf);
+        if (node) {
+                __address left_pg = leaf->key[leaf->keys - 1], right_pg = node->key[0];
+                count_t left_cnt = (count_t) leaf->value[leaf->keys - 1], right_cnt = (count_t) node->value[0];
+                
+                /*
+                 * Examine the possibility that the interval fits
+                 * somewhere between the leftmost interval of
+                 * the right neigbour and the last interval of the leaf.
+                 */
+
+                if (page < left_pg) {
+                        /* Do nothing. */
+                } else if (overlaps(page, count*PAGE_SIZE, left_pg, left_cnt*PAGE_SIZE)) {
+                        /* The interval intersects with the left interval. */
+                        return 0;
+                } 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;
+                        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;
+                        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->key[0] = page;
+                        return 1;
+                } else {
+                        /*
+                         * The interval is between both neigbouring intervals,
+                         * but cannot be merged with any of them.
+                         */
+                        btree_insert(&a->used_space, page, (void *) count, leaf);
+                        return 1;
+                }
+        } else if (page >= leaf->key[leaf->keys - 1]) {
+                __address left_pg = leaf->key[leaf->keys - 1];
+                count_t left_cnt = (count_t) leaf->value[leaf->keys - 1];
+        
+                /*
+                 * 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. */
+                        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;
+                        return 1;
+                } else {
+                        /*
+                         * The interval doesn't adjoin with the left interval.
+                         * It must be added individually.
+                         */
+                        btree_insert(&a->used_space, page, (void *) count, leaf);
+                        return 1;
+                }
+        }
+        
+        /*
+         * Note that if the algorithm made it thus far, the interval can fit only
+         * between two other intervals of the leaf. The two border cases were already
+         * resolved.
+         */
+        for (i = 1; i < leaf->keys; i++) {
+                if (page < leaf->key[i]) {
+                        __address left_pg = leaf->key[i - 1], right_pg = leaf->key[i];
+                        count_t left_cnt = (count_t) leaf->value[i - 1], right_cnt = (count_t) leaf->value[i];
+
+                        /*
+                         * The interval fits between left_pg and right_pg.
+                         */
+
+                        if (overlaps(page, count*PAGE_SIZE, left_pg, left_cnt*PAGE_SIZE)) {
+                                /* The interval intersects with the left interval. */
+                                return 0;
+                        } 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;
+                                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;
+                                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->key[i] = page;
+                                return 1;
+                        } else {
+                                /*
+                                 * The interval is between both neigbouring intervals,
+                                 * but cannot be merged with any of them.
+                                 */
+                                btree_insert(&a->used_space, page, (void *) count, leaf);
+                                return 1;
+                        }
+                }
+        }
+
+        panic("Inconsistency detected while adding %d pages of used space at %P.\n", count, page);
+}
+
+/** Mark portion of address space area as unused.
+ *
+ * The address space area must be already locked.
+ *
+ * @param a Address space area.
+ * @param page First page to be marked.
+ * @param count Number of page to be marked.
+ *
+ * @return 0 on failure and 1 on success.
+ */
+int used_space_remove(as_area_t *a, __address page, count_t count)
+{
+        btree_node_t *leaf, *node;
+        count_t pages;
+        int i;
+
+        ASSERT(page == ALIGN_DOWN(page, PAGE_SIZE));
+        ASSERT(count);
+
+        pages = (count_t) btree_search(&a->used_space, page, &leaf);
+        if (pages) {
+                /*
+                 * We are lucky, page is the beginning of some interval.
+                 */
+                if (count > pages) {
+                        return 0;
+                } else if (count == pages) {
+                        btree_remove(&a->used_space, page, leaf);
+                } 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;
+                                        return 1;
+                                }
+                        }
+                        goto error;
+                }
+        }
+
+        node = btree_leaf_node_left_neighbour(&a->used_space, leaf);
+        if (node && page < leaf->key[0]) {
+                __address left_pg = node->key[node->keys - 1];
+                count_t left_cnt = (count_t) node->value[node->keys - 1];
+
+                if (overlaps(left_pg, left_cnt*PAGE_SIZE, page, count*PAGE_SIZE)) {
+                        if (page + count*PAGE_SIZE == left_pg + left_cnt*PAGE_SIZE) {
+                                /*
+                                 * 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;
+                                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);
+                                
+                                /*
+                                 * 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.
+                                 */
+                                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;
+                        }
+                }
+                return 0;
+        } else if (page < leaf->key[0]) {
+                return 0;
+        }
+        
+        if (page > leaf->key[leaf->keys - 1]) {
+                __address left_pg = leaf->key[leaf->keys - 1];
+                count_t left_cnt = (count_t) leaf->value[leaf->keys - 1];
+
+                if (overlaps(left_pg, left_cnt*PAGE_SIZE, page, count*PAGE_SIZE)) {
+                        if (page + count*PAGE_SIZE == left_pg + left_cnt*PAGE_SIZE) {
+                                /*
+                                 * 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;
+                                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);
+                                
+                                /*
+                                 * 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.
+                                 */
+                                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;
+                        }
+                }
+                return 0;
+        }       
+        
+        /*
+         * The border cases have been already resolved.
+         * Now the interval can be only between intervals of the leaf. 
+         */
+        for (i = 1; i < leaf->keys - 1; i++) {
+                if (page < leaf->key[i]) {
+                        __address left_pg = leaf->key[i - 1];
+                        count_t left_cnt = (count_t) leaf->value[i - 1];
+
+                        /*
+                         * Now the interval is between intervals corresponding to (i - 1) and i.
+                         */
+                        if (overlaps(left_pg, left_cnt*PAGE_SIZE, page, count*PAGE_SIZE)) {
+                                if (page + count*PAGE_SIZE == left_pg + left_cnt*PAGE_SIZE) {
+                                        /*
+                                        * 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;
+                                        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);
+                                
+                                        /*
+                                         * 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.
+                                         */
+                                        leaf->value[i - 1] -= (count_t) count + new_cnt;
+                                        btree_insert(&a->used_space, page + count*PAGE_SIZE, (void *) new_cnt, leaf);
+                                        return 1;
+                                }
+                        }
+                        return 0;
+                }
+        }
+
+error:
+        panic("Inconsistency detected while removing %d pages of used space from %P.\n", count, page);
+}
+
 /*
  * Address space related syscalls.