AryaWu/sqlite
0
1/*2** 2004 April 63**4** The author disclaims copyright to this source code. In place of5** a legal notice, here is a blessing:6**7** May you do good and not evil.8** May you find forgiveness for yourself and forgive others.9** May you share freely, never taking more than you give.10**11*************************************************************************12** This file implements an external (disk-based) database using BTrees.13** See the header comment on "btreeInt.h" for additional information.14** Including a description of file format and an overview of operation.15*/16#include "btreeInt.h"17 18/*19** The header string that appears at the beginning of every20** SQLite database.21*/22static const char zMagicHeader[] = SQLITE_FILE_HEADER;23 24/*25** Set this global variable to 1 to enable tracing using the TRACE26** macro.27*/28#if 029int sqlite3BtreeTrace=1; /* True to enable tracing */30# define TRACE(X) if(sqlite3BtreeTrace){printf X;fflush(stdout);}31#else32# define TRACE(X)33#endif34 35/*36** Extract a 2-byte big-endian integer from an array of unsigned bytes.37** But if the value is zero, make it 65536.38**39** This routine is used to extract the "offset to cell content area" value40** from the header of a btree page. If the page size is 65536 and the page41** is empty, the offset should be 65536, but the 2-byte value stores zero.42** This routine makes the necessary adjustment to 65536.43*/44#define get2byteNotZero(X) (((((int)get2byte(X))-1)&0xffff)+1)45 46/*47** Values passed as the 5th argument to allocateBtreePage()48*/49#define BTALLOC_ANY 0 /* Allocate any page */50#define BTALLOC_EXACT 1 /* Allocate exact page if possible */51#define BTALLOC_LE 2 /* Allocate any page <= the parameter */52 53/*54** Macro IfNotOmitAV(x) returns (x) if SQLITE_OMIT_AUTOVACUUM is not55** defined, or 0 if it is. For example:56**57** bIncrVacuum = IfNotOmitAV(pBtShared->incrVacuum);58*/59#ifndef SQLITE_OMIT_AUTOVACUUM60#define IfNotOmitAV(expr) (expr)61#else62#define IfNotOmitAV(expr) 063#endif64 65#ifndef SQLITE_OMIT_SHARED_CACHE66/*67** A list of BtShared objects that are eligible for participation68** in shared cache. This variable has file scope during normal builds,69** but the test harness needs to access it so we make it global for70** test builds.71**72** Access to this variable is protected by SQLITE_MUTEX_STATIC_MAIN.73*/74#ifdef SQLITE_TEST75BtShared *SQLITE_WSD sqlite3SharedCacheList = 0;76#else77static BtShared *SQLITE_WSD sqlite3SharedCacheList = 0;78#endif79#endif /* SQLITE_OMIT_SHARED_CACHE */80 81#ifndef SQLITE_OMIT_SHARED_CACHE82/*83** Enable or disable the shared pager and schema features.84**85** This routine has no effect on existing database connections.86** The shared cache setting effects only future calls to87** sqlite3_open(), sqlite3_open16(), or sqlite3_open_v2().88*/89int sqlite3_enable_shared_cache(int enable){90 sqlite3GlobalConfig.sharedCacheEnabled = enable;91 return SQLITE_OK;92}93#endif94 95 96 97#ifdef SQLITE_OMIT_SHARED_CACHE98 /*99 ** The functions querySharedCacheTableLock(), setSharedCacheTableLock(),100 ** and clearAllSharedCacheTableLocks()101 ** manipulate entries in the BtShared.pLock linked list used to store102 ** shared-cache table level locks. If the library is compiled with the103 ** shared-cache feature disabled, then there is only ever one user104 ** of each BtShared structure and so this locking is not necessary.105 ** So define the lock related functions as no-ops.106 */107 #define querySharedCacheTableLock(a,b,c) SQLITE_OK108 #define setSharedCacheTableLock(a,b,c) SQLITE_OK109 #define clearAllSharedCacheTableLocks(a)110 #define downgradeAllSharedCacheTableLocks(a)111 #define hasSharedCacheTableLock(a,b,c,d) 1112 #define hasReadConflicts(a, b) 0113#endif114 115#ifdef SQLITE_DEBUG116/*117** Return and reset the seek counter for a Btree object.118*/119sqlite3_uint64 sqlite3BtreeSeekCount(Btree *pBt){120 u64 n = pBt->nSeek;121 pBt->nSeek = 0;122 return n;123}124#endif125 126/*127** Implementation of the SQLITE_CORRUPT_PAGE() macro. Takes a single128** (MemPage*) as an argument. The (MemPage*) must not be NULL.129**130** If SQLITE_DEBUG is not defined, then this macro is equivalent to131** SQLITE_CORRUPT_BKPT. Or, if SQLITE_DEBUG is set, then the log message132** normally produced as a side-effect of SQLITE_CORRUPT_BKPT is augmented133** with the page number and filename associated with the (MemPage*).134*/135#ifdef SQLITE_DEBUG136int corruptPageError(int lineno, MemPage *p){137 char *zMsg;138 sqlite3BeginBenignMalloc();139 zMsg = sqlite3_mprintf("database corruption page %u of %s",140 p->pgno, sqlite3PagerFilename(p->pBt->pPager, 0)141 );142 sqlite3EndBenignMalloc();143 if( zMsg ){144 sqlite3ReportError(SQLITE_CORRUPT, lineno, zMsg);145 }146 sqlite3_free(zMsg);147 return SQLITE_CORRUPT_BKPT;148}149# define SQLITE_CORRUPT_PAGE(pMemPage) corruptPageError(__LINE__, pMemPage)150#else151# define SQLITE_CORRUPT_PAGE(pMemPage) SQLITE_CORRUPT_PGNO(pMemPage->pgno)152#endif153 154/* Default value for SHARED_LOCK_TRACE macro if shared-cache is disabled155** or if the lock tracking is disabled. This is always the value for156** release builds.157*/158#define SHARED_LOCK_TRACE(X,MSG,TAB,TYPE) /*no-op*/159 160#ifndef SQLITE_OMIT_SHARED_CACHE161 162#if 0163/* ^---- Change to 1 and recompile to enable shared-lock tracing164** for debugging purposes.165**166** Print all shared-cache locks on a BtShared. Debugging use only.167*/168static void sharedLockTrace(169 BtShared *pBt,170 const char *zMsg,171 int iRoot,172 int eLockType173){174 BtLock *pLock;175 if( iRoot>0 ){176 printf("%s-%p %u%s:", zMsg, pBt, iRoot, eLockType==READ_LOCK?"R":"W");177 }else{178 printf("%s-%p:", zMsg, pBt);179 }180 for(pLock=pBt->pLock; pLock; pLock=pLock->pNext){181 printf(" %p/%u%s", pLock->pBtree, pLock->iTable,182 pLock->eLock==READ_LOCK ? "R" : "W");183 while( pLock->pNext && pLock->pBtree==pLock->pNext->pBtree ){184 pLock = pLock->pNext;185 printf(",%u%s", pLock->iTable, pLock->eLock==READ_LOCK ? "R" : "W");186 }187 }188 printf("\n");189 fflush(stdout);190}191#undef SHARED_LOCK_TRACE192#define SHARED_LOCK_TRACE(X,MSG,TAB,TYPE) sharedLockTrace(X,MSG,TAB,TYPE)193#endif /* Shared-lock tracing */194 195#ifdef SQLITE_DEBUG196/*197**** This function is only used as part of an assert() statement. ***198**199** Check to see if pBtree holds the required locks to read or write to the200** table with root page iRoot. Return 1 if it does and 0 if not.201**202** For example, when writing to a table with root-page iRoot via203** Btree connection pBtree:204**205** assert( hasSharedCacheTableLock(pBtree, iRoot, 0, WRITE_LOCK) );206**207** When writing to an index that resides in a sharable database, the208** caller should have first obtained a lock specifying the root page of209** the corresponding table. This makes things a bit more complicated,210** as this module treats each table as a separate structure. To determine211** the table corresponding to the index being written, this212** function has to search through the database schema.213**214** Instead of a lock on the table/index rooted at page iRoot, the caller may215** hold a write-lock on the schema table (root page 1). This is also216** acceptable.217*/218static int hasSharedCacheTableLock(219 Btree *pBtree, /* Handle that must hold lock */220 Pgno iRoot, /* Root page of b-tree */221 int isIndex, /* True if iRoot is the root of an index b-tree */222 int eLockType /* Required lock type (READ_LOCK or WRITE_LOCK) */223){224 Schema *pSchema = (Schema *)pBtree->pBt->pSchema;225 Pgno iTab = 0;226 BtLock *pLock;227 228 /* If this database is not shareable, or if the client is reading229 ** and has the read-uncommitted flag set, then no lock is required.230 ** Return true immediately.231 */232 if( (pBtree->sharable==0)233 || (eLockType==READ_LOCK && (pBtree->db->flags & SQLITE_ReadUncommit))234 ){235 return 1;236 }237 238 /* If the client is reading or writing an index and the schema is239 ** not loaded, then it is too difficult to actually check to see if240 ** the correct locks are held. So do not bother - just return true.241 ** This case does not come up very often anyhow.242 */243 if( isIndex && (!pSchema || (pSchema->schemaFlags&DB_SchemaLoaded)==0) ){244 return 1;245 }246 247 /* Figure out the root-page that the lock should be held on. For table248 ** b-trees, this is just the root page of the b-tree being read or249 ** written. For index b-trees, it is the root page of the associated250 ** table. */251 if( isIndex ){252 HashElem *p;253 int bSeen = 0;254 for(p=sqliteHashFirst(&pSchema->idxHash); p; p=sqliteHashNext(p)){255 Index *pIdx = (Index *)sqliteHashData(p);256 if( pIdx->tnum==iRoot ){257 if( bSeen ){258 /* Two or more indexes share the same root page. There must259 ** be imposter tables. So just return true. The assert is not260 ** useful in that case. */261 return 1;262 }263 iTab = pIdx->pTable->tnum;264 bSeen = 1;265 }266 }267 }else{268 iTab = iRoot;269 }270 271 SHARED_LOCK_TRACE(pBtree->pBt,"hasLock",iRoot,eLockType);272 273 /* Search for the required lock. Either a write-lock on root-page iTab, a274 ** write-lock on the schema table, or (if the client is reading) a275 ** read-lock on iTab will suffice. Return 1 if any of these are found. */276 for(pLock=pBtree->pBt->pLock; pLock; pLock=pLock->pNext){277 if( pLock->pBtree==pBtree278 && (pLock->iTable==iTab || (pLock->eLock==WRITE_LOCK && pLock->iTable==1))279 && pLock->eLock>=eLockType280 ){281 return 1;282 }283 }284 285 /* Failed to find the required lock. */286 return 0;287}288#endif /* SQLITE_DEBUG */289 290#ifdef SQLITE_DEBUG291/*292**** This function may be used as part of assert() statements only. ****293**294** Return true if it would be illegal for pBtree to write into the295** table or index rooted at iRoot because other shared connections are296** simultaneously reading that same table or index.297**298** It is illegal for pBtree to write if some other Btree object that299** shares the same BtShared object is currently reading or writing300** the iRoot table. Except, if the other Btree object has the301** read-uncommitted flag set, then it is OK for the other object to302** have a read cursor.303**304** For example, before writing to any part of the table or index305** rooted at page iRoot, one should call:306**307** assert( !hasReadConflicts(pBtree, iRoot) );308*/309static int hasReadConflicts(Btree *pBtree, Pgno iRoot){310 BtCursor *p;311 for(p=pBtree->pBt->pCursor; p; p=p->pNext){312 if( p->pgnoRoot==iRoot313 && p->pBtree!=pBtree314 && 0==(p->pBtree->db->flags & SQLITE_ReadUncommit)315 ){316 return 1;317 }318 }319 return 0;320}321#endif /* #ifdef SQLITE_DEBUG */322 323/*324** Query to see if Btree handle p may obtain a lock of type eLock325** (READ_LOCK or WRITE_LOCK) on the table with root-page iTab. Return326** SQLITE_OK if the lock may be obtained (by calling327** setSharedCacheTableLock()), or SQLITE_LOCKED if not.328*/329static int querySharedCacheTableLock(Btree *p, Pgno iTab, u8 eLock){330 BtShared *pBt = p->pBt;331 BtLock *pIter;332 333 assert( sqlite3BtreeHoldsMutex(p) );334 assert( eLock==READ_LOCK || eLock==WRITE_LOCK );335 assert( p->db!=0 );336 assert( !(p->db->flags&SQLITE_ReadUncommit)||eLock==WRITE_LOCK||iTab==1 );337 338 /* If requesting a write-lock, then the Btree must have an open write339 ** transaction on this file. And, obviously, for this to be so there340 ** must be an open write transaction on the file itself.341 */342 assert( eLock==READ_LOCK || (p==pBt->pWriter && p->inTrans==TRANS_WRITE) );343 assert( eLock==READ_LOCK || pBt->inTransaction==TRANS_WRITE );344 345 /* This routine is a no-op if the shared-cache is not enabled */346 if( !p->sharable ){347 return SQLITE_OK;348 }349 350 /* If some other connection is holding an exclusive lock, the351 ** requested lock may not be obtained.352 */353 if( pBt->pWriter!=p && (pBt->btsFlags & BTS_EXCLUSIVE)!=0 ){354 sqlite3ConnectionBlocked(p->db, pBt->pWriter->db);355 return SQLITE_LOCKED_SHAREDCACHE;356 }357 358 for(pIter=pBt->pLock; pIter; pIter=pIter->pNext){359 /* The condition (pIter->eLock!=eLock) in the following if(...)360 ** statement is a simplification of:361 **362 ** (eLock==WRITE_LOCK || pIter->eLock==WRITE_LOCK)363 **364 ** since we know that if eLock==WRITE_LOCK, then no other connection365 ** may hold a WRITE_LOCK on any table in this file (since there can366 ** only be a single writer).367 */368 assert( pIter->eLock==READ_LOCK || pIter->eLock==WRITE_LOCK );369 assert( eLock==READ_LOCK || pIter->pBtree==p || pIter->eLock==READ_LOCK);370 if( pIter->pBtree!=p && pIter->iTable==iTab && pIter->eLock!=eLock ){371 sqlite3ConnectionBlocked(p->db, pIter->pBtree->db);372 if( eLock==WRITE_LOCK ){373 assert( p==pBt->pWriter );374 pBt->btsFlags |= BTS_PENDING;375 }376 return SQLITE_LOCKED_SHAREDCACHE;377 }378 }379 return SQLITE_OK;380}381#endif /* !SQLITE_OMIT_SHARED_CACHE */382 383#ifndef SQLITE_OMIT_SHARED_CACHE384/*385** Add a lock on the table with root-page iTable to the shared-btree used386** by Btree handle p. Parameter eLock must be either READ_LOCK or387** WRITE_LOCK.388**389** This function assumes the following:390**391** (a) The specified Btree object p is connected to a sharable392** database (one with the BtShared.sharable flag set), and393**394** (b) No other Btree objects hold a lock that conflicts395** with the requested lock (i.e. querySharedCacheTableLock() has396** already been called and returned SQLITE_OK).397**398** SQLITE_OK is returned if the lock is added successfully. SQLITE_NOMEM399** is returned if a malloc attempt fails.400*/401static int setSharedCacheTableLock(Btree *p, Pgno iTable, u8 eLock){402 BtShared *pBt = p->pBt;403 BtLock *pLock = 0;404 BtLock *pIter;405 406 SHARED_LOCK_TRACE(pBt,"setLock", iTable, eLock);407 408 assert( sqlite3BtreeHoldsMutex(p) );409 assert( eLock==READ_LOCK || eLock==WRITE_LOCK );410 assert( p->db!=0 );411 412 /* A connection with the read-uncommitted flag set will never try to413 ** obtain a read-lock using this function. The only read-lock obtained414 ** by a connection in read-uncommitted mode is on the sqlite_schema415 ** table, and that lock is obtained in BtreeBeginTrans(). */416 assert( 0==(p->db->flags&SQLITE_ReadUncommit) || eLock==WRITE_LOCK );417 418 /* This function should only be called on a sharable b-tree after it419 ** has been determined that no other b-tree holds a conflicting lock. */420 assert( p->sharable );421 assert( SQLITE_OK==querySharedCacheTableLock(p, iTable, eLock) );422 423 /* First search the list for an existing lock on this table. */424 for(pIter=pBt->pLock; pIter; pIter=pIter->pNext){425 if( pIter->iTable==iTable && pIter->pBtree==p ){426 pLock = pIter;427 break;428 }429 }430 431 /* If the above search did not find a BtLock struct associating Btree p432 ** with table iTable, allocate one and link it into the list.433 */434 if( !pLock ){435 pLock = (BtLock *)sqlite3MallocZero(sizeof(BtLock));436 if( !pLock ){437 return SQLITE_NOMEM_BKPT;438 }439 pLock->iTable = iTable;440 pLock->pBtree = p;441 pLock->pNext = pBt->pLock;442 pBt->pLock = pLock;443 }444 445 /* Set the BtLock.eLock variable to the maximum of the current lock446 ** and the requested lock. This means if a write-lock was already held447 ** and a read-lock requested, we don't incorrectly downgrade the lock.448 */449 assert( WRITE_LOCK>READ_LOCK );450 if( eLock>pLock->eLock ){451 pLock->eLock = eLock;452 }453 454 return SQLITE_OK;455}456#endif /* !SQLITE_OMIT_SHARED_CACHE */457 458#ifndef SQLITE_OMIT_SHARED_CACHE459/*460** Release all the table locks (locks obtained via calls to461** the setSharedCacheTableLock() procedure) held by Btree object p.462**463** This function assumes that Btree p has an open read or write464** transaction. If it does not, then the BTS_PENDING flag465** may be incorrectly cleared.466*/467static void clearAllSharedCacheTableLocks(Btree *p){468 BtShared *pBt = p->pBt;469 BtLock **ppIter = &pBt->pLock;470 471 assert( sqlite3BtreeHoldsMutex(p) );472 assert( p->sharable || 0==*ppIter );473 assert( p->inTrans>0 );474 475 SHARED_LOCK_TRACE(pBt, "clearAllLocks", 0, 0);476 477 while( *ppIter ){478 BtLock *pLock = *ppIter;479 assert( (pBt->btsFlags & BTS_EXCLUSIVE)==0 || pBt->pWriter==pLock->pBtree );480 assert( pLock->pBtree->inTrans>=pLock->eLock );481 if( pLock->pBtree==p ){482 *ppIter = pLock->pNext;483 assert( pLock->iTable!=1 || pLock==&p->lock );484 if( pLock->iTable!=1 ){485 sqlite3_free(pLock);486 }487 }else{488 ppIter = &pLock->pNext;489 }490 }491 492 assert( (pBt->btsFlags & BTS_PENDING)==0 || pBt->pWriter );493 if( pBt->pWriter==p ){494 pBt->pWriter = 0;495 pBt->btsFlags &= ~(BTS_EXCLUSIVE|BTS_PENDING);496 }else if( pBt->nTransaction==2 ){497 /* This function is called when Btree p is concluding its498 ** transaction. If there currently exists a writer, and p is not499 ** that writer, then the number of locks held by connections other500 ** than the writer must be about to drop to zero. In this case501 ** set the BTS_PENDING flag to 0.502 **503 ** If there is not currently a writer, then BTS_PENDING must504 ** be zero already. So this next line is harmless in that case.505 */506 pBt->btsFlags &= ~BTS_PENDING;507 }508}509 510/*511** This function changes all write-locks held by Btree p into read-locks.512*/513static void downgradeAllSharedCacheTableLocks(Btree *p){514 BtShared *pBt = p->pBt;515 516 SHARED_LOCK_TRACE(pBt, "downgradeLocks", 0, 0);517 518 if( pBt->pWriter==p ){519 BtLock *pLock;520 pBt->pWriter = 0;521 pBt->btsFlags &= ~(BTS_EXCLUSIVE|BTS_PENDING);522 for(pLock=pBt->pLock; pLock; pLock=pLock->pNext){523 assert( pLock->eLock==READ_LOCK || pLock->pBtree==p );524 pLock->eLock = READ_LOCK;525 }526 }527}528 529#endif /* SQLITE_OMIT_SHARED_CACHE */530 531static void releasePage(MemPage *pPage); /* Forward reference */532static void releasePageOne(MemPage *pPage); /* Forward reference */533static void releasePageNotNull(MemPage *pPage); /* Forward reference */534 535/*536***** This routine is used inside of assert() only ****537**538** Verify that the cursor holds the mutex on its BtShared539*/540#ifdef SQLITE_DEBUG541static int cursorHoldsMutex(BtCursor *p){542 return sqlite3_mutex_held(p->pBt->mutex);543}544 545/* Verify that the cursor and the BtShared agree about what is the current546** database connetion. This is important in shared-cache mode. If the database547** connection pointers get out-of-sync, it is possible for routines like548** btreeInitPage() to reference an stale connection pointer that references a549** a connection that has already closed. This routine is used inside assert()550** statements only and for the purpose of double-checking that the btree code551** does keep the database connection pointers up-to-date.552*/553static int cursorOwnsBtShared(BtCursor *p){554 assert( cursorHoldsMutex(p) );555 return (p->pBtree->db==p->pBt->db);556}557#endif558 559/*560** Invalidate the overflow cache of the cursor passed as the first argument.561** on the shared btree structure pBt.562*/563#define invalidateOverflowCache(pCur) (pCur->curFlags &= ~BTCF_ValidOvfl)564 565/*566** Invalidate the overflow page-list cache for all cursors opened567** on the shared btree structure pBt.568*/569static void invalidateAllOverflowCache(BtShared *pBt){570 BtCursor *p;571 assert( sqlite3_mutex_held(pBt->mutex) );572 for(p=pBt->pCursor; p; p=p->pNext){573 invalidateOverflowCache(p);574 }575}576 577#ifndef SQLITE_OMIT_INCRBLOB578/*579** This function is called before modifying the contents of a table580** to invalidate any incrblob cursors that are open on the581** row or one of the rows being modified.582**583** If argument isClearTable is true, then the entire contents of the584** table is about to be deleted. In this case invalidate all incrblob585** cursors open on any row within the table with root-page pgnoRoot.586**587** Otherwise, if argument isClearTable is false, then the row with588** rowid iRow is being replaced or deleted. In this case invalidate589** only those incrblob cursors open on that specific row.590*/591static void invalidateIncrblobCursors(592 Btree *pBtree, /* The database file to check */593 Pgno pgnoRoot, /* The table that might be changing */594 i64 iRow, /* The rowid that might be changing */595 int isClearTable /* True if all rows are being deleted */596){597 BtCursor *p;598 assert( pBtree->hasIncrblobCur );599 assert( sqlite3BtreeHoldsMutex(pBtree) );600 pBtree->hasIncrblobCur = 0;601 for(p=pBtree->pBt->pCursor; p; p=p->pNext){602 if( (p->curFlags & BTCF_Incrblob)!=0 ){603 pBtree->hasIncrblobCur = 1;604 if( p->pgnoRoot==pgnoRoot && (isClearTable || p->info.nKey==iRow) ){605 p->eState = CURSOR_INVALID;606 }607 }608 }609}610 611#else612 /* Stub function when INCRBLOB is omitted */613 #define invalidateIncrblobCursors(w,x,y,z)614#endif /* SQLITE_OMIT_INCRBLOB */615 616/*617** Set bit pgno of the BtShared.pHasContent bitvec. This is called618** when a page that previously contained data becomes a free-list leaf619** page.620**621** The BtShared.pHasContent bitvec exists to work around an obscure622** bug caused by the interaction of two useful IO optimizations surrounding623** free-list leaf pages:624**625** 1) When all data is deleted from a page and the page becomes626** a free-list leaf page, the page is not written to the database627** (as free-list leaf pages contain no meaningful data). Sometimes628** such a page is not even journalled (as it will not be modified,629** why bother journalling it?).630**631** 2) When a free-list leaf page is reused, its content is not read632** from the database or written to the journal file (why should it633** be, if it is not at all meaningful?).634**635** By themselves, these optimizations work fine and provide a handy636** performance boost to bulk delete or insert operations. However, if637** a page is moved to the free-list and then reused within the same638** transaction, a problem comes up. If the page is not journalled when639** it is moved to the free-list and it is also not journalled when it640** is extracted from the free-list and reused, then the original data641** may be lost. In the event of a rollback, it may not be possible642** to restore the database to its original configuration.643**644** The solution is the BtShared.pHasContent bitvec. Whenever a page is645** moved to become a free-list leaf page, the corresponding bit is646** set in the bitvec. Whenever a leaf page is extracted from the free-list,647** optimization 2 above is omitted if the corresponding bit is already648** set in BtShared.pHasContent. The contents of the bitvec are cleared649** at the end of every transaction.650*/651static int btreeSetHasContent(BtShared *pBt, Pgno pgno){652 int rc = SQLITE_OK;653 if( !pBt->pHasContent ){654 assert( pgno<=pBt->nPage );655 pBt->pHasContent = sqlite3BitvecCreate(pBt->nPage);656 if( !pBt->pHasContent ){657 rc = SQLITE_NOMEM_BKPT;658 }659 }660 if( rc==SQLITE_OK && pgno<=sqlite3BitvecSize(pBt->pHasContent) ){661 rc = sqlite3BitvecSet(pBt->pHasContent, pgno);662 }663 return rc;664}665 666/*667** Query the BtShared.pHasContent vector.668**669** This function is called when a free-list leaf page is removed from the670** free-list for reuse. It returns false if it is safe to retrieve the671** page from the pager layer with the 'no-content' flag set. True otherwise.672*/673static int btreeGetHasContent(BtShared *pBt, Pgno pgno){674 Bitvec *p = pBt->pHasContent;675 return p && (pgno>sqlite3BitvecSize(p) || sqlite3BitvecTestNotNull(p, pgno));676}677 678/*679** Clear (destroy) the BtShared.pHasContent bitvec. This should be680** invoked at the conclusion of each write-transaction.681*/682static void btreeClearHasContent(BtShared *pBt){683 sqlite3BitvecDestroy(pBt->pHasContent);684 pBt->pHasContent = 0;685}686 687/*688** Release all of the apPage[] pages for a cursor.689*/690static void btreeReleaseAllCursorPages(BtCursor *pCur){691 int i;692 if( pCur->iPage>=0 ){693 for(i=0; i<pCur->iPage; i++){694 releasePageNotNull(pCur->apPage[i]);695 }696 releasePageNotNull(pCur->pPage);697 pCur->iPage = -1;698 }699}700 701/*702** The cursor passed as the only argument must point to a valid entry703** when this function is called (i.e. have eState==CURSOR_VALID). This704** function saves the current cursor key in variables pCur->nKey and705** pCur->pKey. SQLITE_OK is returned if successful or an SQLite error706** code otherwise.707**708** If the cursor is open on an intkey table, then the integer key709** (the rowid) is stored in pCur->nKey and pCur->pKey is left set to710** NULL. If the cursor is open on a non-intkey table, then pCur->pKey is711** set to point to a malloced buffer pCur->nKey bytes in size containing712** the key.713*/714static int saveCursorKey(BtCursor *pCur){715 int rc = SQLITE_OK;716 assert( CURSOR_VALID==pCur->eState );717 assert( 0==pCur->pKey );718 assert( cursorHoldsMutex(pCur) );719 720 if( pCur->curIntKey ){721 /* Only the rowid is required for a table btree */722 pCur->nKey = sqlite3BtreeIntegerKey(pCur);723 }else{724 /* For an index btree, save the complete key content. It is possible725 ** that the current key is corrupt. In that case, it is possible that726 ** the sqlite3VdbeRecordUnpack() function may overread the buffer by727 ** up to the size of 1 varint plus 1 8-byte value when the cursor728 ** position is restored. Hence the 17 bytes of padding allocated729 ** below. */730 void *pKey;731 pCur->nKey = sqlite3BtreePayloadSize(pCur);732 pKey = sqlite3Malloc( ((i64)pCur->nKey) + 9 + 8 );733 if( pKey ){734 rc = sqlite3BtreePayload(pCur, 0, (int)pCur->nKey, pKey);735 if( rc==SQLITE_OK ){736 memset(((u8*)pKey)+pCur->nKey, 0, 9+8);737 pCur->pKey = pKey;738 }else{739 sqlite3_free(pKey);740 }741 }else{742 rc = SQLITE_NOMEM_BKPT;743 }744 }745 assert( !pCur->curIntKey || !pCur->pKey );746 return rc;747}748 749/*750** Save the current cursor position in the variables BtCursor.nKey751** and BtCursor.pKey. The cursor's state is set to CURSOR_REQUIRESEEK.752**753** The caller must ensure that the cursor is valid (has eState==CURSOR_VALID)754** prior to calling this routine. 755*/756static int saveCursorPosition(BtCursor *pCur){757 int rc;758 759 assert( CURSOR_VALID==pCur->eState || CURSOR_SKIPNEXT==pCur->eState );760 assert( 0==pCur->pKey );761 assert( cursorHoldsMutex(pCur) );762 763 if( pCur->curFlags & BTCF_Pinned ){764 return SQLITE_CONSTRAINT_PINNED;765 }766 if( pCur->eState==CURSOR_SKIPNEXT ){767 pCur->eState = CURSOR_VALID;768 }else{769 pCur->skipNext = 0;770 }771 772 rc = saveCursorKey(pCur);773 if( rc==SQLITE_OK ){774 btreeReleaseAllCursorPages(pCur);775 pCur->eState = CURSOR_REQUIRESEEK;776 }777 778 pCur->curFlags &= ~(BTCF_ValidNKey|BTCF_ValidOvfl|BTCF_AtLast);779 return rc;780}781 782/* Forward reference */783static int SQLITE_NOINLINE saveCursorsOnList(BtCursor*,Pgno,BtCursor*);784 785/*786** Save the positions of all cursors (except pExcept) that are open on787** the table with root-page iRoot. "Saving the cursor position" means that788** the location in the btree is remembered in such a way that it can be789** moved back to the same spot after the btree has been modified. This790** routine is called just before cursor pExcept is used to modify the791** table, for example in BtreeDelete() or BtreeInsert().792**793** If there are two or more cursors on the same btree, then all such794** cursors should have their BTCF_Multiple flag set. The btreeCursor()795** routine enforces that rule. This routine only needs to be called in796** the uncommon case when pExpect has the BTCF_Multiple flag set.797**798** If pExpect!=NULL and if no other cursors are found on the same root-page,799** then the BTCF_Multiple flag on pExpect is cleared, to avoid another800** pointless call to this routine.801**802** Implementation note: This routine merely checks to see if any cursors803** need to be saved. It calls out to saveCursorsOnList() in the (unusual)804** event that cursors are in need to being saved.805*/806static int saveAllCursors(BtShared *pBt, Pgno iRoot, BtCursor *pExcept){807 BtCursor *p;808 assert( sqlite3_mutex_held(pBt->mutex) );809 assert( pExcept==0 || pExcept->pBt==pBt );810 for(p=pBt->pCursor; p; p=p->pNext){811 if( p!=pExcept && (0==iRoot || p->pgnoRoot==iRoot) ) break;812 }813 if( p ) return saveCursorsOnList(p, iRoot, pExcept);814 if( pExcept ) pExcept->curFlags &= ~BTCF_Multiple;815 return SQLITE_OK;816}817 818/* This helper routine to saveAllCursors does the actual work of saving819** the cursors if and when a cursor is found that actually requires saving.820** The common case is that no cursors need to be saved, so this routine is821** broken out from its caller to avoid unnecessary stack pointer movement.822*/823static int SQLITE_NOINLINE saveCursorsOnList(824 BtCursor *p, /* The first cursor that needs saving */825 Pgno iRoot, /* Only save cursor with this iRoot. Save all if zero */826 BtCursor *pExcept /* Do not save this cursor */827){828 do{829 if( p!=pExcept && (0==iRoot || p->pgnoRoot==iRoot) ){830 if( p->eState==CURSOR_VALID || p->eState==CURSOR_SKIPNEXT ){831 int rc = saveCursorPosition(p);832 if( SQLITE_OK!=rc ){833 return rc;834 }835 }else{836 testcase( p->iPage>=0 );837 btreeReleaseAllCursorPages(p);838 }839 }840 p = p->pNext;841 }while( p );842 return SQLITE_OK;843}844 845/*846** Clear the current cursor position.847*/848void sqlite3BtreeClearCursor(BtCursor *pCur){849 assert( cursorHoldsMutex(pCur) );850 sqlite3_free(pCur->pKey);851 pCur->pKey = 0;852 pCur->eState = CURSOR_INVALID;853}854 855/*856** In this version of BtreeMoveto, pKey is a packed index record857** such as is generated by the OP_MakeRecord opcode. Unpack the858** record and then call sqlite3BtreeIndexMoveto() to do the work.859*/860static int btreeMoveto(861 BtCursor *pCur, /* Cursor open on the btree to be searched */862 const void *pKey, /* Packed key if the btree is an index */863 i64 nKey, /* Integer key for tables. Size of pKey for indices */864 int bias, /* Bias search to the high end */865 int *pRes /* Write search results here */866){867 int rc; /* Status code */868 UnpackedRecord *pIdxKey; /* Unpacked index key */869 870 if( pKey ){871 KeyInfo *pKeyInfo = pCur->pKeyInfo;872 assert( nKey==(i64)(int)nKey );873 pIdxKey = sqlite3VdbeAllocUnpackedRecord(pKeyInfo);874 if( pIdxKey==0 ) return SQLITE_NOMEM_BKPT;875 sqlite3VdbeRecordUnpack((int)nKey, pKey, pIdxKey);876 if( pIdxKey->nField==0 || pIdxKey->nField>pKeyInfo->nAllField ){877 rc = SQLITE_CORRUPT_BKPT;878 }else{879 rc = sqlite3BtreeIndexMoveto(pCur, pIdxKey, pRes);880 }881 sqlite3DbFree(pCur->pKeyInfo->db, pIdxKey);882 }else{883 pIdxKey = 0;884 rc = sqlite3BtreeTableMoveto(pCur, nKey, bias, pRes);885 }886 return rc;887}888 889/*890** Restore the cursor to the position it was in (or as close to as possible)891** when saveCursorPosition() was called. Note that this call deletes the892** saved position info stored by saveCursorPosition(), so there can be893** at most one effective restoreCursorPosition() call after each894** saveCursorPosition().895*/896static int btreeRestoreCursorPosition(BtCursor *pCur){897 int rc;898 int skipNext = 0;899 assert( cursorOwnsBtShared(pCur) );900 assert( pCur->eState>=CURSOR_REQUIRESEEK );901 if( pCur->eState==CURSOR_FAULT ){902 return pCur->skipNext;903 }904 pCur->eState = CURSOR_INVALID;905 if( sqlite3FaultSim(410) ){906 rc = SQLITE_IOERR;907 }else{908 rc = btreeMoveto(pCur, pCur->pKey, pCur->nKey, 0, &skipNext);909 }910 if( rc==SQLITE_OK ){911 sqlite3_free(pCur->pKey);912 pCur->pKey = 0;913 assert( pCur->eState==CURSOR_VALID || pCur->eState==CURSOR_INVALID );914 if( skipNext ) pCur->skipNext = skipNext;915 if( pCur->skipNext && pCur->eState==CURSOR_VALID ){916 pCur->eState = CURSOR_SKIPNEXT;917 }918 }919 return rc;920}921 922#define restoreCursorPosition(p) \923 (p->eState>=CURSOR_REQUIRESEEK ? \924 btreeRestoreCursorPosition(p) : \925 SQLITE_OK)926 927/*928** Determine whether or not a cursor has moved from the position where929** it was last placed, or has been invalidated for any other reason.930** Cursors can move when the row they are pointing at is deleted out931** from under them, for example. Cursor might also move if a btree932** is rebalanced.933**934** Calling this routine with a NULL cursor pointer returns false.935**936** Use the separate sqlite3BtreeCursorRestore() routine to restore a cursor937** back to where it ought to be if this routine returns true.938*/939int sqlite3BtreeCursorHasMoved(BtCursor *pCur){940 assert( EIGHT_BYTE_ALIGNMENT(pCur)941 || pCur==sqlite3BtreeFakeValidCursor() );942 assert( offsetof(BtCursor, eState)==0 );943 assert( sizeof(pCur->eState)==1 );944 return CURSOR_VALID != *(u8*)pCur;945}946 947/*948** Return a pointer to a fake BtCursor object that will always answer949** false to the sqlite3BtreeCursorHasMoved() routine above. The fake950** cursor returned must not be used with any other Btree interface.951*/952BtCursor *sqlite3BtreeFakeValidCursor(void){953 static u8 fakeCursor = CURSOR_VALID;954 assert( offsetof(BtCursor, eState)==0 );955 return (BtCursor*)&fakeCursor;956}957 958/*959** This routine restores a cursor back to its original position after it960** has been moved by some outside activity (such as a btree rebalance or961** a row having been deleted out from under the cursor). 962**963** On success, the *pDifferentRow parameter is false if the cursor is left964** pointing at exactly the same row. *pDifferntRow is the row the cursor965** was pointing to has been deleted, forcing the cursor to point to some966** nearby row.967**968** This routine should only be called for a cursor that just returned969** TRUE from sqlite3BtreeCursorHasMoved().970*/971int sqlite3BtreeCursorRestore(BtCursor *pCur, int *pDifferentRow){972 int rc;973 974 assert( pCur!=0 );975 assert( pCur->eState!=CURSOR_VALID );976 rc = restoreCursorPosition(pCur);977 if( rc ){978 *pDifferentRow = 1;979 return rc;980 }981 if( pCur->eState!=CURSOR_VALID ){982 *pDifferentRow = 1;983 }else{984 *pDifferentRow = 0;985 }986 return SQLITE_OK;987}988 989#ifdef SQLITE_ENABLE_CURSOR_HINTS990/*991** Provide hints to the cursor. The particular hint given (and the type992** and number of the varargs parameters) is determined by the eHintType993** parameter. See the definitions of the BTREE_HINT_* macros for details.994*/995void sqlite3BtreeCursorHint(BtCursor *pCur, int eHintType, ...){996 /* Used only by system that substitute their own storage engine */997#ifdef SQLITE_DEBUG998 if( ALWAYS(eHintType==BTREE_HINT_RANGE) ){999 va_list ap;1000 Expr *pExpr;1001 Walker w;1002 memset(&w, 0, sizeof(w));1003 w.xExprCallback = sqlite3CursorRangeHintExprCheck;1004 va_start(ap, eHintType);1005 pExpr = va_arg(ap, Expr*);1006 w.u.aMem = va_arg(ap, Mem*);1007 va_end(ap);1008 assert( pExpr!=0 );1009 assert( w.u.aMem!=0 );1010 sqlite3WalkExpr(&w, pExpr);1011 }1012#endif /* SQLITE_DEBUG */1013}1014#endif /* SQLITE_ENABLE_CURSOR_HINTS */1015 1016 1017/*1018** Provide flag hints to the cursor.1019*/1020void sqlite3BtreeCursorHintFlags(BtCursor *pCur, unsigned x){1021 assert( x==BTREE_SEEK_EQ || x==BTREE_BULKLOAD || x==0 );1022 pCur->hints = (u8)x;1023}1024 1025 1026#ifndef SQLITE_OMIT_AUTOVACUUM1027/*1028** Given a page number of a regular database page, return the page1029** number for the pointer-map page that contains the entry for the1030** input page number.1031**1032** Return 0 (not a valid page) for pgno==1 since there is1033** no pointer map associated with page 1. The integrity_check logic1034** requires that ptrmapPageno(*,1)!=1.1035*/1036static Pgno ptrmapPageno(BtShared *pBt, Pgno pgno){1037 int nPagesPerMapPage;1038 Pgno iPtrMap, ret;1039 assert( sqlite3_mutex_held(pBt->mutex) );1040 if( pgno<2 ) return 0;1041 nPagesPerMapPage = (pBt->usableSize/5)+1;1042 iPtrMap = (pgno-2)/nPagesPerMapPage;1043 ret = (iPtrMap*nPagesPerMapPage) + 2;1044 if( ret==PENDING_BYTE_PAGE(pBt) ){1045 ret++;1046 }1047 return ret;1048}1049 1050/*1051** Write an entry into the pointer map.1052**1053** This routine updates the pointer map entry for page number 'key'1054** so that it maps to type 'eType' and parent page number 'pgno'.1055**1056** If *pRC is initially non-zero (non-SQLITE_OK) then this routine is1057** a no-op. If an error occurs, the appropriate error code is written1058** into *pRC.1059*/1060static void ptrmapPut(BtShared *pBt, Pgno key, u8 eType, Pgno parent, int *pRC){1061 DbPage *pDbPage; /* The pointer map page */1062 u8 *pPtrmap; /* The pointer map data */1063 Pgno iPtrmap; /* The pointer map page number */1064 int offset; /* Offset in pointer map page */1065 int rc; /* Return code from subfunctions */1066 1067 if( *pRC ) return;1068 1069 assert( sqlite3_mutex_held(pBt->mutex) );1070 /* The super-journal page number must never be used as a pointer map page */1071 assert( 0==PTRMAP_ISPAGE(pBt, PENDING_BYTE_PAGE(pBt)) );1072 1073 assert( pBt->autoVacuum );1074 if( key==0 ){1075 *pRC = SQLITE_CORRUPT_BKPT;1076 return;1077 }1078 iPtrmap = PTRMAP_PAGENO(pBt, key);1079 rc = sqlite3PagerGet(pBt->pPager, iPtrmap, &pDbPage, 0);1080 if( rc!=SQLITE_OK ){1081 *pRC = rc;1082 return;1083 }1084 if( ((char*)sqlite3PagerGetExtra(pDbPage))[0]!=0 ){1085 /* The first byte of the extra data is the MemPage.isInit byte.1086 ** If that byte is set, it means this page is also being used1087 ** as a btree page. */1088 *pRC = SQLITE_CORRUPT_BKPT;1089 goto ptrmap_exit;1090 }1091 offset = PTRMAP_PTROFFSET(iPtrmap, key);1092 if( offset<0 ){1093 *pRC = SQLITE_CORRUPT_BKPT;1094 goto ptrmap_exit;1095 }1096 assert( offset <= (int)pBt->usableSize-5 );1097 pPtrmap = (u8 *)sqlite3PagerGetData(pDbPage);1098 1099 if( eType!=pPtrmap[offset] || get4byte(&pPtrmap[offset+1])!=parent ){1100 TRACE(("PTRMAP_UPDATE: %u->(%u,%u)\n", key, eType, parent));1101 *pRC= rc = sqlite3PagerWrite(pDbPage);1102 if( rc==SQLITE_OK ){1103 pPtrmap[offset] = eType;1104 put4byte(&pPtrmap[offset+1], parent);1105 }1106 }1107 1108ptrmap_exit:1109 sqlite3PagerUnref(pDbPage);1110}1111 1112/*1113** Read an entry from the pointer map.1114**1115** This routine retrieves the pointer map entry for page 'key', writing1116** the type and parent page number to *pEType and *pPgno respectively.1117** An error code is returned if something goes wrong, otherwise SQLITE_OK.1118*/1119static int ptrmapGet(BtShared *pBt, Pgno key, u8 *pEType, Pgno *pPgno){1120 DbPage *pDbPage; /* The pointer map page */1121 int iPtrmap; /* Pointer map page index */1122 u8 *pPtrmap; /* Pointer map page data */1123 int offset; /* Offset of entry in pointer map */1124 int rc;1125 1126 assert( sqlite3_mutex_held(pBt->mutex) );1127 1128 iPtrmap = PTRMAP_PAGENO(pBt, key);1129 rc = sqlite3PagerGet(pBt->pPager, iPtrmap, &pDbPage, 0);1130 if( rc!=0 ){1131 return rc;1132 }1133 pPtrmap = (u8 *)sqlite3PagerGetData(pDbPage);1134 1135 offset = PTRMAP_PTROFFSET(iPtrmap, key);1136 if( offset<0 ){1137 sqlite3PagerUnref(pDbPage);1138 return SQLITE_CORRUPT_BKPT;1139 }1140 assert( offset <= (int)pBt->usableSize-5 );1141 assert( pEType!=0 );1142 *pEType = pPtrmap[offset];1143 if( pPgno ) *pPgno = get4byte(&pPtrmap[offset+1]);1144 1145 sqlite3PagerUnref(pDbPage);1146 if( *pEType<1 || *pEType>5 ) return SQLITE_CORRUPT_PGNO(iPtrmap);1147 return SQLITE_OK;1148}1149 1150#else /* if defined SQLITE_OMIT_AUTOVACUUM */1151 #define ptrmapPut(w,x,y,z,rc)1152 #define ptrmapGet(w,x,y,z) SQLITE_OK1153 #define ptrmapPutOvflPtr(x, y, z, rc)1154#endif1155 1156/*1157** Given a btree page and a cell index (0 means the first cell on1158** the page, 1 means the second cell, and so forth) return a pointer1159** to the cell content.1160**1161** findCellPastPtr() does the same except it skips past the initial1162** 4-byte child pointer found on interior pages, if there is one.1163**1164** This routine works only for pages that do not contain overflow cells.1165*/1166#define findCell(P,I) \1167 ((P)->aData + ((P)->maskPage & get2byteAligned(&(P)->aCellIdx[2*(I)])))1168#define findCellPastPtr(P,I) \1169 ((P)->aDataOfst + ((P)->maskPage & get2byteAligned(&(P)->aCellIdx[2*(I)])))1170 1171 1172/*1173** This is common tail processing for btreeParseCellPtr() and1174** btreeParseCellPtrIndex() for the case when the cell does not fit entirely1175** on a single B-tree page. Make necessary adjustments to the CellInfo1176** structure.1177*/1178static SQLITE_NOINLINE void btreeParseCellAdjustSizeForOverflow(1179 MemPage *pPage, /* Page containing the cell */1180 u8 *pCell, /* Pointer to the cell text. */1181 CellInfo *pInfo /* Fill in this structure */1182){1183 /* If the payload will not fit completely on the local page, we have1184 ** to decide how much to store locally and how much to spill onto1185 ** overflow pages. The strategy is to minimize the amount of unused1186 ** space on overflow pages while keeping the amount of local storage1187 ** in between minLocal and maxLocal.1188 **1189 ** Warning: changing the way overflow payload is distributed in any1190 ** way will result in an incompatible file format.1191 */1192 int minLocal; /* Minimum amount of payload held locally */1193 int maxLocal; /* Maximum amount of payload held locally */1194 int surplus; /* Overflow payload available for local storage */1195 1196 minLocal = pPage->minLocal;1197 maxLocal = pPage->maxLocal;1198 surplus = minLocal + (pInfo->nPayload - minLocal)%(pPage->pBt->usableSize-4);1199 testcase( surplus==maxLocal );1200 testcase( surplus==maxLocal+1 );