/ Check-in [ca68472d]
Login
SQLite training in Houston TX on 2019-11-05 (details)
Part of the 2019 Tcl Conference

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

Overview
Comment:Experimental change to the xShmXXX parts of the VFS interface.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | experimental
Files: files | file ages | folders
SHA1: ca68472db01c14a899892007d1cbaff5e86ae193
User & Date: dan 2010-06-11 19:04:21
Context
2010-06-12
12:02
Fix some problems with handling IO errors on the experimental branch. check-in: eade8bc2 user: dan tags: experimental
2010-06-11
19:04
Experimental change to the xShmXXX parts of the VFS interface. check-in: ca68472d user: dan tags: experimental
17:01
Refactor and simplify the logic used to change journalmode. check-in: 95cc3f6f user: drh tags: trunk
Changes
Hide Diffs Unified Diffs Ignore Whitespace Patch

Changes to src/os.c.

115
116
117
118
119
120
121









122
123
124
125
126
127
128
}
void sqlite3OsShmBarrier(sqlite3_file *id){
  id->pMethods->xShmBarrier(id);
}
int sqlite3OsShmClose(sqlite3_file *id, int deleteFlag){
  return id->pMethods->xShmClose(id, deleteFlag);
}










/*
** The next group of routines are convenience wrappers around the
** VFS methods.
*/
int sqlite3OsOpen(
  sqlite3_vfs *pVfs, 







>
>
>
>
>
>
>
>
>







115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
}
void sqlite3OsShmBarrier(sqlite3_file *id){
  id->pMethods->xShmBarrier(id);
}
int sqlite3OsShmClose(sqlite3_file *id, int deleteFlag){
  return id->pMethods->xShmClose(id, deleteFlag);
}
int sqlite3OsShmPage(
  sqlite3_file *id, 
  int iPage, 
  int pgsz, 
  int isWrite, 
  void volatile **pp
){
  return id->pMethods->xShmPage(id, iPage, pgsz, isWrite, pp);
}

/*
** The next group of routines are convenience wrappers around the
** VFS methods.
*/
int sqlite3OsOpen(
  sqlite3_vfs *pVfs, 

Changes to src/os.h.

250
251
252
253
254
255
256

257
258
259
260
261
262
263
int sqlite3OsShmOpen(sqlite3_file *id);
int sqlite3OsShmSize(sqlite3_file *id, int, int*);
int sqlite3OsShmGet(sqlite3_file *id, int, int*, void volatile**);
int sqlite3OsShmRelease(sqlite3_file *id);
int sqlite3OsShmLock(sqlite3_file *id, int, int, int);
void sqlite3OsShmBarrier(sqlite3_file *id);
int sqlite3OsShmClose(sqlite3_file *id, int);


/* 
** Functions for accessing sqlite3_vfs methods 
*/
int sqlite3OsOpen(sqlite3_vfs *, const char *, sqlite3_file*, int, int *);
int sqlite3OsDelete(sqlite3_vfs *, const char *, int);
int sqlite3OsAccess(sqlite3_vfs *, const char *, int, int *pResOut);







>







250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
int sqlite3OsShmOpen(sqlite3_file *id);
int sqlite3OsShmSize(sqlite3_file *id, int, int*);
int sqlite3OsShmGet(sqlite3_file *id, int, int*, void volatile**);
int sqlite3OsShmRelease(sqlite3_file *id);
int sqlite3OsShmLock(sqlite3_file *id, int, int, int);
void sqlite3OsShmBarrier(sqlite3_file *id);
int sqlite3OsShmClose(sqlite3_file *id, int);
int sqlite3OsShmPage(sqlite3_file *,int,int,int,void volatile **);

/* 
** Functions for accessing sqlite3_vfs methods 
*/
int sqlite3OsOpen(sqlite3_vfs *, const char *, sqlite3_file*, int, int *);
int sqlite3OsDelete(sqlite3_vfs *, const char *, int);
int sqlite3OsAccess(sqlite3_vfs *, const char *, int, int *pResOut);

Changes to src/os_unix.c.

3137
3138
3139
3140
3141
3142
3143

3144
3145





3146
3147
3148
3149
3150
3151
3152
....
3262
3263
3264
3265
3266
3267
3268

3269
3270
3271
3272




3273
3274
3275
3276
3277
3278
3279
....
3702
3703
3704
3705
3706
3707
3708

































































3709
3710
3711
3712
3713
3714
3715
3716
3717

3718
3719
3720
3721
3722
3723
3724
....
3774
3775
3776
3777
3778
3779
3780
3781

3782
3783
3784
3785
3786
3787
3788
*/
struct unixShmNode {
  unixInodeInfo *pInode;     /* unixInodeInfo that owns this SHM node */
  sqlite3_mutex *mutex;      /* Mutex to access this object */
  sqlite3_mutex *mutexBuf;   /* Mutex to access zBuf[] */
  char *zFilename;           /* Name of the mmapped file */
  int h;                     /* Open file descriptor */

  int szMap;                 /* Size of the mapping into memory */
  char *pMMapBuf;            /* Where currently mmapped().  NULL if unmapped */





  int nRef;                  /* Number of unixShm objects pointing to this */
  unixShm *pFirst;           /* All unixShm objects pointing to this */
#ifdef SQLITE_DEBUG
  u8 exclMask;               /* Mask of exclusive locks held */
  u8 sharedMask;             /* Mask of shared locks held */
  u8 nextShmId;              /* Next available unixShm.id value */
#endif
................................................................................
** This is not a VFS shared-memory method; it is a utility function called
** by VFS shared-memory methods.
*/
static void unixShmPurge(unixFile *pFd){
  unixShmNode *p = pFd->pInode->pShmNode;
  assert( unixMutexHeld() );
  if( p && p->nRef==0 ){

    assert( p->pInode==pFd->pInode );
    if( p->mutex ) sqlite3_mutex_free(p->mutex);
    if( p->mutexBuf ) sqlite3_mutex_free(p->mutexBuf);
    if( p->pMMapBuf ) munmap(p->pMMapBuf, p->szMap);




    if( p->h>=0 ) close(p->h);
    p->pInode->pShmNode = 0;
    sqlite3_free(p);
  }
}

/* Forward reference */
................................................................................
static void unixShmBarrier(
  sqlite3_file *fd           /* Database file holding the shared memory */
){
  unixEnterMutex();
  unixLeaveMutex();
}



































































#else
# define unixShmOpen    0
# define unixShmSize    0
# define unixShmGet     0
# define unixShmRelease 0
# define unixShmLock    0
# define unixShmBarrier 0
# define unixShmClose   0

#endif /* #ifndef SQLITE_OMIT_WAL */

/*
** Here ends the implementation of all sqlite3_file methods.
**
********************** End sqlite3_file Methods *******************************
******************************************************************************/
................................................................................
   unixDeviceCharacteristics,  /* xDeviceCapabilities */                     \
   unixShmOpen,                /* xShmOpen */                                \
   unixShmSize,                /* xShmSize */                                \
   unixShmGet,                 /* xShmGet */                                 \
   unixShmRelease,             /* xShmRelease */                             \
   unixShmLock,                /* xShmLock */                                \
   unixShmBarrier,             /* xShmBarrier */                             \
   unixShmClose                /* xShmClose */                               \

};                                                                           \
static const sqlite3_io_methods *FINDER##Impl(const char *z, unixFile *p){   \
  UNUSED_PARAMETER(z); UNUSED_PARAMETER(p);                                  \
  return &METHOD;                                                            \
}                                                                            \
static const sqlite3_io_methods *(*const FINDER)(const char*,unixFile *p)    \
    = FINDER##Impl;







>


>
>
>
>
>







 







>




>
>
>
>







 







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









>







 







|
>







3137
3138
3139
3140
3141
3142
3143
3144
3145
3146
3147
3148
3149
3150
3151
3152
3153
3154
3155
3156
3157
3158
....
3268
3269
3270
3271
3272
3273
3274
3275
3276
3277
3278
3279
3280
3281
3282
3283
3284
3285
3286
3287
3288
3289
3290
....
3713
3714
3715
3716
3717
3718
3719
3720
3721
3722
3723
3724
3725
3726
3727
3728
3729
3730
3731
3732
3733
3734
3735
3736
3737
3738
3739
3740
3741
3742
3743
3744
3745
3746
3747
3748
3749
3750
3751
3752
3753
3754
3755
3756
3757
3758
3759
3760
3761
3762
3763
3764
3765
3766
3767
3768
3769
3770
3771
3772
3773
3774
3775
3776
3777
3778
3779
3780
3781
3782
3783
3784
3785
3786
3787
3788
3789
3790
3791
3792
3793
3794
3795
3796
3797
3798
3799
3800
3801
....
3851
3852
3853
3854
3855
3856
3857
3858
3859
3860
3861
3862
3863
3864
3865
3866
*/
struct unixShmNode {
  unixInodeInfo *pInode;     /* unixInodeInfo that owns this SHM node */
  sqlite3_mutex *mutex;      /* Mutex to access this object */
  sqlite3_mutex *mutexBuf;   /* Mutex to access zBuf[] */
  char *zFilename;           /* Name of the mmapped file */
  int h;                     /* Open file descriptor */

  int szMap;                 /* Size of the mapping into memory */
  char *pMMapBuf;            /* Where currently mmapped().  NULL if unmapped */

  int pgsz;                  /* Size of shared-memory pages */
  int nPage;                 /* Size of array apPage */
  char **apPage;             /* Array of mapped shared-memory pages */

  int nRef;                  /* Number of unixShm objects pointing to this */
  unixShm *pFirst;           /* All unixShm objects pointing to this */
#ifdef SQLITE_DEBUG
  u8 exclMask;               /* Mask of exclusive locks held */
  u8 sharedMask;             /* Mask of shared locks held */
  u8 nextShmId;              /* Next available unixShm.id value */
#endif
................................................................................
** This is not a VFS shared-memory method; it is a utility function called
** by VFS shared-memory methods.
*/
static void unixShmPurge(unixFile *pFd){
  unixShmNode *p = pFd->pInode->pShmNode;
  assert( unixMutexHeld() );
  if( p && p->nRef==0 ){
    int i;
    assert( p->pInode==pFd->pInode );
    if( p->mutex ) sqlite3_mutex_free(p->mutex);
    if( p->mutexBuf ) sqlite3_mutex_free(p->mutexBuf);
    if( p->pMMapBuf ) munmap(p->pMMapBuf, p->szMap);
    for(i=0; i<p->nPage; i++){
      munmap(p->apPage[i], p->pgsz);
    }
    sqlite3_free(p->apPage);
    if( p->h>=0 ) close(p->h);
    p->pInode->pShmNode = 0;
    sqlite3_free(p);
  }
}

/* Forward reference */
................................................................................
static void unixShmBarrier(
  sqlite3_file *fd           /* Database file holding the shared memory */
){
  unixEnterMutex();
  unixLeaveMutex();
}

static int unixShmPage(
  sqlite3_file *fd,               /* Handle open on database file */
  int iPage,                      /* Page to retrieve */
  int pgsz,                       /* Size of pages */
  int isWrite,                    /* True to extend file if necessary */
  void volatile **pp              /* OUT: Mapped memory */
){
  unixFile *pDbFd = (unixFile*)fd;
  unixShm *p = pDbFd->pShm;
  unixShmNode *pShmNode = p->pShmNode;
  int rc = SQLITE_OK;

  assert( p->hasMutexBuf==0 );
  sqlite3_mutex_enter(pShmNode->mutexBuf);
  assert( pgsz==pShmNode->pgsz || pShmNode->nPage==0 );

  if( pShmNode->nPage<=iPage ){
    char **apNew;                 /* New apPage[] array */
    int nByte = (iPage+1)*pgsz;   /* Minimum required file size */
    struct stat sStat;

    pShmNode->pgsz = pgsz;

    /* Make sure the underlying file is large enough (or fail) */
    if( fstat(pShmNode->h, &sStat) ){
      rc = SQLITE_IOERR_SHMSIZE;
      goto shmpage_out;
    }else if( sStat.st_size<nByte ){
      if( !isWrite ) goto shmpage_out;
      if( ftruncate(pShmNode->h, nByte) ){
        rc = SQLITE_IOERR_SHMSIZE;
        goto shmpage_out;
      }  
    }

    apNew = (char**)sqlite3_realloc(pShmNode->apPage, (iPage+1)*sizeof(char *));
    if( !apNew ){
      rc = SQLITE_IOERR_NOMEM;
      goto shmpage_out;
    }
    pShmNode->apPage = apNew;

    while(pShmNode->nPage<=iPage){
      void *pMem = mmap(
          0, pgsz, PROT_READ|PROT_WRITE, MAP_SHARED, pShmNode->h, iPage*pgsz
      );
      if( pMem==MAP_FAILED ){
        assert(0);
        rc = SQLITE_IOERR;
        goto shmpage_out;
      }
      pShmNode->apPage[pShmNode->nPage] = pMem;
      pShmNode->nPage++;
    }
  }

shmpage_out:
  if( pShmNode->nPage>iPage ){
    *pp = pShmNode->apPage[iPage];
  }else{
    *pp = 0;
  }
  sqlite3_mutex_leave(pShmNode->mutexBuf);
  return rc;
}

#else
# define unixShmOpen    0
# define unixShmSize    0
# define unixShmGet     0
# define unixShmRelease 0
# define unixShmLock    0
# define unixShmBarrier 0
# define unixShmClose   0
# define unixShmPage    0
#endif /* #ifndef SQLITE_OMIT_WAL */

/*
** Here ends the implementation of all sqlite3_file methods.
**
********************** End sqlite3_file Methods *******************************
******************************************************************************/
................................................................................
   unixDeviceCharacteristics,  /* xDeviceCapabilities */                     \
   unixShmOpen,                /* xShmOpen */                                \
   unixShmSize,                /* xShmSize */                                \
   unixShmGet,                 /* xShmGet */                                 \
   unixShmRelease,             /* xShmRelease */                             \
   unixShmLock,                /* xShmLock */                                \
   unixShmBarrier,             /* xShmBarrier */                             \
   unixShmClose,               /* xShmClose */                               \
   unixShmPage                 /* xShmPage */                                \
};                                                                           \
static const sqlite3_io_methods *FINDER##Impl(const char *z, unixFile *p){   \
  UNUSED_PARAMETER(z); UNUSED_PARAMETER(p);                                  \
  return &METHOD;                                                            \
}                                                                            \
static const sqlite3_io_methods *(*const FINDER)(const char*,unixFile *p)    \
    = FINDER##Impl;

Changes to src/sqlite.h.in.

662
663
664
665
666
667
668

669
670
671
672
673
674
675
  int (*xShmOpen)(sqlite3_file*);
  int (*xShmSize)(sqlite3_file*, int reqSize, int *pNewSize);
  int (*xShmGet)(sqlite3_file*, int reqSize, int *pSize, void volatile**);
  int (*xShmRelease)(sqlite3_file*);
  int (*xShmLock)(sqlite3_file*, int offset, int n, int flags);
  void (*xShmBarrier)(sqlite3_file*);
  int (*xShmClose)(sqlite3_file*, int deleteFlag);

  /* Methods above are valid for version 2 */
  /* Additional methods may be added in future releases */
};

/*
** CAPI3REF: Standard File Control Opcodes
**







>







662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
  int (*xShmOpen)(sqlite3_file*);
  int (*xShmSize)(sqlite3_file*, int reqSize, int *pNewSize);
  int (*xShmGet)(sqlite3_file*, int reqSize, int *pSize, void volatile**);
  int (*xShmRelease)(sqlite3_file*);
  int (*xShmLock)(sqlite3_file*, int offset, int n, int flags);
  void (*xShmBarrier)(sqlite3_file*);
  int (*xShmClose)(sqlite3_file*, int deleteFlag);
  int (*xShmPage)(sqlite3_file*, int iPage, int pgsz, int, void volatile**);
  /* Methods above are valid for version 2 */
  /* Additional methods may be added in future releases */
};

/*
** CAPI3REF: Standard File Control Opcodes
**

Changes to src/test_devsym.c.

53
54
55
56
57
58
59

60
61
62
63
64
65
66
...
121
122
123
124
125
126
127
128

129
130
131
132
133
134
135
...
271
272
273
274
275
276
277










278
279
280
281
282
283
284
static int devsymShmOpen(sqlite3_file*);
static int devsymShmSize(sqlite3_file*,int,int*);
static int devsymShmGet(sqlite3_file*,int,int*,volatile void**);
static int devsymShmRelease(sqlite3_file*);
static int devsymShmLock(sqlite3_file*,int,int,int);
static void devsymShmBarrier(sqlite3_file*);
static int devsymShmClose(sqlite3_file*,int);


/*
** Method declarations for devsym_vfs.
*/
static int devsymOpen(sqlite3_vfs*, const char *, sqlite3_file*, int , int *);
static int devsymDelete(sqlite3_vfs*, const char *zName, int syncDir);
static int devsymAccess(sqlite3_vfs*, const char *zName, int flags, int *);
................................................................................
  devsymDeviceCharacteristics,      /* xDeviceCharacteristics */
  devsymShmOpen,                    /* xShmOpen */
  devsymShmSize,                    /* xShmSize */
  devsymShmGet,                     /* xShmGet */
  devsymShmRelease,                 /* xShmRelease */
  devsymShmLock,                    /* xShmLock */
  devsymShmBarrier,                 /* xShmBarrier */
  devsymShmClose                    /* xShmClose */

};

struct DevsymGlobal {
  sqlite3_vfs *pVfs;
  int iDeviceChar;
  int iSectorSize;
};
................................................................................
  devsym_file *p = (devsym_file *)pFile;
  sqlite3OsShmBarrier(p->pReal);
}
static int devsymShmClose(sqlite3_file *pFile, int delFlag){
  devsym_file *p = (devsym_file *)pFile;
  return sqlite3OsShmClose(p->pReal, delFlag);
}













/*
** Open an devsym file handle.
*/
static int devsymOpen(







>







 







|
>







 







>
>
>
>
>
>
>
>
>
>







53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
...
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
...
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
static int devsymShmOpen(sqlite3_file*);
static int devsymShmSize(sqlite3_file*,int,int*);
static int devsymShmGet(sqlite3_file*,int,int*,volatile void**);
static int devsymShmRelease(sqlite3_file*);
static int devsymShmLock(sqlite3_file*,int,int,int);
static void devsymShmBarrier(sqlite3_file*);
static int devsymShmClose(sqlite3_file*,int);
static int devsymShmPage(sqlite3_file*,int,int,int, void volatile **);

/*
** Method declarations for devsym_vfs.
*/
static int devsymOpen(sqlite3_vfs*, const char *, sqlite3_file*, int , int *);
static int devsymDelete(sqlite3_vfs*, const char *zName, int syncDir);
static int devsymAccess(sqlite3_vfs*, const char *zName, int flags, int *);
................................................................................
  devsymDeviceCharacteristics,      /* xDeviceCharacteristics */
  devsymShmOpen,                    /* xShmOpen */
  devsymShmSize,                    /* xShmSize */
  devsymShmGet,                     /* xShmGet */
  devsymShmRelease,                 /* xShmRelease */
  devsymShmLock,                    /* xShmLock */
  devsymShmBarrier,                 /* xShmBarrier */
  devsymShmClose,                   /* xShmClose */
  devsymShmPage                     /* xShmPage */
};

struct DevsymGlobal {
  sqlite3_vfs *pVfs;
  int iDeviceChar;
  int iSectorSize;
};
................................................................................
  devsym_file *p = (devsym_file *)pFile;
  sqlite3OsShmBarrier(p->pReal);
}
static int devsymShmClose(sqlite3_file *pFile, int delFlag){
  devsym_file *p = (devsym_file *)pFile;
  return sqlite3OsShmClose(p->pReal, delFlag);
}
static int devsymShmPage(
  sqlite3_file *pFile, 
  int iPage, 
  int pgsz, 
  int isWrite, 
  void volatile **pp
){
  devsym_file *p = (devsym_file *)pFile;
  return sqlite3OsShmPage(p->pReal, iPage, pgsz, isWrite, pp);
}



/*
** Open an devsym file handle.
*/
static int devsymOpen(

Changes to src/test_vfs.c.

71
72
73
74
75
76
77

78
79
80
81



82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
...
135
136
137
138
139
140
141

142
143
144
145
146
147
148
...
156
157
158
159
160
161
162
163

164
165
166
167
168
169
170
...
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
...
620
621
622
623
624
625
626

627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651

652
653
654
655

656
657
658
659
660
661
662
663
664
665






666
667
668
669
670
671
672






673
674
675
676
677




678
679
680
681
682








683
684
685

686
687
688
689
690
691
692
...
778
779
780
781
782
783
784

785
786
787

788

789
790
791
792
793
794
795
...
817
818
819
820
821
822
823


824
825
826
827
828
829
830
...
834
835
836
837
838
839
840
841




842

843
844






845
846
847
848
849
850
851
852
#define TESTVFS_SHMOPEN_MASK    0x00000001
#define TESTVFS_SHMSIZE_MASK    0x00000002
#define TESTVFS_SHMGET_MASK     0x00000004
#define TESTVFS_SHMRELEASE_MASK 0x00000008
#define TESTVFS_SHMLOCK_MASK    0x00000010
#define TESTVFS_SHMBARRIER_MASK 0x00000020
#define TESTVFS_SHMCLOSE_MASK   0x00000040


#define TESTVFS_OPEN_MASK       0x00000080
#define TESTVFS_SYNC_MASK       0x00000100
#define TESTVFS_ALL_MASK        0x000001FF




/*
** A shared-memory buffer. There is one of these objects for each shared
** memory region opened by clients. If two clients open the same file,
** there are two TestvfsFile structures but only one TestvfsBuffer structure.
*/
struct TestvfsBuffer {
  char *zFile;                    /* Associated file name */
  int n;                          /* Size of allocated buffer in bytes */
  u8 *a;                          /* Buffer allocated using ckalloc() */
  TestvfsFile *pFile;             /* List of open handles */
  TestvfsBuffer *pNext;           /* Next in linked list of all buffers */
};


#define PARENTVFS(x) (((Testvfs *)((x)->pAppData))->pParent)

................................................................................
static int tvfsShmOpen(sqlite3_file*);
static int tvfsShmSize(sqlite3_file*, int , int *);
static int tvfsShmGet(sqlite3_file*, int , int *, volatile void **);
static int tvfsShmRelease(sqlite3_file*);
static int tvfsShmLock(sqlite3_file*, int , int, int);
static void tvfsShmBarrier(sqlite3_file*);
static int tvfsShmClose(sqlite3_file*, int);


static sqlite3_io_methods tvfs_io_methods = {
  2,                            /* iVersion */
  tvfsClose,                      /* xClose */
  tvfsRead,                       /* xRead */
  tvfsWrite,                      /* xWrite */
  tvfsTruncate,                   /* xTruncate */
................................................................................
  tvfsDeviceCharacteristics,      /* xDeviceCharacteristics */
  tvfsShmOpen,                    /* xShmOpen */
  tvfsShmSize,                    /* xShmSize */
  tvfsShmGet,                     /* xShmGet */
  tvfsShmRelease,                 /* xShmRelease */
  tvfsShmLock,                    /* xShmLock */
  tvfsShmBarrier,                 /* xShmBarrier */
  tvfsShmClose                    /* xShmClose */

};

static int tvfsResultCode(Testvfs *p, int *pRc){
  struct errcode {
    int eCode;
    const char *zCode;
  } aCode[] = {
................................................................................
/*
** Return the current time as a Julian Day number in *pTimeOut.
*/
static int tvfsCurrentTime(sqlite3_vfs *pVfs, double *pTimeOut){
  return PARENTVFS(pVfs)->xCurrentTime(PARENTVFS(pVfs), pTimeOut);
}

static void tvfsGrowBuffer(TestvfsFile *pFd, int reqSize, int *pNewSize){
  TestvfsBuffer *pBuffer = pFd->pShm;
  if( reqSize>pBuffer->n ){
    pBuffer->a = (u8 *)ckrealloc((char *)pBuffer->a, reqSize);
    memset(&pBuffer->a[pBuffer->n], 0x55, reqSize-pBuffer->n);
    pBuffer->n = reqSize;
  }
  *pNewSize = pBuffer->n;
}

static int tvfsInjectIoerr(Testvfs *p){
  int ret = 0;
  if( p->ioerr ){
    p->iIoerrCnt--;
    if( p->iIoerrCnt==0 || (p->iIoerrCnt<0 && p->ioerr==2) ){
      ret = 1;
      p->nIoerrFail++;
................................................................................
}

static int tvfsShmSize(
  sqlite3_file *pFile,
  int reqSize,
  int *pNewSize
){

  int rc = SQLITE_OK;
  TestvfsFile *pFd = (TestvfsFile *)pFile;
  Testvfs *p = (Testvfs *)(pFd->pVfs->pAppData);

  if( p->pScript && p->mask&TESTVFS_SHMSIZE_MASK ){
    tvfsExecTcl(p, "xShmSize", 
        Tcl_NewStringObj(pFd->pShm->zFile, -1), pFd->pShmId, 0
    );
    tvfsResultCode(p, &rc);
  }
  if( rc==SQLITE_OK && p->mask&TESTVFS_SHMSIZE_MASK && tvfsInjectIoerr(p) ){
    rc = SQLITE_IOERR;
  }
  if( rc==SQLITE_OK ){
    tvfsGrowBuffer(pFd, reqSize, pNewSize);
  }
  return rc;
}

static int tvfsShmGet(
  sqlite3_file *pFile, 
  int reqMapSize, 
  int *pMapSize, 
  volatile void **pp
){

  int rc = SQLITE_OK;
  TestvfsFile *pFd = (TestvfsFile *)pFile;
  Testvfs *p = (Testvfs *)(pFd->pVfs->pAppData);


  if( p->pScript && p->mask&TESTVFS_SHMGET_MASK ){
    tvfsExecTcl(p, "xShmGet", 
        Tcl_NewStringObj(pFd->pShm->zFile, -1), pFd->pShmId, 
        Tcl_NewIntObj(reqMapSize)
    );
    tvfsResultCode(p, &rc);
  }
  if( rc==SQLITE_OK && p->mask&TESTVFS_SHMGET_MASK && tvfsInjectIoerr(p) ){
    rc = SQLITE_IOERR;
  }







  *pMapSize = pFd->pShm->n;
  *pp = pFd->pShm->a;
  return rc;
}

static int tvfsShmRelease(sqlite3_file *pFile){






  int rc = SQLITE_OK;
  TestvfsFile *pFd = (TestvfsFile *)pFile;
  Testvfs *p = (Testvfs *)(pFd->pVfs->pAppData);

  if( p->pScript && p->mask&TESTVFS_SHMRELEASE_MASK ){




    tvfsExecTcl(p, "xShmRelease", 
        Tcl_NewStringObj(pFd->pShm->zFile, -1), pFd->pShmId, 0
    );
    tvfsResultCode(p, &rc);
  }









  return rc;
}


static int tvfsShmLock(
  sqlite3_file *pFile,
  int ofst,
  int n,
  int flags
){
................................................................................
  }

  for(ppFd=&pBuffer->pFile; *ppFd!=pFd; ppFd=&((*ppFd)->pNext));
  assert( (*ppFd)==pFd );
  *ppFd = pFd->pNext;

  if( pBuffer->pFile==0 ){

    TestvfsBuffer **pp;
    for(pp=&p->pBuffer; *pp!=pBuffer; pp=&((*pp)->pNext));
    *pp = (*pp)->pNext;

    ckfree((char *)pBuffer->a);

    ckfree((char *)pBuffer);
  }
  pFd->pShm = 0;

  return rc;
}

................................................................................
  if( Tcl_GetIndexFromObj(interp, objv[1], CMD_strs, "subcommand", 0, &i) ){
    return TCL_ERROR;
  }
  Tcl_ResetResult(interp);

  switch( (enum DB_enum)i ){
    case CMD_SHM: {


      TestvfsBuffer *pBuffer;
      char *zName;
      if( objc!=3 && objc!=4 ){
        Tcl_WrongNumArgs(interp, 2, objv, "FILE ?VALUE?");
        return TCL_ERROR;
      }
      zName = Tcl_GetString(objv[2]);
................................................................................
      if( !pBuffer ){
        Tcl_AppendResult(interp, "no such file: ", zName, 0);
        return TCL_ERROR;
      }
      if( objc==4 ){
        int n;
        u8 *a = Tcl_GetByteArrayFromObj(objv[3], &n);
        pBuffer->a = (u8 *)ckrealloc((char *)pBuffer->a, n);




        pBuffer->n = n;

        memcpy(pBuffer->a, a, n);
      }






      Tcl_SetObjResult(interp, Tcl_NewByteArrayObj(pBuffer->a, pBuffer->n));
      break;
    }

    case CMD_FILTER: {
      static struct VfsMethod {
        char *zName;
        int mask;







>

|
|
|
>
>
>








|
|







 







>







 







|
>







 







<
<
<
<
<
<
<
<
<
<







 







>
|
<
<
|
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<






>
|
<
<
|
>
|
|
<
<
<
<
|
<
<
|
>
>
>
>
>
>
|
<
<
<


|
>
>
>
>
>
>




|
>
>
>
>
|
|



>
>
>
>
>
>
>
>



>







 







>



>
|
>







 







>
>







 







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







71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
...
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
...
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
...
549
550
551
552
553
554
555










556
557
558
559
560
561
562
...
616
617
618
619
620
621
622
623
624


625















626
627
628
629
630
631
632
633


634
635
636
637




638


639
640
641
642
643
644
645
646



647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
...
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
...
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
...
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
#define TESTVFS_SHMOPEN_MASK    0x00000001
#define TESTVFS_SHMSIZE_MASK    0x00000002
#define TESTVFS_SHMGET_MASK     0x00000004
#define TESTVFS_SHMRELEASE_MASK 0x00000008
#define TESTVFS_SHMLOCK_MASK    0x00000010
#define TESTVFS_SHMBARRIER_MASK 0x00000020
#define TESTVFS_SHMCLOSE_MASK   0x00000040
#define TESTVFS_SHMPAGE_MASK    0x00000080

#define TESTVFS_OPEN_MASK       0x00000100
#define TESTVFS_SYNC_MASK       0x00000200
#define TESTVFS_ALL_MASK        0x000003FF


#define TESTVFS_MAX_PAGES 256

/*
** A shared-memory buffer. There is one of these objects for each shared
** memory region opened by clients. If two clients open the same file,
** there are two TestvfsFile structures but only one TestvfsBuffer structure.
*/
struct TestvfsBuffer {
  char *zFile;                    /* Associated file name */
  int pgsz;                       /* Page size */
  u8 *aPage[TESTVFS_MAX_PAGES];   /* Array of ckalloc'd pages */
  TestvfsFile *pFile;             /* List of open handles */
  TestvfsBuffer *pNext;           /* Next in linked list of all buffers */
};


#define PARENTVFS(x) (((Testvfs *)((x)->pAppData))->pParent)

................................................................................
static int tvfsShmOpen(sqlite3_file*);
static int tvfsShmSize(sqlite3_file*, int , int *);
static int tvfsShmGet(sqlite3_file*, int , int *, volatile void **);
static int tvfsShmRelease(sqlite3_file*);
static int tvfsShmLock(sqlite3_file*, int , int, int);
static void tvfsShmBarrier(sqlite3_file*);
static int tvfsShmClose(sqlite3_file*, int);
static int tvfsShmPage(sqlite3_file*,int,int,int, void volatile **);

static sqlite3_io_methods tvfs_io_methods = {
  2,                            /* iVersion */
  tvfsClose,                      /* xClose */
  tvfsRead,                       /* xRead */
  tvfsWrite,                      /* xWrite */
  tvfsTruncate,                   /* xTruncate */
................................................................................
  tvfsDeviceCharacteristics,      /* xDeviceCharacteristics */
  tvfsShmOpen,                    /* xShmOpen */
  tvfsShmSize,                    /* xShmSize */
  tvfsShmGet,                     /* xShmGet */
  tvfsShmRelease,                 /* xShmRelease */
  tvfsShmLock,                    /* xShmLock */
  tvfsShmBarrier,                 /* xShmBarrier */
  tvfsShmClose,                   /* xShmClose */
  tvfsShmPage                     /* xShmPage */
};

static int tvfsResultCode(Testvfs *p, int *pRc){
  struct errcode {
    int eCode;
    const char *zCode;
  } aCode[] = {
................................................................................
/*
** Return the current time as a Julian Day number in *pTimeOut.
*/
static int tvfsCurrentTime(sqlite3_vfs *pVfs, double *pTimeOut){
  return PARENTVFS(pVfs)->xCurrentTime(PARENTVFS(pVfs), pTimeOut);
}











static int tvfsInjectIoerr(Testvfs *p){
  int ret = 0;
  if( p->ioerr ){
    p->iIoerrCnt--;
    if( p->iIoerrCnt==0 || (p->iIoerrCnt<0 && p->ioerr==2) ){
      ret = 1;
      p->nIoerrFail++;
................................................................................
}

static int tvfsShmSize(
  sqlite3_file *pFile,
  int reqSize,
  int *pNewSize
){
  assert(0);
  return SQLITE_OK;


}















static int tvfsShmGet(
  sqlite3_file *pFile, 
  int reqMapSize, 
  int *pMapSize, 
  volatile void **pp
){
  assert(0);
  return SQLITE_OK;


}
static int tvfsShmRelease(sqlite3_file *pFile){
  assert(0);
  return SQLITE_OK;




}



static void tvfsAllocPage(TestvfsBuffer *p, int iPage, int pgsz){
  assert( iPage<TESTVFS_MAX_PAGES );
  if( p->aPage[iPage]==0 ){
    p->aPage[iPage] = ckalloc(pgsz);
    memset(p->aPage[iPage], 0, pgsz);
    p->pgsz = pgsz;
  }



}

static int tvfsShmPage(
  sqlite3_file *pFile,            /* Handle open on database file */
  int iPage,                      /* Page to retrieve */
  int pgsz,                       /* Size of pages */
  int isWrite,                    /* True to extend file if necessary */
  void volatile **pp              /* OUT: Mapped memory */
){
  int rc = SQLITE_OK;
  TestvfsFile *pFd = (TestvfsFile *)pFile;
  Testvfs *p = (Testvfs *)(pFd->pVfs->pAppData);

  if( p->pScript && p->mask&TESTVFS_SHMPAGE_MASK ){
    Tcl_Obj *pArg = Tcl_NewObj();
    Tcl_ListObjAppendElement(p->interp, pArg, Tcl_NewIntObj(iPage));
    Tcl_ListObjAppendElement(p->interp, pArg, Tcl_NewIntObj(pgsz));
    Tcl_ListObjAppendElement(p->interp, pArg, Tcl_NewIntObj(isWrite));
    tvfsExecTcl(p, "xShmPage", 
        Tcl_NewStringObj(pFd->pShm->zFile, -1), pFd->pShmId, pArg
    );
    tvfsResultCode(p, &rc);
  }
  if( rc==SQLITE_OK && p->mask&TESTVFS_SHMPAGE_MASK && tvfsInjectIoerr(p) ){
    rc = SQLITE_IOERR;
  }

  if( rc==SQLITE_OK && isWrite && !pFd->pShm->aPage[iPage] ){
    tvfsAllocPage(pFd->pShm, iPage, pgsz);
  }
  *pp = (void volatile *)pFd->pShm->aPage[iPage];

  return rc;
}


static int tvfsShmLock(
  sqlite3_file *pFile,
  int ofst,
  int n,
  int flags
){
................................................................................
  }

  for(ppFd=&pBuffer->pFile; *ppFd!=pFd; ppFd=&((*ppFd)->pNext));
  assert( (*ppFd)==pFd );
  *ppFd = pFd->pNext;

  if( pBuffer->pFile==0 ){
    int i;
    TestvfsBuffer **pp;
    for(pp=&p->pBuffer; *pp!=pBuffer; pp=&((*pp)->pNext));
    *pp = (*pp)->pNext;
    for(i=0; pBuffer->aPage[i]; i++){
      ckfree((char *)pBuffer->aPage[i]);
    }
    ckfree((char *)pBuffer);
  }
  pFd->pShm = 0;

  return rc;
}

................................................................................
  if( Tcl_GetIndexFromObj(interp, objv[1], CMD_strs, "subcommand", 0, &i) ){
    return TCL_ERROR;
  }
  Tcl_ResetResult(interp);

  switch( (enum DB_enum)i ){
    case CMD_SHM: {
      Tcl_Obj *pObj;
      int i;
      TestvfsBuffer *pBuffer;
      char *zName;
      if( objc!=3 && objc!=4 ){
        Tcl_WrongNumArgs(interp, 2, objv, "FILE ?VALUE?");
        return TCL_ERROR;
      }
      zName = Tcl_GetString(objv[2]);
................................................................................
      if( !pBuffer ){
        Tcl_AppendResult(interp, "no such file: ", zName, 0);
        return TCL_ERROR;
      }
      if( objc==4 ){
        int n;
        u8 *a = Tcl_GetByteArrayFromObj(objv[3], &n);
        assert( pBuffer->pgsz==0 || pBuffer->pgsz==32768 );
        for(i=0; i*32768<n; i++){
          int nByte = 32768;
          tvfsAllocPage(pBuffer, i, 32768);
          if( n-i*32768<32768 ){
            nByte = n;
          }
          memcpy(pBuffer->aPage[i], &a[i*32768], nByte);
        }
      }

      pObj = Tcl_NewObj();
      for(i=0; pBuffer->aPage[i]; i++){
        Tcl_AppendObjToObj(pObj, Tcl_NewByteArrayObj(pBuffer->aPage[i], 32768));
      }
      Tcl_SetObjResult(interp, pObj);
      break;
    }

    case CMD_FILTER: {
      static struct VfsMethod {
        char *zName;
        int mask;

Changes to src/wal.c.

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
...
409
410
411
412
413
414
415
416
417
418
419
420


421
422
423
424
425
426
427
428
...
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
...
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
...
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
...
763
764
765
766
767
768
769
















































770
771
772
773
774
775
776
...
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
...
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
...
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
...
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
....
1072
1073
1074
1075
1076
1077
1078
1079
1080
1081
1082
1083
1084
1085
1086
1087
1088
....
1160
1161
1162
1163
1164
1165
1166
1167
1168
1169
1170
1171
1172
1173
1174
....
1203
1204
1205
1206
1207
1208
1209
1210
1211
1212
1213
1214
1215
1216
1217
1218
1219
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
1260
1261
1262
1263
....
1296
1297
1298
1299
1300
1301
1302
1303
1304
1305
1306
1307
1308
1309
1310
1311
1312
1313
1314
1315
1316
1317
1318
1319
1320
1321
1322
1323
1324
1325
1326
1327
1328

1329
1330
1331
1332
1333
1334
1335
1336
1337
1338
1339
1340
1341
1342

1343





1344
1345
1346









1347
1348
1349




1350
1351
1352
1353
1354

1355
1356
1357
1358
1359
1360
1361
1362
1363
....
1426
1427
1428
1429
1430
1431
1432
1433
1434
1435
1436
1437
1438
1439
1440
1441
....
1457
1458
1459
1460
1461
1462
1463

1464
1465
1466
1467
1468
1469
1470
....
1521
1522
1523
1524
1525
1526
1527
1528
1529
1530
1531
1532
1533
1534
1535
1536

1537
1538
1539
1540
1541
1542
1543
....
1556
1557
1558
1559
1560
1561
1562

1563
1564


1565
1566
1567
1568
1569
1570
1571
1572
1573
1574
1575
1576
1577
1578
1579
1580
1581
1582
1583
1584
1585
1586
1587
1588
....
1621
1622
1623
1624
1625
1626
1627

1628
1629
1630

1631
1632
1633
1634
1635
1636
1637
....
1655
1656
1657
1658
1659
1660
1661
1662
1663
1664
1665
1666
1667
1668
1669
1670
1671
1672
1673
1674
1675
1676
....
1706
1707
1708
1709
1710
1711
1712
1713
1714
1715
1716
1717
1718
1719
1720
....
1735
1736
1737
1738
1739
1740
1741
1742
1743
1744
1745
1746
1747
1748
1749
1750
1751
1752
1753
1754
1755
1756
1757
1758
....
1879
1880
1881
1882
1883
1884
1885
1886
1887
1888
1889
1890
1891
1892
1893
....
1909
1910
1911
1912
1913
1914
1915
1916
1917
1918
1919
1920
1921
1922
1923
....
1928
1929
1930
1931
1932
1933
1934
1935
1936
1937
1938
1939
1940
1941
1942
1943
1944
1945
1946
1947
....
1959
1960
1961
1962
1963
1964
1965
1966
1967
1968
1969
1970
1971
1972
1973
1974
1975
1976
1977
1978
1979
1980
1981
1982
1983
1984
1985
1986
1987
1988
1989
1990
1991
1992
1993
1994
1995
1996
1997
1998
1999
2000
2001
2002
2003
2004
2005
2006
2007
2008
2009
2010
2011
2012
2013
....
2035
2036
2037
2038
2039
2040
2041

2042
2043
2044
2045
2046
2047
2048
....
2053
2054
2055
2056
2057
2058
2059
2060
2061
2062
2063
2064
2065
2066
2067
2068
2069
2070
2071
2072
2073
2074
2075
2076
2077
2078
2079
....
2098
2099
2100
2101
2102
2103
2104
2105
2106
2107
2108
2109
2110
2111
2112
2113
2114
2115
2116
....
2120
2121
2122
2123
2124
2125
2126
2127
2128
2129
2130
2131
2132
2133
2134
2135
2136
2137
2138
2139
....
2166
2167
2168
2169
2170
2171
2172
2173
2174
2175
2176
2177
2178
2179
2180
2181
2182
2183
2184
2185
2186
2187
2188
2189
....
2195
2196
2197
2198
2199
2200
2201
2202
2203
2204
2205
2206
2207
2208
2209
2210
2211
....
2233
2234
2235
2236
2237
2238
2239
2240
2241
2242
2243
2244
2245
2246
2247
2248
2249
2250
2251
....
2263
2264
2265
2266
2267
2268
2269
2270
2271
2272
2273
2274
2275
2276
2277
2278
2279
2280
2281
2282
2283
2284
2285
2286
2287
2288
2289
2290
2291
2292
2293
....
2354
2355
2356
2357
2358
2359
2360
2361
2362
2363
2364
2365
2366
2367
2368
....
2387
2388
2389
2390
2391
2392
2393
2394
2395
2396
2397
2398
2399
2400
2401
....
2408
2409
2410
2411
2412
2413
2414
2415
2416
2417
2418
2419
2420
2421
2422
....
2437
2438
2439
2440
2441
2442
2443
2444
2445
2446
2447
2448
2449
2450
2451
** following object.
*/
struct Wal {
  sqlite3_vfs *pVfs;         /* The VFS used to create pDbFd */
  sqlite3_file *pDbFd;       /* File handle for the database file */
  sqlite3_file *pWalFd;      /* File handle for WAL file */
  u32 iCallback;             /* Value to pass to log callback (or 0) */
  int szWIndex;              /* Size of the wal-index that is mapped in mem */
  volatile u32 *pWiData;     /* Pointer to wal-index content in memory */
  u16 szPage;                /* Database page size */
  i16 readLock;              /* Which read lock is being held.  -1 for none */
  u8 exclusiveMode;          /* Non-zero if connection is in exclusive mode */
  u8 isWIndexOpen;           /* True if ShmOpen() called on pDbFd */
  u8 writeLock;              /* True if in a write transaction */
  u8 ckptLock;               /* True if holding a checkpoint lock */
  WalIndexHdr hdr;           /* Wal-index header for current transaction */
  char *zWalName;            /* Name of WAL file */
  u32 nCkpt;                 /* Checkpoint sequence counter in the wal-header */
#ifdef SQLITE_DEBUG
  u8 lockError;              /* True if a locking error has occurred */
#endif
};

/*





























































** Return a pointer to the WalCkptInfo structure in the wal-index.
*/
static volatile WalCkptInfo *walCkptInfo(Wal *pWal){


  assert( pWal->pWiData!=0 );
  return (volatile WalCkptInfo*)&pWal->pWiData[sizeof(WalIndexHdr)/2];
}


/*
** This structure is used to implement an iterator that loops through
** all frames in the WAL in database page order. Where two or more frames
** correspond to the same database page, the iterator visits only the 
** frame most recently written to the WAL (in other words, the frame with
** the largest index).
................................................................................
**   walIteratorFree() - Free an iterator.
**
** This functionality is used by the checkpoint code (see walCheckpoint()).
*/
struct WalIterator {
  int iPrior;           /* Last result returned from the iterator */
  int nSegment;         /* Size of the aSegment[] array */
  int nFinal;           /* Elements in aSegment[nSegment-1]  */
  struct WalSegment {
    int iNext;              /* Next slot in aIndex[] not previously returned */
    u8 *aIndex;             /* i0, i1, i2... such that aPgno[iN] ascending */
    u32 *aPgno;             /* 256 page numbers.  Pointer to Wal.pWiData */


  } aSegment[1];        /* One for every 256 entries in the WAL */
};

/*
** The argument to this macro must be of type u32. On a little-endian
** architecture, it returns the u32 value that results from interpreting
** the 4 bytes as a big-endian value. On a big-endian architecture, it
** returns the value that would be produced by intepreting the 4 bytes
................................................................................
static void walIndexWriteHdr(Wal *pWal){
  WalIndexHdr *aHdr;

  assert( pWal->writeLock );
  pWal->hdr.isInit = 1;
  walChecksumBytes(1, (u8*)&pWal->hdr, offsetof(WalIndexHdr, aCksum),
                   0, pWal->hdr.aCksum);
  aHdr = (WalIndexHdr*)pWal->pWiData;
  memcpy(&aHdr[1], &pWal->hdr, sizeof(WalIndexHdr));
  sqlite3OsShmBarrier(pWal->pDbFd);
  memcpy(&aHdr[0], &pWal->hdr, sizeof(WalIndexHdr));
}

/*
** This function encodes a single frame header and writes it to a buffer
................................................................................
  ** and the new database size.
  */
  *piPage = pgno;
  *pnTruncate = sqlite3Get4byte(&aFrame[4]);
  return 1;
}

/*
** Define the parameters of the hash tables in the wal-index file. There
** is a hash-table following every HASHTABLE_NPAGE page numbers in the
** wal-index.
**
** Changing any of these constants will alter the wal-index format and
** create incompatibilities.
*/
#define HASHTABLE_NPAGE      4096  /* Must be power of 2 and multiple of 256 */
#define HASHTABLE_DATATYPE   u16
#define HASHTABLE_HASH_1     383                  /* Should be prime */
#define HASHTABLE_NSLOT      (HASHTABLE_NPAGE*2)  /* Must be a power of 2 */
#define HASHTABLE_NBYTE      (sizeof(HASHTABLE_DATATYPE)*HASHTABLE_NSLOT)

#if defined(SQLITE_TEST) && defined(SQLITE_DEBUG)
/*
** Names of locks.  This routine is used to provide debugging output and is not
** a part of an ordinary build.
*/
static const char *walLockName(int lockIdx){
................................................................................
  if( pWal->exclusiveMode ) return;
  (void)sqlite3OsShmLock(pWal->pDbFd, lockIdx, n,
                         SQLITE_SHM_UNLOCK | SQLITE_SHM_EXCLUSIVE);
  WALTRACE(("WAL%p: release EXCLUSIVE-%s cnt=%d\n", pWal,
             walLockName(lockIdx), n));
}

/*
** Return the index in the Wal.pWiData array that corresponds to 
** frame iFrame.
**
** Wal.pWiData is an array of u32 elements that is the wal-index.
** The array begins with a header and is then followed by alternating
** "map" and "hash-table" blocks.  Each "map" block consists of
** HASHTABLE_NPAGE u32 elements which are page numbers corresponding
** to frames in the WAL file.  
**
** This routine returns an index X such that Wal.pWiData[X] is part
** of a "map" block that contains the page number of the iFrame-th
** frame in the WAL file.
*/
static int walIndexEntry(u32 iFrame){
  return (
      (WALINDEX_LOCK_OFFSET+WALINDEX_LOCK_RESERVED)/sizeof(u32)
    + (((iFrame-1)/HASHTABLE_NPAGE) * HASHTABLE_NBYTE)/sizeof(u32)
    + (iFrame-1)
  );
}

/*
** Return the minimum size of the shared-memory, in bytes, that is needed
** to support a wal-index containing frame iFrame.  The value returned
** includes the wal-index header and the complete "block" containing iFrame,
** including the hash table segment that follows the block.
*/
static int walMappingSize(u32 iFrame){
  const int nByte = (sizeof(u32)*HASHTABLE_NPAGE + HASHTABLE_NBYTE) ;
  return ( WALINDEX_LOCK_OFFSET 
         + WALINDEX_LOCK_RESERVED 
         + nByte * ((iFrame + HASHTABLE_NPAGE - 1)/HASHTABLE_NPAGE)
  );
}

/*
** Release our reference to the wal-index memory map, if we are holding
** it.
*/
static void walIndexUnmap(Wal *pWal){
  if( pWal->pWiData ){
    sqlite3OsShmRelease(pWal->pDbFd);
  }
  pWal->pWiData = 0;
  pWal->szWIndex = -1;
}

/*
** Map the wal-index file into memory if it isn't already. 
**
** The reqSize parameter is the requested size of the mapping.  The
** mapping will be at least this big if the underlying storage is
** that big.  But the mapping will never grow larger than the underlying
** storage.  Use the walIndexRemap() to enlarget the storage space.
*/
static int walIndexMap(Wal *pWal, int reqSize){
  int rc = SQLITE_OK;
  if( pWal->pWiData==0 || reqSize>pWal->szWIndex ){
    walIndexUnmap(pWal);
    rc = sqlite3OsShmGet(pWal->pDbFd, reqSize, &pWal->szWIndex,
                             (void volatile**)(char volatile*)&pWal->pWiData);
    if( rc!=SQLITE_OK ){
      walIndexUnmap(pWal);
    }
  }
  return rc;
}

/*
** Enlarge the wal-index to be at least enlargeTo bytes in size and
** Remap the wal-index so that the mapping covers the full size
** of the underlying file.
**
** If enlargeTo is non-negative, then increase the size of the underlying
** storage to be at least as big as enlargeTo before remapping.
*/
static int walIndexRemap(Wal *pWal, int enlargeTo){
  int rc;
  int sz;
  assert( pWal->writeLock );
  rc = sqlite3OsShmSize(pWal->pDbFd, enlargeTo, &sz);
  if( rc==SQLITE_OK && sz>pWal->szWIndex ){
    walIndexUnmap(pWal);
    rc = walIndexMap(pWal, sz);
  }
  assert( pWal->szWIndex>=enlargeTo || rc!=SQLITE_OK );
  return rc;
}

/*
** Compute a hash on a page number.  The resulting hash value must land
** between 0 and (HASHTABLE_NSLOT-1).  The walHashNext() function advances
** the hash to the next value in the event of a collision.
*/
static int walHash(u32 iPage){
  assert( iPage>0 );
................................................................................
  assert( (HASHTABLE_NSLOT & (HASHTABLE_NSLOT-1))==0 );
  return (iPage*HASHTABLE_HASH_1) & (HASHTABLE_NSLOT-1);
}
static int walNextHash(int iPriorHash){
  return (iPriorHash+1)&(HASHTABLE_NSLOT-1);
}


















































/* 
** Find the hash table and (section of the) page number array used to
** store data for WAL frame iFrame.
**
** Set output variable *paHash to point to the start of the hash table
** in the wal-index file. Set *piZero to one less than the frame 
................................................................................
static void walHashFind(
  Wal *pWal,                      /* WAL handle */
  u32 iFrame,                     /* Find the hash table indexing this frame */
  volatile HASHTABLE_DATATYPE **paHash,    /* OUT: Pointer to hash index */
  volatile u32 **paPgno,          /* OUT: Pointer to page number array */
  u32 *piZero                     /* OUT: Frame associated with *paPgno[0] */
){
  u32 iZero;
  volatile u32 *aPgno;
  volatile HASHTABLE_DATATYPE *aHash;

  iZero = ((iFrame-1)/HASHTABLE_NPAGE) * HASHTABLE_NPAGE;
  aPgno = &pWal->pWiData[walIndexEntry(iZero+1)-iZero-1];
  aHash = (HASHTABLE_DATATYPE *)&aPgno[iZero+HASHTABLE_NPAGE+1];

  /* Assert that:
  **
  **   + the mapping is large enough for this hash-table, and
  **
  **   + that aPgno[iZero+1] really is the database page number associated
  **     with the first frame indexed by this hash table.
  */
  assert( (u32*)(&aHash[HASHTABLE_NSLOT])<=&pWal->pWiData[pWal->szWIndex/4] );
  assert( walIndexEntry(iZero+1)==(&aPgno[iZero+1] - pWal->pWiData) );

  *paHash = aHash;
  *paPgno = aPgno;
  *piZero = iZero;
}

/*
** Remove entries from the hash table that point to WAL slots greater
** than pWal->hdr.mxFrame.
**
** This function is called whenever pWal->hdr.mxFrame is decreased due
................................................................................
** actually needed.
*/
static void walCleanupHash(Wal *pWal){
  volatile HASHTABLE_DATATYPE *aHash;  /* Pointer to hash table to clear */
  volatile u32 *aPgno;                 /* Unused return from walHashFind() */
  u32 iZero;                           /* frame == (aHash[x]+iZero) */
  int iLimit = 0;                      /* Zero values greater than this */



  assert( pWal->writeLock );
  testcase( pWal->hdr.mxFrame==HASHTABLE_NPAGE-1 );
  testcase( pWal->hdr.mxFrame==HASHTABLE_NPAGE );
  testcase( pWal->hdr.mxFrame==HASHTABLE_NPAGE+1 );
  if( (pWal->hdr.mxFrame % HASHTABLE_NPAGE)>0 ){
    int nByte;                    /* Number of bytes to zero in aPgno[] */
    int i;                        /* Used to iterate through aHash[] */

    walHashFind(pWal, pWal->hdr.mxFrame+1, &aHash, &aPgno, &iZero);

    iLimit = pWal->hdr.mxFrame - iZero;
    assert( iLimit>0 );
    for(i=0; i<HASHTABLE_NSLOT; i++){
      if( aHash[i]>iLimit ){
        aHash[i] = 0;
      }
    }

    /* Zero the entries in the aPgno array that correspond to frames with
    ** frame numbers greater than pWal->hdr.mxFrame. 
    */
    nByte = sizeof(u32) * (HASHTABLE_NPAGE-iLimit);
    memset((void *)&aPgno[iZero+iLimit+1], 0, nByte);
    assert( &((u8 *)&aPgno[iZero+iLimit+1])[nByte]==(u8 *)aHash );
  }

#ifdef SQLITE_ENABLE_EXPENSIVE_ASSERT
  /* Verify that the every entry in the mapping region is still reachable
  ** via the hash table even after the cleanup.
  */
  if( iLimit ){
................................................................................


/*
** Set an entry in the wal-index that will map database page number
** pPage into WAL frame iFrame.
*/
static int walIndexAppend(Wal *pWal, u32 iFrame, u32 iPage){
  int rc;                         /* Return code */
  int nMapping;                   /* Required mapping size in bytes */
  
  /* Make sure the wal-index is mapped. Enlarge the mapping if required. */
  nMapping = walMappingSize(iFrame);
  rc = walIndexMap(pWal, nMapping);
  while( rc==SQLITE_OK && nMapping>pWal->szWIndex ){
    rc = walIndexRemap(pWal, nMapping);
  }

  /* Assuming the wal-index file was successfully mapped, find the hash 
  ** table and section of of the page number array that pertain to frame 
  ** iFrame of the WAL. Then populate the page number array and the hash 
  ** table entry.
  */
  if( rc==SQLITE_OK ){
................................................................................
    volatile HASHTABLE_DATATYPE *aHash;  /* Hash table */
    int idx;                             /* Value to write to hash-table slot */
    TESTONLY( int nCollide = 0;          /* Number of hash collisions */ )

    walHashFind(pWal, iFrame, &aHash, &aPgno, &iZero);
    idx = iFrame - iZero;
    if( idx==1 ){
      memset((void*)&aPgno[iZero+1], 0, HASHTABLE_NPAGE*sizeof(u32));
      memset((void*)aHash, 0, HASHTABLE_NBYTE);
    }
    assert( idx <= HASHTABLE_NSLOT/2 + 1 );

    if( aPgno[iFrame] ){
      /* If the entry in aPgno[] is already set, then the previous writer
      ** must have exited unexpectedly in the middle of a transaction (after
      ** writing one or more dirty pages to the WAL to free up memory). 
................................................................................
      }
    }

    sqlite3_free(aFrame);
  }

finished:
  if( rc==SQLITE_OK && pWal->hdr.mxFrame==0 ){
    rc = walIndexRemap(pWal, walMappingSize(1));
  }
  if( rc==SQLITE_OK ){
    volatile WalCkptInfo *pInfo;
    int i;
    pWal->hdr.aFrameCksum[0] = aFrameCksum[0];
    pWal->hdr.aFrameCksum[1] = aFrameCksum[1];
    walIndexWriteHdr(pWal);

................................................................................
  if( !pRet ){
    return SQLITE_NOMEM;
  }

  pRet->pVfs = pVfs;
  pRet->pWalFd = (sqlite3_file *)&pRet[1];
  pRet->pDbFd = pDbFd;
  pRet->szWIndex = -1;
  pRet->readLock = -1;
  sqlite3_randomness(8, &pRet->hdr.aSalt);
  pRet->zWalName = zWal = pVfs->szOsFile + (char*)pRet->pWalFd;
  sqlite3_snprintf(nWal, zWal, "%s-wal", zDbName);
  rc = sqlite3OsShmOpen(pDbFd);

  /* Open file handle on the write-ahead log file. */
................................................................................
  WalIterator *p,               /* Iterator */
  u32 *piPage,                  /* OUT: The page number of the next page */
  u32 *piFrame                  /* OUT: Wal frame index of next page */
){
  u32 iMin;                     /* Result pgno must be greater than iMin */
  u32 iRet = 0xFFFFFFFF;        /* 0xffffffff is never a valid page number */
  int i;                        /* For looping through segments */
  int nBlock = p->nFinal;       /* Number of entries in current segment */

  iMin = p->iPrior;
  assert( iMin<0xffffffff );
  for(i=p->nSegment-1; i>=0; i--){
    struct WalSegment *pSegment = &p->aSegment[i];
    while( pSegment->iNext<nBlock ){
      u32 iPg = pSegment->aPgno[pSegment->aIndex[pSegment->iNext]];
      if( iPg>iMin ){
        if( iPg<iRet ){
          iRet = iPg;
          *piFrame = i*256 + 1 + pSegment->aIndex[pSegment->iNext];
        }
        break;
      }
      pSegment->iNext++;
    }
    nBlock = 256;
  }

  *piPage = p->iPrior = iRet;
  return (iRet==0xFFFFFFFF);
}


static void walMergesort8(
  Pgno *aContent,                 /* Pages in wal */
  u8 *aBuffer,                    /* Buffer of at least *pnList items to use */
  u8 *aList,                      /* IN/OUT: List to sort */
  int *pnList                     /* IN/OUT: Number of elements in aList[] */
){
  int nList = *pnList;
  if( nList>1 ){
    int nLeft = nList / 2;        /* Elements in left list */
    int nRight = nList - nLeft;   /* Elements in right list */
    u8 *aLeft = aList;            /* Left list */
    u8 *aRight = &aList[nLeft];   /* Right list */
    int iLeft = 0;                /* Current index in aLeft */
    int iRight = 0;               /* Current index in aright */
    int iOut = 0;                 /* Current index in output buffer */



    /* TODO: Change to non-recursive version. */
    walMergesort8(aContent, aBuffer, aLeft, &nLeft);
    walMergesort8(aContent, aBuffer, aRight, &nRight);

    while( iRight<nRight || iLeft<nLeft ){
      u8 logpage;
      Pgno dbpage;

      if( (iLeft<nLeft) 
       && (iRight>=nRight || aContent[aLeft[iLeft]]<aContent[aRight[iRight]])
      ){
        logpage = aLeft[iLeft++];
      }else{
................................................................................
**
** The calling routine should invoke walIteratorFree() to destroy the
** WalIterator object when it has finished with it.  The caller must
** also unmap the wal-index.  But the wal-index must not be unmapped
** prior to the WalIterator object being destroyed.
*/
static int walIteratorInit(Wal *pWal, WalIterator **pp){
  u32 *aData;           /* Content of the wal-index file */
  WalIterator *p;       /* Return value */
  int nSegment;         /* Number of segments to merge */
  u32 iLast;            /* Last frame in log */
  int nByte;            /* Number of bytes to allocate */
  int i;                /* Iterator variable */
  int nFinal;           /* Number of unindexed entries */
  u8 *aTmp;             /* Temp space used by merge-sort */
  u8 *aSpace;           /* Surplus space on the end of the allocation */

  /* Make sure the wal-index is mapped into local memory */
  assert( pWal->pWiData && pWal->szWIndex>=walMappingSize(pWal->hdr.mxFrame) );

  /* This routine only runs while holding SQLITE_SHM_CHECKPOINT.  No other
  ** thread is able to write to shared memory while this routine is
  ** running (or, indeed, while the WalIterator object exists).  Hence,
  ** we can cast off the volatile qualifacation from shared memory
  */
  assert( pWal->ckptLock );
  aData = (u32*)pWal->pWiData;

  /* Allocate space for the WalIterator object */
  iLast = pWal->hdr.mxFrame;
  nSegment = (iLast >> 8) + 1;
  nFinal = (iLast & 0x000000FF);
  nByte = sizeof(WalIterator) + (nSegment+1)*(sizeof(struct WalSegment)+256);

  p = (WalIterator *)sqlite3_malloc(nByte);
  if( !p ){
    return SQLITE_NOMEM;
  }
  memset(p, 0, nByte);

  /* Initialize the WalIterator object.  Each 256-entry segment is
  ** presorted in order to make iterating through all entries much
  ** faster.
  */
  p->nSegment = nSegment;
  aSpace = (u8 *)&p->aSegment[nSegment];
  aTmp = &aSpace[nSegment*256];
  for(i=0; i<nSegment; i++){

    int j;





    int nIndex = (i==nSegment-1) ? nFinal : 256;
    p->aSegment[i].aPgno = &aData[walIndexEntry(i*256+1)];
    p->aSegment[i].aIndex = aSpace;









    for(j=0; j<nIndex; j++){
      aSpace[j] = j;
    }




    walMergesort8(p->aSegment[i].aPgno, aTmp, aSpace, &nIndex);
    memset(&aSpace[nIndex], aSpace[nIndex-1], 256-nIndex);
    aSpace += 256;
    p->nFinal = nIndex;
  }


  /* Return the fully initializd WalIterator object */
  *pp = p;
  return SQLITE_OK ;
}

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

  /* Compute in mxSafeFrame the index of the last frame of the WAL that is
  ** safe to write into the database.  Frames beyond mxSafeFrame might
  ** overwrite database pages that are in use by active readers and thus
  ** cannot be backfilled from the WAL.
  */
  mxSafeFrame = pWal->hdr.mxFrame;
  pHdr = (volatile WalIndexHdr*)pWal->pWiData;
  pInfo = (volatile WalCkptInfo*)&pHdr[2];
  assert( pInfo==walCkptInfo(pWal) );
  for(i=1; i<WAL_NREADER; i++){
    u32 y = pInfo->aReadMark[i];
    if( mxSafeFrame>=y ){
      assert( y<=pWal->hdr.mxFrame );
      rc = walLockExclusive(pWal, WAL_READ_LOCK(i), 1);
      if( rc==SQLITE_OK ){
................................................................................
    /* Sync the WAL to disk */
    if( sync_flags ){
      rc = sqlite3OsSync(pWal->pWalFd, sync_flags);
    }

    /* Iterate through the contents of the WAL, copying data to the db file. */
    while( rc==SQLITE_OK && 0==walIteratorNext(pIter, &iDbpage, &iFrame) ){

      if( iFrame<=nBackfill || iFrame>mxSafeFrame ) continue;
      rc = sqlite3OsRead(pWal->pWalFd, zBuf, szPage, 
          walFrameOffset(iFrame, szPage) + WAL_FRAME_HDRSIZE
      );
      if( rc!=SQLITE_OK ) break;
      rc = sqlite3OsWrite(pWal->pDbFd, zBuf, szPage, (iDbpage-1)*szPage);
      if( rc!=SQLITE_OK ) break;
................................................................................
    rc = sqlite3OsLock(pWal->pDbFd, SQLITE_LOCK_EXCLUSIVE);
    if( rc==SQLITE_OK ){
      pWal->exclusiveMode = 1;
      rc = sqlite3WalCheckpoint(pWal, sync_flags, nBuf, zBuf);
      if( rc==SQLITE_OK ){
        isDelete = 1;
      }
      walIndexUnmap(pWal);
    }

    walIndexClose(pWal, isDelete);
    sqlite3OsClose(pWal->pWalFd);
    if( isDelete ){
      sqlite3OsDelete(pWal->pVfs, pWal->zWalName, 0);
    }
    WALTRACE(("WAL%p: closed\n", pWal));

    sqlite3_free(pWal);
  }
  return rc;
}

/*
** Try to read the wal-index header.  Return 0 on success and 1 if
................................................................................
** If the checksum cannot be verified return non-zero. If the header
** is read successfully and the checksum verified, return zero.
*/
int walIndexTryHdr(Wal *pWal, int *pChanged){
  u32 aCksum[2];               /* Checksum on the header content */
  WalIndexHdr h1, h2;          /* Two copies of the header content */
  WalIndexHdr *aHdr;           /* Header in shared memory */


  if( pWal->szWIndex < WALINDEX_HDR_SIZE ){


    /* The wal-index is not large enough to hold the header, then assume
    ** header is invalid. */
    return 1;
  }
  assert( pWal->pWiData );

  /* Read the header. This might happen currently with a write to the
  ** same area of shared memory on a different CPU in a SMP,
  ** meaning it is possible that an inconsistent snapshot is read
  ** from the file. If this happens, return non-zero.
  **
  ** There are two copies of the header at the beginning of the wal-index.
  ** When reading, read [0] first then [1].  Writes are in the reverse order.
  ** Memory barriers are used to prevent the compiler or the hardware from
  ** reordering the reads and writes.
  */
  aHdr = (WalIndexHdr*)pWal->pWiData;
  memcpy(&h1, &aHdr[0], sizeof(h1));
  sqlite3OsShmBarrier(pWal->pDbFd);
  memcpy(&h2, &aHdr[1], sizeof(h2));

  if( memcmp(&h1, &h2, sizeof(h1))!=0 ){
    return 1;   /* Dirty read */
  }  
................................................................................
**
** If the wal-index header is successfully read, return SQLITE_OK. 
** Otherwise an SQLite error code.
*/
static int walIndexReadHdr(Wal *pWal, int *pChanged){
  int rc;                         /* Return code */
  int badHdr;                     /* True if a header read failed */


  assert( pChanged );
  rc = walIndexMap(pWal, walMappingSize(1));

  if( rc!=SQLITE_OK ){
    return rc;
  }

  /* Try once to read the header straight out.  This works most of the
  ** time.
  */
................................................................................
        *pChanged = 1;
      }
      walUnlockExclusive(pWal, WAL_WRITE_LOCK, 1);
      pWal->writeLock = 0;
    }
  }

  /* Make sure the mapping is large enough to cover the entire wal-index */
  if( rc==SQLITE_OK ){
    int szWanted = walMappingSize(pWal->hdr.mxFrame);
    if( pWal->szWIndex<szWanted ){
      rc = walIndexMap(pWal, szWanted);
    }
  }

  return rc;
}

/*
** This is the value that walTryBeginRead returns when it needs to
** be retried.
*/
................................................................................
*/
static int walTryBeginRead(Wal *pWal, int *pChanged, int useWal, int cnt){
  volatile WalIndexHdr *pHdr;     /* Header of the wal-index */
  volatile WalCkptInfo *pInfo;    /* Checkpoint information in wal-index */
  u32 mxReadMark;                 /* Largest aReadMark[] value */
  int mxI;                        /* Index of largest aReadMark[] value */
  int i;                          /* Loop counter */
  int rc;                         /* Return code  */

  assert( pWal->readLock<0 );     /* Not currently locked */

  /* Take steps to avoid spinning forever if there is a protocol error. */
  if( cnt>5 ){
    if( cnt>100 ) return SQLITE_PROTOCOL;
    sqlite3OsSleep(pWal->pVfs, 1);
................................................................................
      if( rc==SQLITE_OK ){
        walUnlockShared(pWal, WAL_RECOVER_LOCK);
        rc = WAL_RETRY;
      }else if( rc==SQLITE_BUSY ){
        rc = SQLITE_BUSY_RECOVERY;
      }
    }
  }else{
    rc = walIndexMap(pWal, walMappingSize(pWal->hdr.mxFrame));
  }
  if( rc!=SQLITE_OK ){
    return rc;
  }

  pHdr = (volatile WalIndexHdr*)pWal->pWiData;
  pInfo = (volatile WalCkptInfo*)&pHdr[2];
  assert( pInfo==walCkptInfo(pWal) );
  if( !useWal && pInfo->nBackfill==pWal->hdr.mxFrame ){
    /* The WAL has been completely backfilled (or it is empty).
    ** and can be safely ignored.
    */
    rc = walLockShared(pWal, WAL_READ_LOCK(0));
    sqlite3OsShmBarrier(pWal->pDbFd);
    if( rc==SQLITE_OK ){
................................................................................
int sqlite3WalBeginReadTransaction(Wal *pWal, int *pChanged){
  int rc;                         /* Return code */
  int cnt = 0;                    /* Number of TryBeginRead attempts */

  do{
    rc = walTryBeginRead(pWal, pChanged, 0, ++cnt);
  }while( rc==WAL_RETRY );
  walIndexUnmap(pWal);
  return rc;
}

/*
** Finish with a read transaction.  All this does is release the
** read-lock.
*/
................................................................................
int sqlite3WalRead(
  Wal *pWal,                      /* WAL handle */
  Pgno pgno,                      /* Database page number to read data for */
  int *pInWal,                    /* OUT: True if data is read from WAL */
  int nOut,                       /* Size of buffer pOut in bytes */
  u8 *pOut                        /* Buffer to write page data to */
){
  int rc;                         /* Return code */
  u32 iRead = 0;                  /* If !=0, WAL frame to return data from */
  u32 iLast = pWal->hdr.mxFrame;  /* Last page in WAL for this reader */
  int iHash;                      /* Used to loop through N hash tables */

  /* This routine is only be called from within a read transaction. */
  assert( pWal->readLock>=0 || pWal->lockError );

................................................................................
  ** return early, as if the WAL were empty.
  */
  if( iLast==0 || pWal->readLock==0 ){
    *pInWal = 0;
    return SQLITE_OK;
  }

  /* Ensure the wal-index is mapped. */
  rc = walIndexMap(pWal, walMappingSize(iLast));
  if( rc!=SQLITE_OK ){
    return rc;
  }

  /* Search the hash table or tables for an entry matching page number
  ** pgno. Each iteration of the following for() loop searches one
  ** hash table (each hash table indexes up to HASHTABLE_NPAGE frames).
  **
  ** This code may run concurrently to the code in walIndexAppend()
  ** that adds entries to the wal-index (and possibly to this hash 
  ** table). This means the value just read from the hash 
................................................................................
  **   (aPgno[iFrame]==pgno): 
  **     This condition filters out normal hash-table collisions.
  **
  **   (iFrame<=iLast): 
  **     This condition filters out entries that were added to the hash
  **     table after the current read-transaction had started.
  */
  for(iHash=iLast; iHash>0 && iRead==0; iHash-=HASHTABLE_NPAGE){
    volatile HASHTABLE_DATATYPE *aHash;  /* Pointer to hash table */
    volatile u32 *aPgno;                 /* Pointer to array of page numbers */
    u32 iZero;                    /* Frame number corresponding to aPgno[0] */
    int iKey;                     /* Hash slot index */
    int mxHash;                   /* upper bound on aHash[] values */

    walHashFind(pWal, iHash, &aHash, &aPgno, &iZero);
    mxHash = iLast - iZero;
    if( mxHash > HASHTABLE_NPAGE )  mxHash = HASHTABLE_NPAGE;
    for(iKey=walHash(pgno); aHash[iKey]; iKey=walNextHash(iKey)){
      u32 iFrame = aHash[iKey] + iZero;
      if( iFrame<=iLast && aPgno[iFrame]==pgno ){
        assert( iFrame>iRead );
        iRead = iFrame;
      }
    }
  }
  assert( iRead==0 || pWal->pWiData[walIndexEntry(iRead)]==pgno );

#ifdef SQLITE_ENABLE_EXPENSIVE_ASSERT
  /* If expensive assert() statements are available, do a linear search
  ** of the wal-index file content. Make sure the results agree with the
  ** result obtained using the hash indexes above.  */
  {
    u32 iRead2 = 0;
    u32 iTest;
    for(iTest=iLast; iTest>0; iTest--){
      if( pWal->pWiData[walIndexEntry(iTest)]==pgno ){
        iRead2 = iTest;
        break;
      }
    }
    assert( iRead==iRead2 );
  }
#endif

  /* If iRead is non-zero, then it is the log frame number that contains the
  ** required page. Read and return data from the log file.
  */
  walIndexUnmap(pWal);
  if( iRead ){
    i64 iOffset = walFrameOffset(iRead, pWal->hdr.szPage) + WAL_FRAME_HDRSIZE;
    *pInWal = 1;
    return sqlite3OsRead(pWal->pWalFd, pOut, nOut, iOffset);
  }

  *pInWal = 0;
................................................................................
** thread to write as doing so would cause a fork.  So this routine
** returns SQLITE_BUSY in that case and no write transaction is started.
**
** There can only be a single writer active at a time.
*/
int sqlite3WalBeginWriteTransaction(Wal *pWal){
  int rc;


  /* Cannot start a write transaction without first holding a read
  ** transaction. */
  assert( pWal->readLock>=0 );

  /* Only one writer allowed at a time.  Get the write lock.  Return
  ** SQLITE_BUSY if unable.
................................................................................
  }
  pWal->writeLock = 1;

  /* If another connection has written to the database file since the
  ** time the read transaction on this connection was started, then
  ** the write is disallowed.
  */
  rc = walIndexMap(pWal, walMappingSize(pWal->hdr.mxFrame));
  if( rc ){
    walUnlockExclusive(pWal, WAL_WRITE_LOCK, 1);
    pWal->writeLock = 0;
    return rc;
  }
  if( memcmp(&pWal->hdr, (void*)pWal->pWiData, sizeof(WalIndexHdr))!=0 ){
    walUnlockExclusive(pWal, WAL_WRITE_LOCK, 1);
    pWal->writeLock = 0;
    rc = SQLITE_BUSY;
  }

  walIndexUnmap(pWal);
  return rc;
}

/*
** End a write transaction.  The commit has already been done.  This
** routine merely releases the lock.
*/
................................................................................
int sqlite3WalUndo(Wal *pWal, int (*xUndo)(void *, Pgno), void *pUndoCtx){
  int rc = SQLITE_OK;
  if( pWal->writeLock ){
    int unused;
    Pgno iMax = pWal->hdr.mxFrame;
    Pgno iFrame;
  
    assert( pWal->pWiData==0 );
    rc = walIndexReadHdr(pWal, &unused);
    if( rc==SQLITE_OK ){
      rc = walIndexMap(pWal, walMappingSize(iMax));
    }
    if( rc==SQLITE_OK ){
      for(iFrame=pWal->hdr.mxFrame+1; 
          ALWAYS(rc==SQLITE_OK) && iFrame<=iMax; 
          iFrame++
      ){
        /* This call cannot fail. Unless the page for which the page number
        ** is passed as the second argument is (a) in the cache and 
................................................................................
        **
        ** If the upper layer is doing a rollback, it is guaranteed that there
        ** are no outstanding references to any page other than page 1. And
        ** page 1 is never written to the log until the transaction is
        ** committed. As a result, the call to xUndo may not fail.
        */
        assert( pWal->writeLock );
        assert( pWal->pWiData[walIndexEntry(iFrame)]!=1 );
        rc = xUndo(pUndoCtx, pWal->pWiData[walIndexEntry(iFrame)]);
      }
      walCleanupHash(pWal);
    }
    walIndexUnmap(pWal);
  }
  return rc;
}

/* 
** Argument aWalData must point to an array of WAL_SAVEPOINT_NDATA u32 
** values. This function populates the array with values required to 
................................................................................
    ** to the start of the log. Update the savepoint values to match.
    */
    aWalData[0] = 0;
    aWalData[3] = pWal->nCkpt;
  }

  if( aWalData[0]<pWal->hdr.mxFrame ){
    rc = walIndexMap(pWal, walMappingSize(pWal->hdr.mxFrame));
    pWal->hdr.mxFrame = aWalData[0];
    pWal->hdr.aFrameCksum[0] = aWalData[1];
    pWal->hdr.aFrameCksum[1] = aWalData[2];
    if( rc==SQLITE_OK ){
      walCleanupHash(pWal);
    }
  }

  walIndexUnmap(pWal);
  return rc;
}

/*
** This function is called just before writing a set of frames to the log
** file (see sqlite3WalFrames()). It checks to see if, instead of appending
** to the current log file, it is possible to overwrite the start of the
................................................................................
** or not pWal->hdr.mxFrame is modified). An SQLite error code is returned
** if some error 
*/
static int walRestartLog(Wal *pWal){
  int rc = SQLITE_OK;
  int cnt;

  if( pWal->readLock==0 
   && SQLITE_OK==(rc = walIndexMap(pWal, walMappingSize(pWal->hdr.mxFrame)))
  ){
    volatile WalCkptInfo *pInfo = walCkptInfo(pWal);
    assert( pInfo->nBackfill==pWal->hdr.mxFrame );
    if( pInfo->nBackfill>0 ){
      rc = walLockExclusive(pWal, WAL_READ_LOCK(1), WAL_NREADER-1);
      if( rc==SQLITE_OK ){
        /* If all readers are using WAL_READ_LOCK(0) (in other words if no
        ** readers are currently using the WAL), then the transactions
................................................................................
    walUnlockShared(pWal, WAL_READ_LOCK(0));
    pWal->readLock = -1;
    cnt = 0;
    do{
      int notUsed;
      rc = walTryBeginRead(pWal, &notUsed, 1, ++cnt);
    }while( rc==WAL_RETRY );

    /* Unmap the wal-index before returning. Otherwise the VFS layer may
    ** hold a mutex for the duration of the IO performed by WalFrames().
    */
    walIndexUnmap(pWal);
  }
  return rc;
}

/* 
** Write a set of frames to the log. The caller must hold the write-lock
** on the log file (obtained using sqlite3WalBeginWriteTransaction()).
................................................................................
  u8 aFrame[WAL_FRAME_HDRSIZE];   /* Buffer to assemble frame-header in */
  PgHdr *p;                       /* Iterator to run through pList with. */
  PgHdr *pLast = 0;               /* Last frame in list */
  int nLast = 0;                  /* Number of extra copies of last page */

  assert( pList );
  assert( pWal->writeLock );
  assert( pWal->pWiData==0 );

#if defined(SQLITE_TEST) && defined(SQLITE_DEBUG)
  { int cnt; for(cnt=0, p=pList; p; p=p->pDirty, cnt++){}
    WALTRACE(("WAL%p: frame write begin. %d frames. mxFrame=%d. %s\n",
              pWal, cnt, pWal->hdr.mxFrame, isCommit ? "Commit" : "Spill"));
  }
#endif

  /* See if it is possible to write these frames into the start of the
  ** log file, instead of appending to it at pWal->hdr.mxFrame.
  */
  if( SQLITE_OK!=(rc = walRestartLog(pWal)) ){
    assert( pWal->pWiData==0 );
    return rc;
  }
  assert( pWal->pWiData==0 && pWal->readLock>0 );

  /* If this is the first frame written into the log, write the WAL
  ** header to the start of the WAL file. See comments at the top of
  ** this source file for a description of the WAL header format.
  */
  iFrame = pWal->hdr.mxFrame;
  if( iFrame==0 ){
................................................................................
      }
      nLast++;
      iOffset += szPage;
    }

    rc = sqlite3OsSync(pWal->pWalFd, sync_flags);
  }
  assert( pWal->pWiData==0 );

  /* Append data to the wal-index. It is not necessary to lock the 
  ** wal-index to do this as the SQLITE_SHM_WRITE lock held on the wal-index
  ** guarantees that there are no other writers, and no data that may
  ** be in use by existing readers is being overwritten.
  */
  iFrame = pWal->hdr.mxFrame;
................................................................................
    /* If this is a commit, update the wal-index header too. */
    if( isCommit ){
      walIndexWriteHdr(pWal);
      pWal->iCallback = iFrame;
    }
  }

  walIndexUnmap(pWal);
  WALTRACE(("WAL%p: frame write %s\n", pWal, rc ? "failed" : "ok"));
  return rc;
}

/* 
** This routine is called to implement sqlite3_wal_checkpoint() and
** related interfaces.
................................................................................
  int sync_flags,                 /* Flags to sync db file with (or 0) */
  int nBuf,                       /* Size of temporary buffer */
  u8 *zBuf                        /* Temporary buffer to use */
){
  int rc;                         /* Return code */
  int isChanged = 0;              /* True if a new wal-index header is loaded */

  assert( pWal->pWiData==0 );
  assert( pWal->ckptLock==0 );

  WALTRACE(("WAL%p: checkpoint begins\n", pWal));
  rc = walLockExclusive(pWal, WAL_CKPT_LOCK, 1);
  if( rc ){
    /* Usually this is SQLITE_BUSY meaning that another thread or process
    ** is already running a checkpoint, or maybe a recovery.  But it might
................................................................................
    ** next time the pager opens a snapshot on this database it knows that
    ** the cache needs to be reset.
    */
    memset(&pWal->hdr, 0, sizeof(WalIndexHdr));
  }

  /* Release the locks. */
  walIndexUnmap(pWal);
  walUnlockExclusive(pWal, WAL_CKPT_LOCK, 1);
  pWal->ckptLock = 0;
  WALTRACE(("WAL%p: checkpoint %s\n", pWal, rc ? "failed" : "ok"));
  return rc;
}

/* Return the value to pass to a sqlite3_wal_hook callback, the







|
|















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



>
>
|
|

<







 







<

|
|
|
>
>
|







 







|







 







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







 







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







 







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







 







|
|
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<







 







>
>





<
<
<

|
>







|



|
|
<







 







|
<
<
<
<
<
<
<
<







 







|
|







 







<
<
<







 







<







 







<





|




|





<







|
|
|
|






<
<



>
>


|
|


|







 







<





<
|
|
<
<
<




|


|


|
|
<
|
>






|
<
<
<

|
|

>

>
>
>
>
>
|
<
<
>
>
>
>
>
>
>
>
>
|


>
>
>
>
|
<
|
<

>

|







 







|
|







 







>







 







<








>







 







>

<
>
>




<











|







 







>


<
>







 







<
<
<
<
<
<
<
<







 







|







 







<
<





|
|
|







 







<







 







<







 







<
<
<
<
<
<







 







|




<

|
<
<








<









|











<







 







>







 







|
<
<
<
<
<
|





<







 







<

<
<
<







 







|
|



<







 







<








<







 







|
<
<







 







<
<
<
<
<







 







<












<


<







 







<







 







<







 







<







 







<







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
...
471
472
473
474
475
476
477

478
479
480
481
482
483
484
485
486
487
488
489
490
491
...
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
...
645
646
647
648
649
650
651













652
653
654
655
656
657
658
...
709
710
711
712
713
714
715


























































































716
717
718
719
720
721
722
...
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
...
793
794
795
796
797
798
799
800
801



















802
803
804
805
806
807
808
...
814
815
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
...
862
863
864
865
866
867
868
869








870
871
872
873
874
875
876
...
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
....
1052
1053
1054
1055
1056
1057
1058



1059
1060
1061
1062
1063
1064
1065
....
1137
1138
1139
1140
1141
1142
1143

1144
1145
1146
1147
1148
1149
1150
....
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
1213
1214
1215
1216
1217
1218


1219
1220
1221
1222
1223
1224
1225
1226
1227
1228
1229
1230
1231
1232
1233
1234
1235
1236
1237
....
1270
1271
1272
1273
1274
1275
1276

1277
1278
1279
1280
1281

1282
1283



1284
1285
1286
1287
1288
1289
1290
1291
1292
1293
1294
1295

1296
1297
1298
1299
1300
1301
1302
1303
1304



1305
1306
1307
1308
1309
1310
1311
1312
1313
1314
1315
1316


1317
1318
1319
1320
1321
1322
1323
1324
1325
1326
1327
1328
1329
1330
1331
1332
1333

1334

1335
1336
1337
1338
1339
1340
1341
1342
1343
1344
1345
....
1408
1409
1410
1411
1412
1413
1414
1415
1416
1417
1418
1419
1420
1421
1422
1423
....
1439
1440
1441
1442
1443
1444
1445
1446
1447
1448
1449
1450
1451
1452
1453
....
1504
1505
1506
1507
1508
1509
1510

1511
1512
1513
1514
1515
1516
1517
1518
1519
1520
1521
1522
1523
1524
1525
1526
....
1539
1540
1541
1542
1543
1544
1545
1546
1547

1548
1549
1550
1551
1552
1553

1554
1555
1556
1557
1558
1559
1560
1561
1562
1563
1564
1565
1566
1567
1568
1569
1570
1571
1572
....
1605
1606
1607
1608
1609
1610
1611
1612
1613
1614

1615
1616
1617
1618
1619
1620
1621
1622
....
1640
1641
1642
1643
1644
1645
1646








1647
1648
1649
1650
1651
1652
1653
....
1683
1684
1685
1686
1687
1688
1689
1690
1691
1692
1693
1694
1695
1696
1697
....
1712
1713
1714
1715
1716
1717
1718


1719
1720
1721
1722
1723
1724
1725
1726
1727
1728
1729
1730
1731
1732
1733
....
1854
1855
1856
1857
1858
1859
1860

1861
1862
1863
1864
1865
1866
1867
....
1883
1884
1885
1886
1887
1888
1889

1890
1891
1892
1893
1894
1895
1896
....
1901
1902
1903
1904
1905
1906
1907






1908
1909
1910
1911
1912
1913
1914
....
1926
1927
1928
1929
1930
1931
1932
1933
1934
1935
1936
1937

1938
1939


1940
1941
1942
1943
1944
1945
1946
1947

1948
1949
1950
1951
1952
1953
1954
1955
1956
1957
1958
1959
1960
1961
1962
1963
1964
1965
1966
1967
1968

1969
1970
1971
1972
1973
1974
1975
....
1997
1998
1999
2000
2001
2002
2003
2004
2005
2006
2007
2008
2009
2010
2011
....
2016
2017
2018
2019
2020
2021
2022
2023





2024
2025
2026
2027
2028
2029

2030
2031
2032
2033
2034
2035
2036
....
2055
2056
2057
2058
2059
2060
2061

2062



2063
2064
2065
2066
2067
2068
2069
....
2073
2074
2075
2076
2077
2078
2079
2080
2081
2082
2083
2084

2085
2086
2087
2088
2089
2090
2091
....
2118
2119
2120
2121
2122
2123
2124

2125
2126
2127
2128
2129
2130
2131
2132

2133
2134
2135
2136
2137
2138
2139
....
2145
2146
2147
2148
2149
2150
2151
2152


2153
2154
2155
2156
2157
2158
2159
....
2181
2182
2183
2184
2185
2186
2187





2188
2189
2190
2191
2192
2193
2194
....
2206
2207
2208
2209
2210
2211
2212

2213
2214
2215
2216
2217
2218
2219
2220
2221
2222
2223
2224

2225
2226

2227
2228
2229
2230
2231
2232
2233
....
2294
2295
2296
2297
2298
2299
2300

2301
2302
2303
2304
2305
2306
2307
....
2326
2327
2328
2329
2330
2331
2332

2333
2334
2335
2336
2337
2338
2339
....
2346
2347
2348
2349
2350
2351
2352

2353
2354
2355
2356
2357
2358
2359
....
2374
2375
2376
2377
2378
2379
2380

2381
2382
2383
2384
2385
2386
2387
** following object.
*/
struct Wal {
  sqlite3_vfs *pVfs;         /* The VFS used to create pDbFd */
  sqlite3_file *pDbFd;       /* File handle for the database file */
  sqlite3_file *pWalFd;      /* File handle for WAL file */
  u32 iCallback;             /* Value to pass to log callback (or 0) */
  int nWiData;               /* Size of array apWiData */
  volatile u32 **apWiData;   /* Pointer to wal-index content in memory */
  u16 szPage;                /* Database page size */
  i16 readLock;              /* Which read lock is being held.  -1 for none */
  u8 exclusiveMode;          /* Non-zero if connection is in exclusive mode */
  u8 isWIndexOpen;           /* True if ShmOpen() called on pDbFd */
  u8 writeLock;              /* True if in a write transaction */
  u8 ckptLock;               /* True if holding a checkpoint lock */
  WalIndexHdr hdr;           /* Wal-index header for current transaction */
  char *zWalName;            /* Name of WAL file */
  u32 nCkpt;                 /* Checkpoint sequence counter in the wal-header */
#ifdef SQLITE_DEBUG
  u8 lockError;              /* True if a locking error has occurred */
#endif
};

/*
** Define the parameters of the hash tables in the wal-index file. There
** is a hash-table following every HASHTABLE_NPAGE page numbers in the
** wal-index.
**
** Changing any of these constants will alter the wal-index format and
** create incompatibilities.
*/
#define HASHTABLE_NPAGE      4096  /* Must be power of 2 and multiple of 256 */
#define HASHTABLE_DATATYPE   u16
#define HASHTABLE_HASH_1     383                  /* Should be prime */
#define HASHTABLE_NSLOT      (HASHTABLE_NPAGE*2)  /* Must be a power of 2 */
#define HASHTABLE_NBYTE      (sizeof(HASHTABLE_DATATYPE)*HASHTABLE_NSLOT)

/* The block of page numbers associated with the first hash-table in a
** wal-index is smaller than usual. This is so that there is a complete
** hash-table on each aligned 32KB page of the wal-index.
*/
#define HASHTABLE_NPAGE_ONE  (4096 - (WALINDEX_HDR_SIZE/sizeof(u32)))

/* The wal-index is divided into pages of HASHTABLE_PAGESIZE bytes each. */
#define HASHTABLE_PAGESIZE   (HASHTABLE_NBYTE + HASHTABLE_NPAGE*sizeof(u32))

/*
** Obtain a pointer to the iPage'th page of the wal-index. The wal-index
** is broken into pages of HASHTABLE_PAGESIZE bytes. Wal-index pages are
** numbered from zero.
**
** If this call is successful, *ppPage is set to point to the wal-index
** page and SQLITE_OK is returned. If an error (an OOM or VFS error) occurs,
** then an SQLite error code is returned and *ppPage is set to 0.
*/
static int walIndexPage(Wal *pWal, int iPage, volatile u32 **ppPage){
  int rc = SQLITE_OK;

  /* Enlarge the pWal->apWiData[] array if required */
  if( pWal->nWiData<=iPage ){
    int nByte = sizeof(u32 *)*(iPage+1);
    volatile u32 **apNew;
    apNew = (volatile u32 **)sqlite3_realloc(pWal->apWiData, nByte);
    if( !apNew ){
      *ppPage = 0;
      return SQLITE_NOMEM;
    }
    memset(&apNew[pWal->nWiData], 0, sizeof(u32 *)*(iPage+1-pWal->nWiData));
    pWal->apWiData = apNew;
    pWal->nWiData = iPage+1;
  }

  /* Request a pointer to the required page from the VFS */
  if( pWal->apWiData[iPage]==0 ){
    rc = sqlite3OsShmPage(pWal->pDbFd, iPage, HASHTABLE_PAGESIZE, 
        pWal->writeLock, (void volatile **)&pWal->apWiData[iPage]
    );
  }

  *ppPage = pWal->apWiData[iPage];
  assert( iPage==0 || *ppPage || rc!=SQLITE_OK );
  return rc;
}

/*
** Return a pointer to the WalCkptInfo structure in the wal-index.
*/
static volatile WalCkptInfo *walCkptInfo(Wal *pWal){
  volatile u32 *page1 = 0;
  walIndexPage(pWal, 0, &page1);
  assert( page1 );
  return (volatile WalCkptInfo*)&page1[sizeof(WalIndexHdr)/2];
}


/*
** This structure is used to implement an iterator that loops through
** all frames in the WAL in database page order. Where two or more frames
** correspond to the same database page, the iterator visits only the 
** frame most recently written to the WAL (in other words, the frame with
** the largest index).
................................................................................
**   walIteratorFree() - Free an iterator.
**
** This functionality is used by the checkpoint code (see walCheckpoint()).
*/
struct WalIterator {
  int iPrior;           /* Last result returned from the iterator */
  int nSegment;         /* Size of the aSegment[] array */

  struct WalSegment {
    int iNext;                    /* Next slot in aIndex[] not yet returned */
    HASHTABLE_DATATYPE *aIndex;   /* i0, i1, i2... such that aPgno[iN] ascend */
    u32 *aPgno;                   /* Array of page numbers. */
    int nEntry;                   /* Max size of aPgno[] and aIndex[] arrays */
    int iZero;                    /* Frame number associated with aPgno[0] */
  } aSegment[1];        /* One for every 32KB page in the WAL */
};

/*
** The argument to this macro must be of type u32. On a little-endian
** architecture, it returns the u32 value that results from interpreting
** the 4 bytes as a big-endian value. On a big-endian architecture, it
** returns the value that would be produced by intepreting the 4 bytes
................................................................................
static void walIndexWriteHdr(Wal *pWal){
  WalIndexHdr *aHdr;

  assert( pWal->writeLock );
  pWal->hdr.isInit = 1;
  walChecksumBytes(1, (u8*)&pWal->hdr, offsetof(WalIndexHdr, aCksum),
                   0, pWal->hdr.aCksum);
  walIndexPage(pWal, 0, (volatile u32 **)&aHdr);
  memcpy(&aHdr[1], &pWal->hdr, sizeof(WalIndexHdr));
  sqlite3OsShmBarrier(pWal->pDbFd);
  memcpy(&aHdr[0], &pWal->hdr, sizeof(WalIndexHdr));
}

/*
** This function encodes a single frame header and writes it to a buffer
................................................................................
  ** and the new database size.
  */
  *piPage = pgno;
  *pnTruncate = sqlite3Get4byte(&aFrame[4]);
  return 1;
}















#if defined(SQLITE_TEST) && defined(SQLITE_DEBUG)
/*
** Names of locks.  This routine is used to provide debugging output and is not
** a part of an ordinary build.
*/
static const char *walLockName(int lockIdx){
................................................................................
  if( pWal->exclusiveMode ) return;
  (void)sqlite3OsShmLock(pWal->pDbFd, lockIdx, n,
                         SQLITE_SHM_UNLOCK | SQLITE_SHM_EXCLUSIVE);
  WALTRACE(("WAL%p: release EXCLUSIVE-%s cnt=%d\n", pWal,
             walLockName(lockIdx), n));
}



























































































/*
** Compute a hash on a page number.  The resulting hash value must land
** between 0 and (HASHTABLE_NSLOT-1).  The walHashNext() function advances
** the hash to the next value in the event of a collision.
*/
static int walHash(u32 iPage){
  assert( iPage>0 );
................................................................................
  assert( (HASHTABLE_NSLOT & (HASHTABLE_NSLOT-1))==0 );
  return (iPage*HASHTABLE_HASH_1) & (HASHTABLE_NSLOT-1);
}
static int walNextHash(int iPriorHash){
  return (iPriorHash+1)&(HASHTABLE_NSLOT-1);
}

static void walHashGet(
  Wal *pWal,                      /* WAL handle */
  int iHash,                      /* Find the iHash'th table */
  volatile HASHTABLE_DATATYPE **paHash,     /* OUT: Pointer to hash index */
  volatile u32 **paPgno,          /* OUT: Pointer to page number array */
  u32 *piZero                     /* OUT: Frame associated with *paPgno[0] */
){
  u32 iZero;
  volatile u32 *aPgno;
  volatile HASHTABLE_DATATYPE *aHash;

  walIndexPage(pWal, iHash, &aPgno);
  aHash = (volatile HASHTABLE_DATATYPE *)&aPgno[HASHTABLE_NPAGE];

  if( iHash==0 ){
    aPgno = &aPgno[WALINDEX_HDR_SIZE/sizeof(u32)-1];
    iZero = 0;
  }else{
    iZero = HASHTABLE_NPAGE_ONE + (iHash-1)*HASHTABLE_NPAGE;
    aPgno = &aPgno[-1*iZero-1];
  }

  *paPgno = aPgno;
  *paHash = aHash;
  *piZero = iZero;
}

static int walFramePage(u32 iFrame){
  int iHash = (iFrame+HASHTABLE_NPAGE-HASHTABLE_NPAGE_ONE-1) / HASHTABLE_NPAGE;
  assert( (iHash==0 || iFrame>HASHTABLE_NPAGE_ONE)
       && (iHash>=1 || iFrame<=HASHTABLE_NPAGE_ONE)
       && (iHash<=1 || iFrame>(HASHTABLE_NPAGE_ONE+HASHTABLE_NPAGE))
       && (iHash>=2 || iFrame<=HASHTABLE_NPAGE_ONE+HASHTABLE_NPAGE)
       && (iHash<=2 || iFrame>(HASHTABLE_NPAGE_ONE+2*HASHTABLE_NPAGE))
  );
  return iHash;
}

/*
** Return the page number associated with frame iFrame in this WAL.
*/
static u32 walFramePgno(Wal *pWal, u32 iFrame){
  int iHash = walFramePage(iFrame);
  if( iHash==0 ){
    return pWal->apWiData[0][WALINDEX_HDR_SIZE/sizeof(u32) + iFrame - 1];
  }
  return pWal->apWiData[iHash][(iFrame-1-HASHTABLE_NPAGE_ONE)%HASHTABLE_NPAGE];
}

/* 
** Find the hash table and (section of the) page number array used to
** store data for WAL frame iFrame.
**
** Set output variable *paHash to point to the start of the hash table
** in the wal-index file. Set *piZero to one less than the frame 
................................................................................
static void walHashFind(
  Wal *pWal,                      /* WAL handle */
  u32 iFrame,                     /* Find the hash table indexing this frame */
  volatile HASHTABLE_DATATYPE **paHash,    /* OUT: Pointer to hash index */
  volatile u32 **paPgno,          /* OUT: Pointer to page number array */
  u32 *piZero                     /* OUT: Frame associated with *paPgno[0] */
){
  int iHash = walFramePage(iFrame);
  walHashGet(pWal, iHash, paHash, paPgno, piZero);



















}

/*
** Remove entries from the hash table that point to WAL slots greater
** than pWal->hdr.mxFrame.
**
** This function is called whenever pWal->hdr.mxFrame is decreased due
................................................................................
** actually needed.
*/
static void walCleanupHash(Wal *pWal){
  volatile HASHTABLE_DATATYPE *aHash;  /* Pointer to hash table to clear */
  volatile u32 *aPgno;                 /* Unused return from walHashFind() */
  u32 iZero;                           /* frame == (aHash[x]+iZero) */
  int iLimit = 0;                      /* Zero values greater than this */
  int nByte;                           /* Number of bytes to zero in aPgno[] */
  int i;                               /* Used to iterate through aHash[] */

  assert( pWal->writeLock );
  testcase( pWal->hdr.mxFrame==HASHTABLE_NPAGE-1 );
  testcase( pWal->hdr.mxFrame==HASHTABLE_NPAGE );
  testcase( pWal->hdr.mxFrame==HASHTABLE_NPAGE+1 );




  walHashFind(pWal, pWal->hdr.mxFrame+1, &aHash, &aPgno, &iZero);
  if( iZero!=pWal->hdr.mxFrame ){
    iLimit = pWal->hdr.mxFrame - iZero;
    assert( iLimit>0 );
    for(i=0; i<HASHTABLE_NSLOT; i++){
      if( aHash[i]>iLimit ){
        aHash[i] = 0;
      }
    }
  
    /* Zero the entries in the aPgno array that correspond to frames with
    ** frame numbers greater than pWal->hdr.mxFrame. 
    */
    nByte = ((char *)aHash - (char *)&aPgno[pWal->hdr.mxFrame+1]);
    memset((void *)&aPgno[pWal->hdr.mxFrame+1], 0, nByte);

  }

#ifdef SQLITE_ENABLE_EXPENSIVE_ASSERT
  /* Verify that the every entry in the mapping region is still reachable
  ** via the hash table even after the cleanup.
  */
  if( iLimit ){
................................................................................


/*
** Set an entry in the wal-index that will map database page number
** pPage into WAL frame iFrame.
*/
static int walIndexAppend(Wal *pWal, u32 iFrame, u32 iPage){
  int rc = SQLITE_OK;             /* Return code */









  /* Assuming the wal-index file was successfully mapped, find the hash 
  ** table and section of of the page number array that pertain to frame 
  ** iFrame of the WAL. Then populate the page number array and the hash 
  ** table entry.
  */
  if( rc==SQLITE_OK ){
................................................................................
    volatile HASHTABLE_DATATYPE *aHash;  /* Hash table */
    int idx;                             /* Value to write to hash-table slot */
    TESTONLY( int nCollide = 0;          /* Number of hash collisions */ )

    walHashFind(pWal, iFrame, &aHash, &aPgno, &iZero);
    idx = iFrame - iZero;
    if( idx==1 ){
      int nByte = (u8 *)&aHash[HASHTABLE_NSLOT] - (u8 *)&aPgno[1+iZero];
      memset((void*)&aPgno[1+iZero], 0, nByte);
    }
    assert( idx <= HASHTABLE_NSLOT/2 + 1 );

    if( aPgno[iFrame] ){
      /* If the entry in aPgno[] is already set, then the previous writer
      ** must have exited unexpectedly in the middle of a transaction (after
      ** writing one or more dirty pages to the WAL to free up memory). 
................................................................................
      }
    }

    sqlite3_free(aFrame);
  }

finished:



  if( rc==SQLITE_OK ){
    volatile WalCkptInfo *pInfo;
    int i;
    pWal->hdr.aFrameCksum[0] = aFrameCksum[0];
    pWal->hdr.aFrameCksum[1] = aFrameCksum[1];
    walIndexWriteHdr(pWal);

................................................................................
  if( !pRet ){
    return SQLITE_NOMEM;
  }

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

  pRet->readLock = -1;
  sqlite3_randomness(8, &pRet->hdr.aSalt);
  pRet->zWalName = zWal = pVfs->szOsFile + (char*)pRet->pWalFd;
  sqlite3_snprintf(nWal, zWal, "%s-wal", zDbName);
  rc = sqlite3OsShmOpen(pDbFd);

  /* Open file handle on the write-ahead log file. */
................................................................................
  WalIterator *p,               /* Iterator */
  u32 *piPage,                  /* OUT: The page number of the next page */
  u32 *piFrame                  /* OUT: Wal frame index of next page */
){
  u32 iMin;                     /* Result pgno must be greater than iMin */
  u32 iRet = 0xFFFFFFFF;        /* 0xffffffff is never a valid page number */
  int i;                        /* For looping through segments */


  iMin = p->iPrior;
  assert( iMin<0xffffffff );
  for(i=p->nSegment-1; i>=0; i--){
    struct WalSegment *pSegment = &p->aSegment[i];
    while( pSegment->iNext<pSegment->nEntry ){
      u32 iPg = pSegment->aPgno[pSegment->aIndex[pSegment->iNext]];
      if( iPg>iMin ){
        if( iPg<iRet ){
          iRet = iPg;
          *piFrame = pSegment->iZero + pSegment->aIndex[pSegment->iNext];
        }
        break;
      }
      pSegment->iNext++;
    }

  }

  *piPage = p->iPrior = iRet;
  return (iRet==0xFFFFFFFF);
}


static void walMergesort(
  u32 *aContent,                  /* Pages in wal */
  HASHTABLE_DATATYPE *aBuffer,    /* Buffer of at least *pnList items to use */
  HASHTABLE_DATATYPE *aList,      /* IN/OUT: List to sort */
  int *pnList                     /* IN/OUT: Number of elements in aList[] */
){
  int nList = *pnList;
  if( nList>1 ){
    int nLeft = nList / 2;        /* Elements in left list */
    int nRight = nList - nLeft;   /* Elements in right list */


    int iLeft = 0;                /* Current index in aLeft */
    int iRight = 0;               /* Current index in aright */
    int iOut = 0;                 /* Current index in output buffer */
    HASHTABLE_DATATYPE *aLeft = aList;           /* Left list */
    HASHTABLE_DATATYPE *aRight = &aList[nLeft];  /* Right list */

    /* TODO: Change to non-recursive version. */
    walMergesort(aContent, aBuffer, aLeft, &nLeft);
    walMergesort(aContent, aBuffer, aRight, &nRight);

    while( iRight<nRight || iLeft<nLeft ){
      HASHTABLE_DATATYPE logpage;
      Pgno dbpage;

      if( (iLeft<nLeft) 
       && (iRight>=nRight || aContent[aLeft[iLeft]]<aContent[aRight[iRight]])
      ){
        logpage = aLeft[iLeft++];
      }else{
................................................................................
**
** The calling routine should invoke walIteratorFree() to destroy the
** WalIterator object when it has finished with it.  The caller must
** also unmap the wal-index.  But the wal-index must not be unmapped
** prior to the WalIterator object being destroyed.
*/
static int walIteratorInit(Wal *pWal, WalIterator **pp){

  WalIterator *p;       /* Return value */
  int nSegment;         /* Number of segments to merge */
  u32 iLast;            /* Last frame in log */
  int nByte;            /* Number of bytes to allocate */
  int i;                /* Iterator variable */

  HASHTABLE_DATATYPE *aTmp;       /* Temp space used by merge-sort */
  HASHTABLE_DATATYPE *aSpace;     /* Space at the end of the allocation */




  /* This routine only runs while holding SQLITE_SHM_CHECKPOINT.  No other
  ** thread is able to write to shared memory while this routine is
  ** running (or, indeed, while the WalIterator object exists).  Hence,
  ** we can cast off the volatile qualification from shared memory
  */
  assert( pWal->ckptLock );
  iLast = pWal->hdr.mxFrame;

  /* Allocate space for the WalIterator object */
  nSegment = walFramePage(iLast) + 1;
  nByte = sizeof(WalIterator) 

        + nSegment*(sizeof(struct WalSegment))
        + (nSegment+1)*(HASHTABLE_NPAGE * sizeof(HASHTABLE_DATATYPE));
  p = (WalIterator *)sqlite3_malloc(nByte);
  if( !p ){
    return SQLITE_NOMEM;
  }
  memset(p, 0, nByte);

  /* Allocate space for the WalIterator object */



  p->nSegment = nSegment;
  aSpace = (HASHTABLE_DATATYPE *)&p->aSegment[nSegment];
  aTmp = &aSpace[HASHTABLE_NPAGE*nSegment];
  for(i=0; i<nSegment; i++){
    volatile HASHTABLE_DATATYPE *pDummy;
    int j;
    u32 iZero;
    int nEntry;
    volatile u32 *aPgno;

    walHashGet(pWal, i, &pDummy, &aPgno, &iZero);
    if( i==(nSegment-1) ){


      nEntry = iLast - iZero;
    }else if( i==0 ){
      nEntry = HASHTABLE_NPAGE_ONE;
    }else{
      nEntry = HASHTABLE_NPAGE;
    }
    iZero++;
    aPgno += iZero;

    for(j=0; j<nEntry; j++){
      aSpace[j] = j;
    }
    walMergesort((u32 *)aPgno, aTmp, aSpace, &nEntry);
    p->aSegment[i].iZero = iZero;
    p->aSegment[i].nEntry = nEntry;
    p->aSegment[i].aIndex = aSpace;
    p->aSegment[i].aPgno = (u32 *)aPgno;

    aSpace += HASHTABLE_NPAGE;

  }
  assert( aSpace==aTmp );

  /* Return the fully initialized WalIterator object */
  *pp = p;
  return SQLITE_OK ;
}

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

  /* Compute in mxSafeFrame the index of the last frame of the WAL that is
  ** safe to write into the database.  Frames beyond mxSafeFrame might
  ** overwrite database pages that are in use by active readers and thus
  ** cannot be backfilled from the WAL.
  */
  mxSafeFrame = pWal->hdr.mxFrame;
  walIndexPage(pWal, 0, (volatile u32 **)&pHdr);
  pInfo = walCkptInfo(pWal);
  assert( pInfo==walCkptInfo(pWal) );
  for(i=1; i<WAL_NREADER; i++){
    u32 y = pInfo->aReadMark[i];
    if( mxSafeFrame>=y ){
      assert( y<=pWal->hdr.mxFrame );
      rc = walLockExclusive(pWal, WAL_READ_LOCK(i), 1);
      if( rc==SQLITE_OK ){
................................................................................
    /* Sync the WAL to disk */
    if( sync_flags ){
      rc = sqlite3OsSync(pWal->pWalFd, sync_flags);
    }

    /* Iterate through the contents of the WAL, copying data to the db file. */
    while( rc==SQLITE_OK && 0==walIteratorNext(pIter, &iDbpage, &iFrame) ){
      assert( walFramePgno(pWal, iFrame)==iDbpage );
      if( iFrame<=nBackfill || iFrame>mxSafeFrame ) continue;
      rc = sqlite3OsRead(pWal->pWalFd, zBuf, szPage, 
          walFrameOffset(iFrame, szPage) + WAL_FRAME_HDRSIZE
      );
      if( rc!=SQLITE_OK ) break;
      rc = sqlite3OsWrite(pWal->pDbFd, zBuf, szPage, (iDbpage-1)*szPage);
      if( rc!=SQLITE_OK ) break;
................................................................................
    rc = sqlite3OsLock(pWal->pDbFd, SQLITE_LOCK_EXCLUSIVE);
    if( rc==SQLITE_OK ){
      pWal->exclusiveMode = 1;
      rc = sqlite3WalCheckpoint(pWal, sync_flags, nBuf, zBuf);
      if( rc==SQLITE_OK ){
        isDelete = 1;
      }

    }

    walIndexClose(pWal, isDelete);
    sqlite3OsClose(pWal->pWalFd);
    if( isDelete ){
      sqlite3OsDelete(pWal->pVfs, pWal->zWalName, 0);
    }
    WALTRACE(("WAL%p: closed\n", pWal));
    sqlite3_free(pWal->apWiData);
    sqlite3_free(pWal);
  }
  return rc;
}

/*
** Try to read the wal-index header.  Return 0 on success and 1 if
................................................................................
** If the checksum cannot be verified return non-zero. If the header
** is read successfully and the checksum verified, return zero.
*/
int walIndexTryHdr(Wal *pWal, int *pChanged){
  u32 aCksum[2];               /* Checksum on the header content */
  WalIndexHdr h1, h2;          /* Two copies of the header content */
  WalIndexHdr *aHdr;           /* Header in shared memory */
  volatile u32 *page1 = 0;


  walIndexPage(pWal, 0, &page1);
  if( !page1 ){
    /* The wal-index is not large enough to hold the header, then assume
    ** header is invalid. */
    return 1;
  }


  /* Read the header. This might happen currently with a write to the
  ** same area of shared memory on a different CPU in a SMP,
  ** meaning it is possible that an inconsistent snapshot is read
  ** from the file. If this happens, return non-zero.
  **
  ** There are two copies of the header at the beginning of the wal-index.
  ** When reading, read [0] first then [1].  Writes are in the reverse order.
  ** Memory barriers are used to prevent the compiler or the hardware from
  ** reordering the reads and writes.
  */
  aHdr = (WalIndexHdr*)page1;
  memcpy(&h1, &aHdr[0], sizeof(h1));
  sqlite3OsShmBarrier(pWal->pDbFd);
  memcpy(&h2, &aHdr[1], sizeof(h2));

  if( memcmp(&h1, &h2, sizeof(h1))!=0 ){
    return 1;   /* Dirty read */
  }  
................................................................................
**
** If the wal-index header is successfully read, return SQLITE_OK. 
** Otherwise an SQLite error code.
*/
static int walIndexReadHdr(Wal *pWal, int *pChanged){
  int rc;                         /* Return code */
  int badHdr;                     /* True if a header read failed */
  volatile u32 *dummy;

  assert( pChanged );

  rc = walIndexPage(pWal, 0, &dummy);
  if( rc!=SQLITE_OK ){
    return rc;
  }

  /* Try once to read the header straight out.  This works most of the
  ** time.
  */
................................................................................
        *pChanged = 1;
      }
      walUnlockExclusive(pWal, WAL_WRITE_LOCK, 1);
      pWal->writeLock = 0;
    }
  }









  return rc;
}

/*
** This is the value that walTryBeginRead returns when it needs to
** be retried.
*/
................................................................................
*/
static int walTryBeginRead(Wal *pWal, int *pChanged, int useWal, int cnt){
  volatile WalIndexHdr *pHdr;     /* Header of the wal-index */
  volatile WalCkptInfo *pInfo;    /* Checkpoint information in wal-index */
  u32 mxReadMark;                 /* Largest aReadMark[] value */
  int mxI;                        /* Index of largest aReadMark[] value */
  int i;                          /* Loop counter */
  int rc = SQLITE_OK;             /* Return code  */

  assert( pWal->readLock<0 );     /* Not currently locked */

  /* Take steps to avoid spinning forever if there is a protocol error. */
  if( cnt>5 ){
    if( cnt>100 ) return SQLITE_PROTOCOL;
    sqlite3OsSleep(pWal->pVfs, 1);
................................................................................
      if( rc==SQLITE_OK ){
        walUnlockShared(pWal, WAL_RECOVER_LOCK);
        rc = WAL_RETRY;
      }else if( rc==SQLITE_BUSY ){
        rc = SQLITE_BUSY_RECOVERY;
      }
    }


  }
  if( rc!=SQLITE_OK ){
    return rc;
  }

  walIndexPage(pWal, 0, (volatile u32 **)&pHdr);
  pInfo = walCkptInfo(pWal);
  assert( pInfo==(volatile WalCkptInfo *)&pHdr[2] );
  if( !useWal && pInfo->nBackfill==pWal->hdr.mxFrame ){
    /* The WAL has been completely backfilled (or it is empty).
    ** and can be safely ignored.
    */
    rc = walLockShared(pWal, WAL_READ_LOCK(0));
    sqlite3OsShmBarrier(pWal->pDbFd);
    if( rc==SQLITE_OK ){
................................................................................
int sqlite3WalBeginReadTransaction(Wal *pWal, int *pChanged){
  int rc;                         /* Return code */
  int cnt = 0;                    /* Number of TryBeginRead attempts */

  do{
    rc = walTryBeginRead(pWal, pChanged, 0, ++cnt);
  }while( rc==WAL_RETRY );

  return rc;
}

/*
** Finish with a read transaction.  All this does is release the
** read-lock.
*/
................................................................................
int sqlite3WalRead(
  Wal *pWal,                      /* WAL handle */
  Pgno pgno,                      /* Database page number to read data for */
  int *pInWal,                    /* OUT: True if data is read from WAL */
  int nOut,                       /* Size of buffer pOut in bytes */
  u8 *pOut                        /* Buffer to write page data to */
){

  u32 iRead = 0;                  /* If !=0, WAL frame to return data from */
  u32 iLast = pWal->hdr.mxFrame;  /* Last page in WAL for this reader */
  int iHash;                      /* Used to loop through N hash tables */

  /* This routine is only be called from within a read transaction. */
  assert( pWal->readLock>=0 || pWal->lockError );

................................................................................
  ** return early, as if the WAL were empty.
  */
  if( iLast==0 || pWal->readLock==0 ){
    *pInWal = 0;
    return SQLITE_OK;
  }







  /* Search the hash table or tables for an entry matching page number
  ** pgno. Each iteration of the following for() loop searches one
  ** hash table (each hash table indexes up to HASHTABLE_NPAGE frames).
  **
  ** This code may run concurrently to the code in walIndexAppend()
  ** that adds entries to the wal-index (and possibly to this hash 
  ** table). This means the value just read from the hash 
................................................................................
  **   (aPgno[iFrame]==pgno): 
  **     This condition filters out normal hash-table collisions.
  **
  **   (iFrame<=iLast): 
  **     This condition filters out entries that were added to the hash
  **     table after the current read-transaction had started.
  */
  for(iHash=walFramePage(iLast); iHash>=0 && iRead==0; iHash--){
    volatile HASHTABLE_DATATYPE *aHash;  /* Pointer to hash table */
    volatile u32 *aPgno;                 /* Pointer to array of page numbers */
    u32 iZero;                    /* Frame number corresponding to aPgno[0] */
    int iKey;                     /* Hash slot index */


    walHashGet(pWal, iHash, &aHash, &aPgno, &iZero);


    for(iKey=walHash(pgno); aHash[iKey]; iKey=walNextHash(iKey)){
      u32 iFrame = aHash[iKey] + iZero;
      if( iFrame<=iLast && aPgno[iFrame]==pgno ){
        assert( iFrame>iRead );
        iRead = iFrame;
      }
    }
  }


#ifdef SQLITE_ENABLE_EXPENSIVE_ASSERT
  /* If expensive assert() statements are available, do a linear search
  ** of the wal-index file content. Make sure the results agree with the
  ** result obtained using the hash indexes above.  */
  {
    u32 iRead2 = 0;
    u32 iTest;
    for(iTest=iLast; iTest>0; iTest--){
      if( walFramePgno(pWal, iTest)==pgno ){
        iRead2 = iTest;
        break;
      }
    }
    assert( iRead==iRead2 );
  }
#endif

  /* If iRead is non-zero, then it is the log frame number that contains the
  ** required page. Read and return data from the log file.
  */

  if( iRead ){
    i64 iOffset = walFrameOffset(iRead, pWal->hdr.szPage) + WAL_FRAME_HDRSIZE;
    *pInWal = 1;
    return sqlite3OsRead(pWal->pWalFd, pOut, nOut, iOffset);
  }

  *pInWal = 0;
................................................................................
** thread to write as doing so would cause a fork.  So this routine
** returns SQLITE_BUSY in that case and no write transaction is started.
**
** There can only be a single writer active at a time.
*/
int sqlite3WalBeginWriteTransaction(Wal *pWal){
  int rc;
  volatile u32 *page1;

  /* Cannot start a write transaction without first holding a read
  ** transaction. */
  assert( pWal->readLock>=0 );

  /* Only one writer allowed at a time.  Get the write lock.  Return
  ** SQLITE_BUSY if unable.
................................................................................
  }
  pWal->writeLock = 1;

  /* If another connection has written to the database file since the
  ** time the read transaction on this connection was started, then
  ** the write is disallowed.
  */
  walIndexPage(pWal, 0, &page1);





  if( memcmp(&pWal->hdr, (void*)page1, sizeof(WalIndexHdr))!=0 ){
    walUnlockExclusive(pWal, WAL_WRITE_LOCK, 1);
    pWal->writeLock = 0;
    rc = SQLITE_BUSY;
  }


  return rc;
}

/*
** End a write transaction.  The commit has already been done.  This
** routine merely releases the lock.
*/
................................................................................
int sqlite3WalUndo(Wal *pWal, int (*xUndo)(void *, Pgno), void *pUndoCtx){
  int rc = SQLITE_OK;
  if( pWal->writeLock ){
    int unused;
    Pgno iMax = pWal->hdr.mxFrame;
    Pgno iFrame;
  

    rc = walIndexReadHdr(pWal, &unused);



    if( rc==SQLITE_OK ){
      for(iFrame=pWal->hdr.mxFrame+1; 
          ALWAYS(rc==SQLITE_OK) && iFrame<=iMax; 
          iFrame++
      ){
        /* This call cannot fail. Unless the page for which the page number
        ** is passed as the second argument is (a) in the cache and 
................................................................................
        **
        ** If the upper layer is doing a rollback, it is guaranteed that there
        ** are no outstanding references to any page other than page 1. And
        ** page 1 is never written to the log until the transaction is
        ** committed. As a result, the call to xUndo may not fail.
        */
        assert( pWal->writeLock );
        assert( walFramePgno(pWal, iFrame)!=1 );
        rc = xUndo(pUndoCtx, walFramePgno(pWal, iFrame));
      }
      walCleanupHash(pWal);
    }

  }
  return rc;
}

/* 
** Argument aWalData must point to an array of WAL_SAVEPOINT_NDATA u32 
** values. This function populates the array with values required to 
................................................................................
    ** to the start of the log. Update the savepoint values to match.
    */
    aWalData[0] = 0;
    aWalData[3] = pWal->nCkpt;
  }

  if( aWalData[0]<pWal->hdr.mxFrame ){

    pWal->hdr.mxFrame = aWalData[0];
    pWal->hdr.aFrameCksum[0] = aWalData[1];
    pWal->hdr.aFrameCksum[1] = aWalData[2];
    if( rc==SQLITE_OK ){
      walCleanupHash(pWal);
    }
  }


  return rc;
}

/*
** This function is called just before writing a set of frames to the log
** file (see sqlite3WalFrames()). It checks to see if, instead of appending
** to the current log file, it is possible to overwrite the start of the
................................................................................
** or not pWal->hdr.mxFrame is modified). An SQLite error code is returned
** if some error 
*/
static int walRestartLog(Wal *pWal){
  int rc = SQLITE_OK;
  int cnt;

  if( pWal->readLock==0 ){


    volatile WalCkptInfo *pInfo = walCkptInfo(pWal);
    assert( pInfo->nBackfill==pWal->hdr.mxFrame );
    if( pInfo->nBackfill>0 ){
      rc = walLockExclusive(pWal, WAL_READ_LOCK(1), WAL_NREADER-1);
      if( rc==SQLITE_OK ){
        /* If all readers are using WAL_READ_LOCK(0) (in other words if no
        ** readers are currently using the WAL), then the transactions
................................................................................
    walUnlockShared(pWal, WAL_READ_LOCK(0));
    pWal->readLock = -1;
    cnt = 0;
    do{
      int notUsed;
      rc = walTryBeginRead(pWal, &notUsed, 1, ++cnt);
    }while( rc==WAL_RETRY );





  }
  return rc;
}

/* 
** Write a set of frames to the log. The caller must hold the write-lock
** on the log file (obtained using sqlite3WalBeginWriteTransaction()).
................................................................................
  u8 aFrame[WAL_FRAME_HDRSIZE];   /* Buffer to assemble frame-header in */
  PgHdr *p;                       /* Iterator to run through pList with. */
  PgHdr *pLast = 0;               /* Last frame in list */
  int nLast = 0;                  /* Number of extra copies of last page */

  assert( pList );
  assert( pWal->writeLock );


#if defined(SQLITE_TEST) && defined(SQLITE_DEBUG)
  { int cnt; for(cnt=0, p=pList; p; p=p->pDirty, cnt++){}
    WALTRACE(("WAL%p: frame write begin. %d frames. mxFrame=%d. %s\n",
              pWal, cnt, pWal->hdr.mxFrame, isCommit ? "Commit" : "Spill"));
  }
#endif

  /* See if it is possible to write these frames into the start of the
  ** log file, instead of appending to it at pWal->hdr.mxFrame.
  */
  if( SQLITE_OK!=(rc = walRestartLog(pWal)) ){

    return rc;
  }


  /* If this is the first frame written into the log, write the WAL
  ** header to the start of the WAL file. See comments at the top of
  ** this source file for a description of the WAL header format.
  */
  iFrame = pWal->hdr.mxFrame;
  if( iFrame==0 ){
................................................................................
      }
      nLast++;
      iOffset += szPage;
    }

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


  /* Append data to the wal-index. It is not necessary to lock the 
  ** wal-index to do this as the SQLITE_SHM_WRITE lock held on the wal-index
  ** guarantees that there are no other writers, and no data that may
  ** be in use by existing readers is being overwritten.
  */
  iFrame = pWal->hdr.mxFrame;
................................................................................
    /* If this is a commit, update the wal-index header too. */
    if( isCommit ){
      walIndexWriteHdr(pWal);
      pWal->iCallback = iFrame;
    }
  }


  WALTRACE(("WAL%p: frame write %s\n", pWal, rc ? "failed" : "ok"));
  return rc;
}

/* 
** This routine is called to implement sqlite3_wal_checkpoint() and
** related interfaces.
................................................................................
  int sync_flags,                 /* Flags to sync db file with (or 0) */
  int nBuf,                       /* Size of temporary buffer */
  u8 *zBuf                        /* Temporary buffer to use */
){
  int rc;                         /* Return code */
  int isChanged = 0;              /* True if a new wal-index header is loaded */


  assert( pWal->ckptLock==0 );

  WALTRACE(("WAL%p: checkpoint begins\n", pWal));
  rc = walLockExclusive(pWal, WAL_CKPT_LOCK, 1);
  if( rc ){
    /* Usually this is SQLITE_BUSY meaning that another thread or process
    ** is already running a checkpoint, or maybe a recovery.  But it might
................................................................................
    ** next time the pager opens a snapshot on this database it knows that
    ** the cache needs to be reset.
    */
    memset(&pWal->hdr, 0, sizeof(WalIndexHdr));
  }

  /* Release the locks. */

  walUnlockExclusive(pWal, WAL_CKPT_LOCK, 1);
  pWal->ckptLock = 0;
  WALTRACE(("WAL%p: checkpoint %s\n", pWal, rc ? "failed" : "ok"));
  return rc;
}

/* Return the value to pass to a sqlite3_wal_hook callback, the

Changes to test/permutations.test.

9
10
11
12
13
14
15

16
17
18
19
20
21
22
#
#***********************************************************************
#
# $Id: permutations.test,v 1.51 2009/07/01 18:09:02 danielk1977 Exp $

set testdir [file dirname $argv0]
source $testdir/tester.tcl


# Argument processing.
#
#puts "PERM-DEBUG: argv=$argv"
namespace eval ::perm {
  variable testmode [lindex $::argv 0]
  variable testfile [lindex $::argv 1]







>







9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#
#***********************************************************************
#
# $Id: permutations.test,v 1.51 2009/07/01 18:09:02 danielk1977 Exp $

set testdir [file dirname $argv0]
source $testdir/tester.tcl
db close

# Argument processing.
#
#puts "PERM-DEBUG: argv=$argv"
namespace eval ::perm {
  variable testmode [lindex $::argv 0]
  variable testfile [lindex $::argv 1]

Changes to test/wal2.test.

71
72
73
74
75
76
77


78


79
80

81
82
83
84
85
86
87
...
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139



140
141
142
143
144
145
146
147
...
170
171
172
173
174
175
176

177
178

179
180
181
182
183
184
185
...
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
263
264
265
266
267
#      of the the integer fields (so that the reader ends up with a corrupted
#      header).
#
#   3. Check that the reader recovers the wal-index and reads the correct
#      database content.
#
do_test wal2-1.0 {


  proc tvfs_cb {method args} { return SQLITE_OK }


  testvfs tvfs
  tvfs script tvfs_cb


  sqlite3 db  test.db -vfs tvfs
  sqlite3 db2 test.db -vfs tvfs

  execsql {
    PRAGMA journal_mode = WAL;
    CREATE TABLE t1(a);
................................................................................
        10   13   {13 91}   8             {$RECOVER $READ}
        11   14   {14 105}  9             {$RECOVER $READ}
        12   15   {15 120}  -1            {$READ}
" {

  do_test wal2-1.$tn.1 {
    execsql { INSERT INTO t1 VALUES($iInsert) }

    set ::locks [list]
    set ::cb_done 0

    proc tvfs_cb {method args} {
      if {$::cb_done == 0 && $method == "xShmGet"} {
        set ::cb_done 1
        if {$::wal_index_hdr_mod >= 0} {
          incr_tvfs_hdr [lindex $args 0] $::wal_index_hdr_mod 1
        }
      }
      if {$method == "xShmLock"} { lappend ::locks [lindex $args 2] }
      return SQLITE_OK
    }




    execsql { SELECT count(a), sum(a) FROM t1 } db2
  } $res

  do_test wal2-1.$tn.2 {
    set ::locks
  } $wal_locks
}
................................................................................
  {4 1 lock exclusive} {4 1 unlock exclusive} \
  {4 1 lock shared}    {4 1 unlock shared}    \
]
do_test wal2-2.0 {

  testvfs tvfs
  tvfs script tvfs_cb

  proc tvfs_cb {method args} {
    if {$method == "xShmOpen"} { set ::shm_file [lindex $args 0] }

    return SQLITE_OK
  }

  sqlite3 db  test.db -vfs tvfs
  sqlite3 db2 test.db -vfs tvfs

  execsql {
................................................................................
         4    7   {6 21}   {7 28}    2
         5    8   {7 28}   {8 36}    3
         6    9   {8 36}   {9 45}    4
         7   10   {9 45}   {10 55}   5
         8   11   {10 55}  {11 66}   6
         9   12   {11 66}  {12 78}   7
} {


  do_test wal2-2.$tn.1 {
    set oldhdr [set_tvfs_hdr $::shm_file]
    execsql { INSERT INTO t1 VALUES($iInsert) }
    execsql { SELECT count(a), sum(a) FROM t1 }
  } $res1

  do_test wal2-2.$tn.2 {
    set ::locks [list]
    set ::cb_done 0
    proc tvfs_cb {method args} {
      if {$::cb_done == 0 && $method == "xShmGet"} {
        set ::cb_done 1
        if {$::wal_index_hdr_mod >= 0} {
          incr_tvfs_hdr $::shm_file $::wal_index_hdr_mod 1
        }
      }
      if {$method == "xShmLock"} {
        set lock [lindex $args 2]
        lappend ::locks $lock
        if {$lock == $::WRITER} {
          set_tvfs_hdr $::shm_file $::oldhdr
        }
      }
      return SQLITE_OK
    }




    execsql { SELECT count(a), sum(a) FROM t1 } db2
  } $res0

  do_test wal2-2.$tn.3 {
    set ::locks
  } $LOCKS

  do_test wal2-2.$tn.4 {
    set ::locks [list]
    set ::cb_done 0
    proc tvfs_cb {method args} {
      if {$::cb_done == 0 && $method == "xShmGet"} {
        set ::cb_done 1
        if {$::wal_index_hdr_mod >= 0} {
          incr_tvfs_hdr $::shm_file $::wal_index_hdr_mod 1
        }
      }
      if {$method == "xShmLock"} {
        set lock [lindex $args 2]
        lappend ::locks $lock
      }
      return SQLITE_OK
    }




    execsql { SELECT count(a), sum(a) FROM t1 } db2
  } $res1
}
db close
db2 close
tvfs delete
file delete -force test.db test.db-wal test.db-journal







>
>
|
>
>


>







 







<

<
<

<
<
<
<
<
<
|


>
>
>
|







 







>

<
>







 







>
>

|






<

<
<
<
<
<
<
<
|
|
|
|
<




>
>
>









<

<
<
<
<
<
<
<
|
|
<



>
>
>







71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
...
124
125
126
127
128
129
130

131


132






133
134
135
136
137
138
139
140
141
142
143
144
145
146
...
169
170
171
172
173
174
175
176
177

178
179
180
181
182
183
184
185
...
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
#      of the the integer fields (so that the reader ends up with a corrupted
#      header).
#
#   3. Check that the reader recovers the wal-index and reads the correct
#      database content.
#
do_test wal2-1.0 {
  proc tvfs_cb {method filename args} { 
    set ::filename $filename
    return SQLITE_OK 
  }

  testvfs tvfs
  tvfs script tvfs_cb
  tvfs filter xShmOpen

  sqlite3 db  test.db -vfs tvfs
  sqlite3 db2 test.db -vfs tvfs

  execsql {
    PRAGMA journal_mode = WAL;
    CREATE TABLE t1(a);
................................................................................
        10   13   {13 91}   8             {$RECOVER $READ}
        11   14   {14 105}  9             {$RECOVER $READ}
        12   15   {15 120}  -1            {$READ}
" {

  do_test wal2-1.$tn.1 {
    execsql { INSERT INTO t1 VALUES($iInsert) }

    set ::locks [list]


    proc tvfs_cb {method args} {






      lappend ::locks [lindex $args 2]
      return SQLITE_OK
    }
    tvfs filter xShmLock
    if {$::wal_index_hdr_mod >= 0} {
      incr_tvfs_hdr $::filename $::wal_index_hdr_mod 1
    }
    execsql { SELECT count(a), sum(a) FROM t1 } db2
  } $res

  do_test wal2-1.$tn.2 {
    set ::locks
  } $wal_locks
}
................................................................................
  {4 1 lock exclusive} {4 1 unlock exclusive} \
  {4 1 lock shared}    {4 1 unlock shared}    \
]
do_test wal2-2.0 {

  testvfs tvfs
  tvfs script tvfs_cb
  tvfs filter xShmOpen
  proc tvfs_cb {method args} {

    set ::filename [lindex $args 0]
    return SQLITE_OK
  }

  sqlite3 db  test.db -vfs tvfs
  sqlite3 db2 test.db -vfs tvfs

  execsql {
................................................................................
         4    7   {6 21}   {7 28}    2
         5    8   {7 28}   {8 36}    3
         6    9   {8 36}   {9 45}    4
         7   10   {9 45}   {10 55}   5
         8   11   {10 55}  {11 66}   6
         9   12   {11 66}  {12 78}   7
} {
  tvfs filter xShmLock

  do_test wal2-2.$tn.1 {
    set oldhdr [set_tvfs_hdr $::filename]
    execsql { INSERT INTO t1 VALUES($iInsert) }
    execsql { SELECT count(a), sum(a) FROM t1 }
  } $res1

  do_test wal2-2.$tn.2 {
    set ::locks [list]

    proc tvfs_cb {method args} {







      set lock [lindex $args 2]
      lappend ::locks $lock
      if {$lock == $::WRITER} {
        set_tvfs_hdr $::filename $::oldhdr

      }
      return SQLITE_OK
    }

    if {$::wal_index_hdr_mod >= 0} {
      incr_tvfs_hdr $::filename $::wal_index_hdr_mod 1
    }
    execsql { SELECT count(a), sum(a) FROM t1 } db2
  } $res0

  do_test wal2-2.$tn.3 {
    set ::locks
  } $LOCKS

  do_test wal2-2.$tn.4 {
    set ::locks [list]

    proc tvfs_cb {method args} {







      set lock [lindex $args 2]
      lappend ::locks $lock

      return SQLITE_OK
    }

    if {$::wal_index_hdr_mod >= 0} {
      incr_tvfs_hdr $::filename $::wal_index_hdr_mod 1
    }
    execsql { SELECT count(a), sum(a) FROM t1 } db2
  } $res1
}
db close
db2 close
tvfs delete
file delete -force test.db test.db-wal test.db-journal

Changes to test/wal3.test.

349
350
351
352
353
354
355
356
357
358
359
360
361
362
363

testvfs T -default 1
T script method_callback

proc method_callback {method args} {
  if {$method == "xShmBarrier"} {
    incr ::barrier_count
    if {$::barrier_count == 1} {
      # This code is executed within the xShmBarrier() callback invoked
      # by the client running recovery as part of writing the recovered
      # wal-index header. If a second client attempts to access the 
      # database now, it reads a corrupt (partially written) wal-index
      # header. But it cannot even get that far, as the first client
      # is still holding all the locks (recovery takes an exclusive lock
      # on *all* db locks, preventing access by any other client).







|







349
350
351
352
353
354
355
356
357
358
359
360
361
362
363

testvfs T -default 1
T script method_callback

proc method_callback {method args} {
  if {$method == "xShmBarrier"} {
    incr ::barrier_count
    if {$::barrier_count == 2} {
      # This code is executed within the xShmBarrier() callback invoked
      # by the client running recovery as part of writing the recovered
      # wal-index header. If a second client attempts to access the 
      # database now, it reads a corrupt (partially written) wal-index
      # header. But it cannot even get that far, as the first client
      # is still holding all the locks (recovery takes an exclusive lock
      # on *all* db locks, preventing access by any other client).