AryaWu/sqlite

1/*2** 2007 October 143**4** The author disclaims copyright to this source code.  In place of5** 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** This file contains the C functions that implement a memory13** allocation subsystem for use by SQLite. 14**15** This version of the memory allocation subsystem omits all16** use of malloc(). The application gives SQLite a block of memory17** before calling sqlite3_initialize() from which allocations18** are made and returned by the xMalloc() and xRealloc() 19** implementations. Once sqlite3_initialize() has been called,20** the amount of memory available to SQLite is fixed and cannot21** be changed.22**23** This version of the memory allocation subsystem is included24** in the build only if SQLITE_ENABLE_MEMSYS5 is defined.25**26** This memory allocator uses the following algorithm:27**28**   1.  All memory allocation sizes are rounded up to a power of 2.29**30**   2.  If two adjacent free blocks are the halves of a larger block,31**       then the two blocks are coalesced into the single larger block.32**33**   3.  New memory is allocated from the first available free block.34**35** This algorithm is described in: J. M. Robson. "Bounds for Some Functions36** Concerning Dynamic Storage Allocation". Journal of the Association for37** Computing Machinery, Volume 21, Number 8, July 1974, pages 491-499.38** 39** Let n be the size of the largest allocation divided by the minimum40** allocation size (after rounding all sizes up to a power of 2.)  Let M41** be the maximum amount of memory ever outstanding at one time.  Let42** N be the total amount of memory available for allocation.  Robson43** proved that this memory allocator will never breakdown due to 44** fragmentation as long as the following constraint holds:45**46**      N >=  M*(1 + log2(n)/2) - n + 147**48** The sqlite3_status() logic tracks the maximum values of n and M so49** that an application can, at any time, verify this constraint.50*/51#include "sqliteInt.h"52 53/*54** This version of the memory allocator is used only when 55** SQLITE_ENABLE_MEMSYS5 is defined.56*/57#ifdef SQLITE_ENABLE_MEMSYS558 59/*60** A minimum allocation is an instance of the following structure.61** Larger allocations are an array of these structures where the62** size of the array is a power of 2.63**64** The size of this object must be a power of two.  That fact is65** verified in memsys5Init().66*/67typedef struct Mem5Link Mem5Link;68struct Mem5Link {69  int next;       /* Index of next free chunk */70  int prev;       /* Index of previous free chunk */71};72 73/*74** Maximum size of any allocation is ((1<<LOGMAX)*mem5.szAtom). Since75** mem5.szAtom is always at least 8 and 32-bit integers are used,76** it is not actually possible to reach this limit.77*/78#define LOGMAX 3079 80/*81** Masks used for mem5.aCtrl[] elements.82*/83#define CTRL_LOGSIZE  0x1f    /* Log2 Size of this block */84#define CTRL_FREE     0x20    /* True if not checked out */85 86/*87** All of the static variables used by this module are collected88** into a single structure named "mem5".  This is to keep the89** static variables organized and to reduce namespace pollution90** when this module is combined with other in the amalgamation.91*/92static SQLITE_WSD struct Mem5Global {93  /*94  ** Memory available for allocation95  */96  int szAtom;      /* Smallest possible allocation in bytes */97  int nBlock;      /* Number of szAtom sized blocks in zPool */98  u8 *zPool;       /* Memory available to be allocated */99  100  /*101  ** Mutex to control access to the memory allocation subsystem.102  */103  sqlite3_mutex *mutex;104 105#if defined(SQLITE_DEBUG) || defined(SQLITE_TEST)106  /*107  ** Performance statistics108  */109  u64 nAlloc;         /* Total number of calls to malloc */110  u64 totalAlloc;     /* Total of all malloc calls - includes internal frag */111  u64 totalExcess;    /* Total internal fragmentation */112  u32 currentOut;     /* Current checkout, including internal fragmentation */113  u32 currentCount;   /* Current number of distinct checkouts */114  u32 maxOut;         /* Maximum instantaneous currentOut */115  u32 maxCount;       /* Maximum instantaneous currentCount */116  u32 maxRequest;     /* Largest allocation (exclusive of internal frag) */117#endif118  119  /*120  ** Lists of free blocks.  aiFreelist[0] is a list of free blocks of121  ** size mem5.szAtom.  aiFreelist[1] holds blocks of size szAtom*2.122  ** aiFreelist[2] holds free blocks of size szAtom*4.  And so forth.123  */124  int aiFreelist[LOGMAX+1];125 126  /*127  ** Space for tracking which blocks are checked out and the size128  ** of each block.  One byte per block.129  */130  u8 *aCtrl;131 132} mem5;133 134/*135** Access the static variable through a macro for SQLITE_OMIT_WSD.136*/137#define mem5 GLOBAL(struct Mem5Global, mem5)138 139/*140** Assuming mem5.zPool is divided up into an array of Mem5Link141** structures, return a pointer to the idx-th such link.142*/143#define MEM5LINK(idx) ((Mem5Link *)(&mem5.zPool[(idx)*mem5.szAtom]))144 145/*146** Unlink the chunk at mem5.aPool[i] from list it is currently147** on.  It should be found on mem5.aiFreelist[iLogsize].148*/149static void memsys5Unlink(int i, int iLogsize){150  int next, prev;151  assert( i>=0 && i<mem5.nBlock );152  assert( iLogsize>=0 && iLogsize<=LOGMAX );153  assert( (mem5.aCtrl[i] & CTRL_LOGSIZE)==iLogsize );154 155  next = MEM5LINK(i)->next;156  prev = MEM5LINK(i)->prev;157  if( prev<0 ){158    mem5.aiFreelist[iLogsize] = next;159  }else{160    MEM5LINK(prev)->next = next;161  }162  if( next>=0 ){163    MEM5LINK(next)->prev = prev;164  }165}166 167/*168** Link the chunk at mem5.aPool[i] so that is on the iLogsize169** free list.170*/171static void memsys5Link(int i, int iLogsize){172  int x;173  assert( sqlite3_mutex_held(mem5.mutex) );174  assert( i>=0 && i<mem5.nBlock );175  assert( iLogsize>=0 && iLogsize<=LOGMAX );176  assert( (mem5.aCtrl[i] & CTRL_LOGSIZE)==iLogsize );177 178  x = MEM5LINK(i)->next = mem5.aiFreelist[iLogsize];179  MEM5LINK(i)->prev = -1;180  if( x>=0 ){181    assert( x<mem5.nBlock );182    MEM5LINK(x)->prev = i;183  }184  mem5.aiFreelist[iLogsize] = i;185}186 187/*188** Obtain or release the mutex needed to access global data structures.189*/190static void memsys5Enter(void){191  sqlite3_mutex_enter(mem5.mutex);192}193static void memsys5Leave(void){194  sqlite3_mutex_leave(mem5.mutex);195}196 197/*198** Return the size of an outstanding allocation, in bytes.199** This only works for chunks that are currently checked out.200*/201static int memsys5Size(void *p){202  int iSize, i;203  assert( p!=0 );204  i = (int)(((u8 *)p-mem5.zPool)/mem5.szAtom);205  assert( i>=0 && i<mem5.nBlock );206  iSize = mem5.szAtom * (1 << (mem5.aCtrl[i]&CTRL_LOGSIZE));207  return iSize;208}209 210/*211** Return a block of memory of at least nBytes in size.212** Return NULL if unable.  Return NULL if nBytes==0.213**214** The caller guarantees that nByte is positive.215**216** The caller has obtained a mutex prior to invoking this217** routine so there is never any chance that two or more218** threads can be in this routine at the same time.219*/220static void *memsys5MallocUnsafe(int nByte){221  int i;           /* Index of a mem5.aPool[] slot */222  int iBin;        /* Index into mem5.aiFreelist[] */223  int iFullSz;     /* Size of allocation rounded up to power of 2 */224  int iLogsize;    /* Log2 of iFullSz/POW2_MIN */225 226  /* nByte must be a positive */227  assert( nByte>0 );228 229  /* No more than 1GiB per allocation */230  if( nByte > 0x40000000 ) return 0;231 232#if defined(SQLITE_DEBUG) || defined(SQLITE_TEST)233  /* Keep track of the maximum allocation request.  Even unfulfilled234  ** requests are counted */235  if( (u32)nByte>mem5.maxRequest ){236    mem5.maxRequest = nByte;237  }238#endif239 240 241  /* Round nByte up to the next valid power of two */242  for(iFullSz=mem5.szAtom,iLogsize=0; iFullSz<nByte; iFullSz*=2,iLogsize++){}243 244  /* Make sure mem5.aiFreelist[iLogsize] contains at least one free245  ** block.  If not, then split a block of the next larger power of246  ** two in order to create a new free block of size iLogsize.247  */248  for(iBin=iLogsize; iBin<=LOGMAX && mem5.aiFreelist[iBin]<0; iBin++){}249  if( iBin>LOGMAX ){250    testcase( sqlite3GlobalConfig.xLog!=0 );251    sqlite3_log(SQLITE_NOMEM, "failed to allocate %u bytes", nByte);252    return 0;253  }254  i = mem5.aiFreelist[iBin];255  memsys5Unlink(i, iBin);256  while( iBin>iLogsize ){257    int newSize;258 259    iBin--;260    newSize = 1 << iBin;261    mem5.aCtrl[i+newSize] = CTRL_FREE | iBin;262    memsys5Link(i+newSize, iBin);263  }264  mem5.aCtrl[i] = iLogsize;265 266#if defined(SQLITE_DEBUG) || defined(SQLITE_TEST)267  /* Update allocator performance statistics. */268  mem5.nAlloc++;269  mem5.totalAlloc += iFullSz;270  mem5.totalExcess += iFullSz - nByte;271  mem5.currentCount++;272  mem5.currentOut += iFullSz;273  if( mem5.maxCount<mem5.currentCount ) mem5.maxCount = mem5.currentCount;274  if( mem5.maxOut<mem5.currentOut ) mem5.maxOut = mem5.currentOut;275#endif276 277#ifdef SQLITE_DEBUG278  /* Make sure the allocated memory does not assume that it is set to zero279  ** or retains a value from a previous allocation */280  memset(&mem5.zPool[i*mem5.szAtom], 0xAA, iFullSz);281#endif282 283  /* Return a pointer to the allocated memory. */284  return (void*)&mem5.zPool[i*mem5.szAtom];285}286 287/*288** Free an outstanding memory allocation.289*/290static void memsys5FreeUnsafe(void *pOld){291  u32 size, iLogsize;292  int iBlock;293 294  /* Set iBlock to the index of the block pointed to by pOld in 295  ** the array of mem5.szAtom byte blocks pointed to by mem5.zPool.296  */297  iBlock = (int)(((u8 *)pOld-mem5.zPool)/mem5.szAtom);298 299  /* Check that the pointer pOld points to a valid, non-free block. */300  assert( iBlock>=0 && iBlock<mem5.nBlock );301  assert( ((u8 *)pOld-mem5.zPool)%mem5.szAtom==0 );302  assert( (mem5.aCtrl[iBlock] & CTRL_FREE)==0 );303 304  iLogsize = mem5.aCtrl[iBlock] & CTRL_LOGSIZE;305  size = 1<<iLogsize;306  assert( iBlock+size-1<(u32)mem5.nBlock );307 308  mem5.aCtrl[iBlock] |= CTRL_FREE;309  mem5.aCtrl[iBlock+size-1] |= CTRL_FREE;310 311#if defined(SQLITE_DEBUG) || defined(SQLITE_TEST)312  assert( mem5.currentCount>0 );313  assert( mem5.currentOut>=(size*mem5.szAtom) );314  mem5.currentCount--;315  mem5.currentOut -= size*mem5.szAtom;316  assert( mem5.currentOut>0 || mem5.currentCount==0 );317  assert( mem5.currentCount>0 || mem5.currentOut==0 );318#endif319 320  mem5.aCtrl[iBlock] = CTRL_FREE | iLogsize;321  while( ALWAYS(iLogsize<LOGMAX) ){322    int iBuddy;323    if( (iBlock>>iLogsize) & 1 ){324      iBuddy = iBlock - size;325      assert( iBuddy>=0 );326    }else{327      iBuddy = iBlock + size;328      if( iBuddy>=mem5.nBlock ) break;329    }330    if( mem5.aCtrl[iBuddy]!=(CTRL_FREE | iLogsize) ) break;331    memsys5Unlink(iBuddy, iLogsize);332    iLogsize++;333    if( iBuddy<iBlock ){334      mem5.aCtrl[iBuddy] = CTRL_FREE | iLogsize;335      mem5.aCtrl[iBlock] = 0;336      iBlock = iBuddy;337    }else{338      mem5.aCtrl[iBlock] = CTRL_FREE | iLogsize;339      mem5.aCtrl[iBuddy] = 0;340    }341    size *= 2;342  }343 344#ifdef SQLITE_DEBUG345  /* Overwrite freed memory with the 0x55 bit pattern to verify that it is346  ** not used after being freed */347  memset(&mem5.zPool[iBlock*mem5.szAtom], 0x55, size);348#endif349 350  memsys5Link(iBlock, iLogsize);351}352 353/*354** Allocate nBytes of memory.355*/356static void *memsys5Malloc(int nBytes){357  sqlite3_int64 *p = 0;358  if( nBytes>0 ){359    memsys5Enter();360    p = memsys5MallocUnsafe(nBytes);361    memsys5Leave();362  }363  return (void*)p; 364}365 366/*367** Free memory.368**369** The outer layer memory allocator prevents this routine from370** being called with pPrior==0.371*/372static void memsys5Free(void *pPrior){373  assert( pPrior!=0 );374  memsys5Enter();375  memsys5FreeUnsafe(pPrior);376  memsys5Leave();  377}378 379/*380** Change the size of an existing memory allocation.381**382** The outer layer memory allocator prevents this routine from383** being called with pPrior==0.  384**385** nBytes is always a value obtained from a prior call to386** memsys5Round().  Hence nBytes is always a non-negative power387** of two.  If nBytes==0 that means that an oversize allocation388** (an allocation larger than 0x40000000) was requested and this389** routine should return 0 without freeing pPrior.390*/391static void *memsys5Realloc(void *pPrior, int nBytes){392  int nOld;393  void *p;394  assert( pPrior!=0 );395  assert( (nBytes&(nBytes-1))==0 );  /* EV: R-46199-30249 */396  assert( nBytes>=0 );397  if( nBytes==0 ){398    return 0;399  }400  nOld = memsys5Size(pPrior);401  if( nBytes<=nOld ){402    return pPrior;403  }404  p = memsys5Malloc(nBytes);405  if( p ){406    memcpy(p, pPrior, nOld);407    memsys5Free(pPrior);408  }409  return p;410}411 412/*413** Round up a request size to the next valid allocation size.  If414** the allocation is too large to be handled by this allocation system,415** return 0.416**417** All allocations must be a power of two and must be expressed by a418** 32-bit signed integer.  Hence the largest allocation is 0x40000000419** or 1073741824 bytes.420*/421static int memsys5Roundup(int n){422  int iFullSz;423  if( n<=mem5.szAtom*2 ){424    if( n<=mem5.szAtom ) return mem5.szAtom;425    return mem5.szAtom*2;426  }427  if( n>0x10000000 ){428    if( n>0x40000000 ) return 0;429    if( n>0x20000000 ) return 0x40000000;430    return 0x20000000;431  }432  for(iFullSz=mem5.szAtom*8; iFullSz<n; iFullSz *= 4);433  if( (iFullSz/2)>=(i64)n ) return iFullSz/2;434  return iFullSz;435}436 437/*438** Return the ceiling of the logarithm base 2 of iValue.439**440** Examples:   memsys5Log(1) -> 0441**             memsys5Log(2) -> 1442**             memsys5Log(4) -> 2443**             memsys5Log(5) -> 3444**             memsys5Log(8) -> 3445**             memsys5Log(9) -> 4446*/447static int memsys5Log(int iValue){448  int iLog;449  for(iLog=0; (iLog<(int)((sizeof(int)*8)-1)) && (1<<iLog)<iValue; iLog++);450  return iLog;451}452 453/*454** Initialize the memory allocator.455**456** This routine is not threadsafe.  The caller must be holding a mutex457** to prevent multiple threads from entering at the same time.458*/459static int memsys5Init(void *NotUsed){460  int ii;            /* Loop counter */461  int nByte;         /* Number of bytes of memory available to this allocator */462  u8 *zByte;         /* Memory usable by this allocator */463  int nMinLog;       /* Log base 2 of minimum allocation size in bytes */464  int iOffset;       /* An offset into mem5.aCtrl[] */465 466  UNUSED_PARAMETER(NotUsed);467 468  /* For the purposes of this routine, disable the mutex */469  mem5.mutex = 0;470 471  /* The size of a Mem5Link object must be a power of two.  Verify that472  ** this is case.473  */474  assert( (sizeof(Mem5Link)&(sizeof(Mem5Link)-1))==0 );475 476  nByte = sqlite3GlobalConfig.nHeap;477  zByte = (u8*)sqlite3GlobalConfig.pHeap;478  assert( zByte!=0 );  /* sqlite3_config() does not allow otherwise */479 480  /* boundaries on sqlite3GlobalConfig.mnReq are enforced in sqlite3_config() */481  nMinLog = memsys5Log(sqlite3GlobalConfig.mnReq);482  mem5.szAtom = (1<<nMinLog);483  while( (int)sizeof(Mem5Link)>mem5.szAtom ){484    mem5.szAtom = mem5.szAtom << 1;485  }486 487  mem5.nBlock = (nByte / (mem5.szAtom+sizeof(u8)));488  mem5.zPool = zByte;489  mem5.aCtrl = (u8 *)&mem5.zPool[mem5.nBlock*mem5.szAtom];490 491  for(ii=0; ii<=LOGMAX; ii++){492    mem5.aiFreelist[ii] = -1;493  }494 495  iOffset = 0;496  for(ii=LOGMAX; ii>=0; ii--){497    int nAlloc = (1<<ii);498    if( (iOffset+nAlloc)<=mem5.nBlock ){499      mem5.aCtrl[iOffset] = ii | CTRL_FREE;500      memsys5Link(iOffset, ii);501      iOffset += nAlloc;502    }503    assert((iOffset+nAlloc)>mem5.nBlock);504  }505 506  /* If a mutex is required for normal operation, allocate one */507  if( sqlite3GlobalConfig.bMemstat==0 ){508    mem5.mutex = sqlite3MutexAlloc(SQLITE_MUTEX_STATIC_MEM);509  }510 511  return SQLITE_OK;512}513 514/*515** Deinitialize this module.516*/517static void memsys5Shutdown(void *NotUsed){518  UNUSED_PARAMETER(NotUsed);519  mem5.mutex = 0;520  return;521}522 523#ifdef SQLITE_TEST524/*525** Open the file indicated and write a log of all unfreed memory 526** allocations into that log.527*/528void sqlite3Memsys5Dump(const char *zFilename){529  FILE *out;530  int i, j, n;531  int nMinLog;532 533  if( zFilename==0 || zFilename[0]==0 ){534    out = stdout;535  }else{536    out = fopen(zFilename, "w");537    if( out==0 ){538      fprintf(stderr, "** Unable to output memory debug output log: %s **\n",539                      zFilename);540      return;541    }542  }543  memsys5Enter();544  nMinLog = memsys5Log(mem5.szAtom);545  for(i=0; i<=LOGMAX && i+nMinLog<32; i++){546    for(n=0, j=mem5.aiFreelist[i]; j>=0; j = MEM5LINK(j)->next, n++){}547    fprintf(out, "freelist items of size %d: %d\n", mem5.szAtom << i, n);548  }549  fprintf(out, "mem5.nAlloc       = %llu\n", mem5.nAlloc);550  fprintf(out, "mem5.totalAlloc   = %llu\n", mem5.totalAlloc);551  fprintf(out, "mem5.totalExcess  = %llu\n", mem5.totalExcess);552  fprintf(out, "mem5.currentOut   = %u\n", mem5.currentOut);553  fprintf(out, "mem5.currentCount = %u\n", mem5.currentCount);554  fprintf(out, "mem5.maxOut       = %u\n", mem5.maxOut);555  fprintf(out, "mem5.maxCount     = %u\n", mem5.maxCount);556  fprintf(out, "mem5.maxRequest   = %u\n", mem5.maxRequest);557  memsys5Leave();558  if( out==stdout ){559    fflush(stdout);560  }else{561    fclose(out);562  }563}564#endif565 566/*567** This routine is the only routine in this file with external 568** linkage. It returns a pointer to a static sqlite3_mem_methods569** struct populated with the memsys5 methods.570*/571const sqlite3_mem_methods *sqlite3MemGetMemsys5(void){572  static const sqlite3_mem_methods memsys5Methods = {573     memsys5Malloc,574     memsys5Free,575     memsys5Realloc,576     memsys5Size,577     memsys5Roundup,578     memsys5Init,579     memsys5Shutdown,580     0581  };582  return &memsys5Methods;583}584 585#endif /* SQLITE_ENABLE_MEMSYS5 */586