Many hyperlinks are disabled.
Use anonymous login
to enable hyperlinks.
Overview
Comment: | Make cellSizePtr() a method on the MemPage object, with alternative implementations depending on the page type. This results is a small performance improvement and size reduction. |
---|---|
Downloads: | Tarball | ZIP archive |
Timelines: | family | ancestors | descendants | both | trunk |
Files: | files | file ages | folders |
SHA1: |
02f7e9d7d7b93d0b6bbd6cc0d0359b3b |
User & Date: | drh 2015-06-19 15:07:14.566 |
Context
2015-06-19
| ||
17:19 | Add the MemPage.xParseCell method and provide various implementations (variations on the former btreeParseCellPtr()) depending on the page type. (check-in: 41d03d883c user: drh tags: trunk) | |
15:07 | Make cellSizePtr() a method on the MemPage object, with alternative implementations depending on the page type. This results is a small performance improvement and size reduction. (check-in: 02f7e9d7d7 user: drh tags: trunk) | |
2015-06-18
| ||
15:26 | Further #ifdef changes in speedtest1.c in order to support SQLite back to version 3.3.9 and perhaps even earlier. (check-in: 9246eca54a user: drh tags: trunk) | |
Changes
Changes to src/btree.c.
︙ | ︙ | |||
1061 1062 1063 1064 1065 1066 1067 1068 1069 1070 1071 1072 1073 1074 1075 1076 1077 1078 1079 1080 1081 1082 | } /* ** Compute the total number of bytes that a Cell needs in the cell ** data area of the btree-page. The return number includes the cell ** data header and the local payload, but not any overflow page or ** the space used by the cell pointer. */ static u16 cellSizePtr(MemPage *pPage, u8 *pCell){ u8 *pIter = pCell + pPage->childPtrSize; /* For looping over bytes of pCell */ u8 *pEnd; /* End mark for a varint */ u32 nSize; /* Size value to return */ #ifdef SQLITE_DEBUG /* The value returned by this function should always be the same as ** the (CellInfo.nSize) value found by doing a full parse of the ** cell. If SQLITE_DEBUG is defined, an assert() at the bottom of ** this function verifies that this invariant is not violated. */ CellInfo debuginfo; btreeParseCellPtr(pPage, pCell, &debuginfo); #endif | > > > > > | < < < < < | 1061 1062 1063 1064 1065 1066 1067 1068 1069 1070 1071 1072 1073 1074 1075 1076 1077 1078 1079 1080 1081 1082 1083 1084 1085 1086 1087 1088 1089 1090 1091 1092 1093 1094 1095 | } /* ** Compute the total number of bytes that a Cell needs in the cell ** data area of the btree-page. The return number includes the cell ** data header and the local payload, but not any overflow page or ** the space used by the cell pointer. ** ** The first implementation, cellSizePtr(), handles pages that contain ** payload, which is to say all index pages and left table pages. The ** second cellSizePtrNoPayload() implemention is a high-speed version ** for pages that contain no payload - internal table pages. */ static u16 cellSizePtr(MemPage *pPage, u8 *pCell){ u8 *pIter = pCell + pPage->childPtrSize; /* For looping over bytes of pCell */ u8 *pEnd; /* End mark for a varint */ u32 nSize; /* Size value to return */ #ifdef SQLITE_DEBUG /* The value returned by this function should always be the same as ** the (CellInfo.nSize) value found by doing a full parse of the ** cell. If SQLITE_DEBUG is defined, an assert() at the bottom of ** this function verifies that this invariant is not violated. */ CellInfo debuginfo; btreeParseCellPtr(pPage, pCell, &debuginfo); #endif assert( pPage->noPayload==0 ); nSize = *pIter; if( nSize>=0x80 ){ pEnd = &pIter[9]; nSize &= 0x7f; do{ nSize = (nSize<<7) | (*++pIter & 0x7f); }while( *(pIter)>=0x80 && pIter<pEnd ); |
︙ | ︙ | |||
1116 1117 1118 1119 1120 1121 1122 1123 1124 1125 1126 1127 | nSize = minLocal; } nSize += 4 + (u16)(pIter - pCell); } assert( nSize==debuginfo.nSize || CORRUPT_DB ); return (u16)nSize; } #ifdef SQLITE_DEBUG /* This variation on cellSizePtr() is used inside of assert() statements ** only. */ static u16 cellSize(MemPage *pPage, int iCell){ | > > > > > > > > > > > > > > > > > > > > | | 1116 1117 1118 1119 1120 1121 1122 1123 1124 1125 1126 1127 1128 1129 1130 1131 1132 1133 1134 1135 1136 1137 1138 1139 1140 1141 1142 1143 1144 1145 1146 1147 1148 1149 1150 1151 1152 1153 1154 1155 | nSize = minLocal; } nSize += 4 + (u16)(pIter - pCell); } assert( nSize==debuginfo.nSize || CORRUPT_DB ); return (u16)nSize; } static u16 cellSizePtrNoPayload(MemPage *pPage, u8 *pCell){ u8 *pIter = pCell + 4; /* For looping over bytes of pCell */ u8 *pEnd; /* End mark for a varint */ #ifdef SQLITE_DEBUG /* The value returned by this function should always be the same as ** the (CellInfo.nSize) value found by doing a full parse of the ** cell. If SQLITE_DEBUG is defined, an assert() at the bottom of ** this function verifies that this invariant is not violated. */ CellInfo debuginfo; btreeParseCellPtr(pPage, pCell, &debuginfo); #endif assert( pPage->childPtrSize==4 ); pEnd = pIter + 9; while( (*pIter++)&0x80 && pIter<pEnd ); assert( debuginfo.nSize==(u16)(pIter - pCell) || CORRUPT_DB ); return (u16)(pIter - pCell); } #ifdef SQLITE_DEBUG /* This variation on cellSizePtr() is used inside of assert() statements ** only. */ static u16 cellSize(MemPage *pPage, int iCell){ return pPage->xCellSize(pPage, findCell(pPage, iCell)); } #endif #ifndef SQLITE_OMIT_AUTOVACUUM /* ** If the cell pCell, part of page pPage contains a pointer ** to an overflow page, insert an entry into the pointer-map |
︙ | ︙ | |||
1199 1200 1201 1202 1203 1204 1205 | /* These conditions have already been verified in btreeInitPage() ** if PRAGMA cell_size_check=ON. */ if( pc<iCellFirst || pc>iCellLast ){ return SQLITE_CORRUPT_BKPT; } assert( pc>=iCellFirst && pc<=iCellLast ); | | | 1219 1220 1221 1222 1223 1224 1225 1226 1227 1228 1229 1230 1231 1232 1233 | /* These conditions have already been verified in btreeInitPage() ** if PRAGMA cell_size_check=ON. */ if( pc<iCellFirst || pc>iCellLast ){ return SQLITE_CORRUPT_BKPT; } assert( pc>=iCellFirst && pc<=iCellLast ); size = pPage->xCellSize(pPage, &src[pc]); cbrk -= size; if( cbrk<iCellFirst || pc+size>usableSize ){ return SQLITE_CORRUPT_BKPT; } assert( cbrk+size<=usableSize && cbrk>=iCellFirst ); testcase( cbrk+size==usableSize ); testcase( pc+size==usableSize ); |
︙ | ︙ | |||
1503 1504 1505 1506 1507 1508 1509 1510 1511 1512 1513 1514 1515 1516 1517 1518 | BtShared *pBt; /* A copy of pPage->pBt */ assert( pPage->hdrOffset==(pPage->pgno==1 ? 100 : 0) ); assert( sqlite3_mutex_held(pPage->pBt->mutex) ); pPage->leaf = (u8)(flagByte>>3); assert( PTF_LEAF == 1<<3 ); flagByte &= ~PTF_LEAF; pPage->childPtrSize = 4-4*pPage->leaf; pBt = pPage->pBt; if( flagByte==(PTF_LEAFDATA | PTF_INTKEY) ){ /* EVIDENCE-OF: R-03640-13415 A value of 5 means the page is an interior ** table b-tree page. */ assert( (PTF_LEAFDATA|PTF_INTKEY)==5 ); /* EVIDENCE-OF: R-20501-61796 A value of 13 means the page is a leaf ** table b-tree page. */ assert( (PTF_LEAFDATA|PTF_INTKEY|PTF_LEAF)==13 ); pPage->intKey = 1; | > > | | > > > > > | 1523 1524 1525 1526 1527 1528 1529 1530 1531 1532 1533 1534 1535 1536 1537 1538 1539 1540 1541 1542 1543 1544 1545 1546 1547 1548 1549 1550 1551 1552 1553 1554 | BtShared *pBt; /* A copy of pPage->pBt */ assert( pPage->hdrOffset==(pPage->pgno==1 ? 100 : 0) ); assert( sqlite3_mutex_held(pPage->pBt->mutex) ); pPage->leaf = (u8)(flagByte>>3); assert( PTF_LEAF == 1<<3 ); flagByte &= ~PTF_LEAF; pPage->childPtrSize = 4-4*pPage->leaf; pPage->xCellSize = cellSizePtr; pBt = pPage->pBt; if( flagByte==(PTF_LEAFDATA | PTF_INTKEY) ){ /* EVIDENCE-OF: R-03640-13415 A value of 5 means the page is an interior ** table b-tree page. */ assert( (PTF_LEAFDATA|PTF_INTKEY)==5 ); /* EVIDENCE-OF: R-20501-61796 A value of 13 means the page is a leaf ** table b-tree page. */ assert( (PTF_LEAFDATA|PTF_INTKEY|PTF_LEAF)==13 ); pPage->intKey = 1; if( pPage->leaf ){ pPage->intKeyLeaf = 1; pPage->noPayload = 0; }else{ pPage->intKeyLeaf = 0; pPage->noPayload = 1; pPage->xCellSize = cellSizePtrNoPayload; } pPage->maxLocal = pBt->maxLeaf; pPage->minLocal = pBt->minLeaf; }else if( flagByte==PTF_ZERODATA ){ /* EVIDENCE-OF: R-27225-53936 A value of 2 means the page is an interior ** index b-tree page. */ assert( (PTF_ZERODATA)==2 ); /* EVIDENCE-OF: R-16571-11615 A value of 10 means the page is a leaf |
︙ | ︙ | |||
1620 1621 1622 1623 1624 1625 1626 | for(i=0; i<pPage->nCell; i++){ pc = get2byte(&data[cellOffset+i*2]); testcase( pc==iCellFirst ); testcase( pc==iCellLast ); if( pc<iCellFirst || pc>iCellLast ){ return SQLITE_CORRUPT_BKPT; } | | | 1647 1648 1649 1650 1651 1652 1653 1654 1655 1656 1657 1658 1659 1660 1661 | for(i=0; i<pPage->nCell; i++){ pc = get2byte(&data[cellOffset+i*2]); testcase( pc==iCellFirst ); testcase( pc==iCellLast ); if( pc<iCellFirst || pc>iCellLast ){ return SQLITE_CORRUPT_BKPT; } sz = pPage->xCellSize(pPage, &data[pc]); testcase( pc+sz==usableSize ); if( pc+sz>usableSize ){ return SQLITE_CORRUPT_BKPT; } } if( !pPage->leaf ) iCellLast++; } |
︙ | ︙ | |||
6092 6093 6094 6095 6096 6097 6098 | assert( ArraySize(pPage->apOvfl)==ArraySize(pPage->aiOvfl) ); assert( sqlite3_mutex_held(pPage->pBt->mutex) ); /* The cell should normally be sized correctly. However, when moving a ** 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(). */ | | | 6119 6120 6121 6122 6123 6124 6125 6126 6127 6128 6129 6130 6131 6132 6133 | assert( ArraySize(pPage->apOvfl)==ArraySize(pPage->aiOvfl) ); assert( sqlite3_mutex_held(pPage->pBt->mutex) ); /* The cell should normally be sized correctly. However, when moving a ** 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) ); if( pPage->nOverflow || sz+2>pPage->nFree ){ if( pTemp ){ memcpy(pTemp, pCell, sz); pCell = pTemp; } if( iChild ){ put4byte(pCell, iChild); |
︙ | ︙ | |||
6183 6184 6185 6186 6187 6188 6189 | if( pCell>aData && pCell<pEnd ){ pCell = &pTmp[pCell - aData]; } pData -= szCell[i]; memcpy(pData, pCell, szCell[i]); put2byte(pCellptr, (pData - aData)); pCellptr += 2; | | | | 6210 6211 6212 6213 6214 6215 6216 6217 6218 6219 6220 6221 6222 6223 6224 6225 | if( pCell>aData && pCell<pEnd ){ pCell = &pTmp[pCell - aData]; } pData -= szCell[i]; memcpy(pData, pCell, szCell[i]); put2byte(pCellptr, (pData - aData)); pCellptr += 2; assert( szCell[i]==pPg->xCellSize(pPg, pCell) || CORRUPT_DB ); testcase( szCell[i]==pPg->xCellSize(pPg,pCell) ); } /* The pPg->nFree field is now set incorrectly. The caller will fix it. */ pPg->nCell = nCell; pPg->nOverflow = 0; put2byte(&aData[hdr+1], 0); |
︙ | ︙ | |||
6474 6475 6476 6477 6478 6479 6480 | */ rc = allocateBtreePage(pBt, &pNew, &pgnoNew, 0, 0); if( rc==SQLITE_OK ){ u8 *pOut = &pSpace[4]; u8 *pCell = pPage->apOvfl[0]; | | | 6501 6502 6503 6504 6505 6506 6507 6508 6509 6510 6511 6512 6513 6514 6515 | */ rc = allocateBtreePage(pBt, &pNew, &pgnoNew, 0, 0); if( rc==SQLITE_OK ){ u8 *pOut = &pSpace[4]; u8 *pCell = pPage->apOvfl[0]; u16 szCell = pPage->xCellSize(pPage, pCell); u8 *pStop; assert( sqlite3PagerIswriteable(pNew->pDbPage) ); assert( pPage->aData[0]==(PTF_INTKEY|PTF_LEAFDATA|PTF_LEAF) ); zeroPage(pNew, PTF_INTKEY|PTF_LEAFDATA|PTF_LEAF); rebuildPage(pNew, 1, &pCell, &szCell); pNew->nFree = pBt->usableSize - pNew->cellOffset - 2 - szCell; |
︙ | ︙ | |||
6780 6781 6782 6783 6784 6785 6786 | } nMaxCells += 1+apOld[i]->nCell+apOld[i]->nOverflow; if( (i--)==0 ) break; if( i+nxDiv==pParent->aiOvfl[0] && pParent->nOverflow ){ apDiv[i] = pParent->apOvfl[0]; pgno = get4byte(apDiv[i]); | | | | 6807 6808 6809 6810 6811 6812 6813 6814 6815 6816 6817 6818 6819 6820 6821 6822 6823 6824 6825 6826 | } nMaxCells += 1+apOld[i]->nCell+apOld[i]->nOverflow; if( (i--)==0 ) break; if( i+nxDiv==pParent->aiOvfl[0] && pParent->nOverflow ){ apDiv[i] = pParent->apOvfl[0]; pgno = get4byte(apDiv[i]); szNew[i] = pParent->xCellSize(pParent, apDiv[i]); pParent->nOverflow = 0; }else{ apDiv[i] = findCell(pParent, i+nxDiv-pParent->nOverflow); pgno = get4byte(apDiv[i]); szNew[i] = pParent->xCellSize(pParent, apDiv[i]); /* Drop the cell from the parent page. apDiv[i] still points to ** the cell within the parent, even though it has been dropped. ** This is safe because dropping a cell only overwrites the first ** four bytes of it, and this function does not need the first ** four bytes of the divider cell. So the pointer is safe to use ** later on. |
︙ | ︙ | |||
6875 6876 6877 6878 6879 6880 6881 | } limit = pOld->nCell+pOld->nOverflow; if( pOld->nOverflow>0 ){ for(j=0; j<limit; j++){ assert( nCell<nMaxCells ); apCell[nCell] = findOverflowCell(pOld, j); | | | | 6902 6903 6904 6905 6906 6907 6908 6909 6910 6911 6912 6913 6914 6915 6916 6917 6918 6919 6920 6921 6922 6923 6924 6925 6926 | } limit = pOld->nCell+pOld->nOverflow; if( pOld->nOverflow>0 ){ for(j=0; j<limit; j++){ assert( nCell<nMaxCells ); apCell[nCell] = findOverflowCell(pOld, j); szCell[nCell] = pOld->xCellSize(pOld, apCell[nCell]); nCell++; } }else{ u8 *aData = pOld->aData; u16 maskPage = pOld->maskPage; u16 cellOffset = pOld->cellOffset; for(j=0; j<limit; j++){ assert( nCell<nMaxCells ); apCell[nCell] = findCellv2(aData, maskPage, cellOffset, j); szCell[nCell] = pOld->xCellSize(pOld, apCell[nCell]); nCell++; } } cntOld[i] = nCell; if( i<nOld-1 && !leafData){ u16 sz = (u16)szNew[i]; u8 *pTemp; |
︙ | ︙ | |||
7203 7204 7205 7206 7207 7208 7209 | ** ** Note that this can never happen in an SQLite data file, as all ** cells are at least 4 bytes. It only happens in b-trees used ** to evaluate "IN (SELECT ...)" and similar clauses. */ if( szCell[j]==4 ){ assert(leafCorrection==4); | | | 7230 7231 7232 7233 7234 7235 7236 7237 7238 7239 7240 7241 7242 7243 7244 | ** ** Note that this can never happen in an SQLite data file, as all ** cells are at least 4 bytes. It only happens in b-trees used ** to evaluate "IN (SELECT ...)" and similar clauses. */ if( szCell[j]==4 ){ assert(leafCorrection==4); sz = pParent->xCellSize(pParent, pCell); } } iOvflSpace += sz; assert( sz<=pBt->maxLocal+23 ); assert( iOvflSpace <= (int)pBt->pageSize ); insertCell(pParent, nxDiv+i, pCell, sz, pTemp, pNew->pgno, &rc); if( rc!=SQLITE_OK ) goto balance_cleanup; |
︙ | ︙ | |||
7648 7649 7650 7651 7652 7653 7654 | pCur->pgnoRoot, nKey, nData, pPage->pgno, loc==0 ? "overwrite" : "new entry")); assert( pPage->isInit ); newCell = pBt->pTmpSpace; assert( newCell!=0 ); rc = fillInCell(pPage, newCell, pKey, nKey, pData, nData, nZero, &szNew); if( rc ) goto end_insert; | | | 7675 7676 7677 7678 7679 7680 7681 7682 7683 7684 7685 7686 7687 7688 7689 | pCur->pgnoRoot, nKey, nData, pPage->pgno, loc==0 ? "overwrite" : "new entry")); assert( pPage->isInit ); newCell = pBt->pTmpSpace; assert( newCell!=0 ); rc = fillInCell(pPage, newCell, pKey, nKey, pData, nData, nZero, &szNew); if( rc ) goto end_insert; assert( szNew==pPage->xCellSize(pPage, newCell) ); assert( szNew <= MX_CELL_SIZE(pBt) ); idx = pCur->aiIdx[pCur->iPage]; if( loc==0 ){ u16 szOld; assert( idx<pPage->nCell ); rc = sqlite3PagerWrite(pPage->pDbPage); if( rc ){ |
︙ | ︙ | |||
7790 7791 7792 7793 7794 7795 7796 | MemPage *pLeaf = pCur->apPage[pCur->iPage]; int nCell; Pgno n = pCur->apPage[iCellDepth+1]->pgno; unsigned char *pTmp; pCell = findCell(pLeaf, pLeaf->nCell-1); if( pCell<&pLeaf->aData[4] ) return SQLITE_CORRUPT_BKPT; | | | 7817 7818 7819 7820 7821 7822 7823 7824 7825 7826 7827 7828 7829 7830 7831 | MemPage *pLeaf = pCur->apPage[pCur->iPage]; int nCell; Pgno n = pCur->apPage[iCellDepth+1]->pgno; unsigned char *pTmp; pCell = findCell(pLeaf, pLeaf->nCell-1); if( pCell<&pLeaf->aData[4] ) return SQLITE_CORRUPT_BKPT; nCell = pLeaf->xCellSize(pLeaf, pCell); assert( MX_CELL_SIZE(pBt) >= nCell ); pTmp = pBt->pTmpSpace; assert( pTmp!=0 ); rc = sqlite3PagerWrite(pLeaf->pDbPage); insertCell(pPage, iCellIdx, pCell-4, nCell+4, pTmp, n, &rc); dropCell(pLeaf, pLeaf->nCell-1, nCell, &rc); if( rc ) return rc; |
︙ | ︙ | |||
8802 8803 8804 8805 8806 8807 8808 | cellStart = hdr + 12 - 4*pPage->leaf; /* EVIDENCE-OF: R-02776-14802 The cell pointer array consists of K 2-byte ** integer offsets to the cell contents. */ for(i=0; i<nCell; i++){ int pc = get2byte(&data[cellStart+i*2]); u32 size = 65536; if( pc<=usableSize-4 ){ | | | 8829 8830 8831 8832 8833 8834 8835 8836 8837 8838 8839 8840 8841 8842 8843 | cellStart = hdr + 12 - 4*pPage->leaf; /* EVIDENCE-OF: R-02776-14802 The cell pointer array consists of K 2-byte ** integer offsets to the cell contents. */ for(i=0; i<nCell; i++){ int pc = get2byte(&data[cellStart+i*2]); u32 size = 65536; if( pc<=usableSize-4 ){ size = pPage->xCellSize(pPage, &data[pc]); } if( (int)(pc+size-1)>=usableSize ){ pCheck->zPfx = 0; checkAppendMsg(pCheck, "Corruption detected in cell %d on page %d",i,iPage); }else{ btreeHeapInsert(heap, (pc<<16)|(pc+size-1)); |
︙ | ︙ |
Changes to src/btreeInt.h.
︙ | ︙ | |||
291 292 293 294 295 296 297 298 299 300 301 302 303 304 | ** non-overflow cell */ u8 *apOvfl[5]; /* Pointers to the body of overflow cells */ BtShared *pBt; /* Pointer to BtShared that this page is part of */ u8 *aData; /* Pointer to disk image of the page data */ u8 *aDataEnd; /* One byte past the end of usable data */ u8 *aCellIdx; /* The cell index area */ DbPage *pDbPage; /* Pager page handle */ Pgno pgno; /* Page number for this page */ }; /* ** The in-memory image of a disk page has the auxiliary information appended ** to the end. EXTRA_SIZE is the number of bytes of space needed to hold ** that extra information. | > | 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 | ** non-overflow cell */ u8 *apOvfl[5]; /* Pointers to the body of overflow cells */ BtShared *pBt; /* Pointer to BtShared that this page is part of */ u8 *aData; /* Pointer to disk image of the page data */ u8 *aDataEnd; /* One byte past the end of usable data */ u8 *aCellIdx; /* The cell index area */ DbPage *pDbPage; /* Pager page handle */ u16 (*xCellSize)(MemPage*,u8*); /* cellSizePtr method */ Pgno pgno; /* Page number for this page */ }; /* ** The in-memory image of a disk page has the auxiliary information appended ** to the end. EXTRA_SIZE is the number of bytes of space needed to hold ** that extra information. |
︙ | ︙ |