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.
 */
 
/** @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 <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 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("#%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);
        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 %zd free elements (%zd blocks)\n" , elem_count, block_count);
 
}
 
/** @}
 */
 
 

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

Subversion Repositories HelenOS-historic

(root)/kernel/trunk/generic/src/mm/buddy.c – Rev 1708 → 1757