API tools faq
paste
cgabriel

sqlite3 priority cache

cgabriel
Feb 25th, 2013
109
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Diff 9.40 KB | None | 0 0
raw download clone embed print report
  1. --- C:/Dokumente und Einstellungen/gc/Lokale Einstellungen/Temp/_tc/sqlite-src-3071502/src/pcache1.c    Wed Jan 09 20:51:48 2013
  2. +++ c:/MinGW/projects/sqlite-src-3071502/src/pcache1.c  Mon Feb 25 12:02:42 2013
  3. @@ -23,6 +23,17 @@
  4.  typedef struct PgHdr1 PgHdr1;
  5.  typedef struct PgFreeslot PgFreeslot;
  6.  typedef struct PGroup PGroup;
  7. +typedef struct PHeap1 PHeap1;
  8. +
  9. +/* gc:
  10. +  Heap structure for keeping cached pages
  11. +*/
  12. +struct PHeap1{
  13. +  PgHdr1 **hItems;               // 1 extra item; valid 1..iCount
  14. +  int    iCount;                 // stored entries
  15. +  int    iCap;                   // capacity
  16. +};
  17. +
  18.  
  19.  /* Each page cache (or PCache) belongs to a PGroup.  A PGroup is a set
  20.  ** of one or more PCaches that are able to recycle each others unpinned
  21. @@ -52,7 +63,8 @@
  22.    unsigned int nMinPage;         /* Sum of nMin for purgeable caches */
  23.    unsigned int mxPinned;         /* nMaxpage + 10 - nMinPage */
  24.    unsigned int nCurrentPage;     /* Number of purgeable pages allocated */
  25. -  PgHdr1 *pLruHead, *pLruTail;   /* LRU list of unpinned pages */
  26. +
  27. +  PHeap1 h;                      /* heap containing unpinned pages */
  28.  };
  29.  
  30.  /* Each page cache is an instance of the following object.  Every
  31. @@ -96,13 +108,120 @@
  32.  struct PgHdr1 {
  33.    sqlite3_pcache_page page;
  34.    unsigned int iKey;             /* Key value (page number) */
  35. +  unsigned int iFetch;           /* fetch count */
  36. +  unsigned int hPos;             /* heap position; updated on change */
  37.    PgHdr1 *pNext;                 /* Next in hash table chain */
  38.    PCache1 *pCache;               /* Cache that currently owns this page */
  39. -  PgHdr1 *pLruNext;              /* Next in LRU list of unpinned pages */
  40. -  PgHdr1 *pLruPrev;              /* Previous in LRU list of unpinned pages */
  41.  };
  42.  
  43.  /*
  44. +  Gabriel Corneanu: heap implementation on cache pages
  45. +*/
  46. +static int HGrow(PHeap1 *h){
  47. +  h->iCap = (h->iCap >= 20) ? h->iCap * 11 / 10 : 20;
  48. +  h->hItems = sqlite3Realloc(h->hItems, h->iCap * sizeof(PgHdr1));
  49. +}
  50. +
  51. +static int HInit(PHeap1 *h){
  52. +  h->iCount = 0;
  53. +  h->hItems = 0;
  54. +  h->iCap   = 50;
  55. +  h->hItems = 0;
  56. +  HGrow(h);
  57. +}
  58. +
  59. +static int HFree(PHeap1 *h){
  60. +  sqlite3_free(h->hItems);
  61. +}
  62. +
  63. +#define HeapCompare(A,B) \
  64. +  (h->hItems[A]->iFetch <= h->hItems[B]->iFetch)
  65. +
  66. +#define ParentElement(i) (i / 2)
  67. +#define LeftChildElement(i) (i * 2)
  68. +
  69. +static void HPropagateDown(PHeap1 *h, int Elem){
  70. +//
  71. +// propagate the given element down to its place in the heap
  72. +// this makes sense from the top (or for rebuild)
  73. +// returns new position
  74. +//
  75. +  if (Elem >= h->iCount) return;
  76. +  int c = LeftChildElement(Elem);
  77. +  PgHdr1 *t = h->hItems[Elem]; // compare value
  78. +  while (c <= h->iCount){
  79. +    //smallest child, if available
  80. +    if ((c < h->iCount) && !HeapCompare(c, c+1) )
  81. +      c++; //the other child
  82. +
  83. +    if (t->iFetch <= h->hItems[c]->iFetch) break;
  84. +    //exchange is not needed, only once at the end!
  85. +    h->hItems[Elem] = h->hItems[c];
  86. +    h->hItems[Elem]->hPos = Elem;
  87. +    Elem = c;
  88. +    c = LeftChildElement(c);
  89. +  }
  90. +  h->hItems[Elem] = t;
  91. +  h->hItems[Elem]->hPos = Elem;
  92. +}
  93. +
  94. +/*
  95. +// propagate the given element down to its place in the heap
  96. +// returns new position
  97. +*/
  98. +void HPropagateUp(PHeap1 *h, int Elem){
  99. +  if (Elem <= 1) return;
  100. +  int p = ParentElement(Elem);
  101. +  PgHdr1 *t = h->hItems[Elem]; // compare value
  102. +  while (p > 1 && (t->iFetch <= h->hItems[p]->iFetch) ) {
  103. +    //exchange is not needed, only once at the end!
  104. +    h->hItems[Elem] = h->hItems[p];
  105. +    h->hItems[Elem]->hPos = Elem;
  106. +    Elem = p;
  107. +    p = ParentElement(p);
  108. +  }
  109. +  h->hItems[Elem] = t;
  110. +  h->hItems[Elem]->hPos = Elem;
  111. +}
  112. +
  113. +/*
  114. +// extract requested element and adjust the heap
  115. +*/
  116. +static PgHdr1 *HExtract(PHeap1 *h, int Elem){
  117. +  if (Elem < 1 || Elem > h->iCount){
  118. +    return 0;
  119. +  }
  120. +
  121. +  PgHdr1 *p = h->hItems[Elem];
  122. +  assert(p->hPos == Elem);
  123. +  p->hPos = 0;
  124. +  h->hItems[Elem] = h->hItems[ h->iCount -- ];
  125. +  h->hItems[Elem]->hPos = Elem;
  126. +  HPropagateDown(h, Elem);
  127. +  return p;
  128. +}
  129. +
  130. +/* usual pop, not used * /
  131. +static PgHdr1 *HPop(PHeap1 *h){ return HExtract(h->iCount); }
  132. +*/
  133. +
  134. +/* usual peek; extraction is done via pcache1PinPage */
  135. +static PgHdr1 *HPeek(PHeap1 *h){ return h->iCount ? h->hItems[1] : 0 ; }
  136. +
  137. +/*
  138. +//add a new element in heap
  139. +*/
  140. +static void HPush(PHeap1 *h, PgHdr1 *p){
  141. +  if (h->iCount >= h->iCap)
  142. +    HGrow(h);
  143. +
  144. +  int pos = ++ (h->iCount);
  145. +  p->hPos = pos;
  146. +  h->hItems[pos] = p;
  147. +  HPropagateUp(h, pos);
  148. +}
  149. +
  150. +/*
  151.  ** Free slots in the allocator used to divide up the buffer provided using
  152.  ** the SQLITE_CONFIG_PAGECACHE mechanism.
  153.  */
  154. @@ -435,22 +554,9 @@
  155.    pCache = pPage->pCache;
  156.    pGroup = pCache->pGroup;
  157.    assert( sqlite3_mutex_held(pGroup->mutex) );
  158. -  if( pPage->pLruNext || pPage==pGroup->pLruTail ){
  159. -    if( pPage->pLruPrev ){
  160. -      pPage->pLruPrev->pLruNext = pPage->pLruNext;
  161. -    }
  162. -    if( pPage->pLruNext ){
  163. -      pPage->pLruNext->pLruPrev = pPage->pLruPrev;
  164. -    }
  165. -    if( pGroup->pLruHead==pPage ){
  166. -      pGroup->pLruHead = pPage->pLruNext;
  167. -    }
  168. -    if( pGroup->pLruTail==pPage ){
  169. -      pGroup->pLruTail = pPage->pLruPrev;
  170. -    }
  171. -    pPage->pLruNext = 0;
  172. -    pPage->pLruPrev = 0;
  173. -    pPage->pCache->nRecyclable--;
  174. +  if( pPage->hPos ){
  175. +    HExtract(&pGroup->h, pPage->hPos);
  176. +    pCache->nRecyclable--;
  177.    }
  178.  }
  179.  
  180. @@ -480,8 +586,8 @@
  181.  */
  182.  static void pcache1EnforceMaxPage(PGroup *pGroup){
  183.    assert( sqlite3_mutex_held(pGroup->mutex) );
  184. -  while( pGroup->nCurrentPage>pGroup->nMaxPage && pGroup->pLruTail ){
  185. -    PgHdr1 *p = pGroup->pLruTail;
  186. +  PgHdr1 *p;
  187. +  while( pGroup->nCurrentPage>pGroup->nMaxPage && (p = HPeek(&pGroup->h))){
  188.      assert( p->pCache->pGroup==pGroup );
  189.      pcache1PinPage(p);
  190.      pcache1RemoveFromHash(p);
  191. @@ -535,6 +641,7 @@
  192.      pcache1.grp.mutex = sqlite3_mutex_alloc(SQLITE_MUTEX_STATIC_LRU);
  193.      pcache1.mutex = sqlite3_mutex_alloc(SQLITE_MUTEX_STATIC_PMEM);
  194.    }
  195. +  HInit(&pcache1.grp.h);
  196.    pcache1.grp.mxPinned = 10;
  197.    pcache1.isInit = 1;
  198.    return SQLITE_OK;
  199. @@ -548,6 +655,7 @@
  200.  static void pcache1Shutdown(void *NotUsed){
  201.    UNUSED_PARAMETER(NotUsed);
  202.    assert( pcache1.isInit!=0 );
  203. +  HFree(&pcache1.grp.h);
  204.    memset(&pcache1, 0, sizeof(pcache1));
  205.  }
  206.  
  207. @@ -588,6 +696,7 @@
  208.      if( separateCache ){
  209.        pGroup = (PGroup*)&pCache[1];
  210.        pGroup->mxPinned = 10;
  211. +      HInit(&pGroup->h);
  212.      }else{
  213.        pGroup = &pcache1.grp;
  214.      }
  215. @@ -735,6 +844,11 @@
  216.    /* Step 2: Abort if no existing page is found and createFlag is 0 */
  217.    if( pPage || createFlag==0 ){
  218.      pcache1PinPage(pPage);
  219. +    if(pPage){
  220. +      pPage->iFetch++; //increment fetch counter
  221. +      if(pPage->hPos)
  222. +        HPropagateDown(&pGroup->h, pPage->hPos);
  223. +    }
  224.      goto fetch_out;
  225.    }
  226.  
  227. @@ -767,13 +881,13 @@
  228.    }
  229.  
  230.    /* Step 4. Try to recycle a page. */
  231. -  if( pCache->bPurgeable && pGroup->pLruTail && (
  232. +  if( pCache->bPurgeable && pGroup->h.iCount && (
  233.           (pCache->nPage+1>=pCache->nMax)
  234.        || pGroup->nCurrentPage>=pGroup->nMaxPage
  235.        || pcache1UnderMemoryPressure(pCache)
  236.    )){
  237.      PCache1 *pOther;
  238. -    pPage = pGroup->pLruTail;
  239. +    pPage = HPeek(&pGroup->h);
  240.      pcache1RemoveFromHash(pPage);
  241.      pcache1PinPage(pPage);
  242.      pOther = pPage->pCache;
  243. @@ -808,8 +922,8 @@
  244.      pPage->iKey = iKey;
  245.      pPage->pNext = pCache->apHash[h];
  246.      pPage->pCache = pCache;
  247. -    pPage->pLruPrev = 0;
  248. -    pPage->pLruNext = 0;
  249. +    pPage->hPos   = 0;
  250. +    pPage->iFetch = 0;
  251.      *(void **)pPage->page.pExtra = 0;
  252.      pCache->apHash[h] = pPage;
  253.    }
  254. @@ -843,22 +957,14 @@
  255.    /* It is an error to call this function if the page is already
  256.    ** part of the PGroup LRU list.
  257.    */
  258. -  assert( pPage->pLruPrev==0 && pPage->pLruNext==0 );
  259. -  assert( pGroup->pLruHead!=pPage && pGroup->pLruTail!=pPage );
  260. +  assert( pPage->hPos==0 );
  261.  
  262.    if( reuseUnlikely || pGroup->nCurrentPage>pGroup->nMaxPage ){
  263.      pcache1RemoveFromHash(pPage);
  264.      pcache1FreePage(pPage);
  265.    }else{
  266.      /* Add the page to the PGroup LRU list. */
  267. -    if( pGroup->pLruHead ){
  268. -      pGroup->pLruHead->pLruPrev = pPage;
  269. -      pPage->pLruNext = pGroup->pLruHead;
  270. -      pGroup->pLruHead = pPage;
  271. -    }else{
  272. -      pGroup->pLruTail = pPage;
  273. -      pGroup->pLruHead = pPage;
  274. -    }
  275. +    HPush(&pGroup->h, pPage);
  276.      pCache->nRecyclable++;
  277.    }
  278.  
  279. @@ -935,6 +1041,8 @@
  280.    pGroup->nMinPage -= pCache->nMin;
  281.    pGroup->mxPinned = pGroup->nMaxPage + 10 - pGroup->nMinPage;
  282.    pcache1EnforceMaxPage(pGroup);
  283. +  if(pGroup != &pcache1.grp)
  284. +    HFree(&pGroup->h);
  285.    pcache1LeaveMutex(pGroup);
  286.    sqlite3_free(pCache->apHash);
  287.    sqlite3_free(pCache);
  288. @@ -981,7 +1089,7 @@
  289.    if( pcache1.pStart==0 ){
  290.      PgHdr1 *p;
  291.      pcache1EnterMutex(&pcache1.grp);
  292. -    while( (nReq<0 || nFree<nReq) && ((p=pcache1.grp.pLruTail)!=0) ){
  293. +    while( (nReq<0 || nFree<nReq) && (p=HPeek(&pcache1.grp.h)) ){
  294.        nFree += pcache1MemSize(p->page.pBuf);
  295.  #ifdef SQLITE_PCACHE_SEPARATE_HEADER
  296.        nFree += sqlite3MemSize(p);
  297. @@ -1007,11 +1115,7 @@
  298.    int *pnMin,          /* OUT: Sum of PCache1.nMin for purgeable caches */
  299.    int *pnRecyclable    /* OUT: Total number of pages available for recycling */
  300.  ){
  301. -  PgHdr1 *p;
  302. -  int nRecyclable = 0;
  303. -  for(p=pcache1.grp.pLruHead; p; p=p->pLruNext){
  304. -    nRecyclable++;
  305. -  }
  306. +  int nRecyclable = pcache1.grp.h.iCount;
  307.    *pnCurrent = pcache1.grp.nCurrentPage;
  308.    *pnMax = (int)pcache1.grp.nMaxPage;
  309.    *pnMin = (int)pcache1.grp.nMinPage;
Advertisement
Add Comment
Please, Sign In to add comment
Public Pastes
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!