Changeset 30187eb in mainline

Timestamp:

2005-11-12T20:30:45Z (19 years ago)

Author:

Sergey Bondari <bondari@…>

Branches:

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

Children:

a4be38d

Parents:

6e8b3c8

Message:

Buddy system allocator implementation. Not checked. For review only.

Location:

generic

Files:

• include/mm/buddy.h (modified) (1 diff)
• include/mm/frame.h (modified) (5 diffs)
• src/mm/frame.c (modified) (1 diff)

generic/include/mm/buddy.h

@@ -36 +36 @@
 
 struct buddy_system_operations {
-        link_t *(* find_buddy)(link_t *);               /**< Return pointer to left-side or right-side buddy for block passed as argument. */
-        link_t *(* bisect)(link_t *);                   /**< Bisect the block passed as argument and return pointer to the new right-side buddy. */
-        link_t *(* coalesce)(link_t *, link_t *);       /**< Coalesce to buddies into a bigger block. */
-        void (*set_order)(link_t *, __u8);              /**< Set order of block passed as argument. */
-        __u8 (*get_order)(link_t *);                    /**< Return order of block passed as argument. */
+        link_t *(* find_buddy)(link_t *);                               /**< Return pointer to left-side or right-side buddy for block passed as argument. */
+        link_t *(* bisect)(link_t *);                                   /**< Bisect the block passed as argument and return pointer to the new right-side buddy. */
+        link_t *(* coalesce)(link_t *, link_t *);                       /**< Coalesce to buddies into a bigger block. */
+        void (*set_order)(link_t *, __u8);                              /**< Set order of block passed as argument. */
+        __u8 (*get_order)(link_t *);                                    /**< Return order of block passed as argument. */
 };
 

generic/include/mm/frame.h

@@ -1 +1 @@
 /*
  * Copyright (C) 2005 Jakub Jermar
+ * Copyright (C) 2005 Sergey Bondari
  * All rights reserved.
  *
@@ -39 +40 @@
 #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]))
+#define FRAME2ADDR(zone, frame)                 ((zone)->base + ((frame) - (zone)->frames) * FRAME_SIZE)
+#define ADDR2FRAME(zone, addr)                  (&((zone)->frames[((addr) - (zone)->base) / FRAME_SIZE]))
+#define FRAME_INDEX(zone, frame)                ((count_t)((frame) - (zone)->frames))
+#define IS_BUDDY_LEFT_BLOCK(zone, frame)        ((FRAME_INDEX((zone), (frame)) % (1 >> ((frame)->buddy_order + 1))) == 0)
+#define IS_BUDDY_RIGHT_BLOCK(zone, frame)       ((FRAME_INDEX((zone), (frame)) % (1 >> ((frame)->buddy_order + 1))) == (1 >> (frame)->buddy_order))
+
+
 
 struct zone {
@@ -52 +58 @@
         count_t busy_count;     /**< number of frame_t structures not in free list */
         
-        buddy_system_t * buddy_system; /**< buddy system allocator for the zone */
+        buddy_system_t * buddy_system; /**< buddy system for the zone */
         int flags;
 };
@@ -59 +65 @@
         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 */
+        __u8 buddy_order;       /**< buddy system block order */
         link_t buddy_link;      /**< link to the next free block inside one order*/
 };
@@ -76 +82 @@
 extern void frame_not_free(__address addr);
 extern void frame_region_not_free(__address start, __address stop);
+zone_t * get_zone_by_frame(frame_t * frame);
 
 /*

generic/src/mm/frame.c

@@ -508 +508 @@
 }
 
+/** Guess zone by frame instance address
+ *
+ * @param frame Frame
+ *
+ * @return Zone of given frame
+ */
+zone_t * get_zone_by_frame(frame_t * frame) {
+        link_t * cur;
+        zone_t * zone, *z;
+
+        ASSERT(frame);
+        /*
+         * 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);
+                
+                /*
+                 * Check if frame address belongs to z.
+                 */
+                if ((frame >= z->frames) && (frame <= z->frames + (z->free_count + z->busy_count))) {
+                        zone = z;
+                        break;
+                }
+                spinlock_unlock(&z->lock);
+        }
+        ASSERT(zone);
+        
+        return zone;
+
+
+}
 
 /** Buddy system find_buddy implementation
- *
- */
-link_t * zone_buddy_find_buddy(link_t * buddy) {
-
+ * @param block Block for which buddy should be found
+ *
+ * @return Buddy for given block if found
+ */
+link_t * zone_buddy_find_buddy(link_t * block) {
+        frame_t * frame, * f;
+        zone_t * zone;
+        link_t * cur;
+        bool is_left, is_right;
+
+        frame = list_get_instance(block, frame_t, buddy_link);
+        zone = get_zone_by_frame(frame);
+        
+        
+        /* 
+         * (FRAME_INDEX % 2^(ORDER+1)) == 0 ===> LEFT BUDDY 
+         * (FRAME_INDEX % 2^(ORDER+1)) == 2^(ORDER) ===> RIGHT BUDDY
+         */
+         
+        is_left = IS_BUDDY_LEFT_BLOCK(zone, frame);
+        is_right = IS_BUDDY_RIGHT_BLOCK(zone, frame);
+        
+        ASSERT((is_left || is_right) && (!is_left || !is_right));
+        
+        for (cur = &zone->buddy_system->order[frame->buddy_order]; cur; cur = cur->next) {
+                f = list_get_instance(cur, frame_t, buddy_link);
+                
+                ASSERT(f->buddy_order == frame->buddy_order);
+                
+                /* 
+                 * if found frame is coherent with our frame from the left 
+                 */
+                if ((FRAME_INDEX(zone, f) + 1 >> frame->buddy_order == FRAME_INDEX(zone, frame)) && is_right) {
+                        return cur;
+                }
+                
+                /* 
+                 * if found frame is coherent with our frame from the right 
+                 */
+                if ((FRAME_INDEX(zone,f) - 1 >> frame->buddy_order == FRAME_INDEX(zone, frame)) && is_left) {
+                        return cur;
+                }
+                
+        }
+        
+        return NULL;
+        
+        
 }
 
 /** Buddy system bisect implementation
  *
+ * @param block Block to bisect
+ *
+ * @return right block
  */
 link_t * zone_buddy_bisect(link_t * block) {
-
+        frame_t * frame_l, * frame_r;
+        zone_t * zone;
+        
+        frame_l = list_get_instance(block, frame_t, buddy_link);
+
+        zone = get_zone_by_frame(frame_l);
+        
+        frame_r = &zone->frames[FRAME_INDEX(zone, frame_l) + 1>>(frame_l->buddy_order-1)];
+
+
+        return &frame_r->buddy_link;
+        
 }
 
 /** Buddy system coalesce implementation
  *
- */
-link_t * zone_buddy_coalesce(link_t * buddy_l, link_t * buddy_r) {
+ * @param block_1 First block
+ * @param block_2 First block's buddy
+ *
+ * @return Coalesced block (actually block that represents lower address)
+ */
+link_t * zone_buddy_coalesce(link_t * block_1, link_t * block_2) {
+        frame_t * frame1, * frame2;
+        zone_t * zone;
+        
+        frame1 = list_get_instance(block_1, frame_t, buddy_link);
+        frame2 = list_get_instance(block_2, frame_t, buddy_link);
+        
+        zone = get_zone_by_frame(frame1);
+        
+        return FRAME_INDEX(zone, frame1) < FRAME_INDEX(zone, frame2) ? block_1 : block_2;
 
 }
 
 /** Buddy system set_order implementation
- *
+ * @param block Buddy system block
+ * @param order Order to set
  */
 void zone_buddy_set_order(link_t * block, __u8 order) {
-
+        frame_t * frame;
+        frame = list_get_instance(block, frame_t, buddy_link);
+        frame->buddy_order = order;
 }
 
 /** Buddy system get_order implementation
- *
+ * @param block Buddy system block
+ *
+ * @return Order of block
  */
 __u8 zone_buddy_get_order(link_t * block) {
-
-
-}
+        frame_t * frame;
+        frame = list_get_instance(block, frame_t, buddy_link);
+        return frame->buddy_order;
+}