/*

 ** 2007 August 15

 **

 ** The author disclaims copyright to this source code.  In place of

 ** a legal notice, here is a blessing:

 **

 **    May you do good and not evil.

 **    May you find forgiveness for yourself and forgive others.

 **    May you share freely, never taking more than you give.

 **

 *************************************************************************

 **

 ** This file contains low-level memory allocation drivers for when

 ** SQLite will use the standard C-library malloc/realloc/free interface

 ** to obtain the memory it needs while adding lots of additional debugging

 ** information to each allocation in order to help detect and fix memory

 ** leaks and memory usage errors.

 **

 ** This file contains implementations of the low-level memory allocation

 ** routines specified in the sqlite3_mem_methods object.

 **

 ** $Id: mem2.c,v 1.37 2008/07/25 08:49:00 danielk1977 Exp $

 */

 #include "sqliteInt.h"

 /*

 ** This version of the memory allocator is used only if the

 ** SQLITE_MEMDEBUG macro is defined

 */

 #ifdef SQLITE_MEMDEBUG

 /*

 ** The backtrace functionality is only available with GLIBC

 */

 #ifdef __GLIBC__

   extern int backtrace(void**,int);

   extern void backtrace_symbols_fd(void*const*,int,int);

 #else

 # define backtrace(A,B) 0

 # define backtrace_symbols_fd(A,B,C)

 #endif

 #include <stdio.h>

 /*

 ** Each memory allocation looks like this:

 **

 **  ------------------------------------------------------------------------

 **  | Title |  backtrace pointers |  MemBlockHdr |  allocation |  EndGuard |

 **  ------------------------------------------------------------------------

 **

 ** The application code sees only a pointer to the allocation.  We have

 ** to back up from the allocation pointer to find the MemBlockHdr.  The

 ** MemBlockHdr tells us the size of the allocation and the number of

 ** backtrace pointers.  There is also a guard word at the end of the

 ** MemBlockHdr.

 */

 struct MemBlockHdr {

   i64 iSize;                          /* Size of this allocation */

   struct MemBlockHdr *pNext, *pPrev;  /* Linked list of all unfreed memory */

   char nBacktrace;                    /* Number of backtraces on this alloc */

   char nBacktraceSlots;               /* Available backtrace slots */

   short nTitle;                       /* Bytes of title; includes '\0' */

   int iForeGuard;                     /* Guard word for sanity */

 };

 /*

 ** Guard words

 */

 #define FOREGUARD 0x80F5E153

 #define REARGUARD 0xE4676B53

 /*

 ** Number of malloc size increments to track.

 */

 #define NCSIZE  1000

 /*

 ** All of the static variables used by this module are collected

 ** into a single structure named "mem".  This is to keep the

 ** static variables organized and to reduce namespace pollution

 ** when this module is combined with other in the amalgamation.

 */

 static struct {

   /*

   ** Mutex to control access to the memory allocation subsystem.

   */

   sqlite3_mutex *mutex;

   /*

   ** Head and tail of a linked list of all outstanding allocations

   */

   struct MemBlockHdr *pFirst;

   struct MemBlockHdr *pLast;

   /*

   ** The number of levels of backtrace to save in new allocations.

   */

   int nBacktrace;

   void (*xBacktrace)(int, int, void **);

   /*

   ** Title text to insert in front of each block

   */

   int nTitle;        /* Bytes of zTitle to save.  Includes '\0' and padding */

   char zTitle[100];  /* The title text */

   /* 

   ** sqlite3MallocDisallow() increments the following counter.

   ** sqlite3MallocAllow() decrements it.

   */

   int disallow; /* Do not allow memory allocation */

   /*

   ** Gather statistics on the sizes of memory allocations.

   ** nAlloc[i] is the number of allocation attempts of i*8

   ** bytes.  i==NCSIZE is the number of allocation attempts for

   ** sizes more than NCSIZE*8 bytes.

   */

   int nAlloc[NCSIZE];      /* Total number of allocations */

   int nCurrent[NCSIZE];    /* Current number of allocations */

   int mxCurrent[NCSIZE];   /* Highwater mark for nCurrent */

 } mem;

 /*

 ** Adjust memory usage statistics

 */

 static void adjustStats(int iSize, int increment){

   int i = ((iSize+7)&~7)/8;

   if( i>NCSIZE-1 ){

     i = NCSIZE - 1;

   }

   if( increment>0 ){

     mem.nAlloc[i]++;

     mem.nCurrent[i]++;

     if( mem.nCurrent[i]>mem.mxCurrent[i] ){

       mem.mxCurrent[i] = mem.nCurrent[i];

     }

   }else{

     mem.nCurrent[i]--;

     assert( mem.nCurrent[i]>=0 );

   }

 }

 /*

 ** Given an allocation, find the MemBlockHdr for that allocation.

 **

 ** This routine checks the guards at either end of the allocation and

 ** if they are incorrect it asserts.

 */

 static struct MemBlockHdr *sqlite3MemsysGetHeader(void *pAllocation){

   struct MemBlockHdr *p;

   int *pInt;

   u8 *pU8;

   int nReserve;

   p = (struct MemBlockHdr*)pAllocation;

   p--;

   assert( p->iForeGuard==FOREGUARD );

   nReserve = (p->iSize+7)&~7;

   pInt = (int*)pAllocation;

   pU8 = (u8*)pAllocation;

   assert( pInt[nReserve/sizeof(int)]==REARGUARD );

   assert( (nReserve-0)<=p->iSize || pU8[nReserve-1]==0x65 );

   assert( (nReserve-1)<=p->iSize || pU8[nReserve-2]==0x65 );

   assert( (nReserve-2)<=p->iSize || pU8[nReserve-3]==0x65 );

   return p;

 }

 /*

 ** Return the number of bytes currently allocated at address p.

 */

 static int sqlite3MemSize(void *p){

   struct MemBlockHdr *pHdr;

   if( !p ){

     return 0;

   }

   pHdr = sqlite3MemsysGetHeader(p);

   return pHdr->iSize;

 }

 /*

 ** Initialize the memory allocation subsystem.

 */

 static int sqlite3MemInit(void *NotUsed){

   if( !sqlite3Config.bMemstat ){

     /* If memory status is enabled, then the malloc.c wrapper will already

     ** hold the STATIC_MEM mutex when the routines here are invoked. */

     mem.mutex = sqlite3MutexAlloc(SQLITE_MUTEX_STATIC_MEM);

   }

   return SQLITE_OK;

 }

 /*

 ** Deinitialize the memory allocation subsystem.

 */

 static void sqlite3MemShutdown(void *NotUsed){

   mem.mutex = 0;

 }

 /*

 ** Round up a request size to the next valid allocation size.

 */

 static int sqlite3MemRoundup(int n){

   return (n+7) & ~7;

 }

 /*

 ** Allocate nByte bytes of memory.

 */

 static void *sqlite3MemMalloc(int nByte){

   struct MemBlockHdr *pHdr;

   void **pBt;

   char *z;

   int *pInt;

   void *p = 0;

   int totalSize;

   int nReserve;

   sqlite3_mutex_enter(mem.mutex);

   assert( mem.disallow==0 );

   nReserve = (nByte+7)&~7;

   totalSize = nReserve + sizeof(*pHdr) + sizeof(int) +

                mem.nBacktrace*sizeof(void*) + mem.nTitle;

   p = malloc(totalSize);

   if( p ){

     z = p;

     pBt = (void**)&z[mem.nTitle];

     pHdr = (struct MemBlockHdr*)&pBt[mem.nBacktrace];

     pHdr->pNext = 0;

     pHdr->pPrev = mem.pLast;

     if( mem.pLast ){

       mem.pLast->pNext = pHdr;

     }else{

       mem.pFirst = pHdr;

     }

     mem.pLast = pHdr;

     pHdr->iForeGuard = FOREGUARD;

     pHdr->nBacktraceSlots = mem.nBacktrace;

     pHdr->nTitle = mem.nTitle;

     if( mem.nBacktrace ){

       void *aAddr[40];

       pHdr->nBacktrace = backtrace(aAddr, mem.nBacktrace+1)-1;

       memcpy(pBt, &aAddr[1], pHdr->nBacktrace*sizeof(void*));

       if( mem.xBacktrace ){

         mem.xBacktrace(nByte, pHdr->nBacktrace-1, &aAddr[1]);

       }

     }else{

       pHdr->nBacktrace = 0;

     }

     if( mem.nTitle ){

       memcpy(z, mem.zTitle, mem.nTitle);

     }

     pHdr->iSize = nByte;

     adjustStats(nByte, +1);

     pInt = (int*)&pHdr[1];

     pInt[nReserve/sizeof(int)] = REARGUARD;

     memset(pInt, 0x65, nReserve);

     p = (void*)pInt;

   }

   sqlite3_mutex_leave(mem.mutex);

   return p; 

 }

 /*

 ** Free memory.

 */

 static void sqlite3MemFree(void *pPrior){

   struct MemBlockHdr *pHdr;

   void **pBt;

   char *z;

   assert( sqlite3Config.bMemstat || mem.mutex!=0 );

   pHdr = sqlite3MemsysGetHeader(pPrior);

   pBt = (void**)pHdr;

   pBt -= pHdr->nBacktraceSlots;

   sqlite3_mutex_enter(mem.mutex);

   if( pHdr->pPrev ){

     assert( pHdr->pPrev->pNext==pHdr );

     pHdr->pPrev->pNext = pHdr->pNext;

   }else{

     assert( mem.pFirst==pHdr );

     mem.pFirst = pHdr->pNext;

   }

   if( pHdr->pNext ){

     assert( pHdr->pNext->pPrev==pHdr );

     pHdr->pNext->pPrev = pHdr->pPrev;

   }else{

     assert( mem.pLast==pHdr );

     mem.pLast = pHdr->pPrev;

   }

   z = (char*)pBt;

   z -= pHdr->nTitle;

   adjustStats(pHdr->iSize, -1);

   memset(z, 0x2b, sizeof(void*)*pHdr->nBacktraceSlots + sizeof(*pHdr) +

                   pHdr->iSize + sizeof(int) + pHdr->nTitle);

   free(z);

   sqlite3_mutex_leave(mem.mutex);  

 }

 /*

 ** Change the size of an existing memory allocation.

 **

 ** For this debugging implementation, we *always* make a copy of the

 ** allocation into a new place in memory.  In this way, if the 

 ** higher level code is using pointer to the old allocation, it is 

 ** much more likely to break and we are much more liking to find

 ** the error.

 */

 static void *sqlite3MemRealloc(void *pPrior, int nByte){

   struct MemBlockHdr *pOldHdr;

   void *pNew;

   assert( mem.disallow==0 );

   pOldHdr = sqlite3MemsysGetHeader(pPrior);

   pNew = sqlite3MemMalloc(nByte);

   if( pNew ){

     memcpy(pNew, pPrior, nByte<pOldHdr->iSize ? nByte : pOldHdr->iSize);

     if( nByte>pOldHdr->iSize ){

       memset(&((char*)pNew)[pOldHdr->iSize], 0x2b, nByte - pOldHdr->iSize);

     }

     sqlite3MemFree(pPrior);

   }

   return pNew;

 }

 const sqlite3_mem_methods *sqlite3MemGetDefault(void){

   static const sqlite3_mem_methods defaultMethods = {

      sqlite3MemMalloc,

      sqlite3MemFree,

      sqlite3MemRealloc,

      sqlite3MemSize,

      sqlite3MemRoundup,

      sqlite3MemInit,

      sqlite3MemShutdown,

      0

   };

   return &defaultMethods;

 }

 /*

 ** Populate the low-level memory allocation function pointers in

 ** sqlite3Config.m with pointers to the routines in this file.

 */

 void sqlite3MemSetDefault(void){

   sqlite3_config(SQLITE_CONFIG_MALLOC, sqlite3MemGetDefault());

 }

 /*

 ** Set the number of backtrace levels kept for each allocation.

 ** A value of zero turns off backtracing.  The number is always rounded

 ** up to a multiple of 2.

 */

 void sqlite3MemdebugBacktrace(int depth){

   if( depth<0 ){ depth = 0; }

   if( depth>20 ){ depth = 20; }

   depth = (depth+1)&0xfe;

   mem.nBacktrace = depth;

 }

 void sqlite3MemdebugBacktraceCallback(void (*xBacktrace)(int, int, void **)){

   mem.xBacktrace = xBacktrace;

 }

 /*

 ** Set the title string for subsequent allocations.

 */

 void sqlite3MemdebugSettitle(const char *zTitle){

   int n = strlen(zTitle) + 1;

   sqlite3_mutex_enter(mem.mutex);

   if( n>=sizeof(mem.zTitle) ) n = sizeof(mem.zTitle)-1;

   memcpy(mem.zTitle, zTitle, n);

   mem.zTitle[n] = 0;

   mem.nTitle = (n+7)&~7;

   sqlite3_mutex_leave(mem.mutex);

 }

 void sqlite3MemdebugSync(){

   struct MemBlockHdr *pHdr;

   for(pHdr=mem.pFirst; pHdr; pHdr=pHdr->pNext){

     void **pBt = (void**)pHdr;

     pBt -= pHdr->nBacktraceSlots;

     mem.xBacktrace(pHdr->iSize, pHdr->nBacktrace-1, &pBt[1]);

   }

 }

 /*

 ** Open the file indicated and write a log of all unfreed memory 

 ** allocations into that log.

 */

 void sqlite3MemdebugDump(const char *zFilename){

   FILE *out;

   struct MemBlockHdr *pHdr;

   void **pBt;

   int i;

   out = fopen(zFilename, "w");

   if( out==0 ){

     fprintf(stderr, "** Unable to output memory debug output log: %s **\n",

                     zFilename);

     return;

   }

   for(pHdr=mem.pFirst; pHdr; pHdr=pHdr->pNext){

     char *z = (char*)pHdr;

     z -= pHdr->nBacktraceSlots*sizeof(void*) + pHdr->nTitle;

     fprintf(out, "**** %lld bytes at %p from %s ****\n", 

             pHdr->iSize, &pHdr[1], pHdr->nTitle ? z : "???");

     if( pHdr->nBacktrace ){

       fflush(out);

       pBt = (void**)pHdr;

       pBt -= pHdr->nBacktraceSlots;

       backtrace_symbols_fd(pBt, pHdr->nBacktrace, fileno(out));

       fprintf(out, "\n");

     }

   }

   fprintf(out, "COUNTS:\n");

   for(i=0; i<NCSIZE-1; i++){

     if( mem.nAlloc[i] ){

       fprintf(out, "   %5d: %10d %10d %10d\n", 

             i*8, mem.nAlloc[i], mem.nCurrent[i], mem.mxCurrent[i]);

     }

   }

   if( mem.nAlloc[NCSIZE-1] ){

     fprintf(out, "   %5d: %10d %10d %10d\n",

              NCSIZE*8-8, mem.nAlloc[NCSIZE-1],

              mem.nCurrent[NCSIZE-1], mem.mxCurrent[NCSIZE-1]);

   }

   fclose(out);

 }

 /*

 ** Return the number of times sqlite3MemMalloc() has been called.

 */

 int sqlite3MemdebugMallocCount(){

   int i;

   int nTotal = 0;

   for(i=0; i<NCSIZE; i++){

     nTotal += mem.nAlloc[i];

   }

   return nTotal;

 }

 #endif /* SQLITE_MEMDEBUG */