/ Check-in [bec6a65a]
Login

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

Overview
Comment:Auto-vacuum bug: Deallocate pointer-map pages when shrinking a database file. (CVS 2048)
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1:bec6a65acaa8bfd8fe2cb475ba2e992a1993e4e7
User & Date: danielk1977 2004-11-03 11:37:08
Context
2004-11-03
13:59
More work on optionally removing unused features at compile-time. (CVS 2049) check-in: a82980fd user: drh tags: trunk
11:37
Auto-vacuum bug: Deallocate pointer-map pages when shrinking a database file. (CVS 2048) check-in: bec6a65a user: danielk1977 tags: trunk
09:30
Comment the autovacuum.test script. No code or test-case changes. (CVS 2047) check-in: 2eacd386 user: danielk1977 tags: trunk
Changes
Hide Diffs Side-by-Side Diffs Ignore Whitespace Patch

Changes to src/btree.c.

     5      5   ** a legal notice, here is a blessing:
     6      6   **
     7      7   **    May you do good and not evil.
     8      8   **    May you find forgiveness for yourself and forgive others.
     9      9   **    May you share freely, never taking more than you give.
    10     10   **
    11     11   *************************************************************************
    12         -** $Id: btree.c,v 1.201 2004/11/03 03:52:37 danielk1977 Exp $
           12  +** $Id: btree.c,v 1.202 2004/11/03 11:37:08 danielk1977 Exp $
    13     13   **
    14     14   ** This file implements a external (disk-based) database using BTrees.
    15     15   ** For a detailed discussion of BTrees, refer to
    16     16   **
    17     17   **     Donald E. Knuth, THE ART OF COMPUTER PROGRAMMING, Volume 3:
    18     18   **     "Sorting And Searching", pages 473-480. Addison-Wesley
    19     19   **     Publishing Company, Reading, Massachusetts.
................................................................................
   408    408   **
   409    409   ** If the pgno argument passed to PTRMAP_PAGENO is a pointer-map page,
   410    410   ** then pgno is returned. So (pgno==PTRMAP_PAGENO(pgsz, pgno)) can be
   411    411   ** used to test if pgno is a pointer-map page.
   412    412   */
   413    413   #define PTRMAP_PAGENO(pgsz, pgno) (((pgno-2)/(pgsz/5+1))*(pgsz/5+1)+2)
   414    414   #define PTRMAP_PTROFFSET(pgsz, pgno) (((pgno-2)%(pgsz/5+1)-1)*5)
          415  +
          416  +#define PTRMAP_ISPAGE(pgsz, pgno) (PTRMAP_PAGENO(pgsz,pgno)==pgno)
   415    417   
   416    418   /*
   417    419   ** The pointer map is a lookup table that contains an entry for each database
   418    420   ** page in the file except for page 1. In this context 'database page' refers
   419    421   ** to any page that is not part of the pointer map itself.  Each pointer map
   420    422   ** entry consists of a single byte 'type' and a 4 byte page number. The
   421    423   ** PTRMAP_XXX identifiers below are the valid types. The interpretation
................................................................................
  1610   1612   /*
  1611   1613   ** This routine is called prior to sqlite3pager_commit when a transaction
  1612   1614   ** is commited for an auto-vacuum database.
  1613   1615   */
  1614   1616   static int autoVacuumCommit(Btree *pBt){
  1615   1617     Pager *pPager = pBt->pPager;
  1616   1618     Pgno nFreeList;   /* Number of pages remaining on the free-list. */
  1617         -  Pgno origDbSize;  /* Pages in the database file */
  1618         -  Pgno finDbSize;   /* Pages in the database file after truncation */
         1619  +  int nPtrMap;      /* Number of pointer-map pages deallocated */
         1620  +  Pgno origSize;  /* Pages in the database file */
         1621  +  Pgno finSize;   /* Pages in the database file after truncation */
  1619   1622     int i;            /* Counter variable */
  1620   1623     int rc;           /* Return code */
  1621   1624     u8 eType;
  1622         -
         1625  +  int pgsz = pBt->pageSize;  /* Page size for this database */
  1623   1626     Pgno iDbPage;              /* The database page to move */
  1624   1627     u8 *pDbPage = 0;           /* "" */
  1625   1628     MemPage *pDbMemPage = 0;   /* "" */
  1626   1629     Pgno iPtrPage;             /* The page that contains a pointer to iDbPage */
  1627   1630     MemPage *pPtrMemPage = 0;  /* "" */
  1628   1631     Pgno iFreePage;            /* The free-list page to move iDbPage to */
  1629   1632     MemPage *pFreeMemPage = 0; /* "" */
  1630   1633   
  1631   1634   #ifndef NDEBUG
  1632   1635     int nRef = *sqlite3pager_stats(pPager);
  1633   1636   #endif
  1634   1637   
  1635   1638     assert( pBt->autoVacuum );
         1639  +  assert( 0==PTRMAP_ISPAGE(pgsz, sqlite3pager_pagecount(pPager)) );
  1636   1640   
  1637   1641     /* Figure out how many free-pages are in the database. If there are no
  1638   1642     ** free pages, then auto-vacuum is a no-op.
  1639   1643     */
  1640   1644     nFreeList = get4byte(&pBt->pPage1->aData[36]);
  1641         -  if( nFreeList==0 ) return SQLITE_OK;
         1645  +  if( nFreeList==0 ){
         1646  +    return SQLITE_OK;
         1647  +  }
  1642   1648   
  1643         -  /* TODO: This does not calculate finDbSize correctly for the case where
  1644         -  ** pointer-map pages must be deallocated.
  1645         -  */
  1646         -  origDbSize = sqlite3pager_pagecount(pPager);
  1647         -  finDbSize = origDbSize - nFreeList;
  1648         -  TRACE(("AUTOVACUUM: Begin (db size %d->%d)\n", origDbSize, finDbSize));
         1649  +  origSize = sqlite3pager_pagecount(pPager);
         1650  +  nPtrMap = (nFreeList-origSize+PTRMAP_PAGENO(pgsz, origSize)+pgsz/5)/(pgsz/5);
         1651  +  finSize = origSize - nFreeList - nPtrMap;
         1652  +
         1653  +  TRACE(("AUTOVACUUM: Begin (db size %d->%d)\n", origSize, finSize));
  1649   1654   
  1650   1655     /* Note: This is temporary code for use during development of auto-vacuum. 
  1651   1656     **
  1652   1657     ** Inspect the pointer map to make sure there are no root pages with a
  1653         -  ** page number greater than finDbSize. If so, the auto-vacuum cannot
         1658  +  ** page number greater than finSize. If so, the auto-vacuum cannot
  1654   1659     ** proceed. This limitation will be fixed when root pages are automatically
  1655   1660     ** allocated at the start of the database file.
  1656   1661     */
  1657         -  for( i=finDbSize+1; i<=origDbSize; i++ ){
         1662  +  for( i=finSize+1; i<=origSize; i++ ){
  1658   1663       rc = ptrmapGet(pBt, i, &eType, 0);
  1659   1664       if( rc!=SQLITE_OK ) goto autovacuum_out;
  1660   1665       if( eType==PTRMAP_ROOTPAGE ){
  1661   1666         TRACE(("AUTOVACUUM: Cannot proceed due to root-page on page %d\n", i));
  1662   1667         return SQLITE_OK;
  1663   1668       }
  1664   1669     }
  1665   1670   
  1666         -  /* Variable 'finDbSize' will be the size of the file in pages after
         1671  +  /* Variable 'finSize' will be the size of the file in pages after
  1667   1672     ** the auto-vacuum has completed (the current file size minus the number
  1668   1673     ** of pages on the free list). Loop through the pages that lie beyond
  1669   1674     ** this mark, and if they are not already on the free list, move them
  1670         -  ** to a free page earlier in the file (somewhere before finDbSize).
         1675  +  ** to a free page earlier in the file (somewhere before finSize).
  1671   1676     */
  1672         -  for( iDbPage=finDbSize+1; iDbPage<=origDbSize; iDbPage++ ){
         1677  +  for( iDbPage=finSize+1; iDbPage<=origSize; iDbPage++ ){
  1673   1678       rc = ptrmapGet(pBt, iDbPage, &eType, &iPtrPage);
  1674   1679       if( rc!=SQLITE_OK ) goto autovacuum_out;
  1675   1680       assert( eType!=PTRMAP_ROOTPAGE );
  1676   1681   
  1677   1682       /* If iDbPage is a free or pointer map page, do not swap it. */
  1678         -    if( eType==PTRMAP_FREEPAGE ||
  1679         -        iDbPage==PTRMAP_PAGENO(pBt->pageSize, iDbPage) ){
         1683  +    if( eType==PTRMAP_FREEPAGE || PTRMAP_ISPAGE(pgsz, iDbPage) ){
  1680   1684         continue;
  1681   1685       }
  1682   1686       rc = getPage(pBt, iDbPage, &pDbMemPage);
  1683   1687       if( rc!=SQLITE_OK ) goto autovacuum_out;
  1684   1688       pDbPage = pDbMemPage->aData;
  1685   1689   
  1686   1690       /* Find the next page in the free-list that is not already at the end 
................................................................................
  1690   1694       do{
  1691   1695         if( pFreeMemPage ){
  1692   1696           releasePage(pFreeMemPage);
  1693   1697           pFreeMemPage = 0;
  1694   1698         }
  1695   1699         rc = allocatePage(pBt, &pFreeMemPage, &iFreePage, 0);
  1696   1700         if( rc!=SQLITE_OK ) goto autovacuum_out;
  1697         -      assert( iFreePage<=origDbSize );
  1698         -    }while( iFreePage>finDbSize );
         1701  +      assert( iFreePage<=origSize );
         1702  +    }while( iFreePage>finSize );
  1699   1703   
  1700   1704       /* Move page iDbPage from it's current location to page number iFreePage */
  1701   1705       TRACE(("AUTOVACUUM: Moving %d to free page %d (ptr page %d type %d)\n", 
  1702   1706           iDbPage, iFreePage, iPtrPage, eType));
  1703   1707       releasePage(pFreeMemPage);
  1704   1708       pFreeMemPage = 0;
  1705   1709       rc = sqlite3pager_movepage(pPager, pDbPage, iFreePage);
................................................................................
  1716   1720       */
  1717   1721       if( eType==PTRMAP_BTREE ){
  1718   1722         rc = setChildPtrmaps(pDbMemPage);
  1719   1723         if( rc!=SQLITE_OK ) goto autovacuum_out;
  1720   1724       }else{
  1721   1725         Pgno nextOvfl = get4byte(pDbPage);
  1722   1726         if( nextOvfl!=0 ){
  1723         -        assert( nextOvfl<=origDbSize );
         1727  +        assert( nextOvfl<=origSize );
  1724   1728           rc = ptrmapPut(pBt, nextOvfl, PTRMAP_OVERFLOW2, iFreePage);
  1725   1729           if( rc!=SQLITE_OK ) goto autovacuum_out;
  1726   1730         }
  1727   1731       }
  1728   1732       releasePage(pDbMemPage);
  1729   1733       pDbMemPage = 0;
  1730   1734   
................................................................................
  1739   1743       modifyPagePointer(pPtrMemPage, iDbPage, iFreePage, eType);
  1740   1744       rc = ptrmapPut(pBt, iFreePage, eType, iPtrPage);
  1741   1745       if( rc!=SQLITE_OK ) goto autovacuum_out;
  1742   1746       releasePage(pPtrMemPage);
  1743   1747     }
  1744   1748   
  1745   1749     /* The entire free-list has been swapped to the end of the file. So
  1746         -  ** truncate the database file to finDbSize pages and consider the
         1750  +  ** truncate the database file to finSize pages and consider the
  1747   1751     ** free-list empty.
  1748   1752     */
  1749   1753     rc = sqlite3pager_write(pBt->pPage1->aData);
  1750   1754     if( rc!=SQLITE_OK ) goto autovacuum_out;
  1751   1755     put4byte(&pBt->pPage1->aData[32], 0);
  1752   1756     put4byte(&pBt->pPage1->aData[36], 0);
  1753         -  rc = sqlite3pager_truncate(pBt->pPager, finDbSize);
         1757  +  rc = sqlite3pager_truncate(pBt->pPager, finSize);
  1754   1758     if( rc!=SQLITE_OK ) goto autovacuum_out;
  1755   1759   
  1756   1760   autovacuum_out:
  1757   1761     /* TODO: A goto autovacuum_out; will fail to call releasePage() on 
  1758   1762     ** outstanding references. Fix.
  1759   1763     */
  1760   1764     assert( nRef==*sqlite3pager_stats(pPager) );
................................................................................
  2870   2874       }
  2871   2875     }else{
  2872   2876       /* There are no pages on the freelist, so create a new page at the
  2873   2877       ** end of the file */
  2874   2878       *pPgno = sqlite3pager_pagecount(pBt->pPager) + 1;
  2875   2879   
  2876   2880   #ifndef SQLITE_OMIT_AUTOVACUUM
  2877         -    if( pBt->autoVacuum && *pPgno==PTRMAP_PAGENO(pBt->pageSize, *pPgno) ){
         2881  +    if( pBt->autoVacuum && PTRMAP_ISPAGE(pBt->pageSize, *pPgno) ){
  2878   2882         /* If *pPgno refers to a pointer-map page, allocate two new pages
  2879   2883         ** at the end of the file instead of one. The first allocated page
  2880   2884         ** becomes a new pointer-map page, the second is used by the caller.
  2881   2885         */
  2882   2886         TRACE(("ALLOCATE: %d from end of file (pointer-map page)\n", *pPgno));
  2883   2887         (*pPgno)++;
  2884   2888       }
................................................................................
  3054   3058     while( nPayload>0 ){
  3055   3059       if( spaceLeft==0 ){
  3056   3060   #ifndef SQLITE_OMIT_AUTOVACUUM
  3057   3061         Pgno pgnoPtrmap = pgnoOvfl; /* Overflow page pointer-map entry page */
  3058   3062   #endif
  3059   3063         rc = allocatePage(pBt, &pOvfl, &pgnoOvfl, pgnoOvfl);
  3060   3064   #ifndef SQLITE_OMIT_AUTOVACUUM
  3061         -      /* If the database supports auto-vacuum, add an entry to the 
  3062         -      ** pointer-map for the overflow page just allocated. If the page just 
  3063         -      ** allocated was the first in the overflow list, then the balance() 
  3064         -      ** routine may adjust the pointer-map entry later.
         3065  +      /* If the database supports auto-vacuum, and the second or subsequent
         3066  +      ** overflow page is being allocated, add an entry to the pointer-map
         3067  +      ** for that page now. The entry for the first overflow page will be
         3068  +      ** added later, by the insertCell() routine.
  3065   3069         */
  3066         -      if( pBt->autoVacuum && rc==0 ){
  3067         -        if( pgnoPtrmap!=0 ){
  3068         -          rc = ptrmapPut(pBt, pgnoOvfl, PTRMAP_OVERFLOW2, pgnoPtrmap);
  3069         -        }else{
  3070         -          rc = ptrmapPut(pBt, pgnoOvfl, PTRMAP_OVERFLOW1, pPage->pgno);
  3071         -        }
         3070  +      if( pBt->autoVacuum && pgnoPtrmap!=0 && rc==SQLITE_OK ){
         3071  +        rc = ptrmapPut(pBt, pgnoOvfl, PTRMAP_OVERFLOW2, pgnoPtrmap);
  3072   3072         }
  3073   3073   #endif
  3074   3074         if( rc ){
  3075   3075           releasePage(pToRelease);
  3076   3076           clearCell(pPage, pCell);
  3077   3077           return rc;
  3078   3078         }
................................................................................
  3285   3285         ptr[0] = ptr[-2];
  3286   3286         ptr[1] = ptr[-1];
  3287   3287       }
  3288   3288       put2byte(&data[ins], idx);
  3289   3289       put2byte(&data[hdr+3], pPage->nCell);
  3290   3290       pPage->idxShift = 1;
  3291   3291       pageIntegrity(pPage);
         3292  +#ifndef SQLITE_OMIT_AUTOVACUUM
         3293  +    if( pPage->pBt->autoVacuum ){
         3294  +      /* The cell may contain a pointer to an overflow page. If so, write
         3295  +      ** the entry for the overflow page into the pointer map.
         3296  +      */
         3297  +      CellInfo info;
         3298  +      parseCellPtr(pPage, pCell, &info);
         3299  +      if( (info.nData+(pPage->intKey?0:info.nKey))>info.nLocal ){
         3300  +        Pgno pgnoOvfl = get4byte(&pCell[info.iOverflow]);
         3301  +        int rc = ptrmapPut(pPage->pBt, pgnoOvfl, PTRMAP_OVERFLOW1, pPage->pgno);
         3302  +        if( rc!=SQLITE_OK ) return rc;
         3303  +      }
         3304  +    }
         3305  +#endif
  3292   3306     }
  3293   3307   
  3294         -#ifndef SQLITE_OMIT_AUTOVACUUM
  3295         -  if( pPage->pBt->autoVacuum ){
  3296         -    /* The cell may contain a pointer to an overflow page. If so, write
  3297         -    ** the entry for the overflow page into the pointer map.
  3298         -    */
  3299         -    CellInfo info;
  3300         -    parseCellPtr(pPage, pCell, &info);
  3301         -    if( (info.nData+(pPage->intKey?0:info.nKey))>info.nLocal ){
  3302         -      Pgno pgnoOvfl = get4byte(&pCell[info.iOverflow]);
  3303         -      int rc = ptrmapPut(pPage->pBt, pgnoOvfl, PTRMAP_OVERFLOW1, pPage->pgno);
  3304         -      if( rc!=SQLITE_OK ) return rc;
  3305         -    }
  3306         -  }
  3307         -#endif
  3308   3308     return SQLITE_OK;
  3309   3309   }
  3310   3310   
  3311   3311   /*
  3312   3312   ** Add a list of cells to a page.  The page should be initially empty.
  3313   3313   ** The cells are guaranteed to fit on the page.
  3314   3314   */