pg.ddx.io pgsql-hackers@postgresql.org mailing list archive
help / color / mirror / Atom feedrandom() (was Re: New GUC to sample log queries)
33+ messages / 6 participants
[nested] [flat]
* random() (was Re: New GUC to sample log queries)
@ 2018-12-26 18:45 Tom Lane <tgl@sss.pgh.pa.us>
2018-12-26 19:08 ` Re: random() (was Re: New GUC to sample log queries) Peter Geoghegan <pg@bowt.ie>
2018-12-27 01:34 ` Re: random() (was Re: New GUC to sample log queries) Michael Paquier <michael@paquier.xyz>
2018-12-27 08:36 ` Re: random() (was Re: New GUC to sample log queries) Fabien COELHO <coelho@cri.ensmp.fr>
2018-12-28 12:10 ` Re: random() (was Re: New GUC to sample log queries) Adrien NAYRAT <adrien.nayrat@anayrat.info>
0 siblings, 4 replies; 33+ messages in thread
From: Tom Lane @ 2018-12-26 18:45 UTC (permalink / raw)
To: Alvaro Herrera <alvherre@2ndquadrant.com>; +Cc: Adrien Nayrat <adrien.nayrat@anayrat.info>; Thomas Munro <thomas.munro@enterprisedb.com>; Dmitry Dolgov <9erthalion6@gmail.com>; Tomas Vondra <tomas.vondra@2ndquadrant.com>; vik.fearing@2ndquadrant.com, Robert Haas <robertmhaas@gmail.com>; Michael Paquier <michael@paquier.xyz>; David Rowley <david.rowley@2ndquadrant.com>; pgsql-hackers
Alvaro Herrera <alvherre@2ndquadrant.com> writes:
> Thanks! I pushed this with two changes -- one was to reword the docs a
> bit more, and the other was to compute in_sample only if it's going to
> be used (when exceeded is true). I hope this won't upset any compilers ...
> I wonder if there's any sensible way to verify the behavior in an
> automated fashion. Who know what marvels we'd discover about the
> reliability/uniformity of random() across platforms.
So Coverity doesn't like this patch:
2250 in_sample = exceeded &&
2251 log_statement_sample_rate != 0 &&
2252 (log_statement_sample_rate == 1 ||
>>> CID 1441909: Security best practices violations (DC.WEAK_CRYPTO)
>>> "random" should not be used for security related applications, as linear congruential algorithms are too easy to break.
2253 random() <= log_statement_sample_rate * MAX_RANDOM_VALUE);
2254
2255 if ((exceeded && in_sample) || log_duration)
I am not sure I buy the argument that this is a security hazard, but
there are other reasons to question the use of random() here, some of
which you stated yourself above. Another one is that using random()
for internal purposes interferes with applications' possible use of
drandom() and setseed(), ie an application depending on getting a
particular random series would see different behavior depending on
whether this GUC is active or not.
I wonder whether we should establish a project policy to avoid use
of random() for internal purposes, ie try to get to a point where
drandom() is the only caller in the backend. A quick grep says
that there's a dozen or so callers, so this patch certainly isn't
the only offender ... but should we make an effort to convert them
all to use, say, pg_erand48()? I think all the existing callers
could happily share a process-wide random state, so we could make
a wrapper that's no harder to use than random().
Another idea, which would be a lot less prone to breakage by
add-on code, is to change drandom() and setseed() to themselves
use pg_erand48() with a private seed. Then we could positively
promise that their behavior isn't affected by anything else
(and it'd become platform-independent, too, which it probably
isn't today). There would be a one-time compatibility breakage
for anyone who's depending on the exact current behavior, but
that might be OK considering how weak our guarantees are for it
right now.
regards, tom lane
^ permalink raw reply [nested|flat] 33+ messages in thread
* Re: random() (was Re: New GUC to sample log queries)
2018-12-26 18:45 random() (was Re: New GUC to sample log queries) Tom Lane <tgl@sss.pgh.pa.us>
@ 2018-12-26 19:08 ` Peter Geoghegan <pg@bowt.ie>
2018-12-26 19:31 ` Re: random() (was Re: New GUC to sample log queries) Tom Lane <tgl@sss.pgh.pa.us>
3 siblings, 1 reply; 33+ messages in thread
From: Peter Geoghegan @ 2018-12-26 19:08 UTC (permalink / raw)
To: Tom Lane <tgl@sss.pgh.pa.us>; +Cc: Alvaro Herrera <alvherre@2ndquadrant.com>; Adrien Nayrat <adrien.nayrat@anayrat.info>; Thomas Munro <thomas.munro@enterprisedb.com>; Dmitry Dolgov <9erthalion6@gmail.com>; Tomas Vondra <tomas.vondra@2ndquadrant.com>; Vik Fearing <vik.fearing@2ndquadrant.com>; Robert Haas <robertmhaas@gmail.com>; Michael Paquier <michael@paquier.xyz>; David Rowley <david.rowley@2ndquadrant.com>; pgsql-hackers
On Wed, Dec 26, 2018 at 10:45 AM Tom Lane <tgl@sss.pgh.pa.us> wrote:
> I wonder whether we should establish a project policy to avoid use
> of random() for internal purposes, ie try to get to a point where
> drandom() is the only caller in the backend. A quick grep says
> that there's a dozen or so callers, so this patch certainly isn't
> the only offender ... but should we make an effort to convert them
> all to use, say, pg_erand48()? I think all the existing callers
> could happily share a process-wide random state, so we could make
> a wrapper that's no harder to use than random().
I've used setseed() to make nbtree's "getting tired" behavior
deterministic for specific test cases I've developed -- the random()
choice of whether to split a page full of duplicates, or continue
right in search of free space becomes predictable. I've used this to
determine whether my nbtree patch's pg_upgrade'd indexes have
precisely the same behavior as v3 indexes on the master branch
(precisely the same in terms of the structure of the final index
following a bulk load).
I'm not sure whether or not kind of debugging scenario is worth giving
much weight to going forward, but it's something to consider. It seems
generally useful to be able to force deterministic-ish behavior in a
single session. I don't expect that the test case is even a bit
portable, but the technique was quite effective.
--
Peter Geoghegan
^ permalink raw reply [nested|flat] 33+ messages in thread
* Re: random() (was Re: New GUC to sample log queries)
2018-12-26 18:45 random() (was Re: New GUC to sample log queries) Tom Lane <tgl@sss.pgh.pa.us>
2018-12-26 19:08 ` Re: random() (was Re: New GUC to sample log queries) Peter Geoghegan <pg@bowt.ie>
@ 2018-12-26 19:31 ` Tom Lane <tgl@sss.pgh.pa.us>
2018-12-26 19:46 ` Re: random() (was Re: New GUC to sample log queries) Peter Geoghegan <pg@bowt.ie>
0 siblings, 1 reply; 33+ messages in thread
From: Tom Lane @ 2018-12-26 19:31 UTC (permalink / raw)
To: Peter Geoghegan <pg@bowt.ie>; +Cc: Alvaro Herrera <alvherre@2ndquadrant.com>; Adrien Nayrat <adrien.nayrat@anayrat.info>; Thomas Munro <thomas.munro@enterprisedb.com>; Dmitry Dolgov <9erthalion6@gmail.com>; Tomas Vondra <tomas.vondra@2ndquadrant.com>; Vik Fearing <vik.fearing@2ndquadrant.com>; Robert Haas <robertmhaas@gmail.com>; Michael Paquier <michael@paquier.xyz>; David Rowley <david.rowley@2ndquadrant.com>; pgsql-hackers
Peter Geoghegan <pg@bowt.ie> writes:
> On Wed, Dec 26, 2018 at 10:45 AM Tom Lane <tgl@sss.pgh.pa.us> wrote:
>> I wonder whether we should establish a project policy to avoid use
>> of random() for internal purposes, ie try to get to a point where
>> drandom() is the only caller in the backend. A quick grep says
>> that there's a dozen or so callers, so this patch certainly isn't
>> the only offender ... but should we make an effort to convert them
>> all to use, say, pg_erand48()? I think all the existing callers
>> could happily share a process-wide random state, so we could make
>> a wrapper that's no harder to use than random().
> I've used setseed() to make nbtree's "getting tired" behavior
> deterministic for specific test cases I've developed -- the random()
> choice of whether to split a page full of duplicates, or continue
> right in search of free space becomes predictable. I've used this to
> determine whether my nbtree patch's pg_upgrade'd indexes have
> precisely the same behavior as v3 indexes on the master branch
> (precisely the same in terms of the structure of the final index
> following a bulk load).
TBH, I'd call it a bug --- maybe even a low-grade security hazard
--- that it's possible to affect that from user level.
In fact, contemplating that for a bit: it is possible, as things
stand in HEAD, for a user to control which of his statements will
get logged if the DBA has enabled log_statement_sample_rate.
It doesn't take a lot of creativity to think of ways to abuse that.
So maybe Coverity had the right idea to start with.
There might well be debugging value in affecting internal PRNG usages,
but let's please not think it's a good idea that that's trivially
reachable from SQL.
regards, tom lane
^ permalink raw reply [nested|flat] 33+ messages in thread
* Re: random() (was Re: New GUC to sample log queries)
2018-12-26 18:45 random() (was Re: New GUC to sample log queries) Tom Lane <tgl@sss.pgh.pa.us>
2018-12-26 19:08 ` Re: random() (was Re: New GUC to sample log queries) Peter Geoghegan <pg@bowt.ie>
2018-12-26 19:31 ` Re: random() (was Re: New GUC to sample log queries) Tom Lane <tgl@sss.pgh.pa.us>
@ 2018-12-26 19:46 ` Peter Geoghegan <pg@bowt.ie>
2018-12-26 19:56 ` Re: random() (was Re: New GUC to sample log queries) Peter Geoghegan <pg@bowt.ie>
0 siblings, 1 reply; 33+ messages in thread
From: Peter Geoghegan @ 2018-12-26 19:46 UTC (permalink / raw)
To: Tom Lane <tgl@sss.pgh.pa.us>; +Cc: Alvaro Herrera <alvherre@2ndquadrant.com>; Adrien Nayrat <adrien.nayrat@anayrat.info>; Thomas Munro <thomas.munro@enterprisedb.com>; Dmitry Dolgov <9erthalion6@gmail.com>; Tomas Vondra <tomas.vondra@2ndquadrant.com>; Vik Fearing <vik.fearing@2ndquadrant.com>; Robert Haas <robertmhaas@gmail.com>; Michael Paquier <michael@paquier.xyz>; David Rowley <david.rowley@2ndquadrant.com>; pgsql-hackers
On Wed, Dec 26, 2018 at 11:31 AM Tom Lane <tgl@sss.pgh.pa.us> wrote:
> I've used setseed() to make nbtree's "getting tired" behavior
> > deterministic for specific test cases I've developed -- the random()
> > choice of whether to split a page full of duplicates, or continue
> > right in search of free space becomes predictable.
> TBH, I'd call it a bug --- maybe even a low-grade security hazard
> --- that it's possible to affect that from user level.
I don't disagree with that conclusion. Deterministic behavior is
always preferable to random behavior when the randomness is not truly
necessary.
> There might well be debugging value in affecting internal PRNG usages,
> but let's please not think it's a good idea that that's trivially
> reachable from SQL.
I hesitate to say that there is much value beyond the value that I've
found in this one instance. Maybe the remaining cases where this
technique could be applied just aren't very interesting.
--
Peter Geoghegan
^ permalink raw reply [nested|flat] 33+ messages in thread
* Re: random() (was Re: New GUC to sample log queries)
2018-12-26 18:45 random() (was Re: New GUC to sample log queries) Tom Lane <tgl@sss.pgh.pa.us>
2018-12-26 19:08 ` Re: random() (was Re: New GUC to sample log queries) Peter Geoghegan <pg@bowt.ie>
2018-12-26 19:31 ` Re: random() (was Re: New GUC to sample log queries) Tom Lane <tgl@sss.pgh.pa.us>
2018-12-26 19:46 ` Re: random() (was Re: New GUC to sample log queries) Peter Geoghegan <pg@bowt.ie>
@ 2018-12-26 19:56 ` Peter Geoghegan <pg@bowt.ie>
2018-12-26 20:19 ` Re: random() (was Re: New GUC to sample log queries) Tom Lane <tgl@sss.pgh.pa.us>
0 siblings, 1 reply; 33+ messages in thread
From: Peter Geoghegan @ 2018-12-26 19:56 UTC (permalink / raw)
To: Tom Lane <tgl@sss.pgh.pa.us>; +Cc: Alvaro Herrera <alvherre@2ndquadrant.com>; Adrien Nayrat <adrien.nayrat@anayrat.info>; Thomas Munro <thomas.munro@enterprisedb.com>; Dmitry Dolgov <9erthalion6@gmail.com>; Tomas Vondra <tomas.vondra@2ndquadrant.com>; Vik Fearing <vik.fearing@2ndquadrant.com>; Robert Haas <robertmhaas@gmail.com>; Michael Paquier <michael@paquier.xyz>; David Rowley <david.rowley@2ndquadrant.com>; pgsql-hackers
On Wed, Dec 26, 2018 at 11:46 AM Peter Geoghegan <pg@bowt.ie> wrote:
> > There might well be debugging value in affecting internal PRNG usages,
> > but let's please not think it's a good idea that that's trivially
> > reachable from SQL.
>
> I hesitate to say that there is much value beyond the value that I've
> found in this one instance. Maybe the remaining cases where this
> technique could be applied just aren't very interesting.
Actually, it looks like there may be several cases that are quite
similar to the "getting tired" case that I took an interest in. You
have spgdoinsert(), gistchoose(), and gin_rand()/dropItem(), just for
starters -- those all seem to affect the final structure of an index.
I'm beginning to think that the technique that I came up with to make
"getting tired" deterministic ought to be supporting as a debugging
option if we're to do away with internal use of the generic/seedable
backend PRNG.
--
Peter Geoghegan
^ permalink raw reply [nested|flat] 33+ messages in thread
* Re: random() (was Re: New GUC to sample log queries)
2018-12-26 18:45 random() (was Re: New GUC to sample log queries) Tom Lane <tgl@sss.pgh.pa.us>
2018-12-26 19:08 ` Re: random() (was Re: New GUC to sample log queries) Peter Geoghegan <pg@bowt.ie>
2018-12-26 19:31 ` Re: random() (was Re: New GUC to sample log queries) Tom Lane <tgl@sss.pgh.pa.us>
2018-12-26 19:46 ` Re: random() (was Re: New GUC to sample log queries) Peter Geoghegan <pg@bowt.ie>
2018-12-26 19:56 ` Re: random() (was Re: New GUC to sample log queries) Peter Geoghegan <pg@bowt.ie>
@ 2018-12-26 20:19 ` Tom Lane <tgl@sss.pgh.pa.us>
2018-12-26 20:27 ` Re: random() (was Re: New GUC to sample log queries) Peter Geoghegan <pg@bowt.ie>
0 siblings, 1 reply; 33+ messages in thread
From: Tom Lane @ 2018-12-26 20:19 UTC (permalink / raw)
To: Peter Geoghegan <pg@bowt.ie>; +Cc: Alvaro Herrera <alvherre@2ndquadrant.com>; Adrien Nayrat <adrien.nayrat@anayrat.info>; Thomas Munro <thomas.munro@enterprisedb.com>; Dmitry Dolgov <9erthalion6@gmail.com>; Tomas Vondra <tomas.vondra@2ndquadrant.com>; Vik Fearing <vik.fearing@2ndquadrant.com>; Robert Haas <robertmhaas@gmail.com>; Michael Paquier <michael@paquier.xyz>; David Rowley <david.rowley@2ndquadrant.com>; pgsql-hackers
Peter Geoghegan <pg@bowt.ie> writes:
> I'm beginning to think that the technique that I came up with to make
> "getting tired" deterministic ought to be supporting as a debugging
> option if we're to do away with internal use of the generic/seedable
> backend PRNG.
I have no objection to providing such a thing as a debug option; I just
don't want it to be reachable from SQL (at least not without pieces
that aren't there normally, e.g. a loadable C function).
Replacing random() might actually make that easier not harder, since
we'd have more control over what happens when.
regards, tom lane
^ permalink raw reply [nested|flat] 33+ messages in thread
* Re: random() (was Re: New GUC to sample log queries)
2018-12-26 18:45 random() (was Re: New GUC to sample log queries) Tom Lane <tgl@sss.pgh.pa.us>
2018-12-26 19:08 ` Re: random() (was Re: New GUC to sample log queries) Peter Geoghegan <pg@bowt.ie>
2018-12-26 19:31 ` Re: random() (was Re: New GUC to sample log queries) Tom Lane <tgl@sss.pgh.pa.us>
2018-12-26 19:46 ` Re: random() (was Re: New GUC to sample log queries) Peter Geoghegan <pg@bowt.ie>
2018-12-26 19:56 ` Re: random() (was Re: New GUC to sample log queries) Peter Geoghegan <pg@bowt.ie>
2018-12-26 20:19 ` Re: random() (was Re: New GUC to sample log queries) Tom Lane <tgl@sss.pgh.pa.us>
@ 2018-12-26 20:27 ` Peter Geoghegan <pg@bowt.ie>
2018-12-26 21:21 ` Re: random() (was Re: New GUC to sample log queries) Tom Lane <tgl@sss.pgh.pa.us>
0 siblings, 1 reply; 33+ messages in thread
From: Peter Geoghegan @ 2018-12-26 20:27 UTC (permalink / raw)
To: Tom Lane <tgl@sss.pgh.pa.us>; +Cc: Alvaro Herrera <alvherre@2ndquadrant.com>; Adrien Nayrat <adrien.nayrat@anayrat.info>; Thomas Munro <thomas.munro@enterprisedb.com>; Dmitry Dolgov <9erthalion6@gmail.com>; Tomas Vondra <tomas.vondra@2ndquadrant.com>; Vik Fearing <vik.fearing@2ndquadrant.com>; Robert Haas <robertmhaas@gmail.com>; Michael Paquier <michael@paquier.xyz>; David Rowley <david.rowley@2ndquadrant.com>; pgsql-hackers
On Wed, Dec 26, 2018 at 12:19 PM Tom Lane <tgl@sss.pgh.pa.us> wrote:
> Replacing random() might actually make that easier not harder, since
> we'd have more control over what happens when.
That does seem useful. I'm in favor. But why does the function to seed
the internal PRNG have to be loadable? Can't it just be
superuser-only?
--
Peter Geoghegan
^ permalink raw reply [nested|flat] 33+ messages in thread
* Re: random() (was Re: New GUC to sample log queries)
2018-12-26 18:45 random() (was Re: New GUC to sample log queries) Tom Lane <tgl@sss.pgh.pa.us>
2018-12-26 19:08 ` Re: random() (was Re: New GUC to sample log queries) Peter Geoghegan <pg@bowt.ie>
2018-12-26 19:31 ` Re: random() (was Re: New GUC to sample log queries) Tom Lane <tgl@sss.pgh.pa.us>
2018-12-26 19:46 ` Re: random() (was Re: New GUC to sample log queries) Peter Geoghegan <pg@bowt.ie>
2018-12-26 19:56 ` Re: random() (was Re: New GUC to sample log queries) Peter Geoghegan <pg@bowt.ie>
2018-12-26 20:19 ` Re: random() (was Re: New GUC to sample log queries) Tom Lane <tgl@sss.pgh.pa.us>
2018-12-26 20:27 ` Re: random() (was Re: New GUC to sample log queries) Peter Geoghegan <pg@bowt.ie>
@ 2018-12-26 21:21 ` Tom Lane <tgl@sss.pgh.pa.us>
2018-12-26 21:48 ` Re: random() (was Re: New GUC to sample log queries) Peter Geoghegan <pg@bowt.ie>
0 siblings, 1 reply; 33+ messages in thread
From: Tom Lane @ 2018-12-26 21:21 UTC (permalink / raw)
To: Peter Geoghegan <pg@bowt.ie>; +Cc: Alvaro Herrera <alvherre@2ndquadrant.com>; Adrien Nayrat <adrien.nayrat@anayrat.info>; Thomas Munro <thomas.munro@enterprisedb.com>; Dmitry Dolgov <9erthalion6@gmail.com>; Tomas Vondra <tomas.vondra@2ndquadrant.com>; Vik Fearing <vik.fearing@2ndquadrant.com>; Robert Haas <robertmhaas@gmail.com>; Michael Paquier <michael@paquier.xyz>; David Rowley <david.rowley@2ndquadrant.com>; pgsql-hackers
Peter Geoghegan <pg@bowt.ie> writes:
> On Wed, Dec 26, 2018 at 12:19 PM Tom Lane <tgl@sss.pgh.pa.us> wrote:
>> Replacing random() might actually make that easier not harder, since
>> we'd have more control over what happens when.
> That does seem useful. I'm in favor. But why does the function to seed
> the internal PRNG have to be loadable? Can't it just be
> superuser-only?
That'd work as far as I'm concerned. (But I can hear Frost wanting
a built-in role for it ;-))
One thing we'd have to think about if we want to take this seriously
is whether a process-wide PRNG state is really adequate; if you're
trying to make a particular call site be deterministic, you'd likely
wish it weren't interfered with by other call sites. On the flip
side, having more call sites probably makes things more random and
thus better for normal usage. Not sure how to resolve that tension
(but I don't want to build a whole lot of new infrastructure here).
regards, tom lane
^ permalink raw reply [nested|flat] 33+ messages in thread
* Re: random() (was Re: New GUC to sample log queries)
2018-12-26 18:45 random() (was Re: New GUC to sample log queries) Tom Lane <tgl@sss.pgh.pa.us>
2018-12-26 19:08 ` Re: random() (was Re: New GUC to sample log queries) Peter Geoghegan <pg@bowt.ie>
2018-12-26 19:31 ` Re: random() (was Re: New GUC to sample log queries) Tom Lane <tgl@sss.pgh.pa.us>
2018-12-26 19:46 ` Re: random() (was Re: New GUC to sample log queries) Peter Geoghegan <pg@bowt.ie>
2018-12-26 19:56 ` Re: random() (was Re: New GUC to sample log queries) Peter Geoghegan <pg@bowt.ie>
2018-12-26 20:19 ` Re: random() (was Re: New GUC to sample log queries) Tom Lane <tgl@sss.pgh.pa.us>
2018-12-26 20:27 ` Re: random() (was Re: New GUC to sample log queries) Peter Geoghegan <pg@bowt.ie>
2018-12-26 21:21 ` Re: random() (was Re: New GUC to sample log queries) Tom Lane <tgl@sss.pgh.pa.us>
@ 2018-12-26 21:48 ` Peter Geoghegan <pg@bowt.ie>
0 siblings, 0 replies; 33+ messages in thread
From: Peter Geoghegan @ 2018-12-26 21:48 UTC (permalink / raw)
To: Tom Lane <tgl@sss.pgh.pa.us>; +Cc: Alvaro Herrera <alvherre@2ndquadrant.com>; Adrien Nayrat <adrien.nayrat@anayrat.info>; Thomas Munro <thomas.munro@enterprisedb.com>; Dmitry Dolgov <9erthalion6@gmail.com>; Tomas Vondra <tomas.vondra@2ndquadrant.com>; Vik Fearing <vik.fearing@2ndquadrant.com>; Robert Haas <robertmhaas@gmail.com>; Michael Paquier <michael@paquier.xyz>; David Rowley <david.rowley@2ndquadrant.com>; pgsql-hackers
On Wed, Dec 26, 2018 at 1:21 PM Tom Lane <tgl@sss.pgh.pa.us> wrote:
> One thing we'd have to think about if we want to take this seriously
> is whether a process-wide PRNG state is really adequate; if you're
> trying to make a particular call site be deterministic, you'd likely
> wish it weren't interfered with by other call sites. On the flip
> side, having more call sites probably makes things more random and
> thus better for normal usage. Not sure how to resolve that tension
> (but I don't want to build a whole lot of new infrastructure here).
I don't think that you need to resolve the tension -- I'd be fine with
continuing to have a process-wide PRNG that was cordoned-off for
internal use. I care about making behavior deterministic when running
an SQL script within a single backend. This can only be expected to
work when all inputs (non-random and random alike) are carefully
accounted for, including even the mutation of a seed value as the test
case runs. I also found myself disabling synchronized sequential
scanning within the same test case I mentioned, because they caused
false positive failures very occasionally. I can imagining a similar
test case where the tester has to worry about autovacuum running
ANALYZE, too (as it happens, these were all INSERT ... SELECT
statements, where that didn't seem to be an issue).
Trying to reason about the behavior of a call site in isolation seems
way too complicated to be practical. In general, there will never be a
standard way to think about this kind of debugging, and it would be
unreasonable to insist on providing any kind of standard framework.
It's a low-level tool, useful only to backend hackers.
--
Peter Geoghegan
^ permalink raw reply [nested|flat] 33+ messages in thread
* Re: random() (was Re: New GUC to sample log queries)
2018-12-26 18:45 random() (was Re: New GUC to sample log queries) Tom Lane <tgl@sss.pgh.pa.us>
@ 2018-12-27 01:34 ` Michael Paquier <michael@paquier.xyz>
2018-12-27 01:46 ` Re: random() (was Re: New GUC to sample log queries) Tom Lane <tgl@sss.pgh.pa.us>
3 siblings, 1 reply; 33+ messages in thread
From: Michael Paquier @ 2018-12-27 01:34 UTC (permalink / raw)
To: Tom Lane <tgl@sss.pgh.pa.us>; +Cc: Alvaro Herrera <alvherre@2ndquadrant.com>; Adrien Nayrat <adrien.nayrat@anayrat.info>; Thomas Munro <thomas.munro@enterprisedb.com>; Dmitry Dolgov <9erthalion6@gmail.com>; Tomas Vondra <tomas.vondra@2ndquadrant.com>; vik.fearing@2ndquadrant.com, Robert Haas <robertmhaas@gmail.com>; David Rowley <david.rowley@2ndquadrant.com>; pgsql-hackers
On Wed, Dec 26, 2018 at 01:45:00PM -0500, Tom Lane wrote:
> I am not sure I buy the argument that this is a security hazard, but
> there are other reasons to question the use of random() here, some of
> which you stated yourself above. I wonder whether we should
> establish a project policy to avoid use of random() for internal
> purposes, ie try to get to a point where drandom() is the only
> caller in the backend.
Agreed for all three points.
> A quick grep says that there's a dozen or so callers, so this patch
> certainly isn't the only offender ... but should we make an effort
> to convert them all to use, say, pg_erand48()? I think all the
> existing callers could happily share a process-wide random state,
> so we could make a wrapper that's no harder to use than random().
Another possibility would be to extend a bit more the use of
pg_strong_random(), though it is designed to really be used in cases
like authentication where the random bytes are strong for
cryptography. pg_erand48() would be a good step forward.
--
Michael
Attachments:
[application/pgp-signature] signature.asc (832B, ../../20181227013458.GF2106@paquier.xyz/2-signature.asc)
download
^ permalink raw reply [nested|flat] 33+ messages in thread
* Re: random() (was Re: New GUC to sample log queries)
2018-12-26 18:45 random() (was Re: New GUC to sample log queries) Tom Lane <tgl@sss.pgh.pa.us>
2018-12-27 01:34 ` Re: random() (was Re: New GUC to sample log queries) Michael Paquier <michael@paquier.xyz>
@ 2018-12-27 01:46 ` Tom Lane <tgl@sss.pgh.pa.us>
2018-12-27 02:04 ` Re: random() (was Re: New GUC to sample log queries) Michael Paquier <michael@paquier.xyz>
2018-12-27 02:20 ` Re: random() (was Re: New GUC to sample log queries) Peter Geoghegan <pg@bowt.ie>
0 siblings, 2 replies; 33+ messages in thread
From: Tom Lane @ 2018-12-27 01:46 UTC (permalink / raw)
To: Michael Paquier <michael@paquier.xyz>; +Cc: Alvaro Herrera <alvherre@2ndquadrant.com>; Adrien Nayrat <adrien.nayrat@anayrat.info>; Thomas Munro <thomas.munro@enterprisedb.com>; Dmitry Dolgov <9erthalion6@gmail.com>; Tomas Vondra <tomas.vondra@2ndquadrant.com>; vik.fearing@2ndquadrant.com, Robert Haas <robertmhaas@gmail.com>; David Rowley <david.rowley@2ndquadrant.com>; pgsql-hackers
Michael Paquier <michael@paquier.xyz> writes:
> On Wed, Dec 26, 2018 at 01:45:00PM -0500, Tom Lane wrote:
>> A quick grep says that there's a dozen or so callers, so this patch
>> certainly isn't the only offender ... but should we make an effort
>> to convert them all to use, say, pg_erand48()? I think all the
>> existing callers could happily share a process-wide random state,
>> so we could make a wrapper that's no harder to use than random().
> Another possibility would be to extend a bit more the use of
> pg_strong_random(), though it is designed to really be used in cases
> like authentication where the random bytes are strong for
> cryptography. pg_erand48() would be a good step forward.
I think pg_strong_random is overkill, and overly expensive, for
most if not all of the existing callers of random(). We already
changed the ones where it's important to be strong ...
One thing I was wondering is if we should try to enforce a policy
like this by putting, say,
#define random() pg_random()
into port.h or so. That would have the advantages of not having to touch
any existing calls and not having to worry too much about future patches
breaking the policy. On the other hand, it's conceivable that third-party
extensions might get annoyed with us for hijacking a libc function.
Thoughts?
regards, tom lane
^ permalink raw reply [nested|flat] 33+ messages in thread
* Re: random() (was Re: New GUC to sample log queries)
2018-12-26 18:45 random() (was Re: New GUC to sample log queries) Tom Lane <tgl@sss.pgh.pa.us>
2018-12-27 01:34 ` Re: random() (was Re: New GUC to sample log queries) Michael Paquier <michael@paquier.xyz>
2018-12-27 01:46 ` Re: random() (was Re: New GUC to sample log queries) Tom Lane <tgl@sss.pgh.pa.us>
@ 2018-12-27 02:04 ` Michael Paquier <michael@paquier.xyz>
1 sibling, 0 replies; 33+ messages in thread
From: Michael Paquier @ 2018-12-27 02:04 UTC (permalink / raw)
To: Tom Lane <tgl@sss.pgh.pa.us>; +Cc: Alvaro Herrera <alvherre@2ndquadrant.com>; Adrien Nayrat <adrien.nayrat@anayrat.info>; Thomas Munro <thomas.munro@enterprisedb.com>; Dmitry Dolgov <9erthalion6@gmail.com>; Tomas Vondra <tomas.vondra@2ndquadrant.com>; vik.fearing@2ndquadrant.com, Robert Haas <robertmhaas@gmail.com>; David Rowley <david.rowley@2ndquadrant.com>; pgsql-hackers
On Wed, Dec 26, 2018 at 08:46:25PM -0500, Tom Lane wrote:
> One thing I was wondering is if we should try to enforce a policy
> like this by putting, say,
>
> #define random() pg_random()
>
> into port.h or so. That would have the advantages of not having to touch
> any existing calls and not having to worry too much about future patches
> breaking the policy. On the other hand, it's conceivable that third-party
> extensions might get annoyed with us for hijacking a libc function.
> Thoughts?
Not much a fan of that for random() to be honest as we are talking
about 15 callers in the backend code and enforcing a call of in a
low-level library..
--
Michael
Attachments:
[application/pgp-signature] signature.asc (832B, ../../20181227020433.GH2106@paquier.xyz/2-signature.asc)
download
^ permalink raw reply [nested|flat] 33+ messages in thread
* Re: random() (was Re: New GUC to sample log queries)
2018-12-26 18:45 random() (was Re: New GUC to sample log queries) Tom Lane <tgl@sss.pgh.pa.us>
2018-12-27 01:34 ` Re: random() (was Re: New GUC to sample log queries) Michael Paquier <michael@paquier.xyz>
2018-12-27 01:46 ` Re: random() (was Re: New GUC to sample log queries) Tom Lane <tgl@sss.pgh.pa.us>
@ 2018-12-27 02:20 ` Peter Geoghegan <pg@bowt.ie>
2018-12-27 02:39 ` Re: random() (was Re: New GUC to sample log queries) Tom Lane <tgl@sss.pgh.pa.us>
1 sibling, 1 reply; 33+ messages in thread
From: Peter Geoghegan @ 2018-12-27 02:20 UTC (permalink / raw)
To: Tom Lane <tgl@sss.pgh.pa.us>; +Cc: Michael Paquier <michael@paquier.xyz>; Alvaro Herrera <alvherre@2ndquadrant.com>; Adrien Nayrat <adrien.nayrat@anayrat.info>; Thomas Munro <thomas.munro@enterprisedb.com>; Dmitry Dolgov <9erthalion6@gmail.com>; Tomas Vondra <tomas.vondra@2ndquadrant.com>; Vik Fearing <vik.fearing@2ndquadrant.com>; Robert Haas <robertmhaas@gmail.com>; David Rowley <david.rowley@2ndquadrant.com>; pgsql-hackers
On Wed, Dec 26, 2018 at 5:46 PM Tom Lane <tgl@sss.pgh.pa.us> wrote:
> I think pg_strong_random is overkill, and overly expensive, for
> most if not all of the existing callers of random(). We already
> changed the ones where it's important to be strong ...
+1.
There was a controversy a bit like this in the Python community a few
years ago [1]. I don't think you can trust somebody to write Postgres
backend code but not trust them to understand the security issues with
a fast user-space PRNG (I think that I'd be willing to say the same
thing about people that write Python programs of any consequence).
It's always possible to make a change that might stop someone from
introducing a bug. The question ought to be: why this change, and why
now?
[1] https://lwn.net/Articles/657269/
--
Peter Geoghegan
^ permalink raw reply [nested|flat] 33+ messages in thread
* Re: random() (was Re: New GUC to sample log queries)
2018-12-26 18:45 random() (was Re: New GUC to sample log queries) Tom Lane <tgl@sss.pgh.pa.us>
2018-12-27 01:34 ` Re: random() (was Re: New GUC to sample log queries) Michael Paquier <michael@paquier.xyz>
2018-12-27 01:46 ` Re: random() (was Re: New GUC to sample log queries) Tom Lane <tgl@sss.pgh.pa.us>
2018-12-27 02:20 ` Re: random() (was Re: New GUC to sample log queries) Peter Geoghegan <pg@bowt.ie>
@ 2018-12-27 02:39 ` Tom Lane <tgl@sss.pgh.pa.us>
2018-12-27 02:55 ` Re: random() (was Re: New GUC to sample log queries) Peter Geoghegan <pg@bowt.ie>
0 siblings, 1 reply; 33+ messages in thread
From: Tom Lane @ 2018-12-27 02:39 UTC (permalink / raw)
To: Peter Geoghegan <pg@bowt.ie>; +Cc: Michael Paquier <michael@paquier.xyz>; Alvaro Herrera <alvherre@2ndquadrant.com>; Adrien Nayrat <adrien.nayrat@anayrat.info>; Thomas Munro <thomas.munro@enterprisedb.com>; Dmitry Dolgov <9erthalion6@gmail.com>; Tomas Vondra <tomas.vondra@2ndquadrant.com>; Vik Fearing <vik.fearing@2ndquadrant.com>; Robert Haas <robertmhaas@gmail.com>; David Rowley <david.rowley@2ndquadrant.com>; pgsql-hackers
Peter Geoghegan <pg@bowt.ie> writes:
> It's always possible to make a change that might stop someone from
> introducing a bug. The question ought to be: why this change, and why
> now?
The point here is not to be cryptographically strong at every single
place where the backend might want a random number; I think we're
all agreed that we don't need that. To me, the point is to ensure that
the user-accessible random sequence is kept separate from internal uses,
and the potential security exposure in the new random-logging patch is
what justifies getting more worried about this than we were before.
Now, we could probably fix that with some less intrusive patch than
#define'ing random() --- in particular, if we give drandom and setseed
their own private PRNG state, we've really fixed the security exposure
without need to change anything else anywhere. So maybe we should
just do that and be happy.
regards, tom lane
^ permalink raw reply [nested|flat] 33+ messages in thread
* Re: random() (was Re: New GUC to sample log queries)
2018-12-26 18:45 random() (was Re: New GUC to sample log queries) Tom Lane <tgl@sss.pgh.pa.us>
2018-12-27 01:34 ` Re: random() (was Re: New GUC to sample log queries) Michael Paquier <michael@paquier.xyz>
2018-12-27 01:46 ` Re: random() (was Re: New GUC to sample log queries) Tom Lane <tgl@sss.pgh.pa.us>
2018-12-27 02:20 ` Re: random() (was Re: New GUC to sample log queries) Peter Geoghegan <pg@bowt.ie>
2018-12-27 02:39 ` Re: random() (was Re: New GUC to sample log queries) Tom Lane <tgl@sss.pgh.pa.us>
@ 2018-12-27 02:55 ` Peter Geoghegan <pg@bowt.ie>
2018-12-27 04:55 ` Re: random() (was Re: New GUC to sample log queries) Thomas Munro <thomas.munro@enterprisedb.com>
2018-12-27 19:33 ` Re: random() (was Re: New GUC to sample log queries) Tom Lane <tgl@sss.pgh.pa.us>
0 siblings, 2 replies; 33+ messages in thread
From: Peter Geoghegan @ 2018-12-27 02:55 UTC (permalink / raw)
To: Tom Lane <tgl@sss.pgh.pa.us>; +Cc: Michael Paquier <michael@paquier.xyz>; Alvaro Herrera <alvherre@2ndquadrant.com>; Adrien Nayrat <adrien.nayrat@anayrat.info>; Thomas Munro <thomas.munro@enterprisedb.com>; Dmitry Dolgov <9erthalion6@gmail.com>; Tomas Vondra <tomas.vondra@2ndquadrant.com>; Vik Fearing <vik.fearing@2ndquadrant.com>; Robert Haas <robertmhaas@gmail.com>; David Rowley <david.rowley@2ndquadrant.com>; pgsql-hackers
On Wed, Dec 26, 2018 at 6:39 PM Tom Lane <tgl@sss.pgh.pa.us> wrote:
> The point here is not to be cryptographically strong at every single
> place where the backend might want a random number; I think we're
> all agreed that we don't need that. To me, the point is to ensure that
> the user-accessible random sequence is kept separate from internal uses,
> and the potential security exposure in the new random-logging patch is
> what justifies getting more worried about this than we were before.
I agree that that's the point here.
> Now, we could probably fix that with some less intrusive patch than
> #define'ing random() --- in particular, if we give drandom and setseed
> their own private PRNG state, we've really fixed the security exposure
> without need to change anything else anywhere. So maybe we should
> just do that and be happy.
+1. I don't like the idea of #define'ing random() myself.
We're already making fairly broad assumptions about our having control
of the backend's PRNG state within InitProcessGlobals(). How should
this affect the new drandom()/setseed() private state, if at all?
--
Peter Geoghegan
^ permalink raw reply [nested|flat] 33+ messages in thread
* Re: random() (was Re: New GUC to sample log queries)
2018-12-26 18:45 random() (was Re: New GUC to sample log queries) Tom Lane <tgl@sss.pgh.pa.us>
2018-12-27 01:34 ` Re: random() (was Re: New GUC to sample log queries) Michael Paquier <michael@paquier.xyz>
2018-12-27 01:46 ` Re: random() (was Re: New GUC to sample log queries) Tom Lane <tgl@sss.pgh.pa.us>
2018-12-27 02:20 ` Re: random() (was Re: New GUC to sample log queries) Peter Geoghegan <pg@bowt.ie>
2018-12-27 02:39 ` Re: random() (was Re: New GUC to sample log queries) Tom Lane <tgl@sss.pgh.pa.us>
2018-12-27 02:55 ` Re: random() (was Re: New GUC to sample log queries) Peter Geoghegan <pg@bowt.ie>
@ 2018-12-27 04:55 ` Thomas Munro <thomas.munro@enterprisedb.com>
2018-12-27 19:36 ` Re: random() (was Re: New GUC to sample log queries) Tom Lane <tgl@sss.pgh.pa.us>
1 sibling, 1 reply; 33+ messages in thread
From: Thomas Munro @ 2018-12-27 04:55 UTC (permalink / raw)
To: Peter Geoghegan <pg@bowt.ie>; +Cc: Tom Lane <tgl@sss.pgh.pa.us>; Michael Paquier <michael@paquier.xyz>; Alvaro Herrera <alvherre@2ndquadrant.com>; Adrien Nayrat <adrien.nayrat@anayrat.info>; Dmitry Dolgov <9erthalion6@gmail.com>; Tomas Vondra <tomas.vondra@2ndquadrant.com>; Vik Fearing <vik.fearing@2ndquadrant.com>; Robert Haas <robertmhaas@gmail.com>; David Rowley <david.rowley@2ndquadrant.com>; pgsql-hackers
On Thu, Dec 27, 2018 at 3:55 PM Peter Geoghegan <pg@bowt.ie> wrote:
> On Wed, Dec 26, 2018 at 6:39 PM Tom Lane <tgl@sss.pgh.pa.us> wrote:
> > The point here is not to be cryptographically strong at every single
> > place where the backend might want a random number; I think we're
> > all agreed that we don't need that. To me, the point is to ensure that
> > the user-accessible random sequence is kept separate from internal uses,
> > and the potential security exposure in the new random-logging patch is
> > what justifies getting more worried about this than we were before.
>
> I agree that that's the point here.
+1, but I wonder if just separating them is enough. Is our seeding
algorithm good enough for this new purpose? The initial seed is 100%
predictable to a logged in user (it's made from the backend PID and
backend start time, which we tell you), and not even that hard to
guess from the outside, so I think Coverity's warning is an
understatement in this case. Even if we separate the PRNG state used
for internal stuff so that users can't clobber its seed from SQL,
wouldn't it be possible to predict which statements will survive the
log sampling filter given easily available information and a good
guess at how many times random() (or whatever similar thing) has been
called so far?
> > Now, we could probably fix that with some less intrusive patch than
> > #define'ing random() --- in particular, if we give drandom and setseed
> > their own private PRNG state, we've really fixed the security exposure
> > without need to change anything else anywhere. So maybe we should
> > just do that and be happy.
>
> +1. I don't like the idea of #define'ing random() myself.
+1, me neither.
--
Thomas Munro
http://www.enterprisedb.com
^ permalink raw reply [nested|flat] 33+ messages in thread
* Re: random() (was Re: New GUC to sample log queries)
2018-12-26 18:45 random() (was Re: New GUC to sample log queries) Tom Lane <tgl@sss.pgh.pa.us>
2018-12-27 01:34 ` Re: random() (was Re: New GUC to sample log queries) Michael Paquier <michael@paquier.xyz>
2018-12-27 01:46 ` Re: random() (was Re: New GUC to sample log queries) Tom Lane <tgl@sss.pgh.pa.us>
2018-12-27 02:20 ` Re: random() (was Re: New GUC to sample log queries) Peter Geoghegan <pg@bowt.ie>
2018-12-27 02:39 ` Re: random() (was Re: New GUC to sample log queries) Tom Lane <tgl@sss.pgh.pa.us>
2018-12-27 02:55 ` Re: random() (was Re: New GUC to sample log queries) Peter Geoghegan <pg@bowt.ie>
2018-12-27 04:55 ` Re: random() (was Re: New GUC to sample log queries) Thomas Munro <thomas.munro@enterprisedb.com>
@ 2018-12-27 19:36 ` Tom Lane <tgl@sss.pgh.pa.us>
2018-12-28 23:15 ` Re: random() (was Re: New GUC to sample log queries) Tom Lane <tgl@sss.pgh.pa.us>
0 siblings, 1 reply; 33+ messages in thread
From: Tom Lane @ 2018-12-27 19:36 UTC (permalink / raw)
To: Thomas Munro <thomas.munro@enterprisedb.com>; +Cc: Peter Geoghegan <pg@bowt.ie>; Michael Paquier <michael@paquier.xyz>; Alvaro Herrera <alvherre@2ndquadrant.com>; Adrien Nayrat <adrien.nayrat@anayrat.info>; Dmitry Dolgov <9erthalion6@gmail.com>; Tomas Vondra <tomas.vondra@2ndquadrant.com>; Vik Fearing <vik.fearing@2ndquadrant.com>; Robert Haas <robertmhaas@gmail.com>; David Rowley <david.rowley@2ndquadrant.com>; pgsql-hackers
Thomas Munro <thomas.munro@enterprisedb.com> writes:
> On Thu, Dec 27, 2018 at 3:55 PM Peter Geoghegan <pg@bowt.ie> wrote:
>> On Wed, Dec 26, 2018 at 6:39 PM Tom Lane <tgl@sss.pgh.pa.us> wrote:
>>> The point here is not to be cryptographically strong at every single
>>> place where the backend might want a random number; I think we're
>>> all agreed that we don't need that. To me, the point is to ensure that
>>> the user-accessible random sequence is kept separate from internal uses,
>>> and the potential security exposure in the new random-logging patch is
>>> what justifies getting more worried about this than we were before.
> +1, but I wonder if just separating them is enough. Is our seeding
> algorithm good enough for this new purpose? The initial seed is 100%
> predictable to a logged in user (it's made from the backend PID and
> backend start time, which we tell you), and not even that hard to
> guess from the outside, so I think Coverity's warning is an
> understatement in this case. Even if we separate the PRNG state used
> for internal stuff so that users can't clobber its seed from SQL,
> wouldn't it be possible to predict which statements will survive the
> log sampling filter given easily available information and a good
> guess at how many times random() (or whatever similar thing) has been
> called so far?
Yeah, that's a good point. Maybe we should upgrade the per-process
seed initialization to make it less predictable. I could see expending
a call of the strong RNG to contribute some more noise to the seeds
selected in InitProcessGlobals().
regards, tom lane
^ permalink raw reply [nested|flat] 33+ messages in thread
* Re: random() (was Re: New GUC to sample log queries)
2018-12-26 18:45 random() (was Re: New GUC to sample log queries) Tom Lane <tgl@sss.pgh.pa.us>
2018-12-27 01:34 ` Re: random() (was Re: New GUC to sample log queries) Michael Paquier <michael@paquier.xyz>
2018-12-27 01:46 ` Re: random() (was Re: New GUC to sample log queries) Tom Lane <tgl@sss.pgh.pa.us>
2018-12-27 02:20 ` Re: random() (was Re: New GUC to sample log queries) Peter Geoghegan <pg@bowt.ie>
2018-12-27 02:39 ` Re: random() (was Re: New GUC to sample log queries) Tom Lane <tgl@sss.pgh.pa.us>
2018-12-27 02:55 ` Re: random() (was Re: New GUC to sample log queries) Peter Geoghegan <pg@bowt.ie>
2018-12-27 04:55 ` Re: random() (was Re: New GUC to sample log queries) Thomas Munro <thomas.munro@enterprisedb.com>
2018-12-27 19:36 ` Re: random() (was Re: New GUC to sample log queries) Tom Lane <tgl@sss.pgh.pa.us>
@ 2018-12-28 23:15 ` Tom Lane <tgl@sss.pgh.pa.us>
2018-12-29 00:36 ` Re: random() (was Re: New GUC to sample log queries) Tom Lane <tgl@sss.pgh.pa.us>
0 siblings, 1 reply; 33+ messages in thread
From: Tom Lane @ 2018-12-28 23:15 UTC (permalink / raw)
To: Thomas Munro <thomas.munro@enterprisedb.com>; +Cc: Heikki Linnakangas <hlinnaka@iki.fi>; Peter Geoghegan <pg@bowt.ie>; Michael Paquier <michael@paquier.xyz>; Alvaro Herrera <alvherre@2ndquadrant.com>; Adrien Nayrat <adrien.nayrat@anayrat.info>; Dmitry Dolgov <9erthalion6@gmail.com>; Tomas Vondra <tomas.vondra@2ndquadrant.com>; Vik Fearing <vik.fearing@2ndquadrant.com>; Robert Haas <robertmhaas@gmail.com>; David Rowley <david.rowley@2ndquadrant.com>; pgsql-hackers
I wrote:
> Thomas Munro <thomas.munro@enterprisedb.com> writes:
>> +1, but I wonder if just separating them is enough. Is our seeding
>> algorithm good enough for this new purpose? The initial seed is 100%
>> predictable to a logged in user (it's made from the backend PID and
>> backend start time, which we tell you), and not even that hard to
>> guess from the outside, so I think Coverity's warning is an
>> understatement in this case. Even if we separate the PRNG state used
>> for internal stuff so that users can't clobber its seed from SQL,
>> wouldn't it be possible to predict which statements will survive the
>> log sampling filter given easily available information and a good
>> guess at how many times random() (or whatever similar thing) has been
>> called so far?
> Yeah, that's a good point. Maybe we should upgrade the per-process
> seed initialization to make it less predictable. I could see expending
> a call of the strong RNG to contribute some more noise to the seeds
> selected in InitProcessGlobals().
Here's a simple patch to do so.
Looking at this, I seem to remember that we considered doing exactly this
awhile ago, but refrained because there was concern about depleting the
system's reserve of entropy if we have a high backend spawn rate, and it
didn't seem like there was a security reason to insist on unpredictable
random() results. However, the log-sampling patch destroys the latter
argument. As for the former argument, I'm not sure how big a deal that
really is. Presumably, the act of spawning a backend would itself
contribute some more entropy to the pool (particularly if a network
connection is involved), so the depletion problem might be fictitious
in the first place. Also, a few references I consulted, such as the
Linux urandom(4) man page, suggest that even in a depleted-entropy
state the results of reading /dev/urandom should be random enough
for all but the very strictest security requirements.
Thoughts?
regards, tom lane
Attachments:
[text/x-diff] make-random-seed-more-random-1.patch (2.5K, ../../10913.1546038905@sss.pgh.pa.us/2-make-random-seed-more-random-1.patch)
download | inline diff:
diff --git a/src/backend/postmaster/postmaster.c b/src/backend/postmaster/postmaster.c
index eedc617..2d5a0ac 100644
*** a/src/backend/postmaster/postmaster.c
--- b/src/backend/postmaster/postmaster.c
*************** ClosePostmasterPorts(bool am_syslogger)
*** 2520,2530 ****
/*
* InitProcessGlobals -- set MyProcPid, MyStartTime[stamp], random seeds
*
! * Called early in every backend.
*/
void
InitProcessGlobals(void)
{
MyProcPid = getpid();
MyStartTimestamp = GetCurrentTimestamp();
MyStartTime = timestamptz_to_time_t(MyStartTimestamp);
--- 2520,2532 ----
/*
* InitProcessGlobals -- set MyProcPid, MyStartTime[stamp], random seeds
*
! * Called early in the postmaster and every backend.
*/
void
InitProcessGlobals(void)
{
+ unsigned int rseed;
+
MyProcPid = getpid();
MyStartTimestamp = GetCurrentTimestamp();
MyStartTime = timestamptz_to_time_t(MyStartTimestamp);
*************** InitProcessGlobals(void)
*** 2539,2553 ****
#endif
/*
! * Set a different seed for random() in every backend. Since PIDs and
! * timestamps tend to change more frequently in their least significant
! * bits, shift the timestamp left to allow a larger total number of seeds
! * in a given time period. Since that would leave only 20 bits of the
! * timestamp that cycle every ~1 second, also mix in some higher bits.
*/
! srandom(((uint64) MyProcPid) ^
((uint64) MyStartTimestamp << 12) ^
! ((uint64) MyStartTimestamp >> 20));
}
--- 2541,2570 ----
#endif
/*
! * Set a different seed for random() 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.
! *
! * Note we can't use pg_backend_random here, since this is used in the
! * postmaster, and even in a backend we might not be attached to shared
! * memory yet.
*/
! #ifdef HAVE_STRONG_RANDOM
! if (!pg_strong_random(&rseed, sizeof(rseed)))
! #endif
! {
! /*
! * Since PIDs and timestamps tend to change more frequently in their
! * least significant bits, shift the timestamp left to allow a larger
! * total number of seeds in a given time period. Since that would
! * leave only 20 bits of the timestamp that cycle every ~1 second,
! * also mix in some higher bits.
! */
! rseed = ((uint64) MyProcPid) ^
((uint64) MyStartTimestamp << 12) ^
! ((uint64) MyStartTimestamp >> 20);
! }
! srandom(rseed);
}
=
^ permalink raw reply [nested|flat] 33+ messages in thread
* Re: random() (was Re: New GUC to sample log queries)
2018-12-26 18:45 random() (was Re: New GUC to sample log queries) Tom Lane <tgl@sss.pgh.pa.us>
2018-12-27 01:34 ` Re: random() (was Re: New GUC to sample log queries) Michael Paquier <michael@paquier.xyz>
2018-12-27 01:46 ` Re: random() (was Re: New GUC to sample log queries) Tom Lane <tgl@sss.pgh.pa.us>
2018-12-27 02:20 ` Re: random() (was Re: New GUC to sample log queries) Peter Geoghegan <pg@bowt.ie>
2018-12-27 02:39 ` Re: random() (was Re: New GUC to sample log queries) Tom Lane <tgl@sss.pgh.pa.us>
2018-12-27 02:55 ` Re: random() (was Re: New GUC to sample log queries) Peter Geoghegan <pg@bowt.ie>
2018-12-27 04:55 ` Re: random() (was Re: New GUC to sample log queries) Thomas Munro <thomas.munro@enterprisedb.com>
2018-12-27 19:36 ` Re: random() (was Re: New GUC to sample log queries) Tom Lane <tgl@sss.pgh.pa.us>
2018-12-28 23:15 ` Re: random() (was Re: New GUC to sample log queries) Tom Lane <tgl@sss.pgh.pa.us>
@ 2018-12-29 00:36 ` Tom Lane <tgl@sss.pgh.pa.us>
2018-12-29 00:45 ` Re: random() (was Re: New GUC to sample log queries) Thomas Munro <thomas.munro@enterprisedb.com>
0 siblings, 1 reply; 33+ messages in thread
From: Tom Lane @ 2018-12-29 00:36 UTC (permalink / raw)
To: Thomas Munro <thomas.munro@enterprisedb.com>; +Cc: Heikki Linnakangas <hlinnaka@iki.fi>; Peter Geoghegan <pg@bowt.ie>; Michael Paquier <michael@paquier.xyz>; Alvaro Herrera <alvherre@2ndquadrant.com>; Adrien Nayrat <adrien.nayrat@anayrat.info>; Dmitry Dolgov <9erthalion6@gmail.com>; Tomas Vondra <tomas.vondra@2ndquadrant.com>; Vik Fearing <vik.fearing@2ndquadrant.com>; Robert Haas <robertmhaas@gmail.com>; David Rowley <david.rowley@2ndquadrant.com>; pgsql-hackers
I wrote:
> Looking at this, I seem to remember that we considered doing exactly this
> awhile ago, but refrained because there was concern about depleting the
> system's reserve of entropy if we have a high backend spawn rate, and it
> didn't seem like there was a security reason to insist on unpredictable
> random() results. However, the log-sampling patch destroys the latter
> argument. As for the former argument, I'm not sure how big a deal that
> really is. Presumably, the act of spawning a backend would itself
> contribute some more entropy to the pool (particularly if a network
> connection is involved), so the depletion problem might be fictitious
> in the first place. Also, a few references I consulted, such as the
> Linux urandom(4) man page, suggest that even in a depleted-entropy
> state the results of reading /dev/urandom should be random enough
> for all but the very strictest security requirements.
I did some experimentation, watching /proc/sys/kernel/random/entropy_avail
while continuously spawning backends, and I can't see any difference in
behavior with or without this patch. If there is any effect at all, it's
completely swamped by other noise (and there's a lot of noise, even on a
machine that's idle).
Also, further googling says there's a pretty sizable body of opinion that
Linux's available-entropy calculation is bogus anyway: once the system's
acquired a reasonable amount of entropy, no amount of reading from
/dev/urandom will cause the randomness of the results to decrease.
So there's no reason to be concerned about whether we're reading it
"too much".
regards, tom lane
^ permalink raw reply [nested|flat] 33+ messages in thread
* Re: random() (was Re: New GUC to sample log queries)
2018-12-26 18:45 random() (was Re: New GUC to sample log queries) Tom Lane <tgl@sss.pgh.pa.us>
2018-12-27 01:34 ` Re: random() (was Re: New GUC to sample log queries) Michael Paquier <michael@paquier.xyz>
2018-12-27 01:46 ` Re: random() (was Re: New GUC to sample log queries) Tom Lane <tgl@sss.pgh.pa.us>
2018-12-27 02:20 ` Re: random() (was Re: New GUC to sample log queries) Peter Geoghegan <pg@bowt.ie>
2018-12-27 02:39 ` Re: random() (was Re: New GUC to sample log queries) Tom Lane <tgl@sss.pgh.pa.us>
2018-12-27 02:55 ` Re: random() (was Re: New GUC to sample log queries) Peter Geoghegan <pg@bowt.ie>
2018-12-27 04:55 ` Re: random() (was Re: New GUC to sample log queries) Thomas Munro <thomas.munro@enterprisedb.com>
2018-12-27 19:36 ` Re: random() (was Re: New GUC to sample log queries) Tom Lane <tgl@sss.pgh.pa.us>
2018-12-28 23:15 ` Re: random() (was Re: New GUC to sample log queries) Tom Lane <tgl@sss.pgh.pa.us>
2018-12-29 00:36 ` Re: random() (was Re: New GUC to sample log queries) Tom Lane <tgl@sss.pgh.pa.us>
@ 2018-12-29 00:45 ` Thomas Munro <thomas.munro@enterprisedb.com>
2018-12-29 00:57 ` Re: random() (was Re: New GUC to sample log queries) Tom Lane <tgl@sss.pgh.pa.us>
0 siblings, 1 reply; 33+ messages in thread
From: Thomas Munro @ 2018-12-29 00:45 UTC (permalink / raw)
To: Tom Lane <tgl@sss.pgh.pa.us>; +Cc: Heikki Linnakangas <hlinnaka@iki.fi>; Peter Geoghegan <pg@bowt.ie>; Michael Paquier <michael@paquier.xyz>; Alvaro Herrera <alvherre@2ndquadrant.com>; Adrien Nayrat <adrien.nayrat@anayrat.info>; Dmitry Dolgov <9erthalion6@gmail.com>; Tomas Vondra <tomas.vondra@2ndquadrant.com>; Vik Fearing <vik.fearing@2ndquadrant.com>; Robert Haas <robertmhaas@gmail.com>; David Rowley <david.rowley@2ndquadrant.com>; pgsql-hackers
On Sat, Dec 29, 2018 at 1:37 PM Tom Lane <tgl@sss.pgh.pa.us> wrote:
> I wrote:
> > Looking at this, I seem to remember that we considered doing exactly this
> > awhile ago, but refrained because there was concern about depleting the
> > system's reserve of entropy if we have a high backend spawn rate, and it
> > didn't seem like there was a security reason to insist on unpredictable
> > random() results. However, the log-sampling patch destroys the latter
> > argument. As for the former argument, I'm not sure how big a deal that
> > really is. Presumably, the act of spawning a backend would itself
> > contribute some more entropy to the pool (particularly if a network
> > connection is involved), so the depletion problem might be fictitious
> > in the first place. Also, a few references I consulted, such as the
> > Linux urandom(4) man page, suggest that even in a depleted-entropy
> > state the results of reading /dev/urandom should be random enough
> > for all but the very strictest security requirements.
>
> I did some experimentation, watching /proc/sys/kernel/random/entropy_avail
> while continuously spawning backends, and I can't see any difference in
> behavior with or without this patch. If there is any effect at all, it's
> completely swamped by other noise (and there's a lot of noise, even on a
> machine that's idle).
>
> Also, further googling says there's a pretty sizable body of opinion that
> Linux's available-entropy calculation is bogus anyway: once the system's
> acquired a reasonable amount of entropy, no amount of reading from
> /dev/urandom will cause the randomness of the results to decrease.
> So there's no reason to be concerned about whether we're reading it
> "too much".
I was going to suggest that we might be able to use a single
not-visible-to-users number that is mixed into the existing recipe, so
that we only ever read urandom once for the cluster. But it sounds
like it's not a problem, and it's probably better to just pass the
whole problem over to the OS.
--
Thomas Munro
http://www.enterprisedb.com
^ permalink raw reply [nested|flat] 33+ messages in thread
* Re: random() (was Re: New GUC to sample log queries)
2018-12-26 18:45 random() (was Re: New GUC to sample log queries) Tom Lane <tgl@sss.pgh.pa.us>
2018-12-27 01:34 ` Re: random() (was Re: New GUC to sample log queries) Michael Paquier <michael@paquier.xyz>
2018-12-27 01:46 ` Re: random() (was Re: New GUC to sample log queries) Tom Lane <tgl@sss.pgh.pa.us>
2018-12-27 02:20 ` Re: random() (was Re: New GUC to sample log queries) Peter Geoghegan <pg@bowt.ie>
2018-12-27 02:39 ` Re: random() (was Re: New GUC to sample log queries) Tom Lane <tgl@sss.pgh.pa.us>
2018-12-27 02:55 ` Re: random() (was Re: New GUC to sample log queries) Peter Geoghegan <pg@bowt.ie>
2018-12-27 04:55 ` Re: random() (was Re: New GUC to sample log queries) Thomas Munro <thomas.munro@enterprisedb.com>
2018-12-27 19:36 ` Re: random() (was Re: New GUC to sample log queries) Tom Lane <tgl@sss.pgh.pa.us>
2018-12-28 23:15 ` Re: random() (was Re: New GUC to sample log queries) Tom Lane <tgl@sss.pgh.pa.us>
2018-12-29 00:36 ` Re: random() (was Re: New GUC to sample log queries) Tom Lane <tgl@sss.pgh.pa.us>
2018-12-29 00:45 ` Re: random() (was Re: New GUC to sample log queries) Thomas Munro <thomas.munro@enterprisedb.com>
@ 2018-12-29 00:57 ` Tom Lane <tgl@sss.pgh.pa.us>
2018-12-29 21:07 ` Re: random() (was Re: New GUC to sample log queries) Tom Lane <tgl@sss.pgh.pa.us>
0 siblings, 1 reply; 33+ messages in thread
From: Tom Lane @ 2018-12-29 00:57 UTC (permalink / raw)
To: Thomas Munro <thomas.munro@enterprisedb.com>; +Cc: Heikki Linnakangas <hlinnaka@iki.fi>; Peter Geoghegan <pg@bowt.ie>; Michael Paquier <michael@paquier.xyz>; Alvaro Herrera <alvherre@2ndquadrant.com>; Adrien Nayrat <adrien.nayrat@anayrat.info>; Dmitry Dolgov <9erthalion6@gmail.com>; Tomas Vondra <tomas.vondra@2ndquadrant.com>; Vik Fearing <vik.fearing@2ndquadrant.com>; Robert Haas <robertmhaas@gmail.com>; David Rowley <david.rowley@2ndquadrant.com>; pgsql-hackers
Thomas Munro <thomas.munro@enterprisedb.com> writes:
> I was going to suggest that we might be able to use a single
> not-visible-to-users number that is mixed into the existing recipe, so
> that we only ever read urandom once for the cluster.
Yeah, I was thinking along similar lines, but there's a problem:
InitProcessGlobals runs before an EXEC_BACKEND child has reconnected
to shared memory, so there's no cheap way to pass state to it.
No doubt there are ways around that, but I'd just as soon avoid
adding complexity here. If we broke it somehow, the likely results
would be silent failure of the per-process seed to be random, which
might escape detection for a long time.
> But it sounds
> like it's not a problem, and it's probably better to just pass the
> whole problem over to the OS.
Yeah, that's what I'm thinking.
regards, tom lane
^ permalink raw reply [nested|flat] 33+ messages in thread
* Re: random() (was Re: New GUC to sample log queries)
2018-12-26 18:45 random() (was Re: New GUC to sample log queries) Tom Lane <tgl@sss.pgh.pa.us>
2018-12-27 01:34 ` Re: random() (was Re: New GUC to sample log queries) Michael Paquier <michael@paquier.xyz>
2018-12-27 01:46 ` Re: random() (was Re: New GUC to sample log queries) Tom Lane <tgl@sss.pgh.pa.us>
2018-12-27 02:20 ` Re: random() (was Re: New GUC to sample log queries) Peter Geoghegan <pg@bowt.ie>
2018-12-27 02:39 ` Re: random() (was Re: New GUC to sample log queries) Tom Lane <tgl@sss.pgh.pa.us>
2018-12-27 02:55 ` Re: random() (was Re: New GUC to sample log queries) Peter Geoghegan <pg@bowt.ie>
2018-12-27 04:55 ` Re: random() (was Re: New GUC to sample log queries) Thomas Munro <thomas.munro@enterprisedb.com>
2018-12-27 19:36 ` Re: random() (was Re: New GUC to sample log queries) Tom Lane <tgl@sss.pgh.pa.us>
2018-12-28 23:15 ` Re: random() (was Re: New GUC to sample log queries) Tom Lane <tgl@sss.pgh.pa.us>
2018-12-29 00:36 ` Re: random() (was Re: New GUC to sample log queries) Tom Lane <tgl@sss.pgh.pa.us>
2018-12-29 00:45 ` Re: random() (was Re: New GUC to sample log queries) Thomas Munro <thomas.munro@enterprisedb.com>
2018-12-29 00:57 ` Re: random() (was Re: New GUC to sample log queries) Tom Lane <tgl@sss.pgh.pa.us>
@ 2018-12-29 21:07 ` Tom Lane <tgl@sss.pgh.pa.us>
0 siblings, 0 replies; 33+ messages in thread
From: Tom Lane @ 2018-12-29 21:07 UTC (permalink / raw)
To: Thomas Munro <thomas.munro@enterprisedb.com>; +Cc: Heikki Linnakangas <hlinnaka@iki.fi>; Peter Geoghegan <pg@bowt.ie>; Michael Paquier <michael@paquier.xyz>; Alvaro Herrera <alvherre@2ndquadrant.com>; Adrien Nayrat <adrien.nayrat@anayrat.info>; Dmitry Dolgov <9erthalion6@gmail.com>; Tomas Vondra <tomas.vondra@2ndquadrant.com>; Vik Fearing <vik.fearing@2ndquadrant.com>; Robert Haas <robertmhaas@gmail.com>; David Rowley <david.rowley@2ndquadrant.com>; pgsql-hackers
I wrote:
> Thomas Munro <thomas.munro@enterprisedb.com> writes:
>> I was going to suggest that we might be able to use a single
>> not-visible-to-users number that is mixed into the existing recipe, so
>> that we only ever read urandom once for the cluster.
> Yeah, I was thinking along similar lines, but there's a problem:
> InitProcessGlobals runs before an EXEC_BACKEND child has reconnected
> to shared memory, so there's no cheap way to pass state to it.
> No doubt there are ways around that, but I'd just as soon avoid
> adding complexity here. If we broke it somehow, the likely results
> would be silent failure of the per-process seed to be random, which
> might escape detection for a long time.
>> But it sounds
>> like it's not a problem, and it's probably better to just pass the
>> whole problem over to the OS.
> Yeah, that's what I'm thinking.
One final point on this --- I wondered whether initializing the
seed with pg_strong_random would be too costly time-wise.
It doesn't seem so; I measure the time to do it as ~25us with
/dev/urandom or ~80us with OpenSSL on my main development
workstation. The total time to start a backend on that machine
is a few milliseconds depending on what you want to count.
I got numbers broadly in line with those results on half a dozen
other platforms (recent Fedora, Mac, various BSD on x86_64, ARM,
and PPC).
So I'd judge that the time cost is not a reason not to apply this
patch, but we might want to reconsider why we're preferring
OpenSSL over direct use of /dev/urandom.
I also wondered whether we might do something like Thomas' suggestion
to try to cut the startup time. In a fork() environment it'd be
pretty cheap to pass down a master seed value from the postmaster,
but with EXEC_BACKEND I think the only reliable way would be to
put the seed value in a file and have backends read it from there.
That's none too cheap either --- for grins, I hacked pg_strong_random.c
to read an ordinary file instead of /dev/urandom, and got runtimes
around 15us, so reading /dev/urandom is really not that much slower than
a plain file. On the whole I don't find this line of thought attractive,
especially since it's not real clear to me how safe it would be to work
like this rather than have a fully independent seed for each process.
Anyway, I've run out of reasons why we might not want to do this,
so I'm going to go ahead and commit it.
regards, tom lane
^ permalink raw reply [nested|flat] 33+ messages in thread
* Re: random() (was Re: New GUC to sample log queries)
2018-12-26 18:45 random() (was Re: New GUC to sample log queries) Tom Lane <tgl@sss.pgh.pa.us>
2018-12-27 01:34 ` Re: random() (was Re: New GUC to sample log queries) Michael Paquier <michael@paquier.xyz>
2018-12-27 01:46 ` Re: random() (was Re: New GUC to sample log queries) Tom Lane <tgl@sss.pgh.pa.us>
2018-12-27 02:20 ` Re: random() (was Re: New GUC to sample log queries) Peter Geoghegan <pg@bowt.ie>
2018-12-27 02:39 ` Re: random() (was Re: New GUC to sample log queries) Tom Lane <tgl@sss.pgh.pa.us>
2018-12-27 02:55 ` Re: random() (was Re: New GUC to sample log queries) Peter Geoghegan <pg@bowt.ie>
@ 2018-12-27 19:33 ` Tom Lane <tgl@sss.pgh.pa.us>
2018-12-27 20:00 ` Re: random() (was Re: New GUC to sample log queries) Tom Lane <tgl@sss.pgh.pa.us>
1 sibling, 1 reply; 33+ messages in thread
From: Tom Lane @ 2018-12-27 19:33 UTC (permalink / raw)
To: Peter Geoghegan <pg@bowt.ie>; +Cc: Michael Paquier <michael@paquier.xyz>; Alvaro Herrera <alvherre@2ndquadrant.com>; Adrien Nayrat <adrien.nayrat@anayrat.info>; Thomas Munro <thomas.munro@enterprisedb.com>; Dmitry Dolgov <9erthalion6@gmail.com>; Tomas Vondra <tomas.vondra@2ndquadrant.com>; Vik Fearing <vik.fearing@2ndquadrant.com>; Robert Haas <robertmhaas@gmail.com>; David Rowley <david.rowley@2ndquadrant.com>; pgsql-hackers
Peter Geoghegan <pg@bowt.ie> writes:
> On Wed, Dec 26, 2018 at 6:39 PM Tom Lane <tgl@sss.pgh.pa.us> wrote:
>> Now, we could probably fix that with some less intrusive patch than
>> #define'ing random() --- in particular, if we give drandom and setseed
>> their own private PRNG state, we've really fixed the security exposure
>> without need to change anything else anywhere. So maybe we should
>> just do that and be happy.
> +1. I don't like the idea of #define'ing random() myself.
> We're already making fairly broad assumptions about our having control
> of the backend's PRNG state within InitProcessGlobals(). How should
> this affect the new drandom()/setseed() private state, if at all?
I would think that InitProcessGlobals would initialize drandom's
seed alongside random()'s seed. Hopefully to values not easily
predictable from each other -- see also Munro's comment, which
I'll respond to in a moment.
regards, tom lane
^ permalink raw reply [nested|flat] 33+ messages in thread
* Re: random() (was Re: New GUC to sample log queries)
2018-12-26 18:45 random() (was Re: New GUC to sample log queries) Tom Lane <tgl@sss.pgh.pa.us>
2018-12-27 01:34 ` Re: random() (was Re: New GUC to sample log queries) Michael Paquier <michael@paquier.xyz>
2018-12-27 01:46 ` Re: random() (was Re: New GUC to sample log queries) Tom Lane <tgl@sss.pgh.pa.us>
2018-12-27 02:20 ` Re: random() (was Re: New GUC to sample log queries) Peter Geoghegan <pg@bowt.ie>
2018-12-27 02:39 ` Re: random() (was Re: New GUC to sample log queries) Tom Lane <tgl@sss.pgh.pa.us>
2018-12-27 02:55 ` Re: random() (was Re: New GUC to sample log queries) Peter Geoghegan <pg@bowt.ie>
2018-12-27 19:33 ` Re: random() (was Re: New GUC to sample log queries) Tom Lane <tgl@sss.pgh.pa.us>
@ 2018-12-27 20:00 ` Tom Lane <tgl@sss.pgh.pa.us>
2018-12-28 21:42 ` Re: random() (was Re: New GUC to sample log queries) Tom Lane <tgl@sss.pgh.pa.us>
0 siblings, 1 reply; 33+ messages in thread
From: Tom Lane @ 2018-12-27 20:00 UTC (permalink / raw)
To: Peter Geoghegan <pg@bowt.ie>; +Cc: Michael Paquier <michael@paquier.xyz>; Alvaro Herrera <alvherre@2ndquadrant.com>; Adrien Nayrat <adrien.nayrat@anayrat.info>; Thomas Munro <thomas.munro@enterprisedb.com>; Dmitry Dolgov <9erthalion6@gmail.com>; Tomas Vondra <tomas.vondra@2ndquadrant.com>; Vik Fearing <vik.fearing@2ndquadrant.com>; Robert Haas <robertmhaas@gmail.com>; David Rowley <david.rowley@2ndquadrant.com>; pgsql-hackers
I wrote:
> Peter Geoghegan <pg@bowt.ie> writes:
>> We're already making fairly broad assumptions about our having control
>> of the backend's PRNG state within InitProcessGlobals(). How should
>> this affect the new drandom()/setseed() private state, if at all?
> I would think that InitProcessGlobals would initialize drandom's
> seed alongside random()'s seed. Hopefully to values not easily
> predictable from each other -- see also Munro's comment, which
> I'll respond to in a moment.
On further reflection, it seems likely that in most installations a lot
of processes never invoke drandom()/setseed() at all, making such work
in InitProcessGlobals a waste of cycles. Probably a better idea is to
have drandom() initialize the seed on first use, if it wasn't already
set by setseed(). This might also make it easier to decouple that
seed value from the random() sequence --- we could use a fresh
timestamp value, and perhaps another strong-RNG call, though I'm not
sure if the latter is worthwhile.
regards, tom lane
^ permalink raw reply [nested|flat] 33+ messages in thread
* Re: random() (was Re: New GUC to sample log queries)
2018-12-26 18:45 random() (was Re: New GUC to sample log queries) Tom Lane <tgl@sss.pgh.pa.us>
2018-12-27 01:34 ` Re: random() (was Re: New GUC to sample log queries) Michael Paquier <michael@paquier.xyz>
2018-12-27 01:46 ` Re: random() (was Re: New GUC to sample log queries) Tom Lane <tgl@sss.pgh.pa.us>
2018-12-27 02:20 ` Re: random() (was Re: New GUC to sample log queries) Peter Geoghegan <pg@bowt.ie>
2018-12-27 02:39 ` Re: random() (was Re: New GUC to sample log queries) Tom Lane <tgl@sss.pgh.pa.us>
2018-12-27 02:55 ` Re: random() (was Re: New GUC to sample log queries) Peter Geoghegan <pg@bowt.ie>
2018-12-27 19:33 ` Re: random() (was Re: New GUC to sample log queries) Tom Lane <tgl@sss.pgh.pa.us>
2018-12-27 20:00 ` Re: random() (was Re: New GUC to sample log queries) Tom Lane <tgl@sss.pgh.pa.us>
@ 2018-12-28 21:42 ` Tom Lane <tgl@sss.pgh.pa.us>
0 siblings, 0 replies; 33+ messages in thread
From: Tom Lane @ 2018-12-28 21:42 UTC (permalink / raw)
To: Peter Geoghegan <pg@bowt.ie>; +Cc: Michael Paquier <michael@paquier.xyz>; Alvaro Herrera <alvherre@2ndquadrant.com>; Adrien Nayrat <adrien.nayrat@anayrat.info>; Thomas Munro <thomas.munro@enterprisedb.com>; Dmitry Dolgov <9erthalion6@gmail.com>; Tomas Vondra <tomas.vondra@2ndquadrant.com>; Vik Fearing <vik.fearing@2ndquadrant.com>; Robert Haas <robertmhaas@gmail.com>; David Rowley <david.rowley@2ndquadrant.com>; pgsql-hackers
I wrote:
> On further reflection, it seems likely that in most installations a lot
> of processes never invoke drandom()/setseed() at all, making such work
> in InitProcessGlobals a waste of cycles. Probably a better idea is to
> have drandom() initialize the seed on first use, if it wasn't already
> set by setseed().
Here's a proposed patch for that.
It occurs to me that there's still another good reason to decouple
drandom from everything else: the point of setseed(), if it has any
at all, is to allow a repeatable sequence of drandom values to be
generated. Without this patch, no such guarantee exists because of
the possibility of the backend making additional internal calls of
libc random().
regards, tom lane
Attachments:
[text/x-diff] decouple-drandom-from-other-random-calls-1.patch (4.2K, ../../22401.1546033340@sss.pgh.pa.us/2-decouple-drandom-from-other-random-calls-1.patch)
download | inline diff:
diff --git a/doc/src/sgml/func.sgml b/doc/src/sgml/func.sgml
index 3786099..1df4356 100644
*** a/doc/src/sgml/func.sgml
--- b/doc/src/sgml/func.sgml
***************
*** 1136,1146 ****
</table>
<para>
! The characteristics of the values returned by
! <literal><function>random()</function></literal> depend
! on the system implementation. It is not suitable for cryptographic
! applications; see <xref linkend="pgcrypto"/> module for an alternative.
! </para>
<para>
Finally, <xref linkend="functions-math-trig-table"/> shows the
--- 1136,1150 ----
</table>
<para>
! The <function>random()</function> function uses a simple linear
! congruential algorithm. It is fast but not suitable for cryptographic
! applications; see the <xref linkend="pgcrypto"/> module for an
! alternative.
! If <function>setseed()</function> is called, the results of
! subsequent <function>random()</function> calls in the current session are
! repeatable by re-issuing <function>setseed()</function> with the same
! argument.
! </para>
<para>
Finally, <xref linkend="functions-math-trig-table"/> shows the
diff --git a/src/backend/utils/adt/float.c b/src/backend/utils/adt/float.c
index cf9327f..add099e 100644
*** a/src/backend/utils/adt/float.c
--- b/src/backend/utils/adt/float.c
***************
*** 22,31 ****
--- 22,34 ----
#include "catalog/pg_type.h"
#include "common/int.h"
#include "libpq/pqformat.h"
+ #include "miscadmin.h"
#include "utils/array.h"
+ #include "utils/backend_random.h"
#include "utils/float.h"
#include "utils/fmgrprotos.h"
#include "utils/sortsupport.h"
+ #include "utils/timestamp.h"
/* Configurable GUC parameter */
*************** float8 degree_c_sixty = 60.0;
*** 53,58 ****
--- 56,65 ----
float8 degree_c_one_half = 0.5;
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};
+
/* Local function prototypes */
static double sind_q1(double x);
static double cosd_q1(double x);
*************** drandom(PG_FUNCTION_ARGS)
*** 2378,2385 ****
{
float8 result;
! /* result [0.0 - 1.0) */
! result = (double) random() / ((double) MAX_RANDOM_VALUE + 1);
PG_RETURN_FLOAT8(result);
}
--- 2385,2414 ----
{
float8 result;
! /* Initialize random seed, if not done yet in this process */
! if (unlikely(!drandom_seed_set))
! {
! /*
! * If possible, initialize the seed using high-quality random bits.
! * Should that fail for some reason, we fall back on a lower-quality
! * seed based on current time and PID.
! */
! if (!pg_backend_random((char *) drandom_seed, sizeof(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);
! }
! drandom_seed_set = true;
! }
!
! /* pg_erand48 produces desired result range [0.0 - 1.0) */
! result = pg_erand48(drandom_seed);
PG_RETURN_FLOAT8(result);
}
*************** Datum
*** 2392,2404 ****
setseed(PG_FUNCTION_ARGS)
{
float8 seed = PG_GETARG_FLOAT8(0);
! int iseed;
! if (seed < -1 || seed > 1)
! elog(ERROR, "setseed parameter %f out of range [-1,1]", seed);
! iseed = (int) (seed * MAX_RANDOM_VALUE);
! srandom((unsigned int) iseed);
PG_RETURN_VOID();
}
--- 2421,2440 ----
setseed(PG_FUNCTION_ARGS)
{
float8 seed = PG_GETARG_FLOAT8(0);
! uint64 iseed;
! if (seed < -1 || seed > 1 || isnan(seed))
! ereport(ERROR,
! (errcode(ERRCODE_INVALID_PARAMETER_VALUE),
! 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);
! drandom_seed_set = true;
PG_RETURN_VOID();
}
^ permalink raw reply [nested|flat] 33+ messages in thread
* Re: random() (was Re: New GUC to sample log queries)
2018-12-26 18:45 random() (was Re: New GUC to sample log queries) Tom Lane <tgl@sss.pgh.pa.us>
@ 2018-12-27 08:36 ` Fabien COELHO <coelho@cri.ensmp.fr>
2018-12-27 23:00 ` Re: random() (was Re: New GUC to sample log queries) Tom Lane <tgl@sss.pgh.pa.us>
3 siblings, 1 reply; 33+ messages in thread
From: Fabien COELHO @ 2018-12-27 08:36 UTC (permalink / raw)
To: Tom Lane <tgl@sss.pgh.pa.us>; +Cc: Alvaro Herrera <alvherre@2ndquadrant.com>; Adrien Nayrat <adrien.nayrat@anayrat.info>; Thomas Munro <thomas.munro@enterprisedb.com>; Dmitry Dolgov <9erthalion6@gmail.com>; Tomas Vondra <tomas.vondra@2ndquadrant.com>; vik.fearing@2ndquadrant.com, Robert Haas <robertmhaas@gmail.com>; Michael Paquier <michael@paquier.xyz>; David Rowley <david.rowley@2ndquadrant.com>; pgsql-hackers
Hello all,
> I am not sure I buy the argument that this is a security hazard, but
> there are other reasons to question the use of random() here, some of
> which you stated yourself above. Another one is that using random()
> for internal purposes interferes with applications' possible use of
> drandom() and setseed(), ie an application depending on getting a
> particular random series would see different behavior depending on
> whether this GUC is active or not.
>
> Another idea, which would be a lot less prone to breakage by
> add-on code, is to change drandom() and setseed() to themselves
> use pg_erand48() with a private seed.
My random thoughts about random, erand48, etc. which may be slightly out
of topic, sorry if this is the case.
The word "random" is a misnommer for these pseudo-random generators, so
that "strong" has to be used for higher quality generators:-(
On Linux, random() is advertised with a period of around 2**36, its
internal state is 8 to 256 bytes (default unclear, probably 8 bytes),
however seeding with srandom() provides only 32 bits, which is a drawback.
The pg_erand48 code looks like crumbs from the 70's optimized for 16 bits
architectures (which it is probably not, but why not going to 64 bits or
128 bits directly looks like a missed opportunity), its internal state is
48 bits as its name implies, and its period probably around 2**48, which
is 2**12 better than the previous case, not an extraordinary achievement.
Initial seeding of any pseudo-random generator should NEVER only use pid &
time, which are too predictable, as already noted on the thread. They
should use a strong random source if available, and maybe some backup, eg
hashing logs. I think that this should be directly implemented, maybe with
some provision to set the seed manually for debugging purposes, although
with time-dependent features that may use random I'm not sure how far this
would go.
Also, I would suggest to centralize and abstract the implementation of a
default pseudo-random generator so that its actual internal size and
quality can be changed. That would mean renaming pg_erand48 and hidding
its state size, maybe along the lines of:
// extractors
void pg_random_bytes(int nbytes, char *where_to_put_them);
uint32 pg_random_32();
uint64 pg_random_48();
uint64 pg_random_64();
...
// dynamic?
int pg_random_state_size(void); // in bytes
// or static?
#define PG_RANDOM_STATE_SIZE 6 // bytes
// get/set state
bool pg_random_get_state(uchar *state(, int size|[PG_RANDOM_STATE_SIZE]));
bool pg_random_set_state(const uchar *state...);
Given the typical hardware a postgres instance runs on, I would shop
around for a pseudo-random generator which takes advantage of 64 bits
operations, and not go below 64 bit seeds, or possibly 128.
If a strong random source is available but considered too costly, so that
a (weak) linear congruencial algorithm must be used, a possible compromise
is to reseed from the strong source every few thousands/millions draws, or
with a time periodicity, eg every few minutes, or maybe some configurable
option.
A not too costly security enhancer is to combine different fast generators
so that if one becomes weak at some point, the combination does not.
--
Fabien.
^ permalink raw reply [nested|flat] 33+ messages in thread
* Re: random() (was Re: New GUC to sample log queries)
2018-12-26 18:45 random() (was Re: New GUC to sample log queries) Tom Lane <tgl@sss.pgh.pa.us>
2018-12-27 08:36 ` Re: random() (was Re: New GUC to sample log queries) Fabien COELHO <coelho@cri.ensmp.fr>
@ 2018-12-27 23:00 ` Tom Lane <tgl@sss.pgh.pa.us>
2018-12-28 08:18 ` Re: random() (was Re: New GUC to sample log queries) Fabien COELHO <coelho@cri.ensmp.fr>
0 siblings, 1 reply; 33+ messages in thread
From: Tom Lane @ 2018-12-27 23:00 UTC (permalink / raw)
To: Fabien COELHO <coelho@cri.ensmp.fr>; +Cc: Alvaro Herrera <alvherre@2ndquadrant.com>; Adrien Nayrat <adrien.nayrat@anayrat.info>; Thomas Munro <thomas.munro@enterprisedb.com>; Dmitry Dolgov <9erthalion6@gmail.com>; Tomas Vondra <tomas.vondra@2ndquadrant.com>; vik.fearing@2ndquadrant.com, Robert Haas <robertmhaas@gmail.com>; Michael Paquier <michael@paquier.xyz>; David Rowley <david.rowley@2ndquadrant.com>; pgsql-hackers
Fabien COELHO <coelho@cri.ensmp.fr> writes:
>> Another idea, which would be a lot less prone to breakage by
>> add-on code, is to change drandom() and setseed() to themselves
>> use pg_erand48() with a private seed.
> The pg_erand48 code looks like crumbs from the 70's optimized for 16 bits
> architectures (which it is probably not, but why not going to 64 bits or
> 128 bits directly looks like a missed opportunity), its internal state is
> 48 bits as its name implies, and its period probably around 2**48, which
> is 2**12 better than the previous case, not an extraordinary achievement.
I can't get terribly excited about rewriting that code. You're arguing
from a "one size should fit all" perspective, which is exactly not the
design approach we're using. We've already converted security-sensitive
PRNG uses to use pg_strong_random (or if we haven't, that's a localized
bug in any such places we missed). What remains are places where we are
not so concerned about cryptographic strength but rather speed. It does
behoove us to ensure that the seed values are unpredictable and that a
user-controllable seed isn't used for internal operations, but I don't
feel a need for replacing the algorithm.
You might argue that the SQL function drandom should be held to a higher
standard, but we document exactly this same tradeoff for it. Users who
want cryptographic strength are directed to pgcrypto, leaving the audience
for drandom being people who want speed.
I do notice a couple of things that could be improved about erand48.c:
1. The _rand48_mult and _rand48_add values are constants, but probably few
compilers would notice that, given that they're assigned to in pg_srand48.
I think we should replace the references to those variables with direct
uses of the macros for their values, to save a few cycles in _dorand48.
2. There seems to be a bug in pg_jrand48 (which is relatively new, added
in fe0a0b599, without bothering to update the header comment).
Per POSIX,
The mrand48() and jrand48() functions return signed long integers
uniformly distributed over the interval [-2^31, 2^31).
However, if "long" is 64 bits what you're actually going to get is
unsigned values ranging up to 2^32-1. This doesn't matter to existing
callers because they coerce the value to int32 or uint32, but it's going
to bite somebody eventually.
regards, tom lane
^ permalink raw reply [nested|flat] 33+ messages in thread
* Re: random() (was Re: New GUC to sample log queries)
2018-12-26 18:45 random() (was Re: New GUC to sample log queries) Tom Lane <tgl@sss.pgh.pa.us>
2018-12-27 08:36 ` Re: random() (was Re: New GUC to sample log queries) Fabien COELHO <coelho@cri.ensmp.fr>
2018-12-27 23:00 ` Re: random() (was Re: New GUC to sample log queries) Tom Lane <tgl@sss.pgh.pa.us>
@ 2018-12-28 08:18 ` Fabien COELHO <coelho@cri.ensmp.fr>
2018-12-28 08:44 ` Re: random() (was Re: New GUC to sample log queries) Fabien COELHO <coelho@cri.ensmp.fr>
2018-12-28 17:29 ` Re: random() (was Re: New GUC to sample log queries) Tom Lane <tgl@sss.pgh.pa.us>
0 siblings, 2 replies; 33+ messages in thread
From: Fabien COELHO @ 2018-12-28 08:18 UTC (permalink / raw)
To: Tom Lane <tgl@sss.pgh.pa.us>; +Cc: Alvaro Herrera <alvherre@2ndquadrant.com>; Adrien Nayrat <adrien.nayrat@anayrat.info>; Thomas Munro <thomas.munro@enterprisedb.com>; Dmitry Dolgov <9erthalion6@gmail.com>; Tomas Vondra <tomas.vondra@2ndquadrant.com>; vik.fearing@2ndquadrant.com, Robert Haas <robertmhaas@gmail.com>; Michael Paquier <michael@paquier.xyz>; David Rowley <david.rowley@2ndquadrant.com>; pgsql-hackers
Hello Tom,
>>> Another idea, which would be a lot less prone to breakage by
>>> add-on code, is to change drandom() and setseed() to themselves
>>> use pg_erand48() with a private seed.
>
>> The pg_erand48 code looks like crumbs from the 70's optimized for 16 bits
>> architectures (which it is probably not, but why not going to 64 bits or
>> 128 bits directly looks like a missed opportunity), its internal state is
>> 48 bits as its name implies, and its period probably around 2**48, which
>> is 2**12 better than the previous case, not an extraordinary achievement.
>
> I can't get terribly excited about rewriting that code. You're arguing
> from a "one size should fit all" perspective,
Not exactly. I'm not claiming that distinguishing parts that require
good random from others is a bad choice. I'm arguing that:
(1) from a software engineering perspective, the PRNG implementation
should hide the underlying generator name and state size.
(2) from a numerical perspective, poor seedings practice should be avoided
when possible.
(3) from a cryptographic perspective, LCG is a poor choice of fast PRNG,
which a quick look at wikipedia (mother of all knowledge) confirms.
(4) the fact that pg historical PRNG choices are well documented is not a
good justification for not improving them.
Better alternatives exist that do not cost much (eg xorshift variants,
WELL...), some of which are optimized for 64 bits architectures.
> which is exactly not the design approach we're using.
> We've already converted security-sensitive PRNG uses to use
> pg_strong_random (or if we haven't, that's a localized bug in any such
> places we missed). What remains are places where we are not so
> concerned about cryptographic strength but rather speed.
I do agree with the speed concern. I'm arguing that better quality at
speed can be achieved with better seeding practices and not using a LCG.
About costs, not counting array accesses:
- lrand48 (48 bits state as 3 uint16) is 29 ops
(10 =, 8 *, 7 +, 4 >>)
- xorshift+ (128 bits state as 2 uint64) is 13 ops
( 5 =, 0 *, 1 +, 3 >>, 4 ^)
- xororshift128+ (idem) is 17 ops
( 6 =, 0 *, 1 +, 5 >>, 3 ^, 2 |, less if rot in hardware)
- WELL512 (512 bits state as 16 uint32) is 38 ops
(11 =, 0 *, 3 +, 7 >>, 10 ^, 4 &)
probably much better, but probably slower than the current version
I'd be of the (debatable) opinion that we could use xororshift128+,
already used by various languages, even if it fails some specialized
tests.
> It does behoove us to ensure that the seed values are unpredictable and
> that a user-controllable seed isn't used for internal operations,
Sure.
> but I don't feel a need for replacing the algorithm.
Hmmm. Does it mean that you would veto any change, even if the speed
concern is addressed (i.e. faster/not slower with better quality)?
> You might argue that the SQL function drandom should be held to a higher
> standard, but we document exactly this same tradeoff for it. Users who
> want cryptographic strength are directed to pgcrypto, leaving the audience
> for drandom being people who want speed.
My point is that speed is not necessary incompatible with better quality.
Better quality should not replace strong random when needed.
--
Fabien.
^ permalink raw reply [nested|flat] 33+ messages in thread
* Re: random() (was Re: New GUC to sample log queries)
2018-12-26 18:45 random() (was Re: New GUC to sample log queries) Tom Lane <tgl@sss.pgh.pa.us>
2018-12-27 08:36 ` Re: random() (was Re: New GUC to sample log queries) Fabien COELHO <coelho@cri.ensmp.fr>
2018-12-27 23:00 ` Re: random() (was Re: New GUC to sample log queries) Tom Lane <tgl@sss.pgh.pa.us>
2018-12-28 08:18 ` Re: random() (was Re: New GUC to sample log queries) Fabien COELHO <coelho@cri.ensmp.fr>
@ 2018-12-28 08:44 ` Fabien COELHO <coelho@cri.ensmp.fr>
2018-12-28 11:07 ` Re: random() (was Re: New GUC to sample log queries) Fabien COELHO <coelho@cri.ensmp.fr>
1 sibling, 1 reply; 33+ messages in thread
From: Fabien COELHO @ 2018-12-28 08:44 UTC (permalink / raw)
To: Tom Lane <tgl@sss.pgh.pa.us>; +Cc: Alvaro Herrera <alvherre@2ndquadrant.com>; Adrien Nayrat <adrien.nayrat@anayrat.info>; Thomas Munro <thomas.munro@enterprisedb.com>; Dmitry Dolgov <9erthalion6@gmail.com>; Tomas Vondra <tomas.vondra@2ndquadrant.com>; vik.fearing@2ndquadrant.com, Robert Haas <robertmhaas@gmail.com>; Michael Paquier <michael@paquier.xyz>; David Rowley <david.rowley@2ndquadrant.com>; pgsql-hackers
> About costs, not counting array accesses:
>
> - lrand48 (48 bits state as 3 uint16) is 29 ops
> (10 =, 8 *, 7 +, 4 >>)
> - xorshift+ (128 bits state as 2 uint64) is 13 ops
> ( 5 =, 0 *, 1 +, 3 >>, 4 ^)
> - xororshift128+ (idem) is 17 ops
> ( 6 =, 0 *, 1 +, 5 >>, 3 ^, 2 |, less if rot in hardware)
> - WELL512 (512 bits state as 16 uint32) is 38 ops
> (11 =, 0 *, 3 +, 7 >>, 10 ^, 4 &)
> probably much better, but probably slower than the current version
>
> I'd be of the (debatable) opinion that we could use xororshift128+, already
> used by various languages, even if it fails some specialized tests.
After some more digging, the better choice seems to be the 64 bits
optimized xoshiro256** (xoshiro = xor shift rotate):
- xoshiro256** (256 bits states as 4 uint64) is 24 ops (18 if rot in hw)
8 =, 2 *, 2 +, 5 <<, 5 ^, 2 |
See http://vigna.di.unimi.it/xorshift/
--
Fabien.
^ permalink raw reply [nested|flat] 33+ messages in thread
* Re: random() (was Re: New GUC to sample log queries)
2018-12-26 18:45 random() (was Re: New GUC to sample log queries) Tom Lane <tgl@sss.pgh.pa.us>
2018-12-27 08:36 ` Re: random() (was Re: New GUC to sample log queries) Fabien COELHO <coelho@cri.ensmp.fr>
2018-12-27 23:00 ` Re: random() (was Re: New GUC to sample log queries) Tom Lane <tgl@sss.pgh.pa.us>
2018-12-28 08:18 ` Re: random() (was Re: New GUC to sample log queries) Fabien COELHO <coelho@cri.ensmp.fr>
2018-12-28 08:44 ` Re: random() (was Re: New GUC to sample log queries) Fabien COELHO <coelho@cri.ensmp.fr>
@ 2018-12-28 11:07 ` Fabien COELHO <coelho@cri.ensmp.fr>
2018-12-28 14:27 ` Re: random() (was Re: New GUC to sample log queries) Fabien COELHO <coelho@cri.ensmp.fr>
0 siblings, 1 reply; 33+ messages in thread
From: Fabien COELHO @ 2018-12-28 11:07 UTC (permalink / raw)
To: Tom Lane <tgl@sss.pgh.pa.us>; +Cc: Alvaro Herrera <alvherre@2ndquadrant.com>; Adrien Nayrat <adrien.nayrat@anayrat.info>; Thomas Munro <thomas.munro@enterprisedb.com>; Dmitry Dolgov <9erthalion6@gmail.com>; Tomas Vondra <tomas.vondra@2ndquadrant.com>; vik.fearing@2ndquadrant.com, Robert Haas <robertmhaas@gmail.com>; Michael Paquier <michael@paquier.xyz>; David Rowley <david.rowley@2ndquadrant.com>; pgsql-hackers
>> - lrand48 (48 bits state as 3 uint16) is 29 ops
>> (10 =, 8 *, 7 +, 4 >>)
>
> - xoshiro256** (256 bits states as 4 uint64) is 24 ops (18 if rot in hw)
> 8 =, 2 *, 2 +, 5 <<, 5 ^, 2 |
>
> See http://vigna.di.unimi.it/xorshift/
Small benchmark on my laptop with gcc-7.3 -O3:
- pg_lrand48 takes 4.0 seconds to generate 1 billion 32-bit ints
- xoshiro256** takes 1.6 seconds to generate 1 billion 64-bit ints
With -O2 it is 4.8 and 3.4 seconds, respectively. So significantly better
speed _and_ quality are quite achievable.
Note that small attempt at optimizing these functions (inline constants,
array replaced with scalars) did not yield significant improvements.
--
Fabien.
Attachments:
[text/x-csrc] test_pg_erand48.c (1.6K, ../../alpine.DEB.2.21.1812281149090.32444@lancre/2-test_pg_erand48.c)
download | inline:
// pg erand48 implementation
#include <stdio.h>
#define RAND48_SEED_0 (0x330e)
#define RAND48_SEED_1 (0xabcd)
#define RAND48_SEED_2 (0x1234)
#define RAND48_MULT_0 (0xe66d)
#define RAND48_MULT_1 (0xdeec)
#define RAND48_MULT_2 (0x0005)
#define RAND48_ADD (0x000b)
static unsigned short _rand48_seed[3] = {
RAND48_SEED_0,
RAND48_SEED_1,
RAND48_SEED_2
};
static unsigned short _rand48_mult[3] = {
RAND48_MULT_0,
RAND48_MULT_1,
RAND48_MULT_2
};
static unsigned short _rand48_add = RAND48_ADD;
static void
_dorand48(unsigned short xseed[3])
{
unsigned long accu;
unsigned short temp[2];
accu = (unsigned long) _rand48_mult[0] * (unsigned long) xseed[0] +
(unsigned long) _rand48_add;
temp[0] = (unsigned short) accu; /* lower 16 bits */
accu >>= sizeof(unsigned short) * 8;
accu += (unsigned long) _rand48_mult[0] * (unsigned long) xseed[1] +
(unsigned long) _rand48_mult[1] * (unsigned long) xseed[0];
temp[1] = (unsigned short) accu; /* middle 16 bits */
accu >>= sizeof(unsigned short) * 8;
accu += _rand48_mult[0] * xseed[2] + _rand48_mult[1] * xseed[1] + _rand48_mult[2] * xseed[0];
xseed[0] = temp[0];
xseed[1] = temp[1];
xseed[2] = (unsigned short) accu;
}
long
pg_lrand48(void)
{
_dorand48(_rand48_seed);
return ((long) _rand48_seed[2] << 15) + ((long) _rand48_seed[1] >> 1);
}
int main(void)
{
long l;
for (int i = 0; i < 1000000000; i++)
l = pg_lrand48();
fprintf(stdout, "%ld\n", l);
return 0;
}
[text/x-csrc] test_xoroshi256ss.c (740B, ../../alpine.DEB.2.21.1812281149090.32444@lancre/3-test_xoroshi256ss.c)
download | inline:
// XOROSHI256**
#include <stdio.h>
#include <stdint.h>
static inline uint64_t rotl(const uint64_t x, int k) {
return (x << k) | (x >> (64 - k));
}
static uint64_t s[4];
uint64_t next(void) {
const uint64_t result_starstar = rotl(s[1] * 5, 7) * 9;
const uint64_t t = s[1] << 17;
s[2] ^= s[0];
s[3] ^= s[1];
s[1] ^= s[2];
s[0] ^= s[3];
s[2] ^= t;
s[3] = rotl(s[3], 45);
return result_starstar;
}
int main(void)
{
uint64_t l;
s[0] = 0xdeadbeefdeadbeefLL;
s[1] = 0xdeadbeefdeadbeefLL;
s[2] = 0xdeadbeefdeadbeefLL;
s[3] = 0xdeadbeefdeadbeefLL;
// loop 1 billion times
for (int i = 0; i < 1000000000; i++)
l = next();
fprintf(stdout, "%lu\n", l);
return 0;
}
^ permalink raw reply [nested|flat] 33+ messages in thread
* Re: random() (was Re: New GUC to sample log queries)
2018-12-26 18:45 random() (was Re: New GUC to sample log queries) Tom Lane <tgl@sss.pgh.pa.us>
2018-12-27 08:36 ` Re: random() (was Re: New GUC to sample log queries) Fabien COELHO <coelho@cri.ensmp.fr>
2018-12-27 23:00 ` Re: random() (was Re: New GUC to sample log queries) Tom Lane <tgl@sss.pgh.pa.us>
2018-12-28 08:18 ` Re: random() (was Re: New GUC to sample log queries) Fabien COELHO <coelho@cri.ensmp.fr>
2018-12-28 08:44 ` Re: random() (was Re: New GUC to sample log queries) Fabien COELHO <coelho@cri.ensmp.fr>
2018-12-28 11:07 ` Re: random() (was Re: New GUC to sample log queries) Fabien COELHO <coelho@cri.ensmp.fr>
@ 2018-12-28 14:27 ` Fabien COELHO <coelho@cri.ensmp.fr>
0 siblings, 0 replies; 33+ messages in thread
From: Fabien COELHO @ 2018-12-28 14:27 UTC (permalink / raw)
To: Tom Lane <tgl@sss.pgh.pa.us>; +Cc: Alvaro Herrera <alvherre@2ndquadrant.com>; Adrien Nayrat <adrien.nayrat@anayrat.info>; Thomas Munro <thomas.munro@enterprisedb.com>; Dmitry Dolgov <9erthalion6@gmail.com>; Tomas Vondra <tomas.vondra@2ndquadrant.com>; vik.fearing@2ndquadrant.com, Robert Haas <robertmhaas@gmail.com>; Michael Paquier <michael@paquier.xyz>; David Rowley <david.rowley@2ndquadrant.com>; pgsql-hackers
Hello again,
>>> - lrand48 (48 bits state as 3 uint16) is 29 ops
>>> (10 =, 8 *, 7 +, 4 >>)
>>
>> - xoshiro256** (256 bits states as 4 uint64) is 24 ops (18 if rot in hw)
>> 8 =, 2 *, 2 +, 5 <<, 5 ^, 2 |
>
> Small benchmark on my laptop with gcc-7.3 -O3:
>
> - pg_lrand48 takes 4.0 seconds to generate 1 billion 32-bit ints
> - xoshiro256** takes 1.6 seconds to generate 1 billion 64-bit ints
These too-good-to-be-true figures have raised doubt in my mind, so after
giving it some thought, I do not trust them: the function call is probably
inlined and other optimizations are performed which would not apply in a
more realistic case.
> With -O2 it is 4.8 and 3.4 seconds, respectively.
I trust this one, which is reasonably consistent with the operation count.
More tests with "clang -O2" yielded 3.2 and 1.6 respectively, that I do
not trust either.
I did separate compilation to prevent inlining and other undesirable
optimizations: clang -Ofast or -O2 gives 5.2 and 3.9, gcc -Ofast gives 5.4
and 3.5.
It seems that clang is better at compiling pg_erand48 but gcc is better at
xoroshi256**.
> So significantly better speed _and_ quality are quite achievable.
xoroshi256** is about 1/3 faster at producing twice as much pseudo-randoms
stuff, and it passed significant randomness tests that an LCG PRNG would
not.
--
Fabien.
^ permalink raw reply [nested|flat] 33+ messages in thread
* Re: random() (was Re: New GUC to sample log queries)
2018-12-26 18:45 random() (was Re: New GUC to sample log queries) Tom Lane <tgl@sss.pgh.pa.us>
2018-12-27 08:36 ` Re: random() (was Re: New GUC to sample log queries) Fabien COELHO <coelho@cri.ensmp.fr>
2018-12-27 23:00 ` Re: random() (was Re: New GUC to sample log queries) Tom Lane <tgl@sss.pgh.pa.us>
2018-12-28 08:18 ` Re: random() (was Re: New GUC to sample log queries) Fabien COELHO <coelho@cri.ensmp.fr>
@ 2018-12-28 17:29 ` Tom Lane <tgl@sss.pgh.pa.us>
1 sibling, 0 replies; 33+ messages in thread
From: Tom Lane @ 2018-12-28 17:29 UTC (permalink / raw)
To: Fabien COELHO <coelho@cri.ensmp.fr>; +Cc: Alvaro Herrera <alvherre@2ndquadrant.com>; Adrien Nayrat <adrien.nayrat@anayrat.info>; Thomas Munro <thomas.munro@enterprisedb.com>; Dmitry Dolgov <9erthalion6@gmail.com>; Tomas Vondra <tomas.vondra@2ndquadrant.com>; vik.fearing@2ndquadrant.com, Robert Haas <robertmhaas@gmail.com>; Michael Paquier <michael@paquier.xyz>; David Rowley <david.rowley@2ndquadrant.com>; pgsql-hackers
Fabien COELHO <coelho@cri.ensmp.fr> writes:
>> but I don't feel a need for replacing the algorithm.
> Hmmm. Does it mean that you would veto any change, even if the speed
> concern is addressed (i.e. faster/not slower with better quality)?
Well, not veto exactly, but I'd be suspicious of it.
First, erand48 has been around a *long* time and its properties are pretty
well understood; these other algorithms you found on the net have no real
pedigree IMO. Moreover, since it is standard, there's a lower cognitive
burden on people to understand what it is and what it can be trusted for.
Second, we don't actually have a problem we need to fix by changing the
algorithm. We do need to worry about keeping drandom's state separate
from the internal random() usages, but that's independent of what the
algorithm is. Nobody has complained that random() is insufficiently
random, only that the seed might be predictable.
I do agree, after closer inspection, that our current coding of _dorand48
is a hangover from machines lacking 64-bit arithmetic. glibc does it like
this:
int
__drand48_iterate (unsigned short int xsubi[3], struct drand48_data *buffer)
{
uint64_t X;
uint64_t result;
/* Initialize buffer, if not yet done. */
if (__glibc_unlikely (!buffer->__init))
{
buffer->__a = 0x5deece66dull;
buffer->__c = 0xb;
buffer->__init = 1;
}
/* Do the real work. We choose a data type which contains at least
48 bits. Because we compute the modulus it does not care how
many bits really are computed. */
X = (uint64_t) xsubi[2] << 32 | (uint32_t) xsubi[1] << 16 | xsubi[0];
result = X * buffer->__a + buffer->__c;
xsubi[0] = result & 0xffff;
xsubi[1] = (result >> 16) & 0xffff;
xsubi[2] = (result >> 32) & 0xffff;
return 0;
}
and other than the pointless use of variable __a and __c, I think
we ought to adopt similar coding.
regards, tom lane
^ permalink raw reply [nested|flat] 33+ messages in thread
* Re: random() (was Re: New GUC to sample log queries)
2018-12-26 18:45 random() (was Re: New GUC to sample log queries) Tom Lane <tgl@sss.pgh.pa.us>
@ 2018-12-28 12:10 ` Adrien NAYRAT <adrien.nayrat@anayrat.info>
3 siblings, 0 replies; 33+ messages in thread
From: Adrien NAYRAT @ 2018-12-28 12:10 UTC (permalink / raw)
To: Tom Lane <tgl@sss.pgh.pa.us>; Alvaro Herrera <alvherre@2ndquadrant.com>; +Cc: Thomas Munro <thomas.munro@enterprisedb.com>; Dmitry Dolgov <9erthalion6@gmail.com>; Tomas Vondra <tomas.vondra@2ndquadrant.com>; vik.fearing@2ndquadrant.com; Robert Haas <robertmhaas@gmail.com>; Michael Paquier <michael@paquier.xyz>; David Rowley <david.rowley@2ndquadrant.com>; pgsql-hackers
On 12/26/18 7:45 PM, Tom Lane wrote:
> I wonder whether we should establish a project policy to avoid use
> of random() for internal purposes, ie try to get to a point where
> drandom() is the only caller in the backend.
FYI I picked the idea from auto_explain. Maybe we will have to change
auto_explain too.
^ permalink raw reply [nested|flat] 33+ messages in thread
end of thread, other threads:[~2018-12-29 21:07 UTC | newest]
Thread overview: 33+ messages (download: mbox mbox.gz follow: Atom feed)
-- links below jump to the message on this page --
2018-12-26 18:45 random() (was Re: New GUC to sample log queries) Tom Lane <tgl@sss.pgh.pa.us>
2018-12-26 19:08 ` Peter Geoghegan <pg@bowt.ie>
2018-12-26 19:31 ` Tom Lane <tgl@sss.pgh.pa.us>
2018-12-26 19:46 ` Peter Geoghegan <pg@bowt.ie>
2018-12-26 19:56 ` Peter Geoghegan <pg@bowt.ie>
2018-12-26 20:19 ` Tom Lane <tgl@sss.pgh.pa.us>
2018-12-26 20:27 ` Peter Geoghegan <pg@bowt.ie>
2018-12-26 21:21 ` Tom Lane <tgl@sss.pgh.pa.us>
2018-12-26 21:48 ` Peter Geoghegan <pg@bowt.ie>
2018-12-27 01:34 ` Michael Paquier <michael@paquier.xyz>
2018-12-27 01:46 ` Tom Lane <tgl@sss.pgh.pa.us>
2018-12-27 02:04 ` Michael Paquier <michael@paquier.xyz>
2018-12-27 02:20 ` Peter Geoghegan <pg@bowt.ie>
2018-12-27 02:39 ` Tom Lane <tgl@sss.pgh.pa.us>
2018-12-27 02:55 ` Peter Geoghegan <pg@bowt.ie>
2018-12-27 04:55 ` Thomas Munro <thomas.munro@enterprisedb.com>
2018-12-27 19:36 ` Tom Lane <tgl@sss.pgh.pa.us>
2018-12-28 23:15 ` Tom Lane <tgl@sss.pgh.pa.us>
2018-12-29 00:36 ` Tom Lane <tgl@sss.pgh.pa.us>
2018-12-29 00:45 ` Thomas Munro <thomas.munro@enterprisedb.com>
2018-12-29 00:57 ` Tom Lane <tgl@sss.pgh.pa.us>
2018-12-29 21:07 ` Tom Lane <tgl@sss.pgh.pa.us>
2018-12-27 19:33 ` Tom Lane <tgl@sss.pgh.pa.us>
2018-12-27 20:00 ` Tom Lane <tgl@sss.pgh.pa.us>
2018-12-28 21:42 ` Tom Lane <tgl@sss.pgh.pa.us>
2018-12-27 08:36 ` Fabien COELHO <coelho@cri.ensmp.fr>
2018-12-27 23:00 ` Tom Lane <tgl@sss.pgh.pa.us>
2018-12-28 08:18 ` Fabien COELHO <coelho@cri.ensmp.fr>
2018-12-28 08:44 ` Fabien COELHO <coelho@cri.ensmp.fr>
2018-12-28 11:07 ` Fabien COELHO <coelho@cri.ensmp.fr>
2018-12-28 14:27 ` Fabien COELHO <coelho@cri.ensmp.fr>
2018-12-28 17:29 ` Tom Lane <tgl@sss.pgh.pa.us>
2018-12-28 12:10 ` Adrien NAYRAT <adrien.nayrat@anayrat.info>
This inbox is served by DDX for PostgreSQL; see mirroring instructions
for how to clone and mirror all data and code used for this inbox