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

Subversion Repositories HelenOS-historic

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