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 |