[Refinery] Introduce TypePropagatorAnalyzer - pointer types.

[Refinery] Introduce TypePropagatorAnalyzer - pointer types.

The TypePropagatorAnalyzer processes the typed block layer looking for
pointer types to generate new typed block information.

BUG=
R=siggi@chromium.org

Committed: https://github.com/google/syzygy/commit/70e0f5fcdaab6aef1d56cac83e65b5c42d0754dc

[manzagop (departed), 2015-11-26 21:04:42]

Description was changed from

==========
[Refinery] WIP - Introduce TypePropagatorAnalyzer.

The TypePropagatorAnalyzer processes the typed block layer looking for
pointer types to generate new typed block information.

Details:
- switch TypedBlock to use TypeId instead of type names

BUG=
==========

to

==========
[Refinery] Introduce TypePropagatorAnalyzer - pointer types.

The TypePropagatorAnalyzer processes the typed block layer looking for
pointer types to generate new typed block information.

BUG=
==========

[manzagop (departed), 2015-11-26 21:05:43]

manzagop@chromium.org changed reviewers:
+ siggi@chromium.org

[manzagop (departed), 2015-11-26 21:05:43]

Please have a look! This only looks at pointer typed blocks.

[Sigurður Ásgeirsson, 2015-11-26 21:45:12]

First batch of comments - more tomorrow. This is very exciting!

https://codereview.chromium.org/1475083002/diff/60001/syzygy/refinery/analyze...
File syzygy/refinery/analyzers/type_propagator_analyzer.cc (right):

https://codereview.chromium.org/1475083002/diff/60001/syzygy/refinery/analyze...
syzygy/refinery/analyzers/type_propagator_analyzer.cc:49: return ANALYSIS_ERROR;
Is this an error, or just unexpected?

https://codereview.chromium.org/1475083002/diff/60001/syzygy/refinery/analyze...
syzygy/refinery/analyzers/type_propagator_analyzer.cc:76:
process_queue.emplace(process_state, type, rec->range().start());
nit: I don't think we're allowed emplace just yet?

https://codereview.chromium.org/1475083002/diff/60001/syzygy/refinery/analyze...
syzygy/refinery/analyzers/type_propagator_analyzer.cc:86: return
ANALYSIS_COMPLETE;
Hmmm - I think you want to iterate here until stable?

https://codereview.chromium.org/1475083002/diff/60001/syzygy/refinery/analyze...
syzygy/refinery/analyzers/type_propagator_analyzer.cc:120: // TODO(manzagop):
implement.
aha - this is where you'd recurse?

https://codereview.chromium.org/1475083002/diff/60001/syzygy/refinery/analyze...
File syzygy/refinery/analyzers/type_propagator_analyzer.h (right):

https://codereview.chromium.org/1475083002/diff/60001/syzygy/refinery/analyze...
syzygy/refinery/analyzers/type_propagator_analyzer.h:28: class
TypePropagatorAnalyzer : public Analyzer {
this is very exciting!

https://codereview.chromium.org/1475083002/diff/60001/syzygy/refinery/analyze...
File syzygy/refinery/analyzers/type_propagator_analyzer_unittest.cc (right):

https://codereview.chromium.org/1475083002/diff/60001/syzygy/refinery/analyze...
syzygy/refinery/analyzers/type_propagator_analyzer_unittest.cc:2: //
TODO(siggi): Go from here!

https://codereview.chromium.org/1475083002/diff/60001/syzygy/refinery/types/t...
File syzygy/refinery/types/type_repository.h (right):

https://codereview.chromium.org/1475083002/diff/60001/syzygy/refinery/types/t...
syzygy/refinery/types/type_repository.h:40: explicit TypeRepository(const
pe::PEFile::Signature& signature);
I think we want to abstract the module ID to something less Windowsy. Maybe we
can just use something like

using ModuleId = std::string;

and have a central service that casts from PE signature to string?

Also, I think it probably should be mandatory to provide the string. If it takes
a separate CL, then that's fine with a TODO here?

[Sigurður Ásgeirsson, 2015-11-27 14:45:31]

nice - here's the balance of my comments.

https://codereview.chromium.org/1475083002/diff/60001/syzygy/refinery/analyze...
File syzygy/refinery/analyzers/type_propagator_analyzer_unittest.cc (right):

https://codereview.chromium.org/1475083002/diff/60001/syzygy/refinery/analyze...
syzygy/refinery/analyzers/type_propagator_analyzer_unittest.cc:45: class
MockSymbolProvider : public SymbolProvider {
Yeah - this feels like broken infrastructure again :). Fine for now, but a type
repo factory would provide a much nicer test seam here.

https://codereview.chromium.org/1475083002/diff/60001/syzygy/refinery/analyze...
syzygy/refinery/analyzers/type_propagator_analyzer_unittest.cc:104:
memcpy(&buffer->at(0), &variable_ptr_, sizeof(variable_ptr_));
WriteInto makes this more concise, I think?

https://codereview.chromium.org/1475083002/diff/60001/syzygy/refinery/process...
File syzygy/refinery/process_state/refinery.proto (right):

https://codereview.chromium.org/1475083002/diff/60001/syzygy/refinery/process...
syzygy/refinery/process_state/refinery.proto:111: // A module identifier within
the module layer.
nit: this is an unsafe change to a protobuffer. Doesn't matter here, but should
be avoided in general.

[manzagop (departed), 2015-11-27 15:20:28]

Please have another look!

https://codereview.chromium.org/1475083002/diff/60001/syzygy/refinery/analyze...
File syzygy/refinery/analyzers/type_propagator_analyzer.cc (right):

https://codereview.chromium.org/1475083002/diff/60001/syzygy/refinery/analyze...
syzygy/refinery/analyzers/type_propagator_analyzer.cc:49: return ANALYSIS_ERROR;
On 2015/11/26 21:45:12, Sigurður Ásgeirsson wrote:
> Is this an error, or just unexpected?

I'm using this as a proxy for "StackFrameAnalyzer must have run". Although it's
possible it ran without creating the typed block layer, it's pretty unlikely. 

I clarified the comment.

https://codereview.chromium.org/1475083002/diff/60001/syzygy/refinery/analyze...
syzygy/refinery/analyzers/type_propagator_analyzer.cc:76:
process_queue.emplace(process_state, type, rec->range().start());
On 2015/11/26 21:45:12, Sigurður Ásgeirsson wrote:
> nit: I don't think we're allowed emplace just yet?

Haha. I'd actually checked and seen "Use where element construction within a
container is needed." Turns out this is just a description, and this content
appears in a "Don't use these" section.

Done.

https://codereview.chromium.org/1475083002/diff/60001/syzygy/refinery/analyze...
syzygy/refinery/analyzers/type_propagator_analyzer.cc:86: return
ANALYSIS_COMPLETE;
On 2015/11/26 21:45:12, Sigurður Ásgeirsson wrote:
> Hmmm - I think you want to iterate here until stable?

As you guessed, there's recursion in AnalyzeTypedData.

https://codereview.chromium.org/1475083002/diff/60001/syzygy/refinery/analyze...
syzygy/refinery/analyzers/type_propagator_analyzer.cc:120: // TODO(manzagop):
implement.
On 2015/11/26 21:45:12, Sigurður Ásgeirsson wrote:
> aha - this is where you'd recurse?

That is correct.

https://codereview.chromium.org/1475083002/diff/60001/syzygy/refinery/analyze...
File syzygy/refinery/analyzers/type_propagator_analyzer.h (right):

https://codereview.chromium.org/1475083002/diff/60001/syzygy/refinery/analyze...
syzygy/refinery/analyzers/type_propagator_analyzer.h:28: class
TypePropagatorAnalyzer : public Analyzer {
On 2015/11/26 21:45:12, Sigurður Ásgeirsson wrote:
> this is very exciting!

TOTALLY!

https://codereview.chromium.org/1475083002/diff/60001/syzygy/refinery/analyze...
File syzygy/refinery/analyzers/type_propagator_analyzer_unittest.cc (right):

https://codereview.chromium.org/1475083002/diff/60001/syzygy/refinery/analyze...
syzygy/refinery/analyzers/type_propagator_analyzer_unittest.cc:2: //
On 2015/11/26 21:45:12, Sigurður Ásgeirsson wrote:
> TODO(siggi): Go from here!

Acknowledged.

https://codereview.chromium.org/1475083002/diff/60001/syzygy/refinery/analyze...
syzygy/refinery/analyzers/type_propagator_analyzer_unittest.cc:45: class
MockSymbolProvider : public SymbolProvider {
On 2015/11/27 14:45:31, Sigurður Ásgeirsson wrote:
> Yeah - this feels like broken infrastructure again :). Fine for now, but a
type
> repo factory would provide a much nicer test seam here.

Acknowledged.

https://codereview.chromium.org/1475083002/diff/60001/syzygy/refinery/analyze...
syzygy/refinery/analyzers/type_propagator_analyzer_unittest.cc:104:
memcpy(&buffer->at(0), &variable_ptr_, sizeof(variable_ptr_));
On 2015/11/27 14:45:31, Sigurður Ásgeirsson wrote:
> WriteInto makes this more concise, I think?

Done.

https://codereview.chromium.org/1475083002/diff/60001/syzygy/refinery/process...
File syzygy/refinery/process_state/refinery.proto (right):

https://codereview.chromium.org/1475083002/diff/60001/syzygy/refinery/process...
syzygy/refinery/process_state/refinery.proto:111: // A module identifier within
the module layer.
On 2015/11/27 14:45:31, Sigurður Ásgeirsson wrote:
> nit: this is an unsafe change to a protobuffer. Doesn't matter here, but
should
> be avoided in general.

Yup, I'm aware this is a no-no when we'll start having stored data / live code.
Thanks for checking!

https://codereview.chromium.org/1475083002/diff/60001/syzygy/refinery/types/t...
File syzygy/refinery/types/type_repository.h (right):

https://codereview.chromium.org/1475083002/diff/60001/syzygy/refinery/types/t...
syzygy/refinery/types/type_repository.h:40: explicit TypeRepository(const
pe::PEFile::Signature& signature);
On 2015/11/26 21:45:12, Sigurður Ásgeirsson wrote:
> I think we want to abstract the module ID to something less Windowsy. Maybe we
> can just use something like
> 
> using ModuleId = std::string;

Yes, I was thinking we'd have a Signature interface that gets factory created
based on platform specific signatures, but thought it too heavy short term.
Added TODO.

> and have a central service that casts from PE signature to string?
> 
> Also, I think it probably should be mandatory to provide the string. If it
takes
> a separate CL, then that's fine with a TODO here?

I was hesitant with the notion of including a signature in a TypeRepo because
until now nothing about the class said there needs to be a 1:1 match between a
repo and a module. Agreed going halfway about it is actually worse. Will tackle
in a follow up cl, as this one is pretty large.

Added TODO.

[Sigurður Ásgeirsson, 2015-11-27 15:33:40]

nice - it's fine to address these comments with TODO if you prefer at this point
:).

https://codereview.chromium.org/1475083002/diff/60001/syzygy/refinery/analyze...
File syzygy/refinery/analyzers/type_propagator_analyzer.cc (right):

https://codereview.chromium.org/1475083002/diff/60001/syzygy/refinery/analyze...
syzygy/refinery/analyzers/type_propagator_analyzer.cc:86: return
ANALYSIS_COMPLETE;
On 2015/11/27 15:20:28, manzagop wrote:
> On 2015/11/26 21:45:12, Sigurður Ásgeirsson wrote:
> > Hmmm - I think you want to iterate here until stable?
> 
> As you guessed, there's recursion in AnalyzeTypedData.

That's not quite the same thing. A single iteration through this Analyzer can
unwind only one level of e.g. a linked list, or a tree.
Generally each time a new typed data is discovered, this Analyzer may
potentially propagate types from that. 

As type recovery/discovery is not limited to the stack analyzer - nor this
analyzer - the best thing to do is probably to return the "please call again"
code until no more propagation can be done?
This also implies maintaining state someplace - a simple thing to do would be to
e.g. assign an ordinal to each record in our layers, maintain the max-seen
ordinal and then iterate over only new records?

https://codereview.chromium.org/1475083002/diff/80001/syzygy/refinery/analyze...
File syzygy/refinery/analyzers/type_propagator_analyzer.cc (right):

https://codereview.chromium.org/1475083002/diff/80001/syzygy/refinery/analyze...
syzygy/refinery/analyzers/type_propagator_analyzer.cc:85: return ANALYSIS_ERROR;
I don't think we want to fail analysis on this condition, as Dereference can
fail for a variety of reasons?

[manzagop (departed), 2015-11-27 18:17:03]

Please have another look. Punted most of it to TODOs.

https://codereview.chromium.org/1475083002/diff/60001/syzygy/refinery/analyze...
File syzygy/refinery/analyzers/type_propagator_analyzer.cc (right):

https://codereview.chromium.org/1475083002/diff/60001/syzygy/refinery/analyze...
syzygy/refinery/analyzers/type_propagator_analyzer.cc:86: return
ANALYSIS_COMPLETE;
On 2015/11/27 15:33:40, Sigurður Ásgeirsson wrote:
> On 2015/11/27 15:20:28, manzagop wrote:
> > On 2015/11/26 21:45:12, Sigurður Ásgeirsson wrote:
> > > Hmmm - I think you want to iterate here until stable?
> > 
> > As you guessed, there's recursion in AnalyzeTypedData.
> 
> That's not quite the same thing. A single iteration through this Analyzer can
> unwind only one level of e.g. a linked list, or a tree.
> Generally each time a new typed data is discovered, this Analyzer may
> potentially propagate types from that. 

As discussed, there's currently recursion that goes beyond the first level, but
there's two issues with it:
- possibly large recursion depth
- cycles in the TypedData

Removing the recursion and adding a TODO for now.

> As type recovery/discovery is not limited to the stack analyzer - nor this
> analyzer - the best thing to do is probably to return the "please call again"
> code until no more propagation can be done?
> This also implies maintaining state someplace - a simple thing to do would be
to
> e.g. assign an ordinal to each record in our layers, maintain the max-seen
> ordinal and then iterate over only new records?

Good idea. Also adding a TODO for this mechanism.

https://codereview.chromium.org/1475083002/diff/80001/syzygy/refinery/analyze...
File syzygy/refinery/analyzers/type_propagator_analyzer.cc (right):

https://codereview.chromium.org/1475083002/diff/80001/syzygy/refinery/analyze...
syzygy/refinery/analyzers/type_propagator_analyzer.cc:85: return ANALYSIS_ERROR;
On 2015/11/27 15:33:40, Sigurður Ásgeirsson wrote:
> I don't think we want to fail analysis on this condition, as Dereference can
> fail for a variety of reasons?

I'm finding more and more that we need to better distinguish between failures
and negative results (something that is not acceptable from something that is,
eg not having the bytes). Also, it would be really nice to have some counter
mechanism to see stats about the different events.

I've changed the code to actually handle the return value from Dereference
(which I wasn't checking!) and treat a failed dereference as a success. Tell me
what you think.

[Sigurður Ásgeirsson, 2015-11-27 18:19:37]

lgtm - most exciting!

https://codereview.chromium.org/1475083002/diff/100001/syzygy/refinery/analyz...
File syzygy/refinery/analyzers/type_propagator_analyzer.cc (right):

https://codereview.chromium.org/1475083002/diff/100001/syzygy/refinery/analyz...
syzygy/refinery/analyzers/type_propagator_analyzer.cc:138: // TODO(manzagop):
have a better way to distinguish a failure (can't cast t
cast t?

[manzagop (departed), 2015-11-27 18:49:54]

Thanks! Committing.

https://codereview.chromium.org/1475083002/diff/100001/syzygy/refinery/analyz...
File syzygy/refinery/analyzers/type_propagator_analyzer.cc (right):

https://codereview.chromium.org/1475083002/diff/100001/syzygy/refinery/analyz...
syzygy/refinery/analyzers/type_propagator_analyzer.cc:138: // TODO(manzagop):
have a better way to distinguish a failure (can't cast t
On 2015/11/27 18:19:37, Sigurður Ásgeirsson wrote:
> cast t?

Done.

[manzagop (departed), 2015-11-27 18:56:45]

Description was changed from

==========
[Refinery] Introduce TypePropagatorAnalyzer - pointer types.

The TypePropagatorAnalyzer processes the typed block layer looking for
pointer types to generate new typed block information.

BUG=
==========

to

==========
[Refinery] Introduce TypePropagatorAnalyzer - pointer types.

The TypePropagatorAnalyzer processes the typed block layer looking for
pointer types to generate new typed block information.

BUG=
R=siggi@chromium.org

Committed:
https://github.com/google/syzygy/commit/70e0f5fcdaab6aef1d56cac83e65b5c42d0754dc
==========

[manzagop (departed), 2015-11-27 18:56:47]

Committed patchset #7 (id:120001) manually as
70e0f5fcdaab6aef1d56cac83e65b5c42d0754dc (presubmit successful).