Merge Chromium + Blink git repositories
[chromium-blink-merge.git] / third_party / sqlite / sqlite-src-3080704 / src / mem2.c
blob51ea297c6a1af6e1f6bdc3c1087ea270b2c2d5d7
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.
11 *************************************************************************
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.
19 ** This file contains implementations of the low-level memory allocation
20 ** routines specified in the sqlite3_mem_methods object.
22 #include "sqliteInt.h"
25 ** This version of the memory allocator is used only if the
26 ** SQLITE_MEMDEBUG macro is defined
28 #ifdef SQLITE_MEMDEBUG
31 ** The backtrace functionality is only available with GLIBC
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>
43 ** Each memory allocation looks like this:
45 ** ------------------------------------------------------------------------
46 ** | Title | backtrace pointers | MemBlockHdr | allocation | EndGuard |
47 ** ------------------------------------------------------------------------
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.
55 struct 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 */
66 ** Guard words
68 #define FOREGUARD 0x80F5E153
69 #define REARGUARD 0xE4676B53
72 ** Number of malloc size increments to track.
74 #define NCSIZE 1000
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.
82 static struct {
85 ** Mutex to control access to the memory allocation subsystem.
87 sqlite3_mutex *mutex;
90 ** Head and tail of a linked list of all outstanding allocations
92 struct MemBlockHdr *pFirst;
93 struct MemBlockHdr *pLast;
96 ** The number of levels of backtrace to save in new allocations.
98 int nBacktrace;
99 void (*xBacktrace)(int, int, void **);
102 ** Title text to insert in front of each block
104 int nTitle; /* Bytes of zTitle to save. Includes '\0' and padding */
105 char zTitle[100]; /* The title text */
108 ** sqlite3MallocDisallow() increments the following counter.
109 ** sqlite3MallocAllow() decrements it.
111 int disallow; /* Do not allow memory allocation */
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.
119 int nAlloc[NCSIZE]; /* Total number of allocations */
120 int nCurrent[NCSIZE]; /* Current number of allocations */
121 int mxCurrent[NCSIZE]; /* Highwater mark for nCurrent */
123 } mem;
127 ** Adjust memory usage statistics
129 static void adjustStats(int iSize, int increment){
130 int i = ROUND8(iSize)/8;
131 if( i>NCSIZE-1 ){
132 i = NCSIZE - 1;
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];
140 }else{
141 mem.nCurrent[i]--;
142 assert( mem.nCurrent[i]>=0 );
147 ** Given an allocation, find the MemBlockHdr for that allocation.
149 ** This routine checks the guards at either end of the allocation and
150 ** if they are incorrect it asserts.
152 static struct MemBlockHdr *sqlite3MemsysGetHeader(void *pAllocation){
153 struct MemBlockHdr *p;
154 int *pInt;
155 u8 *pU8;
156 int nReserve;
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.
169 while( nReserve-- > p->iSize ) assert( pU8[nReserve]==0x65 );
170 return p;
174 ** Return the number of bytes currently allocated at address p.
176 static int sqlite3MemSize(void *p){
177 struct MemBlockHdr *pHdr;
178 if( !p ){
179 return 0;
181 pHdr = sqlite3MemsysGetHeader(p);
182 return (int)pHdr->iSize;
186 ** Initialize the memory allocation subsystem.
188 static 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);
196 return SQLITE_OK;
200 ** Deinitialize the memory allocation subsystem.
202 static void sqlite3MemShutdown(void *NotUsed){
203 UNUSED_PARAMETER(NotUsed);
204 mem.mutex = 0;
208 ** Round up a request size to the next valid allocation size.
210 static int sqlite3MemRoundup(int n){
211 return ROUND8(n);
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.
219 static 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) ^ (-(int)(x&1) & 0xd0000001);
225 y = y*1103515245 + 12345;
226 r = x ^ y;
227 *(int*)pBuf = r;
228 pBuf += 4;
229 nByte -= 4;
231 while( nByte-- > 0 ){
232 x = (x>>1) ^ (-(int)(x&1) & 0xd0000001);
233 y = y*1103515245 + 12345;
234 r = x ^ y;
235 *(pBuf++) = r & 0xff;
240 ** Allocate nByte bytes of memory.
242 static 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;
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]);
280 }else{
281 pHdr->nBacktrace = 0;
283 if( mem.nTitle ){
284 memcpy(z, mem.zTitle, mem.nTitle);
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;
294 sqlite3_mutex_leave(mem.mutex);
295 return p;
299 ** Free memory.
301 static 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;
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;
325 z = (char*)pBt;
326 z -= pHdr->nTitle;
327 adjustStats((int)pHdr->iSize, -1);
328 randomFill(z, sizeof(void*)*pHdr->nBacktraceSlots + sizeof(*pHdr) +
329 (int)pHdr->iSize + sizeof(int) + pHdr->nTitle);
330 free(z);
331 sqlite3_mutex_leave(mem.mutex);
335 ** Change the size of an existing memory allocation.
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.
343 static 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, (int)(nByte<pOldHdr->iSize ? nByte : pOldHdr->iSize));
352 if( nByte>pOldHdr->iSize ){
353 randomFill(&((char*)pNew)[pOldHdr->iSize], nByte - (int)pOldHdr->iSize);
355 sqlite3MemFree(pPrior);
357 return pNew;
361 ** Populate the low-level memory allocation function pointers in
362 ** sqlite3GlobalConfig.m with pointers to the routines in this file.
364 void sqlite3MemSetDefault(void){
365 static const sqlite3_mem_methods defaultMethods = {
366 sqlite3MemMalloc,
367 sqlite3MemFree,
368 sqlite3MemRealloc,
369 sqlite3MemSize,
370 sqlite3MemRoundup,
371 sqlite3MemInit,
372 sqlite3MemShutdown,
375 sqlite3_config(SQLITE_CONFIG_MALLOC, &defaultMethods);
379 ** Set the "type" of an allocation.
381 void 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;
391 ** Return TRUE if the mask of type in eType matches the type of the
392 ** allocation p. Also return true if p==NULL.
394 ** This routine is designed for use within an assert() statement, to
395 ** verify the type of an allocation. For example:
397 ** assert( sqlite3MemdebugHasType(p, MEMTYPE_HEAP) );
399 int 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;
409 return rc;
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.
416 ** This routine is designed for use within an assert() statement, to
417 ** verify the type of an allocation. For example:
419 ** assert( sqlite3MemdebugNoType(p, MEMTYPE_LOOKASIDE) );
421 int 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;
431 return rc;
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.
439 void sqlite3MemdebugBacktrace(int depth){
440 if( depth<0 ){ depth = 0; }
441 if( depth>20 ){ depth = 20; }
442 depth = (depth+1)&0xfe;
443 mem.nBacktrace = depth;
446 void sqlite3MemdebugBacktraceCallback(void (*xBacktrace)(int, int, void **)){
447 mem.xBacktrace = xBacktrace;
451 ** Set the title string for subsequent allocations.
453 void 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);
463 void 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((int)pHdr->iSize, pHdr->nBacktrace-1, &pBt[1]);
473 ** Open the file indicated and write a log of all unfreed memory
474 ** allocations into that log.
476 void 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;
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");
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]);
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]);
512 fclose(out);
516 ** Return the number of times sqlite3MemMalloc() has been called.
518 int sqlite3MemdebugMallocCount(){
519 int i;
520 int nTotal = 0;
521 for(i=0; i<NCSIZE; i++){
522 nTotal += mem.nAlloc[i];
524 return nTotal;
528 #endif /* SQLITE_MEMDEBUG */