Changes in kernel/generic/src/mm/frame.c [64f3d3b:905721b] in mainline

File:

• kernel/generic/src/mm/frame.c (modified) (52 diffs)

kernel/generic/src/mm/frame.c

@@ -38 +38 @@
  *
  * This file contains the physical frame allocator and memory zone management.
- * The frame allocator is built on top of the two-level bitmap structure.
- *
+ * The frame allocator is built on top of the buddy allocator.
+ *
+ * @see buddy.c
  */
 
@@ -61 +62 @@
 #include <str.h>
 
-#define BITMAP_BLOCK_SIZE  128
-
 zones_t zones;
 
@@ -93 +92 @@
 }
 
+NO_TRACE static inline size_t make_frame_index(zone_t *zone, frame_t *frame)
+{
+        return (frame - zone->frames);
+}
+
 /** Initialize frame structure.
  *
@@ -100 +104 @@
 NO_TRACE static void frame_initialize(frame_t *frame)
 {
-        frame->refcount = 0;
-        frame->parent = NULL;
+        frame->refcount = 1;
+        frame->buddy_order = 0;
 }
 
@@ -157 +161 @@
         
         /* Move other zones up */
-        for (size_t j = zones.count; j > i; j--)
+        size_t j;
+        for (j = zones.count; j > i; j--) {
                 zones.info[j] = zones.info[j - 1];
+                if (zones.info[j].buddy_system != NULL)
+                        zones.info[j].buddy_system->data =
+                            (void *) &zones.info[j];
+        }
         
         zones.count++;
@@ -228 +237 @@
 }
 
-/** @return True if zone can allocate specified number of frames */
-NO_TRACE static bool zone_can_alloc(zone_t *zone, size_t count,
-    pfn_t constraint)
-{
-        /*
-         * The function bitmap_allocate_range() does not modify
-         * the bitmap if the last argument is NULL.
-         */
+/** @return True if zone can allocate specified order */
+NO_TRACE static bool zone_can_alloc(zone_t *zone, uint8_t order)
+{
         return ((zone->flags & ZONE_AVAILABLE) &&
-            bitmap_allocate_range(&zone->bitmap, count, zone->base,
-            constraint, NULL));
-}
-
-/** Find a zone that can allocate specified number of frames
+            buddy_system_can_alloc(zone->buddy_system, order));
+}
+
+/** Find a zone that can allocate order frames.
  *
  * Assume interrupts are disabled and zones lock is
  * locked.
  *
- * @param count      Number of free frames we are trying to find.
- * @param flags      Required flags of the target zone.
- * @param constraint Indication of bits that cannot be set in the
- *                   physical frame number of the first allocated frame.
- * @param hind       Preferred zone.
- *
- */
-NO_TRACE static size_t find_free_zone(size_t count, zone_flags_t flags,
-    pfn_t constraint, size_t hint)
+ * @param order Size (2^order) of free space we are trying to find.
+ * @param flags Required flags of the target zone.
+ * @param hind  Preferred zone.
+ *
+ */
+NO_TRACE static size_t find_free_zone(uint8_t order, zone_flags_t flags,
+    size_t hint)
 {
         if (hint >= zones.count)
@@ -266 +267 @@
                 if (ZONE_FLAGS_MATCH(zones.info[i].flags, flags)) {
                         /*
-                         * Check if the zone can satisfy the allocation request.
+                         * Check if the zone has 2^order frames area available.
                          */
-                        if (zone_can_alloc(&zones.info[i], count, constraint))
+                        if (zone_can_alloc(&zones.info[i], order))
                                 return i;
                 }
@@ -281 +282 @@
 }
 
+/**************************/
+/* Buddy system functions */
+/**************************/
+
+/** Buddy system find_block implementation.
+ *
+ * Find block that is parent of current list.
+ * That means go to lower addresses, until such block is found
+ *
+ * @param order Order of parent must be different then this
+ *              parameter!!
+ *
+ */
+NO_TRACE static link_t *zone_buddy_find_block(buddy_system_t *buddy,
+    link_t *child, uint8_t order)
+{
+        frame_t *frame = list_get_instance(child, frame_t, buddy_link);
+        zone_t *zone = (zone_t *) buddy->data;
+        
+        size_t index = frame_index(zone, frame);
+        do {
+                if (zone->frames[index].buddy_order != order)
+                        return &zone->frames[index].buddy_link;
+        } while (index-- > 0);
+        
+        return NULL;
+}
+
+/** Buddy system find_buddy implementation.
+ *
+ * @param buddy Buddy system.
+ * @param block Block for which buddy should be found.
+ *
+ * @return Buddy for given block if found.
+ *
+ */
+NO_TRACE static link_t *zone_buddy_find_buddy(buddy_system_t *buddy,
+    link_t *block)
+{
+        frame_t *frame = list_get_instance(block, frame_t, buddy_link);
+        zone_t *zone = (zone_t *) buddy->data;
+        ASSERT(IS_BUDDY_ORDER_OK(frame_index_abs(zone, frame),
+            frame->buddy_order));
+        
+        bool is_left = IS_BUDDY_LEFT_BLOCK_ABS(zone, frame);
+        
+        size_t index;
+        if (is_left) {
+                index = (frame_index(zone, frame)) +
+                    (1 << frame->buddy_order);
+        } else {  /* is_right */
+                index = (frame_index(zone, frame)) -
+                    (1 << frame->buddy_order);
+        }
+        
+        if (frame_index_valid(zone, index)) {
+                if ((zone->frames[index].buddy_order == frame->buddy_order) &&
+                    (zone->frames[index].refcount == 0)) {
+                        return &zone->frames[index].buddy_link;
+                }
+        }
+        
+        return NULL;
+}
+
+/** Buddy system bisect implementation.
+ *
+ * @param buddy Buddy system.
+ * @param block Block to bisect.
+ *
+ * @return Right block.
+ *
+ */
+NO_TRACE static link_t *zone_buddy_bisect(buddy_system_t *buddy, link_t *block)
+{
+        frame_t *frame_l = list_get_instance(block, frame_t, buddy_link);
+        frame_t *frame_r = (frame_l + (1 << (frame_l->buddy_order - 1)));
+        
+        return &frame_r->buddy_link;
+}
+
+/** Buddy system coalesce implementation.
+ *
+ * @param buddy   Buddy system.
+ * @param block_1 First block.
+ * @param block_2 First block's buddy.
+ *
+ * @return Coalesced block (actually block that represents lower
+ *         address).
+ *
+ */
+NO_TRACE static link_t *zone_buddy_coalesce(buddy_system_t *buddy,
+    link_t *block_1, link_t *block_2)
+{
+        frame_t *frame1 = list_get_instance(block_1, frame_t, buddy_link);
+        frame_t *frame2 = list_get_instance(block_2, frame_t, buddy_link);
+        
+        return ((frame1 < frame2) ? block_1 : block_2);
+}
+
+/** Buddy system set_order implementation.
+ *
+ * @param buddy Buddy system.
+ * @param block Buddy system block.
+ * @param order Order to set.
+ *
+ */
+NO_TRACE static void zone_buddy_set_order(buddy_system_t *buddy, link_t *block,
+    uint8_t order)
+{
+        list_get_instance(block, frame_t, buddy_link)->buddy_order = order;
+}
+
+/** Buddy system get_order implementation.
+ *
+ * @param buddy Buddy system.
+ * @param block Buddy system block.
+ *
+ * @return Order of block.
+ *
+ */
+NO_TRACE static uint8_t zone_buddy_get_order(buddy_system_t *buddy,
+    link_t *block)
+{
+        return list_get_instance(block, frame_t, buddy_link)->buddy_order;
+}
+
+/** Buddy system mark_busy implementation.
+ *
+ * @param buddy Buddy system.
+ * @param block Buddy system block.
+ *
+ */
+NO_TRACE static void zone_buddy_mark_busy(buddy_system_t *buddy, link_t *block)
+{
+        list_get_instance(block, frame_t, buddy_link)->refcount = 1;
+}
+
+/** Buddy system mark_available implementation.
+ *
+ * @param buddy Buddy system.
+ * @param block Buddy system block.
+ *
+ */
+NO_TRACE static void zone_buddy_mark_available(buddy_system_t *buddy,
+    link_t *block)
+{
+        list_get_instance(block, frame_t, buddy_link)->refcount = 0;
+}
+
+static buddy_system_operations_t zone_buddy_system_operations = {
+        .find_buddy = zone_buddy_find_buddy,
+        .bisect = zone_buddy_bisect,
+        .coalesce = zone_buddy_coalesce,
+        .set_order = zone_buddy_set_order,
+        .get_order = zone_buddy_get_order,
+        .mark_busy = zone_buddy_mark_busy,
+        .mark_available = zone_buddy_mark_available,
+        .find_block = zone_buddy_find_block
+};
+
 /******************/
 /* Zone functions */
 /******************/
 
-/** Return frame from zone. */
-NO_TRACE static frame_t *zone_get_frame(zone_t *zone, size_t index)
-{
-        ASSERT(index < zone->count);
-        
-        return &zone->frames[index];
-}
-
 /** Allocate frame in particular zone.
  *
@@ -298 +452 @@
  * Panics if allocation is impossible.
  *
- * @param zone       Zone to allocate from.
- * @param count      Number of frames to allocate
- * @param constraint Indication of bits that cannot be set in the
- *                   physical frame number of the first allocated frame.
+ * @param zone  Zone to allocate from.
+ * @param order Allocate exactly 2^order frames.
  *
  * @return Frame index in zone.
  *
  */
-NO_TRACE static size_t zone_frame_alloc(zone_t *zone, size_t count,
-    pfn_t constraint)
+NO_TRACE static pfn_t zone_frame_alloc(zone_t *zone, uint8_t order)
 {
         ASSERT(zone->flags & ZONE_AVAILABLE);
         
-        /* Allocate frames from zone */
-        size_t index;
-        int avail = bitmap_allocate_range(&zone->bitmap, count, zone->base,
-            constraint, &index);
-        
-        ASSERT(avail);
-        
-        /* Update frame reference count */
-        for (size_t i = 0; i < count; i++) {
-                frame_t *frame = zone_get_frame(zone, index + i);
-                
-                ASSERT(frame->refcount == 0);
-                frame->refcount = 1;
-        }
+        /* Allocate frames from zone buddy system */
+        link_t *link = buddy_system_alloc(zone->buddy_system, order);
+        
+        ASSERT(link);
         
         /* Update zone information. */
-        zone->free_count -= count;
-        zone->busy_count += count;
-        
-        return index;
+        zone->free_count -= (1 << order);
+        zone->busy_count += (1 << order);
+        
+        /* Frame will be actually a first frame of the block. */
+        frame_t *frame = list_get_instance(link, frame_t, buddy_link);
+        
+        /* Get frame address */
+        return make_frame_index(zone, frame);
 }
 
@@ -337 +482 @@
  * Assume zone is locked and is available for deallocation.
  *
- * @param zone  Pointer to zone from which the frame is to be freed.
- * @param index Frame index relative to zone.
- *
- * @return Number of freed frames.
- *
- */
-NO_TRACE static size_t zone_frame_free(zone_t *zone, size_t index)
+ * @param zone      Pointer to zone from which the frame is to be freed.
+ * @param frame_idx Frame index relative to zone.
+ *
+ * @return          Number of freed frames.
+ *
+ */
+NO_TRACE static size_t zone_frame_free(zone_t *zone, size_t frame_idx)
 {
         ASSERT(zone->flags & ZONE_AVAILABLE);
         
-        frame_t *frame = zone_get_frame(zone, index);
-        
-        ASSERT(frame->refcount > 0);
+        frame_t *frame = &zone->frames[frame_idx];
+        size_t size = 0;
+        
+        ASSERT(frame->refcount);
         
         if (!--frame->refcount) {
-                bitmap_set(&zone->bitmap, index, 0);
-                
+                size = 1 << frame->buddy_order;
+                buddy_system_free(zone->buddy_system, &frame->buddy_link);              
                 /* Update zone information. */
-                zone->free_count++;
-                zone->busy_count--;
-                
-                return 1;
-        }
-        
-        return 0;
+                zone->free_count += size;
+                zone->busy_count -= size;
+        }
+        
+        return size;
+}
+
+/** Return frame from zone. */
+NO_TRACE static frame_t *zone_get_frame(zone_t *zone, size_t frame_idx)
+{
+        ASSERT(frame_idx < zone->count);
+        return &zone->frames[frame_idx];
 }
 
 /** Mark frame in zone unavailable to allocation. */
-NO_TRACE static void zone_mark_unavailable(zone_t *zone, size_t index)
-{
-        if (!(zone->flags & ZONE_AVAILABLE))
+NO_TRACE static void zone_mark_unavailable(zone_t *zone, size_t frame_idx)
+{
+        ASSERT(zone->flags & ZONE_AVAILABLE);
+        
+        frame_t *frame = zone_get_frame(zone, frame_idx);
+        if (frame->refcount)
                 return;
         
-        frame_t *frame = zone_get_frame(zone, index);
-        if (frame->refcount > 0)
-                return;
-        
-        frame->refcount = 1;
-        bitmap_set_range(&zone->bitmap, index, 1);
-        
+        link_t *link __attribute__ ((unused));
+        
+        link = buddy_system_alloc_block(zone->buddy_system,
+            &frame->buddy_link);
+        
+        ASSERT(link);
         zone->free_count--;
         reserve_force_alloc(1);
@@ -383 +536 @@
 /** Merge two zones.
  *
+ * Expect buddy to point to space at least zone_conf_size large.
  * Assume z1 & z2 are locked and compatible and zones lock is
  * locked.
  *
- * @param z1       First zone to merge.
- * @param z2       Second zone to merge.
- * @param old_z1   Original data of the first zone.
- * @param confdata Merged zone configuration data.
+ * @param z1     First zone to merge.
+ * @param z2     Second zone to merge.
+ * @param old_z1 Original date of the first zone.
+ * @param buddy  Merged zone buddy.
  *
  */
 NO_TRACE static void zone_merge_internal(size_t z1, size_t z2, zone_t *old_z1,
-    void *confdata)
+    buddy_system_t *buddy)
 {
         ASSERT(zones.info[z1].flags & ZONE_AVAILABLE);
@@ -408 +562 @@
         zones.info[z1].free_count += zones.info[z2].free_count;
         zones.info[z1].busy_count += zones.info[z2].busy_count;
-        
-        bitmap_initialize(&zones.info[z1].bitmap, zones.info[z1].count,
-            BITMAP_BLOCK_SIZE, confdata +
-            (sizeof(frame_t) * zones.info[z1].count));
-        bitmap_clear_range(&zones.info[z1].bitmap, 0, zones.info[z1].count);
-        
-        zones.info[z1].frames = (frame_t *) confdata;
-        
-        /*
-         * Copy frames and bits from both zones to preserve parents, etc.
+        zones.info[z1].buddy_system = buddy;
+        
+        uint8_t order = fnzb(zones.info[z1].count);
+        buddy_system_create(zones.info[z1].buddy_system, order,
+            &zone_buddy_system_operations, (void *) &zones.info[z1]);
+        
+        zones.info[z1].frames =
+            (frame_t *) ((uint8_t *) zones.info[z1].buddy_system
+            + buddy_conf_size(order));
+        
+        /* This marks all frames busy */
+        size_t i;
+        for (i = 0; i < zones.info[z1].count; i++)
+                frame_initialize(&zones.info[z1].frames[i]);
+        
+        /* Copy frames from both zones to preserve full frame orders,
+         * parents etc. Set all free frames with refcount = 0 to 1, because
+         * we add all free frames to buddy allocator later again, clearing
+         * order to 0. Don't set busy frames with refcount = 0, as they
+         * will not be reallocated during merge and it would make later
+         * problems with allocation/free.
          */
-        
-        for (size_t i = 0; i < old_z1->count; i++) {
-                bitmap_set(&zones.info[z1].bitmap, i,
-                    bitmap_get(&old_z1->bitmap, i));
+        for (i = 0; i < old_z1->count; i++)
                 zones.info[z1].frames[i] = old_z1->frames[i];
-        }
-        
-        for (size_t i = 0; i < zones.info[z2].count; i++) {
-                bitmap_set(&zones.info[z1].bitmap, base_diff + i,
-                    bitmap_get(&zones.info[z2].bitmap, i));
-                zones.info[z1].frames[base_diff + i] =
-                    zones.info[z2].frames[i];
+        
+        for (i = 0; i < zones.info[z2].count; i++)
+                zones.info[z1].frames[base_diff + i]
+                    = zones.info[z2].frames[i];
+        
+        i = 0;
+        while (i < zones.info[z1].count) {
+                if (zones.info[z1].frames[i].refcount) {
+                        /* Skip busy frames */
+                        i += 1 << zones.info[z1].frames[i].buddy_order;
+                } else {
+                        /* Free frames, set refcount = 1
+                         * (all free frames have refcount == 0, we need not
+                         * to check the order)
+                         */
+                        zones.info[z1].frames[i].refcount = 1;
+                        zones.info[z1].frames[i].buddy_order = 0;
+                        i++;
+                }
+        }
+        
+        /* Add free blocks from the original zone z1 */
+        while (zone_can_alloc(old_z1, 0)) {
+                /* Allocate from the original zone */
+                pfn_t frame_idx = zone_frame_alloc(old_z1, 0);
+                
+                /* Free the frame from the merged zone */
+                frame_t *frame = &zones.info[z1].frames[frame_idx];
+                frame->refcount = 0;
+                buddy_system_free(zones.info[z1].buddy_system, &frame->buddy_link);
+        }
+        
+        /* Add free blocks from the original zone z2 */
+        while (zone_can_alloc(&zones.info[z2], 0)) {
+                /* Allocate from the original zone */
+                pfn_t frame_idx = zone_frame_alloc(&zones.info[z2], 0);
+                
+                /* Free the frame from the merged zone */
+                frame_t *frame = &zones.info[z1].frames[base_diff + frame_idx];
+                frame->refcount = 0;
+                buddy_system_free(zones.info[z1].buddy_system, &frame->buddy_link);
         }
 }
@@ -453 +649 @@
         size_t cframes = SIZE2FRAMES(zone_conf_size(count));
         
-        if ((pfn < zones.info[znum].base) ||
-            (pfn >= zones.info[znum].base + zones.info[znum].count))
+        if ((pfn < zones.info[znum].base)
+            || (pfn >= zones.info[znum].base + zones.info[znum].count))
                 return;
         
-        for (size_t i = 0; i < cframes; i++)
+        frame_t *frame __attribute__ ((unused));
+
+        frame = &zones.info[znum].frames[pfn - zones.info[znum].base];
+        ASSERT(!frame->buddy_order);
+        
+        size_t i;
+        for (i = 0; i < cframes; i++) {
+                zones.info[znum].busy_count++;
                 (void) zone_frame_free(&zones.info[znum],
                     pfn - zones.info[znum].base + i);
+        }
+}
+
+/** Reduce allocated block to count of order 0 frames.
+ *
+ * The allocated block needs 2^order frames. Reduce all frames
+ * in the block to order 0 and free the unneeded frames. This means that
+ * when freeing the previously allocated block starting with frame_idx,
+ * you have to free every frame.
+ *
+ * @param znum      Zone.
+ * @param frame_idx Index the first frame of the block.
+ * @param count     Allocated frames in block.
+ *
+ */
+NO_TRACE static void zone_reduce_region(size_t znum, pfn_t frame_idx,
+    size_t count)
+{
+        ASSERT(zones.info[znum].flags & ZONE_AVAILABLE);
+        ASSERT(frame_idx + count < zones.info[znum].count);
+        
+        uint8_t order = zones.info[znum].frames[frame_idx].buddy_order;
+        ASSERT((size_t) (1 << order) >= count);
+        
+        /* Reduce all blocks to order 0 */
+        size_t i;
+        for (i = 0; i < (size_t) (1 << order); i++) {
+                frame_t *frame = &zones.info[znum].frames[i + frame_idx];
+                frame->buddy_order = 0;
+                if (!frame->refcount)
+                        frame->refcount = 1;
+                ASSERT(frame->refcount == 1);
+        }
+        
+        /* Free unneeded frames */
+        for (i = count; i < (size_t) (1 << order); i++)
+                (void) zone_frame_free(&zones.info[znum], i + frame_idx);
 }
 
@@ -479 +719 @@
         bool ret = true;
         
-        /*
-         * We can join only 2 zones with none existing inbetween,
+        /* We can join only 2 zones with none existing inbetween,
          * the zones have to be available and with the same
          * set of flags
@@ -494 +733 @@
             + zones.info[z2].count));
         
+        uint8_t order;
+        if (cframes == 1)
+                order = 0;
+        else
+                order = fnzb(cframes - 1) + 1;
+        
         /* Allocate merged zone data inside one of the zones */
         pfn_t pfn;
-        if (zone_can_alloc(&zones.info[z1], cframes, 0)) {
-                pfn = zones.info[z1].base +
-                    zone_frame_alloc(&zones.info[z1], cframes, 0);
-        } else if (zone_can_alloc(&zones.info[z2], cframes, 0)) {
-                pfn = zones.info[z2].base +
-                    zone_frame_alloc(&zones.info[z2], cframes, 0);
+        if (zone_can_alloc(&zones.info[z1], order)) {
+                pfn = zones.info[z1].base + zone_frame_alloc(&zones.info[z1], order);
+        } else if (zone_can_alloc(&zones.info[z2], order)) {
+                pfn = zones.info[z2].base + zone_frame_alloc(&zones.info[z2], order);
         } else {
                 ret = false;
@@ -509 +752 @@
         /* Preserve original data from z1 */
         zone_t old_z1 = zones.info[z1];
+        old_z1.buddy_system->data = (void *) &old_z1;
         
         /* Do zone merging */
-        zone_merge_internal(z1, z2, &old_z1, (void *) PA2KA(PFN2ADDR(pfn)));
+        buddy_system_t *buddy = (buddy_system_t *) PA2KA(PFN2ADDR(pfn));
+        zone_merge_internal(z1, z2, &old_z1, buddy);
+        
+        /* Free unneeded config frames */
+        zone_reduce_region(z1, pfn - zones.info[z1].base, cframes);
         
         /* Subtract zone information from busy frames */
@@ -524 +772 @@
         
         /* Move zones down */
-        for (size_t i = z2 + 1; i < zones.count; i++)
+        size_t i;
+        for (i = z2 + 1; i < zones.count; i++) {
                 zones.info[i - 1] = zones.info[i];
+                if (zones.info[i - 1].buddy_system != NULL)
+                        zones.info[i - 1].buddy_system->data =
+                            (void *) &zones.info[i - 1];
+        }
         
         zones.count--;
@@ -544 +797 @@
 void zone_merge_all(void)
 {
-        size_t i = 1;
-        
+        size_t i = 0;
         while (i < zones.count) {
-                if (!zone_merge(i - 1, i))
+                if (!zone_merge(i, i + 1))
                         i++;
         }
@@ -554 +806 @@
 /** Create new frame zone.
  *
- * @param zone     Zone to construct.
- * @param start    Physical address of the first frame within the zone.
- * @param count    Count of frames in zone.
- * @param flags    Zone flags.
- * @param confdata Configuration data of the zone.
+ * @param zone  Zone to construct.
+ * @param buddy Address of buddy system configuration information.
+ * @param start Physical address of the first frame within the zone.
+ * @param count Count of frames in zone.
+ * @param flags Zone flags.
  *
  * @return Initialized zone.
  *
  */
-NO_TRACE static void zone_construct(zone_t *zone, pfn_t start, size_t count,
-    zone_flags_t flags, void *confdata)
+NO_TRACE static void zone_construct(zone_t *zone, buddy_system_t *buddy,
+    pfn_t start, size_t count, zone_flags_t flags)
 {
         zone->base = start;
@@ -571 +823 @@
         zone->free_count = count;
         zone->busy_count = 0;
+        zone->buddy_system = buddy;
         
         if (flags & ZONE_AVAILABLE) {
                 /*
-                 * Initialize frame bitmap (located after the array of
-                 * frame_t structures in the configuration space).
+                 * Compute order for buddy system and initialize
                  */
-                
-                bitmap_initialize(&zone->bitmap, count, BITMAP_BLOCK_SIZE,
-                    confdata + (sizeof(frame_t) * count));
-                bitmap_clear_range(&zone->bitmap, 0, count);
-                
-                /*
-                 * Initialize the array of frame_t structures.
-                 */
-                
-                zone->frames = (frame_t *) confdata;
-                
-                for (size_t i = 0; i < count; i++)
+                uint8_t order = fnzb(count);
+                buddy_system_create(zone->buddy_system, order,
+                    &zone_buddy_system_operations, (void *) zone);
+                
+                /* Allocate frames _after_ the confframe */
+                
+                /* Check sizes */
+                zone->frames = (frame_t *) ((uint8_t *) zone->buddy_system +
+                    buddy_conf_size(order));
+                
+                size_t i;
+                for (i = 0; i < count; i++)
                         frame_initialize(&zone->frames[i]);
-        } else {
-                bitmap_initialize(&zone->bitmap, 0, 0, NULL);
+                
+                /* Stuffing frames */
+                for (i = 0; i < count; i++) {
+                        zone->frames[i].refcount = 0;
+                        buddy_system_free(zone->buddy_system, &zone->frames[i].buddy_link);
+                }
+        } else
                 zone->frames = NULL;
-        }
 }
 
@@ -605 +861 @@
 size_t zone_conf_size(size_t count)
 {
-        return (count * sizeof(frame_t) +
-            bitmap_size(count, BITMAP_BLOCK_SIZE));
+        return (count * sizeof(frame_t) + buddy_conf_size(fnzb(count)));
 }
 
@@ -612 +867 @@
 pfn_t zone_external_conf_alloc(size_t count)
 {
-        size_t frames = SIZE2FRAMES(zone_conf_size(count));
-        
-        return ADDR2PFN((uintptr_t)
-            frame_alloc(frames, FRAME_LOWMEM | FRAME_ATOMIC, 0));
+        size_t size = zone_conf_size(count);
+        size_t order = ispwr2(size) ? fnzb(size) : (fnzb(size) + 1);
+
+        return ADDR2PFN((uintptr_t) frame_alloc(order - FRAME_WIDTH,
+            FRAME_LOWMEM | FRAME_ATOMIC));
 }
 
@@ -623 +879 @@
  * @param count     Size of zone in frames.
  * @param confframe Where configuration frames are supposed to be.
- *                  Automatically checks that we will not disturb the
+ *                  Automatically checks, that we will not disturb the
  *                  kernel and possibly init. If confframe is given
  *                  _outside_ this zone, it is expected, that the area is
@@ -640 +896 @@
         
         if (flags & ZONE_AVAILABLE) {  /* Create available zone */
-                /*
-                 * Theoretically we could have NULL here, practically make sure
+                /* Theoretically we could have NULL here, practically make sure
                  * nobody tries to do that. If some platform requires, remove
                  * the assert
                  */
                 ASSERT(confframe != ADDR2PFN((uintptr_t ) NULL));
-                
+
                 /* Update the known end of physical memory. */
                 config.physmem_end = max(config.physmem_end, PFN2ADDR(start + count));
                 
-                /*
-                 * If confframe is supposed to be inside our zone, then make sure
+                /* If confframe is supposed to be inside our zone, then make sure
                  * it does not span kernel & init
                  */
                 size_t confcount = SIZE2FRAMES(zone_conf_size(count));
-                
                 if ((confframe >= start) && (confframe < start + count)) {
                         for (; confframe < start + count; confframe++) {
@@ -668 +921 @@
                                 
                                 bool overlap = false;
-                                for (size_t i = 0; i < init.cnt; i++) {
+                                size_t i;
+                                for (i = 0; i < init.cnt; i++)
                                         if (overlaps(addr, PFN2ADDR(confcount),
                                             init.tasks[i].paddr,
@@ -675 +929 @@
                                                 break;
                                         }
-                                }
-                                
                                 if (overlap)
                                         continue;
@@ -693 +945 @@
                 }
                 
-                void *confdata = (void *) PA2KA(PFN2ADDR(confframe));
-                zone_construct(&zones.info[znum], start, count, flags, confdata);
+                buddy_system_t *buddy = (buddy_system_t *) PA2KA(PFN2ADDR(confframe));
+                zone_construct(&zones.info[znum], buddy, start, count, flags);
                 
                 /* If confdata in zone, mark as unavailable */
                 if ((confframe >= start) && (confframe < start + count)) {
-                        for (size_t i = confframe; i < confframe + confcount; i++)
+                        size_t i;
+                        for (i = confframe; i < confframe + confcount; i++)
                                 zone_mark_unavailable(&zones.info[znum],
                                     i - zones.info[znum].base);
@@ -714 +967 @@
                 return (size_t) -1;
         }
-        
-        zone_construct(&zones.info[znum], start, count, flags, NULL);
+        zone_construct(&zones.info[znum], NULL, start, count, flags);
         
         irq_spinlock_unlock(&zones.lock, true);
@@ -757 +1009 @@
 }
 
-/** Allocate frames of physical memory.
- *
- * @param count      Number of continuous frames to allocate.
- * @param flags      Flags for host zone selection and address processing.
- * @param constraint Indication of physical address bits that cannot be
- *                   set in the address of the first allocated frame.
- * @param pzone      Preferred zone.
+/** Allocate power-of-two frames of physical memory.
+ *
+ * @param order Allocate exactly 2^order frames.
+ * @param flags Flags for host zone selection and address processing.
+ * @param pzone Preferred zone.
  *
  * @return Physical address of the allocated frame.
  *
  */
-uintptr_t frame_alloc_generic(size_t count, frame_flags_t flags,
-    uintptr_t constraint, size_t *pzone)
-{
-        ASSERT(count > 0);
-        
+void *frame_alloc_generic(uint8_t order, frame_flags_t flags, size_t *pzone)
+{
+        size_t size = ((size_t) 1) << order;
         size_t hint = pzone ? (*pzone) : 0;
-        pfn_t frame_constraint = ADDR2PFN(constraint);
         
         /*
          * If not told otherwise, we must first reserve the memory.
          */
-        if (!(flags & FRAME_NO_RESERVE))
-                reserve_force_alloc(count);
-        
+        if (!(flags & FRAME_NO_RESERVE)) 
+                reserve_force_alloc(size);
+
 loop:
         irq_spinlock_lock(&zones.lock, true);
@@ -788 +1035 @@
          * First, find suitable frame zone.
          */
-        size_t znum = find_free_zone(count, FRAME_TO_ZONE_FLAGS(flags),
-            frame_constraint, hint);
-        
-        /*
-         * If no memory, reclaim some slab memory,
-         * if it does not help, reclaim all.
-         */
+        size_t znum = find_free_zone(order,
+            FRAME_TO_ZONE_FLAGS(flags), hint);
+        
+        /* If no memory, reclaim some slab memory,
+           if it does not help, reclaim all */
         if ((znum == (size_t) -1) && (!(flags & FRAME_NO_RECLAIM))) {
                 irq_spinlock_unlock(&zones.lock, true);
@@ -801 +1046 @@
                 
                 if (freed > 0)
-                        znum = find_free_zone(count, FRAME_TO_ZONE_FLAGS(flags),
-                            frame_constraint, hint);
+                        znum = find_free_zone(order,
+                            FRAME_TO_ZONE_FLAGS(flags), hint);
                 
                 if (znum == (size_t) -1) {
@@ -810 +1055 @@
                         
                         if (freed > 0)
-                                znum = find_free_zone(count, FRAME_TO_ZONE_FLAGS(flags),
-                                    frame_constraint, hint);
+                                znum = find_free_zone(order,
+                                    FRAME_TO_ZONE_FLAGS(flags), hint);
                 }
         }
@@ -818 +1063 @@
                 if (flags & FRAME_ATOMIC) {
                         irq_spinlock_unlock(&zones.lock, true);
-                        
                         if (!(flags & FRAME_NO_RESERVE))
-                                reserve_free(count);
-                        
-                        return 0;
+                                reserve_free(size);
+                        return NULL;
                 }
                 
@@ -832 +1075 @@
                 
                 if (!THREAD)
-                        panic("Cannot wait for %zu frames to become available "
-                            "(%zu available).", count, avail);
+                        panic("Cannot wait for memory to become available.");
                 
                 /*
@@ -840 +1082 @@
                 
 #ifdef CONFIG_DEBUG
-                printf("Thread %" PRIu64 " waiting for %zu frames "
-                    "(%zu available).\n", THREAD->tid, count, avail);
+                printf("Thread %" PRIu64 " waiting for %zu frames, "
+                    "%zu available.\n", THREAD->tid, size, avail);
 #endif
                 
                 /*
-                 * Since the mem_avail_mtx is an active mutex, we need to
-                 * disable interrupts to prevent deadlock with TLB shootdown.
+                 * Since the mem_avail_mtx is an active mutex, we need to disable interrupts
+                 * to prevent deadlock with TLB shootdown.
                  */
                 ipl_t ipl = interrupts_disable();
@@ -852 +1094 @@
                 
                 if (mem_avail_req > 0)
-                        mem_avail_req = min(mem_avail_req, count);
+                        mem_avail_req = min(mem_avail_req, size);
                 else
-                        mem_avail_req = count;
-                
+                        mem_avail_req = size;
                 size_t gen = mem_avail_gen;
                 
@@ -871 +1112 @@
         }
         
-        pfn_t pfn = zone_frame_alloc(&zones.info[znum], count,
-            frame_constraint) + zones.info[znum].base;
+        pfn_t pfn = zone_frame_alloc(&zones.info[znum], order)
+            + zones.info[znum].base;
         
         irq_spinlock_unlock(&zones.lock, true);
@@ -879 +1120 @@
                 *pzone = znum;
         
-        return PFN2ADDR(pfn);
-}
-
-uintptr_t frame_alloc(size_t count, frame_flags_t flags, uintptr_t constraint)
-{
-        return frame_alloc_generic(count, flags, constraint, NULL);
-}
-
-uintptr_t frame_alloc_noreserve(size_t count, frame_flags_t flags,
-    uintptr_t constraint)
-{
-        return frame_alloc_generic(count, flags | FRAME_NO_RESERVE, constraint,
-            NULL);
-}
-
-/** Free frames of physical memory.
- *
- * Find respective frame structures for supplied physical frames.
- * Decrement each frame reference count. If it drops to zero, mark
- * the frames as available.
- *
- * @param start Physical Address of the first frame to be freed.
- * @param count Number of frames to free.
+        if (flags & FRAME_KA)
+                return (void *) PA2KA(PFN2ADDR(pfn));
+        
+        return (void *) PFN2ADDR(pfn);
+}
+
+void *frame_alloc(uint8_t order, frame_flags_t flags)
+{
+        return frame_alloc_generic(order, flags, NULL);
+}
+
+void *frame_alloc_noreserve(uint8_t order, frame_flags_t flags)
+{
+        return frame_alloc_generic(order, flags | FRAME_NO_RESERVE, NULL);
+}
+
+/** Free a frame.
+ *
+ * Find respective frame structure for supplied physical frame address.
+ * Decrement frame reference count. If it drops to zero, move the frame
+ * structure to free list.
+ *
+ * @param frame Physical Address of of the frame to be freed.
  * @param flags Flags to control memory reservation.
  *
  */
-void frame_free_generic(uintptr_t start, size_t count, frame_flags_t flags)
-{
-        size_t freed = 0;
+void frame_free_generic(uintptr_t frame, frame_flags_t flags)
+{
+        size_t size;
         
         irq_spinlock_lock(&zones.lock, true);
         
-        for (size_t i = 0; i < count; i++) {
-                /*
-                 * First, find host frame zone for addr.
-                 */
-                pfn_t pfn = ADDR2PFN(start) + i;
-                size_t znum = find_zone(pfn, 1, 0);
-                
-                ASSERT(znum != (size_t) -1);
-                
-                freed += zone_frame_free(&zones.info[znum],
-                    pfn - zones.info[znum].base);
-        }
+        /*
+         * First, find host frame zone for addr.
+         */
+        pfn_t pfn = ADDR2PFN(frame);
+        size_t znum = find_zone(pfn, 1, 0);
+
+        ASSERT(znum != (size_t) -1);
+        
+        size = zone_frame_free(&zones.info[znum], pfn - zones.info[znum].base);
         
         irq_spinlock_unlock(&zones.lock, true);
@@ -928 +1166 @@
         /*
          * Signal that some memory has been freed.
-         * Since the mem_avail_mtx is an active mutex,
-         * we need to disable interruptsto prevent deadlock
-         * with TLB shootdown.
          */
-        
+
+        
+        /*
+         * Since the mem_avail_mtx is an active mutex, we need to disable interrupts
+         * to prevent deadlock with TLB shootdown.
+         */
         ipl_t ipl = interrupts_disable();
         mutex_lock(&mem_avail_mtx);
-        
         if (mem_avail_req > 0)
-                mem_avail_req -= min(mem_avail_req, freed);
+                mem_avail_req -= min(mem_avail_req, size);
         
         if (mem_avail_req == 0) {
@@ -943 +1182 @@
                 condvar_broadcast(&mem_avail_cv);
         }
-        
         mutex_unlock(&mem_avail_mtx);
         interrupts_restore(ipl);
         
         if (!(flags & FRAME_NO_RESERVE))
-                reserve_free(freed);
-}
-
-void frame_free(uintptr_t frame, size_t count)
-{
-        frame_free_generic(frame, count, 0);
-}
-
-void frame_free_noreserve(uintptr_t frame, size_t count)
-{
-        frame_free_generic(frame, count, FRAME_NO_RESERVE);
+                reserve_free(size);
+}
+
+void frame_free(uintptr_t frame)
+{
+        frame_free_generic(frame, 0);
+}
+
+void frame_free_noreserve(uintptr_t frame)
+{
+        frame_free_generic(frame, FRAME_NO_RESERVE);
 }
 
@@ -992 +1230 @@
         irq_spinlock_lock(&zones.lock, true);
         
-        for (size_t i = 0; i < count; i++) {
+        size_t i;
+        for (i = 0; i < count; i++) {
                 size_t znum = find_zone(start + i, 1, 0);
-                
                 if (znum == (size_t) -1)  /* PFN not found */
                         continue;
@@ -1019 +1257 @@
         /* Tell the architecture to create some memory */
         frame_low_arch_init();
-        
         if (config.cpu_active == 1) {
                 frame_mark_unavailable(ADDR2PFN(KA2PA(config.base)),
@@ -1026 +1263 @@
                     SIZE2FRAMES(config.stack_size));
                 
-                for (size_t i = 0; i < init.cnt; i++)
-                        frame_mark_unavailable(ADDR2PFN(init.tasks[i].paddr),
+                size_t i;
+                for (i = 0; i < init.cnt; i++) {
+                        pfn_t pfn = ADDR2PFN(init.tasks[i].paddr);
+                        frame_mark_unavailable(pfn,
                             SIZE2FRAMES(init.tasks[i].size));
+                }
                 
                 if (ballocs.size)
@@ -1034 +1274 @@
                             SIZE2FRAMES(ballocs.size));
                 
-                /*
-                 * Blacklist first frame, as allocating NULL would
+                /* Black list first frame, as allocating NULL would
                  * fail in some places
                  */
                 frame_mark_unavailable(0, 1);
         }
-        
         frame_high_arch_init();
 }
@@ -1046 +1284 @@
 /** Adjust bounds of physical memory region according to low/high memory split.
  *
- * @param low[in]      If true, the adjustment is performed to make the region
- *                     fit in the low memory. Otherwise the adjustment is
- *                     performed to make the region fit in the high memory.
- * @param basep[inout] Pointer to a variable which contains the region's base
- *                     address and which may receive the adjusted base address.
- * @param sizep[inout] Pointer to a variable which contains the region's size
- *                     and which may receive the adjusted size.
- *
- * @return True if the region still exists even after the adjustment.
- * @return False otherwise.
- *
+ * @param low[in]       If true, the adjustment is performed to make the region
+ *                      fit in the low memory. Otherwise the adjustment is
+ *                      performed to make the region fit in the high memory.
+ * @param basep[inout]  Pointer to a variable which contains the region's base
+ *                      address and which may receive the adjusted base address.
+ * @param sizep[inout]  Pointer to a variable which contains the region's size
+ *                      and which may receive the adjusted size.
+ * @retun               True if the region still exists even after the
+ *                      adjustment, false otherwise.
  */
 bool frame_adjust_zone_bounds(bool low, uintptr_t *basep, size_t *sizep)
 {
         uintptr_t limit = KA2PA(config.identity_base) + config.identity_size;
-        
+
         if (low) {
                 if (*basep > limit)
                         return false;
-                
                 if (*basep + *sizep > limit)
                         *sizep = limit - *basep;
@@ -1071 +1306 @@
                 if (*basep + *sizep <= limit)
                         return false;
-                
                 if (*basep <= limit) {
                         *sizep -= limit - *basep;
@@ -1077 +1311 @@
                 }
         }
-        
         return true;
 }
@@ -1089 +1322 @@
         
         uint64_t total = 0;
-        
-        for (size_t i = 0; i < zones.count; i++)
+        size_t i;
+        for (i = 0; i < zones.count; i++)
                 total += (uint64_t) FRAMES2SIZE(zones.info[i].count);
         
@@ -1113 +1346 @@
         *free = 0;
         
-        for (size_t i = 0; i < zones.count; i++) {
+        size_t i;
+        for (i = 0; i < zones.count; i++) {
                 *total += (uint64_t) FRAMES2SIZE(zones.info[i].count);
                 
@@ -1150 +1384 @@
          */
         
-        for (size_t i = 0;; i++) {
+        size_t i;
+        for (i = 0;; i++) {
                 irq_spinlock_lock(&zones.lock, true);
                 
@@ -1203 +1438 @@
         size_t znum = (size_t) -1;
         
-        for (size_t i = 0; i < zones.count; i++) {
+        size_t i;
+        for (i = 0; i < zones.count; i++) {
                 if ((i == num) || (PFN2ADDR(zones.info[i].base) == num)) {
                         znum = i;
@@ -1216 +1452 @@
         }
         
-        uintptr_t base = PFN2ADDR(zones.info[znum].base);
-        zone_flags_t flags = zones.info[znum].flags;
-        size_t count = zones.info[znum].count;
-        size_t free_count = zones.info[znum].free_count;
-        size_t busy_count = zones.info[znum].busy_count;
+        uintptr_t base = PFN2ADDR(zones.info[i].base);
+        zone_flags_t flags = zones.info[i].flags;
+        size_t count = zones.info[i].count;
+        size_t free_count = zones.info[i].free_count;
+        size_t busy_count = zones.info[i].busy_count;
         
         irq_spinlock_unlock(&zones.lock, true);