/ Check-in [05a3a2cd]
Login

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

Overview
Comment:Simplification of the LRU list handling in pcache1.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1: 05a3a2cd140587265b5427d23c93c5be1f39e199
User & Date: drh 2015-09-04 04:31:56
Context
2015-09-04
10:31
Modify the fts5 custom tokenizer interface to permit synonym support. The fts5_api.iVersion value is now set to 2. Existing fts5 custom tokenizers (if there are such things) will need to be updated to use the new api version. check-in: 0b7e4ab8 user: dan tags: trunk
10:24
Merge latest trunk changes. Closed-Leaf check-in: 443a5eb8 user: dan tags: fts5-incompatible
04:31
Simplification of the LRU list handling in pcache1. check-in: 05a3a2cd user: drh tags: trunk
2015-09-03
20:43
Change the pcache module to keep track of the total number of references to all pages rather than the number of pages references, for a performance improvement and size reduction. check-in: f00a9e1e user: drh tags: trunk
Changes
Hide Diffs Side-by-Side Diffs Ignore Whitespace Patch

Changes to src/pcache1.c.

    82     82   */
    83     83   #include "sqliteInt.h"
    84     84   
    85     85   typedef struct PCache1 PCache1;
    86     86   typedef struct PgHdr1 PgHdr1;
    87     87   typedef struct PgFreeslot PgFreeslot;
    88     88   typedef struct PGroup PGroup;
           89  +
           90  +/*
           91  +** Each cache entry is represented by an instance of the following 
           92  +** structure. Unless SQLITE_PCACHE_SEPARATE_HEADER is defined, a buffer of
           93  +** PgHdr1.pCache->szPage bytes is allocated directly before this structure 
           94  +** in memory.
           95  +*/
           96  +struct PgHdr1 {
           97  +  sqlite3_pcache_page page;      /* Base class. Must be first. pBuf & pExtra */
           98  +  unsigned int iKey;             /* Key value (page number) */
           99  +  u8 isPinned;                   /* Page in use, not on the LRU list */
          100  +  u8 isBulkLocal;                /* This page from bulk local storage */
          101  +  u8 isAnchor;                   /* This is the PGroup.lru element */
          102  +  PgHdr1 *pNext;                 /* Next in hash table chain */
          103  +  PCache1 *pCache;               /* Cache that currently owns this page */
          104  +  PgHdr1 *pLruNext;              /* Next in LRU list of unpinned pages */
          105  +  PgHdr1 *pLruPrev;              /* Previous in LRU list of unpinned pages */
          106  +};
    89    107   
    90    108   /* Each page cache (or PCache) belongs to a PGroup.  A PGroup is a set 
    91    109   ** of one or more PCaches that are able to recycle each other's unpinned
    92    110   ** pages when they are under memory pressure.  A PGroup is an instance of
    93    111   ** the following object.
    94    112   **
    95    113   ** This page cache implementation works in one of two modes:
................................................................................
   111    129   */
   112    130   struct PGroup {
   113    131     sqlite3_mutex *mutex;          /* MUTEX_STATIC_LRU or NULL */
   114    132     unsigned int nMaxPage;         /* Sum of nMax for purgeable caches */
   115    133     unsigned int nMinPage;         /* Sum of nMin for purgeable caches */
   116    134     unsigned int mxPinned;         /* nMaxpage + 10 - nMinPage */
   117    135     unsigned int nCurrentPage;     /* Number of purgeable pages allocated */
   118         -  PgHdr1 *pLruHead, *pLruTail;   /* LRU list of unpinned pages */
          136  +  PgHdr1 lru;                    /* The beginning and end of the LRU list */
   119    137   };
   120    138   
   121    139   /* Each page cache is an instance of the following object.  Every
   122    140   ** open database file (including each in-memory database and each
   123    141   ** temporary or transient database) has a single page cache which
   124    142   ** is an instance of this object.
   125    143   **
................................................................................
   149    167     unsigned int nPage;                 /* Total number of pages in apHash */
   150    168     unsigned int nHash;                 /* Number of slots in apHash[] */
   151    169     PgHdr1 **apHash;                    /* Hash table for fast lookup by key */
   152    170     PgHdr1 *pFree;                      /* List of unused pcache-local pages */
   153    171     void *pBulk;                        /* Bulk memory used by pcache-local */
   154    172   };
   155    173   
   156         -/*
   157         -** Each cache entry is represented by an instance of the following 
   158         -** structure. Unless SQLITE_PCACHE_SEPARATE_HEADER is defined, a buffer of
   159         -** PgHdr1.pCache->szPage bytes is allocated directly before this structure 
   160         -** in memory.
   161         -*/
   162         -struct PgHdr1 {
   163         -  sqlite3_pcache_page page;
   164         -  unsigned int iKey;             /* Key value (page number) */
   165         -  u8 isPinned;                   /* Page in use, not on the LRU list */
   166         -  u8 isBulkLocal;                /* This page from bulk local storage */
   167         -  PgHdr1 *pNext;                 /* Next in hash table chain */
   168         -  PCache1 *pCache;               /* Cache that currently owns this page */
   169         -  PgHdr1 *pLruNext;              /* Next in LRU list of unpinned pages */
   170         -  PgHdr1 *pLruPrev;              /* Previous in LRU list of unpinned pages */
   171         -};
   172         -
   173    174   /*
   174    175   ** Free slots in the allocator used to divide up the global page cache
   175    176   ** buffer provided using the SQLITE_CONFIG_PAGECACHE mechanism.
   176    177   */
   177    178   struct PgFreeslot {
   178    179     PgFreeslot *pNext;  /* Next free slot */
   179    180   };
................................................................................
   225    226   # define pcache1EnterMutex(X) sqlite3_mutex_enter((X)->mutex)
   226    227   # define pcache1LeaveMutex(X) sqlite3_mutex_leave((X)->mutex)
   227    228   # define PCACHE1_MIGHT_USE_GROUP_MUTEX 1
   228    229   #endif
   229    230   
   230    231   /******************************************************************************/
   231    232   /******** Page Allocation/SQLITE_CONFIG_PCACHE Related Functions **************/
          233  +
   232    234   
   233    235   /*
   234    236   ** This function is called during initialization if a static buffer is 
   235    237   ** supplied to use for the page-cache by passing the SQLITE_CONFIG_PAGECACHE
   236    238   ** verb to sqlite3_config(). Parameter pBuf points to an allocation large
   237    239   ** enough to contain 'n' buffers of 'sz' bytes each.
   238    240   **
................................................................................
   285    287       int nBulk = sqlite3MallocSize(zBulk)/pCache->szAlloc;
   286    288       int i;
   287    289       for(i=0; i<nBulk; i++){
   288    290         PgHdr1 *pX = (PgHdr1*)&zBulk[pCache->szPage];
   289    291         pX->page.pBuf = zBulk;
   290    292         pX->page.pExtra = &pX[1];
   291    293         pX->isBulkLocal = 1;
          294  +      pX->isAnchor = 0;
   292    295         pX->pNext = pCache->pFree;
   293    296         pCache->pFree = pX;
   294    297         zBulk += pCache->szAlloc;
   295    298       }
   296    299     }
   297    300     return pCache->pFree!=0;
   298    301   }
................................................................................
   427    430   #ifdef SQLITE_ENABLE_MEMORY_MANAGEMENT
   428    431       pcache1EnterMutex(pCache->pGroup);
   429    432   #endif
   430    433       if( pPg==0 ) return 0;
   431    434       p->page.pBuf = pPg;
   432    435       p->page.pExtra = &p[1];
   433    436       p->isBulkLocal = 0;
          437  +    p->isAnchor = 0;
   434    438     }
   435    439     if( pCache->bPurgeable ){
   436    440       pCache->pGroup->nCurrentPage++;
   437    441     }
   438    442     return p;
   439    443   }
   440    444   
................................................................................
   553    557   */
   554    558   static PgHdr1 *pcache1PinPage(PgHdr1 *pPage){
   555    559     PCache1 *pCache;
   556    560   
   557    561     assert( pPage!=0 );
   558    562     assert( pPage->isPinned==0 );
   559    563     pCache = pPage->pCache;
   560         -  assert( pPage->pLruNext || pPage==pCache->pGroup->pLruTail );
   561         -  assert( pPage->pLruPrev || pPage==pCache->pGroup->pLruHead );
          564  +  assert( pPage->pLruNext );
          565  +  assert( pPage->pLruPrev );
   562    566     assert( sqlite3_mutex_held(pCache->pGroup->mutex) );
   563         -  if( pPage->pLruPrev ){
   564         -    pPage->pLruPrev->pLruNext = pPage->pLruNext;
   565         -  }else{
   566         -    pCache->pGroup->pLruHead = pPage->pLruNext;
   567         -  }
   568         -  if( pPage->pLruNext ){
   569         -    pPage->pLruNext->pLruPrev = pPage->pLruPrev;
   570         -  }else{
   571         -    pCache->pGroup->pLruTail = pPage->pLruPrev;
   572         -  }
          567  +  pPage->pLruPrev->pLruNext = pPage->pLruNext;
          568  +  pPage->pLruNext->pLruPrev = pPage->pLruPrev;
   573    569     pPage->pLruNext = 0;
   574    570     pPage->pLruPrev = 0;
   575    571     pPage->isPinned = 1;
          572  +  assert( pPage->isAnchor==0 );
          573  +  assert( pCache->pGroup->lru.isAnchor==1 );
   576    574     pCache->nRecyclable--;
   577    575     return pPage;
   578    576   }
   579    577   
   580    578   
   581    579   /*
   582    580   ** Remove the page supplied as an argument from the hash table 
................................................................................
   601    599   
   602    600   /*
   603    601   ** If there are currently more than nMaxPage pages allocated, try
   604    602   ** to recycle pages to reduce the number allocated to nMaxPage.
   605    603   */
   606    604   static void pcache1EnforceMaxPage(PCache1 *pCache){
   607    605     PGroup *pGroup = pCache->pGroup;
          606  +  PgHdr1 *p;
   608    607     assert( sqlite3_mutex_held(pGroup->mutex) );
   609         -  while( pGroup->nCurrentPage>pGroup->nMaxPage && pGroup->pLruTail ){
   610         -    PgHdr1 *p = pGroup->pLruTail;
          608  +  while( pGroup->nCurrentPage>pGroup->nMaxPage
          609  +      && (p=pGroup->lru.pLruPrev)->isAnchor==0
          610  +  ){
   611    611       assert( p->pCache->pGroup==pGroup );
   612    612       assert( p->isPinned==0 );
   613    613       pcache1PinPage(p);
   614    614       pcache1RemoveFromHash(p, 1);
   615    615     }
   616    616     if( pCache->nPage==0 && pCache->pBulk ){
   617    617       sqlite3_free(pCache->pBulk);
................................................................................
   737    737     if( pCache ){
   738    738       if( pcache1.separateCache ){
   739    739         pGroup = (PGroup*)&pCache[1];
   740    740         pGroup->mxPinned = 10;
   741    741       }else{
   742    742         pGroup = &pcache1.grp;
   743    743       }
          744  +    if( pGroup->lru.isAnchor==0 ){
          745  +      pGroup->lru.isAnchor = 1;
          746  +      pGroup->lru.pLruPrev = pGroup->lru.pLruNext = &pGroup->lru;
          747  +    }
   744    748       pCache->pGroup = pGroup;
   745    749       pCache->szPage = szPage;
   746    750       pCache->szExtra = szExtra;
   747    751       pCache->szAlloc = szPage + szExtra + ROUND8(sizeof(PgHdr1));
   748    752       pCache->bPurgeable = (bPurgeable ? 1 : 0);
   749    753       pcache1EnterMutex(pGroup);
   750    754       pcache1ResizeHash(pCache);
................................................................................
   844    848     }
   845    849   
   846    850     if( pCache->nPage>=pCache->nHash ) pcache1ResizeHash(pCache);
   847    851     assert( pCache->nHash>0 && pCache->apHash );
   848    852   
   849    853     /* Step 4. Try to recycle a page. */
   850    854     if( pCache->bPurgeable
   851         -   && pGroup->pLruTail
          855  +   && !pGroup->lru.pLruPrev->isAnchor
   852    856      && ((pCache->nPage+1>=pCache->nMax) || pcache1UnderMemoryPressure(pCache))
   853    857     ){
   854    858       PCache1 *pOther;
   855         -    pPage = pGroup->pLruTail;
          859  +    pPage = pGroup->lru.pLruPrev;
   856    860       assert( pPage->isPinned==0 );
   857    861       pcache1RemoveFromHash(pPage, 0);
   858    862       pcache1PinPage(pPage);
   859    863       pOther = pPage->pCache;
   860    864       if( pOther->szAlloc != pCache->szAlloc ){
   861    865         pcache1FreePage(pPage);
   862    866         pPage = 0;
................................................................................
  1037   1041     assert( pPage->pCache==pCache );
  1038   1042     pcache1EnterMutex(pGroup);
  1039   1043   
  1040   1044     /* It is an error to call this function if the page is already 
  1041   1045     ** part of the PGroup LRU list.
  1042   1046     */
  1043   1047     assert( pPage->pLruPrev==0 && pPage->pLruNext==0 );
  1044         -  assert( pGroup->pLruHead!=pPage && pGroup->pLruTail!=pPage );
  1045   1048     assert( pPage->isPinned==1 );
  1046   1049   
  1047   1050     if( reuseUnlikely || pGroup->nCurrentPage>pGroup->nMaxPage ){
  1048   1051       pcache1RemoveFromHash(pPage, 1);
  1049   1052     }else{
  1050   1053       /* Add the page to the PGroup LRU list. */
  1051         -    if( pGroup->pLruHead ){
  1052         -      pGroup->pLruHead->pLruPrev = pPage;
  1053         -      pPage->pLruNext = pGroup->pLruHead;
  1054         -      pGroup->pLruHead = pPage;
  1055         -    }else{
  1056         -      pGroup->pLruTail = pPage;
  1057         -      pGroup->pLruHead = pPage;
  1058         -    }
         1054  +    PgHdr1 **ppFirst = &pGroup->lru.pLruNext;
         1055  +    pPage->pLruPrev = &pGroup->lru;
         1056  +    (pPage->pLruNext = *ppFirst)->pLruPrev = pPage;
         1057  +    *ppFirst = pPage;
  1059   1058       pCache->nRecyclable++;
  1060   1059       pPage->isPinned = 0;
  1061   1060     }
  1062   1061   
  1063   1062     pcache1LeaveMutex(pCache->pGroup);
  1064   1063   }
  1065   1064   
................................................................................
  1189   1188   int sqlite3PcacheReleaseMemory(int nReq){
  1190   1189     int nFree = 0;
  1191   1190     assert( sqlite3_mutex_notheld(pcache1.grp.mutex) );
  1192   1191     assert( sqlite3_mutex_notheld(pcache1.mutex) );
  1193   1192     if( sqlite3GlobalConfig.nPage==0 ){
  1194   1193       PgHdr1 *p;
  1195   1194       pcache1EnterMutex(&pcache1.grp);
  1196         -    while( (nReq<0 || nFree<nReq) && ((p=pcache1.grp.pLruTail)!=0) ){
         1195  +    while( (nReq<0 || nFree<nReq)
         1196  +       &&  (p=pcache1.grp.lru.pLruPrev)->isAnchor==0
         1197  +    ){
  1197   1198         nFree += pcache1MemSize(p->page.pBuf);
  1198   1199   #ifdef SQLITE_PCACHE_SEPARATE_HEADER
  1199   1200         nFree += sqlite3MemSize(p);
  1200   1201   #endif
  1201   1202         assert( p->isPinned==0 );
  1202   1203         pcache1PinPage(p);
  1203   1204         pcache1RemoveFromHash(p, 1);
................................................................................
  1217   1218     int *pnCurrent,      /* OUT: Total number of pages cached */
  1218   1219     int *pnMax,          /* OUT: Global maximum cache size */
  1219   1220     int *pnMin,          /* OUT: Sum of PCache1.nMin for purgeable caches */
  1220   1221     int *pnRecyclable    /* OUT: Total number of pages available for recycling */
  1221   1222   ){
  1222   1223     PgHdr1 *p;
  1223   1224     int nRecyclable = 0;
  1224         -  for(p=pcache1.grp.pLruHead; p; p=p->pLruNext){
         1225  +  for(p=pcache1.grp.lru.pLruNext; !p->isAnchor; p=p->pLruNext){
  1225   1226       assert( p->isPinned==0 );
  1226   1227       nRecyclable++;
  1227   1228     }
  1228   1229     *pnCurrent = pcache1.grp.nCurrentPage;
  1229   1230     *pnMax = (int)pcache1.grp.nMaxPage;
  1230   1231     *pnMin = (int)pcache1.grp.nMinPage;
  1231   1232     *pnRecyclable = nRecyclable;
  1232   1233   }
  1233   1234   #endif