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

Subversion Repositories HelenOS

(root)/tags/0.2.0/kernel/generic/src/mm/buddy.c – Rev 1964 → 1968