1 //===- ShadowStackGCLowering.cpp - Custom lowering for shadow-stack gc ----===//
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 // This file contains the custom lowering code required by the shadow-stack GC
10 // strategy.
11 //
12 // This pass implements the code transformation described in this paper:
13 // "Accurate Garbage Collection in an Uncooperative Environment"
14 // Fergus Henderson, ISMM, 2002
15 //
16 //===----------------------------------------------------------------------===//
17
18 #include "llvm/CodeGen/ShadowStackGCLowering.h"
19 #include "llvm/ADT/SmallVector.h"
20 #include "llvm/ADT/StringExtras.h"
21 #include "llvm/Analysis/DomTreeUpdater.h"
22 #include "llvm/CodeGen/GCMetadata.h"
23 #include "llvm/CodeGen/Passes.h"
24 #include "llvm/IR/BasicBlock.h"
25 #include "llvm/IR/Constant.h"
26 #include "llvm/IR/Constants.h"
27 #include "llvm/IR/DerivedTypes.h"
28 #include "llvm/IR/Dominators.h"
29 #include "llvm/IR/Function.h"
30 #include "llvm/IR/GlobalValue.h"
31 #include "llvm/IR/GlobalVariable.h"
32 #include "llvm/IR/IRBuilder.h"
33 #include "llvm/IR/Instructions.h"
34 #include "llvm/IR/IntrinsicInst.h"
35 #include "llvm/IR/Intrinsics.h"
36 #include "llvm/IR/Module.h"
37 #include "llvm/IR/Type.h"
38 #include "llvm/IR/Value.h"
39 #include "llvm/InitializePasses.h"
40 #include "llvm/Pass.h"
41 #include "llvm/Support/Casting.h"
42 #include "llvm/Transforms/Utils/EscapeEnumerator.h"
43 #include <cassert>
44 #include <optional>
45 #include <string>
46 #include <utility>
47 #include <vector>
48
49 using namespace llvm;
50
51 #define DEBUG_TYPE "shadow-stack-gc-lowering"
52
53 namespace {
54
55 class ShadowStackGCLoweringImpl {
56 /// RootChain - This is the global linked-list that contains the chain of GC
57 /// roots.
58 GlobalVariable *Head = nullptr;
59
60 /// StackEntryTy - Abstract type of a link in the shadow stack.
61 StructType *StackEntryTy = nullptr;
62 StructType *FrameMapTy = nullptr;
63
64 /// Roots - GC roots in the current function. Each is a pair of the
65 /// intrinsic call and its corresponding alloca.
66 std::vector<std::pair<CallInst *, AllocaInst *>> Roots;
67
68 public:
69 ShadowStackGCLoweringImpl() = default;
70
71 bool doInitialization(Module &M);
72 bool runOnFunction(Function &F, DomTreeUpdater *DTU);
73
74 private:
75 bool IsNullValue(Value *V);
76 Constant *GetFrameMap(Function &F);
77 Type *GetConcreteStackEntryType(Function &F);
78 void CollectRoots(Function &F);
79
80 static GetElementPtrInst *CreateGEP(LLVMContext &Context, IRBuilder<> &B,
81 Type *Ty, Value *BasePtr, int Idx1,
82 const char *Name);
83 static GetElementPtrInst *CreateGEP(LLVMContext &Context, IRBuilder<> &B,
84 Type *Ty, Value *BasePtr, int Idx1, int Idx2,
85 const char *Name);
86 };
87
88 class ShadowStackGCLowering : public FunctionPass {
89 ShadowStackGCLoweringImpl Impl;
90
91 public:
92 static char ID;
93
94 ShadowStackGCLowering();
95
doInitialization(Module & M)96 bool doInitialization(Module &M) override { return Impl.doInitialization(M); }
getAnalysisUsage(AnalysisUsage & AU) const97 void getAnalysisUsage(AnalysisUsage &AU) const override {
98 AU.addPreserved<DominatorTreeWrapperPass>();
99 }
runOnFunction(Function & F)100 bool runOnFunction(Function &F) override {
101 std::optional<DomTreeUpdater> DTU;
102 if (auto *DTWP = getAnalysisIfAvailable<DominatorTreeWrapperPass>())
103 DTU.emplace(DTWP->getDomTree(), DomTreeUpdater::UpdateStrategy::Lazy);
104 return Impl.runOnFunction(F, DTU ? &*DTU : nullptr);
105 }
106 };
107
108 } // end anonymous namespace
109
run(Module & M,ModuleAnalysisManager & MAM)110 PreservedAnalyses ShadowStackGCLoweringPass::run(Module &M,
111 ModuleAnalysisManager &MAM) {
112 auto &Map = MAM.getResult<CollectorMetadataAnalysis>(M);
113 if (Map.StrategyMap.contains("shadow-stack"))
114 return PreservedAnalyses::all();
115
116 ShadowStackGCLoweringImpl Impl;
117 bool Changed = Impl.doInitialization(M);
118 for (auto &F : M) {
119 auto &FAM =
120 MAM.getResult<FunctionAnalysisManagerModuleProxy>(M).getManager();
121 auto *DT = FAM.getCachedResult<DominatorTreeAnalysis>(F);
122 DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Lazy);
123 Changed |= Impl.runOnFunction(F, DT ? &DTU : nullptr);
124 }
125
126 if (!Changed)
127 return PreservedAnalyses::all();
128 PreservedAnalyses PA;
129 PA.preserve<DominatorTreeAnalysis>();
130 return PA;
131 }
132
133 char ShadowStackGCLowering::ID = 0;
134 char &llvm::ShadowStackGCLoweringID = ShadowStackGCLowering::ID;
135
136 INITIALIZE_PASS_BEGIN(ShadowStackGCLowering, DEBUG_TYPE,
137 "Shadow Stack GC Lowering", false, false)
INITIALIZE_PASS_DEPENDENCY(GCModuleInfo)138 INITIALIZE_PASS_DEPENDENCY(GCModuleInfo)
139 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
140 INITIALIZE_PASS_END(ShadowStackGCLowering, DEBUG_TYPE,
141 "Shadow Stack GC Lowering", false, false)
142
143 FunctionPass *llvm::createShadowStackGCLoweringPass() { return new ShadowStackGCLowering(); }
144
ShadowStackGCLowering()145 ShadowStackGCLowering::ShadowStackGCLowering() : FunctionPass(ID) {
146 initializeShadowStackGCLoweringPass(*PassRegistry::getPassRegistry());
147 }
148
GetFrameMap(Function & F)149 Constant *ShadowStackGCLoweringImpl::GetFrameMap(Function &F) {
150 // doInitialization creates the abstract type of this value.
151 Type *VoidPtr = PointerType::getUnqual(F.getContext());
152
153 // Truncate the ShadowStackDescriptor if some metadata is null.
154 unsigned NumMeta = 0;
155 SmallVector<Constant *, 16> Metadata;
156 for (unsigned I = 0; I != Roots.size(); ++I) {
157 Constant *C = cast<Constant>(Roots[I].first->getArgOperand(1));
158 if (!C->isNullValue())
159 NumMeta = I + 1;
160 Metadata.push_back(C);
161 }
162 Metadata.resize(NumMeta);
163
164 Type *Int32Ty = Type::getInt32Ty(F.getContext());
165
166 Constant *BaseElts[] = {
167 ConstantInt::get(Int32Ty, Roots.size(), false),
168 ConstantInt::get(Int32Ty, NumMeta, false),
169 };
170
171 Constant *DescriptorElts[] = {
172 ConstantStruct::get(FrameMapTy, BaseElts),
173 ConstantArray::get(ArrayType::get(VoidPtr, NumMeta), Metadata)};
174
175 Type *EltTys[] = {DescriptorElts[0]->getType(), DescriptorElts[1]->getType()};
176 StructType *STy = StructType::create(EltTys, "gc_map." + utostr(NumMeta));
177
178 Constant *FrameMap = ConstantStruct::get(STy, DescriptorElts);
179
180 // FIXME: Is this actually dangerous as WritingAnLLVMPass.html claims? Seems
181 // that, short of multithreaded LLVM, it should be safe; all that is
182 // necessary is that a simple Module::iterator loop not be invalidated.
183 // Appending to the GlobalVariable list is safe in that sense.
184 //
185 // All of the output passes emit globals last. The ExecutionEngine
186 // explicitly supports adding globals to the module after
187 // initialization.
188 //
189 // Still, if it isn't deemed acceptable, then this transformation needs
190 // to be a ModulePass (which means it cannot be in the 'llc' pipeline
191 // (which uses a FunctionPassManager (which segfaults (not asserts) if
192 // provided a ModulePass))).
193 Constant *GV = new GlobalVariable(*F.getParent(), FrameMap->getType(), true,
194 GlobalVariable::InternalLinkage, FrameMap,
195 "__gc_" + F.getName());
196
197 Constant *GEPIndices[2] = {
198 ConstantInt::get(Type::getInt32Ty(F.getContext()), 0),
199 ConstantInt::get(Type::getInt32Ty(F.getContext()), 0)};
200 return ConstantExpr::getGetElementPtr(FrameMap->getType(), GV, GEPIndices);
201 }
202
GetConcreteStackEntryType(Function & F)203 Type *ShadowStackGCLoweringImpl::GetConcreteStackEntryType(Function &F) {
204 // doInitialization creates the generic version of this type.
205 std::vector<Type *> EltTys;
206 EltTys.push_back(StackEntryTy);
207 for (const std::pair<CallInst *, AllocaInst *> &Root : Roots)
208 EltTys.push_back(Root.second->getAllocatedType());
209
210 return StructType::create(EltTys, ("gc_stackentry." + F.getName()).str());
211 }
212
213 /// doInitialization - If this module uses the GC intrinsics, find them now. If
214 /// not, exit fast.
doInitialization(Module & M)215 bool ShadowStackGCLoweringImpl::doInitialization(Module &M) {
216 bool Active = false;
217 for (Function &F : M) {
218 if (F.hasGC() && F.getGC() == "shadow-stack") {
219 Active = true;
220 break;
221 }
222 }
223 if (!Active)
224 return false;
225
226 // struct FrameMap {
227 // int32_t NumRoots; // Number of roots in stack frame.
228 // int32_t NumMeta; // Number of metadata descriptors. May be < NumRoots.
229 // void *Meta[]; // May be absent for roots without metadata.
230 // };
231 std::vector<Type *> EltTys;
232 // 32 bits is ok up to a 32GB stack frame. :)
233 EltTys.push_back(Type::getInt32Ty(M.getContext()));
234 // Specifies length of variable length array.
235 EltTys.push_back(Type::getInt32Ty(M.getContext()));
236 FrameMapTy = StructType::create(EltTys, "gc_map");
237 PointerType *FrameMapPtrTy = PointerType::getUnqual(FrameMapTy);
238
239 // struct StackEntry {
240 // ShadowStackEntry *Next; // Caller's stack entry.
241 // FrameMap *Map; // Pointer to constant FrameMap.
242 // void *Roots[]; // Stack roots (in-place array, so we pretend).
243 // };
244
245 StackEntryTy = StructType::create(M.getContext(), "gc_stackentry");
246
247 EltTys.clear();
248 EltTys.push_back(PointerType::getUnqual(StackEntryTy));
249 EltTys.push_back(FrameMapPtrTy);
250 StackEntryTy->setBody(EltTys);
251 PointerType *StackEntryPtrTy = PointerType::getUnqual(StackEntryTy);
252
253 // Get the root chain if it already exists.
254 Head = M.getGlobalVariable("llvm_gc_root_chain");
255 if (!Head) {
256 // If the root chain does not exist, insert a new one with linkonce
257 // linkage!
258 Head = new GlobalVariable(
259 M, StackEntryPtrTy, false, GlobalValue::LinkOnceAnyLinkage,
260 Constant::getNullValue(StackEntryPtrTy), "llvm_gc_root_chain");
261 } else if (Head->hasExternalLinkage() && Head->isDeclaration()) {
262 Head->setInitializer(Constant::getNullValue(StackEntryPtrTy));
263 Head->setLinkage(GlobalValue::LinkOnceAnyLinkage);
264 }
265
266 return true;
267 }
268
IsNullValue(Value * V)269 bool ShadowStackGCLoweringImpl::IsNullValue(Value *V) {
270 if (Constant *C = dyn_cast<Constant>(V))
271 return C->isNullValue();
272 return false;
273 }
274
CollectRoots(Function & F)275 void ShadowStackGCLoweringImpl::CollectRoots(Function &F) {
276 // FIXME: Account for original alignment. Could fragment the root array.
277 // Approach 1: Null initialize empty slots at runtime. Yuck.
278 // Approach 2: Emit a map of the array instead of just a count.
279
280 assert(Roots.empty() && "Not cleaned up?");
281
282 SmallVector<std::pair<CallInst *, AllocaInst *>, 16> MetaRoots;
283
284 for (BasicBlock &BB : F)
285 for (Instruction &I : BB)
286 if (IntrinsicInst *CI = dyn_cast<IntrinsicInst>(&I))
287 if (Function *F = CI->getCalledFunction())
288 if (F->getIntrinsicID() == Intrinsic::gcroot) {
289 std::pair<CallInst *, AllocaInst *> Pair = std::make_pair(
290 CI,
291 cast<AllocaInst>(CI->getArgOperand(0)->stripPointerCasts()));
292 if (IsNullValue(CI->getArgOperand(1)))
293 Roots.push_back(Pair);
294 else
295 MetaRoots.push_back(Pair);
296 }
297
298 // Number roots with metadata (usually empty) at the beginning, so that the
299 // FrameMap::Meta array can be elided.
300 Roots.insert(Roots.begin(), MetaRoots.begin(), MetaRoots.end());
301 }
302
303 GetElementPtrInst *
CreateGEP(LLVMContext & Context,IRBuilder<> & B,Type * Ty,Value * BasePtr,int Idx,int Idx2,const char * Name)304 ShadowStackGCLoweringImpl::CreateGEP(LLVMContext &Context, IRBuilder<> &B,
305 Type *Ty, Value *BasePtr, int Idx,
306 int Idx2, const char *Name) {
307 Value *Indices[] = {ConstantInt::get(Type::getInt32Ty(Context), 0),
308 ConstantInt::get(Type::getInt32Ty(Context), Idx),
309 ConstantInt::get(Type::getInt32Ty(Context), Idx2)};
310 Value *Val = B.CreateGEP(Ty, BasePtr, Indices, Name);
311
312 assert(isa<GetElementPtrInst>(Val) && "Unexpected folded constant");
313
314 return dyn_cast<GetElementPtrInst>(Val);
315 }
316
CreateGEP(LLVMContext & Context,IRBuilder<> & B,Type * Ty,Value * BasePtr,int Idx,const char * Name)317 GetElementPtrInst *ShadowStackGCLoweringImpl::CreateGEP(LLVMContext &Context,
318 IRBuilder<> &B,
319 Type *Ty,
320 Value *BasePtr, int Idx,
321 const char *Name) {
322 Value *Indices[] = {ConstantInt::get(Type::getInt32Ty(Context), 0),
323 ConstantInt::get(Type::getInt32Ty(Context), Idx)};
324 Value *Val = B.CreateGEP(Ty, BasePtr, Indices, Name);
325
326 assert(isa<GetElementPtrInst>(Val) && "Unexpected folded constant");
327
328 return dyn_cast<GetElementPtrInst>(Val);
329 }
330
331 /// runOnFunction - Insert code to maintain the shadow stack.
runOnFunction(Function & F,DomTreeUpdater * DTU)332 bool ShadowStackGCLoweringImpl::runOnFunction(Function &F,
333 DomTreeUpdater *DTU) {
334 // Quick exit for functions that do not use the shadow stack GC.
335 if (!F.hasGC() || F.getGC() != "shadow-stack")
336 return false;
337
338 LLVMContext &Context = F.getContext();
339
340 // Find calls to llvm.gcroot.
341 CollectRoots(F);
342
343 // If there are no roots in this function, then there is no need to add a
344 // stack map entry for it.
345 if (Roots.empty())
346 return false;
347
348 // Build the constant map and figure the type of the shadow stack entry.
349 Value *FrameMap = GetFrameMap(F);
350 Type *ConcreteStackEntryTy = GetConcreteStackEntryType(F);
351
352 // Build the shadow stack entry at the very start of the function.
353 BasicBlock::iterator IP = F.getEntryBlock().begin();
354 IRBuilder<> AtEntry(IP->getParent(), IP);
355
356 Instruction *StackEntry =
357 AtEntry.CreateAlloca(ConcreteStackEntryTy, nullptr, "gc_frame");
358
359 AtEntry.SetInsertPointPastAllocas(&F);
360 IP = AtEntry.GetInsertPoint();
361
362 // Initialize the map pointer and load the current head of the shadow stack.
363 Instruction *CurrentHead =
364 AtEntry.CreateLoad(AtEntry.getPtrTy(), Head, "gc_currhead");
365 Instruction *EntryMapPtr = CreateGEP(Context, AtEntry, ConcreteStackEntryTy,
366 StackEntry, 0, 1, "gc_frame.map");
367 AtEntry.CreateStore(FrameMap, EntryMapPtr);
368
369 // After all the allocas...
370 for (unsigned I = 0, E = Roots.size(); I != E; ++I) {
371 // For each root, find the corresponding slot in the aggregate...
372 Value *SlotPtr = CreateGEP(Context, AtEntry, ConcreteStackEntryTy,
373 StackEntry, 1 + I, "gc_root");
374
375 // And use it in lieu of the alloca.
376 AllocaInst *OriginalAlloca = Roots[I].second;
377 SlotPtr->takeName(OriginalAlloca);
378 OriginalAlloca->replaceAllUsesWith(SlotPtr);
379 }
380
381 // Move past the original stores inserted by GCStrategy::InitRoots. This isn't
382 // really necessary (the collector would never see the intermediate state at
383 // runtime), but it's nicer not to push the half-initialized entry onto the
384 // shadow stack.
385 while (isa<StoreInst>(IP))
386 ++IP;
387 AtEntry.SetInsertPoint(IP->getParent(), IP);
388
389 // Push the entry onto the shadow stack.
390 Instruction *EntryNextPtr = CreateGEP(Context, AtEntry, ConcreteStackEntryTy,
391 StackEntry, 0, 0, "gc_frame.next");
392 Instruction *NewHeadVal = CreateGEP(Context, AtEntry, ConcreteStackEntryTy,
393 StackEntry, 0, "gc_newhead");
394 AtEntry.CreateStore(CurrentHead, EntryNextPtr);
395 AtEntry.CreateStore(NewHeadVal, Head);
396
397 // For each instruction that escapes...
398 EscapeEnumerator EE(F, "gc_cleanup", /*HandleExceptions=*/true, DTU);
399 while (IRBuilder<> *AtExit = EE.Next()) {
400 // Pop the entry from the shadow stack. Don't reuse CurrentHead from
401 // AtEntry, since that would make the value live for the entire function.
402 Instruction *EntryNextPtr2 =
403 CreateGEP(Context, *AtExit, ConcreteStackEntryTy, StackEntry, 0, 0,
404 "gc_frame.next");
405 Value *SavedHead =
406 AtExit->CreateLoad(AtExit->getPtrTy(), EntryNextPtr2, "gc_savedhead");
407 AtExit->CreateStore(SavedHead, Head);
408 }
409
410 // Delete the original allocas (which are no longer used) and the intrinsic
411 // calls (which are no longer valid). Doing this last avoids invalidating
412 // iterators.
413 for (std::pair<CallInst *, AllocaInst *> &Root : Roots) {
414 Root.first->eraseFromParent();
415 Root.second->eraseFromParent();
416 }
417
418 Roots.clear();
419 return true;
420 }
421