SQLite

Check-in [40249ed19c]
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
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1: 40249ed19cd53cb61f9575d8165316faf2627479
User & Date: danielk1977 2004-11-02 14:40:32.000
Context
2004-11-02
18:05
Get btree.c to compile with -DNDEBUG=1. (CVS 2040) (check-in: 8378c144c1 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: 40249ed19c user: danielk1977 tags: trunk)
14:24
Require that the page size be a power of 2. (CVS 2038) (check-in: c33b34dbe9 user: drh tags: trunk)
Changes
Unified Diff Ignore Whitespace Patch
Changes to src/btree.c.
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.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.











|







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.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.
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
**
** 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]) ){







>

|








<
<







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
**
** 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]) ){
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
      }
      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.







|
|









>
>
>
>




>
>
>
>
>
>
>







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
      }
      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.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

31
32
33
34
35
36
37
38
39
40
41
# 2001 September 15
#
# 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.
#
#***********************************************************************
# 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}














|
















>



|







1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
# 2001 September 15
#
# 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.
#
#***********************************************************************
# 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}