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