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