bheap_new.c

深圳市微逻辑电子有限公司 巨果&#8226 Kingmos&reg 系统核心

/******************************************************
Copyright(c) 版权所有，1998-2003微逻辑。保留所有权利。
******************************************************/

/*****************************************************
文件说明：块堆管理,用在提供服务的模块里的动态分配，
		  释放时，将块按大小放到块管理容器，分配时，首先从
          块管理容器分配，如果没有分配到，则从系统分配
版本号：1.0.0
开发时期：2004-07-05
作者：李林
修改记录：
******************************************************/

#include <ewindows.h>
#include <bheap.h>

#include <eobjlist.h>

typedef struct _BLOCK_DATA
{
	USHORT wBlockSize;
	USHORT wReserve;//
#ifdef __DEBUG
	LONG   nCount;
#endif
	LPBYTE lpFreeBlock;
}BLOCK_DATA, FAR * LPBLOCK_DATA;

#define DEF_INC_BLOCKS 8
#define BHF_VARIABLE          0x1
typedef struct BLOCK_HEAP
{
	BYTE nTotalBlockCount;	//总的块对象 = nAllocBlockCount + nFreeBlockCount
	BYTE nAllocBlockCount;	//已使用块对象
	BYTE nFreeBlockCount;	//空闲块对象
    BYTE iRemainderIndex;
    LPBYTE lpFree;
    int uiFreeSize;
    UINT uiMaxBlockSize;
	HANDLE hThis;
	HANDLE hProcessHeap;
	UINT uOption;	//
//	LPUINT lpAllocList;
	CRITICAL_SECTION cs; 

	//BLOCK_DATA block[1];
	LPBLOCK_DATA lpBlock;
}BLOCK_HEAP, FAR * LPBLOCK_HEAP;

//#define MAX_BLOCK_POOLS ( sizeof( heap ) / sizeof( BLOCKHEAP ) ) 


#define INSERT_FREE_BLOCK( lpHeap, lpvBlock ) \
	do{\
	    *( (LPBYTE*)(lpvBlock) ) = (lpHeap)->lpFreeBlock;\
		(lpHeap)->lpFreeBlock = (LPBYTE)(lpvBlock);\
	}while(0)

#define REMOVE_FREE_BLOCK( lpHeap, lpRet ) \
	do{\
	    if( ((lpRet) = (lpHeap)->lpFreeBlock ) != NULL ) \
		    (lpHeap)->lpFreeBlock = *( (LPBYTE*)(lpHeap)->lpFreeBlock );\
	}while(0)

 //align to 4 bytes;
#define ALIGN_SIZE( uiSize ) ( ( (uiSize) + 7) & (~7) )

static LPBLOCK_DATA BlockHeap_AllocBlockObject( LPBLOCK_HEAP lpbh, UINT uiSize )
{
	//LPBLOCK_DATA = HeapAlloc( lpbh->hProcessHeap, HEAP_ZERO_MEMORY, sizeof( BLOCK_HEAP ) );
_again:
	if( lpbh->nFreeBlockCount )
	{
		LPBLOCK_DATA lpblkEnd, lpCur = lpbh->lpBlock;
		int count = lpbh->nAllocBlockCount;
		int cur;
		//得到快对应的位置（按块大小排序）
		for( cur = 0; cur < count; cur++, lpCur++ )
		{
			if( uiSize < lpCur->wBlockSize )
				break;
		}
		//移动数据
		lpblkEnd = lpCur + count;
		for( ;cur < count; count--, lpblkEnd-- )
		{
			*lpblkEnd = *(lpblkEnd - 1);
		}
		memset( lpCur, 0, sizeof( BLOCK_DATA ) );
		lpCur->wBlockSize = uiSize;
		lpbh->nAllocBlockCount++;
		lpbh->nFreeBlockCount--;
		lpbh->uiMaxBlockSize = MAX( uiSize, lpbh->uiMaxBlockSize );

		return lpCur;
	}
	else
	{	//没有足够的空闲位置，需要重新分配
		LPBLOCK_DATA lpBlock = HeapReAlloc( lpbh->hProcessHeap, 0, lpbh->lpBlock, (lpbh->nTotalBlockCount + DEF_INC_BLOCKS) * sizeof(BLOCK_DATA) );
		if( lpBlock )
		{	//分配成功
			lpbh->lpBlock = lpBlock;
			lpbh->nTotalBlockCount += DEF_INC_BLOCKS;
			lpbh->nFreeBlockCount = DEF_INC_BLOCKS;
			goto _again;
		}
	}
	return NULL;
}

static LPBLOCK_DATA BlockHeap_GetPtr( LPBLOCK_HEAP lpbh, UINT uiSize )
{
	//BLOCKHEAP * lpHeap = &heap[0];
    int i;
	int count = lpbh->nAllocBlockCount;
	LPBLOCK_DATA lpblk = lpbh->lpBlock;

	for( i = 0; i < count; i++, lpblk++ )
	{
		if( lpblk->wBlockSize >= uiSize )
		{
			if( lpbh->uOption & BHF_VARIABLE )
			{	//可变
				if( lpblk->wBlockSize < uiSize + 8 )
					return lpblk;
				//没有符合要求的，需要重新增加一个块描述对象
				lpblk = BlockHeap_AllocBlockObject( lpbh, uiSize );
				return lpblk;
			}
			else
				return lpblk;	//不可变，符合条件
		}
	}
	//没有找到合适的
	if( lpbh->uOption & BHF_VARIABLE )
	{  //可变块
		return BlockHeap_AllocBlockObject( lpbh, uiSize );
	}

	RETAILMSG( 1, ( "error heap size:uiSize=%d.\r\n", uiSize ) );
	return NULL;
}

static void FreeRemainder( LPBLOCK_HEAP lpbh, LPBYTE lpRemainder, UINT iRemainderSize )
{
	int i = lpbh->iRemainderIndex;
	LPBLOCK_DATA lpblk = lpbh->lpBlock;
	UINT uiMinBlockSize = lpblk->wBlockSize;

//	UINT uiSave;

	while( iRemainderSize >= uiMinBlockSize )
	{
		ASSERT( i < lpbh->nAllocBlockCount );
		if( lpblk->wBlockSize <= iRemainderSize )
		{
			INSERT_FREE_BLOCK( lpblk, lpRemainder );
			//KL_InterlockedIncrement( &heap[i].iMaxBlocks );//2003-06-04, DEL

			lpRemainder += lpblk->wBlockSize;
            iRemainderSize -= lpblk->wBlockSize; 
		}
		if( ++i == lpbh->nAllocBlockCount )
		{
			i = 0;
			lpblk = lpbh->lpBlock;
		}
		else
			lpblk++;
		//i = (i + 1) % MAX_BLOCK_POOLS;
	}

	//LockIRQSave( &uiSave );//2003-06-11, ADD
	
	lpbh->iRemainderIndex = i;
	//INTR_ON();
	//UnlockIRQRestore( &uiSave ); //2003-06-11, ADD
}

#define ALLOC_PAGE_SIZE   4096

static LPBYTE BlockHeap_Increase( LPBLOCK_HEAP lpbh, UINT uiFlags, int size )
{
	LPBYTE lpRet = NULL;

	//if( !(uiFlags & BLOCKHEAP_NO_SERIALIZE) )
	//{
	//	EnterCriticalSection( &lpbh->cs );
	//}

	if( lpbh->uiFreeSize >= size )
	{
		lpRet = lpbh->lpFree;
		lpbh->lpFree += size;
		lpbh->uiFreeSize -= size;
	}
	else
	{  //
		if( size <= ALLOC_PAGE_SIZE )
		{
			//if( !(uiFlags & BLOCKHEAP_NO_SERIALIZE) )
			//{
			//	LeaveCriticalSection( &lpbh->cs );
			//}
			lpRet = (LPBYTE)HeapAlloc( lpbh->hProcessHeap, 0, ALLOC_PAGE_SIZE );

			//if( !(uiFlags & BLOCKHEAP_NO_SERIALIZE) )
			//{
			//	EnterCriticalSection( &lpbh->cs );
			//}
			if(  lpRet )
			{
				LPBYTE lpRemainder;
				int uiRemainderSize;
				UINT uiFreeBytes = ALLOC_PAGE_SIZE;// - 8;
				
				//INTR_OFF();
				//			LockIRQSave( &uiSave ); //2003-06-11, ADD
	//			ASSERT( size < ALLOC_PAGE_SIZE );
//				{  // must size <= ALLOC_PAGE_SIZE - 8
	//				*( (LPUINT*)lpRet ) = lpbh->lpAllocList;
	//				lpbh->lpAllocList = (LPUINT)lpRet;
	//				lpRet = (LPBYTE)lpRet + 8; 
	//			}
				if( lpbh->uiFreeSize < (int)(uiFreeBytes - size) )
				{
					lpRemainder = lpbh->lpFree;
					uiRemainderSize = lpbh->uiFreeSize;
					
					lpbh->lpFree = lpRet + size;
					lpbh->uiFreeSize = uiFreeBytes - size;
				}
				else
				{
					lpRemainder = lpRet + size;
					uiRemainderSize = uiFreeBytes - size;
				}
				//INTR_ON();
				//			UnlockIRQRestore( &uiSave ); //2003-06-11, ADD
				
				FreeRemainder( lpbh, lpRemainder, uiRemainderSize );
			}
		}
		else
		{
			RETAILMSG( 1, ( "invalid blockheap size(%d).\r\n", size ) );
//			return NULL;//
		}
	}

	//if( !(uiFlags & BLOCKHEAP_NO_SERIALIZE) )
	//{
	//	LeaveCriticalSection( &lpbh->cs );
	//}
	
	return lpRet;
}

static UINT SortAndCompressSize( LPUINT lpuiDestSize, LPUINT lpuiSrcSize, UINT nCount )
{
	UINT nMin, nMinPos;
	UINT n;
	UINT uiValue;
	LPUINT lpui, lpuiStart; //
    UINT k;
	memcpy( lpuiDestSize, lpuiSrcSize, sizeof( UINT ) * nCount );
	//nStart = 0;

	k = nCount;
	lpuiStart = lpuiDestSize;
	while( k > 1 )
	{
		nMinPos = 0;
	    lpui = lpuiStart;

		nMin = *lpui++;
		n = 1;
		for( ; n < k; n++, lpui++ )
		{
			if( nMin > *lpui )
			{
				nMin = *lpui;
				nMinPos = n;
			}
		}
		uiValue = *lpuiStart;
		*lpuiStart = nMin;
		lpuiStart[nMinPos] = uiValue;
		k--;
		lpuiStart++;
	}
	//去掉相同的size值
	lpui = lpuiDestSize;
	nMin = *lpui;
	nMin = ALIGN_SIZE( nMin );
	*lpui++ = nMin;
	lpuiStart = lpui;
    for( k = 1; k < nCount; k++ )
	{
		UINT v = *lpuiStart;
        v = ALIGN_SIZE( v );
		ASSERT( nMin <= v );
		if( nMin != v )
		{
			*lpui++ = nMin = v;
		}
		lpuiStart++;
	}
	return lpui - lpuiDestSize;
}

HANDLE WINAPI BlockHeap_Create( LPUINT lpuiSize, UINT nCount )
{
	LPBLOCK_HEAP lpbh;
	UINT nRealCount;
	UINT uiSize[32];
	HANDLE hProcessHeap;
	LPUINT lpui;

	//UINT bhSize;
	if( lpuiSize && nCount )
	{	//不可变块对象
		UINT i;

		
		if( nCount == 0 || nCount > 32 )
			return NULL;
		for( lpui = lpuiSize, i = 0; i < nCount; i++, lpui++ )
		{
			if( *lpui > ALLOC_PAGE_SIZE )
				return NULL;
		}
		// 将lpuiSize的值由小到大排例
		nRealCount = SortAndCompressSize( uiSize, lpuiSize, nCount );
	}
	else
		nRealCount = DEF_INC_BLOCKS;
		
//	bhSize = nRealCount  * sizeof( BLOCK_DATA ) + sizeof( BLOCK_HEAP );
	lpbh = HeapAlloc( hProcessHeap = GetProcessHeap(), HEAP_ZERO_MEMORY, sizeof( BLOCK_HEAP ) );
	if( lpbh )
	{			
		BLOCK_DATA * lpBlock = HeapAlloc( hProcessHeap, HEAP_ZERO_MEMORY, nRealCount * sizeof( BLOCK_DATA ) );
		if( lpBlock )
		{
			lpbh->lpBlock = lpBlock;
			lpbh->hProcessHeap = hProcessHeap;
			lpbh->nTotalBlockCount = nRealCount;
			lpbh->hThis = (HANDLE)PTR_TO_HANDLE( lpbh );
			if( lpuiSize && nCount )
			{	//不可变块对象
				UINT i;
				lpui = uiSize;				
				for( i = 0; i < nRealCount; i++, lpui++ )
				{
					lpbh->lpBlock[i].wBlockSize = *lpui; 
				}
				lpbh->uiMaxBlockSize = uiSize[nRealCount-1];
				lpbh->nAllocBlockCount = nRealCount;
			}
			else
			{
				lpbh->uOption = BHF_VARIABLE;