Index: src/btree.c ================================================================== --- src/btree.c +++ src/btree.c @@ -1431,12 +1431,12 @@ ** offsets to each pointer in the cell-pointer array than it is to ** reconstruct the entire page. */ if( (int)data[hdr+7]<=nMaxFrag ){ int iFree = get2byte(&data[hdr+1]); - /* If the initial freeblock offset were out of bounds, that would - ** have been detected by btreeInitPage() when it was computing the + /* If the initial freeblock offset were out of bounds, that would have + ** been detected by btreeComputeFreeSpace() when it was computing the ** number of free bytes on the page. */ assert( iFree<=usableSize-4 ); if( iFree ){ int iFree2 = get2byte(&data[iFree]); if( iFree2>usableSize-4 ) return SQLITE_CORRUPT_PAGE(pPage); @@ -1504,10 +1504,11 @@ memcpy(&data[cbrk], &src[pc], size); } data[hdr+7] = 0; defragment_out: + assert( pPage->nFree>=0 ); if( data[hdr+7]+cbrk-iCellFirst!=pPage->nFree ){ return SQLITE_CORRUPT_PAGE(pPage); } assert( cbrk>=iCellFirst ); put2byte(&data[hdr+5], cbrk); @@ -1631,13 +1632,13 @@ }else{ return SQLITE_CORRUPT_PAGE(pPage); } } - /* If there is enough space between gap and top for one more cell pointer - ** array entry offset, and if the freelist is not empty, then search the - ** freelist looking for a free slot big enough to satisfy the request. + /* If there is enough space between gap and top for one more cell pointer, + ** and if the freelist is not empty, then search the + ** freelist looking for a slot big enough to satisfy the request. */ testcase( gap+2==top ); testcase( gap+1==top ); testcase( gap==top ); if( (data[hdr+2] || data[hdr+1]) && gap+2<=top ){ @@ -1655,10 +1656,11 @@ ** to see if defragmentation is necessary. */ testcase( gap+2+nByte==top ); if( gap+2+nByte>top ){ assert( pPage->nCell>0 || CORRUPT_DB ); + assert( pPage->nFree>=0 ); rc = defragmentPage(pPage, MIN(4, pPage->nFree - (2+nByte))); if( rc ) return rc; top = get2byteNotZero(&data[hdr+5]); assert( gap+2+nByte<=top ); } @@ -1844,25 +1846,18 @@ pPage->max1bytePayload = pBt->max1bytePayload; return SQLITE_OK; } /* -** Initialize the auxiliary information for a disk block. -** -** Return SQLITE_OK on success. If we see that the page does -** not contain a well-formed database page, then return -** SQLITE_CORRUPT. Note that a return of SQLITE_OK does not -** guarantee that the page is well-formed. It only shows that -** we failed to detect any corruption. +** Compute the amount of freespace on the page. In other words, fill +** in the pPage->nFree field. */ -static int btreeInitPage(MemPage *pPage){ +static int btreeComputeFreeSpace(MemPage *pPage){ int pc; /* Address of a freeblock within pPage->aData[] */ u8 hdr; /* Offset to beginning of page header */ u8 *data; /* Equal to pPage->aData */ - BtShared *pBt; /* The main btree structure */ int usableSize; /* Amount of usable space on each page */ - u16 cellOffset; /* Offset from start of page to first cell pointer */ int nFree; /* Number of unused bytes on the page */ int top; /* First byte of the cell content area */ int iCellFirst; /* First allowable cell or freeblock offset */ int iCellLast; /* Last possible cell or freeblock offset */ @@ -1870,75 +1865,22 @@ assert( pPage->pBt->db!=0 ); assert( sqlite3_mutex_held(pPage->pBt->mutex) ); assert( pPage->pgno==sqlite3PagerPagenumber(pPage->pDbPage) ); assert( pPage == sqlite3PagerGetExtra(pPage->pDbPage) ); assert( pPage->aData == sqlite3PagerGetData(pPage->pDbPage) ); - assert( pPage->isInit==0 ); + assert( pPage->isInit==1 ); + assert( pPage->nFree<0 ); - pBt = pPage->pBt; + usableSize = pPage->pBt->usableSize; hdr = pPage->hdrOffset; data = pPage->aData; - /* EVIDENCE-OF: R-28594-02890 The one-byte flag at offset 0 indicating - ** the b-tree page type. */ - if( decodeFlags(pPage, data[hdr]) ){ - return SQLITE_CORRUPT_PAGE(pPage); - } - assert( pBt->pageSize>=512 && pBt->pageSize<=65536 ); - pPage->maskPage = (u16)(pBt->pageSize - 1); - pPage->nOverflow = 0; - usableSize = pBt->usableSize; - pPage->cellOffset = cellOffset = hdr + 8 + pPage->childPtrSize; - pPage->aDataEnd = &data[usableSize]; - pPage->aCellIdx = &data[cellOffset]; - pPage->aDataOfst = &data[pPage->childPtrSize]; /* EVIDENCE-OF: R-58015-48175 The two-byte integer at offset 5 designates ** the start of the cell content area. A zero value for this integer is ** interpreted as 65536. */ top = get2byteNotZero(&data[hdr+5]); - /* EVIDENCE-OF: R-37002-32774 The two-byte integer at offset 3 gives the - ** number of cells on the page. */ - pPage->nCell = get2byte(&data[hdr+3]); - if( pPage->nCell>MX_CELL(pBt) ){ - /* To many cells for a single page. The page must be corrupt */ - return SQLITE_CORRUPT_PAGE(pPage); - } - testcase( pPage->nCell==MX_CELL(pBt) ); - /* EVIDENCE-OF: R-24089-57979 If a page contains no cells (which is only - ** possible for a root page of a table that contains no rows) then the - ** offset to the cell content area will equal the page size minus the - ** bytes of reserved space. */ - assert( pPage->nCell>0 || top==usableSize || CORRUPT_DB ); - - /* A malformed database page might cause us to read past the end - ** of page when parsing a cell. - ** - ** The following block of code checks early to see if a cell extends - ** past the end of a page boundary and causes SQLITE_CORRUPT to be - ** returned if it does. - */ - iCellFirst = cellOffset + 2*pPage->nCell; + iCellFirst = hdr + 8 + pPage->childPtrSize + 2*pPage->nCell; iCellLast = usableSize - 4; - if( pBt->db->flags & SQLITE_CellSizeCk ){ - int i; /* Index into the cell pointer array */ - int sz; /* Size of a cell */ - - if( !pPage->leaf ) iCellLast--; - for(i=0; inCell; i++){ - pc = get2byteAligned(&data[cellOffset+i*2]); - testcase( pc==iCellFirst ); - testcase( pc==iCellLast ); - if( pciCellLast ){ - return SQLITE_CORRUPT_PAGE(pPage); - } - sz = pPage->xCellSize(pPage, &data[pc]); - testcase( pc+sz==usableSize ); - if( pc+sz>usableSize ){ - return SQLITE_CORRUPT_PAGE(pPage); - } - } - if( !pPage->leaf ) iCellLast++; - } /* Compute the total free space on the page ** EVIDENCE-OF: R-23588-34450 The two-byte integer at offset 1 gives the ** start of the first freeblock on the page, or is zero if there are no ** freeblocks. */ @@ -1982,10 +1924,102 @@ */ if( nFree>usableSize ){ return SQLITE_CORRUPT_PAGE(pPage); } pPage->nFree = (u16)(nFree - iCellFirst); + return SQLITE_OK; +} + +/* +** Initialize the auxiliary information for a disk block. +** +** Return SQLITE_OK on success. If we see that the page does +** not contain a well-formed database page, then return +** SQLITE_CORRUPT. Note that a return of SQLITE_OK does not +** guarantee that the page is well-formed. It only shows that +** we failed to detect any corruption. +*/ +static int btreeInitPage(MemPage *pPage){ + int pc; /* Address of a freeblock within pPage->aData[] */ + u8 hdr; /* Offset to beginning of page header */ + u8 *data; /* Equal to pPage->aData */ + BtShared *pBt; /* The main btree structure */ + int usableSize; /* Amount of usable space on each page */ + u16 cellOffset; /* Offset from start of page to first cell pointer */ + int iCellFirst; /* First allowable cell or freeblock offset */ + int iCellLast; /* Last possible cell or freeblock offset */ + + assert( pPage->pBt!=0 ); + assert( pPage->pBt->db!=0 ); + assert( sqlite3_mutex_held(pPage->pBt->mutex) ); + assert( pPage->pgno==sqlite3PagerPagenumber(pPage->pDbPage) ); + assert( pPage == sqlite3PagerGetExtra(pPage->pDbPage) ); + assert( pPage->aData == sqlite3PagerGetData(pPage->pDbPage) ); + assert( pPage->isInit==0 ); + + pBt = pPage->pBt; + hdr = pPage->hdrOffset; + data = pPage->aData; + /* EVIDENCE-OF: R-28594-02890 The one-byte flag at offset 0 indicating + ** the b-tree page type. */ + if( decodeFlags(pPage, data[hdr]) ){ + return SQLITE_CORRUPT_PAGE(pPage); + } + assert( pBt->pageSize>=512 && pBt->pageSize<=65536 ); + pPage->maskPage = (u16)(pBt->pageSize - 1); + pPage->nOverflow = 0; + usableSize = pBt->usableSize; + pPage->cellOffset = cellOffset = hdr + 8 + pPage->childPtrSize; + pPage->aDataEnd = &data[usableSize]; + pPage->aCellIdx = &data[cellOffset]; + pPage->aDataOfst = &data[pPage->childPtrSize]; + /* EVIDENCE-OF: R-37002-32774 The two-byte integer at offset 3 gives the + ** number of cells on the page. */ + pPage->nCell = get2byte(&data[hdr+3]); + if( pPage->nCell>MX_CELL(pBt) ){ + /* To many cells for a single page. The page must be corrupt */ + return SQLITE_CORRUPT_PAGE(pPage); + } + testcase( pPage->nCell==MX_CELL(pBt) ); + /* EVIDENCE-OF: R-24089-57979 If a page contains no cells (which is only + ** possible for a root page of a table that contains no rows) then the + ** offset to the cell content area will equal the page size minus the + ** bytes of reserved space. */ + assert( pPage->nCell>0 + || get2byteNotZero(&data[hdr+5])==usableSize + || CORRUPT_DB ); + + /* A malformed database page might cause us to read past the end + ** of page when parsing a cell. + ** + ** The following block of code checks early to see if a cell extends + ** past the end of a page boundary and causes SQLITE_CORRUPT to be + ** returned if it does. + */ + iCellFirst = cellOffset + 2*pPage->nCell; + iCellLast = usableSize - 4; + if( pBt->db->flags & SQLITE_CellSizeCk ){ + int i; /* Index into the cell pointer array */ + int sz; /* Size of a cell */ + + if( !pPage->leaf ) iCellLast--; + for(i=0; inCell; i++){ + pc = get2byteAligned(&data[cellOffset+i*2]); + testcase( pc==iCellFirst ); + testcase( pc==iCellLast ); + if( pciCellLast ){ + return SQLITE_CORRUPT_PAGE(pPage); + } + sz = pPage->xCellSize(pPage, &data[pc]); + testcase( pc+sz==usableSize ); + if( pc+sz>usableSize ){ + return SQLITE_CORRUPT_PAGE(pPage); + } + } + if( !pPage->leaf ) iCellLast++; + } + pPage->nFree = -1; /* Indicate that this value is yet uncomputed */ pPage->isInit = 1; return SQLITE_OK; } /* @@ -2125,38 +2159,38 @@ assert( pCur==0 || bReadOnly==pCur->curPagerFlags ); assert( pCur==0 || pCur->iPage>0 ); if( pgno>btreePagecount(pBt) ){ rc = SQLITE_CORRUPT_BKPT; - goto getAndInitPage_error; + goto getAndInitPage_error1; } rc = sqlite3PagerGet(pBt->pPager, pgno, (DbPage**)&pDbPage, bReadOnly); if( rc ){ - goto getAndInitPage_error; + goto getAndInitPage_error1; } *ppPage = (MemPage*)sqlite3PagerGetExtra(pDbPage); if( (*ppPage)->isInit==0 ){ btreePageFromDbPage(pDbPage, pgno, pBt); rc = btreeInitPage(*ppPage); if( rc!=SQLITE_OK ){ - releasePage(*ppPage); - goto getAndInitPage_error; + goto getAndInitPage_error2; } } assert( (*ppPage)->pgno==pgno ); assert( (*ppPage)->aData==sqlite3PagerGetData(pDbPage) ); /* If obtaining a child page for a cursor, we must verify that the page is ** compatible with the root page. */ if( pCur && ((*ppPage)->nCell<1 || (*ppPage)->intKey!=pCur->curIntKey) ){ rc = SQLITE_CORRUPT_PGNO(pgno); - releasePage(*ppPage); - goto getAndInitPage_error; + goto getAndInitPage_error2; } return SQLITE_OK; -getAndInitPage_error: +getAndInitPage_error2: + releasePage(*ppPage); +getAndInitPage_error1: if( pCur ){ pCur->iPage--; pCur->pPage = pCur->apPage[pCur->iPage]; } testcase( pgno==0 ); @@ -6564,10 +6598,11 @@ if( *pRC ) return; assert( idx>=0 && idxnCell ); assert( CORRUPT_DB || sz==cellSize(pPage, idx) ); assert( sqlite3PagerIswriteable(pPage->pDbPage) ); assert( sqlite3_mutex_held(pPage->pBt->mutex) ); + assert( pPage->nFree>=0 ); data = pPage->aData; ptr = &pPage->aCellIdx[2*idx]; pc = get2byte(ptr); hdr = pPage->hdrOffset; testcase( pc==get2byte(&data[hdr+5]) ); @@ -6634,10 +6669,11 @@ ** malformed cell from a leaf page to an interior page, if the cell size ** wanted to be less than 4 but got rounded up to 4 on the leaf, then size ** might be less than 8 (leaf-size + pointer) on the interior node. Hence ** the term after the || in the following assert(). */ assert( sz==pPage->xCellSize(pPage, pCell) || (sz==8 && iChild>0) ); + assert( pPage->nFree>=0 ); if( pPage->nOverflow || sz+2>pPage->nFree ){ if( pTemp ){ memcpy(pTemp, pCell, sz); pCell = pTemp; } @@ -7185,12 +7221,14 @@ Pgno pgnoNew; /* Page number of pNew */ assert( sqlite3_mutex_held(pPage->pBt->mutex) ); assert( sqlite3PagerIswriteable(pParent->pDbPage) ); assert( pPage->nOverflow==1 ); - + if( pPage->nCell==0 ) return SQLITE_CORRUPT_BKPT; /* dbfuzz001.test */ + assert( pPage->nFree>=0 ); + assert( pParent->nFree>=0 ); /* Allocate a new page. This page will become the right-sibling of ** pPage. Make the parent page writable, so that the new divider cell ** may be inserted. If both these operations are successful, proceed. */ @@ -7356,10 +7394,11 @@ ** fairly obscure circumstances, even though it is a copy of initialized ** page pFrom. */ pTo->isInit = 0; rc = btreeInitPage(pTo); + if( rc==SQLITE_OK ) rc = btreeComputeFreeSpace(pTo); if( rc!=SQLITE_OK ){ *pRC = rc; return; } @@ -7464,10 +7503,11 @@ assert( pParent->nOverflow==0 || pParent->aiOvfl[0]==iParentIdx ); if( !aOvflSpace ){ return SQLITE_NOMEM_BKPT; } + assert( pParent->nFree>=0 ); /* Find the sibling pages to balance. Also locate the cells in pParent ** that divide the siblings. An attempt is made to find NN siblings on ** either side of pPage. More siblings are taken from one side, however, ** if there are fewer than NN siblings on the other side. If pParent @@ -7502,10 +7542,17 @@ while( 1 ){ rc = getAndInitPage(pBt, pgno, &apOld[i], 0, 0); if( rc ){ memset(apOld, 0, (i+1)*sizeof(MemPage*)); goto balance_cleanup; + } + if( apOld[i]->nFree<0 ){ + rc = btreeComputeFreeSpace(apOld[i]); + if( rc ){ + memset(apOld, 0, (i)*sizeof(MemPage*)); + goto balance_cleanup; + } } nMaxCells += 1+apOld[i]->nCell+apOld[i]->nOverflow; if( (i--)==0 ) break; if( pParent->nOverflow && i+nxDiv==pParent->aiOvfl[0] ){ @@ -7702,10 +7749,11 @@ if( !leafData ){ k++; b.apEnd[k] = pParent->aDataEnd; b.ixNx[k] = cntOld[i]+1; } + assert( p->nFree>=0 ); szNew[i] = usableSpace - p->nFree; for(j=0; jnOverflow; j++){ szNew[i] += 2 + p->xCellSize(p, p->apOvfl[j]); } cntNew[i] = cntOld[i]; @@ -8245,10 +8293,11 @@ do { int iPage = pCur->iPage; MemPage *pPage = pCur->pPage; + if( NEVER(pPage->nFree<0) && btreeComputeFreeSpace(pPage) ) break; if( iPage==0 ){ if( pPage->nOverflow ){ /* The root page of the b-tree is overfull. In this case call the ** balance_deeper() function to create a new child for the root-page ** and copy the current contents of the root-page to it. The @@ -8273,10 +8322,13 @@ }else{ MemPage * const pParent = pCur->apPage[iPage-1]; int const iIdx = pCur->aiIdx[iPage-1]; rc = sqlite3PagerWrite(pParent->pDbPage); + if( rc==SQLITE_OK && pParent->nFree<0 ){ + rc = btreeComputeFreeSpace(pParent); + } if( rc==SQLITE_OK ){ #ifndef SQLITE_OMIT_QUICKBALANCE if( pPage->intKeyLeaf && pPage->nOverflow==1 && pPage->aiOvfl[0]==pPage->nCell @@ -8619,10 +8671,14 @@ assert( pCur->eState==CURSOR_VALID || (pCur->eState==CURSOR_INVALID && loc) ); pPage = pCur->pPage; assert( pPage->intKey || pX->nKey>=0 ); assert( pPage->leaf || !pPage->intKey ); + if( pPage->nFree<0 ){ + rc = btreeComputeFreeSpace(pPage); + if( rc ) return rc; + } TRACE(("INSERT: table=%d nkey=%lld ndata=%d page=%d %s\n", pCur->pgnoRoot, pX->nKey, pX->nData, pPage->pgno, loc==0 ? "overwrite" : "new entry")); assert( pPage->isInit ); @@ -8769,10 +8825,11 @@ iCellDepth = pCur->iPage; iCellIdx = pCur->ix; pPage = pCur->pPage; pCell = findCell(pPage, iCellIdx); + if( pPage->nFree<0 && btreeComputeFreeSpace(pPage) ) return SQLITE_CORRUPT; /* If the bPreserve flag is set to true, then the cursor position must ** be preserved following this delete operation. If the current delete ** will cause a b-tree rebalance, then this is done by saving the cursor ** key and leaving the cursor in CURSOR_REQUIRESEEK state before @@ -8839,10 +8896,14 @@ MemPage *pLeaf = pCur->pPage; int nCell; Pgno n; unsigned char *pTmp; + if( pLeaf->nFree<0 ){ + rc = btreeComputeFreeSpace(pLeaf); + if( rc ) return rc; + } if( iCellDepthiPage-1 ){ n = pCur->apPage[iCellDepth+1]->pgno; }else{ n = pCur->pPage->pgno; } @@ -9729,10 +9790,15 @@ if( (rc = btreeInitPage(pPage))!=0 ){ assert( rc==SQLITE_CORRUPT ); /* The only possible error from InitPage */ checkAppendMsg(pCheck, "btreeInitPage() returns error code %d", rc); goto end_of_check; + } + if( (rc = btreeComputeFreeSpace(pPage))!=0 ){ + assert( rc==SQLITE_CORRUPT ); + checkAppendMsg(pCheck, "free space corruption", rc); + goto end_of_check; } data = pPage->aData; hdr = pPage->hdrOffset; /* Set up for cell analysis */ Index: src/btreeInt.h ================================================================== --- src/btreeInt.h +++ src/btreeInt.h @@ -284,11 +284,11 @@ u8 max1bytePayload; /* min(maxLocal,127) */ u8 nOverflow; /* Number of overflow cell bodies in aCell[] */ u16 maxLocal; /* Copy of BtShared.maxLocal or BtShared.maxLeaf */ u16 minLocal; /* Copy of BtShared.minLocal or BtShared.minLeaf */ u16 cellOffset; /* Index in aData of first cell pointer */ - u16 nFree; /* Number of free bytes on the page */ + int nFree; /* Number of free bytes on the page. -1 for unknown */ u16 nCell; /* Number of cells on this page, local and ovfl */ u16 maskPage; /* Mask for page offset */ u16 aiOvfl[4]; /* Insert the i-th overflow cell before the aiOvfl-th ** non-overflow cell */ u8 *apOvfl[4]; /* Pointers to the body of overflow cells */ Index: test/corrupt2.test ================================================================== --- test/corrupt2.test +++ test/corrupt2.test @@ -93,15 +93,15 @@ seek $f 101 start puts -nonewline $f "\xFF\xFF" close $f sqlite3 db2 corrupt.db - catchsql " - $::presql - SELECT * FROM sqlite_master; - " db2 -} {1 {database disk image is malformed}} + # Note: This test is no longer meaningful due to the deferred computation + # of MemPage.nFree + catchsql {PRAGMA quick_check} db2 +} {0 {{*** in database main *** +Page 1: free space corruption}}} do_test corrupt2-1.5 { db2 close # Corrupt the free-block list on page 1. @@ -116,15 +116,13 @@ puts -nonewline $f "\x00\x00" puts -nonewline $f "\x10\x00" close $f sqlite3 db2 corrupt.db - catchsql " - $::presql - SELECT * FROM sqlite_master; - " db2 -} {1 {database disk image is malformed}} + catchsql {PRAGMA quick_check} db2 +} {0 {{*** in database main *** +Page 1: free space corruption}}} db2 close # Corrupt a database by having 2 indices of the same name: do_test corrupt2-2.1 { Index: test/corruptD.test ================================================================== --- test/corruptD.test +++ test/corruptD.test @@ -109,12 +109,13 @@ # containing the offset of the first free block in a page. # do_test corruptD-1.1.1 { incr_change_counter hexio_write test.db [expr 1024+1] FFFF - catchsql { SELECT * FROM t1 ORDER BY rowid } -} {1 {database disk image is malformed}} + catchsql { PRAGMA quick_check } +} {0 {{*** in database main *** +Page 2: free space corruption}}} do_test corruptD-1.1.2 { incr_change_counter hexio_write test.db [expr 1024+1] [hexio_render_int32 1021] catchsql { SELECT * FROM t1 ORDER BY rowid } } {1 {database disk image is malformed}} Index: test/corruptK.test ================================================================== --- test/corruptK.test +++ test/corruptK.test @@ -66,13 +66,19 @@ close $fd } {} do_execsql_test 1.3 { INSERT INTO t1 VALUES(randomblob(20)); } + +# This test no longer functions due to the deferred computation of +# MemPage.nFree. +# +if 0 { do_catchsql_test 1.4 { INSERT INTO t1 VALUES(randomblob(90)); } {1 {database disk image is malformed}} +} #------------------------------------------------------------------------- reset_db do_execsql_test 2.1 { PRAGMA page_size=1024;