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.
10**
11*************************************************************************
12** This file contains the C functions that implement a memory
13** allocation subsystem for use by SQLite.
14**
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.
22**
23** This version of the memory allocation subsystem is included
24** in the build only if SQLITE_ENABLE_MEMSYS5 is defined.
25**
26** This memory allocator uses the following algorithm:
27**
28** 1. All memory allocation sizes are rounded up to a power of 2.
29**
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.
32**
33** 3. New memory is allocated from the first available free block.
34**
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:
45**
46** N >= M*(1 + log2(n)/2) - n + 1
47**
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.
50*/
51#include "sqliteInt.h"
52
53/*
54** This version of the memory allocator is used only when
55** SQLITE_ENABLE_MEMSYS5 is defined.
56*/
57#ifdef SQLITE_ENABLE_MEMSYS5
58
59/*
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.
63**
64** The size of this object must be a power of two. That fact is
65** verified in memsys5Init().
66*/
67typedef struct Mem5Link Mem5Link;
68struct Mem5Link {
69 int next; /* Index of next free chunk */
70 int prev; /* Index of previous free chunk */
71};
72
73/*
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.
77*/
78#define LOGMAX 30
79
80/*
81** Masks used for mem5.aCtrl[] elements.
82*/
83#define CTRL_LOGSIZE 0x1f /* Log2 Size of this block */
84#define CTRL_FREE 0x20 /* True if not checked out */
85
86/*
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.
91*/
92static SQLITE_WSD struct Mem5Global {
93 /*
94 ** Memory available for allocation
95 */
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 */
99
100 /*
101 ** Mutex to control access to the memory allocation subsystem.
102 */
103 sqlite3_mutex *mutex;
104
105#if defined(SQLITE_DEBUG) || defined(SQLITE_TEST)
106 /*
107 ** Performance statistics
108 */
109 u64 nAlloc; /* Total number of calls to malloc */
110 u64 totalAlloc; /* Total of all malloc calls - includes internal frag */
111 u64 totalExcess; /* Total internal fragmentation */
112 u32 currentOut; /* Current checkout, including internal fragmentation */
113 u32 currentCount; /* Current number of distinct checkouts */
114 u32 maxOut; /* Maximum instantaneous currentOut */
115 u32 maxCount; /* Maximum instantaneous currentCount */
116 u32 maxRequest; /* Largest allocation (exclusive of internal frag) */
117#endif
118
119 /*
120 ** Lists of free blocks. aiFreelist[0] is a list of free blocks of
121 ** size mem5.szAtom. aiFreelist[1] holds blocks of size szAtom*2.
122 ** aiFreelist[2] holds free blocks of size szAtom*4. And so forth.
123 */
124 int aiFreelist[LOGMAX+1];
125
126 /*
127 ** Space for tracking which blocks are checked out and the size
128 ** of each block. One byte per block.
129 */
130 u8 *aCtrl;
131
132} mem5;
133
134/*
135** Access the static variable through a macro for SQLITE_OMIT_WSD.
136*/
137#define mem5 GLOBAL(struct Mem5Global, mem5)
138
139/*
140** Assuming mem5.zPool is divided up into an array of Mem5Link
141** structures, return a pointer to the idx-th such link.
142*/
143#define MEM5LINK(idx) ((Mem5Link *)(&mem5.zPool[(idx)*mem5.szAtom]))
144
145/*
146** Unlink the chunk at mem5.aPool[i] from list it is currently
147** on. It should be found on mem5.aiFreelist[iLogsize].
148*/
149static void memsys5Unlink(int i, int iLogsize){
150 int next, prev;
151 assert( i>=0 && i<mem5.nBlock );
152 assert( iLogsize>=0 && iLogsize<=LOGMAX );
153 assert( (mem5.aCtrl[i] & CTRL_LOGSIZE)==iLogsize );
154
155 next = MEM5LINK(i)->next;
156 prev = MEM5LINK(i)->prev;
157 if( prev<0 ){
158 mem5.aiFreelist[iLogsize] = next;
159 }else{
160 MEM5LINK(prev)->next = next;
161 }
162 if( next>=0 ){
163 MEM5LINK(next)->prev = prev;
164 }
165}
166
167/*
168** Link the chunk at mem5.aPool[i] so that is on the iLogsize
169** free list.
170*/
171static void memsys5Link(int i, int iLogsize){
172 int x;
173 assert( sqlite3_mutex_held(mem5.mutex) );
174 assert( i>=0 && i<mem5.nBlock );
175 assert( iLogsize>=0 && iLogsize<=LOGMAX );
176 assert( (mem5.aCtrl[i] & CTRL_LOGSIZE)==iLogsize );
177
178 x = MEM5LINK(i)->next = mem5.aiFreelist[iLogsize];
179 MEM5LINK(i)->prev = -1;
180 if( x>=0 ){
181 assert( x<mem5.nBlock );
182 MEM5LINK(x)->prev = i;
183 }
184 mem5.aiFreelist[iLogsize] = i;
185}
186
187/*
188** Obtain or release the mutex needed to access global data structures.
189*/
190static void memsys5Enter(void){
191 sqlite3_mutex_enter(mem5.mutex);
192}
193static void memsys5Leave(void){
194 sqlite3_mutex_leave(mem5.mutex);
195}
196
197/*
198** Return the size of an outstanding allocation, in bytes.
199** This only works for chunks that are currently checked out.
200*/
201static int memsys5Size(void *p){
202 int iSize, i;
203 assert( p!=0 );
204 i = (int)(((u8 *)p-mem5.zPool)/mem5.szAtom);
205 assert( i>=0 && i<mem5.nBlock );
206 iSize = mem5.szAtom * (1 << (mem5.aCtrl[i]&CTRL_LOGSIZE));
207 return iSize;
208}
209
210/*
211** Return a block of memory of at least nBytes in size.
212** Return NULL if unable. Return NULL if nBytes==0.
213**
214** The caller guarantees that nByte is positive.
215**
216** The caller has obtained a mutex prior to invoking this
217** routine so there is never any chance that two or more
218** threads can be in this routine at the same time.
219*/
220static void *memsys5MallocUnsafe(int nByte){
221 int i; /* Index of a mem5.aPool[] slot */
222 int iBin; /* Index into mem5.aiFreelist[] */
223 int iFullSz; /* Size of allocation rounded up to power of 2 */
224 int iLogsize; /* Log2 of iFullSz/POW2_MIN */
225
226 /* nByte must be a positive */
227 assert( nByte>0 );
228
229 /* No more than 1GiB per allocation */
230 if( nByte > 0x40000000 ) return 0;
231
232#if defined(SQLITE_DEBUG) || defined(SQLITE_TEST)
233 /* Keep track of the maximum allocation request. Even unfulfilled
234 ** requests are counted */
235 if( (u32)nByte>mem5.maxRequest ){
236 mem5.maxRequest = nByte;
237 }
238#endif
239
240
241 /* Round nByte up to the next valid power of two */
242 for(iFullSz=mem5.szAtom,iLogsize=0; iFullSz<nByte; iFullSz*=2,iLogsize++){}
243
244 /* Make sure mem5.aiFreelist[iLogsize] contains at least one free
245 ** block. If not, then split a block of the next larger power of
246 ** two in order to create a new free block of size iLogsize.
247 */
248 for(iBin=iLogsize; iBin<=LOGMAX && mem5.aiFreelist[iBin]<0; iBin++){}
249 if( iBin>LOGMAX ){
250 testcase( sqlite3GlobalConfig.xLog!=0 );
251 sqlite3_log(SQLITE_NOMEM, "failed to allocate %u bytes", nByte);
252 return 0;
253 }
254 i = mem5.aiFreelist[iBin];
255 memsys5Unlink(i, iBin);
256 while( iBin>iLogsize ){
257 int newSize;
258
259 iBin--;
260 newSize = 1 << iBin;
261 mem5.aCtrl[i+newSize] = CTRL_FREE | iBin;
262 memsys5Link(i+newSize, iBin);
263 }
264 mem5.aCtrl[i] = iLogsize;
265
266#if defined(SQLITE_DEBUG) || defined(SQLITE_TEST)
267 /* Update allocator performance statistics. */
268 mem5.nAlloc++;
269 mem5.totalAlloc += iFullSz;
270 mem5.totalExcess += iFullSz - nByte;
271 mem5.currentCount++;
272 mem5.currentOut += iFullSz;
273 if( mem5.maxCount<mem5.currentCount ) mem5.maxCount = mem5.currentCount;
274 if( mem5.maxOut<mem5.currentOut ) mem5.maxOut = mem5.currentOut;
275#endif
276
277#ifdef SQLITE_DEBUG
278 /* Make sure the allocated memory does not assume that it is set to zero
279 ** or retains a value from a previous allocation */
280 memset(&mem5.zPool[i*mem5.szAtom], 0xAA, iFullSz);
281#endif
282
283 /* Return a pointer to the allocated memory. */
284 return (void*)&mem5.zPool[i*mem5.szAtom];
285}
286
287/*
288** Free an outstanding memory allocation.
289*/
290static void memsys5FreeUnsafe(void *pOld){
291 u32 size, iLogsize;
292 int iBlock;
293
294 /* Set iBlock to the index of the block pointed to by pOld in
295 ** the array of mem5.szAtom byte blocks pointed to by mem5.zPool.
296 */
297 iBlock = (int)(((u8 *)pOld-mem5.zPool)/mem5.szAtom);
298
299 /* Check that the pointer pOld points to a valid, non-free block. */
300 assert( iBlock>=0 && iBlock<mem5.nBlock );
301 assert( ((u8 *)pOld-mem5.zPool)%mem5.szAtom==0 );
302 assert( (mem5.aCtrl[iBlock] & CTRL_FREE)==0 );
303
304 iLogsize = mem5.aCtrl[iBlock] & CTRL_LOGSIZE;
305 size = 1<<iLogsize;
306 assert( iBlock+size-1<(u32)mem5.nBlock );
307
308 mem5.aCtrl[iBlock] |= CTRL_FREE;
309 mem5.aCtrl[iBlock+size-1] |= CTRL_FREE;
310
311#if defined(SQLITE_DEBUG) || defined(SQLITE_TEST)
312 assert( mem5.currentCount>0 );
313 assert( mem5.currentOut>=(size*mem5.szAtom) );
314 mem5.currentCount--;
315 mem5.currentOut -= size*mem5.szAtom;
316 assert( mem5.currentOut>0 || mem5.currentCount==0 );
317 assert( mem5.currentCount>0 || mem5.currentOut==0 );
318#endif
319
320 mem5.aCtrl[iBlock] = CTRL_FREE | iLogsize;
321 while( ALWAYS(iLogsize<LOGMAX) ){
322 int iBuddy;
323 if( (iBlock>>iLogsize) & 1 ){
324 iBuddy = iBlock - size;
325 assert( iBuddy>=0 );
326 }else{
327 iBuddy = iBlock + size;
328 if( iBuddy>=mem5.nBlock ) break;
329 }
330 if( mem5.aCtrl[iBuddy]!=(CTRL_FREE | iLogsize) ) break;
331 memsys5Unlink(iBuddy, iLogsize);
332 iLogsize++;
333 if( iBuddy<iBlock ){
334 mem5.aCtrl[iBuddy] = CTRL_FREE | iLogsize;
335 mem5.aCtrl[iBlock] = 0;
336 iBlock = iBuddy;
337 }else{
338 mem5.aCtrl[iBlock] = CTRL_FREE | iLogsize;
339 mem5.aCtrl[iBuddy] = 0;
340 }
341 size *= 2;
342 }
343
344#ifdef SQLITE_DEBUG
345 /* Overwrite freed memory with the 0x55 bit pattern to verify that it is
346 ** not used after being freed */
347 memset(&mem5.zPool[iBlock*mem5.szAtom], 0x55, size);
348#endif
349
350 memsys5Link(iBlock, iLogsize);
351}
352
353/*
354** Allocate nBytes of memory.
355*/
356static void *memsys5Malloc(int nBytes){
357 sqlite3_int64 *p = 0;
358 if( nBytes>0 ){
359 memsys5Enter();
360 p = memsys5MallocUnsafe(nBytes);
361 memsys5Leave();
362 }
363 return (void*)p;
364}
365
366/*
367** Free memory.
368**
369** The outer layer memory allocator prevents this routine from
370** being called with pPrior==0.
371*/
372static void memsys5Free(void *pPrior){
373 assert( pPrior!=0 );
374 memsys5Enter();
375 memsys5FreeUnsafe(pPrior);
376 memsys5Leave();
377}
378
379/*
380** Change the size of an existing memory allocation.
381**
382** The outer layer memory allocator prevents this routine from
383** being called with pPrior==0.
384**
385** nBytes is always a value obtained from a prior call to
386** memsys5Round(). Hence nBytes is always a non-negative power
387** of two. If nBytes==0 that means that an oversize allocation
388** (an allocation larger than 0x40000000) was requested and this
389** routine should return 0 without freeing pPrior.
390*/
391static void *memsys5Realloc(void *pPrior, int nBytes){
392 int nOld;
393 void *p;
394 assert( pPrior!=0 );
395 assert( (nBytes&(nBytes-1))==0 ); /* EV: R-46199-30249 */
396 assert( nBytes>=0 );
397 if( nBytes==0 ){
398 return 0;
399 }
400 nOld = memsys5Size(pPrior);
401 if( nBytes<=nOld ){
402 return pPrior;
403 }
404 p = memsys5Malloc(nBytes);
405 if( p ){
406 memcpy(p, pPrior, nOld);
407 memsys5Free(pPrior);
408 }
409 return p;
410}
411
412/*
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.
416**
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.
420*/
421static int memsys5Roundup(int n){
422 int iFullSz;
423 if( n<=mem5.szAtom*2 ){
424 if( n<=mem5.szAtom ) return mem5.szAtom;
425 return mem5.szAtom*2;
426 }
427 if( n>0x10000000 ){
428 if( n>0x40000000 ) return 0;
429 if( n>0x20000000 ) return 0x40000000;
430 return 0x20000000;
431 }
432 for(iFullSz=mem5.szAtom*8; iFullSz<n; iFullSz *= 4);
433 if( (iFullSz/2)>=(i64)n ) return iFullSz/2;
434 return iFullSz;
435}
436
437/*
438** Return the ceiling of the logarithm base 2 of iValue.
439**
440** Examples: memsys5Log(1) -> 0
441** memsys5Log(2) -> 1
442** memsys5Log(4) -> 2
443** memsys5Log(5) -> 3
444** memsys5Log(8) -> 3
445** memsys5Log(9) -> 4
446*/
447static int memsys5Log(int iValue){
448 int iLog;
449 for(iLog=0; (iLog<(int)((sizeof(int)*8)-1)) && (1<<iLog)<iValue; iLog++);
450 return iLog;
451}
452
453/*
454** Initialize the memory allocator.
455**
456** This routine is not threadsafe. The caller must be holding a mutex
457** to prevent multiple threads from entering at the same time.
458*/
459static int memsys5Init(void *NotUsed){
460 int ii; /* Loop counter */
461 int nByte; /* Number of bytes of memory available to this allocator */
462 u8 *zByte; /* Memory usable by this allocator */
463 int nMinLog; /* Log base 2 of minimum allocation size in bytes */
464 int iOffset; /* An offset into mem5.aCtrl[] */
465
466 UNUSED_PARAMETER(NotUsed);
467
468 /* For the purposes of this routine, disable the mutex */
469 mem5.mutex = 0;
470
471 /* The size of a Mem5Link object must be a power of two. Verify that
472 ** this is case.
473 */
474 assert( (sizeof(Mem5Link)&(sizeof(Mem5Link)-1))==0 );
475
476 nByte = sqlite3GlobalConfig.nHeap;
477 zByte = (u8*)sqlite3GlobalConfig.pHeap;
478 assert( zByte!=0 ); /* sqlite3_config() does not allow otherwise */
479
480 /* boundaries on sqlite3GlobalConfig.mnReq are enforced in sqlite3_config() */
481 nMinLog = memsys5Log(sqlite3GlobalConfig.mnReq);
482 mem5.szAtom = (1<<nMinLog);
483 while( (int)sizeof(Mem5Link)>mem5.szAtom ){
484 mem5.szAtom = mem5.szAtom << 1;
485 }
486
487 mem5.nBlock = (nByte / (mem5.szAtom+sizeof(u8)));
488 mem5.zPool = zByte;
489 mem5.aCtrl = (u8 *)&mem5.zPool[mem5.nBlock*mem5.szAtom];
490
491 for(ii=0; ii<=LOGMAX; ii++){
492 mem5.aiFreelist[ii] = -1;
493 }
494
495 iOffset = 0;
496 for(ii=LOGMAX; ii>=0; ii--){
497 int nAlloc = (1<<ii);
498 if( (iOffset+nAlloc)<=mem5.nBlock ){
499 mem5.aCtrl[iOffset] = ii | CTRL_FREE;
500 memsys5Link(iOffset, ii);
501 iOffset += nAlloc;
502 }
503 assert((iOffset+nAlloc)>mem5.nBlock);
504 }
505
506 /* If a mutex is required for normal operation, allocate one */
507 if( sqlite3GlobalConfig.bMemstat==0 ){
508 mem5.mutex = sqlite3MutexAlloc(SQLITE_MUTEX_STATIC_MEM);
509 }
510
511 return SQLITE_OK;
512}
513
514/*
515** Deinitialize this module.
516*/
517static void memsys5Shutdown(void *NotUsed){
518 UNUSED_PARAMETER(NotUsed);
519 mem5.mutex = 0;
520 return;
521}
522
523#ifdef SQLITE_TEST
524/*
525** Open the file indicated and write a log of all unfreed memory
526** allocations into that log.
527*/
528void sqlite3Memsys5Dump(const char *zFilename){
529 FILE *out;
530 int i, j, n;
531 int nMinLog;
532
533 if( zFilename==0 || zFilename[0]==0 ){
534 out = stdout;
535 }else{
536 out = fopen(zFilename, "w");
537 if( out==0 ){
538 fprintf(stderr, "** Unable to output memory debug output log: %s **\n",
539 zFilename);
540 return;
541 }
542 }
543 memsys5Enter();
544 nMinLog = memsys5Log(mem5.szAtom);
545 for(i=0; i<=LOGMAX && i+nMinLog<32; i++){
546 for(n=0, j=mem5.aiFreelist[i]; j>=0; j = MEM5LINK(j)->next, n++){}
547 fprintf(out, "freelist items of size %d: %d\n", mem5.szAtom << i, n);
548 }
549 fprintf(out, "mem5.nAlloc = %llu\n", mem5.nAlloc);
550 fprintf(out, "mem5.totalAlloc = %llu\n", mem5.totalAlloc);
551 fprintf(out, "mem5.totalExcess = %llu\n", mem5.totalExcess);
552 fprintf(out, "mem5.currentOut = %u\n", mem5.currentOut);
553 fprintf(out, "mem5.currentCount = %u\n", mem5.currentCount);
554 fprintf(out, "mem5.maxOut = %u\n", mem5.maxOut);
555 fprintf(out, "mem5.maxCount = %u\n", mem5.maxCount);
556 fprintf(out, "mem5.maxRequest = %u\n", mem5.maxRequest);
557 memsys5Leave();
558 if( out==stdout ){
559 fflush(stdout);
560 }else{
561 fclose(out);
562 }
563}
564#endif
565
566/*
567** This routine is the only routine in this file with external
568** linkage. It returns a pointer to a static sqlite3_mem_methods
569** struct populated with the memsys5 methods.
570*/
571const sqlite3_mem_methods *sqlite3MemGetMemsys5(void){
572 static const sqlite3_mem_methods memsys5Methods = {
573 memsys5Malloc,
574 memsys5Free,
575 memsys5Realloc,
576 memsys5Size,
577 memsys5Roundup,
578 memsys5Init,
579 memsys5Shutdown,
580 0
581 };
582 return &memsys5Methods;
583}
584
585#endif /* SQLITE_ENABLE_MEMSYS5 */
586