wasCSharpSQLite – Blame information for rev 1

Subversion Repositories:
Rev:
Rev Author Line No. Line
1 office 1 using System;
2 using System.Diagnostics;
3 using System.Text;
4  
5 using Bitmask = System.UInt64;
6 using u32 = System.UInt32;
7  
8 namespace Community.CsharpSqlite
9 {
10 public partial class Sqlite3
11 {
12 /*
13 ** 2010 February 1
14 **
15 ** The author disclaims copyright to this source code. In place of
16 ** a legal notice, here is a blessing:
17 **
18 ** May you do good and not evil.
19 ** May you find forgiveness for yourself and forgive others.
20 ** May you share freely, never taking more than you give.
21 **
22 *************************************************************************
23 **
24 ** This file contains the implementation of a write-ahead log (WAL) used in
25 ** "journal_mode=WAL" mode.
26 **
27 ** WRITE-AHEAD LOG (WAL) FILE FORMAT
28 **
29 ** A WAL file consists of a header followed by zero or more "frames".
30 ** Each frame records the revised content of a single page from the
31 ** database file. All changes to the database are recorded by writing
32 ** frames into the WAL. Transactions commit when a frame is written that
33 ** contains a commit marker. A single WAL can and usually does record
34 ** multiple transactions. Periodically, the content of the WAL is
35 ** transferred back into the database file in an operation called a
36 ** "checkpoint".
37 **
38 ** A single WAL file can be used multiple times. In other words, the
39 ** WAL can fill up with frames and then be checkpointed and then new
40 ** frames can overwrite the old ones. A WAL always grows from beginning
41 ** toward the end. Checksums and counters attached to each frame are
42 ** used to determine which frames within the WAL are valid and which
43 ** are leftovers from prior checkpoints.
44 **
45 ** The WAL header is 32 bytes in size and consists of the following eight
46 ** big-endian 32-bit unsigned integer values:
47 **
48 ** 0: Magic number. 0x377f0682 or 0x377f0683
49 ** 4: File format version. Currently 3007000
50 ** 8: Database page size. Example: 1024
51 ** 12: Checkpoint sequence number
52 ** 16: Salt-1, random integer incremented with each checkpoint
53 ** 20: Salt-2, a different random integer changing with each ckpt
54 ** 24: Checksum-1 (first part of checksum for first 24 bytes of header).
55 ** 28: Checksum-2 (second part of checksum for first 24 bytes of header).
56 **
57 ** Immediately following the wal-header are zero or more frames. Each
58 ** frame consists of a 24-byte frame-header followed by a <page-size> bytes
59 ** of page data. The frame-header is six big-endian 32-bit unsigned
60 ** integer values, as follows:
61 **
62 ** 0: Page number.
63 ** 4: For commit records, the size of the database image in pages
64 ** after the commit. For all other records, zero.
65 ** 8: Salt-1 (copied from the header)
66 ** 12: Salt-2 (copied from the header)
67 ** 16: Checksum-1.
68 ** 20: Checksum-2.
69 **
70 ** A frame is considered valid if and only if the following conditions are
71 ** true:
72 **
73 ** (1) The salt-1 and salt-2 values in the frame-header match
74 ** salt values in the wal-header
75 **
76 ** (2) The checksum values in the final 8 bytes of the frame-header
77 ** exactly match the checksum computed consecutively on the
78 ** WAL header and the first 8 bytes and the content of all frames
79 ** up to and including the current frame.
80 **
81 ** The checksum is computed using 32-bit big-endian integers if the
82 ** magic number in the first 4 bytes of the WAL is 0x377f0683 and it
83 ** is computed using little-endian if the magic number is 0x377f0682.
84 ** The checksum values are always stored in the frame header in a
85 ** big-endian format regardless of which byte order is used to compute
86 ** the checksum. The checksum is computed by interpreting the input as
87 ** an even number of unsigned 32-bit integers: x[0] through x[N]. The
88 ** algorithm used for the checksum is as follows:
89 **
90 ** for i from 0 to n-1 step 2:
91 ** s0 += x[i] + s1;
92 ** s1 += x[i+1] + s0;
93 ** endfor
94 **
95 ** Note that s0 and s1 are both weighted checksums using fibonacci weights
96 ** in reverse order (the largest fibonacci weight occurs on the first element
97 ** of the sequence being summed.) The s1 value spans all 32-bit
98 ** terms of the sequence whereas s0 omits the final term.
99 **
100 ** On a checkpoint, the WAL is first VFS.xSync-ed, then valid content of the
101 ** WAL is transferred into the database, then the database is VFS.xSync-ed.
102 ** The VFS.xSync operations serve as write barriers - all writes launched
103 ** before the xSync must complete before any write that launches after the
104 ** xSync begins.
105 **
106 ** After each checkpoint, the salt-1 value is incremented and the salt-2
107 ** value is randomized. This prevents old and new frames in the WAL from
108 ** being considered valid at the same time and being checkpointing together
109 ** following a crash.
110 **
111 ** READER ALGORITHM
112 **
113 ** To read a page from the database (call it page number P), a reader
114 ** first checks the WAL to see if it contains page P. If so, then the
115 ** last valid instance of page P that is a followed by a commit frame
116 ** or is a commit frame itself becomes the value read. If the WAL
117 ** contains no copies of page P that are valid and which are a commit
118 ** frame or are followed by a commit frame, then page P is read from
119 ** the database file.
120 **
121 ** To start a read transaction, the reader records the index of the last
122 ** valid frame in the WAL. The reader uses this recorded "mxFrame" value
123 ** for all subsequent read operations. New transactions can be appended
124 ** to the WAL, but as long as the reader uses its original mxFrame value
125 ** and ignores the newly appended content, it will see a consistent snapshot
126 ** of the database from a single point in time. This technique allows
127 ** multiple concurrent readers to view different versions of the database
128 ** content simultaneously.
129 **
130 ** The reader algorithm in the previous paragraphs works correctly, but
131 ** because frames for page P can appear anywhere within the WAL, the
132 ** reader has to scan the entire WAL looking for page P frames. If the
133 ** WAL is large (multiple megabytes is typical) that scan can be slow,
134 ** and read performance suffers. To overcome this problem, a separate
135 ** data structure called the wal-index is maintained to expedite the
136 ** search for frames of a particular page.
137 **
138 ** WAL-INDEX FORMAT
139 **
140 ** Conceptually, the wal-index is shared memory, though VFS implementations
141 ** might choose to implement the wal-index using a mmapped file. Because
142 ** the wal-index is shared memory, SQLite does not support journal_mode=WAL
143 ** on a network filesystem. All users of the database must be able to
144 ** share memory.
145 **
146 ** The wal-index is transient. After a crash, the wal-index can (and should
147 ** be) reconstructed from the original WAL file. In fact, the VFS is required
148 ** to either truncate or zero the header of the wal-index when the last
149 ** connection to it closes. Because the wal-index is transient, it can
150 ** use an architecture-specific format; it does not have to be cross-platform.
151 ** Hence, unlike the database and WAL file formats which store all values
152 ** as big endian, the wal-index can store multi-byte values in the native
153 ** byte order of the host computer.
154 **
155 ** The purpose of the wal-index is to answer this question quickly: Given
156 ** a page number P, return the index of the last frame for page P in the WAL,
157 ** or return NULL if there are no frames for page P in the WAL.
158 **
159 ** The wal-index consists of a header region, followed by an one or
160 ** more index blocks.
161 **
162 ** The wal-index header contains the total number of frames within the WAL
163 ** in the the mxFrame field.
164 **
165 ** Each index block except for the first contains information on
166 ** HASHTABLE_NPAGE frames. The first index block contains information on
167 ** HASHTABLE_NPAGE_ONE frames. The values of HASHTABLE_NPAGE_ONE and
168 ** HASHTABLE_NPAGE are selected so that together the wal-index header and
169 ** first index block are the same size as all other index blocks in the
170 ** wal-index.
171 **
172 ** Each index block contains two sections, a page-mapping that contains the
173 ** database page number associated with each wal frame, and a hash-table
174 ** that allows readers to query an index block for a specific page number.
175 ** The page-mapping is an array of HASHTABLE_NPAGE (or HASHTABLE_NPAGE_ONE
176 ** for the first index block) 32-bit page numbers. The first entry in the
177 ** first index-block contains the database page number corresponding to the
178 ** first frame in the WAL file. The first entry in the second index block
179 ** in the WAL file corresponds to the (HASHTABLE_NPAGE_ONE+1)th frame in
180 ** the log, and so on.
181 **
182 ** The last index block in a wal-index usually contains less than the full
183 ** complement of HASHTABLE_NPAGE (or HASHTABLE_NPAGE_ONE) page-numbers,
184 ** depending on the contents of the WAL file. This does not change the
185 ** allocated size of the page-mapping array - the page-mapping array merely
186 ** contains unused entries.
187 **
188 ** Even without using the hash table, the last frame for page P
189 ** can be found by scanning the page-mapping sections of each index block
190 ** starting with the last index block and moving toward the first, and
191 ** within each index block, starting at the end and moving toward the
192 ** beginning. The first entry that equals P corresponds to the frame
193 ** holding the content for that page.
194 **
195 ** The hash table consists of HASHTABLE_NSLOT 16-bit unsigned integers.
196 ** HASHTABLE_NSLOT = 2*HASHTABLE_NPAGE, and there is one entry in the
197 ** hash table for each page number in the mapping section, so the hash
198 ** table is never more than half full. The expected number of collisions
199 ** prior to finding a match is 1. Each entry of the hash table is an
200 ** 1-based index of an entry in the mapping section of the same
201 ** index block. Let K be the 1-based index of the largest entry in
202 ** the mapping section. (For index blocks other than the last, K will
203 ** always be exactly HASHTABLE_NPAGE (4096) and for the last index block
204 ** K will be (mxFrame%HASHTABLE_NPAGE).) Unused slots of the hash table
205 ** contain a value of 0.
206 **
207 ** To look for page P in the hash table, first compute a hash iKey on
208 ** P as follows:
209 **
210 ** iKey = (P * 383) % HASHTABLE_NSLOT
211 **
212 ** Then start scanning entries of the hash table, starting with iKey
213 ** (wrapping around to the beginning when the end of the hash table is
214 ** reached) until an unused hash slot is found. Let the first unused slot
215 ** be at index iUnused. (iUnused might be less than iKey if there was
216 ** wrap-around.) Because the hash table is never more than half full,
217 ** the search is guaranteed to eventually hit an unused entry. Let
218 ** iMax be the value between iKey and iUnused, closest to iUnused,
219 ** where aHash[iMax]==P. If there is no iMax entry (if there exists
220 ** no hash slot such that aHash[i]==p) then page P is not in the
221 ** current index block. Otherwise the iMax-th mapping entry of the
222 ** current index block corresponds to the last entry that references
223 ** page P.
224 **
225 ** A hash search begins with the last index block and moves toward the
226 ** first index block, looking for entries corresponding to page P. On
227 ** average, only two or three slots in each index block need to be
228 ** examined in order to either find the last entry for page P, or to
229 ** establish that no such entry exists in the block. Each index block
230 ** holds over 4000 entries. So two or three index blocks are sufficient
231 ** to cover a typical 10 megabyte WAL file, assuming 1K pages. 8 or 10
232 ** comparisons (on average) suffice to either locate a frame in the
233 ** WAL or to establish that the frame does not exist in the WAL. This
234 ** is much faster than scanning the entire 10MB WAL.
235 **
236 ** Note that entries are added in order of increasing K. Hence, one
237 ** reader might be using some value K0 and a second reader that started
238 ** at a later time (after additional transactions were added to the WAL
239 ** and to the wal-index) might be using a different value K1, where K1>K0.
240 ** Both readers can use the same hash table and mapping section to get
241 ** the correct result. There may be entries in the hash table with
242 ** K>K0 but to the first reader, those entries will appear to be unused
243 ** slots in the hash table and so the first reader will get an answer as
244 ** if no values greater than K0 had ever been inserted into the hash table
245 ** in the first place - which is what reader one wants. Meanwhile, the
246 ** second reader using K1 will see additional values that were inserted
247 ** later, which is exactly what reader two wants.
248 **
249 ** When a rollback occurs, the value of K is decreased. Hash table entries
250 ** that correspond to frames greater than the new K value are removed
251 ** from the hash table at this point.
252 *************************************************************************
253 ** Included in SQLite3 port to C#-SQLite; 2008 Noah B Hart
254 ** C#-SQLite is an independent reimplementation of the SQLite software library
255 **
256 ** SQLITE_SOURCE_ID: 2011-06-23 19:49:22 4374b7e83ea0a3fbc3691f9c0c936272862f32f2
257 **
258 *************************************************************************
259 */
260 #if !SQLITE_OMIT_WAL
261  
262 //#include "wal.h"
263  
264 /*
265 ** Trace output macros
266 */
267 #if (SQLITE_TEST) && (SQLITE_DEBUG)
268 int sqlite3WalTrace = 0;
269 //# define WALTRACE(X) if(sqlite3WalTrace) sqlite3DebugPrintf X
270 #else
271 //# define WALTRACE(X)
272 #endif
273  
274 /*
275 ** The maximum (and only) versions of the wal and wal-index formats
276 ** that may be interpreted by this version of SQLite.
277 **
278 ** If a client begins recovering a WAL file and finds that (a) the checksum
279 ** values in the wal-header are correct and (b) the version field is not
280 ** WAL_MAX_VERSION, recovery fails and SQLite returns SQLITE_CANTOPEN.
281 **
282 ** Similarly, if a client successfully reads a wal-index header (i.e. the
283 ** checksum test is successful) and finds that the version field is not
284 ** WALINDEX_MAX_VERSION, then no read-transaction is opened and SQLite
285 ** returns SQLITE_CANTOPEN.
286 */
287 ////#define WAL_MAX_VERSION 3007000
288 ////#define WALINDEX_MAX_VERSION 3007000
289  
290 /*
291 ** Indices of various locking bytes. WAL_NREADER is the number
292 ** of available reader locks and should be at least 3.
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 */
303 typedef struct WalIndexHdr WalIndexHdr;
304 typedef struct WalIterator WalIterator;
305 typedef 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.
313 **
314 ** The szPage value can be any power of 2 between 512 and 32768, inclusive.
315 ** Or it can be 1 to represent a 65536-byte page. The latter case was
316 ** added in 3.7.1 when support for 64K pages was added.
317 */
318 struct WalIndexHdr {
319 u32 iVersion; /* Wal-index version */
320 u32 unused; /* Unused (padding) field */
321 u32 iChange; /* Counter incremented each transaction */
322 u8 isInit; /* 1 when initialized */
323 u8 bigEndCksum; /* True if checksums in WAL are big-endian */
324 u16 szPage; /* Database page size in bytes. 1==64K */
325 u32 mxFrame; /* Index of last valid frame in the WAL */
326 u32 nPage; /* Size of database in pages */
327 u32 aFrameCksum[2]; /* Checksum of last frame in log */
328 u32 aSalt[2]; /* Two salt values copied from WAL header */
329 u32 aCksum[2]; /* Checksum over all prior fields */
330 };
331  
332 /*
333 ** A copy of the following object occurs in the wal-index immediately
334 ** following the second copy of the WalIndexHdr. This object stores
335 ** information used by checkpoint.
336 **
337 ** nBackfill is the number of frames in the WAL that have been written
338 ** back into the database. (We call the act of moving content from WAL to
339 ** database "backfilling".) The nBackfill number is never greater than
340 ** WalIndexHdr.mxFrame. nBackfill can only be increased by threads
341 ** holding the WAL_CKPT_LOCK lock (which includes a recovery thread).
342 ** However, a WAL_WRITE_LOCK thread can move the value of nBackfill from
343 ** mxFrame back to zero when the WAL is reset.
344 **
345 ** There is one entry in aReadMark[] for each reader lock. If a reader
346 ** holds read-lock K, then the value in aReadMark[K] is no greater than
347 ** the mxFrame for that reader. The value READMARK_NOT_USED (0xffffffff)
348 ** for any aReadMark[] means that entry is unused. aReadMark[0] is
349 ** a special case; its value is never used and it exists as a place-holder
350 ** to avoid having to offset aReadMark[] indexs by one. Readers holding
351 ** WAL_READ_LOCK(0) always ignore the entire WAL and read all content
352 ** directly from the database.
353 **
354 ** The value of aReadMark[K] may only be changed by a thread that
355 ** is holding an exclusive lock on WAL_READ_LOCK(K). Thus, the value of
356 ** aReadMark[K] cannot changed while there is a reader is using that mark
357 ** since the reader will be holding a shared lock on WAL_READ_LOCK(K).
358 **
359 ** The checkpointer may only transfer frames from WAL to database where
360 ** the frame numbers are less than or equal to every aReadMark[] that is
361 ** in use (that is, every aReadMark[j] for which there is a corresponding
362 ** WAL_READ_LOCK(j)). New readers (usually) pick the aReadMark[] with the
363 ** largest value and will increase an unused aReadMark[] to mxFrame if there
364 ** is not already an aReadMark[] equal to mxFrame. The exception to the
365 ** previous sentence is when nBackfill equals mxFrame (meaning that everything
366 ** in the WAL has been backfilled into the database) then new readers
367 ** will choose aReadMark[0] which has value 0 and hence such reader will
368 ** get all their all content directly from the database file and ignore
369 ** the WAL.
370 **
371 ** Writers normally append new frames to the end of the WAL. However,
372 ** if nBackfill equals mxFrame (meaning that all WAL content has been
373 ** written back into the database) and if no readers are using the WAL
374 ** (in other words, if there are no WAL_READ_LOCK(i) where i>0) then
375 ** the writer will first "reset" the WAL back to the beginning and start
376 ** writing new content beginning at frame 1.
377 **
378 ** We assume that 32-bit loads are atomic and so no locks are needed in
379 ** order to read from any aReadMark[] entries.
380 */
381 struct WalCkptInfo {
382 u32 nBackfill; /* Number of WAL frames backfilled into DB */
383 u32 aReadMark[WAL_NREADER]; /* Reader marks */
384 };
385 ////#define READMARK_NOT_USED 0xffffffff
386  
387  
388 /* A block of WALINDEX_LOCK_RESERVED bytes beginning at
389 ** WALINDEX_LOCK_OFFSET is reserved for locks. Since some systems
390 ** only support mandatory file-locks, we do not read or write data
391 ** from the region of the file on which locks are applied.
392 */
393 ////#define WALINDEX_LOCK_OFFSET (sizeof(WalIndexHdr)*2 + sizeof(WalCkptInfo))
394 ////#define WALINDEX_LOCK_RESERVED 16
395 ////#define WALINDEX_HDR_SIZE (WALINDEX_LOCK_OFFSET+WALINDEX_LOCK_RESERVED)
396  
397 /* Size of header before each frame in wal */
398 ////#define WAL_FRAME_HDRSIZE 24
399  
400 /* Size of write ahead log header, including checksum. */
401 /* ////#define WAL_HDRSIZE 24 */
402 ////#define WAL_HDRSIZE 32
403  
404 /* WAL magic value. Either this value, or the same value with the least
405 ** significant bit also set (WAL_MAGIC | 0x00000001) is stored in 32-bit
406 ** big-endian format in the first 4 bytes of a WAL file.
407 **
408 ** If the LSB is set, then the checksums for each frame within the WAL
409 ** file are calculated by treating all data as an array of 32-bit
410 ** big-endian words. Otherwise, they are calculated by interpreting
411 ** all data as 32-bit little-endian words.
412 */
413 ////#define WAL_MAGIC 0x377f0682
414  
415 /*
416 ** Return the offset of frame iFrame in the write-ahead log file,
417 ** assuming a database page size of szPage bytes. The offset returned
418 ** is to the start of the write-ahead log frame-header.
419 */
420 ////#define walFrameOffset(iFrame, szPage) ( \
421 WAL_HDRSIZE + ((iFrame)-1)*(i64)((szPage)+WAL_FRAME_HDRSIZE) \
422 )
423  
424 /*
425 ** An open write-ahead log file is represented by an instance of the
426 ** following object.
427 */
428 struct Wal {
429 sqlite3_vfs *pVfs; /* The VFS used to create pDbFd */
430 sqlite3_file *pDbFd; /* File handle for the database file */
431 sqlite3_file *pWalFd; /* File handle for WAL file */
432 u32 iCallback; /* Value to pass to log callback (or 0) */
433 i64 mxWalSize; /* Truncate WAL to this size upon reset */
434 int nWiData; /* Size of array apWiData */
435 volatile u32 **apWiData; /* Pointer to wal-index content in memory */
436 u32 szPage; /* Database page size */
437 i16 readLock; /* Which read lock is being held. -1 for none */
438 u8 exclusiveMode; /* Non-zero if connection is in exclusive mode */
439 u8 writeLock; /* True if in a write transaction */
440 u8 ckptLock; /* True if holding a checkpoint lock */
441 u8 readOnly; /* WAL_RDWR, WAL_RDONLY, or WAL_SHM_RDONLY */
442 WalIndexHdr hdr; /* Wal-index header for current transaction */
443 string zWalName; /* Name of WAL file */
444 u32 nCkpt; /* Checkpoint sequence counter in the wal-header */
445 #if SQLITE_DEBUG
446 u8 lockError; /* True if a locking error has occurred */
447 #endif
448 };
449  
450 /*
451 ** Candidate values for Wal.exclusiveMode.
452 */
453 //#define WAL_NORMAL_MODE 0
454 //#define WAL_EXCLUSIVE_MODE 1
455 //#define WAL_HEAPMEMORY_MODE 2
456  
457 /*
458 ** Possible values for WAL.readOnly
459 */
460 //#define WAL_RDWR 0 /* Normal read/write connection */
461 //#define WAL_RDONLY 1 /* The WAL file is readonly */
462 //#define WAL_SHM_RDONLY 2 /* The SHM file is readonly */
463  
464 /*
465 ** Each page of the wal-index mapping contains a hash-table made up of
466 ** an array of HASHTABLE_NSLOT elements of the following type.
467 */
468 typedef u16 ht_slot;
469  
470 /*
471 ** This structure is used to implement an iterator that loops through
472 ** all frames in the WAL in database page order. Where two or more frames
473 ** correspond to the same database page, the iterator visits only the
474 ** frame most recently written to the WAL (in other words, the frame with
475 ** the largest index).
476 **
477 ** The internals of this structure are only accessed by:
478 **
479 ** walIteratorInit() - Create a new iterator,
480 ** walIteratorNext() - Step an iterator,
481 ** walIteratorFree() - Free an iterator.
482 **
483 ** This functionality is used by the checkpoint code (see walCheckpoint()).
484 */
485 struct WalIterator {
486 int iPrior; /* Last result returned from the iterator */
487 int nSegment; /* Number of entries in aSegment[] */
488 struct WalSegment {
489 int iNext; /* Next slot in aIndex[] not yet returned */
490 ht_slot *aIndex; /* i0, i1, i2... such that aPgno[iN] ascend */
491 u32 *aPgno; /* Array of page numbers. */
492 int nEntry; /* Nr. of entries in aPgno[] and aIndex[] */
493 int iZero; /* Frame number associated with aPgno[0] */
494 } aSegment[1]; /* One for every 32KB page in the wal-index */
495 };
496  
497 /*
498 ** Define the parameters of the hash tables in the wal-index file. There
499 ** is a hash-table following every HASHTABLE_NPAGE page numbers in the
500 ** wal-index.
501 **
502 ** Changing any of these constants will alter the wal-index format and
503 ** create incompatibilities.
504 */
505 //#define HASHTABLE_NPAGE 4096 /* Must be power of 2 */
506 //#define HASHTABLE_HASH_1 383 /* Should be prime */
507 //#define HASHTABLE_NSLOT (HASHTABLE_NPAGE*2) /* Must be a power of 2 */
508  
509 /*
510 ** The block of page numbers associated with the first hash-table in a
511 ** wal-index is smaller than usual. This is so that there is a complete
512 ** hash-table on each aligned 32KB page of the wal-index.
513 */
514 //#define HASHTABLE_NPAGE_ONE (HASHTABLE_NPAGE - (WALINDEX_HDR_SIZE/sizeof(u32)))
515  
516 /* The wal-index is divided into pages of WALINDEX_PGSZ bytes each. */
517 //#define WALINDEX_PGSZ ( \
518 sizeof(ht_slot)*HASHTABLE_NSLOT + HASHTABLE_NPAGE*sizeof(u32) \
519 )
520  
521 /*
522 ** Obtain a pointer to the iPage'th page of the wal-index. The wal-index
523 ** is broken into pages of WALINDEX_PGSZ bytes. Wal-index pages are
524 ** numbered from zero.
525 **
526 ** If this call is successful, *ppPage is set to point to the wal-index
527 ** page and SQLITE_OK is returned. If an error (an OOM or VFS error) occurs,
528 ** then an SQLite error code is returned and *ppPage is set to 0.
529 */
530 static int walIndexPage(Wal *pWal, int iPage, volatile u32 **ppPage){
531 int rc = SQLITE_OK;
532  
533 /* Enlarge the pWal->apWiData[] array if required */
534 if( pWal->nWiData<=iPage ){
535 int nByte = sizeof(u32)*(iPage+1);
536 volatile u32 **apNew;
537 apNew = (volatile u32 *)sqlite3_realloc((void )pWal->apWiData, nByte);
538 if( null==apNew ){
539 *ppPage = 0;
540 return SQLITE_NOMEM;
541 }
542 memset((void)&apNew[pWal->nWiData], 0,
543 sizeof(u32)*(iPage+1-pWal->nWiData));
544 pWal->apWiData = apNew;
545 pWal->nWiData = iPage+1;
546 }
547  
548 /* Request a pointer to the required page from the VFS */
549 if( pWal->apWiData[iPage]==0 ){
550 if( pWal->exclusiveMode==WAL_HEAPMEMORY_MODE ){
551 pWal->apWiData[iPage] = (u32 volatile )sqlite3MallocZero(WALINDEX_PGSZ);
552 if( null==pWal->apWiData[iPage] ) rc = SQLITE_NOMEM;
553 }else{
554 rc = sqlite3OsShmMap(pWal->pDbFd, iPage, WALINDEX_PGSZ,
555 pWal->writeLock, (void volatile *)&pWal->apWiData[iPage]
556 );
557 if( rc==SQLITE_READONLY ){
558 pWal->readOnly |= WAL_SHM_RDONLY;
559 rc = SQLITE_OK;
560 }
561 }
562 }
563  
564 *ppPage = pWal->apWiData[iPage];
565 Debug.Assert( iPage==0 || *ppPage || rc!=SQLITE_OK );
566 return rc;
567 }
568  
569 /*
570 ** Return a pointer to the WalCkptInfo structure in the wal-index.
571 */
572 static volatile WalCkptInfo *walCkptInfo(Wal *pWal){
573 Debug.Assert( pWal->nWiData>0 && pWal->apWiData[0] );
574 return (volatile WalCkptInfo)&(pWal->apWiData[0][sizeof(WalIndexHdr)/2]);
575 }
576  
577 /*
578 ** Return a pointer to the WalIndexHdr structure in the wal-index.
579 */
580 static volatile WalIndexHdr *walIndexHdr(Wal *pWal){
581 Debug.Assert( pWal->nWiData>0 && pWal->apWiData[0] );
582 return (volatile WalIndexHdr)pWal->apWiData[0];
583 }
584  
585 /*
586 ** The argument to this macro must be of type u32. On a little-endian
587 ** architecture, it returns the u32 value that results from interpreting
588 ** the 4 bytes as a big-endian value. On a big-endian architecture, it
589 ** returns the value that would be produced by intepreting the 4 bytes
590 ** of the input value as a little-endian integer.
591 */
592 //#define BYTESWAP32(x) ( \
593 (((x)&0x000000FF)<<24) + (((x)&0x0000FF00)<<8) \
594 + (((x)&0x00FF0000)>>8) + (((x)&0xFF000000)>>24) \
595 )
596  
597 /*
598 ** Generate or extend an 8 byte checksum based on the data in
599 ** array aByte[] and the initial values of aIn[0] and aIn[1] (or
600 ** initial values of 0 and 0 if aIn==NULL).
601 **
602 ** The checksum is written back into aOut[] before returning.
603 **
604 ** nByte must be a positive multiple of 8.
605 */
606 static void walChecksumBytes(
607 int nativeCksum, /* True for native byte-order, false for non-native */
608 u8 *a, /* Content to be checksummed */
609 int nByte, /* Bytes of content in a[]. Must be a multiple of 8. */
610 const u32 *aIn, /* Initial checksum value input */
611 u32 *aout /* OUT: Final checksum value output */
612 ){
613 u32 s1, s2;
614 u32 *aData = (u32 )a;
615 u32 *aEnd = (u32 )&a[nByte];
616  
617 if( aIn ){
618 s1 = aIn[0];
619 s2 = aIn[1];
620 }else{
621 s1 = s2 = 0;
622 }
623  
624 Debug.Assert( nByte>=8 );
625 Debug.Assert( (nByte&0x00000007)==0 );
626  
627 if( nativeCksum ){
628 do {
629 s1 += *aData++ + s2;
630 s2 += *aData++ + s1;
631 }while( aData<aEnd );
632 }else{
633 do {
634 s1 += BYTESWAP32(aData[0]) + s2;
635 s2 += BYTESWAP32(aData[1]) + s1;
636 aData += 2;
637 }while( aData<aEnd );
638 }
639  
640 aOut[0] = s1;
641 aOut[1] = s2;
642 }
643  
644 static void walShmBarrier(Wal *pWal){
645 if( pWal->exclusiveMode!=WAL_HEAPMEMORY_MODE ){
646 sqlite3OsShmBarrier(pWal->pDbFd);
647 }
648 }
649  
650 /*
651 ** Write the header information in pWal->hdr into the wal-index.
652 **
653 ** The checksum on pWal->hdr is updated before it is written.
654 */
655 static void walIndexWriteHdr(Wal *pWal){
656 volatile WalIndexHdr *aHdr = walIndexHdr(pWal);
657 const int nCksum = offsetof(WalIndexHdr, aCksum);
658  
659 Debug.Assert( pWal->writeLock );
660 pWal->hdr.isInit = 1;
661 pWal->hdr.iVersion = WALINDEX_MAX_VERSION;
662 walChecksumBytes(1, (u8)&pWal->hdr, nCksum, 0, pWal->hdr.aCksum);
663 memcpy((void )&aHdr[1], (void )&pWal->hdr, sizeof(WalIndexHdr));
664 walShmBarrier(pWal);
665 memcpy((void )&aHdr[0], (void )&pWal->hdr, sizeof(WalIndexHdr));
666 }
667  
668 /*
669 ** This function encodes a single frame header and writes it to a buffer
670 ** supplied by the caller. A frame-header is made up of a series of
671 ** 4-byte big-endian integers, as follows:
672 **
673 ** 0: Page number.
674 ** 4: For commit records, the size of the database image in pages
675 ** after the commit. For all other records, zero.
676 ** 8: Salt-1 (copied from the wal-header)
677 ** 12: Salt-2 (copied from the wal-header)
678 ** 16: Checksum-1.
679 ** 20: Checksum-2.
680 */
681 static void walEncodeFrame(
682 Wal *pWal, /* The write-ahead log */
683 u32 iPage, /* Database page number for frame */
684 u32 nTruncate, /* New db size (or 0 for non-commit frames) */
685 u8 *aData, /* Pointer to page data */
686 u8 *aFrame /* OUT: Write encoded frame here */
687 ){
688 int nativeCksum; /* True for native byte-order checksums */
689 u32 *aCksum = pWal->hdr.aFrameCksum;
690 Debug.Assert( WAL_FRAME_HDRSIZE==24 );
691 sqlite3Put4byte(&aFrame[0], iPage);
692 sqlite3Put4byte(&aFrame[4], nTruncate);
693 memcpy(&aFrame[8], pWal->hdr.aSalt, 8);
694  
695 nativeCksum = (pWal->hdr.bigEndCksum==SQLITE_BIGENDIAN);
696 walChecksumBytes(nativeCksum, aFrame, 8, aCksum, aCksum);
697 walChecksumBytes(nativeCksum, aData, pWal->szPage, aCksum, aCksum);
698  
699 sqlite3Put4byte(&aFrame[16], aCksum[0]);
700 sqlite3Put4byte(&aFrame[20], aCksum[1]);
701 }
702  
703 /*
704 ** Check to see if the frame with header in aFrame[] and content
705 ** in aData[] is valid. If it is a valid frame, fill *piPage and
706 ** *pnTruncate and return true. Return if the frame is not valid.
707 */
708 static int walDecodeFrame(
709 Wal *pWal, /* The write-ahead log */
710 u32 *piPage, /* OUT: Database page number for frame */
711 u32 *pnTruncate, /* OUT: New db size (or 0 if not commit) */
712 u8 *aData, /* Pointer to page data (for checksum) */
713 u8 *aFrame /* Frame data */
714 ){
715 int nativeCksum; /* True for native byte-order checksums */
716 u32 *aCksum = pWal->hdr.aFrameCksum;
717 u32 pgno; /* Page number of the frame */
718 Debug.Assert( WAL_FRAME_HDRSIZE==24 );
719  
720 /* A frame is only valid if the salt values in the frame-header
721 ** match the salt values in the wal-header.
722 */
723 if( memcmp(&pWal->hdr.aSalt, &aFrame[8], 8)!=0 ){
724 return 0;
725 }
726  
727 /* A frame is only valid if the page number is creater than zero.
728 */
729 pgno = sqlite3Get4byte(&aFrame[0]);
730 if( pgno==0 ){
731 return 0;
732 }
733  
734 /* A frame is only valid if a checksum of the WAL header,
735 ** all prior frams, the first 16 bytes of this frame-header,
736 ** and the frame-data matches the checksum in the last 8
737 ** bytes of this frame-header.
738 */
739 nativeCksum = (pWal->hdr.bigEndCksum==SQLITE_BIGENDIAN);
740 walChecksumBytes(nativeCksum, aFrame, 8, aCksum, aCksum);
741 walChecksumBytes(nativeCksum, aData, pWal->szPage, aCksum, aCksum);
742 if( aCksum[0]!=sqlite3Get4byte(&aFrame[16])
743 || aCksum[1]!=sqlite3Get4byte(&aFrame[20])
744 ){
745 /* Checksum failed. */
746 return 0;
747 }
748  
749 /* If we reach this point, the frame is valid. Return the page number
750 ** and the new database size.
751 */
752 *piPage = pgno;
753 *pnTruncate = sqlite3Get4byte(&aFrame[4]);
754 return 1;
755 }
756  
757  
758 #if (SQLITE_TEST) && (SQLITE_DEBUG)
759 /*
760 ** Names of locks. This routine is used to provide debugging output and is not
761 ** a part of an ordinary build.
762 */
763 static string walLockName(int lockIdx){
764 if( lockIdx==WAL_WRITE_LOCK ){
765 return "WRITE-LOCK";
766 }else if( lockIdx==WAL_CKPT_LOCK ){
767 return "CKPT-LOCK";
768 }else if( lockIdx==WAL_RECOVER_LOCK ){
769 return "RECOVER-LOCK";
770 }else{
771 static char zName[15];
772 sqlite3_snprintf(sizeof(zName), zName, "READ-LOCK[%d]",
773 lockIdx-WAL_READ_LOCK(0));
774 return zName;
775 }
776 }
777 #endif //*defined(SQLITE_TEST) || defined(SQLITE_DEBUG) */
778  
779  
780 /*
781 ** Set or release locks on the WAL. Locks are either shared or exclusive.
782 ** A lock cannot be moved directly between shared and exclusive - it must go
783 ** through the unlocked state first.
784 **
785 ** In locking_mode=EXCLUSIVE, all of these routines become no-ops.
786 */
787 static int walLockShared(Wal *pWal, int lockIdx){
788 int rc;
789 if( pWal->exclusiveMode ) return SQLITE_OK;
790 rc = sqlite3OsShmLock(pWal->pDbFd, lockIdx, 1,
791 SQLITE_SHM_LOCK | SQLITE_SHM_SHARED);
792 WALTRACE(("WAL%p: acquire SHARED-%s %s\n", pWal,
793 walLockName(lockIdx), rc ? "failed" : "ok"));
794 VVA_ONLY( pWal->lockError = (u8)(rc!=SQLITE_OK && rc!=SQLITE_BUSY); )
795 return rc;
796 }
797 static void walUnlockShared(Wal *pWal, int lockIdx){
798 if( pWal->exclusiveMode ) return;
799 (void)sqlite3OsShmLock(pWal->pDbFd, lockIdx, 1,
800 SQLITE_SHM_UNLOCK | SQLITE_SHM_SHARED);
801 WALTRACE(("WAL%p: release SHARED-%s\n", pWal, walLockName(lockIdx)));
802 }
803 static int walLockExclusive(Wal *pWal, int lockIdx, int n){
804 int rc;
805 if( pWal->exclusiveMode ) return SQLITE_OK;
806 rc = sqlite3OsShmLock(pWal->pDbFd, lockIdx, n,
807 SQLITE_SHM_LOCK | SQLITE_SHM_EXCLUSIVE);
808 WALTRACE(("WAL%p: acquire EXCLUSIVE-%s cnt=%d %s\n", pWal,
809 walLockName(lockIdx), n, rc ? "failed" : "ok"));
810 VVA_ONLY( pWal->lockError = (u8)(rc!=SQLITE_OK && rc!=SQLITE_BUSY); )
811 return rc;
812 }
813 static void walUnlockExclusive(Wal *pWal, int lockIdx, int n){
814 if( pWal->exclusiveMode ) return;
815 (void)sqlite3OsShmLock(pWal->pDbFd, lockIdx, n,
816 SQLITE_SHM_UNLOCK | SQLITE_SHM_EXCLUSIVE);
817 WALTRACE(("WAL%p: release EXCLUSIVE-%s cnt=%d\n", pWal,
818 walLockName(lockIdx), n));
819 }
820  
821 /*
822 ** Compute a hash on a page number. The resulting hash value must land
823 ** between 0 and (HASHTABLE_NSLOT-1). The walHashNext() function advances
824 ** the hash to the next value in the event of a collision.
825 */
826 static int walHash(u32 iPage){
827 Debug.Assert( iPage>0 );
828 Debug.Assert( (HASHTABLE_NSLOT & (HASHTABLE_NSLOT-1))==0 );
829 return (iPage*HASHTABLE_HASH_1) & (HASHTABLE_NSLOT-1);
830 }
831 static int walNextHash(int iPriorHash){
832 return (iPriorHash+1)&(HASHTABLE_NSLOT-1);
833 }
834  
835 /*
836 ** Return pointers to the hash table and page number array stored on
837 ** page iHash of the wal-index. The wal-index is broken into 32KB pages
838 ** numbered starting from 0.
839 **
840 ** Set output variable *paHash to point to the start of the hash table
841 ** in the wal-index file. Set *piZero to one less than the frame
842 ** number of the first frame indexed by this hash table. If a
843 ** slot in the hash table is set to N, it refers to frame number
844 ** (*piZero+N) in the log.
845 **
846 ** Finally, set *paPgno so that *paPgno[1] is the page number of the
847 ** first frame indexed by the hash table, frame (*piZero+1).
848 */
849 static int walHashGet(
850 Wal *pWal, /* WAL handle */
851 int iHash, /* Find the iHash'th table */
852 volatile ht_slot **paHash, /* OUT: Pointer to hash index */
853 volatile u32 **paPgno, /* OUT: Pointer to page number array */
854 u32 *piZero /* OUT: Frame associated with *paPgno[0] */
855 ){
856 int rc; /* Return code */
857 volatile u32 *aPgno;
858  
859 rc = walIndexPage(pWal, iHash, &aPgno);
860 Debug.Assert( rc==SQLITE_OK || iHash>0 );
861  
862 if( rc==SQLITE_OK ){
863 u32 iZero;
864 volatile ht_slot *aHash;
865  
866 aHash = (volatile ht_slot )&aPgno[HASHTABLE_NPAGE];
867 if( iHash==0 ){
868 aPgno = aPgno[WALINDEX_HDR_SIZE/sizeof(u32)];
869 iZero = 0;
870 }else{
871 iZero = HASHTABLE_NPAGE_ONE + (iHash-1)*HASHTABLE_NPAGE;
872 }
873  
874 *paPgno = aPgno[-1];
875 *paHash = aHash;
876 *piZero = iZero;
877 }
878 return rc;
879 }
880  
881 /*
882 ** Return the number of the wal-index page that contains the hash-table
883 ** and page-number array that contain entries corresponding to WAL frame
884 ** iFrame. The wal-index is broken up into 32KB pages. Wal-index pages
885 ** are numbered starting from 0.
886 */
887 static int walFramePage(u32 iFrame){
888 int iHash = (iFrame+HASHTABLE_NPAGE-HASHTABLE_NPAGE_ONE-1) / HASHTABLE_NPAGE;
889 Debug.Assert( (iHash==0 || iFrame>HASHTABLE_NPAGE_ONE)
890 && (iHash>=1 || iFrame<=HASHTABLE_NPAGE_ONE)
891 && (iHash<=1 || iFrame>(HASHTABLE_NPAGE_ONE+HASHTABLE_NPAGE))
892 && (iHash>=2 || iFrame<=HASHTABLE_NPAGE_ONE+HASHTABLE_NPAGE)
893 && (iHash<=2 || iFrame>(HASHTABLE_NPAGE_ONE+2*HASHTABLE_NPAGE))
894 );
895 return iHash;
896 }
897  
898 /*
899 ** Return the page number associated with frame iFrame in this WAL.
900 */
901 static u32 walFramePgno(Wal *pWal, u32 iFrame){
902 int iHash = walFramePage(iFrame);
903 if( iHash==0 ){
904 return pWal->apWiData[0][WALINDEX_HDR_SIZE/sizeof(u32) + iFrame - 1];
905 }
906 return pWal->apWiData[iHash][(iFrame-1-HASHTABLE_NPAGE_ONE)%HASHTABLE_NPAGE];
907 }
908  
909 /*
910 ** Remove entries from the hash table that point to WAL slots greater
911 ** than pWal->hdr.mxFrame.
912 **
913 ** This function is called whenever pWal->hdr.mxFrame is decreased due
914 ** to a rollback or savepoint.
915 **
916 ** At most only the hash table containing pWal->hdr.mxFrame needs to be
917 ** updated. Any later hash tables will be automatically cleared when
918 ** pWal->hdr.mxFrame advances to the point where those hash tables are
919 ** actually needed.
920 */
921 static void walCleanupHash(Wal *pWal){
922 volatile ht_slot *aHash = 0; /* Pointer to hash table to clear */
923 volatile u32 *aPgno = 0; /* Page number array for hash table */
924 u32 iZero = 0; /* frame == (aHash[x]+iZero) */
925 int iLimit = 0; /* Zero values greater than this */
926 int nByte; /* Number of bytes to zero in aPgno[] */
927 int i; /* Used to iterate through aHash[] */
928  
929 Debug.Assert( pWal->writeLock );
930 testcase( pWal->hdr.mxFrame==HASHTABLE_NPAGE_ONE-1 );
931 testcase( pWal->hdr.mxFrame==HASHTABLE_NPAGE_ONE );
932 testcase( pWal->hdr.mxFrame==HASHTABLE_NPAGE_ONE+1 );
933  
934 if( pWal->hdr.mxFrame==0 ) return;
935  
936 /* Obtain pointers to the hash-table and page-number array containing
937 ** the entry that corresponds to frame pWal->hdr.mxFrame. It is guaranteed
938 ** that the page said hash-table and array reside on is already mapped.
939 */
940 Debug.Assert( pWal->nWiData>walFramePage(pWal->hdr.mxFrame) );
941 Debug.Assert( pWal->apWiData[walFramePage(pWal->hdr.mxFrame)] );
942 walHashGet(pWal, walFramePage(pWal->hdr.mxFrame), &aHash, &aPgno, &iZero);
943  
944 /* Zero all hash-table entries that correspond to frame numbers greater
945 ** than pWal->hdr.mxFrame.
946 */
947 iLimit = pWal->hdr.mxFrame - iZero;
948 Debug.Assert( iLimit>0 );
949 for(i=0; i<HASHTABLE_NSLOT; i++){
950 if( aHash[i]>iLimit ){
951 aHash[i] = 0;
952 }
953 }
954  
955 /* Zero the entries in the aPgno array that correspond to frames with
956 ** frame numbers greater than pWal->hdr.mxFrame.
957 */
958 nByte = (int)((char )aHash - (char )&aPgno[iLimit+1]);
959 memset((void )&aPgno[iLimit+1], 0, nByte);
960  
961 #if SQLITE_ENABLE_EXPENSIVE_ASSERT
962 /* Verify that the every entry in the mapping region is still reachable
963 ** via the hash table even after the cleanup.
964 */
965 if( iLimit ){
966 int i; /* Loop counter */
967 int iKey; /* Hash key */
968 for(i=1; i<=iLimit; i++){
969 for(iKey=walHash(aPgno[i]); aHash[iKey]; iKey=walNextHash(iKey)){
970 if( aHash[iKey]==i ) break;
971 }
972 Debug.Assert( aHash[iKey]==i );
973 }
974 }
975 #endif //* SQLITE_ENABLE_EXPENSIVE_ASSERT */
976 }
977  
978  
979 /*
980 ** Set an entry in the wal-index that will map database page number
981 ** pPage into WAL frame iFrame.
982 */
983 static int walIndexAppend(Wal *pWal, u32 iFrame, u32 iPage){
984 int rc; /* Return code */
985 u32 iZero = 0; /* One less than frame number of aPgno[1] */
986 volatile u32 *aPgno = 0; /* Page number array */
987 volatile ht_slot *aHash = 0; /* Hash table */
988  
989 rc = walHashGet(pWal, walFramePage(iFrame), &aHash, &aPgno, &iZero);
990  
991 /* Assuming the wal-index file was successfully mapped, populate the
992 ** page number array and hash table entry.
993 */
994 if( rc==SQLITE_OK ){
995 int iKey; /* Hash table key */
996 int idx; /* Value to write to hash-table slot */
997 int nCollide; /* Number of hash collisions */
998  
999 idx = iFrame - iZero;
1000 Debug.Assert( idx <= HASHTABLE_NSLOT/2 + 1 );
1001  
1002 /* If this is the first entry to be added to this hash-table, zero the
1003 ** entire hash table and aPgno[] array before proceding.
1004 */
1005 if( idx==1 ){
1006 int nByte = (int)((u8 )&aHash[HASHTABLE_NSLOT] - (u8 )&aPgno[1]);
1007 memset((void)&aPgno[1], 0, nByte);
1008 }
1009  
1010 /* If the entry in aPgno[] is already set, then the previous writer
1011 ** must have exited unexpectedly in the middle of a transaction (after
1012 ** writing one or more dirty pages to the WAL to free up memory).
1013 ** Remove the remnants of that writers uncommitted transaction from
1014 ** the hash-table before writing any new entries.
1015 */
1016 if( aPgno[idx] ){
1017 walCleanupHash(pWal);
1018 Debug.Assert( !aPgno[idx] );
1019 }
1020  
1021 /* Write the aPgno[] array entry and the hash-table slot. */
1022 nCollide = idx;
1023 for(iKey=walHash(iPage); aHash[iKey]; iKey=walNextHash(iKey)){
1024 if( (nCollide--)==0 ) return SQLITE_CORRUPT_BKPT;
1025 }
1026 aPgno[idx] = iPage;
1027 aHash[iKey] = (ht_slot)idx;
1028  
1029 #if SQLITE_ENABLE_EXPENSIVE_ASSERT
1030 /* Verify that the number of entries in the hash table exactly equals
1031 ** the number of entries in the mapping region.
1032 */
1033 {
1034 int i; /* Loop counter */
1035 int nEntry = 0; /* Number of entries in the hash table */
1036 for(i=0; i<HASHTABLE_NSLOT; i++){ if( aHash[i] ) nEntry++; }
1037 Debug.Assert( nEntry==idx );
1038 }
1039  
1040 /* Verify that the every entry in the mapping region is reachable
1041 ** via the hash table. This turns out to be a really, really expensive
1042 ** thing to check, so only do this occasionally - not on every
1043 ** iteration.
1044 */
1045 if( (idx&0x3ff)==0 ){
1046 int i; /* Loop counter */
1047 for(i=1; i<=idx; i++){
1048 for(iKey=walHash(aPgno[i]); aHash[iKey]; iKey=walNextHash(iKey)){
1049 if( aHash[iKey]==i ) break;
1050 }
1051 Debug.Assert( aHash[iKey]==i );
1052 }
1053 }
1054 #endif //* SQLITE_ENABLE_EXPENSIVE_ASSERT */
1055 }
1056  
1057  
1058 return rc;
1059 }
1060  
1061  
1062 /*
1063 ** Recover the wal-index by reading the write-ahead log file.
1064 **
1065 ** This routine first tries to establish an exclusive lock on the
1066 ** wal-index to prevent other threads/processes from doing anything
1067 ** with the WAL or wal-index while recovery is running. The
1068 ** WAL_RECOVER_LOCK is also held so that other threads will know
1069 ** that this thread is running recovery. If unable to establish
1070 ** the necessary locks, this routine returns SQLITE_BUSY.
1071 */
1072 static int walIndexRecover(Wal *pWal){
1073 int rc; /* Return Code */
1074 i64 nSize; /* Size of log file */
1075 u32 aFrameCksum[2] = {0, 0};
1076 int iLock; /* Lock offset to lock for checkpoint */
1077 int nLock; /* Number of locks to hold */
1078  
1079 /* Obtain an exclusive lock on all byte in the locking range not already
1080 ** locked by the caller. The caller is guaranteed to have locked the
1081 ** WAL_WRITE_LOCK byte, and may have also locked the WAL_CKPT_LOCK byte.
1082 ** If successful, the same bytes that are locked here are unlocked before
1083 ** this function returns.
1084 */
1085 Debug.Assert( pWal->ckptLock==1 || pWal->ckptLock==0 );
1086 Debug.Assert( WAL_ALL_BUT_WRITE==WAL_WRITE_LOCK+1 );
1087 Debug.Assert( WAL_CKPT_LOCK==WAL_ALL_BUT_WRITE );
1088 Debug.Assert( pWal->writeLock );
1089 iLock = WAL_ALL_BUT_WRITE + pWal->ckptLock;
1090 nLock = SQLITE_SHM_NLOCK - iLock;
1091 rc = walLockExclusive(pWal, iLock, nLock);
1092 if( rc ){
1093 return rc;
1094 }
1095 WALTRACE(("WAL%p: recovery begin...\n", pWal));
1096  
1097 memset(&pWal->hdr, 0, sizeof(WalIndexHdr));
1098  
1099 rc = sqlite3OsFileSize(pWal->pWalFd, &nSize);
1100 if( rc!=SQLITE_OK ){
1101 goto recovery_error;
1102 }
1103  
1104 if( nSize>WAL_HDRSIZE ){
1105 u8 aBuf[WAL_HDRSIZE]; /* Buffer to load WAL header into */
1106 u8 *aFrame = 0; /* Malloc'd buffer to load entire frame */
1107 int szFrame; /* Number of bytes in buffer aFrame[] */
1108 u8 *aData; /* Pointer to data part of aFrame buffer */
1109 int iFrame; /* Index of last frame read */
1110 i64 iOffset; /* Next offset to read from log file */
1111 int szPage; /* Page size according to the log */
1112 u32 magic; /* Magic value read from WAL header */
1113 u32 version; /* Magic value read from WAL header */
1114  
1115 /* Read in the WAL header. */
1116 rc = sqlite3OsRead(pWal->pWalFd, aBuf, WAL_HDRSIZE, 0);
1117 if( rc!=SQLITE_OK ){
1118 goto recovery_error;
1119 }
1120  
1121 /* If the database page size is not a power of two, or is greater than
1122 ** SQLITE_MAX_PAGE_SIZE, conclude that the WAL file contains no valid
1123 ** data. Similarly, if the 'magic' value is invalid, ignore the whole
1124 ** WAL file.
1125 */
1126 magic = sqlite3Get4byte(&aBuf[0]);
1127 szPage = sqlite3Get4byte(&aBuf[8]);
1128 if( (magic&0xFFFFFFFE)!=WAL_MAGIC
1129 || szPage&(szPage-1)
1130 || szPage>SQLITE_MAX_PAGE_SIZE
1131 || szPage<512
1132 ){
1133 goto finished;
1134 }
1135 pWal->hdr.bigEndCksum = (u8)(magic&0x00000001);
1136 pWal->szPage = szPage;
1137 pWal->nCkpt = sqlite3Get4byte(&aBuf[12]);
1138 memcpy(&pWal->hdr.aSalt, &aBuf[16], 8);
1139  
1140 /* Verify that the WAL header checksum is correct */
1141 walChecksumBytes(pWal->hdr.bigEndCksum==SQLITE_BIGENDIAN,
1142 aBuf, WAL_HDRSIZE-2*4, 0, pWal->hdr.aFrameCksum
1143 );
1144 if( pWal->hdr.aFrameCksum[0]!=sqlite3Get4byte(&aBuf[24])
1145 || pWal->hdr.aFrameCksum[1]!=sqlite3Get4byte(&aBuf[28])
1146 ){
1147 goto finished;
1148 }
1149  
1150 /* Verify that the version number on the WAL format is one that
1151 ** are able to understand */
1152 version = sqlite3Get4byte(&aBuf[4]);
1153 if( version!=WAL_MAX_VERSION ){
1154 rc = SQLITE_CANTOPEN_BKPT;
1155 goto finished;
1156 }
1157  
1158 /* Malloc a buffer to read frames into. */
1159 szFrame = szPage + WAL_FRAME_HDRSIZE;
1160 aFrame = (u8 )sqlite3_malloc(szFrame);
1161 if( null==aFrame ){
1162 rc = SQLITE_NOMEM;
1163 goto recovery_error;
1164 }
1165 aData = aFrame[WAL_FRAME_HDRSIZE];
1166  
1167 /* Read all frames from the log file. */
1168 iFrame = 0;
1169 for(iOffset=WAL_HDRSIZE; (iOffset+szFrame)<=nSize; iOffset+=szFrame){
1170 u32 pgno; /* Database page number for frame */
1171 u32 nTruncate; /* dbsize field from frame header */
1172 int isValid; /* True if this frame is valid */
1173  
1174 /* Read and decode the next log frame. */
1175 rc = sqlite3OsRead(pWal->pWalFd, aFrame, szFrame, iOffset);
1176 if( rc!=SQLITE_OK ) break;
1177 isValid = walDecodeFrame(pWal, &pgno, &nTruncate, aData, aFrame);
1178 if( null==isValid ) break;
1179 rc = walIndexAppend(pWal, ++iFrame, pgno);
1180 if( rc!=SQLITE_OK ) break;
1181  
1182 /* If nTruncate is non-zero, this is a commit record. */
1183 if( nTruncate ){
1184 pWal->hdr.mxFrame = iFrame;
1185 pWal->hdr.nPage = nTruncate;
1186 pWal->hdr.szPage = (u16)((szPage&0xff00) | (szPage>>16));
1187 testcase( szPage<=32768 );
1188 testcase( szPage>=65536 );
1189 aFrameCksum[0] = pWal->hdr.aFrameCksum[0];
1190 aFrameCksum[1] = pWal->hdr.aFrameCksum[1];
1191 }
1192 }
1193  
1194 sqlite3_free(aFrame);
1195 }
1196  
1197 finished:
1198 if( rc==SQLITE_OK ){
1199 volatile WalCkptInfo *pInfo;
1200 int i;
1201 pWal->hdr.aFrameCksum[0] = aFrameCksum[0];
1202 pWal->hdr.aFrameCksum[1] = aFrameCksum[1];
1203 walIndexWriteHdr(pWal);
1204  
1205 /* Reset the checkpoint-header. This is safe because this thread is
1206 ** currently holding locks that exclude all other readers, writers and
1207 ** checkpointers.
1208 */
1209 pInfo = walCkptInfo(pWal);
1210 pInfo->nBackfill = 0;
1211 pInfo->aReadMark[0] = 0;
1212 for(i=1; i<WAL_NREADER; i++) pInfo->aReadMark[i] = READMARK_NOT_USED;
1213  
1214 /* If more than one frame was recovered from the log file, report an
1215 ** event via sqlite3_log(). This is to help with identifying performance
1216 ** problems caused by applications routinely shutting down without
1217 ** checkpointing the log file.
1218 */
1219 if( pWal->hdr.nPage ){
1220 sqlite3_log(SQLITE_OK, "Recovered %d frames from WAL file %s",
1221 pWal->hdr.nPage, pWal->zWalName
1222 );
1223 }
1224 }
1225  
1226 recovery_error:
1227 WALTRACE(("WAL%p: recovery %s\n", pWal, rc ? "failed" : "ok"));
1228 walUnlockExclusive(pWal, iLock, nLock);
1229 return rc;
1230 }
1231  
1232 /*
1233 ** Close an open wal-index.
1234 */
1235 static void walIndexClose(Wal *pWal, int isDelete){
1236 if( pWal->exclusiveMode==WAL_HEAPMEMORY_MODE ){
1237 int i;
1238 for(i=0; i<pWal->nWiData; i++){
1239 sqlite3_free((void )pWal->apWiData[i]);
1240 pWal->apWiData[i] = 0;
1241 }
1242 }else{
1243 sqlite3OsShmUnmap(pWal->pDbFd, isDelete);
1244 }
1245 }
1246  
1247 /*
1248 ** Open a connection to the WAL file zWalName. The database file must
1249 ** already be opened on connection pDbFd. The buffer that zWalName points
1250 ** to must remain valid for the lifetime of the returned Wal* handle.
1251 **
1252 ** A SHARED lock should be held on the database file when this function
1253 ** is called. The purpose of this SHARED lock is to prevent any other
1254 ** client from unlinking the WAL or wal-index file. If another process
1255 ** were to do this just after this client opened one of these files, the
1256 ** system would be badly broken.
1257 **
1258 ** If the log file is successfully opened, SQLITE_OK is returned and
1259 ** *ppWal is set to point to a new WAL handle. If an error occurs,
1260 ** an SQLite error code is returned and *ppWal is left unmodified.
1261 */
1262 int sqlite3WalOpen(
1263 sqlite3_vfs *pVfs, /* vfs module to open wal and wal-index */
1264 sqlite3_file *pDbFd, /* The open database file */
1265 string zWalName, /* Name of the WAL file */
1266 int bNoShm, /* True to run in heap-memory mode */
1267 i64 mxWalSize, /* Truncate WAL to this size on reset */
1268 Wal **ppWal /* OUT: Allocated Wal handle */
1269 ){
1270 int rc; /* Return Code */
1271 Wal *pRet; /* Object to allocate and return */
1272 int flags; /* Flags passed to OsOpen() */
1273  
1274 Debug.Assert( zWalName && zWalName[0] );
1275 Debug.Assert( pDbFd );
1276  
1277 /* In the amalgamation, the os_unix.c and os_win.c source files come before
1278 ** this source file. Verify that the #defines of the locking byte offsets
1279 ** in os_unix.c and os_win.c agree with the WALINDEX_LOCK_OFFSET value.
1280 */
1281 #if WIN_SHM_BASE
1282 Debug.Assert( WIN_SHM_BASE==WALINDEX_LOCK_OFFSET );
1283 #endif
1284 #if UNIX_SHM_BASE
1285 Debug.Assert( UNIX_SHM_BASE==WALINDEX_LOCK_OFFSET );
1286 #endif
1287  
1288  
1289 /* Allocate an instance of struct Wal to return. */
1290 *ppWal = 0;
1291 pRet = (Wal)sqlite3MallocZero(sizeof(Wal) + pVfs->szOsFile);
1292 if( null==pRet ){
1293 return SQLITE_NOMEM;
1294 }
1295  
1296 pRet->pVfs = pVfs;
1297 pRet->pWalFd = (sqlite3_file )&pRet[1];
1298 pRet->pDbFd = pDbFd;
1299 pRet->readLock = -1;
1300 pRet->mxWalSize = mxWalSize;
1301 pRet->zWalName = zWalName;
1302 pRet->exclusiveMode = (bNoShm ? WAL_HEAPMEMORY_MODE: WAL_NORMAL_MODE);
1303  
1304 /* Open file handle on the write-ahead log file. */
1305 flags = (SQLITE_OPEN_READWRITE|SQLITE_OPEN_CREATE|SQLITE_OPEN_WAL);
1306 rc = sqlite3OsOpen(pVfs, zWalName, pRet->pWalFd, flags, &flags);
1307 if( rc==SQLITE_OK && flags&SQLITE_OPEN_READONLY ){
1308 pRet->readOnly = WAL_RDONLY;
1309 }
1310  
1311 if( rc!=SQLITE_OK ){
1312 walIndexClose(pRet, 0);
1313 sqlite3OsClose(pRet->pWalFd);
1314 sqlite3_free(pRet);
1315 }else{
1316 *ppWal = pRet;
1317 WALTRACE(("WAL%d: opened\n", pRet));
1318 }
1319 return rc;
1320 }
1321  
1322 /*
1323 ** Change the size to which the WAL file is trucated on each reset.
1324 */
1325 void sqlite3WalLimit(Wal *pWal, i64 iLimit){
1326 if( pWal ) pWal->mxWalSize = iLimit;
1327 }
1328  
1329 /*
1330 ** Find the smallest page number out of all pages held in the WAL that
1331 ** has not been returned by any prior invocation of this method on the
1332 ** same WalIterator object. Write into *piFrame the frame index where
1333 ** that page was last written into the WAL. Write into *piPage the page
1334 ** number.
1335 **
1336 ** Return 0 on success. If there are no pages in the WAL with a page
1337 ** number larger than *piPage, then return 1.
1338 */
1339 static int walIteratorNext(
1340 WalIterator *p, /* Iterator */
1341 u32 *piPage, /* OUT: The page number of the next page */
1342 u32 *piFrame /* OUT: Wal frame index of next page */
1343 ){
1344 u32 iMin; /* Result pgno must be greater than iMin */
1345 u32 iRet = 0xFFFFFFFF; /* 0xffffffff is never a valid page number */
1346 int i; /* For looping through segments */
1347  
1348 iMin = p->iPrior;
1349 Debug.Assert( iMin<0xffffffff );
1350 for(i=p->nSegment-1; i>=0; i--){
1351 struct WalSegment *pSegment = p->aSegment[i];
1352 while( pSegment->iNext<pSegment->nEntry ){
1353 u32 iPg = pSegment->aPgno[pSegment->aIndex[pSegment->iNext]];
1354 if( iPg>iMin ){
1355 if( iPg<iRet ){
1356 iRet = iPg;
1357 *piFrame = pSegment->iZero + pSegment->aIndex[pSegment->iNext];
1358 }
1359 break;
1360 }
1361 pSegment->iNext++;
1362 }
1363 }
1364  
1365 *piPage = p->iPrior = iRet;
1366 return (iRet==0xFFFFFFFF);
1367 }
1368  
1369 /*
1370 ** This function merges two sorted lists into a single sorted list.
1371 **
1372 ** aLeft[] and aRight[] are arrays of indices. The sort key is
1373 ** aContent[aLeft[]] and aContent[aRight[]]. Upon entry, the following
1374 ** is guaranteed for all J<K:
1375 **
1376 ** aContent[aLeft[J]] < aContent[aLeft[K]]
1377 ** aContent[aRight[J]] < aContent[aRight[K]]
1378 **
1379 ** This routine overwrites aRight[] with a new (probably longer) sequence
1380 ** of indices such that the aRight[] contains every index that appears in
1381 ** either aLeft[] or the old aRight[] and such that the second condition
1382 ** above is still met.
1383 **
1384 ** The aContent[aLeft[X]] values will be unique for all X. And the
1385 ** aContent[aRight[X]] values will be unique too. But there might be
1386 ** one or more combinations of X and Y such that
1387 **
1388 ** aLeft[X]!=aRight[Y] && aContent[aLeft[X]] == aContent[aRight[Y]]
1389 **
1390 ** When that happens, omit the aLeft[X] and use the aRight[Y] index.
1391 */
1392 static void walMerge(
1393 const u32 *aContent, /* Pages in wal - keys for the sort */
1394 ht_slot *aLeft, /* IN: Left hand input list */
1395 int nLeft, /* IN: Elements in array *paLeft */
1396 ht_slot **paRight, /* IN/OUT: Right hand input list */
1397 int *pnRight, /* IN/OUT: Elements in *paRight */
1398 ht_slot *aTmp /* Temporary buffer */
1399 ){
1400 int iLeft = 0; /* Current index in aLeft */
1401 int iRight = 0; /* Current index in aRight */
1402 int iOut = 0; /* Current index in output buffer */
1403 int nRight = *pnRight;
1404 ht_slot *aRight = *paRight;
1405  
1406 Debug.Assert( nLeft>0 && nRight>0 );
1407 while( iRight<nRight || iLeft<nLeft ){
1408 ht_slot logpage;
1409 Pgno dbpage;
1410  
1411 if( (iLeft<nLeft)
1412 && (iRight>=nRight || aContent[aLeft[iLeft]]<aContent[aRight[iRight]])
1413 ){
1414 logpage = aLeft[iLeft++];
1415 }else{
1416 logpage = aRight[iRight++];
1417 }
1418 dbpage = aContent[logpage];
1419  
1420 aTmp[iOut++] = logpage;
1421 if( iLeft<nLeft && aContent[aLeft[iLeft]]==dbpage ) iLeft++;
1422  
1423 Debug.Assert( iLeft>=nLeft || aContent[aLeft[iLeft]]>dbpage );
1424 Debug.Assert( iRight>=nRight || aContent[aRight[iRight]]>dbpage );
1425 }
1426  
1427 *paRight = aLeft;
1428 *pnRight = iOut;
1429 memcpy(aLeft, aTmp, sizeof(aTmp[0])*iOut);
1430 }
1431  
1432 /*
1433 ** Sort the elements in list aList using aContent[] as the sort key.
1434 ** Remove elements with duplicate keys, preferring to keep the
1435 ** larger aList[] values.
1436 **
1437 ** The aList[] entries are indices into aContent[]. The values in
1438 ** aList[] are to be sorted so that for all J<K:
1439 **
1440 ** aContent[aList[J]] < aContent[aList[K]]
1441 **
1442 ** For any X and Y such that
1443 **
1444 ** aContent[aList[X]] == aContent[aList[Y]]
1445 **
1446 ** Keep the larger of the two values aList[X] and aList[Y] and discard
1447 ** the smaller.
1448 */
1449 static void walMergesort(
1450 const u32 *aContent, /* Pages in wal */
1451 ht_slot *aBuffer, /* Buffer of at least *pnList items to use */
1452 ht_slot *aList, /* IN/OUT: List to sort */
1453 int *pnList /* IN/OUT: Number of elements in aList[] */
1454 ){
1455 struct Sublist {
1456 int nList; /* Number of elements in aList */
1457 ht_slot *aList; /* Pointer to sub-list content */
1458 };
1459  
1460 const int nList = *pnList; /* Size of input list */
1461 int nMerge = 0; /* Number of elements in list aMerge */
1462 ht_slot *aMerge = 0; /* List to be merged */
1463 int iList; /* Index into input list */
1464 int iSub = 0; /* Index into aSub array */
1465 struct Sublist aSub[13]; /* Array of sub-lists */
1466  
1467 memset(aSub, 0, sizeof(aSub));
1468 Debug.Assert( nList<=HASHTABLE_NPAGE && nList>0 );
1469 Debug.Assert( HASHTABLE_NPAGE==(1<<(ArraySize(aSub)-1)) );
1470  
1471 for(iList=0; iList<nList; iList++){
1472 nMerge = 1;
1473 aMerge = aList[iList];
1474 for(iSub=0; iList & (1<<iSub); iSub++){
1475 struct Sublist *p = aSub[iSub];
1476 Debug.Assert( p->aList && p->nList<=(1<<iSub) );
1477 Debug.Assert( p->aList==&aList[iList&~((2<<iSub)-1)] );
1478 walMerge(aContent, p->aList, p->nList, &aMerge, &nMerge, aBuffer);
1479 }
1480 aSub[iSub].aList = aMerge;
1481 aSub[iSub].nList = nMerge;
1482 }
1483  
1484 for(iSub++; iSub<ArraySize(aSub); iSub++){
1485 if( nList & (1<<iSub) ){
1486 struct Sublist *p = aSub[iSub];
1487 Debug.Assert( p->nList<=(1<<iSub) );
1488 Debug.Assert( p->aList==&aList[nList&~((2<<iSub)-1)] );
1489 walMerge(aContent, p->aList, p->nList, &aMerge, &nMerge, aBuffer);
1490 }
1491 }
1492 Debug.Assert( aMerge==aList );
1493 *pnList = nMerge;
1494  
1495 #if SQLITE_DEBUG
1496 {
1497 int i;
1498 for(i=1; i<*pnList; i++){
1499 Debug.Assert( aContent[aList[i]] > aContent[aList[i-1]] );
1500 }
1501 }
1502 #endif
1503 }
1504  
1505 /*
1506 ** Free an iterator allocated by walIteratorInit().
1507 */
1508 static void walIteratorFree(WalIterator *p){
1509 sqlite3ScratchFree(p);
1510 }
1511  
1512 /*
1513 ** Construct a WalInterator object that can be used to loop over all
1514 ** pages in the WAL in ascending order. The caller must hold the checkpoint
1515 ** lock.
1516 **
1517 ** On success, make *pp point to the newly allocated WalInterator object
1518 ** return SQLITE_OK. Otherwise, return an error code. If this routine
1519 ** returns an error, the value of *pp is undefined.
1520 **
1521 ** The calling routine should invoke walIteratorFree() to destroy the
1522 ** WalIterator object when it has finished with it.
1523 */
1524 static int walIteratorInit(Wal *pWal, WalIterator **pp){
1525 WalIterator *p; /* Return value */
1526 int nSegment; /* Number of segments to merge */
1527 u32 iLast; /* Last frame in log */
1528 int nByte; /* Number of bytes to allocate */
1529 int i; /* Iterator variable */
1530 ht_slot *aTmp; /* Temp space used by merge-sort */
1531 int rc = SQLITE_OK; /* Return Code */
1532  
1533 /* This routine only runs while holding the checkpoint lock. And
1534 ** it only runs if there is actually content in the log (mxFrame>0).
1535 */
1536 Debug.Assert( pWal->ckptLock && pWal->hdr.mxFrame>0 );
1537 iLast = pWal->hdr.mxFrame;
1538  
1539 /* Allocate space for the WalIterator object. */
1540 nSegment = walFramePage(iLast) + 1;
1541 nByte = sizeof(WalIterator)
1542 + (nSegment-1)*sizeof(struct WalSegment)
1543 + iLast*sizeof(ht_slot);
1544 p = (WalIterator )sqlite3ScratchMalloc(nByte);
1545 if( null==p ){
1546 return SQLITE_NOMEM;
1547 }
1548 memset(p, 0, nByte);
1549 p->nSegment = nSegment;
1550  
1551 /* Allocate temporary space used by the merge-sort routine. This block
1552 ** of memory will be freed before this function returns.
1553 */
1554 aTmp = (ht_slot )sqlite3ScratchMalloc(
1555 sizeof(ht_slot) * (iLast>HASHTABLE_NPAGE?HASHTABLE_NPAGE:iLast)
1556 );
1557 if( null==aTmp ){
1558 rc = SQLITE_NOMEM;
1559 }
1560  
1561 for(i=0; rc==SQLITE_OK && i<nSegment; i++){
1562 volatile ht_slot *aHash;
1563 u32 iZero;
1564 volatile u32 *aPgno;
1565  
1566 rc = walHashGet(pWal, i, &aHash, &aPgno, &iZero);
1567 if( rc==SQLITE_OK ){
1568 int j; /* Counter variable */
1569 int nEntry; /* Number of entries in this segment */
1570 ht_slot *aIndex; /* Sorted index for this segment */
1571  
1572 aPgno++;
1573 if( (i+1)==nSegment ){
1574 nEntry = (int)(iLast - iZero);
1575 }else{
1576 nEntry = (int)((u32)aHash - (u32)aPgno);
1577 }
1578 aIndex = ((ht_slot )&p->aSegment[p->nSegment])[iZero];
1579 iZero++;
1580  
1581 for(j=0; j<nEntry; j++){
1582 aIndex[j] = (ht_slot)j;
1583 }
1584 walMergesort((u32 )aPgno, aTmp, aIndex, &nEntry);
1585 p->aSegment[i].iZero = iZero;
1586 p->aSegment[i].nEntry = nEntry;
1587 p->aSegment[i].aIndex = aIndex;
1588 p->aSegment[i].aPgno = (u32 )aPgno;
1589 }
1590 }
1591 sqlite3ScratchFree(aTmp);
1592  
1593 if( rc!=SQLITE_OK ){
1594 walIteratorFree(p);
1595 }
1596 *pp = p;
1597 return rc;
1598 }
1599  
1600 /*
1601 ** Attempt to obtain the exclusive WAL lock defined by parameters lockIdx and
1602 ** n. If the attempt fails and parameter xBusy is not NULL, then it is a
1603 ** busy-handler function. Invoke it and retry the lock until either the
1604 ** lock is successfully obtained or the busy-handler returns 0.
1605 */
1606 static int walBusyLock(
1607 Wal *pWal, /* WAL connection */
1608 int (*xBusy)(void), /* Function to call when busy */
1609 void *pBusyArg, /* Context argument for xBusyHandler */
1610 int lockIdx, /* Offset of first byte to lock */
1611 int n /* Number of bytes to lock */
1612 ){
1613 int rc;
1614 do {
1615 rc = walLockExclusive(pWal, lockIdx, n);
1616 }while( xBusy && rc==SQLITE_BUSY && xBusy(pBusyArg) );
1617 return rc;
1618 }
1619  
1620 /*
1621 ** The cache of the wal-index header must be valid to call this function.
1622 ** Return the page-size in bytes used by the database.
1623 */
1624 static int walPagesize(Wal *pWal){
1625 return (pWal->hdr.szPage&0xfe00) + ((pWal->hdr.szPage&0x0001)<<16);
1626 }
1627  
1628 /*
1629 ** Copy as much content as we can from the WAL back into the database file
1630 ** in response to an sqlite3_wal_checkpoint() request or the equivalent.
1631 **
1632 ** The amount of information copies from WAL to database might be limited
1633 ** by active readers. This routine will never overwrite a database page
1634 ** that a concurrent reader might be using.
1635 **
1636 ** All I/O barrier operations (a.k.a fsyncs) occur in this routine when
1637 ** SQLite is in WAL-mode in synchronous=NORMAL. That means that if
1638 ** checkpoints are always run by a background thread or background
1639 ** process, foreground threads will never block on a lengthy fsync call.
1640 **
1641 ** Fsync is called on the WAL before writing content out of the WAL and
1642 ** into the database. This ensures that if the new content is persistent
1643 ** in the WAL and can be recovered following a power-loss or hard reset.
1644 **
1645 ** Fsync is also called on the database file if (and only if) the entire
1646 ** WAL content is copied into the database file. This second fsync makes
1647 ** it safe to delete the WAL since the new content will persist in the
1648 ** database file.
1649 **
1650 ** This routine uses and updates the nBackfill field of the wal-index header.
1651 ** This is the only routine tha will increase the value of nBackfill.
1652 ** (A WAL reset or recovery will revert nBackfill to zero, but not increase
1653 ** its value.)
1654 **
1655 ** The caller must be holding sufficient locks to ensure that no other
1656 ** checkpoint is running (in any other thread or process) at the same
1657 ** time.
1658 */
1659 static int walCheckpoint(
1660 Wal *pWal, /* Wal connection */
1661 int eMode, /* One of PASSIVE, FULL or RESTART */
1662 int (*xBusyCall)(void), /* Function to call when busy */
1663 void *pBusyArg, /* Context argument for xBusyHandler */
1664 int sync_flags, /* Flags for OsSync() (or 0) */
1665 u8 *zBuf /* Temporary buffer to use */
1666 ){
1667 int rc; /* Return code */
1668 int szPage; /* Database page-size */
1669 WalIterator *pIter = 0; /* Wal iterator context */
1670 u32 iDbpage = 0; /* Next database page to write */
1671 u32 iFrame = 0; /* Wal frame containing data for iDbpage */
1672 u32 mxSafeFrame; /* Max frame that can be backfilled */
1673 u32 mxPage; /* Max database page to write */
1674 int i; /* Loop counter */
1675 volatile WalCkptInfo *pInfo; /* The checkpoint status information */
1676 int (*xBusy)(void) = 0; /* Function to call when waiting for locks */
1677  
1678 szPage = walPagesize(pWal);
1679 testcase( szPage<=32768 );
1680 testcase( szPage>=65536 );
1681 pInfo = walCkptInfo(pWal);
1682 if( pInfo->nBackfill>=pWal->hdr.mxFrame ) return SQLITE_OK;
1683  
1684 /* Allocate the iterator */
1685 rc = walIteratorInit(pWal, &pIter);
1686 if( rc!=SQLITE_OK ){
1687 return rc;
1688 }
1689 Debug.Assert( pIter );
1690  
1691 if( eMode!=SQLITE_CHECKPOINT_PASSIVE ) xBusy = xBusyCall;
1692  
1693 /* Compute in mxSafeFrame the index of the last frame of the WAL that is
1694 ** safe to write into the database. Frames beyond mxSafeFrame might
1695 ** overwrite database pages that are in use by active readers and thus
1696 ** cannot be backfilled from the WAL.
1697 */
1698 mxSafeFrame = pWal->hdr.mxFrame;
1699 mxPage = pWal->hdr.nPage;
1700 for(i=1; i<WAL_NREADER; i++){
1701 u32 y = pInfo->aReadMark[i];
1702 if( mxSafeFrame>y ){
1703 Debug.Assert( y<=pWal->hdr.mxFrame );
1704 rc = walBusyLock(pWal, xBusy, pBusyArg, WAL_READ_LOCK(i), 1);
1705 if( rc==SQLITE_OK ){
1706 pInfo->aReadMark[i] = READMARK_NOT_USED;
1707 walUnlockExclusive(pWal, WAL_READ_LOCK(i), 1);
1708 }else if( rc==SQLITE_BUSY ){
1709 mxSafeFrame = y;
1710 xBusy = 0;
1711 }else{
1712 goto walcheckpoint_out;
1713 }
1714 }
1715 }
1716  
1717 if( pInfo->nBackfill<mxSafeFrame
1718 && (rc = walBusyLock(pWal, xBusy, pBusyArg, WAL_READ_LOCK(0), 1))==SQLITE_OK
1719 ){
1720 i64 nSize; /* Current size of database file */
1721 u32 nBackfill = pInfo->nBackfill;
1722  
1723 /* Sync the WAL to disk */
1724 if( sync_flags ){
1725 rc = sqlite3OsSync(pWal->pWalFd, sync_flags);
1726 }
1727  
1728 /* If the database file may grow as a result of this checkpoint, hint
1729 ** about the eventual size of the db file to the VFS layer.
1730 */
1731 if( rc==SQLITE_OK ){
1732 i64 nReq = ((i64)mxPage * szPage);
1733 rc = sqlite3OsFileSize(pWal->pDbFd, &nSize);
1734 if( rc==SQLITE_OK && nSize<nReq ){
1735 sqlite3OsFileControl(pWal->pDbFd, SQLITE_FCNTL_SIZE_HINT, &nReq);
1736 }
1737 }
1738  
1739 /* Iterate through the contents of the WAL, copying data to the db file. */
1740 while( rc==SQLITE_OK && 0==walIteratorNext(pIter, &iDbpage, &iFrame) ){
1741 i64 iOffset;
1742 Debug.Assert( walFramePgno(pWal, iFrame)==iDbpage );
1743 if( iFrame<=nBackfill || iFrame>mxSafeFrame || iDbpage>mxPage ) continue;
1744 iOffset = walFrameOffset(iFrame, szPage) + WAL_FRAME_HDRSIZE;
1745 /* testcase( IS_BIG_INT(iOffset) ); // requires a 4GiB WAL file */
1746 rc = sqlite3OsRead(pWal->pWalFd, zBuf, szPage, iOffset);
1747 if( rc!=SQLITE_OK ) break;
1748 iOffset = (iDbpage-1)*(i64)szPage;
1749 testcase( IS_BIG_INT(iOffset) );
1750 rc = sqlite3OsWrite(pWal->pDbFd, zBuf, szPage, iOffset);
1751 if( rc!=SQLITE_OK ) break;
1752 }
1753  
1754 /* If work was actually accomplished... */
1755 if( rc==SQLITE_OK ){
1756 if( mxSafeFrame==walIndexHdr(pWal)->mxFrame ){
1757 i64 szDb = pWal->hdr.nPage*(i64)szPage;
1758 testcase( IS_BIG_INT(szDb) );
1759 rc = sqlite3OsTruncate(pWal->pDbFd, szDb);
1760 if( rc==SQLITE_OK && sync_flags ){
1761 rc = sqlite3OsSync(pWal->pDbFd, sync_flags);
1762 }
1763 }
1764 if( rc==SQLITE_OK ){
1765 pInfo->nBackfill = mxSafeFrame;
1766 }
1767 }
1768  
1769 /* Release the reader lock held while backfilling */
1770 walUnlockExclusive(pWal, WAL_READ_LOCK(0), 1);
1771 }
1772  
1773 if( rc==SQLITE_BUSY ){
1774 /* Reset the return code so as not to report a checkpoint failure
1775 ** just because there are active readers. */
1776 rc = SQLITE_OK;
1777 }
1778  
1779 /* If this is an SQLITE_CHECKPOINT_RESTART operation, and the entire wal
1780 ** file has been copied into the database file, then block until all
1781 ** readers have finished using the wal file. This ensures that the next
1782 ** process to write to the database restarts the wal file.
1783 */
1784 if( rc==SQLITE_OK && eMode!=SQLITE_CHECKPOINT_PASSIVE ){
1785 Debug.Assert( pWal->writeLock );
1786 if( pInfo->nBackfill<pWal->hdr.mxFrame ){
1787 rc = SQLITE_BUSY;
1788 }else if( eMode==SQLITE_CHECKPOINT_RESTART ){
1789 Debug.Assert( mxSafeFrame==pWal->hdr.mxFrame );
1790 rc = walBusyLock(pWal, xBusy, pBusyArg, WAL_READ_LOCK(1), WAL_NREADER-1);
1791 if( rc==SQLITE_OK ){
1792 walUnlockExclusive(pWal, WAL_READ_LOCK(1), WAL_NREADER-1);
1793 }
1794 }
1795 }
1796  
1797 walcheckpoint_out:
1798 walIteratorFree(pIter);
1799 return rc;
1800 }
1801  
1802 /*
1803 ** Close a connection to a log file.
1804 */
1805 int sqlite3WalClose(
1806 Wal *pWal, /* Wal to close */
1807 int sync_flags, /* Flags to pass to OsSync() (or 0) */
1808 int nBuf,
1809 u8 *zBuf /* Buffer of at least nBuf bytes */
1810 ){
1811 int rc = SQLITE_OK;
1812 if( pWal ){
1813 int isDelete = 0; /* True to unlink wal and wal-index files */
1814  
1815 /* If an EXCLUSIVE lock can be obtained on the database file (using the
1816 ** ordinary, rollback-mode locking methods, this guarantees that the
1817 ** connection associated with this log file is the only connection to
1818 ** the database. In this case checkpoint the database and unlink both
1819 ** the wal and wal-index files.
1820 **
1821 ** The EXCLUSIVE lock is not released before returning.
1822 */
1823 rc = sqlite3OsLock(pWal->pDbFd, SQLITE_LOCK_EXCLUSIVE);
1824 if( rc==SQLITE_OK ){
1825 if( pWal->exclusiveMode==WAL_NORMAL_MODE ){
1826 pWal->exclusiveMode = WAL_EXCLUSIVE_MODE;
1827 }
1828 rc = sqlite3WalCheckpoint(
1829 pWal, SQLITE_CHECKPOINT_PASSIVE, 0, 0, sync_flags, nBuf, zBuf, 0, 0
1830 );
1831 if( rc==SQLITE_OK ){
1832 isDelete = 1;
1833 }
1834 }
1835  
1836 walIndexClose(pWal, isDelete);
1837 sqlite3OsClose(pWal->pWalFd);
1838 if( isDelete ){
1839 sqlite3OsDelete(pWal->pVfs, pWal->zWalName, 0);
1840 }
1841 WALTRACE(("WAL%p: closed\n", pWal));
1842 sqlite3_free((void )pWal->apWiData);
1843 sqlite3_free(pWal);
1844 }
1845 return rc;
1846 }
1847  
1848 /*
1849 ** Try to read the wal-index header. Return 0 on success and 1 if
1850 ** there is a problem.
1851 **
1852 ** The wal-index is in shared memory. Another thread or process might
1853 ** be writing the header at the same time this procedure is trying to
1854 ** read it, which might result in inconsistency. A dirty read is detected
1855 ** by verifying that both copies of the header are the same and also by
1856 ** a checksum on the header.
1857 **
1858 ** If and only if the read is consistent and the header is different from
1859 ** pWal->hdr, then pWal->hdr is updated to the content of the new header
1860 ** and *pChanged is set to 1.
1861 **
1862 ** If the checksum cannot be verified return non-zero. If the header
1863 ** is read successfully and the checksum verified, return zero.
1864 */
1865 static int walIndexTryHdr(Wal *pWal, int *pChanged){
1866 u32 aCksum[2]; /* Checksum on the header content */
1867 WalIndexHdr h1, h2; /* Two copies of the header content */
1868 WalIndexHdr volatile *aHdr; /* Header in shared memory */
1869  
1870 /* The first page of the wal-index must be mapped at this point. */
1871 Debug.Assert( pWal->nWiData>0 && pWal->apWiData[0] );
1872  
1873 /* Read the header. This might happen concurrently with a write to the
1874 ** same area of shared memory on a different CPU in a SMP,
1875 ** meaning it is possible that an inconsistent snapshot is read
1876 ** from the file. If this happens, return non-zero.
1877 **
1878 ** There are two copies of the header at the beginning of the wal-index.
1879 ** When reading, read [0] first then [1]. Writes are in the reverse order.
1880 ** Memory barriers are used to prevent the compiler or the hardware from
1881 ** reordering the reads and writes.
1882 */
1883 aHdr = walIndexHdr(pWal);
1884 memcpy(&h1, (void )&aHdr[0], sizeof(h1));
1885 walShmBarrier(pWal);
1886 memcpy(&h2, (void )&aHdr[1], sizeof(h2));
1887  
1888 if( memcmp(&h1, &h2, sizeof(h1))!=0 ){
1889 return 1; /* Dirty read */
1890 }
1891 if( h1.isInit==0 ){
1892 return 1; /* Malformed header - probably all zeros */
1893 }
1894 walChecksumBytes(1, (u8)&h1, sizeof(h1)-sizeof(h1.aCksum), 0, aCksum);
1895 if( aCksum[0]!=h1.aCksum[0] || aCksum[1]!=h1.aCksum[1] ){
1896 return 1; /* Checksum does not match */
1897 }
1898  
1899 if( memcmp(&pWal->hdr, &h1, sizeof(WalIndexHdr)) ){
1900 *pChanged = 1;
1901 memcpy(&pWal->hdr, &h1, sizeof(WalIndexHdr));
1902 pWal->szPage = (pWal->hdr.szPage&0xfe00) + ((pWal->hdr.szPage&0x0001)<<16);
1903 testcase( pWal->szPage<=32768 );
1904 testcase( pWal->szPage>=65536 );
1905 }
1906  
1907 /* The header was successfully read. Return zero. */
1908 return 0;
1909 }
1910  
1911 /*
1912 ** Read the wal-index header from the wal-index and into pWal->hdr.
1913 ** If the wal-header appears to be corrupt, try to reconstruct the
1914 ** wal-index from the WAL before returning.
1915 **
1916 ** Set *pChanged to 1 if the wal-index header value in pWal->hdr is
1917 ** changed by this opertion. If pWal->hdr is unchanged, set *pChanged
1918 ** to 0.
1919 **
1920 ** If the wal-index header is successfully read, return SQLITE_OK.
1921 ** Otherwise an SQLite error code.
1922 */
1923 static int walIndexReadHdr(Wal *pWal, int *pChanged){
1924 int rc; /* Return code */
1925 int badHdr; /* True if a header read failed */
1926 volatile u32 *page0; /* Chunk of wal-index containing header */
1927  
1928 /* Ensure that page 0 of the wal-index (the page that contains the
1929 ** wal-index header) is mapped. Return early if an error occurs here.
1930 */
1931 Debug.Assert( pChanged );
1932 rc = walIndexPage(pWal, 0, &page0);
1933 if( rc!=SQLITE_OK ){
1934 return rc;
1935 };
1936 Debug.Assert( page0 || pWal->writeLock==0 );
1937  
1938 /* If the first page of the wal-index has been mapped, try to read the
1939 ** wal-index header immediately, without holding any lock. This usually
1940 ** works, but may fail if the wal-index header is corrupt or currently
1941 ** being modified by another thread or process.
1942 */
1943 badHdr = (page0 ? walIndexTryHdr(pWal, pChanged) : 1);
1944  
1945 /* If the first attempt failed, it might have been due to a race
1946 ** with a writer. So get a WRITE lock and try again.
1947 */
1948 Debug.Assert( badHdr==0 || pWal->writeLock==0 );
1949 if( badHdr ){
1950 if( pWal->readOnly & WAL_SHM_RDONLY ){
1951 if( SQLITE_OK==(rc = walLockShared(pWal, WAL_WRITE_LOCK)) ){
1952 walUnlockShared(pWal, WAL_WRITE_LOCK);
1953 rc = SQLITE_READONLY_RECOVERY;
1954 }
1955 }else if( SQLITE_OK==(rc = walLockExclusive(pWal, WAL_WRITE_LOCK, 1)) ){
1956 pWal->writeLock = 1;
1957 if( SQLITE_OK==(rc = walIndexPage(pWal, 0, &page0)) ){
1958 badHdr = walIndexTryHdr(pWal, pChanged);
1959 if( badHdr ){
1960 /* If the wal-index header is still malformed even while holding
1961 ** a WRITE lock, it can only mean that the header is corrupted and
1962 ** needs to be reconstructed. So run recovery to do exactly that.
1963 */
1964 rc = walIndexRecover(pWal);
1965 *pChanged = 1;
1966 }
1967 }
1968 pWal->writeLock = 0;
1969 walUnlockExclusive(pWal, WAL_WRITE_LOCK, 1);
1970 }
1971 }
1972  
1973 /* If the header is read successfully, check the version number to make
1974 ** sure the wal-index was not constructed with some future format that
1975 ** this version of SQLite cannot understand.
1976 */
1977 if( badHdr==0 && pWal->hdr.iVersion!=WALINDEX_MAX_VERSION ){
1978 rc = SQLITE_CANTOPEN_BKPT;
1979 }
1980  
1981 return rc;
1982 }
1983  
1984 /*
1985 ** This is the value that walTryBeginRead returns when it needs to
1986 ** be retried.
1987 */
1988 //#define WAL_RETRY (-1)
1989  
1990 /*
1991 ** Attempt to start a read transaction. This might fail due to a race or
1992 ** other transient condition. When that happens, it returns WAL_RETRY to
1993 ** indicate to the caller that it is safe to retry immediately.
1994 **
1995 ** On success return SQLITE_OK. On a permanent failure (such an
1996 ** I/O error or an SQLITE_BUSY because another process is running
1997 ** recovery) return a positive error code.
1998 **
1999 ** The useWal parameter is true to force the use of the WAL and disable
2000 ** the case where the WAL is bypassed because it has been completely
2001 ** checkpointed. If useWal==0 then this routine calls walIndexReadHdr()
2002 ** to make a copy of the wal-index header into pWal->hdr. If the
2003 ** wal-index header has changed, *pChanged is set to 1 (as an indication
2004 ** to the caller that the local paget cache is obsolete and needs to be
2005 ** flushed.) When useWal==1, the wal-index header is assumed to already
2006 ** be loaded and the pChanged parameter is unused.
2007 **
2008 ** The caller must set the cnt parameter to the number of prior calls to
2009 ** this routine during the current read attempt that returned WAL_RETRY.
2010 ** This routine will start taking more aggressive measures to clear the
2011 ** race conditions after multiple WAL_RETRY returns, and after an excessive
2012 ** number of errors will ultimately return SQLITE_PROTOCOL. The
2013 ** SQLITE_PROTOCOL return indicates that some other process has gone rogue
2014 ** and is not honoring the locking protocol. There is a vanishingly small
2015 ** chance that SQLITE_PROTOCOL could be returned because of a run of really
2016 ** bad luck when there is lots of contention for the wal-index, but that
2017 ** possibility is so small that it can be safely neglected, we believe.
2018 **
2019 ** On success, this routine obtains a read lock on
2020 ** WAL_READ_LOCK(pWal->readLock). The pWal->readLock integer is
2021 ** in the range 0 <= pWal->readLock < WAL_NREADER. If pWal->readLock==(-1)
2022 ** that means the Wal does not hold any read lock. The reader must not
2023 ** access any database page that is modified by a WAL frame up to and
2024 ** including frame number aReadMark[pWal->readLock]. The reader will
2025 ** use WAL frames up to and including pWal->hdr.mxFrame if pWal->readLock>0
2026 ** Or if pWal->readLock==0, then the reader will ignore the WAL
2027 ** completely and get all content directly from the database file.
2028 ** If the useWal parameter is 1 then the WAL will never be ignored and
2029 ** this routine will always set pWal->readLock>0 on success.
2030 ** When the read transaction is completed, the caller must release the
2031 ** lock on WAL_READ_LOCK(pWal->readLock) and set pWal->readLock to -1.
2032 **
2033 ** This routine uses the nBackfill and aReadMark[] fields of the header
2034 ** to select a particular WAL_READ_LOCK() that strives to let the
2035 ** checkpoint process do as much work as possible. This routine might
2036 ** update values of the aReadMark[] array in the header, but if it does
2037 ** so it takes care to hold an exclusive lock on the corresponding
2038 ** WAL_READ_LOCK() while changing values.
2039 */
2040 static int walTryBeginRead(Wal *pWal, int *pChanged, int useWal, int cnt){
2041 volatile WalCkptInfo *pInfo; /* Checkpoint information in wal-index */
2042 u32 mxReadMark; /* Largest aReadMark[] value */
2043 int mxI; /* Index of largest aReadMark[] value */
2044 int i; /* Loop counter */
2045 int rc = SQLITE_OK; /* Return code */
2046  
2047 Debug.Assert( pWal->readLock<0 ); /* Not currently locked */
2048  
2049 /* Take steps to avoid spinning forever if there is a protocol error.
2050 **
2051 ** Circumstances that cause a RETRY should only last for the briefest
2052 ** instances of time. No I/O or other system calls are done while the
2053 ** locks are held, so the locks should not be held for very long. But
2054 ** if we are unlucky, another process that is holding a lock might get
2055 ** paged out or take a page-fault that is time-consuming to resolve,
2056 ** during the few nanoseconds that it is holding the lock. In that case,
2057 ** it might take longer than normal for the lock to free.
2058 **
2059 ** After 5 RETRYs, we begin calling sqlite3OsSleep(). The first few
2060 ** calls to sqlite3OsSleep() have a delay of 1 microsecond. Really this
2061 ** is more of a scheduler yield than an actual delay. But on the 10th
2062 ** an subsequent retries, the delays start becoming longer and longer,
2063 ** so that on the 100th (and last) RETRY we delay for 21 milliseconds.
2064 ** The total delay time before giving up is less than 1 second.
2065 */
2066 if( cnt>5 ){
2067 int nDelay = 1; /* Pause time in microseconds */
2068 if( cnt>100 ){
2069 VVA_ONLY( pWal->lockError = 1; )
2070 return SQLITE_PROTOCOL;
2071 }
2072 if( cnt>=10 ) nDelay = (cnt-9)*238; /* Max delay 21ms. Total delay 996ms */
2073 sqlite3OsSleep(pWal->pVfs, nDelay);
2074 }
2075  
2076 if( null==useWal ){
2077 rc = walIndexReadHdr(pWal, pChanged);
2078 if( rc==SQLITE_BUSY ){
2079 /* If there is not a recovery running in another thread or process
2080 ** then convert BUSY errors to WAL_RETRY. If recovery is known to
2081 ** be running, convert BUSY to BUSY_RECOVERY. There is a race here
2082 ** which might cause WAL_RETRY to be returned even if BUSY_RECOVERY
2083 ** would be technically correct. But the race is benign since with
2084 ** WAL_RETRY this routine will be called again and will probably be
2085 ** right on the second iteration.
2086 */
2087 if( pWal->apWiData[0]==0 ){
2088 /* This branch is taken when the xShmMap() method returns SQLITE_BUSY.
2089 ** We assume this is a transient condition, so return WAL_RETRY. The
2090 ** xShmMap() implementation used by the default unix and win32 VFS
2091 ** modules may return SQLITE_BUSY due to a race condition in the
2092 ** code that determines whether or not the shared-memory region
2093 ** must be zeroed before the requested page is returned.
2094 */
2095 rc = WAL_RETRY;
2096 }else if( SQLITE_OK==(rc = walLockShared(pWal, WAL_RECOVER_LOCK)) ){
2097 walUnlockShared(pWal, WAL_RECOVER_LOCK);
2098 rc = WAL_RETRY;
2099 }else if( rc==SQLITE_BUSY ){
2100 rc = SQLITE_BUSY_RECOVERY;
2101 }
2102 }
2103 if( rc!=SQLITE_OK ){
2104 return rc;
2105 }
2106 }
2107  
2108 pInfo = walCkptInfo(pWal);
2109 if( null==useWal && pInfo->nBackfill==pWal->hdr.mxFrame ){
2110 /* The WAL has been completely backfilled (or it is empty).
2111 ** and can be safely ignored.
2112 */
2113 rc = walLockShared(pWal, WAL_READ_LOCK(0));
2114 walShmBarrier(pWal);
2115 if( rc==SQLITE_OK ){
2116 if( memcmp((void )walIndexHdr(pWal), &pWal->hdr, sizeof(WalIndexHdr)) ){
2117 /* It is not safe to allow the reader to continue here if frames
2118 ** may have been appended to the log before READ_LOCK(0) was obtained.
2119 ** When holding READ_LOCK(0), the reader ignores the entire log file,
2120 ** which implies that the database file contains a trustworthy
2121 ** snapshoT. Since holding READ_LOCK(0) prevents a checkpoint from
2122 ** happening, this is usually correct.
2123 **
2124 ** However, if frames have been appended to the log (or if the log
2125 ** is wrapped and written for that matter) before the READ_LOCK(0)
2126 ** is obtained, that is not necessarily true. A checkpointer may
2127 ** have started to backfill the appended frames but crashed before
2128 ** it finished. Leaving a corrupt image in the database file.
2129 */
2130 walUnlockShared(pWal, WAL_READ_LOCK(0));
2131 return WAL_RETRY;
2132 }
2133 pWal->readLock = 0;
2134 return SQLITE_OK;
2135 }else if( rc!=SQLITE_BUSY ){
2136 return rc;
2137 }
2138 }
2139  
2140 /* If we get this far, it means that the reader will want to use
2141 ** the WAL to get at content from recent commits. The job now is
2142 ** to select one of the aReadMark[] entries that is closest to
2143 ** but not exceeding pWal->hdr.mxFrame and lock that entry.
2144 */
2145 mxReadMark = 0;
2146 mxI = 0;
2147 for(i=1; i<WAL_NREADER; i++){
2148 u32 thisMark = pInfo->aReadMark[i];
2149 if( mxReadMark<=thisMark && thisMark<=pWal->hdr.mxFrame ){
2150 Debug.Assert( thisMark!=READMARK_NOT_USED );
2151 mxReadMark = thisMark;
2152 mxI = i;
2153 }
2154 }
2155 /* There was once an "if" here. The extra "{" is to preserve indentation. */
2156 {
2157 if( (pWal->readOnly & WAL_SHM_RDONLY)==0
2158 && (mxReadMark<pWal->hdr.mxFrame || mxI==0)
2159 ){
2160 for(i=1; i<WAL_NREADER; i++){
2161 rc = walLockExclusive(pWal, WAL_READ_LOCK(i), 1);
2162 if( rc==SQLITE_OK ){
2163 mxReadMark = pInfo->aReadMark[i] = pWal->hdr.mxFrame;
2164 mxI = i;
2165 walUnlockExclusive(pWal, WAL_READ_LOCK(i), 1);
2166 break;
2167 }else if( rc!=SQLITE_BUSY ){
2168 return rc;
2169 }
2170 }
2171 }
2172 if( mxI==0 ){
2173 Debug.Assert( rc==SQLITE_BUSY || (pWal->readOnly & WAL_SHM_RDONLY)!=0 );
2174 return rc==SQLITE_BUSY ? WAL_RETRY : SQLITE_READONLY_CANTLOCK;
2175 }
2176  
2177 rc = walLockShared(pWal, WAL_READ_LOCK(mxI));
2178 if( rc ){
2179 return rc==SQLITE_BUSY ? WAL_RETRY : rc;
2180 }
2181 /* Now that the read-lock has been obtained, check that neither the
2182 ** value in the aReadMark[] array or the contents of the wal-index
2183 ** header have changed.
2184 **
2185 ** It is necessary to check that the wal-index header did not change
2186 ** between the time it was read and when the shared-lock was obtained
2187 ** on WAL_READ_LOCK(mxI) was obtained to account for the possibility
2188 ** that the log file may have been wrapped by a writer, or that frames
2189 ** that occur later in the log than pWal->hdr.mxFrame may have been
2190 ** copied into the database by a checkpointer. If either of these things
2191 ** happened, then reading the database with the current value of
2192 ** pWal->hdr.mxFrame risks reading a corrupted snapshot. So, retry
2193 ** instead.
2194 **
2195 ** This does not guarantee that the copy of the wal-index header is up to
2196 ** date before proceeding. That would not be possible without somehow
2197 ** blocking writers. It only guarantees that a dangerous checkpoint or
2198 ** log-wrap (either of which would require an exclusive lock on
2199 ** WAL_READ_LOCK(mxI)) has not occurred since the snapshot was valid.
2200 */
2201 walShmBarrier(pWal);
2202 if( pInfo->aReadMark[mxI]!=mxReadMark
2203 || memcmp((void )walIndexHdr(pWal), &pWal->hdr, sizeof(WalIndexHdr))
2204 ){
2205 walUnlockShared(pWal, WAL_READ_LOCK(mxI));
2206 return WAL_RETRY;
2207 }else{
2208 Debug.Assert( mxReadMark<=pWal->hdr.mxFrame );
2209 pWal->readLock = (i16)mxI;
2210 }
2211 }
2212 return rc;
2213 }
2214  
2215 /*
2216 ** Begin a read transaction on the database.
2217 **
2218 ** This routine used to be called sqlite3OpenSnapshot() and with good reason:
2219 ** it takes a snapshot of the state of the WAL and wal-index for the current
2220 ** instant in time. The current thread will continue to use this snapshot.
2221 ** Other threads might append new content to the WAL and wal-index but
2222 ** that extra content is ignored by the current thread.
2223 **
2224 ** If the database contents have changes since the previous read
2225 ** transaction, then *pChanged is set to 1 before returning. The
2226 ** Pager layer will use this to know that is cache is stale and
2227 ** needs to be flushed.
2228 */
2229 int sqlite3WalBeginReadTransaction(Wal *pWal, int *pChanged){
2230 int rc; /* Return code */
2231 int cnt = 0; /* Number of TryBeginRead attempts */
2232  
2233 do{
2234 rc = walTryBeginRead(pWal, pChanged, 0, ++cnt);
2235 }while( rc==WAL_RETRY );
2236 testcase( (rc&0xff)==SQLITE_BUSY );
2237 testcase( (rc&0xff)==SQLITE_IOERR );
2238 testcase( rc==SQLITE_PROTOCOL );
2239 testcase( rc==SQLITE_OK );
2240 return rc;
2241 }
2242  
2243 /*
2244 ** Finish with a read transaction. All this does is release the
2245 ** read-lock.
2246 */
2247 void sqlite3WalEndReadTransaction(Wal *pWal){
2248 sqlite3WalEndWriteTransaction(pWal);
2249 if( pWal->readLock>=0 ){
2250 walUnlockShared(pWal, WAL_READ_LOCK(pWal->readLock));
2251 pWal->readLock = -1;
2252 }
2253 }
2254  
2255 /*
2256 ** Read a page from the WAL, if it is present in the WAL and if the
2257 ** current read transaction is configured to use the WAL.
2258 **
2259 ** The *pInWal is set to 1 if the requested page is in the WAL and
2260 ** has been loaded. Or *pInWal is set to 0 if the page was not in
2261 ** the WAL and needs to be read out of the database.
2262 */
2263 int sqlite3WalRead(
2264 Wal *pWal, /* WAL handle */
2265 Pgno pgno, /* Database page number to read data for */
2266 int *pInWal, /* OUT: True if data is read from WAL */
2267 int nOut, /* Size of buffer pOut in bytes */
2268 u8 *pout /* Buffer to write page data to */
2269 ){
2270 u32 iRead = 0; /* If !=0, WAL frame to return data from */
2271 u32 iLast = pWal->hdr.mxFrame; /* Last page in WAL for this reader */
2272 int iHash; /* Used to loop through N hash tables */
2273  
2274 /* This routine is only be called from within a read transaction. */
2275 Debug.Assert( pWal->readLock>=0 || pWal->lockError );
2276  
2277 /* If the "last page" field of the wal-index header snapshot is 0, then
2278 ** no data will be read from the wal under any circumstances. Return early
2279 ** in this case as an optimization. Likewise, if pWal->readLock==0,
2280 ** then the WAL is ignored by the reader so return early, as if the
2281 ** WAL were empty.
2282 */
2283 if( iLast==0 || pWal->readLock==0 ){
2284 *pInWal = 0;
2285 return SQLITE_OK;
2286 }
2287  
2288 /* Search the hash table or tables for an entry matching page number
2289 ** pgno. Each iteration of the following for() loop searches one
2290 ** hash table (each hash table indexes up to HASHTABLE_NPAGE frames).
2291 **
2292 ** This code might run concurrently to the code in walIndexAppend()
2293 ** that adds entries to the wal-index (and possibly to this hash
2294 ** table). This means the value just read from the hash
2295 ** slot (aHash[iKey]) may have been added before or after the
2296 ** current read transaction was opened. Values added after the
2297 ** read transaction was opened may have been written incorrectly -
2298 ** i.e. these slots may contain garbage data. However, we assume
2299 ** that any slots written before the current read transaction was
2300 ** opened remain unmodified.
2301 **
2302 ** For the reasons above, the if(...) condition featured in the inner
2303 ** loop of the following block is more stringent that would be required
2304 ** if we had exclusive access to the hash-table:
2305 **
2306 ** (aPgno[iFrame]==pgno):
2307 ** This condition filters out normal hash-table collisions.
2308 **
2309 ** (iFrame<=iLast):
2310 ** This condition filters out entries that were added to the hash
2311 ** table after the current read-transaction had started.
2312 */
2313 for(iHash=walFramePage(iLast); iHash>=0 && iRead==0; iHash--){
2314 volatile ht_slot *aHash; /* Pointer to hash table */
2315 volatile u32 *aPgno; /* Pointer to array of page numbers */
2316 u32 iZero; /* Frame number corresponding to aPgno[0] */
2317 int iKey; /* Hash slot index */
2318 int nCollide; /* Number of hash collisions remaining */
2319 int rc; /* Error code */
2320  
2321 rc = walHashGet(pWal, iHash, &aHash, &aPgno, &iZero);
2322 if( rc!=SQLITE_OK ){
2323 return rc;
2324 }
2325 nCollide = HASHTABLE_NSLOT;
2326 for(iKey=walHash(pgno); aHash[iKey]; iKey=walNextHash(iKey)){
2327 u32 iFrame = aHash[iKey] + iZero;
2328 if( iFrame<=iLast && aPgno[aHash[iKey]]==pgno ){
2329 Debug.Assert( iFrame>iRead );
2330 iRead = iFrame;
2331 }
2332 if( (nCollide--)==0 ){
2333 return SQLITE_CORRUPT_BKPT;
2334 }
2335 }
2336 }
2337  
2338 #if SQLITE_ENABLE_EXPENSIVE_ASSERT
2339 /* If expensive Debug.Assert() statements are available, do a linear search
2340 ** of the wal-index file content. Make sure the results agree with the
2341 ** result obtained using the hash indexes above. */
2342 {
2343 u32 iRead2 = 0;
2344 u32 iTest;
2345 for(iTest=iLast; iTest>0; iTest--){
2346 if( walFramePgno(pWal, iTest)==pgno ){
2347 iRead2 = iTest;
2348 break;
2349 }
2350 }
2351 Debug.Assert( iRead==iRead2 );
2352 }
2353 #endif
2354  
2355 /* If iRead is non-zero, then it is the log frame number that contains the
2356 ** required page. Read and return data from the log file.
2357 */
2358 if( iRead ){
2359 int sz;
2360 i64 iOffset;
2361 sz = pWal->hdr.szPage;
2362 sz = (pWal->hdr.szPage&0xfe00) + ((pWal->hdr.szPage&0x0001)<<16);
2363 testcase( sz<=32768 );
2364 testcase( sz>=65536 );
2365 iOffset = walFrameOffset(iRead, sz) + WAL_FRAME_HDRSIZE;
2366 *pInWal = 1;
2367 /* testcase( IS_BIG_INT(iOffset) ); // requires a 4GiB WAL */
2368 return sqlite3OsRead(pWal->pWalFd, pOut, nOut, iOffset);
2369 }
2370  
2371 *pInWal = 0;
2372 return SQLITE_OK;
2373 }
2374  
2375  
2376 /*
2377 ** Return the size of the database in pages (or zero, if unknown).
2378 */
2379 Pgno sqlite3WalDbsize(Wal *pWal){
2380 if( pWal && ALWAYS(pWal->readLock>=0) ){
2381 return pWal->hdr.nPage;
2382 }
2383 return 0;
2384 }
2385  
2386  
2387 /*
2388 ** This function starts a write transaction on the WAL.
2389 **
2390 ** A read transaction must have already been started by a prior call
2391 ** to sqlite3WalBeginReadTransaction().
2392 **
2393 ** If another thread or process has written into the database since
2394 ** the read transaction was started, then it is not possible for this
2395 ** thread to write as doing so would cause a fork. So this routine
2396 ** returns SQLITE_BUSY in that case and no write transaction is started.
2397 **
2398 ** There can only be a single writer active at a time.
2399 */
2400 int sqlite3WalBeginWriteTransaction(Wal *pWal){
2401 int rc;
2402  
2403 /* Cannot start a write transaction without first holding a read
2404 ** transaction. */
2405 Debug.Assert( pWal->readLock>=0 );
2406  
2407 if( pWal->readOnly ){
2408 return SQLITE_READONLY;
2409 }
2410  
2411 /* Only one writer allowed at a time. Get the write lock. Return
2412 ** SQLITE_BUSY if unable.
2413 */
2414 rc = walLockExclusive(pWal, WAL_WRITE_LOCK, 1);
2415 if( rc ){
2416 return rc;
2417 }
2418 pWal->writeLock = 1;
2419  
2420 /* If another connection has written to the database file since the
2421 ** time the read transaction on this connection was started, then
2422 ** the write is disallowed.
2423 */
2424 if( memcmp(&pWal->hdr, (void )walIndexHdr(pWal), sizeof(WalIndexHdr))!=0 ){
2425 walUnlockExclusive(pWal, WAL_WRITE_LOCK, 1);
2426 pWal->writeLock = 0;
2427 rc = SQLITE_BUSY;
2428 }
2429  
2430 return rc;
2431 }
2432  
2433 /*
2434 ** End a write transaction. The commit has already been done. This
2435 ** routine merely releases the lock.
2436 */
2437 int sqlite3WalEndWriteTransaction(Wal *pWal){
2438 if( pWal->writeLock ){
2439 walUnlockExclusive(pWal, WAL_WRITE_LOCK, 1);
2440 pWal->writeLock = 0;
2441 }
2442 return SQLITE_OK;
2443 }
2444  
2445 /*
2446 ** If any data has been written (but not committed) to the log file, this
2447 ** function moves the write-pointer back to the start of the transaction.
2448 **
2449 ** Additionally, the callback function is invoked for each frame written
2450 ** to the WAL since the start of the transaction. If the callback returns
2451 ** other than SQLITE_OK, it is not invoked again and the error code is
2452 ** returned to the caller.
2453 **
2454 ** Otherwise, if the callback function does not return an error, this
2455 ** function returns SQLITE_OK.
2456 */
2457 int sqlite3WalUndo(Wal *pWal, int (*xUndo)(void *, Pgno), object *pUndoCtx){
2458 int rc = SQLITE_OK;
2459 if( ALWAYS(pWal->writeLock) ){
2460 Pgno iMax = pWal->hdr.mxFrame;
2461 Pgno iFrame;
2462  
2463 /* Restore the clients cache of the wal-index header to the state it
2464 ** was in before the client began writing to the database.
2465 */
2466 memcpy(&pWal->hdr, (void )walIndexHdr(pWal), sizeof(WalIndexHdr));
2467  
2468 for(iFrame=pWal->hdr.mxFrame+1;
2469 ALWAYS(rc==SQLITE_OK) && iFrame<=iMax;
2470 iFrame++
2471 ){
2472 /* This call cannot fail. Unless the page for which the page number
2473 ** is passed as the second argument is (a) in the cache and
2474 ** (b) has an outstanding reference, then xUndo is either a no-op
2475 ** (if (a) is false) or simply expels the page from the cache (if (b)
2476 ** is false).
2477 **
2478 ** If the upper layer is doing a rollback, it is guaranteed that there
2479 ** are no outstanding references to any page other than page 1. And
2480 ** page 1 is never written to the log until the transaction is
2481 ** committed. As a result, the call to xUndo may not fail.
2482 */
2483 Debug.Assert( walFramePgno(pWal, iFrame)!=1 );
2484 rc = xUndo(pUndoCtx, walFramePgno(pWal, iFrame));
2485 }
2486 walCleanupHash(pWal);
2487 }
2488 Debug.Assert( rc==SQLITE_OK );
2489 return rc;
2490 }
2491  
2492 /*
2493 ** Argument aWalData must point to an array of WAL_SAVEPOINT_NDATA u32
2494 ** values. This function populates the array with values required to
2495 ** "rollback" the write position of the WAL handle back to the current
2496 ** point in the event of a savepoint rollback (via WalSavepointUndo()).
2497 */
2498 void sqlite3WalSavepoint(Wal *pWal, u32 *aWalData){
2499 Debug.Assert( pWal->writeLock );
2500 aWalData[0] = pWal->hdr.mxFrame;
2501 aWalData[1] = pWal->hdr.aFrameCksum[0];
2502 aWalData[2] = pWal->hdr.aFrameCksum[1];
2503 aWalData[3] = pWal->nCkpt;
2504 }
2505  
2506 /*
2507 ** Move the write position of the WAL back to the point identified by
2508 ** the values in the aWalData[] array. aWalData must point to an array
2509 ** of WAL_SAVEPOINT_NDATA u32 values that has been previously populated
2510 ** by a call to WalSavepoint().
2511 */
2512 int sqlite3WalSavepointUndo(Wal *pWal, u32 *aWalData){
2513 int rc = SQLITE_OK;
2514  
2515 Debug.Assert( pWal->writeLock );
2516 Debug.Assert( aWalData[3]!=pWal->nCkpt || aWalData[0]<=pWal->hdr.mxFrame );
2517  
2518 if( aWalData[3]!=pWal->nCkpt ){
2519 /* This savepoint was opened immediately after the write-transaction
2520 ** was started. Right after that, the writer decided to wrap around
2521 ** to the start of the log. Update the savepoint values to match.
2522 */
2523 aWalData[0] = 0;
2524 aWalData[3] = pWal->nCkpt;
2525 }
2526  
2527 if( aWalData[0]<pWal->hdr.mxFrame ){
2528 pWal->hdr.mxFrame = aWalData[0];
2529 pWal->hdr.aFrameCksum[0] = aWalData[1];
2530 pWal->hdr.aFrameCksum[1] = aWalData[2];
2531 walCleanupHash(pWal);
2532 }
2533  
2534 return rc;
2535 }
2536  
2537 /*
2538 ** This function is called just before writing a set of frames to the log
2539 ** file (see sqlite3WalFrames()). It checks to see if, instead of appending
2540 ** to the current log file, it is possible to overwrite the start of the
2541 ** existing log file with the new frames (i.e. "reset" the log). If so,
2542 ** it sets pWal->hdr.mxFrame to 0. Otherwise, pWal->hdr.mxFrame is left
2543 ** unchanged.
2544 **
2545 ** SQLITE_OK is returned if no error is encountered (regardless of whether
2546 ** or not pWal->hdr.mxFrame is modified). An SQLite error code is returned
2547 ** if an error occurs.
2548 */
2549 static int walRestartLog(Wal *pWal){
2550 int rc = SQLITE_OK;
2551 int cnt;
2552  
2553 if( pWal->readLock==0 ){
2554 volatile WalCkptInfo *pInfo = walCkptInfo(pWal);
2555 Debug.Assert( pInfo->nBackfill==pWal->hdr.mxFrame );
2556 if( pInfo->nBackfill>0 ){
2557 u32 salt1;
2558 sqlite3_randomness(4, &salt1);
2559 rc = walLockExclusive(pWal, WAL_READ_LOCK(1), WAL_NREADER-1);
2560 if( rc==SQLITE_OK ){
2561 /* If all readers are using WAL_READ_LOCK(0) (in other words if no
2562 ** readers are currently using the WAL), then the transactions
2563 ** frames will overwrite the start of the existing log. Update the
2564 ** wal-index header to reflect this.
2565 **
2566 ** In theory it would be Ok to update the cache of the header only
2567 ** at this point. But updating the actual wal-index header is also
2568 ** safe and means there is no special case for sqlite3WalUndo()
2569 ** to handle if this transaction is rolled back.
2570 */
2571 int i; /* Loop counter */
2572 u32 *aSalt = pWal->hdr.aSalt; /* Big-endian salt values */
2573  
2574 /* Limit the size of WAL file if the journal_size_limit PRAGMA is
2575 ** set to a non-negative value. Log errors encountered
2576 ** during the truncation attempt. */
2577 if( pWal->mxWalSize>=0 ){
2578 i64 sz;
2579 int rx;
2580 sqlite3BeginBenignMalloc();
2581 rx = sqlite3OsFileSize(pWal->pWalFd, &sz);
2582 if( rx==SQLITE_OK && (sz > pWal->mxWalSize) ){
2583 rx = sqlite3OsTruncate(pWal->pWalFd, pWal->mxWalSize);
2584 }
2585 sqlite3EndBenignMalloc();
2586 if( rx ){
2587 sqlite3_log(rx, "cannot limit WAL size: %s", pWal->zWalName);
2588 }
2589 }
2590  
2591 pWal->nCkpt++;
2592 pWal->hdr.mxFrame = 0;
2593 sqlite3Put4byte((u8)&aSalt[0], 1 + sqlite3Get4byte((u8)&aSalt[0]));
2594 aSalt[1] = salt1;
2595 walIndexWriteHdr(pWal);
2596 pInfo->nBackfill = 0;
2597 for(i=1; i<WAL_NREADER; i++) pInfo->aReadMark[i] = READMARK_NOT_USED;
2598 Debug.Assert( pInfo->aReadMark[0]==0 );
2599 walUnlockExclusive(pWal, WAL_READ_LOCK(1), WAL_NREADER-1);
2600 }else if( rc!=SQLITE_BUSY ){
2601 return rc;
2602 }
2603 }
2604 walUnlockShared(pWal, WAL_READ_LOCK(0));
2605 pWal->readLock = -1;
2606 cnt = 0;
2607 do{
2608 int notUsed;
2609 rc = walTryBeginRead(pWal, &notUsed, 1, ++cnt);
2610 }while( rc==WAL_RETRY );
2611 Debug.Assert( (rc&0xff)!=SQLITE_BUSY ); /* BUSY not possible when useWal==1 */
2612 testcase( (rc&0xff)==SQLITE_IOERR );
2613 testcase( rc==SQLITE_PROTOCOL );
2614 testcase( rc==SQLITE_OK );
2615 }
2616 return rc;
2617 }
2618  
2619 /*
2620 ** Write a set of frames to the log. The caller must hold the write-lock
2621 ** on the log file (obtained using sqlite3WalBeginWriteTransaction()).
2622 */
2623 int sqlite3WalFrames(
2624 Wal *pWal, /* Wal handle to write to */
2625 int szPage, /* Database page-size in bytes */
2626 PgHdr *pList, /* List of dirty pages to write */
2627 Pgno nTruncate, /* Database size after this commit */
2628 int isCommit, /* True if this is a commit */
2629 int sync_flags /* Flags to pass to OsSync() (or 0) */
2630 ){
2631 int rc; /* Used to catch return codes */
2632 u32 iFrame; /* Next frame address */
2633 u8 aFrame[WAL_FRAME_HDRSIZE]; /* Buffer to assemble frame-header in */
2634 PgHdr *p; /* Iterator to run through pList with. */
2635 PgHdr *pLast = 0; /* Last frame in list */
2636 int nLast = 0; /* Number of extra copies of last page */
2637  
2638 Debug.Assert( pList );
2639 Debug.Assert( pWal->writeLock );
2640  
2641 #if (SQLITE_TEST) && (SQLITE_DEBUG)
2642 { int cnt; for(cnt=0, p=pList; p; p=p->pDirty, cnt++){}
2643 WALTRACE(("WAL%p: frame write begin. %d frames. mxFrame=%d. %s\n",
2644 pWal, cnt, pWal->hdr.mxFrame, isCommit ? "Commit" : "Spill"));
2645 }
2646 #endif
2647  
2648 /* See if it is possible to write these frames into the start of the
2649 ** log file, instead of appending to it at pWal->hdr.mxFrame.
2650 */
2651 if( SQLITE_OK!=(rc = walRestartLog(pWal)) ){
2652 return rc;
2653 }
2654  
2655 /* If this is the first frame written into the log, write the WAL
2656 ** header to the start of the WAL file. See comments at the top of
2657 ** this source file for a description of the WAL header format.
2658 */
2659 iFrame = pWal->hdr.mxFrame;
2660 if( iFrame==0 ){
2661 u8 aWalHdr[WAL_HDRSIZE]; /* Buffer to assemble wal-header in */
2662 u32 aCksum[2]; /* Checksum for wal-header */
2663  
2664 sqlite3Put4byte(&aWalHdr[0], (WAL_MAGIC | SQLITE_BIGENDIAN));
2665 sqlite3Put4byte(&aWalHdr[4], WAL_MAX_VERSION);
2666 sqlite3Put4byte(&aWalHdr[8], szPage);
2667 sqlite3Put4byte(&aWalHdr[12], pWal->nCkpt);
2668 sqlite3_randomness(8, pWal->hdr.aSalt);
2669 memcpy(&aWalHdr[16], pWal->hdr.aSalt, 8);
2670 walChecksumBytes(1, aWalHdr, WAL_HDRSIZE-2*4, 0, aCksum);
2671 sqlite3Put4byte(&aWalHdr[24], aCksum[0]);
2672 sqlite3Put4byte(&aWalHdr[28], aCksum[1]);
2673  
2674 pWal->szPage = szPage;
2675 pWal->hdr.bigEndCksum = SQLITE_BIGENDIAN;
2676 pWal->hdr.aFrameCksum[0] = aCksum[0];
2677 pWal->hdr.aFrameCksum[1] = aCksum[1];
2678  
2679 rc = sqlite3OsWrite(pWal->pWalFd, aWalHdr, sizeof(aWalHdr), 0);
2680 WALTRACE(("WAL%p: wal-header write %s\n", pWal, rc ? "failed" : "ok"));
2681 if( rc!=SQLITE_OK ){
2682 return rc;
2683 }
2684 }
2685 Debug.Assert( (int)pWal->szPage==szPage );
2686  
2687 /* Write the log file. */
2688 for(p=pList; p; p=p->pDirty){
2689 u32 nDbsize; /* Db-size field for frame header */
2690 i64 iOffset; /* Write offset in log file */
2691 void *pData;
2692  
2693 iOffset = walFrameOffset(++iFrame, szPage);
2694 /* testcase( IS_BIG_INT(iOffset) ); // requires a 4GiB WAL */
2695  
2696 /* Populate and write the frame header */
2697 nDbsize = (isCommit && p->pDirty==0) ? nTruncate : 0;
2698 #if (SQLITE_HAS_CODEC)
2699 if( (pData = sqlite3PagerCodec(p))==0 ) return SQLITE_NOMEM;
2700 #else
2701 pData = p->pData;
2702 #endif
2703 walEncodeFrame(pWal, p->pgno, nDbsize, pData, aFrame);
2704 rc = sqlite3OsWrite(pWal->pWalFd, aFrame, sizeof(aFrame), iOffset);
2705 if( rc!=SQLITE_OK ){
2706 return rc;
2707 }
2708  
2709 /* Write the page data */
2710 rc = sqlite3OsWrite(pWal->pWalFd, pData, szPage, iOffset+sizeof(aFrame));
2711 if( rc!=SQLITE_OK ){
2712 return rc;
2713 }
2714 pLast = p;
2715 }
2716  
2717 /* Sync the log file if the 'isSync' flag was specified. */
2718 if( sync_flags ){
2719 i64 iSegment = sqlite3OsSectorSize(pWal->pWalFd);
2720 i64 iOffset = walFrameOffset(iFrame+1, szPage);
2721  
2722 Debug.Assert( isCommit );
2723 Debug.Assert( iSegment>0 );
2724  
2725 iSegment = (((iOffset+iSegment-1)/iSegment) * iSegment);
2726 while( iOffset<iSegment ){
2727 void *pData;
2728 #if (SQLITE_HAS_CODEC)
2729 if( (pData = sqlite3PagerCodec(pLast))==0 ) return SQLITE_NOMEM;
2730 #else
2731 pData = pLast->pData;
2732 #endif
2733 walEncodeFrame(pWal, pLast->pgno, nTruncate, pData, aFrame);
2734 /* testcase( IS_BIG_INT(iOffset) ); // requires a 4GiB WAL */
2735 rc = sqlite3OsWrite(pWal->pWalFd, aFrame, sizeof(aFrame), iOffset);
2736 if( rc!=SQLITE_OK ){
2737 return rc;
2738 }
2739 iOffset += WAL_FRAME_HDRSIZE;
2740 rc = sqlite3OsWrite(pWal->pWalFd, pData, szPage, iOffset);
2741 if( rc!=SQLITE_OK ){
2742 return rc;
2743 }
2744 nLast++;
2745 iOffset += szPage;
2746 }
2747  
2748 rc = sqlite3OsSync(pWal->pWalFd, sync_flags);
2749 }
2750  
2751 /* Append data to the wal-index. It is not necessary to lock the
2752 ** wal-index to do this as the SQLITE_SHM_WRITE lock held on the wal-index
2753 ** guarantees that there are no other writers, and no data that may
2754 ** be in use by existing readers is being overwritten.
2755 */
2756 iFrame = pWal->hdr.mxFrame;
2757 for(p=pList; p && rc==SQLITE_OK; p=p->pDirty){
2758 iFrame++;
2759 rc = walIndexAppend(pWal, iFrame, p->pgno);
2760 }
2761 while( nLast>0 && rc==SQLITE_OK ){
2762 iFrame++;
2763 nLast--;
2764 rc = walIndexAppend(pWal, iFrame, pLast->pgno);
2765 }
2766  
2767 if( rc==SQLITE_OK ){
2768 /* Update the private copy of the header. */
2769 pWal->hdr.szPage = (u16)((szPage&0xff00) | (szPage>>16));
2770 testcase( szPage<=32768 );
2771 testcase( szPage>=65536 );
2772 pWal->hdr.mxFrame = iFrame;
2773 if( isCommit ){
2774 pWal->hdr.iChange++;
2775 pWal->hdr.nPage = nTruncate;
2776 }
2777 /* If this is a commit, update the wal-index header too. */
2778 if( isCommit ){
2779 walIndexWriteHdr(pWal);
2780 pWal->iCallback = iFrame;
2781 }
2782 }
2783  
2784 WALTRACE(("WAL%p: frame write %s\n", pWal, rc ? "failed" : "ok"));
2785 return rc;
2786 }
2787  
2788 /*
2789 ** This routine is called to implement sqlite3_wal_checkpoint() and
2790 ** related interfaces.
2791 **
2792 ** Obtain a CHECKPOINT lock and then backfill as much information as
2793 ** we can from WAL into the database.
2794 **
2795 ** If parameter xBusy is not NULL, it is a pointer to a busy-handler
2796 ** callback. In this case this function runs a blocking checkpoint.
2797 */
2798 int sqlite3WalCheckpoint(
2799 Wal *pWal, /* Wal connection */
2800 int eMode, /* PASSIVE, FULL or RESTART */
2801 int (*xBusy)(void), /* Function to call when busy */
2802 void *pBusyArg, /* Context argument for xBusyHandler */
2803 int sync_flags, /* Flags to sync db file with (or 0) */
2804 int nBuf, /* Size of temporary buffer */
2805 u8 *zBuf, /* Temporary buffer to use */
2806 int *pnLog, /* OUT: Number of frames in WAL */
2807 int *pnCkpt /* OUT: Number of backfilled frames in WAL */
2808 ){
2809 int rc; /* Return code */
2810 int isChanged = 0; /* True if a new wal-index header is loaded */
2811 int eMode2 = eMode; /* Mode to pass to walCheckpoint() */
2812  
2813 Debug.Assert( pWal->ckptLock==0 );
2814 Debug.Assert( pWal->writeLock==0 );
2815  
2816 if( pWal->readOnly ) return SQLITE_READONLY;
2817 WALTRACE(("WAL%p: checkpoint begins\n", pWal));
2818 rc = walLockExclusive(pWal, WAL_CKPT_LOCK, 1);
2819 if( rc ){
2820 /* Usually this is SQLITE_BUSY meaning that another thread or process
2821 ** is already running a checkpoint, or maybe a recovery. But it might
2822 ** also be SQLITE_IOERR. */
2823 return rc;
2824 }
2825 pWal->ckptLock = 1;
2826  
2827 /* If this is a blocking-checkpoint, then obtain the write-lock as well
2828 ** to prevent any writers from running while the checkpoint is underway.
2829 ** This has to be done before the call to walIndexReadHdr() below.
2830 **
2831 ** If the writer lock cannot be obtained, then a passive checkpoint is
2832 ** run instead. Since the checkpointer is not holding the writer lock,
2833 ** there is no point in blocking waiting for any readers. Assuming no
2834 ** other error occurs, this function will return SQLITE_BUSY to the caller.
2835 */
2836 if( eMode!=SQLITE_CHECKPOINT_PASSIVE ){
2837 rc = walBusyLock(pWal, xBusy, pBusyArg, WAL_WRITE_LOCK, 1);
2838 if( rc==SQLITE_OK ){
2839 pWal->writeLock = 1;
2840 }else if( rc==SQLITE_BUSY ){
2841 eMode2 = SQLITE_CHECKPOINT_PASSIVE;
2842 rc = SQLITE_OK;
2843 }
2844 }
2845  
2846 /* Read the wal-index header. */
2847 if( rc==SQLITE_OK ){
2848 rc = walIndexReadHdr(pWal, &isChanged);
2849 }
2850  
2851 /* Copy data from the log to the database file. */
2852 if( rc==SQLITE_OK ){
2853 if( pWal->hdr.mxFrame && walPagesize(pWal)!=nBuf ){
2854 rc = SQLITE_CORRUPT_BKPT;
2855 }else{
2856 rc = walCheckpoint(pWal, eMode2, xBusy, pBusyArg, sync_flags, zBuf);
2857 }
2858  
2859 /* If no error occurred, set the output variables. */
2860 if( rc==SQLITE_OK || rc==SQLITE_BUSY ){
2861 if( pnLog ) *pnLog = (int)pWal->hdr.mxFrame;
2862 if( pnCkpt ) *pnCkpt = (int)(walCkptInfo(pWal)->nBackfill);
2863 }
2864 }
2865  
2866 if( isChanged ){
2867 /* If a new wal-index header was loaded before the checkpoint was
2868 ** performed, then the pager-cache associated with pWal is now
2869 ** out of date. So zero the cached wal-index header to ensure that
2870 ** next time the pager opens a snapshot on this database it knows that
2871 ** the cache needs to be reset.
2872 */
2873 memset(&pWal->hdr, 0, sizeof(WalIndexHdr));
2874 }
2875  
2876 /* Release the locks. */
2877 sqlite3WalEndWriteTransaction(pWal);
2878 walUnlockExclusive(pWal, WAL_CKPT_LOCK, 1);
2879 pWal->ckptLock = 0;
2880 WALTRACE(("WAL%p: checkpoint %s\n", pWal, rc ? "failed" : "ok"));
2881 return (rc==SQLITE_OK && eMode!=eMode2 ? SQLITE_BUSY : rc);
2882 }
2883  
2884 /* Return the value to pass to a sqlite3_wal_hook callback, the
2885 ** number of frames in the WAL at the point of the last commit since
2886 ** sqlite3WalCallback() was called. If no commits have occurred since
2887 ** the last call, then return 0.
2888 */
2889 int sqlite3WalCallback(Wal *pWal){
2890 u32 ret = 0;
2891 if( pWal ){
2892 ret = pWal->iCallback;
2893 pWal->iCallback = 0;
2894 }
2895 return (int)ret;
2896 }
2897  
2898 /*
2899 ** This function is called to change the WAL subsystem into or out
2900 ** of locking_mode=EXCLUSIVE.
2901 **
2902 ** If op is zero, then attempt to change from locking_mode=EXCLUSIVE
2903 ** into locking_mode=NORMAL. This means that we must acquire a lock
2904 ** on the pWal->readLock byte. If the WAL is already in locking_mode=NORMAL
2905 ** or if the acquisition of the lock fails, then return 0. If the
2906 ** transition out of exclusive-mode is successful, return 1. This
2907 ** operation must occur while the pager is still holding the exclusive
2908 ** lock on the main database file.
2909 **
2910 ** If op is one, then change from locking_mode=NORMAL into
2911 ** locking_mode=EXCLUSIVE. This means that the pWal->readLock must
2912 ** be released. Return 1 if the transition is made and 0 if the
2913 ** WAL is already in exclusive-locking mode - meaning that this
2914 ** routine is a no-op. The pager must already hold the exclusive lock
2915 ** on the main database file before invoking this operation.
2916 **
2917 ** If op is negative, then do a dry-run of the op==1 case but do
2918 ** not actually change anything. The pager uses this to see if it
2919 ** should acquire the database exclusive lock prior to invoking
2920 ** the op==1 case.
2921 */
2922 int sqlite3WalExclusiveMode(Wal *pWal, int op){
2923 int rc;
2924 Debug.Assert( pWal->writeLock==0 );
2925 Debug.Assert( pWal->exclusiveMode!=WAL_HEAPMEMORY_MODE || op==-1 );
2926  
2927 /* pWal->readLock is usually set, but might be -1 if there was a
2928 ** prior error while attempting to acquire are read-lock. This cannot
2929 ** happen if the connection is actually in exclusive mode (as no xShmLock
2930 ** locks are taken in this case). Nor should the pager attempt to
2931 ** upgrade to exclusive-mode following such an error.
2932 */
2933 Debug.Assert( pWal->readLock>=0 || pWal->lockError );
2934 Debug.Assert( pWal->readLock>=0 || (op<=0 && pWal->exclusiveMode==0) );
2935  
2936 if( op==0 ){
2937 if( pWal->exclusiveMode ){
2938 pWal->exclusiveMode = 0;
2939 if( walLockShared(pWal, WAL_READ_LOCK(pWal->readLock))!=SQLITE_OK ){
2940 pWal->exclusiveMode = 1;
2941 }
2942 rc = pWal->exclusiveMode==0;
2943 }else{
2944 /* Already in locking_mode=NORMAL */
2945 rc = 0;
2946 }
2947 }else if( op>0 ){
2948 Debug.Assert( pWal->exclusiveMode==0 );
2949 Debug.Assert( pWal->readLock>=0 );
2950 walUnlockShared(pWal, WAL_READ_LOCK(pWal->readLock));
2951 pWal->exclusiveMode = 1;
2952 rc = 1;
2953 }else{
2954 rc = pWal->exclusiveMode==0;
2955 }
2956 return rc;
2957 }
2958  
2959 /*
2960 ** Return true if the argument is non-NULL and the WAL module is using
2961 ** heap-memory for the wal-index. Otherwise, if the argument is NULL or the
2962 ** WAL module is using shared-memory, return false.
2963 */
2964 int sqlite3WalHeapMemory(Wal *pWal){
2965 return (pWal && pWal->exclusiveMode==WAL_HEAPMEMORY_MODE );
2966 }
2967  
2968 #endif //* #if !SQLITE_OMIT_WAL */
2969 }
2970 }