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__ 161