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