heap.cpp

一本叫自己动手写嵌入式操作系统的书的源代码,作者是蓝枫叶,详细介绍了如何写一个嵌入式操作系统,而不是操作系统

				lpTmpHeader->lpNext = lpFreeBlock->lpNext;
				lpTmpHeader->lpPrev = lpFreeBlock->lpPrev;
				lpTmpHeader->lpNext->lpPrev = lpTmpHeader;
				lpTmpHeader->lpPrev->lpNext = lpTmpHeader;

				lpFreeBlock->dwBlockSize = dwSize;
				lpFreeBlock->dwFlags     |= BLOCK_FLAGS_USED;
				lpFreeBlock->dwFlags     &= ~BLOCK_FLAGS_FREE;  //Clear the free flags.
				lpFreeBlock->lpPrev      = NULL;
				lpFreeBlock->lpNext      = NULL;
				lpResult                 = (LPVOID)((DWORD)lpFreeBlock
					+ sizeof(__FREE_BLOCK_HEADER));
				goto __TERMINAL;
			}
			else  //Now need to split,return the block is OK.
			{
				//
				//Delete the free block from free block list.
				//
				lpFreeBlock->lpNext->lpPrev = lpFreeBlock->lpPrev;
				lpFreeBlock->lpPrev->lpNext = lpFreeBlock->lpNext;
				lpFreeBlock->dwFlags        |= BLOCK_FLAGS_USED;
				lpFreeBlock->dwFlags        &= ~BLOCK_FLAGS_FREE;  //Clear free bit.
				lpFreeBlock->lpNext         = NULL;
				lpFreeBlock->lpPrev         = NULL;
				lpResult = (LPVOID)((DWORD)lpFreeBlock + sizeof(__FREE_BLOCK_HEADER));
				goto __TERMINAL;
			}
		}
		lpFreeBlock = lpFreeBlock->lpNext;  //Check the next block.
	}
	if(lpResult)    //Have found a block.
		goto __TERMINAL;
	//
	//If can not find a statisfying block in above process,we should allocate a
	//new virtual area according to dwSize,insert the virtual area into free list,
	//then repeat above process.
	//
	lpVirtualArea = (__VIRTUAL_AREA_NODE*)GET_KERNEL_MEMORY(sizeof(__VIRTUAL_AREA_NODE));
	if(NULL == lpVirtualArea)  //Can not allocate kernel memory.
		goto __TERMINAL;
	lpVirtualArea->dwAreaSize     = ((dwSize + sizeof(__FREE_BLOCK_HEADER))
		> DEFAULT_VIRTUAL_AREA_SIZE) ?
		(dwSize + sizeof(__FREE_BLOCK_HEADER)) : DEFAULT_VIRTUAL_AREA_SIZE;

	lpVirtualArea->lpStartAddress = GET_VIRTUAL_AREA(lpVirtualArea->dwAreaSize);
	if(NULL == lpVirtualArea->lpStartAddress)  //Can not get virtual area.
	{
		RELEASE_KERNEL_MEMORY((LPVOID)lpVirtualArea);
		goto __TERMINAL;
	}
	//
	//Insert the virtual area node object into virtual area list
	//of current heap object.
	//
	lpVirtualArea->lpNext       = lpHeapObject->lpVirtualArea;
	lpHeapObject->lpVirtualArea = lpVirtualArea;
	//
	//Now,insert the free block(virtual area) into free list of the
	//heap object.
	//
	lpTmpHeader = (__FREE_BLOCK_HEADER*)lpVirtualArea->lpStartAddress;
	lpTmpHeader->dwFlags |= BLOCK_FLAGS_FREE;
	lpTmpHeader->dwFlags &= ~BLOCK_FLAGS_USED;  //Clear the used flags.
	lpTmpHeader->dwBlockSize = lpVirtualArea->dwAreaSize - sizeof(__FREE_BLOCK_HEADER);

	lpTmpHeader->lpNext  = lpHeapObject->FreeBlockHeader.lpNext;
	lpTmpHeader->lpPrev  = &lpHeapObject->FreeBlockHeader;
	lpTmpHeader->lpNext->lpPrev = lpTmpHeader;
	lpTmpHeader->lpPrev->lpNext = lpTmpHeader;
	//
	//Now,call HeapAlloc again,this time must successful.
	//
	lpResult = HeapAlloc(lpHeapObject,dwSize);

__TERMINAL:
	return lpResult;
}

//
//The following routine is a helper routine,used to combine several small
//free blocks into one big free block.
//The combine unit is a virtual area,so,a problem may exists:if two virtual
//areas,one's end address is the same as the other's start address,so in normal
//case,these two virtual area should be combined into one big block.But in 
//current implementation,this function is implemented by Hello China,in fact,
//this function have very seldom influence the efficiency.
//This routine does the following actions:
// 1. From the first block,check if there are at least two blocks free and
//    consecutive;
// 2. If so,combine the two blocks into one block,and remove one from free
//    list;
// 3. Until reach the end position of the virtual area.
//
static VOID CombineBlock(__VIRTUAL_AREA_NODE* lpVirtualArea,__HEAP_OBJECT* lpHeapObj)
{
	__FREE_BLOCK_HEADER*           lpFirstBlock     = NULL;
	__FREE_BLOCK_HEADER*           lpSecondBlock    = NULL;
	LPVOID                         lpEndAddr        = NULL;

	if((NULL == lpVirtualArea) || (NULL == lpHeapObj)) //Invalid parameters.
		return;

	lpEndAddr     = (LPVOID)((DWORD)lpVirtualArea->lpStartAddress
		+ lpVirtualArea->dwAreaSize);

	lpFirstBlock  = (__FREE_BLOCK_HEADER*)lpVirtualArea->lpStartAddress;
	lpSecondBlock = (__FREE_BLOCK_HEADER*)((DWORD)lpFirstBlock
		+ sizeof(__FREE_BLOCK_HEADER)
		+ lpFirstBlock->dwBlockSize);  //Now,lpSecondBlock pointing to the second block.

	while(TRUE)
	{
		if(lpEndAddr == (LPVOID)lpSecondBlock) //Reach the end of the virtual area.
			break;
		if((lpFirstBlock->dwFlags & BLOCK_FLAGS_FREE) &&
		   (lpSecondBlock->dwFlags & BLOCK_FLAGS_FREE))  //Two blocks all free,combine it.
		{
			lpFirstBlock->dwBlockSize += lpSecondBlock->dwBlockSize;
			lpFirstBlock->dwBlockSize += sizeof(__FREE_BLOCK_HEADER);
			//
			//Delete the second block from free list.
			//
			lpSecondBlock->lpNext->lpPrev = lpSecondBlock->lpPrev;
			lpSecondBlock->lpPrev->lpNext = lpSecondBlock->lpNext;

			lpSecondBlock = (__FREE_BLOCK_HEADER*)((DWORD)lpFirstBlock
				+ sizeof(__FREE_BLOCK_HEADER)
				+ lpFirstBlock->dwBlockSize);  //Update the second block.
			continue;   //Continue to next round.
		}
		if((lpFirstBlock->dwFlags & BLOCK_FLAGS_USED) ||
		   (lpSecondBlock->dwFlags & BLOCK_FLAGS_USED)) //Any block is used.
		{
			lpFirstBlock  = lpSecondBlock;
			lpSecondBlock = (__FREE_BLOCK_HEADER*)((DWORD)lpFirstBlock
				+ sizeof(__FREE_BLOCK_HEADER)
				+ lpFirstBlock->dwBlockSize);
			continue;
		}	
	}
}

//
//The implementation of HeapFree routine.
//This routine does the following:
// 1. Insert the memory block freed by user into heap's free list;
// 2. Find which virtual area this address belong to;
// 3. Combine the virtual area by calling CombineBlock routine;
// 4. Check if the virtual area to be combined is ONE free block,
//    If so,then release the virtual area and virtual area node
//    object.
//
static VOID HeapFree(LPVOID lpStartAddr,__HEAP_OBJECT* lpHeapObj)
{
	__FREE_BLOCK_HEADER*    lpFreeHeader  = NULL;
	__VIRTUAL_AREA_NODE*    lpVirtualArea = NULL;
	__VIRTUAL_AREA_NODE*    lpVirtualTmp  = NULL;

	if((NULL == lpStartAddr) || (NULL == lpHeapObj)) //Invalid parameter.
		return;

	lpFreeHeader = (__FREE_BLOCK_HEADER*)((DWORD)lpStartAddr
		- sizeof(__FREE_BLOCK_HEADER));  //Get the block's header.
	if(!(lpFreeHeader->dwFlags & BLOCK_FLAGS_USED)) //Abnormal case.
		return;

	//
	//Now,check the block to be freed belong to which virtual area.
	//
	lpVirtualArea = lpHeapObj->lpVirtualArea;
	while(lpVirtualArea)
	{
		if(((DWORD)lpStartAddr > (DWORD)lpVirtualArea->lpStartAddress) &&
		   ((DWORD)lpStartAddr < (DWORD)lpVirtualArea->lpStartAddress
		   + lpVirtualArea->dwAreaSize))  //Belong to this virtual area.
		{
			break;
		}
		lpVirtualArea = lpVirtualArea->lpNext;
	}
	if(NULL == lpVirtualArea)  //Can not find a virtual area that countains
		                       //the free block to be released.
	{
		//printf("\r\nFree a invalid block: can not find virtual area.");
	    return;
	}

	//
	//Now,should insert the free block into heap object's free list.
	//
	lpFreeHeader->dwFlags |= BLOCK_FLAGS_FREE;
	lpFreeHeader->dwFlags &= ~BLOCK_FLAGS_USED;  //Clear the used flags.
	lpFreeHeader->lpPrev   = &lpHeapObj->FreeBlockHeader;
	lpFreeHeader->lpNext   = lpHeapObj->FreeBlockHeader.lpNext;
	lpFreeHeader->lpPrev->lpNext = lpFreeHeader;
	lpFreeHeader->lpNext->lpPrev = lpFreeHeader;

	CombineBlock(lpVirtualArea,lpHeapObj);      //Combine this virtual area.
	//
	//Now,should check if the whole virtual area is a free block.
	//If so,delete the free block from free list,then release the 
	//virtual area to system.
	//
	lpFreeHeader = (__FREE_BLOCK_HEADER*)(lpVirtualArea->lpStartAddress);
	if((lpFreeHeader->dwFlags & BLOCK_FLAGS_FREE) &&
	   (lpFreeHeader->dwBlockSize + sizeof(__FREE_BLOCK_HEADER)
	   == lpVirtualArea->dwAreaSize))
	{
		//
		//Delete the free block from free list.
		//
		lpFreeHeader->lpPrev->lpNext = lpFreeHeader->lpNext;
		lpFreeHeader->lpNext->lpPrev = lpFreeHeader->lpPrev;
		//
		//Now,should delete the virtual area node object from
		//heap object's virtual list.
		//
		lpVirtualTmp = lpHeapObj->lpVirtualArea;
		if(lpVirtualTmp == lpVirtualArea)  //The first virtual node.
		{
			lpHeapObj->lpVirtualArea = lpVirtualArea->lpNext;
		}
		else    //Not the first one.
		{
			while(lpVirtualTmp->lpNext != lpVirtualArea)
			{
				lpVirtualTmp = lpVirtualTmp->lpNext;
			}
			lpVirtualTmp->lpNext = lpVirtualArea->lpNext;  //Delete it.
		}
		//
		//Then,should release the virtual area and virtual area node 
		//object.
		//
		RELEASE_VIRTUAL_AREA((LPVOID)lpVirtualArea->lpStartAddress);
		RELEASE_KERNEL_MEMORY((LPVOID)lpVirtualArea);
	}

	return;
}

/*************************************************************************
**************************************************************************
**************************************************************************
**************************************************************************
*************************************************************************/
//
//The declaration of HeapManager object.
//There is only one HeapManager object in whole system.
//

__HEAP_MANAGER HeapManager = {
	CreateHeap,                   //CreateHeap routine.
	DestroyHeap,                  //DestroyHeap routine.
	DestroyAllHeap,               //DestroyAllHeap routine.
	HeapAlloc,                    //HeapAlloc routine.
	HeapFree                      //HeapFree routine.
};

//
//The following are malloc routine's implementation.
//This routine create a default heap,if not exists yet,then allocate
//memory from this default heap.
//
LPVOID malloc(DWORD dwSize)
{
	DWORD            dwFlags    = NULL;
	LPVOID           lpResult   = NULL;
	__HEAP_OBJECT*   lpHeapObj  = NULL;
	DWORD            dwHeapSize = 0L;

	if(0 == dwSize)  //Invalid parameter.
		return lpResult;

	if(NULL == CURRENT_KERNEL_THREAD->lpDefaultHeap)  //Should create one.
	{
		dwHeapSize = (dwSize + sizeof(__FREE_BLOCK_HEADER) > DEFAULT_VIRTUAL_AREA_SIZE) ?
			(dwSize + sizeof(__FREE_BLOCK_HEADER)) : DEFAULT_VIRTUAL_AREA_SIZE;
		lpHeapObj = CreateHeap(dwHeapSize);
		if(NULL == lpHeapObj)  //Can not create heap object.
			return lpResult;
		__ENTER_CRITICAL_SECTION(NULL,dwFlags);
		CURRENT_KERNEL_THREAD->lpDefaultHeap = (LPVOID)lpHeapObj;
		__LEAVE_CRITICAL_SECTION(NULL,dwFlags);
	}
	else
	{
		lpHeapObj = (__HEAP_OBJECT*)CURRENT_KERNEL_THREAD->lpDefaultHeap;
	}
	return HeapAlloc(lpHeapObj,dwSize);
}

//
//The implementation of free routine.
//This routine frees a memory block,to the default heap object of
//current kernel thread.
//
VOID free(LPVOID lpMemory)
{
	__HEAP_OBJECT*      lpHeapObj = NULL;
	
	if(NULL == lpMemory)
		return;

	lpHeapObj = (__HEAP_OBJECT*)CURRENT_KERNEL_THREAD->lpDefaultHeap;
	if(NULL == lpHeapObj)    //Invalid case.
		return;
	HeapFree(lpMemory,lpHeapObj);
}