[Syzygy Instrumenter] Add FillerTransform.

syzygy/instrument/transforms/filler_transform.h

Index: syzygy/instrument/transforms/filler_transform.h
diff --git a/syzygy/instrument/transforms/filler_transform.h b/syzygy/instrument/transforms/filler_transform.h
new file mode 100644
index 0000000000000000000000000000000000000000..d4a01da8def3e03c01e91634ac55922dec3b553e
--- /dev/null
+++ b/syzygy/instrument/transforms/filler_transform.h
@@ -0,0 +1,175 @@
+// Copyright 2015 Google Inc. All Rights Reserved.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//     http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+//
+// Declaration of the filler instrumentation transform. This instruments a given
+// list of functions by injecting benign fillers at various places.

[chrisha, 2015/06/04 22:31:55]

Maybe specify that the benign fillers are nops?

[huangs, 2015/06/05 15:13:24]

Done.

+
+#ifndef SYZYGY_INSTRUMENT_TRANSFORMS_FILLER_TRANSFORM_H_
+#define SYZYGY_INSTRUMENT_TRANSFORMS_FILLER_TRANSFORM_H_
+
+#include <map>
+#include <string>
+#include <vector>
+
+#include "base/macros.h"
+#include "base/files/file_path.h"
+#include "base/memory/scoped_ptr.h"
+#include "syzygy/block_graph/basic_block.h"
+#include "syzygy/block_graph/block_graph.h"
+#include "syzygy/block_graph/transforms/iterative_transform.h"
+#include "syzygy/block_graph/transforms/named_transform.h"
+
+using block_graph::TransformPolicyInterface;
+
+namespace instrument {
+namespace transforms {
+
+// A class to inject NOP into Instructions.
+class NopInjector {
+ public:
+  typedef block_graph::BasicBlock BasicBlock;
+
+  // NOP sizes that are represented by a single instruction. Multi-instruction
+  // NOPs are avoided to maintain consistent NOP code offsets after injection.
+  enum NopSizes {
+    NOP1 = 1,
+    NOP2,
+    NOP3,
+    NOP4,
+    NOP5,
+    NOP6,
+    NOP7,
+    NOP8,
+    NOP9,
+    NOP10,
+    NOP11

[chrisha, 2015/06/04 22:31:55]

Do you really need this enum? Can't we just have a kMaximumNopSize, and map
instruction index to nop-size as a size_t?

[huangs, 2015/06/05 15:13:23]

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).

+  };
+
+  // Specifications (code offsets and sizes) for NOP injection. The keys
+  // specify desired 0-based code offsets *after* injection. The values specify

[chrisha, 2015/06/04 22:31:55]

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?

[huangs, 2015/06/05 15:13:24]

Done; renamed throughout.

+  // NOP sizes. For example, {1: NOP3, 3: NOP2, 4: NOP5} specifies a
+  // transformation that takes instruction sequence "ABCDE" to "AXBYZCDE", where
+  //  "X" is NOP3, "Y" is NOP2, and "Z" is NOP5.
+  typedef const std::map<size_t, NopSizes> NopSpec;
+
+  explicit NopInjector(const NopSpec& nop_spec) : nop_spec_(nop_spec) { }
+  ~NopInjector() { }
+
+  // Injects NOP into @p instruction. The (post-injection) offsets and NOP sizes
+  // are given by nop_spec_. NOP is not injected past the last instruction.
+  // Returns the number of NOPs injected.

[chrisha, 2015/06/04 22:31:54]

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.)

[huangs, 2015/06/05 15:13:24]

I used it for testing, but its not used in actual code so removing it.
 
Making this void, since the failure cases don't appear (see NopSize comment
above).
Moved into FillerBasicBlockTransform.

+  size_t Inject(BasicBlock::Instructions* instructions) const;
+
+ private:
+  NopSpec nop_spec_;
+
+  DISALLOW_COPY_AND_ASSIGN(NopInjector);
+};
+
+// Applies filler transform to a subgraph.

[chrisha, 2015/06/04 22:31:55]

That describes the TransformBasicBlockSubGraph function, not the transform.
Please document the transform itself.

[huangs, 2015/06/05 15:13:24]

Done.

+class FillerBasicBlockTransform
+    : public block_graph::transforms::NamedBasicBlockSubGraphTransformImpl<
+          FillerBasicBlockTransform> {
+ public:
+  typedef block_graph::BasicBlock BasicBlock;
+  typedef block_graph::BasicCodeBlock BasicCodeBlock;
+  typedef block_graph::BlockGraph BlockGraph;
+  typedef BlockGraph::Block Block;

[chrisha, 2015/06/04 22:31:55]

This typedef to the end of the list (block_graph sorts before BlockGraph)

[huangs, 2015/06/05 15:13:24]

Done.

+  typedef block_graph::BasicBlockSubGraph BasicBlockSubGraph;

[chrisha, 2015/06/04 22:31:54]

And put this one in alphabetical order too, please.

[huangs, 2015/06/05 15:13:24]

Done.

+  typedef block_graph::TransformPolicyInterface TransformPolicyInterface;
+
+  FillerBasicBlockTransform() { }
+  virtual ~FillerBasicBlockTransform() { }
+
+  // For NamedBlockGraphTransformImpl.
+  static const char kTransformName[];
+

[chrisha, 2015/06/04 22:31:55]

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.

[huangs, 2015/06/05 15:13:24]

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).

+ protected:
+  // @name BasicBlockSubGraphTransformInterface implementation.
+  // @{
+  // Applies the filler transform. Specifically, visits every basic code graph

[chrisha, 2015/06/04 22:31:55]

basic code block?

[huangs, 2015/06/05 15:13:24]

Done.

+  // in @p basic_block_subgraph and injects NOP at various places.
+  bool TransformBasicBlockSubGraph(

[chrisha, 2015/06/04 22:31:54]

Why is this function protected?

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

Moved to public:.

+      const TransformPolicyInterface* policy,
+      BlockGraph* block_graph,
+      BasicBlockSubGraph* basic_block_subgraph) override;
+  // @}
+
+ private:
+  DISALLOW_COPY_AND_ASSIGN(FillerBasicBlockTransform);
+};
+
+// Takes a list of target function names, and applies filler transform only to

[chrisha, 2015/06/04 22:31:55]

Decorated function names? Undecorated? Please be very specific.

[huangs, 2015/06/05 15:13:24]

Done.

+// the specified functions. Also contains counters.

[chrisha, 2015/06/04 22:31:55]

Counters of what? For what purpose?

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

[huangs, 2015/06/05 15:13:24]

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.

+class FillerTransform
+    : public block_graph::transforms::IterativeTransformImpl<FillerTransform> {
+ public:
+  typedef block_graph::BasicBlockSubGraph BasicBlockSubGraph;
+  typedef block_graph::BlockGraph BlockGraph;
+  typedef BlockGraph::Block Block;
+
+  explicit FillerTransform(const std::vector<std::string>& target_list);

[chrisha, 2015/06/04 22:31:55]

We want this transform to be randomized, but repeatable. It should likely take a
random seed as input somewhere?

[huangs, 2015/06/05 15:13:24]

Can we do this in a separate CL? This complicates testing as well.

+  virtual ~FillerTransform() { }
+
+  // Accessors
+  // @{
+  size_t num_target_updated() const { return num_target_updated_; }
+  // @}
+
+  // For NamedBlockGraphTransformImpl.
+  static const char kTransformName[];
+
+ protected:
+  // Returns whether @p block is a target.
+  bool ShouldProcessBlock(Block* block) const;
+
+  // Verifies that all targets were found, and displays error messages if not.
+  void CheckAllTargetFound() const;

[chrisha, 2015/06/04 22:31:55]

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)

[huangs, 2015/06/05 15:13:24]

Done.

+
+  // @name IterativeTransformImpl implementation.
+  // @{
+  bool PreBlockGraphIteration(const TransformPolicyInterface* policy,
+                              BlockGraph* block_graph,
+                              Block* header_block);
+  bool OnBlock(const TransformPolicyInterface* policy,
+               BlockGraph* block_graph,
+               Block* block);
+  bool PostBlockGraphIteration(const TransformPolicyInterface* policy,
+                               BlockGraph* block_graph,
+                               Block* header_block);
+  // @}
+
+ private:
+  friend NamedBlockGraphTransformImpl<FillerTransform>;
+  friend IterativeTransformImpl<FillerTransform>;
+
+  scoped_ptr<FillerBasicBlockTransform> basic_block_transform_;
+
+  // Names of targets, maps to whether the target was seen.
+  std::map<std::string, bool> target_names_;
+
+  // Counters.

[chrisha, 2015/06/04 22:31:54]

I imagine these are used by CheckAllTargetsFound? Maybe document that fact.

[huangs, 2015/06/05 15:13:24]

Done.

+  // @{
+  size_t num_block_;
+  size_t num_code_block_;

[chrisha, 2015/06/04 22:31:55]

num_blocks_?

[chrisha, 2015/06/04 22:31:55]

num_code_basic_blocks_?

[huangs, 2015/06/05 15:13:24]

Done.

[huangs, 2015/06/05 15:13:24]

Done.

+  size_t num_target_updated_;

[chrisha, 2015/06/04 22:31:54]

num_targets_updated_?

[huangs, 2015/06/05 15:13:24]

Done.

+  // @}
+
+  DISALLOW_COPY_AND_ASSIGN(FillerTransform);
+};
+
+}  // namespace transforms
+}  // namespace instrument
+
+#endif  // SYZYGY_INSTRUMENT_TRANSFORMS_FILLER_TRANSFORM_H_