00001 /* 00002 ** 2007 October 14 00003 ** 00004 ** The author disclaims copyright to this source code. In place of 00005 ** a legal notice, here is a blessing: 00006 ** 00007 ** May you do good and not evil. 00008 ** May you find forgiveness for yourself and forgive others. 00009 ** May you share freely, never taking more than you give. 00010 ** 00011 ************************************************************************* 00012 ** This file contains the C functions that implement a memory 00013 ** allocation subsystem for use by SQLite. 00014 ** 00015 ** This version of the memory allocation subsystem omits all 00016 ** use of malloc(). The SQLite user supplies a block of memory 00017 ** before calling sqlite3_initialize() from which allocations 00018 ** are made and returned by the xMalloc() and xRealloc() 00019 ** implementations. Once sqlite3_initialize() has been called, 00020 ** the amount of memory available to SQLite is fixed and cannot 00021 ** be changed. 00022 ** 00023 ** This version of the memory allocation subsystem is included 00024 ** in the build only if SQLITE_ENABLE_MEMSYS5 is defined. 00025 ** 00026 ** $Id: mem5.c,v 1.15 2008/10/28 18:58:20 drh Exp $ 00027 */ 00028 #include "sqliteInt.h" 00029 00030 /* 00031 ** This version of the memory allocator is used only when 00032 ** SQLITE_ENABLE_MEMSYS5 is defined. 00033 */ 00034 #ifdef SQLITE_ENABLE_MEMSYS5 00035 00036 /* 00037 ** A minimum allocation is an instance of the following structure. 00038 ** Larger allocations are an array of these structures where the 00039 ** size of the array is a power of 2. 00040 */ 00041 typedef struct Mem5Link Mem5Link; 00042 struct Mem5Link { 00043 int next; /* Index of next free chunk */ 00044 int prev; /* Index of previous free chunk */ 00045 }; 00046 00047 /* 00048 ** Maximum size of any allocation is ((1<<LOGMAX)*mem5.nAtom). Since 00049 ** mem5.nAtom is always at least 8, this is not really a practical 00050 ** limitation. 00051 */ 00052 #define LOGMAX 30 00053 00054 /* 00055 ** Masks used for mem5.aCtrl[] elements. 00056 */ 00057 #define CTRL_LOGSIZE 0x1f /* Log2 Size of this block relative to POW2_MIN */ 00058 #define CTRL_FREE 0x20 /* True if not checked out */ 00059 00060 /* 00061 ** All of the static variables used by this module are collected 00062 ** into a single structure named "mem5". This is to keep the 00063 ** static variables organized and to reduce namespace pollution 00064 ** when this module is combined with other in the amalgamation. 00065 */ 00066 static SQLITE_WSD struct Mem5Global { 00067 /* 00068 ** Memory available for allocation 00069 */ 00070 int nAtom; /* Smallest possible allocation in bytes */ 00071 int nBlock; /* Number of nAtom sized blocks in zPool */ 00072 u8 *zPool; 00073 00074 /* 00075 ** Mutex to control access to the memory allocation subsystem. 00076 */ 00077 sqlite3_mutex *mutex; 00078 00079 /* 00080 ** Performance statistics 00081 */ 00082 u64 nAlloc; /* Total number of calls to malloc */ 00083 u64 totalAlloc; /* Total of all malloc calls - includes internal frag */ 00084 u64 totalExcess; /* Total internal fragmentation */ 00085 u32 currentOut; /* Current checkout, including internal fragmentation */ 00086 u32 currentCount; /* Current number of distinct checkouts */ 00087 u32 maxOut; /* Maximum instantaneous currentOut */ 00088 u32 maxCount; /* Maximum instantaneous currentCount */ 00089 u32 maxRequest; /* Largest allocation (exclusive of internal frag) */ 00090 00091 /* 00092 ** Lists of free blocks of various sizes. 00093 */ 00094 int aiFreelist[LOGMAX+1]; 00095 00096 /* 00097 ** Space for tracking which blocks are checked out and the size 00098 ** of each block. One byte per block. 00099 */ 00100 u8 *aCtrl; 00101 00102 } mem5 = { 19804167 }; 00103 00104 #define mem5 GLOBAL(struct Mem5Global, mem5) 00105 00106 #define MEM5LINK(idx) ((Mem5Link *)(&mem5.zPool[(idx)*mem5.nAtom])) 00107 00108 /* 00109 ** Unlink the chunk at mem5.aPool[i] from list it is currently 00110 ** on. It should be found on mem5.aiFreelist[iLogsize]. 00111 */ 00112 static void memsys5Unlink(int i, int iLogsize){ 00113 int next, prev; 00114 assert( i>=0 && i<mem5.nBlock ); 00115 assert( iLogsize>=0 && iLogsize<=LOGMAX ); 00116 assert( (mem5.aCtrl[i] & CTRL_LOGSIZE)==iLogsize ); 00117 00118 next = MEM5LINK(i)->next; 00119 prev = MEM5LINK(i)->prev; 00120 if( prev<0 ){ 00121 mem5.aiFreelist[iLogsize] = next; 00122 }else{ 00123 MEM5LINK(prev)->next = next; 00124 } 00125 if( next>=0 ){ 00126 MEM5LINK(next)->prev = prev; 00127 } 00128 } 00129 00130 /* 00131 ** Link the chunk at mem5.aPool[i] so that is on the iLogsize 00132 ** free list. 00133 */ 00134 static void memsys5Link(int i, int iLogsize){ 00135 int x; 00136 assert( sqlite3_mutex_held(mem5.mutex) ); 00137 assert( i>=0 && i<mem5.nBlock ); 00138 assert( iLogsize>=0 && iLogsize<=LOGMAX ); 00139 assert( (mem5.aCtrl[i] & CTRL_LOGSIZE)==iLogsize ); 00140 00141 x = MEM5LINK(i)->next = mem5.aiFreelist[iLogsize]; 00142 MEM5LINK(i)->prev = -1; 00143 if( x>=0 ){ 00144 assert( x<mem5.nBlock ); 00145 MEM5LINK(x)->prev = i; 00146 } 00147 mem5.aiFreelist[iLogsize] = i; 00148 } 00149 00150 /* 00151 ** If the STATIC_MEM mutex is not already held, obtain it now. The mutex 00152 ** will already be held (obtained by code in malloc.c) if 00153 ** sqlite3GlobalConfig.bMemStat is true. 00154 */ 00155 static void memsys5Enter(void){ 00156 if( sqlite3GlobalConfig.bMemstat==0 && mem5.mutex==0 ){ 00157 mem5.mutex = sqlite3MutexAlloc(SQLITE_MUTEX_STATIC_MEM); 00158 } 00159 sqlite3_mutex_enter(mem5.mutex); 00160 } 00161 static void memsys5Leave(void){ 00162 sqlite3_mutex_leave(mem5.mutex); 00163 } 00164 00165 /* 00166 ** Return the size of an outstanding allocation, in bytes. The 00167 ** size returned omits the 8-byte header overhead. This only 00168 ** works for chunks that are currently checked out. 00169 */ 00170 static int memsys5Size(void *p){ 00171 int iSize = 0; 00172 if( p ){ 00173 int i = ((u8 *)p-mem5.zPool)/mem5.nAtom; 00174 assert( i>=0 && i<mem5.nBlock ); 00175 iSize = mem5.nAtom * (1 << (mem5.aCtrl[i]&CTRL_LOGSIZE)); 00176 } 00177 return iSize; 00178 } 00179 00180 /* 00181 ** Find the first entry on the freelist iLogsize. Unlink that 00182 ** entry and return its index. 00183 */ 00184 static int memsys5UnlinkFirst(int iLogsize){ 00185 int i; 00186 int iFirst; 00187 00188 assert( iLogsize>=0 && iLogsize<=LOGMAX ); 00189 i = iFirst = mem5.aiFreelist[iLogsize]; 00190 assert( iFirst>=0 ); 00191 while( i>0 ){ 00192 if( i<iFirst ) iFirst = i; 00193 i = MEM5LINK(i)->next; 00194 } 00195 memsys5Unlink(iFirst, iLogsize); 00196 return iFirst; 00197 } 00198 00199 /* 00200 ** Return a block of memory of at least nBytes in size. 00201 ** Return NULL if unable. 00202 */ 00203 static void *memsys5MallocUnsafe(int nByte){ 00204 int i; /* Index of a mem5.aPool[] slot */ 00205 int iBin; /* Index into mem5.aiFreelist[] */ 00206 int iFullSz; /* Size of allocation rounded up to power of 2 */ 00207 int iLogsize; /* Log2 of iFullSz/POW2_MIN */ 00208 00209 /* Keep track of the maximum allocation request. Even unfulfilled 00210 ** requests are counted */ 00211 if( nByte>mem5.maxRequest ){ 00212 mem5.maxRequest = nByte; 00213 } 00214 00215 /* Round nByte up to the next valid power of two */ 00216 if( nByte>POW2_MAX ) return 0; 00217 for(iFullSz=mem5.nAtom, iLogsize=0; iFullSz<nByte; iFullSz *= 2, iLogsize++){} 00218 00219 /* Make sure mem5.aiFreelist[iLogsize] contains at least one free 00220 ** block. If not, then split a block of the next larger power of 00221 ** two in order to create a new free block of size iLogsize. 00222 */ 00223 for(iBin=iLogsize; mem5.aiFreelist[iBin]<0 && iBin<=LOGMAX; iBin++){} 00224 if( iBin>LOGMAX ) return 0; 00225 i = memsys5UnlinkFirst(iBin); 00226 while( iBin>iLogsize ){ 00227 int newSize; 00228 00229 iBin--; 00230 newSize = 1 << iBin; 00231 mem5.aCtrl[i+newSize] = CTRL_FREE | iBin; 00232 memsys5Link(i+newSize, iBin); 00233 } 00234 mem5.aCtrl[i] = iLogsize; 00235 00236 /* Update allocator performance statistics. */ 00237 mem5.nAlloc++; 00238 mem5.totalAlloc += iFullSz; 00239 mem5.totalExcess += iFullSz - nByte; 00240 mem5.currentCount++; 00241 mem5.currentOut += iFullSz; 00242 if( mem5.maxCount<mem5.currentCount ) mem5.maxCount = mem5.currentCount; 00243 if( mem5.maxOut<mem5.currentOut ) mem5.maxOut = mem5.currentOut; 00244 00245 /* Return a pointer to the allocated memory. */ 00246 return (void*)&mem5.zPool[i*mem5.nAtom]; 00247 } 00248 00249 /* 00250 ** Free an outstanding memory allocation. 00251 */ 00252 static void memsys5FreeUnsafe(void *pOld){ 00253 u32 size, iLogsize; 00254 int iBlock; 00255 00256 /* Set iBlock to the index of the block pointed to by pOld in 00257 ** the array of mem5.nAtom byte blocks pointed to by mem5.zPool. 00258 */ 00259 iBlock = ((u8 *)pOld-mem5.zPool)/mem5.nAtom; 00260 00261 /* Check that the pointer pOld points to a valid, non-free block. */ 00262 assert( iBlock>=0 && iBlock<mem5.nBlock ); 00263 assert( ((u8 *)pOld-mem5.zPool)%mem5.nAtom==0 ); 00264 assert( (mem5.aCtrl[iBlock] & CTRL_FREE)==0 ); 00265 00266 iLogsize = mem5.aCtrl[iBlock] & CTRL_LOGSIZE; 00267 size = 1<<iLogsize; 00268 assert( iBlock+size-1<mem5.nBlock ); 00269 00270 mem5.aCtrl[iBlock] |= CTRL_FREE; 00271 mem5.aCtrl[iBlock+size-1] |= CTRL_FREE; 00272 assert( mem5.currentCount>0 ); 00273 assert( mem5.currentOut>=0 ); 00274 mem5.currentCount--; 00275 mem5.currentOut -= size*mem5.nAtom; 00276 assert( mem5.currentOut>0 || mem5.currentCount==0 ); 00277 assert( mem5.currentCount>0 || mem5.currentOut==0 ); 00278 00279 mem5.aCtrl[iBlock] = CTRL_FREE | iLogsize; 00280 while( iLogsize<LOGMAX ){ 00281 int iBuddy; 00282 if( (iBlock>>iLogsize) & 1 ){ 00283 iBuddy = iBlock - size; 00284 }else{ 00285 iBuddy = iBlock + size; 00286 } 00287 assert( iBuddy>=0 ); 00288 if( (iBuddy+(1<<iLogsize))>mem5.nBlock ) break; 00289 if( mem5.aCtrl[iBuddy]!=(CTRL_FREE | iLogsize) ) break; 00290 memsys5Unlink(iBuddy, iLogsize); 00291 iLogsize++; 00292 if( iBuddy<iBlock ){ 00293 mem5.aCtrl[iBuddy] = CTRL_FREE | iLogsize; 00294 mem5.aCtrl[iBlock] = 0; 00295 iBlock = iBuddy; 00296 }else{ 00297 mem5.aCtrl[iBlock] = CTRL_FREE | iLogsize; 00298 mem5.aCtrl[iBuddy] = 0; 00299 } 00300 size *= 2; 00301 } 00302 memsys5Link(iBlock, iLogsize); 00303 } 00304 00305 /* 00306 ** Allocate nBytes of memory 00307 */ 00308 static void *memsys5Malloc(int nBytes){ 00309 sqlite3_int64 *p = 0; 00310 if( nBytes>0 ){ 00311 memsys5Enter(); 00312 p = memsys5MallocUnsafe(nBytes); 00313 memsys5Leave(); 00314 } 00315 return (void*)p; 00316 } 00317 00318 /* 00319 ** Free memory. 00320 */ 00321 static void memsys5Free(void *pPrior){ 00322 if( pPrior==0 ){ 00323 assert(0); 00324 return; 00325 } 00326 memsys5Enter(); 00327 memsys5FreeUnsafe(pPrior); 00328 memsys5Leave(); 00329 } 00330 00331 /* 00332 ** Change the size of an existing memory allocation 00333 */ 00334 static void *memsys5Realloc(void *pPrior, int nBytes){ 00335 int nOld; 00336 void *p; 00337 if( pPrior==0 ){ 00338 return memsys5Malloc(nBytes); 00339 } 00340 if( nBytes<=0 ){ 00341 memsys5Free(pPrior); 00342 return 0; 00343 } 00344 nOld = memsys5Size(pPrior); 00345 if( nBytes<=nOld ){ 00346 return pPrior; 00347 } 00348 memsys5Enter(); 00349 p = memsys5MallocUnsafe(nBytes); 00350 if( p ){ 00351 memcpy(p, pPrior, nOld); 00352 memsys5FreeUnsafe(pPrior); 00353 } 00354 memsys5Leave(); 00355 return p; 00356 } 00357 00358 /* 00359 ** Round up a request size to the next valid allocation size. 00360 */ 00361 static int memsys5Roundup(int n){ 00362 int iFullSz; 00363 for(iFullSz=mem5.nAtom; iFullSz<n; iFullSz *= 2); 00364 return iFullSz; 00365 } 00366 00367 static int memsys5Log(int iValue){ 00368 int iLog; 00369 for(iLog=0; (1<<iLog)<iValue; iLog++); 00370 return iLog; 00371 } 00372 00373 /* 00374 ** Initialize this module. 00375 */ 00376 static int memsys5Init(void *NotUsed){ 00377 int ii; 00378 int nByte = sqlite3GlobalConfig.nHeap; 00379 u8 *zByte = (u8 *)sqlite3GlobalConfig.pHeap; 00380 int nMinLog; /* Log of minimum allocation size in bytes*/ 00381 int iOffset; 00382 00383 if( !zByte ){ 00384 return SQLITE_ERROR; 00385 } 00386 00387 nMinLog = memsys5Log(sqlite3GlobalConfig.mnReq); 00388 mem5.nAtom = (1<<nMinLog); 00389 while( sizeof(Mem5Link)>mem5.nAtom ){ 00390 mem5.nAtom = mem5.nAtom << 1; 00391 } 00392 00393 mem5.nBlock = (nByte / (mem5.nAtom+sizeof(u8))); 00394 mem5.zPool = zByte; 00395 mem5.aCtrl = (u8 *)&mem5.zPool[mem5.nBlock*mem5.nAtom]; 00396 00397 for(ii=0; ii<=LOGMAX; ii++){ 00398 mem5.aiFreelist[ii] = -1; 00399 } 00400 00401 iOffset = 0; 00402 for(ii=LOGMAX; ii>=0; ii--){ 00403 int nAlloc = (1<<ii); 00404 if( (iOffset+nAlloc)<=mem5.nBlock ){ 00405 mem5.aCtrl[iOffset] = ii | CTRL_FREE; 00406 memsys5Link(iOffset, ii); 00407 iOffset += nAlloc; 00408 } 00409 assert((iOffset+nAlloc)>mem5.nBlock); 00410 } 00411 00412 return SQLITE_OK; 00413 } 00414 00415 /* 00416 ** Deinitialize this module. 00417 */ 00418 static void memsys5Shutdown(void *NotUsed){ 00419 return; 00420 } 00421 00422 /* 00423 ** Open the file indicated and write a log of all unfreed memory 00424 ** allocations into that log. 00425 */ 00426 void sqlite3Memsys5Dump(const char *zFilename){ 00427 #ifdef SQLITE_DEBUG 00428 FILE *out; 00429 int i, j, n; 00430 int nMinLog; 00431 00432 if( zFilename==0 || zFilename[0]==0 ){ 00433 out = stdout; 00434 }else{ 00435 out = fopen(zFilename, "w"); 00436 if( out==0 ){ 00437 fprintf(stderr, "** Unable to output memory debug output log: %s **\n", 00438 zFilename); 00439 return; 00440 } 00441 } 00442 memsys5Enter(); 00443 nMinLog = memsys5Log(mem5.nAtom); 00444 for(i=0; i<=LOGMAX && i+nMinLog<32; i++){ 00445 for(n=0, j=mem5.aiFreelist[i]; j>=0; j = MEM5LINK(j)->next, n++){} 00446 fprintf(out, "freelist items of size %d: %d\n", mem5.nAtom << i, n); 00447 } 00448 fprintf(out, "mem5.nAlloc = %llu\n", mem5.nAlloc); 00449 fprintf(out, "mem5.totalAlloc = %llu\n", mem5.totalAlloc); 00450 fprintf(out, "mem5.totalExcess = %llu\n", mem5.totalExcess); 00451 fprintf(out, "mem5.currentOut = %u\n", mem5.currentOut); 00452 fprintf(out, "mem5.currentCount = %u\n", mem5.currentCount); 00453 fprintf(out, "mem5.maxOut = %u\n", mem5.maxOut); 00454 fprintf(out, "mem5.maxCount = %u\n", mem5.maxCount); 00455 fprintf(out, "mem5.maxRequest = %u\n", mem5.maxRequest); 00456 memsys5Leave(); 00457 if( out==stdout ){ 00458 fflush(stdout); 00459 }else{ 00460 fclose(out); 00461 } 00462 #endif 00463 } 00464 00465 /* 00466 ** This routine is the only routine in this file with external 00467 ** linkage. It returns a pointer to a static sqlite3_mem_methods 00468 ** struct populated with the memsys5 methods. 00469 */ 00470 const sqlite3_mem_methods *sqlite3MemGetMemsys5(void){ 00471 static const sqlite3_mem_methods memsys5Methods = { 00472 memsys5Malloc, 00473 memsys5Free, 00474 memsys5Realloc, 00475 memsys5Size, 00476 memsys5Roundup, 00477 memsys5Init, 00478 memsys5Shutdown, 00479 0 00480 }; 00481 return &memsys5Methods; 00482 } 00483 00484 #endif /* SQLITE_ENABLE_MEMSYS5 */
ContextLogger2—ContextLogger2 Logger Daemon Internals—Generated on Mon May 2 13:49:55 2011 by Doxygen 1.6.1