src/third_party/sqlite/src/src/mem5.c

   1 /*
   2 ** 2007 October 14
   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 ** This file contains the C functions that implement a memory
  13 ** allocation subsystem for use by SQLite.
  14 **
  15 ** This version of the memory allocation subsystem omits all
  16 ** use of malloc(). The application gives SQLite a block of memory
  17 ** before calling sqlite3_initialize() from which allocations
  18 ** 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 cannot
  21 ** be changed.
  22 **
  23 ** This version of the memory allocation subsystem is included
  24 ** in the build only if SQLITE_ENABLE_MEMSYS5 is defined.
  25 **
  26 ** This memory allocator uses the following algorithm:
  27 **
  28 **   1.  All memory allocations 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 coalesed 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 Functions
  36 ** Concerning Dynamic Storage Allocation". Journal of the Association for
  37 ** 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 minimum
  40 ** allocation size (after rounding all sizes up to a power of 2.)  Let M
  41 ** be the maximum amount of memory ever outstanding at one time.  Let
  42 ** N be the total amount of memory available for allocation.  Robson
  43 ** 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 + 1
  47 **
  48 ** The sqlite3_status() logic tracks the maximum values of n and M so
  49 ** 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_MEMSYS5
  58
  59 /*
  60 ** A minimum allocation is an instance of the following structure.
  61 ** Larger allocations are an array of these structures where the
  62 ** size of the array is a power of 2.
  63 **
  64 ** The size of this object must be a power of two.  That fact is
  65 ** verified in memsys5Init().
  66 */
  67 typedef struct Mem5Link Mem5Link;
  68 struct 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). Since
  75 ** 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 30
  79
  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 collected
  88 ** into a single structure named "mem5".  This is to keep the
  89 ** static variables organized and to reduce namespace pollution
  90 ** when this module is combined with other in the amalgamation.
  91 */
  92 static SQLITE_WSD struct Mem5Global {
  93   /*
  94   ** Memory available for allocation
  95   */
  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   /*
 106   ** Performance statistics
 107   */
 108   u64 nAlloc;         /* Total number of calls to malloc */
 109   u64 totalAlloc;     /* Total of all malloc calls - includes internal frag */
 110   u64 totalExcess;    /* Total internal fragmentation */
 111   u32 currentOut;     /* Current checkout, including internal fragmentation */
 112   u32 currentCount;   /* Current number of distinct checkouts */
 113   u32 maxOut;         /* Maximum instantaneous currentOut */
 114   u32 maxCount;       /* Maximum instantaneous currentCount */
 115   u32 maxRequest;     /* Largest allocation (exclusive of internal frag) */
 116
 117   /*
 118   ** Lists of free blocks.  aiFreelist[0] is a list of free blocks of
 119   ** size mem5.szAtom.  aiFreelist[1] holds blocks of size szAtom*2.
 120   ** and so forth.
 121   */
 122   int aiFreelist[LOGMAX+1];
 123
 124   /*
 125   ** Space for tracking which blocks are checked out and the size
 126   ** of each block.  One byte per block.
 127   */
 128   u8 *aCtrl;
 129
 130 } mem5;
 131
 132 /*
 133 ** Access the static variable through a macro for SQLITE_OMIT_WSD
 134 */
 135 #define mem5 GLOBAL(struct Mem5Global, mem5)
 136
 137 /*
 138 ** Assuming mem5.zPool is divided up into an array of Mem5Link
 139 ** structures, return a pointer to the idx-th such lik.
 140 */
 141 #define MEM5LINK(idx) ((Mem5Link *)(&mem5.zPool[(idx)*mem5.szAtom]))
 142
 143 /*
 144 ** Unlink the chunk at mem5.aPool[i] from list it is currently
 145 ** on.  It should be found on mem5.aiFreelist[iLogsize].
 146 */
 147 static void memsys5Unlink(int i, int iLogsize){
 148   int next, prev;
 149   assert( i>=0 && i<mem5.nBlock );
 150   assert( iLogsize>=0 && iLogsize<=LOGMAX );
 151   assert( (mem5.aCtrl[i] & CTRL_LOGSIZE)==iLogsize );
 152
 153   next = MEM5LINK(i)->next;
 154   prev = MEM5LINK(i)->prev;
 155   if( prev<0 ){
 156     mem5.aiFreelist[iLogsize] = next;
 157   }else{
 158     MEM5LINK(prev)->next = next;
 159   }
 160   if( next>=0 ){
 161     MEM5LINK(next)->prev = prev;
 162   }
 163 }
 164
 165 /*
 166 ** Link the chunk at mem5.aPool[i] so that is on the iLogsize
 167 ** free list.
 168 */
 169 static void memsys5Link(int i, int iLogsize){
 170   int x;
 171   assert( sqlite3_mutex_held(mem5.mutex) );
 172   assert( i>=0 && i<mem5.nBlock );
 173   assert( iLogsize>=0 && iLogsize<=LOGMAX );
 174   assert( (mem5.aCtrl[i] & CTRL_LOGSIZE)==iLogsize );
 175
 176   x = MEM5LINK(i)->next = mem5.aiFreelist[iLogsize];
 177   MEM5LINK(i)->prev = -1;
 178   if( x>=0 ){
 179     assert( x<mem5.nBlock );
 180     MEM5LINK(x)->prev = i;
 181   }
 182   mem5.aiFreelist[iLogsize] = i;
 183 }
 184
 185 /*
 186 ** If the STATIC_MEM mutex is not already held, obtain it now. The mutex
 187 ** will already be held (obtained by code in malloc.c) if
 188 ** sqlite3GlobalConfig.bMemStat is true.
 189 */
 190 static void memsys5Enter(void){
 191   sqlite3_mutex_enter(mem5.mutex);
 192 }
 193 static void memsys5Leave(void){
 194   sqlite3_mutex_leave(mem5.mutex);
 195 }
 196
 197 /*
 198 ** Return the size of an outstanding allocation, in bytes.  The
 199 ** size returned omits the 8-byte header overhead.  This only
 200 ** works for chunks that are currently checked out.
 201 */
 202 static int memsys5Size(void *p){
 203   int iSize = 0;
 204   if( p ){
 205     int i = ((u8 *)p-mem5.zPool)/mem5.szAtom;
 206     assert( i>=0 && i<mem5.nBlock );
 207     iSize = mem5.szAtom * (1 << (mem5.aCtrl[i]&CTRL_LOGSIZE));
 208   }
 209   return iSize;
 210 }
 211
 212 /*
 213 ** Find the first entry on the freelist iLogsize.  Unlink that
 214 ** entry and return its index.
 215 */
 216 static int memsys5UnlinkFirst(int iLogsize){
 217   int i;
 218   int iFirst;
 219
 220   assert( iLogsize>=0 && iLogsize<=LOGMAX );
 221   i = iFirst = mem5.aiFreelist[iLogsize];
 222   assert( iFirst>=0 );
 223   while( i>0 ){
 224     if( i<iFirst ) iFirst = i;
 225     i = MEM5LINK(i)->next;
 226   }
 227   memsys5Unlink(iFirst, iLogsize);
 228   return iFirst;
 229 }
 230
 231 /*
 232 ** Return a block of memory of at least nBytes in size.
 233 ** Return NULL if unable.  Return NULL if nBytes==0.
 234 **
 235 ** The caller guarantees that nByte positive.
 236 **
 237 ** The caller has obtained a mutex prior to invoking this
 238 ** routine so there is never any chance that two or more
 239 ** threads can be in this routine at the same time.
 240 */
 241 static void *memsys5MallocUnsafe(int nByte){
 242   int i;           /* Index of a mem5.aPool[] slot */
 243   int iBin;        /* Index into mem5.aiFreelist[] */
 244   int iFullSz;     /* Size of allocation rounded up to power of 2 */
 245   int iLogsize;    /* Log2 of iFullSz/POW2_MIN */
 246
 247   /* nByte must be a positive */
 248   assert( nByte>0 );
 249
 250   /* Keep track of the maximum allocation request.  Even unfulfilled
 251   ** requests are counted */
 252   if( (u32)nByte>mem5.maxRequest ){
 253     mem5.maxRequest = nByte;
 254   }
 255
 256   /* Abort if the requested allocation size is larger than the largest
 257   ** power of two that we can represent using 32-bit signed integers.
 258   */
 259   if( nByte > 0x40000000 ){
 260     return 0;
 261   }
 262
 263   /* Round nByte up to the next valid power of two */
 264   for(iFullSz=mem5.szAtom, iLogsize=0; iFullSz<nByte; iFullSz *= 2, iLogsize++){}
 265
 266   /* Make sure mem5.aiFreelist[iLogsize] contains at least one free
 267   ** block.  If not, then split a block of the next larger power of
 268   ** two in order to create a new free block of size iLogsize.
 269   */
 270   for(iBin=iLogsize; mem5.aiFreelist[iBin]<0 && iBin<=LOGMAX; iBin++){}
 271   if( iBin>LOGMAX ){
 272     testcase( sqlite3GlobalConfig.xLog!=0 );
 273     sqlite3_log(SQLITE_NOMEM, "failed to allocate %u bytes", nByte);
 274     return 0;
 275   }
 276   i = memsys5UnlinkFirst(iBin);
 277   while( iBin>iLogsize ){
 278     int newSize;
 279
 280     iBin--;
 281     newSize = 1 << iBin;
 282     mem5.aCtrl[i+newSize] = CTRL_FREE | iBin;
 283     memsys5Link(i+newSize, iBin);
 284   }
 285   mem5.aCtrl[i] = iLogsize;
 286
 287   /* Update allocator performance statistics. */
 288   mem5.nAlloc++;
 289   mem5.totalAlloc += iFullSz;
 290   mem5.totalExcess += iFullSz - nByte;
 291   mem5.currentCount++;
 292   mem5.currentOut += iFullSz;
 293   if( mem5.maxCount<mem5.currentCount ) mem5.maxCount = mem5.currentCount;
 294   if( mem5.maxOut<mem5.currentOut ) mem5.maxOut = mem5.currentOut;
 295
 296   /* Return a pointer to the allocated memory. */
 297   return (void*)&mem5.zPool[i*mem5.szAtom];
 298 }
 299
 300 /*
 301 ** Free an outstanding memory allocation.
 302 */
 303 static void memsys5FreeUnsafe(void *pOld){
 304   u32 size, iLogsize;
 305   int iBlock;
 306
 307   /* Set iBlock to the index of the block pointed to by pOld in
 308   ** the array of mem5.szAtom byte blocks pointed to by mem5.zPool.
 309   */
 310   iBlock = ((u8 *)pOld-mem5.zPool)/mem5.szAtom;
 311
 312   /* Check that the pointer pOld points to a valid, non-free block. */
 313   assert( iBlock>=0 && iBlock<mem5.nBlock );
 314   assert( ((u8 *)pOld-mem5.zPool)%mem5.szAtom==0 );
 315   assert( (mem5.aCtrl[iBlock] & CTRL_FREE)==0 );
 316
 317   iLogsize = mem5.aCtrl[iBlock] & CTRL_LOGSIZE;
 318   size = 1<<iLogsize;
 319   assert( iBlock+size-1<(u32)mem5.nBlock );
 320
 321   mem5.aCtrl[iBlock] |= CTRL_FREE;
 322   mem5.aCtrl[iBlock+size-1] |= CTRL_FREE;
 323   assert( mem5.currentCount>0 );
 324   assert( mem5.currentOut>=(size*mem5.szAtom) );
 325   mem5.currentCount--;
 326   mem5.currentOut -= size*mem5.szAtom;
 327   assert( mem5.currentOut>0 || mem5.currentCount==0 );
 328   assert( mem5.currentCount>0 || mem5.currentOut==0 );
 329
 330   mem5.aCtrl[iBlock] = CTRL_FREE | iLogsize;
 331   while( ALWAYS(iLogsize<LOGMAX) ){
 332     int iBuddy;
 333     if( (iBlock>>iLogsize) & 1 ){
 334       iBuddy = iBlock - size;
 335     }else{
 336       iBuddy = iBlock + size;
 337     }
 338     assert( iBuddy>=0 );
 339     if( (iBuddy+(1<<iLogsize))>mem5.nBlock ) break;
 340     if( mem5.aCtrl[iBuddy]!=(CTRL_FREE | iLogsize) ) break;
 341     memsys5Unlink(iBuddy, iLogsize);
 342     iLogsize++;
 343     if( iBuddy<iBlock ){
 344       mem5.aCtrl[iBuddy] = CTRL_FREE | iLogsize;
 345       mem5.aCtrl[iBlock] = 0;
 346       iBlock = iBuddy;
 347     }else{
 348       mem5.aCtrl[iBlock] = CTRL_FREE | iLogsize;
 349       mem5.aCtrl[iBuddy] = 0;
 350     }
 351     size *= 2;
 352   }
 353   memsys5Link(iBlock, iLogsize);
 354 }
 355
 356 /*
 357 ** Allocate nBytes of memory
 358 */
 359 static void *memsys5Malloc(int nBytes){
 360   sqlite3_int64 *p = 0;
 361   if( nBytes>0 ){
 362     memsys5Enter();
 363     p = memsys5MallocUnsafe(nBytes);
 364     memsys5Leave();
 365   }
 366   return (void*)p;
 367 }
 368
 369 /*
 370 ** Free memory.
 371 **
 372 ** The outer layer memory allocator prevents this routine from
 373 ** being called with pPrior==0.
 374 */
 375 static void memsys5Free(void *pPrior){
 376   assert( pPrior!=0 );
 377   memsys5Enter();
 378   memsys5FreeUnsafe(pPrior);
 379   memsys5Leave();
 380 }
 381
 382 /*
 383 ** Change the size of an existing memory allocation.
 384 **
 385 ** The outer layer memory allocator prevents this routine from
 386 ** being called with pPrior==0.
 387 **
 388 ** nBytes is always a value obtained from a prior call to
 389 ** memsys5Round().  Hence nBytes is always a non-negative power
 390 ** of two.  If nBytes==0 that means that an oversize allocation
 391 ** (an allocation larger than 0x40000000) was requested and this
 392 ** routine should return 0 without freeing pPrior.
 393 */
 394 static void *memsys5Realloc(void *pPrior, int nBytes){
 395   int nOld;
 396   void *p;
 397   assert( pPrior!=0 );
 398   assert( (nBytes&(nBytes-1))==0 );  /* EV: R-46199-30249 */
 399   assert( nBytes>=0 );
 400   if( nBytes==0 ){
 401     return 0;
 402   }
 403   nOld = memsys5Size(pPrior);
 404   if( nBytes<=nOld ){
 405     return pPrior;
 406   }
 407   memsys5Enter();
 408   p = memsys5MallocUnsafe(nBytes);
 409   if( p ){
 410     memcpy(p, pPrior, nOld);
 411     memsys5FreeUnsafe(pPrior);
 412   }
 413   memsys5Leave();
 414   return p;
 415 }
 416
 417 /*
 418 ** Round up a request size to the next valid allocation size.  If
 419 ** the allocation is too large to be handled by this allocation system,
 420 ** return 0.
 421 **
 422 ** All allocations must be a power of two and must be expressed by a
 423 ** 32-bit signed integer.  Hence the largest allocation is 0x40000000
 424 ** or 1073741824 bytes.
 425 */
 426 static int memsys5Roundup(int n){
 427   int iFullSz;
 428   if( n > 0x40000000 ) return 0;
 429   for(iFullSz=mem5.szAtom; iFullSz<n; iFullSz *= 2);
 430   return iFullSz;
 431 }
 432
 433 /*
 434 ** Return the ceiling of the logarithm base 2 of iValue.
 435 **
 436 ** Examples:   memsys5Log(1) -> 0
 437 **             memsys5Log(2) -> 1
 438 **             memsys5Log(4) -> 2
 439 **             memsys5Log(5) -> 3
 440 **             memsys5Log(8) -> 3
 441 **             memsys5Log(9) -> 4
 442 */
 443 static int memsys5Log(int iValue){
 444   int iLog;
 445   for(iLog=0; (iLog<(int)((sizeof(int)*8)-1)) && (1<<iLog)<iValue; iLog++);
 446   return iLog;
 447 }
 448
 449 /*
 450 ** Initialize the memory allocator.
 451 **
 452 ** This routine is not threadsafe.  The caller must be holding a mutex
 453 ** to prevent multiple threads from entering at the same time.
 454 */
 455 static int memsys5Init(void *NotUsed){
 456   int ii;            /* Loop counter */
 457   int nByte;         /* Number of bytes of memory available to this allocator */
 458   u8 *zByte;         /* Memory usable by this allocator */
 459   int nMinLog;       /* Log base 2 of minimum allocation size in bytes */
 460   int iOffset;       /* An offset into mem5.aCtrl[] */
 461
 462   UNUSED_PARAMETER(NotUsed);
 463
 464   /* For the purposes of this routine, disable the mutex */
 465   mem5.mutex = 0;
 466
 467   /* The size of a Mem5Link object must be a power of two.  Verify that
 468   ** this is case.
 469   */
 470   assert( (sizeof(Mem5Link)&(sizeof(Mem5Link)-1))==0 );
 471
 472   nByte = sqlite3GlobalConfig.nHeap;
 473   zByte = (u8*)sqlite3GlobalConfig.pHeap;
 474   assert( zByte!=0 );  /* sqlite3_config() does not allow otherwise */
 475
 476   /* boundaries on sqlite3GlobalConfig.mnReq are enforced in sqlite3_config() */
 477   nMinLog = memsys5Log(sqlite3GlobalConfig.mnReq);
 478   mem5.szAtom = (1<<nMinLog);
 479   while( (int)sizeof(Mem5Link)>mem5.szAtom ){
 480     mem5.szAtom = mem5.szAtom << 1;
 481   }
 482
 483   mem5.nBlock = (nByte / (mem5.szAtom+sizeof(u8)));
 484   mem5.zPool = zByte;
 485   mem5.aCtrl = (u8 *)&mem5.zPool[mem5.nBlock*mem5.szAtom];
 486
 487   for(ii=0; ii<=LOGMAX; ii++){
 488     mem5.aiFreelist[ii] = -1;
 489   }
 490
 491   iOffset = 0;
 492   for(ii=LOGMAX; ii>=0; ii--){
 493     int nAlloc = (1<<ii);
 494     if( (iOffset+nAlloc)<=mem5.nBlock ){
 495       mem5.aCtrl[iOffset] = ii | CTRL_FREE;
 496       memsys5Link(iOffset, ii);
 497       iOffset += nAlloc;
 498     }
 499     assert((iOffset+nAlloc)>mem5.nBlock);
 500   }
 501
 502   /* If a mutex is required for normal operation, allocate one */
 503   if( sqlite3GlobalConfig.bMemstat==0 ){
 504     mem5.mutex = sqlite3MutexAlloc(SQLITE_MUTEX_STATIC_MEM);
 505   }
 506
 507   return SQLITE_OK;
 508 }
 509
 510 /*
 511 ** Deinitialize this module.
 512 */
 513 static void memsys5Shutdown(void *NotUsed){
 514   UNUSED_PARAMETER(NotUsed);
 515   mem5.mutex = 0;
 516   return;
 517 }
 518
 519 #ifdef SQLITE_TEST
 520 /*
 521 ** Open the file indicated and write a log of all unfreed memory
 522 ** allocations into that log.
 523 */
 524 void sqlite3Memsys5Dump(const char *zFilename){
 525   FILE *out;
 526   int i, j, n;
 527   int nMinLog;
 528
 529   if( zFilename==0 || zFilename[0]==0 ){
 530     out = stdout;
 531   }else{
 532     out = fopen(zFilename, "w");
 533     if( out==0 ){
 534       fprintf(stderr, "** Unable to output memory debug output log: %s **\n",
 535                       zFilename);
 536       return;
 537     }
 538   }
 539   memsys5Enter();
 540   nMinLog = memsys5Log(mem5.szAtom);
 541   for(i=0; i<=LOGMAX && i+nMinLog<32; i++){
 542     for(n=0, j=mem5.aiFreelist[i]; j>=0; j = MEM5LINK(j)->next, n++){}
 543     fprintf(out, "freelist items of size %d: %d\n", mem5.szAtom << i, n);
 544   }
 545   fprintf(out, "mem5.nAlloc       = %llu\n", mem5.nAlloc);
 546   fprintf(out, "mem5.totalAlloc   = %llu\n", mem5.totalAlloc);
 547   fprintf(out, "mem5.totalExcess  = %llu\n", mem5.totalExcess);
 548   fprintf(out, "mem5.currentOut   = %u\n", mem5.currentOut);
 549   fprintf(out, "mem5.currentCount = %u\n", mem5.currentCount);
 550   fprintf(out, "mem5.maxOut       = %u\n", mem5.maxOut);
 551   fprintf(out, "mem5.maxCount     = %u\n", mem5.maxCount);
 552   fprintf(out, "mem5.maxRequest   = %u\n", mem5.maxRequest);
 553   memsys5Leave();
 554   if( out==stdout ){
 555     fflush(stdout);
 556   }else{
 557     fclose(out);
 558   }
 559 }
 560 #endif
 561
 562 /*
 563 ** This routine is the only routine in this file with external
 564 ** linkage. It returns a pointer to a static sqlite3_mem_methods
 565 ** struct populated with the memsys5 methods.
 566 */
 567 const sqlite3_mem_methods *sqlite3MemGetMemsys5(void){
 568   static const sqlite3_mem_methods memsys5Methods = {
 569      memsys5Malloc,
 570      memsys5Free,
 571      memsys5Realloc,
 572      memsys5Size,
 573      memsys5Roundup,
 574      memsys5Init,
 575      memsys5Shutdown,
 576      0
 577   };
 578   return &memsys5Methods;
 579 }
 580
 581 #endif /* SQLITE_ENABLE_MEMSYS5 */