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 allocations 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 coalesed 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: */
67: typedef struct Mem5Link Mem5Link;
68: struct 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: */
92: static 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: /*
106: ** Performance statistics
107: */
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) */
116:
117: /*
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.
121: */
122: int aiFreelist[LOGMAX+1];
123:
124: /*
125: ** Space for tracking which blocks are checked out and the size
126: ** of each block. One byte per block.
127: */
128: u8 *aCtrl;
129:
130: } mem5;
131:
132: /*
133: ** Access the static variable through a macro for SQLITE_OMIT_WSD
134: */
135: #define mem5 GLOBAL(struct Mem5Global, mem5)
136:
137: /*
138: ** Assuming mem5.zPool is divided up into an array of Mem5Link
139: ** structures, return a pointer to the idx-th such lik.
140: */
141: #define MEM5LINK(idx) ((Mem5Link *)(&mem5.zPool[(idx)*mem5.szAtom]))
142:
143: /*
144: ** Unlink the chunk at mem5.aPool[i] from list it is currently
145: ** on. It should be found on mem5.aiFreelist[iLogsize].
146: */
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 );
152:
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;
159: }
160: if( next>=0 ){
161: MEM5LINK(next)->prev = prev;
162: }
163: }
164:
165: /*
166: ** Link the chunk at mem5.aPool[i] so that is on the iLogsize
167: ** free list.
168: */
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 );
175:
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;
181: }
182: mem5.aiFreelist[iLogsize] = i;
183: }
184:
185: /*
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.
189: */
190: static void memsys5Enter(void){
191: sqlite3_mutex_enter(mem5.mutex);
192: }
193: static void memsys5Leave(void){
194: sqlite3_mutex_leave(mem5.mutex);
195: }
196:
197: /*
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.
201: */
202: static int memsys5Size(void *p){
203: int iSize = 0;
204: if( p ){
205: int i = ((u8 *)p-mem5.zPool)/mem5.szAtom;
206: assert( i>=0 && i<mem5.nBlock );
207: iSize = mem5.szAtom * (1 << (mem5.aCtrl[i]&CTRL_LOGSIZE));
208: }
209: return iSize;
210: }
211:
212: /*
213: ** Find the first entry on the freelist iLogsize. Unlink that
214: ** entry and return its index.
215: */
216: static int memsys5UnlinkFirst(int iLogsize){
217: int i;
218: int iFirst;
219:
220: assert( iLogsize>=0 && iLogsize<=LOGMAX );
221: i = iFirst = mem5.aiFreelist[iLogsize];
222: assert( iFirst>=0 );
223: while( i>0 ){
224: if( i<iFirst ) iFirst = i;
225: i = MEM5LINK(i)->next;
226: }
227: memsys5Unlink(iFirst, iLogsize);
228: return iFirst;
229: }
230:
231: /*
232: ** Return a block of memory of at least nBytes in size.
233: ** Return NULL if unable. Return NULL if nBytes==0.
234: **
235: ** The caller guarantees that nByte positive.
236: **
237: ** The caller has obtained a mutex prior to invoking this
238: ** routine so there is never any chance that two or more
239: ** threads can be in this routine at the same time.
240: */
241: static void *memsys5MallocUnsafe(int nByte){
242: int i; /* Index of a mem5.aPool[] slot */
243: int iBin; /* Index into mem5.aiFreelist[] */
244: int iFullSz; /* Size of allocation rounded up to power of 2 */
245: int iLogsize; /* Log2 of iFullSz/POW2_MIN */
246:
247: /* nByte must be a positive */
248: assert( nByte>0 );
249:
250: /* Keep track of the maximum allocation request. Even unfulfilled
251: ** requests are counted */
252: if( (u32)nByte>mem5.maxRequest ){
253: mem5.maxRequest = nByte;
254: }
255:
256: /* Abort if the requested allocation size is larger than the largest
257: ** power of two that we can represent using 32-bit signed integers.
258: */
259: if( nByte > 0x40000000 ){
260: return 0;
261: }
262:
263: /* Round nByte up to the next valid power of two */
264: for(iFullSz=mem5.szAtom, iLogsize=0; iFullSz<nByte; iFullSz *= 2, iLogsize++){}
265:
266: /* Make sure mem5.aiFreelist[iLogsize] contains at least one free
267: ** block. If not, then split a block of the next larger power of
268: ** two in order to create a new free block of size iLogsize.
269: */
270: for(iBin=iLogsize; mem5.aiFreelist[iBin]<0 && iBin<=LOGMAX; iBin++){}
271: if( iBin>LOGMAX ){
272: testcase( sqlite3GlobalConfig.xLog!=0 );
273: sqlite3_log(SQLITE_NOMEM, "failed to allocate %u bytes", nByte);
274: return 0;
275: }
276: i = memsys5UnlinkFirst(iBin);
277: while( iBin>iLogsize ){
278: int newSize;
279:
280: iBin--;
281: newSize = 1 << iBin;
282: mem5.aCtrl[i+newSize] = CTRL_FREE | iBin;
283: memsys5Link(i+newSize, iBin);
284: }
285: mem5.aCtrl[i] = iLogsize;
286:
287: /* Update allocator performance statistics. */
288: mem5.nAlloc++;
289: mem5.totalAlloc += iFullSz;
290: mem5.totalExcess += iFullSz - nByte;
291: mem5.currentCount++;
292: mem5.currentOut += iFullSz;
293: if( mem5.maxCount<mem5.currentCount ) mem5.maxCount = mem5.currentCount;
294: if( mem5.maxOut<mem5.currentOut ) mem5.maxOut = mem5.currentOut;
295:
296: /* Return a pointer to the allocated memory. */
297: return (void*)&mem5.zPool[i*mem5.szAtom];
298: }
299:
300: /*
301: ** Free an outstanding memory allocation.
302: */
303: static void memsys5FreeUnsafe(void *pOld){
304: u32 size, iLogsize;
305: int iBlock;
306:
307: /* Set iBlock to the index of the block pointed to by pOld in
308: ** the array of mem5.szAtom byte blocks pointed to by mem5.zPool.
309: */
310: iBlock = ((u8 *)pOld-mem5.zPool)/mem5.szAtom;
311:
312: /* Check that the pointer pOld points to a valid, non-free block. */
313: assert( iBlock>=0 && iBlock<mem5.nBlock );
314: assert( ((u8 *)pOld-mem5.zPool)%mem5.szAtom==0 );
315: assert( (mem5.aCtrl[iBlock] & CTRL_FREE)==0 );
316:
317: iLogsize = mem5.aCtrl[iBlock] & CTRL_LOGSIZE;
318: size = 1<<iLogsize;
319: assert( iBlock+size-1<(u32)mem5.nBlock );
320:
321: mem5.aCtrl[iBlock] |= CTRL_FREE;
322: mem5.aCtrl[iBlock+size-1] |= CTRL_FREE;
323: assert( mem5.currentCount>0 );
324: assert( mem5.currentOut>=(size*mem5.szAtom) );
325: mem5.currentCount--;
326: mem5.currentOut -= size*mem5.szAtom;
327: assert( mem5.currentOut>0 || mem5.currentCount==0 );
328: assert( mem5.currentCount>0 || mem5.currentOut==0 );
329:
330: mem5.aCtrl[iBlock] = CTRL_FREE | iLogsize;
331: while( ALWAYS(iLogsize<LOGMAX) ){
332: int iBuddy;
333: if( (iBlock>>iLogsize) & 1 ){
334: iBuddy = iBlock - size;
335: }else{
336: iBuddy = iBlock + size;
337: }
338: assert( iBuddy>=0 );
339: if( (iBuddy+(1<<iLogsize))>mem5.nBlock ) break;
340: if( mem5.aCtrl[iBuddy]!=(CTRL_FREE | iLogsize) ) break;
341: memsys5Unlink(iBuddy, iLogsize);
342: iLogsize++;
343: if( iBuddy<iBlock ){
344: mem5.aCtrl[iBuddy] = CTRL_FREE | iLogsize;
345: mem5.aCtrl[iBlock] = 0;
346: iBlock = iBuddy;
347: }else{
348: mem5.aCtrl[iBlock] = CTRL_FREE | iLogsize;
349: mem5.aCtrl[iBuddy] = 0;
350: }
351: size *= 2;
352: }
353: memsys5Link(iBlock, iLogsize);
354: }
355:
356: /*
357: ** Allocate nBytes of memory
358: */
359: static void *memsys5Malloc(int nBytes){
360: sqlite3_int64 *p = 0;
361: if( nBytes>0 ){
362: memsys5Enter();
363: p = memsys5MallocUnsafe(nBytes);
364: memsys5Leave();
365: }
366: return (void*)p;
367: }
368:
369: /*
370: ** Free memory.
371: **
372: ** The outer layer memory allocator prevents this routine from
373: ** being called with pPrior==0.
374: */
375: static void memsys5Free(void *pPrior){
376: assert( pPrior!=0 );
377: memsys5Enter();
378: memsys5FreeUnsafe(pPrior);
379: memsys5Leave();
380: }
381:
382: /*
383: ** Change the size of an existing memory allocation.
384: **
385: ** The outer layer memory allocator prevents this routine from
386: ** being called with pPrior==0.
387: **
388: ** nBytes is always a value obtained from a prior call to
389: ** memsys5Round(). Hence nBytes is always a non-negative power
390: ** of two. If nBytes==0 that means that an oversize allocation
391: ** (an allocation larger than 0x40000000) was requested and this
392: ** routine should return 0 without freeing pPrior.
393: */
394: static void *memsys5Realloc(void *pPrior, int nBytes){
395: int nOld;
396: void *p;
397: assert( pPrior!=0 );
398: assert( (nBytes&(nBytes-1))==0 ); /* EV: R-46199-30249 */
399: assert( nBytes>=0 );
400: if( nBytes==0 ){
401: return 0;
402: }
403: nOld = memsys5Size(pPrior);
404: if( nBytes<=nOld ){
405: return pPrior;
406: }
407: memsys5Enter();
408: p = memsys5MallocUnsafe(nBytes);
409: if( p ){
410: memcpy(p, pPrior, nOld);
411: memsys5FreeUnsafe(pPrior);
412: }
413: memsys5Leave();
414: return p;
415: }
416:
417: /*
418: ** Round up a request size to the next valid allocation size. If
419: ** the allocation is too large to be handled by this allocation system,
420: ** return 0.
421: **
422: ** All allocations must be a power of two and must be expressed by a
423: ** 32-bit signed integer. Hence the largest allocation is 0x40000000
424: ** or 1073741824 bytes.
425: */
426: static int memsys5Roundup(int n){
427: int iFullSz;
428: if( n > 0x40000000 ) return 0;
429: for(iFullSz=mem5.szAtom; iFullSz<n; iFullSz *= 2);
430: return iFullSz;
431: }
432:
433: /*
434: ** Return the ceiling of the logarithm base 2 of iValue.
435: **
436: ** Examples: memsys5Log(1) -> 0
437: ** memsys5Log(2) -> 1
438: ** memsys5Log(4) -> 2
439: ** memsys5Log(5) -> 3
440: ** memsys5Log(8) -> 3
441: ** memsys5Log(9) -> 4
442: */
443: static int memsys5Log(int iValue){
444: int iLog;
445: for(iLog=0; (iLog<(int)((sizeof(int)*8)-1)) && (1<<iLog)<iValue; iLog++);
446: return iLog;
447: }
448:
449: /*
450: ** Initialize the memory allocator.
451: **
452: ** This routine is not threadsafe. The caller must be holding a mutex
453: ** to prevent multiple threads from entering at the same time.
454: */
455: static int memsys5Init(void *NotUsed){
456: int ii; /* Loop counter */
457: int nByte; /* Number of bytes of memory available to this allocator */
458: u8 *zByte; /* Memory usable by this allocator */
459: int nMinLog; /* Log base 2 of minimum allocation size in bytes */
460: int iOffset; /* An offset into mem5.aCtrl[] */
461:
462: UNUSED_PARAMETER(NotUsed);
463:
464: /* For the purposes of this routine, disable the mutex */
465: mem5.mutex = 0;
466:
467: /* The size of a Mem5Link object must be a power of two. Verify that
468: ** this is case.
469: */
470: assert( (sizeof(Mem5Link)&(sizeof(Mem5Link)-1))==0 );
471:
472: nByte = sqlite3GlobalConfig.nHeap;
473: zByte = (u8*)sqlite3GlobalConfig.pHeap;
474: assert( zByte!=0 ); /* sqlite3_config() does not allow otherwise */
475:
476: /* boundaries on sqlite3GlobalConfig.mnReq are enforced in sqlite3_config() */
477: nMinLog = memsys5Log(sqlite3GlobalConfig.mnReq);
478: mem5.szAtom = (1<<nMinLog);
479: while( (int)sizeof(Mem5Link)>mem5.szAtom ){
480: mem5.szAtom = mem5.szAtom << 1;
481: }
482:
483: mem5.nBlock = (nByte / (mem5.szAtom+sizeof(u8)));
484: mem5.zPool = zByte;
485: mem5.aCtrl = (u8 *)&mem5.zPool[mem5.nBlock*mem5.szAtom];
486:
487: for(ii=0; ii<=LOGMAX; ii++){
488: mem5.aiFreelist[ii] = -1;
489: }
490:
491: iOffset = 0;
492: for(ii=LOGMAX; ii>=0; ii--){
493: int nAlloc = (1<<ii);
494: if( (iOffset+nAlloc)<=mem5.nBlock ){
495: mem5.aCtrl[iOffset] = ii | CTRL_FREE;
496: memsys5Link(iOffset, ii);
497: iOffset += nAlloc;
498: }
499: assert((iOffset+nAlloc)>mem5.nBlock);
500: }
501:
502: /* If a mutex is required for normal operation, allocate one */
503: if( sqlite3GlobalConfig.bMemstat==0 ){
504: mem5.mutex = sqlite3MutexAlloc(SQLITE_MUTEX_STATIC_MEM);
505: }
506:
507: return SQLITE_OK;
508: }
509:
510: /*
511: ** Deinitialize this module.
512: */
513: static void memsys5Shutdown(void *NotUsed){
514: UNUSED_PARAMETER(NotUsed);
515: mem5.mutex = 0;
516: return;
517: }
518:
519: #ifdef SQLITE_TEST
520: /*
521: ** Open the file indicated and write a log of all unfreed memory
522: ** allocations into that log.
523: */
524: void sqlite3Memsys5Dump(const char *zFilename){
525: FILE *out;
526: int i, j, n;
527: int nMinLog;
528:
529: if( zFilename==0 || zFilename[0]==0 ){
530: out = stdout;
531: }else{
532: out = fopen(zFilename, "w");
533: if( out==0 ){
534: fprintf(stderr, "** Unable to output memory debug output log: %s **\n",
535: zFilename);
536: return;
537: }
538: }
539: memsys5Enter();
540: nMinLog = memsys5Log(mem5.szAtom);
541: for(i=0; i<=LOGMAX && i+nMinLog<32; i++){
542: for(n=0, j=mem5.aiFreelist[i]; j>=0; j = MEM5LINK(j)->next, n++){}
543: fprintf(out, "freelist items of size %d: %d\n", mem5.szAtom << i, n);
544: }
545: fprintf(out, "mem5.nAlloc = %llu\n", mem5.nAlloc);
546: fprintf(out, "mem5.totalAlloc = %llu\n", mem5.totalAlloc);
547: fprintf(out, "mem5.totalExcess = %llu\n", mem5.totalExcess);
548: fprintf(out, "mem5.currentOut = %u\n", mem5.currentOut);
549: fprintf(out, "mem5.currentCount = %u\n", mem5.currentCount);
550: fprintf(out, "mem5.maxOut = %u\n", mem5.maxOut);
551: fprintf(out, "mem5.maxCount = %u\n", mem5.maxCount);
552: fprintf(out, "mem5.maxRequest = %u\n", mem5.maxRequest);
553: memsys5Leave();
554: if( out==stdout ){
555: fflush(stdout);
556: }else{
557: fclose(out);
558: }
559: }
560: #endif
561:
562: /*
563: ** This routine is the only routine in this file with external
564: ** linkage. It returns a pointer to a static sqlite3_mem_methods
565: ** struct populated with the memsys5 methods.
566: */
567: const sqlite3_mem_methods *sqlite3MemGetMemsys5(void){
568: static const sqlite3_mem_methods memsys5Methods = {
569: memsys5Malloc,
570: memsys5Free,
571: memsys5Realloc,
572: memsys5Size,
573: memsys5Roundup,
574: memsys5Init,
575: memsys5Shutdown,
576: 0
577: };
578: return &memsys5Methods;
579: }
580:
581: #endif /* SQLITE_ENABLE_MEMSYS5 */
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>
![[BACK]](/icons/cvsweb/back.gif){kind=icon}
Return to mem5.c CVS log ![[TXT]](/icons/cvsweb/text.gif){kind=icon}
![[DIR]](/icons/cvsweb/dir.gif){kind=icon}
Up to [ELWIX - Embedded LightWeight unIX -] / embedaddon / sqlite3 / src