| 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 | |
| 49 | using namespace llvm; |
| 50 | |
| 51 | #define DEBUG_TYPE "bpf-func-table" |
| 52 | |
| 53 | namespace { |
| 54 | |
| 55 | /// The functions of one type: where they start in the table. |
| 56 | struct 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. |
| 65 | static 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. |
| 71 | static 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. |
| 90 | static 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 | |
| 102 | static 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 | |
| 119 | static 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 | |
| 207 | namespace { |
| 208 | |
| 209 | struct 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 | |
| 218 | char BPFFuncTableLegacy::ID = 0; |
| 219 | |
| 220 | INITIALIZE_PASS(BPFFuncTableLegacy, DEBUG_TYPE, "BPF Function Table" , false, |
| 221 | false) |
| 222 | |
| 223 | ModulePass *llvm::createBPFFuncTablePass() { return new BPFFuncTableLegacy(); } |
| 224 | |
| 225 | PreservedAnalyses BPFFuncTablePass::run(Module &M, ModuleAnalysisManager &AM) { |
| 226 | return runFuncTable(M) ? PreservedAnalyses::none() : PreservedAnalyses::all(); |
| 227 | } |
| 228 | |