/ Check-in [177f5f40]
Login

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

Overview
Comment:Defer computing the number of bytes of free space on a btree page until that value is actually needed.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA3-256:177f5f40eabfcfd229ac7f291dfed9e9ee35762e86923a0f356915f389da177d
User & Date: drh 2019-02-12 01:04:49
Context
2019-02-12
01:28
New test cases in test/fuzzdata8.db. check-in: ab2356f5 user: drh tags: trunk
01:04
Defer computing the number of bytes of free space on a btree page until that value is actually needed. check-in: 177f5f40 user: drh tags: trunk
00:58
Change an assert() into a NEVER(), since the condition is difficult to prove with certainty. Improved comment on the MemPage.nFree field. Closed-Leaf check-in: fec071b8 user: drh tags: deferred-free-space
2019-02-11
16:12
Fix another segfault that could occur in fts5 with a corrupted database. check-in: 09e33738 user: dan tags: trunk
Changes
Hide Diffs Side-by-Side Diffs Ignore Whitespace Patch

Changes to src/btree.c.

  1429   1429     ** or fewer fragmented bytes. In this case it is faster to move the
  1430   1430     ** two (or one) blocks of cells using memmove() and add the required
  1431   1431     ** offsets to each pointer in the cell-pointer array than it is to 
  1432   1432     ** reconstruct the entire page.  */
  1433   1433     if( (int)data[hdr+7]<=nMaxFrag ){
  1434   1434       int iFree = get2byte(&data[hdr+1]);
  1435   1435   
  1436         -    /* If the initial freeblock offset were out of bounds, that would
  1437         -    ** have been detected by btreeInitPage() when it was computing the
         1436  +    /* If the initial freeblock offset were out of bounds, that would have
         1437  +    ** been detected by btreeComputeFreeSpace() when it was computing the
  1438   1438       ** number of free bytes on the page. */
  1439   1439       assert( iFree<=usableSize-4 );
  1440   1440       if( iFree ){
  1441   1441         int iFree2 = get2byte(&data[iFree]);
  1442   1442         if( iFree2>usableSize-4 ) return SQLITE_CORRUPT_PAGE(pPage);
  1443   1443         if( 0==iFree2 || (data[iFree2]==0 && data[iFree2+1]==0) ){
  1444   1444           u8 *pEnd = &data[cellOffset + nCell*2];
................................................................................
  1502   1502         src = temp;
  1503   1503       }
  1504   1504       memcpy(&data[cbrk], &src[pc], size);
  1505   1505     }
  1506   1506     data[hdr+7] = 0;
  1507   1507   
  1508   1508    defragment_out:
         1509  +  assert( pPage->nFree>=0 );
  1509   1510     if( data[hdr+7]+cbrk-iCellFirst!=pPage->nFree ){
  1510   1511       return SQLITE_CORRUPT_PAGE(pPage);
  1511   1512     }
  1512   1513     assert( cbrk>=iCellFirst );
  1513   1514     put2byte(&data[hdr+5], cbrk);
  1514   1515     data[hdr+1] = 0;
  1515   1516     data[hdr+2] = 0;
................................................................................
  1629   1630       if( top==0 && pPage->pBt->usableSize==65536 ){
  1630   1631         top = 65536;
  1631   1632       }else{
  1632   1633         return SQLITE_CORRUPT_PAGE(pPage);
  1633   1634       }
  1634   1635     }
  1635   1636   
  1636         -  /* If there is enough space between gap and top for one more cell pointer
  1637         -  ** array entry offset, and if the freelist is not empty, then search the
  1638         -  ** freelist looking for a free slot big enough to satisfy the request.
         1637  +  /* If there is enough space between gap and top for one more cell pointer,
         1638  +  ** and if the freelist is not empty, then search the
         1639  +  ** freelist looking for a slot big enough to satisfy the request.
  1639   1640     */
  1640   1641     testcase( gap+2==top );
  1641   1642     testcase( gap+1==top );
  1642   1643     testcase( gap==top );
  1643   1644     if( (data[hdr+2] || data[hdr+1]) && gap+2<=top ){
  1644   1645       u8 *pSpace = pageFindSlot(pPage, nByte, &rc);
  1645   1646       if( pSpace ){
................................................................................
  1653   1654   
  1654   1655     /* The request could not be fulfilled using a freelist slot.  Check
  1655   1656     ** to see if defragmentation is necessary.
  1656   1657     */
  1657   1658     testcase( gap+2+nByte==top );
  1658   1659     if( gap+2+nByte>top ){
  1659   1660       assert( pPage->nCell>0 || CORRUPT_DB );
         1661  +    assert( pPage->nFree>=0 );
  1660   1662       rc = defragmentPage(pPage, MIN(4, pPage->nFree - (2+nByte)));
  1661   1663       if( rc ) return rc;
  1662   1664       top = get2byteNotZero(&data[hdr+5]);
  1663   1665       assert( gap+2+nByte<=top );
  1664   1666     }
  1665   1667   
  1666   1668   
................................................................................
  1842   1844       return SQLITE_CORRUPT_PAGE(pPage);
  1843   1845     }
  1844   1846     pPage->max1bytePayload = pBt->max1bytePayload;
  1845   1847     return SQLITE_OK;
  1846   1848   }
  1847   1849   
  1848   1850   /*
  1849         -** Initialize the auxiliary information for a disk block.
  1850         -**
  1851         -** Return SQLITE_OK on success.  If we see that the page does
  1852         -** not contain a well-formed database page, then return 
  1853         -** SQLITE_CORRUPT.  Note that a return of SQLITE_OK does not
  1854         -** guarantee that the page is well-formed.  It only shows that
  1855         -** we failed to detect any corruption.
         1851  +** Compute the amount of freespace on the page.  In other words, fill
         1852  +** in the pPage->nFree field.
  1856   1853   */
  1857         -static int btreeInitPage(MemPage *pPage){
         1854  +static int btreeComputeFreeSpace(MemPage *pPage){
  1858   1855     int pc;            /* Address of a freeblock within pPage->aData[] */
  1859   1856     u8 hdr;            /* Offset to beginning of page header */
  1860   1857     u8 *data;          /* Equal to pPage->aData */
  1861         -  BtShared *pBt;        /* The main btree structure */
  1862   1858     int usableSize;    /* Amount of usable space on each page */
  1863         -  u16 cellOffset;    /* Offset from start of page to first cell pointer */
  1864   1859     int nFree;         /* Number of unused bytes on the page */
  1865   1860     int top;           /* First byte of the cell content area */
  1866   1861     int iCellFirst;    /* First allowable cell or freeblock offset */
  1867   1862     int iCellLast;     /* Last possible cell or freeblock offset */
  1868   1863   
  1869   1864     assert( pPage->pBt!=0 );
  1870   1865     assert( pPage->pBt->db!=0 );
  1871   1866     assert( sqlite3_mutex_held(pPage->pBt->mutex) );
  1872   1867     assert( pPage->pgno==sqlite3PagerPagenumber(pPage->pDbPage) );
  1873   1868     assert( pPage == sqlite3PagerGetExtra(pPage->pDbPage) );
  1874   1869     assert( pPage->aData == sqlite3PagerGetData(pPage->pDbPage) );
  1875         -  assert( pPage->isInit==0 );
         1870  +  assert( pPage->isInit==1 );
         1871  +  assert( pPage->nFree<0 );
  1876   1872   
  1877         -  pBt = pPage->pBt;
         1873  +  usableSize = pPage->pBt->usableSize;
  1878   1874     hdr = pPage->hdrOffset;
  1879   1875     data = pPage->aData;
  1880         -  /* EVIDENCE-OF: R-28594-02890 The one-byte flag at offset 0 indicating
  1881         -  ** the b-tree page type. */
  1882         -  if( decodeFlags(pPage, data[hdr]) ){
  1883         -    return SQLITE_CORRUPT_PAGE(pPage);
  1884         -  }
  1885         -  assert( pBt->pageSize>=512 && pBt->pageSize<=65536 );
  1886         -  pPage->maskPage = (u16)(pBt->pageSize - 1);
  1887         -  pPage->nOverflow = 0;
  1888         -  usableSize = pBt->usableSize;
  1889         -  pPage->cellOffset = cellOffset = hdr + 8 + pPage->childPtrSize;
  1890         -  pPage->aDataEnd = &data[usableSize];
  1891         -  pPage->aCellIdx = &data[cellOffset];
  1892         -  pPage->aDataOfst = &data[pPage->childPtrSize];
  1893   1876     /* EVIDENCE-OF: R-58015-48175 The two-byte integer at offset 5 designates
  1894   1877     ** the start of the cell content area. A zero value for this integer is
  1895   1878     ** interpreted as 65536. */
  1896   1879     top = get2byteNotZero(&data[hdr+5]);
  1897         -  /* EVIDENCE-OF: R-37002-32774 The two-byte integer at offset 3 gives the
  1898         -  ** number of cells on the page. */
  1899         -  pPage->nCell = get2byte(&data[hdr+3]);
  1900         -  if( pPage->nCell>MX_CELL(pBt) ){
  1901         -    /* To many cells for a single page.  The page must be corrupt */
  1902         -    return SQLITE_CORRUPT_PAGE(pPage);
  1903         -  }
  1904         -  testcase( pPage->nCell==MX_CELL(pBt) );
  1905         -  /* EVIDENCE-OF: R-24089-57979 If a page contains no cells (which is only
  1906         -  ** possible for a root page of a table that contains no rows) then the
  1907         -  ** offset to the cell content area will equal the page size minus the
  1908         -  ** bytes of reserved space. */
  1909         -  assert( pPage->nCell>0 || top==usableSize || CORRUPT_DB );
  1910         -
  1911         -  /* A malformed database page might cause us to read past the end
  1912         -  ** of page when parsing a cell.  
  1913         -  **
  1914         -  ** The following block of code checks early to see if a cell extends
  1915         -  ** past the end of a page boundary and causes SQLITE_CORRUPT to be 
  1916         -  ** returned if it does.
  1917         -  */
  1918         -  iCellFirst = cellOffset + 2*pPage->nCell;
         1880  +  iCellFirst = hdr + 8 + pPage->childPtrSize + 2*pPage->nCell;
  1919   1881     iCellLast = usableSize - 4;
  1920         -  if( pBt->db->flags & SQLITE_CellSizeCk ){
  1921         -    int i;            /* Index into the cell pointer array */
  1922         -    int sz;           /* Size of a cell */
  1923         -
  1924         -    if( !pPage->leaf ) iCellLast--;
  1925         -    for(i=0; i<pPage->nCell; i++){
  1926         -      pc = get2byteAligned(&data[cellOffset+i*2]);
  1927         -      testcase( pc==iCellFirst );
  1928         -      testcase( pc==iCellLast );
  1929         -      if( pc<iCellFirst || pc>iCellLast ){
  1930         -        return SQLITE_CORRUPT_PAGE(pPage);
  1931         -      }
  1932         -      sz = pPage->xCellSize(pPage, &data[pc]);
  1933         -      testcase( pc+sz==usableSize );
  1934         -      if( pc+sz>usableSize ){
  1935         -        return SQLITE_CORRUPT_PAGE(pPage);
  1936         -      }
  1937         -    }
  1938         -    if( !pPage->leaf ) iCellLast++;
  1939         -  }  
  1940   1882   
  1941   1883     /* Compute the total free space on the page
  1942   1884     ** EVIDENCE-OF: R-23588-34450 The two-byte integer at offset 1 gives the
  1943   1885     ** start of the first freeblock on the page, or is zero if there are no
  1944   1886     ** freeblocks. */
  1945   1887     pc = get2byte(&data[hdr+1]);
  1946   1888     nFree = data[hdr+7] + top;  /* Init nFree to non-freeblock free space */
................................................................................
  1980   1922     ** serves to verify that the offset to the start of the cell-content
  1981   1923     ** area, according to the page header, lies within the page.
  1982   1924     */
  1983   1925     if( nFree>usableSize ){
  1984   1926       return SQLITE_CORRUPT_PAGE(pPage);
  1985   1927     }
  1986   1928     pPage->nFree = (u16)(nFree - iCellFirst);
         1929  +  return SQLITE_OK;
         1930  +}
         1931  +
         1932  +/*
         1933  +** Initialize the auxiliary information for a disk block.
         1934  +**
         1935  +** Return SQLITE_OK on success.  If we see that the page does
         1936  +** not contain a well-formed database page, then return 
         1937  +** SQLITE_CORRUPT.  Note that a return of SQLITE_OK does not
         1938  +** guarantee that the page is well-formed.  It only shows that
         1939  +** we failed to detect any corruption.
         1940  +*/
         1941  +static int btreeInitPage(MemPage *pPage){
         1942  +  int pc;            /* Address of a freeblock within pPage->aData[] */
         1943  +  u8 hdr;            /* Offset to beginning of page header */
         1944  +  u8 *data;          /* Equal to pPage->aData */
         1945  +  BtShared *pBt;        /* The main btree structure */
         1946  +  int usableSize;    /* Amount of usable space on each page */
         1947  +  u16 cellOffset;    /* Offset from start of page to first cell pointer */
         1948  +  int iCellFirst;    /* First allowable cell or freeblock offset */
         1949  +  int iCellLast;     /* Last possible cell or freeblock offset */
         1950  +
         1951  +  assert( pPage->pBt!=0 );
         1952  +  assert( pPage->pBt->db!=0 );
         1953  +  assert( sqlite3_mutex_held(pPage->pBt->mutex) );
         1954  +  assert( pPage->pgno==sqlite3PagerPagenumber(pPage->pDbPage) );
         1955  +  assert( pPage == sqlite3PagerGetExtra(pPage->pDbPage) );
         1956  +  assert( pPage->aData == sqlite3PagerGetData(pPage->pDbPage) );
         1957  +  assert( pPage->isInit==0 );
         1958  +
         1959  +  pBt = pPage->pBt;
         1960  +  hdr = pPage->hdrOffset;
         1961  +  data = pPage->aData;
         1962  +  /* EVIDENCE-OF: R-28594-02890 The one-byte flag at offset 0 indicating
         1963  +  ** the b-tree page type. */
         1964  +  if( decodeFlags(pPage, data[hdr]) ){
         1965  +    return SQLITE_CORRUPT_PAGE(pPage);
         1966  +  }
         1967  +  assert( pBt->pageSize>=512 && pBt->pageSize<=65536 );
         1968  +  pPage->maskPage = (u16)(pBt->pageSize - 1);
         1969  +  pPage->nOverflow = 0;
         1970  +  usableSize = pBt->usableSize;
         1971  +  pPage->cellOffset = cellOffset = hdr + 8 + pPage->childPtrSize;
         1972  +  pPage->aDataEnd = &data[usableSize];
         1973  +  pPage->aCellIdx = &data[cellOffset];
         1974  +  pPage->aDataOfst = &data[pPage->childPtrSize];
         1975  +  /* EVIDENCE-OF: R-37002-32774 The two-byte integer at offset 3 gives the
         1976  +  ** number of cells on the page. */
         1977  +  pPage->nCell = get2byte(&data[hdr+3]);
         1978  +  if( pPage->nCell>MX_CELL(pBt) ){
         1979  +    /* To many cells for a single page.  The page must be corrupt */
         1980  +    return SQLITE_CORRUPT_PAGE(pPage);
         1981  +  }
         1982  +  testcase( pPage->nCell==MX_CELL(pBt) );
         1983  +  /* EVIDENCE-OF: R-24089-57979 If a page contains no cells (which is only
         1984  +  ** possible for a root page of a table that contains no rows) then the
         1985  +  ** offset to the cell content area will equal the page size minus the
         1986  +  ** bytes of reserved space. */
         1987  +  assert( pPage->nCell>0
         1988  +       || get2byteNotZero(&data[hdr+5])==usableSize
         1989  +       || CORRUPT_DB );
         1990  +
         1991  +  /* A malformed database page might cause us to read past the end
         1992  +  ** of page when parsing a cell.  
         1993  +  **
         1994  +  ** The following block of code checks early to see if a cell extends
         1995  +  ** past the end of a page boundary and causes SQLITE_CORRUPT to be 
         1996  +  ** returned if it does.
         1997  +  */
         1998  +  iCellFirst = cellOffset + 2*pPage->nCell;
         1999  +  iCellLast = usableSize - 4;
         2000  +  if( pBt->db->flags & SQLITE_CellSizeCk ){
         2001  +    int i;            /* Index into the cell pointer array */
         2002  +    int sz;           /* Size of a cell */
         2003  +
         2004  +    if( !pPage->leaf ) iCellLast--;
         2005  +    for(i=0; i<pPage->nCell; i++){
         2006  +      pc = get2byteAligned(&data[cellOffset+i*2]);
         2007  +      testcase( pc==iCellFirst );
         2008  +      testcase( pc==iCellLast );
         2009  +      if( pc<iCellFirst || pc>iCellLast ){
         2010  +        return SQLITE_CORRUPT_PAGE(pPage);
         2011  +      }
         2012  +      sz = pPage->xCellSize(pPage, &data[pc]);
         2013  +      testcase( pc+sz==usableSize );
         2014  +      if( pc+sz>usableSize ){
         2015  +        return SQLITE_CORRUPT_PAGE(pPage);
         2016  +      }
         2017  +    }
         2018  +    if( !pPage->leaf ) iCellLast++;
         2019  +  }  
         2020  +  pPage->nFree = -1;  /* Indicate that this value is yet uncomputed */
  1987   2021     pPage->isInit = 1;
  1988   2022     return SQLITE_OK;
  1989   2023   }
  1990   2024   
  1991   2025   /*
  1992   2026   ** Set up a raw page so that it looks like a database page holding
  1993   2027   ** no entries.
................................................................................
  2123   2157     assert( sqlite3_mutex_held(pBt->mutex) );
  2124   2158     assert( pCur==0 || ppPage==&pCur->pPage );
  2125   2159     assert( pCur==0 || bReadOnly==pCur->curPagerFlags );
  2126   2160     assert( pCur==0 || pCur->iPage>0 );
  2127   2161   
  2128   2162     if( pgno>btreePagecount(pBt) ){
  2129   2163       rc = SQLITE_CORRUPT_BKPT;
  2130         -    goto getAndInitPage_error;
         2164  +    goto getAndInitPage_error1;
  2131   2165     }
  2132   2166     rc = sqlite3PagerGet(pBt->pPager, pgno, (DbPage**)&pDbPage, bReadOnly);
  2133   2167     if( rc ){
  2134         -    goto getAndInitPage_error;
         2168  +    goto getAndInitPage_error1;
  2135   2169     }
  2136   2170     *ppPage = (MemPage*)sqlite3PagerGetExtra(pDbPage);
  2137   2171     if( (*ppPage)->isInit==0 ){
  2138   2172       btreePageFromDbPage(pDbPage, pgno, pBt);
  2139   2173       rc = btreeInitPage(*ppPage);
  2140   2174       if( rc!=SQLITE_OK ){
  2141         -      releasePage(*ppPage);
  2142         -      goto getAndInitPage_error;
         2175  +      goto getAndInitPage_error2;
  2143   2176       }
  2144   2177     }
  2145   2178     assert( (*ppPage)->pgno==pgno );
  2146   2179     assert( (*ppPage)->aData==sqlite3PagerGetData(pDbPage) );
  2147   2180   
  2148   2181     /* If obtaining a child page for a cursor, we must verify that the page is
  2149   2182     ** compatible with the root page. */
  2150   2183     if( pCur && ((*ppPage)->nCell<1 || (*ppPage)->intKey!=pCur->curIntKey) ){
  2151   2184       rc = SQLITE_CORRUPT_PGNO(pgno);
  2152         -    releasePage(*ppPage);
  2153         -    goto getAndInitPage_error;
         2185  +    goto getAndInitPage_error2;
  2154   2186     }
  2155   2187     return SQLITE_OK;
  2156   2188   
  2157         -getAndInitPage_error:
         2189  +getAndInitPage_error2:
         2190  +  releasePage(*ppPage);
         2191  +getAndInitPage_error1:
  2158   2192     if( pCur ){
  2159   2193       pCur->iPage--;
  2160   2194       pCur->pPage = pCur->apPage[pCur->iPage];
  2161   2195     }
  2162   2196     testcase( pgno==0 );
  2163   2197     assert( pgno!=0 || rc==SQLITE_CORRUPT );
  2164   2198     return rc;
................................................................................
  6562   6596     int hdr;        /* Beginning of the header.  0 most pages.  100 page 1 */
  6563   6597   
  6564   6598     if( *pRC ) return;
  6565   6599     assert( idx>=0 && idx<pPage->nCell );
  6566   6600     assert( CORRUPT_DB || sz==cellSize(pPage, idx) );
  6567   6601     assert( sqlite3PagerIswriteable(pPage->pDbPage) );
  6568   6602     assert( sqlite3_mutex_held(pPage->pBt->mutex) );
         6603  +  assert( pPage->nFree>=0 );
  6569   6604     data = pPage->aData;
  6570   6605     ptr = &pPage->aCellIdx[2*idx];
  6571   6606     pc = get2byte(ptr);
  6572   6607     hdr = pPage->hdrOffset;
  6573   6608     testcase( pc==get2byte(&data[hdr+5]) );
  6574   6609     testcase( pc+sz==pPage->pBt->usableSize );
  6575   6610     if( pc+sz > pPage->pBt->usableSize ){
................................................................................
  6632   6667     assert( sqlite3_mutex_held(pPage->pBt->mutex) );
  6633   6668     /* The cell should normally be sized correctly.  However, when moving a
  6634   6669     ** malformed cell from a leaf page to an interior page, if the cell size
  6635   6670     ** wanted to be less than 4 but got rounded up to 4 on the leaf, then size
  6636   6671     ** might be less than 8 (leaf-size + pointer) on the interior node.  Hence
  6637   6672     ** the term after the || in the following assert(). */
  6638   6673     assert( sz==pPage->xCellSize(pPage, pCell) || (sz==8 && iChild>0) );
         6674  +  assert( pPage->nFree>=0 );
  6639   6675     if( pPage->nOverflow || sz+2>pPage->nFree ){
  6640   6676       if( pTemp ){
  6641   6677         memcpy(pTemp, pCell, sz);
  6642   6678         pCell = pTemp;
  6643   6679       }
  6644   6680       if( iChild ){
  6645   6681         put4byte(pCell, iChild);
................................................................................
  7183   7219     MemPage *pNew;                       /* Newly allocated page */
  7184   7220     int rc;                              /* Return Code */
  7185   7221     Pgno pgnoNew;                        /* Page number of pNew */
  7186   7222   
  7187   7223     assert( sqlite3_mutex_held(pPage->pBt->mutex) );
  7188   7224     assert( sqlite3PagerIswriteable(pParent->pDbPage) );
  7189   7225     assert( pPage->nOverflow==1 );
  7190         -
         7226  +  
  7191   7227     if( pPage->nCell==0 ) return SQLITE_CORRUPT_BKPT;  /* dbfuzz001.test */
         7228  +  assert( pPage->nFree>=0 );
         7229  +  assert( pParent->nFree>=0 );
  7192   7230   
  7193   7231     /* Allocate a new page. This page will become the right-sibling of 
  7194   7232     ** pPage. Make the parent page writable, so that the new divider cell
  7195   7233     ** may be inserted. If both these operations are successful, proceed.
  7196   7234     */
  7197   7235     rc = allocateBtreePage(pBt, &pNew, &pgnoNew, 0, 0);
  7198   7236   
................................................................................
  7354   7392       /* Reinitialize page pTo so that the contents of the MemPage structure
  7355   7393       ** match the new data. The initialization of pTo can actually fail under
  7356   7394       ** fairly obscure circumstances, even though it is a copy of initialized 
  7357   7395       ** page pFrom.
  7358   7396       */
  7359   7397       pTo->isInit = 0;
  7360   7398       rc = btreeInitPage(pTo);
         7399  +    if( rc==SQLITE_OK ) rc = btreeComputeFreeSpace(pTo);
  7361   7400       if( rc!=SQLITE_OK ){
  7362   7401         *pRC = rc;
  7363   7402         return;
  7364   7403       }
  7365   7404     
  7366   7405       /* If this is an auto-vacuum database, update the pointer-map entries
  7367   7406       ** for any b-tree or overflow pages that pTo now contains the pointers to.
................................................................................
  7462   7501     */
  7463   7502     assert( pParent->nOverflow==0 || pParent->nOverflow==1 );
  7464   7503     assert( pParent->nOverflow==0 || pParent->aiOvfl[0]==iParentIdx );
  7465   7504   
  7466   7505     if( !aOvflSpace ){
  7467   7506       return SQLITE_NOMEM_BKPT;
  7468   7507     }
         7508  +  assert( pParent->nFree>=0 );
  7469   7509   
  7470   7510     /* Find the sibling pages to balance. Also locate the cells in pParent 
  7471   7511     ** that divide the siblings. An attempt is made to find NN siblings on 
  7472   7512     ** either side of pPage. More siblings are taken from one side, however, 
  7473   7513     ** if there are fewer than NN siblings on the other side. If pParent
  7474   7514     ** has NB or fewer children then all children of pParent are taken.  
  7475   7515     **
................................................................................
  7500   7540     }
  7501   7541     pgno = get4byte(pRight);
  7502   7542     while( 1 ){
  7503   7543       rc = getAndInitPage(pBt, pgno, &apOld[i], 0, 0);
  7504   7544       if( rc ){
  7505   7545         memset(apOld, 0, (i+1)*sizeof(MemPage*));
  7506   7546         goto balance_cleanup;
         7547  +    }
         7548  +    if( apOld[i]->nFree<0 ){
         7549  +      rc = btreeComputeFreeSpace(apOld[i]);
         7550  +      if( rc ){
         7551  +        memset(apOld, 0, (i)*sizeof(MemPage*));
         7552  +        goto balance_cleanup;
         7553  +      }
  7507   7554       }
  7508   7555       nMaxCells += 1+apOld[i]->nCell+apOld[i]->nOverflow;
  7509   7556       if( (i--)==0 ) break;
  7510   7557   
  7511   7558       if( pParent->nOverflow && i+nxDiv==pParent->aiOvfl[0] ){
  7512   7559         apDiv[i] = pParent->apOvfl[0];
  7513   7560         pgno = get4byte(apDiv[i]);
................................................................................
  7700   7747       b.apEnd[k] = p->aDataEnd;
  7701   7748       b.ixNx[k] = cntOld[i];
  7702   7749       if( !leafData ){
  7703   7750         k++;
  7704   7751         b.apEnd[k] = pParent->aDataEnd;
  7705   7752         b.ixNx[k] = cntOld[i]+1;
  7706   7753       }
         7754  +    assert( p->nFree>=0 );
  7707   7755       szNew[i] = usableSpace - p->nFree;
  7708   7756       for(j=0; j<p->nOverflow; j++){
  7709   7757         szNew[i] += 2 + p->xCellSize(p, p->apOvfl[j]);
  7710   7758       }
  7711   7759       cntNew[i] = cntOld[i];
  7712   7760     }
  7713   7761     k = nOld;
................................................................................
  8243   8291     VVA_ONLY( int balance_quick_called = 0 );
  8244   8292     VVA_ONLY( int balance_deeper_called = 0 );
  8245   8293   
  8246   8294     do {
  8247   8295       int iPage = pCur->iPage;
  8248   8296       MemPage *pPage = pCur->pPage;
  8249   8297   
         8298  +    if( NEVER(pPage->nFree<0) && btreeComputeFreeSpace(pPage) ) break;
  8250   8299       if( iPage==0 ){
  8251   8300         if( pPage->nOverflow ){
  8252   8301           /* The root page of the b-tree is overfull. In this case call the
  8253   8302           ** balance_deeper() function to create a new child for the root-page
  8254   8303           ** and copy the current contents of the root-page to it. The
  8255   8304           ** next iteration of the do-loop will balance the child page.
  8256   8305           */ 
................................................................................
  8271   8320       }else if( pPage->nOverflow==0 && pPage->nFree<=nMin ){
  8272   8321         break;
  8273   8322       }else{
  8274   8323         MemPage * const pParent = pCur->apPage[iPage-1];
  8275   8324         int const iIdx = pCur->aiIdx[iPage-1];
  8276   8325   
  8277   8326         rc = sqlite3PagerWrite(pParent->pDbPage);
         8327  +      if( rc==SQLITE_OK && pParent->nFree<0 ){
         8328  +        rc = btreeComputeFreeSpace(pParent);
         8329  +      }
  8278   8330         if( rc==SQLITE_OK ){
  8279   8331   #ifndef SQLITE_OMIT_QUICKBALANCE
  8280   8332           if( pPage->intKeyLeaf
  8281   8333            && pPage->nOverflow==1
  8282   8334            && pPage->aiOvfl[0]==pPage->nCell
  8283   8335            && pParent->pgno!=1
  8284   8336            && pParent->nCell==iIdx
................................................................................
  8617   8669   
  8618   8670     }
  8619   8671     assert( pCur->eState==CURSOR_VALID || (pCur->eState==CURSOR_INVALID && loc) );
  8620   8672   
  8621   8673     pPage = pCur->pPage;
  8622   8674     assert( pPage->intKey || pX->nKey>=0 );
  8623   8675     assert( pPage->leaf || !pPage->intKey );
         8676  +  if( pPage->nFree<0 ){
         8677  +    rc = btreeComputeFreeSpace(pPage);
         8678  +    if( rc ) return rc;
         8679  +  }
  8624   8680   
  8625   8681     TRACE(("INSERT: table=%d nkey=%lld ndata=%d page=%d %s\n",
  8626   8682             pCur->pgnoRoot, pX->nKey, pX->nData, pPage->pgno,
  8627   8683             loc==0 ? "overwrite" : "new entry"));
  8628   8684     assert( pPage->isInit );
  8629   8685     newCell = pBt->pTmpSpace;
  8630   8686     assert( newCell!=0 );
................................................................................
  8767   8823     assert( pCur->eState==CURSOR_VALID );
  8768   8824     assert( (flags & ~(BTREE_SAVEPOSITION | BTREE_AUXDELETE))==0 );
  8769   8825   
  8770   8826     iCellDepth = pCur->iPage;
  8771   8827     iCellIdx = pCur->ix;
  8772   8828     pPage = pCur->pPage;
  8773   8829     pCell = findCell(pPage, iCellIdx);
         8830  +  if( pPage->nFree<0 && btreeComputeFreeSpace(pPage) ) return SQLITE_CORRUPT;
  8774   8831   
  8775   8832     /* If the bPreserve flag is set to true, then the cursor position must
  8776   8833     ** be preserved following this delete operation. If the current delete
  8777   8834     ** will cause a b-tree rebalance, then this is done by saving the cursor
  8778   8835     ** key and leaving the cursor in CURSOR_REQUIRESEEK state before 
  8779   8836     ** returning. 
  8780   8837     **
................................................................................
  8837   8894     ** node to replace the deleted cell.  */
  8838   8895     if( !pPage->leaf ){
  8839   8896       MemPage *pLeaf = pCur->pPage;
  8840   8897       int nCell;
  8841   8898       Pgno n;
  8842   8899       unsigned char *pTmp;
  8843   8900   
         8901  +    if( pLeaf->nFree<0 ){
         8902  +      rc = btreeComputeFreeSpace(pLeaf);
         8903  +      if( rc ) return rc;
         8904  +    }
  8844   8905       if( iCellDepth<pCur->iPage-1 ){
  8845   8906         n = pCur->apPage[iCellDepth+1]->pgno;
  8846   8907       }else{
  8847   8908         n = pCur->pPage->pgno;
  8848   8909       }
  8849   8910       pCell = findCell(pLeaf, pLeaf->nCell-1);
  8850   8911       if( pCell<&pLeaf->aData[4] ) return SQLITE_CORRUPT_BKPT;
................................................................................
  9727   9788     savedIsInit = pPage->isInit;
  9728   9789     pPage->isInit = 0;
  9729   9790     if( (rc = btreeInitPage(pPage))!=0 ){
  9730   9791       assert( rc==SQLITE_CORRUPT );  /* The only possible error from InitPage */
  9731   9792       checkAppendMsg(pCheck,
  9732   9793                      "btreeInitPage() returns error code %d", rc);
  9733   9794       goto end_of_check;
         9795  +  }
         9796  +  if( (rc = btreeComputeFreeSpace(pPage))!=0 ){
         9797  +    assert( rc==SQLITE_CORRUPT );
         9798  +    checkAppendMsg(pCheck, "free space corruption", rc);
         9799  +    goto end_of_check;
  9734   9800     }
  9735   9801     data = pPage->aData;
  9736   9802     hdr = pPage->hdrOffset;
  9737   9803   
  9738   9804     /* Set up for cell analysis */
  9739   9805     pCheck->zPfx = "On tree page %d cell %d: ";
  9740   9806     contentOffset = get2byteNotZero(&data[hdr+5]);

Changes to src/btreeInt.h.

   282    282     u8 hdrOffset;        /* 100 for page 1.  0 otherwise */
   283    283     u8 childPtrSize;     /* 0 if leaf==1.  4 if leaf==0 */
   284    284     u8 max1bytePayload;  /* min(maxLocal,127) */
   285    285     u8 nOverflow;        /* Number of overflow cell bodies in aCell[] */
   286    286     u16 maxLocal;        /* Copy of BtShared.maxLocal or BtShared.maxLeaf */
   287    287     u16 minLocal;        /* Copy of BtShared.minLocal or BtShared.minLeaf */
   288    288     u16 cellOffset;      /* Index in aData of first cell pointer */
   289         -  u16 nFree;           /* Number of free bytes on the page */
          289  +  int nFree;           /* Number of free bytes on the page. -1 for unknown */
   290    290     u16 nCell;           /* Number of cells on this page, local and ovfl */
   291    291     u16 maskPage;        /* Mask for page offset */
   292    292     u16 aiOvfl[4];       /* Insert the i-th overflow cell before the aiOvfl-th
   293    293                          ** non-overflow cell */
   294    294     u8 *apOvfl[4];       /* Pointers to the body of overflow cells */
   295    295     BtShared *pBt;       /* Pointer to BtShared that this page is part of */
   296    296     u8 *aData;           /* Pointer to disk image of the page data */

Changes to test/corrupt2.test.

    91     91     set f [open corrupt.db RDWR]
    92     92     fconfigure $f -encoding binary
    93     93     seek $f 101 start
    94     94     puts -nonewline $f "\xFF\xFF"
    95     95     close $f
    96     96   
    97     97     sqlite3 db2 corrupt.db
    98         -  catchsql "
    99         -    $::presql
   100         -    SELECT * FROM sqlite_master;
   101         -  " db2
   102         -} {1 {database disk image is malformed}}
           98  +  # Note: This test is no longer meaningful due to the deferred computation
           99  +  # of MemPage.nFree 
          100  +  catchsql {PRAGMA quick_check} db2
          101  +} {0 {{*** in database main ***
          102  +Page 1: free space corruption}}}
   103    103   
   104    104   do_test corrupt2-1.5 {
   105    105     db2 close
   106    106   
   107    107     # Corrupt the free-block list on page 1.
   108    108     forcedelete corrupt.db
   109    109     forcedelete corrupt.db-journal
................................................................................
   114    114     puts -nonewline $f "\x00\xC8"
   115    115     seek $f 200 start
   116    116     puts -nonewline $f "\x00\x00"
   117    117     puts -nonewline $f "\x10\x00"
   118    118     close $f
   119    119   
   120    120     sqlite3 db2 corrupt.db
   121         -  catchsql "
   122         -    $::presql
   123         -    SELECT * FROM sqlite_master;
   124         -  " db2
   125         -} {1 {database disk image is malformed}}
          121  +  catchsql {PRAGMA quick_check} db2
          122  +} {0 {{*** in database main ***
          123  +Page 1: free space corruption}}}
   126    124   db2 close
   127    125   
   128    126   # Corrupt a database by having 2 indices of the same name:
   129    127   do_test corrupt2-2.1 {
   130    128   
   131    129     forcedelete corrupt.db
   132    130     forcedelete corrupt.db-journal

Changes to test/corruptD.test.

   107    107   #-------------------------------------------------------------------------
   108    108   # The following tests, corruptD-1.1.*, focus on the page header field
   109    109   # containing the offset of the first free block in a page. 
   110    110   #
   111    111   do_test corruptD-1.1.1 {
   112    112     incr_change_counter
   113    113     hexio_write test.db [expr 1024+1] FFFF
   114         -  catchsql { SELECT * FROM t1 ORDER BY rowid }
   115         -} {1 {database disk image is malformed}}
          114  +  catchsql { PRAGMA quick_check }
          115  +} {0 {{*** in database main ***
          116  +Page 2: free space corruption}}}
   116    117   do_test corruptD-1.1.2 {
   117    118     incr_change_counter
   118    119     hexio_write test.db [expr 1024+1] [hexio_render_int32 1021]
   119    120     catchsql { SELECT * FROM t1 ORDER BY rowid }
   120    121   } {1 {database disk image is malformed}}
   121    122   
   122    123   #-------------------------------------------------------------------------

Changes to test/corruptK.test.

    64     64     seek $fd 30
    65     65     puts -nonewline $fd "\x18"
    66     66     close $fd
    67     67   } {}
    68     68   do_execsql_test 1.3 {
    69     69     INSERT INTO t1 VALUES(randomblob(20));
    70     70   }
           71  +
           72  +# This test no longer functions due to the deferred computation of
           73  +# MemPage.nFree.
           74  +#
           75  +if 0 {
    71     76   do_catchsql_test 1.4 {
    72     77     INSERT INTO t1 VALUES(randomblob(90));
    73     78   } {1 {database disk image is malformed}}
           79  +}
    74     80   
    75     81   #-------------------------------------------------------------------------
    76     82   reset_db
    77     83   do_execsql_test 2.1 {
    78     84     PRAGMA page_size=1024;
    79     85     PRAGMA auto_vacuum=0;
    80     86     CREATE TABLE t1(x);