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(const 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.xFree==sqlite3MemFree ){
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(const void *p, u8 eType){
000400 int rc = 1;
000401 if( p && sqlite3GlobalConfig.m.xFree==sqlite3MemFree ){
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(const void *p, u8 eType){
000422 int rc = 1;
000423 if( p && sqlite3GlobalConfig.m.xFree==sqlite3MemFree ){
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 */