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/Support/MathExtras.h"
16#include "llvm/Support/raw_ostream.h"
17#include <algorithm>
18
19namespace 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.
28static 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.
35static const size_t kMinAlignment = 16;
36
37// The larger the variable Size the larger is the redzone.
38// The resulting frame size is a multiple of Alignment.
39static size_t VarAndRedzoneSize(size_t Size, size_t Alignment) {
40  size_t Res = 0;
41  if (Size <= 4)  Res = 16;
42  else if (Size <= 16) Res = 32;
43  else if (Size <= 128) Res = Size + 32;
44  else if (Size <= 512) Res = Size + 64;
45  else if (Size <= 4096) Res = Size + 128;
46  else                   Res = Size + 256;
47  return alignTo(Res, Alignment);
48}
49
50void
51ComputeASanStackFrameLayout(SmallVectorImpl<ASanStackVariableDescription> &Vars,
52                            size_t Granularity, size_t MinHeaderSize,
53                            ASanStackFrameLayout *Layout) {
54  assert(Granularity >= 8 && Granularity <= 64 &&
55         (Granularity & (Granularity - 1)) == 0);
56  assert(MinHeaderSize >= 16 && (MinHeaderSize & (MinHeaderSize - 1)) == 0 &&
57         MinHeaderSize >= Granularity);
58  size_t NumVars = Vars.size();
59  assert(NumVars > 0);
60  for (size_t i = 0; i < NumVars; i++)
61    Vars[i].Alignment = std::max(Vars[i].Alignment, kMinAlignment);
62
63  std::stable_sort(Vars.begin(), Vars.end(), CompareVars);
64  SmallString<2048> StackDescriptionStorage;
65  raw_svector_ostream StackDescription(StackDescriptionStorage);
66  StackDescription << NumVars;
67  Layout->FrameAlignment = std::max(Granularity, Vars[0].Alignment);
68  SmallVector<uint8_t, 64> &SB(Layout->ShadowBytes);
69  SB.clear();
70  size_t Offset = std::max(std::max(MinHeaderSize, Granularity),
71     Vars[0].Alignment);
72  assert((Offset % Granularity) == 0);
73  SB.insert(SB.end(), Offset / Granularity, kAsanStackLeftRedzoneMagic);
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    const char *Name = Vars[i].Name;
80    assert((Alignment & (Alignment - 1)) == 0);
81    assert(Layout->FrameAlignment >= Alignment);
82    assert((Offset % Alignment) == 0);
83    assert(Size > 0);
84    StackDescription << " " << Offset << " " << Size << " " << strlen(Name)
85                     << " " << Name;
86    size_t NextAlignment = IsLast ? Granularity
87                   : std::max(Granularity, Vars[i + 1].Alignment);
88    size_t SizeWithRedzone = VarAndRedzoneSize(Vars[i].Size, NextAlignment);
89    SB.insert(SB.end(), Size / Granularity, 0);
90    if (Size % Granularity)
91      SB.insert(SB.end(), Size % Granularity);
92    SB.insert(SB.end(), (SizeWithRedzone - Size) / Granularity,
93        IsLast ? kAsanStackRightRedzoneMagic
94        : kAsanStackMidRedzoneMagic);
95    Vars[i].Offset = Offset;
96    Offset += SizeWithRedzone;
97  }
98  if (Offset % MinHeaderSize) {
99    size_t ExtraRedzone = MinHeaderSize - (Offset % MinHeaderSize);
100    SB.insert(SB.end(), ExtraRedzone / Granularity,
101              kAsanStackRightRedzoneMagic);
102    Offset += ExtraRedzone;
103  }
104  Layout->DescriptionString = StackDescription.str();
105  Layout->FrameSize = Offset;
106  assert((Layout->FrameSize % MinHeaderSize) == 0);
107  assert(Layout->FrameSize / Granularity == Layout->ShadowBytes.size());
108}
109
110} // llvm namespace
111