OLD | NEW |
1 /* | 1 /* |
2 ** 2007 October 14 | 2 ** 2007 October 14 |
3 ** | 3 ** |
4 ** The author disclaims copyright to this source code. In place of | 4 ** The author disclaims copyright to this source code. In place of |
5 ** a legal notice, here is a blessing: | 5 ** a legal notice, here is a blessing: |
6 ** | 6 ** |
7 ** May you do good and not evil. | 7 ** May you do good and not evil. |
8 ** May you find forgiveness for yourself and forgive others. | 8 ** May you find forgiveness for yourself and forgive others. |
9 ** May you share freely, never taking more than you give. | 9 ** May you share freely, never taking more than you give. |
10 ** | 10 ** |
(...skipping 84 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
95 */ | 95 */ |
96 int szAtom; /* Smallest possible allocation in bytes */ | 96 int szAtom; /* Smallest possible allocation in bytes */ |
97 int nBlock; /* Number of szAtom sized blocks in zPool */ | 97 int nBlock; /* Number of szAtom sized blocks in zPool */ |
98 u8 *zPool; /* Memory available to be allocated */ | 98 u8 *zPool; /* Memory available to be allocated */ |
99 | 99 |
100 /* | 100 /* |
101 ** Mutex to control access to the memory allocation subsystem. | 101 ** Mutex to control access to the memory allocation subsystem. |
102 */ | 102 */ |
103 sqlite3_mutex *mutex; | 103 sqlite3_mutex *mutex; |
104 | 104 |
| 105 #if defined(SQLITE_DEBUG) || defined(SQLITE_TEST) |
105 /* | 106 /* |
106 ** Performance statistics | 107 ** Performance statistics |
107 */ | 108 */ |
108 u64 nAlloc; /* Total number of calls to malloc */ | 109 u64 nAlloc; /* Total number of calls to malloc */ |
109 u64 totalAlloc; /* Total of all malloc calls - includes internal frag */ | 110 u64 totalAlloc; /* Total of all malloc calls - includes internal frag */ |
110 u64 totalExcess; /* Total internal fragmentation */ | 111 u64 totalExcess; /* Total internal fragmentation */ |
111 u32 currentOut; /* Current checkout, including internal fragmentation */ | 112 u32 currentOut; /* Current checkout, including internal fragmentation */ |
112 u32 currentCount; /* Current number of distinct checkouts */ | 113 u32 currentCount; /* Current number of distinct checkouts */ |
113 u32 maxOut; /* Maximum instantaneous currentOut */ | 114 u32 maxOut; /* Maximum instantaneous currentOut */ |
114 u32 maxCount; /* Maximum instantaneous currentCount */ | 115 u32 maxCount; /* Maximum instantaneous currentCount */ |
115 u32 maxRequest; /* Largest allocation (exclusive of internal frag) */ | 116 u32 maxRequest; /* Largest allocation (exclusive of internal frag) */ |
| 117 #endif |
116 | 118 |
117 /* | 119 /* |
118 ** Lists of free blocks. aiFreelist[0] is a list of free blocks of | 120 ** 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. | 121 ** size mem5.szAtom. aiFreelist[1] holds blocks of size szAtom*2. |
120 ** aiFreelist[2] holds free blocks of size szAtom*4. And so forth. | 122 ** aiFreelist[2] holds free blocks of size szAtom*4. And so forth. |
121 */ | 123 */ |
122 int aiFreelist[LOGMAX+1]; | 124 int aiFreelist[LOGMAX+1]; |
123 | 125 |
124 /* | 126 /* |
125 ** Space for tracking which blocks are checked out and the size | 127 ** Space for tracking which blocks are checked out and the size |
(...skipping 91 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
217 */ | 219 */ |
218 static void *memsys5MallocUnsafe(int nByte){ | 220 static void *memsys5MallocUnsafe(int nByte){ |
219 int i; /* Index of a mem5.aPool[] slot */ | 221 int i; /* Index of a mem5.aPool[] slot */ |
220 int iBin; /* Index into mem5.aiFreelist[] */ | 222 int iBin; /* Index into mem5.aiFreelist[] */ |
221 int iFullSz; /* Size of allocation rounded up to power of 2 */ | 223 int iFullSz; /* Size of allocation rounded up to power of 2 */ |
222 int iLogsize; /* Log2 of iFullSz/POW2_MIN */ | 224 int iLogsize; /* Log2 of iFullSz/POW2_MIN */ |
223 | 225 |
224 /* nByte must be a positive */ | 226 /* nByte must be a positive */ |
225 assert( nByte>0 ); | 227 assert( nByte>0 ); |
226 | 228 |
| 229 /* No more than 1GiB per allocation */ |
| 230 if( nByte > 0x40000000 ) return 0; |
| 231 |
| 232 #if defined(SQLITE_DEBUG) || defined(SQLITE_TEST) |
227 /* Keep track of the maximum allocation request. Even unfulfilled | 233 /* Keep track of the maximum allocation request. Even unfulfilled |
228 ** requests are counted */ | 234 ** requests are counted */ |
229 if( (u32)nByte>mem5.maxRequest ){ | 235 if( (u32)nByte>mem5.maxRequest ){ |
230 /* Abort if the requested allocation size is larger than the largest | |
231 ** power of two that we can represent using 32-bit signed integers. */ | |
232 if( nByte > 0x40000000 ) return 0; | |
233 mem5.maxRequest = nByte; | 236 mem5.maxRequest = nByte; |
234 } | 237 } |
| 238 #endif |
| 239 |
235 | 240 |
236 /* Round nByte up to the next valid power of two */ | 241 /* Round nByte up to the next valid power of two */ |
237 for(iFullSz=mem5.szAtom,iLogsize=0; iFullSz<nByte; iFullSz*=2,iLogsize++){} | 242 for(iFullSz=mem5.szAtom,iLogsize=0; iFullSz<nByte; iFullSz*=2,iLogsize++){} |
238 | 243 |
239 /* Make sure mem5.aiFreelist[iLogsize] contains at least one free | 244 /* Make sure mem5.aiFreelist[iLogsize] contains at least one free |
240 ** block. If not, then split a block of the next larger power of | 245 ** block. If not, then split a block of the next larger power of |
241 ** two in order to create a new free block of size iLogsize. | 246 ** two in order to create a new free block of size iLogsize. |
242 */ | 247 */ |
243 for(iBin=iLogsize; iBin<=LOGMAX && mem5.aiFreelist[iBin]<0; iBin++){} | 248 for(iBin=iLogsize; iBin<=LOGMAX && mem5.aiFreelist[iBin]<0; iBin++){} |
244 if( iBin>LOGMAX ){ | 249 if( iBin>LOGMAX ){ |
245 testcase( sqlite3GlobalConfig.xLog!=0 ); | 250 testcase( sqlite3GlobalConfig.xLog!=0 ); |
246 sqlite3_log(SQLITE_NOMEM, "failed to allocate %u bytes", nByte); | 251 sqlite3_log(SQLITE_NOMEM, "failed to allocate %u bytes", nByte); |
247 return 0; | 252 return 0; |
248 } | 253 } |
249 i = mem5.aiFreelist[iBin]; | 254 i = mem5.aiFreelist[iBin]; |
250 memsys5Unlink(i, iBin); | 255 memsys5Unlink(i, iBin); |
251 while( iBin>iLogsize ){ | 256 while( iBin>iLogsize ){ |
252 int newSize; | 257 int newSize; |
253 | 258 |
254 iBin--; | 259 iBin--; |
255 newSize = 1 << iBin; | 260 newSize = 1 << iBin; |
256 mem5.aCtrl[i+newSize] = CTRL_FREE | iBin; | 261 mem5.aCtrl[i+newSize] = CTRL_FREE | iBin; |
257 memsys5Link(i+newSize, iBin); | 262 memsys5Link(i+newSize, iBin); |
258 } | 263 } |
259 mem5.aCtrl[i] = iLogsize; | 264 mem5.aCtrl[i] = iLogsize; |
260 | 265 |
| 266 #if defined(SQLITE_DEBUG) || defined(SQLITE_TEST) |
261 /* Update allocator performance statistics. */ | 267 /* Update allocator performance statistics. */ |
262 mem5.nAlloc++; | 268 mem5.nAlloc++; |
263 mem5.totalAlloc += iFullSz; | 269 mem5.totalAlloc += iFullSz; |
264 mem5.totalExcess += iFullSz - nByte; | 270 mem5.totalExcess += iFullSz - nByte; |
265 mem5.currentCount++; | 271 mem5.currentCount++; |
266 mem5.currentOut += iFullSz; | 272 mem5.currentOut += iFullSz; |
267 if( mem5.maxCount<mem5.currentCount ) mem5.maxCount = mem5.currentCount; | 273 if( mem5.maxCount<mem5.currentCount ) mem5.maxCount = mem5.currentCount; |
268 if( mem5.maxOut<mem5.currentOut ) mem5.maxOut = mem5.currentOut; | 274 if( mem5.maxOut<mem5.currentOut ) mem5.maxOut = mem5.currentOut; |
| 275 #endif |
269 | 276 |
270 #ifdef SQLITE_DEBUG | 277 #ifdef SQLITE_DEBUG |
271 /* Make sure the allocated memory does not assume that it is set to zero | 278 /* Make sure the allocated memory does not assume that it is set to zero |
272 ** or retains a value from a previous allocation */ | 279 ** or retains a value from a previous allocation */ |
273 memset(&mem5.zPool[i*mem5.szAtom], 0xAA, iFullSz); | 280 memset(&mem5.zPool[i*mem5.szAtom], 0xAA, iFullSz); |
274 #endif | 281 #endif |
275 | 282 |
276 /* Return a pointer to the allocated memory. */ | 283 /* Return a pointer to the allocated memory. */ |
277 return (void*)&mem5.zPool[i*mem5.szAtom]; | 284 return (void*)&mem5.zPool[i*mem5.szAtom]; |
278 } | 285 } |
(...skipping 14 matching lines...) Expand all Loading... |
293 assert( iBlock>=0 && iBlock<mem5.nBlock ); | 300 assert( iBlock>=0 && iBlock<mem5.nBlock ); |
294 assert( ((u8 *)pOld-mem5.zPool)%mem5.szAtom==0 ); | 301 assert( ((u8 *)pOld-mem5.zPool)%mem5.szAtom==0 ); |
295 assert( (mem5.aCtrl[iBlock] & CTRL_FREE)==0 ); | 302 assert( (mem5.aCtrl[iBlock] & CTRL_FREE)==0 ); |
296 | 303 |
297 iLogsize = mem5.aCtrl[iBlock] & CTRL_LOGSIZE; | 304 iLogsize = mem5.aCtrl[iBlock] & CTRL_LOGSIZE; |
298 size = 1<<iLogsize; | 305 size = 1<<iLogsize; |
299 assert( iBlock+size-1<(u32)mem5.nBlock ); | 306 assert( iBlock+size-1<(u32)mem5.nBlock ); |
300 | 307 |
301 mem5.aCtrl[iBlock] |= CTRL_FREE; | 308 mem5.aCtrl[iBlock] |= CTRL_FREE; |
302 mem5.aCtrl[iBlock+size-1] |= CTRL_FREE; | 309 mem5.aCtrl[iBlock+size-1] |= CTRL_FREE; |
| 310 |
| 311 #if defined(SQLITE_DEBUG) || defined(SQLITE_TEST) |
303 assert( mem5.currentCount>0 ); | 312 assert( mem5.currentCount>0 ); |
304 assert( mem5.currentOut>=(size*mem5.szAtom) ); | 313 assert( mem5.currentOut>=(size*mem5.szAtom) ); |
305 mem5.currentCount--; | 314 mem5.currentCount--; |
306 mem5.currentOut -= size*mem5.szAtom; | 315 mem5.currentOut -= size*mem5.szAtom; |
307 assert( mem5.currentOut>0 || mem5.currentCount==0 ); | 316 assert( mem5.currentOut>0 || mem5.currentCount==0 ); |
308 assert( mem5.currentCount>0 || mem5.currentOut==0 ); | 317 assert( mem5.currentCount>0 || mem5.currentOut==0 ); |
| 318 #endif |
309 | 319 |
310 mem5.aCtrl[iBlock] = CTRL_FREE | iLogsize; | 320 mem5.aCtrl[iBlock] = CTRL_FREE | iLogsize; |
311 while( ALWAYS(iLogsize<LOGMAX) ){ | 321 while( ALWAYS(iLogsize<LOGMAX) ){ |
312 int iBuddy; | 322 int iBuddy; |
313 if( (iBlock>>iLogsize) & 1 ){ | 323 if( (iBlock>>iLogsize) & 1 ){ |
314 iBuddy = iBlock - size; | 324 iBuddy = iBlock - size; |
| 325 assert( iBuddy>=0 ); |
315 }else{ | 326 }else{ |
316 iBuddy = iBlock + size; | 327 iBuddy = iBlock + size; |
| 328 if( iBuddy>=mem5.nBlock ) break; |
317 } | 329 } |
318 assert( iBuddy>=0 ); | |
319 if( (iBuddy+(1<<iLogsize))>mem5.nBlock ) break; | |
320 if( mem5.aCtrl[iBuddy]!=(CTRL_FREE | iLogsize) ) break; | 330 if( mem5.aCtrl[iBuddy]!=(CTRL_FREE | iLogsize) ) break; |
321 memsys5Unlink(iBuddy, iLogsize); | 331 memsys5Unlink(iBuddy, iLogsize); |
322 iLogsize++; | 332 iLogsize++; |
323 if( iBuddy<iBlock ){ | 333 if( iBuddy<iBlock ){ |
324 mem5.aCtrl[iBuddy] = CTRL_FREE | iLogsize; | 334 mem5.aCtrl[iBuddy] = CTRL_FREE | iLogsize; |
325 mem5.aCtrl[iBlock] = 0; | 335 mem5.aCtrl[iBlock] = 0; |
326 iBlock = iBuddy; | 336 iBlock = iBuddy; |
327 }else{ | 337 }else{ |
328 mem5.aCtrl[iBlock] = CTRL_FREE | iLogsize; | 338 mem5.aCtrl[iBlock] = CTRL_FREE | iLogsize; |
329 mem5.aCtrl[iBuddy] = 0; | 339 mem5.aCtrl[iBuddy] = 0; |
(...skipping 227 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
557 memsys5Size, | 567 memsys5Size, |
558 memsys5Roundup, | 568 memsys5Roundup, |
559 memsys5Init, | 569 memsys5Init, |
560 memsys5Shutdown, | 570 memsys5Shutdown, |
561 0 | 571 0 |
562 }; | 572 }; |
563 return &memsys5Methods; | 573 return &memsys5Methods; |
564 } | 574 } |
565 | 575 |
566 #endif /* SQLITE_ENABLE_MEMSYS5 */ | 576 #endif /* SQLITE_ENABLE_MEMSYS5 */ |
OLD | NEW |