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 #include <errno.h> | 5 #include <errno.h> |
6 | 6 |
7 #include <algorithm> | 7 #include <algorithm> |
8 #include <set> | 8 #include <set> |
9 #include <vector> | 9 #include <vector> |
10 | 10 |
(...skipping 23 matching lines...) Expand all Loading... |
34 return CodeGen::CutGraphIntoBasicBlocks(insns, branch_targets, blocks); | 34 return CodeGen::CutGraphIntoBasicBlocks(insns, branch_targets, blocks); |
35 } | 35 } |
36 | 36 |
37 void MergeTails(TargetsToBlocks* blocks) { CodeGen::MergeTails(blocks); } | 37 void MergeTails(TargetsToBlocks* blocks) { CodeGen::MergeTails(blocks); } |
38 }; | 38 }; |
39 | 39 |
40 enum { NO_FLAGS = 0x0000, HAS_MERGEABLE_TAILS = 0x0001, }; | 40 enum { NO_FLAGS = 0x0000, HAS_MERGEABLE_TAILS = 0x0001, }; |
41 | 41 |
42 Instruction* SampleProgramOneInstruction(CodeGen* codegen, int* flags) { | 42 Instruction* SampleProgramOneInstruction(CodeGen* codegen, int* flags) { |
43 // Create the most basic valid BPF program: | 43 // Create the most basic valid BPF program: |
44 // RET ERR_ALLOWED | 44 // RET 0 |
45 *flags = NO_FLAGS; | 45 *flags = NO_FLAGS; |
46 return codegen->MakeInstruction(BPF_RET + BPF_K, | 46 return codegen->MakeInstruction(BPF_RET + BPF_K, 0); |
47 ErrorCode(ErrorCode::ERR_ALLOWED)); | |
48 } | 47 } |
49 | 48 |
50 Instruction* SampleProgramSimpleBranch(CodeGen* codegen, int* flags) { | 49 Instruction* SampleProgramSimpleBranch(CodeGen* codegen, int* flags) { |
51 // Create a program with a single branch: | 50 // Create a program with a single branch: |
52 // JUMP if eq 42 then $0 else $1 | 51 // JUMP if eq 42 then $0 else $1 |
53 // 0: RET EPERM | 52 // 0: RET 1 |
54 // 1: RET ERR_ALLOWED | 53 // 1: RET 0 |
55 *flags = NO_FLAGS; | 54 *flags = NO_FLAGS; |
56 return codegen->MakeInstruction( | 55 return codegen->MakeInstruction( |
57 BPF_JMP + BPF_JEQ + BPF_K, | 56 BPF_JMP + BPF_JEQ + BPF_K, |
58 42, | 57 42, |
59 codegen->MakeInstruction(BPF_RET + BPF_K, ErrorCode(EPERM)), | 58 codegen->MakeInstruction(BPF_RET + BPF_K, 1), |
60 codegen->MakeInstruction(BPF_RET + BPF_K, | 59 codegen->MakeInstruction(BPF_RET + BPF_K, 0)); |
61 ErrorCode(ErrorCode::ERR_ALLOWED))); | |
62 } | 60 } |
63 | 61 |
64 Instruction* SampleProgramAtypicalBranch(CodeGen* codegen, int* flags) { | 62 Instruction* SampleProgramAtypicalBranch(CodeGen* codegen, int* flags) { |
65 // Create a program with a single branch: | 63 // Create a program with a single branch: |
66 // JUMP if eq 42 then $0 else $0 | 64 // JUMP if eq 42 then $0 else $0 |
67 // 0: RET ERR_ALLOWED | 65 // 0: RET 0 |
68 | 66 |
69 // N.B.: As the instructions in both sides of the branch are already | 67 // N.B.: As the instructions in both sides of the branch are already |
70 // the same object, we do not actually have any "mergeable" branches. | 68 // the same object, we do not actually have any "mergeable" branches. |
71 // This needs to be reflected in our choice of "flags". | 69 // This needs to be reflected in our choice of "flags". |
72 *flags = NO_FLAGS; | 70 *flags = NO_FLAGS; |
73 | 71 |
74 Instruction* ret = codegen->MakeInstruction( | 72 Instruction* ret = codegen->MakeInstruction( |
75 BPF_RET + BPF_K, ErrorCode(ErrorCode::ERR_ALLOWED)); | 73 BPF_RET + BPF_K, 0); |
76 return codegen->MakeInstruction(BPF_JMP + BPF_JEQ + BPF_K, 42, ret, ret); | 74 return codegen->MakeInstruction(BPF_JMP + BPF_JEQ + BPF_K, 42, ret, ret); |
77 } | 75 } |
78 | 76 |
79 Instruction* SampleProgramComplex(CodeGen* codegen, int* flags) { | 77 Instruction* SampleProgramComplex(CodeGen* codegen, int* flags) { |
80 // Creates a basic BPF program that we'll use to test some of the code: | 78 // Creates a basic BPF program that we'll use to test some of the code: |
81 // JUMP if eq 42 the $0 else $1 (insn6) | 79 // JUMP if eq 42 the $0 else $1 (insn6) |
82 // 0: LD 23 (insn5) | 80 // 0: LD 23 (insn5) |
83 // 1: JUMP if eq 42 then $2 else $4 (insn4) | 81 // 1: JUMP if eq 42 then $2 else $4 (insn4) |
84 // 2: JUMP to $3 (insn1) | 82 // 2: JUMP to $3 (insn1) |
85 // 3: LD 42 (insn0) | 83 // 3: LD 42 (insn0) |
86 // RET ErrorCode(42) (insn2) | 84 // RET 42 (insn2) |
87 // 4: LD 42 (insn3) | 85 // 4: LD 42 (insn3) |
88 // RET ErrorCode(42) (insn3+) | 86 // RET 42 (insn3+) |
89 *flags = HAS_MERGEABLE_TAILS; | 87 *flags = HAS_MERGEABLE_TAILS; |
90 | 88 |
91 Instruction* insn0 = codegen->MakeInstruction(BPF_LD + BPF_W + BPF_ABS, 42); | 89 Instruction* insn0 = codegen->MakeInstruction(BPF_LD + BPF_W + BPF_ABS, 42); |
92 SANDBOX_ASSERT(insn0); | 90 SANDBOX_ASSERT(insn0); |
93 SANDBOX_ASSERT(insn0->code == BPF_LD + BPF_W + BPF_ABS); | 91 SANDBOX_ASSERT(insn0->code == BPF_LD + BPF_W + BPF_ABS); |
94 SANDBOX_ASSERT(insn0->k == 42); | 92 SANDBOX_ASSERT(insn0->k == 42); |
95 SANDBOX_ASSERT(insn0->next == NULL); | 93 SANDBOX_ASSERT(insn0->next == NULL); |
96 | 94 |
97 Instruction* insn1 = codegen->MakeInstruction(BPF_JMP + BPF_JA, 0, insn0); | 95 Instruction* insn1 = codegen->MakeInstruction(BPF_JMP + BPF_JA, 0, insn0); |
98 SANDBOX_ASSERT(insn1); | 96 SANDBOX_ASSERT(insn1); |
99 SANDBOX_ASSERT(insn1->code == BPF_JMP + BPF_JA); | 97 SANDBOX_ASSERT(insn1->code == BPF_JMP + BPF_JA); |
100 SANDBOX_ASSERT(insn1->jt_ptr == insn0); | 98 SANDBOX_ASSERT(insn1->jt_ptr == insn0); |
101 | 99 |
102 Instruction* insn2 = codegen->MakeInstruction(BPF_RET + BPF_K, ErrorCode(42)); | 100 Instruction* insn2 = codegen->MakeInstruction(BPF_RET + BPF_K, 42); |
103 SANDBOX_ASSERT(insn2); | 101 SANDBOX_ASSERT(insn2); |
104 SANDBOX_ASSERT(insn2->code == BPF_RET + BPF_K); | 102 SANDBOX_ASSERT(insn2->code == BPF_RET + BPF_K); |
105 SANDBOX_ASSERT(insn2->next == NULL); | 103 SANDBOX_ASSERT(insn2->next == NULL); |
106 | 104 |
107 // We explicitly duplicate instructions so that MergeTails() can coalesce | 105 // We explicitly duplicate instructions so that MergeTails() can coalesce |
108 // them later. | 106 // them later. |
109 Instruction* insn3 = codegen->MakeInstruction( | 107 Instruction* insn3 = codegen->MakeInstruction( |
110 BPF_LD + BPF_W + BPF_ABS, | 108 BPF_LD + BPF_W + BPF_ABS, |
111 42, | 109 42, |
112 codegen->MakeInstruction(BPF_RET + BPF_K, ErrorCode(42))); | 110 codegen->MakeInstruction(BPF_RET + BPF_K, 42)); |
113 | 111 |
114 Instruction* insn4 = | 112 Instruction* insn4 = |
115 codegen->MakeInstruction(BPF_JMP + BPF_JEQ + BPF_K, 42, insn1, insn3); | 113 codegen->MakeInstruction(BPF_JMP + BPF_JEQ + BPF_K, 42, insn1, insn3); |
116 SANDBOX_ASSERT(insn4); | 114 SANDBOX_ASSERT(insn4); |
117 SANDBOX_ASSERT(insn4->code == BPF_JMP + BPF_JEQ + BPF_K); | 115 SANDBOX_ASSERT(insn4->code == BPF_JMP + BPF_JEQ + BPF_K); |
118 SANDBOX_ASSERT(insn4->k == 42); | 116 SANDBOX_ASSERT(insn4->k == 42); |
119 SANDBOX_ASSERT(insn4->jt_ptr == insn1); | 117 SANDBOX_ASSERT(insn4->jt_ptr == insn1); |
120 SANDBOX_ASSERT(insn4->jf_ptr == insn3); | 118 SANDBOX_ASSERT(insn4->jf_ptr == insn3); |
121 | 119 |
122 codegen->JoinInstructions(insn0, insn2); | 120 codegen->JoinInstructions(insn0, insn2); |
(...skipping 27 matching lines...) Expand all Loading... |
150 // Without the fix for this bug, this program should trigger the check in | 148 // Without the fix for this bug, this program should trigger the check in |
151 // CompileAndCompare: the serialized graphs from the program and its compiled | 149 // CompileAndCompare: the serialized graphs from the program and its compiled |
152 // version will differ. | 150 // version will differ. |
153 // | 151 // |
154 // 0) LOAD 1 // ??? | 152 // 0) LOAD 1 // ??? |
155 // 1) if A == 0x1; then JMP 2 else JMP 3 | 153 // 1) if A == 0x1; then JMP 2 else JMP 3 |
156 // 2) LOAD 0 // System call number | 154 // 2) LOAD 0 // System call number |
157 // 3) if A == 0x2; then JMP 4 else JMP 5 | 155 // 3) if A == 0x2; then JMP 4 else JMP 5 |
158 // 4) LOAD 0 // System call number | 156 // 4) LOAD 0 // System call number |
159 // 5) if A == 0x1; then JMP 6 else JMP 7 | 157 // 5) if A == 0x1; then JMP 6 else JMP 7 |
160 // 6) RET 0x50000 // errno = 0 | 158 // 6) RET 0 |
161 // 7) RET 0x50001 // errno = 1 | 159 // 7) RET 1 |
162 *flags = NO_FLAGS; | 160 *flags = NO_FLAGS; |
163 | 161 |
164 Instruction* i7 = codegen->MakeInstruction(BPF_RET, ErrorCode(1)); | 162 Instruction* i7 = codegen->MakeInstruction(BPF_RET + BPF_K, 1); |
165 Instruction* i6 = codegen->MakeInstruction(BPF_RET, ErrorCode(0)); | 163 Instruction* i6 = codegen->MakeInstruction(BPF_RET + BPF_K, 0); |
166 Instruction* i5 = | 164 Instruction* i5 = |
167 codegen->MakeInstruction(BPF_JMP + BPF_JEQ + BPF_K, 1, i6, i7); | 165 codegen->MakeInstruction(BPF_JMP + BPF_JEQ + BPF_K, 1, i6, i7); |
168 Instruction* i4 = codegen->MakeInstruction(BPF_LD + BPF_W + BPF_ABS, 0, i5); | 166 Instruction* i4 = codegen->MakeInstruction(BPF_LD + BPF_W + BPF_ABS, 0, i5); |
169 Instruction* i3 = | 167 Instruction* i3 = |
170 codegen->MakeInstruction(BPF_JMP + BPF_JEQ + BPF_K, 2, i4, i5); | 168 codegen->MakeInstruction(BPF_JMP + BPF_JEQ + BPF_K, 2, i4, i5); |
171 Instruction* i2 = codegen->MakeInstruction(BPF_LD + BPF_W + BPF_ABS, 0, i3); | 169 Instruction* i2 = codegen->MakeInstruction(BPF_LD + BPF_W + BPF_ABS, 0, i3); |
172 Instruction* i1 = | 170 Instruction* i1 = |
173 codegen->MakeInstruction(BPF_JMP + BPF_JEQ + BPF_K, 1, i2, i3); | 171 codegen->MakeInstruction(BPF_JMP + BPF_JEQ + BPF_K, 1, i2, i3); |
174 Instruction* i0 = codegen->MakeInstruction(BPF_LD + BPF_W + BPF_ABS, 1, i1); | 172 Instruction* i0 = codegen->MakeInstruction(BPF_LD + BPF_W + BPF_ABS, 1, i1); |
175 | 173 |
176 return i0; | 174 return i0; |
177 } | 175 } |
178 | 176 |
179 Instruction* SampleProgramConfusingTailsBasic(CodeGen* codegen, int* flags) { | 177 Instruction* SampleProgramConfusingTailsBasic(CodeGen* codegen, int* flags) { |
180 // Without the fix for https://crbug.com/351103/, (see | 178 // Without the fix for https://crbug.com/351103/, (see |
181 // SampleProgramConfusingTails()), this would generate a cyclic graph and | 179 // SampleProgramConfusingTails()), this would generate a cyclic graph and |
182 // crash as the two "LOAD 0" instructions would get merged. | 180 // crash as the two "LOAD 0" instructions would get merged. |
183 // | 181 // |
184 // 0) LOAD 1 // ??? | 182 // 0) LOAD 1 // ??? |
185 // 1) if A == 0x1; then JMP 2 else JMP 3 | 183 // 1) if A == 0x1; then JMP 2 else JMP 3 |
186 // 2) LOAD 0 // System call number | 184 // 2) LOAD 0 // System call number |
187 // 3) if A == 0x2; then JMP 4 else JMP 5 | 185 // 3) if A == 0x2; then JMP 4 else JMP 5 |
188 // 4) LOAD 0 // System call number | 186 // 4) LOAD 0 // System call number |
189 // 5) RET 0x50001 // errno = 1 | 187 // 5) RET 1 |
190 *flags = NO_FLAGS; | 188 *flags = NO_FLAGS; |
191 | 189 |
192 Instruction* i5 = codegen->MakeInstruction(BPF_RET, ErrorCode(1)); | 190 Instruction* i5 = codegen->MakeInstruction(BPF_RET + BPF_K, 1); |
193 Instruction* i4 = codegen->MakeInstruction(BPF_LD + BPF_W + BPF_ABS, 0, i5); | 191 Instruction* i4 = codegen->MakeInstruction(BPF_LD + BPF_W + BPF_ABS, 0, i5); |
194 Instruction* i3 = | 192 Instruction* i3 = |
195 codegen->MakeInstruction(BPF_JMP + BPF_JEQ + BPF_K, 2, i4, i5); | 193 codegen->MakeInstruction(BPF_JMP + BPF_JEQ + BPF_K, 2, i4, i5); |
196 Instruction* i2 = codegen->MakeInstruction(BPF_LD + BPF_W + BPF_ABS, 0, i3); | 194 Instruction* i2 = codegen->MakeInstruction(BPF_LD + BPF_W + BPF_ABS, 0, i3); |
197 Instruction* i1 = | 195 Instruction* i1 = |
198 codegen->MakeInstruction(BPF_JMP + BPF_JEQ + BPF_K, 1, i2, i3); | 196 codegen->MakeInstruction(BPF_JMP + BPF_JEQ + BPF_K, 1, i2, i3); |
199 Instruction* i0 = codegen->MakeInstruction(BPF_LD + BPF_W + BPF_ABS, 1, i1); | 197 Instruction* i0 = codegen->MakeInstruction(BPF_LD + BPF_W + BPF_ABS, 1, i1); |
200 | 198 |
201 return i0; | 199 return i0; |
202 } | 200 } |
203 | 201 |
204 Instruction* SampleProgramConfusingTailsMergeable(CodeGen* codegen, | 202 Instruction* SampleProgramConfusingTailsMergeable(CodeGen* codegen, |
205 int* flags) { | 203 int* flags) { |
206 // This is similar to SampleProgramConfusingTails(), except that | 204 // This is similar to SampleProgramConfusingTails(), except that |
207 // instructions 2 and 4 are now RET instructions. | 205 // instructions 2 and 4 are now RET instructions. |
208 // In PointerCompare(), this exercises the path where two blocks are of the | 206 // In PointerCompare(), this exercises the path where two blocks are of the |
209 // same length and identical and the last instruction is a JMP or RET, so the | 207 // same length and identical and the last instruction is a JMP or RET, so the |
210 // following blocks don't need to be looked at and the blocks are mergeable. | 208 // following blocks don't need to be looked at and the blocks are mergeable. |
211 // | 209 // |
212 // 0) LOAD 1 // ??? | 210 // 0) LOAD 1 // ??? |
213 // 1) if A == 0x1; then JMP 2 else JMP 3 | 211 // 1) if A == 0x1; then JMP 2 else JMP 3 |
214 // 2) RET 0x5002a // errno = 42 | 212 // 2) RET 42 |
215 // 3) if A == 0x2; then JMP 4 else JMP 5 | 213 // 3) if A == 0x2; then JMP 4 else JMP 5 |
216 // 4) RET 0x5002a // errno = 42 | 214 // 4) RET 42 |
217 // 5) if A == 0x1; then JMP 6 else JMP 7 | 215 // 5) if A == 0x1; then JMP 6 else JMP 7 |
218 // 6) RET 0x50000 // errno = 0 | 216 // 6) RET 0 |
219 // 7) RET 0x50001 // errno = 1 | 217 // 7) RET 1 |
220 *flags = HAS_MERGEABLE_TAILS; | 218 *flags = HAS_MERGEABLE_TAILS; |
221 | 219 |
222 Instruction* i7 = codegen->MakeInstruction(BPF_RET, ErrorCode(1)); | 220 Instruction* i7 = codegen->MakeInstruction(BPF_RET + BPF_K, 1); |
223 Instruction* i6 = codegen->MakeInstruction(BPF_RET, ErrorCode(0)); | 221 Instruction* i6 = codegen->MakeInstruction(BPF_RET + BPF_K, 0); |
224 Instruction* i5 = | 222 Instruction* i5 = |
225 codegen->MakeInstruction(BPF_JMP + BPF_JEQ + BPF_K, 1, i6, i7); | 223 codegen->MakeInstruction(BPF_JMP + BPF_JEQ + BPF_K, 1, i6, i7); |
226 Instruction* i4 = codegen->MakeInstruction(BPF_RET, ErrorCode(42)); | 224 Instruction* i4 = codegen->MakeInstruction(BPF_RET + BPF_K, 42); |
227 Instruction* i3 = | 225 Instruction* i3 = |
228 codegen->MakeInstruction(BPF_JMP + BPF_JEQ + BPF_K, 2, i4, i5); | 226 codegen->MakeInstruction(BPF_JMP + BPF_JEQ + BPF_K, 2, i4, i5); |
229 Instruction* i2 = codegen->MakeInstruction(BPF_RET, ErrorCode(42)); | 227 Instruction* i2 = codegen->MakeInstruction(BPF_RET + BPF_K, 42); |
230 Instruction* i1 = | 228 Instruction* i1 = |
231 codegen->MakeInstruction(BPF_JMP + BPF_JEQ + BPF_K, 1, i2, i3); | 229 codegen->MakeInstruction(BPF_JMP + BPF_JEQ + BPF_K, 1, i2, i3); |
232 Instruction* i0 = codegen->MakeInstruction(BPF_LD + BPF_W + BPF_ABS, 1, i1); | 230 Instruction* i0 = codegen->MakeInstruction(BPF_LD + BPF_W + BPF_ABS, 1, i1); |
233 | 231 |
234 return i0; | 232 return i0; |
235 } | 233 } |
236 void ForAllPrograms(void (*test)(CodeGenUnittestHelper*, Instruction*, int)) { | 234 void ForAllPrograms(void (*test)(CodeGenUnittestHelper*, Instruction*, int)) { |
237 Instruction* (*function_table[])(CodeGen* codegen, int* flags) = { | 235 Instruction* (*function_table[])(CodeGen* codegen, int* flags) = { |
238 SampleProgramOneInstruction, | 236 SampleProgramOneInstruction, |
239 SampleProgramSimpleBranch, | 237 SampleProgramSimpleBranch, |
(...skipping 289 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
529 assembly.append(reinterpret_cast<char*>(&insn.k), sizeof(insn.k)); | 527 assembly.append(reinterpret_cast<char*>(&insn.k), sizeof(insn.k)); |
530 } | 528 } |
531 SANDBOX_ASSERT(source == assembly); | 529 SANDBOX_ASSERT(source == assembly); |
532 } | 530 } |
533 | 531 |
534 SANDBOX_TEST(CodeGen, All) { | 532 SANDBOX_TEST(CodeGen, All) { |
535 ForAllPrograms(CompileAndCompare); | 533 ForAllPrograms(CompileAndCompare); |
536 } | 534 } |
537 | 535 |
538 } // namespace sandbox | 536 } // namespace sandbox |
OLD | NEW |