WebSVN – HelenOS-historic – Diff – /kernel/trunk/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 <arch/types.h>
#include <typedefs.h>
#include <adt/list.h>
#include <debug.h>
#include <print.h>
 
/** Return size needed for the buddy configuration data */
size_t buddy_conf_size(int max_order)
{
    return sizeof(buddy_system_t) + (max_order + 1) * sizeof(link_t);
}
 
 
/** Create buddy system
 *
 * Allocate memory for and initialize new buddy system.
 *
 * @param b Preallocated buddy system control data
 * @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.
 */
void buddy_system_create(buddy_system_t *b,
             __u8 max_order,
             buddy_system_operations_t *op,
             void *data)
{
    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);
 
    /*
     * Use memory after our own structure
     */
    b->order = (link_t *) (&b[1]);
   
    for (i = 0; i <= max_order; i++)
        list_initialize(&b->order[i]);
 
    b->max_order = max_order;
    b->op = op;
    b->data = data;
}
 
/** 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;
   
    /*
     * If requested block is greater then maximal block
     * we know immediatly that we cannot satisfy the request.
     */
    if (i > b->max_order) return false;
 
    /*
     * Check if any bigger or equal order has free elements
     */
    for (k=i; k <= b->max_order; k++) {
        if (!list_empty(&b->order[k])) {
            return true;
        }
    }
   
    return false;
   
}
 
/** Allocate PARTICULAR block from buddy system
 *
 * @ return Block of data or NULL if no such block was found
 */
link_t *buddy_system_alloc_block(buddy_system_t *b, link_t *block)
{
    link_t *left,*right, *tmp;
    __u8 order;
 
    left = b->op->find_block(b, block, BUDDY_SYSTEM_INNER_BLOCK);
    ASSERT(left);
    list_remove(left);
    while (1) {
        if (! b->op->get_order(b,left)) {
            b->op->mark_busy(b, left);
            return left;
        }
       
        order = b->op->get_order(b, left);
 
        right = b->op->bisect(b, left);
        b->op->set_order(b, left, order-1);
        b->op->set_order(b, right, order-1);
 
        tmp = b->op->find_block(b, block, BUDDY_SYSTEM_INNER_BLOCK);
 
        if (tmp == right) {
            right = left;
            left = tmp;
        }
        ASSERT(tmp == left);
        b->op->mark_busy(b, left);
        buddy_system_free(b, right);
        b->op->mark_available(b, left);
    }
}
 
/** 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)
        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. Mark the first part
     * full, so that it won't coalesce again.
     */
    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) {
        /*
         * 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]);
 
}
 
/** Prints out structure of buddy system
 *
 * @param b Pointer to buddy system
 * @param es Element size
 */
void buddy_system_structure_print(buddy_system_t *b, size_t elem_size) {
    index_t i;
    count_t cnt, elem_count = 0, block_count = 0;
    link_t * cur;
   
 
    printf("Order\tBlocks\tSize    \tBlock size\tElems per block\n");
    printf("-----\t------\t--------\t----------\t---------------\n");
   
    for (i=0;i <= b->max_order; i++) {
        cnt = 0;
        if (!list_empty(&b->order[i])) {
            for (cur = b->order[i].next; cur != &b->order[i]; cur = cur->next)
                cnt++;
        }
   
        printf("#%d\t%d\t%dK\t\t%dK\t\t%d\t", i, cnt, (cnt * (1 << i) * elem_size) >> 10, ((1 << i) * elem_size) >> 10, 1 << i);
        if (!list_empty(&b->order[i])) {
            for (cur = b->order[i].next; cur != &b->order[i]; cur = cur->next) {
                b->op->print_id(b, cur);
                printf(" ");
            }
        }
        printf("\n");
           
        block_count += cnt;
        elem_count += (1 << i) * cnt;
    }
    printf("-----\t------\t--------\t----------\t---------------\n");
    printf("Buddy system contains %d free elements (%d blocks)\n" , elem_count, block_count);
 
}
 

Rev 815	Rev 822
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 <arch/types.h>	31	#include <arch/types.h>
32	#include <typedefs.h>	32	#include <typedefs.h>
33	#include <adt/list.h>	33	#include <adt/list.h>
34	#include <debug.h>	34	#include <debug.h>
35	#include <print.h>	35	#include <print.h>
36		36
37	/** Return size needed for the buddy configuration data */	37	/** Return size needed for the buddy configuration data */
38	size_t buddy_conf_size(int max_order)	38	size_t buddy_conf_size(int max_order)
39	{	39	{
40	return sizeof(buddy_system_t) + (max_order + 1) * sizeof(link_t);	40	return sizeof(buddy_system_t) + (max_order + 1) * sizeof(link_t);
41	}	41	}
42		42
43		43
44	/** Create buddy system	44	/** Create buddy system
45	*	45	*
46	* Allocate memory for and initialize new buddy system.	46	* Allocate memory for and initialize new buddy system.
47	*	47	*
48	* @param b Preallocated buddy system control data	48	* @param b Preallocated buddy system control data
49	* @param max_order The biggest allocable size will be 2^max_order.	49	* @param max_order The biggest allocable size will be 2^max_order.
50	* @param op Operations for new buddy system.	50	* @param op Operations for new buddy system.
51	* @param data Pointer to be used by implementation.	51	* @param data Pointer to be used by implementation.
52	*	52	*
53	* @return New buddy system.	53	* @return New buddy system.
54	*/	54	*/
55	void buddy_system_create(buddy_system_t *b,	55	void buddy_system_create(buddy_system_t *b,
56	__u8 max_order,	56	__u8 max_order,
57	buddy_system_operations_t *op,	57	buddy_system_operations_t *op,
58	void *data)	58	void *data)
59	{	59	{
60	int i;	60	int i;
61		61
62	ASSERT(max_order < BUDDY_SYSTEM_INNER_BLOCK);	62	ASSERT(max_order < BUDDY_SYSTEM_INNER_BLOCK);
63		63
64	ASSERT(op->find_buddy);	64	ASSERT(op->find_buddy);
65	ASSERT(op->set_order);	65	ASSERT(op->set_order);
66	ASSERT(op->get_order);	66	ASSERT(op->get_order);
67	ASSERT(op->bisect);	67	ASSERT(op->bisect);
68	ASSERT(op->coalesce);	68	ASSERT(op->coalesce);
69	ASSERT(op->mark_busy);	69	ASSERT(op->mark_busy);
70		70
71	/*	71	/*
72	* Use memory after our own structure	72	* Use memory after our own structure
73	*/	73	*/
74	b->order = (link_t *) (&b[1]);	74	b->order = (link_t *) (&b[1]);
75		75
76	for (i = 0; i <= max_order; i++)	76	for (i = 0; i <= max_order; i++)
77	list_initialize(&b->order[i]);	77	list_initialize(&b->order[i]);
78		78
79	b->max_order = max_order;	79	b->max_order = max_order;
80	b->op = op;	80	b->op = op;
81	b->data = data;	81	b->data = data;
82	}	82	}
83		83
84	/** Check if buddy system can allocate block	84	/** Check if buddy system can allocate block
85	*	85	*
86	* @param b Buddy system pointer	86	* @param b Buddy system pointer
87	* @param i Size of the block (2^i)	87	* @param i Size of the block (2^i)
88	*	88	*
89	* @return True if block can be allocated	89	* @return True if block can be allocated
90	*/	90	*/
91	bool buddy_system_can_alloc(buddy_system_t *b, __u8 i) {	91	bool buddy_system_can_alloc(buddy_system_t *b, __u8 i) {
92	__u8 k;	92	__u8 k;
93		93
94	/*	94	/*
95	* If requested block is greater then maximal block	95	* If requested block is greater then maximal block
96	* we know immediatly that we cannot satisfy the request.	96	* we know immediatly that we cannot satisfy the request.
97	*/	97	*/
98	if (i > b->max_order) return false;	98	if (i > b->max_order) return false;
99		99
100	/*	100	/*
101	* Check if any bigger or equal order has free elements	101	* Check if any bigger or equal order has free elements
102	*/	102	*/
103	for (k=i; k <= b->max_order; k++) {	103	for (k=i; k <= b->max_order; k++) {
104	if (!list_empty(&b->order[k])) {	104	if (!list_empty(&b->order[k])) {
105	return true;	105	return true;
106	}	106	}
107	}	107	}
108		108
109	return false;	109	return false;
110		110
111	}	111	}
112		112
113	/** Allocate PARTICULAR block from buddy system	113	/** Allocate PARTICULAR block from buddy system
114	*	114	*
115	* @ return Block of data or NULL if no such block was found	115	* @ return Block of data or NULL if no such block was found
116	*/	116	*/
117	link_t buddy_system_alloc_block(buddy_system_t b, link_t *block)	117	link_t buddy_system_alloc_block(buddy_system_t b, link_t *block)
118	{	118	{
119	link_t left,right, *tmp;	119	link_t left,right, *tmp;
120	__u8 order;	120	__u8 order;
121		121
122	left = b->op->find_block(b, block, BUDDY_SYSTEM_INNER_BLOCK);	122	left = b->op->find_block(b, block, BUDDY_SYSTEM_INNER_BLOCK);
123	ASSERT(left);	123	ASSERT(left);
124	list_remove(left);	124	list_remove(left);
125	while (1) {	125	while (1) {
126	if (! b->op->get_order(b,left)) {	126	if (! b->op->get_order(b,left)) {
127	b->op->mark_busy(b, left);	127	b->op->mark_busy(b, left);
128	return left;	128	return left;
129	}	129	}
130		130
131	order = b->op->get_order(b, left);	131	order = b->op->get_order(b, left);
132		132
133	right = b->op->bisect(b, left);	133	right = b->op->bisect(b, left);
134	b->op->set_order(b, left, order-1);	134	b->op->set_order(b, left, order-1);
135	b->op->set_order(b, right, order-1);	135	b->op->set_order(b, right, order-1);
136		136
137	tmp = b->op->find_block(b, block, BUDDY_SYSTEM_INNER_BLOCK);	137	tmp = b->op->find_block(b, block, BUDDY_SYSTEM_INNER_BLOCK);
138		138
139	if (tmp == right) {	139	if (tmp == right) {
140	right = left;	140	right = left;
141	left = tmp;	141	left = tmp;
142	}	142	}
-		143	ASSERT(tmp == left);
143	b->op->mark_busy(b, left);	144	b->op->mark_busy(b, left);
144	buddy_system_free(b, right);	145	buddy_system_free(b, right);
145	b->op->mark_available(b, left);	146	b->op->mark_available(b, left);
146	}	147	}
147	}	148	}
148		149
149	/** Allocate block from buddy system.	150	/** Allocate block from buddy system.
150	*	151	*
151	* @param b Buddy system pointer.	152	* @param b Buddy system pointer.
152	* @param i Returned block will be 2^i big.	153	* @param i Returned block will be 2^i big.
153	*	154	*
154	* @return Block of data represented by link_t.	155	* @return Block of data represented by link_t.
155	*/	156	*/
156	link_t buddy_system_alloc(buddy_system_t b, __u8 i)	157	link_t buddy_system_alloc(buddy_system_t b, __u8 i)
157	{	158	{
158	link_t res, hlp;	159	link_t res, hlp;
159		160
160	ASSERT(i <= b->max_order);	161	ASSERT(i <= b->max_order);
161		162
162	/*	163	/*
163	* If the list of order i is not empty,	164	* If the list of order i is not empty,
164	* the request can be immediatelly satisfied.	165	* the request can be immediatelly satisfied.
165	*/	166	*/
166	if (!list_empty(&b->order[i])) {	167	if (!list_empty(&b->order[i])) {
167	res = b->order[i].next;	168	res = b->order[i].next;
168	list_remove(res);	169	list_remove(res);
169	b->op->mark_busy(b, res);	170	b->op->mark_busy(b, res);
170	return res;	171	return res;
171	}	172	}
172	/*	173	/*
173	* If order i is already the maximal order,	174	* If order i is already the maximal order,
174	* the request cannot be satisfied.	175	* the request cannot be satisfied.
175	*/	176	*/
176	if (i == b->max_order)	177	if (i == b->max_order)
177	return NULL;	178	return NULL;
178		179
179	/*	180	/*
180	* Try to recursively satisfy the request from higher order lists.	181	* Try to recursively satisfy the request from higher order lists.
181	*/	182	*/
182	hlp = buddy_system_alloc(b, i + 1);	183	hlp = buddy_system_alloc(b, i + 1);
183		184
184	/*	185	/*
185	* The request could not be satisfied	186	* The request could not be satisfied
186	* from higher order lists.	187	* from higher order lists.
187	*/	188	*/
188	if (!hlp)	189	if (!hlp)
189	return NULL;	190	return NULL;
190		191
191	res = hlp;	192	res = hlp;
192		193
193	/*	194	/*
194	* Bisect the block and set order of both of its parts to i.	195	* Bisect the block and set order of both of its parts to i.
195	*/	196	*/
196	hlp = b->op->bisect(b, res);	197	hlp = b->op->bisect(b, res);
197	b->op->set_order(b, res, i);	198	b->op->set_order(b, res, i);
198	b->op->set_order(b, hlp, i);	199	b->op->set_order(b, hlp, i);
199		200
200	/*	201	/*
201	* Return the other half to buddy system. Mark the first part	202	* Return the other half to buddy system. Mark the first part
202	* full, so that it won't coalesce again.	203	* full, so that it won't coalesce again.
203	*/	204	*/
204	b->op->mark_busy(b, res);	205	b->op->mark_busy(b, res);
205	buddy_system_free(b, hlp);	206	buddy_system_free(b, hlp);
206		207
207	return res;	208	return res;
208		209
209	}	210	}
210		211
211	/** Return block to buddy system.	212	/** Return block to buddy system.
212	*	213	*
213	* @param b Buddy system pointer.	214	* @param b Buddy system pointer.
214	* @param block Block to return.	215	* @param block Block to return.
215	*/	216	*/
216	void buddy_system_free(buddy_system_t b, link_t block)	217	void buddy_system_free(buddy_system_t b, link_t block)
217	{	218	{
218	link_t buddy, hlp;	219	link_t buddy, hlp;
219	__u8 i;	220	__u8 i;
220		221
221	/*	222	/*
222	* Determine block's order.	223	* Determine block's order.
223	*/	224	*/
224	i = b->op->get_order(b, block);	225	i = b->op->get_order(b, block);
225		226
226	ASSERT(i <= b->max_order);	227	ASSERT(i <= b->max_order);
227		228
228	if (i != b->max_order) {	229	if (i != b->max_order) {
229	/*	230	/*
230	* See if there is any buddy in the list of order i.	231	* See if there is any buddy in the list of order i.
231	*/	232	*/
232	buddy = b->op->find_buddy(b, block);	233	buddy = b->op->find_buddy(b, block);
233	if (buddy) {	234	if (buddy) {
234		235
235	ASSERT(b->op->get_order(b, buddy) == i);	236	ASSERT(b->op->get_order(b, buddy) == i);
236	/*	237	/*
237	* Remove buddy from the list of order i.	238	* Remove buddy from the list of order i.
238	*/	239	*/
239	list_remove(buddy);	240	list_remove(buddy);
240		241
241	/*	242	/*
242	* Invalidate order of both block and buddy.	243	* Invalidate order of both block and buddy.
243	*/	244	*/
244	b->op->set_order(b, block, BUDDY_SYSTEM_INNER_BLOCK);	245	b->op->set_order(b, block, BUDDY_SYSTEM_INNER_BLOCK);
245	b->op->set_order(b, buddy, BUDDY_SYSTEM_INNER_BLOCK);	246	b->op->set_order(b, buddy, BUDDY_SYSTEM_INNER_BLOCK);
246		247
247	/*	248	/*
248	* Coalesce block and buddy into one block.	249	* Coalesce block and buddy into one block.
249	*/	250	*/
250	hlp = b->op->coalesce(b, block, buddy);	251	hlp = b->op->coalesce(b, block, buddy);
251		252
252	/*	253	/*
253	* Set order of the coalesced block to i + 1.	254	* Set order of the coalesced block to i + 1.
254	*/	255	*/
255	b->op->set_order(b, hlp, i + 1);	256	b->op->set_order(b, hlp, i + 1);
256		257
257	/*	258	/*
258	* Recursively add the coalesced block to the list of order i + 1.	259	* Recursively add the coalesced block to the list of order i + 1.
259	*/	260	*/
260	buddy_system_free(b, hlp);	261	buddy_system_free(b, hlp);
261	return;	262	return;
262	}	263	}
263	}	264	}
264		265
265	/*	266	/*
266	* Insert block into the list of order i.	267	* Insert block into the list of order i.
267	*/	268	*/
268	list_append(block, &b->order[i]);	269	list_append(block, &b->order[i]);
269		270
270	}	271	}
271		272
272	/** Prints out structure of buddy system	273	/** Prints out structure of buddy system
273	*	274	*
274	* @param b Pointer to buddy system	275	* @param b Pointer to buddy system
275	* @param es Element size	276	* @param es Element size
276	*/	277	*/
277	void buddy_system_structure_print(buddy_system_t *b, size_t elem_size) {	278	void buddy_system_structure_print(buddy_system_t *b, size_t elem_size) {
278	index_t i;	279	index_t i;
279	count_t cnt, elem_count = 0, block_count = 0;	280	count_t cnt, elem_count = 0, block_count = 0;
280	link_t * cur;	281	link_t * cur;
281		282
282		283
283	printf("Order\tBlocks\tSize \tBlock size\tElems per block\n");	284	printf("Order\tBlocks\tSize \tBlock size\tElems per block\n");
284	printf("-----\t------\t--------\t----------\t---------------\n");	285	printf("-----\t------\t--------\t----------\t---------------\n");
285		286
286	for (i=0;i <= b->max_order; i++) {	287	for (i=0;i <= b->max_order; i++) {
287	cnt = 0;	288	cnt = 0;
288	if (!list_empty(&b->order[i])) {	289	if (!list_empty(&b->order[i])) {
289	for (cur = b->order[i].next; cur != &b->order[i]; cur = cur->next)	290	for (cur = b->order[i].next; cur != &b->order[i]; cur = cur->next)
290	cnt++;	291	cnt++;
291	}	292	}
292		293
293	printf("#%d\t%d\t%dK\t\t%dK\t\t%d\n", i, cnt, (cnt * (1 << i) * elem_size) >> 10, ((1 << i) * elem_size) >> 10, 1 << i);	294	printf("#%d\t%d\t%dK\t\t%dK\t\t%d\t", i, cnt, (cnt * (1 << i) * elem_size) >> 10, ((1 << i) * elem_size) >> 10, 1 << i);
-		295	if (!list_empty(&b->order[i])) {
-		296	for (cur = b->order[i].next; cur != &b->order[i]; cur = cur->next) {
-		297	b->op->print_id(b, cur);
-		298	printf(" ");
-		299	}
-		300	}
-		301	printf("\n");
294		302
295	block_count += cnt;	303	block_count += cnt;
296	elem_count += (1 << i) * cnt;	304	elem_count += (1 << i) * cnt;
297	}	305	}
298	printf("-----\t------\t--------\t----------\t---------------\n");	306	printf("-----\t------\t--------\t----------\t---------------\n");
299	printf("Buddy system contains %d free elements (%d blocks)\n" , elem_count, block_count);	307	printf("Buddy system contains %d free elements (%d blocks)\n" , elem_count, block_count);
300		308
301	}	309	}
302		310

Subversion Repositories HelenOS-historic

(root)/kernel/trunk/generic/src/mm/buddy.c – Rev 815 → 822