diff options
Diffstat (limited to 'src')
41 files changed, 522 insertions, 433 deletions
diff --git a/src/backend/access/gin/ginget.c b/src/backend/access/gin/ginget.c index 03191e016c..e93bf29999 100644 --- a/src/backend/access/gin/ginget.c +++ b/src/backend/access/gin/ginget.c @@ -16,6 +16,7 @@ #include "access/gin_private.h" #include "access/relscan.h" +#include "common/pg_prng.h" #include "miscadmin.h" #include "storage/predicate.h" #include "utils/datum.h" @@ -787,7 +788,7 @@ entryLoadMoreItems(GinState *ginstate, GinScanEntry entry, } } -#define gin_rand() (((double) random()) / ((double) MAX_RANDOM_VALUE)) +#define gin_rand() pg_prng_double(&pg_global_prng_state) #define dropItem(e) ( gin_rand() > ((double)GinFuzzySearchLimit)/((double)((e)->predictNumberResult)) ) /* diff --git a/src/backend/access/gist/gistutil.c b/src/backend/access/gist/gistutil.c index 43ba03b6eb..94dbabc198 100644 --- a/src/backend/access/gist/gistutil.c +++ b/src/backend/access/gist/gistutil.c @@ -19,6 +19,7 @@ #include "access/htup_details.h" #include "access/reloptions.h" #include "catalog/pg_opclass.h" +#include "common/pg_prng.h" #include "storage/indexfsm.h" #include "storage/lmgr.h" #include "utils/float.h" @@ -507,7 +508,7 @@ gistchoose(Relation r, Page p, IndexTuple it, /* it has compressed entry */ if (keep_current_best == -1) { /* we didn't make the random choice yet for this old best */ - keep_current_best = (random() <= (MAX_RANDOM_VALUE / 2)) ? 1 : 0; + keep_current_best = pg_prng_bool(&pg_global_prng_state) ? 1 : 0; } if (keep_current_best == 0) { @@ -529,7 +530,7 @@ gistchoose(Relation r, Page p, IndexTuple it, /* it has compressed entry */ if (keep_current_best == -1) { /* we didn't make the random choice yet for this old best */ - keep_current_best = (random() <= (MAX_RANDOM_VALUE / 2)) ? 1 : 0; + keep_current_best = pg_prng_bool(&pg_global_prng_state) ? 1 : 0; } if (keep_current_best == 1) break; diff --git a/src/backend/access/nbtree/nbtinsert.c b/src/backend/access/nbtree/nbtinsert.c index 0fe8c70939..37ee0b4d6e 100644 --- a/src/backend/access/nbtree/nbtinsert.c +++ b/src/backend/access/nbtree/nbtinsert.c @@ -19,6 +19,7 @@ #include "access/nbtxlog.h" #include "access/transam.h" #include "access/xloginsert.h" +#include "common/pg_prng.h" #include "lib/qunique.h" #include "miscadmin.h" #include "storage/lmgr.h" @@ -965,7 +966,7 @@ _bt_findinsertloc(Relation rel, if (P_RIGHTMOST(opaque) || _bt_compare(rel, itup_key, page, P_HIKEY) != 0 || - random() <= (MAX_RANDOM_VALUE / 100)) + pg_prng_uint32(&pg_global_prng_state) <= (PG_UINT32_MAX / 100)) break; _bt_stepright(rel, insertstate, stack); diff --git a/src/backend/access/spgist/spgdoinsert.c b/src/backend/access/spgist/spgdoinsert.c index 70557bcf3d..e7afb2c242 100644 --- a/src/backend/access/spgist/spgdoinsert.c +++ b/src/backend/access/spgist/spgdoinsert.c @@ -19,6 +19,7 @@ #include "access/spgist_private.h" #include "access/spgxlog.h" #include "access/xloginsert.h" +#include "common/pg_prng.h" #include "miscadmin.h" #include "storage/bufmgr.h" #include "utils/rel.h" @@ -2210,7 +2211,9 @@ spgdoinsert(Relation index, SpGistState *state, if (out.resultType == spgAddNode) elog(ERROR, "cannot add a node to an allTheSame inner tuple"); else if (out.resultType == spgMatchNode) - out.result.matchNode.nodeN = random() % innerTuple->nNodes; + out.result.matchNode.nodeN = + pg_prng_uint64_range(&pg_global_prng_state, + 0, innerTuple->nNodes - 1); } switch (out.resultType) diff --git a/src/backend/access/transam/xact.c b/src/backend/access/transam/xact.c index 8e35c432f5..e7b0bc804d 100644 --- a/src/backend/access/transam/xact.c +++ b/src/backend/access/transam/xact.c @@ -37,6 +37,7 @@ #include "commands/async.h" #include "commands/tablecmds.h" #include "commands/trigger.h" +#include "common/pg_prng.h" #include "executor/spi.h" #include "libpq/be-fsstubs.h" #include "libpq/pqsignal.h" @@ -1990,7 +1991,7 @@ StartTransaction(void) /* Determine if statements are logged in this transaction */ xact_is_sampled = log_xact_sample_rate != 0 && (log_xact_sample_rate == 1 || - random() <= log_xact_sample_rate * MAX_RANDOM_VALUE); + pg_prng_double(&pg_global_prng_state) <= log_xact_sample_rate); /* * initialize current transaction state fields diff --git a/src/backend/commands/analyze.c b/src/backend/commands/analyze.c index 4928702aec..cd77907fc7 100644 --- a/src/backend/commands/analyze.c +++ b/src/backend/commands/analyze.c @@ -38,6 +38,7 @@ #include "commands/progress.h" #include "commands/tablecmds.h" #include "commands/vacuum.h" +#include "common/pg_prng.h" #include "executor/executor.h" #include "foreign/fdwapi.h" #include "miscadmin.h" @@ -1140,7 +1141,7 @@ acquire_sample_rows(Relation onerel, int elevel, double liverows = 0; /* # live rows seen */ double deadrows = 0; /* # dead rows seen */ double rowstoskip = -1; /* -1 means not set yet */ - long randseed; /* Seed for block sampler(s) */ + uint32 randseed; /* Seed for block sampler(s) */ BlockNumber totalblocks; TransactionId OldestXmin; BlockSamplerData bs; @@ -1162,7 +1163,7 @@ acquire_sample_rows(Relation onerel, int elevel, OldestXmin = GetOldestNonRemovableTransactionId(onerel); /* Prepare for sampling block numbers */ - randseed = random(); + randseed = pg_prng_uint32(&pg_global_prng_state); nblocks = BlockSampler_Init(&bs, totalblocks, targrows, randseed); #ifdef USE_PREFETCH @@ -1279,7 +1280,7 @@ acquire_sample_rows(Relation onerel, int elevel, * Found a suitable tuple, so save it, replacing one old * tuple at random */ - int k = (int) (targrows * sampler_random_fract(rstate.randstate)); + int k = (int) (targrows * sampler_random_fract(&rstate.randstate)); Assert(k >= 0 && k < targrows); heap_freetuple(rows[k]); diff --git a/src/backend/executor/nodeSamplescan.c b/src/backend/executor/nodeSamplescan.c index 44232d50d0..33b6fb1377 100644 --- a/src/backend/executor/nodeSamplescan.c +++ b/src/backend/executor/nodeSamplescan.c @@ -17,6 +17,7 @@ #include "access/relscan.h" #include "access/tableam.h" #include "access/tsmapi.h" +#include "common/pg_prng.h" #include "executor/executor.h" #include "executor/nodeSamplescan.h" #include "miscadmin.h" @@ -154,7 +155,7 @@ ExecInitSampleScan(SampleScan *node, EState *estate, int eflags) * do this just once, since the seed shouldn't change over rescans. */ if (tsc->repeatable == NULL) - scanstate->seed = random(); + scanstate->seed = pg_prng_uint32(&pg_global_prng_state); /* * Finally, initialize the TABLESAMPLE method handler. diff --git a/src/backend/lib/bloomfilter.c b/src/backend/lib/bloomfilter.c index daf2c40ebf..ac6001b712 100644 --- a/src/backend/lib/bloomfilter.c +++ b/src/backend/lib/bloomfilter.c @@ -81,8 +81,7 @@ static inline uint32 mod_m(uint32 a, uint64 m); * distinct seed value on every call makes it unlikely that the same false * positives will reoccur when the same set is fingerprinted a second time. * Callers that don't care about this pass a constant as their seed, typically - * 0. Callers can use a pseudo-random seed in the range of 0 - INT_MAX by - * calling random(). + * 0. Callers can also use a pseudo-random seed, eg from pg_prng_uint64(). */ bloom_filter * bloom_create(int64 total_elems, int bloom_work_mem, uint64 seed) diff --git a/src/backend/optimizer/geqo/geqo_random.c b/src/backend/optimizer/geqo/geqo_random.c index f21bc047e6..4d9432c0df 100644 --- a/src/backend/optimizer/geqo/geqo_random.c +++ b/src/backend/optimizer/geqo/geqo_random.c @@ -21,14 +21,7 @@ geqo_set_seed(PlannerInfo *root, double seed) { GeqoPrivateData *private = (GeqoPrivateData *) root->join_search_private; - /* - * XXX. This seeding algorithm could certainly be improved - but it is not - * critical to do so. - */ - memset(private->random_state, 0, sizeof(private->random_state)); - memcpy(private->random_state, - &seed, - Min(sizeof(private->random_state), sizeof(seed))); + pg_prng_fseed(&private->random_state, seed); } double @@ -36,5 +29,17 @@ geqo_rand(PlannerInfo *root) { GeqoPrivateData *private = (GeqoPrivateData *) root->join_search_private; - return pg_erand48(private->random_state); + return pg_prng_double(&private->random_state); +} + +int +geqo_randint(PlannerInfo *root, int upper, int lower) +{ + GeqoPrivateData *private = (GeqoPrivateData *) root->join_search_private; + + /* + * In current usage, "lower" is never negative so we can just use + * pg_prng_uint64_range directly. + */ + return (int) pg_prng_uint64_range(&private->random_state, lower, upper); } diff --git a/src/backend/optimizer/geqo/geqo_selection.c b/src/backend/optimizer/geqo/geqo_selection.c index 66b6c8ae38..68a2e4e9f1 100644 --- a/src/backend/optimizer/geqo/geqo_selection.c +++ b/src/backend/optimizer/geqo/geqo_selection.c @@ -63,10 +63,6 @@ geqo_selection(PlannerInfo *root, Chromosome *momma, Chromosome *daddy, /* * Ensure we have selected different genes, except if pool size is only * one, when we can't. - * - * This code was observed to hang up in an infinite loop when the - * platform's implementation of erand48() was broken. We now always use - * our own version. */ if (pool->size > 1) { @@ -95,11 +91,11 @@ linear_rand(PlannerInfo *root, int pool_size, double bias) double max = (double) pool_size; /* - * If geqo_rand() returns exactly 1.0 then we will get exactly max from - * this equation, whereas we need 0 <= index < max. Also it seems - * possible that roundoff error might deliver values slightly outside the - * range; in particular avoid passing a value slightly less than 0 to - * sqrt(). If we get a bad value just try again. + * geqo_rand() is not supposed to return 1.0, but if it does then we will + * get exactly max from this equation, whereas we need 0 <= index < max. + * Also it seems possible that roundoff error might deliver values + * slightly outside the range; in particular avoid passing a value + * slightly less than 0 to sqrt(). If we get a bad value just try again. */ do { diff --git a/src/backend/postmaster/postmaster.c b/src/backend/postmaster/postmaster.c index db797c040b..328ecafa8c 100644 --- a/src/backend/postmaster/postmaster.c +++ b/src/backend/postmaster/postmaster.c @@ -98,6 +98,7 @@ #include "catalog/pg_control.h" #include "common/file_perm.h" #include "common/ip.h" +#include "common/pg_prng.h" #include "common/string.h" #include "lib/ilist.h" #include "libpq/auth.h" @@ -2699,19 +2700,19 @@ ClosePostmasterPorts(bool am_syslogger) void InitProcessGlobals(void) { - unsigned int rseed; - MyProcPid = getpid(); MyStartTimestamp = GetCurrentTimestamp(); MyStartTime = timestamptz_to_time_t(MyStartTimestamp); /* - * Set a different seed for random() in every process. We want something + * Set a different global seed in every process. We want something * unpredictable, so if possible, use high-quality random bits for the * seed. Otherwise, fall back to a seed based on timestamp and PID. */ - if (!pg_strong_random(&rseed, sizeof(rseed))) + if (unlikely(!pg_prng_strong_seed(&pg_global_prng_state))) { + uint64 rseed; + /* * Since PIDs and timestamps tend to change more frequently in their * least significant bits, shift the timestamp left to allow a larger @@ -2722,8 +2723,17 @@ InitProcessGlobals(void) rseed = ((uint64) MyProcPid) ^ ((uint64) MyStartTimestamp << 12) ^ ((uint64) MyStartTimestamp >> 20); + + pg_prng_seed(&pg_global_prng_state, rseed); } - srandom(rseed); + + /* + * Also make sure that we've set a good seed for random(3). Use of that + * is deprecated in core Postgres, but extensions might use it. + */ +#ifndef WIN32 + srandom(pg_prng_uint32(&pg_global_prng_state)); +#endif } diff --git a/src/backend/storage/file/fd.c b/src/backend/storage/file/fd.c index cb1a8dd34f..263057841d 100644 --- a/src/backend/storage/file/fd.c +++ b/src/backend/storage/file/fd.c @@ -92,6 +92,7 @@ #include "catalog/pg_tablespace.h" #include "common/file_perm.h" #include "common/file_utils.h" +#include "common/pg_prng.h" #include "miscadmin.h" #include "pgstat.h" #include "port/pg_iovec.h" @@ -2939,7 +2940,8 @@ SetTempTablespaces(Oid *tableSpaces, int numSpaces) * available tablespaces. */ if (numSpaces > 1) - nextTempTableSpace = random() % numSpaces; + nextTempTableSpace = pg_prng_uint64_range(&pg_global_prng_state, + 0, numSpaces - 1); else nextTempTableSpace = 0; } diff --git a/src/backend/storage/ipc/dsm.c b/src/backend/storage/ipc/dsm.c index b461a5f7e9..074dff4e6d 100644 --- a/src/backend/storage/ipc/dsm.c +++ b/src/backend/storage/ipc/dsm.c @@ -33,6 +33,7 @@ #endif #include <sys/stat.h> +#include "common/pg_prng.h" #include "lib/ilist.h" #include "miscadmin.h" #include "port/pg_bitutils.h" @@ -180,7 +181,8 @@ dsm_postmaster_startup(PGShmemHeader *shim) { Assert(dsm_control_address == NULL); Assert(dsm_control_mapped_size == 0); - dsm_control_handle = random() << 1; /* Even numbers only */ + /* Use even numbers only */ + dsm_control_handle = pg_prng_uint32(&pg_global_prng_state) << 1; if (dsm_control_handle == DSM_HANDLE_INVALID) continue; if (dsm_impl_op(DSM_OP_CREATE, dsm_control_handle, segsize, @@ -536,7 +538,8 @@ dsm_create(Size size, int flags) for (;;) { Assert(seg->mapped_address == NULL && seg->mapped_size == 0); - seg->handle = random() << 1; /* Even numbers only */ + /* Use even numbers only */ + seg->handle = pg_prng_uint32(&pg_global_prng_state) << 1; if (seg->handle == DSM_HANDLE_INVALID) /* Reserve sentinel */ continue; if (dsm_impl_op(DSM_OP_CREATE, seg->handle, size, &seg->impl_private, @@ -1237,7 +1240,7 @@ make_main_region_dsm_handle(int slot) */ handle = 1; handle |= slot << 1; - handle |= random() << (pg_leftmost_one_pos32(dsm_control->maxitems) + 1); + handle |= pg_prng_uint32(&pg_global_prng_state) << (pg_leftmost_one_pos32(dsm_control->maxitems) + 1); return handle; } diff --git a/src/backend/storage/lmgr/Makefile b/src/backend/storage/lmgr/Makefile index 829b792fcb..b25b7ee421 100644 --- a/src/backend/storage/lmgr/Makefile +++ b/src/backend/storage/lmgr/Makefile @@ -30,9 +30,10 @@ ifdef TAS TASPATH = $(top_builddir)/src/backend/port/tas.o endif -s_lock_test: s_lock.c $(top_builddir)/src/port/libpgport.a +s_lock_test: s_lock.c $(top_builddir)/src/common/libpgcommon.a $(top_builddir)/src/port/libpgport.a $(CC) $(CPPFLAGS) $(CFLAGS) -DS_LOCK_TEST=1 $(srcdir)/s_lock.c \ - $(TASPATH) -L $(top_builddir)/src/port -lpgport -o s_lock_test + $(TASPATH) -L $(top_builddir)/src/common -lpgcommon \ + -L $(top_builddir)/src/port -lpgport -o s_lock_test # see notes in src/backend/parser/Makefile lwlocknames.c: lwlocknames.h diff --git a/src/backend/storage/lmgr/s_lock.c b/src/backend/storage/lmgr/s_lock.c index 91322a40c1..75c0f4535c 100644 --- a/src/backend/storage/lmgr/s_lock.c +++ b/src/backend/storage/lmgr/s_lock.c @@ -50,6 +50,7 @@ #include <time.h> #include <unistd.h> +#include "common/pg_prng.h" #include "port/atomics.h" #include "storage/s_lock.h" @@ -144,7 +145,7 @@ perform_spin_delay(SpinDelayStatus *status) /* increase delay by a random fraction between 1X and 2X */ status->cur_delay += (int) (status->cur_delay * - ((double) random() / (double) MAX_RANDOM_VALUE) + 0.5); + pg_prng_double(&pg_global_prng_state) + 0.5); /* wrap back to minimum delay when max is exceeded */ if (status->cur_delay > MAX_DELAY_USEC) status->cur_delay = MIN_DELAY_USEC; @@ -303,7 +304,7 @@ volatile struct test_lock_struct test_lock; int main() { - srandom((unsigned int) time(NULL)); + pg_prng_seed(&pg_global_prng_state, (uint64) time(NULL)); test_lock.pad1 = test_lock.pad2 = 0x44; diff --git a/src/backend/tcop/postgres.c b/src/backend/tcop/postgres.c index 0775abe35d..82de01cdc6 100644 --- a/src/backend/tcop/postgres.c +++ b/src/backend/tcop/postgres.c @@ -42,6 +42,7 @@ #include "catalog/pg_type.h" #include "commands/async.h" #include "commands/prepare.h" +#include "common/pg_prng.h" #include "executor/spi.h" #include "jit/jit.h" #include "libpq/libpq.h" @@ -2355,13 +2356,13 @@ check_log_duration(char *msec_str, bool was_logged) /* * Do not log if log_statement_sample_rate = 0. Log a sample if - * log_statement_sample_rate <= 1 and avoid unnecessary random() call - * if log_statement_sample_rate = 1. + * log_statement_sample_rate <= 1 and avoid unnecessary PRNG call if + * log_statement_sample_rate = 1. */ if (exceeded_sample_duration) in_sample = log_statement_sample_rate != 0 && (log_statement_sample_rate == 1 || - random() <= log_statement_sample_rate * MAX_RANDOM_VALUE); + pg_prng_double(&pg_global_prng_state) <= log_statement_sample_rate); if (exceeded_duration || in_sample || log_duration || xact_is_sampled) { diff --git a/src/backend/utils/adt/float.c b/src/backend/utils/adt/float.c index 098bbb372b..455e5d8cbe 100644 --- a/src/backend/utils/adt/float.c +++ b/src/backend/utils/adt/float.c @@ -21,6 +21,7 @@ #include "catalog/pg_type.h" #include "common/int.h" +#include "common/pg_prng.h" #include "common/shortest_dec.h" #include "libpq/pqformat.h" #include "miscadmin.h" @@ -65,7 +66,7 @@ float8 degree_c_one = 1.0; /* State for drandom() and setseed() */ static bool drandom_seed_set = false; -static unsigned short drandom_seed[3] = {0, 0, 0}; +static pg_prng_state drandom_seed; /* Local function prototypes */ static double sind_q1(double x); @@ -2762,22 +2763,20 @@ drandom(PG_FUNCTION_ARGS) * Should that fail for some reason, we fall back on a lower-quality * seed based on current time and PID. */ - if (!pg_strong_random(drandom_seed, sizeof(drandom_seed))) + if (unlikely(!pg_prng_strong_seed(&drandom_seed))) { TimestampTz now = GetCurrentTimestamp(); uint64 iseed; /* Mix the PID with the most predictable bits of the timestamp */ iseed = (uint64) now ^ ((uint64) MyProcPid << 32); - drandom_seed[0] = (unsigned short) iseed; - drandom_seed[1] = (unsigned short) (iseed >> 16); - drandom_seed[2] = (unsigned short) (iseed >> 32); + pg_prng_seed(&drandom_seed, iseed); } drandom_seed_set = true; } - /* pg_erand48 produces desired result range [0.0 - 1.0) */ - result = pg_erand48(drandom_seed); + /* pg_prng_double produces desired result range [0.0 - 1.0) */ + result = pg_prng_double(&drandom_seed); PG_RETURN_FLOAT8(result); } @@ -2790,7 +2789,6 @@ Datum setseed(PG_FUNCTION_ARGS) { float8 seed = PG_GETARG_FLOAT8(0); - uint64 iseed; if (seed < -1 || seed > 1 || isnan(seed)) ereport(ERROR, @@ -2798,11 +2796,7 @@ setseed(PG_FUNCTION_ARGS) errmsg("setseed parameter %g is out of allowed range [-1,1]", seed))); - /* Use sign bit + 47 fractional bits to fill drandom_seed[] */ - iseed = (int64) (seed * (float8) UINT64CONST(0x7FFFFFFFFFFF)); - drandom_seed[0] = (unsigned short) iseed; - drandom_seed[1] = (unsigned short) (iseed >> 16); - drandom_seed[2] = (unsigned short) (iseed >> 32); + pg_prng_fseed(&drandom_seed, seed); drandom_seed_set = true; PG_RETURN_VOID(); diff --git a/src/backend/utils/misc/sampling.c b/src/backend/utils/misc/sampling.c index 0c327e823f..d1a2416e8b 100644 --- a/src/backend/utils/misc/sampling.c +++ b/src/backend/utils/misc/sampling.c @@ -37,7 +37,7 @@ */ BlockNumber BlockSampler_Init(BlockSampler bs, BlockNumber nblocks, int samplesize, - long randseed) + uint32 randseed) { bs->N = nblocks; /* measured table size */ @@ -49,7 +49,7 @@ BlockSampler_Init(BlockSampler bs, BlockNumber nblocks, int samplesize, bs->t = 0; /* blocks scanned so far */ bs->m = 0; /* blocks selected so far */ - sampler_random_init_state(randseed, bs->randstate); + sampler_random_init_state(randseed, &bs->randstate); return Min(bs->n, bs->N); } @@ -98,7 +98,7 @@ BlockSampler_Next(BlockSampler bs) * less than k, which means that we cannot fail to select enough blocks. *---------- */ - V = sampler_random_fract(bs->randstate); + V = sampler_random_fract(&bs->randstate); p = 1.0 - (double) k / (double) K; while (V < p) { @@ -136,10 +136,11 @@ reservoir_init_selection_state(ReservoirState rs, int n) * Reservoir sampling is not used anywhere where it would need to return * repeatable results so we can initialize it randomly. */ - sampler_random_init_state(random(), rs->randstate); + sampler_random_init_state(pg_prng_uint32(&pg_global_prng_state), + &rs->randstate); /* Initial value of W (for use when Algorithm Z is first applied) */ - rs->W = exp(-log(sampler_random_fract(rs->randstate)) / n); + rs->W = exp(-log(sampler_random_fract(&rs->randstate)) / n); } double @@ -154,7 +155,7 @@ reservoir_get_next_S(ReservoirState rs, double t, int n) double V, quot; - V = sampler_random_fract(rs->randstate); /* Generate V */ + V = sampler_random_fract(&rs->randstate); /* Generate V */ S = 0; t += 1; /* Note: "num" in Vitter's code is always equal to t - n */ @@ -186,7 +187,7 @@ reservoir_get_next_S(ReservoirState rs, double t, int n) tmp; /* Generate U and X */ - U = sampler_random_fract(rs->randstate); + U = sampler_random_fract(&rs->randstate); X = t * (W - 1.0); S = floor(X); /* S is tentatively set to floor(X) */ /* Test if U <= h(S)/cg(X) in the manner of (6.3) */ @@ -215,7 +216,7 @@ reservoir_get_next_S(ReservoirState rs, double t, int n) y *= numer / denom; denom -= 1; } - W = exp(-log(sampler_random_fract(rs->randstate)) / n); /* Generate W in advance */ + W = exp(-log(sampler_random_fract(&rs->randstate)) / n); /* Generate W in advance */ if (exp(log(y) / n) <= (t + X) / t) break; } @@ -230,24 +231,22 @@ reservoir_get_next_S(ReservoirState rs, double t, int n) *---------- */ void -sampler_random_init_state(long seed, SamplerRandomState randstate) +sampler_random_init_state(uint32 seed, pg_prng_state *randstate) { - randstate[0] = 0x330e; /* same as pg_erand48, but could be anything */ - randstate[1] = (unsigned short) seed; - randstate[2] = (unsigned short) (seed >> 16); + pg_prng_seed(randstate, (uint64) seed); } /* Select a random value R uniformly distributed in (0 - 1) */ double -sampler_random_fract(SamplerRandomState randstate) +sampler_random_fract(pg_prng_state *randstate) { double res; - /* pg_erand48 returns a value in [0.0 - 1.0), so we must reject 0 */ + /* pg_prng_double returns a value in [0.0 - 1.0), so we must reject 0.0 */ do { - res = pg_erand48(randstate); - } while (res == 0.0); + res = pg_prng_double(randstate); + } while (unlikely(res == 0.0)); return res; } @@ -261,27 +260,36 @@ sampler_random_fract(SamplerRandomState randstate) * except that a common random state is used across all callers. */ static ReservoirStateData oldrs; +static bool oldrs_initialized = false; double anl_random_fract(void) { /* initialize if first time through */ - if (oldrs.randstate[0] == 0) - sampler_random_init_state(random(), oldrs.randstate); + if (unlikely(!oldrs_initialized)) + { + sampler_random_init_state(pg_prng_uint32(&pg_global_prng_state), + &oldrs.randstate); + oldrs_initialized = true; + } /* and compute a random fraction */ - return sampler_random_fract(oldrs.randstate); + return sampler_random_fract(&oldrs.randstate); } double anl_init_selection_state(int n) { /* initialize if first time through */ - if (oldrs.randstate[0] == 0) - sampler_random_init_state(random(), oldrs.randstate); + if (unlikely(!oldrs_initialized)) + { + sampler_random_init_state(pg_prng_uint32(&pg_global_prng_state), + &oldrs.randstate); + oldrs_initialized = true; + } /* Initial value of W (for use when Algorithm Z is first applied) */ - return exp(-log(sampler_random_fract(oldrs.randstate)) / n); + return exp(-log(sampler_random_fract(&oldrs.randstate)) / n); } double diff --git a/src/bin/initdb/initdb.c b/src/bin/initdb/initdb.c index 3c61c789e4..403adb0ee7 100644 --- a/src/bin/initdb/initdb.c +++ b/src/bin/initdb/initdb.c @@ -66,6 +66,7 @@ #include "common/file_perm.h" #include "common/file_utils.h" #include "common/logging.h" +#include "common/pg_prng.h" #include "common/restricted_token.h" #include "common/string.h" #include "common/username.h" @@ -880,9 +881,10 @@ choose_dsm_implementation(void) { #ifdef HAVE_SHM_OPEN int ntries = 10; + pg_prng_state prng_state; - /* Initialize random(); this function is its only user in this program. */ - srandom((unsigned int) (getpid() ^ time(NULL))); + /* Initialize prng; this function is its only user in this program. */ + pg_prng_seed(&prng_state, (uint64) (getpid() ^ time(NULL))); while (ntries > 0) { @@ -890,7 +892,7 @@ choose_dsm_implementation(void) char name[64]; int fd; - handle = random(); + handle = pg_prng_uint32(&prng_state); snprintf(name, 64, "/PostgreSQL.%u", handle); if ((fd = shm_open(name, O_CREAT | O_RDWR | O_EXCL, 0600)) != -1) { diff --git a/src/bin/pg_test_fsync/pg_test_fsync.c b/src/bin/pg_test_fsync/pg_test_fsync.c index fef31844fa..ddabf64c58 100644 --- a/src/bin/pg_test_fsync/pg_test_fsync.c +++ b/src/bin/pg_test_fsync/pg_test_fsync.c @@ -15,6 +15,7 @@ #include "access/xlogdefs.h" #include "common/logging.h" +#include "common/pg_prng.h" #include "getopt_long.h" /* @@ -117,6 +118,8 @@ main(int argc, char *argv[]) pqsignal(SIGHUP, signal_cleanup); #endif + pg_prng_seed(&pg_global_prng_state, (uint64) time(NULL)); + prepare_buf(); test_open(); @@ -233,7 +236,7 @@ prepare_buf(void) /* write random data into buffer */ for (ops = 0; ops < DEFAULT_XLOG_SEG_SIZE; ops++) - full_buf[ops] = random(); + full_buf[ops] = (char) pg_prng_int32(&pg_global_prng_state); buf = (char *) TYPEALIGN(XLOG_BLCKSZ, full_buf); } diff --git a/src/bin/pgbench/pgbench.c b/src/bin/pgbench/pgbench.c index c12b6f0615..ea9639984c 100644 --- a/src/bin/pgbench/pgbench.c +++ b/src/bin/pgbench/pgbench.c @@ -59,6 +59,7 @@ #include "common/int.h" #include "common/logging.h" +#include "common/pg_prng.h" #include "common/string.h" #include "common/username.h" #include "fe_utils/cancel.h" @@ -350,16 +351,8 @@ typedef struct StatsData */ pg_time_usec_t epoch_shift; -/* - * Struct to keep random state. - */ -typedef struct RandomState -{ - unsigned short xseed[3]; -} RandomState; - /* Various random sequences are initialized from this one. */ -static RandomState base_random_sequence; +static pg_prng_state base_random_sequence; /* Synchronization barrier for start and connection */ static THREAD_BARRIER_T barrier; @@ -461,7 +454,7 @@ typedef struct * Separate randomness for each client. This is used for random functions * PGBENCH_RANDOM_* during the execution of the script. */ - RandomState cs_func_rs; + pg_prng_state cs_func_rs; int use_file; /* index in sql_script for this client */ int command; /* command number in script */ @@ -498,9 +491,9 @@ typedef struct * random state to make all of them independent of each other and * therefore deterministic at the thread level. */ - RandomState ts_choose_rs; /* random state for selecting a script */ - RandomState ts_throttle_rs; /* random state for transaction throttling */ - RandomState ts_sample_rs; /* random state for log sampling */ + pg_prng_state ts_choose_rs; /* random state for selecting a script */ + pg_prng_state ts_throttle_rs; /* random state for transaction throttling */ + pg_prng_state ts_sample_rs; /* random state for log sampling */ int64 throttle_trigger; /* previous/next throttling (us) */ FILE *logfile; /* where to log, or NULL */ @@ -898,42 +891,28 @@ strtodouble(const char *str, bool errorOK, double *dv) } /* - * Initialize a random state struct. + * Initialize a prng state struct. * * We derive the seed from base_random_sequence, which must be set up already. */ static void -initRandomState(RandomState *random_state) -{ - random_state->xseed[0] = (unsigned short) - (pg_jrand48(base_random_sequence.xseed) & 0xFFFF); - random_state->xseed[1] = (unsigned short) - (pg_jrand48(base_random_sequence.xseed) & 0xFFFF); - random_state->xseed[2] = (unsigned short) - (pg_jrand48(base_random_sequence.xseed) & 0xFFFF); +initRandomState(pg_prng_state *state) +{ + pg_prng_seed(state, pg_prng_uint64(&base_random_sequence)); } + /* - * Random number generator: uniform distribution from min to max inclusive. + * random number generator: uniform distribution from min to max inclusive. * * Although the limits are expressed as int64, you can't generate the full * int64 range in one call, because the difference of the limits mustn't - * overflow int64. In practice it's unwise to ask for more than an int32 - * range, because of the limited precision of pg_erand48(). + * overflow int64. This is not checked. */ static int64 -getrand(RandomState *random_state, int64 min, int64 max) +getrand(pg_prng_state *state, int64 min, int64 max) { - /* - * Odd coding is so that min and max have approximately the same chance of - * being selected as do numbers between them. - * - * pg_erand48() is thread-safe and concurrent, which is why we use it - * rather than random(), which in glibc is non-reentrant, and therefore - * protected by a mutex, and therefore a bottleneck on machines with many - * CPUs. - */ - return min + (int64) ((max - min + 1) * pg_erand48(random_state->xseed)); + return min + (int64) pg_prng_uint64_range(state, 0, max - min); } /* @@ -942,7 +921,7 @@ getrand(RandomState *random_state, int64 min, int64 max) * value is exp(-parameter). */ static int64 -getExponentialRand(RandomState *random_state, int64 min, int64 max, +getExponentialRand(pg_prng_state *state, int64 min, int64 max, double parameter) { double cut, @@ -952,8 +931,8 @@ getExponentialRand(RandomState *random_state, int64 min, int64 max, /* abort if wrong parameter, but must really be checked beforehand */ Assert(parameter > 0.0); cut = exp(-parameter); - /* erand in [0, 1), uniform in (0, 1] */ - uniform = 1.0 - pg_erand48(random_state->xseed); + /* pg_prng_double value in [0, 1), uniform in (0, 1] */ + uniform = 1.0 - pg_prng_double(state); /* * inner expression in (cut, 1] (if parameter > 0), rand in [0, 1) @@ -966,7 +945,7 @@ getExponentialRand(RandomState *random_state, int64 min, int64 max, /* random number generator: gaussian distribution from min to max inclusive */ static int64 -getGaussianRand(RandomState *random_state, int64 min, int64 max, +getGaussianRand(pg_prng_state *state, int64 min, int64 max, double parameter) { double stdev; @@ -990,13 +969,13 @@ getGaussianRand(RandomState *random_state, int64 min, int64 max, do { /* - * pg_erand48 generates [0,1), but for the basic version of the + * pg_prng_double generates [0, 1), but for the basic version of the * Box-Muller transform the two uniformly distributed random numbers - * are expected in (0, 1] (see + * are expected to be in (0, 1] (see * https://en.wikipedia.org/wiki/Box-Muller_transform) */ - double rand1 = 1.0 - pg_erand48(random_state->xseed); - double rand2 = 1.0 - pg_erand48(random_state->xseed); + double rand1 = 1.0 - pg_prng_double(state); + double rand2 = 1.0 - pg_prng_double(state); /* Box-Muller basic form transform */ double var_sqrt = sqrt(-2.0 * log(rand1)); @@ -1026,7 +1005,7 @@ getGaussianRand(RandomState *random_state, int64 min, int64 max, * not be one. */ static int64 -getPoissonRand(RandomState *random_state, double center) +getPoissonRand(pg_prng_state *state, double center) { /* * Use inverse transform sampling to generate a value > 0, such that the @@ -1034,8 +1013,8 @@ getPoissonRand(RandomState *random_state, double center) */ double uniform; - /* erand in [0, 1), uniform in (0, 1] */ - uniform = 1.0 - pg_erand48(random_state->xseed); + /* pg_prng_double value in [0, 1), uniform in (0, 1] */ + uniform = 1.0 - pg_prng_double(state); return (int64) (-log(uniform) * center + 0.5); } @@ -1048,7 +1027,7 @@ getPoissonRand(RandomState *random_state, double center) * This works for s > 1.0, but may perform badly for s very close to 1.0. */ static int64 -computeIterativeZipfian(RandomState *random_state, int64 n, double s) +computeIterativeZipfian(pg_prng_state *state, int64 n, double s) { double b = pow(2.0, s - 1.0); double x, @@ -1063,8 +1042,8 @@ computeIterativeZipfian(RandomState *random_state, int64 n, double s) while (true) { /* random variates */ - u = pg_erand48(random_state->xseed); - v = pg_erand48(random_state->xseed); + u = pg_prng_double(state); + v = pg_prng_double(state); x = floor(pow(u, -1.0 / (s - 1.0))); @@ -1078,14 +1057,14 @@ computeIterativeZipfian(RandomState *random_state, int64 n, double s) /* random number generator: zipfian distribution from min to max inclusive */ static int64 -getZipfianRand(RandomState *random_state, int64 min, int64 max, double s) +getZipfianRand(pg_prng_state *state, int64 min, int64 max, double s) { int64 n = max - min + 1; /* abort if parameter is invalid */ Assert(MIN_ZIPFIAN_PARAM <= s && s <= MAX_ZIPFIAN_PARAM); - return min - 1 + computeIterativeZipfian(random_state, n, s); + return min - 1 + computeIterativeZipfian(state, n, s); } /* @@ -1142,7 +1121,7 @@ getHashMurmur2(int64 val, uint64 seed) * For small sizes, this generates each of the (size!) possible permutations * of integers in the range [0, size) with roughly equal probability. Once * the size is larger than 20, the number of possible permutations exceeds the - * number of distinct states of the internal pseudorandom number generators, + * number of distinct states of the internal pseudorandom number generator, * and so not all possible permutations can be generated, but the permutations * chosen should continue to give the appearance of being random. * @@ -1152,8 +1131,8 @@ getHashMurmur2(int64 val, uint64 seed) static int64 permute(const int64 val, const int64 isize, const int64 seed) { - RandomState random_state1; - RandomState random_state2; + /* using a high-end PRNG is probably overkill */ + pg_prng_state state; uint64 size; uint64 v; int masklen; @@ -1163,14 +1142,8 @@ permute(const int64 val, const int64 isize, const int64 seed) if (isize < 2) return 0; /* nothing to permute */ - /* Initialize a pair of random states using the seed */ - random_state1.xseed[0] = seed & 0xFFFF; - random_state1.xseed[1] = (seed >> 16) & 0xFFFF; - random_state1.xseed[2] = (seed >> 32) & 0xFFFF; - - random_state2.xseed[0] = (((uint64) seed) >> 48) & 0xFFFF; - random_state2.xseed[1] = seed & 0xFFFF; - random_state2.xseed[2] = (seed >> 16) & 0xFFFF; + /* Initialize prng state using the seed */ + pg_prng_seed(&state, (uint64) seed); /* Computations are performed on unsigned values */ size = (uint64) isize; @@ -1216,8 +1189,8 @@ permute(const int64 val, const int64 isize, const int64 seed) t; /* Random multiply (by an odd number), XOR and rotate of lower half */ - m = (uint64) getrand(&random_state1, 0, mask) | 1; - r = (uint64) getrand(&random_state2, 0, mask); + m = (pg_prng_uint64(&state) & mask) | 1; + r = pg_prng_uint64(&state) & mask; if (v <= mask) { v = ((v * m) ^ r) & mask; @@ -1225,8 +1198,8 @@ permute(const int64 val, const int64 isize, const int64 seed) } /* Random multiply (by an odd number), XOR and rotate of upper half */ - m = (uint64) getrand(&random_state1, 0, mask) | 1; - r = (uint64) getrand(&random_state2, 0, mask); + m = (pg_prng_uint64(&state) & mask) | 1; + r = pg_prng_uint64(&state) & mask; t = size - 1 - v; if (t <= mask) { @@ -1236,7 +1209,7 @@ permute(const int64 val, const int64 isize, const int64 seed) } /* Random offset */ - r = (uint64) getrand(&random_state2, 0, size - 1); + r = pg_prng_uint64_range(&state, 0, size - 1); v = (v + r) % size; } @@ -3831,7 +3804,7 @@ doLog(TState *thread, CState *st, * to the random sample. */ if (sample_rate != 0.0 && - pg_erand48(thread->ts_sample_rs.xseed) > sample_rate) + pg_prng_double(&thread->ts_sample_rs) > sample_rate) return; /* should we aggregate the results or not? */ @@ -5770,12 +5743,11 @@ set_random_seed(const char *seed) if (seed != NULL) pg_log_info("setting random seed to %llu", (unsigned long long) iseed); + random_seed = iseed; - /* Fill base_random_sequence with low-order bits of seed */ - base_random_sequence.xseed[0] = iseed & 0xFFFF; - base_random_sequence.xseed[1] = (iseed >> 16) & 0xFFFF; - base_random_sequence.xseed[2] = (iseed >> 32) & 0xFFFF; + /* Initialize base_random_sequence using seed */ + pg_prng_seed(&base_random_sequence, (uint64) iseed); return true; } @@ -6449,9 +6421,7 @@ main(int argc, char **argv) /* set default seed for hash functions */ if (lookupVariable(&state[0], "default_seed") == NULL) { - uint64 seed = - ((uint64) pg_jrand48(base_random_sequence.xseed) & 0xFFFFFFFF) | - (((uint64) pg_jrand48(base_random_sequence.xseed) & 0xFFFFFFFF) << 32); + uint64 seed = pg_prng_uint64(&base_random_sequence); for (i = 0; i < nclients; i++) if (!putVariableInt(&state[i], "startup", "default_seed", (int64) seed)) diff --git a/src/bin/pgbench/t/001_pgbench_with_server.pl b/src/bin/pgbench/t/001_pgbench_with_server.pl index 69ffa595dd..97ed6c71ed 100644 --- a/src/bin/pgbench/t/001_pgbench_with_server.pl +++ b/src/bin/pgbench/t/001_pgbench_with_server.pl @@ -369,7 +369,6 @@ $node->append_conf('postgresql.conf', $node->reload; # test expressions -# command 1..3 and 23 depend on random seed which is used to call srandom. $node->pgbench( '--random-seed=5432 -t 1 -Dfoo=-10.1 -Dbla=false -Di=+3 -Dn=null -Dt=t -Df=of -Dd=1.0', 0, @@ -378,9 +377,9 @@ $node->pgbench( qr{setting random seed to 5432\b}, # After explicit seeding, the four random checks (1-3,20) are - # deterministic - qr{command=1.: int 13\b}, # uniform random - qr{command=2.: int 116\b}, # exponential random + # deterministic; but see also magic values in checks 111,113. + qr{command=1.: int 17\b}, # uniform random + qr{command=2.: int 104\b}, # exponential random qr{command=3.: int 1498\b}, # gaussian random qr{command=4.: int 4\b}, qr{command=5.: int 5\b}, @@ -394,7 +393,7 @@ $node->pgbench( qr{command=15.: double 15\b}, qr{command=16.: double 16\b}, qr{command=17.: double 17\b}, - qr{command=20.: int 1\b}, # zipfian random + qr{command=20.: int 3\b}, # zipfian random qr{command=21.: double -27\b}, qr{command=22.: double 1024\b}, qr{command=23.: double 1\b}, @@ -448,6 +447,7 @@ $node->pgbench( qr{command=109.: boolean true\b}, qr{command=110.: boolean true\b}, qr{command=111.: boolean true\b}, + qr{command=113.: boolean true\b}, ], 'pgbench expressions', { @@ -591,8 +591,17 @@ SELECT :v0, :v1, :v2, :v3; \set t debug(0 <= :p and :p < :size and :p = permute(:v + :size, :size) and :p <> permute(:v + 1, :size)) -- actual values \set t debug(permute(:v, 1) = 0) -\set t debug(permute(0, 2, 5432) = 0 and permute(1, 2, 5432) = 1 and \ - permute(0, 2, 5435) = 1 and permute(1, 2, 5435) = 0) +\set t debug(permute(0, 2, 5431) = 0 and permute(1, 2, 5431) = 1 and \ + permute(0, 2, 5433) = 1 and permute(1, 2, 5433) = 0) +-- check permute's portability across architectures +\set size debug(:max - 10) +\set t debug(permute(:size-1, :size, 5432) = 520382784483822430 and \ + permute(:size-2, :size, 5432) = 1143715004660802862 and \ + permute(:size-3, :size, 5432) = 447293596416496998 and \ + permute(:size-4, :size, 5432) = 916527772266572956 and \ + permute(:size-5, :size, 5432) = 2763809008686028849 and \ + permute(:size-6, :size, 5432) = 8648551549198294572 and \ + permute(:size-7, :size, 5432) = 4542876852200565125) } }); diff --git a/src/common/Makefile b/src/common/Makefile index 880722fcf5..31c0dd366d 100644 --- a/src/common/Makefile +++ b/src/common/Makefile @@ -66,6 +66,7 @@ OBJS_COMMON = \ md5_common.o \ pg_get_line.o \ pg_lzcompress.o \ + pg_prng.o \ pgfnames.o \ psprintf.o \ relpath.o \ diff --git a/src/common/pg_prng.c b/src/common/pg_prng.c new file mode 100644 index 0000000000..a0b6bcb3b5 --- /dev/null +++ b/src/common/pg_prng.c @@ -0,0 +1,247 @@ +/*------------------------------------------------------------------------- + * + * Pseudo-Random Number Generator + * + * We use Blackman and Vigna's xoroshiro128** 1.0 algorithm + * to have a small, fast PRNG suitable for generating reasonably + * good-quality 64-bit data. This should not be considered + * cryptographically strong, however. + * + * About these generators: https://prng.di.unimi.it/ + * See also https://en.wikipedia.org/wiki/List_of_random_number_generators + * + * Copyright (c) 2021, PostgreSQL Global Development Group + * + * src/common/pg_prng.c + * + *------------------------------------------------------------------------- + */ + +#include "c.h" + +#include <math.h> /* for ldexp() */ + +#include "common/pg_prng.h" +#include "port/pg_bitutils.h" + +/* process-wide state vector */ +pg_prng_state pg_global_prng_state; + + +/* + * 64-bit rotate left + */ +static inline uint64 +rotl(uint64 x, int bits) +{ + return (x << bits) | (x >> (64 - bits)); +} + +/* + * The basic xoroshiro128** algorithm. + * Generates and returns a 64-bit uniformly distributed number, + * updating the state vector for next time. + * + * Note: the state vector must not be all-zeroes, as that is a fixed point. + */ +static uint64 +xoroshiro128ss(pg_prng_state *state) +{ + uint64 s0 = state->s0, + sx = state->s1 ^ s0, + val = rotl(s0 * 5, 7) * 9; + + /* update state */ + state->s0 = rotl(s0, 24) ^ sx ^ (sx << 16); + state->s1 = rotl(sx, 37); + + return val; +} + +/* + * We use this generator just to fill the xoroshiro128** state vector + * from a 64-bit seed. + */ +static uint64 +splitmix64(uint64 *state) +{ + /* state update */ + uint64 val = (*state += UINT64CONST(0x9E3779B97f4A7C15)); + + /* value extraction */ + val = (val ^ (val >> 30)) * UINT64CONST(0xBF58476D1CE4E5B9); + val = (val ^ (val >> 27)) * UINT64CONST(0x94D049BB133111EB); + + return val ^ (val >> 31); +} + +/* + * Initialize the PRNG state from a 64-bit integer, + * taking care that we don't produce all-zeroes. + */ +void +pg_prng_seed(pg_prng_state *state, uint64 seed) +{ + state->s0 = splitmix64(&seed); + state->s1 = splitmix64(&seed); + /* Let's just make sure we didn't get all-zeroes */ + (void) pg_prng_seed_check(state); +} + +/* + * Initialize the PRNG state from a double in the range [-1.0, 1.0], + * taking care that we don't produce all-zeroes. + */ +void +pg_prng_fseed(pg_prng_state *state, double fseed) +{ + /* Assume there's about 52 mantissa bits; the sign contributes too. */ + int64 seed = ((double) ((UINT64CONST(1) << 52) - 1)) * fseed; + + pg_prng_seed(state, (uint64) seed); +} + +/* + * Validate a PRNG seed value. + */ +bool +pg_prng_seed_check(pg_prng_state *state) +{ + /* + * If the seeding mechanism chanced to produce all-zeroes, insert + * something nonzero. Anything would do; use Knuth's LCG parameters. + */ + if (unlikely(state->s0 == 0 && state->s1 == 0)) + { + state->s0 = UINT64CONST(0x5851F42D4C957F2D); + state->s1 = UINT64CONST(0x14057B7EF767814F); + } + + /* As a convenience for the pg_prng_strong_seed macro, return true */ + return true; +} + +/* + * Select a random uint64 uniformly from the range [0, PG_UINT64_MAX]. + */ +uint64 +pg_prng_uint64(pg_prng_state *state) +{ + return xoroshiro128ss(state); +} + +/* + * Select a random uint64 uniformly from the range [rmin, rmax]. + * If the range is empty, rmin is always produced. + */ +uint64 +pg_prng_uint64_range(pg_prng_state *state, uint64 rmin, uint64 rmax) +{ + uint64 val; + + if (likely(rmax > rmin)) + { + /* + * Use bitmask rejection method to generate an offset in 0..range. + * Each generated val is less than twice "range", so on average we + * should not have to iterate more than twice. + */ + uint64 range = rmax - rmin; + uint32 rshift = 63 - pg_leftmost_one_pos64(range); + + do + { + val = xoroshiro128ss(state) >> rshift; + } while (val > range); + } + else + val = 0; + + return rmin + val; +} + +/* + * Select a random int64 uniformly from the range [PG_INT64_MIN, PG_INT64_MAX]. + */ +int64 +pg_prng_int64(pg_prng_state *state) +{ + return (int64) xoroshiro128ss(state); +} + +/* + * Select a random int64 uniformly from the range [0, PG_INT64_MAX]. + */ +int64 +pg_prng_int64p(pg_prng_state *state) +{ + return (int64) (xoroshiro128ss(state) & UINT64CONST(0x7FFFFFFFFFFFFFFF)); +} + +/* + * Select a random uint32 uniformly from the range [0, PG_UINT32_MAX]. + */ +uint32 +pg_prng_uint32(pg_prng_state *state) +{ + /* + * Although xoroshiro128** is not known to have any weaknesses in + * randomness of low-order bits, we prefer to use the upper bits of its + * result here and below. + */ + uint64 v = xoroshiro128ss(state); + + return (uint32) (v >> 32); +} + +/* + * Select a random int32 uniformly from the range [PG_INT32_MIN, PG_INT32_MAX]. + */ +int32 +pg_prng_int32(pg_prng_state *state) +{ + uint64 v = xoroshiro128ss(state); + + return (int32) (v >> 32); +} + +/* + * Select a random int32 uniformly from the range [0, PG_INT32_MAX]. + */ +int32 +pg_prng_int32p(pg_prng_state *state) +{ + uint64 v = xoroshiro128ss(state); + + return (int32) (v >> 33); +} + +/* + * Select a random double uniformly from the range [0.0, 1.0). + * + * Note: if you want a result in the range (0.0, 1.0], the standard way + * to get that is "1.0 - pg_prng_double(state)". + */ +double +pg_prng_double(pg_prng_state *state) +{ + uint64 v = xoroshiro128ss(state); + + /* + * As above, assume there's 52 mantissa bits in a double. This result + * could round to 1.0 if double's precision is less than that; but we + * assume IEEE float arithmetic elsewhere in Postgres, so this seems OK. + */ + return ldexp((double) (v >> (64 - 52)), -52); +} + +/* + * Select a random boolean value. + */ +bool +pg_prng_bool(pg_prng_state *state) +{ + uint64 v = xoroshiro128ss(state); + + return (bool) (v >> 63); +} diff --git a/src/include/common/pg_prng.h b/src/include/common/pg_prng.h new file mode 100644 index 0000000000..623c65ae73 --- /dev/null +++ b/src/include/common/pg_prng.h @@ -0,0 +1,60 @@ +/*------------------------------------------------------------------------- + * + * Pseudo-Random Number Generator + * + * Copyright (c) 2021, PostgreSQL Global Development Group + * + * src/include/common/pg_prng.h + * + *------------------------------------------------------------------------- + */ +#ifndef PG_PRNG_H +#define PG_PRNG_H + +/* + * State vector for PRNG generation. Callers should treat this as an + * opaque typedef, but we expose its definition to allow it to be + * embedded in other structs. + */ +typedef struct pg_prng_state +{ + uint64 s0, + s1; +} pg_prng_state; + +/* + * Callers not needing local PRNG series may use this global state vector, + * after initializing it with one of the pg_prng_...seed functions. + */ +extern PGDLLIMPORT pg_prng_state pg_global_prng_state; + +extern void pg_prng_seed(pg_prng_state *state, uint64 seed); +extern void pg_prng_fseed(pg_prng_state *state, double fseed); +extern bool pg_prng_seed_check(pg_prng_state *state); + +/* + * Initialize the PRNG state from the pg_strong_random source, + * taking care that we don't produce all-zeroes. If this returns false, + * caller should initialize the PRNG state from some other random seed, + * using pg_prng_[f]seed. + * + * We implement this as a macro, so that the pg_strong_random() call is + * in the caller. If it were in pg_prng.c, programs using pg_prng.c + * but not needing strong seeding would nonetheless be forced to pull in + * pg_strong_random.c and thence OpenSSL. + */ +#define pg_prng_strong_seed(state) \ + (pg_strong_random((void *) (state), sizeof(pg_prng_state)) ? \ + pg_prng_seed_check(state) : false) + +extern uint64 pg_prng_uint64(pg_prng_state *state); +extern uint64 pg_prng_uint64_range(pg_prng_state *state, uint64 rmin, uint64 rmax); +extern int64 pg_prng_int64(pg_prng_state *state); +extern int64 pg_prng_int64p(pg_prng_state *state); +extern uint32 pg_prng_uint32(pg_prng_state *state); +extern int32 pg_prng_int32(pg_prng_state *state); +extern int32 pg_prng_int32p(pg_prng_state *state); +extern double pg_prng_double(pg_prng_state *state); +extern bool pg_prng_bool(pg_prng_state *state); + +#endif /* PG_PRNG_H */ diff --git a/src/include/optimizer/geqo.h b/src/include/optimizer/geqo.h index 24dcdfb6cc..b9635a2170 100644 --- a/src/include/optimizer/geqo.h +++ b/src/include/optimizer/geqo.h @@ -22,6 +22,7 @@ #ifndef GEQO_H #define GEQO_H +#include "common/pg_prng.h" #include "nodes/pathnodes.h" #include "optimizer/geqo_gene.h" @@ -73,7 +74,7 @@ extern double Geqo_seed; /* 0 .. 1 */ typedef struct { List *initial_rels; /* the base relations we are joining */ - unsigned short random_state[3]; /* state for pg_erand48() */ + pg_prng_state random_state; /* PRNG state */ } GeqoPrivateData; diff --git a/src/include/optimizer/geqo_random.h b/src/include/optimizer/geqo_random.h index 7f4aad4439..958fdaf299 100644 --- a/src/include/optimizer/geqo_random.h +++ b/src/include/optimizer/geqo_random.h @@ -31,11 +31,10 @@ extern void geqo_set_seed(PlannerInfo *root, double seed); -/* geqo_rand returns a random float value between 0 and 1 inclusive */ +/* geqo_rand returns a random float value in the range [0.0, 1.0) */ extern double geqo_rand(PlannerInfo *root); /* geqo_randint returns integer value between lower and upper inclusive */ -#define geqo_randint(root, upper, lower) \ - ( (int) floor( geqo_rand(root)*(((upper)-(lower))+0.999999) ) + (lower) ) +extern int geqo_randint(PlannerInfo *root, int upper, int lower); #endif /* GEQO_RANDOM_H */ diff --git a/src/include/pg_config.h.in b/src/include/pg_config.h.in index ca3592465e..d793734fe1 100644 --- a/src/include/pg_config.h.in +++ b/src/include/pg_config.h.in @@ -445,9 +445,6 @@ /* Define to 1 if you have the `pwrite' function. */ #undef HAVE_PWRITE -/* Define to 1 if you have the `random' function. */ -#undef HAVE_RANDOM - /* Define to 1 if you have the <readline.h> header file. */ #undef HAVE_READLINE_H @@ -512,9 +509,6 @@ /* Define to 1 if you have spinlocks. */ #undef HAVE_SPINLOCKS -/* Define to 1 if you have the `srandom' function. */ -#undef HAVE_SRANDOM - /* Define to 1 if stdbool.h conforms to C99. */ #undef HAVE_STDBOOL_H diff --git a/src/include/pg_config_manual.h b/src/include/pg_config_manual.h index 225c5b87cc..427ffabd14 100644 --- a/src/include/pg_config_manual.h +++ b/src/include/pg_config_manual.h @@ -235,17 +235,6 @@ #define DEFAULT_EVENT_SOURCE "PostgreSQL" /* - * The random() function is expected to yield values between 0 and - * MAX_RANDOM_VALUE. Currently, all known implementations yield - * 0..2^31-1, so we just hardwire this constant. We could do a - * configure test if it proves to be necessary. CAUTION: Think not to - * replace this with RAND_MAX. RAND_MAX defines the maximum value of - * the older rand() function, which is often different from --- and - * considerably inferior to --- random(). - */ -#define MAX_RANDOM_VALUE PG_INT32_MAX - -/* * On PPC machines, decide whether to use the mutex hint bit in LWARX * instructions. Setting the hint bit will slightly improve spinlock * performance on POWER6 and later machines, but does nothing before that, diff --git a/src/include/port.h b/src/include/port.h index 49b4d38131..806fb795ed 100644 --- a/src/include/port.h +++ b/src/include/port.h @@ -362,11 +362,6 @@ extern int gettimeofday(struct timeval *tp, struct timezone *tzp); #define pgoff_t off_t #endif -extern double pg_erand48(unsigned short xseed[3]); -extern long pg_lrand48(void); -extern long pg_jrand48(unsigned short xseed[3]); -extern void pg_srand48(long seed); - #ifndef HAVE_FLS extern int fls(int mask); #endif @@ -452,10 +447,6 @@ extern size_t strlcpy(char *dst, const char *src, size_t siz); extern size_t strnlen(const char *str, size_t maxlen); #endif -#if !defined(HAVE_RANDOM) -extern long random(void); -#endif - #ifndef HAVE_SETENV extern int setenv(const char *name, const char *value, int overwrite); #endif @@ -464,10 +455,6 @@ extern int setenv(const char *name, const char *value, int overwrite); extern int unsetenv(const char *name); #endif -#ifndef HAVE_SRANDOM -extern void srandom(unsigned int seed); -#endif - #ifndef HAVE_DLOPEN extern void *dlopen(const char *file, int mode); extern void *dlsym(void *handle, const char *symbol); diff --git a/src/include/utils/sampling.h b/src/include/utils/sampling.h index a58d14281b..74ce8f9dc3 100644 --- a/src/include/utils/sampling.h +++ b/src/include/utils/sampling.h @@ -13,15 +13,14 @@ #ifndef SAMPLING_H #define SAMPLING_H +#include "common/pg_prng.h" #include "storage/block.h" /* for typedef BlockNumber */ /* Random generator for sampling code */ -typedef unsigned short SamplerRandomState[3]; - -extern void sampler_random_init_state(long seed, - SamplerRandomState randstate); -extern double sampler_random_fract(SamplerRandomState randstate); +extern void sampler_random_init_state(uint32 seed, + pg_prng_state *randstate); +extern double sampler_random_fract(pg_prng_state *randstate); /* Block sampling methods */ @@ -32,13 +31,13 @@ typedef struct int n; /* desired sample size */ BlockNumber t; /* current block number */ int m; /* blocks selected so far */ - SamplerRandomState randstate; /* random generator state */ + pg_prng_state randstate; /* random generator state */ } BlockSamplerData; typedef BlockSamplerData *BlockSampler; extern BlockNumber BlockSampler_Init(BlockSampler bs, BlockNumber nblocks, - int samplesize, long randseed); + int samplesize, uint32 randseed); extern bool BlockSampler_HasMore(BlockSampler bs); extern BlockNumber BlockSampler_Next(BlockSampler bs); @@ -47,7 +46,7 @@ extern BlockNumber BlockSampler_Next(BlockSampler bs); typedef struct { double W; - SamplerRandomState randstate; /* random generator state */ + pg_prng_state randstate; /* random generator state */ } ReservoirStateData; typedef ReservoirStateData *ReservoirState; diff --git a/src/port/Makefile b/src/port/Makefile index 52dbf5783f..b3754d8940 100644 --- a/src/port/Makefile +++ b/src/port/Makefile @@ -42,7 +42,6 @@ OBJS = \ $(PG_CRC32C_OBJS) \ bsearch_arg.o \ chklocale.o \ - erand48.o \ inet_net_ntop.o \ noblock.o \ path.o \ diff --git a/src/port/erand48.c b/src/port/erand48.c deleted file mode 100644 index a82ea94220..0000000000 --- a/src/port/erand48.c +++ /dev/null @@ -1,136 +0,0 @@ -/*------------------------------------------------------------------------- - * - * erand48.c - * - * This file supplies pg_erand48() and related functions, which except - * for the names are just like the POSIX-standard erand48() family. - * (We don't supply the full set though, only the ones we have found use - * for in Postgres. In particular, we do *not* implement lcong48(), so - * that there is no need for the multiplier and addend to be variable.) - * - * We used to test for an operating system version rather than - * unconditionally using our own, but (1) some versions of Cygwin have a - * buggy erand48() that always returns zero and (2) as of 2011, glibc's - * erand48() is strangely coded to be almost-but-not-quite thread-safe, - * which doesn't matter for the backend but is important for pgbench. - * - * Portions Copyright (c) 1996-2021, PostgreSQL Global Development Group - * - * Portions Copyright (c) 1993 Martin Birgmeier - * All rights reserved. - * - * You may redistribute unmodified or modified versions of this source - * code provided that the above copyright notice and this and the - * following conditions are retained. - * - * This software is provided ``as is'', and comes with no warranties - * of any kind. I shall in no event be liable for anything that happens - * to anyone/anything when using this software. - * - * IDENTIFICATION - * src/port/erand48.c - * - *------------------------------------------------------------------------- - */ - -#include "c.h" - -#include <math.h> - -/* These values are specified by POSIX */ -#define RAND48_MULT UINT64CONST(0x0005deece66d) -#define RAND48_ADD UINT64CONST(0x000b) - -/* POSIX specifies 0x330e's use in srand48, but the other bits are arbitrary */ -#define RAND48_SEED_0 (0x330e) -#define RAND48_SEED_1 (0xabcd) -#define RAND48_SEED_2 (0x1234) - -static unsigned short _rand48_seed[3] = { - RAND48_SEED_0, - RAND48_SEED_1, - RAND48_SEED_2 -}; - - -/* - * Advance the 48-bit value stored in xseed[] to the next "random" number. - * - * Also returns the value of that number --- without masking it to 48 bits. - * If caller uses the result, it must mask off the bits it wants. - */ -static uint64 -_dorand48(unsigned short xseed[3]) -{ - /* - * We do the arithmetic in uint64; any type wider than 48 bits would work. - */ - uint64 in; - uint64 out; - - in = (uint64) xseed[2] << 32 | (uint64) xseed[1] << 16 | (uint64) xseed[0]; - - out = in * RAND48_MULT + RAND48_ADD; - - xseed[0] = out & 0xFFFF; - xseed[1] = (out >> 16) & 0xFFFF; - xseed[2] = (out >> 32) & 0xFFFF; - - return out; -} - - -/* - * Generate a random floating-point value using caller-supplied state. - * Values are uniformly distributed over the interval [0.0, 1.0). - */ -double -pg_erand48(unsigned short xseed[3]) -{ - uint64 x = _dorand48(xseed); - - return ldexp((double) (x & UINT64CONST(0xFFFFFFFFFFFF)), -48); -} - -/* - * Generate a random non-negative integral value using internal state. - * Values are uniformly distributed over the interval [0, 2^31). - */ -long -pg_lrand48(void) -{ - uint64 x = _dorand48(_rand48_seed); - - return (x >> 17) & UINT64CONST(0x7FFFFFFF); -} - -/* - * Generate a random signed integral value using caller-supplied state. - * Values are uniformly distributed over the interval [-2^31, 2^31). - */ -long -pg_jrand48(unsigned short xseed[3]) -{ - uint64 x = _dorand48(xseed); - - return (int32) ((x >> 16) & UINT64CONST(0xFFFFFFFF)); -} - -/* - * Initialize the internal state using the given seed. - * - * Per POSIX, this uses only 32 bits from "seed" even if "long" is wider. - * Hence, the set of possible seed values is smaller than it could be. - * Better practice is to use caller-supplied state and initialize it with - * random bits obtained from a high-quality source of random bits. - * - * Note: POSIX specifies a function seed48() that allows all 48 bits - * of the internal state to be set, but we don't currently support that. - */ -void -pg_srand48(long seed) -{ - _rand48_seed[0] = RAND48_SEED_0; - _rand48_seed[1] = (unsigned short) seed; - _rand48_seed[2] = (unsigned short) (seed >> 16); -} diff --git a/src/port/random.c b/src/port/random.c deleted file mode 100644 index 2dd59a0829..0000000000 --- a/src/port/random.c +++ /dev/null @@ -1,25 +0,0 @@ -/*------------------------------------------------------------------------- - * - * random.c - * random() wrapper - * - * Portions Copyright (c) 1996-2021, PostgreSQL Global Development Group - * Portions Copyright (c) 1994, Regents of the University of California - * - * - * IDENTIFICATION - * src/port/random.c - * - *------------------------------------------------------------------------- - */ - -#include "c.h" - -#include <math.h> - - -long -random(void) -{ - return pg_lrand48(); -} diff --git a/src/port/srandom.c b/src/port/srandom.c deleted file mode 100644 index cf1007b2ef..0000000000 --- a/src/port/srandom.c +++ /dev/null @@ -1,25 +0,0 @@ -/*------------------------------------------------------------------------- - * - * srandom.c - * srandom() wrapper - * - * Portions Copyright (c) 1996-2021, PostgreSQL Global Development Group - * Portions Copyright (c) 1994, Regents of the University of California - * - * - * IDENTIFICATION - * src/port/srandom.c - * - *------------------------------------------------------------------------- - */ - -#include "c.h" - -#include <math.h> - - -void -srandom(unsigned int seed) -{ - pg_srand48((long int) seed); -} diff --git a/src/test/modules/test_bloomfilter/test_bloomfilter.c b/src/test/modules/test_bloomfilter/test_bloomfilter.c index 96c5011428..7109f0476c 100644 --- a/src/test/modules/test_bloomfilter/test_bloomfilter.c +++ b/src/test/modules/test_bloomfilter/test_bloomfilter.c @@ -12,6 +12,7 @@ */ #include "postgres.h" +#include "common/pg_prng.h" #include "fmgr.h" #include "lib/bloomfilter.h" #include "miscadmin.h" @@ -83,9 +84,8 @@ create_and_test_bloom(int power, int64 nelements, int callerseed) * Generate random seed, or use caller's. Seed should always be a * positive value less than or equal to PG_INT32_MAX, to ensure that any * random seed can be recreated through callerseed if the need arises. - * (Don't assume that RAND_MAX cannot exceed PG_INT32_MAX.) */ - seed = callerseed < 0 ? random() % PG_INT32_MAX : callerseed; + seed = callerseed < 0 ? pg_prng_int32p(&pg_global_prng_state) : callerseed; /* Create Bloom filter, populate it, and report on false positive rate */ filter = bloom_create(nelements, bloom_work_mem, seed); diff --git a/src/test/modules/test_integerset/test_integerset.c b/src/test/modules/test_integerset/test_integerset.c index 21c6f49b37..58ffff89b3 100644 --- a/src/test/modules/test_integerset/test_integerset.c +++ b/src/test/modules/test_integerset/test_integerset.c @@ -12,6 +12,7 @@ */ #include "postgres.h" +#include "common/pg_prng.h" #include "fmgr.h" #include "lib/integerset.h" #include "miscadmin.h" @@ -248,8 +249,7 @@ test_pattern(const test_spec *spec) * only a small part of the integer space is used. We would very * rarely hit values that are actually in the set. */ - x = (pg_lrand48() << 31) | pg_lrand48(); - x = x % (last_int + 1000); + x = pg_prng_uint64_range(&pg_global_prng_state, 0, last_int + 1000); /* Do we expect this value to be present in the set? */ if (x >= last_int) @@ -571,7 +571,7 @@ test_huge_distances(void) */ while (num_values < 1000) { - val += pg_lrand48(); + val += pg_prng_uint32(&pg_global_prng_state); values[num_values++] = val; } diff --git a/src/test/modules/test_rbtree/test_rbtree.c b/src/test/modules/test_rbtree/test_rbtree.c index 713ebd1b26..646c6e42fa 100644 --- a/src/test/modules/test_rbtree/test_rbtree.c +++ b/src/test/modules/test_rbtree/test_rbtree.c @@ -13,6 +13,7 @@ #include "postgres.h" +#include "common/pg_prng.h" #include "fmgr.h" #include "lib/rbtree.h" #include "utils/memutils.h" @@ -108,7 +109,7 @@ GetPermutation(int size) */ for (i = 1; i < size; i++) { - int j = random() % (i + 1); + int j = pg_prng_uint64_range(&pg_global_prng_state, 0, i); if (j < i) /* avoid fetching undefined data if j=i */ permutation[i] = permutation[j]; @@ -320,7 +321,7 @@ testdelete(int size, int delsize) for (i = 0; i < delsize; i++) { - int k = random() % size; + int k = pg_prng_uint64_range(&pg_global_prng_state, 0, size - 1); while (chosen[k]) k = (k + 1) % size; diff --git a/src/tools/msvc/Mkvcbuild.pm b/src/tools/msvc/Mkvcbuild.pm index 41172eab36..5a374a4727 100644 --- a/src/tools/msvc/Mkvcbuild.pm +++ b/src/tools/msvc/Mkvcbuild.pm @@ -99,9 +99,9 @@ sub mkvcbuild $solution = CreateSolution($vsVersion, $config); our @pgportfiles = qw( - chklocale.c explicit_bzero.c fls.c getpeereid.c getrusage.c inet_aton.c random.c - srandom.c getaddrinfo.c gettimeofday.c inet_net_ntop.c kill.c open.c - erand48.c snprintf.c strlcat.c strlcpy.c dirmod.c noblock.c path.c + chklocale.c explicit_bzero.c fls.c getpeereid.c getrusage.c inet_aton.c + getaddrinfo.c gettimeofday.c inet_net_ntop.c kill.c open.c + snprintf.c strlcat.c strlcpy.c dirmod.c noblock.c path.c dirent.c dlopen.c getopt.c getopt_long.c link.c pread.c preadv.c pwrite.c pwritev.c pg_bitutils.c pg_strong_random.c pgcheckdir.c pgmkdirp.c pgsleep.c pgstrcasecmp.c @@ -127,9 +127,9 @@ sub mkvcbuild config_info.c controldata_utils.c d2s.c encnames.c exec.c f2s.c file_perm.c file_utils.c hashfn.c ip.c jsonapi.c keywords.c kwlookup.c link-canary.c md5_common.c - pg_get_line.c pg_lzcompress.c pgfnames.c psprintf.c relpath.c rmtree.c - saslprep.c scram-common.c string.c stringinfo.c unicode_norm.c username.c - wait_error.c wchar.c); + pg_get_line.c pg_lzcompress.c pg_prng.c pgfnames.c psprintf.c relpath.c + rmtree.c saslprep.c scram-common.c string.c stringinfo.c unicode_norm.c + username.c wait_error.c wchar.c); if ($solution->{options}->{openssl}) { diff --git a/src/tools/msvc/Solution.pm b/src/tools/msvc/Solution.pm index b0726c2eba..1cb31d929f 100644 --- a/src/tools/msvc/Solution.pm +++ b/src/tools/msvc/Solution.pm @@ -342,7 +342,6 @@ sub GenerateFiles HAVE_PTHREAD_IS_THREADED_NP => undef, HAVE_PTHREAD_PRIO_INHERIT => undef, HAVE_PWRITE => undef, - HAVE_RANDOM => undef, HAVE_READLINE_H => undef, HAVE_READLINE_HISTORY_H => undef, HAVE_READLINE_READLINE_H => undef, @@ -363,7 +362,6 @@ sub GenerateFiles HAVE_SHM_OPEN => undef, HAVE_SOCKLEN_T => 1, HAVE_SPINLOCKS => 1, - HAVE_SRANDOM => undef, HAVE_STDBOOL_H => 1, HAVE_STDINT_H => 1, HAVE_STDLIB_H => 1, diff --git a/src/tools/testint128.c b/src/tools/testint128.c index 71c345969a..47cc685ab4 100644 --- a/src/tools/testint128.c +++ b/src/tools/testint128.c @@ -27,6 +27,7 @@ #endif #include "common/int128.h" +#include "common/pg_prng.h" /* * We assume the parts of this union are laid out compatibly. @@ -62,26 +63,10 @@ my_int128_compare(int128 x, int128 y) } /* - * Get a random uint64 value. - * We don't assume random() is good for more than 16 bits. - */ -static uint64 -get_random_uint64(void) -{ - uint64 x; - - x = (uint64) (random() & 0xFFFF) << 48; - x |= (uint64) (random() & 0xFFFF) << 32; - x |= (uint64) (random() & 0xFFFF) << 16; - x |= (uint64) (random() & 0xFFFF); - return x; -} - -/* * Main program. * * Generates a lot of random numbers and tests the implementation for each. - * The results should be reproducible, since we don't call srandom(). + * The results should be reproducible, since we use a fixed PRNG seed. * * You can give a loop count if you don't like the default 1B iterations. */ @@ -90,6 +75,8 @@ main(int argc, char **argv) { long count; + pg_prng_seed(&pg_global_prng_state, 0); + if (argc >= 2) count = strtol(argv[1], NULL, 0); else @@ -97,9 +84,9 @@ main(int argc, char **argv) while (count-- > 0) { - int64 x = get_random_uint64(); - int64 y = get_random_uint64(); - int64 z = get_random_uint64(); + int64 x = pg_prng_uint64(&pg_global_prng_state); + int64 y = pg_prng_uint64(&pg_global_prng_state); + int64 z = pg_prng_uint64(&pg_global_prng_state); test128 t1; test128 t2; @@ -151,7 +138,7 @@ main(int argc, char **argv) t1.hl.hi = x; t1.hl.lo = y; t2.hl.hi = z; - t2.hl.lo = get_random_uint64(); + t2.hl.lo = pg_prng_uint64(&pg_global_prng_state); if (my_int128_compare(t1.i128, t2.i128) != int128_compare(t1.I128, t2.I128)) |