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