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