1 /*

     2 ** 2007 August 15

     3 **

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

     5 ** a legal notice, here is a blessing:

     6 **

     7 **    May you do good and not evil.

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

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

    10 **

    11 *************************************************************************

    12 ** This file contains the C functions that implement a memory

    13 ** allocation subsystem for use by SQLite.  

    14 **

    15 ** $Id: mem2.cpp 1282 2008-11-13 09:31:33Z LarsPson $

    16 */

    17 

    18 /*

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

    20 ** SQLITE_MEMDEBUG macro is defined and SQLITE_OMIT_MEMORY_ALLOCATION

    21 ** is not defined.

    22 */

    23 #if defined(SQLITE_MEMDEBUG)

    24 

    25 /*

    26 ** We will eventually construct multiple memory allocation subsystems

    27 ** suitable for use in various contexts:

    28 **

    29 **    *  Normal multi-threaded builds

    30 **    *  Normal single-threaded builds

    31 **    *  Debugging builds

    32 **

    33 ** This version is suitable for use in debugging builds.

    34 **

    35 ** Features:

    36 **

    37 **    * Every allocate has guards at both ends.

    38 **    * New allocations are initialized with randomness

    39 **    * Allocations are overwritten with randomness when freed

    40 **    * Optional logs of malloc activity generated

    41 **    * Summary of outstanding allocations with backtraces to the

    42 **      point of allocation.

    43 **    * The ability to simulate memory allocation failure

    44 */

    45 #include "sqliteInt.h"

    46 #include <stdio.h>

    47 

    48 /*

    49 ** The backtrace functionality is only available with GLIBC

    50 */

    51 #ifdef __GLIBC__

    52   extern int backtrace(void**,int);

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

    54 #else

    55 # define backtrace(A,B) 0

    56 # define backtrace_symbols_fd(A,B,C)

    57 #endif

    58 

    59 /*

    60 ** Each memory allocation looks like this:

    61 **

    62 **  ------------------------------------------------------------------------

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

    64 **  ------------------------------------------------------------------------

    65 **

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

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

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

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

    70 ** MemBlockHdr.

    71 */

    72 struct MemBlockHdr {

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

    74   int iSize;                          /* Size of this allocation */

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

    76   char nBacktraceSlots;               /* Available backtrace slots */

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

    78   int iForeGuard;                     /* Guard word for sanity */

    79 };

    80 

    81 /*

    82 ** Guard words

    83 */

    84 #define FOREGUARD 0x80F5E153

    85 #define REARGUARD 0xE4676B53

    86 

    87 /*

    88 ** Number of malloc size increments to track.

    89 */

    90 #define NCSIZE  1000

    91 

    92 /*

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

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

    95 ** static variables organized and to reduce namespace pollution

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

    97 */

    98 static struct {

    99   /*

   100   ** The alarm callback and its arguments.  The mem.mutex lock will

   101   ** be held while the callback is running.  Recursive calls into

   102   ** the memory subsystem are allowed, but no new callbacks will be

   103   ** issued.  The alarmBusy variable is set to prevent recursive

   104   ** callbacks.

   105   */

   106   sqlite3_int64 alarmThreshold;

   107   void (*alarmCallback)(void*, sqlite3_int64, int);

   108   void *alarmArg;

   109   int alarmBusy;

   110   

   111   /*

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

   113   */

   114   sqlite3_mutex *mutex;

   115   

   116   /*

   117   ** Current allocation and high-water mark.

   118   */

   119   sqlite3_int64 nowUsed;

   120   sqlite3_int64 mxUsed;

   121   

   122   /*

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

   124   */

   125   struct MemBlockHdr *pFirst;

   126   struct MemBlockHdr *pLast;

   127   

   128   /*

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

   130   */

   131   int nBacktrace;

   132 

   133   /*

   134   ** Title text to insert in front of each block

   135   */

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

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

   138 

   139   /*

   140   ** These values are used to simulate malloc failures.  When

   141   ** iFail is 1, simulate a malloc failures and reset the value

   142   ** to iReset.

   143   */

   144   int iFail;    /* Decrement and fail malloc when this is 1 */

   145   int iReset;   /* When malloc fails set iiFail to this value */

   146   int iFailCnt;         /* Number of failures */

   147   int iBenignFailCnt;   /* Number of benign failures */

   148   int iNextIsBenign;    /* True if the next call to malloc may fail benignly */

   149   int iIsBenign;        /* All malloc calls may fail benignly */

   150 

   151   /* 

   152   ** sqlite3MallocDisallow() increments the following counter.

   153   ** sqlite3MallocAllow() decrements it.

   154   */

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

   156 

   157   /*

   158   ** Gather statistics on the sizes of memory allocations.

   159   ** sizeCnt[i] is the number of allocation attempts of i*8

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

   161   ** sizes more than NCSIZE*8 bytes.

   162   */

   163   int sizeCnt[NCSIZE];

   164 

   165 } mem;

   166 

   167 

   168 /*

   169 ** Enter the mutex mem.mutex. Allocate it if it is not already allocated.

   170 */

   171 static void enterMem(void){

   172   if( mem.mutex==0 ){

   173     mem.mutex = sqlite3_mutex_alloc(SQLITE_MUTEX_STATIC_MEM);

   174   }

   175   sqlite3_mutex_enter(mem.mutex);

   176 }

   177 

   178 /*

   179 ** Return the amount of memory currently checked out.

   180 */

   181 sqlite3_int64 sqlite3_memory_used(void){

   182   sqlite3_int64 n;

   183   enterMem();

   184   n = mem.nowUsed;

   185   sqlite3_mutex_leave(mem.mutex);  

   186   return n;

   187 }

   188 

   189 /*

   190 ** Return the maximum amount of memory that has ever been

   191 ** checked out since either the beginning of this process

   192 ** or since the most recent reset.

   193 */

   194 sqlite3_int64 sqlite3_memory_highwater(int resetFlag){

   195   sqlite3_int64 n;

   196   enterMem();

   197   n = mem.mxUsed;

   198   if( resetFlag ){

   199     mem.mxUsed = mem.nowUsed;

   200   }

   201   sqlite3_mutex_leave(mem.mutex);  

   202   return n;

   203 }

   204 

   205 /*

   206 ** Change the alarm callback

   207 */

   208 int sqlite3_memory_alarm(

   209   void(*xCallback)(void *pArg, sqlite3_int64 used, int N),

   210   void *pArg,

   211   sqlite3_int64 iThreshold

   212 ){

   213   enterMem();

   214   mem.alarmCallback = xCallback;

   215   mem.alarmArg = pArg;

   216   mem.alarmThreshold = iThreshold;

   217   sqlite3_mutex_leave(mem.mutex);

   218   return SQLITE_OK;

   219 }

   220 

   221 /*

   222 ** Trigger the alarm 

   223 */

   224 static void sqlite3MemsysAlarm(int nByte){

   225   void (*xCallback)(void*,sqlite3_int64,int);

   226   sqlite3_int64 nowUsed;

   227   void *pArg;

   228   if( mem.alarmCallback==0 || mem.alarmBusy  ) return;

   229   mem.alarmBusy = 1;

   230   xCallback = mem.alarmCallback;

   231   nowUsed = mem.nowUsed;

   232   pArg = mem.alarmArg;

   233   sqlite3_mutex_leave(mem.mutex);

   234   xCallback(pArg, nowUsed, nByte);

   235   sqlite3_mutex_enter(mem.mutex);

   236   mem.alarmBusy = 0;

   237 }

   238 

   239 /*

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

   241 **

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

   243 ** if they are incorrect it asserts.

   244 */

   245 static struct MemBlockHdr *sqlite3MemsysGetHeader(void *pAllocation){

   246   struct MemBlockHdr *p;

   247   int *pInt;

   248 

   249   p = (struct MemBlockHdr*)pAllocation;

   250   p--;

   251   assert( p->iForeGuard==FOREGUARD );

   252   assert( (p->iSize & 3)==0 );

   253   pInt = (int*)pAllocation;

   254   assert( pInt[p->iSize/sizeof(int)]==REARGUARD );

   255   return p;

   256 }

   257 

   258 /*

   259 ** This routine is called once the first time a simulated memory

   260 ** failure occurs.  The sole purpose of this routine is to provide

   261 ** a convenient place to set a debugger breakpoint when debugging

   262 ** errors related to malloc() failures.

   263 */

   264 static void sqlite3MemsysFailed(void){

   265   mem.iFailCnt = 0;

   266   mem.iBenignFailCnt = 0;

   267 }

   268 

   269 /*

   270 ** Allocate nByte bytes of memory.

   271 */

   272 void *sqlite3_malloc(int nByte){

   273   struct MemBlockHdr *pHdr;

   274   void **pBt;

   275   char *z;

   276   int *pInt;

   277   void *p = 0;

   278   int totalSize;

   279 

   280   if( nByte>0 ){

   281     enterMem();

   282     assert( mem.disallow==0 );

   283     if( mem.alarmCallback!=0 && mem.nowUsed+nByte>=mem.alarmThreshold ){

   284       sqlite3MemsysAlarm(nByte);

   285     }

   286     nByte = (nByte+3)&~3;

   287     if( nByte/8>NCSIZE-1 ){

   288       mem.sizeCnt[NCSIZE-1]++;

   289     }else{

   290       mem.sizeCnt[nByte/8]++;

   291     }

   292     totalSize = nByte + sizeof(*pHdr) + sizeof(int) +

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

   294     if( mem.iFail>0 ){

   295       if( mem.iFail==1 ){

   296         p = 0;

   297         mem.iFail = mem.iReset;

   298         if( mem.iFailCnt==0 ){

   299           sqlite3MemsysFailed();  /* A place to set a breakpoint */

   300         }

   301         mem.iFailCnt++;

   302         if( mem.iNextIsBenign || mem.iIsBenign ){

   303           mem.iBenignFailCnt++;

   304         }

   305       }else{

   306         p = malloc(totalSize);

   307         mem.iFail--;

   308       }

   309     }else{

   310       p = malloc(totalSize);

   311       if( p==0 ){

   312         sqlite3MemsysAlarm(nByte);

   313         p = malloc(totalSize);

   314       }

   315     }

   316     if( p ){

   317       z = p;

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

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

   320       pHdr->pNext = 0;

   321       pHdr->pPrev = mem.pLast;

   322       if( mem.pLast ){

   323         mem.pLast->pNext = pHdr;

   324       }else{

   325         mem.pFirst = pHdr;

   326       }

   327       mem.pLast = pHdr;

   328       pHdr->iForeGuard = FOREGUARD;

   329       pHdr->nBacktraceSlots = mem.nBacktrace;

   330       pHdr->nTitle = mem.nTitle;

   331       if( mem.nBacktrace ){

   332         void *aAddr[40];

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

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

   335       }else{

   336         pHdr->nBacktrace = 0;

   337       }

   338       if( mem.nTitle ){

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

   340       }

   341       pHdr->iSize = nByte;

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

   343       pInt[nByte/sizeof(int)] = REARGUARD;

   344       memset(pInt, 0x65, nByte);

   345       mem.nowUsed += nByte;

   346       if( mem.nowUsed>mem.mxUsed ){

   347         mem.mxUsed = mem.nowUsed;

   348       }

   349       p = (void*)pInt;

   350     }

   351     sqlite3_mutex_leave(mem.mutex);

   352   }

   353   mem.iNextIsBenign = 0;

   354   return p; 

   355 }

   356 

   357 /*

   358 ** Free memory.

   359 */

   360 void sqlite3_free(void *pPrior){

   361   struct MemBlockHdr *pHdr;

   362   void **pBt;

   363   char *z;

   364   if( pPrior==0 ){

   365     return;

   366   }

   367   assert( mem.mutex!=0 );

   368   pHdr = sqlite3MemsysGetHeader(pPrior);

   369   pBt = (void**)pHdr;

   370   pBt -= pHdr->nBacktraceSlots;

   371   sqlite3_mutex_enter(mem.mutex);

   372   mem.nowUsed -= pHdr->iSize;

   373   if( pHdr->pPrev ){

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

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

   376   }else{

   377     assert( mem.pFirst==pHdr );

   378     mem.pFirst = pHdr->pNext;

   379   }

   380   if( pHdr->pNext ){

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

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

   383   }else{

   384     assert( mem.pLast==pHdr );

   385     mem.pLast = pHdr->pPrev;

   386   }

   387   z = (char*)pBt;

   388   z -= pHdr->nTitle;

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

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

   391   free(z);

   392   sqlite3_mutex_leave(mem.mutex);  

   393 }

   394 

   395 /*

   396 ** Change the size of an existing memory allocation.

   397 **

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

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

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

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

   402 ** the error.

   403 */

   404 void *sqlite3_realloc(void *pPrior, int nByte){

   405   struct MemBlockHdr *pOldHdr;

   406   void *pNew;

   407   if( pPrior==0 ){

   408     return sqlite3_malloc(nByte);

   409   }

   410   if( nByte<=0 ){

   411     sqlite3_free(pPrior);

   412     return 0;

   413   }

   414   assert( mem.disallow==0 );

   415   pOldHdr = sqlite3MemsysGetHeader(pPrior);

   416   pNew = sqlite3_malloc(nByte);

   417   if( pNew ){

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

   419     if( nByte>pOldHdr->iSize ){

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

   421     }

   422     sqlite3_free(pPrior);

   423   }

   424   return pNew;

   425 }

   426 

   427 /*

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

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

   430 ** up to a multiple of 2.

   431 */

   432 void sqlite3_memdebug_backtrace(int depth){

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

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

   435   depth = (depth+1)&0xfe;

   436   mem.nBacktrace = depth;

   437 }

   438 

   439 /*

   440 ** Set the title string for subsequent allocations.

   441 */

   442 void sqlite3_memdebug_settitle(const char *zTitle){

   443   int n = strlen(zTitle) + 1;

   444   enterMem();

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

   446   memcpy(mem.zTitle, zTitle, n);

   447   mem.zTitle[n] = 0;

   448   mem.nTitle = (n+3)&~3;

   449   sqlite3_mutex_leave(mem.mutex);

   450 }

   451 

   452 /*

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

   454 ** allocations into that log.

   455 */

   456 void sqlite3_memdebug_dump(const char *zFilename){

   457   FILE *out;

   458   struct MemBlockHdr *pHdr;

   459   void **pBt;

   460   int i;

   461   out = fopen(zFilename, "w");

   462   if( out==0 ){

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

   464                     zFilename);

   465     return;

   466   }

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

   468     char *z = (char*)pHdr;

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

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

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

   472     if( pHdr->nBacktrace ){

   473       fflush(out);

   474       pBt = (void**)pHdr;

   475       pBt -= pHdr->nBacktraceSlots;

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

   477       fprintf(out, "\n");

   478     }

   479   }

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

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

   482     if( mem.sizeCnt[i] ){

   483       fprintf(out, "   %3d: %d\n", i*8+8, mem.sizeCnt[i]);

   484     }

   485   }

   486   if( mem.sizeCnt[NCSIZE-1] ){

   487     fprintf(out, "  >%3d: %d\n", NCSIZE*8, mem.sizeCnt[NCSIZE-1]);

   488   }

   489   fclose(out);

   490 }

   491 

   492 /*

   493 ** This routine is used to simulate malloc failures.

   494 **

   495 ** After calling this routine, there will be iFail successful

   496 ** memory allocations and then a failure.  If iRepeat is 1

   497 ** all subsequent memory allocations will fail.  If iRepeat is

   498 ** 0, only a single allocation will fail.  If iRepeat is negative

   499 ** then the previous setting for iRepeat is unchanged.

   500 **

   501 ** Each call to this routine overrides the previous.  To disable

   502 ** the simulated allocation failure mechanism, set iFail to -1.

   503 **

   504 ** This routine returns the number of simulated failures that have

   505 ** occurred since the previous call.

   506 */

   507 int sqlite3_memdebug_fail(int iFail, int iRepeat, int *piBenign){

   508   int n = mem.iFailCnt;

   509   if( piBenign ){

   510     *piBenign = mem.iBenignFailCnt;

   511   }

   512   mem.iFail = iFail+1;

   513   if( iRepeat>=0 ){

   514     mem.iReset = iRepeat;

   515   }

   516   mem.iFailCnt = 0;

   517   mem.iBenignFailCnt = 0;

   518   return n;

   519 }

   520 

   521 int sqlite3_memdebug_pending(){

   522   return (mem.iFail-1);

   523 }

   524 

   525 /*

   526 ** The following three functions are used to indicate to the test 

   527 ** infrastructure which malloc() calls may fail benignly without

   528 ** affecting functionality. This can happen when resizing hash tables 

   529 ** (failing to resize a hash-table is a performance hit, but not an 

   530 ** error) or sometimes during a rollback operation.

   531 **

   532 ** If the argument is true, sqlite3MallocBenignFailure() indicates that the

   533 ** next call to allocate memory may fail benignly.

   534 **

   535 ** If sqlite3MallocEnterBenignBlock() is called with a non-zero argument,

   536 ** then all memory allocations requested before the next call to

   537 ** sqlite3MallocLeaveBenignBlock() may fail benignly.

   538 */

   539 void sqlite3MallocBenignFailure(int isBenign){

   540   if( isBenign ){

   541     mem.iNextIsBenign = 1;

   542   }

   543 }

   544 void sqlite3MallocEnterBenignBlock(int isBenign){

   545   if( isBenign ){

   546     mem.iIsBenign = 1;

   547   }

   548 }

   549 void sqlite3MallocLeaveBenignBlock(){

   550   mem.iIsBenign = 0;

   551 }

   552 

   553 /*

   554 ** The following two routines are used to assert that no memory

   555 ** allocations occur between one call and the next.  The use of

   556 ** these routines does not change the computed results in any way.

   557 ** These routines are like asserts.

   558 */

   559 void sqlite3MallocDisallow(void){

   560   assert( mem.mutex!=0 );

   561   sqlite3_mutex_enter(mem.mutex);

   562   mem.disallow++;

   563   sqlite3_mutex_leave(mem.mutex);

   564 }

   565 void sqlite3MallocAllow(void){

   566   assert( mem.mutex );

   567   sqlite3_mutex_enter(mem.mutex);

   568   assert( mem.disallow>0 );

   569   mem.disallow--;

   570   sqlite3_mutex_leave(mem.mutex);

   571 }

   572 

   573 #endif /* SQLITE_MEMDEBUG && !SQLITE_OMIT_MEMORY_ALLOCATION */