src/test_pcache.c

   1 /*
   2 ** 2008 November 18
   3 **
   4 ** The author disclaims copyright to this source code.  In place of
   5 ** a legal notice, here is a blessing:
   6 **
   7 **    May you do good and not evil.
   8 **    May you find forgiveness for yourself and forgive others.
   9 **    May you share freely, never taking more than you give.
  10 **
  11 *************************************************************************
  12 **
  13 ** This file contains code used for testing the SQLite system.
  14 ** None of the code in this file goes into a deliverable build.
  15 **
  16 ** This file contains an application-defined pager cache
  17 ** implementation that can be plugged in in place of the
  18 ** default pcache.  This alternative pager cache will throw
  19 ** some errors that the default cache does not.
  20 **
  21 ** This pagecache implementation is designed for simplicity
  22 ** not speed.
  23 */
  24 #include "sqlite3.h"
  25 #include <string.h>
  26 #include <assert.h>
  27
  28 /*
  29 ** Global data used by this test implementation.  There is no
  30 ** mutexing, which means this page cache will not work in a
  31 ** multi-threaded test.
  32 */
  33 typedef struct testpcacheGlobalType testpcacheGlobalType;
  34 struct testpcacheGlobalType {
  35   void *pDummy;             /* Dummy allocation to simulate failures */
  36   int nInstance;            /* Number of current instances */
  37   unsigned discardChance;   /* Chance of discarding on an unpin (0-100) */
  38   unsigned prngSeed;        /* Seed for the PRNG */
  39   unsigned highStress;      /* Call xStress aggressively */
  40 };
  41 static testpcacheGlobalType testpcacheGlobal;
  42
  43 /*
  44 ** Initializer.
  45 **
  46 ** Verify that the initializer is only called when the system is
  47 ** uninitialized.  Allocate some memory and report SQLITE_NOMEM if
  48 ** the allocation fails.  This provides a means to test the recovery
  49 ** from a failed initialization attempt.  It also verifies that the
  50 ** the destructor always gets call - otherwise there would be a
  51 ** memory leak.
  52 */
  53 static int testpcacheInit(void *pArg){
  54   assert( pArg==(void*)&testpcacheGlobal );
  55   assert( testpcacheGlobal.pDummy==0 );
  56   assert( testpcacheGlobal.nInstance==0 );
  57   testpcacheGlobal.pDummy = sqlite3_malloc(10);
  58   return testpcacheGlobal.pDummy==0 ? SQLITE_NOMEM : SQLITE_OK;
  59 }
  60
  61 /*
  62 ** Destructor
  63 **
  64 ** Verify that this is only called after initialization.
  65 ** Free the memory allocated by the initializer.
  66 */
  67 static void testpcacheShutdown(void *pArg){
  68   assert( pArg==(void*)&testpcacheGlobal );
  69   assert( testpcacheGlobal.pDummy!=0 );
  70   assert( testpcacheGlobal.nInstance==0 );
  71   sqlite3_free( testpcacheGlobal.pDummy );
  72   testpcacheGlobal.pDummy = 0;
  73 }
  74
  75 /*
  76 ** Number of pages in a cache.
  77 **
  78 ** The number of pages is a hard upper bound in this test module.
  79 ** If more pages are requested, sqlite3PcacheFetch() returns NULL.
  80 **
  81 ** If testing with in-memory temp tables, provide a larger pcache.
  82 ** Some of the test cases need this.
  83 */
  84 #if defined(SQLITE_TEMP_STORE) && SQLITE_TEMP_STORE>=2
  85 # define TESTPCACHE_NPAGE    499
  86 #else
  87 # define TESTPCACHE_NPAGE    217
  88 #endif
  89 #define TESTPCACHE_RESERVE   17
  90
  91 /*
  92 ** Magic numbers used to determine validity of the page cache.
  93 */
  94 #define TESTPCACHE_VALID  0x364585fd
  95 #define TESTPCACHE_CLEAR  0xd42670d4
  96
  97 /*
  98 ** Private implementation of a page cache.
  99 */
 100 typedef struct testpcache testpcache;
 101 struct testpcache {
 102   sqlite3_int64 szPage;     /* Size of each page.  Multiple of 8. */
 103   int szExtra;              /* Size of extra data that accompanies each page */
 104   int bPurgeable;           /* True if the page cache is purgeable */
 105   int nFree;                /* Number of unused slots in a[] */
 106   int nPinned;              /* Number of pinned slots in a[] */
 107   unsigned iRand;           /* State of the PRNG */
 108   unsigned iMagic;          /* Magic number for sanity checking */
 109   struct testpcachePage {
 110     sqlite3_pcache_page page;  /* Base class */
 111     unsigned key;              /* The key for this page. 0 means unallocated */
 112     int isPinned;              /* True if the page is pinned */
 113   } a[TESTPCACHE_NPAGE];    /* All pages in the cache */
 114 };
 115
 116 /*
 117 ** Get a random number using the PRNG in the given page cache.
 118 */
 119 static unsigned testpcacheRandom(testpcache *p){
 120   unsigned x = 0;
 121   int i;
 122   for(i=0; i<4; i++){
 123     p->iRand = (p->iRand*69069 + 5);
 124     x = (x<<8) | ((p->iRand>>16)&0xff);
 125   }
 126   return x;
 127 }
 128
 129
 130 /*
 131 ** Allocate a new page cache instance.
 132 */
 133 static sqlite3_pcache *testpcacheCreate(
 134   int szPage,
 135   int szExtra,
 136   int bPurgeable
 137 ){
 138   int nMem;
 139   char *x;
 140   testpcache *p;
 141   int i;
 142   assert( testpcacheGlobal.pDummy!=0 );
 143   szPage = (szPage+7)&~7;
 144   szExtra = (szPage+7)&~7;
 145   nMem = sizeof(testpcache) + TESTPCACHE_NPAGE*(szPage+szExtra);
 146   p = sqlite3_malloc( nMem );
 147   if( p==0 ) return 0;
 148   x = (char*)&p[1];
 149   p->szPage = szPage;
 150   p->szExtra = szExtra;
 151   p->nFree = TESTPCACHE_NPAGE;
 152   p->nPinned = 0;
 153   p->iRand = testpcacheGlobal.prngSeed;
 154   p->bPurgeable = bPurgeable;
 155   p->iMagic = TESTPCACHE_VALID;
 156   for(i=0; i<TESTPCACHE_NPAGE; i++, x += (szPage+szExtra)){
 157     p->a[i].key = 0;
 158     p->a[i].isPinned = 0;
 159     p->a[i].page.pBuf = (void*)x;
 160     p->a[i].page.pExtra = (void*)&x[szPage];
 161   }
 162   testpcacheGlobal.nInstance++;
 163   return (sqlite3_pcache*)p;
 164 }
 165
 166 /*
 167 ** Set the cache size
 168 */
 169 static void testpcacheCachesize(sqlite3_pcache *pCache, int newSize){
 170   testpcache *p = (testpcache*)pCache;
 171   assert( p->iMagic==TESTPCACHE_VALID );
 172   assert( testpcacheGlobal.pDummy!=0 );
 173   assert( testpcacheGlobal.nInstance>0 );
 174 }
 175
 176 /*
 177 ** Return the number of pages in the cache that are being used.
 178 ** This includes both pinned and unpinned pages.
 179 */
 180 static int testpcachePagecount(sqlite3_pcache *pCache){
 181   testpcache *p = (testpcache*)pCache;
 182   assert( p->iMagic==TESTPCACHE_VALID );
 183   assert( testpcacheGlobal.pDummy!=0 );
 184   assert( testpcacheGlobal.nInstance>0 );
 185   return TESTPCACHE_NPAGE - p->nFree;
 186 }
 187
 188 /*
 189 ** Fetch a page.
 190 */
 191 static sqlite3_pcache_page *testpcacheFetch(
 192   sqlite3_pcache *pCache,
 193   unsigned key,
 194   int createFlag
 195 ){
 196   testpcache *p = (testpcache*)pCache;
 197   int i, j;
 198   assert( p->iMagic==TESTPCACHE_VALID );
 199   assert( testpcacheGlobal.pDummy!=0 );
 200   assert( testpcacheGlobal.nInstance>0 );
 201
 202   /* See if the page is already in cache.  Return immediately if it is */
 203   for(i=0; i<TESTPCACHE_NPAGE; i++){
 204     if( p->a[i].key==key ){
 205       if( !p->a[i].isPinned ){
 206         p->nPinned++;
 207         assert( p->nPinned <= TESTPCACHE_NPAGE - p->nFree );
 208         p->a[i].isPinned = 1;
 209       }
 210       return &p->a[i].page;
 211     }
 212   }
 213
 214   /* If createFlag is 0, never allocate a new page */
 215   if( createFlag==0 ){
 216     return 0;
 217   }
 218
 219   /* If no pages are available, always fail */
 220   if( p->nPinned==TESTPCACHE_NPAGE ){
 221     return 0;
 222   }
 223
 224   /* Do not allocate the last TESTPCACHE_RESERVE pages unless createFlag is 2 */
 225   if( p->nPinned>=TESTPCACHE_NPAGE-TESTPCACHE_RESERVE && createFlag<2 ){
 226     return 0;
 227   }
 228
 229   /* Do not allocate if highStress is enabled and createFlag is not 2.
 230   **
 231   ** The highStress setting causes pagerStress() to be called much more
 232   ** often, which exercises the pager logic more intensely.
 233   */
 234   if( testpcacheGlobal.highStress && createFlag<2 ){
 235     return 0;
 236   }
 237
 238   /* Find a free page to allocate if there are any free pages.
 239   ** Withhold TESTPCACHE_RESERVE free pages until createFlag is 2.
 240   */
 241   if( p->nFree>TESTPCACHE_RESERVE || (createFlag==2 && p->nFree>0) ){
 242     j = testpcacheRandom(p) % TESTPCACHE_NPAGE;
 243     for(i=0; i<TESTPCACHE_NPAGE; i++, j = (j+1)%TESTPCACHE_NPAGE){
 244       if( p->a[j].key==0 ){
 245         p->a[j].key = key;
 246         p->a[j].isPinned = 1;
 247         memset(p->a[j].page.pBuf, 0, p->szPage);
 248         memset(p->a[j].page.pExtra, 0, p->szExtra);
 249         p->nPinned++;
 250         p->nFree--;
 251         assert( p->nPinned <= TESTPCACHE_NPAGE - p->nFree );
 252         return &p->a[j].page;
 253       }
 254     }
 255
 256     /* The prior loop always finds a freepage to allocate */
 257     assert( 0 );
 258   }
 259
 260   /* If this cache is not purgeable then we have to fail.
 261   */
 262   if( p->bPurgeable==0 ){
 263     return 0;
 264   }
 265
 266   /* If there are no free pages, recycle a page.  The page to
 267   ** recycle is selected at random from all unpinned pages.
 268   */
 269   j = testpcacheRandom(p) % TESTPCACHE_NPAGE;
 270   for(i=0; i<TESTPCACHE_NPAGE; i++, j = (j+1)%TESTPCACHE_NPAGE){
 271     if( p->a[j].key>0 && p->a[j].isPinned==0 ){
 272       p->a[j].key = key;
 273       p->a[j].isPinned = 1;
 274       memset(p->a[j].page.pBuf, 0, p->szPage);
 275       memset(p->a[j].page.pExtra, 0, p->szExtra);
 276       p->nPinned++;
 277       assert( p->nPinned <= TESTPCACHE_NPAGE - p->nFree );
 278       return &p->a[j].page;
 279     }
 280   }
 281
 282   /* The previous loop always finds a page to recycle. */
 283   assert(0);
 284   return 0;
 285 }
 286
 287 /*
 288 ** Unpin a page.
 289 */
 290 static void testpcacheUnpin(
 291   sqlite3_pcache *pCache,
 292   sqlite3_pcache_page *pOldPage,
 293   int discard
 294 ){
 295   testpcache *p = (testpcache*)pCache;
 296   int i;
 297   assert( p->iMagic==TESTPCACHE_VALID );
 298   assert( testpcacheGlobal.pDummy!=0 );
 299   assert( testpcacheGlobal.nInstance>0 );
 300
 301   /* Randomly discard pages as they are unpinned according to the
 302   ** discardChance setting.  If discardChance is 0, the random discard
 303   ** never happens.  If discardChance is 100, it always happens.
 304   */
 305   if( p->bPurgeable
 306   && (100-testpcacheGlobal.discardChance) <= (testpcacheRandom(p)%100)
 307   ){
 308     discard = 1;
 309   }
 310
 311   for(i=0; i<TESTPCACHE_NPAGE; i++){
 312     if( &p->a[i].page==pOldPage ){
 313       /* The pOldPage pointer always points to a pinned page */
 314       assert( p->a[i].isPinned );
 315       p->a[i].isPinned = 0;
 316       p->nPinned--;
 317       assert( p->nPinned>=0 );
 318       if( discard ){
 319         p->a[i].key = 0;
 320         p->nFree++;
 321         assert( p->nFree<=TESTPCACHE_NPAGE );
 322       }
 323       return;
 324     }
 325   }
 326
 327   /* The pOldPage pointer always points to a valid page */
 328   assert( 0 );
 329 }
 330
 331
 332 /*
 333 ** Rekey a single page.
 334 */
 335 static void testpcacheRekey(
 336   sqlite3_pcache *pCache,
 337   sqlite3_pcache_page *pOldPage,
 338   unsigned oldKey,
 339   unsigned newKey
 340 ){
 341   testpcache *p = (testpcache*)pCache;
 342   int i;
 343   assert( p->iMagic==TESTPCACHE_VALID );
 344   assert( testpcacheGlobal.pDummy!=0 );
 345   assert( testpcacheGlobal.nInstance>0 );
 346
 347   /* If there already exists another page at newKey, verify that
 348   ** the other page is unpinned and discard it.
 349   */
 350   for(i=0; i<TESTPCACHE_NPAGE; i++){
 351     if( p->a[i].key==newKey ){
 352       /* The new key is never a page that is already pinned */
 353       assert( p->a[i].isPinned==0 );
 354       p->a[i].key = 0;
 355       p->nFree++;
 356       assert( p->nFree<=TESTPCACHE_NPAGE );
 357       break;
 358     }
 359   }
 360
 361   /* Find the page to be rekeyed and rekey it.
 362   */
 363   for(i=0; i<TESTPCACHE_NPAGE; i++){
 364     if( p->a[i].key==oldKey ){
 365       /* The oldKey and pOldPage parameters match */
 366       assert( &p->a[i].page==pOldPage );
 367       /* Page to be rekeyed must be pinned */
 368       assert( p->a[i].isPinned );
 369       p->a[i].key = newKey;
 370       return;
 371     }
 372   }
 373
 374   /* Rekey is always given a valid page to work with */
 375   assert( 0 );
 376 }
 377
 378
 379 /*
 380 ** Truncate the page cache.  Every page with a key of iLimit or larger
 381 ** is discarded.
 382 */
 383 static void testpcacheTruncate(sqlite3_pcache *pCache, unsigned iLimit){
 384   testpcache *p = (testpcache*)pCache;
 385   unsigned int i;
 386   assert( p->iMagic==TESTPCACHE_VALID );
 387   assert( testpcacheGlobal.pDummy!=0 );
 388   assert( testpcacheGlobal.nInstance>0 );
 389   for(i=0; i<TESTPCACHE_NPAGE; i++){
 390     if( p->a[i].key>=iLimit ){
 391       p->a[i].key = 0;
 392       if( p->a[i].isPinned ){
 393         p->nPinned--;
 394         assert( p->nPinned>=0 );
 395       }
 396       p->nFree++;
 397       assert( p->nFree<=TESTPCACHE_NPAGE );
 398     }
 399   }
 400 }
 401
 402 /*
 403 ** Destroy a page cache.
 404 */
 405 static void testpcacheDestroy(sqlite3_pcache *pCache){
 406   testpcache *p = (testpcache*)pCache;
 407   assert( p->iMagic==TESTPCACHE_VALID );
 408   assert( testpcacheGlobal.pDummy!=0 );
 409   assert( testpcacheGlobal.nInstance>0 );
 410   p->iMagic = TESTPCACHE_CLEAR;
 411   sqlite3_free(p);
 412   testpcacheGlobal.nInstance--;
 413 }
 414
 415
 416 /*
 417 ** Invoke this routine to register or unregister the testing pager cache
 418 ** implemented by this file.
 419 **
 420 ** Install the test pager cache if installFlag is 1 and uninstall it if
 421 ** installFlag is 0.
 422 **
 423 ** When installing, discardChance is a number between 0 and 100 that
 424 ** indicates the probability of discarding a page when unpinning the
 425 ** page.  0 means never discard (unless the discard flag is set).
 426 ** 100 means always discard.
 427 */
 428 void installTestPCache(
 429   int installFlag,            /* True to install.  False to uninstall. */
 430   unsigned discardChance,     /* 0-100.  Chance to discard on unpin */
 431   unsigned prngSeed,          /* Seed for the PRNG */
 432   unsigned highStress         /* Call xStress aggressively */
 433 ){
 434   static const sqlite3_pcache_methods2 testPcache = {
 435     1,
 436     (void*)&testpcacheGlobal,
 437     testpcacheInit,
 438     testpcacheShutdown,
 439     testpcacheCreate,
 440     testpcacheCachesize,
 441     testpcachePagecount,
 442     testpcacheFetch,
 443     testpcacheUnpin,
 444     testpcacheRekey,
 445     testpcacheTruncate,
 446     testpcacheDestroy,
 447   };
 448   static sqlite3_pcache_methods2 defaultPcache;
 449   static int isInstalled = 0;
 450
 451   assert( testpcacheGlobal.nInstance==0 );
 452   assert( testpcacheGlobal.pDummy==0 );
 453   assert( discardChance<=100 );
 454   testpcacheGlobal.discardChance = discardChance;
 455   testpcacheGlobal.prngSeed = prngSeed ^ (prngSeed<<16);
 456   testpcacheGlobal.highStress = highStress;
 457   if( installFlag!=isInstalled ){
 458     if( installFlag ){
 459       sqlite3_config(SQLITE_CONFIG_GETPCACHE2, &defaultPcache);
 460       assert( defaultPcache.xCreate!=testpcacheCreate );
 461       sqlite3_config(SQLITE_CONFIG_PCACHE2, &testPcache);
 462     }else{
 463       assert( defaultPcache.xCreate!=0 );
 464       sqlite3_config(SQLITE_CONFIG_PCACHE2, &defaultPcache);
 465     }
 466     isInstalled = installFlag;
 467   }
 468 }