/ Check-in [93ae382e]
Login

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

Overview
Comment:Further performance improvements to btreeInitPage().
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA3-256:93ae382e97c23c90312739481e47ef7f9bc475a8382c063a2de2986c950c0aec
User & Date: drh 2019-02-12 16:58:26
Context
2019-02-12
21:04
Enhancement the progress callback mechanism so that the progress callback is always invoked at least once at the end of a prepared statement if the opcode count has been exceeded. This makes the progress callback more effective at limiting run times. This check-in also includes and unrelated performance enhancement to OP_Column. check-in: 68cce272 user: drh tags: trunk
16:58
Further performance improvements to btreeInitPage(). check-in: 93ae382e user: drh tags: trunk
15:51
Increase the version number to 3.28.0 for the next release cycle. check-in: 6eb38c59 user: drh tags: trunk
Changes
Hide Diffs Side-by-Side Diffs Ignore Whitespace Patch

Changes to src/btree.c.

  1663   1663       if( rc ) return rc;
  1664   1664       top = get2byteNotZero(&data[hdr+5]);
  1665   1665       assert( gap+2+nByte<=top );
  1666   1666     }
  1667   1667   
  1668   1668   
  1669   1669     /* Allocate memory from the gap in between the cell pointer array
  1670         -  ** and the cell content area.  The btreeInitPage() call has already
         1670  +  ** and the cell content area.  The btreeComputeFreeSpace() call has already
  1671   1671     ** validated the freelist.  Given that the freelist is valid, there
  1672   1672     ** is no way that the allocation can extend off the end of the page.
  1673   1673     ** The assert() below verifies the previous sentence.
  1674   1674     */
  1675   1675     top -= nByte;
  1676   1676     put2byte(&data[hdr+5], top);
  1677   1677     assert( top+nByte <= (int)pPage->pBt->usableSize );
................................................................................
  1682   1682   /*
  1683   1683   ** Return a section of the pPage->aData to the freelist.
  1684   1684   ** The first byte of the new free block is pPage->aData[iStart]
  1685   1685   ** and the size of the block is iSize bytes.
  1686   1686   **
  1687   1687   ** Adjacent freeblocks are coalesced.
  1688   1688   **
  1689         -** Note that even though the freeblock list was checked by btreeInitPage(),
         1689  +** Even though the freeblock list was checked by btreeComputeFreeSpace(),
  1690   1690   ** that routine will not detect overlap between cells or freeblocks.  Nor
  1691   1691   ** does it detect cells or freeblocks that encrouch into the reserved bytes
  1692   1692   ** at the end of the page.  So do additional corruption checks inside this
  1693   1693   ** routine and return SQLITE_CORRUPT if any problems are found.
  1694   1694   */
  1695   1695   static int freeSpace(MemPage *pPage, u16 iStart, u16 iSize){
  1696   1696     u16 iPtr;                             /* Address of ptr to next freeblock */
................................................................................
  1924   1924     */
  1925   1925     if( nFree>usableSize ){
  1926   1926       return SQLITE_CORRUPT_PAGE(pPage);
  1927   1927     }
  1928   1928     pPage->nFree = (u16)(nFree - iCellFirst);
  1929   1929     return SQLITE_OK;
  1930   1930   }
         1931  +
         1932  +/*
         1933  +** Do additional sanity check after btreeInitPage() if
         1934  +** PRAGMA cell_size_check=ON 
         1935  +*/
         1936  +static SQLITE_NOINLINE int btreeCellSizeCheck(MemPage *pPage){
         1937  +  int iCellFirst;    /* First allowable cell or freeblock offset */
         1938  +  int iCellLast;     /* Last possible cell or freeblock offset */
         1939  +  int i;             /* Index into the cell pointer array */
         1940  +  int sz;            /* Size of a cell */
         1941  +  int pc;            /* Address of a freeblock within pPage->aData[] */
         1942  +  u8 *data;          /* Equal to pPage->aData */
         1943  +  int usableSize;    /* Maximum usable space on the page */
         1944  +  int cellOffset;    /* Start of cell content area */
         1945  +
         1946  +  iCellFirst = pPage->cellOffset + 2*pPage->nCell;
         1947  +  usableSize = pPage->pBt->usableSize;
         1948  +  iCellLast = usableSize - 4;
         1949  +  data = pPage->aData;
         1950  +  cellOffset = pPage->cellOffset;
         1951  +  if( !pPage->leaf ) iCellLast--;
         1952  +  for(i=0; i<pPage->nCell; i++){
         1953  +    pc = get2byteAligned(&data[cellOffset+i*2]);
         1954  +    testcase( pc==iCellFirst );
         1955  +    testcase( pc==iCellLast );
         1956  +    if( pc<iCellFirst || pc>iCellLast ){
         1957  +      return SQLITE_CORRUPT_PAGE(pPage);
         1958  +    }
         1959  +    sz = pPage->xCellSize(pPage, &data[pc]);
         1960  +    testcase( pc+sz==usableSize );
         1961  +    if( pc+sz>usableSize ){
         1962  +      return SQLITE_CORRUPT_PAGE(pPage);
         1963  +    }
         1964  +  }
         1965  +  return SQLITE_OK;
         1966  +}
  1931   1967   
  1932   1968   /*
  1933   1969   ** Initialize the auxiliary information for a disk block.
  1934   1970   **
  1935   1971   ** Return SQLITE_OK on success.  If we see that the page does
  1936   1972   ** not contain a well-formed database page, then return 
  1937   1973   ** SQLITE_CORRUPT.  Note that a return of SQLITE_OK does not
  1938   1974   ** guarantee that the page is well-formed.  It only shows that
  1939   1975   ** we failed to detect any corruption.
  1940   1976   */
  1941   1977   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   1978     u8 *data;          /* Equal to pPage->aData */
  1945   1979     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   1980   
  1951   1981     assert( pPage->pBt!=0 );
  1952   1982     assert( pPage->pBt->db!=0 );
  1953   1983     assert( sqlite3_mutex_held(pPage->pBt->mutex) );
  1954   1984     assert( pPage->pgno==sqlite3PagerPagenumber(pPage->pDbPage) );
  1955   1985     assert( pPage == sqlite3PagerGetExtra(pPage->pDbPage) );
  1956   1986     assert( pPage->aData == sqlite3PagerGetData(pPage->pDbPage) );
  1957   1987     assert( pPage->isInit==0 );
  1958   1988   
  1959   1989     pBt = pPage->pBt;
  1960         -  hdr = pPage->hdrOffset;
  1961         -  data = pPage->aData;
         1990  +  data = pPage->aData + pPage->hdrOffset;
  1962   1991     /* EVIDENCE-OF: R-28594-02890 The one-byte flag at offset 0 indicating
  1963   1992     ** the b-tree page type. */
  1964         -  if( decodeFlags(pPage, data[hdr]) ){
         1993  +  if( decodeFlags(pPage, data[0]) ){
  1965   1994       return SQLITE_CORRUPT_PAGE(pPage);
  1966   1995     }
  1967   1996     assert( pBt->pageSize>=512 && pBt->pageSize<=65536 );
  1968   1997     pPage->maskPage = (u16)(pBt->pageSize - 1);
  1969   1998     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];
         1999  +  pPage->cellOffset = pPage->hdrOffset + 8 + pPage->childPtrSize;
         2000  +  pPage->aCellIdx = data + pPage->childPtrSize + 8;
         2001  +  pPage->aDataEnd = pPage->aData + pBt->usableSize;
         2002  +  pPage->aDataOfst = pPage->aData + pPage->childPtrSize;
  1975   2003     /* EVIDENCE-OF: R-37002-32774 The two-byte integer at offset 3 gives the
  1976   2004     ** number of cells on the page. */
  1977         -  pPage->nCell = get2byte(&data[hdr+3]);
         2005  +  pPage->nCell = get2byte(&data[3]);
  1978   2006     if( pPage->nCell>MX_CELL(pBt) ){
  1979   2007       /* To many cells for a single page.  The page must be corrupt */
  1980   2008       return SQLITE_CORRUPT_PAGE(pPage);
  1981   2009     }
  1982   2010     testcase( pPage->nCell==MX_CELL(pBt) );
  1983   2011     /* EVIDENCE-OF: R-24089-57979 If a page contains no cells (which is only
  1984   2012     ** possible for a root page of a table that contains no rows) then the
  1985   2013     ** offset to the cell content area will equal the page size minus the
  1986   2014     ** bytes of reserved space. */
  1987   2015     assert( pPage->nCell>0
  1988         -       || get2byteNotZero(&data[hdr+5])==usableSize
         2016  +       || get2byteNotZero(&data[5])==pBt->usableSize
  1989   2017          || 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   2018     pPage->nFree = -1;  /* Indicate that this value is yet uncomputed */
  2021   2019     pPage->isInit = 1;
         2020  +  if( pBt->db->flags & SQLITE_CellSizeCk ){
         2021  +    return btreeCellSizeCheck(pPage);
         2022  +  }
  2022   2023     return SQLITE_OK;
  2023   2024   }
  2024   2025   
  2025   2026   /*
  2026   2027   ** Set up a raw page so that it looks like a database page holding
  2027   2028   ** no entries.
  2028   2029   */
................................................................................
  9926   9927       ** EVIDENCE-OF: R-20690-50594 The second field of the b-tree page header
  9927   9928       ** is the offset of the first freeblock, or zero if there are no
  9928   9929       ** freeblocks on the page. 
  9929   9930       */
  9930   9931       i = get2byte(&data[hdr+1]);
  9931   9932       while( i>0 ){
  9932   9933         int size, j;
  9933         -      assert( (u32)i<=usableSize-4 );     /* Enforced by btreeInitPage() */
         9934  +      assert( (u32)i<=usableSize-4 ); /* Enforced by btreeComputeFreeSpace() */
  9934   9935         size = get2byte(&data[i+2]);
  9935         -      assert( (u32)(i+size)<=usableSize );  /* Enforced by btreeInitPage() */
         9936  +      assert( (u32)(i+size)<=usableSize ); /* due to btreeComputeFreeSpace() */
  9936   9937         btreeHeapInsert(heap, (((u32)i)<<16)|(i+size-1));
  9937   9938         /* EVIDENCE-OF: R-58208-19414 The first 2 bytes of a freeblock are a
  9938   9939         ** big-endian integer which is the offset in the b-tree page of the next
  9939   9940         ** freeblock in the chain, or zero if the freeblock is the last on the
  9940   9941         ** chain. */
  9941   9942         j = get2byte(&data[i]);
  9942   9943         /* EVIDENCE-OF: R-06866-39125 Freeblocks are always connected in order of
  9943   9944         ** increasing offset. */
  9944         -      assert( j==0 || j>i+size );  /* Enforced by btreeInitPage() */
  9945         -      assert( (u32)j<=usableSize-4 );   /* Enforced by btreeInitPage() */
         9945  +      assert( j==0 || j>i+size );     /* Enforced by btreeComputeFreeSpace() */
         9946  +      assert( (u32)j<=usableSize-4 ); /* Enforced by btreeComputeFreeSpace() */
  9946   9947         i = j;
  9947   9948       }
  9948   9949       /* Analyze the min-heap looking for overlap between cells and/or 
  9949   9950       ** freeblocks, and counting the number of untracked bytes in nFrag.
  9950   9951       ** 
  9951   9952       ** Each min-heap entry is of the form:    (start_address<<16)|end_address.
  9952   9953       ** There is an implied first entry the covers the page header, the cell