/*

** 2007 August 15

**

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

** a legal notice, here is a blessing:

**

** May you do good and not evil.

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

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

**

*************************************************************************

**

** This file contains low-level memory allocation drivers for when

** SQLite will use the standard C-library malloc/realloc/free interface

** to obtain the memory it needs while adding lots of additional debugging

** information to each allocation in order to help detect and fix memory

** leaks and memory usage errors.

**

** This file contains implementations of the low-level memory allocation

** routines specified in the sqlite3_mem_methods object.

*/

#include "sqliteInt.h"

/*

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

** SQLITE_MEMDEBUG macro is defined

*/

#ifdef SQLITE_MEMDEBUG

/*

** The backtrace functionality is only available with GLIBC

*/

#ifdef __GLIBC__

extern int backtrace(void**,int);

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

#else

# define backtrace(A,B) 1

# define backtrace_symbols_fd(A,B,C)

#endif

#include <stdio.h>

/*

** Each memory allocation looks like this:

**

** ------------------------------------------------------------------------

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

** ------------------------------------------------------------------------

**

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

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

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

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

** MemBlockHdr.

*/

struct MemBlockHdr {

i64 iSize; /* Size of this allocation */

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

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

char nBacktraceSlots; /* Available backtrace slots */

u8 nTitle; /* Bytes of title; includes '\0' */

u8 eType; /* Allocation type code */

int iForeGuard; /* Guard word for sanity */

};

/*

** Guard words

*/

#define FOREGUARD 0x80F5E153

#define REARGUARD 0xE4676B53

/*

** Number of malloc size increments to track.

*/

#define NCSIZE 1000

/*

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

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

** static variables organized and to reduce namespace pollution

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

*/

static struct {

/*

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

*/

sqlite3_mutex *mutex;

/*

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

*/

struct MemBlockHdr *pFirst;

struct MemBlockHdr *pLast;

/*

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

*/

int nBacktrace;

void (*xBacktrace)(int, int, void **);

/*

** Title text to insert in front of each block

*/

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

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

/*

** sqlite3MallocDisallow() increments the following counter.

** sqlite3MallocAllow() decrements it.

*/

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

/*

** Gather statistics on the sizes of memory allocations.

** nAlloc[i] is the number of allocation attempts of i*8

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

** sizes more than NCSIZE*8 bytes.

*/

int nAlloc[NCSIZE]; /* Total number of allocations */

int nCurrent[NCSIZE]; /* Current number of allocations */

int mxCurrent[NCSIZE]; /* Highwater mark for nCurrent */

} mem;

/*

** Adjust memory usage statistics

*/

static void adjustStats(int iSize, int increment){

int i = ROUND8(iSize)/8;

if( i>NCSIZE-1 ){

i = NCSIZE - 1;

}

if( increment>0 ){

mem.nAlloc[i]++;

mem.nCurrent[i]++;

if( mem.nCurrent[i]>mem.mxCurrent[i] ){

mem.mxCurrent[i] = mem.nCurrent[i];

}

}else{

mem.nCurrent[i]--;

assert( mem.nCurrent[i]>=0 );

}

}

/*

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

**

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

** if they are incorrect it asserts.

*/

static struct MemBlockHdr *sqlite3MemsysGetHeader(void *pAllocation){

struct MemBlockHdr *p;

int *pInt;

u8 *pU8;

int nReserve;

p = (struct MemBlockHdr*)pAllocation;

p--;

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

nReserve = ROUND8(p->iSize);

pInt = (int*)pAllocation;

pU8 = (u8*)pAllocation;

assert( pInt[nReserve/sizeof(int)]==(int)REARGUARD );

/* This checks any of the "extra" bytes allocated due

** to rounding up to an 8 byte boundary to ensure

** they haven't been overwritten.

*/

while( nReserve-- > p->iSize ) assert( pU8[nReserve]==0x65 );

return p;

}

/*

** Return the number of bytes currently allocated at address p.

*/

static int sqlite3MemSize(void *p){

struct MemBlockHdr *pHdr;

if( !p ){

return 0;

}

pHdr = sqlite3MemsysGetHeader(p);

return (int)pHdr->iSize;

}

/*

** Initialize the memory allocation subsystem.

*/

static int sqlite3MemInit(void *NotUsed){

UNUSED_PARAMETER(NotUsed);

assert( (sizeof(struct MemBlockHdr)&7) == 0 );

if( !sqlite3GlobalConfig.bMemstat ){

/* If memory status is enabled, then the malloc.c wrapper will already

** hold the STATIC_MEM mutex when the routines here are invoked. */

mem.mutex = sqlite3MutexAlloc(SQLITE_MUTEX_STATIC_MEM);

}

return SQLITE_OK;

}

/*

** Deinitialize the memory allocation subsystem.

*/

static void sqlite3MemShutdown(void *NotUsed){

UNUSED_PARAMETER(NotUsed);

mem.mutex = 0;

}

/*

** Round up a request size to the next valid allocation size.

*/

static int sqlite3MemRoundup(int n){

return ROUND8(n);

}

/*

** Fill a buffer with pseudo-random bytes. This is used to preset

** the content of a new memory allocation to unpredictable values and

** to clear the content of a freed allocation to unpredictable values.

*/

static void randomFill(char *pBuf, int nByte){

unsigned int x, y, r;

x = SQLITE_PTR_TO_INT(pBuf);

y = nByte | 1;

while( nByte >= 4 ){

x = (x>>1) ^ (-(int)(x&1) & 0xd0000001);

y = y*1103515245 + 12345;

r = x ^ y;

*(int*)pBuf = r;

pBuf += 4;

nByte -= 4;

}

while( nByte-- > 0 ){

x = (x>>1) ^ (-(int)(x&1) & 0xd0000001);

y = y*1103515245 + 12345;

r = x ^ y;

*(pBuf++) = r & 0xff;

}

}

/*

** Allocate nByte bytes of memory.

*/

static void *sqlite3MemMalloc(int nByte){

struct MemBlockHdr *pHdr;

void **pBt;

char *z;

int *pInt;

void *p = 0;

int totalSize;

int nReserve;

sqlite3_mutex_enter(mem.mutex);

assert( mem.disallow==0 );

nReserve = ROUND8(nByte);

totalSize = nReserve + sizeof(*pHdr) + sizeof(int) +

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

p = malloc(totalSize);

if( p ){

z = p;

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

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

pHdr->pNext = 0;

pHdr->pPrev = mem.pLast;

if( mem.pLast ){

mem.pLast->pNext = pHdr;

}else{

mem.pFirst = pHdr;

}

mem.pLast = pHdr;

pHdr->iForeGuard = FOREGUARD;

pHdr->eType = MEMTYPE_HEAP;

pHdr->nBacktraceSlots = mem.nBacktrace;

pHdr->nTitle = mem.nTitle;

if( mem.nBacktrace ){

void *aAddr[40];

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

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

assert(pBt[0]);

if( mem.xBacktrace ){

mem.xBacktrace(nByte, pHdr->nBacktrace-1, &aAddr[1]);

}

}else{

pHdr->nBacktrace = 0;

}

if( mem.nTitle ){

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

}

pHdr->iSize = nByte;

adjustStats(nByte, +1);

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

pInt[nReserve/sizeof(int)] = REARGUARD;

randomFill((char*)pInt, nByte);

memset(((char*)pInt)+nByte, 0x65, nReserve-nByte);

p = (void*)pInt;

}

sqlite3_mutex_leave(mem.mutex);

return p;

}

/*

** Free memory.

*/

static void sqlite3MemFree(void *pPrior){

struct MemBlockHdr *pHdr;

void **pBt;

char *z;

assert( sqlite3GlobalConfig.bMemstat || sqlite3GlobalConfig.bCoreMutex==0

|| mem.mutex!=0 );

pHdr = sqlite3MemsysGetHeader(pPrior);

pBt = (void**)pHdr;

pBt -= pHdr->nBacktraceSlots;

sqlite3_mutex_enter(mem.mutex);

if( pHdr->pPrev ){

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

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

}else{

assert( mem.pFirst==pHdr );

mem.pFirst = pHdr->pNext;

}

if( pHdr->pNext ){

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

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

}else{

assert( mem.pLast==pHdr );

mem.pLast = pHdr->pPrev;

}

z = (char*)pBt;

z -= pHdr->nTitle;

adjustStats((int)pHdr->iSize, -1);

randomFill(z, sizeof(void*)*pHdr->nBacktraceSlots + sizeof(*pHdr) +

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

free(z);

sqlite3_mutex_leave(mem.mutex);

}

/*

** Change the size of an existing memory allocation.

**

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

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

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

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

** the error.

*/

static void *sqlite3MemRealloc(void *pPrior, int nByte){

struct MemBlockHdr *pOldHdr;

void *pNew;

assert( mem.disallow==0 );

assert( (nByte & 7)==0 ); /* EV: R-46199-30249 */

pOldHdr = sqlite3MemsysGetHeader(pPrior);

pNew = sqlite3MemMalloc(nByte);

if( pNew ){

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

if( nByte>pOldHdr->iSize ){

randomFill(&((char*)pNew)[pOldHdr->iSize], nByte - (int)pOldHdr->iSize);

}

sqlite3MemFree(pPrior);

}

return pNew;

}

/*

** Populate the low-level memory allocation function pointers in

** sqlite3GlobalConfig.m with pointers to the routines in this file.

*/

void sqlite3MemSetDefault(void){

static const sqlite3_mem_methods defaultMethods = {

sqlite3MemMalloc,

sqlite3MemFree,

sqlite3MemRealloc,

sqlite3MemSize,

sqlite3MemRoundup,

sqlite3MemInit,

sqlite3MemShutdown,

0

};

sqlite3_config(SQLITE_CONFIG_MALLOC, &defaultMethods);

}

/*

** Set the "type" of an allocation.

*/

void sqlite3MemdebugSetType(void *p, u8 eType){

if( p && sqlite3GlobalConfig.m.xMalloc==sqlite3MemMalloc ){

struct MemBlockHdr *pHdr;

pHdr = sqlite3MemsysGetHeader(p);

assert( pHdr->iForeGuard==FOREGUARD );

pHdr->eType = eType;

}

}

/*

** Return TRUE if the mask of type in eType matches the type of the

** allocation p. Also return true if p==NULL.

**

** This routine is designed for use within an assert() statement, to

** verify the type of an allocation. For example:

**

** assert( sqlite3MemdebugHasType(p, MEMTYPE_HEAP) );

*/

int sqlite3MemdebugHasType(void *p, u8 eType){

int rc = 1;

if( p && sqlite3GlobalConfig.m.xMalloc==sqlite3MemMalloc ){

struct MemBlockHdr *pHdr;

pHdr = sqlite3MemsysGetHeader(p);

assert( pHdr->iForeGuard==FOREGUARD ); /* Allocation is valid */

if( (pHdr->eType&eType)==0 ){

rc = 0;

}

}

return rc;

}

/*

** Return TRUE if the mask of type in eType matches no bits of the type of the

** allocation p. Also return true if p==NULL.

**

** This routine is designed for use within an assert() statement, to

** verify the type of an allocation. For example:

**

** assert( sqlite3MemdebugNoType(p, MEMTYPE_LOOKASIDE) );

*/

int sqlite3MemdebugNoType(void *p, u8 eType){

int rc = 1;

if( p && sqlite3GlobalConfig.m.xMalloc==sqlite3MemMalloc ){

struct MemBlockHdr *pHdr;

pHdr = sqlite3MemsysGetHeader(p);

assert( pHdr->iForeGuard==FOREGUARD ); /* Allocation is valid */

if( (pHdr->eType&eType)!=0 ){

rc = 0;

}

}

return rc;

}

/*

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

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

** up to a multiple of 2.

*/

void sqlite3MemdebugBacktrace(int depth){

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

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

depth = (depth+1)&0xfe;

mem.nBacktrace = depth;

}

void sqlite3MemdebugBacktraceCallback(void (*xBacktrace)(int, int, void **)){

mem.xBacktrace = xBacktrace;

}

/*

** Set the title string for subsequent allocations.

*/

void sqlite3MemdebugSettitle(const char *zTitle){

unsigned int n = sqlite3Strlen30(zTitle) + 1;

sqlite3_mutex_enter(mem.mutex);

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

memcpy(mem.zTitle, zTitle, n);

mem.zTitle[n] = 0;

mem.nTitle = ROUND8(n);

sqlite3_mutex_leave(mem.mutex);

}

void sqlite3MemdebugSync(){

struct MemBlockHdr *pHdr;

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

void **pBt = (void**)pHdr;

pBt -= pHdr->nBacktraceSlots;

mem.xBacktrace((int)pHdr->iSize, pHdr->nBacktrace-1, &pBt[1]);

}

}

/*

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

** allocations into that log.

*/

void sqlite3MemdebugDump(const char *zFilename){

FILE *out;

struct MemBlockHdr *pHdr;

void **pBt;

int i;

out = fopen(zFilename, "w");

if( out==0 ){

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

zFilename);

return;

}

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

char *z = (char*)pHdr;

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

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

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

if( pHdr->nBacktrace ){

fflush(out);

pBt = (void**)pHdr;

pBt -= pHdr->nBacktraceSlots;

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

fprintf(out, "\n");

}

}

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

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

if( mem.nAlloc[i] ){

fprintf(out, " %5d: %10d %10d %10d\n",

i*8, mem.nAlloc[i], mem.nCurrent[i], mem.mxCurrent[i]);

}

}

if( mem.nAlloc[NCSIZE-1] ){

fprintf(out, " %5d: %10d %10d %10d\n",

NCSIZE*8-8, mem.nAlloc[NCSIZE-1],

mem.nCurrent[NCSIZE-1], mem.mxCurrent[NCSIZE-1]);

}

fclose(out);

}

/*

** Return the number of times sqlite3MemMalloc() has been called.

*/

int sqlite3MemdebugMallocCount(){

int i;

int nTotal = 0;

for(i=0; i<NCSIZE; i++){

nTotal += mem.nAlloc[i];

}

return nTotal;

}

#endif /* SQLITE_MEMDEBUG */