From 1235bb18159f55bde171a39fc85fe25158e49e0a Mon Sep 17 00:00:00 2001 From: dan Date: Tue, 3 Apr 2012 17:43:28 +0000 Subject: [PATCH] Modify the integrity-check code to reduce the size of the large allocation from 4 bytes to 1 bit for each page in the database file. FossilOrigin-Name: fa3a498dfe9ed59c30da5eaa0d7cad167fd4e393 --- manifest | 16 ++++++++-------- manifest.uuid | 2 +- src/btree.c | 42 ++++++++++++++++++++++++++++++------------ src/btreeInt.h | 8 +++++++- 4 files changed, 46 insertions(+), 22 deletions(-) diff --git a/manifest b/manifest index be9d261014..9edb1496da 100644 --- a/manifest +++ b/manifest @@ -1,5 +1,5 @@ -C Fix\sa\stypo\sin\sthe\srtree6.test\sscript\sthat\sprevented\sit\sfrom\srunning. -D 2012-04-03T17:05:16.797 +C Modify\sthe\sintegrity-check\scode\sto\sreduce\sthe\ssize\sof\sthe\slarge\sallocation\sfrom\s4\sbytes\sto\s1\sbit\sfor\seach\spage\sin\sthe\sdatabase\sfile. +D 2012-04-03T17:43:28.322 F Makefile.arm-wince-mingw32ce-gcc d6df77f1f48d690bd73162294bbba7f59507c72f F Makefile.in 2f37e468503dbe79d35c9f6dffcf3fae1ae9ec20 F Makefile.linux-gcc 91d710bdc4998cb015f39edf3cb314ec4f4d7e23 @@ -126,9 +126,9 @@ F src/auth.c 523da7fb4979469955d822ff9298352d6b31de34 F src/backup.c 6be23a344d3301ae38e92fddb3a33b91c309fce4 F src/bitvec.c af50f1c8c0ff54d6bdb7a80e2fceca5a93670bef F src/btmutex.c 976f45a12e37293e32cae0281b15a21d48a8aaa7 -F src/btree.c 02aeee1f6d425e11f7b9b2d9d461ac501645ed6f +F src/btree.c df800f10896bc2ddaa1125c532d6e7a7b9efc532 F src/btree.h 48a013f8964f12d944d90e4700df47b72dd6d923 -F src/btreeInt.h 26d8ca625b141927fe6620c1d2cf58eaf494ca0c +F src/btreeInt.h 38a639c0542c29fe8331a221c4aed0cb8686249e F src/build.c 987c6933ea170e443dc6a79d52f8d2506206b12b F src/callback.c 0425c6320730e6d3981acfb9202c1bed9016ad1a F src/complete.c dc1d136c0feee03c2f7550bafc0d29075e36deac @@ -1000,7 +1000,7 @@ F tool/tostr.awk e75472c2f98dd76e06b8c9c1367f4ab07e122d06 F tool/vdbe-compress.tcl d70ea6d8a19e3571d7ab8c9b75cba86d1173ff0f F tool/warnings-clang.sh 9f406d66e750e8ac031c63a9ef3248aaa347ef2a F tool/warnings.sh fbc018d67fd7395f440c28f33ef0f94420226381 -P 6d73eb20e825f51143a1b59ad33f44e6448ef760 -R 1bfa9697c3ee58e945b220e1f2e117e6 -U drh -Z 04df2a29417f5db40a26641a7a738bb8 +P 221fe4a8ea5bea90031e459746ea71ff173e6f52 +R 32aad9893eefdebd852afcbce9893d62 +U dan +Z 24eef38a1ddea33d5b3c726c6b9516d2 diff --git a/manifest.uuid b/manifest.uuid index 286c3c4141..6ef0041f8e 100644 --- a/manifest.uuid +++ b/manifest.uuid @@ -1 +1 @@ -221fe4a8ea5bea90031e459746ea71ff173e6f52 \ No newline at end of file +fa3a498dfe9ed59c30da5eaa0d7cad167fd4e393 \ No newline at end of file diff --git a/src/btree.c b/src/btree.c index d24c2be069..2876526925 100644 --- a/src/btree.c +++ b/src/btree.c @@ -7554,6 +7554,25 @@ static void checkAppendMsg( #endif /* SQLITE_OMIT_INTEGRITY_CHECK */ #ifndef SQLITE_OMIT_INTEGRITY_CHECK + +/* +** Return non-zero if the bit in the IntegrityCk.aPgRef[] array that +** corresponds to page iPg is already set. +*/ +static int getPageReferenced(IntegrityCk *pCheck, Pgno iPg){ + assert( iPg<=pCheck->nPage && sizeof(pCheck->aPgRef[0])==1 ); + return (pCheck->aPgRef[iPg/8] & (1 << (iPg & 0x07))); +} + +/* +** Set the bit in the IntegrityCk.aPgRef[] array that corresponds to page iPg. +*/ +static void setPageReferenced(IntegrityCk *pCheck, Pgno iPg){ + assert( iPg<=pCheck->nPage && sizeof(pCheck->aPgRef[0])==1 ); + pCheck->aPgRef[iPg/8] |= (1 << (iPg & 0x07)); +} + + /* ** Add 1 to the reference count for page iPage. If this is the second ** reference to the page, add an error message to pCheck->zErrMsg. @@ -7568,11 +7587,12 @@ static int checkRef(IntegrityCk *pCheck, Pgno iPage, char *zContext){ checkAppendMsg(pCheck, zContext, "invalid page number %d", iPage); return 1; } - if( pCheck->anRef[iPage]==1 ){ + if( getPageReferenced(pCheck, iPage) ){ checkAppendMsg(pCheck, zContext, "2nd reference to page %d", iPage); return 1; } - return (pCheck->anRef[iPage]++)>1; + setPageReferenced(pCheck, iPage); + return 0; } #ifndef SQLITE_OMIT_AUTOVACUUM @@ -7948,17 +7968,15 @@ char *sqlite3BtreeIntegrityCheck( sqlite3BtreeLeave(p); return 0; } - sCheck.anRef = sqlite3Malloc( (sCheck.nPage+1)*sizeof(sCheck.anRef[0]) ); - if( !sCheck.anRef ){ + + sCheck.aPgRef = sqlite3MallocZero((sCheck.nPage / 8)+ 1); + if( !sCheck.aPgRef ){ *pnErr = 1; sqlite3BtreeLeave(p); return 0; } - for(i=0; i<=sCheck.nPage; i++){ sCheck.anRef[i] = 0; } i = PENDING_BYTE_PAGE(pBt); - if( i<=sCheck.nPage ){ - sCheck.anRef[i] = 1; - } + if( i<=sCheck.nPage ) setPageReferenced(&sCheck, i); sqlite3StrAccumInit(&sCheck.errMsg, zErr, sizeof(zErr), 20000); sCheck.errMsg.useMalloc = 2; @@ -7983,18 +8001,18 @@ char *sqlite3BtreeIntegrityCheck( */ for(i=1; i<=sCheck.nPage && sCheck.mxErr; i++){ #ifdef SQLITE_OMIT_AUTOVACUUM - if( sCheck.anRef[i]==0 ){ + if( getPageReferenced(&sCheck, i)==0 ){ checkAppendMsg(&sCheck, 0, "Page %d is never used", i); } #else /* If the database supports auto-vacuum, make sure no tables contain ** references to pointer-map pages. */ - if( sCheck.anRef[i]==0 && + if( getPageReferenced(&sCheck, i)==0 && (PTRMAP_PAGENO(pBt, i)!=i || !pBt->autoVacuum) ){ checkAppendMsg(&sCheck, 0, "Page %d is never used", i); } - if( sCheck.anRef[i]!=0 && + if( getPageReferenced(&sCheck, i)!=0 && (PTRMAP_PAGENO(pBt, i)==i && pBt->autoVacuum) ){ checkAppendMsg(&sCheck, 0, "Pointer map page %d is referenced", i); } @@ -8015,7 +8033,7 @@ char *sqlite3BtreeIntegrityCheck( /* Clean up and report errors. */ sqlite3BtreeLeave(p); - sqlite3_free(sCheck.anRef); + sqlite3_free(sCheck.aPgRef); if( sCheck.mallocFailed ){ sqlite3StrAccumReset(&sCheck.errMsg); *pnErr = sCheck.nErr+1; diff --git a/src/btreeInt.h b/src/btreeInt.h index 841e2c6eab..0d21497966 100644 --- a/src/btreeInt.h +++ b/src/btreeInt.h @@ -631,12 +631,18 @@ struct BtCursor { /* ** This structure is passed around through all the sanity checking routines ** in order to keep track of some global state information. +** +** The aRef[] array is allocated so that there is 1 bit for each page in +** the database. As the integrity-check proceeds, for each page used in +** the database the corresponding bit is set. This allows integrity-check to +** detect pages that are used twice and orphaned pages (both of which +** indicate corruption). */ typedef struct IntegrityCk IntegrityCk; struct IntegrityCk { BtShared *pBt; /* The tree being checked out */ Pager *pPager; /* The associated pager. Also accessible by pBt->pPager */ - int *anRef; /* Number of times each page is referenced */ + u8 *aPgRef; /* 1 bit per page in the db (see above) */ Pgno nPage; /* Number of pages in the database */ int mxErr; /* Stop accumulating errors when this reaches zero */ int nErr; /* Number of messages written to zErrMsg so far */ -- 2.47.2