Linux Sandbox: fix BPF compiler bug

sandbox/linux/seccomp-bpf/codegen.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 <stdio.h>
 
+#include "base/logging.h"
 #include "sandbox/linux/seccomp-bpf/codegen.h"
 
 namespace {
 
 // Helper function for Traverse().
 void TraverseRecursively(std::set<sandbox::Instruction*>* visited,
                          sandbox::Instruction* instruction) {
   if (visited->find(instruction) == visited->end()) {
     visited->insert(instruction);
     switch (BPF_CLASS(instruction->code)) {
@@ skipping 408 matching lines @@
   // Return <0, 0, or >0 depending on the ordering of "block1" and "block2".
   // If we are looking at the exact same block, this is trivial and we don't
   // need to do a full comparison.
   if (block1 == block2) {
     return 0;
   }
 
   // We compare the sequence of instructions in both basic blocks.
   const Instructions& insns1 = block1->instructions;
   const Instructions& insns2 = block2->instructions;
+  // Basic blocks should never be empty.
+  CHECK(!insns1.empty());
+  CHECK(!insns2.empty());
+
   Instructions::const_iterator iter1 = insns1.begin();
   Instructions::const_iterator iter2 = insns2.begin();
   for (;; ++iter1, ++iter2) {
     // If we have reached the end of the sequence of instructions in one or
     // both basic blocks, we know the relative ordering between the two blocks
     // and can return.
     if (iter1 == insns1.end()) {
-      return iter2 == insns2.end() ? 0 : -1;
+      if (iter2 == insns2.end()) {
+        // If the two blocks are the same length (and have elementwise-equal
+        // code and k fields, which is the only way we can reach this point),
+        // and the last instruction isn't a JMP or a RET, then we must compare
+        // their successors.
+        Instruction* const insns1_last = insns1.back();
+        Instruction* const insns2_last = insns2.back();
+        if (BPF_CLASS(insns1_last->code) != BPF_JMP &&
+            BPF_CLASS(insns1_last->code) != BPF_RET) {
+          // Non jumping instructions will always have a valid next instruction.
+          CHECK(insns1_last->next);
+          CHECK(insns2_last->next);
+          return PointerCompare(blocks.find(insns1_last->next)->second,
+                                blocks.find(insns2_last->next)->second,
+                                blocks);
+        } else {
+          return 0;
+        }
+      }
+      return -1;
     } else if (iter2 == insns2.end()) {
       return 1;
     }
 
     // Compare the individual fields for both instructions.
     const Instruction& insn1 = **iter1;
     const Instruction& insn2 = **iter2;
     if (insn1.code == insn2.code) {
       if (insn1.k == insn2.k) {
         // Only conditional jump instructions use the jt_ptr and jf_ptr
@@ skipping 288 matching lines @@
       CutGraphIntoBasicBlocks(instructions, branch_targets, &all_blocks);
   MergeTails(&all_blocks);
   BasicBlocks basic_blocks;
   TopoSortBasicBlocks(first_block, all_blocks, &basic_blocks);
   ComputeRelativeJumps(&basic_blocks, all_blocks);
   ConcatenateBasicBlocks(basic_blocks, program);
   return;
 }
 
 }  // namespace sandbox