|
sl@0
|
1 |
/*
|
|
sl@0
|
2 |
** 2008 July 24
|
|
sl@0
|
3 |
**
|
|
sl@0
|
4 |
** The author disclaims copyright to this source code. In place of
|
|
sl@0
|
5 |
** a legal notice, here is a blessing:
|
|
sl@0
|
6 |
**
|
|
sl@0
|
7 |
** May you do good and not evil.
|
|
sl@0
|
8 |
** May you find forgiveness for yourself and forgive others.
|
|
sl@0
|
9 |
** May you share freely, never taking more than you give.
|
|
sl@0
|
10 |
**
|
|
sl@0
|
11 |
*************************************************************************
|
|
sl@0
|
12 |
**
|
|
sl@0
|
13 |
** This file contains an alternative memory allocation system for SQLite.
|
|
sl@0
|
14 |
** This system is implemented as a wrapper around the system provided
|
|
sl@0
|
15 |
** by the operating system - vanilla malloc(), realloc() and free().
|
|
sl@0
|
16 |
**
|
|
sl@0
|
17 |
** This system differentiates between requests for "small" allocations
|
|
sl@0
|
18 |
** (by default those of 128 bytes or less) and "large" allocations (all
|
|
sl@0
|
19 |
** others). The 256 byte threshhold is configurable at runtime.
|
|
sl@0
|
20 |
**
|
|
sl@0
|
21 |
** All requests for large allocations are passed through to the
|
|
sl@0
|
22 |
** default system.
|
|
sl@0
|
23 |
**
|
|
sl@0
|
24 |
** Requests for small allocations are met by allocating space within
|
|
sl@0
|
25 |
** one or more larger "chunks" of memory obtained from the default
|
|
sl@0
|
26 |
** memory allocation system. Chunks of memory are usually 64KB or
|
|
sl@0
|
27 |
** larger. The algorithm used to manage space within each chunk is
|
|
sl@0
|
28 |
** the same as that used by mem5.c.
|
|
sl@0
|
29 |
**
|
|
sl@0
|
30 |
** This strategy is designed to prevent the default memory allocation
|
|
sl@0
|
31 |
** system (usually the system malloc) from suffering from heap
|
|
sl@0
|
32 |
** fragmentation. On some systems, heap fragmentation can cause a
|
|
sl@0
|
33 |
** significant real-time slowdown.
|
|
sl@0
|
34 |
**
|
|
sl@0
|
35 |
** $Id: mem6.c,v 1.10 2008/09/02 17:52:52 danielk1977 Exp $
|
|
sl@0
|
36 |
*/
|
|
sl@0
|
37 |
|
|
sl@0
|
38 |
#ifdef SQLITE_ENABLE_MEMSYS6
|
|
sl@0
|
39 |
|
|
sl@0
|
40 |
#include "sqliteInt.h"
|
|
sl@0
|
41 |
|
|
sl@0
|
42 |
/*
|
|
sl@0
|
43 |
** Maximum size of any "small" allocation is ((1<<LOGMAX)*Mem6Chunk.nAtom).
|
|
sl@0
|
44 |
** Mem6Chunk.nAtom is always at least 8, so this is not a practical
|
|
sl@0
|
45 |
** limitation
|
|
sl@0
|
46 |
*/
|
|
sl@0
|
47 |
#define LOGMAX 30
|
|
sl@0
|
48 |
|
|
sl@0
|
49 |
/*
|
|
sl@0
|
50 |
** Default value for the "small" allocation size threshold.
|
|
sl@0
|
51 |
*/
|
|
sl@0
|
52 |
#define SMALL_MALLOC_DEFAULT_THRESHOLD 256
|
|
sl@0
|
53 |
|
|
sl@0
|
54 |
/*
|
|
sl@0
|
55 |
** Minimum size for a memory chunk.
|
|
sl@0
|
56 |
*/
|
|
sl@0
|
57 |
#define MIN_CHUNKSIZE (1<<16)
|
|
sl@0
|
58 |
|
|
sl@0
|
59 |
#define LOG2_MINALLOC 4
|
|
sl@0
|
60 |
|
|
sl@0
|
61 |
|
|
sl@0
|
62 |
typedef struct Mem6Chunk Mem6Chunk;
|
|
sl@0
|
63 |
typedef struct Mem6Link Mem6Link;
|
|
sl@0
|
64 |
|
|
sl@0
|
65 |
/*
|
|
sl@0
|
66 |
** A minimum allocation is an instance of the following structure.
|
|
sl@0
|
67 |
** Larger allocations are an array of these structures where the
|
|
sl@0
|
68 |
** size of the array is a power of 2.
|
|
sl@0
|
69 |
*/
|
|
sl@0
|
70 |
struct Mem6Link {
|
|
sl@0
|
71 |
int next; /* Index of next free chunk */
|
|
sl@0
|
72 |
int prev; /* Index of previous free chunk */
|
|
sl@0
|
73 |
};
|
|
sl@0
|
74 |
|
|
sl@0
|
75 |
/*
|
|
sl@0
|
76 |
** Masks used for mem5.aCtrl[] elements.
|
|
sl@0
|
77 |
*/
|
|
sl@0
|
78 |
#define CTRL_LOGSIZE 0x1f /* Log2 Size of this block relative to POW2_MIN */
|
|
sl@0
|
79 |
#define CTRL_FREE 0x20 /* True if not checked out */
|
|
sl@0
|
80 |
|
|
sl@0
|
81 |
struct Mem6Chunk {
|
|
sl@0
|
82 |
Mem6Chunk *pNext;
|
|
sl@0
|
83 |
|
|
sl@0
|
84 |
/*
|
|
sl@0
|
85 |
** Lists of free blocks of various sizes.
|
|
sl@0
|
86 |
*/
|
|
sl@0
|
87 |
int aiFreelist[LOGMAX+1];
|
|
sl@0
|
88 |
|
|
sl@0
|
89 |
int nCheckedOut; /* Number of currently outstanding allocations */
|
|
sl@0
|
90 |
|
|
sl@0
|
91 |
/*
|
|
sl@0
|
92 |
** Space for tracking which blocks are checked out and the size
|
|
sl@0
|
93 |
** of each block. One byte per block.
|
|
sl@0
|
94 |
*/
|
|
sl@0
|
95 |
u8 *aCtrl;
|
|
sl@0
|
96 |
|
|
sl@0
|
97 |
/*
|
|
sl@0
|
98 |
** Memory available for allocation
|
|
sl@0
|
99 |
*/
|
|
sl@0
|
100 |
int nAtom; /* Smallest possible allocation in bytes */
|
|
sl@0
|
101 |
int nBlock; /* Number of nAtom sized blocks in zPool */
|
|
sl@0
|
102 |
u8 *zPool; /* Pointer to memory chunk from which allocations are made */
|
|
sl@0
|
103 |
};
|
|
sl@0
|
104 |
|
|
sl@0
|
105 |
#define MEM6LINK(idx) ((Mem6Link *)(&pChunk->zPool[(idx)*pChunk->nAtom]))
|
|
sl@0
|
106 |
|
|
sl@0
|
107 |
static SQLITE_WSD struct Mem6Global {
|
|
sl@0
|
108 |
int nMinAlloc; /* Minimum allowed allocation size */
|
|
sl@0
|
109 |
int nThreshold; /* Allocs larger than this go to malloc() */
|
|
sl@0
|
110 |
int nLogThreshold; /* log2 of (nThreshold/nMinAlloc) */
|
|
sl@0
|
111 |
sqlite3_mutex *mutex;
|
|
sl@0
|
112 |
Mem6Chunk *pChunk; /* Singly linked list of all memory chunks */
|
|
sl@0
|
113 |
} mem6 = { 48642791 };
|
|
sl@0
|
114 |
|
|
sl@0
|
115 |
#define mem6 GLOBAL(struct Mem6Global, mem6)
|
|
sl@0
|
116 |
|
|
sl@0
|
117 |
/*
|
|
sl@0
|
118 |
** Unlink the chunk at pChunk->aPool[i] from list it is currently
|
|
sl@0
|
119 |
** on. It should be found on pChunk->aiFreelist[iLogsize].
|
|
sl@0
|
120 |
*/
|
|
sl@0
|
121 |
static void memsys6Unlink(Mem6Chunk *pChunk, int i, int iLogsize){
|
|
sl@0
|
122 |
int next, prev;
|
|
sl@0
|
123 |
assert( i>=0 && i<pChunk->nBlock );
|
|
sl@0
|
124 |
assert( iLogsize>=0 && iLogsize<=mem6.nLogThreshold );
|
|
sl@0
|
125 |
assert( (pChunk->aCtrl[i] & CTRL_LOGSIZE)==iLogsize );
|
|
sl@0
|
126 |
|
|
sl@0
|
127 |
next = MEM6LINK(i)->next;
|
|
sl@0
|
128 |
prev = MEM6LINK(i)->prev;
|
|
sl@0
|
129 |
if( prev<0 ){
|
|
sl@0
|
130 |
pChunk->aiFreelist[iLogsize] = next;
|
|
sl@0
|
131 |
}else{
|
|
sl@0
|
132 |
MEM6LINK(prev)->next = next;
|
|
sl@0
|
133 |
}
|
|
sl@0
|
134 |
if( next>=0 ){
|
|
sl@0
|
135 |
MEM6LINK(next)->prev = prev;
|
|
sl@0
|
136 |
}
|
|
sl@0
|
137 |
}
|
|
sl@0
|
138 |
|
|
sl@0
|
139 |
/*
|
|
sl@0
|
140 |
** Link the chunk at mem5.aPool[i] so that is on the iLogsize
|
|
sl@0
|
141 |
** free list.
|
|
sl@0
|
142 |
*/
|
|
sl@0
|
143 |
static void memsys6Link(Mem6Chunk *pChunk, int i, int iLogsize){
|
|
sl@0
|
144 |
int x;
|
|
sl@0
|
145 |
assert( i>=0 && i<pChunk->nBlock );
|
|
sl@0
|
146 |
assert( iLogsize>=0 && iLogsize<=mem6.nLogThreshold );
|
|
sl@0
|
147 |
assert( (pChunk->aCtrl[i] & CTRL_LOGSIZE)==iLogsize );
|
|
sl@0
|
148 |
|
|
sl@0
|
149 |
x = MEM6LINK(i)->next = pChunk->aiFreelist[iLogsize];
|
|
sl@0
|
150 |
MEM6LINK(i)->prev = -1;
|
|
sl@0
|
151 |
if( x>=0 ){
|
|
sl@0
|
152 |
assert( x<pChunk->nBlock );
|
|
sl@0
|
153 |
MEM6LINK(x)->prev = i;
|
|
sl@0
|
154 |
}
|
|
sl@0
|
155 |
pChunk->aiFreelist[iLogsize] = i;
|
|
sl@0
|
156 |
}
|
|
sl@0
|
157 |
|
|
sl@0
|
158 |
|
|
sl@0
|
159 |
/*
|
|
sl@0
|
160 |
** Find the first entry on the freelist iLogsize. Unlink that
|
|
sl@0
|
161 |
** entry and return its index.
|
|
sl@0
|
162 |
*/
|
|
sl@0
|
163 |
static int memsys6UnlinkFirst(Mem6Chunk *pChunk, int iLogsize){
|
|
sl@0
|
164 |
int i;
|
|
sl@0
|
165 |
int iFirst;
|
|
sl@0
|
166 |
|
|
sl@0
|
167 |
assert( iLogsize>=0 && iLogsize<=mem6.nLogThreshold );
|
|
sl@0
|
168 |
i = iFirst = pChunk->aiFreelist[iLogsize];
|
|
sl@0
|
169 |
assert( iFirst>=0 );
|
|
sl@0
|
170 |
memsys6Unlink(pChunk, iFirst, iLogsize);
|
|
sl@0
|
171 |
return iFirst;
|
|
sl@0
|
172 |
}
|
|
sl@0
|
173 |
|
|
sl@0
|
174 |
static int roundupLog2(int n){
|
|
sl@0
|
175 |
static const char LogTable256[256] = {
|
|
sl@0
|
176 |
0, /* 1 */
|
|
sl@0
|
177 |
1, /* 2 */
|
|
sl@0
|
178 |
2, 2, /* 3..4 */
|
|
sl@0
|
179 |
3, 3, 3, 3, /* 5..8 */
|
|
sl@0
|
180 |
4, 4, 4, 4, 4, 4, 4, 4, /* 9..16 */
|
|
sl@0
|
181 |
5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, /* 17..32 */
|
|
sl@0
|
182 |
6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
|
|
sl@0
|
183 |
6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, /* 33..64 */
|
|
sl@0
|
184 |
7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
|
|
sl@0
|
185 |
7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
|
|
sl@0
|
186 |
7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
|
|
sl@0
|
187 |
7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, /* 65..128 */
|
|
sl@0
|
188 |
8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
|
|
sl@0
|
189 |
8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
|
|
sl@0
|
190 |
8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
|
|
sl@0
|
191 |
8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
|
|
sl@0
|
192 |
8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
|
|
sl@0
|
193 |
8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
|
|
sl@0
|
194 |
8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
|
|
sl@0
|
195 |
8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, /* 129..256 */
|
|
sl@0
|
196 |
};
|
|
sl@0
|
197 |
|
|
sl@0
|
198 |
assert(n<=(1<<16) && n>0);
|
|
sl@0
|
199 |
if( n<=256 ) return LogTable256[n-1];
|
|
sl@0
|
200 |
return LogTable256[(n>>8) - ((n&0xFF)?0:1)] + 8;
|
|
sl@0
|
201 |
}
|
|
sl@0
|
202 |
|
|
sl@0
|
203 |
/*
|
|
sl@0
|
204 |
** Allocate and return a block of (pChunk->nAtom << iLogsize) bytes from chunk
|
|
sl@0
|
205 |
** pChunk. If the allocation request cannot be satisfied, return 0.
|
|
sl@0
|
206 |
*/
|
|
sl@0
|
207 |
static void *chunkMalloc(Mem6Chunk *pChunk, int iLogsize){
|
|
sl@0
|
208 |
int i; /* Index of a mem5.aPool[] slot */
|
|
sl@0
|
209 |
int iBin; /* Index into mem5.aiFreelist[] */
|
|
sl@0
|
210 |
|
|
sl@0
|
211 |
/* Make sure mem5.aiFreelist[iLogsize] contains at least one free
|
|
sl@0
|
212 |
** block. If not, then split a block of the next larger power of
|
|
sl@0
|
213 |
** two in order to create a new free block of size iLogsize.
|
|
sl@0
|
214 |
*/
|
|
sl@0
|
215 |
for(iBin=iLogsize; pChunk->aiFreelist[iBin]<0 && iBin<=mem6.nLogThreshold; iBin++){}
|
|
sl@0
|
216 |
if( iBin>mem6.nLogThreshold ) return 0;
|
|
sl@0
|
217 |
i = memsys6UnlinkFirst(pChunk, iBin);
|
|
sl@0
|
218 |
while( iBin>iLogsize ){
|
|
sl@0
|
219 |
int newSize;
|
|
sl@0
|
220 |
iBin--;
|
|
sl@0
|
221 |
newSize = 1 << iBin;
|
|
sl@0
|
222 |
pChunk->aCtrl[i+newSize] = CTRL_FREE | iBin;
|
|
sl@0
|
223 |
memsys6Link(pChunk, i+newSize, iBin);
|
|
sl@0
|
224 |
}
|
|
sl@0
|
225 |
pChunk->aCtrl[i] = iLogsize;
|
|
sl@0
|
226 |
|
|
sl@0
|
227 |
/* Return a pointer to the allocated memory. */
|
|
sl@0
|
228 |
pChunk->nCheckedOut++;
|
|
sl@0
|
229 |
return (void*)&pChunk->zPool[i*pChunk->nAtom];
|
|
sl@0
|
230 |
}
|
|
sl@0
|
231 |
|
|
sl@0
|
232 |
/*
|
|
sl@0
|
233 |
** Free the allocation pointed to by p, which is guaranteed to be non-zero
|
|
sl@0
|
234 |
** and a part of chunk object pChunk.
|
|
sl@0
|
235 |
*/
|
|
sl@0
|
236 |
static void chunkFree(Mem6Chunk *pChunk, void *pOld){
|
|
sl@0
|
237 |
u32 size, iLogsize;
|
|
sl@0
|
238 |
int iBlock;
|
|
sl@0
|
239 |
|
|
sl@0
|
240 |
/* Set iBlock to the index of the block pointed to by pOld in
|
|
sl@0
|
241 |
** the array of pChunk->nAtom byte blocks pointed to by pChunk->zPool.
|
|
sl@0
|
242 |
*/
|
|
sl@0
|
243 |
iBlock = ((u8 *)pOld-pChunk->zPool)/pChunk->nAtom;
|
|
sl@0
|
244 |
|
|
sl@0
|
245 |
/* Check that the pointer pOld points to a valid, non-free block. */
|
|
sl@0
|
246 |
assert( iBlock>=0 && iBlock<pChunk->nBlock );
|
|
sl@0
|
247 |
assert( ((u8 *)pOld-pChunk->zPool)%pChunk->nAtom==0 );
|
|
sl@0
|
248 |
assert( (pChunk->aCtrl[iBlock] & CTRL_FREE)==0 );
|
|
sl@0
|
249 |
|
|
sl@0
|
250 |
iLogsize = pChunk->aCtrl[iBlock] & CTRL_LOGSIZE;
|
|
sl@0
|
251 |
size = 1<<iLogsize;
|
|
sl@0
|
252 |
assert( iBlock+size-1<pChunk->nBlock );
|
|
sl@0
|
253 |
|
|
sl@0
|
254 |
pChunk->aCtrl[iBlock] |= CTRL_FREE;
|
|
sl@0
|
255 |
pChunk->aCtrl[iBlock+size-1] |= CTRL_FREE;
|
|
sl@0
|
256 |
|
|
sl@0
|
257 |
pChunk->aCtrl[iBlock] = CTRL_FREE | iLogsize;
|
|
sl@0
|
258 |
while( iLogsize<mem6.nLogThreshold ){
|
|
sl@0
|
259 |
int iBuddy;
|
|
sl@0
|
260 |
if( (iBlock>>iLogsize) & 1 ){
|
|
sl@0
|
261 |
iBuddy = iBlock - size;
|
|
sl@0
|
262 |
}else{
|
|
sl@0
|
263 |
iBuddy = iBlock + size;
|
|
sl@0
|
264 |
}
|
|
sl@0
|
265 |
assert( iBuddy>=0 );
|
|
sl@0
|
266 |
if( (iBuddy+(1<<iLogsize))>pChunk->nBlock ) break;
|
|
sl@0
|
267 |
if( pChunk->aCtrl[iBuddy]!=(CTRL_FREE | iLogsize) ) break;
|
|
sl@0
|
268 |
memsys6Unlink(pChunk, iBuddy, iLogsize);
|
|
sl@0
|
269 |
iLogsize++;
|
|
sl@0
|
270 |
if( iBuddy<iBlock ){
|
|
sl@0
|
271 |
pChunk->aCtrl[iBuddy] = CTRL_FREE | iLogsize;
|
|
sl@0
|
272 |
pChunk->aCtrl[iBlock] = 0;
|
|
sl@0
|
273 |
iBlock = iBuddy;
|
|
sl@0
|
274 |
}else{
|
|
sl@0
|
275 |
pChunk->aCtrl[iBlock] = CTRL_FREE | iLogsize;
|
|
sl@0
|
276 |
pChunk->aCtrl[iBuddy] = 0;
|
|
sl@0
|
277 |
}
|
|
sl@0
|
278 |
size *= 2;
|
|
sl@0
|
279 |
}
|
|
sl@0
|
280 |
pChunk->nCheckedOut--;
|
|
sl@0
|
281 |
memsys6Link(pChunk, iBlock, iLogsize);
|
|
sl@0
|
282 |
}
|
|
sl@0
|
283 |
|
|
sl@0
|
284 |
/*
|
|
sl@0
|
285 |
** Return the actual size of the block pointed to by p, which is guaranteed
|
|
sl@0
|
286 |
** to have been allocated from chunk pChunk.
|
|
sl@0
|
287 |
*/
|
|
sl@0
|
288 |
static int chunkSize(Mem6Chunk *pChunk, void *p){
|
|
sl@0
|
289 |
int iSize = 0;
|
|
sl@0
|
290 |
if( p ){
|
|
sl@0
|
291 |
int i = ((u8 *)p-pChunk->zPool)/pChunk->nAtom;
|
|
sl@0
|
292 |
assert( i>=0 && i<pChunk->nBlock );
|
|
sl@0
|
293 |
iSize = pChunk->nAtom * (1 << (pChunk->aCtrl[i]&CTRL_LOGSIZE));
|
|
sl@0
|
294 |
}
|
|
sl@0
|
295 |
return iSize;
|
|
sl@0
|
296 |
}
|
|
sl@0
|
297 |
|
|
sl@0
|
298 |
/*
|
|
sl@0
|
299 |
** Return true if there are currently no outstanding allocations.
|
|
sl@0
|
300 |
*/
|
|
sl@0
|
301 |
static int chunkIsEmpty(Mem6Chunk *pChunk){
|
|
sl@0
|
302 |
return (pChunk->nCheckedOut==0);
|
|
sl@0
|
303 |
}
|
|
sl@0
|
304 |
|
|
sl@0
|
305 |
/*
|
|
sl@0
|
306 |
** Initialize the buffer zChunk, which is nChunk bytes in size, as
|
|
sl@0
|
307 |
** an Mem6Chunk object. Return a copy of the zChunk pointer.
|
|
sl@0
|
308 |
*/
|
|
sl@0
|
309 |
static Mem6Chunk *chunkInit(u8 *zChunk, int nChunk, int nMinAlloc){
|
|
sl@0
|
310 |
int ii;
|
|
sl@0
|
311 |
int iOffset;
|
|
sl@0
|
312 |
Mem6Chunk *pChunk = (Mem6Chunk *)zChunk;
|
|
sl@0
|
313 |
|
|
sl@0
|
314 |
assert( nChunk>sizeof(Mem6Chunk) );
|
|
sl@0
|
315 |
assert( nMinAlloc>sizeof(Mem6Link) );
|
|
sl@0
|
316 |
|
|
sl@0
|
317 |
memset(pChunk, 0, sizeof(Mem6Chunk));
|
|
sl@0
|
318 |
pChunk->nAtom = nMinAlloc;
|
|
sl@0
|
319 |
pChunk->nBlock = ((nChunk-sizeof(Mem6Chunk)) / (pChunk->nAtom+sizeof(u8)));
|
|
sl@0
|
320 |
|
|
sl@0
|
321 |
pChunk->zPool = (u8 *)&pChunk[1];
|
|
sl@0
|
322 |
pChunk->aCtrl = &pChunk->zPool[pChunk->nBlock*pChunk->nAtom];
|
|
sl@0
|
323 |
|
|
sl@0
|
324 |
for(ii=0; ii<=mem6.nLogThreshold; ii++){
|
|
sl@0
|
325 |
pChunk->aiFreelist[ii] = -1;
|
|
sl@0
|
326 |
}
|
|
sl@0
|
327 |
|
|
sl@0
|
328 |
iOffset = 0;
|
|
sl@0
|
329 |
for(ii=mem6.nLogThreshold; ii>=0; ii--){
|
|
sl@0
|
330 |
int nAlloc = (1<<ii);
|
|
sl@0
|
331 |
while( (iOffset+nAlloc)<=pChunk->nBlock ){
|
|
sl@0
|
332 |
pChunk->aCtrl[iOffset] = ii | CTRL_FREE;
|
|
sl@0
|
333 |
memsys6Link(pChunk, iOffset, ii);
|
|
sl@0
|
334 |
iOffset += nAlloc;
|
|
sl@0
|
335 |
}
|
|
sl@0
|
336 |
}
|
|
sl@0
|
337 |
|
|
sl@0
|
338 |
return pChunk;
|
|
sl@0
|
339 |
}
|
|
sl@0
|
340 |
|
|
sl@0
|
341 |
|
|
sl@0
|
342 |
static void mem6Enter(void){
|
|
sl@0
|
343 |
sqlite3_mutex_enter(mem6.mutex);
|
|
sl@0
|
344 |
}
|
|
sl@0
|
345 |
|
|
sl@0
|
346 |
static void mem6Leave(void){
|
|
sl@0
|
347 |
sqlite3_mutex_leave(mem6.mutex);
|
|
sl@0
|
348 |
}
|
|
sl@0
|
349 |
|
|
sl@0
|
350 |
/*
|
|
sl@0
|
351 |
** Based on the number and size of the currently allocated chunks, return
|
|
sl@0
|
352 |
** the size of the next chunk to allocate, in bytes.
|
|
sl@0
|
353 |
*/
|
|
sl@0
|
354 |
static int nextChunkSize(void){
|
|
sl@0
|
355 |
int iTotal = MIN_CHUNKSIZE;
|
|
sl@0
|
356 |
Mem6Chunk *p;
|
|
sl@0
|
357 |
for(p=mem6.pChunk; p; p=p->pNext){
|
|
sl@0
|
358 |
iTotal = iTotal*2;
|
|
sl@0
|
359 |
}
|
|
sl@0
|
360 |
return iTotal;
|
|
sl@0
|
361 |
}
|
|
sl@0
|
362 |
|
|
sl@0
|
363 |
static void freeChunk(Mem6Chunk *pChunk){
|
|
sl@0
|
364 |
Mem6Chunk **pp = &mem6.pChunk;
|
|
sl@0
|
365 |
for( pp=&mem6.pChunk; *pp!=pChunk; pp = &(*pp)->pNext );
|
|
sl@0
|
366 |
*pp = (*pp)->pNext;
|
|
sl@0
|
367 |
free(pChunk);
|
|
sl@0
|
368 |
}
|
|
sl@0
|
369 |
|
|
sl@0
|
370 |
static void *memsys6Malloc(int nByte){
|
|
sl@0
|
371 |
Mem6Chunk *pChunk;
|
|
sl@0
|
372 |
void *p = 0;
|
|
sl@0
|
373 |
int nTotal = nByte+8;
|
|
sl@0
|
374 |
int iOffset = 0;
|
|
sl@0
|
375 |
|
|
sl@0
|
376 |
if( nTotal>mem6.nThreshold ){
|
|
sl@0
|
377 |
p = malloc(nTotal);
|
|
sl@0
|
378 |
}else{
|
|
sl@0
|
379 |
int iLogsize = 0;
|
|
sl@0
|
380 |
if( nTotal>(1<<LOG2_MINALLOC) ){
|
|
sl@0
|
381 |
iLogsize = roundupLog2(nTotal) - LOG2_MINALLOC;
|
|
sl@0
|
382 |
}
|
|
sl@0
|
383 |
mem6Enter();
|
|
sl@0
|
384 |
for(pChunk=mem6.pChunk; pChunk; pChunk=pChunk->pNext){
|
|
sl@0
|
385 |
p = chunkMalloc(pChunk, iLogsize);
|
|
sl@0
|
386 |
if( p ){
|
|
sl@0
|
387 |
break;
|
|
sl@0
|
388 |
}
|
|
sl@0
|
389 |
}
|
|
sl@0
|
390 |
if( !p ){
|
|
sl@0
|
391 |
int iSize = nextChunkSize();
|
|
sl@0
|
392 |
p = malloc(iSize);
|
|
sl@0
|
393 |
if( p ){
|
|
sl@0
|
394 |
pChunk = chunkInit((u8 *)p, iSize, mem6.nMinAlloc);
|
|
sl@0
|
395 |
pChunk->pNext = mem6.pChunk;
|
|
sl@0
|
396 |
mem6.pChunk = pChunk;
|
|
sl@0
|
397 |
p = chunkMalloc(pChunk, iLogsize);
|
|
sl@0
|
398 |
assert(p);
|
|
sl@0
|
399 |
}
|
|
sl@0
|
400 |
}
|
|
sl@0
|
401 |
iOffset = ((u8*)p - (u8*)pChunk);
|
|
sl@0
|
402 |
mem6Leave();
|
|
sl@0
|
403 |
}
|
|
sl@0
|
404 |
|
|
sl@0
|
405 |
if( !p ){
|
|
sl@0
|
406 |
return 0;
|
|
sl@0
|
407 |
}
|
|
sl@0
|
408 |
((u32 *)p)[0] = iOffset;
|
|
sl@0
|
409 |
((u32 *)p)[1] = nByte;
|
|
sl@0
|
410 |
return &((u32 *)p)[2];
|
|
sl@0
|
411 |
}
|
|
sl@0
|
412 |
|
|
sl@0
|
413 |
static int memsys6Size(void *pPrior){
|
|
sl@0
|
414 |
if( pPrior==0 ) return 0;
|
|
sl@0
|
415 |
return ((u32*)pPrior)[-1];
|
|
sl@0
|
416 |
}
|
|
sl@0
|
417 |
|
|
sl@0
|
418 |
static void memsys6Free(void *pPrior){
|
|
sl@0
|
419 |
int iSlot;
|
|
sl@0
|
420 |
void *p = &((u32 *)pPrior)[-2];
|
|
sl@0
|
421 |
iSlot = ((u32 *)p)[0];
|
|
sl@0
|
422 |
if( iSlot ){
|
|
sl@0
|
423 |
Mem6Chunk *pChunk;
|
|
sl@0
|
424 |
mem6Enter();
|
|
sl@0
|
425 |
pChunk = (Mem6Chunk *)(&((u8 *)p)[-1 * iSlot]);
|
|
sl@0
|
426 |
chunkFree(pChunk, p);
|
|
sl@0
|
427 |
if( chunkIsEmpty(pChunk) ){
|
|
sl@0
|
428 |
freeChunk(pChunk);
|
|
sl@0
|
429 |
}
|
|
sl@0
|
430 |
mem6Leave();
|
|
sl@0
|
431 |
}else{
|
|
sl@0
|
432 |
free(p);
|
|
sl@0
|
433 |
}
|
|
sl@0
|
434 |
}
|
|
sl@0
|
435 |
|
|
sl@0
|
436 |
static void *memsys6Realloc(void *p, int nByte){
|
|
sl@0
|
437 |
void *p2;
|
|
sl@0
|
438 |
|
|
sl@0
|
439 |
if( p && nByte<=memsys6Size(p) ){
|
|
sl@0
|
440 |
p2 = p;
|
|
sl@0
|
441 |
}else{
|
|
sl@0
|
442 |
p2 = memsys6Malloc(nByte);
|
|
sl@0
|
443 |
if( p && p2 ){
|
|
sl@0
|
444 |
memcpy(p2, p, memsys6Size(p));
|
|
sl@0
|
445 |
memsys6Free(p);
|
|
sl@0
|
446 |
}
|
|
sl@0
|
447 |
}
|
|
sl@0
|
448 |
|
|
sl@0
|
449 |
return p2;
|
|
sl@0
|
450 |
}
|
|
sl@0
|
451 |
|
|
sl@0
|
452 |
static int memsys6Roundup(int n){
|
|
sl@0
|
453 |
if( n>mem6.nThreshold ){
|
|
sl@0
|
454 |
return n;
|
|
sl@0
|
455 |
}else{
|
|
sl@0
|
456 |
return (1<<roundupLog2(n));
|
|
sl@0
|
457 |
}
|
|
sl@0
|
458 |
}
|
|
sl@0
|
459 |
|
|
sl@0
|
460 |
static int memsys6Init(void *pCtx){
|
|
sl@0
|
461 |
u8 bMemstat = sqlite3GlobalConfig.bMemstat;
|
|
sl@0
|
462 |
mem6.nMinAlloc = (1 << LOG2_MINALLOC);
|
|
sl@0
|
463 |
mem6.pChunk = 0;
|
|
sl@0
|
464 |
mem6.nThreshold = sqlite3GlobalConfig.nSmall;
|
|
sl@0
|
465 |
if( mem6.nThreshold<=0 ){
|
|
sl@0
|
466 |
mem6.nThreshold = SMALL_MALLOC_DEFAULT_THRESHOLD;
|
|
sl@0
|
467 |
}
|
|
sl@0
|
468 |
mem6.nLogThreshold = roundupLog2(mem6.nThreshold) - LOG2_MINALLOC;
|
|
sl@0
|
469 |
if( !bMemstat ){
|
|
sl@0
|
470 |
mem6.mutex = sqlite3MutexAlloc(SQLITE_MUTEX_STATIC_MEM);
|
|
sl@0
|
471 |
}
|
|
sl@0
|
472 |
return SQLITE_OK;
|
|
sl@0
|
473 |
}
|
|
sl@0
|
474 |
|
|
sl@0
|
475 |
static void memsys6Shutdown(void *pCtx){
|
|
sl@0
|
476 |
memset(&mem6, 0, sizeof(mem6));
|
|
sl@0
|
477 |
}
|
|
sl@0
|
478 |
|
|
sl@0
|
479 |
/*
|
|
sl@0
|
480 |
** This routine is the only routine in this file with external
|
|
sl@0
|
481 |
** linkage. It returns a pointer to a static sqlite3_mem_methods
|
|
sl@0
|
482 |
** struct populated with the memsys6 methods.
|
|
sl@0
|
483 |
*/
|
|
sl@0
|
484 |
const sqlite3_mem_methods *sqlite3MemGetMemsys6(void){
|
|
sl@0
|
485 |
static const sqlite3_mem_methods memsys6Methods = {
|
|
sl@0
|
486 |
memsys6Malloc,
|
|
sl@0
|
487 |
memsys6Free,
|
|
sl@0
|
488 |
memsys6Realloc,
|
|
sl@0
|
489 |
memsys6Size,
|
|
sl@0
|
490 |
memsys6Roundup,
|
|
sl@0
|
491 |
memsys6Init,
|
|
sl@0
|
492 |
memsys6Shutdown,
|
|
sl@0
|
493 |
0
|
|
sl@0
|
494 |
};
|
|
sl@0
|
495 |
return &memsys6Methods;
|
|
sl@0
|
496 |
}
|
|
sl@0
|
497 |
|
|
sl@0
|
498 |
#endif
|