blob: 02f665e9c311050e6acb916eeae5187e67d453f6 [file] [log] [blame]
drh0d180202008-02-14 23:26:56 +00001/*
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
drh4c5514d2009-08-18 01:54:19 +000016** use of malloc(). The application gives SQLite a block of memory
danielk1977c66c0e12008-06-25 14:26:07 +000017** 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.
drh0d180202008-02-14 23:26:56 +000022**
danielk1977c66c0e12008-06-25 14:26:07 +000023** This version of the memory allocation subsystem is included
24** in the build only if SQLITE_ENABLE_MEMSYS5 is defined.
drh0d180202008-02-14 23:26:56 +000025**
drh4c5514d2009-08-18 01:54:19 +000026** 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. To adjacent and aligned free blocks are coalesced into a single
31** block of the next larger size.
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.
drh0d180202008-02-14 23:26:56 +000050*/
51#include "sqliteInt.h"
52
53/*
54** This version of the memory allocator is used only when
drhd1370b62008-10-28 18:58:20 +000055** SQLITE_ENABLE_MEMSYS5 is defined.
drh0d180202008-02-14 23:26:56 +000056*/
danielk1977c66c0e12008-06-25 14:26:07 +000057#ifdef SQLITE_ENABLE_MEMSYS5
drh0d180202008-02-14 23:26:56 +000058
59/*
drh2d7636e2008-02-16 16:21:45 +000060** 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.
drh4c5514d2009-08-18 01:54:19 +000063**
64** The size of this object must be a power of two. That fact is
65** verified in memsys5Init().
drh2d7636e2008-02-16 16:21:45 +000066*/
danielk19775099be52008-06-27 13:27:03 +000067typedef struct Mem5Link Mem5Link;
68struct Mem5Link {
69 int next; /* Index of next free chunk */
70 int prev; /* Index of previous free chunk */
drh0d180202008-02-14 23:26:56 +000071};
72
73/*
danielk19775099be52008-06-27 13:27:03 +000074** Maximum size of any allocation is ((1<<LOGMAX)*mem5.nAtom). Since
drh4c5514d2009-08-18 01:54:19 +000075** mem5.nAtom is always at least 8 and 32-bit integers are used,
76** it is not actually possible to reach this limit.
drh2d7636e2008-02-16 16:21:45 +000077*/
danielk19775099be52008-06-27 13:27:03 +000078#define LOGMAX 30
drh2d7636e2008-02-16 16:21:45 +000079
80/*
danielk1977c66c0e12008-06-25 14:26:07 +000081** Masks used for mem5.aCtrl[] elements.
drh2d7636e2008-02-16 16:21:45 +000082*/
83#define CTRL_LOGSIZE 0x1f /* Log2 Size of this block relative to POW2_MIN */
84#define CTRL_FREE 0x20 /* True if not checked out */
85
86/*
drh0d180202008-02-14 23:26:56 +000087** All of the static variables used by this module are collected
danielk1977c66c0e12008-06-25 14:26:07 +000088** into a single structure named "mem5". This is to keep the
drh0d180202008-02-14 23:26:56 +000089** static variables organized and to reduce namespace pollution
90** when this module is combined with other in the amalgamation.
91*/
danielk19775c8f8582008-09-02 10:22:00 +000092static SQLITE_WSD struct Mem5Global {
drh0d180202008-02-14 23:26:56 +000093 /*
danielk197723bf0f42008-09-02 17:52:51 +000094 ** Memory available for allocation
drh0d180202008-02-14 23:26:56 +000095 */
danielk197723bf0f42008-09-02 17:52:51 +000096 int nAtom; /* Smallest possible allocation in bytes */
97 int nBlock; /* Number of nAtom sized blocks in zPool */
drh4c5514d2009-08-18 01:54:19 +000098 u8 *zPool; /* Memory available to be allocated */
drh0d180202008-02-14 23:26:56 +000099
100 /*
101 ** Mutex to control access to the memory allocation subsystem.
102 */
103 sqlite3_mutex *mutex;
drh2d7636e2008-02-16 16:21:45 +0000104
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) */
drh0d180202008-02-14 23:26:56 +0000116
117 /*
drh2d7636e2008-02-16 16:21:45 +0000118 ** Lists of free blocks of various sizes.
drh0d180202008-02-14 23:26:56 +0000119 */
danielk19775099be52008-06-27 13:27:03 +0000120 int aiFreelist[LOGMAX+1];
drh0d180202008-02-14 23:26:56 +0000121
122 /*
drh2d7636e2008-02-16 16:21:45 +0000123 ** Space for tracking which blocks are checked out and the size
124 ** of each block. One byte per block.
drh0d180202008-02-14 23:26:56 +0000125 */
danielk1977c66c0e12008-06-25 14:26:07 +0000126 u8 *aCtrl;
drh0d180202008-02-14 23:26:56 +0000127
drh4c5514d2009-08-18 01:54:19 +0000128} mem5 = { 0 };
danielk19775c8f8582008-09-02 10:22:00 +0000129
drh4c5514d2009-08-18 01:54:19 +0000130/*
131** Access the static variable through a macro for SQLITE_OMIT_WSD
132*/
danielk19775c8f8582008-09-02 10:22:00 +0000133#define mem5 GLOBAL(struct Mem5Global, mem5)
drh0d180202008-02-14 23:26:56 +0000134
drh4c5514d2009-08-18 01:54:19 +0000135/*
136** Assuming mem5.zPool is divided up into an array of Mem5Link
137** structures, return a pointer to the idx-th such lik.
138*/
danielk19775099be52008-06-27 13:27:03 +0000139#define MEM5LINK(idx) ((Mem5Link *)(&mem5.zPool[(idx)*mem5.nAtom]))
140
drh0d180202008-02-14 23:26:56 +0000141/*
danielk1977c66c0e12008-06-25 14:26:07 +0000142** Unlink the chunk at mem5.aPool[i] from list it is currently
143** on. It should be found on mem5.aiFreelist[iLogsize].
drh0d180202008-02-14 23:26:56 +0000144*/
drh2d7636e2008-02-16 16:21:45 +0000145static void memsys5Unlink(int i, int iLogsize){
146 int next, prev;
danielk1977c66c0e12008-06-25 14:26:07 +0000147 assert( i>=0 && i<mem5.nBlock );
danielk19775099be52008-06-27 13:27:03 +0000148 assert( iLogsize>=0 && iLogsize<=LOGMAX );
danielk1977c66c0e12008-06-25 14:26:07 +0000149 assert( (mem5.aCtrl[i] & CTRL_LOGSIZE)==iLogsize );
drh2d7636e2008-02-16 16:21:45 +0000150
danielk19775099be52008-06-27 13:27:03 +0000151 next = MEM5LINK(i)->next;
152 prev = MEM5LINK(i)->prev;
drh2d7636e2008-02-16 16:21:45 +0000153 if( prev<0 ){
danielk1977c66c0e12008-06-25 14:26:07 +0000154 mem5.aiFreelist[iLogsize] = next;
drh0d180202008-02-14 23:26:56 +0000155 }else{
danielk19775099be52008-06-27 13:27:03 +0000156 MEM5LINK(prev)->next = next;
drh0d180202008-02-14 23:26:56 +0000157 }
drh2d7636e2008-02-16 16:21:45 +0000158 if( next>=0 ){
danielk19775099be52008-06-27 13:27:03 +0000159 MEM5LINK(next)->prev = prev;
drh0d180202008-02-14 23:26:56 +0000160 }
drh0d180202008-02-14 23:26:56 +0000161}
162
163/*
danielk1977c66c0e12008-06-25 14:26:07 +0000164** Link the chunk at mem5.aPool[i] so that is on the iLogsize
drh2d7636e2008-02-16 16:21:45 +0000165** free list.
drh0d180202008-02-14 23:26:56 +0000166*/
drh2d7636e2008-02-16 16:21:45 +0000167static void memsys5Link(int i, int iLogsize){
168 int x;
danielk1977c66c0e12008-06-25 14:26:07 +0000169 assert( sqlite3_mutex_held(mem5.mutex) );
170 assert( i>=0 && i<mem5.nBlock );
danielk19775099be52008-06-27 13:27:03 +0000171 assert( iLogsize>=0 && iLogsize<=LOGMAX );
danielk1977c66c0e12008-06-25 14:26:07 +0000172 assert( (mem5.aCtrl[i] & CTRL_LOGSIZE)==iLogsize );
drh0d180202008-02-14 23:26:56 +0000173
danielk19775099be52008-06-27 13:27:03 +0000174 x = MEM5LINK(i)->next = mem5.aiFreelist[iLogsize];
175 MEM5LINK(i)->prev = -1;
drh2d7636e2008-02-16 16:21:45 +0000176 if( x>=0 ){
danielk1977c66c0e12008-06-25 14:26:07 +0000177 assert( x<mem5.nBlock );
danielk19775099be52008-06-27 13:27:03 +0000178 MEM5LINK(x)->prev = i;
drh0d180202008-02-14 23:26:56 +0000179 }
danielk1977c66c0e12008-06-25 14:26:07 +0000180 mem5.aiFreelist[iLogsize] = i;
drh0d180202008-02-14 23:26:56 +0000181}
182
183/*
danielk19776b39c2e2008-06-25 14:57:53 +0000184** If the STATIC_MEM mutex is not already held, obtain it now. The mutex
185** will already be held (obtained by code in malloc.c) if
danielk1977075c23a2008-09-01 18:34:20 +0000186** sqlite3GlobalConfig.bMemStat is true.
drh0d180202008-02-14 23:26:56 +0000187*/
drh2d7636e2008-02-16 16:21:45 +0000188static void memsys5Enter(void){
danielk1977075c23a2008-09-01 18:34:20 +0000189 if( sqlite3GlobalConfig.bMemstat==0 && mem5.mutex==0 ){
danielk19776b39c2e2008-06-25 14:57:53 +0000190 mem5.mutex = sqlite3MutexAlloc(SQLITE_MUTEX_STATIC_MEM);
191 }
192 sqlite3_mutex_enter(mem5.mutex);
drh0d180202008-02-14 23:26:56 +0000193}
danielk1977c66c0e12008-06-25 14:26:07 +0000194static void memsys5Leave(void){
danielk19776b39c2e2008-06-25 14:57:53 +0000195 sqlite3_mutex_leave(mem5.mutex);
drh0d180202008-02-14 23:26:56 +0000196}
197
198/*
drh0d180202008-02-14 23:26:56 +0000199** Return the size of an outstanding allocation, in bytes. The
200** size returned omits the 8-byte header overhead. This only
201** works for chunks that are currently checked out.
202*/
danielk1977c66c0e12008-06-25 14:26:07 +0000203static int memsys5Size(void *p){
drh0d180202008-02-14 23:26:56 +0000204 int iSize = 0;
205 if( p ){
danielk19775099be52008-06-27 13:27:03 +0000206 int i = ((u8 *)p-mem5.zPool)/mem5.nAtom;
danielk1977c66c0e12008-06-25 14:26:07 +0000207 assert( i>=0 && i<mem5.nBlock );
danielk19775099be52008-06-27 13:27:03 +0000208 iSize = mem5.nAtom * (1 << (mem5.aCtrl[i]&CTRL_LOGSIZE));
drh0d180202008-02-14 23:26:56 +0000209 }
210 return iSize;
211}
212
213/*
drh2d7636e2008-02-16 16:21:45 +0000214** Find the first entry on the freelist iLogsize. Unlink that
215** entry and return its index.
drh0d180202008-02-14 23:26:56 +0000216*/
drh2d7636e2008-02-16 16:21:45 +0000217static int memsys5UnlinkFirst(int iLogsize){
218 int i;
219 int iFirst;
drh0d180202008-02-14 23:26:56 +0000220
danielk19775099be52008-06-27 13:27:03 +0000221 assert( iLogsize>=0 && iLogsize<=LOGMAX );
danielk1977c66c0e12008-06-25 14:26:07 +0000222 i = iFirst = mem5.aiFreelist[iLogsize];
drh2d7636e2008-02-16 16:21:45 +0000223 assert( iFirst>=0 );
224 while( i>0 ){
225 if( i<iFirst ) iFirst = i;
danielk19775099be52008-06-27 13:27:03 +0000226 i = MEM5LINK(i)->next;
drh0d180202008-02-14 23:26:56 +0000227 }
drh2d7636e2008-02-16 16:21:45 +0000228 memsys5Unlink(iFirst, iLogsize);
229 return iFirst;
drh0d180202008-02-14 23:26:56 +0000230}
231
232/*
233** Return a block of memory of at least nBytes in size.
drh4c5514d2009-08-18 01:54:19 +0000234** Return NULL if unable. Return NULL if nBytes==0.
235**
236** The caller guarantees that nByte positive.
237**
238** The caller has obtained a mutex prior to invoking this
239** routine so there is never any chance that two or more
240** threads can be in this routine at the same time.
drh0d180202008-02-14 23:26:56 +0000241*/
danielk1977c66c0e12008-06-25 14:26:07 +0000242static void *memsys5MallocUnsafe(int nByte){
243 int i; /* Index of a mem5.aPool[] slot */
244 int iBin; /* Index into mem5.aiFreelist[] */
drh2d7636e2008-02-16 16:21:45 +0000245 int iFullSz; /* Size of allocation rounded up to power of 2 */
246 int iLogsize; /* Log2 of iFullSz/POW2_MIN */
drh0d180202008-02-14 23:26:56 +0000247
drh4c5514d2009-08-18 01:54:19 +0000248 /* nByte must be a positive */
249 assert( nByte>0 );
250
drheee4c8c2008-02-18 22:24:57 +0000251 /* Keep track of the maximum allocation request. Even unfulfilled
252 ** requests are counted */
danielk197700e13612008-11-17 19:18:54 +0000253 if( (u32)nByte>mem5.maxRequest ){
danielk1977c66c0e12008-06-25 14:26:07 +0000254 mem5.maxRequest = nByte;
drheee4c8c2008-02-18 22:24:57 +0000255 }
256
drh4c5514d2009-08-18 01:54:19 +0000257 /* Abort if the size is too great */
258 if( nByte > 0x40000000 ){
259 return 0;
260 }
261
drheee4c8c2008-02-18 22:24:57 +0000262 /* Round nByte up to the next valid power of two */
danielk19775099be52008-06-27 13:27:03 +0000263 for(iFullSz=mem5.nAtom, iLogsize=0; iFullSz<nByte; iFullSz *= 2, iLogsize++){}
drh0d180202008-02-14 23:26:56 +0000264
danielk1977c66c0e12008-06-25 14:26:07 +0000265 /* Make sure mem5.aiFreelist[iLogsize] contains at least one free
drheee4c8c2008-02-18 22:24:57 +0000266 ** block. If not, then split a block of the next larger power of
267 ** two in order to create a new free block of size iLogsize.
268 */
danielk19775099be52008-06-27 13:27:03 +0000269 for(iBin=iLogsize; mem5.aiFreelist[iBin]<0 && iBin<=LOGMAX; iBin++){}
270 if( iBin>LOGMAX ) return 0;
drh2d7636e2008-02-16 16:21:45 +0000271 i = memsys5UnlinkFirst(iBin);
272 while( iBin>iLogsize ){
273 int newSize;
274
275 iBin--;
276 newSize = 1 << iBin;
danielk1977c66c0e12008-06-25 14:26:07 +0000277 mem5.aCtrl[i+newSize] = CTRL_FREE | iBin;
drh2d7636e2008-02-16 16:21:45 +0000278 memsys5Link(i+newSize, iBin);
drh0d180202008-02-14 23:26:56 +0000279 }
danielk1977c66c0e12008-06-25 14:26:07 +0000280 mem5.aCtrl[i] = iLogsize;
drh0d180202008-02-14 23:26:56 +0000281
drheee4c8c2008-02-18 22:24:57 +0000282 /* Update allocator performance statistics. */
danielk1977c66c0e12008-06-25 14:26:07 +0000283 mem5.nAlloc++;
284 mem5.totalAlloc += iFullSz;
285 mem5.totalExcess += iFullSz - nByte;
286 mem5.currentCount++;
287 mem5.currentOut += iFullSz;
288 if( mem5.maxCount<mem5.currentCount ) mem5.maxCount = mem5.currentCount;
289 if( mem5.maxOut<mem5.currentOut ) mem5.maxOut = mem5.currentOut;
drh0d180202008-02-14 23:26:56 +0000290
drheee4c8c2008-02-18 22:24:57 +0000291 /* Return a pointer to the allocated memory. */
danielk19775099be52008-06-27 13:27:03 +0000292 return (void*)&mem5.zPool[i*mem5.nAtom];
drh0d180202008-02-14 23:26:56 +0000293}
294
295/*
296** Free an outstanding memory allocation.
297*/
danielk1977c66c0e12008-06-25 14:26:07 +0000298static void memsys5FreeUnsafe(void *pOld){
drh2d7636e2008-02-16 16:21:45 +0000299 u32 size, iLogsize;
drh4c5514d2009-08-18 01:54:19 +0000300 int iBlock;
drh0d180202008-02-14 23:26:56 +0000301
danielk19775099be52008-06-27 13:27:03 +0000302 /* Set iBlock to the index of the block pointed to by pOld in
303 ** the array of mem5.nAtom byte blocks pointed to by mem5.zPool.
304 */
305 iBlock = ((u8 *)pOld-mem5.zPool)/mem5.nAtom;
306
307 /* Check that the pointer pOld points to a valid, non-free block. */
308 assert( iBlock>=0 && iBlock<mem5.nBlock );
309 assert( ((u8 *)pOld-mem5.zPool)%mem5.nAtom==0 );
310 assert( (mem5.aCtrl[iBlock] & CTRL_FREE)==0 );
311
312 iLogsize = mem5.aCtrl[iBlock] & CTRL_LOGSIZE;
drh2d7636e2008-02-16 16:21:45 +0000313 size = 1<<iLogsize;
danielk197700e13612008-11-17 19:18:54 +0000314 assert( iBlock+size-1<(u32)mem5.nBlock );
danielk19775099be52008-06-27 13:27:03 +0000315
316 mem5.aCtrl[iBlock] |= CTRL_FREE;
317 mem5.aCtrl[iBlock+size-1] |= CTRL_FREE;
danielk1977c66c0e12008-06-25 14:26:07 +0000318 assert( mem5.currentCount>0 );
danielk197700e13612008-11-17 19:18:54 +0000319 assert( mem5.currentOut>=(size*mem5.nAtom) );
danielk1977c66c0e12008-06-25 14:26:07 +0000320 mem5.currentCount--;
danielk19775099be52008-06-27 13:27:03 +0000321 mem5.currentOut -= size*mem5.nAtom;
danielk1977c66c0e12008-06-25 14:26:07 +0000322 assert( mem5.currentOut>0 || mem5.currentCount==0 );
323 assert( mem5.currentCount>0 || mem5.currentOut==0 );
drh2d7636e2008-02-16 16:21:45 +0000324
danielk19775099be52008-06-27 13:27:03 +0000325 mem5.aCtrl[iBlock] = CTRL_FREE | iLogsize;
326 while( iLogsize<LOGMAX ){
drh2d7636e2008-02-16 16:21:45 +0000327 int iBuddy;
danielk19775099be52008-06-27 13:27:03 +0000328 if( (iBlock>>iLogsize) & 1 ){
329 iBuddy = iBlock - size;
drh2d7636e2008-02-16 16:21:45 +0000330 }else{
danielk19775099be52008-06-27 13:27:03 +0000331 iBuddy = iBlock + size;
drh0d180202008-02-14 23:26:56 +0000332 }
danielk19775099be52008-06-27 13:27:03 +0000333 assert( iBuddy>=0 );
334 if( (iBuddy+(1<<iLogsize))>mem5.nBlock ) break;
danielk1977c66c0e12008-06-25 14:26:07 +0000335 if( mem5.aCtrl[iBuddy]!=(CTRL_FREE | iLogsize) ) break;
drh2d7636e2008-02-16 16:21:45 +0000336 memsys5Unlink(iBuddy, iLogsize);
337 iLogsize++;
danielk19775099be52008-06-27 13:27:03 +0000338 if( iBuddy<iBlock ){
danielk1977c66c0e12008-06-25 14:26:07 +0000339 mem5.aCtrl[iBuddy] = CTRL_FREE | iLogsize;
danielk19775099be52008-06-27 13:27:03 +0000340 mem5.aCtrl[iBlock] = 0;
341 iBlock = iBuddy;
drh2d7636e2008-02-16 16:21:45 +0000342 }else{
danielk19775099be52008-06-27 13:27:03 +0000343 mem5.aCtrl[iBlock] = CTRL_FREE | iLogsize;
danielk1977c66c0e12008-06-25 14:26:07 +0000344 mem5.aCtrl[iBuddy] = 0;
drh0d180202008-02-14 23:26:56 +0000345 }
drh2d7636e2008-02-16 16:21:45 +0000346 size *= 2;
drh0d180202008-02-14 23:26:56 +0000347 }
danielk19775099be52008-06-27 13:27:03 +0000348 memsys5Link(iBlock, iLogsize);
drh0d180202008-02-14 23:26:56 +0000349}
350
351/*
352** Allocate nBytes of memory
353*/
danielk1977c66c0e12008-06-25 14:26:07 +0000354static void *memsys5Malloc(int nBytes){
drh0d180202008-02-14 23:26:56 +0000355 sqlite3_int64 *p = 0;
356 if( nBytes>0 ){
drh2d7636e2008-02-16 16:21:45 +0000357 memsys5Enter();
danielk1977c66c0e12008-06-25 14:26:07 +0000358 p = memsys5MallocUnsafe(nBytes);
359 memsys5Leave();
drh0d180202008-02-14 23:26:56 +0000360 }
361 return (void*)p;
362}
363
364/*
365** Free memory.
drh4c5514d2009-08-18 01:54:19 +0000366**
367** The outer layer memory allocator prevents this routine from
368** being called with pPrior==0.
drh0d180202008-02-14 23:26:56 +0000369*/
danielk1977c66c0e12008-06-25 14:26:07 +0000370static void memsys5Free(void *pPrior){
drh4c5514d2009-08-18 01:54:19 +0000371 assert( pPrior!=0 );
danielk1977c66c0e12008-06-25 14:26:07 +0000372 memsys5Enter();
373 memsys5FreeUnsafe(pPrior);
374 memsys5Leave();
drh0d180202008-02-14 23:26:56 +0000375}
376
377/*
drh4c5514d2009-08-18 01:54:19 +0000378** Change the size of an existing memory allocation.
379**
380** The outer layer memory allocator prevents this routine from
381** being called with pPrior==0.
drh0d180202008-02-14 23:26:56 +0000382*/
danielk1977c66c0e12008-06-25 14:26:07 +0000383static void *memsys5Realloc(void *pPrior, int nBytes){
drh0d180202008-02-14 23:26:56 +0000384 int nOld;
385 void *p;
drh4c5514d2009-08-18 01:54:19 +0000386 assert( pPrior!=0 );
drh0d180202008-02-14 23:26:56 +0000387 if( nBytes<=0 ){
danielk1977c66c0e12008-06-25 14:26:07 +0000388 memsys5Free(pPrior);
drh0d180202008-02-14 23:26:56 +0000389 return 0;
390 }
danielk1977c66c0e12008-06-25 14:26:07 +0000391 nOld = memsys5Size(pPrior);
drh2d7636e2008-02-16 16:21:45 +0000392 if( nBytes<=nOld ){
drh0d180202008-02-14 23:26:56 +0000393 return pPrior;
394 }
danielk1977c66c0e12008-06-25 14:26:07 +0000395 memsys5Enter();
396 p = memsys5MallocUnsafe(nBytes);
drh0d180202008-02-14 23:26:56 +0000397 if( p ){
drh2d7636e2008-02-16 16:21:45 +0000398 memcpy(p, pPrior, nOld);
danielk1977c66c0e12008-06-25 14:26:07 +0000399 memsys5FreeUnsafe(pPrior);
drh0d180202008-02-14 23:26:56 +0000400 }
danielk1977c66c0e12008-06-25 14:26:07 +0000401 memsys5Leave();
drh0d180202008-02-14 23:26:56 +0000402 return p;
403}
404
405/*
drh4c5514d2009-08-18 01:54:19 +0000406** Round up a request size to the next valid allocation size. If
407** the allocation is too large to be handled by this allocation system,
408** return 0.
danielk1977c66c0e12008-06-25 14:26:07 +0000409*/
410static int memsys5Roundup(int n){
411 int iFullSz;
drh4c5514d2009-08-18 01:54:19 +0000412 if( n > 0x40000000 ) return 0;
danielk19775099be52008-06-27 13:27:03 +0000413 for(iFullSz=mem5.nAtom; iFullSz<n; iFullSz *= 2);
danielk1977c66c0e12008-06-25 14:26:07 +0000414 return iFullSz;
415}
416
drh4c5514d2009-08-18 01:54:19 +0000417/*
418** Return the logarithm base 2 of iValue.
419*/
danielk19775099be52008-06-27 13:27:03 +0000420static int memsys5Log(int iValue){
421 int iLog;
422 for(iLog=0; (1<<iLog)<iValue; iLog++);
423 return iLog;
424}
425
danielk1977c66c0e12008-06-25 14:26:07 +0000426/*
427** Initialize this module.
428*/
429static int memsys5Init(void *NotUsed){
danielk19775099be52008-06-27 13:27:03 +0000430 int ii;
danielk1977075c23a2008-09-01 18:34:20 +0000431 int nByte = sqlite3GlobalConfig.nHeap;
432 u8 *zByte = (u8 *)sqlite3GlobalConfig.pHeap;
danielk19775099be52008-06-27 13:27:03 +0000433 int nMinLog; /* Log of minimum allocation size in bytes*/
434 int iOffset;
435
danielk1977a03396a2008-11-19 14:35:46 +0000436 UNUSED_PARAMETER(NotUsed);
437
danielk19770d84e5b2008-06-27 14:05:24 +0000438 if( !zByte ){
439 return SQLITE_ERROR;
440 }
441
danielk1977075c23a2008-09-01 18:34:20 +0000442 nMinLog = memsys5Log(sqlite3GlobalConfig.mnReq);
danielk19775099be52008-06-27 13:27:03 +0000443 mem5.nAtom = (1<<nMinLog);
danielk197700e13612008-11-17 19:18:54 +0000444 while( (int)sizeof(Mem5Link)>mem5.nAtom ){
danielk19775099be52008-06-27 13:27:03 +0000445 mem5.nAtom = mem5.nAtom << 1;
446 }
447
448 mem5.nBlock = (nByte / (mem5.nAtom+sizeof(u8)));
449 mem5.zPool = zByte;
450 mem5.aCtrl = (u8 *)&mem5.zPool[mem5.nBlock*mem5.nAtom];
451
452 for(ii=0; ii<=LOGMAX; ii++){
453 mem5.aiFreelist[ii] = -1;
454 }
455
456 iOffset = 0;
457 for(ii=LOGMAX; ii>=0; ii--){
458 int nAlloc = (1<<ii);
459 if( (iOffset+nAlloc)<=mem5.nBlock ){
460 mem5.aCtrl[iOffset] = ii | CTRL_FREE;
461 memsys5Link(iOffset, ii);
462 iOffset += nAlloc;
463 }
464 assert((iOffset+nAlloc)>mem5.nBlock);
465 }
466
danielk1977c66c0e12008-06-25 14:26:07 +0000467 return SQLITE_OK;
468}
469
470/*
471** Deinitialize this module.
472*/
473static void memsys5Shutdown(void *NotUsed){
danielk1977a03396a2008-11-19 14:35:46 +0000474 UNUSED_PARAMETER(NotUsed);
danielk1977c66c0e12008-06-25 14:26:07 +0000475 return;
476}
477
478/*
drh0d180202008-02-14 23:26:56 +0000479** Open the file indicated and write a log of all unfreed memory
480** allocations into that log.
481*/
danielk1977c66c0e12008-06-25 14:26:07 +0000482void sqlite3Memsys5Dump(const char *zFilename){
drh0d180202008-02-14 23:26:56 +0000483#ifdef SQLITE_DEBUG
484 FILE *out;
drh2d7636e2008-02-16 16:21:45 +0000485 int i, j, n;
danielk19775099be52008-06-27 13:27:03 +0000486 int nMinLog;
drh2d7636e2008-02-16 16:21:45 +0000487
drh0d180202008-02-14 23:26:56 +0000488 if( zFilename==0 || zFilename[0]==0 ){
489 out = stdout;
490 }else{
491 out = fopen(zFilename, "w");
492 if( out==0 ){
493 fprintf(stderr, "** Unable to output memory debug output log: %s **\n",
494 zFilename);
495 return;
496 }
497 }
drh2d7636e2008-02-16 16:21:45 +0000498 memsys5Enter();
danielk19775099be52008-06-27 13:27:03 +0000499 nMinLog = memsys5Log(mem5.nAtom);
500 for(i=0; i<=LOGMAX && i+nMinLog<32; i++){
501 for(n=0, j=mem5.aiFreelist[i]; j>=0; j = MEM5LINK(j)->next, n++){}
502 fprintf(out, "freelist items of size %d: %d\n", mem5.nAtom << i, n);
drh0d180202008-02-14 23:26:56 +0000503 }
danielk1977c66c0e12008-06-25 14:26:07 +0000504 fprintf(out, "mem5.nAlloc = %llu\n", mem5.nAlloc);
505 fprintf(out, "mem5.totalAlloc = %llu\n", mem5.totalAlloc);
506 fprintf(out, "mem5.totalExcess = %llu\n", mem5.totalExcess);
507 fprintf(out, "mem5.currentOut = %u\n", mem5.currentOut);
508 fprintf(out, "mem5.currentCount = %u\n", mem5.currentCount);
509 fprintf(out, "mem5.maxOut = %u\n", mem5.maxOut);
510 fprintf(out, "mem5.maxCount = %u\n", mem5.maxCount);
511 fprintf(out, "mem5.maxRequest = %u\n", mem5.maxRequest);
512 memsys5Leave();
drh0d180202008-02-14 23:26:56 +0000513 if( out==stdout ){
514 fflush(stdout);
515 }else{
516 fclose(out);
517 }
danielk1977f3d3c272008-11-19 16:52:44 +0000518#else
519 UNUSED_PARAMETER(zFilename);
drh0d180202008-02-14 23:26:56 +0000520#endif
521}
522
danielk1977c66c0e12008-06-25 14:26:07 +0000523/*
524** This routine is the only routine in this file with external
danielk19775099be52008-06-27 13:27:03 +0000525** linkage. It returns a pointer to a static sqlite3_mem_methods
526** struct populated with the memsys5 methods.
danielk1977c66c0e12008-06-25 14:26:07 +0000527*/
danielk19775099be52008-06-27 13:27:03 +0000528const sqlite3_mem_methods *sqlite3MemGetMemsys5(void){
danielk1977c66c0e12008-06-25 14:26:07 +0000529 static const sqlite3_mem_methods memsys5Methods = {
530 memsys5Malloc,
531 memsys5Free,
532 memsys5Realloc,
533 memsys5Size,
534 memsys5Roundup,
535 memsys5Init,
536 memsys5Shutdown,
537 0
538 };
danielk19775099be52008-06-27 13:27:03 +0000539 return &memsys5Methods;
danielk1977c66c0e12008-06-25 14:26:07 +0000540}
541
542#endif /* SQLITE_ENABLE_MEMSYS5 */