/ Check-in [d0356dee]
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:Turn on quick-balance by default. (CVS 2221)
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1: d0356dee55bd43f361ede1344e90d1ba6b5cde1e
User & Date: drh 2005-01-16 23:21:00
Context
2005-01-17
01:33
Have sqlite3pager_get() return SQLITE_CORRUPT for a page number greater than 2^31. (CVS 2222) check-in: feb49d10 user: danielk1977 tags: trunk
2005-01-16
23:21
Turn on quick-balance by default. (CVS 2221) check-in: d0356dee user: drh tags: trunk
20:47
Drop support for MAC OS9. SQLite 3 has never worked for that OS because the developers do not have access to a machine running it and nobody from the community has stepped forward to provide a port. By moving the os_mac.c file into the attic, we make the lack of support official. (CVS 2220) check-in: de9ad673 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
...
354
355
356
357
358
359
360













361
362
363
364
365
366
367
368
369
370
371
372
...
416
417
418
419
420
421
422
423


424
425
426
427
428





429
430
431
432
433
434
435
...
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
...
468
469
470
471
472
473
474
475

476
477
478
479
480
481
482
483
484
485
486
487
488
....
1559
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
....
3567
3568
3569
3570
3571
3572
3573

3574
3575
3576
3577
3578
3579
3580
....
3654
3655
3656
3657
3658
3659
3660

3661
3662
3663
3664
3665
3666
3667
....
3743
3744
3745
3746
3747
3748
3749
3750
3751
3752
3753
3754
3755
3756
3757
** 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.237 2005/01/16 11:07:07 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.
................................................................................
  MemPage *pPage;           /* Page that contains the entry */
  int idx;                  /* Index of the entry in pPage->aCell[] */
  CellInfo info;            /* A parse of the cell we are pointing at */
  u8 wrFlag;                /* True if writable */
  u8 isValid;               /* TRUE if points to a valid entry */
};














/*
** Forward declaration
*/
static int checkReadLocks(Btree*,Pgno,BtCursor*);


/*
** Read or write a two- and four-byte big-endian integer values.
*/
static u32 get2byte(unsigned char *p){
  return (p[0]<<8) | p[1];
}
................................................................................
** this test.
*/
#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
** of the page-number depends on the type, as follows:





**
** PTRMAP_ROOTPAGE: The database page is a root-page. The page-number is not
**                  used in this case.
**
** PTRMAP_FREEPAGE: The database page is an unused (free) page. The page-number 
**                  is not used in this case.
**
................................................................................
/*
** Write an entry into the pointer map.
**
** This routine updates the pointer map entry for page number 'key'
** so that it maps to type 'eType' and parent page number 'pgno'.
** An error code is returned if something goes wrong, otherwise SQLITE_OK.
*/
static int ptrmapPut(Btree *pBt, Pgno key, u8 eType, Pgno pgno){
  u8 *pPtrmap;    /* The pointer map page */
  Pgno iPtrmap;   /* The pointer map page number */
  int offset;     /* Offset in pointer map page */
  int rc;

  assert( pBt->autoVacuum );
  assert( key!=0 );
................................................................................
  iPtrmap = PTRMAP_PAGENO(pBt->usableSize, key);
  rc = sqlite3pager_get(pBt->pPager, iPtrmap, (void **)&pPtrmap);
  if( rc!=SQLITE_OK ){
    return rc;
  }
  offset = PTRMAP_PTROFFSET(pBt->usableSize, key);

  if( eType!=pPtrmap[offset] || get4byte(&pPtrmap[offset+1])!=pgno ){

    rc = sqlite3pager_write(pPtrmap);
    if( rc!=0 ){
      return rc;
    }
    pPtrmap[offset] = eType;
    put4byte(&pPtrmap[offset+1], pgno);
  }

  sqlite3pager_unref(pPtrmap);
  return SQLITE_OK;
}

/*
................................................................................
    if( wrflag ) pBt->inStmt = 0;
  }else{
    unlockBtreeIfUnused(pBt);
  }
  return rc;
}

/*
** The TRACE macro will print high-level status information about the
** btree operation when the global variable sqlite3_btree_trace is
** enabled.
*/
#if SQLITE_TEST
# define TRACE(X)   if( sqlite3_btree_trace )\
                        { sqlite3DebugPrintf X; fflush(stdout); }
#else
# define TRACE(X)
#endif
int sqlite3_btree_trace=0;  /* True to enable tracing */

#ifndef SQLITE_OMIT_AUTOVACUUM

/*
** Set the pointer-map entries for all children of page pPage. Also, if
** pPage contains cells that point to overflow pages, set the pointer
** map entries for the overflow pages as well.
*/
................................................................................
*/
#define NN 1             /* Number of neighbors on either side of pPage */
#define NB (NN*2+1)      /* Total pages involved in the balance */

/* Forward reference */
static int balance(MemPage*, int);


/*
** This version of balance() handles the common special case where
** a new entry is being inserted on the extreme right-end of the
** tree, in other words, when the new entry will become the largest
** entry in the tree.
**
** Instead of trying balance the 3 right-most leaf pages, just add
................................................................................

  /* Release the reference to the new page and balance the parent page,
  ** in case the divider cell inserted caused it to become overfull.
  */
  releasePage(pNew);
  return balance(pParent, 0);
}


/*
** The ISAUTOVACUUM macro is used within balance_nonroot() to determine
** if the database supports auto-vacuum or not. Because it is used
** within an expression that is an argument to another macro 
** (sqliteMallocRaw), it is not possible to use conditional compilation.
** So, this macro is defined instead.
................................................................................
  assert( sqlite3pager_iswriteable(pPage->aData) );
  pBt = pPage->pBt;
  pParent = pPage->pParent;
  sqlite3pager_write(pParent->aData);
  assert( pParent );
  TRACE(("BALANCE: begin page %d child of %d\n", pPage->pgno, pParent->pgno));

#ifdef SQLITE_BALANCE_QUICK
  /*
  ** 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)
  ** an the new entry is the right-most entry in the tree (it has the
  ** largest key) then use the special balance_quick() routine for
  ** balancing.  balance_quick() is much faster and results in a tighter
  ** packing of data in the common case.







|







 







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




<







 







|
>
>
|
|
|
|
<
>
>
>
>
>







 







|







 







|
>





|







 







<
<
<
<
<
<
<
<
<
<
<
<
<







 







>







 







>







 







|







5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
...
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
...
428
429
430
431
432
433
434
435
436
437
438
439
440
441

442
443
444
445
446
447
448
449
450
451
452
453
...
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
...
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
....
1578
1579
1580
1581
1582
1583
1584













1585
1586
1587
1588
1589
1590
1591
....
3573
3574
3575
3576
3577
3578
3579
3580
3581
3582
3583
3584
3585
3586
3587
....
3661
3662
3663
3664
3665
3666
3667
3668
3669
3670
3671
3672
3673
3674
3675
....
3751
3752
3753
3754
3755
3756
3757
3758
3759
3760
3761
3762
3763
3764
3765
** 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.238 2005/01/16 23:21:00 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.
................................................................................
  MemPage *pPage;           /* Page that contains the entry */
  int idx;                  /* Index of the entry in pPage->aCell[] */
  CellInfo info;            /* A parse of the cell we are pointing at */
  u8 wrFlag;                /* True if writable */
  u8 isValid;               /* TRUE if points to a valid entry */
};

/*
** The TRACE macro will print high-level status information about the
** btree operation when the global variable sqlite3_btree_trace is
** enabled.
*/
#if SQLITE_TEST
# define TRACE(X)   if( sqlite3_btree_trace )\
                        { sqlite3DebugPrintf X; fflush(stdout); }
#else
# define TRACE(X)
#endif
int sqlite3_btree_trace=0;  /* True to enable tracing */

/*
** Forward declaration
*/
static int checkReadLocks(Btree*,Pgno,BtCursor*);


/*
** Read or write a two- and four-byte big-endian integer values.
*/
static u32 get2byte(unsigned char *p){
  return (p[0]<<8) | p[1];
}
................................................................................
** this test.
*/
#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 identifies the parent page for
** each child page in the database file.  The parent page is the page that
** contains a pointer to the child.  Every page in the database contains
** 0 or 1 parent pages.  (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 parent page number.
** The PTRMAP_XXX identifiers below are the valid types.

**
** The purpose of the pointer map is to facility moving pages from one
** position in the file to another as part of autovacuum.  When a page
** is moved, the pointer in its parent must be updated to point to the
** new location.  The pointer map is used to locate the parent page quickly.
**
** PTRMAP_ROOTPAGE: The database page is a root-page. The page-number is not
**                  used in this case.
**
** PTRMAP_FREEPAGE: The database page is an unused (free) page. The page-number 
**                  is not used in this case.
**
................................................................................
/*
** Write an entry into the pointer map.
**
** This routine updates the pointer map entry for page number 'key'
** so that it maps to type 'eType' and parent page number 'pgno'.
** An error code is returned if something goes wrong, otherwise SQLITE_OK.
*/
static int ptrmapPut(Btree *pBt, Pgno key, u8 eType, Pgno parent){
  u8 *pPtrmap;    /* The pointer map page */
  Pgno iPtrmap;   /* The pointer map page number */
  int offset;     /* Offset in pointer map page */
  int rc;

  assert( pBt->autoVacuum );
  assert( key!=0 );
................................................................................
  iPtrmap = PTRMAP_PAGENO(pBt->usableSize, key);
  rc = sqlite3pager_get(pBt->pPager, iPtrmap, (void **)&pPtrmap);
  if( rc!=SQLITE_OK ){
    return rc;
  }
  offset = PTRMAP_PTROFFSET(pBt->usableSize, key);

  if( eType!=pPtrmap[offset] || get4byte(&pPtrmap[offset+1])!=parent ){
    TRACE(("PTRMAP_UPDATE: %d->(%d,%d)\n", key, eType, parent));
    rc = sqlite3pager_write(pPtrmap);
    if( rc!=0 ){
      return rc;
    }
    pPtrmap[offset] = eType;
    put4byte(&pPtrmap[offset+1], parent);
  }

  sqlite3pager_unref(pPtrmap);
  return SQLITE_OK;
}

/*
................................................................................
    if( wrflag ) pBt->inStmt = 0;
  }else{
    unlockBtreeIfUnused(pBt);
  }
  return rc;
}














#ifndef SQLITE_OMIT_AUTOVACUUM

/*
** Set the pointer-map entries for all children of page pPage. Also, if
** pPage contains cells that point to overflow pages, set the pointer
** map entries for the overflow pages as well.
*/
................................................................................
*/
#define NN 1             /* Number of neighbors on either side of pPage */
#define NB (NN*2+1)      /* Total pages involved in the balance */

/* Forward reference */
static int balance(MemPage*, int);

#ifndef SQLITE_OMIT_QUICKBALANCE
/*
** This version of balance() handles the common special case where
** a new entry is being inserted on the extreme right-end of the
** tree, in other words, when the new entry will become the largest
** entry in the tree.
**
** Instead of trying balance the 3 right-most leaf pages, just add
................................................................................

  /* Release the reference to the new page and balance the parent page,
  ** in case the divider cell inserted caused it to become overfull.
  */
  releasePage(pNew);
  return balance(pParent, 0);
}
#endif /* SQLITE_OMIT_QUICKBALANCE */

/*
** The ISAUTOVACUUM macro is used within balance_nonroot() to determine
** if the database supports auto-vacuum or not. Because it is used
** within an expression that is an argument to another macro 
** (sqliteMallocRaw), it is not possible to use conditional compilation.
** So, this macro is defined instead.
................................................................................
  assert( sqlite3pager_iswriteable(pPage->aData) );
  pBt = pPage->pBt;
  pParent = pPage->pParent;
  sqlite3pager_write(pParent->aData);
  assert( pParent );
  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)
  ** an the new entry is the right-most entry in the tree (it has the
  ** largest key) then use the special balance_quick() routine for
  ** balancing.  balance_quick() is much faster and results in a tighter
  ** packing of data in the common case.

Changes to test/corrupt.test.

9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
..
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59


60
61
62
63
64
65



66
67
68
69
70
71
72
73
..
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
#
#***********************************************************************
# This file implements regression tests for SQLite library.
#
# This file implements tests to make sure SQLite does not crash or
# segfault if it sees a corrupt database file.
#
# $Id: corrupt.test,v 1.1 2004/08/30 16:52:19 drh Exp $

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

# Construct a large database for testing.
#
do_test corrupt-1.1 {
................................................................................
    CREATE TABLE t2 AS SELECT * FROM t1;
    DELETE FROM t2 WHERE rowid%5!=0;
    COMMIT;
    PRAGMA integrity_check;
  }
} {ok}

# Copy a file 
#
proc copy_file {from to} {
  set f [open $from]
  fconfigure $f -translation binary
  set t [open $to w]
  fconfigure $t -translation binary
  puts -nonewline $t [read $f [file size $from]]
  close $t
  close $f
}

# Setup for the tests.


copy_file test.db test.bu
set fsize [file size test.db]
set junk "abcdefghijklmnopqrstuvwxyz0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"
while {[string length $junk]<256} {append junk $junk}
set junk [string range $junk 0 255]





for {set i [expr {1*256}]} {$i<$fsize-256} {incr i 256} {
  set tn [expr {$i/256}]
  db close
  copy_file test.bu test.db
  set fd [open test.db r+]
  fconfigure $fd -translation binary
  seek $fd $i
................................................................................
    catchsql {CREATE TABLE t3 AS SELECT * FROM t1}
    set x {}
  } {}
  do_test corrupt-2.$tn.6 {
    catchsql {DROP TABLE t1}
    set x {}
  } {}
if {$tn==724} btree_breakpoint
  do_test corrupt-2.$tn.7 {
    catchsql {PRAGMA integrity_check}
    set x {}
  } {}
}  

finish_test







|







 







|











|
>
>






>
>
>
|







 







<







9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
..
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
...
100
101
102
103
104
105
106

107
108
109
110
111
112
113
#
#***********************************************************************
# This file implements regression tests for SQLite library.
#
# This file implements tests to make sure SQLite does not crash or
# segfault if it sees a corrupt database file.
#
# $Id: corrupt.test,v 1.2 2005/01/16 23:21:00 drh Exp $

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

# Construct a large database for testing.
#
do_test corrupt-1.1 {
................................................................................
    CREATE TABLE t2 AS SELECT * FROM t1;
    DELETE FROM t2 WHERE rowid%5!=0;
    COMMIT;
    PRAGMA integrity_check;
  }
} {ok}

# Copy file $from into $to
#
proc copy_file {from to} {
  set f [open $from]
  fconfigure $f -translation binary
  set t [open $to w]
  fconfigure $t -translation binary
  puts -nonewline $t [read $f [file size $from]]
  close $t
  close $f
}

# Setup for the tests.  Make a backup copy of the good database in test.bu.
# Create a string of garbage data that is 256 bytes long.
#
copy_file test.db test.bu
set fsize [file size test.db]
set junk "abcdefghijklmnopqrstuvwxyz0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"
while {[string length $junk]<256} {append junk $junk}
set junk [string range $junk 0 255]

# Go through the database and write garbage data into each 256 segment
# of the file.  Then do various operations on the file to make sure that
# the database engine can recover gracefully from the corruption.
#
for {set i [expr {1*256}]} {$i<$fsize-256} {incr i 256} {
  set tn [expr {$i/256}]
  db close
  copy_file test.bu test.db
  set fd [open test.db r+]
  fconfigure $fd -translation binary
  seek $fd $i
................................................................................
    catchsql {CREATE TABLE t3 AS SELECT * FROM t1}
    set x {}
  } {}
  do_test corrupt-2.$tn.6 {
    catchsql {DROP TABLE t1}
    set x {}
  } {}

  do_test corrupt-2.$tn.7 {
    catchsql {PRAGMA integrity_check}
    set x {}
  } {}
}  

finish_test