third_party/sqlite/sqlite-src-3080704/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 agressively */
  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   int 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   nMem = sizeof(testpcache) + TESTPCACHE_NPAGE*(szPage+szExtra);
 145   p = sqlite3_malloc( nMem );
 146   if( p==0 ) return 0;
 147   x = (char*)&p[1];
 148   p->szPage = szPage;
 149   p->szExtra = szExtra;
 150   p->nFree = TESTPCACHE_NPAGE;
 151   p->nPinned = 0;
 152   p->iRand = testpcacheGlobal.prngSeed;
 153   p->bPurgeable = bPurgeable;
 154   p->iMagic = TESTPCACHE_VALID;
 155   for(i=0; i<TESTPCACHE_NPAGE; i++, x += (szPage+szExtra)){
 156     p->a[i].key = 0;
 157     p->a[i].isPinned = 0;
 158     p->a[i].page.pBuf = (void*)x;
 159     p->a[i].page.pExtra = (void*)&x[szPage];
 160   }
 161   testpcacheGlobal.nInstance++;
 162   return (sqlite3_pcache*)p;
 163 }
 164
 165 /*
 166 ** Set the cache size
 167 */
 168 static void testpcacheCachesize(sqlite3_pcache *pCache, int newSize){
 169   testpcache *p = (testpcache*)pCache;
 170   assert( p->iMagic==TESTPCACHE_VALID );
 171   assert( testpcacheGlobal.pDummy!=0 );
 172   assert( testpcacheGlobal.nInstance>0 );
 173 }
 174
 175 /*
 176 ** Return the number of pages in the cache that are being used.
 177 ** This includes both pinned and unpinned pages.
 178 */
 179 static int testpcachePagecount(sqlite3_pcache *pCache){
 180   testpcache *p = (testpcache*)pCache;
 181   assert( p->iMagic==TESTPCACHE_VALID );
 182   assert( testpcacheGlobal.pDummy!=0 );
 183   assert( testpcacheGlobal.nInstance>0 );
 184   return TESTPCACHE_NPAGE - p->nFree;
 185 }
 186
 187 /*
 188 ** Fetch a page.
 189 */
 190 static sqlite3_pcache_page *testpcacheFetch(
 191   sqlite3_pcache *pCache,
 192   unsigned key,
 193   int createFlag
 194 ){
 195   testpcache *p = (testpcache*)pCache;
 196   int i, j;
 197   assert( p->iMagic==TESTPCACHE_VALID );
 198   assert( testpcacheGlobal.pDummy!=0 );
 199   assert( testpcacheGlobal.nInstance>0 );
 200
 201   /* See if the page is already in cache.  Return immediately if it is */
 202   for(i=0; i<TESTPCACHE_NPAGE; i++){
 203     if( p->a[i].key==key ){
 204       if( !p->a[i].isPinned ){
 205         p->nPinned++;
 206         assert( p->nPinned <= TESTPCACHE_NPAGE - p->nFree );
 207         p->a[i].isPinned = 1;
 208       }
 209       return &p->a[i].page;
 210     }
 211   }
 212
 213   /* If createFlag is 0, never allocate a new page */
 214   if( createFlag==0 ){
 215     return 0;
 216   }
 217
 218   /* If no pages are available, always fail */
 219   if( p->nPinned==TESTPCACHE_NPAGE ){
 220     return 0;
 221   }
 222
 223   /* Do not allocate the last TESTPCACHE_RESERVE pages unless createFlag is 2 */
 224   if( p->nPinned>=TESTPCACHE_NPAGE-TESTPCACHE_RESERVE && createFlag<2 ){
 225     return 0;
 226   }
 227
 228   /* Do not allocate if highStress is enabled and createFlag is not 2.
 229   **
 230   ** The highStress setting causes pagerStress() to be called much more
 231   ** often, which exercises the pager logic more intensely.
 232   */
 233   if( testpcacheGlobal.highStress && createFlag<2 ){
 234     return 0;
 235   }
 236
 237   /* Find a free page to allocate if there are any free pages.
 238   ** Withhold TESTPCACHE_RESERVE free pages until createFlag is 2.
 239   */
 240   if( p->nFree>TESTPCACHE_RESERVE || (createFlag==2 && p->nFree>0) ){
 241     j = testpcacheRandom(p) % TESTPCACHE_NPAGE;
 242     for(i=0; i<TESTPCACHE_NPAGE; i++, j = (j+1)%TESTPCACHE_NPAGE){
 243       if( p->a[j].key==0 ){
 244         p->a[j].key = key;
 245         p->a[j].isPinned = 1;
 246         memset(p->a[j].page.pBuf, 0, p->szPage);
 247         memset(p->a[j].page.pExtra, 0, p->szExtra);
 248         p->nPinned++;
 249         p->nFree--;
 250         assert( p->nPinned <= TESTPCACHE_NPAGE - p->nFree );
 251         return &p->a[j].page;
 252       }
 253     }
 254
 255     /* The prior loop always finds a freepage to allocate */
 256     assert( 0 );
 257   }
 258
 259   /* If this cache is not purgeable then we have to fail.
 260   */
 261   if( p->bPurgeable==0 ){
 262     return 0;
 263   }
 264
 265   /* If there are no free pages, recycle a page.  The page to
 266   ** recycle is selected at random from all unpinned pages.
 267   */
 268   j = testpcacheRandom(p) % TESTPCACHE_NPAGE;
 269   for(i=0; i<TESTPCACHE_NPAGE; i++, j = (j+1)%TESTPCACHE_NPAGE){
 270     if( p->a[j].key>0 && p->a[j].isPinned==0 ){
 271       p->a[j].key = key;
 272       p->a[j].isPinned = 1;
 273       memset(p->a[j].page.pBuf, 0, p->szPage);
 274       memset(p->a[j].page.pExtra, 0, p->szExtra);
 275       p->nPinned++;
 276       assert( p->nPinned <= TESTPCACHE_NPAGE - p->nFree );
 277       return &p->a[j].page;
 278     }
 279   }
 280
 281   /* The previous loop always finds a page to recycle. */
 282   assert(0);
 283   return 0;
 284 }
 285
 286 /*
 287 ** Unpin a page.
 288 */
 289 static void testpcacheUnpin(
 290   sqlite3_pcache *pCache,
 291   sqlite3_pcache_page *pOldPage,
 292   int discard
 293 ){
 294   testpcache *p = (testpcache*)pCache;
 295   int i;
 296   assert( p->iMagic==TESTPCACHE_VALID );
 297   assert( testpcacheGlobal.pDummy!=0 );
 298   assert( testpcacheGlobal.nInstance>0 );
 299
 300   /* Randomly discard pages as they are unpinned according to the
 301   ** discardChance setting.  If discardChance is 0, the random discard
 302   ** never happens.  If discardChance is 100, it always happens.
 303   */
 304   if( p->bPurgeable
 305   && (100-testpcacheGlobal.discardChance) <= (testpcacheRandom(p)%100)
 306   ){
 307     discard = 1;
 308   }
 309
 310   for(i=0; i<TESTPCACHE_NPAGE; i++){
 311     if( &p->a[i].page==pOldPage ){
 312       /* The pOldPage pointer always points to a pinned page */
 313       assert( p->a[i].isPinned );
 314       p->a[i].isPinned = 0;
 315       p->nPinned--;
 316       assert( p->nPinned>=0 );
 317       if( discard ){
 318         p->a[i].key = 0;
 319         p->nFree++;
 320         assert( p->nFree<=TESTPCACHE_NPAGE );
 321       }
 322       return;
 323     }
 324   }
 325
 326   /* The pOldPage pointer always points to a valid page */
 327   assert( 0 );
 328 }
 329
 330
 331 /*
 332 ** Rekey a single page.
 333 */
 334 static void testpcacheRekey(
 335   sqlite3_pcache *pCache,
 336   sqlite3_pcache_page *pOldPage,
 337   unsigned oldKey,
 338   unsigned newKey
 339 ){
 340   testpcache *p = (testpcache*)pCache;
 341   int i;
 342   assert( p->iMagic==TESTPCACHE_VALID );
 343   assert( testpcacheGlobal.pDummy!=0 );
 344   assert( testpcacheGlobal.nInstance>0 );
 345
 346   /* If there already exists another page at newKey, verify that
 347   ** the other page is unpinned and discard it.
 348   */
 349   for(i=0; i<TESTPCACHE_NPAGE; i++){
 350     if( p->a[i].key==newKey ){
 351       /* The new key is never a page that is already pinned */
 352       assert( p->a[i].isPinned==0 );
 353       p->a[i].key = 0;
 354       p->nFree++;
 355       assert( p->nFree<=TESTPCACHE_NPAGE );
 356       break;
 357     }
 358   }
 359
 360   /* Find the page to be rekeyed and rekey it.
 361   */
 362   for(i=0; i<TESTPCACHE_NPAGE; i++){
 363     if( p->a[i].key==oldKey ){
 364       /* The oldKey and pOldPage parameters match */
 365       assert( &p->a[i].page==pOldPage );
 366       /* Page to be rekeyed must be pinned */
 367       assert( p->a[i].isPinned );
 368       p->a[i].key = newKey;
 369       return;
 370     }
 371   }
 372
 373   /* Rekey is always given a valid page to work with */
 374   assert( 0 );
 375 }
 376
 377
 378 /*
 379 ** Truncate the page cache.  Every page with a key of iLimit or larger
 380 ** is discarded.
 381 */
 382 static void testpcacheTruncate(sqlite3_pcache *pCache, unsigned iLimit){
 383   testpcache *p = (testpcache*)pCache;
 384   unsigned int i;
 385   assert( p->iMagic==TESTPCACHE_VALID );
 386   assert( testpcacheGlobal.pDummy!=0 );
 387   assert( testpcacheGlobal.nInstance>0 );
 388   for(i=0; i<TESTPCACHE_NPAGE; i++){
 389     if( p->a[i].key>=iLimit ){
 390       p->a[i].key = 0;
 391       if( p->a[i].isPinned ){
 392         p->nPinned--;
 393         assert( p->nPinned>=0 );
 394       }
 395       p->nFree++;
 396       assert( p->nFree<=TESTPCACHE_NPAGE );
 397     }
 398   }
 399 }
 400
 401 /*
 402 ** Destroy a page cache.
 403 */
 404 static void testpcacheDestroy(sqlite3_pcache *pCache){
 405   testpcache *p = (testpcache*)pCache;
 406   assert( p->iMagic==TESTPCACHE_VALID );
 407   assert( testpcacheGlobal.pDummy!=0 );
 408   assert( testpcacheGlobal.nInstance>0 );
 409   p->iMagic = TESTPCACHE_CLEAR;
 410   sqlite3_free(p);
 411   testpcacheGlobal.nInstance--;
 412 }
 413
 414
 415 /*
 416 ** Invoke this routine to register or unregister the testing pager cache
 417 ** implemented by this file.
 418 **
 419 ** Install the test pager cache if installFlag is 1 and uninstall it if
 420 ** installFlag is 0.
 421 **
 422 ** When installing, discardChance is a number between 0 and 100 that
 423 ** indicates the probability of discarding a page when unpinning the
 424 ** page.  0 means never discard (unless the discard flag is set).
 425 ** 100 means always discard.
 426 */
 427 void installTestPCache(
 428   int installFlag,            /* True to install.  False to uninstall. */
 429   unsigned discardChance,     /* 0-100.  Chance to discard on unpin */
 430   unsigned prngSeed,          /* Seed for the PRNG */
 431   unsigned highStress         /* Call xStress agressively */
 432 ){
 433   static const sqlite3_pcache_methods2 testPcache = {
 434     1,
 435     (void*)&testpcacheGlobal,
 436     testpcacheInit,
 437     testpcacheShutdown,
 438     testpcacheCreate,
 439     testpcacheCachesize,
 440     testpcachePagecount,
 441     testpcacheFetch,
 442     testpcacheUnpin,
 443     testpcacheRekey,
 444     testpcacheTruncate,
 445     testpcacheDestroy,
 446   };
 447   static sqlite3_pcache_methods2 defaultPcache;
 448   static int isInstalled = 0;
 449
 450   assert( testpcacheGlobal.nInstance==0 );
 451   assert( testpcacheGlobal.pDummy==0 );
 452   assert( discardChance<=100 );
 453   testpcacheGlobal.discardChance = discardChance;
 454   testpcacheGlobal.prngSeed = prngSeed ^ (prngSeed<<16);
 455   testpcacheGlobal.highStress = highStress;
 456   if( installFlag!=isInstalled ){
 457     if( installFlag ){
 458       sqlite3_config(SQLITE_CONFIG_GETPCACHE2, &defaultPcache);
 459       assert( defaultPcache.xCreate!=testpcacheCreate );
 460       sqlite3_config(SQLITE_CONFIG_PCACHE2, &testPcache);
 461     }else{
 462       assert( defaultPcache.xCreate!=0 );
 463       sqlite3_config(SQLITE_CONFIG_PCACHE2, &defaultPcache);
 464     }
 465     isInstalled = installFlag;
 466   }
 467 }