1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/os/persistentdata/persistentstorage/sql/SQLite364/mem5.c Fri Jun 15 03:10:57 2012 +0200
1.3 @@ -0,0 +1,506 @@
1.4 +/*
1.5 +** 2007 October 14
1.6 +**
1.7 +** The author disclaims copyright to this source code. In place of
1.8 +** a legal notice, here is a blessing:
1.9 +**
1.10 +** May you do good and not evil.
1.11 +** May you find forgiveness for yourself and forgive others.
1.12 +** May you share freely, never taking more than you give.
1.13 +**
1.14 +*************************************************************************
1.15 +** This file contains the C functions that implement a memory
1.16 +** allocation subsystem for use by SQLite.
1.17 +**
1.18 +** This version of the memory allocation subsystem omits all
1.19 +** use of malloc(). The SQLite user supplies a block of memory
1.20 +** before calling sqlite3_initialize() from which allocations
1.21 +** are made and returned by the xMalloc() and xRealloc()
1.22 +** implementations. Once sqlite3_initialize() has been called,
1.23 +** the amount of memory available to SQLite is fixed and cannot
1.24 +** be changed.
1.25 +**
1.26 +** This version of the memory allocation subsystem is included
1.27 +** in the build only if SQLITE_ENABLE_MEMSYS5 is defined.
1.28 +**
1.29 +** $Id: mem5.c,v 1.14 2008/09/02 17:52:52 danielk1977 Exp $
1.30 +*/
1.31 +#include "sqliteInt.h"
1.32 +
1.33 +/*
1.34 +** This version of the memory allocator is used only when
1.35 +** SQLITE_POW2_MEMORY_SIZE is defined.
1.36 +*/
1.37 +#ifdef SQLITE_ENABLE_MEMSYS5
1.38 +
1.39 +/*
1.40 +** Log2 of the minimum size of an allocation. For example, if
1.41 +** 4 then all allocations will be rounded up to at least 16 bytes.
1.42 +** If 5 then all allocations will be rounded up to at least 32 bytes.
1.43 +*/
1.44 +#ifndef SQLITE_POW2_LOGMIN
1.45 +# define SQLITE_POW2_LOGMIN 6
1.46 +#endif
1.47 +
1.48 +/*
1.49 +** Log2 of the maximum size of an allocation.
1.50 +*/
1.51 +#ifndef SQLITE_POW2_LOGMAX
1.52 +# define SQLITE_POW2_LOGMAX 20
1.53 +#endif
1.54 +#define POW2_MAX (((unsigned int)1)<<SQLITE_POW2_LOGMAX)
1.55 +
1.56 +/*
1.57 +** Number of distinct allocation sizes.
1.58 +*/
1.59 +#define NSIZE (SQLITE_POW2_LOGMAX - SQLITE_POW2_LOGMIN + 1)
1.60 +
1.61 +/*
1.62 +** A minimum allocation is an instance of the following structure.
1.63 +** Larger allocations are an array of these structures where the
1.64 +** size of the array is a power of 2.
1.65 +*/
1.66 +typedef struct Mem5Link Mem5Link;
1.67 +struct Mem5Link {
1.68 + int next; /* Index of next free chunk */
1.69 + int prev; /* Index of previous free chunk */
1.70 +};
1.71 +
1.72 +/*
1.73 +** Maximum size of any allocation is ((1<<LOGMAX)*mem5.nAtom). Since
1.74 +** mem5.nAtom is always at least 8, this is not really a practical
1.75 +** limitation.
1.76 +*/
1.77 +#define LOGMAX 30
1.78 +
1.79 +/*
1.80 +** Masks used for mem5.aCtrl[] elements.
1.81 +*/
1.82 +#define CTRL_LOGSIZE 0x1f /* Log2 Size of this block relative to POW2_MIN */
1.83 +#define CTRL_FREE 0x20 /* True if not checked out */
1.84 +
1.85 +/*
1.86 +** All of the static variables used by this module are collected
1.87 +** into a single structure named "mem5". This is to keep the
1.88 +** static variables organized and to reduce namespace pollution
1.89 +** when this module is combined with other in the amalgamation.
1.90 +*/
1.91 +static SQLITE_WSD struct Mem5Global {
1.92 + /*
1.93 + ** Memory available for allocation
1.94 + */
1.95 + int nAtom; /* Smallest possible allocation in bytes */
1.96 + int nBlock; /* Number of nAtom sized blocks in zPool */
1.97 + u8 *zPool;
1.98 +
1.99 + /*
1.100 + ** Mutex to control access to the memory allocation subsystem.
1.101 + */
1.102 + sqlite3_mutex *mutex;
1.103 +
1.104 + /*
1.105 + ** Performance statistics
1.106 + */
1.107 + u64 nAlloc; /* Total number of calls to malloc */
1.108 + u64 totalAlloc; /* Total of all malloc calls - includes internal frag */
1.109 + u64 totalExcess; /* Total internal fragmentation */
1.110 + u32 currentOut; /* Current checkout, including internal fragmentation */
1.111 + u32 currentCount; /* Current number of distinct checkouts */
1.112 + u32 maxOut; /* Maximum instantaneous currentOut */
1.113 + u32 maxCount; /* Maximum instantaneous currentCount */
1.114 + u32 maxRequest; /* Largest allocation (exclusive of internal frag) */
1.115 +
1.116 + /*
1.117 + ** Lists of free blocks of various sizes.
1.118 + */
1.119 + int aiFreelist[LOGMAX+1];
1.120 +
1.121 + /*
1.122 + ** Space for tracking which blocks are checked out and the size
1.123 + ** of each block. One byte per block.
1.124 + */
1.125 + u8 *aCtrl;
1.126 +
1.127 +} mem5 = { 19804167 };
1.128 +
1.129 +#define mem5 GLOBAL(struct Mem5Global, mem5)
1.130 +
1.131 +#define MEM5LINK(idx) ((Mem5Link *)(&mem5.zPool[(idx)*mem5.nAtom]))
1.132 +
1.133 +/*
1.134 +** Unlink the chunk at mem5.aPool[i] from list it is currently
1.135 +** on. It should be found on mem5.aiFreelist[iLogsize].
1.136 +*/
1.137 +static void memsys5Unlink(int i, int iLogsize){
1.138 + int next, prev;
1.139 + assert( i>=0 && i<mem5.nBlock );
1.140 + assert( iLogsize>=0 && iLogsize<=LOGMAX );
1.141 + assert( (mem5.aCtrl[i] & CTRL_LOGSIZE)==iLogsize );
1.142 +
1.143 + next = MEM5LINK(i)->next;
1.144 + prev = MEM5LINK(i)->prev;
1.145 + if( prev<0 ){
1.146 + mem5.aiFreelist[iLogsize] = next;
1.147 + }else{
1.148 + MEM5LINK(prev)->next = next;
1.149 + }
1.150 + if( next>=0 ){
1.151 + MEM5LINK(next)->prev = prev;
1.152 + }
1.153 +}
1.154 +
1.155 +/*
1.156 +** Link the chunk at mem5.aPool[i] so that is on the iLogsize
1.157 +** free list.
1.158 +*/
1.159 +static void memsys5Link(int i, int iLogsize){
1.160 + int x;
1.161 + assert( sqlite3_mutex_held(mem5.mutex) );
1.162 + assert( i>=0 && i<mem5.nBlock );
1.163 + assert( iLogsize>=0 && iLogsize<=LOGMAX );
1.164 + assert( (mem5.aCtrl[i] & CTRL_LOGSIZE)==iLogsize );
1.165 +
1.166 + x = MEM5LINK(i)->next = mem5.aiFreelist[iLogsize];
1.167 + MEM5LINK(i)->prev = -1;
1.168 + if( x>=0 ){
1.169 + assert( x<mem5.nBlock );
1.170 + MEM5LINK(x)->prev = i;
1.171 + }
1.172 + mem5.aiFreelist[iLogsize] = i;
1.173 +}
1.174 +
1.175 +/*
1.176 +** If the STATIC_MEM mutex is not already held, obtain it now. The mutex
1.177 +** will already be held (obtained by code in malloc.c) if
1.178 +** sqlite3GlobalConfig.bMemStat is true.
1.179 +*/
1.180 +static void memsys5Enter(void){
1.181 + if( sqlite3GlobalConfig.bMemstat==0 && mem5.mutex==0 ){
1.182 + mem5.mutex = sqlite3MutexAlloc(SQLITE_MUTEX_STATIC_MEM);
1.183 + }
1.184 + sqlite3_mutex_enter(mem5.mutex);
1.185 +}
1.186 +static void memsys5Leave(void){
1.187 + sqlite3_mutex_leave(mem5.mutex);
1.188 +}
1.189 +
1.190 +/*
1.191 +** Return the size of an outstanding allocation, in bytes. The
1.192 +** size returned omits the 8-byte header overhead. This only
1.193 +** works for chunks that are currently checked out.
1.194 +*/
1.195 +static int memsys5Size(void *p){
1.196 + int iSize = 0;
1.197 + if( p ){
1.198 + int i = ((u8 *)p-mem5.zPool)/mem5.nAtom;
1.199 + assert( i>=0 && i<mem5.nBlock );
1.200 + iSize = mem5.nAtom * (1 << (mem5.aCtrl[i]&CTRL_LOGSIZE));
1.201 + }
1.202 + return iSize;
1.203 +}
1.204 +
1.205 +/*
1.206 +** Find the first entry on the freelist iLogsize. Unlink that
1.207 +** entry and return its index.
1.208 +*/
1.209 +static int memsys5UnlinkFirst(int iLogsize){
1.210 + int i;
1.211 + int iFirst;
1.212 +
1.213 + assert( iLogsize>=0 && iLogsize<=LOGMAX );
1.214 + i = iFirst = mem5.aiFreelist[iLogsize];
1.215 + assert( iFirst>=0 );
1.216 + while( i>0 ){
1.217 + if( i<iFirst ) iFirst = i;
1.218 + i = MEM5LINK(i)->next;
1.219 + }
1.220 + memsys5Unlink(iFirst, iLogsize);
1.221 + return iFirst;
1.222 +}
1.223 +
1.224 +/*
1.225 +** Return a block of memory of at least nBytes in size.
1.226 +** Return NULL if unable.
1.227 +*/
1.228 +static void *memsys5MallocUnsafe(int nByte){
1.229 + int i; /* Index of a mem5.aPool[] slot */
1.230 + int iBin; /* Index into mem5.aiFreelist[] */
1.231 + int iFullSz; /* Size of allocation rounded up to power of 2 */
1.232 + int iLogsize; /* Log2 of iFullSz/POW2_MIN */
1.233 +
1.234 + /* Keep track of the maximum allocation request. Even unfulfilled
1.235 + ** requests are counted */
1.236 + if( nByte>mem5.maxRequest ){
1.237 + mem5.maxRequest = nByte;
1.238 + }
1.239 +
1.240 + /* Round nByte up to the next valid power of two */
1.241 + if( nByte>POW2_MAX ) return 0;
1.242 + for(iFullSz=mem5.nAtom, iLogsize=0; iFullSz<nByte; iFullSz *= 2, iLogsize++){}
1.243 +
1.244 + /* Make sure mem5.aiFreelist[iLogsize] contains at least one free
1.245 + ** block. If not, then split a block of the next larger power of
1.246 + ** two in order to create a new free block of size iLogsize.
1.247 + */
1.248 + for(iBin=iLogsize; mem5.aiFreelist[iBin]<0 && iBin<=LOGMAX; iBin++){}
1.249 + if( iBin>LOGMAX ) return 0;
1.250 + i = memsys5UnlinkFirst(iBin);
1.251 + while( iBin>iLogsize ){
1.252 + int newSize;
1.253 +
1.254 + iBin--;
1.255 + newSize = 1 << iBin;
1.256 + mem5.aCtrl[i+newSize] = CTRL_FREE | iBin;
1.257 + memsys5Link(i+newSize, iBin);
1.258 + }
1.259 + mem5.aCtrl[i] = iLogsize;
1.260 +
1.261 + /* Update allocator performance statistics. */
1.262 + mem5.nAlloc++;
1.263 + mem5.totalAlloc += iFullSz;
1.264 + mem5.totalExcess += iFullSz - nByte;
1.265 + mem5.currentCount++;
1.266 + mem5.currentOut += iFullSz;
1.267 + if( mem5.maxCount<mem5.currentCount ) mem5.maxCount = mem5.currentCount;
1.268 + if( mem5.maxOut<mem5.currentOut ) mem5.maxOut = mem5.currentOut;
1.269 +
1.270 + /* Return a pointer to the allocated memory. */
1.271 + return (void*)&mem5.zPool[i*mem5.nAtom];
1.272 +}
1.273 +
1.274 +/*
1.275 +** Free an outstanding memory allocation.
1.276 +*/
1.277 +static void memsys5FreeUnsafe(void *pOld){
1.278 + u32 size, iLogsize;
1.279 + int iBlock;
1.280 +
1.281 + /* Set iBlock to the index of the block pointed to by pOld in
1.282 + ** the array of mem5.nAtom byte blocks pointed to by mem5.zPool.
1.283 + */
1.284 + iBlock = ((u8 *)pOld-mem5.zPool)/mem5.nAtom;
1.285 +
1.286 + /* Check that the pointer pOld points to a valid, non-free block. */
1.287 + assert( iBlock>=0 && iBlock<mem5.nBlock );
1.288 + assert( ((u8 *)pOld-mem5.zPool)%mem5.nAtom==0 );
1.289 + assert( (mem5.aCtrl[iBlock] & CTRL_FREE)==0 );
1.290 +
1.291 + iLogsize = mem5.aCtrl[iBlock] & CTRL_LOGSIZE;
1.292 + size = 1<<iLogsize;
1.293 + assert( iBlock+size-1<mem5.nBlock );
1.294 +
1.295 + mem5.aCtrl[iBlock] |= CTRL_FREE;
1.296 + mem5.aCtrl[iBlock+size-1] |= CTRL_FREE;
1.297 + assert( mem5.currentCount>0 );
1.298 + assert( mem5.currentOut>=0 );
1.299 + mem5.currentCount--;
1.300 + mem5.currentOut -= size*mem5.nAtom;
1.301 + assert( mem5.currentOut>0 || mem5.currentCount==0 );
1.302 + assert( mem5.currentCount>0 || mem5.currentOut==0 );
1.303 +
1.304 + mem5.aCtrl[iBlock] = CTRL_FREE | iLogsize;
1.305 + while( iLogsize<LOGMAX ){
1.306 + int iBuddy;
1.307 + if( (iBlock>>iLogsize) & 1 ){
1.308 + iBuddy = iBlock - size;
1.309 + }else{
1.310 + iBuddy = iBlock + size;
1.311 + }
1.312 + assert( iBuddy>=0 );
1.313 + if( (iBuddy+(1<<iLogsize))>mem5.nBlock ) break;
1.314 + if( mem5.aCtrl[iBuddy]!=(CTRL_FREE | iLogsize) ) break;
1.315 + memsys5Unlink(iBuddy, iLogsize);
1.316 + iLogsize++;
1.317 + if( iBuddy<iBlock ){
1.318 + mem5.aCtrl[iBuddy] = CTRL_FREE | iLogsize;
1.319 + mem5.aCtrl[iBlock] = 0;
1.320 + iBlock = iBuddy;
1.321 + }else{
1.322 + mem5.aCtrl[iBlock] = CTRL_FREE | iLogsize;
1.323 + mem5.aCtrl[iBuddy] = 0;
1.324 + }
1.325 + size *= 2;
1.326 + }
1.327 + memsys5Link(iBlock, iLogsize);
1.328 +}
1.329 +
1.330 +/*
1.331 +** Allocate nBytes of memory
1.332 +*/
1.333 +static void *memsys5Malloc(int nBytes){
1.334 + sqlite3_int64 *p = 0;
1.335 + if( nBytes>0 ){
1.336 + memsys5Enter();
1.337 + p = memsys5MallocUnsafe(nBytes);
1.338 + memsys5Leave();
1.339 + }
1.340 + return (void*)p;
1.341 +}
1.342 +
1.343 +/*
1.344 +** Free memory.
1.345 +*/
1.346 +static void memsys5Free(void *pPrior){
1.347 + if( pPrior==0 ){
1.348 +assert(0);
1.349 + return;
1.350 + }
1.351 + memsys5Enter();
1.352 + memsys5FreeUnsafe(pPrior);
1.353 + memsys5Leave();
1.354 +}
1.355 +
1.356 +/*
1.357 +** Change the size of an existing memory allocation
1.358 +*/
1.359 +static void *memsys5Realloc(void *pPrior, int nBytes){
1.360 + int nOld;
1.361 + void *p;
1.362 + if( pPrior==0 ){
1.363 + return memsys5Malloc(nBytes);
1.364 + }
1.365 + if( nBytes<=0 ){
1.366 + memsys5Free(pPrior);
1.367 + return 0;
1.368 + }
1.369 + nOld = memsys5Size(pPrior);
1.370 + if( nBytes<=nOld ){
1.371 + return pPrior;
1.372 + }
1.373 + memsys5Enter();
1.374 + p = memsys5MallocUnsafe(nBytes);
1.375 + if( p ){
1.376 + memcpy(p, pPrior, nOld);
1.377 + memsys5FreeUnsafe(pPrior);
1.378 + }
1.379 + memsys5Leave();
1.380 + return p;
1.381 +}
1.382 +
1.383 +/*
1.384 +** Round up a request size to the next valid allocation size.
1.385 +*/
1.386 +static int memsys5Roundup(int n){
1.387 + int iFullSz;
1.388 + for(iFullSz=mem5.nAtom; iFullSz<n; iFullSz *= 2);
1.389 + return iFullSz;
1.390 +}
1.391 +
1.392 +static int memsys5Log(int iValue){
1.393 + int iLog;
1.394 + for(iLog=0; (1<<iLog)<iValue; iLog++);
1.395 + return iLog;
1.396 +}
1.397 +
1.398 +/*
1.399 +** Initialize this module.
1.400 +*/
1.401 +static int memsys5Init(void *NotUsed){
1.402 + int ii;
1.403 + int nByte = sqlite3GlobalConfig.nHeap;
1.404 + u8 *zByte = (u8 *)sqlite3GlobalConfig.pHeap;
1.405 + int nMinLog; /* Log of minimum allocation size in bytes*/
1.406 + int iOffset;
1.407 +
1.408 + if( !zByte ){
1.409 + return SQLITE_ERROR;
1.410 + }
1.411 +
1.412 + nMinLog = memsys5Log(sqlite3GlobalConfig.mnReq);
1.413 + mem5.nAtom = (1<<nMinLog);
1.414 + while( sizeof(Mem5Link)>mem5.nAtom ){
1.415 + mem5.nAtom = mem5.nAtom << 1;
1.416 + }
1.417 +
1.418 + mem5.nBlock = (nByte / (mem5.nAtom+sizeof(u8)));
1.419 + mem5.zPool = zByte;
1.420 + mem5.aCtrl = (u8 *)&mem5.zPool[mem5.nBlock*mem5.nAtom];
1.421 +
1.422 + for(ii=0; ii<=LOGMAX; ii++){
1.423 + mem5.aiFreelist[ii] = -1;
1.424 + }
1.425 +
1.426 + iOffset = 0;
1.427 + for(ii=LOGMAX; ii>=0; ii--){
1.428 + int nAlloc = (1<<ii);
1.429 + if( (iOffset+nAlloc)<=mem5.nBlock ){
1.430 + mem5.aCtrl[iOffset] = ii | CTRL_FREE;
1.431 + memsys5Link(iOffset, ii);
1.432 + iOffset += nAlloc;
1.433 + }
1.434 + assert((iOffset+nAlloc)>mem5.nBlock);
1.435 + }
1.436 +
1.437 + return SQLITE_OK;
1.438 +}
1.439 +
1.440 +/*
1.441 +** Deinitialize this module.
1.442 +*/
1.443 +static void memsys5Shutdown(void *NotUsed){
1.444 + return;
1.445 +}
1.446 +
1.447 +/*
1.448 +** Open the file indicated and write a log of all unfreed memory
1.449 +** allocations into that log.
1.450 +*/
1.451 +void sqlite3Memsys5Dump(const char *zFilename){
1.452 +#ifdef SQLITE_DEBUG
1.453 + FILE *out;
1.454 + int i, j, n;
1.455 + int nMinLog;
1.456 +
1.457 + if( zFilename==0 || zFilename[0]==0 ){
1.458 + out = stdout;
1.459 + }else{
1.460 + out = fopen(zFilename, "w");
1.461 + if( out==0 ){
1.462 + fprintf(stderr, "** Unable to output memory debug output log: %s **\n",
1.463 + zFilename);
1.464 + return;
1.465 + }
1.466 + }
1.467 + memsys5Enter();
1.468 + nMinLog = memsys5Log(mem5.nAtom);
1.469 + for(i=0; i<=LOGMAX && i+nMinLog<32; i++){
1.470 + for(n=0, j=mem5.aiFreelist[i]; j>=0; j = MEM5LINK(j)->next, n++){}
1.471 + fprintf(out, "freelist items of size %d: %d\n", mem5.nAtom << i, n);
1.472 + }
1.473 + fprintf(out, "mem5.nAlloc = %llu\n", mem5.nAlloc);
1.474 + fprintf(out, "mem5.totalAlloc = %llu\n", mem5.totalAlloc);
1.475 + fprintf(out, "mem5.totalExcess = %llu\n", mem5.totalExcess);
1.476 + fprintf(out, "mem5.currentOut = %u\n", mem5.currentOut);
1.477 + fprintf(out, "mem5.currentCount = %u\n", mem5.currentCount);
1.478 + fprintf(out, "mem5.maxOut = %u\n", mem5.maxOut);
1.479 + fprintf(out, "mem5.maxCount = %u\n", mem5.maxCount);
1.480 + fprintf(out, "mem5.maxRequest = %u\n", mem5.maxRequest);
1.481 + memsys5Leave();
1.482 + if( out==stdout ){
1.483 + fflush(stdout);
1.484 + }else{
1.485 + fclose(out);
1.486 + }
1.487 +#endif
1.488 +}
1.489 +
1.490 +/*
1.491 +** This routine is the only routine in this file with external
1.492 +** linkage. It returns a pointer to a static sqlite3_mem_methods
1.493 +** struct populated with the memsys5 methods.
1.494 +*/
1.495 +const sqlite3_mem_methods *sqlite3MemGetMemsys5(void){
1.496 + static const sqlite3_mem_methods memsys5Methods = {
1.497 + memsys5Malloc,
1.498 + memsys5Free,
1.499 + memsys5Realloc,
1.500 + memsys5Size,
1.501 + memsys5Roundup,
1.502 + memsys5Init,
1.503 + memsys5Shutdown,
1.504 + 0
1.505 + };
1.506 + return &memsys5Methods;
1.507 +}
1.508 +
1.509 +#endif /* SQLITE_ENABLE_MEMSYS5 */