/ Check-in [1d43ee40]
Login

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

Overview
Comment:Defer computing the MemPage.nFree value of an in-memory btree page until it is actually needed, since for many pages it is never needed. This checkin works sufficiently to prove the concept, but still has issues with exception handling.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | deferred-free-space
Files: files | file ages | folders
SHA3-256:1d43ee4000b71f5c6d49244dee96358c567f09ba3451b9d22895a796d3f61ad6
User & Date: drh 2019-02-09 21:06:40
Context
2019-02-09
22:33
Fix a page-cache reference leak in the btree balancer when there is a corrupt database. check-in: 92858991 user: drh tags: deferred-free-space
21:06
Defer computing the MemPage.nFree value of an in-memory btree page until it is actually needed, since for many pages it is never needed. This checkin works sufficiently to prove the concept, but still has issues with exception handling. check-in: 1d43ee40 user: drh tags: deferred-free-space
19:23
Change a few assert() statements in fts3 that might fail if the database is corrupt. check-in: db74a56a user: dan tags: trunk
Changes
Hide Diffs Side-by-Side Diffs Ignore Whitespace Patch

Changes to src/btree.c.

  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;
................................................................................
  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  +  if( pPage->nFree<0 ){
         7229  +    rc = btreeComputeFreeSpace(pPage);
         7230  +    if( rc ) return rc;
         7231  +  }
         7232  +  if( pParent->nFree<0 ){
         7233  +    rc = btreeComputeFreeSpace(pParent);
         7234  +    if( rc ) return rc;
         7235  +  }
         7236  +
  7192   7237   
  7193   7238     /* Allocate a new page. This page will become the right-sibling of 
  7194   7239     ** pPage. Make the parent page writable, so that the new divider cell
  7195   7240     ** may be inserted. If both these operations are successful, proceed.
  7196   7241     */
  7197   7242     rc = allocateBtreePage(pBt, &pNew, &pgnoNew, 0, 0);
  7198   7243   
................................................................................
  7462   7507     */
  7463   7508     assert( pParent->nOverflow==0 || pParent->nOverflow==1 );
  7464   7509     assert( pParent->nOverflow==0 || pParent->aiOvfl[0]==iParentIdx );
  7465   7510   
  7466   7511     if( !aOvflSpace ){
  7467   7512       return SQLITE_NOMEM_BKPT;
  7468   7513     }
         7514  +  if( pParent->nFree<0 ){
         7515  +    rc = btreeComputeFreeSpace(pParent);
         7516  +    if( rc ) return rc;
         7517  +  }
  7469   7518   
  7470   7519     /* Find the sibling pages to balance. Also locate the cells in pParent 
  7471   7520     ** that divide the siblings. An attempt is made to find NN siblings on 
  7472   7521     ** either side of pPage. More siblings are taken from one side, however, 
  7473   7522     ** if there are fewer than NN siblings on the other side. If pParent
  7474   7523     ** has NB or fewer children then all children of pParent are taken.  
  7475   7524     **
................................................................................
  7497   7546       pRight = &pParent->aData[pParent->hdrOffset+8];
  7498   7547     }else{
  7499   7548       pRight = findCell(pParent, i+nxDiv-pParent->nOverflow);
  7500   7549     }
  7501   7550     pgno = get4byte(pRight);
  7502   7551     while( 1 ){
  7503   7552       rc = getAndInitPage(pBt, pgno, &apOld[i], 0, 0);
         7553  +    if( rc==0 && apOld[i]->nFree<0 ){
         7554  +      rc = btreeComputeFreeSpace(apOld[i]);
         7555  +    }
  7504   7556       if( rc ){
  7505   7557         memset(apOld, 0, (i+1)*sizeof(MemPage*));
  7506   7558         goto balance_cleanup;
  7507   7559       }
  7508   7560       nMaxCells += 1+apOld[i]->nCell+apOld[i]->nOverflow;
  7509   7561       if( (i--)==0 ) break;
  7510   7562   
................................................................................
  7700   7752       b.apEnd[k] = p->aDataEnd;
  7701   7753       b.ixNx[k] = cntOld[i];
  7702   7754       if( !leafData ){
  7703   7755         k++;
  7704   7756         b.apEnd[k] = pParent->aDataEnd;
  7705   7757         b.ixNx[k] = cntOld[i]+1;
  7706   7758       }
         7759  +    assert( p->nFree>=0 );
  7707   7760       szNew[i] = usableSpace - p->nFree;
  7708   7761       for(j=0; j<p->nOverflow; j++){
  7709   7762         szNew[i] += 2 + p->xCellSize(p, p->apOvfl[j]);
  7710   7763       }
  7711   7764       cntNew[i] = cntOld[i];
  7712   7765     }
  7713   7766     k = nOld;
................................................................................
  8243   8296     VVA_ONLY( int balance_quick_called = 0 );
  8244   8297     VVA_ONLY( int balance_deeper_called = 0 );
  8245   8298   
  8246   8299     do {
  8247   8300       int iPage = pCur->iPage;
  8248   8301       MemPage *pPage = pCur->pPage;
  8249   8302   
         8303  +    if( pPage->nFree<0 ){
         8304  +      rc = btreeComputeFreeSpace(pPage);
         8305  +      if( rc ) break;
         8306  +    }
  8250   8307       if( iPage==0 ){
  8251   8308         if( pPage->nOverflow ){
  8252   8309           /* The root page of the b-tree is overfull. In this case call the
  8253   8310           ** balance_deeper() function to create a new child for the root-page
  8254   8311           ** and copy the current contents of the root-page to it. The
  8255   8312           ** next iteration of the do-loop will balance the child page.
  8256   8313           */ 
................................................................................
  8617   8674   
  8618   8675     }
  8619   8676     assert( pCur->eState==CURSOR_VALID || (pCur->eState==CURSOR_INVALID && loc) );
  8620   8677   
  8621   8678     pPage = pCur->pPage;
  8622   8679     assert( pPage->intKey || pX->nKey>=0 );
  8623   8680     assert( pPage->leaf || !pPage->intKey );
         8681  +  if( pPage->nFree<0 ){
         8682  +    rc = btreeComputeFreeSpace(pPage);
         8683  +    if( rc ) return rc;
         8684  +  }
  8624   8685   
  8625   8686     TRACE(("INSERT: table=%d nkey=%lld ndata=%d page=%d %s\n",
  8626   8687             pCur->pgnoRoot, pX->nKey, pX->nData, pPage->pgno,
  8627   8688             loc==0 ? "overwrite" : "new entry"));
  8628   8689     assert( pPage->isInit );
  8629   8690     newCell = pBt->pTmpSpace;
  8630   8691     assert( newCell!=0 );
................................................................................
  8767   8828     assert( pCur->eState==CURSOR_VALID );
  8768   8829     assert( (flags & ~(BTREE_SAVEPOSITION | BTREE_AUXDELETE))==0 );
  8769   8830   
  8770   8831     iCellDepth = pCur->iPage;
  8771   8832     iCellIdx = pCur->ix;
  8772   8833     pPage = pCur->pPage;
  8773   8834     pCell = findCell(pPage, iCellIdx);
         8835  +  if( pPage->nFree<0 && btreeComputeFreeSpace(pPage) ) return SQLITE_CORRUPT;
  8774   8836   
  8775   8837     /* If the bPreserve flag is set to true, then the cursor position must
  8776   8838     ** be preserved following this delete operation. If the current delete
  8777   8839     ** will cause a b-tree rebalance, then this is done by saving the cursor
  8778   8840     ** key and leaving the cursor in CURSOR_REQUIRESEEK state before 
  8779   8841     ** returning. 
  8780   8842     **
................................................................................
  8837   8899     ** node to replace the deleted cell.  */
  8838   8900     if( !pPage->leaf ){
  8839   8901       MemPage *pLeaf = pCur->pPage;
  8840   8902       int nCell;
  8841   8903       Pgno n;
  8842   8904       unsigned char *pTmp;
  8843   8905   
         8906  +    if( pLeaf->nFree<0 ){
         8907  +      rc = btreeComputeFreeSpace(pLeaf);
         8908  +      if( rc ) return rc;
         8909  +    }
  8844   8910       if( iCellDepth<pCur->iPage-1 ){
  8845   8911         n = pCur->apPage[iCellDepth+1]->pgno;
  8846   8912       }else{
  8847   8913         n = pCur->pPage->pgno;
  8848   8914       }
  8849   8915       pCell = findCell(pLeaf, pLeaf->nCell-1);
  8850   8916       if( pCell<&pLeaf->aData[4] ) return SQLITE_CORRUPT_BKPT;
................................................................................
  9727   9793     savedIsInit = pPage->isInit;
  9728   9794     pPage->isInit = 0;
  9729   9795     if( (rc = btreeInitPage(pPage))!=0 ){
  9730   9796       assert( rc==SQLITE_CORRUPT );  /* The only possible error from InitPage */
  9731   9797       checkAppendMsg(pCheck,
  9732   9798                      "btreeInitPage() returns error code %d", rc);
  9733   9799       goto end_of_check;
         9800  +  }
         9801  +  if( (rc = btreeComputeFreeSpace(pPage))!=0 ){
         9802  +    assert( rc==SQLITE_CORRUPT );
         9803  +    checkAppendMsg(pCheck, "free space corruption", rc);
         9804  +    goto end_of_check;
  9734   9805     }
  9735   9806     data = pPage->aData;
  9736   9807     hdr = pPage->hdrOffset;
  9737   9808   
  9738   9809     /* Set up for cell analysis */
  9739   9810     pCheck->zPfx = "On tree page %d cell %d: ";
  9740   9811     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 */
   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 */