/ Check-in [e88fc6d0]
Login

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

Overview
Comment:Use the mutex-free PRNG in this branch, since anybody using this branch is probably interested in high concurrency.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | begin-concurrent
Files: files | file ages | folders
SHA3-256: e88fc6d0cd6c470394176e259001a7810eab0a1f56e5feb8cf0b8b3eea870c2d
User & Date: drh 2019-03-26 14:04:43
Wiki:begin-concurrent
Context
2019-04-15
14:59
Merge the latest enhancements from trunk. check-in: 7c328e88 user: drh tags: begin-concurrent
2019-03-26
14:04
Use the mutex-free PRNG in this branch, since anybody using this branch is probably interested in high concurrency. check-in: e88fc6d0 user: drh tags: begin-concurrent
12:07
Merge recent enhancements from trunk. check-in: 774d0d52 user: drh tags: begin-concurrent
2017-09-09
08:03
Use a mutex-free PRNG for the random() and randomblob() SQL functions and for the randomness used during checkpoint operations. Leaf check-in: e63d1a7c user: drh tags: mutex-free-randomness
Changes
Hide Diffs Side-by-Side Diffs Ignore Whitespace Patch

Changes to src/func.c.

   485    485   */
   486    486   static void randomFunc(
   487    487     sqlite3_context *context,
   488    488     int NotUsed,
   489    489     sqlite3_value **NotUsed2
   490    490   ){
   491    491     sqlite_int64 r;
          492  +  sqlite3 *db = sqlite3_context_db_handle(context);
   492    493     UNUSED_PARAMETER2(NotUsed, NotUsed2);
   493         -  sqlite3_randomness(sizeof(r), &r);
          494  +  sqlite3FastRandomness(&db->sPrng, sizeof(r), &r);
   494    495     if( r<0 ){
   495    496       /* We need to prevent a random number of 0x8000000000000000 
   496    497       ** (or -9223372036854775808) since when you do abs() of that
   497    498       ** number of you get the same value back again.  To do this
   498    499       ** in a way that is testable, mask the sign bit off of negative
   499    500       ** values, resulting in a positive value.  Then take the 
   500    501       ** 2s complement of that positive value.  The end result can
................................................................................
   512    513   static void randomBlob(
   513    514     sqlite3_context *context,
   514    515     int argc,
   515    516     sqlite3_value **argv
   516    517   ){
   517    518     sqlite3_int64 n;
   518    519     unsigned char *p;
          520  +  sqlite3 *db = sqlite3_context_db_handle(context);
   519    521     assert( argc==1 );
   520    522     UNUSED_PARAMETER(argc);
   521    523     n = sqlite3_value_int64(argv[0]);
   522    524     if( n<1 ){
   523    525       n = 1;
   524    526     }
   525    527     p = contextMalloc(context, n);
   526    528     if( p ){
   527         -    sqlite3_randomness(n, p);
          529  +    sqlite3FastRandomness(&db->sPrng, n, p);
   528    530       sqlite3_result_blob(context, (char*)p, n, sqlite3_free);
   529    531     }
   530    532   }
   531    533   
   532    534   /*
   533    535   ** Implementation of the last_insert_rowid() SQL function.  The return
   534    536   ** value is the same as the sqlite3_last_insert_rowid() API function.

Changes to src/main.c.

  3064   3064     }
  3065   3065     sqlite3_mutex_enter(db->mutex);
  3066   3066     db->errMask = 0xff;
  3067   3067     db->nDb = 2;
  3068   3068     db->magic = SQLITE_MAGIC_BUSY;
  3069   3069     db->aDb = db->aDbStatic;
  3070   3070     db->lookaside.bDisable = 1;
  3071         -
         3071  +  sqlite3FastPrngInit(&db->sPrng);
  3072   3072     assert( sizeof(db->aLimit)==sizeof(aHardLimit) );
  3073   3073     memcpy(db->aLimit, aHardLimit, sizeof(db->aLimit));
  3074   3074     db->aLimit[SQLITE_LIMIT_WORKER_THREADS] = SQLITE_DEFAULT_WORKER_THREADS;
  3075   3075     db->autoCommit = 1;
  3076   3076     db->nextAutovac = -1;
  3077   3077     db->szMmap = sqlite3GlobalConfig.szMmap;
  3078   3078     db->nextPagesize = 0;

Changes to src/random.c.

   101    101       wsdPrng.s[wsdPrng.i] = wsdPrng.s[wsdPrng.j];
   102    102       wsdPrng.s[wsdPrng.j] = t;
   103    103       t += wsdPrng.s[wsdPrng.i];
   104    104       *(zBuf++) = wsdPrng.s[t];
   105    105     }while( --N );
   106    106     sqlite3_mutex_leave(mutex);
   107    107   }
          108  +
          109  +/*
          110  +** Initialize a fast PRNG.  A Fast PRNG is called "fast" because it does
          111  +** not need a mutex to operate, though it does use a mutex to initialize.
          112  +** The quality of the randomness is not as good as the global PRNG.
          113  +*/
          114  +void sqlite3FastPrngInit(FastPrng *pPrng){
          115  +  sqlite3_randomness(sizeof(*pPrng), pPrng);
          116  +  pPrng->x |= 1;
          117  +}
          118  +
          119  +/*
          120  +** Generate N bytes of pseudo-randomness using a FastPrng
          121  +*/
          122  +void sqlite3FastRandomness(FastPrng *pPrng, int N, void *P){
          123  +  unsigned char *pOut = (unsigned char*)P;
          124  +  while( N-->0 ){
          125  +    pPrng->x = ((pPrng->x)>>1) ^ ((1+~((pPrng->x)&1)) & 0xd0000001);
          126  +    pPrng->y = (pPrng->y)*1103515245 + 12345;
          127  +    *(pOut++) = (pPrng->x ^ pPrng->y) & 0xff;
          128  +  }
          129  +}
   108    130   
   109    131   #ifndef SQLITE_UNTESTABLE
   110    132   /*
   111    133   ** For testing purposes, we sometimes want to preserve the state of
   112    134   ** PRNG and restore the PRNG to its saved state at a later time, or
   113    135   ** to reset the PRNG to its initial state.  These routines accomplish
   114    136   ** those tasks.

Changes to src/select.c.

  1995   1995       while( zName && sqlite3HashFind(&ht, zName)!=0 ){
  1996   1996         nName = sqlite3Strlen30(zName);
  1997   1997         if( nName>0 ){
  1998   1998           for(j=nName-1; j>0 && sqlite3Isdigit(zName[j]); j--){}
  1999   1999           if( zName[j]==':' ) nName = j;
  2000   2000         }
  2001   2001         zName = sqlite3MPrintf(db, "%.*z:%u", nName, zName, ++cnt);
  2002         -      if( cnt>3 ) sqlite3_randomness(sizeof(cnt), &cnt);
         2002  +      if( cnt>3 ) sqlite3FastRandomness(&db->sPrng, sizeof(cnt), &cnt);
  2003   2003       }
  2004   2004       pCol->zName = zName;
  2005   2005       sqlite3ColumnPropertiesFromName(0, pCol);
  2006   2006       if( zName && sqlite3HashInsert(&ht, zName, pCol)==pCol ){
  2007   2007         sqlite3OomFault(db);
  2008   2008       }
  2009   2009     }

Changes to src/sqliteInt.h.

  1068   1068   typedef struct Bitvec Bitvec;
  1069   1069   typedef struct CollSeq CollSeq;
  1070   1070   typedef struct Column Column;
  1071   1071   typedef struct Db Db;
  1072   1072   typedef struct Schema Schema;
  1073   1073   typedef struct Expr Expr;
  1074   1074   typedef struct ExprList ExprList;
         1075  +typedef struct FastPrng FastPrng;
  1075   1076   typedef struct FKey FKey;
  1076   1077   typedef struct FuncDestructor FuncDestructor;
  1077   1078   typedef struct FuncDef FuncDef;
  1078   1079   typedef struct FuncDefHash FuncDefHash;
  1079   1080   typedef struct IdList IdList;
  1080   1081   typedef struct Index Index;
  1081   1082   typedef struct IndexSample IndexSample;
................................................................................
  1184   1185   */
  1185   1186   #ifndef SQLITE_DEFAULT_SYNCHRONOUS
  1186   1187   # define SQLITE_DEFAULT_SYNCHRONOUS 2
  1187   1188   #endif
  1188   1189   #ifndef SQLITE_DEFAULT_WAL_SYNCHRONOUS
  1189   1190   # define SQLITE_DEFAULT_WAL_SYNCHRONOUS SQLITE_DEFAULT_SYNCHRONOUS
  1190   1191   #endif
         1192  +
         1193  +/*
         1194  +** State of a simple PRNG used for the per-connection and per-pager
         1195  +** pseudo-random number generators.
         1196  +*/
         1197  +struct FastPrng {
         1198  +  unsigned int x, y;
         1199  +};
  1191   1200   
  1192   1201   /*
  1193   1202   ** Each database file to be accessed by the system is an instance
  1194   1203   ** of the following structure.  There are normally two of these structures
  1195   1204   ** in the sqlite.aDb[] array.  aDb[0] is the main database file and
  1196   1205   ** aDb[1] is the database file used to hold temporary tables.  Additional
  1197   1206   ** databases may be attached.
................................................................................
  1397   1406     u8 vtabOnConflict;            /* Value to return for s3_vtab_on_conflict() */
  1398   1407     u8 isTransactionSavepoint;    /* True if the outermost savepoint is a TS */
  1399   1408     u8 mTrace;                    /* zero or more SQLITE_TRACE flags */
  1400   1409     u8 noSharedCache;             /* True if no shared-cache backends */
  1401   1410     u8 nSqlExec;                  /* Number of pending OP_SqlExec opcodes */
  1402   1411     int nextPagesize;             /* Pagesize after VACUUM if >0 */
  1403   1412     u32 magic;                    /* Magic number for detect library misuse */
         1413  +  FastPrng sPrng;               /* State of the per-connection PRNG */
  1404   1414     int nChange;                  /* Value returned by sqlite3_changes() */
  1405   1415     int nTotalChange;             /* Value returned by sqlite3_total_changes() */
  1406   1416     int aLimit[SQLITE_N_LIMIT];   /* Limits */
  1407   1417     int nMaxSorterMmap;           /* Maximum size of regions mapped by sorter */
  1408   1418     struct sqlite3InitInfo {      /* Information used during initialization */
  1409   1419       int newTnum;                /* Rootpage of table being initialized */
  1410   1420       u8 iDb;                     /* Which db file is being initialized */
................................................................................
  4023   4033   int sqlite3ExprCoveredByIndex(Expr*, int iCur, Index *pIdx);
  4024   4034   int sqlite3FunctionUsesThisSrc(Expr*, SrcList*);
  4025   4035   Vdbe *sqlite3GetVdbe(Parse*);
  4026   4036   #ifndef SQLITE_UNTESTABLE
  4027   4037   void sqlite3PrngSaveState(void);
  4028   4038   void sqlite3PrngRestoreState(void);
  4029   4039   #endif
         4040  +void sqlite3FastPrngInit(FastPrng*);
         4041  +void sqlite3FastRandomness(FastPrng*, int N, void *P);
  4030   4042   void sqlite3RollbackAll(sqlite3*,int);
  4031   4043   void sqlite3CodeVerifySchema(Parse*, int);
  4032   4044   void sqlite3CodeVerifyNamedSchema(Parse*, const char *zDb);
  4033   4045   void sqlite3BeginTransaction(Parse*, int);
  4034   4046   void sqlite3EndTransaction(Parse*,int);
  4035   4047   void sqlite3Savepoint(Parse*, int, Token*);
  4036   4048   void sqlite3CloseSavepoints(sqlite3 *);

Changes to src/wal.c.

   470    470     u8 bShmUnreliable;         /* SHM content is read-only and unreliable */
   471    471     WalIndexHdr hdr;           /* Wal-index header for current transaction */
   472    472     u32 minFrame;              /* Ignore wal frames before this one */
   473    473     u32 iReCksum;              /* On commit, recalculate checksums from here */
   474    474     u32 nPriorFrame;           /* For sqlite3WalInfo() */
   475    475     const char *zWalName;      /* Name of WAL file */
   476    476     u32 nCkpt;                 /* Checkpoint sequence counter in the wal-header */
          477  +  FastPrng sPrng;            /* Random number generator */
   477    478   #ifdef SQLITE_DEBUG
   478    479     u8 lockError;              /* True if a locking error has occurred */
   479    480   #endif
   480    481   #ifdef SQLITE_ENABLE_SNAPSHOT
   481    482     WalIndexHdr *pSnapshot;    /* Start transaction here if not NULL */
   482    483   #endif
   483    484   };
................................................................................
  1376   1377     pRet->pDbFd = pDbFd;
  1377   1378     pRet->readLock = -1;
  1378   1379     pRet->mxWalSize = mxWalSize;
  1379   1380     pRet->zWalName = zWalName;
  1380   1381     pRet->syncHeader = 1;
  1381   1382     pRet->padToSectorBoundary = 1;
  1382   1383     pRet->exclusiveMode = (bNoShm ? WAL_HEAPMEMORY_MODE: WAL_NORMAL_MODE);
         1384  +  sqlite3FastPrngInit(&pRet->sPrng);
  1383   1385   
  1384   1386     /* Open file handle on the write-ahead log file. */
  1385   1387     flags = (SQLITE_OPEN_READWRITE|SQLITE_OPEN_CREATE|SQLITE_OPEN_WAL);
  1386   1388     rc = sqlite3OsOpen(pVfs, zWalName, pRet->pWalFd, flags, &flags);
  1387   1389     if( rc==SQLITE_OK && flags&SQLITE_OPEN_READONLY ){
  1388   1390       pRet->readOnly = WAL_RDONLY;
  1389   1391     }
................................................................................
  1922   1924     */
  1923   1925     if( rc==SQLITE_OK && eMode!=SQLITE_CHECKPOINT_PASSIVE ){
  1924   1926       assert( pWal->writeLock );
  1925   1927       if( pInfo->nBackfill<pWal->hdr.mxFrame ){
  1926   1928         rc = SQLITE_BUSY;
  1927   1929       }else if( eMode>=SQLITE_CHECKPOINT_RESTART ){
  1928   1930         u32 salt1;
  1929         -      sqlite3_randomness(4, &salt1);
         1931  +      sqlite3FastRandomness(&pWal->sPrng, 4, &salt1);
  1930   1932         assert( pInfo->nBackfill==pWal->hdr.mxFrame );
  1931   1933         rc = walBusyLock(pWal, xBusy, pBusyArg, WAL_READ_LOCK(1), WAL_NREADER-1);
  1932   1934         if( rc==SQLITE_OK ){
  1933   1935           if( eMode==SQLITE_CHECKPOINT_TRUNCATE ){
  1934   1936             /* IMPLEMENTATION-OF: R-44699-57140 This mode works the same way as
  1935   1937             ** SQLITE_CHECKPOINT_RESTART with the addition that it also
  1936   1938             ** truncates the log file to zero bytes just prior to a
................................................................................
  3362   3364     int rc = SQLITE_OK;
  3363   3365   
  3364   3366     if( pWal->readLock==0 ){
  3365   3367       volatile WalCkptInfo *pInfo = walCkptInfo(pWal);
  3366   3368       assert( pInfo->nBackfill==pWal->hdr.mxFrame );
  3367   3369       if( pInfo->nBackfill>0 ){
  3368   3370         u32 salt1;
  3369         -      sqlite3_randomness(4, &salt1);
         3371  +      sqlite3FastRandomness(&pWal->sPrng, 4, &salt1);
  3370   3372         rc = walLockExclusive(pWal, WAL_READ_LOCK(1), WAL_NREADER-1);
  3371   3373         if( rc==SQLITE_OK ){
  3372   3374           /* If all readers are using WAL_READ_LOCK(0) (in other words if no
  3373   3375           ** readers are currently using the WAL), then the transactions
  3374   3376           ** frames will overwrite the start of the existing log. Update the
  3375   3377           ** wal-index header to reflect this.
  3376   3378           **
................................................................................
  3578   3580       u8 aWalHdr[WAL_HDRSIZE];      /* Buffer to assemble wal-header in */
  3579   3581       u32 aCksum[2];                /* Checksum for wal-header */
  3580   3582   
  3581   3583       sqlite3Put4byte(&aWalHdr[0], (WAL_MAGIC | SQLITE_BIGENDIAN));
  3582   3584       sqlite3Put4byte(&aWalHdr[4], WAL_MAX_VERSION);
  3583   3585       sqlite3Put4byte(&aWalHdr[8], szPage);
  3584   3586       sqlite3Put4byte(&aWalHdr[12], pWal->nCkpt);
  3585         -    if( pWal->nCkpt==0 ) sqlite3_randomness(8, pWal->hdr.aSalt);
         3587  +    if( pWal->nCkpt==0 ) sqlite3FastRandomness(&pWal->sPrng, 8, pWal->hdr.aSalt);
  3586   3588       memcpy(&aWalHdr[16], pWal->hdr.aSalt, 8);
  3587   3589       walChecksumBytes(1, aWalHdr, WAL_HDRSIZE-2*4, 0, aCksum);
  3588   3590       sqlite3Put4byte(&aWalHdr[24], aCksum[0]);
  3589   3591       sqlite3Put4byte(&aWalHdr[28], aCksum[1]);
  3590   3592       
  3591   3593       pWal->szPage = szPage;
  3592   3594       pWal->hdr.bigEndCksum = SQLITE_BIGENDIAN;

Changes to test/concurrent2.test.

   339    339   #-------------------------------------------------------------------------
   340    340   # Test that "PRAGMA integrity_check" works within a concurrent 
   341    341   # transaction. Within a concurrent transaction, "PRAGMA integrity_check"
   342    342   # is unable to detect unused database pages, but can detect other types
   343    343   # of corruption.
   344    344   #
   345    345   reset_db
   346         -do_execsql_test 8.1 {
   347         -  PRAGMA journal_mode = wal;
   348         -  CREATE TABLE kv(k INTEGER PRIMARY KEY, v UNIQUE);
   349         -  INSERT INTO kv VALUES(NULL, randomblob(750));
   350         -  INSERT INTO kv SELECT NULL, randomblob(750) FROM kv;
   351         -  INSERT INTO kv SELECT NULL, randomblob(750) FROM kv;
   352         -  INSERT INTO kv SELECT NULL, randomblob(750) FROM kv;
   353         -  INSERT INTO kv SELECT NULL, randomblob(750) FROM kv;
   354         -  INSERT INTO kv SELECT NULL, randomblob(750) FROM kv;
   355         -  DELETE FROM kv WHERE rowid%2;
   356         -  PRAGMA freelist_count;
   357         -} {wal 34}
          346  +do_test 8.1 {
          347  +  execsql {
          348  +    PRAGMA journal_mode = wal;
          349  +    CREATE TABLE kv(k INTEGER PRIMARY KEY, v UNIQUE);
          350  +    INSERT INTO kv VALUES(NULL, randomblob(750));
          351  +    INSERT INTO kv SELECT NULL, randomblob(750) FROM kv;
          352  +    INSERT INTO kv SELECT NULL, randomblob(750) FROM kv;
          353  +    INSERT INTO kv SELECT NULL, randomblob(750) FROM kv;
          354  +    INSERT INTO kv SELECT NULL, randomblob(750) FROM kv;
          355  +    INSERT INTO kv SELECT NULL, randomblob(750) FROM kv;
          356  +    DELETE FROM kv WHERE rowid%2;
          357  +  }
          358  +  set v [db one {PRAGMA freelist_count}]
          359  +  expr $v==33 || $v==34
          360  +} {1}
   358    361   do_execsql_test 8.2 { PRAGMA integrity_check } ok
   359    362   do_execsql_test 8.3 { 
   360    363     BEGIN CONCURRENT;
   361    364       PRAGMA integrity_check;
   362    365   } {ok}
   363    366   do_execsql_test 8.4 { 
   364    367       INSERT INTO kv VALUES(1100, 1100);