/ Check-in [d3897235]
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 | SQL archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1: d3897235d77e48ad09f7edb0a7641458afa0a282
User & Date: drh 2009-07-15 17:25:46
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: 6242db39 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: d3897235 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: a42dc51e user: drh tags: trunk
Changes
Hide Diffs Side-by-Side Diffs Ignore Whitespace Patch

Changes to src/btree.c.

     5      5   ** a legal notice, here is a blessing:
     6      6   **
     7      7   **    May you do good and not evil.
     8      8   **    May you find forgiveness for yourself and forgive others.
     9      9   **    May you share freely, never taking more than you give.
    10     10   **
    11     11   *************************************************************************
    12         -** $Id: btree.c,v 1.688 2009/07/15 11:26:44 drh Exp $
           12  +** $Id: btree.c,v 1.689 2009/07/15 17:25:46 drh Exp $
    13     13   **
    14     14   ** This file implements a external (disk-based) database using BTrees.
    15     15   ** See the header comment on "btreeInt.h" for additional information.
    16     16   ** Including a description of file format and an overview of operation.
    17     17   */
    18     18   #include "btreeInt.h"
    19     19   
................................................................................
   496    496   ** optimization 2 above is ommitted if the corresponding bit is already
   497    497   ** set in BtShared.pHasContent. The contents of the bitvec are cleared
   498    498   ** at the end of every transaction.
   499    499   */
   500    500   static int btreeSetHasContent(BtShared *pBt, Pgno pgno){
   501    501     int rc = SQLITE_OK;
   502    502     if( !pBt->pHasContent ){
   503         -    int nPage;
   504         -    rc = sqlite3PagerPagecount(pBt->pPager, &nPage);
   505         -    if( rc==SQLITE_OK ){
   506         -      pBt->pHasContent = sqlite3BitvecCreate((u32)nPage);
   507         -      if( !pBt->pHasContent ){
   508         -        rc = SQLITE_NOMEM;
   509         -      }
          503  +    int nPage = 100;
          504  +    sqlite3PagerPagecount(pBt->pPager, &nPage);
          505  +    /* If sqlite3PagerPagecount() fails there is no harm because the
          506  +    ** nPage variable is unchanged from its default value of 100 */
          507  +    pBt->pHasContent = sqlite3BitvecCreate((u32)nPage);
          508  +    if( !pBt->pHasContent ){
          509  +      rc = SQLITE_NOMEM;
   510    510       }
   511    511     }
   512    512     if( rc==SQLITE_OK && pgno<=sqlite3BitvecSize(pBt->pHasContent) ){
   513    513       rc = sqlite3BitvecSet(pBt->pHasContent, pgno);
   514    514     }
   515    515     return rc;
   516    516   }
................................................................................
   544    544     int rc;
   545    545   
   546    546     assert( CURSOR_VALID==pCur->eState );
   547    547     assert( 0==pCur->pKey );
   548    548     assert( cursorHoldsMutex(pCur) );
   549    549   
   550    550     rc = sqlite3BtreeKeySize(pCur, &pCur->nKey);
          551  +  assert( rc==SQLITE_OK );  /* Cannot fail since pCur->eState==VALID */
   551    552   
   552    553     /* If this is an intKey table, then the above call to BtreeKeySize()
   553    554     ** stores the integer key in pCur->nKey. In this case this value is
   554    555     ** all that is required. Otherwise, if pCur is not open on an intKey
   555    556     ** table, then malloc space for and store the pCur->nKey bytes of key 
   556    557     ** data.
   557    558     */
   558         -  if( rc==SQLITE_OK && 0==pCur->apPage[0]->intKey){
          559  +  if( 0==pCur->apPage[0]->intKey ){
   559    560       void *pKey = sqlite3Malloc( (int)pCur->nKey );
   560    561       if( pKey ){
   561    562         rc = sqlite3BtreeKey(pCur, 0, (int)pCur->nKey, pKey);
   562    563         if( rc==SQLITE_OK ){
   563    564           pCur->pKey = pKey;
   564    565         }else{
   565    566           sqlite3_free(pKey);
................................................................................
   654    655   ** saveCursorPosition().
   655    656   */
   656    657   static int btreeRestoreCursorPosition(BtCursor *pCur){
   657    658     int rc;
   658    659     assert( cursorHoldsMutex(pCur) );
   659    660     assert( pCur->eState>=CURSOR_REQUIRESEEK );
   660    661     if( pCur->eState==CURSOR_FAULT ){
   661         -    return pCur->skip;
          662  +    return pCur->skipNext;
   662    663     }
   663    664     pCur->eState = CURSOR_INVALID;
   664         -  rc = btreeMoveto(pCur, pCur->pKey, pCur->nKey, 0, &pCur->skip);
          665  +  rc = btreeMoveto(pCur, pCur->pKey, pCur->nKey, 0, &pCur->skipNext);
   665    666     if( rc==SQLITE_OK ){
   666    667       sqlite3_free(pCur->pKey);
   667    668       pCur->pKey = 0;
   668    669       assert( pCur->eState==CURSOR_VALID || pCur->eState==CURSOR_INVALID );
   669    670     }
   670    671     return rc;
   671    672   }
................................................................................
   687    688     int rc;
   688    689   
   689    690     rc = restoreCursorPosition(pCur);
   690    691     if( rc ){
   691    692       *pHasMoved = 1;
   692    693       return rc;
   693    694     }
   694         -  if( pCur->eState!=CURSOR_VALID || pCur->skip!=0 ){
          695  +  if( pCur->eState!=CURSOR_VALID || pCur->skipNext!=0 ){
   695    696       *pHasMoved = 1;
   696    697     }else{
   697    698       *pHasMoved = 0;
   698    699     }
   699    700     return SQLITE_OK;
   700    701   }
   701    702   
................................................................................
  2429   2430       goto trans_begun;
  2430   2431     }
  2431   2432   #endif
  2432   2433   
  2433   2434     /* Any read-only or read-write transaction implies a read-lock on 
  2434   2435     ** page 1. So if some other shared-cache client already has a write-lock 
  2435   2436     ** on page 1, the transaction cannot be opened. */
  2436         -  if( SQLITE_OK!=(rc = querySharedCacheTableLock(p, MASTER_ROOT, READ_LOCK)) ){
  2437         -    goto trans_begun;
  2438         -  }
         2437  +  rc = querySharedCacheTableLock(p, MASTER_ROOT, READ_LOCK);
         2438  +  if( SQLITE_OK!=rc ) goto trans_begun;
  2439   2439   
  2440   2440     do {
  2441   2441       /* Call lockBtree() until either pBt->pPage1 is populated or
  2442   2442       ** lockBtree() returns something other than SQLITE_OK. lockBtree()
  2443   2443       ** may return SQLITE_OK but leave pBt->pPage1 set to 0 if after
  2444   2444       ** reading page 1 it discovers that the page-size of the database 
  2445   2445       ** file is not pBt->pageSize. In this case lockBtree() will update
................................................................................
  3087   3087   void sqlite3BtreeTripAllCursors(Btree *pBtree, int errCode){
  3088   3088     BtCursor *p;
  3089   3089     sqlite3BtreeEnter(pBtree);
  3090   3090     for(p=pBtree->pBt->pCursor; p; p=p->pNext){
  3091   3091       int i;
  3092   3092       sqlite3BtreeClearCursor(p);
  3093   3093       p->eState = CURSOR_FAULT;
  3094         -    p->skip = errCode;
         3094  +    p->skipNext = errCode;
  3095   3095       for(i=0; i<=p->iPage; i++){
  3096   3096         releasePage(p->apPage[i]);
  3097   3097         p->apPage[i] = 0;
  3098   3098       }
  3099   3099     }
  3100   3100     sqlite3BtreeLeave(pBtree);
  3101   3101   }
................................................................................
  4007   4007   
  4008   4008     assert( cursorHoldsMutex(pCur) );
  4009   4009     assert( CURSOR_INVALID < CURSOR_REQUIRESEEK );
  4010   4010     assert( CURSOR_VALID   < CURSOR_REQUIRESEEK );
  4011   4011     assert( CURSOR_FAULT   > CURSOR_REQUIRESEEK );
  4012   4012     if( pCur->eState>=CURSOR_REQUIRESEEK ){
  4013   4013       if( pCur->eState==CURSOR_FAULT ){
  4014         -      assert( pCur->skip!=SQLITE_OK );
  4015         -      return pCur->skip;
         4014  +      assert( pCur->skipNext!=SQLITE_OK );
         4015  +      return pCur->skipNext;
  4016   4016       }
  4017   4017       sqlite3BtreeClearCursor(pCur);
  4018   4018     }
  4019   4019   
  4020   4020     if( pCur->iPage>=0 ){
  4021   4021       int i;
  4022   4022       for(i=1; i<=pCur->iPage; i++){
  4023   4023         releasePage(pCur->apPage[i]);
  4024   4024       }
  4025   4025       pCur->iPage = 0;
  4026   4026     }else{
  4027         -    if( 
  4028         -      SQLITE_OK!=(rc = getAndInitPage(pBt, pCur->pgnoRoot, &pCur->apPage[0]))
  4029         -    ){
         4027  +    rc = getAndInitPage(pBt, pCur->pgnoRoot, &pCur->apPage[0]);
         4028  +    if( rc!=SQLITE_OK ){
  4030   4029         pCur->eState = CURSOR_INVALID;
  4031   4030         return rc;
  4032   4031       }
  4033   4032       pCur->iPage = 0;
  4034   4033   
  4035   4034       /* If pCur->pKeyInfo is not NULL, then the caller that opened this cursor
  4036   4035       ** expected to open it on an index b-tree. Otherwise, if pKeyInfo is
................................................................................
  4419   4418       return rc;
  4420   4419     }
  4421   4420     assert( pRes!=0 );
  4422   4421     if( CURSOR_INVALID==pCur->eState ){
  4423   4422       *pRes = 1;
  4424   4423       return SQLITE_OK;
  4425   4424     }
  4426         -  if( pCur->skip>0 ){
  4427         -    pCur->skip = 0;
         4425  +  if( pCur->skipNext>0 ){
         4426  +    pCur->skipNext = 0;
  4428   4427       *pRes = 0;
  4429   4428       return SQLITE_OK;
  4430   4429     }
  4431         -  pCur->skip = 0;
         4430  +  pCur->skipNext = 0;
  4432   4431   
  4433   4432     pPage = pCur->apPage[pCur->iPage];
  4434   4433     idx = ++pCur->aiIdx[pCur->iPage];
  4435   4434     assert( pPage->isInit );
  4436   4435     assert( idx<=pPage->nCell );
  4437   4436   
  4438   4437     pCur->info.nSize = 0;
................................................................................
  4487   4486       return rc;
  4488   4487     }
  4489   4488     pCur->atLast = 0;
  4490   4489     if( CURSOR_INVALID==pCur->eState ){
  4491   4490       *pRes = 1;
  4492   4491       return SQLITE_OK;
  4493   4492     }
  4494         -  if( pCur->skip<0 ){
  4495         -    pCur->skip = 0;
         4493  +  if( pCur->skipNext<0 ){
         4494  +    pCur->skipNext = 0;
  4496   4495       *pRes = 0;
  4497   4496       return SQLITE_OK;
  4498   4497     }
  4499         -  pCur->skip = 0;
         4498  +  pCur->skipNext = 0;
  4500   4499   
  4501   4500     pPage = pCur->apPage[pCur->iPage];
  4502   4501     assert( pPage->isInit );
  4503   4502     if( !pPage->leaf ){
  4504   4503       int idx = pCur->aiIdx[pCur->iPage];
  4505   4504       rc = moveToChild(pCur, get4byte(findCell(pPage, idx)));
  4506   4505       if( rc ){
................................................................................
  4624   4623         }
  4625   4624         if( rc ){
  4626   4625           pTrunk = 0;
  4627   4626           goto end_allocate_page;
  4628   4627         }
  4629   4628   
  4630   4629         k = get4byte(&pTrunk->aData[4]);
  4631         -      testcase( k==(u32)(pBt->usableSize/4 - 2) );
  4632   4630         if( k==0 && !searchList ){
  4633   4631           /* The trunk has no leaves and the list is not being searched. 
  4634   4632           ** So extract the trunk page itself and use it as the newly 
  4635   4633           ** allocated page */
  4636   4634           assert( pPrevTrunk==0 );
  4637   4635           rc = sqlite3PagerWrite(pTrunk->pDbPage);
  4638   4636           if( rc ){
................................................................................
  5183   5181     assert( idx>=0 && idx<pPage->nCell );
  5184   5182     assert( sz==cellSize(pPage, idx) );
  5185   5183     assert( sqlite3PagerIswriteable(pPage->pDbPage) );
  5186   5184     assert( sqlite3_mutex_held(pPage->pBt->mutex) );
  5187   5185     data = pPage->aData;
  5188   5186     ptr = &data[pPage->cellOffset + 2*idx];
  5189   5187     pc = get2byte(ptr);
  5190         -  if( NEVER(pc<pPage->hdrOffset+6+pPage->childPtrSize)
         5188  +  if( (pc<pPage->hdrOffset+6+pPage->childPtrSize)
  5191   5189        || (pc+sz>pPage->pBt->usableSize) ){
  5192   5190       return SQLITE_CORRUPT_BKPT;
  5193   5191     }
  5194   5192     rc = freeSpace(pPage, pc, sz);
  5195   5193     if( rc!=SQLITE_OK ){
  5196   5194       return rc;
  5197   5195     }
................................................................................
  6426   6424     ** cursors open on the row being replaced (assuming this is a replace
  6427   6425     ** operation - if it is not, the following is a no-op).  */
  6428   6426     if( pCur->pKeyInfo==0 ){
  6429   6427       invalidateIncrblobCursors(p, pCur->pgnoRoot, nKey, 0);
  6430   6428     }
  6431   6429   
  6432   6430     if( pCur->eState==CURSOR_FAULT ){
  6433         -    assert( pCur->skip!=SQLITE_OK );
  6434         -    return pCur->skip;
         6431  +    assert( pCur->skipNext!=SQLITE_OK );
         6432  +    return pCur->skipNext;
  6435   6433     }
  6436   6434   
  6437   6435     /* Save the positions of any other cursors open on this table.
  6438   6436     **
  6439   6437     ** In some cases, the call to btreeMoveto() below is a no-op. For
  6440   6438     ** example, when inserting data into a table with auto-generated integer
  6441   6439     ** keys, the VDBE layer invokes sqlite3BtreeLast() to figure out the 
  6442   6440     ** integer key to use. It then calls this function to actually insert the 
  6443   6441     ** data into the intkey B-Tree. In this case btreeMoveto() recognizes
  6444   6442     ** that the cursor is already where it needs to be and returns without
  6445   6443     ** doing any work. To avoid thwarting these optimizations, it is important
  6446   6444     ** not to clear the cursor here.
  6447   6445     */
  6448         -  if(
  6449         -    SQLITE_OK!=(rc = saveAllCursors(pBt, pCur->pgnoRoot, pCur)) || (!loc &&
  6450         -    SQLITE_OK!=(rc = btreeMoveto(pCur, pKey, nKey, appendBias, &loc))
  6451         -  )){
  6452         -    return rc;
         6446  +  rc = saveAllCursors(pBt, pCur->pgnoRoot, pCur);
         6447  +  if( rc ) return rc;
         6448  +  if( !loc ){
         6449  +    rc = btreeMoveto(pCur, pKey, nKey, appendBias, &loc);
         6450  +    if( rc ) return rc;
  6453   6451     }
  6454   6452     assert( pCur->eState==CURSOR_VALID || (pCur->eState==CURSOR_INVALID && loc) );
  6455   6453   
  6456   6454     pPage = pCur->apPage[pCur->iPage];
  6457   6455     assert( pPage->intKey || nKey>=0 );
  6458   6456     assert( pPage->leaf || !pPage->intKey );
  6459   6457   
................................................................................
  6576   6574     ** the entry being deleted. This cell will replace the cell being deleted
  6577   6575     ** from the internal node. The 'previous' entry is used for this instead
  6578   6576     ** of the 'next' entry, as the previous entry is always a part of the
  6579   6577     ** sub-tree headed by the child page of the cell being deleted. This makes
  6580   6578     ** balancing the tree following the delete operation easier.  */
  6581   6579     if( !pPage->leaf ){
  6582   6580       int notUsed;
  6583         -    if( SQLITE_OK!=(rc = sqlite3BtreePrevious(pCur, &notUsed)) ){
  6584         -      return rc;
  6585         -    }
         6581  +    rc = sqlite3BtreePrevious(pCur, &notUsed);
         6582  +    if( rc ) return rc;
  6586   6583     }
  6587   6584   
  6588   6585     /* Save the positions of any other cursors open on this table before
  6589   6586     ** making any modifications. Make the page containing the entry to be 
  6590   6587     ** deleted writable. Then free any overflow pages associated with the 
  6591   6588     ** entry and finally remove the cell itself from within the page.  
  6592   6589     */

Changes to src/btreeInt.h.

     5      5   ** a legal notice, here is a blessing:
     6      6   **
     7      7   **    May you do good and not evil.
     8      8   **    May you find forgiveness for yourself and forgive others.
     9      9   **    May you share freely, never taking more than you give.
    10     10   **
    11     11   *************************************************************************
    12         -** $Id: btreeInt.h,v 1.51 2009/07/09 05:07:38 danielk1977 Exp $
           12  +** $Id: btreeInt.h,v 1.52 2009/07/15 17:25:46 drh Exp $
    13     13   **
    14     14   ** This file implements a external (disk-based) database using BTrees.
    15     15   ** For a detailed discussion of BTrees, refer to
    16     16   **
    17     17   **     Donald E. Knuth, THE ART OF COMPUTER PROGRAMMING, Volume 3:
    18     18   **     "Sorting And Searching", pages 473-480. Addison-Wesley
    19     19   **     Publishing Company, Reading, Massachusetts.
................................................................................
   488    488     CellInfo info;            /* A parse of the cell we are pointing at */
   489    489     u8 wrFlag;                /* True if writable */
   490    490     u8 atLast;                /* Cursor pointing to the last entry */
   491    491     u8 validNKey;             /* True if info.nKey is valid */
   492    492     u8 eState;                /* One of the CURSOR_XXX constants (see below) */
   493    493     void *pKey;      /* Saved key that was cursor's last known position */
   494    494     i64 nKey;        /* Size of pKey, or last integer key */
   495         -  int skip;        /* (skip<0) -> Prev() is a no-op. (skip>0) -> Next() is */
          495  +  int skipNext;    /* Prev() is noop if negative. Next() is noop if positive */
   496    496   #ifndef SQLITE_OMIT_INCRBLOB
   497    497     u8 isIncrblobHandle;      /* True if this cursor is an incr. io handle */
   498    498     Pgno *aOverflow;          /* Cache of overflow page locations */
   499    499   #endif
   500    500     i16 iPage;                            /* Index of current page in apPage */
   501    501     MemPage *apPage[BTCURSOR_MAX_DEPTH];  /* Pages from root to current page */
   502    502     u16 aiIdx[BTCURSOR_MAX_DEPTH];        /* Current index in apPage[i] */
................................................................................
   634    634   /*
   635    635   ** Read or write a two- and four-byte big-endian integer values.
   636    636   */
   637    637   #define get2byte(x)   ((x)[0]<<8 | (x)[1])
   638    638   #define put2byte(p,v) ((p)[0] = (u8)((v)>>8), (p)[1] = (u8)(v))
   639    639   #define get4byte sqlite3Get4byte
   640    640   #define put4byte sqlite3Put4byte
   641         -