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