SQLite

**
*************************************************************************
** Main file for the SQLite library.  The routines in this file
** implement the programmer interface to the library.  Routines in
** other files are for internal use by SQLite and should not be
** accessed by users of the library.
**
** $Id: main.c,v 1.466 2008/06/27 13:27:04 danielk1977 Exp $
*/
#include "sqliteInt.h"
#include <ctype.h>

#ifdef SQLITE_ENABLE_FTS3
# include "fts3.h"
#endif

    }
    case SQLITE_CONFIG_SERIALIZED: {
      /* Enable all mutexing */
      sqlite3Config.bCoreMutex = 1;
      sqlite3Config.bFullMutex = 1;
      break;
    }
















    case SQLITE_CONFIG_MALLOC: {
      /* Specify an alternative malloc implementation */
      sqlite3Config.m = *va_arg(ap, sqlite3_mem_methods*);
      break;
    }
    case SQLITE_CONFIG_GETMALLOC: {
      /* Retrieve the current malloc() implementation */

    case SQLITE_CONFIG_PAGECACHE: {
      /* Designate a buffer for scratch memory space */
      sqlite3Config.pPage = va_arg(ap, void*);
      sqlite3Config.szPage = va_arg(ap, int);
      sqlite3Config.nPage = va_arg(ap, int);
      break;
    }

    case SQLITE_CONFIG_HEAP: {
      /* Designate a buffer for heap memory space */
      sqlite3Config.pHeap = va_arg(ap, void*);
      sqlite3Config.nHeap = va_arg(ap, int);
      sqlite3Config.mnReq = va_arg(ap, int);

      /* Fall through to install the mem5.c/mem3.c methods. If neither
      ** ENABLE_MEMSYS3 nor ENABLE_MEMSYS5 is defined, fall through to
      ** the default case and return an error.
      */
    }

#ifdef SQLITE_ENABLE_MEMSYS5
    case SQLITE_CONFIG_MEMSYS5: {
      sqlite3_mem_methods *p = sqlite3MemGetMemsys5();
      sqlite3Config.m = *p;
      break;
    }
#endif
#ifdef SQLITE_ENABLE_MEMSYS3
    case SQLITE_CONFIG_MEMSYS3: {
      sqlite3_mem_methods *p = sqlite3MemGetMemsys3();
      sqlite3Config.m = *p;
      break;
    }
#endif

    default: {
      rc = SQLITE_ERROR;
      break;
    }
  }
  va_end(ap);
  return rc;

** implementations. Once sqlite3_initialize() has been called,
** the amount of memory available to SQLite is fixed and cannot
** be changed.
**
** This version of the memory allocation subsystem is included
** in the build only if SQLITE_ENABLE_MEMSYS5 is defined.
**
** $Id: mem5.c,v 1.9 2008/06/27 13:27:04 danielk1977 Exp $
*/
#include "sqliteInt.h"

/*
** This version of the memory allocator is used only when 
** SQLITE_POW2_MEMORY_SIZE is defined.
*/
#ifdef SQLITE_ENABLE_MEMSYS5

/*
** Log2 of the minimum size of an allocation.  For example, if
** 4 then all allocations will be rounded up to at least 16 bytes.
** If 5 then all allocations will be rounded up to at least 32 bytes.
*/
#ifndef SQLITE_POW2_LOGMIN
# define SQLITE_POW2_LOGMIN 6
#endif


/*
** Log2 of the maximum size of an allocation.
*/
#ifndef SQLITE_POW2_LOGMAX
# define SQLITE_POW2_LOGMAX 18
#endif
#define POW2_MAX (((unsigned int)1)<<SQLITE_POW2_LOGMAX)

/*
** Number of distinct allocation sizes.
*/
#define NSIZE (SQLITE_POW2_LOGMAX - SQLITE_POW2_LOGMIN + 1)

/*
** A minimum allocation is an instance of the following structure.
** Larger allocations are an array of these structures where the
** size of the array is a power of 2.
*/
typedef struct Mem5Link Mem5Link;
struct Mem5Link {



  int next;       /* Index of next free chunk */
  int prev;       /* Index of previous free chunk */


};

/*
** Maximum size of any allocation is ((1<<LOGMAX)*mem5.nAtom). Since
** mem5.nAtom is always at least 8, this is not really a practical
** limitation.
*/
#define LOGMAX 30

/*
** Masks used for mem5.aCtrl[] elements.
*/
#define CTRL_LOGSIZE  0x1f    /* Log2 Size of this block relative to POW2_MIN */
#define CTRL_FREE     0x20    /* True if not checked out */

  u32 maxOut;         /* Maximum instantaneous currentOut */
  u32 maxCount;       /* Maximum instantaneous currentCount */
  u32 maxRequest;     /* Largest allocation (exclusive of internal frag) */
  
  /*
  ** Lists of free blocks of various sizes.
  */
  int aiFreelist[LOGMAX+1];

  /*
  ** Space for tracking which blocks are checked out and the size
  ** of each block.  One byte per block.
  */
  u8 *aCtrl;

  /*
  ** Memory available for allocation
  */
  int nAtom;       /* Smallest possible allocation in bytes */
  int nBlock;      /* Number of nAtom sized blocks in zPool */
  u8 *zPool;
} mem5;

#define MEM5LINK(idx) ((Mem5Link *)(&mem5.zPool[(idx)*mem5.nAtom]))

/*
** Unlink the chunk at mem5.aPool[i] from list it is currently
** on.  It should be found on mem5.aiFreelist[iLogsize].
*/
static void memsys5Unlink(int i, int iLogsize){
  int next, prev;
  assert( i>=0 && i<mem5.nBlock );
  assert( iLogsize>=0 && iLogsize<=LOGMAX );
  assert( (mem5.aCtrl[i] & CTRL_LOGSIZE)==iLogsize );

  next = MEM5LINK(i)->next;
  prev = MEM5LINK(i)->prev;
  if( prev<0 ){
    mem5.aiFreelist[iLogsize] = next;
  }else{
    MEM5LINK(prev)->next = next;
  }
  if( next>=0 ){
    MEM5LINK(next)->prev = prev;
  }
}

/*
** Link the chunk at mem5.aPool[i] so that is on the iLogsize
** free list.
*/
static void memsys5Link(int i, int iLogsize){
  int x;
  assert( sqlite3_mutex_held(mem5.mutex) );
  assert( i>=0 && i<mem5.nBlock );
  assert( iLogsize>=0 && iLogsize<=LOGMAX );
  assert( (mem5.aCtrl[i] & CTRL_LOGSIZE)==iLogsize );

  x = MEM5LINK(i)->next = mem5.aiFreelist[iLogsize];
  MEM5LINK(i)->prev = -1;
  if( x>=0 ){
    assert( x<mem5.nBlock );
    MEM5LINK(x)->prev = i;
  }
  mem5.aiFreelist[iLogsize] = i;
}

/*
** If the STATIC_MEM mutex is not already held, obtain it now. The mutex
** will already be held (obtained by code in malloc.c) if

** Return the size of an outstanding allocation, in bytes.  The
** size returned omits the 8-byte header overhead.  This only
** works for chunks that are currently checked out.
*/
static int memsys5Size(void *p){
  int iSize = 0;
  if( p ){
    int i = ((u8 *)p-mem5.zPool)/mem5.nAtom;
    assert( i>=0 && i<mem5.nBlock );
    iSize = mem5.nAtom * (1 << (mem5.aCtrl[i]&CTRL_LOGSIZE));
  }
  return iSize;
}

/*
** Find the first entry on the freelist iLogsize.  Unlink that
** entry and return its index. 
*/
static int memsys5UnlinkFirst(int iLogsize){
  int i;
  int iFirst;

  assert( iLogsize>=0 && iLogsize<=LOGMAX );
  i = iFirst = mem5.aiFreelist[iLogsize];
  assert( iFirst>=0 );
  while( i>0 ){
    if( i<iFirst ) iFirst = i;
    i = MEM5LINK(i)->next;
  }
  memsys5Unlink(iFirst, iLogsize);
  return iFirst;
}

/*
** Return a block of memory of at least nBytes in size.

  ** requests are counted */
  if( nByte>mem5.maxRequest ){
    mem5.maxRequest = nByte;
  }

  /* Round nByte up to the next valid power of two */
  if( nByte>POW2_MAX ) return 0;
  for(iFullSz=mem5.nAtom, iLogsize=0; iFullSz<nByte; iFullSz *= 2, iLogsize++){}

  /* Make sure mem5.aiFreelist[iLogsize] contains at least one free
  ** block.  If not, then split a block of the next larger power of
  ** two in order to create a new free block of size iLogsize.
  */
  for(iBin=iLogsize; mem5.aiFreelist[iBin]<0 && iBin<=LOGMAX; iBin++){}
  if( iBin>LOGMAX ) return 0;
  i = memsys5UnlinkFirst(iBin);
  while( iBin>iLogsize ){
    int newSize;

    iBin--;
    newSize = 1 << iBin;
    mem5.aCtrl[i+newSize] = CTRL_FREE | iBin;

  mem5.totalExcess += iFullSz - nByte;
  mem5.currentCount++;
  mem5.currentOut += iFullSz;
  if( mem5.maxCount<mem5.currentCount ) mem5.maxCount = mem5.currentCount;
  if( mem5.maxOut<mem5.currentOut ) mem5.maxOut = mem5.currentOut;

  /* Return a pointer to the allocated memory. */
  return (void*)&mem5.zPool[i*mem5.nAtom];
}

/*
** Free an outstanding memory allocation.
*/
static void memsys5FreeUnsafe(void *pOld){
  u32 size, iLogsize;
  int iBlock;             

  /* Set iBlock to the index of the block pointed to by pOld in 
  ** the array of mem5.nAtom byte blocks pointed to by mem5.zPool.
  */
  iBlock = ((u8 *)pOld-mem5.zPool)/mem5.nAtom;

  /* Check that the pointer pOld points to a valid, non-free block. */
  assert( iBlock>=0 && iBlock<mem5.nBlock );
  assert( ((u8 *)pOld-mem5.zPool)%mem5.nAtom==0 );
  assert( (mem5.aCtrl[iBlock] & CTRL_FREE)==0 );

  iLogsize = mem5.aCtrl[iBlock] & CTRL_LOGSIZE;
  size = 1<<iLogsize;
  assert( iBlock+size-1<mem5.nBlock );

  mem5.aCtrl[iBlock] |= CTRL_FREE;
  mem5.aCtrl[iBlock+size-1] |= CTRL_FREE;
  assert( mem5.currentCount>0 );
  assert( mem5.currentOut>=0 );
  mem5.currentCount--;
  mem5.currentOut -= size*mem5.nAtom;
  assert( mem5.currentOut>0 || mem5.currentCount==0 );
  assert( mem5.currentCount>0 || mem5.currentOut==0 );

  mem5.aCtrl[iBlock] = CTRL_FREE | iLogsize;
  while( iLogsize<LOGMAX ){
    int iBuddy;

    if( (iBlock>>iLogsize) & 1 ){
      iBuddy = iBlock - size;
    }else{
      iBuddy = iBlock + size;
    }
    assert( iBuddy>=0 );
    if( (iBuddy+(1<<iLogsize))>mem5.nBlock ) break;
    if( mem5.aCtrl[iBuddy]!=(CTRL_FREE | iLogsize) ) break;
    memsys5Unlink(iBuddy, iLogsize);
    iLogsize++;
    if( iBuddy<iBlock ){
      mem5.aCtrl[iBuddy] = CTRL_FREE | iLogsize;
      mem5.aCtrl[iBlock] = 0;
      iBlock = iBuddy;
    }else{
      mem5.aCtrl[iBlock] = CTRL_FREE | iLogsize;
      mem5.aCtrl[iBuddy] = 0;
    }
    size *= 2;
  }
  memsys5Link(iBlock, iLogsize);
}

/*
** Allocate nBytes of memory
*/
static void *memsys5Malloc(int nBytes){
  sqlite3_int64 *p = 0;
  if( nBytes>0 ){
    memsys5Enter();
    p = memsys5MallocUnsafe(nBytes);
    memsys5Leave();
  }
  return (void*)p; 
}

/*
** Free memory.
*/
static void memsys5Free(void *pPrior){
  if( pPrior==0 ){
assert(0);
    return;
  }
  memsys5Enter();
  memsys5FreeUnsafe(pPrior);
  memsys5Leave();  
}

}

/*
** Round up a request size to the next valid allocation size.
*/
static int memsys5Roundup(int n){
  int iFullSz;
  for(iFullSz=mem5.nAtom; iFullSz<n; iFullSz *= 2);
  return iFullSz;
}

static int memsys5Log(int iValue){
  int iLog;
  for(iLog=0; (1<<iLog)<iValue; iLog++);
  return iLog;
}

/*
** Initialize this module.
*/
static int memsys5Init(void *NotUsed){
  int ii;
  int nByte = sqlite3Config.nHeap;
  u8 *zByte = (u8 *)sqlite3Config.pHeap;
  int nMinLog;                 /* Log of minimum allocation size in bytes*/
  int iOffset;

  nMinLog = memsys5Log(sqlite3Config.mnReq);
  mem5.nAtom = (1<<nMinLog);
  while( sizeof(Mem5Link)>mem5.nAtom ){
    mem5.nAtom = mem5.nAtom << 1;
  }

  mem5.nBlock = (nByte / (mem5.nAtom+sizeof(u8)));
  mem5.zPool = zByte;
  mem5.aCtrl = (u8 *)&mem5.zPool[mem5.nBlock*mem5.nAtom];

  for(ii=0; ii<=LOGMAX; ii++){
    mem5.aiFreelist[ii] = -1;
  }

  iOffset = 0;
  for(ii=LOGMAX; ii>=0; ii--){
    int nAlloc = (1<<ii);
    if( (iOffset+nAlloc)<=mem5.nBlock ){
      mem5.aCtrl[iOffset] = ii | CTRL_FREE;
      memsys5Link(iOffset, ii);
      iOffset += nAlloc;
    }
    assert((iOffset+nAlloc)>mem5.nBlock);
  }

  return SQLITE_OK;
}

/*
** Deinitialize this module.
*/
static void memsys5Shutdown(void *NotUsed){
  return;
}

/*
** Open the file indicated and write a log of all unfreed memory 
** allocations into that log.
*/
void sqlite3Memsys5Dump(const char *zFilename){
#ifdef SQLITE_DEBUG
  FILE *out;
  int i, j, n;
  int nMinLog;

  if( zFilename==0 || zFilename[0]==0 ){
    out = stdout;
  }else{
    out = fopen(zFilename, "w");
    if( out==0 ){
      fprintf(stderr, "** Unable to output memory debug output log: %s **\n",
                      zFilename);
      return;
    }
  }
  memsys5Enter();
  nMinLog = memsys5Log(mem5.nAtom);
  for(i=0; i<=LOGMAX && i+nMinLog<32; i++){
    for(n=0, j=mem5.aiFreelist[i]; j>=0; j = MEM5LINK(j)->next, n++){}
    fprintf(out, "freelist items of size %d: %d\n", mem5.nAtom << i, n);
  }
  fprintf(out, "mem5.nAlloc       = %llu\n", mem5.nAlloc);
  fprintf(out, "mem5.totalAlloc   = %llu\n", mem5.totalAlloc);
  fprintf(out, "mem5.totalExcess  = %llu\n", mem5.totalExcess);
  fprintf(out, "mem5.currentOut   = %u\n", mem5.currentOut);
  fprintf(out, "mem5.currentCount = %u\n", mem5.currentCount);
  fprintf(out, "mem5.maxOut       = %u\n", mem5.maxOut);
  fprintf(out, "mem5.maxCount     = %u\n", mem5.maxCount);
  fprintf(out, "mem5.maxRequest   = %u\n", mem5.maxRequest);
  memsys5Leave();
  if( out==stdout ){
    fflush(stdout);
  }else{
    fclose(out);
  }
#endif
}

/*
** This routine is the only routine in this file with external 
** linkage. It returns a pointer to a static sqlite3_mem_methods

** struct populated with the memsys5 methods.





*/
const sqlite3_mem_methods *sqlite3MemGetMemsys5(void){
  static const sqlite3_mem_methods memsys5Methods = {
     memsys5Malloc,
     memsys5Free,
     memsys5Realloc,
     memsys5Size,
     memsys5Roundup,
     memsys5Init,
     memsys5Shutdown,
     0
  };


















  return &memsys5Methods;
}

#endif /* SQLITE_ENABLE_MEMSYS5 */

/*
** 2001 September 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.
**
*************************************************************************
** Internal interface definitions for SQLite.
**
** @(#) $Id: sqliteInt.h,v 1.733 2008/06/27 13:27:04 danielk1977 Exp $
*/
#ifndef _SQLITEINT_H_
#define _SQLITEINT_H_

/*
** Include the configuration header output by 'configure' if we're using the
** autoconf-based build

int sqlite3MallocSize(void *);
void *sqlite3ScratchMalloc(int);
void sqlite3ScratchFree(void*);
void *sqlite3PageMalloc(int);
void sqlite3PageFree(void*);
void sqlite3MemSetDefault(void);
void sqlite3MemSetMemsys3(u8 *pBlock, int nBlock);
const sqlite3_mem_methods *sqlite3MemGetMemsys5(void);
void sqlite3BenignMallocHooks(void (*)(void), void (*)(void));

#ifndef SQLITE_MUTEX_NOOP
  sqlite3_mutex_methods *sqlite3DefaultMutex(void);
  sqlite3_mutex *sqlite3MutexAlloc(int);
  int sqlite3MutexInit(void);
  int sqlite3MutexEnd(void);

**    May you share freely, never taking more than you give.
**
*************************************************************************
**
** This file contains code used to implement test interfaces to the
** memory allocation subsystem.
**
** $Id: test_malloc.c,v 1.32 2008/06/27 13:27:04 danielk1977 Exp $
*/
#include "sqliteInt.h"
#include "tcl.h"
#include <stdlib.h>
#include <string.h>
#include <assert.h>

      sz = sizeof(buf);
    }
    rc = sqlite3_config((int)clientData, buf, sz);
  }
  Tcl_SetResult(interp, (char *)sqlite3TestErrorName(rc), TCL_VOLATILE);
  return TCL_OK;
}

/*
** Usage:
**
**   sqlite3_config_heap ?-memsys3? NBYTE NMINALLOC
*/
static int test_config_heap(
  void * clientData, 
  Tcl_Interp *interp,
  int objc,
  Tcl_Obj *CONST objv[]
){
  static char zBuf[1048576];
  int nByte;         /* Size of buffer to pass to sqlite3_config() */
  int nMinAlloc;     /* Size of minimum allocation */
  int rc;            /* Return code of sqlite3_config() */
  int isMemsys3 = 0; /* True if the -memsys3 switch is present */

  Tcl_Obj * CONST *aArg = &objv[1];
  int nArg = objc-1;

  if( nArg>0 && 0==strcmp("-memsys3", Tcl_GetString(aArg[0])) ){
    nArg--;
    aArg++;
    isMemsys3 = 1;
  }
  if( nArg!=2 ){
    Tcl_WrongNumArgs(interp, 1, objv, "?-memsys3? NBYTE NMINALLOC");
    return TCL_ERROR;
  }
  if( Tcl_GetIntFromObj(interp, aArg[0], &nByte) ) return TCL_ERROR;
  if( Tcl_GetIntFromObj(interp, aArg[1], &nMinAlloc) ) return TCL_ERROR;

  if( nByte>sizeof(zBuf) ){
    nByte = sizeof(zBuf);
  }
  rc = sqlite3_config(SQLITE_CONFIG_HEAP, zBuf, nByte, nMinAlloc);

  Tcl_SetResult(interp, (char *)sqlite3TestErrorName(rc), TCL_VOLATILE);
  return TCL_OK;
}

/*
** Usage:    
**
**   sqlite3_dump_memsys3  FILENAME
**   sqlite3_dump_memsys5  FILENAME
**

     { "sqlite3_memdebug_log",       test_memdebug_log             ,0. },
     { "sqlite3_config_scratch",     test_config_scratch           ,0. },
     { "sqlite3_config_pagecache",   test_config_pagecache         ,0. },
     { "sqlite3_status",             test_status                   ,0. },
     { "install_malloc_faultsim",    test_install_malloc_faultsim  ,0. },
     { "sqlite3_config_memsys3", test_config_memsys3, SQLITE_CONFIG_MEMSYS3 },
     { "sqlite3_config_memsys5", test_config_memsys3, SQLITE_CONFIG_MEMSYS5 },
     { "sqlite3_config_heap",        test_config_heap,              0 },
     { "sqlite3_dump_memsys3",   test_dump_memsys3  , SQLITE_CONFIG_MEMSYS3 },
     { "sqlite3_dump_memsys5",   test_dump_memsys3  , SQLITE_CONFIG_MEMSYS5 }
  };
  int i;
  for(i=0; i<sizeof(aObjCmd)/sizeof(aObjCmd[0]); i++){
    ClientData c = (ClientData)aObjCmd[i].clientData;
    Tcl_CreateObjCommand(interp, aObjCmd[i].zName, aObjCmd[i].xProc, c, 0);
  }
  return TCL_OK;
}
#endif

# 2008 June 21
#
# 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.
#
#***********************************************************************
#
# $Id: permutations.test,v 1.8 2008/06/27 13:27:04 danielk1977 Exp $

set testdir [file dirname $argv0]
source $testdir/tester.tcl

# Argument processing.
#
set ::testmode [lindex $argv 0]

    collate5.test  delete3.test index2.test     ioerr.test  join3.test 
    pagesize.test  bitvec.test  capi3.test      memsubsys1.test  limit.test
    memdb.test     capi3c.test  func.test
  } -initialize {
    catch {db close}
    sqlite3_reset_auto_extension
    sqlite3_shutdown
    sqlite3_config_heap 1000000 64
    install_malloc_faultsim 1 
    sqlite3_initialize
    autoinstall_test_functions
  } -shutdown {
    catch {db close}
    sqlite3_reset_auto_extension
    sqlite3_shutdown
    sqlite3_config_memsys5 0
    install_malloc_faultsim 1 
    sqlite3_initialize
  }

  run_tests "memsys5-2" -description {
    Run tests using the allocator in mem5.c in a different configuration.
  } -include { select1.test 
  } -initialize {
    catch {db close}
    sqlite3_reset_auto_extension
    sqlite3_shutdown
    sqlite3_config_heap 250000 16
    install_malloc_faultsim 1 
    sqlite3_initialize
    autoinstall_test_functions
  } -shutdown {
    catch {db close}
    sqlite3_reset_auto_extension
    sqlite3_shutdown