SQLite

/*
** 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.192 2004/10/05 02:41:42 drh Exp $
** $Id: btree.c,v 1.193 2004/10/22 16:22:58 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.

*/
#include "sqliteInt.h"
#include "pager.h"
#include "btree.h"
#include "os.h"
#include <assert.h>

/*
** This macro rounds values up so that if the value is an address it
** is guaranteed to be an address that is aligned to an 8-byte boundary.
*/
#define FORCE_ALIGNMENT(X)   (((X)+7)&~7)

/* The following value is the maximum cell size assuming a maximum page
** size give above.
*/
#define MX_CELL_SIZE(pBt)  (pBt->pageSize-8)

/* The maximum number of cells on a single page of the database.  This

  u8 inStmt;            /* True if we are in a statement subtransaction */
  u8 readOnly;          /* True if the underlying file is readonly */
  u8 maxEmbedFrac;      /* Maximum payload as % of total page size */
  u8 minEmbedFrac;      /* Minimum payload as % of total page size */
  u8 minLeafFrac;       /* Minimum leaf payload as % of total page size */
  u8 pageSizeFixed;     /* True if the page size can no longer be changed */
  u16 pageSize;         /* Total number of bytes on a page */
  u16 psAligned;        /* pageSize rounded up to a multiple of 8 */
  u16 usableSize;       /* Number of usable bytes on each page */
  int maxLocal;         /* Maximum local payload in non-LEAFDATA tables */
  int minLocal;         /* Minimum local payload in non-LEAFDATA tables */
  int maxLeaf;          /* Maximum local payload in a LEAFDATA table */
  int minLeaf;          /* Minimum local payload in a LEAFDATA table */
};
typedef Btree Bt;

  int cellOffset;
  int nCell, cellLimit;
  u8 *used;

  used = sqliteMallocRaw( pPage->pBt->pageSize );
  if( used==0 ) return;
  usableSize = pPage->pBt->usableSize;
  assert( pPage->aData==&((unsigned char*)pPage)[-pPage->pBt->pageSize] );
  assert( pPage->aData==&((unsigned char*)pPage)[-pPage->pBt->psAligned] );
  hdr = pPage->hdrOffset;
  assert( hdr==(pPage->pgno==1 ? 100 : 0) );
  assert( pPage->pgno==sqlite3pager_pagenumber(pPage->aData) );
  c = pPage->aData[hdr];
  if( pPage->isInit ){
    assert( pPage->leaf == ((c & PTF_LEAF)!=0) );
    assert( pPage->zeroData == ((c & PTF_ZERODATA)!=0) );

  int nFree;         /* Number of unused bytes on the page */
  int top;           /* First byte of the cell content area */

  pBt = pPage->pBt;
  assert( pBt!=0 );
  assert( pParent==0 || pParent->pBt==pBt );
  assert( pPage->pgno==sqlite3pager_pagenumber(pPage->aData) );
  assert( pPage->aData == &((unsigned char*)pPage)[-pBt->pageSize] );
  assert( pPage->aData == &((unsigned char*)pPage)[-pBt->psAligned] );
  if( pPage->pParent!=pParent && (pPage->pParent!=0 || pPage->isInit) ){
    /* The parent page should never change unless the file is corrupt */
    return SQLITE_CORRUPT; /* bkpt-CORRUPT */
  }
  if( pPage->isInit ) return SQLITE_OK;
  if( pPage->pParent==0 && pParent!=0 ){
    pPage->pParent = pParent;

static void zeroPage(MemPage *pPage, int flags){
  unsigned char *data = pPage->aData;
  Btree *pBt = pPage->pBt;
  int hdr = pPage->hdrOffset;
  int first;

  assert( sqlite3pager_pagenumber(data)==pPage->pgno );
  assert( &data[pBt->pageSize] == (unsigned char*)pPage );
  assert( &data[pBt->psAligned] == (unsigned char*)pPage );
  assert( sqlite3pager_iswriteable(data) );
  memset(&data[hdr], 0, pBt->usableSize - hdr);
  data[hdr] = flags;
  first = hdr + 8 + 4*((flags&PTF_LEAF)==0);
  memset(&data[hdr+1], 0, 4);
  data[hdr+7] = 0;
  put2byte(&data[hdr+5], pBt->usableSize);

*/
static int getPage(Btree *pBt, Pgno pgno, MemPage **ppPage){
  int rc;
  unsigned char *aData;
  MemPage *pPage;
  rc = sqlite3pager_get(pBt->pPager, pgno, (void**)&aData);
  if( rc ) return rc;
  pPage = (MemPage*)&aData[pBt->pageSize];
  pPage = (MemPage*)&aData[pBt->psAligned];
  pPage->aData = aData;
  pPage->pBt = pBt;
  pPage->pgno = pgno;
  pPage->hdrOffset = pPage->pgno==1 ? 100 : 0;
  *ppPage = pPage;
  return SQLITE_OK;
}

** Release a MemPage.  This should be called once for each prior
** call to getPage.
*/
static void releasePage(MemPage *pPage){
  if( pPage ){
    assert( pPage->aData );
    assert( pPage->pBt );
    assert( &pPage->aData[pPage->pBt->pageSize]==(unsigned char*)pPage );
    assert( &pPage->aData[pPage->pBt->psAligned]==(unsigned char*)pPage );
    sqlite3pager_unref(pPage->aData);
  }
}

/*
** This routine is called when the reference count for a page
** reaches zero.  We need to unref the pParent pointer when that
** happens.
*/
static void pageDestructor(void *pData, int pageSize){
  MemPage *pPage = (MemPage*)&((char*)pData)[pageSize];
  MemPage *pPage = (MemPage*)&((char*)pData)[FORCE_ALIGNMENT(pageSize)];
  if( pPage->pParent ){
    MemPage *pParent = pPage->pParent;
    pPage->pParent = 0;
    releasePage(pParent);
  }
  pPage->isInit = 0;
}

/*
** During a rollback, when the pager reloads information into the cache
** so that the cache is restored to its original state at the start of
** the transaction, for each page restored this routine is called.
**
** This routine needs to reset the extra data section at the end of the
** page to agree with the restored data.
*/
static void pageReinit(void *pData, int pageSize){
  MemPage *pPage = (MemPage*)&((char*)pData)[pageSize];
  MemPage *pPage = (MemPage*)&((char*)pData)[FORCE_ALIGNMENT(pageSize)];
  if( pPage->isInit ){
    pPage->isInit = 0;
    initPage(pPage, pPage->pParent);
  }
}

/*

    nReserve = zDbHeader[20];
    pBt->maxEmbedFrac = zDbHeader[21];
    pBt->minEmbedFrac = zDbHeader[22];
    pBt->minLeafFrac = zDbHeader[23];
    pBt->pageSizeFixed = 1;
  }
  pBt->usableSize = pBt->pageSize - nReserve;
  pBt->psAligned = FORCE_ALIGNMENT(pBt->pageSize);
  sqlite3pager_set_pagesize(pBt->pPager, pBt->pageSize);
  *ppBtree = pBt;
  return SQLITE_OK;
}

/*
** Close an open database and invalidate all cursors.

    return SQLITE_READONLY;
  }
  if( nReserve<0 ){
    nReserve = pBt->pageSize - pBt->usableSize;
  }
  if( pageSize>=512 && pageSize<=SQLITE_MAX_PAGE_SIZE ){
    pBt->pageSize = pageSize;
    pBt->psAligned = FORCE_ALIGNMENT(pageSize);
    sqlite3pager_set_pagesize(pBt->pPager, pageSize);
  }
  pBt->usableSize = pBt->pageSize - nReserve;
  return SQLITE_OK;
}

/*

      goto page1_init_failed;
    }
    pBt->pageSize = get2byte(&page1[16]);
    pBt->usableSize = pBt->pageSize - page1[20];
    if( pBt->usableSize<500 ){
      goto page1_init_failed;
    }
    pBt->psAligned = FORCE_ALIGNMENT(pBt->pageSize);
    pBt->maxEmbedFrac = page1[21];
    pBt->minEmbedFrac = page1[22];
    pBt->minLeafFrac = page1[23];
  }

  /* maxLocal is the maximum amount of payload to store locally for
  ** a cell.  Make sure it is small enough so that at least minFanout

**
** If there is a transaction in progress, this routine is a no-op.
*/
static void unlockBtreeIfUnused(Btree *pBt){
  if( pBt->inTrans==TRANS_NONE && pBt->pCursor==0 && pBt->pPage1!=0 ){
    if( pBt->pPage1->aData==0 ){
      MemPage *pPage = pBt->pPage1;
      pPage->aData = &((char*)pPage)[-pBt->pageSize];
      pPage->aData = &((char*)pPage)[-pBt->psAligned];
      pPage->pBt = pBt;
      pPage->pgno = 1;
    }
    releasePage(pBt->pPage1);
    pBt->pPage1 = 0;
    pBt->inStmt = 0;
  }

  MemPage *pThis;
  unsigned char *aData;

  if( pgno==0 ) return;
  assert( pBt->pPager!=0 );
  aData = sqlite3pager_lookup(pBt->pPager, pgno);
  if( aData ){
    pThis = (MemPage*)&aData[pBt->pageSize];
    pThis = (MemPage*)&aData[pBt->psAligned];
    assert( pThis->aData==aData );
    if( pThis->isInit ){
      if( pThis->pParent!=pNewParent ){
        if( pThis->pParent ) sqlite3pager_unref(pThis->pParent->aData);
        pThis->pParent = pNewParent;
        if( pNewParent ) sqlite3pager_ref(pNewParent->aData);
      }

  /*
  ** Allocate space for memory structures
  */
  mxCellPerPage = MX_CELL(pBt);
  apCell = sqliteMallocRaw( 
       (mxCellPerPage+2)*NB*(sizeof(u8*)+sizeof(int))
     + sizeof(MemPage)*NB
     + pBt->pageSize*(5+NB)
     + pBt->psAligned*(5+NB)
  );
  if( apCell==0 ){
    return SQLITE_NOMEM;
  }
  szCell = (int*)&apCell[(mxCellPerPage+2)*NB];
  aCopy[0] = (u8*)&szCell[(mxCellPerPage+2)*NB];
  for(i=1; i<NB; i++){
    aCopy[i] = &aCopy[i-1][pBt->pageSize+sizeof(MemPage)];
    aCopy[i] = &aCopy[i-1][pBt->psAligned+sizeof(MemPage)];
  }
  aSpace = &aCopy[NB-1][pBt->pageSize+sizeof(MemPage)];
  aSpace = &aCopy[NB-1][pBt->psAligned+sizeof(MemPage)];
  
  /*
  ** Find the cell in the parent page whose left child points back
  ** to pPage.  The "idx" variable is the index of that cell.  If pPage
  ** is the rightmost child of pParent then set idx to pParent->nCell 
  */
  if( pParent->idxShift ){

  /*
  ** Make copies of the content of pPage and its siblings into aOld[].
  ** The rest of this function will use data from the copies rather
  ** that the original pages since the original pages will be in the
  ** process of being overwritten.
  */
  for(i=0; i<nOld; i++){
    MemPage *p = apCopy[i] = (MemPage*)&aCopy[i][pBt->pageSize];
    p->aData = &((u8*)p)[-pBt->pageSize];
    memcpy(p->aData, apOld[i]->aData, pBt->pageSize + sizeof(MemPage));
    p->aData = &((u8*)p)[-pBt->pageSize];
    MemPage *p = apCopy[i] = (MemPage*)&aCopy[i][pBt->psAligned];
    p->aData = &((u8*)p)[-pBt->psAligned];
    memcpy(p->aData, apOld[i]->aData, pBt->psAligned + sizeof(MemPage));
    p->aData = &((u8*)p)[-pBt->psAligned];
  }

  /*
  ** Load pointers to all cells on sibling pages and the divider cells
  ** into the local apCell[] array.  Make copies of the divider cells
  ** into space obtained form aSpace[] and remove the the divider Cells
  ** from pParent.

        */
        dropCell(pParent, nxDiv, sz);
      }else{
        u8 *pTemp;
        szCell[nCell] = sz;
        pTemp = &aSpace[iSpace];
        iSpace += sz;
        assert( iSpace<=pBt->pageSize*5 );
        assert( iSpace<=pBt->psAligned*5 );
        memcpy(pTemp, apDiv[i], sz);
        apCell[nCell] = pTemp+leafCorrection;
        dropCell(pParent, nxDiv, sz);
        szCell[nCell] -= leafCorrection;
        assert( get4byte(pTemp)==pgnoOld[i] );
        if( !pOld->leaf ){
          assert( leafCorrection==0 );

      }else if( leafData ){
        CellInfo info;
        j--;
        parseCellPtr(pNew, apCell[j], &info);
        pCell = &aSpace[iSpace];
        fillInCell(pParent, pCell, 0, info.nKey, 0, 0, &sz);
        iSpace += sz;
        assert( iSpace<=pBt->pageSize*5 );
        assert( iSpace<=pBt->psAligned*5 );
        pTemp = 0;
      }else{
        pCell -= 4;
        pTemp = &aSpace[iSpace];
        iSpace += sz;
        assert( iSpace<=pBt->pageSize*5 );
        assert( iSpace<=pBt->psAligned*5 );
      }
      insertCell(pParent, nxDiv, pCell, sz, pTemp);
      put4byte(findOverflowCell(pParent,nxDiv), pNew->pgno);
      j++;
      nxDiv++;
    }
  }

** The pager is used to access a database disk file.  It implements
** atomic commit and rollback through the use of a journal file that
** is separate from the database file.  The pager also implements file
** locking to prevent two processes from writing the same database
** file simultaneously, or one process from reading the database while
** another is writing.
**
** @(#) $Id: pager.c,v 1.167 2004/10/05 02:41:43 drh Exp $
** @(#) $Id: pager.c,v 1.168 2004/10/22 16:22:59 drh Exp $
*/
#include "sqliteInt.h"
#include "os.h"
#include "pager.h"
#include <assert.h>
#include <string.h>

** (if it never invokes its busy callback) then the contention will be
** resolved quickly.
*/
#ifndef SQLITE_BUSY_RESERVED_LOCK
# define SQLITE_BUSY_RESERVED_LOCK 0
#endif

/*
** This macro rounds values up so that if the value is an address it
** is guaranteed to be an address that is aligned to an 8-byte boundary.
*/
#define FORCE_ALIGNMENT(X)   (((X)+7)&~7)

/*
** Each in-memory image of a page begins with the following header.
** This header is only visible to this pager module.  The client
** code that calls pager sees only the data that follows the header.
**
** Client code should call sqlite3pager_write() on a page prior to making
** any modifications to that page.  The first time sqlite3pager_write()

  u8 inJournal;                  /* TRUE if has been written to journal */
  u8 inStmt;                     /* TRUE if in the statement subjournal */
  u8 dirty;                      /* TRUE if we need to write back changes */
  u8 needSync;                   /* Sync journal before writing this page */
  u8 alwaysRollback;             /* Disable dont_rollback() for this page */
  short int nRef;                /* Number of users of this page */
  PgHdr *pDirty;                 /* Dirty pages sorted by PgHdr.pgno */
  /* pPager->pageSize bytes of page data follow this header */
  /* pPager->psAligned bytes of page data follow this header */
  /* Pager.nExtra bytes of local data follow the page data */
};

/*
** For an in-memory only database, some extra information is recorded about
** each page so that changes can be rolled back.  (Journal files are not
** used for in-memory databases.)  The following information is added to

/*
** Convert a pointer to a PgHdr into a pointer to its data
** and back again.
*/
#define PGHDR_TO_DATA(P)  ((void*)(&(P)[1]))
#define DATA_TO_PGHDR(D)  (&((PgHdr*)(D))[-1])
#define PGHDR_TO_EXTRA(G,P) ((void*)&((char*)(&(G)[1]))[(P)->pageSize])
#define PGHDR_TO_EXTRA(G,P) ((void*)&((char*)(&(G)[1]))[(P)->psAligned])
#define PGHDR_TO_HIST(P,PGR)  \
            ((PgHistory*)&((char*)(&(P)[1]))[(PGR)->pageSize+(PGR)->nExtra])
            ((PgHistory*)&((char*)(&(P)[1]))[(PGR)->psAligned+(PGR)->nExtra])

/*
** How big to make the hash table used for locating in-memory pages
** by page number.
*/
#define N_PG_HASH 2048

  int nRec;                   /* Number of pages written to the journal */
  u32 cksumInit;              /* Quasi-random value added to every checksum */
  int stmtNRec;               /* Number of records in stmt subjournal */
  int nExtra;                 /* Add this many bytes to each in-memory page */
  void (*xDestructor)(void*,int); /* Call this routine when freeing pages */
  void (*xReiniter)(void*,int);   /* Call this routine when reloading pages */
  int pageSize;               /* Number of bytes in a page */
  int psAligned;              /* pageSize rounded up to a multiple of 8 */
  int nPage;                  /* Total number of in-memory pages */
  int nRef;                   /* Number of in-memory pages with PgHdr.nRef>0 */
  int mxPage;                 /* Maximum number of pages to hold in cache */
  int nHit, nMiss, nOvfl;     /* Cache hits, missing, and LRU overflows */
  void (*xCodec)(void*,void*,Pgno,int); /* Routine for en/decoding data */
  void *pCodecArg;            /* First argument to xCodec() */
  u8 journalOpen;             /* True if journal file descriptors is valid */

  pPager->journalOpen = 0;
  pPager->useJournal = useJournal && !memDb;
  pPager->stmtOpen = 0;
  pPager->stmtInUse = 0;
  pPager->nRef = 0;
  pPager->dbSize = memDb-1;
  pPager->pageSize = SQLITE_DEFAULT_PAGE_SIZE;
  pPager->psAligned = FORCE_ALIGNMENT(pPager->pageSize);
  pPager->stmtSize = 0;
  pPager->stmtJSize = 0;
  pPager->nPage = 0;
  pPager->mxPage = 100;
  pPager->state = PAGER_UNLOCK;
  pPager->errMask = 0;
  pPager->tempFile = tempFile;
  pPager->memDb = memDb;
  pPager->readOnly = readOnly;
  pPager->needSync = 0;
  pPager->noSync = pPager->tempFile || !useJournal;
  pPager->fullSync = (pPager->noSync?0:1);
  pPager->pFirst = 0;
  pPager->pFirstSynced = 0;
  pPager->pLast = 0;
  pPager->nExtra = nExtra;
  pPager->nExtra = FORCE_ALIGNMENT(nExtra);
  pPager->sectorSize = PAGER_SECTOR_SIZE;
  pPager->pBusyHandler = 0;
  memset(pPager->aHash, 0, sizeof(pPager->aHash));
  *ppPager = pPager;
  return SQLITE_OK;
}

** Set the page size.
**
** The page size must only be changed when the cache is empty.
*/
void sqlite3pager_set_pagesize(Pager *pPager, int pageSize){
  assert( pageSize>=512 && pageSize<=SQLITE_MAX_PAGE_SIZE );
  pPager->pageSize = pageSize;
  pPager->psAligned = FORCE_ALIGNMENT(pageSize);
}

/*
** Read the first N bytes from the beginning of the file into memory
** that pDest points to.  No error checking is done.
*/
void sqlite3pager_read_fileheader(Pager *pPager, int N, unsigned char *pDest){

  }
  if( pPg==0 ){
    /* The requested page is not in the page cache. */
    int h;
    pPager->nMiss++;
    if( pPager->nPage<pPager->mxPage || pPager->pFirst==0 || pPager->memDb ){
      /* Create a new page */
      pPg = sqliteMallocRaw( sizeof(*pPg) + pPager->pageSize 
      pPg = sqliteMallocRaw( sizeof(*pPg) + pPager->psAligned
                              + sizeof(u32) + pPager->nExtra
                              + pPager->memDb*sizeof(PgHistory) );
      if( pPg==0 ){
        if( !pPager->memDb ){
          pager_unwritelock(pPager);
        }
        pPager->errMask |= PAGER_ERR_MEM;

# 2004 September 2
#
# 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.
#
#***********************************************************************
# This file implements regression tests for SQLite library.
# This file implements tests for the page_size PRAGMA.
#
# $Id: pagesize.test,v 1.3 2004/09/05 00:33:44 drh Exp $
# $Id: pagesize.test,v 1.4 2004/10/22 16:22:59 drh Exp $


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

do_test pagesize-1.1 {
  execsql {PRAGMA page_size}

    PRAGMA page_size=65537;
    PRAGMA page_size;
  }
} 8192
  


foreach PGSZ {512 2000 2048 3000 4096} {
foreach PGSZ {512 515 516 751 2000 2001 2002 2003 2004 2048 3000 4096} {
  do_test pagesize-2.$PGSZ.1 {
    db close
    file delete -force test.db
    sqlite3 db test.db
    execsql "PRAGMA page_size=$PGSZ"
    execsql {
      CREATE TABLE t1(x);