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 14namespace sandbox { 15struct BasicBlock; 16struct Instruction; 17 18typedef std::vector<Instruction*> Instructions; 19typedef std::vector<BasicBlock*> BasicBlocks; 20typedef std::map<const Instruction*, int> BranchTargets; 21typedef std::map<const Instruction*, BasicBlock*> TargetsToBlocks; 22typedef 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// 54class 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