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


/*
 * Copyright (C) 2001-2005 Jakub Jermar
 * Copyright (C) 2005 Sergey Bondari
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 *
 * - Redistributions of source code must retain the above copyright
 *   notice, this list of conditions and the following disclaimer.
 * - Redistributions in binary form must reproduce the above copyright
 *   notice, this list of conditions and the following disclaimer in the
 *   documentation and/or other materials provided with the distribution.
 * - The name of the author may not be used to endorse or promote products
 *   derived from this software without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
 * 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/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_DECLARE(lock); /**< this lock protects everything below */
    pfn_t base; /**< frame_no of the first frame in the frames array */
    count_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;
 
/*
 * The zoneinfo.lock must be locked when accessing zoneinfo structure.
 * Some of the attributes in zone_t structures are 'read-only'
 */
 
struct {
    SPINLOCK_DECLARE(lock);
    int count;
    zone_t *info[ZONES_MAX];
}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 index_t make_frame_index(zone_t *zone, frame_t *frame)
{
    return frame - zone->frames;
}
 
/** Initialize frame structure
 *
 * Initialize frame structure.
 *
 * @param frame Frame structure to be initialized.
 */
static void frame_initialize(frame_t *frame)
{
    frame->refcount = 1;
    frame->buddy_order = 0;
}
 
/*************************************/
/* Zoneinfo functions */
 
/**
 * Insert-sort zone into zones list
 */
static void zones_add_zone(zone_t *zone)
{
    int i;
 
    spinlock_lock(&zones.lock);
    /* 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);
}
 
/**
 * 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 interrupts disable
 */
static zone_t * find_zone_and_lock(pfn_t frame, int *pzone)
{
    int i;
    int hint = pzone ? *pzone : 0;
    zone_t *z;
   
    spinlock_lock(&zones.lock);
 
    if (hint >= zones.count || hint < 0)
        hint = 0;
   
    i = hint;
    do {
        z = zones.info[i];
        spinlock_lock(&z->lock);
        if (z->base <= frame && z->base + z->count > frame) {
            spinlock_unlock(&zones.lock); /* Unlock the global lock */
            if (pzone)
                *pzone = i;
            return z;
        }
        spinlock_unlock(&z->lock);
 
        i++;
        if (i >= zones.count)
            i = 0;
    } while(i != hint);
 
    spinlock_unlock(&zones.lock);
    return NULL;
}
 
/**
 * Find AND LOCK zone that can allocate order frames
 *
 * Assume interrupts are disabled!!
 *
 * @param pzone Pointer to preferred zone or NULL, on return contains zone number
 */
static zone_t * find_free_zone_lock(__u8 order, int *pzone)
{
    int i;
    zone_t *z;
    int hint = pzone ? *pzone : 0;
   
    spinlock_lock(&zones.lock);
    if (hint >= zones.count)
        hint = 0;
    i = hint;
    do {
        z = zones.info[i];
       
        spinlock_lock(&z->lock);
 
        /* Check if the zone has 2^order frames area available  */
        if (buddy_system_can_alloc(z->buddy_system, order)) {
            spinlock_unlock(&zones.lock);
            if (pzone)
                *pzone = i;
            return z;
        }
        spinlock_unlock(&z->lock);
        if (++i >= zones.count)
            i = 0;
    } while(i != hint);
    spinlock_unlock(&zones.lock);
    return NULL;
}
 
/********************************************/
/* 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!!
 */
static link_t *zone_buddy_find_block(buddy_system_t *b, link_t *child,
                     __u8 order)
{
    frame_t * frame;
    zone_t * zone;
    index_t index;
   
    frame = list_get_instance(child, frame_t, buddy_link);
    zone = (zone_t *) b->data;
 
    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 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;
    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));
   
    is_left = IS_BUDDY_LEFT_BLOCK_ABS(zone, frame);
    is_right = IS_BUDDY_RIGHT_BLOCK_ABS(zone, frame);
 
    ASSERT(is_left ^ is_right);
    if (is_left) {
        index = (frame_index(zone, frame)) + (1 << frame->buddy_order);
    } else { // if (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 b Buddy system.
 * @param block Block to bisect
 *
 * @return right block
 */
static link_t * zone_buddy_bisect(buddy_system_t *b, link_t * block) {
    frame_t * frame_l, * frame_r;
 
    frame_l = list_get_instance(block, frame_t, buddy_link);
    frame_r = (frame_l + (1 << (frame_l->buddy_order - 1)));
   
    return &frame_r->buddy_link;
}
 
/** Buddy system coalesce implementation
 *
 * @param b Buddy system.
 * @param block_1 First block
 * @param block_2 First block's buddy
 *
 * @return Coalesced block (actually block that represents lower address)
 */
static link_t * zone_buddy_coalesce(buddy_system_t *b, link_t * block_1,
                    link_t * block_2) {
    frame_t *frame1, *frame2;
   
    frame1 = list_get_instance(block_1, frame_t, buddy_link);
    frame2 = list_get_instance(block_2, frame_t, buddy_link);
   
    return frame1 < frame2 ? block_1 : block_2;
}
 
/** Buddy system set_order implementation
 *
 * @param b Buddy system.
 * @param block Buddy system block
 * @param order Order to set
 */
static 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.
 * @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;
    frame = list_get_instance(block, frame_t, buddy_link);
    frame->refcount = 1;
}
 
/** Buddy system mark_available implementation
 *
 * @param b Buddy system
 * @param block Buddy system block
 *
 */
static void zone_buddy_mark_available(buddy_system_t *b, link_t * block) {
    frame_t * frame;
    frame = list_get_instance(block, frame_t, buddy_link);
    frame->refcount = 0;
}
 
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 */
 
/** Allocate frame in particular zone
 *
 * Assume zone is locked
 *
 * @return Frame index in zone
 */
static pfn_t zone_frame_alloc(zone_t *zone,__u8 order, int flags, int *status)
{
    pfn_t v;
    link_t *tmp;
    frame_t *frame;
 
    /* Allocate frames from zone buddy system */
    tmp = buddy_system_alloc(zone->buddy_system, order);
   
    ASSERT(tmp);
   
    /* Update zone information. */
    zone->free_count -= (1 << order);
    zone->busy_count += (1 << order);
 
    /* Frame will be actually a first frame of the block. */
    frame = list_get_instance(tmp, frame_t, buddy_link);
   
    /* get frame address */
    v = make_frame_index(zone, frame);
    return v;
}
 
/** Free frame from zone
 *
 * Assume zone is locked
 */
static void zone_frame_free(zone_t *zone, index_t frame_idx)
{
    frame_t *frame;
    __u8 order;
 
    frame = &zone->frames[frame_idx];
   
    /* remember frame order */
    order = frame->buddy_order;
 
    ASSERT(frame->refcount);
 
    if (!--frame->refcount) {
        buddy_system_free(zone->buddy_system, &frame->buddy_link);
    }
 
    /* Update zone information. */
    zone->free_count += (1 << order);
    zone->busy_count -= (1 << order);
}
 
/** Return frame from zone */
static frame_t * zone_get_frame(zone_t *zone, index_t frame_idx)
{
    ASSERT(frame_idx < zone->count);
    return &zone->frames[frame_idx];
}
 
/** Mark frame in zone unavailable to allocation */
static void zone_mark_unavailable(zone_t *zone, index_t frame_idx)
{
    frame_t *frame;
    link_t *link;
 
    frame = zone_get_frame(zone, frame_idx);
    link = buddy_system_alloc_block(zone->buddy_system,
                    &frame->buddy_link);
    ASSERT(link);
    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.
 */
static zone_t * zone_construct(pfn_t start, count_t count,
                   zone_t *z, int flags)
{
    int i;
    __u8 max_order;
 
    spinlock_initialize(&z->lock, "zone_lock");
    z->base = start;
    z->count = count;
    z->flags = flags;
    z->free_count = count;
    z->busy_count = 0;
 
    /*
     * Compute order for buddy system, initialize
     */
    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->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 */
    for (i = 0; i < count; i++) {
        z->frames[i].refcount = 0;
        buddy_system_free(z->buddy_system, &z->frames[i].buddy_link);
    }
    return z;
}
 
 
/** Compute configuration data size for zone */
__address zone_conf_size(pfn_t start, count_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;
}
 
/** Create and add zone to system
 *
 * @param confframe Where configuration frame is supposed to be.
 *                  Always check, that we will not disturb 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_create(pfn_t start, count_t count, pfn_t confframe, int flags)
{
    zone_t *z;
    __address addr,endaddr;
    count_t confcount;
    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 = SIZE2FRAMES(zone_conf_size(start,count));
    if (confframe >= start && confframe < start+count) {
        for (;confframe < start+count;confframe++) {
            addr = PFN2ADDR(confframe);
            endaddr =  PFN2ADDR (confframe + confcount);
            if (overlaps(addr, endaddr, KA2PA(config.base),
                     KA2PA(config.base+config.kernel_size)))
                continue;
            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);
    zones_add_zone(z);
   
    /* If confdata in zone, mark as unavailable */
    if (confframe >= start && confframe < start+count)
        for (i=confframe; i<confframe+confcount; i++) {
            zone_mark_unavailable(z, i - z->base);
        }
}
 
/***************************************/
/* Frame functions */
 
/** Set parent of frame */
void frame_set_parent(pfn_t pfn, void *data, int hint)
{
    zone_t *zone = find_zone_and_lock(pfn, &hint);
 
    ASSERT(zone);
 
    zone_get_frame(zone, pfn-zone->base)->parent = data;
    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;
}
 
/** Allocate power-of-two frames of physical memory.
 *
 * @param flags Flags for host zone selection and address processing.
 * @param order Allocate exactly 2^order frames.
 * @param pzone Preferred zone
 *
 * @return Allocated frame.
 */
pfn_t frame_alloc_generic(__u8 order, int flags, int * status, int *pzone)
{
    ipl_t ipl;
    int freed;
    pfn_t v;
    zone_t *zone;
   
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");
       
        /*
         * TODO: Sleep until frames are available again.
         */
        interrupts_restore(ipl);
 
        if (flags & FRAME_ATOMIC) {
            ASSERT(status != NULL);
            if (status)
                *status = FRAME_NO_MEMORY;
            return NULL;
        }
       
        panic("Sleep not implemented.\n");
        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 v;
}
 
/** Free a frame.
 *
 * Find respective frame structrue for supplied addr.
 * Decrement frame reference count.
 * If it drops to zero, move the frame structure to free list.
 *
 * @param frame Frame no to be freed.
 */
void frame_free(pfn_t pfn)
{
    ipl_t ipl;
    zone_t *zone;
 
    ipl = interrupts_disable();
   
    /*
     * First, find host frame zone for addr.
     */
    zone = find_zone_and_lock(pfn,NULL);
    ASSERT(zone);
   
    zone_frame_free(zone, pfn-zone->base);
   
    spinlock_unlock(&zone->lock);
    interrupts_restore(ipl);
}
 
 
 
/** Mark given range unavailable in frame zones */
void frame_mark_unavailable(pfn_t start, count_t count)
{
    int i;
    zone_t *zone;
    int prefzone = 0;
 
    for (i=0; i<count; i++) {
        zone = find_zone_and_lock(start+i,&prefzone);
        if (!zone) /* PFN not found */
            continue;
        zone_mark_unavailable(zone, start+i-zone->base);
 
        spinlock_unlock(&zone->lock);
    }
}
 
/** Initialize physical memory management
 *
 * Initialize physical memory managemnt.
 */
void frame_init(void)
{
    if (config.cpu_active == 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)),
                       SIZE2FRAMES(config.kernel_size));
        if (config.init_size > 0)
            frame_mark_unavailable(ADDR2PFN(KA2PA(config.init_addr)),
                           SIZE2FRAMES(config.init_size));
    }
}
 
 
 
/** Prints list of zones
 *
 */
void zone_print_list(void) {
    zone_t *zone = NULL;
    int i;
    ipl_t ipl;
 
    ipl = interrupts_disable();
    spinlock_lock(&zones.lock);
    printf("Base address\tFree Frames\tBusy Frames\n");
    printf("------------\t-----------\t-----------\n");
    for (i=0;i<zones.count;i++) {
        zone = zones.info[i];
        spinlock_lock(&zone->lock);
        printf("%L\t%d\t\t%d\n",PFN2ADDR(zone->base),
               zone->free_count, zone->busy_count);
        spinlock_unlock(&zone->lock);
    }
    spinlock_unlock(&zones.lock);
    interrupts_restore(ipl);
}
 
/** Prints zone details
 *
 * @param base Zone base address
 */
void zone_print_one(int znum) {
    zone_t *zone = NULL;
    ipl_t ipl;
 
    ipl = interrupts_disable();
    spinlock_lock(&zones.lock);
   
    if (znum >= zones.count || znum < 0) {
        printf("Zone number out of bounds.\n");
        spinlock_unlock(&zones.lock);
        interrupts_restore(ipl);
        return;
    }
   
    zone = zones.info[znum];
   
    spinlock_lock(&zone->lock);
    printf("Memory zone information\n\n");
    printf("Zone base address: %P\n", PFN2ADDR(zone->base));
    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(&zones.lock);
    interrupts_restore(ipl);
}
 
 

Rev 814	Rev 820
1	/*	1	/*
2	* Copyright (C) 2001-2005 Jakub Jermar	2	* Copyright (C) 2001-2005 Jakub Jermar
3	* Copyright (C) 2005 Sergey Bondari	3	* Copyright (C) 2005 Sergey Bondari
4	* All rights reserved.	4	* All rights reserved.
5	*	5	*
6	* Redistribution and use in source and binary forms, with or without	6	* Redistribution and use in source and binary forms, with or without
7	* modification, are permitted provided that the following conditions	7	* modification, are permitted provided that the following conditions
8	* are met:	8	* are met:
9	*	9	*
10	* - Redistributions of source code must retain the above copyright	10	* - Redistributions of source code must retain the above copyright
11	* notice, this list of conditions and the following disclaimer.	11	* notice, this list of conditions and the following disclaimer.
12	* - Redistributions in binary form must reproduce the above copyright	12	* - Redistributions in binary form must reproduce the above copyright
13	* notice, this list of conditions and the following disclaimer in the	13	* notice, this list of conditions and the following disclaimer in the
14	* documentation and/or other materials provided with the distribution.	14	* documentation and/or other materials provided with the distribution.
15	* - The name of the author may not be used to endorse or promote products	15	* - The name of the author may not be used to endorse or promote products
16	* derived from this software without specific prior written permission.	16	* derived from this software without specific prior written permission.
17	*	17	*
18	* THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR	18	* THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
19	* IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES	19	* IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
20	* OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.	20	* OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
21	* IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,	21	* IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
22	* INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT	22	* INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
23	* NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,	23	* NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
24	* DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY	24	* DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
25	* THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT	25	* THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
26	* (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF	26	* (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
27	* THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.	27	* THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
28	*/	28	*/
29		29
30	/*	30	/*
31	* Locking order	31	* Locking order
32	*	32	*
33	* In order to access particular zone, the process must first lock	33	* In order to access particular zone, the process must first lock
34	* the zones.lock, then lock the zone and then unlock the zones.lock.	34	* the zones.lock, then lock the zone and then unlock the zones.lock.
35	* This insures, that we can fiddle with the zones in runtime without	35	* This insures, that we can fiddle with the zones in runtime without
36	* affecting the processes.	36	* affecting the processes.
37	*	37	*
38	*/	38	*/
39		39
40	#include <typedefs.h>	40	#include <typedefs.h>
41	#include <arch/types.h>	41	#include <arch/types.h>
42	#include <mm/frame.h>	42	#include <mm/frame.h>
43	#include <mm/as.h>	43	#include <mm/as.h>
44	#include <panic.h>	44	#include <panic.h>
45	#include <debug.h>	45	#include <debug.h>
46	#include <adt/list.h>	46	#include <adt/list.h>
47	#include <synch/spinlock.h>	47	#include <synch/spinlock.h>
48	#include <arch/asm.h>	48	#include <arch/asm.h>
49	#include <arch.h>	49	#include <arch.h>
50	#include <print.h>	50	#include <print.h>
51	#include <align.h>	51	#include <align.h>
52	#include <mm/slab.h>	52	#include <mm/slab.h>
53		53
54	typedef struct {	54	typedef struct {
55	count_t refcount; /*< tracking of shared frames /	55	count_t refcount; /*< tracking of shared frames /
56	__u8 buddy_order; /*< buddy system block order /	56	__u8 buddy_order; /*< buddy system block order /
57	link_t buddy_link; /*< link to the next free block inside one order /	57	link_t buddy_link; /*< link to the next free block inside one order /
58	void parent; /< If allocated by slab, this points there /	58	void parent; /< If allocated by slab, this points there /
59	}frame_t;	59	}frame_t;
60		60
61	typedef struct {	61	typedef struct {
62	SPINLOCK_DECLARE(lock); /*< this lock protects everything below /	62	SPINLOCK_DECLARE(lock); /*< this lock protects everything below /
63	pfn_t base; /*< frame_no of the first frame in the frames array /	63	pfn_t base; /*< frame_no of the first frame in the frames array /
64	pfn_t count; /*< Size of zone /	64	count_t count; /*< Size of zone /
65		65
66	frame_t frames; /< array of frame_t structures in this zone /	66	frame_t frames; /< array of frame_t structures in this zone /
67	count_t free_count; /*< number of free frame_t structures /	67	count_t free_count; /*< number of free frame_t structures /
68	count_t busy_count; /*< number of busy frame_t structures /	68	count_t busy_count; /*< number of busy frame_t structures /
69		69
70	buddy_system_t * buddy_system; /*< buddy system for the zone /	70	buddy_system_t * buddy_system; /*< buddy system for the zone /
71	int flags;	71	int flags;
72	}zone_t;	72	}zone_t;
73		73
74	/*	74	/*
75	* The zoneinfo.lock must be locked when accessing zoneinfo structure.	75	* The zoneinfo.lock must be locked when accessing zoneinfo structure.
76	* Some of the attributes in zone_t structures are 'read-only'	76	* Some of the attributes in zone_t structures are 'read-only'
77	*/	77	*/
78		78
79	struct {	79	struct {
80	SPINLOCK_DECLARE(lock);	80	SPINLOCK_DECLARE(lock);
81	int count;	81	int count;
82	zone_t *info[ZONES_MAX];	82	zone_t *info[ZONES_MAX];
83	}zones;	83	}zones;
84		84
85		85
86	/*********************************/	86	/*********************************/
87	/* Helper functions */	87	/* Helper functions */
88	static inline index_t frame_index(zone_t zone, frame_t frame)	88	static inline index_t frame_index(zone_t zone, frame_t frame)
89	{	89	{
90	return (index_t)(frame - zone->frames);	90	return (index_t)(frame - zone->frames);
91	}	91	}
92	static inline index_t frame_index_abs(zone_t zone, frame_t frame)	92	static inline index_t frame_index_abs(zone_t zone, frame_t frame)
93	{	93	{
94	return (index_t)(frame - zone->frames) + zone->base;	94	return (index_t)(frame - zone->frames) + zone->base;
95	}	95	}
96	static inline int frame_index_valid(zone_t *zone, index_t index)	96	static inline int frame_index_valid(zone_t *zone, index_t index)
97	{	97	{
98	return index >= 0 && index < zone->count;	98	return index >= 0 && index < zone->count;
99	}	99	}
100		100
101	/** Compute pfn_t from frame_t pointer & zone pointer */	101	/** Compute pfn_t from frame_t pointer & zone pointer */
102	static pfn_t make_frame_index(zone_t zone, frame_t frame)	102	static index_t make_frame_index(zone_t zone, frame_t frame)
103	{	103	{
104	return frame - zone->frames;	104	return frame - zone->frames;
105	}	105	}
106		106
107	/** Initialize frame structure	107	/** Initialize frame structure
108	*	108	*
109	* Initialize frame structure.	109	* Initialize frame structure.
110	*	110	*
111	* @param frame Frame structure to be initialized.	111	* @param frame Frame structure to be initialized.
112	*/	112	*/
113	static void frame_initialize(frame_t *frame)	113	static void frame_initialize(frame_t *frame)
114	{	114	{
115	frame->refcount = 1;	115	frame->refcount = 1;
116	frame->buddy_order = 0;	116	frame->buddy_order = 0;
117	}	117	}
118		118
119	/*************************************/	119	/*************************************/
120	/* Zoneinfo functions */	120	/* Zoneinfo functions */
121		121
122	/**	122	/**
123	* Insert-sort zone into zones list	123	* Insert-sort zone into zones list
124	*/	124	*/
125	static void zones_add_zone(zone_t *zone)	125	static void zones_add_zone(zone_t *zone)
126	{	126	{
127	int i;	127	int i;
128		128
129	spinlock_lock(&zones.lock);	129	spinlock_lock(&zones.lock);
130	/* Try to merge */	130	/* Try to merge */
131	if (zone->flags & ZONE_JOIN) {	131	if (zone->flags & ZONE_JOIN) {
132	for (i=0; i < zones.count; i++) {	132	for (i=0; i < zones.count; i++) {
133	spinlock_lock(&zones.info[i]->lock);	133	spinlock_lock(&zones.info[i]->lock);
134		134
135	/* Join forward, join backward */	135	/* Join forward, join backward */
136	panic("Not implemented");	136	panic("Not implemented");
137		137
138	spinlock_unlock(&zones.info[i]->lock);	138	spinlock_unlock(&zones.info[i]->lock);
139	}	139	}
140	spinlock_unlock(&zones.lock);	140	spinlock_unlock(&zones.lock);
141	} else {	141	} else {
142	if (zones.count+1 == ZONES_MAX)	142	if (zones.count+1 == ZONES_MAX)
143	panic("Maximum zone(%d) count exceeded.", ZONES_MAX);	143	panic("Maximum zone(%d) count exceeded.", ZONES_MAX);
144	zones.info[zones.count++] = zone;	144	zones.info[zones.count++] = zone;
145	}	145	}
146	spinlock_unlock(&zones.lock);	146	spinlock_unlock(&zones.lock);
147	}	147	}
148		148
149	/**	149	/**
150	* Try to find a zone where can we find the frame	150	* Try to find a zone where can we find the frame
151	*	151	*
152	* @param hint Start searching in zone 'hint'	152	* @param hint Start searching in zone 'hint'
153	* @param lock Lock zone if true	153	* @param lock Lock zone if true
154	*	154	*
155	* Assume interrupts disable	155	* Assume interrupts disable
156	*/	156	*/
157	static zone_t * find_zone_and_lock(pfn_t frame, int *pzone)	157	static zone_t * find_zone_and_lock(pfn_t frame, int *pzone)
158	{	158	{
159	int i;	159	int i;
160	int hint = pzone ? *pzone : 0;	160	int hint = pzone ? *pzone : 0;
161	zone_t *z;	161	zone_t *z;
162		162
163	spinlock_lock(&zones.lock);	163	spinlock_lock(&zones.lock);
164		164
165	if (hint >= zones.count \|\| hint < 0)	165	if (hint >= zones.count \|\| hint < 0)
166	hint = 0;	166	hint = 0;
167		167
168	i = hint;	168	i = hint;
169	do {	169	do {
170	z = zones.info[i];	170	z = zones.info[i];
171	spinlock_lock(&z->lock);	171	spinlock_lock(&z->lock);
172	if (z->base <= frame && z->base + z->count > frame) {	172	if (z->base <= frame && z->base + z->count > frame) {
173	spinlock_unlock(&zones.lock); /* Unlock the global lock */	173	spinlock_unlock(&zones.lock); /* Unlock the global lock */
174	if (pzone)	174	if (pzone)
175	*pzone = i;	175	*pzone = i;
176	return z;	176	return z;
177	}	177	}
178	spinlock_unlock(&z->lock);	178	spinlock_unlock(&z->lock);
179		179
180	i++;	180	i++;
181	if (i >= zones.count)	181	if (i >= zones.count)
182	i = 0;	182	i = 0;
183	} while(i != hint);	183	} while(i != hint);
184		184
185	spinlock_unlock(&zones.lock);	185	spinlock_unlock(&zones.lock);
186	return NULL;	186	return NULL;
187	}	187	}
188		188
189	/**	189	/**
190	* Find AND LOCK zone that can allocate order frames	190	* Find AND LOCK zone that can allocate order frames
191	*	191	*
192	* Assume interrupts are disabled!!	192	* Assume interrupts are disabled!!
193	*	193	*
194	* @param pzone Pointer to preferred zone or NULL, on return contains zone number	194	* @param pzone Pointer to preferred zone or NULL, on return contains zone number
195	*/	195	*/
196	static zone_t * find_free_zone_lock(__u8 order, int *pzone)	196	static zone_t * find_free_zone_lock(__u8 order, int *pzone)
197	{	197	{
198	int i;	198	int i;
199	zone_t *z;	199	zone_t *z;
200	int hint = pzone ? *pzone : 0;	200	int hint = pzone ? *pzone : 0;
201		201
202	spinlock_lock(&zones.lock);	202	spinlock_lock(&zones.lock);
203	if (hint >= zones.count)	203	if (hint >= zones.count)
204	hint = 0;	204	hint = 0;
205	i = hint;	205	i = hint;
206	do {	206	do {
207	z = zones.info[i];	207	z = zones.info[i];
208		208
209	spinlock_lock(&z->lock);	209	spinlock_lock(&z->lock);
210		210
211	/* Check if the zone has 2^order frames area available */	211	/* Check if the zone has 2^order frames area available */
212	if (buddy_system_can_alloc(z->buddy_system, order)) {	212	if (buddy_system_can_alloc(z->buddy_system, order)) {
213	spinlock_unlock(&zones.lock);	213	spinlock_unlock(&zones.lock);
214	if (pzone)	214	if (pzone)
215	*pzone = i;	215	*pzone = i;
216	return z;	216	return z;
217	}	217	}
218	spinlock_unlock(&z->lock);	218	spinlock_unlock(&z->lock);
219	if (++i >= zones.count)	219	if (++i >= zones.count)
220	i = 0;	220	i = 0;
221	} while(i != hint);	221	} while(i != hint);
222	spinlock_unlock(&zones.lock);	222	spinlock_unlock(&zones.lock);
223	return NULL;	223	return NULL;
224	}	224	}
225		225
226	/********************************************/	226	/********************************************/
227	/* Buddy system functions */	227	/* Buddy system functions */
228		228
229	/** Buddy system find_block implementation	229	/** Buddy system find_block implementation
230	*	230	*
231	* Find block that is parent of current list.	231	* Find block that is parent of current list.
232	* That means go to lower addresses, until such block is found	232	* That means go to lower addresses, until such block is found
233	*	233	*
234	* @param order - Order of parent must be different then this parameter!!	234	* @param order - Order of parent must be different then this parameter!!
235	*/	235	*/
236	static link_t zone_buddy_find_block(buddy_system_t b, link_t *child,	236	static link_t zone_buddy_find_block(buddy_system_t b, link_t *child,
237	__u8 order)	237	__u8 order)
238	{	238	{
239	frame_t * frame;	239	frame_t * frame;
240	zone_t * zone;	240	zone_t * zone;
241	index_t index;	241	index_t index;
242		242
243	frame = list_get_instance(child, frame_t, buddy_link);	243	frame = list_get_instance(child, frame_t, buddy_link);
244	zone = (zone_t *) b->data;	244	zone = (zone_t *) b->data;
245		245
246	index = frame_index(zone, frame);	246	index = frame_index(zone, frame);
247	do {	247	do {
248	if (zone->frames[index].buddy_order != order) {	248	if (zone->frames[index].buddy_order != order) {
249	return &zone->frames[index].buddy_link;	249	return &zone->frames[index].buddy_link;
250	}	250	}
251	} while(index-- > 0);	251	} while(index-- > 0);
252	return NULL;	252	return NULL;
253	}	253	}
254		254
255		255
256		256
257	/** Buddy system find_buddy implementation	257	/** Buddy system find_buddy implementation
258	*	258	*
259	* @param b Buddy system.	259	* @param b Buddy system.
260	* @param block Block for which buddy should be found	260	* @param block Block for which buddy should be found
261	*	261	*
262	* @return Buddy for given block if found	262	* @return Buddy for given block if found
263	*/	263	*/
264	static link_t * zone_buddy_find_buddy(buddy_system_t b, link_t block)	264	static link_t * zone_buddy_find_buddy(buddy_system_t b, link_t block)
265	{	265	{
266	frame_t * frame;	266	frame_t * frame;
267	zone_t * zone;	267	zone_t * zone;
268	index_t index;	268	index_t index;
269	bool is_left, is_right;	269	bool is_left, is_right;
270		270
271	frame = list_get_instance(block, frame_t, buddy_link);	271	frame = list_get_instance(block, frame_t, buddy_link);
272	zone = (zone_t *) b->data;	272	zone = (zone_t *) b->data;
273	ASSERT(IS_BUDDY_ORDER_OK(frame_index_abs(zone, frame), frame->buddy_order));	273	ASSERT(IS_BUDDY_ORDER_OK(frame_index_abs(zone, frame), frame->buddy_order));
274		274
275	is_left = IS_BUDDY_LEFT_BLOCK_ABS(zone, frame);	275	is_left = IS_BUDDY_LEFT_BLOCK_ABS(zone, frame);
276	is_right = IS_BUDDY_RIGHT_BLOCK_ABS(zone, frame);	276	is_right = IS_BUDDY_RIGHT_BLOCK_ABS(zone, frame);
277		277
278	ASSERT(is_left ^ is_right);	278	ASSERT(is_left ^ is_right);
279	if (is_left) {	279	if (is_left) {
280	index = (frame_index(zone, frame)) + (1 << frame->buddy_order);	280	index = (frame_index(zone, frame)) + (1 << frame->buddy_order);
281	} else { // if (is_right)	281	} else { // if (is_right)
282	index = (frame_index(zone, frame)) - (1 << frame->buddy_order);	282	index = (frame_index(zone, frame)) - (1 << frame->buddy_order);
283	}	283	}
284		284
285		285
286	if (frame_index_valid(zone, index)) {	286	if (frame_index_valid(zone, index)) {
287	if (zone->frames[index].buddy_order == frame->buddy_order &&	287	if (zone->frames[index].buddy_order == frame->buddy_order &&
288	zone->frames[index].refcount == 0) {	288	zone->frames[index].refcount == 0) {
289	return &zone->frames[index].buddy_link;	289	return &zone->frames[index].buddy_link;
290	}	290	}
291	}	291	}
292		292
293	return NULL;	293	return NULL;
294	}	294	}
295		295
296	/** Buddy system bisect implementation	296	/** Buddy system bisect implementation
297	*	297	*
298	* @param b Buddy system.	298	* @param b Buddy system.
299	* @param block Block to bisect	299	* @param block Block to bisect
300	*	300	*
301	* @return right block	301	* @return right block
302	*/	302	*/
303	static link_t * zone_buddy_bisect(buddy_system_t b, link_t block) {	303	static link_t * zone_buddy_bisect(buddy_system_t b, link_t block) {
304	frame_t * frame_l, * frame_r;	304	frame_t * frame_l, * frame_r;
305		305
306	frame_l = list_get_instance(block, frame_t, buddy_link);	306	frame_l = list_get_instance(block, frame_t, buddy_link);
307	frame_r = (frame_l + (1 << (frame_l->buddy_order - 1)));	307	frame_r = (frame_l + (1 << (frame_l->buddy_order - 1)));
308		308
309	return &frame_r->buddy_link;	309	return &frame_r->buddy_link;
310	}	310	}
311		311
312	/** Buddy system coalesce implementation	312	/** Buddy system coalesce implementation
313	*	313	*
314	* @param b Buddy system.	314	* @param b Buddy system.
315	* @param block_1 First block	315	* @param block_1 First block
316	* @param block_2 First block's buddy	316	* @param block_2 First block's buddy
317	*	317	*
318	* @return Coalesced block (actually block that represents lower address)	318	* @return Coalesced block (actually block that represents lower address)
319	*/	319	*/
320	static link_t * zone_buddy_coalesce(buddy_system_t b, link_t block_1,	320	static link_t * zone_buddy_coalesce(buddy_system_t b, link_t block_1,
321	link_t * block_2) {	321	link_t * block_2) {
322	frame_t frame1, frame2;	322	frame_t frame1, frame2;
323		323
324	frame1 = list_get_instance(block_1, frame_t, buddy_link);	324	frame1 = list_get_instance(block_1, frame_t, buddy_link);
325	frame2 = list_get_instance(block_2, frame_t, buddy_link);	325	frame2 = list_get_instance(block_2, frame_t, buddy_link);
326		326
327	return frame1 < frame2 ? block_1 : block_2;	327	return frame1 < frame2 ? block_1 : block_2;
328	}	328	}
329		329
330	/** Buddy system set_order implementation	330	/** Buddy system set_order implementation
331	*	331	*
332	* @param b Buddy system.	332	* @param b Buddy system.
333	* @param block Buddy system block	333	* @param block Buddy system block
334	* @param order Order to set	334	* @param order Order to set
335	*/	335	*/
336	static void zone_buddy_set_order(buddy_system_t b, link_t block, __u8 order) {	336	static void zone_buddy_set_order(buddy_system_t b, link_t block, __u8 order) {
337	frame_t * frame;	337	frame_t * frame;
338	frame = list_get_instance(block, frame_t, buddy_link);	338	frame = list_get_instance(block, frame_t, buddy_link);
339	frame->buddy_order = order;	339	frame->buddy_order = order;
340	}	340	}
341		341
342	/** Buddy system get_order implementation	342	/** Buddy system get_order implementation
343	*	343	*
344	* @param b Buddy system.	344	* @param b Buddy system.
345	* @param block Buddy system block	345	* @param block Buddy system block
346	*	346	*
347	* @return Order of block	347	* @return Order of block
348	*/	348	*/
349	static __u8 zone_buddy_get_order(buddy_system_t b, link_t block) {	349	static __u8 zone_buddy_get_order(buddy_system_t b, link_t block) {
350	frame_t * frame;	350	frame_t * frame;
351	frame = list_get_instance(block, frame_t, buddy_link);	351	frame = list_get_instance(block, frame_t, buddy_link);
352	return frame->buddy_order;	352	return frame->buddy_order;
353	}	353	}
354		354
355	/** Buddy system mark_busy implementation	355	/** Buddy system mark_busy implementation
356	*	356	*
357	* @param b Buddy system	357	* @param b Buddy system
358	* @param block Buddy system block	358	* @param block Buddy system block
359	*	359	*
360	*/	360	*/
361	static void zone_buddy_mark_busy(buddy_system_t b, link_t block) {	361	static void zone_buddy_mark_busy(buddy_system_t b, link_t block) {
362	frame_t * frame;	362	frame_t * frame;
363	frame = list_get_instance(block, frame_t, buddy_link);	363	frame = list_get_instance(block, frame_t, buddy_link);
364	frame->refcount = 1;	364	frame->refcount = 1;
365	}	365	}
366		366
367	/** Buddy system mark_available implementation	367	/** Buddy system mark_available implementation
368	*	368	*
369	* @param b Buddy system	369	* @param b Buddy system
370	* @param block Buddy system block	370	* @param block Buddy system block
371	*	371	*
372	*/	372	*/
373	static void zone_buddy_mark_available(buddy_system_t b, link_t block) {	373	static void zone_buddy_mark_available(buddy_system_t b, link_t block) {
374	frame_t * frame;	374	frame_t * frame;
375	frame = list_get_instance(block, frame_t, buddy_link);	375	frame = list_get_instance(block, frame_t, buddy_link);
376	frame->refcount = 0;	376	frame->refcount = 0;
377	}	377	}
378		378
379	static struct buddy_system_operations zone_buddy_system_operations = {	379	static struct buddy_system_operations zone_buddy_system_operations = {
380	.find_buddy = zone_buddy_find_buddy,	380	.find_buddy = zone_buddy_find_buddy,
381	.bisect = zone_buddy_bisect,	381	.bisect = zone_buddy_bisect,
382	.coalesce = zone_buddy_coalesce,	382	.coalesce = zone_buddy_coalesce,
383	.set_order = zone_buddy_set_order,	383	.set_order = zone_buddy_set_order,
384	.get_order = zone_buddy_get_order,	384	.get_order = zone_buddy_get_order,
385	.mark_busy = zone_buddy_mark_busy,	385	.mark_busy = zone_buddy_mark_busy,
386	.mark_available = zone_buddy_mark_available,	386	.mark_available = zone_buddy_mark_available,
387	.find_block = zone_buddy_find_block	387	.find_block = zone_buddy_find_block
388	};	388	};
389		389
390	/*************************************/	390	/*************************************/
391	/* Zone functions */	391	/* Zone functions */
392		392
393	/** Allocate frame in particular zone	393	/** Allocate frame in particular zone
394	*	394	*
395	* Assume zone is locked	395	* Assume zone is locked
396	*	396	*
397	* @return Frame index in zone	397	* @return Frame index in zone
398	*/	398	*/
399	static pfn_t zone_frame_alloc(zone_t zone,__u8 order, int flags, int status)	399	static pfn_t zone_frame_alloc(zone_t zone,__u8 order, int flags, int status)
400	{	400	{
401	pfn_t v;	401	pfn_t v;
402	link_t *tmp;	402	link_t *tmp;
403	frame_t *frame;	403	frame_t *frame;
404		404
405	/* Allocate frames from zone buddy system */	405	/* Allocate frames from zone buddy system */
406	tmp = buddy_system_alloc(zone->buddy_system, order);	406	tmp = buddy_system_alloc(zone->buddy_system, order);
407		407
408	ASSERT(tmp);	408	ASSERT(tmp);
409		409
410	/* Update zone information. */	410	/* Update zone information. */
411	zone->free_count -= (1 << order);	411	zone->free_count -= (1 << order);
412	zone->busy_count += (1 << order);	412	zone->busy_count += (1 << order);
413		413
414	/* Frame will be actually a first frame of the block. */	414	/* Frame will be actually a first frame of the block. */
415	frame = list_get_instance(tmp, frame_t, buddy_link);	415	frame = list_get_instance(tmp, frame_t, buddy_link);
416		416
417	/* get frame address */	417	/* get frame address */
418	v = make_frame_index(zone, frame);	418	v = make_frame_index(zone, frame);
419	return v;	419	return v;
420	}	420	}
421		421
422	/** Free frame from zone	422	/** Free frame from zone
423	*	423	*
424	* Assume zone is locked	424	* Assume zone is locked
425	*/	425	*/
426	static void zone_frame_free(zone_t *zone, pfn_t frame_idx)	426	static void zone_frame_free(zone_t *zone, index_t frame_idx)
427	{	427	{
428	frame_t *frame;	428	frame_t *frame;
429	__u8 order;	429	__u8 order;
430		430
431	frame = &zone->frames[frame_idx];	431	frame = &zone->frames[frame_idx];
432		432
433	/* remember frame order */	433	/* remember frame order */
434	order = frame->buddy_order;	434	order = frame->buddy_order;
435		435
436	ASSERT(frame->refcount);	436	ASSERT(frame->refcount);
437		437
438	if (!--frame->refcount) {	438	if (!--frame->refcount) {
439	buddy_system_free(zone->buddy_system, &frame->buddy_link);	439	buddy_system_free(zone->buddy_system, &frame->buddy_link);
440	}	440	}
441		441
442	/* Update zone information. */	442	/* Update zone information. */
443	zone->free_count += (1 << order);	443	zone->free_count += (1 << order);
444	zone->busy_count -= (1 << order);	444	zone->busy_count -= (1 << order);
445	}	445	}
446		446
447	/** Return frame from zone */	447	/** Return frame from zone */
448	static frame_t * zone_get_frame(zone_t *zone, pfn_t frame_idx)	448	static frame_t * zone_get_frame(zone_t *zone, index_t frame_idx)
449	{	449	{
450	ASSERT(frame_idx < zone->count);	450	ASSERT(frame_idx < zone->count);
451	return &zone->frames[frame_idx];	451	return &zone->frames[frame_idx];
452	}	452	}
453		453
454	/** Mark frame in zone unavailable to allocation */	454	/** Mark frame in zone unavailable to allocation */
455	static void zone_mark_unavailable(zone_t *zone, pfn_t frame_idx)	455	static void zone_mark_unavailable(zone_t *zone, index_t frame_idx)
456	{	456	{
457	frame_t *frame;	457	frame_t *frame;
458	link_t *link;	458	link_t *link;
459		459
460	frame = zone_get_frame(zone, frame_idx);	460	frame = zone_get_frame(zone, frame_idx);
461	link = buddy_system_alloc_block(zone->buddy_system,	461	link = buddy_system_alloc_block(zone->buddy_system,
462	&frame->buddy_link);	462	&frame->buddy_link);
463	ASSERT(link);	463	ASSERT(link);
464	zone->free_count--;	464	zone->free_count--;
465	}	465	}
466		466
467	/** Create frame zone	467	/** Create frame zone
468	*	468	*
469	* Create new frame zone.	469	* Create new frame zone.
470	*	470	*
471	* @param start Physical address of the first frame within the zone.	471	* @param start Physical address of the first frame within the zone.
472	* @param size Size of the zone. Must be a multiple of FRAME_SIZE.	472	* @param size Size of the zone. Must be a multiple of FRAME_SIZE.
473	* @param conffram Address of configuration frame	473	* @param conffram Address of configuration frame
474	* @param flags Zone flags.	474	* @param flags Zone flags.
475	*	475	*
476	* @return Initialized zone.	476	* @return Initialized zone.
477	*/	477	*/
478	static zone_t * zone_construct(pfn_t start, pfn_t count,	478	static zone_t * zone_construct(pfn_t start, count_t count,
479	zone_t *z, int flags)	479	zone_t *z, int flags)
480	{	480	{
481	int i;	481	int i;
482	__u8 max_order;	482	__u8 max_order;
483		483
484	spinlock_initialize(&z->lock, "zone_lock");	484	spinlock_initialize(&z->lock, "zone_lock");
485	z->base = start;	485	z->base = start;
486	z->count = count;	486	z->count = count;
487	z->flags = flags;	487	z->flags = flags;
488	z->free_count = count;	488	z->free_count = count;
489	z->busy_count = 0;	489	z->busy_count = 0;
490		490
491	/*	491	/*
492	* Compute order for buddy system, initialize	492	* Compute order for buddy system, initialize
493	*/	493	*/
494	for (max_order = 0; count >> max_order; max_order++)	494	for (max_order = 0; count >> max_order; max_order++)
495	;	495	;
496	z->buddy_system = (buddy_system_t *)&z[1];	496	z->buddy_system = (buddy_system_t *)&z[1];
497		497
498	buddy_system_create(z->buddy_system, max_order,	498	buddy_system_create(z->buddy_system, max_order,
499	&zone_buddy_system_operations,	499	&zone_buddy_system_operations,
500	(void *) z);	500	(void *) z);

Subversion Repositories HelenOS-historic

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