CodeGen: simplify unit tests [2/3]

sandbox/linux/seccomp-bpf/codegen_unittest.cc

Index: sandbox/linux/seccomp-bpf/codegen_unittest.cc
diff --git a/sandbox/linux/seccomp-bpf/codegen_unittest.cc b/sandbox/linux/seccomp-bpf/codegen_unittest.cc
index c5708dff6f3ed8f486b9c6ffed144e14aa9f9899..3f1a04bd710c5329df43bba2349234b3f3098063 100644
--- a/sandbox/linux/seccomp-bpf/codegen_unittest.cc
+++ b/sandbox/linux/seccomp-bpf/codegen_unittest.cc
@@ -6,79 +6,188 @@
 
 #include <linux/filter.h>
 
-#include <set>
-#include <string>
+#include <map>
+#include <utility>
 #include <vector>
 
-#include "sandbox/linux/seccomp-bpf/basicblock.h"
-#include "sandbox/linux/seccomp-bpf/errorcode.h"
-#include "sandbox/linux/seccomp-bpf/instruction.h"
+#include "base/macros.h"
+#include "base/md5.h"
+#include "base/strings/string_piece.h"
 #include "testing/gtest/include/gtest/gtest.h"
 
 namespace sandbox {
+namespace {
 
-// We want to access some of the private methods in the code generator. We
-// do so by defining a "friend" that makes these methods public for us.
-class CodeGenUnittestHelper : public CodeGen {
+// Hash provides an abstraction for building "hash trees" from BPF
+// control flow graphs, and efficiently identifying equivalent graphs.
+//
+// For simplicity, we use MD5, because base happens to provide a
+// convenient API for its use. However, any collision-resistant hash
+// should suffice.
+class Hash {
  public:
-  using CodeGen::CutGraphIntoBasicBlocks;
-  using CodeGen::FindBranchTargets;
-  using CodeGen::MergeTails;
-};
+  static const Hash kZero;
+
+  Hash() : digest_() {}
+
+  Hash(uint16_t code,
+       uint32_t k,
+       const Hash& jt = kZero,
+       const Hash& jf = kZero)
+      : digest_() {
+    base::MD5Context ctx;
+    base::MD5Init(&ctx);
+    HashValue(&ctx, code);
+    HashValue(&ctx, k);
+    HashValue(&ctx, jt);
+    HashValue(&ctx, jf);
+    base::MD5Final(&digest_, &ctx);
+  }
 
-namespace {
+  Hash(const Hash& hash) = default;
+  Hash& operator=(const Hash& rhs) = default;
+
+  friend bool operator==(const Hash& lhs, const Hash& rhs) {
+    return lhs.Base16() == rhs.Base16();
+  }
+  friend bool operator!=(const Hash& lhs, const Hash& rhs) {
+    return !(lhs == rhs);
+  }
+
+ private:
+  template <typename T>
+  void HashValue(base::MD5Context* ctx, const T& value) {
+    base::MD5Update(ctx,
+                    base::StringPiece(reinterpret_cast<const char*>(&value),
+                                      sizeof(value)));
+  }
+
+  std::string Base16() const {
+    return MD5DigestToBase16(digest_);
+  }
 
-enum {
-  NO_FLAGS = 0x0000,
-  HAS_MERGEABLE_TAILS = 0x0001,
+  base::MD5Digest digest_;
 };
 
-using ProgramTestFunc = void (*)(CodeGenUnittestHelper* gen,
-                                 CodeGen::Node head,
-                                 int flags);
+const Hash Hash::kZero;
 
-class ProgramTest : public ::testing::TestWithParam<ProgramTestFunc> {
- protected:
-  ProgramTest() : gen_() {}
+// Sanity check that equality and inequality work on Hash as required.
+TEST(CodeGen, HashSanity) {
+  std::vector<Hash> hashes;
 
-  // RunTest runs the test function argument.  It should be called at
-  // the end of each program test case.
-  void RunTest(CodeGen::Node head, int flags) {
-    GetParam()(&gen_, head, flags);
+  // Push a bunch of logically distinct hashes.
+  hashes.push_back(Hash::kZero);
+  for (int i = 0; i < 4; ++i) {
+    hashes.push_back(Hash(i & 1, i & 2));
+  }
+  for (int i = 0; i < 16; ++i) {
+    hashes.push_back(Hash(i & 1, i & 2, Hash(i & 4, i & 8)));
   }
+  for (int i = 0; i < 64; ++i) {
+    hashes.push_back(
+        Hash(i & 1, i & 2, Hash(i & 4, i & 8), Hash(i & 16, i & 32)));
+  }
+
+  for (const Hash& a : hashes) {
+    for (const Hash& b : hashes) {
+      // Hashes should equal themselves, but not equal all others.
+      if (&a == &b) {
+        EXPECT_EQ(a, b);
+      } else {
+        EXPECT_NE(a, b);
+      }
+    }
+  }
+}
+
+// ProgramTest provides a fixture for writing compiling sample
+// programs with CodeGen and verifying the linearized output matches
+// the input DAG.
+class ProgramTest : public ::testing::Test {
+ protected:
+  ProgramTest() : gen_(), node_hashes_() {}
 
+  // MakeInstruction calls CodeGen::MakeInstruction() and associated
+  // the returned address with a hash of the instruction.
   CodeGen::Node MakeInstruction(uint16_t code,
                                 uint32_t k,
-                                CodeGen::Node jt = nullptr,
-                                CodeGen::Node jf = nullptr) {
-    CodeGen::Node ret = gen_.MakeInstruction(code, k, jt, jf);
-    EXPECT_NE(nullptr, ret);
-    EXPECT_EQ(code, ret->code);
-    EXPECT_EQ(k, ret->k);
-    if (BPF_CLASS(code) == BPF_JMP) {
-      EXPECT_EQ(nullptr, ret->next);
-      EXPECT_EQ(jt, ret->jt_ptr);
-      EXPECT_EQ(jf, ret->jf_ptr);
+                                CodeGen::Node jt = CodeGen::kNullNode,
+                                CodeGen::Node jf = CodeGen::kNullNode) {
+    CodeGen::Node res = gen_.MakeInstruction(code, k, jt, jf);
+    EXPECT_NE(CodeGen::kNullNode, res);
+
+    Hash digest;
+    if (code == BPF_JMP + BPF_JA) {
+      // TODO(mdempsky): Disallow use of JA.
+      digest = Lookup(jt);
     } else {
-      EXPECT_EQ(jt, ret->next);
-      EXPECT_EQ(nullptr, ret->jt_ptr);
-      EXPECT_EQ(nullptr, ret->jf_ptr);
+      digest = Hash(code, k, Lookup(jt), Lookup(jf));
     }
-    return ret;
+    auto it = node_hashes_.insert(std::make_pair(res, digest));
+    EXPECT_EQ(digest, it.first->second);
+
+    return res;
+  }
+
+  // RunTest compiles the program and verifies that the output matches
+  // what is expected.  It should be called at the end of each program
+  // test case.
+  void RunTest(CodeGen::Node head) {
+    // Compile the program
+    CodeGen::Program program;
+    gen_.Compile(head, &program);
+
+    // Walk the program backwards, and compute the hash for each instruction.
+    std::vector<Hash> prog_hashes(program.size());
+    for (size_t i = program.size(); i > 0; --i) {
+      const sock_filter& insn = program.at(i - 1);
+      Hash& hash = prog_hashes.at(i - 1);
+
+      if (BPF_CLASS(insn.code) == BPF_JMP) {
+        if (BPF_OP(insn.code) == BPF_JA) {
+          // The compiler adds JA instructions as needed, so skip them.
+          hash = prog_hashes.at(i + insn.k);
+        } else {
+          hash = Hash(insn.code, insn.k, prog_hashes.at(i + insn.jt),
+                      prog_hashes.at(i + insn.jf));
+        }
+      } else if (BPF_CLASS(insn.code) == BPF_RET) {
+        hash = Hash(insn.code, insn.k);
+      } else {
+        hash = Hash(insn.code, insn.k, prog_hashes.at(i));
+      }
+    }
+
+    EXPECT_EQ(Lookup(head), prog_hashes.at(0));
   }
 
  private:
-  CodeGenUnittestHelper gen_;
+  const Hash& Lookup(CodeGen::Node next) const {
+    if (next == CodeGen::kNullNode) {
+      return Hash::kZero;
+    }
+    auto it = node_hashes_.find(next);
+    if (it == node_hashes_.end()) {
+      ADD_FAILURE() << "No hash found for node " << next;
+      return Hash::kZero;
+    }
+    return it->second;
+  }
+
+  CodeGen gen_;
+  std::map<CodeGen::Node, Hash> node_hashes_;
+
+  DISALLOW_COPY_AND_ASSIGN(ProgramTest);
 };
 
-TEST_P(ProgramTest, OneInstruction) {
+TEST_F(ProgramTest, OneInstruction) {
   // Create the most basic valid BPF program:
   //    RET 0
   CodeGen::Node head = MakeInstruction(BPF_RET + BPF_K, 0);
-  RunTest(head, NO_FLAGS);
+  RunTest(head);
 }
 
-TEST_P(ProgramTest, SimpleBranch) {
+TEST_F(ProgramTest, SimpleBranch) {
   // Create a program with a single branch:
   //    JUMP if eq 42 then $0 else $1
   // 0: RET 1
@@ -86,10 +195,10 @@ TEST_P(ProgramTest, SimpleBranch) {
   CodeGen::Node head = MakeInstruction(BPF_JMP + BPF_JEQ + BPF_K, 42,
                                        MakeInstruction(BPF_RET + BPF_K, 1),
                                        MakeInstruction(BPF_RET + BPF_K, 0));
-  RunTest(head, NO_FLAGS);
+  RunTest(head);
 }
 
-TEST_P(ProgramTest, AtypicalBranch) {
+TEST_F(ProgramTest, AtypicalBranch) {
   // Create a program with a single branch:
   //    JUMP if eq 42 then $0 else $0
   // 0: RET 0
@@ -100,10 +209,10 @@ TEST_P(ProgramTest, AtypicalBranch) {
   // N.B.: As the instructions in both sides of the branch are already
   //       the same object, we do not actually have any "mergeable" branches.
   //       This needs to be reflected in our choice of "flags".
-  RunTest(head, NO_FLAGS);
+  RunTest(head);
 }
 
-TEST_P(ProgramTest, Complex) {
+TEST_F(ProgramTest, Complex) {
   // Creates a basic BPF program that we'll use to test some of the code:
   //    JUMP if eq 42 the $0 else $1     (insn6)
   // 0: LD 23                            (insn5)
@@ -135,10 +244,10 @@ TEST_P(ProgramTest, Complex) {
   CodeGen::Node insn6 =
       MakeInstruction(BPF_JMP + BPF_JEQ + BPF_K, 42, insn5, insn4);
 
-  RunTest(insn6, HAS_MERGEABLE_TAILS);
+  RunTest(insn6);
 }
 
-TEST_P(ProgramTest, ConfusingTails) {
+TEST_F(ProgramTest, ConfusingTails) {
   // This simple program demonstrates https://crbug.com/351103/
   // The two "LOAD 0" instructions are blocks of their own. MergeTails() could
   // be tempted to merge them since they are the same. However, they are
@@ -166,10 +275,10 @@ TEST_P(ProgramTest, ConfusingTails) {
   CodeGen::Node i1 = MakeInstruction(BPF_JMP + BPF_JEQ + BPF_K, 1, i2, i3);
   CodeGen::Node i0 = MakeInstruction(BPF_LD + BPF_W + BPF_ABS, 1, i1);
 
-  RunTest(i0, NO_FLAGS);
+  RunTest(i0);
 }
 
-TEST_P(ProgramTest, ConfusingTailsBasic) {
+TEST_F(ProgramTest, ConfusingTailsBasic) {
   // Without the fix for https://crbug.com/351103/, (see
   // SampleProgramConfusingTails()), this would generate a cyclic graph and
   // crash as the two "LOAD 0" instructions would get merged.
@@ -188,10 +297,10 @@ TEST_P(ProgramTest, ConfusingTailsBasic) {
   CodeGen::Node i1 = MakeInstruction(BPF_JMP + BPF_JEQ + BPF_K, 1, i2, i3);
   CodeGen::Node i0 = MakeInstruction(BPF_LD + BPF_W + BPF_ABS, 1, i1);
 
-  RunTest(i0, NO_FLAGS);
+  RunTest(i0);
 }
 
-TEST_P(ProgramTest, ConfusingTailsMergeable) {
+TEST_F(ProgramTest, ConfusingTailsMergeable) {
   // This is similar to SampleProgramConfusingTails(), except that
   // instructions 2 and 4 are now RET instructions.
   // In PointerCompare(), this exercises the path where two blocks are of the
@@ -216,287 +325,8 @@ TEST_P(ProgramTest, ConfusingTailsMergeable) {
   CodeGen::Node i1 = MakeInstruction(BPF_JMP + BPF_JEQ + BPF_K, 1, i2, i3);
   CodeGen::Node i0 = MakeInstruction(BPF_LD + BPF_W + BPF_ABS, 1, i1);
 
-  RunTest(i0, HAS_MERGEABLE_TAILS);
+  RunTest(i0);
 }
 
-void MakeInstruction(CodeGenUnittestHelper* codegen,
-                     CodeGen::Node program,
-                     int) {
-  // Nothing to do here
-}
-
-void FindBranchTargets(CodeGenUnittestHelper* codegen, CodeGen::Node prg, int) {
-  BranchTargets branch_targets;
-  codegen->FindBranchTargets(*prg, &branch_targets);
-
-  // Verifying the general properties that should be true for every
-  // well-formed BPF program.
-  // Perform a depth-first traversal of the BPF program an verify that all
-  // targets of BPF_JMP instructions are represented in the "branch_targets".
-  // At the same time, compute a set of both the branch targets and all the
-  // instructions in the program.
-  std::vector<CodeGen::Node> stack;
-  std::set<CodeGen::Node> all_instructions;
-  std::set<CodeGen::Node> target_instructions;
-  BranchTargets::const_iterator end = branch_targets.end();
-  for (CodeGen::Node insn = prg;;) {
-    all_instructions.insert(insn);
-    if (BPF_CLASS(insn->code) == BPF_JMP) {
-      target_instructions.insert(insn->jt_ptr);
-      ASSERT_TRUE(insn->jt_ptr != NULL);
-      ASSERT_TRUE(branch_targets.find(insn->jt_ptr) != end);
-      if (BPF_OP(insn->code) != BPF_JA) {
-        target_instructions.insert(insn->jf_ptr);
-        ASSERT_TRUE(insn->jf_ptr != NULL);
-        ASSERT_TRUE(branch_targets.find(insn->jf_ptr) != end);
-        stack.push_back(insn->jf_ptr);
-      }
-      insn = insn->jt_ptr;
-    } else if (BPF_CLASS(insn->code) == BPF_RET) {
-      ASSERT_TRUE(insn->next == NULL);
-      if (stack.empty()) {
-        break;
-      }
-      insn = stack.back();
-      stack.pop_back();
-    } else {
-      ASSERT_TRUE(insn->next != NULL);
-      insn = insn->next;
-    }
-  }
-  ASSERT_TRUE(target_instructions.size() == branch_targets.size());
-
-  // We can now subtract the set of the branch targets from the set of all
-  // instructions. This gives us a set with the instructions that nobody
-  // ever jumps to. Verify that they are no included in the
-  // "branch_targets" that FindBranchTargets() computed for us.
-  Instructions non_target_instructions(all_instructions.size() -
-                                       target_instructions.size());
-  set_difference(all_instructions.begin(),
-                 all_instructions.end(),
-                 target_instructions.begin(),
-                 target_instructions.end(),
-                 non_target_instructions.begin());
-  for (Instructions::const_iterator iter = non_target_instructions.begin();
-       iter != non_target_instructions.end();
-       ++iter) {
-    ASSERT_TRUE(branch_targets.find(*iter) == end);
-  }
-}
-
-void CutGraphIntoBasicBlocks(CodeGenUnittestHelper* codegen,
-                             CodeGen::Node prg,
-                             int) {
-  BranchTargets branch_targets;
-  codegen->FindBranchTargets(*prg, &branch_targets);
-  TargetsToBlocks all_blocks;
-  BasicBlock* first_block =
-      codegen->CutGraphIntoBasicBlocks(prg, branch_targets, &all_blocks);
-  ASSERT_TRUE(first_block != NULL);
-  ASSERT_TRUE(first_block->instructions.size() > 0);
-  CodeGen::Node first_insn = first_block->instructions[0];
-
-  // Basic blocks are supposed to start with a branch target and end with
-  // either a jump or a return instruction. It can also end, if the next
-  // instruction forms the beginning of a new basic block. There should be
-  // no other jumps or return instructions in the middle of a basic block.
-  for (TargetsToBlocks::const_iterator bb_iter = all_blocks.begin();
-       bb_iter != all_blocks.end();
-       ++bb_iter) {
-    BasicBlock* bb = bb_iter->second;
-    ASSERT_TRUE(bb != NULL);
-    ASSERT_TRUE(bb->instructions.size() > 0);
-    CodeGen::Node insn = bb->instructions[0];
-    ASSERT_TRUE(insn == first_insn ||
-                branch_targets.find(insn) != branch_targets.end());
-    for (Instructions::const_iterator insn_iter = bb->instructions.begin();;) {
-      insn = *insn_iter;
-      if (++insn_iter != bb->instructions.end()) {
-        ASSERT_TRUE(BPF_CLASS(insn->code) != BPF_JMP);
-        ASSERT_TRUE(BPF_CLASS(insn->code) != BPF_RET);
-      } else {
-        ASSERT_TRUE(BPF_CLASS(insn->code) == BPF_JMP ||
-                    BPF_CLASS(insn->code) == BPF_RET ||
-                    branch_targets.find(insn->next) != branch_targets.end());
-        break;
-      }
-      ASSERT_TRUE(branch_targets.find(*insn_iter) == branch_targets.end());
-    }
-  }
-}
-
-void MergeTails(CodeGenUnittestHelper* codegen, CodeGen::Node prg, int flags) {
-  BranchTargets branch_targets;
-  codegen->FindBranchTargets(*prg, &branch_targets);
-  TargetsToBlocks all_blocks;
-  BasicBlock* first_block =
-      codegen->CutGraphIntoBasicBlocks(prg, branch_targets, &all_blocks);
-
-  // The shape of our graph and thus the function of our program should
-  // still be unchanged after we run MergeTails(). We verify this by
-  // serializing the graph and verifying that it is still the same.
-  // We also verify that at least some of the edges changed because of
-  // tail merging.
-  std::string graph[2];
-  std::string edges[2];
-
-  // The loop executes twice. After the first run, we call MergeTails() on
-  // our graph.
-  for (int i = 0;;) {
-    // Traverse the entire program in depth-first order.
-    std::vector<BasicBlock*> stack;
-    for (BasicBlock* bb = first_block;;) {
-      // Serialize the instructions in this basic block. In general, we only
-      // need to serialize "code" and "k"; except for a BPF_JA instruction
-      // where "k" isn't set.
-      // The stream of instructions should be unchanged after MergeTails().
-      for (Instructions::const_iterator iter = bb->instructions.begin();
-           iter != bb->instructions.end();
-           ++iter) {
-        graph[i].append(reinterpret_cast<char*>(&(*iter)->code),
-                        sizeof((*iter)->code));
-        if (BPF_CLASS((*iter)->code) != BPF_JMP ||
-            BPF_OP((*iter)->code) != BPF_JA) {
-          graph[i].append(reinterpret_cast<char*>(&(*iter)->k),
-                          sizeof((*iter)->k));
-        }
-      }
-
-      // Also serialize the addresses the basic blocks as we encounter them.
-      // This will change as basic blocks are coalesed by MergeTails().
-      edges[i].append(reinterpret_cast<char*>(&bb), sizeof(bb));
-
-      // Depth-first traversal of the graph. We only ever need to look at the
-      // very last instruction in the basic block, as that is the only one that
-      // can change code flow.
-      CodeGen::Node insn = bb->instructions.back();
-      if (BPF_CLASS(insn->code) == BPF_JMP) {
-        // For jump instructions, we need to remember the "false" branch while
-        // traversing the "true" branch. This is not necessary for BPF_JA which
-        // only has a single branch.
-        if (BPF_OP(insn->code) != BPF_JA) {
-          stack.push_back(all_blocks[insn->jf_ptr]);
-        }
-        bb = all_blocks[insn->jt_ptr];
-      } else if (BPF_CLASS(insn->code) == BPF_RET) {
-        // After a BPF_RET, see if we need to back track.
-        if (stack.empty()) {
-          break;
-        }
-        bb = stack.back();
-        stack.pop_back();
-      } else {
-        // For "normal" instructions, just follow to the next basic block.
-        bb = all_blocks[insn->next];
-      }
-    }
-
-    // Our loop runs exactly two times.
-    if (++i > 1) {
-      break;
-    }
-    codegen->MergeTails(&all_blocks);
-  }
-  ASSERT_TRUE(graph[0] == graph[1]);
-  if (flags & HAS_MERGEABLE_TAILS) {
-    ASSERT_TRUE(edges[0] != edges[1]);
-  } else {
-    ASSERT_TRUE(edges[0] == edges[1]);
-  }
-}
-
-void CompileAndCompare(CodeGenUnittestHelper* codegen, CodeGen::Node prg, int) {
-  // TopoSortBasicBlocks() has internal checks that cause it to fail, if it
-  // detects a problem. Typically, if anything goes wrong, this looks to the
-  // TopoSort algorithm as if there had been cycles in the input data.
-  // This provides a pretty good unittest.
-  // We hand-crafted the program returned by SampleProgram() to exercise
-  // several of the more interesting code-paths. See comments in
-  // SampleProgram() for details.
-  // In addition to relying on the internal consistency checks in the compiler,
-  // we also serialize the graph and the resulting BPF program and compare
-  // them. With the exception of BPF_JA instructions that might have been
-  // inserted, both instruction streams should be equivalent.
-  // As Compile() modifies the instructions, we have to serialize the graph
-  // before calling Compile().
-  std::string source;
-  Instructions source_stack;
-  for (const Instruction* insn = prg, *next; insn; insn = next) {
-    if (BPF_CLASS(insn->code) == BPF_JMP) {
-      if (BPF_OP(insn->code) == BPF_JA) {
-        // Do not serialize BPF_JA instructions (see above).
-        next = insn->jt_ptr;
-        continue;
-      } else {
-        source_stack.push_back(insn->jf_ptr);
-        next = insn->jt_ptr;
-      }
-    } else if (BPF_CLASS(insn->code) == BPF_RET) {
-      if (source_stack.empty()) {
-        next = NULL;
-      } else {
-        next = source_stack.back();
-        source_stack.pop_back();
-      }
-    } else {
-      next = insn->next;
-    }
-    // Only serialize "code" and "k". That's all the information we need to
-    // compare. The rest of the information is encoded in the order of
-    // instructions.
-    source.append(reinterpret_cast<const char*>(&insn->code),
-                  sizeof(insn->code));
-    source.append(reinterpret_cast<const char*>(&insn->k), sizeof(insn->k));
-  }
-
-  // Compile the program
-  CodeGen::Program bpf;
-  codegen->Compile(prg, &bpf);
-
-  // Serialize the resulting BPF instructions.
-  std::string assembly;
-  std::vector<int> assembly_stack;
-  for (int idx = 0; idx >= 0;) {
-    ASSERT_TRUE(idx < (int)bpf.size());
-    struct sock_filter& insn = bpf[idx];
-    if (BPF_CLASS(insn.code) == BPF_JMP) {
-      if (BPF_OP(insn.code) == BPF_JA) {
-        // Do not serialize BPF_JA instructions (see above).
-        idx += insn.k + 1;
-        continue;
-      } else {
-        assembly_stack.push_back(idx + insn.jf + 1);
-        idx += insn.jt + 1;
-      }
-    } else if (BPF_CLASS(insn.code) == BPF_RET) {
-      if (assembly_stack.empty()) {
-        idx = -1;
-      } else {
-        idx = assembly_stack.back();
-        assembly_stack.pop_back();
-      }
-    } else {
-      ++idx;
-    }
-    // Serialize the same information that we serialized before compilation.
-    assembly.append(reinterpret_cast<char*>(&insn.code), sizeof(insn.code));
-    assembly.append(reinterpret_cast<char*>(&insn.k), sizeof(insn.k));
-  }
-  ASSERT_TRUE(source == assembly);
-}
-
-const ProgramTestFunc kProgramTestFuncs[] = {
-    MakeInstruction,
-    FindBranchTargets,
-    CutGraphIntoBasicBlocks,
-    MergeTails,
-    CompileAndCompare,
-};
-
-INSTANTIATE_TEST_CASE_P(CodeGen,
-                        ProgramTest,
-                        ::testing::ValuesIn(kProgramTestFuncs));
-
 }  // namespace
-
 }  // namespace sandbox