drh | 0d18020 | 2008-02-14 23:26:56 +0000 | [diff] [blame] | 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 |
drh | 4c5514d | 2009-08-18 01:54:19 +0000 | [diff] [blame^] | 16 | ** use of malloc(). The application gives SQLite a block of memory |
danielk1977 | c66c0e1 | 2008-06-25 14:26:07 +0000 | [diff] [blame] | 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. |
drh | 0d18020 | 2008-02-14 23:26:56 +0000 | [diff] [blame] | 22 | ** |
danielk1977 | c66c0e1 | 2008-06-25 14:26:07 +0000 | [diff] [blame] | 23 | ** This version of the memory allocation subsystem is included |
| 24 | ** in the build only if SQLITE_ENABLE_MEMSYS5 is defined. |
drh | 0d18020 | 2008-02-14 23:26:56 +0000 | [diff] [blame] | 25 | ** |
drh | 4c5514d | 2009-08-18 01:54:19 +0000 | [diff] [blame^] | 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. 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. |
drh | 0d18020 | 2008-02-14 23:26:56 +0000 | [diff] [blame] | 50 | */ |
| 51 | #include "sqliteInt.h" |
| 52 | |
| 53 | /* |
| 54 | ** This version of the memory allocator is used only when |
drh | d1370b6 | 2008-10-28 18:58:20 +0000 | [diff] [blame] | 55 | ** SQLITE_ENABLE_MEMSYS5 is defined. |
drh | 0d18020 | 2008-02-14 23:26:56 +0000 | [diff] [blame] | 56 | */ |
danielk1977 | c66c0e1 | 2008-06-25 14:26:07 +0000 | [diff] [blame] | 57 | #ifdef SQLITE_ENABLE_MEMSYS5 |
drh | 0d18020 | 2008-02-14 23:26:56 +0000 | [diff] [blame] | 58 | |
| 59 | /* |
drh | 2d7636e | 2008-02-16 16:21:45 +0000 | [diff] [blame] | 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. |
drh | 4c5514d | 2009-08-18 01:54:19 +0000 | [diff] [blame^] | 63 | ** |
| 64 | ** The size of this object must be a power of two. That fact is |
| 65 | ** verified in memsys5Init(). |
drh | 2d7636e | 2008-02-16 16:21:45 +0000 | [diff] [blame] | 66 | */ |
danielk1977 | 5099be5 | 2008-06-27 13:27:03 +0000 | [diff] [blame] | 67 | typedef struct Mem5Link Mem5Link; |
| 68 | struct Mem5Link { |
| 69 | int next; /* Index of next free chunk */ |
| 70 | int prev; /* Index of previous free chunk */ |
drh | 0d18020 | 2008-02-14 23:26:56 +0000 | [diff] [blame] | 71 | }; |
| 72 | |
| 73 | /* |
danielk1977 | 5099be5 | 2008-06-27 13:27:03 +0000 | [diff] [blame] | 74 | ** Maximum size of any allocation is ((1<<LOGMAX)*mem5.nAtom). Since |
drh | 4c5514d | 2009-08-18 01:54:19 +0000 | [diff] [blame^] | 75 | ** mem5.nAtom is always at least 8 and 32-bit integers are used, |
| 76 | ** it is not actually possible to reach this limit. |
drh | 2d7636e | 2008-02-16 16:21:45 +0000 | [diff] [blame] | 77 | */ |
danielk1977 | 5099be5 | 2008-06-27 13:27:03 +0000 | [diff] [blame] | 78 | #define LOGMAX 30 |
drh | 2d7636e | 2008-02-16 16:21:45 +0000 | [diff] [blame] | 79 | |
| 80 | /* |
danielk1977 | c66c0e1 | 2008-06-25 14:26:07 +0000 | [diff] [blame] | 81 | ** Masks used for mem5.aCtrl[] elements. |
drh | 2d7636e | 2008-02-16 16:21:45 +0000 | [diff] [blame] | 82 | */ |
| 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 | /* |
drh | 0d18020 | 2008-02-14 23:26:56 +0000 | [diff] [blame] | 87 | ** All of the static variables used by this module are collected |
danielk1977 | c66c0e1 | 2008-06-25 14:26:07 +0000 | [diff] [blame] | 88 | ** into a single structure named "mem5". This is to keep the |
drh | 0d18020 | 2008-02-14 23:26:56 +0000 | [diff] [blame] | 89 | ** static variables organized and to reduce namespace pollution |
| 90 | ** when this module is combined with other in the amalgamation. |
| 91 | */ |
danielk1977 | 5c8f858 | 2008-09-02 10:22:00 +0000 | [diff] [blame] | 92 | static SQLITE_WSD struct Mem5Global { |
drh | 0d18020 | 2008-02-14 23:26:56 +0000 | [diff] [blame] | 93 | /* |
danielk1977 | 23bf0f4 | 2008-09-02 17:52:51 +0000 | [diff] [blame] | 94 | ** Memory available for allocation |
drh | 0d18020 | 2008-02-14 23:26:56 +0000 | [diff] [blame] | 95 | */ |
danielk1977 | 23bf0f4 | 2008-09-02 17:52:51 +0000 | [diff] [blame] | 96 | int nAtom; /* Smallest possible allocation in bytes */ |
| 97 | int nBlock; /* Number of nAtom sized blocks in zPool */ |
drh | 4c5514d | 2009-08-18 01:54:19 +0000 | [diff] [blame^] | 98 | u8 *zPool; /* Memory available to be allocated */ |
drh | 0d18020 | 2008-02-14 23:26:56 +0000 | [diff] [blame] | 99 | |
| 100 | /* |
| 101 | ** Mutex to control access to the memory allocation subsystem. |
| 102 | */ |
| 103 | sqlite3_mutex *mutex; |
drh | 2d7636e | 2008-02-16 16:21:45 +0000 | [diff] [blame] | 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) */ |
drh | 0d18020 | 2008-02-14 23:26:56 +0000 | [diff] [blame] | 116 | |
| 117 | /* |
drh | 2d7636e | 2008-02-16 16:21:45 +0000 | [diff] [blame] | 118 | ** Lists of free blocks of various sizes. |
drh | 0d18020 | 2008-02-14 23:26:56 +0000 | [diff] [blame] | 119 | */ |
danielk1977 | 5099be5 | 2008-06-27 13:27:03 +0000 | [diff] [blame] | 120 | int aiFreelist[LOGMAX+1]; |
drh | 0d18020 | 2008-02-14 23:26:56 +0000 | [diff] [blame] | 121 | |
| 122 | /* |
drh | 2d7636e | 2008-02-16 16:21:45 +0000 | [diff] [blame] | 123 | ** Space for tracking which blocks are checked out and the size |
| 124 | ** of each block. One byte per block. |
drh | 0d18020 | 2008-02-14 23:26:56 +0000 | [diff] [blame] | 125 | */ |
danielk1977 | c66c0e1 | 2008-06-25 14:26:07 +0000 | [diff] [blame] | 126 | u8 *aCtrl; |
drh | 0d18020 | 2008-02-14 23:26:56 +0000 | [diff] [blame] | 127 | |
drh | 4c5514d | 2009-08-18 01:54:19 +0000 | [diff] [blame^] | 128 | } mem5 = { 0 }; |
danielk1977 | 5c8f858 | 2008-09-02 10:22:00 +0000 | [diff] [blame] | 129 | |
drh | 4c5514d | 2009-08-18 01:54:19 +0000 | [diff] [blame^] | 130 | /* |
| 131 | ** Access the static variable through a macro for SQLITE_OMIT_WSD |
| 132 | */ |
danielk1977 | 5c8f858 | 2008-09-02 10:22:00 +0000 | [diff] [blame] | 133 | #define mem5 GLOBAL(struct Mem5Global, mem5) |
drh | 0d18020 | 2008-02-14 23:26:56 +0000 | [diff] [blame] | 134 | |
drh | 4c5514d | 2009-08-18 01:54:19 +0000 | [diff] [blame^] | 135 | /* |
| 136 | ** Assuming mem5.zPool is divided up into an array of Mem5Link |
| 137 | ** structures, return a pointer to the idx-th such lik. |
| 138 | */ |
danielk1977 | 5099be5 | 2008-06-27 13:27:03 +0000 | [diff] [blame] | 139 | #define MEM5LINK(idx) ((Mem5Link *)(&mem5.zPool[(idx)*mem5.nAtom])) |
| 140 | |
drh | 0d18020 | 2008-02-14 23:26:56 +0000 | [diff] [blame] | 141 | /* |
danielk1977 | c66c0e1 | 2008-06-25 14:26:07 +0000 | [diff] [blame] | 142 | ** Unlink the chunk at mem5.aPool[i] from list it is currently |
| 143 | ** on. It should be found on mem5.aiFreelist[iLogsize]. |
drh | 0d18020 | 2008-02-14 23:26:56 +0000 | [diff] [blame] | 144 | */ |
drh | 2d7636e | 2008-02-16 16:21:45 +0000 | [diff] [blame] | 145 | static void memsys5Unlink(int i, int iLogsize){ |
| 146 | int next, prev; |
danielk1977 | c66c0e1 | 2008-06-25 14:26:07 +0000 | [diff] [blame] | 147 | assert( i>=0 && i<mem5.nBlock ); |
danielk1977 | 5099be5 | 2008-06-27 13:27:03 +0000 | [diff] [blame] | 148 | assert( iLogsize>=0 && iLogsize<=LOGMAX ); |
danielk1977 | c66c0e1 | 2008-06-25 14:26:07 +0000 | [diff] [blame] | 149 | assert( (mem5.aCtrl[i] & CTRL_LOGSIZE)==iLogsize ); |
drh | 2d7636e | 2008-02-16 16:21:45 +0000 | [diff] [blame] | 150 | |
danielk1977 | 5099be5 | 2008-06-27 13:27:03 +0000 | [diff] [blame] | 151 | next = MEM5LINK(i)->next; |
| 152 | prev = MEM5LINK(i)->prev; |
drh | 2d7636e | 2008-02-16 16:21:45 +0000 | [diff] [blame] | 153 | if( prev<0 ){ |
danielk1977 | c66c0e1 | 2008-06-25 14:26:07 +0000 | [diff] [blame] | 154 | mem5.aiFreelist[iLogsize] = next; |
drh | 0d18020 | 2008-02-14 23:26:56 +0000 | [diff] [blame] | 155 | }else{ |
danielk1977 | 5099be5 | 2008-06-27 13:27:03 +0000 | [diff] [blame] | 156 | MEM5LINK(prev)->next = next; |
drh | 0d18020 | 2008-02-14 23:26:56 +0000 | [diff] [blame] | 157 | } |
drh | 2d7636e | 2008-02-16 16:21:45 +0000 | [diff] [blame] | 158 | if( next>=0 ){ |
danielk1977 | 5099be5 | 2008-06-27 13:27:03 +0000 | [diff] [blame] | 159 | MEM5LINK(next)->prev = prev; |
drh | 0d18020 | 2008-02-14 23:26:56 +0000 | [diff] [blame] | 160 | } |
drh | 0d18020 | 2008-02-14 23:26:56 +0000 | [diff] [blame] | 161 | } |
| 162 | |
| 163 | /* |
danielk1977 | c66c0e1 | 2008-06-25 14:26:07 +0000 | [diff] [blame] | 164 | ** Link the chunk at mem5.aPool[i] so that is on the iLogsize |
drh | 2d7636e | 2008-02-16 16:21:45 +0000 | [diff] [blame] | 165 | ** free list. |
drh | 0d18020 | 2008-02-14 23:26:56 +0000 | [diff] [blame] | 166 | */ |
drh | 2d7636e | 2008-02-16 16:21:45 +0000 | [diff] [blame] | 167 | static void memsys5Link(int i, int iLogsize){ |
| 168 | int x; |
danielk1977 | c66c0e1 | 2008-06-25 14:26:07 +0000 | [diff] [blame] | 169 | assert( sqlite3_mutex_held(mem5.mutex) ); |
| 170 | assert( i>=0 && i<mem5.nBlock ); |
danielk1977 | 5099be5 | 2008-06-27 13:27:03 +0000 | [diff] [blame] | 171 | assert( iLogsize>=0 && iLogsize<=LOGMAX ); |
danielk1977 | c66c0e1 | 2008-06-25 14:26:07 +0000 | [diff] [blame] | 172 | assert( (mem5.aCtrl[i] & CTRL_LOGSIZE)==iLogsize ); |
drh | 0d18020 | 2008-02-14 23:26:56 +0000 | [diff] [blame] | 173 | |
danielk1977 | 5099be5 | 2008-06-27 13:27:03 +0000 | [diff] [blame] | 174 | x = MEM5LINK(i)->next = mem5.aiFreelist[iLogsize]; |
| 175 | MEM5LINK(i)->prev = -1; |
drh | 2d7636e | 2008-02-16 16:21:45 +0000 | [diff] [blame] | 176 | if( x>=0 ){ |
danielk1977 | c66c0e1 | 2008-06-25 14:26:07 +0000 | [diff] [blame] | 177 | assert( x<mem5.nBlock ); |
danielk1977 | 5099be5 | 2008-06-27 13:27:03 +0000 | [diff] [blame] | 178 | MEM5LINK(x)->prev = i; |
drh | 0d18020 | 2008-02-14 23:26:56 +0000 | [diff] [blame] | 179 | } |
danielk1977 | c66c0e1 | 2008-06-25 14:26:07 +0000 | [diff] [blame] | 180 | mem5.aiFreelist[iLogsize] = i; |
drh | 0d18020 | 2008-02-14 23:26:56 +0000 | [diff] [blame] | 181 | } |
| 182 | |
| 183 | /* |
danielk1977 | 6b39c2e | 2008-06-25 14:57:53 +0000 | [diff] [blame] | 184 | ** 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 |
danielk1977 | 075c23a | 2008-09-01 18:34:20 +0000 | [diff] [blame] | 186 | ** sqlite3GlobalConfig.bMemStat is true. |
drh | 0d18020 | 2008-02-14 23:26:56 +0000 | [diff] [blame] | 187 | */ |
drh | 2d7636e | 2008-02-16 16:21:45 +0000 | [diff] [blame] | 188 | static void memsys5Enter(void){ |
danielk1977 | 075c23a | 2008-09-01 18:34:20 +0000 | [diff] [blame] | 189 | if( sqlite3GlobalConfig.bMemstat==0 && mem5.mutex==0 ){ |
danielk1977 | 6b39c2e | 2008-06-25 14:57:53 +0000 | [diff] [blame] | 190 | mem5.mutex = sqlite3MutexAlloc(SQLITE_MUTEX_STATIC_MEM); |
| 191 | } |
| 192 | sqlite3_mutex_enter(mem5.mutex); |
drh | 0d18020 | 2008-02-14 23:26:56 +0000 | [diff] [blame] | 193 | } |
danielk1977 | c66c0e1 | 2008-06-25 14:26:07 +0000 | [diff] [blame] | 194 | static void memsys5Leave(void){ |
danielk1977 | 6b39c2e | 2008-06-25 14:57:53 +0000 | [diff] [blame] | 195 | sqlite3_mutex_leave(mem5.mutex); |
drh | 0d18020 | 2008-02-14 23:26:56 +0000 | [diff] [blame] | 196 | } |
| 197 | |
| 198 | /* |
drh | 0d18020 | 2008-02-14 23:26:56 +0000 | [diff] [blame] | 199 | ** 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 | */ |
danielk1977 | c66c0e1 | 2008-06-25 14:26:07 +0000 | [diff] [blame] | 203 | static int memsys5Size(void *p){ |
drh | 0d18020 | 2008-02-14 23:26:56 +0000 | [diff] [blame] | 204 | int iSize = 0; |
| 205 | if( p ){ |
danielk1977 | 5099be5 | 2008-06-27 13:27:03 +0000 | [diff] [blame] | 206 | int i = ((u8 *)p-mem5.zPool)/mem5.nAtom; |
danielk1977 | c66c0e1 | 2008-06-25 14:26:07 +0000 | [diff] [blame] | 207 | assert( i>=0 && i<mem5.nBlock ); |
danielk1977 | 5099be5 | 2008-06-27 13:27:03 +0000 | [diff] [blame] | 208 | iSize = mem5.nAtom * (1 << (mem5.aCtrl[i]&CTRL_LOGSIZE)); |
drh | 0d18020 | 2008-02-14 23:26:56 +0000 | [diff] [blame] | 209 | } |
| 210 | return iSize; |
| 211 | } |
| 212 | |
| 213 | /* |
drh | 2d7636e | 2008-02-16 16:21:45 +0000 | [diff] [blame] | 214 | ** Find the first entry on the freelist iLogsize. Unlink that |
| 215 | ** entry and return its index. |
drh | 0d18020 | 2008-02-14 23:26:56 +0000 | [diff] [blame] | 216 | */ |
drh | 2d7636e | 2008-02-16 16:21:45 +0000 | [diff] [blame] | 217 | static int memsys5UnlinkFirst(int iLogsize){ |
| 218 | int i; |
| 219 | int iFirst; |
drh | 0d18020 | 2008-02-14 23:26:56 +0000 | [diff] [blame] | 220 | |
danielk1977 | 5099be5 | 2008-06-27 13:27:03 +0000 | [diff] [blame] | 221 | assert( iLogsize>=0 && iLogsize<=LOGMAX ); |
danielk1977 | c66c0e1 | 2008-06-25 14:26:07 +0000 | [diff] [blame] | 222 | i = iFirst = mem5.aiFreelist[iLogsize]; |
drh | 2d7636e | 2008-02-16 16:21:45 +0000 | [diff] [blame] | 223 | assert( iFirst>=0 ); |
| 224 | while( i>0 ){ |
| 225 | if( i<iFirst ) iFirst = i; |
danielk1977 | 5099be5 | 2008-06-27 13:27:03 +0000 | [diff] [blame] | 226 | i = MEM5LINK(i)->next; |
drh | 0d18020 | 2008-02-14 23:26:56 +0000 | [diff] [blame] | 227 | } |
drh | 2d7636e | 2008-02-16 16:21:45 +0000 | [diff] [blame] | 228 | memsys5Unlink(iFirst, iLogsize); |
| 229 | return iFirst; |
drh | 0d18020 | 2008-02-14 23:26:56 +0000 | [diff] [blame] | 230 | } |
| 231 | |
| 232 | /* |
| 233 | ** Return a block of memory of at least nBytes in size. |
drh | 4c5514d | 2009-08-18 01:54:19 +0000 | [diff] [blame^] | 234 | ** 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. |
drh | 0d18020 | 2008-02-14 23:26:56 +0000 | [diff] [blame] | 241 | */ |
danielk1977 | c66c0e1 | 2008-06-25 14:26:07 +0000 | [diff] [blame] | 242 | static void *memsys5MallocUnsafe(int nByte){ |
| 243 | int i; /* Index of a mem5.aPool[] slot */ |
| 244 | int iBin; /* Index into mem5.aiFreelist[] */ |
drh | 2d7636e | 2008-02-16 16:21:45 +0000 | [diff] [blame] | 245 | int iFullSz; /* Size of allocation rounded up to power of 2 */ |
| 246 | int iLogsize; /* Log2 of iFullSz/POW2_MIN */ |
drh | 0d18020 | 2008-02-14 23:26:56 +0000 | [diff] [blame] | 247 | |
drh | 4c5514d | 2009-08-18 01:54:19 +0000 | [diff] [blame^] | 248 | /* nByte must be a positive */ |
| 249 | assert( nByte>0 ); |
| 250 | |
drh | eee4c8c | 2008-02-18 22:24:57 +0000 | [diff] [blame] | 251 | /* Keep track of the maximum allocation request. Even unfulfilled |
| 252 | ** requests are counted */ |
danielk1977 | 00e1361 | 2008-11-17 19:18:54 +0000 | [diff] [blame] | 253 | if( (u32)nByte>mem5.maxRequest ){ |
danielk1977 | c66c0e1 | 2008-06-25 14:26:07 +0000 | [diff] [blame] | 254 | mem5.maxRequest = nByte; |
drh | eee4c8c | 2008-02-18 22:24:57 +0000 | [diff] [blame] | 255 | } |
| 256 | |
drh | 4c5514d | 2009-08-18 01:54:19 +0000 | [diff] [blame^] | 257 | /* Abort if the size is too great */ |
| 258 | if( nByte > 0x40000000 ){ |
| 259 | return 0; |
| 260 | } |
| 261 | |
drh | eee4c8c | 2008-02-18 22:24:57 +0000 | [diff] [blame] | 262 | /* Round nByte up to the next valid power of two */ |
danielk1977 | 5099be5 | 2008-06-27 13:27:03 +0000 | [diff] [blame] | 263 | for(iFullSz=mem5.nAtom, iLogsize=0; iFullSz<nByte; iFullSz *= 2, iLogsize++){} |
drh | 0d18020 | 2008-02-14 23:26:56 +0000 | [diff] [blame] | 264 | |
danielk1977 | c66c0e1 | 2008-06-25 14:26:07 +0000 | [diff] [blame] | 265 | /* Make sure mem5.aiFreelist[iLogsize] contains at least one free |
drh | eee4c8c | 2008-02-18 22:24:57 +0000 | [diff] [blame] | 266 | ** 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 | */ |
danielk1977 | 5099be5 | 2008-06-27 13:27:03 +0000 | [diff] [blame] | 269 | for(iBin=iLogsize; mem5.aiFreelist[iBin]<0 && iBin<=LOGMAX; iBin++){} |
| 270 | if( iBin>LOGMAX ) return 0; |
drh | 2d7636e | 2008-02-16 16:21:45 +0000 | [diff] [blame] | 271 | i = memsys5UnlinkFirst(iBin); |
| 272 | while( iBin>iLogsize ){ |
| 273 | int newSize; |
| 274 | |
| 275 | iBin--; |
| 276 | newSize = 1 << iBin; |
danielk1977 | c66c0e1 | 2008-06-25 14:26:07 +0000 | [diff] [blame] | 277 | mem5.aCtrl[i+newSize] = CTRL_FREE | iBin; |
drh | 2d7636e | 2008-02-16 16:21:45 +0000 | [diff] [blame] | 278 | memsys5Link(i+newSize, iBin); |
drh | 0d18020 | 2008-02-14 23:26:56 +0000 | [diff] [blame] | 279 | } |
danielk1977 | c66c0e1 | 2008-06-25 14:26:07 +0000 | [diff] [blame] | 280 | mem5.aCtrl[i] = iLogsize; |
drh | 0d18020 | 2008-02-14 23:26:56 +0000 | [diff] [blame] | 281 | |
drh | eee4c8c | 2008-02-18 22:24:57 +0000 | [diff] [blame] | 282 | /* Update allocator performance statistics. */ |
danielk1977 | c66c0e1 | 2008-06-25 14:26:07 +0000 | [diff] [blame] | 283 | 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; |
drh | 0d18020 | 2008-02-14 23:26:56 +0000 | [diff] [blame] | 290 | |
drh | eee4c8c | 2008-02-18 22:24:57 +0000 | [diff] [blame] | 291 | /* Return a pointer to the allocated memory. */ |
danielk1977 | 5099be5 | 2008-06-27 13:27:03 +0000 | [diff] [blame] | 292 | return (void*)&mem5.zPool[i*mem5.nAtom]; |
drh | 0d18020 | 2008-02-14 23:26:56 +0000 | [diff] [blame] | 293 | } |
| 294 | |
| 295 | /* |
| 296 | ** Free an outstanding memory allocation. |
| 297 | */ |
danielk1977 | c66c0e1 | 2008-06-25 14:26:07 +0000 | [diff] [blame] | 298 | static void memsys5FreeUnsafe(void *pOld){ |
drh | 2d7636e | 2008-02-16 16:21:45 +0000 | [diff] [blame] | 299 | u32 size, iLogsize; |
drh | 4c5514d | 2009-08-18 01:54:19 +0000 | [diff] [blame^] | 300 | int iBlock; |
drh | 0d18020 | 2008-02-14 23:26:56 +0000 | [diff] [blame] | 301 | |
danielk1977 | 5099be5 | 2008-06-27 13:27:03 +0000 | [diff] [blame] | 302 | /* 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; |
drh | 2d7636e | 2008-02-16 16:21:45 +0000 | [diff] [blame] | 313 | size = 1<<iLogsize; |
danielk1977 | 00e1361 | 2008-11-17 19:18:54 +0000 | [diff] [blame] | 314 | assert( iBlock+size-1<(u32)mem5.nBlock ); |
danielk1977 | 5099be5 | 2008-06-27 13:27:03 +0000 | [diff] [blame] | 315 | |
| 316 | mem5.aCtrl[iBlock] |= CTRL_FREE; |
| 317 | mem5.aCtrl[iBlock+size-1] |= CTRL_FREE; |
danielk1977 | c66c0e1 | 2008-06-25 14:26:07 +0000 | [diff] [blame] | 318 | assert( mem5.currentCount>0 ); |
danielk1977 | 00e1361 | 2008-11-17 19:18:54 +0000 | [diff] [blame] | 319 | assert( mem5.currentOut>=(size*mem5.nAtom) ); |
danielk1977 | c66c0e1 | 2008-06-25 14:26:07 +0000 | [diff] [blame] | 320 | mem5.currentCount--; |
danielk1977 | 5099be5 | 2008-06-27 13:27:03 +0000 | [diff] [blame] | 321 | mem5.currentOut -= size*mem5.nAtom; |
danielk1977 | c66c0e1 | 2008-06-25 14:26:07 +0000 | [diff] [blame] | 322 | assert( mem5.currentOut>0 || mem5.currentCount==0 ); |
| 323 | assert( mem5.currentCount>0 || mem5.currentOut==0 ); |
drh | 2d7636e | 2008-02-16 16:21:45 +0000 | [diff] [blame] | 324 | |
danielk1977 | 5099be5 | 2008-06-27 13:27:03 +0000 | [diff] [blame] | 325 | mem5.aCtrl[iBlock] = CTRL_FREE | iLogsize; |
| 326 | while( iLogsize<LOGMAX ){ |
drh | 2d7636e | 2008-02-16 16:21:45 +0000 | [diff] [blame] | 327 | int iBuddy; |
danielk1977 | 5099be5 | 2008-06-27 13:27:03 +0000 | [diff] [blame] | 328 | if( (iBlock>>iLogsize) & 1 ){ |
| 329 | iBuddy = iBlock - size; |
drh | 2d7636e | 2008-02-16 16:21:45 +0000 | [diff] [blame] | 330 | }else{ |
danielk1977 | 5099be5 | 2008-06-27 13:27:03 +0000 | [diff] [blame] | 331 | iBuddy = iBlock + size; |
drh | 0d18020 | 2008-02-14 23:26:56 +0000 | [diff] [blame] | 332 | } |
danielk1977 | 5099be5 | 2008-06-27 13:27:03 +0000 | [diff] [blame] | 333 | assert( iBuddy>=0 ); |
| 334 | if( (iBuddy+(1<<iLogsize))>mem5.nBlock ) break; |
danielk1977 | c66c0e1 | 2008-06-25 14:26:07 +0000 | [diff] [blame] | 335 | if( mem5.aCtrl[iBuddy]!=(CTRL_FREE | iLogsize) ) break; |
drh | 2d7636e | 2008-02-16 16:21:45 +0000 | [diff] [blame] | 336 | memsys5Unlink(iBuddy, iLogsize); |
| 337 | iLogsize++; |
danielk1977 | 5099be5 | 2008-06-27 13:27:03 +0000 | [diff] [blame] | 338 | if( iBuddy<iBlock ){ |
danielk1977 | c66c0e1 | 2008-06-25 14:26:07 +0000 | [diff] [blame] | 339 | mem5.aCtrl[iBuddy] = CTRL_FREE | iLogsize; |
danielk1977 | 5099be5 | 2008-06-27 13:27:03 +0000 | [diff] [blame] | 340 | mem5.aCtrl[iBlock] = 0; |
| 341 | iBlock = iBuddy; |
drh | 2d7636e | 2008-02-16 16:21:45 +0000 | [diff] [blame] | 342 | }else{ |
danielk1977 | 5099be5 | 2008-06-27 13:27:03 +0000 | [diff] [blame] | 343 | mem5.aCtrl[iBlock] = CTRL_FREE | iLogsize; |
danielk1977 | c66c0e1 | 2008-06-25 14:26:07 +0000 | [diff] [blame] | 344 | mem5.aCtrl[iBuddy] = 0; |
drh | 0d18020 | 2008-02-14 23:26:56 +0000 | [diff] [blame] | 345 | } |
drh | 2d7636e | 2008-02-16 16:21:45 +0000 | [diff] [blame] | 346 | size *= 2; |
drh | 0d18020 | 2008-02-14 23:26:56 +0000 | [diff] [blame] | 347 | } |
danielk1977 | 5099be5 | 2008-06-27 13:27:03 +0000 | [diff] [blame] | 348 | memsys5Link(iBlock, iLogsize); |
drh | 0d18020 | 2008-02-14 23:26:56 +0000 | [diff] [blame] | 349 | } |
| 350 | |
| 351 | /* |
| 352 | ** Allocate nBytes of memory |
| 353 | */ |
danielk1977 | c66c0e1 | 2008-06-25 14:26:07 +0000 | [diff] [blame] | 354 | static void *memsys5Malloc(int nBytes){ |
drh | 0d18020 | 2008-02-14 23:26:56 +0000 | [diff] [blame] | 355 | sqlite3_int64 *p = 0; |
| 356 | if( nBytes>0 ){ |
drh | 2d7636e | 2008-02-16 16:21:45 +0000 | [diff] [blame] | 357 | memsys5Enter(); |
danielk1977 | c66c0e1 | 2008-06-25 14:26:07 +0000 | [diff] [blame] | 358 | p = memsys5MallocUnsafe(nBytes); |
| 359 | memsys5Leave(); |
drh | 0d18020 | 2008-02-14 23:26:56 +0000 | [diff] [blame] | 360 | } |
| 361 | return (void*)p; |
| 362 | } |
| 363 | |
| 364 | /* |
| 365 | ** Free memory. |
drh | 4c5514d | 2009-08-18 01:54:19 +0000 | [diff] [blame^] | 366 | ** |
| 367 | ** The outer layer memory allocator prevents this routine from |
| 368 | ** being called with pPrior==0. |
drh | 0d18020 | 2008-02-14 23:26:56 +0000 | [diff] [blame] | 369 | */ |
danielk1977 | c66c0e1 | 2008-06-25 14:26:07 +0000 | [diff] [blame] | 370 | static void memsys5Free(void *pPrior){ |
drh | 4c5514d | 2009-08-18 01:54:19 +0000 | [diff] [blame^] | 371 | assert( pPrior!=0 ); |
danielk1977 | c66c0e1 | 2008-06-25 14:26:07 +0000 | [diff] [blame] | 372 | memsys5Enter(); |
| 373 | memsys5FreeUnsafe(pPrior); |
| 374 | memsys5Leave(); |
drh | 0d18020 | 2008-02-14 23:26:56 +0000 | [diff] [blame] | 375 | } |
| 376 | |
| 377 | /* |
drh | 4c5514d | 2009-08-18 01:54:19 +0000 | [diff] [blame^] | 378 | ** 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. |
drh | 0d18020 | 2008-02-14 23:26:56 +0000 | [diff] [blame] | 382 | */ |
danielk1977 | c66c0e1 | 2008-06-25 14:26:07 +0000 | [diff] [blame] | 383 | static void *memsys5Realloc(void *pPrior, int nBytes){ |
drh | 0d18020 | 2008-02-14 23:26:56 +0000 | [diff] [blame] | 384 | int nOld; |
| 385 | void *p; |
drh | 4c5514d | 2009-08-18 01:54:19 +0000 | [diff] [blame^] | 386 | assert( pPrior!=0 ); |
drh | 0d18020 | 2008-02-14 23:26:56 +0000 | [diff] [blame] | 387 | if( nBytes<=0 ){ |
danielk1977 | c66c0e1 | 2008-06-25 14:26:07 +0000 | [diff] [blame] | 388 | memsys5Free(pPrior); |
drh | 0d18020 | 2008-02-14 23:26:56 +0000 | [diff] [blame] | 389 | return 0; |
| 390 | } |
danielk1977 | c66c0e1 | 2008-06-25 14:26:07 +0000 | [diff] [blame] | 391 | nOld = memsys5Size(pPrior); |
drh | 2d7636e | 2008-02-16 16:21:45 +0000 | [diff] [blame] | 392 | if( nBytes<=nOld ){ |
drh | 0d18020 | 2008-02-14 23:26:56 +0000 | [diff] [blame] | 393 | return pPrior; |
| 394 | } |
danielk1977 | c66c0e1 | 2008-06-25 14:26:07 +0000 | [diff] [blame] | 395 | memsys5Enter(); |
| 396 | p = memsys5MallocUnsafe(nBytes); |
drh | 0d18020 | 2008-02-14 23:26:56 +0000 | [diff] [blame] | 397 | if( p ){ |
drh | 2d7636e | 2008-02-16 16:21:45 +0000 | [diff] [blame] | 398 | memcpy(p, pPrior, nOld); |
danielk1977 | c66c0e1 | 2008-06-25 14:26:07 +0000 | [diff] [blame] | 399 | memsys5FreeUnsafe(pPrior); |
drh | 0d18020 | 2008-02-14 23:26:56 +0000 | [diff] [blame] | 400 | } |
danielk1977 | c66c0e1 | 2008-06-25 14:26:07 +0000 | [diff] [blame] | 401 | memsys5Leave(); |
drh | 0d18020 | 2008-02-14 23:26:56 +0000 | [diff] [blame] | 402 | return p; |
| 403 | } |
| 404 | |
| 405 | /* |
drh | 4c5514d | 2009-08-18 01:54:19 +0000 | [diff] [blame^] | 406 | ** 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. |
danielk1977 | c66c0e1 | 2008-06-25 14:26:07 +0000 | [diff] [blame] | 409 | */ |
| 410 | static int memsys5Roundup(int n){ |
| 411 | int iFullSz; |
drh | 4c5514d | 2009-08-18 01:54:19 +0000 | [diff] [blame^] | 412 | if( n > 0x40000000 ) return 0; |
danielk1977 | 5099be5 | 2008-06-27 13:27:03 +0000 | [diff] [blame] | 413 | for(iFullSz=mem5.nAtom; iFullSz<n; iFullSz *= 2); |
danielk1977 | c66c0e1 | 2008-06-25 14:26:07 +0000 | [diff] [blame] | 414 | return iFullSz; |
| 415 | } |
| 416 | |
drh | 4c5514d | 2009-08-18 01:54:19 +0000 | [diff] [blame^] | 417 | /* |
| 418 | ** Return the logarithm base 2 of iValue. |
| 419 | */ |
danielk1977 | 5099be5 | 2008-06-27 13:27:03 +0000 | [diff] [blame] | 420 | static int memsys5Log(int iValue){ |
| 421 | int iLog; |
| 422 | for(iLog=0; (1<<iLog)<iValue; iLog++); |
| 423 | return iLog; |
| 424 | } |
| 425 | |
danielk1977 | c66c0e1 | 2008-06-25 14:26:07 +0000 | [diff] [blame] | 426 | /* |
| 427 | ** Initialize this module. |
| 428 | */ |
| 429 | static int memsys5Init(void *NotUsed){ |
danielk1977 | 5099be5 | 2008-06-27 13:27:03 +0000 | [diff] [blame] | 430 | int ii; |
danielk1977 | 075c23a | 2008-09-01 18:34:20 +0000 | [diff] [blame] | 431 | int nByte = sqlite3GlobalConfig.nHeap; |
| 432 | u8 *zByte = (u8 *)sqlite3GlobalConfig.pHeap; |
danielk1977 | 5099be5 | 2008-06-27 13:27:03 +0000 | [diff] [blame] | 433 | int nMinLog; /* Log of minimum allocation size in bytes*/ |
| 434 | int iOffset; |
| 435 | |
danielk1977 | a03396a | 2008-11-19 14:35:46 +0000 | [diff] [blame] | 436 | UNUSED_PARAMETER(NotUsed); |
| 437 | |
danielk1977 | 0d84e5b | 2008-06-27 14:05:24 +0000 | [diff] [blame] | 438 | if( !zByte ){ |
| 439 | return SQLITE_ERROR; |
| 440 | } |
| 441 | |
danielk1977 | 075c23a | 2008-09-01 18:34:20 +0000 | [diff] [blame] | 442 | nMinLog = memsys5Log(sqlite3GlobalConfig.mnReq); |
danielk1977 | 5099be5 | 2008-06-27 13:27:03 +0000 | [diff] [blame] | 443 | mem5.nAtom = (1<<nMinLog); |
danielk1977 | 00e1361 | 2008-11-17 19:18:54 +0000 | [diff] [blame] | 444 | while( (int)sizeof(Mem5Link)>mem5.nAtom ){ |
danielk1977 | 5099be5 | 2008-06-27 13:27:03 +0000 | [diff] [blame] | 445 | 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 | |
danielk1977 | c66c0e1 | 2008-06-25 14:26:07 +0000 | [diff] [blame] | 467 | return SQLITE_OK; |
| 468 | } |
| 469 | |
| 470 | /* |
| 471 | ** Deinitialize this module. |
| 472 | */ |
| 473 | static void memsys5Shutdown(void *NotUsed){ |
danielk1977 | a03396a | 2008-11-19 14:35:46 +0000 | [diff] [blame] | 474 | UNUSED_PARAMETER(NotUsed); |
danielk1977 | c66c0e1 | 2008-06-25 14:26:07 +0000 | [diff] [blame] | 475 | return; |
| 476 | } |
| 477 | |
| 478 | /* |
drh | 0d18020 | 2008-02-14 23:26:56 +0000 | [diff] [blame] | 479 | ** Open the file indicated and write a log of all unfreed memory |
| 480 | ** allocations into that log. |
| 481 | */ |
danielk1977 | c66c0e1 | 2008-06-25 14:26:07 +0000 | [diff] [blame] | 482 | void sqlite3Memsys5Dump(const char *zFilename){ |
drh | 0d18020 | 2008-02-14 23:26:56 +0000 | [diff] [blame] | 483 | #ifdef SQLITE_DEBUG |
| 484 | FILE *out; |
drh | 2d7636e | 2008-02-16 16:21:45 +0000 | [diff] [blame] | 485 | int i, j, n; |
danielk1977 | 5099be5 | 2008-06-27 13:27:03 +0000 | [diff] [blame] | 486 | int nMinLog; |
drh | 2d7636e | 2008-02-16 16:21:45 +0000 | [diff] [blame] | 487 | |
drh | 0d18020 | 2008-02-14 23:26:56 +0000 | [diff] [blame] | 488 | 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 | } |
drh | 2d7636e | 2008-02-16 16:21:45 +0000 | [diff] [blame] | 498 | memsys5Enter(); |
danielk1977 | 5099be5 | 2008-06-27 13:27:03 +0000 | [diff] [blame] | 499 | 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); |
drh | 0d18020 | 2008-02-14 23:26:56 +0000 | [diff] [blame] | 503 | } |
danielk1977 | c66c0e1 | 2008-06-25 14:26:07 +0000 | [diff] [blame] | 504 | 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(); |
drh | 0d18020 | 2008-02-14 23:26:56 +0000 | [diff] [blame] | 513 | if( out==stdout ){ |
| 514 | fflush(stdout); |
| 515 | }else{ |
| 516 | fclose(out); |
| 517 | } |
danielk1977 | f3d3c27 | 2008-11-19 16:52:44 +0000 | [diff] [blame] | 518 | #else |
| 519 | UNUSED_PARAMETER(zFilename); |
drh | 0d18020 | 2008-02-14 23:26:56 +0000 | [diff] [blame] | 520 | #endif |
| 521 | } |
| 522 | |
danielk1977 | c66c0e1 | 2008-06-25 14:26:07 +0000 | [diff] [blame] | 523 | /* |
| 524 | ** This routine is the only routine in this file with external |
danielk1977 | 5099be5 | 2008-06-27 13:27:03 +0000 | [diff] [blame] | 525 | ** linkage. It returns a pointer to a static sqlite3_mem_methods |
| 526 | ** struct populated with the memsys5 methods. |
danielk1977 | c66c0e1 | 2008-06-25 14:26:07 +0000 | [diff] [blame] | 527 | */ |
danielk1977 | 5099be5 | 2008-06-27 13:27:03 +0000 | [diff] [blame] | 528 | const sqlite3_mem_methods *sqlite3MemGetMemsys5(void){ |
danielk1977 | c66c0e1 | 2008-06-25 14:26:07 +0000 | [diff] [blame] | 529 | static const sqlite3_mem_methods memsys5Methods = { |
| 530 | memsys5Malloc, |
| 531 | memsys5Free, |
| 532 | memsys5Realloc, |
| 533 | memsys5Size, |
| 534 | memsys5Roundup, |
| 535 | memsys5Init, |
| 536 | memsys5Shutdown, |
| 537 | 0 |
| 538 | }; |
danielk1977 | 5099be5 | 2008-06-27 13:27:03 +0000 | [diff] [blame] | 539 | return &memsys5Methods; |
danielk1977 | c66c0e1 | 2008-06-25 14:26:07 +0000 | [diff] [blame] | 540 | } |
| 541 | |
| 542 | #endif /* SQLITE_ENABLE_MEMSYS5 */ |