third_party/sqlite/sqlite-src-3080704/src/wal.c - Issue 2363173002: [sqlite] Remove obsolete reference version 3.8.7.4.

Side by Side Diff: third_party/sqlite/sqlite-src-3080704/src/wal.c

Issue 2363173002: [sqlite] Remove obsolete reference version 3.8.7.4. (Closed)

Patch Set: Created 4 years, 3 months ago

Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.

Jump to:

OLD	NEW
	(Empty)
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 and a maximum frame index M, return the index of the

146 ** last frame in the wal before frame M for page P in the WAL, or return

147 ** NULL if there are no frames for page P in the WAL prior to M.

148 **

149 ** The wal-index consists of a header region, followed by an one or

150 ** more index blocks.

151 **

152 ** The wal-index header contains the total number of frames within the WAL

153 ** in the mxFrame field.

154 **

155 ** Each index block except for the first contains information on

156 ** HASHTABLE_NPAGE frames. The first index block contains information on

157 ** HASHTABLE_NPAGE_ONE frames. The values of HASHTABLE_NPAGE_ONE and

158 ** HASHTABLE_NPAGE are selected so that together the wal-index header and

159 ** first index block are the same size as all other index blocks in the

160 ** wal-index.

161 **

162 ** Each index block contains two sections, a page-mapping that contains the

163 ** database page number associated with each wal frame, and a hash-table

164 ** that allows readers to query an index block for a specific page number.

165 ** The page-mapping is an array of HASHTABLE_NPAGE (or HASHTABLE_NPAGE_ONE

166 ** for the first index block) 32-bit page numbers. The first entry in the

167 ** first index-block contains the database page number corresponding to the

168 ** first frame in the WAL file. The first entry in the second index block

169 ** in the WAL file corresponds to the (HASHTABLE_NPAGE_ONE+1)th frame in

170 ** the log, and so on.

171 **

172 ** The last index block in a wal-index usually contains less than the full

173 ** complement of HASHTABLE_NPAGE (or HASHTABLE_NPAGE_ONE) page-numbers,

174 ** depending on the contents of the WAL file. This does not change the

175 ** allocated size of the page-mapping array - the page-mapping array merely

176 ** contains unused entries.

177 **

178 ** Even without using the hash table, the last frame for page P

179 ** can be found by scanning the page-mapping sections of each index block

180 ** starting with the last index block and moving toward the first, and

181 ** within each index block, starting at the end and moving toward the

182 ** beginning. The first entry that equals P corresponds to the frame

183 ** holding the content for that page.

184 **

185 ** The hash table consists of HASHTABLE_NSLOT 16-bit unsigned integers.

186 ** HASHTABLE_NSLOT = 2*HASHTABLE_NPAGE, and there is one entry in the

187 ** hash table for each page number in the mapping section, so the hash

188 ** table is never more than half full. The expected number of collisions

189 ** prior to finding a match is 1. Each entry of the hash table is an

190 ** 1-based index of an entry in the mapping section of the same

191 ** index block. Let K be the 1-based index of the largest entry in

192 ** the mapping section. (For index blocks other than the last, K will

193 ** always be exactly HASHTABLE_NPAGE (4096) and for the last index block

194 ** K will be (mxFrame%HASHTABLE_NPAGE).) Unused slots of the hash table

195 ** contain a value of 0.

196 **

197 ** To look for page P in the hash table, first compute a hash iKey on

198 ** P as follows:

199 **

200 ** iKey = (P * 383) % HASHTABLE_NSLOT

201 **

202 ** Then start scanning entries of the hash table, starting with iKey

203 ** (wrapping around to the beginning when the end of the hash table is

204 ** reached) until an unused hash slot is found. Let the first unused slot

205 ** be at index iUnused. (iUnused might be less than iKey if there was

206 ** wrap-around.) Because the hash table is never more than half full,

207 ** the search is guaranteed to eventually hit an unused entry. Let

208 ** iMax be the value between iKey and iUnused, closest to iUnused,

209 ** where aHash[iMax]==P. If there is no iMax entry (if there exists

210 ** no hash slot such that aHash[i]==p) then page P is not in the

211 ** current index block. Otherwise the iMax-th mapping entry of the

212 ** current index block corresponds to the last entry that references

213 ** page P.

214 **

215 ** A hash search begins with the last index block and moves toward the

216 ** first index block, looking for entries corresponding to page P. On

217 ** average, only two or three slots in each index block need to be

218 ** examined in order to either find the last entry for page P, or to

219 ** establish that no such entry exists in the block. Each index block

220 ** holds over 4000 entries. So two or three index blocks are sufficient

221 ** to cover a typical 10 megabyte WAL file, assuming 1K pages. 8 or 10

222 ** comparisons (on average) suffice to either locate a frame in the

223 ** WAL or to establish that the frame does not exist in the WAL. This

224 ** is much faster than scanning the entire 10MB WAL.

225 **

226 ** Note that entries are added in order of increasing K. Hence, one

227 ** reader might be using some value K0 and a second reader that started

228 ** at a later time (after additional transactions were added to the WAL

229 ** and to the wal-index) might be using a different value K1, where K1>K0.

230 ** Both readers can use the same hash table and mapping section to get

231 ** the correct result. There may be entries in the hash table with

232 ** K>K0 but to the first reader, those entries will appear to be unused

233 ** slots in the hash table and so the first reader will get an answer as

234 ** if no values greater than K0 had ever been inserted into the hash table

235 ** in the first place - which is what reader one wants. Meanwhile, the

236 ** second reader using K1 will see additional values that were inserted

237 ** later, which is exactly what reader two wants.

238 **

239 ** When a rollback occurs, the value of K is decreased. Hash table entries

240 ** that correspond to frames greater than the new K value are removed

241 ** from the hash table at this point.

242 */

243 #ifndef SQLITE_OMIT_WAL

244

245 #include "wal.h"

246

247 /*

248 ** Trace output macros

249 */

250 #if defined(SQLITE_TEST) && defined(SQLITE_DEBUG)

251 int sqlite3WalTrace = 0;

252 # define WALTRACE(X) if(sqlite3WalTrace) sqlite3DebugPrintf X

253 #else

254 # define WALTRACE(X)

255 #endif

256

257 /*

258 ** The maximum (and only) versions of the wal and wal-index formats

259 ** that may be interpreted by this version of SQLite.

260 **

261 ** If a client begins recovering a WAL file and finds that (a) the checksum

262 ** values in the wal-header are correct and (b) the version field is not

263 ** WAL_MAX_VERSION, recovery fails and SQLite returns SQLITE_CANTOPEN.

264 **

265 ** Similarly, if a client successfully reads a wal-index header (i.e. the

266 ** checksum test is successful) and finds that the version field is not

267 ** WALINDEX_MAX_VERSION, then no read-transaction is opened and SQLite

268 ** returns SQLITE_CANTOPEN.

269 */

270 #define WAL_MAX_VERSION 3007000

271 #define WALINDEX_MAX_VERSION 3007000

272

273 /*

274 ** Indices of various locking bytes. WAL_NREADER is the number

275 ** of available reader locks and should be at least 3.

276 */

277 #define WAL_WRITE_LOCK 0

278 #define WAL_ALL_BUT_WRITE 1

279 #define WAL_CKPT_LOCK 1

280 #define WAL_RECOVER_LOCK 2

281 #define WAL_READ_LOCK(I) (3+(I))

282 #define WAL_NREADER (SQLITE_SHM_NLOCK-3)

283

284

285 /* Object declarations */

286 typedef struct WalIndexHdr WalIndexHdr;

287 typedef struct WalIterator WalIterator;

288 typedef struct WalCkptInfo WalCkptInfo;

289

290

291 /*

292 ** The following object holds a copy of the wal-index header content.

293 **

294 ** The actual header in the wal-index consists of two copies of this

295 ** object.

296 **

297 ** The szPage value can be any power of 2 between 512 and 32768, inclusive.

298 ** Or it can be 1 to represent a 65536-byte page. The latter case was

299 ** added in 3.7.1 when support for 64K pages was added.

300 */

301 struct WalIndexHdr {

302 u32 iVersion; /* Wal-index version */

303 u32 unused; /* Unused (padding) field */

304 u32 iChange; /* Counter incremented each transaction */

305 u8 isInit; /* 1 when initialized */

306 u8 bigEndCksum; /* True if checksums in WAL are big-endian */

307 u16 szPage; /* Database page size in bytes. 1==64K */

308 u32 mxFrame; /* Index of last valid frame in the WAL */

309 u32 nPage; /* Size of database in pages */

310 u32 aFrameCksum[2]; /* Checksum of last frame in log */

311 u32 aSalt[2]; /* Two salt values copied from WAL header */

312 u32 aCksum[2]; /* Checksum over all prior fields */

313 };

314

315 /*

316 ** A copy of the following object occurs in the wal-index immediately

317 ** following the second copy of the WalIndexHdr. This object stores

318 ** information used by checkpoint.

319 **

320 ** nBackfill is the number of frames in the WAL that have been written

321 ** back into the database. (We call the act of moving content from WAL to

322 ** database "backfilling".) The nBackfill number is never greater than

323 ** WalIndexHdr.mxFrame. nBackfill can only be increased by threads

324 ** holding the WAL_CKPT_LOCK lock (which includes a recovery thread).

325 ** However, a WAL_WRITE_LOCK thread can move the value of nBackfill from

326 ** mxFrame back to zero when the WAL is reset.

327 **

328 ** There is one entry in aReadMark[] for each reader lock. If a reader

329 ** holds read-lock K, then the value in aReadMark[K] is no greater than

330 ** the mxFrame for that reader. The value READMARK_NOT_USED (0xffffffff)

331 ** for any aReadMark[] means that entry is unused. aReadMark[0] is

332 ** a special case; its value is never used and it exists as a place-holder

333 ** to avoid having to offset aReadMark[] indexs by one. Readers holding

334 ** WAL_READ_LOCK(0) always ignore the entire WAL and read all content

335 ** directly from the database.

336 **

337 ** The value of aReadMark[K] may only be changed by a thread that

338 ** is holding an exclusive lock on WAL_READ_LOCK(K). Thus, the value of

339 ** aReadMark[K] cannot changed while there is a reader is using that mark

340 ** since the reader will be holding a shared lock on WAL_READ_LOCK(K).

341 **

342 ** The checkpointer may only transfer frames from WAL to database where

343 ** the frame numbers are less than or equal to every aReadMark[] that is

344 ** in use (that is, every aReadMark[j] for which there is a corresponding

345 ** WAL_READ_LOCK(j)). New readers (usually) pick the aReadMark[] with the

346 ** largest value and will increase an unused aReadMark[] to mxFrame if there

347 ** is not already an aReadMark[] equal to mxFrame. The exception to the

348 ** previous sentence is when nBackfill equals mxFrame (meaning that everything

349 ** in the WAL has been backfilled into the database) then new readers

350 ** will choose aReadMark[0] which has value 0 and hence such reader will

351 ** get all their all content directly from the database file and ignore

352 ** the WAL.

353 **

354 ** Writers normally append new frames to the end of the WAL. However,

355 ** if nBackfill equals mxFrame (meaning that all WAL content has been

356 ** written back into the database) and if no readers are using the WAL

357 ** (in other words, if there are no WAL_READ_LOCK(i) where i>0) then

358 ** the writer will first "reset" the WAL back to the beginning and start

359 ** writing new content beginning at frame 1.

360 **

361 ** We assume that 32-bit loads are atomic and so no locks are needed in

362 ** order to read from any aReadMark[] entries.

363 */

364 struct WalCkptInfo {

365 u32 nBackfill; /* Number of WAL frames backfilled into DB */

366 u32 aReadMark[WAL_NREADER]; /* Reader marks */

367 };

368 #define READMARK_NOT_USED 0xffffffff

369

370

371 /* A block of WALINDEX_LOCK_RESERVED bytes beginning at

372 ** WALINDEX_LOCK_OFFSET is reserved for locks. Since some systems

373 ** only support mandatory file-locks, we do not read or write data

374 ** from the region of the file on which locks are applied.

375 */

376 #define WALINDEX_LOCK_OFFSET (sizeof(WalIndexHdr)*2 + sizeof(WalCkptInfo))

377 #define WALINDEX_LOCK_RESERVED 16

378 #define WALINDEX_HDR_SIZE (WALINDEX_LOCK_OFFSET+WALINDEX_LOCK_RESERVED)

379

380 /* Size of header before each frame in wal */

381 #define WAL_FRAME_HDRSIZE 24

382

383 /* Size of write ahead log header, including checksum. */

384 /* #define WAL_HDRSIZE 24 */

385 #define WAL_HDRSIZE 32

386

387 /* WAL magic value. Either this value, or the same value with the least

388 ** significant bit also set (WAL_MAGIC \| 0x00000001) is stored in 32-bit

389 ** big-endian format in the first 4 bytes of a WAL file.

390 **

391 ** If the LSB is set, then the checksums for each frame within the WAL

392 ** file are calculated by treating all data as an array of 32-bit

393 ** big-endian words. Otherwise, they are calculated by interpreting

394 ** all data as 32-bit little-endian words.

395 */

396 #define WAL_MAGIC 0x377f0682

397

398 /*

399 ** Return the offset of frame iFrame in the write-ahead log file,

400 ** assuming a database page size of szPage bytes. The offset returned

401 ** is to the start of the write-ahead log frame-header.

402 */

403 #define walFrameOffset(iFrame, szPage) ( \

404 WAL_HDRSIZE + ((iFrame)-1)*(i64)((szPage)+WAL_FRAME_HDRSIZE) \

405 )

406

407 /*

408 ** An open write-ahead log file is represented by an instance of the

409 ** following object.

410 */

411 struct Wal {

412 sqlite3_vfs pVfs; / The VFS used to create pDbFd */

413 sqlite3_file pDbFd; / File handle for the database file */

414 sqlite3_file pWalFd; / File handle for WAL file */

415 u32 iCallback; /* Value to pass to log callback (or 0) */

416 i64 mxWalSize; /* Truncate WAL to this size upon reset */

417 int nWiData; /* Size of array apWiData */

418 int szFirstBlock; /* Size of first block written to WAL file */

419 volatile u32 *apWiData; / Pointer to wal-index content in memory */

420 u32 szPage; /* Database page size */

421 i16 readLock; /* Which read lock is being held. -1 for none */

422 u8 syncFlags; /* Flags to use to sync header writes */

423 u8 exclusiveMode; /* Non-zero if connection is in exclusive mode */

424 u8 writeLock; /* True if in a write transaction */

425 u8 ckptLock; /* True if holding a checkpoint lock */

426 u8 readOnly; /* WAL_RDWR, WAL_RDONLY, or WAL_SHM_RDONLY */

427 u8 truncateOnCommit; /* True to truncate WAL file on commit */

428 u8 syncHeader; /* Fsync the WAL header if true */

429 u8 padToSectorBoundary; /* Pad transactions out to the next sector */

430 WalIndexHdr hdr; /* Wal-index header for current transaction */

431 const char zWalName; / Name of WAL file */

432 u32 nCkpt; /* Checkpoint sequence counter in the wal-header */

433 #ifdef SQLITE_DEBUG

434 u8 lockError; /* True if a locking error has occurred */

435 #endif

436 };

437

438 /*

439 ** Candidate values for Wal.exclusiveMode.

440 */

441 #define WAL_NORMAL_MODE 0

442 #define WAL_EXCLUSIVE_MODE 1

443 #define WAL_HEAPMEMORY_MODE 2

444

445 /*

446 ** Possible values for WAL.readOnly

447 */

448 #define WAL_RDWR 0 /* Normal read/write connection */

449 #define WAL_RDONLY 1 /* The WAL file is readonly */

450 #define WAL_SHM_RDONLY 2 /* The SHM file is readonly */

451

452 /*

453 ** Each page of the wal-index mapping contains a hash-table made up of

454 ** an array of HASHTABLE_NSLOT elements of the following type.

455 */

456 typedef u16 ht_slot;

457

458 /*

459 ** This structure is used to implement an iterator that loops through

460 ** all frames in the WAL in database page order. Where two or more frames

461 ** correspond to the same database page, the iterator visits only the

462 ** frame most recently written to the WAL (in other words, the frame with

463 ** the largest index).

464 **

465 ** The internals of this structure are only accessed by:

466 **

467 ** walIteratorInit() - Create a new iterator,

468 ** walIteratorNext() - Step an iterator,

469 ** walIteratorFree() - Free an iterator.

470 **

471 ** This functionality is used by the checkpoint code (see walCheckpoint()).

472 */

473 struct WalIterator {

474 int iPrior; /* Last result returned from the iterator */

475 int nSegment; /* Number of entries in aSegment[] */

476 struct WalSegment {

477 int iNext; /* Next slot in aIndex[] not yet returned */

478 ht_slot aIndex; / i0, i1, i2... such that aPgno[iN] ascend */

479 u32 aPgno; / Array of page numbers. */

480 int nEntry; /* Nr. of entries in aPgno[] and aIndex[] */

481 int iZero; /* Frame number associated with aPgno[0] */

482 } aSegment[1]; /* One for every 32KB page in the wal-index */

483 };

484

485 /*

486 ** Define the parameters of the hash tables in the wal-index file. There

487 ** is a hash-table following every HASHTABLE_NPAGE page numbers in the

488 ** wal-index.

489 **

490 ** Changing any of these constants will alter the wal-index format and

491 ** create incompatibilities.

492 */

493 #define HASHTABLE_NPAGE 4096 /* Must be power of 2 */

494 #define HASHTABLE_HASH_1 383 /* Should be prime */

495 #define HASHTABLE_NSLOT (HASHTABLE_NPAGE2) / Must be a power of 2 */

496

497 /*

498 ** The block of page numbers associated with the first hash-table in a

499 ** wal-index is smaller than usual. This is so that there is a complete

500 ** hash-table on each aligned 32KB page of the wal-index.

501 */

502 #define HASHTABLE_NPAGE_ONE (HASHTABLE_NPAGE - (WALINDEX_HDR_SIZE/sizeof(u32)))

503

504 /* The wal-index is divided into pages of WALINDEX_PGSZ bytes each. */

505 #define WALINDEX_PGSZ ( \

506 sizeof(ht_slot)HASHTABLE_NSLOT + HASHTABLE_NPAGEsizeof(u32) \

507 )

508

509 /*

510 ** Obtain a pointer to the iPage'th page of the wal-index. The wal-index

511 ** is broken into pages of WALINDEX_PGSZ bytes. Wal-index pages are

512 ** numbered from zero.

513 **

514 ** If this call is successful, *ppPage is set to point to the wal-index

515 ** page and SQLITE_OK is returned. If an error (an OOM or VFS error) occurs,

516 ** then an SQLite error code is returned and *ppPage is set to 0.

517 */

518 static int walIndexPage(Wal pWal, int iPage, volatile u32 *ppPage){

519 int rc = SQLITE_OK;

520

521 /* Enlarge the pWal->apWiData[] array if required */

522 if( pWal->nWiData<=iPage ){

523 int nByte = sizeof(u32)(iPage+1);

524 volatile u32 **apNew;

525 apNew = (volatile u32 *)sqlite3_realloc((void )pWal->apWiData, nByte);

526 if( !apNew ){

527 *ppPage = 0;

528 return SQLITE_NOMEM;

529 }

530 memset((void*)&apNew[pWal->nWiData], 0,

531 sizeof(u32)(iPage+1-pWal->nWiData));

532 pWal->apWiData = apNew;

533 pWal->nWiData = iPage+1;

534 }

535

536 /* Request a pointer to the required page from the VFS */

537 if( pWal->apWiData[iPage]==0 ){

538 if( pWal->exclusiveMode==WAL_HEAPMEMORY_MODE ){

539 pWal->apWiData[iPage] = (u32 volatile *)sqlite3MallocZero(WALINDEX_PGSZ);

540 if( !pWal->apWiData[iPage] ) rc = SQLITE_NOMEM;

541 }else{

542 rc = sqlite3OsShmMap(pWal->pDbFd, iPage, WALINDEX_PGSZ,

543 pWal->writeLock, (void volatile **)&pWal->apWiData[iPage]

544 );

545 if( rc==SQLITE_READONLY ){

546 pWal->readOnly \|= WAL_SHM_RDONLY;

547 rc = SQLITE_OK;

548 }

549 }

550 }

551

552 *ppPage = pWal->apWiData[iPage];

553 assert( iPage==0 \|\| *ppPage \|\| rc!=SQLITE_OK );

554 return rc;

555 }

556

557 /*

558 ** Return a pointer to the WalCkptInfo structure in the wal-index.

559 */

560 static volatile WalCkptInfo walCkptInfo(Wal pWal){

561 assert( pWal->nWiData>0 && pWal->apWiData[0] );

562 return (volatile WalCkptInfo*)&(pWal->apWiData[0][sizeof(WalIndexHdr)/2]);

563 }

564

565 /*

566 ** Return a pointer to the WalIndexHdr structure in the wal-index.

567 */

568 static volatile WalIndexHdr walIndexHdr(Wal pWal){

569 assert( pWal->nWiData>0 && pWal->apWiData[0] );

570 return (volatile WalIndexHdr*)pWal->apWiData[0];

571 }

572

573 /*

574 ** The argument to this macro must be of type u32. On a little-endian

575 ** architecture, it returns the u32 value that results from interpreting

576 ** the 4 bytes as a big-endian value. On a big-endian architecture, it

577 ** returns the value that would be produced by interpreting the 4 bytes

578 ** of the input value as a little-endian integer.

579 */

580 #define BYTESWAP32(x) ( \

581 (((x)&0x000000FF)<<24) + (((x)&0x0000FF00)<<8) \

582 + (((x)&0x00FF0000)>>8) + (((x)&0xFF000000)>>24) \

583 )

584

585 /*

586 ** Generate or extend an 8 byte checksum based on the data in

587 ** array aByte[] and the initial values of aIn[0] and aIn[1] (or

588 ** initial values of 0 and 0 if aIn==NULL).

589 **

590 ** The checksum is written back into aOut[] before returning.

591 **

592 ** nByte must be a positive multiple of 8.

593 */

594 static void walChecksumBytes(

595 int nativeCksum, /* True for native byte-order, false for non-native */

596 u8 a, / Content to be checksummed */

597 int nByte, /* Bytes of content in a[]. Must be a multiple of 8. */

598 const u32 aIn, / Initial checksum value input */

599 u32 aOut / OUT: Final checksum value output */

600 ){

601 u32 s1, s2;

602 u32 aData = (u32 )a;

603 u32 aEnd = (u32 )&a[nByte];

604

605 if( aIn ){

606 s1 = aIn[0];

607 s2 = aIn[1];

608 }else{

609 s1 = s2 = 0;

610 }

611

612 assert( nByte>=8 );

613 assert( (nByte&0x00000007)==0 );

614

615 if( nativeCksum ){

616 do {

617 s1 += *aData++ + s2;

618 s2 += *aData++ + s1;

619 }while( aData<aEnd );

620 }else{

621 do {

622 s1 += BYTESWAP32(aData[0]) + s2;

623 s2 += BYTESWAP32(aData[1]) + s1;

624 aData += 2;

625 }while( aData<aEnd );

626 }

627

628 aOut[0] = s1;

629 aOut[1] = s2;

630 }

631

632 static void walShmBarrier(Wal *pWal){

633 if( pWal->exclusiveMode!=WAL_HEAPMEMORY_MODE ){

634 sqlite3OsShmBarrier(pWal->pDbFd);

635 }

636 }

637

638 /*

639 ** Write the header information in pWal->hdr into the wal-index.

640 **

641 ** The checksum on pWal->hdr is updated before it is written.

642 */

643 static void walIndexWriteHdr(Wal *pWal){

644 volatile WalIndexHdr *aHdr = walIndexHdr(pWal);

645 const int nCksum = offsetof(WalIndexHdr, aCksum);

646

647 assert( pWal->writeLock );

648 pWal->hdr.isInit = 1;

649 pWal->hdr.iVersion = WALINDEX_MAX_VERSION;

650 walChecksumBytes(1, (u8*)&pWal->hdr, nCksum, 0, pWal->hdr.aCksum);

651 memcpy((void )&aHdr[1], (void )&pWal->hdr, sizeof(WalIndexHdr));

652 walShmBarrier(pWal);

653 memcpy((void )&aHdr[0], (void )&pWal->hdr, sizeof(WalIndexHdr));

654 }

655

656 /*

657 ** This function encodes a single frame header and writes it to a buffer

658 ** supplied by the caller. A frame-header is made up of a series of

659 ** 4-byte big-endian integers, as follows:

660 **

661 ** 0: Page number.

662 ** 4: For commit records, the size of the database image in pages

663 ** after the commit. For all other records, zero.

664 ** 8: Salt-1 (copied from the wal-header)

665 ** 12: Salt-2 (copied from the wal-header)

666 ** 16: Checksum-1.

667 ** 20: Checksum-2.

668 */

669 static void walEncodeFrame(

670 Wal pWal, / The write-ahead log */

671 u32 iPage, /* Database page number for frame */

672 u32 nTruncate, /* New db size (or 0 for non-commit frames) */

673 u8 aData, / Pointer to page data */

674 u8 aFrame / OUT: Write encoded frame here */

675 ){

676 int nativeCksum; /* True for native byte-order checksums */

677 u32 *aCksum = pWal->hdr.aFrameCksum;

678 assert( WAL_FRAME_HDRSIZE==24 );

679 sqlite3Put4byte(&aFrame[0], iPage);

680 sqlite3Put4byte(&aFrame[4], nTruncate);

681 memcpy(&aFrame[8], pWal->hdr.aSalt, 8);

682

683 nativeCksum = (pWal->hdr.bigEndCksum==SQLITE_BIGENDIAN);

684 walChecksumBytes(nativeCksum, aFrame, 8, aCksum, aCksum);

685 walChecksumBytes(nativeCksum, aData, pWal->szPage, aCksum, aCksum);

686

687 sqlite3Put4byte(&aFrame[16], aCksum[0]);

688 sqlite3Put4byte(&aFrame[20], aCksum[1]);

689 }

690

691 /*

692 ** Check to see if the frame with header in aFrame[] and content

693 ** in aData[] is valid. If it is a valid frame, fill *piPage and

694 ** *pnTruncate and return true. Return if the frame is not valid.

695 */

696 static int walDecodeFrame(

697 Wal pWal, / The write-ahead log */

698 u32 piPage, / OUT: Database page number for frame */

699 u32 pnTruncate, / OUT: New db size (or 0 if not commit) */

700 u8 aData, / Pointer to page data (for checksum) */

701 u8 aFrame / Frame data */

702 ){

703 int nativeCksum; /* True for native byte-order checksums */

704 u32 *aCksum = pWal->hdr.aFrameCksum;

705 u32 pgno; /* Page number of the frame */

706 assert( WAL_FRAME_HDRSIZE==24 );

707

708 /* A frame is only valid if the salt values in the frame-header

709 ** match the salt values in the wal-header.

710 */

711 if( memcmp(&pWal->hdr.aSalt, &aFrame[8], 8)!=0 ){

712 return 0;

713 }

714

715 /* A frame is only valid if the page number is creater than zero.

716 */

717 pgno = sqlite3Get4byte(&aFrame[0]);

718 if( pgno==0 ){

719 return 0;

720 }

721

722 /* A frame is only valid if a checksum of the WAL header,

723 ** all prior frams, the first 16 bytes of this frame-header,

724 ** and the frame-data matches the checksum in the last 8

725 ** bytes of this frame-header.

726 */

727 nativeCksum = (pWal->hdr.bigEndCksum==SQLITE_BIGENDIAN);

728 walChecksumBytes(nativeCksum, aFrame, 8, aCksum, aCksum);

729 walChecksumBytes(nativeCksum, aData, pWal->szPage, aCksum, aCksum);

730 if( aCksum[0]!=sqlite3Get4byte(&aFrame[16])

731 \|\| aCksum[1]!=sqlite3Get4byte(&aFrame[20])

732 ){

733 /* Checksum failed. */

734 return 0;

735 }

736

737 /* If we reach this point, the frame is valid. Return the page number

738 ** and the new database size.

739 */

740 *piPage = pgno;

741 *pnTruncate = sqlite3Get4byte(&aFrame[4]);

742 return 1;

743 }

744

745

746 #if defined(SQLITE_TEST) && defined(SQLITE_DEBUG)

747 /*

748 ** Names of locks. This routine is used to provide debugging output and is not

749 ** a part of an ordinary build.

750 */

751 static const char *walLockName(int lockIdx){

752 if( lockIdx==WAL_WRITE_LOCK ){

753 return "WRITE-LOCK";

754 }else if( lockIdx==WAL_CKPT_LOCK ){

755 return "CKPT-LOCK";

756 }else if( lockIdx==WAL_RECOVER_LOCK ){

757 return "RECOVER-LOCK";

758 }else{

759 static char zName[15];

760 sqlite3_snprintf(sizeof(zName), zName, "READ-LOCK[%d]",

761 lockIdx-WAL_READ_LOCK(0));

762 return zName;

763 }

764 }

765 #endif /defined(SQLITE_TEST) \|\| defined(SQLITE_DEBUG) /

766

767

768 /*

769 ** Set or release locks on the WAL. Locks are either shared or exclusive.

770 ** A lock cannot be moved directly between shared and exclusive - it must go

771 ** through the unlocked state first.

772 **

773 ** In locking_mode=EXCLUSIVE, all of these routines become no-ops.

774 */

775 static int walLockShared(Wal *pWal, int lockIdx){

776 int rc;

777 if( pWal->exclusiveMode ) return SQLITE_OK;

778 rc = sqlite3OsShmLock(pWal->pDbFd, lockIdx, 1,

779 SQLITE_SHM_LOCK \| SQLITE_SHM_SHARED);

780 WALTRACE(("WAL%p: acquire SHARED-%s %s\n", pWal,

781 walLockName(lockIdx), rc ? "failed" : "ok"));

782 VVA_ONLY( pWal->lockError = (u8)(rc!=SQLITE_OK && rc!=SQLITE_BUSY); )

783 return rc;

784 }

785 static void walUnlockShared(Wal *pWal, int lockIdx){

786 if( pWal->exclusiveMode ) return;

787 (void)sqlite3OsShmLock(pWal->pDbFd, lockIdx, 1,

788 SQLITE_SHM_UNLOCK \| SQLITE_SHM_SHARED);

789 WALTRACE(("WAL%p: release SHARED-%s\n", pWal, walLockName(lockIdx)));

790 }

791 static int walLockExclusive(Wal *pWal, int lockIdx, int n){

792 int rc;

793 if( pWal->exclusiveMode ) return SQLITE_OK;

794 rc = sqlite3OsShmLock(pWal->pDbFd, lockIdx, n,

795 SQLITE_SHM_LOCK \| SQLITE_SHM_EXCLUSIVE);

796 WALTRACE(("WAL%p: acquire EXCLUSIVE-%s cnt=%d %s\n", pWal,

797 walLockName(lockIdx), n, rc ? "failed" : "ok"));

798 VVA_ONLY( pWal->lockError = (u8)(rc!=SQLITE_OK && rc!=SQLITE_BUSY); )

799 return rc;

800 }

801 static void walUnlockExclusive(Wal *pWal, int lockIdx, int n){

802 if( pWal->exclusiveMode ) return;

803 (void)sqlite3OsShmLock(pWal->pDbFd, lockIdx, n,

804 SQLITE_SHM_UNLOCK \| SQLITE_SHM_EXCLUSIVE);

805 WALTRACE(("WAL%p: release EXCLUSIVE-%s cnt=%d\n", pWal,

806 walLockName(lockIdx), n));

807 }

808

809 /*

810 ** Compute a hash on a page number. The resulting hash value must land

811 ** between 0 and (HASHTABLE_NSLOT-1). The walHashNext() function advances

812 ** the hash to the next value in the event of a collision.

813 */

814 static int walHash(u32 iPage){

815 assert( iPage>0 );

816 assert( (HASHTABLE_NSLOT & (HASHTABLE_NSLOT-1))==0 );

817 return (iPage*HASHTABLE_HASH_1) & (HASHTABLE_NSLOT-1);

818 }

819 static int walNextHash(int iPriorHash){

820 return (iPriorHash+1)&(HASHTABLE_NSLOT-1);

821 }

822

823 /*

824 ** Return pointers to the hash table and page number array stored on

825 ** page iHash of the wal-index. The wal-index is broken into 32KB pages

826 ** numbered starting from 0.

827 **

828 ** Set output variable *paHash to point to the start of the hash table

829 ** in the wal-index file. Set *piZero to one less than the frame

830 ** number of the first frame indexed by this hash table. If a

831 ** slot in the hash table is set to N, it refers to frame number

832 ** (*piZero+N) in the log.

833 **

834 ** Finally, set paPgno so that paPgno[1] is the page number of the

835 ** first frame indexed by the hash table, frame (*piZero+1).

836 */

837 static int walHashGet(

838 Wal pWal, / WAL handle */

839 int iHash, /* Find the iHash'th table */

840 volatile ht_slot *paHash, / OUT: Pointer to hash index */

841 volatile u32 *paPgno, / OUT: Pointer to page number array */

842 u32 piZero / OUT: Frame associated with paPgno[0] /

843 ){

844 int rc; /* Return code */

845 volatile u32 *aPgno;

846

847 rc = walIndexPage(pWal, iHash, &aPgno);

848 assert( rc==SQLITE_OK \|\| iHash>0 );

849

850 if( rc==SQLITE_OK ){

851 u32 iZero;

852 volatile ht_slot *aHash;

853

854 aHash = (volatile ht_slot *)&aPgno[HASHTABLE_NPAGE];

855 if( iHash==0 ){

856 aPgno = &aPgno[WALINDEX_HDR_SIZE/sizeof(u32)];

857 iZero = 0;

858 }else{

859 iZero = HASHTABLE_NPAGE_ONE + (iHash-1)*HASHTABLE_NPAGE;

860 }

861

862 *paPgno = &aPgno[-1];

863 *paHash = aHash;

864 *piZero = iZero;

865 }

866 return rc;

867 }

868

869 /*

870 ** Return the number of the wal-index page that contains the hash-table

871 ** and page-number array that contain entries corresponding to WAL frame

872 ** iFrame. The wal-index is broken up into 32KB pages. Wal-index pages

873 ** are numbered starting from 0.

874 */

875 static int walFramePage(u32 iFrame){

876 int iHash = (iFrame+HASHTABLE_NPAGE-HASHTABLE_NPAGE_ONE-1) / HASHTABLE_NPAGE;

877 assert( (iHash==0 \|\| iFrame>HASHTABLE_NPAGE_ONE)

878 && (iHash>=1 \|\| iFrame<=HASHTABLE_NPAGE_ONE)

879 && (iHash<=1 \|\| iFrame>(HASHTABLE_NPAGE_ONE+HASHTABLE_NPAGE))

880 && (iHash>=2 \|\| iFrame<=HASHTABLE_NPAGE_ONE+HASHTABLE_NPAGE)

881 && (iHash<=2 \|\| iFrame>(HASHTABLE_NPAGE_ONE+2*HASHTABLE_NPAGE))

882 );

883 return iHash;

884 }

885

886 /*

887 ** Return the page number associated with frame iFrame in this WAL.

888 */

889 static u32 walFramePgno(Wal *pWal, u32 iFrame){

890 int iHash = walFramePage(iFrame);

891 if( iHash==0 ){

892 return pWal->apWiData[0][WALINDEX_HDR_SIZE/sizeof(u32) + iFrame - 1];

893 }

894 return pWal->apWiData[iHash][(iFrame-1-HASHTABLE_NPAGE_ONE)%HASHTABLE_NPAGE];

895 }

896

897 /*

898 ** Remove entries from the hash table that point to WAL slots greater

899 ** than pWal->hdr.mxFrame.

900 **

901 ** This function is called whenever pWal->hdr.mxFrame is decreased due

902 ** to a rollback or savepoint.

903 **

904 ** At most only the hash table containing pWal->hdr.mxFrame needs to be

905 ** updated. Any later hash tables will be automatically cleared when

906 ** pWal->hdr.mxFrame advances to the point where those hash tables are

907 ** actually needed.

908 */

909 static void walCleanupHash(Wal *pWal){

910 volatile ht_slot aHash = 0; / Pointer to hash table to clear */

911 volatile u32 aPgno = 0; / Page number array for hash table */

912 u32 iZero = 0; /* frame == (aHash[x]+iZero) */

913 int iLimit = 0; /* Zero values greater than this */

914 int nByte; /* Number of bytes to zero in aPgno[] */

915 int i; /* Used to iterate through aHash[] */

916

917 assert( pWal->writeLock );

918 testcase( pWal->hdr.mxFrame==HASHTABLE_NPAGE_ONE-1 );

919 testcase( pWal->hdr.mxFrame==HASHTABLE_NPAGE_ONE );

920 testcase( pWal->hdr.mxFrame==HASHTABLE_NPAGE_ONE+1 );

921

922 if( pWal->hdr.mxFrame==0 ) return;

923

924 /* Obtain pointers to the hash-table and page-number array containing

925 ** the entry that corresponds to frame pWal->hdr.mxFrame. It is guaranteed

926 ** that the page said hash-table and array reside on is already mapped.

927 */

928 assert( pWal->nWiData>walFramePage(pWal->hdr.mxFrame) );

929 assert( pWal->apWiData[walFramePage(pWal->hdr.mxFrame)] );

930 walHashGet(pWal, walFramePage(pWal->hdr.mxFrame), &aHash, &aPgno, &iZero);

931

932 /* Zero all hash-table entries that correspond to frame numbers greater

933 ** than pWal->hdr.mxFrame.

934 */

935 iLimit = pWal->hdr.mxFrame - iZero;

936 assert( iLimit>0 );

937 for(i=0; i<HASHTABLE_NSLOT; i++){

938 if( aHash[i]>iLimit ){

939 aHash[i] = 0;

940 }

941 }

942

943 /* Zero the entries in the aPgno array that correspond to frames with

944 ** frame numbers greater than pWal->hdr.mxFrame.

945 */

946 nByte = (int)((char )aHash - (char )&aPgno[iLimit+1]);

947 memset((void *)&aPgno[iLimit+1], 0, nByte);

948

949 #ifdef SQLITE_ENABLE_EXPENSIVE_ASSERT

950 /* Verify that the every entry in the mapping region is still reachable

951 ** via the hash table even after the cleanup.

952 */

953 if( iLimit ){

954 int i; /* Loop counter */

955 int iKey; /* Hash key */

956 for(i=1; i<=iLimit; i++){

957 for(iKey=walHash(aPgno[i]); aHash[iKey]; iKey=walNextHash(iKey)){

958 if( aHash[iKey]==i ) break;

959 }

960 assert( aHash[iKey]==i );

961 }

962 }

963 #endif /* SQLITE_ENABLE_EXPENSIVE_ASSERT */

964 }

965

966

967 /*

968 ** Set an entry in the wal-index that will map database page number

969 ** pPage into WAL frame iFrame.

970 */

971 static int walIndexAppend(Wal *pWal, u32 iFrame, u32 iPage){

972 int rc; /* Return code */

973 u32 iZero = 0; /* One less than frame number of aPgno[1] */

974 volatile u32 aPgno = 0; / Page number array */

975 volatile ht_slot aHash = 0; / Hash table */

976

977 rc = walHashGet(pWal, walFramePage(iFrame), &aHash, &aPgno, &iZero);

978

979 /* Assuming the wal-index file was successfully mapped, populate the

980 ** page number array and hash table entry.

981 */

982 if( rc==SQLITE_OK ){

983 int iKey; /* Hash table key */

984 int idx; /* Value to write to hash-table slot */

985 int nCollide; /* Number of hash collisions */

986

987 idx = iFrame - iZero;

988 assert( idx <= HASHTABLE_NSLOT/2 + 1 );

989

990 /* If this is the first entry to be added to this hash-table, zero the

991 ** entire hash table and aPgno[] array before proceeding.

992 */

993 if( idx==1 ){

994 int nByte = (int)((u8 )&aHash[HASHTABLE_NSLOT] - (u8 )&aPgno[1]);

995 memset((void*)&aPgno[1], 0, nByte);

996 }

997

998 /* If the entry in aPgno[] is already set, then the previous writer

999 ** must have exited unexpectedly in the middle of a transaction (after

1000 ** writing one or more dirty pages to the WAL to free up memory).

1001 ** Remove the remnants of that writers uncommitted transaction from

1002 ** the hash-table before writing any new entries.

1003 */

1004 if( aPgno[idx] ){

1005 walCleanupHash(pWal);

1006 assert( !aPgno[idx] );

1007 }

1008

1009 /* Write the aPgno[] array entry and the hash-table slot. */

1010 nCollide = idx;

1011 for(iKey=walHash(iPage); aHash[iKey]; iKey=walNextHash(iKey)){

1012 if( (nCollide--)==0 ) return SQLITE_CORRUPT_BKPT;

1013 }

1014 aPgno[idx] = iPage;

1015 aHash[iKey] = (ht_slot)idx;

1016

1017 #ifdef SQLITE_ENABLE_EXPENSIVE_ASSERT

1018 /* Verify that the number of entries in the hash table exactly equals

1019 ** the number of entries in the mapping region.

1020 */

1021 {

1022 int i; /* Loop counter */

1023 int nEntry = 0; /* Number of entries in the hash table */

1024 for(i=0; i<HASHTABLE_NSLOT; i++){ if( aHash[i] ) nEntry++; }

1025 assert( nEntry==idx );

1026 }

1027

1028 /* Verify that the every entry in the mapping region is reachable

1029 ** via the hash table. This turns out to be a really, really expensive

1030 ** thing to check, so only do this occasionally - not on every

1031 ** iteration.

1032 */

1033 if( (idx&0x3ff)==0 ){

1034 int i; /* Loop counter */

1035 for(i=1; i<=idx; i++){

1036 for(iKey=walHash(aPgno[i]); aHash[iKey]; iKey=walNextHash(iKey)){

1037 if( aHash[iKey]==i ) break;

1038 }

1039 assert( aHash[iKey]==i );

1040 }

1041 }

1042 #endif /* SQLITE_ENABLE_EXPENSIVE_ASSERT */

1043 }

1044

1045

1046 return rc;

1047 }

1048

1049

1050 /*

1051 ** Recover the wal-index by reading the write-ahead log file.

1052 **

1053 ** This routine first tries to establish an exclusive lock on the

1054 ** wal-index to prevent other threads/processes from doing anything

1055 ** with the WAL or wal-index while recovery is running. The

1056 ** WAL_RECOVER_LOCK is also held so that other threads will know

1057 ** that this thread is running recovery. If unable to establish

1058 ** the necessary locks, this routine returns SQLITE_BUSY.

1059 */

1060 static int walIndexRecover(Wal *pWal){

1061 int rc; /* Return Code */

1062 i64 nSize; /* Size of log file */

1063 u32 aFrameCksum[2] = {0, 0};

1064 int iLock; /* Lock offset to lock for checkpoint */

1065 int nLock; /* Number of locks to hold */

1066

1067 /* Obtain an exclusive lock on all byte in the locking range not already

1068 ** locked by the caller. The caller is guaranteed to have locked the

1069 ** WAL_WRITE_LOCK byte, and may have also locked the WAL_CKPT_LOCK byte.

1070 ** If successful, the same bytes that are locked here are unlocked before

1071 ** this function returns.

1072 */

1073 assert( pWal->ckptLock==1 \|\| pWal->ckptLock==0 );

1074 assert( WAL_ALL_BUT_WRITE==WAL_WRITE_LOCK+1 );

1075 assert( WAL_CKPT_LOCK==WAL_ALL_BUT_WRITE );

1076 assert( pWal->writeLock );

1077 iLock = WAL_ALL_BUT_WRITE + pWal->ckptLock;

1078 nLock = SQLITE_SHM_NLOCK - iLock;

1079 rc = walLockExclusive(pWal, iLock, nLock);

1080 if( rc ){

1081 return rc;

1082 }

1083 WALTRACE(("WAL%p: recovery begin...\n", pWal));

1084

1085 memset(&pWal->hdr, 0, sizeof(WalIndexHdr));

1086

1087 rc = sqlite3OsFileSize(pWal->pWalFd, &nSize);

1088 if( rc!=SQLITE_OK ){

1089 goto recovery_error;

1090 }

1091

1092 if( nSize>WAL_HDRSIZE ){

1093 u8 aBuf[WAL_HDRSIZE]; /* Buffer to load WAL header into */

1094 u8 aFrame = 0; / Malloc'd buffer to load entire frame */

1095 int szFrame; /* Number of bytes in buffer aFrame[] */

1096 u8 aData; / Pointer to data part of aFrame buffer */

1097 int iFrame; /* Index of last frame read */

1098 i64 iOffset; /* Next offset to read from log file */

1099 int szPage; /* Page size according to the log */

1100 u32 magic; /* Magic value read from WAL header */

1101 u32 version; /* Magic value read from WAL header */

1102 int isValid; /* True if this frame is valid */

1103

1104 /* Read in the WAL header. */

1105 rc = sqlite3OsRead(pWal->pWalFd, aBuf, WAL_HDRSIZE, 0);

1106 if( rc!=SQLITE_OK ){

1107 goto recovery_error;

1108 }

1109

1110 /* If the database page size is not a power of two, or is greater than

1111 ** SQLITE_MAX_PAGE_SIZE, conclude that the WAL file contains no valid

1112 ** data. Similarly, if the 'magic' value is invalid, ignore the whole

1113 ** WAL file.

1114 */

1115 magic = sqlite3Get4byte(&aBuf[0]);

1116 szPage = sqlite3Get4byte(&aBuf[8]);

1117 if( (magic&0xFFFFFFFE)!=WAL_MAGIC

1118 \|\| szPage&(szPage-1)

1119 \|\| szPage>SQLITE_MAX_PAGE_SIZE

1120 \|\| szPage<512

1121 ){

1122 goto finished;

1123 }

1124 pWal->hdr.bigEndCksum = (u8)(magic&0x00000001);

1125 pWal->szPage = szPage;

1126 pWal->nCkpt = sqlite3Get4byte(&aBuf[12]);

1127 memcpy(&pWal->hdr.aSalt, &aBuf[16], 8);

1128

1129 /* Verify that the WAL header checksum is correct */

1130 walChecksumBytes(pWal->hdr.bigEndCksum==SQLITE_BIGENDIAN,

1131 aBuf, WAL_HDRSIZE-2*4, 0, pWal->hdr.aFrameCksum

1132 );

1133 if( pWal->hdr.aFrameCksum[0]!=sqlite3Get4byte(&aBuf[24])

1134 \|\| pWal->hdr.aFrameCksum[1]!=sqlite3Get4byte(&aBuf[28])

1135 ){

1136 goto finished;

1137 }

1138

1139 /* Verify that the version number on the WAL format is one that

1140 ** are able to understand */

1141 version = sqlite3Get4byte(&aBuf[4]);

1142 if( version!=WAL_MAX_VERSION ){

1143 rc = SQLITE_CANTOPEN_BKPT;

1144 goto finished;

1145 }

1146

1147 /* Malloc a buffer to read frames into. */

1148 szFrame = szPage + WAL_FRAME_HDRSIZE;

1149 aFrame = (u8 *)sqlite3_malloc(szFrame);

1150 if( !aFrame ){

1151 rc = SQLITE_NOMEM;

1152 goto recovery_error;

1153 }

1154 aData = &aFrame[WAL_FRAME_HDRSIZE];

1155

1156 /* Read all frames from the log file. */

1157 iFrame = 0;

1158 for(iOffset=WAL_HDRSIZE; (iOffset+szFrame)<=nSize; iOffset+=szFrame){

1159 u32 pgno; /* Database page number for frame */

1160 u32 nTruncate; /* dbsize field from frame header */

1161

1162 /* Read and decode the next log frame. */

1163 iFrame++;

1164 rc = sqlite3OsRead(pWal->pWalFd, aFrame, szFrame, iOffset);

1165 if( rc!=SQLITE_OK ) break;

1166 isValid = walDecodeFrame(pWal, &pgno, &nTruncate, aData, aFrame);

1167 if( !isValid ) break;

1168 rc = walIndexAppend(pWal, iFrame, pgno);

1169 if( rc!=SQLITE_OK ) break;

1170

1171 /* If nTruncate is non-zero, this is a commit record. */

1172 if( nTruncate ){

1173 pWal->hdr.mxFrame = iFrame;

1174 pWal->hdr.nPage = nTruncate;

1175 pWal->hdr.szPage = (u16)((szPage&0xff00) \| (szPage>>16));

1176 testcase( szPage<=32768 );

1177 testcase( szPage>=65536 );

1178 aFrameCksum[0] = pWal->hdr.aFrameCksum[0];

1179 aFrameCksum[1] = pWal->hdr.aFrameCksum[1];

1180 }

1181 }

1182

1183 sqlite3_free(aFrame);

1184 }

1185

1186 finished:

1187 if( rc==SQLITE_OK ){

1188 volatile WalCkptInfo *pInfo;

1189 int i;

1190 pWal->hdr.aFrameCksum[0] = aFrameCksum[0];

1191 pWal->hdr.aFrameCksum[1] = aFrameCksum[1];

1192 walIndexWriteHdr(pWal);

1193

1194 /* Reset the checkpoint-header. This is safe because this thread is

1195 ** currently holding locks that exclude all other readers, writers and

1196 ** checkpointers.

1197 */

1198 pInfo = walCkptInfo(pWal);

1199 pInfo->nBackfill = 0;

1200 pInfo->aReadMark[0] = 0;

1201 for(i=1; i<WAL_NREADER; i++) pInfo->aReadMark[i] = READMARK_NOT_USED;

1202 if( pWal->hdr.mxFrame ) pInfo->aReadMark[1] = pWal->hdr.mxFrame;

1203

1204 /* If more than one frame was recovered from the log file, report an

1205 ** event via sqlite3_log(). This is to help with identifying performance

1206 ** problems caused by applications routinely shutting down without

1207 ** checkpointing the log file.

1208 */

1209 if( pWal->hdr.nPage ){

1210 sqlite3_log(SQLITE_NOTICE_RECOVER_WAL,

1211 "recovered %d frames from WAL file %s",

1212 pWal->hdr.mxFrame, pWal->zWalName

1213 );

1214 }

1215 }

1216

1217 recovery_error:

1218 WALTRACE(("WAL%p: recovery %s\n", pWal, rc ? "failed" : "ok"));

1219 walUnlockExclusive(pWal, iLock, nLock);

1220 return rc;

1221 }

1222

1223 /*

1224 ** Close an open wal-index.

1225 */

1226 static void walIndexClose(Wal *pWal, int isDelete){

1227 if( pWal->exclusiveMode==WAL_HEAPMEMORY_MODE ){

1228 int i;

1229 for(i=0; i<pWal->nWiData; i++){

1230 sqlite3_free((void *)pWal->apWiData[i]);

1231 pWal->apWiData[i] = 0;

1232 }

1233 }else{

1234 sqlite3OsShmUnmap(pWal->pDbFd, isDelete);

1235 }

1236 }

1237

1238 /*

1239 ** Open a connection to the WAL file zWalName. The database file must

1240 ** already be opened on connection pDbFd. The buffer that zWalName points

1241 ** to must remain valid for the lifetime of the returned Wal* handle.

1242 **

1243 ** A SHARED lock should be held on the database file when this function

1244 ** is called. The purpose of this SHARED lock is to prevent any other

1245 ** client from unlinking the WAL or wal-index file. If another process

1246 ** were to do this just after this client opened one of these files, the

1247 ** system would be badly broken.

1248 **

1249 ** If the log file is successfully opened, SQLITE_OK is returned and

1250 ** *ppWal is set to point to a new WAL handle. If an error occurs,

1251 ** an SQLite error code is returned and *ppWal is left unmodified.

1252 */

1253 int sqlite3WalOpen(

1254 sqlite3_vfs pVfs, / vfs module to open wal and wal-index */

1255 sqlite3_file pDbFd, / The open database file */

1256 const char zWalName, / Name of the WAL file */

1257 int bNoShm, /* True to run in heap-memory mode */

1258 i64 mxWalSize, /* Truncate WAL to this size on reset */

1259 Wal *ppWal / OUT: Allocated Wal handle */

1260 ){

1261 int rc; /* Return Code */

1262 Wal pRet; / Object to allocate and return */

1263 int flags; /* Flags passed to OsOpen() */

1264

1265 assert( zWalName && zWalName[0] );

1266 assert( pDbFd );

1267

1268 /* In the amalgamation, the os_unix.c and os_win.c source files come before

1269 ** this source file. Verify that the #defines of the locking byte offsets

1270 ** in os_unix.c and os_win.c agree with the WALINDEX_LOCK_OFFSET value.

1271 */

1272 #ifdef WIN_SHM_BASE

1273 assert( WIN_SHM_BASE==WALINDEX_LOCK_OFFSET );

1274 #endif

1275 #ifdef UNIX_SHM_BASE

1276 assert( UNIX_SHM_BASE==WALINDEX_LOCK_OFFSET );

1277 #endif

1278

1279

1280 /* Allocate an instance of struct Wal to return. */

1281 *ppWal = 0;

1282 pRet = (Wal*)sqlite3MallocZero(sizeof(Wal) + pVfs->szOsFile);

1283 if( !pRet ){

1284 return SQLITE_NOMEM;

1285 }

1286

1287 pRet->pVfs = pVfs;

1288 pRet->pWalFd = (sqlite3_file *)&pRet[1];

1289 pRet->pDbFd = pDbFd;

1290 pRet->readLock = -1;

1291 pRet->mxWalSize = mxWalSize;

1292 pRet->zWalName = zWalName;

1293 pRet->syncHeader = 1;

1294 pRet->padToSectorBoundary = 1;

1295 pRet->exclusiveMode = (bNoShm ? WAL_HEAPMEMORY_MODE: WAL_NORMAL_MODE);

1296

1297 /* Open file handle on the write-ahead log file. */

1298 flags = (SQLITE_OPEN_READWRITE\|SQLITE_OPEN_CREATE\|SQLITE_OPEN_WAL);

1299 rc = sqlite3OsOpen(pVfs, zWalName, pRet->pWalFd, flags, &flags);

1300 if( rc==SQLITE_OK && flags&SQLITE_OPEN_READONLY ){

1301 pRet->readOnly = WAL_RDONLY;

1302 }

1303

1304 if( rc!=SQLITE_OK ){

1305 walIndexClose(pRet, 0);

1306 sqlite3OsClose(pRet->pWalFd);

1307 sqlite3_free(pRet);

1308 }else{

1309 int iDC = sqlite3OsDeviceCharacteristics(pDbFd);

1310 if( iDC & SQLITE_IOCAP_SEQUENTIAL ){ pRet->syncHeader = 0; }

1311 if( iDC & SQLITE_IOCAP_POWERSAFE_OVERWRITE ){

1312 pRet->padToSectorBoundary = 0;

1313 }

1314 *ppWal = pRet;

1315 WALTRACE(("WAL%d: opened\n", pRet));

1316 }

1317 return rc;

1318 }

1319

1320 /*

1321 ** Change the size to which the WAL file is trucated on each reset.

1322 */

1323 void sqlite3WalLimit(Wal *pWal, i64 iLimit){

1324 if( pWal ) pWal->mxWalSize = iLimit;

1325 }

1326

1327 /*

1328 ** Find the smallest page number out of all pages held in the WAL that

1329 ** has not been returned by any prior invocation of this method on the

1330 ** same WalIterator object. Write into *piFrame the frame index where

1331 ** that page was last written into the WAL. Write into *piPage the page

1332 ** number.

1333 **

1334 ** Return 0 on success. If there are no pages in the WAL with a page

1335 ** number larger than *piPage, then return 1.

1336 */

1337 static int walIteratorNext(

1338 WalIterator p, / Iterator */

1339 u32 piPage, / OUT: The page number of the next page */

1340 u32 piFrame / OUT: Wal frame index of next page */

1341 ){

1342 u32 iMin; /* Result pgno must be greater than iMin */

1343 u32 iRet = 0xFFFFFFFF; /* 0xffffffff is never a valid page number */

1344 int i; /* For looping through segments */

1345

1346 iMin = p->iPrior;

1347 assert( iMin<0xffffffff );

1348 for(i=p->nSegment-1; i>=0; i--){

1349 struct WalSegment *pSegment = &p->aSegment[i];

1350 while( pSegment->iNext<pSegment->nEntry ){

1351 u32 iPg = pSegment->aPgno[pSegment->aIndex[pSegment->iNext]];

1352 if( iPg>iMin ){

1353 if( iPg<iRet ){

1354 iRet = iPg;

1355 *piFrame = pSegment->iZero + pSegment->aIndex[pSegment->iNext];

1356 }

1357 break;

1358 }

1359 pSegment->iNext++;

1360 }

1361 }

1362

1363 *piPage = p->iPrior = iRet;

1364 return (iRet==0xFFFFFFFF);

1365 }

1366

1367 /*

1368 ** This function merges two sorted lists into a single sorted list.

1369 **

1370 ** aLeft[] and aRight[] are arrays of indices. The sort key is

1371 ** aContent[aLeft[]] and aContent[aRight[]]. Upon entry, the following

1372 ** is guaranteed for all J<K:

1373 **

1374 ** aContent[aLeft[J]] < aContent[aLeft[K]]

1375 ** aContent[aRight[J]] < aContent[aRight[K]]

1376 **

1377 ** This routine overwrites aRight[] with a new (probably longer) sequence

1378 ** of indices such that the aRight[] contains every index that appears in

1379 ** either aLeft[] or the old aRight[] and such that the second condition

1380 ** above is still met.

1381 **

1382 ** The aContent[aLeft[X]] values will be unique for all X. And the

1383 ** aContent[aRight[X]] values will be unique too. But there might be

1384 ** one or more combinations of X and Y such that

1385 **

1386 ** aLeft[X]!=aRight[Y] && aContent[aLeft[X]] == aContent[aRight[Y]]

1387 **

1388 ** When that happens, omit the aLeft[X] and use the aRight[Y] index.

1389 */

1390 static void walMerge(

1391 const u32 aContent, / Pages in wal - keys for the sort */

1392 ht_slot aLeft, / IN: Left hand input list */

1393 int nLeft, /* IN: Elements in array paLeft /

1394 ht_slot *paRight, / IN/OUT: Right hand input list */

1395 int pnRight, / IN/OUT: Elements in paRight /

1396 ht_slot aTmp / Temporary buffer */

1397 ){

1398 int iLeft = 0; /* Current index in aLeft */

1399 int iRight = 0; /* Current index in aRight */

1400 int iOut = 0; /* Current index in output buffer */

1401 int nRight = *pnRight;

1402 ht_slot aRight = paRight;

1403

1404 assert( nLeft>0 && nRight>0 );

1405 while( iRight<nRight \|\| iLeft<nLeft ){

1406 ht_slot logpage;

1407 Pgno dbpage;

1408

1409 if( (iLeft<nLeft)

1410 && (iRight>=nRight \|\| aContent[aLeft[iLeft]]<aContent[aRight[iRight]])

1411 ){

1412 logpage = aLeft[iLeft++];

1413 }else{

1414 logpage = aRight[iRight++];

1415 }

1416 dbpage = aContent[logpage];

1417

1418 aTmp[iOut++] = logpage;

1419 if( iLeft<nLeft && aContent[aLeft[iLeft]]==dbpage ) iLeft++;

1420

1421 assert( iLeft>=nLeft \|\| aContent[aLeft[iLeft]]>dbpage );

1422 assert( iRight>=nRight \|\| aContent[aRight[iRight]]>dbpage );

1423 }

1424

1425 *paRight = aLeft;

1426 *pnRight = iOut;

1427 memcpy(aLeft, aTmp, sizeof(aTmp[0])*iOut);

1428 }

1429

1430 /*

1431 ** Sort the elements in list aList using aContent[] as the sort key.

1432 ** Remove elements with duplicate keys, preferring to keep the

1433 ** larger aList[] values.

1434 **

1435 ** The aList[] entries are indices into aContent[]. The values in

1436 ** aList[] are to be sorted so that for all J<K:

1437 **

1438 ** aContent[aList[J]] < aContent[aList[K]]

1439 **

1440 ** For any X and Y such that

1441 **

1442 ** aContent[aList[X]] == aContent[aList[Y]]

1443 **

1444 ** Keep the larger of the two values aList[X] and aList[Y] and discard

1445 ** the smaller.

1446 */

1447 static void walMergesort(

1448 const u32 aContent, / Pages in wal */

1449 ht_slot aBuffer, / Buffer of at least pnList items to use /

1450 ht_slot aList, / IN/OUT: List to sort */

1451 int pnList / IN/OUT: Number of elements in aList[] */

1452 ){

1453 struct Sublist {

1454 int nList; /* Number of elements in aList */

1455 ht_slot aList; / Pointer to sub-list content */

1456 };

1457

1458 const int nList = pnList; / Size of input list */

1459 int nMerge = 0; /* Number of elements in list aMerge */

1460 ht_slot aMerge = 0; / List to be merged */

1461 int iList; /* Index into input list */

1462 int iSub = 0; /* Index into aSub array */

1463 struct Sublist aSub[13]; /* Array of sub-lists */

1464

1465 memset(aSub, 0, sizeof(aSub));

1466 assert( nList<=HASHTABLE_NPAGE && nList>0 );

1467 assert( HASHTABLE_NPAGE==(1<<(ArraySize(aSub)-1)) );

1468

1469 for(iList=0; iList<nList; iList++){

1470 nMerge = 1;

1471 aMerge = &aList[iList];

1472 for(iSub=0; iList & (1<<iSub); iSub++){

1473 struct Sublist *p = &aSub[iSub];

1474 assert( p->aList && p->nList<=(1<<iSub) );

1475 assert( p->aList==&aList[iList&~((2<<iSub)-1)] );

1476 walMerge(aContent, p->aList, p->nList, &aMerge, &nMerge, aBuffer);

1477 }

1478 aSub[iSub].aList = aMerge;

1479 aSub[iSub].nList = nMerge;

1480 }

1481

1482 for(iSub++; iSub<ArraySize(aSub); iSub++){

1483 if( nList & (1<<iSub) ){

1484 struct Sublist *p = &aSub[iSub];

1485 assert( p->nList<=(1<<iSub) );

1486 assert( p->aList==&aList[nList&~((2<<iSub)-1)] );

1487 walMerge(aContent, p->aList, p->nList, &aMerge, &nMerge, aBuffer);

1488 }

1489 }

1490 assert( aMerge==aList );

1491 *pnList = nMerge;

1492

1493 #ifdef SQLITE_DEBUG

1494 {

1495 int i;

1496 for(i=1; i<*pnList; i++){

1497 assert( aContent[aList[i]] > aContent[aList[i-1]] );

1498 }

1499 }

1500 #endif

1501 }

1502

1503 /*

1504 ** Free an iterator allocated by walIteratorInit().

1505 */

1506 static void walIteratorFree(WalIterator *p){

1507 sqlite3ScratchFree(p);

1508 }

1509

1510 /*

1511 ** Construct a WalInterator object that can be used to loop over all

1512 ** pages in the WAL in ascending order. The caller must hold the checkpoint

1513 ** lock.

1514 **

1515 ** On success, make *pp point to the newly allocated WalInterator object

1516 ** return SQLITE_OK. Otherwise, return an error code. If this routine

1517 ** returns an error, the value of *pp is undefined.

1518 **

1519 ** The calling routine should invoke walIteratorFree() to destroy the

1520 ** WalIterator object when it has finished with it.

1521 */

1522 static int walIteratorInit(Wal pWal, WalIterator *pp){

1523 WalIterator p; / Return value */

1524 int nSegment; /* Number of segments to merge */

1525 u32 iLast; /* Last frame in log */

1526 int nByte; /* Number of bytes to allocate */

1527 int i; /* Iterator variable */

1528 ht_slot aTmp; / Temp space used by merge-sort */

1529 int rc = SQLITE_OK; /* Return Code */

1530

1531 /* This routine only runs while holding the checkpoint lock. And

1532 ** it only runs if there is actually content in the log (mxFrame>0).

1533 */

1534 assert( pWal->ckptLock && pWal->hdr.mxFrame>0 );

1535 iLast = pWal->hdr.mxFrame;

1536

1537 /* Allocate space for the WalIterator object. */

1538 nSegment = walFramePage(iLast) + 1;

1539 nByte = sizeof(WalIterator)

1540 + (nSegment-1)*sizeof(struct WalSegment)

1541 + iLast*sizeof(ht_slot);

1542 p = (WalIterator *)sqlite3ScratchMalloc(nByte);

1543 if( !p ){

1544 return SQLITE_NOMEM;

1545 }

1546 memset(p, 0, nByte);

1547 p->nSegment = nSegment;

1548

1549 /* Allocate temporary space used by the merge-sort routine. This block

1550 ** of memory will be freed before this function returns.

1551 */

1552 aTmp = (ht_slot *)sqlite3ScratchMalloc(

1553 sizeof(ht_slot) * (iLast>HASHTABLE_NPAGE?HASHTABLE_NPAGE:iLast)

1554 );

1555 if( !aTmp ){

1556 rc = SQLITE_NOMEM;

1557 }

1558

1559 for(i=0; rc==SQLITE_OK && i<nSegment; i++){

1560 volatile ht_slot *aHash;

1561 u32 iZero;

1562 volatile u32 *aPgno;

1563

1564 rc = walHashGet(pWal, i, &aHash, &aPgno, &iZero);

1565 if( rc==SQLITE_OK ){

1566 int j; /* Counter variable */

1567 int nEntry; /* Number of entries in this segment */

1568 ht_slot aIndex; / Sorted index for this segment */

1569

1570 aPgno++;

1571 if( (i+1)==nSegment ){

1572 nEntry = (int)(iLast - iZero);

1573 }else{

1574 nEntry = (int)((u32)aHash - (u32)aPgno);

1575 }

1576 aIndex = &((ht_slot *)&p->aSegment[p->nSegment])[iZero];

1577 iZero++;

1578

1579 for(j=0; j<nEntry; j++){

1580 aIndex[j] = (ht_slot)j;

1581 }

1582 walMergesort((u32 *)aPgno, aTmp, aIndex, &nEntry);

1583 p->aSegment[i].iZero = iZero;

1584 p->aSegment[i].nEntry = nEntry;

1585 p->aSegment[i].aIndex = aIndex;

1586 p->aSegment[i].aPgno = (u32 *)aPgno;

1587 }

1588 }

1589 sqlite3ScratchFree(aTmp);

1590

1591 if( rc!=SQLITE_OK ){

1592 walIteratorFree(p);

1593 }

1594 *pp = p;

1595 return rc;

1596 }

1597

1598 /*

1599 ** Attempt to obtain the exclusive WAL lock defined by parameters lockIdx and

1600 ** n. If the attempt fails and parameter xBusy is not NULL, then it is a

1601 ** busy-handler function. Invoke it and retry the lock until either the

1602 ** lock is successfully obtained or the busy-handler returns 0.

1603 */

1604 static int walBusyLock(

1605 Wal pWal, / WAL connection */

1606 int (xBusy)(void), /* Function to call when busy */

1607 void pBusyArg, / Context argument for xBusyHandler */

1608 int lockIdx, /* Offset of first byte to lock */

1609 int n /* Number of bytes to lock */

1610 ){

1611 int rc;

1612 do {

1613 rc = walLockExclusive(pWal, lockIdx, n);

1614 }while( xBusy && rc==SQLITE_BUSY && xBusy(pBusyArg) );

1615 return rc;

1616 }

1617

1618 /*

1619 ** The cache of the wal-index header must be valid to call this function.

1620 ** Return the page-size in bytes used by the database.

1621 */

1622 static int walPagesize(Wal *pWal){

1623 return (pWal->hdr.szPage&0xfe00) + ((pWal->hdr.szPage&0x0001)<<16);

1624 }

1625

1626 /*

1627 ** Copy as much content as we can from the WAL back into the database file

1628 ** in response to an sqlite3_wal_checkpoint() request or the equivalent.

1629 **

1630 ** The amount of information copies from WAL to database might be limited

1631 ** by active readers. This routine will never overwrite a database page

1632 ** that a concurrent reader might be using.

1633 **

1634 ** All I/O barrier operations (a.k.a fsyncs) occur in this routine when

1635 ** SQLite is in WAL-mode in synchronous=NORMAL. That means that if

1636 ** checkpoints are always run by a background thread or background

1637 ** process, foreground threads will never block on a lengthy fsync call.

1638 **

1639 ** Fsync is called on the WAL before writing content out of the WAL and

1640 ** into the database. This ensures that if the new content is persistent

1641 ** in the WAL and can be recovered following a power-loss or hard reset.

1642 **

1643 ** Fsync is also called on the database file if (and only if) the entire

1644 ** WAL content is copied into the database file. This second fsync makes

1645 ** it safe to delete the WAL since the new content will persist in the

1646 ** database file.

1647 **

1648 ** This routine uses and updates the nBackfill field of the wal-index header.

1649 ** This is the only routine that will increase the value of nBackfill.

1650 ** (A WAL reset or recovery will revert nBackfill to zero, but not increase

1651 ** its value.)

1652 **

1653 ** The caller must be holding sufficient locks to ensure that no other

1654 ** checkpoint is running (in any other thread or process) at the same

1655 ** time.

1656 */

1657 static int walCheckpoint(

1658 Wal pWal, / Wal connection */

1659 int eMode, /* One of PASSIVE, FULL or RESTART */

1660 int (xBusyCall)(void), /* Function to call when busy */

1661 void pBusyArg, / Context argument for xBusyHandler */

1662 int sync_flags, /* Flags for OsSync() (or 0) */

1663 u8 zBuf / Temporary buffer to use */

1664 ){

1665 int rc; /* Return code */

1666 int szPage; /* Database page-size */

1667 WalIterator pIter = 0; / Wal iterator context */

1668 u32 iDbpage = 0; /* Next database page to write */

1669 u32 iFrame = 0; /* Wal frame containing data for iDbpage */

1670 u32 mxSafeFrame; /* Max frame that can be backfilled */

1671 u32 mxPage; /* Max database page to write */

1672 int i; /* Loop counter */

1673 volatile WalCkptInfo pInfo; / The checkpoint status information */

1674 int (xBusy)(void) = 0; /* Function to call when waiting for locks */

1675

1676 szPage = walPagesize(pWal);

1677 testcase( szPage<=32768 );

1678 testcase( szPage>=65536 );

1679 pInfo = walCkptInfo(pWal);

1680 if( pInfo->nBackfill>=pWal->hdr.mxFrame ) return SQLITE_OK;

1681

1682 /* Allocate the iterator */

1683 rc = walIteratorInit(pWal, &pIter);

1684 if( rc!=SQLITE_OK ){

1685 return rc;

1686 }

1687 assert( pIter );

1688

1689 if( eMode!=SQLITE_CHECKPOINT_PASSIVE ) xBusy = xBusyCall;

1690

1691 /* Compute in mxSafeFrame the index of the last frame of the WAL that is

1692 ** safe to write into the database. Frames beyond mxSafeFrame might

1693 ** overwrite database pages that are in use by active readers and thus

1694 ** cannot be backfilled from the WAL.

1695 */

1696 mxSafeFrame = pWal->hdr.mxFrame;

1697 mxPage = pWal->hdr.nPage;

1698 for(i=1; i<WAL_NREADER; i++){

1699 u32 y = pInfo->aReadMark[i];

1700 if( mxSafeFrame>y ){

1701 assert( y<=pWal->hdr.mxFrame );

1702 rc = walBusyLock(pWal, xBusy, pBusyArg, WAL_READ_LOCK(i), 1);

1703 if( rc==SQLITE_OK ){

1704 pInfo->aReadMark[i] = (i==1 ? mxSafeFrame : READMARK_NOT_USED);

1705 walUnlockExclusive(pWal, WAL_READ_LOCK(i), 1);

1706 }else if( rc==SQLITE_BUSY ){

1707 mxSafeFrame = y;

1708 xBusy = 0;

1709 }else{

1710 goto walcheckpoint_out;

1711 }

1712 }

1713 }

1714

1715 if( pInfo->nBackfill<mxSafeFrame

1716 && (rc = walBusyLock(pWal, xBusy, pBusyArg, WAL_READ_LOCK(0), 1))==SQLITE_OK

1717 ){

1718 i64 nSize; /* Current size of database file */

1719 u32 nBackfill = pInfo->nBackfill;

1720

1721 /* Sync the WAL to disk */

1722 if( sync_flags ){

1723 rc = sqlite3OsSync(pWal->pWalFd, sync_flags);

1724 }

1725

1726 /* If the database may grow as a result of this checkpoint, hint

1727 ** about the eventual size of the db file to the VFS layer.

1728 */

1729 if( rc==SQLITE_OK ){

1730 i64 nReq = ((i64)mxPage * szPage);

1731 rc = sqlite3OsFileSize(pWal->pDbFd, &nSize);

1732 if( rc==SQLITE_OK && nSize<nReq ){

1733 sqlite3OsFileControlHint(pWal->pDbFd, SQLITE_FCNTL_SIZE_HINT, &nReq);

1734 }

1735 }

1736

1737

1738 /* Iterate through the contents of the WAL, copying data to the db file. */

1739 while( rc==SQLITE_OK && 0==walIteratorNext(pIter, &iDbpage, &iFrame) ){

1740 i64 iOffset;

1741 assert( walFramePgno(pWal, iFrame)==iDbpage );

1742 if( iFrame<=nBackfill \|\| iFrame>mxSafeFrame \|\| iDbpage>mxPage ) continue;

1743 iOffset = walFrameOffset(iFrame, szPage) + WAL_FRAME_HDRSIZE;

1744 /* testcase( IS_BIG_INT(iOffset) ); // requires a 4GiB WAL file */

1745 rc = sqlite3OsRead(pWal->pWalFd, zBuf, szPage, iOffset);

1746 if( rc!=SQLITE_OK ) break;

1747 iOffset = (iDbpage-1)*(i64)szPage;

1748 testcase( IS_BIG_INT(iOffset) );

1749 rc = sqlite3OsWrite(pWal->pDbFd, zBuf, szPage, iOffset);

1750 if( rc!=SQLITE_OK ) break;

1751 }

1752

1753 /* If work was actually accomplished... */

1754 if( rc==SQLITE_OK ){

1755 if( mxSafeFrame==walIndexHdr(pWal)->mxFrame ){

1756 i64 szDb = pWal->hdr.nPage*(i64)szPage;

1757 testcase( IS_BIG_INT(szDb) );

1758 rc = sqlite3OsTruncate(pWal->pDbFd, szDb);

1759 if( rc==SQLITE_OK && sync_flags ){

1760 rc = sqlite3OsSync(pWal->pDbFd, sync_flags);

1761 }

1762 }

1763 if( rc==SQLITE_OK ){

1764 pInfo->nBackfill = mxSafeFrame;

1765 }

1766 }

1767

1768 /* Release the reader lock held while backfilling */

1769 walUnlockExclusive(pWal, WAL_READ_LOCK(0), 1);

1770 }

1771

1772 if( rc==SQLITE_BUSY ){

1773 /* Reset the return code so as not to report a checkpoint failure

1774 ** just because there are active readers. */

1775 rc = SQLITE_OK;

1776 }

1777

1778 /* If this is an SQLITE_CHECKPOINT_RESTART operation, and the entire wal

1779 ** file has been copied into the database file, then block until all

1780 ** readers have finished using the wal file. This ensures that the next

1781 ** process to write to the database restarts the wal file.

1782 */

1783 if( rc==SQLITE_OK && eMode!=SQLITE_CHECKPOINT_PASSIVE ){

1784 assert( pWal->writeLock );

1785 if( pInfo->nBackfill<pWal->hdr.mxFrame ){

1786 rc = SQLITE_BUSY;

1787 }else if( eMode==SQLITE_CHECKPOINT_RESTART ){

1788 assert( mxSafeFrame==pWal->hdr.mxFrame );

1789 rc = walBusyLock(pWal, xBusy, pBusyArg, WAL_READ_LOCK(1), WAL_NREADER-1);

1790 if( rc==SQLITE_OK ){

1791 walUnlockExclusive(pWal, WAL_READ_LOCK(1), WAL_NREADER-1);

1792 }

1793 }

1794 }

1795

1796 walcheckpoint_out:

1797 walIteratorFree(pIter);

1798 return rc;

1799 }

1800

1801 /*

1802 ** If the WAL file is currently larger than nMax bytes in size, truncate

1803 ** it to exactly nMax bytes. If an error occurs while doing so, ignore it.

1804 */

1805 static void walLimitSize(Wal *pWal, i64 nMax){

1806 i64 sz;

1807 int rx;

1808 sqlite3BeginBenignMalloc();

1809 rx = sqlite3OsFileSize(pWal->pWalFd, &sz);

1810 if( rx==SQLITE_OK && (sz > nMax ) ){

1811 rx = sqlite3OsTruncate(pWal->pWalFd, nMax);

1812 }

1813 sqlite3EndBenignMalloc();

1814 if( rx ){

1815 sqlite3_log(rx, "cannot limit WAL size: %s", pWal->zWalName);

1816 }

1817 }

1818

1819 /*

1820 ** Close a connection to a log file.

1821 */

1822 int sqlite3WalClose(

1823 Wal pWal, / Wal to close */

1824 int sync_flags, /* Flags to pass to OsSync() (or 0) */

1825 int nBuf,

1826 u8 zBuf / Buffer of at least nBuf bytes */

1827 ){

1828 int rc = SQLITE_OK;

1829 if( pWal ){

1830 int isDelete = 0; /* True to unlink wal and wal-index files */

1831

1832 /* If an EXCLUSIVE lock can be obtained on the database file (using the

1833 ** ordinary, rollback-mode locking methods, this guarantees that the

1834 ** connection associated with this log file is the only connection to

1835 ** the database. In this case checkpoint the database and unlink both

1836 ** the wal and wal-index files.

1837 **

1838 ** The EXCLUSIVE lock is not released before returning.

1839 */

1840 rc = sqlite3OsLock(pWal->pDbFd, SQLITE_LOCK_EXCLUSIVE);

1841 if( rc==SQLITE_OK ){

1842 if( pWal->exclusiveMode==WAL_NORMAL_MODE ){

1843 pWal->exclusiveMode = WAL_EXCLUSIVE_MODE;

1844 }

1845 rc = sqlite3WalCheckpoint(

1846 pWal, SQLITE_CHECKPOINT_PASSIVE, 0, 0, sync_flags, nBuf, zBuf, 0, 0

1847 );

1848 if( rc==SQLITE_OK ){

1849 int bPersist = -1;

1850 sqlite3OsFileControlHint(

1851 pWal->pDbFd, SQLITE_FCNTL_PERSIST_WAL, &bPersist

1852 );

1853 if( bPersist!=1 ){

1854 /* Try to delete the WAL file if the checkpoint completed and

1855 ** fsyned (rc==SQLITE_OK) and if we are not in persistent-wal

1856 ** mode (!bPersist) */

1857 isDelete = 1;

1858 }else if( pWal->mxWalSize>=0 ){

1859 /* Try to truncate the WAL file to zero bytes if the checkpoint

1860 ** completed and fsynced (rc==SQLITE_OK) and we are in persistent

1861 ** WAL mode (bPersist) and if the PRAGMA journal_size_limit is a

1862 ** non-negative value (pWal->mxWalSize>=0). Note that we truncate

1863 ** to zero bytes as truncating to the journal_size_limit might

1864 ** leave a corrupt WAL file on disk. */

1865 walLimitSize(pWal, 0);

1866 }

1867 }

1868 }

1869

1870 walIndexClose(pWal, isDelete);

1871 sqlite3OsClose(pWal->pWalFd);

1872 if( isDelete ){

1873 sqlite3BeginBenignMalloc();

1874 sqlite3OsDelete(pWal->pVfs, pWal->zWalName, 0);

1875 sqlite3EndBenignMalloc();

1876 }

1877 WALTRACE(("WAL%p: closed\n", pWal));

1878 sqlite3_free((void *)pWal->apWiData);

1879 sqlite3_free(pWal);

1880 }

1881 return rc;

1882 }

1883

1884 /*

1885 ** Try to read the wal-index header. Return 0 on success and 1 if

1886 ** there is a problem.

1887 **

1888 ** The wal-index is in shared memory. Another thread or process might

1889 ** be writing the header at the same time this procedure is trying to

1890 ** read it, which might result in inconsistency. A dirty read is detected

1891 ** by verifying that both copies of the header are the same and also by

1892 ** a checksum on the header.

1893 **

1894 ** If and only if the read is consistent and the header is different from

1895 ** pWal->hdr, then pWal->hdr is updated to the content of the new header

1896 ** and *pChanged is set to 1.

1897 **

1898 ** If the checksum cannot be verified return non-zero. If the header

1899 ** is read successfully and the checksum verified, return zero.

1900 */

1901 static int walIndexTryHdr(Wal pWal, int pChanged){

1902 u32 aCksum[2]; /* Checksum on the header content */

1903 WalIndexHdr h1, h2; /* Two copies of the header content */

1904 WalIndexHdr volatile aHdr; / Header in shared memory */

1905

1906 /* The first page of the wal-index must be mapped at this point. */

1907 assert( pWal->nWiData>0 && pWal->apWiData[0] );

1908

1909 /* Read the header. This might happen concurrently with a write to the

1910 ** same area of shared memory on a different CPU in a SMP,

1911 ** meaning it is possible that an inconsistent snapshot is read

1912 ** from the file. If this happens, return non-zero.

1913 **

1914 ** There are two copies of the header at the beginning of the wal-index.

1915 ** When reading, read [0] first then [1]. Writes are in the reverse order.

1916 ** Memory barriers are used to prevent the compiler or the hardware from

1917 ** reordering the reads and writes.

1918 */

1919 aHdr = walIndexHdr(pWal);

1920 memcpy(&h1, (void *)&aHdr[0], sizeof(h1));

1921 walShmBarrier(pWal);

1922 memcpy(&h2, (void *)&aHdr[1], sizeof(h2));

1923

1924 if( memcmp(&h1, &h2, sizeof(h1))!=0 ){

1925 return 1; /* Dirty read */

1926 }

1927 if( h1.isInit==0 ){

1928 return 1; /* Malformed header - probably all zeros */

1929 }

1930 walChecksumBytes(1, (u8*)&h1, sizeof(h1)-sizeof(h1.aCksum), 0, aCksum);

1931 if( aCksum[0]!=h1.aCksum[0] \|\| aCksum[1]!=h1.aCksum[1] ){

1932 return 1; /* Checksum does not match */

1933 }

1934

1935 if( memcmp(&pWal->hdr, &h1, sizeof(WalIndexHdr)) ){

1936 *pChanged = 1;

1937 memcpy(&pWal->hdr, &h1, sizeof(WalIndexHdr));

1938 pWal->szPage = (pWal->hdr.szPage&0xfe00) + ((pWal->hdr.szPage&0x0001)<<16);

1939 testcase( pWal->szPage<=32768 );

1940 testcase( pWal->szPage>=65536 );

1941 }

1942

1943 /* The header was successfully read. Return zero. */

1944 return 0;

1945 }

1946

1947 /*

1948 ** Read the wal-index header from the wal-index and into pWal->hdr.

1949 ** If the wal-header appears to be corrupt, try to reconstruct the

1950 ** wal-index from the WAL before returning.

1951 **

1952 ** Set *pChanged to 1 if the wal-index header value in pWal->hdr is

1953 ** changed by this operation. If pWal->hdr is unchanged, set *pChanged

1954 ** to 0.

1955 **

1956 ** If the wal-index header is successfully read, return SQLITE_OK.

1957 ** Otherwise an SQLite error code.

1958 */

1959 static int walIndexReadHdr(Wal pWal, int pChanged){

1960 int rc; /* Return code */

1961 int badHdr; /* True if a header read failed */

1962 volatile u32 page0; / Chunk of wal-index containing header */

1963

1964 /* Ensure that page 0 of the wal-index (the page that contains the

1965 ** wal-index header) is mapped. Return early if an error occurs here.

1966 */

1967 assert( pChanged );

1968 rc = walIndexPage(pWal, 0, &page0);

1969 if( rc!=SQLITE_OK ){

1970 return rc;

1971 };

1972 assert( page0 \|\| pWal->writeLock==0 );

1973

1974 /* If the first page of the wal-index has been mapped, try to read the

1975 ** wal-index header immediately, without holding any lock. This usually

1976 ** works, but may fail if the wal-index header is corrupt or currently

1977 ** being modified by another thread or process.

1978 */

1979 badHdr = (page0 ? walIndexTryHdr(pWal, pChanged) : 1);

1980

1981 /* If the first attempt failed, it might have been due to a race

1982 ** with a writer. So get a WRITE lock and try again.

1983 */

1984 assert( badHdr==0 \|\| pWal->writeLock==0 );

1985 if( badHdr ){

1986 if( pWal->readOnly & WAL_SHM_RDONLY ){

1987 if( SQLITE_OK==(rc = walLockShared(pWal, WAL_WRITE_LOCK)) ){

1988 walUnlockShared(pWal, WAL_WRITE_LOCK);

1989 rc = SQLITE_READONLY_RECOVERY;

1990 }

1991 }else if( SQLITE_OK==(rc = walLockExclusive(pWal, WAL_WRITE_LOCK, 1)) ){

1992 pWal->writeLock = 1;

1993 if( SQLITE_OK==(rc = walIndexPage(pWal, 0, &page0)) ){

1994 badHdr = walIndexTryHdr(pWal, pChanged);

1995 if( badHdr ){

1996 /* If the wal-index header is still malformed even while holding

1997 ** a WRITE lock, it can only mean that the header is corrupted and

1998 ** needs to be reconstructed. So run recovery to do exactly that.

1999 */

2000 rc = walIndexRecover(pWal);

2001 *pChanged = 1;

2002 }

2003 }

2004 pWal->writeLock = 0;

2005 walUnlockExclusive(pWal, WAL_WRITE_LOCK, 1);

2006 }

2007 }

2008

2009 /* If the header is read successfully, check the version number to make

2010 ** sure the wal-index was not constructed with some future format that

2011 ** this version of SQLite cannot understand.

2012 */

2013 if( badHdr==0 && pWal->hdr.iVersion!=WALINDEX_MAX_VERSION ){

2014 rc = SQLITE_CANTOPEN_BKPT;

2015 }

2016

2017 return rc;

2018 }

2019

2020 /*

2021 ** This is the value that walTryBeginRead returns when it needs to

2022 ** be retried.

2023 */

2024 #define WAL_RETRY (-1)

2025

2026 /*

2027 ** Attempt to start a read transaction. This might fail due to a race or

2028 ** other transient condition. When that happens, it returns WAL_RETRY to

2029 ** indicate to the caller that it is safe to retry immediately.

2030 **

2031 ** On success return SQLITE_OK. On a permanent failure (such an

2032 ** I/O error or an SQLITE_BUSY because another process is running

2033 ** recovery) return a positive error code.

2034 **

2035 ** The useWal parameter is true to force the use of the WAL and disable

2036 ** the case where the WAL is bypassed because it has been completely

2037 ** checkpointed. If useWal==0 then this routine calls walIndexReadHdr()

2038 ** to make a copy of the wal-index header into pWal->hdr. If the

2039 ** wal-index header has changed, *pChanged is set to 1 (as an indication

2040 ** to the caller that the local paget cache is obsolete and needs to be

2041 ** flushed.) When useWal==1, the wal-index header is assumed to already

2042 ** be loaded and the pChanged parameter is unused.

2043 **

2044 ** The caller must set the cnt parameter to the number of prior calls to

2045 ** this routine during the current read attempt that returned WAL_RETRY.

2046 ** This routine will start taking more aggressive measures to clear the

2047 ** race conditions after multiple WAL_RETRY returns, and after an excessive

2048 ** number of errors will ultimately return SQLITE_PROTOCOL. The

2049 ** SQLITE_PROTOCOL return indicates that some other process has gone rogue

2050 ** and is not honoring the locking protocol. There is a vanishingly small

2051 ** chance that SQLITE_PROTOCOL could be returned because of a run of really

2052 ** bad luck when there is lots of contention for the wal-index, but that

2053 ** possibility is so small that it can be safely neglected, we believe.

2054 **

2055 ** On success, this routine obtains a read lock on

2056 ** WAL_READ_LOCK(pWal->readLock). The pWal->readLock integer is

2057 ** in the range 0 <= pWal->readLock < WAL_NREADER. If pWal->readLock==(-1)

2058 ** that means the Wal does not hold any read lock. The reader must not

2059 ** access any database page that is modified by a WAL frame up to and

2060 ** including frame number aReadMark[pWal->readLock]. The reader will

2061 ** use WAL frames up to and including pWal->hdr.mxFrame if pWal->readLock>0

2062 ** Or if pWal->readLock==0, then the reader will ignore the WAL

2063 ** completely and get all content directly from the database file.

2064 ** If the useWal parameter is 1 then the WAL will never be ignored and

2065 ** this routine will always set pWal->readLock>0 on success.

2066 ** When the read transaction is completed, the caller must release the

2067 ** lock on WAL_READ_LOCK(pWal->readLock) and set pWal->readLock to -1.

2068 **

2069 ** This routine uses the nBackfill and aReadMark[] fields of the header

2070 ** to select a particular WAL_READ_LOCK() that strives to let the

2071 ** checkpoint process do as much work as possible. This routine might

2072 ** update values of the aReadMark[] array in the header, but if it does

2073 ** so it takes care to hold an exclusive lock on the corresponding

2074 ** WAL_READ_LOCK() while changing values.

2075 */

2076 static int walTryBeginRead(Wal pWal, int pChanged, int useWal, int cnt){

2077 volatile WalCkptInfo pInfo; / Checkpoint information in wal-index */

2078 u32 mxReadMark; /* Largest aReadMark[] value */

2079 int mxI; /* Index of largest aReadMark[] value */

2080 int i; /* Loop counter */

2081 int rc = SQLITE_OK; /* Return code */

2082

2083 assert( pWal->readLock<0 ); /* Not currently locked */

2084

2085 /* Take steps to avoid spinning forever if there is a protocol error.

2086 **

2087 ** Circumstances that cause a RETRY should only last for the briefest

2088 ** instances of time. No I/O or other system calls are done while the

2089 ** locks are held, so the locks should not be held for very long. But

2090 ** if we are unlucky, another process that is holding a lock might get

2091 ** paged out or take a page-fault that is time-consuming to resolve,

2092 ** during the few nanoseconds that it is holding the lock. In that case,

2093 ** it might take longer than normal for the lock to free.

2094 **

2095 ** After 5 RETRYs, we begin calling sqlite3OsSleep(). The first few

2096 ** calls to sqlite3OsSleep() have a delay of 1 microsecond. Really this

2097 ** is more of a scheduler yield than an actual delay. But on the 10th

2098 ** an subsequent retries, the delays start becoming longer and longer,

2099 ** so that on the 100th (and last) RETRY we delay for 323 milliseconds.

2100 ** The total delay time before giving up is less than 10 seconds.

2101 */

2102 if( cnt>5 ){

2103 int nDelay = 1; /* Pause time in microseconds */

2104 if( cnt>100 ){

2105 VVA_ONLY( pWal->lockError = 1; )

2106 return SQLITE_PROTOCOL;

2107 }

2108 if( cnt>=10 ) nDelay = (cnt-9)(cnt-9)39;

2109 sqlite3OsSleep(pWal->pVfs, nDelay);

2110 }

2111

2112 if( !useWal ){

2113 rc = walIndexReadHdr(pWal, pChanged);

2114 if( rc==SQLITE_BUSY ){

2115 /* If there is not a recovery running in another thread or process

2116 ** then convert BUSY errors to WAL_RETRY. If recovery is known to

2117 ** be running, convert BUSY to BUSY_RECOVERY. There is a race here

2118 ** which might cause WAL_RETRY to be returned even if BUSY_RECOVERY

2119 ** would be technically correct. But the race is benign since with

2120 ** WAL_RETRY this routine will be called again and will probably be

2121 ** right on the second iteration.

2122 */

2123 if( pWal->apWiData[0]==0 ){

2124 /* This branch is taken when the xShmMap() method returns SQLITE_BUSY.

2125 ** We assume this is a transient condition, so return WAL_RETRY. The

2126 ** xShmMap() implementation used by the default unix and win32 VFS

2127 ** modules may return SQLITE_BUSY due to a race condition in the

2128 ** code that determines whether or not the shared-memory region

2129 ** must be zeroed before the requested page is returned.

2130 */

2131 rc = WAL_RETRY;

2132 }else if( SQLITE_OK==(rc = walLockShared(pWal, WAL_RECOVER_LOCK)) ){

2133 walUnlockShared(pWal, WAL_RECOVER_LOCK);

2134 rc = WAL_RETRY;

2135 }else if( rc==SQLITE_BUSY ){

2136 rc = SQLITE_BUSY_RECOVERY;

2137 }

2138 }

2139 if( rc!=SQLITE_OK ){

2140 return rc;

2141 }

2142 }

2143

2144 pInfo = walCkptInfo(pWal);

2145 if( !useWal && pInfo->nBackfill==pWal->hdr.mxFrame ){

2146 /* The WAL has been completely backfilled (or it is empty).

2147 ** and can be safely ignored.

2148 */

2149 rc = walLockShared(pWal, WAL_READ_LOCK(0));

2150 walShmBarrier(pWal);

2151 if( rc==SQLITE_OK ){

2152 if( memcmp((void *)walIndexHdr(pWal), &pWal->hdr, sizeof(WalIndexHdr)) ){

2153 /* It is not safe to allow the reader to continue here if frames

2154 ** may have been appended to the log before READ_LOCK(0) was obtained.

2155 ** When holding READ_LOCK(0), the reader ignores the entire log file,

2156 ** which implies that the database file contains a trustworthy

2157 ** snapshot. Since holding READ_LOCK(0) prevents a checkpoint from

2158 ** happening, this is usually correct.

2159 **

2160 ** However, if frames have been appended to the log (or if the log

2161 ** is wrapped and written for that matter) before the READ_LOCK(0)

2162 ** is obtained, that is not necessarily true. A checkpointer may

2163 ** have started to backfill the appended frames but crashed before

2164 ** it finished. Leaving a corrupt image in the database file.

2165 */

2166 walUnlockShared(pWal, WAL_READ_LOCK(0));

2167 return WAL_RETRY;

2168 }

2169 pWal->readLock = 0;

2170 return SQLITE_OK;

2171 }else if( rc!=SQLITE_BUSY ){

2172 return rc;

2173 }

2174 }

2175

2176 /* If we get this far, it means that the reader will want to use

2177 ** the WAL to get at content from recent commits. The job now is

2178 ** to select one of the aReadMark[] entries that is closest to

2179 ** but not exceeding pWal->hdr.mxFrame and lock that entry.

2180 */

2181 mxReadMark = 0;

2182 mxI = 0;

2183 for(i=1; i<WAL_NREADER; i++){

2184 u32 thisMark = pInfo->aReadMark[i];

2185 if( mxReadMark<=thisMark && thisMark<=pWal->hdr.mxFrame ){

2186 assert( thisMark!=READMARK_NOT_USED );

2187 mxReadMark = thisMark;

2188 mxI = i;

2189 }

2190 }

2191 /* There was once an "if" here. The extra "{" is to preserve indentation. */

2192 {

2193 if( (pWal->readOnly & WAL_SHM_RDONLY)==0

2194 && (mxReadMark<pWal->hdr.mxFrame \|\| mxI==0)

2195 ){

2196 for(i=1; i<WAL_NREADER; i++){

2197 rc = walLockExclusive(pWal, WAL_READ_LOCK(i), 1);

2198 if( rc==SQLITE_OK ){

2199 mxReadMark = pInfo->aReadMark[i] = pWal->hdr.mxFrame;

2200 mxI = i;

2201 walUnlockExclusive(pWal, WAL_READ_LOCK(i), 1);

2202 break;

2203 }else if( rc!=SQLITE_BUSY ){

2204 return rc;

2205 }

2206 }

2207 }

2208 if( mxI==0 ){

2209 assert( rc==SQLITE_BUSY \|\| (pWal->readOnly & WAL_SHM_RDONLY)!=0 );

2210 return rc==SQLITE_BUSY ? WAL_RETRY : SQLITE_READONLY_CANTLOCK;

2211 }

2212

2213 rc = walLockShared(pWal, WAL_READ_LOCK(mxI));

2214 if( rc ){

2215 return rc==SQLITE_BUSY ? WAL_RETRY : rc;

2216 }

2217 /* Now that the read-lock has been obtained, check that neither the

2218 ** value in the aReadMark[] array or the contents of the wal-index

2219 ** header have changed.

2220 **

2221 ** It is necessary to check that the wal-index header did not change

2222 ** between the time it was read and when the shared-lock was obtained

2223 ** on WAL_READ_LOCK(mxI) was obtained to account for the possibility

2224 ** that the log file may have been wrapped by a writer, or that frames

2225 ** that occur later in the log than pWal->hdr.mxFrame may have been

2226 ** copied into the database by a checkpointer. If either of these things

2227 ** happened, then reading the database with the current value of

2228 ** pWal->hdr.mxFrame risks reading a corrupted snapshot. So, retry

2229 ** instead.

2230 **

2231 ** This does not guarantee that the copy of the wal-index header is up to

2232 ** date before proceeding. That would not be possible without somehow

2233 ** blocking writers. It only guarantees that a dangerous checkpoint or

2234 ** log-wrap (either of which would require an exclusive lock on

2235 ** WAL_READ_LOCK(mxI)) has not occurred since the snapshot was valid.

2236 */

2237 walShmBarrier(pWal);

2238 if( pInfo->aReadMark[mxI]!=mxReadMark

2239 \|\| memcmp((void *)walIndexHdr(pWal), &pWal->hdr, sizeof(WalIndexHdr))

2240 ){

2241 walUnlockShared(pWal, WAL_READ_LOCK(mxI));

2242 return WAL_RETRY;

2243 }else{

2244 assert( mxReadMark<=pWal->hdr.mxFrame );

2245 pWal->readLock = (i16)mxI;

2246 }

2247 }

2248 return rc;

2249 }

2250

2251 /*

2252 ** Begin a read transaction on the database.

2253 **

2254 ** This routine used to be called sqlite3OpenSnapshot() and with good reason:

2255 ** it takes a snapshot of the state of the WAL and wal-index for the current

2256 ** instant in time. The current thread will continue to use this snapshot.

2257 ** Other threads might append new content to the WAL and wal-index but

2258 ** that extra content is ignored by the current thread.

2259 **

2260 ** If the database contents have changes since the previous read

2261 ** transaction, then *pChanged is set to 1 before returning. The

2262 ** Pager layer will use this to know that is cache is stale and

2263 ** needs to be flushed.

2264 */

2265 int sqlite3WalBeginReadTransaction(Wal pWal, int pChanged){

2266 int rc; /* Return code */

2267 int cnt = 0; /* Number of TryBeginRead attempts */

2268

2269 do{

2270 rc = walTryBeginRead(pWal, pChanged, 0, ++cnt);

2271 }while( rc==WAL_RETRY );

2272 testcase( (rc&0xff)==SQLITE_BUSY );

2273 testcase( (rc&0xff)==SQLITE_IOERR );

2274 testcase( rc==SQLITE_PROTOCOL );

2275 testcase( rc==SQLITE_OK );

2276 return rc;

2277 }

2278

2279 /*

2280 ** Finish with a read transaction. All this does is release the

2281 ** read-lock.

2282 */

2283 void sqlite3WalEndReadTransaction(Wal *pWal){

2284 sqlite3WalEndWriteTransaction(pWal);

2285 if( pWal->readLock>=0 ){

2286 walUnlockShared(pWal, WAL_READ_LOCK(pWal->readLock));

2287 pWal->readLock = -1;

2288 }

2289 }

2290

2291 /*

2292 ** Search the wal file for page pgno. If found, set *piRead to the frame that

2293 ** contains the page. Otherwise, if pgno is not in the wal file, set *piRead

2294 ** to zero.

2295 **

2296 ** Return SQLITE_OK if successful, or an error code if an error occurs. If an

2297 ** error does occur, the final value of *piRead is undefined.

2298 */

2299 int sqlite3WalFindFrame(

2300 Wal pWal, / WAL handle */

2301 Pgno pgno, /* Database page number to read data for */

2302 u32 piRead / OUT: Frame number (or zero) */

2303 ){

2304 u32 iRead = 0; /* If !=0, WAL frame to return data from */

2305 u32 iLast = pWal->hdr.mxFrame; /* Last page in WAL for this reader */

2306 int iHash; /* Used to loop through N hash tables */

2307

2308 /* This routine is only be called from within a read transaction. */

2309 assert( pWal->readLock>=0 \|\| pWal->lockError );

2310

2311 /* If the "last page" field of the wal-index header snapshot is 0, then

2312 ** no data will be read from the wal under any circumstances. Return early

2313 ** in this case as an optimization. Likewise, if pWal->readLock==0,

2314 ** then the WAL is ignored by the reader so return early, as if the

2315 ** WAL were empty.

2316 */

2317 if( iLast==0 \|\| pWal->readLock==0 ){

2318 *piRead = 0;

2319 return SQLITE_OK;

2320 }

2321

2322 /* Search the hash table or tables for an entry matching page number

2323 ** pgno. Each iteration of the following for() loop searches one

2324 ** hash table (each hash table indexes up to HASHTABLE_NPAGE frames).

2325 **

2326 ** This code might run concurrently to the code in walIndexAppend()

2327 ** that adds entries to the wal-index (and possibly to this hash

2328 ** table). This means the value just read from the hash

2329 ** slot (aHash[iKey]) may have been added before or after the

2330 ** current read transaction was opened. Values added after the

2331 ** read transaction was opened may have been written incorrectly -

2332 ** i.e. these slots may contain garbage data. However, we assume

2333 ** that any slots written before the current read transaction was

2334 ** opened remain unmodified.

2335 **

2336 ** For the reasons above, the if(...) condition featured in the inner

2337 ** loop of the following block is more stringent that would be required

2338 ** if we had exclusive access to the hash-table:

2339 **

2340 ** (aPgno[iFrame]==pgno):

2341 ** This condition filters out normal hash-table collisions.

2342 **

2343 ** (iFrame<=iLast):

2344 ** This condition filters out entries that were added to the hash

2345 ** table after the current read-transaction had started.

2346 */

2347 for(iHash=walFramePage(iLast); iHash>=0 && iRead==0; iHash--){

2348 volatile ht_slot aHash; / Pointer to hash table */

2349 volatile u32 aPgno; / Pointer to array of page numbers */

2350 u32 iZero; /* Frame number corresponding to aPgno[0] */

2351 int iKey; /* Hash slot index */

2352 int nCollide; /* Number of hash collisions remaining */

2353 int rc; /* Error code */

2354

2355 rc = walHashGet(pWal, iHash, &aHash, &aPgno, &iZero);

2356 if( rc!=SQLITE_OK ){

2357 return rc;

2358 }

2359 nCollide = HASHTABLE_NSLOT;

2360 for(iKey=walHash(pgno); aHash[iKey]; iKey=walNextHash(iKey)){

2361 u32 iFrame = aHash[iKey] + iZero;

2362 if( iFrame<=iLast && aPgno[aHash[iKey]]==pgno ){

2363 /* assert( iFrame>iRead ); -- not true if there is corruption */

2364 iRead = iFrame;

2365 }

2366 if( (nCollide--)==0 ){

2367 return SQLITE_CORRUPT_BKPT;

2368 }

2369 }

2370 }

2371

2372 #ifdef SQLITE_ENABLE_EXPENSIVE_ASSERT

2373 /* If expensive assert() statements are available, do a linear search

2374 ** of the wal-index file content. Make sure the results agree with the

2375 ** result obtained using the hash indexes above. */

2376 {

2377 u32 iRead2 = 0;

2378 u32 iTest;

2379 for(iTest=iLast; iTest>0; iTest--){

2380 if( walFramePgno(pWal, iTest)==pgno ){

2381 iRead2 = iTest;

2382 break;

2383 }

2384 }

2385 assert( iRead==iRead2 );

2386 }

2387 #endif

2388

2389 *piRead = iRead;

2390 return SQLITE_OK;

2391 }

2392

2393 /*

2394 ** Read the contents of frame iRead from the wal file into buffer pOut

2395 ** (which is nOut bytes in size). Return SQLITE_OK if successful, or an

2396 ** error code otherwise.

2397 */

2398 int sqlite3WalReadFrame(

2399 Wal pWal, / WAL handle */

2400 u32 iRead, /* Frame to read */

2401 int nOut, /* Size of buffer pOut in bytes */

2402 u8 pOut / Buffer to write page data to */

2403 ){

2404 int sz;

2405 i64 iOffset;

2406 sz = pWal->hdr.szPage;

2407 sz = (sz&0xfe00) + ((sz&0x0001)<<16);

2408 testcase( sz<=32768 );

2409 testcase( sz>=65536 );

2410 iOffset = walFrameOffset(iRead, sz) + WAL_FRAME_HDRSIZE;

2411 /* testcase( IS_BIG_INT(iOffset) ); // requires a 4GiB WAL */

2412 return sqlite3OsRead(pWal->pWalFd, pOut, (nOut>sz ? sz : nOut), iOffset);

2413 }

2414

2415 /*

2416 ** Return the size of the database in pages (or zero, if unknown).

2417 */

2418 Pgno sqlite3WalDbsize(Wal *pWal){

2419 if( pWal && ALWAYS(pWal->readLock>=0) ){

2420 return pWal->hdr.nPage;

2421 }

2422 return 0;

2423 }

2424

2425

2426 /*

2427 ** This function starts a write transaction on the WAL.

2428 **

2429 ** A read transaction must have already been started by a prior call

2430 ** to sqlite3WalBeginReadTransaction().

2431 **

2432 ** If another thread or process has written into the database since

2433 ** the read transaction was started, then it is not possible for this

2434 ** thread to write as doing so would cause a fork. So this routine

2435 ** returns SQLITE_BUSY in that case and no write transaction is started.

2436 **

2437 ** There can only be a single writer active at a time.

2438 */

2439 int sqlite3WalBeginWriteTransaction(Wal *pWal){

2440 int rc;

2441

2442 /* Cannot start a write transaction without first holding a read

2443 ** transaction. */

2444 assert( pWal->readLock>=0 );

2445

2446 if( pWal->readOnly ){

2447 return SQLITE_READONLY;

2448 }

2449

2450 /* Only one writer allowed at a time. Get the write lock. Return

2451 ** SQLITE_BUSY if unable.

2452 */

2453 rc = walLockExclusive(pWal, WAL_WRITE_LOCK, 1);

2454 if( rc ){

2455 return rc;

2456 }

2457 pWal->writeLock = 1;

2458

2459 /* If another connection has written to the database file since the

2460 ** time the read transaction on this connection was started, then

2461 ** the write is disallowed.

2462 */

2463 if( memcmp(&pWal->hdr, (void *)walIndexHdr(pWal), sizeof(WalIndexHdr))!=0 ){

2464 walUnlockExclusive(pWal, WAL_WRITE_LOCK, 1);

2465 pWal->writeLock = 0;

2466 rc = SQLITE_BUSY_SNAPSHOT;

2467 }

2468

2469 return rc;

2470 }

2471

2472 /*

2473 ** End a write transaction. The commit has already been done. This

2474 ** routine merely releases the lock.

2475 */

2476 int sqlite3WalEndWriteTransaction(Wal *pWal){

2477 if( pWal->writeLock ){

2478 walUnlockExclusive(pWal, WAL_WRITE_LOCK, 1);

2479 pWal->writeLock = 0;

2480 pWal->truncateOnCommit = 0;

2481 }

2482 return SQLITE_OK;

2483 }

2484

2485 /*

2486 ** If any data has been written (but not committed) to the log file, this

2487 ** function moves the write-pointer back to the start of the transaction.

2488 **

2489 ** Additionally, the callback function is invoked for each frame written

2490 ** to the WAL since the start of the transaction. If the callback returns

2491 ** other than SQLITE_OK, it is not invoked again and the error code is

2492 ** returned to the caller.

2493 **

2494 ** Otherwise, if the callback function does not return an error, this

2495 ** function returns SQLITE_OK.

2496 */

2497 int sqlite3WalUndo(Wal pWal, int (xUndo)(void , Pgno), void pUndoCtx){

2498 int rc = SQLITE_OK;

2499 if( ALWAYS(pWal->writeLock) ){

2500 Pgno iMax = pWal->hdr.mxFrame;

2501 Pgno iFrame;

2502

2503 /* Restore the clients cache of the wal-index header to the state it

2504 ** was in before the client began writing to the database.

2505 */

2506 memcpy(&pWal->hdr, (void *)walIndexHdr(pWal), sizeof(WalIndexHdr));

2507

2508 for(iFrame=pWal->hdr.mxFrame+1;

2509 ALWAYS(rc==SQLITE_OK) && iFrame<=iMax;

2510 iFrame++

2511 ){

2512 /* This call cannot fail. Unless the page for which the page number

2513 ** is passed as the second argument is (a) in the cache and

2514 ** (b) has an outstanding reference, then xUndo is either a no-op

2515 ** (if (a) is false) or simply expels the page from the cache (if (b)

2516 ** is false).

2517 **

2518 ** If the upper layer is doing a rollback, it is guaranteed that there

2519 ** are no outstanding references to any page other than page 1. And

2520 ** page 1 is never written to the log until the transaction is

2521 ** committed. As a result, the call to xUndo may not fail.

2522 */

2523 assert( walFramePgno(pWal, iFrame)!=1 );

2524 rc = xUndo(pUndoCtx, walFramePgno(pWal, iFrame));

2525 }

2526 if( iMax!=pWal->hdr.mxFrame ) walCleanupHash(pWal);

2527 }

2528 return rc;

2529 }

2530

2531 /*

2532 ** Argument aWalData must point to an array of WAL_SAVEPOINT_NDATA u32

2533 ** values. This function populates the array with values required to

2534 ** "rollback" the write position of the WAL handle back to the current

2535 ** point in the event of a savepoint rollback (via WalSavepointUndo()).

2536 */

2537 void sqlite3WalSavepoint(Wal pWal, u32 aWalData){

2538 assert( pWal->writeLock );

2539 aWalData[0] = pWal->hdr.mxFrame;

2540 aWalData[1] = pWal->hdr.aFrameCksum[0];

2541 aWalData[2] = pWal->hdr.aFrameCksum[1];

2542 aWalData[3] = pWal->nCkpt;

2543 }

2544

2545 /*

2546 ** Move the write position of the WAL back to the point identified by

2547 ** the values in the aWalData[] array. aWalData must point to an array

2548 ** of WAL_SAVEPOINT_NDATA u32 values that has been previously populated

2549 ** by a call to WalSavepoint().

2550 */

2551 int sqlite3WalSavepointUndo(Wal pWal, u32 aWalData){

2552 int rc = SQLITE_OK;

2553

2554 assert( pWal->writeLock );

2555 assert( aWalData[3]!=pWal->nCkpt \|\| aWalData[0]<=pWal->hdr.mxFrame );

2556

2557 if( aWalData[3]!=pWal->nCkpt ){

2558 /* This savepoint was opened immediately after the write-transaction

2559 ** was started. Right after that, the writer decided to wrap around

2560 ** to the start of the log. Update the savepoint values to match.

2561 */

2562 aWalData[0] = 0;

2563 aWalData[3] = pWal->nCkpt;

2564 }

2565

2566 if( aWalData[0]<pWal->hdr.mxFrame ){

2567 pWal->hdr.mxFrame = aWalData[0];

2568 pWal->hdr.aFrameCksum[0] = aWalData[1];

2569 pWal->hdr.aFrameCksum[1] = aWalData[2];

2570 walCleanupHash(pWal);

2571 }

2572

2573 return rc;

2574 }

2575

2576

2577 /*

2578 ** This function is called just before writing a set of frames to the log

2579 ** file (see sqlite3WalFrames()). It checks to see if, instead of appending

2580 ** to the current log file, it is possible to overwrite the start of the

2581 ** existing log file with the new frames (i.e. "reset" the log). If so,

2582 ** it sets pWal->hdr.mxFrame to 0. Otherwise, pWal->hdr.mxFrame is left

2583 ** unchanged.

2584 **

2585 ** SQLITE_OK is returned if no error is encountered (regardless of whether

2586 ** or not pWal->hdr.mxFrame is modified). An SQLite error code is returned

2587 ** if an error occurs.

2588 */

2589 static int walRestartLog(Wal *pWal){

2590 int rc = SQLITE_OK;

2591 int cnt;

2592

2593 if( pWal->readLock==0 ){

2594 volatile WalCkptInfo *pInfo = walCkptInfo(pWal);

2595 assert( pInfo->nBackfill==pWal->hdr.mxFrame );

2596 if( pInfo->nBackfill>0 ){

2597 u32 salt1;

2598 sqlite3_randomness(4, &salt1);

2599 rc = walLockExclusive(pWal, WAL_READ_LOCK(1), WAL_NREADER-1);

2600 if( rc==SQLITE_OK ){

2601 /* If all readers are using WAL_READ_LOCK(0) (in other words if no

2602 ** readers are currently using the WAL), then the transactions

2603 ** frames will overwrite the start of the existing log. Update the

2604 ** wal-index header to reflect this.

2605 **

2606 ** In theory it would be Ok to update the cache of the header only

2607 ** at this point. But updating the actual wal-index header is also

2608 ** safe and means there is no special case for sqlite3WalUndo()

2609 ** to handle if this transaction is rolled back.

2610 */

2611 int i; /* Loop counter */

2612 u32 aSalt = pWal->hdr.aSalt; / Big-endian salt values */

2613

2614 pWal->nCkpt++;

2615 pWal->hdr.mxFrame = 0;

2616 sqlite3Put4byte((u8)&aSalt[0], 1 + sqlite3Get4byte((u8)&aSalt[0]));

2617 aSalt[1] = salt1;

2618 walIndexWriteHdr(pWal);

2619 pInfo->nBackfill = 0;

2620 pInfo->aReadMark[1] = 0;

2621 for(i=2; i<WAL_NREADER; i++) pInfo->aReadMark[i] = READMARK_NOT_USED;

2622 assert( pInfo->aReadMark[0]==0 );

2623 walUnlockExclusive(pWal, WAL_READ_LOCK(1), WAL_NREADER-1);

2624 }else if( rc!=SQLITE_BUSY ){

2625 return rc;

2626 }

2627 }

2628 walUnlockShared(pWal, WAL_READ_LOCK(0));

2629 pWal->readLock = -1;

2630 cnt = 0;

2631 do{

2632 int notUsed;

2633 rc = walTryBeginRead(pWal, &notUsed, 1, ++cnt);

2634 }while( rc==WAL_RETRY );

2635 assert( (rc&0xff)!=SQLITE_BUSY ); /* BUSY not possible when useWal==1 */

2636 testcase( (rc&0xff)==SQLITE_IOERR );

2637 testcase( rc==SQLITE_PROTOCOL );

2638 testcase( rc==SQLITE_OK );

2639 }

2640 return rc;

2641 }

2642

2643 /*

2644 ** Information about the current state of the WAL file and where

2645 ** the next fsync should occur - passed from sqlite3WalFrames() into

2646 ** walWriteToLog().

2647 */

2648 typedef struct WalWriter {

2649 Wal pWal; / The complete WAL information */

2650 sqlite3_file pFd; / The WAL file to which we write */

2651 sqlite3_int64 iSyncPoint; /* Fsync at this offset */

2652 int syncFlags; /* Flags for the fsync */

2653 int szPage; /* Size of one page */

2654 } WalWriter;

2655

2656 /*

2657 ** Write iAmt bytes of content into the WAL file beginning at iOffset.

2658 ** Do a sync when crossing the p->iSyncPoint boundary.

2659 **

2660 ** In other words, if iSyncPoint is in between iOffset and iOffset+iAmt,

2661 ** first write the part before iSyncPoint, then sync, then write the

2662 ** rest.

2663 */

2664 static int walWriteToLog(

2665 WalWriter p, / WAL to write to */

2666 void pContent, / Content to be written */

2667 int iAmt, /* Number of bytes to write */

2668 sqlite3_int64 iOffset /* Start writing at this offset */

2669 ){

2670 int rc;

2671 if( iOffset<p->iSyncPoint && iOffset+iAmt>=p->iSyncPoint ){

2672 int iFirstAmt = (int)(p->iSyncPoint - iOffset);

2673 rc = sqlite3OsWrite(p->pFd, pContent, iFirstAmt, iOffset);

2674 if( rc ) return rc;

2675 iOffset += iFirstAmt;

2676 iAmt -= iFirstAmt;

2677 pContent = (void)(iFirstAmt + (char)pContent);

2678 assert( p->syncFlags & (SQLITE_SYNC_NORMAL\|SQLITE_SYNC_FULL) );

2679 rc = sqlite3OsSync(p->pFd, p->syncFlags & SQLITE_SYNC_MASK);

2680 if( iAmt==0 \|\| rc ) return rc;

2681 }

2682 rc = sqlite3OsWrite(p->pFd, pContent, iAmt, iOffset);

2683 return rc;

2684 }

2685

2686 /*

2687 ** Write out a single frame of the WAL

2688 */

2689 static int walWriteOneFrame(

2690 WalWriter p, / Where to write the frame */

2691 PgHdr pPage, / The page of the frame to be written */

2692 int nTruncate, /* The commit flag. Usually 0. >0 for commit */

2693 sqlite3_int64 iOffset /* Byte offset at which to write */

2694 ){

2695 int rc; /* Result code from subfunctions */

2696 void pData; / Data actually written */

2697 u8 aFrame[WAL_FRAME_HDRSIZE]; /* Buffer to assemble frame-header in */

2698 #if defined(SQLITE_HAS_CODEC)

2699 if( (pData = sqlite3PagerCodec(pPage))==0 ) return SQLITE_NOMEM;

2700 #else

2701 pData = pPage->pData;

2702 #endif

2703 walEncodeFrame(p->pWal, pPage->pgno, nTruncate, pData, aFrame);

2704 rc = walWriteToLog(p, aFrame, sizeof(aFrame), iOffset);

2705 if( rc ) return rc;

2706 /* Write the page data */

2707 rc = walWriteToLog(p, pData, p->szPage, iOffset+sizeof(aFrame));

2708 return rc;

2709 }

2710

2711 /*

2712 ** Write a set of frames to the log. The caller must hold the write-lock

2713 ** on the log file (obtained using sqlite3WalBeginWriteTransaction()).

2714 */

2715 int sqlite3WalFrames(

2716 Wal pWal, / Wal handle to write to */

2717 int szPage, /* Database page-size in bytes */

2718 PgHdr pList, / List of dirty pages to write */

2719 Pgno nTruncate, /* Database size after this commit */

2720 int isCommit, /* True if this is a commit */

2721 int sync_flags /* Flags to pass to OsSync() (or 0) */

2722 ){

2723 int rc; /* Used to catch return codes */

2724 u32 iFrame; /* Next frame address */

2725 PgHdr p; / Iterator to run through pList with. */

2726 PgHdr pLast = 0; / Last frame in list */

2727 int nExtra = 0; /* Number of extra copies of last page */

2728 int szFrame; /* The size of a single frame */

2729 i64 iOffset; /* Next byte to write in WAL file */

2730 WalWriter w; /* The writer */

2731

2732 assert( pList );

2733 assert( pWal->writeLock );

2734

2735 /* If this frame set completes a transaction, then nTruncate>0. If

2736 ** nTruncate==0 then this frame set does not complete the transaction. */

2737 assert( (isCommit!=0)==(nTruncate!=0) );

2738

2739 #if defined(SQLITE_TEST) && defined(SQLITE_DEBUG)

2740 { int cnt; for(cnt=0, p=pList; p; p=p->pDirty, cnt++){}

2741 WALTRACE(("WAL%p: frame write begin. %d frames. mxFrame=%d. %s\n",

2742 pWal, cnt, pWal->hdr.mxFrame, isCommit ? "Commit" : "Spill"));

2743 }

2744 #endif

2745

2746 /* See if it is possible to write these frames into the start of the

2747 ** log file, instead of appending to it at pWal->hdr.mxFrame.

2748 */

2749 if( SQLITE_OK!=(rc = walRestartLog(pWal)) ){

2750 return rc;

2751 }

2752

2753 /* If this is the first frame written into the log, write the WAL

2754 ** header to the start of the WAL file. See comments at the top of

2755 ** this source file for a description of the WAL header format.

2756 */

2757 iFrame = pWal->hdr.mxFrame;

2758 if( iFrame==0 ){

2759 u8 aWalHdr[WAL_HDRSIZE]; /* Buffer to assemble wal-header in */

2760 u32 aCksum[2]; /* Checksum for wal-header */

2761

2762 sqlite3Put4byte(&aWalHdr[0], (WAL_MAGIC \| SQLITE_BIGENDIAN));

2763 sqlite3Put4byte(&aWalHdr[4], WAL_MAX_VERSION);

2764 sqlite3Put4byte(&aWalHdr[8], szPage);

2765 sqlite3Put4byte(&aWalHdr[12], pWal->nCkpt);

2766 if( pWal->nCkpt==0 ) sqlite3_randomness(8, pWal->hdr.aSalt);

2767 memcpy(&aWalHdr[16], pWal->hdr.aSalt, 8);

2768 walChecksumBytes(1, aWalHdr, WAL_HDRSIZE-2*4, 0, aCksum);

2769 sqlite3Put4byte(&aWalHdr[24], aCksum[0]);

2770 sqlite3Put4byte(&aWalHdr[28], aCksum[1]);

2771

2772 pWal->szPage = szPage;

2773 pWal->hdr.bigEndCksum = SQLITE_BIGENDIAN;

2774 pWal->hdr.aFrameCksum[0] = aCksum[0];

2775 pWal->hdr.aFrameCksum[1] = aCksum[1];

2776 pWal->truncateOnCommit = 1;

2777

2778 rc = sqlite3OsWrite(pWal->pWalFd, aWalHdr, sizeof(aWalHdr), 0);

2779 WALTRACE(("WAL%p: wal-header write %s\n", pWal, rc ? "failed" : "ok"));

2780 if( rc!=SQLITE_OK ){

2781 return rc;

2782 }

2783

2784 /* Sync the header (unless SQLITE_IOCAP_SEQUENTIAL is true or unless

2785 ** all syncing is turned off by PRAGMA synchronous=OFF). Otherwise

2786 ** an out-of-order write following a WAL restart could result in

2787 ** database corruption. See the ticket:

2788 **

2789 ** http://localhost:591/sqlite/info/ff5be73dee

2790 */

2791 if( pWal->syncHeader && sync_flags ){

2792 rc = sqlite3OsSync(pWal->pWalFd, sync_flags & SQLITE_SYNC_MASK);

2793 if( rc ) return rc;

2794 }

2795 }

2796 assert( (int)pWal->szPage==szPage );

2797

2798 /* Setup information needed to write frames into the WAL */

2799 w.pWal = pWal;

2800 w.pFd = pWal->pWalFd;

2801 w.iSyncPoint = 0;

2802 w.syncFlags = sync_flags;

2803 w.szPage = szPage;

2804 iOffset = walFrameOffset(iFrame+1, szPage);

2805 szFrame = szPage + WAL_FRAME_HDRSIZE;

2806

2807 /* Write all frames into the log file exactly once */

2808 for(p=pList; p; p=p->pDirty){

2809 int nDbSize; /* 0 normally. Positive == commit flag */

2810 iFrame++;

2811 assert( iOffset==walFrameOffset(iFrame, szPage) );

2812 nDbSize = (isCommit && p->pDirty==0) ? nTruncate : 0;

2813 rc = walWriteOneFrame(&w, p, nDbSize, iOffset);

2814 if( rc ) return rc;

2815 pLast = p;

2816 iOffset += szFrame;

2817 }

2818

2819 /* If this is the end of a transaction, then we might need to pad

2820 ** the transaction and/or sync the WAL file.

2821 **

2822 ** Padding and syncing only occur if this set of frames complete a

2823 ** transaction and if PRAGMA synchronous=FULL. If synchronous==NORMAL

2824 ** or synchronous==OFF, then no padding or syncing are needed.

2825 **

2826 ** If SQLITE_IOCAP_POWERSAFE_OVERWRITE is defined, then padding is not

2827 ** needed and only the sync is done. If padding is needed, then the

2828 ** final frame is repeated (with its commit mark) until the next sector

2829 ** boundary is crossed. Only the part of the WAL prior to the last

2830 ** sector boundary is synced; the part of the last frame that extends

2831 ** past the sector boundary is written after the sync.

2832 */

2833 if( isCommit && (sync_flags & WAL_SYNC_TRANSACTIONS)!=0 ){

2834 if( pWal->padToSectorBoundary ){

2835 int sectorSize = sqlite3SectorSize(pWal->pWalFd);

2836 w.iSyncPoint = ((iOffset+sectorSize-1)/sectorSize)*sectorSize;

2837 while( iOffset<w.iSyncPoint ){

2838 rc = walWriteOneFrame(&w, pLast, nTruncate, iOffset);

2839 if( rc ) return rc;

2840 iOffset += szFrame;

2841 nExtra++;

2842 }

2843 }else{

2844 rc = sqlite3OsSync(w.pFd, sync_flags & SQLITE_SYNC_MASK);

2845 }

2846 }

2847

2848 /* If this frame set completes the first transaction in the WAL and

2849 ** if PRAGMA journal_size_limit is set, then truncate the WAL to the

2850 ** journal size limit, if possible.

2851 */

2852 if( isCommit && pWal->truncateOnCommit && pWal->mxWalSize>=0 ){

2853 i64 sz = pWal->mxWalSize;

2854 if( walFrameOffset(iFrame+nExtra+1, szPage)>pWal->mxWalSize ){

2855 sz = walFrameOffset(iFrame+nExtra+1, szPage);

2856 }

2857 walLimitSize(pWal, sz);

2858 pWal->truncateOnCommit = 0;

2859 }

2860

2861 /* Append data to the wal-index. It is not necessary to lock the

2862 ** wal-index to do this as the SQLITE_SHM_WRITE lock held on the wal-index

2863 ** guarantees that there are no other writers, and no data that may

2864 ** be in use by existing readers is being overwritten.

2865 */

2866 iFrame = pWal->hdr.mxFrame;

2867 for(p=pList; p && rc==SQLITE_OK; p=p->pDirty){

2868 iFrame++;

2869 rc = walIndexAppend(pWal, iFrame, p->pgno);

2870 }

2871 while( rc==SQLITE_OK && nExtra>0 ){

2872 iFrame++;

2873 nExtra--;

2874 rc = walIndexAppend(pWal, iFrame, pLast->pgno);

2875 }

2876

2877 if( rc==SQLITE_OK ){

2878 /* Update the private copy of the header. */

2879 pWal->hdr.szPage = (u16)((szPage&0xff00) \| (szPage>>16));

2880 testcase( szPage<=32768 );

2881 testcase( szPage>=65536 );

2882 pWal->hdr.mxFrame = iFrame;

2883 if( isCommit ){

2884 pWal->hdr.iChange++;

2885 pWal->hdr.nPage = nTruncate;

2886 }

2887 /* If this is a commit, update the wal-index header too. */

2888 if( isCommit ){

2889 walIndexWriteHdr(pWal);

2890 pWal->iCallback = iFrame;

2891 }

2892 }

2893

2894 WALTRACE(("WAL%p: frame write %s\n", pWal, rc ? "failed" : "ok"));

2895 return rc;

2896 }

2897

2898 /*

2899 ** This routine is called to implement sqlite3_wal_checkpoint() and

2900 ** related interfaces.

2901 **

2902 ** Obtain a CHECKPOINT lock and then backfill as much information as

2903 ** we can from WAL into the database.

2904 **

2905 ** If parameter xBusy is not NULL, it is a pointer to a busy-handler

2906 ** callback. In this case this function runs a blocking checkpoint.

2907 */

2908 int sqlite3WalCheckpoint(

2909 Wal pWal, / Wal connection */

2910 int eMode, /* PASSIVE, FULL or RESTART */

2911 int (xBusy)(void), /* Function to call when busy */

2912 void pBusyArg, / Context argument for xBusyHandler */

2913 int sync_flags, /* Flags to sync db file with (or 0) */

2914 int nBuf, /* Size of temporary buffer */

2915 u8 zBuf, / Temporary buffer to use */

2916 int pnLog, / OUT: Number of frames in WAL */

2917 int pnCkpt / OUT: Number of backfilled frames in WAL */

2918 ){

2919 int rc; /* Return code */

2920 int isChanged = 0; /* True if a new wal-index header is loaded */

2921 int eMode2 = eMode; /* Mode to pass to walCheckpoint() */

2922

2923 assert( pWal->ckptLock==0 );

2924 assert( pWal->writeLock==0 );

2925

2926 if( pWal->readOnly ) return SQLITE_READONLY;

2927 WALTRACE(("WAL%p: checkpoint begins\n", pWal));

2928 rc = walLockExclusive(pWal, WAL_CKPT_LOCK, 1);

2929 if( rc ){

2930 /* Usually this is SQLITE_BUSY meaning that another thread or process

2931 ** is already running a checkpoint, or maybe a recovery. But it might

2932 ** also be SQLITE_IOERR. */

2933 return rc;

2934 }

2935 pWal->ckptLock = 1;

2936

2937 /* If this is a blocking-checkpoint, then obtain the write-lock as well

2938 ** to prevent any writers from running while the checkpoint is underway.

2939 ** This has to be done before the call to walIndexReadHdr() below.

2940 **

2941 ** If the writer lock cannot be obtained, then a passive checkpoint is

2942 ** run instead. Since the checkpointer is not holding the writer lock,

2943 ** there is no point in blocking waiting for any readers. Assuming no

2944 ** other error occurs, this function will return SQLITE_BUSY to the caller.

2945 */

2946 if( eMode!=SQLITE_CHECKPOINT_PASSIVE ){

2947 rc = walBusyLock(pWal, xBusy, pBusyArg, WAL_WRITE_LOCK, 1);

2948 if( rc==SQLITE_OK ){

2949 pWal->writeLock = 1;

2950 }else if( rc==SQLITE_BUSY ){

2951 eMode2 = SQLITE_CHECKPOINT_PASSIVE;

2952 rc = SQLITE_OK;

2953 }

2954 }

2955

2956 /* Read the wal-index header. */

2957 if( rc==SQLITE_OK ){

2958 rc = walIndexReadHdr(pWal, &isChanged);

2959 if( isChanged && pWal->pDbFd->pMethods->iVersion>=3 ){

2960 sqlite3OsUnfetch(pWal->pDbFd, 0, 0);

2961 }

2962 }

2963

2964 /* Copy data from the log to the database file. */

2965 if( rc==SQLITE_OK ){

2966 if( pWal->hdr.mxFrame && walPagesize(pWal)!=nBuf ){

2967 rc = SQLITE_CORRUPT_BKPT;

2968 }else{

2969 rc = walCheckpoint(pWal, eMode2, xBusy, pBusyArg, sync_flags, zBuf);

2970 }

2971

2972 /* If no error occurred, set the output variables. */

2973 if( rc==SQLITE_OK \|\| rc==SQLITE_BUSY ){

2974 if( pnLog ) *pnLog = (int)pWal->hdr.mxFrame;

2975 if( pnCkpt ) *pnCkpt = (int)(walCkptInfo(pWal)->nBackfill);

2976 }

2977 }

2978

2979 if( isChanged ){

2980 /* If a new wal-index header was loaded before the checkpoint was

2981 ** performed, then the pager-cache associated with pWal is now

2982 ** out of date. So zero the cached wal-index header to ensure that

2983 ** next time the pager opens a snapshot on this database it knows that

2984 ** the cache needs to be reset.

2985 */

2986 memset(&pWal->hdr, 0, sizeof(WalIndexHdr));

2987 }

2988

2989 /* Release the locks. */

2990 sqlite3WalEndWriteTransaction(pWal);

2991 walUnlockExclusive(pWal, WAL_CKPT_LOCK, 1);

2992 pWal->ckptLock = 0;

2993 WALTRACE(("WAL%p: checkpoint %s\n", pWal, rc ? "failed" : "ok"));

2994 return (rc==SQLITE_OK && eMode!=eMode2 ? SQLITE_BUSY : rc);

2995 }

2996

2997 /* Return the value to pass to a sqlite3_wal_hook callback, the

2998 ** number of frames in the WAL at the point of the last commit since

2999 ** sqlite3WalCallback() was called. If no commits have occurred since

3000 ** the last call, then return 0.

3001 */

3002 int sqlite3WalCallback(Wal *pWal){

3003 u32 ret = 0;

3004 if( pWal ){

3005 ret = pWal->iCallback;

3006 pWal->iCallback = 0;

3007 }

3008 return (int)ret;

3009 }

3010

3011 /*

3012 ** This function is called to change the WAL subsystem into or out

3013 ** of locking_mode=EXCLUSIVE.

3014 **

3015 ** If op is zero, then attempt to change from locking_mode=EXCLUSIVE

3016 ** into locking_mode=NORMAL. This means that we must acquire a lock

3017 ** on the pWal->readLock byte. If the WAL is already in locking_mode=NORMAL

3018 ** or if the acquisition of the lock fails, then return 0. If the

3019 ** transition out of exclusive-mode is successful, return 1. This

3020 ** operation must occur while the pager is still holding the exclusive

3021 ** lock on the main database file.

3022 **

3023 ** If op is one, then change from locking_mode=NORMAL into

3024 ** locking_mode=EXCLUSIVE. This means that the pWal->readLock must

3025 ** be released. Return 1 if the transition is made and 0 if the

3026 ** WAL is already in exclusive-locking mode - meaning that this

3027 ** routine is a no-op. The pager must already hold the exclusive lock

3028 ** on the main database file before invoking this operation.

3029 **

3030 ** If op is negative, then do a dry-run of the op==1 case but do

3031 ** not actually change anything. The pager uses this to see if it

3032 ** should acquire the database exclusive lock prior to invoking

3033 ** the op==1 case.

3034 */

3035 int sqlite3WalExclusiveMode(Wal *pWal, int op){

3036 int rc;

3037 assert( pWal->writeLock==0 );

3038 assert( pWal->exclusiveMode!=WAL_HEAPMEMORY_MODE \|\| op==-1 );

3039

3040 /* pWal->readLock is usually set, but might be -1 if there was a

3041 ** prior error while attempting to acquire are read-lock. This cannot

3042 ** happen if the connection is actually in exclusive mode (as no xShmLock

3043 ** locks are taken in this case). Nor should the pager attempt to

3044 ** upgrade to exclusive-mode following such an error.

3045 */

3046 assert( pWal->readLock>=0 \|\| pWal->lockError );

3047 assert( pWal->readLock>=0 \|\| (op<=0 && pWal->exclusiveMode==0) );

3048

3049 if( op==0 ){

3050 if( pWal->exclusiveMode ){

3051 pWal->exclusiveMode = 0;

3052 if( walLockShared(pWal, WAL_READ_LOCK(pWal->readLock))!=SQLITE_OK ){

3053 pWal->exclusiveMode = 1;

3054 }

3055 rc = pWal->exclusiveMode==0;

3056 }else{

3057 /* Already in locking_mode=NORMAL */

3058 rc = 0;

3059 }

3060 }else if( op>0 ){

3061 assert( pWal->exclusiveMode==0 );

3062 assert( pWal->readLock>=0 );

3063 walUnlockShared(pWal, WAL_READ_LOCK(pWal->readLock));

3064 pWal->exclusiveMode = 1;

3065 rc = 1;

3066 }else{

3067 rc = pWal->exclusiveMode==0;

3068 }

3069 return rc;

3070 }

3071

3072 /*

3073 ** Return true if the argument is non-NULL and the WAL module is using

3074 ** heap-memory for the wal-index. Otherwise, if the argument is NULL or the

3075 ** WAL module is using shared-memory, return false.

3076 */

3077 int sqlite3WalHeapMemory(Wal *pWal){

3078 return (pWal && pWal->exclusiveMode==WAL_HEAPMEMORY_MODE );

3079 }

3080

3081 #ifdef SQLITE_ENABLE_ZIPVFS

3082 /*

3083 ** If the argument is not NULL, it points to a Wal object that holds a

3084 ** read-lock. This function returns the database page-size if it is known,

3085 ** or zero if it is not (or if pWal is NULL).

3086 */

3087 int sqlite3WalFramesize(Wal *pWal){

3088 assert( pWal==0 \|\| pWal->readLock>=0 );

3089 return (pWal ? pWal->szPage : 0);

3090 }

3091 #endif

3092

3093 #endif /* #ifndef SQLITE_OMIT_WAL */

OLD	NEW

« no previous file with comments | « third_party/sqlite/sqlite-src-3080704/src/wal.h ('k') | third_party/sqlite/sqlite-src-3080704/src/walker.c » ('j') | no next file with comments »