Enable deterministic random number generation

Enable deterministic random number generation

This patch makes Math.random() behave deterministically when a fixed
random seed is provided. This is done by re-seeding the random number
generator the first time a script requests a random number. Doing this
ensures Math.random() returns the same sequence across page loads and
across iframes.

BUG=chromium:696001
Review-Url: https://codereview.chromium.org/2760393002
Cr-Commit-Position: refs/heads/master@{#44076}
Committed: https://chromium.googlesource.com/v8/v8/+/9b152fdafdd55f5e5ada88b9fae296d823f797c8

[Sami, 2017-03-21 18:51:26]

Description was changed from

==========
Enable deterministic random number generation

This patch makes two modifications to allow Math.random() to behave
deterministically:

1. Use a separate random number generator for script (i.e.,
   Math.random()) and for V8 internals. This avoids the problem of
   internal compiler operations perturbing the random number sequence
   observed by JavaScript.

2. If a fixed random number seed is provided, re-seed both random number
   generators to that value when a new context is created. This ensures
   Math.random() returns the same sequence across page loads.

BUG=chromium:696001
==========

to

==========
Enable deterministic random number generation

This patch makes two modifications to allow Math.random() to behave
deterministically:

1. Use a separate random number generator for script (i.e.,
   Math.random()) and for V8 internals. This avoids the problem of
   internal compiler operations perturbing the random number sequence
   observed by JavaScript.

2. If a fixed random number seed is provided, re-seed both random number
   generators to that value when a new context is created. This ensures
   Math.random() returns the same sequence across page loads.

BUG=chromium:696001
==========

[Sami, 2017-03-21 18:51:26]

skyostil@chromium.org changed reviewers:
+ rmcilroy@chromium.org

[Sami, 2017-03-21 18:51:43]

Hey Ross, can you review and/or suggest a reviewer?

[Sami, 2017-03-21 18:52:59]

The CQ bit was checked by skyostil@chromium.org to run a CQ dry run

[commit-bot: I haz the power, 2017-03-21 18:53:02]

Dry run: CQ is trying da patch. Follow status at
 
https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...

[commit-bot: I haz the power, 2017-03-21 19:19:56]

The CQ bit was unchecked by commit-bot@chromium.org

[commit-bot: I haz the power, 2017-03-21 19:19:57]

Dry run: This issue passed the CQ dry run.

[rmcilroy, 2017-03-22 16:37:23]

rmcilroy@chromium.org changed reviewers:
+ yangguo@chromium.org

[rmcilroy, 2017-03-22 16:37:23]

Looks reasonable to me but I think Yang would be the best review for this. Yang
could you review this for Sami please?

[Yang, 2017-03-22 18:12:03]

On 2017/03/22 16:37:23, rmcilroy wrote:
> Looks reasonable to me but I think Yang would be the best review for this.
Yang
> could you review this for Sami please?

I'm not fully convinced this is the right approach. This assumes that
(1) use order of random_number_generator() is not deterministic.
(2) order of initial calls to Math.random across native contexts is
deterministic.

But if (1) is the case, we already are missing the goal, and V8 does not truly
run deterministically. If (1) is fixed, there is no need for this CL.
Is (2) guaranteed? Is the order separate iframes execute JS deterministic?

Aside from this, we could achieve more or less the same by always seeding
Math.random() with the value in FLAG_random_seed. Or if necessary, increment
FLAG_random_seed every time.

[Sami, 2017-03-22 20:08:12]

On 2017/03/22 18:12:03, Yang wrote:
> On 2017/03/22 16:37:23, rmcilroy wrote:
> > Looks reasonable to me but I think Yang would be the best review for this.
> Yang
> > could you review this for Sami please?
> 
> I'm not fully convinced this is the right approach. This assumes that
> (1) use order of random_number_generator() is not deterministic.
> (2) order of initial calls to Math.random across native contexts is
> deterministic.
> 
> But if (1) is the case, we already are missing the goal, and V8 does not truly
> run deterministically. If (1) is fixed, there is no need for this CL.

I'm not a v8 expert, but I assumed fixing (1) isn't really feasible because of
the non-deterministic nature of things like garbage collection. Maybe that's not
the case? What would we need to change to make things deterministic?

> Is (2) guaranteed? Is the order separate iframes execute JS deterministic?

We're aiming to make that the case by doing things like deterministically
completing fetches in the same order and pausing JS execution while fetches are
pending.

> Aside from this, we could achieve more or less the same by always seeding
> Math.random() with the value in FLAG_random_seed. Or if necessary, increment
> FLAG_random_seed every time.

Do you mean seeding in some other place than bootstrapper.cc like in this patch?
FWIW I tried using a single generator and seeding it there, and because of (1)
the return values from Math.random() still weren't deterministic.

[Yang, 2017-03-22 20:31:33]

On 2017/03/22 20:08:12, Sami wrote:
> On 2017/03/22 18:12:03, Yang wrote:
> > On 2017/03/22 16:37:23, rmcilroy wrote:
> > > Looks reasonable to me but I think Yang would be the best review for this.
> > Yang
> > > could you review this for Sami please?
> > 
> > I'm not fully convinced this is the right approach. This assumes that
> > (1) use order of random_number_generator() is not deterministic.
> > (2) order of initial calls to Math.random across native contexts is
> > deterministic.
> > 
> > But if (1) is the case, we already are missing the goal, and V8 does not
truly
> > run deterministically. If (1) is fixed, there is no need for this CL.
> 
> I'm not a v8 expert, but I assumed fixing (1) isn't really feasible because of
> the non-deterministic nature of things like garbage collection. Maybe that's
not
> the case? What would we need to change to make things deterministic?
> 
> > Is (2) guaranteed? Is the order separate iframes execute JS deterministic?
> 
> We're aiming to make that the case by doing things like deterministically
> completing fetches in the same order and pausing JS execution while fetches
are
> pending.
> 
> > Aside from this, we could achieve more or less the same by always seeding
> > Math.random() with the value in FLAG_random_seed. Or if necessary, increment
> > FLAG_random_seed every time.
> 
> Do you mean seeding in some other place than bootstrapper.cc like in this
patch?
> FWIW I tried using a single generator and seeding it there, and because of (1)
> the return values from Math.random() still weren't deterministic.

regarding (1), have you tried --predictable?

[Yang, 2017-03-23 08:32:24]

On 2017/03/22 20:31:33, Yang wrote:
> On 2017/03/22 20:08:12, Sami wrote:
> > On 2017/03/22 18:12:03, Yang wrote:
> > > On 2017/03/22 16:37:23, rmcilroy wrote:
> > > > Looks reasonable to me but I think Yang would be the best review for
this.
> > > Yang
> > > > could you review this for Sami please?
> > > 
> > > I'm not fully convinced this is the right approach. This assumes that
> > > (1) use order of random_number_generator() is not deterministic.
> > > (2) order of initial calls to Math.random across native contexts is
> > > deterministic.
> > > 
> > > But if (1) is the case, we already are missing the goal, and V8 does not
> truly
> > > run deterministically. If (1) is fixed, there is no need for this CL.
> > 
> > I'm not a v8 expert, but I assumed fixing (1) isn't really feasible because
of
> > the non-deterministic nature of things like garbage collection. Maybe that's
> not
> > the case? What would we need to change to make things deterministic?
> > 
> > > Is (2) guaranteed? Is the order separate iframes execute JS deterministic?
> > 
> > We're aiming to make that the case by doing things like deterministically
> > completing fetches in the same order and pausing JS execution while fetches
> are
> > pending.
> > 
> > > Aside from this, we could achieve more or less the same by always seeding
> > > Math.random() with the value in FLAG_random_seed. Or if necessary,
increment
> > > FLAG_random_seed every time.
> > 
> > Do you mean seeding in some other place than bootstrapper.cc like in this
> patch?
> > FWIW I tried using a single generator and seeding it there, and because of
(1)
> > the return values from Math.random() still weren't deterministic.
> 
> regarding (1), have you tried --predictable?

Detailed answer. I haven't had time to respond more yesterday.

V8 offers a --predictable flag, which turns off concurrency features and other
sources of non-determinism. It should work fairly well, but can obviously
regress performance. If performance regression is not acceptable, you will have
to live with some non-determinism either way.

Regarding Math.random, it seems to me that resetting the seed of the random
number generators on the isolate in the bootstrapper is the wrong approach. The
bootstrapper is run every time a native context is created. So the seed for
Math.random in a particular native context would depend on how many times
Math.random in other native contexts have been seeded since the last time a
native context has been created.

This is seems unnecessarily complicated and not straight-forward to me. If every
native context seeds Math.random before a new native context is created,
Math.random in every native context returns the same sequence. If that's good
enough to you, why not simply seed Math.random with FLAG_random_seed in the
first place?

[Sami, 2017-03-23 10:52:37]

On 2017/03/23 08:32:24, Yang wrote:
> V8 offers a --predictable flag, which turns off concurrency features and other
> sources of non-determinism. It should work fairly well, but can obviously
> regress performance. If performance regression is not acceptable, you will
have
> to live with some non-determinism either way.

Thanks for the tip. I tried --predictable with a single random number generator
and looks like Math.random() still doesn't give a stable sequence. I'm testing
with a page like this by loading it once and then hitting reload:

<!DOCTYPE html>
<div id="r"></div>
<script>
document.querySelector('#r').innerHTML = Math.random();
</script>

> Regarding Math.random, it seems to me that resetting the seed of the random
> number generators on the isolate in the bootstrapper is the wrong approach.
The
> bootstrapper is run every time a native context is created. So the seed for
> Math.random in a particular native context would depend on how many times
> Math.random in other native contexts have been seeded since the last time a
> native context has been created.
> 
> This is seems unnecessarily complicated and not straight-forward to me. If
every
> native context seeds Math.random before a new native context is created,
> Math.random in every native context returns the same sequence. If that's good
> enough to you, why not simply seed Math.random with FLAG_random_seed in the
> first place?

I'm not very familiar with the terminology here: how does a native context
relate to Math.random? Seeding Math.random with a known seed for every newly
created Blink execution context (not sure what the v8 equivalent is) is exactly
what I'm trying to do, but I'm not sure where to do it. Do you mean doing the
seeding in Runtime_GenerateRandomNumbers directly?

[Yang, 2017-03-23 11:01:55]

On 2017/03/23 10:52:37, Sami wrote:
> On 2017/03/23 08:32:24, Yang wrote:
> > V8 offers a --predictable flag, which turns off concurrency features and
other
> > sources of non-determinism. It should work fairly well, but can obviously
> > regress performance. If performance regression is not acceptable, you will
> have
> > to live with some non-determinism either way.
> 
> Thanks for the tip. I tried --predictable with a single random number
generator
> and looks like Math.random() still doesn't give a stable sequence. I'm testing
> with a page like this by loading it once and then hitting reload:
> 
> <!DOCTYPE html>
> <div id="r"></div>
> <script>
> document.querySelector('#r').innerHTML = Math.random();
> </script>

I'm not trying to assign blame here, but if the V8 API is called
non-deterministically, V8 may behave non-deterministically as well. That being
said, I don't know how well --predictable works right now.

> 
> > Regarding Math.random, it seems to me that resetting the seed of the random
> > number generators on the isolate in the bootstrapper is the wrong approach.
> The
> > bootstrapper is run every time a native context is created. So the seed for
> > Math.random in a particular native context would depend on how many times
> > Math.random in other native contexts have been seeded since the last time a
> > native context has been created.
> > 
> > This is seems unnecessarily complicated and not straight-forward to me. If
> every
> > native context seeds Math.random before a new native context is created,
> > Math.random in every native context returns the same sequence. If that's
good
> > enough to you, why not simply seed Math.random with FLAG_random_seed in the
> > first place?
> 
> I'm not very familiar with the terminology here: how does a native context
> relate to Math.random? Seeding Math.random with a known seed for every newly
> created Blink execution context (not sure what the v8 equivalent is) is
exactly
> what I'm trying to do, but I'm not sure where to do it. Do you mean doing the
> seeding in Runtime_GenerateRandomNumbers directly?

A native context corresponds to an iframe and has its own global (window) object
including its own copy of JavaScript built-in objects. Each native context keeps
its own random state so that calls to Math.random in different native contexts
do not influence each other. And yes, I'm suggesting to use a fixed seed in
Runtime_GenerateRandomNumbers. The snippet of code that you changed there gets
executed every time Math.random is called for the first time in a native
context, as it has no random state yet.

[Sami, 2017-03-23 12:26:28]

On 2017/03/23 11:01:55, Yang wrote:
> I'm not trying to assign blame here, but if the V8 API is called
> non-deterministically, V8 may behave non-deterministically as well. That being
> said, I don't know how well --predictable works right now.

Ah I see, there are lots of potential ways for non-determinism to creep in. That
makes sense.

> A native context corresponds to an iframe and has its own global (window)
object
> including its own copy of JavaScript built-in objects. Each native context
keeps
> its own random state so that calls to Math.random in different native contexts
> do not influence each other. And yes, I'm suggesting to use a fixed seed in
> Runtime_GenerateRandomNumbers. The snippet of code that you changed there gets
> executed every time Math.random is called for the first time in a native
> context, as it has no random state yet.

Thanks, that makes things clearer. Re-seeding in Runtime_GenerateRandomNumbers
seems like a good approach -- done.

[Yang, 2017-03-23 12:30:13]

LGTM, with a suggestion though.

https://codereview.chromium.org/2760393002/diff/20001/src/runtime/runtime-mat...
File src/runtime/runtime-maths.cc (right):

https://codereview.chromium.org/2760393002/diff/20001/src/runtime/runtime-mat...
src/runtime/runtime-maths.cc:45:
isolate->random_number_generator()->SetSeed(FLAG_random_seed);
I wonder whether it would be easier to simply set state0 and state1 to
FLAG_random_seed, and not touch random_number_generator at all, since its also
used elsewhere.

[Yang, 2017-03-23 12:33:12]

On 2017/03/23 12:30:13, Yang wrote:
> LGTM, with a suggestion though.
> 
>
https://codereview.chromium.org/2760393002/diff/20001/src/runtime/runtime-mat...
> File src/runtime/runtime-maths.cc (right):
> 
>
https://codereview.chromium.org/2760393002/diff/20001/src/runtime/runtime-mat...
> src/runtime/runtime-maths.cc:45:
> isolate->random_number_generator()->SetSeed(FLAG_random_seed);
> I wonder whether it would be easier to simply set state0 and state1 to
> FLAG_random_seed, and not touch random_number_generator at all, since its also
> used elsewhere.

Oh and please update CL description!

[Sami, 2017-03-23 16:52:16]

Description was changed from

==========
Enable deterministic random number generation

This patch makes two modifications to allow Math.random() to behave
deterministically:

1. Use a separate random number generator for script (i.e.,
   Math.random()) and for V8 internals. This avoids the problem of
   internal compiler operations perturbing the random number sequence
   observed by JavaScript.

2. If a fixed random number seed is provided, re-seed both random number
   generators to that value when a new context is created. This ensures
   Math.random() returns the same sequence across page loads.

BUG=chromium:696001
==========

to

==========
Enable deterministic random number generation

This patch makes Math.random() behave deterministically when a fixed
random seed is provided. This is done by re-seeding the random number
generator the first time a script requests a random number. Doing this
ensures Math.random() returns the same sequence across page loads and
across iframes.

BUG=chromium:696001
==========

[Sami, 2017-03-23 16:52:41]

On 2017/03/23 12:33:12, Yang wrote:
> Oh and please update CL description!

Thanks, done!

[Yang, 2017-03-23 16:53:56]

On 2017/03/23 16:52:41, Sami wrote:
> On 2017/03/23 12:33:12, Yang wrote:
> > Oh and please update CL description!
> 
> Thanks, done!

Did you see the suggestion I had in #18?

[Sami, 2017-03-23 17:00:18]

Initialize state directly

[Sami, 2017-03-23 17:00:27]

https://codereview.chromium.org/2760393002/diff/20001/src/runtime/runtime-mat...
File src/runtime/runtime-maths.cc (right):

https://codereview.chromium.org/2760393002/diff/20001/src/runtime/runtime-mat...
src/runtime/runtime-maths.cc:45:
isolate->random_number_generator()->SetSeed(FLAG_random_seed);
On 2017/03/23 12:30:13, Yang wrote:
> I wonder whether it would be easier to simply set state0 and state1 to
> FLAG_random_seed, and not touch random_number_generator at all, since its also
> used elsewhere.

Sorry, missed this comment earlier. Yeah, that would be a simpler change. Done,
PTAL.

[Yang, 2017-03-23 17:22:23]

On 2017/03/23 17:00:27, Sami wrote:
>
https://codereview.chromium.org/2760393002/diff/20001/src/runtime/runtime-mat...
> File src/runtime/runtime-maths.cc (right):
> 
>
https://codereview.chromium.org/2760393002/diff/20001/src/runtime/runtime-mat...
> src/runtime/runtime-maths.cc:45:
> isolate->random_number_generator()->SetSeed(FLAG_random_seed);
> On 2017/03/23 12:30:13, Yang wrote:
> > I wonder whether it would be easier to simply set state0 and state1 to
> > FLAG_random_seed, and not touch random_number_generator at all, since its
also
> > used elsewhere.
> 
> Sorry, missed this comment earlier. Yeah, that would be a simpler change.
Done,
> PTAL.

Thanks. LGTM!

[Yang, 2017-03-23 17:31:57]

The CQ bit was checked by yangguo@chromium.org to run a CQ dry run

[commit-bot: I haz the power, 2017-03-23 17:32:00]

Dry run: CQ is trying da patch. Follow status at
 
https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...

[Sami, 2017-03-23 17:44:40]

The CQ bit was unchecked by skyostil@chromium.org

[Sami, 2017-03-23 17:44:54]

The CQ bit was checked by skyostil@chromium.org

[commit-bot: I haz the power, 2017-03-23 17:44:58]

CQ is trying da patch. Follow status at
 
https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...

[commit-bot: I haz the power, 2017-03-23 18:14:41]

CQ is committing da patch.

Bot data: {"patchset_id": 40001, "attempt_start_ts": 1490291094936830,
"parent_rev": "fb52f5c55cb9bf8403931851b3a2d47512db45c2", "commit_rev":
"9b152fdafdd55f5e5ada88b9fae296d823f797c8"}

[commit-bot: I haz the power, 2017-03-23 18:14:47]

Description was changed from

==========
Enable deterministic random number generation

This patch makes Math.random() behave deterministically when a fixed
random seed is provided. This is done by re-seeding the random number
generator the first time a script requests a random number. Doing this
ensures Math.random() returns the same sequence across page loads and
across iframes.

BUG=chromium:696001
==========

to

==========
Enable deterministic random number generation

This patch makes Math.random() behave deterministically when a fixed
random seed is provided. This is done by re-seeding the random number
generator the first time a script requests a random number. Doing this
ensures Math.random() returns the same sequence across page loads and
across iframes.

BUG=chromium:696001

Review-Url: https://codereview.chromium.org/2760393002
Cr-Commit-Position: refs/heads/master@{#44076}
Committed:
https://chromium.googlesource.com/v8/v8/+/9b152fdafdd55f5e5ada88b9fae296d823f...
==========

[commit-bot: I haz the power, 2017-03-23 18:14:48]

Committed patchset #3 (id:40001) as
https://chromium.googlesource.com/v8/v8/+/9b152fdafdd55f5e5ada88b9fae296d823f...