1251034Sed//===-- asan_fake_stack.h ---------------------------------------*- C++ -*-===// 2251034Sed// 3251034Sed// The LLVM Compiler Infrastructure 4251034Sed// 5251034Sed// This file is distributed under the University of Illinois Open Source 6251034Sed// License. See LICENSE.TXT for details. 7251034Sed// 8251034Sed//===----------------------------------------------------------------------===// 9251034Sed// 10251034Sed// This file is a part of AddressSanitizer, an address sanity checker. 11251034Sed// 12274201Sdim// ASan-private header for asan_fake_stack.cc, implements FakeStack. 13251034Sed//===----------------------------------------------------------------------===// 14251034Sed 15251034Sed#ifndef ASAN_FAKE_STACK_H 16251034Sed#define ASAN_FAKE_STACK_H 17251034Sed 18274201Sdim#include "sanitizer_common/sanitizer_common.h" 19274201Sdim 20251034Sednamespace __asan { 21251034Sed 22251034Sed// Fake stack frame contains local variables of one function. 23251034Sedstruct FakeFrame { 24251034Sed uptr magic; // Modified by the instrumented code. 25251034Sed uptr descr; // Modified by the instrumented code. 26251034Sed uptr pc; // Modified by the instrumented code. 27274201Sdim uptr real_stack; 28251034Sed}; 29251034Sed 30251034Sed// For each thread we create a fake stack and place stack objects on this fake 31251034Sed// stack instead of the real stack. The fake stack is not really a stack but 32251034Sed// a fast malloc-like allocator so that when a function exits the fake stack 33274201Sdim// is not popped but remains there for quite some time until gets used again. 34251034Sed// So, we poison the objects on the fake stack when function returns. 35251034Sed// It helps us find use-after-return bugs. 36274201Sdim// 37274201Sdim// The FakeStack objects is allocated by a single mmap call and has no other 38274201Sdim// pointers. The size of the fake stack depends on the actual thread stack size 39274201Sdim// and thus can not be a constant. 40274201Sdim// stack_size is a power of two greater or equal to the thread's stack size; 41274201Sdim// we store it as its logarithm (stack_size_log). 42274201Sdim// FakeStack has kNumberOfSizeClasses (11) size classes, each size class 43274201Sdim// is a power of two, starting from 64 bytes. Each size class occupies 44274201Sdim// stack_size bytes and thus can allocate 45274201Sdim// NumberOfFrames=(stack_size/BytesInSizeClass) fake frames (also a power of 2). 46274201Sdim// For each size class we have NumberOfFrames allocation flags, 47274201Sdim// each flag indicates whether the given frame is currently allocated. 48274201Sdim// All flags for size classes 0 .. 10 are stored in a single contiguous region 49274201Sdim// followed by another contiguous region which contains the actual memory for 50274201Sdim// size classes. The addresses are computed by GetFlags and GetFrame without 51274201Sdim// any memory accesses solely based on 'this' and stack_size_log. 52274201Sdim// Allocate() flips the appropriate allocation flag atomically, thus achieving 53274201Sdim// async-signal safety. 54274201Sdim// This allocator does not have quarantine per se, but it tries to allocate the 55274201Sdim// frames in round robin fasion to maximize the delay between a deallocation 56274201Sdim// and the next allocation. 57251034Sedclass FakeStack { 58274201Sdim static const uptr kMinStackFrameSizeLog = 6; // Min frame is 64B. 59274201Sdim static const uptr kMaxStackFrameSizeLog = 16; // Max stack frame is 64K. 60274201Sdim 61251034Sed public: 62251034Sed static const uptr kNumberOfSizeClasses = 63274201Sdim kMaxStackFrameSizeLog - kMinStackFrameSizeLog + 1; 64251034Sed 65274201Sdim // CTOR: create the FakeStack as a single mmap-ed object. 66274201Sdim static FakeStack *Create(uptr stack_size_log); 67251034Sed 68276789Sdim void Destroy(int tid); 69251034Sed 70274201Sdim // stack_size_log is at least 15 (stack_size >= 32K). 71274201Sdim static uptr SizeRequiredForFlags(uptr stack_size_log) { 72274201Sdim return 1UL << (stack_size_log + 1 - kMinStackFrameSizeLog); 73251034Sed } 74251034Sed 75274201Sdim // Each size class occupies stack_size bytes. 76274201Sdim static uptr SizeRequiredForFrames(uptr stack_size_log) { 77274201Sdim return (1ULL << stack_size_log) * kNumberOfSizeClasses; 78274201Sdim } 79251034Sed 80274201Sdim // Number of bytes requires for the whole object. 81274201Sdim static uptr RequiredSize(uptr stack_size_log) { 82274201Sdim return kFlagsOffset + SizeRequiredForFlags(stack_size_log) + 83274201Sdim SizeRequiredForFrames(stack_size_log); 84274201Sdim } 85251034Sed 86274201Sdim // Offset of the given flag from the first flag. 87274201Sdim // The flags for class 0 begin at offset 000000000 88274201Sdim // The flags for class 1 begin at offset 100000000 89274201Sdim // ....................2................ 110000000 90274201Sdim // ....................3................ 111000000 91274201Sdim // and so on. 92274201Sdim static uptr FlagsOffset(uptr stack_size_log, uptr class_id) { 93274201Sdim uptr t = kNumberOfSizeClasses - 1 - class_id; 94274201Sdim const uptr all_ones = (1 << (kNumberOfSizeClasses - 1)) - 1; 95274201Sdim return ((all_ones >> t) << t) << (stack_size_log - 15); 96274201Sdim } 97251034Sed 98274201Sdim static uptr NumberOfFrames(uptr stack_size_log, uptr class_id) { 99274201Sdim return 1UL << (stack_size_log - kMinStackFrameSizeLog - class_id); 100274201Sdim } 101274201Sdim 102274201Sdim // Divide n by the numbe of frames in size class. 103274201Sdim static uptr ModuloNumberOfFrames(uptr stack_size_log, uptr class_id, uptr n) { 104274201Sdim return n & (NumberOfFrames(stack_size_log, class_id) - 1); 105274201Sdim } 106274201Sdim 107274201Sdim // The the pointer to the flags of the given class_id. 108274201Sdim u8 *GetFlags(uptr stack_size_log, uptr class_id) { 109274201Sdim return reinterpret_cast<u8 *>(this) + kFlagsOffset + 110274201Sdim FlagsOffset(stack_size_log, class_id); 111274201Sdim } 112274201Sdim 113274201Sdim // Get frame by class_id and pos. 114274201Sdim u8 *GetFrame(uptr stack_size_log, uptr class_id, uptr pos) { 115274201Sdim return reinterpret_cast<u8 *>(this) + kFlagsOffset + 116274201Sdim SizeRequiredForFlags(stack_size_log) + 117274201Sdim (1 << stack_size_log) * class_id + BytesInSizeClass(class_id) * pos; 118274201Sdim } 119274201Sdim 120274201Sdim // Allocate the fake frame. 121274201Sdim FakeFrame *Allocate(uptr stack_size_log, uptr class_id, uptr real_stack); 122274201Sdim 123274201Sdim // Deallocate the fake frame: read the saved flag address and write 0 there. 124274201Sdim static void Deallocate(uptr x, uptr class_id) { 125274201Sdim **SavedFlagPtr(x, class_id) = 0; 126274201Sdim } 127274201Sdim 128274201Sdim // Poison the entire FakeStack's shadow with the magic value. 129274201Sdim void PoisonAll(u8 magic); 130274201Sdim 131274201Sdim // Return the beginning of the FakeFrame or 0 if the address is not ours. 132276789Sdim uptr AddrIsInFakeStack(uptr addr, uptr *frame_beg, uptr *frame_end); 133276789Sdim USED uptr AddrIsInFakeStack(uptr addr) { 134276789Sdim uptr t1, t2; 135276789Sdim return AddrIsInFakeStack(addr, &t1, &t2); 136276789Sdim } 137274201Sdim 138274201Sdim // Number of bytes in a fake frame of this size class. 139274201Sdim static uptr BytesInSizeClass(uptr class_id) { 140274201Sdim return 1UL << (class_id + kMinStackFrameSizeLog); 141274201Sdim } 142274201Sdim 143274201Sdim // The fake frame is guaranteed to have a right redzone. 144274201Sdim // We use the last word of that redzone to store the address of the flag 145274201Sdim // that corresponds to the current frame to make faster deallocation. 146274201Sdim static u8 **SavedFlagPtr(uptr x, uptr class_id) { 147274201Sdim return reinterpret_cast<u8 **>(x + BytesInSizeClass(class_id) - sizeof(x)); 148274201Sdim } 149274201Sdim 150274201Sdim uptr stack_size_log() const { return stack_size_log_; } 151274201Sdim 152274201Sdim void HandleNoReturn(); 153274201Sdim void GC(uptr real_stack); 154274201Sdim 155274201Sdim void ForEachFakeFrame(RangeIteratorCallback callback, void *arg); 156274201Sdim 157274201Sdim private: 158274201Sdim FakeStack() { } 159274201Sdim static const uptr kFlagsOffset = 4096; // This is were the flags begin. 160274201Sdim // Must match the number of uses of DEFINE_STACK_MALLOC_FREE_WITH_CLASS_ID 161274201Sdim COMPILER_CHECK(kNumberOfSizeClasses == 11); 162274201Sdim static const uptr kMaxStackMallocSize = 1 << kMaxStackFrameSizeLog; 163274201Sdim 164274201Sdim uptr hint_position_[kNumberOfSizeClasses]; 165274201Sdim uptr stack_size_log_; 166274201Sdim // a bit is set if something was allocated from the corresponding size class. 167274201Sdim bool needs_gc_; 168251034Sed}; 169251034Sed 170274201SdimFakeStack *GetTLSFakeStack(); 171274201Sdimvoid SetTLSFakeStack(FakeStack *fs); 172274201Sdim 173251034Sed} // namespace __asan 174251034Sed 175251034Sed#endif // ASAN_FAKE_STACK_H 176