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 17 namespace playground2 { 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 Sandbox::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 // Sandbox::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 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 Sandbox::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, uint32_t k, 70 Instruction *next = NULL); 71 Instruction *MakeInstruction(uint16_t code, const ErrorCode& err); 72 Instruction *MakeInstruction(uint16_t code, uint32_t k, 73 Instruction *jt, Instruction *jf); 74 75 // Join two (sequences of) instructions. This is useful, if the "next" 76 // parameter had not originally been given in the call to MakeInstruction(), 77 // or if a (conditional) jump still has an unsatisfied target. 78 void JoinInstructions(Instruction *head, Instruction *tail); 79 80 // Traverse the graph of instructions and visit each instruction once. 81 // Traversal order is implementation-defined. It is acceptable to make 82 // changes to the graph from within the callback function. These changes 83 // do not affect traversal. 84 // The "fnc" function gets called with both the instruction and the opaque 85 // "aux" pointer. 86 void Traverse(Instruction *, void (*fnc)(Instruction *, void *aux), 87 void *aux); 88 89 // Compiles the graph of instructions into a BPF program that can be passed 90 // to the kernel. Please note that this function modifies the graph in place 91 // and must therefore only be called once per graph. 92 void Compile(Instruction *instructions, Sandbox::Program *program); 93 94 private: 95 friend class CodeGenUnittestHelper; 96 97 // Find all the instructions that are the target of BPF_JMPs. 98 void FindBranchTargets(const Instruction& instructions, 99 BranchTargets *branch_targets); 100 101 // Combine instructions between "head" and "tail" into a new basic block. 102 // Basic blocks are defined as sequences of instructions whose only branch 103 // target is the very first instruction; furthermore, any BPF_JMP or BPF_RET 104 // instruction must be at the very end of the basic block. 105 BasicBlock *MakeBasicBlock(Instruction *head, Instruction *tail); 106 107 // Creates a basic block and adds it to "basic_blocks"; sets "first_block" 108 // if it is still NULL. 109 void AddBasicBlock(Instruction *head, Instruction *tail, 110 const BranchTargets& branch_targets, 111 TargetsToBlocks *basic_blocks, BasicBlock **first_block); 112 113 // Cuts the DAG of instructions into basic blocks. 114 BasicBlock *CutGraphIntoBasicBlocks(Instruction *instructions, 115 const BranchTargets& branch_targets, 116 TargetsToBlocks *blocks); 117 118 // Find common tail sequences of basic blocks and coalesce them. 119 void MergeTails(TargetsToBlocks *blocks); 120 121 // For each basic block, compute the number of incoming branches. 122 void ComputeIncomingBranches(BasicBlock *block, 123 const TargetsToBlocks& targets_to_blocks, 124 IncomingBranches *incoming_branches); 125 126 // Topologically sort the basic blocks so that all jumps are forward jumps. 127 // This is a requirement for any well-formed BPF program. 128 void TopoSortBasicBlocks(BasicBlock *first_block, 129 const TargetsToBlocks& blocks, 130 BasicBlocks *basic_blocks); 131 132 // Convert jt_ptr_ and jf_ptr_ fields in BPF_JMP instructions to valid 133 // jt_ and jf_ jump offsets. This can result in BPF_JA instructions being 134 // inserted, if we need to jump over more than 256 instructions. 135 void ComputeRelativeJumps(BasicBlocks *basic_blocks, 136 const TargetsToBlocks& targets_to_blocks); 137 138 // Concatenate instructions from all basic blocks into a BPF program that 139 // can be passed to the kernel. 140 void ConcatenateBasicBlocks(const BasicBlocks&, Sandbox::Program *program); 141 142 // We stick all instructions and basic blocks into pools that get destroyed 143 // when the CodeGen object is destroyed. This way, we neither need to worry 144 // about explicitly managing ownership, nor do we need to worry about using 145 // smart pointers in the presence of circular references. 146 Instructions instructions_; 147 BasicBlocks basic_blocks_; 148 149 // Compile() must only ever be called once as it makes destructive changes 150 // to the DAG. 151 bool compiled_; 152 }; 153 154 } // namespace 155 156 #endif // SANDBOX_LINUX_SECCOMP_BPF_CODEGEN_H__ 157
