Many hyperlinks are disabled.
Use anonymous login
to enable hyperlinks.
Overview
Comment: | Fix obscure issues with the memsys5 memory allocator. Arrange that the xRealloc() interface to memory allocators is only called with a value that has been through xRoundup(). |
---|---|
Downloads: | Tarball | ZIP archive |
Timelines: | family | ancestors | descendants | both | trunk |
Files: | files | file ages | folders |
SHA1: |
577bd6f15556b7f6d86ee5167353fdd5 |
User & Date: | drh 2009-08-18 14:48:54.000 |
Context
2009-08-18
| ||
15:33 | Move the allocation of the memsys5 mutex into the initializer. (check-in: 4e377a09c1 user: drh tags: trunk) | |
14:48 | Fix obscure issues with the memsys5 memory allocator. Arrange that the xRealloc() interface to memory allocators is only called with a value that has been through xRoundup(). (check-in: 577bd6f155 user: drh tags: trunk) | |
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) | |
Changes
Changes to src/malloc.c.
︙ | ︙ | |||
477 478 479 480 481 482 483 | return 0; } if( nBytes>=0x7fffff00 ){ /* The 0x7ffff00 limit term is explained in comments on sqlite3Malloc() */ return 0; } nOld = sqlite3MallocSize(pOld); | < < < | | | | > > | | | | | | | | | | | | | < | | 477 478 479 480 481 482 483 484 485 486 487 488 489 490 491 492 493 494 495 496 497 498 499 500 501 502 503 504 505 506 507 508 509 510 511 512 | return 0; } if( nBytes>=0x7fffff00 ){ /* The 0x7ffff00 limit term is explained in comments on sqlite3Malloc() */ return 0; } nOld = sqlite3MallocSize(pOld); nNew = sqlite3GlobalConfig.m.xRoundup(nBytes); if( nOld==nNew ){ pNew = pOld; }else if( sqlite3GlobalConfig.bMemstat ){ sqlite3_mutex_enter(mem0.mutex); sqlite3StatusSet(SQLITE_STATUS_MALLOC_SIZE, nBytes); if( sqlite3StatusValue(SQLITE_STATUS_MEMORY_USED)+nNew-nOld >= mem0.alarmThreshold ){ sqlite3MallocAlarm(nNew-nOld); } pNew = sqlite3GlobalConfig.m.xRealloc(pOld, nNew); if( pNew==0 && mem0.alarmCallback ){ sqlite3MallocAlarm(nBytes); pNew = sqlite3GlobalConfig.m.xRealloc(pOld, nNew); } if( pNew ){ nNew = sqlite3MallocSize(pNew); sqlite3StatusAdd(SQLITE_STATUS_MEMORY_USED, nNew-nOld); } sqlite3_mutex_leave(mem0.mutex); }else{ pNew = sqlite3GlobalConfig.m.xRealloc(pOld, nNew); } return pNew; } /* ** The public interface to sqlite3Realloc. Make sure that the memory ** subsystem is initialized prior to invoking sqliteRealloc. |
︙ | ︙ |
Changes to src/mem5.c.
︙ | ︙ | |||
23 24 25 26 27 28 29 | ** 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. ** | | | | 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 | ** 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. If two adjacent free blocks are the halves of a larger block, ** then the two blocks are coalesed into the single larger block. ** ** 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. ** |
︙ | ︙ | |||
67 68 69 70 71 72 73 | typedef struct Mem5Link Mem5Link; struct Mem5Link { int next; /* Index of next free chunk */ int prev; /* Index of previous free chunk */ }; /* | | | | | | | > > | | 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 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 146 147 148 | 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.szAtom). Since ** mem5.szAtom 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 */ #define CTRL_FREE 0x20 /* True if not checked out */ /* ** All of the static variables used by this module are collected ** into a single structure named "mem5". This is to keep the ** static variables organized and to reduce namespace pollution ** when this module is combined with other in the amalgamation. */ static SQLITE_WSD struct Mem5Global { /* ** Memory available for allocation */ int szAtom; /* Smallest possible allocation in bytes */ int nBlock; /* Number of szAtom sized blocks in zPool */ u8 *zPool; /* Memory available to be allocated */ /* ** Mutex to control access to the memory allocation subsystem. */ sqlite3_mutex *mutex; /* ** Performance statistics */ u64 nAlloc; /* Total number of calls to malloc */ u64 totalAlloc; /* Total of all malloc calls - includes internal frag */ u64 totalExcess; /* Total internal fragmentation */ u32 currentOut; /* Current checkout, including internal fragmentation */ u32 currentCount; /* Current number of distinct checkouts */ u32 maxOut; /* Maximum instantaneous currentOut */ u32 maxCount; /* Maximum instantaneous currentCount */ u32 maxRequest; /* Largest allocation (exclusive of internal frag) */ /* ** Lists of free blocks. aiFreelist[0] is a list of free blocks of ** size mem5.szAtom. aiFreelist[1] holds blocks of size szAtom*2. ** and so forth. */ int aiFreelist[LOGMAX+1]; /* ** 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.szAtom])) /* ** 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){ int next, prev; |
︙ | ︙ | |||
199 200 201 202 203 204 205 | ** Return the size of an outstanding allocation, in bytes. The ** size returned omits the 8-byte header overhead. This only ** works for chunks that are currently checked out. */ static int memsys5Size(void *p){ int iSize = 0; if( p ){ | | | | 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 | ** Return the size of an outstanding allocation, in bytes. The ** size returned omits the 8-byte header overhead. This only ** works for chunks that are currently checked out. */ static int memsys5Size(void *p){ int iSize = 0; if( p ){ int i = ((u8 *)p-mem5.zPool)/mem5.szAtom; assert( i>=0 && i<mem5.nBlock ); iSize = mem5.szAtom * (1 << (mem5.aCtrl[i]&CTRL_LOGSIZE)); } return iSize; } /* ** Find the first entry on the freelist iLogsize. Unlink that ** entry and return its index. |
︙ | ︙ | |||
250 251 252 253 254 255 256 | /* Keep track of the maximum allocation request. Even unfulfilled ** requests are counted */ if( (u32)nByte>mem5.maxRequest ){ mem5.maxRequest = nByte; } | | > > | | 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 | /* Keep track of the maximum allocation request. Even unfulfilled ** requests are counted */ if( (u32)nByte>mem5.maxRequest ){ mem5.maxRequest = nByte; } /* Abort if the requested allocation size is larger than the largest ** power of two that we can represent using 32-bit signed integers. */ if( nByte > 0x40000000 ){ return 0; } /* Round nByte up to the next valid power of two */ for(iFullSz=mem5.szAtom, 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. */ for(iBin=iLogsize; mem5.aiFreelist[iBin]<0 && iBin<=LOGMAX; iBin++){} if( iBin>LOGMAX ) return 0; |
︙ | ︙ | |||
285 286 287 288 289 290 291 | mem5.totalExcess += iFullSz - nByte; mem5.currentCount++; mem5.currentOut += iFullSz; if( mem5.maxCount<mem5.currentCount ) mem5.maxCount = mem5.currentCount; if( mem5.maxOut<mem5.currentOut ) mem5.maxOut = mem5.currentOut; /* Return a pointer to the allocated memory. */ | | | | | | | | | 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 | mem5.totalExcess += iFullSz - nByte; mem5.currentCount++; mem5.currentOut += iFullSz; if( mem5.maxCount<mem5.currentCount ) mem5.maxCount = mem5.currentCount; if( mem5.maxOut<mem5.currentOut ) mem5.maxOut = mem5.currentOut; /* Return a pointer to the allocated memory. */ return (void*)&mem5.zPool[i*mem5.szAtom]; } /* ** 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.szAtom byte blocks pointed to by mem5.zPool. */ iBlock = ((u8 *)pOld-mem5.zPool)/mem5.szAtom; /* Check that the pointer pOld points to a valid, non-free block. */ assert( iBlock>=0 && iBlock<mem5.nBlock ); assert( ((u8 *)pOld-mem5.zPool)%mem5.szAtom==0 ); assert( (mem5.aCtrl[iBlock] & CTRL_FREE)==0 ); iLogsize = mem5.aCtrl[iBlock] & CTRL_LOGSIZE; size = 1<<iLogsize; assert( iBlock+size-1<(u32)mem5.nBlock ); mem5.aCtrl[iBlock] |= CTRL_FREE; mem5.aCtrl[iBlock+size-1] |= CTRL_FREE; assert( mem5.currentCount>0 ); assert( mem5.currentOut>=(size*mem5.szAtom) ); mem5.currentCount--; mem5.currentOut -= size*mem5.szAtom; assert( mem5.currentOut>0 || mem5.currentCount==0 ); assert( mem5.currentCount>0 || mem5.currentOut==0 ); mem5.aCtrl[iBlock] = CTRL_FREE | iLogsize; while( ALWAYS(iLogsize<LOGMAX) ){ int iBuddy; if( (iBlock>>iLogsize) & 1 ){ iBuddy = iBlock - size; }else{ iBuddy = iBlock + size; } assert( iBuddy>=0 ); |
︙ | ︙ | |||
374 375 376 377 378 379 380 | memsys5Leave(); } /* ** Change the size of an existing memory allocation. ** ** The outer layer memory allocator prevents this routine from | | > > > > > > > > | < > > > > | | > > > > > > > | | | | | | | | > > | > > > | | | | | | 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 427 428 429 430 431 432 433 434 435 436 437 438 439 440 441 442 443 444 445 446 447 448 449 450 451 452 453 454 455 456 457 458 459 460 461 462 463 464 465 466 467 468 469 470 471 472 473 474 475 476 477 478 479 480 481 482 483 484 | memsys5Leave(); } /* ** Change the size of an existing memory allocation. ** ** The outer layer memory allocator prevents this routine from ** being called with pPrior==0. ** ** nBytes is always a value obtained from a prior call to ** memsys5Round(). Hence nBytes is always a non-negative power ** of two. If nBytes==0 that means that an oversize allocation ** (an allocation larger than 0x40000000) was requested and this ** routine should return 0 without freeing pPrior. */ static void *memsys5Realloc(void *pPrior, int nBytes){ int nOld; void *p; assert( pPrior!=0 ); assert( (nBytes&(nBytes-1))==0 ); assert( nBytes>=0 ); if( nBytes==0 ){ 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. ** ** All allocations must be a power of two and must be expressed by a ** 32-bit signed integer. Hence the largest allocation is 0x40000000 ** or 1073741824 bytes. */ static int memsys5Roundup(int n){ int iFullSz; if( n > 0x40000000 ) return 0; for(iFullSz=mem5.szAtom; iFullSz<n; iFullSz *= 2); return iFullSz; } /* ** Return the ceiling of the logarithm base 2 of iValue. ** ** Examples: memsys5Log(1) -> 0 ** memsys5Log(2) -> 1 ** memsys5Log(4) -> 2 ** memsys5Log(5) -> 3 ** memsys5Log(8) -> 3 ** memsys5Log(9) -> 4 */ static int memsys5Log(int iValue){ int iLog; for(iLog=0; (1<<iLog)<iValue; iLog++); return iLog; } /* ** Initialize the memory allocator. */ static int memsys5Init(void *NotUsed){ int ii; /* Loop counter */ int nByte; /* Number of bytes of memory available to this allocator */ u8 *zByte; /* Memory usable by this allocator */ int nMinLog; /* Log base 2 of minimum allocation size in bytes */ int iOffset; /* An offset into mem5.aCtrl[] */ UNUSED_PARAMETER(NotUsed); /* The size of a Mem5Link object must be a power of two. Verify that ** this is case. */ assert( (sizeof(Mem5Link)&(sizeof(Mem5Link)-1))==0 ); nByte = sqlite3GlobalConfig.nHeap; zByte = (u8*)sqlite3GlobalConfig.pHeap; assert( zByte!=0 ); /* sqlite3_config() does not allow otherwise */ nMinLog = memsys5Log(sqlite3GlobalConfig.mnReq); mem5.szAtom = (1<<nMinLog); while( (int)sizeof(Mem5Link)>mem5.szAtom ){ mem5.szAtom = mem5.szAtom << 1; } mem5.nBlock = (nByte / (mem5.szAtom+sizeof(u8))); mem5.zPool = zByte; mem5.aCtrl = (u8 *)&mem5.zPool[mem5.nBlock*mem5.szAtom]; for(ii=0; ii<=LOGMAX; ii++){ mem5.aiFreelist[ii] = -1; } iOffset = 0; for(ii=LOGMAX; ii>=0; ii--){ |
︙ | ︙ | |||
472 473 474 475 476 477 478 479 480 481 482 483 | */ static void memsys5Shutdown(void *NotUsed){ UNUSED_PARAMETER(NotUsed); mem5.mutex = 0; return; } /* ** Open the file indicated and write a log of all unfreed memory ** allocations into that log. */ void sqlite3Memsys5Dump(const char *zFilename){ | > < | | < < < > | 499 500 501 502 503 504 505 506 507 508 509 510 511 512 513 514 515 516 517 518 519 520 521 522 523 524 525 526 527 528 529 530 531 532 533 534 535 536 537 538 539 540 541 542 543 544 545 546 547 548 549 550 551 552 553 554 | */ static void memsys5Shutdown(void *NotUsed){ UNUSED_PARAMETER(NotUsed); mem5.mutex = 0; return; } #ifdef SQLITE_TEST /* ** Open the file indicated and write a log of all unfreed memory ** allocations into that log. */ void sqlite3Memsys5Dump(const char *zFilename){ FILE *out; int i, j, n; int nMinLog; if( zFilename==0 || zFilename[0]==0 ){ out = stdout; }else{ out = fopen(zFilename, "w"); if( out==0 ){ fprintf(stderr, "** Unable to output memory debug output log: %s **\n", zFilename); return; } } memsys5Enter(); nMinLog = memsys5Log(mem5.szAtom); for(i=0; i<=LOGMAX && i+nMinLog<32; i++){ for(n=0, j=mem5.aiFreelist[i]; j>=0; j = MEM5LINK(j)->next, n++){} fprintf(out, "freelist items of size %d: %d\n", mem5.szAtom << i, n); } fprintf(out, "mem5.nAlloc = %llu\n", mem5.nAlloc); fprintf(out, "mem5.totalAlloc = %llu\n", mem5.totalAlloc); fprintf(out, "mem5.totalExcess = %llu\n", mem5.totalExcess); fprintf(out, "mem5.currentOut = %u\n", mem5.currentOut); fprintf(out, "mem5.currentCount = %u\n", mem5.currentCount); fprintf(out, "mem5.maxOut = %u\n", mem5.maxOut); fprintf(out, "mem5.maxCount = %u\n", mem5.maxCount); fprintf(out, "mem5.maxRequest = %u\n", mem5.maxRequest); memsys5Leave(); if( out==stdout ){ fflush(stdout); }else{ fclose(out); } } #endif /* ** This routine is the only routine in this file with external ** linkage. It returns a pointer to a static sqlite3_mem_methods ** struct populated with the memsys5 methods. */ const sqlite3_mem_methods *sqlite3MemGetMemsys5(void){ |
︙ | ︙ |