Use binary search to optimize code generation for BPF filters.

BUG=130662
TEST=make && ./demo32 && ./demo64


Review URL: https://chromiumcodereview.appspot.com/10538075

git-svn-id: svn://svn.chromium.org/chrome/trunk/src@142365 0039d316-1c4b-4281-b951-d872f2087c98

3 files changed, 123 insertions, 38 deletions

diff --git a/sandbox/linux/seccomp-bpf/sandbox_bpf.cc b/sandbox/linux/seccomp-bpf/sandbox_bpf.cc
index 60a400d..85900ea 100644
--- a/sandbox/linux/seccomp-bpf/sandbox_bpf.cc
+++ b/sandbox/linux/seccomp-bpf/sandbox_bpf.cc
@@ -343,19 +343,18 @@ void Sandbox::installFilter() {
                        "Illegal mixing of system call ABIs")));
 #endif
 
-  // Evaluate all possible system calls and group their ErrorCodes into
-  // ranges of identical codes.
-  Ranges ranges;
-  findRanges(&ranges);
 
-  // Compile the system call ranges to an optimized BPF program.
-  rangesToBPF(program, ranges);
+  {
+    // Evaluate all possible system calls and group their ErrorCodes into
+    // ranges of identical codes.
+    Ranges ranges;
+    findRanges(&ranges);
 
-  // Unless there is a bug in the compiler, there is no execution path through
-  // the BPF program that falls through to the end.
-  program->push_back((struct sock_filter)
-    BPF_STMT(BPF_RET+BPF_K,
-             ErrorCode(bpfFailure, "Detected unfiltered system call")));
+    // Compile the system call ranges to an optimized BPF program
+    RetInsns rets;
+    emitJumpStatements(program, &rets, ranges.begin(), ranges.end());
+    emitReturnStatements(program, rets);
+  }
 
   // Make sure compilation resulted in BPF program that executes
   // correctly. Otherwise, there is an internal error in our BPF compiler.
@@ -435,37 +434,104 @@ void Sandbox::findRanges(Ranges *ranges) {
     Range(oldSysnum, std::numeric_limits<unsigned>::max(), oldErr));
 }
 
-void Sandbox::rangesToBPF(Program *program, const Ranges& ranges) {
-  // TODO: We currently search linearly through all ranges. An improved
-  //       algorithm should be doing a binary search.
-
-  // System call ranges must cover the entire number range.
-  if (ranges.empty() ||
-      ranges.begin()->from != 0 ||
-      ranges.back().to != std::numeric_limits<unsigned>::max()) {
-  rangeError:
+void Sandbox::emitJumpStatements(Program *program, RetInsns *rets,
+                                 Ranges::const_iterator start,
+                                 Ranges::const_iterator stop) {
+  // We convert the list of system call ranges into jump table that performs
+  // a binary search over the ranges.
+  // As a sanity check, we need to have at least two distinct ranges for us
+  // to be able to build a jump table.
+  if (stop - start <= 1) {
     die("Invalid set of system call ranges");
   }
-  uint32_t from = 0;
-  for (Ranges::const_iterator iter = ranges.begin();
-       iter != ranges.end();
-       ++iter) {
-    // Ranges must be contiguous and monotonically increasing.
-    if (iter->from > iter->to ||
-        iter->from != from) {
-      goto rangeError;
+
+  // Pick the range object that is located at the mid point of our list.
+  // We compare our system call number against the lowest valid system call
+  // number in this range object. If our number is lower, it is outside of
+  // this range object. If it is greater or equal, it might be inside.
+  Ranges::const_iterator mid = start + (stop - start)/2;
+  Program::size_type jmp = program->size();
+  if (jmp >= SECCOMP_MAX_PROGRAM_SIZE) {
+  compiler_err:
+    die("Internal compiler error; failed to compile jump table");
+  }
+  program->push_back((struct sock_filter)
+    BPF_JUMP(BPF_JMP+BPF_JGE+BPF_K, mid->from,
+             // Jump targets are place-holders that will be fixed up later.
+             0, 0));
+
+  // The comparison turned out to be false; i.e. our system call number is
+  // less than the range object at the mid point of the list.
+  if (mid - start == 1) {
+    // If we have narrowed things down to a single range object, we can
+    // return from the BPF filter program.
+    // Instead of emitting a BPF_RET statement, we want to coalesce all
+    // identical BPF_RET statements into a single instance. This results in
+    // a more efficient BPF program that uses less CPU cache.
+    // Since all branches in BPF programs have to be forward branches, we
+    // keep track of our current instruction pointer and then fix up the
+    // branch when we emit the BPF_RET statement in emitReturnStatements().
+    (*rets)[start->err].push_back(FixUp(jmp, false));
+  } else {
+    // Sub-divide the list of ranges and continue recursively.
+    emitJumpStatements(program, rets, start, mid);
+  }
+
+  // The comparison turned out to be true; i.e. our system call number is
+  // greater or equal to the range object at the mid point of the list.
+  if (stop - mid == 1) {
+    // We narrowed things down to a single range object. Remember instruction
+    // pointer and exit code, so that we can patch up the target of the jump
+    // instruction in emitReturnStatements().
+    (*rets)[mid->err].push_back(FixUp(jmp, true));
+  } else {
+    // We now know where the block of instructions for the "true" comparison
+    // starts. Patch up the jump target of the BPF_JMP instruction that we
+    // emitted earlier.
+    int distance = program->size() - jmp - 1;
+    if (distance < 0 || distance > 255) {
+      goto compiler_err;
     }
-    from = iter->to + 1;
+    (*program)[jmp].jt = distance;
 
-    // Emit BPF instructions matching this range.
-    if (iter->to != std::numeric_limits<unsigned>::max()) {
-      program->push_back((struct sock_filter)
-        BPF_JUMP(BPF_JMP+BPF_JGT+BPF_K, iter->to, 1, 0));
+    // Sub-divide the list of ranges and continue recursively.
+    emitJumpStatements(program, rets, mid, stop);
+  }
+}
+
+void Sandbox::emitReturnStatements(Program *program, const RetInsns& rets) {
+  // Iterate over the list of distinct exit codes from our BPF filter
+  // program and emit the BPF_RET statements.
+  for (RetInsns::const_iterator ret_iter = rets.begin();
+       ret_iter != rets.end();
+       ++ret_iter) {
+    Program::size_type ip = program->size();
+    if (ip >= SECCOMP_MAX_PROGRAM_SIZE) {
+      die("Internal compiler error; failed to compile jump table");
     }
     program->push_back((struct sock_filter)
-      BPF_STMT(BPF_RET+BPF_K, iter->err));
+      BPF_STMT(BPF_RET+BPF_K, ret_iter->first));
+
+    // Iterate over the instruction pointers for the BPF_JMP instructions
+    // that need to be patched up.
+    for (std::vector<FixUp>::const_iterator insn_iter=ret_iter->second.begin();
+         insn_iter != ret_iter->second.end();
+         ++insn_iter) {
+      // Jumps are always relative and they are always forward.
+      int distance = ip - insn_iter->addr - 1;
+      if (distance < 0 || distance > 255) {
+        die("Internal compiler error; failed to compile jump table");
+      }
+
+      // Decide whether we need to patch up the "true" or the "false" jump
+      // target.
+      if (insn_iter->jt) {
+        (*program)[insn_iter->addr].jt = distance;
+      } else {
+        (*program)[insn_iter->addr].jf = distance;
+      }
+    }
   }
-  return;
 }
 
 void Sandbox::sigSys(int nr, siginfo_t *info, void *void_context) {
@@ -560,8 +626,8 @@ int Sandbox::getTrapId(Sandbox::TrapFnc fnc, const void *aux) {
     if (!traps_) {
       traps_ = new Traps();
     }
-    int id   = traps_->size() + 1;
-    if (id > static_cast<int>(SECCOMP_RET_DATA)) {
+    Traps::size_type id = traps_->size() + 1;
+    if (id > SECCOMP_RET_DATA) {
       // In practice, this is pretty much impossible to trigger, as there
       // are other kernel limitations that restrict overall BPF program sizes.
       die("Too many SECCOMP_RET_TRAP callback instances");
diff --git a/sandbox/linux/seccomp-bpf/sandbox_bpf.h b/sandbox/linux/seccomp-bpf/sandbox_bpf.h
index 3a297e9..de7fa50 100644
--- a/sandbox/linux/seccomp-bpf/sandbox_bpf.h
+++ b/sandbox/linux/seccomp-bpf/sandbox_bpf.h
@@ -74,6 +74,11 @@
 #define SYS_SECCOMP                   1
 #endif
 
+// Impose some reasonable maximum BPF program size. Realistically, the
+// kernel probably has much lower limits. But by limiting to less than
+// 30 bits, we can ease requirements on some of our data types.
+#define SECCOMP_MAX_PROGRAM_SIZE (1<<30)
+
 #if defined(__i386__)
 #define MIN_SYSCALL  0u
 #define MAX_SYSCALL  1024u
@@ -326,7 +331,14 @@ class Sandbox {
     uint32_t  from, to;
     ErrorCode err;
   };
+  struct FixUp {
+    FixUp(unsigned int a, bool j) :
+      jt(j), addr(a) { }
+    bool     jt:1;
+    unsigned addr:31;
+  };
   typedef std::vector<Range> Ranges;
+  typedef std::map<uint32_t, std::vector<FixUp> > RetInsns;
   typedef std::vector<struct sock_filter> Program;
   typedef std::vector<ErrorCode> Traps;
   typedef std::map<std::pair<TrapFnc, const void *>, int> TrapIds;
@@ -339,7 +351,10 @@ class Sandbox {
                                       EvaluateArguments argumentEvaluator);
   static void      installFilter();
   static void      findRanges(Ranges *ranges);
-  static void      rangesToBPF(Program *program, const Ranges& ranges);
+  static void      emitJumpStatements(Program *program, RetInsns *rets,
+                                      Ranges::const_iterator start,
+                                      Ranges::const_iterator stop);
+  static void      emitReturnStatements(Program *prog, const RetInsns& rets);
   static void      sigSys(int nr, siginfo_t *info, void *void_context);
   static intptr_t  bpfFailure(const struct arch_seccomp_data& data, void *aux);
   static int       getTrapId(TrapFnc fnc, const void *aux);
diff --git a/sandbox/linux/seccomp-bpf/verifier.cc b/sandbox/linux/seccomp-bpf/verifier.cc
index 71b743c..52a385e 100644
--- a/sandbox/linux/seccomp-bpf/verifier.cc
+++ b/sandbox/linux/seccomp-bpf/verifier.cc
@@ -52,6 +52,10 @@ uint32_t Verifier::evaluateBPF(const std::vector<struct sock_filter>& program,
                                const struct arch_seccomp_data& data,
                                const char **err) {
   *err = NULL;
+  if (program.size() < 1 || program.size() >= SECCOMP_MAX_PROGRAM_SIZE) {
+    *err = "Invalid program length";
+    return 0;
+  }
   for (State state(program, data); !*err; ++state.ip) {
     if (state.ip >= program.size()) {
       *err = "Invalid instruction pointer in BPF program";