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 #include "sandbox/linux/seccomp-bpf/codegen.h"
6
7 #include <errno.h>
8 #include <linux/filter.h>
9
10 #include <set>
11 #include <string>
12 #include <vector>
13
14 #include "sandbox/linux/seccomp-bpf/basicblock.h"
15 #include "sandbox/linux/seccomp-bpf/errorcode.h"
16 #include "sandbox/linux/seccomp-bpf/instruction.h"
17 #include "sandbox/linux/seccomp-bpf/sandbox_bpf.h"
18 #include "sandbox/linux/tests/unit_tests.h"
19
20 namespace sandbox {
21
22 class SandboxUnittestHelper : public SandboxBPF {
23 public:
24 typedef SandboxBPF::Program Program;
25 };
26
27 // We want to access some of the private methods in the code generator. We
28 // do so by defining a "friend" that makes these methods public for us.
29 class CodeGenUnittestHelper : public CodeGen {
30 public:
FindBranchTargets(const Instruction & instructions,BranchTargets * branch_targets)31 void FindBranchTargets(const Instruction& instructions,
32 BranchTargets* branch_targets) {
33 CodeGen::FindBranchTargets(instructions, branch_targets);
34 }
35
CutGraphIntoBasicBlocks(Instruction * insns,const BranchTargets & branch_targets,TargetsToBlocks * blocks)36 BasicBlock* CutGraphIntoBasicBlocks(Instruction* insns,
37 const BranchTargets& branch_targets,
38 TargetsToBlocks* blocks) {
39 return CodeGen::CutGraphIntoBasicBlocks(insns, branch_targets, blocks);
40 }
41
MergeTails(TargetsToBlocks * blocks)42 void MergeTails(TargetsToBlocks* blocks) { CodeGen::MergeTails(blocks); }
43 };
44
45 enum { NO_FLAGS = 0x0000, HAS_MERGEABLE_TAILS = 0x0001, };
46
SampleProgramOneInstruction(CodeGen * codegen,int * flags)47 Instruction* SampleProgramOneInstruction(CodeGen* codegen, int* flags) {
48 // Create the most basic valid BPF program:
49 // RET 0
50 *flags = NO_FLAGS;
51 return codegen->MakeInstruction(BPF_RET + BPF_K, 0);
52 }
53
SampleProgramSimpleBranch(CodeGen * codegen,int * flags)54 Instruction* SampleProgramSimpleBranch(CodeGen* codegen, int* flags) {
55 // Create a program with a single branch:
56 // JUMP if eq 42 then $0 else $1
57 // 0: RET 1
58 // 1: RET 0
59 *flags = NO_FLAGS;
60 return codegen->MakeInstruction(
61 BPF_JMP + BPF_JEQ + BPF_K,
62 42,
63 codegen->MakeInstruction(BPF_RET + BPF_K, 1),
64 codegen->MakeInstruction(BPF_RET + BPF_K, 0));
65 }
66
SampleProgramAtypicalBranch(CodeGen * codegen,int * flags)67 Instruction* SampleProgramAtypicalBranch(CodeGen* codegen, int* flags) {
68 // Create a program with a single branch:
69 // JUMP if eq 42 then $0 else $0
70 // 0: RET 0
71
72 // N.B.: As the instructions in both sides of the branch are already
73 // the same object, we do not actually have any "mergeable" branches.
74 // This needs to be reflected in our choice of "flags".
75 *flags = NO_FLAGS;
76
77 Instruction* ret = codegen->MakeInstruction(
78 BPF_RET + BPF_K, 0);
79 return codegen->MakeInstruction(BPF_JMP + BPF_JEQ + BPF_K, 42, ret, ret);
80 }
81
SampleProgramComplex(CodeGen * codegen,int * flags)82 Instruction* SampleProgramComplex(CodeGen* codegen, int* flags) {
83 // Creates a basic BPF program that we'll use to test some of the code:
84 // JUMP if eq 42 the $0 else $1 (insn6)
85 // 0: LD 23 (insn5)
86 // 1: JUMP if eq 42 then $2 else $4 (insn4)
87 // 2: JUMP to $3 (insn2)
88 // 3: LD 42 (insn1)
89 // RET 42 (insn0)
90 // 4: LD 42 (insn3)
91 // RET 42 (insn3+)
92 *flags = HAS_MERGEABLE_TAILS;
93
94 Instruction* insn0 = codegen->MakeInstruction(BPF_RET + BPF_K, 42);
95 SANDBOX_ASSERT(insn0);
96 SANDBOX_ASSERT(insn0->code == BPF_RET + BPF_K);
97 SANDBOX_ASSERT(insn0->next == NULL);
98
99 Instruction* insn1 =
100 codegen->MakeInstruction(BPF_LD + BPF_W + BPF_ABS, 42, insn0);
101 SANDBOX_ASSERT(insn1);
102 SANDBOX_ASSERT(insn1->code == BPF_LD + BPF_W + BPF_ABS);
103 SANDBOX_ASSERT(insn1->k == 42);
104 SANDBOX_ASSERT(insn1->next == insn0);
105
106 Instruction* insn2 = codegen->MakeInstruction(BPF_JMP + BPF_JA, 0, insn1);
107 SANDBOX_ASSERT(insn2);
108 SANDBOX_ASSERT(insn2->code == BPF_JMP + BPF_JA);
109 SANDBOX_ASSERT(insn2->jt_ptr == insn1);
110
111 // We explicitly duplicate instructions so that MergeTails() can coalesce
112 // them later.
113 Instruction* insn3 = codegen->MakeInstruction(
114 BPF_LD + BPF_W + BPF_ABS,
115 42,
116 codegen->MakeInstruction(BPF_RET + BPF_K, 42));
117
118 Instruction* insn4 =
119 codegen->MakeInstruction(BPF_JMP + BPF_JEQ + BPF_K, 42, insn2, insn3);
120 SANDBOX_ASSERT(insn4);
121 SANDBOX_ASSERT(insn4->code == BPF_JMP + BPF_JEQ + BPF_K);
122 SANDBOX_ASSERT(insn4->k == 42);
123 SANDBOX_ASSERT(insn4->jt_ptr == insn2);
124 SANDBOX_ASSERT(insn4->jf_ptr == insn3);
125
126 Instruction* insn5 =
127 codegen->MakeInstruction(BPF_LD + BPF_W + BPF_ABS, 23, insn4);
128 SANDBOX_ASSERT(insn5);
129 SANDBOX_ASSERT(insn5->code == BPF_LD + BPF_W + BPF_ABS);
130 SANDBOX_ASSERT(insn5->k == 23);
131 SANDBOX_ASSERT(insn5->next == insn4);
132
133 // Force a basic block that ends in neither a jump instruction nor a return
134 // instruction. It only contains "insn5". This exercises one of the less
135 // common code paths in the topo-sort algorithm.
136 // This also gives us a diamond-shaped pattern in our graph, which stresses
137 // another aspect of the topo-sort algorithm (namely, the ability to
138 // correctly count the incoming branches for subtrees that are not disjunct).
139 Instruction* insn6 =
140 codegen->MakeInstruction(BPF_JMP + BPF_JEQ + BPF_K, 42, insn5, insn4);
141
142 return insn6;
143 }
144
SampleProgramConfusingTails(CodeGen * codegen,int * flags)145 Instruction* SampleProgramConfusingTails(CodeGen* codegen, int* flags) {
146 // This simple program demonstrates https://crbug.com/351103/
147 // The two "LOAD 0" instructions are blocks of their own. MergeTails() could
148 // be tempted to merge them since they are the same. However, they are
149 // not mergeable because they fall-through to non semantically equivalent
150 // blocks.
151 // Without the fix for this bug, this program should trigger the check in
152 // CompileAndCompare: the serialized graphs from the program and its compiled
153 // version will differ.
154 //
155 // 0) LOAD 1 // ???
156 // 1) if A == 0x1; then JMP 2 else JMP 3
157 // 2) LOAD 0 // System call number
158 // 3) if A == 0x2; then JMP 4 else JMP 5
159 // 4) LOAD 0 // System call number
160 // 5) if A == 0x1; then JMP 6 else JMP 7
161 // 6) RET 0
162 // 7) RET 1
163 *flags = NO_FLAGS;
164
165 Instruction* i7 = codegen->MakeInstruction(BPF_RET + BPF_K, 1);
166 Instruction* i6 = codegen->MakeInstruction(BPF_RET + BPF_K, 0);
167 Instruction* i5 =
168 codegen->MakeInstruction(BPF_JMP + BPF_JEQ + BPF_K, 1, i6, i7);
169 Instruction* i4 = codegen->MakeInstruction(BPF_LD + BPF_W + BPF_ABS, 0, i5);
170 Instruction* i3 =
171 codegen->MakeInstruction(BPF_JMP + BPF_JEQ + BPF_K, 2, i4, i5);
172 Instruction* i2 = codegen->MakeInstruction(BPF_LD + BPF_W + BPF_ABS, 0, i3);
173 Instruction* i1 =
174 codegen->MakeInstruction(BPF_JMP + BPF_JEQ + BPF_K, 1, i2, i3);
175 Instruction* i0 = codegen->MakeInstruction(BPF_LD + BPF_W + BPF_ABS, 1, i1);
176
177 return i0;
178 }
179
SampleProgramConfusingTailsBasic(CodeGen * codegen,int * flags)180 Instruction* SampleProgramConfusingTailsBasic(CodeGen* codegen, int* flags) {
181 // Without the fix for https://crbug.com/351103/, (see
182 // SampleProgramConfusingTails()), this would generate a cyclic graph and
183 // crash as the two "LOAD 0" instructions would get merged.
184 //
185 // 0) LOAD 1 // ???
186 // 1) if A == 0x1; then JMP 2 else JMP 3
187 // 2) LOAD 0 // System call number
188 // 3) if A == 0x2; then JMP 4 else JMP 5
189 // 4) LOAD 0 // System call number
190 // 5) RET 1
191 *flags = NO_FLAGS;
192
193 Instruction* i5 = codegen->MakeInstruction(BPF_RET + BPF_K, 1);
194 Instruction* i4 = codegen->MakeInstruction(BPF_LD + BPF_W + BPF_ABS, 0, i5);
195 Instruction* i3 =
196 codegen->MakeInstruction(BPF_JMP + BPF_JEQ + BPF_K, 2, i4, i5);
197 Instruction* i2 = codegen->MakeInstruction(BPF_LD + BPF_W + BPF_ABS, 0, i3);
198 Instruction* i1 =
199 codegen->MakeInstruction(BPF_JMP + BPF_JEQ + BPF_K, 1, i2, i3);
200 Instruction* i0 = codegen->MakeInstruction(BPF_LD + BPF_W + BPF_ABS, 1, i1);
201
202 return i0;
203 }
204
SampleProgramConfusingTailsMergeable(CodeGen * codegen,int * flags)205 Instruction* SampleProgramConfusingTailsMergeable(CodeGen* codegen,
206 int* flags) {
207 // This is similar to SampleProgramConfusingTails(), except that
208 // instructions 2 and 4 are now RET instructions.
209 // In PointerCompare(), this exercises the path where two blocks are of the
210 // same length and identical and the last instruction is a JMP or RET, so the
211 // following blocks don't need to be looked at and the blocks are mergeable.
212 //
213 // 0) LOAD 1 // ???
214 // 1) if A == 0x1; then JMP 2 else JMP 3
215 // 2) RET 42
216 // 3) if A == 0x2; then JMP 4 else JMP 5
217 // 4) RET 42
218 // 5) if A == 0x1; then JMP 6 else JMP 7
219 // 6) RET 0
220 // 7) RET 1
221 *flags = HAS_MERGEABLE_TAILS;
222
223 Instruction* i7 = codegen->MakeInstruction(BPF_RET + BPF_K, 1);
224 Instruction* i6 = codegen->MakeInstruction(BPF_RET + BPF_K, 0);
225 Instruction* i5 =
226 codegen->MakeInstruction(BPF_JMP + BPF_JEQ + BPF_K, 1, i6, i7);
227 Instruction* i4 = codegen->MakeInstruction(BPF_RET + BPF_K, 42);
228 Instruction* i3 =
229 codegen->MakeInstruction(BPF_JMP + BPF_JEQ + BPF_K, 2, i4, i5);
230 Instruction* i2 = codegen->MakeInstruction(BPF_RET + BPF_K, 42);
231 Instruction* i1 =
232 codegen->MakeInstruction(BPF_JMP + BPF_JEQ + BPF_K, 1, i2, i3);
233 Instruction* i0 = codegen->MakeInstruction(BPF_LD + BPF_W + BPF_ABS, 1, i1);
234
235 return i0;
236 }
ForAllPrograms(void (* test)(CodeGenUnittestHelper *,Instruction *,int))237 void ForAllPrograms(void (*test)(CodeGenUnittestHelper*, Instruction*, int)) {
238 Instruction* (*function_table[])(CodeGen* codegen, int* flags) = {
239 SampleProgramOneInstruction,
240 SampleProgramSimpleBranch,
241 SampleProgramAtypicalBranch,
242 SampleProgramComplex,
243 SampleProgramConfusingTails,
244 SampleProgramConfusingTailsBasic,
245 SampleProgramConfusingTailsMergeable,
246 };
247
248 for (size_t i = 0; i < arraysize(function_table); ++i) {
249 CodeGenUnittestHelper codegen;
250 int flags = NO_FLAGS;
251 Instruction *prg = function_table[i](&codegen, &flags);
252 test(&codegen, prg, flags);
253 }
254 }
255
MakeInstruction(CodeGenUnittestHelper * codegen,Instruction * program,int)256 void MakeInstruction(CodeGenUnittestHelper* codegen,
257 Instruction* program, int) {
258 // Nothing to do here
259 }
260
SANDBOX_TEST(CodeGen,MakeInstruction)261 SANDBOX_TEST(CodeGen, MakeInstruction) {
262 ForAllPrograms(MakeInstruction);
263 }
264
FindBranchTargets(CodeGenUnittestHelper * codegen,Instruction * prg,int)265 void FindBranchTargets(CodeGenUnittestHelper* codegen, Instruction* prg, int) {
266 BranchTargets branch_targets;
267 codegen->FindBranchTargets(*prg, &branch_targets);
268
269 // Verifying the general properties that should be true for every
270 // well-formed BPF program.
271 // Perform a depth-first traversal of the BPF program an verify that all
272 // targets of BPF_JMP instructions are represented in the "branch_targets".
273 // At the same time, compute a set of both the branch targets and all the
274 // instructions in the program.
275 std::vector<Instruction*> stack;
276 std::set<Instruction*> all_instructions;
277 std::set<Instruction*> target_instructions;
278 BranchTargets::const_iterator end = branch_targets.end();
279 for (Instruction* insn = prg;;) {
280 all_instructions.insert(insn);
281 if (BPF_CLASS(insn->code) == BPF_JMP) {
282 target_instructions.insert(insn->jt_ptr);
283 SANDBOX_ASSERT(insn->jt_ptr != NULL);
284 SANDBOX_ASSERT(branch_targets.find(insn->jt_ptr) != end);
285 if (BPF_OP(insn->code) != BPF_JA) {
286 target_instructions.insert(insn->jf_ptr);
287 SANDBOX_ASSERT(insn->jf_ptr != NULL);
288 SANDBOX_ASSERT(branch_targets.find(insn->jf_ptr) != end);
289 stack.push_back(insn->jf_ptr);
290 }
291 insn = insn->jt_ptr;
292 } else if (BPF_CLASS(insn->code) == BPF_RET) {
293 SANDBOX_ASSERT(insn->next == NULL);
294 if (stack.empty()) {
295 break;
296 }
297 insn = stack.back();
298 stack.pop_back();
299 } else {
300 SANDBOX_ASSERT(insn->next != NULL);
301 insn = insn->next;
302 }
303 }
304 SANDBOX_ASSERT(target_instructions.size() == branch_targets.size());
305
306 // We can now subtract the set of the branch targets from the set of all
307 // instructions. This gives us a set with the instructions that nobody
308 // ever jumps to. Verify that they are no included in the
309 // "branch_targets" that FindBranchTargets() computed for us.
310 Instructions non_target_instructions(all_instructions.size() -
311 target_instructions.size());
312 set_difference(all_instructions.begin(),
313 all_instructions.end(),
314 target_instructions.begin(),
315 target_instructions.end(),
316 non_target_instructions.begin());
317 for (Instructions::const_iterator iter = non_target_instructions.begin();
318 iter != non_target_instructions.end();
319 ++iter) {
320 SANDBOX_ASSERT(branch_targets.find(*iter) == end);
321 }
322 }
323
SANDBOX_TEST(CodeGen,FindBranchTargets)324 SANDBOX_TEST(CodeGen, FindBranchTargets) { ForAllPrograms(FindBranchTargets); }
325
CutGraphIntoBasicBlocks(CodeGenUnittestHelper * codegen,Instruction * prg,int)326 void CutGraphIntoBasicBlocks(CodeGenUnittestHelper* codegen,
327 Instruction* prg,
328 int) {
329 BranchTargets branch_targets;
330 codegen->FindBranchTargets(*prg, &branch_targets);
331 TargetsToBlocks all_blocks;
332 BasicBlock* first_block =
333 codegen->CutGraphIntoBasicBlocks(prg, branch_targets, &all_blocks);
334 SANDBOX_ASSERT(first_block != NULL);
335 SANDBOX_ASSERT(first_block->instructions.size() > 0);
336 Instruction* first_insn = first_block->instructions[0];
337
338 // Basic blocks are supposed to start with a branch target and end with
339 // either a jump or a return instruction. It can also end, if the next
340 // instruction forms the beginning of a new basic block. There should be
341 // no other jumps or return instructions in the middle of a basic block.
342 for (TargetsToBlocks::const_iterator bb_iter = all_blocks.begin();
343 bb_iter != all_blocks.end();
344 ++bb_iter) {
345 BasicBlock* bb = bb_iter->second;
346 SANDBOX_ASSERT(bb != NULL);
347 SANDBOX_ASSERT(bb->instructions.size() > 0);
348 Instruction* insn = bb->instructions[0];
349 SANDBOX_ASSERT(insn == first_insn ||
350 branch_targets.find(insn) != branch_targets.end());
351 for (Instructions::const_iterator insn_iter = bb->instructions.begin();;) {
352 insn = *insn_iter;
353 if (++insn_iter != bb->instructions.end()) {
354 SANDBOX_ASSERT(BPF_CLASS(insn->code) != BPF_JMP);
355 SANDBOX_ASSERT(BPF_CLASS(insn->code) != BPF_RET);
356 } else {
357 SANDBOX_ASSERT(BPF_CLASS(insn->code) == BPF_JMP ||
358 BPF_CLASS(insn->code) == BPF_RET ||
359 branch_targets.find(insn->next) != branch_targets.end());
360 break;
361 }
362 SANDBOX_ASSERT(branch_targets.find(*insn_iter) == branch_targets.end());
363 }
364 }
365 }
366
SANDBOX_TEST(CodeGen,CutGraphIntoBasicBlocks)367 SANDBOX_TEST(CodeGen, CutGraphIntoBasicBlocks) {
368 ForAllPrograms(CutGraphIntoBasicBlocks);
369 }
370
MergeTails(CodeGenUnittestHelper * codegen,Instruction * prg,int flags)371 void MergeTails(CodeGenUnittestHelper* codegen, Instruction* prg, int flags) {
372 BranchTargets branch_targets;
373 codegen->FindBranchTargets(*prg, &branch_targets);
374 TargetsToBlocks all_blocks;
375 BasicBlock* first_block =
376 codegen->CutGraphIntoBasicBlocks(prg, branch_targets, &all_blocks);
377
378 // The shape of our graph and thus the function of our program should
379 // still be unchanged after we run MergeTails(). We verify this by
380 // serializing the graph and verifying that it is still the same.
381 // We also verify that at least some of the edges changed because of
382 // tail merging.
383 std::string graph[2];
384 std::string edges[2];
385
386 // The loop executes twice. After the first run, we call MergeTails() on
387 // our graph.
388 for (int i = 0;;) {
389 // Traverse the entire program in depth-first order.
390 std::vector<BasicBlock*> stack;
391 for (BasicBlock* bb = first_block;;) {
392 // Serialize the instructions in this basic block. In general, we only
393 // need to serialize "code" and "k"; except for a BPF_JA instruction
394 // where "k" isn't set.
395 // The stream of instructions should be unchanged after MergeTails().
396 for (Instructions::const_iterator iter = bb->instructions.begin();
397 iter != bb->instructions.end();
398 ++iter) {
399 graph[i].append(reinterpret_cast<char*>(&(*iter)->code),
400 sizeof((*iter)->code));
401 if (BPF_CLASS((*iter)->code) != BPF_JMP ||
402 BPF_OP((*iter)->code) != BPF_JA) {
403 graph[i].append(reinterpret_cast<char*>(&(*iter)->k),
404 sizeof((*iter)->k));
405 }
406 }
407
408 // Also serialize the addresses the basic blocks as we encounter them.
409 // This will change as basic blocks are coalesed by MergeTails().
410 edges[i].append(reinterpret_cast<char*>(&bb), sizeof(bb));
411
412 // Depth-first traversal of the graph. We only ever need to look at the
413 // very last instruction in the basic block, as that is the only one that
414 // can change code flow.
415 Instruction* insn = bb->instructions.back();
416 if (BPF_CLASS(insn->code) == BPF_JMP) {
417 // For jump instructions, we need to remember the "false" branch while
418 // traversing the "true" branch. This is not necessary for BPF_JA which
419 // only has a single branch.
420 if (BPF_OP(insn->code) != BPF_JA) {
421 stack.push_back(all_blocks[insn->jf_ptr]);
422 }
423 bb = all_blocks[insn->jt_ptr];
424 } else if (BPF_CLASS(insn->code) == BPF_RET) {
425 // After a BPF_RET, see if we need to back track.
426 if (stack.empty()) {
427 break;
428 }
429 bb = stack.back();
430 stack.pop_back();
431 } else {
432 // For "normal" instructions, just follow to the next basic block.
433 bb = all_blocks[insn->next];
434 }
435 }
436
437 // Our loop runs exactly two times.
438 if (++i > 1) {
439 break;
440 }
441 codegen->MergeTails(&all_blocks);
442 }
443 SANDBOX_ASSERT(graph[0] == graph[1]);
444 if (flags & HAS_MERGEABLE_TAILS) {
445 SANDBOX_ASSERT(edges[0] != edges[1]);
446 } else {
447 SANDBOX_ASSERT(edges[0] == edges[1]);
448 }
449 }
450
SANDBOX_TEST(CodeGen,MergeTails)451 SANDBOX_TEST(CodeGen, MergeTails) {
452 ForAllPrograms(MergeTails);
453 }
454
CompileAndCompare(CodeGenUnittestHelper * codegen,Instruction * prg,int)455 void CompileAndCompare(CodeGenUnittestHelper* codegen, Instruction* prg, int) {
456 // TopoSortBasicBlocks() has internal checks that cause it to fail, if it
457 // detects a problem. Typically, if anything goes wrong, this looks to the
458 // TopoSort algorithm as if there had been cycles in the input data.
459 // This provides a pretty good unittest.
460 // We hand-crafted the program returned by SampleProgram() to exercise
461 // several of the more interesting code-paths. See comments in
462 // SampleProgram() for details.
463 // In addition to relying on the internal consistency checks in the compiler,
464 // we also serialize the graph and the resulting BPF program and compare
465 // them. With the exception of BPF_JA instructions that might have been
466 // inserted, both instruction streams should be equivalent.
467 // As Compile() modifies the instructions, we have to serialize the graph
468 // before calling Compile().
469 std::string source;
470 Instructions source_stack;
471 for (const Instruction* insn = prg, *next; insn; insn = next) {
472 if (BPF_CLASS(insn->code) == BPF_JMP) {
473 if (BPF_OP(insn->code) == BPF_JA) {
474 // Do not serialize BPF_JA instructions (see above).
475 next = insn->jt_ptr;
476 continue;
477 } else {
478 source_stack.push_back(insn->jf_ptr);
479 next = insn->jt_ptr;
480 }
481 } else if (BPF_CLASS(insn->code) == BPF_RET) {
482 if (source_stack.empty()) {
483 next = NULL;
484 } else {
485 next = source_stack.back();
486 source_stack.pop_back();
487 }
488 } else {
489 next = insn->next;
490 }
491 // Only serialize "code" and "k". That's all the information we need to
492 // compare. The rest of the information is encoded in the order of
493 // instructions.
494 source.append(reinterpret_cast<const char*>(&insn->code),
495 sizeof(insn->code));
496 source.append(reinterpret_cast<const char*>(&insn->k), sizeof(insn->k));
497 }
498
499 // Compile the program
500 SandboxUnittestHelper::Program bpf;
501 codegen->Compile(prg, &bpf);
502
503 // Serialize the resulting BPF instructions.
504 std::string assembly;
505 std::vector<int> assembly_stack;
506 for (int idx = 0; idx >= 0;) {
507 SANDBOX_ASSERT(idx < (int)bpf.size());
508 struct sock_filter& insn = bpf[idx];
509 if (BPF_CLASS(insn.code) == BPF_JMP) {
510 if (BPF_OP(insn.code) == BPF_JA) {
511 // Do not serialize BPF_JA instructions (see above).
512 idx += insn.k + 1;
513 continue;
514 } else {
515 assembly_stack.push_back(idx + insn.jf + 1);
516 idx += insn.jt + 1;
517 }
518 } else if (BPF_CLASS(insn.code) == BPF_RET) {
519 if (assembly_stack.empty()) {
520 idx = -1;
521 } else {
522 idx = assembly_stack.back();
523 assembly_stack.pop_back();
524 }
525 } else {
526 ++idx;
527 }
528 // Serialize the same information that we serialized before compilation.
529 assembly.append(reinterpret_cast<char*>(&insn.code), sizeof(insn.code));
530 assembly.append(reinterpret_cast<char*>(&insn.k), sizeof(insn.k));
531 }
532 SANDBOX_ASSERT(source == assembly);
533 }
534
SANDBOX_TEST(CodeGen,All)535 SANDBOX_TEST(CodeGen, All) {
536 ForAllPrograms(CompileAndCompare);
537 }
538
539 } // namespace sandbox
540