15821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Copyright (c) 2012 The Chromium Authors. All rights reserved. 25821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Use of this source code is governed by a BSD-style license that can be 35821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// found in the LICENSE file. 45821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 55821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include <algorithm> 65821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include <set> 75821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include <vector> 85821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 95821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "sandbox/linux/seccomp-bpf/codegen.h" 105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "sandbox/linux/seccomp-bpf/sandbox_bpf.h" 115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "sandbox/linux/tests/unit_tests.h" 125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)namespace playground2 { 145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)class SandboxUnittestHelper : public Sandbox { 165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) public: 175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) typedef Sandbox::Program Program; 185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}; 195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// We want to access some of the private methods in the code generator. We 215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// do so by defining a "friend" that makes these methods public for us. 225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)class CodeGenUnittestHelper : public CodeGen { 235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) public: 245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) void FindBranchTargets(const Instruction& instructions, 255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) BranchTargets *branch_targets) { 265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) CodeGen::FindBranchTargets(instructions, branch_targets); 275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) BasicBlock *CutGraphIntoBasicBlocks(Instruction *insns, 305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const BranchTargets& branch_targets, 315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) TargetsToBlocks *blocks) { 325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return CodeGen::CutGraphIntoBasicBlocks(insns, branch_targets, blocks); 335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) void MergeTails(TargetsToBlocks *blocks) { 365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) CodeGen::MergeTails(blocks); 375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}; 395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)enum { NO_FLAGS = 0x0000, 415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) HAS_MERGEABLE_TAILS = 0x0001, 425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}; 435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)Instruction *SampleProgramOneInstruction(CodeGen *codegen, int *flags) { 455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Create the most basic valid BPF program: 465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // RET ERR_ALLOWED 475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) *flags = NO_FLAGS; 485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return codegen->MakeInstruction(BPF_RET+BPF_K, 495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ErrorCode(ErrorCode::ERR_ALLOWED)); 505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)Instruction *SampleProgramSimpleBranch(CodeGen *codegen, int *flags) { 535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Create a program with a single branch: 545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // JUMP if eq 42 then $0 else $1 555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // 0: RET EPERM 565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // 1: RET ERR_ALLOWED 575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) *flags = NO_FLAGS; 585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return codegen->MakeInstruction(BPF_JMP+BPF_JEQ+BPF_K, 42, 595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) codegen->MakeInstruction(BPF_RET+BPF_K, 605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ErrorCode(EPERM)), 615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) codegen->MakeInstruction(BPF_RET+BPF_K, 625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ErrorCode(ErrorCode::ERR_ALLOWED))); 635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)Instruction *SampleProgramAtypicalBranch(CodeGen *codegen, int *flags) { 665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Create a program with a single branch: 675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // JUMP if eq 42 then $0 else $0 685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // 0: RET ERR_ALLOWED 695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // N.B.: As the instructions in both sides of the branch are already 715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // the same object, we do not actually have any "mergeable" branches. 725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // This needs to be reflected in our choice of "flags". 735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) *flags = NO_FLAGS; 745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Instruction *ret = 765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) codegen->MakeInstruction(BPF_RET+BPF_K, 775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ErrorCode(ErrorCode::ERR_ALLOWED)); 785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return codegen->MakeInstruction(BPF_JMP+BPF_JEQ+BPF_K, 42, ret, ret); 795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)Instruction *SampleProgramComplex(CodeGen *codegen, int *flags) { 825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Creates a basic BPF program that we'll use to test some of the code: 835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // JUMP if eq 42 the $0 else $1 (insn6) 845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // 0: LD 23 (insn5) 855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // 1: JUMP if eq 42 then $2 else $4 (insn4) 865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // 2: JUMP to $3 (insn1) 875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // 3: LD 42 (insn0) 885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // RET ErrorCode(42) (insn2) 895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // 4: LD 42 (insn3) 905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // RET ErrorCode(42) (insn3+) 915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) *flags = HAS_MERGEABLE_TAILS; 925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Instruction *insn0 = codegen->MakeInstruction(BPF_LD+BPF_W+BPF_ABS, 42); 945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) SANDBOX_ASSERT(insn0); 955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) SANDBOX_ASSERT(insn0->code == BPF_LD+BPF_W+BPF_ABS); 965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) SANDBOX_ASSERT(insn0->k == 42); 975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) SANDBOX_ASSERT(insn0->next == NULL); 985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Instruction *insn1 = codegen->MakeInstruction(BPF_JMP+BPF_JA, 0, insn0); 1005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) SANDBOX_ASSERT(insn1); 1015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) SANDBOX_ASSERT(insn1->code == BPF_JMP+BPF_JA); 1025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) SANDBOX_ASSERT(insn1->jt_ptr == insn0); 1035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Instruction *insn2 = codegen->MakeInstruction(BPF_RET+BPF_K, ErrorCode(42)); 1055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) SANDBOX_ASSERT(insn2); 1065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) SANDBOX_ASSERT(insn2->code == BPF_RET+BPF_K); 1075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) SANDBOX_ASSERT(insn2->next == NULL); 1085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // We explicitly duplicate instructions so that MergeTails() can coalesce 1105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // them later. 1115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Instruction *insn3 = codegen->MakeInstruction(BPF_LD+BPF_W+BPF_ABS, 42, 1125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) codegen->MakeInstruction(BPF_RET+BPF_K, ErrorCode(42))); 1135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Instruction *insn4 = codegen->MakeInstruction(BPF_JMP+BPF_JEQ+BPF_K, 42, 1155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) insn1, insn3); 1165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) SANDBOX_ASSERT(insn4); 1175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) SANDBOX_ASSERT(insn4->code == BPF_JMP+BPF_JEQ+BPF_K); 1185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) SANDBOX_ASSERT(insn4->k == 42); 1195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) SANDBOX_ASSERT(insn4->jt_ptr == insn1); 1205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) SANDBOX_ASSERT(insn4->jf_ptr == insn3); 1215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) codegen->JoinInstructions(insn0, insn2); 1235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) SANDBOX_ASSERT(insn0->next == insn2); 1245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Instruction *insn5 = codegen->MakeInstruction(BPF_LD+BPF_W+BPF_ABS, 1265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 23, insn4); 1275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) SANDBOX_ASSERT(insn5); 1285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) SANDBOX_ASSERT(insn5->code == BPF_LD+BPF_W+BPF_ABS); 1295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) SANDBOX_ASSERT(insn5->k == 23); 1305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) SANDBOX_ASSERT(insn5->next == insn4); 1315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Force a basic block that ends in neither a jump instruction nor a return 1335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // instruction. It only contains "insn5". This exercises one of the less 1345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // common code paths in the topo-sort algorithm. 1355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // This also gives us a diamond-shaped pattern in our graph, which stresses 1365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // another aspect of the topo-sort algorithm (namely, the ability to 1375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // correctly count the incoming branches for subtrees that are not disjunct). 1385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Instruction *insn6 = codegen->MakeInstruction(BPF_JMP+BPF_JEQ+BPF_K, 42, 1395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) insn5, insn4); 1405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return insn6; 1425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 1435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void ForAllPrograms(void (*test)(CodeGenUnittestHelper *, Instruction *, int)){ 1455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Instruction *(*function_table[])(CodeGen *codegen, int *flags) = { 1465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) SampleProgramOneInstruction, 1475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) SampleProgramSimpleBranch, 1485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) SampleProgramAtypicalBranch, 1495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) SampleProgramComplex, 1505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) }; 1515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (size_t i = 0; i < arraysize(function_table); ++i) { 1535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) CodeGenUnittestHelper codegen; 1545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int flags = NO_FLAGS; 1555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Instruction *prg = function_table[i](&codegen, &flags); 1565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) test(&codegen, prg, flags); 1575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 1595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void MakeInstruction(CodeGenUnittestHelper *codegen, 1615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Instruction *program, int) { 1625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Nothing to do here 1635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 1645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)SANDBOX_TEST(CodeGen, MakeInstruction) { 1665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ForAllPrograms(MakeInstruction); 1675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 1685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void FindBranchTargets(CodeGenUnittestHelper *codegen, Instruction *prg, int) { 1705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) BranchTargets branch_targets; 1715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) codegen->FindBranchTargets(*prg, &branch_targets); 1725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Verifying the general properties that should be true for every 1745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // well-formed BPF program. 1755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Perform a depth-first traversal of the BPF program an verify that all 1765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // targets of BPF_JMP instructions are represented in the "branch_targets". 1775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // At the same time, compute a set of both the branch targets and all the 1785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // instructions in the program. 1795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) std::vector<Instruction *> stack; 1805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) std::set<Instruction *> all_instructions; 1815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) std::set<Instruction *> target_instructions; 1825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) BranchTargets::const_iterator end = branch_targets.end(); 1835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (Instruction *insn = prg;;) { 1845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) all_instructions.insert(insn); 1855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (BPF_CLASS(insn->code) == BPF_JMP) { 1865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) target_instructions.insert(insn->jt_ptr); 1875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) SANDBOX_ASSERT(insn->jt_ptr != NULL); 1885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) SANDBOX_ASSERT(branch_targets.find(insn->jt_ptr) != end); 1895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (BPF_OP(insn->code) != BPF_JA) { 1905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) target_instructions.insert(insn->jf_ptr); 1915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) SANDBOX_ASSERT(insn->jf_ptr != NULL); 1925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) SANDBOX_ASSERT(branch_targets.find(insn->jf_ptr) != end); 1935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) stack.push_back(insn->jf_ptr); 1945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) insn = insn->jt_ptr; 1965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } else if (BPF_CLASS(insn->code) == BPF_RET) { 1975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) SANDBOX_ASSERT(insn->next == NULL); 1985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (stack.empty()) { 1995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) break; 2005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) insn = stack.back(); 2025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) stack.pop_back(); 2035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } else { 2045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) SANDBOX_ASSERT(insn->next != NULL); 2055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) insn = insn->next; 2065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) SANDBOX_ASSERT(target_instructions.size() == branch_targets.size()); 2095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // We can now subtract the set of the branch targets from the set of all 2115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // instructions. This gives us a set with the instructions that nobody 2125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // ever jumps to. Verify that they are no included in the 2135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // "branch_targets" that FindBranchTargets() computed for us. 2145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Instructions non_target_instructions(all_instructions.size() - 2155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) target_instructions.size()); 2165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) set_difference(all_instructions.begin(), all_instructions.end(), 2175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) target_instructions.begin(), target_instructions.end(), 2185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) non_target_instructions.begin()); 2195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (Instructions::const_iterator iter = non_target_instructions.begin(); 2205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) iter != non_target_instructions.end(); 2215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ++iter) { 2225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) SANDBOX_ASSERT(branch_targets.find(*iter) == end); 2235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 2255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)SANDBOX_TEST(CodeGen, FindBranchTargets) { 2275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ForAllPrograms(FindBranchTargets); 2285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 2295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void CutGraphIntoBasicBlocks(CodeGenUnittestHelper *codegen, 2315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Instruction *prg, int) { 2325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) BranchTargets branch_targets; 2335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) codegen->FindBranchTargets(*prg, &branch_targets); 2345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) TargetsToBlocks all_blocks; 2355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) BasicBlock *first_block = 2365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) codegen->CutGraphIntoBasicBlocks(prg, branch_targets, &all_blocks); 2375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) SANDBOX_ASSERT(first_block != NULL); 2385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) SANDBOX_ASSERT(first_block->instructions.size() > 0); 2395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Instruction *first_insn = first_block->instructions[0]; 2405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Basic blocks are supposed to start with a branch target and end with 2425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // either a jump or a return instruction. It can also end, if the next 2435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // instruction forms the beginning of a new basic block. There should be 2445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // no other jumps or return instructions in the middle of a basic block. 2455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (TargetsToBlocks::const_iterator bb_iter = all_blocks.begin(); 2465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) bb_iter != all_blocks.end(); 2475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ++bb_iter) { 2485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) BasicBlock *bb = bb_iter->second; 2495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) SANDBOX_ASSERT(bb != NULL); 2505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) SANDBOX_ASSERT(bb->instructions.size() > 0); 2515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Instruction *insn = bb->instructions[0]; 2525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) SANDBOX_ASSERT(insn == first_insn || 2535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) branch_targets.find(insn) != branch_targets.end()); 2545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (Instructions::const_iterator insn_iter = bb->instructions.begin();;){ 2555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) insn = *insn_iter; 2565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (++insn_iter != bb->instructions.end()) { 2575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) SANDBOX_ASSERT(BPF_CLASS(insn->code) != BPF_JMP); 2585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) SANDBOX_ASSERT(BPF_CLASS(insn->code) != BPF_RET); 2595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } else { 2605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) SANDBOX_ASSERT(BPF_CLASS(insn->code) == BPF_JMP || 2615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) BPF_CLASS(insn->code) == BPF_RET || 2625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) branch_targets.find(insn->next) != 2635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) branch_targets.end()); 2645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) break; 2655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) SANDBOX_ASSERT(branch_targets.find(*insn_iter) == branch_targets.end()); 2675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 2705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)SANDBOX_TEST(CodeGen, CutGraphIntoBasicBlocks) { 2725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ForAllPrograms(CutGraphIntoBasicBlocks); 2735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 2745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void MergeTails(CodeGenUnittestHelper *codegen, Instruction *prg, 2765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int flags) { 2775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) BranchTargets branch_targets; 2785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) codegen->FindBranchTargets(*prg, &branch_targets); 2795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) TargetsToBlocks all_blocks; 2805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) BasicBlock *first_block = 2815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) codegen->CutGraphIntoBasicBlocks(prg, branch_targets, &all_blocks); 2825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // The shape of our graph and thus the function of our program should 2845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // still be unchanged after we run MergeTails(). We verify this by 2855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // serializing the graph and verifying that it is still the same. 2865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // We also verify that at least some of the edges changed because of 2875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // tail merging. 2885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) std::string graph[2]; 2895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) std::string edges[2]; 2905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // The loop executes twice. After the first run, we call MergeTails() on 2925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // our graph. 2935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (int i = 0;;) { 2945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Traverse the entire program in depth-first order. 2955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) std::vector<BasicBlock *> stack; 2965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (BasicBlock *bb = first_block;;) { 2975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Serialize the instructions in this basic block. In general, we only 2985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // need to serialize "code" and "k"; except for a BPF_JA instruction 2995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // where "k" isn't set. 3005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // The stream of instructions should be unchanged after MergeTails(). 3015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (Instructions::const_iterator iter = bb->instructions.begin(); 3025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) iter != bb->instructions.end(); 3035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ++iter) { 3045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) graph[i].append(reinterpret_cast<char *>(&(*iter)->code), 3055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) sizeof((*iter)->code)); 3065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (BPF_CLASS((*iter)->code) != BPF_JMP || 3075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) BPF_OP((*iter)->code) != BPF_JA) { 3085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) graph[i].append(reinterpret_cast<char *>(&(*iter)->k), 3095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) sizeof((*iter)->k)); 3105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 3115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 3125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Also serialize the addresses the basic blocks as we encounter them. 3145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // This will change as basic blocks are coalesed by MergeTails(). 3155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) edges[i].append(reinterpret_cast<char *>(&bb), sizeof(bb)); 3165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Depth-first traversal of the graph. We only ever need to look at the 3185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // very last instruction in the basic block, as that is the only one that 3195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // can change code flow. 3205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Instruction *insn = bb->instructions.back(); 3215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (BPF_CLASS(insn->code) == BPF_JMP) { 3225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // For jump instructions, we need to remember the "false" branch while 3235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // traversing the "true" branch. This is not necessary for BPF_JA which 3245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // only has a single branch. 3255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (BPF_OP(insn->code) != BPF_JA) { 3265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) stack.push_back(all_blocks[insn->jf_ptr]); 3275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 3285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) bb = all_blocks[insn->jt_ptr]; 3295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } else if (BPF_CLASS(insn->code) == BPF_RET) { 3305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // After a BPF_RET, see if we need to back track. 3315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (stack.empty()) { 3325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) break; 3335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 3345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) bb = stack.back(); 3355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) stack.pop_back(); 3365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } else { 3375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // For "normal" instructions, just follow to the next basic block. 3385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) bb = all_blocks[insn->next]; 3395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 3405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 3415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Our loop runs exactly two times. 3435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (++i > 1) { 3445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) break; 3455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 3465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) codegen->MergeTails(&all_blocks); 3475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 3485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) SANDBOX_ASSERT(graph[0] == graph[1]); 3495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (flags & HAS_MERGEABLE_TAILS) { 3505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) SANDBOX_ASSERT(edges[0] != edges[1]); 3515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } else { 3525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) SANDBOX_ASSERT(edges[0] == edges[1]); 3535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 3545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 3555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)SANDBOX_TEST(CodeGen, MergeTails) { 3575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ForAllPrograms(MergeTails); 3585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 3595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void CompileAndCompare(CodeGenUnittestHelper *codegen, Instruction *prg, int) { 3615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // TopoSortBasicBlocks() has internal checks that cause it to fail, if it 3625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // detects a problem. Typically, if anything goes wrong, this looks to the 3635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // TopoSort algorithm as if there had been cycles in the input data. 3645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // This provides a pretty good unittest. 3655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // We hand-crafted the program returned by SampleProgram() to exercise 3665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // several of the more interesting code-paths. See comments in 3675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // SampleProgram() for details. 3685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // In addition to relying on the internal consistency checks in the compiler, 3695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // we also serialize the graph and the resulting BPF program and compare 3705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // them. With the exception of BPF_JA instructions that might have been 3715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // inserted, both instruction streams should be equivalent. 3725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // As Compile() modifies the instructions, we have to serialize the graph 3735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // before calling Compile(). 3745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) std::string source; 3755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Instructions source_stack; 3765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (const Instruction *insn = prg, *next; insn; insn = next) { 3775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (BPF_CLASS(insn->code) == BPF_JMP) { 3785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (BPF_OP(insn->code) == BPF_JA) { 3795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Do not serialize BPF_JA instructions (see above). 3805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) next = insn->jt_ptr; 3815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) continue; 3825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } else { 3835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) source_stack.push_back(insn->jf_ptr); 3845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) next = insn->jt_ptr; 3855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 3865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } else if (BPF_CLASS(insn->code) == BPF_RET) { 3875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (source_stack.empty()) { 3885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) next = NULL; 3895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } else { 3905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) next = source_stack.back(); 3915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) source_stack.pop_back(); 3925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 3935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } else { 3945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) next = insn->next; 3955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 3965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Only serialize "code" and "k". That's all the information we need to 3975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // compare. The rest of the information is encoded in the order of 3985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // instructions. 3995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) source.append(reinterpret_cast<const char *>(&insn->code), 4005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) sizeof(insn->code)); 4015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) source.append(reinterpret_cast<const char *>(&insn->k), 4025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) sizeof(insn->k)); 4035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 4045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 4055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Compile the program 4065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) SandboxUnittestHelper::Program bpf; 4075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) codegen->Compile(prg, &bpf); 4085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 4095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Serialize the resulting BPF instructions. 4105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) std::string assembly; 4115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) std::vector<int> assembly_stack; 4125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (int idx = 0; idx >= 0;) { 4135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) SANDBOX_ASSERT(idx < (int)bpf.size()); 4145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) struct sock_filter& insn = bpf[idx]; 4155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (BPF_CLASS(insn.code) == BPF_JMP) { 4165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (BPF_OP(insn.code) == BPF_JA) { 4175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Do not serialize BPF_JA instructions (see above). 4185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) idx += insn.k + 1; 4195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) continue; 4205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } else { 4215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) assembly_stack.push_back(idx + insn.jf + 1); 4225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) idx += insn.jt + 1; 4235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 4245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } else if (BPF_CLASS(insn.code) == BPF_RET) { 4255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (assembly_stack.empty()) { 4265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) idx = -1; 4275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } else { 4285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) idx = assembly_stack.back(); 4295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) assembly_stack.pop_back(); 4305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 4315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } else { 4325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ++idx; 4335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 4345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Serialize the same information that we serialized before compilation. 4355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) assembly.append(reinterpret_cast<char *>(&insn.code), sizeof(insn.code)); 4365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) assembly.append(reinterpret_cast<char *>(&insn.k), sizeof(insn.k)); 4375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 4385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) SANDBOX_ASSERT(source == assembly); 4395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 4405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 4415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)SANDBOX_TEST(CodeGen, All) { 4425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ForAllPrograms(CompileAndCompare); 4435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 4445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 4455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} // namespace playground2 446