/ Check-in [e63d1a7c]
Login

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

Overview
Comment:Use a mutex-free PRNG for the random() and randomblob() SQL functions and for the randomness used during checkpoint operations.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | mutex-free-randomness
Files: files | file ages | folders
SHA3-256:e63d1a7cd317811f74d206ae47bd11a8fc6b6311218fbc6d0cbf49e8281b362f
User & Date: drh 2017-09-09 08:03:28
Context
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
2017-09-12
18:11
Merge the mutex-free PRNG change into this branch. check-in: 8b1fc4b9 user: dan tags: shared-mapping-hack
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
00:51
Fix harmless compiler warnings seen with MSVC. check-in: faa22e29 user: mistachkin tags: trunk
Changes
Hide Diffs Side-by-Side Diffs Ignore Whitespace Patch

Changes to src/func.c.

   477    477   */
   478    478   static void randomFunc(
   479    479     sqlite3_context *context,
   480    480     int NotUsed,
   481    481     sqlite3_value **NotUsed2
   482    482   ){
   483    483     sqlite_int64 r;
          484  +  sqlite3 *db = sqlite3_context_db_handle(context);
   484    485     UNUSED_PARAMETER2(NotUsed, NotUsed2);
   485         -  sqlite3_randomness(sizeof(r), &r);
          486  +  sqlite3FastRandomness(&db->sPrng, sizeof(r), &r);
   486    487     if( r<0 ){
   487    488       /* We need to prevent a random number of 0x8000000000000000 
   488    489       ** (or -9223372036854775808) since when you do abs() of that
   489    490       ** number of you get the same value back again.  To do this
   490    491       ** in a way that is testable, mask the sign bit off of negative
   491    492       ** values, resulting in a positive value.  Then take the 
   492    493       ** 2s complement of that positive value.  The end result can
................................................................................
   504    505   static void randomBlob(
   505    506     sqlite3_context *context,
   506    507     int argc,
   507    508     sqlite3_value **argv
   508    509   ){
   509    510     int n;
   510    511     unsigned char *p;
          512  +  sqlite3 *db = sqlite3_context_db_handle(context);
   511    513     assert( argc==1 );
   512    514     UNUSED_PARAMETER(argc);
   513    515     n = sqlite3_value_int(argv[0]);
   514    516     if( n<1 ){
   515    517       n = 1;
   516    518     }
   517    519     p = contextMalloc(context, n);
   518    520     if( p ){
   519         -    sqlite3_randomness(n, p);
          521  +    sqlite3FastRandomness(&db->sPrng, n, p);
   520    522       sqlite3_result_blob(context, (char*)p, n, sqlite3_free);
   521    523     }
   522    524   }
   523    525   
   524    526   /*
   525    527   ** Implementation of the last_insert_rowid() SQL function.  The return
   526    528   ** value is the same as the sqlite3_last_insert_rowid() API function.

Changes to src/main.c.

  2861   2861       }
  2862   2862     }
  2863   2863     sqlite3_mutex_enter(db->mutex);
  2864   2864     db->errMask = 0xff;
  2865   2865     db->nDb = 2;
  2866   2866     db->magic = SQLITE_MAGIC_BUSY;
  2867   2867     db->aDb = db->aDbStatic;
         2868  +  sqlite3FastPrngInit(&db->sPrng);
  2868   2869   
  2869   2870     assert( sizeof(db->aLimit)==sizeof(aHardLimit) );
  2870   2871     memcpy(db->aLimit, aHardLimit, sizeof(db->aLimit));
  2871   2872     db->aLimit[SQLITE_LIMIT_WORKER_THREADS] = SQLITE_DEFAULT_WORKER_THREADS;
  2872   2873     db->autoCommit = 1;
  2873   2874     db->nextAutovac = -1;
  2874   2875     db->szMmap = sqlite3GlobalConfig.szMmap;

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.

  1741   1741       while( zName && sqlite3HashFind(&ht, zName)!=0 ){
  1742   1742         nName = sqlite3Strlen30(zName);
  1743   1743         if( nName>0 ){
  1744   1744           for(j=nName-1; j>0 && sqlite3Isdigit(zName[j]); j--){}
  1745   1745           if( zName[j]==':' ) nName = j;
  1746   1746         }
  1747   1747         zName = sqlite3MPrintf(db, "%.*z:%u", nName, zName, ++cnt);
  1748         -      if( cnt>3 ) sqlite3_randomness(sizeof(cnt), &cnt);
         1748  +      if( cnt>3 ) sqlite3FastRandomness(&db->sPrng, sizeof(cnt), &cnt);
  1749   1749       }
  1750   1750       pCol->zName = zName;
  1751   1751       sqlite3ColumnPropertiesFromName(0, pCol);
  1752   1752       if( zName && sqlite3HashInsert(&ht, zName, pCol)==pCol ){
  1753   1753         sqlite3OomFault(db);
  1754   1754       }
  1755   1755     }

Changes to src/sqliteInt.h.

  1069   1069   typedef struct Lookaside Lookaside;
  1070   1070   typedef struct LookasideSlot LookasideSlot;
  1071   1071   typedef struct Module Module;
  1072   1072   typedef struct NameContext NameContext;
  1073   1073   typedef struct Parse Parse;
  1074   1074   typedef struct PreUpdate PreUpdate;
  1075   1075   typedef struct PrintfArguments PrintfArguments;
         1076  +typedef struct FastPrng FastPrng;
  1076   1077   typedef struct RowSet RowSet;
  1077   1078   typedef struct Savepoint Savepoint;
  1078   1079   typedef struct Select Select;
  1079   1080   typedef struct SQLiteThread SQLiteThread;
  1080   1081   typedef struct SelectDest SelectDest;
  1081   1082   typedef struct SrcList SrcList;
  1082   1083   typedef struct StrAccum StrAccum;
................................................................................
  1140   1141   */
  1141   1142   #ifndef SQLITE_DEFAULT_SYNCHRONOUS
  1142   1143   # define SQLITE_DEFAULT_SYNCHRONOUS 2
  1143   1144   #endif
  1144   1145   #ifndef SQLITE_DEFAULT_WAL_SYNCHRONOUS
  1145   1146   # define SQLITE_DEFAULT_WAL_SYNCHRONOUS SQLITE_DEFAULT_SYNCHRONOUS
  1146   1147   #endif
         1148  +
         1149  +/*
         1150  +** State of a simple PRNG used for the per-connection and per-pager
         1151  +** pseudo-random number generators.
         1152  +*/
         1153  +struct FastPrng {
         1154  +  unsigned int x, y;
         1155  +};
  1147   1156   
  1148   1157   /*
  1149   1158   ** Each database file to be accessed by the system is an instance
  1150   1159   ** of the following structure.  There are normally two of these structures
  1151   1160   ** in the sqlite.aDb[] array.  aDb[0] is the main database file and
  1152   1161   ** aDb[1] is the database file used to hold temporary tables.  Additional
  1153   1162   ** databases may be attached.
................................................................................
  1347   1356     u8 vtabOnConflict;            /* Value to return for s3_vtab_on_conflict() */
  1348   1357     u8 isTransactionSavepoint;    /* True if the outermost savepoint is a TS */
  1349   1358     u8 mTrace;                    /* zero or more SQLITE_TRACE flags */
  1350   1359     u8 skipBtreeMutex;            /* True if no shared-cache backends */
  1351   1360     u8 nSqlExec;                  /* Number of pending OP_SqlExec opcodes */
  1352   1361     int nextPagesize;             /* Pagesize after VACUUM if >0 */
  1353   1362     u32 magic;                    /* Magic number for detect library misuse */
         1363  +  FastPrng sPrng;               /* State of the per-connection PRNG */
  1354   1364     int nChange;                  /* Value returned by sqlite3_changes() */
  1355   1365     int nTotalChange;             /* Value returned by sqlite3_total_changes() */
  1356   1366     int aLimit[SQLITE_N_LIMIT];   /* Limits */
  1357   1367     int nMaxSorterMmap;           /* Maximum size of regions mapped by sorter */
  1358   1368     struct sqlite3InitInfo {      /* Information used during initialization */
  1359   1369       int newTnum;                /* Rootpage of table being initialized */
  1360   1370       u8 iDb;                     /* Which db file is being initialized */
................................................................................
  3817   3827   int sqlite3ExprCoveredByIndex(Expr*, int iCur, Index *pIdx);
  3818   3828   int sqlite3FunctionUsesThisSrc(Expr*, SrcList*);
  3819   3829   Vdbe *sqlite3GetVdbe(Parse*);
  3820   3830   #ifndef SQLITE_UNTESTABLE
  3821   3831   void sqlite3PrngSaveState(void);
  3822   3832   void sqlite3PrngRestoreState(void);
  3823   3833   #endif
         3834  +void sqlite3FastPrngInit(FastPrng*);
         3835  +void sqlite3FastRandomness(FastPrng*, int N, void *P);
  3824   3836   void sqlite3RollbackAll(sqlite3*,int);
  3825   3837   void sqlite3CodeVerifySchema(Parse*, int);
  3826   3838   void sqlite3CodeVerifyNamedSchema(Parse*, const char *zDb);
  3827   3839   void sqlite3BeginTransaction(Parse*, int);
  3828   3840   void sqlite3EndTransaction(Parse*,int);
  3829   3841   void sqlite3Savepoint(Parse*, int, Token*);
  3830   3842   void sqlite3CloseSavepoints(sqlite3 *);

Changes to src/wal.c.

   444    444     u8 syncHeader;             /* Fsync the WAL header if true */
   445    445     u8 padToSectorBoundary;    /* Pad transactions out to the next sector */
   446    446     WalIndexHdr hdr;           /* Wal-index header for current transaction */
   447    447     u32 minFrame;              /* Ignore wal frames before this one */
   448    448     u32 iReCksum;              /* On commit, recalculate checksums from here */
   449    449     const char *zWalName;      /* Name of WAL file */
   450    450     u32 nCkpt;                 /* Checkpoint sequence counter in the wal-header */
          451  +  FastPrng sPrng;            /* Random number generator */
   451    452   #ifdef SQLITE_DEBUG
   452    453     u8 lockError;              /* True if a locking error has occurred */
   453    454   #endif
   454    455   #ifdef SQLITE_ENABLE_SNAPSHOT
   455    456     WalIndexHdr *pSnapshot;    /* Start transaction here if not NULL */
   456    457   #endif
   457    458   };
................................................................................
  1319   1320     pRet->pDbFd = pDbFd;
  1320   1321     pRet->readLock = -1;
  1321   1322     pRet->mxWalSize = mxWalSize;
  1322   1323     pRet->zWalName = zWalName;
  1323   1324     pRet->syncHeader = 1;
  1324   1325     pRet->padToSectorBoundary = 1;
  1325   1326     pRet->exclusiveMode = (bNoShm ? WAL_HEAPMEMORY_MODE: WAL_NORMAL_MODE);
         1327  +  sqlite3FastPrngInit(&pRet->sPrng);
  1326   1328   
  1327   1329     /* Open file handle on the write-ahead log file. */
  1328   1330     flags = (SQLITE_OPEN_READWRITE|SQLITE_OPEN_CREATE|SQLITE_OPEN_WAL);
  1329   1331     rc = sqlite3OsOpen(pVfs, zWalName, pRet->pWalFd, flags, &flags);
  1330   1332     if( rc==SQLITE_OK && flags&SQLITE_OPEN_READONLY ){
  1331   1333       pRet->readOnly = WAL_RDONLY;
  1332   1334     }
................................................................................
  1866   1868     */
  1867   1869     if( rc==SQLITE_OK && eMode!=SQLITE_CHECKPOINT_PASSIVE ){
  1868   1870       assert( pWal->writeLock );
  1869   1871       if( pInfo->nBackfill<pWal->hdr.mxFrame ){
  1870   1872         rc = SQLITE_BUSY;
  1871   1873       }else if( eMode>=SQLITE_CHECKPOINT_RESTART ){
  1872   1874         u32 salt1;
  1873         -      sqlite3_randomness(4, &salt1);
         1875  +      sqlite3FastRandomness(&pWal->sPrng, 4, &salt1);
  1874   1876         assert( pInfo->nBackfill==pWal->hdr.mxFrame );
  1875   1877         rc = walBusyLock(pWal, xBusy, pBusyArg, WAL_READ_LOCK(1), WAL_NREADER-1);
  1876   1878         if( rc==SQLITE_OK ){
  1877   1879           if( eMode==SQLITE_CHECKPOINT_TRUNCATE ){
  1878   1880             /* IMPLEMENTATION-OF: R-44699-57140 This mode works the same way as
  1879   1881             ** SQLITE_CHECKPOINT_RESTART with the addition that it also
  1880   1882             ** truncates the log file to zero bytes just prior to a
................................................................................
  2874   2876     int cnt;
  2875   2877   
  2876   2878     if( pWal->readLock==0 ){
  2877   2879       volatile WalCkptInfo *pInfo = walCkptInfo(pWal);
  2878   2880       assert( pInfo->nBackfill==pWal->hdr.mxFrame );
  2879   2881       if( pInfo->nBackfill>0 ){
  2880   2882         u32 salt1;
  2881         -      sqlite3_randomness(4, &salt1);
         2883  +      sqlite3FastRandomness(&pWal->sPrng, 4, &salt1);
  2882   2884         rc = walLockExclusive(pWal, WAL_READ_LOCK(1), WAL_NREADER-1);
  2883   2885         if( rc==SQLITE_OK ){
  2884   2886           /* If all readers are using WAL_READ_LOCK(0) (in other words if no
  2885   2887           ** readers are currently using the WAL), then the transactions
  2886   2888           ** frames will overwrite the start of the existing log. Update the
  2887   2889           ** wal-index header to reflect this.
  2888   2890           **
................................................................................
  3090   3092       u8 aWalHdr[WAL_HDRSIZE];      /* Buffer to assemble wal-header in */
  3091   3093       u32 aCksum[2];                /* Checksum for wal-header */
  3092   3094   
  3093   3095       sqlite3Put4byte(&aWalHdr[0], (WAL_MAGIC | SQLITE_BIGENDIAN));
  3094   3096       sqlite3Put4byte(&aWalHdr[4], WAL_MAX_VERSION);
  3095   3097       sqlite3Put4byte(&aWalHdr[8], szPage);
  3096   3098       sqlite3Put4byte(&aWalHdr[12], pWal->nCkpt);
  3097         -    if( pWal->nCkpt==0 ) sqlite3_randomness(8, pWal->hdr.aSalt);
         3099  +    if( pWal->nCkpt==0 ) sqlite3FastRandomness(&pWal->sPrng, 8, pWal->hdr.aSalt);
  3098   3100       memcpy(&aWalHdr[16], pWal->hdr.aSalt, 8);
  3099   3101       walChecksumBytes(1, aWalHdr, WAL_HDRSIZE-2*4, 0, aCksum);
  3100   3102       sqlite3Put4byte(&aWalHdr[24], aCksum[0]);
  3101   3103       sqlite3Put4byte(&aWalHdr[28], aCksum[1]);
  3102   3104       
  3103   3105       pWal->szPage = szPage;
  3104   3106       pWal->hdr.bigEndCksum = SQLITE_BIGENDIAN;