asan_fake_stack.h revision b388987bf988435ee87dc4848ea8e62ebfa942eb
1//===-- asan_fake_stack.h ---------------------------------------*- C++ -*-===// 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// This file is a part of AddressSanitizer, an address sanity checker. 11// 12// ASan-private header for asan_fake_stack.cc, implements FakeStack. 13//===----------------------------------------------------------------------===// 14 15#ifndef ASAN_FAKE_STACK_H 16#define ASAN_FAKE_STACK_H 17 18#include "sanitizer_common/sanitizer_common.h" 19 20namespace __asan { 21 22// Fake stack frame contains local variables of one function. 23struct FakeFrame { 24 uptr magic; // Modified by the instrumented code. 25 uptr descr; // Modified by the instrumented code. 26 uptr pc; // Modified by the instrumented code. 27 uptr real_stack; 28}; 29 30// For each thread we create a fake stack and place stack objects on this fake 31// stack instead of the real stack. The fake stack is not really a stack but 32// a fast malloc-like allocator so that when a function exits the fake stack 33// is not popped but remains there for quite some time until gets used again. 34// So, we poison the objects on the fake stack when function returns. 35// It helps us find use-after-return bugs. 36// 37// The FakeStack objects is allocated by a single mmap call and has no other 38// pointers. The size of the fake stack depends on the actual thread stack size 39// and thus can not be a constant. 40// stack_size is a power of two greater or equal to the thread's stack size; 41// we store it as its logarithm (stack_size_log). 42// FakeStack has kNumberOfSizeClasses (11) size classes, each size class 43// is a power of two, starting from 64 bytes. Each size class occupies 44// stack_size bytes and thus can allocate 45// NumberOfFrames=(stack_size/BytesInSizeClass) fake frames (also a power of 2). 46// For each size class we have NumberOfFrames allocation flags, 47// each flag indicates whether the given frame is currently allocated. 48// All flags for size classes 0 .. 10 are stored in a single contiguous region 49// followed by another contiguous region which contains the actual memory for 50// size classes. The addresses are computed by GetFlags and GetFrame without 51// any memory accesses solely based on 'this' and stack_size_log. 52// Allocate() flips the appropriate allocation flag atomically, thus achieving 53// async-signal safety. 54// This allocator does not have quarantine per se, but it tries to allocate the 55// frames in round robin fasion to maximize the delay between a deallocation 56// and the next allocation. 57class FakeStack { 58 static const uptr kMinStackFrameSizeLog = 6; // Min frame is 64B. 59 static const uptr kMaxStackFrameSizeLog = 16; // Max stack frame is 64K. 60 61 public: 62 static const uptr kNumberOfSizeClasses = 63 kMaxStackFrameSizeLog - kMinStackFrameSizeLog + 1; 64 65 // CTOR: create the FakeStack as a single mmap-ed object. 66 static FakeStack *Create(uptr stack_size_log) { 67 static uptr kMinStackSizeLog = 16; 68 static uptr kMaxStackSizeLog = FIRST_32_SECOND_64(23, 26); 69 if (stack_size_log < kMinStackSizeLog) 70 stack_size_log = kMinStackSizeLog; 71 if (stack_size_log > kMaxStackSizeLog) 72 stack_size_log = kMaxStackSizeLog; 73 FakeStack *res = reinterpret_cast<FakeStack *>( 74 MmapOrDie(RequiredSize(stack_size_log), "FakeStack")); 75 res->stack_size_log_ = stack_size_log; 76 return res; 77 } 78 79 void Destroy() { 80 UnmapOrDie(this, RequiredSize(stack_size_log_)); 81 } 82 83 // stack_size_log is at least 15 (stack_size >= 32K). 84 static uptr SizeRequiredForFlags(uptr stack_size_log) { 85 return 1UL << (stack_size_log + 1 - kMinStackFrameSizeLog); 86 } 87 88 // Each size class occupies stack_size bytes. 89 static uptr SizeRequiredForFrames(uptr stack_size_log) { 90 return (1ULL << stack_size_log) * kNumberOfSizeClasses; 91 } 92 93 // Number of bytes requires for the whole object. 94 static uptr RequiredSize(uptr stack_size_log) { 95 return kFlagsOffset + SizeRequiredForFlags(stack_size_log) + 96 SizeRequiredForFrames(stack_size_log); 97 } 98 99 // Offset of the given flag from the first flag. 100 // The flags for class 0 begin at offset 000000000 101 // The flags for class 1 begin at offset 100000000 102 // ....................2................ 110000000 103 // ....................3................ 111000000 104 // and so on. 105 static uptr FlagsOffset(uptr stack_size_log, uptr class_id) { 106 uptr t = kNumberOfSizeClasses - 1 - class_id; 107 const uptr all_ones = (1 << (kNumberOfSizeClasses - 1)) - 1; 108 return ((all_ones >> t) << t) << (stack_size_log - 15); 109 } 110 111 static uptr NumberOfFrames(uptr stack_size_log, uptr class_id) { 112 return 1UL << (stack_size_log - kMinStackFrameSizeLog - class_id); 113 } 114 115 // Divide n by the numbe of frames in size class. 116 static uptr ModuloNumberOfFrames(uptr stack_size_log, uptr class_id, uptr n) { 117 return n & (NumberOfFrames(stack_size_log, class_id) - 1); 118 } 119 120 // The the pointer to the flags of the given class_id. 121 u8 *GetFlags(uptr stack_size_log, uptr class_id) { 122 return reinterpret_cast<u8 *>(this) + kFlagsOffset + 123 FlagsOffset(stack_size_log, class_id); 124 } 125 126 // Get frame by class_id and pos. 127 u8 *GetFrame(uptr stack_size_log, uptr class_id, uptr pos) { 128 return reinterpret_cast<u8 *>(this) + kFlagsOffset + 129 SizeRequiredForFlags(stack_size_log) + 130 (1 << stack_size_log) * class_id + BytesInSizeClass(class_id) * pos; 131 } 132 133 // Allocate the fake frame. 134 FakeFrame *Allocate(uptr stack_size_log, uptr class_id, uptr real_stack); 135 136 // Deallocate the fake frame: read the saved flag address and write 0 there. 137 static void Deallocate(uptr x, uptr class_id) { 138 **SavedFlagPtr(x, class_id) = 0; 139 } 140 141 // Poison the entire FakeStack's shadow with the magic value. 142 void PoisonAll(u8 magic); 143 144 // Return the beginning of the FakeFrame or 0 if the address is not ours. 145 uptr AddrIsInFakeStack(uptr addr); 146 147 // Number of bytes in a fake frame of this size class. 148 static uptr BytesInSizeClass(uptr class_id) { 149 return 1UL << (class_id + kMinStackFrameSizeLog); 150 } 151 152 // The fake frame is guaranteed to have a right redzone. 153 // We use the last word of that redzone to store the address of the flag 154 // that corresponds to the current frame to make faster deallocation. 155 static u8 **SavedFlagPtr(uptr x, uptr class_id) { 156 return reinterpret_cast<u8 **>(x + BytesInSizeClass(class_id) - sizeof(x)); 157 } 158 159 uptr stack_size_log() const { return stack_size_log_; } 160 161 void HandleNoReturn(); 162 void GC(uptr real_stack); 163 164 private: 165 FakeStack() { } 166 static const uptr kFlagsOffset = 4096; // This is were the flags begin. 167 // Must match the number of uses of DEFINE_STACK_MALLOC_FREE_WITH_CLASS_ID 168 COMPILER_CHECK(kNumberOfSizeClasses == 11); 169 static const uptr kMaxStackMallocSize = 1 << kMaxStackFrameSizeLog; 170 171 uptr hint_position_[kNumberOfSizeClasses]; 172 uptr stack_size_log_; 173 // a bit is set if something was allocated from the corresponding size class. 174 bool needs_gc_; 175}; 176 177FakeStack *GetTLSFakeStack(); 178void SetTLSFakeStack(FakeStack *fs); 179 180} // namespace __asan 181 182#endif // ASAN_FAKE_STACK_H 183