rmmmhomemade.c

神龙卡开发原代码

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

#define RM_LIBRARY_SELF_COMPILING 1

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

// 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 Memory Block Header struct mbh,
  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 32bit 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 32bit 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 and >0, for occupied or free blocks.
  * only _free_ mbhs 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 mbh
  since it is always the address of the header plus HeaderSkip(pZ->alignment),
  see function DataAddress.]

  [Note3: pFirstFree field in struct mz 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 LOCALDBG ENABLE
#else
#define LOCALDBG DISABLE
#endif

struct mz {
	struct mbh *pFirstFree;
	RMuint8 *beginning;
	RMuint32 totalSize;
	RMalignment alignment;
	RMuint32 successfulMallocs,successfulFrees;
	RMint32 occupiedSize; // occupied size excludes headers (allow negative to trap corruption)
	RMint32 maxSize;
	void *syncCookie;
};

static const RMuint32 freeBlockHash  =0xfeedface;
static const RMuint32 disappearedHash=0xdeadbeef;

struct mbh {
	RMuint32 hash;
	RMuint32 size;
	struct mbh *next;
};

// classic way (type safe)
#define MMREAD8(mac,address) (*(RMuint8 *)(address))
#define MMWRITE8(mac,address,value) do { *(RMuint8 *)(address)=(value); } while (0)
#define MMREAD32(mac,address) (*(address))
#define MMWRITE32(mac,address,value) do { *(address)=(value); } while (0)
#define MMREADFIELD(mac,structaddress,field) ((structaddress)->field)
#define MMWRITEFIELD(mac,structaddress,field,value) do { (structaddress)->field=(value); } while (0)

#ifdef MMGBUS

#undef MMREAD8
#undef MMWRITE8
#undef MMREAD32
#undef MMWRITE32
#undef MMREADFIELD
#undef MMWRITEFIELD

#define MMREAD8(mac,address)          gbus_read_uint8  (mac,(RMuint32)(address))
#define MMWRITE8(mac,address,value)   gbus_write_uint8 (mac,(RMuint32)(address),(RMuint8)(value))
#define MMREAD32(mac,address)         gbus_read_uint32 (mac,(RMuint32)(address))
#define MMWRITE32(mac,address,value)  gbus_write_uint32(mac,(RMuint32)(address),(RMuint32)(value))


// type safety would be better with gcc stuff like typeof((structaddress)->field))  
#define MMREADFIELD(mac,structaddress,field) 						\
(MMREAD32(mac,(RMuint8 *)(&(structaddress)->field)))
     
#define MMWRITEFIELD(mac,structaddress,field,value) \
do 											    \
{ 											    \
	MMWRITE32(mac,									    \
		  (RMuint8 *)(&(structaddress)->field),                                     \
		  value); 								    \
} while (0)
     
#endif // MMGBUS

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(struct mbh),alignment);
}

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

static inline RMbool AmIBefore(struct mbh *pU,struct mbh *pV) 
{
	return ((RMuint32)pU<(RMuint32)pV);
}
		
static inline RMbool AmILeftNeighbor(void *mac,struct mbh *pU,struct mbh *pV,RMalignment alignment) 
{
	return ((struct mbh *)(DataAddress(pU,alignment)+MMREADFIELD(mac,pU,size))==pV);
}

static inline RMuint32 Hash(RMuint32 x,RMuint32 y) 
{
	RMuint32 u=x^y,result;
	result=u*(u-1)*(u-0xface)+0xabba0000; // any quick computation that spreads on the 32 bits

	return result;
}

struct mz *MOD(RMCreateZone)(void *mac,
			     RMalignment al,
			     RMuint8 *pSubmittedBuffer,
			     RMuint32 submittedSize)
{
	RMuint8 *pRectifiedBuffer;
	RMint32 rectifiedSize;
	struct mz *pZ;
	
	if (pSubmittedBuffer==NULL) RMPanic(RM_FATALINVALIDPOINTER);
	
	// align beginning if needed, and keep the beginning to store the struct mz struct
	pRectifiedBuffer=NextAlignedAddress(pSubmittedBuffer,al);
	pZ=(struct mz *)pRectifiedBuffer;
	pRectifiedBuffer=NextAlignedAddress(pRectifiedBuffer+sizeof(struct mz),al);
	
	// rectify the size.
	rectifiedSize=submittedSize-(pRectifiedBuffer-pSubmittedBuffer);
	if (rectifiedSize-HeaderSkip(al)<=0) RMPanic(RM_FATALBUFFERTOOSMALL);

	// make size a multiple of alignment.
	rectifiedSize=(rectifiedSize/al)*al;
	
	MMWRITEFIELD(mac,pZ,beginning,pRectifiedBuffer);
	MMWRITEFIELD(mac,pZ,totalSize,rectifiedSize);
	MMWRITEFIELD(mac,pZ,alignment,al);
	MMWRITEFIELD(mac,pZ,successfulMallocs,0);
	MMWRITEFIELD(mac,pZ,successfulFrees,0);
	MMWRITEFIELD(mac,pZ,occupiedSize,0);
	MMWRITEFIELD(mac,pZ,maxSize,0);
	MMWRITEFIELD(mac,pZ,syncCookie,0);
	
	// define the first free block as the whole buffer.
	RMDBGLOG((LOCALDBG,"RMCreateZone: first free block offset %ld\n",pRectifiedBuffer-pSubmittedBuffer));
	MMWRITEFIELD(mac,pZ,pFirstFree,(struct mbh *)pRectifiedBuffer);
	MMWRITEFIELD(mac,(struct mbh *)pRectifiedBuffer,size,rectifiedSize-HeaderSkip(al));
	MMWRITEFIELD(mac,(struct mbh *)pRectifiedBuffer,next,(struct mbh *)NULL);
	
	RMDBGLOG((LOCALDBG,"RMCreateZone: %lu bytes zone ready (pZ=%p)\n",MMREADFIELD(mac,pZ,totalSize),pZ));
	
	return pZ;
}

#ifdef WITH_THREADS

#define LOCK(mac) do	{							\
	void *cookie=(void *)MMREADFIELD(mac,pZ,syncCookie);		\
	if (cookie==NULL) 						\
		RMDBGLOG((ENABLE,"should lock but no cookie yet\n"));	\
	else								\
		mzlock(mac,cookie);						\
} while (0)

#define UNLOCK(mac) do	{						\
	void *cookie=(void *)MMREADFIELD(mac,pZ,syncCookie);		\
	if (cookie==NULL) 						\
		RMDBGLOG((ENABLE,"should unlock but no cookie yet\n"));	\
	else								\
		mzunlock(mac,cookie);					\
} while (0)

void MOD(RMSetSyncCookie)(void *mac,struct mz *pZ,void *cookie)
{
	MMWRITEFIELD(mac,pZ,syncCookie,cookie);
}

void *MOD(RMGetSyncCookie)(void *mac,struct mz *pZ)
{
	return (void *)MMREADFIELD(mac,pZ,syncCookie);
}

#else

#define LOCK(mac) do {} while (0)
#define UNLOCK(mac) do {} while (0)

#endif // WITH_THREADS

RMstatus MOD(RMDeleteZone)(void *mac,struct mz *pZ)
{
	if (MMREADFIELD(mac,pZ,occupiedSize)!=0) {
		RMDBGLOG((ENABLE,
			  "RMDeleteZone: shame on you, memory leak (%lu allocations, %lu bytes)\n",
			  MMREADFIELD(mac,pZ,successfulMallocs)-MMREADFIELD(mac,pZ,successfulFrees),
			  MMREADFIELD(mac,pZ,occupiedSize)
			  ));
		return RM_ERRORMEMORYISNOTFREE;
	}
	
	//MMREADFIELD(mac,pZ,pCSops)->Delete(NULL);

	RMDBGLOG((LOCALDBG,
		  "RMDeleteZone: peak usage=%lu/%lu bytes (%ld%%)\n",
		  MMREADFIELD(mac,pZ,maxSize),
		  MMREADFIELD(mac,pZ,totalSize),
		  100*MMREADFIELD(mac,pZ,maxSize)/MMREADFIELD(mac,pZ,totalSize)));
	
	return RM_OK;
}

void *MOD(RMMallocInZone)(void *mac,struct mz *pZ,RMuint32 submittedSize)
{
	RMalignment al=MMREADFIELD(mac,pZ,alignment);

	RMuint32 rectifiedSize;
	struct mbh *pCurrent,*pPrevious;

	// ! &(x->field) is tricky but ok
	struct mbh **ppFirstFree=(struct mbh **)(&(pZ->pFirstFree));

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

	LOCK(mac);
	
	rectifiedSize=(RMuint32)NextAlignedAddress((RMuint8 *)submittedSize,al);

	pPrevious=(struct mbh *)NULL;
	pCurrent=(struct mbh *)MMREAD32(mac,ppFirstFree);

	while (pCurrent) {
		if (MMREADFIELD(mac,pCurrent,size)==rectifiedSize) {
			// simply remove the block from the linked list
			if (pPrevious) {
				RMDBGLOG((LOCALDBG,"RMMallocInZone: EQUALITY, MIDDLE OF LIST\n"));
				MMWRITEFIELD(mac,pPrevious,next,MMREADFIELD(mac,pCurrent,next));
			}
			else {
				RMDBGLOG((LOCALDBG,"RMMallocInZone: EQUALITY, BEGINNING OF LIST\n"));
				MMWRITE32(mac,ppFirstFree,MMREADFIELD(mac,pCurrent,next));
			}
			
			goto returnok;
		}
		
		if (MMREADFIELD(mac,pCurrent,size)>rectifiedSize+HeaderSkip(al)) {
			// split the block
			struct mbh *pNewBlock;

			pNewBlock=(struct mbh *)(DataAddress(pCurrent,al)+rectifiedSize);
			MMWRITEFIELD(mac,pNewBlock,size,MMREADFIELD(mac,pCurrent,size)-rectifiedSize-HeaderSkip(al));
			MMWRITEFIELD(mac,pNewBlock,next,MMREADFIELD(mac,pCurrent,next));

			MMWRITEFIELD(mac,pCurrent,size,rectifiedSize);
			
			if (pPrevious) {
				RMDBGLOG((LOCALDBG,"RMMallocInZone: INFERIORITY, MIDDLE OF LIST\n"));
				MMWRITEFIELD(mac,pPrevious,next,pNewBlock);
			}
			else {
				RMDBGLOG((LOCALDBG,"RMMallocInZone: INFERIORITY, BEGINNING OF LIST\n"));
				MMWRITE32(mac,ppFirstFree,pNewBlock);
			}

			goto returnok;
		}
		
		pPrevious=pCurrent;
		pCurrent=(struct mbh *)MMREADFIELD(mac,pCurrent,next);

		//RMDBGLOG((LOCALDBG,"(RMMallocInZone: hop to next free block)\n"));
	}
	
	// failure (out of memory)
	
	UNLOCK(mac);
	
	RMDBGLOG((ENABLE,"RMMallocInZone: could not allocate %ld bytes \n", submittedSize));
	
#ifdef WITH_FEEBLEMM
	// just let RMMalloc return NULL
#else
	RMPanic(RM_FATALOUTOFMEMORY);
#endif // WITH_FEEBLEMM
	
	return NULL;
	
 returnok:
	MMWRITEFIELD(mac,pCurrent,hash,Hash((RMuint32)DataAddress(pCurrent,al),rectifiedSize));
	MMWRITEFIELD(mac,pZ,successfulMallocs,MMREADFIELD(mac,pZ,successfulMallocs)+1);
	MMWRITEFIELD(mac,pZ,occupiedSize,MMREADFIELD(mac,pZ,occupiedSize)+rectifiedSize);

	MMWRITEFIELD(mac,pZ,maxSize,
		     RMmax(
			   MMREADFIELD(mac,pZ,maxSize),
			   MMREADFIELD(mac,pZ,occupiedSize)
			   )
		     );

	UNLOCK(mac);

	return (void *)DataAddress(pCurrent,al);
}

void *MOD(RMCallocInZone)(void *mac,struct mz *pZ,RMuint32 nmemb,RMuint32 size)
{
	RMuint8 *beginning=(RMuint8 *)MOD(RMMallocInZone)(mac,pZ,size*nmemb);
	MOD(RMMemsetInZone)(mac,pZ,beginning,0,size*nmemb);