| 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 |