Home | History | Annotate | Download | only in seccomp-bpf 
      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_SECCOMP_BPF_CODEGEN_H__
      6 #define SANDBOX_LINUX_SECCOMP_BPF_CODEGEN_H__
      7 
      8 #include <map>
      9 #include <vector>
     10 
     11 #include "sandbox/linux/seccomp-bpf/sandbox_bpf.h"
     12 #include "sandbox/sandbox_export.h"
     13 
     14 namespace sandbox {
     15 struct BasicBlock;
     16 struct Instruction;
     17 
     18 typedef std::vector<Instruction*> Instructions;
     19 typedef std::vector<BasicBlock*> BasicBlocks;
     20 typedef std::map<const Instruction*, int> BranchTargets;
     21 typedef std::map<const Instruction*, BasicBlock*> TargetsToBlocks;
     22 typedef std::map<const BasicBlock*, int> IncomingBranches;
     23 
     24 // The code generator instantiates a basic compiler that can convert a
     25 // graph of BPF instructions into a well-formed stream of BPF instructions.
     26 // Most notably, it ensures that jumps are always forward and don't exceed
     27 // the limit of 255 instructions imposed by the instruction set.
     28 //
     29 // Callers would typically create a new CodeGen object and then use it to
     30 // build a DAG of Instructions. They'll eventually call Compile() to convert
     31 // this DAG to a SandboxBPF::Program.
     32 //
     33 //   CodeGen gen;
     34 //   Instruction *allow, *branch, *dag;
     35 //
     36 //   allow =
     37 //     gen.MakeInstruction(BPF_RET+BPF_K,
     38 //                         ErrorCode(ErrorCode::ERR_ALLOWED).err()));
     39 //   branch =
     40 //     gen.MakeInstruction(BPF_JMP+BPF_EQ+BPF_K, __NR_getpid,
     41 //                         Trap(GetPidHandler, NULL), allow);
     42 //   dag =
     43 //     gen.MakeInstruction(BPF_LD+BPF_W+BPF_ABS,
     44 //                         offsetof(struct arch_seccomp_data, nr), branch);
     45 //
     46 //   // Simplified code follows; in practice, it is important to avoid calling
     47 //   // any C++ destructors after starting the sandbox.
     48 //   SandboxBPF::Program program;
     49 //   gen.Compile(dag, program);
     50 //   const struct sock_fprog prog = {
     51 //     static_cast<unsigned short>(program->size()), &program[0] };
     52 //   prctl(PR_SET_SECCOMP, SECCOMP_MODE_FILTER, &prog);
     53 //
     54 class SANDBOX_EXPORT CodeGen {
     55  public:
     56   CodeGen();
     57   ~CodeGen();
     58 
     59   // This is a helper method that can be used for debugging purposes. It is
     60   // not normally called.
     61   static void PrintProgram(const SandboxBPF::Program& program);
     62 
     63   // Create a new instruction. Instructions form a DAG. The instruction objects
     64   // are owned by the CodeGen object. They do not need to be explicitly
     65   // deleted.
     66   // For details on the possible parameters refer to <linux/filter.h>
     67   Instruction* MakeInstruction(uint16_t code,
     68                                uint32_t k,
     69                                Instruction* next = NULL);
     70   Instruction* MakeInstruction(uint16_t code,
     71                                uint32_t k,
     72                                Instruction* jt,
     73                                Instruction* jf);
     74 
     75   // Traverse the graph of instructions and visit each instruction once.
     76   // Traversal order is implementation-defined. It is acceptable to make
     77   // changes to the graph from within the callback function. These changes
     78   // do not affect traversal.
     79   // The "fnc" function gets called with both the instruction and the opaque
     80   // "aux" pointer.
     81   void Traverse(Instruction*, void (*fnc)(Instruction*, void* aux), void* aux);
     82 
     83   // Compiles the graph of instructions into a BPF program that can be passed
     84   // to the kernel. Please note that this function modifies the graph in place
     85   // and must therefore only be called once per graph.
     86   void Compile(Instruction* instructions, SandboxBPF::Program* program);
     87 
     88  private:
     89   friend class CodeGenUnittestHelper;
     90 
     91   // Find all the instructions that are the target of BPF_JMPs.
     92   void FindBranchTargets(const Instruction& instructions,
     93                          BranchTargets* branch_targets);
     94 
     95   // Combine instructions between "head" and "tail" into a new basic block.
     96   // Basic blocks are defined as sequences of instructions whose only branch
     97   // target is the very first instruction; furthermore, any BPF_JMP or BPF_RET
     98   // instruction must be at the very end of the basic block.
     99   BasicBlock* MakeBasicBlock(Instruction* head, Instruction* tail);
    100 
    101   // Creates a basic block and adds it to "basic_blocks"; sets "first_block"
    102   // if it is still NULL.
    103   void AddBasicBlock(Instruction* head,
    104                      Instruction* tail,
    105                      const BranchTargets& branch_targets,
    106                      TargetsToBlocks* basic_blocks,
    107                      BasicBlock** first_block);
    108 
    109   // Cuts the DAG of instructions into basic blocks.
    110   BasicBlock* CutGraphIntoBasicBlocks(Instruction* instructions,
    111                                       const BranchTargets& branch_targets,
    112                                       TargetsToBlocks* blocks);
    113 
    114   // Find common tail sequences of basic blocks and coalesce them.
    115   void MergeTails(TargetsToBlocks* blocks);
    116 
    117   // For each basic block, compute the number of incoming branches.
    118   void ComputeIncomingBranches(BasicBlock* block,
    119                                const TargetsToBlocks& targets_to_blocks,
    120                                IncomingBranches* incoming_branches);
    121 
    122   // Topologically sort the basic blocks so that all jumps are forward jumps.
    123   // This is a requirement for any well-formed BPF program.
    124   void TopoSortBasicBlocks(BasicBlock* first_block,
    125                            const TargetsToBlocks& blocks,
    126                            BasicBlocks* basic_blocks);
    127 
    128   // Convert jt_ptr_ and jf_ptr_ fields in BPF_JMP instructions to valid
    129   // jt_ and jf_ jump offsets. This can result in BPF_JA instructions being
    130   // inserted, if we need to jump over more than 256 instructions.
    131   void ComputeRelativeJumps(BasicBlocks* basic_blocks,
    132                             const TargetsToBlocks& targets_to_blocks);
    133 
    134   // Concatenate instructions from all basic blocks into a BPF program that
    135   // can be passed to the kernel.
    136   void ConcatenateBasicBlocks(const BasicBlocks&, SandboxBPF::Program* program);
    137 
    138   // We stick all instructions and basic blocks into pools that get destroyed
    139   // when the CodeGen object is destroyed. This way, we neither need to worry
    140   // about explicitly managing ownership, nor do we need to worry about using
    141   // smart pointers in the presence of circular references.
    142   Instructions instructions_;
    143   BasicBlocks basic_blocks_;
    144 
    145   // Compile() must only ever be called once as it makes destructive changes
    146   // to the DAG.
    147   bool compiled_;
    148 };
    149 
    150 }  // namespace sandbox
    151 
    152 #endif  // SANDBOX_LINUX_SECCOMP_BPF_CODEGEN_H__
    153