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

Subversion Repositories HelenOS-historic

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