WebSVN – HelenOS – Diff – /trunk/kernel/generic/src/mm/buddy.c


/*
 * Copyright (C) 2005 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 <mm/buddy.h>
#include <mm/frame.h>
#include <mm/heap.h>
#include <arch/types.h>
#include <typedefs.h>
#include <list.h>
#include <debug.h>
 
/** Create buddy system
 *
 * Allocate memory for and initialize new buddy system.
 *
 * @param max_order The biggest allocable size will be 2^max_order.
 * @param op Operations for new buddy system.
 *
 * @return New buddy system.
 */
buddy_system_t *buddy_system_create(__u8 max_order, buddy_operations_t *op)
{
    buddy_system_t *b;
    int i;
 
    ASSERT(max_order < BUDDY_SYSTEM_INNER_BLOCK);
 
    ASSERT(op->find_buddy);
    ASSERT(op->set_order);
    ASSERT(op->get_order);
    ASSERT(op->bisect);
    ASSERT(op->coalesce);
 
    /*
     * Allocate memory for structure describing the whole buddy system.
     */
    b = (buddy_system_t *) early_malloc(sizeof(buddy_system_t));
   
    if (b) {
        /*
         * Allocate memory for all orders this buddy system will work with.
         */
        b->order = (link_t *) early_malloc(max_order * sizeof(link_t));
        if (!b->order) {
            early_free(b);
            return NULL;
        }
   
        for (i = 0; i < max_order; i++)
            list_initialize(&b->order[i]);
   
        b->max_order = max_order;
        b->op = op;
    }
   
    return b;
}
 
/** Allocate block from buddy system.
 *
 * Allocate block from buddy system.
 *
 * @param b Buddy system pointer.
 * @param i Returned block will be 2^i big.
 *
 * @return Block of data represented by link_t.
 */
link_t *buddy_system_alloc(buddy_system_t *b, __u8 i)
{
    link_t *res, *hlp;
 
    ASSERT(i < b->max_order);
 
    /*
     * If the list of order i is not empty,
     * the request can be immediatelly satisfied.
     */
    if (!list_empty(&b->order[i])) {
        res = b->order[i].next;
        list_remove(res);
        return res;
    }
   
    /*
     * If order i is already the maximal order,
     * the request cannot be satisfied.
     */
    if (i == b->max_order - 1)
        return NULL;
 
    /*
     * Try to recursively satisfy the request from higher order lists.
     */
    hlp = buddy_system_alloc(b, i + 1);
   
    /*
     * The request could not be satisfied
     * from higher order lists.
     */
    if (!hlp)
        return NULL;
       
    res = hlp;
   
    /*
     * Bisect the block and set order of both of its parts to i.
     */
    hlp = b->op->bisect(res);
    b->op->set_order(res, i);
    b->op->set_order(hlp, i);
   
    /*
     * Return the other half to buddy system.
     */
    buddy_system_free(b, hlp);
   
    return res;
   
}
 
/** Return block to buddy system.
 *
 * Return block to buddy system.
 *
 * @param b Buddy system pointer.
 * @param block Block to return.
 */
void buddy_system_free(buddy_system_t *b, link_t *block)
{
    link_t *buddy, *hlp;
    __u8 i;
   
    /*
     * Determine block's order.
     */
    i = b->op->get_order(block);
 
    ASSERT(i < b->max_order);
 
    /*
     * See if there is any buddy in the list of order i.
     */
    buddy = b->op->find_buddy(block);
   
    if (buddy && i != b->max_order - 1) {
 
        ASSERT(b->op->get_order(buddy) == i);
       
        /*
         * Remove buddy from the list of order i.
         */
        list_remove(buddy);
       
        /*
         * Invalidate order of both block and buddy.
         */
        b->op->set_order(block, BUDDY_SYSTEM_INNER_BLOCK);
        b->op->set_order(buddy, BUDDY_SYSTEM_INNER_BLOCK);
       
        /*
         * Coalesce block and buddy into one block.
         */
        hlp = b->op->coalesce(block, buddy);
 
        /*
         * Set order of the coalesced block to i + 1.
         */
        b->op->set_order(hlp, i + 1);
 
        /*
         * Recursively add the coalesced block to the list of order i + 1.
         */
        buddy_system_free(b, hlp);
    }
    else {
        /*
         * Insert block into the list of order i.
         */
        list_append(block, &b->order[i]);
    }
 
}
 

Rev 377	Rev 378
1	/*	1	/*
2	* Copyright (C) 2005 Jakub Jermar	2	* Copyright (C) 2005 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 <mm/buddy.h>	29	#include <mm/buddy.h>
30	#include <mm/frame.h>	30	#include <mm/frame.h>
31	#include <mm/heap.h>	31	#include <mm/heap.h>
32	#include <arch/types.h>	32	#include <arch/types.h>
33	#include <typedefs.h>	33	#include <typedefs.h>
34	#include <list.h>	34	#include <list.h>
35	#include <debug.h>	35	#include <debug.h>
36		36
37	/** Create buddy system	37	/** Create buddy system
38	*	38	*
39	* Allocate memory for and initialize new buddy system.	39	* Allocate memory for and initialize new buddy system.
40	*	40	*
41	* @param max_order The biggest allocable size will be 2^max_order.	41	* @param max_order The biggest allocable size will be 2^max_order.
42	* @param op Operations for new buddy system.	42	* @param op Operations for new buddy system.
43	*	43	*
44	* @return New buddy system.	44	* @return New buddy system.
45	*/	45	*/
46	buddy_system_t buddy_system_create(__u8 max_order, buddy_operations_t op)	46	buddy_system_t buddy_system_create(__u8 max_order, buddy_operations_t op)
47	{	47	{
48	buddy_system_t *b;	48	buddy_system_t *b;
49	int i;	49	int i;
50		50
-		51	ASSERT(max_order < BUDDY_SYSTEM_INNER_BLOCK);
-		52
51	ASSERT(op->find_buddy);	53	ASSERT(op->find_buddy);
52	ASSERT(op->set_order);	54	ASSERT(op->set_order);
53	ASSERT(op->get_order);	55	ASSERT(op->get_order);
54	ASSERT(op->bisect);	56	ASSERT(op->bisect);
55	ASSERT(op->coalesce);	57	ASSERT(op->coalesce);
56		58
57	/*	59	/*
58	* Allocate memory for structure describing the whole buddy system.	60	* Allocate memory for structure describing the whole buddy system.
59	*/	61	*/
60	b = (buddy_system_t *) early_malloc(sizeof(buddy_system_t));	62	b = (buddy_system_t *) early_malloc(sizeof(buddy_system_t));
61		63
62	if (b) {	64	if (b) {
63	/*	65	/*
64	* Allocate memory for all orders this buddy system will work with.	66	* Allocate memory for all orders this buddy system will work with.
65	*/	67	*/
66	b->order = (link_t ) early_malloc(max_order sizeof(link_t));	68	b->order = (link_t ) early_malloc(max_order sizeof(link_t));
67	if (!b->order) {	69	if (!b->order) {
68	early_free(b);	70	early_free(b);
69	return NULL;	71	return NULL;
70	}	72	}
71		73
72	for (i = 0; i < max_order; i++)	74	for (i = 0; i < max_order; i++)
73	list_initialize(&b->order[i]);	75	list_initialize(&b->order[i]);
74		76
75	b->max_order = max_order;	77	b->max_order = max_order;
76	b->op = op;	78	b->op = op;
77	}	79	}
78		80
79	return b;	81	return b;
80	}	82	}
81		83
82	/** Allocate block from buddy system.	84	/** Allocate block from buddy system.
83	*	85	*
84	* Allocate block from buddy system.	86	* Allocate block from buddy system.
85	*	87	*
86	* @param b Buddy system pointer.	88	* @param b Buddy system pointer.
87	* @param i Returned block will be 2^i big.	89	* @param i Returned block will be 2^i big.
88	*	90	*
89	* @return Block of data represented by link_t.	91	* @return Block of data represented by link_t.
90	*/	92	*/
91	link_t buddy_system_alloc(buddy_system_t b, __u8 i)	93	link_t buddy_system_alloc(buddy_system_t b, __u8 i)
92	{	94	{
93	link_t res, hlp;	95	link_t res, hlp;
94		96
95	ASSERT(i < b->max_order);	97	ASSERT(i < b->max_order);
96		98
97	/*	99	/*
98	* If the list of order i is not empty,	100	* If the list of order i is not empty,
99	* the request can be immediatelly satisfied.	101	* the request can be immediatelly satisfied.
100	*/	102	*/
101	if (!list_empty(&b->order[i])) {	103	if (!list_empty(&b->order[i])) {
102	res = b->order[i].next;	104	res = b->order[i].next;
103	list_remove(res);	105	list_remove(res);
104	return res;	106	return res;
105	}	107	}
106		108
107	/*	109	/*
108	* If order i is already the maximal order,	110	* If order i is already the maximal order,
109	* the request cannot be satisfied.	111	* the request cannot be satisfied.
110	*/	112	*/
111	if (i == b->max_order - 1)	113	if (i == b->max_order - 1)
112	return NULL;	114	return NULL;
113		115
114	/*	116	/*
115	* Try to recursively satisfy the request from higher order lists.	117	* Try to recursively satisfy the request from higher order lists.
116	*/	118	*/
117	hlp = buddy_system_alloc(b, i + 1);	119	hlp = buddy_system_alloc(b, i + 1);
118		120
119	/*	121	/*
120	* The request could not be satisfied	122	* The request could not be satisfied
121	* from higher order lists.	123	* from higher order lists.
122	*/	124	*/
123	if (!hlp)	125	if (!hlp)
124	return NULL;	126	return NULL;
125		127
126	res = hlp;	128	res = hlp;
127		129
128	/*	130	/*
129	* Bisect the block and set order of both of its parts to i.	131	* Bisect the block and set order of both of its parts to i.
130	*/	132	*/
131	hlp = b->op->bisect(res);	133	hlp = b->op->bisect(res);
132	b->op->set_order(res, i);	134	b->op->set_order(res, i);
133	b->op->set_order(hlp, i);	135	b->op->set_order(hlp, i);
134		136
135	/*	137	/*
136	* Return the other half to buddy system.	138	* Return the other half to buddy system.
137	*/	139	*/
138	buddy_system_free(b, hlp);	140	buddy_system_free(b, hlp);
139		141
140	return res;	142	return res;
141		143
142	}	144	}
143		145
144	/** Return block to buddy system.	146	/** Return block to buddy system.
145	*	147	*
146	* Return block to buddy system.	148	* Return block to buddy system.
147	*	149	*
148	* @param b Buddy system pointer.	150	* @param b Buddy system pointer.
149	* @param block Block to return.	151	* @param block Block to return.
150	*/	152	*/
151	void buddy_system_free(buddy_system_t b, link_t block)	153	void buddy_system_free(buddy_system_t b, link_t block)
152	{	154	{
153	link_t buddy, hlp;	155	link_t buddy, hlp;
154	__u8 i;	156	__u8 i;
155		157
156	/*	158	/*
157	* Determine block's order.	159	* Determine block's order.
158	*/	160	*/
159	i = b->op->get_order(block);	161	i = b->op->get_order(block);
160		162
161	ASSERT(i < b->max_order);	163	ASSERT(i < b->max_order);
162		164
163	/*	165	/*
164	* See if there is any buddy in the list of order i.	166	* See if there is any buddy in the list of order i.
165	*/	167	*/
166	buddy = b->op->find_buddy(block);	168	buddy = b->op->find_buddy(block);
167		169
168	if (buddy && i != b->max_order - 1) {	170	if (buddy && i != b->max_order - 1) {
-		171
-		172	ASSERT(b->op->get_order(buddy) == i);
-		173
169	/*	174	/*
170	* Remove buddy from the list of order i.	175	* Remove buddy from the list of order i.
171	*/	176	*/
172	list_remove(buddy);	177	list_remove(buddy);
173		178
-		179	/*
-		180	* Invalidate order of both block and buddy.
-		181	*/
-		182	b->op->set_order(block, BUDDY_SYSTEM_INNER_BLOCK);
-		183	b->op->set_order(buddy, BUDDY_SYSTEM_INNER_BLOCK);
-		184
174	/*	185	/*
175	* Coalesce block and buddy into one block.	186	* Coalesce block and buddy into one block.
176	*/	187	*/
177	hlp = b->op->coalesce(block, buddy);	188	hlp = b->op->coalesce(block, buddy);
178		189
179	/*	190	/*
180	* Set order of the coalesced block to i + 1.	191	* Set order of the coalesced block to i + 1.
181	*/	192	*/
182	b->op->set_order(hlp, i + 1);	193	b->op->set_order(hlp, i + 1);
183		194
184	/*	195	/*
185	* Recursively add the coalesced block to the list of order i + 1.	196	* Recursively add the coalesced block to the list of order i + 1.
186	*/	197	*/
187	buddy_system_free(b, hlp);	198	buddy_system_free(b, hlp);
188	}	199	}
189	else {	200	else {
190	/*	201	/*
191	* Insert block into the list of order i.	202	* Insert block into the list of order i.
192	*/	203	*/
193	list_append(block, &b->order[i]);	204	list_append(block, &b->order[i]);
194	}	205	}
195		206
196	}	207	}
197		208

Subversion Repositories HelenOS

(root)/trunk/kernel/generic/src/mm/buddy.c @ 2071 – Rev 377 → 378