000001  /*
000002  ** 2007 August 15
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  **
000013  ** This file contains low-level memory allocation drivers for when
000014  ** SQLite will use the standard C-library malloc/realloc/free interface
000015  ** to obtain the memory it needs while adding lots of additional debugging
000016  ** information to each allocation in order to help detect and fix memory
000017  ** leaks and memory usage errors.
000018  **
000019  ** This file contains implementations of the low-level memory allocation
000020  ** routines specified in the sqlite3_mem_methods object.
000021  */
000022  #include "sqliteInt.h"
000023  
000024  /*
000025  ** This version of the memory allocator is used only if the
000026  ** SQLITE_MEMDEBUG macro is defined
000027  */
000028  #ifdef SQLITE_MEMDEBUG
000029  
000030  /*
000031  ** The backtrace functionality is only available with GLIBC
000032  */
000033  #ifdef __GLIBC__
000034    extern int backtrace(void**,int);
000035    extern void backtrace_symbols_fd(void*const*,int,int);
000036  #else
000037  # define backtrace(A,B) 1
000038  # define backtrace_symbols_fd(A,B,C)
000039  #endif
000040  #include <stdio.h>
000041  
000042  /*
000043  ** Each memory allocation looks like this:
000044  **
000045  **  ------------------------------------------------------------------------
000046  **  | Title |  backtrace pointers |  MemBlockHdr |  allocation |  EndGuard |
000047  **  ------------------------------------------------------------------------
000048  **
000049  ** The application code sees only a pointer to the allocation.  We have
000050  ** to back up from the allocation pointer to find the MemBlockHdr.  The
000051  ** MemBlockHdr tells us the size of the allocation and the number of
000052  ** backtrace pointers.  There is also a guard word at the end of the
000053  ** MemBlockHdr.
000054  */
000055  struct MemBlockHdr {
000056    i64 iSize;                          /* Size of this allocation */
000057    struct MemBlockHdr *pNext, *pPrev;  /* Linked list of all unfreed memory */
000058    char nBacktrace;                    /* Number of backtraces on this alloc */
000059    char nBacktraceSlots;               /* Available backtrace slots */
000060    u8 nTitle;                          /* Bytes of title; includes '\0' */
000061    u8 eType;                           /* Allocation type code */
000062    int iForeGuard;                     /* Guard word for sanity */
000063  };
000064  
000065  /*
000066  ** Guard words
000067  */
000068  #define FOREGUARD 0x80F5E153
000069  #define REARGUARD 0xE4676B53
000070  
000071  /*
000072  ** Number of malloc size increments to track.
000073  */
000074  #define NCSIZE  1000
000075  
000076  /*
000077  ** All of the static variables used by this module are collected
000078  ** into a single structure named "mem".  This is to keep the
000079  ** static variables organized and to reduce namespace pollution
000080  ** when this module is combined with other in the amalgamation.
000081  */
000082  static struct {
000083    
000084    /*
000085    ** Mutex to control access to the memory allocation subsystem.
000086    */
000087    sqlite3_mutex *mutex;
000088  
000089    /*
000090    ** Head and tail of a linked list of all outstanding allocations
000091    */
000092    struct MemBlockHdr *pFirst;
000093    struct MemBlockHdr *pLast;
000094    
000095    /*
000096    ** The number of levels of backtrace to save in new allocations.
000097    */
000098    int nBacktrace;
000099    void (*xBacktrace)(int, int, void **);
000100  
000101    /*
000102    ** Title text to insert in front of each block
000103    */
000104    int nTitle;        /* Bytes of zTitle to save.  Includes '\0' and padding */
000105    char zTitle[100];  /* The title text */
000106  
000107    /* 
000108    ** sqlite3MallocDisallow() increments the following counter.
000109    ** sqlite3MallocAllow() decrements it.
000110    */
000111    int disallow; /* Do not allow memory allocation */
000112  
000113    /*
000114    ** Gather statistics on the sizes of memory allocations.
000115    ** nAlloc[i] is the number of allocation attempts of i*8
000116    ** bytes.  i==NCSIZE is the number of allocation attempts for
000117    ** sizes more than NCSIZE*8 bytes.
000118    */
000119    int nAlloc[NCSIZE];      /* Total number of allocations */
000120    int nCurrent[NCSIZE];    /* Current number of allocations */
000121    int mxCurrent[NCSIZE];   /* Highwater mark for nCurrent */
000122  
000123  } mem;
000124  
000125  
000126  /*
000127  ** Adjust memory usage statistics
000128  */
000129  static void adjustStats(int iSize, int increment){
000130    int i = ROUND8(iSize)/8;
000131    if( i>NCSIZE-1 ){
000132      i = NCSIZE - 1;
000133    }
000134    if( increment>0 ){
000135      mem.nAlloc[i]++;
000136      mem.nCurrent[i]++;
000137      if( mem.nCurrent[i]>mem.mxCurrent[i] ){
000138        mem.mxCurrent[i] = mem.nCurrent[i];
000139      }
000140    }else{
000141      mem.nCurrent[i]--;
000142      assert( mem.nCurrent[i]>=0 );
000143    }
000144  }
000145  
000146  /*
000147  ** Given an allocation, find the MemBlockHdr for that allocation.
000148  **
000149  ** This routine checks the guards at either end of the allocation and
000150  ** if they are incorrect it asserts.
000151  */
000152  static struct MemBlockHdr *sqlite3MemsysGetHeader(void *pAllocation){
000153    struct MemBlockHdr *p;
000154    int *pInt;
000155    u8 *pU8;
000156    int nReserve;
000157  
000158    p = (struct MemBlockHdr*)pAllocation;
000159    p--;
000160    assert( p->iForeGuard==(int)FOREGUARD );
000161    nReserve = ROUND8(p->iSize);
000162    pInt = (int*)pAllocation;
000163    pU8 = (u8*)pAllocation;
000164    assert( pInt[nReserve/sizeof(int)]==(int)REARGUARD );
000165    /* This checks any of the "extra" bytes allocated due
000166    ** to rounding up to an 8 byte boundary to ensure 
000167    ** they haven't been overwritten.
000168    */
000169    while( nReserve-- > p->iSize ) assert( pU8[nReserve]==0x65 );
000170    return p;
000171  }
000172  
000173  /*
000174  ** Return the number of bytes currently allocated at address p.
000175  */
000176  static int sqlite3MemSize(void *p){
000177    struct MemBlockHdr *pHdr;
000178    if( !p ){
000179      return 0;
000180    }
000181    pHdr = sqlite3MemsysGetHeader(p);
000182    return (int)pHdr->iSize;
000183  }
000184  
000185  /*
000186  ** Initialize the memory allocation subsystem.
000187  */
000188  static int sqlite3MemInit(void *NotUsed){
000189    UNUSED_PARAMETER(NotUsed);
000190    assert( (sizeof(struct MemBlockHdr)&7) == 0 );
000191    if( !sqlite3GlobalConfig.bMemstat ){
000192      /* If memory status is enabled, then the malloc.c wrapper will already
000193      ** hold the STATIC_MEM mutex when the routines here are invoked. */
000194      mem.mutex = sqlite3MutexAlloc(SQLITE_MUTEX_STATIC_MEM);
000195    }
000196    return SQLITE_OK;
000197  }
000198  
000199  /*
000200  ** Deinitialize the memory allocation subsystem.
000201  */
000202  static void sqlite3MemShutdown(void *NotUsed){
000203    UNUSED_PARAMETER(NotUsed);
000204    mem.mutex = 0;
000205  }
000206  
000207  /*
000208  ** Round up a request size to the next valid allocation size.
000209  */
000210  static int sqlite3MemRoundup(int n){
000211    return ROUND8(n);
000212  }
000213  
000214  /*
000215  ** Fill a buffer with pseudo-random bytes.  This is used to preset
000216  ** the content of a new memory allocation to unpredictable values and
000217  ** to clear the content of a freed allocation to unpredictable values.
000218  */
000219  static void randomFill(char *pBuf, int nByte){
000220    unsigned int x, y, r;
000221    x = SQLITE_PTR_TO_INT(pBuf);
000222    y = nByte | 1;
000223    while( nByte >= 4 ){
000224      x = (x>>1) ^ (-(int)(x&1) & 0xd0000001);
000225      y = y*1103515245 + 12345;
000226      r = x ^ y;
000227      *(int*)pBuf = r;
000228      pBuf += 4;
000229      nByte -= 4;
000230    }
000231    while( nByte-- > 0 ){
000232      x = (x>>1) ^ (-(int)(x&1) & 0xd0000001);
000233      y = y*1103515245 + 12345;
000234      r = x ^ y;
000235      *(pBuf++) = r & 0xff;
000236    }
000237  }
000238  
000239  /*
000240  ** Allocate nByte bytes of memory.
000241  */
000242  static void *sqlite3MemMalloc(int nByte){
000243    struct MemBlockHdr *pHdr;
000244    void **pBt;
000245    char *z;
000246    int *pInt;
000247    void *p = 0;
000248    int totalSize;
000249    int nReserve;
000250    sqlite3_mutex_enter(mem.mutex);
000251    assert( mem.disallow==0 );
000252    nReserve = ROUND8(nByte);
000253    totalSize = nReserve + sizeof(*pHdr) + sizeof(int) +
000254                 mem.nBacktrace*sizeof(void*) + mem.nTitle;
000255    p = malloc(totalSize);
000256    if( p ){
000257      z = p;
000258      pBt = (void**)&z[mem.nTitle];
000259      pHdr = (struct MemBlockHdr*)&pBt[mem.nBacktrace];
000260      pHdr->pNext = 0;
000261      pHdr->pPrev = mem.pLast;
000262      if( mem.pLast ){
000263        mem.pLast->pNext = pHdr;
000264      }else{
000265        mem.pFirst = pHdr;
000266      }
000267      mem.pLast = pHdr;
000268      pHdr->iForeGuard = FOREGUARD;
000269      pHdr->eType = MEMTYPE_HEAP;
000270      pHdr->nBacktraceSlots = mem.nBacktrace;
000271      pHdr->nTitle = mem.nTitle;
000272      if( mem.nBacktrace ){
000273        void *aAddr[40];
000274        pHdr->nBacktrace = backtrace(aAddr, mem.nBacktrace+1)-1;
000275        memcpy(pBt, &aAddr[1], pHdr->nBacktrace*sizeof(void*));
000276        assert(pBt[0]);
000277        if( mem.xBacktrace ){
000278          mem.xBacktrace(nByte, pHdr->nBacktrace-1, &aAddr[1]);
000279        }
000280      }else{
000281        pHdr->nBacktrace = 0;
000282      }
000283      if( mem.nTitle ){
000284        memcpy(z, mem.zTitle, mem.nTitle);
000285      }
000286      pHdr->iSize = nByte;
000287      adjustStats(nByte, +1);
000288      pInt = (int*)&pHdr[1];
000289      pInt[nReserve/sizeof(int)] = REARGUARD;
000290      randomFill((char*)pInt, nByte);
000291      memset(((char*)pInt)+nByte, 0x65, nReserve-nByte);
000292      p = (void*)pInt;
000293    }
000294    sqlite3_mutex_leave(mem.mutex);
000295    return p; 
000296  }
000297  
000298  /*
000299  ** Free memory.
000300  */
000301  static void sqlite3MemFree(void *pPrior){
000302    struct MemBlockHdr *pHdr;
000303    void **pBt;
000304    char *z;
000305    assert( sqlite3GlobalConfig.bMemstat || sqlite3GlobalConfig.bCoreMutex==0 
000306         || mem.mutex!=0 );
000307    pHdr = sqlite3MemsysGetHeader(pPrior);
000308    pBt = (void**)pHdr;
000309    pBt -= pHdr->nBacktraceSlots;
000310    sqlite3_mutex_enter(mem.mutex);
000311    if( pHdr->pPrev ){
000312      assert( pHdr->pPrev->pNext==pHdr );
000313      pHdr->pPrev->pNext = pHdr->pNext;
000314    }else{
000315      assert( mem.pFirst==pHdr );
000316      mem.pFirst = pHdr->pNext;
000317    }
000318    if( pHdr->pNext ){
000319      assert( pHdr->pNext->pPrev==pHdr );
000320      pHdr->pNext->pPrev = pHdr->pPrev;
000321    }else{
000322      assert( mem.pLast==pHdr );
000323      mem.pLast = pHdr->pPrev;
000324    }
000325    z = (char*)pBt;
000326    z -= pHdr->nTitle;
000327    adjustStats((int)pHdr->iSize, -1);
000328    randomFill(z, sizeof(void*)*pHdr->nBacktraceSlots + sizeof(*pHdr) +
000329                  (int)pHdr->iSize + sizeof(int) + pHdr->nTitle);
000330    free(z);
000331    sqlite3_mutex_leave(mem.mutex);  
000332  }
000333  
000334  /*
000335  ** Change the size of an existing memory allocation.
000336  **
000337  ** For this debugging implementation, we *always* make a copy of the
000338  ** allocation into a new place in memory.  In this way, if the 
000339  ** higher level code is using pointer to the old allocation, it is 
000340  ** much more likely to break and we are much more liking to find
000341  ** the error.
000342  */
000343  static void *sqlite3MemRealloc(void *pPrior, int nByte){
000344    struct MemBlockHdr *pOldHdr;
000345    void *pNew;
000346    assert( mem.disallow==0 );
000347    assert( (nByte & 7)==0 );     /* EV: R-46199-30249 */
000348    pOldHdr = sqlite3MemsysGetHeader(pPrior);
000349    pNew = sqlite3MemMalloc(nByte);
000350    if( pNew ){
000351      memcpy(pNew, pPrior, (int)(nByte<pOldHdr->iSize ? nByte : pOldHdr->iSize));
000352      if( nByte>pOldHdr->iSize ){
000353        randomFill(&((char*)pNew)[pOldHdr->iSize], nByte - (int)pOldHdr->iSize);
000354      }
000355      sqlite3MemFree(pPrior);
000356    }
000357    return pNew;
000358  }
000359  
000360  /*
000361  ** Populate the low-level memory allocation function pointers in
000362  ** sqlite3GlobalConfig.m with pointers to the routines in this file.
000363  */
000364  void sqlite3MemSetDefault(void){
000365    static const sqlite3_mem_methods defaultMethods = {
000366       sqlite3MemMalloc,
000367       sqlite3MemFree,
000368       sqlite3MemRealloc,
000369       sqlite3MemSize,
000370       sqlite3MemRoundup,
000371       sqlite3MemInit,
000372       sqlite3MemShutdown,
000373       0
000374    };
000375    sqlite3_config(SQLITE_CONFIG_MALLOC, &defaultMethods);
000376  }
000377  
000378  /*
000379  ** Set the "type" of an allocation.
000380  */
000381  void sqlite3MemdebugSetType(void *p, u8 eType){
000382    if( p && sqlite3GlobalConfig.m.xMalloc==sqlite3MemMalloc ){
000383      struct MemBlockHdr *pHdr;
000384      pHdr = sqlite3MemsysGetHeader(p);
000385      assert( pHdr->iForeGuard==FOREGUARD );
000386      pHdr->eType = eType;
000387    }
000388  }
000389  
000390  /*
000391  ** Return TRUE if the mask of type in eType matches the type of the
000392  ** allocation p.  Also return true if p==NULL.
000393  **
000394  ** This routine is designed for use within an assert() statement, to
000395  ** verify the type of an allocation.  For example:
000396  **
000397  **     assert( sqlite3MemdebugHasType(p, MEMTYPE_HEAP) );
000398  */
000399  int sqlite3MemdebugHasType(void *p, u8 eType){
000400    int rc = 1;
000401    if( p && sqlite3GlobalConfig.m.xMalloc==sqlite3MemMalloc ){
000402      struct MemBlockHdr *pHdr;
000403      pHdr = sqlite3MemsysGetHeader(p);
000404      assert( pHdr->iForeGuard==FOREGUARD );         /* Allocation is valid */
000405      if( (pHdr->eType&eType)==0 ){
000406        rc = 0;
000407      }
000408    }
000409    return rc;
000410  }
000411  
000412  /*
000413  ** Return TRUE if the mask of type in eType matches no bits of the type of the
000414  ** allocation p.  Also return true if p==NULL.
000415  **
000416  ** This routine is designed for use within an assert() statement, to
000417  ** verify the type of an allocation.  For example:
000418  **
000419  **     assert( sqlite3MemdebugNoType(p, MEMTYPE_LOOKASIDE) );
000420  */
000421  int sqlite3MemdebugNoType(void *p, u8 eType){
000422    int rc = 1;
000423    if( p && sqlite3GlobalConfig.m.xMalloc==sqlite3MemMalloc ){
000424      struct MemBlockHdr *pHdr;
000425      pHdr = sqlite3MemsysGetHeader(p);
000426      assert( pHdr->iForeGuard==FOREGUARD );         /* Allocation is valid */
000427      if( (pHdr->eType&eType)!=0 ){
000428        rc = 0;
000429      }
000430    }
000431    return rc;
000432  }
000433  
000434  /*
000435  ** Set the number of backtrace levels kept for each allocation.
000436  ** A value of zero turns off backtracing.  The number is always rounded
000437  ** up to a multiple of 2.
000438  */
000439  void sqlite3MemdebugBacktrace(int depth){
000440    if( depth<0 ){ depth = 0; }
000441    if( depth>20 ){ depth = 20; }
000442    depth = (depth+1)&0xfe;
000443    mem.nBacktrace = depth;
000444  }
000445  
000446  void sqlite3MemdebugBacktraceCallback(void (*xBacktrace)(int, int, void **)){
000447    mem.xBacktrace = xBacktrace;
000448  }
000449  
000450  /*
000451  ** Set the title string for subsequent allocations.
000452  */
000453  void sqlite3MemdebugSettitle(const char *zTitle){
000454    unsigned int n = sqlite3Strlen30(zTitle) + 1;
000455    sqlite3_mutex_enter(mem.mutex);
000456    if( n>=sizeof(mem.zTitle) ) n = sizeof(mem.zTitle)-1;
000457    memcpy(mem.zTitle, zTitle, n);
000458    mem.zTitle[n] = 0;
000459    mem.nTitle = ROUND8(n);
000460    sqlite3_mutex_leave(mem.mutex);
000461  }
000462  
000463  void sqlite3MemdebugSync(){
000464    struct MemBlockHdr *pHdr;
000465    for(pHdr=mem.pFirst; pHdr; pHdr=pHdr->pNext){
000466      void **pBt = (void**)pHdr;
000467      pBt -= pHdr->nBacktraceSlots;
000468      mem.xBacktrace((int)pHdr->iSize, pHdr->nBacktrace-1, &pBt[1]);
000469    }
000470  }
000471  
000472  /*
000473  ** Open the file indicated and write a log of all unfreed memory 
000474  ** allocations into that log.
000475  */
000476  void sqlite3MemdebugDump(const char *zFilename){
000477    FILE *out;
000478    struct MemBlockHdr *pHdr;
000479    void **pBt;
000480    int i;
000481    out = fopen(zFilename, "w");
000482    if( out==0 ){
000483      fprintf(stderr, "** Unable to output memory debug output log: %s **\n",
000484                      zFilename);
000485      return;
000486    }
000487    for(pHdr=mem.pFirst; pHdr; pHdr=pHdr->pNext){
000488      char *z = (char*)pHdr;
000489      z -= pHdr->nBacktraceSlots*sizeof(void*) + pHdr->nTitle;
000490      fprintf(out, "**** %lld bytes at %p from %s ****\n", 
000491              pHdr->iSize, &pHdr[1], pHdr->nTitle ? z : "???");
000492      if( pHdr->nBacktrace ){
000493        fflush(out);
000494        pBt = (void**)pHdr;
000495        pBt -= pHdr->nBacktraceSlots;
000496        backtrace_symbols_fd(pBt, pHdr->nBacktrace, fileno(out));
000497        fprintf(out, "\n");
000498      }
000499    }
000500    fprintf(out, "COUNTS:\n");
000501    for(i=0; i<NCSIZE-1; i++){
000502      if( mem.nAlloc[i] ){
000503        fprintf(out, "   %5d: %10d %10d %10d\n", 
000504              i*8, mem.nAlloc[i], mem.nCurrent[i], mem.mxCurrent[i]);
000505      }
000506    }
000507    if( mem.nAlloc[NCSIZE-1] ){
000508      fprintf(out, "   %5d: %10d %10d %10d\n",
000509               NCSIZE*8-8, mem.nAlloc[NCSIZE-1],
000510               mem.nCurrent[NCSIZE-1], mem.mxCurrent[NCSIZE-1]);
000511    }
000512    fclose(out);
000513  }
000514  
000515  /*
000516  ** Return the number of times sqlite3MemMalloc() has been called.
000517  */
000518  int sqlite3MemdebugMallocCount(){
000519    int i;
000520    int nTotal = 0;
000521    for(i=0; i<NCSIZE; i++){
000522      nTotal += mem.nAlloc[i];
000523    }
000524    return nTotal;
000525  }
000526  
000527  
000528  #endif /* SQLITE_MEMDEBUG */