Merge Chromium + Blink git repositories
[chromium-blink-merge.git] / third_party / sqlite / sqlite-src-3080704 / src / mem5.c
blob1479ddd0d09d69dad6780d40abeebb22bcfa0f67
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.
11 *************************************************************************
12 ** This file contains the C functions that implement a memory
13 ** allocation subsystem for use by SQLite.
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.
23 ** This version of the memory allocation subsystem is included
24 ** in the build only if SQLITE_ENABLE_MEMSYS5 is defined.
26 ** This memory allocator uses the following algorithm:
28 ** 1. All memory allocations sizes are rounded up to a power of 2.
30 ** 2. If two adjacent free blocks are the halves of a larger block,
31 ** then the two blocks are coalesced into the single larger block.
33 ** 3. New memory is allocated from the first available free block.
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:
46 ** N >= M*(1 + log2(n)/2) - n + 1
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.
51 #include "sqliteInt.h"
54 ** This version of the memory allocator is used only when
55 ** SQLITE_ENABLE_MEMSYS5 is defined.
57 #ifdef SQLITE_ENABLE_MEMSYS5
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.
64 ** The size of this object must be a power of two. That fact is
65 ** verified in memsys5Init().
67 typedef struct Mem5Link Mem5Link;
68 struct Mem5Link {
69 int next; /* Index of next free chunk */
70 int prev; /* Index of previous free chunk */
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.
78 #define LOGMAX 30
81 ** Masks used for mem5.aCtrl[] elements.
83 #define CTRL_LOGSIZE 0x1f /* Log2 Size of this block */
84 #define CTRL_FREE 0x20 /* True if not checked out */
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.
92 static SQLITE_WSD struct Mem5Global {
94 ** Memory available for allocation
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 */
101 ** Mutex to control access to the memory allocation subsystem.
103 sqlite3_mutex *mutex;
106 ** Performance statistics
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) */
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.
122 int aiFreelist[LOGMAX+1];
125 ** Space for tracking which blocks are checked out and the size
126 ** of each block. One byte per block.
128 u8 *aCtrl;
130 } mem5;
133 ** Access the static variable through a macro for SQLITE_OMIT_WSD.
135 #define mem5 GLOBAL(struct Mem5Global, mem5)
138 ** Assuming mem5.zPool is divided up into an array of Mem5Link
139 ** structures, return a pointer to the idx-th such link.
141 #define MEM5LINK(idx) ((Mem5Link *)(&mem5.zPool[(idx)*mem5.szAtom]))
144 ** Unlink the chunk at mem5.aPool[i] from list it is currently
145 ** on. It should be found on mem5.aiFreelist[iLogsize].
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 );
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;
160 if( next>=0 ){
161 MEM5LINK(next)->prev = prev;
166 ** Link the chunk at mem5.aPool[i] so that is on the iLogsize
167 ** free list.
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 );
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;
182 mem5.aiFreelist[iLogsize] = i;
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.
190 static void memsys5Enter(void){
191 sqlite3_mutex_enter(mem5.mutex);
193 static void memsys5Leave(void){
194 sqlite3_mutex_leave(mem5.mutex);
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.
202 static int memsys5Size(void *p){
203 int iSize = 0;
204 if( p ){
205 int i = (int)(((u8 *)p-mem5.zPool)/mem5.szAtom);
206 assert( i>=0 && i<mem5.nBlock );
207 iSize = mem5.szAtom * (1 << (mem5.aCtrl[i]&CTRL_LOGSIZE));
209 return iSize;
213 ** Return a block of memory of at least nBytes in size.
214 ** Return NULL if unable. Return NULL if nBytes==0.
216 ** The caller guarantees that nByte is positive.
218 ** The caller has obtained a mutex prior to invoking this
219 ** routine so there is never any chance that two or more
220 ** threads can be in this routine at the same time.
222 static void *memsys5MallocUnsafe(int nByte){
223 int i; /* Index of a mem5.aPool[] slot */
224 int iBin; /* Index into mem5.aiFreelist[] */
225 int iFullSz; /* Size of allocation rounded up to power of 2 */
226 int iLogsize; /* Log2 of iFullSz/POW2_MIN */
228 /* nByte must be a positive */
229 assert( nByte>0 );
231 /* Keep track of the maximum allocation request. Even unfulfilled
232 ** requests are counted */
233 if( (u32)nByte>mem5.maxRequest ){
234 mem5.maxRequest = nByte;
237 /* Abort if the requested allocation size is larger than the largest
238 ** power of two that we can represent using 32-bit signed integers.
240 if( nByte > 0x40000000 ){
241 return 0;
244 /* Round nByte up to the next valid power of two */
245 for(iFullSz=mem5.szAtom, iLogsize=0; iFullSz<nByte; iFullSz *= 2, iLogsize++){}
247 /* Make sure mem5.aiFreelist[iLogsize] contains at least one free
248 ** block. If not, then split a block of the next larger power of
249 ** two in order to create a new free block of size iLogsize.
251 for(iBin=iLogsize; iBin<=LOGMAX && mem5.aiFreelist[iBin]<0; iBin++){}
252 if( iBin>LOGMAX ){
253 testcase( sqlite3GlobalConfig.xLog!=0 );
254 sqlite3_log(SQLITE_NOMEM, "failed to allocate %u bytes", nByte);
255 return 0;
257 i = mem5.aiFreelist[iBin];
258 memsys5Unlink(i, iBin);
259 while( iBin>iLogsize ){
260 int newSize;
262 iBin--;
263 newSize = 1 << iBin;
264 mem5.aCtrl[i+newSize] = CTRL_FREE | iBin;
265 memsys5Link(i+newSize, iBin);
267 mem5.aCtrl[i] = iLogsize;
269 /* Update allocator performance statistics. */
270 mem5.nAlloc++;
271 mem5.totalAlloc += iFullSz;
272 mem5.totalExcess += iFullSz - nByte;
273 mem5.currentCount++;
274 mem5.currentOut += iFullSz;
275 if( mem5.maxCount<mem5.currentCount ) mem5.maxCount = mem5.currentCount;
276 if( mem5.maxOut<mem5.currentOut ) mem5.maxOut = mem5.currentOut;
278 #ifdef SQLITE_DEBUG
279 /* Make sure the allocated memory does not assume that it is set to zero
280 ** or retains a value from a previous allocation */
281 memset(&mem5.zPool[i*mem5.szAtom], 0xAA, iFullSz);
282 #endif
284 /* Return a pointer to the allocated memory. */
285 return (void*)&mem5.zPool[i*mem5.szAtom];
289 ** Free an outstanding memory allocation.
291 static void memsys5FreeUnsafe(void *pOld){
292 u32 size, iLogsize;
293 int iBlock;
295 /* Set iBlock to the index of the block pointed to by pOld in
296 ** the array of mem5.szAtom byte blocks pointed to by mem5.zPool.
298 iBlock = (int)(((u8 *)pOld-mem5.zPool)/mem5.szAtom);
300 /* Check that the pointer pOld points to a valid, non-free block. */
301 assert( iBlock>=0 && iBlock<mem5.nBlock );
302 assert( ((u8 *)pOld-mem5.zPool)%mem5.szAtom==0 );
303 assert( (mem5.aCtrl[iBlock] & CTRL_FREE)==0 );
305 iLogsize = mem5.aCtrl[iBlock] & CTRL_LOGSIZE;
306 size = 1<<iLogsize;
307 assert( iBlock+size-1<(u32)mem5.nBlock );
309 mem5.aCtrl[iBlock] |= CTRL_FREE;
310 mem5.aCtrl[iBlock+size-1] |= CTRL_FREE;
311 assert( mem5.currentCount>0 );
312 assert( mem5.currentOut>=(size*mem5.szAtom) );
313 mem5.currentCount--;
314 mem5.currentOut -= size*mem5.szAtom;
315 assert( mem5.currentOut>0 || mem5.currentCount==0 );
316 assert( mem5.currentCount>0 || mem5.currentOut==0 );
318 mem5.aCtrl[iBlock] = CTRL_FREE | iLogsize;
319 while( ALWAYS(iLogsize<LOGMAX) ){
320 int iBuddy;
321 if( (iBlock>>iLogsize) & 1 ){
322 iBuddy = iBlock - size;
323 }else{
324 iBuddy = iBlock + size;
326 assert( iBuddy>=0 );
327 if( (iBuddy+(1<<iLogsize))>mem5.nBlock ) break;
328 if( mem5.aCtrl[iBuddy]!=(CTRL_FREE | iLogsize) ) break;
329 memsys5Unlink(iBuddy, iLogsize);
330 iLogsize++;
331 if( iBuddy<iBlock ){
332 mem5.aCtrl[iBuddy] = CTRL_FREE | iLogsize;
333 mem5.aCtrl[iBlock] = 0;
334 iBlock = iBuddy;
335 }else{
336 mem5.aCtrl[iBlock] = CTRL_FREE | iLogsize;
337 mem5.aCtrl[iBuddy] = 0;
339 size *= 2;
342 #ifdef SQLITE_DEBUG
343 /* Overwrite freed memory with the 0x55 bit pattern to verify that it is
344 ** not used after being freed */
345 memset(&mem5.zPool[iBlock*mem5.szAtom], 0x55, size);
346 #endif
348 memsys5Link(iBlock, iLogsize);
352 ** Allocate nBytes of memory.
354 static void *memsys5Malloc(int nBytes){
355 sqlite3_int64 *p = 0;
356 if( nBytes>0 ){
357 memsys5Enter();
358 p = memsys5MallocUnsafe(nBytes);
359 memsys5Leave();
361 return (void*)p;
365 ** Free memory.
367 ** The outer layer memory allocator prevents this routine from
368 ** being called with pPrior==0.
370 static void memsys5Free(void *pPrior){
371 assert( pPrior!=0 );
372 memsys5Enter();
373 memsys5FreeUnsafe(pPrior);
374 memsys5Leave();
378 ** Change the size of an existing memory allocation.
380 ** The outer layer memory allocator prevents this routine from
381 ** being called with pPrior==0.
383 ** nBytes is always a value obtained from a prior call to
384 ** memsys5Round(). Hence nBytes is always a non-negative power
385 ** of two. If nBytes==0 that means that an oversize allocation
386 ** (an allocation larger than 0x40000000) was requested and this
387 ** routine should return 0 without freeing pPrior.
389 static void *memsys5Realloc(void *pPrior, int nBytes){
390 int nOld;
391 void *p;
392 assert( pPrior!=0 );
393 assert( (nBytes&(nBytes-1))==0 ); /* EV: R-46199-30249 */
394 assert( nBytes>=0 );
395 if( nBytes==0 ){
396 return 0;
398 nOld = memsys5Size(pPrior);
399 if( nBytes<=nOld ){
400 return pPrior;
402 memsys5Enter();
403 p = memsys5MallocUnsafe(nBytes);
404 if( p ){
405 memcpy(p, pPrior, nOld);
406 memsys5FreeUnsafe(pPrior);
408 memsys5Leave();
409 return p;
413 ** Round up a request size to the next valid allocation size. If
414 ** the allocation is too large to be handled by this allocation system,
415 ** return 0.
417 ** All allocations must be a power of two and must be expressed by a
418 ** 32-bit signed integer. Hence the largest allocation is 0x40000000
419 ** or 1073741824 bytes.
421 static int memsys5Roundup(int n){
422 int iFullSz;
423 if( n > 0x40000000 ) return 0;
424 for(iFullSz=mem5.szAtom; iFullSz<n; iFullSz *= 2);
425 return iFullSz;
429 ** Return the ceiling of the logarithm base 2 of iValue.
431 ** Examples: memsys5Log(1) -> 0
432 ** memsys5Log(2) -> 1
433 ** memsys5Log(4) -> 2
434 ** memsys5Log(5) -> 3
435 ** memsys5Log(8) -> 3
436 ** memsys5Log(9) -> 4
438 static int memsys5Log(int iValue){
439 int iLog;
440 for(iLog=0; (iLog<(int)((sizeof(int)*8)-1)) && (1<<iLog)<iValue; iLog++);
441 return iLog;
445 ** Initialize the memory allocator.
447 ** This routine is not threadsafe. The caller must be holding a mutex
448 ** to prevent multiple threads from entering at the same time.
450 static int memsys5Init(void *NotUsed){
451 int ii; /* Loop counter */
452 int nByte; /* Number of bytes of memory available to this allocator */
453 u8 *zByte; /* Memory usable by this allocator */
454 int nMinLog; /* Log base 2 of minimum allocation size in bytes */
455 int iOffset; /* An offset into mem5.aCtrl[] */
457 UNUSED_PARAMETER(NotUsed);
459 /* For the purposes of this routine, disable the mutex */
460 mem5.mutex = 0;
462 /* The size of a Mem5Link object must be a power of two. Verify that
463 ** this is case.
465 assert( (sizeof(Mem5Link)&(sizeof(Mem5Link)-1))==0 );
467 nByte = sqlite3GlobalConfig.nHeap;
468 zByte = (u8*)sqlite3GlobalConfig.pHeap;
469 assert( zByte!=0 ); /* sqlite3_config() does not allow otherwise */
471 /* boundaries on sqlite3GlobalConfig.mnReq are enforced in sqlite3_config() */
472 nMinLog = memsys5Log(sqlite3GlobalConfig.mnReq);
473 mem5.szAtom = (1<<nMinLog);
474 while( (int)sizeof(Mem5Link)>mem5.szAtom ){
475 mem5.szAtom = mem5.szAtom << 1;
478 mem5.nBlock = (nByte / (mem5.szAtom+sizeof(u8)));
479 mem5.zPool = zByte;
480 mem5.aCtrl = (u8 *)&mem5.zPool[mem5.nBlock*mem5.szAtom];
482 for(ii=0; ii<=LOGMAX; ii++){
483 mem5.aiFreelist[ii] = -1;
486 iOffset = 0;
487 for(ii=LOGMAX; ii>=0; ii--){
488 int nAlloc = (1<<ii);
489 if( (iOffset+nAlloc)<=mem5.nBlock ){
490 mem5.aCtrl[iOffset] = ii | CTRL_FREE;
491 memsys5Link(iOffset, ii);
492 iOffset += nAlloc;
494 assert((iOffset+nAlloc)>mem5.nBlock);
497 /* If a mutex is required for normal operation, allocate one */
498 if( sqlite3GlobalConfig.bMemstat==0 ){
499 mem5.mutex = sqlite3MutexAlloc(SQLITE_MUTEX_STATIC_MEM);
502 return SQLITE_OK;
506 ** Deinitialize this module.
508 static void memsys5Shutdown(void *NotUsed){
509 UNUSED_PARAMETER(NotUsed);
510 mem5.mutex = 0;
511 return;
514 #ifdef SQLITE_TEST
516 ** Open the file indicated and write a log of all unfreed memory
517 ** allocations into that log.
519 void sqlite3Memsys5Dump(const char *zFilename){
520 FILE *out;
521 int i, j, n;
522 int nMinLog;
524 if( zFilename==0 || zFilename[0]==0 ){
525 out = stdout;
526 }else{
527 out = fopen(zFilename, "w");
528 if( out==0 ){
529 fprintf(stderr, "** Unable to output memory debug output log: %s **\n",
530 zFilename);
531 return;
534 memsys5Enter();
535 nMinLog = memsys5Log(mem5.szAtom);
536 for(i=0; i<=LOGMAX && i+nMinLog<32; i++){
537 for(n=0, j=mem5.aiFreelist[i]; j>=0; j = MEM5LINK(j)->next, n++){}
538 fprintf(out, "freelist items of size %d: %d\n", mem5.szAtom << i, n);
540 fprintf(out, "mem5.nAlloc = %llu\n", mem5.nAlloc);
541 fprintf(out, "mem5.totalAlloc = %llu\n", mem5.totalAlloc);
542 fprintf(out, "mem5.totalExcess = %llu\n", mem5.totalExcess);
543 fprintf(out, "mem5.currentOut = %u\n", mem5.currentOut);
544 fprintf(out, "mem5.currentCount = %u\n", mem5.currentCount);
545 fprintf(out, "mem5.maxOut = %u\n", mem5.maxOut);
546 fprintf(out, "mem5.maxCount = %u\n", mem5.maxCount);
547 fprintf(out, "mem5.maxRequest = %u\n", mem5.maxRequest);
548 memsys5Leave();
549 if( out==stdout ){
550 fflush(stdout);
551 }else{
552 fclose(out);
555 #endif
558 ** This routine is the only routine in this file with external
559 ** linkage. It returns a pointer to a static sqlite3_mem_methods
560 ** struct populated with the memsys5 methods.
562 const sqlite3_mem_methods *sqlite3MemGetMemsys5(void){
563 static const sqlite3_mem_methods memsys5Methods = {
564 memsys5Malloc,
565 memsys5Free,
566 memsys5Realloc,
567 memsys5Size,
568 memsys5Roundup,
569 memsys5Init,
570 memsys5Shutdown,
573 return &memsys5Methods;
576 #endif /* SQLITE_ENABLE_MEMSYS5 */