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