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.
 */
 
/** @addtogroup genericmm
 * @{
 */
 
/**
 * @file
 * @brief   Buddy allocator framework.
 *
 * This file contains buddy system allocator framework.
 * Specialized functions are needed for this abstract framework
 * to be useful.
 */
 
#include <mm/buddy.h>
#include <mm/frame.h>
#include <arch/types.h>
#include <debug.h>
#include <print.h>
#include <macros.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,
             uint8_t 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, uint8_t i) {
    uint8_t 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;
    uint8_t 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, uint8_t 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;
    uint8_t 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 elem_size 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("#%" PRIi "\t%5" PRIc "\t%7" PRIc "K\t%8" PRIi "K\t%6u\t",
            i, cnt, SIZE2KB(cnt * (1 << i) * elem_size), SIZE2KB((1 << i) * elem_size), 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 %" PRIc " free elements (%" PRIc " blocks)\n" , elem_count, block_count);
 
}
 
/** @}
 */
 

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

Subversion Repositories HelenOS

(root)/trunk/kernel/generic/src/mm/buddy.c @ 2089 – Rev 2089 → 3057