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

Changes to src/btree.c.

     5      5   ** a legal notice, here is a blessing:
     6      6   **
     7      7   **    May you do good and not evil.
     8      8   **    May you find forgiveness for yourself and forgive others.
     9      9   **    May you share freely, never taking more than you give.
    10     10   **
    11     11   *************************************************************************
    12         -** $Id: btree.c,v 1.185 2004/09/01 16:12:25 drh Exp $
           12  +** $Id: btree.c,v 1.186 2004/09/03 18:38:45 drh Exp $
    13     13   **
    14     14   ** This file implements a external (disk-based) database using BTrees.
    15     15   ** For a detailed discussion of BTrees, refer to
    16     16   **
    17     17   **     Donald E. Knuth, THE ART OF COMPUTER PROGRAMMING, Volume 3:
    18     18   **     "Sorting And Searching", pages 473-480. Addison-Wesley
    19     19   **     Publishing Company, Reading, Massachusetts.
................................................................................
   210    210   #include "os.h"
   211    211   #include <assert.h>
   212    212   
   213    213   
   214    214   /* The following value is the maximum cell size assuming a maximum page
   215    215   ** size give above.
   216    216   */
   217         -#define MX_CELL_SIZE  (SQLITE_MAX_PAGE_SIZE-8)
          217  +#define MX_CELL_SIZE(pBt)  (pBt->pageSize-8)
   218    218   
   219    219   /* The maximum number of cells on a single page of the database.  This
   220    220   ** assumes a minimum cell size of 3 bytes.  Such small cells will be
   221    221   ** exceedingly rare, but they are possible.
   222    222   */
   223         -#define MX_CELL ((SQLITE_MAX_PAGE_SIZE-8)/3)
          223  +#define MX_CELL(pBt) ((pBt->pageSize-8)/3)
   224    224   
   225    225   /* Forward declarations */
   226    226   typedef struct MemPage MemPage;
   227    227   
   228    228   /*
   229    229   ** This is a magic string that appears at the beginning of every
   230    230   ** SQLite database in order to identify the file as a real database.
................................................................................
   523    523   #if defined(BTREE_DEBUG) && !defined(NDEBUG) && 0
   524    524   static void _pageIntegrity(MemPage *pPage){
   525    525     int usableSize;
   526    526     u8 *data;
   527    527     int i, j, idx, c, pc, hdr, nFree;
   528    528     int cellOffset;
   529    529     int nCell, cellLimit;
   530         -  u8 used[SQLITE_MAX_PAGE_SIZE];
          530  +  u8 *used;
   531    531   
          532  +  used = sqliteMallocRaw( pPage->pBt->pageSize );
          533  +  if( used==0 ) return;
   532    534     usableSize = pPage->pBt->usableSize;
   533    535     assert( pPage->aData==&((unsigned char*)pPage)[-pPage->pBt->pageSize] );
   534    536     hdr = pPage->hdrOffset;
   535    537     assert( hdr==(pPage->pgno==1 ? 100 : 0) );
   536    538     assert( pPage->pgno==sqlite3pager_pagenumber(pPage->aData) );
   537    539     c = pPage->aData[hdr];
   538    540     if( pPage->isInit ){
................................................................................
   585    587     }
   586    588     nFree = 0;
   587    589     for(i=0; i<usableSize; i++){
   588    590       assert( used[i]<=1 );
   589    591       if( used[i]==0 ) nFree++;
   590    592     }
   591    593     assert( nFree==data[hdr+7] );
          594  +  sqliteFree(used);
   592    595   }
   593    596   #define pageIntegrity(X) _pageIntegrity(X)
   594    597   #else
   595    598   # define pageIntegrity(X)
   596    599   #endif
   597    600   
   598    601   /*
   599    602   ** Defragment the page given.  All Cells are moved to the
   600    603   ** beginning of the page and all free space is collected 
   601    604   ** into one big FreeBlk at the end of the page.
   602    605   */
   603         -static void defragmentPage(MemPage *pPage){
          606  +static int defragmentPage(MemPage *pPage){
   604    607     int i;                     /* Loop counter */
   605    608     int pc;                    /* Address of a i-th cell */
   606    609     int addr;                  /* Offset of first byte after cell pointer array */
   607    610     int hdr;                   /* Offset to the page header */
   608    611     int size;                  /* Size of a cell */
   609    612     int usableSize;            /* Number of usable bytes on a page */
   610    613     int cellOffset;            /* Offset to the cell pointer array */
   611    614     int brk;                   /* Offset to the cell content area */
   612    615     int nCell;                 /* Number of cells on the page */
   613         -  unsigned char *data;               /* The page data */
   614         -  unsigned char temp[SQLITE_MAX_PAGE_SIZE];  /* Temp area for cell content */
          616  +  unsigned char *data;       /* The page data */
          617  +  unsigned char *temp;       /* Temp area for cell content */
   615    618   
   616    619     assert( sqlite3pager_iswriteable(pPage->aData) );
   617    620     assert( pPage->pBt!=0 );
   618    621     assert( pPage->pBt->usableSize <= SQLITE_MAX_PAGE_SIZE );
   619    622     assert( pPage->nOverflow==0 );
          623  +  temp = sqliteMalloc( pPage->pBt->pageSize );
          624  +  if( temp==0 ) return SQLITE_NOMEM;
   620    625     data = pPage->aData;
   621    626     hdr = pPage->hdrOffset;
   622    627     cellOffset = pPage->cellOffset;
   623    628     nCell = pPage->nCell;
   624    629     assert( nCell==get2byte(&data[hdr+3]) );
   625    630     usableSize = pPage->pBt->usableSize;
   626    631     brk = get2byte(&data[hdr+5]);
................................................................................
   639    644     assert( brk>=cellOffset+2*nCell );
   640    645     put2byte(&data[hdr+5], brk);
   641    646     data[hdr+1] = 0;
   642    647     data[hdr+2] = 0;
   643    648     data[hdr+7] = 0;
   644    649     addr = cellOffset+2*nCell;
   645    650     memset(&data[addr], 0, brk-addr);
          651  +  sqliteFree(temp);
          652  +  return SQLITE_OK;
   646    653   }
   647    654   
   648    655   /*
   649    656   ** Allocate nByte bytes of space on a page.
   650    657   **
   651    658   ** Return the index into pPage->aData[] of the first byte of
   652    659   ** the new allocation. Or return 0 if there is not enough free
................................................................................
   698    705     /* Allocate memory from the gap in between the cell pointer array
   699    706     ** and the cell content area.
   700    707     */
   701    708     top = get2byte(&data[hdr+5]);
   702    709     nCell = get2byte(&data[hdr+3]);
   703    710     cellOffset = pPage->cellOffset;
   704    711     if( nFrag>=60 || cellOffset + 2*nCell > top - nByte ){
   705         -    defragmentPage(pPage);
          712  +    if( defragmentPage(pPage) ) return 0;
   706    713       top = get2byte(&data[hdr+5]);
   707    714     }
   708    715     top -= nByte;
   709    716     assert( cellOffset + 2*nCell <= top );
   710    717     put2byte(&data[hdr+5], top);
   711    718     return top;
   712    719   }
................................................................................
   815    822     MemPage *pPage,        /* The page to be initialized */
   816    823     MemPage *pParent       /* The parent.  Might be NULL */
   817    824   ){
   818    825     int pc;            /* Address of a freeblock within pPage->aData[] */
   819    826     int i;             /* Loop counter */
   820    827     int hdr;           /* Offset to beginning of page header */
   821    828     u8 *data;          /* Equal to pPage->aData */
          829  +  Btree *pBt;        /* The main btree structure */
   822    830     int usableSize;    /* Amount of usable space on each page */
   823    831     int cellOffset;    /* Offset from start of page to first cell pointer */
   824    832     int nFree;         /* Number of unused bytes on the page */
   825    833     int top;           /* First byte of the cell content area */
   826    834   
   827         -  assert( pPage->pBt!=0 );
   828         -  assert( pParent==0 || pParent->pBt==pPage->pBt );
          835  +  pBt = pPage->pBt;
          836  +  assert( pBt!=0 );
          837  +  assert( pParent==0 || pParent->pBt==pBt );
   829    838     assert( pPage->pgno==sqlite3pager_pagenumber(pPage->aData) );
   830         -  assert( pPage->aData == &((unsigned char*)pPage)[-pPage->pBt->pageSize] );
          839  +  assert( pPage->aData == &((unsigned char*)pPage)[-pBt->pageSize] );
   831    840     if( pPage->pParent!=pParent && (pPage->pParent!=0 || pPage->isInit) ){
   832    841       /* The parent page should never change unless the file is corrupt */
   833    842       return SQLITE_CORRUPT; /* bkpt-CORRUPT */
   834    843     }
   835    844     if( pPage->isInit ) return SQLITE_OK;
   836    845     if( pPage->pParent==0 && pParent!=0 ){
   837    846       pPage->pParent = pParent;
................................................................................
   838    847       sqlite3pager_ref(pParent->aData);
   839    848     }
   840    849     hdr = pPage->hdrOffset;
   841    850     data = pPage->aData;
   842    851     decodeFlags(pPage, data[hdr]);
   843    852     pPage->nOverflow = 0;
   844    853     pPage->idxShift = 0;
   845         -  usableSize = pPage->pBt->usableSize;
          854  +  usableSize = pBt->usableSize;
   846    855     pPage->cellOffset = cellOffset = hdr + 12 - 4*pPage->leaf;
   847    856     top = get2byte(&data[hdr+5]);
   848    857     pPage->nCell = get2byte(&data[hdr+3]);
   849         -  if( pPage->nCell>MX_CELL ){
          858  +  if( pPage->nCell>MX_CELL(pBt) ){
   850    859       /* To many cells for a single page.  The page must be corrupt */
   851    860       return SQLITE_CORRUPT; /* bkpt-CORRUPT */
   852    861     }
   853    862     if( pPage->nCell==0 && pParent!=0 && pParent->pgno!=1 ){
   854    863       /* All pages must have at least one cell, except for root pages */
   855    864       return SQLITE_CORRUPT; /* bkpt-CORRUPT */
   856    865     }
................................................................................
  1214   1223     pBt->maxLocal = (pBt->usableSize-12)*pBt->maxEmbedFrac/255 - 23;
  1215   1224     pBt->minLocal = (pBt->usableSize-12)*pBt->minEmbedFrac/255 - 23;
  1216   1225     pBt->maxLeaf = pBt->usableSize - 35;
  1217   1226     pBt->minLeaf = (pBt->usableSize-12)*pBt->minLeafFrac/255 - 23;
  1218   1227     if( pBt->minLocal>pBt->maxLocal || pBt->maxLocal<0 ){
  1219   1228       goto page1_init_failed;
  1220   1229     }
  1221         -  assert( pBt->maxLeaf + 23 <= MX_CELL_SIZE );
         1230  +  assert( pBt->maxLeaf + 23 <= MX_CELL_SIZE(pBt) );
  1222   1231     pBt->pPage1 = pPage1;
  1223   1232     pBt->pageSizeFixed = 1;
  1224   1233     return SQLITE_OK;
  1225   1234   
  1226   1235   page1_init_failed:
  1227   1236     releasePage(pPage1);
  1228   1237     pBt->pPage1 = 0;
................................................................................
  2912   2921     int rc;                      /* The return code */
  2913   2922     int leafCorrection;          /* 4 if pPage is a leaf.  0 if not */
  2914   2923     int leafData;                /* True if pPage is a leaf of a LEAFDATA tree */
  2915   2924     int usableSpace;             /* Bytes in pPage beyond the header */
  2916   2925     int pageFlags;               /* Value of pPage->aData[0] */
  2917   2926     int subtotal;                /* Subtotal of bytes in cells on one page */
  2918   2927     int iSpace = 0;              /* First unused byte of aSpace[] */
         2928  +  int mxCellPerPage;           /* Maximum number of cells in one page */
  2919   2929     MemPage *apOld[NB];          /* pPage and up to two siblings */
  2920   2930     Pgno pgnoOld[NB];            /* Page numbers for each page in apOld[] */
  2921   2931     MemPage *apCopy[NB];         /* Private copies of apOld[] pages */
  2922   2932     MemPage *apNew[NB+2];        /* pPage and up to NB siblings after balancing */
  2923   2933     Pgno pgnoNew[NB+2];          /* Page numbers for each page in apNew[] */
  2924   2934     int idxDiv[NB];              /* Indices of divider cells in pParent */
  2925   2935     u8 *apDiv[NB];               /* Divider cells in pParent */
  2926   2936     int cntNew[NB+2];            /* Index in aCell[] of cell after i-th page */
  2927   2937     int szNew[NB+2];             /* Combined size of cells place on i-th page */
  2928         -  u8 *apCell[(MX_CELL+2)*NB];  /* All cells from pages being balanced */
  2929         -  int szCell[(MX_CELL+2)*NB];  /* Local size of all cells */
  2930         -  u8 aCopy[NB][SQLITE_MAX_PAGE_SIZE+sizeof(MemPage)];  /* Space for apCopy[] */
  2931         -  u8 aSpace[SQLITE_MAX_PAGE_SIZE*5];   /* Space to copies of divider cells */
         2938  +  u8 **apCell;                 /* All cells begin balanced */
         2939  +  int *szCell;                 /* Local size of all cells in apCell[] */
         2940  +  u8 *aCopy[NB];               /* Space for holding data of apCopy[] */
         2941  +  u8 *aSpace;                  /* Space to hold copies of dividers cells */
  2932   2942   
  2933   2943     /* 
  2934   2944     ** Find the parent page.
  2935   2945     */
  2936   2946     assert( pPage->isInit );
  2937   2947     assert( sqlite3pager_iswriteable(pPage->aData) );
  2938   2948     pBt = pPage->pBt;
  2939   2949     pParent = pPage->pParent;
  2940   2950     sqlite3pager_write(pParent->aData);
  2941   2951     assert( pParent );
  2942   2952     TRACE(("BALANCE: begin page %d child of %d\n", pPage->pgno, pParent->pgno));
         2953  +
         2954  +  /*
         2955  +  ** Allocate space for memory structures
         2956  +  */
         2957  +  mxCellPerPage = MX_CELL(pBt);
         2958  +  apCell = sqliteMallocRaw( 
         2959  +       (mxCellPerPage+2)*NB*(sizeof(u8*)+sizeof(int))
         2960  +     + sizeof(MemPage)*NB
         2961  +     + pBt->pageSize*(5+NB)
         2962  +  );
         2963  +  if( apCell==0 ){
         2964  +    return SQLITE_NOMEM;
         2965  +  }
         2966  +  szCell = (int*)&apCell[(mxCellPerPage+2)*NB];
         2967  +  aCopy[0] = (u8*)&szCell[(mxCellPerPage+2)*NB];
         2968  +  for(i=1; i<NB; i++){
         2969  +    aCopy[i] = &aCopy[i-1][pBt->pageSize+sizeof(MemPage)];
         2970  +  }
         2971  +  aSpace = &aCopy[NB-1][pBt->pageSize+sizeof(MemPage)];
  2943   2972     
  2944   2973     /*
  2945   2974     ** Find the cell in the parent page whose left child points back
  2946   2975     ** to pPage.  The "idx" variable is the index of that cell.  If pPage
  2947   2976     ** is the rightmost child of pParent then set idx to pParent->nCell 
  2948   2977     */
  2949   2978     if( pParent->idxShift ){
................................................................................
  3006   3035     /*
  3007   3036     ** Make copies of the content of pPage and its siblings into aOld[].
  3008   3037     ** The rest of this function will use data from the copies rather
  3009   3038     ** that the original pages since the original pages will be in the
  3010   3039     ** process of being overwritten.
  3011   3040     */
  3012   3041     for(i=0; i<nOld; i++){
  3013         -    MemPage *p = apCopy[i] = (MemPage*)&aCopy[i+1][-(int)sizeof(MemPage)];
         3042  +    MemPage *p = apCopy[i] = (MemPage*)&aCopy[i][pBt->pageSize];
  3014   3043       p->aData = &((u8*)p)[-pBt->pageSize];
  3015   3044       memcpy(p->aData, apOld[i]->aData, pBt->pageSize + sizeof(MemPage));
  3016   3045       p->aData = &((u8*)p)[-pBt->pageSize];
  3017   3046     }
  3018   3047   
  3019   3048     /*
  3020   3049     ** Load pointers to all cells on sibling pages and the divider cells
................................................................................
  3053   3082           */
  3054   3083           dropCell(pParent, nxDiv, sz);
  3055   3084         }else{
  3056   3085           u8 *pTemp;
  3057   3086           szCell[nCell] = sz;
  3058   3087           pTemp = &aSpace[iSpace];
  3059   3088           iSpace += sz;
  3060         -        assert( iSpace<=sizeof(aSpace) );
         3089  +        assert( iSpace<=pBt->pageSize*5 );
  3061   3090           memcpy(pTemp, apDiv[i], sz);
  3062   3091           apCell[nCell] = pTemp+leafCorrection;
  3063   3092           dropCell(pParent, nxDiv, sz);
  3064   3093           szCell[nCell] -= leafCorrection;
  3065   3094           assert( get4byte(pTemp)==pgnoOld[i] );
  3066   3095           if( !pOld->leaf ){
  3067   3096             assert( leafCorrection==0 );
................................................................................
  3237   3266         }else if( leafData ){
  3238   3267           CellInfo info;
  3239   3268           j--;
  3240   3269           parseCellPtr(pNew, apCell[j], &info);
  3241   3270           pCell = &aSpace[iSpace];
  3242   3271           fillInCell(pParent, pCell, 0, info.nKey, 0, 0, &sz);
  3243   3272           iSpace += sz;
  3244         -        assert( iSpace<=sizeof(aSpace) );
         3273  +        assert( iSpace<=pBt->pageSize*5 );
  3245   3274           pTemp = 0;
  3246   3275         }else{
  3247   3276           pCell -= 4;
  3248   3277           pTemp = &aSpace[iSpace];
  3249   3278           iSpace += sz;
  3250         -        assert( iSpace<=sizeof(aSpace) );
         3279  +        assert( iSpace<=pBt->pageSize*5 );
  3251   3280         }
  3252   3281         insertCell(pParent, nxDiv, pCell, sz, pTemp);
  3253   3282         put4byte(findOverflowCell(pParent,nxDiv), pNew->pgno);
  3254   3283         j++;
  3255   3284         nxDiv++;
  3256   3285       }
  3257   3286     }
................................................................................
  3286   3315     /* pageIntegrity(pPage);    // No! pPage might have been added to freelist */ 
  3287   3316     rc = balance(pParent);
  3288   3317     
  3289   3318     /*
  3290   3319     ** Cleanup before returning.
  3291   3320     */
  3292   3321   balance_cleanup:
         3322  +  sqliteFree(apCell);
  3293   3323     for(i=0; i<nOld; i++){
  3294   3324       releasePage(apOld[i]);
  3295   3325     }
  3296   3326     for(i=0; i<nNew; i++){
  3297   3327       releasePage(apNew[i]);
  3298   3328     }
  3299   3329     releasePage(pParent);
................................................................................
  3306   3336   ** This routine is called for the root page of a btree when the root
  3307   3337   ** page contains no cells.  This is an opportunity to make the tree
  3308   3338   ** shallower by one level.
  3309   3339   */
  3310   3340   static int balance_shallower(MemPage *pPage){
  3311   3341     MemPage *pChild;             /* The only child page of pPage */
  3312   3342     Pgno pgnoChild;              /* Page number for pChild */
  3313         -  int rc;                      /* Return code from subprocedures */
  3314         -  u8 *apCell[(MX_CELL+2)*NB];  /* All cells from pages being balanced */
  3315         -  int szCell[(MX_CELL+2)*NB];  /* Local size of all cells */
         3343  +  int rc = SQLITE_OK;          /* Return code from subprocedures */
         3344  +  Btree *pBt;                  /* The main BTree structure */
         3345  +  int mxCellPerPage;           /* Maximum number of cells per page */
         3346  +  u8 **apCell;                 /* All cells from pages being balanced */
         3347  +  int *szCell;                 /* Local size of all cells */
  3316   3348   
  3317   3349     assert( pPage->pParent==0 );
  3318   3350     assert( pPage->nCell==0 );
         3351  +  pBt = pPage->pBt;
         3352  +  mxCellPerPage = MX_CELL(pBt);
         3353  +  apCell = sqliteMallocRaw( mxCellPerPage*(sizeof(u8*)+sizeof(int)) );
         3354  +  if( apCell==0 ) return SQLITE_NOMEM;
         3355  +  szCell = (int*)&apCell[mxCellPerPage];
  3319   3356     if( pPage->leaf ){
  3320   3357       /* The table is completely empty */
  3321   3358       TRACE(("BALANCE: empty table %d\n", pPage->pgno));
  3322   3359     }else{
  3323   3360       /* The root page is empty but has one child.  Transfer the
  3324   3361       ** information from that one child into the root page if it 
  3325   3362       ** will fit.  This reduces the depth of the tree by one.
................................................................................
  3332   3369       ** for the right-pointer to the child page.  The child page becomes
  3333   3370       ** the virtual root of the tree.
  3334   3371       */
  3335   3372       pgnoChild = get4byte(&pPage->aData[pPage->hdrOffset+8]);
  3336   3373       assert( pgnoChild>0 );
  3337   3374       assert( pgnoChild<=sqlite3pager_pagecount(pPage->pBt->pPager) );
  3338   3375       rc = getPage(pPage->pBt, pgnoChild, &pChild);
  3339         -    if( rc ) return rc;
         3376  +    if( rc ) goto end_shallow_balance;
  3340   3377       if( pPage->pgno==1 ){
  3341   3378         rc = initPage(pChild, pPage);
  3342         -      if( rc ) return rc;
         3379  +      if( rc ) goto end_shallow_balance;
  3343   3380         assert( pChild->nOverflow==0 );
  3344   3381         if( pChild->nFree>=100 ){
  3345   3382           /* The child information will fit on the root page, so do the
  3346   3383           ** copy */
  3347   3384           int i;
  3348   3385           zeroPage(pPage, pChild->aData[0]);
  3349   3386           for(i=0; i<pChild->nCell; i++){
................................................................................
  3367   3404         freePage(pChild);
  3368   3405         TRACE(("BALANCE: transfer child %d into root %d\n",
  3369   3406                 pChild->pgno, pPage->pgno));
  3370   3407       }
  3371   3408       reparentChildPages(pPage);
  3372   3409       releasePage(pChild);
  3373   3410     }
  3374         -  return SQLITE_OK;
         3411  +end_shallow_balance:
         3412  +  sqliteFree(apCell);
         3413  +  return rc;
  3375   3414   }
  3376   3415   
  3377   3416   
  3378   3417   /*
  3379   3418   ** The root page is overfull
  3380   3419   **
  3381   3420   ** When this happens, Create a new child page and copy the
................................................................................
  3488   3527   ){
  3489   3528     int rc;
  3490   3529     int loc;
  3491   3530     int szNew;
  3492   3531     MemPage *pPage;
  3493   3532     Btree *pBt = pCur->pBt;
  3494   3533     unsigned char *oldCell;
  3495         -  unsigned char newCell[MX_CELL_SIZE];
         3534  +  unsigned char *newCell = 0;
  3496   3535   
  3497   3536     if( pCur->status ){
  3498   3537       return pCur->status;  /* A rollback destroyed this cursor */
  3499   3538     }
  3500   3539     if( pBt->inTrans!=TRANS_WRITE ){
  3501   3540       /* Must start a transaction before doing an insert */
  3502   3541       return pBt->readOnly ? SQLITE_READONLY : SQLITE_ERROR;
................................................................................
  3515   3554     assert( pPage->leaf || !pPage->leafData );
  3516   3555     TRACE(("INSERT: table=%d nkey=%lld ndata=%d page=%d %s\n",
  3517   3556             pCur->pgnoRoot, nKey, nData, pPage->pgno,
  3518   3557             loc==0 ? "overwrite" : "new entry"));
  3519   3558     assert( pPage->isInit );
  3520   3559     rc = sqlite3pager_write(pPage->aData);
  3521   3560     if( rc ) return rc;
         3561  +  newCell = sqliteMallocRaw( MX_CELL_SIZE(pBt) );
         3562  +  if( newCell==0 ) return SQLITE_NOMEM;
  3522   3563     rc = fillInCell(pPage, newCell, pKey, nKey, pData, nData, &szNew);
  3523         -  if( rc ) return rc;
         3564  +  if( rc ) goto end_insert;
  3524   3565     assert( szNew==cellSizePtr(pPage, newCell) );
  3525         -  assert( szNew<=sizeof(newCell) );
         3566  +  assert( szNew<=MX_CELL_SIZE(pBt) );
  3526   3567     if( loc==0 && pCur->isValid ){
  3527   3568       int szOld;
  3528   3569       assert( pCur->idx>=0 && pCur->idx<pPage->nCell );
  3529   3570       oldCell = findCell(pPage, pCur->idx);
  3530   3571       if( !pPage->leaf ){
  3531   3572         memcpy(newCell, oldCell, 4);
  3532   3573       }
  3533   3574       szOld = cellSizePtr(pPage, oldCell);
  3534   3575       rc = clearCell(pPage, oldCell);
  3535         -    if( rc ) return rc;
         3576  +    if( rc ) goto end_insert;
  3536   3577       dropCell(pPage, pCur->idx, szOld);
  3537   3578     }else if( loc<0 && pPage->nCell>0 ){
  3538   3579       assert( pPage->leaf );
  3539   3580       pCur->idx++;
  3540   3581       pCur->info.nSize = 0;
  3541   3582     }else{
  3542   3583       assert( pPage->leaf );
  3543   3584     }
  3544   3585     insertCell(pPage, pCur->idx, newCell, szNew, 0);
  3545   3586     rc = balance(pPage);
  3546   3587     /* sqlite3BtreePageDump(pCur->pBt, pCur->pgnoRoot, 1); */
  3547   3588     /* fflush(stdout); */
  3548   3589     moveToRoot(pCur);
         3590  +end_insert:
         3591  +  sqliteFree(newCell);
  3549   3592     return rc;
  3550   3593   }
  3551   3594   
  3552   3595   /*
  3553   3596   ** Delete the entry that the cursor is pointing to.  The cursor
  3554   3597   ** is left pointing at a random location.
  3555   3598   */
................................................................................
  3593   3636       ** next Cell after the one to be deleted is guaranteed to exist and
  3594   3637       ** to be a leaf so we can use it.
  3595   3638       */
  3596   3639       BtCursor leafCur;
  3597   3640       unsigned char *pNext;
  3598   3641       int szNext;
  3599   3642       int notUsed;
  3600         -    unsigned char tempCell[MX_CELL_SIZE];
         3643  +    unsigned char *tempCell;
  3601   3644       assert( !pPage->leafData );
  3602   3645       getTempCursor(pCur, &leafCur);
  3603   3646       rc = sqlite3BtreeNext(&leafCur, &notUsed);
  3604   3647       if( rc!=SQLITE_OK ){
  3605   3648         if( rc!=SQLITE_NOMEM ){
  3606   3649           rc = SQLITE_CORRUPT;  /* bkpt-CORRUPT */
  3607   3650         }
................................................................................
  3610   3653       rc = sqlite3pager_write(leafCur.pPage->aData);
  3611   3654       if( rc ) return rc;
  3612   3655       TRACE(("DELETE: table=%d delete internal from %d replace from leaf %d\n",
  3613   3656          pCur->pgnoRoot, pPage->pgno, leafCur.pPage->pgno));
  3614   3657       dropCell(pPage, pCur->idx, cellSizePtr(pPage, pCell));
  3615   3658       pNext = findCell(leafCur.pPage, leafCur.idx);
  3616   3659       szNext = cellSizePtr(leafCur.pPage, pNext);
  3617         -    assert( sizeof(tempCell)>=szNext+4 );
         3660  +    assert( MX_CELL_SIZE(pBt)>=szNext+4 );
         3661  +    tempCell = sqliteMallocRaw( MX_CELL_SIZE(pBt) );
         3662  +    if( tempCell==0 ) return SQLITE_NOMEM;
  3618   3663       insertCell(pPage, pCur->idx, pNext-4, szNext+4, tempCell);
  3619   3664       put4byte(findOverflowCell(pPage, pCur->idx), pgnoChild);
  3620   3665       rc = balance(pPage);
         3666  +    sqliteFree(tempCell);
  3621   3667       if( rc ) return rc;
  3622   3668       dropCell(leafCur.pPage, leafCur.idx, szNext);
  3623   3669       rc = balance(leafCur.pPage);
  3624   3670       releaseTempCursor(&leafCur);
  3625   3671     }else{
  3626   3672       TRACE(("DELETE: table=%d delete from leaf %d\n",
  3627   3673          pCur->pgnoRoot, pPage->pgno));
................................................................................
  4009   4055     int *anRef;    /* Number of times each page is referenced */
  4010   4056     char *zErrMsg; /* An error message.  NULL of no errors seen. */
  4011   4057   };
  4012   4058   
  4013   4059   /*
  4014   4060   ** Append a message to the error message string.
  4015   4061   */
  4016         -static void checkAppendMsg(IntegrityCk *pCheck, char *zMsg1, char *zMsg2){
         4062  +static void checkAppendMsg(
         4063  +  IntegrityCk *pCheck,
         4064  +  char *zMsg1,
         4065  +  const char *zFormat,
         4066  +  ...
         4067  +){
         4068  +  va_list ap;
         4069  +  char *zMsg2;
         4070  +  va_start(ap, zFormat);
         4071  +  zMsg2 = sqlite3VMPrintf(zFormat, ap);
         4072  +  va_end(ap);
         4073  +  if( zMsg1==0 ) zMsg1 = "";
  4017   4074     if( pCheck->zErrMsg ){
  4018   4075       char *zOld = pCheck->zErrMsg;
  4019   4076       pCheck->zErrMsg = 0;
  4020   4077       sqlite3SetString(&pCheck->zErrMsg, zOld, "\n", zMsg1, zMsg2, (char*)0);
  4021   4078       sqliteFree(zOld);
  4022   4079     }else{
  4023   4080       sqlite3SetString(&pCheck->zErrMsg, zMsg1, zMsg2, (char*)0);
  4024   4081     }
         4082  +  sqliteFree(zMsg2);
  4025   4083   }
  4026   4084   
  4027   4085   /*
  4028   4086   ** Add 1 to the reference count for page iPage.  If this is the second
  4029   4087   ** reference to the page, add an error message to pCheck->zErrMsg.
  4030   4088   ** Return 1 if there are 2 ore more references to the page and 0 if
  4031   4089   ** if this is the first reference to the page.
  4032   4090   **
  4033   4091   ** Also check that the page number is in bounds.
  4034   4092   */
  4035   4093   static int checkRef(IntegrityCk *pCheck, int iPage, char *zContext){
  4036   4094     if( iPage==0 ) return 1;
  4037   4095     if( iPage>pCheck->nPage || iPage<0 ){
  4038         -    char zBuf[100];
  4039         -    sprintf(zBuf, "invalid page number %d", iPage);
  4040         -    checkAppendMsg(pCheck, zContext, zBuf);
         4096  +    checkAppendMsg(pCheck, zContext, "invalid page number %d", iPage);
  4041   4097       return 1;
  4042   4098     }
  4043   4099     if( pCheck->anRef[iPage]==1 ){
  4044         -    char zBuf[100];
  4045         -    sprintf(zBuf, "2nd reference to page %d", iPage);
  4046         -    checkAppendMsg(pCheck, zContext, zBuf);
         4100  +    checkAppendMsg(pCheck, zContext, "2nd reference to page %d", iPage);
  4047   4101       return 1;
  4048   4102     }
  4049   4103     return  (pCheck->anRef[iPage]++)>1;
  4050   4104   }
  4051   4105   
  4052   4106   /*
  4053   4107   ** Check the integrity of the freelist or of an overflow page list.
................................................................................
  4059   4113     int iPage,            /* Page number for first page in the list */
  4060   4114     int N,                /* Expected number of pages in the list */
  4061   4115     char *zContext        /* Context for error messages */
  4062   4116   ){
  4063   4117     int i;
  4064   4118     int expected = N;
  4065   4119     int iFirst = iPage;
  4066         -  char zMsg[100];
  4067   4120     while( N-- > 0 ){
  4068   4121       unsigned char *pOvfl;
  4069   4122       if( iPage<1 ){
  4070         -      sprintf(zMsg, "%d of %d pages missing from overflow list starting at %d",
         4123  +      checkAppendMsg(pCheck, zContext,
         4124  +         "%d of %d pages missing from overflow list starting at %d",
  4071   4125             N+1, expected, iFirst);
  4072         -      checkAppendMsg(pCheck, zContext, zMsg);
  4073   4126         break;
  4074   4127       }
  4075   4128       if( checkRef(pCheck, iPage, zContext) ) break;
  4076   4129       if( sqlite3pager_get(pCheck->pPager, (Pgno)iPage, (void**)&pOvfl) ){
  4077         -      sprintf(zMsg, "failed to get page %d", iPage);
  4078         -      checkAppendMsg(pCheck, zContext, zMsg);
         4130  +      checkAppendMsg(pCheck, zContext, "failed to get page %d", iPage);
  4079   4131         break;
  4080   4132       }
  4081   4133       if( isFreeList ){
  4082   4134         int n = get4byte(&pOvfl[4]);
  4083   4135         if( n>pCheck->pBt->usableSize/4-8 ){
  4084         -        sprintf(zMsg, "freelist leaf count too big on page %d", iPage);
  4085         -        checkAppendMsg(pCheck, zContext, zMsg);
         4136  +        checkAppendMsg(pCheck, zContext,
         4137  +           "freelist leaf count too big on page %d", iPage);
  4086   4138           N--;
  4087   4139         }else{
  4088   4140           for(i=0; i<n; i++){
  4089   4141             checkRef(pCheck, get4byte(&pOvfl[8+i*4]), zContext);
  4090   4142           }
  4091   4143           N -= n;
  4092   4144         }
................................................................................
  4128   4180     int i, rc, depth, d2, pgno, cnt;
  4129   4181     int hdr, cellStart;
  4130   4182     int nCell;
  4131   4183     u8 *data;
  4132   4184     BtCursor cur;
  4133   4185     Btree *pBt;
  4134   4186     int maxLocal, usableSize;
  4135         -  char zMsg[100];
  4136   4187     char zContext[100];
  4137         -  char hit[SQLITE_MAX_PAGE_SIZE];
         4188  +  char *hit;
  4138   4189   
  4139   4190     /* Check that the page exists
  4140   4191     */
  4141   4192     cur.pBt = pBt = pCheck->pBt;
  4142   4193     usableSize = pBt->usableSize;
  4143   4194     if( iPage==0 ) return 0;
  4144   4195     if( checkRef(pCheck, iPage, zParentContext) ) return 0;
  4145   4196     if( (rc = getPage(pBt, (Pgno)iPage, &pPage))!=0 ){
  4146         -    sprintf(zMsg, "unable to get the page. error code=%d", rc);
  4147         -    checkAppendMsg(pCheck, zContext, zMsg);
         4197  +    checkAppendMsg(pCheck, zContext,
         4198  +       "unable to get the page. error code=%d", rc);
  4148   4199       return 0;
  4149   4200     }
  4150   4201     maxLocal = pPage->leafData ? pBt->maxLeaf : pBt->maxLocal;
  4151   4202     if( (rc = initPage(pPage, pParent))!=0 ){
  4152         -    sprintf(zMsg, "initPage() returns error code %d", rc);
  4153         -    checkAppendMsg(pCheck, zContext, zMsg);
         4203  +    checkAppendMsg(pCheck, zContext, "initPage() returns error code %d", rc);
  4154   4204       releasePage(pPage);
  4155   4205       return 0;
  4156   4206     }
  4157   4207   
  4158   4208     /* Check out all the cells.
  4159   4209     */
  4160   4210     depth = 0;
................................................................................
  4193   4243       checkTreePage(pCheck, pgno, pPage, zContext,0,0,0,0);
  4194   4244     }
  4195   4245    
  4196   4246     /* Check for complete coverage of the page
  4197   4247     */
  4198   4248     data = pPage->aData;
  4199   4249     hdr = pPage->hdrOffset;
  4200         -  memset(hit, 0, usableSize);
  4201         -  memset(hit, 1, get2byte(&data[hdr+5]));
  4202         -  nCell = get2byte(&data[hdr+3]);
  4203         -  cellStart = hdr + 12 - 4*pPage->leaf;
  4204         -  for(i=0; i<nCell; i++){
  4205         -    int pc = get2byte(&data[cellStart+i*2]);
  4206         -    int size = cellSizePtr(pPage, &data[pc]);
  4207         -    int j;
  4208         -    for(j=pc+size-1; j>=pc; j--) hit[j]++;
  4209         -  }
  4210         -  for(cnt=0, i=get2byte(&data[hdr+1]); i>0 && i<usableSize && cnt<10000; cnt++){
  4211         -    int size = get2byte(&data[i+2]);
  4212         -    int j;
  4213         -    for(j=i+size-1; j>=i; j--) hit[j]++;
  4214         -    i = get2byte(&data[i]);
  4215         -  }
  4216         -  for(i=cnt=0; i<usableSize; i++){
  4217         -    if( hit[i]==0 ){
  4218         -      cnt++;
  4219         -    }else if( hit[i]>1 ){
  4220         -      sprintf(zMsg, "Multiple uses for byte %d of page %d", i, iPage);
  4221         -      checkAppendMsg(pCheck, zMsg, 0);
  4222         -      break;
         4250  +  hit = sqliteMalloc( usableSize );
         4251  +  if( hit ){
         4252  +    memset(hit, 1, get2byte(&data[hdr+5]));
         4253  +    nCell = get2byte(&data[hdr+3]);
         4254  +    cellStart = hdr + 12 - 4*pPage->leaf;
         4255  +    for(i=0; i<nCell; i++){
         4256  +      int pc = get2byte(&data[cellStart+i*2]);
         4257  +      int size = cellSizePtr(pPage, &data[pc]);
         4258  +      int j;
         4259  +      for(j=pc+size-1; j>=pc; j--) hit[j]++;
         4260  +    }
         4261  +    for(cnt=0, i=get2byte(&data[hdr+1]); i>0 && i<usableSize && cnt<10000; 
         4262  +           cnt++){
         4263  +      int size = get2byte(&data[i+2]);
         4264  +      int j;
         4265  +      for(j=i+size-1; j>=i; j--) hit[j]++;
         4266  +      i = get2byte(&data[i]);
         4267  +    }
         4268  +    for(i=cnt=0; i<usableSize; i++){
         4269  +      if( hit[i]==0 ){
         4270  +        cnt++;
         4271  +      }else if( hit[i]>1 ){
         4272  +        checkAppendMsg(pCheck, 0,
         4273  +          "Multiple uses for byte %d of page %d", i, iPage);
         4274  +        break;
         4275  +      }
         4276  +    }
         4277  +    if( cnt!=data[hdr+7] ){
         4278  +      checkAppendMsg(pCheck, 0, 
         4279  +          "Fragmented space is %d byte reported as %d on page %d",
         4280  +          cnt, data[hdr+7], iPage);
  4223   4281       }
  4224   4282     }
  4225         -  if( cnt!=data[hdr+7] ){
  4226         -    sprintf(zMsg, "Fragmented space is %d byte reported as %d on page %d",
  4227         -        cnt, data[hdr+7], iPage);
  4228         -    checkAppendMsg(pCheck, zMsg, 0);
  4229         -  }
         4283  +  sqliteFree(hit);
  4230   4284   
  4231   4285     releasePage(pPage);
  4232   4286     return depth+1;
  4233   4287   }
  4234   4288   
  4235   4289   /*
  4236   4290   ** This routine does a complete check of the given BTree file.  aRoot[] is
................................................................................
  4278   4332       checkTreePage(&sCheck, aRoot[i], 0, "List of tree roots: ", 0,0,0,0);
  4279   4333     }
  4280   4334   
  4281   4335     /* Make sure every page in the file is referenced
  4282   4336     */
  4283   4337     for(i=1; i<=sCheck.nPage; i++){
  4284   4338       if( sCheck.anRef[i]==0 ){
  4285         -      char zBuf[100];
  4286         -      sprintf(zBuf, "Page %d is never used", i);
  4287         -      checkAppendMsg(&sCheck, zBuf, 0);
         4339  +      checkAppendMsg(&sCheck, 0, "Page %d is never used", i);
  4288   4340       }
  4289   4341     }
  4290   4342   
  4291   4343     /* Make sure this analysis did not leave any unref() pages
  4292   4344     */
  4293   4345     unlockBtreeIfUnused(pBt);
  4294   4346     if( nRef != *sqlite3pager_stats(pBt->pPager) ){
  4295         -    char zBuf[100];
  4296         -    sprintf(zBuf, 
         4347  +    checkAppendMsg(&sCheck, 0, 
  4297   4348         "Outstanding page count goes from %d to %d during this analysis",
  4298   4349         nRef, *sqlite3pager_stats(pBt->pPager)
  4299   4350       );
  4300         -    checkAppendMsg(&sCheck, zBuf, 0);
  4301   4351     }
  4302   4352   
  4303   4353     /* Clean  up and report errors.
  4304   4354     */
  4305   4355     sqliteFree(sCheck.anRef);
  4306   4356     return sCheck.zErrMsg;
  4307   4357   }

Changes to test/memleak.test.

     6      6   #    May you do good and not evil.
     7      7   #    May you find forgiveness for yourself and forgive others.
     8      8   #    May you share freely, never taking more than you give.
     9      9   #
    10     10   #***********************************************************************
    11     11   # This file runs all tests.
    12     12   #
    13         -# $Id: memleak.test,v 1.6 2004/08/01 03:52:18 drh Exp $
           13  +# $Id: memleak.test,v 1.7 2004/09/03 18:38:46 drh Exp $
    14     14   
    15     15   set testdir [file dirname $argv0]
    16     16   source $testdir/tester.tcl
    17     17   rename finish_test really_finish_test
    18     18   proc finish_test {} {
    19     19     catch {db close}
    20     20     memleak_check
................................................................................
    37     37     quick.test
    38     38     malloc.test
    39     39     misuse.test
    40     40     memleak.test
    41     41     btree2.test
    42     42     trans.test
    43     43     crash.test
           44  +  corrupt.test
    44     45   }
    45     46   if {[sqlite3 -has-codec]} {
    46     47     # lappend EXCLUDE 
    47     48   }
    48     49   if {[llength $argv]>0} {
    49     50     set FILELIST $argv
    50     51     set argv {}