CodeGen: rewrite implementation [3/3]

sandbox/linux/seccomp-bpf/codegen_unittest.cc

 // Copyright (c) 2012 The Chromium Authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 #include "sandbox/linux/seccomp-bpf/codegen.h"
 
 #include <linux/filter.h>
 
 #include <cstring>
 #include <map>
@@ skipping 95 matching lines @@
 
   // MakeInstruction calls CodeGen::MakeInstruction() and associated
   // the returned address with a hash of the instruction.
   CodeGen::Addr MakeInstruction(uint16_t code,
                                 uint32_t k,
                                 CodeGen::Addr jt = CodeGen::kNullAddr,
                                 CodeGen::Addr jf = CodeGen::kNullAddr) {
     CodeGen::Addr res = gen_.MakeInstruction(code, k, jt, jf);
     EXPECT_NE(CodeGen::kNullAddr, res);
 
-    Hash digest;
-    if (code == BPF_JMP + BPF_JA) {
-      // TODO(mdempsky): Disallow use of JA.
-      digest = Lookup(jt);
-    } else {
-      digest = Hash(code, k, Lookup(jt), Lookup(jf));
-    }
+    Hash digest(code, k, Lookup(jt), Lookup(jf));
     auto it = addr_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::Addr head) {
@@ skipping 71 matching lines @@
   //       the same object, we do not actually have any "mergeable" branches.
   //       This needs to be reflected in our choice of "flags".
   RunTest(head);
 }
 
 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)
   // 1: JUMP if eq 42 then $2 else $4    (insn4)
   // 2: JUMP to $3                       (insn2)

[rickyz (no longer on Chrome), 2014/11/12 23:43:50]

Update this comment now that we got rid of the jump

[mdempsky, 2014/11/18 01:07:30]

So my reasoning was this is the description of the program we logically want to
encode, and then below is how we actually encoded it using the current CodeGen
API.  The current API uses implicit JUMPs from simply reusing a Node (hence the
"Implicit JUMP" comment below).

If you prefer, I can remove the JUMP and renumber the insn variables?

   // 3: LD 42                            (insn1)
   //    RET 42                           (insn0)
   // 4: LD 42                            (insn3)
   //    RET 42                           (insn3+)
   CodeGen::Addr insn0 = MakeInstruction(BPF_RET + BPF_K, 42);
   CodeGen::Addr insn1 = MakeInstruction(BPF_LD + BPF_W + BPF_ABS, 42, insn0);
-  CodeGen::Addr insn2 = MakeInstruction(BPF_JMP + BPF_JA, 0, insn1);
+  CodeGen::Addr insn2 = insn1;  // Implicit JUMP
 
-  // We explicitly duplicate instructions so that MergeTails() can coalesce
-  // them later.
+  // We explicitly duplicate instructions to check that CodeGen merges them.
   CodeGen::Addr insn3 = MakeInstruction(BPF_LD + BPF_W + BPF_ABS, 42,
                                         MakeInstruction(BPF_RET + BPF_K, 42));
+  EXPECT_EQ(insn2, insn3);
 
   CodeGen::Addr insn4 =
       MakeInstruction(BPF_JMP + BPF_JEQ + BPF_K, 42, insn2, insn3);
   CodeGen::Addr insn5 = MakeInstruction(BPF_LD + BPF_W + BPF_ABS, 23, insn4);
 
   // Force a basic block that ends in neither a jump instruction nor a return
   // instruction. It only contains "insn5". This exercises one of the less
   // common code paths in the topo-sort algorithm.
   // This also gives us a diamond-shaped pattern in our graph, which stresses
   // another aspect of the topo-sort algorithm (namely, the ability to
@@ skipping 78 matching lines @@
   CodeGen::Addr i5 = MakeInstruction(BPF_JMP + BPF_JEQ + BPF_K, 1, i6, i7);
   CodeGen::Addr i4 = MakeInstruction(BPF_RET + BPF_K, 42);
   CodeGen::Addr i3 = MakeInstruction(BPF_JMP + BPF_JEQ + BPF_K, 2, i4, i5);
   CodeGen::Addr i2 = MakeInstruction(BPF_RET + BPF_K, 42);
   CodeGen::Addr i1 = MakeInstruction(BPF_JMP + BPF_JEQ + BPF_K, 1, i2, i3);
   CodeGen::Addr i0 = MakeInstruction(BPF_LD + BPF_W + BPF_ABS, 1, i1);
 
   RunTest(i0);
 }
 
+TEST_F(ProgramTest, InstructionFolding) {
+  // Check that simple instructions are folded as expected.
+  CodeGen::Addr a = MakeInstruction(BPF_RET + BPF_K, 0);
+  EXPECT_EQ(a, MakeInstruction(BPF_RET + BPF_K, 0));
+  CodeGen::Addr b = MakeInstruction(BPF_RET + BPF_K, 1);
+  EXPECT_EQ(a, MakeInstruction(BPF_RET + BPF_K, 0));
+  EXPECT_EQ(b, MakeInstruction(BPF_RET + BPF_K, 1));
+  EXPECT_EQ(b, MakeInstruction(BPF_RET + BPF_K, 1));
+
+  // Check that complex sequences are folded too.
+  CodeGen::Addr c =
+      MakeInstruction(BPF_LD + BPF_W + BPF_ABS, 0,
+                      MakeInstruction(BPF_JMP + BPF_JSET + BPF_K, 0x100, a, b));
+  EXPECT_EQ(c, MakeInstruction(
+                   BPF_LD + BPF_W + BPF_ABS, 0,
+                   MakeInstruction(BPF_JMP + BPF_JSET + BPF_K, 0x100, a, b)));
+
+  RunTest(c);
+}
+
 }  // namespace

[rickyz (no longer on Chrome), 2014/11/12 23:43:50]

Can you add a test that calls MakeInstruction with jt/jf > 255?

[mdempsky, 2014/11/18 01:07:30]

Done.

 }  // namespace sandbox