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

Overview
Comment:Add extra tests and fixes. Make the block size and page size configurable.
Downloads: Tarball | ZIP archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1: b43e752c983ecd40b594c7451193e8e48113e899
User & Date: dan 2014-02-05 19:10:53.603
Context
2014-02-05
20:05
Fix a buffer overrun occuring when many overflow pages are recycled by a merge operation. check-in: 28340557fc user: dan tags: trunk
19:10
Add extra tests and fixes. Make the block size and page size configurable. check-in: b43e752c98 user: dan tags: trunk
2014-02-04
19:40
Fix a couple of other bugs. check-in: 822a5aad62 user: dan tags: trunk
Changes
Unified Diff Ignore Whitespace Patch
Changes to lsm-test/lsmtest.h.
94
95
96
97
98
99
100

101
102
103
104
105
106
107
int test_lsm_mt3(const char*, const char *zFile, int bClear, TestDb **ppDb);

int tdb_lsm_configure(lsm_db *, const char *);

/* Functions in lsmtest_tdb4.c */
int test_bt_open(const char*, const char *zFile, int bClear, TestDb **ppDb);
int test_fbt_open(const char*, const char *zFile, int bClear, TestDb **ppDb);



/* Functions in testutil.c. */
int  testPrngInit(void);
u32  testPrngValue(u32 iVal);
void testPrngArray(u32 iVal, u32 *aOut, int nOut);
void testPrngString(u32 iVal, char *aOut, int nOut);







>







94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
int test_lsm_mt3(const char*, const char *zFile, int bClear, TestDb **ppDb);

int tdb_lsm_configure(lsm_db *, const char *);

/* Functions in lsmtest_tdb4.c */
int test_bt_open(const char*, const char *zFile, int bClear, TestDb **ppDb);
int test_fbt_open(const char*, const char *zFile, int bClear, TestDb **ppDb);
int test_fbts_open(const char*, const char *zFile, int bClear, TestDb **ppDb);


/* Functions in testutil.c. */
int  testPrngInit(void);
u32  testPrngValue(u32 iVal);
void testPrngArray(u32 iVal, u32 *aOut, int nOut);
void testPrngString(u32 iVal, char *aOut, int nOut);
Changes to lsm-test/lsmtest1.c.
237
238
239
240
241
242
243





























244
245
246
247
248
249
250
    fflush(stdout);
    iDot++;
  }
  *piDot = iDot;
}

int testCaseNDot(void){ return 20; }






























#if 0
static void printScanCb(
    void *pCtx, void *pKey, int nKey, void *pVal, int nVal
){
  printf("%s\n", (char *)pKey);
  fflush(stdout);







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







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
    fflush(stdout);
    iDot++;
  }
  *piDot = iDot;
}

int testCaseNDot(void){ return 20; }

/*
** If argument "db" is actually a bt database, check if there are any
** leaked pages or blocks. Output an error message and raise an exception 
** if there are.
**
** If "db" is not a bt database, this function is a no-op.
*/
void testCaseDbLeaks(TestDb *db, int *pRc){
  if( *pRc==SQLITE4_OK ){
    bt_db *pBt = tdb_bt(db);
    if( pBt ){
      int rc;
      bt_info i;
      i.eType = BT_INFO_PAGE_LEAKS;
      i.pgno = 0;
      sqlite4_buffer_init(&i.output, 0);

      rc = sqlite4BtControl(pBt, BT_CONTROL_INFO, (void*)&i);
      if( rc==SQLITE4_OK && (*(char*)i.output.p)!='\0' ){
        rc = 1;
        testPrintError("Page leaks: %s\n", (char*)i.output.p);
      }
      sqlite4_buffer_clear(&i.output);
      *pRc = rc;
      if( rc ) test_failed();
    }
  }
}

#if 0
static void printScanCb(
    void *pCtx, void *pKey, int nKey, void *pVal, int nVal
){
  printf("%s\n", (char *)pKey);
  fflush(stdout);
303
304
305
306
307
308
309



310
311
312
313
314
315
316

    /* Check that the db content is still correct. */
    testDbContents(pDb, pData, p->nRow, i, p->nRow-1,p->nTest,p->bTestScan,&rc);

    /* Update the progress dots... */
    testCaseProgress(i, p->nRow, testCaseNDot()/2, &iDot);
  }




  /* Free the datasource, close the database and finish the test case. */
  testDatasourceFree(pData);
  tdb_close(pDb);
  testCaseFinish(rc);
  *pRc = rc;
}







>
>
>







332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348

    /* Check that the db content is still correct. */
    testDbContents(pDb, pData, p->nRow, i, p->nRow-1,p->nTest,p->bTestScan,&rc);

    /* Update the progress dots... */
    testCaseProgress(i, p->nRow, testCaseNDot()/2, &iDot);
  }

  /* Check that no pages or blocks were leaked (bt only) */
  testCaseDbLeaks(pDb, &rc);

  /* Free the datasource, close the database and finish the test case. */
  testDatasourceFree(pData);
  tdb_close(pDb);
  testCaseFinish(rc);
  *pRc = rc;
}
Changes to lsm-test/lsmtest_tdb.c.
707
708
709
710
711
712
713

714
715
716
717
718
719
720
static struct Lib {
  const char *zName;
  const char *zDefaultDb;
  int (*xOpen)(const char *, const char *zFilename, int bClear, TestDb **ppDb);
} aLib[] = {
  { "bt",           "testdb.bt",        test_bt_open },
  { "fbt",          "testdb.fbt",       test_fbt_open },

  { "sqlite3",      "testdb.sqlite",    sql_open },
  { "lsm_small",    "testdb.lsm_small", test_lsm_small_open },
  { "lsm_lomem",    "testdb.lsm_lomem", test_lsm_lomem_open },
#ifdef HAVE_ZLIB
  { "lsm_zip",      "testdb.lsm_zip",   test_lsm_zip_open },
#endif
  { "lsm",          "testdb.lsm",       test_lsm_open },







>







707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
static struct Lib {
  const char *zName;
  const char *zDefaultDb;
  int (*xOpen)(const char *, const char *zFilename, int bClear, TestDb **ppDb);
} aLib[] = {
  { "bt",           "testdb.bt",        test_bt_open },
  { "fbt",          "testdb.fbt",       test_fbt_open },
  { "fbts",         "testdb.fbts",      test_fbts_open },
  { "sqlite3",      "testdb.sqlite",    sql_open },
  { "lsm_small",    "testdb.lsm_small", test_lsm_small_open },
  { "lsm_lomem",    "testdb.lsm_lomem", test_lsm_lomem_open },
#ifdef HAVE_ZLIB
  { "lsm_zip",      "testdb.lsm_zip",   test_lsm_zip_open },
#endif
  { "lsm",          "testdb.lsm",       test_lsm_open },
Changes to lsm-test/lsmtest_tdb.h.
11
12
13
14
15
16
17

18
19
20
21
22
23
24
#define __WRAPPER_H_

#ifdef __cplusplus
extern "C" {
#endif

#include "lsm.h"


typedef struct TestDb TestDb;

/*
** Open a new database connection. The first argument is the name of the
** database library to use. e.g. something like:
**







>







11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#define __WRAPPER_H_

#ifdef __cplusplus
extern "C" {
#endif

#include "lsm.h"
#include "bt.h"

typedef struct TestDb TestDb;

/*
** Open a new database connection. The first argument is the name of the
** database library to use. e.g. something like:
**
159
160
161
162
163
164
165

166
167
168
169
170
171
172
173
174
175
176
177
void tdb_lsm_config_work_hook(TestDb *pDb, void (*)(lsm_db *, void *), void *);
void tdb_lsm_write_hook(TestDb *, void(*)(void*,int,lsm_i64,int,int), void*);
int tdb_lsm_config_str(TestDb *pDb, const char *zStr);

/*************************************************************************
** Start of bt specific things. From lsmtest_tdb4.c.
*/


/*
** Simulate a system crash during the iSync'th call to xSync(). Passing
** iSync==1 means crash the next time xSync is called.
*/
void tdb_bt_prepare_sync_crash(TestDb *pDb, int iSync);

#ifdef __cplusplus
}  /* End of the 'extern "C"' block */
#endif

#endif







>












160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
void tdb_lsm_config_work_hook(TestDb *pDb, void (*)(lsm_db *, void *), void *);
void tdb_lsm_write_hook(TestDb *, void(*)(void*,int,lsm_i64,int,int), void*);
int tdb_lsm_config_str(TestDb *pDb, const char *zStr);

/*************************************************************************
** Start of bt specific things. From lsmtest_tdb4.c.
*/
bt_db *tdb_bt(TestDb *pDb);

/*
** Simulate a system crash during the iSync'th call to xSync(). Passing
** iSync==1 means crash the next time xSync is called.
*/
void tdb_bt_prepare_sync_crash(TestDb *pDb, int iSync);

#ifdef __cplusplus
}  /* End of the 'extern "C"' block */
#endif

#endif
Changes to lsm-test/lsmtest_tdb4.c.
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641


642
643
644
645
646
647
648
  const char *p = z;

  while( *p>='0' && *p<='9' ){
    i = i*10 + (*p - '0');
    p++;
  }
  if( *p=='K' || *p=='k' ){
    i = i * 1000;
    p++;
  }else if( *p=='M' || *p=='m' ){
    i = i * 1000000;
    p++;
  }

  if( *p ) return SQLITE4_ERROR;
  *piVal = i;
  return SQLITE4_OK;
}

static int testBtConfigure(BtDb *pDb, const char *zCfg, int *pbMt){
  int rc = SQLITE4_OK;

  if( zCfg ){
    struct CfgParam {
      const char *zParam;
      int eParam;
    } aParam[] = {
      { "safety",         BT_CONTROL_SAFETY },
      { "autockpt",       BT_CONTROL_AUTOCKPT },
      { "multiproc",      BT_CONTROL_MULTIPROC },


      { "mt",             -1 },
      { "fastinsert",     -2 },
      { 0, 0 }
    };
    const char *z = zCfg;
    int n = strlen(z);
    char *aSpace;







|


|



















>
>







612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
  const char *p = z;

  while( *p>='0' && *p<='9' ){
    i = i*10 + (*p - '0');
    p++;
  }
  if( *p=='K' || *p=='k' ){
    i = i * 1024;
    p++;
  }else if( *p=='M' || *p=='m' ){
    i = i * 1024 * 1024;
    p++;
  }

  if( *p ) return SQLITE4_ERROR;
  *piVal = i;
  return SQLITE4_OK;
}

static int testBtConfigure(BtDb *pDb, const char *zCfg, int *pbMt){
  int rc = SQLITE4_OK;

  if( zCfg ){
    struct CfgParam {
      const char *zParam;
      int eParam;
    } aParam[] = {
      { "safety",         BT_CONTROL_SAFETY },
      { "autockpt",       BT_CONTROL_AUTOCKPT },
      { "multiproc",      BT_CONTROL_MULTIPROC },
      { "blksz",          BT_CONTROL_BLKSZ },
      { "pagesz",         BT_CONTROL_PAGESZ },
      { "mt",             -1 },
      { "fastinsert",     -2 },
      { 0, 0 }
    };
    const char *z = zCfg;
    int n = strlen(z);
    char *aSpace;
762
763
764
765
766
767
768










769
770
771
772
773
774
775







776
777
778
779
780
781
782
  const char *zSpec, 
  const char *zFilename, 
  int bClear, 
  TestDb **ppDb
){
  return test_bt_open("fast=1", zFilename, bClear, ppDb);
}











void tdb_bt_prepare_sync_crash(TestDb *pTestDb, int iSync){
  BtDb *p = (BtDb*)pTestDb;
  assert( pTestDb->pMethods->xClose==bt_close );
  assert( p->bCrash==0 );
  p->nCrashSync = iSync;
}








/*************************************************************************
** Beginning of code for background checkpointer.
*/

struct bt_ckpter {
  sqlite4_buffer file;            /* File name */







>
>
>
>
>
>
>
>
>
>







>
>
>
>
>
>
>







764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
  const char *zSpec, 
  const char *zFilename, 
  int bClear, 
  TestDb **ppDb
){
  return test_bt_open("fast=1", zFilename, bClear, ppDb);
}

int test_fbts_open(
  const char *zSpec, 
  const char *zFilename, 
  int bClear, 
  TestDb **ppDb
){
  return test_bt_open("fast=1 blksz=32K pagesz=512", zFilename, bClear, ppDb);
}


void tdb_bt_prepare_sync_crash(TestDb *pTestDb, int iSync){
  BtDb *p = (BtDb*)pTestDb;
  assert( pTestDb->pMethods->xClose==bt_close );
  assert( p->bCrash==0 );
  p->nCrashSync = iSync;
}

bt_db *tdb_bt(TestDb *pDb){
  if( pDb->pMethods->xClose==bt_close ){
    return ((BtDb *)pDb)->pBt;
  }
  return 0;
}

/*************************************************************************
** Beginning of code for background checkpointer.
*/

struct bt_ckpter {
  sqlite4_buffer file;            /* File name */
Changes to src/bt.h.
1
2
3
4
5
6
7
8
9
10
11
12
13



14
15
16
17
18
19
20
/*
** 2013 September 14
**
** The author disclaims copyright to this source code.  In place of
** a legal notice, here is a blessing:
**
**    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.
**
*************************************************************************
**
*/




#include <sqlite4.h>

typedef struct bt_db bt_db;
typedef struct bt_cursor bt_cursor;

/* 













>
>
>







1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/*
** 2013 September 14
**
** The author disclaims copyright to this source code.  In place of
** a legal notice, here is a blessing:
**
**    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.
**
*************************************************************************
**
*/

#ifndef __BT_H
#define __BT_H

#include <sqlite4.h>

typedef struct bt_db bt_db;
typedef struct bt_cursor bt_cursor;

/* 
181
182
183
184
185
186
187


188
189
190
191
192
193
194
#define BT_CONTROL_SAFETY         7706392
#define BT_CONTROL_AUTOCKPT       7706393
#define BT_CONTROL_LOGSIZE        7706394
#define BT_CONTROL_MULTIPROC      7706395
#define BT_CONTROL_LOGSIZECB      7706396
#define BT_CONTROL_CHECKPOINT     7706397
#define BT_CONTROL_FAST_INSERT_OP 7706498



int sqlite4BtControl(bt_db*, int op, void *pArg);

#define BT_SAFETY_OFF    0
#define BT_SAFETY_NORMAL 1
#define BT_SAFETY_FULL   2








>
>







184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
#define BT_CONTROL_SAFETY         7706392
#define BT_CONTROL_AUTOCKPT       7706393
#define BT_CONTROL_LOGSIZE        7706394
#define BT_CONTROL_MULTIPROC      7706395
#define BT_CONTROL_LOGSIZECB      7706396
#define BT_CONTROL_CHECKPOINT     7706397
#define BT_CONTROL_FAST_INSERT_OP 7706498
#define BT_CONTROL_BLKSZ          7706499
#define BT_CONTROL_PAGESZ         7706500

int sqlite4BtControl(bt_db*, int op, void *pArg);

#define BT_SAFETY_OFF    0
#define BT_SAFETY_NORMAL 1
#define BT_SAFETY_FULL   2

251
252
253
254
255
256
257

258
** Flags for xOpen
*/
#define BT_OPEN_DATABASE   0x0001
#define BT_OPEN_LOG        0x0002
#define BT_OPEN_SHARED     0x0004
#define BT_OPEN_READONLY   0x0008










>

256
257
258
259
260
261
262
263
264
** Flags for xOpen
*/
#define BT_OPEN_DATABASE   0x0001
#define BT_OPEN_LOG        0x0002
#define BT_OPEN_SHARED     0x0004
#define BT_OPEN_READONLY   0x0008

#endif /* ifndef __BT_H */

Changes to src/btInt.h.
322
323
324
325
326
327
328


329
330
331
332
333
334
335
  **
  ** iSafetyLevel:
  **   Current safety level. 0==off, 1==normal, 2=full.
  */
  int iSafetyLevel;               /* 0==OFF, 1==NORMAL, 2==FULL */
  int nAutoCkpt;                  /* Auto-checkpoint when log is this large */
  int bRequestMultiProc;          /* Request multi-proc support */



  /* These are used only by the bt_lock module. */
  BtShared *pShared;              /* Shared by all handles on this file */
  BtLock *pNext;                  /* Next connection using pShared */
  u32 mExclLock;                  /* Mask of exclusive locks held */
  u32 mSharedLock;                /* Mask of shared locks held */
  BtFile *pBtFile;                /* Used to defer close if necessary */







>
>







322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
  **
  ** iSafetyLevel:
  **   Current safety level. 0==off, 1==normal, 2=full.
  */
  int iSafetyLevel;               /* 0==OFF, 1==NORMAL, 2==FULL */
  int nAutoCkpt;                  /* Auto-checkpoint when log is this large */
  int bRequestMultiProc;          /* Request multi-proc support */
  int nBlksz;                     /* Requested block-size in bytes */
  int nPgsz;                      /* Requested page-size in bytes */

  /* These are used only by the bt_lock module. */
  BtShared *pShared;              /* Shared by all handles on this file */
  BtLock *pNext;                  /* Next connection using pShared */
  u32 mExclLock;                  /* Mask of exclusive locks held */
  u32 mSharedLock;                /* Mask of shared locks held */
  BtFile *pBtFile;                /* Used to defer close if necessary */
Changes to src/bt_log.c.
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
  if( aData ){
    memcpy(&hdr, aData, sizeof(BtDbHdrCksum));
    btLogChecksum32(1, (u8*)&hdr, offsetof(BtDbHdrCksum, aCksum), 0, aCksum);
  }

  if( aData==0 || aCksum[0]!=hdr.aCksum[0] || aCksum[1]!=hdr.aCksum[1] ){
    memset(&hdr, 0, sizeof(BtDbHdrCksum));
    hdr.hdr.pgsz = BT_DEFAULT_PGSZ;
    hdr.hdr.blksz = BT_DEFAULT_BLKSZ;
    hdr.hdr.nPg = 2;
    hdr.hdr.iRoot = 2;
  }

  memcpy(pHdr, &hdr, sizeof(BtDbHdr));
}








|
|







882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
  if( aData ){
    memcpy(&hdr, aData, sizeof(BtDbHdrCksum));
    btLogChecksum32(1, (u8*)&hdr, offsetof(BtDbHdrCksum, aCksum), 0, aCksum);
  }

  if( aData==0 || aCksum[0]!=hdr.aCksum[0] || aCksum[1]!=hdr.aCksum[1] ){
    memset(&hdr, 0, sizeof(BtDbHdrCksum));
    hdr.hdr.pgsz = pLog->pLock->nPgsz;
    hdr.hdr.blksz = pLog->pLock->nBlksz;
    hdr.hdr.nPg = 2;
    hdr.hdr.iRoot = 2;
  }

  memcpy(pHdr, &hdr, sizeof(BtDbHdr));
}

Changes to src/bt_main.c.
43
44
45
46
47
48
49



50
51
52
53
54
55
56
  BtPager *pPager;                /* Underlying page-based database */
  bt_cursor *pAllCsr;             /* List of all open cursors */
  int nMinMerge;
  int nScheduleAlloc;
  int bFastInsertOp;              /* Set by CONTROL_FAST_INSERT_OP */
};




typedef struct BtOvfl BtOvfl;
struct BtOvfl {
  int nKey;
  int nVal;
  sqlite4_buffer buf;
};








>
>
>







43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
  BtPager *pPager;                /* Underlying page-based database */
  bt_cursor *pAllCsr;             /* List of all open cursors */
  int nMinMerge;
  int nScheduleAlloc;
  int bFastInsertOp;              /* Set by CONTROL_FAST_INSERT_OP */
};

/*
** Overflow buffer is valid if nKey!=0.
*/
typedef struct BtOvfl BtOvfl;
struct BtOvfl {
  int nKey;
  int nVal;
  sqlite4_buffer buf;
};

354
355
356
357
358
359
360

361
362
363
364
365
366
367
  btCsrReleaseAll(pCsr);
  if( bFreeBuffer ){
    sqlite4_buffer_clear(&pCsr->ovfl.buf);
  }
  pCsr->bSkipNext = 0;
  pCsr->bSkipPrev = 0;
  pCsr->bRequireReseek = 0;

}

static void fiCsrReset(FiCursor *pCsr){
  int i;
  bt_db *db = pCsr->base.pDb;
  for(i=0; i<pCsr->nBt; i++){
    btCsrReset(&pCsr->aSub[i].csr, 1);







>







357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
  btCsrReleaseAll(pCsr);
  if( bFreeBuffer ){
    sqlite4_buffer_clear(&pCsr->ovfl.buf);
  }
  pCsr->bSkipNext = 0;
  pCsr->bSkipPrev = 0;
  pCsr->bRequireReseek = 0;
  pCsr->ovfl.nKey = 0;
}

static void fiCsrReset(FiCursor *pCsr){
  int i;
  bt_db *db = pCsr->base.pDb;
  for(i=0; i<pCsr->nBt; i++){
    btCsrReset(&pCsr->aSub[i].csr, 1);
1041
1042
1043
1044
1045
1046
1047
1048
1049
1050
1051
1052
1053
1054
1055
1056
1057
1058
1059
1060
1061
1062
1063
1064
1065
1066
1067
1068
1069
1070
1071
1072
1073
1074
1075
1076
1077


1078
1079
1080
1081
1082
1083
1084
1085
      int iLo;                    /* pK/nK is > than cell (iLo-1) */
      int res;                    /* Result of comparison */
      u8 *aData = (u8*)sqlite4BtPageData(pCsr->apPage[pCsr->nPg-1]);
      int bLeaf = ((btFlags(aData) & BT_PGFLAGS_INTERNAL)==0);

      iLo = 0;
      iHi = nCell = btCellCount(aData, pgsz);
      if( nCell==0 ){
        rc = SQLITE4_NOTFOUND;
        break;
      }

      while( iHi>iLo ){
        int iTst = (iHi+iLo)/2;   /* Cell to compare to pK/nK */
        pCsr->aiCell[pCsr->nPg-1] = iTst;
        rc = btCellKeyCompare(pCsr, bLeaf, aPrefix, pK, nK, &res);
        if( rc!=SQLITE4_OK || res==0 ){
          /* Cell iTst is EQUAL to pK/nK */
          iHi = iLo = iTst;
        }else if( res<0 ){
          /* Cell iTst is SMALLER than pK/nK */
          iLo = iTst+1;
        }else{
          /* Cell iTst is LARGER than pK/nK */
          iHi = iTst;
        }
      }
      if( rc!=SQLITE4_OK ) break;
      assert( iHi==iLo );

      iHi += (bLeaf==0 && res==0);
      pCsr->aiCell[pCsr->nPg-1] = iHi;
      if( bLeaf==0 ){
        pgno = btChildPgno(aData, pgsz, iHi);
      }else{
        pgno = 0;



        if( res!=0 ){
          if( eSeek==BT_SEEK_EQ ){
            if( eCsrseek==BT_CSRSEEK_RESEEK ){
              rc = SQLITE4_OK;
              if( iHi==nCell ){
                assert( pCsr->aiCell[pCsr->nPg-1]>0 );
                pCsr->aiCell[pCsr->nPg-1]--;
                pCsr->bSkipPrev = 1;







<
<
<
<



















|






>
>
|







1045
1046
1047
1048
1049
1050
1051




1052
1053
1054
1055
1056
1057
1058
1059
1060
1061
1062
1063
1064
1065
1066
1067
1068
1069
1070
1071
1072
1073
1074
1075
1076
1077
1078
1079
1080
1081
1082
1083
1084
1085
1086
1087
      int iLo;                    /* pK/nK is > than cell (iLo-1) */
      int res;                    /* Result of comparison */
      u8 *aData = (u8*)sqlite4BtPageData(pCsr->apPage[pCsr->nPg-1]);
      int bLeaf = ((btFlags(aData) & BT_PGFLAGS_INTERNAL)==0);

      iLo = 0;
      iHi = nCell = btCellCount(aData, pgsz);





      while( iHi>iLo ){
        int iTst = (iHi+iLo)/2;   /* Cell to compare to pK/nK */
        pCsr->aiCell[pCsr->nPg-1] = iTst;
        rc = btCellKeyCompare(pCsr, bLeaf, aPrefix, pK, nK, &res);
        if( rc!=SQLITE4_OK || res==0 ){
          /* Cell iTst is EQUAL to pK/nK */
          iHi = iLo = iTst;
        }else if( res<0 ){
          /* Cell iTst is SMALLER than pK/nK */
          iLo = iTst+1;
        }else{
          /* Cell iTst is LARGER than pK/nK */
          iHi = iTst;
        }
      }
      if( rc!=SQLITE4_OK ) break;
      assert( iHi==iLo );

      iHi += (nCell>0 && bLeaf==0 && res==0);
      pCsr->aiCell[pCsr->nPg-1] = iHi;
      if( bLeaf==0 ){
        pgno = btChildPgno(aData, pgsz, iHi);
      }else{
        pgno = 0;

        if( nCell==0 ){
          rc = SQLITE4_NOTFOUND;
        }else if( res!=0 ){
          if( eSeek==BT_SEEK_EQ ){
            if( eCsrseek==BT_CSRSEEK_RESEEK ){
              rc = SQLITE4_OK;
              if( iHi==nCell ){
                assert( pCsr->aiCell[pCsr->nPg-1]>0 );
                pCsr->aiCell[pCsr->nPg-1]--;
                pCsr->bSkipPrev = 1;
1142
1143
1144
1145
1146
1147
1148

1149
1150
1151
1152
1153
1154
1155
** bNext is true) and Pref() (if bNext is false).
*/
static int btCsrStep(BtCursor *pCsr, int bNext){
  const int pgsz = sqlite4BtPagerPagesize(pCsr->base.pDb->pPager);
  int rc = SQLITE4_OK;
  int bRequireDescent = 0;


  rc = btCsrReseek(pCsr);
  if( rc==SQLITE4_OK && pCsr->nPg==0 ){
    rc = SQLITE4_NOTFOUND;
  }

  if( (pCsr->bSkipNext && bNext) || (pCsr->bSkipPrev && bNext==0) ){
    pCsr->bSkipPrev = pCsr->bSkipNext = 0;







>







1144
1145
1146
1147
1148
1149
1150
1151
1152
1153
1154
1155
1156
1157
1158
** bNext is true) and Pref() (if bNext is false).
*/
static int btCsrStep(BtCursor *pCsr, int bNext){
  const int pgsz = sqlite4BtPagerPagesize(pCsr->base.pDb->pPager);
  int rc = SQLITE4_OK;
  int bRequireDescent = 0;

  pCsr->ovfl.nKey = 0;
  rc = btCsrReseek(pCsr);
  if( rc==SQLITE4_OK && pCsr->nPg==0 ){
    rc = SQLITE4_NOTFOUND;
  }

  if( (pCsr->bSkipNext && bNext) || (pCsr->bSkipPrev && bNext==0) ){
    pCsr->bSkipPrev = pCsr->bSkipNext = 0;
1231
1232
1233
1234
1235
1236
1237




1238
1239
1240
1241

1242
1243
1244
1245
1246
1247
1248
1249
1250
1251
1252
    if( rc==SQLITE4_OK ){
      int nCell;                  /* Number of cells on this page */
      int nByte;
      u8 *pCell;
      u8 *aData = (u8*)sqlite4BtPageData(pCsr->apPage[pCsr->nPg-1]);

      nCell = btCellCount(aData, pgsz);




      if( nCell==0 ){
        btCsrReset(pCsr, 0);
        return SQLITE4_NOTFOUND;
      }


      /* If the cursor has descended to a leaf break out of the loop. */
      pCsr->aiCell[pCsr->nPg-1] = (bLast ? nCell : 0);
      if( (aData[0] & BT_PGFLAGS_INTERNAL)==0 ) break;
      
      /* Otherwise, set pgno to the left or rightmost child of the page
      ** just loaded, depending on whether the cursor is seeking to the
      ** start or end of the tree.  */
      if( bLast==0 ){
        pCell = btCellFind(aData, pgsz, 0);
        pCell += sqlite4BtVarintGet32(pCell, &nByte);







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







1234
1235
1236
1237
1238
1239
1240
1241
1242
1243
1244
1245
1246
1247
1248
1249
1250



1251
1252
1253
1254
1255
1256
1257
    if( rc==SQLITE4_OK ){
      int nCell;                  /* Number of cells on this page */
      int nByte;
      u8 *pCell;
      u8 *aData = (u8*)sqlite4BtPageData(pCsr->apPage[pCsr->nPg-1]);

      nCell = btCellCount(aData, pgsz);
      pCsr->aiCell[pCsr->nPg-1] = (bLast ? nCell : 0);

      /* If the cursor has descended to a leaf break out of the loop. */
      if( (aData[0] & BT_PGFLAGS_INTERNAL)==0 ){
        if( nCell==0 ){
          btCsrReset(pCsr, 0);
          rc = SQLITE4_NOTFOUND;
        }
        break;
      }



      
      /* Otherwise, set pgno to the left or rightmost child of the page
      ** just loaded, depending on whether the cursor is seeking to the
      ** start or end of the tree.  */
      if( bLast==0 ){
        pCell = btCellFind(aData, pgsz, 0);
        pCell += sqlite4BtVarintGet32(pCell, &nByte);
1452
1453
1454
1455
1456
1457
1458
1459
1460


1461
1462
1463
1464
1465
1466
1467
1468
1469
1470
1471
1472
1473
1474
1475
1476
1477
1478
1479
1480
1481
1482
1483
1484
1485
1486
1487
1488
1489
1490
1491
1492
1493
1494
1495
1496
1497
1498
1499
1500
1501
1502
1503
1504
1505
1506
1507
1508
1509
1510
1511
1512
1513
1514
1515
1516
1517
1518
1519
1520
1521

1522
1523
1524
1525
1526
1527
1528


/*
** Buffer the key and value belonging to the current cursor position
** in pCsr->ovfl.
*/
static int btCsrBuffer(BtCursor *pCsr, int bVal){
  const int pgsz = sqlite4BtPagerPagesize(pCsr->base.pDb->pPager);
  int rc = SQLITE4_OK;            /* Return code */


  u8 *aData;                      /* Page data */
  u8 *pCell;                      /* Pointer to cell within aData[] */
  int nReq;                       /* Total required space */
  u8 *aOut;                       /* Output buffer */
  u8 *pKLocal = 0;                /* Pointer to local part of key */
  u8 *pVLocal = 0;                /* Pointer to local part of value (if any) */
  int nKLocal = 0;                /* Bytes of key on page */
  int nVLocal = 0;                /* Bytes of value on page */
  int nKOvfl = 0;                 /* Bytes of key on overflow pages */
  int nVOvfl = 0;                 /* Bytes of value on overflow pages */

  aData = (u8*)sqlite4BtPageData(pCsr->apPage[pCsr->nPg-1]);
  pCell = btCellFind(aData, pgsz, pCsr->aiCell[pCsr->nPg-1]);
  pCell += sqlite4BtVarintGet32(pCell, &nKLocal);
  if( nKLocal==0 ){
    /* Type (c) leaf cell. */
    pCell += sqlite4BtVarintGet32(pCell, &nKLocal);
    pKLocal = pCell;
    pCell += nKLocal;
    pCell += sqlite4BtVarintGet32(pCell, &nKOvfl);
    pCell += sqlite4BtVarintGet32(pCell, &nVOvfl);
    if( nVOvfl>0 ) nVOvfl -= 1;

  }else{
    pKLocal = pCell;
    pCell += nKLocal;
    pCell += sqlite4BtVarintGet32(pCell, &nVLocal);
    if( nVLocal==0 ){
      /* Type (b) */
      pCell += sqlite4BtVarintGet32(pCell, &nVLocal);
      pVLocal = pCell;
      pCell += nVLocal;
      pCell += sqlite4BtVarintGet32(pCell, &nVOvfl);
    }else{
      /* Type (a) */
      pVLocal = pCell;
      nVLocal -= 2;
    }
  }

  /* A delete-key */
  if( nVLocal<0 ) nVLocal = 0;

  pCsr->ovfl.nKey = nKLocal + nKOvfl;
  pCsr->ovfl.nVal = nVLocal + nVOvfl;

  nReq = pCsr->ovfl.nKey + pCsr->ovfl.nVal;
  assert( nReq>0 );
  rc = sqlite4_buffer_resize(&pCsr->ovfl.buf, nReq);
  if( rc!=SQLITE4_OK ) return rc;

  /* Copy in local data */
  aOut = (u8*)pCsr->ovfl.buf.p;
  memcpy(aOut, pKLocal, nKLocal);
  memcpy(&aOut[nKLocal], pVLocal, nVLocal);

  /* Load in overflow data */
  if( nKOvfl || nVOvfl ){
    rc = btOverflowArrayRead(
        pCsr->base.pDb, pCell, &aOut[nKLocal + nVLocal], nKOvfl + nVOvfl
    );

  }

  return rc;
}


static int btCsrKey(BtCursor *pCsr, const void **ppK, int *pnK){







<

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

|
|
|
|
|
|
|
|
|
|
|

|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|

|
|

|
|

|
|
|
|

|
|
|
|

|
|
|
|
|
>







1457
1458
1459
1460
1461
1462
1463

1464
1465
1466
1467
1468
1469
1470
1471
1472
1473
1474
1475
1476
1477
1478
1479
1480
1481
1482
1483
1484
1485
1486
1487
1488
1489
1490
1491
1492
1493
1494
1495
1496
1497
1498
1499
1500
1501
1502
1503
1504
1505
1506
1507
1508
1509
1510
1511
1512
1513
1514
1515
1516
1517
1518
1519
1520
1521
1522
1523
1524
1525
1526
1527
1528
1529
1530
1531
1532
1533
1534
1535


/*
** Buffer the key and value belonging to the current cursor position
** in pCsr->ovfl.
*/
static int btCsrBuffer(BtCursor *pCsr, int bVal){

  int rc = SQLITE4_OK;            /* Return code */
  if( pCsr->ovfl.nKey<=0 ){
    const int pgsz = sqlite4BtPagerPagesize(pCsr->base.pDb->pPager);
    u8 *aData;                      /* Page data */
    u8 *pCell;                      /* Pointer to cell within aData[] */
    int nReq;                       /* Total required space */
    u8 *aOut;                       /* Output buffer */
    u8 *pKLocal = 0;                /* Pointer to local part of key */
    u8 *pVLocal = 0;                /* Pointer to local part of value, if any */
    int nKLocal = 0;                /* Bytes of key on page */
    int nVLocal = 0;                /* Bytes of value on page */
    int nKOvfl = 0;                 /* Bytes of key on overflow pages */
    int nVOvfl = 0;                 /* Bytes of value on overflow pages */

    aData = (u8*)sqlite4BtPageData(pCsr->apPage[pCsr->nPg-1]);
    pCell = btCellFind(aData, pgsz, pCsr->aiCell[pCsr->nPg-1]);
    pCell += sqlite4BtVarintGet32(pCell, &nKLocal);
    if( nKLocal==0 ){
      /* Type (c) leaf cell. */
      pCell += sqlite4BtVarintGet32(pCell, &nKLocal);
      pKLocal = pCell;
      pCell += nKLocal;
      pCell += sqlite4BtVarintGet32(pCell, &nKOvfl);
      pCell += sqlite4BtVarintGet32(pCell, &nVOvfl);
      if( nVOvfl>0 ) nVOvfl -= 1;

    }else{
      pKLocal = pCell;
      pCell += nKLocal;
      pCell += sqlite4BtVarintGet32(pCell, &nVLocal);
      if( nVLocal==0 ){
        /* Type (b) */
        pCell += sqlite4BtVarintGet32(pCell, &nVLocal);
        pVLocal = pCell;
        pCell += nVLocal;
        pCell += sqlite4BtVarintGet32(pCell, &nVOvfl);
      }else{
        /* Type (a) */
        pVLocal = pCell;
        nVLocal -= 2;
      }
    }

    /* A delete-key */
    if( nVLocal<0 ) nVLocal = 0;

    pCsr->ovfl.nKey = nKLocal + nKOvfl;
    pCsr->ovfl.nVal = nVLocal + nVOvfl;

    nReq = pCsr->ovfl.nKey + pCsr->ovfl.nVal;
    assert( nReq>0 );
    rc = sqlite4_buffer_resize(&pCsr->ovfl.buf, nReq);
    if( rc!=SQLITE4_OK ) return rc;

    /* Copy in local data */
    aOut = (u8*)pCsr->ovfl.buf.p;
    memcpy(aOut, pKLocal, nKLocal);
    memcpy(&aOut[nKLocal], pVLocal, nVLocal);

    /* Load in overflow data */
    if( nKOvfl || nVOvfl ){
      rc = btOverflowArrayRead(
          pCsr->base.pDb, pCell, &aOut[nKLocal + nVLocal], nKOvfl + nVOvfl
          );
    }
  }

  return rc;
}


static int btCsrKey(BtCursor *pCsr, const void **ppK, int *pnK){
5185
5186
5187
5188
5189
5190
5191













5192
5193
5194
5195
5196
5197
5198
      break;
    }

    case BT_CONTROL_FAST_INSERT_OP: {
      db->bFastInsertOp = 1;
      break;
    }













  }

  return rc;
}

#ifndef NDEBUG








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







5192
5193
5194
5195
5196
5197
5198
5199
5200
5201
5202
5203
5204
5205
5206
5207
5208
5209
5210
5211
5212
5213
5214
5215
5216
5217
5218
      break;
    }

    case BT_CONTROL_FAST_INSERT_OP: {
      db->bFastInsertOp = 1;
      break;
    }

    case BT_CONTROL_BLKSZ: {
      int *pInt = (int*)pArg;
      ((BtLock*)db->pPager)->nBlksz = *pInt;
      break;
    }

    case BT_CONTROL_PAGESZ: {
      int *pInt = (int*)pArg;
      ((BtLock*)db->pPager)->nPgsz = *pInt;
      break;
    }

  }

  return rc;
}

#ifndef NDEBUG

5217
5218
5219
5220
5221
5222
5223

5224
5225
5226
5227
5228
5229
5230
5231
5232
5233
5234
5235

5236








5237
5238
5239
5240
5241
5242
5243
5244

5245
5246
5247
5248
5249
5250
5251
5252
5253
5254
5255
5256
5257
5258
/*
** Iterate through the b-tree with root page iRoot. For each page used
** by the b-tree, set the corresponding entry in the aUsed[] array.
*/
static void assert_pages_used(
  bt_db *db,                      /* Database handle */
  u32 iRoot,                      /* Root page of b-tree to iterate through */

  int *pRc                        /* IN/OUT: Error code */
){
  if( *pRc==SQLITE4_OK && iRoot ){
    BtDbHdr *pHdr = sqlite4BtPagerDbhdr(db->pPager);
    int nPgPerBlk = (pHdr->blksz / pHdr->pgsz);
    int bMeta = (iRoot==pHdr->iMRoot);
    BtLock *pLock = (BtLock*)(db->pPager);
    u8 *aUsed = pLock->aUsed;
    int rc;
    BtCursor csr;

    btCsrSetup(db, iRoot, &csr);

    rc = btCsrEnd(&csr, 0);








    while( rc==SQLITE4_OK ){
      rc = btCsrBuffer(&csr, 1);
      if( bMeta && rc==SQLITE4_OK ){
        u8 *aVal;
        int nVal;

        btCsrKey(&csr, (const void**)&aVal, &nVal);
        if( nVal!=sizeof(aSummaryKey) || memcmp(aVal, aSummaryKey, nVal) ){

          u32 iSubRoot;
          u32 iBlk;
          int i;
          btCsrData(&csr, 0, 4, (const void**)&aVal, &nVal);
          iSubRoot = btGetU32(aVal);
          iBlk = (iSubRoot / nPgPerBlk) + 1;
          assert_pages_used(db, iSubRoot, &rc);
          markBlockAsUsed(db, iBlk, aUsed);
        }
      }
      if( rc==SQLITE4_OK ) rc = btCsrStep(&csr, 1);
    }
  }
}







>












>
|
>
>
>
>
>
>
>
>



|
<

|
|
>






|







5237
5238
5239
5240
5241
5242
5243
5244
5245
5246
5247
5248
5249
5250
5251
5252
5253
5254
5255
5256
5257
5258
5259
5260
5261
5262
5263
5264
5265
5266
5267
5268
5269
5270

5271
5272
5273
5274
5275
5276
5277
5278
5279
5280
5281
5282
5283
5284
5285
5286
5287
5288
/*
** Iterate through the b-tree with root page iRoot. For each page used
** by the b-tree, set the corresponding entry in the aUsed[] array.
*/
static void assert_pages_used(
  bt_db *db,                      /* Database handle */
  u32 iRoot,                      /* Root page of b-tree to iterate through */
  const void *pFirst, int nFirst, /* Starting with this key (if pFirst!=0) */
  int *pRc                        /* IN/OUT: Error code */
){
  if( *pRc==SQLITE4_OK && iRoot ){
    BtDbHdr *pHdr = sqlite4BtPagerDbhdr(db->pPager);
    int nPgPerBlk = (pHdr->blksz / pHdr->pgsz);
    int bMeta = (iRoot==pHdr->iMRoot);
    BtLock *pLock = (BtLock*)(db->pPager);
    u8 *aUsed = pLock->aUsed;
    int rc;
    BtCursor csr;

    btCsrSetup(db, iRoot, &csr);
    if( nFirst==0 ){
      rc = btCsrEnd(&csr, 0);
    }else{
      pLock->aUsed = 0;
      rc = btCsrSeek(&csr, 0, pFirst, nFirst, BT_SEEK_GE, BT_CSRSEEK_SEEK);
      if( rc==SQLITE4_INEXACT ) rc = SQLITE4_OK;
      pLock->aUsed = aUsed;
      csr.ovfl.nKey = 0;
    }

    while( rc==SQLITE4_OK ){
      rc = btCsrBuffer(&csr, 1);
      if( bMeta && rc==SQLITE4_OK ){
        u8 *aKey; int nKey;


        btCsrKey(&csr, (const void**)&aKey, &nKey);
        if( nKey!=sizeof(aSummaryKey) || memcmp(aKey, aSummaryKey, nKey) ){
          u8 *aVal; int nVal;
          u32 iSubRoot;
          u32 iBlk;
          int i;
          btCsrData(&csr, 0, 4, (const void**)&aVal, &nVal);
          iSubRoot = btGetU32(aVal);
          iBlk = (iSubRoot / nPgPerBlk) + 1;
          assert_pages_used(db, iSubRoot, &aKey[8], nKey-8, &rc);
          markBlockAsUsed(db, iBlk, aUsed);
        }
      }
      if( rc==SQLITE4_OK ) rc = btCsrStep(&csr, 1);
    }
  }
}
5351
5352
5353
5354
5355
5356
5357
5358
5359
5360
5361
5362
5363
5364
5365
5366
5367
5368
      aUsed[0] = 1;                 /* Page 1 is always in use */
      pLock->aUsed = &aUsed[-1];

      /* The scheduled-merge page, if it is allocated */
      assert_schedule_page_used(db, pLock->aUsed, &rc);

      /* Walk the main b-tree */
      assert_pages_used(db, pHdr->iRoot, &rc);

      /* Walk the meta-tree */
      assert_pages_used(db, pHdr->iMRoot, &rc);

      /* Walk the free-page list */
      assert_freelist_pages_used(db, 0, pLock->aUsed, &rc);

      /* The free-block list */
      assert_freelist_pages_used(db, 1, pLock->aUsed, &rc);








|


|







5381
5382
5383
5384
5385
5386
5387
5388
5389
5390
5391
5392
5393
5394
5395
5396
5397
5398
      aUsed[0] = 1;                 /* Page 1 is always in use */
      pLock->aUsed = &aUsed[-1];

      /* The scheduled-merge page, if it is allocated */
      assert_schedule_page_used(db, pLock->aUsed, &rc);

      /* Walk the main b-tree */
      assert_pages_used(db, pHdr->iRoot, 0, 0, &rc);

      /* Walk the meta-tree */
      assert_pages_used(db, pHdr->iMRoot, 0, 0, &rc);

      /* Walk the free-page list */
      assert_freelist_pages_used(db, 0, pLock->aUsed, &rc);

      /* The free-block list */
      assert_freelist_pages_used(db, 1, pLock->aUsed, &rc);

Changes to src/bt_pager.c.
220
221
222
223
224
225
226


227
228
229
230
231
232
233
  memset(p, 0, nByte);

  p->btl.pEnv = pEnv;
  p->btl.pVfs = sqlite4BtEnvDefault();
  p->btl.iSafetyLevel = BT_DEFAULT_SAFETY;
  p->btl.nAutoCkpt = BT_DEFAULT_AUTOCKPT;
  p->btl.bRequestMultiProc = BT_DEFAULT_MULTIPROC;


  *pp = p;
  return SQLITE4_OK;
}

static void btFreePage(BtPager *p, BtPage *pPg){
  if( pPg ){
    sqlite4_free(p->btl.pEnv, pPg->aData);







>
>







220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
  memset(p, 0, nByte);

  p->btl.pEnv = pEnv;
  p->btl.pVfs = sqlite4BtEnvDefault();
  p->btl.iSafetyLevel = BT_DEFAULT_SAFETY;
  p->btl.nAutoCkpt = BT_DEFAULT_AUTOCKPT;
  p->btl.bRequestMultiProc = BT_DEFAULT_MULTIPROC;
  p->btl.nBlksz = BT_DEFAULT_BLKSZ;
  p->btl.nPgsz = BT_DEFAULT_PGSZ;
  *pp = p;
  return SQLITE4_OK;
}

static void btFreePage(BtPager *p, BtPage *pPg){
  if( pPg ){
    sqlite4_free(p->btl.pEnv, pPg->aData);