Changeset 26258

Timestamp:

07/04/08 21:12:34 (5 months ago)

Author:

mmlr

Message:

Make the all_areas list ordered by base and take advantage of this ordering
when looking up the target area on free(). This makes free() scale better with
large area counts, as the lookup can abort early when it knows that no area
below the only candidate can contain the address.

Files:

• haiku/trunk/src/system/kernel/heap.cpp (modified) (5 diffs)

haiku/trunk/src/system/kernel/heap.cpp

@@ -642 +642 @@
         uint32 totalFreePageCount = 0;
         heap_area *area = heap->all_areas;
-        while (area) {
+        while (area != NULL) {
                 // validate the free pages list
                 uint32 freePageCount = 0;
@@ -694 +694 @@
         heap_area *lastArea = NULL;
         uint32 lastFreeCount = 0;
-        while (area) {
+        while (area != NULL) {
                 if (area->free_page_count < lastFreeCount)
-                        panic("ordering of area list broken\n");
+                        panic("size ordering of area list broken\n");
 
                 if (area->prev != lastArea)
@@ -704 +704 @@
                 lastFreeCount = area->free_page_count;
                 area = area->next;
+        }
+
+        lastArea = NULL;
+        area = heap->all_areas;
+        while (area != NULL) {
+                if (lastArea != NULL && lastArea->base < area->base)
+                        panic("base ordering of all_areas list broken\n");
+
+                lastArea = area;
+                area = area->all_next;
         }
 
@@ -846 +856 @@
         }
 
-        area->all_next = heap->all_areas;
-        heap->all_areas = area;
+        // insert this area in the all_areas list so it stays ordered by base
+        if (heap->all_areas == NULL || heap->all_areas->base < area->base) {
+                area->all_next = heap->all_areas;
+                heap->all_areas = area;
+        } else {
+                heap_area *insert = heap->all_areas;
+                while (insert->all_next && insert->all_next->base > area->base)
+                        insert = insert->all_next;
+
+                area->all_next = insert->all_next;
+                insert->all_next = area;
+        }
+
         heap->total_pages += area->page_count;
         heap->total_free_pages += area->free_page_count;
@@ -1284 +1305 @@
         heap_area *area = heap->all_areas;
         while (area) {
-                if ((addr_t)address >= area->base
-                        && (addr_t)address < area->base + area->size)
+                // since the all_areas list is ordered by base with the biggest
+                // base at the top, we need only find the first area with a base
+                // smaller than our address to become our only candidate for freeing
+                if (area->base <= (addr_t)address) {
+                        if ((addr_t)address >= area->base + area->size) {
+                                // the only candidate area doesn't contain the address,
+                                // set it to NULL so we return below (none of the other areas
+                                // can contain the address as the list is ordered)
+                                area = NULL;
+                        }
+
                         break;
+                }
 
                 area = area->all_next;