000001 /*
000002 ** 2007 October 14
000003 **
000004 ** The author disclaims copyright to this source code. In place of
000005 ** a legal notice, here is a blessing:
000006 **
000007 ** May you do good and not evil.
000008 ** May you find forgiveness for yourself and forgive others.
000009 ** May you share freely, never taking more than you give.
000010 **
000011 *************************************************************************
000012 ** This file contains the C functions that implement a memory
000013 ** allocation subsystem for use by SQLite.
000014 **
000015 ** This version of the memory allocation subsystem omits all
000016 ** use of malloc(). The application gives SQLite a block of memory
000017 ** before calling sqlite3_initialize() from which allocations
000018 ** are made and returned by the xMalloc() and xRealloc()
000019 ** implementations. Once sqlite3_initialize() has been called,
000020 ** the amount of memory available to SQLite is fixed and cannot
000021 ** be changed.
000022 **
000023 ** This version of the memory allocation subsystem is included
000024 ** in the build only if SQLITE_ENABLE_MEMSYS5 is defined.
000025 **
000026 ** This memory allocator uses the following algorithm:
000027 **
000028 ** 1. All memory allocation sizes are rounded up to a power of 2.
000029 **
000030 ** 2. If two adjacent free blocks are the halves of a larger block,
000031 ** then the two blocks are coalesced into the single larger block.
000032 **
000033 ** 3. New memory is allocated from the first available free block.
000034 **
000035 ** This algorithm is described in: J. M. Robson. "Bounds for Some Functions
000036 ** Concerning Dynamic Storage Allocation". Journal of the Association for
000037 ** Computing Machinery, Volume 21, Number 8, July 1974, pages 491-499.
000038 **
000039 ** Let n be the size of the largest allocation divided by the minimum
000040 ** allocation size (after rounding all sizes up to a power of 2.) Let M
000041 ** be the maximum amount of memory ever outstanding at one time. Let
000042 ** N be the total amount of memory available for allocation. Robson
000043 ** proved that this memory allocator will never breakdown due to
000044 ** fragmentation as long as the following constraint holds:
000045 **
000046 ** N >= M*(1 + log2(n)/2) - n + 1
000047 **
000048 ** The sqlite3_status() logic tracks the maximum values of n and M so
000049 ** that an application can, at any time, verify this constraint.
000050 */
000051 #include "sqliteInt.h"
000052
000053 /*
000054 ** This version of the memory allocator is used only when
000055 ** SQLITE_ENABLE_MEMSYS5 is defined.
000056 */
000057 #ifdef SQLITE_ENABLE_MEMSYS5
000058
000059 /*
000060 ** A minimum allocation is an instance of the following structure.
000061 ** Larger allocations are an array of these structures where the
000062 ** size of the array is a power of 2.
000063 **
000064 ** The size of this object must be a power of two. That fact is
000065 ** verified in memsys5Init().
000066 */
000067 typedef struct Mem5Link Mem5Link;
000068 struct Mem5Link {
000069 int next; /* Index of next free chunk */
000070 int prev; /* Index of previous free chunk */
000071 };
000072
000073 /*
000074 ** Maximum size of any allocation is ((1<<LOGMAX)*mem5.szAtom). Since
000075 ** mem5.szAtom is always at least 8 and 32-bit integers are used,
000076 ** it is not actually possible to reach this limit.
000077 */
000078 #define LOGMAX 30
000079
000080 /*
000081 ** Masks used for mem5.aCtrl[] elements.
000082 */
000083 #define CTRL_LOGSIZE 0x1f /* Log2 Size of this block */
000084 #define CTRL_FREE 0x20 /* True if not checked out */
000085
000086 /*
000087 ** All of the static variables used by this module are collected
000088 ** into a single structure named "mem5". This is to keep the
000089 ** static variables organized and to reduce namespace pollution
000090 ** when this module is combined with other in the amalgamation.
000091 */
000092 static SQLITE_WSD struct Mem5Global {
000093 /*
000094 ** Memory available for allocation
000095 */
000096 int szAtom; /* Smallest possible allocation in bytes */
000097 int nBlock; /* Number of szAtom sized blocks in zPool */
000098 u8 *zPool; /* Memory available to be allocated */
000099
000100 /*
000101 ** Mutex to control access to the memory allocation subsystem.
000102 */
000103 sqlite3_mutex *mutex;
000104
000105 #if defined(SQLITE_DEBUG) || defined(SQLITE_TEST)
000106 /*
000107 ** Performance statistics
000108 */
000109 u64 nAlloc; /* Total number of calls to malloc */
000110 u64 totalAlloc; /* Total of all malloc calls - includes internal frag */
000111 u64 totalExcess; /* Total internal fragmentation */
000112 u32 currentOut; /* Current checkout, including internal fragmentation */
000113 u32 currentCount; /* Current number of distinct checkouts */
000114 u32 maxOut; /* Maximum instantaneous currentOut */
000115 u32 maxCount; /* Maximum instantaneous currentCount */
000116 u32 maxRequest; /* Largest allocation (exclusive of internal frag) */
000117 #endif
000118
000119 /*
000120 ** Lists of free blocks. aiFreelist[0] is a list of free blocks of
000121 ** size mem5.szAtom. aiFreelist[1] holds blocks of size szAtom*2.
000122 ** aiFreelist[2] holds free blocks of size szAtom*4. And so forth.
000123 */
000124 int aiFreelist[LOGMAX+1];
000125
000126 /*
000127 ** Space for tracking which blocks are checked out and the size
000128 ** of each block. One byte per block.
000129 */
000130 u8 *aCtrl;
000131
000132 } mem5;
000133
000134 /*
000135 ** Access the static variable through a macro for SQLITE_OMIT_WSD.
000136 */
000137 #define mem5 GLOBAL(struct Mem5Global, mem5)
000138
000139 /*
000140 ** Assuming mem5.zPool is divided up into an array of Mem5Link
000141 ** structures, return a pointer to the idx-th such link.
000142 */
000143 #define MEM5LINK(idx) ((Mem5Link *)(&mem5.zPool[(idx)*mem5.szAtom]))
000144
000145 /*
000146 ** Unlink the chunk at mem5.aPool[i] from list it is currently
000147 ** on. It should be found on mem5.aiFreelist[iLogsize].
000148 */
000149 static void memsys5Unlink(int i, int iLogsize){
000150 int next, prev;
000151 assert( i>=0 && i<mem5.nBlock );
000152 assert( iLogsize>=0 && iLogsize<=LOGMAX );
000153 assert( (mem5.aCtrl[i] & CTRL_LOGSIZE)==iLogsize );
000154
000155 next = MEM5LINK(i)->next;
000156 prev = MEM5LINK(i)->prev;
000157 if( prev<0 ){
000158 mem5.aiFreelist[iLogsize] = next;
000159 }else{
000160 MEM5LINK(prev)->next = next;
000161 }
000162 if( next>=0 ){
000163 MEM5LINK(next)->prev = prev;
000164 }
000165 }
000166
000167 /*
000168 ** Link the chunk at mem5.aPool[i] so that is on the iLogsize
000169 ** free list.
000170 */
000171 static void memsys5Link(int i, int iLogsize){
000172 int x;
000173 assert( sqlite3_mutex_held(mem5.mutex) );
000174 assert( i>=0 && i<mem5.nBlock );
000175 assert( iLogsize>=0 && iLogsize<=LOGMAX );
000176 assert( (mem5.aCtrl[i] & CTRL_LOGSIZE)==iLogsize );
000177
000178 x = MEM5LINK(i)->next = mem5.aiFreelist[iLogsize];
000179 MEM5LINK(i)->prev = -1;
000180 if( x>=0 ){
000181 assert( x<mem5.nBlock );
000182 MEM5LINK(x)->prev = i;
000183 }
000184 mem5.aiFreelist[iLogsize] = i;
000185 }
000186
000187 /*
000188 ** Obtain or release the mutex needed to access global data structures.
000189 */
000190 static void memsys5Enter(void){
000191 sqlite3_mutex_enter(mem5.mutex);
000192 }
000193 static void memsys5Leave(void){
000194 sqlite3_mutex_leave(mem5.mutex);
000195 }
000196
000197 /*
000198 ** Return the size of an outstanding allocation, in bytes.
000199 ** This only works for chunks that are currently checked out.
000200 */
000201 static int memsys5Size(void *p){
000202 int iSize, i;
000203 assert( p!=0 );
000204 i = (int)(((u8 *)p-mem5.zPool)/mem5.szAtom);
000205 assert( i>=0 && i<mem5.nBlock );
000206 iSize = mem5.szAtom * (1 << (mem5.aCtrl[i]&CTRL_LOGSIZE));
000207 return iSize;
000208 }
000209
000210 /*
000211 ** Return a block of memory of at least nBytes in size.
000212 ** Return NULL if unable. Return NULL if nBytes==0.
000213 **
000214 ** The caller guarantees that nByte is positive.
000215 **
000216 ** The caller has obtained a mutex prior to invoking this
000217 ** routine so there is never any chance that two or more
000218 ** threads can be in this routine at the same time.
000219 */
000220 static void *memsys5MallocUnsafe(int nByte){
000221 int i; /* Index of a mem5.aPool[] slot */
000222 int iBin; /* Index into mem5.aiFreelist[] */
000223 int iFullSz; /* Size of allocation rounded up to power of 2 */
000224 int iLogsize; /* Log2 of iFullSz/POW2_MIN */
000225
000226 /* nByte must be a positive */
000227 assert( nByte>0 );
000228
000229 /* No more than 1GiB per allocation */
000230 if( nByte > 0x40000000 ) return 0;
000231
000232 #if defined(SQLITE_DEBUG) || defined(SQLITE_TEST)
000233 /* Keep track of the maximum allocation request. Even unfulfilled
000234 ** requests are counted */
000235 if( (u32)nByte>mem5.maxRequest ){
000236 mem5.maxRequest = nByte;
000237 }
000238 #endif
000239
000240
000241 /* Round nByte up to the next valid power of two */
000242 for(iFullSz=mem5.szAtom,iLogsize=0; iFullSz<nByte; iFullSz*=2,iLogsize++){}
000243
000244 /* Make sure mem5.aiFreelist[iLogsize] contains at least one free
000245 ** block. If not, then split a block of the next larger power of
000246 ** two in order to create a new free block of size iLogsize.
000247 */
000248 for(iBin=iLogsize; iBin<=LOGMAX && mem5.aiFreelist[iBin]<0; iBin++){}
000249 if( iBin>LOGMAX ){
000250 testcase( sqlite3GlobalConfig.xLog!=0 );
000251 sqlite3_log(SQLITE_NOMEM, "failed to allocate %u bytes", nByte);
000252 return 0;
000253 }
000254 i = mem5.aiFreelist[iBin];
000255 memsys5Unlink(i, iBin);
000256 while( iBin>iLogsize ){
000257 int newSize;
000258
000259 iBin--;
000260 newSize = 1 << iBin;
000261 mem5.aCtrl[i+newSize] = CTRL_FREE | iBin;
000262 memsys5Link(i+newSize, iBin);
000263 }
000264 mem5.aCtrl[i] = iLogsize;
000265
000266 #if defined(SQLITE_DEBUG) || defined(SQLITE_TEST)
000267 /* Update allocator performance statistics. */
000268 mem5.nAlloc++;
000269 mem5.totalAlloc += iFullSz;
000270 mem5.totalExcess += iFullSz - nByte;
000271 mem5.currentCount++;
000272 mem5.currentOut += iFullSz;
000273 if( mem5.maxCount<mem5.currentCount ) mem5.maxCount = mem5.currentCount;
000274 if( mem5.maxOut<mem5.currentOut ) mem5.maxOut = mem5.currentOut;
000275 #endif
000276
000277 #ifdef SQLITE_DEBUG
000278 /* Make sure the allocated memory does not assume that it is set to zero
000279 ** or retains a value from a previous allocation */
000280 memset(&mem5.zPool[i*mem5.szAtom], 0xAA, iFullSz);
000281 #endif
000282
000283 /* Return a pointer to the allocated memory. */
000284 return (void*)&mem5.zPool[i*mem5.szAtom];
000285 }
000286
000287 /*
000288 ** Free an outstanding memory allocation.
000289 */
000290 static void memsys5FreeUnsafe(void *pOld){
000291 u32 size, iLogsize;
000292 int iBlock;
000293
000294 /* Set iBlock to the index of the block pointed to by pOld in
000295 ** the array of mem5.szAtom byte blocks pointed to by mem5.zPool.
000296 */
000297 iBlock = (int)(((u8 *)pOld-mem5.zPool)/mem5.szAtom);
000298
000299 /* Check that the pointer pOld points to a valid, non-free block. */
000300 assert( iBlock>=0 && iBlock<mem5.nBlock );
000301 assert( ((u8 *)pOld-mem5.zPool)%mem5.szAtom==0 );
000302 assert( (mem5.aCtrl[iBlock] & CTRL_FREE)==0 );
000303
000304 iLogsize = mem5.aCtrl[iBlock] & CTRL_LOGSIZE;
000305 size = 1<<iLogsize;
000306 assert( iBlock+size-1<(u32)mem5.nBlock );
000307
000308 mem5.aCtrl[iBlock] |= CTRL_FREE;
000309 mem5.aCtrl[iBlock+size-1] |= CTRL_FREE;
000310
000311 #if defined(SQLITE_DEBUG) || defined(SQLITE_TEST)
000312 assert( mem5.currentCount>0 );
000313 assert( mem5.currentOut>=(size*mem5.szAtom) );
000314 mem5.currentCount--;
000315 mem5.currentOut -= size*mem5.szAtom;
000316 assert( mem5.currentOut>0 || mem5.currentCount==0 );
000317 assert( mem5.currentCount>0 || mem5.currentOut==0 );
000318 #endif
000319
000320 mem5.aCtrl[iBlock] = CTRL_FREE | iLogsize;
000321 while( ALWAYS(iLogsize<LOGMAX) ){
000322 int iBuddy;
000323 if( (iBlock>>iLogsize) & 1 ){
000324 iBuddy = iBlock - size;
000325 assert( iBuddy>=0 );
000326 }else{
000327 iBuddy = iBlock + size;
000328 if( iBuddy>=mem5.nBlock ) break;
000329 }
000330 if( mem5.aCtrl[iBuddy]!=(CTRL_FREE | iLogsize) ) break;
000331 memsys5Unlink(iBuddy, iLogsize);
000332 iLogsize++;
000333 if( iBuddy<iBlock ){
000334 mem5.aCtrl[iBuddy] = CTRL_FREE | iLogsize;
000335 mem5.aCtrl[iBlock] = 0;
000336 iBlock = iBuddy;
000337 }else{
000338 mem5.aCtrl[iBlock] = CTRL_FREE | iLogsize;
000339 mem5.aCtrl[iBuddy] = 0;
000340 }
000341 size *= 2;
000342 }
000343
000344 #ifdef SQLITE_DEBUG
000345 /* Overwrite freed memory with the 0x55 bit pattern to verify that it is
000346 ** not used after being freed */
000347 memset(&mem5.zPool[iBlock*mem5.szAtom], 0x55, size);
000348 #endif
000349
000350 memsys5Link(iBlock, iLogsize);
000351 }
000352
000353 /*
000354 ** Allocate nBytes of memory.
000355 */
000356 static void *memsys5Malloc(int nBytes){
000357 sqlite3_int64 *p = 0;
000358 if( nBytes>0 ){
000359 memsys5Enter();
000360 p = memsys5MallocUnsafe(nBytes);
000361 memsys5Leave();
000362 }
000363 return (void*)p;
000364 }
000365
000366 /*
000367 ** Free memory.
000368 **
000369 ** The outer layer memory allocator prevents this routine from
000370 ** being called with pPrior==0.
000371 */
000372 static void memsys5Free(void *pPrior){
000373 assert( pPrior!=0 );
000374 memsys5Enter();
000375 memsys5FreeUnsafe(pPrior);
000376 memsys5Leave();
000377 }
000378
000379 /*
000380 ** Change the size of an existing memory allocation.
000381 **
000382 ** The outer layer memory allocator prevents this routine from
000383 ** being called with pPrior==0.
000384 **
000385 ** nBytes is always a value obtained from a prior call to
000386 ** memsys5Round(). Hence nBytes is always a non-negative power
000387 ** of two. If nBytes==0 that means that an oversize allocation
000388 ** (an allocation larger than 0x40000000) was requested and this
000389 ** routine should return 0 without freeing pPrior.
000390 */
000391 static void *memsys5Realloc(void *pPrior, int nBytes){
000392 int nOld;
000393 void *p;
000394 assert( pPrior!=0 );
000395 assert( (nBytes&(nBytes-1))==0 ); /* EV: R-46199-30249 */
000396 assert( nBytes>=0 );
000397 if( nBytes==0 ){
000398 return 0;
000399 }
000400 nOld = memsys5Size(pPrior);
000401 if( nBytes<=nOld ){
000402 return pPrior;
000403 }
000404 p = memsys5Malloc(nBytes);
000405 if( p ){
000406 memcpy(p, pPrior, nOld);
000407 memsys5Free(pPrior);
000408 }
000409 return p;
000410 }
000411
000412 /*
000413 ** Round up a request size to the next valid allocation size. If
000414 ** the allocation is too large to be handled by this allocation system,
000415 ** return 0.
000416 **
000417 ** All allocations must be a power of two and must be expressed by a
000418 ** 32-bit signed integer. Hence the largest allocation is 0x40000000
000419 ** or 1073741824 bytes.
000420 */
000421 static int memsys5Roundup(int n){
000422 int iFullSz;
000423 if( n<=mem5.szAtom*2 ){
000424 if( n<=mem5.szAtom ) return mem5.szAtom;
000425 return mem5.szAtom*2;
000426 }
000427 if( n>0x10000000 ){
000428 if( n>0x40000000 ) return 0;
000429 if( n>0x20000000 ) return 0x40000000;
000430 return 0x20000000;
000431 }
000432 for(iFullSz=mem5.szAtom*8; iFullSz<n; iFullSz *= 4);
000433 if( (iFullSz/2)>=(i64)n ) return iFullSz/2;
000434 return iFullSz;
000435 }
000436
000437 /*
000438 ** Return the ceiling of the logarithm base 2 of iValue.
000439 **
000440 ** Examples: memsys5Log(1) -> 0
000441 ** memsys5Log(2) -> 1
000442 ** memsys5Log(4) -> 2
000443 ** memsys5Log(5) -> 3
000444 ** memsys5Log(8) -> 3
000445 ** memsys5Log(9) -> 4
000446 */
000447 static int memsys5Log(int iValue){
000448 int iLog;
000449 for(iLog=0; (iLog<(int)((sizeof(int)*8)-1)) && (1<<iLog)<iValue; iLog++);
000450 return iLog;
000451 }
000452
000453 /*
000454 ** Initialize the memory allocator.
000455 **
000456 ** This routine is not threadsafe. The caller must be holding a mutex
000457 ** to prevent multiple threads from entering at the same time.
000458 */
000459 static int memsys5Init(void *NotUsed){
000460 int ii; /* Loop counter */
000461 int nByte; /* Number of bytes of memory available to this allocator */
000462 u8 *zByte; /* Memory usable by this allocator */
000463 int nMinLog; /* Log base 2 of minimum allocation size in bytes */
000464 int iOffset; /* An offset into mem5.aCtrl[] */
000465
000466 UNUSED_PARAMETER(NotUsed);
000467
000468 /* For the purposes of this routine, disable the mutex */
000469 mem5.mutex = 0;
000470
000471 /* The size of a Mem5Link object must be a power of two. Verify that
000472 ** this is case.
000473 */
000474 assert( (sizeof(Mem5Link)&(sizeof(Mem5Link)-1))==0 );
000475
000476 nByte = sqlite3GlobalConfig.nHeap;
000477 zByte = (u8*)sqlite3GlobalConfig.pHeap;
000478 assert( zByte!=0 ); /* sqlite3_config() does not allow otherwise */
000479
000480 /* boundaries on sqlite3GlobalConfig.mnReq are enforced in sqlite3_config() */
000481 nMinLog = memsys5Log(sqlite3GlobalConfig.mnReq);
000482 mem5.szAtom = (1<<nMinLog);
000483 while( (int)sizeof(Mem5Link)>mem5.szAtom ){
000484 mem5.szAtom = mem5.szAtom << 1;
000485 }
000486
000487 mem5.nBlock = (nByte / (mem5.szAtom+sizeof(u8)));
000488 mem5.zPool = zByte;
000489 mem5.aCtrl = (u8 *)&mem5.zPool[mem5.nBlock*mem5.szAtom];
000490
000491 for(ii=0; ii<=LOGMAX; ii++){
000492 mem5.aiFreelist[ii] = -1;
000493 }
000494
000495 iOffset = 0;
000496 for(ii=LOGMAX; ii>=0; ii--){
000497 int nAlloc = (1<<ii);
000498 if( (iOffset+nAlloc)<=mem5.nBlock ){
000499 mem5.aCtrl[iOffset] = ii | CTRL_FREE;
000500 memsys5Link(iOffset, ii);
000501 iOffset += nAlloc;
000502 }
000503 assert((iOffset+nAlloc)>mem5.nBlock);
000504 }
000505
000506 /* If a mutex is required for normal operation, allocate one */
000507 if( sqlite3GlobalConfig.bMemstat==0 ){
000508 mem5.mutex = sqlite3MutexAlloc(SQLITE_MUTEX_STATIC_MEM);
000509 }
000510
000511 return SQLITE_OK;
000512 }
000513
000514 /*
000515 ** Deinitialize this module.
000516 */
000517 static void memsys5Shutdown(void *NotUsed){
000518 UNUSED_PARAMETER(NotUsed);
000519 mem5.mutex = 0;
000520 return;
000521 }
000522
000523 #ifdef SQLITE_TEST
000524 /*
000525 ** Open the file indicated and write a log of all unfreed memory
000526 ** allocations into that log.
000527 */
000528 void sqlite3Memsys5Dump(const char *zFilename){
000529 FILE *out;
000530 int i, j, n;
000531 int nMinLog;
000532
000533 if( zFilename==0 || zFilename[0]==0 ){
000534 out = stdout;
000535 }else{
000536 out = fopen(zFilename, "w");
000537 if( out==0 ){
000538 fprintf(stderr, "** Unable to output memory debug output log: %s **\n",
000539 zFilename);
000540 return;
000541 }
000542 }
000543 memsys5Enter();
000544 nMinLog = memsys5Log(mem5.szAtom);
000545 for(i=0; i<=LOGMAX && i+nMinLog<32; i++){
000546 for(n=0, j=mem5.aiFreelist[i]; j>=0; j = MEM5LINK(j)->next, n++){}
000547 fprintf(out, "freelist items of size %d: %d\n", mem5.szAtom << i, n);
000548 }
000549 fprintf(out, "mem5.nAlloc = %llu\n", mem5.nAlloc);
000550 fprintf(out, "mem5.totalAlloc = %llu\n", mem5.totalAlloc);
000551 fprintf(out, "mem5.totalExcess = %llu\n", mem5.totalExcess);
000552 fprintf(out, "mem5.currentOut = %u\n", mem5.currentOut);
000553 fprintf(out, "mem5.currentCount = %u\n", mem5.currentCount);
000554 fprintf(out, "mem5.maxOut = %u\n", mem5.maxOut);
000555 fprintf(out, "mem5.maxCount = %u\n", mem5.maxCount);
000556 fprintf(out, "mem5.maxRequest = %u\n", mem5.maxRequest);
000557 memsys5Leave();
000558 if( out==stdout ){
000559 fflush(stdout);
000560 }else{
000561 fclose(out);
000562 }
000563 }
000564 #endif
000565
000566 /*
000567 ** This routine is the only routine in this file with external
000568 ** linkage. It returns a pointer to a static sqlite3_mem_methods
000569 ** struct populated with the memsys5 methods.
000570 */
000571 const sqlite3_mem_methods *sqlite3MemGetMemsys5(void){
000572 static const sqlite3_mem_methods memsys5Methods = {
000573 memsys5Malloc,
000574 memsys5Free,
000575 memsys5Realloc,
000576 memsys5Size,
000577 memsys5Roundup,
000578 memsys5Init,
000579 memsys5Shutdown,
000580 0
000581 };
000582 return &memsys5Methods;
000583 }
000584
000585 #endif /* SQLITE_ENABLE_MEMSYS5 */