Update from https://crrev.com/305340

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 <map>
 #include <utility>
@@ skipping 98 matching lines @@
 
   // 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 = 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 {
-      digest = Hash(code, k, Lookup(jt), Lookup(jf));
-    }
+    Hash digest(code, k, Lookup(jt), Lookup(jf));
     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) {
@@ skipping 81 matching lines @@
   //    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)
   // 3: LD 42                            (insn1)
   //    RET 42                           (insn0)
   // 4: LD 42                            (insn3)
   //    RET 42                           (insn3+)
   CodeGen::Node insn0 = MakeInstruction(BPF_RET + BPF_K, 42);
   CodeGen::Node insn1 = MakeInstruction(BPF_LD + BPF_W + BPF_ABS, 42, insn0);
-  CodeGen::Node insn2 = MakeInstruction(BPF_JMP + BPF_JA, 0, insn1);
+  CodeGen::Node insn2 = insn1;  // Implicit JUMP
 
-  // We explicitly duplicate instructions so that MergeTails() can coalesce
-  // them later.
+  // We explicitly duplicate instructions to test that they're merged.
   CodeGen::Node insn3 = MakeInstruction(BPF_LD + BPF_W + BPF_ABS, 42,
                                         MakeInstruction(BPF_RET + BPF_K, 42));
+  EXPECT_EQ(insn2, insn3);
 
   CodeGen::Node insn4 =
       MakeInstruction(BPF_JMP + BPF_JEQ + BPF_K, 42, insn2, insn3);
   CodeGen::Node 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::Node i5 = MakeInstruction(BPF_JMP + BPF_JEQ + BPF_K, 1, i6, i7);
   CodeGen::Node i4 = MakeInstruction(BPF_RET + BPF_K, 42);
   CodeGen::Node i3 = MakeInstruction(BPF_JMP + BPF_JEQ + BPF_K, 2, i4, i5);
   CodeGen::Node i2 = MakeInstruction(BPF_RET + BPF_K, 42);
   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);
 }
 
+TEST_F(ProgramTest, InstructionFolding) {
+  // Check that simple instructions are folded as expected.
+  CodeGen::Node a = MakeInstruction(BPF_RET + BPF_K, 0);
+  EXPECT_EQ(a, MakeInstruction(BPF_RET + BPF_K, 0));
+  CodeGen::Node 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::Node 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);
+}
+
+TEST_F(ProgramTest, FarBranches) {
+  // BPF instructions use 8-bit fields for branch offsets, which means
+  // branch targets must be within 255 instructions of the branch
+  // instruction. CodeGen abstracts away this detail by inserting jump
+  // instructions as needed, which we test here by generating programs
+  // that should trigger any interesting boundary conditions.
+
+  // Populate with 260 initial instruction nodes.
+  std::vector<CodeGen::Node> nodes;
+  nodes.push_back(MakeInstruction(BPF_RET + BPF_K, 0));
+  for (size_t i = 1; i < 260; ++i) {
+    nodes.push_back(
+        MakeInstruction(BPF_ALU + BPF_ADD + BPF_K, i, nodes.back()));
+  }
+
+  // Exhaustively test branch offsets near BPF's limits.
+  for (size_t jt = 250; jt < 260; ++jt) {
+    for (size_t jf = 250; jf < 260; ++jf) {
+      nodes.push_back(MakeInstruction(BPF_JMP + BPF_JEQ + BPF_K, 0,
+                                      nodes.rbegin()[jt], nodes.rbegin()[jf]));
+      RunTest(nodes.back());
+    }
+  }
+}
+
 }  // namespace
 }  // namespace sandbox