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


/*
 * Copyright (C) 2001-2004 Jakub Jermar
 * 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.
 */
 
#include <typedefs.h>
#include <arch/types.h>
#include <mm/heap.h>
#include <mm/frame.h>
#include <mm/vm.h>
#include <panic.h>
#include <debug.h>
#include <list.h>
#include <synch/spinlock.h>
#include <arch/asm.h>
#include <arch.h>
 
spinlock_t zone_head_lock;       /**< this lock protects zone_head list */
link_t zone_head;                /**< list of all zones in the system */
 
static struct buddy_system_operations  zone_buddy_system_operations = {
    .find_buddy = zone_buddy_find_buddy,
    .bisect = zone_buddy_bisect,
    .coalesce = zone_buddy_coalesce,
    .set_order = zone_buddy_set_order,
    .get_order = zone_buddy_get_order,
};
 
/** Initialize physical memory management
 *
 * Initialize physical memory managemnt.
 */
void frame_init(void)
{
    if (config.cpu_active == 1) {
        zone_init();
    }
 
    frame_arch_init();
   
    if (config.cpu_active == 1) {
                frame_region_not_free(config.base, config.base + config.kernel_size + CONFIG_STACK_SIZE);
        }  
}
 
/** Allocate a frame
 *
 * Allocate a frame of physical memory.
 *
 * @param flags Flags for host zone selection and address processing.
 *
 * @return Allocated frame.
 */
__address frame_alloc(int flags)
{
    ipl_t ipl;
    link_t *cur, *tmp;
    zone_t *z;
    zone_t *zone = NULL;
    frame_t *frame = NULL;
    __address v;
   
loop:
    ipl = interrupts_disable();
    spinlock_lock(&zone_head_lock);
   
    /*
     * First, find suitable frame zone.
     */
    for (cur = zone_head.next; cur != &zone_head; cur = cur->next) {
        z = list_get_instance(cur, zone_t, link);
       
        spinlock_lock(&z->lock);
        /*
         * Check if the zone has any free frames.
         */
        if (z->free_count) {
            zone = z;
            break;
        }
        spinlock_unlock(&z->lock);
    }
   
    if (!zone) {
        if (flags & FRAME_PANIC)
            panic("Can't allocate frame.\n");
       
        /*
         * TODO: Sleep until frames are available again.
         */
        spinlock_unlock(&zone_head_lock);
        interrupts_restore(ipl);
 
        panic("Sleep not implemented.\n");
        goto loop;
    }
       
    tmp = zone->free_head.next;
    frame = list_get_instance(tmp, frame_t, link);
 
    frame->refcount++;
    list_remove(tmp);           /* remove frame from free_head */
    zone->free_count--;
    zone->busy_count++;
   
    //v = zone->base + (frame - zone->frames) * FRAME_SIZE;
    v = FRAME2ADDR(zone, frame);
   
    if (flags & FRAME_KA)
        v = PA2KA(v);
   
    spinlock_unlock(&zone->lock);
   
    spinlock_unlock(&zone_head_lock);
    interrupts_restore(ipl);
   
    return v;
}
 
/** Free 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 addr Address of the frame to be freed. It must be a multiple of FRAME_SIZE.
 */
void frame_free(__address addr)
{
    ipl_t ipl;
    link_t *cur;
    zone_t *z;
    zone_t *zone = NULL;
    frame_t *frame;
   
    ASSERT(addr % FRAME_SIZE == 0);
   
    ipl = interrupts_disable();
    spinlock_lock(&zone_head_lock);
   
    /*
     * First, find host frame zone for addr.
     */
    for (cur = zone_head.next; cur != &zone_head; cur = cur->next) {
        z = list_get_instance(cur, zone_t, link);
       
        spinlock_lock(&z->lock);
       
        if (IS_KA(addr))
            addr = KA2PA(addr);
       
        /*
         * Check if addr belongs to z.
         */
        if ((addr >= z->base) && (addr <= z->base + (z->free_count + z->busy_count) * FRAME_SIZE)) {
            zone = z;
            break;
        }
        spinlock_unlock(&z->lock);
    }
   
    ASSERT(zone != NULL);
   
    frame = ADDR2FRAME(zone, addr);
    // frame = &zone->frames[(addr - zone->base)/FRAME_SIZE];
    ASSERT(frame->refcount);
 
    if (!--frame->refcount) {
        list_append(&frame->link, &zone->free_head);    /* append frame to free_head */
        zone->free_count++;
        zone->busy_count--;
    }
   
    spinlock_unlock(&zone->lock);  
   
    spinlock_unlock(&zone_head_lock);
    interrupts_restore(ipl);
}
 
/** Mark frame not free.
 *
 * Find respective frame structrue for supplied addr.
 * Increment frame reference count and remove the frame structure from free list.
 *
 * @param addr Address of the frame to be marked. It must be a multiple of FRAME_SIZE.
 */
void frame_not_free(__address addr)
{
    ipl_t ipl;
    link_t *cur;
    zone_t *z;
    zone_t *zone = NULL;
    frame_t *frame;
   
    ASSERT(addr % FRAME_SIZE == 0);
   
    ipl = interrupts_disable();
    spinlock_lock(&zone_head_lock);
   
    /*
     * First, find host frame zone for addr.
     */
    for (cur = zone_head.next; cur != &zone_head; cur = cur->next) {
        z = list_get_instance(cur, zone_t, link);
       
        spinlock_lock(&z->lock);
       
        if (IS_KA(addr))
            addr = KA2PA(addr);
       
        /*
         * Check if addr belongs to z.
         */
        if ((addr >= z->base) && (addr <= z->base + (z->free_count + z->busy_count) * FRAME_SIZE)) {
            zone = z;
            break;
        }
        spinlock_unlock(&z->lock);
    }
   
    ASSERT(zone != NULL);
   
    //frame = &zone->frames[(addr - zone->base)/FRAME_SIZE];
    frame = ADDR2FRAME(zone, addr);
 
    if (!frame->refcount) {
        frame->refcount++;
 
        list_remove(&frame->link);          /* remove frame from free_head */
        zone->free_count--;
        zone->busy_count++;
    }
   
    spinlock_unlock(&zone->lock);  
   
    spinlock_unlock(&zone_head_lock);
    interrupts_restore(ipl);
}
 
/** Mark frame region not free.
 *
 * Mark frame region not free.
 *
 * @param start First address.
 * @param stop Last address.
 */
void frame_region_not_free(__address start, __address stop)
{
        __address a;
 
        start /= FRAME_SIZE;
        stop /= FRAME_SIZE;
        for (a = start; a <= stop; a++)
                frame_not_free(a * FRAME_SIZE);
}
 
 
/** Initialize zonekeeping
 *
 * Initialize zonekeeping.
 */
void zone_init(void)
{
    spinlock_initialize(&zone_head_lock);
    list_initialize(&zone_head);
}
 
/** 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 flags Zone flags.
 *
 * @return Initialized zone.
 */
zone_t *zone_create(__address start, size_t size, 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);
   
        z->base = start;
        z->flags = flags;
 
        z->free_count = cnt;
        list_initialize(&z->free_head);
 
        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);
            list_append(&z->frames[i].link, &z->free_head);
        }
       
        /*
         * Create buddy system for the zone
         */
        for (max_order = 0; cnt >> max_order; max_order++);
        z->buddy_system = buddy_system_create(max_order, &zone_buddy_system_operations);
    }
   
    return z;
}
 
/** Attach frame zone
 *
 * Attach frame zone to zone list.
 *
 * @param zone Zone to be attached.
 */
void zone_attach(zone_t *zone)
{
    ipl_t ipl;
   
    ipl = interrupts_disable();
    spinlock_lock(&zone_head_lock);
   
    list_append(&zone->link, &zone_head);
   
    spinlock_unlock(&zone_head_lock);
    interrupts_restore(ipl);
}
 
/** Initialize frame structure
 *
 * Initialize frame structure.
 *
 * @param frame Frame structure to be initialized.
 * @param zone Host frame zone.
 */
void frame_initialize(frame_t *frame, zone_t *zone)
{
    frame->refcount = 0;
    link_initialize(&frame->link);
}
 
 
 
/*
 * buddy system functions (under construction)
 *
 */
 
 
/** Allocate 2^order frames
 *
 */
__address zone_buddy_frame_alloc(int flags, __u8 order) {
    ipl_t ipl;
    link_t *cur, *tmp;
    zone_t *z;
    zone_t *zone = NULL;
    frame_t *frame = NULL;
    __address v;
   
loop:
    ipl = interrupts_disable();
    spinlock_lock(&zone_head_lock);
   
    /*
     * First, find suitable frame zone.
     */
    for (cur = zone_head.next; cur != &zone_head; cur = cur->next) {
        z = list_get_instance(cur, zone_t, link);
       
        spinlock_lock(&z->lock);
        /*
         * Check if the zone has 2^order frames area available
         * TODO: Must check if buddy system has at least block in order >= given order
         */
        if (z->free_count == (1 >> order)) {
            zone = z;
            break;
        }
       
        spinlock_unlock(&z->lock);
    }
   
    if (!zone) {
        if (flags & FRAME_PANIC)
            panic("Can't allocate frame.\n");
       
        /*
         * TODO: Sleep until frames are available again.
         */
        spinlock_unlock(&zone_head_lock);
        interrupts_restore(ipl);
 
        panic("Sleep not implemented.\n");
        goto loop;
    }
       
 
    /* Allocate frames from zone buddy system */
    cur = buddy_system_alloc(zone->buddy_system, order);
   
    /* frame will be actually a first frame of the block */
    frame = list_get_instance(cur, frame_t, buddy_link);
   
    /* get frame address */
    v = FRAME2ADDR(zone, frame);
   
    if (flags & FRAME_KA)
        v = PA2KA(v);
   
    spinlock_unlock(&zone->lock);
    spinlock_unlock(&zone_head_lock);
    interrupts_restore(ipl);
   
    return v;
}
 
 
/** Free frame(s)
 *
 * @param addr Address of the frame(s) to be freed. It must be a multiple of FRAME_SIZE.
 */
void zone_buddy_frame_free(__address addr)
{
    ipl_t ipl;
    link_t *cur;
    zone_t *z;
    zone_t *zone = NULL;
    frame_t *frame;
   
    ASSERT(addr % FRAME_SIZE == 0);
   
    ipl = interrupts_disable();
    spinlock_lock(&zone_head_lock);
   
    /*
     * First, find host frame zone for addr.
     */
    for (cur = zone_head.next; cur != &zone_head; cur = cur->next) {
        z = list_get_instance(cur, zone_t, link);
       
        spinlock_lock(&z->lock);
       
        if (IS_KA(addr))
            addr = KA2PA(addr);
       
        /*
         * Check if addr belongs to z.
         */
        if ((addr >= z->base) && (addr <= z->base + (z->free_count + z->busy_count) * FRAME_SIZE)) {
            zone = z;
            break;
        }
        spinlock_unlock(&z->lock);
    }
   
    ASSERT(zone != NULL);
   
    frame = ADDR2FRAME(zone, addr);
 
    ASSERT(frame->refcount);
 
    if (!--frame->refcount) {
        buddy_system_free(zone->buddy_system, &frame->buddy_link);
    }
   
    spinlock_unlock(&zone->lock);  
   
    spinlock_unlock(&zone_head_lock);
    interrupts_restore(ipl);
}
 
/** 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
 * @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
 *
 * @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;
}
 

Rev 479	Rev 480
1	/*	1	/*
2	* Copyright (C) 2001-2004 Jakub Jermar	2	* Copyright (C) 2001-2004 Jakub Jermar
3	* All rights reserved.	3	* All rights reserved.
4	*	4	*
5	* Redistribution and use in source and binary forms, with or without	5	* Redistribution and use in source and binary forms, with or without
6	* modification, are permitted provided that the following conditions	6	* modification, are permitted provided that the following conditions
7	* are met:	7	* are met:
8	*	8	*
9	* - Redistributions of source code must retain the above copyright	9	* - Redistributions of source code must retain the above copyright
10	* notice, this list of conditions and the following disclaimer.	10	* notice, this list of conditions and the following disclaimer.
11	* - Redistributions in binary form must reproduce the above copyright	11	* - Redistributions in binary form must reproduce the above copyright
12	* notice, this list of conditions and the following disclaimer in the	12	* notice, this list of conditions and the following disclaimer in the
13	* documentation and/or other materials provided with the distribution.	13	* documentation and/or other materials provided with the distribution.
14	* - The name of the author may not be used to endorse or promote products	14	* - The name of the author may not be used to endorse or promote products
15	* derived from this software without specific prior written permission.	15	* derived from this software without specific prior written permission.
16	*	16	*
17	* THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR	17	* THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
18	* IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES	18	* IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
19	* OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.	19	* OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
20	* IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,	20	* IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
21	* INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT	21	* INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
22	* NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,	22	* NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
23	* DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY	23	* DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
24	* THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT	24	* THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
25	* (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF	25	* (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
26	* THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.	26	* THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
27	*/	27	*/
28		28
29	#include <typedefs.h>	29	#include <typedefs.h>
30	#include <arch/types.h>	30	#include <arch/types.h>
31	#include <mm/heap.h>	31	#include <mm/heap.h>
32	#include <mm/frame.h>	32	#include <mm/frame.h>
33	#include <mm/vm.h>	33	#include <mm/vm.h>
34	#include <panic.h>	34	#include <panic.h>
35	#include <debug.h>	35	#include <debug.h>
36	#include <list.h>	36	#include <list.h>
37	#include <synch/spinlock.h>	37	#include <synch/spinlock.h>
38	#include <arch/asm.h>	38	#include <arch/asm.h>
39	#include <arch.h>	39	#include <arch.h>
40		40
41	spinlock_t zone_head_lock; /*< this lock protects zone_head list /	41	spinlock_t zone_head_lock; /*< this lock protects zone_head list /
42	link_t zone_head; /*< list of all zones in the system /	42	link_t zone_head; /*< list of all zones in the system /
43		43
44	static struct buddy_system_operations zone_buddy_system_operations = {	44	static struct buddy_system_operations zone_buddy_system_operations = {
45	.find_buddy = zone_buddy_find_buddy,	45	.find_buddy = zone_buddy_find_buddy,
46	.bisect = zone_buddy_bisect,	46	.bisect = zone_buddy_bisect,
47	.coalesce = zone_buddy_coalesce,	47	.coalesce = zone_buddy_coalesce,
48	.set_order = zone_buddy_set_order,	48	.set_order = zone_buddy_set_order,
49	.get_order = zone_buddy_get_order,	49	.get_order = zone_buddy_get_order,
50	};	50	};
51		51
52	/** Initialize physical memory management	52	/** Initialize physical memory management
53	*	53	*
54	* Initialize physical memory managemnt.	54	* Initialize physical memory managemnt.
55	*/	55	*/
56	void frame_init(void)	56	void frame_init(void)
57	{	57	{
58	if (config.cpu_active == 1) {	58	if (config.cpu_active == 1) {
59	zone_init();	59	zone_init();
60	}	60	}
61		61
62	frame_arch_init();	62	frame_arch_init();
63		63
64	if (config.cpu_active == 1) {	64	if (config.cpu_active == 1) {
65	frame_region_not_free(config.base, config.base + config.kernel_size + CONFIG_STACK_SIZE);	65	frame_region_not_free(config.base, config.base + config.kernel_size + CONFIG_STACK_SIZE);
66	}	66	}
67	}	67	}
68		68
69	/** Allocate a frame	69	/** Allocate a frame
70	*	70	*
71	* Allocate a frame of physical memory.	71	* Allocate a frame of physical memory.
72	*	72	*
73	* @param flags Flags for host zone selection and address processing.	73	* @param flags Flags for host zone selection and address processing.
74	*	74	*
75	* @return Allocated frame.	75	* @return Allocated frame.
76	*/	76	*/
77	__address frame_alloc(int flags)	77	__address frame_alloc(int flags)
78	{	78	{
79	ipl_t ipl;	79	ipl_t ipl;
80	link_t cur, tmp;	80	link_t cur, tmp;
81	zone_t *z;	81	zone_t *z;
82	zone_t *zone = NULL;	82	zone_t *zone = NULL;
83	frame_t *frame = NULL;	83	frame_t *frame = NULL;
84	__address v;	84	__address v;
85		85
86	loop:	86	loop:
87	ipl = interrupts_disable();	87	ipl = interrupts_disable();
88	spinlock_lock(&zone_head_lock);	88	spinlock_lock(&zone_head_lock);
89		89
90	/*	90	/*
91	* First, find suitable frame zone.	91	* First, find suitable frame zone.
92	*/	92	*/
93	for (cur = zone_head.next; cur != &zone_head; cur = cur->next) {	93	for (cur = zone_head.next; cur != &zone_head; cur = cur->next) {
94	z = list_get_instance(cur, zone_t, link);	94	z = list_get_instance(cur, zone_t, link);
95		95
96	spinlock_lock(&z->lock);	96	spinlock_lock(&z->lock);
97	/*	97	/*
98	* Check if the zone has any free frames.	98	* Check if the zone has any free frames.
99	*/	99	*/
100	if (z->free_count) {	100	if (z->free_count) {
101	zone = z;	101	zone = z;
102	break;	102	break;
103	}	103	}
104	spinlock_unlock(&z->lock);	104	spinlock_unlock(&z->lock);
105	}	105	}
106		106
107	if (!zone) {	107	if (!zone) {
108	if (flags & FRAME_PANIC)	108	if (flags & FRAME_PANIC)
109	panic("Can't allocate frame.\n");	109	panic("Can't allocate frame.\n");
110		110
111	/*	111	/*
112	* TODO: Sleep until frames are available again.	112	* TODO: Sleep until frames are available again.
113	*/	113	*/
114	spinlock_unlock(&zone_head_lock);	114	spinlock_unlock(&zone_head_lock);
115	interrupts_restore(ipl);	115	interrupts_restore(ipl);
116		116
117	panic("Sleep not implemented.\n");	117	panic("Sleep not implemented.\n");
118	goto loop;	118	goto loop;
119	}	119	}
120		120
121	tmp = zone->free_head.next;	121	tmp = zone->free_head.next;
122	frame = list_get_instance(tmp, frame_t, link);	122	frame = list_get_instance(tmp, frame_t, link);
123		123
124	frame->refcount++;	124	frame->refcount++;
125	list_remove(tmp); /* remove frame from free_head */	125	list_remove(tmp); /* remove frame from free_head */
126	zone->free_count--;	126	zone->free_count--;
127	zone->busy_count++;	127	zone->busy_count++;
128		128
129	//v = zone->base + (frame - zone->frames) * FRAME_SIZE;	129	//v = zone->base + (frame - zone->frames) * FRAME_SIZE;
130	v = FRAME2ADDR(zone, frame);	130	v = FRAME2ADDR(zone, frame);
131		131
132	if (flags & FRAME_KA)	132	if (flags & FRAME_KA)
133	v = PA2KA(v);	133	v = PA2KA(v);
134		134
135	spinlock_unlock(&zone->lock);	135	spinlock_unlock(&zone->lock);
136		136
137	spinlock_unlock(&zone_head_lock);	137	spinlock_unlock(&zone_head_lock);
138	interrupts_restore(ipl);	138	interrupts_restore(ipl);
139		139
140	return v;	140	return v;
141	}	141	}
142		142
143	/** Free a frame.	143	/** Free a frame.
144	*	144	*
145	* Find respective frame structrue for supplied addr.	145	* Find respective frame structrue for supplied addr.
146	* Decrement frame reference count.	146	* Decrement frame reference count.
147	* If it drops to zero, move the frame structure to free list.	147	* If it drops to zero, move the frame structure to free list.
148	*	148	*
149	* @param addr Address of the frame to be freed. It must be a multiple of FRAME_SIZE.	149	* @param addr Address of the frame to be freed. It must be a multiple of FRAME_SIZE.
150	*/	150	*/
151	void frame_free(__address addr)	151	void frame_free(__address addr)
152	{	152	{
153	ipl_t ipl;	153	ipl_t ipl;
154	link_t *cur;	154	link_t *cur;
155	zone_t *z;	155	zone_t *z;
156	zone_t *zone = NULL;	156	zone_t *zone = NULL;
157	frame_t *frame;	157	frame_t *frame;
158		158
159	ASSERT(addr % FRAME_SIZE == 0);	159	ASSERT(addr % FRAME_SIZE == 0);
160		160
161	ipl = interrupts_disable();	161	ipl = interrupts_disable();
162	spinlock_lock(&zone_head_lock);	162	spinlock_lock(&zone_head_lock);
163		163
164	/*	164	/*
165	* First, find host frame zone for addr.	165	* First, find host frame zone for addr.
166	*/	166	*/
167	for (cur = zone_head.next; cur != &zone_head; cur = cur->next) {	167	for (cur = zone_head.next; cur != &zone_head; cur = cur->next) {
168	z = list_get_instance(cur, zone_t, link);	168	z = list_get_instance(cur, zone_t, link);
169		169
170	spinlock_lock(&z->lock);	170	spinlock_lock(&z->lock);
171		171
172	if (IS_KA(addr))	172	if (IS_KA(addr))
173	addr = KA2PA(addr);	173	addr = KA2PA(addr);
174		174
175	/*	175	/*
176	* Check if addr belongs to z.	176	* Check if addr belongs to z.
177	*/	177	*/
178	if ((addr >= z->base) && (addr <= z->base + (z->free_count + z->busy_count) * FRAME_SIZE)) {	178	if ((addr >= z->base) && (addr <= z->base + (z->free_count + z->busy_count) * FRAME_SIZE)) {
179	zone = z;	179	zone = z;
180	break;	180	break;
181	}	181	}
182	spinlock_unlock(&z->lock);	182	spinlock_unlock(&z->lock);
183	}	183	}
184		184
185	ASSERT(zone != NULL);	185	ASSERT(zone != NULL);
186		186
187	frame = ADDR2FRAME(zone, addr);	187	frame = ADDR2FRAME(zone, addr);
188	// frame = &zone->frames[(addr - zone->base)/FRAME_SIZE];	188	// frame = &zone->frames[(addr - zone->base)/FRAME_SIZE];
189	ASSERT(frame->refcount);	189	ASSERT(frame->refcount);
190		190
191	if (!--frame->refcount) {	191	if (!--frame->refcount) {
192	list_append(&frame->link, &zone->free_head); /* append frame to free_head */	192	list_append(&frame->link, &zone->free_head); /* append frame to free_head */
193	zone->free_count++;	193	zone->free_count++;
194	zone->busy_count--;	194	zone->busy_count--;
195	}	195	}
196		196
197	spinlock_unlock(&zone->lock);	197	spinlock_unlock(&zone->lock);
198		198
199	spinlock_unlock(&zone_head_lock);	199	spinlock_unlock(&zone_head_lock);
200	interrupts_restore(ipl);	200	interrupts_restore(ipl);
201	}	201	}
202		202
203	/** Mark frame not free.	203	/** Mark frame not free.
204	*	204	*
205	* Find respective frame structrue for supplied addr.	205	* Find respective frame structrue for supplied addr.
206	* Increment frame reference count and remove the frame structure from free list.	206	* Increment frame reference count and remove the frame structure from free list.
207	*	207	*
208	* @param addr Address of the frame to be marked. It must be a multiple of FRAME_SIZE.	208	* @param addr Address of the frame to be marked. It must be a multiple of FRAME_SIZE.
209	*/	209	*/
210	void frame_not_free(__address addr)	210	void frame_not_free(__address addr)
211	{	211	{
212	ipl_t ipl;	212	ipl_t ipl;
213	link_t *cur;	213	link_t *cur;
214	zone_t *z;	214	zone_t *z;
215	zone_t *zone = NULL;	215	zone_t *zone = NULL;
216	frame_t *frame;	216	frame_t *frame;
217		217
218	ASSERT(addr % FRAME_SIZE == 0);	218	ASSERT(addr % FRAME_SIZE == 0);
219		219
220	ipl = interrupts_disable();	220	ipl = interrupts_disable();
221	spinlock_lock(&zone_head_lock);	221	spinlock_lock(&zone_head_lock);
222		222
223	/*	223	/*
224	* First, find host frame zone for addr.	224	* First, find host frame zone for addr.
225	*/	225	*/
226	for (cur = zone_head.next; cur != &zone_head; cur = cur->next) {	226	for (cur = zone_head.next; cur != &zone_head; cur = cur->next) {
227	z = list_get_instance(cur, zone_t, link);	227	z = list_get_instance(cur, zone_t, link);
228		228
229	spinlock_lock(&z->lock);	229	spinlock_lock(&z->lock);
230		230
231	if (IS_KA(addr))	231	if (IS_KA(addr))
232	addr = KA2PA(addr);	232	addr = KA2PA(addr);
233		233
234	/*	234	/*
235	* Check if addr belongs to z.	235	* Check if addr belongs to z.
236	*/	236	*/
237	if ((addr >= z->base) && (addr <= z->base + (z->free_count + z->busy_count) * FRAME_SIZE)) {	237	if ((addr >= z->base) && (addr <= z->base + (z->free_count + z->busy_count) * FRAME_SIZE)) {
238	zone = z;	238	zone = z;
239	break;	239	break;
240	}	240	}
241	spinlock_unlock(&z->lock);	241	spinlock_unlock(&z->lock);
242	}	242	}
243		243
244	ASSERT(zone != NULL);	244	ASSERT(zone != NULL);
245		245
246	//frame = &zone->frames[(addr - zone->base)/FRAME_SIZE];	246	//frame = &zone->frames[(addr - zone->base)/FRAME_SIZE];
247	frame = ADDR2FRAME(zone, addr);	247	frame = ADDR2FRAME(zone, addr);
248		248
249	if (!frame->refcount) {	249	if (!frame->refcount) {
250	frame->refcount++;	250	frame->refcount++;
251		251
252	list_remove(&frame->link); /* remove frame from free_head */	252	list_remove(&frame->link); /* remove frame from free_head */
253	zone->free_count--;	253	zone->free_count--;
254	zone->busy_count++;	254	zone->busy_count++;
255	}	255	}
256		256
257	spinlock_unlock(&zone->lock);	257	spinlock_unlock(&zone->lock);
258		258
259	spinlock_unlock(&zone_head_lock);	259	spinlock_unlock(&zone_head_lock);
260	interrupts_restore(ipl);	260	interrupts_restore(ipl);
261	}	261	}
262		262
263	/** Mark frame region not free.	263	/** Mark frame region not free.
264	*	264	*
265	* Mark frame region not free.	265	* Mark frame region not free.
266	*	266	*
267	* @param start First address.	267	* @param start First address.
268	* @param stop Last address.	268	* @param stop Last address.
269	*/	269	*/
270	void frame_region_not_free(__address start, __address stop)	270	void frame_region_not_free(__address start, __address stop)
271	{	271	{
272	__address a;	272	__address a;
273		273
274	start /= FRAME_SIZE;	274	start /= FRAME_SIZE;
275	stop /= FRAME_SIZE;	275	stop /= FRAME_SIZE;
276	for (a = start; a <= stop; a++)	276	for (a = start; a <= stop; a++)
277	frame_not_free(a * FRAME_SIZE);	277	frame_not_free(a * FRAME_SIZE);
278	}	278	}
279		279
280		280
281	/** Initialize zonekeeping	281	/** Initialize zonekeeping
282	*	282	*
283	* Initialize zonekeeping.	283	* Initialize zonekeeping.
284	*/	284	*/
285	void zone_init(void)	285	void zone_init(void)
286	{	286	{
287	spinlock_initialize(&zone_head_lock);	287	spinlock_initialize(&zone_head_lock);
288	list_initialize(&zone_head);	288	list_initialize(&zone_head);
289	}	289	}
290		290
291	/** Create frame zone	291	/** Create frame zone
292	*	292	*
293	* Create new frame zone.	293	* Create new frame zone.
294	*	294	*
295	* @param start Physical address of the first frame within the zone.	295	* @param start Physical address of the first frame within the zone.
296	* @param size Size of the zone. Must be a multiple of FRAME_SIZE.	296	* @param size Size of the zone. Must be a multiple of FRAME_SIZE.
297	* @param flags Zone flags.	297	* @param flags Zone flags.
298	*	298	*
299	* @return Initialized zone.	299	* @return Initialized zone.
300	*/	300	*/
301	zone_t *zone_create(__address start, size_t size, int flags)	301	zone_t *zone_create(__address start, size_t size, int flags)
302	{	302	{
303	zone_t *z;	303	zone_t *z;
304	count_t cnt;	304	count_t cnt;
305	int i;	305	int i;
306	__u8 max_order;	306	__u8 max_order;
307		307
308	ASSERT(start % FRAME_SIZE == 0);	308	ASSERT(start % FRAME_SIZE == 0);
309	ASSERT(size % FRAME_SIZE == 0);	309	ASSERT(size % FRAME_SIZE == 0);
310		310
311	cnt = size / FRAME_SIZE;	311	cnt = size / FRAME_SIZE;
312		312
313	z = (zone_t *) early_malloc(sizeof(zone_t));	313	z = (zone_t *) early_malloc(sizeof(zone_t));
314	if (z) {	314	if (z) {
315	link_initialize(&z->link);	315	link_initialize(&z->link);
316	spinlock_initialize(&z->lock);	316	spinlock_initialize(&z->lock);
317		317
318	z->base = start;	318	z->base = start;
319	z->flags = flags;	319	z->flags = flags;
320		320
321	z->free_count = cnt;	321	z->free_count = cnt;
322	list_initialize(&z->free_head);	322	list_initialize(&z->free_head);
323		323
324	z->busy_count = 0;	324	z->busy_count = 0;
325		325
326	z->frames = (frame_t ) early_malloc(cnt sizeof(frame_t));	326	z->frames = (frame_t ) early_malloc(cnt sizeof(frame_t));
327	if (!z->frames) {	327	if (!z->frames) {
328	early_free(z);	328	early_free(z);
329	return NULL;	329	return NULL;
330	}	330	}
331		331
332	for (i = 0; i<cnt; i++) {	332	for (i = 0; i<cnt; i++) {
333	frame_initialize(&z->frames[i], z);	333	frame_initialize(&z->frames[i], z);
334	list_append(&z->frames[i].link, &z->free_head);	334	list_append(&z->frames[i].link, &z->free_head);
335	}	335	}
336		336
337	/*	337	/*
338	* Create buddy system for the zone	338	* Create buddy system for the zone
339	*/	339	*/
340	for (max_order = 0; cnt >> max_order; max_order++);	340	for (max_order = 0; cnt >> max_order; max_order++);
341	z->buddy_system = buddy_system_create(max_order, &zone_buddy_system_operations);	341	z->buddy_system = buddy_system_create(max_order, &zone_buddy_system_operations);
342	}	342	}
343		343
344	return z;	344	return z;
345	}	345	}
346		346
347	/** Attach frame zone	347	/** Attach frame zone
348	*	348	*
349	* Attach frame zone to zone list.	349	* Attach frame zone to zone list.
350	*	350	*
351	* @param zone Zone to be attached.	351	* @param zone Zone to be attached.
352	*/	352	*/
353	void zone_attach(zone_t *zone)	353	void zone_attach(zone_t *zone)
354	{	354	{
355	ipl_t ipl;	355	ipl_t ipl;
356		356
357	ipl = interrupts_disable();	357	ipl = interrupts_disable();
358	spinlock_lock(&zone_head_lock);	358	spinlock_lock(&zone_head_lock);
359		359
360	list_append(&zone->link, &zone_head);	360	list_append(&zone->link, &zone_head);
361		361
362	spinlock_unlock(&zone_head_lock);	362	spinlock_unlock(&zone_head_lock);
363	interrupts_restore(ipl);	363	interrupts_restore(ipl);
364	}	364	}
365		365
366	/** Initialize frame structure	366	/** Initialize frame structure
367	*	367	*
368	* Initialize frame structure.	368	* Initialize frame structure.
369	*	369	*
370	* @param frame Frame structure to be initialized.	370	* @param frame Frame structure to be initialized.
371	* @param zone Host frame zone.	371	* @param zone Host frame zone.
372	*/	372	*/
373	void frame_initialize(frame_t frame, zone_t zone)	373	void frame_initialize(frame_t frame, zone_t zone)
374	{	374	{
375	frame->refcount = 0;	375	frame->refcount = 0;
376	link_initialize(&frame->link);	376	link_initialize(&frame->link);
377	}	377	}
378		378
379		379
380		380
381	/*	381	/*
382	* buddy system functions (under construction)	382	* buddy system functions (under construction)
383	*	383	*
384	*/	384	*/
385		385
386		386
387	/** Allocate 2^order frames	387	/** Allocate 2^order frames
388	*	388	*
389	*/	389	*/
390	__address zone_buddy_frame_alloc(int flags, __u8 order) {	390	__address zone_buddy_frame_alloc(int flags, __u8 order) {
391	ipl_t ipl;	391	ipl_t ipl;
392	link_t cur, tmp;	392	link_t cur, tmp;
393	zone_t *z;	393	zone_t *z;
394	zone_t *zone = NULL;	394	zone_t *zone = NULL;
395	frame_t *frame = NULL;	395	frame_t *frame = NULL;
396	__address v;	396	__address v;
397		397
398	loop:	398	loop:
399	ipl = interrupts_disable();	399	ipl = interrupts_disable();
400	spinlock_lock(&zone_head_lock);	400	spinlock_lock(&zone_head_lock);
401		401
402	/*	402	/*
403	* First, find suitable frame zone.	403	* First, find suitable frame zone.
404	*/	404	*/
405	for (cur = zone_head.next; cur != &zone_head; cur = cur->next) {	405	for (cur = zone_head.next; cur != &zone_head; cur = cur->next) {
406	z = list_get_instance(cur, zone_t, link);	406	z = list_get_instance(cur, zone_t, link);
407		407
408	spinlock_lock(&z->lock);	408	spinlock_lock(&z->lock);
409	/*	409	/*
410	* Check if the zone has 2^order frames area available	410	* Check if the zone has 2^order frames area available
411	* TODO: Must check if buddy system has at least block in order >= given order	411	* TODO: Must check if buddy system has at least block in order >= given order
412	*/	412	*/
413	if (z->free_count == (1 >> order)) {	413	if (z->free_count == (1 >> order)) {
414	zone = z;	414	zone = z;
415	break;	415	break;
416	}	416	}
417		417
418	spinlock_unlock(&z->lock);	418	spinlock_unlock(&z->lock);
419	}	419	}
420		420
421	if (!zone) {	421	if (!zone) {
422	if (flags & FRAME_PANIC)	422	if (flags & FRAME_PANIC)
423	panic("Can't allocate frame.\n");	423	panic("Can't allocate frame.\n");
424		424
425	/*	425	/*
426	* TODO: Sleep until frames are available again.	426	* TODO: Sleep until frames are available again.
427	*/	427	*/
428	spinlock_unlock(&zone_head_lock);	428	spinlock_unlock(&zone_head_lock);
429	interrupts_restore(ipl);	429	interrupts_restore(ipl);
430		430
431	panic("Sleep not implemented.\n");	431	panic("Sleep not implemented.\n");
432	goto loop;	432	goto loop;
433	}	433	}
434		434
435		435
436	/* Allocate frames from zone buddy system */	436	/* Allocate frames from zone buddy system */
437	cur = buddy_system_alloc(zone->buddy_system, order);	437	cur = buddy_system_alloc(zone->buddy_system, order);
438		438
439	/* frame will be actually a first frame of the block */	439	/* frame will be actually a first frame of the block */
440	frame = list_get_instance(cur, frame_t, buddy_link);	440	frame = list_get_instance(cur, frame_t, buddy_link);
441		441
442	/* get frame address */	442	/* get frame address */
443	v = FRAME2ADDR(zone, frame);	443	v = FRAME2ADDR(zone, frame);
444		444
445	if (flags & FRAME_KA)	445	if (flags & FRAME_KA)
446	v = PA2KA(v);	446	v = PA2KA(v);
447		447
448	spinlock_unlock(&zone->lock);	448	spinlock_unlock(&zone->lock);
449	spinlock_unlock(&zone_head_lock);	449	spinlock_unlock(&zone_head_lock);
450	interrupts_restore(ipl);	450	interrupts_restore(ipl);
451		451
452	return v;	452	return v;
453	}	453	}
454		454
455		455
456	/** Free frame(s)	456	/** Free frame(s)
457	*	457	*
458	* @param addr Address of the frame(s) to be freed. It must be a multiple of FRAME_SIZE.	458	* @param addr Address of the frame(s) to be freed. It must be a multiple of FRAME_SIZE.
459	*/	459	*/
460	void zone_buddy_frame_free(__address addr)	460	void zone_buddy_frame_free(__address addr)
461	{	461	{
462	ipl_t ipl;	462	ipl_t ipl;
463	link_t *cur;	463	link_t *cur;
464	zone_t *z;	464	zone_t *z;
465	zone_t *zone = NULL;	465	zone_t *zone = NULL;
466	frame_t *frame;	466	frame_t *frame;
467		467
468	ASSERT(addr % FRAME_SIZE == 0);	468	ASSERT(addr % FRAME_SIZE == 0);
469		469
470	ipl = interrupts_disable();	470	ipl = interrupts_disable();
471	spinlock_lock(&zone_head_lock);	471	spinlock_lock(&zone_head_lock);
472		472
473	/*	473	/*
474	* First, find host frame zone for addr.	474	* First, find host frame zone for addr.
475	*/	475	*/
476	for (cur = zone_head.next; cur != &zone_head; cur = cur->next) {	476	for (cur = zone_head.next; cur != &zone_head; cur = cur->next) {
477	z = list_get_instance(cur, zone_t, link);	477	z = list_get_instance(cur, zone_t, link);
478		478
479	spinlock_lock(&z->lock);	479	spinlock_lock(&z->lock);
480		480
481	if (IS_KA(addr))	481	if (IS_KA(addr))
482	addr = KA2PA(addr);	482	addr = KA2PA(addr);
483		483
484	/*	484	/*
485	* Check if addr belongs to z.	485	* Check if addr belongs to z.
486	*/	486	*/
487	if ((addr >= z->base) && (addr <= z->base + (z->free_count + z->busy_count) * FRAME_SIZE)) {	487	if ((addr >= z->base) && (addr <= z->base + (z->free_count + z->busy_count) * FRAME_SIZE)) {
488	zone = z;	488	zone = z;
489	break;	489	break;
490	}	490	}
491	spinlock_unlock(&z->lock);	491	spinlock_unlock(&z->lock);
492	}	492	}
493		493
494	ASSERT(zone != NULL);	494	ASSERT(zone != NULL);
495		495
496	frame = ADDR2FRAME(zone, addr);	496	frame = ADDR2FRAME(zone, addr);
497		497
498	ASSERT(frame->refcount);	498	ASSERT(frame->refcount);
499		499
500	if (!--frame->refcount) {	500	if (!--frame->refcount) {

Subversion Repositories HelenOS-historic

(root)/kernel/trunk/generic/src/mm/frame.c @ 1712 – Rev 479 → 480