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/raw_ostream.h"
16#include <algorithm>
17
18namespace llvm {
19
20// We sort the stack variables by alignment (largest first) to minimize
21// unnecessary large gaps due to alignment.
22// It is tempting to also sort variables by size so that larger variables
23// have larger redzones at both ends. But reordering will make report analysis
24// harder, especially when temporary unnamed variables are present.
25// So, until we can provide more information (type, line number, etc)
26// for the stack variables we avoid reordering them too much.
27static inline bool CompareVars(const ASanStackVariableDescription &a,
28                               const ASanStackVariableDescription &b) {
29  return a.Alignment > b.Alignment;
30}
31
32// We also force minimal alignment for all vars to kMinAlignment so that vars
33// with e.g. alignment 1 and alignment 16 do not get reordered by CompareVars.
34static const size_t kMinAlignment = 16;
35
36static size_t RoundUpTo(size_t X, size_t RoundTo) {
37  assert((RoundTo & (RoundTo - 1)) == 0);
38  return (X + RoundTo - 1) & ~(RoundTo - 1);
39}
40
41// The larger the variable Size the larger is the redzone.
42// The resulting frame size is a multiple of Alignment.
43static size_t VarAndRedzoneSize(size_t Size, 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 RoundUpTo(Res, Alignment);
52}
53
54void
55ComputeASanStackFrameLayout(SmallVectorImpl<ASanStackVariableDescription> &Vars,
56                            size_t Granularity, size_t MinHeaderSize,
57                            ASanStackFrameLayout *Layout) {
58  assert(Granularity >= 8 && Granularity <= 64 &&
59         (Granularity & (Granularity - 1)) == 0);
60  assert(MinHeaderSize >= 16 && (MinHeaderSize & (MinHeaderSize - 1)) == 0 &&
61         MinHeaderSize >= Granularity);
62  size_t NumVars = Vars.size();
63  assert(NumVars > 0);
64  for (size_t i = 0; i < NumVars; i++)
65    Vars[i].Alignment = std::max(Vars[i].Alignment, kMinAlignment);
66
67  std::stable_sort(Vars.begin(), Vars.end(), CompareVars);
68  SmallString<2048> StackDescriptionStorage;
69  raw_svector_ostream StackDescription(StackDescriptionStorage);
70  StackDescription << NumVars;
71  Layout->FrameAlignment = std::max(Granularity, Vars[0].Alignment);
72  SmallVector<uint8_t, 64> &SB(Layout->ShadowBytes);
73  SB.clear();
74  size_t Offset = std::max(std::max(MinHeaderSize, Granularity),
75     Vars[0].Alignment);
76  assert((Offset % Granularity) == 0);
77  SB.insert(SB.end(), Offset / Granularity, kAsanStackLeftRedzoneMagic);
78  for (size_t i = 0; i < NumVars; i++) {
79    bool IsLast = i == NumVars - 1;
80    size_t Alignment = std::max(Granularity, Vars[i].Alignment);
81    (void)Alignment;  // Used only in asserts.
82    size_t Size = Vars[i].Size;
83    const char *Name = Vars[i].Name;
84    assert((Alignment & (Alignment - 1)) == 0);
85    assert(Layout->FrameAlignment >= Alignment);
86    assert((Offset % Alignment) == 0);
87    assert(Size > 0);
88    StackDescription << " " << Offset << " " << Size << " " << strlen(Name)
89                     << " " << Name;
90    size_t NextAlignment = IsLast ? Granularity
91                   : std::max(Granularity, Vars[i + 1].Alignment);
92    size_t SizeWithRedzone = VarAndRedzoneSize(Vars[i].Size, NextAlignment);
93    SB.insert(SB.end(), Size / Granularity, 0);
94    if (Size % Granularity)
95      SB.insert(SB.end(), Size % Granularity);
96    SB.insert(SB.end(), (SizeWithRedzone - Size) / Granularity,
97        IsLast ? kAsanStackRightRedzoneMagic
98        : kAsanStackMidRedzoneMagic);
99    Vars[i].Offset = Offset;
100    Offset += SizeWithRedzone;
101  }
102  if (Offset % MinHeaderSize) {
103    size_t ExtraRedzone = MinHeaderSize - (Offset % MinHeaderSize);
104    SB.insert(SB.end(), ExtraRedzone / Granularity,
105              kAsanStackRightRedzoneMagic);
106    Offset += ExtraRedzone;
107  }
108  Layout->DescriptionString = StackDescription.str();
109  Layout->FrameSize = Offset;
110  assert((Layout->FrameSize % MinHeaderSize) == 0);
111  assert(Layout->FrameSize / Granularity == Layout->ShadowBytes.size());
112}
113
114} // llvm namespace
115