SQLite4
Check-in [f69b88077c3a7322b1a3ad6e33e0be9c7162aa1a]
Not logged in

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

Overview
SHA1 Hash:f69b88077c3a7322b1a3ad6e33e0be9c7162aa1a
Date: 2013-10-12 19:50:57
User: dan
Comment:Fix page reference leaks in btree code.
Tags And Properties
Changes
Hide Diffs Unified Diffs Ignore Whitespace Patch

Changes to lsm-test/lsmtest_tdb.c

908
909
910
911
912
913
914


















915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933

    sqlite4BtCsrClose(pCsr);
  }

  rc = btRestoreTransaction(p, iLevel, rc);
  return rc;
}



















int bt_open(const char *zFilename, int bClear, TestDb **ppDb){
  static const DatabaseMethods SqlMethods = {
    bt_close,
    bt_write,
    bt_delete,
    bt_delete_range,
    bt_fetch,
    bt_scan,
    0,
    0,
    0
  };
  BtDb *p = 0;
  bt_db *pBt = 0;
  int rc;
  sqlite4_env *pEnv = sqlite4_env_default();

  if( bClear && zFilename && zFilename[0] ){







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









|
|
|







908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951

    sqlite4BtCsrClose(pCsr);
  }

  rc = btRestoreTransaction(p, iLevel, rc);
  return rc;
}

static int bt_begin(TestDb *pTestDb, int iLvl){
  BtDb *p = (BtDb*)pTestDb;
  int rc = sqlite4BtBegin(p->pBt, iLvl);
  return rc;
}

static int bt_commit(TestDb *pTestDb, int iLvl){
  BtDb *p = (BtDb*)pTestDb;
  int rc = sqlite4BtCommit(p->pBt, iLvl);
  return rc;
}

static int bt_rollback(TestDb *pTestDb, int iLvl){
  BtDb *p = (BtDb*)pTestDb;
  int rc = sqlite4BtRollback(p->pBt, iLvl);
  return rc;
}

int bt_open(const char *zFilename, int bClear, TestDb **ppDb){
  static const DatabaseMethods SqlMethods = {
    bt_close,
    bt_write,
    bt_delete,
    bt_delete_range,
    bt_fetch,
    bt_scan,
    bt_begin,
    bt_commit,
    bt_rollback
  };
  BtDb *p = 0;
  bt_db *pBt = 0;
  int rc;
  sqlite4_env *pEnv = sqlite4_env_default();

  if( bClear && zFilename && zFilename[0] ){

Changes to src/btInt.h

81
82
83
84
85
86
87





88
89
90
91
92
93
94

/*
** Query page references.
*/
u32 sqlite4BtPagePgno(BtPage*);
void *sqlite4BtPageData(BtPage*);






/* 
** Read/write the schema cookie value.
*/
int sqlite4BtPagerSetCookie(BtPager*, u32 iVal);
int sqlite4BtPagerGetCookie(BtPager*, u32 *piVal);
/*
** End of bt_pager.c interface.







>
>
>
>
>







81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99

/*
** Query page references.
*/
u32 sqlite4BtPagePgno(BtPage*);
void *sqlite4BtPageData(BtPage*);

/*
** Debugging only. Return number of outstanding page references.
*/
int sqlite4BtPagerRefcount(BtPager*);

/* 
** Read/write the schema cookie value.
*/
int sqlite4BtPagerSetCookie(BtPager*, u32 iVal);
int sqlite4BtPagerGetCookie(BtPager*, u32 *piVal);
/*
** End of bt_pager.c interface.

Changes to src/bt_main.c

25
26
27
28
29
30
31


32
33
34

35
36
37
38
39
40
41
..
43
44
45
46
47
48
49
50
51
52
53
54
55

56
57
58
59
60
61
62
63
64
















65
66
67
68
69
70
71
...
185
186
187
188
189
190
191


192
193
194
195
196
197
198
...
201
202
203
204
205
206
207

208


209
210
211
212
213
214
215
....
1211
1212
1213
1214
1215
1216
1217


1218
1219
1220
1221
1222
1223
1224
....
2114
2115
2116
2117
2118
2119
2120

2121
2122
2123
2124
2125
2126
2127
....
2146
2147
2148
2149
2150
2151
2152

2153
2154
2155
2156
2157

2158
2159
2160
2161

2162
2163
2164
2165
2166
2167
2168
2169
2170
2171
2172
*/
#define BT_PGFLAGS_INTERNAL 0x01  /* True for non-leaf nodes */

#ifndef MIN
# define MIN(a,b) (((a)<(b))?(a):(b))
#endif



struct bt_db {
  sqlite4_env *pEnv;              /* SQLite environment */
  BtPager *pPager;                /* Underlying page-based database */

};

typedef struct BtOvfl BtOvfl;
struct BtOvfl {
  int nKey;
  int nVal;
  u8 *pBuf;
................................................................................
};

/*
** Database cursor handle.
*/
struct bt_cursor {
  bt_db *pDb;                     /* Database that owns this cursor */

  int nPg;                        /* Number of valid entries in apPage[] */
  int aiCell[BT_MAX_DEPTH];       /* Current cell of each apPage[] entry */
  BtPage *apPage[BT_MAX_DEPTH];   /* All pages from root to current leaf */

  BtOvfl ovfl;                    /* Overflow cache (see above) */

};

#ifndef btErrorBkpt
int btErrorBkpt(int rc){
  static int error_cnt = 0;
  error_cnt++;
  return rc;
}
#endif

















/*
** Interpret the first 4 bytes of the buffer indicated by the first 
** parameter as a 32-bit unsigned big-endian integer.
*/
static u32 btGetU32(const u8 *a){
  return ((u32)a[0] << 24) + ((u32)a[1] << 16) + ((u32)a[2] << 8) + ((u32)a[3]);
................................................................................

  nByte = sizeof(bt_cursor) + nExtra;
  *ppCsr = pCsr = (bt_cursor*)sqlite4_malloc(db->pEnv, nByte);
  if( pCsr==0 ){
    rc = btErrorBkpt(SQLITE4_NOMEM);
  }else{
    btCsrSetup(db, pCsr);


  }

  return rc;
}

static void btCsrReset(bt_cursor *pCsr, int bFreeBuffer){
  int i;
................................................................................
  }
  if( bFreeBuffer ) sqlite4_free(pCsr->pDb->pEnv, pCsr->ovfl.pBuf);
  pCsr->nPg = 0;
}

int sqlite4BtCsrClose(bt_cursor *pCsr){
  if( pCsr ){

    btCsrReset(pCsr, 1);


    sqlite4_free(pCsr->pDb->pEnv, pCsr);
  }
  return SQLITE4_OK;
}

void *sqlite4BtCsrExtra(bt_cursor *pCsr){
  return (void*)&pCsr[1];
................................................................................
    pgno = sqlite4BtPagePgno(pPg);

    nCopy1 = MIN(pgsz, nBuf1 - n1);
    nCopy2 = MIN(pgsz - nCopy1, nBuf2 - n2);

    memcpy(aData, &pBuf1[n1], nCopy1); n1 += nCopy1;
    memcpy(&aData[nCopy1], &pBuf2[n2], nCopy2); n2 += nCopy2;



    if( iOvfl<(BT_MAX_DIRECT_OVERFLOW+(nDepth==0)) ){
      btPutU32(&aOut[1 + iOvfl*4], pgno);
      nDirect++;
    }else{
      assert( nDepth>0 );
      for(i=nDepth-1; pgno && i>=0; i--){
................................................................................
/*
** Insert a new key/value pair or replace an existing one.
*/
int sqlite4BtReplace(bt_db *db, const void *pK, int nK, const void *pV, int nV){
  int rc = SQLITE4_OK;
  bt_cursor csr;


  btCsrSetup(db, &csr);
  rc = btCsrSeek(&csr, pK, nK, BT_SEEK_GE, 1);
  if( rc==SQLITE4_OK ){
    /* The cursor currently points to an entry with key pK/nK. This call
    ** should therefore replace that entry. So delete it and then re-seek
    ** the cursor.  */
    rc = sqlite4BtDelete(&csr);
................................................................................
    }
    if( kv.eType==KV_CELL ){
      sqlite4_free(db->pEnv, (void*)kv.pV);
    }
  }
  btCsrReset(&csr, 1);


  return rc;
}

int sqlite4BtDelete(bt_cursor *pCsr){
  int rc;

  rc =  btDeleteFromPage(pCsr, 1);
  if( rc==SQLITE4_OK ){
    rc = btBalanceIfUnderfull(pCsr);
  }

  return rc;
}

int sqlite4BtSetCookie(bt_db *db, unsigned int iVal){
  return sqlite4BtPagerSetCookie(db->pPager, iVal);
}

int sqlite4BtGetCookie(bt_db *db, unsigned int *piVal){
  return sqlite4BtPagerGetCookie(db->pPager, piVal);
}








>
>



>







 







<



<

>









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







 







>
>







 







>

>
>







 







>
>







 







>







 







>





>




>











25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
..
46
47
48
49
50
51
52

53
54
55

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
82
83
84
85
86
87
88
89
...
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
...
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
....
1234
1235
1236
1237
1238
1239
1240
1241
1242
1243
1244
1245
1246
1247
1248
1249
....
2139
2140
2141
2142
2143
2144
2145
2146
2147
2148
2149
2150
2151
2152
2153
....
2172
2173
2174
2175
2176
2177
2178
2179
2180
2181
2182
2183
2184
2185
2186
2187
2188
2189
2190
2191
2192
2193
2194
2195
2196
2197
2198
2199
2200
2201
*/
#define BT_PGFLAGS_INTERNAL 0x01  /* True for non-leaf nodes */

#ifndef MIN
# define MIN(a,b) (((a)<(b))?(a):(b))
#endif

#define BT_EXPENSIVE_ASSERT 0

struct bt_db {
  sqlite4_env *pEnv;              /* SQLite environment */
  BtPager *pPager;                /* Underlying page-based database */
  bt_cursor *pAllCsr;             /* List of all open cursors */
};

typedef struct BtOvfl BtOvfl;
struct BtOvfl {
  int nKey;
  int nVal;
  u8 *pBuf;
................................................................................
};

/*
** Database cursor handle.
*/
struct bt_cursor {
  bt_db *pDb;                     /* Database that owns this cursor */

  int nPg;                        /* Number of valid entries in apPage[] */
  int aiCell[BT_MAX_DEPTH];       /* Current cell of each apPage[] entry */
  BtPage *apPage[BT_MAX_DEPTH];   /* All pages from root to current leaf */

  BtOvfl ovfl;                    /* Overflow cache (see above) */
  bt_cursor *pNextCsr;            /* Next cursor opened by same db handle */
};

#ifndef btErrorBkpt
int btErrorBkpt(int rc){
  static int error_cnt = 0;
  error_cnt++;
  return rc;
}
#endif

#if !defined(NDEBUG) && BT_EXPENSIVE_ASSERT
static void btCheckPageRefs(bt_db *pDb){
  int nActual = 0;
  int nExpect;
  bt_cursor *pCsr;

  nExpect = sqlite4BtPagerRefcount(pDb->pPager);
  for(pCsr=pDb->pAllCsr; pCsr; pCsr=pCsr->pNextCsr){
    if( pCsr->nPg>0 ) nActual += pCsr->nPg;
  }
  assert( nActual==nExpect );
}
#else
# define btCheckPageRefs(x) 
#endif

/*
** Interpret the first 4 bytes of the buffer indicated by the first 
** parameter as a 32-bit unsigned big-endian integer.
*/
static u32 btGetU32(const u8 *a){
  return ((u32)a[0] << 24) + ((u32)a[1] << 16) + ((u32)a[2] << 8) + ((u32)a[3]);
................................................................................

  nByte = sizeof(bt_cursor) + nExtra;
  *ppCsr = pCsr = (bt_cursor*)sqlite4_malloc(db->pEnv, nByte);
  if( pCsr==0 ){
    rc = btErrorBkpt(SQLITE4_NOMEM);
  }else{
    btCsrSetup(db, pCsr);
    pCsr->pNextCsr = db->pAllCsr;
    db->pAllCsr = pCsr;
  }

  return rc;
}

static void btCsrReset(bt_cursor *pCsr, int bFreeBuffer){
  int i;
................................................................................
  }
  if( bFreeBuffer ) sqlite4_free(pCsr->pDb->pEnv, pCsr->ovfl.pBuf);
  pCsr->nPg = 0;
}

int sqlite4BtCsrClose(bt_cursor *pCsr){
  if( pCsr ){
    bt_cursor **pp;
    btCsrReset(pCsr, 1);
    for(pp=&pCsr->pDb->pAllCsr; *pp!=pCsr; pp=&(*pp)->pNextCsr);
    *pp = pCsr->pNextCsr;
    sqlite4_free(pCsr->pDb->pEnv, pCsr);
  }
  return SQLITE4_OK;
}

void *sqlite4BtCsrExtra(bt_cursor *pCsr){
  return (void*)&pCsr[1];
................................................................................
    pgno = sqlite4BtPagePgno(pPg);

    nCopy1 = MIN(pgsz, nBuf1 - n1);
    nCopy2 = MIN(pgsz - nCopy1, nBuf2 - n2);

    memcpy(aData, &pBuf1[n1], nCopy1); n1 += nCopy1;
    memcpy(&aData[nCopy1], &pBuf2[n2], nCopy2); n2 += nCopy2;
    rc = sqlite4BtPageRelease(pPg);
    if( rc!=SQLITE4_OK ) break;

    if( iOvfl<(BT_MAX_DIRECT_OVERFLOW+(nDepth==0)) ){
      btPutU32(&aOut[1 + iOvfl*4], pgno);
      nDirect++;
    }else{
      assert( nDepth>0 );
      for(i=nDepth-1; pgno && i>=0; i--){
................................................................................
/*
** Insert a new key/value pair or replace an existing one.
*/
int sqlite4BtReplace(bt_db *db, const void *pK, int nK, const void *pV, int nV){
  int rc = SQLITE4_OK;
  bt_cursor csr;

  btCheckPageRefs(db);
  btCsrSetup(db, &csr);
  rc = btCsrSeek(&csr, pK, nK, BT_SEEK_GE, 1);
  if( rc==SQLITE4_OK ){
    /* The cursor currently points to an entry with key pK/nK. This call
    ** should therefore replace that entry. So delete it and then re-seek
    ** the cursor.  */
    rc = sqlite4BtDelete(&csr);
................................................................................
    }
    if( kv.eType==KV_CELL ){
      sqlite4_free(db->pEnv, (void*)kv.pV);
    }
  }
  btCsrReset(&csr, 1);

  btCheckPageRefs(db);
  return rc;
}

int sqlite4BtDelete(bt_cursor *pCsr){
  int rc;
  btCheckPageRefs(db);
  rc =  btDeleteFromPage(pCsr, 1);
  if( rc==SQLITE4_OK ){
    rc = btBalanceIfUnderfull(pCsr);
  }
  btCheckPageRefs(db);
  return rc;
}

int sqlite4BtSetCookie(bt_db *db, unsigned int iVal){
  return sqlite4BtPagerSetCookie(db->pPager, iVal);
}

int sqlite4BtGetCookie(bt_db *db, unsigned int *piVal){
  return sqlite4BtPagerGetCookie(db->pPager, piVal);
}

Changes to src/bt_pager.c

159
160
161
162
163
164
165
















166
167
168
169
170
171
172
...
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
...
502
503
504
505
506
507
508

509
510
511
512
513
514
515
...
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
...
577
578
579
580
581
582
583
584












** Remove all entries from the hash-table. And free any allocations made
** by earlier calls to btHashAdd().
*/
static void btHashClear(BtPager *p){
  sqlite4_free(p->pEnv, p->hash.aHash);
  memset(&p->hash, 0, sizeof(BtPageHash));
}
















/*
** End of BtPageHash object interface.
**************************************************************************/

/*
** Open a new pager database handle.
*/
................................................................................
*/
u32 sqlite4BtPagerRootpgno(BtPager *p){
  assert( p->iTransactionLevel>=1 && p->pFd );
  return 2;
}

/*
** Read, write and trim existing database pages.
*/
int sqlite4BtPageGet(BtPager *p, u32 pgno, BtPage **ppPg){
  int rc = SQLITE4_OK;            /* Return code */
  BtPage *pRet;                   /* Returned page handle */

  /* Search the cache for an existing page. */
  pRet = btHashSearch(p, pgno);
................................................................................

/*
** Decrement the refcount on page pPg. Also, indicate that page pPg is
** no longer in use.
*/
int sqlite4BtPageTrim(BtPage *pPg){
  /* assert( !"todo" ); */

  return SQLITE4_OK;
}

int sqlite4BtPageRelease(BtPage *pPg){
  if( pPg ){
    assert( pPg->nRef>=1 );
    pPg->nRef--;
................................................................................
  }
  return SQLITE4_OK;
}

void sqlite4BtPageReference(BtPage *pPg){
  assert( pPg->nRef>=1 );
  pPg->nRef++;
  return SQLITE4_OK;
}

/*
** Allocate a new database page and return a writable reference to it.
*/
int sqlite4BtPageAllocate(BtPager *p, BtPage **ppPg){
  BtPage *pPg = 0;
................................................................................
** Set the schema cookie value. Requires an open write-transaction.
*/
int sqlite4BtPagerGetCookie(BtPager *p, u32 *piVal){
  assert( p->iTransactionLevel>=1 );
  *piVal = p->dbhdr.cookie;
  return SQLITE4_OK;
}




















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







 







|







 







>







 







<







 








>
>
>
>
>
>
>
>
>
>
>
>
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
...
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
...
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
...
533
534
535
536
537
538
539

540
541
542
543
544
545
546
...
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
** Remove all entries from the hash-table. And free any allocations made
** by earlier calls to btHashAdd().
*/
static void btHashClear(BtPager *p){
  sqlite4_free(p->pEnv, p->hash.aHash);
  memset(&p->hash, 0, sizeof(BtPageHash));
}

#ifndef NDEBUG
static void btHashIterate(
  BtPager *p, 
  void (*xCall)(void*, BtPage*),
  void *pCtx
){
  int i;
  for(i=0; i<p->hash.nHash; i++){
    BtPage *pPg;
    for(pPg=p->hash.aHash[i]; pPg; pPg=pPg->pNextHash){
      xCall(pCtx, pPg);
    }
  }
}
#endif
/*
** End of BtPageHash object interface.
**************************************************************************/

/*
** Open a new pager database handle.
*/
................................................................................
*/
u32 sqlite4BtPagerRootpgno(BtPager *p){
  assert( p->iTransactionLevel>=1 && p->pFd );
  return 2;
}

/*
** Request a reference to page pgno of the database.
*/
int sqlite4BtPageGet(BtPager *p, u32 pgno, BtPage **ppPg){
  int rc = SQLITE4_OK;            /* Return code */
  BtPage *pRet;                   /* Returned page handle */

  /* Search the cache for an existing page. */
  pRet = btHashSearch(p, pgno);
................................................................................

/*
** Decrement the refcount on page pPg. Also, indicate that page pPg is
** no longer in use.
*/
int sqlite4BtPageTrim(BtPage *pPg){
  /* assert( !"todo" ); */
  sqlite4BtPageRelease(pPg);
  return SQLITE4_OK;
}

int sqlite4BtPageRelease(BtPage *pPg){
  if( pPg ){
    assert( pPg->nRef>=1 );
    pPg->nRef--;
................................................................................
  }
  return SQLITE4_OK;
}

void sqlite4BtPageReference(BtPage *pPg){
  assert( pPg->nRef>=1 );
  pPg->nRef++;

}

/*
** Allocate a new database page and return a writable reference to it.
*/
int sqlite4BtPageAllocate(BtPager *p, BtPage **ppPg){
  BtPage *pPg = 0;
................................................................................
** Set the schema cookie value. Requires an open write-transaction.
*/
int sqlite4BtPagerGetCookie(BtPager *p, u32 *piVal){
  assert( p->iTransactionLevel>=1 );
  *piVal = p->dbhdr.cookie;
  return SQLITE4_OK;
}

#ifndef NDEBUG
static void btPagerRefcountCb(void *pCtx, BtPage *pPg){
  assert( pPg->nRef>=0 );
  (*(int*)pCtx) += pPg->nRef;
}
int sqlite4BtPagerRefcount(BtPager *p){
  int nRef = 0;
  btHashIterate(p, btPagerRefcountCb, (void*)&nRef);
  return nRef;
}
#endif

Changes to www/bt.wiki

831
832
833
834
835
836
837
838
839

840

841
842
843
844
845
846
847

<p>To commit a write-transaction:





<!--
<hr>



<p>
  As well as the merge-tree file format, LSM style embedded databases derive
  their performance advantages by:

<ol>
  <li> <p>Accumulating a number of writes in main-memory before flushing them to
  disk. LSM does this using its "in-memory tree" in shared-memory. LevelDb uses







|

>

>







831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849

<p>To commit a write-transaction:





<hr>
<hr>
<hr>

<i>
<p>
  As well as the merge-tree file format, LSM style embedded databases derive
  their performance advantages by:

<ol>
  <li> <p>Accumulating a number of writes in main-memory before flushing them to
  disk. LSM does this using its "in-memory tree" in shared-memory. LevelDb uses