1//===-- BPFFuncTable.cpp - Call functions through a table -----------------===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9// A program that keeps its data in arena keeps pointers to functions there too:
10// vtables, closures, Box<dyn Trait>. Arena is shared with user space, so what
11// is loaded from it is a number and the kernel does not let callx take it.
12//
13// Make the pointer to a function a number to begin with: the index of the
14// function in a table that is read-only data.
15// &f index of f
16// (*p)(...) __bpf_func_table[min(p - first, cnt - 1) + first](...)
17// The functions of one type are next to each other in the table: 'first' and
18// 'cnt' are those of the type of the call. A number that is not an index of
19// such function calls the last one of them. That is not what the program
20// meant, but it is a function that takes what the call passes.
21//
22// The kernel knows the pointers to functions in read-only data. A load at
23// an offset that is not constant is fine as long as there is such a pointer at
24// every offset it can be at. So callx gets a pointer to a function again and
25// there is nothing for a loader or the kernel to do.
26//
27// 0 is not an index, so that null stays null. When there is one function of
28// the type the call is direct. When there is none it is a trap.
29//
30// A function that is passed to a helper or to a kfunc stays a function, also
31// when it is one of several: cond ? cb1 : cb2.
32//
33// All functions whose address is taken have to be in the module and static.
34//
35//===----------------------------------------------------------------------===//
36
37#include "BPF.h"
38#include "llvm/ADT/MapVector.h"
39#include "llvm/ADT/SetVector.h"
40#include "llvm/IR/Constants.h"
41#include "llvm/IR/DiagnosticInfo.h"
42#include "llvm/IR/IRBuilder.h"
43#include "llvm/IR/InstIterator.h"
44#include "llvm/IR/Instructions.h"
45#include "llvm/IR/Module.h"
46#include "llvm/Pass.h"
47#include "llvm/Transforms/Utils/ModuleUtils.h"
48
49using namespace llvm;
50
51#define DEBUG_TYPE "bpf-func-table"
52
53namespace {
54
55/// The functions of one type: where they start in the table.
56struct FuncRange {
57 uint64_t First = 0;
58 SmallVector<Function *, 4> Funcs;
59};
60
61} // namespace
62
63/// The address of a function in another section is the address of a program,
64/// e.g. in struct_ops.
65static bool isInText(const Function &F) {
66 return !F.isDeclaration() && !F.hasSection();
67}
68
69/// A callback: bpf_loop(), bpf_timer_set_callback() and co. The kernel calls
70/// it and wants the function. A helper is a number, a kfunc a declaration.
71static bool isCallbackUse(const Use &U, SmallPtrSetImpl<const User *> &Seen) {
72 const User *Usr = U.getUser();
73
74 // cond ? cb1 : cb2, as long as nothing else is done with the result. A call
75 // of it goes through the table and wants an index.
76 if (isa<SelectInst, PHINode>(Val: Usr))
77 return !Seen.insert(Ptr: Usr).second || all_of(Range: Usr->uses(), P: [&](const Use &U) {
78 return isCallbackUse(U, Seen);
79 });
80
81 const auto *CB = dyn_cast<CallBase>(Val: Usr);
82 if (!CB || CB->isCallee(U: &U))
83 return false;
84 const Value *Callee = CB->getCalledOperand()->stripPointerCasts();
85 const auto *F = dyn_cast<Function>(Val: Callee);
86 return F ? F->isDeclaration() && !F->isIntrinsic() : isa<Constant>(Val: Callee);
87}
88
89/// The use is the address of the function as a value.
90static bool isAddressUse(const Use &U) {
91 const User *Usr = U.getUser();
92 const auto *CB = dyn_cast<CallBase>(Val: Usr);
93 SmallPtrSet<const User *, 4> Seen;
94
95 if ((CB && CB->isCallee(U: &U)) || isCallbackUse(U, Seen))
96 return false;
97 // Personality, prefix and prologue data, aliases.
98 return !isa<BlockAddress, NoCFIValue, Function, GlobalAlias, GlobalIFunc>(
99 Val: Usr);
100}
101
102static void replaceAddress(Function &F, Constant *Index) {
103 SmallSetVector<Constant *, 4> Constants;
104
105 for (Use &U : make_early_inc_range(Range: F.uses())) {
106 if (!isAddressUse(U))
107 continue;
108 // Constants are uniqued: the operand cannot be set.
109 auto *C = dyn_cast<Constant>(Val: U.getUser());
110 if (C && !isa<GlobalValue>(Val: C))
111 Constants.insert(X: C);
112 else
113 U.set(Index);
114 }
115 for (Constant *C : Constants)
116 C->handleOperandChange(&F, Index);
117}
118
119static bool runFuncTable(Module &M) {
120 LLVMContext &C = M.getContext();
121 const DataLayout &DL = M.getDataLayout();
122 Type *I64 = Type::getInt64Ty(C);
123 PointerType *Ptr = PointerType::getUnqual(C);
124 MapVector<FunctionType *, FuncRange> Types;
125 SmallVector<CallBase *, 16> Calls;
126 SmallVector<GlobalValue *, 4> Used, CompilerUsed;
127 SmallVector<Constant *, 16> Table;
128
129 // They hold functions, not their addresses.
130 if (GlobalVariable *GV = collectUsedGlobalVariables(M, Vec&: Used, CompilerUsed: false))
131 GV->eraseFromParent();
132 if (GlobalVariable *GV = collectUsedGlobalVariables(M, Vec&: CompilerUsed, CompilerUsed: true))
133 GV->eraseFromParent();
134 bool Changed = !Used.empty() || !CompilerUsed.empty();
135
136 for (Function &F : M) {
137 if (isInText(F) && any_of(Range: F.uses(), P: isAddressUse)) {
138 // callx takes static functions only. An address that is left as it is
139 // would be an index out of range: a call of another function.
140 if (!F.hasLocalLinkage())
141 C.diagnose(DI: DiagnosticInfoUnsupported(
142 F, "BPF func-table cannot take the address of a function that is "
143 "not static"));
144 Types[F.getFunctionType()].Funcs.push_back(Elt: &F);
145 }
146 for (Instruction &I : instructions(F)) {
147 auto *CB = dyn_cast<CallBase>(Val: &I);
148 // A constant is a function or the number of a helper.
149 if (CB && !CB->isInlineAsm() && !isa<Constant>(Val: CB->getCalledOperand()))
150 Calls.push_back(Elt: CB);
151 }
152 }
153
154 Table.push_back(Elt: ConstantPointerNull::get(T: Ptr));
155 for (auto &[FTy, R] : Types) {
156 R.First = Table.size();
157 for (Function *F : R.Funcs) {
158 replaceAddress(F&: *F, Index: ConstantExpr::getIntToPtr(
159 C: ConstantInt::get(Ty: I64, V: Table.size()), Ty: Ptr));
160 Table.push_back(Elt: F);
161 }
162 }
163
164 appendToUsed(M, Values: Used);
165 appendToCompilerUsed(M, Values: CompilerUsed);
166 if (Calls.empty() && Types.empty())
167 return Changed;
168
169 ArrayType *TableTy = ArrayType::get(ElementType: Ptr, NumElements: Table.size());
170 GlobalVariable *GV = nullptr;
171
172 for (CallBase *CB : Calls) {
173 const FuncRange &R = Types.lookup(Key: CB->getFunctionType());
174 uint64_t Cnt = R.Funcs.size();
175
176 // Nothing to call. The kernel rejects the trap if it is reachable. A call
177 // of null alone is undefined behaviour: what leads to nothing else is
178 // removed with it, the exit of a loop for example.
179 if (!Cnt) {
180 IRBuilder<>(CB).CreateIntrinsic(ID: Intrinsic::trap, Args: {});
181 CB->setCalledOperand(ConstantPointerNull::get(T: Ptr));
182 continue;
183 }
184 if (Cnt == 1) {
185 CB->setCalledOperand(R.Funcs[0]);
186 continue;
187 }
188 if (!GV)
189 GV = new GlobalVariable(M, TableTy, true, GlobalValue::InternalLinkage,
190 ConstantArray::get(T: TableTy, V: Table),
191 "__bpf_func_table");
192
193 IRBuilder<> B(CB);
194 B.disableGEPCanonicalization();
195 Value *Idx = B.CreatePtrToInt(V: CB->getCalledOperand(), DestTy: I64);
196 Idx = B.CreateSub(LHS: Idx, RHS: ConstantInt::get(Ty: I64, V: R.First));
197 Idx = B.CreateBinaryIntrinsic(ID: Intrinsic::umin, LHS: Idx,
198 RHS: ConstantInt::get(Ty: I64, V: Cnt - 1));
199 Constant *First = ConstantExpr::getInBoundsPtrAdd(
200 Ptr: GV, Offset: ConstantInt::get(Ty: I64, V: R.First * DL.getPointerSize()));
201 Value *Slot = B.CreateInBoundsGEP(Ty: Ptr, Ptr: First, IdxList: Idx);
202 CB->setCalledOperand(B.CreateLoad(Ty: Ptr, Ptr: Slot));
203 }
204 return true;
205}
206
207namespace {
208
209struct BPFFuncTableLegacy : public ModulePass {
210 static char ID;
211 BPFFuncTableLegacy() : ModulePass(ID) {}
212 StringRef getPassName() const override { return "BPF Function Table"; }
213 bool runOnModule(Module &M) override { return runFuncTable(M); }
214};
215
216} // namespace
217
218char BPFFuncTableLegacy::ID = 0;
219
220INITIALIZE_PASS(BPFFuncTableLegacy, DEBUG_TYPE, "BPF Function Table", false,
221 false)
222
223ModulePass *llvm::createBPFFuncTablePass() { return new BPFFuncTableLegacy(); }
224
225PreservedAnalyses BPFFuncTablePass::run(Module &M, ModuleAnalysisManager &AM) {
226 return runFuncTable(M) ? PreservedAnalyses::none() : PreservedAnalyses::all();
227}
228