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
49using namespace llvm;
50
51#define DEBUG_TYPE "shadow-stack-gc-lowering"
52
53namespace {
54
55class 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
68public:
69 ShadowStackGCLoweringImpl() = default;
70
71 bool doInitialization(Module &M);
72 bool runOnFunction(Function &F, DomTreeUpdater *DTU);
73
74private:
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
88class ShadowStackGCLowering : public FunctionPass {
89 ShadowStackGCLoweringImpl Impl;
90
91public:
92 static char ID;
93
94 ShadowStackGCLowering();
95
96 bool doInitialization(Module &M) override { return Impl.doInitialization(M); }
97 void getAnalysisUsage(AnalysisUsage &AU) const override {
98 AU.addPreserved<DominatorTreeWrapperPass>();
99 }
100 bool runOnFunction(Function &F) override {
101 std::optional<DomTreeUpdater> DTU;
102 if (auto *DTWP = getAnalysisIfAvailable<DominatorTreeWrapperPass>())
103 DTU.emplace(args&: DTWP->getDomTree(), args: DomTreeUpdater::UpdateStrategy::Lazy);
104 return Impl.runOnFunction(F, DTU: DTU ? &*DTU : nullptr);
105 }
106};
107
108} // end anonymous namespace
109
110PreservedAnalyses ShadowStackGCLoweringPass::run(Module &M,
111 ModuleAnalysisManager &MAM) {
112 auto &Map = MAM.getResult<CollectorMetadataAnalysis>(IR&: M);
113 if (Map.StrategyMap.contains(Key: "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>(IR&: M).getManager();
121 auto *DT = FAM.getCachedResult<DominatorTreeAnalysis>(IR&: F);
122 DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Lazy);
123 Changed |= Impl.runOnFunction(F, DTU: DT ? &DTU : nullptr);
124 }
125
126 if (!Changed)
127 return PreservedAnalyses::all();
128 PreservedAnalyses PA;
129 PA.preserve<DominatorTreeAnalysis>();
130 return PA;
131}
132
133char ShadowStackGCLowering::ID = 0;
134char &llvm::ShadowStackGCLoweringID = ShadowStackGCLowering::ID;
135
136INITIALIZE_PASS_BEGIN(ShadowStackGCLowering, DEBUG_TYPE,
137 "Shadow Stack GC Lowering", false, false)
138INITIALIZE_PASS_DEPENDENCY(GCModuleInfo)
139INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
140INITIALIZE_PASS_END(ShadowStackGCLowering, DEBUG_TYPE,
141 "Shadow Stack GC Lowering", false, false)
142
143FunctionPass *llvm::createShadowStackGCLoweringPass() { return new ShadowStackGCLowering(); }
144
145ShadowStackGCLowering::ShadowStackGCLowering() : FunctionPass(ID) {
146 initializeShadowStackGCLoweringPass(Registry&: *PassRegistry::getPassRegistry());
147}
148
149Constant *ShadowStackGCLoweringImpl::GetFrameMap(Function &F) {
150 // doInitialization creates the abstract type of this value.
151 Type *VoidPtr = PointerType::getUnqual(C&: 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>(Val: Roots[I].first->getArgOperand(i: 1));
158 if (!C->isNullValue())
159 NumMeta = I + 1;
160 Metadata.push_back(Elt: C);
161 }
162 Metadata.resize(N: NumMeta);
163
164 Type *Int32Ty = Type::getInt32Ty(C&: F.getContext());
165
166 Constant *BaseElts[] = {
167 ConstantInt::get(Ty: Int32Ty, V: Roots.size(), IsSigned: false),
168 ConstantInt::get(Ty: Int32Ty, V: NumMeta, IsSigned: false),
169 };
170
171 Constant *DescriptorElts[] = {
172 ConstantStruct::get(T: FrameMapTy, V: BaseElts),
173 ConstantArray::get(T: ArrayType::get(ElementType: VoidPtr, NumElements: NumMeta), V: Metadata)};
174
175 Type *EltTys[] = {DescriptorElts[0]->getType(), DescriptorElts[1]->getType()};
176 StructType *STy = StructType::create(Elements: EltTys, Name: "gc_map." + utostr(X: NumMeta));
177
178 Constant *FrameMap = ConstantStruct::get(T: STy, V: 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(Ty: Type::getInt32Ty(C&: F.getContext()), V: 0),
199 ConstantInt::get(Ty: Type::getInt32Ty(C&: F.getContext()), V: 0)};
200 return ConstantExpr::getGetElementPtr(Ty: FrameMap->getType(), C: GV, IdxList: GEPIndices);
201}
202
203Type *ShadowStackGCLoweringImpl::GetConcreteStackEntryType(Function &F) {
204 // doInitialization creates the generic version of this type.
205 std::vector<Type *> EltTys;
206 EltTys.push_back(x: StackEntryTy);
207 for (const std::pair<CallInst *, AllocaInst *> &Root : Roots)
208 EltTys.push_back(x: Root.second->getAllocatedType());
209
210 return StructType::create(Elements: EltTys, Name: ("gc_stackentry." + F.getName()).str());
211}
212
213/// doInitialization - If this module uses the GC intrinsics, find them now. If
214/// not, exit fast.
215bool 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(x: Type::getInt32Ty(C&: M.getContext()));
234 // Specifies length of variable length array.
235 EltTys.push_back(x: Type::getInt32Ty(C&: M.getContext()));
236 FrameMapTy = StructType::create(Elements: EltTys, Name: "gc_map");
237 PointerType *FrameMapPtrTy = PointerType::getUnqual(ElementType: 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(Context&: M.getContext(), Name: "gc_stackentry");
246
247 EltTys.clear();
248 EltTys.push_back(x: PointerType::getUnqual(ElementType: StackEntryTy));
249 EltTys.push_back(x: FrameMapPtrTy);
250 StackEntryTy->setBody(Elements: EltTys);
251 PointerType *StackEntryPtrTy = PointerType::getUnqual(ElementType: StackEntryTy);
252
253 // Get the root chain if it already exists.
254 Head = M.getGlobalVariable(Name: "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(Ty: StackEntryPtrTy), "llvm_gc_root_chain");
261 } else if (Head->hasExternalLinkage() && Head->isDeclaration()) {
262 Head->setInitializer(Constant::getNullValue(Ty: StackEntryPtrTy));
263 Head->setLinkage(GlobalValue::LinkOnceAnyLinkage);
264 }
265
266 return true;
267}
268
269bool ShadowStackGCLoweringImpl::IsNullValue(Value *V) {
270 if (Constant *C = dyn_cast<Constant>(Val: V))
271 return C->isNullValue();
272 return false;
273}
274
275void 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>(Val: &I))
287 if (Function *F = CI->getCalledFunction())
288 if (F->getIntrinsicID() == Intrinsic::gcroot) {
289 std::pair<CallInst *, AllocaInst *> Pair = std::make_pair(
290 x&: CI,
291 y: cast<AllocaInst>(Val: CI->getArgOperand(i: 0)->stripPointerCasts()));
292 if (IsNullValue(V: CI->getArgOperand(i: 1)))
293 Roots.push_back(x: Pair);
294 else
295 MetaRoots.push_back(Elt: 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(position: Roots.begin(), first: MetaRoots.begin(), last: MetaRoots.end());
301}
302
303GetElementPtrInst *
304ShadowStackGCLoweringImpl::CreateGEP(LLVMContext &Context, IRBuilder<> &B,
305 Type *Ty, Value *BasePtr, int Idx,
306 int Idx2, const char *Name) {
307 Value *Indices[] = {ConstantInt::get(Ty: Type::getInt32Ty(C&: Context), V: 0),
308 ConstantInt::get(Ty: Type::getInt32Ty(C&: Context), V: Idx),
309 ConstantInt::get(Ty: Type::getInt32Ty(C&: Context), V: Idx2)};
310 Value *Val = B.CreateGEP(Ty, Ptr: BasePtr, IdxList: Indices, Name);
311
312 assert(isa<GetElementPtrInst>(Val) && "Unexpected folded constant");
313
314 return dyn_cast<GetElementPtrInst>(Val);
315}
316
317GetElementPtrInst *ShadowStackGCLoweringImpl::CreateGEP(LLVMContext &Context,
318 IRBuilder<> &B,
319 Type *Ty,
320 Value *BasePtr, int Idx,
321 const char *Name) {
322 Value *Indices[] = {ConstantInt::get(Ty: Type::getInt32Ty(C&: Context), V: 0),
323 ConstantInt::get(Ty: Type::getInt32Ty(C&: Context), V: Idx)};
324 Value *Val = B.CreateGEP(Ty, Ptr: BasePtr, IdxList: 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.
332bool 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(Ty: ConcreteStackEntryTy, ArraySize: nullptr, Name: "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(Ty: AtEntry.getPtrTy(), Ptr: Head, Name: "gc_currhead");
365 Instruction *EntryMapPtr = CreateGEP(Context, B&: AtEntry, Ty: ConcreteStackEntryTy,
366 BasePtr: StackEntry, Idx: 0, Idx2: 1, Name: "gc_frame.map");
367 AtEntry.CreateStore(Val: FrameMap, Ptr: 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, B&: AtEntry, Ty: ConcreteStackEntryTy,
373 BasePtr: StackEntry, Idx: 1 + I, Name: "gc_root");
374
375 // And use it in lieu of the alloca.
376 AllocaInst *OriginalAlloca = Roots[I].second;
377 SlotPtr->takeName(V: OriginalAlloca);
378 OriginalAlloca->replaceAllUsesWith(V: 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>(Val: IP))
386 ++IP;
387 AtEntry.SetInsertPoint(TheBB: IP->getParent(), IP);
388
389 // Push the entry onto the shadow stack.
390 Instruction *EntryNextPtr = CreateGEP(Context, B&: AtEntry, Ty: ConcreteStackEntryTy,
391 BasePtr: StackEntry, Idx: 0, Idx2: 0, Name: "gc_frame.next");
392 Instruction *NewHeadVal = CreateGEP(Context, B&: AtEntry, Ty: ConcreteStackEntryTy,
393 BasePtr: StackEntry, Idx: 0, Name: "gc_newhead");
394 AtEntry.CreateStore(Val: CurrentHead, Ptr: EntryNextPtr);
395 AtEntry.CreateStore(Val: NewHeadVal, Ptr: 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, B&: *AtExit, Ty: ConcreteStackEntryTy, BasePtr: StackEntry, Idx: 0, Idx2: 0,
404 Name: "gc_frame.next");
405 Value *SavedHead =
406 AtExit->CreateLoad(Ty: AtExit->getPtrTy(), Ptr: EntryNextPtr2, Name: "gc_savedhead");
407 AtExit->CreateStore(Val: SavedHead, Ptr: 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