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