/******************************************************************** 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_MEMstatic 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 endstatic 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);