rmmmhomemade.c

神龙解压卡Linux下的完整开发包,绝对是超值超值超值

/*****************************************************************
*** Copyright (c) 2002 Sigma Designs Inc. All rights reserved. ***
*****************************************************************/

#define RM_LIBRARY_SELF_COMPILING 1

#include "../../rmdef/rmdef.h"
#include "../include/rmmmhomemade.h"

#ifdef USE_LEAK_CHECKER
#include "../../rmleakchecker/include/rmleakchecker.h"
#endif //USE_LEAK_CHECKER


// author: Vincent Trinh. Rewritten by Emmanuel Michon; added hash codes.
/*
  VOCABULARY

  RMCreateZone makes a large amount of memory (called Zone)
  ready to be cut into smaller units.
  
  The Zone is split in variable size, contiguous ``memory blocks''.
 
  Each block has a header described by the memoryBlockHeader struct,
  remaining part is usable data.

  A memory block is either free or occupied.

  RMMallocInZone, RMFreeInZone implement usual allocation
  functions inside this zone using memory blocks 
  (there is no realloc function). At creation step
  you can specify a proper alignment for the pointers
  you create in the Zone.

  Unlike traditional free() call, free() has a valid return
  value and fails if called on bogus pointer or twice on the
  same pointer.
  
  The functions increase of decrease an allocCount counter
  per zone; RMDeleteZone can only succeed if this count is 0.

  [RMDeleteZone does not try to free the zone, as well as RMCreateZone
  does not call the system libc function malloc itself.]

  DETAILS

  We say that a block A is ``before'' (resp. ``after'') another block B 
  (free or occupied) if address_of_A < (resp. >) address_of_B.

  We call ``neighbors'' two blocks (free or occupied) that are contiguous
  in memory. See AmILeftNeighbor function for algorithmic definition.

  All the available free memory blocks are linked in increasing
  address order using the ``next'' field. Only the free blocks are
  linked together.

  At the beginning there is one big free memory block. 

  RMMallocInZone goes thru all free blocks:
    - if too small, goes to the next one,
    - if exact size, removed from the linked list,
    - if too large, split: one part is removed from the linked 
      list and creation of a new memory block as the remaining part.
    - computes a 64bit hash code.

  RMFreeInZone(... ptr ...) rewinds to the memory block header address
  from the memory block data address ptr.
    - it checks if this is a valid header by computing a hash function
      on its supposed size and address and comparing the result. Since this function
      has a 64bit result, it is very unlikely a bogus RMFreeInZone (... wrongptr ...)
      computes the good hash result.
    - the occupied block is reintegrated to the free block list. The hash
      is blanked.
    - if the occupied block has a left or right (or both) neighbor block part of the
      free list, free blocks are gathered to make one bigger. See function
      for algorithm detail.
      
  When block gathering happens, the middle blocks header data becomes useless and
  we say the middle blocks ``disappear''.
  For efficiency reasons, there is no special attempt to dump zeroes 
  in former struct fields or freed data. So you really cannot assume memory 
  returned by RMMallocInZone contains zeroes (use RMCallocInZone for this). However, 
  hash codes are always overridden (to disappearedHash) to avoid bogus hashes in this case.
  
  [Note1: field policy.
  * ``hash'' field is HASH(dataaddress,size) for an occupied block
  and is freeBlockHash for a free block.
  * ``size'' field is always up to date, occupied or free block
  * only _free_ memoryBlockHeaders are linked together with the 
  ``next'' filed. Occupied block's ``next'' field content can be 
  considered as garbage.]

  [Note2: no need to store the usable data address in memoryBlockHeader
  since it is always the address of the header plus HeaderSkip(pZone->alignment),
  see function DataAddress.]

  [Note3: pFirstFree field in RMmemoryZone points to the first free
  memory block header. As such, it changes as soon as the first
  block is occupied and all the time. When RMDeleteZone is called, it 
  first checks the balance between RMMallocInZone/RMFreeInZone, so pFirstFree 
  has always come back to its original value.]

  [Note4: since modifications on the free block list can only happen in RMFreeInZone,
  and this function takes care of gathering free neighbor blocks when possible, 
  the free block list is only made of non-contiguous free blocks.]
 */

// debugging output for this module.
#if 0
  #define MEMDBG ENABLE
#else
  #define MEMDBG DISABLE
#endif

// The debugging option will make sure all allocated memory is returned initialized with
// 0x66 in it. As soon as a free happens, 0x66 are filled in memory. This should allow
// users to detect dangling references early.
#ifdef _DEBUG
#define TRASH_MEM 1
#else //_DEBUG
#undef TRASH_MEM
#endif //_DEBUG

#ifdef TRASH_MEM
static inline void trashMemory (void *ptr, RMuint32 size)
{
	RMMemset (ptr, 0x66, size);
}
#endif // TRASH_MEM

/** Defines a Zone. Do not interact with fields directly. 
    Use rmmemorymanager API 

    [Each Zone has to be locked with a semaphore that cannot
    be a RMsemaphore since rmsemaphores.c functions can call allocation
    functions. It has to be the primitive semaphore type of your
    operating system and we assume it is 
    less than MAX_PRIMITIVE_SEMAPHORE_SIZE bytes]
 */
struct _RMmemoryZone {
	void *pFirstFree;
	RMuint8 *beginning;
	RMuint32 totalSize;
	RMalignment alignment;
	RMuint32 successfulMallocs,successfulFrees;
	RMint32 occupiedSize; // occupied size excludes headers (allow negative to trap corruption)
#ifdef USE_LEAK_CHECKER
	RMleakChecker leakChecker; // a platform-dependant pointer to the leak checker zone-related data.
	RMbool recordLeaks; // whether or not to record leaks.
#endif // USE_LEAK_CHECKER
	RMint32 maxSize;
	RMcriticalsection cs;
	RMcriticalsectionOps *pCSops;
};

static const RMuint64 one=1;
static const RMuint64 freeBlockHash  =(((RMuint64)0xfeedface)<<32)+0xdeadbeef; // gcc wants ULL at the end
static const RMuint64 disappearedHash=(((RMuint64)0xabacabab)<<32)+0xacabfada;

/** Defines the memory block header. Do not interact with fields directly */
typedef struct tagmemoryBlockHeader{
	RMuint64 hash;
	RMuint32 size;
	struct tagmemoryBlockHeader *next;
} memoryBlockHeader;

static inline RMuint8 *NextAlignedAddress(RMuint8 *address,RMalignment alignment)
{
	RMuint32 modulo=((RMuint32)address)%alignment;
	
	if (modulo) 
		return address+alignment-modulo;
	else
		return address;
}

static inline RMuint32 HeaderSkip(RMalignment alignment)
{
	return (RMuint32)NextAlignedAddress((RMuint8 *)sizeof(memoryBlockHeader),alignment);
}

static inline RMuint8 *DataAddress(memoryBlockHeader *pHeader,RMalignment alignment)
{
	return ((RMuint8 *)(pHeader)) + HeaderSkip(alignment);
}

static inline RMbool AmIBefore(memoryBlockHeader *pU,memoryBlockHeader *pV) 
{
	return ((RMuint32)(pU)<(RMuint32)(pV));
}
		
static inline RMbool AmILeftNeighbor(memoryBlockHeader *pU,memoryBlockHeader *pV,RMalignment alignment) 
{
	return ((memoryBlockHeader *)(DataAddress(pU,alignment)+(pU)->size)==(pV));
}

static inline RMuint64 Hash(RMuint32 x,RMuint32 y) 
{
	RMuint64 u=((RMuint64)x)^((RMuint64)y);

	return u*u*u-one;
}

static RMmemoryZone zones[RMMAXMEMORYZONES];

void RMCreateZone(RMuint32 zid,
		  RMalignment alignment,
		  RMuint8 *pSubmittedBuffer,
		  RMuint32 submittedSize,
		  RMcriticalsectionOps *pCSops)
{
	RMmemoryZone *pZone=&zones[zid];

	RMuint8 *pRectifiedBuffer;
	RMuint32 rectifiedSize;
	memoryBlockHeader **ppFirstFree;

#ifdef TRASH_MEM
	trashMemory (pSubmittedBuffer, submittedSize);
#endif

	ppFirstFree=(memoryBlockHeader **)(&(pZone->pFirstFree));
	
	if (pSubmittedBuffer==NULL) RMPanic(RM_FATALINVALIDPOINTER);

	// align beginning if needed.
	pRectifiedBuffer=NextAlignedAddress(pSubmittedBuffer,alignment);
	// rectify the size.
	rectifiedSize=submittedSize-(pRectifiedBuffer-pSubmittedBuffer);
	// make size a multiple of alignment.
	rectifiedSize=(rectifiedSize/alignment)*alignment;
	if ((pRectifiedBuffer!=pSubmittedBuffer)||(rectifiedSize!=submittedSize)) 
		RMDBGLOG((MEMDBG,"RMCreateZone: rectified (%p,%ld) to (%p,%ld)\n",pSubmittedBuffer,submittedSize,pRectifiedBuffer,rectifiedSize));
	
	pZone->beginning=pRectifiedBuffer;
	pZone->totalSize=rectifiedSize;
	pZone->alignment=alignment;
	pZone->successfulMallocs=0;
	pZone->successfulFrees=0;
	pZone->occupiedSize=0;
	pZone->maxSize = 0;

	// define the first free block as all the buffer.
	*ppFirstFree=(memoryBlockHeader *)pRectifiedBuffer;
	(*ppFirstFree)->size=rectifiedSize-HeaderSkip(pZone->alignment);
	(*ppFirstFree)->next=(memoryBlockHeader *)NULL;

#ifdef USE_LEAK_CHECKER
	pZone->leakChecker = RMCreateLeakChecker ();

#endif

	pZone->pCSops=pCSops;
	if (pZone->pCSops!=NULL) pZone->cs=pZone->pCSops->Create();

	RMDBGLOG((ENABLE,"RMCreateZone: %lu bytes zone ready\n",pZone->totalSize));
}

RMstatus RMDeleteZone(RMuint32 zid)
{
	RMmemoryZone *pZone=&zones[zid];

	if ((pZone->successfulMallocs-pZone->successfulFrees)!=0 ||
	    pZone->occupiedSize!=0) {
		RMDBGLOG((ENABLE,
			  "RMDeleteZone: shame on you, memory leak (%lu allocations, %lu bytes)\n",
			  (pZone->successfulMallocs-pZone->successfulFrees),
			  pZone->occupiedSize
			  ));
		return RM_ERRORMEMORYISNOTFREE;
	}

	if (pZone->pCSops!=NULL) pZone->pCSops->Delete(pZone->cs);

#ifdef USE_LEAK_CHECKER
	RMDeleteLeakChecker (pZone->leakChecker);
#endif
	RMDBGLOG((ENABLE,
		  "RMDeleteZone: peak usage=%lu/%lu bytes (%ld%%)\n",
		  pZone->maxSize,
		  pZone->totalSize,
		  100*pZone->maxSize/pZone->totalSize));
	
	return RM_OK;
}

void *RMMallocInZone(RMuint32 zid,RMuint32 submittedSize)
{
	RMmemoryZone *pZone=&zones[zid];

	RMuint32 rectifiedSize;
	memoryBlockHeader *pCurrent,*pPrevious;

	memoryBlockHeader **ppFirstFree=(memoryBlockHeader **)(&(pZone->pFirstFree));

	if (submittedSize==0) 
		RMPanic(RM_FATALASKEDZEROSIZEMALLOC);

	if (pZone->pCSops!=NULL) pZone->pCSops->Enter(pZone->cs);

	rectifiedSize=(RMuint32)NextAlignedAddress((RMuint8 *)submittedSize,pZone->alignment);

	pPrevious=(memoryBlockHeader *)NULL;
	pCurrent=*ppFirstFree;

	while (pCurrent) {
		if (pCurrent->size==rectifiedSize) {
			// simply remove the block from the linked list
			if (pPrevious) {
				RMDBGLOG((MEMDBG,"RMMallocInZone: EQUALITY, MIDDLE OF LIST\n"));
				pPrevious->next=pCurrent->next;
			}
			else {
				RMDBGLOG((MEMDBG,"RMMallocInZone: EQUALITY, BEGINNING OF LIST\n"));
				*ppFirstFree=pCurrent->next;
			}
			
			goto returnok;
		}
		
		if (pCurrent->size>rectifiedSize+HeaderSkip(pZone->alignment)) {
			// split the block
			memoryBlockHeader *pNewBlock;

			pNewBlock=(memoryBlockHeader *)(DataAddress(pCurrent,pZone->alignment)+rectifiedSize);
			pNewBlock->size=pCurrent->size-rectifiedSize-HeaderSkip(pZone->alignment);
			pNewBlock->next=pCurrent->next;

			pCurrent->size=rectifiedSize;
			
			if (pPrevious) {
				RMDBGLOG((MEMDBG,"RMMallocInZone: INFERIORITY, MIDDLE OF LIST\n"));
				pPrevious->next=pNewBlock;
			}
			else {
				RMDBGLOG((MEMDBG,"RMMallocInZone: INFERIORITY, BEGINNING OF LIST\n"));
				*ppFirstFree=pNewBlock;
			}

			goto returnok;
		}
		
		pPrevious=pCurrent;
		pCurrent=pCurrent->next;

		//RMDBGLOG((MEMDBG,"(RMMallocInZone: hop to next free block)\n"));
	}
	
	// failure (out of memory)
	
	if (pZone->pCSops!=NULL) pZone->pCSops->Leave(pZone->cs);
	
	RMDBGLOG((ENABLE,"RMMallocInZone: could not allocate %ld bytes \n", submittedSize));
#ifdef USE_LEAK_CHECKER
	RMPrintBackTrace ();
	RMPrintLeaksLeakChecker (pZone->leakChecker);
#endif // USE_LEAK_CHECKER
	RMPanic(RM_FATALOUTOFMEMORY);
	
	return NULL;
	
 returnok:
	pCurrent->hash=Hash((RMuint32)DataAddress(pCurrent,pZone->alignment),rectifiedSize);
	pZone->successfulMallocs++;
	pZone->occupiedSize+=rectifiedSize;

	pZone->maxSize=RMmax(pZone->maxSize,pZone->occupiedSize);