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** 13** This file contains low-level memory allocation drivers for when 14** SQLite will use the standard C-library malloc/realloc/free interface 15** to obtain the memory it needs while adding lots of additional debugging 16** information to each allocation in order to help detect and fix memory 17** leaks and memory usage errors. 18** 19** This file contains implementations of the low-level memory allocation 20** routines specified in the sqlite3_mem_methods object. 21*/ 22#include "sqliteInt.h" 23 24/* 25** This version of the memory allocator is used only if the 26** SQLITE_MEMDEBUG macro is defined 27*/ 28#ifdef SQLITE_MEMDEBUG 29 30/* 31** The backtrace functionality is only available with GLIBC 32*/ 33#ifdef __GLIBC__ 34 extern int backtrace(void**,int); 35 extern void backtrace_symbols_fd(void*const*,int,int); 36#else 37# define backtrace(A,B) 1 38# define backtrace_symbols_fd(A,B,C) 39#endif 40#include <stdio.h> 41 42/* 43** Each memory allocation looks like this: 44** 45** ------------------------------------------------------------------------ 46** | Title | backtrace pointers | MemBlockHdr | allocation | EndGuard | 47** ------------------------------------------------------------------------ 48** 49** The application code sees only a pointer to the allocation. We have 50** to back up from the allocation pointer to find the MemBlockHdr. The 51** MemBlockHdr tells us the size of the allocation and the number of 52** backtrace pointers. There is also a guard word at the end of the 53** MemBlockHdr. 54*/ 55struct MemBlockHdr { 56 i64 iSize; /* Size of this allocation */ 57 struct MemBlockHdr *pNext, *pPrev; /* Linked list of all unfreed memory */ 58 char nBacktrace; /* Number of backtraces on this alloc */ 59 char nBacktraceSlots; /* Available backtrace slots */ 60 u8 nTitle; /* Bytes of title; includes '\0' */ 61 u8 eType; /* Allocation type code */ 62 int iForeGuard; /* Guard word for sanity */ 63}; 64 65/* 66** Guard words 67*/ 68#define FOREGUARD 0x80F5E153 69#define REARGUARD 0xE4676B53 70 71/* 72** Number of malloc size increments to track. 73*/ 74#define NCSIZE 1000 75 76/* 77** All of the static variables used by this module are collected 78** into a single structure named "mem". This is to keep the 79** static variables organized and to reduce namespace pollution 80** when this module is combined with other in the amalgamation. 81*/ 82static struct { 83 84 /* 85 ** Mutex to control access to the memory allocation subsystem. 86 */ 87 sqlite3_mutex *mutex; 88 89 /* 90 ** Head and tail of a linked list of all outstanding allocations 91 */ 92 struct MemBlockHdr *pFirst; 93 struct MemBlockHdr *pLast; 94 95 /* 96 ** The number of levels of backtrace to save in new allocations. 97 */ 98 int nBacktrace; 99 void (*xBacktrace)(int, int, void **); 100 101 /* 102 ** Title text to insert in front of each block 103 */ 104 int nTitle; /* Bytes of zTitle to save. Includes '\0' and padding */ 105 char zTitle[100]; /* The title text */ 106 107 /* 108 ** sqlite3MallocDisallow() increments the following counter. 109 ** sqlite3MallocAllow() decrements it. 110 */ 111 int disallow; /* Do not allow memory allocation */ 112 113 /* 114 ** Gather statistics on the sizes of memory allocations. 115 ** nAlloc[i] is the number of allocation attempts of i*8 116 ** bytes. i==NCSIZE is the number of allocation attempts for 117 ** sizes more than NCSIZE*8 bytes. 118 */ 119 int nAlloc[NCSIZE]; /* Total number of allocations */ 120 int nCurrent[NCSIZE]; /* Current number of allocations */ 121 int mxCurrent[NCSIZE]; /* Highwater mark for nCurrent */ 122 123} mem; 124 125 126/* 127** Adjust memory usage statistics 128*/ 129static void adjustStats(int iSize, int increment){ 130 int i = ROUND8(iSize)/8; 131 if( i>NCSIZE-1 ){ 132 i = NCSIZE - 1; 133 } 134 if( increment>0 ){ 135 mem.nAlloc[i]++; 136 mem.nCurrent[i]++; 137 if( mem.nCurrent[i]>mem.mxCurrent[i] ){ 138 mem.mxCurrent[i] = mem.nCurrent[i]; 139 } 140 }else{ 141 mem.nCurrent[i]--; 142 assert( mem.nCurrent[i]>=0 ); 143 } 144} 145 146/* 147** Given an allocation, find the MemBlockHdr for that allocation. 148** 149** This routine checks the guards at either end of the allocation and 150** if they are incorrect it asserts. 151*/ 152static struct MemBlockHdr *sqlite3MemsysGetHeader(void *pAllocation){ 153 struct MemBlockHdr *p; 154 int *pInt; 155 u8 *pU8; 156 int nReserve; 157 158 p = (struct MemBlockHdr*)pAllocation; 159 p--; 160 assert( p->iForeGuard==(int)FOREGUARD ); 161 nReserve = ROUND8(p->iSize); 162 pInt = (int*)pAllocation; 163 pU8 = (u8*)pAllocation; 164 assert( pInt[nReserve/sizeof(int)]==(int)REARGUARD ); 165 /* This checks any of the "extra" bytes allocated due 166 ** to rounding up to an 8 byte boundary to ensure 167 ** they haven't been overwritten. 168 */ 169 while( nReserve-- > p->iSize ) assert( pU8[nReserve]==0x65 ); 170 return p; 171} 172 173/* 174** Return the number of bytes currently allocated at address p. 175*/ 176static int sqlite3MemSize(void *p){ 177 struct MemBlockHdr *pHdr; 178 if( !p ){ 179 return 0; 180 } 181 pHdr = sqlite3MemsysGetHeader(p); 182 return pHdr->iSize; 183} 184 185/* 186** Initialize the memory allocation subsystem. 187*/ 188static int sqlite3MemInit(void *NotUsed){ 189 UNUSED_PARAMETER(NotUsed); 190 assert( (sizeof(struct MemBlockHdr)&7) == 0 ); 191 if( !sqlite3GlobalConfig.bMemstat ){ 192 /* If memory status is enabled, then the malloc.c wrapper will already 193 ** hold the STATIC_MEM mutex when the routines here are invoked. */ 194 mem.mutex = sqlite3MutexAlloc(SQLITE_MUTEX_STATIC_MEM); 195 } 196 return SQLITE_OK; 197} 198 199/* 200** Deinitialize the memory allocation subsystem. 201*/ 202static void sqlite3MemShutdown(void *NotUsed){ 203 UNUSED_PARAMETER(NotUsed); 204 mem.mutex = 0; 205} 206 207/* 208** Round up a request size to the next valid allocation size. 209*/ 210static int sqlite3MemRoundup(int n){ 211 return ROUND8(n); 212} 213 214/* 215** Fill a buffer with pseudo-random bytes. This is used to preset 216** the content of a new memory allocation to unpredictable values and 217** to clear the content of a freed allocation to unpredictable values. 218*/ 219static void randomFill(char *pBuf, int nByte){ 220 unsigned int x, y, r; 221 x = SQLITE_PTR_TO_INT(pBuf); 222 y = nByte | 1; 223 while( nByte >= 4 ){ 224 x = (x>>1) ^ (-(x&1) & 0xd0000001); 225 y = y*1103515245 + 12345; 226 r = x ^ y; 227 *(int*)pBuf = r; 228 pBuf += 4; 229 nByte -= 4; 230 } 231 while( nByte-- > 0 ){ 232 x = (x>>1) ^ (-(x&1) & 0xd0000001); 233 y = y*1103515245 + 12345; 234 r = x ^ y; 235 *(pBuf++) = r & 0xff; 236 } 237} 238 239/* 240** Allocate nByte bytes of memory. 241*/ 242static void *sqlite3MemMalloc(int nByte){ 243 struct MemBlockHdr *pHdr; 244 void **pBt; 245 char *z; 246 int *pInt; 247 void *p = 0; 248 int totalSize; 249 int nReserve; 250 sqlite3_mutex_enter(mem.mutex); 251 assert( mem.disallow==0 ); 252 nReserve = ROUND8(nByte); 253 totalSize = nReserve + sizeof(*pHdr) + sizeof(int) + 254 mem.nBacktrace*sizeof(void*) + mem.nTitle; 255 p = malloc(totalSize); 256 if( p ){ 257 z = p; 258 pBt = (void**)&z[mem.nTitle]; 259 pHdr = (struct MemBlockHdr*)&pBt[mem.nBacktrace]; 260 pHdr->pNext = 0; 261 pHdr->pPrev = mem.pLast; 262 if( mem.pLast ){ 263 mem.pLast->pNext = pHdr; 264 }else{ 265 mem.pFirst = pHdr; 266 } 267 mem.pLast = pHdr; 268 pHdr->iForeGuard = FOREGUARD; 269 pHdr->eType = MEMTYPE_HEAP; 270 pHdr->nBacktraceSlots = mem.nBacktrace; 271 pHdr->nTitle = mem.nTitle; 272 if( mem.nBacktrace ){ 273 void *aAddr[40]; 274 pHdr->nBacktrace = backtrace(aAddr, mem.nBacktrace+1)-1; 275 memcpy(pBt, &aAddr[1], pHdr->nBacktrace*sizeof(void*)); 276 assert(pBt[0]); 277 if( mem.xBacktrace ){ 278 mem.xBacktrace(nByte, pHdr->nBacktrace-1, &aAddr[1]); 279 } 280 }else{ 281 pHdr->nBacktrace = 0; 282 } 283 if( mem.nTitle ){ 284 memcpy(z, mem.zTitle, mem.nTitle); 285 } 286 pHdr->iSize = nByte; 287 adjustStats(nByte, +1); 288 pInt = (int*)&pHdr[1]; 289 pInt[nReserve/sizeof(int)] = REARGUARD; 290 randomFill((char*)pInt, nByte); 291 memset(((char*)pInt)+nByte, 0x65, nReserve-nByte); 292 p = (void*)pInt; 293 } 294 sqlite3_mutex_leave(mem.mutex); 295 return p; 296} 297 298/* 299** Free memory. 300*/ 301static void sqlite3MemFree(void *pPrior){ 302 struct MemBlockHdr *pHdr; 303 void **pBt; 304 char *z; 305 assert( sqlite3GlobalConfig.bMemstat || sqlite3GlobalConfig.bCoreMutex==0 306 || mem.mutex!=0 ); 307 pHdr = sqlite3MemsysGetHeader(pPrior); 308 pBt = (void**)pHdr; 309 pBt -= pHdr->nBacktraceSlots; 310 sqlite3_mutex_enter(mem.mutex); 311 if( pHdr->pPrev ){ 312 assert( pHdr->pPrev->pNext==pHdr ); 313 pHdr->pPrev->pNext = pHdr->pNext; 314 }else{ 315 assert( mem.pFirst==pHdr ); 316 mem.pFirst = pHdr->pNext; 317 } 318 if( pHdr->pNext ){ 319 assert( pHdr->pNext->pPrev==pHdr ); 320 pHdr->pNext->pPrev = pHdr->pPrev; 321 }else{ 322 assert( mem.pLast==pHdr ); 323 mem.pLast = pHdr->pPrev; 324 } 325 z = (char*)pBt; 326 z -= pHdr->nTitle; 327 adjustStats(pHdr->iSize, -1); 328 randomFill(z, sizeof(void*)*pHdr->nBacktraceSlots + sizeof(*pHdr) + 329 pHdr->iSize + sizeof(int) + pHdr->nTitle); 330 free(z); 331 sqlite3_mutex_leave(mem.mutex); 332} 333 334/* 335** Change the size of an existing memory allocation. 336** 337** For this debugging implementation, we *always* make a copy of the 338** allocation into a new place in memory. In this way, if the 339** higher level code is using pointer to the old allocation, it is 340** much more likely to break and we are much more liking to find 341** the error. 342*/ 343static void *sqlite3MemRealloc(void *pPrior, int nByte){ 344 struct MemBlockHdr *pOldHdr; 345 void *pNew; 346 assert( mem.disallow==0 ); 347 assert( (nByte & 7)==0 ); /* EV: R-46199-30249 */ 348 pOldHdr = sqlite3MemsysGetHeader(pPrior); 349 pNew = sqlite3MemMalloc(nByte); 350 if( pNew ){ 351 memcpy(pNew, pPrior, nByte<pOldHdr->iSize ? nByte : pOldHdr->iSize); 352 if( nByte>pOldHdr->iSize ){ 353 randomFill(&((char*)pNew)[pOldHdr->iSize], nByte - pOldHdr->iSize); 354 } 355 sqlite3MemFree(pPrior); 356 } 357 return pNew; 358} 359 360/* 361** Populate the low-level memory allocation function pointers in 362** sqlite3GlobalConfig.m with pointers to the routines in this file. 363*/ 364void sqlite3MemSetDefault(void){ 365 static const sqlite3_mem_methods defaultMethods = { 366 sqlite3MemMalloc, 367 sqlite3MemFree, 368 sqlite3MemRealloc, 369 sqlite3MemSize, 370 sqlite3MemRoundup, 371 sqlite3MemInit, 372 sqlite3MemShutdown, 373 0 374 }; 375 sqlite3_config(SQLITE_CONFIG_MALLOC, &defaultMethods); 376} 377 378/* 379** Set the "type" of an allocation. 380*/ 381void sqlite3MemdebugSetType(void *p, u8 eType){ 382 if( p && sqlite3GlobalConfig.m.xMalloc==sqlite3MemMalloc ){ 383 struct MemBlockHdr *pHdr; 384 pHdr = sqlite3MemsysGetHeader(p); 385 assert( pHdr->iForeGuard==FOREGUARD ); 386 pHdr->eType = eType; 387 } 388} 389 390/* 391** Return TRUE if the mask of type in eType matches the type of the 392** allocation p. Also return true if p==NULL. 393** 394** This routine is designed for use within an assert() statement, to 395** verify the type of an allocation. For example: 396** 397** assert( sqlite3MemdebugHasType(p, MEMTYPE_DB) ); 398*/ 399int sqlite3MemdebugHasType(void *p, u8 eType){ 400 int rc = 1; 401 if( p && sqlite3GlobalConfig.m.xMalloc==sqlite3MemMalloc ){ 402 struct MemBlockHdr *pHdr; 403 pHdr = sqlite3MemsysGetHeader(p); 404 assert( pHdr->iForeGuard==FOREGUARD ); /* Allocation is valid */ 405 if( (pHdr->eType&eType)==0 ){ 406 rc = 0; 407 } 408 } 409 return rc; 410} 411 412/* 413** Return TRUE if the mask of type in eType matches no bits of the type of the 414** allocation p. Also return true if p==NULL. 415** 416** This routine is designed for use within an assert() statement, to 417** verify the type of an allocation. For example: 418** 419** assert( sqlite3MemdebugNoType(p, MEMTYPE_DB) ); 420*/ 421int sqlite3MemdebugNoType(void *p, u8 eType){ 422 int rc = 1; 423 if( p && sqlite3GlobalConfig.m.xMalloc==sqlite3MemMalloc ){ 424 struct MemBlockHdr *pHdr; 425 pHdr = sqlite3MemsysGetHeader(p); 426 assert( pHdr->iForeGuard==FOREGUARD ); /* Allocation is valid */ 427 if( (pHdr->eType&eType)!=0 ){ 428 rc = 0; 429 } 430 } 431 return rc; 432} 433 434/* 435** Set the number of backtrace levels kept for each allocation. 436** A value of zero turns off backtracing. The number is always rounded 437** up to a multiple of 2. 438*/ 439void sqlite3MemdebugBacktrace(int depth){ 440 if( depth<0 ){ depth = 0; } 441 if( depth>20 ){ depth = 20; } 442 depth = (depth+1)&0xfe; 443 mem.nBacktrace = depth; 444} 445 446void sqlite3MemdebugBacktraceCallback(void (*xBacktrace)(int, int, void **)){ 447 mem.xBacktrace = xBacktrace; 448} 449 450/* 451** Set the title string for subsequent allocations. 452*/ 453void sqlite3MemdebugSettitle(const char *zTitle){ 454 unsigned int n = sqlite3Strlen30(zTitle) + 1; 455 sqlite3_mutex_enter(mem.mutex); 456 if( n>=sizeof(mem.zTitle) ) n = sizeof(mem.zTitle)-1; 457 memcpy(mem.zTitle, zTitle, n); 458 mem.zTitle[n] = 0; 459 mem.nTitle = ROUND8(n); 460 sqlite3_mutex_leave(mem.mutex); 461} 462 463void sqlite3MemdebugSync(){ 464 struct MemBlockHdr *pHdr; 465 for(pHdr=mem.pFirst; pHdr; pHdr=pHdr->pNext){ 466 void **pBt = (void**)pHdr; 467 pBt -= pHdr->nBacktraceSlots; 468 mem.xBacktrace(pHdr->iSize, pHdr->nBacktrace-1, &pBt[1]); 469 } 470} 471 472/* 473** Open the file indicated and write a log of all unfreed memory 474** allocations into that log. 475*/ 476void sqlite3MemdebugDump(const char *zFilename){ 477 FILE *out; 478 struct MemBlockHdr *pHdr; 479 void **pBt; 480 int i; 481 out = fopen(zFilename, "w"); 482 if( out==0 ){ 483 fprintf(stderr, "** Unable to output memory debug output log: %s **\n", 484 zFilename); 485 return; 486 } 487 for(pHdr=mem.pFirst; pHdr; pHdr=pHdr->pNext){ 488 char *z = (char*)pHdr; 489 z -= pHdr->nBacktraceSlots*sizeof(void*) + pHdr->nTitle; 490 fprintf(out, "**** %lld bytes at %p from %s ****\n", 491 pHdr->iSize, &pHdr[1], pHdr->nTitle ? z : "???"); 492 if( pHdr->nBacktrace ){ 493 fflush(out); 494 pBt = (void**)pHdr; 495 pBt -= pHdr->nBacktraceSlots; 496 backtrace_symbols_fd(pBt, pHdr->nBacktrace, fileno(out)); 497 fprintf(out, "\n"); 498 } 499 } 500 fprintf(out, "COUNTS:\n"); 501 for(i=0; i<NCSIZE-1; i++){ 502 if( mem.nAlloc[i] ){ 503 fprintf(out, " %5d: %10d %10d %10d\n", 504 i*8, mem.nAlloc[i], mem.nCurrent[i], mem.mxCurrent[i]); 505 } 506 } 507 if( mem.nAlloc[NCSIZE-1] ){ 508 fprintf(out, " %5d: %10d %10d %10d\n", 509 NCSIZE*8-8, mem.nAlloc[NCSIZE-1], 510 mem.nCurrent[NCSIZE-1], mem.mxCurrent[NCSIZE-1]); 511 } 512 fclose(out); 513} 514 515/* 516** Return the number of times sqlite3MemMalloc() has been called. 517*/ 518int sqlite3MemdebugMallocCount(){ 519 int i; 520 int nTotal = 0; 521 for(i=0; i<NCSIZE; i++){ 522 nTotal += mem.nAlloc[i]; 523 } 524 return nTotal; 525} 526 527 528#endif /* SQLITE_MEMDEBUG */ 529