Changeset 252127e in mainline

Timestamp:

2006-04-03T22:15:56Z (19 years ago)

Author:

Jakub Jermar <jakub@…>

Branches:

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

Children:

b26db0c

Parents:

b9b14a83

Message:

Deploy B+tree in address space area management.
Change as_remap() to check for conflicts with other address space areas only when the area in question grows.

Location:

generic

Files:

• include/adt/btree.h (modified) (1 diff)
• include/mm/as.h (modified) (3 diffs)
• src/adt/btree.c (modified) (1 diff)
• src/mm/as.c (modified) (9 diffs)

generic/include/adt/btree.h

@@ -84 +84 @@
 extern void *btree_search(btree_t *t, __native key, btree_node_t **leaf_node);
 
+extern btree_node_t *btree_node_left_sibling(btree_t *t, btree_node_t *node);
+extern btree_node_t *btree_node_right_sibling(btree_t *t, btree_node_t *node);
+
 extern void btree_print(btree_t *t);
 #endif

generic/include/mm/as.h

@@ -37 +37 @@
 #include <synch/spinlock.h>
 #include <adt/list.h>
+#include <adt/btree.h>
 
 /** Defined to be true if user address space and kernel address space shadow each other. */
@@ -64 +65 @@
 struct as_area {
         SPINLOCK_DECLARE(lock);
-        link_t link;
         int flags;
         count_t pages;          /**< Size of this area in multiples of PAGE_SIZE. */
@@ -86 +86 @@
         count_t refcount;
 
-        link_t as_area_head;
+        /** B+-tree of address space areas. */
+        btree_t as_area_btree;
 
         /** Page table pointer. Constant on architectures that use global page hash table. */

generic/src/adt/btree.c

@@ -341 +341 @@
 }
 
+/** Return pointer to B-tree node's left sibling.
+ *
+ * @param t B-tree.
+ * @param node Node whose left sibling will be returned.
+ *
+ * @return Left sibling of the node or NULL if the node does not have the left sibling.
+ */
+btree_node_t *btree_node_left_sibling(btree_t *t, btree_node_t *node)
+{
+        ASSERT(LEAF_NODE(node));
+        if (node->leaf_link.prev != &t->leaf_head)
+                return list_get_instance(node->leaf_link.prev, btree_node_t, leaf_link);
+        else
+                return NULL;
+}
+
+/** Return pointer to B-tree node's right sibling.
+ *
+ * @param t B-tree.
+ * @param node Node whose right sibling will be returned.
+ *
+ * @return Right sibling of the node or NULL if the node does not have the right sibling.
+ */
+btree_node_t *btree_node_right_sibling(btree_t *t, btree_node_t *node)
+{
+        ASSERT(LEAF_NODE(node));
+        if (node->leaf_link.next != &t->leaf_head)
+                return list_get_instance(node->leaf_link.next, btree_node_t, leaf_link);
+        else
+                return NULL;
+}
+
 /** Initialize B-tree node.
  *

generic/src/mm/as.c

@@ -49 +49 @@
 #include <config.h>
 #include <adt/list.h>
+#include <adt/btree.h>
 #include <panic.h>
 #include <arch/asm.h>
@@ -95 +96 @@
         link_initialize(&as->inactive_as_with_asid_link);
         spinlock_initialize(&as->lock, "as_lock");
-        list_initialize(&as->as_area_head);
+        btree_create(&as->as_area_btree);
         
         if (flags & FLAG_AS_KERNEL)
@@ -154 +155 @@
         spinlock_initialize(&a->lock, "as_area_lock");
         
-        link_initialize(&a->link);                      
         a->flags = flags;
         a->pages = SIZE2FRAMES(size);
         a->base = base;
         
-        list_append(&a->link, &as->as_area_head);
+        btree_insert(&as->as_area_btree, base, (void *) a, NULL);
 
         spinlock_unlock(&as->lock);
@@ -446 +446 @@
 
         pages = SIZE2FRAMES((address - area->base) + size);
-        if (!check_area_conflicts(as, address, pages * PAGE_SIZE, area)) {
-                spinlock_unlock(&area->lock);
-                spinlock_unlock(&as->lock);             
-                interrupts_restore(ipl);
-                return (__address) -1;
-        }
-
         if (pages < area->pages) {
                 int i;
@@ -458 +451 @@
                 /*
                  * Shrinking the area.
+                 * No need to check for overlaps.
                  */
                 for (i = pages; i < area->pages; i++) {
@@ -487 +481 @@
                 tlb_invalidate_pages(AS->asid, area->base + pages*PAGE_SIZE, area->pages - pages);
                 tlb_shootdown_finalize();
+        } else {
+                /*
+                 * Growing the area.
+                 * Check for overlaps with other address space areas.
+                 */
+                if (!check_area_conflicts(as, address, pages * PAGE_SIZE, area)) {
+                        spinlock_unlock(&area->lock);
+                        spinlock_unlock(&as->lock);             
+                        interrupts_restore(ipl);
+                        return (__address) -1;
+                }
         } 
 
@@ -509 +514 @@
 as_area_t *find_area_and_lock(as_t *as, __address va)
 {
-        link_t *cur;
         as_area_t *a;
-        
-        for (cur = as->as_area_head.next; cur != &as->as_area_head; cur = cur->next) {
-                a = list_get_instance(cur, as_area_t, link);
+        btree_node_t *leaf, *lnode;
+        int i;
+        
+        a = (as_area_t *) btree_search(&as->as_area_btree, va, &leaf);
+        if (a) {
+                /* va is the base address of an address space area */
                 spinlock_lock(&a->lock);
-
-                if ((va >= a->base) && (va < a->base + a->pages * PAGE_SIZE))
+                return a;
+        }
+        
+        /*
+         * Search the leaf node and the righmost record of its left sibling
+         * to find out whether this is a miss or va belongs to an address
+         * space area found there.
+         */
+        
+        /* First, search the leaf node itself. */
+        for (i = 0; i < leaf->keys; i++) {
+                a = (as_area_t *) leaf->value[i];
+                spinlock_lock(&a->lock);
+                if ((a->base <= va) && (va < a->base + a->pages * PAGE_SIZE)) {
                         return a;
-                
+                }
+                spinlock_unlock(&a->lock);
+        }
+
+        /*
+         * Second, locate the left sibling and test its last record.
+         * Because of its position in the B+-tree, it must have base < va.
+         */
+        if ((lnode = btree_node_left_sibling(&as->as_area_btree, leaf))) {
+                a = (as_area_t *) lnode->value[lnode->keys - 1];
+                spinlock_lock(&a->lock);
+                if (va < a->base + a->pages * PAGE_SIZE) {
+                        return a;
+                }
                 spinlock_unlock(&a->lock);
         }
@@ -538 +570 @@
 bool check_area_conflicts(as_t *as, __address va, size_t size, as_area_t *avoid_area)
 {
-        link_t *cur;
         as_area_t *a;
+        btree_node_t *leaf, *node;
+        int i;
         
         /*
@@ -547 +580 @@
                 return false;
         
-        for (cur = as->as_area_head.next; cur != &as->as_area_head; cur = cur->next) {
-                __address a_start;
-                size_t a_size;
-        
-                a = list_get_instance(cur, as_area_t, link);
+        /*
+         * The leaf node is found in O(log n), where n is proportional to
+         * the number of address space areas belonging to as.
+         * The check for conflicts is then attempted on the rightmost
+         * record in the left sibling, the leftmost record in the right
+         * sibling and all records in the leaf node itself.
+         */
+        
+        if ((a = (as_area_t *) btree_search(&as->as_area_btree, va, &leaf))) {
+                if (a != avoid_area)
+                        return false;
+        }
+        
+        /* First, check the two border cases. */
+        if ((node = btree_node_left_sibling(&as->as_area_btree, leaf))) {
+                a = (as_area_t *) node->value[node->keys - 1];
+                spinlock_lock(&a->lock);
+                if (overlaps(va, size, a->base, a->pages * PAGE_SIZE)) {
+                        spinlock_unlock(&a->lock);
+                        return false;
+                }
+                spinlock_unlock(&a->lock);
+        }
+        if ((node = btree_node_right_sibling(&as->as_area_btree, leaf))) {
+                a = (as_area_t *) node->value[0];
+                spinlock_lock(&a->lock);
+                if (overlaps(va, size, a->base, a->pages * PAGE_SIZE)) {
+                        spinlock_unlock(&a->lock);
+                        return false;
+                }
+                spinlock_unlock(&a->lock);
+        }
+        
+        /* Second, check the leaf node. */
+        for (i = 0; i < leaf->keys; i++) {
+                a = (as_area_t *) leaf->value[i];
+        
                 if (a == avoid_area)
                         continue;
-                        
+        
                 spinlock_lock(&a->lock);
-
-                a_start = a->base;
-                a_size = a->pages * PAGE_SIZE;
-
+                if (overlaps(va, size, a->base, a->pages * PAGE_SIZE)) {
+                        spinlock_unlock(&a->lock);
+                        return false;
+                }
                 spinlock_unlock(&a->lock);
-
-                if (overlaps(va, size, a_start, a_size))
-                        return false;           
-
         }