blob: 103a1f3230f1c9b9ad74468ae35911a1530287aa [file] [log] [blame]
/*
** 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.
**
*************************************************************************
** This file implements a external (disk-based) database using BTrees.
** See the header comment on "btreeInt.h" for additional information.
** Including a description of file format and an overview of operation.
*/
#include "btreeInt.h"
/*
** The header string that appears at the beginning of every
** SQLite database.
*/
static const char zMagicHeader[] = SQLITE_FILE_HEADER;
/*
** Set this global variable to 1 to enable tracing using the TRACE
** macro.
*/
#if 0
int sqlite3BtreeTrace=1; /* True to enable tracing */
# define TRACE(X) if(sqlite3BtreeTrace){printf X;fflush(stdout);}
#else
# define TRACE(X)
#endif
/*
** Extract a 2-byte big-endian integer from an array of unsigned bytes.
** But if the value is zero, make it 65536.
**
** This routine is used to extract the "offset to cell content area" value
** from the header of a btree page. If the page size is 65536 and the page
** is empty, the offset should be 65536, but the 2-byte value stores zero.
** This routine makes the necessary adjustment to 65536.
*/
#define get2byteNotZero(X) (((((int)get2byte(X))-1)&0xffff)+1)
#ifndef SQLITE_OMIT_SHARED_CACHE
/*
** A list of BtShared objects that are eligible for participation
** in shared cache. This variable has file scope during normal builds,
** but the test harness needs to access it so we make it global for
** test builds.
**
** Access to this variable is protected by SQLITE_MUTEX_STATIC_MASTER.
*/
#ifdef SQLITE_TEST
BtShared *SQLITE_WSD sqlite3SharedCacheList = 0;
#else
static BtShared *SQLITE_WSD sqlite3SharedCacheList = 0;
#endif
#endif /* SQLITE_OMIT_SHARED_CACHE */
#ifndef SQLITE_OMIT_SHARED_CACHE
/*
** Enable or disable the shared pager and schema features.
**
** This routine has no effect on existing database connections.
** The shared cache setting effects only future calls to
** sqlite3_open(), sqlite3_open16(), or sqlite3_open_v2().
*/
int sqlite3_enable_shared_cache(int enable){
sqlite3GlobalConfig.sharedCacheEnabled = enable;
return SQLITE_OK;
}
#endif
#ifdef SQLITE_OMIT_SHARED_CACHE
/*
** The functions querySharedCacheTableLock(), setSharedCacheTableLock(),
** and clearAllSharedCacheTableLocks()
** manipulate entries in the BtShared.pLock linked list used to store
** shared-cache table level locks. If the library is compiled with the
** shared-cache feature disabled, then there is only ever one user
** of each BtShared structure and so this locking is not necessary.
** So define the lock related functions as no-ops.
*/
#define querySharedCacheTableLock(a,b,c) SQLITE_OK
#define setSharedCacheTableLock(a,b,c) SQLITE_OK
#define clearAllSharedCacheTableLocks(a)
#define downgradeAllSharedCacheTableLocks(a)
#define hasSharedCacheTableLock(a,b,c,d) 1
#define hasReadConflicts(a, b) 0
#endif
#ifndef SQLITE_OMIT_SHARED_CACHE
#ifdef SQLITE_DEBUG
/*
**** This function is only used as part of an assert() statement. ***
**
** Check to see if pBtree holds the required locks to read or write to the
** table with root page iRoot. Return 1 if it does and 0 if not.
**
** For example, when writing to a table with root-page iRoot via
** Btree connection pBtree:
**
** assert( hasSharedCacheTableLock(pBtree, iRoot, 0, WRITE_LOCK) );
**
** When writing to an index that resides in a sharable database, the
** caller should have first obtained a lock specifying the root page of
** the corresponding table. This makes things a bit more complicated,
** as this module treats each table as a separate structure. To determine
** the table corresponding to the index being written, this
** function has to search through the database schema.
**
** Instead of a lock on the table/index rooted at page iRoot, the caller may
** hold a write-lock on the schema table (root page 1). This is also
** acceptable.
*/
static int hasSharedCacheTableLock(
Btree *pBtree, /* Handle that must hold lock */
Pgno iRoot, /* Root page of b-tree */
int isIndex, /* True if iRoot is the root of an index b-tree */
int eLockType /* Required lock type (READ_LOCK or WRITE_LOCK) */
){
Schema *pSchema = (Schema *)pBtree->pBt->pSchema;
Pgno iTab = 0;
BtLock *pLock;
/* If this database is not shareable, or if the client is reading
** and has the read-uncommitted flag set, then no lock is required.
** Return true immediately.
*/
if( (pBtree->sharable==0)
|| (eLockType==READ_LOCK && (pBtree->db->flags & SQLITE_ReadUncommitted))
){
return 1;
}
/* If the client is reading or writing an index and the schema is
** not loaded, then it is too difficult to actually check to see if
** the correct locks are held. So do not bother - just return true.
** This case does not come up very often anyhow.
*/
if( isIndex && (!pSchema || (pSchema->flags&DB_SchemaLoaded)==0) ){
return 1;
}
/* Figure out the root-page that the lock should be held on. For table
** b-trees, this is just the root page of the b-tree being read or
** written. For index b-trees, it is the root page of the associated
** table. */
if( isIndex ){
HashElem *p;
for(p=sqliteHashFirst(&pSchema->idxHash); p; p=sqliteHashNext(p)){
Index *pIdx = (Index *)sqliteHashData(p);
if( pIdx->tnum==(int)iRoot ){
iTab = pIdx->pTable->tnum;
}
}
}else{
iTab = iRoot;
}
/* Search for the required lock. Either a write-lock on root-page iTab, a
** write-lock on the schema table, or (if the client is reading) a
** read-lock on iTab will suffice. Return 1 if any of these are found. */
for(pLock=pBtree->pBt->pLock; pLock; pLock=pLock->pNext){
if( pLock->pBtree==pBtree
&& (pLock->iTable==iTab || (pLock->eLock==WRITE_LOCK && pLock->iTable==1))
&& pLock->eLock>=eLockType
){
return 1;
}
}
/* Failed to find the required lock. */
return 0;
}
#endif /* SQLITE_DEBUG */
#ifdef SQLITE_DEBUG
/*
**** This function may be used as part of assert() statements only. ****
**
** Return true if it would be illegal for pBtree to write into the
** table or index rooted at iRoot because other shared connections are
** simultaneously reading that same table or index.
**
** It is illegal for pBtree to write if some other Btree object that
** shares the same BtShared object is currently reading or writing
** the iRoot table. Except, if the other Btree object has the
** read-uncommitted flag set, then it is OK for the other object to
** have a read cursor.
**
** For example, before writing to any part of the table or index
** rooted at page iRoot, one should call:
**
** assert( !hasReadConflicts(pBtree, iRoot) );
*/
static int hasReadConflicts(Btree *pBtree, Pgno iRoot){
BtCursor *p;
for(p=pBtree->pBt->pCursor; p; p=p->pNext){
if( p->pgnoRoot==iRoot
&& p->pBtree!=pBtree
&& 0==(p->pBtree->db->flags & SQLITE_ReadUncommitted)
){
return 1;
}
}
return 0;
}
#endif /* #ifdef SQLITE_DEBUG */
/*
** Query to see if Btree handle p may obtain a lock of type eLock
** (READ_LOCK or WRITE_LOCK) on the table with root-page iTab. Return
** SQLITE_OK if the lock may be obtained (by calling
** setSharedCacheTableLock()), or SQLITE_LOCKED if not.
*/
static int querySharedCacheTableLock(Btree *p, Pgno iTab, u8 eLock){
BtShared *pBt = p->pBt;
BtLock *pIter;
assert( sqlite3BtreeHoldsMutex(p) );
assert( eLock==READ_LOCK || eLock==WRITE_LOCK );
assert( p->db!=0 );
assert( !(p->db->flags&SQLITE_ReadUncommitted)||eLock==WRITE_LOCK||iTab==1 );
/* If requesting a write-lock, then the Btree must have an open write
** transaction on this file. And, obviously, for this to be so there
** must be an open write transaction on the file itself.
*/
assert( eLock==READ_LOCK || (p==pBt->pWriter && p->inTrans==TRANS_WRITE) );
assert( eLock==READ_LOCK || pBt->inTransaction==TRANS_WRITE );
/* This routine is a no-op if the shared-cache is not enabled */
if( !p->sharable ){
return SQLITE_OK;
}
/* If some other connection is holding an exclusive lock, the
** requested lock may not be obtained.
*/
if( pBt->pWriter!=p && pBt->isExclusive ){
sqlite3ConnectionBlocked(p->db, pBt->pWriter->db);
return SQLITE_LOCKED_SHAREDCACHE;
}
for(pIter=pBt->pLock; pIter; pIter=pIter->pNext){
/* The condition (pIter->eLock!=eLock) in the following if(...)
** statement is a simplification of:
**
** (eLock==WRITE_LOCK || pIter->eLock==WRITE_LOCK)
**
** since we know that if eLock==WRITE_LOCK, then no other connection
** may hold a WRITE_LOCK on any table in this file (since there can
** only be a single writer).
*/
assert( pIter->eLock==READ_LOCK || pIter->eLock==WRITE_LOCK );
assert( eLock==READ_LOCK || pIter->pBtree==p || pIter->eLock==READ_LOCK);
if( pIter->pBtree!=p && pIter->iTable==iTab && pIter->eLock!=eLock ){
sqlite3ConnectionBlocked(p->db, pIter->pBtree->db);
if( eLock==WRITE_LOCK ){
assert( p==pBt->pWriter );
pBt->isPending = 1;
}
return SQLITE_LOCKED_SHAREDCACHE;
}
}
return SQLITE_OK;
}
#endif /* !SQLITE_OMIT_SHARED_CACHE */
#ifndef SQLITE_OMIT_SHARED_CACHE
/*
** Add a lock on the table with root-page iTable to the shared-btree used
** by Btree handle p. Parameter eLock must be either READ_LOCK or
** WRITE_LOCK.
**
** This function assumes the following:
**
** (a) The specified Btree object p is connected to a sharable
** database (one with the BtShared.sharable flag set), and
**
** (b) No other Btree objects hold a lock that conflicts
** with the requested lock (i.e. querySharedCacheTableLock() has
** already been called and returned SQLITE_OK).
**
** SQLITE_OK is returned if the lock is added successfully. SQLITE_NOMEM
** is returned if a malloc attempt fails.
*/
static int setSharedCacheTableLock(Btree *p, Pgno iTable, u8 eLock){
BtShared *pBt = p->pBt;
BtLock *pLock = 0;
BtLock *pIter;
assert( sqlite3BtreeHoldsMutex(p) );
assert( eLock==READ_LOCK || eLock==WRITE_LOCK );
assert( p->db!=0 );
/* A connection with the read-uncommitted flag set will never try to
** obtain a read-lock using this function. The only read-lock obtained
** by a connection in read-uncommitted mode is on the sqlite_master
** table, and that lock is obtained in BtreeBeginTrans(). */
assert( 0==(p->db->flags&SQLITE_ReadUncommitted) || eLock==WRITE_LOCK );
/* This function should only be called on a sharable b-tree after it
** has been determined that no other b-tree holds a conflicting lock. */
assert( p->sharable );
assert( SQLITE_OK==querySharedCacheTableLock(p, iTable, eLock) );
/* First search the list for an existing lock on this table. */
for(pIter=pBt->pLock; pIter; pIter=pIter->pNext){
if( pIter->iTable==iTable && pIter->pBtree==p ){
pLock = pIter;
break;
}
}
/* If the above search did not find a BtLock struct associating Btree p
** with table iTable, allocate one and link it into the list.
*/
if( !pLock ){
pLock = (BtLock *)sqlite3MallocZero(sizeof(BtLock));
if( !pLock ){
return SQLITE_NOMEM;
}
pLock->iTable = iTable;
pLock->pBtree = p;
pLock->pNext = pBt->pLock;
pBt->pLock = pLock;
}
/* Set the BtLock.eLock variable to the maximum of the current lock
** and the requested lock. This means if a write-lock was already held
** and a read-lock requested, we don't incorrectly downgrade the lock.
*/
assert( WRITE_LOCK>READ_LOCK );
if( eLock>pLock->eLock ){
pLock->eLock = eLock;
}
return SQLITE_OK;
}
#endif /* !SQLITE_OMIT_SHARED_CACHE */
#ifndef SQLITE_OMIT_SHARED_CACHE
/*
** Release all the table locks (locks obtained via calls to
** the setSharedCacheTableLock() procedure) held by Btree object p.
**
** This function assumes that Btree p has an open read or write
** transaction. If it does not, then the BtShared.isPending variable
** may be incorrectly cleared.
*/
static void clearAllSharedCacheTableLocks(Btree *p){
BtShared *pBt = p->pBt;
BtLock **ppIter = &pBt->pLock;
assert( sqlite3BtreeHoldsMutex(p) );
assert( p->sharable || 0==*ppIter );
assert( p->inTrans>0 );
while( *ppIter ){
BtLock *pLock = *ppIter;
assert( pBt->isExclusive==0 || pBt->pWriter==pLock->pBtree );
assert( pLock->pBtree->inTrans>=pLock->eLock );
if( pLock->pBtree==p ){
*ppIter = pLock->pNext;
assert( pLock->iTable!=1 || pLock==&p->lock );
if( pLock->iTable!=1 ){
sqlite3_free(pLock);
}
}else{
ppIter = &pLock->pNext;
}
}
assert( pBt->isPending==0 || pBt->pWriter );
if( pBt->pWriter==p ){
pBt->pWriter = 0;
pBt->isExclusive = 0;
pBt->isPending = 0;
}else if( pBt->nTransaction==2 ){
/* This function is called when Btree p is concluding its
** transaction. If there currently exists a writer, and p is not
** that writer, then the number of locks held by connections other
** than the writer must be about to drop to zero. In this case
** set the isPending flag to 0.
**
** If there is not currently a writer, then BtShared.isPending must
** be zero already. So this next line is harmless in that case.
*/
pBt->isPending = 0;
}
}
/*
** This function changes all write-locks held by Btree p into read-locks.
*/
static void downgradeAllSharedCacheTableLocks(Btree *p){
BtShared *pBt = p->pBt;
if( pBt->pWriter==p ){
BtLock *pLock;
pBt->pWriter = 0;
pBt->isExclusive = 0;
pBt->isPending = 0;
for(pLock=pBt->pLock; pLock; pLock=pLock->pNext){
assert( pLock->eLock==READ_LOCK || pLock->pBtree==p );
pLock->eLock = READ_LOCK;
}
}
}
#endif /* SQLITE_OMIT_SHARED_CACHE */
static void releasePage(MemPage *pPage); /* Forward reference */
/*
***** This routine is used inside of assert() only ****
**
** Verify that the cursor holds the mutex on its BtShared
*/
#ifdef SQLITE_DEBUG
static int cursorHoldsMutex(BtCursor *p){
return sqlite3_mutex_held(p->pBt->mutex);
}
#endif
#ifndef SQLITE_OMIT_INCRBLOB
/*
** Invalidate the overflow page-list cache for cursor pCur, if any.
*/
static void invalidateOverflowCache(BtCursor *pCur){
assert( cursorHoldsMutex(pCur) );
sqlite3_free(pCur->aOverflow);
pCur->aOverflow = 0;
}
/*
** Invalidate the overflow page-list cache for all cursors opened
** on the shared btree structure pBt.
*/
static void invalidateAllOverflowCache(BtShared *pBt){
BtCursor *p;
assert( sqlite3_mutex_held(pBt->mutex) );
for(p=pBt->pCursor; p; p=p->pNext){
invalidateOverflowCache(p);
}
}
/*
** This function is called before modifying the contents of a table
** to invalidate any incrblob cursors that are open on the
** row or one of the rows being modified.
**
** If argument isClearTable is true, then the entire contents of the
** table is about to be deleted. In this case invalidate all incrblob
** cursors open on any row within the table with root-page pgnoRoot.
**
** Otherwise, if argument isClearTable is false, then the row with
** rowid iRow is being replaced or deleted. In this case invalidate
** only those incrblob cursors open on that specific row.
*/
static void invalidateIncrblobCursors(
Btree *pBtree, /* The database file to check */
i64 iRow, /* The rowid that might be changing */
int isClearTable /* True if all rows are being deleted */
){
BtCursor *p;
BtShared *pBt = pBtree->pBt;
assert( sqlite3BtreeHoldsMutex(pBtree) );
for(p=pBt->pCursor; p; p=p->pNext){
if( p->isIncrblobHandle && (isClearTable || p->info.nKey==iRow) ){
p->eState = CURSOR_INVALID;
}
}
}
#else
/* Stub functions when INCRBLOB is omitted */
#define invalidateOverflowCache(x)
#define invalidateAllOverflowCache(x)
#define invalidateIncrblobCursors(x,y,z)
#endif /* SQLITE_OMIT_INCRBLOB */
/*
** Set bit pgno of the BtShared.pHasContent bitvec. This is called
** when a page that previously contained data becomes a free-list leaf
** page.
**
** The BtShared.pHasContent bitvec exists to work around an obscure
** bug caused by the interaction of two useful IO optimizations surrounding
** free-list leaf pages:
**
** 1) When all data is deleted from a page and the page becomes
** a free-list leaf page, the page is not written to the database
** (as free-list leaf pages contain no meaningful data). Sometimes
** such a page is not even journalled (as it will not be modified,
** why bother journalling it?).
**
** 2) When a free-list leaf page is reused, its content is not read
** from the database or written to the journal file (why should it
** be, if it is not at all meaningful?).
**
** By themselves, these optimizations work fine and provide a handy
** performance boost to bulk delete or insert operations. However, if
** a page is moved to the free-list and then reused within the same
** transaction, a problem comes up. If the page is not journalled when
** it is moved to the free-list and it is also not journalled when it
** is extracted from the free-list and reused, then the original data
** may be lost. In the event of a rollback, it may not be possible
** to restore the database to its original configuration.
**
** The solution is the BtShared.pHasContent bitvec. Whenever a page is
** moved to become a free-list leaf page, the corresponding bit is
** set in the bitvec. Whenever a leaf page is extracted from the free-list,
** optimization 2 above is omitted if the corresponding bit is already
** set in BtShared.pHasContent. The contents of the bitvec are cleared
** at the end of every transaction.
*/
static int btreeSetHasContent(BtShared *pBt, Pgno pgno){
int rc = SQLITE_OK;
if( !pBt->pHasContent ){
assert( pgno<=pBt->nPage );
pBt->pHasContent = sqlite3BitvecCreate(pBt->nPage);
if( !pBt->pHasContent ){
rc = SQLITE_NOMEM;
}
}
if( rc==SQLITE_OK && pgno<=sqlite3BitvecSize(pBt->pHasContent) ){
rc = sqlite3BitvecSet(pBt->pHasContent, pgno);
}
return rc;
}
/*
** Query the BtShared.pHasContent vector.
**
** This function is called when a free-list leaf page is removed from the
** free-list for reuse. It returns false if it is safe to retrieve the
** page from the pager layer with the 'no-content' flag set. True otherwise.
*/
static int btreeGetHasContent(BtShared *pBt, Pgno pgno){
Bitvec *p = pBt->pHasContent;
return (p && (pgno>sqlite3BitvecSize(p) || sqlite3BitvecTest(p, pgno)));
}
/*
** Clear (destroy) the BtShared.pHasContent bitvec. This should be
** invoked at the conclusion of each write-transaction.
*/
static void btreeClearHasContent(BtShared *pBt){
sqlite3BitvecDestroy(pBt->pHasContent);
pBt->pHasContent = 0;
}
/*
** Save the current cursor position in the variables BtCursor.nKey
** and BtCursor.pKey. The cursor's state is set to CURSOR_REQUIRESEEK.
**
** The caller must ensure that the cursor is valid (has eState==CURSOR_VALID)
** prior to calling this routine.
*/
static int saveCursorPosition(BtCursor *pCur){
int rc;
assert( CURSOR_VALID==pCur->eState );
assert( 0==pCur->pKey );
assert( cursorHoldsMutex(pCur) );
rc = sqlite3BtreeKeySize(pCur, &pCur->nKey);
assert( rc==SQLITE_OK ); /* KeySize() cannot fail */
/* If this is an intKey table, then the above call to BtreeKeySize()
** stores the integer key in pCur->nKey. In this case this value is
** all that is required. Otherwise, if pCur is not open on an intKey
** table, then malloc space for and store the pCur->nKey bytes of key
** data.
*/
if( 0==pCur->apPage[0]->intKey ){
void *pKey = sqlite3Malloc( (int)pCur->nKey );
if( pKey ){
rc = sqlite3BtreeKey(pCur, 0, (int)pCur->nKey, pKey);
if( rc==SQLITE_OK ){
pCur->pKey = pKey;
}else{
sqlite3_free(pKey);
}
}else{
rc = SQLITE_NOMEM;
}
}
assert( !pCur->apPage[0]->intKey || !pCur->pKey );
if( rc==SQLITE_OK ){
int i;
for(i=0; i<=pCur->iPage; i++){
releasePage(pCur->apPage[i]);
pCur->apPage[i] = 0;
}
pCur->iPage = -1;
pCur->eState = CURSOR_REQUIRESEEK;
}
invalidateOverflowCache(pCur);
return rc;
}
/*
** Save the positions of all cursors (except pExcept) that are open on
** the table with root-page iRoot. Usually, this is called just before cursor
** pExcept is used to modify the table (BtreeDelete() or BtreeInsert()).
*/
static int saveAllCursors(BtShared *pBt, Pgno iRoot, BtCursor *pExcept){
BtCursor *p;
assert( sqlite3_mutex_held(pBt->mutex) );
assert( pExcept==0 || pExcept->pBt==pBt );
for(p=pBt->pCursor; p; p=p->pNext){
if( p!=pExcept && (0==iRoot || p->pgnoRoot==iRoot) &&
p->eState==CURSOR_VALID ){
int rc = saveCursorPosition(p);
if( SQLITE_OK!=rc ){
return rc;
}
}
}
return SQLITE_OK;
}
/*
** Clear the current cursor position.
*/
void sqlite3BtreeClearCursor(BtCursor *pCur){
assert( cursorHoldsMutex(pCur) );
sqlite3_free(pCur->pKey);
pCur->pKey = 0;
pCur->eState = CURSOR_INVALID;
}
/*
** In this version of BtreeMoveto, pKey is a packed index record
** such as is generated by the OP_MakeRecord opcode. Unpack the
** record and then call BtreeMovetoUnpacked() to do the work.
*/
static int btreeMoveto(
BtCursor *pCur, /* Cursor open on the btree to be searched */
const void *pKey, /* Packed key if the btree is an index */
i64 nKey, /* Integer key for tables. Size of pKey for indices */
int bias, /* Bias search to the high end */
int *pRes /* Write search results here */
){
int rc; /* Status code */
UnpackedRecord *pIdxKey; /* Unpacked index key */
char aSpace[150]; /* Temp space for pIdxKey - to avoid a malloc */
if( pKey ){
assert( nKey==(i64)(int)nKey );
pIdxKey = sqlite3VdbeRecordUnpack(pCur->pKeyInfo, (int)nKey, pKey,
aSpace, sizeof(aSpace));
if( pIdxKey==0 ) return SQLITE_NOMEM;
}else{
pIdxKey = 0;
}
rc = sqlite3BtreeMovetoUnpacked(pCur, pIdxKey, nKey, bias, pRes);
if( pKey ){
sqlite3VdbeDeleteUnpackedRecord(pIdxKey);
}
return rc;
}
/*
** Restore the cursor to the position it was in (or as close to as possible)
** when saveCursorPosition() was called. Note that this call deletes the
** saved position info stored by saveCursorPosition(), so there can be
** at most one effective restoreCursorPosition() call after each
** saveCursorPosition().
*/
static int btreeRestoreCursorPosition(BtCursor *pCur){
int rc;
assert( cursorHoldsMutex(pCur) );
assert( pCur->eState>=CURSOR_REQUIRESEEK );
if( pCur->eState==CURSOR_FAULT ){
return pCur->skipNext;
}
pCur->eState = CURSOR_INVALID;
rc = btreeMoveto(pCur, pCur->pKey, pCur->nKey, 0, &pCur->skipNext);
if( rc==SQLITE_OK ){
sqlite3_free(pCur->pKey);
pCur->pKey = 0;
assert( pCur->eState==CURSOR_VALID || pCur->eState==CURSOR_INVALID );
}
return rc;
}
#define restoreCursorPosition(p) \
(p->eState>=CURSOR_REQUIRESEEK ? \
btreeRestoreCursorPosition(p) : \
SQLITE_OK)
/*
** Determine whether or not a cursor has moved from the position it
** was last placed at. Cursors can move when the row they are pointing
** at is deleted out from under them.
**
** This routine returns an error code if something goes wrong. The
** integer *pHasMoved is set to one if the cursor has moved and 0 if not.
*/
int sqlite3BtreeCursorHasMoved(BtCursor *pCur, int *pHasMoved){
int rc;
rc = restoreCursorPosition(pCur);
if( rc ){
*pHasMoved = 1;
return rc;
}
if( pCur->eState!=CURSOR_VALID || pCur->skipNext!=0 ){
*pHasMoved = 1;
}else{
*pHasMoved = 0;
}
return SQLITE_OK;
}
#ifndef SQLITE_OMIT_AUTOVACUUM
/*
** Given a page number of a regular database page, return the page
** number for the pointer-map page that contains the entry for the
** input page number.
**
** Return 0 (not a valid page) for pgno==1 since there is
** no pointer map associated with page 1. The integrity_check logic
** requires that ptrmapPageno(*,1)!=1.
*/
static Pgno ptrmapPageno(BtShared *pBt, Pgno pgno){
int nPagesPerMapPage;
Pgno iPtrMap, ret;
assert( sqlite3_mutex_held(pBt->mutex) );
if( pgno<2 ) return 0;
nPagesPerMapPage = (pBt->usableSize/5)+1;
iPtrMap = (pgno-2)/nPagesPerMapPage;
ret = (iPtrMap*nPagesPerMapPage) + 2;
if( ret==PENDING_BYTE_PAGE(pBt) ){
ret++;
}
return ret;
}
/*
** Write an entry into the pointer map.
**
** This routine updates the pointer map entry for page number 'key'
** so that it maps to type 'eType' and parent page number 'pgno'.
**
** If *pRC is initially non-zero (non-SQLITE_OK) then this routine is
** a no-op. If an error occurs, the appropriate error code is written
** into *pRC.
*/
static void ptrmapPut(BtShared *pBt, Pgno key, u8 eType, Pgno parent, int *pRC){
DbPage *pDbPage; /* The pointer map page */
u8 *pPtrmap; /* The pointer map data */
Pgno iPtrmap; /* The pointer map page number */
int offset; /* Offset in pointer map page */
int rc; /* Return code from subfunctions */
if( *pRC ) return;
assert( sqlite3_mutex_held(pBt->mutex) );
/* The master-journal page number must never be used as a pointer map page */
assert( 0==PTRMAP_ISPAGE(pBt, PENDING_BYTE_PAGE(pBt)) );
assert( pBt->autoVacuum );
if( key==0 ){
*pRC = SQLITE_CORRUPT_BKPT;
return;
}
iPtrmap = PTRMAP_PAGENO(pBt, key);
rc = sqlite3PagerGet(pBt->pPager, iPtrmap, &pDbPage);
if( rc!=SQLITE_OK ){
*pRC = rc;
return;
}
offset = PTRMAP_PTROFFSET(iPtrmap, key);
if( offset<0 ){
*pRC = SQLITE_CORRUPT_BKPT;
goto ptrmap_exit;
}
pPtrmap = (u8 *)sqlite3PagerGetData(pDbPage);
if( eType!=pPtrmap[offset] || get4byte(&pPtrmap[offset+1])!=parent ){
TRACE(("PTRMAP_UPDATE: %d->(%d,%d)\n", key, eType, parent));
*pRC= rc = sqlite3PagerWrite(pDbPage);
if( rc==SQLITE_OK ){
pPtrmap[offset] = eType;
put4byte(&pPtrmap[offset+1], parent);
}
}
ptrmap_exit:
sqlite3PagerUnref(pDbPage);
}
/*
** Read an entry from the pointer map.
**
** This routine retrieves the pointer map entry for page 'key', writing
** the type and parent page number to *pEType and *pPgno respectively.
** An error code is returned if something goes wrong, otherwise SQLITE_OK.
*/
static int ptrmapGet(BtShared *pBt, Pgno key, u8 *pEType, Pgno *pPgno){
DbPage *pDbPage; /* The pointer map page */
int iPtrmap; /* Pointer map page index */
u8 *pPtrmap; /* Pointer map page data */
int offset; /* Offset of entry in pointer map */
int rc;
assert( sqlite3_mutex_held(pBt->mutex) );
iPtrmap = PTRMAP_PAGENO(pBt, key);
rc = sqlite3PagerGet(pBt->pPager, iPtrmap, &pDbPage);
if( rc!=0 ){
return rc;
}
pPtrmap = (u8 *)sqlite3PagerGetData(pDbPage);
offset = PTRMAP_PTROFFSET(iPtrmap, key);
assert( pEType!=0 );
*pEType = pPtrmap[offset];
if( pPgno ) *pPgno = get4byte(&pPtrmap[offset+1]);
sqlite3PagerUnref(pDbPage);
if( *pEType<1 || *pEType>5 ) return SQLITE_CORRUPT_BKPT;
return SQLITE_OK;
}
#else /* if defined SQLITE_OMIT_AUTOVACUUM */
#define ptrmapPut(w,x,y,z,rc)
#define ptrmapGet(w,x,y,z) SQLITE_OK
#define ptrmapPutOvflPtr(x, y, rc)
#endif
/*
** Given a btree page and a cell index (0 means the first cell on
** the page, 1 means the second cell, and so forth) return a pointer
** to the cell content.
**
** This routine works only for pages that do not contain overflow cells.
*/
#define findCell(P,I) \
((P)->aData + ((P)->maskPage & get2byte(&(P)->aData[(P)->cellOffset+2*(I)])))
/*
** This a more complex version of findCell() that works for
** pages that do contain overflow cells.
*/
static u8 *findOverflowCell(MemPage *pPage, int iCell){
int i;
assert( sqlite3_mutex_held(pPage->pBt->mutex) );
for(i=pPage->nOverflow-1; i>=0; i--){
int k;
struct _OvflCell *pOvfl;
pOvfl = &pPage->aOvfl[i];
k = pOvfl->idx;
if( k<=iCell ){
if( k==iCell ){
return pOvfl->pCell;
}
iCell--;
}
}
return findCell(pPage, iCell);
}
/*
** Parse a cell content block and fill in the CellInfo structure. There
** are two versions of this function. btreeParseCell() takes a
** cell index as the second argument and btreeParseCellPtr()
** takes a pointer to the body of the cell as its second argument.
**
** Within this file, the parseCell() macro can be called instead of
** btreeParseCellPtr(). Using some compilers, this will be faster.
*/
static void btreeParseCellPtr(
MemPage *pPage, /* Page containing the cell */
u8 *pCell, /* Pointer to the cell text. */
CellInfo *pInfo /* Fill in this structure */
){
u16 n; /* Number bytes in cell content header */
u32 nPayload; /* Number of bytes of cell payload */
assert( sqlite3_mutex_held(pPage->pBt->mutex) );
pInfo->pCell = pCell;
assert( pPage->leaf==0 || pPage->leaf==1 );
n = pPage->childPtrSize;
assert( n==4-4*pPage->leaf );
if( pPage->intKey ){
if( pPage->hasData ){
n += getVarint32(&pCell[n], nPayload);
}else{
nPayload = 0;
}
n += getVarint(&pCell[n], (u64*)&pInfo->nKey);
pInfo->nData = nPayload;
}else{
pInfo->nData = 0;
n += getVarint32(&pCell[n], nPayload);
pInfo->nKey = nPayload;
}
pInfo->nPayload = nPayload;
pInfo->nHeader = n;
testcase( nPayload==pPage->maxLocal );
testcase( nPayload==pPage->maxLocal+1 );
if( likely(nPayload<=pPage->maxLocal) ){
/* This is the (easy) common case where the entire payload fits
** on the local page. No overflow is required.
*/
if( (pInfo->nSize = (u16)(n+nPayload))<4 ) pInfo->nSize = 4;
pInfo->nLocal = (u16)nPayload;
pInfo->iOverflow = 0;
}else{
/* If the payload will not fit completely on the local page, we have
** to decide how much to store locally and how much to spill onto
** overflow pages. The strategy is to minimize the amount of unused
** space on overflow pages while keeping the amount of local storage
** in between minLocal and maxLocal.
**
** Warning: changing the way overflow payload is distributed in any
** way will result in an incompatible file format.
*/
int minLocal; /* Minimum amount of payload held locally */
int maxLocal; /* Maximum amount of payload held locally */
int surplus; /* Overflow payload available for local storage */
minLocal = pPage->minLocal;
maxLocal = pPage->maxLocal;
surplus = minLocal + (nPayload - minLocal)%(pPage->pBt->usableSize - 4);
testcase( surplus==maxLocal );
testcase( surplus==maxLocal+1 );
if( surplus <= maxLocal ){
pInfo->nLocal = (u16)surplus;
}else{
pInfo->nLocal = (u16)minLocal;
}
pInfo->iOverflow = (u16)(pInfo->nLocal + n);
pInfo->nSize = pInfo->iOverflow + 4;
}
}
#define parseCell(pPage, iCell, pInfo) \
btreeParseCellPtr((pPage), findCell((pPage), (iCell)), (pInfo))
static void btreeParseCell(
MemPage *pPage, /* Page containing the cell */
int iCell, /* The cell index. First cell is 0 */
CellInfo *pInfo /* Fill in this structure */
){
parseCell(pPage, iCell, pInfo);
}
/*
** Compute the total number of bytes that a Cell needs in the cell
** data area of the btree-page. The return number includes the cell
** data header and the local payload, but not any overflow page or
** the space used by the cell pointer.
*/
static u16 cellSizePtr(MemPage *pPage, u8 *pCell){
u8 *pIter = &pCell[pPage->childPtrSize];
u32 nSize;
#ifdef SQLITE_DEBUG
/* The value returned by this function should always be the same as
** the (CellInfo.nSize) value found by doing a full parse of the
** cell. If SQLITE_DEBUG is defined, an assert() at the bottom of
** this function verifies that this invariant is not violated. */
CellInfo debuginfo;
btreeParseCellPtr(pPage, pCell, &debuginfo);
#endif
if( pPage->intKey ){
u8 *pEnd;
if( pPage->hasData ){
pIter += getVarint32(pIter, nSize);
}else{
nSize = 0;
}
/* pIter now points at the 64-bit integer key value, a variable length
** integer. The following block moves pIter to point at the first byte
** past the end of the key value. */
pEnd = &pIter[9];
while( (*pIter++)&0x80 && pIter<pEnd );
}else{
pIter += getVarint32(pIter, nSize);
}
testcase( nSize==pPage->maxLocal );
testcase( nSize==pPage->maxLocal+1 );
if( nSize>pPage->maxLocal ){
int minLocal = pPage->minLocal;
nSize = minLocal + (nSize - minLocal) % (pPage->pBt->usableSize - 4);
testcase( nSize==pPage->maxLocal );
testcase( nSize==pPage->maxLocal+1 );
if( nSize>pPage->maxLocal ){
nSize = minLocal;
}
nSize += 4;
}
nSize += (u32)(pIter - pCell);
/* The minimum size of any cell is 4 bytes. */
if( nSize<4 ){
nSize = 4;
}
assert( nSize==debuginfo.nSize );
return (u16)nSize;
}
#ifdef SQLITE_DEBUG
/* This variation on cellSizePtr() is used inside of assert() statements
** only. */
static u16 cellSize(MemPage *pPage, int iCell){
return cellSizePtr(pPage, findCell(pPage, iCell));
}
#endif
#ifndef SQLITE_OMIT_AUTOVACUUM
/*
** If the cell pCell, part of page pPage contains a pointer
** to an overflow page, insert an entry into the pointer-map
** for the overflow page.
*/
static void ptrmapPutOvflPtr(MemPage *pPage, u8 *pCell, int *pRC){
CellInfo info;
if( *pRC ) return;
assert( pCell!=0 );
btreeParseCellPtr(pPage, pCell, &info);
assert( (info.nData+(pPage->intKey?0:info.nKey))==info.nPayload );
if( info.iOverflow ){
Pgno ovfl = get4byte(&pCell[info.iOverflow]);
ptrmapPut(pPage->pBt, ovfl, PTRMAP_OVERFLOW1, pPage->pgno, pRC);
}
}
#endif
/*
** Defragment the page given. All Cells are moved to the
** end of the page and all free space is collected into one
** big FreeBlk that occurs in between the header and cell
** pointer array and the cell content area.
*/
static int defragmentPage(MemPage *pPage){
int i; /* Loop counter */
int pc; /* Address of a i-th cell */
int hdr; /* Offset to the page header */
int size; /* Size of a cell */
int usableSize; /* Number of usable bytes on a page */
int cellOffset; /* Offset to the cell pointer array */
int cbrk; /* Offset to the cell content area */
int nCell; /* Number of cells on the page */
unsigned char *data; /* The page data */
unsigned char *temp; /* Temp area for cell content */
int iCellFirst; /* First allowable cell index */
int iCellLast; /* Last possible cell index */
assert( sqlite3PagerIswriteable(pPage->pDbPage) );
assert( pPage->pBt!=0 );
assert( pPage->pBt->usableSize <= SQLITE_MAX_PAGE_SIZE );
assert( pPage->nOverflow==0 );
assert( sqlite3_mutex_held(pPage->pBt->mutex) );
temp = sqlite3PagerTempSpace(pPage->pBt->pPager);
data = pPage->aData;
hdr = pPage->hdrOffset;
cellOffset = pPage->cellOffset;
nCell = pPage->nCell;
assert( nCell==get2byte(&data[hdr+3]) );
usableSize = pPage->pBt->usableSize;
cbrk = get2byte(&data[hdr+5]);
memcpy(&temp[cbrk], &data[cbrk], usableSize - cbrk);
cbrk = usableSize;
iCellFirst = cellOffset + 2*nCell;
iCellLast = usableSize - 4;
for(i=0; i<nCell; i++){
u8 *pAddr; /* The i-th cell pointer */
pAddr = &data[cellOffset + i*2];
pc = get2byte(pAddr);
testcase( pc==iCellFirst );
testcase( pc==iCellLast );
#if !defined(SQLITE_ENABLE_OVERSIZE_CELL_CHECK)
/* These conditions have already been verified in btreeInitPage()
** if SQLITE_ENABLE_OVERSIZE_CELL_CHECK is defined
*/
if( pc<iCellFirst || pc>iCellLast ){
return SQLITE_CORRUPT_BKPT;
}
#endif
assert( pc>=iCellFirst && pc<=iCellLast );
size = cellSizePtr(pPage, &temp[pc]);
cbrk -= size;
#if defined(SQLITE_ENABLE_OVERSIZE_CELL_CHECK)
if( cbrk<iCellFirst ){
return SQLITE_CORRUPT_BKPT;
}
#else
if( cbrk<iCellFirst || pc+size>usableSize ){
return SQLITE_CORRUPT_BKPT;
}
#endif
assert( cbrk+size<=usableSize && cbrk>=iCellFirst );
testcase( cbrk+size==usableSize );
testcase( pc+size==usableSize );
memcpy(&data[cbrk], &temp[pc], size);
put2byte(pAddr, cbrk);
}
assert( cbrk>=iCellFirst );
put2byte(&data[hdr+5], cbrk);
data[hdr+1] = 0;
data[hdr+2] = 0;
data[hdr+7] = 0;
memset(&data[iCellFirst], 0, cbrk-iCellFirst);
assert( sqlite3PagerIswriteable(pPage->pDbPage) );
if( cbrk-iCellFirst!=pPage->nFree ){
return SQLITE_CORRUPT_BKPT;
}
return SQLITE_OK;
}
/*
** Allocate nByte bytes of space from within the B-Tree page passed
** as the first argument. Write into *pIdx the index into pPage->aData[]
** of the first byte of allocated space. Return either SQLITE_OK or
** an error code (usually SQLITE_CORRUPT).
**
** The caller guarantees that there is sufficient space to make the
** allocation. This routine might need to defragment in order to bring
** all the space together, however. This routine will avoid using
** the first two bytes past the cell pointer area since presumably this
** allocation is being made in order to insert a new cell, so we will
** also end up needing a new cell pointer.
*/
static int allocateSpace(MemPage *pPage, int nByte, int *pIdx){
const int hdr = pPage->hdrOffset; /* Local cache of pPage->hdrOffset */
u8 * const data = pPage->aData; /* Local cache of pPage->aData */
int nFrag; /* Number of fragmented bytes on pPage */
int top; /* First byte of cell content area */
int gap; /* First byte of gap between cell pointers and cell content */
int rc; /* Integer return code */
int usableSize; /* Usable size of the page */
assert( sqlite3PagerIswriteable(pPage->pDbPage) );
assert( pPage->pBt );
assert( sqlite3_mutex_held(pPage->pBt->mutex) );
assert( nByte>=0 ); /* Minimum cell size is 4 */
assert( pPage->nFree>=nByte );
assert( pPage->nOverflow==0 );
usableSize = pPage->pBt->usableSize;
assert( nByte < usableSize-8 );
nFrag = data[hdr+7];
assert( pPage->cellOffset == hdr + 12 - 4*pPage->leaf );
gap = pPage->cellOffset + 2*pPage->nCell;
top = get2byteNotZero(&data[hdr+5]);
if( gap>top ) return SQLITE_CORRUPT_BKPT;
testcase( gap+2==top );
testcase( gap+1==top );
testcase( gap==top );
if( nFrag>=60 ){
/* Always defragment highly fragmented pages */
rc = defragmentPage(pPage);
if( rc ) return rc;
top = get2byteNotZero(&data[hdr+5]);
}else if( gap+2<=top ){
/* Search the freelist looking for a free slot big enough to satisfy
** the request. The allocation is made from the first free slot in
** the list that is large enough to accomadate it.
*/
int pc, addr;
for(addr=hdr+1; (pc = get2byte(&data[addr]))>0; addr=pc){
int size; /* Size of the free slot */
if( pc>usableSize-4 || pc<addr+4 ){
return SQLITE_CORRUPT_BKPT;
}
size = get2byte(&data[pc+2]);
if( size>=nByte ){
int x = size - nByte;
testcase( x==4 );
testcase( x==3 );
if( x<4 ){
/* Remove the slot from the free-list. Update the number of
** fragmented bytes within the page. */
memcpy(&data[addr], &data[pc], 2);
data[hdr+7] = (u8)(nFrag + x);
}else if( size+pc > usableSize ){
return SQLITE_CORRUPT_BKPT;
}else{
/* The slot remains on the free-list. Reduce its size to account
** for the portion used by the new allocation. */
put2byte(&data[pc+2], x);
}
*pIdx = pc + x;
return SQLITE_OK;
}
}
}
/* Check to make sure there is enough space in the gap to satisfy
** the allocation. If not, defragment.
*/
testcase( gap+2+nByte==top );
if( gap+2+nByte>top ){
rc = defragmentPage(pPage);
if( rc ) return rc;
top = get2byteNotZero(&data[hdr+5]);
assert( gap+nByte<=top );
}
/* Allocate memory from the gap in between the cell pointer array
** and the cell content area. The btreeInitPage() call has already
** validated the freelist. Given that the freelist is valid, there
** is no way that the allocation can extend off the end of the page.
** The assert() below verifies the previous sentence.
*/
top -= nByte;
put2byte(&data[hdr+5], top);
assert( top+nByte <= (int)pPage->pBt->usableSize );
*pIdx = top;
return SQLITE_OK;
}
/*
** Return a section of the pPage->aData to the freelist.
** The first byte of the new free block is pPage->aDisk[start]
** and the size of the block is "size" bytes.
**
** Most of the effort here is involved in coalesing adjacent
** free blocks into a single big free block.
*/
static int freeSpace(MemPage *pPage, int start, int size){
int addr, pbegin, hdr;
int iLast; /* Largest possible freeblock offset */
unsigned char *data = pPage->aData;
assert( pPage->pBt!=0 );
assert( sqlite3PagerIswriteable(pPage->pDbPage) );
assert( start>=pPage->hdrOffset+6+pPage->childPtrSize );
assert( (start + size) <= (int)pPage->pBt->usableSize );
assert( sqlite3_mutex_held(pPage->pBt->mutex) );
assert( size>=0 ); /* Minimum cell size is 4 */
if( pPage->pBt->secureDelete ){
/* Overwrite deleted information with zeros when the secure_delete
** option is enabled */
memset(&data[start], 0, size);
}
/* Add the space back into the linked list of freeblocks. Note that
** even though the freeblock list was checked by btreeInitPage(),
** btreeInitPage() did not detect overlapping cells or
** freeblocks that overlapped cells. Nor does it detect when the
** cell content area exceeds the value in the page header. If these
** situations arise, then subsequent insert operations might corrupt
** the freelist. So we do need to check for corruption while scanning
** the freelist.
*/
hdr = pPage->hdrOffset;
addr = hdr + 1;
iLast = pPage->pBt->usableSize - 4;
assert( start<=iLast );
while( (pbegin = get2byte(&data[addr]))<start && pbegin>0 ){
if( pbegin<addr+4 ){
return SQLITE_CORRUPT_BKPT;
}
addr = pbegin;
}
if( pbegin>iLast ){
return SQLITE_CORRUPT_BKPT;
}
assert( pbegin>addr || pbegin==0 );
put2byte(&data[addr], start);
put2byte(&data[start], pbegin);
put2byte(&data[start+2], size);
pPage->nFree = pPage->nFree + (u16)size;
/* Coalesce adjacent free blocks */
addr = hdr + 1;
while( (pbegin = get2byte(&data[addr]))>0 ){
int pnext, psize, x;
assert( pbegin>addr );
assert( pbegin <= (int)pPage->pBt->usableSize-4 );
pnext = get2byte(&data[pbegin]);
psize = get2byte(&data[pbegin+2]);
if( pbegin + psize + 3 >= pnext && pnext>0 ){
int frag = pnext - (pbegin+psize);
if( (frag<0) || (frag>(int)data[hdr+7]) ){
return SQLITE_CORRUPT_BKPT;
}
data[hdr+7] -= (u8)frag;
x = get2byte(&data[pnext]);
put2byte(&data[pbegin], x);
x = pnext + get2byte(&data[pnext+2]) - pbegin;
put2byte(&data[pbegin+2], x);
}else{
addr = pbegin;
}
}
/* If the cell content area begins with a freeblock, remove it. */
if( data[hdr+1]==data[hdr+5] && data[hdr+2]==data[hdr+6] ){
int top;
pbegin = get2byte(&data[hdr+1]);
memcpy(&data[hdr+1], &data[pbegin], 2);
top = get2byte(&data[hdr+5]) + get2byte(&data[pbegin+2]);
put2byte(&data[hdr+5], top);
}
assert( sqlite3PagerIswriteable(pPage->pDbPage) );
return SQLITE_OK;
}
/*
** Decode the flags byte (the first byte of the header) for a page
** and initialize fields of the MemPage structure accordingly.
**
** Only the following combinations are supported. Anything different
** indicates a corrupt database files:
**
** PTF_ZERODATA
** PTF_ZERODATA | PTF_LEAF
** PTF_LEAFDATA | PTF_INTKEY
** PTF_LEAFDATA | PTF_INTKEY | PTF_LEAF
*/
static int decodeFlags(MemPage *pPage, int flagByte){
BtShared *pBt; /* A copy of pPage->pBt */
assert( pPage->hdrOffset==(pPage->pgno==1 ? 100 : 0) );
assert( sqlite3_mutex_held(pPage->pBt->mutex) );
pPage->leaf = (u8)(flagByte>>3); assert( PTF_LEAF == 1<<3 );
flagByte &= ~PTF_LEAF;
pPage->childPtrSize = 4-4*pPage->leaf;
pBt = pPage->pBt;
if( flagByte==(PTF_LEAFDATA | PTF_INTKEY) ){
pPage->intKey = 1;
pPage->hasData = pPage->leaf;
pPage->maxLocal = pBt->maxLeaf;
pPage->minLocal = pBt->minLeaf;
}else if( flagByte==PTF_ZERODATA ){
pPage->intKey = 0;
pPage->hasData = 0;
pPage->maxLocal = pBt->maxLocal;
pPage->minLocal = pBt->minLocal;
}else{
return SQLITE_CORRUPT_BKPT;
}
return SQLITE_OK;
}
/*
** Initialize the auxiliary information for a disk block.
**
** Return SQLITE_OK on success. If we see that the page does
** not contain a well-formed database page, then return
** SQLITE_CORRUPT. Note that a return of SQLITE_OK does not
** guarantee that the page is well-formed. It only shows that
** we failed to detect any corruption.
*/
static int btreeInitPage(MemPage *pPage){
assert( pPage->pBt!=0 );
assert( sqlite3_mutex_held(pPage->pBt->mutex) );
assert( pPage->pgno==sqlite3PagerPagenumber(pPage->pDbPage) );
assert( pPage == sqlite3PagerGetExtra(pPage->pDbPage) );
assert( pPage->aData == sqlite3PagerGetData(pPage->pDbPage) );
if( !pPage->isInit ){
u16 pc; /* Address of a freeblock within pPage->aData[] */
u8 hdr; /* Offset to beginning of page header */
u8 *data; /* Equal to pPage->aData */
BtShared *pBt; /* The main btree structure */
int usableSize; /* Amount of usable space on each page */
u16 cellOffset; /* Offset from start of page to first cell pointer */
int nFree; /* Number of unused bytes on the page */
int top; /* First byte of the cell content area */
int iCellFirst; /* First allowable cell or freeblock offset */
int iCellLast; /* Last possible cell or freeblock offset */
pBt = pPage->pBt;
hdr = pPage->hdrOffset;
data = pPage->aData;
if( decodeFlags(pPage, data[hdr]) ) return SQLITE_CORRUPT_BKPT;
assert( pBt->pageSize>=512 && pBt->pageSize<=65536 );
pPage->maskPage = (u16)(pBt->pageSize - 1);
pPage->nOverflow = 0;
usableSize = pBt->usableSize;
pPage->cellOffset = cellOffset = hdr + 12 - 4*pPage->leaf;
top = get2byteNotZero(&data[hdr+5]);
pPage->nCell = get2byte(&data[hdr+3]);
if( pPage->nCell>MX_CELL(pBt) ){
/* To many cells for a single page. The page must be corrupt */
return SQLITE_CORRUPT_BKPT;
}
testcase( pPage->nCell==MX_CELL(pBt) );
/* A malformed database page might cause us to read past the end
** of page when parsing a cell.
**
** The following block of code checks early to see if a cell extends
** past the end of a page boundary and causes SQLITE_CORRUPT to be
** returned if it does.
*/
iCellFirst = cellOffset + 2*pPage->nCell;
iCellLast = usableSize - 4;
#if defined(SQLITE_ENABLE_OVERSIZE_CELL_CHECK)
{
int i; /* Index into the cell pointer array */
int sz; /* Size of a cell */
if( !pPage->leaf ) iCellLast--;
for(i=0; i<pPage->nCell; i++){
pc = get2byte(&data[cellOffset+i*2]);
testcase( pc==iCellFirst );
testcase( pc==iCellLast );
if( pc<iCellFirst || pc>iCellLast ){
return SQLITE_CORRUPT_BKPT;
}
sz = cellSizePtr(pPage, &data[pc]);
testcase( pc+sz==usableSize );
if( pc+sz>usableSize ){
return SQLITE_CORRUPT_BKPT;
}
}
if( !pPage->leaf ) iCellLast++;
}
#endif
/* Compute the total free space on the page */
pc = get2byte(&data[hdr+1]);
nFree = data[hdr+7] + top;
while( pc>0 ){
u16 next, size;
if( pc<iCellFirst || pc>iCellLast ){
/* Start of free block is off the page */
return SQLITE_CORRUPT_BKPT;
}
next = get2byte(&data[pc]);
size = get2byte(&data[pc+2]);
if( (next>0 && next<=pc+size+3) || pc+size>usableSize ){
/* Free blocks must be in ascending order. And the last byte of
** the free-block must lie on the database page. */
return SQLITE_CORRUPT_BKPT;
}
nFree = nFree + size;
pc = next;
}
/* At this point, nFree contains the sum of the offset to the start
** of the cell-content area plus the number of free bytes within
** the cell-content area. If this is greater than the usable-size
** of the page, then the page must be corrupted. This check also
** serves to verify that the offset to the start of the cell-content
** area, according to the page header, lies within the page.
*/
if( nFree>usableSize ){
return SQLITE_CORRUPT_BKPT;
}
pPage->nFree = (u16)(nFree - iCellFirst);
pPage->isInit = 1;
}
return SQLITE_OK;
}
/*
** Set up a raw page so that it looks like a database page holding
** no entries.
*/
static void zeroPage(MemPage *pPage, int flags){
unsigned char *data = pPage->aData;
BtShared *pBt = pPage->pBt;
u8 hdr = pPage->hdrOffset;
u16 first;
assert( sqlite3PagerPagenumber(pPage->pDbPage)==pPage->pgno );
assert( sqlite3PagerGetExtra(pPage->pDbPage) == (void*)pPage );
assert( sqlite3PagerGetData(pPage->pDbPage) == data );
assert( sqlite3PagerIswriteable(pPage->pDbPage) );
assert( sqlite3_mutex_held(pBt->mutex) );
if( pBt->secureDelete ){
memset(&data[hdr], 0, pBt->usableSize - hdr);
}
data[hdr] = (char)flags;
first = hdr + 8 + 4*((flags&PTF_LEAF)==0 ?1:0);
memset(&data[hdr+1], 0, 4);
data[hdr+7] = 0;
put2byte(&data[hdr+5], pBt->usableSize);
pPage->nFree = (u16)(pBt->usableSize - first);
decodeFlags(pPage, flags);
pPage->hdrOffset = hdr;
pPage->cellOffset = first;
pPage->nOverflow = 0;
assert( pBt->pageSize>=512 && pBt->pageSize<=65536 );
pPage->maskPage = (u16)(pBt->pageSize - 1);
pPage->nCell = 0;
pPage->isInit = 1;
}
/*
** Convert a DbPage obtained from the pager into a MemPage used by
** the btree layer.
*/
static MemPage *btreePageFromDbPage(DbPage *pDbPage, Pgno pgno, BtShared *pBt){
MemPage *pPage = (MemPage*)sqlite3PagerGetExtra(pDbPage);
pPage->aData = sqlite3PagerGetData(pDbPage);
pPage->pDbPage = pDbPage;
pPage->pBt = pBt;
pPage->pgno = pgno;
pPage->hdrOffset = pPage->pgno==1 ? 100 : 0;
return pPage;
}
/*
** Get a page from the pager. Initialize the MemPage.pBt and
** MemPage.aData elements if needed.
**
** If the noContent flag is set, it means that we do not care about
** the content of the page at this time. So do not go to the disk
** to fetch the content. Just fill in the content with zeros for now.
** If in the future we call sqlite3PagerWrite() on this page, that
** means we have started to be concerned about content and the disk
** read should occur at that point.
*/
static int btreeGetPage(
BtShared *pBt, /* The btree */
Pgno pgno, /* Number of the page to fetch */
MemPage **ppPage, /* Return the page in this parameter */
int noContent /* Do not load page content if true */
){
int rc;
DbPage *pDbPage;
assert( sqlite3_mutex_held(pBt->mutex) );
rc = sqlite3PagerAcquire(pBt->pPager, pgno, (DbPage**)&pDbPage, noContent);
if( rc ) return rc;
*ppPage = btreePageFromDbPage(pDbPage, pgno, pBt);
return SQLITE_OK;
}
/*
** Retrieve a page from the pager cache. If the requested page is not
** already in the pager cache return NULL. Initialize the MemPage.pBt and
** MemPage.aData elements if needed.
*/
static MemPage *btreePageLookup(BtShared *pBt, Pgno pgno){
DbPage *pDbPage;
assert( sqlite3_mutex_held(pBt->mutex) );
pDbPage = sqlite3PagerLookup(pBt->pPager, pgno);
if( pDbPage ){
return btreePageFromDbPage(pDbPage, pgno, pBt);
}
return 0;
}
/*
** Return the size of the database file in pages. If there is any kind of
** error, return ((unsigned int)-1).
*/
static Pgno btreePagecount(BtShared *pBt){
return pBt->nPage;
}
u32 sqlite3BtreeLastPage(Btree *p){
assert( sqlite3BtreeHoldsMutex(p) );
assert( ((p->pBt->nPage)&0x8000000)==0 );
return (int)btreePagecount(p->pBt);
}
/*
** Get a page from the pager and initialize it. This routine is just a
** convenience wrapper around separate calls to btreeGetPage() and
** btreeInitPage().
**
** If an error occurs, then the value *ppPage is set to is undefined. It
** may remain unchanged, or it may be set to an invalid value.
*/
static int getAndInitPage(
BtShared *pBt, /* The database file */
Pgno pgno, /* Number of the page to get */
MemPage **ppPage /* Write the page pointer here */
){
int rc;
assert( sqlite3_mutex_held(pBt->mutex) );
if( pgno>btreePagecount(pBt) ){
rc = SQLITE_CORRUPT_BKPT;
}else{
rc = btreeGetPage(pBt, pgno, ppPage, 0);
if( rc==SQLITE_OK ){
rc = btreeInitPage(*ppPage);
if( rc!=SQLITE_OK ){
releasePage(*ppPage);
}
}
}
testcase( pgno==0 );
assert( pgno!=0 || rc==SQLITE_CORRUPT );
return rc;
}
/*
** Release a MemPage. This should be called once for each prior
** call to btreeGetPage.
*/
static void releasePage(MemPage *pPage){
if( pPage ){
assert( pPage->aData );
assert( pPage->pBt );
assert( sqlite3PagerGetExtra(pPage->pDbPage) == (void*)pPage );
assert( sqlite3PagerGetData(pPage->pDbPage)==pPage->aData );
assert( sqlite3_mutex_held(pPage->pBt->mutex) );
sqlite3PagerUnref(pPage->pDbPage);
}
}
/*
** 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(DbPage *pData){
MemPage *pPage;
pPage = (MemPage *)sqlite3PagerGetExtra(pData);
assert( sqlite3PagerPageRefcount(pData)>0 );
if( pPage->isInit ){
assert( sqlite3_mutex_held(pPage->pBt->mutex) );
pPage->isInit = 0;
if( sqlite3PagerPageRefcount(pData)>1 ){
/* pPage might not be a btree page; it might be an overflow page
** or ptrmap page or a free page. In those cases, the following
** call to btreeInitPage() will likely return SQLITE_CORRUPT.
** But no harm is done by this. And it is very important that
** btreeInitPage() be called on every btree page so we make
** the call for every page that comes in for re-initing. */
btreeInitPage(pPage);
}
}
}
/*
** Invoke the busy handler for a btree.
*/
static int btreeInvokeBusyHandler(void *pArg){
BtShared *pBt = (BtShared*)pArg;
assert( pBt->db );
assert( sqlite3_mutex_held(pBt->db->mutex) );
return sqlite3InvokeBusyHandler(&pBt->db->busyHandler);
}
/*
** Open a database file.
**
** zFilename is the name of the database file. If zFilename is NULL
** then an ephemeral database is created. The ephemeral database might
** be exclusively in memory, or it might use a disk-based memory cache.
** Either way, the ephemeral database will be automatically deleted
** when sqlite3BtreeClose() is called.
**
** If zFilename is ":memory:" then an in-memory database is created
** that is automatically destroyed when it is closed.
**
** The "flags" parameter is a bitmask that might contain bits
** BTREE_OMIT_JOURNAL and/or BTREE_NO_READLOCK. The BTREE_NO_READLOCK
** bit is also set if the SQLITE_NoReadlock flags is set in db->flags.
** These flags are passed through into sqlite3PagerOpen() and must
** be the same values as PAGER_OMIT_JOURNAL and PAGER_NO_READLOCK.
**
** If the database is already opened in the same database connection
** and we are in shared cache mode, then the open will fail with an
** SQLITE_CONSTRAINT error. We cannot allow two or more BtShared
** objects in the same database connection since doing so will lead
** to problems with locking.
*/
int sqlite3BtreeOpen(
const char *zFilename, /* Name of the file containing the BTree database */
sqlite3 *db, /* Associated database handle */
Btree **ppBtree, /* Pointer to new Btree object written here */
int flags, /* Options */
int vfsFlags /* Flags passed through to sqlite3_vfs.xOpen() */
){
sqlite3_vfs *pVfs; /* The VFS to use for this btree */
BtShared *pBt = 0; /* Shared part of btree structure */
Btree *p; /* Handle to return */
sqlite3_mutex *mutexOpen = 0; /* Prevents a race condition. Ticket #3537 */
int rc = SQLITE_OK; /* Result code from this function */
u8 nReserve; /* Byte of unused space on each page */
unsigned char zDbHeader[100]; /* Database header content */
/* True if opening an ephemeral, temporary database */
const int isTempDb = zFilename==0 || zFilename[0]==0;
/* Set the variable isMemdb to true for an in-memory database, or
** false for a file-based database.
*/
#ifdef SQLITE_OMIT_MEMORYDB
const int isMemdb = 0;
#else
const int isMemdb = (zFilename && strcmp(zFilename, ":memory:")==0)
|| (isTempDb && sqlite3TempInMemory(db));
#endif
assert( db!=0 );
assert( sqlite3_mutex_held(db->mutex) );
assert( (flags&0xff)==flags ); /* flags fit in 8 bits */
/* Only a BTREE_SINGLE database can be BTREE_UNORDERED */
assert( (flags & BTREE_UNORDERED)==0 || (flags & BTREE_SINGLE)!=0 );
/* A BTREE_SINGLE database is always a temporary and/or ephemeral */
assert( (flags & BTREE_SINGLE)==0 || isTempDb );
if( db->flags & SQLITE_NoReadlock ){
flags |= BTREE_NO_READLOCK;
}
if( isMemdb ){
flags |= BTREE_MEMORY;
}
if( (vfsFlags & SQLITE_OPEN_MAIN_DB)!=0 && (isMemdb || isTempDb) ){
vfsFlags = (vfsFlags & ~SQLITE_OPEN_MAIN_DB) | SQLITE_OPEN_TEMP_DB;
}
pVfs = db->pVfs;
p = sqlite3MallocZero(sizeof(Btree));
if( !p ){
return SQLITE_NOMEM;
}
p->inTrans = TRANS_NONE;
p->db = db;
#ifndef SQLITE_OMIT_SHARED_CACHE
p->lock.pBtree = p;
p->lock.iTable = 1;
#endif
#if !defined(SQLITE_OMIT_SHARED_CACHE) && !defined(SQLITE_OMIT_DISKIO)
/*
** If this Btree is a candidate for shared cache, try to find an
** existing BtShared object that we can share with
*/
if( isMemdb==0 && isTempDb==0 ){
if( vfsFlags & SQLITE_OPEN_SHAREDCACHE ){
int nFullPathname = pVfs->mxPathname+1;
char *zFullPathname = sqlite3Malloc(nFullPathname);
sqlite3_mutex *mutexShared;
p->sharable = 1;
if( !zFullPathname ){
sqlite3_free(p);
return SQLITE_NOMEM;
}
sqlite3OsFullPathname(pVfs, zFilename, nFullPathname, zFullPathname);
mutexOpen = sqlite3MutexAlloc(SQLITE_MUTEX_STATIC_OPEN);
sqlite3_mutex_enter(mutexOpen);
mutexShared = sqlite3MutexAlloc(SQLITE_MUTEX_STATIC_MASTER);
sqlite3_mutex_enter(mutexShared);
for(pBt=GLOBAL(BtShared*,sqlite3SharedCacheList); pBt; pBt=pBt->pNext){
assert( pBt->nRef>0 );
if( 0==strcmp(zFullPathname, sqlite3PagerFilename(pBt->pPager))
&& sqlite3PagerVfs(pBt->pPager)==pVfs ){
int iDb;
for(iDb=db->nDb-1; iDb>=0; iDb--){
Btree *pExisting = db->aDb[iDb].pBt;
if( pExisting && pExisting->pBt==pBt ){
sqlite3_mutex_leave(mutexShared);
sqlite3_mutex_leave(mutexOpen);
sqlite3_free(zFullPathname);
sqlite3_free(p);
return SQLITE_CONSTRAINT;
}
}
p->pBt = pBt;
pBt->nRef++;
break;
}
}
sqlite3_mutex_leave(mutexShared);
sqlite3_free(zFullPathname);
}
#ifdef SQLITE_DEBUG
else{
/* In debug mode, we mark all persistent databases as sharable
** even when they are not. This exercises the locking code and
** gives more opportunity for asserts(sqlite3_mutex_held())
** statements to find locking problems.
*/
p->sharable = 1;
}
#endif
}
#endif
if( pBt==0 ){
/*
** The following asserts make sure that structures used by the btree are
** the right size. This is to guard against size changes that result
** when compiling on a different architecture.
*/
assert( sizeof(i64)==8 || sizeof(i64)==4 );
assert( sizeof(u64)==8 || sizeof(u64)==4 );
assert( sizeof(u32)==4 );
assert( sizeof(u16)==2 );
assert( sizeof(Pgno)==4 );
pBt = sqlite3MallocZero( sizeof(*pBt) );
if( pBt==0 ){
rc = SQLITE_NOMEM;
goto btree_open_out;
}
rc = sqlite3PagerOpen(pVfs, &pBt->pPager, zFilename,
EXTRA_SIZE, flags, vfsFlags, pageReinit);
if( rc==SQLITE_OK ){
rc = sqlite3PagerReadFileheader(pBt->pPager,sizeof(zDbHeader),zDbHeader);
}
if( rc!=SQLITE_OK ){
goto btree_open_out;
}
pBt->openFlags = (u8)flags;
pBt->db = db;
sqlite3PagerSetBusyhandler(pBt->pPager, btreeInvokeBusyHandler, pBt);
p->pBt = pBt;
pBt->pCursor = 0;
pBt->pPage1 = 0;
pBt->readOnly = sqlite3PagerIsreadonly(pBt->pPager);
#ifdef SQLITE_SECURE_DELETE
pBt->secureDelete = 1;
#endif
pBt->pageSize = (zDbHeader[16]<<8) | (zDbHeader[17]<<16);
if( pBt->pageSize<512 || pBt->pageSize>SQLITE_MAX_PAGE_SIZE
|| ((pBt->pageSize-1)&pBt->pageSize)!=0 ){
pBt->pageSize = 0;
#ifndef SQLITE_OMIT_AUTOVACUUM
/* If the magic name ":memory:" will create an in-memory database, then
** leave the autoVacuum mode at 0 (do not auto-vacuum), even if
** SQLITE_DEFAULT_AUTOVACUUM is true. On the other hand, if
** SQLITE_OMIT_MEMORYDB has been defined, then ":memory:" is just a
** regular file-name. In this case the auto-vacuum applies as per normal.
*/
if( zFilename && !isMemdb ){
pBt->autoVacuum = (SQLITE_DEFAULT_AUTOVACUUM ? 1 : 0);
pBt->incrVacuum = (SQLITE_DEFAULT_AUTOVACUUM==2 ? 1 : 0);
}
#endif
nReserve = 0;
}else{
nReserve = zDbHeader[20];
pBt->pageSizeFixed = 1;
#ifndef SQLITE_OMIT_AUTOVACUUM
pBt->autoVacuum = (get4byte(&zDbHeader[36 + 4*4])?1:0);
pBt->incrVacuum = (get4byte(&zDbHeader[36 + 7*4])?1:0);
#endif
}
rc = sqlite3PagerSetPagesize(pBt->pPager, &pBt->pageSize, nReserve);
if( rc ) goto btree_open_out;
pBt->usableSize = pBt->pageSize - nReserve;
assert( (pBt->pageSize & 7)==0 ); /* 8-byte alignment of pageSize */
#if !defined(SQLITE_OMIT_SHARED_CACHE) && !defined(SQLITE_OMIT_DISKIO)
/* Add the new BtShared object to the linked list sharable BtShareds.
*/
if( p->sharable ){
sqlite3_mutex *mutexShared;
pBt->nRef = 1;
mutexShared = sqlite3MutexAlloc(SQLITE_MUTEX_STATIC_MASTER);
if( SQLITE_THREADSAFE && sqlite3GlobalConfig.bCoreMutex ){
pBt->mutex = sqlite3MutexAlloc(SQLITE_MUTEX_FAST);
if( pBt->mutex==0 ){
rc = SQLITE_NOMEM;
db->mallocFailed = 0;
goto btree_open_out;
}
}
sqlite3_mutex_enter(mutexShared);
pBt->pNext = GLOBAL(BtShared*,sqlite3SharedCacheList);
GLOBAL(BtShared*,sqlite3SharedCacheList) = pBt;
sqlite3_mutex_leave(mutexShared);
}
#endif
}
#if !defined(SQLITE_OMIT_SHARED_CACHE) && !defined(SQLITE_OMIT_DISKIO)
/* If the new Btree uses a sharable pBtShared, then link the new
** Btree into the list of all sharable Btrees for the same connection.
** The list is kept in ascending order by pBt address.
*/
if( p->sharable ){
int i;
Btree *pSib;
for(i=0; i<db->nDb; i++){
if( (pSib = db->aDb[i].pBt)!=0 && pSib->sharable ){
while( pSib->pPrev ){ pSib = pSib->pPrev; }
if( p->pBt<pSib->pBt ){
p->pNext = pSib;
p->pPrev = 0;
pSib->pPrev = p;
}else{
while( pSib->pNext && pSib->pNext->pBt<p->pBt ){
pSib = pSib->pNext;
}
p->pNext = pSib->pNext;
p->pPrev = pSib;
if( p->pNext ){
p->pNext->pPrev = p;
}
pSib->pNext = p;
}
break;
}
}
}
#endif
*ppBtree = p;
btree_open_out:
if( rc!=SQLITE_OK ){
if( pBt && pBt->pPager ){
sqlite3PagerClose(pBt->pPager);
}
sqlite3_free(pBt);
sqlite3_free(p);
*ppBtree = 0;
}else{
/* If the B-Tree was successfully opened, set the pager-cache size to the
** default value. Except, when opening on an existing shared pager-cache,
** do not change the pager-cache size.
*/
if( sqlite3BtreeSchema(p, 0, 0)==0 ){
sqlite3PagerSetCachesize(p->pBt->pPager, SQLITE_DEFAULT_CACHE_SIZE);
}
}
if( mutexOpen ){
assert( sqlite3_mutex_held(mutexOpen) );
sqlite3_mutex_leave(mutexOpen);
}
return rc;
}
/*
** Decrement the BtShared.nRef counter. When it reaches zero,
** remove the BtShared structure from the sharing list. Return
** true if the BtShared.nRef counter reaches zero and return
** false if it is still positive.
*/
static int removeFromSharingList(BtShared *pBt){
#ifndef SQLITE_OMIT_SHARED_CACHE
sqlite3_mutex *pMaster;
BtShared *pList;
int removed = 0;
assert( sqlite3_mutex_notheld(pBt->mutex) );
pMaster = sqlite3MutexAlloc(SQLITE_MUTEX_STATIC_MASTER);
sqlite3_mutex_enter(pMaster);
pBt->nRef--;
if( pBt->nRef<=0 ){
if( GLOBAL(BtShared*,sqlite3SharedCacheList)==pBt ){
GLOBAL(BtShared*,sqlite3SharedCacheList) = pBt->pNext;
}else{
pList = GLOBAL(BtShared*,sqlite3SharedCacheList);
while( ALWAYS(pList) && pList->pNext!=pBt ){
pList=pList->pNext;
}
if( ALWAYS(pList) ){
pList->pNext = pBt->pNext;
}
}
if( SQLITE_THREADSAFE ){
sqlite3_mutex_free(pBt->mutex);
}
removed = 1;
}
sqlite3_mutex_leave(pMaster);
return removed;
#else
return 1;
#endif
}
/*
** Make sure pBt->pTmpSpace points to an allocation of
** MX_CELL_SIZE(pBt) bytes.
*/
static void allocateTempSpace(BtShared *pBt){
if( !pBt->pTmpSpace ){
pBt->pTmpSpace = sqlite3PageMalloc( pBt->pageSize );
}
}
/*
** Free the pBt->pTmpSpace allocation
*/
static void freeTempSpace(BtShared *pBt){
sqlite3PageFree( pBt->pTmpSpace);
pBt->pTmpSpace = 0;
}
/*
** Close an open database and invalidate all cursors.
*/
int sqlite3BtreeClose(Btree *p){
BtShared *pBt = p->pBt;
BtCursor *pCur;
/* Close all cursors opened via this handle. */
assert( sqlite3_mutex_held(p->db->mutex) );
sqlite3BtreeEnter(p);
pCur = pBt->pCursor;
while( pCur ){
BtCursor *pTmp = pCur;
pCur = pCur->pNext;
if( pTmp->pBtree==p ){
sqlite3BtreeCloseCursor(pTmp);
}
}
/* Rollback any active transaction and free the handle structure.
** The call to sqlite3BtreeRollback() drops any table-locks held by
** this handle.
*/
sqlite3BtreeRollback(p);
sqlite3BtreeLeave(p);
/* If there are still other outstanding references to the shared-btree
** structure, return now. The remainder of this procedure cleans
** up the shared-btree.
*/
assert( p->wantToLock==0 && p->locked==0 );
if( !p->sharable || removeFromSharingList(pBt) ){
/* The pBt is no longer on the sharing list, so we can access
** it without having to hold the mutex.
**
** Clean out and delete the BtShared object.
*/
assert( !pBt->pCursor );
sqlite3PagerClose(pBt->pPager);
if( pBt->xFreeSchema && pBt->pSchema ){
pBt->xFreeSchema(pBt->pSchema);
}
sqlite3DbFree(0, pBt->pSchema);
freeTempSpace(pBt);
sqlite3_free(pBt);
}
#ifndef SQLITE_OMIT_SHARED_CACHE
assert( p->wantToLock==0 );
assert( p->locked==0 );
if( p->pPrev ) p->pPrev->pNext = p->pNext;
if( p->pNext ) p->pNext->pPrev = p->pPrev;
#endif
sqlite3_free(p);
return SQLITE_OK;
}
/*
** Change the limit on the number of pages allowed in the cache.
**
** The maximum number of cache pages is set to the absolute
** value of mxPage. If mxPage is negative, the pager will
** operate asynchronously - it will not stop to do fsync()s
** to insure data is written to the disk surface before
** continuing. Transactions still work if synchronous is off,
** and the database cannot be corrupted if this program
** crashes. But if the operating system crashes or there is
** an abrupt power failure when synchronous is off, the database
** could be left in an inconsistent and unrecoverable state.
** Synchronous is on by default so database corruption is not
** normally a worry.
*/
int sqlite3BtreeSetCacheSize(Btree *p, int mxPage){
BtShared *pBt = p->pBt;
assert( sqlite3_mutex_held(p->db->mutex) );
sqlite3BtreeEnter(p);
sqlite3PagerSetCachesize(pBt->pPager, mxPage);
sqlite3BtreeLeave(p);
return SQLITE_OK;
}
/*
** Change the way data is synced to disk in order to increase or decrease
** how well the database resists damage due to OS crashes and power
** failures. Level 1 is the same as asynchronous (no syncs() occur and
** there is a high probability of damage) Level 2 is the default. There
** is a very low but non-zero probability of damage. Level 3 reduces the
** probability of damage to near zero but with a write performance reduction.
*/
#ifndef SQLITE_OMIT_PAGER_PRAGMAS
int sqlite3BtreeSetSafetyLevel(
Btree *p, /* The btree to set the safety level on */
int level, /* PRAGMA synchronous. 1=OFF, 2=NORMAL, 3=FULL */
int fullSync, /* PRAGMA fullfsync. */
int ckptFullSync /* PRAGMA checkpoint_fullfync */
){
BtShared *pBt = p->pBt;
assert( sqlite3_mutex_held(p->db->mutex) );
assert( level>=1 && level<=3 );
sqlite3BtreeEnter(p);
sqlite3PagerSetSafetyLevel(pBt->pPager, level, fullSync, ckptFullSync);
sqlite3BtreeLeave(p);
return SQLITE_OK;
}
#endif
/*
** Return TRUE if the given btree is set to safety level 1. In other
** words, return TRUE if no sync() occurs on the disk files.
*/
int sqlite3BtreeSyncDisabled(Btree *p){
BtShared *pBt = p->pBt;
int rc;
assert( sqlite3_mutex_held(p->db->mutex) );
sqlite3BtreeEnter(p);
assert( pBt && pBt->pPager );
rc = sqlite3PagerNosync(pBt->pPager);
sqlite3BtreeLeave(p);
return rc;
}
/*
** Change the default pages size and the number of reserved bytes per page.
** Or, if the page size has already been fixed, return SQLITE_READONLY
** without changing anything.
**
** The page size must be a power of 2 between 512 and 65536. If the page
** size supplied does not meet this constraint then the page size is not
** changed.
**
** Page sizes are constrained to be a power of two so that the region
** of the database file used for locking (beginning at PENDING_BYTE,
** the first byte past the 1GB boundary, 0x40000000) needs to occur
** at the beginning of a page.
**
** If parameter nReserve is less than zero, then the number of reserved
** bytes per page is left unchanged.
**
** If the iFix!=0 then the pageSizeFixed flag is set so that the page size
** and autovacuum mode can no longer be changed.
*/
int sqlite3BtreeSetPageSize(Btree *p, int pageSize, int nReserve, int iFix){
int rc = SQLITE_OK;
BtShared *pBt = p->pBt;
assert( nReserve>=-1 && nReserve<=255 );
sqlite3BtreeEnter(p);
if( pBt->pageSizeFixed ){
sqlite3BtreeLeave(p);
return SQLITE_READONLY;
}
if( nReserve<0 ){
nReserve = pBt->pageSize - pBt->usableSize;
}
assert( nReserve>=0 && nReserve<=255 );
if( pageSize>=512 && pageSize<=SQLITE_MAX_PAGE_SIZE &&
((pageSize-1)&pageSize)==0 ){
assert( (pageSize & 7)==0 );
assert( !pBt->pPage1 && !pBt->pCursor );
pBt->pageSize = (u32)pageSize;
freeTempSpace(pBt);
}
rc = sqlite3PagerSetPagesize(pBt->pPager, &pBt->pageSize, nReserve);
pBt->usableSize = pBt->pageSize - (u16)nReserve;
if( iFix ) pBt->pageSizeFixed = 1;
sqlite3BtreeLeave(p);
return rc;
}
/*
** Return the currently defined page size
*/
int sqlite3BtreeGetPageSize(Btree *p){
return p->pBt->pageSize;
}
#if !defined(SQLITE_OMIT_PAGER_PRAGMAS) || !defined(SQLITE_OMIT_VACUUM)
/*
** Return the number of bytes of space at the end of every page that
** are intentually left unused. This is the "reserved" space that is
** sometimes used by extensions.
*/
int sqlite3BtreeGetReserve(Btree *p){
int n;
sqlite3BtreeEnter(p);
n = p->pBt->pageSize - p->pBt->usableSize;
sqlite3BtreeLeave(p);
return n;
}
/*
** Set the maximum page count for a database if mxPage is positive.
** No changes are made if mxPage is 0 or negative.
** Regardless of the value of mxPage, return the maximum page count.
*/
int sqlite3BtreeMaxPageCount(Btree *p, int mxPage){
int n;
sqlite3BtreeEnter(p);
n = sqlite3PagerMaxPageCount(p->pBt->pPager, mxPage);
sqlite3BtreeLeave(p);
return n;
}
/*
** Set the secureDelete flag if newFlag is 0 or 1. If newFlag is -1,
** then make no changes. Always return the value of the secureDelete
** setting after the change.
*/
int sqlite3BtreeSecureDelete(Btree *p, int newFlag){
int b;
if( p==0 ) return 0;
sqlite3BtreeEnter(p);
if( newFlag>=0 ){
p->pBt->secureDelete = (newFlag!=0) ? 1 : 0;
}
b = p->pBt->secureDelete;
sqlite3BtreeLeave(p);
return b;
}
#endif /* !defined(SQLITE_OMIT_PAGER_PRAGMAS) || !defined(SQLITE_OMIT_VACUUM) */
/*
** Change the 'auto-vacuum' property of the database. If the 'autoVacuum'
** parameter is non-zero, then auto-vacuum mode is enabled. If zero, it
** is disabled. The default value for the auto-vacuum property is
** determined by the SQLITE_DEFAULT_AUTOVACUUM macro.
*/
int sqlite3BtreeSetAutoVacuum(Btree *p, int autoVacuum){
#ifdef SQLITE_OMIT_AUTOVACUUM
return SQLITE_READONLY;
#else
BtShared *pBt = p->pBt;
int rc = SQLITE_OK;
u8 av = (u8)autoVacuum;
sqlite3BtreeEnter(p);
if( pBt->pageSizeFixed && (av ?1:0)!=pBt->autoVacuum ){
rc = SQLITE_READONLY;
}else{
pBt->autoVacuum = av ?1:0;
pBt->incrVacuum = av==2 ?1:0;
}
sqlite3BtreeLeave(p);
return rc;
#endif
}
/*
** Return the value of the 'auto-vacuum' property. If auto-vacuum is
** enabled 1 is returned. Otherwise 0.
*/
int sqlite3BtreeGetAutoVacuum(Btree *p){
#ifdef SQLITE_OMIT_AUTOVACUUM
return BTREE_AUTOVACUUM_NONE;
#else
int rc;
sqlite3BtreeEnter(p);
rc = (
(!p->pBt->autoVacuum)?BTREE_AUTOVACUUM_NONE:
(!p->pBt->incrVacuum)?BTREE_AUTOVACUUM_FULL:
BTREE_AUTOVACUUM_INCR
);
sqlite3BtreeLeave(p);
return rc;
#endif
}
/*
** Get a reference to pPage1 of the database file. This will
** also acquire a readlock on that file.
**
** SQLITE_OK is returned on success. If the file is not a
** well-formed database file, then SQLITE_CORRUPT is returned.
** SQLITE_BUSY is returned if the database is locked. SQLITE_NOMEM
** is returned if we run out of memory.
*/
static int lockBtree(BtShared *pBt){
int rc; /* Result code from subfunctions */
MemPage *pPage1; /* Page 1 of the database file */
int nPage; /* Number of pages in the database */
int nPageFile = 0; /* Number of pages in the database file */
int nPageHeader; /* Number of pages in the database according to hdr */
assert( sqlite3_mutex_held(pBt->mutex) );
assert( pBt->pPage1==0 );
rc = sqlite3PagerSharedLock(pBt->pPager);
if( rc!=SQLITE_OK ) return rc;
rc = btreeGetPage(pBt, 1, &pPage1, 0);
if( rc!=SQLITE_OK ) return rc;
/* Do some checking to help insure the file we opened really is
** a valid database file.
*/
nPage = nPageHeader = get4byte(28+(u8*)pPage1->aData);
sqlite3PagerPagecount(pBt->pPager, &nPageFile);
if( nPage==0 || memcmp(24+(u8*)pPage1->aData, 92+(u8*)pPage1->aData,4)!=0 ){
nPage = nPageFile;
}
if( nPage>0 ){
u32 pageSize;
u32 usableSize;
u8 *page1 = pPage1->aData;
rc = SQLITE_NOTADB;
if( memcmp(page1, zMagicHeader, 16)!=0 ){
goto page1_init_failed;
}
#ifdef SQLITE_OMIT_WAL
if( page1[18]>1 ){
pBt->readOnly = 1;
}
if( page1[19]>1 ){
goto page1_init_failed;
}
#else
if( page1[18]>2 ){
pBt->readOnly = 1;
}
if( page1[19]>2 ){
goto page1_init_failed;
}
/* If the write version is set to 2, this database should be accessed
** in WAL mode. If the log is not already open, open it now. Then
** return SQLITE_OK and return without populating BtShared.pPage1.
** The caller detects this and calls this function again. This is
** required as the version of page 1 currently in the page1 buffer
** may not be the latest version - there may be a newer one in the log
** file.
*/
if( page1[19]==2 && pBt->doNotUseWAL==0 ){
int isOpen = 0;
rc = sqlite3PagerOpenWal(pBt->pPager, &isOpen);
if( rc!=SQLITE_OK ){
goto page1_init_failed;
}else if( isOpen==0 ){
releasePage(pPage1);
return SQLITE_OK;
}
rc = SQLITE_NOTADB;
}
#endif
/* The maximum embedded fraction must be exactly 25%. And the minimum
** embedded fraction must be 12.5% for both leaf-data and non-leaf-data.
** The original design allowed these amounts to vary, but as of
** version 3.6.0, we require them to be fixed.
*/
if( memcmp(&page1[21], "\100\040\040",3)!=0 ){
goto page1_init_failed;
}
pageSize = (page1[16]<<8) | (page1[17]<<16);
if( ((pageSize-1)&pageSize)!=0
|| pageSize>SQLITE_MAX_PAGE_SIZE
|| pageSize<=256
){
goto page1_init_failed;
}
assert( (pageSize & 7)==0 );
usableSize = pageSize - page1[20];
if( (u32)pageSize!=pBt->pageSize ){
/* After reading the first page of the database assuming a page size
** of BtShared.pageSize, we have discovered that the page-size is
** actually pageSize. Unlock the database, leave pBt->pPage1 at
** zero and return SQLITE_OK. The caller will call this function
** again with the correct page-size.
*/
releasePage(pPage1);
pBt->usableSize = usableSize;
pBt->pageSize = pageSize;
freeTempSpace(pBt);
rc = sqlite3PagerSetPagesize(pBt->pPager, &pBt->pageSize,
pageSize-usableSize);
return rc;
}
if( (pBt->db->flags & SQLITE_RecoveryMode)==0 && nPage>nPageFile ){
rc = SQLITE_CORRUPT_BKPT;
goto page1_init_failed;
}
if( usableSize<480 ){
goto page1_init_failed;
}
pBt->pageSize = pageSize;
pBt->usableSize = usableSize;
#ifndef SQLITE_OMIT_AUTOVACUUM
pBt->autoVacuum = (get4byte(&page1[36 + 4*4])?1:0);
pBt->incrVacuum = (get4byte(&page1[36 + 7*4])?1:0);
#endif
}
/* maxLocal is the maximum amount of payload to store locally for
** a cell. Make sure it is small enough so that at least minFanout
** cells can will fit on one page. We assume a 10-byte page header.
** Besides the payload, the cell must store:
** 2-byte pointer to the cell
** 4-byte child pointer
** 9-byte nKey value
** 4-byte nData value
** 4-byte overflow page pointer
** So a cell consists of a 2-byte pointer, a header which is as much as
** 17 bytes long, 0 to N bytes of payload, and an optional 4 byte overflow
** page pointer.
*/
pBt->maxLocal = (u16)((pBt->usableSize-12)*64/255 - 23);
pBt->minLocal = (u16)((pBt->usableSize-12)*32/255 - 23);
pBt->maxLeaf = (u16)(pBt->usableSize - 35);
pBt->minLeaf = (u16)((pBt->usableSize-12)*32/255 - 23);
assert( pBt->maxLeaf + 23 <= MX_CELL_SIZE(pBt) );
pBt->pPage1 = pPage1;
pBt->nPage = nPage;
return SQLITE_OK;
page1_init_failed:
releasePage(pPage1);
pBt->pPage1 = 0;
return rc;
}
/*
** If there are no outstanding cursors and we are not in the middle
** of a transaction but there is a read lock on the database, then
** this routine unrefs the first page of the database file which
** has the effect of releasing the read lock.
**
** If there is a transaction in progress, this routine is a no-op.
*/
static void unlockBtreeIfUnused(BtShared *pBt){
assert( sqlite3_mutex_held(pBt->mutex) );
assert( pBt->pCursor==0 || pBt->inTransaction>TRANS_NONE );
if( pBt->inTransaction==TRANS_NONE && pBt->pPage1!=0 ){
assert( pBt->pPage1->aData );
assert( sqlite3PagerRefcount(pBt->pPager)==1 );
assert( pBt->pPage1->aData );
releasePage(pBt->pPage1);
pBt->pPage1 = 0;
}
}
/*
** If pBt points to an empty file then convert that empty file
** into a new empty database by initializing the first page of
** the database.
*/
static int newDatabase(BtShared *pBt){
MemPage *pP1;
unsigned char *data;
int rc;
assert( sqlite3_mutex_held(pBt->mutex) );
if( pBt->nPage>0 ){
return SQLITE_OK;
}
pP1 = pBt->pPage1;
assert( pP1!=0 );
data = pP1->aData;
rc = sqlite3PagerWrite(pP1->pDbPage);
if( rc ) return rc;
memcpy(data, zMagicHeader, sizeof(zMagicHeader));
assert( sizeof(zMagicHeader)==16 );
data[16] = (u8)((pBt->pageSize>>8)&0xff);
data[17] = (u8)((pBt->pageSize>>16)&0xff);
data[18] = 1;
data[19] = 1;
assert( pBt->usableSize<=pBt->pageSize && pBt->usableSize+255>=pBt->pageSize);
data[20] = (u8)(pBt->pageSize - pBt->usableSize);
data[21] = 64;
data[22] = 32;
data[23] = 32;
memset(&data[24], 0, 100-24);
zeroPage(pP1, PTF_INTKEY|PTF_LEAF|PTF_LEAFDATA );
pBt->pageSizeFixed = 1;
#ifndef SQLITE_OMIT_AUTOVACUUM
assert( pBt->autoVacuum==1 || pBt->autoVacuum==0 );
assert( pBt->incrVacuum==1 || pBt->incrVacuum==0 );
put4byte(&data[36 + 4*4], pBt->autoVacuum);
put4byte(&data[36 + 7*4], pBt->incrVacuum);
#endif
pBt->nPage = 1;
data[31] = 1;
return SQLITE_OK;
}
/*
** Attempt to start a new transaction. A write-transaction
** is started if the second argument is nonzero, otherwise a read-
** transaction. If the second argument is 2 or more and exclusive
** transaction is started, meaning that no other process is allowed
** to access the database. A preexisting transaction may not be
** upgraded to exclusive by calling this routine a second time - the
** exclusivity flag only works for a new transaction.
**
** A write-transaction must be started before attempting any
** changes to the database. None of the following routines
** will work unless a transaction is started first:
**
** sqlite3BtreeCreateTable()
** sqlite3BtreeCreateIndex()
** sqlite3BtreeClearTable()
** sqlite3BtreeDropTable()
** sqlite3BtreeInsert()
** sqlite3BtreeDelete()
** sqlite3BtreeUpdateMeta()
**
** If an initial attempt to acquire the lock fails because of lock contention
** and the database was previously unlocked, then invoke the busy handler
** if there is one. But if there was previously a read-lock, do not
** invoke the busy handler - just return SQLITE_BUSY. SQLITE_BUSY is
** returned when there is already a read-lock in order to avoid a deadlock.
**
** Suppose there are two processes A and B. A has a read lock and B has
** a reserved lock. B tries to promote to exclusive but is blocked because
** of A's read lock. A tries to promote to reserved but is blocked by B.
** One or the other of the two processes must give way or there can be
** no progress. By returning SQLITE_BUSY and not invoking the busy callback
** when A already has a read lock, we encourage A to give up and let B
** proceed.
*/
int sqlite3BtreeBeginTrans(Btree *p, int wrflag){
sqlite3 *pBlock = 0;
BtShared *pBt = p->pBt;
int rc = SQLITE_OK;
sqlite3BtreeEnter(p);
btreeIntegrity(p);
/* If the btree is already in a write-transaction, or it
** is already in a read-transaction and a read-transaction
** is requested, this is a no-op.
*/
if( p->inTrans==TRANS_WRITE || (p->inTrans==TRANS_READ && !wrflag) ){
goto trans_begun;
}
/* Write transactions are not possible on a read-only database */
if( pBt->readOnly && wrflag ){
rc = SQLITE_READONLY;
goto trans_begun;
}
#ifndef SQLITE_OMIT_SHARED_CACHE
/* If another database handle has already opened a write transaction
** on this shared-btree structure and a second write transaction is
** requested, return SQLITE_LOCKED.
*/
if( (wrflag && pBt->inTransaction==TRANS_WRITE) || pBt->isPending ){
pBlock = pBt->pWriter->db;
}else if( wrflag>1 ){
BtLock *pIter;
for(pIter=pBt->pLock; pIter; pIter=pIter->pNext){
if( pIter->pBtree!=p ){
pBlock = pIter->pBtree->db;
break;
}
}
}
if( pBlock ){
sqlite3ConnectionBlocked(p->db, pBlock);
rc = SQLITE_LOCKED_SHAREDCACHE;
goto trans_begun;
}
#endif
/* Any read-only or read-write transaction implies a read-lock on
** page 1. So if some other shared-cache client already has a write-lock
** on page 1, the transaction cannot be opened. */
rc = querySharedCacheTableLock(p, MASTER_ROOT, READ_LOCK);
if( SQLITE_OK!=rc ) goto trans_begun;
pBt->initiallyEmpty = (u8)(pBt->nPage==0);
do {
/* Call lockBtree() until either pBt->pPage1 is populated or
** lockBtree() returns something other than SQLITE_OK. lockBtree()
** may return SQLITE_OK but leave pBt->pPage1 set to 0 if after
** reading page 1 it discovers that the page-size of the database
** file is not pBt->pageSize. In this case lockBtree() will update
** pBt->pageSize to the page-size of the file on disk.
*/
while( pBt->pPage1==0 && SQLITE_OK==(rc = lockBtree(pBt)) );
if( rc==SQLITE_OK && wrflag ){
if( pBt->readOnly ){
rc = SQLITE_READONLY;
}else{
rc = sqlite3PagerBegin(pBt->pPager,wrflag>1,sqlite3TempInMemory(p->db));
if( rc==SQLITE_OK ){
rc = newDatabase(pBt);
}
}
}
if( rc!=SQLITE_OK ){
unlockBtreeIfUnused(pBt);
}
}while( (rc&0xFF)==SQLITE_BUSY && pBt->inTransaction==TRANS_NONE &&
btreeInvokeBusyHandler(pBt) );
if( rc==SQLITE_OK ){
if( p->inTrans==TRANS_NONE ){
pBt->nTransaction++;
#ifndef SQLITE_OMIT_SHARED_CACHE
if( p->sharable ){
assert( p->lock.pBtree==p && p->lock.iTable==1 );
p->lock.eLock = READ_LOCK;
p->lock.pNext = pBt->pLock;
pBt->pLock = &p->lock;
}
#endif
}
p->inTrans = (wrflag?TRANS_WRITE:TRANS_READ);
if( p->inTrans>pBt->inTransaction ){
pBt->inTransaction = p->inTrans;
}
if( wrflag ){
MemPage *pPage1 = pBt->pPage1;
#ifndef SQLITE_OMIT_SHARED_CACHE
assert( !pBt->pWriter );
pBt->pWriter = p;
pBt->isExclusive = (u8)(wrflag>1);
#endif
/* If the db-size header field is incorrect (as it may be if an old
** client has been writing the database file), update it now. Doing
** this sooner rather than later means the database size can safely
** re-read the database size from page 1 if a savepoint or transaction
** rollback occurs within the transaction.
*/
if( pBt->nPage!=get4byte(&pPage1->aData[28]) ){
rc = sqlite3PagerWrite(pPage1->pDbPage);
if( rc==SQLITE_OK ){
put4byte(&pPage1->aData[28], pBt->nPage);
}
}
}
}
trans_begun:
if( rc==SQLITE_OK && wrflag ){
/* This call makes sure that the pager has the correct number of
** open savepoints. If the second parameter is greater than 0 and
** the sub-journal is not already open, then it will be opened here.
*/
rc = sqlite3PagerOpenSavepoint(pBt->pPager, p->db->nSavepoint);
}
btreeIntegrity(p);
sqlite3BtreeLeave(p);
return rc;
}
#ifndef SQLITE_OMIT_AUTOVACUUM
/*
** Set the pointer-map entries for all children of page pPage. Also, if
** pPage contains cells that point to overflow pages, set the pointer
** map entries for the overflow pages as well.
*/
static int setChildPtrmaps(MemPage *pPage){
int i; /* Counter variable */
int nCell; /* Number of cells in page pPage */
int rc; /* Return code */
BtShared *pBt = pPage->pBt;
u8 isInitOrig = pPage->isInit;
Pgno pgno = pPage->pgno;
assert( sqlite3_mutex_held(pPage->pBt->mutex) );
rc = btreeInitPage(pPage);
if( rc!=SQLITE_OK ){
goto set_child_ptrmaps_out;
}
nCell = pPage->nCell;
for(i=0; i<nCell; i++){
u8 *pCell = findCell(pPage, i);
ptrmapPutOvflPtr(pPage, pCell, &rc);
if( !pPage->leaf ){
Pgno childPgno = get4byte(pCell);
ptrmapPut(pBt, childPgno, PTRMAP_BTREE, pgno, &rc);
}
}
if( !pPage->leaf ){
Pgno childPgno = get4byte(&pPage->aData[pPage->hdrOffset+8]);
ptrmapPut(pBt, childPgno, PTRMAP_BTREE, pgno, &rc);
}
set_child_ptrmaps_out:
pPage->isInit = isInitOrig;
return rc;
}
/*
** Somewhere on pPage is a pointer to page iFrom. Modify this pointer so
** that it points to iTo. Parameter eType describes the type of pointer to
** be modified, as follows:
**
** PTRMAP_BTREE: pPage is a btree-page. The pointer points at a child
** page of pPage.
**
** PTRMAP_OVERFLOW1: pPage is a btree-page. The pointer points at an overflow
** page pointed to by one of the cells on pPage.
**
** PTRMAP_OVERFLOW2: pPage is an overflow-page. The pointer points at the next
** overflow page in the list.
*/
static int modifyPagePointer(MemPage *pPage, Pgno iFrom, Pgno iTo, u8 eType){
assert( sqlite3_mutex_held(pPage->pBt->mutex) );
assert( sqlite3PagerIswriteable(pPage->pDbPage) );
if( eType==PTRMAP_OVERFLOW2 ){
/* The pointer is always the first 4 bytes of the page in this case. */
if( get4byte(pPage->aData)!=iFrom ){
return SQLITE_CORRUPT_BKPT;
}
put4byte(pPage->aData, iTo);
}else{
u8 isInitOrig = pPage->isInit;
int i;
int nCell;
btreeInitPage(pPage);
nCell = pPage->nCell;
for(i=0; i<nCell; i++){
u8 *pCell = findCell(pPage, i);
if( eType==PTRMAP_OVERFLOW1 ){
CellInfo info;
btreeParseCellPtr(pPage, pCell, &info);
if( info.iOverflow ){
if( iFrom==get4byte(&pCell[info.iOverflow]) ){
put4byte(&pCell[info.iOverflow], iTo);
break;
}
}
}else{
if( get4byte(pCell)==iFrom ){
put4byte(pCell, iTo);
break;
}
}
}
if( i==nCell ){
if( eType!=PTRMAP_BTREE ||
get4byte(&pPage->aData[pPage->hdrOffset+8])!=iFrom ){
return SQLITE_CORRUPT_BKPT;
}
put4byte(&pPage->aData[pPage->hdrOffset+8], iTo);
}
pPage->isInit = isInitOrig;
}
return SQLITE_OK;
}
/*
** Move the open database page pDbPage to location iFreePage in the
** database. The pDbPage reference remains valid.
**
** The isCommit flag indicates that there is no need to remember that
** the journal needs to be sync()ed before database page pDbPage->pgno
** can be written to. The caller has already promised not to write to that
** page.
*/
static int relocatePage(
BtShared *pBt, /* Btree */
MemPage *pDbPage, /* Open page to move */
u8 eType, /* Pointer map 'type' entry for pDbPage */
Pgno iPtrPage, /* Pointer map 'page-no' entry for pDbPage */
Pgno iFreePage, /* The location to move pDbPage to */
int isCommit /* isCommit flag passed to sqlite3PagerMovepage */
){
MemPage *pPtrPage; /* The page that contains a pointer to pDbPage */
Pgno iDbPage = pDbPage->pgno;
Pager *pPager = pBt->pPager;
int rc;
assert( eType==PTRMAP_OVERFLOW2 || eType==PTRMAP_OVERFLOW1 ||
eType==PTRMAP_BTREE || eType==PTRMAP_ROOTPAGE );
assert( sqlite3_mutex_held(pBt->mutex) );
assert( pDbPage->pBt==pBt );
/* Move page iDbPage from its current location to page number iFreePage */
TRACE(("AUTOVACUUM: Moving %d to free page %d (ptr page %d type %d)\n",
iDbPage, iFreePage, iPtrPage, eType));
rc = sqlite3PagerMovepage(pPager, pDbPage->pDbPage, iFreePage, isCommit);
if( rc!=SQLITE_OK ){
return rc;
}
pDbPage->pgno = iFreePage;
/* If pDbPage was a btree-page, then it may have child pages and/or cells
** that point to overflow pages. The pointer map entries for all these
** pages need to be changed.
**
** If pDbPage is an overflow page, then the first 4 bytes may store a
** pointer to a subsequent overflow page. If this is the case, then
** the pointer map needs to be updated for the subsequent overflow page.
*/
if( eType==PTRMAP_BTREE || eType==PTRMAP_ROOTPAGE ){
rc = setChildPtrmaps(pDbPage);
if( rc!=SQLITE_OK ){
return rc;
}
}else{
Pgno nextOvfl = get4byte(pDbPage->aData);
if( nextOvfl!=0 ){
ptrmapPut(pBt, nextOvfl, PTRMAP_OVERFLOW2, iFreePage, &rc);
if( rc!=SQLITE_OK ){
return rc;
}
}
}
/* Fix the database pointer on page iPtrPage that pointed at iDbPage so
** that it points at iFreePage. Also fix the pointer map entry for
** iPtrPage.
*/
if( eType!=PTRMAP_ROOTPAGE ){
rc = btreeGetPage(pBt, iPtrPage, &pPtrPage, 0);
if( rc!=SQLITE_OK ){
return rc;
}
rc = sqlite3PagerWrite(pPtrPage->pDbPage);
if( rc!=SQLITE_OK ){
releasePage(pPtrPage);
return rc;
}
rc = modifyPagePointer(pPtrPage, iDbPage, iFreePage, eType);
releasePage(pPtrPage);
if( rc==SQLITE_OK ){
ptrmapPut(pBt, iFreePage, eType, iPtrPage, &rc);
}
}
return rc;
}
/* Forward declaration required by incrVacuumStep(). */
static int allocateBtreePage(BtShared *, MemPage **, Pgno *, Pgno, u8);
/*
** Perform a single step of an incremental-vacuum. If successful,
** return SQLITE_OK. If there is no work to do (and therefore no
** point in calling this function again), return SQLITE_DONE.
**
** More specificly, this function attempts to re-organize the
** database so that the last page of the file currently in use
** is no longer in use.
**
** If the nFin parameter is non-zero, this function assumes
** that the caller will keep calling incrVacuumStep() until
** it returns SQLITE_DONE or an error, and that nFin is the
** number of pages the database file will contain after this
** process is complete. If nFin is zero, it is assumed that
** incrVacuumStep() will be called a finite amount of times
** which may or may not empty the freelist. A full autovacuum
** has nFin>0. A "PRAGMA incremental_vacuum" has nFin==0.
*/
static int incrVacuumStep(BtShared *pBt, Pgno nFin, Pgno iLastPg){
Pgno nFreeList; /* Number of pages still on the free-list */
int rc;
assert( sqlite3_mutex_held(pBt->mutex) );
assert( iLastPg>nFin );
if( !PTRMAP_ISPAGE(pBt, iLastPg) && iLastPg!=PENDING_BYTE_PAGE(pBt) ){
u8 eType;
Pgno iPtrPage;
nFreeList = get4byte(&pBt->pPage1->aData[36]);
if( nFreeList==0 ){
return SQLITE_DONE;
}
rc = ptrmapGet(pBt, iLastPg, &eType, &iPtrPage);
if( rc!=SQLITE_OK ){
return rc;
}
if( eType==PTRMAP_ROOTPAGE ){
return SQLITE_CORRUPT_BKPT;
}
if( eType==PTRMAP_FREEPAGE ){
if( nFin==0 ){
/* Remove the page from the files free-list. This is not required
** if nFin is non-zero. In that case, the free-list will be
** truncated to zero after this function returns, so it doesn't
** matter if it still contains some garbage entries.
*/
Pgno iFreePg;
MemPage *pFreePg;
rc = allocateBtreePage(pBt, &pFreePg, &iFreePg, iLastPg, 1);
if( rc!=SQLITE_OK ){
return rc;
}
assert( iFreePg==iLastPg );
releasePage(pFreePg);
}
} else {
Pgno iFreePg; /* Index of free page to move pLastPg to */
MemPage *pLastPg;
rc = btreeGetPage(pBt, iLastPg, &pLastPg, 0);
if( rc!=SQLITE_OK ){
return rc;
}
/* If nFin is zero, this loop runs exactly once and page pLastPg
** is swapped with the first free page pulled off the free list.
**
** On the other hand, if nFin is greater than zero, then keep
** looping until a free-page located within the first nFin pages
** of the file is found.
*/
do {
MemPage *pFreePg;
rc = allocateBtreePage(pBt, &pFreePg, &iFreePg, 0, 0);
if( rc!=SQLITE_OK ){
releasePage(pLastPg);
return rc;
}
releasePage(pFreePg);
}while( nFin!=0 && iFreePg>nFin );
assert( iFreePg<iLastPg );
rc = sqlite3PagerWrite(pLastPg->pDbPage);
if( rc==SQLITE_OK ){
rc = relocatePage(pBt, pLastPg, eType, iPtrPage, iFreePg, nFin!=0);
}
releasePage(pLastPg);
if( rc!=SQLITE_OK ){
return rc;
}
}
}
if( nFin==0 ){
iLastPg--;
while( iLastPg==PENDING_BYTE_PAGE(pBt)||PTRMAP_ISPAGE(pBt, iLastPg) ){
if( PTRMAP_ISPAGE(pBt, iLastPg) ){
MemPage *pPg;
rc = btreeGetPage(pBt, iLastPg, &pPg, 0);
if( rc!=SQLITE_OK ){
return rc;
}
rc = sqlite3PagerWrite(pPg->pDbPage);
releasePage(pPg);
if( rc!=SQLITE_OK ){
return rc;
}
}
iLastPg--;
}
sqlite3PagerTruncateImage(pBt->pPager, iLastPg);
pBt->nPage = iLastPg;
}
return SQLITE_OK;
}
/*
** A write-transaction must be opened before calling this function.
** It performs a single unit of work towards an incremental vacuum.
**
** If the incremental vacuum is finished after this function has run,
** SQLITE_DONE is returned. If it is not finished, but no error occurred,
** SQLITE_OK is returned. Otherwise an SQLite error code.
*/
int sqlite3BtreeIncrVacuum(Btree *p){
int rc;
BtShared *pBt = p->pBt;
sqlite3BtreeEnter(p);
assert( pBt->inTransaction==TRANS_WRITE && p->inTrans==TRANS_WRITE );
if( !pBt->autoVacuum ){
rc = SQLITE_DONE;
}else{
invalidateAllOverflowCache(pBt);
rc = incrVacuumStep(pBt, 0, btreePagecount(pBt));
if( rc==SQLITE_OK ){
rc = sqlite3PagerWrite(pBt->pPage1->pDbPage);
put4byte(&pBt->pPage1->aData[28], pBt->nPage);
}
}
sqlite3BtreeLeave(p);
return rc;
}
/*
** This routine is called prior to sqlite3PagerCommit when a transaction
** is commited for an auto-vacuum database.
**
** If SQLITE_OK is returned, then *pnTrunc is set to the number of pages
** the database file should be truncated to during the commit process.
** i.e. the database has been reorganized so that only the first *pnTrunc
** pages are in use.
*/
static int autoVacuumCommit(BtShared *pBt){
int rc = SQLITE_OK;
Pager *pPager = pBt->pPager;
VVA_ONLY( int nRef = sqlite3PagerRefcount(pPager) );
assert( sqlite3_mutex_held(pBt->mutex) );
invalidateAllOverflowCache(pBt);
assert(pBt->autoVacuum);
if( !pBt->incrVacuum ){
Pgno nFin; /* Number of pages in database after autovacuuming */
Pgno nFree; /* Number of pages on the freelist initially */
Pgno nPtrmap; /* Number of PtrMap pages to be freed */
Pgno iFree; /* The next page to be freed */
int nEntry; /* Number of entries on one ptrmap page */
Pgno nOrig; /* Database size before freeing */
nOrig = btreePagecount(pBt);
if( PTRMAP_ISPAGE(pBt, nOrig) || nOrig==PENDING_BYTE_PAGE(pBt) ){
/* It is not possible to create a database for which the final page
** is either a pointer-map page or the pending-byte page. If one
** is encountered, this indicates corruption.
*/
return SQLITE_CORRUPT_BKPT;
}
nFree = get4byte(&pBt->pPage1->aData[36]);
nEntry = pBt->usableSize/5;
nPtrmap = (nFree-nOrig+PTRMAP_PAGENO(pBt, nOrig)+nEntry)/nEntry;
nFin = nOrig - nFree - nPtrmap;
if( nOrig>PENDING_BYTE_PAGE(pBt) && nFin<PENDING_BYTE_PAGE(pBt) ){
nFin--;
}
while( PTRMAP_ISPAGE(pBt, nFin) || nFin==PENDING_BYTE_PAGE(pBt) ){
nFin--;
}
if( nFin>nOrig ) return SQLITE_CORRUPT_BKPT;
for(iFree=nOrig; iFree>nFin && rc==SQLITE_OK; iFree--){
rc = incrVacuumStep(pBt, nFin, iFree);
}
if( (rc==SQLITE_DONE || rc==SQLITE_OK) && nFree>0 ){
rc = sqlite3PagerWrite(pBt->pPage1->