diff options
Diffstat (limited to 'lib/Target/BPF/BPFAbstractMemberAccess.cpp')
| -rw-r--r-- | lib/Target/BPF/BPFAbstractMemberAccess.cpp | 482 |
1 files changed, 482 insertions, 0 deletions
diff --git a/lib/Target/BPF/BPFAbstractMemberAccess.cpp b/lib/Target/BPF/BPFAbstractMemberAccess.cpp new file mode 100644 index 000000000000..51d4cbc8a429 --- /dev/null +++ b/lib/Target/BPF/BPFAbstractMemberAccess.cpp @@ -0,0 +1,482 @@ +//===------ BPFAbstractMemberAccess.cpp - Abstracting Member Accesses -----===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +// +// This pass abstracted struct/union member accesses in order to support +// compile-once run-everywhere (CO-RE). The CO-RE intends to compile the program +// which can run on different kernels. In particular, if bpf program tries to +// access a particular kernel data structure member, the details of the +// intermediate member access will be remembered so bpf loader can do +// necessary adjustment right before program loading. +// +// For example, +// +// struct s { +// int a; +// int b; +// }; +// struct t { +// struct s c; +// int d; +// }; +// struct t e; +// +// For the member access e.c.b, the compiler will generate code +// &e + 4 +// +// The compile-once run-everywhere instead generates the following code +// r = 4 +// &e + r +// The "4" in "r = 4" can be changed based on a particular kernel version. +// For example, on a particular kernel version, if struct s is changed to +// +// struct s { +// int new_field; +// int a; +// int b; +// } +// +// By repeating the member access on the host, the bpf loader can +// adjust "r = 4" as "r = 8". +// +// This feature relies on the following three intrinsic calls: +// addr = preserve_array_access_index(base, dimension, index) +// addr = preserve_union_access_index(base, di_index) +// !llvm.preserve.access.index <union_ditype> +// addr = preserve_struct_access_index(base, gep_index, di_index) +// !llvm.preserve.access.index <struct_ditype> +// +//===----------------------------------------------------------------------===// + +#include "BPF.h" +#include "BPFCORE.h" +#include "BPFTargetMachine.h" +#include "llvm/IR/DebugInfoMetadata.h" +#include "llvm/IR/GlobalVariable.h" +#include "llvm/IR/Instruction.h" +#include "llvm/IR/Instructions.h" +#include "llvm/IR/Module.h" +#include "llvm/IR/Type.h" +#include "llvm/IR/User.h" +#include "llvm/IR/Value.h" +#include "llvm/Pass.h" +#include "llvm/Transforms/Utils/BasicBlockUtils.h" + +#define DEBUG_TYPE "bpf-abstract-member-access" + +namespace llvm { +const std::string BPFCoreSharedInfo::AmaAttr = "btf_ama"; +const std::string BPFCoreSharedInfo::PatchableExtSecName = + ".BPF.patchable_externs"; +} // namespace llvm + +using namespace llvm; + +namespace { + +class BPFAbstractMemberAccess final : public ModulePass { + StringRef getPassName() const override { + return "BPF Abstract Member Access"; + } + + bool runOnModule(Module &M) override; + +public: + static char ID; + BPFAbstractMemberAccess() : ModulePass(ID) {} + +private: + enum : uint32_t { + BPFPreserveArrayAI = 1, + BPFPreserveUnionAI = 2, + BPFPreserveStructAI = 3, + }; + + std::map<std::string, GlobalVariable *> GEPGlobals; + // A map to link preserve_*_access_index instrinsic calls. + std::map<CallInst *, std::pair<CallInst *, uint32_t>> AIChain; + // A map to hold all the base preserve_*_access_index instrinsic calls. + // The base call is not an input of any other preserve_*_access_index + // intrinsics. + std::map<CallInst *, uint32_t> BaseAICalls; + + bool doTransformation(Module &M); + + void traceAICall(CallInst *Call, uint32_t Kind); + void traceBitCast(BitCastInst *BitCast, CallInst *Parent, uint32_t Kind); + void traceGEP(GetElementPtrInst *GEP, CallInst *Parent, uint32_t Kind); + void collectAICallChains(Module &M, Function &F); + + bool IsPreserveDIAccessIndexCall(const CallInst *Call, uint32_t &Kind); + bool removePreserveAccessIndexIntrinsic(Module &M); + void replaceWithGEP(std::vector<CallInst *> &CallList, + uint32_t NumOfZerosIndex, uint32_t DIIndex); + + Value *computeBaseAndAccessStr(CallInst *Call, std::string &AccessStr, + std::string &AccessKey, uint32_t Kind, + MDNode *&TypeMeta); + bool getAccessIndex(const Value *IndexValue, uint64_t &AccessIndex); + bool transformGEPChain(Module &M, CallInst *Call, uint32_t Kind); +}; +} // End anonymous namespace + +char BPFAbstractMemberAccess::ID = 0; +INITIALIZE_PASS(BPFAbstractMemberAccess, DEBUG_TYPE, + "abstracting struct/union member accessees", false, false) + +ModulePass *llvm::createBPFAbstractMemberAccess() { + return new BPFAbstractMemberAccess(); +} + +bool BPFAbstractMemberAccess::runOnModule(Module &M) { + LLVM_DEBUG(dbgs() << "********** Abstract Member Accesses **********\n"); + + // Bail out if no debug info. + if (empty(M.debug_compile_units())) + return false; + + return doTransformation(M); +} + +/// Check whether a call is a preserve_*_access_index intrinsic call or not. +bool BPFAbstractMemberAccess::IsPreserveDIAccessIndexCall(const CallInst *Call, + uint32_t &Kind) { + if (!Call) + return false; + + const auto *GV = dyn_cast<GlobalValue>(Call->getCalledValue()); + if (!GV) + return false; + if (GV->getName().startswith("llvm.preserve.array.access.index")) { + Kind = BPFPreserveArrayAI; + return true; + } + if (GV->getName().startswith("llvm.preserve.union.access.index")) { + Kind = BPFPreserveUnionAI; + return true; + } + if (GV->getName().startswith("llvm.preserve.struct.access.index")) { + Kind = BPFPreserveStructAI; + return true; + } + + return false; +} + +void BPFAbstractMemberAccess::replaceWithGEP(std::vector<CallInst *> &CallList, + uint32_t DimensionIndex, + uint32_t GEPIndex) { + for (auto Call : CallList) { + uint32_t Dimension = 1; + if (DimensionIndex > 0) + Dimension = cast<ConstantInt>(Call->getArgOperand(DimensionIndex)) + ->getZExtValue(); + + Constant *Zero = + ConstantInt::get(Type::getInt32Ty(Call->getParent()->getContext()), 0); + SmallVector<Value *, 4> IdxList; + for (unsigned I = 0; I < Dimension; ++I) + IdxList.push_back(Zero); + IdxList.push_back(Call->getArgOperand(GEPIndex)); + + auto *GEP = GetElementPtrInst::CreateInBounds(Call->getArgOperand(0), + IdxList, "", Call); + Call->replaceAllUsesWith(GEP); + Call->eraseFromParent(); + } +} + +bool BPFAbstractMemberAccess::removePreserveAccessIndexIntrinsic(Module &M) { + std::vector<CallInst *> PreserveArrayIndexCalls; + std::vector<CallInst *> PreserveUnionIndexCalls; + std::vector<CallInst *> PreserveStructIndexCalls; + bool Found = false; + + for (Function &F : M) + for (auto &BB : F) + for (auto &I : BB) { + auto *Call = dyn_cast<CallInst>(&I); + uint32_t Kind; + if (!IsPreserveDIAccessIndexCall(Call, Kind)) + continue; + + Found = true; + if (Kind == BPFPreserveArrayAI) + PreserveArrayIndexCalls.push_back(Call); + else if (Kind == BPFPreserveUnionAI) + PreserveUnionIndexCalls.push_back(Call); + else + PreserveStructIndexCalls.push_back(Call); + } + + // do the following transformation: + // . addr = preserve_array_access_index(base, dimension, index) + // is transformed to + // addr = GEP(base, dimenion's zero's, index) + // . addr = preserve_union_access_index(base, di_index) + // is transformed to + // addr = base, i.e., all usages of "addr" are replaced by "base". + // . addr = preserve_struct_access_index(base, gep_index, di_index) + // is transformed to + // addr = GEP(base, 0, gep_index) + replaceWithGEP(PreserveArrayIndexCalls, 1, 2); + replaceWithGEP(PreserveStructIndexCalls, 0, 1); + for (auto Call : PreserveUnionIndexCalls) { + Call->replaceAllUsesWith(Call->getArgOperand(0)); + Call->eraseFromParent(); + } + + return Found; +} + +void BPFAbstractMemberAccess::traceAICall(CallInst *Call, uint32_t Kind) { + for (User *U : Call->users()) { + Instruction *Inst = dyn_cast<Instruction>(U); + if (!Inst) + continue; + + if (auto *BI = dyn_cast<BitCastInst>(Inst)) { + traceBitCast(BI, Call, Kind); + } else if (auto *CI = dyn_cast<CallInst>(Inst)) { + uint32_t CIKind; + if (IsPreserveDIAccessIndexCall(CI, CIKind)) { + AIChain[CI] = std::make_pair(Call, Kind); + traceAICall(CI, CIKind); + } else { + BaseAICalls[Call] = Kind; + } + } else if (auto *GI = dyn_cast<GetElementPtrInst>(Inst)) { + if (GI->hasAllZeroIndices()) + traceGEP(GI, Call, Kind); + else + BaseAICalls[Call] = Kind; + } + } +} + +void BPFAbstractMemberAccess::traceBitCast(BitCastInst *BitCast, + CallInst *Parent, uint32_t Kind) { + for (User *U : BitCast->users()) { + Instruction *Inst = dyn_cast<Instruction>(U); + if (!Inst) + continue; + + if (auto *BI = dyn_cast<BitCastInst>(Inst)) { + traceBitCast(BI, Parent, Kind); + } else if (auto *CI = dyn_cast<CallInst>(Inst)) { + uint32_t CIKind; + if (IsPreserveDIAccessIndexCall(CI, CIKind)) { + AIChain[CI] = std::make_pair(Parent, Kind); + traceAICall(CI, CIKind); + } else { + BaseAICalls[Parent] = Kind; + } + } else if (auto *GI = dyn_cast<GetElementPtrInst>(Inst)) { + if (GI->hasAllZeroIndices()) + traceGEP(GI, Parent, Kind); + else + BaseAICalls[Parent] = Kind; + } + } +} + +void BPFAbstractMemberAccess::traceGEP(GetElementPtrInst *GEP, CallInst *Parent, + uint32_t Kind) { + for (User *U : GEP->users()) { + Instruction *Inst = dyn_cast<Instruction>(U); + if (!Inst) + continue; + + if (auto *BI = dyn_cast<BitCastInst>(Inst)) { + traceBitCast(BI, Parent, Kind); + } else if (auto *CI = dyn_cast<CallInst>(Inst)) { + uint32_t CIKind; + if (IsPreserveDIAccessIndexCall(CI, CIKind)) { + AIChain[CI] = std::make_pair(Parent, Kind); + traceAICall(CI, CIKind); + } else { + BaseAICalls[Parent] = Kind; + } + } else if (auto *GI = dyn_cast<GetElementPtrInst>(Inst)) { + if (GI->hasAllZeroIndices()) + traceGEP(GI, Parent, Kind); + else + BaseAICalls[Parent] = Kind; + } + } +} + +void BPFAbstractMemberAccess::collectAICallChains(Module &M, Function &F) { + AIChain.clear(); + BaseAICalls.clear(); + + for (auto &BB : F) + for (auto &I : BB) { + uint32_t Kind; + auto *Call = dyn_cast<CallInst>(&I); + if (!IsPreserveDIAccessIndexCall(Call, Kind) || + AIChain.find(Call) != AIChain.end()) + continue; + + traceAICall(Call, Kind); + } +} + +/// Get access index from the preserve_*_access_index intrinsic calls. +bool BPFAbstractMemberAccess::getAccessIndex(const Value *IndexValue, + uint64_t &AccessIndex) { + const ConstantInt *CV = dyn_cast<ConstantInt>(IndexValue); + if (!CV) + return false; + + AccessIndex = CV->getValue().getZExtValue(); + return true; +} + +/// Compute the base of the whole preserve_*_access_index chains, i.e., the base +/// pointer of the first preserve_*_access_index call, and construct the access +/// string, which will be the name of a global variable. +Value *BPFAbstractMemberAccess::computeBaseAndAccessStr(CallInst *Call, + std::string &AccessStr, + std::string &AccessKey, + uint32_t Kind, + MDNode *&TypeMeta) { + Value *Base = nullptr; + std::vector<uint64_t> AccessIndices; + uint64_t TypeNameIndex = 0; + std::string LastTypeName; + + while (Call) { + // Base of original corresponding GEP + Base = Call->getArgOperand(0); + + // Type Name + std::string TypeName; + MDNode *MDN; + if (Kind == BPFPreserveUnionAI || Kind == BPFPreserveStructAI) { + MDN = Call->getMetadata(LLVMContext::MD_preserve_access_index); + if (!MDN) + return nullptr; + + DIType *Ty = dyn_cast<DIType>(MDN); + if (!Ty) + return nullptr; + + TypeName = Ty->getName(); + } + + // Access Index + uint64_t AccessIndex; + uint32_t ArgIndex = (Kind == BPFPreserveUnionAI) ? 1 : 2; + if (!getAccessIndex(Call->getArgOperand(ArgIndex), AccessIndex)) + return nullptr; + + AccessIndices.push_back(AccessIndex); + if (TypeName.size()) { + TypeNameIndex = AccessIndices.size() - 1; + LastTypeName = TypeName; + TypeMeta = MDN; + } + + Kind = AIChain[Call].second; + Call = AIChain[Call].first; + } + + // The intial type name is required. + // FIXME: if the initial type access is an array index, e.g., + // &a[3].b.c, only one dimentional array is supported. + if (!LastTypeName.size() || AccessIndices.size() > TypeNameIndex + 2) + return nullptr; + + // Construct the type string AccessStr. + for (unsigned I = 0; I < AccessIndices.size(); ++I) + AccessStr = std::to_string(AccessIndices[I]) + ":" + AccessStr; + + if (TypeNameIndex == AccessIndices.size() - 1) + AccessStr = "0:" + AccessStr; + + // Access key is the type name + access string, uniquely identifying + // one kernel memory access. + AccessKey = LastTypeName + ":" + AccessStr; + + return Base; +} + +/// Call/Kind is the base preserve_*_access_index() call. Attempts to do +/// transformation to a chain of relocable GEPs. +bool BPFAbstractMemberAccess::transformGEPChain(Module &M, CallInst *Call, + uint32_t Kind) { + std::string AccessStr, AccessKey; + MDNode *TypeMeta = nullptr; + Value *Base = + computeBaseAndAccessStr(Call, AccessStr, AccessKey, Kind, TypeMeta); + if (!Base) + return false; + + // Do the transformation + // For any original GEP Call and Base %2 like + // %4 = bitcast %struct.net_device** %dev1 to i64* + // it is transformed to: + // %6 = load __BTF_0:sk_buff:0:0:2:0: + // %7 = bitcast %struct.sk_buff* %2 to i8* + // %8 = getelementptr i8, i8* %7, %6 + // %9 = bitcast i8* %8 to i64* + // using %9 instead of %4 + // The original Call inst is removed. + BasicBlock *BB = Call->getParent(); + GlobalVariable *GV; + + if (GEPGlobals.find(AccessKey) == GEPGlobals.end()) { + GV = new GlobalVariable(M, Type::getInt64Ty(BB->getContext()), false, + GlobalVariable::ExternalLinkage, NULL, AccessStr); + GV->addAttribute(BPFCoreSharedInfo::AmaAttr); + // Set the metadata (debuginfo types) for the global. + if (TypeMeta) + GV->setMetadata(LLVMContext::MD_preserve_access_index, TypeMeta); + GEPGlobals[AccessKey] = GV; + } else { + GV = GEPGlobals[AccessKey]; + } + + // Load the global variable. + auto *LDInst = new LoadInst(Type::getInt64Ty(BB->getContext()), GV); + BB->getInstList().insert(Call->getIterator(), LDInst); + + // Generate a BitCast + auto *BCInst = new BitCastInst(Base, Type::getInt8PtrTy(BB->getContext())); + BB->getInstList().insert(Call->getIterator(), BCInst); + + // Generate a GetElementPtr + auto *GEP = GetElementPtrInst::Create(Type::getInt8Ty(BB->getContext()), + BCInst, LDInst); + BB->getInstList().insert(Call->getIterator(), GEP); + + // Generate a BitCast + auto *BCInst2 = new BitCastInst(GEP, Call->getType()); + BB->getInstList().insert(Call->getIterator(), BCInst2); + + Call->replaceAllUsesWith(BCInst2); + Call->eraseFromParent(); + + return true; +} + +bool BPFAbstractMemberAccess::doTransformation(Module &M) { + bool Transformed = false; + + for (Function &F : M) { + // Collect PreserveDIAccessIndex Intrinsic call chains. + // The call chains will be used to generate the access + // patterns similar to GEP. + collectAICallChains(M, F); + + for (auto &C : BaseAICalls) + Transformed = transformGEPChain(M, C.first, C.second) || Transformed; + } + + return removePreserveAccessIndexIntrinsic(M) || Transformed; +} |