| OLD | NEW |
| 1 // Copyright (c) 2012 The Chromium Authors. All rights reserved. | 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 | 2 // Use of this source code is governed by a BSD-style license that can be |
| 3 // found in the LICENSE file. | 3 // found in the LICENSE file. |
| 4 | 4 |
| 5 #ifndef SANDBOX_LINUX_SECCOMP_BPF_CODEGEN_H__ | 5 #ifndef SANDBOX_LINUX_SECCOMP_BPF_CODEGEN_H__ |
| 6 #define SANDBOX_LINUX_SECCOMP_BPF_CODEGEN_H__ | 6 #define SANDBOX_LINUX_SECCOMP_BPF_CODEGEN_H__ |
| 7 | 7 |
| 8 #include <map> | 8 #include <map> |
| 9 #include <set> | 9 #include <set> |
| 10 #include <vector> | 10 #include <vector> |
| 11 | 11 |
| 12 #include "sandbox/linux/seccomp-bpf/basicblock.h" | 12 #include "sandbox/linux/seccomp-bpf/basicblock.h" |
| 13 #include "sandbox/linux/seccomp-bpf/instruction.h" | 13 #include "sandbox/linux/seccomp-bpf/instruction.h" |
| 14 #include "sandbox/linux/seccomp-bpf/sandbox_bpf.h" | 14 #include "sandbox/linux/seccomp-bpf/sandbox_bpf.h" |
| 15 | 15 |
| 16 | |
| 17 namespace playground2 { | 16 namespace playground2 { |
| 18 | 17 |
| 19 typedef std::vector<Instruction *> Instructions; | 18 typedef std::vector<Instruction*> Instructions; |
| 20 typedef std::vector<BasicBlock *> BasicBlocks; | 19 typedef std::vector<BasicBlock*> BasicBlocks; |
| 21 typedef std::map<const Instruction *, int> BranchTargets; | 20 typedef std::map<const Instruction*, int> BranchTargets; |
| 22 typedef std::map<const Instruction *, BasicBlock *> TargetsToBlocks; | 21 typedef std::map<const Instruction*, BasicBlock*> TargetsToBlocks; |
| 23 typedef std::map<const BasicBlock *, int> IncomingBranches; | 22 typedef std::map<const BasicBlock*, int> IncomingBranches; |
| 24 | 23 |
| 25 // The code generator instantiates a basic compiler that can convert a | 24 // The code generator instantiates a basic compiler that can convert a |
| 26 // graph of BPF instructions into a well-formed stream of BPF instructions. | 25 // 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 | 26 // Most notably, it ensures that jumps are always forward and don't exceed |
| 28 // the limit of 255 instructions imposed by the instruction set. | 27 // the limit of 255 instructions imposed by the instruction set. |
| 29 // | 28 // |
| 30 // Callers would typically create a new CodeGen object and then use it to | 29 // 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 | 30 // build a DAG of Instructions. They'll eventually call Compile() to convert |
| 32 // this DAG to a Sandbox::Program. | 31 // this DAG to a Sandbox::Program. |
| 33 // | 32 // |
| (...skipping 25 matching lines...) Expand all Loading... |
| 59 ~CodeGen(); | 58 ~CodeGen(); |
| 60 | 59 |
| 61 // This is a helper method that can be used for debugging purposes. It is | 60 // This is a helper method that can be used for debugging purposes. It is |
| 62 // not normally called. | 61 // not normally called. |
| 63 static void PrintProgram(const Sandbox::Program& program); | 62 static void PrintProgram(const Sandbox::Program& program); |
| 64 | 63 |
| 65 // Create a new instruction. Instructions form a DAG. The instruction objects | 64 // 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 | 65 // are owned by the CodeGen object. They do not need to be explicitly |
| 67 // deleted. | 66 // deleted. |
| 68 // For details on the possible parameters refer to <linux/filter.h> | 67 // For details on the possible parameters refer to <linux/filter.h> |
| 69 Instruction *MakeInstruction(uint16_t code, uint32_t k, | 68 Instruction* MakeInstruction(uint16_t code, |
| 70 Instruction *next = NULL); | 69 uint32_t k, |
| 71 Instruction *MakeInstruction(uint16_t code, const ErrorCode& err); | 70 Instruction* next = NULL); |
| 72 Instruction *MakeInstruction(uint16_t code, uint32_t k, | 71 Instruction* MakeInstruction(uint16_t code, const ErrorCode& err); |
| 73 Instruction *jt, Instruction *jf); | 72 Instruction* MakeInstruction(uint16_t code, |
| 73 uint32_t k, |
| 74 Instruction* jt, |
| 75 Instruction* jf); |
| 74 | 76 |
| 75 // Join two (sequences of) instructions. This is useful, if the "next" | 77 // Join two (sequences of) instructions. This is useful, if the "next" |
| 76 // parameter had not originally been given in the call to MakeInstruction(), | 78 // parameter had not originally been given in the call to MakeInstruction(), |
| 77 // or if a (conditional) jump still has an unsatisfied target. | 79 // or if a (conditional) jump still has an unsatisfied target. |
| 78 void JoinInstructions(Instruction *head, Instruction *tail); | 80 void JoinInstructions(Instruction* head, Instruction* tail); |
| 79 | 81 |
| 80 // Traverse the graph of instructions and visit each instruction once. | 82 // Traverse the graph of instructions and visit each instruction once. |
| 81 // Traversal order is implementation-defined. It is acceptable to make | 83 // Traversal order is implementation-defined. It is acceptable to make |
| 82 // changes to the graph from within the callback function. These changes | 84 // changes to the graph from within the callback function. These changes |
| 83 // do not affect traversal. | 85 // do not affect traversal. |
| 84 // The "fnc" function gets called with both the instruction and the opaque | 86 // The "fnc" function gets called with both the instruction and the opaque |
| 85 // "aux" pointer. | 87 // "aux" pointer. |
| 86 void Traverse(Instruction *, void (*fnc)(Instruction *, void *aux), | 88 void Traverse(Instruction*, void (*fnc)(Instruction*, void* aux), void* aux); |
| 87 void *aux); | |
| 88 | 89 |
| 89 // Compiles the graph of instructions into a BPF program that can be passed | 90 // 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 // to the kernel. Please note that this function modifies the graph in place |
| 91 // and must therefore only be called once per graph. | 92 // and must therefore only be called once per graph. |
| 92 void Compile(Instruction *instructions, Sandbox::Program *program); | 93 void Compile(Instruction* instructions, Sandbox::Program* program); |
| 93 | 94 |
| 94 private: | 95 private: |
| 95 friend class CodeGenUnittestHelper; | 96 friend class CodeGenUnittestHelper; |
| 96 | 97 |
| 97 // Find all the instructions that are the target of BPF_JMPs. | 98 // Find all the instructions that are the target of BPF_JMPs. |
| 98 void FindBranchTargets(const Instruction& instructions, | 99 void FindBranchTargets(const Instruction& instructions, |
| 99 BranchTargets *branch_targets); | 100 BranchTargets* branch_targets); |
| 100 | 101 |
| 101 // Combine instructions between "head" and "tail" into a new basic block. | 102 // Combine instructions between "head" and "tail" into a new basic block. |
| 102 // Basic blocks are defined as sequences of instructions whose only branch | 103 // 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 // 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 // instruction must be at the very end of the basic block. |
| 105 BasicBlock *MakeBasicBlock(Instruction *head, Instruction *tail); | 106 BasicBlock* MakeBasicBlock(Instruction* head, Instruction* tail); |
| 106 | 107 |
| 107 // Creates a basic block and adds it to "basic_blocks"; sets "first_block" | 108 // Creates a basic block and adds it to "basic_blocks"; sets "first_block" |
| 108 // if it is still NULL. | 109 // if it is still NULL. |
| 109 void AddBasicBlock(Instruction *head, Instruction *tail, | 110 void AddBasicBlock(Instruction* head, |
| 111 Instruction* tail, |
| 110 const BranchTargets& branch_targets, | 112 const BranchTargets& branch_targets, |
| 111 TargetsToBlocks *basic_blocks, BasicBlock **first_block); | 113 TargetsToBlocks* basic_blocks, |
| 114 BasicBlock** first_block); |
| 112 | 115 |
| 113 // Cuts the DAG of instructions into basic blocks. | 116 // Cuts the DAG of instructions into basic blocks. |
| 114 BasicBlock *CutGraphIntoBasicBlocks(Instruction *instructions, | 117 BasicBlock* CutGraphIntoBasicBlocks(Instruction* instructions, |
| 115 const BranchTargets& branch_targets, | 118 const BranchTargets& branch_targets, |
| 116 TargetsToBlocks *blocks); | 119 TargetsToBlocks* blocks); |
| 117 | 120 |
| 118 // Find common tail sequences of basic blocks and coalesce them. | 121 // Find common tail sequences of basic blocks and coalesce them. |
| 119 void MergeTails(TargetsToBlocks *blocks); | 122 void MergeTails(TargetsToBlocks* blocks); |
| 120 | 123 |
| 121 // For each basic block, compute the number of incoming branches. | 124 // For each basic block, compute the number of incoming branches. |
| 122 void ComputeIncomingBranches(BasicBlock *block, | 125 void ComputeIncomingBranches(BasicBlock* block, |
| 123 const TargetsToBlocks& targets_to_blocks, | 126 const TargetsToBlocks& targets_to_blocks, |
| 124 IncomingBranches *incoming_branches); | 127 IncomingBranches* incoming_branches); |
| 125 | 128 |
| 126 // Topologically sort the basic blocks so that all jumps are forward jumps. | 129 // Topologically sort the basic blocks so that all jumps are forward jumps. |
| 127 // This is a requirement for any well-formed BPF program. | 130 // This is a requirement for any well-formed BPF program. |
| 128 void TopoSortBasicBlocks(BasicBlock *first_block, | 131 void TopoSortBasicBlocks(BasicBlock* first_block, |
| 129 const TargetsToBlocks& blocks, | 132 const TargetsToBlocks& blocks, |
| 130 BasicBlocks *basic_blocks); | 133 BasicBlocks* basic_blocks); |
| 131 | 134 |
| 132 // Convert jt_ptr_ and jf_ptr_ fields in BPF_JMP instructions to valid | 135 // 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 | 136 // 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. | 137 // inserted, if we need to jump over more than 256 instructions. |
| 135 void ComputeRelativeJumps(BasicBlocks *basic_blocks, | 138 void ComputeRelativeJumps(BasicBlocks* basic_blocks, |
| 136 const TargetsToBlocks& targets_to_blocks); | 139 const TargetsToBlocks& targets_to_blocks); |
| 137 | 140 |
| 138 // Concatenate instructions from all basic blocks into a BPF program that | 141 // Concatenate instructions from all basic blocks into a BPF program that |
| 139 // can be passed to the kernel. | 142 // can be passed to the kernel. |
| 140 void ConcatenateBasicBlocks(const BasicBlocks&, Sandbox::Program *program); | 143 void ConcatenateBasicBlocks(const BasicBlocks&, Sandbox::Program* program); |
| 141 | 144 |
| 142 // We stick all instructions and basic blocks into pools that get destroyed | 145 // 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 | 146 // 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 | 147 // about explicitly managing ownership, nor do we need to worry about using |
| 145 // smart pointers in the presence of circular references. | 148 // smart pointers in the presence of circular references. |
| 146 Instructions instructions_; | 149 Instructions instructions_; |
| 147 BasicBlocks basic_blocks_; | 150 BasicBlocks basic_blocks_; |
| 148 | 151 |
| 149 // Compile() must only ever be called once as it makes destructive changes | 152 // Compile() must only ever be called once as it makes destructive changes |
| 150 // to the DAG. | 153 // to the DAG. |
| 151 bool compiled_; | 154 bool compiled_; |
| 152 }; | 155 }; |
| 153 | 156 |
| 154 } // namespace | 157 } // namespace |
| 155 | 158 |
| 156 #endif // SANDBOX_LINUX_SECCOMP_BPF_CODEGEN_H__ | 159 #endif // SANDBOX_LINUX_SECCOMP_BPF_CODEGEN_H__ |
| OLD | NEW |