heap.c.svn-base

RT-Thread是发展中的下一代微内核嵌入式实时操作系统

/*
 * File      : heap.c
 * This file is part of RT-Thread RTOS
 * COPYRIGHT (C) 2006, RT-Thread Development Team
 *
 * The license and distribution terms for this file may be
 * found in the file LICENSE in this distribution or at
 * http://www.fayfayspace.org/license/LICENSE.
 *
 * Change Logs:
 * Date           Author       Notes
 * 2006-03-19     Bernard      the first version
 * 2006-07-02     Bernard      clean RT_ASSERT in alloc and free
 */

#include <rtthread.h>

/**
 * @addtogroup Kernel
 */

/*@{*/

/* page allocator */
struct rt_page_head
{
	struct rt_page_head *next;		/* next valid page */
	rt_size_t page;					/* number of page  */

	/* dummy */
	char dummy[RT_MM_PAGE_SIZE - (sizeof(struct rt_page_head*) + sizeof (rt_size_t))];
};
static struct rt_page_head *rt_page_list;

void rt_page_init(void* addr, rt_size_t npages);
void *rt_page_alloc(rt_size_t npages);
void rt_page_free(void *addr, rt_size_t npages);

void rt_system_page_init(void* begin_addr, void* end_addr)
{
	rt_page_init(begin_addr, 
		((rt_ubase_t)end_addr - (rt_ubase_t)begin_addr) / RT_MM_PAGE_SIZE);
}

void rt_page_init(void* addr, rt_size_t npages)
{
	RT_ASSERT(addr != RT_NULL);
	RT_ASSERT(npages != 0);

	/* alin */
	addr = (void *)((int)((char *)addr + RT_MM_PAGE_SIZE - 1) & ~(RT_MM_PAGE_SIZE - 1));

	rt_page_list = RT_NULL;
	rt_page_free(addr, npages);
}

void *rt_page_alloc(rt_size_t npages)
{
	struct rt_page_head *b, *n;
	struct rt_page_head **prev;

	RT_ASSERT(npages != 0);

	for (prev = &rt_page_list; (b = *prev) != RT_NULL; prev = &(b->next))
	{
		if (b->page > npages)
		{
			n = b + npages;
			n->next = b->next;
			n->page = b->page - npages;
			*prev = n;
			break;
		}

		if (b->page == npages)
		{
			*prev = b->next;
			break;
		}
	}

	return b;
}

void rt_page_free(void *addr, rt_size_t npages)
{
	struct rt_page_head *b, *n;
	struct rt_page_head **prev;

	RT_ASSERT(addr != RT_NULL);
	RT_ASSERT((int)addr % RT_MM_PAGE_SIZE == 0);
	RT_ASSERT(npages != 0);

	n = (struct rt_page_head *)addr;

	for (prev = &rt_page_list; (b = *prev) != RT_NULL; prev = &(b->next))
	{
		RT_ASSERT(b->page > 0);
		RT_ASSERT(b > n || b + b->page <= n);

		if (b + b->page == n)
		{
			if (b + (b->page += npages) == b->next)
			{
				b->page += b->next->page;
				b->next  = b->next->next;
			}

			return;
		}

		if (b == n + npages)
		{
			n->page = b->page + npages;
			n->next = b->next;
			*prev = n;

			return;
		}

		if (b > n + npages) break;
	}

	n->page = npages;
	n->next = b;
	*prev = n;
}

union block_head
{
	union block_head *next;		/* when free */
	struct
	{
		rt_uint16 magic;		/* magic number */
		rt_uint16 index;		/* bucket #     */
	}bhu;
#define block_head_magic	bhu.magic
#define block_head_index	bhu.index
};

#define RT_MM_MAGIC	0xbeef

#define NBUCKETS	(RT_MM_PAGE_BITS - 3)
static union block_head *block_next_free[NBUCKETS];

void* rt_malloc(rt_size_t nbytes)
{
	union block_head *op;
	rt_size_t amt;
	rt_size_t bucket;

	if (nbytes == 0) return RT_NULL;

	/*
	 * Convert amount of memory requested into closest block size
	 * stored in hash buckets which satisfies request.
	 * Account for space used per block for accounting.
	 */
	nbytes += sizeof(*op);

	if (nbytes > RT_MM_PAGE_SIZE / 2)
	{
		bucket = (nbytes + (RT_MM_PAGE_SIZE - 1)) >> RT_MM_PAGE_BITS;
		if (bucket <= 0 || bucket > RT_UINT16_MAX - NBUCKETS) return RT_NULL;
		op = rt_page_alloc(bucket);
		if (op == RT_NULL) return RT_NULL;
		bucket += NBUCKETS;
	}
	else
	{
		amt    = 8;
		bucket = 0;
		
		while (nbytes > amt)
		{
			amt <<= 1;
			bucket++;
		}
		
		RT_ASSERT(bucket < NBUCKETS);
		
		/* no bucket, request more memory from the system. */
		op = block_next_free[bucket];
		if (op == RT_NULL)
		{
			int nblocks;
			
			op = rt_page_alloc(1);
			if (op == RT_NULL)
			{
				return RT_NULL;
			}

			block_next_free[bucket] = op;
			nblocks = RT_MM_PAGE_SIZE / amt;
			while (--nblocks > 0)
			{
				op = op->next = (union block_head *)((char*)op + amt);
			}
			op->next = RT_NULL;
			op = block_next_free[bucket];
		}
		/* remove from linked list */
		block_next_free[bucket] = op->next;
	}

	RT_ASSERT(bucket != NBUCKETS);
	op->block_head_magic = RT_MM_MAGIC;
	op->block_head_index = bucket;
	return (char*)(op + 1);
}

void rt_free (void *ptr)
{
	union block_head *op;
	rt_int32 size;

	if (ptr == RT_NULL) return;

	op = (union block_head *)ptr - 1;
	
	if (op->block_head_magic != RT_MM_MAGIC) return;

	size = op->block_head_index;
	RT_ASSERT(size != NBUCKETS);
	if (size > NBUCKETS) rt_page_free(op, size - NBUCKETS);
	else
	{
		op->next = block_next_free[size];
		block_next_free[size] = op;
	}
}

/*@}*/