Many hyperlinks are disabled.
Use anonymous login to enable hyperlinks.

Overview
Comment:Add code for taking and querying read-locks. Untested.
Downloads: Tarball | ZIP archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1: ef0cf1ade397e34127a927c805e058fe4fde1cf0
User & Date: dan 2013-10-28 19:48:35.055
Context
2013-10-29
17:46
Add code to prevent database writers from overwriting portions of the log that might be required by present or future database readers or recoverers. check-in: 407a82adbf user: dan tags: trunk
2013-10-28
19:48
Add code for taking and querying read-locks. Untested. check-in: ef0cf1ade3 user: dan tags: trunk
10:56
Fix a problem causing builds without LSM_NO_SYNC to fail. check-in: f8ce90c4a6 user: dan tags: trunk
Changes
Unified Diff Ignore Whitespace Patch
Changes to src/btInt.h.
193
194
195
196
197
198
199


200
201
202
203
204
205
206
207
208
209
210
211
212
213
214

215
216
217
218
219
220
221
222
223
224
225
226
227





228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245







246
247
248
249
250
251
252
int sqlite4BtLogSnapshotOpen(BtLog*);
int sqlite4BtLogSnapshotClose(BtLog*);
int sqlite4BtLogSnapshotWritable(BtLog*);

int sqlite4BtLogSize(BtLog*);
int sqlite4BtLogCheckpoint(BtLog*);



#ifndef NDEBUG
void sqlite4BtDebugReadPage(u32 pgno, u8 *aData, int pgsz);
#else
# define sqlite4BtDebugReadPage(a,b,c)
#endif

/*
** End of bt_log.c interface.
*************************************************************************/

/*************************************************************************
** Interface to bt_lock.c functionality.
*/
typedef struct BtShared BtShared;
typedef struct BtLock BtLock;

struct BtLock {
  /* These three are set by the bt_pager module and thereafter used by 
  ** the bt_lock, bt_pager and bt_log modules. */
  sqlite4_env *pEnv;              /* SQLite environment */
  bt_env *pVfs;                   /* Bt environment */
  bt_file *pFd;                   /* Database file descriptor */

  /* These are used only by the bt_lock module. */
  BtShared *pShared;              /* Shared by all handles on this file */
  BtLock *pNext;                  /* Next connection using pShared */
  u32 mExclLock;                  /* Mask of exclusive locks held */
  u32 mSharedLock;                /* Mask of shared locks held */
};






/* Connect and disconnect procedures */
int sqlite4BtLockConnect(BtLock*, int (*xRecover)(BtLock*));
int sqlite4BtLockDisconnect(BtLock*, int(*xCkpt)(BtLock*), int(*xDel)(BtLock*));

/* Obtain and release the WRITER lock */
int sqlite4BtLockWriter(BtLock*);
int sqlite4BtLockWriterUnlock(BtLock*);

/* Obtain, release and query READER locks.  */
int sqlite4BtLockReader(BtLock*, u32 *aLog, u32 *aLock);
int sqlite4BtLockReaderUnlock(BtLock*);
int sqlite4BtLockReaderMin(BtLock*, u32 *aLog, u32 *aLock, u32 *piMinFrame);

/* Obtain and release CHECKPOINTER lock */
int sqlite4BtLockCkpt(BtLock*);
int sqlite4BtLockCkptUnlock(BtLock*);








/* Obtain pointers to shared-memory chunks */
int sqlite4BtLockShmMap(BtLock*, int iChunk, int nByte, u8 **ppOut);

/*
** End of bt_lock.c interface.
*************************************************************************/








>
>















>













>
>
>
>
>









<
<
<
<
<




>
>
>
>
>
>
>







193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244





245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
int sqlite4BtLogSnapshotOpen(BtLog*);
int sqlite4BtLogSnapshotClose(BtLog*);
int sqlite4BtLogSnapshotWritable(BtLog*);

int sqlite4BtLogSize(BtLog*);
int sqlite4BtLogCheckpoint(BtLog*);

int sqlite4BtLogFrameToIdx(u32 *aLog, u32 iFrame);

#ifndef NDEBUG
void sqlite4BtDebugReadPage(u32 pgno, u8 *aData, int pgsz);
#else
# define sqlite4BtDebugReadPage(a,b,c)
#endif

/*
** End of bt_log.c interface.
*************************************************************************/

/*************************************************************************
** Interface to bt_lock.c functionality.
*/
typedef struct BtShared BtShared;
typedef struct BtLock BtLock;
typedef struct BtReadSlot BtReadSlot;
struct BtLock {
  /* These three are set by the bt_pager module and thereafter used by 
  ** the bt_lock, bt_pager and bt_log modules. */
  sqlite4_env *pEnv;              /* SQLite environment */
  bt_env *pVfs;                   /* Bt environment */
  bt_file *pFd;                   /* Database file descriptor */

  /* These are used only by the bt_lock module. */
  BtShared *pShared;              /* Shared by all handles on this file */
  BtLock *pNext;                  /* Next connection using pShared */
  u32 mExclLock;                  /* Mask of exclusive locks held */
  u32 mSharedLock;                /* Mask of shared locks held */
};

struct BtReadSlot {
  u32 iFirst;
  u32 iLast;
};

/* Connect and disconnect procedures */
int sqlite4BtLockConnect(BtLock*, int (*xRecover)(BtLock*));
int sqlite4BtLockDisconnect(BtLock*, int(*xCkpt)(BtLock*), int(*xDel)(BtLock*));

/* Obtain and release the WRITER lock */
int sqlite4BtLockWriter(BtLock*);
int sqlite4BtLockWriterUnlock(BtLock*);






/* Obtain and release CHECKPOINTER lock */
int sqlite4BtLockCkpt(BtLock*);
int sqlite4BtLockCkptUnlock(BtLock*);

/* Obtain and release READER locks.  */
int sqlite4BtLockReader(BtLock*, u32 *aLog, BtReadSlot *aLock);
int sqlite4BtLockReaderUnlock(BtLock*);

/* Query READER locks.  */
int sqlite4BtLockReaderQuery(BtLock*, u32*, BtReadSlot*, u32*, int*);

/* Obtain pointers to shared-memory chunks */
int sqlite4BtLockShmMap(BtLock*, int iChunk, int nByte, u8 **ppOut);

/*
** End of bt_lock.c interface.
*************************************************************************/

Changes to src/bt_lock.c.
15
16
17
18
19
20
21
22
23
24
25
26

27
28
29
30
31
32
33
34
#include "sqliteInt.h"
#include "btInt.h"

#include <string.h>
#include <assert.h>
#include <stdio.h>

#define BT_LOCK_DMS1       0      /* DMS1 */
#define BT_LOCK_DMS2_RW    1      /* DMS2/rw */
#define BT_LOCK_DMS2_RO    2      /* DMS2/ro */
#define BT_LOCK_WRITER     3      /* WRITER lock */
#define BT_LOCK_CKPTER     4      /* CHECKPOINTER lock */

#define BT_LOCK_READER0    5      /* Array of BT_NREADER locks */

#define BT_LOCK_UNLOCK     0
#define BT_LOCK_SHARED     1
#define BT_LOCK_EXCL       2

typedef struct BtFile BtFile;








|
|
|
|
|
>
|







15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include "sqliteInt.h"
#include "btInt.h"

#include <string.h>
#include <assert.h>
#include <stdio.h>

#define BT_LOCK_DMS1          0   /* DMS1 */
#define BT_LOCK_DMS2_RW       1   /* DMS2/rw */
#define BT_LOCK_DMS2_RO       2   /* DMS2/ro */
#define BT_LOCK_WRITER        3   /* WRITER lock */
#define BT_LOCK_CKPTER        4   /* CHECKPOINTER lock */
#define BT_LOCK_READER_DBONLY 5   /* Reading the db file only */
#define BT_LOCK_READER0       6   /* Array of BT_NREADER locks */

#define BT_LOCK_UNLOCK     0
#define BT_LOCK_SHARED     1
#define BT_LOCK_EXCL       2

typedef struct BtFile BtFile;

330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356






357































358





















359
360
361
362
363
364









































































365
366
367
368
369
370
371
    sqlite4_free(p->pEnv, pShared->apShmChunk);
    sqlite4_free(p->pEnv, pShared);
  }
  btLockMutexLeave();
  return rc;
}

int sqlite4BtLockCheckpoint(BtLock *p, int (*xCkpt)(BtLock*)){
  return xCkpt(p);
}

int sqlite4BtLockBegin(BtLock *p, int eLock){
  return SQLITE4_OK;
}

int sqlite4BtLockEnd(BtLock *p, int eLock){
  return SQLITE4_OK;
}

/* 
** Obtain a READER lock. 
**
** Argument aLog points to an array of 6 frame addresses. These are the 
** first and last frames in each of log regions A, B and C. Argument 
** aLock points to the array of read-lock slots in shared memory.
*/
int sqlite4BtLockReader(BtLock *pLock, u32 *aLog, u32 *aLock){






  /* todo... */































  return SQLITE4_OK;





















}

/*
** Release the READER lock currently held by connection pLock.
*/
int sqlite4BtLockReaderUnlock(BtLock *pLock){









































































  return SQLITE4_OK;
}

int sqlite4BtLockShmMap(BtLock *pLock, int iChunk, int nByte, u8 **ppOut){
  int rc = SQLITE4_OK;
  BtShared *pShared = pLock->pShared;
  u8 *pOut = 0;







<
<
<
<
<
<
<
<
<
<
<
<







|
>
>
>
>
>
>
|
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
|
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>






>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>







331
332
333
334
335
336
337












338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
    sqlite4_free(p->pEnv, pShared->apShmChunk);
    sqlite4_free(p->pEnv, pShared);
  }
  btLockMutexLeave();
  return rc;
}













/* 
** Obtain a READER lock. 
**
** Argument aLog points to an array of 6 frame addresses. These are the 
** first and last frames in each of log regions A, B and C. Argument 
** aLock points to the array of read-lock slots in shared memory.
*/
int sqlite4BtLockReader(
  BtLock *pLock,                  /* Lock module handle */
  u32 *aLog,                      /* Current log file topology */
  BtReadSlot *aSlot               /* Array of read-lock slots (in shmem) */
){
  int rc = SQLITE4_BUSY;          /* Return code */
  int i;                          /* Loop counter */

  /* Find the first and last log frames that this client will use. */
  u32 iLast = aLog[5];
  u32 iFirst = 0;
  for(i=0; iFirst==0 && i<3; i++){
    iFirst = aLog[i*2];
  }

  if( iFirst==0 ){
    rc = btLockLockop(pLock, BT_LOCK_READER_DBONLY, BT_LOCK_SHARED, 0);
  }else{
    int nAttempt = 100;           /* Remaining lock attempts */

    while( rc==SQLITE4_BUSY && (nAttempt--)>0 ){

      /* Try to find a slot populated with the values required. */
      for(i=0; i<BT_NREADER; i++){
        if( aSlot[i].iFirst==iFirst && aSlot[i].iLast==iLast ) break;
      }

      /* Or, if there is no slot with the required values - try to create one */
      if( i==BT_NREADER ){
        for(i=0; i<BT_NREADER; i++){
          rc = btLockLockop(pLock, BT_LOCK_READER0 + i, BT_LOCK_EXCL, 0);
          if( rc==SQLITE4_OK ){
            /* The EXCLUSIVE lock obtained by the successful call to
             ** btLockLockop() is released below by the call to obtain
             ** a SHARED lock on the same locking slot. */
            aSlot[i].iFirst = iFirst;
            aSlot[i].iLast = iLast;
            break;
          }else if( rc!=SQLITE4_BUSY ){
            return rc;
          }
        }
      }

      if( i==BT_NREADER ){
        /* TODO: Try to find a usable slot */
      }

      if( i<BT_NREADER ){
        rc = btLockLockop(pLock, BT_LOCK_READER0 + i, BT_LOCK_SHARED, 0);
        if( rc==SQLITE4_OK ){
          if( aSlot[i].iFirst!=iFirst || aSlot[i].iLast!=iLast ){
            btLockLockop(pLock, BT_LOCK_READER0 + i, BT_LOCK_UNLOCK, 0);
            rc = SQLITE4_BUSY;
          }
        }
      }
    }
  }

  return rc;
}

/*
** Release the READER lock currently held by connection pLock.
*/
int sqlite4BtLockReaderUnlock(BtLock *pLock){
  int i;

  /* Release any locks held on reader slots. */
  assert( (BT_LOCK_READER_DBONLY+1)==BT_LOCK_READER0 );
  for(i=0; i<BT_NREADER+1; i++){
    btLockLockop(pLock, BT_LOCK_READER_DBONLY + i, BT_LOCK_UNLOCK, 0);
  }

  return SQLITE4_OK;
}

/*
** This function is used to determine which parts of the log and database
** files are currently in use by readers. It is called in two scenarios:
**
**   * by CHECKPOINTER clients, to determine how much of the log may
**     be safely copied into the database file. In this case parameter
**     piDblocked is non-NULL.
**
**   * by WRITER clients, to determine how much of the log is no longer
**     required by any present or future reader. This case can be identified
**     by (piDblocked==NULL).
*/
int sqlite4BtLockReaderQuery(
  BtLock *pLock,                  /* Lock handle */
  u32 *aLog,                      /* Current log topology */
  BtReadSlot *aSlot,              /* Array of BT_NREADER read slots */
  u32 *piOut,                     /* OUT: Query result */
  int *piDblocked                 /* OUT: True if READER_DB_ONLY is locked */
){
  u32 iOut = 0;
  u32 iIdxOut = 0;
  int bLast = (piDblocked!=0);
  int rc = SQLITE4_OK;
  int i;

  if( piDblocked ){
    rc = btLockLockop(pLock, BT_LOCK_READER_DBONLY, BT_LOCK_EXCL, 0);
    if( rc==SQLITE4_OK ){
      *piDblocked = 0;
      btLockLockop(pLock, BT_LOCK_READER_DBONLY, BT_LOCK_UNLOCK, 0);
    }else if( rc==SQLITE4_BUSY ){
      *piDblocked = 1;
    }else{
      return rc;
    }
  }

  for(i=0; i<3 && iOut==0; i++){
    int iSlot;
    for(iSlot=0; iSlot<BT_NREADER; iSlot++){
      u32 iVal = (bLast ? aSlot[iSlot].iLast : aSlot[iSlot].iFirst);
      if( iVal ){
        /* Try to zero the slot. */
        rc = btLockLockop(pLock, BT_LOCK_READER0 + iSlot, BT_LOCK_EXCL, 0);
        if( rc==SQLITE4_OK ){
          aSlot[iSlot].iFirst = 0;
          aSlot[iSlot].iLast = 0;
          btLockLockop(pLock, BT_LOCK_READER0 + iSlot, BT_LOCK_UNLOCK, 0);
        }else if( rc==SQLITE4_BUSY ){
          int iIdx = sqlite4BtLogFrameToIdx(aLog, iVal);
          if( iOut==0 || iIdx<iIdxOut ){
            iIdxOut = iIdx;
            iOut = iVal;
          }
        }else{
          return rc;
        }
      }
    }
  }

  *piOut = iOut;
  return SQLITE4_OK;
}

int sqlite4BtLockShmMap(BtLock *pLock, int iChunk, int nByte, u8 **ppOut){
  int rc = SQLITE4_OK;
  BtShared *pShared = pLock->pShared;
  u8 *pOut = 0;
401
402
403
404
405
406
407







408
409
410
411
412
413
414
415














  }
  sqlite4_mutex_leave(pShared->pClientMutex);
  
  *ppOut = pOut;
  return rc;
}








int sqlite4BtLockCkpt(BtLock *pLock){
  return btLockLockop(pLock, BT_LOCK_CKPTER, BT_LOCK_EXCL, 0);
}

int sqlite4BtLockCkptUnlock(BtLock *pLock){
  return btLockLockop(pLock, BT_LOCK_CKPTER, BT_LOCK_UNLOCK, 0);
}






















>
>
>
>
>
>
>



<




>
>
>
>
>
>
>
>
>
>
>
>
>
>
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537

538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
  }
  sqlite4_mutex_leave(pShared->pClientMutex);
  
  *ppOut = pOut;
  return rc;
}

/*
** Attempt to obtain the CHECKPOINTER lock. If the attempt is successful,
** return SQLITE4_OK. If the CHECKPOINTER lock cannot be obtained because
** it is held by some other connection, return SQLITE4_BUSY. 
**
** If any other error occurs, return an SQLite4 error code.
*/
int sqlite4BtLockCkpt(BtLock *pLock){
  return btLockLockop(pLock, BT_LOCK_CKPTER, BT_LOCK_EXCL, 0);
}

int sqlite4BtLockCkptUnlock(BtLock *pLock){
  return btLockLockop(pLock, BT_LOCK_CKPTER, BT_LOCK_UNLOCK, 0);
}

/*
** Attempt to obtain the WRITER lock. If the attempt is successful,
** return SQLITE4_OK. If the WRITER lock cannot be obtained because
** it is held by some other connection, return SQLITE4_BUSY. 
**
** If any other error occurs, return an SQLite4 error code.
*/
int sqlite4BtLockWriter(BtLock *pLock){
  return btLockLockop(pLock, BT_LOCK_WRITER, BT_LOCK_EXCL, 0);
}
int sqlite4BtLockWriterUnlock(BtLock *pLock){
  return btLockLockop(pLock, BT_LOCK_WRITER, BT_LOCK_UNLOCK, 0);
}

Changes to src/bt_log.c.
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
  u32 iFirstRecover;              /* First recovery frame */
};

struct BtShm {
  BtShmHdr hdr1;
  BtShmHdr hdr2;
  BtCkptHdr ckpt;
  u32 aReadlock[BT_NREADER];
};

/* 
** Log handle used by bt_pager.c to access functionality implemented by
** this module. 
*/
struct BtLog {







|







105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
  u32 iFirstRecover;              /* First recovery frame */
};

struct BtShm {
  BtShmHdr hdr1;
  BtShmHdr hdr2;
  BtCkptHdr ckpt;
  BtReadSlot aReadlock[BT_NREADER];
};

/* 
** Log handle used by bt_pager.c to access functionality implemented by
** this module. 
*/
struct BtLog {
816
817
818
819
820
821
822
823
824
825
826

827
828
829
830
831
832
833
834
835
836
837


838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853

854





855





856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873















874
875
876
877
878
879
880
    }
  }

  return rc;
}

/*
** Attempt to read data for page pgno from the log file. If successful,
** the data is written into buffer aData[] (which must be at least as
** large as a database page). In this case SQLITE4_OK is returned.
**

** If the log does not contain any version of page pgno, SQLITE4_NOTFOUND
** is returned and the contents of buffer aData[] are not modified.
**
** If any other error occurs, an SQLite4 error code is returned. The final
** state of buffer aData[] is undefined in this case.
*/
int sqlite4BtLogRead(BtLog *pLog, u32 pgno, u8 *aData){
  const int pgsz = sqlite4BtPagerPagesize((BtPager*)(pLog->pLock));
  int rc = SQLITE4_NOTFOUND;
  u32 iFrame = 0;
  int i;



  /* Loop through regions (c), (b) and (a) of the log file. In that order. */
  for(i=2; i>=0 && rc==SQLITE4_NOTFOUND; i--){
    u32 iLo = pLog->snapshot.aLog[i*2+0];
    u32 iHi = pLog->snapshot.aLog[i*2+1];
    int iSide;
    int iHash;
    int iHashLast;

    iHash = btLogFrameHash(pLog, iHi);
    iHashLast = btLogFrameHash(pLog, iLo);
    iSide = (pLog->snapshot.iHashSide + (i==0)) % 2;

    for( ; rc==SQLITE4_NOTFOUND && iHash>=iHashLast; iHash--){
      rc = btLogHashSearch(pLog, iSide, iHash, iHi, pgno, &iFrame);
      if( rc==SQLITE4_OK && (iFrame<iLo || iFrame>iHi) ){

        rc = SQLITE4_NOTFOUND;





      }





    }
  }

  if( rc==SQLITE4_OK ){
    bt_env *pVfs = pLog->pLock->pVfs;
    i64 iOff;
    assert( rc==SQLITE4_OK );
    iOff = btLogFrameOffset(pLog, pgsz, iFrame);
    rc = pVfs->xRead(pLog->pFd, iOff + sizeof(BtFrameHdr), aData, pgsz);

#if 0
    fprintf(stderr, "read page %d from offset %d\n", (int)pgno, (int)iOff);
    fflush(stderr);
#endif
  }

  return rc;
}
















/*
** Write a frame to the log file.
*/
int sqlite4BtLogWrite(BtLog *pLog, u32 pgno, u8 *aData, int bCommit){
  const int pgsz = sqlite4BtPagerPagesize((BtPager*)(pLog->pLock));
  int rc = SQLITE4_OK;







|
<
|
<
>
|
<
<
<
<

|




>
>















|
>
|
>
>
>
>
>
|
>
>
>
>
>


















>
>
>
>
>
>
>
>
>
>
>
>
>
>
>







816
817
818
819
820
821
822
823

824

825
826




827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
    }
  }

  return rc;
}

/*
** If parameter iSafe is non-zero, then this function is being called as

** part of a checkpoint operation. In this case, if there exists a version

** of page pgno within the log at some point past frame iSafe, return
** SQLITE4_NOTFOUND.




*/
int btLogRead(BtLog *pLog, u32 pgno, u8 *aData, u32 iSafe){
  const int pgsz = sqlite4BtPagerPagesize((BtPager*)(pLog->pLock));
  int rc = SQLITE4_NOTFOUND;
  u32 iFrame = 0;
  int i;

  int bSeen = (iSafe==0);

  /* Loop through regions (c), (b) and (a) of the log file. In that order. */
  for(i=2; i>=0 && rc==SQLITE4_NOTFOUND; i--){
    u32 iLo = pLog->snapshot.aLog[i*2+0];
    u32 iHi = pLog->snapshot.aLog[i*2+1];
    int iSide;
    int iHash;
    int iHashLast;

    iHash = btLogFrameHash(pLog, iHi);
    iHashLast = btLogFrameHash(pLog, iLo);
    iSide = (pLog->snapshot.iHashSide + (i==0)) % 2;

    for( ; rc==SQLITE4_NOTFOUND && iHash>=iHashLast; iHash--){
      rc = btLogHashSearch(pLog, iSide, iHash, iHi, pgno, &iFrame);
      if( rc==SQLITE4_OK ){
        if( iFrame<iLo || iFrame>iHi ){
          rc = SQLITE4_NOTFOUND;
        }else{
          if( iSafe>=iLo && iSafe<=iHi ){
            if( iFrame>iSafe ) return SQLITE4_NOTFOUND;
          }else if( bSeen==0 ){
            return SQLITE4_NOTFOUND;
          }
        }
      }
    }
    if( (iSafe>=iLo && iSafe<=iHi) ){
      bSeen = 1;
    }
  }

  if( rc==SQLITE4_OK ){
    bt_env *pVfs = pLog->pLock->pVfs;
    i64 iOff;
    assert( rc==SQLITE4_OK );
    iOff = btLogFrameOffset(pLog, pgsz, iFrame);
    rc = pVfs->xRead(pLog->pFd, iOff + sizeof(BtFrameHdr), aData, pgsz);

#if 0
    fprintf(stderr, "read page %d from offset %d\n", (int)pgno, (int)iOff);
    fflush(stderr);
#endif
  }

  return rc;
}

/*
** Attempt to read data for page pgno from the log file. If successful,
** the data is written into buffer aData[] (which must be at least as
** large as a database page). In this case SQLITE4_OK is returned.
**
** If the log does not contain any version of page pgno, SQLITE4_NOTFOUND
** is returned and the contents of buffer aData[] are not modified.
**
** If any other error occurs, an SQLite4 error code is returned. The final
** state of buffer aData[] is undefined in this case.
*/
int sqlite4BtLogRead(BtLog *pLog, u32 pgno, u8 *aData){
  return btLogRead(pLog, pgno, aData, 0);
}

/*
** Write a frame to the log file.
*/
int sqlite4BtLogWrite(BtLog *pLog, u32 pgno, u8 *aData, int bCommit){
  const int pgsz = sqlite4BtPagerPagesize((BtPager*)(pLog->pLock));
  int rc = SQLITE4_OK;
1031
1032
1033
1034
1035
1036
1037
1038
1039
1040
1041
1042
1043
1044
1045

  while( rc==SQLITE4_NOTFOUND ){
    /* Attempt to read a copy of the BtShmHdr from shared-memory. */
    rc = btLogSnapshot(pLog, &pLog->snapshot);

    /* Take a read lock on the database */
    if( rc==SQLITE4_OK ){
      u32 *aReadlock = btLogShm(pLog)->aReadlock;
      rc = sqlite4BtLockReader(pLog->pLock, pLog->snapshot.aLog, aReadlock);
    }

    /* Check that the BtShmHdr in shared-memory has not changed. If it has,
    ** drop the read-lock and re-attempt the entire operation. */
    if( rc==SQLITE4_OK ){
      rc = btLogSnapshot(pLog, &shmhdr);







|







1054
1055
1056
1057
1058
1059
1060
1061
1062
1063
1064
1065
1066
1067
1068

  while( rc==SQLITE4_NOTFOUND ){
    /* Attempt to read a copy of the BtShmHdr from shared-memory. */
    rc = btLogSnapshot(pLog, &pLog->snapshot);

    /* Take a read lock on the database */
    if( rc==SQLITE4_OK ){
      BtReadSlot *aReadlock = btLogShm(pLog)->aReadlock;
      rc = sqlite4BtLockReader(pLog->pLock, pLog->snapshot.aLog, aReadlock);
    }

    /* Check that the BtShmHdr in shared-memory has not changed. If it has,
    ** drop the read-lock and re-attempt the entire operation. */
    if( rc==SQLITE4_OK ){
      rc = btLogSnapshot(pLog, &shmhdr);
1124
1125
1126
1127
1128
1129
1130



















1131
1132
1133
1134
1135
1136
1137
1138
1139
1140
1141
1142
1143
1144


1145
1146
1147
1148
1149
1150
1151
1152









1153
1154
1155
1156
1157
1158
1159
      int nLeft = MIN(nMerge, nPgno-iLeft);
      u32 *aRight = &aPgno[iLeft+nMerge];
      int nRight = MIN(nMerge, nPgno-iLeft-nLeft);
      btLogMergeInplace(aLeft, nLeft, aRight, nRight, aSpace, pnPgno);
    }
  }
}




















/*
** Parameters iFirst and iLast are frame numbers for frames that are part 
** of the current log. This function scans the wal-index from iFirst to
** iLast (inclusive) and records the set of page numbers that occur once.
** This set is sorted in ascending order and returned via the output 
** variables *paPgno and *pnPgno.
*/
static int btLogGatherPgno(
  BtLog *pLog,                    /* Log module handle */
  u32 **paPgno,                   /* OUT: s4_malloc'd array of sorted pgno */
  int *pnPgno,                    /* OUT: Number of entries in *paPgno */
  u32 *piLastFrame
){


  u32 *aLog = pLog->snapshot.aLog;/* Log file topology */
  u32 i;
  u32 *aPgno;                     /* Returned array */
  int nPgno;                      /* Elements in aPgno[] */
  u32 *aSpace;                    /* Temporary space used by merge-sort */
  int nMax;
  int rc = SQLITE4_OK;
  int iRegion;










  /* Determine an upper limit on the number of distinct page numbers. This
  ** limit is used to allocate space for the returned array.  */
  nMax = 0;
  for(iRegion=0; iRegion<3; iRegion++){
    if( aLog[iRegion*2] ){
      nMax += 1 + aLog[iRegion*2+1] - aLog[iRegion*2+0];







>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>












|

>
>








>
>
>
>
>
>
>
>
>







1147
1148
1149
1150
1151
1152
1153
1154
1155
1156
1157
1158
1159
1160
1161
1162
1163
1164
1165
1166
1167
1168
1169
1170
1171
1172
1173
1174
1175
1176
1177
1178
1179
1180
1181
1182
1183
1184
1185
1186
1187
1188
1189
1190
1191
1192
1193
1194
1195
1196
1197
1198
1199
1200
1201
1202
1203
1204
1205
1206
1207
1208
1209
1210
1211
1212
      int nLeft = MIN(nMerge, nPgno-iLeft);
      u32 *aRight = &aPgno[iLeft+nMerge];
      int nRight = MIN(nMerge, nPgno-iLeft-nLeft);
      btLogMergeInplace(aLeft, nLeft, aRight, nRight, aSpace, pnPgno);
    }
  }
}

int sqlite4BtLogFrameToIdx(u32 *aLog, u32 iFrame){
  int i;
  int iRet = 0;
  for(i=0; i<3; i++){
    u32 iFirst = aLog[i*2];
    u32 iLast = aLog[i*2+1];
    if( iFirst ){
      if( iFrame>=iFirst && iFrame<=iLast ){
        iRet += (iFrame - iFirst);
        return iRet;
      }else{
        iRet += (iLast - iFirst);
      }
    }
  }
  if( i==3 ) return -1;
  return iRet;
}

/*
** Parameters iFirst and iLast are frame numbers for frames that are part 
** of the current log. This function scans the wal-index from iFirst to
** iLast (inclusive) and records the set of page numbers that occur once.
** This set is sorted in ascending order and returned via the output 
** variables *paPgno and *pnPgno.
*/
static int btLogGatherPgno(
  BtLog *pLog,                    /* Log module handle */
  u32 **paPgno,                   /* OUT: s4_malloc'd array of sorted pgno */
  int *pnPgno,                    /* OUT: Number of entries in *paPgno */
  u32 *piLastFrame                /* OUT: Last frame checkpointed */
){
  BtShm *pShm = btLogShm(pLog);
  BtLock *pLock = pLog->pLock;
  u32 *aLog = pLog->snapshot.aLog;/* Log file topology */
  u32 i;
  u32 *aPgno;                     /* Returned array */
  int nPgno;                      /* Elements in aPgno[] */
  u32 *aSpace;                    /* Temporary space used by merge-sort */
  int nMax;
  int rc = SQLITE4_OK;
  int iRegion;
  int bLocked;
  u32 iSafe;                      /* Last frame in log it is safe to gather */

  *paPgno = 0;
  *pnPgno = 0;
  *piLastFrame = 0;

  rc = sqlite4BtLockReaderQuery(pLock, aLog, pShm->aReadlock, &iSafe, &bLocked);
  if( rc!=SQLITE4_OK || bLocked ) return rc;

  /* Determine an upper limit on the number of distinct page numbers. This
  ** limit is used to allocate space for the returned array.  */
  nMax = 0;
  for(iRegion=0; iRegion<3; iRegion++){
    if( aLog[iRegion*2] ){
      nMax += 1 + aLog[iRegion*2+1] - aLog[iRegion*2+0];
1167
1168
1169
1170
1171
1172
1173






1174
1175
1176
1177
1178
1179
1180
1181
1182
1183
1184
1185
1186
1187
1188
1189




1190
1191
1192
1193
1194
1195
1196
  nPgno = 0;

  /* Copy the required page numbers into the allocated array */
  for(iRegion=0; iRegion<3; iRegion++){
    u32 iFirst = aLog[iRegion*2];
    u32 iLast = aLog[iRegion*2+1];
    if( iFirst ){






      for(i=iFirst; rc==SQLITE4_OK && i<=iLast; i++){
        int iHash = btLogFrameHash(pLog, i);
        u32 *aPage;
        ht_slot *aHash;
        u32 iZero;

        /* It doesn't matter which 'side' of the hash table is requested here,
        ** as only the page-number array, not the aHash[] table, will be used.
        ** And it is the same for both sides. Hence the constant 0 passed as
        ** the second argument to btLogFindHash().  */
        rc = btLogFindHash(pLog, 0, iHash, &aHash, &aPage, &iZero);
        if( rc==SQLITE4_OK ){
          aPgno[nPgno++] = aPage[i-iZero];
        }
      }
      *piLastFrame = iLast;




    }
  }

  /* Sort the contents of the array in ascending order. This step also 
  ** eliminates any  duplicate page numbers. */
  if( rc==SQLITE4_OK ){
    btLogMergeSort(aPgno, &nPgno, aSpace);







>
>
>
>
>
>
















>
>
>
>







1220
1221
1222
1223
1224
1225
1226
1227
1228
1229
1230
1231
1232
1233
1234
1235
1236
1237
1238
1239
1240
1241
1242
1243
1244
1245
1246
1247
1248
1249
1250
1251
1252
1253
1254
1255
1256
1257
1258
1259
  nPgno = 0;

  /* Copy the required page numbers into the allocated array */
  for(iRegion=0; iRegion<3; iRegion++){
    u32 iFirst = aLog[iRegion*2];
    u32 iLast = aLog[iRegion*2+1];
    if( iFirst ){
      /* If the last frame that it is safe to gather is part of this 
      ** region, gather no frames that lie beyond it.  */
      if( iSafe>=iFirst && iSafe<=iLast ){
        iLast = iSafe;
      }

      for(i=iFirst; rc==SQLITE4_OK && i<=iLast; i++){
        int iHash = btLogFrameHash(pLog, i);
        u32 *aPage;
        ht_slot *aHash;
        u32 iZero;

        /* It doesn't matter which 'side' of the hash table is requested here,
        ** as only the page-number array, not the aHash[] table, will be used.
        ** And it is the same for both sides. Hence the constant 0 passed as
        ** the second argument to btLogFindHash().  */
        rc = btLogFindHash(pLog, 0, iHash, &aHash, &aPage, &iZero);
        if( rc==SQLITE4_OK ){
          aPgno[nPgno++] = aPage[i-iZero];
        }
      }
      *piLastFrame = iLast;

      /* If the last frame of this region is the last frame that it is
      ** safe to gather, break out of the loop.  */
      if( iLast==iSafe ) break;
    }
  }

  /* Sort the contents of the array in ascending order. This step also 
  ** eliminates any  duplicate page numbers. */
  if( rc==SQLITE4_OK ){
    btLogMergeSort(aPgno, &nPgno, aSpace);
1247
1248
1249
1250
1251
1252
1253
1254
1255
1256
1257
1258


1259
1260
1261
1262
1263
1264
1265
      rc = btLogReadData(pLog, iOff, (u8*)&fhdr, sizeof(BtFrameHdr));
      iFirstRead = (fhdr.ctrl & ~BT_FRAME_COMMIT);
    }

    /* Copy data from the log file to the database file. */
    for(i=0; rc==SQLITE4_OK && i<nPgno; i++){
      u32 pgno = aPgno[i];
      rc = sqlite4BtLogRead(pLog, pgno, aBuf);
      if( rc==SQLITE4_OK ){
        btDebugCkptPage(pgno, aBuf, pgsz);
        i64 iOff = (i64)pgsz * (pgno-1);
        rc = pVfs->xWrite(pFd, iOff, aBuf, pgsz);


      }
    }

    /* Update the first field of the checkpoint-header. This tells readers
    ** that they need not consider anything that in the log before this
    ** point (since the data has already been copied into the database
    ** file).  */







|




>
>







1310
1311
1312
1313
1314
1315
1316
1317
1318
1319
1320
1321
1322
1323
1324
1325
1326
1327
1328
1329
1330
      rc = btLogReadData(pLog, iOff, (u8*)&fhdr, sizeof(BtFrameHdr));
      iFirstRead = (fhdr.ctrl & ~BT_FRAME_COMMIT);
    }

    /* Copy data from the log file to the database file. */
    for(i=0; rc==SQLITE4_OK && i<nPgno; i++){
      u32 pgno = aPgno[i];
      rc = btLogRead(pLog, pgno, aBuf, iLast);
      if( rc==SQLITE4_OK ){
        btDebugCkptPage(pgno, aBuf, pgsz);
        i64 iOff = (i64)pgsz * (pgno-1);
        rc = pVfs->xWrite(pFd, iOff, aBuf, pgsz);
      }else if( rc==SQLITE4_NOTFOUND ){
        rc = SQLITE4_OK;
      }
    }

    /* Update the first field of the checkpoint-header. This tells readers
    ** that they need not consider anything that in the log before this
    ** point (since the data has already been copied into the database
    ** file).  */
1303
1304
1305
1306
1307
1308
1309
1310
1311

    /* Free the buffer and drop the checkpointer lock */
    sqlite4_free(pLock->pEnv, aBuf);
    sqlite4BtLockCkptUnlock(pLog->pLock);
  }
  return rc;
}










<
1368
1369
1370
1371
1372
1373
1374
1375


    /* Free the buffer and drop the checkpointer lock */
    sqlite4_free(pLock->pEnv, aBuf);
    sqlite4BtLockCkptUnlock(pLog->pLock);
  }
  return rc;
}