000001 /*
000002 ** 2010 February 1
000003 **
000004 ** The author disclaims copyright to this source code. In place of
000005 ** a legal notice, here is a blessing:
000006 **
000007 ** May you do good and not evil.
000008 ** May you find forgiveness for yourself and forgive others.
000009 ** May you share freely, never taking more than you give.
000010 **
000011 *************************************************************************
000012 **
000013 ** This file contains the implementation of a write-ahead log (WAL) used in
000014 ** "journal_mode=WAL" mode.
000015 **
000016 ** WRITE-AHEAD LOG (WAL) FILE FORMAT
000017 **
000018 ** A WAL file consists of a header followed by zero or more "frames".
000019 ** Each frame records the revised content of a single page from the
000020 ** database file. All changes to the database are recorded by writing
000021 ** frames into the WAL. Transactions commit when a frame is written that
000022 ** contains a commit marker. A single WAL can and usually does record
000023 ** multiple transactions. Periodically, the content of the WAL is
000024 ** transferred back into the database file in an operation called a
000025 ** "checkpoint".
000026 **
000027 ** A single WAL file can be used multiple times. In other words, the
000028 ** WAL can fill up with frames and then be checkpointed and then new
000029 ** frames can overwrite the old ones. A WAL always grows from beginning
000030 ** toward the end. Checksums and counters attached to each frame are
000031 ** used to determine which frames within the WAL are valid and which
000032 ** are leftovers from prior checkpoints.
000033 **
000034 ** The WAL header is 32 bytes in size and consists of the following eight
000035 ** big-endian 32-bit unsigned integer values:
000036 **
000037 ** 0: Magic number. 0x377f0682 or 0x377f0683
000038 ** 4: File format version. Currently 3007000
000039 ** 8: Database page size. Example: 1024
000040 ** 12: Checkpoint sequence number
000041 ** 16: Salt-1, random integer incremented with each checkpoint
000042 ** 20: Salt-2, a different random integer changing with each ckpt
000043 ** 24: Checksum-1 (first part of checksum for first 24 bytes of header).
000044 ** 28: Checksum-2 (second part of checksum for first 24 bytes of header).
000045 **
000046 ** Immediately following the wal-header are zero or more frames. Each
000047 ** frame consists of a 24-byte frame-header followed by a <page-size> bytes
000048 ** of page data. The frame-header is six big-endian 32-bit unsigned
000049 ** integer values, as follows:
000050 **
000051 ** 0: Page number.
000052 ** 4: For commit records, the size of the database image in pages
000053 ** after the commit. For all other records, zero.
000054 ** 8: Salt-1 (copied from the header)
000055 ** 12: Salt-2 (copied from the header)
000056 ** 16: Checksum-1.
000057 ** 20: Checksum-2.
000058 **
000059 ** A frame is considered valid if and only if the following conditions are
000060 ** true:
000061 **
000062 ** (1) The salt-1 and salt-2 values in the frame-header match
000063 ** salt values in the wal-header
000064 **
000065 ** (2) The checksum values in the final 8 bytes of the frame-header
000066 ** exactly match the checksum computed consecutively on the
000067 ** WAL header and the first 8 bytes and the content of all frames
000068 ** up to and including the current frame.
000069 **
000070 ** The checksum is computed using 32-bit big-endian integers if the
000071 ** magic number in the first 4 bytes of the WAL is 0x377f0683 and it
000072 ** is computed using little-endian if the magic number is 0x377f0682.
000073 ** The checksum values are always stored in the frame header in a
000074 ** big-endian format regardless of which byte order is used to compute
000075 ** the checksum. The checksum is computed by interpreting the input as
000076 ** an even number of unsigned 32-bit integers: x[0] through x[N]. The
000077 ** algorithm used for the checksum is as follows:
000078 **
000079 ** for i from 0 to n-1 step 2:
000080 ** s0 += x[i] + s1;
000081 ** s1 += x[i+1] + s0;
000082 ** endfor
000083 **
000084 ** Note that s0 and s1 are both weighted checksums using fibonacci weights
000085 ** in reverse order (the largest fibonacci weight occurs on the first element
000086 ** of the sequence being summed.) The s1 value spans all 32-bit
000087 ** terms of the sequence whereas s0 omits the final term.
000088 **
000089 ** On a checkpoint, the WAL is first VFS.xSync-ed, then valid content of the
000090 ** WAL is transferred into the database, then the database is VFS.xSync-ed.
000091 ** The VFS.xSync operations serve as write barriers - all writes launched
000092 ** before the xSync must complete before any write that launches after the
000093 ** xSync begins.
000094 **
000095 ** After each checkpoint, the salt-1 value is incremented and the salt-2
000096 ** value is randomized. This prevents old and new frames in the WAL from
000097 ** being considered valid at the same time and being checkpointing together
000098 ** following a crash.
000099 **
000100 ** READER ALGORITHM
000101 **
000102 ** To read a page from the database (call it page number P), a reader
000103 ** first checks the WAL to see if it contains page P. If so, then the
000104 ** last valid instance of page P that is a followed by a commit frame
000105 ** or is a commit frame itself becomes the value read. If the WAL
000106 ** contains no copies of page P that are valid and which are a commit
000107 ** frame or are followed by a commit frame, then page P is read from
000108 ** the database file.
000109 **
000110 ** To start a read transaction, the reader records the index of the last
000111 ** valid frame in the WAL. The reader uses this recorded "mxFrame" value
000112 ** for all subsequent read operations. New transactions can be appended
000113 ** to the WAL, but as long as the reader uses its original mxFrame value
000114 ** and ignores the newly appended content, it will see a consistent snapshot
000115 ** of the database from a single point in time. This technique allows
000116 ** multiple concurrent readers to view different versions of the database
000117 ** content simultaneously.
000118 **
000119 ** The reader algorithm in the previous paragraphs works correctly, but
000120 ** because frames for page P can appear anywhere within the WAL, the
000121 ** reader has to scan the entire WAL looking for page P frames. If the
000122 ** WAL is large (multiple megabytes is typical) that scan can be slow,
000123 ** and read performance suffers. To overcome this problem, a separate
000124 ** data structure called the wal-index is maintained to expedite the
000125 ** search for frames of a particular page.
000126 **
000127 ** WAL-INDEX FORMAT
000128 **
000129 ** Conceptually, the wal-index is shared memory, though VFS implementations
000130 ** might choose to implement the wal-index using a mmapped file. Because
000131 ** the wal-index is shared memory, SQLite does not support journal_mode=WAL
000132 ** on a network filesystem. All users of the database must be able to
000133 ** share memory.
000134 **
000135 ** The wal-index is transient. After a crash, the wal-index can (and should
000136 ** be) reconstructed from the original WAL file. In fact, the VFS is required
000137 ** to either truncate or zero the header of the wal-index when the last
000138 ** connection to it closes. Because the wal-index is transient, it can
000139 ** use an architecture-specific format; it does not have to be cross-platform.
000140 ** Hence, unlike the database and WAL file formats which store all values
000141 ** as big endian, the wal-index can store multi-byte values in the native
000142 ** byte order of the host computer.
000143 **
000144 ** The purpose of the wal-index is to answer this question quickly: Given
000145 ** a page number P and a maximum frame index M, return the index of the
000146 ** last frame in the wal before frame M for page P in the WAL, or return
000147 ** NULL if there are no frames for page P in the WAL prior to M.
000148 **
000149 ** The wal-index consists of a header region, followed by an one or
000150 ** more index blocks.
000151 **
000152 ** The wal-index header contains the total number of frames within the WAL
000153 ** in the mxFrame field.
000154 **
000155 ** Each index block except for the first contains information on
000156 ** HASHTABLE_NPAGE frames. The first index block contains information on
000157 ** HASHTABLE_NPAGE_ONE frames. The values of HASHTABLE_NPAGE_ONE and
000158 ** HASHTABLE_NPAGE are selected so that together the wal-index header and
000159 ** first index block are the same size as all other index blocks in the
000160 ** wal-index.
000161 **
000162 ** Each index block contains two sections, a page-mapping that contains the
000163 ** database page number associated with each wal frame, and a hash-table
000164 ** that allows readers to query an index block for a specific page number.
000165 ** The page-mapping is an array of HASHTABLE_NPAGE (or HASHTABLE_NPAGE_ONE
000166 ** for the first index block) 32-bit page numbers. The first entry in the
000167 ** first index-block contains the database page number corresponding to the
000168 ** first frame in the WAL file. The first entry in the second index block
000169 ** in the WAL file corresponds to the (HASHTABLE_NPAGE_ONE+1)th frame in
000170 ** the log, and so on.
000171 **
000172 ** The last index block in a wal-index usually contains less than the full
000173 ** complement of HASHTABLE_NPAGE (or HASHTABLE_NPAGE_ONE) page-numbers,
000174 ** depending on the contents of the WAL file. This does not change the
000175 ** allocated size of the page-mapping array - the page-mapping array merely
000176 ** contains unused entries.
000177 **
000178 ** Even without using the hash table, the last frame for page P
000179 ** can be found by scanning the page-mapping sections of each index block
000180 ** starting with the last index block and moving toward the first, and
000181 ** within each index block, starting at the end and moving toward the
000182 ** beginning. The first entry that equals P corresponds to the frame
000183 ** holding the content for that page.
000184 **
000185 ** The hash table consists of HASHTABLE_NSLOT 16-bit unsigned integers.
000186 ** HASHTABLE_NSLOT = 2*HASHTABLE_NPAGE, and there is one entry in the
000187 ** hash table for each page number in the mapping section, so the hash
000188 ** table is never more than half full. The expected number of collisions
000189 ** prior to finding a match is 1. Each entry of the hash table is an
000190 ** 1-based index of an entry in the mapping section of the same
000191 ** index block. Let K be the 1-based index of the largest entry in
000192 ** the mapping section. (For index blocks other than the last, K will
000193 ** always be exactly HASHTABLE_NPAGE (4096) and for the last index block
000194 ** K will be (mxFrame%HASHTABLE_NPAGE).) Unused slots of the hash table
000195 ** contain a value of 0.
000196 **
000197 ** To look for page P in the hash table, first compute a hash iKey on
000198 ** P as follows:
000199 **
000200 ** iKey = (P * 383) % HASHTABLE_NSLOT
000201 **
000202 ** Then start scanning entries of the hash table, starting with iKey
000203 ** (wrapping around to the beginning when the end of the hash table is
000204 ** reached) until an unused hash slot is found. Let the first unused slot
000205 ** be at index iUnused. (iUnused might be less than iKey if there was
000206 ** wrap-around.) Because the hash table is never more than half full,
000207 ** the search is guaranteed to eventually hit an unused entry. Let
000208 ** iMax be the value between iKey and iUnused, closest to iUnused,
000209 ** where aHash[iMax]==P. If there is no iMax entry (if there exists
000210 ** no hash slot such that aHash[i]==p) then page P is not in the
000211 ** current index block. Otherwise the iMax-th mapping entry of the
000212 ** current index block corresponds to the last entry that references
000213 ** page P.
000214 **
000215 ** A hash search begins with the last index block and moves toward the
000216 ** first index block, looking for entries corresponding to page P. On
000217 ** average, only two or three slots in each index block need to be
000218 ** examined in order to either find the last entry for page P, or to
000219 ** establish that no such entry exists in the block. Each index block
000220 ** holds over 4000 entries. So two or three index blocks are sufficient
000221 ** to cover a typical 10 megabyte WAL file, assuming 1K pages. 8 or 10
000222 ** comparisons (on average) suffice to either locate a frame in the
000223 ** WAL or to establish that the frame does not exist in the WAL. This
000224 ** is much faster than scanning the entire 10MB WAL.
000225 **
000226 ** Note that entries are added in order of increasing K. Hence, one
000227 ** reader might be using some value K0 and a second reader that started
000228 ** at a later time (after additional transactions were added to the WAL
000229 ** and to the wal-index) might be using a different value K1, where K1>K0.
000230 ** Both readers can use the same hash table and mapping section to get
000231 ** the correct result. There may be entries in the hash table with
000232 ** K>K0 but to the first reader, those entries will appear to be unused
000233 ** slots in the hash table and so the first reader will get an answer as
000234 ** if no values greater than K0 had ever been inserted into the hash table
000235 ** in the first place - which is what reader one wants. Meanwhile, the
000236 ** second reader using K1 will see additional values that were inserted
000237 ** later, which is exactly what reader two wants.
000238 **
000239 ** When a rollback occurs, the value of K is decreased. Hash table entries
000240 ** that correspond to frames greater than the new K value are removed
000241 ** from the hash table at this point.
000242 */
000243 #ifndef SQLITE_OMIT_WAL
000244
000245 #include "wal.h"
000246
000247 /*
000248 ** Trace output macros
000249 */
000250 #if defined(SQLITE_TEST) && defined(SQLITE_DEBUG)
000251 int sqlite3WalTrace = 0;
000252 # define WALTRACE(X) if(sqlite3WalTrace) sqlite3DebugPrintf X
000253 #else
000254 # define WALTRACE(X)
000255 #endif
000256
000257 /*
000258 ** The maximum (and only) versions of the wal and wal-index formats
000259 ** that may be interpreted by this version of SQLite.
000260 **
000261 ** If a client begins recovering a WAL file and finds that (a) the checksum
000262 ** values in the wal-header are correct and (b) the version field is not
000263 ** WAL_MAX_VERSION, recovery fails and SQLite returns SQLITE_CANTOPEN.
000264 **
000265 ** Similarly, if a client successfully reads a wal-index header (i.e. the
000266 ** checksum test is successful) and finds that the version field is not
000267 ** WALINDEX_MAX_VERSION, then no read-transaction is opened and SQLite
000268 ** returns SQLITE_CANTOPEN.
000269 */
000270 #define WAL_MAX_VERSION 3007000
000271 #define WALINDEX_MAX_VERSION 3007000
000272
000273 /*
000274 ** Indices of various locking bytes. WAL_NREADER is the number
000275 ** of available reader locks and should be at least 3. The default
000276 ** is SQLITE_SHM_NLOCK==8 and WAL_NREADER==5.
000277 */
000278 #define WAL_WRITE_LOCK 0
000279 #define WAL_ALL_BUT_WRITE 1
000280 #define WAL_CKPT_LOCK 1
000281 #define WAL_RECOVER_LOCK 2
000282 #define WAL_READ_LOCK(I) (3+(I))
000283 #define WAL_NREADER (SQLITE_SHM_NLOCK-3)
000284
000285
000286 /* Object declarations */
000287 typedef struct WalIndexHdr WalIndexHdr;
000288 typedef struct WalIterator WalIterator;
000289 typedef struct WalCkptInfo WalCkptInfo;
000290
000291
000292 /*
000293 ** The following object holds a copy of the wal-index header content.
000294 **
000295 ** The actual header in the wal-index consists of two copies of this
000296 ** object followed by one instance of the WalCkptInfo object.
000297 ** For all versions of SQLite through 3.10.0 and probably beyond,
000298 ** the locking bytes (WalCkptInfo.aLock) start at offset 120 and
000299 ** the total header size is 136 bytes.
000300 **
000301 ** The szPage value can be any power of 2 between 512 and 32768, inclusive.
000302 ** Or it can be 1 to represent a 65536-byte page. The latter case was
000303 ** added in 3.7.1 when support for 64K pages was added.
000304 */
000305 struct WalIndexHdr {
000306 u32 iVersion; /* Wal-index version */
000307 u32 unused; /* Unused (padding) field */
000308 u32 iChange; /* Counter incremented each transaction */
000309 u8 isInit; /* 1 when initialized */
000310 u8 bigEndCksum; /* True if checksums in WAL are big-endian */
000311 u16 szPage; /* Database page size in bytes. 1==64K */
000312 u32 mxFrame; /* Index of last valid frame in the WAL */
000313 u32 nPage; /* Size of database in pages */
000314 u32 aFrameCksum[2]; /* Checksum of last frame in log */
000315 u32 aSalt[2]; /* Two salt values copied from WAL header */
000316 u32 aCksum[2]; /* Checksum over all prior fields */
000317 };
000318
000319 /*
000320 ** A copy of the following object occurs in the wal-index immediately
000321 ** following the second copy of the WalIndexHdr. This object stores
000322 ** information used by checkpoint.
000323 **
000324 ** nBackfill is the number of frames in the WAL that have been written
000325 ** back into the database. (We call the act of moving content from WAL to
000326 ** database "backfilling".) The nBackfill number is never greater than
000327 ** WalIndexHdr.mxFrame. nBackfill can only be increased by threads
000328 ** holding the WAL_CKPT_LOCK lock (which includes a recovery thread).
000329 ** However, a WAL_WRITE_LOCK thread can move the value of nBackfill from
000330 ** mxFrame back to zero when the WAL is reset.
000331 **
000332 ** nBackfillAttempted is the largest value of nBackfill that a checkpoint
000333 ** has attempted to achieve. Normally nBackfill==nBackfillAtempted, however
000334 ** the nBackfillAttempted is set before any backfilling is done and the
000335 ** nBackfill is only set after all backfilling completes. So if a checkpoint
000336 ** crashes, nBackfillAttempted might be larger than nBackfill. The
000337 ** WalIndexHdr.mxFrame must never be less than nBackfillAttempted.
000338 **
000339 ** The aLock[] field is a set of bytes used for locking. These bytes should
000340 ** never be read or written.
000341 **
000342 ** There is one entry in aReadMark[] for each reader lock. If a reader
000343 ** holds read-lock K, then the value in aReadMark[K] is no greater than
000344 ** the mxFrame for that reader. The value READMARK_NOT_USED (0xffffffff)
000345 ** for any aReadMark[] means that entry is unused. aReadMark[0] is
000346 ** a special case; its value is never used and it exists as a place-holder
000347 ** to avoid having to offset aReadMark[] indexs by one. Readers holding
000348 ** WAL_READ_LOCK(0) always ignore the entire WAL and read all content
000349 ** directly from the database.
000350 **
000351 ** The value of aReadMark[K] may only be changed by a thread that
000352 ** is holding an exclusive lock on WAL_READ_LOCK(K). Thus, the value of
000353 ** aReadMark[K] cannot changed while there is a reader is using that mark
000354 ** since the reader will be holding a shared lock on WAL_READ_LOCK(K).
000355 **
000356 ** The checkpointer may only transfer frames from WAL to database where
000357 ** the frame numbers are less than or equal to every aReadMark[] that is
000358 ** in use (that is, every aReadMark[j] for which there is a corresponding
000359 ** WAL_READ_LOCK(j)). New readers (usually) pick the aReadMark[] with the
000360 ** largest value and will increase an unused aReadMark[] to mxFrame if there
000361 ** is not already an aReadMark[] equal to mxFrame. The exception to the
000362 ** previous sentence is when nBackfill equals mxFrame (meaning that everything
000363 ** in the WAL has been backfilled into the database) then new readers
000364 ** will choose aReadMark[0] which has value 0 and hence such reader will
000365 ** get all their all content directly from the database file and ignore
000366 ** the WAL.
000367 **
000368 ** Writers normally append new frames to the end of the WAL. However,
000369 ** if nBackfill equals mxFrame (meaning that all WAL content has been
000370 ** written back into the database) and if no readers are using the WAL
000371 ** (in other words, if there are no WAL_READ_LOCK(i) where i>0) then
000372 ** the writer will first "reset" the WAL back to the beginning and start
000373 ** writing new content beginning at frame 1.
000374 **
000375 ** We assume that 32-bit loads are atomic and so no locks are needed in
000376 ** order to read from any aReadMark[] entries.
000377 */
000378 struct WalCkptInfo {
000379 u32 nBackfill; /* Number of WAL frames backfilled into DB */
000380 u32 aReadMark[WAL_NREADER]; /* Reader marks */
000381 u8 aLock[SQLITE_SHM_NLOCK]; /* Reserved space for locks */
000382 u32 nBackfillAttempted; /* WAL frames perhaps written, or maybe not */
000383 u32 notUsed0; /* Available for future enhancements */
000384 };
000385 #define READMARK_NOT_USED 0xffffffff
000386
000387
000388 /* A block of WALINDEX_LOCK_RESERVED bytes beginning at
000389 ** WALINDEX_LOCK_OFFSET is reserved for locks. Since some systems
000390 ** only support mandatory file-locks, we do not read or write data
000391 ** from the region of the file on which locks are applied.
000392 */
000393 #define WALINDEX_LOCK_OFFSET (sizeof(WalIndexHdr)*2+offsetof(WalCkptInfo,aLock))
000394 #define WALINDEX_HDR_SIZE (sizeof(WalIndexHdr)*2+sizeof(WalCkptInfo))
000395
000396 /* Size of header before each frame in wal */
000397 #define WAL_FRAME_HDRSIZE 24
000398
000399 /* Size of write ahead log header, including checksum. */
000400 /* #define WAL_HDRSIZE 24 */
000401 #define WAL_HDRSIZE 32
000402
000403 /* WAL magic value. Either this value, or the same value with the least
000404 ** significant bit also set (WAL_MAGIC | 0x00000001) is stored in 32-bit
000405 ** big-endian format in the first 4 bytes of a WAL file.
000406 **
000407 ** If the LSB is set, then the checksums for each frame within the WAL
000408 ** file are calculated by treating all data as an array of 32-bit
000409 ** big-endian words. Otherwise, they are calculated by interpreting
000410 ** all data as 32-bit little-endian words.
000411 */
000412 #define WAL_MAGIC 0x377f0682
000413
000414 /*
000415 ** Return the offset of frame iFrame in the write-ahead log file,
000416 ** assuming a database page size of szPage bytes. The offset returned
000417 ** is to the start of the write-ahead log frame-header.
000418 */
000419 #define walFrameOffset(iFrame, szPage) ( \
000420 WAL_HDRSIZE + ((iFrame)-1)*(i64)((szPage)+WAL_FRAME_HDRSIZE) \
000421 )
000422
000423 /*
000424 ** An open write-ahead log file is represented by an instance of the
000425 ** following object.
000426 */
000427 struct Wal {
000428 sqlite3_vfs *pVfs; /* The VFS used to create pDbFd */
000429 sqlite3_file *pDbFd; /* File handle for the database file */
000430 sqlite3_file *pWalFd; /* File handle for WAL file */
000431 u32 iCallback; /* Value to pass to log callback (or 0) */
000432 i64 mxWalSize; /* Truncate WAL to this size upon reset */
000433 int nWiData; /* Size of array apWiData */
000434 int szFirstBlock; /* Size of first block written to WAL file */
000435 volatile u32 **apWiData; /* Pointer to wal-index content in memory */
000436 u32 szPage; /* Database page size */
000437 i16 readLock; /* Which read lock is being held. -1 for none */
000438 u8 syncFlags; /* Flags to use to sync header writes */
000439 u8 exclusiveMode; /* Non-zero if connection is in exclusive mode */
000440 u8 writeLock; /* True if in a write transaction */
000441 u8 ckptLock; /* True if holding a checkpoint lock */
000442 u8 readOnly; /* WAL_RDWR, WAL_RDONLY, or WAL_SHM_RDONLY */
000443 u8 truncateOnCommit; /* True to truncate WAL file on commit */
000444 u8 syncHeader; /* Fsync the WAL header if true */
000445 u8 padToSectorBoundary; /* Pad transactions out to the next sector */
000446 WalIndexHdr hdr; /* Wal-index header for current transaction */
000447 u32 minFrame; /* Ignore wal frames before this one */
000448 u32 iReCksum; /* On commit, recalculate checksums from here */
000449 const char *zWalName; /* Name of WAL file */
000450 u32 nCkpt; /* Checkpoint sequence counter in the wal-header */
000451 #ifdef SQLITE_DEBUG
000452 u8 lockError; /* True if a locking error has occurred */
000453 #endif
000454 #ifdef SQLITE_ENABLE_SNAPSHOT
000455 WalIndexHdr *pSnapshot; /* Start transaction here if not NULL */
000456 #endif
000457 };
000458
000459 /*
000460 ** Candidate values for Wal.exclusiveMode.
000461 */
000462 #define WAL_NORMAL_MODE 0
000463 #define WAL_EXCLUSIVE_MODE 1
000464 #define WAL_HEAPMEMORY_MODE 2
000465
000466 /*
000467 ** Possible values for WAL.readOnly
000468 */
000469 #define WAL_RDWR 0 /* Normal read/write connection */
000470 #define WAL_RDONLY 1 /* The WAL file is readonly */
000471 #define WAL_SHM_RDONLY 2 /* The SHM file is readonly */
000472
000473 /*
000474 ** Each page of the wal-index mapping contains a hash-table made up of
000475 ** an array of HASHTABLE_NSLOT elements of the following type.
000476 */
000477 typedef u16 ht_slot;
000478
000479 /*
000480 ** This structure is used to implement an iterator that loops through
000481 ** all frames in the WAL in database page order. Where two or more frames
000482 ** correspond to the same database page, the iterator visits only the
000483 ** frame most recently written to the WAL (in other words, the frame with
000484 ** the largest index).
000485 **
000486 ** The internals of this structure are only accessed by:
000487 **
000488 ** walIteratorInit() - Create a new iterator,
000489 ** walIteratorNext() - Step an iterator,
000490 ** walIteratorFree() - Free an iterator.
000491 **
000492 ** This functionality is used by the checkpoint code (see walCheckpoint()).
000493 */
000494 struct WalIterator {
000495 int iPrior; /* Last result returned from the iterator */
000496 int nSegment; /* Number of entries in aSegment[] */
000497 struct WalSegment {
000498 int iNext; /* Next slot in aIndex[] not yet returned */
000499 ht_slot *aIndex; /* i0, i1, i2... such that aPgno[iN] ascend */
000500 u32 *aPgno; /* Array of page numbers. */
000501 int nEntry; /* Nr. of entries in aPgno[] and aIndex[] */
000502 int iZero; /* Frame number associated with aPgno[0] */
000503 } aSegment[1]; /* One for every 32KB page in the wal-index */
000504 };
000505
000506 /*
000507 ** Define the parameters of the hash tables in the wal-index file. There
000508 ** is a hash-table following every HASHTABLE_NPAGE page numbers in the
000509 ** wal-index.
000510 **
000511 ** Changing any of these constants will alter the wal-index format and
000512 ** create incompatibilities.
000513 */
000514 #define HASHTABLE_NPAGE 4096 /* Must be power of 2 */
000515 #define HASHTABLE_HASH_1 383 /* Should be prime */
000516 #define HASHTABLE_NSLOT (HASHTABLE_NPAGE*2) /* Must be a power of 2 */
000517
000518 /*
000519 ** The block of page numbers associated with the first hash-table in a
000520 ** wal-index is smaller than usual. This is so that there is a complete
000521 ** hash-table on each aligned 32KB page of the wal-index.
000522 */
000523 #define HASHTABLE_NPAGE_ONE (HASHTABLE_NPAGE - (WALINDEX_HDR_SIZE/sizeof(u32)))
000524
000525 /* The wal-index is divided into pages of WALINDEX_PGSZ bytes each. */
000526 #define WALINDEX_PGSZ ( \
000527 sizeof(ht_slot)*HASHTABLE_NSLOT + HASHTABLE_NPAGE*sizeof(u32) \
000528 )
000529
000530 /*
000531 ** Obtain a pointer to the iPage'th page of the wal-index. The wal-index
000532 ** is broken into pages of WALINDEX_PGSZ bytes. Wal-index pages are
000533 ** numbered from zero.
000534 **
000535 ** If this call is successful, *ppPage is set to point to the wal-index
000536 ** page and SQLITE_OK is returned. If an error (an OOM or VFS error) occurs,
000537 ** then an SQLite error code is returned and *ppPage is set to 0.
000538 */
000539 static int walIndexPage(Wal *pWal, int iPage, volatile u32 **ppPage){
000540 int rc = SQLITE_OK;
000541
000542 /* Enlarge the pWal->apWiData[] array if required */
000543 if( pWal->nWiData<=iPage ){
000544 int nByte = sizeof(u32*)*(iPage+1);
000545 volatile u32 **apNew;
000546 apNew = (volatile u32 **)sqlite3_realloc64((void *)pWal->apWiData, nByte);
000547 if( !apNew ){
000548 *ppPage = 0;
000549 return SQLITE_NOMEM_BKPT;
000550 }
000551 memset((void*)&apNew[pWal->nWiData], 0,
000552 sizeof(u32*)*(iPage+1-pWal->nWiData));
000553 pWal->apWiData = apNew;
000554 pWal->nWiData = iPage+1;
000555 }
000556
000557 /* Request a pointer to the required page from the VFS */
000558 if( pWal->apWiData[iPage]==0 ){
000559 if( pWal->exclusiveMode==WAL_HEAPMEMORY_MODE ){
000560 pWal->apWiData[iPage] = (u32 volatile *)sqlite3MallocZero(WALINDEX_PGSZ);
000561 if( !pWal->apWiData[iPage] ) rc = SQLITE_NOMEM_BKPT;
000562 }else{
000563 rc = sqlite3OsShmMap(pWal->pDbFd, iPage, WALINDEX_PGSZ,
000564 pWal->writeLock, (void volatile **)&pWal->apWiData[iPage]
000565 );
000566 if( rc==SQLITE_READONLY ){
000567 pWal->readOnly |= WAL_SHM_RDONLY;
000568 rc = SQLITE_OK;
000569 }
000570 }
000571 }
000572
000573 *ppPage = pWal->apWiData[iPage];
000574 assert( iPage==0 || *ppPage || rc!=SQLITE_OK );
000575 return rc;
000576 }
000577
000578 /*
000579 ** Return a pointer to the WalCkptInfo structure in the wal-index.
000580 */
000581 static volatile WalCkptInfo *walCkptInfo(Wal *pWal){
000582 assert( pWal->nWiData>0 && pWal->apWiData[0] );
000583 return (volatile WalCkptInfo*)&(pWal->apWiData[0][sizeof(WalIndexHdr)/2]);
000584 }
000585
000586 /*
000587 ** Return a pointer to the WalIndexHdr structure in the wal-index.
000588 */
000589 static volatile WalIndexHdr *walIndexHdr(Wal *pWal){
000590 assert( pWal->nWiData>0 && pWal->apWiData[0] );
000591 return (volatile WalIndexHdr*)pWal->apWiData[0];
000592 }
000593
000594 /*
000595 ** The argument to this macro must be of type u32. On a little-endian
000596 ** architecture, it returns the u32 value that results from interpreting
000597 ** the 4 bytes as a big-endian value. On a big-endian architecture, it
000598 ** returns the value that would be produced by interpreting the 4 bytes
000599 ** of the input value as a little-endian integer.
000600 */
000601 #define BYTESWAP32(x) ( \
000602 (((x)&0x000000FF)<<24) + (((x)&0x0000FF00)<<8) \
000603 + (((x)&0x00FF0000)>>8) + (((x)&0xFF000000)>>24) \
000604 )
000605
000606 /*
000607 ** Generate or extend an 8 byte checksum based on the data in
000608 ** array aByte[] and the initial values of aIn[0] and aIn[1] (or
000609 ** initial values of 0 and 0 if aIn==NULL).
000610 **
000611 ** The checksum is written back into aOut[] before returning.
000612 **
000613 ** nByte must be a positive multiple of 8.
000614 */
000615 static void walChecksumBytes(
000616 int nativeCksum, /* True for native byte-order, false for non-native */
000617 u8 *a, /* Content to be checksummed */
000618 int nByte, /* Bytes of content in a[]. Must be a multiple of 8. */
000619 const u32 *aIn, /* Initial checksum value input */
000620 u32 *aOut /* OUT: Final checksum value output */
000621 ){
000622 u32 s1, s2;
000623 u32 *aData = (u32 *)a;
000624 u32 *aEnd = (u32 *)&a[nByte];
000625
000626 if( aIn ){
000627 s1 = aIn[0];
000628 s2 = aIn[1];
000629 }else{
000630 s1 = s2 = 0;
000631 }
000632
000633 assert( nByte>=8 );
000634 assert( (nByte&0x00000007)==0 );
000635
000636 if( nativeCksum ){
000637 do {
000638 s1 += *aData++ + s2;
000639 s2 += *aData++ + s1;
000640 }while( aData<aEnd );
000641 }else{
000642 do {
000643 s1 += BYTESWAP32(aData[0]) + s2;
000644 s2 += BYTESWAP32(aData[1]) + s1;
000645 aData += 2;
000646 }while( aData<aEnd );
000647 }
000648
000649 aOut[0] = s1;
000650 aOut[1] = s2;
000651 }
000652
000653 static void walShmBarrier(Wal *pWal){
000654 if( pWal->exclusiveMode!=WAL_HEAPMEMORY_MODE ){
000655 sqlite3OsShmBarrier(pWal->pDbFd);
000656 }
000657 }
000658
000659 /*
000660 ** Write the header information in pWal->hdr into the wal-index.
000661 **
000662 ** The checksum on pWal->hdr is updated before it is written.
000663 */
000664 static void walIndexWriteHdr(Wal *pWal){
000665 volatile WalIndexHdr *aHdr = walIndexHdr(pWal);
000666 const int nCksum = offsetof(WalIndexHdr, aCksum);
000667
000668 assert( pWal->writeLock );
000669 pWal->hdr.isInit = 1;
000670 pWal->hdr.iVersion = WALINDEX_MAX_VERSION;
000671 walChecksumBytes(1, (u8*)&pWal->hdr, nCksum, 0, pWal->hdr.aCksum);
000672 memcpy((void*)&aHdr[1], (const void*)&pWal->hdr, sizeof(WalIndexHdr));
000673 walShmBarrier(pWal);
000674 memcpy((void*)&aHdr[0], (const void*)&pWal->hdr, sizeof(WalIndexHdr));
000675 }
000676
000677 /*
000678 ** This function encodes a single frame header and writes it to a buffer
000679 ** supplied by the caller. A frame-header is made up of a series of
000680 ** 4-byte big-endian integers, as follows:
000681 **
000682 ** 0: Page number.
000683 ** 4: For commit records, the size of the database image in pages
000684 ** after the commit. For all other records, zero.
000685 ** 8: Salt-1 (copied from the wal-header)
000686 ** 12: Salt-2 (copied from the wal-header)
000687 ** 16: Checksum-1.
000688 ** 20: Checksum-2.
000689 */
000690 static void walEncodeFrame(
000691 Wal *pWal, /* The write-ahead log */
000692 u32 iPage, /* Database page number for frame */
000693 u32 nTruncate, /* New db size (or 0 for non-commit frames) */
000694 u8 *aData, /* Pointer to page data */
000695 u8 *aFrame /* OUT: Write encoded frame here */
000696 ){
000697 int nativeCksum; /* True for native byte-order checksums */
000698 u32 *aCksum = pWal->hdr.aFrameCksum;
000699 assert( WAL_FRAME_HDRSIZE==24 );
000700 sqlite3Put4byte(&aFrame[0], iPage);
000701 sqlite3Put4byte(&aFrame[4], nTruncate);
000702 if( pWal->iReCksum==0 ){
000703 memcpy(&aFrame[8], pWal->hdr.aSalt, 8);
000704
000705 nativeCksum = (pWal->hdr.bigEndCksum==SQLITE_BIGENDIAN);
000706 walChecksumBytes(nativeCksum, aFrame, 8, aCksum, aCksum);
000707 walChecksumBytes(nativeCksum, aData, pWal->szPage, aCksum, aCksum);
000708
000709 sqlite3Put4byte(&aFrame[16], aCksum[0]);
000710 sqlite3Put4byte(&aFrame[20], aCksum[1]);
000711 }else{
000712 memset(&aFrame[8], 0, 16);
000713 }
000714 }
000715
000716 /*
000717 ** Check to see if the frame with header in aFrame[] and content
000718 ** in aData[] is valid. If it is a valid frame, fill *piPage and
000719 ** *pnTruncate and return true. Return if the frame is not valid.
000720 */
000721 static int walDecodeFrame(
000722 Wal *pWal, /* The write-ahead log */
000723 u32 *piPage, /* OUT: Database page number for frame */
000724 u32 *pnTruncate, /* OUT: New db size (or 0 if not commit) */
000725 u8 *aData, /* Pointer to page data (for checksum) */
000726 u8 *aFrame /* Frame data */
000727 ){
000728 int nativeCksum; /* True for native byte-order checksums */
000729 u32 *aCksum = pWal->hdr.aFrameCksum;
000730 u32 pgno; /* Page number of the frame */
000731 assert( WAL_FRAME_HDRSIZE==24 );
000732
000733 /* A frame is only valid if the salt values in the frame-header
000734 ** match the salt values in the wal-header.
000735 */
000736 if( memcmp(&pWal->hdr.aSalt, &aFrame[8], 8)!=0 ){
000737 return 0;
000738 }
000739
000740 /* A frame is only valid if the page number is creater than zero.
000741 */
000742 pgno = sqlite3Get4byte(&aFrame[0]);
000743 if( pgno==0 ){
000744 return 0;
000745 }
000746
000747 /* A frame is only valid if a checksum of the WAL header,
000748 ** all prior frams, the first 16 bytes of this frame-header,
000749 ** and the frame-data matches the checksum in the last 8
000750 ** bytes of this frame-header.
000751 */
000752 nativeCksum = (pWal->hdr.bigEndCksum==SQLITE_BIGENDIAN);
000753 walChecksumBytes(nativeCksum, aFrame, 8, aCksum, aCksum);
000754 walChecksumBytes(nativeCksum, aData, pWal->szPage, aCksum, aCksum);
000755 if( aCksum[0]!=sqlite3Get4byte(&aFrame[16])
000756 || aCksum[1]!=sqlite3Get4byte(&aFrame[20])
000757 ){
000758 /* Checksum failed. */
000759 return 0;
000760 }
000761
000762 /* If we reach this point, the frame is valid. Return the page number
000763 ** and the new database size.
000764 */
000765 *piPage = pgno;
000766 *pnTruncate = sqlite3Get4byte(&aFrame[4]);
000767 return 1;
000768 }
000769
000770
000771 #if defined(SQLITE_TEST) && defined(SQLITE_DEBUG)
000772 /*
000773 ** Names of locks. This routine is used to provide debugging output and is not
000774 ** a part of an ordinary build.
000775 */
000776 static const char *walLockName(int lockIdx){
000777 if( lockIdx==WAL_WRITE_LOCK ){
000778 return "WRITE-LOCK";
000779 }else if( lockIdx==WAL_CKPT_LOCK ){
000780 return "CKPT-LOCK";
000781 }else if( lockIdx==WAL_RECOVER_LOCK ){
000782 return "RECOVER-LOCK";
000783 }else{
000784 static char zName[15];
000785 sqlite3_snprintf(sizeof(zName), zName, "READ-LOCK[%d]",
000786 lockIdx-WAL_READ_LOCK(0));
000787 return zName;
000788 }
000789 }
000790 #endif /*defined(SQLITE_TEST) || defined(SQLITE_DEBUG) */
000791
000792
000793 /*
000794 ** Set or release locks on the WAL. Locks are either shared or exclusive.
000795 ** A lock cannot be moved directly between shared and exclusive - it must go
000796 ** through the unlocked state first.
000797 **
000798 ** In locking_mode=EXCLUSIVE, all of these routines become no-ops.
000799 */
000800 static int walLockShared(Wal *pWal, int lockIdx){
000801 int rc;
000802 if( pWal->exclusiveMode ) return SQLITE_OK;
000803 rc = sqlite3OsShmLock(pWal->pDbFd, lockIdx, 1,
000804 SQLITE_SHM_LOCK | SQLITE_SHM_SHARED);
000805 WALTRACE(("WAL%p: acquire SHARED-%s %s\n", pWal,
000806 walLockName(lockIdx), rc ? "failed" : "ok"));
000807 VVA_ONLY( pWal->lockError = (u8)(rc!=SQLITE_OK && rc!=SQLITE_BUSY); )
000808 return rc;
000809 }
000810 static void walUnlockShared(Wal *pWal, int lockIdx){
000811 if( pWal->exclusiveMode ) return;
000812 (void)sqlite3OsShmLock(pWal->pDbFd, lockIdx, 1,
000813 SQLITE_SHM_UNLOCK | SQLITE_SHM_SHARED);
000814 WALTRACE(("WAL%p: release SHARED-%s\n", pWal, walLockName(lockIdx)));
000815 }
000816 static int walLockExclusive(Wal *pWal, int lockIdx, int n){
000817 int rc;
000818 if( pWal->exclusiveMode ) return SQLITE_OK;
000819 rc = sqlite3OsShmLock(pWal->pDbFd, lockIdx, n,
000820 SQLITE_SHM_LOCK | SQLITE_SHM_EXCLUSIVE);
000821 WALTRACE(("WAL%p: acquire EXCLUSIVE-%s cnt=%d %s\n", pWal,
000822 walLockName(lockIdx), n, rc ? "failed" : "ok"));
000823 VVA_ONLY( pWal->lockError = (u8)(rc!=SQLITE_OK && rc!=SQLITE_BUSY); )
000824 return rc;
000825 }
000826 static void walUnlockExclusive(Wal *pWal, int lockIdx, int n){
000827 if( pWal->exclusiveMode ) return;
000828 (void)sqlite3OsShmLock(pWal->pDbFd, lockIdx, n,
000829 SQLITE_SHM_UNLOCK | SQLITE_SHM_EXCLUSIVE);
000830 WALTRACE(("WAL%p: release EXCLUSIVE-%s cnt=%d\n", pWal,
000831 walLockName(lockIdx), n));
000832 }
000833
000834 /*
000835 ** Compute a hash on a page number. The resulting hash value must land
000836 ** between 0 and (HASHTABLE_NSLOT-1). The walHashNext() function advances
000837 ** the hash to the next value in the event of a collision.
000838 */
000839 static int walHash(u32 iPage){
000840 assert( iPage>0 );
000841 assert( (HASHTABLE_NSLOT & (HASHTABLE_NSLOT-1))==0 );
000842 return (iPage*HASHTABLE_HASH_1) & (HASHTABLE_NSLOT-1);
000843 }
000844 static int walNextHash(int iPriorHash){
000845 return (iPriorHash+1)&(HASHTABLE_NSLOT-1);
000846 }
000847
000848 /*
000849 ** Return pointers to the hash table and page number array stored on
000850 ** page iHash of the wal-index. The wal-index is broken into 32KB pages
000851 ** numbered starting from 0.
000852 **
000853 ** Set output variable *paHash to point to the start of the hash table
000854 ** in the wal-index file. Set *piZero to one less than the frame
000855 ** number of the first frame indexed by this hash table. If a
000856 ** slot in the hash table is set to N, it refers to frame number
000857 ** (*piZero+N) in the log.
000858 **
000859 ** Finally, set *paPgno so that *paPgno[1] is the page number of the
000860 ** first frame indexed by the hash table, frame (*piZero+1).
000861 */
000862 static int walHashGet(
000863 Wal *pWal, /* WAL handle */
000864 int iHash, /* Find the iHash'th table */
000865 volatile ht_slot **paHash, /* OUT: Pointer to hash index */
000866 volatile u32 **paPgno, /* OUT: Pointer to page number array */
000867 u32 *piZero /* OUT: Frame associated with *paPgno[0] */
000868 ){
000869 int rc; /* Return code */
000870 volatile u32 *aPgno;
000871
000872 rc = walIndexPage(pWal, iHash, &aPgno);
000873 assert( rc==SQLITE_OK || iHash>0 );
000874
000875 if( rc==SQLITE_OK ){
000876 u32 iZero;
000877 volatile ht_slot *aHash;
000878
000879 aHash = (volatile ht_slot *)&aPgno[HASHTABLE_NPAGE];
000880 if( iHash==0 ){
000881 aPgno = &aPgno[WALINDEX_HDR_SIZE/sizeof(u32)];
000882 iZero = 0;
000883 }else{
000884 iZero = HASHTABLE_NPAGE_ONE + (iHash-1)*HASHTABLE_NPAGE;
000885 }
000886
000887 *paPgno = &aPgno[-1];
000888 *paHash = aHash;
000889 *piZero = iZero;
000890 }
000891 return rc;
000892 }
000893
000894 /*
000895 ** Return the number of the wal-index page that contains the hash-table
000896 ** and page-number array that contain entries corresponding to WAL frame
000897 ** iFrame. The wal-index is broken up into 32KB pages. Wal-index pages
000898 ** are numbered starting from 0.
000899 */
000900 static int walFramePage(u32 iFrame){
000901 int iHash = (iFrame+HASHTABLE_NPAGE-HASHTABLE_NPAGE_ONE-1) / HASHTABLE_NPAGE;
000902 assert( (iHash==0 || iFrame>HASHTABLE_NPAGE_ONE)
000903 && (iHash>=1 || iFrame<=HASHTABLE_NPAGE_ONE)
000904 && (iHash<=1 || iFrame>(HASHTABLE_NPAGE_ONE+HASHTABLE_NPAGE))
000905 && (iHash>=2 || iFrame<=HASHTABLE_NPAGE_ONE+HASHTABLE_NPAGE)
000906 && (iHash<=2 || iFrame>(HASHTABLE_NPAGE_ONE+2*HASHTABLE_NPAGE))
000907 );
000908 return iHash;
000909 }
000910
000911 /*
000912 ** Return the page number associated with frame iFrame in this WAL.
000913 */
000914 static u32 walFramePgno(Wal *pWal, u32 iFrame){
000915 int iHash = walFramePage(iFrame);
000916 if( iHash==0 ){
000917 return pWal->apWiData[0][WALINDEX_HDR_SIZE/sizeof(u32) + iFrame - 1];
000918 }
000919 return pWal->apWiData[iHash][(iFrame-1-HASHTABLE_NPAGE_ONE)%HASHTABLE_NPAGE];
000920 }
000921
000922 /*
000923 ** Remove entries from the hash table that point to WAL slots greater
000924 ** than pWal->hdr.mxFrame.
000925 **
000926 ** This function is called whenever pWal->hdr.mxFrame is decreased due
000927 ** to a rollback or savepoint.
000928 **
000929 ** At most only the hash table containing pWal->hdr.mxFrame needs to be
000930 ** updated. Any later hash tables will be automatically cleared when
000931 ** pWal->hdr.mxFrame advances to the point where those hash tables are
000932 ** actually needed.
000933 */
000934 static void walCleanupHash(Wal *pWal){
000935 volatile ht_slot *aHash = 0; /* Pointer to hash table to clear */
000936 volatile u32 *aPgno = 0; /* Page number array for hash table */
000937 u32 iZero = 0; /* frame == (aHash[x]+iZero) */
000938 int iLimit = 0; /* Zero values greater than this */
000939 int nByte; /* Number of bytes to zero in aPgno[] */
000940 int i; /* Used to iterate through aHash[] */
000941
000942 assert( pWal->writeLock );
000943 testcase( pWal->hdr.mxFrame==HASHTABLE_NPAGE_ONE-1 );
000944 testcase( pWal->hdr.mxFrame==HASHTABLE_NPAGE_ONE );
000945 testcase( pWal->hdr.mxFrame==HASHTABLE_NPAGE_ONE+1 );
000946
000947 if( pWal->hdr.mxFrame==0 ) return;
000948
000949 /* Obtain pointers to the hash-table and page-number array containing
000950 ** the entry that corresponds to frame pWal->hdr.mxFrame. It is guaranteed
000951 ** that the page said hash-table and array reside on is already mapped.
000952 */
000953 assert( pWal->nWiData>walFramePage(pWal->hdr.mxFrame) );
000954 assert( pWal->apWiData[walFramePage(pWal->hdr.mxFrame)] );
000955 walHashGet(pWal, walFramePage(pWal->hdr.mxFrame), &aHash, &aPgno, &iZero);
000956
000957 /* Zero all hash-table entries that correspond to frame numbers greater
000958 ** than pWal->hdr.mxFrame.
000959 */
000960 iLimit = pWal->hdr.mxFrame - iZero;
000961 assert( iLimit>0 );
000962 for(i=0; i<HASHTABLE_NSLOT; i++){
000963 if( aHash[i]>iLimit ){
000964 aHash[i] = 0;
000965 }
000966 }
000967
000968 /* Zero the entries in the aPgno array that correspond to frames with
000969 ** frame numbers greater than pWal->hdr.mxFrame.
000970 */
000971 nByte = (int)((char *)aHash - (char *)&aPgno[iLimit+1]);
000972 memset((void *)&aPgno[iLimit+1], 0, nByte);
000973
000974 #ifdef SQLITE_ENABLE_EXPENSIVE_ASSERT
000975 /* Verify that the every entry in the mapping region is still reachable
000976 ** via the hash table even after the cleanup.
000977 */
000978 if( iLimit ){
000979 int j; /* Loop counter */
000980 int iKey; /* Hash key */
000981 for(j=1; j<=iLimit; j++){
000982 for(iKey=walHash(aPgno[j]); aHash[iKey]; iKey=walNextHash(iKey)){
000983 if( aHash[iKey]==j ) break;
000984 }
000985 assert( aHash[iKey]==j );
000986 }
000987 }
000988 #endif /* SQLITE_ENABLE_EXPENSIVE_ASSERT */
000989 }
000990
000991
000992 /*
000993 ** Set an entry in the wal-index that will map database page number
000994 ** pPage into WAL frame iFrame.
000995 */
000996 static int walIndexAppend(Wal *pWal, u32 iFrame, u32 iPage){
000997 int rc; /* Return code */
000998 u32 iZero = 0; /* One less than frame number of aPgno[1] */
000999 volatile u32 *aPgno = 0; /* Page number array */
001000 volatile ht_slot *aHash = 0; /* Hash table */
001001
001002 rc = walHashGet(pWal, walFramePage(iFrame), &aHash, &aPgno, &iZero);
001003
001004 /* Assuming the wal-index file was successfully mapped, populate the
001005 ** page number array and hash table entry.
001006 */
001007 if( rc==SQLITE_OK ){
001008 int iKey; /* Hash table key */
001009 int idx; /* Value to write to hash-table slot */
001010 int nCollide; /* Number of hash collisions */
001011
001012 idx = iFrame - iZero;
001013 assert( idx <= HASHTABLE_NSLOT/2 + 1 );
001014
001015 /* If this is the first entry to be added to this hash-table, zero the
001016 ** entire hash table and aPgno[] array before proceeding.
001017 */
001018 if( idx==1 ){
001019 int nByte = (int)((u8 *)&aHash[HASHTABLE_NSLOT] - (u8 *)&aPgno[1]);
001020 memset((void*)&aPgno[1], 0, nByte);
001021 }
001022
001023 /* If the entry in aPgno[] is already set, then the previous writer
001024 ** must have exited unexpectedly in the middle of a transaction (after
001025 ** writing one or more dirty pages to the WAL to free up memory).
001026 ** Remove the remnants of that writers uncommitted transaction from
001027 ** the hash-table before writing any new entries.
001028 */
001029 if( aPgno[idx] ){
001030 walCleanupHash(pWal);
001031 assert( !aPgno[idx] );
001032 }
001033
001034 /* Write the aPgno[] array entry and the hash-table slot. */
001035 nCollide = idx;
001036 for(iKey=walHash(iPage); aHash[iKey]; iKey=walNextHash(iKey)){
001037 if( (nCollide--)==0 ) return SQLITE_CORRUPT_BKPT;
001038 }
001039 aPgno[idx] = iPage;
001040 aHash[iKey] = (ht_slot)idx;
001041
001042 #ifdef SQLITE_ENABLE_EXPENSIVE_ASSERT
001043 /* Verify that the number of entries in the hash table exactly equals
001044 ** the number of entries in the mapping region.
001045 */
001046 {
001047 int i; /* Loop counter */
001048 int nEntry = 0; /* Number of entries in the hash table */
001049 for(i=0; i<HASHTABLE_NSLOT; i++){ if( aHash[i] ) nEntry++; }
001050 assert( nEntry==idx );
001051 }
001052
001053 /* Verify that the every entry in the mapping region is reachable
001054 ** via the hash table. This turns out to be a really, really expensive
001055 ** thing to check, so only do this occasionally - not on every
001056 ** iteration.
001057 */
001058 if( (idx&0x3ff)==0 ){
001059 int i; /* Loop counter */
001060 for(i=1; i<=idx; i++){
001061 for(iKey=walHash(aPgno[i]); aHash[iKey]; iKey=walNextHash(iKey)){
001062 if( aHash[iKey]==i ) break;
001063 }
001064 assert( aHash[iKey]==i );
001065 }
001066 }
001067 #endif /* SQLITE_ENABLE_EXPENSIVE_ASSERT */
001068 }
001069
001070
001071 return rc;
001072 }
001073
001074
001075 /*
001076 ** Recover the wal-index by reading the write-ahead log file.
001077 **
001078 ** This routine first tries to establish an exclusive lock on the
001079 ** wal-index to prevent other threads/processes from doing anything
001080 ** with the WAL or wal-index while recovery is running. The
001081 ** WAL_RECOVER_LOCK is also held so that other threads will know
001082 ** that this thread is running recovery. If unable to establish
001083 ** the necessary locks, this routine returns SQLITE_BUSY.
001084 */
001085 static int walIndexRecover(Wal *pWal){
001086 int rc; /* Return Code */
001087 i64 nSize; /* Size of log file */
001088 u32 aFrameCksum[2] = {0, 0};
001089 int iLock; /* Lock offset to lock for checkpoint */
001090 int nLock; /* Number of locks to hold */
001091
001092 /* Obtain an exclusive lock on all byte in the locking range not already
001093 ** locked by the caller. The caller is guaranteed to have locked the
001094 ** WAL_WRITE_LOCK byte, and may have also locked the WAL_CKPT_LOCK byte.
001095 ** If successful, the same bytes that are locked here are unlocked before
001096 ** this function returns.
001097 */
001098 assert( pWal->ckptLock==1 || pWal->ckptLock==0 );
001099 assert( WAL_ALL_BUT_WRITE==WAL_WRITE_LOCK+1 );
001100 assert( WAL_CKPT_LOCK==WAL_ALL_BUT_WRITE );
001101 assert( pWal->writeLock );
001102 iLock = WAL_ALL_BUT_WRITE + pWal->ckptLock;
001103 nLock = SQLITE_SHM_NLOCK - iLock;
001104 rc = walLockExclusive(pWal, iLock, nLock);
001105 if( rc ){
001106 return rc;
001107 }
001108 WALTRACE(("WAL%p: recovery begin...\n", pWal));
001109
001110 memset(&pWal->hdr, 0, sizeof(WalIndexHdr));
001111
001112 rc = sqlite3OsFileSize(pWal->pWalFd, &nSize);
001113 if( rc!=SQLITE_OK ){
001114 goto recovery_error;
001115 }
001116
001117 if( nSize>WAL_HDRSIZE ){
001118 u8 aBuf[WAL_HDRSIZE]; /* Buffer to load WAL header into */
001119 u8 *aFrame = 0; /* Malloc'd buffer to load entire frame */
001120 int szFrame; /* Number of bytes in buffer aFrame[] */
001121 u8 *aData; /* Pointer to data part of aFrame buffer */
001122 int iFrame; /* Index of last frame read */
001123 i64 iOffset; /* Next offset to read from log file */
001124 int szPage; /* Page size according to the log */
001125 u32 magic; /* Magic value read from WAL header */
001126 u32 version; /* Magic value read from WAL header */
001127 int isValid; /* True if this frame is valid */
001128
001129 /* Read in the WAL header. */
001130 rc = sqlite3OsRead(pWal->pWalFd, aBuf, WAL_HDRSIZE, 0);
001131 if( rc!=SQLITE_OK ){
001132 goto recovery_error;
001133 }
001134
001135 /* If the database page size is not a power of two, or is greater than
001136 ** SQLITE_MAX_PAGE_SIZE, conclude that the WAL file contains no valid
001137 ** data. Similarly, if the 'magic' value is invalid, ignore the whole
001138 ** WAL file.
001139 */
001140 magic = sqlite3Get4byte(&aBuf[0]);
001141 szPage = sqlite3Get4byte(&aBuf[8]);
001142 if( (magic&0xFFFFFFFE)!=WAL_MAGIC
001143 || szPage&(szPage-1)
001144 || szPage>SQLITE_MAX_PAGE_SIZE
001145 || szPage<512
001146 ){
001147 goto finished;
001148 }
001149 pWal->hdr.bigEndCksum = (u8)(magic&0x00000001);
001150 pWal->szPage = szPage;
001151 pWal->nCkpt = sqlite3Get4byte(&aBuf[12]);
001152 memcpy(&pWal->hdr.aSalt, &aBuf[16], 8);
001153
001154 /* Verify that the WAL header checksum is correct */
001155 walChecksumBytes(pWal->hdr.bigEndCksum==SQLITE_BIGENDIAN,
001156 aBuf, WAL_HDRSIZE-2*4, 0, pWal->hdr.aFrameCksum
001157 );
001158 if( pWal->hdr.aFrameCksum[0]!=sqlite3Get4byte(&aBuf[24])
001159 || pWal->hdr.aFrameCksum[1]!=sqlite3Get4byte(&aBuf[28])
001160 ){
001161 goto finished;
001162 }
001163
001164 /* Verify that the version number on the WAL format is one that
001165 ** are able to understand */
001166 version = sqlite3Get4byte(&aBuf[4]);
001167 if( version!=WAL_MAX_VERSION ){
001168 rc = SQLITE_CANTOPEN_BKPT;
001169 goto finished;
001170 }
001171
001172 /* Malloc a buffer to read frames into. */
001173 szFrame = szPage + WAL_FRAME_HDRSIZE;
001174 aFrame = (u8 *)sqlite3_malloc64(szFrame);
001175 if( !aFrame ){
001176 rc = SQLITE_NOMEM_BKPT;
001177 goto recovery_error;
001178 }
001179 aData = &aFrame[WAL_FRAME_HDRSIZE];
001180
001181 /* Read all frames from the log file. */
001182 iFrame = 0;
001183 for(iOffset=WAL_HDRSIZE; (iOffset+szFrame)<=nSize; iOffset+=szFrame){
001184 u32 pgno; /* Database page number for frame */
001185 u32 nTruncate; /* dbsize field from frame header */
001186
001187 /* Read and decode the next log frame. */
001188 iFrame++;
001189 rc = sqlite3OsRead(pWal->pWalFd, aFrame, szFrame, iOffset);
001190 if( rc!=SQLITE_OK ) break;
001191 isValid = walDecodeFrame(pWal, &pgno, &nTruncate, aData, aFrame);
001192 if( !isValid ) break;
001193 rc = walIndexAppend(pWal, iFrame, pgno);
001194 if( rc!=SQLITE_OK ) break;
001195
001196 /* If nTruncate is non-zero, this is a commit record. */
001197 if( nTruncate ){
001198 pWal->hdr.mxFrame = iFrame;
001199 pWal->hdr.nPage = nTruncate;
001200 pWal->hdr.szPage = (u16)((szPage&0xff00) | (szPage>>16));
001201 testcase( szPage<=32768 );
001202 testcase( szPage>=65536 );
001203 aFrameCksum[0] = pWal->hdr.aFrameCksum[0];
001204 aFrameCksum[1] = pWal->hdr.aFrameCksum[1];
001205 }
001206 }
001207
001208 sqlite3_free(aFrame);
001209 }
001210
001211 finished:
001212 if( rc==SQLITE_OK ){
001213 volatile WalCkptInfo *pInfo;
001214 int i;
001215 pWal->hdr.aFrameCksum[0] = aFrameCksum[0];
001216 pWal->hdr.aFrameCksum[1] = aFrameCksum[1];
001217 walIndexWriteHdr(pWal);
001218
001219 /* Reset the checkpoint-header. This is safe because this thread is
001220 ** currently holding locks that exclude all other readers, writers and
001221 ** checkpointers.
001222 */
001223 pInfo = walCkptInfo(pWal);
001224 pInfo->nBackfill = 0;
001225 pInfo->nBackfillAttempted = pWal->hdr.mxFrame;
001226 pInfo->aReadMark[0] = 0;
001227 for(i=1; i<WAL_NREADER; i++) pInfo->aReadMark[i] = READMARK_NOT_USED;
001228 if( pWal->hdr.mxFrame ) pInfo->aReadMark[1] = pWal->hdr.mxFrame;
001229
001230 /* If more than one frame was recovered from the log file, report an
001231 ** event via sqlite3_log(). This is to help with identifying performance
001232 ** problems caused by applications routinely shutting down without
001233 ** checkpointing the log file.
001234 */
001235 if( pWal->hdr.nPage ){
001236 sqlite3_log(SQLITE_NOTICE_RECOVER_WAL,
001237 "recovered %d frames from WAL file %s",
001238 pWal->hdr.mxFrame, pWal->zWalName
001239 );
001240 }
001241 }
001242
001243 recovery_error:
001244 WALTRACE(("WAL%p: recovery %s\n", pWal, rc ? "failed" : "ok"));
001245 walUnlockExclusive(pWal, iLock, nLock);
001246 return rc;
001247 }
001248
001249 /*
001250 ** Close an open wal-index.
001251 */
001252 static void walIndexClose(Wal *pWal, int isDelete){
001253 if( pWal->exclusiveMode==WAL_HEAPMEMORY_MODE ){
001254 int i;
001255 for(i=0; i<pWal->nWiData; i++){
001256 sqlite3_free((void *)pWal->apWiData[i]);
001257 pWal->apWiData[i] = 0;
001258 }
001259 }else{
001260 sqlite3OsShmUnmap(pWal->pDbFd, isDelete);
001261 }
001262 }
001263
001264 /*
001265 ** Open a connection to the WAL file zWalName. The database file must
001266 ** already be opened on connection pDbFd. The buffer that zWalName points
001267 ** to must remain valid for the lifetime of the returned Wal* handle.
001268 **
001269 ** A SHARED lock should be held on the database file when this function
001270 ** is called. The purpose of this SHARED lock is to prevent any other
001271 ** client from unlinking the WAL or wal-index file. If another process
001272 ** were to do this just after this client opened one of these files, the
001273 ** system would be badly broken.
001274 **
001275 ** If the log file is successfully opened, SQLITE_OK is returned and
001276 ** *ppWal is set to point to a new WAL handle. If an error occurs,
001277 ** an SQLite error code is returned and *ppWal is left unmodified.
001278 */
001279 int sqlite3WalOpen(
001280 sqlite3_vfs *pVfs, /* vfs module to open wal and wal-index */
001281 sqlite3_file *pDbFd, /* The open database file */
001282 const char *zWalName, /* Name of the WAL file */
001283 int bNoShm, /* True to run in heap-memory mode */
001284 i64 mxWalSize, /* Truncate WAL to this size on reset */
001285 Wal **ppWal /* OUT: Allocated Wal handle */
001286 ){
001287 int rc; /* Return Code */
001288 Wal *pRet; /* Object to allocate and return */
001289 int flags; /* Flags passed to OsOpen() */
001290
001291 assert( zWalName && zWalName[0] );
001292 assert( pDbFd );
001293
001294 /* In the amalgamation, the os_unix.c and os_win.c source files come before
001295 ** this source file. Verify that the #defines of the locking byte offsets
001296 ** in os_unix.c and os_win.c agree with the WALINDEX_LOCK_OFFSET value.
001297 ** For that matter, if the lock offset ever changes from its initial design
001298 ** value of 120, we need to know that so there is an assert() to check it.
001299 */
001300 assert( 120==WALINDEX_LOCK_OFFSET );
001301 assert( 136==WALINDEX_HDR_SIZE );
001302 #ifdef WIN_SHM_BASE
001303 assert( WIN_SHM_BASE==WALINDEX_LOCK_OFFSET );
001304 #endif
001305 #ifdef UNIX_SHM_BASE
001306 assert( UNIX_SHM_BASE==WALINDEX_LOCK_OFFSET );
001307 #endif
001308
001309
001310 /* Allocate an instance of struct Wal to return. */
001311 *ppWal = 0;
001312 pRet = (Wal*)sqlite3MallocZero(sizeof(Wal) + pVfs->szOsFile);
001313 if( !pRet ){
001314 return SQLITE_NOMEM_BKPT;
001315 }
001316
001317 pRet->pVfs = pVfs;
001318 pRet->pWalFd = (sqlite3_file *)&pRet[1];
001319 pRet->pDbFd = pDbFd;
001320 pRet->readLock = -1;
001321 pRet->mxWalSize = mxWalSize;
001322 pRet->zWalName = zWalName;
001323 pRet->syncHeader = 1;
001324 pRet->padToSectorBoundary = 1;
001325 pRet->exclusiveMode = (bNoShm ? WAL_HEAPMEMORY_MODE: WAL_NORMAL_MODE);
001326
001327 /* Open file handle on the write-ahead log file. */
001328 flags = (SQLITE_OPEN_READWRITE|SQLITE_OPEN_CREATE|SQLITE_OPEN_WAL);
001329 rc = sqlite3OsOpen(pVfs, zWalName, pRet->pWalFd, flags, &flags);
001330 if( rc==SQLITE_OK && flags&SQLITE_OPEN_READONLY ){
001331 pRet->readOnly = WAL_RDONLY;
001332 }
001333
001334 if( rc!=SQLITE_OK ){
001335 walIndexClose(pRet, 0);
001336 sqlite3OsClose(pRet->pWalFd);
001337 sqlite3_free(pRet);
001338 }else{
001339 int iDC = sqlite3OsDeviceCharacteristics(pDbFd);
001340 if( iDC & SQLITE_IOCAP_SEQUENTIAL ){ pRet->syncHeader = 0; }
001341 if( iDC & SQLITE_IOCAP_POWERSAFE_OVERWRITE ){
001342 pRet->padToSectorBoundary = 0;
001343 }
001344 *ppWal = pRet;
001345 WALTRACE(("WAL%d: opened\n", pRet));
001346 }
001347 return rc;
001348 }
001349
001350 /*
001351 ** Change the size to which the WAL file is trucated on each reset.
001352 */
001353 void sqlite3WalLimit(Wal *pWal, i64 iLimit){
001354 if( pWal ) pWal->mxWalSize = iLimit;
001355 }
001356
001357 /*
001358 ** Find the smallest page number out of all pages held in the WAL that
001359 ** has not been returned by any prior invocation of this method on the
001360 ** same WalIterator object. Write into *piFrame the frame index where
001361 ** that page was last written into the WAL. Write into *piPage the page
001362 ** number.
001363 **
001364 ** Return 0 on success. If there are no pages in the WAL with a page
001365 ** number larger than *piPage, then return 1.
001366 */
001367 static int walIteratorNext(
001368 WalIterator *p, /* Iterator */
001369 u32 *piPage, /* OUT: The page number of the next page */
001370 u32 *piFrame /* OUT: Wal frame index of next page */
001371 ){
001372 u32 iMin; /* Result pgno must be greater than iMin */
001373 u32 iRet = 0xFFFFFFFF; /* 0xffffffff is never a valid page number */
001374 int i; /* For looping through segments */
001375
001376 iMin = p->iPrior;
001377 assert( iMin<0xffffffff );
001378 for(i=p->nSegment-1; i>=0; i--){
001379 struct WalSegment *pSegment = &p->aSegment[i];
001380 while( pSegment->iNext<pSegment->nEntry ){
001381 u32 iPg = pSegment->aPgno[pSegment->aIndex[pSegment->iNext]];
001382 if( iPg>iMin ){
001383 if( iPg<iRet ){
001384 iRet = iPg;
001385 *piFrame = pSegment->iZero + pSegment->aIndex[pSegment->iNext];
001386 }
001387 break;
001388 }
001389 pSegment->iNext++;
001390 }
001391 }
001392
001393 *piPage = p->iPrior = iRet;
001394 return (iRet==0xFFFFFFFF);
001395 }
001396
001397 /*
001398 ** This function merges two sorted lists into a single sorted list.
001399 **
001400 ** aLeft[] and aRight[] are arrays of indices. The sort key is
001401 ** aContent[aLeft[]] and aContent[aRight[]]. Upon entry, the following
001402 ** is guaranteed for all J<K:
001403 **
001404 ** aContent[aLeft[J]] < aContent[aLeft[K]]
001405 ** aContent[aRight[J]] < aContent[aRight[K]]
001406 **
001407 ** This routine overwrites aRight[] with a new (probably longer) sequence
001408 ** of indices such that the aRight[] contains every index that appears in
001409 ** either aLeft[] or the old aRight[] and such that the second condition
001410 ** above is still met.
001411 **
001412 ** The aContent[aLeft[X]] values will be unique for all X. And the
001413 ** aContent[aRight[X]] values will be unique too. But there might be
001414 ** one or more combinations of X and Y such that
001415 **
001416 ** aLeft[X]!=aRight[Y] && aContent[aLeft[X]] == aContent[aRight[Y]]
001417 **
001418 ** When that happens, omit the aLeft[X] and use the aRight[Y] index.
001419 */
001420 static void walMerge(
001421 const u32 *aContent, /* Pages in wal - keys for the sort */
001422 ht_slot *aLeft, /* IN: Left hand input list */
001423 int nLeft, /* IN: Elements in array *paLeft */
001424 ht_slot **paRight, /* IN/OUT: Right hand input list */
001425 int *pnRight, /* IN/OUT: Elements in *paRight */
001426 ht_slot *aTmp /* Temporary buffer */
001427 ){
001428 int iLeft = 0; /* Current index in aLeft */
001429 int iRight = 0; /* Current index in aRight */
001430 int iOut = 0; /* Current index in output buffer */
001431 int nRight = *pnRight;
001432 ht_slot *aRight = *paRight;
001433
001434 assert( nLeft>0 && nRight>0 );
001435 while( iRight<nRight || iLeft<nLeft ){
001436 ht_slot logpage;
001437 Pgno dbpage;
001438
001439 if( (iLeft<nLeft)
001440 && (iRight>=nRight || aContent[aLeft[iLeft]]<aContent[aRight[iRight]])
001441 ){
001442 logpage = aLeft[iLeft++];
001443 }else{
001444 logpage = aRight[iRight++];
001445 }
001446 dbpage = aContent[logpage];
001447
001448 aTmp[iOut++] = logpage;
001449 if( iLeft<nLeft && aContent[aLeft[iLeft]]==dbpage ) iLeft++;
001450
001451 assert( iLeft>=nLeft || aContent[aLeft[iLeft]]>dbpage );
001452 assert( iRight>=nRight || aContent[aRight[iRight]]>dbpage );
001453 }
001454
001455 *paRight = aLeft;
001456 *pnRight = iOut;
001457 memcpy(aLeft, aTmp, sizeof(aTmp[0])*iOut);
001458 }
001459
001460 /*
001461 ** Sort the elements in list aList using aContent[] as the sort key.
001462 ** Remove elements with duplicate keys, preferring to keep the
001463 ** larger aList[] values.
001464 **
001465 ** The aList[] entries are indices into aContent[]. The values in
001466 ** aList[] are to be sorted so that for all J<K:
001467 **
001468 ** aContent[aList[J]] < aContent[aList[K]]
001469 **
001470 ** For any X and Y such that
001471 **
001472 ** aContent[aList[X]] == aContent[aList[Y]]
001473 **
001474 ** Keep the larger of the two values aList[X] and aList[Y] and discard
001475 ** the smaller.
001476 */
001477 static void walMergesort(
001478 const u32 *aContent, /* Pages in wal */
001479 ht_slot *aBuffer, /* Buffer of at least *pnList items to use */
001480 ht_slot *aList, /* IN/OUT: List to sort */
001481 int *pnList /* IN/OUT: Number of elements in aList[] */
001482 ){
001483 struct Sublist {
001484 int nList; /* Number of elements in aList */
001485 ht_slot *aList; /* Pointer to sub-list content */
001486 };
001487
001488 const int nList = *pnList; /* Size of input list */
001489 int nMerge = 0; /* Number of elements in list aMerge */
001490 ht_slot *aMerge = 0; /* List to be merged */
001491 int iList; /* Index into input list */
001492 u32 iSub = 0; /* Index into aSub array */
001493 struct Sublist aSub[13]; /* Array of sub-lists */
001494
001495 memset(aSub, 0, sizeof(aSub));
001496 assert( nList<=HASHTABLE_NPAGE && nList>0 );
001497 assert( HASHTABLE_NPAGE==(1<<(ArraySize(aSub)-1)) );
001498
001499 for(iList=0; iList<nList; iList++){
001500 nMerge = 1;
001501 aMerge = &aList[iList];
001502 for(iSub=0; iList & (1<<iSub); iSub++){
001503 struct Sublist *p;
001504 assert( iSub<ArraySize(aSub) );
001505 p = &aSub[iSub];
001506 assert( p->aList && p->nList<=(1<<iSub) );
001507 assert( p->aList==&aList[iList&~((2<<iSub)-1)] );
001508 walMerge(aContent, p->aList, p->nList, &aMerge, &nMerge, aBuffer);
001509 }
001510 aSub[iSub].aList = aMerge;
001511 aSub[iSub].nList = nMerge;
001512 }
001513
001514 for(iSub++; iSub<ArraySize(aSub); iSub++){
001515 if( nList & (1<<iSub) ){
001516 struct Sublist *p;
001517 assert( iSub<ArraySize(aSub) );
001518 p = &aSub[iSub];
001519 assert( p->nList<=(1<<iSub) );
001520 assert( p->aList==&aList[nList&~((2<<iSub)-1)] );
001521 walMerge(aContent, p->aList, p->nList, &aMerge, &nMerge, aBuffer);
001522 }
001523 }
001524 assert( aMerge==aList );
001525 *pnList = nMerge;
001526
001527 #ifdef SQLITE_DEBUG
001528 {
001529 int i;
001530 for(i=1; i<*pnList; i++){
001531 assert( aContent[aList[i]] > aContent[aList[i-1]] );
001532 }
001533 }
001534 #endif
001535 }
001536
001537 /*
001538 ** Free an iterator allocated by walIteratorInit().
001539 */
001540 static void walIteratorFree(WalIterator *p){
001541 sqlite3_free(p);
001542 }
001543
001544 /*
001545 ** Construct a WalInterator object that can be used to loop over all
001546 ** pages in the WAL in ascending order. The caller must hold the checkpoint
001547 ** lock.
001548 **
001549 ** On success, make *pp point to the newly allocated WalInterator object
001550 ** return SQLITE_OK. Otherwise, return an error code. If this routine
001551 ** returns an error, the value of *pp is undefined.
001552 **
001553 ** The calling routine should invoke walIteratorFree() to destroy the
001554 ** WalIterator object when it has finished with it.
001555 */
001556 static int walIteratorInit(Wal *pWal, WalIterator **pp){
001557 WalIterator *p; /* Return value */
001558 int nSegment; /* Number of segments to merge */
001559 u32 iLast; /* Last frame in log */
001560 int nByte; /* Number of bytes to allocate */
001561 int i; /* Iterator variable */
001562 ht_slot *aTmp; /* Temp space used by merge-sort */
001563 int rc = SQLITE_OK; /* Return Code */
001564
001565 /* This routine only runs while holding the checkpoint lock. And
001566 ** it only runs if there is actually content in the log (mxFrame>0).
001567 */
001568 assert( pWal->ckptLock && pWal->hdr.mxFrame>0 );
001569 iLast = pWal->hdr.mxFrame;
001570
001571 /* Allocate space for the WalIterator object. */
001572 nSegment = walFramePage(iLast) + 1;
001573 nByte = sizeof(WalIterator)
001574 + (nSegment-1)*sizeof(struct WalSegment)
001575 + iLast*sizeof(ht_slot);
001576 p = (WalIterator *)sqlite3_malloc64(nByte);
001577 if( !p ){
001578 return SQLITE_NOMEM_BKPT;
001579 }
001580 memset(p, 0, nByte);
001581 p->nSegment = nSegment;
001582
001583 /* Allocate temporary space used by the merge-sort routine. This block
001584 ** of memory will be freed before this function returns.
001585 */
001586 aTmp = (ht_slot *)sqlite3_malloc64(
001587 sizeof(ht_slot) * (iLast>HASHTABLE_NPAGE?HASHTABLE_NPAGE:iLast)
001588 );
001589 if( !aTmp ){
001590 rc = SQLITE_NOMEM_BKPT;
001591 }
001592
001593 for(i=0; rc==SQLITE_OK && i<nSegment; i++){
001594 volatile ht_slot *aHash;
001595 u32 iZero;
001596 volatile u32 *aPgno;
001597
001598 rc = walHashGet(pWal, i, &aHash, &aPgno, &iZero);
001599 if( rc==SQLITE_OK ){
001600 int j; /* Counter variable */
001601 int nEntry; /* Number of entries in this segment */
001602 ht_slot *aIndex; /* Sorted index for this segment */
001603
001604 aPgno++;
001605 if( (i+1)==nSegment ){
001606 nEntry = (int)(iLast - iZero);
001607 }else{
001608 nEntry = (int)((u32*)aHash - (u32*)aPgno);
001609 }
001610 aIndex = &((ht_slot *)&p->aSegment[p->nSegment])[iZero];
001611 iZero++;
001612
001613 for(j=0; j<nEntry; j++){
001614 aIndex[j] = (ht_slot)j;
001615 }
001616 walMergesort((u32 *)aPgno, aTmp, aIndex, &nEntry);
001617 p->aSegment[i].iZero = iZero;
001618 p->aSegment[i].nEntry = nEntry;
001619 p->aSegment[i].aIndex = aIndex;
001620 p->aSegment[i].aPgno = (u32 *)aPgno;
001621 }
001622 }
001623 sqlite3_free(aTmp);
001624
001625 if( rc!=SQLITE_OK ){
001626 walIteratorFree(p);
001627 }
001628 *pp = p;
001629 return rc;
001630 }
001631
001632 /*
001633 ** Attempt to obtain the exclusive WAL lock defined by parameters lockIdx and
001634 ** n. If the attempt fails and parameter xBusy is not NULL, then it is a
001635 ** busy-handler function. Invoke it and retry the lock until either the
001636 ** lock is successfully obtained or the busy-handler returns 0.
001637 */
001638 static int walBusyLock(
001639 Wal *pWal, /* WAL connection */
001640 int (*xBusy)(void*), /* Function to call when busy */
001641 void *pBusyArg, /* Context argument for xBusyHandler */
001642 int lockIdx, /* Offset of first byte to lock */
001643 int n /* Number of bytes to lock */
001644 ){
001645 int rc;
001646 do {
001647 rc = walLockExclusive(pWal, lockIdx, n);
001648 }while( xBusy && rc==SQLITE_BUSY && xBusy(pBusyArg) );
001649 return rc;
001650 }
001651
001652 /*
001653 ** The cache of the wal-index header must be valid to call this function.
001654 ** Return the page-size in bytes used by the database.
001655 */
001656 static int walPagesize(Wal *pWal){
001657 return (pWal->hdr.szPage&0xfe00) + ((pWal->hdr.szPage&0x0001)<<16);
001658 }
001659
001660 /*
001661 ** The following is guaranteed when this function is called:
001662 **
001663 ** a) the WRITER lock is held,
001664 ** b) the entire log file has been checkpointed, and
001665 ** c) any existing readers are reading exclusively from the database
001666 ** file - there are no readers that may attempt to read a frame from
001667 ** the log file.
001668 **
001669 ** This function updates the shared-memory structures so that the next
001670 ** client to write to the database (which may be this one) does so by
001671 ** writing frames into the start of the log file.
001672 **
001673 ** The value of parameter salt1 is used as the aSalt[1] value in the
001674 ** new wal-index header. It should be passed a pseudo-random value (i.e.
001675 ** one obtained from sqlite3_randomness()).
001676 */
001677 static void walRestartHdr(Wal *pWal, u32 salt1){
001678 volatile WalCkptInfo *pInfo = walCkptInfo(pWal);
001679 int i; /* Loop counter */
001680 u32 *aSalt = pWal->hdr.aSalt; /* Big-endian salt values */
001681 pWal->nCkpt++;
001682 pWal->hdr.mxFrame = 0;
001683 sqlite3Put4byte((u8*)&aSalt[0], 1 + sqlite3Get4byte((u8*)&aSalt[0]));
001684 memcpy(&pWal->hdr.aSalt[1], &salt1, 4);
001685 walIndexWriteHdr(pWal);
001686 pInfo->nBackfill = 0;
001687 pInfo->nBackfillAttempted = 0;
001688 pInfo->aReadMark[1] = 0;
001689 for(i=2; i<WAL_NREADER; i++) pInfo->aReadMark[i] = READMARK_NOT_USED;
001690 assert( pInfo->aReadMark[0]==0 );
001691 }
001692
001693 /*
001694 ** Copy as much content as we can from the WAL back into the database file
001695 ** in response to an sqlite3_wal_checkpoint() request or the equivalent.
001696 **
001697 ** The amount of information copies from WAL to database might be limited
001698 ** by active readers. This routine will never overwrite a database page
001699 ** that a concurrent reader might be using.
001700 **
001701 ** All I/O barrier operations (a.k.a fsyncs) occur in this routine when
001702 ** SQLite is in WAL-mode in synchronous=NORMAL. That means that if
001703 ** checkpoints are always run by a background thread or background
001704 ** process, foreground threads will never block on a lengthy fsync call.
001705 **
001706 ** Fsync is called on the WAL before writing content out of the WAL and
001707 ** into the database. This ensures that if the new content is persistent
001708 ** in the WAL and can be recovered following a power-loss or hard reset.
001709 **
001710 ** Fsync is also called on the database file if (and only if) the entire
001711 ** WAL content is copied into the database file. This second fsync makes
001712 ** it safe to delete the WAL since the new content will persist in the
001713 ** database file.
001714 **
001715 ** This routine uses and updates the nBackfill field of the wal-index header.
001716 ** This is the only routine that will increase the value of nBackfill.
001717 ** (A WAL reset or recovery will revert nBackfill to zero, but not increase
001718 ** its value.)
001719 **
001720 ** The caller must be holding sufficient locks to ensure that no other
001721 ** checkpoint is running (in any other thread or process) at the same
001722 ** time.
001723 */
001724 static int walCheckpoint(
001725 Wal *pWal, /* Wal connection */
001726 sqlite3 *db, /* Check for interrupts on this handle */
001727 int eMode, /* One of PASSIVE, FULL or RESTART */
001728 int (*xBusy)(void*), /* Function to call when busy */
001729 void *pBusyArg, /* Context argument for xBusyHandler */
001730 int sync_flags, /* Flags for OsSync() (or 0) */
001731 u8 *zBuf /* Temporary buffer to use */
001732 ){
001733 int rc = SQLITE_OK; /* Return code */
001734 int szPage; /* Database page-size */
001735 WalIterator *pIter = 0; /* Wal iterator context */
001736 u32 iDbpage = 0; /* Next database page to write */
001737 u32 iFrame = 0; /* Wal frame containing data for iDbpage */
001738 u32 mxSafeFrame; /* Max frame that can be backfilled */
001739 u32 mxPage; /* Max database page to write */
001740 int i; /* Loop counter */
001741 volatile WalCkptInfo *pInfo; /* The checkpoint status information */
001742
001743 szPage = walPagesize(pWal);
001744 testcase( szPage<=32768 );
001745 testcase( szPage>=65536 );
001746 pInfo = walCkptInfo(pWal);
001747 if( pInfo->nBackfill<pWal->hdr.mxFrame ){
001748
001749 /* Allocate the iterator */
001750 rc = walIteratorInit(pWal, &pIter);
001751 if( rc!=SQLITE_OK ){
001752 return rc;
001753 }
001754 assert( pIter );
001755
001756 /* EVIDENCE-OF: R-62920-47450 The busy-handler callback is never invoked
001757 ** in the SQLITE_CHECKPOINT_PASSIVE mode. */
001758 assert( eMode!=SQLITE_CHECKPOINT_PASSIVE || xBusy==0 );
001759
001760 /* Compute in mxSafeFrame the index of the last frame of the WAL that is
001761 ** safe to write into the database. Frames beyond mxSafeFrame might
001762 ** overwrite database pages that are in use by active readers and thus
001763 ** cannot be backfilled from the WAL.
001764 */
001765 mxSafeFrame = pWal->hdr.mxFrame;
001766 mxPage = pWal->hdr.nPage;
001767 for(i=1; i<WAL_NREADER; i++){
001768 /* Thread-sanitizer reports that the following is an unsafe read,
001769 ** as some other thread may be in the process of updating the value
001770 ** of the aReadMark[] slot. The assumption here is that if that is
001771 ** happening, the other client may only be increasing the value,
001772 ** not decreasing it. So assuming either that either the "old" or
001773 ** "new" version of the value is read, and not some arbitrary value
001774 ** that would never be written by a real client, things are still
001775 ** safe. */
001776 u32 y = pInfo->aReadMark[i];
001777 if( mxSafeFrame>y ){
001778 assert( y<=pWal->hdr.mxFrame );
001779 rc = walBusyLock(pWal, xBusy, pBusyArg, WAL_READ_LOCK(i), 1);
001780 if( rc==SQLITE_OK ){
001781 pInfo->aReadMark[i] = (i==1 ? mxSafeFrame : READMARK_NOT_USED);
001782 walUnlockExclusive(pWal, WAL_READ_LOCK(i), 1);
001783 }else if( rc==SQLITE_BUSY ){
001784 mxSafeFrame = y;
001785 xBusy = 0;
001786 }else{
001787 goto walcheckpoint_out;
001788 }
001789 }
001790 }
001791
001792 if( pInfo->nBackfill<mxSafeFrame
001793 && (rc = walBusyLock(pWal, xBusy, pBusyArg, WAL_READ_LOCK(0),1))==SQLITE_OK
001794 ){
001795 i64 nSize; /* Current size of database file */
001796 u32 nBackfill = pInfo->nBackfill;
001797
001798 pInfo->nBackfillAttempted = mxSafeFrame;
001799
001800 /* Sync the WAL to disk */
001801 if( sync_flags ){
001802 rc = sqlite3OsSync(pWal->pWalFd, sync_flags);
001803 }
001804
001805 /* If the database may grow as a result of this checkpoint, hint
001806 ** about the eventual size of the db file to the VFS layer.
001807 */
001808 if( rc==SQLITE_OK ){
001809 i64 nReq = ((i64)mxPage * szPage);
001810 rc = sqlite3OsFileSize(pWal->pDbFd, &nSize);
001811 if( rc==SQLITE_OK && nSize<nReq ){
001812 sqlite3OsFileControlHint(pWal->pDbFd, SQLITE_FCNTL_SIZE_HINT, &nReq);
001813 }
001814 }
001815
001816
001817 /* Iterate through the contents of the WAL, copying data to the db file */
001818 while( rc==SQLITE_OK && 0==walIteratorNext(pIter, &iDbpage, &iFrame) ){
001819 i64 iOffset;
001820 assert( walFramePgno(pWal, iFrame)==iDbpage );
001821 if( db->u1.isInterrupted ){
001822 rc = db->mallocFailed ? SQLITE_NOMEM_BKPT : SQLITE_INTERRUPT;
001823 break;
001824 }
001825 if( iFrame<=nBackfill || iFrame>mxSafeFrame || iDbpage>mxPage ){
001826 continue;
001827 }
001828 iOffset = walFrameOffset(iFrame, szPage) + WAL_FRAME_HDRSIZE;
001829 /* testcase( IS_BIG_INT(iOffset) ); // requires a 4GiB WAL file */
001830 rc = sqlite3OsRead(pWal->pWalFd, zBuf, szPage, iOffset);
001831 if( rc!=SQLITE_OK ) break;
001832 iOffset = (iDbpage-1)*(i64)szPage;
001833 testcase( IS_BIG_INT(iOffset) );
001834 rc = sqlite3OsWrite(pWal->pDbFd, zBuf, szPage, iOffset);
001835 if( rc!=SQLITE_OK ) break;
001836 }
001837
001838 /* If work was actually accomplished... */
001839 if( rc==SQLITE_OK ){
001840 if( mxSafeFrame==walIndexHdr(pWal)->mxFrame ){
001841 i64 szDb = pWal->hdr.nPage*(i64)szPage;
001842 testcase( IS_BIG_INT(szDb) );
001843 rc = sqlite3OsTruncate(pWal->pDbFd, szDb);
001844 if( rc==SQLITE_OK && sync_flags ){
001845 rc = sqlite3OsSync(pWal->pDbFd, sync_flags);
001846 }
001847 }
001848 if( rc==SQLITE_OK ){
001849 pInfo->nBackfill = mxSafeFrame;
001850 }
001851 }
001852
001853 /* Release the reader lock held while backfilling */
001854 walUnlockExclusive(pWal, WAL_READ_LOCK(0), 1);
001855 }
001856
001857 if( rc==SQLITE_BUSY ){
001858 /* Reset the return code so as not to report a checkpoint failure
001859 ** just because there are active readers. */
001860 rc = SQLITE_OK;
001861 }
001862 }
001863
001864 /* If this is an SQLITE_CHECKPOINT_RESTART or TRUNCATE operation, and the
001865 ** entire wal file has been copied into the database file, then block
001866 ** until all readers have finished using the wal file. This ensures that
001867 ** the next process to write to the database restarts the wal file.
001868 */
001869 if( rc==SQLITE_OK && eMode!=SQLITE_CHECKPOINT_PASSIVE ){
001870 assert( pWal->writeLock );
001871 if( pInfo->nBackfill<pWal->hdr.mxFrame ){
001872 rc = SQLITE_BUSY;
001873 }else if( eMode>=SQLITE_CHECKPOINT_RESTART ){
001874 u32 salt1;
001875 sqlite3_randomness(4, &salt1);
001876 assert( pInfo->nBackfill==pWal->hdr.mxFrame );
001877 rc = walBusyLock(pWal, xBusy, pBusyArg, WAL_READ_LOCK(1), WAL_NREADER-1);
001878 if( rc==SQLITE_OK ){
001879 if( eMode==SQLITE_CHECKPOINT_TRUNCATE ){
001880 /* IMPLEMENTATION-OF: R-44699-57140 This mode works the same way as
001881 ** SQLITE_CHECKPOINT_RESTART with the addition that it also
001882 ** truncates the log file to zero bytes just prior to a
001883 ** successful return.
001884 **
001885 ** In theory, it might be safe to do this without updating the
001886 ** wal-index header in shared memory, as all subsequent reader or
001887 ** writer clients should see that the entire log file has been
001888 ** checkpointed and behave accordingly. This seems unsafe though,
001889 ** as it would leave the system in a state where the contents of
001890 ** the wal-index header do not match the contents of the
001891 ** file-system. To avoid this, update the wal-index header to
001892 ** indicate that the log file contains zero valid frames. */
001893 walRestartHdr(pWal, salt1);
001894 rc = sqlite3OsTruncate(pWal->pWalFd, 0);
001895 }
001896 walUnlockExclusive(pWal, WAL_READ_LOCK(1), WAL_NREADER-1);
001897 }
001898 }
001899 }
001900
001901 walcheckpoint_out:
001902 walIteratorFree(pIter);
001903 return rc;
001904 }
001905
001906 /*
001907 ** If the WAL file is currently larger than nMax bytes in size, truncate
001908 ** it to exactly nMax bytes. If an error occurs while doing so, ignore it.
001909 */
001910 static void walLimitSize(Wal *pWal, i64 nMax){
001911 i64 sz;
001912 int rx;
001913 sqlite3BeginBenignMalloc();
001914 rx = sqlite3OsFileSize(pWal->pWalFd, &sz);
001915 if( rx==SQLITE_OK && (sz > nMax ) ){
001916 rx = sqlite3OsTruncate(pWal->pWalFd, nMax);
001917 }
001918 sqlite3EndBenignMalloc();
001919 if( rx ){
001920 sqlite3_log(rx, "cannot limit WAL size: %s", pWal->zWalName);
001921 }
001922 }
001923
001924 /*
001925 ** Close a connection to a log file.
001926 */
001927 int sqlite3WalClose(
001928 Wal *pWal, /* Wal to close */
001929 sqlite3 *db, /* For interrupt flag */
001930 int sync_flags, /* Flags to pass to OsSync() (or 0) */
001931 int nBuf,
001932 u8 *zBuf /* Buffer of at least nBuf bytes */
001933 ){
001934 int rc = SQLITE_OK;
001935 if( pWal ){
001936 int isDelete = 0; /* True to unlink wal and wal-index files */
001937
001938 /* If an EXCLUSIVE lock can be obtained on the database file (using the
001939 ** ordinary, rollback-mode locking methods, this guarantees that the
001940 ** connection associated with this log file is the only connection to
001941 ** the database. In this case checkpoint the database and unlink both
001942 ** the wal and wal-index files.
001943 **
001944 ** The EXCLUSIVE lock is not released before returning.
001945 */
001946 if( zBuf!=0
001947 && SQLITE_OK==(rc = sqlite3OsLock(pWal->pDbFd, SQLITE_LOCK_EXCLUSIVE))
001948 ){
001949 if( pWal->exclusiveMode==WAL_NORMAL_MODE ){
001950 pWal->exclusiveMode = WAL_EXCLUSIVE_MODE;
001951 }
001952 rc = sqlite3WalCheckpoint(pWal, db,
001953 SQLITE_CHECKPOINT_PASSIVE, 0, 0, sync_flags, nBuf, zBuf, 0, 0
001954 );
001955 if( rc==SQLITE_OK ){
001956 int bPersist = -1;
001957 sqlite3OsFileControlHint(
001958 pWal->pDbFd, SQLITE_FCNTL_PERSIST_WAL, &bPersist
001959 );
001960 if( bPersist!=1 ){
001961 /* Try to delete the WAL file if the checkpoint completed and
001962 ** fsyned (rc==SQLITE_OK) and if we are not in persistent-wal
001963 ** mode (!bPersist) */
001964 isDelete = 1;
001965 }else if( pWal->mxWalSize>=0 ){
001966 /* Try to truncate the WAL file to zero bytes if the checkpoint
001967 ** completed and fsynced (rc==SQLITE_OK) and we are in persistent
001968 ** WAL mode (bPersist) and if the PRAGMA journal_size_limit is a
001969 ** non-negative value (pWal->mxWalSize>=0). Note that we truncate
001970 ** to zero bytes as truncating to the journal_size_limit might
001971 ** leave a corrupt WAL file on disk. */
001972 walLimitSize(pWal, 0);
001973 }
001974 }
001975 }
001976
001977 walIndexClose(pWal, isDelete);
001978 sqlite3OsClose(pWal->pWalFd);
001979 if( isDelete ){
001980 sqlite3BeginBenignMalloc();
001981 sqlite3OsDelete(pWal->pVfs, pWal->zWalName, 0);
001982 sqlite3EndBenignMalloc();
001983 }
001984 WALTRACE(("WAL%p: closed\n", pWal));
001985 sqlite3_free((void *)pWal->apWiData);
001986 sqlite3_free(pWal);
001987 }
001988 return rc;
001989 }
001990
001991 /*
001992 ** Try to read the wal-index header. Return 0 on success and 1 if
001993 ** there is a problem.
001994 **
001995 ** The wal-index is in shared memory. Another thread or process might
001996 ** be writing the header at the same time this procedure is trying to
001997 ** read it, which might result in inconsistency. A dirty read is detected
001998 ** by verifying that both copies of the header are the same and also by
001999 ** a checksum on the header.
002000 **
002001 ** If and only if the read is consistent and the header is different from
002002 ** pWal->hdr, then pWal->hdr is updated to the content of the new header
002003 ** and *pChanged is set to 1.
002004 **
002005 ** If the checksum cannot be verified return non-zero. If the header
002006 ** is read successfully and the checksum verified, return zero.
002007 */
002008 static int walIndexTryHdr(Wal *pWal, int *pChanged){
002009 u32 aCksum[2]; /* Checksum on the header content */
002010 WalIndexHdr h1, h2; /* Two copies of the header content */
002011 WalIndexHdr volatile *aHdr; /* Header in shared memory */
002012
002013 /* The first page of the wal-index must be mapped at this point. */
002014 assert( pWal->nWiData>0 && pWal->apWiData[0] );
002015
002016 /* Read the header. This might happen concurrently with a write to the
002017 ** same area of shared memory on a different CPU in a SMP,
002018 ** meaning it is possible that an inconsistent snapshot is read
002019 ** from the file. If this happens, return non-zero.
002020 **
002021 ** There are two copies of the header at the beginning of the wal-index.
002022 ** When reading, read [0] first then [1]. Writes are in the reverse order.
002023 ** Memory barriers are used to prevent the compiler or the hardware from
002024 ** reordering the reads and writes.
002025 */
002026 aHdr = walIndexHdr(pWal);
002027 memcpy(&h1, (void *)&aHdr[0], sizeof(h1));
002028 walShmBarrier(pWal);
002029 memcpy(&h2, (void *)&aHdr[1], sizeof(h2));
002030
002031 if( memcmp(&h1, &h2, sizeof(h1))!=0 ){
002032 return 1; /* Dirty read */
002033 }
002034 if( h1.isInit==0 ){
002035 return 1; /* Malformed header - probably all zeros */
002036 }
002037 walChecksumBytes(1, (u8*)&h1, sizeof(h1)-sizeof(h1.aCksum), 0, aCksum);
002038 if( aCksum[0]!=h1.aCksum[0] || aCksum[1]!=h1.aCksum[1] ){
002039 return 1; /* Checksum does not match */
002040 }
002041
002042 if( memcmp(&pWal->hdr, &h1, sizeof(WalIndexHdr)) ){
002043 *pChanged = 1;
002044 memcpy(&pWal->hdr, &h1, sizeof(WalIndexHdr));
002045 pWal->szPage = (pWal->hdr.szPage&0xfe00) + ((pWal->hdr.szPage&0x0001)<<16);
002046 testcase( pWal->szPage<=32768 );
002047 testcase( pWal->szPage>=65536 );
002048 }
002049
002050 /* The header was successfully read. Return zero. */
002051 return 0;
002052 }
002053
002054 /*
002055 ** Read the wal-index header from the wal-index and into pWal->hdr.
002056 ** If the wal-header appears to be corrupt, try to reconstruct the
002057 ** wal-index from the WAL before returning.
002058 **
002059 ** Set *pChanged to 1 if the wal-index header value in pWal->hdr is
002060 ** changed by this operation. If pWal->hdr is unchanged, set *pChanged
002061 ** to 0.
002062 **
002063 ** If the wal-index header is successfully read, return SQLITE_OK.
002064 ** Otherwise an SQLite error code.
002065 */
002066 static int walIndexReadHdr(Wal *pWal, int *pChanged){
002067 int rc; /* Return code */
002068 int badHdr; /* True if a header read failed */
002069 volatile u32 *page0; /* Chunk of wal-index containing header */
002070
002071 /* Ensure that page 0 of the wal-index (the page that contains the
002072 ** wal-index header) is mapped. Return early if an error occurs here.
002073 */
002074 assert( pChanged );
002075 rc = walIndexPage(pWal, 0, &page0);
002076 if( rc!=SQLITE_OK ){
002077 return rc;
002078 };
002079 assert( page0 || pWal->writeLock==0 );
002080
002081 /* If the first page of the wal-index has been mapped, try to read the
002082 ** wal-index header immediately, without holding any lock. This usually
002083 ** works, but may fail if the wal-index header is corrupt or currently
002084 ** being modified by another thread or process.
002085 */
002086 badHdr = (page0 ? walIndexTryHdr(pWal, pChanged) : 1);
002087
002088 /* If the first attempt failed, it might have been due to a race
002089 ** with a writer. So get a WRITE lock and try again.
002090 */
002091 assert( badHdr==0 || pWal->writeLock==0 );
002092 if( badHdr ){
002093 if( pWal->readOnly & WAL_SHM_RDONLY ){
002094 if( SQLITE_OK==(rc = walLockShared(pWal, WAL_WRITE_LOCK)) ){
002095 walUnlockShared(pWal, WAL_WRITE_LOCK);
002096 rc = SQLITE_READONLY_RECOVERY;
002097 }
002098 }else if( SQLITE_OK==(rc = walLockExclusive(pWal, WAL_WRITE_LOCK, 1)) ){
002099 pWal->writeLock = 1;
002100 if( SQLITE_OK==(rc = walIndexPage(pWal, 0, &page0)) ){
002101 badHdr = walIndexTryHdr(pWal, pChanged);
002102 if( badHdr ){
002103 /* If the wal-index header is still malformed even while holding
002104 ** a WRITE lock, it can only mean that the header is corrupted and
002105 ** needs to be reconstructed. So run recovery to do exactly that.
002106 */
002107 rc = walIndexRecover(pWal);
002108 *pChanged = 1;
002109 }
002110 }
002111 pWal->writeLock = 0;
002112 walUnlockExclusive(pWal, WAL_WRITE_LOCK, 1);
002113 }
002114 }
002115
002116 /* If the header is read successfully, check the version number to make
002117 ** sure the wal-index was not constructed with some future format that
002118 ** this version of SQLite cannot understand.
002119 */
002120 if( badHdr==0 && pWal->hdr.iVersion!=WALINDEX_MAX_VERSION ){
002121 rc = SQLITE_CANTOPEN_BKPT;
002122 }
002123
002124 return rc;
002125 }
002126
002127 /*
002128 ** This is the value that walTryBeginRead returns when it needs to
002129 ** be retried.
002130 */
002131 #define WAL_RETRY (-1)
002132
002133 /*
002134 ** Attempt to start a read transaction. This might fail due to a race or
002135 ** other transient condition. When that happens, it returns WAL_RETRY to
002136 ** indicate to the caller that it is safe to retry immediately.
002137 **
002138 ** On success return SQLITE_OK. On a permanent failure (such an
002139 ** I/O error or an SQLITE_BUSY because another process is running
002140 ** recovery) return a positive error code.
002141 **
002142 ** The useWal parameter is true to force the use of the WAL and disable
002143 ** the case where the WAL is bypassed because it has been completely
002144 ** checkpointed. If useWal==0 then this routine calls walIndexReadHdr()
002145 ** to make a copy of the wal-index header into pWal->hdr. If the
002146 ** wal-index header has changed, *pChanged is set to 1 (as an indication
002147 ** to the caller that the local paget cache is obsolete and needs to be
002148 ** flushed.) When useWal==1, the wal-index header is assumed to already
002149 ** be loaded and the pChanged parameter is unused.
002150 **
002151 ** The caller must set the cnt parameter to the number of prior calls to
002152 ** this routine during the current read attempt that returned WAL_RETRY.
002153 ** This routine will start taking more aggressive measures to clear the
002154 ** race conditions after multiple WAL_RETRY returns, and after an excessive
002155 ** number of errors will ultimately return SQLITE_PROTOCOL. The
002156 ** SQLITE_PROTOCOL return indicates that some other process has gone rogue
002157 ** and is not honoring the locking protocol. There is a vanishingly small
002158 ** chance that SQLITE_PROTOCOL could be returned because of a run of really
002159 ** bad luck when there is lots of contention for the wal-index, but that
002160 ** possibility is so small that it can be safely neglected, we believe.
002161 **
002162 ** On success, this routine obtains a read lock on
002163 ** WAL_READ_LOCK(pWal->readLock). The pWal->readLock integer is
002164 ** in the range 0 <= pWal->readLock < WAL_NREADER. If pWal->readLock==(-1)
002165 ** that means the Wal does not hold any read lock. The reader must not
002166 ** access any database page that is modified by a WAL frame up to and
002167 ** including frame number aReadMark[pWal->readLock]. The reader will
002168 ** use WAL frames up to and including pWal->hdr.mxFrame if pWal->readLock>0
002169 ** Or if pWal->readLock==0, then the reader will ignore the WAL
002170 ** completely and get all content directly from the database file.
002171 ** If the useWal parameter is 1 then the WAL will never be ignored and
002172 ** this routine will always set pWal->readLock>0 on success.
002173 ** When the read transaction is completed, the caller must release the
002174 ** lock on WAL_READ_LOCK(pWal->readLock) and set pWal->readLock to -1.
002175 **
002176 ** This routine uses the nBackfill and aReadMark[] fields of the header
002177 ** to select a particular WAL_READ_LOCK() that strives to let the
002178 ** checkpoint process do as much work as possible. This routine might
002179 ** update values of the aReadMark[] array in the header, but if it does
002180 ** so it takes care to hold an exclusive lock on the corresponding
002181 ** WAL_READ_LOCK() while changing values.
002182 */
002183 static int walTryBeginRead(Wal *pWal, int *pChanged, int useWal, int cnt){
002184 volatile WalCkptInfo *pInfo; /* Checkpoint information in wal-index */
002185 u32 mxReadMark; /* Largest aReadMark[] value */
002186 int mxI; /* Index of largest aReadMark[] value */
002187 int i; /* Loop counter */
002188 int rc = SQLITE_OK; /* Return code */
002189 u32 mxFrame; /* Wal frame to lock to */
002190
002191 assert( pWal->readLock<0 ); /* Not currently locked */
002192
002193 /* Take steps to avoid spinning forever if there is a protocol error.
002194 **
002195 ** Circumstances that cause a RETRY should only last for the briefest
002196 ** instances of time. No I/O or other system calls are done while the
002197 ** locks are held, so the locks should not be held for very long. But
002198 ** if we are unlucky, another process that is holding a lock might get
002199 ** paged out or take a page-fault that is time-consuming to resolve,
002200 ** during the few nanoseconds that it is holding the lock. In that case,
002201 ** it might take longer than normal for the lock to free.
002202 **
002203 ** After 5 RETRYs, we begin calling sqlite3OsSleep(). The first few
002204 ** calls to sqlite3OsSleep() have a delay of 1 microsecond. Really this
002205 ** is more of a scheduler yield than an actual delay. But on the 10th
002206 ** an subsequent retries, the delays start becoming longer and longer,
002207 ** so that on the 100th (and last) RETRY we delay for 323 milliseconds.
002208 ** The total delay time before giving up is less than 10 seconds.
002209 */
002210 if( cnt>5 ){
002211 int nDelay = 1; /* Pause time in microseconds */
002212 if( cnt>100 ){
002213 VVA_ONLY( pWal->lockError = 1; )
002214 return SQLITE_PROTOCOL;
002215 }
002216 if( cnt>=10 ) nDelay = (cnt-9)*(cnt-9)*39;
002217 sqlite3OsSleep(pWal->pVfs, nDelay);
002218 }
002219
002220 if( !useWal ){
002221 rc = walIndexReadHdr(pWal, pChanged);
002222 if( rc==SQLITE_BUSY ){
002223 /* If there is not a recovery running in another thread or process
002224 ** then convert BUSY errors to WAL_RETRY. If recovery is known to
002225 ** be running, convert BUSY to BUSY_RECOVERY. There is a race here
002226 ** which might cause WAL_RETRY to be returned even if BUSY_RECOVERY
002227 ** would be technically correct. But the race is benign since with
002228 ** WAL_RETRY this routine will be called again and will probably be
002229 ** right on the second iteration.
002230 */
002231 if( pWal->apWiData[0]==0 ){
002232 /* This branch is taken when the xShmMap() method returns SQLITE_BUSY.
002233 ** We assume this is a transient condition, so return WAL_RETRY. The
002234 ** xShmMap() implementation used by the default unix and win32 VFS
002235 ** modules may return SQLITE_BUSY due to a race condition in the
002236 ** code that determines whether or not the shared-memory region
002237 ** must be zeroed before the requested page is returned.
002238 */
002239 rc = WAL_RETRY;
002240 }else if( SQLITE_OK==(rc = walLockShared(pWal, WAL_RECOVER_LOCK)) ){
002241 walUnlockShared(pWal, WAL_RECOVER_LOCK);
002242 rc = WAL_RETRY;
002243 }else if( rc==SQLITE_BUSY ){
002244 rc = SQLITE_BUSY_RECOVERY;
002245 }
002246 }
002247 if( rc!=SQLITE_OK ){
002248 return rc;
002249 }
002250 }
002251
002252 pInfo = walCkptInfo(pWal);
002253 if( !useWal && pInfo->nBackfill==pWal->hdr.mxFrame
002254 #ifdef SQLITE_ENABLE_SNAPSHOT
002255 && (pWal->pSnapshot==0 || pWal->hdr.mxFrame==0
002256 || 0==memcmp(&pWal->hdr, pWal->pSnapshot, sizeof(WalIndexHdr)))
002257 #endif
002258 ){
002259 /* The WAL has been completely backfilled (or it is empty).
002260 ** and can be safely ignored.
002261 */
002262 rc = walLockShared(pWal, WAL_READ_LOCK(0));
002263 walShmBarrier(pWal);
002264 if( rc==SQLITE_OK ){
002265 if( memcmp((void *)walIndexHdr(pWal), &pWal->hdr, sizeof(WalIndexHdr)) ){
002266 /* It is not safe to allow the reader to continue here if frames
002267 ** may have been appended to the log before READ_LOCK(0) was obtained.
002268 ** When holding READ_LOCK(0), the reader ignores the entire log file,
002269 ** which implies that the database file contains a trustworthy
002270 ** snapshot. Since holding READ_LOCK(0) prevents a checkpoint from
002271 ** happening, this is usually correct.
002272 **
002273 ** However, if frames have been appended to the log (or if the log
002274 ** is wrapped and written for that matter) before the READ_LOCK(0)
002275 ** is obtained, that is not necessarily true. A checkpointer may
002276 ** have started to backfill the appended frames but crashed before
002277 ** it finished. Leaving a corrupt image in the database file.
002278 */
002279 walUnlockShared(pWal, WAL_READ_LOCK(0));
002280 return WAL_RETRY;
002281 }
002282 pWal->readLock = 0;
002283 return SQLITE_OK;
002284 }else if( rc!=SQLITE_BUSY ){
002285 return rc;
002286 }
002287 }
002288
002289 /* If we get this far, it means that the reader will want to use
002290 ** the WAL to get at content from recent commits. The job now is
002291 ** to select one of the aReadMark[] entries that is closest to
002292 ** but not exceeding pWal->hdr.mxFrame and lock that entry.
002293 */
002294 mxReadMark = 0;
002295 mxI = 0;
002296 mxFrame = pWal->hdr.mxFrame;
002297 #ifdef SQLITE_ENABLE_SNAPSHOT
002298 if( pWal->pSnapshot && pWal->pSnapshot->mxFrame<mxFrame ){
002299 mxFrame = pWal->pSnapshot->mxFrame;
002300 }
002301 #endif
002302 for(i=1; i<WAL_NREADER; i++){
002303 u32 thisMark = pInfo->aReadMark[i];
002304 if( mxReadMark<=thisMark && thisMark<=mxFrame ){
002305 assert( thisMark!=READMARK_NOT_USED );
002306 mxReadMark = thisMark;
002307 mxI = i;
002308 }
002309 }
002310 if( (pWal->readOnly & WAL_SHM_RDONLY)==0
002311 && (mxReadMark<mxFrame || mxI==0)
002312 ){
002313 for(i=1; i<WAL_NREADER; i++){
002314 rc = walLockExclusive(pWal, WAL_READ_LOCK(i), 1);
002315 if( rc==SQLITE_OK ){
002316 mxReadMark = pInfo->aReadMark[i] = mxFrame;
002317 mxI = i;
002318 walUnlockExclusive(pWal, WAL_READ_LOCK(i), 1);
002319 break;
002320 }else if( rc!=SQLITE_BUSY ){
002321 return rc;
002322 }
002323 }
002324 }
002325 if( mxI==0 ){
002326 assert( rc==SQLITE_BUSY || (pWal->readOnly & WAL_SHM_RDONLY)!=0 );
002327 return rc==SQLITE_BUSY ? WAL_RETRY : SQLITE_READONLY_CANTLOCK;
002328 }
002329
002330 rc = walLockShared(pWal, WAL_READ_LOCK(mxI));
002331 if( rc ){
002332 return rc==SQLITE_BUSY ? WAL_RETRY : rc;
002333 }
002334 /* Now that the read-lock has been obtained, check that neither the
002335 ** value in the aReadMark[] array or the contents of the wal-index
002336 ** header have changed.
002337 **
002338 ** It is necessary to check that the wal-index header did not change
002339 ** between the time it was read and when the shared-lock was obtained
002340 ** on WAL_READ_LOCK(mxI) was obtained to account for the possibility
002341 ** that the log file may have been wrapped by a writer, or that frames
002342 ** that occur later in the log than pWal->hdr.mxFrame may have been
002343 ** copied into the database by a checkpointer. If either of these things
002344 ** happened, then reading the database with the current value of
002345 ** pWal->hdr.mxFrame risks reading a corrupted snapshot. So, retry
002346 ** instead.
002347 **
002348 ** Before checking that the live wal-index header has not changed
002349 ** since it was read, set Wal.minFrame to the first frame in the wal
002350 ** file that has not yet been checkpointed. This client will not need
002351 ** to read any frames earlier than minFrame from the wal file - they
002352 ** can be safely read directly from the database file.
002353 **
002354 ** Because a ShmBarrier() call is made between taking the copy of
002355 ** nBackfill and checking that the wal-header in shared-memory still
002356 ** matches the one cached in pWal->hdr, it is guaranteed that the
002357 ** checkpointer that set nBackfill was not working with a wal-index
002358 ** header newer than that cached in pWal->hdr. If it were, that could
002359 ** cause a problem. The checkpointer could omit to checkpoint
002360 ** a version of page X that lies before pWal->minFrame (call that version
002361 ** A) on the basis that there is a newer version (version B) of the same
002362 ** page later in the wal file. But if version B happens to like past
002363 ** frame pWal->hdr.mxFrame - then the client would incorrectly assume
002364 ** that it can read version A from the database file. However, since
002365 ** we can guarantee that the checkpointer that set nBackfill could not
002366 ** see any pages past pWal->hdr.mxFrame, this problem does not come up.
002367 */
002368 pWal->minFrame = pInfo->nBackfill+1;
002369 walShmBarrier(pWal);
002370 if( pInfo->aReadMark[mxI]!=mxReadMark
002371 || memcmp((void *)walIndexHdr(pWal), &pWal->hdr, sizeof(WalIndexHdr))
002372 ){
002373 walUnlockShared(pWal, WAL_READ_LOCK(mxI));
002374 return WAL_RETRY;
002375 }else{
002376 assert( mxReadMark<=pWal->hdr.mxFrame );
002377 pWal->readLock = (i16)mxI;
002378 }
002379 return rc;
002380 }
002381
002382 #ifdef SQLITE_ENABLE_SNAPSHOT
002383 /*
002384 ** Attempt to reduce the value of the WalCkptInfo.nBackfillAttempted
002385 ** variable so that older snapshots can be accessed. To do this, loop
002386 ** through all wal frames from nBackfillAttempted to (nBackfill+1),
002387 ** comparing their content to the corresponding page with the database
002388 ** file, if any. Set nBackfillAttempted to the frame number of the
002389 ** first frame for which the wal file content matches the db file.
002390 **
002391 ** This is only really safe if the file-system is such that any page
002392 ** writes made by earlier checkpointers were atomic operations, which
002393 ** is not always true. It is also possible that nBackfillAttempted
002394 ** may be left set to a value larger than expected, if a wal frame
002395 ** contains content that duplicate of an earlier version of the same
002396 ** page.
002397 **
002398 ** SQLITE_OK is returned if successful, or an SQLite error code if an
002399 ** error occurs. It is not an error if nBackfillAttempted cannot be
002400 ** decreased at all.
002401 */
002402 int sqlite3WalSnapshotRecover(Wal *pWal){
002403 int rc;
002404
002405 assert( pWal->readLock>=0 );
002406 rc = walLockExclusive(pWal, WAL_CKPT_LOCK, 1);
002407 if( rc==SQLITE_OK ){
002408 volatile WalCkptInfo *pInfo = walCkptInfo(pWal);
002409 int szPage = (int)pWal->szPage;
002410 i64 szDb; /* Size of db file in bytes */
002411
002412 rc = sqlite3OsFileSize(pWal->pDbFd, &szDb);
002413 if( rc==SQLITE_OK ){
002414 void *pBuf1 = sqlite3_malloc(szPage);
002415 void *pBuf2 = sqlite3_malloc(szPage);
002416 if( pBuf1==0 || pBuf2==0 ){
002417 rc = SQLITE_NOMEM;
002418 }else{
002419 u32 i = pInfo->nBackfillAttempted;
002420 for(i=pInfo->nBackfillAttempted; i>pInfo->nBackfill; i--){
002421 volatile ht_slot *dummy;
002422 volatile u32 *aPgno; /* Array of page numbers */
002423 u32 iZero; /* Frame corresponding to aPgno[0] */
002424 u32 pgno; /* Page number in db file */
002425 i64 iDbOff; /* Offset of db file entry */
002426 i64 iWalOff; /* Offset of wal file entry */
002427
002428 rc = walHashGet(pWal, walFramePage(i), &dummy, &aPgno, &iZero);
002429 if( rc!=SQLITE_OK ) break;
002430 pgno = aPgno[i-iZero];
002431 iDbOff = (i64)(pgno-1) * szPage;
002432
002433 if( iDbOff+szPage<=szDb ){
002434 iWalOff = walFrameOffset(i, szPage) + WAL_FRAME_HDRSIZE;
002435 rc = sqlite3OsRead(pWal->pWalFd, pBuf1, szPage, iWalOff);
002436
002437 if( rc==SQLITE_OK ){
002438 rc = sqlite3OsRead(pWal->pDbFd, pBuf2, szPage, iDbOff);
002439 }
002440
002441 if( rc!=SQLITE_OK || 0==memcmp(pBuf1, pBuf2, szPage) ){
002442 break;
002443 }
002444 }
002445
002446 pInfo->nBackfillAttempted = i-1;
002447 }
002448 }
002449
002450 sqlite3_free(pBuf1);
002451 sqlite3_free(pBuf2);
002452 }
002453 walUnlockExclusive(pWal, WAL_CKPT_LOCK, 1);
002454 }
002455
002456 return rc;
002457 }
002458 #endif /* SQLITE_ENABLE_SNAPSHOT */
002459
002460 /*
002461 ** Begin a read transaction on the database.
002462 **
002463 ** This routine used to be called sqlite3OpenSnapshot() and with good reason:
002464 ** it takes a snapshot of the state of the WAL and wal-index for the current
002465 ** instant in time. The current thread will continue to use this snapshot.
002466 ** Other threads might append new content to the WAL and wal-index but
002467 ** that extra content is ignored by the current thread.
002468 **
002469 ** If the database contents have changes since the previous read
002470 ** transaction, then *pChanged is set to 1 before returning. The
002471 ** Pager layer will use this to know that is cache is stale and
002472 ** needs to be flushed.
002473 */
002474 int sqlite3WalBeginReadTransaction(Wal *pWal, int *pChanged){
002475 int rc; /* Return code */
002476 int cnt = 0; /* Number of TryBeginRead attempts */
002477
002478 #ifdef SQLITE_ENABLE_SNAPSHOT
002479 int bChanged = 0;
002480 WalIndexHdr *pSnapshot = pWal->pSnapshot;
002481 if( pSnapshot && memcmp(pSnapshot, &pWal->hdr, sizeof(WalIndexHdr))!=0 ){
002482 bChanged = 1;
002483 }
002484 #endif
002485
002486 do{
002487 rc = walTryBeginRead(pWal, pChanged, 0, ++cnt);
002488 }while( rc==WAL_RETRY );
002489 testcase( (rc&0xff)==SQLITE_BUSY );
002490 testcase( (rc&0xff)==SQLITE_IOERR );
002491 testcase( rc==SQLITE_PROTOCOL );
002492 testcase( rc==SQLITE_OK );
002493
002494 #ifdef SQLITE_ENABLE_SNAPSHOT
002495 if( rc==SQLITE_OK ){
002496 if( pSnapshot && memcmp(pSnapshot, &pWal->hdr, sizeof(WalIndexHdr))!=0 ){
002497 /* At this point the client has a lock on an aReadMark[] slot holding
002498 ** a value equal to or smaller than pSnapshot->mxFrame, but pWal->hdr
002499 ** is populated with the wal-index header corresponding to the head
002500 ** of the wal file. Verify that pSnapshot is still valid before
002501 ** continuing. Reasons why pSnapshot might no longer be valid:
002502 **
002503 ** (1) The WAL file has been reset since the snapshot was taken.
002504 ** In this case, the salt will have changed.
002505 **
002506 ** (2) A checkpoint as been attempted that wrote frames past
002507 ** pSnapshot->mxFrame into the database file. Note that the
002508 ** checkpoint need not have completed for this to cause problems.
002509 */
002510 volatile WalCkptInfo *pInfo = walCkptInfo(pWal);
002511
002512 assert( pWal->readLock>0 || pWal->hdr.mxFrame==0 );
002513 assert( pInfo->aReadMark[pWal->readLock]<=pSnapshot->mxFrame );
002514
002515 /* It is possible that there is a checkpointer thread running
002516 ** concurrent with this code. If this is the case, it may be that the
002517 ** checkpointer has already determined that it will checkpoint
002518 ** snapshot X, where X is later in the wal file than pSnapshot, but
002519 ** has not yet set the pInfo->nBackfillAttempted variable to indicate
002520 ** its intent. To avoid the race condition this leads to, ensure that
002521 ** there is no checkpointer process by taking a shared CKPT lock
002522 ** before checking pInfo->nBackfillAttempted.
002523 **
002524 ** TODO: Does the aReadMark[] lock prevent a checkpointer from doing
002525 ** this already?
002526 */
002527 rc = walLockShared(pWal, WAL_CKPT_LOCK);
002528
002529 if( rc==SQLITE_OK ){
002530 /* Check that the wal file has not been wrapped. Assuming that it has
002531 ** not, also check that no checkpointer has attempted to checkpoint any
002532 ** frames beyond pSnapshot->mxFrame. If either of these conditions are
002533 ** true, return SQLITE_BUSY_SNAPSHOT. Otherwise, overwrite pWal->hdr
002534 ** with *pSnapshot and set *pChanged as appropriate for opening the
002535 ** snapshot. */
002536 if( !memcmp(pSnapshot->aSalt, pWal->hdr.aSalt, sizeof(pWal->hdr.aSalt))
002537 && pSnapshot->mxFrame>=pInfo->nBackfillAttempted
002538 ){
002539 assert( pWal->readLock>0 );
002540 memcpy(&pWal->hdr, pSnapshot, sizeof(WalIndexHdr));
002541 *pChanged = bChanged;
002542 }else{
002543 rc = SQLITE_BUSY_SNAPSHOT;
002544 }
002545
002546 /* Release the shared CKPT lock obtained above. */
002547 walUnlockShared(pWal, WAL_CKPT_LOCK);
002548 }
002549
002550
002551 if( rc!=SQLITE_OK ){
002552 sqlite3WalEndReadTransaction(pWal);
002553 }
002554 }
002555 }
002556 #endif
002557 return rc;
002558 }
002559
002560 /*
002561 ** Finish with a read transaction. All this does is release the
002562 ** read-lock.
002563 */
002564 void sqlite3WalEndReadTransaction(Wal *pWal){
002565 sqlite3WalEndWriteTransaction(pWal);
002566 if( pWal->readLock>=0 ){
002567 walUnlockShared(pWal, WAL_READ_LOCK(pWal->readLock));
002568 pWal->readLock = -1;
002569 }
002570 }
002571
002572 /*
002573 ** Search the wal file for page pgno. If found, set *piRead to the frame that
002574 ** contains the page. Otherwise, if pgno is not in the wal file, set *piRead
002575 ** to zero.
002576 **
002577 ** Return SQLITE_OK if successful, or an error code if an error occurs. If an
002578 ** error does occur, the final value of *piRead is undefined.
002579 */
002580 int sqlite3WalFindFrame(
002581 Wal *pWal, /* WAL handle */
002582 Pgno pgno, /* Database page number to read data for */
002583 u32 *piRead /* OUT: Frame number (or zero) */
002584 ){
002585 u32 iRead = 0; /* If !=0, WAL frame to return data from */
002586 u32 iLast = pWal->hdr.mxFrame; /* Last page in WAL for this reader */
002587 int iHash; /* Used to loop through N hash tables */
002588 int iMinHash;
002589
002590 /* This routine is only be called from within a read transaction. */
002591 assert( pWal->readLock>=0 || pWal->lockError );
002592
002593 /* If the "last page" field of the wal-index header snapshot is 0, then
002594 ** no data will be read from the wal under any circumstances. Return early
002595 ** in this case as an optimization. Likewise, if pWal->readLock==0,
002596 ** then the WAL is ignored by the reader so return early, as if the
002597 ** WAL were empty.
002598 */
002599 if( iLast==0 || pWal->readLock==0 ){
002600 *piRead = 0;
002601 return SQLITE_OK;
002602 }
002603
002604 /* Search the hash table or tables for an entry matching page number
002605 ** pgno. Each iteration of the following for() loop searches one
002606 ** hash table (each hash table indexes up to HASHTABLE_NPAGE frames).
002607 **
002608 ** This code might run concurrently to the code in walIndexAppend()
002609 ** that adds entries to the wal-index (and possibly to this hash
002610 ** table). This means the value just read from the hash
002611 ** slot (aHash[iKey]) may have been added before or after the
002612 ** current read transaction was opened. Values added after the
002613 ** read transaction was opened may have been written incorrectly -
002614 ** i.e. these slots may contain garbage data. However, we assume
002615 ** that any slots written before the current read transaction was
002616 ** opened remain unmodified.
002617 **
002618 ** For the reasons above, the if(...) condition featured in the inner
002619 ** loop of the following block is more stringent that would be required
002620 ** if we had exclusive access to the hash-table:
002621 **
002622 ** (aPgno[iFrame]==pgno):
002623 ** This condition filters out normal hash-table collisions.
002624 **
002625 ** (iFrame<=iLast):
002626 ** This condition filters out entries that were added to the hash
002627 ** table after the current read-transaction had started.
002628 */
002629 iMinHash = walFramePage(pWal->minFrame);
002630 for(iHash=walFramePage(iLast); iHash>=iMinHash && iRead==0; iHash--){
002631 volatile ht_slot *aHash; /* Pointer to hash table */
002632 volatile u32 *aPgno; /* Pointer to array of page numbers */
002633 u32 iZero; /* Frame number corresponding to aPgno[0] */
002634 int iKey; /* Hash slot index */
002635 int nCollide; /* Number of hash collisions remaining */
002636 int rc; /* Error code */
002637
002638 rc = walHashGet(pWal, iHash, &aHash, &aPgno, &iZero);
002639 if( rc!=SQLITE_OK ){
002640 return rc;
002641 }
002642 nCollide = HASHTABLE_NSLOT;
002643 for(iKey=walHash(pgno); aHash[iKey]; iKey=walNextHash(iKey)){
002644 u32 iFrame = aHash[iKey] + iZero;
002645 if( iFrame<=iLast && iFrame>=pWal->minFrame && aPgno[aHash[iKey]]==pgno ){
002646 assert( iFrame>iRead || CORRUPT_DB );
002647 iRead = iFrame;
002648 }
002649 if( (nCollide--)==0 ){
002650 return SQLITE_CORRUPT_BKPT;
002651 }
002652 }
002653 }
002654
002655 #ifdef SQLITE_ENABLE_EXPENSIVE_ASSERT
002656 /* If expensive assert() statements are available, do a linear search
002657 ** of the wal-index file content. Make sure the results agree with the
002658 ** result obtained using the hash indexes above. */
002659 {
002660 u32 iRead2 = 0;
002661 u32 iTest;
002662 assert( pWal->minFrame>0 );
002663 for(iTest=iLast; iTest>=pWal->minFrame; iTest--){
002664 if( walFramePgno(pWal, iTest)==pgno ){
002665 iRead2 = iTest;
002666 break;
002667 }
002668 }
002669 assert( iRead==iRead2 );
002670 }
002671 #endif
002672
002673 *piRead = iRead;
002674 return SQLITE_OK;
002675 }
002676
002677 /*
002678 ** Read the contents of frame iRead from the wal file into buffer pOut
002679 ** (which is nOut bytes in size). Return SQLITE_OK if successful, or an
002680 ** error code otherwise.
002681 */
002682 int sqlite3WalReadFrame(
002683 Wal *pWal, /* WAL handle */
002684 u32 iRead, /* Frame to read */
002685 int nOut, /* Size of buffer pOut in bytes */
002686 u8 *pOut /* Buffer to write page data to */
002687 ){
002688 int sz;
002689 i64 iOffset;
002690 sz = pWal->hdr.szPage;
002691 sz = (sz&0xfe00) + ((sz&0x0001)<<16);
002692 testcase( sz<=32768 );
002693 testcase( sz>=65536 );
002694 iOffset = walFrameOffset(iRead, sz) + WAL_FRAME_HDRSIZE;
002695 /* testcase( IS_BIG_INT(iOffset) ); // requires a 4GiB WAL */
002696 return sqlite3OsRead(pWal->pWalFd, pOut, (nOut>sz ? sz : nOut), iOffset);
002697 }
002698
002699 /*
002700 ** Return the size of the database in pages (or zero, if unknown).
002701 */
002702 Pgno sqlite3WalDbsize(Wal *pWal){
002703 if( pWal && ALWAYS(pWal->readLock>=0) ){
002704 return pWal->hdr.nPage;
002705 }
002706 return 0;
002707 }
002708
002709
002710 /*
002711 ** This function starts a write transaction on the WAL.
002712 **
002713 ** A read transaction must have already been started by a prior call
002714 ** to sqlite3WalBeginReadTransaction().
002715 **
002716 ** If another thread or process has written into the database since
002717 ** the read transaction was started, then it is not possible for this
002718 ** thread to write as doing so would cause a fork. So this routine
002719 ** returns SQLITE_BUSY in that case and no write transaction is started.
002720 **
002721 ** There can only be a single writer active at a time.
002722 */
002723 int sqlite3WalBeginWriteTransaction(Wal *pWal){
002724 int rc;
002725
002726 /* Cannot start a write transaction without first holding a read
002727 ** transaction. */
002728 assert( pWal->readLock>=0 );
002729 assert( pWal->writeLock==0 && pWal->iReCksum==0 );
002730
002731 if( pWal->readOnly ){
002732 return SQLITE_READONLY;
002733 }
002734
002735 /* Only one writer allowed at a time. Get the write lock. Return
002736 ** SQLITE_BUSY if unable.
002737 */
002738 rc = walLockExclusive(pWal, WAL_WRITE_LOCK, 1);
002739 if( rc ){
002740 return rc;
002741 }
002742 pWal->writeLock = 1;
002743
002744 /* If another connection has written to the database file since the
002745 ** time the read transaction on this connection was started, then
002746 ** the write is disallowed.
002747 */
002748 if( memcmp(&pWal->hdr, (void *)walIndexHdr(pWal), sizeof(WalIndexHdr))!=0 ){
002749 walUnlockExclusive(pWal, WAL_WRITE_LOCK, 1);
002750 pWal->writeLock = 0;
002751 rc = SQLITE_BUSY_SNAPSHOT;
002752 }
002753
002754 return rc;
002755 }
002756
002757 /*
002758 ** End a write transaction. The commit has already been done. This
002759 ** routine merely releases the lock.
002760 */
002761 int sqlite3WalEndWriteTransaction(Wal *pWal){
002762 if( pWal->writeLock ){
002763 walUnlockExclusive(pWal, WAL_WRITE_LOCK, 1);
002764 pWal->writeLock = 0;
002765 pWal->iReCksum = 0;
002766 pWal->truncateOnCommit = 0;
002767 }
002768 return SQLITE_OK;
002769 }
002770
002771 /*
002772 ** If any data has been written (but not committed) to the log file, this
002773 ** function moves the write-pointer back to the start of the transaction.
002774 **
002775 ** Additionally, the callback function is invoked for each frame written
002776 ** to the WAL since the start of the transaction. If the callback returns
002777 ** other than SQLITE_OK, it is not invoked again and the error code is
002778 ** returned to the caller.
002779 **
002780 ** Otherwise, if the callback function does not return an error, this
002781 ** function returns SQLITE_OK.
002782 */
002783 int sqlite3WalUndo(Wal *pWal, int (*xUndo)(void *, Pgno), void *pUndoCtx){
002784 int rc = SQLITE_OK;
002785 if( ALWAYS(pWal->writeLock) ){
002786 Pgno iMax = pWal->hdr.mxFrame;
002787 Pgno iFrame;
002788
002789 /* Restore the clients cache of the wal-index header to the state it
002790 ** was in before the client began writing to the database.
002791 */
002792 memcpy(&pWal->hdr, (void *)walIndexHdr(pWal), sizeof(WalIndexHdr));
002793
002794 for(iFrame=pWal->hdr.mxFrame+1;
002795 ALWAYS(rc==SQLITE_OK) && iFrame<=iMax;
002796 iFrame++
002797 ){
002798 /* This call cannot fail. Unless the page for which the page number
002799 ** is passed as the second argument is (a) in the cache and
002800 ** (b) has an outstanding reference, then xUndo is either a no-op
002801 ** (if (a) is false) or simply expels the page from the cache (if (b)
002802 ** is false).
002803 **
002804 ** If the upper layer is doing a rollback, it is guaranteed that there
002805 ** are no outstanding references to any page other than page 1. And
002806 ** page 1 is never written to the log until the transaction is
002807 ** committed. As a result, the call to xUndo may not fail.
002808 */
002809 assert( walFramePgno(pWal, iFrame)!=1 );
002810 rc = xUndo(pUndoCtx, walFramePgno(pWal, iFrame));
002811 }
002812 if( iMax!=pWal->hdr.mxFrame ) walCleanupHash(pWal);
002813 }
002814 return rc;
002815 }
002816
002817 /*
002818 ** Argument aWalData must point to an array of WAL_SAVEPOINT_NDATA u32
002819 ** values. This function populates the array with values required to
002820 ** "rollback" the write position of the WAL handle back to the current
002821 ** point in the event of a savepoint rollback (via WalSavepointUndo()).
002822 */
002823 void sqlite3WalSavepoint(Wal *pWal, u32 *aWalData){
002824 assert( pWal->writeLock );
002825 aWalData[0] = pWal->hdr.mxFrame;
002826 aWalData[1] = pWal->hdr.aFrameCksum[0];
002827 aWalData[2] = pWal->hdr.aFrameCksum[1];
002828 aWalData[3] = pWal->nCkpt;
002829 }
002830
002831 /*
002832 ** Move the write position of the WAL back to the point identified by
002833 ** the values in the aWalData[] array. aWalData must point to an array
002834 ** of WAL_SAVEPOINT_NDATA u32 values that has been previously populated
002835 ** by a call to WalSavepoint().
002836 */
002837 int sqlite3WalSavepointUndo(Wal *pWal, u32 *aWalData){
002838 int rc = SQLITE_OK;
002839
002840 assert( pWal->writeLock );
002841 assert( aWalData[3]!=pWal->nCkpt || aWalData[0]<=pWal->hdr.mxFrame );
002842
002843 if( aWalData[3]!=pWal->nCkpt ){
002844 /* This savepoint was opened immediately after the write-transaction
002845 ** was started. Right after that, the writer decided to wrap around
002846 ** to the start of the log. Update the savepoint values to match.
002847 */
002848 aWalData[0] = 0;
002849 aWalData[3] = pWal->nCkpt;
002850 }
002851
002852 if( aWalData[0]<pWal->hdr.mxFrame ){
002853 pWal->hdr.mxFrame = aWalData[0];
002854 pWal->hdr.aFrameCksum[0] = aWalData[1];
002855 pWal->hdr.aFrameCksum[1] = aWalData[2];
002856 walCleanupHash(pWal);
002857 }
002858
002859 return rc;
002860 }
002861
002862 /*
002863 ** This function is called just before writing a set of frames to the log
002864 ** file (see sqlite3WalFrames()). It checks to see if, instead of appending
002865 ** to the current log file, it is possible to overwrite the start of the
002866 ** existing log file with the new frames (i.e. "reset" the log). If so,
002867 ** it sets pWal->hdr.mxFrame to 0. Otherwise, pWal->hdr.mxFrame is left
002868 ** unchanged.
002869 **
002870 ** SQLITE_OK is returned if no error is encountered (regardless of whether
002871 ** or not pWal->hdr.mxFrame is modified). An SQLite error code is returned
002872 ** if an error occurs.
002873 */
002874 static int walRestartLog(Wal *pWal){
002875 int rc = SQLITE_OK;
002876 int cnt;
002877
002878 if( pWal->readLock==0 ){
002879 volatile WalCkptInfo *pInfo = walCkptInfo(pWal);
002880 assert( pInfo->nBackfill==pWal->hdr.mxFrame );
002881 if( pInfo->nBackfill>0 ){
002882 u32 salt1;
002883 sqlite3_randomness(4, &salt1);
002884 rc = walLockExclusive(pWal, WAL_READ_LOCK(1), WAL_NREADER-1);
002885 if( rc==SQLITE_OK ){
002886 /* If all readers are using WAL_READ_LOCK(0) (in other words if no
002887 ** readers are currently using the WAL), then the transactions
002888 ** frames will overwrite the start of the existing log. Update the
002889 ** wal-index header to reflect this.
002890 **
002891 ** In theory it would be Ok to update the cache of the header only
002892 ** at this point. But updating the actual wal-index header is also
002893 ** safe and means there is no special case for sqlite3WalUndo()
002894 ** to handle if this transaction is rolled back. */
002895 walRestartHdr(pWal, salt1);
002896 walUnlockExclusive(pWal, WAL_READ_LOCK(1), WAL_NREADER-1);
002897 }else if( rc!=SQLITE_BUSY ){
002898 return rc;
002899 }
002900 }
002901 walUnlockShared(pWal, WAL_READ_LOCK(0));
002902 pWal->readLock = -1;
002903 cnt = 0;
002904 do{
002905 int notUsed;
002906 rc = walTryBeginRead(pWal, ¬Used, 1, ++cnt);
002907 }while( rc==WAL_RETRY );
002908 assert( (rc&0xff)!=SQLITE_BUSY ); /* BUSY not possible when useWal==1 */
002909 testcase( (rc&0xff)==SQLITE_IOERR );
002910 testcase( rc==SQLITE_PROTOCOL );
002911 testcase( rc==SQLITE_OK );
002912 }
002913 return rc;
002914 }
002915
002916 /*
002917 ** Information about the current state of the WAL file and where
002918 ** the next fsync should occur - passed from sqlite3WalFrames() into
002919 ** walWriteToLog().
002920 */
002921 typedef struct WalWriter {
002922 Wal *pWal; /* The complete WAL information */
002923 sqlite3_file *pFd; /* The WAL file to which we write */
002924 sqlite3_int64 iSyncPoint; /* Fsync at this offset */
002925 int syncFlags; /* Flags for the fsync */
002926 int szPage; /* Size of one page */
002927 } WalWriter;
002928
002929 /*
002930 ** Write iAmt bytes of content into the WAL file beginning at iOffset.
002931 ** Do a sync when crossing the p->iSyncPoint boundary.
002932 **
002933 ** In other words, if iSyncPoint is in between iOffset and iOffset+iAmt,
002934 ** first write the part before iSyncPoint, then sync, then write the
002935 ** rest.
002936 */
002937 static int walWriteToLog(
002938 WalWriter *p, /* WAL to write to */
002939 void *pContent, /* Content to be written */
002940 int iAmt, /* Number of bytes to write */
002941 sqlite3_int64 iOffset /* Start writing at this offset */
002942 ){
002943 int rc;
002944 if( iOffset<p->iSyncPoint && iOffset+iAmt>=p->iSyncPoint ){
002945 int iFirstAmt = (int)(p->iSyncPoint - iOffset);
002946 rc = sqlite3OsWrite(p->pFd, pContent, iFirstAmt, iOffset);
002947 if( rc ) return rc;
002948 iOffset += iFirstAmt;
002949 iAmt -= iFirstAmt;
002950 pContent = (void*)(iFirstAmt + (char*)pContent);
002951 assert( p->syncFlags & (SQLITE_SYNC_NORMAL|SQLITE_SYNC_FULL) );
002952 rc = sqlite3OsSync(p->pFd, p->syncFlags & SQLITE_SYNC_MASK);
002953 if( iAmt==0 || rc ) return rc;
002954 }
002955 rc = sqlite3OsWrite(p->pFd, pContent, iAmt, iOffset);
002956 return rc;
002957 }
002958
002959 /*
002960 ** Write out a single frame of the WAL
002961 */
002962 static int walWriteOneFrame(
002963 WalWriter *p, /* Where to write the frame */
002964 PgHdr *pPage, /* The page of the frame to be written */
002965 int nTruncate, /* The commit flag. Usually 0. >0 for commit */
002966 sqlite3_int64 iOffset /* Byte offset at which to write */
002967 ){
002968 int rc; /* Result code from subfunctions */
002969 void *pData; /* Data actually written */
002970 u8 aFrame[WAL_FRAME_HDRSIZE]; /* Buffer to assemble frame-header in */
002971 #if defined(SQLITE_HAS_CODEC)
002972 if( (pData = sqlite3PagerCodec(pPage))==0 ) return SQLITE_NOMEM_BKPT;
002973 #else
002974 pData = pPage->pData;
002975 #endif
002976 walEncodeFrame(p->pWal, pPage->pgno, nTruncate, pData, aFrame);
002977 rc = walWriteToLog(p, aFrame, sizeof(aFrame), iOffset);
002978 if( rc ) return rc;
002979 /* Write the page data */
002980 rc = walWriteToLog(p, pData, p->szPage, iOffset+sizeof(aFrame));
002981 return rc;
002982 }
002983
002984 /*
002985 ** This function is called as part of committing a transaction within which
002986 ** one or more frames have been overwritten. It updates the checksums for
002987 ** all frames written to the wal file by the current transaction starting
002988 ** with the earliest to have been overwritten.
002989 **
002990 ** SQLITE_OK is returned if successful, or an SQLite error code otherwise.
002991 */
002992 static int walRewriteChecksums(Wal *pWal, u32 iLast){
002993 const int szPage = pWal->szPage;/* Database page size */
002994 int rc = SQLITE_OK; /* Return code */
002995 u8 *aBuf; /* Buffer to load data from wal file into */
002996 u8 aFrame[WAL_FRAME_HDRSIZE]; /* Buffer to assemble frame-headers in */
002997 u32 iRead; /* Next frame to read from wal file */
002998 i64 iCksumOff;
002999
003000 aBuf = sqlite3_malloc(szPage + WAL_FRAME_HDRSIZE);
003001 if( aBuf==0 ) return SQLITE_NOMEM_BKPT;
003002
003003 /* Find the checksum values to use as input for the recalculating the
003004 ** first checksum. If the first frame is frame 1 (implying that the current
003005 ** transaction restarted the wal file), these values must be read from the
003006 ** wal-file header. Otherwise, read them from the frame header of the
003007 ** previous frame. */
003008 assert( pWal->iReCksum>0 );
003009 if( pWal->iReCksum==1 ){
003010 iCksumOff = 24;
003011 }else{
003012 iCksumOff = walFrameOffset(pWal->iReCksum-1, szPage) + 16;
003013 }
003014 rc = sqlite3OsRead(pWal->pWalFd, aBuf, sizeof(u32)*2, iCksumOff);
003015 pWal->hdr.aFrameCksum[0] = sqlite3Get4byte(aBuf);
003016 pWal->hdr.aFrameCksum[1] = sqlite3Get4byte(&aBuf[sizeof(u32)]);
003017
003018 iRead = pWal->iReCksum;
003019 pWal->iReCksum = 0;
003020 for(; rc==SQLITE_OK && iRead<=iLast; iRead++){
003021 i64 iOff = walFrameOffset(iRead, szPage);
003022 rc = sqlite3OsRead(pWal->pWalFd, aBuf, szPage+WAL_FRAME_HDRSIZE, iOff);
003023 if( rc==SQLITE_OK ){
003024 u32 iPgno, nDbSize;
003025 iPgno = sqlite3Get4byte(aBuf);
003026 nDbSize = sqlite3Get4byte(&aBuf[4]);
003027
003028 walEncodeFrame(pWal, iPgno, nDbSize, &aBuf[WAL_FRAME_HDRSIZE], aFrame);
003029 rc = sqlite3OsWrite(pWal->pWalFd, aFrame, sizeof(aFrame), iOff);
003030 }
003031 }
003032
003033 sqlite3_free(aBuf);
003034 return rc;
003035 }
003036
003037 /*
003038 ** Write a set of frames to the log. The caller must hold the write-lock
003039 ** on the log file (obtained using sqlite3WalBeginWriteTransaction()).
003040 */
003041 int sqlite3WalFrames(
003042 Wal *pWal, /* Wal handle to write to */
003043 int szPage, /* Database page-size in bytes */
003044 PgHdr *pList, /* List of dirty pages to write */
003045 Pgno nTruncate, /* Database size after this commit */
003046 int isCommit, /* True if this is a commit */
003047 int sync_flags /* Flags to pass to OsSync() (or 0) */
003048 ){
003049 int rc; /* Used to catch return codes */
003050 u32 iFrame; /* Next frame address */
003051 PgHdr *p; /* Iterator to run through pList with. */
003052 PgHdr *pLast = 0; /* Last frame in list */
003053 int nExtra = 0; /* Number of extra copies of last page */
003054 int szFrame; /* The size of a single frame */
003055 i64 iOffset; /* Next byte to write in WAL file */
003056 WalWriter w; /* The writer */
003057 u32 iFirst = 0; /* First frame that may be overwritten */
003058 WalIndexHdr *pLive; /* Pointer to shared header */
003059
003060 assert( pList );
003061 assert( pWal->writeLock );
003062
003063 /* If this frame set completes a transaction, then nTruncate>0. If
003064 ** nTruncate==0 then this frame set does not complete the transaction. */
003065 assert( (isCommit!=0)==(nTruncate!=0) );
003066
003067 #if defined(SQLITE_TEST) && defined(SQLITE_DEBUG)
003068 { int cnt; for(cnt=0, p=pList; p; p=p->pDirty, cnt++){}
003069 WALTRACE(("WAL%p: frame write begin. %d frames. mxFrame=%d. %s\n",
003070 pWal, cnt, pWal->hdr.mxFrame, isCommit ? "Commit" : "Spill"));
003071 }
003072 #endif
003073
003074 pLive = (WalIndexHdr*)walIndexHdr(pWal);
003075 if( memcmp(&pWal->hdr, (void *)pLive, sizeof(WalIndexHdr))!=0 ){
003076 iFirst = pLive->mxFrame+1;
003077 }
003078
003079 /* See if it is possible to write these frames into the start of the
003080 ** log file, instead of appending to it at pWal->hdr.mxFrame.
003081 */
003082 if( SQLITE_OK!=(rc = walRestartLog(pWal)) ){
003083 return rc;
003084 }
003085
003086 /* If this is the first frame written into the log, write the WAL
003087 ** header to the start of the WAL file. See comments at the top of
003088 ** this source file for a description of the WAL header format.
003089 */
003090 iFrame = pWal->hdr.mxFrame;
003091 if( iFrame==0 ){
003092 u8 aWalHdr[WAL_HDRSIZE]; /* Buffer to assemble wal-header in */
003093 u32 aCksum[2]; /* Checksum for wal-header */
003094
003095 sqlite3Put4byte(&aWalHdr[0], (WAL_MAGIC | SQLITE_BIGENDIAN));
003096 sqlite3Put4byte(&aWalHdr[4], WAL_MAX_VERSION);
003097 sqlite3Put4byte(&aWalHdr[8], szPage);
003098 sqlite3Put4byte(&aWalHdr[12], pWal->nCkpt);
003099 if( pWal->nCkpt==0 ) sqlite3_randomness(8, pWal->hdr.aSalt);
003100 memcpy(&aWalHdr[16], pWal->hdr.aSalt, 8);
003101 walChecksumBytes(1, aWalHdr, WAL_HDRSIZE-2*4, 0, aCksum);
003102 sqlite3Put4byte(&aWalHdr[24], aCksum[0]);
003103 sqlite3Put4byte(&aWalHdr[28], aCksum[1]);
003104
003105 pWal->szPage = szPage;
003106 pWal->hdr.bigEndCksum = SQLITE_BIGENDIAN;
003107 pWal->hdr.aFrameCksum[0] = aCksum[0];
003108 pWal->hdr.aFrameCksum[1] = aCksum[1];
003109 pWal->truncateOnCommit = 1;
003110
003111 rc = sqlite3OsWrite(pWal->pWalFd, aWalHdr, sizeof(aWalHdr), 0);
003112 WALTRACE(("WAL%p: wal-header write %s\n", pWal, rc ? "failed" : "ok"));
003113 if( rc!=SQLITE_OK ){
003114 return rc;
003115 }
003116
003117 /* Sync the header (unless SQLITE_IOCAP_SEQUENTIAL is true or unless
003118 ** all syncing is turned off by PRAGMA synchronous=OFF). Otherwise
003119 ** an out-of-order write following a WAL restart could result in
003120 ** database corruption. See the ticket:
003121 **
003122 ** http://localhost:591/sqlite/info/ff5be73dee
003123 */
003124 if( pWal->syncHeader && sync_flags ){
003125 rc = sqlite3OsSync(pWal->pWalFd, sync_flags & SQLITE_SYNC_MASK);
003126 if( rc ) return rc;
003127 }
003128 }
003129 assert( (int)pWal->szPage==szPage );
003130
003131 /* Setup information needed to write frames into the WAL */
003132 w.pWal = pWal;
003133 w.pFd = pWal->pWalFd;
003134 w.iSyncPoint = 0;
003135 w.syncFlags = sync_flags;
003136 w.szPage = szPage;
003137 iOffset = walFrameOffset(iFrame+1, szPage);
003138 szFrame = szPage + WAL_FRAME_HDRSIZE;
003139
003140 /* Write all frames into the log file exactly once */
003141 for(p=pList; p; p=p->pDirty){
003142 int nDbSize; /* 0 normally. Positive == commit flag */
003143
003144 /* Check if this page has already been written into the wal file by
003145 ** the current transaction. If so, overwrite the existing frame and
003146 ** set Wal.writeLock to WAL_WRITELOCK_RECKSUM - indicating that
003147 ** checksums must be recomputed when the transaction is committed. */
003148 if( iFirst && (p->pDirty || isCommit==0) ){
003149 u32 iWrite = 0;
003150 VVA_ONLY(rc =) sqlite3WalFindFrame(pWal, p->pgno, &iWrite);
003151 assert( rc==SQLITE_OK || iWrite==0 );
003152 if( iWrite>=iFirst ){
003153 i64 iOff = walFrameOffset(iWrite, szPage) + WAL_FRAME_HDRSIZE;
003154 void *pData;
003155 if( pWal->iReCksum==0 || iWrite<pWal->iReCksum ){
003156 pWal->iReCksum = iWrite;
003157 }
003158 #if defined(SQLITE_HAS_CODEC)
003159 if( (pData = sqlite3PagerCodec(p))==0 ) return SQLITE_NOMEM;
003160 #else
003161 pData = p->pData;
003162 #endif
003163 rc = sqlite3OsWrite(pWal->pWalFd, pData, szPage, iOff);
003164 if( rc ) return rc;
003165 p->flags &= ~PGHDR_WAL_APPEND;
003166 continue;
003167 }
003168 }
003169
003170 iFrame++;
003171 assert( iOffset==walFrameOffset(iFrame, szPage) );
003172 nDbSize = (isCommit && p->pDirty==0) ? nTruncate : 0;
003173 rc = walWriteOneFrame(&w, p, nDbSize, iOffset);
003174 if( rc ) return rc;
003175 pLast = p;
003176 iOffset += szFrame;
003177 p->flags |= PGHDR_WAL_APPEND;
003178 }
003179
003180 /* Recalculate checksums within the wal file if required. */
003181 if( isCommit && pWal->iReCksum ){
003182 rc = walRewriteChecksums(pWal, iFrame);
003183 if( rc ) return rc;
003184 }
003185
003186 /* If this is the end of a transaction, then we might need to pad
003187 ** the transaction and/or sync the WAL file.
003188 **
003189 ** Padding and syncing only occur if this set of frames complete a
003190 ** transaction and if PRAGMA synchronous=FULL. If synchronous==NORMAL
003191 ** or synchronous==OFF, then no padding or syncing are needed.
003192 **
003193 ** If SQLITE_IOCAP_POWERSAFE_OVERWRITE is defined, then padding is not
003194 ** needed and only the sync is done. If padding is needed, then the
003195 ** final frame is repeated (with its commit mark) until the next sector
003196 ** boundary is crossed. Only the part of the WAL prior to the last
003197 ** sector boundary is synced; the part of the last frame that extends
003198 ** past the sector boundary is written after the sync.
003199 */
003200 if( isCommit && (sync_flags & WAL_SYNC_TRANSACTIONS)!=0 ){
003201 int bSync = 1;
003202 if( pWal->padToSectorBoundary ){
003203 int sectorSize = sqlite3SectorSize(pWal->pWalFd);
003204 w.iSyncPoint = ((iOffset+sectorSize-1)/sectorSize)*sectorSize;
003205 bSync = (w.iSyncPoint==iOffset);
003206 testcase( bSync );
003207 while( iOffset<w.iSyncPoint ){
003208 rc = walWriteOneFrame(&w, pLast, nTruncate, iOffset);
003209 if( rc ) return rc;
003210 iOffset += szFrame;
003211 nExtra++;
003212 }
003213 }
003214 if( bSync ){
003215 assert( rc==SQLITE_OK );
003216 rc = sqlite3OsSync(w.pFd, sync_flags & SQLITE_SYNC_MASK);
003217 }
003218 }
003219
003220 /* If this frame set completes the first transaction in the WAL and
003221 ** if PRAGMA journal_size_limit is set, then truncate the WAL to the
003222 ** journal size limit, if possible.
003223 */
003224 if( isCommit && pWal->truncateOnCommit && pWal->mxWalSize>=0 ){
003225 i64 sz = pWal->mxWalSize;
003226 if( walFrameOffset(iFrame+nExtra+1, szPage)>pWal->mxWalSize ){
003227 sz = walFrameOffset(iFrame+nExtra+1, szPage);
003228 }
003229 walLimitSize(pWal, sz);
003230 pWal->truncateOnCommit = 0;
003231 }
003232
003233 /* Append data to the wal-index. It is not necessary to lock the
003234 ** wal-index to do this as the SQLITE_SHM_WRITE lock held on the wal-index
003235 ** guarantees that there are no other writers, and no data that may
003236 ** be in use by existing readers is being overwritten.
003237 */
003238 iFrame = pWal->hdr.mxFrame;
003239 for(p=pList; p && rc==SQLITE_OK; p=p->pDirty){
003240 if( (p->flags & PGHDR_WAL_APPEND)==0 ) continue;
003241 iFrame++;
003242 rc = walIndexAppend(pWal, iFrame, p->pgno);
003243 }
003244 while( rc==SQLITE_OK && nExtra>0 ){
003245 iFrame++;
003246 nExtra--;
003247 rc = walIndexAppend(pWal, iFrame, pLast->pgno);
003248 }
003249
003250 if( rc==SQLITE_OK ){
003251 /* Update the private copy of the header. */
003252 pWal->hdr.szPage = (u16)((szPage&0xff00) | (szPage>>16));
003253 testcase( szPage<=32768 );
003254 testcase( szPage>=65536 );
003255 pWal->hdr.mxFrame = iFrame;
003256 if( isCommit ){
003257 pWal->hdr.iChange++;
003258 pWal->hdr.nPage = nTruncate;
003259 }
003260 /* If this is a commit, update the wal-index header too. */
003261 if( isCommit ){
003262 walIndexWriteHdr(pWal);
003263 pWal->iCallback = iFrame;
003264 }
003265 }
003266
003267 WALTRACE(("WAL%p: frame write %s\n", pWal, rc ? "failed" : "ok"));
003268 return rc;
003269 }
003270
003271 /*
003272 ** This routine is called to implement sqlite3_wal_checkpoint() and
003273 ** related interfaces.
003274 **
003275 ** Obtain a CHECKPOINT lock and then backfill as much information as
003276 ** we can from WAL into the database.
003277 **
003278 ** If parameter xBusy is not NULL, it is a pointer to a busy-handler
003279 ** callback. In this case this function runs a blocking checkpoint.
003280 */
003281 int sqlite3WalCheckpoint(
003282 Wal *pWal, /* Wal connection */
003283 sqlite3 *db, /* Check this handle's interrupt flag */
003284 int eMode, /* PASSIVE, FULL, RESTART, or TRUNCATE */
003285 int (*xBusy)(void*), /* Function to call when busy */
003286 void *pBusyArg, /* Context argument for xBusyHandler */
003287 int sync_flags, /* Flags to sync db file with (or 0) */
003288 int nBuf, /* Size of temporary buffer */
003289 u8 *zBuf, /* Temporary buffer to use */
003290 int *pnLog, /* OUT: Number of frames in WAL */
003291 int *pnCkpt /* OUT: Number of backfilled frames in WAL */
003292 ){
003293 int rc; /* Return code */
003294 int isChanged = 0; /* True if a new wal-index header is loaded */
003295 int eMode2 = eMode; /* Mode to pass to walCheckpoint() */
003296 int (*xBusy2)(void*) = xBusy; /* Busy handler for eMode2 */
003297
003298 assert( pWal->ckptLock==0 );
003299 assert( pWal->writeLock==0 );
003300
003301 /* EVIDENCE-OF: R-62920-47450 The busy-handler callback is never invoked
003302 ** in the SQLITE_CHECKPOINT_PASSIVE mode. */
003303 assert( eMode!=SQLITE_CHECKPOINT_PASSIVE || xBusy==0 );
003304
003305 if( pWal->readOnly ) return SQLITE_READONLY;
003306 WALTRACE(("WAL%p: checkpoint begins\n", pWal));
003307
003308 /* IMPLEMENTATION-OF: R-62028-47212 All calls obtain an exclusive
003309 ** "checkpoint" lock on the database file. */
003310 rc = walLockExclusive(pWal, WAL_CKPT_LOCK, 1);
003311 if( rc ){
003312 /* EVIDENCE-OF: R-10421-19736 If any other process is running a
003313 ** checkpoint operation at the same time, the lock cannot be obtained and
003314 ** SQLITE_BUSY is returned.
003315 ** EVIDENCE-OF: R-53820-33897 Even if there is a busy-handler configured,
003316 ** it will not be invoked in this case.
003317 */
003318 testcase( rc==SQLITE_BUSY );
003319 testcase( xBusy!=0 );
003320 return rc;
003321 }
003322 pWal->ckptLock = 1;
003323
003324 /* IMPLEMENTATION-OF: R-59782-36818 The SQLITE_CHECKPOINT_FULL, RESTART and
003325 ** TRUNCATE modes also obtain the exclusive "writer" lock on the database
003326 ** file.
003327 **
003328 ** EVIDENCE-OF: R-60642-04082 If the writer lock cannot be obtained
003329 ** immediately, and a busy-handler is configured, it is invoked and the
003330 ** writer lock retried until either the busy-handler returns 0 or the
003331 ** lock is successfully obtained.
003332 */
003333 if( eMode!=SQLITE_CHECKPOINT_PASSIVE ){
003334 rc = walBusyLock(pWal, xBusy, pBusyArg, WAL_WRITE_LOCK, 1);
003335 if( rc==SQLITE_OK ){
003336 pWal->writeLock = 1;
003337 }else if( rc==SQLITE_BUSY ){
003338 eMode2 = SQLITE_CHECKPOINT_PASSIVE;
003339 xBusy2 = 0;
003340 rc = SQLITE_OK;
003341 }
003342 }
003343
003344 /* Read the wal-index header. */
003345 if( rc==SQLITE_OK ){
003346 rc = walIndexReadHdr(pWal, &isChanged);
003347 if( isChanged && pWal->pDbFd->pMethods->iVersion>=3 ){
003348 sqlite3OsUnfetch(pWal->pDbFd, 0, 0);
003349 }
003350 }
003351
003352 /* Copy data from the log to the database file. */
003353 if( rc==SQLITE_OK ){
003354
003355 if( pWal->hdr.mxFrame && walPagesize(pWal)!=nBuf ){
003356 rc = SQLITE_CORRUPT_BKPT;
003357 }else{
003358 rc = walCheckpoint(pWal, db, eMode2, xBusy2, pBusyArg, sync_flags, zBuf);
003359 }
003360
003361 /* If no error occurred, set the output variables. */
003362 if( rc==SQLITE_OK || rc==SQLITE_BUSY ){
003363 if( pnLog ) *pnLog = (int)pWal->hdr.mxFrame;
003364 if( pnCkpt ) *pnCkpt = (int)(walCkptInfo(pWal)->nBackfill);
003365 }
003366 }
003367
003368 if( isChanged ){
003369 /* If a new wal-index header was loaded before the checkpoint was
003370 ** performed, then the pager-cache associated with pWal is now
003371 ** out of date. So zero the cached wal-index header to ensure that
003372 ** next time the pager opens a snapshot on this database it knows that
003373 ** the cache needs to be reset.
003374 */
003375 memset(&pWal->hdr, 0, sizeof(WalIndexHdr));
003376 }
003377
003378 /* Release the locks. */
003379 sqlite3WalEndWriteTransaction(pWal);
003380 walUnlockExclusive(pWal, WAL_CKPT_LOCK, 1);
003381 pWal->ckptLock = 0;
003382 WALTRACE(("WAL%p: checkpoint %s\n", pWal, rc ? "failed" : "ok"));
003383 return (rc==SQLITE_OK && eMode!=eMode2 ? SQLITE_BUSY : rc);
003384 }
003385
003386 /* Return the value to pass to a sqlite3_wal_hook callback, the
003387 ** number of frames in the WAL at the point of the last commit since
003388 ** sqlite3WalCallback() was called. If no commits have occurred since
003389 ** the last call, then return 0.
003390 */
003391 int sqlite3WalCallback(Wal *pWal){
003392 u32 ret = 0;
003393 if( pWal ){
003394 ret = pWal->iCallback;
003395 pWal->iCallback = 0;
003396 }
003397 return (int)ret;
003398 }
003399
003400 /*
003401 ** This function is called to change the WAL subsystem into or out
003402 ** of locking_mode=EXCLUSIVE.
003403 **
003404 ** If op is zero, then attempt to change from locking_mode=EXCLUSIVE
003405 ** into locking_mode=NORMAL. This means that we must acquire a lock
003406 ** on the pWal->readLock byte. If the WAL is already in locking_mode=NORMAL
003407 ** or if the acquisition of the lock fails, then return 0. If the
003408 ** transition out of exclusive-mode is successful, return 1. This
003409 ** operation must occur while the pager is still holding the exclusive
003410 ** lock on the main database file.
003411 **
003412 ** If op is one, then change from locking_mode=NORMAL into
003413 ** locking_mode=EXCLUSIVE. This means that the pWal->readLock must
003414 ** be released. Return 1 if the transition is made and 0 if the
003415 ** WAL is already in exclusive-locking mode - meaning that this
003416 ** routine is a no-op. The pager must already hold the exclusive lock
003417 ** on the main database file before invoking this operation.
003418 **
003419 ** If op is negative, then do a dry-run of the op==1 case but do
003420 ** not actually change anything. The pager uses this to see if it
003421 ** should acquire the database exclusive lock prior to invoking
003422 ** the op==1 case.
003423 */
003424 int sqlite3WalExclusiveMode(Wal *pWal, int op){
003425 int rc;
003426 assert( pWal->writeLock==0 );
003427 assert( pWal->exclusiveMode!=WAL_HEAPMEMORY_MODE || op==-1 );
003428
003429 /* pWal->readLock is usually set, but might be -1 if there was a
003430 ** prior error while attempting to acquire are read-lock. This cannot
003431 ** happen if the connection is actually in exclusive mode (as no xShmLock
003432 ** locks are taken in this case). Nor should the pager attempt to
003433 ** upgrade to exclusive-mode following such an error.
003434 */
003435 assert( pWal->readLock>=0 || pWal->lockError );
003436 assert( pWal->readLock>=0 || (op<=0 && pWal->exclusiveMode==0) );
003437
003438 if( op==0 ){
003439 if( pWal->exclusiveMode ){
003440 pWal->exclusiveMode = 0;
003441 if( walLockShared(pWal, WAL_READ_LOCK(pWal->readLock))!=SQLITE_OK ){
003442 pWal->exclusiveMode = 1;
003443 }
003444 rc = pWal->exclusiveMode==0;
003445 }else{
003446 /* Already in locking_mode=NORMAL */
003447 rc = 0;
003448 }
003449 }else if( op>0 ){
003450 assert( pWal->exclusiveMode==0 );
003451 assert( pWal->readLock>=0 );
003452 walUnlockShared(pWal, WAL_READ_LOCK(pWal->readLock));
003453 pWal->exclusiveMode = 1;
003454 rc = 1;
003455 }else{
003456 rc = pWal->exclusiveMode==0;
003457 }
003458 return rc;
003459 }
003460
003461 /*
003462 ** Return true if the argument is non-NULL and the WAL module is using
003463 ** heap-memory for the wal-index. Otherwise, if the argument is NULL or the
003464 ** WAL module is using shared-memory, return false.
003465 */
003466 int sqlite3WalHeapMemory(Wal *pWal){
003467 return (pWal && pWal->exclusiveMode==WAL_HEAPMEMORY_MODE );
003468 }
003469
003470 #ifdef SQLITE_ENABLE_SNAPSHOT
003471 /* Create a snapshot object. The content of a snapshot is opaque to
003472 ** every other subsystem, so the WAL module can put whatever it needs
003473 ** in the object.
003474 */
003475 int sqlite3WalSnapshotGet(Wal *pWal, sqlite3_snapshot **ppSnapshot){
003476 int rc = SQLITE_OK;
003477 WalIndexHdr *pRet;
003478 static const u32 aZero[4] = { 0, 0, 0, 0 };
003479
003480 assert( pWal->readLock>=0 && pWal->writeLock==0 );
003481
003482 if( memcmp(&pWal->hdr.aFrameCksum[0],aZero,16)==0 ){
003483 *ppSnapshot = 0;
003484 return SQLITE_ERROR;
003485 }
003486 pRet = (WalIndexHdr*)sqlite3_malloc(sizeof(WalIndexHdr));
003487 if( pRet==0 ){
003488 rc = SQLITE_NOMEM_BKPT;
003489 }else{
003490 memcpy(pRet, &pWal->hdr, sizeof(WalIndexHdr));
003491 *ppSnapshot = (sqlite3_snapshot*)pRet;
003492 }
003493
003494 return rc;
003495 }
003496
003497 /* Try to open on pSnapshot when the next read-transaction starts
003498 */
003499 void sqlite3WalSnapshotOpen(Wal *pWal, sqlite3_snapshot *pSnapshot){
003500 pWal->pSnapshot = (WalIndexHdr*)pSnapshot;
003501 }
003502
003503 /*
003504 ** Return a +ve value if snapshot p1 is newer than p2. A -ve value if
003505 ** p1 is older than p2 and zero if p1 and p2 are the same snapshot.
003506 */
003507 int sqlite3_snapshot_cmp(sqlite3_snapshot *p1, sqlite3_snapshot *p2){
003508 WalIndexHdr *pHdr1 = (WalIndexHdr*)p1;
003509 WalIndexHdr *pHdr2 = (WalIndexHdr*)p2;
003510
003511 /* aSalt[0] is a copy of the value stored in the wal file header. It
003512 ** is incremented each time the wal file is restarted. */
003513 if( pHdr1->aSalt[0]<pHdr2->aSalt[0] ) return -1;
003514 if( pHdr1->aSalt[0]>pHdr2->aSalt[0] ) return +1;
003515 if( pHdr1->mxFrame<pHdr2->mxFrame ) return -1;
003516 if( pHdr1->mxFrame>pHdr2->mxFrame ) return +1;
003517 return 0;
003518 }
003519 #endif /* SQLITE_ENABLE_SNAPSHOT */
003520
003521 #ifdef SQLITE_ENABLE_ZIPVFS
003522 /*
003523 ** If the argument is not NULL, it points to a Wal object that holds a
003524 ** read-lock. This function returns the database page-size if it is known,
003525 ** or zero if it is not (or if pWal is NULL).
003526 */
003527 int sqlite3WalFramesize(Wal *pWal){
003528 assert( pWal==0 || pWal->readLock>=0 );
003529 return (pWal ? pWal->szPage : 0);
003530 }
003531 #endif
003532
003533 /* Return the sqlite3_file object for the WAL file
003534 */
003535 sqlite3_file *sqlite3WalFile(Wal *pWal){
003536 return pWal->pWalFd;
003537 }
003538
003539 #endif /* #ifndef SQLITE_OMIT_WAL */