/ Check-in [fa3a498d]
Login

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

Overview
Comment: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.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1: fa3a498dfe9ed59c30da5eaa0d7cad167fd4e393
User & Date: dan 2012-04-03 17:43:28
Context
2012-04-03
18:33
Modify capi3.test and capi3c.test so that they work with SQLITE_OMIT_AUTORESET builds. check-in: 1d5e744c user: dan tags: trunk
17:43
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. check-in: fa3a498d user: dan tags: trunk
17:05
Fix a typo in the rtree6.test script that prevented it from running. check-in: 221fe4a8 user: drh tags: trunk
Changes
Hide Diffs Side-by-Side Diffs Ignore Whitespace Patch

Changes to src/btree.c.

  7550   7550     if( pCheck->errMsg.mallocFailed ){
  7551   7551       pCheck->mallocFailed = 1;
  7552   7552     }
  7553   7553   }
  7554   7554   #endif /* SQLITE_OMIT_INTEGRITY_CHECK */
  7555   7555   
  7556   7556   #ifndef SQLITE_OMIT_INTEGRITY_CHECK
         7557  +
         7558  +/*
         7559  +** Return non-zero if the bit in the IntegrityCk.aPgRef[] array that
         7560  +** corresponds to page iPg is already set.
         7561  +*/
         7562  +static int getPageReferenced(IntegrityCk *pCheck, Pgno iPg){
         7563  +  assert( iPg<=pCheck->nPage && sizeof(pCheck->aPgRef[0])==1 );
         7564  +  return (pCheck->aPgRef[iPg/8] & (1 << (iPg & 0x07)));
         7565  +}
         7566  +
         7567  +/*
         7568  +** Set the bit in the IntegrityCk.aPgRef[] array that corresponds to page iPg.
         7569  +*/
         7570  +static void setPageReferenced(IntegrityCk *pCheck, Pgno iPg){
         7571  +  assert( iPg<=pCheck->nPage && sizeof(pCheck->aPgRef[0])==1 );
         7572  +  pCheck->aPgRef[iPg/8] |= (1 << (iPg & 0x07));
         7573  +}
         7574  +
         7575  +
  7557   7576   /*
  7558   7577   ** Add 1 to the reference count for page iPage.  If this is the second
  7559   7578   ** reference to the page, add an error message to pCheck->zErrMsg.
  7560   7579   ** Return 1 if there are 2 ore more references to the page and 0 if
  7561   7580   ** if this is the first reference to the page.
  7562   7581   **
  7563   7582   ** Also check that the page number is in bounds.
................................................................................
  7564   7583   */
  7565   7584   static int checkRef(IntegrityCk *pCheck, Pgno iPage, char *zContext){
  7566   7585     if( iPage==0 ) return 1;
  7567   7586     if( iPage>pCheck->nPage ){
  7568   7587       checkAppendMsg(pCheck, zContext, "invalid page number %d", iPage);
  7569   7588       return 1;
  7570   7589     }
  7571         -  if( pCheck->anRef[iPage]==1 ){
         7590  +  if( getPageReferenced(pCheck, iPage) ){
  7572   7591       checkAppendMsg(pCheck, zContext, "2nd reference to page %d", iPage);
  7573   7592       return 1;
  7574   7593     }
  7575         -  return  (pCheck->anRef[iPage]++)>1;
         7594  +  setPageReferenced(pCheck, iPage);
         7595  +  return 0;
  7576   7596   }
  7577   7597   
  7578   7598   #ifndef SQLITE_OMIT_AUTOVACUUM
  7579   7599   /*
  7580   7600   ** Check that the entry in the pointer-map for page iChild maps to 
  7581   7601   ** page iParent, pointer type ptrType. If not, append an error message
  7582   7602   ** to pCheck.
................................................................................
  7944   7964     sCheck.nErr = 0;
  7945   7965     sCheck.mallocFailed = 0;
  7946   7966     *pnErr = 0;
  7947   7967     if( sCheck.nPage==0 ){
  7948   7968       sqlite3BtreeLeave(p);
  7949   7969       return 0;
  7950   7970     }
  7951         -  sCheck.anRef = sqlite3Malloc( (sCheck.nPage+1)*sizeof(sCheck.anRef[0]) );
  7952         -  if( !sCheck.anRef ){
         7971  +
         7972  +  sCheck.aPgRef = sqlite3MallocZero((sCheck.nPage / 8)+ 1);
         7973  +  if( !sCheck.aPgRef ){
  7953   7974       *pnErr = 1;
  7954   7975       sqlite3BtreeLeave(p);
  7955   7976       return 0;
  7956   7977     }
  7957         -  for(i=0; i<=sCheck.nPage; i++){ sCheck.anRef[i] = 0; }
  7958   7978     i = PENDING_BYTE_PAGE(pBt);
  7959         -  if( i<=sCheck.nPage ){
  7960         -    sCheck.anRef[i] = 1;
  7961         -  }
         7979  +  if( i<=sCheck.nPage ) setPageReferenced(&sCheck, i);
  7962   7980     sqlite3StrAccumInit(&sCheck.errMsg, zErr, sizeof(zErr), 20000);
  7963   7981     sCheck.errMsg.useMalloc = 2;
  7964   7982   
  7965   7983     /* Check the integrity of the freelist
  7966   7984     */
  7967   7985     checkList(&sCheck, 1, get4byte(&pBt->pPage1->aData[32]),
  7968   7986               get4byte(&pBt->pPage1->aData[36]), "Main freelist: ");
................................................................................
  7979   7997       checkTreePage(&sCheck, aRoot[i], "List of tree roots: ", NULL, NULL);
  7980   7998     }
  7981   7999   
  7982   8000     /* Make sure every page in the file is referenced
  7983   8001     */
  7984   8002     for(i=1; i<=sCheck.nPage && sCheck.mxErr; i++){
  7985   8003   #ifdef SQLITE_OMIT_AUTOVACUUM
  7986         -    if( sCheck.anRef[i]==0 ){
         8004  +    if( getPageReferenced(&sCheck, i)==0 ){
  7987   8005         checkAppendMsg(&sCheck, 0, "Page %d is never used", i);
  7988   8006       }
  7989   8007   #else
  7990   8008       /* If the database supports auto-vacuum, make sure no tables contain
  7991   8009       ** references to pointer-map pages.
  7992   8010       */
  7993         -    if( sCheck.anRef[i]==0 && 
         8011  +    if( getPageReferenced(&sCheck, i)==0 && 
  7994   8012          (PTRMAP_PAGENO(pBt, i)!=i || !pBt->autoVacuum) ){
  7995   8013         checkAppendMsg(&sCheck, 0, "Page %d is never used", i);
  7996   8014       }
  7997         -    if( sCheck.anRef[i]!=0 && 
         8015  +    if( getPageReferenced(&sCheck, i)!=0 && 
  7998   8016          (PTRMAP_PAGENO(pBt, i)==i && pBt->autoVacuum) ){
  7999   8017         checkAppendMsg(&sCheck, 0, "Pointer map page %d is referenced", i);
  8000   8018       }
  8001   8019   #endif
  8002   8020     }
  8003   8021   
  8004   8022     /* Make sure this analysis did not leave any unref() pages.
................................................................................
  8011   8029         nRef, sqlite3PagerRefcount(pBt->pPager)
  8012   8030       );
  8013   8031     }
  8014   8032   
  8015   8033     /* Clean  up and report errors.
  8016   8034     */
  8017   8035     sqlite3BtreeLeave(p);
  8018         -  sqlite3_free(sCheck.anRef);
         8036  +  sqlite3_free(sCheck.aPgRef);
  8019   8037     if( sCheck.mallocFailed ){
  8020   8038       sqlite3StrAccumReset(&sCheck.errMsg);
  8021   8039       *pnErr = sCheck.nErr+1;
  8022   8040       return 0;
  8023   8041     }
  8024   8042     *pnErr = sCheck.nErr;
  8025   8043     if( sCheck.nErr==0 ) sqlite3StrAccumReset(&sCheck.errMsg);

Changes to src/btreeInt.h.

   627    627   #define ISAUTOVACUUM 0
   628    628   #endif
   629    629   
   630    630   
   631    631   /*
   632    632   ** This structure is passed around through all the sanity checking routines
   633    633   ** in order to keep track of some global state information.
          634  +**
          635  +** The aRef[] array is allocated so that there is 1 bit for each page in
          636  +** the database. As the integrity-check proceeds, for each page used in
          637  +** the database the corresponding bit is set. This allows integrity-check to 
          638  +** detect pages that are used twice and orphaned pages (both of which 
          639  +** indicate corruption).
   634    640   */
   635    641   typedef struct IntegrityCk IntegrityCk;
   636    642   struct IntegrityCk {
   637    643     BtShared *pBt;    /* The tree being checked out */
   638    644     Pager *pPager;    /* The associated pager.  Also accessible by pBt->pPager */
   639         -  int *anRef;       /* Number of times each page is referenced */
          645  +  u8 *aPgRef;       /* 1 bit per page in the db (see above) */
   640    646     Pgno nPage;       /* Number of pages in the database */
   641    647     int mxErr;        /* Stop accumulating errors when this reaches zero */
   642    648     int nErr;         /* Number of messages written to zErrMsg so far */
   643    649     int mallocFailed; /* A memory allocation error has occurred */
   644    650     StrAccum errMsg;  /* Accumulate the error message text here */
   645    651   };
   646    652