136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines//===-- ASanStackFrameLayout.cpp - helper for AddressSanitizer ------------===// 236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines// 336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines// The LLVM Compiler Infrastructure 436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines// 536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines// This file is distributed under the University of Illinois Open Source 636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines// License. See LICENSE.TXT for details. 736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines// 836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines//===----------------------------------------------------------------------===// 936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines// 1036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines// Definition of ComputeASanStackFrameLayout (see ASanStackFrameLayout.h). 1136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines// 1236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines//===----------------------------------------------------------------------===// 1336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines#include "llvm/Transforms/Utils/ASanStackFrameLayout.h" 1436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines#include "llvm/ADT/SmallString.h" 1536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines#include "llvm/Support/raw_ostream.h" 1636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines#include <algorithm> 1736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 1836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hinesnamespace llvm { 1936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 2036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines// We sort the stack variables by alignment (largest first) to minimize 2136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines// unnecessary large gaps due to alignment. 2236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines// It is tempting to also sort variables by size so that larger variables 2336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines// have larger redzones at both ends. But reordering will make report analysis 2436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines// harder, especially when temporary unnamed variables are present. 2536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines// So, until we can provide more information (type, line number, etc) 2636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines// for the stack variables we avoid reordering them too much. 2736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hinesstatic inline bool CompareVars(const ASanStackVariableDescription &a, 2836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines const ASanStackVariableDescription &b) { 2936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return a.Alignment > b.Alignment; 3036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines} 3136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 3236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines// We also force minimal alignment for all vars to kMinAlignment so that vars 3336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines// with e.g. alignment 1 and alignment 16 do not get reordered by CompareVars. 3436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hinesstatic const size_t kMinAlignment = 16; 3536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 3636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hinesstatic size_t RoundUpTo(size_t X, size_t RoundTo) { 3736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines assert((RoundTo & (RoundTo - 1)) == 0); 3836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return (X + RoundTo - 1) & ~(RoundTo - 1); 3936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines} 4036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 4136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines// The larger the variable Size the larger is the redzone. 4236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines// The resulting frame size is a multiple of Alignment. 4336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hinesstatic size_t VarAndRedzoneSize(size_t Size, size_t Alignment) { 4436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines size_t Res = 0; 4536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (Size <= 4) Res = 16; 4636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines else if (Size <= 16) Res = 32; 4736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines else if (Size <= 128) Res = Size + 32; 4836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines else if (Size <= 512) Res = Size + 64; 4936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines else if (Size <= 4096) Res = Size + 128; 5036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines else Res = Size + 256; 5136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return RoundUpTo(Res, Alignment); 5236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines} 5336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 5436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hinesvoid 5536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen HinesComputeASanStackFrameLayout(SmallVectorImpl<ASanStackVariableDescription> &Vars, 5636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines size_t Granularity, size_t MinHeaderSize, 5736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines ASanStackFrameLayout *Layout) { 5836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines assert(Granularity >= 8 && Granularity <= 64 && 5936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines (Granularity & (Granularity - 1)) == 0); 6036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines assert(MinHeaderSize >= 16 && (MinHeaderSize & (MinHeaderSize - 1)) == 0 && 6136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines MinHeaderSize >= Granularity); 6236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines size_t NumVars = Vars.size(); 6336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines assert(NumVars > 0); 6436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines for (size_t i = 0; i < NumVars; i++) 6536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Vars[i].Alignment = std::max(Vars[i].Alignment, kMinAlignment); 6636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 6736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines std::stable_sort(Vars.begin(), Vars.end(), CompareVars); 6836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines SmallString<2048> StackDescriptionStorage; 6936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines raw_svector_ostream StackDescription(StackDescriptionStorage); 7036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines StackDescription << NumVars; 7136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Layout->FrameAlignment = std::max(Granularity, Vars[0].Alignment); 7236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines SmallVector<uint8_t, 64> &SB(Layout->ShadowBytes); 7336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines SB.clear(); 7436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines size_t Offset = std::max(std::max(MinHeaderSize, Granularity), 7536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Vars[0].Alignment); 7636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines assert((Offset % Granularity) == 0); 7736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines SB.insert(SB.end(), Offset / Granularity, kAsanStackLeftRedzoneMagic); 7836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines for (size_t i = 0; i < NumVars; i++) { 7936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines bool IsLast = i == NumVars - 1; 8036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines size_t Alignment = std::max(Granularity, Vars[i].Alignment); 8136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines (void)Alignment; // Used only in asserts. 8236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines size_t Size = Vars[i].Size; 8336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines const char *Name = Vars[i].Name; 8436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines assert((Alignment & (Alignment - 1)) == 0); 8536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines assert(Layout->FrameAlignment >= Alignment); 8636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines assert((Offset % Alignment) == 0); 8736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines assert(Size > 0); 8836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines StackDescription << " " << Offset << " " << Size << " " << strlen(Name) 8936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines << " " << Name; 9036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines size_t NextAlignment = IsLast ? Granularity 9136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines : std::max(Granularity, Vars[i + 1].Alignment); 9236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines size_t SizeWithRedzone = VarAndRedzoneSize(Vars[i].Size, NextAlignment); 9336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines SB.insert(SB.end(), Size / Granularity, 0); 9436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (Size % Granularity) 9536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines SB.insert(SB.end(), Size % Granularity); 9636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines SB.insert(SB.end(), (SizeWithRedzone - Size) / Granularity, 9736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines IsLast ? kAsanStackRightRedzoneMagic 9836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines : kAsanStackMidRedzoneMagic); 9936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Vars[i].Offset = Offset; 10036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Offset += SizeWithRedzone; 10136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines } 10236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (Offset % MinHeaderSize) { 10336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines size_t ExtraRedzone = MinHeaderSize - (Offset % MinHeaderSize); 10436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines SB.insert(SB.end(), ExtraRedzone / Granularity, 10536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines kAsanStackRightRedzoneMagic); 10636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Offset += ExtraRedzone; 10736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines } 10836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Layout->DescriptionString = StackDescription.str(); 10936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Layout->FrameSize = Offset; 11036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines assert((Layout->FrameSize % MinHeaderSize) == 0); 11136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines assert(Layout->FrameSize / Granularity == Layout->ShadowBytes.size()); 11236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines} 11336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 11436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines} // llvm namespace 115