DSM segment handle generation in background workers

On Mon, Oct 8, 2018 at 1:17 AM Thomas Munro
<thomas.munro@enterprisedb.com> wrote:

That's because the bgworker startup path doesn't contain a call to
srandom(...distinguishing stuff...), unlike BackendRun(). I suppose
do_start_bgworker() could gain a similar call... or perhaps that call
should be moved into InitPostmasterChild(). If we put it in there
right after MyStartTime is assigned a new value, we could use the same
incantation that PostmasterMain() uses.

I noticed that the comment in PostmasterMain() refers to
PostmasterRandom(), which is gone.

Maybe something like this?

--
Thomas Munro
http://www.enterprisedb.com

Thomas Munro <thomas.munro@enterprisedb.com> writes:

On Mon, Oct 8, 2018 at 1:17 AM Thomas Munro
<thomas.munro@enterprisedb.com> wrote:

That's because the bgworker startup path doesn't contain a call to
srandom(...distinguishing stuff...), unlike BackendRun(). I suppose
do_start_bgworker() could gain a similar call... or perhaps that call
should be moved into InitPostmasterChild(). If we put it in there
right after MyStartTime is assigned a new value, we could use the same
incantation that PostmasterMain() uses.

Maybe something like this?

I think the bit with

#ifndef HAVE_STRONG_RANDOM
random_seed = 0;
random_start_time.tv_usec = 0;
#endif

should also be done in every postmaster child, no? If we want to hide the
postmaster's state from child processes, we ought to hide it from all.

regards, tom lane

On Tue, Oct 9, 2018 at 1:53 PM Tom Lane <tgl@sss.pgh.pa.us> wrote:

Thomas Munro <thomas.munro@enterprisedb.com> writes:

On Mon, Oct 8, 2018 at 1:17 AM Thomas Munro
<thomas.munro@enterprisedb.com> wrote:

That's because the bgworker startup path doesn't contain a call to
srandom(...distinguishing stuff...), unlike BackendRun(). I suppose
do_start_bgworker() could gain a similar call... or perhaps that call
should be moved into InitPostmasterChild(). If we put it in there
right after MyStartTime is assigned a new value, we could use the same
incantation that PostmasterMain() uses.

Maybe something like this?

I think the bit with

#ifndef HAVE_STRONG_RANDOM
random_seed = 0;
random_start_time.tv_usec = 0;
#endif

should also be done in every postmaster child, no? If we want to hide the
postmaster's state from child processes, we ought to hide it from all.

Ok, here is a sketch patch with a new function InitRandomSeeds() to do
that. It is called from PostmasterMain(), InitPostmasterChild() and
InitStandaloneProcess() for consistency.

It seems a bit strange to me that internal infrastructure shares a
random number generator with SQL-callable functions random() and
setseed(), though I'm not saying it's harmful.

While wondering if something like this should be back-patched, I
noticed that SQL random() is declared as parallel-restricted, which is
good: it means we aren't exposing a random() function that generates
the same values in every parallel worker. So I think this is probably
just a minor nuisance and should probably only be pushed to master, or
at most to 11 (since Parallel Hash likes to create DSM segments in
workers), unless someone can think of a more serious way this can hurt
you.

(Tangentially: I suppose it might be useful to have a different SQL
random number function that is parallel safe, that isn't associated
with a user-controllable seed, and whose seed is different in each
backend.)

--
Thomas Munro
http://www.enterprisedb.com

On Tue, Oct 9, 2018 at 3:21 PM Thomas Munro
<thomas.munro@enterprisedb.com> wrote:

On Tue, Oct 9, 2018 at 1:53 PM Tom Lane <tgl@sss.pgh.pa.us> wrote:

Thomas Munro <thomas.munro@enterprisedb.com> writes:

On Mon, Oct 8, 2018 at 1:17 AM Thomas Munro
<thomas.munro@enterprisedb.com> wrote:

That's because the bgworker startup path doesn't contain a call to
srandom(...distinguishing stuff...), unlike BackendRun(). I suppose
do_start_bgworker() could gain a similar call... or perhaps that call
should be moved into InitPostmasterChild(). If we put it in there
right after MyStartTime is assigned a new value, we could use the same
incantation that PostmasterMain() uses.

Maybe something like this?

I think the bit with

#ifndef HAVE_STRONG_RANDOM
random_seed = 0;
random_start_time.tv_usec = 0;
#endif

should also be done in every postmaster child, no? If we want to hide the
postmaster's state from child processes, we ought to hide it from all.

Ok, here is a sketch patch with a new function InitRandomSeeds() to do
that. It is called from PostmasterMain(), InitPostmasterChild() and
InitStandaloneProcess() for consistency.

Here's a version I propose to push to master and 11 tomorrow, if there
are no objections.

--
Thomas Munro
http://www.enterprisedb.com

Thomas Munro <thomas.munro@enterprisedb.com> writes:

Ok, here is a sketch patch with a new function InitRandomSeeds() to do
that. It is called from PostmasterMain(), InitPostmasterChild() and
InitStandaloneProcess() for consistency.

Here's a version I propose to push to master and 11 tomorrow, if there
are no objections.

The comment adjacent to the change in InitStandaloneProcess bothers me.
In particular, it points out that what BackendRun() is currently doing
creates more entropy in the process's random seed than what you have
here: MyStartTime is only good to the nearest second, whereas the code
you removed from BackendRun() factors in fractional seconds to whatever
the precision of GetCurrentTimestamp is. This does not seem like an
improvement.

I'm inclined to think we should refactor a bit more aggressively so
that, rather than dumbing backends down to the standard of other
processes, we make them all use the better method. A reasonable way
to approach this would be to invent a global variable MyStartTimestamp
beside MyStartTime, and initialize both of them in the places that
currently initialize the latter, using code like that in
BackendInitialize:

/* save process start time */
port->SessionStartTime = GetCurrentTimestamp();
MyStartTime = timestamptz_to_time_t(port->SessionStartTime);

and then this new InitRandomSeeds function could adopt BackendRun's
seed initialization method instead of the stupider way.

Possibly it'd be sane to merge the MyStartTime* initializations
and the srandom resets into one function, not sure.

regards, tom lane

On Thu, Oct 11, 2018 at 5:51 PM Tom Lane <tgl@sss.pgh.pa.us> wrote:

The comment adjacent to the change in InitStandaloneProcess bothers me.
In particular, it points out that what BackendRun() is currently doing
creates more entropy in the process's random seed than what you have
here: MyStartTime is only good to the nearest second, whereas the code
you removed from BackendRun() factors in fractional seconds to whatever
the precision of GetCurrentTimestamp is. This does not seem like an
improvement.

True.

I'm inclined to think we should refactor a bit more aggressively so
that, rather than dumbing backends down to the standard of other
processes, we make them all use the better method. A reasonable way
to approach this would be to invent a global variable MyStartTimestamp
beside MyStartTime, and initialize both of them in the places that
currently initialize the latter, using code like that in
BackendInitialize:

/* save process start time */
port->SessionStartTime = GetCurrentTimestamp();
MyStartTime = timestamptz_to_time_t(port->SessionStartTime);

and then this new InitRandomSeeds function could adopt BackendRun's
seed initialization method instead of the stupider way.

Ok, done.

With MyStartTimestamp in the picture, port->SessionStartTime is
probably redundant... <looks around> and in fact the comment in struct
Port says it shouldn't even be there. So... I removed it, and used
the new MyStartTimestamp in the couple of places that wanted it.
Thoughts?

Possibly it'd be sane to merge the MyStartTime* initializations
and the srandom resets into one function, not sure.

+1

The main difficulty was coming up with a name for the function that
does those things. I went with InitProcessGlobals(). Better
suggestions welcome.

--
Thomas Munro
http://www.enterprisedb.com

On Sat, Oct 13, 2018 at 11:45 PM Thomas Munro
<thomas.munro@enterprisedb.com> wrote:

On Thu, Oct 11, 2018 at 5:51 PM Tom Lane <tgl@sss.pgh.pa.us> wrote:

The comment adjacent to the change in InitStandaloneProcess bothers me.
In particular, it points out that what BackendRun() is currently doing
creates more entropy in the process's random seed than what you have
here: MyStartTime is only good to the nearest second, whereas the code
you removed from BackendRun() factors in fractional seconds to whatever
the precision of GetCurrentTimestamp is. This does not seem like an
improvement.

True.

I'm inclined to think we should refactor a bit more aggressively so
that, rather than dumbing backends down to the standard of other
processes, we make them all use the better method. A reasonable way
to approach this would be to invent a global variable MyStartTimestamp
beside MyStartTime, and initialize both of them in the places that
currently initialize the latter, using code like that in
BackendInitialize:

/* save process start time */
port->SessionStartTime = GetCurrentTimestamp();
MyStartTime = timestamptz_to_time_t(port->SessionStartTime);

and then this new InitRandomSeeds function could adopt BackendRun's
seed initialization method instead of the stupider way.

Ok, done.

With MyStartTimestamp in the picture, port->SessionStartTime is
probably redundant... <looks around> and in fact the comment in struct
Port says it shouldn't even be there. So... I removed it, and used
the new MyStartTimestamp in the couple of places that wanted it.
Thoughts?

Possibly it'd be sane to merge the MyStartTime* initializations
and the srandom resets into one function, not sure.

+1

The main difficulty was coming up with a name for the function that
does those things. I went with InitProcessGlobals(). Better
suggestions welcome.

Pushed to master only.

--
Thomas Munro
http://www.enterprisedb.com

On Sat, Oct 13, 2018 at 11:45:17PM +1300, Thomas Munro wrote:

+	/* Set a different seed for random() in every backend. */
+	srandom((unsigned int) MyProcPid ^ (unsigned int) MyStartTimestamp);

- TimestampDifference(0, port->SessionStartTime, &secs, &usecs);
- srandom((unsigned int) (MyProcPid ^ (usecs << 12) ^ secs));

Compared to the old code, the new code requires more wall time to visit every
possible seed value. New code xor's the PID bits into the fastest-changing
timestamp bits, so only about twenty bits can vary within any given one-second
period. (That assumes a PID space of twenty or fewer bits; fifteen bits is
the Linux default.) Is that aspect of the change justified?

On Mon, Nov 12, 2018 at 9:34 PM Noah Misch <noah@leadboat.com> wrote:

On Sat, Oct 13, 2018 at 11:45:17PM +1300, Thomas Munro wrote:

+     /* Set a different seed for random() in every backend. */
+     srandom((unsigned int) MyProcPid ^ (unsigned int) MyStartTimestamp);

- TimestampDifference(0, port->SessionStartTime, &secs, &usecs);
- srandom((unsigned int) (MyProcPid ^ (usecs << 12) ^ secs));

Compared to the old code, the new code requires more wall time to visit every
possible seed value. New code xor's the PID bits into the fastest-changing
timestamp bits, so only about twenty bits can vary within any given one-second
period. (That assumes a PID space of twenty or fewer bits; fifteen bits is
the Linux default.) Is that aspect of the change justified?

Hmm, right. How about applying pg_bswap32() to one of the terms, as
an easy approximation of reversing the bits?

--
Thomas Munro
http://www.enterprisedb.com

Thomas Munro <thomas.munro@enterprisedb.com> writes:

On Mon, Nov 12, 2018 at 9:34 PM Noah Misch <noah@leadboat.com> wrote:

Compared to the old code, the new code requires more wall time to visit every
possible seed value. New code xor's the PID bits into the fastest-changing
timestamp bits, so only about twenty bits can vary within any given one-second
period. (That assumes a PID space of twenty or fewer bits; fifteen bits is
the Linux default.) Is that aspect of the change justified?

Hmm, right. How about applying pg_bswap32() to one of the terms, as
an easy approximation of reversing the bits?

I doubt that's a good idea; to a first approximation, it would mean that
half the seed depends only on the PID and the other half only on the
timestamp. Maybe we could improve matters a little by left-shifting the
PID four bits or so, but I think we still want it to mix with some
rapidly-changing time bits.

I'm not really sure that we need to do anything though. Basically,
what we've got here is a tradeoff between how many bits change over
a given timespan and how unpredictable those bits are. I don't see
that one of those is necessarily more important than the other.

regards, tom lane

On Mon, Nov 12, 2018 at 09:39:01AM -0500, Tom Lane wrote:

Thomas Munro <thomas.munro@enterprisedb.com> writes:

On Mon, Nov 12, 2018 at 9:34 PM Noah Misch <noah@leadboat.com> wrote:

Compared to the old code, the new code requires more wall time to visit every
possible seed value. New code xor's the PID bits into the fastest-changing
timestamp bits, so only about twenty bits can vary within any given one-second
period. (That assumes a PID space of twenty or fewer bits; fifteen bits is
the Linux default.) Is that aspect of the change justified?

Hmm, right. How about applying pg_bswap32() to one of the terms, as
an easy approximation of reversing the bits?

That seems adequate, yes. But why not just restore the old algorithm in the
new function? (I'm not opposed to revising the algorithm, but I think a
revision should have explicit goals. The ease of pg_bswap32() is not itself a
worthy goal, because the old BackendRun() algorithm was also quite easy.)

I doubt that's a good idea; to a first approximation, it would mean that
half the seed depends only on the PID and the other half only on the
timestamp. Maybe we could improve matters a little by left-shifting the
PID four bits or so, but I think we still want it to mix with some
rapidly-changing time bits.

I'm not really sure that we need to do anything though. Basically,
what we've got here is a tradeoff between how many bits change over
a given timespan and how unpredictable those bits are. I don't see
that one of those is necessarily more important than the other.

What counts is the ease of predicting a complete seed. HEAD's algorithm has
~13 trivially-predictable bits, and the algorithm that stood in BackendRun()
from 98c5065 until 197e4af had no such bits. You're right that the other 19
bits are harder to predict than any given 19 bits under the old algorithm, but
the complete seed remains more predictable than it was before 197e4af.

Goal I recommend: if connections arrive in a Poisson distribution of unknown
lambda, maximize the number of distinct seeds.

nm

On Wed, Nov 14, 2018 at 3:24 PM Noah Misch <noah@leadboat.com> wrote:

On Mon, Nov 12, 2018 at 09:39:01AM -0500, Tom Lane wrote:

Thomas Munro <thomas.munro@enterprisedb.com> writes:

On Mon, Nov 12, 2018 at 9:34 PM Noah Misch <noah@leadboat.com> wrote:

Compared to the old code, the new code requires more wall time to visit every
possible seed value. New code xor's the PID bits into the fastest-changing
timestamp bits, so only about twenty bits can vary within any given one-second
period. (That assumes a PID space of twenty or fewer bits; fifteen bits is
the Linux default.) Is that aspect of the change justified?

Hmm, right. How about applying pg_bswap32() to one of the terms, as
an easy approximation of reversing the bits?

That seems adequate, yes. But why not just restore the old algorithm in the
new function? (I'm not opposed to revising the algorithm, but I think a
revision should have explicit goals. The ease of pg_bswap32() is not itself a
worthy goal, because the old BackendRun() algorithm was also quite easy.)

Ok. I rewrote it only because in the new coding I had a TimestampTz
rather than the separate sec and usec components of the old code. I
didn't intend to revise the algorithm fundamentally, but I missed the
significance of the bit shifting from commit 98c50656c that moved the
faster moving bits up. I'll change it back.

I doubt that's a good idea; to a first approximation, it would mean that
half the seed depends only on the PID and the other half only on the
timestamp. Maybe we could improve matters a little by left-shifting the
PID four bits or so, but I think we still want it to mix with some
rapidly-changing time bits.

I'm not really sure that we need to do anything though. Basically,
what we've got here is a tradeoff between how many bits change over
a given timespan and how unpredictable those bits are. I don't see
that one of those is necessarily more important than the other.

What counts is the ease of predicting a complete seed. HEAD's algorithm has
~13 trivially-predictable bits, and the algorithm that stood in BackendRun()
from 98c5065 until 197e4af had no such bits. You're right that the other 19
bits are harder to predict than any given 19 bits under the old algorithm, but
the complete seed remains more predictable than it was before 197e4af.

However we mix them, given that the source code is well known, isn't
an attacker's job really to predict the time and pid, two not
especially well guarded secrets? I don't see how the mixing matters
in that respect. (You can also just clobber the seed from SQL, but
that'd be cheating.)

Goal I recommend: if connections arrive in a Poisson distribution of unknown
lambda, maximize the number of distinct seeds.

Yeah. I think bit reversing one of them achieves the maximum number
of distinct seeds by putting the busy ends far apart, but the original
bit shifting is similar.

--
Thomas Munro
http://www.enterprisedb.com

On Wed, Nov 14, 2018 at 05:50:26PM +1300, Thomas Munro wrote:

On Wed, Nov 14, 2018 at 3:24 PM Noah Misch <noah@leadboat.com> wrote:

On Mon, Nov 12, 2018 at 09:39:01AM -0500, Tom Lane wrote:

I doubt that's a good idea; to a first approximation, it would mean that
half the seed depends only on the PID and the other half only on the
timestamp. Maybe we could improve matters a little by left-shifting the
PID four bits or so, but I think we still want it to mix with some
rapidly-changing time bits.

I'm not really sure that we need to do anything though. Basically,
what we've got here is a tradeoff between how many bits change over
a given timespan and how unpredictable those bits are. I don't see
that one of those is necessarily more important than the other.

What counts is the ease of predicting a complete seed. HEAD's algorithm has
~13 trivially-predictable bits, and the algorithm that stood in BackendRun()
from 98c5065 until 197e4af had no such bits. You're right that the other 19
bits are harder to predict than any given 19 bits under the old algorithm, but
the complete seed remains more predictable than it was before 197e4af.

However we mix them, given that the source code is well known, isn't
an attacker's job really to predict the time and pid, two not
especially well guarded secrets?

True. Better to frame the issue as uniform distribution of seed, not
unpredictability of seed selection.

Incidentally, possible future work may be to use pg_strong_random() when
available, like pgbench set_random_seed() does. That would achieve both
unpredictability and uniform distribution. It would be mere defense in depth;
if unpredictability matters, one still needs a CSPRNG (e.g. pgcrypto).

On Wed, Nov 14, 2018 at 6:34 PM Noah Misch <noah@leadboat.com> wrote:

On Wed, Nov 14, 2018 at 05:50:26PM +1300, Thomas Munro wrote:

On Wed, Nov 14, 2018 at 3:24 PM Noah Misch <noah@leadboat.com> wrote:

What counts is the ease of predicting a complete seed. HEAD's algorithm has
~13 trivially-predictable bits, and the algorithm that stood in BackendRun()
from 98c5065 until 197e4af had no such bits. You're right that the other 19
bits are harder to predict than any given 19 bits under the old algorithm, but
the complete seed remains more predictable than it was before 197e4af.

However we mix them, given that the source code is well known, isn't
an attacker's job really to predict the time and pid, two not
especially well guarded secrets?

True. Better to frame the issue as uniform distribution of seed, not
unpredictability of seed selection.

What do you think about the attached?

--
Thomas Munro
http://www.enterprisedb.com

On Wed, Nov 14, 2018 at 08:22:42PM +1300, Thomas Munro wrote:

On Wed, Nov 14, 2018 at 6:34 PM Noah Misch <noah@leadboat.com> wrote:

On Wed, Nov 14, 2018 at 05:50:26PM +1300, Thomas Munro wrote:

On Wed, Nov 14, 2018 at 3:24 PM Noah Misch <noah@leadboat.com> wrote:

What counts is the ease of predicting a complete seed. HEAD's algorithm has
~13 trivially-predictable bits, and the algorithm that stood in BackendRun()
from 98c5065 until 197e4af had no such bits. You're right that the other 19
bits are harder to predict than any given 19 bits under the old algorithm, but
the complete seed remains more predictable than it was before 197e4af.

However we mix them, given that the source code is well known, isn't
an attacker's job really to predict the time and pid, two not
especially well guarded secrets?

True. Better to frame the issue as uniform distribution of seed, not
unpredictability of seed selection.

What do you think about the attached?

You mentioned that you rewrote the algorithm because the new function had a
TimestampTz. But the BackendRun() code, which it replaced, also had a
TimestampTz. You can reuse the exact algorithm. Is there a reason to change?

On Wed, Nov 14, 2018 at 8:52 PM Noah Misch <noah@leadboat.com> wrote:

On Wed, Nov 14, 2018 at 08:22:42PM +1300, Thomas Munro wrote:

On Wed, Nov 14, 2018 at 6:34 PM Noah Misch <noah@leadboat.com> wrote:

On Wed, Nov 14, 2018 at 05:50:26PM +1300, Thomas Munro wrote:

On Wed, Nov 14, 2018 at 3:24 PM Noah Misch <noah@leadboat.com> wrote:

What counts is the ease of predicting a complete seed. HEAD's algorithm has
~13 trivially-predictable bits, and the algorithm that stood in BackendRun()
from 98c5065 until 197e4af had no such bits. You're right that the other 19
bits are harder to predict than any given 19 bits under the old algorithm, but
the complete seed remains more predictable than it was before 197e4af.

However we mix them, given that the source code is well known, isn't
an attacker's job really to predict the time and pid, two not
especially well guarded secrets?

True. Better to frame the issue as uniform distribution of seed, not
unpredictability of seed selection.

What do you think about the attached?

You mentioned that you rewrote the algorithm because the new function had a
TimestampTz. But the BackendRun() code, which it replaced, also had a
TimestampTz. You can reuse the exact algorithm. Is there a reason to change?

The old code used a "slightly hacky way to convert timestamptz into
integers" because TimestampTz might have been floating point back in
the day. Now that TimestampTz is always an integer, we might as well
use it directly and shuffle its bits for the same general effect, no?
The difference between x >> 20 and x / USECS_PER_SEC doesn't seem to
be material.

--
Thomas Munro
http://www.enterprisedb.com

Thomas Munro <thomas.munro@enterprisedb.com> writes:

What do you think about the attached?

I think you need to cast MyStartTimestamp to uint64 before shifting
to ensure portable behavior of the shifts. In principle it wouldn't
matter because the int64 sign bit is nowhere near the part we care
about, but I've heard some pretty wild claims about what compiler
writers are entitled to do with "undefined" cases.

regards, tom lane

On Thu, Nov 15, 2018 at 4:25 AM Tom Lane <tgl@sss.pgh.pa.us> wrote:

Thomas Munro <thomas.munro@enterprisedb.com> writes:

What do you think about the attached?

I think you need to cast MyStartTimestamp to uint64 before shifting
to ensure portable behavior of the shifts. In principle it wouldn't
matter because the int64 sign bit is nowhere near the part we care
about, but I've heard some pretty wild claims about what compiler
writers are entitled to do with "undefined" cases.

Thanks. Pushed.

--
Thomas Munro
http://www.enterprisedb.com