Changeset 6e8b3c8 in mainline

Timestamp:

2005-11-11T18:50:41Z (19 years ago)

Author:

Sergey Bondari <bondari@…>

Branches:

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

Children:

30187eb

Parents:

8a0b3730

Message:

Buddy system implementation. Not functional yet - only framework prepeared.
Also added 2 macros FRAME2ADDR and ADDR2FRAME.

Location:

generic

Files:

• include/mm/frame.h (modified) (4 diffs)
• src/mm/frame.c (modified) (7 diffs)

generic/include/mm/frame.h

@@ -34 +34 @@
 #include <list.h>
 #include <synch/spinlock.h>
+#include <mm/buddy.h>
 
 #define FRAME_KA        1       /* skip frames conflicting with user address space */
 #define FRAME_PANIC     2       /* panic on failure */
+
+#define FRAME2ADDR(zone, frame)         ((zone)->base + ((frame) - (zone)->frames) * FRAME_SIZE)
+#define ADDR2FRAME(zone, addr)          (&((zone)->frames[((addr) - (zone)->base) / FRAME_SIZE]))
 
 struct zone {
@@ -47 +51 @@
         count_t free_count;     /**< number of frame_t structures in free list */
         count_t busy_count;     /**< number of frame_t structures not in free list */
+        
+        buddy_system_t * buddy_system; /**< buddy system allocator for the zone */
         int flags;
 };
@@ -53 +59 @@
         count_t refcount;       /**< when == 0, the frame is in free list */
         link_t link;            /**< link to zone free list when refcount == 0 */
+        __u8 order;             /**< buddy system  block order */
+        link_t buddy_link;      /**< link to the next free block inside one order*/
 };
 
@@ -70 +78 @@
 
 /*
+ * Buddy system operations
+ */
+link_t * zone_buddy_find_buddy(link_t * buddy);
+link_t * zone_buddy_bisect(link_t * block);
+link_t * zone_buddy_coalesce(link_t * buddy_l, link_t * buddy_r);
+void zone_buddy_set_order(link_t * block, __u8 order);
+__u8 zone_buddy_get_order(link_t * block);
+
+__address zone_buddy_frame_alloc(int flags, __u8 order);
+void zone_buddy_frame_free(__address addr);
+
+/*
  * TODO: Implement the following functions.
  */

generic/src/mm/frame.c

@@ -42 +42 @@
 link_t zone_head;                /**< list of all zones in the system */
 
+static struct buddy_system_operations  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,
+};
+
 /** Initialize physical memory management
  *
@@ -119 +127 @@
         zone->busy_count++;
         
-        v = zone->base + (frame - zone->frames) * FRAME_SIZE;
+        //v = zone->base + (frame - zone->frames) * FRAME_SIZE;
+        v = FRAME2ADDR(zone, frame);
         
         if (flags & FRAME_KA)
@@ -176 +185 @@
         ASSERT(zone != NULL);
         
-        frame = &zone->frames[(addr - zone->base)/FRAME_SIZE];
+        frame = ADDR2FRAME(zone, addr);
+        // frame = &zone->frames[(addr - zone->base)/FRAME_SIZE];
         ASSERT(frame->refcount);
 
@@ -234 +244 @@
         ASSERT(zone != NULL);
         
-        frame = &zone->frames[(addr - zone->base)/FRAME_SIZE];
+        //frame = &zone->frames[(addr - zone->base)/FRAME_SIZE];
+        frame = ADDR2FRAME(zone, addr);
 
         if (!frame->refcount) {
@@ -293 +304 @@
         count_t cnt;
         int i;
+        __u8 max_order;
         
         ASSERT(start % FRAME_SIZE == 0);
@@ -323 +335 @@
                 }
                 
+                /*
+                 * Create buddy system for the zone
+                 */
+                for (max_order = 0; cnt >> max_order; max_order++);
+                z->buddy_system = buddy_system_create(max_order, &zone_buddy_system_operations);
         }
         
@@ -359 +376 @@
         link_initialize(&frame->link);
 }
+
+
+
+/*
+ * buddy system functions (under construction)
+ * 
+ */
+
+
+/** Allocate 2^order frames
+ *
+ */
+__address zone_buddy_frame_alloc(int flags, __u8 order) {
+        ipl_t ipl;
+        link_t *cur, *tmp;
+        zone_t *z;
+        zone_t *zone = NULL;
+        frame_t *frame = NULL;
+        __address v;
+        
+loop:
+        ipl = interrupts_disable();
+        spinlock_lock(&zone_head_lock);
+        
+        /*
+         * First, find suitable frame zone.
+         */
+        for (cur = zone_head.next; cur != &zone_head; cur = cur->next) {
+                z = list_get_instance(cur, zone_t, link);
+                
+                spinlock_lock(&z->lock);
+                /*
+                 * Check if the zone has 2^order frames area available
+                 * TODO: Must check if buddy system has at least block in order >= given order
+                 */
+                if (z->free_count == (1 >> order)) { 
+                        zone = z;
+                        break;
+                }
+                
+                spinlock_unlock(&z->lock);
+        }
+        
+        if (!zone) {
+                if (flags & FRAME_PANIC)
+                        panic("Can't allocate frame.\n");
+                
+                /*
+                 * TODO: Sleep until frames are available again.
+                 */
+                spinlock_unlock(&zone_head_lock);
+                interrupts_restore(ipl);
+
+                panic("Sleep not implemented.\n");
+                goto loop;
+        }
+                
+
+        /* Allocate frames from zone buddy system */
+        cur = buddy_system_alloc(zone->buddy_system, order);
+        
+        /* frame will be actually a first frame of the block */
+        frame = list_get_instance(cur, frame_t, buddy_link);
+        
+        /* get frame address */
+        v = FRAME2ADDR(zone, frame);
+        
+        if (flags & FRAME_KA)
+                v = PA2KA(v);
+        
+        spinlock_unlock(&zone->lock);
+        spinlock_unlock(&zone_head_lock);
+        interrupts_restore(ipl);
+        
+        return v;
+}
+
+
+/** Free frame(s)
+ *
+ * @param addr Address of the frame(s) to be freed. It must be a multiple of FRAME_SIZE.
+ */
+void zone_buddy_frame_free(__address addr)
+{
+        ipl_t ipl;
+        link_t *cur;
+        zone_t *z;
+        zone_t *zone = NULL;
+        frame_t *frame;
+        
+        ASSERT(addr % FRAME_SIZE == 0);
+        
+        ipl = interrupts_disable();
+        spinlock_lock(&zone_head_lock);
+        
+        /*
+         * First, find host frame zone for addr.
+         */
+        for (cur = zone_head.next; cur != &zone_head; cur = cur->next) {
+                z = list_get_instance(cur, zone_t, link);
+                
+                spinlock_lock(&z->lock);
+                
+                if (IS_KA(addr))
+                        addr = KA2PA(addr);
+                
+                /*
+                 * Check if addr belongs to z.
+                 */
+                if ((addr >= z->base) && (addr <= z->base + (z->free_count + z->busy_count) * FRAME_SIZE)) {
+                        zone = z;
+                        break;
+                }
+                spinlock_unlock(&z->lock);
+        }
+        
+        ASSERT(zone != NULL);
+        
+        frame = ADDR2FRAME(zone, addr);
+
+        ASSERT(frame->refcount);
+
+        if (!--frame->refcount) {
+                buddy_system_free(zone->buddy_system, &frame->buddy_link);
+        }
+        
+        spinlock_unlock(&zone->lock);   
+        
+        spinlock_unlock(&zone_head_lock);
+        interrupts_restore(ipl);
+}
+
+
+/** Buddy system find_buddy implementation
+ *
+ */
+link_t * zone_buddy_find_buddy(link_t * buddy) {
+
+}
+
+/** Buddy system bisect implementation
+ *
+ */
+link_t * zone_buddy_bisect(link_t * block) {
+
+}
+
+/** Buddy system coalesce implementation
+ *
+ */
+link_t * zone_buddy_coalesce(link_t * buddy_l, link_t * buddy_r) {
+
+}
+
+/** Buddy system set_order implementation
+ *
+ */
+void zone_buddy_set_order(link_t * block, __u8 order) {
+
+}
+
+/** Buddy system get_order implementation
+ *
+ */
+__u8 zone_buddy_get_order(link_t * block) {
+
+
+}