/ Check-in [40249ed1]
Login

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

Overview
Comment:Fix an auto-vacuum bug for btree entries that span more than one overflow page. (CVS 2039)
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1: 40249ed19cd53cb61f9575d8165316faf2627479
User & Date: danielk1977 2004-11-02 14:40:32
Context
2004-11-02
18:05
Get btree.c to compile with -DNDEBUG=1. (CVS 2040) check-in: 8378c144 user: drh tags: trunk
14:40
Fix an auto-vacuum bug for btree entries that span more than one overflow page. (CVS 2039) check-in: 40249ed1 user: danielk1977 tags: trunk
14:24
Require that the page size be a power of 2. (CVS 2038) check-in: c33b34db user: drh tags: trunk
Changes
Hide Diffs Unified Diffs Ignore Whitespace Patch

Changes to src/btree.c.

5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
....
1560
1561
1562
1563
1564
1565
1566

1567
1568
1569
1570
1571
1572
1573
1574
1575
1576
1577
1578
1579
1580
1581
1582
1583
1584
1585
....
1691
1692
1693
1694
1695
1696
1697
1698
1699
1700
1701
1702
1703
1704
1705
1706
1707
1708




1709
1710
1711
1712







1713
1714
1715
1716
1717
1718
1719
** 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.197 2004/11/02 14:24:34 drh 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.
................................................................................
**
** PTRMAP_OVERFLOW2: pPage is an overflow-page. The pointer points at the next
**                   overflow page in the list.
*/
static void modifyPagePointer(MemPage *pPage, Pgno iFrom, Pgno iTo, u8 eType){

  if( eType==PTRMAP_OVERFLOW2 ){

    assert( get4byte(pPage->aData)==iFrom );
    put4byte(pPage->aData, iFrom);
  }else{
    int isInitOrig = pPage->isInit;
    int i;
    int nCell;

    initPage(pPage, 0);
    nCell = pPage->nCell;

   /*  assert( !pPage->leaf && eType==PTRMAP_BTREE ); */

    for(i=0; i<nCell; i++){
      u8 *pCell = findCell(pPage, i);
      if( eType==PTRMAP_OVERFLOW1 ){
        CellInfo info;
        parseCellPtr(pPage, pCell, &info);
        if( info.iOverflow ){
          if( iFrom==get4byte(&pCell[info.iOverflow]) ){
................................................................................
      }
      rc = allocatePage(pBt, &pFreeMemPage, &iFreePage, 0);
      if( rc!=SQLITE_OK ) goto autovacuum_out;
      assert( iFreePage<=origDbSize );
    }while( iFreePage>finDbSize );

    /* Move page iDbPage from it's current location to page number iFreePage */
    TRACE(("AUTOVACUUM: Moving %d to free page %d (ptr page %d)\n", 
        iDbPage, iFreePage, iPtrPage));
    releasePage(pFreeMemPage);
    pFreeMemPage = 0;
    rc = sqlite3pager_movepage(pPager, pDbPage, iFreePage);
    if( rc!=SQLITE_OK ) goto autovacuum_out;
    pDbMemPage->pgno = iFreePage;

    /* If pDbPage was a btree-page, then it may have child pages and/or cells
    ** that point to overflow pages. The pointer map entries for all these
    ** pages need to be changed.




    */
    if( eType==PTRMAP_BTREE ){
      rc = setChildPtrmaps(pDbMemPage);
      if( rc!=SQLITE_OK ) goto autovacuum_out;







    }
    releasePage(pDbMemPage);
    pDbMemPage = 0;

    /* Fix the database pointer on page iPtrPage that pointed at iDbPage so
    ** that it points at iFreePage. Also fix the pointer map entry for
    ** iPtrPage.







|







 







>

|








<
<







 







|
|









>
>
>
>




>
>
>
>
>
>
>







5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
....
1560
1561
1562
1563
1564
1565
1566
1567
1568
1569
1570
1571
1572
1573
1574
1575
1576
1577


1578
1579
1580
1581
1582
1583
1584
....
1690
1691
1692
1693
1694
1695
1696
1697
1698
1699
1700
1701
1702
1703
1704
1705
1706
1707
1708
1709
1710
1711
1712
1713
1714
1715
1716
1717
1718
1719
1720
1721
1722
1723
1724
1725
1726
1727
1728
1729
** 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.198 2004/11/02 14:40:32 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.
................................................................................
**
** PTRMAP_OVERFLOW2: pPage is an overflow-page. The pointer points at the next
**                   overflow page in the list.
*/
static void modifyPagePointer(MemPage *pPage, Pgno iFrom, Pgno iTo, u8 eType){

  if( eType==PTRMAP_OVERFLOW2 ){
    /* The pointer is always the first 4 bytes of the page in this case.  */
    assert( get4byte(pPage->aData)==iFrom );
    put4byte(pPage->aData, iTo);
  }else{
    int isInitOrig = pPage->isInit;
    int i;
    int nCell;

    initPage(pPage, 0);
    nCell = pPage->nCell;



    for(i=0; i<nCell; i++){
      u8 *pCell = findCell(pPage, i);
      if( eType==PTRMAP_OVERFLOW1 ){
        CellInfo info;
        parseCellPtr(pPage, pCell, &info);
        if( info.iOverflow ){
          if( iFrom==get4byte(&pCell[info.iOverflow]) ){
................................................................................
      }
      rc = allocatePage(pBt, &pFreeMemPage, &iFreePage, 0);
      if( rc!=SQLITE_OK ) goto autovacuum_out;
      assert( iFreePage<=origDbSize );
    }while( iFreePage>finDbSize );

    /* 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);
    if( rc!=SQLITE_OK ) goto autovacuum_out;
    pDbMemPage->pgno = iFreePage;

    /* If pDbPage was a btree-page, then it may have child pages and/or cells
    ** that point to overflow pages. The pointer map entries for all these
    ** pages need to be changed.
    **
    ** If pDbPage is an overflow page, then the first 4 bytes may store a
    ** pointer to a subsequent overflow page. If this is the case, then
    ** the pointer map needs to be updated for the subsequent overflow page.
    */
    if( eType==PTRMAP_BTREE ){
      rc = setChildPtrmaps(pDbMemPage);
      if( rc!=SQLITE_OK ) goto autovacuum_out;
    }else{
      Pgno nextOvfl = get4byte(pDbPage);
      if( nextOvfl!=0 ){
        assert( nextOvfl<=origDbSize );
        rc = ptrmapPut(pBt, nextOvfl, PTRMAP_OVERFLOW2, iFreePage);
        if( rc!=SQLITE_OK ) goto autovacuum_out;
      }
    }
    releasePage(pDbMemPage);
    pDbMemPage = 0;

    /* Fix the database pointer on page iPtrPage that pointed at iDbPage so
    ** that it points at iFreePage. Also fix the pointer map entry for
    ** iPtrPage.

Changes to test/autovacuum.test.

7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
..
24
25
26
27
28
29
30

31
32
33
34
35
36
37
38
39
40
41
#    May you find forgiveness for yourself and forgive others.
#    May you share freely, never taking more than you give.
#
#***********************************************************************
# This file implements regression tests for SQLite library.  The
# focus of this file is testing the SELECT statement.
#
# $Id: autovacuum.test,v 1.1 2004/11/02 12:56:41 danielk1977 Exp $

set testdir [file dirname $argv0]
source $testdir/tester.tcl

proc make_str {char len} {
  set str [string repeat $char. $len]
  return [string range $str 0 [expr $len-1]]
................................................................................
proc file_pages {} {
  return [expr [file size test.db] / 1024]
}

do_test autovacuum-1.1 {
  execsql {
    CREATE TABLE av1(a);

  }
} {}

set ENTRY_LEN 1100

set delete_orders [list]
lappend delete_orders {1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20}
lappend delete_orders {20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1} 
lappend delete_orders {8 18 2 4 14 11 13 3 10 7 9 5 12 17 19 15 20 6 16 1}
lappend delete_orders {10 3 11 17 19 20 7 4 13 6 1 14 16 12 9 18 8 15 5 2}








|







 







>



|







7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
..
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#    May you find forgiveness for yourself and forgive others.
#    May you share freely, never taking more than you give.
#
#***********************************************************************
# This file implements regression tests for SQLite library.  The
# focus of this file is testing the SELECT statement.
#
# $Id: autovacuum.test,v 1.2 2004/11/02 14:40:32 danielk1977 Exp $

set testdir [file dirname $argv0]
source $testdir/tester.tcl

proc make_str {char len} {
  set str [string repeat $char. $len]
  return [string range $str 0 [expr $len-1]]
................................................................................
proc file_pages {} {
  return [expr [file size test.db] / 1024]
}

do_test autovacuum-1.1 {
  execsql {
    CREATE TABLE av1(a);
    -- CREATE INDEX av1_idx ON av1(a);
  }
} {}

set ENTRY_LEN 3000

set delete_orders [list]
lappend delete_orders {1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20}
lappend delete_orders {20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1} 
lappend delete_orders {8 18 2 4 14 11 13 3 10 7 9 5 12 17 19 15 20 6 16 1}
lappend delete_orders {10 3 11 17 19 20 7 4 13 6 1 14 16 12 9 18 8 15 5 2}