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