From 33a588fb736c03ff761678b86fcafc49a126bcd7 Mon Sep 17 00:00:00 2001 From: Tatsuo Ishii Date: Thu, 5 Jun 2025 18:59:25 +0900 Subject: [PATCH v3] Replace random() with pg_prng random function. Previously we used random() for choosing load balancing node. However PostgreSQL has better random number generator: pg_prng.c. This commit imports the file and use pg_prng_double() to generate random number in range [0.0, 1.0). The seed is generated using pg_strong_random(). Other notes regarding the port: - Some of functions in the file were not ported because they require additional library: pg_bitutils.c. In the future we may revisit and import pg_bitutils.c. - All conditional compiling regarding "sun" or "_sun" are removed. It seems the platform is not used for running pgpool anymore. - Since srandom() is not necessary any more, related code are removed from pgpool_main.c, child.c and pcp_worker.c. Author: Martijn van Duren , Tatsuo Ishii Discussion: [pgpool-hackers: 4588] Shuffle random functions and use better random numbers https://www.pgpool.net/pipermail/pgpool-hackers/2025-May/004589.html --- src/Makefile.am | 3 +- src/include/pool_type.h | 8 +- src/include/utils/pg_prng.h | 68 ++++++++ src/main/pgpool_main.c | 5 - src/pcp_con/pcp_worker.c | 6 +- src/protocol/child.c | 13 +- src/protocol/pool_pg_utils.c | 59 ++++--- src/utils/pg_prng.c | 329 +++++++++++++++++++++++++++++++++++ 8 files changed, 445 insertions(+), 46 deletions(-) create mode 100644 src/include/utils/pg_prng.h create mode 100644 src/utils/pg_prng.c diff --git a/src/Makefile.am b/src/Makefile.am index efc11cb68..56f4121c4 100644 --- a/src/Makefile.am +++ b/src/Makefile.am @@ -66,7 +66,8 @@ pgpool_SOURCES = main/main.c \ utils/pool_health_check_stats.c \ utils/psqlscan.l \ utils/pgstrcasecmp.c \ - utils/pg_strong_random.c + utils/pg_strong_random.c \ + utils/pg_prng.c utils/psqlscan.c: utils/psqlscan.l $(LEX) -o'utils/psqlscan.c' $< diff --git a/src/include/pool_type.h b/src/include/pool_type.h index d7cdf936a..8db8ed000 100644 --- a/src/include/pool_type.h +++ b/src/include/pool_type.h @@ -6,7 +6,7 @@ * pgpool: a language independent connection pool server for PostgreSQL * written by Tatsuo Ishii * - * Copyright (c) 2003-2015 PgPool Global Development Group + * Copyright (c) 2003-2025 PgPool Global Development Group * * Permission to use, copy, modify, and distribute this software and * its documentation for any purpose and without fee is hereby @@ -222,6 +222,12 @@ typedef uint8 bits8; /* >= 8 bits */ typedef uint16 bits16; /* >= 16 bits */ typedef uint32 bits32; /* >= 32 bits */ +/* + * 64-bit integers + */ +#define INT64CONST(x) INT64_C(x) +#define UINT64CONST(x) UINT64_C(x) + /* * stdint.h limits aren't guaranteed to be present and aren't guaranteed to * have compatible types with our fixed width types. So just define our own. diff --git a/src/include/utils/pg_prng.h b/src/include/utils/pg_prng.h new file mode 100644 index 000000000..edc20bee6 --- /dev/null +++ b/src/include/utils/pg_prng.h @@ -0,0 +1,68 @@ +/* + * This file was imported from PostgreSQL source code + * (src/include/common/pg_prng.h). + */ + +/*------------------------------------------------------------------------- + * + * Pseudo-Random Number Generator + * + * Portions Copyright (c) 2025, PgPool Global Development Group + * Portions Copyright (c) 2021-2025, 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(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 int64 pg_prng_int64_range(pg_prng_state *state, int64 rmin, int64 rmax); +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 double pg_prng_double_normal(pg_prng_state *state); +extern bool pg_prng_bool(pg_prng_state *state); + +#endif /* PG_PRNG_H */ diff --git a/src/main/pgpool_main.c b/src/main/pgpool_main.c index d74cf12b2..25298eb87 100644 --- a/src/main/pgpool_main.c +++ b/src/main/pgpool_main.c @@ -210,8 +210,6 @@ volatile User1SignalSlot *user1SignalSlot = NULL; /* User 1 signal slot on * shmem */ int current_child_process_count; -struct timeval random_start_time; - /* * To track health check process ids */ @@ -303,9 +301,6 @@ PgpoolMain(bool discard_status, bool clear_memcache_oidmaps) */ volatile bool first = true; - /* For PostmasterRandom */ - gettimeofday(&random_start_time, NULL); - processState = INITIALIZING; /* diff --git a/src/pcp_con/pcp_worker.c b/src/pcp_con/pcp_worker.c index de2658d5e..a5b88a898 100644 --- a/src/pcp_con/pcp_worker.c +++ b/src/pcp_con/pcp_worker.c @@ -4,7 +4,7 @@ * pgpool: a language independent connection pool server for PostgreSQL * written by Tatsuo Ishii * - * Copyright (c) 2003-2024 PgPool Global Development Group + * Copyright (c) 2003-2025 PgPool Global Development Group * * Permission to use, copy, modify, and distribute this software and * its documentation for any purpose and without fee is hereby @@ -112,7 +112,6 @@ pcp_worker_main(int port) char salt[4]; int random_salt = 0; - struct timeval uptime; char tos; int rsize; @@ -122,9 +121,6 @@ pcp_worker_main(int port) /* Identify myself via ps */ init_ps_display("", "", "", ""); - gettimeofday(&uptime, NULL); - srandom((unsigned int) (getpid() ^ uptime.tv_usec)); - /* set up signal handlers */ signal(SIGTERM, die); signal(SIGINT, die); diff --git a/src/protocol/child.c b/src/protocol/child.c index 53a4cce68..dc1bef392 100644 --- a/src/protocol/child.c +++ b/src/protocol/child.c @@ -5,7 +5,7 @@ * pgpool: a language independent connection pool server for PostgreSQL * written by Tatsuo Ishii * - * Copyright (c) 2003-2024 PgPool Global Development Group + * Copyright (c) 2003-2025 PgPool Global Development Group * * Permission to use, copy, modify, and distribute this software and * its documentation for any purpose and without fee is hereby @@ -153,8 +153,6 @@ do_child(int *fds) { sigjmp_buf local_sigjmp_buf; POOL_CONNECTION_POOL *volatile backend = NULL; - struct timeval now; - struct timezone tz; /* counter for child_max_connections. "volatile" declaration is necessary * so that this is counted up even if long jump is issued due to @@ -214,15 +212,6 @@ do_child(int *fds) /* Initialize per process context */ pool_init_process_context(); - /* initialize random seed */ - gettimeofday(&now, &tz); - -#if defined(sun) || defined(__sun) - srand((unsigned int) now.tv_usec); -#else - srandom((unsigned int) now.tv_usec); -#endif - /* initialize connection pool */ if (pool_init_cp()) { diff --git a/src/protocol/pool_pg_utils.c b/src/protocol/pool_pg_utils.c index 25942b6cc..ccbe2b03c 100644 --- a/src/protocol/pool_pg_utils.c +++ b/src/protocol/pool_pg_utils.c @@ -3,7 +3,7 @@ * pgpool: a language independent connection pool server for PostgreSQL * written by Tatsuo Ishii * - * Copyright (c) 2003-2020 PgPool Global Development Group + * Copyright (c) 2003-2025 PgPool Global Development Group * * Permission to use, copy, modify, and distribute this software and * its documentation for any purpose and without fee is hereby @@ -28,6 +28,7 @@ #include "protocol/pool_connection_pool.h" #include "utils/palloc.h" #include "utils/memutils.h" +#include "utils/pg_prng.h" #include "utils/pool_ipc.h" #include "utils/pool_stream.h" #include "utils/pool_ssl.h" @@ -44,6 +45,8 @@ static void free_persistent_db_connection_memory(POOL_CONNECTION_POOL_SLOT * cp) static void si_enter_critical_region(void); static void si_leave_critical_region(void); +static void initialize_prng(pg_prng_state *state); + /* * create a persistent connection */ @@ -299,7 +302,8 @@ pool_free_startup_packet(StartupPacket *sp) /* * Select load balancing node. This function is called when: * 1) client connects - * 2) the node previously selected for the load balance node is down + * 2) an SQL executes (if statement_level_load_balance is enabled) + * 3) the node previously selected for the load balance node is down */ int select_load_balancing_node(void) @@ -317,6 +321,9 @@ select_load_balancing_node(void) uint64 lowest_delay; int lowest_delay_nodes[NUM_BACKENDS]; + /* prng state data for load balancing */ + static pg_prng_state backsel_state; + /* * -2 indicates there's no database_redirect_preference_list. -1 indicates * database_redirect_preference_list exists and any of standby nodes @@ -324,11 +331,10 @@ select_load_balancing_node(void) */ int suggested_node_id = -2; -#if defined(sun) || defined(__sun) - r = (((double) rand()) / RAND_MAX); -#else - r = (((double) random()) / RAND_MAX); -#endif + /* initialize prng if necessary */ + initialize_prng(&backsel_state); + + r = pg_prng_double(&backsel_state); /* * Check user_redirect_preference_list @@ -490,11 +496,7 @@ select_load_balancing_node(void) } } -#if defined(sun) || defined(__sun) - r = (((double) rand()) / RAND_MAX) * total_weight; -#else - r = (((double) random()) / RAND_MAX) * total_weight; -#endif + r = pg_prng_double(&backsel_state) * total_weight; selected_slot = PRIMARY_NODE_ID; total_weight = 0.0; @@ -573,11 +575,7 @@ select_load_balancing_node(void) } } -#if defined(sun) || defined(__sun) - r = (((double) rand()) / RAND_MAX) * total_weight; -#else - r = (((double) random()) / RAND_MAX) * total_weight; -#endif + r = pg_prng_double(&backsel_state) * total_weight; total_weight = 0.0; for (i = 0; i < NUM_BACKENDS; i++) @@ -642,11 +640,7 @@ select_load_balancing_node(void) } } -#if defined(sun) || defined(__sun) - r = (((double) rand()) / RAND_MAX) * total_weight; -#else - r = (((double) random()) / RAND_MAX) * total_weight; -#endif + r = pg_prng_double(&backsel_state) * total_weight; selected_slot = PRIMARY_NODE_ID; @@ -676,6 +670,27 @@ select_load_balancing_node(void) return selected_slot; } +/* + * initialize_prng() - + * + * Initialize (seed) the PRNG, if not done yet in this process. + */ +static void +initialize_prng(pg_prng_state *state) +{ + static bool prng_seed_set = false; + uint64 seed; + + if (unlikely(!prng_seed_set)) + { + /* initialize prng */ + if (!pg_strong_random(&seed, sizeof(seed))) + seed = UINT64CONST(1); /* Pick a value, as long as it spreads */ + pg_prng_seed(state, seed); + prng_seed_set = true; + } +} + /* * Returns PostgreSQL version. * The returned PgVersion struct is in static memory. diff --git a/src/utils/pg_prng.c b/src/utils/pg_prng.c new file mode 100644 index 000000000..cb21a1af9 --- /dev/null +++ b/src/utils/pg_prng.c @@ -0,0 +1,329 @@ +/* + * This file was imported from PostgreSQL source code + * (src/common/pg_prng.c). + */ + +/*------------------------------------------------------------------------- + * + * 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 + * + * Portions Copyright (c) 2025, PgPool Global Development Group + * Portions Copyright (c) 2021-2025, PostgreSQL Global Development Group + * + * src/common/pg_prng.c + * + *------------------------------------------------------------------------- + */ + +#include "pool.h" + +#include + +#include "utils/pg_prng.h" + +/* X/Open (XSI) requires to provide M_PI, but core POSIX does not */ +#ifndef M_PI +#define M_PI 3.14159265358979323846 +#endif + + +/* 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); +} + +/* + * We ignore some functions because we do not port pg_bitutils.c (yet). + */ +#ifdef NOT_USED +/* + * 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); +} +#endif + +/* + * 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)); +} + +#ifdef NOT_USED +/* + * Select a random int64 uniformly from the range [rmin, rmax]. + * If the range is empty, rmin is always produced. + */ +int64 +pg_prng_int64_range(pg_prng_state *state, int64 rmin, int64 rmax) +{ + int64 val; + + if (likely(rmax > rmin)) + { + uint64 uval; + + /* + * Use pg_prng_uint64_range(). Can't simply pass it rmin and rmax, + * since (uint64) rmin will be larger than (uint64) rmax if rmin < 0. + */ + uval = (uint64) rmin + + pg_prng_uint64_range(state, 0, (uint64) rmax - (uint64) rmin); + + /* + * Safely convert back to int64, avoiding implementation-defined + * behavior for values larger than PG_INT64_MAX. Modern compilers + * will reduce this to a simple assignment. + */ + if (uval > PG_INT64_MAX) + val = (int64) (uval - PG_INT64_MIN) + PG_INT64_MIN; + else + val = (int64) uval; + } + else + val = rmin; + + return val; +} +#endif + +/* + * 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 double from the normal distribution with + * mean = 0.0 and stddev = 1.0. + * + * To get a result from a different normal distribution use + * STDDEV * pg_prng_double_normal() + MEAN + * + * Uses https://en.wikipedia.org/wiki/Box%E2%80%93Muller_transform + */ +double +pg_prng_double_normal(pg_prng_state *state) +{ + double u1, + u2, + z0; + + /* + * pg_prng_double generates [0, 1), but for the basic version of the + * Box-Muller transform the two uniformly distributed random numbers are + * expected to be in (0, 1]; in particular we'd better not compute log(0). + */ + u1 = 1.0 - pg_prng_double(state); + u2 = 1.0 - pg_prng_double(state); + + /* Apply Box-Muller transform to get one normal-valued output */ + z0 = sqrt(-2.0 * log(u1)) * sin(2.0 * M_PI * u2); + return z0; +} + +/* + * Select a random boolean value. + */ +bool +pg_prng_bool(pg_prng_state *state) +{ + uint64 v = xoroshiro128ss(state); + + return (bool) (v >> 63); +} -- 2.25.1