malloc.c

An complete pmp solution for mattel juicebox player. Using crossworks for arm.

#include "malloc.h"
//#include "stdint.h"
/*
  pxFreeList: list with pointers to free chunks
  pxFreeListCount: count list. States number of chunks in every freelist region.
  
  In free list item we put pointers to chunks which are not smaller than the size of 
  chunks which the list item is dedicated to store.
  
  Also chunks must be smaller than the next free list entry.
  
  operation:
 
  0-0-0-0-0-0-0-1-x-x-x-...-x
  preliminaryPos = listStart + (bitNum - startNum)*listEntrySize
  
  list entry size is defined by malloc initialization function. It states the number of
  list entries between two items one 2 times smaller than another.
  
  bit number is the number of the most significant nonzero bit of the size.
    
  now the binary search can be used.
  
  size<<= 31 - bitnum
  
  now the size is of form 1xxxxxx...xb
  
  binary search...
  
  
  
  
*/

#define ulListBlockSize 128
#define ulListBlockSize2 7

#define ulListCountBlockSize 128
#define ulListCountBlockSize2 7

#define chunkSetSize(ptr, size) {			\
	*((u32*)(ptr)-2) = (u32) (size);			\
	*((u32*)(ptr)+(size)) = (u32) (size);			\
	}
	
#define chunkSetFreeSize(ptr, size) {			\
	*((u32*)(ptr)-2) = (u32) (size) | 0x80000000;	\
	*((u32*)(ptr)+(size)) = (u32) (size)| 0x80000000;	\
	}
	
#define chunkSize(ptr)    		((u32)*((u32*)(ptr)-2)&0x7FFFFFFF)
#define chunkFree(ptr)    		(*((u32*)(ptr)-2)>0x7FFFFFFF)
#define chunkNext(ptr)    		((u32*)(((u32*)ptr) + ( *((u32*)ptr-2) & 0x7FFFFFFF ) + 3))
#define chunkPrev(ptr)    		((u32*)(((u32*)ptr) - ( *((u32*)ptr-3) & 0x7FFFFFFF ) - 3))
#define chunkFreeNext(ptr) 		(*((u32*)(ptr)))
#define chunkFreePrev(ptr)  	(*((u32*)(ptr)-1))
#define chunkID(ptr)			(*((u32*)(ptr)-1))

#define freeListCountPos(pos) 	((u32)(((u32)pos)>>ulListCountBlockSize2))

static u32 *pxFreeList;
static u32 *pxFreeListCount;

static u32 *pxMemoryStart;
static u32 *pxMemoryEnd;

//this provides about 1 percent memory leak without overhead

            

static const u32 constDividers[ulListBlockSize] = {
0x80000000 , 0x80b1ed4f , 0x8164d1f3 , 0x8218af43 , 0x82cd8698 , 0x8383594e , 0x843a28c3 , 0x84f1f656 ,
0x85aac367 , 0x8664915b , 0x871f6196 , 0x87db357f , 0x88980e80 , 0x8955ee03 , 0x8a14d575 , 0x8ad4c645 ,
0x8b95c1e3 , 0x8c57c9c4 , 0x8d1adf5b , 0x8ddf0420 , 0x8ea4398b , 0x8f6a8117 , 0x9031dc43 , 0x90fa4c8b ,
0x91c3d373 , 0x928e727d , 0x935a2b2f , 0x9426ff0f , 0x94f4efa8 , 0x95c3fe86 , 0x96942d37 , 0x97657d49 ,
0x9837f051 , 0x990b87e2 , 0x99e04593 , 0x9ab62afc , 0x9b8d39b9 , 0x9c657368 , 0x9d3ed9a7 , 0x9e196e18 ,
0x9ef53260 , 0x9fd22825 , 0xa0b0510f , 0xa18faeca , 0xa2704303 , 0xa3520f68 , 0xa43515ae , 0xa5195786 ,
0xa5fed6a9 , 0xa6e594cf , 0xa7cd93b4 , 0xa8b6d516 , 0xa9a15ab4 , 0xaa8d2652 , 0xab7a39b5 , 0xac6896a4 ,
0xad583eea , 0xae493452 , 0xaf3b78ad , 0xb02f0dcb , 0xb123f581 , 0xb21a31a6 , 0xb311c412 , 0xb40aaea2 ,
0xb504f333 , 0xb60093a8 , 0xb6fd91e3 , 0xb7fbefca , 0xb8fbaf47 , 0xb9fcd245 , 0xbaff5ab2 , 0xbc034a7e ,
0xbd08a39f , 0xbe0f6809 , 0xbf1799b6 , 0xc0213aa1 , 0xc12c4cca , 0xc238d231 , 0xc346ccda , 0xc4563ecc ,
0xc5672a11 , 0xc67990b5 , 0xc78d74c8 , 0xc8a2d85c , 0xc9b9bd86 , 0xcad2265e , 0xcbec14fe , 0xcd078b86 ,
0xce248c15 , 0xcf4318cf , 0xd06333da , 0xd184df62 , 0xd2a81d91 , 0xd3ccf099 , 0xd4f35aab , 0xd61b5dfe ,
0xd744fcca , 0xd870394c , 0xd99d15c2 , 0xdacb946f , 0xdbfbb797 , 0xdd2d8185 , 0xde60f482 , 0xdf9612de ,
0xe0ccdeec , 0xe2055aff , 0xe33f8972 , 0xe47b6ca0 , 0xe5b906e7 , 0xe6f85aaa , 0xe8396a50 , 0xe97c3840 ,
0xeac0c6e7 , 0xec0718b6 , 0xed4f301e , 0xee990f98 , 0xefe4b99b , 0xf13230a7 , 0xf281773c , 0xf3d28fde ,
0xf5257d15 , 0xf67a416c , 0xf7d0df73 , 0xf92959bb , 0xfa83b2db , 0xfbdfed6c , 0xfd3e0c0c , 0xfe9e115c
};

u32 wFreeListPos (u32 ulSize)
{
  if (ulSize<=ulListBlockSize) return ulSize;
  //too small so the list is maintained for every item of the list

  u32 pos = ulListBlockSize;
  u32 sizeWindow = ulListBlockSize;
  //now we have the smallest sizewindow (2 if because we have already checked that ulSize is greater than 128)

  /* we try to get how great ulSize in degrees of two so we'll have item's position in the list */
  while (ulSize > sizeWindow)
    {
	sizeWindow <<= 1;
	pos+=ulListBlockSize;
	}
  
  /*ulSize is not important. We know the sector, where item should be,
    so the only thing we have to do is to find correct place in that sector
  */
  //make ulSize as great as possible
  if (ulSize < 0x00010000) ulSize <<= 16;
  if (ulSize < 0x01000000) ulSize <<= 8;
  if (ulSize < 0x10000000) ulSize <<= 4;
  if (ulSize < 0x40000000) ulSize <<= 2;
  if (ulSize < 0x80000000) ulSize <<= 1;
  
  //use binary search to find the certain position of the item
  u32 low = 0;
  u32 high = ulListBlockSize;
  u32 mid = ulListBlockSize;
  
  while (low<high-1)
	{
    mid = (low + high)>>1;
    if (constDividers[mid] > ulSize)
        high = mid; 
        else
        low = mid; 
    }
  
  pos+=low;
  return pos;
}
//-------------------------------------------------
inline void wAddFree(u32 *ptr, u32 size)
{
  chunkSetFreeSize(ptr, size);
  //get the position where it should be..
  u32 pos;
  pos = wFreeListPos(size);

  //mark that there is one more sector with size in specified range
  *((u32*)pxFreeListCount + freeListCountPos(pos)) +=1;
  //get the position in free list
  u32 *rpos = (u32*)((pos) +pxFreeList);
  if (*rpos)
    {
	chunkFreePrev(*rpos) = (u32) ptr;
	chunkFreeNext(ptr) = *rpos;
	}
	else chunkFreeNext(ptr) = (u32)NULL;


  *rpos = (u32)ptr;
  chunkFreePrev(ptr) = (u32)rpos;
}
//---------------------------------------------------
inline void wRemoveFree(u32 *ptr)
{
  u32 size = chunkSize(ptr);
  u32 *pos = (u32*)wFreeListPos(size);
  *((u32*)pxFreeListCount + freeListCountPos(pos)) -=1;

  u32 *ptrf = (u32*) chunkFreePrev(ptr);
  chunkFreeNext(ptrf) = chunkFreeNext(ptr);
  if (chunkFreeNext(ptr)) {
        ptrf = (u32*) chunkFreeNext(ptr);
        chunkFreePrev(ptrf) = chunkFreePrev(ptr);
        }
}
//---------------------------------------------------
inline void  wUseFree(u32 *ptr, u32 sizeReq)
{
  wRemoveFree(ptr);
  u32 size = chunkSize(ptr);
  chunkID(ptr) = 0x12345677;

  if (sizeReq+3<size)
    {
	chunkSetSize(ptr, sizeReq);
	ptr = chunkNext(ptr);
	wAddFree(ptr, size - sizeReq - 3);
	}
    else
	chunkSetSize(ptr, size);

}
//---------------------------------------------------

void wMallocInit (u32 ulMemorySize, u32 *pulMemoryStart)
{
   
  ulMemorySize >>=2;

  u32 size = wFreeListPos(ulMemorySize) + 1;
  pxFreeList = pulMemoryStart;

  u32 *ptr = pxFreeList;
  u32 i;
  for (i=0; i<size; i++)
    *ptr++ = 0;

  pulMemoryStart += size + 128;
  pxFreeListCount = pulMemoryStart;     //size of this array: size>>7+1
  ptr = pxFreeListCount;
  for (i=0; i< freeListCountPos(size) + 1; i++)
    *ptr++ = 0;
  
  pulMemoryStart = ((u32*)pulMemoryStart + freeListCountPos(size) + 3);
  
  ulMemorySize = ulMemorySize - size - freeListCountPos(size) - 5;
  pxMemoryStart = pulMemoryStart;
  pxMemoryEnd = pxMemoryStart + ulMemorySize;
  
  chunkFreeNext(pulMemoryStart) = (u32)NULL;
  chunkFreePrev(pulMemoryStart) = (u32)NULL;


  wAddFree (pulMemoryStart, ulMemorySize);
 
}
//---------------------------------------------------

void *wMalloc (u32 size)
{
  
  size = (size+3)>>2;
  u32 *result;
  
  //we find the position of item where it should be allocated
  u32 pos = wFreeListPos(size);
  
  //position in the list
  u32 *ptrf = (u32*)pxFreeList + (u32)pos;
  //position in sector list
  u32 *ptrc = pxFreeListCount + (size >> ulListBlockSize2);
  if (*ptrc)  //we got some items in current sector
    {
    u32 i;
	//let's check if there are any items in the sector bigger than requested one
	for(i = pos % ulListBlockSize; i<ulListBlockSize; i++)    {
        result = (u32 *) *ptrf++;
        if (result)
	        {
		    wUseFree(result, size);
		    return result;
		    }
        }
	//we haven't found any usable items in this sector
	}
  while(!(*(++ptrc))); //search for suitable sector
  //we've got it! if not, there is fatal error - not enough memory
  //get the position of the first item in the sector
  ptrf = (u32*) (pxFreeList + ((u32)((u32*)ptrc - (u32*)pxFreeListCount))*(ulListBlockSize));
  
  result = (u32*) *ptrf;
  while (!result)
    result = (u32*) *ptrf++;
  wUseFree(result, size);
    
  return result;

}

//----------------------------------------------------------
void wFree (u32 *ptr)
{
  //TODO: check if the chunk was malloced by the calling program
  u32 *ptr2;
  
  if (ptr>pxMemoryStart) 
    {
    ptr2 = chunkPrev(ptr);
    if (ptr2>=pxMemoryStart) if (chunkFree(ptr2))
      {
  	  wRemoveFree(ptr2);
	  u32 size = chunkSize(ptr2) + 3 + chunkSize(ptr);
  	  chunkSetFreeSize (ptr2, size);
	  ptr = ptr2;
	  }
	}
	
  if( ptr < pxMemoryEnd) 
    {
    ptr2 = chunkNext(ptr);
    if (ptr2<pxMemoryEnd) if (chunkFree(ptr2))
      {
	  wRemoveFree(ptr2);
	  u32 size = chunkSize(ptr2) + 3 + chunkSize(ptr);
	  chunkSetFreeSize (ptr, size);		
	  }
	}
  
  wAddFree (ptr, chunkSize(ptr));

}
//===========================================================