[Syzygy Instrumenter] Add FillerTransform.

[Syzygy Instrumenter] Add FillerTransform.

The FillerTransform adds NOP to specified functions at various locations.

R=chrisha@chromium.org

Committed: https://github.com/google/syzygy/commit/4b2d09f05c8ea5bfcb7106c777df2316d6b5d3e8

[huangs, 2015-06-04 21:59:16]

huangs@chromium.org changed reviewers:
+ chrisha@chromium.org, etienneb@chromium.org

[huangs, 2015-06-04 21:59:17]

PTAL. I also have the instrumenter, which is excluded from this CL.

[chrisha, 2015-06-04 22:31:56]

First comments... haven't gotten to the implementation or the tests.

https://codereview.chromium.org/1169603003/diff/1/syzygy/instrument/transform...
File syzygy/instrument/transforms/filler_transform.h (right):

https://codereview.chromium.org/1169603003/diff/1/syzygy/instrument/transform...
syzygy/instrument/transforms/filler_transform.h:16: // list of functions by
injecting benign fillers at various places.
Maybe specify that the benign fillers are nops?

https://codereview.chromium.org/1169603003/diff/1/syzygy/instrument/transform...
syzygy/instrument/transforms/filler_transform.h:56: NOP11
Do you really need this enum? Can't we just have a kMaximumNopSize, and map
instruction index to nop-size as a size_t?

https://codereview.chromium.org/1169603003/diff/1/syzygy/instrument/transform...
syzygy/instrument/transforms/filler_transform.h:60: // specify desired 0-based
code offsets *after* injection. The values specify
A code offset generally refers to the actual bytes, and offsets are signed
quantities for us. I think you mean to refer to instruction indices?

https://codereview.chromium.org/1169603003/diff/1/syzygy/instrument/transform...
syzygy/instrument/transforms/filler_transform.h:71: // Returns the number of
NOPs injected.
Is the return value useful?

Maybe just a true false for separating success from failure? (failure being an
invalid spec for the length of the instruction, I guess.)

Does this need to be a helper class, or could it simply be a static function of
the transform that takes a NopSpec and a list of Instructions? (Avoids the copy
in the constructor.)

https://codereview.chromium.org/1169603003/diff/1/syzygy/instrument/transform...
syzygy/instrument/transforms/filler_transform.h:80: // Applies filler transform
to a subgraph.
That describes the TransformBasicBlockSubGraph function, not the transform.
Please document the transform itself.

https://codereview.chromium.org/1169603003/diff/1/syzygy/instrument/transform...
syzygy/instrument/transforms/filler_transform.h:88: typedef BlockGraph::Block
Block;
This typedef to the end of the list (block_graph sorts before BlockGraph)

https://codereview.chromium.org/1169603003/diff/1/syzygy/instrument/transform...
syzygy/instrument/transforms/filler_transform.h:89: typedef
block_graph::BasicBlockSubGraph BasicBlockSubGraph;
And put this one in alphabetical order too, please.

https://codereview.chromium.org/1169603003/diff/1/syzygy/instrument/transform...
syzygy/instrument/transforms/filler_transform.h:97: 
Please endow this transform with a debug_friendly member, and a
set_debug_friendly mutator. This is a common pattern of ours for transforms that
inject new instructions.

When debug_friendly_ is true, we make the injected instructions clone the source
range of the instruction they are logically 'extending'. (See asan_transform for
examples.) This ensures that if you break on one of these transforms, you'll see
proper line attribution for it.

https://codereview.chromium.org/1169603003/diff/1/syzygy/instrument/transform...
syzygy/instrument/transforms/filler_transform.h:101: // Applies the filler
transform. Specifically, visits every basic code graph
basic code block?

https://codereview.chromium.org/1169603003/diff/1/syzygy/instrument/transform...
syzygy/instrument/transforms/filler_transform.h:103: bool
TransformBasicBlockSubGraph(
Why is this function protected?

https://codereview.chromium.org/1169603003/diff/1/syzygy/instrument/transform...
syzygy/instrument/transforms/filler_transform.h:113: // Takes a list of target
function names, and applies filler transform only to
Decorated function names? Undecorated? Please be very specific.

https://codereview.chromium.org/1169603003/diff/1/syzygy/instrument/transform...
syzygy/instrument/transforms/filler_transform.h:114: // the specified functions.
Also contains counters.
Counters of what? For what purpose?

If they're implementation details, no need to mention them.

https://codereview.chromium.org/1169603003/diff/1/syzygy/instrument/transform...
syzygy/instrument/transforms/filler_transform.h:122: explicit
FillerTransform(const std::vector<std::string>& target_list);
We want this transform to be randomized, but repeatable. It should likely take a
random seed as input somewhere?

https://codereview.chromium.org/1169603003/diff/1/syzygy/instrument/transform...
syzygy/instrument/transforms/filler_transform.h:138: void CheckAllTargetFound()
const;
AllTargets*

Errors are unrecoverable, typically. Should these be warnings? (ie: good to know
that a symbol was missed, but not the end of the world)

https://codereview.chromium.org/1169603003/diff/1/syzygy/instrument/transform...
syzygy/instrument/transforms/filler_transform.h:162: // Counters.
I imagine these are used by CheckAllTargetsFound? Maybe document that fact.

https://codereview.chromium.org/1169603003/diff/1/syzygy/instrument/transform...
syzygy/instrument/transforms/filler_transform.h:165: size_t num_code_block_;
num_code_basic_blocks_?

https://codereview.chromium.org/1169603003/diff/1/syzygy/instrument/transform...
syzygy/instrument/transforms/filler_transform.h:165: size_t num_code_block_;
num_blocks_?

https://codereview.chromium.org/1169603003/diff/1/syzygy/instrument/transform...
syzygy/instrument/transforms/filler_transform.h:166: size_t num_target_updated_;
num_targets_updated_?

[huangs, 2015-06-05 15:13:25]

Updated, PTAL.

https://codereview.chromium.org/1169603003/diff/1/syzygy/instrument/transform...
File syzygy/instrument/transforms/filler_transform.h (right):

https://codereview.chromium.org/1169603003/diff/1/syzygy/instrument/transform...
syzygy/instrument/transforms/filler_transform.h:16: // list of functions by
injecting benign fillers at various places.
On 2015/06/04 22:31:55, chrisha (OOO until June 10) wrote:
> Maybe specify that the benign fillers are nops?

Done.

https://codereview.chromium.org/1169603003/diff/1/syzygy/instrument/transform...
syzygy/instrument/transforms/filler_transform.h:56: NOP11
I wanted to automatically enforce correctness, and 11 does not seem that big.
This way there's no need to worry about correctness w.r.t. sizes, which would
complicates code flow, would require extra test, and would require worrying
about the case like {1: 2, 100000: 1000000}, i.e., allow bad specs slip through
by because bad size is never encountered (alternative is to have dedicated
validation, but that's unwieldy).

https://codereview.chromium.org/1169603003/diff/1/syzygy/instrument/transform...
syzygy/instrument/transforms/filler_transform.h:60: // specify desired 0-based
code offsets *after* injection. The values specify
Done; renamed throughout.

https://codereview.chromium.org/1169603003/diff/1/syzygy/instrument/transform...
syzygy/instrument/transforms/filler_transform.h:71: // Returns the number of
NOPs injected.
On 2015/06/04 22:31:54, chrisha (OOO until June 10) wrote:
> Is the return value useful?

I used it for testing, but its not used in actual code so removing it.
 
> Maybe just a true false for separating success from failure? (failure being an
> invalid spec for the length of the instruction, I guess.)

Making this void, since the failure cases don't appear (see NopSize comment
above).

> Does this need to be a helper class, or could it simply be a static function
of
> the transform that takes a NopSpec and a list of Instructions? (Avoids the
copy
> in the constructor.)

Moved into FillerBasicBlockTransform.

https://codereview.chromium.org/1169603003/diff/1/syzygy/instrument/transform...
syzygy/instrument/transforms/filler_transform.h:80: // Applies filler transform
to a subgraph.
On 2015/06/04 22:31:55, chrisha (OOO until June 10) wrote:
> That describes the TransformBasicBlockSubGraph function, not the transform.
> Please document the transform itself.

Done.

https://codereview.chromium.org/1169603003/diff/1/syzygy/instrument/transform...
syzygy/instrument/transforms/filler_transform.h:88: typedef BlockGraph::Block
Block;
On 2015/06/04 22:31:55, chrisha (OOO until June 10) wrote:
> This typedef to the end of the list (block_graph sorts before BlockGraph)

Done.

https://codereview.chromium.org/1169603003/diff/1/syzygy/instrument/transform...
syzygy/instrument/transforms/filler_transform.h:89: typedef
block_graph::BasicBlockSubGraph BasicBlockSubGraph;
On 2015/06/04 22:31:54, chrisha (OOO until June 10) wrote:
> And put this one in alphabetical order too, please.

Done.

https://codereview.chromium.org/1169603003/diff/1/syzygy/instrument/transform...
syzygy/instrument/transforms/filler_transform.h:97: 
Done. Had to rewrite InjectNop() so consecutive injected NOPs share a common
BasicBlockAssember(). Please let me know if this is not a worthwhile
optimization, then I'll switch back to the old way (which seems nicer).

https://codereview.chromium.org/1169603003/diff/1/syzygy/instrument/transform...
syzygy/instrument/transforms/filler_transform.h:101: // Applies the filler
transform. Specifically, visits every basic code graph
On 2015/06/04 22:31:55, chrisha (OOO until June 10) wrote:
> basic code block?

Done.

https://codereview.chromium.org/1169603003/diff/1/syzygy/instrument/transform...
syzygy/instrument/transforms/filler_transform.h:103: bool
TransformBasicBlockSubGraph(
Moved to public:.

https://codereview.chromium.org/1169603003/diff/1/syzygy/instrument/transform...
syzygy/instrument/transforms/filler_transform.h:113: // Takes a list of target
function names, and applies filler transform only to
On 2015/06/04 22:31:55, chrisha (OOO until June 10) wrote:
> Decorated function names? Undecorated? Please be very specific.

Done.

https://codereview.chromium.org/1169603003/diff/1/syzygy/instrument/transform...
syzygy/instrument/transforms/filler_transform.h:114: // the specified functions.
Also contains counters.
Counters to display messages (displays message if there's a missing target, so
if there's a mistake in the input data file we'd know). Removed comment.

https://codereview.chromium.org/1169603003/diff/1/syzygy/instrument/transform...
syzygy/instrument/transforms/filler_transform.h:122: explicit
FillerTransform(const std::vector<std::string>& target_list);
Can we do this in a separate CL? This complicates testing as well.

https://codereview.chromium.org/1169603003/diff/1/syzygy/instrument/transform...
syzygy/instrument/transforms/filler_transform.h:138: void CheckAllTargetFound()
const;
On 2015/06/04 22:31:55, chrisha (OOO until June 10) wrote:
> AllTargets*
> 
> Errors are unrecoverable, typically. Should these be warnings? (ie: good to
know
> that a symbol was missed, but not the end of the world)

Done.

https://codereview.chromium.org/1169603003/diff/1/syzygy/instrument/transform...
syzygy/instrument/transforms/filler_transform.h:162: // Counters.
On 2015/06/04 22:31:54, chrisha (OOO until June 10) wrote:
> I imagine these are used by CheckAllTargetsFound? Maybe document that fact.

Done.

https://codereview.chromium.org/1169603003/diff/1/syzygy/instrument/transform...
syzygy/instrument/transforms/filler_transform.h:165: size_t num_code_block_;
On 2015/06/04 22:31:55, chrisha (OOO until June 10) wrote:
> num_blocks_?

Done.

https://codereview.chromium.org/1169603003/diff/1/syzygy/instrument/transform...
syzygy/instrument/transforms/filler_transform.h:165: size_t num_code_block_;
On 2015/06/04 22:31:55, chrisha (OOO until June 10) wrote:
> num_code_basic_blocks_?

Done.

https://codereview.chromium.org/1169603003/diff/1/syzygy/instrument/transform...
syzygy/instrument/transforms/filler_transform.h:166: size_t num_target_updated_;
On 2015/06/04 22:31:54, chrisha (OOO until June 10) wrote:
> num_targets_updated_?

Done.

[huangs, 2015-06-05 15:28:33]

Also note that I'm not testing the effect of |debug_friendly|. Will add a test.

[chrisha, 2015-06-10 18:07:27]

https://codereview.chromium.org/1169603003/diff/40001/syzygy/instrument/trans...
File syzygy/instrument/transforms/filler_transform.cc (right):

https://codereview.chromium.org/1169603003/diff/40001/syzygy/instrument/trans...
syzygy/instrument/transforms/filler_transform.cc:48: auto source_range =
inst_it->source_range();
What is this needed for?

https://codereview.chromium.org/1169603003/diff/40001/syzygy/instrument/trans...
syzygy/instrument/transforms/filler_transform.cc:71: NopSpec nop_spec = {{1,
NOP1}};
Is this going to be sufficient? Do we maybe want to randomly generate a NopSpec
based on some input conditions? (ie: maximum number of consecutive original
instructions)

https://codereview.chromium.org/1169603003/diff/40001/syzygy/instrument/trans...
syzygy/instrument/transforms/filler_transform.cc:74: debug_friendly_ ? "true" :
"false");
Debugging code?

https://codereview.chromium.org/1169603003/diff/40001/syzygy/instrument/trans...
File syzygy/instrument/transforms/filler_transform.h (right):

https://codereview.chromium.org/1169603003/diff/40001/syzygy/instrument/trans...
syzygy/instrument/transforms/filler_transform.h:88: // instruction. Returns the
number of NOPs injected.
Return statement no longer applicable?

https://codereview.chromium.org/1169603003/diff/40001/syzygy/instrument/trans...
syzygy/instrument/transforms/filler_transform.h:141: void CheckAllTargetFound()
const;
CheckAllTargetsFound
..............^.....

[huangs, 2015-06-11 14:54:15]

PTAL.

https://chromiumcodereview.appspot.com/1169603003/diff/40001/syzygy/instrumen...
File syzygy/instrument/transforms/filler_transform.cc (right):

https://chromiumcodereview.appspot.com/1169603003/diff/40001/syzygy/instrumen...
syzygy/instrument/transforms/filler_transform.cc:48: auto source_range =
inst_it->source_range();
Removed.

https://chromiumcodereview.appspot.com/1169603003/diff/40001/syzygy/instrumen...
syzygy/instrument/transforms/filler_transform.cc:71: NopSpec nop_spec = {{1,
NOP1}};
We want to start small; will do randomness later.  Also, this is injected to
every basic code block.

https://chromiumcodereview.appspot.com/1169603003/diff/40001/syzygy/instrumen...
syzygy/instrument/transforms/filler_transform.cc:74: debug_friendly_ ? "true" :
"false");
Removed.

https://chromiumcodereview.appspot.com/1169603003/diff/40001/syzygy/instrumen...
File syzygy/instrument/transforms/filler_transform.h (right):

https://chromiumcodereview.appspot.com/1169603003/diff/40001/syzygy/instrumen...
syzygy/instrument/transforms/filler_transform.h:88: // instruction. Returns the
number of NOPs injected.
On 2015/06/10 18:07:27, chrisha wrote:
> Return statement no longer applicable?

Done.

https://chromiumcodereview.appspot.com/1169603003/diff/40001/syzygy/instrumen...
syzygy/instrument/transforms/filler_transform.h:141: void CheckAllTargetFound()
const;
On 2015/06/10 18:07:27, chrisha wrote:
> CheckAllTargetsFound
> ..............^.....

Done.

[huangs, 2015-06-12 14:18:34]

Ping chrisha@. Thanks!

[chrisha, 2015-06-12 15:07:47]

Thorough tests!

lgtm

[huangs, 2015-06-12 15:49:05]

Thanks. Submitting soon!

[huangs, 2015-06-12 17:08:19]

Committed patchset #5 (id:80001) manually as
4b2d09f05c8ea5bfcb7106c777df2316d6b5d3e8 (presubmit successful).