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