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>
#include <print.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.
 * @param data Pointer to be used by implementation.
 *
 * @return New buddy system.
 */
buddy_system_t *buddy_system_create(__u8 max_order, buddy_system_operations_t *op, void *data)
{
    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);
    ASSERT(op->mark_busy);
 
    /*
     * 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;
        b->data = data;
    }
   
    return b;
}
 
/** Check if buddy system can allocate block
 *
 * @param b Buddy system pointer
 * @param i Size of the block (2^i)
 *
 * @return True if block can be allocated
 */
bool buddy_system_can_alloc(buddy_system_t *b, __u8 i) {
    __u8 k;
   
    ASSERT(i < b->max_order);
   
    for (k=i; k < b->max_order; k++) {
        if (!list_empty(&b->order[k])) {
            return true;
        }
    }
   
    return false;
   
}
 
/** 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);
        b->op->mark_busy(b, 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(b, res);
    b->op->set_order(b, res, i);
    b->op->set_order(b, hlp, i);
   
    /*
     * Return the other half to buddy system.
     * PROBLEM!!!! FILL FIND OTHER PART AS BUDDY AND LINK TOGETHER
     */
    b->op->mark_busy(b, res);
    buddy_system_free(b, hlp);
   
    return res;
   
}
 
/** 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(b, block);
 
    ASSERT(i < b->max_order);
 
    if (i != b->max_order - 1) {
        /*
         * See if there is any buddy in the list of order i.
         */
        buddy = b->op->find_buddy(b, block);
        if (buddy) {
 
            ASSERT(b->op->get_order(b, buddy) == i);
 
            /*
             * Remove buddy from the list of order i.
             */
            list_remove(buddy);
       
            /*
             * Invalidate order of both block and buddy.
             */
            b->op->set_order(b, block, BUDDY_SYSTEM_INNER_BLOCK);
            b->op->set_order(b, buddy, BUDDY_SYSTEM_INNER_BLOCK);
       
            /*
             * Coalesce block and buddy into one block.
             */
            hlp = b->op->coalesce(b, block, buddy);
 
            /*
             * Set order of the coalesced block to i + 1.
             */
            b->op->set_order(b, hlp, i + 1);
 
            /*
             * Recursively add the coalesced block to the list of order i + 1.
             */
            buddy_system_free(b, hlp);
            return;
        }
    }
 
    /*
     * Insert block into the list of order i.
     */
    list_append(block, &b->order[i]);
 
}
 

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

Subversion Repositories HelenOS

(root)/trunk/kernel/generic/src/mm/buddy.c @ 3422 – Rev 532 → 533