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