SQLite

/*
** A minimum allocation is an instance of the following structure.
** Larger allocations are an array of these structures where the
** size of the array is a power of 2.
**
** The size of this object must be a power of two.  That fact is
** verified in memsys5Init().
**
** This object overlays the memory allocation when the memory is available
** to be allocated.  In other words Mem5Link objects represent memory
** that is available to be allocated.
**
** All Mem5Link objects of the same size are arranged on a dynamic
** heap, with the root being the Mem5Link that has the smallest address.
** The iLeft and iRight Mem5Link objects are children.  The iSlot numbers
** for the left and right child are as follows:
**
**      pLeft->iSlot = pParent->iSlot*2;
**      pRight->iSlot = pParent->iSlot*2 + 1;
**
** The root of the heap always has iSlot==1.  If the heap contains
** N elements, then they cover all slots from 1 through N.
*/
typedef struct Mem5Link Mem5Link;
struct Mem5Link {
  int iLeft;       /* left child in the heap */
  int iRight;      /* right child in the heap */
  int iSlot;       /* Slot in the heap holding this item. */
  int filler;      /* Not used. Needed to round size up to power of two */
};

/*
** Maximum size of any allocation is ((1<<LOGMAX)*mem5.szAtom). Since
** mem5.szAtom is always at least 8 and 32-bit integers are used,
** it is not actually possible to reach this limit.
*/
#define LOGMAX 30

/*
** Masks used for mem5.aCtrl[] elements.
*/
#define CTRL_LOGSIZE  0x1f    /* Log2 Size of this block */
#define CTRL_FREE     0x20    /* True if not checked out */

/*
** All of the static variables used by this module are collected
** into a single structure named "mem5".  This is to keep the
** static variables organized and to reduce namespace pollution
** when this module is combined with others in the amalgamation.
*/
static SQLITE_WSD struct Mem5Global {

  /* Memory available for allocation
  */
  int szAtom;      /* Smallest possible allocation in bytes */
  int nBlock;      /* Number of szAtom sized blocks in zPool */
  u8 *zPool;       /* Memory available to be allocated */
  

  /* Mutex to control access to the memory allocation subsystem.
  */
  sqlite3_mutex *mutex;


  /* Performance statistics
  */
  u64 nAlloc;         /* Total number of calls to malloc */
  u64 totalAlloc;     /* Total of all malloc calls - includes internal frag */
  u64 totalExcess;    /* Total internal fragmentation */
  u32 currentOut;     /* Current checkout, including internal fragmentation */
  u32 currentCount;   /* Current number of distinct checkouts */
  u32 maxOut;         /* Maximum instantaneous currentOut */
  u32 maxCount;       /* Maximum instantaneous currentCount */
  u32 maxRequest;     /* Largest allocation (exclusive of internal frag) */
  
  /* Heaps of free blocks.  aHeap[0].iRoot is the root of a dynamic
  ** min-heap of free blocks of size mem5.szAtom.  aHeap[1].iRoot is
  ** a heap of free blocks of size mem5.szAtom*2.  aHeap[x].iRoot is
  ** free heap of blocks of size mem5.szAtom*(1<<x).  aHeap[x].nLink
  ** the number of free blocks on each heap.
  */
  struct Mem5Heap {
    int iRoot;            /* The root Mem5Link for this heap */
    int nLink;            /* Number of Mem5Link objects on this heap */
  } aHeap[LOGMAX+1];


  /* The memsys5HeapPath() routine finds a sequence of nodes in a heap
  ** going to a particular Mem5Link.  It writes those nodes into the
  ** following array.  The root of the tree is in aPath[0].  The first
  ** child in aPath[1].  And so forth.
  */
  int aPath[29];          /* Path to a node in a heap */

  /*
  ** Space for tracking which blocks are checked out and the size
  ** of each block.  One byte per block.
  */
  u8 *aCtrl;

} mem5;

/*
** Access the static variable through a macro for SQLITE_OMIT_WSD.
*/
#define mem5 GLOBAL(struct Mem5Global, mem5)

/*
** Assuming mem5.zPool is divided up into an array of Mem5Link
** structures, return a pointer to the idx-th such link.
*/
#define MEM5_PTR(idx) ((Mem5Link*)(&mem5.zPool[(idx)*mem5.szAtom]))

/*
** Given a pointer to an Mem5Link object, return its index into the
** array of all Mem5Link objects.
*/
#define MEM5_ID(p)    (int)(((u8*)(p)-mem5.zPool)/mem5.szAtom)

#if 0  /* This validation step is too slow for normal use */
/*
** Validate an Mem5Link object to make sure it satisfies all of the
** dynamic heap properties.
*/
static void memsys5Validate(int iLink, int nLink){
  Mem5Link *p = MEM5_PTR(iLink);
  assert( p->iLeft>=0 || p->iRight<0 );
  assert( p->iSlot<=nLink );
  if( p->iLeft>=0 ){
    assert( p->iLeft>iLink );
    assert( p->iLeft!=p->iRight );
    assert( MEM5_PTR(p->iLeft)->iSlot==p->iSlot*2 );
    memsys5Validate(p->iLeft, nLink);
  }else{
    assert( p->iSlot*2>nLink );
  }
  if( p->iRight>=0 ){
    assert( p->iRight>iLink );
    assert( p->iLeft!=p->iRight );
    assert( MEM5_PTR(p->iRight)->iSlot==p->iSlot*2+1 );
    memsys5Validate(p->iRight, nLink);
  }else{
    assert( p->iSlot*2+1>nLink );
  }
}
#else
# define memsys5Validate(X,Y)
#endif

/* 
** Compute a path from the root of a heap to a particular slot of the
** heap.  The root is node iRoot and the desired slot is iSlot.  Write
** the sequence of Mem5Link objects on this path into mem5.aPath[] and
** return the number of elements on the path.
*/
static int memsys5HeapPath(int iRoot, int iSlot){
  int x = 1;
  int i = 0;
  int iRes = iRoot;;

  while( x<=iSlot ) x <<= 1;
  x >>= 2;
  mem5.aPath[0] = iRoot;
  assert( MEM5_PTR(iRoot)->iSlot==1 );
  while( x ){
    Mem5Link *p = MEM5_PTR(iRes);
    iRes = (x & iSlot)!=0 ? p->iRight : p->iLeft;
    mem5.aPath[++i] = iRes;
    x >>= 1;
  }
  assert( MEM5_PTR(mem5.aPath[i])->iSlot==iSlot );
  return i;
}

/* One of the children of heap node iParent will be iOld.  Change
** that child to iNew.
*/
static void memsys5ChangeChild(int iParent, int iOld, int iNew){
  Mem5Link *pParent = MEM5_PTR(iParent);
  if( pParent->iLeft==iOld ){
    pParent->iLeft = iNew;
  }else{
    assert( pParent->iRight==iOld );
    pParent->iRight = iNew;
  }
}

/*
** Swap heap elements mem5.aPath[i] and mem5.aPath[i+1].
*/
static void memsys5HeapPathSwap(int i){
  int iA = mem5.aPath[i];
  int iB = mem5.aPath[i+1];
  Mem5Link *pA = MEM5_PTR(iA);
  Mem5Link *pB = MEM5_PTR(iB);
  int iLeft, iRight, iSlot;

  if( i>0 ) memsys5ChangeChild(mem5.aPath[i-1], iA, iB);
  if( pA->iLeft==iB ){
    iRight = pA->iRight;
    iLeft = iA;
  }else{
    iRight = iA;
    iLeft = pA->iLeft;
  }
  iSlot = pA->iSlot;
  pA->iRight = pB->iRight;
  pA->iLeft = pB->iLeft;
  pA->iSlot = pB->iSlot;
  pB->iRight = iRight;
  pB->iLeft = iLeft;
  pB->iSlot = iSlot;
  mem5.aPath[i] = iB;
  mem5.aPath[i+1] = iA;
}

/*
** If mem5.aPath[i] is greater than either child, then shift
** that element downward in the heap. 
*/
static void memsys5SiftDown(int i){
  while(1){
    int x = mem5.aPath[i];
    Mem5Link *p = MEM5_PTR(x);
    if( p->iRight>=0 && p->iRight<x && p->iRight<p->iLeft ){
      mem5.aPath[i+1] = p->iRight;
    }else if( p->iLeft>=0 && p->iLeft<x ){
      mem5.aPath[i+1] = p->iLeft;
    }else{
      break;
    }
    memsys5HeapPathSwap(i);
    i++; 
  }
}

static void memsys5SiftUp(int i){
  while( i>0 && mem5.aPath[i]<mem5.aPath[i-1] ){
    memsys5HeapPathSwap(i-1);
    i--;
  }
}

/*
** Unlink the chunk at mem5.aPool[i] from iLogsize heap.
*/
static void memsys5Unlink(int iOld, int iLogsize){
  struct Mem5Heap *pHeap;
  Mem5Link *pOld, *pLast;
  int i, iLast;
  assert( iOld>=0 && iOld<mem5.nBlock );
  assert( iLogsize>=0 && iLogsize<=LOGMAX );
  assert( (mem5.aCtrl[iOld] & CTRL_LOGSIZE)==iLogsize );
  assert( mem5.aHeap[iLogsize].nLink>0 );

  pHeap = &mem5.aHeap[iLogsize];

  if( pHeap->nLink==1 ){
    pHeap->nLink = 0;

    pHeap->iRoot = -1;
    return;
  }
  i = memsys5HeapPath(pHeap->iRoot, pHeap->nLink);
  iLast = mem5.aPath[i];
  assert( i>0 );
  memsys5ChangeChild(mem5.aPath[i-1], iLast, -1);
  pHeap->nLink--;
  if( iLast==iOld ) return;
  pOld = MEM5_PTR(iOld);
  pLast = MEM5_PTR(iLast);
  i = memsys5HeapPath(pHeap->iRoot, pOld->iSlot);
  assert( mem5.aPath[i]==iOld );
  pLast->iRight = pOld->iRight;
  pLast->iLeft = pOld->iLeft;
  pLast->iSlot = pOld->iSlot;
  mem5.aPath[i] = iLast;
  if( i>0 ) memsys5ChangeChild(mem5.aPath[i-1], iOld, iLast);
  memsys5SiftUp(i);
  memsys5SiftDown(i);
  pHeap->iRoot = mem5.aPath[0];
  memsys5Validate(pHeap->iRoot, pHeap->nLink);
}

/*
** Find the first entry on the free-heap iLogsize.  Unlink that
** entry and return its index. 
*/
static int memsys5UnlinkFirst(int iLogsize){
  struct Mem5Heap *pHeap;
  int iFirst, i, iLast;
  Mem5Link *pLast;
  Mem5Link *pFirst;

  assert( iLogsize>=0 && iLogsize<=LOGMAX );
  pHeap = &mem5.aHeap[iLogsize];
  assert( pHeap->nLink>0 );
  iFirst = pHeap->iRoot;
  pFirst = MEM5_PTR(iFirst);
  if( pHeap->nLink==1 ){
    pHeap->nLink = 0;
    return iFirst;
  }
  i = memsys5HeapPath(iFirst, pHeap->nLink);
  pHeap->nLink--;
  iLast = mem5.aPath[i];
  assert( i>0 );
  memsys5ChangeChild(mem5.aPath[i-1], iLast, -1);
  pLast = MEM5_PTR(iLast);
  pLast->iSlot = 1;
  pLast->iRight = pFirst->iRight;
  pLast->iLeft = pFirst->iLeft;
  mem5.aPath[0] = iLast;
  memsys5SiftDown(0);
  pHeap->iRoot = mem5.aPath[0];
  memsys5Validate(pHeap->iRoot, pHeap->nLink);
  return iFirst;   
}

/*
** Link the chunk at mem5.aPool[i] so that is on the iLogsize
** free-block heap.
*/
static void memsys5Link(int iNew, int iLogsize){
  struct Mem5Heap *pHeap;
  Mem5Link *pNew;
  int i;
  assert( sqlite3_mutex_held(mem5.mutex) );
  assert( iNew>=0 && iNew<mem5.nBlock );
  assert( iLogsize>=0 && iLogsize<=LOGMAX );
  assert( (mem5.aCtrl[iNew] & CTRL_LOGSIZE)==iLogsize );
  
  pNew = MEM5_PTR(iNew);
  pHeap = &mem5.aHeap[iLogsize];
  pNew->iLeft = -1;
  pNew->iRight = -1;
  pNew->iSlot = ++pHeap->nLink;
  if( pHeap->nLink==1 ){

    pHeap->iRoot = iNew;
    return;
  }
  i = memsys5HeapPath(pHeap->iRoot, pHeap->nLink/2);
  memsys5ChangeChild(mem5.aPath[i], -1, iNew);
  mem5.aPath[i+1] = iNew;
  memsys5SiftUp(i+1);
  pHeap->iRoot = mem5.aPath[0];
  memsys5Validate(pHeap->iRoot, pHeap->nLink);
}

/*
** If the STATIC_MEM mutex is not already held, obtain it now. The mutex
** will already be held (obtained by code in malloc.c) if
** sqlite3GlobalConfig.bMemStat is true.
*/

** Return the size of an outstanding allocation, in bytes.  The
** size returned omits the 8-byte header overhead.  This only
** works for chunks that are currently checked out.
*/
static int memsys5Size(void *p){
  int iSize = 0;
  if( p ){
    int i = MEM5_ID(p);
    assert( i>=0 && i<mem5.nBlock );
    iSize = mem5.szAtom * (1 << (mem5.aCtrl[i]&CTRL_LOGSIZE));
  }
  return iSize;
}




















/*
** Return a block of memory of at least nBytes in size.
** Return NULL if unable.  Return NULL if nBytes==0.
**
** The caller guarantees that nByte is positive.
**
** The caller has obtained a mutex prior to invoking this
** routine so there is never any chance that two or more
** threads can be in this routine at the same time.
*/
static void *memsys5MallocUnsafe(int nByte){
  int i;           /* Index of a mem5.aPool[] slot */
  int iBin;        /* Index into mem5.aHeap[] */
  int iFullSz;     /* Size of allocation rounded up to power of 2 */
  int iLogsize;    /* Log2 of iFullSz/POW2_MIN */

  /* nByte must be a positive */
  assert( nByte>0 );

  /* Keep track of the maximum allocation request.  Even unfulfilled

  if( nByte > 0x40000000 ){
    return 0;
  }

  /* Round nByte up to the next valid power of two */
  for(iFullSz=mem5.szAtom, iLogsize=0; iFullSz<nByte; iFullSz *= 2, iLogsize++){}

  /* Make sure mem5.aHeap[iLogsize] contains at least one free
  ** block.  If not, then split a block of the next larger power of
  ** two in order to create a new free block of size iLogsize.
  */
  for(iBin=iLogsize; mem5.aHeap[iBin].nLink==0 && iBin<=LOGMAX; iBin++){}
  if( iBin>LOGMAX ){
    testcase( sqlite3GlobalConfig.xLog!=0 );
    sqlite3_log(SQLITE_NOMEM, "failed to allocate %u bytes", nByte);
    return 0;
  }
  i = memsys5UnlinkFirst(iBin);
  while( iBin>iLogsize ){

static void memsys5FreeUnsafe(void *pOld){
  u32 size, iLogsize;
  int iBlock;

  /* Set iBlock to the index of the block pointed to by pOld in 
  ** the array of mem5.szAtom byte blocks pointed to by mem5.zPool.
  */
  iBlock = MEM5_ID(pOld);

  /* Check that the pointer pOld points to a valid, non-free block. */
  assert( iBlock>=0 && iBlock<mem5.nBlock );
  assert( ((u8 *)pOld-mem5.zPool)%mem5.szAtom==0 );
  assert( (mem5.aCtrl[iBlock] & CTRL_FREE)==0 );

  iLogsize = mem5.aCtrl[iBlock] & CTRL_LOGSIZE;

  }

  mem5.nBlock = (nByte / (mem5.szAtom+sizeof(u8)));
  mem5.zPool = zByte;
  mem5.aCtrl = (u8 *)&mem5.zPool[mem5.nBlock*mem5.szAtom];

  for(ii=0; ii<=LOGMAX; ii++){
    mem5.aHeap[ii].nLink = 0;
  }

  iOffset = 0;
  for(ii=LOGMAX; ii>=0; ii--){
    int nAlloc = (1<<ii);
    if( (iOffset+nAlloc)<=mem5.nBlock ){
      mem5.aCtrl[iOffset] = ii | CTRL_FREE;

#ifdef SQLITE_TEST
/*
** Open the file indicated and write a log of all unfreed memory 
** allocations into that log.
*/
void sqlite3Memsys5Dump(const char *zFilename){
  FILE *out;
  int i;
  int nMinLog;

  if( zFilename==0 || zFilename[0]==0 ){
    out = stdout;
  }else{
    out = fopen(zFilename, "w");
    if( out==0 ){
      fprintf(stderr, "** Unable to output memory debug output log: %s **\n",
                      zFilename);
      return;
    }
  }
  memsys5Enter();
  nMinLog = memsys5Log(mem5.szAtom);
  for(i=0; i<=LOGMAX && i+nMinLog<32; i++){

    fprintf(out, "freelist items of size %d: %d\n",
            mem5.szAtom << i, mem5.aHeap[i].nLink);
  }
  fprintf(out, "mem5.nAlloc       = %llu\n", mem5.nAlloc);
  fprintf(out, "mem5.totalAlloc   = %llu\n", mem5.totalAlloc);
  fprintf(out, "mem5.totalExcess  = %llu\n", mem5.totalExcess);
  fprintf(out, "mem5.currentOut   = %u\n", mem5.currentOut);
  fprintf(out, "mem5.currentCount = %u\n", mem5.currentCount);
  fprintf(out, "mem5.maxOut       = %u\n", mem5.maxOut);