/ Check-in [538a365b]
Login

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

Overview
Comment:Slightly smaller and faster code by encapsulating wal-index hash table location information in a separate WalHashLoc object rather than passing around the various elements as separate variables.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA3-256: 538a365b7a32ab7fa84f59d7556242cfb59b76d287b6417eb3a823197a354e8e
User & Date: drh 2018-06-09 16:49:00
Context
2018-06-09
20:52
Fix a typo in the amalgamation autoconf file. check-in: de0857f3 user: drh tags: trunk
18:09
Merge recent trunk changes with this branch. check-in: c71f2359 user: dan tags: exp-window-functions
16:49
Slightly smaller and faster code by encapsulating wal-index hash table location information in a separate WalHashLoc object rather than passing around the various elements as separate variables. check-in: 538a365b user: drh tags: trunk
14:13
Improved comments an presentation for the recent IN operator decision improvement. check-in: 31e480f6 user: drh tags: trunk
Changes
Hide Diffs Side-by-Side Diffs Ignore Whitespace Patch

Changes to src/wal.c.

   875    875     assert( iPage>0 );
   876    876     assert( (HASHTABLE_NSLOT & (HASHTABLE_NSLOT-1))==0 );
   877    877     return (iPage*HASHTABLE_HASH_1) & (HASHTABLE_NSLOT-1);
   878    878   }
   879    879   static int walNextHash(int iPriorHash){
   880    880     return (iPriorHash+1)&(HASHTABLE_NSLOT-1);
   881    881   }
          882  +
          883  +/*
          884  +** An instance of the WalHashLoc object is used to describe the location
          885  +** of a page hash table in the wal-index.  This becomes the return value
          886  +** from walHashGet().
          887  +*/
          888  +typedef struct WalHashLoc WalHashLoc;
          889  +struct WalHashLoc {
          890  +  volatile ht_slot *aHash;  /* Start of the wal-index hash table */
          891  +  volatile u32 *aPgno;      /* aPgno[1] is the page of first frame indexed */
          892  +  u32 iZero;                /* One less than the frame number of first indexed*/
          893  +};
   882    894   
   883    895   /* 
   884    896   ** Return pointers to the hash table and page number array stored on
   885    897   ** page iHash of the wal-index. The wal-index is broken into 32KB pages
   886    898   ** numbered starting from 0.
   887    899   **
   888         -** Set output variable *paHash to point to the start of the hash table
   889         -** in the wal-index file. Set *piZero to one less than the frame 
          900  +** Set output variable pLoc->aHash to point to the start of the hash table
          901  +** in the wal-index file. Set pLoc->iZero to one less than the frame 
   890    902   ** number of the first frame indexed by this hash table. If a
   891    903   ** slot in the hash table is set to N, it refers to frame number 
   892         -** (*piZero+N) in the log.
          904  +** (pLoc->iZero+N) in the log.
   893    905   **
   894         -** Finally, set *paPgno so that *paPgno[1] is the page number of the
   895         -** first frame indexed by the hash table, frame (*piZero+1).
          906  +** Finally, set pLoc->aPgno so that pLoc->aPgno[1] is the page number of the
          907  +** first frame indexed by the hash table, frame (pLoc->iZero+1).
   896    908   */
   897    909   static int walHashGet(
   898    910     Wal *pWal,                      /* WAL handle */
   899    911     int iHash,                      /* Find the iHash'th table */
   900         -  volatile ht_slot **paHash,      /* OUT: Pointer to hash index */
   901         -  volatile u32 **paPgno,          /* OUT: Pointer to page number array */
   902         -  u32 *piZero                     /* OUT: Frame associated with *paPgno[0] */
          912  +  WalHashLoc *pLoc                /* OUT: Hash table location */
   903    913   ){
   904    914     int rc;                         /* Return code */
   905         -  volatile u32 *aPgno;
   906    915   
   907         -  rc = walIndexPage(pWal, iHash, &aPgno);
          916  +  rc = walIndexPage(pWal, iHash, &pLoc->aPgno);
   908    917     assert( rc==SQLITE_OK || iHash>0 );
   909    918   
   910    919     if( rc==SQLITE_OK ){
   911         -    u32 iZero;
   912         -    volatile ht_slot *aHash;
   913         -
   914         -    aHash = (volatile ht_slot *)&aPgno[HASHTABLE_NPAGE];
          920  +    pLoc->aHash = (volatile ht_slot *)&pLoc->aPgno[HASHTABLE_NPAGE];
   915    921       if( iHash==0 ){
   916         -      aPgno = &aPgno[WALINDEX_HDR_SIZE/sizeof(u32)];
   917         -      iZero = 0;
          922  +      pLoc->aPgno = &pLoc->aPgno[WALINDEX_HDR_SIZE/sizeof(u32)];
          923  +      pLoc->iZero = 0;
   918    924       }else{
   919         -      iZero = HASHTABLE_NPAGE_ONE + (iHash-1)*HASHTABLE_NPAGE;
          925  +      pLoc->iZero = HASHTABLE_NPAGE_ONE + (iHash-1)*HASHTABLE_NPAGE;
   920    926       }
   921         -  
   922         -    *paPgno = &aPgno[-1];
   923         -    *paHash = aHash;
   924         -    *piZero = iZero;
          927  +    pLoc->aPgno = &pLoc->aPgno[-1];
   925    928     }
   926    929     return rc;
   927    930   }
   928    931   
   929    932   /*
   930    933   ** Return the number of the wal-index page that contains the hash-table
   931    934   ** and page-number array that contain entries corresponding to WAL frame
................................................................................
   963    966   **
   964    967   ** At most only the hash table containing pWal->hdr.mxFrame needs to be
   965    968   ** updated.  Any later hash tables will be automatically cleared when
   966    969   ** pWal->hdr.mxFrame advances to the point where those hash tables are
   967    970   ** actually needed.
   968    971   */
   969    972   static void walCleanupHash(Wal *pWal){
   970         -  volatile ht_slot *aHash = 0;    /* Pointer to hash table to clear */
   971         -  volatile u32 *aPgno = 0;        /* Page number array for hash table */
   972         -  u32 iZero = 0;                  /* frame == (aHash[x]+iZero) */
          973  +  WalHashLoc sLoc;                /* Hash table location */
   973    974     int iLimit = 0;                 /* Zero values greater than this */
   974    975     int nByte;                      /* Number of bytes to zero in aPgno[] */
   975    976     int i;                          /* Used to iterate through aHash[] */
   976    977   
   977    978     assert( pWal->writeLock );
   978    979     testcase( pWal->hdr.mxFrame==HASHTABLE_NPAGE_ONE-1 );
   979    980     testcase( pWal->hdr.mxFrame==HASHTABLE_NPAGE_ONE );
................................................................................
   983    984   
   984    985     /* Obtain pointers to the hash-table and page-number array containing 
   985    986     ** the entry that corresponds to frame pWal->hdr.mxFrame. It is guaranteed
   986    987     ** that the page said hash-table and array reside on is already mapped.
   987    988     */
   988    989     assert( pWal->nWiData>walFramePage(pWal->hdr.mxFrame) );
   989    990     assert( pWal->apWiData[walFramePage(pWal->hdr.mxFrame)] );
   990         -  walHashGet(pWal, walFramePage(pWal->hdr.mxFrame), &aHash, &aPgno, &iZero);
          991  +  walHashGet(pWal, walFramePage(pWal->hdr.mxFrame), &sLoc);
   991    992   
   992    993     /* Zero all hash-table entries that correspond to frame numbers greater
   993    994     ** than pWal->hdr.mxFrame.
   994    995     */
   995         -  iLimit = pWal->hdr.mxFrame - iZero;
          996  +  iLimit = pWal->hdr.mxFrame - sLoc.iZero;
   996    997     assert( iLimit>0 );
   997    998     for(i=0; i<HASHTABLE_NSLOT; i++){
   998         -    if( aHash[i]>iLimit ){
   999         -      aHash[i] = 0;
          999  +    if( sLoc.aHash[i]>iLimit ){
         1000  +      sLoc.aHash[i] = 0;
  1000   1001       }
  1001   1002     }
  1002   1003     
  1003   1004     /* Zero the entries in the aPgno array that correspond to frames with
  1004   1005     ** frame numbers greater than pWal->hdr.mxFrame. 
  1005   1006     */
  1006         -  nByte = (int)((char *)aHash - (char *)&aPgno[iLimit+1]);
  1007         -  memset((void *)&aPgno[iLimit+1], 0, nByte);
         1007  +  nByte = (int)((char *)sLoc.aHash - (char *)&sLoc.aPgno[iLimit+1]);
         1008  +  memset((void *)&sLoc.aPgno[iLimit+1], 0, nByte);
  1008   1009   
  1009   1010   #ifdef SQLITE_ENABLE_EXPENSIVE_ASSERT
  1010   1011     /* Verify that the every entry in the mapping region is still reachable
  1011   1012     ** via the hash table even after the cleanup.
  1012   1013     */
  1013   1014     if( iLimit ){
  1014   1015       int j;           /* Loop counter */
  1015   1016       int iKey;        /* Hash key */
  1016   1017       for(j=1; j<=iLimit; j++){
  1017         -      for(iKey=walHash(aPgno[j]); aHash[iKey]; iKey=walNextHash(iKey)){
  1018         -        if( aHash[iKey]==j ) break;
         1018  +      for(iKey=walHash(sLoc.aPgno[j]);sLoc.aHash[iKey];iKey=walNextHash(iKey)){
         1019  +        if( sLoc.aHash[iKey]==j ) break;
  1019   1020         }
  1020         -      assert( aHash[iKey]==j );
         1021  +      assert( sLoc.aHash[iKey]==j );
  1021   1022       }
  1022   1023     }
  1023   1024   #endif /* SQLITE_ENABLE_EXPENSIVE_ASSERT */
  1024   1025   }
  1025   1026   
  1026   1027   
  1027   1028   /*
  1028   1029   ** Set an entry in the wal-index that will map database page number
  1029   1030   ** pPage into WAL frame iFrame.
  1030   1031   */
  1031   1032   static int walIndexAppend(Wal *pWal, u32 iFrame, u32 iPage){
  1032   1033     int rc;                         /* Return code */
  1033         -  u32 iZero = 0;                  /* One less than frame number of aPgno[1] */
  1034         -  volatile u32 *aPgno = 0;        /* Page number array */
  1035         -  volatile ht_slot *aHash = 0;    /* Hash table */
         1034  +  WalHashLoc sLoc;                /* Wal-index hash table location */
  1036   1035   
  1037         -  rc = walHashGet(pWal, walFramePage(iFrame), &aHash, &aPgno, &iZero);
         1036  +  rc = walHashGet(pWal, walFramePage(iFrame), &sLoc);
  1038   1037   
  1039   1038     /* Assuming the wal-index file was successfully mapped, populate the
  1040   1039     ** page number array and hash table entry.
  1041   1040     */
  1042   1041     if( rc==SQLITE_OK ){
  1043   1042       int iKey;                     /* Hash table key */
  1044   1043       int idx;                      /* Value to write to hash-table slot */
  1045   1044       int nCollide;                 /* Number of hash collisions */
  1046   1045   
  1047         -    idx = iFrame - iZero;
         1046  +    idx = iFrame - sLoc.iZero;
  1048   1047       assert( idx <= HASHTABLE_NSLOT/2 + 1 );
  1049   1048       
  1050   1049       /* If this is the first entry to be added to this hash-table, zero the
  1051   1050       ** entire hash table and aPgno[] array before proceeding. 
  1052   1051       */
  1053   1052       if( idx==1 ){
  1054         -      int nByte = (int)((u8 *)&aHash[HASHTABLE_NSLOT] - (u8 *)&aPgno[1]);
  1055         -      memset((void*)&aPgno[1], 0, nByte);
         1053  +      int nByte = (int)((u8 *)&sLoc.aHash[HASHTABLE_NSLOT]
         1054  +                               - (u8 *)&sLoc.aPgno[1]);
         1055  +      memset((void*)&sLoc.aPgno[1], 0, nByte);
  1056   1056       }
  1057   1057   
  1058   1058       /* If the entry in aPgno[] is already set, then the previous writer
  1059   1059       ** must have exited unexpectedly in the middle of a transaction (after
  1060   1060       ** writing one or more dirty pages to the WAL to free up memory). 
  1061   1061       ** Remove the remnants of that writers uncommitted transaction from 
  1062   1062       ** the hash-table before writing any new entries.
  1063   1063       */
  1064         -    if( aPgno[idx] ){
         1064  +    if( sLoc.aPgno[idx] ){
  1065   1065         walCleanupHash(pWal);
  1066         -      assert( !aPgno[idx] );
         1066  +      assert( !sLoc.aPgno[idx] );
  1067   1067       }
  1068   1068   
  1069   1069       /* Write the aPgno[] array entry and the hash-table slot. */
  1070   1070       nCollide = idx;
  1071         -    for(iKey=walHash(iPage); aHash[iKey]; iKey=walNextHash(iKey)){
         1071  +    for(iKey=walHash(iPage); sLoc.aHash[iKey]; iKey=walNextHash(iKey)){
  1072   1072         if( (nCollide--)==0 ) return SQLITE_CORRUPT_BKPT;
  1073   1073       }
  1074         -    aPgno[idx] = iPage;
  1075         -    aHash[iKey] = (ht_slot)idx;
         1074  +    sLoc.aPgno[idx] = iPage;
         1075  +    sLoc.aHash[iKey] = (ht_slot)idx;
  1076   1076   
  1077   1077   #ifdef SQLITE_ENABLE_EXPENSIVE_ASSERT
  1078   1078       /* Verify that the number of entries in the hash table exactly equals
  1079   1079       ** the number of entries in the mapping region.
  1080   1080       */
  1081   1081       {
  1082   1082         int i;           /* Loop counter */
  1083   1083         int nEntry = 0;  /* Number of entries in the hash table */
  1084         -      for(i=0; i<HASHTABLE_NSLOT; i++){ if( aHash[i] ) nEntry++; }
         1084  +      for(i=0; i<HASHTABLE_NSLOT; i++){ if( sLoc.aHash[i] ) nEntry++; }
  1085   1085         assert( nEntry==idx );
  1086   1086       }
  1087   1087   
  1088   1088       /* Verify that the every entry in the mapping region is reachable
  1089   1089       ** via the hash table.  This turns out to be a really, really expensive
  1090   1090       ** thing to check, so only do this occasionally - not on every
  1091   1091       ** iteration.
  1092   1092       */
  1093   1093       if( (idx&0x3ff)==0 ){
  1094   1094         int i;           /* Loop counter */
  1095   1095         for(i=1; i<=idx; i++){
  1096         -        for(iKey=walHash(aPgno[i]); aHash[iKey]; iKey=walNextHash(iKey)){
  1097         -          if( aHash[iKey]==i ) break;
         1096  +        for(iKey=walHash(sLoc.aPgno[i]);
         1097  +            sLoc.aHash[iKey];
         1098  +            iKey=walNextHash(iKey)){
         1099  +          if( sLoc.aHash[iKey]==i ) break;
  1098   1100           }
  1099         -        assert( aHash[iKey]==i );
         1101  +        assert( sLoc.aHash[iKey]==i );
  1100   1102         }
  1101   1103       }
  1102   1104   #endif /* SQLITE_ENABLE_EXPENSIVE_ASSERT */
  1103   1105     }
  1104   1106   
  1105   1107   
  1106   1108     return rc;
................................................................................
  1630   1632         sizeof(ht_slot) * (iLast>HASHTABLE_NPAGE?HASHTABLE_NPAGE:iLast)
  1631   1633     );
  1632   1634     if( !aTmp ){
  1633   1635       rc = SQLITE_NOMEM_BKPT;
  1634   1636     }
  1635   1637   
  1636   1638     for(i=walFramePage(nBackfill+1); rc==SQLITE_OK && i<nSegment; i++){
  1637         -    volatile ht_slot *aHash;
  1638         -    u32 iZero;
  1639         -    volatile u32 *aPgno;
         1639  +    WalHashLoc sLoc;
  1640   1640   
  1641         -    rc = walHashGet(pWal, i, &aHash, &aPgno, &iZero);
         1641  +    rc = walHashGet(pWal, i, &sLoc);
  1642   1642       if( rc==SQLITE_OK ){
  1643   1643         int j;                      /* Counter variable */
  1644   1644         int nEntry;                 /* Number of entries in this segment */
  1645   1645         ht_slot *aIndex;            /* Sorted index for this segment */
  1646   1646   
  1647         -      aPgno++;
         1647  +      sLoc.aPgno++;
  1648   1648         if( (i+1)==nSegment ){
  1649         -        nEntry = (int)(iLast - iZero);
         1649  +        nEntry = (int)(iLast - sLoc.iZero);
  1650   1650         }else{
  1651         -        nEntry = (int)((u32*)aHash - (u32*)aPgno);
         1651  +        nEntry = (int)((u32*)sLoc.aHash - (u32*)sLoc.aPgno);
  1652   1652         }
  1653         -      aIndex = &((ht_slot *)&p->aSegment[p->nSegment])[iZero];
  1654         -      iZero++;
         1653  +      aIndex = &((ht_slot *)&p->aSegment[p->nSegment])[sLoc.iZero];
         1654  +      sLoc.iZero++;
  1655   1655     
  1656   1656         for(j=0; j<nEntry; j++){
  1657   1657           aIndex[j] = (ht_slot)j;
  1658   1658         }
  1659         -      walMergesort((u32 *)aPgno, aTmp, aIndex, &nEntry);
  1660         -      p->aSegment[i].iZero = iZero;
         1659  +      walMergesort((u32 *)sLoc.aPgno, aTmp, aIndex, &nEntry);
         1660  +      p->aSegment[i].iZero = sLoc.iZero;
  1661   1661         p->aSegment[i].nEntry = nEntry;
  1662   1662         p->aSegment[i].aIndex = aIndex;
  1663         -      p->aSegment[i].aPgno = (u32 *)aPgno;
         1663  +      p->aSegment[i].aPgno = (u32 *)sLoc.aPgno;
  1664   1664       }
  1665   1665     }
  1666   1666     sqlite3_free(aTmp);
  1667   1667   
  1668   1668     if( rc!=SQLITE_OK ){
  1669   1669       walIteratorFree(p);
  1670   1670       p = 0;
................................................................................
  2669   2669         void *pBuf1 = sqlite3_malloc(szPage);
  2670   2670         void *pBuf2 = sqlite3_malloc(szPage);
  2671   2671         if( pBuf1==0 || pBuf2==0 ){
  2672   2672           rc = SQLITE_NOMEM;
  2673   2673         }else{
  2674   2674           u32 i = pInfo->nBackfillAttempted;
  2675   2675           for(i=pInfo->nBackfillAttempted; i>pInfo->nBackfill; i--){
  2676         -          volatile ht_slot *dummy;
  2677         -          volatile u32 *aPgno;      /* Array of page numbers */
  2678         -          u32 iZero;                /* Frame corresponding to aPgno[0] */
         2676  +          WalHashLoc sLoc;          /* Hash table location */
  2679   2677             u32 pgno;                 /* Page number in db file */
  2680   2678             i64 iDbOff;               /* Offset of db file entry */
  2681   2679             i64 iWalOff;              /* Offset of wal file entry */
  2682   2680   
  2683         -          rc = walHashGet(pWal, walFramePage(i), &dummy, &aPgno, &iZero);
         2681  +          rc = walHashGet(pWal, walFramePage(i), &sLoc);
  2684   2682             if( rc!=SQLITE_OK ) break;
  2685         -          pgno = aPgno[i-iZero];
         2683  +          pgno = sLoc.aPgno[i-sLoc.iZero];
  2686   2684             iDbOff = (i64)(pgno-1) * szPage;
  2687   2685   
  2688   2686             if( iDbOff+szPage<=szDb ){
  2689   2687               iWalOff = walFrameOffset(i, szPage) + WAL_FRAME_HDRSIZE;
  2690   2688               rc = sqlite3OsRead(pWal->pWalFd, pBuf1, szPage, iWalOff);
  2691   2689   
  2692   2690               if( rc==SQLITE_OK ){
................................................................................
  2879   2877     **
  2880   2878     **   (iFrame<=iLast): 
  2881   2879     **     This condition filters out entries that were added to the hash
  2882   2880     **     table after the current read-transaction had started.
  2883   2881     */
  2884   2882     iMinHash = walFramePage(pWal->minFrame);
  2885   2883     for(iHash=walFramePage(iLast); iHash>=iMinHash; iHash--){
  2886         -    volatile ht_slot *aHash;      /* Pointer to hash table */
  2887         -    volatile u32 *aPgno;          /* Pointer to array of page numbers */
  2888         -    u32 iZero;                    /* Frame number corresponding to aPgno[0] */
         2884  +    WalHashLoc sLoc;              /* Hash table location */
  2889   2885       int iKey;                     /* Hash slot index */
  2890   2886       int nCollide;                 /* Number of hash collisions remaining */
  2891   2887       int rc;                       /* Error code */
  2892   2888   
  2893         -    rc = walHashGet(pWal, iHash, &aHash, &aPgno, &iZero);
         2889  +    rc = walHashGet(pWal, iHash, &sLoc);
  2894   2890       if( rc!=SQLITE_OK ){
  2895   2891         return rc;
  2896   2892       }
  2897   2893       nCollide = HASHTABLE_NSLOT;
  2898         -    for(iKey=walHash(pgno); aHash[iKey]; iKey=walNextHash(iKey)){
  2899         -      u32 iFrame = aHash[iKey] + iZero;
  2900         -      if( iFrame<=iLast && iFrame>=pWal->minFrame && aPgno[aHash[iKey]]==pgno ){
         2894  +    for(iKey=walHash(pgno); sLoc.aHash[iKey]; iKey=walNextHash(iKey)){
         2895  +      u32 iFrame = sLoc.aHash[iKey] + sLoc.iZero;
         2896  +      if( iFrame<=iLast && iFrame>=pWal->minFrame
         2897  +       && sLoc.aPgno[sLoc.aHash[iKey]]==pgno ){
  2901   2898           assert( iFrame>iRead || CORRUPT_DB );
  2902   2899           iRead = iFrame;
  2903   2900         }
  2904   2901         if( (nCollide--)==0 ){
  2905   2902           return SQLITE_CORRUPT_BKPT;
  2906   2903         }
  2907   2904       }