Introduce a string_ostream string builder facilty
[oota-llvm.git] / lib / Transforms / Utils / ASanStackFrameLayout.cpp
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
18 namespace 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.
27 static 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.
34 static const size_t kMinAlignment = 16;
35
36 static 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.
43 static 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
54 void
55 ComputeASanStackFrameLayout(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   small_string_ostream<2048> StackDescription;
69   StackDescription << NumVars;
70   Layout->FrameAlignment = std::max(Granularity, Vars[0].Alignment);
71   SmallVector<uint8_t, 64> &SB(Layout->ShadowBytes);
72   SB.clear();
73   size_t Offset = std::max(std::max(MinHeaderSize, Granularity),
74      Vars[0].Alignment);
75   assert((Offset % Granularity) == 0);
76   SB.insert(SB.end(), Offset / Granularity, kAsanStackLeftRedzoneMagic);
77   for (size_t i = 0; i < NumVars; i++) {
78     bool IsLast = i == NumVars - 1;
79     size_t Alignment = std::max(Granularity, Vars[i].Alignment);
80     (void)Alignment;  // Used only in asserts.
81     size_t Size = Vars[i].Size;
82     const char *Name = Vars[i].Name;
83     assert((Alignment & (Alignment - 1)) == 0);
84     assert(Layout->FrameAlignment >= Alignment);
85     assert((Offset % Alignment) == 0);
86     assert(Size > 0);
87     StackDescription << " " << Offset << " " << Size << " " << strlen(Name)
88                      << " " << Name;
89     size_t NextAlignment = IsLast ? Granularity
90                    : std::max(Granularity, Vars[i + 1].Alignment);
91     size_t SizeWithRedzone = VarAndRedzoneSize(Vars[i].Size, NextAlignment);
92     SB.insert(SB.end(), Size / Granularity, 0);
93     if (Size % Granularity)
94       SB.insert(SB.end(), Size % Granularity);
95     SB.insert(SB.end(), (SizeWithRedzone - Size) / Granularity,
96         IsLast ? kAsanStackRightRedzoneMagic
97         : kAsanStackMidRedzoneMagic);
98     Vars[i].Offset = Offset;
99     Offset += SizeWithRedzone;
100   }
101   if (Offset % MinHeaderSize) {
102     size_t ExtraRedzone = MinHeaderSize - (Offset % MinHeaderSize);
103     SB.insert(SB.end(), ExtraRedzone / Granularity,
104               kAsanStackRightRedzoneMagic);
105     Offset += ExtraRedzone;
106   }
107   Layout->DescriptionString = StackDescription.str();
108   Layout->FrameSize = Offset;
109   assert((Layout->FrameSize % MinHeaderSize) == 0);
110   assert(Layout->FrameSize / Granularity == Layout->ShadowBytes.size());
111 }
112
113 } // llvm namespace