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#ifndef SANDBOX_LINUX_SECCOMP_BPF_CODEGEN_H__
6#define SANDBOX_LINUX_SECCOMP_BPF_CODEGEN_H__
7
8#include <map>
9#include <set>
10#include <vector>
11
12#include "sandbox/linux/seccomp-bpf/basicblock.h"
13#include "sandbox/linux/seccomp-bpf/instruction.h"
14#include "sandbox/linux/seccomp-bpf/sandbox_bpf.h"
15
16namespace sandbox {
17
18typedef std::vector<Instruction*> Instructions;
19typedef std::vector<BasicBlock*> BasicBlocks;
20typedef std::map<const Instruction*, int> BranchTargets;
21typedef std::map<const Instruction*, BasicBlock*> TargetsToBlocks;
22typedef std::map<const BasicBlock*, int> IncomingBranches;
23
24// The code generator instantiates a basic compiler that can convert a
25// graph of BPF instructions into a well-formed stream of BPF instructions.
26// Most notably, it ensures that jumps are always forward and don't exceed
27// the limit of 255 instructions imposed by the instruction set.
28//
29// Callers would typically create a new CodeGen object and then use it to
30// build a DAG of Instructions. They'll eventually call Compile() to convert
31// this DAG to a SandboxBPF::Program.
32//
33// Instructions can be chained at the time when they are created, or they
34// can be joined later by calling JoinInstructions().
35//
36//   CodeGen gen;
37//   Instruction *dag, *branch;
38//   dag =
39//     gen.MakeInstruction(BPF_LD+BPF_W+BPF_ABS,
40//                         offsetof(struct arch_seccomp_data, nr),
41//   branch =
42//     gen.MakeInstruction(BPF_JMP+BPF_EQ+BPF_K, __NR_getpid,
43//                         Trap(GetPidHandler, NULL), NULL);
44//   gen.JoinInstructions(branch,
45//     gen.MakeInstruction(BPF_RET+BPF_K, ErrorCode(ErrorCode::ERR_ALLOWED)));
46//
47//   // Simplified code follows; in practice, it is important to avoid calling
48//   // any C++ destructors after starting the sandbox.
49//   SandboxBPF::Program program;
50//   gen.Compile(dag, program);
51//   const struct sock_fprog prog = {
52//     static_cast<unsigned short>(program->size()), &program[0] };
53//   prctl(PR_SET_SECCOMP, SECCOMP_MODE_FILTER, &prog);
54//
55class CodeGen {
56 public:
57  CodeGen();
58  ~CodeGen();
59
60  // This is a helper method that can be used for debugging purposes. It is
61  // not normally called.
62  static void PrintProgram(const SandboxBPF::Program& program);
63
64  // Create a new instruction. Instructions form a DAG. The instruction objects
65  // are owned by the CodeGen object. They do not need to be explicitly
66  // deleted.
67  // For details on the possible parameters refer to <linux/filter.h>
68  Instruction* MakeInstruction(uint16_t code,
69                               uint32_t k,
70                               Instruction* next = NULL);
71  Instruction* MakeInstruction(uint16_t code, const ErrorCode& err);
72  Instruction* MakeInstruction(uint16_t code,
73                               uint32_t k,
74                               Instruction* jt,
75                               Instruction* jf);
76
77  // Join two (sequences of) instructions. This is useful, if the "next"
78  // parameter had not originally been given in the call to MakeInstruction(),
79  // or if a (conditional) jump still has an unsatisfied target.
80  void JoinInstructions(Instruction* head, Instruction* tail);
81
82  // Traverse the graph of instructions and visit each instruction once.
83  // Traversal order is implementation-defined. It is acceptable to make
84  // changes to the graph from within the callback function. These changes
85  // do not affect traversal.
86  // The "fnc" function gets called with both the instruction and the opaque
87  // "aux" pointer.
88  void Traverse(Instruction*, void (*fnc)(Instruction*, void* aux), void* aux);
89
90  // Compiles the graph of instructions into a BPF program that can be passed
91  // to the kernel. Please note that this function modifies the graph in place
92  // and must therefore only be called once per graph.
93  void Compile(Instruction* instructions, SandboxBPF::Program* program);
94
95 private:
96  friend class CodeGenUnittestHelper;
97
98  // Find all the instructions that are the target of BPF_JMPs.
99  void FindBranchTargets(const Instruction& instructions,
100                         BranchTargets* branch_targets);
101
102  // Combine instructions between "head" and "tail" into a new basic block.
103  // Basic blocks are defined as sequences of instructions whose only branch
104  // target is the very first instruction; furthermore, any BPF_JMP or BPF_RET
105  // instruction must be at the very end of the basic block.
106  BasicBlock* MakeBasicBlock(Instruction* head, Instruction* tail);
107
108  // Creates a basic block and adds it to "basic_blocks"; sets "first_block"
109  // if it is still NULL.
110  void AddBasicBlock(Instruction* head,
111                     Instruction* tail,
112                     const BranchTargets& branch_targets,
113                     TargetsToBlocks* basic_blocks,
114                     BasicBlock** first_block);
115
116  // Cuts the DAG of instructions into basic blocks.
117  BasicBlock* CutGraphIntoBasicBlocks(Instruction* instructions,
118                                      const BranchTargets& branch_targets,
119                                      TargetsToBlocks* blocks);
120
121  // Find common tail sequences of basic blocks and coalesce them.
122  void MergeTails(TargetsToBlocks* blocks);
123
124  // For each basic block, compute the number of incoming branches.
125  void ComputeIncomingBranches(BasicBlock* block,
126                               const TargetsToBlocks& targets_to_blocks,
127                               IncomingBranches* incoming_branches);
128
129  // Topologically sort the basic blocks so that all jumps are forward jumps.
130  // This is a requirement for any well-formed BPF program.
131  void TopoSortBasicBlocks(BasicBlock* first_block,
132                           const TargetsToBlocks& blocks,
133                           BasicBlocks* basic_blocks);
134
135  // Convert jt_ptr_ and jf_ptr_ fields in BPF_JMP instructions to valid
136  // jt_ and jf_ jump offsets. This can result in BPF_JA instructions being
137  // inserted, if we need to jump over more than 256 instructions.
138  void ComputeRelativeJumps(BasicBlocks* basic_blocks,
139                            const TargetsToBlocks& targets_to_blocks);
140
141  // Concatenate instructions from all basic blocks into a BPF program that
142  // can be passed to the kernel.
143  void ConcatenateBasicBlocks(const BasicBlocks&, SandboxBPF::Program* program);
144
145  // We stick all instructions and basic blocks into pools that get destroyed
146  // when the CodeGen object is destroyed. This way, we neither need to worry
147  // about explicitly managing ownership, nor do we need to worry about using
148  // smart pointers in the presence of circular references.
149  Instructions instructions_;
150  BasicBlocks basic_blocks_;
151
152  // Compile() must only ever be called once as it makes destructive changes
153  // to the DAG.
154  bool compiled_;
155};
156
157}  // namespace sandbox
158
159#endif  // SANDBOX_LINUX_SECCOMP_BPF_CODEGEN_H__
160