SQLite

Check-in [d3897235d7]
Login

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

Overview
Comment:Simplifications to btree.c in support of structural testing. Renamed the "skip" field of the BtCursor object to "skipNext" to make it easier to search for places where it is used. (CVS 6896)
Downloads: Tarball | ZIP archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1: d3897235d77e48ad09f7edb0a7641458afa0a282
User & Date: drh 2009-07-15 17:25:46.000
Context
2009-07-15
18:15
Fix a potential database corruption following DROP TABLE when the pending byte page corresponds to a ptrmap page. This situation cannot happen in a real deployment - but it still needs to be fixed. (CVS 6897) (check-in: 6242db39f7 user: drh tags: trunk)
17:25
Simplifications to btree.c in support of structural testing. Renamed the "skip" field of the BtCursor object to "skipNext" to make it easier to search for places where it is used. (CVS 6896) (check-in: d3897235d7 user: drh tags: trunk)
16:30
Remove an assert() from vdbeaux.c that might not be true if the database file is corrupt. (CVS 6895) (check-in: a42dc51e3b user: drh tags: trunk)
Changes
Side-by-Side Diff Ignore Whitespace Patch
Changes to src/btree.c.
1
2
3
4
5
6
7
8
9
10
11
12

13
14
15
16
17
18
19
1
2
3
4
5
6
7
8
9
10
11

12
13
14
15
16
17
18
19











-
+







/*
** 2004 April 6
**
** 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.
**
*************************************************************************
** $Id: btree.c,v 1.688 2009/07/15 11:26:44 drh Exp $
** $Id: btree.c,v 1.689 2009/07/15 17:25:46 drh Exp $
**
** This file implements a external (disk-based) database using BTrees.
** See the header comment on "btreeInt.h" for additional information.
** Including a description of file format and an overview of operation.
*/
#include "btreeInt.h"

496
497
498
499
500
501
502
503
504
505
506
507
508







509
510
511
512
513
514
515
516
496
497
498
499
500
501
502






503
504
505
506
507
508
509

510
511
512
513
514
515
516







-
-
-
-
-
-
+
+
+
+
+
+
+
-







** optimization 2 above is ommitted if the corresponding bit is already
** set in BtShared.pHasContent. The contents of the bitvec are cleared
** at the end of every transaction.
*/
static int btreeSetHasContent(BtShared *pBt, Pgno pgno){
  int rc = SQLITE_OK;
  if( !pBt->pHasContent ){
    int nPage;
    rc = sqlite3PagerPagecount(pBt->pPager, &nPage);
    if( rc==SQLITE_OK ){
      pBt->pHasContent = sqlite3BitvecCreate((u32)nPage);
      if( !pBt->pHasContent ){
        rc = SQLITE_NOMEM;
    int nPage = 100;
    sqlite3PagerPagecount(pBt->pPager, &nPage);
    /* If sqlite3PagerPagecount() fails there is no harm because the
    ** nPage variable is unchanged from its default value of 100 */
    pBt->pHasContent = sqlite3BitvecCreate((u32)nPage);
    if( !pBt->pHasContent ){
      rc = SQLITE_NOMEM;
      }
    }
  }
  if( rc==SQLITE_OK && pgno<=sqlite3BitvecSize(pBt->pHasContent) ){
    rc = sqlite3BitvecSet(pBt->pHasContent, pgno);
  }
  return rc;
}
544
545
546
547
548
549
550

551
552
553
554
555
556
557
558

559
560
561
562
563
564
565
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558

559
560
561
562
563
564
565
566







+







-
+







  int rc;

  assert( CURSOR_VALID==pCur->eState );
  assert( 0==pCur->pKey );
  assert( cursorHoldsMutex(pCur) );

  rc = sqlite3BtreeKeySize(pCur, &pCur->nKey);
  assert( rc==SQLITE_OK );  /* Cannot fail since pCur->eState==VALID */

  /* If this is an intKey table, then the above call to BtreeKeySize()
  ** stores the integer key in pCur->nKey. In this case this value is
  ** all that is required. Otherwise, if pCur is not open on an intKey
  ** table, then malloc space for and store the pCur->nKey bytes of key 
  ** data.
  */
  if( rc==SQLITE_OK && 0==pCur->apPage[0]->intKey){
  if( 0==pCur->apPage[0]->intKey ){
    void *pKey = sqlite3Malloc( (int)pCur->nKey );
    if( pKey ){
      rc = sqlite3BtreeKey(pCur, 0, (int)pCur->nKey, pKey);
      if( rc==SQLITE_OK ){
        pCur->pKey = pKey;
      }else{
        sqlite3_free(pKey);
654
655
656
657
658
659
660
661

662
663
664

665
666
667
668
669
670
671
655
656
657
658
659
660
661

662
663
664

665
666
667
668
669
670
671
672







-
+


-
+







** saveCursorPosition().
*/
static int btreeRestoreCursorPosition(BtCursor *pCur){
  int rc;
  assert( cursorHoldsMutex(pCur) );
  assert( pCur->eState>=CURSOR_REQUIRESEEK );
  if( pCur->eState==CURSOR_FAULT ){
    return pCur->skip;
    return pCur->skipNext;
  }
  pCur->eState = CURSOR_INVALID;
  rc = btreeMoveto(pCur, pCur->pKey, pCur->nKey, 0, &pCur->skip);
  rc = btreeMoveto(pCur, pCur->pKey, pCur->nKey, 0, &pCur->skipNext);
  if( rc==SQLITE_OK ){
    sqlite3_free(pCur->pKey);
    pCur->pKey = 0;
    assert( pCur->eState==CURSOR_VALID || pCur->eState==CURSOR_INVALID );
  }
  return rc;
}
687
688
689
690
691
692
693
694

695
696
697
698
699
700
701
688
689
690
691
692
693
694

695
696
697
698
699
700
701
702







-
+







  int rc;

  rc = restoreCursorPosition(pCur);
  if( rc ){
    *pHasMoved = 1;
    return rc;
  }
  if( pCur->eState!=CURSOR_VALID || pCur->skip!=0 ){
  if( pCur->eState!=CURSOR_VALID || pCur->skipNext!=0 ){
    *pHasMoved = 1;
  }else{
    *pHasMoved = 0;
  }
  return SQLITE_OK;
}

2429
2430
2431
2432
2433
2434
2435
2436
2437


2438
2439
2440
2441
2442
2443
2444
2445
2430
2431
2432
2433
2434
2435
2436


2437
2438

2439
2440
2441
2442
2443
2444
2445







-
-
+
+
-







    goto trans_begun;
  }
#endif

  /* Any read-only or read-write transaction implies a read-lock on 
  ** page 1. So if some other shared-cache client already has a write-lock 
  ** on page 1, the transaction cannot be opened. */
  if( SQLITE_OK!=(rc = querySharedCacheTableLock(p, MASTER_ROOT, READ_LOCK)) ){
    goto trans_begun;
  rc = querySharedCacheTableLock(p, MASTER_ROOT, READ_LOCK);
  if( SQLITE_OK!=rc ) goto trans_begun;
  }

  do {
    /* Call lockBtree() until either pBt->pPage1 is populated or
    ** lockBtree() returns something other than SQLITE_OK. lockBtree()
    ** may return SQLITE_OK but leave pBt->pPage1 set to 0 if after
    ** reading page 1 it discovers that the page-size of the database 
    ** file is not pBt->pageSize. In this case lockBtree() will update
3087
3088
3089
3090
3091
3092
3093
3094

3095
3096
3097
3098
3099
3100
3101
3087
3088
3089
3090
3091
3092
3093

3094
3095
3096
3097
3098
3099
3100
3101







-
+







void sqlite3BtreeTripAllCursors(Btree *pBtree, int errCode){
  BtCursor *p;
  sqlite3BtreeEnter(pBtree);
  for(p=pBtree->pBt->pCursor; p; p=p->pNext){
    int i;
    sqlite3BtreeClearCursor(p);
    p->eState = CURSOR_FAULT;
    p->skip = errCode;
    p->skipNext = errCode;
    for(i=0; i<=p->iPage; i++){
      releasePage(p->apPage[i]);
      p->apPage[i] = 0;
    }
  }
  sqlite3BtreeLeave(pBtree);
}
4007
4008
4009
4010
4011
4012
4013
4014
4015


4016
4017
4018
4019
4020
4021
4022
4023
4024
4025
4026
4027
4028
4029


4030
4031
4032
4033
4034
4035
4036
4007
4008
4009
4010
4011
4012
4013


4014
4015
4016
4017
4018
4019
4020
4021
4022
4023
4024
4025
4026



4027
4028
4029
4030
4031
4032
4033
4034
4035







-
-
+
+











-
-
-
+
+








  assert( cursorHoldsMutex(pCur) );
  assert( CURSOR_INVALID < CURSOR_REQUIRESEEK );
  assert( CURSOR_VALID   < CURSOR_REQUIRESEEK );
  assert( CURSOR_FAULT   > CURSOR_REQUIRESEEK );
  if( pCur->eState>=CURSOR_REQUIRESEEK ){
    if( pCur->eState==CURSOR_FAULT ){
      assert( pCur->skip!=SQLITE_OK );
      return pCur->skip;
      assert( pCur->skipNext!=SQLITE_OK );
      return pCur->skipNext;
    }
    sqlite3BtreeClearCursor(pCur);
  }

  if( pCur->iPage>=0 ){
    int i;
    for(i=1; i<=pCur->iPage; i++){
      releasePage(pCur->apPage[i]);
    }
    pCur->iPage = 0;
  }else{
    if( 
      SQLITE_OK!=(rc = getAndInitPage(pBt, pCur->pgnoRoot, &pCur->apPage[0]))
    ){
    rc = getAndInitPage(pBt, pCur->pgnoRoot, &pCur->apPage[0]);
    if( rc!=SQLITE_OK ){
      pCur->eState = CURSOR_INVALID;
      return rc;
    }
    pCur->iPage = 0;

    /* If pCur->pKeyInfo is not NULL, then the caller that opened this cursor
    ** expected to open it on an index b-tree. Otherwise, if pKeyInfo is
4419
4420
4421
4422
4423
4424
4425
4426
4427


4428
4429
4430
4431

4432
4433
4434
4435
4436
4437
4438
4418
4419
4420
4421
4422
4423
4424


4425
4426
4427
4428
4429

4430
4431
4432
4433
4434
4435
4436
4437







-
-
+
+



-
+







    return rc;
  }
  assert( pRes!=0 );
  if( CURSOR_INVALID==pCur->eState ){
    *pRes = 1;
    return SQLITE_OK;
  }
  if( pCur->skip>0 ){
    pCur->skip = 0;
  if( pCur->skipNext>0 ){
    pCur->skipNext = 0;
    *pRes = 0;
    return SQLITE_OK;
  }
  pCur->skip = 0;
  pCur->skipNext = 0;

  pPage = pCur->apPage[pCur->iPage];
  idx = ++pCur->aiIdx[pCur->iPage];
  assert( pPage->isInit );
  assert( idx<=pPage->nCell );

  pCur->info.nSize = 0;
4487
4488
4489
4490
4491
4492
4493
4494
4495


4496
4497
4498
4499

4500
4501
4502
4503
4504
4505
4506
4486
4487
4488
4489
4490
4491
4492


4493
4494
4495
4496
4497

4498
4499
4500
4501
4502
4503
4504
4505







-
-
+
+



-
+







    return rc;
  }
  pCur->atLast = 0;
  if( CURSOR_INVALID==pCur->eState ){
    *pRes = 1;
    return SQLITE_OK;
  }
  if( pCur->skip<0 ){
    pCur->skip = 0;
  if( pCur->skipNext<0 ){
    pCur->skipNext = 0;
    *pRes = 0;
    return SQLITE_OK;
  }
  pCur->skip = 0;
  pCur->skipNext = 0;

  pPage = pCur->apPage[pCur->iPage];
  assert( pPage->isInit );
  if( !pPage->leaf ){
    int idx = pCur->aiIdx[pCur->iPage];
    rc = moveToChild(pCur, get4byte(findCell(pPage, idx)));
    if( rc ){
4624
4625
4626
4627
4628
4629
4630
4631
4632
4633
4634
4635
4636
4637
4638
4623
4624
4625
4626
4627
4628
4629

4630
4631
4632
4633
4634
4635
4636







-







      }
      if( rc ){
        pTrunk = 0;
        goto end_allocate_page;
      }

      k = get4byte(&pTrunk->aData[4]);
      testcase( k==(u32)(pBt->usableSize/4 - 2) );
      if( k==0 && !searchList ){
        /* The trunk has no leaves and the list is not being searched. 
        ** So extract the trunk page itself and use it as the newly 
        ** allocated page */
        assert( pPrevTrunk==0 );
        rc = sqlite3PagerWrite(pTrunk->pDbPage);
        if( rc ){
5183
5184
5185
5186
5187
5188
5189
5190

5191
5192
5193
5194
5195
5196
5197
5181
5182
5183
5184
5185
5186
5187

5188
5189
5190
5191
5192
5193
5194
5195







-
+







  assert( idx>=0 && idx<pPage->nCell );
  assert( sz==cellSize(pPage, idx) );
  assert( sqlite3PagerIswriteable(pPage->pDbPage) );
  assert( sqlite3_mutex_held(pPage->pBt->mutex) );
  data = pPage->aData;
  ptr = &data[pPage->cellOffset + 2*idx];
  pc = get2byte(ptr);
  if( NEVER(pc<pPage->hdrOffset+6+pPage->childPtrSize)
  if( (pc<pPage->hdrOffset+6+pPage->childPtrSize)
     || (pc+sz>pPage->pBt->usableSize) ){
    return SQLITE_CORRUPT_BKPT;
  }
  rc = freeSpace(pPage, pc, sz);
  if( rc!=SQLITE_OK ){
    return rc;
  }
6426
6427
6428
6429
6430
6431
6432
6433
6434


6435
6436
6437
6438
6439
6440
6441
6442
6443
6444
6445
6446
6447
6448
6449
6450




6451
6452

6453
6454
6455
6456
6457
6458
6459
6424
6425
6426
6427
6428
6429
6430


6431
6432
6433
6434
6435
6436
6437
6438
6439
6440
6441
6442
6443
6444
6445



6446
6447
6448
6449


6450
6451
6452
6453
6454
6455
6456
6457







-
-
+
+













-
-
-
+
+
+
+
-
-
+







  ** cursors open on the row being replaced (assuming this is a replace
  ** operation - if it is not, the following is a no-op).  */
  if( pCur->pKeyInfo==0 ){
    invalidateIncrblobCursors(p, pCur->pgnoRoot, nKey, 0);
  }

  if( pCur->eState==CURSOR_FAULT ){
    assert( pCur->skip!=SQLITE_OK );
    return pCur->skip;
    assert( pCur->skipNext!=SQLITE_OK );
    return pCur->skipNext;
  }

  /* Save the positions of any other cursors open on this table.
  **
  ** In some cases, the call to btreeMoveto() below is a no-op. For
  ** example, when inserting data into a table with auto-generated integer
  ** keys, the VDBE layer invokes sqlite3BtreeLast() to figure out the 
  ** integer key to use. It then calls this function to actually insert the 
  ** data into the intkey B-Tree. In this case btreeMoveto() recognizes
  ** that the cursor is already where it needs to be and returns without
  ** doing any work. To avoid thwarting these optimizations, it is important
  ** not to clear the cursor here.
  */
  if(
    SQLITE_OK!=(rc = saveAllCursors(pBt, pCur->pgnoRoot, pCur)) || (!loc &&
    SQLITE_OK!=(rc = btreeMoveto(pCur, pKey, nKey, appendBias, &loc))
  rc = saveAllCursors(pBt, pCur->pgnoRoot, pCur);
  if( rc ) return rc;
  if( !loc ){
    rc = btreeMoveto(pCur, pKey, nKey, appendBias, &loc);
  )){
    return rc;
    if( rc ) return rc;
  }
  assert( pCur->eState==CURSOR_VALID || (pCur->eState==CURSOR_INVALID && loc) );

  pPage = pCur->apPage[pCur->iPage];
  assert( pPage->intKey || nKey>=0 );
  assert( pPage->leaf || !pPage->intKey );

6576
6577
6578
6579
6580
6581
6582
6583
6584


6585
6586
6587
6588
6589
6590
6591
6592
6574
6575
6576
6577
6578
6579
6580


6581
6582

6583
6584
6585
6586
6587
6588
6589







-
-
+
+
-







  ** the entry being deleted. This cell will replace the cell being deleted
  ** from the internal node. The 'previous' entry is used for this instead
  ** of the 'next' entry, as the previous entry is always a part of the
  ** sub-tree headed by the child page of the cell being deleted. This makes
  ** balancing the tree following the delete operation easier.  */
  if( !pPage->leaf ){
    int notUsed;
    if( SQLITE_OK!=(rc = sqlite3BtreePrevious(pCur, &notUsed)) ){
      return rc;
    rc = sqlite3BtreePrevious(pCur, &notUsed);
    if( rc ) return rc;
    }
  }

  /* Save the positions of any other cursors open on this table before
  ** making any modifications. Make the page containing the entry to be 
  ** deleted writable. Then free any overflow pages associated with the 
  ** entry and finally remove the cell itself from within the page.  
  */
Changes to src/btreeInt.h.
1
2
3
4
5
6
7
8
9
10
11
12

13
14
15
16
17
18
19
1
2
3
4
5
6
7
8
9
10
11

12
13
14
15
16
17
18
19











-
+







/*
** 2004 April 6
**
** 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.
**
*************************************************************************
** $Id: btreeInt.h,v 1.51 2009/07/09 05:07:38 danielk1977 Exp $
** $Id: btreeInt.h,v 1.52 2009/07/15 17:25:46 drh Exp $
**
** This file implements a external (disk-based) database using BTrees.
** For a detailed discussion of BTrees, refer to
**
**     Donald E. Knuth, THE ART OF COMPUTER PROGRAMMING, Volume 3:
**     "Sorting And Searching", pages 473-480. Addison-Wesley
**     Publishing Company, Reading, Massachusetts.
488
489
490
491
492
493
494
495

496
497
498
499
500
501
502
488
489
490
491
492
493
494

495
496
497
498
499
500
501
502







-
+







  CellInfo info;            /* A parse of the cell we are pointing at */
  u8 wrFlag;                /* True if writable */
  u8 atLast;                /* Cursor pointing to the last entry */
  u8 validNKey;             /* True if info.nKey is valid */
  u8 eState;                /* One of the CURSOR_XXX constants (see below) */
  void *pKey;      /* Saved key that was cursor's last known position */
  i64 nKey;        /* Size of pKey, or last integer key */
  int skip;        /* (skip<0) -> Prev() is a no-op. (skip>0) -> Next() is */
  int skipNext;    /* Prev() is noop if negative. Next() is noop if positive */
#ifndef SQLITE_OMIT_INCRBLOB
  u8 isIncrblobHandle;      /* True if this cursor is an incr. io handle */
  Pgno *aOverflow;          /* Cache of overflow page locations */
#endif
  i16 iPage;                            /* Index of current page in apPage */
  MemPage *apPage[BTCURSOR_MAX_DEPTH];  /* Pages from root to current page */
  u16 aiIdx[BTCURSOR_MAX_DEPTH];        /* Current index in apPage[i] */
634
635
636
637
638
639
640
641
634
635
636
637
638
639
640








-
/*
** Read or write a two- and four-byte big-endian integer values.
*/
#define get2byte(x)   ((x)[0]<<8 | (x)[1])
#define put2byte(p,v) ((p)[0] = (u8)((v)>>8), (p)[1] = (u8)(v))
#define get4byte sqlite3Get4byte
#define put4byte sqlite3Put4byte