/ Check-in [491f8f96]
Login
SQLite training in Houston TX on 2019-11-05 (details)
Part of the 2019 Tcl Conference

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

Overview
Comment:Coverage testing for balance_quick() and balance_deeper(). (CVS 5382)
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1: 491f8f9613d2b886acad2ab8f631a4ec61ad698d
User & Date: danielk1977 2008-07-09 11:49:47
Context
2008-07-09
13:28
Begin adding the failsafe() macro. (CVS 5383) check-in: 8aae4fe7 user: drh tags: trunk
11:49
Coverage testing for balance_quick() and balance_deeper(). (CVS 5382) check-in: 491f8f96 user: danielk1977 tags: trunk
01:39
Additional test coverage in select.c and expr.c. (CVS 5381) check-in: c6cf0847 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
...
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
...
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
...
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
....
4641
4642
4643
4644
4645
4646
4647
4648
4649
4650
4651
4652
4653
4654
4655
4656
....
4794
4795
4796
4797
4798
4799
4800










4801
4802
4803
4804
4805
4806
4807
4808
4809

4810
4811
4812
4813
4814
4815
4816
4817
4818
4819
4820
....
4914
4915
4916
4917
4918
4919
4920

4921
4922
4923
4924
4925
4926
4927
....
5595
5596
5597
5598
5599
5600
5601
5602
5603
5604
5605
5606
5607
5608
5609
** 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.473 2008/07/08 19:34:07 drh Exp $
**
** This file implements a external (disk-based) database using BTrees.
** See the header comment on "btreeInt.h" for additional information.
** Including a description of file format and an overview of operation.
*/
#include "btreeInt.h"

................................................................................

/*
** Defragment the page given.  All Cells are moved to the
** end of the page and all free space is collected into one
** big FreeBlk that occurs in between the header and cell
** pointer array and the cell content area.
*/
static int defragmentPage(MemPage *pPage){
  int i;                     /* Loop counter */
  int pc;                    /* Address of a i-th cell */
  int addr;                  /* Offset of first byte after cell pointer array */
  int hdr;                   /* Offset to the page header */
  int size;                  /* Size of a cell */
  int usableSize;            /* Number of usable bytes on a page */
  int cellOffset;            /* Offset to the cell pointer array */
................................................................................
  assert( brk>=cellOffset+2*nCell );
  put2byte(&data[hdr+5], brk);
  data[hdr+1] = 0;
  data[hdr+2] = 0;
  data[hdr+7] = 0;
  addr = cellOffset+2*nCell;
  memset(&data[addr], 0, brk-addr);
  return SQLITE_OK;
}

/*
** Allocate nByte bytes of space on a page.
**
** Return the index into pPage->aData[] of the first byte of
** the new allocation. Or return 0 if there is not enough free
................................................................................
  /* Allocate memory from the gap in between the cell pointer array
  ** and the cell content area.
  */
  top = get2byte(&data[hdr+5]);
  nCell = get2byte(&data[hdr+3]);
  cellOffset = pPage->cellOffset;
  if( nFrag>=60 || cellOffset + 2*nCell > top - nByte ){
    if( defragmentPage(pPage) ) return 0;
    top = get2byte(&data[hdr+5]);
  }
  top -= nByte;
  assert( cellOffset + 2*nCell <= top );
  put2byte(&data[hdr+5], top);
  return top;
}
................................................................................
    data = pPage->aData;
    hdr = pPage->hdrOffset;
    top = get2byte(&data[hdr+5]);
    cellOffset = pPage->cellOffset;
    end = cellOffset + 2*pPage->nCell + 2;
    ins = cellOffset + 2*i;
    if( end > top - sz ){
      rc = defragmentPage(pPage);
      if( rc!=SQLITE_OK ) return rc;
      top = get2byte(&data[hdr+5]);
      assert( end + sz <= top );
    }
    idx = allocateSpace(pPage, sz);
    assert( idx>0 );
    assert( end <= get2byte(&data[hdr+5]) );
    pPage->nCell++;
................................................................................
  /* Set the parent of the newly allocated page to pParent. */
  pNew->pParent = pParent;
  sqlite3PagerRef(pParent->pDbPage);

  /* pPage is currently the right-child of pParent. Change this
  ** so that the right-child is the new page allocated above and
  ** pPage is the next-to-right child. 










  */
  assert( pPage->nCell>0 );
  pCell = findCell(pPage, pPage->nCell-1);
  sqlite3BtreeParseCellPtr(pPage, pCell, &info);
  rc = fillInCell(pParent, parentCell, 0, info.nKey, 0, 0, 0, &parentSize);
  if( rc!=SQLITE_OK ){
    return rc;
  }
  assert( parentSize<64 );

  rc = insertCell(pParent, parentIdx, parentCell, parentSize, 0, 4);
  if( rc!=SQLITE_OK ){
    return rc;
  }
  put4byte(findOverflowCell(pParent,parentIdx), pPage->pgno);
  put4byte(&pParent->aData[pParent->hdrOffset+8], pgnoNew);

#ifndef SQLITE_OMIT_AUTOVACUUM
  /* If this is an auto-vacuum database, update the pointer map
  ** with entries for the new page, and any pointer from the 
  ** cell on the page to an overflow page.
................................................................................
  assert( sqlite3PagerIswriteable(pPage->pDbPage) || pPage->nOverflow==1 );
  pBt = pPage->pBt;
  pParent = pPage->pParent;
  assert( pParent );
  if( SQLITE_OK!=(rc = sqlite3PagerWrite(pParent->pDbPage)) ){
    return rc;
  }

  TRACE(("BALANCE: begin page %d child of %d\n", pPage->pgno, pParent->pgno));

#ifndef SQLITE_OMIT_QUICKBALANCE
  /*
  ** A special case:  If a new entry has just been inserted into a
  ** table (that is, a btree with integer keys and all data at the leaves)
  ** and the new entry is the right-most entry in the tree (it has the
................................................................................
  if( pBt->autoVacuum ){
    int i;
    rc = ptrmapPut(pBt, pChild->pgno, PTRMAP_BTREE, pPage->pgno);
    if( rc ) goto balancedeeper_out;
    for(i=0; i<pChild->nCell; i++){
      rc = ptrmapPutOvfl(pChild, i);
      if( rc!=SQLITE_OK ){
        return rc;
      }
    }
  }
#endif
  rc = balance_nonroot(pChild);

balancedeeper_out:







|







 







|







 







<







 







|







 







|
<







 







>
>
>
>
>
>
>
>
>
>




|
<
<
<

>
|
<
<
<







 







>







 







|







5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
...
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
...
708
709
710
711
712
713
714

715
716
717
718
719
720
721
...
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
....
4640
4641
4642
4643
4644
4645
4646
4647

4648
4649
4650
4651
4652
4653
4654
....
4792
4793
4794
4795
4796
4797
4798
4799
4800
4801
4802
4803
4804
4805
4806
4807
4808
4809
4810
4811
4812
4813



4814
4815
4816



4817
4818
4819
4820
4821
4822
4823
....
4917
4918
4919
4920
4921
4922
4923
4924
4925
4926
4927
4928
4929
4930
4931
....
5599
5600
5601
5602
5603
5604
5605
5606
5607
5608
5609
5610
5611
5612
5613
** 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.474 2008/07/09 11:49:47 danielk1977 Exp $
**
** This file implements a external (disk-based) database using BTrees.
** See the header comment on "btreeInt.h" for additional information.
** Including a description of file format and an overview of operation.
*/
#include "btreeInt.h"

................................................................................

/*
** Defragment the page given.  All Cells are moved to the
** end of the page and all free space is collected into one
** big FreeBlk that occurs in between the header and cell
** pointer array and the cell content area.
*/
static void defragmentPage(MemPage *pPage){
  int i;                     /* Loop counter */
  int pc;                    /* Address of a i-th cell */
  int addr;                  /* Offset of first byte after cell pointer array */
  int hdr;                   /* Offset to the page header */
  int size;                  /* Size of a cell */
  int usableSize;            /* Number of usable bytes on a page */
  int cellOffset;            /* Offset to the cell pointer array */
................................................................................
  assert( brk>=cellOffset+2*nCell );
  put2byte(&data[hdr+5], brk);
  data[hdr+1] = 0;
  data[hdr+2] = 0;
  data[hdr+7] = 0;
  addr = cellOffset+2*nCell;
  memset(&data[addr], 0, brk-addr);

}

/*
** Allocate nByte bytes of space on a page.
**
** Return the index into pPage->aData[] of the first byte of
** the new allocation. Or return 0 if there is not enough free
................................................................................
  /* Allocate memory from the gap in between the cell pointer array
  ** and the cell content area.
  */
  top = get2byte(&data[hdr+5]);
  nCell = get2byte(&data[hdr+3]);
  cellOffset = pPage->cellOffset;
  if( nFrag>=60 || cellOffset + 2*nCell > top - nByte ){
    defragmentPage(pPage);
    top = get2byte(&data[hdr+5]);
  }
  top -= nByte;
  assert( cellOffset + 2*nCell <= top );
  put2byte(&data[hdr+5], top);
  return top;
}
................................................................................
    data = pPage->aData;
    hdr = pPage->hdrOffset;
    top = get2byte(&data[hdr+5]);
    cellOffset = pPage->cellOffset;
    end = cellOffset + 2*pPage->nCell + 2;
    ins = cellOffset + 2*i;
    if( end > top - sz ){
      defragmentPage(pPage);

      top = get2byte(&data[hdr+5]);
      assert( end + sz <= top );
    }
    idx = allocateSpace(pPage, sz);
    assert( idx>0 );
    assert( end <= get2byte(&data[hdr+5]) );
    pPage->nCell++;
................................................................................
  /* Set the parent of the newly allocated page to pParent. */
  pNew->pParent = pParent;
  sqlite3PagerRef(pParent->pDbPage);

  /* pPage is currently the right-child of pParent. Change this
  ** so that the right-child is the new page allocated above and
  ** pPage is the next-to-right child. 
  **
  ** Ignore the return value of the call to fillInCell(). fillInCell()
  ** may only return other than SQLITE_OK if it is required to allocate
  ** one or more overflow pages. Since an internal table B-Tree cell 
  ** may never spill over onto an overflow page (it is a maximum of 
  ** 13 bytes in size), it is not neccessary to check the return code.
  **
  ** Similarly, the insertCell() function cannot fail if the page
  ** being inserted into is already writable and the cell does not 
  ** contain an overflow pointer. So ignore this return code too.
  */
  assert( pPage->nCell>0 );
  pCell = findCell(pPage, pPage->nCell-1);
  sqlite3BtreeParseCellPtr(pPage, pCell, &info);
  fillInCell(pParent, parentCell, 0, info.nKey, 0, 0, 0, &parentSize);



  assert( parentSize<64 );
  assert( sqlite3PagerIswriteable(pParent->pDbPage) );
  insertCell(pParent, parentIdx, parentCell, parentSize, 0, 4);



  put4byte(findOverflowCell(pParent,parentIdx), pPage->pgno);
  put4byte(&pParent->aData[pParent->hdrOffset+8], pgnoNew);

#ifndef SQLITE_OMIT_AUTOVACUUM
  /* If this is an auto-vacuum database, update the pointer map
  ** with entries for the new page, and any pointer from the 
  ** cell on the page to an overflow page.
................................................................................
  assert( sqlite3PagerIswriteable(pPage->pDbPage) || pPage->nOverflow==1 );
  pBt = pPage->pBt;
  pParent = pPage->pParent;
  assert( pParent );
  if( SQLITE_OK!=(rc = sqlite3PagerWrite(pParent->pDbPage)) ){
    return rc;
  }

  TRACE(("BALANCE: begin page %d child of %d\n", pPage->pgno, pParent->pgno));

#ifndef SQLITE_OMIT_QUICKBALANCE
  /*
  ** A special case:  If a new entry has just been inserted into a
  ** table (that is, a btree with integer keys and all data at the leaves)
  ** and the new entry is the right-most entry in the tree (it has the
................................................................................
  if( pBt->autoVacuum ){
    int i;
    rc = ptrmapPut(pBt, pChild->pgno, PTRMAP_BTREE, pPage->pgno);
    if( rc ) goto balancedeeper_out;
    for(i=0; i<pChild->nCell; i++){
      rc = ptrmapPutOvfl(pChild, i);
      if( rc!=SQLITE_OK ){
        goto balancedeeper_out;
      }
    }
  }
#endif
  rc = balance_nonroot(pChild);

balancedeeper_out:

Changes to test/ioerr.test.

11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
...
324
325
326
327
328
329
330

331










































































332
333
# This file implements regression tests for SQLite library.  The
# focus of this file is testing for correct handling of I/O errors
# such as writes failing because the disk is full.
# 
# The tests in this file use special facilities that are only
# available in the SQLite test fixture.
#
# $Id: ioerr.test,v 1.39 2008/07/08 17:13:59 danielk1977 Exp $

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

# If SQLITE_DEFAULT_AUTOVACUUM is set to true, then a simulated IO error
# on the 8th IO operation in the SQL script below doesn't report an error.
#
................................................................................
  db eval { PRAGMA page_size = 1024 }
  db eval { CREATE TABLE t1(x) }
  db eval { INSERT INTO t1 VALUES(randomblob(1100)); }
} -tclbody {
  db eval { INSERT INTO t1 VALUES(randomblob(2000)); }
}
sqlite3_simulate_device -char {} -sectorsize 0












































































finish_test








|







 







>

>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>


11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
...
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
# This file implements regression tests for SQLite library.  The
# focus of this file is testing for correct handling of I/O errors
# such as writes failing because the disk is full.
# 
# The tests in this file use special facilities that are only
# available in the SQLite test fixture.
#
# $Id: ioerr.test,v 1.40 2008/07/09 11:49:48 danielk1977 Exp $

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

# If SQLITE_DEFAULT_AUTOVACUUM is set to true, then a simulated IO error
# on the 8th IO operation in the SQL script below doesn't report an error.
#
................................................................................
  db eval { PRAGMA page_size = 1024 }
  db eval { CREATE TABLE t1(x) }
  db eval { INSERT INTO t1 VALUES(randomblob(1100)); }
} -tclbody {
  db eval { INSERT INTO t1 VALUES(randomblob(2000)); }
}
sqlite3_simulate_device -char {} -sectorsize 0
catch {db close}

do_ioerr_test ioerr-13 -ckrefcount true -erc 1 -sqlprep {
  PRAGMA auto_vacuum = incremental;
  CREATE TABLE t1(x);
  CREATE TABLE t2(x);
  INSERT INTO t2 VALUES(randomblob(1500));
  INSERT INTO t2 SELECT randomblob(1500) FROM t2;
  INSERT INTO t2 SELECT randomblob(1500) FROM t2;
  INSERT INTO t2 SELECT randomblob(1500) FROM t2;
  INSERT INTO t2 SELECT randomblob(1500) FROM t2;
  INSERT INTO t2 SELECT randomblob(1500) FROM t2;
  INSERT INTO t2 SELECT randomblob(1500) FROM t2;
  INSERT INTO t2 SELECT randomblob(1500) FROM t2;
  INSERT INTO t2 SELECT randomblob(1500) FROM t2;
  INSERT INTO t1 VALUES(randomblob(20));
  INSERT INTO t1 SELECT x FROM t1;
  INSERT INTO t1 SELECT x FROM t1;
  INSERT INTO t1 SELECT x FROM t1;
  INSERT INTO t1 SELECT x FROM t1;
  INSERT INTO t1 SELECT x FROM t1;
  INSERT INTO t1 SELECT x FROM t1;             /* 64 entries in t1 */
  INSERT INTO t1 SELECT x FROM t1 LIMIT 14;    /* 78 entries in t1 */
  DELETE FROM t2 WHERE rowid = 3;
} -sqlbody {
  -- This statement uses the balance_quick() optimization. The new page
  -- is appended to the database file. But the overflow page used by
  -- the new record will be positioned near the start of the database
  -- file, in the gap left by the "DELETE FROM t2 WHERE rowid=3" statement
  -- above.
  --
  -- The point of this is that the statement wil need to update two pointer
  -- map pages. Which introduces another opportunity for an IO error.
  --
  INSERT INTO t1 VALUES(randomblob(2000));
}

do_ioerr_test ioerr-14 -ckrefcount true -erc 1 -sqlprep {
  PRAGMA auto_vacuum = incremental;
  CREATE TABLE t1(x);
  CREATE TABLE t2(x);
  INSERT INTO t2 VALUES(randomblob(1500));
  INSERT INTO t2 SELECT randomblob(1500) FROM t2;
  INSERT INTO t2 SELECT randomblob(1500) FROM t2;
  INSERT INTO t2 SELECT randomblob(1500) FROM t2;
  INSERT INTO t2 SELECT randomblob(1500) FROM t2;
  INSERT INTO t2 SELECT randomblob(1500) FROM t2;
  INSERT INTO t2 SELECT randomblob(1500) FROM t2;
  INSERT INTO t2 SELECT randomblob(1500) FROM t2;
  INSERT INTO t2 SELECT randomblob(1500) FROM t2;

  -- This statement inserts a row into t1 with an overflow page at the
  -- end of the file. A long way from its parent (the root of t1).
  INSERT INTO t1 VALUES(randomblob(1500));
  DELETE FROM t2 WHERE rowid<10;
} -sqlbody {
  -- This transaction will cause the root-page of table t1 to divide
  -- (by calling balance_deeper()). When it does, the "parent" page of the
  -- overflow page inserted in the -sqlprep block above will change and
  -- the corresponding pointer map page be updated. This test case attempts
  -- to cause an IO error during the pointer map page update.
  --
  BEGIN;
  INSERT INTO t1 VALUES(randomblob(100));
  INSERT INTO t1 VALUES(randomblob(100));
  INSERT INTO t1 VALUES(randomblob(100));
  INSERT INTO t1 VALUES(randomblob(100));
  INSERT INTO t1 VALUES(randomblob(100));
  INSERT INTO t1 VALUES(randomblob(100));
  INSERT INTO t1 VALUES(randomblob(100));
  INSERT INTO t1 VALUES(randomblob(100));
  INSERT INTO t1 VALUES(randomblob(100));
  INSERT INTO t1 VALUES(randomblob(100));
  COMMIT;
}

finish_test