WebSVN – HelenOS – Diff – /trunk/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>
#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_left;
 
 
   
    /*
     * 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 537	Rev 538
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(KA2PA(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 power-of-two frames of physical memory.	72	/** Allocate power-of-two frames of physical memory.
73	*	73	*
74	* @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.	75	* @param order Allocate exactly 2^order frames.
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 base Base address of non-available region.	204	* @param base Base address of non-available region.
205	* @param size Size of non-available region.	205	* @param size Size of non-available region.
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	index_t index;	209	index_t index;
210	index = zone_blacklist_count++;	210	index = zone_blacklist_count++;
211		211
212	/* Force base to the nearest lower address frame boundary. */	212	/* Force base to the nearest lower address frame boundary. */
213	base &= ~(FRAME_SIZE - 1);	213	base &= ~(FRAME_SIZE - 1);
214	/* Align size to frame boundary. */	214	/* Align size to frame boundary. */
215	size = ALIGN(size, FRAME_SIZE);	215	size = ALIGN(size, FRAME_SIZE);
216		216
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;	237	__address s;
238	size_t sz;	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)	243	if (!size)
244	return;	244	return;
245		245
246	for (i = 0; i < zone_blacklist_count; i++) {	246	for (i = 0; i < zone_blacklist_count; i++) {
247	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) {
248	s = base; sz = zone_blacklist[i].base - base;	248	s = base; sz = zone_blacklist[i].base - base;
249	ASSERT(base != s \|\| sz != size);	249	ASSERT(base != s \|\| sz != size);
250	zone_create_in_region(s, sz);	250	zone_create_in_region(s, sz);
251		251
252	s = zone_blacklist[i].base + zone_blacklist[i].size;	252	s = zone_blacklist[i].base + zone_blacklist[i].size;
253	sz = (base + size) - (zone_blacklist[i].base + zone_blacklist[i].size);	253	sz = (base + size) - (zone_blacklist[i].base + zone_blacklist[i].size);
254	ASSERT(base != s \|\| sz != size);	254	ASSERT(base != s \|\| sz != size);
255	zone_create_in_region(s, sz);	255	zone_create_in_region(s, sz);
256	return;	256	return;
257		257
258	}	258	}
259	}	259	}
260		260
261	z = zone_create(base, size, 0);	261	z = zone_create(base, size, 0);
262		262
263	if (!z) {	263	if (!z) {
264	panic("Cannot allocate zone (%dB).\n", size);	264	panic("Cannot allocate zone (%dB).\n", size);
265	}	265	}
266		266
267	zone_attach(z);	267	zone_attach(z);
268	}	268	}
269		269
270		270
271		271
272	/** Create frame zone	272	/** Create frame zone
273	*	273	*
274	* Create new frame zone.	274	* Create new frame zone.
275	*	275	*
276	* @param start Physical address of the first frame within the zone.	276	* @param start Physical address of the first frame within the zone.
277	* @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.
278	* @param flags Zone flags.	278	* @param flags Zone flags.
279	*	279	*
280	* @return Initialized zone.	280	* @return Initialized zone.
281	*/	281	*/
282	zone_t * zone_create(__address start, size_t size, int flags)	282	zone_t * zone_create(__address start, size_t size, int flags)
283	{	283	{
284	zone_t *z;	284	zone_t *z;
285	count_t cnt;	285	count_t cnt;
286	int i;	286	int i;
287	__u8 max_order;	287	__u8 max_order;
288		288
289	/* hack for bug #10 */	289	/* hack for bug #10 */
290	// if (start == 0x100000) size -= (FRAME_SIZE * 256);	290	// if (start == 0x100000) size -= (FRAME_SIZE * 256);
291		291
292	// 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);
293	ASSERT(start % FRAME_SIZE == 0);	293	ASSERT(start % FRAME_SIZE == 0);
294	ASSERT(size % FRAME_SIZE == 0);	294	ASSERT(size % FRAME_SIZE == 0);
295		295
296	cnt = size / FRAME_SIZE;	296	cnt = size / FRAME_SIZE;
297		297
298	z = (zone_t *) early_malloc(sizeof(zone_t));	298	z = (zone_t *) early_malloc(sizeof(zone_t));
299	if (z) {	299	if (z) {
300	link_initialize(&z->link);	300	link_initialize(&z->link);
301	spinlock_initialize(&z->lock);	301	spinlock_initialize(&z->lock);
302		302
303	z->base = start;	303	z->base = start;
304	z->flags = flags;	304	z->flags = flags;
305		305
306	z->free_count = cnt;	306	z->free_count = cnt;
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	}	317	}
318		318
319	/*	319	/*
320	* Create buddy system for the zone	320	* Create buddy system for the zone
321	*/	321	*/
322	for (max_order = 0; cnt >> max_order; max_order++)	322	for (max_order = 0; cnt >> max_order; max_order++)
323	;	323	;
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	}	365	}
366		366
367		367
368	/** Buddy system find_buddy implementation	368	/** Buddy system find_buddy implementation
369	*	369	*
370	* @param b Buddy system.	370	* @param b Buddy system.
371	* @param block Block for which buddy should be found	371	* @param block Block for which buddy should be found
372	*	372	*
373	* @return Buddy for given block if found	373	* @return Buddy for given block if found
374	*/	374	*/
375	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) {
376	frame_t * frame, * f;	376	frame_t * frame, * f;
377	zone_t * zone;	377	zone_t * zone;
378	link_t * cur;	378	link_t * cur;
379	count_t index;	379	count_t index;
380	bool is_left, is_right;	380	bool is_left, is_right;
381		381
382	frame = list_get_instance(block, frame_t, buddy_link);	382	frame = list_get_instance(block, frame_t, buddy_link);
383	zone = (zone_t *) b->data;	383	zone = (zone_t *) b->data;
384		384
385	/*	385	/*
386	* (FRAME_INDEX % 2^(ORDER+1)) == 0 ===> LEFT BUDDY	386	* (FRAME_INDEX % 2^(ORDER+1)) == 0 ===> LEFT BUDDY
387	* (FRAME_INDEX % 2^(ORDER+1)) == 2^(ORDER) ===> RIGHT BUDDY	387	* (FRAME_INDEX % 2^(ORDER+1)) == 2^(ORDER) ===> RIGHT BUDDY
388	*/	388	*/
389		389
390	is_left = IS_BUDDY_LEFT_BLOCK(zone, frame);	390	is_left = IS_BUDDY_LEFT_BLOCK(zone, frame);
391	is_right = IS_BUDDY_RIGHT_BLOCK(zone, frame);	391	is_right = !is_left;
392		-
393	ASSERT((is_left \|\| is_right) && (!is_left \|\| !is_right));	-
394		392
395	/*	393	/*
396	* test left buddy	394	* test left buddy
397	*/	395	*/
398	if (is_left) {	396	if (is_left) {
399	index = (FRAME_INDEX(zone, frame)) + (1 << frame->buddy_order);	397	index = (FRAME_INDEX(zone, frame)) + (1 << frame->buddy_order);
400	} else if (is_right) {	398	} else if (is_right) {
401	index = (FRAME_INDEX(zone, frame)) - (1 << frame->buddy_order);	399	index = (FRAME_INDEX(zone, frame)) - (1 << frame->buddy_order);
402	}	400	}
403		401
404	if (FRAME_INDEX_VALID(zone, index)) {	402	if (FRAME_INDEX_VALID(zone, index)) {
405	if ( zone->frames[index].buddy_order == frame->buddy_order &&	403	if ( zone->frames[index].buddy_order == frame->buddy_order &&
406	zone->frames[index].refcount == 0) {	404	zone->frames[index].refcount == 0) {
407	return &zone->frames[index].buddy_link;	405	return &zone->frames[index].buddy_link;
408	}	406	}
409	}	407	}
410		408
411	return NULL;	409	return NULL;
412		410
413	}	411	}
414		412
415	/** Buddy system bisect implementation	413	/** Buddy system bisect implementation
416	*	414	*
417	* @param b Buddy system.	415	* @param b Buddy system.
418	* @param block Block to bisect	416	* @param block Block to bisect
419	*	417	*
420	* @return right block	418	* @return right block
421	*/	419	*/
422	link_t * zone_buddy_bisect(buddy_system_t b, link_t block) {	420	link_t * zone_buddy_bisect(buddy_system_t b, link_t block) {
423	frame_t * frame_l, * frame_r;	421	frame_t * frame_l, * frame_r;
424	frame_l = list_get_instance(block, frame_t, buddy_link);	422	frame_l = list_get_instance(block, frame_t, buddy_link);
425	frame_r = (frame_l + (1 << (frame_l->buddy_order - 1)));	423	frame_r = (frame_l + (1 << (frame_l->buddy_order - 1)));
426	return &frame_r->buddy_link;	424	return &frame_r->buddy_link;
427	}	425	}
428		426
429	/** Buddy system coalesce implementation	427	/** Buddy system coalesce implementation
430	*	428	*
431	* @param b Buddy system.	429	* @param b Buddy system.
432	* @param block_1 First block	430	* @param block_1 First block
433	* @param block_2 First block's buddy	431	* @param block_2 First block's buddy
434	*	432	*
435	* @return Coalesced block (actually block that represents lower address)	433	* @return Coalesced block (actually block that represents lower address)
436	*/	434	*/
437	link_t * zone_buddy_coalesce(buddy_system_t b, link_t block_1, link_t * block_2) {	435	link_t * zone_buddy_coalesce(buddy_system_t b, link_t block_1, link_t * block_2) {
438	frame_t * frame1, * frame2;	436	frame_t * frame1, * frame2;
439	frame1 = list_get_instance(block_1, frame_t, buddy_link);	437	frame1 = list_get_instance(block_1, frame_t, buddy_link);
440	frame2 = list_get_instance(block_2, frame_t, buddy_link);	438	frame2 = list_get_instance(block_2, frame_t, buddy_link);
441	return frame1 < frame2 ? block_1 : block_2;	439	return frame1 < frame2 ? block_1 : block_2;
442	}	440	}
443		441
444	/** Buddy system set_order implementation	442	/** Buddy system set_order implementation
445	*	443	*
446	* @param b Buddy system.	444	* @param b Buddy system.
447	* @param block Buddy system block	445	* @param block Buddy system block
448	* @param order Order to set	446	* @param order Order to set
449	*/	447	*/
450	void zone_buddy_set_order(buddy_system_t b, link_t block, __u8 order) {	448	void zone_buddy_set_order(buddy_system_t b, link_t block, __u8 order) {
451	frame_t * frame;	449	frame_t * frame;
452	frame = list_get_instance(block, frame_t, buddy_link);	450	frame = list_get_instance(block, frame_t, buddy_link);
453	frame->buddy_order = order;	451	frame->buddy_order = order;
454	}	452	}
455		453
456	/** Buddy system get_order implementation	454	/** Buddy system get_order implementation
457	*	455	*
458	* @param b Buddy system.	456	* @param b Buddy system.
459	* @param block Buddy system block	457	* @param block Buddy system block
460	*	458	*
461	* @return Order of block	459	* @return Order of block
462	*/	460	*/
463	__u8 zone_buddy_get_order(buddy_system_t b, link_t block) {	461	__u8 zone_buddy_get_order(buddy_system_t b, link_t block) {
464	frame_t * frame;	462	frame_t * frame;
465	frame = list_get_instance(block, frame_t, buddy_link);	463	frame = list_get_instance(block, frame_t, buddy_link);
466	return frame->buddy_order;	464	return frame->buddy_order;
467	}	465	}
468		466
469	/** Buddy system mark_busy implementation	467	/** Buddy system mark_busy implementation
470	*	468	*
471	* @param b Buddy system	469	* @param b Buddy system
472	* @param block Buddy system block	470	* @param block Buddy system block
473	*	471	*
474	*/	472	*/
475	void zone_buddy_mark_busy(buddy_system_t b, link_t block) {	473	void zone_buddy_mark_busy(buddy_system_t b, link_t block) {
476	frame_t * frame;	474	frame_t * frame;
477	frame = list_get_instance(block, frame_t, buddy_link);	475	frame = list_get_instance(block, frame_t, buddy_link);
478	frame->refcount = 1;	476	frame->refcount = 1;
479	}	477	}
480		478

Subversion Repositories HelenOS

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