diff options
Diffstat (limited to 'chromium/third_party/sqlite/sqlite-src-3240000/src/mem5.c')
| -rw-r--r-- | chromium/third_party/sqlite/sqlite-src-3240000/src/mem5.c | 576 |
1 files changed, 0 insertions, 576 deletions
diff --git a/chromium/third_party/sqlite/sqlite-src-3240000/src/mem5.c b/chromium/third_party/sqlite/sqlite-src-3240000/src/mem5.c deleted file mode 100644 index c194a6b7781..00000000000 --- a/chromium/third_party/sqlite/sqlite-src-3240000/src/mem5.c +++ /dev/null @@ -1,576 +0,0 @@ -/* -** 2007 October 14 -** -** The author disclaims copyright to this source code. In place of -** a legal notice, here is a blessing: -** -** May you do good and not evil. -** May you find forgiveness for yourself and forgive others. -** May you share freely, never taking more than you give. -** -************************************************************************* -** This file contains the C functions that implement a memory -** allocation subsystem for use by SQLite. -** -** This version of the memory allocation subsystem omits all -** use of malloc(). The application gives SQLite a block of memory -** before calling sqlite3_initialize() from which allocations -** are made and returned by the xMalloc() and xRealloc() -** implementations. Once sqlite3_initialize() has been called, -** the amount of memory available to SQLite is fixed and cannot -** be changed. -** -** This version of the memory allocation subsystem is included -** in the build only if SQLITE_ENABLE_MEMSYS5 is defined. -** -** This memory allocator uses the following algorithm: -** -** 1. All memory allocation sizes are rounded up to a power of 2. -** -** 2. If two adjacent free blocks are the halves of a larger block, -** then the two blocks are coalesced into the single larger block. -** -** 3. New memory is allocated from the first available free block. -** -** This algorithm is described in: J. M. Robson. "Bounds for Some Functions -** Concerning Dynamic Storage Allocation". Journal of the Association for -** Computing Machinery, Volume 21, Number 8, July 1974, pages 491-499. -** -** Let n be the size of the largest allocation divided by the minimum -** allocation size (after rounding all sizes up to a power of 2.) Let M -** be the maximum amount of memory ever outstanding at one time. Let -** N be the total amount of memory available for allocation. Robson -** proved that this memory allocator will never breakdown due to -** fragmentation as long as the following constraint holds: -** -** N >= M*(1 + log2(n)/2) - n + 1 -** -** The sqlite3_status() logic tracks the maximum values of n and M so -** that an application can, at any time, verify this constraint. -*/ -#include "sqliteInt.h" - -/* -** This version of the memory allocator is used only when -** SQLITE_ENABLE_MEMSYS5 is defined. -*/ -#ifdef SQLITE_ENABLE_MEMSYS5 - -/* -** A minimum allocation is an instance of the following structure. -** Larger allocations are an array of these structures where the -** size of the array is a power of 2. -** -** The size of this object must be a power of two. That fact is -** verified in memsys5Init(). -*/ -typedef struct Mem5Link Mem5Link; -struct Mem5Link { - int next; /* Index of next free chunk */ - int prev; /* Index of previous free chunk */ -}; - -/* -** Maximum size of any allocation is ((1<<LOGMAX)*mem5.szAtom). Since -** mem5.szAtom is always at least 8 and 32-bit integers are used, -** it is not actually possible to reach this limit. -*/ -#define LOGMAX 30 - -/* -** Masks used for mem5.aCtrl[] elements. -*/ -#define CTRL_LOGSIZE 0x1f /* Log2 Size of this block */ -#define CTRL_FREE 0x20 /* True if not checked out */ - -/* -** All of the static variables used by this module are collected -** into a single structure named "mem5". This is to keep the -** static variables organized and to reduce namespace pollution -** when this module is combined with other in the amalgamation. -*/ -static SQLITE_WSD struct Mem5Global { - /* - ** Memory available for allocation - */ - int szAtom; /* Smallest possible allocation in bytes */ - int nBlock; /* Number of szAtom sized blocks in zPool */ - u8 *zPool; /* Memory available to be allocated */ - - /* - ** Mutex to control access to the memory allocation subsystem. - */ - sqlite3_mutex *mutex; - -#if defined(SQLITE_DEBUG) || defined(SQLITE_TEST) - /* - ** Performance statistics - */ - u64 nAlloc; /* Total number of calls to malloc */ - u64 totalAlloc; /* Total of all malloc calls - includes internal frag */ - u64 totalExcess; /* Total internal fragmentation */ - u32 currentOut; /* Current checkout, including internal fragmentation */ - u32 currentCount; /* Current number of distinct checkouts */ - u32 maxOut; /* Maximum instantaneous currentOut */ - u32 maxCount; /* Maximum instantaneous currentCount */ - u32 maxRequest; /* Largest allocation (exclusive of internal frag) */ -#endif - - /* - ** Lists of free blocks. aiFreelist[0] is a list of free blocks of - ** size mem5.szAtom. aiFreelist[1] holds blocks of size szAtom*2. - ** aiFreelist[2] holds free blocks of size szAtom*4. And so forth. - */ - int aiFreelist[LOGMAX+1]; - - /* - ** Space for tracking which blocks are checked out and the size - ** of each block. One byte per block. - */ - u8 *aCtrl; - -} mem5; - -/* -** Access the static variable through a macro for SQLITE_OMIT_WSD. -*/ -#define mem5 GLOBAL(struct Mem5Global, mem5) - -/* -** Assuming mem5.zPool is divided up into an array of Mem5Link -** structures, return a pointer to the idx-th such link. -*/ -#define MEM5LINK(idx) ((Mem5Link *)(&mem5.zPool[(idx)*mem5.szAtom])) - -/* -** Unlink the chunk at mem5.aPool[i] from list it is currently -** on. It should be found on mem5.aiFreelist[iLogsize]. -*/ -static void memsys5Unlink(int i, int iLogsize){ - int next, prev; - assert( i>=0 && i<mem5.nBlock ); - assert( iLogsize>=0 && iLogsize<=LOGMAX ); - assert( (mem5.aCtrl[i] & CTRL_LOGSIZE)==iLogsize ); - - next = MEM5LINK(i)->next; - prev = MEM5LINK(i)->prev; - if( prev<0 ){ - mem5.aiFreelist[iLogsize] = next; - }else{ - MEM5LINK(prev)->next = next; - } - if( next>=0 ){ - MEM5LINK(next)->prev = prev; - } -} - -/* -** Link the chunk at mem5.aPool[i] so that is on the iLogsize -** free list. -*/ -static void memsys5Link(int i, int iLogsize){ - int x; - assert( sqlite3_mutex_held(mem5.mutex) ); - assert( i>=0 && i<mem5.nBlock ); - assert( iLogsize>=0 && iLogsize<=LOGMAX ); - assert( (mem5.aCtrl[i] & CTRL_LOGSIZE)==iLogsize ); - - x = MEM5LINK(i)->next = mem5.aiFreelist[iLogsize]; - MEM5LINK(i)->prev = -1; - if( x>=0 ){ - assert( x<mem5.nBlock ); - MEM5LINK(x)->prev = i; - } - mem5.aiFreelist[iLogsize] = i; -} - -/* -** Obtain or release the mutex needed to access global data structures. -*/ -static void memsys5Enter(void){ - sqlite3_mutex_enter(mem5.mutex); -} -static void memsys5Leave(void){ - sqlite3_mutex_leave(mem5.mutex); -} - -/* -** Return the size of an outstanding allocation, in bytes. -** This only works for chunks that are currently checked out. -*/ -static int memsys5Size(void *p){ - int iSize, i; - assert( p!=0 ); - i = (int)(((u8 *)p-mem5.zPool)/mem5.szAtom); - assert( i>=0 && i<mem5.nBlock ); - iSize = mem5.szAtom * (1 << (mem5.aCtrl[i]&CTRL_LOGSIZE)); - return iSize; -} - -/* -** Return a block of memory of at least nBytes in size. -** Return NULL if unable. Return NULL if nBytes==0. -** -** The caller guarantees that nByte is positive. -** -** The caller has obtained a mutex prior to invoking this -** routine so there is never any chance that two or more -** threads can be in this routine at the same time. -*/ -static void *memsys5MallocUnsafe(int nByte){ - int i; /* Index of a mem5.aPool[] slot */ - int iBin; /* Index into mem5.aiFreelist[] */ - int iFullSz; /* Size of allocation rounded up to power of 2 */ - int iLogsize; /* Log2 of iFullSz/POW2_MIN */ - - /* nByte must be a positive */ - assert( nByte>0 ); - - /* No more than 1GiB per allocation */ - if( nByte > 0x40000000 ) return 0; - -#if defined(SQLITE_DEBUG) || defined(SQLITE_TEST) - /* Keep track of the maximum allocation request. Even unfulfilled - ** requests are counted */ - if( (u32)nByte>mem5.maxRequest ){ - mem5.maxRequest = nByte; - } -#endif - - - /* Round nByte up to the next valid power of two */ - for(iFullSz=mem5.szAtom,iLogsize=0; iFullSz<nByte; iFullSz*=2,iLogsize++){} - - /* Make sure mem5.aiFreelist[iLogsize] contains at least one free - ** block. If not, then split a block of the next larger power of - ** two in order to create a new free block of size iLogsize. - */ - for(iBin=iLogsize; iBin<=LOGMAX && mem5.aiFreelist[iBin]<0; iBin++){} - if( iBin>LOGMAX ){ - testcase( sqlite3GlobalConfig.xLog!=0 ); - sqlite3_log(SQLITE_NOMEM, "failed to allocate %u bytes", nByte); - return 0; - } - i = mem5.aiFreelist[iBin]; - memsys5Unlink(i, iBin); - while( iBin>iLogsize ){ - int newSize; - - iBin--; - newSize = 1 << iBin; - mem5.aCtrl[i+newSize] = CTRL_FREE | iBin; - memsys5Link(i+newSize, iBin); - } - mem5.aCtrl[i] = iLogsize; - -#if defined(SQLITE_DEBUG) || defined(SQLITE_TEST) - /* Update allocator performance statistics. */ - mem5.nAlloc++; - mem5.totalAlloc += iFullSz; - mem5.totalExcess += iFullSz - nByte; - mem5.currentCount++; - mem5.currentOut += iFullSz; - if( mem5.maxCount<mem5.currentCount ) mem5.maxCount = mem5.currentCount; - if( mem5.maxOut<mem5.currentOut ) mem5.maxOut = mem5.currentOut; -#endif - -#ifdef SQLITE_DEBUG - /* Make sure the allocated memory does not assume that it is set to zero - ** or retains a value from a previous allocation */ - memset(&mem5.zPool[i*mem5.szAtom], 0xAA, iFullSz); -#endif - - /* Return a pointer to the allocated memory. */ - return (void*)&mem5.zPool[i*mem5.szAtom]; -} - -/* -** Free an outstanding memory allocation. -*/ -static void memsys5FreeUnsafe(void *pOld){ - u32 size, iLogsize; - int iBlock; - - /* Set iBlock to the index of the block pointed to by pOld in - ** the array of mem5.szAtom byte blocks pointed to by mem5.zPool. - */ - iBlock = (int)(((u8 *)pOld-mem5.zPool)/mem5.szAtom); - - /* Check that the pointer pOld points to a valid, non-free block. */ - assert( iBlock>=0 && iBlock<mem5.nBlock ); - assert( ((u8 *)pOld-mem5.zPool)%mem5.szAtom==0 ); - assert( (mem5.aCtrl[iBlock] & CTRL_FREE)==0 ); - - iLogsize = mem5.aCtrl[iBlock] & CTRL_LOGSIZE; - size = 1<<iLogsize; - assert( iBlock+size-1<(u32)mem5.nBlock ); - - mem5.aCtrl[iBlock] |= CTRL_FREE; - mem5.aCtrl[iBlock+size-1] |= CTRL_FREE; - -#if defined(SQLITE_DEBUG) || defined(SQLITE_TEST) - assert( mem5.currentCount>0 ); - assert( mem5.currentOut>=(size*mem5.szAtom) ); - mem5.currentCount--; - mem5.currentOut -= size*mem5.szAtom; - assert( mem5.currentOut>0 || mem5.currentCount==0 ); - assert( mem5.currentCount>0 || mem5.currentOut==0 ); -#endif - - mem5.aCtrl[iBlock] = CTRL_FREE | iLogsize; - while( ALWAYS(iLogsize<LOGMAX) ){ - int iBuddy; - if( (iBlock>>iLogsize) & 1 ){ - iBuddy = iBlock - size; - assert( iBuddy>=0 ); - }else{ - iBuddy = iBlock + size; - if( iBuddy>=mem5.nBlock ) break; - } - if( mem5.aCtrl[iBuddy]!=(CTRL_FREE | iLogsize) ) break; - memsys5Unlink(iBuddy, iLogsize); - iLogsize++; - if( iBuddy<iBlock ){ - mem5.aCtrl[iBuddy] = CTRL_FREE | iLogsize; - mem5.aCtrl[iBlock] = 0; - iBlock = iBuddy; - }else{ - mem5.aCtrl[iBlock] = CTRL_FREE | iLogsize; - mem5.aCtrl[iBuddy] = 0; - } - size *= 2; - } - -#ifdef SQLITE_DEBUG - /* Overwrite freed memory with the 0x55 bit pattern to verify that it is - ** not used after being freed */ - memset(&mem5.zPool[iBlock*mem5.szAtom], 0x55, size); -#endif - - memsys5Link(iBlock, iLogsize); -} - -/* -** Allocate nBytes of memory. -*/ -static void *memsys5Malloc(int nBytes){ - sqlite3_int64 *p = 0; - if( nBytes>0 ){ - memsys5Enter(); - p = memsys5MallocUnsafe(nBytes); - memsys5Leave(); - } - return (void*)p; -} - -/* -** Free memory. -** -** The outer layer memory allocator prevents this routine from -** being called with pPrior==0. -*/ -static void memsys5Free(void *pPrior){ - assert( pPrior!=0 ); - memsys5Enter(); - memsys5FreeUnsafe(pPrior); - memsys5Leave(); -} - -/* -** Change the size of an existing memory allocation. -** -** The outer layer memory allocator prevents this routine from -** being called with pPrior==0. -** -** nBytes is always a value obtained from a prior call to -** memsys5Round(). Hence nBytes is always a non-negative power -** of two. If nBytes==0 that means that an oversize allocation -** (an allocation larger than 0x40000000) was requested and this -** routine should return 0 without freeing pPrior. -*/ -static void *memsys5Realloc(void *pPrior, int nBytes){ - int nOld; - void *p; - assert( pPrior!=0 ); - assert( (nBytes&(nBytes-1))==0 ); /* EV: R-46199-30249 */ - assert( nBytes>=0 ); - if( nBytes==0 ){ - return 0; - } - nOld = memsys5Size(pPrior); - if( nBytes<=nOld ){ - return pPrior; - } - p = memsys5Malloc(nBytes); - if( p ){ - memcpy(p, pPrior, nOld); - memsys5Free(pPrior); - } - return p; -} - -/* -** Round up a request size to the next valid allocation size. If -** the allocation is too large to be handled by this allocation system, -** return 0. -** -** All allocations must be a power of two and must be expressed by a -** 32-bit signed integer. Hence the largest allocation is 0x40000000 -** or 1073741824 bytes. -*/ -static int memsys5Roundup(int n){ - int iFullSz; - if( n > 0x40000000 ) return 0; - for(iFullSz=mem5.szAtom; iFullSz<n; iFullSz *= 2); - return iFullSz; -} - -/* -** Return the ceiling of the logarithm base 2 of iValue. -** -** Examples: memsys5Log(1) -> 0 -** memsys5Log(2) -> 1 -** memsys5Log(4) -> 2 -** memsys5Log(5) -> 3 -** memsys5Log(8) -> 3 -** memsys5Log(9) -> 4 -*/ -static int memsys5Log(int iValue){ - int iLog; - for(iLog=0; (iLog<(int)((sizeof(int)*8)-1)) && (1<<iLog)<iValue; iLog++); - return iLog; -} - -/* -** Initialize the memory allocator. -** -** This routine is not threadsafe. The caller must be holding a mutex -** to prevent multiple threads from entering at the same time. -*/ -static int memsys5Init(void *NotUsed){ - int ii; /* Loop counter */ - int nByte; /* Number of bytes of memory available to this allocator */ - u8 *zByte; /* Memory usable by this allocator */ - int nMinLog; /* Log base 2 of minimum allocation size in bytes */ - int iOffset; /* An offset into mem5.aCtrl[] */ - - UNUSED_PARAMETER(NotUsed); - - /* For the purposes of this routine, disable the mutex */ - mem5.mutex = 0; - - /* The size of a Mem5Link object must be a power of two. Verify that - ** this is case. - */ - assert( (sizeof(Mem5Link)&(sizeof(Mem5Link)-1))==0 ); - - nByte = sqlite3GlobalConfig.nHeap; - zByte = (u8*)sqlite3GlobalConfig.pHeap; - assert( zByte!=0 ); /* sqlite3_config() does not allow otherwise */ - - /* boundaries on sqlite3GlobalConfig.mnReq are enforced in sqlite3_config() */ - nMinLog = memsys5Log(sqlite3GlobalConfig.mnReq); - mem5.szAtom = (1<<nMinLog); - while( (int)sizeof(Mem5Link)>mem5.szAtom ){ - mem5.szAtom = mem5.szAtom << 1; - } - - mem5.nBlock = (nByte / (mem5.szAtom+sizeof(u8))); - mem5.zPool = zByte; - mem5.aCtrl = (u8 *)&mem5.zPool[mem5.nBlock*mem5.szAtom]; - - for(ii=0; ii<=LOGMAX; ii++){ - mem5.aiFreelist[ii] = -1; - } - - iOffset = 0; - for(ii=LOGMAX; ii>=0; ii--){ - int nAlloc = (1<<ii); - if( (iOffset+nAlloc)<=mem5.nBlock ){ - mem5.aCtrl[iOffset] = ii | CTRL_FREE; - memsys5Link(iOffset, ii); - iOffset += nAlloc; - } - assert((iOffset+nAlloc)>mem5.nBlock); - } - - /* If a mutex is required for normal operation, allocate one */ - if( sqlite3GlobalConfig.bMemstat==0 ){ - mem5.mutex = sqlite3MutexAlloc(SQLITE_MUTEX_STATIC_MEM); - } - - return SQLITE_OK; -} - -/* -** Deinitialize this module. -*/ -static void memsys5Shutdown(void *NotUsed){ - UNUSED_PARAMETER(NotUsed); - mem5.mutex = 0; - return; -} - -#ifdef SQLITE_TEST -/* -** Open the file indicated and write a log of all unfreed memory -** allocations into that log. -*/ -void sqlite3Memsys5Dump(const char *zFilename){ - FILE *out; - int i, j, n; - int nMinLog; - - if( zFilename==0 || zFilename[0]==0 ){ - out = stdout; - }else{ - out = fopen(zFilename, "w"); - if( out==0 ){ - fprintf(stderr, "** Unable to output memory debug output log: %s **\n", - zFilename); - return; - } - } - memsys5Enter(); - nMinLog = memsys5Log(mem5.szAtom); - for(i=0; i<=LOGMAX && i+nMinLog<32; i++){ - for(n=0, j=mem5.aiFreelist[i]; j>=0; j = MEM5LINK(j)->next, n++){} - fprintf(out, "freelist items of size %d: %d\n", mem5.szAtom << i, n); - } - fprintf(out, "mem5.nAlloc = %llu\n", mem5.nAlloc); - fprintf(out, "mem5.totalAlloc = %llu\n", mem5.totalAlloc); - fprintf(out, "mem5.totalExcess = %llu\n", mem5.totalExcess); - fprintf(out, "mem5.currentOut = %u\n", mem5.currentOut); - fprintf(out, "mem5.currentCount = %u\n", mem5.currentCount); - fprintf(out, "mem5.maxOut = %u\n", mem5.maxOut); - fprintf(out, "mem5.maxCount = %u\n", mem5.maxCount); - fprintf(out, "mem5.maxRequest = %u\n", mem5.maxRequest); - memsys5Leave(); - if( out==stdout ){ - fflush(stdout); - }else{ - fclose(out); - } -} -#endif - -/* -** This routine is the only routine in this file with external -** linkage. It returns a pointer to a static sqlite3_mem_methods -** struct populated with the memsys5 methods. -*/ -const sqlite3_mem_methods *sqlite3MemGetMemsys5(void){ - static const sqlite3_mem_methods memsys5Methods = { - memsys5Malloc, - memsys5Free, - memsys5Realloc, - memsys5Size, - memsys5Roundup, - memsys5Init, - memsys5Shutdown, - 0 - }; - return &memsys5Methods; -} - -#endif /* SQLITE_ENABLE_MEMSYS5 */ |