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