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

Subversion Repositories HelenOS-historic

(root)/kernel/trunk/generic/src/mm/frame.c – Rev 536 → 537