WebSVN – HelenOS – Blame – /trunk/kernel/generic/src/mm/buddy.c

Rev	Author	Line No.	Line
377	jermar	1	/*
		2	* Copyright (C) 2005 Jakub Jermar
		3	* All rights reserved.
		4	*
		5	* Redistribution and use in source and binary forms, with or without
		6	* modification, are permitted provided that the following conditions
		7	* are met:
		8	*
		9	* - Redistributions of source code must retain the above copyright
		10	* notice, this list of conditions and the following disclaimer.
		11	* - Redistributions in binary form must reproduce the above copyright
		12	* notice, this list of conditions and the following disclaimer in the
		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
		15	* derived from this software without specific prior written permission.
		16	*
		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
		19	* OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
		20	* IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
		21	* INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
		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
		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
		26	* THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
		27	*/
		28
		29	#include <mm/buddy.h>
		30	#include <mm/frame.h>
		31	#include <mm/heap.h>
		32	#include <arch/types.h>
		33	#include <typedefs.h>
		34	#include <list.h>
		35	#include <debug.h>
		36
		37	/** Create buddy system
		38	*
		39	* Allocate memory for and initialize new buddy system.
		40	*
		41	* @param max_order The biggest allocable size will be 2^max_order.
		42	* @param op Operations for new buddy system.
		43	*
		44	* @return New buddy system.
		45	*/
		46	buddy_system_t buddy_system_create(__u8 max_order, buddy_operations_t op)
		47	{
		48	buddy_system_t *b;
		49	int i;
		50
378	jermar	51	ASSERT(max_order < BUDDY_SYSTEM_INNER_BLOCK);
		52
377	jermar	53	ASSERT(op->find_buddy);
		54	ASSERT(op->set_order);
		55	ASSERT(op->get_order);
		56	ASSERT(op->bisect);
		57	ASSERT(op->coalesce);
		58
		59	/*
		60	* Allocate memory for structure describing the whole buddy system.
		61	*/
		62	b = (buddy_system_t *) early_malloc(sizeof(buddy_system_t));
		63
		64	if (b) {
		65	/*
		66	* Allocate memory for all orders this buddy system will work with.
		67	*/
		68	b->order = (link_t ) early_malloc(max_order sizeof(link_t));
		69	if (!b->order) {
		70	early_free(b);
		71	return NULL;
		72	}
		73
		74	for (i = 0; i < max_order; i++)
		75	list_initialize(&b->order[i]);
		76
		77	b->max_order = max_order;
		78	b->op = op;
		79	}
		80
		81	return b;
		82	}
		83
		84	/** Allocate block from buddy system.
		85	*
		86	* Allocate block from buddy system.
		87	*
		88	* @param b Buddy system pointer.
		89	* @param i Returned block will be 2^i big.
		90	*
		91	* @return Block of data represented by link_t.
		92	*/
		93	link_t buddy_system_alloc(buddy_system_t b, __u8 i)
		94	{
		95	link_t res, hlp;
		96
		97	ASSERT(i < b->max_order);
		98
		99	/*
		100	* If the list of order i is not empty,
		101	* the request can be immediatelly satisfied.
		102	*/
		103	if (!list_empty(&b->order[i])) {
		104	res = b->order[i].next;
		105	list_remove(res);
		106	return res;
		107	}
		108
		109	/*
		110	* If order i is already the maximal order,
		111	* the request cannot be satisfied.
		112	*/
		113	if (i == b->max_order - 1)
		114	return NULL;
		115
		116	/*
		117	* Try to recursively satisfy the request from higher order lists.
		118	*/
		119	hlp = buddy_system_alloc(b, i + 1);
		120
		121	/*
		122	* The request could not be satisfied
		123	* from higher order lists.
		124	*/
		125	if (!hlp)
		126	return NULL;
		127
		128	res = hlp;
		129
		130	/*
		131	* Bisect the block and set order of both of its parts to i.
		132	*/
		133	hlp = b->op->bisect(res);
		134	b->op->set_order(res, i);
		135	b->op->set_order(hlp, i);
		136
		137	/*
		138	* Return the other half to buddy system.
		139	*/
		140	buddy_system_free(b, hlp);
		141
		142	return res;
		143
		144	}
		145
		146	/** Return block to buddy system.
		147	*
		148	* Return block to buddy system.
		149	*
		150	* @param b Buddy system pointer.
		151	* @param block Block to return.
		152	*/
		153	void buddy_system_free(buddy_system_t b, link_t block)
		154	{
		155	link_t buddy, hlp;
		156	__u8 i;
		157
		158	/*
		159	* Determine block's order.
		160	*/
		161	i = b->op->get_order(block);
		162
		163	ASSERT(i < b->max_order);
		164
		165	/*
		166	* See if there is any buddy in the list of order i.
		167	*/
		168	buddy = b->op->find_buddy(block);
		169
		170	if (buddy && i != b->max_order - 1) {
378	jermar	171
		172	ASSERT(b->op->get_order(buddy) == i);
		173
377	jermar	174	/*
		175	* Remove buddy from the list of order i.
		176	*/
		177	list_remove(buddy);
		178
		179	/*
378	jermar	180	* Invalidate order of both block and buddy.
		181	*/
		182	b->op->set_order(block, BUDDY_SYSTEM_INNER_BLOCK);
		183	b->op->set_order(buddy, BUDDY_SYSTEM_INNER_BLOCK);
		184
		185	/*
377	jermar	186	* Coalesce block and buddy into one block.
		187	*/
		188	hlp = b->op->coalesce(block, buddy);
		189
		190	/*
		191	* Set order of the coalesced block to i + 1.
		192	*/
		193	b->op->set_order(hlp, i + 1);
		194
		195	/*
		196	* Recursively add the coalesced block to the list of order i + 1.
		197	*/
		198	buddy_system_free(b, hlp);
		199	}
		200	else {
		201	/*
		202	* Insert block into the list of order i.
		203	*/
		204	list_append(block, &b->order[i]);
		205	}
		206
		207	}

Subversion Repositories HelenOS

(root)/trunk/kernel/generic/src/mm/buddy.c @ 2744 – Rev 378