Add RoutingIDIssuer to ensure the correctness of ID to be routed.

Add RoutingIDIssuer to ensure the correctness of ID to be routed.

This CL introduces RoutingIDIssuer which tracks issued routing
ID per RenderProcessHost and let the Host class verify
routing ids to get routed.

TEST=routing_id_issuer_unitteest.cc
R=jam@chromium.org, sky@chromium.org
TBR=mattm@chromium.org
BUG=381990, 415059
Committed: https://crrev.com/d3e91b36c3c29aee92159db9d5cc331cd3f97241
Cr-Commit-Position: refs/heads/master@{#299423}

[Hajime Morrita, 2014-10-09 20:03:09]

This is for investigating the mysterious crash that blocks
MojoApplicationHost to fly.

[Hajime Morrita, 2014-10-10 00:07:10]

@nasko: When you have time, would you mind to look why
site_per_process_accessibility_browsertest.cc fails without the workaround this
CL adds?

This CL gives some offset to routing IDS based on its host process.
As it just adds an offset, it shouldn't affect the behavior.
Some tests depend on the fact that the ID starts from one, but the accessibility
one
doesn't seem to have such assumption. So I'm wondering why it fails.

[Hajime Morrita, 2014-10-10 00:52:49]

morrita@chromium.org changed reviewers:
+ mattm@chromium.org, nasko@chromium.org, noelutz@chromium.org

[Hajime Morrita, 2014-10-10 00:52:49]

OK, bots are almost green. PTAL?
nasko: content/ 
mattm, noelutz: safe_browsing/ - Adding a workaround to tests.

[Hajime Morrita, 2014-10-11 00:05:18]

OK, now this is green. 
Nasko: PTAL?

[nasko, 2014-10-13 21:03:59]

nasko@chromium.org changed reviewers:
+ nick@chromium.org

[nasko, 2014-10-13 21:04:01]

Some nits and questions, but overall nice idea!

Adding nick@, who I've been bouncing ideas with.

Couple of notes:
* The stack traces that nick@ looked at had the same RenderProcessHost at the
PostTask stack frame and the AddRoute.
* The routing id in one of the traces I looked was 3, suggesting the first
iframe added on a page in a brand new process.

Also, there is one usage of AddRoute in embedded_worker_devtools_agent_host.cc
which wasn't immediately clear if it is correct and needs some auditing.

https://codereview.chromium.org/643733002/diff/910001/content/browser/rendere...
File content/browser/renderer_host/render_widget_helper.h (right):

https://codereview.chromium.org/643733002/diff/910001/content/browser/rendere...
content/browser/renderer_host/render_widget_helper.h:84: // Probablistically
verify if he ID is issued by this helper.
nit: s/if he/if the/

https://codereview.chromium.org/643733002/diff/910001/content/browser/rendere...
content/browser/renderer_host/render_widget_helper.h:86: int
IsRoutingIDProbablyValid(int routing_id) const;
Why return int, when the expected output value is boolean?

https://codereview.chromium.org/643733002/diff/910001/content/browser/rendere...
File content/browser/renderer_host/routing_id_issuer.cc (right):

https://codereview.chromium.org/643733002/diff/910001/content/browser/rendere...
content/browser/renderer_host/routing_id_issuer.cc:11: const int kManglerBit =
3;
nit: I'll name the *Bit variables as *Bits, as it makes reading it a bit easier.

https://codereview.chromium.org/643733002/diff/910001/content/browser/rendere...
content/browser/renderer_host/routing_id_issuer.cc:18: int g_manglerSequence =
0;
Shouldn't this be an atomic type?

https://codereview.chromium.org/643733002/diff/910001/content/browser/rendere...
File content/browser/renderer_host/routing_id_issuer.h (right):

https://codereview.chromium.org/643733002/diff/910001/content/browser/rendere...
content/browser/renderer_host/routing_id_issuer.h:31: static void
StartDisablingIDMangling();
nit: Those will be more readable if they are "Enable/Disable" instead of
"Start/StopDisabling".

https://codereview.chromium.org/643733002/diff/910001/content/public/test/rou...
File content/public/test/routing_id_mangling_disabler.h (right):

https://codereview.chromium.org/643733002/diff/910001/content/public/test/rou...
content/public/test/routing_id_mangling_disabler.h:11: // one. This class
temporarily realizess such an assumption.
nit: s/realizess/satisfies/?

[Hajime Morrita, 2014-10-13 22:23:47]

Thanks for the review!

> Couple of notes:
> * The stack traces that nick@ looked at had the same RenderProcessHost at the
> PostTask stack frame and the AddRoute.
> * The routing id in one of the traces I looked was 3, suggesting the first
> iframe added on a page in a brand new process.
>
> 
> Also, there is one usage of AddRoute in embedded_worker_devtools_agent_host.cc
> which wasn't immediately clear if it is correct and needs some auditing.
>

I'm not sure.
I hope the crash dump made by this change reveals which AddRoute() call was
wrong.
I'll turn the DCHECK() to CHECK() next. It'd be easy to revert than having
CHECK() in this.


> 
>
https://codereview.chromium.org/643733002/diff/910001/content/browser/rendere...
> File content/browser/renderer_host/render_widget_helper.h (right):
> 
>
https://codereview.chromium.org/643733002/diff/910001/content/browser/rendere...
> content/browser/renderer_host/render_widget_helper.h:84: // Probablistically
> verify if he ID is issued by this helper.
> nit: s/if he/if the/
> 
>
https://codereview.chromium.org/643733002/diff/910001/content/browser/rendere...
> content/browser/renderer_host/render_widget_helper.h:86: int
> IsRoutingIDProbablyValid(int routing_id) const;
> Why return int, when the expected output value is boolean?
> 
>
https://codereview.chromium.org/643733002/diff/910001/content/browser/rendere...
> File content/browser/renderer_host/routing_id_issuer.cc (right):
> 
>
https://codereview.chromium.org/643733002/diff/910001/content/browser/rendere...
> content/browser/renderer_host/routing_id_issuer.cc:11: const int kManglerBit =
> 3;
> nit: I'll name the *Bit variables as *Bits, as it makes reading it a bit
easier.
> 
>
https://codereview.chromium.org/643733002/diff/910001/content/browser/rendere...
> content/browser/renderer_host/routing_id_issuer.cc:18: int g_manglerSequence =
> 0;
> Shouldn't this be an atomic type?
> 
>
https://codereview.chromium.org/643733002/diff/910001/content/browser/rendere...
> File content/browser/renderer_host/routing_id_issuer.h (right):
> 
>
https://codereview.chromium.org/643733002/diff/910001/content/browser/rendere...
> content/browser/renderer_host/routing_id_issuer.h:31: static void
> StartDisablingIDMangling();
> nit: Those will be more readable if they are "Enable/Disable" instead of
> "Start/StopDisabling".
> 
>
https://codereview.chromium.org/643733002/diff/910001/content/public/test/rou...
> File content/public/test/routing_id_mangling_disabler.h (right):
> 
>
https://codereview.chromium.org/643733002/diff/910001/content/public/test/rou...
> content/public/test/routing_id_mangling_disabler.h:11: // one. This class
> temporarily realizess such an assumption.
> nit: s/realizess/satisfies/?

[Hajime Morrita, 2014-10-13 22:23:54]

https://codereview.chromium.org/643733002/diff/910001/content/browser/rendere...
File content/browser/renderer_host/render_widget_helper.h (right):

https://codereview.chromium.org/643733002/diff/910001/content/browser/rendere...
content/browser/renderer_host/render_widget_helper.h:84: // Probablistically
verify if he ID is issued by this helper.
On 2014/10/13 21:04:00, nasko wrote:
> nit: s/if he/if the/

Done.

https://codereview.chromium.org/643733002/diff/910001/content/browser/rendere...
content/browser/renderer_host/render_widget_helper.h:86: int
IsRoutingIDProbablyValid(int routing_id) const;
On 2014/10/13 21:04:00, nasko wrote:
> Why return int, when the expected output value is boolean?
Oops. should've returned a bool.

https://codereview.chromium.org/643733002/diff/910001/content/browser/rendere...
File content/browser/renderer_host/routing_id_issuer.cc (right):

https://codereview.chromium.org/643733002/diff/910001/content/browser/rendere...
content/browser/renderer_host/routing_id_issuer.cc:11: const int kManglerBit =
3;
On 2014/10/13 21:04:01, nasko wrote:
> nit: I'll name the *Bit variables as *Bits, as it makes reading it a bit
easier.

Done.

https://codereview.chromium.org/643733002/diff/910001/content/browser/rendere...
content/browser/renderer_host/routing_id_issuer.cc:18: int g_manglerSequence =
0;
On 2014/10/13 21:04:01, nasko wrote:
> Shouldn't this be an atomic type?
I thought this is OK as it is called only from UI thread.
Let me use the atomic type just in case though.

https://codereview.chromium.org/643733002/diff/910001/content/browser/rendere...
File content/browser/renderer_host/routing_id_issuer.h (right):

https://codereview.chromium.org/643733002/diff/910001/content/browser/rendere...
content/browser/renderer_host/routing_id_issuer.h:31: static void
StartDisablingIDMangling();
On 2014/10/13 21:04:01, nasko wrote:
> nit: Those will be more readable if they are "Enable/Disable" instead of
> "Start/StopDisabling".

Done.

https://codereview.chromium.org/643733002/diff/910001/content/public/test/rou...
File content/public/test/routing_id_mangling_disabler.h (right):

https://codereview.chromium.org/643733002/diff/910001/content/public/test/rou...
content/public/test/routing_id_mangling_disabler.h:11: // one. This class
temporarily realizess such an assumption.
On 2014/10/13 21:04:01, nasko wrote:
> nit: s/realizess/satisfies/?

Done.

[nasko, 2014-10-13 22:40:02]

LGTM with a nit.

https://codereview.chromium.org/643733002/diff/1240001/content/browser/render...
File content/browser/renderer_host/routing_id_issuer.cc (right):

https://codereview.chromium.org/643733002/diff/1240001/content/browser/render...
content/browser/renderer_host/routing_id_issuer.cc:18:
base::StaticAtomicSequenceNumber g_manglerSequence;
nit: let's make this one static, as it isn't used outside of this file.

[ncarter (slow), 2014-10-13 22:51:33]

Overall I am okay with adding some kind of type fingerprinting to our route_ids,
given the mystery of the underlying bug.

However I would hope it would be something that doesn't have to live forever in
the codebase.

It also would be nice if, generally, there were some way for people looking at
crashes to tell what "kind" of route_id they were looking at. The scheme
proposed here doesn't have that property, unfortunately: we can use it in CHECKs
when we anticipate a problem, but not in investigation where we see a crash and
suspect a route_id mixup. I propose a technique that might get us part of the
way there, but it's pretty fuzzy and incomplete.

https://codereview.chromium.org/643733002/diff/1020001/content/browser/render...
File content/browser/renderer_host/routing_id_issuer.cc (right):

https://codereview.chromium.org/643733002/diff/1020001/content/browser/render...
content/browser/renderer_host/routing_id_issuer.cc:18: int g_manglerSequence =
0;
Agree with nasko; this should probably be a StaticAtomicSequenceNumber

https://codereview.chromium.org/643733002/diff/1020001/content/browser/render...
content/browser/renderer_host/routing_id_issuer.cc:23: g_manglerSequence =
g_manglerSequence % kManglerWrap;
You might want to consider skipping mangler ID's of 0.

One class of bug we're trying to defend against is random small numbers (or
routing ID's allocated by different kinds of process hosts) being used as id's
here.

https://codereview.chromium.org/643733002/diff/1020001/content/browser/render...
content/browser/renderer_host/routing_id_issuer.cc:47: return (mangler_ <<
kIDBit) | ((next_.GetNext() + 1) & kIDMask);
I had an idea for a sort of different algorithm here, but one which has some
nice properties and some other properties that are not quite as nice as what
you've implemented. It's probably overkill, but let me know what you think:

== 

The idea would be that rather than rotating through a series of
g_manglerSequence values for the top 3 bits, we could instead use hashing to
eliminate some percentage of the possible values.

One seed value would be known at compile time, e.g., a static string like
"RenderProcessHost" -- call this value the flavor_seed. The other could be an
instance-specific value, probably the process_id.

The body of IssueNext would look like:
  while(1) {
    int route_id = next_.GetNext() + 1;
    int flavorhashinput[2] = {route_id, hash_of_flavor_seed_};
    if (base::Hash(flavorhashinput) % 2 == 0)
      continue;
    int instancehashinput[2] = {route_id, process_id_};
    if (base::Hash(instancehashinput) % 2 == 0)
      continue;
    return route_id;
  }

==

The first benefit: when we have a route_id, we can ask (statically), is this
likely a "RenderProcessHost" route id by computing the first hash. And if we
have a route_id and the process_id, then we can compute (statically) the second
value. I think the static nature of this would make for nice asserts, since
sometimes we wind up with route_id's far away from any pointer to a
RoutingIDIssuer.

Note that the use of process_id_ is optional -- that's appropriate if we're
worried about bugs where route_id's wind up paired with the wrong process_id; in
the case of the current bug, it seems that it's possible. If we don't use
process_id, then I think this scheme becomes even more test-friendly, since the
routing_id sequences would become very predictable.

We could conceivably go further, and pick (by brute force) specific flavor_seed_
values that have a low rate of overlap when hashed with small route_id values.

https://codereview.chromium.org/643733002/diff/1020001/content/browser/render...
content/browser/renderer_host/routing_id_issuer.cc:51: return mangler_ ==
((issued_id >> kIDBit) & kManglerMask);
can't issued_id be a negative value? If so then this right shift operation isn't
defined?

[Hajime Morrita, 2014-10-13 23:39:18]

https://codereview.chromium.org/643733002/diff/1020001/content/browser/render...
File content/browser/renderer_host/routing_id_issuer.cc (right):

https://codereview.chromium.org/643733002/diff/1020001/content/browser/render...
content/browser/renderer_host/routing_id_issuer.cc:18: int g_manglerSequence =
0;
On 2014/10/13 22:51:33, ncarter wrote:
> Agree with nasko; this should probably be a StaticAtomicSequenceNumber

Done.

https://codereview.chromium.org/643733002/diff/1020001/content/browser/render...
content/browser/renderer_host/routing_id_issuer.cc:23: g_manglerSequence =
g_manglerSequence % kManglerWrap;
On 2014/10/13 22:51:33, ncarter wrote:
> You might want to consider skipping mangler ID's of 0.
> 
> One class of bug we're trying to defend against is random small numbers (or
> routing ID's allocated by different kinds of process hosts) being used as id's
> here.
Makes sense. Changed to always return non-zero mangler.

https://codereview.chromium.org/643733002/diff/1020001/content/browser/render...
content/browser/renderer_host/routing_id_issuer.cc:47: return (mangler_ <<
kIDBit) | ((next_.GetNext() + 1) & kIDMask);
On 2014/10/13 22:51:33, ncarter wrote:
> I had an idea for a sort of different algorithm here, but one which has some
> nice properties and some other properties that are not quite as nice as what
> you've implemented. It's probably overkill, but let me know what you think:
> 
> == 
> 
> The idea would be that rather than rotating through a series of
> g_manglerSequence values for the top 3 bits, we could instead use hashing to
> eliminate some percentage of the possible values.
> 
> One seed value would be known at compile time, e.g., a static string like
> "RenderProcessHost" -- call this value the flavor_seed. The other could be an
> instance-specific value, probably the process_id.
> 
> The body of IssueNext would look like:
>   while(1) {
>     int route_id = next_.GetNext() + 1;
>     int flavorhashinput[2] = {route_id, hash_of_flavor_seed_};
>     if (base::Hash(flavorhashinput) % 2 == 0)
>       continue;
>     int instancehashinput[2] = {route_id, process_id_};
>     if (base::Hash(instancehashinput) % 2 == 0)
>       continue;
>     return route_id;
>   }
> 
> ==
> 
> The first benefit: when we have a route_id, we can ask (statically), is this
> likely a "RenderProcessHost" route id by computing the first hash. And if we
> have a route_id and the process_id, then we can compute (statically) the
second
> value. I think the static nature of this would make for nice asserts, since
> sometimes we wind up with route_id's far away from any pointer to a
> RoutingIDIssuer.
> 
> Note that the use of process_id_ is optional -- that's appropriate if we're
> worried about bugs where route_id's wind up paired with the wrong process_id;
in
> the case of the current bug, it seems that it's possible. If we don't use
> process_id, then I think this scheme becomes even more test-friendly, since
the
> routing_id sequences would become very predictable.
> 
> We could conceivably go further, and pick (by brute force) specific
flavor_seed_
> values that have a low rate of overlap when hashed with small route_id values.

Thanks for the suggestion! I'd rather avoid using process id as we don't have
one when
RenderProcessHostImpl is created and set the value afterword can possibly
introduce
strange race conditions.

Having the flavor seed sounds promising. Probably we could use something like
FROM_HERE?

Let me land this land this naive version for now.
I don't have good idea how to collect these detailed metrics from wild.
Probably we need some preparation to make it available.
It'd better to add such kind of infrastructure as well if we add more
sophisticated metrics.

https://codereview.chromium.org/643733002/diff/1020001/content/browser/render...
content/browser/renderer_host/routing_id_issuer.cc:51: return mangler_ ==
((issued_id >> kIDBit) & kManglerMask);
On 2014/10/13 22:51:33, ncarter wrote:
> can't issued_id be a negative value? If so then this right shift operation
isn't
> defined?

Oops. Fixing.

https://codereview.chromium.org/643733002/diff/1240001/content/browser/render...
File content/browser/renderer_host/routing_id_issuer.cc (right):

https://codereview.chromium.org/643733002/diff/1240001/content/browser/render...
content/browser/renderer_host/routing_id_issuer.cc:18:
base::StaticAtomicSequenceNumber g_manglerSequence;
On 2014/10/13 22:40:02, nasko wrote:
> nit: let's make this one static, as it isn't used outside of this file.

Done.

[Hajime Morrita, 2014-10-13 23:43:47]

The CQ bit was checked by morrita@chromium.org

[commit-bot: I haz the power, 2014-10-13 23:44:19]

CQ is trying da patch. Follow status at
 https://chromium-cq-status.appspot.com/patch-status/643733002/1590001

[Hajime Morrita, 2014-10-13 23:44:30]

Updated the CL. Nick: PTAL?
Setting the commit bit to reserve cq.

[commit-bot: I haz the power, 2014-10-13 23:52:14]

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

[commit-bot: I haz the power, 2014-10-13 23:52:15]

Try jobs failed on following builders:
  chromium_presubmit on tryserver.chromium.linux
(http://build.chromium.org/p/tryserver.chromium.linux/builders/chromium_presub...)

[Hajime Morrita, 2014-10-14 01:39:25]

The CQ bit was checked by morrita@chromium.org

[commit-bot: I haz the power, 2014-10-14 01:40:50]

CQ is trying da patch. Follow status at
 https://chromium-cq-status.appspot.com/patch-status/643733002/1590001

[commit-bot: I haz the power, 2014-10-14 03:49:41]

Committed patchset #11 (id:1590001)

[commit-bot: I haz the power, 2014-10-14 03:50:33]

Patchset 11 (id:??) landed as
https://crrev.com/d3e91b36c3c29aee92159db9d5cc331cd3f97241
Cr-Commit-Position: refs/heads/master@{#299423}