WebSVN – HelenOS-historic – Diff – /kernel/trunk/generic/src/mm/frame.c

  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  */
+/*
+ * Locking order
+ *
+ * In order to access particular zone, the process must first lock
+ * the zones.lock, then lock the zone and then unlock the zones.lock.
+ * This insures, that we can fiddle with the zones in runtime without
+ * affecting the processes.
+ *
+ */
 #include <typedefs.h>
 #include <arch/types.h>
-#include <mm/heap.h>
 #include <mm/frame.h>
 #include <mm/as.h>
 #include <panic.h>
 #include <debug.h>
 #include <adt/list.h>
 #include <synch/spinlock.h>
 #include <arch/asm.h>
 #include <arch.h>
 #include <print.h>
 #include <align.h>
+#include <mm/slab.h>
+typedef struct {
+    count_t refcount;   /**< tracking of shared frames  */
+    __u8 buddy_order;   /**< buddy system block order */
+    link_t buddy_link;  /**< link to the next free block inside one order */
+    void *parent;           /**< If allocated by slab, this points there */
+}frame_t;
+typedef struct {
-SPINLOCK_INITIALIZE(zone_head_lock);    /**< this lock protects zone_head list */
+    SPINLOCK_DECLARE(lock); /**< this lock protects everything below */
+    pfn_t base; /**< frame_no of the first frame in the frames array */
-LIST_INITIALIZE(zone_head);             /**< list of all zones in the system */
+    pfn_t count;          /**< Size of zone */
+    frame_t *frames;    /**< array of frame_t structures in this zone */
+    count_t free_count; /**< number of free frame_t structures */
+    count_t busy_count; /**< number of busy frame_t structures */
+    buddy_system_t * buddy_system; /**< buddy system for the zone */
+    int flags;
+}zone_t;
-/** Blacklist containing non-available areas of memory.
- *
+/*
- * This blacklist is used to exclude frames that cannot be allocated
+ * The zoneinfo.lock must be locked when accessing zoneinfo structure.
- * (e.g. kernel memory) from available memory map.
+ * Some of the attributes in zone_t structures are 'read-only'
  */
-region_t zone_blacklist[ZONE_BLACKLIST_SIZE];
-count_t zone_blacklist_count = 0;
-static struct buddy_system_operations  zone_buddy_system_operations = {
-    .find_buddy = zone_buddy_find_buddy,
-    .bisect = zone_buddy_bisect,
+struct {
-    .coalesce = zone_buddy_coalesce,
+    SPINLOCK_DECLARE(lock);
-    .set_order = zone_buddy_set_order,
+    int count;
-    .get_order = zone_buddy_get_order,
+    zone_t *info[ZONES_MAX];
-    .mark_busy = zone_buddy_mark_busy,
-};
+}zones;
+/*********************************/
+/* Helper functions */
+static inline index_t frame_index(zone_t *zone, frame_t *frame)
+{
+    return (index_t)(frame - zone->frames);
+}
+static inline index_t frame_index_abs(zone_t *zone, frame_t *frame)
+{
+    return (index_t)(frame - zone->frames) + zone->base;
+}
+static inline int frame_index_valid(zone_t *zone, index_t index)
+{
+    return index >= 0 && index < zone->count;
+}
+/** Compute pfn_t from frame_t pointer & zone pointer */
+static pfn_t make_frame_index(zone_t *zone, frame_t *frame)
+{
+    return frame - zone->frames;
+}
-/** Initialize physical memory management
+/** Initialize frame structure
+ *
- * Initialize physical memory managemnt.
+ * Initialize frame structure.
+ *
+ * @param frame Frame structure to be initialized.
  */
-void frame_init(void)
+static void frame_initialize(frame_t *frame)
+{
-    if (config.cpu_active == 1) {
+    frame->refcount = 1;
-        frame_region_not_free(KA2PA(config.base), config.kernel_size);
-        if (config.init_size > 0)
+    frame->buddy_order = 0;
-            frame_region_not_free(KA2PA(config.init_addr), config.init_size);
+}
+/*************************************/
+/* Zoneinfo functions */
+/**
+ * Insert-sort zone into zones list
+ */
+static void zones_add_zone(zone_t *zone)
+{
+    int i;
+    spinlock_lock(&zones.lock);
-    frame_arch_init();
+    /* Try to merge */
+    if (zone->flags & ZONE_JOIN) {
+        for (i=0; i < zones.count; i++) {
+            spinlock_lock(&zones.info[i]->lock);
+            /* Join forward, join backward */
+            panic("Not implemented");
+            spinlock_unlock(&zones.info[i]->lock);
+        }
+        spinlock_unlock(&zones.lock);
+    } else {
+        if (zones.count+1 == ZONES_MAX)
+            panic("Maximum zone(%d) count exceeded.", ZONES_MAX);
+        zones.info[zones.count++] = zone;
+    }
+    spinlock_unlock(&zones.lock);
+}
 /**
- * Find AND LOCK zone that can allocate order frames
+ * Try to find a zone where can we find the frame
+ *
+ * @param hint Start searching in zone 'hint'
+ * @param lock Lock zone if true
+ *
- * Assume zone_head_lock is locked.
+ * Assume interrupts disable
  */
-static zone_t * find_free_zone(__u8 order)
+static zone_t * find_zone_and_lock(pfn_t frame, int *pzone)
+{
-    link_t *cur;
+    int i;
+    int hint = pzone ? *pzone : 0;
     zone_t *z;
-    for (cur = zone_head.next; cur != &zone_head;cur = cur->next) {
-        z = list_get_instance(cur, zone_t, link);
+    spinlock_lock(&zones.lock);
-        spinlock_lock(&z->lock);
+    if (hint >= zones.count || hint < 0)
+        hint = 0;
+    i = hint;
+    do {
+        z = zones.info[i];
+        spinlock_lock(&z->lock);
-        /* Check if the zone has 2^order frames area available  */
+        if (z->base <= frame && z->base + z->count > frame) {
-        if (buddy_system_can_alloc(z->buddy_system, order))
+            spinlock_unlock(&zones.lock); /* Unlock the global lock */
+            if (pzone)
+                *pzone = i;
             return z;
-        spinlock_unlock(&z->lock);
+        }
+        spinlock_unlock(&z->lock);
+        i++;
+        if (i >= zones.count)
+            i = 0;
+    } while(i != hint);
+    spinlock_unlock(&zones.lock);
     return NULL;
+}
+/**
-/** Allocate power-of-two frames of physical memory.
+ * Find AND LOCK zone that can allocate order frames
+ *
- * @param flags Flags for host zone selection and address processing.
- * @param order Allocate exactly 2^order frames.
+ * Assume interrupts are disabled!!
- * @param pzone Pointer to preferred zone pointer, on output it changes
- *              to the zone that the frame was really allocated to
+ *
- * @return Allocated frame.
+ * @param pzone Pointer to preferred zone or NULL, on return contains zone number
  */
-__address frame_alloc_generic(__u8 order, int flags, int * status, zone_t **pzone)
+static zone_t * find_free_zone_lock(__u8 order, int *pzone)
+{
-    ipl_t ipl;
+    int i;
-    link_t *tmp;
+    zone_t *z;
-    zone_t *zone = NULL;
+    int hint = pzone ? *pzone : 0;
-    frame_t *frame = NULL;
-    int freed;
-    __address v;
+    spinlock_lock(&zones.lock);
+    if (hint >= zones.count)
+        hint = 0;
+    i = hint;
-loop:
+    do {
-    ipl = interrupts_disable();
+        z = zones.info[i];
-    spinlock_lock(&zone_head_lock);
-    /*
-     * First, find suitable frame zone.
-     */
-    if (pzone && *pzone) {
-        spinlock_lock(&(*pzone)->lock);
+        spinlock_lock(&z->lock);
-        if (!buddy_system_can_alloc((*pzone)->buddy_system, order))
-            spinlock_unlock(&(*pzone)->lock);
-        else
-            zone = *pzone;
-    }
-    if (!zone) {
-        zone = find_free_zone(order);
-        /* If no memory, reclaim some slab memory,
-           if it does not help, reclaim all */
+        /* Check if the zone has 2^order frames area available  */
-        if (!zone && !(flags & FRAME_NO_RECLAIM)) {
+        if (buddy_system_can_alloc(z->buddy_system, order)) {
-            spinlock_unlock(&zone_head_lock);
+            spinlock_unlock(&zones.lock);
-            freed = slab_reclaim(0);
-            spinlock_lock(&zone_head_lock);
-            if (freed)
+            if (pzone)
-                zone = find_free_zone(order);
-            if (!zone) {
+                *pzone = i;
-                spinlock_unlock(&zone_head_lock);
-                freed = slab_reclaim(SLAB_RECLAIM_ALL);
-                spinlock_lock(&zone_head_lock);
-                if (freed)
+            return z;
-                    zone = find_free_zone(order);
-            }
+        }
+        spinlock_unlock(&z->lock);
+        if (++i >= zones.count)
+            i = 0;
+    } while(i != hint);
+    spinlock_unlock(&zones.lock);
+    return NULL;
+}
-    if (!zone) {
-        if (flags & FRAME_PANIC)
+/********************************************/
-            panic("Can't allocate frame.\n");
+/* Buddy system functions */
+/** Buddy system find_block implementation
-        /*
+ *
-         * TODO: Sleep until frames are available again.
+ * 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!!
-         */
+ */
+static link_t *zone_buddy_find_block(buddy_system_t *b, link_t *child,
-        spinlock_unlock(&zone_head_lock);
+                     __u8 order)
+{
+    frame_t * frame;
-        interrupts_restore(ipl);
+    zone_t * zone;
+    index_t index;
+    frame = list_get_instance(child, frame_t, buddy_link);
-        if (flags & FRAME_ATOMIC) {
+    zone = (zone_t *) b->data;
-            ASSERT(status != NULL);
+    index = frame_index(zone, frame);
+    do {
+        if (zone->frames[index].buddy_order != order) {
-            *status = FRAME_NO_MEMORY;
+            return &zone->frames[index].buddy_link;
+        }
+    } while(index-- > 0);
-            return NULL;
+    return NULL;
+}
-        panic("Sleep not implemented.\n");
-        goto loop;
-    }
-    /* Allocate frames from zone buddy system */
-    tmp = buddy_system_alloc(zone->buddy_system, order);
+/** Buddy system find_buddy implementation
+ *
+ * @param b Buddy system.
+ * @param block Block for which buddy should be found
+ *
+ * @return Buddy for given block if found
+ */
+static link_t * zone_buddy_find_buddy(buddy_system_t *b, link_t * block)
+{
+    frame_t * frame;
+    zone_t * zone;
-    ASSERT(tmp);
+    index_t index;
+    bool is_left, is_right;
-    /* Update zone information. */
+    frame = list_get_instance(block, frame_t, buddy_link);
-    zone->free_count -= (1 << order);
+    zone = (zone_t *) b->data;
-    zone->busy_count += (1 << order);
+    ASSERT(IS_BUDDY_ORDER_OK(frame_index_abs(zone, frame), frame->buddy_order));
-    /* Frame will be actually a first frame of the block. */
+    is_left = IS_BUDDY_LEFT_BLOCK_ABS(zone, frame);
-    frame = list_get_instance(tmp, frame_t, buddy_link);
+    is_right = IS_BUDDY_RIGHT_BLOCK_ABS(zone, frame);
-    /* get frame address */
+    ASSERT(is_left ^ is_right);
+    if (is_left) {
+        index = (frame_index(zone, frame)) + (1 << frame->buddy_order);
-    v = FRAME2ADDR(zone, frame);
+    } else { // if (is_right)
+        index = (frame_index(zone, frame)) - (1 << frame->buddy_order);
+    }
-    spinlock_unlock(&zone->lock);
-    spinlock_unlock(&zone_head_lock);
-    interrupts_restore(ipl);
-    ASSERT(v == ALIGN_UP(v, FRAME_SIZE << 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;
+        }
+    }
-    if (flags & FRAME_KA)
-        v = PA2KA(v);
+    return NULL;
+}
+/** Buddy system bisect implementation
+ *
-    if (status)
+ * @param b Buddy system.
+ * @param block Block to bisect
+ *
-        *status = FRAME_OK;
+ * @return right block
+ */
+static link_t * zone_buddy_bisect(buddy_system_t *b, link_t * block) {
+    frame_t * frame_l, * frame_r;
-    if (pzone)
+    frame_l = list_get_instance(block, frame_t, buddy_link);
-        *pzone = zone;
+    frame_r = (frame_l + (1 << (frame_l->buddy_order - 1)));
-    return v;
+    return &frame_r->buddy_link;
+}
-/** Convert address to zone pointer
+/** Buddy system coalesce implementation
+ *
+ * @param b Buddy system.
+ * @param block_1 First block
- * Assume zone_head_lock is held
+ * @param block_2 First block's buddy
+ *
- * @param addr Physical address
- * @param lock If true, lock the zone
+ * @return Coalesced block (actually block that represents lower address)
  */
-static zone_t * addr2zone(__address addr, int lock)
+static link_t * zone_buddy_coalesce(buddy_system_t *b, link_t * block_1,
-{
-    link_t *cur;
+                    link_t * block_2) {
-    zone_t *z = NULL;
+    frame_t *frame1, *frame2;
-    for (cur = zone_head.next; cur != &zone_head; cur = cur->next) {
+    frame1 = list_get_instance(block_1, frame_t, buddy_link);
-        z = list_get_instance(cur, zone_t, link);
+    frame2 = list_get_instance(block_2, frame_t, buddy_link);
-        spinlock_lock(&z->lock);
+    return frame1 < frame2 ? block_1 : block_2;
+}
+/** Buddy system set_order implementation
-        /*
+ *
+ * @param b Buddy system.
+ * @param block Buddy system block
-         * Check if addr belongs to z.
+ * @param order Order to set
-         */
+ */
-        if ((addr >= z->base) && (addr <= z->base + (z->free_count + z->busy_count) * FRAME_SIZE)) {
+static void zone_buddy_set_order(buddy_system_t *b, link_t * block, __u8 order) {
-            if (!lock)
+    frame_t * frame;
-                spinlock_unlock(&z->lock);
+    frame = list_get_instance(block, frame_t, buddy_link);
-            return z;
+    frame->buddy_order = order;
+}
+/** Buddy system get_order implementation
+ *
+ * @param b Buddy system.
-        spinlock_unlock(&z->lock);
+ * @param block Buddy system block
+ *
+ * @return Order of block
+ */
+static __u8 zone_buddy_get_order(buddy_system_t *b, link_t * block) {
+    frame_t * frame;
+    frame = list_get_instance(block, frame_t, buddy_link);
+    return frame->buddy_order;
+}
+/** Buddy system mark_busy implementation
+ *
+ * @param b Buddy system
+ * @param block Buddy system block
+ *
+ */
+static void zone_buddy_mark_busy(buddy_system_t *b, link_t * block) {
+    frame_t * frame;
-    panic("Cannot find addr2zone: 0x%X", addr);
+    frame = list_get_instance(block, frame_t, buddy_link);
+    frame->refcount = 1;
+}
-/** Return frame_t structure corresponding to address
+/** Buddy system mark_available implementation
+ *
+ * @param b Buddy system
+ * @param block Buddy system block
+ *
  */
-frame_t * frame_addr2frame(__address addr)
+static void zone_buddy_mark_available(buddy_system_t *b, link_t * block) {
-{
-    ipl_t ipl;
-    frame_t *frame;
+    frame_t * frame;
-    zone_t *zone;
-    if (IS_KA(addr))
-        addr = KA2PA(addr);
-    /* Disable interrupts to avoid deadlocks with interrupt handlers */
-    ipl = interrupts_disable();
-    spinlock_lock(&zone_head_lock);
-    zone = addr2zone(addr,0);
-    frame = ADDR2FRAME(zone, addr);
+    frame = list_get_instance(block, frame_t, buddy_link);
-    spinlock_unlock(&zone_head_lock);
-    interrupts_restore(ipl);
+    frame->refcount = 0;
-    return frame;
+}
+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,
+    .mark_busy = zone_buddy_mark_busy,
+    .mark_available = zone_buddy_mark_available,
+    .find_block = zone_buddy_find_block
+};
+/*************************************/
+/* Zone functions */
-/** Free a frame.
+/** Allocate frame in particular zone
+ *
- * Find respective frame structrue for supplied addr.
- * Decrement frame reference count.
+ * Assume zone is locked
- * If it drops to zero, move the frame structure to free list.
+ *
- * @param addr Address of the frame to be freed. It must be a multiple of FRAME_SIZE.
+ * @return Frame index in zone
  */
-void frame_free(__address addr)
+static pfn_t zone_frame_alloc(zone_t *zone,__u8 order, int flags, int *status)
+{
-    ipl_t ipl;
+    pfn_t v;
-    zone_t *zone;
+    link_t *tmp;
     frame_t *frame;
-    int order;
+    /* Allocate frames from zone buddy system */
+    tmp = buddy_system_alloc(zone->buddy_system, order);
-    ASSERT(addr % FRAME_SIZE == 0);
+    ASSERT(tmp);
+    /* Update zone information. */
-    if (IS_KA(addr))
+    zone->free_count -= (1 << order);
-        addr = KA2PA(addr);
+    zone->busy_count += (1 << order);
-    ipl = interrupts_disable();
+    /* Frame will be actually a first frame of the block. */
-    spinlock_lock(&zone_head_lock);
+    frame = list_get_instance(tmp, frame_t, buddy_link);
+    /* get frame address */
+    v = make_frame_index(zone, frame);
+    return v;
+}
+/** Free frame from zone
-    /*
+ *
-     * First, find host frame zone for addr.
+ * Assume zone is locked
-     */
+ */
-    zone = addr2zone(addr, 1); /* This locks the zone automatically */
+static void zone_frame_free(zone_t *zone, pfn_t frame_idx)
+{
+    frame_t *frame;
+    __u8 order;
-    frame = ADDR2FRAME(zone, addr);
+    frame = &zone->frames[frame_idx];
     /* remember frame order */
     order = frame->buddy_order;
     ASSERT(frame->refcount);
+    }
     /* Update zone information. */
     zone->free_count += (1 << order);
     zone->busy_count -= (1 << order);
-    spinlock_unlock(&zone->lock);
-    spinlock_unlock(&zone_head_lock);
-    interrupts_restore(ipl);
+}
-/** Mark frame region not free.
+/** Return frame from zone */
- *
- * Mark frame region not free.
- *
- * @param base Base address of non-available region.
- * @param size Size of non-available region.
- */
-void frame_region_not_free(__address base, size_t size)
+static frame_t * zone_get_frame(zone_t *zone, pfn_t frame_idx)
+{
-    index_t index;
-    index = zone_blacklist_count++;
+    ASSERT(frame_idx < zone->count);
-    /* Force base to the nearest lower address frame boundary. */
-    base = ALIGN_DOWN(base, FRAME_SIZE);
-    /* Align size to frame boundary. */
+    return &zone->frames[frame_idx];
-    size = ALIGN_UP(size, FRAME_SIZE);
-    ASSERT(index < ZONE_BLACKLIST_SIZE);
-    zone_blacklist[index].base = base;
-    zone_blacklist[index].size = size;
+}
-/** Create frame zones in region of available memory.
+/** Mark frame in zone unavailable to allocation */
- *
- * Avoid any black listed areas of non-available memory.
- * Assume that the black listed areas cannot overlap
- * one another or cross available memory region boundaries.
- *
- * @param base Base address of available memory region.
- * @param size Size of the region.
- */
-void zone_create_in_region(__address base, size_t size) {
+static void zone_mark_unavailable(zone_t *zone, pfn_t frame_idx)
-    int i;
-    zone_t * z;
-    __address s;
-    size_t sz;
-    ASSERT(base % FRAME_SIZE == 0);
-    ASSERT(size % FRAME_SIZE == 0);
+{
-    if (!size)
-        return;
+    frame_t *frame;
-    for (i = 0; i < zone_blacklist_count; i++) {
-        if (zone_blacklist[i].base >= base && zone_blacklist[i].base < base + size) {
-            s = base; sz = zone_blacklist[i].base - base;
-            ASSERT(base != s || sz != size);
-            zone_create_in_region(s, sz);
-            s = zone_blacklist[i].base + zone_blacklist[i].size;
-            sz = (base + size) - (zone_blacklist[i].base + zone_blacklist[i].size);
-            ASSERT(base != s || sz != size);
-            zone_create_in_region(s, sz);
-            return;
+    link_t *link;
-        }
-    }
-    z = zone_create(base, size, 0);
-    if (!z) {
-        panic("Cannot allocate zone (base=%P, size=%d).\n", base, size);
-    }
+    frame = zone_get_frame(zone, frame_idx);
+    link = buddy_system_alloc_block(zone->buddy_system,
+                    &frame->buddy_link);
+    ASSERT(link);
-    zone_attach(z);
+    zone->free_count--;
+}
 /** Create frame zone
+ *
  * Create new frame zone.
+ *
  * @param start Physical address of the first frame within the zone.
  * @param size Size of the zone. Must be a multiple of FRAME_SIZE.
+ * @param conffram Address of configuration frame
  * @param flags Zone flags.
+ *
  * @return Initialized zone.
  */
-zone_t * zone_create(__address start, size_t size, int flags)
+static zone_t * zone_construct(pfn_t start, pfn_t count,
+                   zone_t *z, int flags)
+{
-    zone_t *z;
-    count_t cnt;
     int i;
     __u8 max_order;
-    ASSERT(start % FRAME_SIZE == 0);
-    ASSERT(size % FRAME_SIZE == 0);
-    cnt = size / FRAME_SIZE;
-    z = (zone_t *) early_malloc(sizeof(zone_t));
-    if (z) {
-        link_initialize(&z->link);
-        spinlock_initialize(&z->lock, "zone_lock");
+    spinlock_initialize(&z->lock, "zone_lock");
-        z->base = start;
+    z->base = start;
-        z->base_index = start / FRAME_SIZE;
+    z->count = count;
-        z->flags = flags;
+    z->flags = flags;
-        z->free_count = cnt;
+    z->free_count = count;
-        z->busy_count = 0;
+    z->busy_count = 0;
-        z->frames = (frame_t *) early_malloc(cnt * sizeof(frame_t));
-        if (!z->frames) {
-            early_free(z);
-            return NULL;
-        }
-        for (i = 0; i<cnt; i++) {
-            frame_initialize(&z->frames[i], z);
-        }
-        /*
+    /*
-         * Create buddy system for the zone
+     * Compute order for buddy system, initialize
-         */
+     */
-        for (max_order = 0; cnt >> max_order; max_order++)
+    for (max_order = 0; count >> max_order; max_order++)
+        ;
+    z->buddy_system = (buddy_system_t *)&z[1];
+    buddy_system_create(z->buddy_system, max_order,
+                &zone_buddy_system_operations,
+                (void *) z);
+    /* Allocate frames _after_ the conframe */
+    /* Check sizes */
-        z->buddy_system = buddy_system_create(max_order, &zone_buddy_system_operations, (void *) z);
+    z->frames = (frame_t *)((void *)z->buddy_system+buddy_conf_size(max_order));
+    for (i = 0; i<count; i++) {
+        frame_initialize(&z->frames[i]);
+    }
-        /* Stuffing frames */
+    /* Stuffing frames */
-        for (i = 0; i<cnt; i++) {
+    for (i = 0; i < count; i++) {
-            z->frames[i].refcount = 0;
+        z->frames[i].refcount = 0;
-            buddy_system_free(z->buddy_system, &z->frames[i].buddy_link);
+        buddy_system_free(z->buddy_system, &z->frames[i].buddy_link);
+    }
-    }
     return z;
+}
-/** Attach frame zone
+/** Compute configuration data size for zone */
+__address zone_conf_size(pfn_t start, pfn_t count)
- *
+{
+    int size = sizeof(zone_t) + count*sizeof(frame_t);
+    int max_order;
+    for (max_order = 0; count >> max_order; max_order++)
+        ;
+    size += buddy_conf_size(max_order);
+    return size;
+}
- * Attach frame zone to zone list.
+/** Create and add zone to system
+ *
- * @param zone Zone to be attached.
+ * @param confframe Where configuration frame is supposed to be.
+ *                  Always check, that we will not disturb kernel pages
+ *                  the kernel and possibly init.
+ *                  If confframe is given _outside_ this zone, it is expected,
+ *                  that the area is already marked BUSY and big enough
+ *                  to contain zone_conf_size() amount of data
  */
-void zone_attach(zone_t *zone)
+void zone_create(pfn_t start, pfn_t count, pfn_t confframe, int flags)
+{
+    zone_t *z;
+    __address addr,endaddr;
+    pfn_t confcount;
-    ipl_t ipl;
+    int i;
+    /* Theoretically we could have here 0, practically make sure
+     * nobody tries to do that. If some platform requires, remove
+     * the assert
+     */
+    ASSERT(confframe);
+    /* If conframe is supposed to be inside our zone, then make sure
+     * it does not span kernel & init
+     */
+    confcount = SIZE2PFN(zone_conf_size(start,count));
+    if (confframe >= start && confframe < start+count) {
+        for (;confframe < start+count;confframe++) {
-    ipl = interrupts_disable();
+            addr = PFN2ADDR(confframe);
+            endaddr =  PFN2ADDR (confframe + confcount);
+            if (overlaps(addr, endaddr, KA2PA(config.base),
+                     KA2PA(config.base+config.kernel_size)))
+                continue;
-    spinlock_lock(&zone_head_lock);
+            if (config.init_addr)
+                if (overlaps(addr,endaddr,
+                         KA2PA(config.init_addr),
+                         KA2PA(config.init_addr+config.init_size)))
+                    continue;
+            break;
+        }
+        if (confframe >= start+count)
+            panic("Cannot find configuration data for zone.");
+    }
+    z = zone_construct(start, count, (zone_t *)PA2KA(PFN2ADDR(confframe)), flags);
-    list_append(&zone->link, &zone_head);
+    zones_add_zone(z);
-    spinlock_unlock(&zone_head_lock);
+    /* If confdata in zone, mark as unavailable */
+    if (confframe >= start && confframe < start+count)
+        for (i=confframe; i<confframe+confcount; i++) {
-    interrupts_restore(ipl);
+            zone_mark_unavailable(z, i - z->base);
+        }
+}
-/** Initialize frame structure
+/***************************************/
- *
- * Initialize frame structure.
+/* Frame functions */
- *
- * @param frame Frame structure to be initialized.
- * @param zone Host frame zone.
+/** Set parent of frame */
- */
-void frame_initialize(frame_t *frame, zone_t *zone)
+void frame_set_parent(pfn_t pfn, void *data, int hint)
+{
+    zone_t *zone = find_zone_and_lock(pfn, &hint);
-    frame->refcount = 1;
+    ASSERT(zone);
+    zone_get_frame(zone, pfn-zone->base)->parent = data;
-    frame->buddy_order = 0;
+    spinlock_unlock(&zone->lock);
+}
+void * frame_get_parent(pfn_t pfn, int hint)
+{
+    zone_t *zone = find_zone_and_lock(pfn, &hint);
+    void *res;
+    ASSERT(zone);
+    res = zone_get_frame(zone, pfn - zone->base)->parent;
+    spinlock_unlock(&zone->lock);
+    return res;
+}
-/** Buddy system find_buddy implementation
+/** Allocate power-of-two frames of physical memory.
+ *
+ * @param flags Flags for host zone selection and address processing.
- * @param b Buddy system.
+ * @param order Allocate exactly 2^order frames.
- * @param block Block for which buddy should be found
+ * @param pzone Preferred zone
+ *
- * @return Buddy for given block if found
+ * @return Allocated frame.
  */
-link_t * zone_buddy_find_buddy(buddy_system_t *b, link_t * block) {
+pfn_t frame_alloc_generic(__u8 order, int flags, int * status, int *pzone)
+{
+    ipl_t ipl;
-    frame_t * frame;
+    int freed;
+    pfn_t v;
-    zone_t * zone;
+    zone_t *zone;
-    index_t index;
-    bool is_left, is_right;
-    frame = list_get_instance(block, frame_t, buddy_link);
-    zone = (zone_t *) b->data;
-    ASSERT(IS_BUDDY_ORDER_OK(FRAME_INDEX_ABS(zone, frame), frame->buddy_order));
+loop:
+    ipl = interrupts_disable();
+    /*
+     * First, find suitable frame zone.
+     */
+    zone = find_free_zone_lock(order,pzone);
+    /* If no memory, reclaim some slab memory,
+       if it does not help, reclaim all */
+    if (!zone && !(flags & FRAME_NO_RECLAIM)) {
+        freed = slab_reclaim(0);
+        if (freed)
+            zone = find_free_zone_lock(order,pzone);
+        if (!zone) {
+            freed = slab_reclaim(SLAB_RECLAIM_ALL);
+            if (freed)
+                zone = find_free_zone_lock(order,pzone);
+        }
+    }
+    if (!zone) {
+        if (flags & FRAME_PANIC)
+            panic("Can't allocate frame.\n");
-    is_left = IS_BUDDY_LEFT_BLOCK_ABS(zone, frame);
+        /*
-    is_right = IS_BUDDY_RIGHT_BLOCK_ABS(zone, frame);
+         * TODO: Sleep until frames are available again.
+         */
-    ASSERT(is_left ^ is_right);
+        interrupts_restore(ipl);
-    if (is_left) {
+        if (flags & FRAME_ATOMIC) {
-        index = (FRAME_INDEX(zone, frame)) + (1 << frame->buddy_order);
+            ASSERT(status != NULL);
-    } else { // if (is_right)
+            if (status)
-        index = (FRAME_INDEX(zone, frame)) - (1 << frame->buddy_order);
+                *status = FRAME_NO_MEMORY;
+            return NULL;
+        }
-    if (FRAME_INDEX_VALID(zone, index)) {
-        if (    zone->frames[index].buddy_order == frame->buddy_order &&
-            zone->frames[index].refcount == 0) {
+        panic("Sleep not implemented.\n");
-            return &zone->frames[index].buddy_link;
-        }
+        goto loop;
+    }
+    v = zone_frame_alloc(zone,order,flags,status);
+    v += zone->base;
+    spinlock_unlock(&zone->lock);
+    interrupts_restore(ipl);
+    if (status)
+        *status = FRAME_OK;
-    return NULL;
+    return v;
+}
-/** Buddy system bisect implementation
+/** Free a frame.
+ *
- * @param b Buddy system.
+ * Find respective frame structrue for supplied addr.
- * @param block Block to bisect
+ * Decrement frame reference count.
+ * If it drops to zero, move the frame structure to free list.
+ *
- * @return right block
+ * @param frame Frame no to be freed.
  */
-link_t * zone_buddy_bisect(buddy_system_t *b, link_t * block) {
-    frame_t * frame_l, * frame_r;
+void frame_free(pfn_t pfn)
+{
-    frame_l = list_get_instance(block, frame_t, buddy_link);
+    ipl_t ipl;
-    frame_r = (frame_l + (1 << (frame_l->buddy_order - 1)));
+    zone_t *zone;
-    return &frame_r->buddy_link;
+    ipl = interrupts_disable();
-}
-/** Buddy system coalesce implementation
- *
+    /*
- * @param b Buddy system.
- * @param block_1 First block
- * @param block_2 First block's buddy
+     * First, find host frame zone for addr.
- *
- * @return Coalesced block (actually block that represents lower address)
- */
+     */
-link_t * zone_buddy_coalesce(buddy_system_t *b, link_t * block_1, link_t * block_2) {
+    zone = find_zone_and_lock(pfn,NULL);
-    frame_t * frame1, * frame2;
+    ASSERT(zone);
-    frame1 = list_get_instance(block_1, frame_t, buddy_link);
-    frame2 = list_get_instance(block_2, frame_t, buddy_link);
+    zone_frame_free(zone, pfn-zone->base);
-    return frame1 < frame2 ? block_1 : block_2;
+    spinlock_unlock(&zone->lock);
+    interrupts_restore(ipl);
+}
-/** Buddy system set_order implementation
- *
- * @param b Buddy system.
- * @param block Buddy system block
- * @param order Order to set
- */
-void zone_buddy_set_order(buddy_system_t *b, 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 b Buddy system.
+/** Mark given range unavailable in frame zones */
- * @param block Buddy system block
+void frame_mark_unavailable(pfn_t start, pfn_t count)
- *
+{
+    int i;
+    zone_t *zone;
- * @return Order of block
+    int prefzone = 0;
- */
+    for (i=0; i<count; i++) {
-__u8 zone_buddy_get_order(buddy_system_t *b, link_t * block) {
+        zone = find_zone_and_lock(start+i,&prefzone);
+        if (!zone) /* PFN not found */
-    frame_t * frame;
+            continue;
-    frame = list_get_instance(block, frame_t, buddy_link);
+        zone_mark_unavailable(zone, start+i-zone->base);
-    return frame->buddy_order;
+        spinlock_unlock(&zone->lock);
+    }
+}
-/** Buddy system mark_busy implementation
+/** Initialize physical memory management
- *
- * @param b Buddy system
- * @param block Buddy system block
+ *
+ * Initialize physical memory managemnt.
  */
-void zone_buddy_mark_busy(buddy_system_t *b, link_t * block) {
-    frame_t * frame;
+void frame_init(void)
+{
-    frame = list_get_instance(block, frame_t, buddy_link);
+    if (config.cpu_active == 1) {
-    frame->refcount = 1;
+        zones.count = 0;
+        spinlock_initialize(&zones.lock,"zones_glob_lock");
+    }
+    /* Tell the architecture to create some memory */
+    frame_arch_init();
+    if (config.cpu_active == 1) {
+        frame_mark_unavailable(ADDR2PFN(KA2PA(config.base)),
+                       SIZE2PFN(config.kernel_size));
+        if (config.init_size > 0)
+            frame_mark_unavailable(ADDR2PFN(KA2PA(config.init_addr)),
+                           SIZE2PFN(config.init_size));
+    }
+}
 /** Prints list of zones
+ *
  */
 void zone_print_list(void) {
     zone_t *zone = NULL;
-    link_t *cur;
+    int i;
     ipl_t ipl;
     ipl = interrupts_disable();
-    spinlock_lock(&zone_head_lock);
+    spinlock_lock(&zones.lock);
     printf("Base address\tFree Frames\tBusy Frames\n");
     printf("------------\t-----------\t-----------\n");
-    for (cur = zone_head.next; cur != &zone_head; cur = cur->next) {
+    for (i=0;i<zones.count;i++) {
-        zone = list_get_instance(cur, zone_t, link);
+        zone = zones.info[i];
         spinlock_lock(&zone->lock);
+        printf("%L\t%d\t\t%d\n",PFN2ADDR(zone->base),
-        printf("%L\t%d\t\t%d\n",zone->base, zone->free_count, zone->busy_count);
+               zone->free_count, zone->busy_count);
         spinlock_unlock(&zone->lock);
+    }
-    spinlock_unlock(&zone_head_lock);
+    spinlock_unlock(&zones.lock);
     interrupts_restore(ipl);
+}
 /** Prints zone details
+ *
  * @param base Zone base address
  */
-void zone_print_one(__address base) {
+void zone_print_one(int znum) {
-    zone_t *zone = NULL, *z ;
+    zone_t *zone = NULL;
-    link_t *cur;
     ipl_t ipl;
     ipl = interrupts_disable();
-    spinlock_lock(&zone_head_lock);
+    spinlock_lock(&zones.lock);
-    for (cur = zone_head.next; cur != &zone_head; cur = cur->next) {
+    if (znum >= zones.count || znum < 0) {
-        z = list_get_instance(cur, zone_t, link);
+        printf("Zone number out of bounds.\n");
-        if (base == z->base) {
-            zone = z;
-            break;
-        }
-    }
-    if (!zone) {
-        spinlock_unlock(&zone_head_lock);
+        spinlock_unlock(&zones.lock);
         interrupts_restore(ipl);
-        printf("No zone with address %X\n", base);
         return;
+    }
+    zone = zones.info[znum];
     spinlock_lock(&zone->lock);
     printf("Memory zone information\n\n");
-    printf("Zone base address: %P\n", zone->base);
+    printf("Zone base address: %P\n", PFN2ADDR(zone->base));
-    printf("Zone size: %d frames (%dK)\n", zone->free_count + zone->busy_count, ((zone->free_count + zone->busy_count) * FRAME_SIZE) >> 10);
+    printf("Zone size: %d frames (%dK)\n", zone->count, ((zone->count) * FRAME_SIZE) >> 10);
     printf("Allocated space: %d frames (%dK)\n", zone->busy_count, (zone->busy_count * FRAME_SIZE) >> 10);
     printf("Available space: %d (%dK)\n", zone->free_count, (zone->free_count * FRAME_SIZE) >> 10);
     printf("\nBuddy allocator structures:\n\n");
     buddy_system_structure_print(zone->buddy_system, FRAME_SIZE);
     spinlock_unlock(&zone->lock);
-    spinlock_unlock(&zone_head_lock);
+    spinlock_unlock(&zones.lock);
     interrupts_restore(ipl);
+}

Subversion Repositories HelenOS-historic

(root)/kernel/trunk/generic/src/mm/frame.c – Rev 788 → 814