Many hyperlinks are disabled.
Use anonymous login
to enable hyperlinks.
Overview
Comment: | Fix a bug in mem5.c which would cause an infinite loop on an attempt to allocate more than 1073741824 bytes of contiguous memory. Also, some cleanup of mem5.c. More work to do on this. |
---|---|
Downloads: | Tarball | ZIP archive |
Timelines: | family | ancestors | descendants | both | trunk |
Files: | files | file ages | folders |
SHA1: |
783b751a38f9f911c5ebdf738c255b71 |
User & Date: | drh 2009-08-18 01:54:19.000 |
Context
2009-08-18
| ||
12:16 | When shutting down the memsys5 memory allocator, be sure to clear the mutex pointer in case the next startup does not use a mutex because it is configured differently. (check-in: d4e7e2d823 user: drh tags: trunk) | |
01:54 | Fix a bug in mem5.c which would cause an infinite loop on an attempt to allocate more than 1073741824 bytes of contiguous memory. Also, some cleanup of mem5.c. More work to do on this. (check-in: 783b751a38 user: drh tags: trunk) | |
2009-08-17
| ||
16:01 | Always call sqlite3_malloc() in sqlite3OsInit(), even when not compiled with SQLITE_TEST. (check-in: b98a8706a6 user: drh tags: trunk) | |
Changes
Changes to src/mem5.c.
︙ | ︙ | |||
9 10 11 12 13 14 15 | ** May you share freely, never taking more than you give. ** ************************************************************************* ** This file contains the C functions that implement a memory ** allocation subsystem for use by SQLite. ** ** This version of the memory allocation subsystem omits all | | | > > > > > > > > > > > > > > > > > > > > > > > > > > | | | 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 | ** May you share freely, never taking more than you give. ** ************************************************************************* ** This file contains the C functions that implement a memory ** allocation subsystem for use by SQLite. ** ** This version of the memory allocation subsystem omits all ** use of malloc(). The application gives SQLite a block of memory ** before calling sqlite3_initialize() from which allocations ** are made and returned by the xMalloc() and xRealloc() ** implementations. Once sqlite3_initialize() has been called, ** the amount of memory available to SQLite is fixed and cannot ** be changed. ** ** This version of the memory allocation subsystem is included ** in the build only if SQLITE_ENABLE_MEMSYS5 is defined. ** ** This memory allocator uses the following algorithm: ** ** 1. All memory allocations sizes are rounded up to a power of 2. ** ** 2. To adjacent and aligned free blocks are coalesced into a single ** block of the next larger size. ** ** 3. New memory is allocated from the first available free block. ** ** This algorithm is described in: J. M. Robson. "Bounds for Some Functions ** Concerning Dynamic Storage Allocation". Journal of the Association for ** Computing Machinery, Volume 21, Number 8, July 1974, pages 491-499. ** ** Let n be the size of the largest allocation divided by the minimum ** allocation size (after rounding all sizes up to a power of 2.) Let M ** be the maximum amount of memory ever outstanding at one time. Let ** N be the total amount of memory available for allocation. Robson ** proved that this memory allocator will never breakdown due to ** fragmentation as long as the following constraint holds: ** ** N >= M*(1 + log2(n)/2) - n + 1 ** ** The sqlite3_status() logic tracks the maximum values of n and M so ** that an application can, at any time, verify this constraint. */ #include "sqliteInt.h" /* ** This version of the memory allocator is used only when ** SQLITE_ENABLE_MEMSYS5 is defined. */ #ifdef SQLITE_ENABLE_MEMSYS5 /* ** A minimum allocation is an instance of the following structure. ** Larger allocations are an array of these structures where the ** size of the array is a power of 2. ** ** The size of this object must be a power of two. That fact is ** verified in memsys5Init(). */ typedef struct Mem5Link Mem5Link; struct Mem5Link { int next; /* Index of next free chunk */ int prev; /* Index of previous free chunk */ }; /* ** Maximum size of any allocation is ((1<<LOGMAX)*mem5.nAtom). Since ** mem5.nAtom is always at least 8 and 32-bit integers are used, ** it is not actually possible to reach this limit. */ #define LOGMAX 30 /* ** Masks used for mem5.aCtrl[] elements. */ #define CTRL_LOGSIZE 0x1f /* Log2 Size of this block relative to POW2_MIN */ |
︙ | ︙ | |||
65 66 67 68 69 70 71 | */ static SQLITE_WSD struct Mem5Global { /* ** Memory available for allocation */ int nAtom; /* Smallest possible allocation in bytes */ int nBlock; /* Number of nAtom sized blocks in zPool */ | | | 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 | */ static SQLITE_WSD struct Mem5Global { /* ** Memory available for allocation */ int nAtom; /* Smallest possible allocation in bytes */ int nBlock; /* Number of nAtom sized blocks in zPool */ u8 *zPool; /* Memory available to be allocated */ /* ** Mutex to control access to the memory allocation subsystem. */ sqlite3_mutex *mutex; /* |
︙ | ︙ | |||
95 96 97 98 99 100 101 | /* ** Space for tracking which blocks are checked out and the size ** of each block. One byte per block. */ u8 *aCtrl; | | > > > > > > > | 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 | /* ** Space for tracking which blocks are checked out and the size ** of each block. One byte per block. */ u8 *aCtrl; } mem5 = { 0 }; /* ** Access the static variable through a macro for SQLITE_OMIT_WSD */ #define mem5 GLOBAL(struct Mem5Global, mem5) /* ** Assuming mem5.zPool is divided up into an array of Mem5Link ** structures, return a pointer to the idx-th such lik. */ #define MEM5LINK(idx) ((Mem5Link *)(&mem5.zPool[(idx)*mem5.nAtom])) /* ** Unlink the chunk at mem5.aPool[i] from list it is currently ** on. It should be found on mem5.aiFreelist[iLogsize]. */ static void memsys5Unlink(int i, int iLogsize){ |
︙ | ︙ | |||
194 195 196 197 198 199 200 | } memsys5Unlink(iFirst, iLogsize); return iFirst; } /* ** Return a block of memory of at least nBytes in size. | | > > > > > > > > > > > > > > | 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 | } memsys5Unlink(iFirst, iLogsize); return iFirst; } /* ** Return a block of memory of at least nBytes in size. ** Return NULL if unable. Return NULL if nBytes==0. ** ** The caller guarantees that nByte positive. ** ** The caller has obtained a mutex prior to invoking this ** routine so there is never any chance that two or more ** threads can be in this routine at the same time. */ static void *memsys5MallocUnsafe(int nByte){ int i; /* Index of a mem5.aPool[] slot */ int iBin; /* Index into mem5.aiFreelist[] */ int iFullSz; /* Size of allocation rounded up to power of 2 */ int iLogsize; /* Log2 of iFullSz/POW2_MIN */ /* nByte must be a positive */ assert( nByte>0 ); /* Keep track of the maximum allocation request. Even unfulfilled ** requests are counted */ if( (u32)nByte>mem5.maxRequest ){ mem5.maxRequest = nByte; } /* Abort if the size is too great */ if( nByte > 0x40000000 ){ return 0; } /* Round nByte up to the next valid power of two */ for(iFullSz=mem5.nAtom, iLogsize=0; iFullSz<nByte; iFullSz *= 2, iLogsize++){} /* Make sure mem5.aiFreelist[iLogsize] contains at least one free ** block. If not, then split a block of the next larger power of ** two in order to create a new free block of size iLogsize. |
︙ | ︙ | |||
246 247 248 249 250 251 252 | } /* ** Free an outstanding memory allocation. */ static void memsys5FreeUnsafe(void *pOld){ u32 size, iLogsize; | | | 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 | } /* ** Free an outstanding memory allocation. */ static void memsys5FreeUnsafe(void *pOld){ u32 size, iLogsize; int iBlock; /* Set iBlock to the index of the block pointed to by pOld in ** the array of mem5.nAtom byte blocks pointed to by mem5.zPool. */ iBlock = ((u8 *)pOld-mem5.zPool)/mem5.nAtom; /* Check that the pointer pOld points to a valid, non-free block. */ |
︙ | ︙ | |||
312 313 314 315 316 317 318 319 320 | memsys5Leave(); } return (void*)p; } /* ** Free memory. */ static void memsys5Free(void *pPrior){ | > > > < | < < | > > > | < < | > > > > > > | 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 420 421 422 423 424 425 426 | memsys5Leave(); } return (void*)p; } /* ** Free memory. ** ** The outer layer memory allocator prevents this routine from ** being called with pPrior==0. */ static void memsys5Free(void *pPrior){ assert( pPrior!=0 ); memsys5Enter(); memsys5FreeUnsafe(pPrior); memsys5Leave(); } /* ** Change the size of an existing memory allocation. ** ** The outer layer memory allocator prevents this routine from ** being called with pPrior==0. */ static void *memsys5Realloc(void *pPrior, int nBytes){ int nOld; void *p; assert( pPrior!=0 ); if( nBytes<=0 ){ memsys5Free(pPrior); return 0; } nOld = memsys5Size(pPrior); if( nBytes<=nOld ){ return pPrior; } memsys5Enter(); p = memsys5MallocUnsafe(nBytes); if( p ){ memcpy(p, pPrior, nOld); memsys5FreeUnsafe(pPrior); } memsys5Leave(); return p; } /* ** Round up a request size to the next valid allocation size. If ** the allocation is too large to be handled by this allocation system, ** return 0. */ static int memsys5Roundup(int n){ int iFullSz; if( n > 0x40000000 ) return 0; for(iFullSz=mem5.nAtom; iFullSz<n; iFullSz *= 2); return iFullSz; } /* ** Return the logarithm base 2 of iValue. */ static int memsys5Log(int iValue){ int iLog; for(iLog=0; (1<<iLog)<iValue; iLog++); return iLog; } /* |
︙ | ︙ |