1 //===-- ASanStackFrameLayout.cpp - helper for AddressSanitizer ------------===// 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 // Definition of ComputeASanStackFrameLayout (see ASanStackFrameLayout.h). 10 // 11 //===----------------------------------------------------------------------===// 12 #include "llvm/Transforms/Utils/ASanStackFrameLayout.h" 13 #include "llvm/ADT/SmallString.h" 14 #include "llvm/Support/MathExtras.h" 15 #include "llvm/Support/ScopedPrinter.h" 16 #include "llvm/Support/raw_ostream.h" 17 #include <algorithm> 18 19 namespace llvm { 20 21 // We sort the stack variables by alignment (largest first) to minimize 22 // unnecessary large gaps due to alignment. 23 // It is tempting to also sort variables by size so that larger variables 24 // have larger redzones at both ends. But reordering will make report analysis 25 // harder, especially when temporary unnamed variables are present. 26 // So, until we can provide more information (type, line number, etc) 27 // for the stack variables we avoid reordering them too much. 28 static inline bool CompareVars(const ASanStackVariableDescription &a, 29 const ASanStackVariableDescription &b) { 30 return a.Alignment > b.Alignment; 31 } 32 33 // We also force minimal alignment for all vars to kMinAlignment so that vars 34 // with e.g. alignment 1 and alignment 16 do not get reordered by CompareVars. 35 static const uint64_t kMinAlignment = 16; 36 37 // We want to add a full redzone after every variable. 38 // The larger the variable Size the larger is the redzone. 39 // The resulting frame size is a multiple of Alignment. 40 static uint64_t VarAndRedzoneSize(uint64_t Size, uint64_t Granularity, 41 uint64_t Alignment) { 42 uint64_t Res = 0; 43 if (Size <= 4) Res = 16; 44 else if (Size <= 16) Res = 32; 45 else if (Size <= 128) Res = Size + 32; 46 else if (Size <= 512) Res = Size + 64; 47 else if (Size <= 4096) Res = Size + 128; 48 else Res = Size + 256; 49 return alignTo(std::max(Res, 2 * Granularity), Alignment); 50 } 51 52 ASanStackFrameLayout 53 ComputeASanStackFrameLayout(SmallVectorImpl<ASanStackVariableDescription> &Vars, 54 uint64_t Granularity, uint64_t MinHeaderSize) { 55 assert(Granularity >= 8 && Granularity <= 64 && 56 (Granularity & (Granularity - 1)) == 0); 57 assert(MinHeaderSize >= 16 && (MinHeaderSize & (MinHeaderSize - 1)) == 0 && 58 MinHeaderSize >= Granularity); 59 const size_t NumVars = Vars.size(); 60 assert(NumVars > 0); 61 for (size_t i = 0; i < NumVars; i++) 62 Vars[i].Alignment = std::max(Vars[i].Alignment, kMinAlignment); 63 64 llvm::stable_sort(Vars, CompareVars); 65 66 ASanStackFrameLayout Layout; 67 Layout.Granularity = Granularity; 68 Layout.FrameAlignment = std::max(Granularity, Vars[0].Alignment); 69 uint64_t Offset = 70 std::max(std::max(MinHeaderSize, Granularity), Vars[0].Alignment); 71 assert((Offset % Granularity) == 0); 72 for (size_t i = 0; i < NumVars; i++) { 73 bool IsLast = i == NumVars - 1; 74 uint64_t Alignment = std::max(Granularity, Vars[i].Alignment); 75 (void)Alignment; // Used only in asserts. 76 uint64_t Size = Vars[i].Size; 77 assert((Alignment & (Alignment - 1)) == 0); 78 assert(Layout.FrameAlignment >= Alignment); 79 assert((Offset % Alignment) == 0); 80 assert(Size > 0); 81 uint64_t NextAlignment = 82 IsLast ? Granularity : std::max(Granularity, Vars[i + 1].Alignment); 83 uint64_t SizeWithRedzone = 84 VarAndRedzoneSize(Size, Granularity, NextAlignment); 85 Vars[i].Offset = Offset; 86 Offset += SizeWithRedzone; 87 } 88 if (Offset % MinHeaderSize) { 89 Offset += MinHeaderSize - (Offset % MinHeaderSize); 90 } 91 Layout.FrameSize = Offset; 92 assert((Layout.FrameSize % MinHeaderSize) == 0); 93 return Layout; 94 } 95 96 SmallString<64> ComputeASanStackFrameDescription( 97 const SmallVectorImpl<ASanStackVariableDescription> &Vars) { 98 SmallString<2048> StackDescriptionStorage; 99 raw_svector_ostream StackDescription(StackDescriptionStorage); 100 StackDescription << Vars.size(); 101 102 for (const auto &Var : Vars) { 103 std::string Name = Var.Name; 104 if (Var.Line) { 105 Name += ":"; 106 Name += to_string(Var.Line); 107 } 108 StackDescription << " " << Var.Offset << " " << Var.Size << " " 109 << Name.size() << " " << Name; 110 } 111 return StackDescription.str(); 112 } 113 114 SmallVector<uint8_t, 64> 115 GetShadowBytes(const SmallVectorImpl<ASanStackVariableDescription> &Vars, 116 const ASanStackFrameLayout &Layout) { 117 assert(Vars.size() > 0); 118 SmallVector<uint8_t, 64> SB; 119 SB.clear(); 120 const uint64_t Granularity = Layout.Granularity; 121 SB.resize(Vars[0].Offset / Granularity, kAsanStackLeftRedzoneMagic); 122 for (const auto &Var : Vars) { 123 SB.resize(Var.Offset / Granularity, kAsanStackMidRedzoneMagic); 124 125 SB.resize(SB.size() + Var.Size / Granularity, 0); 126 if (Var.Size % Granularity) 127 SB.push_back(Var.Size % Granularity); 128 } 129 SB.resize(Layout.FrameSize / Granularity, kAsanStackRightRedzoneMagic); 130 return SB; 131 } 132 133 SmallVector<uint8_t, 64> GetShadowBytesAfterScope( 134 const SmallVectorImpl<ASanStackVariableDescription> &Vars, 135 const ASanStackFrameLayout &Layout) { 136 SmallVector<uint8_t, 64> SB = GetShadowBytes(Vars, Layout); 137 const uint64_t Granularity = Layout.Granularity; 138 139 for (const auto &Var : Vars) { 140 assert(Var.LifetimeSize <= Var.Size); 141 const uint64_t LifetimeShadowSize = 142 (Var.LifetimeSize + Granularity - 1) / Granularity; 143 const uint64_t Offset = Var.Offset / Granularity; 144 std::fill(SB.begin() + Offset, SB.begin() + Offset + LifetimeShadowSize, 145 kAsanStackUseAfterScopeMagic); 146 } 147 148 return SB; 149 } 150 151 } // llvm namespace 152