WebSVN – HelenOS-historic – Blame – /kernel/trunk/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
		51	ASSERT(op->find_buddy);
		52	ASSERT(op->set_order);
		53	ASSERT(op->get_order);
		54	ASSERT(op->bisect);
		55	ASSERT(op->coalesce);
		56
		57	/*
		58	* Allocate memory for structure describing the whole buddy system.
		59	*/
		60	b = (buddy_system_t *) early_malloc(sizeof(buddy_system_t));
		61
		62	if (b) {
		63	/*
		64	* Allocate memory for all orders this buddy system will work with.
		65	*/
		66	b->order = (link_t ) early_malloc(max_order sizeof(link_t));
		67	if (!b->order) {
		68	early_free(b);
		69	return NULL;
		70	}
		71
		72	for (i = 0; i < max_order; i++)
		73	list_initialize(&b->order[i]);
		74
		75	b->max_order = max_order;
		76	b->op = op;
		77	}
		78
		79	return b;
		80	}
		81
		82	/** Allocate block from buddy system.
		83	*
		84	* Allocate block from buddy system.
		85	*
		86	* @param b Buddy system pointer.
		87	* @param i Returned block will be 2^i big.
		88	*
		89	* @return Block of data represented by link_t.
		90	*/
		91	link_t buddy_system_alloc(buddy_system_t b, __u8 i)
		92	{
		93	link_t res, hlp;
		94
		95	ASSERT(i < b->max_order);
		96
		97	/*
		98	* If the list of order i is not empty,
		99	* the request can be immediatelly satisfied.
		100	*/
		101	if (!list_empty(&b->order[i])) {
		102	res = b->order[i].next;
		103	list_remove(res);
		104	return res;
		105	}
		106
		107	/*
		108	* If order i is already the maximal order,
		109	* the request cannot be satisfied.
		110	*/
		111	if (i == b->max_order - 1)
		112	return NULL;
		113
		114	/*
		115	* Try to recursively satisfy the request from higher order lists.
		116	*/
		117	hlp = buddy_system_alloc(b, i + 1);
		118
		119	/*
		120	* The request could not be satisfied
		121	* from higher order lists.
		122	*/
		123	if (!hlp)
		124	return NULL;
		125
		126	res = hlp;
		127
		128	/*
		129	* Bisect the block and set order of both of its parts to i.
		130	*/
		131	hlp = b->op->bisect(res);
		132	b->op->set_order(res, i);
		133	b->op->set_order(hlp, i);
		134
		135	/*
		136	* Return the other half to buddy system.
		137	*/
		138	buddy_system_free(b, hlp);
		139
		140	return res;
		141
		142	}
		143
		144	/** Return block to buddy system.
		145	*
		146	* Return block to buddy system.
		147	*
		148	* @param b Buddy system pointer.
		149	* @param block Block to return.
		150	*/
		151	void buddy_system_free(buddy_system_t b, link_t block)
		152	{
		153	link_t buddy, hlp;
		154	__u8 i;
		155
		156	/*
		157	* Determine block's order.
		158	*/
		159	i = b->op->get_order(block);
		160
		161	ASSERT(i < b->max_order);
		162
		163	/*
		164	* See if there is any buddy in the list of order i.
		165	*/
		166	buddy = b->op->find_buddy(block);
		167
		168	if (buddy && i != b->max_order - 1) {
		169	/*
		170	* Remove buddy from the list of order i.
		171	*/
		172	list_remove(buddy);
		173
		174	/*
		175	* Coalesce block and buddy into one block.
		176	*/
		177	hlp = b->op->coalesce(block, buddy);
		178
		179	/*
		180	* Set order of the coalesced block to i + 1.
		181	*/
		182	b->op->set_order(hlp, i + 1);
		183
		184	/*
		185	* Recursively add the coalesced block to the list of order i + 1.
		186	*/
		187	buddy_system_free(b, hlp);
		188	}
		189	else {
		190	/*
		191	* Insert block into the list of order i.
		192	*/
		193	list_append(block, &b->order[i]);
		194	}
		195
		196	}

Subversion Repositories HelenOS-historic

(root)/kernel/trunk/generic/src/mm/buddy.c @ 1780 – Rev 377