From 5860a61d59e78da7d3bb24346c4791343568a5c6 Mon Sep 17 00:00:00 2001 From: drh Date: Tue, 12 Feb 2019 16:58:26 +0000 Subject: [PATCH] Further performance improvements to btreeInitPage(). FossilOrigin-Name: 93ae382e97c23c90312739481e47ef7f9bc475a8382c063a2de2986c950c0aec --- manifest | 12 +++--- manifest.uuid | 2 +- src/btree.c | 105 +++++++++++++++++++++++++------------------------- 3 files changed, 60 insertions(+), 59 deletions(-) diff --git a/manifest b/manifest index 54adae474f..a6491a6926 100644 --- a/manifest +++ b/manifest @@ -1,5 +1,5 @@ -C Increase\sthe\sversion\snumber\sto\s3.28.0\sfor\sthe\snext\srelease\scycle. -D 2019-02-12T15:51:36.707 +C Further\sperformance\simprovements\sto\sbtreeInitPage(). +D 2019-02-12T16:58:26.325 F .fossil-settings/empty-dirs dbb81e8fc0401ac46a1491ab34a7f2c7c0452f2f06b54ebb845d024ca8283ef1 F .fossil-settings/ignore-glob 35175cdfcf539b2318cb04a9901442804be81cd677d8b889fcc9149c21f239ea F Makefile.in 178d8eb6840771149cee40b322d1b3be30d330198c522c903c1b66fb5a1bfca4 @@ -455,7 +455,7 @@ F src/auth.c 0fac71038875693a937e506bceb492c5f136dd7b1249fbd4ae70b4e8da14f9df F src/backup.c 78d3cecfbe28230a3a9a1793e2ead609f469be43e8f486ca996006be551857ab F src/bitvec.c 17ea48eff8ba979f1f5b04cc484c7bb2be632f33 F src/btmutex.c 8acc2f464ee76324bf13310df5692a262b801808984c1b79defb2503bbafadb6 -F src/btree.c 7457f7813873877041ec7e04d76a041c81831704a73419882fbe1c222ce6a68c +F src/btree.c 1336cc1670ec9ab93c097ae0c087480f501fd9c7157be0457b2b04e67a06a377 F src/btree.h 63b94fb38ce571c15eb6a3661815561b501d23d5948b2d1e951fbd7a2d04e8d3 F src/btreeInt.h 6111c15868b90669f79081039d19e7ea8674013f907710baa3c814dc3f8bfd3f F src/build.c b0a9ee5b551afbc8357a68eb30693973300daf845c8c0e564f672d9b3fdeec56 @@ -1804,7 +1804,7 @@ F vsixtest/vsixtest.tcl 6a9a6ab600c25a91a7acc6293828957a386a8a93 F vsixtest/vsixtest.vcxproj.data 2ed517e100c66dc455b492e1a33350c1b20fbcdc F vsixtest/vsixtest.vcxproj.filters 37e51ffedcdb064aad6ff33b6148725226cd608e F vsixtest/vsixtest_TemporaryKey.pfx e5b1b036facdb453873e7084e1cae9102ccc67a0 -P 9bd92afd0cb0a958441e861c7006b77027125b1ceea0868958ec948b6b3c7bc9 -R f84ea4fd0e9bef4a6942eebd8ef1803d +P 6eb38c59a81d27b7c1f3edad84b27a1114df6f1607282b2be1b5de9c7decc512 +R cc90c00a72cee7c141819cd12b6430c9 U drh -Z 98b1f2d1faa7ac033f04d7996aa601e5 +Z ba80ee88206970e9c79aaddf47903f84 diff --git a/manifest.uuid b/manifest.uuid index 0d1cd90740..ed488bb4f5 100644 --- a/manifest.uuid +++ b/manifest.uuid @@ -1 +1 @@ -6eb38c59a81d27b7c1f3edad84b27a1114df6f1607282b2be1b5de9c7decc512 \ No newline at end of file +93ae382e97c23c90312739481e47ef7f9bc475a8382c063a2de2986c950c0aec \ No newline at end of file diff --git a/src/btree.c b/src/btree.c index 4cbad04e4e..fbfc67a796 100644 --- a/src/btree.c +++ b/src/btree.c @@ -1667,7 +1667,7 @@ static int allocateSpace(MemPage *pPage, int nByte, int *pIdx){ /* Allocate memory from the gap in between the cell pointer array - ** and the cell content area. The btreeInitPage() call has already + ** and the cell content area. The btreeComputeFreeSpace() call has already ** validated the freelist. Given that the freelist is valid, there ** is no way that the allocation can extend off the end of the page. ** The assert() below verifies the previous sentence. @@ -1686,7 +1686,7 @@ static int allocateSpace(MemPage *pPage, int nByte, int *pIdx){ ** ** Adjacent freeblocks are coalesced. ** -** Note that even though the freeblock list was checked by btreeInitPage(), +** Even though the freeblock list was checked by btreeComputeFreeSpace(), ** that routine will not detect overlap between cells or freeblocks. Nor ** does it detect cells or freeblocks that encrouch into the reserved bytes ** at the end of the page. So do additional corruption checks inside this @@ -1929,6 +1929,42 @@ static int btreeComputeFreeSpace(MemPage *pPage){ return SQLITE_OK; } +/* +** Do additional sanity check after btreeInitPage() if +** PRAGMA cell_size_check=ON +*/ +static SQLITE_NOINLINE int btreeCellSizeCheck(MemPage *pPage){ + int iCellFirst; /* First allowable cell or freeblock offset */ + int iCellLast; /* Last possible cell or freeblock offset */ + int i; /* Index into the cell pointer array */ + int sz; /* Size of a cell */ + int pc; /* Address of a freeblock within pPage->aData[] */ + u8 *data; /* Equal to pPage->aData */ + int usableSize; /* Maximum usable space on the page */ + int cellOffset; /* Start of cell content area */ + + iCellFirst = pPage->cellOffset + 2*pPage->nCell; + usableSize = pPage->pBt->usableSize; + iCellLast = usableSize - 4; + data = pPage->aData; + cellOffset = pPage->cellOffset; + 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); + } + } + return SQLITE_OK; +} + /* ** Initialize the auxiliary information for a disk block. ** @@ -1939,14 +1975,8 @@ static int btreeComputeFreeSpace(MemPage *pPage){ ** 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 ); @@ -1957,24 +1987,22 @@ static int btreeInitPage(MemPage *pPage){ assert( pPage->isInit==0 ); pBt = pPage->pBt; - hdr = pPage->hdrOffset; - data = pPage->aData; + data = pPage->aData + pPage->hdrOffset; /* EVIDENCE-OF: R-28594-02890 The one-byte flag at offset 0 indicating ** the b-tree page type. */ - if( decodeFlags(pPage, data[hdr]) ){ + if( decodeFlags(pPage, data[0]) ){ 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]; + pPage->cellOffset = pPage->hdrOffset + 8 + pPage->childPtrSize; + pPage->aCellIdx = data + pPage->childPtrSize + 8; + pPage->aDataEnd = pPage->aData + pBt->usableSize; + pPage->aDataOfst = pPage->aData + 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]); + pPage->nCell = get2byte(&data[3]); if( pPage->nCell>MX_CELL(pBt) ){ /* To many cells for a single page. The page must be corrupt */ return SQLITE_CORRUPT_PAGE(pPage); @@ -1985,40 +2013,13 @@ static int btreeInitPage(MemPage *pPage){ ** 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 + || get2byteNotZero(&data[5])==pBt->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; + if( pBt->db->flags & SQLITE_CellSizeCk ){ + return btreeCellSizeCheck(pPage); + } return SQLITE_OK; } @@ -9930,9 +9931,9 @@ static int checkTreePage( i = get2byte(&data[hdr+1]); while( i>0 ){ int size, j; - assert( (u32)i<=usableSize-4 ); /* Enforced by btreeInitPage() */ + assert( (u32)i<=usableSize-4 ); /* Enforced by btreeComputeFreeSpace() */ size = get2byte(&data[i+2]); - assert( (u32)(i+size)<=usableSize ); /* Enforced by btreeInitPage() */ + assert( (u32)(i+size)<=usableSize ); /* due to btreeComputeFreeSpace() */ btreeHeapInsert(heap, (((u32)i)<<16)|(i+size-1)); /* EVIDENCE-OF: R-58208-19414 The first 2 bytes of a freeblock are a ** big-endian integer which is the offset in the b-tree page of the next @@ -9941,8 +9942,8 @@ static int checkTreePage( j = get2byte(&data[i]); /* EVIDENCE-OF: R-06866-39125 Freeblocks are always connected in order of ** increasing offset. */ - assert( j==0 || j>i+size ); /* Enforced by btreeInitPage() */ - assert( (u32)j<=usableSize-4 ); /* Enforced by btreeInitPage() */ + assert( j==0 || j>i+size ); /* Enforced by btreeComputeFreeSpace() */ + assert( (u32)j<=usableSize-4 ); /* Enforced by btreeComputeFreeSpace() */ i = j; } /* Analyze the min-heap looking for overlap between cells and/or -- 2.47.2