Home | History | Annotate | Download | only in bpf_dsl 
      1 // Copyright (c) 2012 The Chromium Authors. All rights reserved.
      2 // Use of this source code is governed by a BSD-style license that can be
      3 // found in the LICENSE file.
      4 
      5 #ifndef SANDBOX_LINUX_BPF_DSL_CODEGEN_H__
      6 #define SANDBOX_LINUX_BPF_DSL_CODEGEN_H__
      7 
      8 #include <stddef.h>
      9 #include <stdint.h>
     10 
     11 #include <map>
     12 #include <tuple>
     13 #include <vector>
     14 
     15 #include "base/macros.h"
     16 #include "sandbox/sandbox_export.h"
     17 
     18 struct sock_filter;
     19 
     20 namespace sandbox {
     21 
     22 // The code generator implements a basic assembler that can convert a
     23 // graph of BPF instructions into a well-formed array of BPF
     24 // instructions. Most notably, it ensures that jumps are always
     25 // forward and don't exceed the limit of 255 instructions imposed by
     26 // the instruction set.
     27 //
     28 // Callers would typically create a new CodeGen object and then use it
     29 // to build a DAG of instruction nodes. They'll eventually call
     30 // Compile() to convert this DAG to a Program.
     31 //
     32 //   CodeGen gen;
     33 //   CodeGen::Node allow, branch, dag;
     34 //
     35 //   allow =
     36 //     gen.MakeInstruction(BPF_RET+BPF_K,
     37 //                         ErrorCode(ErrorCode::ERR_ALLOWED).err()));
     38 //   branch =
     39 //     gen.MakeInstruction(BPF_JMP+BPF_EQ+BPF_K, __NR_getpid,
     40 //                         Trap(GetPidHandler, NULL), allow);
     41 //   dag =
     42 //     gen.MakeInstruction(BPF_LD+BPF_W+BPF_ABS,
     43 //                         offsetof(struct arch_seccomp_data, nr), branch);
     44 //
     45 //   // Simplified code follows; in practice, it is important to avoid calling
     46 //   // any C++ destructors after starting the sandbox.
     47 //   CodeGen::Program program = gen.Compile(dag);
     48 //   const struct sock_fprog prog = {
     49 //     static_cast<unsigned short>(program.size()), &program[0] };
     50 //   prctl(PR_SET_SECCOMP, SECCOMP_MODE_FILTER, &prog);
     51 //
     52 class SANDBOX_EXPORT CodeGen {
     53  public:
     54   // A vector of BPF instructions that need to be installed as a filter
     55   // program in the kernel.
     56   typedef std::vector<struct sock_filter> Program;
     57 
     58   // Node represents a node within the instruction DAG being compiled.
     59   using Node = Program::size_type;
     60 
     61   // kNullNode represents the "null" node; i.e., the reserved node
     62   // value guaranteed to not equal any actual nodes.
     63   static const Node kNullNode = -1;
     64 
     65   CodeGen();
     66   ~CodeGen();
     67 
     68   // MakeInstruction creates a node representing the specified
     69   // instruction, or returns and existing equivalent node if one
     70   // exists. For details on the possible parameters refer to
     71   // https://www.kernel.org/doc/Documentation/networking/filter.txt.
     72   // TODO(mdempsky): Reconsider using default arguments here.
     73   Node MakeInstruction(uint16_t code,
     74                        uint32_t k,
     75                        Node jt = kNullNode,
     76                        Node jf = kNullNode);
     77 
     78   // Compile linearizes the instruction DAG rooted at |head| into a
     79   // program that can be executed by a BPF virtual machine.
     80   Program Compile(Node head);
     81 
     82  private:
     83   using MemoKey = std::tuple<uint16_t, uint32_t, Node, Node>;
     84 
     85   // AppendInstruction adds a new instruction, ensuring that |jt| and
     86   // |jf| are within range as necessary for |code|.
     87   Node AppendInstruction(uint16_t code, uint32_t k, Node jt, Node jf);
     88 
     89   // WithinRange returns a node equivalent to |next| that is at most
     90   // |range| instructions away from the (logical) beginning of the
     91   // program.
     92   Node WithinRange(Node next, size_t range);
     93 
     94   // Append appends a new instruction to the physical end (i.e.,
     95   // logical beginning) of |program_|.
     96   Node Append(uint16_t code, uint32_t k, size_t jt, size_t jf);
     97 
     98   // Offset returns how many instructions exist in |program_| after |target|.
     99   size_t Offset(Node target) const;
    100 
    101   // NOTE: program_ is the compiled program in *reverse*, so that
    102   // indices remain stable as we add instructions.
    103   Program program_;
    104 
    105   // equivalent_ stores the most recent semantically-equivalent node for each
    106   // instruction in program_. A node is defined as semantically-equivalent to N
    107   // if it has the same instruction code and constant as N and its successor
    108   // nodes (if any) are semantically-equivalent to N's successor nodes, or
    109   // if it's an unconditional jump to a node semantically-equivalent to N.
    110   std::vector<Node> equivalent_;
    111 
    112   std::map<MemoKey, Node> memos_;
    113 
    114   DISALLOW_COPY_AND_ASSIGN(CodeGen);
    115 };
    116 
    117 }  // namespace sandbox
    118 
    119 #endif  // SANDBOX_LINUX_BPF_DSL_CODEGEN_H__
    120