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)#ifndef SANDBOX_LINUX_SECCOMP_BPF_CODEGEN_H__ 65821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#define SANDBOX_LINUX_SECCOMP_BPF_CODEGEN_H__ 75821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 85821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include <map> 95821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include <set> 105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include <vector> 115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "sandbox/linux/seccomp-bpf/basicblock.h" 135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "sandbox/linux/seccomp-bpf/instruction.h" 145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "sandbox/linux/seccomp-bpf/sandbox_bpf.h" 155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)namespace playground2 { 185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)typedef std::vector<Instruction *> Instructions; 205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)typedef std::vector<BasicBlock *> BasicBlocks; 215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)typedef std::map<const Instruction *, int> BranchTargets; 225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)typedef std::map<const Instruction *, BasicBlock *> TargetsToBlocks; 235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)typedef std::map<const BasicBlock *, int> IncomingBranches; 245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// The code generator instantiates a basic compiler that can convert a 265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// graph of BPF instructions into a well-formed stream of BPF instructions. 275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Most notably, it ensures that jumps are always forward and don't exceed 285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// the limit of 255 instructions imposed by the instruction set. 295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Callers would typically create a new CodeGen object and then use it to 315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// build a DAG of Instructions. They'll eventually call Compile() to convert 325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// this DAG to a Sandbox::Program. 335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Instructions can be chained at the time when they are created, or they 355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// can be joined later by calling JoinInstructions(). 365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// CodeGen gen; 385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Instruction *dag, *branch; 395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// dag = 405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// gen.MakeInstruction(BPF_LD+BPF_W+BPF_ABS, 415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// offsetof(struct arch_seccomp_data, nr), 425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// branch = 435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// gen.MakeInstruction(BPF_JMP+BPF_EQ+BPF_K, __NR_getpid, 445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Trap(GetPidHandler, NULL), NULL); 455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// gen.JoinInstructions(branch, 465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// gen.MakeInstruction(BPF_RET+BPF_K, ErrorCode(ErrorCode::ERR_ALLOWED))); 475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// // Simplified code follows; in practice, it is important to avoid calling 495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// // any C++ destructors after starting the sandbox. 505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Sandbox::Program program; 515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// gen.Compile(dag, program); 525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// const struct sock_fprog prog = { 535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// static_cast<unsigned short>(program->size()), &program[0] }; 545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// prctl(PR_SET_SECCOMP, SECCOMP_MODE_FILTER, &prog); 555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)class CodeGen { 575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) public: 585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) CodeGen(); 595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ~CodeGen(); 605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // This is a helper method that can be used for debugging purposes. It is 625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // not normally called. 635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) static void PrintProgram(const Sandbox::Program& program); 645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Create a new instruction. Instructions form a DAG. The instruction objects 665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // are owned by the CodeGen object. They do not need to be explicitly 675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // deleted. 685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // For details on the possible parameters refer to <linux/filter.h> 695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Instruction *MakeInstruction(uint16_t code, uint32_t k, 705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Instruction *next = NULL); 715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Instruction *MakeInstruction(uint16_t code, const ErrorCode& err); 725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Instruction *MakeInstruction(uint16_t code, uint32_t k, 735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Instruction *jt, Instruction *jf); 745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Join two (sequences of) instructions. This is useful, if the "next" 765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // parameter had not originally been given in the call to MakeInstruction(), 775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // or if a (conditional) jump still has an unsatisfied target. 785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) void JoinInstructions(Instruction *head, Instruction *tail); 795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 802a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // Traverse the graph of instructions and visit each instruction once. 812a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // Traversal order is implementation-defined. It is acceptable to make 822a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // changes to the graph from within the callback function. These changes 832a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // do not affect traversal. 842a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // The "fnc" function gets called with both the instruction and the opaque 852a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // "aux" pointer. 862a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) void Traverse(Instruction *, void (*fnc)(Instruction *, void *aux), 872a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) void *aux); 882a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Compiles the graph of instructions into a BPF program that can be passed 905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // to the kernel. Please note that this function modifies the graph in place 915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // and must therefore only be called once per graph. 925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) void Compile(Instruction *instructions, Sandbox::Program *program); 935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) private: 955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) friend class CodeGenUnittestHelper; 965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Find all the instructions that are the target of BPF_JMPs. 985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) void FindBranchTargets(const Instruction& instructions, 995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) BranchTargets *branch_targets); 1005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Combine instructions between "head" and "tail" into a new basic block. 1025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Basic blocks are defined as sequences of instructions whose only branch 1035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // target is the very first instruction; furthermore, any BPF_JMP or BPF_RET 1045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // instruction must be at the very end of the basic block. 1055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) BasicBlock *MakeBasicBlock(Instruction *head, Instruction *tail); 1065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Creates a basic block and adds it to "basic_blocks"; sets "first_block" 1085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // if it is still NULL. 1095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) void AddBasicBlock(Instruction *head, Instruction *tail, 1105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const BranchTargets& branch_targets, 1115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) TargetsToBlocks *basic_blocks, BasicBlock **first_block); 1125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Cuts the DAG of instructions into basic blocks. 1145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) BasicBlock *CutGraphIntoBasicBlocks(Instruction *instructions, 1155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const BranchTargets& branch_targets, 1165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) TargetsToBlocks *blocks); 1175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Find common tail sequences of basic blocks and coalesce them. 1195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) void MergeTails(TargetsToBlocks *blocks); 1205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // For each basic block, compute the number of incoming branches. 1225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) void ComputeIncomingBranches(BasicBlock *block, 1235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const TargetsToBlocks& targets_to_blocks, 1245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) IncomingBranches *incoming_branches); 1255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Topologically sort the basic blocks so that all jumps are forward jumps. 1275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // This is a requirement for any well-formed BPF program. 1285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) void TopoSortBasicBlocks(BasicBlock *first_block, 1295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const TargetsToBlocks& blocks, 1305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) BasicBlocks *basic_blocks); 1315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Convert jt_ptr_ and jf_ptr_ fields in BPF_JMP instructions to valid 1335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // jt_ and jf_ jump offsets. This can result in BPF_JA instructions being 1345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // inserted, if we need to jump over more than 256 instructions. 1355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) void ComputeRelativeJumps(BasicBlocks *basic_blocks, 1365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const TargetsToBlocks& targets_to_blocks); 1375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Concatenate instructions from all basic blocks into a BPF program that 1395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // can be passed to the kernel. 1405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) void ConcatenateBasicBlocks(const BasicBlocks&, Sandbox::Program *program); 1415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // We stick all instructions and basic blocks into pools that get destroyed 1435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // when the CodeGen object is destroyed. This way, we neither need to worry 1445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // about explicitly managing ownership, nor do we need to worry about using 1455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // smart pointers in the presence of circular references. 1465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Instructions instructions_; 1475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) BasicBlocks basic_blocks_; 1485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Compile() must only ever be called once as it makes destructive changes 1505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // to the DAG. 1515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) bool compiled_; 1525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}; 1535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} // namespace 1555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#endif // SANDBOX_LINUX_SECCOMP_BPF_CODEGEN_H__ 157