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