WebSVN - shark - Blame - Rev 3 - /shark/trunk/kernel/mem/alloc

Rev	Author	Line No.	Line
2	pj	1	/*
		2	* Project: S.Ha.R.K.
		3	*
		4	* Coordinators:
		5	* Giorgio Buttazzo <giorgio@sssup.it>
		6	* Paolo Gai <pj@gandalf.sssup.it>
		7	*
		8	* Authors :
		9	* Paolo Gai <pj@gandalf.sssup.it>
		10	* (see the web pages for full authors list)
		11	*
		12	* ReTiS Lab (Scuola Superiore S.Anna - Pisa - Italy)
		13	*
		14	* http://www.sssup.it
		15	* http://retis.sssup.it
		16	* http://shark.sssup.it
		17	*/
		18
		19	/**
		20	------------
		21	CVS : $Id: alloc_ge.c,v 1.1.1.1 2002-03-29 14:12:52 pj Exp $
		22
		23	File: $File$
		24	Revision: $Revision: 1.1.1.1 $
		25	Last update: $Date: 2002-03-29 14:12:52 $
		26	------------
		27
		28	this code is from:
		29	List-based Memory Management, from OsKit.
		30
		31	**/
		32
		33	/*
		34	* Copyright (C) 2000 Paolo Gai
		35	*
		36	* This program is free software; you can redistribute it and/or modify
		37	* it under the terms of the GNU General Public License as published by
		38	* the Free Software Foundation; either version 2 of the License, or
		39	* (at your option) any later version.
		40	*
		41	* This program is distributed in the hope that it will be useful,
		42	* but WITHOUT ANY WARRANTY; without even the implied warranty of
		43	* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
		44	* GNU General Public License for more details.
		45	*
		46	* You should have received a copy of the GNU General Public License
		47	* along with this program; if not, write to the Free Software
		48	* Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
		49	*
		50	*/
		51
		52	/*
		53	* Copyright (c) 1995-1996, 1998-1999 University of Utah and the Flux Group.
		54	* All rights reserved.
		55	*
		56	* This file is part of the Flux OSKit. The OSKit is free software, also known
		57	* as "open source;" you can redistribute it and/or modify it under the terms
		58	* of the GNU General Public License (GPL), version 2, as published by the Free
		59	* Software Foundation (FSF). To explore alternate licensing terms, contact
		60	* the University of Utah at csl-dist@cs.utah.edu or +1-801-585-3271.
		61	*
		62	* The OSKit is distributed in the hope that it will be useful, but WITHOUT ANY
		63	* WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
		64	* FOR A PARTICULAR PURPOSE. See the GPL for more details. You should have
		65	* received a copy of the GPL along with the OSKit; see the file COPYING. If
		66	* not, write to the FSF, 59 Temple Place #330, Boston, MA 02111-1307, USA.
		67	*/
		68
		69	#include <kernel/lmm.h>
		70	#define assert(test) assertk(test)
		71
		72	void lmm_alloc_gen(lmm_t lmm, size_t size, lmm_flags_t flags,
		73	int align_bits, DWORD align_ofs,
		74	DWORD in_min, size_t in_size)
		75	{
		76	DWORD in_max = in_min + in_size;
		77	struct lmm_region *reg;
		78
		79	#if 0
		80	kern_printf("lmm_alloc_gen %08x\n", size);
		81	lmm_dump(lmm);
		82	#endif
		83
		84	assert(lmm != 0);
		85	assert(size > 0);
		86
		87	for (reg = lmm->regions; reg; reg = reg->next)
		88	{
		89	struct lmm_node *nodep, node;
		90
		91	CHECKREGPTR(reg);
		92
		93	/* First trivially reject the entire region if possible. */
		94	if ((flags & ~reg->flags)
		95	\|\| (reg->min >= in_max)
		96	\|\| (reg->max <= in_min))
		97	continue;
		98
		99	for (nodep = &reg->nodes;
		100	(node = *nodep) != 0;
		101	nodep = &node->next)
		102	{
		103	DWORD addr;
		104	struct lmm_node *anode;
		105	int i;
		106
		107	assert(((DWORD)node & ALIGN_MASK) == 0);
		108	assert(((DWORD)node->size & ALIGN_MASK) == 0);
		109	assert((node->next == 0) \|\| (node->next > node));
		110	assert((DWORD)node < reg->max);
		111
		112	/* Now make a first-cut trivial elimination check
		113	to skip chunks that are _definitely_ too small. */
		114	if (node->size < size)
		115	continue;
		116
		117	/* Now compute the address at which
		118	the allocated chunk would have to start. */
		119	addr = (DWORD)node;
		120	if (addr < in_min)
		121	addr = in_min;
		122	for (i = 0; i < align_bits; i++)
		123	{
		124	DWORD bit = (DWORD)1 << i;
		125	if ((addr ^ align_ofs) & bit)
		126	addr += bit;
		127	}
		128
		129	/* See if the block at the adjusted address
		130	is still entirely within the node. */
		131	if ((addr - (DWORD)node + size) > node->size)
		132	continue;
		133
		134	/* If the block extends past the range constraint,
		135	then all of the rest of the nodes in this region
		136	will extend past it too, so stop here. */
		137	if (addr + size > in_max)
		138	break;
		139
		140	/* OK, we can allocate the block from this node. */
		141
		142	/* If the allocation leaves at least ALIGN_SIZE
		143	space before it, then split the node. */
		144	anode = (struct lmm_node*)(addr & ~ALIGN_MASK);
		145	assert(anode >= node);
		146	if (anode > node)
		147	{
		148	size_t split_size = (DWORD)anode
		149	- (DWORD)node;
		150	assert((split_size & ALIGN_MASK) == 0);
		151	anode->next = node->next;
		152	anode->size = node->size - split_size;
		153	node->size = split_size;
		154	nodep = &node->next;
		155	}
		156
		157	/* Now use the first part of the anode
		158	to satisfy the allocation,
		159	splitting off the tail end if necessary. */
		160	size = ((addr & ALIGN_MASK) + size + ALIGN_MASK)
		161	& ~ALIGN_MASK;
		162	if (anode->size > size)
		163	{
		164	struct lmm_node *newnode;
		165
		166	/* Split the node and return its head. */
		167	newnode = (struct lmm_node*)
		168	((void*)anode + size);
		169	newnode->next = anode->next;
		170	newnode->size = anode->size - size;
		171	*nodep = newnode;
		172	}
		173	else
		174	{
		175	/* Remove and return the entire node. */
		176	*nodep = anode->next;
		177	}
		178
		179	/* Adjust the region's free memory counter. */
		180	assert(reg->free >= size);
		181	reg->free -= size;
		182
		183	#if 0
		184	kern_printf("lmm_alloc_gen returning %08x\n", addr);
		185	lmm_dump(lmm);
		186	#endif
		187
		188	return (void*)addr;
		189	}
		190	}
		191
		192	#if 0
		193	kern_printf("lmm_alloc_gen failed\n");
		194	#endif
		195
		196	return 0;
		197	}
		198

Subversion Repositories shark

(root)/shark/trunk/kernel/mem/alloc_ge.c - Rev 3