SANDBOX-BPF: Initial version of the updated code generator.

New code generator that is more generic and can automatically reorder
instructions to meet the constraints of BPF programs.

Previously, we were very careful to emit instructions in just the
right order so that there would only ever be forward jumps. As we add
more features to our BPF programs, this code is getting fragile.

So, instead, we now use standard compiler techniques; we first build a
graph of all the instructions, then we split them into basic blocks,
we perform some basic optimizations (at the moment, this is just the
merging of common tails of instructions), we sort the basic blocks
topologically, and then we reassemble all the blocks into a BPF
program.

There should be no functional change, but this code is the
pre-requisite for upcoming changes.


BUG=130662
TEST=sandbox_linux_unittests

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

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

1 files changed, 11 insertions, 12 deletions

diff --git a/sandbox/linux/seccomp-bpf/sandbox_bpf.h b/sandbox/linux/seccomp-bpf/sandbox_bpf.h
index 8cc3b7b..d0764dd 100644
--- a/sandbox/linux/seccomp-bpf/sandbox_bpf.h
+++ b/sandbox/linux/seccomp-bpf/sandbox_bpf.h
@@ -31,6 +31,7 @@
 #include <sys/types.h>
 #include <sys/uio.h>
 #include <sys/wait.h>
+#include <time.h>
 #include <unistd.h>
 
 #include <algorithm>
@@ -184,6 +185,10 @@ struct arch_sigsys {
   unsigned int arch;
 };
 
+class CodeGen;
+class SandboxUnittestHelper;
+struct Instruction;
+
 class Sandbox {
  public:
   enum SandboxStatus {
@@ -271,9 +276,12 @@ class Sandbox {
 
  private:
   friend class ErrorCode;
+  friend class CodeGen;
+  friend class SandboxUnittestHelper;
   friend class Util;
   friend class Verifier;
 
+  typedef std::vector<struct sock_filter> Program;
 
   struct Range {
     Range(uint32_t f, uint32_t t, const ErrorCode& e) :
@@ -284,15 +292,7 @@ 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::map<uint32_t, ErrorCode> ErrMap;
   typedef std::vector<ErrorCode> Traps;
   typedef std::map<std::pair<TrapFnc, const void *>, int> TrapIds;
@@ -316,10 +316,9 @@ class Sandbox {
                                       EvaluateArguments argumentEvaluator);
   static void      installFilter(bool quiet);
   static void      findRanges(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 Instruction *assembleJumpTable(CodeGen *gen,
+                                        Ranges::const_iterator start,
+                                        Ranges::const_iterator stop);
   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);