Many hyperlinks are disabled.
Use anonymous login
to enable hyperlinks.
Overview
| Comment: | Add the experimental mem5.c memory allocator. Allocate the content part of cache pages separately from the header. (See check-ins (4495) and (4409)). (CVS 4789) |
|---|---|
| Downloads: | Tarball | ZIP archive | SQL archive |
| Timelines: | family | ancestors | descendants | both | trunk |
| Files: | files | file ages | folders |
| SHA1: |
669ece8c82bfa69add852589dd121175 |
| User & Date: | drh 2008-02-14 23:26:56 |
Context
|
2008-02-14
| ||
| 23:44 | Fix a bug in EXPLAIN growing out of the new Mem implementation. (CVS 4790) (check-in: 4df62a55 user: drh tags: trunk) | |
| 23:26 | Add the experimental mem5.c memory allocator. Allocate the content part of cache pages separately from the header. (See check-ins (4495) and (4409)). (CVS 4789) (check-in: 669ece8c user: drh tags: trunk) | |
| 23:24 | Fix a typo in a comment used to generate documentation. (CVS 4788) (check-in: 65e66dd8 user: drh tags: trunk) | |
Changes
Changes to main.mk.
47 47 TCCX = $(TCC) $(OPTS) -I. -I$(TOP)/src 48 48 49 49 # Object files for the SQLite library. 50 50 # 51 51 LIBOBJ+= alter.o analyze.o attach.o auth.o btmutex.o btree.o build.o \ 52 52 callback.o complete.o date.o delete.o \ 53 53 expr.o fault.o func.o hash.o insert.o journal.o loadext.o \ 54 - main.o malloc.o mem1.o mem2.o mem3.o mem4.o mutex.o mutex_os2.o \ 55 - mutex_unix.o mutex_w32.o \ 54 + main.o malloc.o mem1.o mem2.o mem3.o mem4.o mem5.o \ 55 + mutex.o mutex_os2.o mutex_unix.o mutex_w32.o \ 56 56 opcodes.o os.o os_os2.o os_unix.o os_win.o \ 57 57 pager.o parse.o pragma.o prepare.o printf.o random.o \ 58 58 select.o table.o $(TCLOBJ) tokenize.o trigger.o \ 59 59 update.o util.o vacuum.o \ 60 60 vdbe.o vdbeapi.o vdbeaux.o vdbeblob.o vdbefifo.o vdbemem.o \ 61 61 where.o utf.o legacy.o vtab.o 62 62 ................................................................................ 105 105 $(TOP)/src/loadext.c \ 106 106 $(TOP)/src/main.c \ 107 107 $(TOP)/src/malloc.c \ 108 108 $(TOP)/src/mem1.c \ 109 109 $(TOP)/src/mem2.c \ 110 110 $(TOP)/src/mem3.c \ 111 111 $(TOP)/src/mem4.c \ 112 + $(TOP)/src/mem5.c \ 112 113 $(TOP)/src/mutex.c \ 113 114 $(TOP)/src/mutex.h \ 114 115 $(TOP)/src/mutex_os2.c \ 115 116 $(TOP)/src/mutex_unix.c \ 116 117 $(TOP)/src/mutex_w32.c \ 117 118 $(TOP)/src/os.c \ 118 119 $(TOP)/src/os.h \
Changes to src/mem1.c.
8 8 ** May you find forgiveness for yourself and forgive others. 9 9 ** May you share freely, never taking more than you give. 10 10 ** 11 11 ************************************************************************* 12 12 ** This file contains the C functions that implement a memory 13 13 ** allocation subsystem for use by SQLite. 14 14 ** 15 -** $Id: mem1.c,v 1.15 2008/02/13 18:25:27 danielk1977 Exp $ 15 +** $Id: mem1.c,v 1.16 2008/02/14 23:26:56 drh Exp $ 16 16 */ 17 +#include "sqliteInt.h" 17 18 18 19 /* 19 20 ** This version of the memory allocator is the default. It is 20 21 ** used when no other memory allocator is specified using compile-time 21 22 ** macros. 22 23 */ 23 -#if !defined(SQLITE_MEMDEBUG) && !defined(SQLITE_MEMORY_SIZE) \ 24 - && !defined(SQLITE_MMAP_HEAP_SIZE) 25 - 26 -/* 27 -** We will eventually construct multiple memory allocation subsystems 28 -** suitable for use in various contexts: 29 -** 30 -** * Normal multi-threaded builds 31 -** * Normal single-threaded builds 32 -** * Debugging builds 33 -** 34 -** This initial version is suitable for use in normal multi-threaded 35 -** builds. We envision that alternative versions will be stored in 36 -** separate source files. #ifdefs will be used to select the code from 37 -** one of the various memN.c source files for use in any given build. 38 -*/ 39 -#include "sqliteInt.h" 24 +#ifdef SQLITE_SYSTEM_MALLOC 40 25 41 26 /* 42 27 ** All of the static variables used by this module are collected 43 28 ** into a single structure named "mem". This is to keep the 44 29 ** static variables organized and to reduce namespace pollution 45 30 ** when this module is combined with other in the amalgamation. 46 31 */ ................................................................................ 235 220 mem.mxUsed = mem.nowUsed; 236 221 } 237 222 } 238 223 sqlite3_mutex_leave(mem.mutex); 239 224 return (void*)p; 240 225 } 241 226 242 -#endif /* !SQLITE_MEMDEBUG && !SQLITE_OMIT_MEMORY_ALLOCATION */ 227 +#endif /* SQLITE_SYSTEM_MALLOC */
Changes to src/mem2.c.
8 8 ** May you find forgiveness for yourself and forgive others. 9 9 ** May you share freely, never taking more than you give. 10 10 ** 11 11 ************************************************************************* 12 12 ** This file contains the C functions that implement a memory 13 13 ** allocation subsystem for use by SQLite. 14 14 ** 15 -** $Id: mem2.c,v 1.20 2008/02/13 18:25:27 danielk1977 Exp $ 15 +** $Id: mem2.c,v 1.21 2008/02/14 23:26:56 drh Exp $ 16 16 */ 17 +#include "sqliteInt.h" 17 18 18 19 /* 19 20 ** This version of the memory allocator is used only if the 20 -** SQLITE_MEMDEBUG macro is defined and SQLITE_OMIT_MEMORY_ALLOCATION 21 -** is not defined. 21 +** SQLITE_MEMDEBUG macro is defined 22 22 */ 23 -#if defined(SQLITE_MEMDEBUG) 24 - 25 -/* 26 -** We will eventually construct multiple memory allocation subsystems 27 -** suitable for use in various contexts: 28 -** 29 -** * Normal multi-threaded builds 30 -** * Normal single-threaded builds 31 -** * Debugging builds 32 -** 33 -** This version is suitable for use in debugging builds. 34 -** 35 -** Features: 36 -** 37 -** * Every allocate has guards at both ends. 38 -** * New allocations are initialized with randomness 39 -** * Allocations are overwritten with randomness when freed 40 -** * Optional logs of malloc activity generated 41 -** * Summary of outstanding allocations with backtraces to the 42 -** point of allocation. 43 -** * The ability to simulate memory allocation failure 44 -*/ 45 -#include "sqliteInt.h" 46 -#include <stdio.h> 23 +#ifdef SQLITE_MEMDEBUG 47 24 48 25 /* 49 26 ** The backtrace functionality is only available with GLIBC 50 27 */ 51 28 #ifdef __GLIBC__ 52 29 extern int backtrace(void**,int); 53 30 extern void backtrace_symbols_fd(void*const*,int,int); 54 31 #else 55 32 # define backtrace(A,B) 0 56 33 # define backtrace_symbols_fd(A,B,C) 57 34 #endif 35 +#include <stdio.h> 58 36 59 37 /* 60 38 ** Each memory allocation looks like this: 61 39 ** 62 40 ** ------------------------------------------------------------------------ 63 41 ** | Title | backtrace pointers | MemBlockHdr | allocation | EndGuard | 64 42 ** ------------------------------------------------------------------------ ................................................................................ 473 451 for(i=0; i<NCSIZE; i++){ 474 452 nTotal += mem.sizeCnt[i]; 475 453 } 476 454 return nTotal; 477 455 } 478 456 479 457 480 -#endif /* SQLITE_MEMDEBUG && !SQLITE_OMIT_MEMORY_ALLOCATION */ 458 +#endif /* SQLITE_MEMDEBUG */
Changes to src/mem3.c.
16 16 ** use of malloc(). All dynamically allocatable memory is 17 17 ** contained in a static array, mem.aPool[]. The size of this 18 18 ** fixed memory pool is SQLITE_MEMORY_SIZE bytes. 19 19 ** 20 20 ** This version of the memory allocation subsystem is used if 21 21 ** and only if SQLITE_MEMORY_SIZE is defined. 22 22 ** 23 -** $Id: mem3.c,v 1.10 2008/02/14 15:31:52 danielk1977 Exp $ 23 +** $Id: mem3.c,v 1.11 2008/02/14 23:26:56 drh Exp $ 24 24 */ 25 +#include "sqliteInt.h" 25 26 26 27 /* 27 28 ** This version of the memory allocator is used only when 28 29 ** SQLITE_MEMORY_SIZE is defined. 29 30 */ 30 -#if defined(SQLITE_MEMORY_SIZE) 31 -#include "sqliteInt.h" 32 - 33 -#ifdef SQLITE_MEMDEBUG 34 -# error cannot define both SQLITE_MEMDEBUG and SQLITE_MEMORY_SIZE 35 -#endif 31 +#ifdef SQLITE_MEMORY_SIZE 36 32 37 33 /* 38 34 ** Maximum size (in Mem3Blocks) of a "small" chunk. 39 35 */ 40 36 #define MX_SMALL 10 41 37 42 38
Changes to src/mem4.c.
8 8 ** May you find forgiveness for yourself and forgive others. 9 9 ** May you share freely, never taking more than you give. 10 10 ** 11 11 ************************************************************************* 12 12 ** This file contains the C functions that implement a memory 13 13 ** allocation subsystem for use by SQLite. 14 14 ** 15 -** $Id: mem4.c,v 1.1 2007/11/29 18:36:49 drh Exp $ 15 +** $Id: mem4.c,v 1.2 2008/02/14 23:26:56 drh Exp $ 16 16 */ 17 +#include "sqliteInt.h" 17 18 18 19 /* 19 20 ** This version of the memory allocator attempts to obtain memory 20 21 ** from mmap() if the size of the allocation is close to the size 21 22 ** of a virtual memory page. If the size of the allocation is different 22 23 ** from the virtual memory page size, then ordinary malloc() is used. 23 24 ** Ordinary malloc is also used if space allocated to mmap() is ................................................................................ 24 25 ** exhausted. 25 26 ** 26 27 ** Enable this memory allocation by compiling with -DSQLITE_MMAP_HEAP_SIZE=nnn 27 28 ** where nnn is the maximum number of bytes of mmap-ed memory you want 28 29 ** to support. This module may choose to use less memory than requested. 29 30 ** 30 31 */ 31 -#if defined(SQLITE_MMAP_HEAP_SIZE) 32 - 33 -#if defined(SQLITE_MEMDEBUG) || defined(SQLITE_MEMORY_SIZE) 34 -# error cannot use SQLITE_MMAP_HEAP_SIZE with either SQLITE_MEMDEBUG \ 35 - or SQLITE_MEMORY_SIZE 36 -#endif 32 +#ifdef SQLITE_MMAP_HEAP_SIZE 37 33 38 34 /* 39 35 ** This is a test version of the memory allocator that attempts to 40 36 ** use mmap() and madvise() for allocations and frees of approximately 41 37 ** the virtual memory page size. 42 38 */ 43 39 #include <sys/types.h> 44 40 #include <sys/mman.h> 45 41 #include <errno.h> 46 -#include "sqliteInt.h" 47 42 #include <unistd.h> 48 43 49 44 50 45 /* 51 46 ** All of the static variables used by this module are collected 52 47 ** into a single structure named "mem". This is to keep the 53 48 ** static variables organized and to reduce namespace pollution ................................................................................ 391 386 memsys4Free(pPrior); 392 387 } 393 388 assert( mem.mutex!=0 ); 394 389 sqlite3_mutex_leave(mem.mutex); 395 390 return (void*)p; 396 391 } 397 392 398 -#endif /* !SQLITE_MEMDEBUG && !SQLITE_OMIT_MEMORY_ALLOCATION */ 393 +#endif /* SQLITE_MMAP_HEAP_SIZE */
Added src/mem5.c.
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 16 +** use of malloc(). All dynamically allocatable memory is 17 +** contained in a static array, mem.aPool[]. The size of this 18 +** fixed memory pool is SQLITE_POW2_MEMORY_SIZE bytes. 19 +** 20 +** This version of the memory allocation subsystem is used if 21 +** and only if SQLITE_POW2_MEMORY_SIZE is defined. 22 +** 23 +** $Id: mem5.c,v 1.1 2008/02/14 23:26:56 drh Exp $ 24 +*/ 25 +#include "sqliteInt.h" 26 + 27 +/* 28 +** This version of the memory allocator is used only when 29 +** SQLITE_POW2_MEMORY_SIZE is defined. 30 +*/ 31 +#ifdef SQLITE_POW2_MEMORY_SIZE 32 + 33 +/* 34 +** Maximum size (in Mem3Blocks) of a "small" chunk. 35 +*/ 36 +#define MX_SMALL 10 37 + 38 + 39 +/* 40 +** Number of freelist hash slots 41 +*/ 42 +#define N_HASH 61 43 + 44 +/* 45 +** A memory allocation (also called a "chunk") consists of two or 46 +** more blocks where each block is 8 bytes. The first 8 bytes are 47 +** a header that is not returned to the user. 48 +** 49 +** A chunk is two or more blocks that is either checked out or 50 +** free. The first block has format u.hdr. u.hdr.size4x is 4 times the 51 +** size of the allocation in blocks if the allocation is free. 52 +** The u.hdr.size4x&1 bit is true if the chunk is checked out and 53 +** false if the chunk is on the freelist. The u.hdr.size4x&2 bit 54 +** is true if the previous chunk is checked out and false if the 55 +** previous chunk is free. The u.hdr.prevSize field is the size of 56 +** the previous chunk in blocks if the previous chunk is on the 57 +** freelist. If the previous chunk is checked out, then 58 +** u.hdr.prevSize can be part of the data for that chunk and should 59 +** not be read or written. 60 +** 61 +** We often identify a chunk by its index in mem.aPool[]. When 62 +** this is done, the chunk index refers to the second block of 63 +** the chunk. In this way, the first chunk has an index of 1. 64 +** A chunk index of 0 means "no such chunk" and is the equivalent 65 +** of a NULL pointer. 66 +** 67 +** The second block of free chunks is of the form u.list. The 68 +** two fields form a double-linked list of chunks of related sizes. 69 +** Pointers to the head of the list are stored in mem.aiSmall[] 70 +** for smaller chunks and mem.aiHash[] for larger chunks. 71 +** 72 +** The second block of a chunk is user data if the chunk is checked 73 +** out. If a chunk is checked out, the user data may extend into 74 +** the u.hdr.prevSize value of the following chunk. 75 +*/ 76 +typedef struct Mem3Block Mem3Block; 77 +struct Mem3Block { 78 + union { 79 + struct { 80 + u32 prevSize; /* Size of previous chunk in Mem3Block elements */ 81 + u32 size4x; /* 4x the size of current chunk in Mem3Block elements */ 82 + } hdr; 83 + struct { 84 + u32 next; /* Index in mem.aPool[] of next free chunk */ 85 + u32 prev; /* Index in mem.aPool[] of previous free chunk */ 86 + } list; 87 + } u; 88 +}; 89 + 90 +/* 91 +** All of the static variables used by this module are collected 92 +** into a single structure named "mem". This is to keep the 93 +** static variables organized and to reduce namespace pollution 94 +** when this module is combined with other in the amalgamation. 95 +*/ 96 +static struct { 97 + /* 98 + ** True if we are evaluating an out-of-memory callback. 99 + */ 100 + int alarmBusy; 101 + 102 + /* 103 + ** Mutex to control access to the memory allocation subsystem. 104 + */ 105 + sqlite3_mutex *mutex; 106 + 107 + /* 108 + ** The minimum amount of free space that we have seen. 109 + */ 110 + u32 mnMaster; 111 + 112 + /* 113 + ** iMaster is the index of the master chunk. Most new allocations 114 + ** occur off of this chunk. szMaster is the size (in Mem3Blocks) 115 + ** of the current master. iMaster is 0 if there is not master chunk. 116 + ** The master chunk is not in either the aiHash[] or aiSmall[]. 117 + */ 118 + u32 iMaster; 119 + u32 szMaster; 120 + 121 + 122 +u64 totalAlloc; 123 +u64 totalExcess; 124 +int nAlloc; 125 + 126 + /* 127 + ** Array of lists of free blocks according to the block size 128 + ** for smaller chunks, or a hash on the block size for larger 129 + ** chunks. 130 + */ 131 + u32 aiSmall[MX_SMALL-1]; /* For sizes 2 through MX_SMALL, inclusive */ 132 + u32 aiHash[N_HASH]; /* For sizes MX_SMALL+1 and larger */ 133 + 134 + /* 135 + ** Memory available for allocation 136 + */ 137 + Mem3Block aPool[SQLITE_POW2_MEMORY_SIZE/sizeof(Mem3Block)+2]; 138 +} mem; 139 + 140 +/* 141 +** Unlink the chunk at mem.aPool[i] from list it is currently 142 +** on. *pRoot is the list that i is a member of. 143 +*/ 144 +static void memsys3UnlinkFromList(u32 i, u32 *pRoot){ 145 + u32 next = mem.aPool[i].u.list.next; 146 + u32 prev = mem.aPool[i].u.list.prev; 147 + assert( sqlite3_mutex_held(mem.mutex) ); 148 + if( prev==0 ){ 149 + *pRoot = next; 150 + }else{ 151 + mem.aPool[prev].u.list.next = next; 152 + } 153 + if( next ){ 154 + mem.aPool[next].u.list.prev = prev; 155 + } 156 + mem.aPool[i].u.list.next = 0; 157 + mem.aPool[i].u.list.prev = 0; 158 +} 159 + 160 +/* 161 +** Unlink the chunk at index i from 162 +** whatever list is currently a member of. 163 +*/ 164 +static void memsys3Unlink(u32 i){ 165 + u32 size, hash; 166 + assert( sqlite3_mutex_held(mem.mutex) ); 167 + assert( (mem.aPool[i-1].u.hdr.size4x & 1)==0 ); 168 + assert( i>=1 ); 169 + size = mem.aPool[i-1].u.hdr.size4x/4; 170 + assert( size==mem.aPool[i+size-1].u.hdr.prevSize ); 171 + assert( size>=2 ); 172 + if( size <= MX_SMALL ){ 173 + memsys3UnlinkFromList(i, &mem.aiSmall[size-2]); 174 + }else{ 175 + hash = size % N_HASH; 176 + memsys3UnlinkFromList(i, &mem.aiHash[hash]); 177 + } 178 +} 179 + 180 +/* 181 +** Link the chunk at mem.aPool[i] so that is on the list rooted 182 +** at *pRoot. 183 +*/ 184 +static void memsys3LinkIntoList(u32 i, u32 *pRoot){ 185 + assert( sqlite3_mutex_held(mem.mutex) ); 186 + mem.aPool[i].u.list.next = *pRoot; 187 + mem.aPool[i].u.list.prev = 0; 188 + if( *pRoot ){ 189 + mem.aPool[*pRoot].u.list.prev = i; 190 + } 191 + *pRoot = i; 192 +} 193 + 194 +/* 195 +** Link the chunk at index i into either the appropriate 196 +** small chunk list, or into the large chunk hash table. 197 +*/ 198 +static void memsys3Link(u32 i){ 199 + u32 size, hash; 200 + assert( sqlite3_mutex_held(mem.mutex) ); 201 + assert( i>=1 ); 202 + assert( (mem.aPool[i-1].u.hdr.size4x & 1)==0 ); 203 + size = mem.aPool[i-1].u.hdr.size4x/4; 204 + assert( size==mem.aPool[i+size-1].u.hdr.prevSize ); 205 + assert( size>=2 ); 206 + if( size <= MX_SMALL ){ 207 + memsys3LinkIntoList(i, &mem.aiSmall[size-2]); 208 + }else{ 209 + hash = size % N_HASH; 210 + memsys3LinkIntoList(i, &mem.aiHash[hash]); 211 + } 212 +} 213 + 214 +/* 215 +** Enter the mutex mem.mutex. Allocate it if it is not already allocated. 216 +** 217 +** Also: Initialize the memory allocation subsystem the first time 218 +** this routine is called. 219 +*/ 220 +static void memsys3Enter(void){ 221 + if( mem.mutex==0 ){ 222 + mem.mutex = sqlite3_mutex_alloc(SQLITE_MUTEX_STATIC_MEM); 223 + mem.aPool[0].u.hdr.size4x = SQLITE_POW2_MEMORY_SIZE/2 + 2; 224 + mem.aPool[SQLITE_POW2_MEMORY_SIZE/8].u.hdr.prevSize = SQLITE_POW2_MEMORY_SIZE/8; 225 + mem.aPool[SQLITE_POW2_MEMORY_SIZE/8].u.hdr.size4x = 1; 226 + mem.iMaster = 1; 227 + mem.szMaster = SQLITE_POW2_MEMORY_SIZE/8; 228 + mem.mnMaster = mem.szMaster; 229 + } 230 + sqlite3_mutex_enter(mem.mutex); 231 +} 232 + 233 +/* 234 +** Return the amount of memory currently checked out. 235 +*/ 236 +sqlite3_int64 sqlite3_memory_used(void){ 237 + sqlite3_int64 n; 238 + memsys3Enter(); 239 + n = SQLITE_POW2_MEMORY_SIZE - mem.szMaster*8; 240 + sqlite3_mutex_leave(mem.mutex); 241 + return n; 242 +} 243 + 244 +/* 245 +** Return the maximum amount of memory that has ever been 246 +** checked out since either the beginning of this process 247 +** or since the most recent reset. 248 +*/ 249 +sqlite3_int64 sqlite3_memory_highwater(int resetFlag){ 250 + sqlite3_int64 n; 251 + memsys3Enter(); 252 + n = SQLITE_POW2_MEMORY_SIZE - mem.mnMaster*8; 253 + if( resetFlag ){ 254 + mem.mnMaster = mem.szMaster; 255 + } 256 +printf("alloc-cnt=%d avg-size=%lld avg-excess=%lld\n", 257 +mem.nAlloc, mem.totalAlloc/mem.nAlloc, mem.totalExcess/mem.nAlloc); 258 + sqlite3_mutex_leave(mem.mutex); 259 + return n; 260 +} 261 + 262 +/* 263 +** Change the alarm callback. 264 +** 265 +** This is a no-op for the static memory allocator. The purpose 266 +** of the memory alarm is to support sqlite3_soft_heap_limit(). 267 +** But with this memory allocator, the soft_heap_limit is really 268 +** a hard limit that is fixed at SQLITE_POW2_MEMORY_SIZE. 269 +*/ 270 +int sqlite3_memory_alarm( 271 + void(*xCallback)(void *pArg, sqlite3_int64 used,int N), 272 + void *pArg, 273 + sqlite3_int64 iThreshold 274 +){ 275 + return SQLITE_OK; 276 +} 277 + 278 +/* 279 +** Called when we are unable to satisfy an allocation of nBytes. 280 +*/ 281 +static void memsys3OutOfMemory(int nByte){ 282 + if( !mem.alarmBusy ){ 283 + mem.alarmBusy = 1; 284 + assert( sqlite3_mutex_held(mem.mutex) ); 285 + sqlite3_mutex_leave(mem.mutex); 286 + sqlite3_release_memory(nByte); 287 + sqlite3_mutex_enter(mem.mutex); 288 + mem.alarmBusy = 0; 289 + } 290 +} 291 + 292 +/* 293 +** Return the size of an outstanding allocation, in bytes. The 294 +** size returned omits the 8-byte header overhead. This only 295 +** works for chunks that are currently checked out. 296 +*/ 297 +int sqlite3MallocSize(void *p){ 298 + int iSize = 0; 299 + if( p ){ 300 + Mem3Block *pBlock = (Mem3Block*)p; 301 + assert( (pBlock[-1].u.hdr.size4x&1)!=0 ); 302 + iSize = (pBlock[-1].u.hdr.size4x&~3)*2 - 4; 303 + } 304 + return iSize; 305 +} 306 + 307 +/* 308 +** Chunk i is a free chunk that has been unlinked. Adjust its 309 +** size parameters for check-out and return a pointer to the 310 +** user portion of the chunk. 311 +*/ 312 +static void *memsys3Checkout(u32 i, int nBlock){ 313 + u32 x; 314 + assert( sqlite3_mutex_held(mem.mutex) ); 315 + assert( i>=1 ); 316 + assert( mem.aPool[i-1].u.hdr.size4x/4==nBlock ); 317 + assert( mem.aPool[i+nBlock-1].u.hdr.prevSize==nBlock ); 318 + x = mem.aPool[i-1].u.hdr.size4x; 319 + mem.aPool[i-1].u.hdr.size4x = nBlock*4 | 1 | (x&2); 320 + mem.aPool[i+nBlock-1].u.hdr.prevSize = nBlock; 321 + mem.aPool[i+nBlock-1].u.hdr.size4x |= 2; 322 + return &mem.aPool[i]; 323 +} 324 + 325 +/* 326 +** Carve a piece off of the end of the mem.iMaster free chunk. 327 +** Return a pointer to the new allocation. Or, if the master chunk 328 +** is not large enough, return 0. 329 +*/ 330 +static void *memsys3FromMaster(int nBlock){ 331 + assert( sqlite3_mutex_held(mem.mutex) ); 332 + assert( mem.szMaster>=nBlock ); 333 + if( nBlock>=mem.szMaster-1 ){ 334 + /* Use the entire master */ 335 + void *p = memsys3Checkout(mem.iMaster, mem.szMaster); 336 + mem.iMaster = 0; 337 + mem.szMaster = 0; 338 + mem.mnMaster = 0; 339 + return p; 340 + }else{ 341 + /* Split the master block. Return the tail. */ 342 + u32 newi, x; 343 + newi = mem.iMaster + mem.szMaster - nBlock; 344 + assert( newi > mem.iMaster+1 ); 345 + mem.aPool[mem.iMaster+mem.szMaster-1].u.hdr.prevSize = nBlock; 346 + mem.aPool[mem.iMaster+mem.szMaster-1].u.hdr.size4x |= 2; 347 + mem.aPool[newi-1].u.hdr.size4x = nBlock*4 + 1; 348 + mem.szMaster -= nBlock; 349 + mem.aPool[newi-1].u.hdr.prevSize = mem.szMaster; 350 + x = mem.aPool[mem.iMaster-1].u.hdr.size4x & 2; 351 + mem.aPool[mem.iMaster-1].u.hdr.size4x = mem.szMaster*4 | x; 352 + if( mem.szMaster < mem.mnMaster ){ 353 + mem.mnMaster = mem.szMaster; 354 + } 355 + return (void*)&mem.aPool[newi]; 356 + } 357 +} 358 + 359 +/* 360 +** *pRoot is the head of a list of free chunks of the same size 361 +** or same size hash. In other words, *pRoot is an entry in either 362 +** mem.aiSmall[] or mem.aiHash[]. 363 +** 364 +** This routine examines all entries on the given list and tries 365 +** to coalesce each entries with adjacent free chunks. 366 +** 367 +** If it sees a chunk that is larger than mem.iMaster, it replaces 368 +** the current mem.iMaster with the new larger chunk. In order for 369 +** this mem.iMaster replacement to work, the master chunk must be 370 +** linked into the hash tables. That is not the normal state of 371 +** affairs, of course. The calling routine must link the master 372 +** chunk before invoking this routine, then must unlink the (possibly 373 +** changed) master chunk once this routine has finished. 374 +*/ 375 +static void memsys3Merge(u32 *pRoot){ 376 + u32 iNext, prev, size, i, x; 377 + 378 + assert( sqlite3_mutex_held(mem.mutex) ); 379 + for(i=*pRoot; i>0; i=iNext){ 380 + iNext = mem.aPool[i].u.list.next; 381 + size = mem.aPool[i-1].u.hdr.size4x; 382 + assert( (size&1)==0 ); 383 + if( (size&2)==0 ){ 384 + memsys3UnlinkFromList(i, pRoot); 385 + assert( i > mem.aPool[i-1].u.hdr.prevSize ); 386 + prev = i - mem.aPool[i-1].u.hdr.prevSize; 387 + if( prev==iNext ){ 388 + iNext = mem.aPool[prev].u.list.next; 389 + } 390 + memsys3Unlink(prev); 391 + size = i + size/4 - prev; 392 + x = mem.aPool[prev-1].u.hdr.size4x & 2; 393 + mem.aPool[prev-1].u.hdr.size4x = size*4 | x; 394 + mem.aPool[prev+size-1].u.hdr.prevSize = size; 395 + memsys3Link(prev); 396 + i = prev; 397 + }else{ 398 + size /= 4; 399 + } 400 + if( size>mem.szMaster ){ 401 + mem.iMaster = i; 402 + mem.szMaster = size; 403 + } 404 + } 405 +} 406 + 407 +/* 408 +** Return a block of memory of at least nBytes in size. 409 +** Return NULL if unable. 410 +*/ 411 +static void *memsys3Malloc(int nByte){ 412 + u32 i; 413 + int nBlock; 414 + int toFree; 415 + int x; 416 + 417 + assert( sqlite3_mutex_held(mem.mutex) ); 418 + assert( sizeof(Mem3Block)==8 ); 419 + for(x=256; x<nByte; x *= 2){} 420 +mem.nAlloc++; 421 +mem.totalAlloc += x; 422 +mem.totalExcess += x - nByte; 423 + nByte = x; 424 + nBlock = (nByte + 11)/8; 425 + assert( nBlock >= 2 ); 426 + 427 + /* STEP 1: 428 + ** Look for an entry of the correct size in either the small 429 + ** chunk table or in the large chunk hash table. This is 430 + ** successful most of the time (about 9 times out of 10). 431 + */ 432 + if( nBlock <= MX_SMALL ){ 433 + i = mem.aiSmall[nBlock-2]; 434 + if( i>0 ){ 435 + memsys3UnlinkFromList(i, &mem.aiSmall[nBlock-2]); 436 + return memsys3Checkout(i, nBlock); 437 + } 438 + }else{ 439 + int hash = nBlock % N_HASH; 440 + for(i=mem.aiHash[hash]; i>0; i=mem.aPool[i].u.list.next){ 441 + if( mem.aPool[i-1].u.hdr.size4x/4==nBlock ){ 442 + memsys3UnlinkFromList(i, &mem.aiHash[hash]); 443 + return memsys3Checkout(i, nBlock); 444 + } 445 + } 446 + } 447 + 448 + /* STEP 2: 449 + ** Try to satisfy the allocation by carving a piece off of the end 450 + ** of the master chunk. This step usually works if step 1 fails. 451 + */ 452 + if( mem.szMaster>=nBlock ){ 453 + return memsys3FromMaster(nBlock); 454 + } 455 + 456 + 457 + /* STEP 3: 458 + ** Loop through the entire memory pool. Coalesce adjacent free 459 + ** chunks. Recompute the master chunk as the largest free chunk. 460 + ** Then try again to satisfy the allocation by carving a piece off 461 + ** of the end of the master chunk. This step happens very 462 + ** rarely (we hope!) 463 + */ 464 + for(toFree=nBlock*16; toFree<SQLITE_POW2_MEMORY_SIZE*2; toFree *= 2){ 465 + memsys3OutOfMemory(toFree); 466 + if( mem.iMaster ){ 467 + memsys3Link(mem.iMaster); 468 + mem.iMaster = 0; 469 + mem.szMaster = 0; 470 + } 471 + for(i=0; i<N_HASH; i++){ 472 + memsys3Merge(&mem.aiHash[i]); 473 + } 474 + for(i=0; i<MX_SMALL-1; i++){ 475 + memsys3Merge(&mem.aiSmall[i]); 476 + } 477 + if( mem.szMaster ){ 478 + memsys3Unlink(mem.iMaster); 479 + if( mem.szMaster>=nBlock ){ 480 + return memsys3FromMaster(nBlock); 481 + } 482 + } 483 + } 484 + 485 + /* If none of the above worked, then we fail. */ 486 + return 0; 487 +} 488 + 489 +/* 490 +** Free an outstanding memory allocation. 491 +*/ 492 +void memsys3Free(void *pOld){ 493 + Mem3Block *p = (Mem3Block*)pOld; 494 + int i; 495 + u32 size, x; 496 + assert( sqlite3_mutex_held(mem.mutex) ); 497 + assert( p>mem.aPool && p<&mem.aPool[SQLITE_POW2_MEMORY_SIZE/8] ); 498 + i = p - mem.aPool; 499 + assert( (mem.aPool[i-1].u.hdr.size4x&1)==1 ); 500 + size = mem.aPool[i-1].u.hdr.size4x/4; 501 + assert( i+size<=SQLITE_POW2_MEMORY_SIZE/8+1 ); 502 + mem.aPool[i-1].u.hdr.size4x &= ~1; 503 + mem.aPool[i+size-1].u.hdr.prevSize = size; 504 + mem.aPool[i+size-1].u.hdr.size4x &= ~2; 505 + memsys3Link(i); 506 + 507 + /* Try to expand the master using the newly freed chunk */ 508 + if( mem.iMaster ){ 509 + while( (mem.aPool[mem.iMaster-1].u.hdr.size4x&2)==0 ){ 510 + size = mem.aPool[mem.iMaster-1].u.hdr.prevSize; 511 + mem.iMaster -= size; 512 + mem.szMaster += size; 513 + memsys3Unlink(mem.iMaster); 514 + x = mem.aPool[mem.iMaster-1].u.hdr.size4x & 2; 515 + mem.aPool[mem.iMaster-1].u.hdr.size4x = mem.szMaster*4 | x; 516 + mem.aPool[mem.iMaster+mem.szMaster-1].u.hdr.prevSize = mem.szMaster; 517 + } 518 + x = mem.aPool[mem.iMaster-1].u.hdr.size4x & 2; 519 + while( (mem.aPool[mem.iMaster+mem.szMaster-1].u.hdr.size4x&1)==0 ){ 520 + memsys3Unlink(mem.iMaster+mem.szMaster); 521 + mem.szMaster += mem.aPool[mem.iMaster+mem.szMaster-1].u.hdr.size4x/4; 522 + mem.aPool[mem.iMaster-1].u.hdr.size4x = mem.szMaster*4 | x; 523 + mem.aPool[mem.iMaster+mem.szMaster-1].u.hdr.prevSize = mem.szMaster; 524 + } 525 + } 526 +} 527 + 528 +/* 529 +** Allocate nBytes of memory 530 +*/ 531 +void *sqlite3_malloc(int nBytes){ 532 + sqlite3_int64 *p = 0; 533 + if( nBytes>0 ){ 534 + memsys3Enter(); 535 + p = memsys3Malloc(nBytes); 536 + sqlite3_mutex_leave(mem.mutex); 537 + } 538 + return (void*)p; 539 +} 540 + 541 +/* 542 +** Free memory. 543 +*/ 544 +void sqlite3_free(void *pPrior){ 545 + if( pPrior==0 ){ 546 + return; 547 + } 548 + assert( mem.mutex!=0 ); 549 + sqlite3_mutex_enter(mem.mutex); 550 + memsys3Free(pPrior); 551 + sqlite3_mutex_leave(mem.mutex); 552 +} 553 + 554 +/* 555 +** Change the size of an existing memory allocation 556 +*/ 557 +void *sqlite3_realloc(void *pPrior, int nBytes){ 558 + int nOld; 559 + void *p; 560 + if( pPrior==0 ){ 561 + return sqlite3_malloc(nBytes); 562 + } 563 + if( nBytes<=0 ){ 564 + sqlite3_free(pPrior); 565 + return 0; 566 + } 567 + assert( mem.mutex!=0 ); 568 + nOld = sqlite3MallocSize(pPrior); 569 + if( nBytes<=nOld && nBytes>=nOld-128 ){ 570 + return pPrior; 571 + } 572 + sqlite3_mutex_enter(mem.mutex); 573 + p = memsys3Malloc(nBytes); 574 + if( p ){ 575 + if( nOld<nBytes ){ 576 + memcpy(p, pPrior, nOld); 577 + }else{ 578 + memcpy(p, pPrior, nBytes); 579 + } 580 + memsys3Free(pPrior); 581 + } 582 + sqlite3_mutex_leave(mem.mutex); 583 + return p; 584 +} 585 + 586 +/* 587 +** Open the file indicated and write a log of all unfreed memory 588 +** allocations into that log. 589 +*/ 590 +void sqlite3_memdebug_dump(const char *zFilename){ 591 +#ifdef SQLITE_DEBUG 592 + FILE *out; 593 + int i, j; 594 + u32 size; 595 + if( zFilename==0 || zFilename[0]==0 ){ 596 + out = stdout; 597 + }else{ 598 + out = fopen(zFilename, "w"); 599 + if( out==0 ){ 600 + fprintf(stderr, "** Unable to output memory debug output log: %s **\n", 601 + zFilename); 602 + return; 603 + } 604 + } 605 + memsys3Enter(); 606 + fprintf(out, "CHUNKS:\n"); 607 + for(i=1; i<=SQLITE_POW2_MEMORY_SIZE/8; i+=size/4){ 608 + size = mem.aPool[i-1].u.hdr.size4x; 609 + if( size/4<=1 ){ 610 + fprintf(out, "%p size error\n", &mem.aPool[i]); 611 + assert( 0 ); 612 + break; 613 + } 614 + if( (size&1)==0 && mem.aPool[i+size/4-1].u.hdr.prevSize!=size/4 ){ 615 + fprintf(out, "%p tail size does not match\n", &mem.aPool[i]); 616 + assert( 0 ); 617 + break; 618 + } 619 + if( ((mem.aPool[i+size/4-1].u.hdr.size4x&2)>>1)!=(size&1) ){ 620 + fprintf(out, "%p tail checkout bit is incorrect\n", &mem.aPool[i]); 621 + assert( 0 ); 622 + break; 623 + } 624 + if( size&1 ){ 625 + fprintf(out, "%p %6d bytes checked out\n", &mem.aPool[i], (size/4)*8-8); 626 + }else{ 627 + fprintf(out, "%p %6d bytes free%s\n", &mem.aPool[i], (size/4)*8-8, 628 + i==mem.iMaster ? " **master**" : ""); 629 + } 630 + } 631 + for(i=0; i<MX_SMALL-1; i++){ 632 + if( mem.aiSmall[i]==0 ) continue; 633 + fprintf(out, "small(%2d):", i); 634 + for(j = mem.aiSmall[i]; j>0; j=mem.aPool[j].u.list.next){ 635 + fprintf(out, " %p(%d)", &mem.aPool[j], 636 + (mem.aPool[j-1].u.hdr.size4x/4)*8-8); 637 + } 638 + fprintf(out, "\n"); 639 + } 640 + for(i=0; i<N_HASH; i++){ 641 + if( mem.aiHash[i]==0 ) continue; 642 + fprintf(out, "hash(%2d):", i); 643 + for(j = mem.aiHash[i]; j>0; j=mem.aPool[j].u.list.next){ 644 + fprintf(out, " %p(%d)", &mem.aPool[j], 645 + (mem.aPool[j-1].u.hdr.size4x/4)*8-8); 646 + } 647 + fprintf(out, "\n"); 648 + } 649 + fprintf(out, "master=%d\n", mem.iMaster); 650 + fprintf(out, "nowUsed=%d\n", SQLITE_POW2_MEMORY_SIZE - mem.szMaster*8); 651 + fprintf(out, "mxUsed=%d\n", SQLITE_POW2_MEMORY_SIZE - mem.mnMaster*8); 652 + sqlite3_mutex_leave(mem.mutex); 653 + if( out==stdout ){ 654 + fflush(stdout); 655 + }else{ 656 + fclose(out); 657 + } 658 +#endif 659 +} 660 + 661 + 662 +#endif /* !SQLITE_POW2_MEMORY_SIZE */
Changes to src/pager.c.
14 14 ** The pager is used to access a database disk file. It implements 15 15 ** atomic commit and rollback through the use of a journal file that 16 16 ** is separate from the database file. The pager also implements file 17 17 ** locking to prevent two processes from writing the same database 18 18 ** file simultaneously, or one process from reading the database while 19 19 ** another is writing. 20 20 ** 21 -** @(#) $Id: pager.c,v 1.405 2008/02/02 20:47:38 drh Exp $ 21 +** @(#) $Id: pager.c,v 1.406 2008/02/14 23:26:56 drh Exp $ 22 22 */ 23 23 #ifndef SQLITE_OMIT_DISKIO 24 24 #include "sqliteInt.h" 25 25 #include <assert.h> 26 26 #include <string.h> 27 27 28 28 /* ................................................................................ 1205 1205 PgHdr *pPg, *pNext; 1206 1206 if( pPager->errCode ) return; 1207 1207 for(pPg=pPager->pAll; pPg; pPg=pNext){ 1208 1208 IOTRACE(("PGFREE %p %d\n", pPager, pPg->pgno)); 1209 1209 PAGER_INCR(sqlite3_pager_pgfree_count); 1210 1210 pNext = pPg->pNextAll; 1211 1211 lruListRemove(pPg); 1212 + sqlite3_free(pPg->pData); 1212 1213 sqlite3_free(pPg); 1213 1214 } 1214 1215 assert(pPager->lru.pFirst==0); 1215 1216 assert(pPager->lru.pFirstSynced==0); 1216 1217 assert(pPager->lru.pLast==0); 1217 1218 pPager->pStmt = 0; 1218 1219 pPager->pAll = 0; ................................................................................ 2535 2536 ppPg = &pPg->pNextAll; 2536 2537 }else{ 2537 2538 *ppPg = pPg->pNextAll; 2538 2539 IOTRACE(("PGFREE %p %d\n", pPager, pPg->pgno)); 2539 2540 PAGER_INCR(sqlite3_pager_pgfree_count); 2540 2541 unlinkPage(pPg); 2541 2542 makeClean(pPg); 2543 + sqlite3_free(pPg->pData); 2542 2544 sqlite3_free(pPg); 2543 2545 pPager->nPage--; 2544 2546 } 2545 2547 } 2546 2548 } 2547 2549 2548 2550 /* ................................................................................ 3201 3203 nReleased += ( 3202 3204 sizeof(*pPg) + pPager->pageSize 3203 3205 + sizeof(u32) + pPager->nExtra 3204 3206 + MEMDB*sizeof(PgHistory) 3205 3207 ); 3206 3208 IOTRACE(("PGFREE %p %d *\n", pPager, pPg->pgno)); 3207 3209 PAGER_INCR(sqlite3_pager_pgfree_count); 3210 + sqlite3_free(pPg->pData); 3208 3211 sqlite3_free(pPg); 3209 3212 pPager->nPage--; 3210 3213 }else{ 3211 3214 /* An error occured whilst writing to the database file or 3212 3215 ** journal in pager_recycle(). The error is not returned to the 3213 3216 ** caller of this function. Instead, set the Pager.errCode variable. 3214 3217 ** The error will be returned to the user (or users, in the case ................................................................................ 3472 3475 /* Create a new PgHdr if any of the four conditions defined 3473 3476 ** above are met: */ 3474 3477 if( pPager->nPage<pPager->mxPage 3475 3478 || pPager->lru.pFirst==0 3476 3479 || MEMDB 3477 3480 || (pPager->lru.pFirstSynced==0 && pPager->doNotSync) 3478 3481 ){ 3482 + void *pData; 3479 3483 if( pPager->nPage>=pPager->nHash ){ 3480 3484 pager_resize_hash_table(pPager, 3481 3485 pPager->nHash<256 ? 256 : pPager->nHash*2); 3482 3486 if( pPager->nHash==0 ){ 3483 3487 rc = SQLITE_NOMEM; 3484 3488 goto pager_allocate_out; 3485 3489 } 3486 3490 } 3487 3491 pagerLeave(pPager); 3488 3492 nByteHdr = sizeof(*pPg) + sizeof(u32) + pPager->nExtra 3489 3493 + MEMDB*sizeof(PgHistory); 3490 - pPg = sqlite3_malloc( nByteHdr + pPager->pageSize ); 3494 + pPg = sqlite3_malloc( nByteHdr ); 3495 + if( pPg ){ 3496 + pData = sqlite3_malloc( pPager->pageSize ); 3497 + if( pData==0 ){ 3498 + sqlite3_free(pPg); 3499 + pPg = 0; 3500 + } 3501 + } 3491 3502 pagerEnter(pPager); 3492 3503 if( pPg==0 ){ 3493 3504 rc = SQLITE_NOMEM; 3494 3505 goto pager_allocate_out; 3495 3506 } 3496 3507 memset(pPg, 0, nByteHdr); 3497 - pPg->pData = (void*)(nByteHdr + (char*)pPg); 3508 + pPg->pData = pData; 3498 3509 pPg->pPager = pPager; 3499 3510 pPg->pNextAll = pPager->pAll; 3500 3511 pPager->pAll = pPg; 3501 3512 pPager->nPage++; 3502 3513 }else{ 3503 3514 /* Recycle an existing page with a zero ref-count. */ 3504 3515 rc = pager_recycle(pPager, &pPg);
Changes to src/sqliteInt.h.
7 7 ** May you do good and not evil. 8 8 ** May you find forgiveness for yourself and forgive others. 9 9 ** May you share freely, never taking more than you give. 10 10 ** 11 11 ************************************************************************* 12 12 ** Internal interface definitions for SQLite. 13 13 ** 14 -** @(#) $Id: sqliteInt.h,v 1.661 2008/02/13 18:25:27 danielk1977 Exp $ 14 +** @(#) $Id: sqliteInt.h,v 1.662 2008/02/14 23:26:56 drh Exp $ 15 15 */ 16 16 #ifndef _SQLITEINT_H_ 17 17 #define _SQLITEINT_H_ 18 18 19 19 /* 20 20 ** The macro unlikely() is a hint that surrounds a boolean 21 21 ** expression that is usually false. Macro likely() surrounds ................................................................................ 113 113 #if defined(THREADSAFE) 114 114 # define SQLITE_THREADSAFE THREADSAFE 115 115 #else 116 116 # define SQLITE_THREADSAFE 1 117 117 #endif 118 118 #endif 119 119 120 +/* 121 +** Exactly one of the following macros must be defined in order to 122 +** specify which memory allocation subsystem to use. 123 +** 124 +** SQLITE_SYSTEM_MALLOC // Use normal system malloc() 125 +** SQLITE_MEMDEBUG // Debugging version of system malloc() 126 +** SQLITE_MEMORY_SIZE // internal allocator #1 127 +** SQLITE_MMAP_HEAP_SIZE // internal mmap() allocator 128 +** SQLITE_POW2_MEMORY_SIZE // internal power-of-two allocator 129 +** 130 +** If none of the above are defined, then set SQLITE_SYSTEM_MALLOC as 131 +** the default. 132 +*/ 133 +#if defined(SQLITE_SYSTEM_MALLOC)+defined(SQLITE_MEMDEBUG)+\ 134 + defined(SQLITE_MEMORY_SIZE)+defined(SQLITE_MMAP_HEAP_SIZE)+\ 135 + defined(SQLITE_POW2_MEMORY_SIZE)>1 136 +# error "At most one of the following compile-time configuration options\ 137 + is allows: SQLITE_SYSTEM_MALLOC, SQLITE_MEMDEBUG, SQLITE_MEMORY_SIZE,\ 138 + SQLITE_MMAP_HEAP_SIZE, SQLITE_POW2_MEMORY_SIZE" 139 +#endif 140 +#if defined(SQLITE_SYSTEM_MALLOC)+defined(SQLITE_MEMDEBUG)+\ 141 + defined(SQLITE_MEMORY_SIZE)+defined(SQLITE_MMAP_HEAP_SIZE)+\ 142 + defined(SQLITE_POW2_MEMORY_SIZE)==0 143 +# define SQLITE_SYSTEM_MALLOC 1 144 +#endif 145 + 120 146 /* 121 147 ** We need to define _XOPEN_SOURCE as follows in order to enable 122 148 ** recursive mutexes on most unix systems. But Mac OS X is different. 123 149 ** The _XOPEN_SOURCE define causes problems for Mac OS X we are told, 124 150 ** so it is omitted there. See ticket #2673. 125 151 ** 126 152 ** Later we learn that _XOPEN_SOURCE is poorly or incorrectly