heap.c

Linux下的类似softice的调试工具

/******************************************************************************
 *
 * Copyright (c) 2003 Gerhard W. Gruber
 *
 * PROJECT: pICE
 * $Source: /cvsroot/pice/pice/module/heap.c,v $
 * $Revision: 1.3 $
 * $Date: 2004/02/17 23:07:36 $
 * $Author: lightweave $
 * $Name:  $
 *
 * $Log: heap.c,v $
 * Revision 1.3  2004/02/17 23:07:36  lightweave
 *
 * Improved the DEBUG facillity and replaced the configuration handler with a
 * new code which now can read MS Windows INI style files. See CHANGES.txt for
 * more details.
 * Also added a macro which prevents compiling for kernels before 2.4.19.
 *
 * Revision 1.2  2003/06/18 22:00:22  lightweave
 * DEBUG and DEBUG_SERIAL added
 *
 *
 *****************************************************************************/

static char *ident = "$Header: /cvsroot/pice/pice/module/heap.c,v 1.3 2004/02/17 23:07:36 lightweave Exp $";


/*++

Copyright (c) 1998-2001 Klaus P. Gerlicher

Module Name:

    heap.c

Abstract:

    memory heap

Environment:

    LINUX 2.2.X
    Kernel mode only

Author:

    Klaus P. Gerlicher

Revision History:

    13-Mar-2001:    created

Copyright notice:

  This file may be distributed under the terms of the GNU Public License.

--*/
#include "remods.h"

#include <linux/vmalloc.h>

#include "precomp.h"

typedef struct _BLOCK_HDR
{
	struct _BLOCK_HDR	*prev, *next;
	PVOID			 	data_p;
	ULONG				size;
} BLOCK_HDR, *PBLOCK_HDR;

////////////////////////////////////////////////////////////////////////////////
// layout of memory heap
// 
// ********************************************* 
// * BLOCK_HDR 0							   * <- initially pointed to by pFree
// *-------------------------------------------* 
// *                                           * 
// *                                           * 
// *                                           * 
// *                                           * 
// *                                           *
// *-------------------------------------------*
// * BLOCK_HDR 1							   * 
// *-------------------------------------------*
//
////////////////////////////////////////////////////////////////////////////////

// root pointers to free and used list
BLOCK_HDR *pFree = NULL, *pUsed = NULL;

// original heap address for vfree()
VOID *pHeapAllocation = NULL;

// processor flag for interrupt suspension
static spinlock_t ulHeapLock;
static ULONG ulHeapFlags;
static ULONG ulHeapSize;

//*************************************************************************
// PICE_HeapEnterCritical()
//
//*************************************************************************
static void PICE_HeapEnterCritical(void) 
{ 
    spin_lock_irqsave(&ulHeapLock,ulHeapFlags);
} 
 
//*************************************************************************
// PICE_HeapLeaveCritical()
//
//*************************************************************************
static void PICE_HeapLeaveCritical(void) 
{ 
    spin_unlock_irqrestore(&ulHeapLock,ulHeapFlags);
} 

//*************************************************************************
// PICE_HEAP_PREV()
//
//*************************************************************************
PBLOCK_HDR PICE_HEAP_PREV(PBLOCK_HDR _p)			
{
	return _p->prev;
}

//*************************************************************************
// PICE_HEAP_NEXT()
//
//*************************************************************************
PBLOCK_HDR PICE_HEAP_NEXT(PBLOCK_HDR _p)			
{
	return _p->next;
}

//*************************************************************************
// PICE_HEAP_START()
//
//*************************************************************************
PVOID PICE_HEAP_START(PBLOCK_HDR _p)
{
	return (PVOID)_p;
}

//*************************************************************************
// PICE_HEAP_END()
//
//*************************************************************************
PVOID PICE_HEAP_END(PBLOCK_HDR _p)
{
	return (PVOID)((ULONG)_p + _p->size + sizeof(BLOCK_HDR)) ;
}

//*************************************************************************
// PICE_HEAP_INIT_BLOCK()
//
//*************************************************************************
void PICE_HEAP_INIT_BLOCK(PBLOCK_HDR _p,ULONG _size,PBLOCK_HDR _prev,PBLOCK_HDR _next)
{													
	_p->prev   = _prev;								
	_p->next   = _next;								
	_p->size   = _size;								
	_p->data_p = (PVOID)(_p+1);						
}

//*************************************************************************
// PICE_HEAP_JOIN_FREE_BLOCKS()
//
//*************************************************************************
BOOLEAN PICE_HEAP_JOIN_FREE_BLOCKS(ULONG size)
{
	BOOLEAN bResult = FALSE;
	PBLOCK_HDR pComp;
	PBLOCK_HDR _p;

restart:
	_p = pFree;
	while(_p)
	{
		pComp = pFree;
		while(pComp)
		{
			// adjacent blocks
			if(PICE_HEAP_END(pComp) == PICE_HEAP_START(_p))
			{
				// add memory to the free block
				pComp->size = _p->size + pComp->size + sizeof(BLOCK_HDR);

				if(_p == pFree)
					pFree = pFree->next;

				// remove the other block from free list
				if(PICE_HEAP_PREV(_p))
					PICE_HEAP_PREV(_p)->next = PICE_HEAP_NEXT(_p);
				if(PICE_HEAP_NEXT(_p))
					PICE_HEAP_NEXT(_p)->prev = PICE_HEAP_PREV(_p);

				// found a block after merge
				if(pComp->size >= size)
					return TRUE;

				goto restart;
			}
			pComp = PICE_HEAP_NEXT(pComp);
		}
		_p = PICE_HEAP_NEXT(_p);
	}

	return bResult;
}

//*************************************************************************
// PICE_HeapFindBlock()
//
// Find the blockheader a given pointer belings to. The pointer must be
// the one returned by PICE_HeapAlloc or PICE_HeapReAlloc. This will not
// work if the pointer is an arbitrary adress within a block returned by
// these functions.
//
//*************************************************************************
BLOCK_HDR *PICE_HeapFindBlock(VOID *p)
{
	 BLOCK_HDR *rc = NULL, *pCur;

	 if(p == NULL)
		  goto Quit;

	 pCur = pUsed;

	 while(pCur)
	 {
		  if(pCur->data_p == p)
		  {
			   rc = pCur;
			   break;
		  }
		  pCur = PICE_HEAP_NEXT(pCur);
	 }

Quit:
	 return(rc);
}

//*************************************************************************
// PICE_HeapInit()
//
//*************************************************************************
BOOLEAN PICE_HeapInit(ULONG size)
{
	BOOLEAN bResult = FALSE;

	// init heap spinlock
    spin_lock_init(&ulHeapLock);

	if(!pFree)
	{
		pFree = (PBLOCK_HDR)vmalloc(size);
		if(pFree)
		{
			pHeapAllocation = (PVOID)pFree;
			ulHeapSize = size;

			PICE_HEAP_INIT_BLOCK(pFree,ulHeapSize-sizeof(BLOCK_HDR),NULL,NULL);

			bResult = TRUE;
		}
	}

	return bResult;
}

//*************************************************************************
// PICE_HeapExit()
//
//*************************************************************************
void PICE_HeapExit(void)
{
#ifdef __PICE_MALLOC_DEBUG__
   PICE_HeapDumpDebug();
#endif // __PICE_MALLOC_DEBUG__

	if(pHeapAllocation )
		vfree(pHeapAllocation);

	ulHeapSize = 0L;
	pHeapAllocation = NULL;
}

//*************************************************************************
// PICE_IHeapAlloc()
//
//*************************************************************************
VOID *PICE_IHeapAlloc(ULONG size)
{
	BLOCK_HDR *p, *pNew;

	// spin forever until a block becomes available
	// NB: this could be never
	p = pFree;

	// out of memory
	if(!p)
	{
		//_asm int 3;
		return NULL;
	}

	// now check the free list for a block of size
	do
	{
		// found a chunk
		// 
		if(p->size >= (size + sizeof(*p)) )
		{
			// create a new block descriptor
			pNew = (PBLOCK_HDR)((ULONG)p->data_p + size);

			// remove it from the free list
			// an split the block creating a free and a used part
			PICE_HEAP_INIT_BLOCK(pNew, p->size - size - sizeof(*p), NULL, NULL);	
			pFree = pNew;
			if(PICE_HEAP_NEXT(pFree))
				PICE_HEAP_NEXT(pFree)->prev = pFree;

			// add it to the used list
			// initially used list is empty
			PICE_HEAP_INIT_BLOCK(p, size, NULL, pUsed);
            pUsed = p;
			if(PICE_HEAP_NEXT(pUsed))
				PICE_HEAP_NEXT(pUsed)->prev = pUsed;

			return p->data_p;
		}

		p = PICE_HEAP_NEXT(p);
	}while(p);

	return NULL;
}

//*************************************************************************
// PICE_HeapAlloc()
//
//*************************************************************************
VOID *PICE_HeapAlloc(ULONG size)
{
   VOID *pResult;

   DVPRINT(PICE_DEBUG, DBT_HEAP, DBL_INFO, "alloc %u bytes\n", size);

   PICE_HeapEnterCritical();	

#ifdef __PICE_MALLOC_DEBUG__
   PICE_HeapDumpDebug();
#endif // __PICE_MALLOC_DEBUG__

	pResult = PICE_IHeapAlloc(size);
	if(!pResult)
	{
		DVPRINT(PICE_DEBUG, DBT_HEAP, DBL_INFO, "retry try alloc %u bytes\n", size);

		PICE_HEAP_JOIN_FREE_BLOCKS(size);

		pResult = PICE_IHeapAlloc(size);
	}

	DVPRINT(PICE_DEBUG, DBT_HEAP, DBL_INFO, "%08X\n", pResult);

#ifdef __PICE_MALLOC_DEBUG__
   PICE_HeapDumpDebug();
#endif // __PICE_MALLOC_DEBUG__

	PICE_HeapLeaveCritical();	

	return pResult;
}

//*************************************************************************
// PICE_HeapReAlloc()
//
//*************************************************************************
VOID *PICE_HeapReAlloc(VOID *p, ULONG size)
{
   VOID *pResult = NULL;
   BLOCK_HDR *pBlock;

   DPRINT(PICE_DEBUG, DBT_HEAP, DBL_INFO, "alloc %p - %u bytes\n", p, size);

   PICE_HeapEnterCritical();

   if(size == 0 && p == NULL)
		goto Quit;

#ifdef __PICE_MALLOC_DEBUG__
   PICE_HeapDumpDebug();
#endif // __PICE_MALLOC_DEBUG__

   if(size)
   {
		pResult = PICE_HeapAlloc(size);
		if((pResult = PICE_HeapAlloc(size)) != NULL)
		{
			 // if the old pointer was NULL we are finished
			 // otherwise we have top copy over the old content
			 // to the new block.
			 if(p)
			 {
				  if((pBlock = PICE_HeapFindBlock(p)) == NULL)
				  {
					   DPRINT(PICE_DEBUG, DBT_HEAP, DBL_INFO, "pointer not found (%p)!\n", p);
					   goto Quit;
				  }
				  DPRINT(PICE_DEBUG, DBT_HEAP, DBL_INFO, "old size %i   new size %i!\n", pBlock->size, size);

				  // We only copy the smaller part of the two blocksizes.
				  memcpy(pResult, p, (size < pBlock->size) ? size : pBlock->size);
			 }
		}
   }
   else
		PICE_HeapFree(p);

   DPRINT(PICE_DEBUG, DBT_HEAP, DBL_INFO, "p\n", pResult);

#ifdef __PICE_MALLOC_DEBUG__
   PICE_HeapDumpDebug();
#endif // __PICE_MALLOC_DEBUG__

Quit:
	PICE_HeapLeaveCritical();	

	return pResult;
}


//*************************************************************************
// PICE_HeapFree()
//
//*************************************************************************
void PICE_HeapFree(PVOID pData)
{
	PBLOCK_HDR p = ((PBLOCK_HDR)pData) - 1;

	DPRINT(PICE_DEBUG, DBT_HEAP, DBL_INFO, "free %8p\n",pData);

	if(!pData)
	{
		DPRINT(PICE_DEBUG, DBT_HEAP, DBL_INFO, "NULL pointer\n");
		return;
	}

	PICE_HeapEnterCritical();	

	// remove from used list
	if(PICE_HEAP_PREV(p))
		PICE_HEAP_PREV(p)->next = PICE_HEAP_NEXT(p);
	if(PICE_HEAP_NEXT(p))
		PICE_HEAP_NEXT(p)->prev = PICE_HEAP_PREV(p);

	if(p == pUsed)
		pUsed = p->next;

	// add back to free list
	PICE_HEAP_INIT_BLOCK(p,p->size,NULL,pFree);	
	pFree = p;
	if(PICE_HEAP_NEXT(pFree))
		PICE_HEAP_NEXT(pFree)->prev = pFree;

	PICE_HeapLeaveCritical();	
}

//*************************************************************************
// PICE_HeapDump()
//
//*************************************************************************
void PICE_HeapDump(void)
{
	PBLOCK_HDR p;
	char tempHeap[256];
	ULONG ulTotal = 0,ulTotalFree = 0,ulTotalAlloc = 0;

	PICE_HeapEnterCritical();	

	Print(OUTPUT_WINDOW,"dump internal heap\n");
    if(WaitForKey()!=FALSE)
	{
		Print(OUTPUT_WINDOW,"free memory\n");
		if(WaitForKey()==FALSE)return;
 		p = pFree;
		while(p)
        {
            PICE_sprintf(tempHeap,"%8.X: %u\n",p,p->size);
            Print(OUTPUT_WINDOW,tempHeap);
            if(WaitForKey()==FALSE)return;

			ulTotal += p->size;
			ulTotalFree += p->size;

			p = p->next;
        }
	}

    if(WaitForKey()!=FALSE)
	{
		Print(OUTPUT_WINDOW,"allocated memory\n");
		if(WaitForKey()==FALSE)return;
		p = pUsed;
		while(p)
        {
            PICE_sprintf(tempHeap,"%8.X: %u\n",p,p->size);
            Print(OUTPUT_WINDOW,tempHeap);
            if(WaitForKey()==FALSE)return;

			ulTotal += p->size;
			ulTotalAlloc += p->size;

			p = p->next;
        }
	}

    PICE_sprintf(tempHeap,"total: %u free: %u alloc: %u\n",ulTotal,ulTotalFree,ulTotalAlloc);
    Print(OUTPUT_WINDOW,tempHeap);
    if(WaitForKey() == FALSE)return;

	PICE_HeapLeaveCritical();	
}

#ifdef __PICE_MALLOC_DEBUG__
//*************************************************************************
// PICE_HeapDumpDebug()
//
//*************************************************************************
void PICE_HeapDumpDebug(void)
{
   PBLOCK_HDR p;
   ULONG ulTotal = 0,ulTotalFree = 0,ulTotalAlloc = 0;

   PICE_HEAP_JOIN_FREE_BLOCKS(0xFFFFFFFF);

   DPRINT(PICE_DEBUG, DBT_HEAP, DBL_INFO, "debug dump internal heap\n");
   DPRINT(PICE_DEBUG, DBT_HEAP, DBL_INFO, "free memory\n");
   p = pFree;
   while(p)
   {
      DPRINT(PICE_DEBUG, DBT_HEAP, DBL_INFO, "%p: %u\n", p, p->size);

      ulTotal += p->size;
      ulTotalFree += p->size;

      p = p->next;
   }

   DPRINT(PICE_DEBUG, DBT_HEAP, DBL_INFO, "allocated memory\n");
   p = pUsed;
   while(p)
   {
		DPRINT(PICE_DEBUG, DBT_HEAP, DBL_INFO, "%p: %u\n", p, p->size);

      ulTotal += p->size;
      ulTotalAlloc += p->size;

      p = p->next;
   }

   DPRINT(PICE_DEBUG, DBT_HEAP, DBL_INFO, "total: %u\n",ulTotal);
   DPRINT(PICE_DEBUG, DBT_HEAP, DBL_INFO, "free: %u\n",ulTotalFree);
   DPRINT(PICE_DEBUG, DBT_HEAP, DBL_INFO, "alloc: %u\n",ulTotalAlloc);
}
#endif // __PICE_MALLOC_DEBUG__