1 //===- SafeStackLayout.cpp - SafeStack frame layout -----------------------===// 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 #include "SafeStackLayout.h" 10 #include "llvm/Analysis/StackLifetime.h" 11 #include "llvm/IR/Value.h" 12 #include "llvm/Support/CommandLine.h" 13 #include "llvm/Support/Compiler.h" 14 #include "llvm/Support/Debug.h" 15 #include "llvm/Support/MathExtras.h" 16 #include "llvm/Support/raw_ostream.h" 17 #include <algorithm> 18 #include <cassert> 19 20 using namespace llvm; 21 using namespace llvm::safestack; 22 23 #define DEBUG_TYPE "safestacklayout" 24 25 static cl::opt<bool> ClLayout("safe-stack-layout", 26 cl::desc("enable safe stack layout"), cl::Hidden, 27 cl::init(true)); 28 29 LLVM_DUMP_METHOD void StackLayout::print(raw_ostream &OS) { 30 OS << "Stack regions:\n"; 31 for (unsigned i = 0; i < Regions.size(); ++i) { 32 OS << " " << i << ": [" << Regions[i].Start << ", " << Regions[i].End 33 << "), range " << Regions[i].Range << "\n"; 34 } 35 OS << "Stack objects:\n"; 36 for (auto &IT : ObjectOffsets) { 37 OS << " at " << IT.getSecond() << ": " << *IT.getFirst() << "\n"; 38 } 39 } 40 41 void StackLayout::addObject(const Value *V, unsigned Size, unsigned Alignment, 42 const StackLifetime::LiveRange &Range) { 43 StackObjects.push_back({V, Size, Alignment, Range}); 44 ObjectAlignments[V] = Alignment; 45 MaxAlignment = std::max(MaxAlignment, Alignment); 46 } 47 48 static unsigned AdjustStackOffset(unsigned Offset, unsigned Size, 49 unsigned Alignment) { 50 return alignTo(Offset + Size, Alignment) - Size; 51 } 52 53 void StackLayout::layoutObject(StackObject &Obj) { 54 if (!ClLayout) { 55 // If layout is disabled, just grab the next aligned address. 56 // This effectively disables stack coloring as well. 57 unsigned LastRegionEnd = Regions.empty() ? 0 : Regions.back().End; 58 unsigned Start = AdjustStackOffset(LastRegionEnd, Obj.Size, Obj.Alignment); 59 unsigned End = Start + Obj.Size; 60 Regions.emplace_back(Start, End, Obj.Range); 61 ObjectOffsets[Obj.Handle] = End; 62 return; 63 } 64 65 LLVM_DEBUG(dbgs() << "Layout: size " << Obj.Size << ", align " 66 << Obj.Alignment << ", range " << Obj.Range << "\n"); 67 assert(Obj.Alignment <= MaxAlignment); 68 unsigned Start = AdjustStackOffset(0, Obj.Size, Obj.Alignment); 69 unsigned End = Start + Obj.Size; 70 LLVM_DEBUG(dbgs() << " First candidate: " << Start << " .. " << End << "\n"); 71 for (const StackRegion &R : Regions) { 72 LLVM_DEBUG(dbgs() << " Examining region: " << R.Start << " .. " << R.End 73 << ", range " << R.Range << "\n"); 74 assert(End >= R.Start); 75 if (Start >= R.End) { 76 LLVM_DEBUG(dbgs() << " Does not intersect, skip.\n"); 77 continue; 78 } 79 if (Obj.Range.overlaps(R.Range)) { 80 // Find the next appropriate location. 81 Start = AdjustStackOffset(R.End, Obj.Size, Obj.Alignment); 82 End = Start + Obj.Size; 83 LLVM_DEBUG(dbgs() << " Overlaps. Next candidate: " << Start << " .. " 84 << End << "\n"); 85 continue; 86 } 87 if (End <= R.End) { 88 LLVM_DEBUG(dbgs() << " Reusing region(s).\n"); 89 break; 90 } 91 } 92 93 unsigned LastRegionEnd = Regions.empty() ? 0 : Regions.back().End; 94 if (End > LastRegionEnd) { 95 // Insert a new region at the end. Maybe two. 96 if (Start > LastRegionEnd) { 97 LLVM_DEBUG(dbgs() << " Creating gap region: " << LastRegionEnd << " .. " 98 << Start << "\n"); 99 Regions.emplace_back(LastRegionEnd, Start, StackLifetime::LiveRange(0)); 100 LastRegionEnd = Start; 101 } 102 LLVM_DEBUG(dbgs() << " Creating new region: " << LastRegionEnd << " .. " 103 << End << ", range " << Obj.Range << "\n"); 104 Regions.emplace_back(LastRegionEnd, End, Obj.Range); 105 LastRegionEnd = End; 106 } 107 108 // Split starting and ending regions if necessary. 109 for (unsigned i = 0; i < Regions.size(); ++i) { 110 StackRegion &R = Regions[i]; 111 if (Start > R.Start && Start < R.End) { 112 StackRegion R0 = R; 113 R.Start = R0.End = Start; 114 Regions.insert(&R, R0); 115 continue; 116 } 117 if (End > R.Start && End < R.End) { 118 StackRegion R0 = R; 119 R0.End = R.Start = End; 120 Regions.insert(&R, R0); 121 break; 122 } 123 } 124 125 // Update live ranges for all affected regions. 126 for (StackRegion &R : Regions) { 127 if (Start < R.End && End > R.Start) 128 R.Range.join(Obj.Range); 129 if (End <= R.End) 130 break; 131 } 132 133 ObjectOffsets[Obj.Handle] = End; 134 } 135 136 void StackLayout::computeLayout() { 137 // Simple greedy algorithm. 138 // If this is replaced with something smarter, it must preserve the property 139 // that the first object is always at the offset 0 in the stack frame (for 140 // StackProtectorSlot), or handle stack protector in some other way. 141 142 // Sort objects by size (largest first) to reduce fragmentation. 143 if (StackObjects.size() > 2) 144 std::stable_sort(StackObjects.begin() + 1, StackObjects.end(), 145 [](const StackObject &a, const StackObject &b) { 146 return a.Size > b.Size; 147 }); 148 149 for (auto &Obj : StackObjects) 150 layoutObject(Obj); 151 152 LLVM_DEBUG(print(dbgs())); 153 } 154