memalloc.c

T-kernel 的extension源代码

/*
 *----------------------------------------------------------------------
 *    T-Kernel / Standard Extension
 *
 *    Copyright (C) 2006 by Ken Sakamura. All rights reserved.
 *    T-Kernel / Standard Extension is distributed 
 *      under the T-License for T-Kernel / Standard Extension.
 *----------------------------------------------------------------------
 *
 *    Version:   1.00.00
 *    Released by T-Engine Forum(http://www.t-engine.org) at 2006/8/11.
 *
 *----------------------------------------------------------------------
 */

/*
 *	memalloc.c (libtkse)
 *
 *	Memory allocation library
 *
 *	Obtain a memory block and divide it to allocate.
 *	(*) Note that it must be reentrant.
 */

#include "mem.h"

Inline W toPageCount( size_t size, MACB *macb );
Inline QUEUE* newPage( size_t size, MACB *macb );
Inline VP allocate( QUEUE *aq, size_t size, MACB *macb );

LOCAL QUEUE* searchFreeArea( size_t size, MACB *macb );
LOCAL void appendFreeArea( QUEUE *aq, MACB *macb );
LOCAL void removeFreeQue( QUEUE *fq );
LOCAL void insertAreaQue( QUEUE *que, QUEUE *ent );
LOCAL void removeAreaQue( QUEUE *aq );

#define TSD_MMF_VAL_2	2
#define TSD_AFA_VAL_2	2
#define TSD_NPG_VAL_2	2
#define TSD_SFA_VAL_4	4U

/*
 * Minimum fragment size
 *	sizeof(QUEUE) * Malfunction occurs if a specified size is smaller than 2.
 */
EXPORT size_t	_mem_minfragment = sizeof(QUEUE) * TSD_MMF_VAL_2;

/*
 * Memory allocation check function
 */
EXPORT BOOL	(*_mem_chkalloc)( void *ptr, int mode, MACB *macb );

#define	chkalloc	(*_mem_chkalloc)

/*
 * Byte size --> Number of pages
 */
Inline W toPageCount( size_t size, MACB *macb )
{
	return (W)((size + (macb->pagesz - 1U)) / macb->pagesz);
}

/*
 * Free queue search
 *	Search for a free space that is of the same size, or larger but of the closest size.
 *	When not found, return &freeque.
 */
LOCAL QUEUE* searchFreeArea( size_t size, MACB *macb )
{
	QUEUE	*q = &macb->freeque;

	/* Spaces not greater than a fourth of the page size must be searched in ascending order of size;
	   spaces larger than that must be searched in descending order. */
	if ( size > (macb->pagesz / TSD_SFA_VAL_4 )) {
		/* Search in descending order of size */
		size_t fsz = 0;
		while ( (q = q->prev) != &macb->freeque ) {
			fsz = (size_t)FreeSize(q);
			if ( fsz <= size ) {
				return ( fsz < size )? q->next: q;
			}
		}
		return ( fsz >= size )? q->next: q;
	} else {
		/* Search in ascending order of size */
		while ( (q = q->next) != &macb->freeque ) {
			if ( (size_t)FreeSize(q) >= size ) {
				break;
			}
		}
		return q;
	}
}

/*
 * Register free space in free queue.
 *	A free queue consists of two queues: one queue links spaces of different sizes in order of size;
 *	the other links spaces of the same size.
 *
 *	macb->freeque
 *	|
 *	v   +-------------------------------+		+-----------------------+
 *	|   | AreaQue		 	    |		| AreaQue		|
 *	|   +-------------------------------+		+-----------------------+
 *	*-->| FreeQue in order of size	    |	 *--------> FreeQue same size ------>
 *	|   | FreeQue same size 	   ------*	| EmptyQue		|
 *	|   |			 	    |		|			|
 *	|   |				    |		|			|
 *	|   +-------------------------------+		+-----------------------+
 *	|   | AreaQue			    |		| AreaQue		|
 *	v   +-------------------------------+		+-----------------------+
 */
LOCAL void appendFreeArea( QUEUE *aq, MACB *macb )
{
	QUEUE	*fq;
	size_t	size = (size_t)AreaSize(aq);

	/* Search of registered position */
	fq = searchFreeArea(size, macb);

	/* Register */
	clrAreaFlag(aq, AREA_USE);
	if (( fq != &macb->freeque )&&((size_t)FreeSize(fq) == size )) {
		QueInsert(aq + 1, fq + 1);
	} else {
		QueInsert(aq + 1, fq);
	}
	QueInit(aq + TSD_AFA_VAL_2);
}

/*
 * Delete from free queue
 */
LOCAL void removeFreeQue( QUEUE *fq )
{
	if ( !isQueEmpty(fq + 1) ) {
		QUEUE *nq = (fq + 1)->next;

		QueRemove(fq + 1);
		QueInsert(nq + 1, nq);
		QueRemove(nq);
		QueInsert(nq, fq);
	}

	QueRemove(fq);
}

/*
 * Register area
 *	Insert ent immediately posterior to que
 */
LOCAL void insertAreaQue( QUEUE *que, QUEUE *ent )
{
	ent->prev = que;
	ent->next = que->next;
	Assign(que->next->prev, ent);
	que->next = ent;
}

/*
 * Delete area
 */
LOCAL void removeAreaQue( QUEUE *aq )
{
	Mask(aq->prev)->next = aq->next;
	Assign(aq->next->prev, Mask(aq->prev));
}

/*
 * Reserve a new page that has an available continuous space of size bytes or larger.
 */
Inline QUEUE* newPage( size_t size, MACB *macb )
{
	QUEUE	*top, *end;
	VB	*bp;
	W	nblk;

	if ( macb->pagesz == 0U ) {
		return NULL;
	}

	/* Reserve page */
	nblk = toPageCount(size + (sizeof(QUEUE) * TSD_NPG_VAL_2), macb);
	bp = (*macb->getblk)(nblk, macb->mematr);
	if ( bp == NULL ) {
		return NULL;
	}

	/* Register in area queue */
	top = (QUEUE*)bp;
	end = (QUEUE*)(bp + ((UW)nblk * macb->pagesz)) - 1U;
	insertAreaQue(&macb->areaque, end);
	insertAreaQue(&macb->areaque, top);
	setAreaFlag(top, AREA_TOP);
	setAreaFlag(end, AREA_END);

	return top;
}

/*
 * Fragment and allocate
 */
Inline VP allocate( QUEUE *aq, size_t size, MACB *macb )
{
	QUEUE	*q;

	/* If a fragment is smaller than the minimum size,
	   include this fragment in other fragment. */
	if (( (UW)AreaSize(aq) - size) >= (MIN_FRAGMENT + sizeof(QUEUE))) {

		/* Divide the area in two. */
		q = (QUEUE*)((VB*)(aq + 1) + size);
		insertAreaQue(aq, q);

		/* Register a remaining area in free queue. */
		appendFreeArea(q, macb);
	}
	setAreaFlag(aq, AREA_USE);

	return (VP)(aq + 1);
}

/* ------------------------------------------------------------------------ */

/*
 * Obtain memory
 */
EXPORT void* _mem_malloc( size_t size, MACB *_macb )
{
	MACB	*macb = AlignMACB(_macb);
	QUEUE	*q;

	if ( macb->testmode > 0 ) {
		chkalloc(NULL, 0, macb);
	}

	if ( size > MAX_ALLOCATE ) {
		return NULL;
	}

	/* If it is smaller than the minimum fragment size,
	   allocate the minimum fragment size. */
	if (( size > 0U )&&( size < MIN_FRAGMENT )) {
		size = MIN_FRAGMENT;
	}

	size = ROUND(size);
	if ( size <= 0U ) {
		return NULL;
	}

	/* Search of free queue */
	q = searchFreeArea(size, macb);
	if ( q != &macb->freeque ) {
		/* If there is a free space, separate it from the free queue. */
		removeFreeQue(q);

		q = q - 1;
	} else {
		/* If there is no free space, reserve a new page. */
		q = newPage(size, macb);
		if ( q == NULL ) {
			return NULL;  /* Insufficient memory */
		}
	}

	/* Memory allocation */
	return allocate(q, size, macb);
}

/*
 * Obtain and clear memory
 */
EXPORT void* _mem_calloc( size_t nmemb, size_t size, MACB *macb )
{
	size_t	sz = nmemb * size;
	void	*p;

	/* Reserve memory */
	p = _mem_malloc(sz, macb);
	if ( p == NULL ) {
		return NULL;
	}

	/* Clear memory */
	return memset(p, 0, sz);
}

/*
 * Change memory allocation size
 */
EXPORT void* _mem_realloc( void *ptr, size_t size, MACB *_macb )
{
	MACB	*macb = AlignMACB(_macb);
	QUEUE	*aq;
	size_t	oldsz, sz;

	if ( macb->testmode > 0 ) {
		if ( !chkalloc(ptr, 0, macb) ) {
			return NULL;
		}
	}

	if ( size > MAX_ALLOCATE ) {
		return NULL;
	}

	/* If it is smaller than the minimum fragment size,
	   allocate the minimum fragment size. */
	if (( size > 0U )&&( size < MIN_FRAGMENT )) {
		size = MIN_FRAGMENT;
	}

	size = ROUND(size);

	aq = (QUEUE*)ptr - 1;

	if ( ptr != NULL ) {
		/* Current allocation size */
		oldsz = (size_t)AreaSize(aq);

		/* If the immediate succeeding space is free, merge them. */
		if ( !chkAreaFlag(aq->next, AREA_END|AREA_USE) ) {
			removeFreeQue(aq->next + 1);
			removeAreaQue(aq->next);
		}

		sz = (size_t)AreaSize(aq);
	} else {
		sz = oldsz = 0;
	}

	if ( size <= sz ) {
		if ( size > 0U ) {
			/* Divide the current space to allocate. */
			(void)allocate(aq, size, macb);
		} else {
			/* Release space */
			_mem_free(ptr, macb);
			ptr = NULL;
		}
	} else {
		/* Allocate new space. */
		void *newptr = _mem_malloc(size, macb);
		if ( newptr == NULL ) {
			/* Reallocate original space in original size. */
			if ( ptr != NULL ) {
				(void)allocate(aq, oldsz, macb);
			}
			return NULL;
		}

		if ( ptr != NULL ) {
			/* Copy the content */
			memcpy(newptr, ptr, oldsz);

			/* Release old space */
			_mem_free(ptr, macb);
		}
		ptr = newptr;
	}

	return ptr;
}

/*
 * Release memory
 */
EXPORT void  _mem_free( void *ptr, MACB *_macb )
{
	MACB	*macb = AlignMACB(_macb);
	QUEUE	*aq;

	if ( ptr == NULL ) {
		return;
	}

	if ( macb->testmode > 0 ) {
		if ( !chkalloc(ptr, 0, macb) ) {
			return;
		}
	}

	aq = (QUEUE*)ptr - 1;
	clrAreaFlag(aq, AREA_USE);

	if ( !chkAreaFlag(aq->next, AREA_END|AREA_USE) ) {
		/* Merge with the immediately succeeding free space */
		removeFreeQue(aq->next + 1);
		removeAreaQue(aq->next);
	}

	if ( !chkAreaFlag(aq, AREA_TOP) && !chkAreaFlag(aq->prev, AREA_USE) ) {
		/* Merge with the immediately preceding free space */
		aq = aq->prev;
		removeFreeQue(aq + 1);
		removeAreaQue(aq->next);
	}

	/* If the entire page becomes empty, release the page itself. */
	if ( chkAreaFlag(aq, AREA_TOP) && chkAreaFlag(aq->next, AREA_END) ) {
		/* Release page */
		removeAreaQue(aq->next);
		removeAreaQue(aq);
		(*macb->relblk)(aq);
	} else {
		/* Register free space in free queue. */
		appendFreeArea(aq, macb);
	}
}