000001  /*
000002  ** 2007 October 14
000003  **
000004  ** The author disclaims copyright to this source code.  In place of
000005  ** a legal notice, here is a blessing:
000006  **
000007  **    May you do good and not evil.
000008  **    May you find forgiveness for yourself and forgive others.
000009  **    May you share freely, never taking more than you give.
000010  **
000011  *************************************************************************
000012  ** This file contains the C functions that implement a memory
000013  ** allocation subsystem for use by SQLite. 
000014  **
000015  ** This version of the memory allocation subsystem omits all
000016  ** use of malloc(). The application gives SQLite a block of memory
000017  ** before calling sqlite3_initialize() from which allocations
000018  ** are made and returned by the xMalloc() and xRealloc() 
000019  ** implementations. Once sqlite3_initialize() has been called,
000020  ** the amount of memory available to SQLite is fixed and cannot
000021  ** be changed.
000022  **
000023  ** This version of the memory allocation subsystem is included
000024  ** in the build only if SQLITE_ENABLE_MEMSYS5 is defined.
000025  **
000026  ** This memory allocator uses the following algorithm:
000027  **
000028  **   1.  All memory allocation sizes are rounded up to a power of 2.
000029  **
000030  **   2.  If two adjacent free blocks are the halves of a larger block,
000031  **       then the two blocks are coalesced into the single larger block.
000032  **
000033  **   3.  New memory is allocated from the first available free block.
000034  **
000035  ** This algorithm is described in: J. M. Robson. "Bounds for Some Functions
000036  ** Concerning Dynamic Storage Allocation". Journal of the Association for
000037  ** Computing Machinery, Volume 21, Number 8, July 1974, pages 491-499.
000038  ** 
000039  ** Let n be the size of the largest allocation divided by the minimum
000040  ** allocation size (after rounding all sizes up to a power of 2.)  Let M
000041  ** be the maximum amount of memory ever outstanding at one time.  Let
000042  ** N be the total amount of memory available for allocation.  Robson
000043  ** proved that this memory allocator will never breakdown due to 
000044  ** fragmentation as long as the following constraint holds:
000045  **
000046  **      N >=  M*(1 + log2(n)/2) - n + 1
000047  **
000048  ** The sqlite3_status() logic tracks the maximum values of n and M so
000049  ** that an application can, at any time, verify this constraint.
000050  */
000051  #include "sqliteInt.h"
000052  
000053  /*
000054  ** This version of the memory allocator is used only when 
000055  ** SQLITE_ENABLE_MEMSYS5 is defined.
000056  */
000057  #ifdef SQLITE_ENABLE_MEMSYS5
000058  
000059  /*
000060  ** A minimum allocation is an instance of the following structure.
000061  ** Larger allocations are an array of these structures where the
000062  ** size of the array is a power of 2.
000063  **
000064  ** The size of this object must be a power of two.  That fact is
000065  ** verified in memsys5Init().
000066  */
000067  typedef struct Mem5Link Mem5Link;
000068  struct Mem5Link {
000069    int next;       /* Index of next free chunk */
000070    int prev;       /* Index of previous free chunk */
000071  };
000072  
000073  /*
000074  ** Maximum size of any allocation is ((1<<LOGMAX)*mem5.szAtom). Since
000075  ** mem5.szAtom is always at least 8 and 32-bit integers are used,
000076  ** it is not actually possible to reach this limit.
000077  */
000078  #define LOGMAX 30
000079  
000080  /*
000081  ** Masks used for mem5.aCtrl[] elements.
000082  */
000083  #define CTRL_LOGSIZE  0x1f    /* Log2 Size of this block */
000084  #define CTRL_FREE     0x20    /* True if not checked out */
000085  
000086  /*
000087  ** All of the static variables used by this module are collected
000088  ** into a single structure named "mem5".  This is to keep the
000089  ** static variables organized and to reduce namespace pollution
000090  ** when this module is combined with other in the amalgamation.
000091  */
000092  static SQLITE_WSD struct Mem5Global {
000093    /*
000094    ** Memory available for allocation
000095    */
000096    int szAtom;      /* Smallest possible allocation in bytes */
000097    int nBlock;      /* Number of szAtom sized blocks in zPool */
000098    u8 *zPool;       /* Memory available to be allocated */
000099    
000100    /*
000101    ** Mutex to control access to the memory allocation subsystem.
000102    */
000103    sqlite3_mutex *mutex;
000104  
000105  #if defined(SQLITE_DEBUG) || defined(SQLITE_TEST)
000106    /*
000107    ** Performance statistics
000108    */
000109    u64 nAlloc;         /* Total number of calls to malloc */
000110    u64 totalAlloc;     /* Total of all malloc calls - includes internal frag */
000111    u64 totalExcess;    /* Total internal fragmentation */
000112    u32 currentOut;     /* Current checkout, including internal fragmentation */
000113    u32 currentCount;   /* Current number of distinct checkouts */
000114    u32 maxOut;         /* Maximum instantaneous currentOut */
000115    u32 maxCount;       /* Maximum instantaneous currentCount */
000116    u32 maxRequest;     /* Largest allocation (exclusive of internal frag) */
000117  #endif
000118    
000119    /*
000120    ** Lists of free blocks.  aiFreelist[0] is a list of free blocks of
000121    ** size mem5.szAtom.  aiFreelist[1] holds blocks of size szAtom*2.
000122    ** aiFreelist[2] holds free blocks of size szAtom*4.  And so forth.
000123    */
000124    int aiFreelist[LOGMAX+1];
000125  
000126    /*
000127    ** Space for tracking which blocks are checked out and the size
000128    ** of each block.  One byte per block.
000129    */
000130    u8 *aCtrl;
000131  
000132  } mem5;
000133  
000134  /*
000135  ** Access the static variable through a macro for SQLITE_OMIT_WSD.
000136  */
000137  #define mem5 GLOBAL(struct Mem5Global, mem5)
000138  
000139  /*
000140  ** Assuming mem5.zPool is divided up into an array of Mem5Link
000141  ** structures, return a pointer to the idx-th such link.
000142  */
000143  #define MEM5LINK(idx) ((Mem5Link *)(&mem5.zPool[(idx)*mem5.szAtom]))
000144  
000145  /*
000146  ** Unlink the chunk at mem5.aPool[i] from list it is currently
000147  ** on.  It should be found on mem5.aiFreelist[iLogsize].
000148  */
000149  static void memsys5Unlink(int i, int iLogsize){
000150    int next, prev;
000151    assert( i>=0 && i<mem5.nBlock );
000152    assert( iLogsize>=0 && iLogsize<=LOGMAX );
000153    assert( (mem5.aCtrl[i] & CTRL_LOGSIZE)==iLogsize );
000154  
000155    next = MEM5LINK(i)->next;
000156    prev = MEM5LINK(i)->prev;
000157    if( prev<0 ){
000158      mem5.aiFreelist[iLogsize] = next;
000159    }else{
000160      MEM5LINK(prev)->next = next;
000161    }
000162    if( next>=0 ){
000163      MEM5LINK(next)->prev = prev;
000164    }
000165  }
000166  
000167  /*
000168  ** Link the chunk at mem5.aPool[i] so that is on the iLogsize
000169  ** free list.
000170  */
000171  static void memsys5Link(int i, int iLogsize){
000172    int x;
000173    assert( sqlite3_mutex_held(mem5.mutex) );
000174    assert( i>=0 && i<mem5.nBlock );
000175    assert( iLogsize>=0 && iLogsize<=LOGMAX );
000176    assert( (mem5.aCtrl[i] & CTRL_LOGSIZE)==iLogsize );
000177  
000178    x = MEM5LINK(i)->next = mem5.aiFreelist[iLogsize];
000179    MEM5LINK(i)->prev = -1;
000180    if( x>=0 ){
000181      assert( x<mem5.nBlock );
000182      MEM5LINK(x)->prev = i;
000183    }
000184    mem5.aiFreelist[iLogsize] = i;
000185  }
000186  
000187  /*
000188  ** Obtain or release the mutex needed to access global data structures.
000189  */
000190  static void memsys5Enter(void){
000191    sqlite3_mutex_enter(mem5.mutex);
000192  }
000193  static void memsys5Leave(void){
000194    sqlite3_mutex_leave(mem5.mutex);
000195  }
000196  
000197  /*
000198  ** Return the size of an outstanding allocation, in bytes.
000199  ** This only works for chunks that are currently checked out.
000200  */
000201  static int memsys5Size(void *p){
000202    int iSize, i;
000203    assert( p!=0 );
000204    i = (int)(((u8 *)p-mem5.zPool)/mem5.szAtom);
000205    assert( i>=0 && i<mem5.nBlock );
000206    iSize = mem5.szAtom * (1 << (mem5.aCtrl[i]&CTRL_LOGSIZE));
000207    return iSize;
000208  }
000209  
000210  /*
000211  ** Return a block of memory of at least nBytes in size.
000212  ** Return NULL if unable.  Return NULL if nBytes==0.
000213  **
000214  ** The caller guarantees that nByte is positive.
000215  **
000216  ** The caller has obtained a mutex prior to invoking this
000217  ** routine so there is never any chance that two or more
000218  ** threads can be in this routine at the same time.
000219  */
000220  static void *memsys5MallocUnsafe(int nByte){
000221    int i;           /* Index of a mem5.aPool[] slot */
000222    int iBin;        /* Index into mem5.aiFreelist[] */
000223    int iFullSz;     /* Size of allocation rounded up to power of 2 */
000224    int iLogsize;    /* Log2 of iFullSz/POW2_MIN */
000225  
000226    /* nByte must be a positive */
000227    assert( nByte>0 );
000228  
000229    /* No more than 1GiB per allocation */
000230    if( nByte > 0x40000000 ) return 0;
000231  
000232  #if defined(SQLITE_DEBUG) || defined(SQLITE_TEST)
000233    /* Keep track of the maximum allocation request.  Even unfulfilled
000234    ** requests are counted */
000235    if( (u32)nByte>mem5.maxRequest ){
000236      mem5.maxRequest = nByte;
000237    }
000238  #endif
000239  
000240  
000241    /* Round nByte up to the next valid power of two */
000242    for(iFullSz=mem5.szAtom,iLogsize=0; iFullSz<nByte; iFullSz*=2,iLogsize++){}
000243  
000244    /* Make sure mem5.aiFreelist[iLogsize] contains at least one free
000245    ** block.  If not, then split a block of the next larger power of
000246    ** two in order to create a new free block of size iLogsize.
000247    */
000248    for(iBin=iLogsize; iBin<=LOGMAX && mem5.aiFreelist[iBin]<0; iBin++){}
000249    if( iBin>LOGMAX ){
000250      testcase( sqlite3GlobalConfig.xLog!=0 );
000251      sqlite3_log(SQLITE_NOMEM, "failed to allocate %u bytes", nByte);
000252      return 0;
000253    }
000254    i = mem5.aiFreelist[iBin];
000255    memsys5Unlink(i, iBin);
000256    while( iBin>iLogsize ){
000257      int newSize;
000258  
000259      iBin--;
000260      newSize = 1 << iBin;
000261      mem5.aCtrl[i+newSize] = CTRL_FREE | iBin;
000262      memsys5Link(i+newSize, iBin);
000263    }
000264    mem5.aCtrl[i] = iLogsize;
000265  
000266  #if defined(SQLITE_DEBUG) || defined(SQLITE_TEST)
000267    /* Update allocator performance statistics. */
000268    mem5.nAlloc++;
000269    mem5.totalAlloc += iFullSz;
000270    mem5.totalExcess += iFullSz - nByte;
000271    mem5.currentCount++;
000272    mem5.currentOut += iFullSz;
000273    if( mem5.maxCount<mem5.currentCount ) mem5.maxCount = mem5.currentCount;
000274    if( mem5.maxOut<mem5.currentOut ) mem5.maxOut = mem5.currentOut;
000275  #endif
000276  
000277  #ifdef SQLITE_DEBUG
000278    /* Make sure the allocated memory does not assume that it is set to zero
000279    ** or retains a value from a previous allocation */
000280    memset(&mem5.zPool[i*mem5.szAtom], 0xAA, iFullSz);
000281  #endif
000282  
000283    /* Return a pointer to the allocated memory. */
000284    return (void*)&mem5.zPool[i*mem5.szAtom];
000285  }
000286  
000287  /*
000288  ** Free an outstanding memory allocation.
000289  */
000290  static void memsys5FreeUnsafe(void *pOld){
000291    u32 size, iLogsize;
000292    int iBlock;
000293  
000294    /* Set iBlock to the index of the block pointed to by pOld in 
000295    ** the array of mem5.szAtom byte blocks pointed to by mem5.zPool.
000296    */
000297    iBlock = (int)(((u8 *)pOld-mem5.zPool)/mem5.szAtom);
000298  
000299    /* Check that the pointer pOld points to a valid, non-free block. */
000300    assert( iBlock>=0 && iBlock<mem5.nBlock );
000301    assert( ((u8 *)pOld-mem5.zPool)%mem5.szAtom==0 );
000302    assert( (mem5.aCtrl[iBlock] & CTRL_FREE)==0 );
000303  
000304    iLogsize = mem5.aCtrl[iBlock] & CTRL_LOGSIZE;
000305    size = 1<<iLogsize;
000306    assert( iBlock+size-1<(u32)mem5.nBlock );
000307  
000308    mem5.aCtrl[iBlock] |= CTRL_FREE;
000309    mem5.aCtrl[iBlock+size-1] |= CTRL_FREE;
000310  
000311  #if defined(SQLITE_DEBUG) || defined(SQLITE_TEST)
000312    assert( mem5.currentCount>0 );
000313    assert( mem5.currentOut>=(size*mem5.szAtom) );
000314    mem5.currentCount--;
000315    mem5.currentOut -= size*mem5.szAtom;
000316    assert( mem5.currentOut>0 || mem5.currentCount==0 );
000317    assert( mem5.currentCount>0 || mem5.currentOut==0 );
000318  #endif
000319  
000320    mem5.aCtrl[iBlock] = CTRL_FREE | iLogsize;
000321    while( ALWAYS(iLogsize<LOGMAX) ){
000322      int iBuddy;
000323      if( (iBlock>>iLogsize) & 1 ){
000324        iBuddy = iBlock - size;
000325        assert( iBuddy>=0 );
000326      }else{
000327        iBuddy = iBlock + size;
000328        if( iBuddy>=mem5.nBlock ) break;
000329      }
000330      if( mem5.aCtrl[iBuddy]!=(CTRL_FREE | iLogsize) ) break;
000331      memsys5Unlink(iBuddy, iLogsize);
000332      iLogsize++;
000333      if( iBuddy<iBlock ){
000334        mem5.aCtrl[iBuddy] = CTRL_FREE | iLogsize;
000335        mem5.aCtrl[iBlock] = 0;
000336        iBlock = iBuddy;
000337      }else{
000338        mem5.aCtrl[iBlock] = CTRL_FREE | iLogsize;
000339        mem5.aCtrl[iBuddy] = 0;
000340      }
000341      size *= 2;
000342    }
000343  
000344  #ifdef SQLITE_DEBUG
000345    /* Overwrite freed memory with the 0x55 bit pattern to verify that it is
000346    ** not used after being freed */
000347    memset(&mem5.zPool[iBlock*mem5.szAtom], 0x55, size);
000348  #endif
000349  
000350    memsys5Link(iBlock, iLogsize);
000351  }
000352  
000353  /*
000354  ** Allocate nBytes of memory.
000355  */
000356  static void *memsys5Malloc(int nBytes){
000357    sqlite3_int64 *p = 0;
000358    if( nBytes>0 ){
000359      memsys5Enter();
000360      p = memsys5MallocUnsafe(nBytes);
000361      memsys5Leave();
000362    }
000363    return (void*)p; 
000364  }
000365  
000366  /*
000367  ** Free memory.
000368  **
000369  ** The outer layer memory allocator prevents this routine from
000370  ** being called with pPrior==0.
000371  */
000372  static void memsys5Free(void *pPrior){
000373    assert( pPrior!=0 );
000374    memsys5Enter();
000375    memsys5FreeUnsafe(pPrior);
000376    memsys5Leave();  
000377  }
000378  
000379  /*
000380  ** Change the size of an existing memory allocation.
000381  **
000382  ** The outer layer memory allocator prevents this routine from
000383  ** being called with pPrior==0.  
000384  **
000385  ** nBytes is always a value obtained from a prior call to
000386  ** memsys5Round().  Hence nBytes is always a non-negative power
000387  ** of two.  If nBytes==0 that means that an oversize allocation
000388  ** (an allocation larger than 0x40000000) was requested and this
000389  ** routine should return 0 without freeing pPrior.
000390  */
000391  static void *memsys5Realloc(void *pPrior, int nBytes){
000392    int nOld;
000393    void *p;
000394    assert( pPrior!=0 );
000395    assert( (nBytes&(nBytes-1))==0 );  /* EV: R-46199-30249 */
000396    assert( nBytes>=0 );
000397    if( nBytes==0 ){
000398      return 0;
000399    }
000400    nOld = memsys5Size(pPrior);
000401    if( nBytes<=nOld ){
000402      return pPrior;
000403    }
000404    p = memsys5Malloc(nBytes);
000405    if( p ){
000406      memcpy(p, pPrior, nOld);
000407      memsys5Free(pPrior);
000408    }
000409    return p;
000410  }
000411  
000412  /*
000413  ** Round up a request size to the next valid allocation size.  If
000414  ** the allocation is too large to be handled by this allocation system,
000415  ** return 0.
000416  **
000417  ** All allocations must be a power of two and must be expressed by a
000418  ** 32-bit signed integer.  Hence the largest allocation is 0x40000000
000419  ** or 1073741824 bytes.
000420  */
000421  static int memsys5Roundup(int n){
000422    int iFullSz;
000423    if( n<=mem5.szAtom*2 ){
000424      if( n<=mem5.szAtom ) return mem5.szAtom;
000425      return mem5.szAtom*2;
000426    }
000427    if( n>0x10000000 ){
000428      if( n>0x40000000 ) return 0;
000429      if( n>0x20000000 ) return 0x40000000;
000430      return 0x20000000;
000431    }
000432    for(iFullSz=mem5.szAtom*8; iFullSz<n; iFullSz *= 4);
000433    if( (iFullSz/2)>=(i64)n ) return iFullSz/2;
000434    return iFullSz;
000435  }
000436  
000437  /*
000438  ** Return the ceiling of the logarithm base 2 of iValue.
000439  **
000440  ** Examples:   memsys5Log(1) -> 0
000441  **             memsys5Log(2) -> 1
000442  **             memsys5Log(4) -> 2
000443  **             memsys5Log(5) -> 3
000444  **             memsys5Log(8) -> 3
000445  **             memsys5Log(9) -> 4
000446  */
000447  static int memsys5Log(int iValue){
000448    int iLog;
000449    for(iLog=0; (iLog<(int)((sizeof(int)*8)-1)) && (1<<iLog)<iValue; iLog++);
000450    return iLog;
000451  }
000452  
000453  /*
000454  ** Initialize the memory allocator.
000455  **
000456  ** This routine is not threadsafe.  The caller must be holding a mutex
000457  ** to prevent multiple threads from entering at the same time.
000458  */
000459  static int memsys5Init(void *NotUsed){
000460    int ii;            /* Loop counter */
000461    int nByte;         /* Number of bytes of memory available to this allocator */
000462    u8 *zByte;         /* Memory usable by this allocator */
000463    int nMinLog;       /* Log base 2 of minimum allocation size in bytes */
000464    int iOffset;       /* An offset into mem5.aCtrl[] */
000465  
000466    UNUSED_PARAMETER(NotUsed);
000467  
000468    /* For the purposes of this routine, disable the mutex */
000469    mem5.mutex = 0;
000470  
000471    /* The size of a Mem5Link object must be a power of two.  Verify that
000472    ** this is case.
000473    */
000474    assert( (sizeof(Mem5Link)&(sizeof(Mem5Link)-1))==0 );
000475  
000476    nByte = sqlite3GlobalConfig.nHeap;
000477    zByte = (u8*)sqlite3GlobalConfig.pHeap;
000478    assert( zByte!=0 );  /* sqlite3_config() does not allow otherwise */
000479  
000480    /* boundaries on sqlite3GlobalConfig.mnReq are enforced in sqlite3_config() */
000481    nMinLog = memsys5Log(sqlite3GlobalConfig.mnReq);
000482    mem5.szAtom = (1<<nMinLog);
000483    while( (int)sizeof(Mem5Link)>mem5.szAtom ){
000484      mem5.szAtom = mem5.szAtom << 1;
000485    }
000486  
000487    mem5.nBlock = (nByte / (mem5.szAtom+sizeof(u8)));
000488    mem5.zPool = zByte;
000489    mem5.aCtrl = (u8 *)&mem5.zPool[mem5.nBlock*mem5.szAtom];
000490  
000491    for(ii=0; ii<=LOGMAX; ii++){
000492      mem5.aiFreelist[ii] = -1;
000493    }
000494  
000495    iOffset = 0;
000496    for(ii=LOGMAX; ii>=0; ii--){
000497      int nAlloc = (1<<ii);
000498      if( (iOffset+nAlloc)<=mem5.nBlock ){
000499        mem5.aCtrl[iOffset] = ii | CTRL_FREE;
000500        memsys5Link(iOffset, ii);
000501        iOffset += nAlloc;
000502      }
000503      assert((iOffset+nAlloc)>mem5.nBlock);
000504    }
000505  
000506    /* If a mutex is required for normal operation, allocate one */
000507    if( sqlite3GlobalConfig.bMemstat==0 ){
000508      mem5.mutex = sqlite3MutexAlloc(SQLITE_MUTEX_STATIC_MEM);
000509    }
000510  
000511    return SQLITE_OK;
000512  }
000513  
000514  /*
000515  ** Deinitialize this module.
000516  */
000517  static void memsys5Shutdown(void *NotUsed){
000518    UNUSED_PARAMETER(NotUsed);
000519    mem5.mutex = 0;
000520    return;
000521  }
000522  
000523  #ifdef SQLITE_TEST
000524  /*
000525  ** Open the file indicated and write a log of all unfreed memory 
000526  ** allocations into that log.
000527  */
000528  void sqlite3Memsys5Dump(const char *zFilename){
000529    FILE *out;
000530    int i, j, n;
000531    int nMinLog;
000532  
000533    if( zFilename==0 || zFilename[0]==0 ){
000534      out = stdout;
000535    }else{
000536      out = fopen(zFilename, "w");
000537      if( out==0 ){
000538        fprintf(stderr, "** Unable to output memory debug output log: %s **\n",
000539                        zFilename);
000540        return;
000541      }
000542    }
000543    memsys5Enter();
000544    nMinLog = memsys5Log(mem5.szAtom);
000545    for(i=0; i<=LOGMAX && i+nMinLog<32; i++){
000546      for(n=0, j=mem5.aiFreelist[i]; j>=0; j = MEM5LINK(j)->next, n++){}
000547      fprintf(out, "freelist items of size %d: %d\n", mem5.szAtom << i, n);
000548    }
000549    fprintf(out, "mem5.nAlloc       = %llu\n", mem5.nAlloc);
000550    fprintf(out, "mem5.totalAlloc   = %llu\n", mem5.totalAlloc);
000551    fprintf(out, "mem5.totalExcess  = %llu\n", mem5.totalExcess);
000552    fprintf(out, "mem5.currentOut   = %u\n", mem5.currentOut);
000553    fprintf(out, "mem5.currentCount = %u\n", mem5.currentCount);
000554    fprintf(out, "mem5.maxOut       = %u\n", mem5.maxOut);
000555    fprintf(out, "mem5.maxCount     = %u\n", mem5.maxCount);
000556    fprintf(out, "mem5.maxRequest   = %u\n", mem5.maxRequest);
000557    memsys5Leave();
000558    if( out==stdout ){
000559      fflush(stdout);
000560    }else{
000561      fclose(out);
000562    }
000563  }
000564  #endif
000565  
000566  /*
000567  ** This routine is the only routine in this file with external 
000568  ** linkage. It returns a pointer to a static sqlite3_mem_methods
000569  ** struct populated with the memsys5 methods.
000570  */
000571  const sqlite3_mem_methods *sqlite3MemGetMemsys5(void){
000572    static const sqlite3_mem_methods memsys5Methods = {
000573       memsys5Malloc,
000574       memsys5Free,
000575       memsys5Realloc,
000576       memsys5Size,
000577       memsys5Roundup,
000578       memsys5Init,
000579       memsys5Shutdown,
000580       0
000581    };
000582    return &memsys5Methods;
000583  }
000584  
000585  #endif /* SQLITE_ENABLE_MEMSYS5 */