sandbox/linux/seccomp-bpf/codegen.h

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