/ Check-in [4f95f4cd]
Login

Many hyperlinks are disabled.
Use anonymous login to enable hyperlinks.

Overview
Comment:Change mem5.c so that the minimum allocation size is runtime configurable. (CVS 5320)
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1: 4f95f4cdf77e134fab42148e10198c7b008d4ae6
User & Date: danielk1977 2008-06-27 13:27:04
Context
2008-06-27
14:05
Fix mem3.c (broken by (5320)). (CVS 5321) check-in: fef90a21 user: danielk1977 tags: trunk
13:27
Change mem5.c so that the minimum allocation size is runtime configurable. (CVS 5320) check-in: 4f95f4cd user: danielk1977 tags: trunk
00:52
Remove unused variable. Fix a compiler warning. (CVS 5319) check-in: 0b01ec5c user: drh tags: trunk
Changes
Hide Diffs Unified Diffs Ignore Whitespace Patch

Changes to src/main.c.

10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
...
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
...
227
228
229
230
231
232
233

234
235
236
237
238











239
240









241
242
243
244
245
246
247
**
*************************************************************************
** Main file for the SQLite library.  The routines in this file
** implement the programmer interface to the library.  Routines in
** other files are for internal use by SQLite and should not be
** accessed by users of the library.
**
** $Id: main.c,v 1.465 2008/06/26 10:54:12 danielk1977 Exp $
*/
#include "sqliteInt.h"
#include <ctype.h>

#ifdef SQLITE_ENABLE_FTS3
# include "fts3.h"
#endif
................................................................................
    }
    case SQLITE_CONFIG_SERIALIZED: {
      /* Enable all mutexing */
      sqlite3Config.bCoreMutex = 1;
      sqlite3Config.bFullMutex = 1;
      break;
    }
#ifdef SQLITE_ENABLE_MEMSYS3
    case SQLITE_CONFIG_MEMSYS3: {
      u8 *pMem = va_arg(ap, u8*);
      int nMem = va_arg(ap, int);
      sqlite3MemSetMemsys3(pMem, nMem);
      break;
    }
#endif
#ifdef SQLITE_ENABLE_MEMSYS5
    case SQLITE_CONFIG_MEMSYS5: {
      u8 *pMem = va_arg(ap, u8*);
      int nMem = va_arg(ap, int);
      sqlite3MemSetMemsys5(pMem, nMem);
      break;
    }
#endif
    case SQLITE_CONFIG_MALLOC: {
      /* Specify an alternative malloc implementation */
      sqlite3Config.m = *va_arg(ap, sqlite3_mem_methods*);
      break;
    }
    case SQLITE_CONFIG_GETMALLOC: {
      /* Retrieve the current malloc() implementation */
................................................................................
    case SQLITE_CONFIG_PAGECACHE: {
      /* Designate a buffer for scratch memory space */
      sqlite3Config.pPage = va_arg(ap, void*);
      sqlite3Config.szPage = va_arg(ap, int);
      sqlite3Config.nPage = va_arg(ap, int);
      break;
    }

    case SQLITE_CONFIG_HEAP: {
      /* Designate a buffer for scratch memory space */
      sqlite3Config.pHeap = va_arg(ap, void*);
      sqlite3Config.nHeap = va_arg(ap, int);
      sqlite3Config.mnReq = va_arg(ap, int);











      break;
    }









    default: {
      rc = SQLITE_ERROR;
      break;
    }
  }
  va_end(ap);
  return rc;







|







 







<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<







 







>

|



>
>
>
>
>
>
>
>
>
>
>


>
>
>
>
>
>
>
>
>







10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
...
171
172
173
174
175
176
177
















178
179
180
181
182
183
184
...
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
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
**
*************************************************************************
** Main file for the SQLite library.  The routines in this file
** implement the programmer interface to the library.  Routines in
** other files are for internal use by SQLite and should not be
** accessed by users of the library.
**
** $Id: main.c,v 1.466 2008/06/27 13:27:04 danielk1977 Exp $
*/
#include "sqliteInt.h"
#include <ctype.h>

#ifdef SQLITE_ENABLE_FTS3
# include "fts3.h"
#endif
................................................................................
    }
    case SQLITE_CONFIG_SERIALIZED: {
      /* Enable all mutexing */
      sqlite3Config.bCoreMutex = 1;
      sqlite3Config.bFullMutex = 1;
      break;
    }
















    case SQLITE_CONFIG_MALLOC: {
      /* Specify an alternative malloc implementation */
      sqlite3Config.m = *va_arg(ap, sqlite3_mem_methods*);
      break;
    }
    case SQLITE_CONFIG_GETMALLOC: {
      /* Retrieve the current malloc() implementation */
................................................................................
    case SQLITE_CONFIG_PAGECACHE: {
      /* Designate a buffer for scratch memory space */
      sqlite3Config.pPage = va_arg(ap, void*);
      sqlite3Config.szPage = va_arg(ap, int);
      sqlite3Config.nPage = va_arg(ap, int);
      break;
    }

    case SQLITE_CONFIG_HEAP: {
      /* Designate a buffer for heap memory space */
      sqlite3Config.pHeap = va_arg(ap, void*);
      sqlite3Config.nHeap = va_arg(ap, int);
      sqlite3Config.mnReq = va_arg(ap, int);

      /* Fall through to install the mem5.c/mem3.c methods. If neither
      ** ENABLE_MEMSYS3 nor ENABLE_MEMSYS5 is defined, fall through to
      ** the default case and return an error.
      */
    }

#ifdef SQLITE_ENABLE_MEMSYS5
    case SQLITE_CONFIG_MEMSYS5: {
      sqlite3_mem_methods *p = sqlite3MemGetMemsys5();
      sqlite3Config.m = *p;
      break;
    }
#endif
#ifdef SQLITE_ENABLE_MEMSYS3
    case SQLITE_CONFIG_MEMSYS3: {
      sqlite3_mem_methods *p = sqlite3MemGetMemsys3();
      sqlite3Config.m = *p;
      break;
    }
#endif

    default: {
      rc = SQLITE_ERROR;
      break;
    }
  }
  va_end(ap);
  return rc;

Changes to src/mem5.c.

19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
..
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
..
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
84
85
...
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
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
...
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
...
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
...
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288





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
...
340
341
342
343
344
345
346

347
348
349
350
351
352
353
...
379
380
381
382
383
384
385
386
387
388






389
390
391
392
393































394
395
396
397
398
399
400
...
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
...
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
485
486
487
488
** 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.
**
** $Id: mem5.c,v 1.8 2008/06/25 14:57:54 danielk1977 Exp $
*/
#include "sqliteInt.h"

/*
** This version of the memory allocator is used only when 
** SQLITE_POW2_MEMORY_SIZE is defined.
*/
................................................................................
** Log2 of the minimum size of an allocation.  For example, if
** 4 then all allocations will be rounded up to at least 16 bytes.
** If 5 then all allocations will be rounded up to at least 32 bytes.
*/
#ifndef SQLITE_POW2_LOGMIN
# define SQLITE_POW2_LOGMIN 6
#endif
#define POW2_MIN (1<<SQLITE_POW2_LOGMIN)

/*
** Log2 of the maximum size of an allocation.
*/
#ifndef SQLITE_POW2_LOGMAX
# define SQLITE_POW2_LOGMAX 18
#endif
................................................................................
#define NSIZE (SQLITE_POW2_LOGMAX - SQLITE_POW2_LOGMIN + 1)

/*
** 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.
*/
typedef struct Mem5Block Mem5Block;
struct Mem5Block {
  union {
    char aData[POW2_MIN];
    struct {
      int next;       /* Index in mem5.aPool[] of next free chunk */
      int prev;       /* Index in mem5.aPool[] of previous free chunk */
    } list;
  } u;
};

/*
** The size in blocks of an POW2_MAX allocation


*/
#define SZ_MAX (1<<(NSIZE-1))


/*
** Masks used for mem5.aCtrl[] elements.
*/
#define CTRL_LOGSIZE  0x1f    /* Log2 Size of this block relative to POW2_MIN */
#define CTRL_FREE     0x20    /* True if not checked out */

................................................................................
  u32 maxOut;         /* Maximum instantaneous currentOut */
  u32 maxCount;       /* Maximum instantaneous currentCount */
  u32 maxRequest;     /* Largest allocation (exclusive of internal frag) */
  
  /*
  ** Lists of free blocks of various sizes.
  */
  int aiFreelist[NSIZE];

  /*
  ** Space for tracking which blocks are checked out and the size
  ** of each block.  One byte per block.
  */
  u8 *aCtrl;

  /*
  ** Memory available for allocation
  */
  int nBlock;

  Mem5Block *aPool;
} mem5;



/*
** 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;
  assert( i>=0 && i<mem5.nBlock );
  assert( iLogsize>=0 && iLogsize<NSIZE );
  assert( (mem5.aCtrl[i] & CTRL_LOGSIZE)==iLogsize );

  next = mem5.aPool[i].u.list.next;
  prev = mem5.aPool[i].u.list.prev;
  if( prev<0 ){
    mem5.aiFreelist[iLogsize] = next;
  }else{
    mem5.aPool[prev].u.list.next = next;
  }
  if( next>=0 ){
    mem5.aPool[next].u.list.prev = prev;
  }
}

/*
** Link the chunk at mem5.aPool[i] so that is on the iLogsize
** free list.
*/
static void memsys5Link(int i, int iLogsize){
  int x;
  assert( sqlite3_mutex_held(mem5.mutex) );
  assert( i>=0 && i<mem5.nBlock );
  assert( iLogsize>=0 && iLogsize<NSIZE );
  assert( (mem5.aCtrl[i] & CTRL_LOGSIZE)==iLogsize );

  mem5.aPool[i].u.list.next = x = mem5.aiFreelist[iLogsize];
  mem5.aPool[i].u.list.prev = -1;
  if( x>=0 ){
    assert( x<mem5.nBlock );
    mem5.aPool[x].u.list.prev = i;
  }
  mem5.aiFreelist[iLogsize] = i;
}

/*
** If the STATIC_MEM mutex is not already held, obtain it now. The mutex
** will already be held (obtained by code in malloc.c) if
................................................................................
** 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 = ((Mem5Block*)p) - mem5.aPool;
    assert( i>=0 && i<mem5.nBlock );
    iSize = 1 << ((mem5.aCtrl[i]&CTRL_LOGSIZE) + SQLITE_POW2_LOGMIN);
  }
  return iSize;
}

/*
** Find the first entry on the freelist iLogsize.  Unlink that
** entry and return its index. 
*/
static int memsys5UnlinkFirst(int iLogsize){
  int i;
  int iFirst;

  assert( iLogsize>=0 && iLogsize<NSIZE );
  i = iFirst = mem5.aiFreelist[iLogsize];
  assert( iFirst>=0 );
  while( i>0 ){
    if( i<iFirst ) iFirst = i;
    i = mem5.aPool[i].u.list.next;
  }
  memsys5Unlink(iFirst, iLogsize);
  return iFirst;
}

/*
** Return a block of memory of at least nBytes in size.
................................................................................
  ** requests are counted */
  if( nByte>mem5.maxRequest ){
    mem5.maxRequest = nByte;
  }

  /* Round nByte up to the next valid power of two */
  if( nByte>POW2_MAX ) return 0;
  for(iFullSz=POW2_MIN, 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<NSIZE; iBin++){}
  if( iBin>=NSIZE ) return 0;
  i = memsys5UnlinkFirst(iBin);
  while( iBin>iLogsize ){
    int newSize;

    iBin--;
    newSize = 1 << iBin;
    mem5.aCtrl[i+newSize] = CTRL_FREE | iBin;
................................................................................
  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.aPool[i];
}

/*
** Free an outstanding memory allocation.
*/
static void memsys5FreeUnsafe(void *pOld){
  u32 size, iLogsize;
  int i;

  i = ((Mem5Block*)pOld) - mem5.aPool;





  assert( i>=0 && i<mem5.nBlock );

  assert( (mem5.aCtrl[i] & CTRL_FREE)==0 );

  iLogsize = mem5.aCtrl[i] & CTRL_LOGSIZE;
  size = 1<<iLogsize;
  assert( i+size-1<mem5.nBlock );

  mem5.aCtrl[i] |= CTRL_FREE;
  mem5.aCtrl[i+size-1] |= CTRL_FREE;
  assert( mem5.currentCount>0 );
  assert( mem5.currentOut>=0 );
  mem5.currentCount--;
  mem5.currentOut -= size*POW2_MIN;
  assert( mem5.currentOut>0 || mem5.currentCount==0 );
  assert( mem5.currentCount>0 || mem5.currentOut==0 );

  mem5.aCtrl[i] = CTRL_FREE | iLogsize;
  while( iLogsize<NSIZE-1 ){
    int iBuddy;

    if( (i>>iLogsize) & 1 ){
      iBuddy = i - size;
    }else{
      iBuddy = i + size;
    }
    assert( iBuddy>=0 && iBuddy<mem5.nBlock );

    if( mem5.aCtrl[iBuddy]!=(CTRL_FREE | iLogsize) ) break;
    memsys5Unlink(iBuddy, iLogsize);
    iLogsize++;
    if( iBuddy<i ){
      mem5.aCtrl[iBuddy] = CTRL_FREE | iLogsize;
      mem5.aCtrl[i] = 0;
      i = iBuddy;
    }else{
      mem5.aCtrl[i] = CTRL_FREE | iLogsize;
      mem5.aCtrl[iBuddy] = 0;
    }
    size *= 2;
  }
  memsys5Link(i, iLogsize);
}

/*
** Allocate nBytes of memory
*/
static void *memsys5Malloc(int nBytes){
  sqlite3_int64 *p = 0;
................................................................................
}

/*
** Free memory.
*/
static void memsys5Free(void *pPrior){
  if( pPrior==0 ){

    return;
  }
  memsys5Enter();
  memsys5FreeUnsafe(pPrior);
  memsys5Leave();  
}

................................................................................
}

/*
** Round up a request size to the next valid allocation size.
*/
static int memsys5Roundup(int n){
  int iFullSz;
  for(iFullSz=POW2_MIN; iFullSz<n; iFullSz *= 2);
  return iFullSz;
}







/*
** Initialize this module.
*/
static int memsys5Init(void *NotUsed){































  return SQLITE_OK;
}

/*
** Deinitialize this module.
*/
static void memsys5Shutdown(void *NotUsed){
................................................................................
** Open the file indicated and write a log of all unfreed memory 
** allocations into that log.
*/
void sqlite3Memsys5Dump(const char *zFilename){
#ifdef SQLITE_DEBUG
  FILE *out;
  int i, j, n;


  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();
  for(i=0; i<NSIZE; i++){

    for(n=0, j=mem5.aiFreelist[i]; j>=0; j = mem5.aPool[j].u.list.next, n++){}
    fprintf(out, "freelist items of size %d: %d\n", POW2_MIN << 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);
................................................................................
    fclose(out);
  }
#endif
}

/*
** This routine is the only routine in this file with external 
** linkage.
**
** Populate the low-level memory allocation function pointers in
** sqlite3Config.m with pointers to the routines in this file. The
** arguments specify the block of memory to manage.
**
** This routine is only called by sqlite3_config(), and therefore
** is not required to be threadsafe (it is not).
*/
void sqlite3MemSetMemsys5(u8 *zByte, int nByte){

  static const sqlite3_mem_methods memsys5Methods = {
     memsys5Malloc,
     memsys5Free,
     memsys5Realloc,
     memsys5Size,
     memsys5Roundup,
     memsys5Init,
     memsys5Shutdown,
     0
  };
  int i;

  mem5.nBlock = (nByte / (sizeof(Mem5Block)+sizeof(u8)));
  mem5.nBlock -= (mem5.nBlock%SZ_MAX);
  mem5.aPool = (Mem5Block *)zByte;
  mem5.aCtrl = (u8 *)&mem5.aPool[mem5.nBlock];

  assert( sizeof(Mem5Block)==POW2_MIN );
  assert( mem5.nBlock>=SZ_MAX );
  assert( (mem5.nBlock%SZ_MAX)==0 );

  for(i=0; i<NSIZE; i++) mem5.aiFreelist[i] = -1;
  for(i=0; i<=mem5.nBlock-SZ_MAX; i += SZ_MAX){
    mem5.aCtrl[i] = (NSIZE-1) | CTRL_FREE;
    memsys5Link(i, NSIZE-1);
  }

  /* Configure the functions to call to allocate memory. */
  sqlite3_config(SQLITE_CONFIG_MALLOC, &memsys5Methods);
}

#endif /* SQLITE_ENABLE_MEMSYS5 */







|







 







<







 







|
|
<
<
<
|
|
<
<



|
>
>

<
>







 







|










|
>
|

>
>








|


|
|



|


|











|


|
|


|







 







|

|












|




|







 







|





|
|







 







|







|

|
>
>
>
>
>
|
>
|
>
|

|
>
|
|



|



|
|

<
|
|

|

|
>



|

|
|

|




|







 







>







 







|


>
>
>
>
>
>





>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>







 







>












|
>
|
|







 







|
|
<
<
<
<
<
<

<
>










<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
|



19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
..
37
38
39
40
41
42
43

44
45
46
47
48
49
50
..
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
...
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
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
...
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
...
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
...
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
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
338
339
340
...
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
...
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
...
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
...
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
** 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.
**
** $Id: mem5.c,v 1.9 2008/06/27 13:27:04 danielk1977 Exp $
*/
#include "sqliteInt.h"

/*
** This version of the memory allocator is used only when 
** SQLITE_POW2_MEMORY_SIZE is defined.
*/
................................................................................
** Log2 of the minimum size of an allocation.  For example, if
** 4 then all allocations will be rounded up to at least 16 bytes.
** If 5 then all allocations will be rounded up to at least 32 bytes.
*/
#ifndef SQLITE_POW2_LOGMIN
# define SQLITE_POW2_LOGMIN 6
#endif


/*
** Log2 of the maximum size of an allocation.
*/
#ifndef SQLITE_POW2_LOGMAX
# define SQLITE_POW2_LOGMAX 18
#endif
................................................................................
#define NSIZE (SQLITE_POW2_LOGMAX - SQLITE_POW2_LOGMIN + 1)

/*
** 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.
*/
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, this is not really a practical
** limitation.
*/

#define LOGMAX 30

/*
** Masks used for mem5.aCtrl[] elements.
*/
#define CTRL_LOGSIZE  0x1f    /* Log2 Size of this block relative to POW2_MIN */
#define CTRL_FREE     0x20    /* True if not checked out */

................................................................................
  u32 maxOut;         /* Maximum instantaneous currentOut */
  u32 maxCount;       /* Maximum instantaneous currentCount */
  u32 maxRequest;     /* Largest allocation (exclusive of internal frag) */
  
  /*
  ** Lists of free blocks of various sizes.
  */
  int aiFreelist[LOGMAX+1];

  /*
  ** Space for tracking which blocks are checked out and the size
  ** of each block.  One byte per block.
  */
  u8 *aCtrl;

  /*
  ** Memory available for allocation
  */
  int nAtom;       /* Smallest possible allocation in bytes */
  int nBlock;      /* Number of nAtom sized blocks in zPool */
  u8 *zPool;
} mem5;

#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){
  int next, prev;
  assert( i>=0 && i<mem5.nBlock );
  assert( iLogsize>=0 && iLogsize<=LOGMAX );
  assert( (mem5.aCtrl[i] & CTRL_LOGSIZE)==iLogsize );

  next = MEM5LINK(i)->next;
  prev = MEM5LINK(i)->prev;
  if( prev<0 ){
    mem5.aiFreelist[iLogsize] = next;
  }else{
    MEM5LINK(prev)->next = next;
  }
  if( next>=0 ){
    MEM5LINK(next)->prev = prev;
  }
}

/*
** Link the chunk at mem5.aPool[i] so that is on the iLogsize
** free list.
*/
static void memsys5Link(int i, int iLogsize){
  int x;
  assert( sqlite3_mutex_held(mem5.mutex) );
  assert( i>=0 && i<mem5.nBlock );
  assert( iLogsize>=0 && iLogsize<=LOGMAX );
  assert( (mem5.aCtrl[i] & CTRL_LOGSIZE)==iLogsize );

  x = MEM5LINK(i)->next = mem5.aiFreelist[iLogsize];
  MEM5LINK(i)->prev = -1;
  if( x>=0 ){
    assert( x<mem5.nBlock );
    MEM5LINK(x)->prev = i;
  }
  mem5.aiFreelist[iLogsize] = i;
}

/*
** If the STATIC_MEM mutex is not already held, obtain it now. The mutex
** will already be held (obtained by code in malloc.c) if
................................................................................
** 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.nAtom;
    assert( i>=0 && i<mem5.nBlock );
    iSize = mem5.nAtom * (1 << (mem5.aCtrl[i]&CTRL_LOGSIZE));
  }
  return iSize;
}

/*
** Find the first entry on the freelist iLogsize.  Unlink that
** entry and return its index. 
*/
static int memsys5UnlinkFirst(int iLogsize){
  int i;
  int iFirst;

  assert( iLogsize>=0 && iLogsize<=LOGMAX );
  i = iFirst = mem5.aiFreelist[iLogsize];
  assert( iFirst>=0 );
  while( i>0 ){
    if( i<iFirst ) iFirst = i;
    i = MEM5LINK(i)->next;
  }
  memsys5Unlink(iFirst, iLogsize);
  return iFirst;
}

/*
** Return a block of memory of at least nBytes in size.
................................................................................
  ** requests are counted */
  if( nByte>mem5.maxRequest ){
    mem5.maxRequest = nByte;
  }

  /* Round nByte up to the next valid power of two */
  if( nByte>POW2_MAX ) return 0;
  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.
  */
  for(iBin=iLogsize; mem5.aiFreelist[iBin]<0 && iBin<=LOGMAX; iBin++){}
  if( iBin>LOGMAX ) return 0;
  i = memsys5UnlinkFirst(iBin);
  while( iBin>iLogsize ){
    int newSize;

    iBin--;
    newSize = 1 << iBin;
    mem5.aCtrl[i+newSize] = CTRL_FREE | iBin;
................................................................................
  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.nAtom];
}

/*
** 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. */
  assert( iBlock>=0 && iBlock<mem5.nBlock );
  assert( ((u8 *)pOld-mem5.zPool)%mem5.nAtom==0 );
  assert( (mem5.aCtrl[iBlock] & CTRL_FREE)==0 );

  iLogsize = mem5.aCtrl[iBlock] & CTRL_LOGSIZE;
  size = 1<<iLogsize;
  assert( iBlock+size-1<mem5.nBlock );

  mem5.aCtrl[iBlock] |= CTRL_FREE;
  mem5.aCtrl[iBlock+size-1] |= CTRL_FREE;
  assert( mem5.currentCount>0 );
  assert( mem5.currentOut>=0 );
  mem5.currentCount--;
  mem5.currentOut -= size*mem5.nAtom;
  assert( mem5.currentOut>0 || mem5.currentCount==0 );
  assert( mem5.currentCount>0 || mem5.currentOut==0 );

  mem5.aCtrl[iBlock] = CTRL_FREE | iLogsize;
  while( iLogsize<LOGMAX ){
    int iBuddy;

    if( (iBlock>>iLogsize) & 1 ){
      iBuddy = iBlock - size;
    }else{
      iBuddy = iBlock + size;
    }
    assert( iBuddy>=0 );
    if( (iBuddy+(1<<iLogsize))>mem5.nBlock ) break;
    if( mem5.aCtrl[iBuddy]!=(CTRL_FREE | iLogsize) ) break;
    memsys5Unlink(iBuddy, iLogsize);
    iLogsize++;
    if( iBuddy<iBlock ){
      mem5.aCtrl[iBuddy] = CTRL_FREE | iLogsize;
      mem5.aCtrl[iBlock] = 0;
      iBlock = iBuddy;
    }else{
      mem5.aCtrl[iBlock] = CTRL_FREE | iLogsize;
      mem5.aCtrl[iBuddy] = 0;
    }
    size *= 2;
  }
  memsys5Link(iBlock, iLogsize);
}

/*
** Allocate nBytes of memory
*/
static void *memsys5Malloc(int nBytes){
  sqlite3_int64 *p = 0;
................................................................................
}

/*
** Free memory.
*/
static void memsys5Free(void *pPrior){
  if( pPrior==0 ){
assert(0);
    return;
  }
  memsys5Enter();
  memsys5FreeUnsafe(pPrior);
  memsys5Leave();  
}

................................................................................
}

/*
** Round up a request size to the next valid allocation size.
*/
static int memsys5Roundup(int n){
  int iFullSz;
  for(iFullSz=mem5.nAtom; iFullSz<n; iFullSz *= 2);
  return iFullSz;
}

static int memsys5Log(int iValue){
  int iLog;
  for(iLog=0; (1<<iLog)<iValue; iLog++);
  return iLog;
}

/*
** Initialize this module.
*/
static int memsys5Init(void *NotUsed){
  int ii;
  int nByte = sqlite3Config.nHeap;
  u8 *zByte = (u8 *)sqlite3Config.pHeap;
  int nMinLog;                 /* Log of minimum allocation size in bytes*/
  int iOffset;

  nMinLog = memsys5Log(sqlite3Config.mnReq);
  mem5.nAtom = (1<<nMinLog);
  while( sizeof(Mem5Link)>mem5.nAtom ){
    mem5.nAtom = mem5.nAtom << 1;
  }

  mem5.nBlock = (nByte / (mem5.nAtom+sizeof(u8)));
  mem5.zPool = zByte;
  mem5.aCtrl = (u8 *)&mem5.zPool[mem5.nBlock*mem5.nAtom];

  for(ii=0; ii<=LOGMAX; ii++){
    mem5.aiFreelist[ii] = -1;
  }

  iOffset = 0;
  for(ii=LOGMAX; ii>=0; ii--){
    int nAlloc = (1<<ii);
    if( (iOffset+nAlloc)<=mem5.nBlock ){
      mem5.aCtrl[iOffset] = ii | CTRL_FREE;
      memsys5Link(iOffset, ii);
      iOffset += nAlloc;
    }
    assert((iOffset+nAlloc)>mem5.nBlock);
  }

  return SQLITE_OK;
}

/*
** Deinitialize this module.
*/
static void memsys5Shutdown(void *NotUsed){
................................................................................
** Open the file indicated and write a log of all unfreed memory 
** allocations into that log.
*/
void sqlite3Memsys5Dump(const char *zFilename){
#ifdef SQLITE_DEBUG
  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.nAtom);
  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.nAtom << 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);
................................................................................
    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){
  static const sqlite3_mem_methods memsys5Methods = {
     memsys5Malloc,
     memsys5Free,
     memsys5Realloc,
     memsys5Size,
     memsys5Roundup,
     memsys5Init,
     memsys5Shutdown,
     0
  };


















  return &memsys5Methods;
}

#endif /* SQLITE_ENABLE_MEMSYS5 */

Changes to src/sqliteInt.h.

7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
....
1803
1804
1805
1806
1807
1808
1809
1810
1811
1812
1813
1814
1815
1816
1817
**    May you do good and not evil.
**    May you find forgiveness for yourself and forgive others.
**    May you share freely, never taking more than you give.
**
*************************************************************************
** Internal interface definitions for SQLite.
**
** @(#) $Id: sqliteInt.h,v 1.732 2008/06/26 18:04:03 danielk1977 Exp $
*/
#ifndef _SQLITEINT_H_
#define _SQLITEINT_H_

/*
** Include the configuration header output by 'configure' if we're using the
** autoconf-based build
................................................................................
int sqlite3MallocSize(void *);
void *sqlite3ScratchMalloc(int);
void sqlite3ScratchFree(void*);
void *sqlite3PageMalloc(int);
void sqlite3PageFree(void*);
void sqlite3MemSetDefault(void);
void sqlite3MemSetMemsys3(u8 *pBlock, int nBlock);
void sqlite3MemSetMemsys5(u8 *pBlock, int nBlock);
void sqlite3BenignMallocHooks(void (*)(void), void (*)(void));

#ifndef SQLITE_MUTEX_NOOP
  sqlite3_mutex_methods *sqlite3DefaultMutex(void);
  sqlite3_mutex *sqlite3MutexAlloc(int);
  int sqlite3MutexInit(void);
  int sqlite3MutexEnd(void);







|







 







|







7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
....
1803
1804
1805
1806
1807
1808
1809
1810
1811
1812
1813
1814
1815
1816
1817
**    May you do good and not evil.
**    May you find forgiveness for yourself and forgive others.
**    May you share freely, never taking more than you give.
**
*************************************************************************
** Internal interface definitions for SQLite.
**
** @(#) $Id: sqliteInt.h,v 1.733 2008/06/27 13:27:04 danielk1977 Exp $
*/
#ifndef _SQLITEINT_H_
#define _SQLITEINT_H_

/*
** Include the configuration header output by 'configure' if we're using the
** autoconf-based build
................................................................................
int sqlite3MallocSize(void *);
void *sqlite3ScratchMalloc(int);
void sqlite3ScratchFree(void*);
void *sqlite3PageMalloc(int);
void sqlite3PageFree(void*);
void sqlite3MemSetDefault(void);
void sqlite3MemSetMemsys3(u8 *pBlock, int nBlock);
const sqlite3_mem_methods *sqlite3MemGetMemsys5(void);
void sqlite3BenignMallocHooks(void (*)(void), void (*)(void));

#ifndef SQLITE_MUTEX_NOOP
  sqlite3_mutex_methods *sqlite3DefaultMutex(void);
  sqlite3_mutex *sqlite3MutexAlloc(int);
  int sqlite3MutexInit(void);
  int sqlite3MutexEnd(void);

Changes to src/test_malloc.c.

9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
...
959
960
961
962
963
964
965









































966
967
968
969
970
971
972
....
1102
1103
1104
1105
1106
1107
1108

1109
1110
1111
1112
1113
1114
1115
1116
1117
1118
1119
**    May you share freely, never taking more than you give.
**
*************************************************************************
**
** This file contains code used to implement test interfaces to the
** memory allocation subsystem.
**
** $Id: test_malloc.c,v 1.31 2008/06/25 14:26:09 danielk1977 Exp $
*/
#include "sqliteInt.h"
#include "tcl.h"
#include <stdlib.h>
#include <string.h>
#include <assert.h>

................................................................................
      sz = sizeof(buf);
    }
    rc = sqlite3_config((int)clientData, buf, sz);
  }
  Tcl_SetResult(interp, (char *)sqlite3TestErrorName(rc), TCL_VOLATILE);
  return TCL_OK;
}










































/*
** Usage:    
**
**   sqlite3_dump_memsys3  FILENAME
**   sqlite3_dump_memsys5  FILENAME
**
................................................................................
     { "sqlite3_memdebug_log",       test_memdebug_log             ,0. },
     { "sqlite3_config_scratch",     test_config_scratch           ,0. },
     { "sqlite3_config_pagecache",   test_config_pagecache         ,0. },
     { "sqlite3_status",             test_status                   ,0. },
     { "install_malloc_faultsim",    test_install_malloc_faultsim  ,0. },
     { "sqlite3_config_memsys3", test_config_memsys3, SQLITE_CONFIG_MEMSYS3 },
     { "sqlite3_config_memsys5", test_config_memsys3, SQLITE_CONFIG_MEMSYS5 },

     { "sqlite3_dump_memsys3",   test_dump_memsys3  , SQLITE_CONFIG_MEMSYS3 },
     { "sqlite3_dump_memsys5",   test_dump_memsys3  , SQLITE_CONFIG_MEMSYS5 }
  };
  int i;
  for(i=0; i<sizeof(aObjCmd)/sizeof(aObjCmd[0]); i++){
    ClientData c = (ClientData)aObjCmd[i].clientData;
    Tcl_CreateObjCommand(interp, aObjCmd[i].zName, aObjCmd[i].xProc, c, 0);
  }
  return TCL_OK;
}
#endif







|







 







>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>







 







>











9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
...
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
1001
1002
1003
1004
1005
1006
1007
1008
1009
1010
1011
1012
1013
....
1143
1144
1145
1146
1147
1148
1149
1150
1151
1152
1153
1154
1155
1156
1157
1158
1159
1160
1161
**    May you share freely, never taking more than you give.
**
*************************************************************************
**
** This file contains code used to implement test interfaces to the
** memory allocation subsystem.
**
** $Id: test_malloc.c,v 1.32 2008/06/27 13:27:04 danielk1977 Exp $
*/
#include "sqliteInt.h"
#include "tcl.h"
#include <stdlib.h>
#include <string.h>
#include <assert.h>

................................................................................
      sz = sizeof(buf);
    }
    rc = sqlite3_config((int)clientData, buf, sz);
  }
  Tcl_SetResult(interp, (char *)sqlite3TestErrorName(rc), TCL_VOLATILE);
  return TCL_OK;
}

/*
** Usage:
**
**   sqlite3_config_heap ?-memsys3? NBYTE NMINALLOC
*/
static int test_config_heap(
  void * clientData, 
  Tcl_Interp *interp,
  int objc,
  Tcl_Obj *CONST objv[]
){
  static char zBuf[1048576];
  int nByte;         /* Size of buffer to pass to sqlite3_config() */
  int nMinAlloc;     /* Size of minimum allocation */
  int rc;            /* Return code of sqlite3_config() */
  int isMemsys3 = 0; /* True if the -memsys3 switch is present */

  Tcl_Obj * CONST *aArg = &objv[1];
  int nArg = objc-1;

  if( nArg>0 && 0==strcmp("-memsys3", Tcl_GetString(aArg[0])) ){
    nArg--;
    aArg++;
    isMemsys3 = 1;
  }
  if( nArg!=2 ){
    Tcl_WrongNumArgs(interp, 1, objv, "?-memsys3? NBYTE NMINALLOC");
    return TCL_ERROR;
  }
  if( Tcl_GetIntFromObj(interp, aArg[0], &nByte) ) return TCL_ERROR;
  if( Tcl_GetIntFromObj(interp, aArg[1], &nMinAlloc) ) return TCL_ERROR;

  if( nByte>sizeof(zBuf) ){
    nByte = sizeof(zBuf);
  }
  rc = sqlite3_config(SQLITE_CONFIG_HEAP, zBuf, nByte, nMinAlloc);

  Tcl_SetResult(interp, (char *)sqlite3TestErrorName(rc), TCL_VOLATILE);
  return TCL_OK;
}

/*
** Usage:    
**
**   sqlite3_dump_memsys3  FILENAME
**   sqlite3_dump_memsys5  FILENAME
**
................................................................................
     { "sqlite3_memdebug_log",       test_memdebug_log             ,0. },
     { "sqlite3_config_scratch",     test_config_scratch           ,0. },
     { "sqlite3_config_pagecache",   test_config_pagecache         ,0. },
     { "sqlite3_status",             test_status                   ,0. },
     { "install_malloc_faultsim",    test_install_malloc_faultsim  ,0. },
     { "sqlite3_config_memsys3", test_config_memsys3, SQLITE_CONFIG_MEMSYS3 },
     { "sqlite3_config_memsys5", test_config_memsys3, SQLITE_CONFIG_MEMSYS5 },
     { "sqlite3_config_heap",        test_config_heap,              0 },
     { "sqlite3_dump_memsys3",   test_dump_memsys3  , SQLITE_CONFIG_MEMSYS3 },
     { "sqlite3_dump_memsys5",   test_dump_memsys3  , SQLITE_CONFIG_MEMSYS5 }
  };
  int i;
  for(i=0; i<sizeof(aObjCmd)/sizeof(aObjCmd[0]); i++){
    ClientData c = (ClientData)aObjCmd[i].clientData;
    Tcl_CreateObjCommand(interp, aObjCmd[i].zName, aObjCmd[i].xProc, c, 0);
  }
  return TCL_OK;
}
#endif

Changes to test/permutations.test.

5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
...
363
364
365
366
367
368
369








370












371
372
373
374
375
376
377
#
#    May you do good and not evil.
#    May you find forgiveness for yourself and forgive others.
#    May you share freely, never taking more than you give.
#
#***********************************************************************
#
# $Id: permutations.test,v 1.7 2008/06/25 14:57:54 danielk1977 Exp $

set testdir [file dirname $argv0]
source $testdir/tester.tcl

# Argument processing.
#
set ::testmode [lindex $argv 0]
................................................................................
    collate5.test  delete3.test index2.test     ioerr.test  join3.test 
    pagesize.test  bitvec.test  capi3.test      memsubsys1.test  limit.test
    memdb.test     capi3c.test  func.test
  } -initialize {
    catch {db close}
    sqlite3_reset_auto_extension
    sqlite3_shutdown








    sqlite3_config_memsys5 1000000












    install_malloc_faultsim 1 
    sqlite3_initialize
    autoinstall_test_functions
  } -shutdown {
    catch {db close}
    sqlite3_reset_auto_extension
    sqlite3_shutdown







|







 







>
>
>
>
>
>
>
>
|
>
>
>
>
>
>
>
>
>
>
>
>







5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
...
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
#
#    May you do good and not evil.
#    May you find forgiveness for yourself and forgive others.
#    May you share freely, never taking more than you give.
#
#***********************************************************************
#
# $Id: permutations.test,v 1.8 2008/06/27 13:27:04 danielk1977 Exp $

set testdir [file dirname $argv0]
source $testdir/tester.tcl

# Argument processing.
#
set ::testmode [lindex $argv 0]
................................................................................
    collate5.test  delete3.test index2.test     ioerr.test  join3.test 
    pagesize.test  bitvec.test  capi3.test      memsubsys1.test  limit.test
    memdb.test     capi3c.test  func.test
  } -initialize {
    catch {db close}
    sqlite3_reset_auto_extension
    sqlite3_shutdown
    sqlite3_config_heap 1000000 64
    install_malloc_faultsim 1 
    sqlite3_initialize
    autoinstall_test_functions
  } -shutdown {
    catch {db close}
    sqlite3_reset_auto_extension
    sqlite3_shutdown
    sqlite3_config_memsys5 0
    install_malloc_faultsim 1 
    sqlite3_initialize
  }

  run_tests "memsys5-2" -description {
    Run tests using the allocator in mem5.c in a different configuration.
  } -include { select1.test 
  } -initialize {
    catch {db close}
    sqlite3_reset_auto_extension
    sqlite3_shutdown
    sqlite3_config_heap 250000 16
    install_malloc_faultsim 1 
    sqlite3_initialize
    autoinstall_test_functions
  } -shutdown {
    catch {db close}
    sqlite3_reset_auto_extension
    sqlite3_shutdown