/ Check-in [7d2cdfad]
Login

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

Overview
Comment:Use a heap-based primary queue rather than a linked list to store the available free blocks of each size in MEMSYS5, since this provides faster access to the first available block.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | memsys5-performance
Files: files | file ages | folders
SHA1:7d2cdfad0e95f8c5b5f7e0abe3b7c0d1fa9f5b83
User & Date: drh 2013-11-23 21:30:22
Context
2013-11-23
21:30
Use a heap-based primary queue rather than a linked list to store the available free blocks of each size in MEMSYS5, since this provides faster access to the first available block. Closed-Leaf check-in: 7d2cdfad user: drh tags: memsys5-performance
21:29
Add newlines at the end of some error messages in speedtest1. check-in: 6b98f0af user: drh tags: trunk
Changes
Hide Diffs Unified Diffs Ignore Whitespace Patch

Changes to src/mem5.c.

59
60
61
62
63
64
65















66
67
68
69
70


71
72
73
74
75
76
77
..
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
...
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
185
186
187
188
189
...
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
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
...
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
...
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
...
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
...
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
...
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
/*
** A minimum allocation is an instance of the following structure.
** Larger allocations are an array of these structures where the
** size of the array is a power of 2.
**
** The size of this object must be a power of two.  That fact is
** verified in memsys5Init().















*/
typedef struct Mem5Link Mem5Link;
struct Mem5Link {
  int next;       /* Index of next free chunk */
  int prev;       /* Index of previous free chunk */


};

/*
** Maximum size of any allocation is ((1<<LOGMAX)*mem5.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 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;

................................................................................
*/
#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 link.
*/
#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;



  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
** sqlite3GlobalConfig.bMemStat is true.
*/
................................................................................
** 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. 
*/
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.
** Return NULL if unable.  Return NULL if nBytes==0.
**
** The caller guarantees that nByte is positive.
**
** The caller has obtained a mutex prior to invoking this
** routine so there is never any chance that two or more
** threads can be in this routine at the same time.
*/
static void *memsys5MallocUnsafe(int nByte){
  int i;           /* Index of a mem5.aPool[] slot */
  int iBin;        /* Index into mem5.aiFreelist[] */
  int iFullSz;     /* Size of allocation rounded up to power of 2 */
  int iLogsize;    /* Log2 of iFullSz/POW2_MIN */

  /* nByte must be a positive */
  assert( nByte>0 );

  /* Keep track of the maximum allocation request.  Even unfulfilled
................................................................................
  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 ){
    testcase( sqlite3GlobalConfig.xLog!=0 );
    sqlite3_log(SQLITE_NOMEM, "failed to allocate %u bytes", nByte);
    return 0;
  }
  i = memsys5UnlinkFirst(iBin);
  while( iBin>iLogsize ){
................................................................................
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;
................................................................................
  }

  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--){
    int nAlloc = (1<<ii);
    if( (iOffset+nAlloc)<=mem5.nBlock ){
      mem5.aCtrl[iOffset] = ii | CTRL_FREE;
................................................................................
#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 ){
................................................................................
                      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);







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



|
|
>
>







 







|


<
|





<
|



<
|










|
|
|
|
>

>
>
>
|
>
>
>
>
>
>
>







 







|


>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
|
<

|
<
>
>
>
|

|
>

<
<
<
<
<
<
>
>
>
>
>

<
<
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
|
|
>
>
>
>
>
>
>
>
>

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


|

|
>
>
|

|

|
|
<
<
<
<
<
>
>
>
>
>
>
>
>

<
>
>
>
>
>
>







 







|






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












|







 







|



|







 







|







 







|







 







|







 







|
|







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
86
87
88
89
90
91
92
93
94
...
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
149
150
151
152
153
154
...
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
185
186
187
188
189
190
191
192
193
194
195
196
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
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
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
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384





385
386
387
388
389
390
391
392
393

394
395
396
397
398
399
400
401
402
403
404
405
406
...
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
...
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
...
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
...
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
...
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
...
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
/*
** A minimum allocation is an instance of the following structure.
** Larger allocations are an array of these structures where the
** size of the array is a power of 2.
**
** The size of this object must be a power of two.  That fact is
** verified in memsys5Init().
**
** This object overlays the memory allocation when the memory is available
** to be allocated.  In other words Mem5Link objects represent memory
** that is available to be allocated.
**
** All Mem5Link objects of the same size are arranged on a dynamic
** heap, with the root being the Mem5Link that has the smallest address.
** The iLeft and iRight Mem5Link objects are children.  The iSlot numbers
** for the left and right child are as follows:
**
**      pLeft->iSlot = pParent->iSlot*2;
**      pRight->iSlot = pParent->iSlot*2 + 1;
**
** The root of the heap always has iSlot==1.  If the heap contains
** N elements, then they cover all slots from 1 through N.
*/
typedef struct Mem5Link Mem5Link;
struct Mem5Link {
  int iLeft;       /* left child in the heap */
  int iRight;      /* right child in the heap */
  int iSlot;       /* Slot in the heap holding this item. */
  int filler;      /* Not used. Needed to round size up to power of two */
};

/*
** 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 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 others 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) */
  
  /* Heaps of free blocks.  aHeap[0].iRoot is the root of a dynamic
  ** min-heap of free blocks of size mem5.szAtom.  aHeap[1].iRoot is
  ** a heap of free blocks of size mem5.szAtom*2.  aHeap[x].iRoot is
  ** free heap of blocks of size mem5.szAtom*(1<<x).  aHeap[x].nLink
  ** the number of free blocks on each heap.
  */
  struct Mem5Heap {
    int iRoot;            /* The root Mem5Link for this heap */
    int nLink;            /* Number of Mem5Link objects on this heap */
  } aHeap[LOGMAX+1];

  /* The memsys5HeapPath() routine finds a sequence of nodes in a heap
  ** going to a particular Mem5Link.  It writes those nodes into the
  ** following array.  The root of the tree is in aPath[0].  The first
  ** child in aPath[1].  And so forth.
  */
  int aPath[29];          /* Path to a node in a heap */

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

................................................................................
*/
#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 link.
*/
#define MEM5_PTR(idx) ((Mem5Link*)(&mem5.zPool[(idx)*mem5.szAtom]))

/*
** Given a pointer to an Mem5Link object, return its index into the
** array of all Mem5Link objects.
*/
#define MEM5_ID(p)    (int)(((u8*)(p)-mem5.zPool)/mem5.szAtom)

#if 0  /* This validation step is too slow for normal use */
/*
** Validate an Mem5Link object to make sure it satisfies all of the
** dynamic heap properties.
*/
static void memsys5Validate(int iLink, int nLink){
  Mem5Link *p = MEM5_PTR(iLink);
  assert( p->iLeft>=0 || p->iRight<0 );
  assert( p->iSlot<=nLink );
  if( p->iLeft>=0 ){
    assert( p->iLeft>iLink );
    assert( p->iLeft!=p->iRight );
    assert( MEM5_PTR(p->iLeft)->iSlot==p->iSlot*2 );
    memsys5Validate(p->iLeft, nLink);
  }else{
    assert( p->iSlot*2>nLink );
  }
  if( p->iRight>=0 ){
    assert( p->iRight>iLink );
    assert( p->iLeft!=p->iRight );
    assert( MEM5_PTR(p->iRight)->iSlot==p->iSlot*2+1 );
    memsys5Validate(p->iRight, nLink);
  }else{
    assert( p->iSlot*2+1>nLink );
  }
}
#else
# define memsys5Validate(X,Y)
#endif

/* 
** Compute a path from the root of a heap to a particular slot of the
** heap.  The root is node iRoot and the desired slot is iSlot.  Write
** the sequence of Mem5Link objects on this path into mem5.aPath[] and
** return the number of elements on the path.
*/
static int memsys5HeapPath(int iRoot, int iSlot){
  int x = 1;
  int i = 0;
  int iRes = iRoot;;

  while( x<=iSlot ) x <<= 1;
  x >>= 2;
  mem5.aPath[0] = iRoot;
  assert( MEM5_PTR(iRoot)->iSlot==1 );
  while( x ){
    Mem5Link *p = MEM5_PTR(iRes);
    iRes = (x & iSlot)!=0 ? p->iRight : p->iLeft;
    mem5.aPath[++i] = iRes;
    x >>= 1;
  }
  assert( MEM5_PTR(mem5.aPath[i])->iSlot==iSlot );
  return i;
}

/* One of the children of heap node iParent will be iOld.  Change
** that child to iNew.
*/
static void memsys5ChangeChild(int iParent, int iOld, int iNew){
  Mem5Link *pParent = MEM5_PTR(iParent);
  if( pParent->iLeft==iOld ){
    pParent->iLeft = iNew;
  }else{
    assert( pParent->iRight==iOld );
    pParent->iRight = iNew;
  }
}

/*
** Swap heap elements mem5.aPath[i] and mem5.aPath[i+1].
*/
static void memsys5HeapPathSwap(int i){
  int iA = mem5.aPath[i];
  int iB = mem5.aPath[i+1];
  Mem5Link *pA = MEM5_PTR(iA);
  Mem5Link *pB = MEM5_PTR(iB);
  int iLeft, iRight, iSlot;

  if( i>0 ) memsys5ChangeChild(mem5.aPath[i-1], iA, iB);
  if( pA->iLeft==iB ){
    iRight = pA->iRight;
    iLeft = iA;
  }else{
    iRight = iA;
    iLeft = pA->iLeft;
  }
  iSlot = pA->iSlot;
  pA->iRight = pB->iRight;
  pA->iLeft = pB->iLeft;
  pA->iSlot = pB->iSlot;
  pB->iRight = iRight;
  pB->iLeft = iLeft;
  pB->iSlot = iSlot;
  mem5.aPath[i] = iB;
  mem5.aPath[i+1] = iA;
}

/*
** If mem5.aPath[i] is greater than either child, then shift
** that element downward in the heap. 
*/
static void memsys5SiftDown(int i){
  while(1){
    int x = mem5.aPath[i];
    Mem5Link *p = MEM5_PTR(x);
    if( p->iRight>=0 && p->iRight<x && p->iRight<p->iLeft ){
      mem5.aPath[i+1] = p->iRight;
    }else if( p->iLeft>=0 && p->iLeft<x ){
      mem5.aPath[i+1] = p->iLeft;
    }else{
      break;
    }
    memsys5HeapPathSwap(i);
    i++; 
  }
}

static void memsys5SiftUp(int i){
  while( i>0 && mem5.aPath[i]<mem5.aPath[i-1] ){
    memsys5HeapPathSwap(i-1);
    i--;
  }
}

/*
** Unlink the chunk at mem5.aPool[i] from iLogsize heap.

*/
static void memsys5Unlink(int iOld, int iLogsize){

  struct Mem5Heap *pHeap;
  Mem5Link *pOld, *pLast;
  int i, iLast;
  assert( iOld>=0 && iOld<mem5.nBlock );
  assert( iLogsize>=0 && iLogsize<=LOGMAX );
  assert( (mem5.aCtrl[iOld] & CTRL_LOGSIZE)==iLogsize );
  assert( mem5.aHeap[iLogsize].nLink>0 );







  pHeap = &mem5.aHeap[iLogsize];
  if( pHeap->nLink==1 ){
    pHeap->nLink = 0;
    pHeap->iRoot = -1;
    return;
  }


  i = memsys5HeapPath(pHeap->iRoot, pHeap->nLink);
  iLast = mem5.aPath[i];
  assert( i>0 );
  memsys5ChangeChild(mem5.aPath[i-1], iLast, -1);
  pHeap->nLink--;
  if( iLast==iOld ) return;
  pOld = MEM5_PTR(iOld);
  pLast = MEM5_PTR(iLast);
  i = memsys5HeapPath(pHeap->iRoot, pOld->iSlot);
  assert( mem5.aPath[i]==iOld );
  pLast->iRight = pOld->iRight;
  pLast->iLeft = pOld->iLeft;
  pLast->iSlot = pOld->iSlot;
  mem5.aPath[i] = iLast;
  if( i>0 ) memsys5ChangeChild(mem5.aPath[i-1], iOld, iLast);
  memsys5SiftUp(i);
  memsys5SiftDown(i);
  pHeap->iRoot = mem5.aPath[0];
  memsys5Validate(pHeap->iRoot, pHeap->nLink);
}

/*
** Find the first entry on the free-heap iLogsize.  Unlink that
** entry and return its index. 
*/
static int memsys5UnlinkFirst(int iLogsize){
  struct Mem5Heap *pHeap;
  int iFirst, i, iLast;
  Mem5Link *pLast;
  Mem5Link *pFirst;

  assert( iLogsize>=0 && iLogsize<=LOGMAX );
  pHeap = &mem5.aHeap[iLogsize];
  assert( pHeap->nLink>0 );
  iFirst = pHeap->iRoot;
  pFirst = MEM5_PTR(iFirst);
  if( pHeap->nLink==1 ){
    pHeap->nLink = 0;
    return iFirst;
  }
  i = memsys5HeapPath(iFirst, pHeap->nLink);
  pHeap->nLink--;
  iLast = mem5.aPath[i];
  assert( i>0 );
  memsys5ChangeChild(mem5.aPath[i-1], iLast, -1);
  pLast = MEM5_PTR(iLast);
  pLast->iSlot = 1;
  pLast->iRight = pFirst->iRight;
  pLast->iLeft = pFirst->iLeft;
  mem5.aPath[0] = iLast;
  memsys5SiftDown(0);
  pHeap->iRoot = mem5.aPath[0];
  memsys5Validate(pHeap->iRoot, pHeap->nLink);
  return iFirst;   
}

/*
** Link the chunk at mem5.aPool[i] so that is on the iLogsize
** free-block heap.
*/
static void memsys5Link(int iNew, int iLogsize){
  struct Mem5Heap *pHeap;
  Mem5Link *pNew;
  int i;
  assert( sqlite3_mutex_held(mem5.mutex) );
  assert( iNew>=0 && iNew<mem5.nBlock );
  assert( iLogsize>=0 && iLogsize<=LOGMAX );
  assert( (mem5.aCtrl[iNew] & CTRL_LOGSIZE)==iLogsize );
  





  pNew = MEM5_PTR(iNew);
  pHeap = &mem5.aHeap[iLogsize];
  pNew->iLeft = -1;
  pNew->iRight = -1;
  pNew->iSlot = ++pHeap->nLink;
  if( pHeap->nLink==1 ){
    pHeap->iRoot = iNew;
    return;
  }

  i = memsys5HeapPath(pHeap->iRoot, pHeap->nLink/2);
  memsys5ChangeChild(mem5.aPath[i], -1, iNew);
  mem5.aPath[i+1] = iNew;
  memsys5SiftUp(i+1);
  pHeap->iRoot = mem5.aPath[0];
  memsys5Validate(pHeap->iRoot, pHeap->nLink);
}

/*
** 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
** sqlite3GlobalConfig.bMemStat is true.
*/
................................................................................
** 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 = MEM5_ID(p);
    assert( i>=0 && i<mem5.nBlock );
    iSize = mem5.szAtom * (1 << (mem5.aCtrl[i]&CTRL_LOGSIZE));
  }
  return iSize;
}




















/*
** Return a block of memory of at least nBytes in size.
** Return NULL if unable.  Return NULL if nBytes==0.
**
** The caller guarantees that nByte is positive.
**
** The caller has obtained a mutex prior to invoking this
** routine so there is never any chance that two or more
** threads can be in this routine at the same time.
*/
static void *memsys5MallocUnsafe(int nByte){
  int i;           /* Index of a mem5.aPool[] slot */
  int iBin;        /* Index into mem5.aHeap[] */
  int iFullSz;     /* Size of allocation rounded up to power of 2 */
  int iLogsize;    /* Log2 of iFullSz/POW2_MIN */

  /* nByte must be a positive */
  assert( nByte>0 );

  /* Keep track of the maximum allocation request.  Even unfulfilled
................................................................................
  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.aHeap[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.aHeap[iBin].nLink==0 && iBin<=LOGMAX; iBin++){}
  if( iBin>LOGMAX ){
    testcase( sqlite3GlobalConfig.xLog!=0 );
    sqlite3_log(SQLITE_NOMEM, "failed to allocate %u bytes", nByte);
    return 0;
  }
  i = memsys5UnlinkFirst(iBin);
  while( iBin>iLogsize ){
................................................................................
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 = MEM5_ID(pOld);

  /* 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;
................................................................................
  }

  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.aHeap[ii].nLink = 0;
  }

  iOffset = 0;
  for(ii=LOGMAX; ii>=0; ii--){
    int nAlloc = (1<<ii);
    if( (iOffset+nAlloc)<=mem5.nBlock ){
      mem5.aCtrl[iOffset] = ii | CTRL_FREE;
................................................................................
#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;
  int nMinLog;

  if( zFilename==0 || zFilename[0]==0 ){
    out = stdout;
  }else{
    out = fopen(zFilename, "w");
    if( out==0 ){
................................................................................
                      zFilename);
      return;
    }
  }
  memsys5Enter();
  nMinLog = memsys5Log(mem5.szAtom);
  for(i=0; i<=LOGMAX && i+nMinLog<32; i++){
    fprintf(out, "freelist items of size %d: %d\n",
            mem5.szAtom << i, mem5.aHeap[i].nLink);
  }
  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);