WebSVN – HelenOS – Diff – /branches/dynload/kernel/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>
#include <print.h>
 
spinlock_t zone_head_lock;       /**< this lock protects zone_head list */
link_t zone_head;                /**< list of all zones in the system */
 
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,
    .coalesce = zone_buddy_coalesce,
    .set_order = zone_buddy_set_order,
    .get_order = zone_buddy_get_order,
    .mark_busy = zone_buddy_mark_busy,
};
 
/** Initialize physical memory management
 *
 * Initialize physical memory managemnt.
 */
void frame_init(void)
{
    if (config.cpu_active == 1) {
        zone_init();
        frame_region_not_free(config.base, config.base + config.kernel_size + CONFIG_STACK_SIZE);
    }
 
    frame_arch_init();
}
 
/** 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, __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  */
        if (buddy_system_can_alloc(z->buddy_system, 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 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);
 
    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);
}
 
/** Mark frame region not free.
 *
 * Mark frame region not free.
 *
 * @param start First address.
 * @param stop Last address.
 */
void frame_region_not_free(__address base, size_t size)
{
    count_t index;
    index = zone_blacklist_count++;
    ASSERT(base % FRAME_SIZE == 0);
   
    if (size % FRAME_SIZE != 0) {
        size = size + (FRAME_SIZE - size % FRAME_SIZE);
    }
    ASSERT(size % FRAME_SIZE == 0);
    ASSERT(zone_blacklist_count <= ZONE_BLACKLIST_SIZE);
    zone_blacklist[index].base = base;
    zone_blacklist[index].size = size;
}
 
 
/** Initialize zonekeeping
 *
 * Initialize zonekeeping.
 */
void zone_init(void)
{
    spinlock_initialize(&zone_head_lock);
    list_initialize(&zone_head);
}
 
 
void zone_create_in_region(__address base, size_t size) {
    int i;
    zone_t * z;
    __address s; size_t sz;
   
    ASSERT(base % FRAME_SIZE == 0);
    ASSERT(size % FRAME_SIZE == 0);
   
    if (!size) return;
   
    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;
       
        }
    }
   
    z = zone_create(base, size, 0);
 
    if (!z) {
        panic("Cannot allocate zone (%dB).\n", size);
    }
   
    zone_attach(z);
}
 
 
 
/** 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;
 
    /* hack for bug #10 */
    // if (start == 0x100000) size -= (FRAME_SIZE * 256);
 
    // printf("ZONE_CREATE()   %X - %X (%d kbytes)          \n", start, start+size, size/1024); 
    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, (void *) z);
       
        /* Stuffing frames */
        for (i = 0; i<cnt; i++) {
            z->frames[i].refcount = 0;
            buddy_system_free(z->buddy_system, &z->frames[i].buddy_link);  
        }
    }
    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 = 1;
    frame->buddy_order = 0;
    link_initialize(&frame->link);
}
 
 
/** 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
 */
link_t * zone_buddy_find_buddy(buddy_system_t *b, link_t * block) {
    frame_t * frame, * f;
    zone_t * zone;
    link_t * cur;
    count_t index;
    bool is_left, is_right;
 
    frame = list_get_instance(block, frame_t, buddy_link);
    zone = (zone_t *) b->data;
   
    /*
     * (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));
   
    /*
     * test left buddy
     */
    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
 */
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)
 */
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
 */
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
 */
__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
 *
 */
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;
}
 

Rev 533	Rev 534
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	#include <print.h>	40	#include <print.h>
41		41
42	spinlock_t zone_head_lock; /*< this lock protects zone_head list /	42	spinlock_t zone_head_lock; /*< this lock protects zone_head list /
43	link_t zone_head; /*< list of all zones in the system /	43	link_t zone_head; /*< list of all zones in the system /
44		44
45	region_t zone_blacklist[ZONE_BLACKLIST_SIZE];	45	region_t zone_blacklist[ZONE_BLACKLIST_SIZE];
46	count_t zone_blacklist_count = 0;	46	count_t zone_blacklist_count = 0;
47		47
48	static struct buddy_system_operations zone_buddy_system_operations = {	48	static struct buddy_system_operations zone_buddy_system_operations = {
49	.find_buddy = zone_buddy_find_buddy,	49	.find_buddy = zone_buddy_find_buddy,
50	.bisect = zone_buddy_bisect,	50	.bisect = zone_buddy_bisect,
51	.coalesce = zone_buddy_coalesce,	51	.coalesce = zone_buddy_coalesce,
52	.set_order = zone_buddy_set_order,	52	.set_order = zone_buddy_set_order,
53	.get_order = zone_buddy_get_order,	53	.get_order = zone_buddy_get_order,
54	.mark_busy = zone_buddy_mark_busy,	54	.mark_busy = zone_buddy_mark_busy,
55	};	55	};
56		56
57	/** Initialize physical memory management	57	/** Initialize physical memory management
58	*	58	*
59	* Initialize physical memory managemnt.	59	* Initialize physical memory managemnt.
60	*/	60	*/
61	void frame_init(void)	61	void frame_init(void)
62	{	62	{
63	if (config.cpu_active == 1) {	63	if (config.cpu_active == 1) {
64	zone_init();	64	zone_init();
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	frame_arch_init();	68	frame_arch_init();
69	}	69	}
70		70
71	/** Allocate a frame	71	/** Allocate a frame
72	*	72	*
73	* Allocate a frame of physical memory.	73	* Allocate a frame of physical memory.
74	*	74	*
75	* @param flags Flags for host zone selection and address processing.	75	* @param flags Flags for host zone selection and address processing.
76	*	76	*
77	* @return Allocated frame.	77	* @return Allocated frame.
78	*/	78	*/
79	__address frame_alloc(int flags, __u8 order)	79	__address frame_alloc(int flags, __u8 order)
80	{	80	{
81	ipl_t ipl;	81	ipl_t ipl;
82	link_t cur, tmp;	82	link_t cur, tmp;
83	zone_t *z;	83	zone_t *z;
84	zone_t *zone = NULL;	84	zone_t *zone = NULL;
85	frame_t *frame = NULL;	85	frame_t *frame = NULL;
86	__address v;	86	__address v;
87		87
88	loop:	88	loop:
89	ipl = interrupts_disable();	89	ipl = interrupts_disable();
90	spinlock_lock(&zone_head_lock);	90	spinlock_lock(&zone_head_lock);
91		91
92	/*	92	/*
93	* First, find suitable frame zone.	93	* First, find suitable frame zone.
94	*/	94	*/
95	for (cur = zone_head.next; cur != &zone_head; cur = cur->next) {	95	for (cur = zone_head.next; cur != &zone_head; cur = cur->next) {
96	z = list_get_instance(cur, zone_t, link);	96	z = list_get_instance(cur, zone_t, link);
97		97
98	spinlock_lock(&z->lock);	98	spinlock_lock(&z->lock);
99		99
100	/* Check if the zone has 2^order frames area available */	100	/* Check if the zone has 2^order frames area available */
101	if (buddy_system_can_alloc(z->buddy_system, order)) {	101	if (buddy_system_can_alloc(z->buddy_system, order)) {
102	zone = z;	102	zone = z;
103	break;	103	break;
104	}	104	}
105		105
106	spinlock_unlock(&z->lock);	106	spinlock_unlock(&z->lock);
107	}	107	}
108		108
109	if (!zone) {	109	if (!zone) {
110	if (flags & FRAME_PANIC)	110	if (flags & FRAME_PANIC)
111	panic("Can't allocate frame.\n");	111	panic("Can't allocate frame.\n");
112		112
113	/*	113	/*
114	* TODO: Sleep until frames are available again.	114	* TODO: Sleep until frames are available again.
115	*/	115	*/
116	spinlock_unlock(&zone_head_lock);	116	spinlock_unlock(&zone_head_lock);
117	interrupts_restore(ipl);	117	interrupts_restore(ipl);
118		118
119	panic("Sleep not implemented.\n");	119	panic("Sleep not implemented.\n");
120	goto loop;	120	goto loop;
121	}	121	}
122		122
123		123
124	/* Allocate frames from zone buddy system */	124	/* Allocate frames from zone buddy system */
125	cur = buddy_system_alloc(zone->buddy_system, order);	125	cur = buddy_system_alloc(zone->buddy_system, order);
126		126
127	/* frame will be actually a first frame of the block */	127	/* frame will be actually a first frame of the block */
128	frame = list_get_instance(cur, frame_t, buddy_link);	128	frame = list_get_instance(cur, frame_t, buddy_link);
129		129
130	/* get frame address */	130	/* get frame address */
131	v = FRAME2ADDR(zone, frame);	131	v = FRAME2ADDR(zone, frame);
132		132
133	if (flags & FRAME_KA)	133	if (flags & FRAME_KA)
134	v = PA2KA(v);	134	v = PA2KA(v);
135		135
136	spinlock_unlock(&zone->lock);	136	spinlock_unlock(&zone->lock);
137	spinlock_unlock(&zone_head_lock);	137	spinlock_unlock(&zone_head_lock);
138	interrupts_restore(ipl);	138	interrupts_restore(ipl);
139	return v;	139	return v;
140		140
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	ASSERT(addr % FRAME_SIZE == 0);	158	ASSERT(addr % FRAME_SIZE == 0);
159		159
160	ipl = interrupts_disable();	160	ipl = interrupts_disable();
161	spinlock_lock(&zone_head_lock);	161	spinlock_lock(&zone_head_lock);
162		162
163	/*	163	/*
164	* First, find host frame zone for addr.	164	* First, find host frame zone for addr.
165	*/	165	*/
166	for (cur = zone_head.next; cur != &zone_head; cur = cur->next) {	166	for (cur = zone_head.next; cur != &zone_head; cur = cur->next) {
167	z = list_get_instance(cur, zone_t, link);	167	z = list_get_instance(cur, zone_t, link);
168		168
169	spinlock_lock(&z->lock);	169	spinlock_lock(&z->lock);
170		170
171	if (IS_KA(addr))	171	if (IS_KA(addr))
172	addr = KA2PA(addr);	172	addr = KA2PA(addr);
173		173
174	/*	174	/*
175	* Check if addr belongs to z.	175	* Check if addr belongs to z.
176	*/	176	*/
177	if ((addr >= z->base) && (addr <= z->base + (z->free_count + z->busy_count) * FRAME_SIZE)) {	177	if ((addr >= z->base) && (addr <= z->base + (z->free_count + z->busy_count) * FRAME_SIZE)) {
178	zone = z;	178	zone = z;
179	break;	179	break;
180	}	180	}
181	spinlock_unlock(&z->lock);	181	spinlock_unlock(&z->lock);
182	}	182	}
183		183
184	ASSERT(zone != NULL);	184	ASSERT(zone != NULL);
185		185
186	frame = ADDR2FRAME(zone, addr);	186	frame = ADDR2FRAME(zone, addr);
187		187
188	ASSERT(frame->refcount);	188	ASSERT(frame->refcount);
189		189
190	if (!--frame->refcount) {	190	if (!--frame->refcount) {
191	buddy_system_free(zone->buddy_system, &frame->buddy_link);	191	buddy_system_free(zone->buddy_system, &frame->buddy_link);
192	}	192	}
193		193
194	spinlock_unlock(&zone->lock);	194	spinlock_unlock(&zone->lock);
195		195
196	spinlock_unlock(&zone_head_lock);	196	spinlock_unlock(&zone_head_lock);
197	interrupts_restore(ipl);	197	interrupts_restore(ipl);
198	}	198	}
199		199
200	/** Mark frame region not free.	200	/** Mark frame region not free.
201	*	201	*
202	* Mark frame region not free.	202	* Mark frame region not free.
203	*	203	*
204	* @param start First address.	204	* @param start First address.
205	* @param stop Last address.	205	* @param stop Last address.
206	*/	206	*/
207	void frame_region_not_free(__address base, size_t size)	207	void frame_region_not_free(__address base, size_t size)
208	{	208	{
209	count_t index;	209	count_t index;
210	index = zone_blacklist_count++;	210	index = zone_blacklist_count++;
211	ASSERT(base % FRAME_SIZE == 0);	211	ASSERT(base % FRAME_SIZE == 0);
212		212
213	if (size % FRAME_SIZE != 0) {	213	if (size % FRAME_SIZE != 0) {
214	size = size + (FRAME_SIZE - size % FRAME_SIZE);	214	size = size + (FRAME_SIZE - size % FRAME_SIZE);
215	}	215	}
216	ASSERT(size % FRAME_SIZE == 0);	216	ASSERT(size % FRAME_SIZE == 0);
217	ASSERT(zone_blacklist_count <= ZONE_BLACKLIST_SIZE);	217	ASSERT(zone_blacklist_count <= ZONE_BLACKLIST_SIZE);
218	zone_blacklist[index].base = base;	218	zone_blacklist[index].base = base;
219	zone_blacklist[index].size = size;	219	zone_blacklist[index].size = size;
220	}	220	}
221		221
222		222
223	/** Initialize zonekeeping	223	/** Initialize zonekeeping
224	*	224	*
225	* Initialize zonekeeping.	225	* Initialize zonekeeping.
226	*/	226	*/
227	void zone_init(void)	227	void zone_init(void)
228	{	228	{
229	spinlock_initialize(&zone_head_lock);	229	spinlock_initialize(&zone_head_lock);
230	list_initialize(&zone_head);	230	list_initialize(&zone_head);
231	}	231	}
232		232
233		233
234	void zone_create_in_region(__address base, size_t size) {	234	void zone_create_in_region(__address base, size_t size) {
235	int i;	235	int i;
236	zone_t * z;	236	zone_t * z;
237	__address s; size_t sz;	237	__address s; size_t sz;
238		238
239	ASSERT(base % FRAME_SIZE == 0);	239	ASSERT(base % FRAME_SIZE == 0);
240	ASSERT(size % FRAME_SIZE == 0);	240	ASSERT(size % FRAME_SIZE == 0);
241		241
242	if (!size) return;	242	if (!size) return;
243		243
244	for (i = 0; i < zone_blacklist_count; i++) {	244	for (i = 0; i < zone_blacklist_count; i++) {
245	if (zone_blacklist[i].base >= base && zone_blacklist[i].base < base + size) {	245	if (zone_blacklist[i].base >= base && zone_blacklist[i].base < base + size) {
246	s = base; sz = zone_blacklist[i].base - base;	246	s = base; sz = zone_blacklist[i].base - base;
247	ASSERT(base != s \|\| sz != size);	247	ASSERT(base != s \|\| sz != size);
248	zone_create_in_region(s, sz);	248	zone_create_in_region(s, sz);
249		249
250	s = zone_blacklist[i].base + zone_blacklist[i].size;	250	s = zone_blacklist[i].base + zone_blacklist[i].size;
251	sz = (base + size) - (zone_blacklist[i].base + zone_blacklist[i].size);	251	sz = (base + size) - (zone_blacklist[i].base + zone_blacklist[i].size);
252	ASSERT(base != s \|\| sz != size);	252	ASSERT(base != s \|\| sz != size);
253	zone_create_in_region(s, sz);	253	zone_create_in_region(s, sz);
254	return;	254	return;
255		255
256	}	256	}
257	}	257	}
258		258
259	z = zone_create(base, size, 0);	259	z = zone_create(base, size, 0);
260		260
261	if (!z) {	261	if (!z) {
262	panic("Cannot allocate zone (%dB).\n", size);	262	panic("Cannot allocate zone (%dB).\n", size);
263	}	263	}
264		264
265	zone_attach(z);	265	zone_attach(z);
266	}	266	}
267		267
268		268
269		269
270	/** Create frame zone	270	/** Create frame zone
271	*	271	*
272	* Create new frame zone.	272	* Create new frame zone.
273	*	273	*
274	* @param start Physical address of the first frame within the zone.	274	* @param start Physical address of the first frame within the zone.
275	* @param size Size of the zone. Must be a multiple of FRAME_SIZE.	275	* @param size Size of the zone. Must be a multiple of FRAME_SIZE.
276	* @param flags Zone flags.	276	* @param flags Zone flags.
277	*	277	*
278	* @return Initialized zone.	278	* @return Initialized zone.
279	*/	279	*/
280	zone_t * zone_create(__address start, size_t size, int flags)	280	zone_t * zone_create(__address start, size_t size, int flags)
281	{	281	{
282	zone_t *z;	282	zone_t *z;
283	count_t cnt;	283	count_t cnt;
284	int i;	284	int i;
285	__u8 max_order;	285	__u8 max_order;
286		286
287	/* hack for bug #10 */	287	/* hack for bug #10 */
288	// if (start == 0x100000) size -= (FRAME_SIZE * 256);	288	// if (start == 0x100000) size -= (FRAME_SIZE * 256);
289		289
290	// printf("ZONE_CREATE() %X - %X (%d kbytes) \n", start, start+size, size/1024);	290	// printf("ZONE_CREATE() %X - %X (%d kbytes) \n", start, start+size, size/1024);
291	ASSERT(start % FRAME_SIZE == 0);	291	ASSERT(start % FRAME_SIZE == 0);
292	ASSERT(size % FRAME_SIZE == 0);	292	ASSERT(size % FRAME_SIZE == 0);
293		293
294	cnt = size / FRAME_SIZE;	294	cnt = size / FRAME_SIZE;
295		295
296	z = (zone_t *) early_malloc(sizeof(zone_t));	296	z = (zone_t *) early_malloc(sizeof(zone_t));
297	if (z) {	297	if (z) {
298	link_initialize(&z->link);	298	link_initialize(&z->link);
299	spinlock_initialize(&z->lock);	299	spinlock_initialize(&z->lock);
300		300
301	z->base = start;	301	z->base = start;
302	z->flags = flags;	302	z->flags = flags;
303		303
304	z->free_count = cnt;	304	z->free_count = cnt;
305	list_initialize(&z->free_head);	305	list_initialize(&z->free_head);
306		306
307	z->busy_count = 0;	307	z->busy_count = 0;
308		308
309	z->frames = (frame_t ) early_malloc(cnt sizeof(frame_t));	309	z->frames = (frame_t ) early_malloc(cnt sizeof(frame_t));
310	if (!z->frames) {	310	if (!z->frames) {
311	early_free(z);	311	early_free(z);
312	return NULL;	312	return NULL;
313	}	313	}
314		314
315	for (i = 0; i<cnt; i++) {	315	for (i = 0; i<cnt; i++) {
316	frame_initialize(&z->frames[i], z);	316	frame_initialize(&z->frames[i], z);
317	list_append(&z->frames[i].link, &z->free_head);	317	list_append(&z->frames[i].link, &z->free_head);
318	}	318	}
319		319
320	/*	320	/*
321	* Create buddy system for the zone	321	* Create buddy system for the zone
322	*/	322	*/
323	for (max_order = 0; cnt >> max_order; max_order++);	323	for (max_order = 0; cnt >> max_order; max_order++);
324	z->buddy_system = buddy_system_create(max_order, &zone_buddy_system_operations, (void *) z);	324	z->buddy_system = buddy_system_create(max_order, &zone_buddy_system_operations, (void *) z);
325		325
326	/* Stuffing frames */	326	/* Stuffing frames */
327	for (i = 0; i<cnt; i++) {	327	for (i = 0; i<cnt; i++) {
328	z->frames[i].refcount = 0;	328	z->frames[i].refcount = 0;
329	buddy_system_free(z->buddy_system, &z->frames[i].buddy_link);	329	buddy_system_free(z->buddy_system, &z->frames[i].buddy_link);
330	}	330	}
331	}	331	}
332	return z;	332	return z;
333	}	333	}
334		334
335	/** Attach frame zone	335	/** Attach frame zone
336	*	336	*
337	* Attach frame zone to zone list.	337	* Attach frame zone to zone list.
338	*	338	*
339	* @param zone Zone to be attached.	339	* @param zone Zone to be attached.
340	*/	340	*/
341	void zone_attach(zone_t *zone)	341	void zone_attach(zone_t *zone)
342	{	342	{
343	ipl_t ipl;	343	ipl_t ipl;
344		344
345	ipl = interrupts_disable();	345	ipl = interrupts_disable();
346	spinlock_lock(&zone_head_lock);	346	spinlock_lock(&zone_head_lock);
347		347
348	list_append(&zone->link, &zone_head);	348	list_append(&zone->link, &zone_head);
349		349
350	spinlock_unlock(&zone_head_lock);	350	spinlock_unlock(&zone_head_lock);
351	interrupts_restore(ipl);	351	interrupts_restore(ipl);
352	}	352	}
353		353
354	/** Initialize frame structure	354	/** Initialize frame structure
355	*	355	*
356	* Initialize frame structure.	356	* Initialize frame structure.
357	*	357	*
358	* @param frame Frame structure to be initialized.	358	* @param frame Frame structure to be initialized.
359	* @param zone Host frame zone.	359	* @param zone Host frame zone.
360	*/	360	*/
361	void frame_initialize(frame_t frame, zone_t zone)	361	void frame_initialize(frame_t frame, zone_t zone)
362	{	362	{
363	frame->refcount = 1;	363	frame->refcount = 1;
364	frame->buddy_order = 0;	364	frame->buddy_order = 0;
365	link_initialize(&frame->link);	365	link_initialize(&frame->link);
366	}	366	}
367		367
368		368
369	/** Buddy system find_buddy implementation	369	/** Buddy system find_buddy implementation
370	*	370	*
371	* @param b Buddy system.	371	* @param b Buddy system.
372	* @param block Block for which buddy should be found	372	* @param block Block for which buddy should be found
373	*	373	*
374	* @return Buddy for given block if found	374	* @return Buddy for given block if found
375	*/	375	*/
376	link_t * zone_buddy_find_buddy(buddy_system_t b, link_t block) {	376	link_t * zone_buddy_find_buddy(buddy_system_t b, link_t block) {
377	frame_t * frame, * f;	377	frame_t * frame, * f;
378	zone_t * zone;	378	zone_t * zone;
379	link_t * cur;	379	link_t * cur;
380	count_t index;	380	count_t index;
381	bool is_left, is_right;	381	bool is_left, is_right;
382		382
383	frame = list_get_instance(block, frame_t, buddy_link);	383	frame = list_get_instance(block, frame_t, buddy_link);
384	zone = (zone_t *) b->data;	384	zone = (zone_t *) b->data;
385		385
386	/*	386	/*
387	* (FRAME_INDEX % 2^(ORDER+1)) == 0 ===> LEFT BUDDY	387	* (FRAME_INDEX % 2^(ORDER+1)) == 0 ===> LEFT BUDDY
388	* (FRAME_INDEX % 2^(ORDER+1)) == 2^(ORDER) ===> RIGHT BUDDY	388	* (FRAME_INDEX % 2^(ORDER+1)) == 2^(ORDER) ===> RIGHT BUDDY
389	*/	389	*/
390		390
391	is_left = IS_BUDDY_LEFT_BLOCK(zone, frame);	391	is_left = IS_BUDDY_LEFT_BLOCK(zone, frame);
392	is_right = IS_BUDDY_RIGHT_BLOCK(zone, frame);	392	is_right = IS_BUDDY_RIGHT_BLOCK(zone, frame);
393		393
394	ASSERT((is_left \|\| is_right) && (!is_left \|\| !is_right));	394	ASSERT((is_left \|\| is_right) && (!is_left \|\| !is_right));
395		395
396	/*	396	/*
397	* test left buddy	397	* test left buddy
398	*/	398	*/
399	if (is_left) {	399	if (is_left) {
400	index = (FRAME_INDEX(zone, frame)) + (1 << frame->buddy_order);	400	index = (FRAME_INDEX(zone, frame)) + (1 << frame->buddy_order);
401	} else if (is_right) {	401	} else if (is_right) {
402	index = (FRAME_INDEX(zone, frame)) - (1 << frame->buddy_order);	402	index = (FRAME_INDEX(zone, frame)) - (1 << frame->buddy_order);
403	}	403	}
404		404
405	if (FRAME_INDEX_VALID(zone, index)) {	405	if (FRAME_INDEX_VALID(zone, index)) {
406	if ( zone->frames[index].buddy_order == frame->buddy_order &&	406	if ( zone->frames[index].buddy_order == frame->buddy_order &&
407	zone->frames[index].refcount == 0) {	407	zone->frames[index].refcount == 0) {
408	return &zone->frames[index].buddy_link;	408	return &zone->frames[index].buddy_link;
409	}	409	}
410	}	410	}
411		411
412	return NULL;	412	return NULL;
413		413
414	}	414	}
415		415
416	/** Buddy system bisect implementation	416	/** Buddy system bisect implementation
417	*	417	*
418	* @param b Buddy system.	418	* @param b Buddy system.
419	* @param block Block to bisect	419	* @param block Block to bisect
420	*	420	*
421	* @return right block	421	* @return right block
422	*/	422	*/
423	link_t * zone_buddy_bisect(buddy_system_t b, link_t block) {	423	link_t * zone_buddy_bisect(buddy_system_t b, link_t block) {
424	frame_t * frame_l, * frame_r;	424	frame_t * frame_l, * frame_r;
425	frame_l = list_get_instance(block, frame_t, buddy_link);	425	frame_l = list_get_instance(block, frame_t, buddy_link);
426	frame_r = (frame_l + (1 << (frame_l->buddy_order - 1)));	426	frame_r = (frame_l + (1 << (frame_l->buddy_order - 1)));
427	return &frame_r->buddy_link;	427	return &frame_r->buddy_link;
428	}	428	}
429		429
430	/** Buddy system coalesce implementation	430	/** Buddy system coalesce implementation
431	*	431	*
432	* @param b Buddy system.	432	* @param b Buddy system.
433	* @param block_1 First block	433	* @param block_1 First block
434	* @param block_2 First block's buddy	434	* @param block_2 First block's buddy
435	*	435	*
436	* @return Coalesced block (actually block that represents lower address)	436	* @return Coalesced block (actually block that represents lower address)
437	*/	437	*/
438	link_t * zone_buddy_coalesce(buddy_system_t b, link_t block_1, link_t * block_2) {	438	link_t * zone_buddy_coalesce(buddy_system_t b, link_t block_1, link_t * block_2) {
439	frame_t * frame1, * frame2;	439	frame_t * frame1, * frame2;
440	frame1 = list_get_instance(block_1, frame_t, buddy_link);	440	frame1 = list_get_instance(block_1, frame_t, buddy_link);
441	frame2 = list_get_instance(block_2, frame_t, buddy_link);	441	frame2 = list_get_instance(block_2, frame_t, buddy_link);
442	return frame1 < frame2 ? block_1 : block_2;	442	return frame1 < frame2 ? block_1 : block_2;
443	}	443	}
444		444
445	/** Buddy system set_order implementation	445	/** Buddy system set_order implementation
446	*	446	*
447	* @param b Buddy system.	447	* @param b Buddy system.
448	* @param block Buddy system block	448	* @param block Buddy system block
449	* @param order Order to set	449	* @param order Order to set
450	*/	450	*/
451	void zone_buddy_set_order(buddy_system_t b, link_t block, __u8 order) {	451	void zone_buddy_set_order(buddy_system_t b, link_t block, __u8 order) {
452	frame_t * frame;	452	frame_t * frame;
453	frame = list_get_instance(block, frame_t, buddy_link);	453	frame = list_get_instance(block, frame_t, buddy_link);
454	frame->buddy_order = order;	454	frame->buddy_order = order;
455	}	455	}
456		456
457	/** Buddy system get_order implementation	457	/** Buddy system get_order implementation
458	*	458	*
459	* @param b Buddy system.	459	* @param b Buddy system.
460	* @param block Buddy system block	460	* @param block Buddy system block
461	*	461	*
462	* @return Order of block	462	* @return Order of block
463	*/	463	*/
464	__u8 zone_buddy_get_order(buddy_system_t b, link_t block) {	464	__u8 zone_buddy_get_order(buddy_system_t b, link_t block) {
465	frame_t * frame;	465	frame_t * frame;
466	frame = list_get_instance(block, frame_t, buddy_link);	466	frame = list_get_instance(block, frame_t, buddy_link);
467	return frame->buddy_order;	467	return frame->buddy_order;
468	}	468	}
469		469
470	/** Buddy system mark_busy implementation	470	/** Buddy system mark_busy implementation
471	*	471	*
472	* @param b Buddy system	472	* @param b Buddy system
473	* @param block Buddy system block	473	* @param block Buddy system block
474	*	474	*
475	*/	475	*/
476	void zone_buddy_mark_busy(buddy_system_t b, link_t block) {	476	void zone_buddy_mark_busy(buddy_system_t b, link_t block) {
477	frame_t * frame;	477	frame_t * frame;
478	frame = list_get_instance(block, frame_t, buddy_link);	478	frame = list_get_instance(block, frame_t, buddy_link);
479	frame->refcount = 1;	479	frame->refcount = 1;
480	}	480	}
481		481

Subversion Repositories HelenOS

(root)/branches/dynload/kernel/generic/src/mm/frame.c @ 4346 – Rev 533 → 534