/ Check-in [4e243337]
Login

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

Overview
Comment:Fix allocation of tables in an auto-vacuum database when the required root-page is on the free-list. (CVS 2065)
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1: 4e2433378e06210f0274c317c6d12b48236211fe
User & Date: danielk1977 2004-11-05 12:27:02
Context
2004-11-05
12:58
Auto-vacuum bug: Don't set meta(3) to a pointer-map page number when deleting a table. (CVS 2066) check-in: 44a015b3 user: danielk1977 tags: trunk
12:27
Fix allocation of tables in an auto-vacuum database when the required root-page is on the free-list. (CVS 2065) check-in: 4e243337 user: danielk1977 tags: trunk
09:19
Don't code an OP_Statement within sqlite3NestedParse(). Also a correction to the UPDATE statement used within destroyRootPage(). (CVS 2064) check-in: fdcc31f0 user: danielk1977 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
....
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
....
1718
1719
1720
1721
1722
1723
1724
1725
1726
1727
1728
1729
1730
1731
1732
1733
1734
1735
1736
1737
1738
1739
1740
1741
1742
1743
1744
1745
1746
1747
1748
1749
1750
1751
1752
1753
1754
1755
1756
1757
1758
1759
1760
1761
1762
1763
1764
1765
....
1768
1769
1770
1771
1772
1773
1774
1775
1776
1777
1778
1779
1780
1781
1782
....
2838
2839
2840
2841
2842
2843
2844




2845
2846






2847
2848
2849
2850
2851
2852
2853
2854
2855
2856

























2857
2858
2859










2860




2861



2862
2863
2864

2865
2866

2867
2868

2869
2870
2871


2872
2873

2874
2875
2876
2877











2878




































2879
2880

2881
2882
2883
2884
2885
2886
2887
2888
2889
2890


2891

2892
2893
2894

2895


2896
2897
2898
2899
2900

2901
2902
2903
2904
2905
2906
2907
2908
2909
2910
2911

2912




2913
2914
2915
2916
2917
2918
2919
....
2954
2955
2956
2957
2958
2959
2960
2961
2962
2963
2964
2965
2966
2967
2968
2969
2970
2971
2972
2973
2974
2975
....
3098
3099
3100
3101
3102
3103
3104
3105
3106
3107
3108
3109
3110
3111
3112
....
3706
3707
3708
3709
3710
3711
3712
3713
3714
3715
3716
3717
3718
3719
3720
....
3968
3969
3970
3971
3972
3973
3974
3975
3976
3977
3978
3979
3980
3981
3982
....
4237
4238
4239
4240
4241
4242
4243
4244
4245
4246
4247
4248
4249
4250
4251
4252
4253
4254
4255
4256
4257
4258
4259
4260
4261
4262
4263
4264
4265
4266
4267
4268
4269
4270
....
4275
4276
4277
4278
4279
4280
4281
4282
4283
4284
4285
4286
4287
4288
4289
....
4325
4326
4327
4328
4329
4330
4331
4332
4333
4334
4335
4336
4337
4338
4339
** 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.207 2004/11/05 03:56:01 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.
................................................................................
    rc = ptrmapPut(pBt, iFreePage, eType, iPtrPage);
    releasePage(pPtrPage);
  }
  return rc;
}

/* Forward declaration required by autoVacuumCommit(). */
static int allocatePage(Btree *, MemPage **, Pgno *, Pgno);

/*
** 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 */
  MemPage *pDbMemPage = 0;   /* "" */
  Pgno iPtrPage;             /* The page that contains a pointer to iDbPage */
  Pgno iFreePage;            /* The free-list page to move iDbPage to */
................................................................................
  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));

#if 0
  /* 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;
    }
  }
#endif

  /* 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.
    ** Instead, make sure the page is in the journal file.
    */
    if( eType==PTRMAP_FREEPAGE || PTRMAP_ISPAGE(pgsz, iDbPage) ){
      continue;
    }
    rc = getPage(pBt, iDbPage, &pDbMemPage);
    if( rc!=SQLITE_OK ) goto autovacuum_out;

................................................................................
    ** 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 );
    releasePage(pFreeMemPage);
    pFreeMemPage = 0;

    rc = relocatePage(pBt, pDbMemPage, eType, iPtrPage, iFreePage);
................................................................................
** an error.  *ppPage and *pPgno are undefined in the event of an error.
** Do not invoke sqlite3pager_unref() on *ppPage if an error is returned.
**
** If the "nearby" parameter is not 0, then a (feeble) effort is made to 
** locate a page close to the page number "nearby".  This can be used in an
** attempt to keep related pages close to each other in the database file,
** which in turn can make database access faster.




*/
static int allocatePage(Btree *pBt, MemPage **ppPage, Pgno *pPgno, Pgno nearby){






  MemPage *pPage1;
  int rc;
  int n;     /* Number of pages on the freelist */
  int k;     /* Number of leaves on the trunk of the freelist */

  pPage1 = pBt->pPage1;
  n = get4byte(&pPage1->aData[36]);
  if( n>0 ){
    /* There are pages on the freelist.  Reuse one of those pages. */
    MemPage *pTrunk;

























    rc = sqlite3pager_write(pPage1->aData);
    if( rc ) return rc;
    put4byte(&pPage1->aData[36], n-1);










    rc = getPage(pBt, get4byte(&pPage1->aData[32]), &pTrunk);




    if( rc ) return rc;



    rc = sqlite3pager_write(pTrunk->aData);
    if( rc ){
      releasePage(pTrunk);

      return rc;
    }

    k = get4byte(&pTrunk->aData[4]);
    if( k==0 ){

      /* The trunk has no leaves.  So extract the trunk page itself and
      ** use it as the newly allocated page */
      *pPgno = get4byte(&pPage1->aData[32]);


      memcpy(&pPage1->aData[32], &pTrunk->aData[0], 4);
      *ppPage = pTrunk;

      TRACE(("ALLOCATE: %d trunk - %d free pages left\n", *pPgno, n-1));
    }else if( k>pBt->usableSize/4 - 8 ){
      /* Value of k is out of range.  Database corruption */
      return SQLITE_CORRUPT; /* bkpt-CORRUPT */











    }else{




































      /* Extract a leaf from the trunk */
      int closest;

      unsigned char *aData = pTrunk->aData;
      if( nearby>0 ){
        int i, dist;
        closest = 0;
        dist = get4byte(&aData[8]) - nearby;
        if( dist<0 ) dist = -dist;
        for(i=1; i<k; i++){
          int d2 = get4byte(&aData[8+i*4]) - nearby;
          if( d2<0 ) d2 = -d2;
          if( d2<dist ) closest = i;


        }

      }else{
        closest = 0;
      }

      *pPgno = get4byte(&aData[8+closest*4]);


      if( *pPgno>sqlite3pager_pagecount(pBt->pPager) ){
        /* Free page off the end of the file */
        return SQLITE_CORRUPT; /* bkpt-CORRUPT */
      }
      TRACE(("ALLOCATE: %d was leaf %d of %d on trunk %d: %d more free pages\n",

             *pPgno, closest+1, k, pTrunk->pgno, n-1));
      if( closest<k-1 ){
        memcpy(&aData[8+closest*4], &aData[4+k*4], 4);
      }
      put4byte(&aData[4], k-1);
      rc = getPage(pBt, *pPgno, ppPage);
      releasePage(pTrunk);
      if( rc==SQLITE_OK ){
        sqlite3pager_dont_rollback((*ppPage)->aData);
        rc = sqlite3pager_write((*ppPage)->aData);
      }

    }




  }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) ){
................................................................................
  rc = sqlite3pager_write(pPage1->aData);
  if( rc ) return rc;
  n = get4byte(&pPage1->aData[36]);
  put4byte(&pPage1->aData[36], n+1);

#ifndef SQLITE_OMIT_AUTOVACUUM
  /* If the database supports auto-vacuum, write an entry in the pointer-map
  ** to indicate that the page is free. Also make sure the page is in
  ** the journal file.
  */
  if( pBt->autoVacuum ){
    rc = ptrmapPut(pBt, pPage->pgno, PTRMAP_FREEPAGE, 0);
    if( rc ) return rc;
    rc = sqlite3pager_write(pPage->aData);
    if( rc ) return rc;
  }
#endif

  if( n==0 ){
    /* This is the first free page */
    rc = sqlite3pager_write(pPage->aData);
    if( rc ) return rc;
................................................................................
  pPrior = &pCell[info.iOverflow];

  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 ){
................................................................................
    MemPage *pNew;
    if( i<nOld ){
      pNew = apNew[i] = apOld[i];
      pgnoNew[i] = pgnoOld[i];
      apOld[i] = 0;
      sqlite3pager_write(pNew->aData);
    }else{
      rc = allocatePage(pBt, &pNew, &pgnoNew[i], pgnoNew[i-1]);
      if( rc ) goto balance_cleanup;
      apNew[i] = pNew;
    }
    nNew++;
    zeroPage(pNew, pageFlags);
  }

................................................................................
  u8 *cdata;          /* Content of the child page */
  int hdr;            /* Offset to page header in parent */
  int brk;            /* Offset to content of first cell in parent */

  assert( pPage->pParent==0 );
  assert( pPage->nOverflow>0 );
  pBt = pPage->pBt;
  rc = allocatePage(pBt, &pChild, &pgnoChild, pPage->pgno);
  if( rc ) return rc;
  assert( sqlite3pager_iswriteable(pChild->aData) );
  usableSize = pBt->usableSize;
  data = pPage->aData;
  hdr = pPage->hdrOffset;
  brk = get2byte(&data[hdr+5]);
  cdata = pChild->aData;
................................................................................
    /* Must start a transaction first */
    return pBt->readOnly ? SQLITE_READONLY : SQLITE_ERROR;
  }
  if( pBt->readOnly ){
    return SQLITE_READONLY;
  }
#ifdef SQLITE_OMIT_AUTOVACUUM
  rc = allocatePage(pBt, &pRoot, &pgnoRoot, 1);
  if( rc ) return rc;
#else
  if( pBt->autoVacuum ){
    Pgno pgnoMove;      /* Move a page here to make room for the root-page */
    MemPage *pPageMove; /* The page to move to. */

    /* Run the auto-vacuum code to ensure the free-list is empty. This is
    ** not really necessary, but it avoids complications in dealing with
    ** a free-list in the code below.
    ** TODO: This may need to be revisited.
    ** TODO2: Actually this is no-good. running the auto-vacuum routine
    **        involves truncating the database, which means the journal-file
    **        must be synced(). No-good.
    */
/*
    rc = autoVacuumCommit(pBt);
    if( rc!=SQLITE_OK ) return rc;
*/

    /* Read the value of meta[3] from the database to determine where the
    ** root page of the new table should go. meta[3] is the largest root-page
    ** created so far, so the new root-page is (meta[3]+1).
    */
    rc = sqlite3BtreeGetMeta(pBt, 4, &pgnoRoot);
    if( rc!=SQLITE_OK ) return rc;
    pgnoRoot++;
................................................................................
    }
    assert( pgnoRoot>=3 );

    /* Allocate a page. The page that currently resides at pgnoRoot will
    ** be moved to the allocated page (unless the allocated page happens
    ** to reside at pgnoRoot).
    */
    rc = allocatePage(pBt, &pPageMove, &pgnoMove, 1);
    if( rc!=SQLITE_OK ){
      return rc;
    }

    if( pgnoMove!=pgnoRoot ){
      u8 eType;
      Pgno iPtrPage;
................................................................................
    }
    rc = sqlite3BtreeUpdateMeta(pBt, 4, pgnoRoot);
    if( rc ){
      releasePage(pRoot);
      return rc;
    }
  }else{
    rc = allocatePage(pBt, &pRoot, &pgnoRoot, 1);
    if( rc ) return rc;
  }
#endif
  assert( sqlite3pager_iswriteable(pRoot->aData) );
  zeroPage(pRoot, flags | PTF_LEAF);
  sqlite3pager_unref(pRoot->aData);
  *piTable = (int)pgnoRoot;







|







 







|











<







 







<


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












|







 







|







 







>
>
>
>

|
>
>
>
>
>
>









|
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>



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







 







|
<




<
<







 







|







 







|







 







|







 







|






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







 







|







 







|







5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
....
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
....
1717
1718
1719
1720
1721
1722
1723

1724
1725


















1726
1727
1728
1729
1730
1731
1732
1733
1734
1735
1736
1737
1738
1739
1740
1741
1742
1743
1744
1745
....
1748
1749
1750
1751
1752
1753
1754
1755
1756
1757
1758
1759
1760
1761
1762
....
2818
2819
2820
2821
2822
2823
2824
2825
2826
2827
2828
2829
2830
2831
2832
2833
2834
2835
2836
2837
2838
2839
2840
2841
2842
2843
2844
2845
2846
2847
2848
2849
2850
2851
2852
2853
2854
2855
2856
2857
2858
2859
2860
2861
2862
2863
2864
2865
2866
2867
2868
2869
2870
2871
2872
2873
2874
2875
2876
2877
2878
2879
2880
2881
2882
2883
2884
2885
2886
2887
2888
2889
2890
2891
2892
2893
2894
2895
2896
2897
2898
2899
2900
2901
2902
2903
2904
2905

2906
2907
2908
2909
2910
2911
2912
2913
2914
2915
2916
2917
2918
2919
2920
2921
2922
2923
2924
2925
2926
2927
2928
2929
2930
2931
2932
2933
2934
2935
2936
2937
2938
2939
2940
2941
2942
2943
2944
2945
2946
2947
2948
2949
2950
2951
2952
2953
2954
2955
2956
2957
2958
2959
2960
2961
2962
2963
2964
2965
2966
2967
2968
2969
2970
2971
2972
2973
2974
2975
2976
2977
2978
2979
2980
2981
2982
2983
2984
2985
2986
2987
2988
2989
2990
2991
2992
2993
2994
2995
2996
2997
2998

2999
3000
3001
3002
3003
3004
3005
3006
3007
3008
3009
3010
3011
3012
3013
3014
3015
....
3050
3051
3052
3053
3054
3055
3056
3057

3058
3059
3060
3061


3062
3063
3064
3065
3066
3067
3068
....
3191
3192
3193
3194
3195
3196
3197
3198
3199
3200
3201
3202
3203
3204
3205
....
3799
3800
3801
3802
3803
3804
3805
3806
3807
3808
3809
3810
3811
3812
3813
....
4061
4062
4063
4064
4065
4066
4067
4068
4069
4070
4071
4072
4073
4074
4075
....
4330
4331
4332
4333
4334
4335
4336
4337
4338
4339
4340
4341
4342
4343













4344
4345
4346
4347
4348
4349
4350
....
4355
4356
4357
4358
4359
4360
4361
4362
4363
4364
4365
4366
4367
4368
4369
....
4405
4406
4407
4408
4409
4410
4411
4412
4413
4414
4415
4416
4417
4418
4419
** 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.208 2004/11/05 12:27:02 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.
................................................................................
    rc = ptrmapPut(pBt, iFreePage, eType, iPtrPage);
    releasePage(pPtrPage);
  }
  return rc;
}

/* Forward declaration required by autoVacuumCommit(). */
static int allocatePage(Btree *, MemPage **, Pgno *, Pgno, u8);

/*
** 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 rc;           /* Return code */
  u8 eType;
  int pgsz = pBt->pageSize;  /* Page size for this database */
  Pgno iDbPage;              /* The database page to move */
  MemPage *pDbMemPage = 0;   /* "" */
  Pgno iPtrPage;             /* The page that contains a pointer to iDbPage */
  Pgno iFreePage;            /* The free-list page to move iDbPage to */
................................................................................
  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));



















  /* 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.
    ** TODO: Instead, make sure the page is in the journal file.
    */
    if( eType==PTRMAP_FREEPAGE || PTRMAP_ISPAGE(pgsz, iDbPage) ){
      continue;
    }
    rc = getPage(pBt, iDbPage, &pDbMemPage);
    if( rc!=SQLITE_OK ) goto autovacuum_out;

................................................................................
    ** allocatePage() routine.
    */
    do{
      if( pFreeMemPage ){
        releasePage(pFreeMemPage);
        pFreeMemPage = 0;
      }
      rc = allocatePage(pBt, &pFreeMemPage, &iFreePage, 0, 0);
      if( rc!=SQLITE_OK ) goto autovacuum_out;
      assert( iFreePage<=origSize );
    }while( iFreePage>finSize );
    releasePage(pFreeMemPage);
    pFreeMemPage = 0;

    rc = relocatePage(pBt, pDbMemPage, eType, iPtrPage, iFreePage);
................................................................................
** an error.  *ppPage and *pPgno are undefined in the event of an error.
** Do not invoke sqlite3pager_unref() on *ppPage if an error is returned.
**
** If the "nearby" parameter is not 0, then a (feeble) effort is made to 
** locate a page close to the page number "nearby".  This can be used in an
** attempt to keep related pages close to each other in the database file,
** which in turn can make database access faster.
**
** If the "exact" parameter is not 0, and the page-number nearby exists 
** anywhere on the free-list, then it is guarenteed to be returned. This
** is only used by auto-vacuum databases when allocating a new table.
*/
static int allocatePage(
  Btree *pBt, 
  MemPage **ppPage, 
  Pgno *pPgno, 
  Pgno nearby,
  u8 exact
){
  MemPage *pPage1;
  int rc;
  int n;     /* Number of pages on the freelist */
  int k;     /* Number of leaves on the trunk of the freelist */

  pPage1 = pBt->pPage1;
  n = get4byte(&pPage1->aData[36]);
  if( n>0 ){
    /* There are pages on the freelist.  Reuse one of those pages. */
    MemPage *pTrunk = 0;
    Pgno iTrunk;
    MemPage *pPrevTrunk = 0;
    u8 searchList = 0; /* If the free-list must be searched for 'nearby' */
    
    /* If the 'exact' parameter was true and a query of the pointer-map
    ** shows that the page 'nearby' is somewhere on the free-list, then
    ** the entire-list will be searched for that page.
    */
#ifndef SQLITE_OMIT_AUTOVACUUM
    if( exact ){
      u8 eType;
      assert( nearby>0 );
      assert( pBt->autoVacuum );
      rc = ptrmapGet(pBt, nearby, &eType, 0);
      if( rc ) return rc;
      if( eType==PTRMAP_FREEPAGE ){
        searchList = 1;
      }
      *pPgno = nearby;
    }
#endif

    /* Decrement the free-list count by 1. Set iTrunk to the index of the
    ** first free-list trunk page. iPrevTrunk is initially 1.
    */
    rc = sqlite3pager_write(pPage1->aData);
    if( rc ) return rc;
    put4byte(&pPage1->aData[36], n-1);

    /* The code within this loop is run only once if the 'searchList' variable
    ** is not true. Otherwise, it runs once for each trunk-page on the
    ** free-list until the page 'nearby' is located.
    */
    do {
      pPrevTrunk = pTrunk;
      if( pPrevTrunk ){
        iTrunk = get4byte(&pPrevTrunk->aData[0]);
      }else{
        iTrunk = get4byte(&pPage1->aData[32]);
      }
      rc = getPage(pBt, iTrunk, &pTrunk);
      if( rc ){
        releasePage(pPrevTrunk);
        return rc;
      }

      /* TODO: This should move to after the loop? */
      rc = sqlite3pager_write(pTrunk->aData);
      if( rc ){
        releasePage(pTrunk);
        releasePage(pPrevTrunk);
        return rc;
      }

      k = get4byte(&pTrunk->aData[4]);
      if( k==0 && !searchList ){
        /* The trunk has no leaves and the list is not being searched. 
        ** So extract the trunk page itself and use it as the newly 
        ** allocated page */

        assert( pPrevTrunk==0 );
        *pPgno = iTrunk;
        memcpy(&pPage1->aData[32], &pTrunk->aData[0], 4);
        *ppPage = pTrunk;
        pTrunk = 0;
        TRACE(("ALLOCATE: %d trunk - %d free pages left\n", *pPgno, n-1));
      }else if( k>pBt->usableSize/4 - 8 ){
        /* Value of k is out of range.  Database corruption */
        return SQLITE_CORRUPT; /* bkpt-CORRUPT */
#ifndef SQLITE_OMIT_AUTOVACUUM
      }else if( searchList && nearby==iTrunk ){
        /* The list is being searched and this trunk page is the page
        ** to allocate, regardless of whether it has leaves.
        */
        assert( *pPgno==iTrunk );
        *ppPage = pTrunk;
        searchList = 0;
        if( k==0 ){
          if( !pPrevTrunk ){
            memcpy(&pPage1->aData[32], &pTrunk->aData[0], 4);
          }else{
            memcpy(&pPrevTrunk->aData[0], &pTrunk->aData[0], 4);
          }
        }else{
          /* The trunk page is required by the caller but it contains 
          ** pointers to free-list leaves. The first leaf becomes a trunk
          ** page in this case.
          */
          MemPage *pNewTrunk;
          Pgno iNewTrunk = get4byte(&pTrunk->aData[8]);
          rc = getPage(pBt, iNewTrunk, &pNewTrunk);
          if( rc!=SQLITE_OK ){
            releasePage(pTrunk);
            releasePage(pPrevTrunk);
            return rc;
          }
          rc = sqlite3pager_write(pNewTrunk->aData);
          if( rc!=SQLITE_OK ){
            releasePage(pNewTrunk);
            releasePage(pTrunk);
            releasePage(pPrevTrunk);
            return rc;
          }
          memcpy(&pNewTrunk->aData[0], &pTrunk->aData[0], 4);
          put4byte(&pNewTrunk->aData[4], k-1);
          memcpy(&pNewTrunk->aData[8], &pTrunk->aData[12], (k-1)*4);
          if( !pPrevTrunk ){
            put4byte(&pPage1->aData[32], iNewTrunk);
          }else{
            put4byte(&pPrevTrunk->aData[0], iNewTrunk);
          }
          releasePage(pNewTrunk);
        }
        pTrunk = 0;
        TRACE(("ALLOCATE: %d trunk - %d free pages left\n", *pPgno, n-1));
#endif
      }else{
        /* Extract a leaf from the trunk */
        int closest;
        Pgno iPage;
        unsigned char *aData = pTrunk->aData;
        if( nearby>0 ){
          int i, dist;
          closest = 0;
          dist = get4byte(&aData[8]) - nearby;
          if( dist<0 ) dist = -dist;
          for(i=1; i<k; i++){
            int d2 = get4byte(&aData[8+i*4]) - nearby;
            if( d2<0 ) d2 = -d2;
            if( d2<dist ){
              closest = i;
              dist = d2;
            }
          }
        }else{
          closest = 0;
        }

        iPage = get4byte(&aData[8+closest*4]);
        if( !searchList || iPage==nearby ){
          *pPgno = iPage;
          if( *pPgno>sqlite3pager_pagecount(pBt->pPager) ){
            /* Free page off the end of the file */
            return SQLITE_CORRUPT; /* bkpt-CORRUPT */
          }
          TRACE(("ALLOCATE: %d was leaf %d of %d on trunk %d"
                 ": %d more free pages\n",
                 *pPgno, closest+1, k, pTrunk->pgno, n-1));
          if( closest<k-1 ){
            memcpy(&aData[8+closest*4], &aData[4+k*4], 4);
          }
          put4byte(&aData[4], k-1);
          rc = getPage(pBt, *pPgno, ppPage);

          if( rc==SQLITE_OK ){
            sqlite3pager_dont_rollback((*ppPage)->aData);
            rc = sqlite3pager_write((*ppPage)->aData);
          }
          searchList = 0;
        }
      }
      releasePage(pPrevTrunk);
    }while( searchList );
    releasePage(pTrunk);
  }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) ){
................................................................................
  rc = sqlite3pager_write(pPage1->aData);
  if( rc ) return rc;
  n = get4byte(&pPage1->aData[36]);
  put4byte(&pPage1->aData[36], n+1);

#ifndef SQLITE_OMIT_AUTOVACUUM
  /* If the database supports auto-vacuum, write an entry in the pointer-map
  ** to indicate that the page is free.

  */
  if( pBt->autoVacuum ){
    rc = ptrmapPut(pBt, pPage->pgno, PTRMAP_FREEPAGE, 0);
    if( rc ) return rc;


  }
#endif

  if( n==0 ){
    /* This is the first free page */
    rc = sqlite3pager_write(pPage->aData);
    if( rc ) return rc;
................................................................................
  pPrior = &pCell[info.iOverflow];

  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, 0);
#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 ){
................................................................................
    MemPage *pNew;
    if( i<nOld ){
      pNew = apNew[i] = apOld[i];
      pgnoNew[i] = pgnoOld[i];
      apOld[i] = 0;
      sqlite3pager_write(pNew->aData);
    }else{
      rc = allocatePage(pBt, &pNew, &pgnoNew[i], pgnoNew[i-1], 0);
      if( rc ) goto balance_cleanup;
      apNew[i] = pNew;
    }
    nNew++;
    zeroPage(pNew, pageFlags);
  }

................................................................................
  u8 *cdata;          /* Content of the child page */
  int hdr;            /* Offset to page header in parent */
  int brk;            /* Offset to content of first cell in parent */

  assert( pPage->pParent==0 );
  assert( pPage->nOverflow>0 );
  pBt = pPage->pBt;
  rc = allocatePage(pBt, &pChild, &pgnoChild, pPage->pgno, 0);
  if( rc ) return rc;
  assert( sqlite3pager_iswriteable(pChild->aData) );
  usableSize = pBt->usableSize;
  data = pPage->aData;
  hdr = pPage->hdrOffset;
  brk = get2byte(&data[hdr+5]);
  cdata = pChild->aData;
................................................................................
    /* Must start a transaction first */
    return pBt->readOnly ? SQLITE_READONLY : SQLITE_ERROR;
  }
  if( pBt->readOnly ){
    return SQLITE_READONLY;
  }
#ifdef SQLITE_OMIT_AUTOVACUUM
  rc = allocatePage(pBt, &pRoot, &pgnoRoot, 1, 0);
  if( rc ) return rc;
#else
  if( pBt->autoVacuum ){
    Pgno pgnoMove;      /* Move a page here to make room for the root-page */
    MemPage *pPageMove; /* The page to move to. */














    /* Read the value of meta[3] from the database to determine where the
    ** root page of the new table should go. meta[3] is the largest root-page
    ** created so far, so the new root-page is (meta[3]+1).
    */
    rc = sqlite3BtreeGetMeta(pBt, 4, &pgnoRoot);
    if( rc!=SQLITE_OK ) return rc;
    pgnoRoot++;
................................................................................
    }
    assert( pgnoRoot>=3 );

    /* Allocate a page. The page that currently resides at pgnoRoot will
    ** be moved to the allocated page (unless the allocated page happens
    ** to reside at pgnoRoot).
    */
    rc = allocatePage(pBt, &pPageMove, &pgnoMove, pgnoRoot, 1);
    if( rc!=SQLITE_OK ){
      return rc;
    }

    if( pgnoMove!=pgnoRoot ){
      u8 eType;
      Pgno iPtrPage;
................................................................................
    }
    rc = sqlite3BtreeUpdateMeta(pBt, 4, pgnoRoot);
    if( rc ){
      releasePage(pRoot);
      return rc;
    }
  }else{
    rc = allocatePage(pBt, &pRoot, &pgnoRoot, 1, 0);
    if( rc ) return rc;
  }
#endif
  assert( sqlite3pager_iswriteable(pRoot->aData) );
  zeroPage(pRoot, flags | PTF_LEAF);
  sqlite3pager_unref(pRoot->aData);
  *piTable = (int)pgnoRoot;

Changes to test/autovacuum.test.

7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
..
75
76
77
78
79
80
81

82
83
84
85
86
87
88
...
108
109
110
111
112
113
114
115
116











117
118
















119
120



121



122









123
124
125
126
127






128

129






130
131
132










133










134




135

136
137
138




139

140
141
142

143













144



145





146


147
148
#    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.6 2004/11/04 14:30:06 danielk1977 Exp $

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

# Return a string $len characters long. The returned string is $char repeated
# over and over. For example, [make_str abc 8] returns "abcabcab".
proc make_str {char len} {
................................................................................
  # Make sure the integrity check passes with the initial data.
  do_test autovacuum-1.$tn.1 {
    execsql {
      pragma integrity_check
    }
  } {ok}


  foreach delete $delete_order {
    # Delete one set of rows from the table.
    do_test autovacuum-1.$tn.($delete).1 {
      execsql "
        DELETE FROM av1 WHERE oid IN ([join $delete ,])
      "
    } {}
................................................................................

  # All rows have been deleted. Ensure the file has shrunk to 4 pages.
  do_test autovacuum-1.$tn.3 {
    file_pages
  } {4}
}

# Tests autovacuum-2.* test that root pages are allocated correctly at
# the start of the file.











do_test autovacuum-2.1 {
  for {set i 0} {$i<5} {incr i} {
















    execsql "
      INSERT INTO av1 VALUES('[make_str abc 1000]')



    "



  }









  file_pages 
} {14}

for {set i 5} {$i < 15} {incr i} {
  set tablename "av$i"






  

  do_test autovacuum-2.$i.2 {






    execsql "
      CREATE TABLE $tablename (a);
      SELECT rootpage FROM sqlite_master WHERE name = '$tablename';










    "










  } $i






  do_test autovacuum-2.$i.3 {
    file_pages 
  } [expr $i+10]






  do_test autovacuum-2.$i.4 {
    execsql {
      pragma integrity_check

    }













  } {ok}



}








finish_test








|







 







>







 







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

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


7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
..
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
...
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129

130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167


168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215

216
217
218
219
220
221
222
223

224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
#    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.7 2004/11/05 12:27:03 danielk1977 Exp $

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

# Return a string $len characters long. The returned string is $char repeated
# over and over. For example, [make_str abc 8] returns "abcabcab".
proc make_str {char len} {
................................................................................
  # Make sure the integrity check passes with the initial data.
  do_test autovacuum-1.$tn.1 {
    execsql {
      pragma integrity_check
    }
  } {ok}

# set btree_trace 1
  foreach delete $delete_order {
    # Delete one set of rows from the table.
    do_test autovacuum-1.$tn.($delete).1 {
      execsql "
        DELETE FROM av1 WHERE oid IN ([join $delete ,])
      "
    } {}
................................................................................

  # All rows have been deleted. Ensure the file has shrunk to 4 pages.
  do_test autovacuum-1.$tn.3 {
    file_pages
  } {4}
}

# Tests cases autovacuum-2.* test that root pages are allocated 
# and deallocated correctly at the start of the file. Operation is roughly as
# follows:
#
# autovacuum-2.1.*: Drop the tables that currently exist in the database.
# autovacuum-2.2.*: Create some tables. Ensure that data pages can be
#                   moved correctly to make space for new root-pages.
# autovacuum-2.3.*: Drop one of the tables just created (not the last one),
#                   and check that one of the other tables is moved to
#                   the free root-page location.
# autovacuum-2.4.*: Check that a table can be created correctly when the
#                   root-page it requires is on the free-list.
#
do_test autovacuum-2.1.1 {

  execsql {
    DROP TABLE av1;
  }
} {}
do_test autovacuum-2.1.2 {
  file_pages
} {1}

# Create a table and put some data in it.
do_test autovacuum-2.2.1 {
  execsql {
    CREATE TABLE av1(x);
    SELECT rootpage FROM sqlite_master ORDER BY rootpage;
  }
} {3}
do_test autovacuum-2.2.2 {
  execsql "
    INSERT INTO av1 VALUES('[make_str abc 3000]');
    INSERT INTO av1 VALUES('[make_str def 3000]');
    INSERT INTO av1 VALUES('[make_str ghi 3000]');
    INSERT INTO av1 VALUES('[make_str jkl 3000]');
  "
  set ::av1_data [db eval {select * from av1}]
  file_pages
} {15}

# Create another table. Check it is located immediately after the first.
# This test case moves the second page in an over-flow chain.
do_test autovacuum-2.2.3 {
  execsql {
    CREATE TABLE av2(x);
    SELECT rootpage FROM sqlite_master ORDER BY rootpage;
  }
} {3 4}
do_test autovacuum-2.2.4 {
  file_pages
} {16}



# Create another table. Check it is located immediately after the second.
# This test case moves the first page in an over-flow chain.
do_test autovacuum-2.2.5 {
  execsql {
    CREATE TABLE av3(x);
    SELECT rootpage FROM sqlite_master ORDER BY rootpage;
  }
} {3 4 5}
do_test autovacuum-2.2.6 {
  file_pages
} {17}

# Create another table. Check it is located immediately after the second.
# This test case moves a btree leaf page.
do_test autovacuum-2.2.7 {
  execsql {
    CREATE TABLE av4(x);
    SELECT rootpage FROM sqlite_master ORDER BY rootpage;
  }
} {3 4 5 6}
do_test autovacuum-2.2.8 {
  file_pages
} {18}
do_test autovacuum-2.2.9 {
  execsql {
    select * from av1
  }
} $av1_data

do_test autovacuum-2.3.1 {
  execsql {
    INSERT INTO av2 SELECT 'av1' || x FROM av1;
    INSERT INTO av3 SELECT 'av2' || x FROM av1;
    INSERT INTO av4 SELECT 'av3' || x FROM av1;
  }
  set ::av2_data [execsql {select x from av2}]
  set ::av3_data [execsql {select x from av3}]
  set ::av4_data [execsql {select x from av4}]
  file_pages
} {54}
do_test autovacuum-2.3.2 {
  execsql {
    DROP TABLE av2;
    SELECT rootpage FROM sqlite_master ORDER BY rootpage;
  }
} {3 4 5}
do_test autovacuum-2.3.3 {
  file_pages

} {41}
do_test autovacuum-2.3.4 {
  execsql {
    SELECT x FROM av3;
  }
} $::av3_data
do_test autovacuum-2.3.5 {
  execsql {

    SELECT x FROM av4;
  }
} $::av4_data

# Drop all the tables in the file. This puts all pages except the first 2
# (the sqlite_master root-page and the first pointer map page) on the 
# free-list.
do_test autovacuum-2.4.1 {
  execsql {
    DROP TABLE av1;
    DROP TABLE av3;
    BEGIN;
    DROP TABLE av4;
  }
  file_pages
} {15}
do_test autovacuum-2.4.2 {
  for {set i 3} {$i<=10} {incr i} {
    execsql "CREATE TABLE av$i (x)"
  }
  file_pages
} {15}
do_test autovacuum-2.4.3 {
  execsql {
    SELECT rootpage FROM sqlite_master ORDER by rootpage
  }
} {3 4 5 6 7 8 9 10}

finish_test