1/*
2** 2010 February 1
3**
4** The author disclaims copyright to this source code. In place of
5** a legal notice, here is a blessing:
6**
7** May you do good and not evil.
8** May you find forgiveness for yourself and forgive others.
9** May you share freely, never taking more than you give.
10**
11*************************************************************************
12**
13** This file contains the implementation of a write-ahead log (WAL) used in
14** "journal_mode=WAL" mode.
15**
16** WRITE-AHEAD LOG (WAL) FILE FORMAT
17**
18** A WAL file consists of a header followed by zero or more "frames".
19** Each frame records the revised content of a single page from the
20** database file. All changes to the database are recorded by writing
21** frames into the WAL. Transactions commit when a frame is written that
22** contains a commit marker. A single WAL can and usually does record
23** multiple transactions. Periodically, the content of the WAL is
24** transferred back into the database file in an operation called a
25** "checkpoint".
26**
27** A single WAL file can be used multiple times. In other words, the
28** WAL can fill up with frames and then be checkpointed and then new
29** frames can overwrite the old ones. A WAL always grows from beginning
30** toward the end. Checksums and counters attached to each frame are
31** used to determine which frames within the WAL are valid and which
32** are leftovers from prior checkpoints.
33**
34** The WAL header is 32 bytes in size and consists of the following eight
35** big-endian 32-bit unsigned integer values:
36**
37** 0: Magic number. 0x377f0682 or 0x377f0683
38** 4: File format version. Currently 3007000
39** 8: Database page size. Example: 1024
40** 12: Checkpoint sequence number
41** 16: Salt-1, random integer incremented with each checkpoint
42** 20: Salt-2, a different random integer changing with each ckpt
43** 24: Checksum-1 (first part of checksum for first 24 bytes of header).
44** 28: Checksum-2 (second part of checksum for first 24 bytes of header).
45**
46** Immediately following the wal-header are zero or more frames. Each
47** frame consists of a 24-byte frame-header followed by a <page-size> bytes
48** of page data. The frame-header is six big-endian 32-bit unsigned
49** integer values, as follows:
50**
51** 0: Page number.
52** 4: For commit records, the size of the database image in pages
53** after the commit. For all other records, zero.
54** 8: Salt-1 (copied from the header)
55** 12: Salt-2 (copied from the header)
56** 16: Checksum-1.
57** 20: Checksum-2.
58**
59** A frame is considered valid if and only if the following conditions are
60** true:
61**
62** (1) The salt-1 and salt-2 values in the frame-header match
63** salt values in the wal-header
64**
65** (2) The checksum values in the final 8 bytes of the frame-header
66** exactly match the checksum computed consecutively on the
67** WAL header and the first 8 bytes and the content of all frames
68** up to and including the current frame.
69**
70** The checksum is computed using 32-bit big-endian integers if the
71** magic number in the first 4 bytes of the WAL is 0x377f0683 and it
72** is computed using little-endian if the magic number is 0x377f0682.
73** The checksum values are always stored in the frame header in a
74** big-endian format regardless of which byte order is used to compute
75** the checksum. The checksum is computed by interpreting the input as
76** an even number of unsigned 32-bit integers: x[0] through x[N]. The
77** algorithm used for the checksum is as follows:
78**
79** for i from 0 to n-1 step 2:
80** s0 += x[i] + s1;
81** s1 += x[i+1] + s0;
82** endfor
83**
84** Note that s0 and s1 are both weighted checksums using fibonacci weights
85** in reverse order (the largest fibonacci weight occurs on the first element
86** of the sequence being summed.) The s1 value spans all 32-bit
87** terms of the sequence whereas s0 omits the final term.
88**
89** On a checkpoint, the WAL is first VFS.xSync-ed, then valid content of the
90** WAL is transferred into the database, then the database is VFS.xSync-ed.
91** The VFS.xSync operations serve as write barriers - all writes launched
92** before the xSync must complete before any write that launches after the
93** xSync begins.
94**
95** After each checkpoint, the salt-1 value is incremented and the salt-2
96** value is randomized. This prevents old and new frames in the WAL from
97** being considered valid at the same time and being checkpointing together
98** following a crash.
99**
100** READER ALGORITHM
101**
102** To read a page from the database (call it page number P), a reader
103** first checks the WAL to see if it contains page P. If so, then the
104** last valid instance of page P that is a followed by a commit frame
105** or is a commit frame itself becomes the value read. If the WAL
106** contains no copies of page P that are valid and which are a commit
107** frame or are followed by a commit frame, then page P is read from
108** the database file.
109**
110** To start a read transaction, the reader records the index of the last
111** valid frame in the WAL. The reader uses this recorded "mxFrame" value
112** for all subsequent read operations. New transactions can be appended
113** to the WAL, but as long as the reader uses its original mxFrame value
114** and ignores the newly appended content, it will see a consistent snapshot
115** of the database from a single point in time. This technique allows
116** multiple concurrent readers to view different versions of the database
117** content simultaneously.
118**
119** The reader algorithm in the previous paragraphs works correctly, but
120** because frames for page P can appear anywhere within the WAL, the
121** reader has to scan the entire WAL looking for page P frames. If the
122** WAL is large (multiple megabytes is typical) that scan can be slow,
123** and read performance suffers. To overcome this problem, a separate
124** data structure called the wal-index is maintained to expedite the
125** search for frames of a particular page.
126**
127** WAL-INDEX FORMAT
128**
129** Conceptually, the wal-index is shared memory, though VFS implementations
130** might choose to implement the wal-index using a mmapped file. Because
131** the wal-index is shared memory, SQLite does not support journal_mode=WAL
132** on a network filesystem. All users of the database must be able to
133** share memory.
134**
135** In the default unix and windows implementation, the wal-index is a mmapped
136** file whose name is the database name with a "-shm" suffix added. For that
137** reason, the wal-index is sometimes called the "shm" file.
138**
139** The wal-index is transient. After a crash, the wal-index can (and should
140** be) reconstructed from the original WAL file. In fact, the VFS is required
141** to either truncate or zero the header of the wal-index when the last
142** connection to it closes. Because the wal-index is transient, it can
143** use an architecture-specific format; it does not have to be cross-platform.
144** Hence, unlike the database and WAL file formats which store all values
145** as big endian, the wal-index can store multi-byte values in the native
146** byte order of the host computer.
147**
148** The purpose of the wal-index is to answer this question quickly: Given
149** a page number P and a maximum frame index M, return the index of the
150** last frame in the wal before frame M for page P in the WAL, or return
151** NULL if there are no frames for page P in the WAL prior to M.
152**
153** The wal-index consists of a header region, followed by an one or
154** more index blocks.
155**
156** The wal-index header contains the total number of frames within the WAL
157** in the mxFrame field.
158**
159** Each index block except for the first contains information on
160** HASHTABLE_NPAGE frames. The first index block contains information on
161** HASHTABLE_NPAGE_ONE frames. The values of HASHTABLE_NPAGE_ONE and
162** HASHTABLE_NPAGE are selected so that together the wal-index header and
163** first index block are the same size as all other index blocks in the
164** wal-index. The values are:
165**
166** HASHTABLE_NPAGE 4096
167** HASHTABLE_NPAGE_ONE 4062
168**
169** Each index block contains two sections, a page-mapping that contains the
170** database page number associated with each wal frame, and a hash-table
171** that allows readers to query an index block for a specific page number.
172** The page-mapping is an array of HASHTABLE_NPAGE (or HASHTABLE_NPAGE_ONE
173** for the first index block) 32-bit page numbers. The first entry in the
174** first index-block contains the database page number corresponding to the
175** first frame in the WAL file. The first entry in the second index block
176** in the WAL file corresponds to the (HASHTABLE_NPAGE_ONE+1)th frame in
177** the log, and so on.
178**
179** The last index block in a wal-index usually contains less than the full
180** complement of HASHTABLE_NPAGE (or HASHTABLE_NPAGE_ONE) page-numbers,
181** depending on the contents of the WAL file. This does not change the
182** allocated size of the page-mapping array - the page-mapping array merely
183** contains unused entries.
184**
185** Even without using the hash table, the last frame for page P
186** can be found by scanning the page-mapping sections of each index block
187** starting with the last index block and moving toward the first, and
188** within each index block, starting at the end and moving toward the
189** beginning. The first entry that equals P corresponds to the frame
190** holding the content for that page.
191**
192** The hash table consists of HASHTABLE_NSLOT 16-bit unsigned integers.
193** HASHTABLE_NSLOT = 2*HASHTABLE_NPAGE, and there is one entry in the
194** hash table for each page number in the mapping section, so the hash
195** table is never more than half full. The expected number of collisions
196** prior to finding a match is 1. Each entry of the hash table is an
197** 1-based index of an entry in the mapping section of the same
198** index block. Let K be the 1-based index of the largest entry in
199** the mapping section. (For index blocks other than the last, K will
200** always be exactly HASHTABLE_NPAGE (4096) and for the last index block
201** K will be (mxFrame%HASHTABLE_NPAGE).) Unused slots of the hash table
202** contain a value of 0.
203**
204** To look for page P in the hash table, first compute a hash iKey on
205** P as follows:
206**
207** iKey = (P * 383) % HASHTABLE_NSLOT
208**
209** Then start scanning entries of the hash table, starting with iKey
210** (wrapping around to the beginning when the end of the hash table is
211** reached) until an unused hash slot is found. Let the first unused slot
212** be at index iUnused. (iUnused might be less than iKey if there was
213** wrap-around.) Because the hash table is never more than half full,
214** the search is guaranteed to eventually hit an unused entry. Let
215** iMax be the value between iKey and iUnused, closest to iUnused,
216** where aHash[iMax]==P. If there is no iMax entry (if there exists
217** no hash slot such that aHash[i]==p) then page P is not in the
218** current index block. Otherwise the iMax-th mapping entry of the
219** current index block corresponds to the last entry that references
220** page P.
221**
222** A hash search begins with the last index block and moves toward the
223** first index block, looking for entries corresponding to page P. On
224** average, only two or three slots in each index block need to be
225** examined in order to either find the last entry for page P, or to
226** establish that no such entry exists in the block. Each index block
227** holds over 4000 entries. So two or three index blocks are sufficient
228** to cover a typical 10 megabyte WAL file, assuming 1K pages. 8 or 10
229** comparisons (on average) suffice to either locate a frame in the
230** WAL or to establish that the frame does not exist in the WAL. This
231** is much faster than scanning the entire 10MB WAL.
232**
233** Note that entries are added in order of increasing K. Hence, one
234** reader might be using some value K0 and a second reader that started
235** at a later time (after additional transactions were added to the WAL
236** and to the wal-index) might be using a different value K1, where K1>K0.
237** Both readers can use the same hash table and mapping section to get
238** the correct result. There may be entries in the hash table with
239** K>K0 but to the first reader, those entries will appear to be unused
240** slots in the hash table and so the first reader will get an answer as
241** if no values greater than K0 had ever been inserted into the hash table
242** in the first place - which is what reader one wants. Meanwhile, the
243** second reader using K1 will see additional values that were inserted
244** later, which is exactly what reader two wants.
245**
246** When a rollback occurs, the value of K is decreased. Hash table entries
247** that correspond to frames greater than the new K value are removed
248** from the hash table at this point.
249*/
250#ifndef SQLITE_OMIT_WAL
251
252#include "wal.h"
253
254/*
255** Trace output macros
256*/
257#if defined(SQLITE_TEST) && defined(SQLITE_DEBUG)
258int sqlite3WalTrace = 0;
259# define WALTRACE(X) if(sqlite3WalTrace) sqlite3DebugPrintf X
260#else
261# define WALTRACE(X)
262#endif
263
264/*
265** The maximum (and only) versions of the wal and wal-index formats
266** that may be interpreted by this version of SQLite.
267**
268** If a client begins recovering a WAL file and finds that (a) the checksum
269** values in the wal-header are correct and (b) the version field is not
270** WAL_MAX_VERSION, recovery fails and SQLite returns SQLITE_CANTOPEN.
271**
272** Similarly, if a client successfully reads a wal-index header (i.e. the
273** checksum test is successful) and finds that the version field is not
274** WALINDEX_MAX_VERSION, then no read-transaction is opened and SQLite
275** returns SQLITE_CANTOPEN.
276*/
277#define WAL_MAX_VERSION 3007000
278#define WALINDEX_MAX_VERSION 3007000
279
280/*
281** Index numbers for various locking bytes. WAL_NREADER is the number
282** of available reader locks and should be at least 3. The default
283** is SQLITE_SHM_NLOCK==8 and WAL_NREADER==5.
284**
285** Technically, the various VFSes are free to implement these locks however
286** they see fit. However, compatibility is encouraged so that VFSes can
287** interoperate. The standard implemention used on both unix and windows
288** is for the index number to indicate a byte offset into the
289** WalCkptInfo.aLock[] array in the wal-index header. In other words, all
290** locks are on the shm file. The WALINDEX_LOCK_OFFSET constant (which
291** should be 120) is the location in the shm file for the first locking
292** byte.
293*/
294#define WAL_WRITE_LOCK 0
295#define WAL_ALL_BUT_WRITE 1
296#define WAL_CKPT_LOCK 1
297#define WAL_RECOVER_LOCK 2
298#define WAL_READ_LOCK(I) (3+(I))
299#define WAL_NREADER (SQLITE_SHM_NLOCK-3)
300
301
302/* Object declarations */
303typedef struct WalIndexHdr WalIndexHdr;
304typedef struct WalIterator WalIterator;
305typedef struct WalCkptInfo WalCkptInfo;
306
307
308/*
309** The following object holds a copy of the wal-index header content.
310**
311** The actual header in the wal-index consists of two copies of this
312** object followed by one instance of the WalCkptInfo object.
313** For all versions of SQLite through 3.10.0 and probably beyond,
314** the locking bytes (WalCkptInfo.aLock) start at offset 120 and
315** the total header size is 136 bytes.
316**
317** The szPage value can be any power of 2 between 512 and 32768, inclusive.
318** Or it can be 1 to represent a 65536-byte page. The latter case was
319** added in 3.7.1 when support for 64K pages was added.
320*/
321struct WalIndexHdr {
322 u32 iVersion; /* Wal-index version */
323 u32 unused; /* Unused (padding) field */
324 u32 iChange; /* Counter incremented each transaction */
325 u8 isInit; /* 1 when initialized */
326 u8 bigEndCksum; /* True if checksums in WAL are big-endian */
327 u16 szPage; /* Database page size in bytes. 1==64K */
328 u32 mxFrame; /* Index of last valid frame in the WAL */
329 u32 nPage; /* Size of database in pages */
330 u32 aFrameCksum[2]; /* Checksum of last frame in log */
331 u32 aSalt[2]; /* Two salt values copied from WAL header */
332 u32 aCksum[2]; /* Checksum over all prior fields */
333};
334
335/*
336** A copy of the following object occurs in the wal-index immediately
337** following the second copy of the WalIndexHdr. This object stores
338** information used by checkpoint.
339**
340** nBackfill is the number of frames in the WAL that have been written
341** back into the database. (We call the act of moving content from WAL to
342** database "backfilling".) The nBackfill number is never greater than
343** WalIndexHdr.mxFrame. nBackfill can only be increased by threads
344** holding the WAL_CKPT_LOCK lock (which includes a recovery thread).
345** However, a WAL_WRITE_LOCK thread can move the value of nBackfill from
346** mxFrame back to zero when the WAL is reset.
347**
348** nBackfillAttempted is the largest value of nBackfill that a checkpoint
349** has attempted to achieve. Normally nBackfill==nBackfillAtempted, however
350** the nBackfillAttempted is set before any backfilling is done and the
351** nBackfill is only set after all backfilling completes. So if a checkpoint
352** crashes, nBackfillAttempted might be larger than nBackfill. The
353** WalIndexHdr.mxFrame must never be less than nBackfillAttempted.
354**
355** The aLock[] field is a set of bytes used for locking. These bytes should
356** never be read or written.
357**
358** There is one entry in aReadMark[] for each reader lock. If a reader
359** holds read-lock K, then the value in aReadMark[K] is no greater than
360** the mxFrame for that reader. The value READMARK_NOT_USED (0xffffffff)
361** for any aReadMark[] means that entry is unused. aReadMark[0] is
362** a special case; its value is never used and it exists as a place-holder
363** to avoid having to offset aReadMark[] indexs by one. Readers holding
364** WAL_READ_LOCK(0) always ignore the entire WAL and read all content
365** directly from the database.
366**
367** The value of aReadMark[K] may only be changed by a thread that
368** is holding an exclusive lock on WAL_READ_LOCK(K). Thus, the value of
369** aReadMark[K] cannot changed while there is a reader is using that mark
370** since the reader will be holding a shared lock on WAL_READ_LOCK(K).
371**
372** The checkpointer may only transfer frames from WAL to database where
373** the frame numbers are less than or equal to every aReadMark[] that is
374** in use (that is, every aReadMark[j] for which there is a corresponding
375** WAL_READ_LOCK(j)). New readers (usually) pick the aReadMark[] with the
376** largest value and will increase an unused aReadMark[] to mxFrame if there
377** is not already an aReadMark[] equal to mxFrame. The exception to the
378** previous sentence is when nBackfill equals mxFrame (meaning that everything
379** in the WAL has been backfilled into the database) then new readers
380** will choose aReadMark[0] which has value 0 and hence such reader will
381** get all their all content directly from the database file and ignore
382** the WAL.
383**
384** Writers normally append new frames to the end of the WAL. However,
385** if nBackfill equals mxFrame (meaning that all WAL content has been
386** written back into the database) and if no readers are using the WAL
387** (in other words, if there are no WAL_READ_LOCK(i) where i>0) then
388** the writer will first "reset" the WAL back to the beginning and start
389** writing new content beginning at frame 1.
390**
391** We assume that 32-bit loads are atomic and so no locks are needed in
392** order to read from any aReadMark[] entries.
393*/
394struct WalCkptInfo {
395 u32 nBackfill; /* Number of WAL frames backfilled into DB */
396 u32 aReadMark[WAL_NREADER]; /* Reader marks */
397 u8 aLock[SQLITE_SHM_NLOCK]; /* Reserved space for locks */
398 u32 nBackfillAttempted; /* WAL frames perhaps written, or maybe not */
399 u32 notUsed0; /* Available for future enhancements */
400};
401#define READMARK_NOT_USED 0xffffffff
402
403/*
404** This is a schematic view of the complete 136-byte header of the
405** wal-index file (also known as the -shm file):
406**
407** +-----------------------------+
408** 0: | iVersion | \
409** +-----------------------------+ |
410** 4: | (unused padding) | |
411** +-----------------------------+ |
412** 8: | iChange | |
413** +-------+-------+-------------+ |
414** 12: | bInit | bBig | szPage | |
415** +-------+-------+-------------+ |
416** 16: | mxFrame | | First copy of the
417** +-----------------------------+ | WalIndexHdr object
418** 20: | nPage | |
419** +-----------------------------+ |
420** 24: | aFrameCksum | |
421** | | |
422** +-----------------------------+ |
423** 32: | aSalt | |
424** | | |
425** +-----------------------------+ |
426** 40: | aCksum | |
427** | | /
428** +-----------------------------+
429** 48: | iVersion | \
430** +-----------------------------+ |
431** 52: | (unused padding) | |
432** +-----------------------------+ |
433** 56: | iChange | |
434** +-------+-------+-------------+ |
435** 60: | bInit | bBig | szPage | |
436** +-------+-------+-------------+ | Second copy of the
437** 64: | mxFrame | | WalIndexHdr
438** +-----------------------------+ |
439** 68: | nPage | |
440** +-----------------------------+ |
441** 72: | aFrameCksum | |
442** | | |
443** +-----------------------------+ |
444** 80: | aSalt | |
445** | | |
446** +-----------------------------+ |
447** 88: | aCksum | |
448** | | /
449** +-----------------------------+
450** 96: | nBackfill |
451** +-----------------------------+
452** 100: | 5 read marks |
453** | |
454** | |
455** | |
456** | |
457** +-------+-------+------+------+
458** 120: | Write | Ckpt | Rcvr | Rd0 | \
459** +-------+-------+------+------+ ) 8 lock bytes
460** | Read1 | Read2 | Rd3 | Rd4 | /
461** +-------+-------+------+------+
462** 128: | nBackfillAttempted |
463** +-----------------------------+
464** 132: | (unused padding) |
465** +-----------------------------+
466*/
467
468/* A block of WALINDEX_LOCK_RESERVED bytes beginning at
469** WALINDEX_LOCK_OFFSET is reserved for locks. Since some systems
470** only support mandatory file-locks, we do not read or write data
471** from the region of the file on which locks are applied.
472*/
473#define WALINDEX_LOCK_OFFSET (sizeof(WalIndexHdr)*2+offsetof(WalCkptInfo,aLock))
474#define WALINDEX_HDR_SIZE (sizeof(WalIndexHdr)*2+sizeof(WalCkptInfo))
475
476/* Size of header before each frame in wal */
477#define WAL_FRAME_HDRSIZE 24
478
479/* Size of write ahead log header, including checksum. */
480#define WAL_HDRSIZE 32
481
482/* WAL magic value. Either this value, or the same value with the least
483** significant bit also set (WAL_MAGIC | 0x00000001) is stored in 32-bit
484** big-endian format in the first 4 bytes of a WAL file.
485**
486** If the LSB is set, then the checksums for each frame within the WAL
487** file are calculated by treating all data as an array of 32-bit
488** big-endian words. Otherwise, they are calculated by interpreting
489** all data as 32-bit little-endian words.
490*/
491#define WAL_MAGIC 0x377f0682
492
493/*
494** Return the offset of frame iFrame in the write-ahead log file,
495** assuming a database page size of szPage bytes. The offset returned
496** is to the start of the write-ahead log frame-header.
497*/
498#define walFrameOffset(iFrame, szPage) ( \
499 WAL_HDRSIZE + ((iFrame)-1)*(i64)((szPage)+WAL_FRAME_HDRSIZE) \
500)
501
502/*
503** An open write-ahead log file is represented by an instance of the
504** following object.
505*/
506struct Wal {
507 sqlite3_vfs *pVfs; /* The VFS used to create pDbFd */
508 sqlite3_file *pDbFd; /* File handle for the database file */
509 sqlite3_file *pWalFd; /* File handle for WAL file */
510 u32 iCallback; /* Value to pass to log callback (or 0) */
511 i64 mxWalSize; /* Truncate WAL to this size upon reset */
512 int nWiData; /* Size of array apWiData */
513 int szFirstBlock; /* Size of first block written to WAL file */
514 volatile u32 **apWiData; /* Pointer to wal-index content in memory */
515 u32 szPage; /* Database page size */
516 i16 readLock; /* Which read lock is being held. -1 for none */
517 u8 syncFlags; /* Flags to use to sync header writes */
518 u8 exclusiveMode; /* Non-zero if connection is in exclusive mode */
519 u8 writeLock; /* True if in a write transaction */
520 u8 ckptLock; /* True if holding a checkpoint lock */
521 u8 readOnly; /* WAL_RDWR, WAL_RDONLY, or WAL_SHM_RDONLY */
522 u8 truncateOnCommit; /* True to truncate WAL file on commit */
523 u8 syncHeader; /* Fsync the WAL header if true */
524 u8 padToSectorBoundary; /* Pad transactions out to the next sector */
525 u8 bShmUnreliable; /* SHM content is read-only and unreliable */
526 WalIndexHdr hdr; /* Wal-index header for current transaction */
527 u32 minFrame; /* Ignore wal frames before this one */
528 u32 iReCksum; /* On commit, recalculate checksums from here */
529 const char *zWalName; /* Name of WAL file */
530 u32 nCkpt; /* Checkpoint sequence counter in the wal-header */
531#ifdef SQLITE_DEBUG
532 u8 lockError; /* True if a locking error has occurred */
533#endif
534#ifdef SQLITE_ENABLE_SNAPSHOT
535 WalIndexHdr *pSnapshot; /* Start transaction here if not NULL */
536#endif
537#ifdef SQLITE_ENABLE_SETLK_TIMEOUT
538 sqlite3 *db;
539#endif
540};
541
542/*
543** Candidate values for Wal.exclusiveMode.
544*/
545#define WAL_NORMAL_MODE 0
546#define WAL_EXCLUSIVE_MODE 1
547#define WAL_HEAPMEMORY_MODE 2
548
549/*
550** Possible values for WAL.readOnly
551*/
552#define WAL_RDWR 0 /* Normal read/write connection */
553#define WAL_RDONLY 1 /* The WAL file is readonly */
554#define WAL_SHM_RDONLY 2 /* The SHM file is readonly */
555
556/*
557** Each page of the wal-index mapping contains a hash-table made up of
558** an array of HASHTABLE_NSLOT elements of the following type.
559*/
560typedef u16 ht_slot;
561
562/*
563** This structure is used to implement an iterator that loops through
564** all frames in the WAL in database page order. Where two or more frames
565** correspond to the same database page, the iterator visits only the
566** frame most recently written to the WAL (in other words, the frame with
567** the largest index).
568**
569** The internals of this structure are only accessed by:
570**
571** walIteratorInit() - Create a new iterator,
572** walIteratorNext() - Step an iterator,
573** walIteratorFree() - Free an iterator.
574**
575** This functionality is used by the checkpoint code (see walCheckpoint()).
576*/
577struct WalIterator {
578 u32 iPrior; /* Last result returned from the iterator */
579 int nSegment; /* Number of entries in aSegment[] */
580 struct WalSegment {
581 int iNext; /* Next slot in aIndex[] not yet returned */
582 ht_slot *aIndex; /* i0, i1, i2... such that aPgno[iN] ascend */
583 u32 *aPgno; /* Array of page numbers. */
584 int nEntry; /* Nr. of entries in aPgno[] and aIndex[] */
585 int iZero; /* Frame number associated with aPgno[0] */
586 } aSegment[1]; /* One for every 32KB page in the wal-index */
587};
588
589/*
590** Define the parameters of the hash tables in the wal-index file. There
591** is a hash-table following every HASHTABLE_NPAGE page numbers in the
592** wal-index.
593**
594** Changing any of these constants will alter the wal-index format and
595** create incompatibilities.
596*/
597#define HASHTABLE_NPAGE 4096 /* Must be power of 2 */
598#define HASHTABLE_HASH_1 383 /* Should be prime */
599#define HASHTABLE_NSLOT (HASHTABLE_NPAGE*2) /* Must be a power of 2 */
600
601/*
602** The block of page numbers associated with the first hash-table in a
603** wal-index is smaller than usual. This is so that there is a complete
604** hash-table on each aligned 32KB page of the wal-index.
605*/
606#define HASHTABLE_NPAGE_ONE (HASHTABLE_NPAGE - (WALINDEX_HDR_SIZE/sizeof(u32)))
607
608/* The wal-index is divided into pages of WALINDEX_PGSZ bytes each. */
609#define WALINDEX_PGSZ ( \
610 sizeof(ht_slot)*HASHTABLE_NSLOT + HASHTABLE_NPAGE*sizeof(u32) \
611)
612
613/*
614** Obtain a pointer to the iPage'th page of the wal-index. The wal-index
615** is broken into pages of WALINDEX_PGSZ bytes. Wal-index pages are
616** numbered from zero.
617**
618** If the wal-index is currently smaller the iPage pages then the size
619** of the wal-index might be increased, but only if it is safe to do
620** so. It is safe to enlarge the wal-index if pWal->writeLock is true
621** or pWal->exclusiveMode==WAL_HEAPMEMORY_MODE.
622**
623** Three possible result scenarios:
624**
625** (1) rc==SQLITE_OK and *ppPage==Requested-Wal-Index-Page
626** (2) rc>=SQLITE_ERROR and *ppPage==NULL
627** (3) rc==SQLITE_OK and *ppPage==NULL // only if iPage==0
628**
629** Scenario (3) can only occur when pWal->writeLock is false and iPage==0
630*/
631static SQLITE_NOINLINE int walIndexPageRealloc(
632 Wal *pWal, /* The WAL context */
633 int iPage, /* The page we seek */
634 volatile u32 **ppPage /* Write the page pointer here */
635){
636 int rc = SQLITE_OK;
637
638 /* Enlarge the pWal->apWiData[] array if required */
639 if( pWal->nWiData<=iPage ){
640 sqlite3_int64 nByte = sizeof(u32*)*(iPage+1);
641 volatile u32 **apNew;
642 apNew = (volatile u32 **)sqlite3Realloc((void *)pWal->apWiData, nByte);
643 if( !apNew ){
644 *ppPage = 0;
645 return SQLITE_NOMEM_BKPT;
646 }
647 memset((void*)&apNew[pWal->nWiData], 0,
648 sizeof(u32*)*(iPage+1-pWal->nWiData));
649 pWal->apWiData = apNew;
650 pWal->nWiData = iPage+1;
651 }
652
653 /* Request a pointer to the required page from the VFS */
654 assert( pWal->apWiData[iPage]==0 );
655 if( pWal->exclusiveMode==WAL_HEAPMEMORY_MODE ){
656 pWal->apWiData[iPage] = (u32 volatile *)sqlite3MallocZero(WALINDEX_PGSZ);
657 if( !pWal->apWiData[iPage] ) rc = SQLITE_NOMEM_BKPT;
658 }else{
659 rc = sqlite3OsShmMap(pWal->pDbFd, iPage, WALINDEX_PGSZ,
660 pWal->writeLock, (void volatile **)&pWal->apWiData[iPage]
661 );
662 assert( pWal->apWiData[iPage]!=0
663 || rc!=SQLITE_OK
664 || (pWal->writeLock==0 && iPage==0) );
665 testcase( pWal->apWiData[iPage]==0 && rc==SQLITE_OK );
666 if( rc==SQLITE_OK ){
667 if( iPage>0 && sqlite3FaultSim(600) ) rc = SQLITE_NOMEM;
668 }else if( (rc&0xff)==SQLITE_READONLY ){
669 pWal->readOnly |= WAL_SHM_RDONLY;
670 if( rc==SQLITE_READONLY ){
671 rc = SQLITE_OK;
672 }
673 }
674 }
675
676 *ppPage = pWal->apWiData[iPage];
677 assert( iPage==0 || *ppPage || rc!=SQLITE_OK );
678 return rc;
679}
680static int walIndexPage(
681 Wal *pWal, /* The WAL context */
682 int iPage, /* The page we seek */
683 volatile u32 **ppPage /* Write the page pointer here */
684){
685 if( pWal->nWiData<=iPage || (*ppPage = pWal->apWiData[iPage])==0 ){
686 return walIndexPageRealloc(pWal, iPage, ppPage);
687 }
688 return SQLITE_OK;
689}
690
691/*
692** Return a pointer to the WalCkptInfo structure in the wal-index.
693*/
694static volatile WalCkptInfo *walCkptInfo(Wal *pWal){
695 assert( pWal->nWiData>0 && pWal->apWiData[0] );
696 return (volatile WalCkptInfo*)&(pWal->apWiData[0][sizeof(WalIndexHdr)/2]);
697}
698
699/*
700** Return a pointer to the WalIndexHdr structure in the wal-index.
701*/
702static volatile WalIndexHdr *walIndexHdr(Wal *pWal){
703 assert( pWal->nWiData>0 && pWal->apWiData[0] );
704 return (volatile WalIndexHdr*)pWal->apWiData[0];
705}
706
707/*
708** The argument to this macro must be of type u32. On a little-endian
709** architecture, it returns the u32 value that results from interpreting
710** the 4 bytes as a big-endian value. On a big-endian architecture, it
711** returns the value that would be produced by interpreting the 4 bytes
712** of the input value as a little-endian integer.
713*/
714#define BYTESWAP32(x) ( \
715 (((x)&0x000000FF)<<24) + (((x)&0x0000FF00)<<8) \
716 + (((x)&0x00FF0000)>>8) + (((x)&0xFF000000)>>24) \
717)
718
719/*
720** Generate or extend an 8 byte checksum based on the data in
721** array aByte[] and the initial values of aIn[0] and aIn[1] (or
722** initial values of 0 and 0 if aIn==NULL).
723**
724** The checksum is written back into aOut[] before returning.
725**
726** nByte must be a positive multiple of 8.
727*/
728static void walChecksumBytes(
729 int nativeCksum, /* True for native byte-order, false for non-native */
730 u8 *a, /* Content to be checksummed */
731 int nByte, /* Bytes of content in a[]. Must be a multiple of 8. */
732 const u32 *aIn, /* Initial checksum value input */
733 u32 *aOut /* OUT: Final checksum value output */
734){
735 u32 s1, s2;
736 u32 *aData = (u32 *)a;
737 u32 *aEnd = (u32 *)&a[nByte];
738
739 if( aIn ){
740 s1 = aIn[0];
741 s2 = aIn[1];
742 }else{
743 s1 = s2 = 0;
744 }
745
746 assert( nByte>=8 );
747 assert( (nByte&0x00000007)==0 );
748 assert( nByte<=65536 );
749
750 if( nativeCksum ){
751 do {
752 s1 += *aData++ + s2;
753 s2 += *aData++ + s1;
754 }while( aData<aEnd );
755 }else{
756 do {
757 s1 += BYTESWAP32(aData[0]) + s2;
758 s2 += BYTESWAP32(aData[1]) + s1;
759 aData += 2;
760 }while( aData<aEnd );
761 }
762
763 aOut[0] = s1;
764 aOut[1] = s2;
765}
766
767/*
768** If there is the possibility of concurrent access to the SHM file
769** from multiple threads and/or processes, then do a memory barrier.
770*/
771static void walShmBarrier(Wal *pWal){
772 if( pWal->exclusiveMode!=WAL_HEAPMEMORY_MODE ){
773 sqlite3OsShmBarrier(pWal->pDbFd);
774 }
775}
776
777/*
778** Add the SQLITE_NO_TSAN as part of the return-type of a function
779** definition as a hint that the function contains constructs that
780** might give false-positive TSAN warnings.
781**
782** See tag-20200519-1.
783*/
784#if defined(__clang__) && !defined(SQLITE_NO_TSAN)
785# define SQLITE_NO_TSAN __attribute__((no_sanitize_thread))
786#else
787# define SQLITE_NO_TSAN
788#endif
789
790/*
791** Write the header information in pWal->hdr into the wal-index.
792**
793** The checksum on pWal->hdr is updated before it is written.
794*/
795static SQLITE_NO_TSAN void walIndexWriteHdr(Wal *pWal){
796 volatile WalIndexHdr *aHdr = walIndexHdr(pWal);
797 const int nCksum = offsetof(WalIndexHdr, aCksum);
798
799 assert( pWal->writeLock );
800 pWal->hdr.isInit = 1;
801 pWal->hdr.iVersion = WALINDEX_MAX_VERSION;
802 walChecksumBytes(1, (u8*)&pWal->hdr, nCksum, 0, pWal->hdr.aCksum);
803 /* Possible TSAN false-positive. See tag-20200519-1 */
804 memcpy((void*)&aHdr[1], (const void*)&pWal->hdr, sizeof(WalIndexHdr));
805 walShmBarrier(pWal);
806 memcpy((void*)&aHdr[0], (const void*)&pWal->hdr, sizeof(WalIndexHdr));
807}
808
809/*
810** This function encodes a single frame header and writes it to a buffer
811** supplied by the caller. A frame-header is made up of a series of
812** 4-byte big-endian integers, as follows:
813**
814** 0: Page number.
815** 4: For commit records, the size of the database image in pages
816** after the commit. For all other records, zero.
817** 8: Salt-1 (copied from the wal-header)
818** 12: Salt-2 (copied from the wal-header)
819** 16: Checksum-1.
820** 20: Checksum-2.
821*/
822static void walEncodeFrame(
823 Wal *pWal, /* The write-ahead log */
824 u32 iPage, /* Database page number for frame */
825 u32 nTruncate, /* New db size (or 0 for non-commit frames) */
826 u8 *aData, /* Pointer to page data */
827 u8 *aFrame /* OUT: Write encoded frame here */
828){
829 int nativeCksum; /* True for native byte-order checksums */
830 u32 *aCksum = pWal->hdr.aFrameCksum;
831 assert( WAL_FRAME_HDRSIZE==24 );
832 sqlite3Put4byte(&aFrame[0], iPage);
833 sqlite3Put4byte(&aFrame[4], nTruncate);
834 if( pWal->iReCksum==0 ){
835 memcpy(&aFrame[8], pWal->hdr.aSalt, 8);
836
837 nativeCksum = (pWal->hdr.bigEndCksum==SQLITE_BIGENDIAN);
838 walChecksumBytes(nativeCksum, aFrame, 8, aCksum, aCksum);
839 walChecksumBytes(nativeCksum, aData, pWal->szPage, aCksum, aCksum);
840
841 sqlite3Put4byte(&aFrame[16], aCksum[0]);
842 sqlite3Put4byte(&aFrame[20], aCksum[1]);
843 }else{
844 memset(&aFrame[8], 0, 16);
845 }
846}
847
848/*
849** Check to see if the frame with header in aFrame[] and content
850** in aData[] is valid. If it is a valid frame, fill *piPage and
851** *pnTruncate and return true. Return if the frame is not valid.
852*/
853static int walDecodeFrame(
854 Wal *pWal, /* The write-ahead log */
855 u32 *piPage, /* OUT: Database page number for frame */
856 u32 *pnTruncate, /* OUT: New db size (or 0 if not commit) */
857 u8 *aData, /* Pointer to page data (for checksum) */
858 u8 *aFrame /* Frame data */
859){
860 int nativeCksum; /* True for native byte-order checksums */
861 u32 *aCksum = pWal->hdr.aFrameCksum;
862 u32 pgno; /* Page number of the frame */
863 assert( WAL_FRAME_HDRSIZE==24 );
864
865 /* A frame is only valid if the salt values in the frame-header
866 ** match the salt values in the wal-header.
867 */
868 if( memcmp(&pWal->hdr.aSalt, &aFrame[8], 8)!=0 ){
869 return 0;
870 }
871
872 /* A frame is only valid if the page number is creater than zero.
873 */
874 pgno = sqlite3Get4byte(&aFrame[0]);
875 if( pgno==0 ){
876 return 0;
877 }
878
879 /* A frame is only valid if a checksum of the WAL header,
880 ** all prior frams, the first 16 bytes of this frame-header,
881 ** and the frame-data matches the checksum in the last 8
882 ** bytes of this frame-header.
883 */
884 nativeCksum = (pWal->hdr.bigEndCksum==SQLITE_BIGENDIAN);
885 walChecksumBytes(nativeCksum, aFrame, 8, aCksum, aCksum);
886 walChecksumBytes(nativeCksum, aData, pWal->szPage, aCksum, aCksum);
887 if( aCksum[0]!=sqlite3Get4byte(&aFrame[16])
888 || aCksum[1]!=sqlite3Get4byte(&aFrame[20])
889 ){
890 /* Checksum failed. */
891 return 0;
892 }
893
894 /* If we reach this point, the frame is valid. Return the page number
895 ** and the new database size.
896 */
897 *piPage = pgno;
898 *pnTruncate = sqlite3Get4byte(&aFrame[4]);
899 return 1;
900}
901
902
903#if defined(SQLITE_TEST) && defined(SQLITE_DEBUG)
904/*
905** Names of locks. This routine is used to provide debugging output and is not
906** a part of an ordinary build.
907*/
908static const char *walLockName(int lockIdx){
909 if( lockIdx==WAL_WRITE_LOCK ){
910 return "WRITE-LOCK";
911 }else if( lockIdx==WAL_CKPT_LOCK ){
912 return "CKPT-LOCK";
913 }else if( lockIdx==WAL_RECOVER_LOCK ){
914 return "RECOVER-LOCK";
915 }else{
916 static char zName[15];
917 sqlite3_snprintf(sizeof(zName), zName, "READ-LOCK[%d]",
918 lockIdx-WAL_READ_LOCK(0));
919 return zName;
920 }
921}
922#endif /*defined(SQLITE_TEST) || defined(SQLITE_DEBUG) */
923
924
925/*
926** Set or release locks on the WAL. Locks are either shared or exclusive.
927** A lock cannot be moved directly between shared and exclusive - it must go
928** through the unlocked state first.
929**
930** In locking_mode=EXCLUSIVE, all of these routines become no-ops.
931*/
932static int walLockShared(Wal *pWal, int lockIdx){
933 int rc;
934 if( pWal->exclusiveMode ) return SQLITE_OK;
935 rc = sqlite3OsShmLock(pWal->pDbFd, lockIdx, 1,
936 SQLITE_SHM_LOCK | SQLITE_SHM_SHARED);
937 WALTRACE(("WAL%p: acquire SHARED-%s %s\n", pWal,
938 walLockName(lockIdx), rc ? "failed" : "ok"));
939 VVA_ONLY( pWal->lockError = (u8)(rc!=SQLITE_OK && (rc&0xFF)!=SQLITE_BUSY); )
940 return rc;
941}
942static void walUnlockShared(Wal *pWal, int lockIdx){
943 if( pWal->exclusiveMode ) return;
944 (void)sqlite3OsShmLock(pWal->pDbFd, lockIdx, 1,
945 SQLITE_SHM_UNLOCK | SQLITE_SHM_SHARED);
946 WALTRACE(("WAL%p: release SHARED-%s\n", pWal, walLockName(lockIdx)));
947}
948static int walLockExclusive(Wal *pWal, int lockIdx, int n){
949 int rc;
950 if( pWal->exclusiveMode ) return SQLITE_OK;
951 rc = sqlite3OsShmLock(pWal->pDbFd, lockIdx, n,
952 SQLITE_SHM_LOCK | SQLITE_SHM_EXCLUSIVE);
953 WALTRACE(("WAL%p: acquire EXCLUSIVE-%s cnt=%d %s\n", pWal,
954 walLockName(lockIdx), n, rc ? "failed" : "ok"));
955 VVA_ONLY( pWal->lockError = (u8)(rc!=SQLITE_OK && (rc&0xFF)!=SQLITE_BUSY); )
956 return rc;
957}
958static void walUnlockExclusive(Wal *pWal, int lockIdx, int n){
959 if( pWal->exclusiveMode ) return;
960 (void)sqlite3OsShmLock(pWal->pDbFd, lockIdx, n,
961 SQLITE_SHM_UNLOCK | SQLITE_SHM_EXCLUSIVE);
962 WALTRACE(("WAL%p: release EXCLUSIVE-%s cnt=%d\n", pWal,
963 walLockName(lockIdx), n));
964}
965
966/*
967** Compute a hash on a page number. The resulting hash value must land
968** between 0 and (HASHTABLE_NSLOT-1). The walHashNext() function advances
969** the hash to the next value in the event of a collision.
970*/
971static int walHash(u32 iPage){
972 assert( iPage>0 );
973 assert( (HASHTABLE_NSLOT & (HASHTABLE_NSLOT-1))==0 );
974 return (iPage*HASHTABLE_HASH_1) & (HASHTABLE_NSLOT-1);
975}
976static int walNextHash(int iPriorHash){
977 return (iPriorHash+1)&(HASHTABLE_NSLOT-1);
978}
979
980/*
981** An instance of the WalHashLoc object is used to describe the location
982** of a page hash table in the wal-index. This becomes the return value
983** from walHashGet().
984*/
985typedef struct WalHashLoc WalHashLoc;
986struct WalHashLoc {
987 volatile ht_slot *aHash; /* Start of the wal-index hash table */
988 volatile u32 *aPgno; /* aPgno[1] is the page of first frame indexed */
989 u32 iZero; /* One less than the frame number of first indexed*/
990};
991
992/*
993** Return pointers to the hash table and page number array stored on
994** page iHash of the wal-index. The wal-index is broken into 32KB pages
995** numbered starting from 0.
996**
997** Set output variable pLoc->aHash to point to the start of the hash table
998** in the wal-index file. Set pLoc->iZero to one less than the frame
999** number of the first frame indexed by this hash table. If a
1000** slot in the hash table is set to N, it refers to frame number
1001** (pLoc->iZero+N) in the log.
1002**
1003** Finally, set pLoc->aPgno so that pLoc->aPgno[0] is the page number of the
1004** first frame indexed by the hash table, frame (pLoc->iZero).
1005*/
1006static int walHashGet(
1007 Wal *pWal, /* WAL handle */
1008 int iHash, /* Find the iHash'th table */
1009 WalHashLoc *pLoc /* OUT: Hash table location */
1010){
1011 int rc; /* Return code */
1012
1013 rc = walIndexPage(pWal, iHash, &pLoc->aPgno);
1014 assert( rc==SQLITE_OK || iHash>0 );
1015
1016 if( pLoc->aPgno ){
1017 pLoc->aHash = (volatile ht_slot *)&pLoc->aPgno[HASHTABLE_NPAGE];
1018 if( iHash==0 ){
1019 pLoc->aPgno = &pLoc->aPgno[WALINDEX_HDR_SIZE/sizeof(u32)];
1020 pLoc->iZero = 0;
1021 }else{
1022 pLoc->iZero = HASHTABLE_NPAGE_ONE + (iHash-1)*HASHTABLE_NPAGE;
1023 }
1024 }else if( NEVER(rc==SQLITE_OK) ){
1025 rc = SQLITE_ERROR;
1026 }
1027 return rc;
1028}
1029
1030/*
1031** Return the number of the wal-index page that contains the hash-table
1032** and page-number array that contain entries corresponding to WAL frame
1033** iFrame. The wal-index is broken up into 32KB pages. Wal-index pages
1034** are numbered starting from 0.
1035*/
1036static int walFramePage(u32 iFrame){
1037 int iHash = (iFrame+HASHTABLE_NPAGE-HASHTABLE_NPAGE_ONE-1) / HASHTABLE_NPAGE;
1038 assert( (iHash==0 || iFrame>HASHTABLE_NPAGE_ONE)
1039 && (iHash>=1 || iFrame<=HASHTABLE_NPAGE_ONE)
1040 && (iHash<=1 || iFrame>(HASHTABLE_NPAGE_ONE+HASHTABLE_NPAGE))
1041 && (iHash>=2 || iFrame<=HASHTABLE_NPAGE_ONE+HASHTABLE_NPAGE)
1042 && (iHash<=2 || iFrame>(HASHTABLE_NPAGE_ONE+2*HASHTABLE_NPAGE))
1043 );
1044 assert( iHash>=0 );
1045 return iHash;
1046}
1047
1048/*
1049** Return the page number associated with frame iFrame in this WAL.
1050*/
1051static u32 walFramePgno(Wal *pWal, u32 iFrame){
1052 int iHash = walFramePage(iFrame);
1053 if( iHash==0 ){
1054 return pWal->apWiData[0][WALINDEX_HDR_SIZE/sizeof(u32) + iFrame - 1];
1055 }
1056 return pWal->apWiData[iHash][(iFrame-1-HASHTABLE_NPAGE_ONE)%HASHTABLE_NPAGE];
1057}
1058
1059/*
1060** Remove entries from the hash table that point to WAL slots greater
1061** than pWal->hdr.mxFrame.
1062**
1063** This function is called whenever pWal->hdr.mxFrame is decreased due
1064** to a rollback or savepoint.
1065**
1066** At most only the hash table containing pWal->hdr.mxFrame needs to be
1067** updated. Any later hash tables will be automatically cleared when
1068** pWal->hdr.mxFrame advances to the point where those hash tables are
1069** actually needed.
1070*/
1071static void walCleanupHash(Wal *pWal){
1072 WalHashLoc sLoc; /* Hash table location */
1073 int iLimit = 0; /* Zero values greater than this */
1074 int nByte; /* Number of bytes to zero in aPgno[] */
1075 int i; /* Used to iterate through aHash[] */
1076
1077 assert( pWal->writeLock );
1078 testcase( pWal->hdr.mxFrame==HASHTABLE_NPAGE_ONE-1 );
1079 testcase( pWal->hdr.mxFrame==HASHTABLE_NPAGE_ONE );
1080 testcase( pWal->hdr.mxFrame==HASHTABLE_NPAGE_ONE+1 );
1081
1082 if( pWal->hdr.mxFrame==0 ) return;
1083
1084 /* Obtain pointers to the hash-table and page-number array containing
1085 ** the entry that corresponds to frame pWal->hdr.mxFrame. It is guaranteed
1086 ** that the page said hash-table and array reside on is already mapped.(1)
1087 */
1088 assert( pWal->nWiData>walFramePage(pWal->hdr.mxFrame) );
1089 assert( pWal->apWiData[walFramePage(pWal->hdr.mxFrame)] );
1090 i = walHashGet(pWal, walFramePage(pWal->hdr.mxFrame), &sLoc);
1091 if( NEVER(i) ) return; /* Defense-in-depth, in case (1) above is wrong */
1092
1093 /* Zero all hash-table entries that correspond to frame numbers greater
1094 ** than pWal->hdr.mxFrame.
1095 */
1096 iLimit = pWal->hdr.mxFrame - sLoc.iZero;
1097 assert( iLimit>0 );
1098 for(i=0; i<HASHTABLE_NSLOT; i++){
1099 if( sLoc.aHash[i]>iLimit ){
1100 sLoc.aHash[i] = 0;
1101 }
1102 }
1103
1104 /* Zero the entries in the aPgno array that correspond to frames with
1105 ** frame numbers greater than pWal->hdr.mxFrame.
1106 */
1107 nByte = (int)((char *)sLoc.aHash - (char *)&sLoc.aPgno[iLimit]);
1108 assert( nByte>=0 );
1109 memset((void *)&sLoc.aPgno[iLimit], 0, nByte);
1110
1111#ifdef SQLITE_ENABLE_EXPENSIVE_ASSERT
1112 /* Verify that the every entry in the mapping region is still reachable
1113 ** via the hash table even after the cleanup.
1114 */
1115 if( iLimit ){
1116 int j; /* Loop counter */
1117 int iKey; /* Hash key */
1118 for(j=0; j<iLimit; j++){
1119 for(iKey=walHash(sLoc.aPgno[j]);sLoc.aHash[iKey];iKey=walNextHash(iKey)){
1120 if( sLoc.aHash[iKey]==j+1 ) break;
1121 }
1122 assert( sLoc.aHash[iKey]==j+1 );
1123 }
1124 }
1125#endif /* SQLITE_ENABLE_EXPENSIVE_ASSERT */
1126}
1127
1128
1129/*
1130** Set an entry in the wal-index that will map database page number
1131** pPage into WAL frame iFrame.
1132*/
1133static int walIndexAppend(Wal *pWal, u32 iFrame, u32 iPage){
1134 int rc; /* Return code */
1135 WalHashLoc sLoc; /* Wal-index hash table location */
1136
1137 rc = walHashGet(pWal, walFramePage(iFrame), &sLoc);
1138
1139 /* Assuming the wal-index file was successfully mapped, populate the
1140 ** page number array and hash table entry.
1141 */
1142 if( rc==SQLITE_OK ){
1143 int iKey; /* Hash table key */
1144 int idx; /* Value to write to hash-table slot */
1145 int nCollide; /* Number of hash collisions */
1146
1147 idx = iFrame - sLoc.iZero;
1148 assert( idx <= HASHTABLE_NSLOT/2 + 1 );
1149
1150 /* If this is the first entry to be added to this hash-table, zero the
1151 ** entire hash table and aPgno[] array before proceeding.
1152 */
1153 if( idx==1 ){
1154 int nByte = (int)((u8*)&sLoc.aHash[HASHTABLE_NSLOT] - (u8*)sLoc.aPgno);
1155 assert( nByte>=0 );
1156 memset((void*)sLoc.aPgno, 0, nByte);
1157 }
1158
1159 /* If the entry in aPgno[] is already set, then the previous writer
1160 ** must have exited unexpectedly in the middle of a transaction (after
1161 ** writing one or more dirty pages to the WAL to free up memory).
1162 ** Remove the remnants of that writers uncommitted transaction from
1163 ** the hash-table before writing any new entries.
1164 */
1165 if( sLoc.aPgno[idx-1] ){
1166 walCleanupHash(pWal);
1167 assert( !sLoc.aPgno[idx-1] );
1168 }
1169
1170 /* Write the aPgno[] array entry and the hash-table slot. */
1171 nCollide = idx;
1172 for(iKey=walHash(iPage); sLoc.aHash[iKey]; iKey=walNextHash(iKey)){
1173 if( (nCollide--)==0 ) return SQLITE_CORRUPT_BKPT;
1174 }
1175 sLoc.aPgno[idx-1] = iPage;
1176 AtomicStore(&sLoc.aHash[iKey], (ht_slot)idx);
1177
1178#ifdef SQLITE_ENABLE_EXPENSIVE_ASSERT
1179 /* Verify that the number of entries in the hash table exactly equals
1180 ** the number of entries in the mapping region.
1181 */
1182 {
1183 int i; /* Loop counter */
1184 int nEntry = 0; /* Number of entries in the hash table */
1185 for(i=0; i<HASHTABLE_NSLOT; i++){ if( sLoc.aHash[i] ) nEntry++; }
1186 assert( nEntry==idx );
1187 }
1188
1189 /* Verify that the every entry in the mapping region is reachable
1190 ** via the hash table. This turns out to be a really, really expensive
1191 ** thing to check, so only do this occasionally - not on every
1192 ** iteration.
1193 */
1194 if( (idx&0x3ff)==0 ){
1195 int i; /* Loop counter */
1196 for(i=0; i<idx; i++){
1197 for(iKey=walHash(sLoc.aPgno[i]);
1198 sLoc.aHash[iKey];
1199 iKey=walNextHash(iKey)){
1200 if( sLoc.aHash[iKey]==i+1 ) break;
1201 }
1202 assert( sLoc.aHash[iKey]==i+1 );
1203 }
1204 }
1205#endif /* SQLITE_ENABLE_EXPENSIVE_ASSERT */
1206 }
1207
1208 return rc;
1209}
1210
1211
1212/*
1213** Recover the wal-index by reading the write-ahead log file.
1214**
1215** This routine first tries to establish an exclusive lock on the
1216** wal-index to prevent other threads/processes from doing anything
1217** with the WAL or wal-index while recovery is running. The
1218** WAL_RECOVER_LOCK is also held so that other threads will know
1219** that this thread is running recovery. If unable to establish
1220** the necessary locks, this routine returns SQLITE_BUSY.
1221*/
1222static int walIndexRecover(Wal *pWal){
1223 int rc; /* Return Code */
1224 i64 nSize; /* Size of log file */
1225 u32 aFrameCksum[2] = {0, 0};
1226 int iLock; /* Lock offset to lock for checkpoint */
1227
1228 /* Obtain an exclusive lock on all byte in the locking range not already
1229 ** locked by the caller. The caller is guaranteed to have locked the
1230 ** WAL_WRITE_LOCK byte, and may have also locked the WAL_CKPT_LOCK byte.
1231 ** If successful, the same bytes that are locked here are unlocked before
1232 ** this function returns.
1233 */
1234 assert( pWal->ckptLock==1 || pWal->ckptLock==0 );
1235 assert( WAL_ALL_BUT_WRITE==WAL_WRITE_LOCK+1 );
1236 assert( WAL_CKPT_LOCK==WAL_ALL_BUT_WRITE );
1237 assert( pWal->writeLock );
1238 iLock = WAL_ALL_BUT_WRITE + pWal->ckptLock;
1239 rc = walLockExclusive(pWal, iLock, WAL_READ_LOCK(0)-iLock);
1240 if( rc ){
1241 return rc;
1242 }
1243
1244 WALTRACE(("WAL%p: recovery begin...\n", pWal));
1245
1246 memset(&pWal->hdr, 0, sizeof(WalIndexHdr));
1247
1248 rc = sqlite3OsFileSize(pWal->pWalFd, &nSize);
1249 if( rc!=SQLITE_OK ){
1250 goto recovery_error;
1251 }
1252
1253 if( nSize>WAL_HDRSIZE ){
1254 u8 aBuf[WAL_HDRSIZE]; /* Buffer to load WAL header into */
1255 u32 *aPrivate = 0; /* Heap copy of *-shm hash being populated */
1256 u8 *aFrame = 0; /* Malloc'd buffer to load entire frame */
1257 int szFrame; /* Number of bytes in buffer aFrame[] */
1258 u8 *aData; /* Pointer to data part of aFrame buffer */
1259 int szPage; /* Page size according to the log */
1260 u32 magic; /* Magic value read from WAL header */
1261 u32 version; /* Magic value read from WAL header */
1262 int isValid; /* True if this frame is valid */
1263 u32 iPg; /* Current 32KB wal-index page */
1264 u32 iLastFrame; /* Last frame in wal, based on nSize alone */
1265
1266 /* Read in the WAL header. */
1267 rc = sqlite3OsRead(pWal->pWalFd, aBuf, WAL_HDRSIZE, 0);
1268 if( rc!=SQLITE_OK ){
1269 goto recovery_error;
1270 }
1271
1272 /* If the database page size is not a power of two, or is greater than
1273 ** SQLITE_MAX_PAGE_SIZE, conclude that the WAL file contains no valid
1274 ** data. Similarly, if the 'magic' value is invalid, ignore the whole
1275 ** WAL file.
1276 */
1277 magic = sqlite3Get4byte(&aBuf[0]);
1278 szPage = sqlite3Get4byte(&aBuf[8]);
1279 if( (magic&0xFFFFFFFE)!=WAL_MAGIC
1280 || szPage&(szPage-1)
1281 || szPage>SQLITE_MAX_PAGE_SIZE
1282 || szPage<512
1283 ){
1284 goto finished;
1285 }
1286 pWal->hdr.bigEndCksum = (u8)(magic&0x00000001);
1287 pWal->szPage = szPage;
1288 pWal->nCkpt = sqlite3Get4byte(&aBuf[12]);
1289 memcpy(&pWal->hdr.aSalt, &aBuf[16], 8);
1290
1291 /* Verify that the WAL header checksum is correct */
1292 walChecksumBytes(pWal->hdr.bigEndCksum==SQLITE_BIGENDIAN,
1293 aBuf, WAL_HDRSIZE-2*4, 0, pWal->hdr.aFrameCksum
1294 );
1295 if( pWal->hdr.aFrameCksum[0]!=sqlite3Get4byte(&aBuf[24])
1296 || pWal->hdr.aFrameCksum[1]!=sqlite3Get4byte(&aBuf[28])
1297 ){
1298 goto finished;
1299 }
1300
1301 /* Verify that the version number on the WAL format is one that
1302 ** are able to understand */
1303 version = sqlite3Get4byte(&aBuf[4]);
1304 if( version!=WAL_MAX_VERSION ){
1305 rc = SQLITE_CANTOPEN_BKPT;
1306 goto finished;
1307 }
1308
1309 /* Malloc a buffer to read frames into. */
1310 szFrame = szPage + WAL_FRAME_HDRSIZE;
1311 aFrame = (u8 *)sqlite3_malloc64(szFrame + WALINDEX_PGSZ);
1312 if( !aFrame ){
1313 rc = SQLITE_NOMEM_BKPT;
1314 goto recovery_error;
1315 }
1316 aData = &aFrame[WAL_FRAME_HDRSIZE];
1317 aPrivate = (u32*)&aData[szPage];
1318
1319 /* Read all frames from the log file. */
1320 iLastFrame = (nSize - WAL_HDRSIZE) / szFrame;
1321 for(iPg=0; iPg<=(u32)walFramePage(iLastFrame); iPg++){
1322 u32 *aShare;
1323 u32 iFrame; /* Index of last frame read */
1324 u32 iLast = MIN(iLastFrame, HASHTABLE_NPAGE_ONE+iPg*HASHTABLE_NPAGE);
1325 u32 iFirst = 1 + (iPg==0?0:HASHTABLE_NPAGE_ONE+(iPg-1)*HASHTABLE_NPAGE);
1326 u32 nHdr, nHdr32;
1327 rc = walIndexPage(pWal, iPg, (volatile u32**)&aShare);
1328 assert( aShare!=0 || rc!=SQLITE_OK );
1329 if( aShare==0 ) break;
1330 pWal->apWiData[iPg] = aPrivate;
1331
1332 for(iFrame=iFirst; iFrame<=iLast; iFrame++){
1333 i64 iOffset = walFrameOffset(iFrame, szPage);
1334 u32 pgno; /* Database page number for frame */
1335 u32 nTruncate; /* dbsize field from frame header */
1336
1337 /* Read and decode the next log frame. */
1338 rc = sqlite3OsRead(pWal->pWalFd, aFrame, szFrame, iOffset);
1339 if( rc!=SQLITE_OK ) break;
1340 isValid = walDecodeFrame(pWal, &pgno, &nTruncate, aData, aFrame);
1341 if( !isValid ) break;
1342 rc = walIndexAppend(pWal, iFrame, pgno);
1343 if( NEVER(rc!=SQLITE_OK) ) break;
1344
1345 /* If nTruncate is non-zero, this is a commit record. */
1346 if( nTruncate ){
1347 pWal->hdr.mxFrame = iFrame;
1348 pWal->hdr.nPage = nTruncate;
1349 pWal->hdr.szPage = (u16)((szPage&0xff00) | (szPage>>16));
1350 testcase( szPage<=32768 );
1351 testcase( szPage>=65536 );
1352 aFrameCksum[0] = pWal->hdr.aFrameCksum[0];
1353 aFrameCksum[1] = pWal->hdr.aFrameCksum[1];
1354 }
1355 }
1356 pWal->apWiData[iPg] = aShare;
1357 nHdr = (iPg==0 ? WALINDEX_HDR_SIZE : 0);
1358 nHdr32 = nHdr / sizeof(u32);
1359#ifndef SQLITE_SAFER_WALINDEX_RECOVERY
1360 /* Memcpy() should work fine here, on all reasonable implementations.
1361 ** Technically, memcpy() might change the destination to some
1362 ** intermediate value before setting to the final value, and that might
1363 ** cause a concurrent reader to malfunction. Memcpy() is allowed to
1364 ** do that, according to the spec, but no memcpy() implementation that
1365 ** we know of actually does that, which is why we say that memcpy()
1366 ** is safe for this. Memcpy() is certainly a lot faster.
1367 */
1368 memcpy(&aShare[nHdr32], &aPrivate[nHdr32], WALINDEX_PGSZ-nHdr);
1369#else
1370 /* In the event that some platform is found for which memcpy()
1371 ** changes the destination to some intermediate value before
1372 ** setting the final value, this alternative copy routine is
1373 ** provided.
1374 */
1375 {
1376 int i;
1377 for(i=nHdr32; i<WALINDEX_PGSZ/sizeof(u32); i++){
1378 if( aShare[i]!=aPrivate[i] ){
1379 /* Atomic memory operations are not required here because if
1380 ** the value needs to be changed, that means it is not being
1381 ** accessed concurrently. */
1382 aShare[i] = aPrivate[i];
1383 }
1384 }
1385 }
1386#endif
1387 if( iFrame<=iLast ) break;
1388 }
1389
1390 sqlite3_free(aFrame);
1391 }
1392
1393finished:
1394 if( rc==SQLITE_OK ){
1395 volatile WalCkptInfo *pInfo;
1396 int i;
1397 pWal->hdr.aFrameCksum[0] = aFrameCksum[0];
1398 pWal->hdr.aFrameCksum[1] = aFrameCksum[1];
1399 walIndexWriteHdr(pWal);
1400
1401 /* Reset the checkpoint-header. This is safe because this thread is
1402 ** currently holding locks that exclude all other writers and
1403 ** checkpointers. Then set the values of read-mark slots 1 through N.
1404 */
1405 pInfo = walCkptInfo(pWal);
1406 pInfo->nBackfill = 0;
1407 pInfo->nBackfillAttempted = pWal->hdr.mxFrame;
1408 pInfo->aReadMark[0] = 0;
1409 for(i=1; i<WAL_NREADER; i++){
1410 rc = walLockExclusive(pWal, WAL_READ_LOCK(i), 1);
1411 if( rc==SQLITE_OK ){
1412 if( i==1 && pWal->hdr.mxFrame ){
1413 pInfo->aReadMark[i] = pWal->hdr.mxFrame;
1414 }else{
1415 pInfo->aReadMark[i] = READMARK_NOT_USED;
1416 }
1417 walUnlockExclusive(pWal, WAL_READ_LOCK(i), 1);
1418 }else if( rc!=SQLITE_BUSY ){
1419 goto recovery_error;
1420 }
1421 }
1422
1423 /* If more than one frame was recovered from the log file, report an
1424 ** event via sqlite3_log(). This is to help with identifying performance
1425 ** problems caused by applications routinely shutting down without
1426 ** checkpointing the log file.
1427 */
1428 if( pWal->hdr.nPage ){
1429 sqlite3_log(SQLITE_NOTICE_RECOVER_WAL,
1430 "recovered %d frames from WAL file %s",
1431 pWal->hdr.mxFrame, pWal->zWalName
1432 );
1433 }
1434 }
1435
1436recovery_error:
1437 WALTRACE(("WAL%p: recovery %s\n", pWal, rc ? "failed" : "ok"));
1438 walUnlockExclusive(pWal, iLock, WAL_READ_LOCK(0)-iLock);
1439 return rc;
1440}
1441
1442/*
1443** Close an open wal-index.
1444*/
1445static void walIndexClose(Wal *pWal, int isDelete){
1446 if( pWal->exclusiveMode==WAL_HEAPMEMORY_MODE || pWal->bShmUnreliable ){
1447 int i;
1448 for(i=0; i<pWal->nWiData; i++){
1449 sqlite3_free((void *)pWal->apWiData[i]);
1450 pWal->apWiData[i] = 0;
1451 }
1452 }
1453 if( pWal->exclusiveMode!=WAL_HEAPMEMORY_MODE ){
1454 sqlite3OsShmUnmap(pWal->pDbFd, isDelete);
1455 }
1456}
1457
1458/*
1459** Open a connection to the WAL file zWalName. The database file must
1460** already be opened on connection pDbFd. The buffer that zWalName points
1461** to must remain valid for the lifetime of the returned Wal* handle.
1462**
1463** A SHARED lock should be held on the database file when this function
1464** is called. The purpose of this SHARED lock is to prevent any other
1465** client from unlinking the WAL or wal-index file. If another process
1466** were to do this just after this client opened one of these files, the
1467** system would be badly broken.
1468**
1469** If the log file is successfully opened, SQLITE_OK is returned and
1470** *ppWal is set to point to a new WAL handle. If an error occurs,
1471** an SQLite error code is returned and *ppWal is left unmodified.
1472*/
1473int sqlite3WalOpen(
1474 sqlite3_vfs *pVfs, /* vfs module to open wal and wal-index */
1475 sqlite3_file *pDbFd, /* The open database file */
1476 const char *zWalName, /* Name of the WAL file */
1477 int bNoShm, /* True to run in heap-memory mode */
1478 i64 mxWalSize, /* Truncate WAL to this size on reset */
1479 Wal **ppWal /* OUT: Allocated Wal handle */
1480){
1481 int rc; /* Return Code */
1482 Wal *pRet; /* Object to allocate and return */
1483 int flags; /* Flags passed to OsOpen() */
1484
1485 assert( zWalName && zWalName[0] );
1486 assert( pDbFd );
1487
1488 /* Verify the values of various constants. Any changes to the values
1489 ** of these constants would result in an incompatible on-disk format
1490 ** for the -shm file. Any change that causes one of these asserts to
1491 ** fail is a backward compatibility problem, even if the change otherwise
1492 ** works.
1493 **
1494 ** This table also serves as a helpful cross-reference when trying to
1495 ** interpret hex dumps of the -shm file.
1496 */
1497 assert( 48 == sizeof(WalIndexHdr) );
1498 assert( 40 == sizeof(WalCkptInfo) );
1499 assert( 120 == WALINDEX_LOCK_OFFSET );
1500 assert( 136 == WALINDEX_HDR_SIZE );
1501 assert( 4096 == HASHTABLE_NPAGE );
1502 assert( 4062 == HASHTABLE_NPAGE_ONE );
1503 assert( 8192 == HASHTABLE_NSLOT );
1504 assert( 383 == HASHTABLE_HASH_1 );
1505 assert( 32768 == WALINDEX_PGSZ );
1506 assert( 8 == SQLITE_SHM_NLOCK );
1507 assert( 5 == WAL_NREADER );
1508 assert( 24 == WAL_FRAME_HDRSIZE );
1509 assert( 32 == WAL_HDRSIZE );
1510 assert( 120 == WALINDEX_LOCK_OFFSET + WAL_WRITE_LOCK );
1511 assert( 121 == WALINDEX_LOCK_OFFSET + WAL_CKPT_LOCK );
1512 assert( 122 == WALINDEX_LOCK_OFFSET + WAL_RECOVER_LOCK );
1513 assert( 123 == WALINDEX_LOCK_OFFSET + WAL_READ_LOCK(0) );
1514 assert( 124 == WALINDEX_LOCK_OFFSET + WAL_READ_LOCK(1) );
1515 assert( 125 == WALINDEX_LOCK_OFFSET + WAL_READ_LOCK(2) );
1516 assert( 126 == WALINDEX_LOCK_OFFSET + WAL_READ_LOCK(3) );
1517 assert( 127 == WALINDEX_LOCK_OFFSET + WAL_READ_LOCK(4) );
1518
1519 /* In the amalgamation, the os_unix.c and os_win.c source files come before
1520 ** this source file. Verify that the #defines of the locking byte offsets
1521 ** in os_unix.c and os_win.c agree with the WALINDEX_LOCK_OFFSET value.
1522 ** For that matter, if the lock offset ever changes from its initial design
1523 ** value of 120, we need to know that so there is an assert() to check it.
1524 */
1525#ifdef WIN_SHM_BASE
1526 assert( WIN_SHM_BASE==WALINDEX_LOCK_OFFSET );
1527#endif
1528#ifdef UNIX_SHM_BASE
1529 assert( UNIX_SHM_BASE==WALINDEX_LOCK_OFFSET );
1530#endif
1531
1532
1533 /* Allocate an instance of struct Wal to return. */
1534 *ppWal = 0;
1535 pRet = (Wal*)sqlite3MallocZero(sizeof(Wal) + pVfs->szOsFile);
1536 if( !pRet ){
1537 return SQLITE_NOMEM_BKPT;
1538 }
1539
1540 pRet->pVfs = pVfs;
1541 pRet->pWalFd = (sqlite3_file *)&pRet[1];
1542 pRet->pDbFd = pDbFd;
1543 pRet->readLock = -1;
1544 pRet->mxWalSize = mxWalSize;
1545 pRet->zWalName = zWalName;
1546 pRet->syncHeader = 1;
1547 pRet->padToSectorBoundary = 1;
1548 pRet->exclusiveMode = (bNoShm ? WAL_HEAPMEMORY_MODE: WAL_NORMAL_MODE);
1549
1550 /* Open file handle on the write-ahead log file. */
1551 flags = (SQLITE_OPEN_READWRITE|SQLITE_OPEN_CREATE|SQLITE_OPEN_WAL);
1552 rc = sqlite3OsOpen(pVfs, zWalName, pRet->pWalFd, flags, &flags);
1553 if( rc==SQLITE_OK && flags&SQLITE_OPEN_READONLY ){
1554 pRet->readOnly = WAL_RDONLY;
1555 }
1556
1557 if( rc!=SQLITE_OK ){
1558 walIndexClose(pRet, 0);
1559 sqlite3OsClose(pRet->pWalFd);
1560 sqlite3_free(pRet);
1561 }else{
1562 int iDC = sqlite3OsDeviceCharacteristics(pDbFd);
1563 if( iDC & SQLITE_IOCAP_SEQUENTIAL ){ pRet->syncHeader = 0; }
1564 if( iDC & SQLITE_IOCAP_POWERSAFE_OVERWRITE ){
1565 pRet->padToSectorBoundary = 0;
1566 }
1567 *ppWal = pRet;
1568 WALTRACE(("WAL%d: opened\n", pRet));
1569 }
1570 return rc;
1571}
1572
1573/*
1574** Change the size to which the WAL file is trucated on each reset.
1575*/
1576void sqlite3WalLimit(Wal *pWal, i64 iLimit){
1577 if( pWal ) pWal->mxWalSize = iLimit;
1578}
1579
1580/*
1581** Find the smallest page number out of all pages held in the WAL that
1582** has not been returned by any prior invocation of this method on the
1583** same WalIterator object. Write into *piFrame the frame index where
1584** that page was last written into the WAL. Write into *piPage the page
1585** number.
1586**
1587** Return 0 on success. If there are no pages in the WAL with a page
1588** number larger than *piPage, then return 1.
1589*/
1590static int walIteratorNext(
1591 WalIterator *p, /* Iterator */
1592 u32 *piPage, /* OUT: The page number of the next page */
1593 u32 *piFrame /* OUT: Wal frame index of next page */
1594){
1595 u32 iMin; /* Result pgno must be greater than iMin */
1596 u32 iRet = 0xFFFFFFFF; /* 0xffffffff is never a valid page number */
1597 int i; /* For looping through segments */
1598
1599 iMin = p->iPrior;
1600 assert( iMin<0xffffffff );
1601 for(i=p->nSegment-1; i>=0; i--){
1602 struct WalSegment *pSegment = &p->aSegment[i];
1603 while( pSegment->iNext<pSegment->nEntry ){
1604 u32 iPg = pSegment->aPgno[pSegment->aIndex[pSegment->iNext]];
1605 if( iPg>iMin ){
1606 if( iPg<iRet ){
1607 iRet = iPg;
1608 *piFrame = pSegment->iZero + pSegment->aIndex[pSegment->iNext];
1609 }
1610 break;
1611 }
1612 pSegment->iNext++;
1613 }
1614 }
1615
1616 *piPage = p->iPrior = iRet;
1617 return (iRet==0xFFFFFFFF);
1618}
1619
1620/*
1621** This function merges two sorted lists into a single sorted list.
1622**
1623** aLeft[] and aRight[] are arrays of indices. The sort key is
1624** aContent[aLeft[]] and aContent[aRight[]]. Upon entry, the following
1625** is guaranteed for all J<K:
1626**
1627** aContent[aLeft[J]] < aContent[aLeft[K]]
1628** aContent[aRight[J]] < aContent[aRight[K]]
1629**
1630** This routine overwrites aRight[] with a new (probably longer) sequence
1631** of indices such that the aRight[] contains every index that appears in
1632** either aLeft[] or the old aRight[] and such that the second condition
1633** above is still met.
1634**
1635** The aContent[aLeft[X]] values will be unique for all X. And the
1636** aContent[aRight[X]] values will be unique too. But there might be
1637** one or more combinations of X and Y such that
1638**
1639** aLeft[X]!=aRight[Y] && aContent[aLeft[X]] == aContent[aRight[Y]]
1640**
1641** When that happens, omit the aLeft[X] and use the aRight[Y] index.
1642*/
1643static void walMerge(
1644 const u32 *aContent, /* Pages in wal - keys for the sort */
1645 ht_slot *aLeft, /* IN: Left hand input list */
1646 int nLeft, /* IN: Elements in array *paLeft */
1647 ht_slot **paRight, /* IN/OUT: Right hand input list */
1648 int *pnRight, /* IN/OUT: Elements in *paRight */
1649 ht_slot *aTmp /* Temporary buffer */
1650){
1651 int iLeft = 0; /* Current index in aLeft */
1652 int iRight = 0; /* Current index in aRight */
1653 int iOut = 0; /* Current index in output buffer */
1654 int nRight = *pnRight;
1655 ht_slot *aRight = *paRight;
1656
1657 assert( nLeft>0 && nRight>0 );
1658 while( iRight<nRight || iLeft<nLeft ){
1659 ht_slot logpage;
1660 Pgno dbpage;
1661
1662 if( (iLeft<nLeft)
1663 && (iRight>=nRight || aContent[aLeft[iLeft]]<aContent[aRight[iRight]])
1664 ){
1665 logpage = aLeft[iLeft++];
1666 }else{
1667 logpage = aRight[iRight++];
1668 }
1669 dbpage = aContent[logpage];
1670
1671 aTmp[iOut++] = logpage;
1672 if( iLeft<nLeft && aContent[aLeft[iLeft]]==dbpage ) iLeft++;
1673
1674 assert( iLeft>=nLeft || aContent[aLeft[iLeft]]>dbpage );
1675 assert( iRight>=nRight || aContent[aRight[iRight]]>dbpage );
1676 }
1677
1678 *paRight = aLeft;
1679 *pnRight = iOut;
1680 memcpy(aLeft, aTmp, sizeof(aTmp[0])*iOut);
1681}
1682
1683/*
1684** Sort the elements in list aList using aContent[] as the sort key.
1685** Remove elements with duplicate keys, preferring to keep the
1686** larger aList[] values.
1687**
1688** The aList[] entries are indices into aContent[]. The values in
1689** aList[] are to be sorted so that for all J<K:
1690**
1691** aContent[aList[J]] < aContent[aList[K]]
1692**
1693** For any X and Y such that
1694**
1695** aContent[aList[X]] == aContent[aList[Y]]
1696**
1697** Keep the larger of the two values aList[X] and aList[Y] and discard
1698** the smaller.
1699*/
1700static void walMergesort(
1701 const u32 *aContent, /* Pages in wal */
1702 ht_slot *aBuffer, /* Buffer of at least *pnList items to use */
1703 ht_slot *aList, /* IN/OUT: List to sort */
1704 int *pnList /* IN/OUT: Number of elements in aList[] */
1705){
1706 struct Sublist {
1707 int nList; /* Number of elements in aList */
1708 ht_slot *aList; /* Pointer to sub-list content */
1709 };
1710
1711 const int nList = *pnList; /* Size of input list */
1712 int nMerge = 0; /* Number of elements in list aMerge */
1713 ht_slot *aMerge = 0; /* List to be merged */
1714 int iList; /* Index into input list */
1715 u32 iSub = 0; /* Index into aSub array */
1716 struct Sublist aSub[13]; /* Array of sub-lists */
1717
1718 memset(aSub, 0, sizeof(aSub));
1719 assert( nList<=HASHTABLE_NPAGE && nList>0 );
1720 assert( HASHTABLE_NPAGE==(1<<(ArraySize(aSub)-1)) );
1721
1722 for(iList=0; iList<nList; iList++){
1723 nMerge = 1;
1724 aMerge = &aList[iList];
1725 for(iSub=0; iList & (1<<iSub); iSub++){
1726 struct Sublist *p;
1727 assert( iSub<ArraySize(aSub) );
1728 p = &aSub[iSub];
1729 assert( p->aList && p->nList<=(1<<iSub) );
1730 assert( p->aList==&aList[iList&~((2<<iSub)-1)] );
1731 walMerge(aContent, p->aList, p->nList, &aMerge, &nMerge, aBuffer);
1732 }
1733 aSub[iSub].aList = aMerge;
1734 aSub[iSub].nList = nMerge;
1735 }
1736
1737 for(iSub++; iSub<ArraySize(aSub); iSub++){
1738 if( nList & (1<<iSub) ){
1739 struct Sublist *p;
1740 assert( iSub<ArraySize(aSub) );
1741 p = &aSub[iSub];
1742 assert( p->nList<=(1<<iSub) );
1743 assert( p->aList==&aList[nList&~((2<<iSub)-1)] );
1744 walMerge(aContent, p->aList, p->nList, &aMerge, &nMerge, aBuffer);
1745 }
1746 }
1747 assert( aMerge==aList );
1748 *pnList = nMerge;
1749
1750#ifdef SQLITE_DEBUG
1751 {
1752 int i;
1753 for(i=1; i<*pnList; i++){
1754 assert( aContent[aList[i]] > aContent[aList[i-1]] );
1755 }
1756 }
1757#endif
1758}
1759
1760/*
1761** Free an iterator allocated by walIteratorInit().
1762*/
1763static void walIteratorFree(WalIterator *p){
1764 sqlite3_free(p);
1765}
1766
1767/*
1768** Construct a WalInterator object that can be used to loop over all
1769** pages in the WAL following frame nBackfill in ascending order. Frames
1770** nBackfill or earlier may be included - excluding them is an optimization
1771** only. The caller must hold the checkpoint lock.
1772**
1773** On success, make *pp point to the newly allocated WalInterator object
1774** return SQLITE_OK. Otherwise, return an error code. If this routine
1775** returns an error, the value of *pp is undefined.
1776**
1777** The calling routine should invoke walIteratorFree() to destroy the
1778** WalIterator object when it has finished with it.
1779*/
1780static int walIteratorInit(Wal *pWal, u32 nBackfill, WalIterator **pp){
1781 WalIterator *p; /* Return value */
1782 int nSegment; /* Number of segments to merge */
1783 u32 iLast; /* Last frame in log */
1784 sqlite3_int64 nByte; /* Number of bytes to allocate */
1785 int i; /* Iterator variable */
1786 ht_slot *aTmp; /* Temp space used by merge-sort */
1787 int rc = SQLITE_OK; /* Return Code */
1788
1789 /* This routine only runs while holding the checkpoint lock. And
1790 ** it only runs if there is actually content in the log (mxFrame>0).
1791 */
1792 assert( pWal->ckptLock && pWal->hdr.mxFrame>0 );
1793 iLast = pWal->hdr.mxFrame;
1794
1795 /* Allocate space for the WalIterator object. */
1796 nSegment = walFramePage(iLast) + 1;
1797 nByte = sizeof(WalIterator)
1798 + (nSegment-1)*sizeof(struct WalSegment)
1799 + iLast*sizeof(ht_slot);
1800 p = (WalIterator *)sqlite3_malloc64(nByte);
1801 if( !p ){
1802 return SQLITE_NOMEM_BKPT;
1803 }
1804 memset(p, 0, nByte);
1805 p->nSegment = nSegment;
1806
1807 /* Allocate temporary space used by the merge-sort routine. This block
1808 ** of memory will be freed before this function returns.
1809 */
1810 aTmp = (ht_slot *)sqlite3_malloc64(
1811 sizeof(ht_slot) * (iLast>HASHTABLE_NPAGE?HASHTABLE_NPAGE:iLast)
1812 );
1813 if( !aTmp ){
1814 rc = SQLITE_NOMEM_BKPT;
1815 }
1816
1817 for(i=walFramePage(nBackfill+1); rc==SQLITE_OK && i<nSegment; i++){
1818 WalHashLoc sLoc;
1819
1820 rc = walHashGet(pWal, i, &sLoc);
1821 if( rc==SQLITE_OK ){
1822 int j; /* Counter variable */
1823 int nEntry; /* Number of entries in this segment */
1824 ht_slot *aIndex; /* Sorted index for this segment */
1825
1826 if( (i+1)==nSegment ){
1827 nEntry = (int)(iLast - sLoc.iZero);
1828 }else{
1829 nEntry = (int)((u32*)sLoc.aHash - (u32*)sLoc.aPgno);
1830 }
1831 aIndex = &((ht_slot *)&p->aSegment[p->nSegment])[sLoc.iZero];
1832 sLoc.iZero++;
1833
1834 for(j=0; j<nEntry; j++){
1835 aIndex[j] = (ht_slot)j;
1836 }
1837 walMergesort((u32 *)sLoc.aPgno, aTmp, aIndex, &nEntry);
1838 p->aSegment[i].iZero = sLoc.iZero;
1839 p->aSegment[i].nEntry = nEntry;
1840 p->aSegment[i].aIndex = aIndex;
1841 p->aSegment[i].aPgno = (u32 *)sLoc.aPgno;
1842 }
1843 }
1844 sqlite3_free(aTmp);
1845
1846 if( rc!=SQLITE_OK ){
1847 walIteratorFree(p);
1848 p = 0;
1849 }
1850 *pp = p;
1851 return rc;
1852}
1853
1854#ifdef SQLITE_ENABLE_SETLK_TIMEOUT
1855/*
1856** Attempt to enable blocking locks. Blocking locks are enabled only if (a)
1857** they are supported by the VFS, and (b) the database handle is configured
1858** with a busy-timeout. Return 1 if blocking locks are successfully enabled,
1859** or 0 otherwise.
1860*/
1861static int walEnableBlocking(Wal *pWal){
1862 int res = 0;
1863 if( pWal->db ){
1864 int tmout = pWal->db->busyTimeout;
1865 if( tmout ){
1866 int rc;
1867 rc = sqlite3OsFileControl(
1868 pWal->pDbFd, SQLITE_FCNTL_LOCK_TIMEOUT, (void*)&tmout
1869 );
1870 res = (rc==SQLITE_OK);
1871 }
1872 }
1873 return res;
1874}
1875
1876/*
1877** Disable blocking locks.
1878*/
1879static void walDisableBlocking(Wal *pWal){
1880 int tmout = 0;
1881 sqlite3OsFileControl(pWal->pDbFd, SQLITE_FCNTL_LOCK_TIMEOUT, (void*)&tmout);
1882}
1883
1884/*
1885** If parameter bLock is true, attempt to enable blocking locks, take
1886** the WRITER lock, and then disable blocking locks. If blocking locks
1887** cannot be enabled, no attempt to obtain the WRITER lock is made. Return
1888** an SQLite error code if an error occurs, or SQLITE_OK otherwise. It is not
1889** an error if blocking locks can not be enabled.
1890**
1891** If the bLock parameter is false and the WRITER lock is held, release it.
1892*/
1893int sqlite3WalWriteLock(Wal *pWal, int bLock){
1894 int rc = SQLITE_OK;
1895 assert( pWal->readLock<0 || bLock==0 );
1896 if( bLock ){
1897 assert( pWal->db );
1898 if( walEnableBlocking(pWal) ){
1899 rc = walLockExclusive(pWal, WAL_WRITE_LOCK, 1);
1900 if( rc==SQLITE_OK ){
1901 pWal->writeLock = 1;
1902 }
1903 walDisableBlocking(pWal);
1904 }
1905 }else if( pWal->writeLock ){
1906 walUnlockExclusive(pWal, WAL_WRITE_LOCK, 1);
1907 pWal->writeLock = 0;
1908 }
1909 return rc;
1910}
1911
1912/*
1913** Set the database handle used to determine if blocking locks are required.
1914*/
1915void sqlite3WalDb(Wal *pWal, sqlite3 *db){
1916 pWal->db = db;
1917}
1918
1919/*
1920** Take an exclusive WRITE lock. Blocking if so configured.
1921*/
1922static int walLockWriter(Wal *pWal){
1923 int rc;
1924 walEnableBlocking(pWal);
1925 rc = walLockExclusive(pWal, WAL_WRITE_LOCK, 1);
1926 walDisableBlocking(pWal);
1927 return rc;
1928}
1929#else
1930# define walEnableBlocking(x) 0
1931# define walDisableBlocking(x)
1932# define walLockWriter(pWal) walLockExclusive((pWal), WAL_WRITE_LOCK, 1)
1933# define sqlite3WalDb(pWal, db)
1934#endif /* ifdef SQLITE_ENABLE_SETLK_TIMEOUT */
1935
1936
1937/*
1938** Attempt to obtain the exclusive WAL lock defined by parameters lockIdx and
1939** n. If the attempt fails and parameter xBusy is not NULL, then it is a
1940** busy-handler function. Invoke it and retry the lock until either the
1941** lock is successfully obtained or the busy-handler returns 0.
1942*/
1943static int walBusyLock(
1944 Wal *pWal, /* WAL connection */
1945 int (*xBusy)(void*), /* Function to call when busy */
1946 void *pBusyArg, /* Context argument for xBusyHandler */
1947 int lockIdx, /* Offset of first byte to lock */
1948 int n /* Number of bytes to lock */
1949){
1950 int rc;
1951 do {
1952 rc = walLockExclusive(pWal, lockIdx, n);
1953 }while( xBusy && rc==SQLITE_BUSY && xBusy(pBusyArg) );
1954#ifdef SQLITE_ENABLE_SETLK_TIMEOUT
1955 if( rc==SQLITE_BUSY_TIMEOUT ){
1956 walDisableBlocking(pWal);
1957 rc = SQLITE_BUSY;
1958 }
1959#endif
1960 return rc;
1961}
1962
1963/*
1964** The cache of the wal-index header must be valid to call this function.
1965** Return the page-size in bytes used by the database.
1966*/
1967static int walPagesize(Wal *pWal){
1968 return (pWal->hdr.szPage&0xfe00) + ((pWal->hdr.szPage&0x0001)<<16);
1969}
1970
1971/*
1972** The following is guaranteed when this function is called:
1973**
1974** a) the WRITER lock is held,
1975** b) the entire log file has been checkpointed, and
1976** c) any existing readers are reading exclusively from the database
1977** file - there are no readers that may attempt to read a frame from
1978** the log file.
1979**
1980** This function updates the shared-memory structures so that the next
1981** client to write to the database (which may be this one) does so by
1982** writing frames into the start of the log file.
1983**
1984** The value of parameter salt1 is used as the aSalt[1] value in the
1985** new wal-index header. It should be passed a pseudo-random value (i.e.
1986** one obtained from sqlite3_randomness()).
1987*/
1988static void walRestartHdr(Wal *pWal, u32 salt1){
1989 volatile WalCkptInfo *pInfo = walCkptInfo(pWal);
1990 int i; /* Loop counter */
1991 u32 *aSalt = pWal->hdr.aSalt; /* Big-endian salt values */
1992 pWal->nCkpt++;
1993 pWal->hdr.mxFrame = 0;
1994 sqlite3Put4byte((u8*)&aSalt[0], 1 + sqlite3Get4byte((u8*)&aSalt[0]));
1995 memcpy(&pWal->hdr.aSalt[1], &salt1, 4);
1996 walIndexWriteHdr(pWal);
1997 AtomicStore(&pInfo->nBackfill, 0);
1998 pInfo->nBackfillAttempted = 0;
1999 pInfo->aReadMark[1] = 0;
2000 for(i=2; i<WAL_NREADER; i++) pInfo->aReadMark[i] = READMARK_NOT_USED;
2001 assert( pInfo->aReadMark[0]==0 );
2002}
2003
2004/*
2005** Copy as much content as we can from the WAL back into the database file
2006** in response to an sqlite3_wal_checkpoint() request or the equivalent.
2007**
2008** The amount of information copies from WAL to database might be limited
2009** by active readers. This routine will never overwrite a database page
2010** that a concurrent reader might be using.
2011**
2012** All I/O barrier operations (a.k.a fsyncs) occur in this routine when
2013** SQLite is in WAL-mode in synchronous=NORMAL. That means that if
2014** checkpoints are always run by a background thread or background
2015** process, foreground threads will never block on a lengthy fsync call.
2016**
2017** Fsync is called on the WAL before writing content out of the WAL and
2018** into the database. This ensures that if the new content is persistent
2019** in the WAL and can be recovered following a power-loss or hard reset.
2020**
2021** Fsync is also called on the database file if (and only if) the entire
2022** WAL content is copied into the database file. This second fsync makes
2023** it safe to delete the WAL since the new content will persist in the
2024** database file.
2025**
2026** This routine uses and updates the nBackfill field of the wal-index header.
2027** This is the only routine that will increase the value of nBackfill.
2028** (A WAL reset or recovery will revert nBackfill to zero, but not increase
2029** its value.)
2030**
2031** The caller must be holding sufficient locks to ensure that no other
2032** checkpoint is running (in any other thread or process) at the same
2033** time.
2034*/
2035static int walCheckpoint(
2036 Wal *pWal, /* Wal connection */
2037 sqlite3 *db, /* Check for interrupts on this handle */
2038 int eMode, /* One of PASSIVE, FULL or RESTART */
2039 int (*xBusy)(void*), /* Function to call when busy */
2040 void *pBusyArg, /* Context argument for xBusyHandler */
2041 int sync_flags, /* Flags for OsSync() (or 0) */
2042 u8 *zBuf /* Temporary buffer to use */
2043){
2044 int rc = SQLITE_OK; /* Return code */
2045 int szPage; /* Database page-size */
2046 WalIterator *pIter = 0; /* Wal iterator context */
2047 u32 iDbpage = 0; /* Next database page to write */
2048 u32 iFrame = 0; /* Wal frame containing data for iDbpage */
2049 u32 mxSafeFrame; /* Max frame that can be backfilled */
2050 u32 mxPage; /* Max database page to write */
2051 int i; /* Loop counter */
2052 volatile WalCkptInfo *pInfo; /* The checkpoint status information */
2053
2054 szPage = walPagesize(pWal);
2055 testcase( szPage<=32768 );
2056 testcase( szPage>=65536 );
2057 pInfo = walCkptInfo(pWal);
2058 if( pInfo->nBackfill<pWal->hdr.mxFrame ){
2059
2060 /* EVIDENCE-OF: R-62920-47450 The busy-handler callback is never invoked
2061 ** in the SQLITE_CHECKPOINT_PASSIVE mode. */
2062 assert( eMode!=SQLITE_CHECKPOINT_PASSIVE || xBusy==0 );
2063
2064 /* Compute in mxSafeFrame the index of the last frame of the WAL that is
2065 ** safe to write into the database. Frames beyond mxSafeFrame might
2066 ** overwrite database pages that are in use by active readers and thus
2067 ** cannot be backfilled from the WAL.
2068 */
2069 mxSafeFrame = pWal->hdr.mxFrame;
2070 mxPage = pWal->hdr.nPage;
2071 for(i=1; i<WAL_NREADER; i++){
2072 u32 y = AtomicLoad(pInfo->aReadMark+i);
2073 if( mxSafeFrame>y ){
2074 assert( y<=pWal->hdr.mxFrame );
2075 rc = walBusyLock(pWal, xBusy, pBusyArg, WAL_READ_LOCK(i), 1);
2076 if( rc==SQLITE_OK ){
2077 u32 iMark = (i==1 ? mxSafeFrame : READMARK_NOT_USED);
2078 AtomicStore(pInfo->aReadMark+i, iMark);
2079 walUnlockExclusive(pWal, WAL_READ_LOCK(i), 1);
2080 }else if( rc==SQLITE_BUSY ){
2081 mxSafeFrame = y;
2082 xBusy = 0;
2083 }else{
2084 goto walcheckpoint_out;
2085 }
2086 }
2087 }
2088
2089 /* Allocate the iterator */
2090 if( pInfo->nBackfill<mxSafeFrame ){
2091 rc = walIteratorInit(pWal, pInfo->nBackfill, &pIter);
2092 assert( rc==SQLITE_OK || pIter==0 );
2093 }
2094
2095 if( pIter
2096 && (rc = walBusyLock(pWal,xBusy,pBusyArg,WAL_READ_LOCK(0),1))==SQLITE_OK
2097 ){
2098 u32 nBackfill = pInfo->nBackfill;
2099
2100 pInfo->nBackfillAttempted = mxSafeFrame;
2101
2102 /* Sync the WAL to disk */
2103 rc = sqlite3OsSync(pWal->pWalFd, CKPT_SYNC_FLAGS(sync_flags));
2104
2105 /* If the database may grow as a result of this checkpoint, hint
2106 ** about the eventual size of the db file to the VFS layer.
2107 */
2108 if( rc==SQLITE_OK ){
2109 i64 nReq = ((i64)mxPage * szPage);
2110 i64 nSize; /* Current size of database file */
2111 sqlite3OsFileControl(pWal->pDbFd, SQLITE_FCNTL_CKPT_START, 0);
2112 rc = sqlite3OsFileSize(pWal->pDbFd, &nSize);
2113 if( rc==SQLITE_OK && nSize<nReq ){
2114 if( (nSize+65536+(i64)pWal->hdr.mxFrame*szPage)<nReq ){
2115 /* If the size of the final database is larger than the current
2116 ** database plus the amount of data in the wal file, plus the
2117 ** maximum size of the pending-byte page (65536 bytes), then
2118 ** must be corruption somewhere. */
2119 rc = SQLITE_CORRUPT_BKPT;
2120 }else{
2121 sqlite3OsFileControlHint(pWal->pDbFd, SQLITE_FCNTL_SIZE_HINT,&nReq);
2122 }
2123 }
2124
2125 }
2126
2127 /* Iterate through the contents of the WAL, copying data to the db file */
2128 while( rc==SQLITE_OK && 0==walIteratorNext(pIter, &iDbpage, &iFrame) ){
2129 i64 iOffset;
2130 assert( walFramePgno(pWal, iFrame)==iDbpage );
2131 if( AtomicLoad(&db->u1.isInterrupted) ){
2132 rc = db->mallocFailed ? SQLITE_NOMEM_BKPT : SQLITE_INTERRUPT;
2133 break;
2134 }
2135 if( iFrame<=nBackfill || iFrame>mxSafeFrame || iDbpage>mxPage ){
2136 continue;
2137 }
2138 iOffset = walFrameOffset(iFrame, szPage) + WAL_FRAME_HDRSIZE;
2139 /* testcase( IS_BIG_INT(iOffset) ); // requires a 4GiB WAL file */
2140 rc = sqlite3OsRead(pWal->pWalFd, zBuf, szPage, iOffset);
2141 if( rc!=SQLITE_OK ) break;
2142 iOffset = (iDbpage-1)*(i64)szPage;
2143 testcase( IS_BIG_INT(iOffset) );
2144 rc = sqlite3OsWrite(pWal->pDbFd, zBuf, szPage, iOffset);
2145 if( rc!=SQLITE_OK ) break;
2146 }
2147 sqlite3OsFileControl(pWal->pDbFd, SQLITE_FCNTL_CKPT_DONE, 0);
2148
2149 /* If work was actually accomplished... */
2150 if( rc==SQLITE_OK ){
2151 if( mxSafeFrame==walIndexHdr(pWal)->mxFrame ){
2152 i64 szDb = pWal->hdr.nPage*(i64)szPage;
2153 testcase( IS_BIG_INT(szDb) );
2154 rc = sqlite3OsTruncate(pWal->pDbFd, szDb);
2155 if( rc==SQLITE_OK ){
2156 rc = sqlite3OsSync(pWal->pDbFd, CKPT_SYNC_FLAGS(sync_flags));
2157 }
2158 }
2159 if( rc==SQLITE_OK ){
2160 AtomicStore(&pInfo->nBackfill, mxSafeFrame);
2161 }
2162 }
2163
2164 /* Release the reader lock held while backfilling */
2165 walUnlockExclusive(pWal, WAL_READ_LOCK(0), 1);
2166 }
2167
2168 if( rc==SQLITE_BUSY ){
2169 /* Reset the return code so as not to report a checkpoint failure
2170 ** just because there are active readers. */
2171 rc = SQLITE_OK;
2172 }
2173 }
2174
2175 /* If this is an SQLITE_CHECKPOINT_RESTART or TRUNCATE operation, and the
2176 ** entire wal file has been copied into the database file, then block
2177 ** until all readers have finished using the wal file. This ensures that
2178 ** the next process to write to the database restarts the wal file.
2179 */
2180 if( rc==SQLITE_OK && eMode!=SQLITE_CHECKPOINT_PASSIVE ){
2181 assert( pWal->writeLock );
2182 if( pInfo->nBackfill<pWal->hdr.mxFrame ){
2183 rc = SQLITE_BUSY;
2184 }else if( eMode>=SQLITE_CHECKPOINT_RESTART ){
2185 u32 salt1;
2186 sqlite3_randomness(4, &salt1);
2187 assert( pInfo->nBackfill==pWal->hdr.mxFrame );
2188 rc = walBusyLock(pWal, xBusy, pBusyArg, WAL_READ_LOCK(1), WAL_NREADER-1);
2189 if( rc==SQLITE_OK ){
2190 if( eMode==SQLITE_CHECKPOINT_TRUNCATE ){
2191 /* IMPLEMENTATION-OF: R-44699-57140 This mode works the same way as
2192 ** SQLITE_CHECKPOINT_RESTART with the addition that it also
2193 ** truncates the log file to zero bytes just prior to a
2194 ** successful return.
2195 **
2196 ** In theory, it might be safe to do this without updating the
2197 ** wal-index header in shared memory, as all subsequent reader or
2198 ** writer clients should see that the entire log file has been
2199 ** checkpointed and behave accordingly. This seems unsafe though,
2200 ** as it would leave the system in a state where the contents of
2201 ** the wal-index header do not match the contents of the
2202 ** file-system. To avoid this, update the wal-index header to
2203 ** indicate that the log file contains zero valid frames. */
2204 walRestartHdr(pWal, salt1);
2205 rc = sqlite3OsTruncate(pWal->pWalFd, 0);
2206 }
2207 walUnlockExclusive(pWal, WAL_READ_LOCK(1), WAL_NREADER-1);
2208 }
2209 }
2210 }
2211
2212 walcheckpoint_out:
2213 walIteratorFree(pIter);
2214 return rc;
2215}
2216
2217/*
2218** If the WAL file is currently larger than nMax bytes in size, truncate
2219** it to exactly nMax bytes. If an error occurs while doing so, ignore it.
2220*/
2221static void walLimitSize(Wal *pWal, i64 nMax){
2222 i64 sz;
2223 int rx;
2224 sqlite3BeginBenignMalloc();
2225 rx = sqlite3OsFileSize(pWal->pWalFd, &sz);
2226 if( rx==SQLITE_OK && (sz > nMax ) ){
2227 rx = sqlite3OsTruncate(pWal->pWalFd, nMax);
2228 }
2229 sqlite3EndBenignMalloc();
2230 if( rx ){
2231 sqlite3_log(rx, "cannot limit WAL size: %s", pWal->zWalName);
2232 }
2233}
2234
2235/*
2236** Close a connection to a log file.
2237*/
2238int sqlite3WalClose(
2239 Wal *pWal, /* Wal to close */
2240 sqlite3 *db, /* For interrupt flag */
2241 int sync_flags, /* Flags to pass to OsSync() (or 0) */
2242 int nBuf,
2243 u8 *zBuf /* Buffer of at least nBuf bytes */
2244){
2245 int rc = SQLITE_OK;
2246 if( pWal ){
2247 int isDelete = 0; /* True to unlink wal and wal-index files */
2248
2249 /* If an EXCLUSIVE lock can be obtained on the database file (using the
2250 ** ordinary, rollback-mode locking methods, this guarantees that the
2251 ** connection associated with this log file is the only connection to
2252 ** the database. In this case checkpoint the database and unlink both
2253 ** the wal and wal-index files.
2254 **
2255 ** The EXCLUSIVE lock is not released before returning.
2256 */
2257 if( zBuf!=0
2258 && SQLITE_OK==(rc = sqlite3OsLock(pWal->pDbFd, SQLITE_LOCK_EXCLUSIVE))
2259 ){
2260 if( pWal->exclusiveMode==WAL_NORMAL_MODE ){
2261 pWal->exclusiveMode = WAL_EXCLUSIVE_MODE;
2262 }
2263 rc = sqlite3WalCheckpoint(pWal, db,
2264 SQLITE_CHECKPOINT_PASSIVE, 0, 0, sync_flags, nBuf, zBuf, 0, 0
2265 );
2266 if( rc==SQLITE_OK ){
2267 int bPersist = -1;
2268 sqlite3OsFileControlHint(
2269 pWal->pDbFd, SQLITE_FCNTL_PERSIST_WAL, &bPersist
2270 );
2271 if( bPersist!=1 ){
2272 /* Try to delete the WAL file if the checkpoint completed and
2273 ** fsyned (rc==SQLITE_OK) and if we are not in persistent-wal
2274 ** mode (!bPersist) */
2275 isDelete = 1;
2276 }else if( pWal->mxWalSize>=0 ){
2277 /* Try to truncate the WAL file to zero bytes if the checkpoint
2278 ** completed and fsynced (rc==SQLITE_OK) and we are in persistent
2279 ** WAL mode (bPersist) and if the PRAGMA journal_size_limit is a
2280 ** non-negative value (pWal->mxWalSize>=0). Note that we truncate
2281 ** to zero bytes as truncating to the journal_size_limit might
2282 ** leave a corrupt WAL file on disk. */
2283 walLimitSize(pWal, 0);
2284 }
2285 }
2286 }
2287
2288 walIndexClose(pWal, isDelete);
2289 sqlite3OsClose(pWal->pWalFd);
2290 if( isDelete ){
2291 sqlite3BeginBenignMalloc();
2292 sqlite3OsDelete(pWal->pVfs, pWal->zWalName, 0);
2293 sqlite3EndBenignMalloc();
2294 }
2295 WALTRACE(("WAL%p: closed\n", pWal));
2296 sqlite3_free((void *)pWal->apWiData);
2297 sqlite3_free(pWal);
2298 }
2299 return rc;
2300}
2301
2302/*
2303** Try to read the wal-index header. Return 0 on success and 1 if
2304** there is a problem.
2305**
2306** The wal-index is in shared memory. Another thread or process might
2307** be writing the header at the same time this procedure is trying to
2308** read it, which might result in inconsistency. A dirty read is detected
2309** by verifying that both copies of the header are the same and also by
2310** a checksum on the header.
2311**
2312** If and only if the read is consistent and the header is different from
2313** pWal->hdr, then pWal->hdr is updated to the content of the new header
2314** and *pChanged is set to 1.
2315**
2316** If the checksum cannot be verified return non-zero. If the header
2317** is read successfully and the checksum verified, return zero.
2318*/
2319static SQLITE_NO_TSAN int walIndexTryHdr(Wal *pWal, int *pChanged){
2320 u32 aCksum[2]; /* Checksum on the header content */
2321 WalIndexHdr h1, h2; /* Two copies of the header content */
2322 WalIndexHdr volatile *aHdr; /* Header in shared memory */
2323
2324 /* The first page of the wal-index must be mapped at this point. */
2325 assert( pWal->nWiData>0 && pWal->apWiData[0] );
2326
2327 /* Read the header. This might happen concurrently with a write to the
2328 ** same area of shared memory on a different CPU in a SMP,
2329 ** meaning it is possible that an inconsistent snapshot is read
2330 ** from the file. If this happens, return non-zero.
2331 **
2332 ** tag-20200519-1:
2333 ** There are two copies of the header at the beginning of the wal-index.
2334 ** When reading, read [0] first then [1]. Writes are in the reverse order.
2335 ** Memory barriers are used to prevent the compiler or the hardware from
2336 ** reordering the reads and writes. TSAN and similar tools can sometimes
2337 ** give false-positive warnings about these accesses because the tools do not
2338 ** account for the double-read and the memory barrier. The use of mutexes
2339 ** here would be problematic as the memory being accessed is potentially
2340 ** shared among multiple processes and not all mutex implementions work
2341 ** reliably in that environment.
2342 */
2343 aHdr = walIndexHdr(pWal);
2344 memcpy(&h1, (void *)&aHdr[0], sizeof(h1)); /* Possible TSAN false-positive */
2345 walShmBarrier(pWal);
2346 memcpy(&h2, (void *)&aHdr[1], sizeof(h2));
2347
2348 if( memcmp(&h1, &h2, sizeof(h1))!=0 ){
2349 return 1; /* Dirty read */
2350 }
2351 if( h1.isInit==0 ){
2352 return 1; /* Malformed header - probably all zeros */
2353 }
2354 walChecksumBytes(1, (u8*)&h1, sizeof(h1)-sizeof(h1.aCksum), 0, aCksum);
2355 if( aCksum[0]!=h1.aCksum[0] || aCksum[1]!=h1.aCksum[1] ){
2356 return 1; /* Checksum does not match */
2357 }
2358
2359 if( memcmp(&pWal->hdr, &h1, sizeof(WalIndexHdr)) ){
2360 *pChanged = 1;
2361 memcpy(&pWal->hdr, &h1, sizeof(WalIndexHdr));
2362 pWal->szPage = (pWal->hdr.szPage&0xfe00) + ((pWal->hdr.szPage&0x0001)<<16);
2363 testcase( pWal->szPage<=32768 );
2364 testcase( pWal->szPage>=65536 );
2365 }
2366
2367 /* The header was successfully read. Return zero. */
2368 return 0;
2369}
2370
2371/*
2372** This is the value that walTryBeginRead returns when it needs to
2373** be retried.
2374*/
2375#define WAL_RETRY (-1)
2376
2377/*
2378** Read the wal-index header from the wal-index and into pWal->hdr.
2379** If the wal-header appears to be corrupt, try to reconstruct the
2380** wal-index from the WAL before returning.
2381**
2382** Set *pChanged to 1 if the wal-index header value in pWal->hdr is
2383** changed by this operation. If pWal->hdr is unchanged, set *pChanged
2384** to 0.
2385**
2386** If the wal-index header is successfully read, return SQLITE_OK.
2387** Otherwise an SQLite error code.
2388*/
2389static int walIndexReadHdr(Wal *pWal, int *pChanged){
2390 int rc; /* Return code */
2391 int badHdr; /* True if a header read failed */
2392 volatile u32 *page0; /* Chunk of wal-index containing header */
2393
2394 /* Ensure that page 0 of the wal-index (the page that contains the
2395 ** wal-index header) is mapped. Return early if an error occurs here.
2396 */
2397 assert( pChanged );
2398 rc = walIndexPage(pWal, 0, &page0);
2399 if( rc!=SQLITE_OK ){
2400 assert( rc!=SQLITE_READONLY ); /* READONLY changed to OK in walIndexPage */
2401 if( rc==SQLITE_READONLY_CANTINIT ){
2402 /* The SQLITE_READONLY_CANTINIT return means that the shared-memory
2403 ** was openable but is not writable, and this thread is unable to
2404 ** confirm that another write-capable connection has the shared-memory
2405 ** open, and hence the content of the shared-memory is unreliable,
2406 ** since the shared-memory might be inconsistent with the WAL file
2407 ** and there is no writer on hand to fix it. */
2408 assert( page0==0 );
2409 assert( pWal->writeLock==0 );
2410 assert( pWal->readOnly & WAL_SHM_RDONLY );
2411 pWal->bShmUnreliable = 1;
2412 pWal->exclusiveMode = WAL_HEAPMEMORY_MODE;
2413 *pChanged = 1;
2414 }else{
2415 return rc; /* Any other non-OK return is just an error */
2416 }
2417 }else{
2418 /* page0 can be NULL if the SHM is zero bytes in size and pWal->writeLock
2419 ** is zero, which prevents the SHM from growing */
2420 testcase( page0!=0 );
2421 }
2422 assert( page0!=0 || pWal->writeLock==0 );
2423
2424 /* If the first page of the wal-index has been mapped, try to read the
2425 ** wal-index header immediately, without holding any lock. This usually
2426 ** works, but may fail if the wal-index header is corrupt or currently
2427 ** being modified by another thread or process.
2428 */
2429 badHdr = (page0 ? walIndexTryHdr(pWal, pChanged) : 1);
2430
2431 /* If the first attempt failed, it might have been due to a race
2432 ** with a writer. So get a WRITE lock and try again.
2433 */
2434 if( badHdr ){
2435 if( pWal->bShmUnreliable==0 && (pWal->readOnly & WAL_SHM_RDONLY) ){
2436 if( SQLITE_OK==(rc = walLockShared(pWal, WAL_WRITE_LOCK)) ){
2437 walUnlockShared(pWal, WAL_WRITE_LOCK);
2438 rc = SQLITE_READONLY_RECOVERY;
2439 }
2440 }else{
2441 int bWriteLock = pWal->writeLock;
2442 if( bWriteLock || SQLITE_OK==(rc = walLockWriter(pWal)) ){
2443 pWal->writeLock = 1;
2444 if( SQLITE_OK==(rc = walIndexPage(pWal, 0, &page0)) ){
2445 badHdr = walIndexTryHdr(pWal, pChanged);
2446 if( badHdr ){
2447 /* If the wal-index header is still malformed even while holding
2448 ** a WRITE lock, it can only mean that the header is corrupted and
2449 ** needs to be reconstructed. So run recovery to do exactly that.
2450 */
2451 rc = walIndexRecover(pWal);
2452 *pChanged = 1;
2453 }
2454 }
2455 if( bWriteLock==0 ){
2456 pWal->writeLock = 0;
2457 walUnlockExclusive(pWal, WAL_WRITE_LOCK, 1);
2458 }
2459 }
2460 }
2461 }
2462
2463 /* If the header is read successfully, check the version number to make
2464 ** sure the wal-index was not constructed with some future format that
2465 ** this version of SQLite cannot understand.
2466 */
2467 if( badHdr==0 && pWal->hdr.iVersion!=WALINDEX_MAX_VERSION ){
2468 rc = SQLITE_CANTOPEN_BKPT;
2469 }
2470 if( pWal->bShmUnreliable ){
2471 if( rc!=SQLITE_OK ){
2472 walIndexClose(pWal, 0);
2473 pWal->bShmUnreliable = 0;
2474 assert( pWal->nWiData>0 && pWal->apWiData[0]==0 );
2475 /* walIndexRecover() might have returned SHORT_READ if a concurrent
2476 ** writer truncated the WAL out from under it. If that happens, it
2477 ** indicates that a writer has fixed the SHM file for us, so retry */
2478 if( rc==SQLITE_IOERR_SHORT_READ ) rc = WAL_RETRY;
2479 }
2480 pWal->exclusiveMode = WAL_NORMAL_MODE;
2481 }
2482
2483 return rc;
2484}
2485
2486/*
2487** Open a transaction in a connection where the shared-memory is read-only
2488** and where we cannot verify that there is a separate write-capable connection
2489** on hand to keep the shared-memory up-to-date with the WAL file.
2490**
2491** This can happen, for example, when the shared-memory is implemented by
2492** memory-mapping a *-shm file, where a prior writer has shut down and
2493** left the *-shm file on disk, and now the present connection is trying
2494** to use that database but lacks write permission on the *-shm file.
2495** Other scenarios are also possible, depending on the VFS implementation.
2496**
2497** Precondition:
2498**
2499** The *-wal file has been read and an appropriate wal-index has been
2500** constructed in pWal->apWiData[] using heap memory instead of shared
2501** memory.
2502**
2503** If this function returns SQLITE_OK, then the read transaction has
2504** been successfully opened. In this case output variable (*pChanged)
2505** is set to true before returning if the caller should discard the
2506** contents of the page cache before proceeding. Or, if it returns
2507** WAL_RETRY, then the heap memory wal-index has been discarded and
2508** the caller should retry opening the read transaction from the
2509** beginning (including attempting to map the *-shm file).
2510**
2511** If an error occurs, an SQLite error code is returned.
2512*/
2513static int walBeginShmUnreliable(Wal *pWal, int *pChanged){
2514 i64 szWal; /* Size of wal file on disk in bytes */
2515 i64 iOffset; /* Current offset when reading wal file */
2516 u8 aBuf[WAL_HDRSIZE]; /* Buffer to load WAL header into */
2517 u8 *aFrame = 0; /* Malloc'd buffer to load entire frame */
2518 int szFrame; /* Number of bytes in buffer aFrame[] */
2519 u8 *aData; /* Pointer to data part of aFrame buffer */
2520 volatile void *pDummy; /* Dummy argument for xShmMap */
2521 int rc; /* Return code */
2522 u32 aSaveCksum[2]; /* Saved copy of pWal->hdr.aFrameCksum */
2523
2524 assert( pWal->bShmUnreliable );
2525 assert( pWal->readOnly & WAL_SHM_RDONLY );
2526 assert( pWal->nWiData>0 && pWal->apWiData[0] );
2527
2528 /* Take WAL_READ_LOCK(0). This has the effect of preventing any
2529 ** writers from running a checkpoint, but does not stop them
2530 ** from running recovery. */
2531 rc = walLockShared(pWal, WAL_READ_LOCK(0));
2532 if( rc!=SQLITE_OK ){
2533 if( rc==SQLITE_BUSY ) rc = WAL_RETRY;
2534 goto begin_unreliable_shm_out;
2535 }
2536 pWal->readLock = 0;
2537
2538 /* Check to see if a separate writer has attached to the shared-memory area,
2539 ** thus making the shared-memory "reliable" again. Do this by invoking
2540 ** the xShmMap() routine of the VFS and looking to see if the return
2541 ** is SQLITE_READONLY instead of SQLITE_READONLY_CANTINIT.
2542 **
2543 ** If the shared-memory is now "reliable" return WAL_RETRY, which will
2544 ** cause the heap-memory WAL-index to be discarded and the actual
2545 ** shared memory to be used in its place.
2546 **
2547 ** This step is important because, even though this connection is holding
2548 ** the WAL_READ_LOCK(0) which prevents a checkpoint, a writer might
2549 ** have already checkpointed the WAL file and, while the current
2550 ** is active, wrap the WAL and start overwriting frames that this
2551 ** process wants to use.
2552 **
2553 ** Once sqlite3OsShmMap() has been called for an sqlite3_file and has
2554 ** returned any SQLITE_READONLY value, it must return only SQLITE_READONLY
2555 ** or SQLITE_READONLY_CANTINIT or some error for all subsequent invocations,
2556 ** even if some external agent does a "chmod" to make the shared-memory
2557 ** writable by us, until sqlite3OsShmUnmap() has been called.
2558 ** This is a requirement on the VFS implementation.
2559 */
2560 rc = sqlite3OsShmMap(pWal->pDbFd, 0, WALINDEX_PGSZ, 0, &pDummy);
2561 assert( rc!=SQLITE_OK ); /* SQLITE_OK not possible for read-only connection */
2562 if( rc!=SQLITE_READONLY_CANTINIT ){
2563 rc = (rc==SQLITE_READONLY ? WAL_RETRY : rc);
2564 goto begin_unreliable_shm_out;
2565 }
2566
2567 /* We reach this point only if the real shared-memory is still unreliable.
2568 ** Assume the in-memory WAL-index substitute is correct and load it
2569 ** into pWal->hdr.
2570 */
2571 memcpy(&pWal->hdr, (void*)walIndexHdr(pWal), sizeof(WalIndexHdr));
2572
2573 /* Make sure some writer hasn't come in and changed the WAL file out
2574 ** from under us, then disconnected, while we were not looking.
2575 */
2576 rc = sqlite3OsFileSize(pWal->pWalFd, &szWal);
2577 if( rc!=SQLITE_OK ){
2578 goto begin_unreliable_shm_out;
2579 }
2580 if( szWal<WAL_HDRSIZE ){
2581 /* If the wal file is too small to contain a wal-header and the
2582 ** wal-index header has mxFrame==0, then it must be safe to proceed
2583 ** reading the database file only. However, the page cache cannot
2584 ** be trusted, as a read/write connection may have connected, written
2585 ** the db, run a checkpoint, truncated the wal file and disconnected
2586 ** since this client's last read transaction. */
2587 *pChanged = 1;
2588 rc = (pWal->hdr.mxFrame==0 ? SQLITE_OK : WAL_RETRY);
2589 goto begin_unreliable_shm_out;
2590 }
2591
2592 /* Check the salt keys at the start of the wal file still match. */
2593 rc = sqlite3OsRead(pWal->pWalFd, aBuf, WAL_HDRSIZE, 0);
2594 if( rc!=SQLITE_OK ){
2595 goto begin_unreliable_shm_out;
2596 }
2597 if( memcmp(&pWal->hdr.aSalt, &aBuf[16], 8) ){
2598 /* Some writer has wrapped the WAL file while we were not looking.
2599 ** Return WAL_RETRY which will cause the in-memory WAL-index to be
2600 ** rebuilt. */
2601 rc = WAL_RETRY;
2602 goto begin_unreliable_shm_out;
2603 }
2604
2605 /* Allocate a buffer to read frames into */
2606 assert( (pWal->szPage & (pWal->szPage-1))==0 );
2607 assert( pWal->szPage>=512 && pWal->szPage<=65536 );
2608 szFrame = pWal->szPage + WAL_FRAME_HDRSIZE;
2609 aFrame = (u8 *)sqlite3_malloc64(szFrame);
2610 if( aFrame==0 ){
2611 rc = SQLITE_NOMEM_BKPT;
2612 goto begin_unreliable_shm_out;
2613 }
2614 aData = &aFrame[WAL_FRAME_HDRSIZE];
2615
2616 /* Check to see if a complete transaction has been appended to the
2617 ** wal file since the heap-memory wal-index was created. If so, the
2618 ** heap-memory wal-index is discarded and WAL_RETRY returned to
2619 ** the caller. */
2620 aSaveCksum[0] = pWal->hdr.aFrameCksum[0];
2621 aSaveCksum[1] = pWal->hdr.aFrameCksum[1];
2622 for(iOffset=walFrameOffset(pWal->hdr.mxFrame+1, pWal->szPage);
2623 iOffset+szFrame<=szWal;
2624 iOffset+=szFrame
2625 ){
2626 u32 pgno; /* Database page number for frame */
2627 u32 nTruncate; /* dbsize field from frame header */
2628
2629 /* Read and decode the next log frame. */
2630 rc = sqlite3OsRead(pWal->pWalFd, aFrame, szFrame, iOffset);
2631 if( rc!=SQLITE_OK ) break;
2632 if( !walDecodeFrame(pWal, &pgno, &nTruncate, aData, aFrame) ) break;
2633
2634 /* If nTruncate is non-zero, then a complete transaction has been
2635 ** appended to this wal file. Set rc to WAL_RETRY and break out of
2636 ** the loop. */
2637 if( nTruncate ){
2638 rc = WAL_RETRY;
2639 break;
2640 }
2641 }
2642 pWal->hdr.aFrameCksum[0] = aSaveCksum[0];
2643 pWal->hdr.aFrameCksum[1] = aSaveCksum[1];
2644
2645 begin_unreliable_shm_out:
2646 sqlite3_free(aFrame);
2647 if( rc!=SQLITE_OK ){
2648 int i;
2649 for(i=0; i<pWal->nWiData; i++){
2650 sqlite3_free((void*)pWal->apWiData[i]);
2651 pWal->apWiData[i] = 0;
2652 }
2653 pWal->bShmUnreliable = 0;
2654 sqlite3WalEndReadTransaction(pWal);
2655 *pChanged = 1;
2656 }
2657 return rc;
2658}
2659
2660/*
2661** Attempt to start a read transaction. This might fail due to a race or
2662** other transient condition. When that happens, it returns WAL_RETRY to
2663** indicate to the caller that it is safe to retry immediately.
2664**
2665** On success return SQLITE_OK. On a permanent failure (such an
2666** I/O error or an SQLITE_BUSY because another process is running
2667** recovery) return a positive error code.
2668**
2669** The useWal parameter is true to force the use of the WAL and disable
2670** the case where the WAL is bypassed because it has been completely
2671** checkpointed. If useWal==0 then this routine calls walIndexReadHdr()
2672** to make a copy of the wal-index header into pWal->hdr. If the
2673** wal-index header has changed, *pChanged is set to 1 (as an indication
2674** to the caller that the local page cache is obsolete and needs to be
2675** flushed.) When useWal==1, the wal-index header is assumed to already
2676** be loaded and the pChanged parameter is unused.
2677**
2678** The caller must set the cnt parameter to the number of prior calls to
2679** this routine during the current read attempt that returned WAL_RETRY.
2680** This routine will start taking more aggressive measures to clear the
2681** race conditions after multiple WAL_RETRY returns, and after an excessive
2682** number of errors will ultimately return SQLITE_PROTOCOL. The
2683** SQLITE_PROTOCOL return indicates that some other process has gone rogue
2684** and is not honoring the locking protocol. There is a vanishingly small
2685** chance that SQLITE_PROTOCOL could be returned because of a run of really
2686** bad luck when there is lots of contention for the wal-index, but that
2687** possibility is so small that it can be safely neglected, we believe.
2688**
2689** On success, this routine obtains a read lock on
2690** WAL_READ_LOCK(pWal->readLock). The pWal->readLock integer is
2691** in the range 0 <= pWal->readLock < WAL_NREADER. If pWal->readLock==(-1)
2692** that means the Wal does not hold any read lock. The reader must not
2693** access any database page that is modified by a WAL frame up to and
2694** including frame number aReadMark[pWal->readLock]. The reader will
2695** use WAL frames up to and including pWal->hdr.mxFrame if pWal->readLock>0
2696** Or if pWal->readLock==0, then the reader will ignore the WAL
2697** completely and get all content directly from the database file.
2698** If the useWal parameter is 1 then the WAL will never be ignored and
2699** this routine will always set pWal->readLock>0 on success.
2700** When the read transaction is completed, the caller must release the
2701** lock on WAL_READ_LOCK(pWal->readLock) and set pWal->readLock to -1.
2702**
2703** This routine uses the nBackfill and aReadMark[] fields of the header
2704** to select a particular WAL_READ_LOCK() that strives to let the
2705** checkpoint process do as much work as possible. This routine might
2706** update values of the aReadMark[] array in the header, but if it does
2707** so it takes care to hold an exclusive lock on the corresponding
2708** WAL_READ_LOCK() while changing values.
2709*/
2710static int walTryBeginRead(Wal *pWal, int *pChanged, int useWal, int cnt){
2711 volatile WalCkptInfo *pInfo; /* Checkpoint information in wal-index */
2712 u32 mxReadMark; /* Largest aReadMark[] value */
2713 int mxI; /* Index of largest aReadMark[] value */
2714 int i; /* Loop counter */
2715 int rc = SQLITE_OK; /* Return code */
2716 u32 mxFrame; /* Wal frame to lock to */
2717
2718 assert( pWal->readLock<0 ); /* Not currently locked */
2719
2720 /* useWal may only be set for read/write connections */
2721 assert( (pWal->readOnly & WAL_SHM_RDONLY)==0 || useWal==0 );
2722
2723 /* Take steps to avoid spinning forever if there is a protocol error.
2724 **
2725 ** Circumstances that cause a RETRY should only last for the briefest
2726 ** instances of time. No I/O or other system calls are done while the
2727 ** locks are held, so the locks should not be held for very long. But
2728 ** if we are unlucky, another process that is holding a lock might get
2729 ** paged out or take a page-fault that is time-consuming to resolve,
2730 ** during the few nanoseconds that it is holding the lock. In that case,
2731 ** it might take longer than normal for the lock to free.
2732 **
2733 ** After 5 RETRYs, we begin calling sqlite3OsSleep(). The first few
2734 ** calls to sqlite3OsSleep() have a delay of 1 microsecond. Really this
2735 ** is more of a scheduler yield than an actual delay. But on the 10th
2736 ** an subsequent retries, the delays start becoming longer and longer,
2737 ** so that on the 100th (and last) RETRY we delay for 323 milliseconds.
2738 ** The total delay time before giving up is less than 10 seconds.
2739 */
2740 if( cnt>5 ){
2741 int nDelay = 1; /* Pause time in microseconds */
2742 if( cnt>100 ){
2743 VVA_ONLY( pWal->lockError = 1; )
2744 return SQLITE_PROTOCOL;
2745 }
2746 if( cnt>=10 ) nDelay = (cnt-9)*(cnt-9)*39;
2747 sqlite3OsSleep(pWal->pVfs, nDelay);
2748 }
2749
2750 if( !useWal ){
2751 assert( rc==SQLITE_OK );
2752 if( pWal->bShmUnreliable==0 ){
2753 rc = walIndexReadHdr(pWal, pChanged);
2754 }
2755 if( rc==SQLITE_BUSY ){
2756 /* If there is not a recovery running in another thread or process
2757 ** then convert BUSY errors to WAL_RETRY. If recovery is known to
2758 ** be running, convert BUSY to BUSY_RECOVERY. There is a race here
2759 ** which might cause WAL_RETRY to be returned even if BUSY_RECOVERY
2760 ** would be technically correct. But the race is benign since with
2761 ** WAL_RETRY this routine will be called again and will probably be
2762 ** right on the second iteration.
2763 */
2764 if( pWal->apWiData[0]==0 ){
2765 /* This branch is taken when the xShmMap() method returns SQLITE_BUSY.
2766 ** We assume this is a transient condition, so return WAL_RETRY. The
2767 ** xShmMap() implementation used by the default unix and win32 VFS
2768 ** modules may return SQLITE_BUSY due to a race condition in the
2769 ** code that determines whether or not the shared-memory region
2770 ** must be zeroed before the requested page is returned.
2771 */
2772 rc = WAL_RETRY;
2773 }else if( SQLITE_OK==(rc = walLockShared(pWal, WAL_RECOVER_LOCK)) ){
2774 walUnlockShared(pWal, WAL_RECOVER_LOCK);
2775 rc = WAL_RETRY;
2776 }else if( rc==SQLITE_BUSY ){
2777 rc = SQLITE_BUSY_RECOVERY;
2778 }
2779 }
2780 if( rc!=SQLITE_OK ){
2781 return rc;
2782 }
2783 else if( pWal->bShmUnreliable ){
2784 return walBeginShmUnreliable(pWal, pChanged);
2785 }
2786 }
2787
2788 assert( pWal->nWiData>0 );
2789 assert( pWal->apWiData[0]!=0 );
2790 pInfo = walCkptInfo(pWal);
2791 if( !useWal && AtomicLoad(&pInfo->nBackfill)==pWal->hdr.mxFrame
2792#ifdef SQLITE_ENABLE_SNAPSHOT
2793 && (pWal->pSnapshot==0 || pWal->hdr.mxFrame==0)
2794#endif
2795 ){
2796 /* The WAL has been completely backfilled (or it is empty).
2797 ** and can be safely ignored.
2798 */
2799 rc = walLockShared(pWal, WAL_READ_LOCK(0));
2800 walShmBarrier(pWal);
2801 if( rc==SQLITE_OK ){
2802 if( memcmp((void *)walIndexHdr(pWal), &pWal->hdr, sizeof(WalIndexHdr)) ){
2803 /* It is not safe to allow the reader to continue here if frames
2804 ** may have been appended to the log before READ_LOCK(0) was obtained.
2805 ** When holding READ_LOCK(0), the reader ignores the entire log file,
2806 ** which implies that the database file contains a trustworthy
2807 ** snapshot. Since holding READ_LOCK(0) prevents a checkpoint from
2808 ** happening, this is usually correct.
2809 **
2810 ** However, if frames have been appended to the log (or if the log
2811 ** is wrapped and written for that matter) before the READ_LOCK(0)
2812 ** is obtained, that is not necessarily true. A checkpointer may
2813 ** have started to backfill the appended frames but crashed before
2814 ** it finished. Leaving a corrupt image in the database file.
2815 */
2816 walUnlockShared(pWal, WAL_READ_LOCK(0));
2817 return WAL_RETRY;
2818 }
2819 pWal->readLock = 0;
2820 return SQLITE_OK;
2821 }else if( rc!=SQLITE_BUSY ){
2822 return rc;
2823 }
2824 }
2825
2826 /* If we get this far, it means that the reader will want to use
2827 ** the WAL to get at content from recent commits. The job now is
2828 ** to select one of the aReadMark[] entries that is closest to
2829 ** but not exceeding pWal->hdr.mxFrame and lock that entry.
2830 */
2831 mxReadMark = 0;
2832 mxI = 0;
2833 mxFrame = pWal->hdr.mxFrame;
2834#ifdef SQLITE_ENABLE_SNAPSHOT
2835 if( pWal->pSnapshot && pWal->pSnapshot->mxFrame<mxFrame ){
2836 mxFrame = pWal->pSnapshot->mxFrame;
2837 }
2838#endif
2839 for(i=1; i<WAL_NREADER; i++){
2840 u32 thisMark = AtomicLoad(pInfo->aReadMark+i);
2841 if( mxReadMark<=thisMark && thisMark<=mxFrame ){
2842 assert( thisMark!=READMARK_NOT_USED );
2843 mxReadMark = thisMark;
2844 mxI = i;
2845 }
2846 }
2847 if( (pWal->readOnly & WAL_SHM_RDONLY)==0
2848 && (mxReadMark<mxFrame || mxI==0)
2849 ){
2850 for(i=1; i<WAL_NREADER; i++){
2851 rc = walLockExclusive(pWal, WAL_READ_LOCK(i), 1);
2852 if( rc==SQLITE_OK ){
2853 AtomicStore(pInfo->aReadMark+i,mxFrame);
2854 mxReadMark = mxFrame;
2855 mxI = i;
2856 walUnlockExclusive(pWal, WAL_READ_LOCK(i), 1);
2857 break;
2858 }else if( rc!=SQLITE_BUSY ){
2859 return rc;
2860 }
2861 }
2862 }
2863 if( mxI==0 ){
2864 assert( rc==SQLITE_BUSY || (pWal->readOnly & WAL_SHM_RDONLY)!=0 );
2865 return rc==SQLITE_BUSY ? WAL_RETRY : SQLITE_READONLY_CANTINIT;
2866 }
2867
2868 rc = walLockShared(pWal, WAL_READ_LOCK(mxI));
2869 if( rc ){
2870 return rc==SQLITE_BUSY ? WAL_RETRY : rc;
2871 }
2872 /* Now that the read-lock has been obtained, check that neither the
2873 ** value in the aReadMark[] array or the contents of the wal-index
2874 ** header have changed.
2875 **
2876 ** It is necessary to check that the wal-index header did not change
2877 ** between the time it was read and when the shared-lock was obtained
2878 ** on WAL_READ_LOCK(mxI) was obtained to account for the possibility
2879 ** that the log file may have been wrapped by a writer, or that frames
2880 ** that occur later in the log than pWal->hdr.mxFrame may have been
2881 ** copied into the database by a checkpointer. If either of these things
2882 ** happened, then reading the database with the current value of
2883 ** pWal->hdr.mxFrame risks reading a corrupted snapshot. So, retry
2884 ** instead.
2885 **
2886 ** Before checking that the live wal-index header has not changed
2887 ** since it was read, set Wal.minFrame to the first frame in the wal
2888 ** file that has not yet been checkpointed. This client will not need
2889 ** to read any frames earlier than minFrame from the wal file - they
2890 ** can be safely read directly from the database file.
2891 **
2892 ** Because a ShmBarrier() call is made between taking the copy of
2893 ** nBackfill and checking that the wal-header in shared-memory still
2894 ** matches the one cached in pWal->hdr, it is guaranteed that the
2895 ** checkpointer that set nBackfill was not working with a wal-index
2896 ** header newer than that cached in pWal->hdr. If it were, that could
2897 ** cause a problem. The checkpointer could omit to checkpoint
2898 ** a version of page X that lies before pWal->minFrame (call that version
2899 ** A) on the basis that there is a newer version (version B) of the same
2900 ** page later in the wal file. But if version B happens to like past
2901 ** frame pWal->hdr.mxFrame - then the client would incorrectly assume
2902 ** that it can read version A from the database file. However, since
2903 ** we can guarantee that the checkpointer that set nBackfill could not
2904 ** see any pages past pWal->hdr.mxFrame, this problem does not come up.
2905 */
2906 pWal->minFrame = AtomicLoad(&pInfo->nBackfill)+1;
2907 walShmBarrier(pWal);
2908 if( AtomicLoad(pInfo->aReadMark+mxI)!=mxReadMark
2909 || memcmp((void *)walIndexHdr(pWal), &pWal->hdr, sizeof(WalIndexHdr))
2910 ){
2911 walUnlockShared(pWal, WAL_READ_LOCK(mxI));
2912 return WAL_RETRY;
2913 }else{
2914 assert( mxReadMark<=pWal->hdr.mxFrame );
2915 pWal->readLock = (i16)mxI;
2916 }
2917 return rc;
2918}
2919
2920#ifdef SQLITE_ENABLE_SNAPSHOT
2921/*
2922** Attempt to reduce the value of the WalCkptInfo.nBackfillAttempted
2923** variable so that older snapshots can be accessed. To do this, loop
2924** through all wal frames from nBackfillAttempted to (nBackfill+1),
2925** comparing their content to the corresponding page with the database
2926** file, if any. Set nBackfillAttempted to the frame number of the
2927** first frame for which the wal file content matches the db file.
2928**
2929** This is only really safe if the file-system is such that any page
2930** writes made by earlier checkpointers were atomic operations, which
2931** is not always true. It is also possible that nBackfillAttempted
2932** may be left set to a value larger than expected, if a wal frame
2933** contains content that duplicate of an earlier version of the same
2934** page.
2935**
2936** SQLITE_OK is returned if successful, or an SQLite error code if an
2937** error occurs. It is not an error if nBackfillAttempted cannot be
2938** decreased at all.
2939*/
2940int sqlite3WalSnapshotRecover(Wal *pWal){
2941 int rc;
2942
2943 assert( pWal->readLock>=0 );
2944 rc = walLockExclusive(pWal, WAL_CKPT_LOCK, 1);
2945 if( rc==SQLITE_OK ){
2946 volatile WalCkptInfo *pInfo = walCkptInfo(pWal);
2947 int szPage = (int)pWal->szPage;
2948 i64 szDb; /* Size of db file in bytes */
2949
2950 rc = sqlite3OsFileSize(pWal->pDbFd, &szDb);
2951 if( rc==SQLITE_OK ){
2952 void *pBuf1 = sqlite3_malloc(szPage);
2953 void *pBuf2 = sqlite3_malloc(szPage);
2954 if( pBuf1==0 || pBuf2==0 ){
2955 rc = SQLITE_NOMEM;
2956 }else{
2957 u32 i = pInfo->nBackfillAttempted;
2958 for(i=pInfo->nBackfillAttempted; i>AtomicLoad(&pInfo->nBackfill); i--){
2959 WalHashLoc sLoc; /* Hash table location */
2960 u32 pgno; /* Page number in db file */
2961 i64 iDbOff; /* Offset of db file entry */
2962 i64 iWalOff; /* Offset of wal file entry */
2963
2964 rc = walHashGet(pWal, walFramePage(i), &sLoc);
2965 if( rc!=SQLITE_OK ) break;
2966 assert( i - sLoc.iZero - 1 >=0 );
2967 pgno = sLoc.aPgno[i-sLoc.iZero-1];
2968 iDbOff = (i64)(pgno-1) * szPage;
2969
2970 if( iDbOff+szPage<=szDb ){
2971 iWalOff = walFrameOffset(i, szPage) + WAL_FRAME_HDRSIZE;
2972 rc = sqlite3OsRead(pWal->pWalFd, pBuf1, szPage, iWalOff);
2973
2974 if( rc==SQLITE_OK ){
2975 rc = sqlite3OsRead(pWal->pDbFd, pBuf2, szPage, iDbOff);
2976 }
2977
2978 if( rc!=SQLITE_OK || 0==memcmp(pBuf1, pBuf2, szPage) ){
2979 break;
2980 }
2981 }
2982
2983 pInfo->nBackfillAttempted = i-1;
2984 }
2985 }
2986
2987 sqlite3_free(pBuf1);
2988 sqlite3_free(pBuf2);
2989 }
2990 walUnlockExclusive(pWal, WAL_CKPT_LOCK, 1);
2991 }
2992
2993 return rc;
2994}
2995#endif /* SQLITE_ENABLE_SNAPSHOT */
2996
2997/*
2998** Begin a read transaction on the database.
2999**
3000** This routine used to be called sqlite3OpenSnapshot() and with good reason:
3001** it takes a snapshot of the state of the WAL and wal-index for the current
3002** instant in time. The current thread will continue to use this snapshot.
3003** Other threads might append new content to the WAL and wal-index but
3004** that extra content is ignored by the current thread.
3005**
3006** If the database contents have changes since the previous read
3007** transaction, then *pChanged is set to 1 before returning. The
3008** Pager layer will use this to know that its cache is stale and
3009** needs to be flushed.
3010*/
3011int sqlite3WalBeginReadTransaction(Wal *pWal, int *pChanged){
3012 int rc; /* Return code */
3013 int cnt = 0; /* Number of TryBeginRead attempts */
3014#ifdef SQLITE_ENABLE_SNAPSHOT
3015 int bChanged = 0;
3016 WalIndexHdr *pSnapshot = pWal->pSnapshot;
3017#endif
3018
3019 assert( pWal->ckptLock==0 );
3020
3021#ifdef SQLITE_ENABLE_SNAPSHOT
3022 if( pSnapshot ){
3023 if( memcmp(pSnapshot, &pWal->hdr, sizeof(WalIndexHdr))!=0 ){
3024 bChanged = 1;
3025 }
3026
3027 /* It is possible that there is a checkpointer thread running
3028 ** concurrent with this code. If this is the case, it may be that the
3029 ** checkpointer has already determined that it will checkpoint
3030 ** snapshot X, where X is later in the wal file than pSnapshot, but
3031 ** has not yet set the pInfo->nBackfillAttempted variable to indicate
3032 ** its intent. To avoid the race condition this leads to, ensure that
3033 ** there is no checkpointer process by taking a shared CKPT lock
3034 ** before checking pInfo->nBackfillAttempted. */
3035 (void)walEnableBlocking(pWal);
3036 rc = walLockShared(pWal, WAL_CKPT_LOCK);
3037 walDisableBlocking(pWal);
3038
3039 if( rc!=SQLITE_OK ){
3040 return rc;
3041 }
3042 pWal->ckptLock = 1;
3043 }
3044#endif
3045
3046 do{
3047 rc = walTryBeginRead(pWal, pChanged, 0, ++cnt);
3048 }while( rc==WAL_RETRY );
3049 testcase( (rc&0xff)==SQLITE_BUSY );
3050 testcase( (rc&0xff)==SQLITE_IOERR );
3051 testcase( rc==SQLITE_PROTOCOL );
3052 testcase( rc==SQLITE_OK );
3053
3054#ifdef SQLITE_ENABLE_SNAPSHOT
3055 if( rc==SQLITE_OK ){
3056 if( pSnapshot && memcmp(pSnapshot, &pWal->hdr, sizeof(WalIndexHdr))!=0 ){
3057 /* At this point the client has a lock on an aReadMark[] slot holding
3058 ** a value equal to or smaller than pSnapshot->mxFrame, but pWal->hdr
3059 ** is populated with the wal-index header corresponding to the head
3060 ** of the wal file. Verify that pSnapshot is still valid before
3061 ** continuing. Reasons why pSnapshot might no longer be valid:
3062 **
3063 ** (1) The WAL file has been reset since the snapshot was taken.
3064 ** In this case, the salt will have changed.
3065 **
3066 ** (2) A checkpoint as been attempted that wrote frames past
3067 ** pSnapshot->mxFrame into the database file. Note that the
3068 ** checkpoint need not have completed for this to cause problems.
3069 */
3070 volatile WalCkptInfo *pInfo = walCkptInfo(pWal);
3071
3072 assert( pWal->readLock>0 || pWal->hdr.mxFrame==0 );
3073 assert( pInfo->aReadMark[pWal->readLock]<=pSnapshot->mxFrame );
3074
3075 /* Check that the wal file has not been wrapped. Assuming that it has
3076 ** not, also check that no checkpointer has attempted to checkpoint any
3077 ** frames beyond pSnapshot->mxFrame. If either of these conditions are
3078 ** true, return SQLITE_ERROR_SNAPSHOT. Otherwise, overwrite pWal->hdr
3079 ** with *pSnapshot and set *pChanged as appropriate for opening the
3080 ** snapshot. */
3081 if( !memcmp(pSnapshot->aSalt, pWal->hdr.aSalt, sizeof(pWal->hdr.aSalt))
3082 && pSnapshot->mxFrame>=pInfo->nBackfillAttempted
3083 ){
3084 assert( pWal->readLock>0 );
3085 memcpy(&pWal->hdr, pSnapshot, sizeof(WalIndexHdr));
3086 *pChanged = bChanged;
3087 }else{
3088 rc = SQLITE_ERROR_SNAPSHOT;
3089 }
3090
3091 /* A client using a non-current snapshot may not ignore any frames
3092 ** from the start of the wal file. This is because, for a system
3093 ** where (minFrame < iSnapshot < maxFrame), a checkpointer may
3094 ** have omitted to checkpoint a frame earlier than minFrame in
3095 ** the file because there exists a frame after iSnapshot that
3096 ** is the same database page. */
3097 pWal->minFrame = 1;
3098
3099 if( rc!=SQLITE_OK ){
3100 sqlite3WalEndReadTransaction(pWal);
3101 }
3102 }
3103 }
3104
3105 /* Release the shared CKPT lock obtained above. */
3106 if( pWal->ckptLock ){
3107 assert( pSnapshot );
3108 walUnlockShared(pWal, WAL_CKPT_LOCK);
3109 pWal->ckptLock = 0;
3110 }
3111#endif
3112 return rc;
3113}
3114
3115/*
3116** Finish with a read transaction. All this does is release the
3117** read-lock.
3118*/
3119void sqlite3WalEndReadTransaction(Wal *pWal){
3120 sqlite3WalEndWriteTransaction(pWal);
3121 if( pWal->readLock>=0 ){
3122 walUnlockShared(pWal, WAL_READ_LOCK(pWal->readLock));
3123 pWal->readLock = -1;
3124 }
3125}
3126
3127/*
3128** Search the wal file for page pgno. If found, set *piRead to the frame that
3129** contains the page. Otherwise, if pgno is not in the wal file, set *piRead
3130** to zero.
3131**
3132** Return SQLITE_OK if successful, or an error code if an error occurs. If an
3133** error does occur, the final value of *piRead is undefined.
3134*/
3135int sqlite3WalFindFrame(
3136 Wal *pWal, /* WAL handle */
3137 Pgno pgno, /* Database page number to read data for */
3138 u32 *piRead /* OUT: Frame number (or zero) */
3139){
3140 u32 iRead = 0; /* If !=0, WAL frame to return data from */
3141 u32 iLast = pWal->hdr.mxFrame; /* Last page in WAL for this reader */
3142 int iHash; /* Used to loop through N hash tables */
3143 int iMinHash;
3144
3145 /* This routine is only be called from within a read transaction. */
3146 assert( pWal->readLock>=0 || pWal->lockError );
3147
3148 /* If the "last page" field of the wal-index header snapshot is 0, then
3149 ** no data will be read from the wal under any circumstances. Return early
3150 ** in this case as an optimization. Likewise, if pWal->readLock==0,
3151 ** then the WAL is ignored by the reader so return early, as if the
3152 ** WAL were empty.
3153 */
3154 if( iLast==0 || (pWal->readLock==0 && pWal->bShmUnreliable==0) ){
3155 *piRead = 0;
3156 return SQLITE_OK;
3157 }
3158
3159 /* Search the hash table or tables for an entry matching page number
3160 ** pgno. Each iteration of the following for() loop searches one
3161 ** hash table (each hash table indexes up to HASHTABLE_NPAGE frames).
3162 **
3163 ** This code might run concurrently to the code in walIndexAppend()
3164 ** that adds entries to the wal-index (and possibly to this hash
3165 ** table). This means the value just read from the hash
3166 ** slot (aHash[iKey]) may have been added before or after the
3167 ** current read transaction was opened. Values added after the
3168 ** read transaction was opened may have been written incorrectly -
3169 ** i.e. these slots may contain garbage data. However, we assume
3170 ** that any slots written before the current read transaction was
3171 ** opened remain unmodified.
3172 **
3173 ** For the reasons above, the if(...) condition featured in the inner
3174 ** loop of the following block is more stringent that would be required
3175 ** if we had exclusive access to the hash-table:
3176 **
3177 ** (aPgno[iFrame]==pgno):
3178 ** This condition filters out normal hash-table collisions.
3179 **
3180 ** (iFrame<=iLast):
3181 ** This condition filters out entries that were added to the hash
3182 ** table after the current read-transaction had started.
3183 */
3184 iMinHash = walFramePage(pWal->minFrame);
3185 for(iHash=walFramePage(iLast); iHash>=iMinHash; iHash--){
3186 WalHashLoc sLoc; /* Hash table location */
3187 int iKey; /* Hash slot index */
3188 int nCollide; /* Number of hash collisions remaining */
3189 int rc; /* Error code */
3190 u32 iH;
3191
3192 rc = walHashGet(pWal, iHash, &sLoc);
3193 if( rc!=SQLITE_OK ){
3194 return rc;
3195 }
3196 nCollide = HASHTABLE_NSLOT;
3197 iKey = walHash(pgno);
3198 while( (iH = AtomicLoad(&sLoc.aHash[iKey]))!=0 ){
3199 u32 iFrame = iH + sLoc.iZero;
3200 if( iFrame<=iLast && iFrame>=pWal->minFrame && sLoc.aPgno[iH-1]==pgno ){
3201 assert( iFrame>iRead || CORRUPT_DB );
3202 iRead = iFrame;
3203 }
3204 if( (nCollide--)==0 ){
3205 return SQLITE_CORRUPT_BKPT;
3206 }
3207 iKey = walNextHash(iKey);
3208 }
3209 if( iRead ) break;
3210 }
3211
3212#ifdef SQLITE_ENABLE_EXPENSIVE_ASSERT
3213 /* If expensive assert() statements are available, do a linear search
3214 ** of the wal-index file content. Make sure the results agree with the
3215 ** result obtained using the hash indexes above. */
3216 {
3217 u32 iRead2 = 0;
3218 u32 iTest;
3219 assert( pWal->bShmUnreliable || pWal->minFrame>0 );
3220 for(iTest=iLast; iTest>=pWal->minFrame && iTest>0; iTest--){
3221 if( walFramePgno(pWal, iTest)==pgno ){
3222 iRead2 = iTest;
3223 break;
3224 }
3225 }
3226 assert( iRead==iRead2 );
3227 }
3228#endif
3229
3230 *piRead = iRead;
3231 return SQLITE_OK;
3232}
3233
3234/*
3235** Read the contents of frame iRead from the wal file into buffer pOut
3236** (which is nOut bytes in size). Return SQLITE_OK if successful, or an
3237** error code otherwise.
3238*/
3239int sqlite3WalReadFrame(
3240 Wal *pWal, /* WAL handle */
3241 u32 iRead, /* Frame to read */
3242 int nOut, /* Size of buffer pOut in bytes */
3243 u8 *pOut /* Buffer to write page data to */
3244){
3245 int sz;
3246 i64 iOffset;
3247 sz = pWal->hdr.szPage;
3248 sz = (sz&0xfe00) + ((sz&0x0001)<<16);
3249 testcase( sz<=32768 );
3250 testcase( sz>=65536 );
3251 iOffset = walFrameOffset(iRead, sz) + WAL_FRAME_HDRSIZE;
3252 /* testcase( IS_BIG_INT(iOffset) ); // requires a 4GiB WAL */
3253 return sqlite3OsRead(pWal->pWalFd, pOut, (nOut>sz ? sz : nOut), iOffset);
3254}
3255
3256/*
3257** Return the size of the database in pages (or zero, if unknown).
3258*/
3259Pgno sqlite3WalDbsize(Wal *pWal){
3260 if( pWal && ALWAYS(pWal->readLock>=0) ){
3261 return pWal->hdr.nPage;
3262 }
3263 return 0;
3264}
3265
3266
3267/*
3268** This function starts a write transaction on the WAL.
3269**
3270** A read transaction must have already been started by a prior call
3271** to sqlite3WalBeginReadTransaction().
3272**
3273** If another thread or process has written into the database since
3274** the read transaction was started, then it is not possible for this
3275** thread to write as doing so would cause a fork. So this routine
3276** returns SQLITE_BUSY in that case and no write transaction is started.
3277**
3278** There can only be a single writer active at a time.
3279*/
3280int sqlite3WalBeginWriteTransaction(Wal *pWal){
3281 int rc;
3282
3283#ifdef SQLITE_ENABLE_SETLK_TIMEOUT
3284 /* If the write-lock is already held, then it was obtained before the
3285 ** read-transaction was even opened, making this call a no-op.
3286 ** Return early. */
3287 if( pWal->writeLock ){
3288 assert( !memcmp(&pWal->hdr,(void *)walIndexHdr(pWal),sizeof(WalIndexHdr)) );
3289 return SQLITE_OK;
3290 }
3291#endif
3292
3293 /* Cannot start a write transaction without first holding a read
3294 ** transaction. */
3295 assert( pWal->readLock>=0 );
3296 assert( pWal->writeLock==0 && pWal->iReCksum==0 );
3297
3298 if( pWal->readOnly ){
3299 return SQLITE_READONLY;
3300 }
3301
3302 /* Only one writer allowed at a time. Get the write lock. Return
3303 ** SQLITE_BUSY if unable.
3304 */
3305 rc = walLockExclusive(pWal, WAL_WRITE_LOCK, 1);
3306 if( rc ){
3307 return rc;
3308 }
3309 pWal->writeLock = 1;
3310
3311 /* If another connection has written to the database file since the
3312 ** time the read transaction on this connection was started, then
3313 ** the write is disallowed.
3314 */
3315 if( memcmp(&pWal->hdr, (void *)walIndexHdr(pWal), sizeof(WalIndexHdr))!=0 ){
3316 walUnlockExclusive(pWal, WAL_WRITE_LOCK, 1);
3317 pWal->writeLock = 0;
3318 rc = SQLITE_BUSY_SNAPSHOT;
3319 }
3320
3321 return rc;
3322}
3323
3324/*
3325** End a write transaction. The commit has already been done. This
3326** routine merely releases the lock.
3327*/
3328int sqlite3WalEndWriteTransaction(Wal *pWal){
3329 if( pWal->writeLock ){
3330 walUnlockExclusive(pWal, WAL_WRITE_LOCK, 1);
3331 pWal->writeLock = 0;
3332 pWal->iReCksum = 0;
3333 pWal->truncateOnCommit = 0;
3334 }
3335 return SQLITE_OK;
3336}
3337
3338/*
3339** If any data has been written (but not committed) to the log file, this
3340** function moves the write-pointer back to the start of the transaction.
3341**
3342** Additionally, the callback function is invoked for each frame written
3343** to the WAL since the start of the transaction. If the callback returns
3344** other than SQLITE_OK, it is not invoked again and the error code is
3345** returned to the caller.
3346**
3347** Otherwise, if the callback function does not return an error, this
3348** function returns SQLITE_OK.
3349*/
3350int sqlite3WalUndo(Wal *pWal, int (*xUndo)(void *, Pgno), void *pUndoCtx){
3351 int rc = SQLITE_OK;
3352 if( ALWAYS(pWal->writeLock) ){
3353 Pgno iMax = pWal->hdr.mxFrame;
3354 Pgno iFrame;
3355
3356 /* Restore the clients cache of the wal-index header to the state it
3357 ** was in before the client began writing to the database.
3358 */
3359 memcpy(&pWal->hdr, (void *)walIndexHdr(pWal), sizeof(WalIndexHdr));
3360
3361 for(iFrame=pWal->hdr.mxFrame+1;
3362 ALWAYS(rc==SQLITE_OK) && iFrame<=iMax;
3363 iFrame++
3364 ){
3365 /* This call cannot fail. Unless the page for which the page number
3366 ** is passed as the second argument is (a) in the cache and
3367 ** (b) has an outstanding reference, then xUndo is either a no-op
3368 ** (if (a) is false) or simply expels the page from the cache (if (b)
3369 ** is false).
3370 **
3371 ** If the upper layer is doing a rollback, it is guaranteed that there
3372 ** are no outstanding references to any page other than page 1. And
3373 ** page 1 is never written to the log until the transaction is
3374 ** committed. As a result, the call to xUndo may not fail.
3375 */
3376 assert( walFramePgno(pWal, iFrame)!=1 );
3377 rc = xUndo(pUndoCtx, walFramePgno(pWal, iFrame));
3378 }
3379 if( iMax!=pWal->hdr.mxFrame ) walCleanupHash(pWal);
3380 }
3381 return rc;
3382}
3383
3384/*
3385** Argument aWalData must point to an array of WAL_SAVEPOINT_NDATA u32
3386** values. This function populates the array with values required to
3387** "rollback" the write position of the WAL handle back to the current
3388** point in the event of a savepoint rollback (via WalSavepointUndo()).
3389*/
3390void sqlite3WalSavepoint(Wal *pWal, u32 *aWalData){
3391 assert( pWal->writeLock );
3392 aWalData[0] = pWal->hdr.mxFrame;
3393 aWalData[1] = pWal->hdr.aFrameCksum[0];
3394 aWalData[2] = pWal->hdr.aFrameCksum[1];
3395 aWalData[3] = pWal->nCkpt;
3396}
3397
3398/*
3399** Move the write position of the WAL back to the point identified by
3400** the values in the aWalData[] array. aWalData must point to an array
3401** of WAL_SAVEPOINT_NDATA u32 values that has been previously populated
3402** by a call to WalSavepoint().
3403*/
3404int sqlite3WalSavepointUndo(Wal *pWal, u32 *aWalData){
3405 int rc = SQLITE_OK;
3406
3407 assert( pWal->writeLock );
3408 assert( aWalData[3]!=pWal->nCkpt || aWalData[0]<=pWal->hdr.mxFrame );
3409
3410 if( aWalData[3]!=pWal->nCkpt ){
3411 /* This savepoint was opened immediately after the write-transaction
3412 ** was started. Right after that, the writer decided to wrap around
3413 ** to the start of the log. Update the savepoint values to match.
3414 */
3415 aWalData[0] = 0;
3416 aWalData[3] = pWal->nCkpt;
3417 }
3418
3419 if( aWalData[0]<pWal->hdr.mxFrame ){
3420 pWal->hdr.mxFrame = aWalData[0];
3421 pWal->hdr.aFrameCksum[0] = aWalData[1];
3422 pWal->hdr.aFrameCksum[1] = aWalData[2];
3423 walCleanupHash(pWal);
3424 }
3425
3426 return rc;
3427}
3428
3429/*
3430** This function is called just before writing a set of frames to the log
3431** file (see sqlite3WalFrames()). It checks to see if, instead of appending
3432** to the current log file, it is possible to overwrite the start of the
3433** existing log file with the new frames (i.e. "reset" the log). If so,
3434** it sets pWal->hdr.mxFrame to 0. Otherwise, pWal->hdr.mxFrame is left
3435** unchanged.
3436**
3437** SQLITE_OK is returned if no error is encountered (regardless of whether
3438** or not pWal->hdr.mxFrame is modified). An SQLite error code is returned
3439** if an error occurs.
3440*/
3441static int walRestartLog(Wal *pWal){
3442 int rc = SQLITE_OK;
3443 int cnt;
3444
3445 if( pWal->readLock==0 ){
3446 volatile WalCkptInfo *pInfo = walCkptInfo(pWal);
3447 assert( pInfo->nBackfill==pWal->hdr.mxFrame );
3448 if( pInfo->nBackfill>0 ){
3449 u32 salt1;
3450 sqlite3_randomness(4, &salt1);
3451 rc = walLockExclusive(pWal, WAL_READ_LOCK(1), WAL_NREADER-1);
3452 if( rc==SQLITE_OK ){
3453 /* If all readers are using WAL_READ_LOCK(0) (in other words if no
3454 ** readers are currently using the WAL), then the transactions
3455 ** frames will overwrite the start of the existing log. Update the
3456 ** wal-index header to reflect this.
3457 **
3458 ** In theory it would be Ok to update the cache of the header only
3459 ** at this point. But updating the actual wal-index header is also
3460 ** safe and means there is no special case for sqlite3WalUndo()
3461 ** to handle if this transaction is rolled back. */
3462 walRestartHdr(pWal, salt1);
3463 walUnlockExclusive(pWal, WAL_READ_LOCK(1), WAL_NREADER-1);
3464 }else if( rc!=SQLITE_BUSY ){
3465 return rc;
3466 }
3467 }
3468 walUnlockShared(pWal, WAL_READ_LOCK(0));
3469 pWal->readLock = -1;
3470 cnt = 0;
3471 do{
3472 int notUsed;
3473 rc = walTryBeginRead(pWal, &notUsed, 1, ++cnt);
3474 }while( rc==WAL_RETRY );
3475 assert( (rc&0xff)!=SQLITE_BUSY ); /* BUSY not possible when useWal==1 */
3476 testcase( (rc&0xff)==SQLITE_IOERR );
3477 testcase( rc==SQLITE_PROTOCOL );
3478 testcase( rc==SQLITE_OK );
3479 }
3480 return rc;
3481}
3482
3483/*
3484** Information about the current state of the WAL file and where
3485** the next fsync should occur - passed from sqlite3WalFrames() into
3486** walWriteToLog().
3487*/
3488typedef struct WalWriter {
3489 Wal *pWal; /* The complete WAL information */
3490 sqlite3_file *pFd; /* The WAL file to which we write */
3491 sqlite3_int64 iSyncPoint; /* Fsync at this offset */
3492 int syncFlags; /* Flags for the fsync */
3493 int szPage; /* Size of one page */
3494} WalWriter;
3495
3496/*
3497** Write iAmt bytes of content into the WAL file beginning at iOffset.
3498** Do a sync when crossing the p->iSyncPoint boundary.
3499**
3500** In other words, if iSyncPoint is in between iOffset and iOffset+iAmt,
3501** first write the part before iSyncPoint, then sync, then write the
3502** rest.
3503*/
3504static int walWriteToLog(
3505 WalWriter *p, /* WAL to write to */
3506 void *pContent, /* Content to be written */
3507 int iAmt, /* Number of bytes to write */
3508 sqlite3_int64 iOffset /* Start writing at this offset */
3509){
3510 int rc;
3511 if( iOffset<p->iSyncPoint && iOffset+iAmt>=p->iSyncPoint ){
3512 int iFirstAmt = (int)(p->iSyncPoint - iOffset);
3513 rc = sqlite3OsWrite(p->pFd, pContent, iFirstAmt, iOffset);
3514 if( rc ) return rc;
3515 iOffset += iFirstAmt;
3516 iAmt -= iFirstAmt;
3517 pContent = (void*)(iFirstAmt + (char*)pContent);
3518 assert( WAL_SYNC_FLAGS(p->syncFlags)!=0 );
3519 rc = sqlite3OsSync(p->pFd, WAL_SYNC_FLAGS(p->syncFlags));
3520 if( iAmt==0 || rc ) return rc;
3521 }
3522 rc = sqlite3OsWrite(p->pFd, pContent, iAmt, iOffset);
3523 return rc;
3524}
3525
3526/*
3527** Write out a single frame of the WAL
3528*/
3529static int walWriteOneFrame(
3530 WalWriter *p, /* Where to write the frame */
3531 PgHdr *pPage, /* The page of the frame to be written */
3532 int nTruncate, /* The commit flag. Usually 0. >0 for commit */
3533 sqlite3_int64 iOffset /* Byte offset at which to write */
3534){
3535 int rc; /* Result code from subfunctions */
3536 void *pData; /* Data actually written */
3537 u8 aFrame[WAL_FRAME_HDRSIZE]; /* Buffer to assemble frame-header in */
3538 pData = pPage->pData;
3539 walEncodeFrame(p->pWal, pPage->pgno, nTruncate, pData, aFrame);
3540 rc = walWriteToLog(p, aFrame, sizeof(aFrame), iOffset);
3541 if( rc ) return rc;
3542 /* Write the page data */
3543 rc = walWriteToLog(p, pData, p->szPage, iOffset+sizeof(aFrame));
3544 return rc;
3545}
3546
3547/*
3548** This function is called as part of committing a transaction within which
3549** one or more frames have been overwritten. It updates the checksums for
3550** all frames written to the wal file by the current transaction starting
3551** with the earliest to have been overwritten.
3552**
3553** SQLITE_OK is returned if successful, or an SQLite error code otherwise.
3554*/
3555static int walRewriteChecksums(Wal *pWal, u32 iLast){
3556 const int szPage = pWal->szPage;/* Database page size */
3557 int rc = SQLITE_OK; /* Return code */
3558 u8 *aBuf; /* Buffer to load data from wal file into */
3559 u8 aFrame[WAL_FRAME_HDRSIZE]; /* Buffer to assemble frame-headers in */
3560 u32 iRead; /* Next frame to read from wal file */
3561 i64 iCksumOff;
3562
3563 aBuf = sqlite3_malloc(szPage + WAL_FRAME_HDRSIZE);
3564 if( aBuf==0 ) return SQLITE_NOMEM_BKPT;
3565
3566 /* Find the checksum values to use as input for the recalculating the
3567 ** first checksum. If the first frame is frame 1 (implying that the current
3568 ** transaction restarted the wal file), these values must be read from the
3569 ** wal-file header. Otherwise, read them from the frame header of the
3570 ** previous frame. */
3571 assert( pWal->iReCksum>0 );
3572 if( pWal->iReCksum==1 ){
3573 iCksumOff = 24;
3574 }else{
3575 iCksumOff = walFrameOffset(pWal->iReCksum-1, szPage) + 16;
3576 }
3577 rc = sqlite3OsRead(pWal->pWalFd, aBuf, sizeof(u32)*2, iCksumOff);
3578 pWal->hdr.aFrameCksum[0] = sqlite3Get4byte(aBuf);
3579 pWal->hdr.aFrameCksum[1] = sqlite3Get4byte(&aBuf[sizeof(u32)]);
3580
3581 iRead = pWal->iReCksum;
3582 pWal->iReCksum = 0;
3583 for(; rc==SQLITE_OK && iRead<=iLast; iRead++){
3584 i64 iOff = walFrameOffset(iRead, szPage);
3585 rc = sqlite3OsRead(pWal->pWalFd, aBuf, szPage+WAL_FRAME_HDRSIZE, iOff);
3586 if( rc==SQLITE_OK ){
3587 u32 iPgno, nDbSize;
3588 iPgno = sqlite3Get4byte(aBuf);
3589 nDbSize = sqlite3Get4byte(&aBuf[4]);
3590
3591 walEncodeFrame(pWal, iPgno, nDbSize, &aBuf[WAL_FRAME_HDRSIZE], aFrame);
3592 rc = sqlite3OsWrite(pWal->pWalFd, aFrame, sizeof(aFrame), iOff);
3593 }
3594 }
3595
3596 sqlite3_free(aBuf);
3597 return rc;
3598}
3599
3600/*
3601** Write a set of frames to the log. The caller must hold the write-lock
3602** on the log file (obtained using sqlite3WalBeginWriteTransaction()).
3603*/
3604int sqlite3WalFrames(
3605 Wal *pWal, /* Wal handle to write to */
3606 int szPage, /* Database page-size in bytes */
3607 PgHdr *pList, /* List of dirty pages to write */
3608 Pgno nTruncate, /* Database size after this commit */
3609 int isCommit, /* True if this is a commit */
3610 int sync_flags /* Flags to pass to OsSync() (or 0) */
3611){
3612 int rc; /* Used to catch return codes */
3613 u32 iFrame; /* Next frame address */
3614 PgHdr *p; /* Iterator to run through pList with. */
3615 PgHdr *pLast = 0; /* Last frame in list */
3616 int nExtra = 0; /* Number of extra copies of last page */
3617 int szFrame; /* The size of a single frame */
3618 i64 iOffset; /* Next byte to write in WAL file */
3619 WalWriter w; /* The writer */
3620 u32 iFirst = 0; /* First frame that may be overwritten */
3621 WalIndexHdr *pLive; /* Pointer to shared header */
3622
3623 assert( pList );
3624 assert( pWal->writeLock );
3625
3626 /* If this frame set completes a transaction, then nTruncate>0. If
3627 ** nTruncate==0 then this frame set does not complete the transaction. */
3628 assert( (isCommit!=0)==(nTruncate!=0) );
3629
3630#if defined(SQLITE_TEST) && defined(SQLITE_DEBUG)
3631 { int cnt; for(cnt=0, p=pList; p; p=p->pDirty, cnt++){}
3632 WALTRACE(("WAL%p: frame write begin. %d frames. mxFrame=%d. %s\n",
3633 pWal, cnt, pWal->hdr.mxFrame, isCommit ? "Commit" : "Spill"));
3634 }
3635#endif
3636
3637 pLive = (WalIndexHdr*)walIndexHdr(pWal);
3638 if( memcmp(&pWal->hdr, (void *)pLive, sizeof(WalIndexHdr))!=0 ){
3639 iFirst = pLive->mxFrame+1;
3640 }
3641
3642 /* See if it is possible to write these frames into the start of the
3643 ** log file, instead of appending to it at pWal->hdr.mxFrame.
3644 */
3645 if( SQLITE_OK!=(rc = walRestartLog(pWal)) ){
3646 return rc;
3647 }
3648
3649 /* If this is the first frame written into the log, write the WAL
3650 ** header to the start of the WAL file. See comments at the top of
3651 ** this source file for a description of the WAL header format.
3652 */
3653 iFrame = pWal->hdr.mxFrame;
3654 if( iFrame==0 ){
3655 u8 aWalHdr[WAL_HDRSIZE]; /* Buffer to assemble wal-header in */
3656 u32 aCksum[2]; /* Checksum for wal-header */
3657
3658 sqlite3Put4byte(&aWalHdr[0], (WAL_MAGIC | SQLITE_BIGENDIAN));
3659 sqlite3Put4byte(&aWalHdr[4], WAL_MAX_VERSION);
3660 sqlite3Put4byte(&aWalHdr[8], szPage);
3661 sqlite3Put4byte(&aWalHdr[12], pWal->nCkpt);
3662 if( pWal->nCkpt==0 ) sqlite3_randomness(8, pWal->hdr.aSalt);
3663 memcpy(&aWalHdr[16], pWal->hdr.aSalt, 8);
3664 walChecksumBytes(1, aWalHdr, WAL_HDRSIZE-2*4, 0, aCksum);
3665 sqlite3Put4byte(&aWalHdr[24], aCksum[0]);
3666 sqlite3Put4byte(&aWalHdr[28], aCksum[1]);
3667
3668 pWal->szPage = szPage;
3669 pWal->hdr.bigEndCksum = SQLITE_BIGENDIAN;
3670 pWal->hdr.aFrameCksum[0] = aCksum[0];
3671 pWal->hdr.aFrameCksum[1] = aCksum[1];
3672 pWal->truncateOnCommit = 1;
3673
3674 rc = sqlite3OsWrite(pWal->pWalFd, aWalHdr, sizeof(aWalHdr), 0);
3675 WALTRACE(("WAL%p: wal-header write %s\n", pWal, rc ? "failed" : "ok"));
3676 if( rc!=SQLITE_OK ){
3677 return rc;
3678 }
3679
3680 /* Sync the header (unless SQLITE_IOCAP_SEQUENTIAL is true or unless
3681 ** all syncing is turned off by PRAGMA synchronous=OFF). Otherwise
3682 ** an out-of-order write following a WAL restart could result in
3683 ** database corruption. See the ticket:
3684 **
3685 ** https://sqlite.org/src/info/ff5be73dee
3686 */
3687 if( pWal->syncHeader ){
3688 rc = sqlite3OsSync(pWal->pWalFd, CKPT_SYNC_FLAGS(sync_flags));
3689 if( rc ) return rc;
3690 }
3691 }
3692 assert( (int)pWal->szPage==szPage );
3693
3694 /* Setup information needed to write frames into the WAL */
3695 w.pWal = pWal;
3696 w.pFd = pWal->pWalFd;
3697 w.iSyncPoint = 0;
3698 w.syncFlags = sync_flags;
3699 w.szPage = szPage;
3700 iOffset = walFrameOffset(iFrame+1, szPage);
3701 szFrame = szPage + WAL_FRAME_HDRSIZE;
3702
3703 /* Write all frames into the log file exactly once */
3704 for(p=pList; p; p=p->pDirty){
3705 int nDbSize; /* 0 normally. Positive == commit flag */
3706
3707 /* Check if this page has already been written into the wal file by
3708 ** the current transaction. If so, overwrite the existing frame and
3709 ** set Wal.writeLock to WAL_WRITELOCK_RECKSUM - indicating that
3710 ** checksums must be recomputed when the transaction is committed. */
3711 if( iFirst && (p->pDirty || isCommit==0) ){
3712 u32 iWrite = 0;
3713 VVA_ONLY(rc =) sqlite3WalFindFrame(pWal, p->pgno, &iWrite);
3714 assert( rc==SQLITE_OK || iWrite==0 );
3715 if( iWrite>=iFirst ){
3716 i64 iOff = walFrameOffset(iWrite, szPage) + WAL_FRAME_HDRSIZE;
3717 void *pData;
3718 if( pWal->iReCksum==0 || iWrite<pWal->iReCksum ){
3719 pWal->iReCksum = iWrite;
3720 }
3721 pData = p->pData;
3722 rc = sqlite3OsWrite(pWal->pWalFd, pData, szPage, iOff);
3723 if( rc ) return rc;
3724 p->flags &= ~PGHDR_WAL_APPEND;
3725 continue;
3726 }
3727 }
3728
3729 iFrame++;
3730 assert( iOffset==walFrameOffset(iFrame, szPage) );
3731 nDbSize = (isCommit && p->pDirty==0) ? nTruncate : 0;
3732 rc = walWriteOneFrame(&w, p, nDbSize, iOffset);
3733 if( rc ) return rc;
3734 pLast = p;
3735 iOffset += szFrame;
3736 p->flags |= PGHDR_WAL_APPEND;
3737 }
3738
3739 /* Recalculate checksums within the wal file if required. */
3740 if( isCommit && pWal->iReCksum ){
3741 rc = walRewriteChecksums(pWal, iFrame);
3742 if( rc ) return rc;
3743 }
3744
3745 /* If this is the end of a transaction, then we might need to pad
3746 ** the transaction and/or sync the WAL file.
3747 **
3748 ** Padding and syncing only occur if this set of frames complete a
3749 ** transaction and if PRAGMA synchronous=FULL. If synchronous==NORMAL
3750 ** or synchronous==OFF, then no padding or syncing are needed.
3751 **
3752 ** If SQLITE_IOCAP_POWERSAFE_OVERWRITE is defined, then padding is not
3753 ** needed and only the sync is done. If padding is needed, then the
3754 ** final frame is repeated (with its commit mark) until the next sector
3755 ** boundary is crossed. Only the part of the WAL prior to the last
3756 ** sector boundary is synced; the part of the last frame that extends
3757 ** past the sector boundary is written after the sync.
3758 */
3759 if( isCommit && WAL_SYNC_FLAGS(sync_flags)!=0 ){
3760 int bSync = 1;
3761 if( pWal->padToSectorBoundary ){
3762 int sectorSize = sqlite3SectorSize(pWal->pWalFd);
3763 w.iSyncPoint = ((iOffset+sectorSize-1)/sectorSize)*sectorSize;
3764 bSync = (w.iSyncPoint==iOffset);
3765 testcase( bSync );
3766 while( iOffset<w.iSyncPoint ){
3767 rc = walWriteOneFrame(&w, pLast, nTruncate, iOffset);
3768 if( rc ) return rc;
3769 iOffset += szFrame;
3770 nExtra++;
3771 assert( pLast!=0 );
3772 }
3773 }
3774 if( bSync ){
3775 assert( rc==SQLITE_OK );
3776 rc = sqlite3OsSync(w.pFd, WAL_SYNC_FLAGS(sync_flags));
3777 }
3778 }
3779
3780 /* If this frame set completes the first transaction in the WAL and
3781 ** if PRAGMA journal_size_limit is set, then truncate the WAL to the
3782 ** journal size limit, if possible.
3783 */
3784 if( isCommit && pWal->truncateOnCommit && pWal->mxWalSize>=0 ){
3785 i64 sz = pWal->mxWalSize;
3786 if( walFrameOffset(iFrame+nExtra+1, szPage)>pWal->mxWalSize ){
3787 sz = walFrameOffset(iFrame+nExtra+1, szPage);
3788 }
3789 walLimitSize(pWal, sz);
3790 pWal->truncateOnCommit = 0;
3791 }
3792
3793 /* Append data to the wal-index. It is not necessary to lock the
3794 ** wal-index to do this as the SQLITE_SHM_WRITE lock held on the wal-index
3795 ** guarantees that there are no other writers, and no data that may
3796 ** be in use by existing readers is being overwritten.
3797 */
3798 iFrame = pWal->hdr.mxFrame;
3799 for(p=pList; p && rc==SQLITE_OK; p=p->pDirty){
3800 if( (p->flags & PGHDR_WAL_APPEND)==0 ) continue;
3801 iFrame++;
3802 rc = walIndexAppend(pWal, iFrame, p->pgno);
3803 }
3804 assert( pLast!=0 || nExtra==0 );
3805 while( rc==SQLITE_OK && nExtra>0 ){
3806 iFrame++;
3807 nExtra--;
3808 rc = walIndexAppend(pWal, iFrame, pLast->pgno);
3809 }
3810
3811 if( rc==SQLITE_OK ){
3812 /* Update the private copy of the header. */
3813 pWal->hdr.szPage = (u16)((szPage&0xff00) | (szPage>>16));
3814 testcase( szPage<=32768 );
3815 testcase( szPage>=65536 );
3816 pWal->hdr.mxFrame = iFrame;
3817 if( isCommit ){
3818 pWal->hdr.iChange++;
3819 pWal->hdr.nPage = nTruncate;
3820 }
3821 /* If this is a commit, update the wal-index header too. */
3822 if( isCommit ){
3823 walIndexWriteHdr(pWal);
3824 pWal->iCallback = iFrame;
3825 }
3826 }
3827
3828 WALTRACE(("WAL%p: frame write %s\n", pWal, rc ? "failed" : "ok"));
3829 return rc;
3830}
3831
3832/*
3833** This routine is called to implement sqlite3_wal_checkpoint() and
3834** related interfaces.
3835**
3836** Obtain a CHECKPOINT lock and then backfill as much information as
3837** we can from WAL into the database.
3838**
3839** If parameter xBusy is not NULL, it is a pointer to a busy-handler
3840** callback. In this case this function runs a blocking checkpoint.
3841*/
3842int sqlite3WalCheckpoint(
3843 Wal *pWal, /* Wal connection */
3844 sqlite3 *db, /* Check this handle's interrupt flag */
3845 int eMode, /* PASSIVE, FULL, RESTART, or TRUNCATE */
3846 int (*xBusy)(void*), /* Function to call when busy */
3847 void *pBusyArg, /* Context argument for xBusyHandler */
3848 int sync_flags, /* Flags to sync db file with (or 0) */
3849 int nBuf, /* Size of temporary buffer */
3850 u8 *zBuf, /* Temporary buffer to use */
3851 int *pnLog, /* OUT: Number of frames in WAL */
3852 int *pnCkpt /* OUT: Number of backfilled frames in WAL */
3853){
3854 int rc; /* Return code */
3855 int isChanged = 0; /* True if a new wal-index header is loaded */
3856 int eMode2 = eMode; /* Mode to pass to walCheckpoint() */
3857 int (*xBusy2)(void*) = xBusy; /* Busy handler for eMode2 */
3858
3859 assert( pWal->ckptLock==0 );
3860 assert( pWal->writeLock==0 );
3861
3862 /* EVIDENCE-OF: R-62920-47450 The busy-handler callback is never invoked
3863 ** in the SQLITE_CHECKPOINT_PASSIVE mode. */
3864 assert( eMode!=SQLITE_CHECKPOINT_PASSIVE || xBusy==0 );
3865
3866 if( pWal->readOnly ) return SQLITE_READONLY;
3867 WALTRACE(("WAL%p: checkpoint begins\n", pWal));
3868
3869 /* Enable blocking locks, if possible. If blocking locks are successfully
3870 ** enabled, set xBusy2=0 so that the busy-handler is never invoked. */
3871 sqlite3WalDb(pWal, db);
3872 (void)walEnableBlocking(pWal);
3873
3874 /* IMPLEMENTATION-OF: R-62028-47212 All calls obtain an exclusive
3875 ** "checkpoint" lock on the database file.
3876 ** EVIDENCE-OF: R-10421-19736 If any other process is running a
3877 ** checkpoint operation at the same time, the lock cannot be obtained and
3878 ** SQLITE_BUSY is returned.
3879 ** EVIDENCE-OF: R-53820-33897 Even if there is a busy-handler configured,
3880 ** it will not be invoked in this case.
3881 */
3882 rc = walLockExclusive(pWal, WAL_CKPT_LOCK, 1);
3883 testcase( rc==SQLITE_BUSY );
3884 testcase( rc!=SQLITE_OK && xBusy2!=0 );
3885 if( rc==SQLITE_OK ){
3886 pWal->ckptLock = 1;
3887
3888 /* IMPLEMENTATION-OF: R-59782-36818 The SQLITE_CHECKPOINT_FULL, RESTART and
3889 ** TRUNCATE modes also obtain the exclusive "writer" lock on the database
3890 ** file.
3891 **
3892 ** EVIDENCE-OF: R-60642-04082 If the writer lock cannot be obtained
3893 ** immediately, and a busy-handler is configured, it is invoked and the
3894 ** writer lock retried until either the busy-handler returns 0 or the
3895 ** lock is successfully obtained.
3896 */
3897 if( eMode!=SQLITE_CHECKPOINT_PASSIVE ){
3898 rc = walBusyLock(pWal, xBusy2, pBusyArg, WAL_WRITE_LOCK, 1);
3899 if( rc==SQLITE_OK ){
3900 pWal->writeLock = 1;
3901 }else if( rc==SQLITE_BUSY ){
3902 eMode2 = SQLITE_CHECKPOINT_PASSIVE;
3903 xBusy2 = 0;
3904 rc = SQLITE_OK;
3905 }
3906 }
3907 }
3908
3909
3910 /* Read the wal-index header. */
3911 if( rc==SQLITE_OK ){
3912 walDisableBlocking(pWal);
3913 rc = walIndexReadHdr(pWal, &isChanged);
3914 (void)walEnableBlocking(pWal);
3915 if( isChanged && pWal->pDbFd->pMethods->iVersion>=3 ){
3916 sqlite3OsUnfetch(pWal->pDbFd, 0, 0);
3917 }
3918 }
3919
3920 /* Copy data from the log to the database file. */
3921 if( rc==SQLITE_OK ){
3922
3923 if( pWal->hdr.mxFrame && walPagesize(pWal)!=nBuf ){
3924 rc = SQLITE_CORRUPT_BKPT;
3925 }else{
3926 rc = walCheckpoint(pWal, db, eMode2, xBusy2, pBusyArg, sync_flags, zBuf);
3927 }
3928
3929 /* If no error occurred, set the output variables. */
3930 if( rc==SQLITE_OK || rc==SQLITE_BUSY ){
3931 if( pnLog ) *pnLog = (int)pWal->hdr.mxFrame;
3932 if( pnCkpt ) *pnCkpt = (int)(walCkptInfo(pWal)->nBackfill);
3933 }
3934 }
3935
3936 if( isChanged ){
3937 /* If a new wal-index header was loaded before the checkpoint was
3938 ** performed, then the pager-cache associated with pWal is now
3939 ** out of date. So zero the cached wal-index header to ensure that
3940 ** next time the pager opens a snapshot on this database it knows that
3941 ** the cache needs to be reset.
3942 */
3943 memset(&pWal->hdr, 0, sizeof(WalIndexHdr));
3944 }
3945
3946 walDisableBlocking(pWal);
3947 sqlite3WalDb(pWal, 0);
3948
3949 /* Release the locks. */
3950 sqlite3WalEndWriteTransaction(pWal);
3951 if( pWal->ckptLock ){
3952 walUnlockExclusive(pWal, WAL_CKPT_LOCK, 1);
3953 pWal->ckptLock = 0;
3954 }
3955 WALTRACE(("WAL%p: checkpoint %s\n", pWal, rc ? "failed" : "ok"));
3956#ifdef SQLITE_ENABLE_SETLK_TIMEOUT
3957 if( rc==SQLITE_BUSY_TIMEOUT ) rc = SQLITE_BUSY;
3958#endif
3959 return (rc==SQLITE_OK && eMode!=eMode2 ? SQLITE_BUSY : rc);
3960}
3961
3962/* Return the value to pass to a sqlite3_wal_hook callback, the
3963** number of frames in the WAL at the point of the last commit since
3964** sqlite3WalCallback() was called. If no commits have occurred since
3965** the last call, then return 0.
3966*/
3967int sqlite3WalCallback(Wal *pWal){
3968 u32 ret = 0;
3969 if( pWal ){
3970 ret = pWal->iCallback;
3971 pWal->iCallback = 0;
3972 }
3973 return (int)ret;
3974}
3975
3976/*
3977** This function is called to change the WAL subsystem into or out
3978** of locking_mode=EXCLUSIVE.
3979**
3980** If op is zero, then attempt to change from locking_mode=EXCLUSIVE
3981** into locking_mode=NORMAL. This means that we must acquire a lock
3982** on the pWal->readLock byte. If the WAL is already in locking_mode=NORMAL
3983** or if the acquisition of the lock fails, then return 0. If the
3984** transition out of exclusive-mode is successful, return 1. This
3985** operation must occur while the pager is still holding the exclusive
3986** lock on the main database file.
3987**
3988** If op is one, then change from locking_mode=NORMAL into
3989** locking_mode=EXCLUSIVE. This means that the pWal->readLock must
3990** be released. Return 1 if the transition is made and 0 if the
3991** WAL is already in exclusive-locking mode - meaning that this
3992** routine is a no-op. The pager must already hold the exclusive lock
3993** on the main database file before invoking this operation.
3994**
3995** If op is negative, then do a dry-run of the op==1 case but do
3996** not actually change anything. The pager uses this to see if it
3997** should acquire the database exclusive lock prior to invoking
3998** the op==1 case.
3999*/
4000int sqlite3WalExclusiveMode(Wal *pWal, int op){
4001 int rc;
4002 assert( pWal->writeLock==0 );
4003 assert( pWal->exclusiveMode!=WAL_HEAPMEMORY_MODE || op==-1 );
4004
4005 /* pWal->readLock is usually set, but might be -1 if there was a
4006 ** prior error while attempting to acquire are read-lock. This cannot
4007 ** happen if the connection is actually in exclusive mode (as no xShmLock
4008 ** locks are taken in this case). Nor should the pager attempt to
4009 ** upgrade to exclusive-mode following such an error.
4010 */
4011 assert( pWal->readLock>=0 || pWal->lockError );
4012 assert( pWal->readLock>=0 || (op<=0 && pWal->exclusiveMode==0) );
4013
4014 if( op==0 ){
4015 if( pWal->exclusiveMode!=WAL_NORMAL_MODE ){
4016 pWal->exclusiveMode = WAL_NORMAL_MODE;
4017 if( walLockShared(pWal, WAL_READ_LOCK(pWal->readLock))!=SQLITE_OK ){
4018 pWal->exclusiveMode = WAL_EXCLUSIVE_MODE;
4019 }
4020 rc = pWal->exclusiveMode==WAL_NORMAL_MODE;
4021 }else{
4022 /* Already in locking_mode=NORMAL */
4023 rc = 0;
4024 }
4025 }else if( op>0 ){
4026 assert( pWal->exclusiveMode==WAL_NORMAL_MODE );
4027 assert( pWal->readLock>=0 );
4028 walUnlockShared(pWal, WAL_READ_LOCK(pWal->readLock));
4029 pWal->exclusiveMode = WAL_EXCLUSIVE_MODE;
4030 rc = 1;
4031 }else{
4032 rc = pWal->exclusiveMode==WAL_NORMAL_MODE;
4033 }
4034 return rc;
4035}
4036
4037/*
4038** Return true if the argument is non-NULL and the WAL module is using
4039** heap-memory for the wal-index. Otherwise, if the argument is NULL or the
4040** WAL module is using shared-memory, return false.
4041*/
4042int sqlite3WalHeapMemory(Wal *pWal){
4043 return (pWal && pWal->exclusiveMode==WAL_HEAPMEMORY_MODE );
4044}
4045
4046#ifdef SQLITE_ENABLE_SNAPSHOT
4047/* Create a snapshot object. The content of a snapshot is opaque to
4048** every other subsystem, so the WAL module can put whatever it needs
4049** in the object.
4050*/
4051int sqlite3WalSnapshotGet(Wal *pWal, sqlite3_snapshot **ppSnapshot){
4052 int rc = SQLITE_OK;
4053 WalIndexHdr *pRet;
4054 static const u32 aZero[4] = { 0, 0, 0, 0 };
4055
4056 assert( pWal->readLock>=0 && pWal->writeLock==0 );
4057
4058 if( memcmp(&pWal->hdr.aFrameCksum[0],aZero,16)==0 ){
4059 *ppSnapshot = 0;
4060 return SQLITE_ERROR;
4061 }
4062 pRet = (WalIndexHdr*)sqlite3_malloc(sizeof(WalIndexHdr));
4063 if( pRet==0 ){
4064 rc = SQLITE_NOMEM_BKPT;
4065 }else{
4066 memcpy(pRet, &pWal->hdr, sizeof(WalIndexHdr));
4067 *ppSnapshot = (sqlite3_snapshot*)pRet;
4068 }
4069
4070 return rc;
4071}
4072
4073/* Try to open on pSnapshot when the next read-transaction starts
4074*/
4075void sqlite3WalSnapshotOpen(
4076 Wal *pWal,
4077 sqlite3_snapshot *pSnapshot
4078){
4079 pWal->pSnapshot = (WalIndexHdr*)pSnapshot;
4080}
4081
4082/*
4083** Return a +ve value if snapshot p1 is newer than p2. A -ve value if
4084** p1 is older than p2 and zero if p1 and p2 are the same snapshot.
4085*/
4086int sqlite3_snapshot_cmp(sqlite3_snapshot *p1, sqlite3_snapshot *p2){
4087 WalIndexHdr *pHdr1 = (WalIndexHdr*)p1;
4088 WalIndexHdr *pHdr2 = (WalIndexHdr*)p2;
4089
4090 /* aSalt[0] is a copy of the value stored in the wal file header. It
4091 ** is incremented each time the wal file is restarted. */
4092 if( pHdr1->aSalt[0]<pHdr2->aSalt[0] ) return -1;
4093 if( pHdr1->aSalt[0]>pHdr2->aSalt[0] ) return +1;
4094 if( pHdr1->mxFrame<pHdr2->mxFrame ) return -1;
4095 if( pHdr1->mxFrame>pHdr2->mxFrame ) return +1;
4096 return 0;
4097}
4098
4099/*
4100** The caller currently has a read transaction open on the database.
4101** This function takes a SHARED lock on the CHECKPOINTER slot and then
4102** checks if the snapshot passed as the second argument is still
4103** available. If so, SQLITE_OK is returned.
4104**
4105** If the snapshot is not available, SQLITE_ERROR is returned. Or, if
4106** the CHECKPOINTER lock cannot be obtained, SQLITE_BUSY. If any error
4107** occurs (any value other than SQLITE_OK is returned), the CHECKPOINTER
4108** lock is released before returning.
4109*/
4110int sqlite3WalSnapshotCheck(Wal *pWal, sqlite3_snapshot *pSnapshot){
4111 int rc;
4112 rc = walLockShared(pWal, WAL_CKPT_LOCK);
4113 if( rc==SQLITE_OK ){
4114 WalIndexHdr *pNew = (WalIndexHdr*)pSnapshot;
4115 if( memcmp(pNew->aSalt, pWal->hdr.aSalt, sizeof(pWal->hdr.aSalt))
4116 || pNew->mxFrame<walCkptInfo(pWal)->nBackfillAttempted
4117 ){
4118 rc = SQLITE_ERROR_SNAPSHOT;
4119 walUnlockShared(pWal, WAL_CKPT_LOCK);
4120 }
4121 }
4122 return rc;
4123}
4124
4125/*
4126** Release a lock obtained by an earlier successful call to
4127** sqlite3WalSnapshotCheck().
4128*/
4129void sqlite3WalSnapshotUnlock(Wal *pWal){
4130 assert( pWal );
4131 walUnlockShared(pWal, WAL_CKPT_LOCK);
4132}
4133
4134
4135#endif /* SQLITE_ENABLE_SNAPSHOT */
4136
4137#ifdef SQLITE_ENABLE_ZIPVFS
4138/*
4139** If the argument is not NULL, it points to a Wal object that holds a
4140** read-lock. This function returns the database page-size if it is known,
4141** or zero if it is not (or if pWal is NULL).
4142*/
4143int sqlite3WalFramesize(Wal *pWal){
4144 assert( pWal==0 || pWal->readLock>=0 );
4145 return (pWal ? pWal->szPage : 0);
4146}
4147#endif
4148
4149/* Return the sqlite3_file object for the WAL file
4150*/
4151sqlite3_file *sqlite3WalFile(Wal *pWal){
4152 return pWal->pWalFd;
4153}
4154
4155#endif /* #ifndef SQLITE_OMIT_WAL */
4156