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