SQLite

Check-in [d6986d1e7c]
Login

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

Overview
Comment:Fixes to the overflow-chain optization of (3672). (CVS 3674)
Downloads: Tarball | ZIP archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1: d6986d1e7cba1d114fa06c5560ffc6bb1feb7389
User & Date: drh 2007-03-06 15:53:44.000
Context
2007-03-06
16:03
Catch an out-of-memory condition in vacuum code. (Bug in (3373)). (CVS 3675) (check-in: 302ec76857 user: danielk1977 tags: trunk)
15:53
Fixes to the overflow-chain optization of (3672). (CVS 3674) (check-in: d6986d1e7c user: drh tags: trunk)
13:46
Use heap instead of stack for large buffers in the pager. Fix for #2262. (CVS 3673) (check-in: dfe1dffa45 user: danielk1977 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.337 2007/03/06 11:42:19 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.338 2007/03/06 15:53:44 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.
361
362
363
364
365
366
367

368
369
370
371
372
373
374
** based on information extract from the raw disk page.
*/
typedef struct CellInfo CellInfo;
struct CellInfo {
  u8 *pCell;     /* Pointer to the start of cell content */
  i64 nKey;      /* The key for INTKEY tables, or number of bytes in key */
  u32 nData;     /* Number of bytes of data */

  u16 nHeader;   /* Size of the cell content header in bytes */
  u16 nLocal;    /* Amount of payload held locally */
  u16 iOverflow; /* Offset to overflow page number.  Zero if no overflow */
  u16 nSize;     /* Size of the cell content on the main b-tree page */
};

/*







>







361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
** based on information extract from the raw disk page.
*/
typedef struct CellInfo CellInfo;
struct CellInfo {
  u8 *pCell;     /* Pointer to the start of cell content */
  i64 nKey;      /* The key for INTKEY tables, or number of bytes in key */
  u32 nData;     /* Number of bytes of data */
  u32 nPayload;  /* Total amount of payload */
  u16 nHeader;   /* Size of the cell content header in bytes */
  u16 nLocal;    /* Amount of payload held locally */
  u16 iOverflow; /* Offset to overflow page number.  Zero if no overflow */
  u16 nSize;     /* Size of the cell content on the main b-tree page */
};

/*
940
941
942
943
944
945
946

947
948
949
950
951
952
953
    n += getVarint(&pCell[n], (u64 *)&pInfo->nKey);
  }else{
    u32 x;
    n += getVarint32(&pCell[n], &x);
    pInfo->nKey = x;
    nPayload += x;
  }

  pInfo->nHeader = n;
  if( nPayload<=pPage->maxLocal ){
    /* This is the (easy) common case where the entire payload fits
    ** on the local page.  No overflow is required.
    */
    int nSize;          /* Total size of cell content in bytes */
    pInfo->nLocal = nPayload;







>







941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
    n += getVarint(&pCell[n], (u64 *)&pInfo->nKey);
  }else{
    u32 x;
    n += getVarint32(&pCell[n], &x);
    pInfo->nKey = x;
    nPayload += x;
  }
  pInfo->nPayload = nPayload;
  pInfo->nHeader = n;
  if( nPayload<=pPage->maxLocal ){
    /* This is the (easy) common case where the entire payload fits
    ** on the local page.  No overflow is required.
    */
    int nSize;          /* Total size of cell content in bytes */
    pInfo->nLocal = nPayload;
1016
1017
1018
1019
1020
1021
1022

1023
1024
1025
1026
1027
1028
1029
** to an overflow page, insert an entry into the pointer-map
** for the overflow page.
*/
static int ptrmapPutOvflPtr(MemPage *pPage, u8 *pCell){
  if( pCell ){
    CellInfo info;
    parseCellPtr(pPage, pCell, &info);

    if( (info.nData+(pPage->intKey?0:info.nKey))>info.nLocal ){
      Pgno ovfl = get4byte(&pCell[info.iOverflow]);
      return ptrmapPut(pPage->pBt, ovfl, PTRMAP_OVERFLOW1, pPage->pgno);
    }
  }
  return SQLITE_OK;
}







>







1018
1019
1020
1021
1022
1023
1024
1025
1026
1027
1028
1029
1030
1031
1032
** to an overflow page, insert an entry into the pointer-map
** for the overflow page.
*/
static int ptrmapPutOvflPtr(MemPage *pPage, u8 *pCell){
  if( pCell ){
    CellInfo info;
    parseCellPtr(pPage, pCell, &info);
    assert( (info.nData+(pPage->intKey?0:info.nKey))==info.nPayload );
    if( (info.nData+(pPage->intKey?0:info.nKey))>info.nLocal ){
      Pgno ovfl = get4byte(&pCell[info.iOverflow]);
      return ptrmapPut(pPage->pBt, ovfl, PTRMAP_OVERFLOW1, pPage->pgno);
    }
  }
  return SQLITE_OK;
}
3872
3873
3874
3875
3876
3877
3878
3879
3880
3881
3882
3883
3884
3885
3886
3887
3888
3889

3890
3891
3892
3893
3894
3895
3896

3897

3898
3899
3900
3901
3902
3903
3904
3905
3906
3907
3908
3909
static int clearCell(MemPage *pPage, unsigned char *pCell){
  BtShared *pBt = pPage->pBt;
  CellInfo info;
  Pgno ovflPgno;
  int rc;
  int nOvfl;
  int ovflPageSize;
  int nPayload;

  parseCellPtr(pPage, pCell, &info);
  if( info.iOverflow==0 ){
    return SQLITE_OK;  /* No overflow pages. Return without doing anything */
  }
  ovflPgno = get4byte(&pCell[info.iOverflow]);
  nPayload = pPage->intKey ? info.nData : info.nKey;
  ovflPageSize = pBt->usableSize - 4;
  nOvfl = (nPayload - info.nLocal + ovflPageSize - 1)/ovflPageSize;
  while( ovflPgno!=0 ){

    MemPage *pOvfl;
    nOvfl--;
    if( ovflPgno>sqlite3pager_pagecount(pBt->pPager) ){
      return SQLITE_CORRUPT_BKPT;
    }
    rc = getPage(pBt, ovflPgno, &pOvfl, nOvfl==0);
    if( rc ) return rc;

    ovflPgno = get4byte(pOvfl->aData);

    rc = freePage(pOvfl);
    sqlite3pager_unref(pOvfl->aData);
    if( rc ) return rc;
  }
  assert( nOvfl==0 );
  return SQLITE_OK;
}

/*
** Create the byte sequence used to represent a cell on page pPage
** and write that byte sequence into pCell[].  Overflow pages are
** allocated and filled in as necessary.  The calling procedure







<






<

|
|
>

<
|


|

>
|
>




<







3875
3876
3877
3878
3879
3880
3881

3882
3883
3884
3885
3886
3887

3888
3889
3890
3891
3892

3893
3894
3895
3896
3897
3898
3899
3900
3901
3902
3903
3904

3905
3906
3907
3908
3909
3910
3911
static int clearCell(MemPage *pPage, unsigned char *pCell){
  BtShared *pBt = pPage->pBt;
  CellInfo info;
  Pgno ovflPgno;
  int rc;
  int nOvfl;
  int ovflPageSize;


  parseCellPtr(pPage, pCell, &info);
  if( info.iOverflow==0 ){
    return SQLITE_OK;  /* No overflow pages. Return without doing anything */
  }
  ovflPgno = get4byte(&pCell[info.iOverflow]);

  ovflPageSize = pBt->usableSize - 4;
  nOvfl = (info.nPayload - info.nLocal + ovflPageSize - 1)/ovflPageSize;
  assert( ovflPgno==0 || nOvfl>0 );
  while( nOvfl-- ){
    MemPage *pOvfl;

    if( ovflPgno==0 || ovflPgno>sqlite3pager_pagecount(pBt->pPager) ){
      return SQLITE_CORRUPT_BKPT;
    }
    rc = getPage(pBt, ovflPgno, &pOvfl, 0);
    if( rc ) return rc;
    if( nOvfl ){
      ovflPgno = get4byte(pOvfl->aData);
    }
    rc = freePage(pOvfl);
    sqlite3pager_unref(pOvfl->aData);
    if( rc ) return rc;
  }

  return SQLITE_OK;
}

/*
** Create the byte sequence used to represent a cell on page pPage
** and write that byte sequence into pCell[].  Overflow pages are
** allocated and filled in as necessary.  The calling procedure
4192
4193
4194
4195
4196
4197
4198

4199
4200
4201
4202
4203
4204
4205
#ifndef SQLITE_OMIT_AUTOVACUUM
    if( pPage->pBt->autoVacuum ){
      /* The cell may contain a pointer to an overflow page. If so, write
      ** the entry for the overflow page into the pointer map.
      */
      CellInfo info;
      parseCellPtr(pPage, pCell, &info);

      if( (info.nData+(pPage->intKey?0:info.nKey))>info.nLocal ){
        Pgno pgnoOvfl = get4byte(&pCell[info.iOverflow]);
        int rc = ptrmapPut(pPage->pBt, pgnoOvfl, PTRMAP_OVERFLOW1, pPage->pgno);
        if( rc!=SQLITE_OK ) return rc;
      }
    }
#endif







>







4194
4195
4196
4197
4198
4199
4200
4201
4202
4203
4204
4205
4206
4207
4208
#ifndef SQLITE_OMIT_AUTOVACUUM
    if( pPage->pBt->autoVacuum ){
      /* The cell may contain a pointer to an overflow page. If so, write
      ** the entry for the overflow page into the pointer map.
      */
      CellInfo info;
      parseCellPtr(pPage, pCell, &info);
      assert( (info.nData+(pPage->intKey?0:info.nKey))==info.nPayload );
      if( (info.nData+(pPage->intKey?0:info.nKey))>info.nLocal ){
        Pgno pgnoOvfl = get4byte(&pCell[info.iOverflow]);
        int rc = ptrmapPut(pPage->pBt, pgnoOvfl, PTRMAP_OVERFLOW1, pPage->pgno);
        if( rc!=SQLITE_OK ) return rc;
      }
    }
#endif
6197
6198
6199
6200
6201
6202
6203

6204
6205
6206
6207
6208
6209
6210
    /* Check payload overflow pages
    */
    sprintf(zContext, "On tree page %d cell %d: ", iPage, i);
    pCell = findCell(pPage,i);
    parseCellPtr(pPage, pCell, &info);
    sz = info.nData;
    if( !pPage->intKey ) sz += info.nKey;

    if( sz>info.nLocal ){
      int nPage = (sz - info.nLocal + usableSize - 5)/(usableSize - 4);
      Pgno pgnoOvfl = get4byte(&pCell[info.iOverflow]);
#ifndef SQLITE_OMIT_AUTOVACUUM
      if( pBt->autoVacuum ){
        checkPtrmap(pCheck, pgnoOvfl, PTRMAP_OVERFLOW1, iPage, zContext);
      }







>







6200
6201
6202
6203
6204
6205
6206
6207
6208
6209
6210
6211
6212
6213
6214
    /* Check payload overflow pages
    */
    sprintf(zContext, "On tree page %d cell %d: ", iPage, i);
    pCell = findCell(pPage,i);
    parseCellPtr(pPage, pCell, &info);
    sz = info.nData;
    if( !pPage->intKey ) sz += info.nKey;
    assert( sz==info.nPayload );
    if( sz>info.nLocal ){
      int nPage = (sz - info.nLocal + usableSize - 5)/(usableSize - 4);
      Pgno pgnoOvfl = get4byte(&pCell[info.iOverflow]);
#ifndef SQLITE_OMIT_AUTOVACUUM
      if( pBt->autoVacuum ){
        checkPtrmap(pCheck, pgnoOvfl, PTRMAP_OVERFLOW1, iPage, zContext);
      }