Kostya Serebryany | 244384d | 2013-04-11 11:39:19 +0000 | [diff] [blame] | 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 | // |
Kostya Serebryany | ac3ae5d | 2013-09-12 07:11:58 +0000 | [diff] [blame] | 12 | // ASan-private header for asan_fake_stack.cc, implements FakeStack. |
Kostya Serebryany | 244384d | 2013-04-11 11:39:19 +0000 | [diff] [blame] | 13 | //===----------------------------------------------------------------------===// |
| 14 | |
| 15 | #ifndef ASAN_FAKE_STACK_H |
| 16 | #define ASAN_FAKE_STACK_H |
| 17 | |
Kostya Serebryany | ac3ae5d | 2013-09-12 07:11:58 +0000 | [diff] [blame] | 18 | #include "sanitizer_common/sanitizer_common.h" |
| 19 | |
Kostya Serebryany | 244384d | 2013-04-11 11:39:19 +0000 | [diff] [blame] | 20 | namespace __asan { |
| 21 | |
| 22 | // Fake stack frame contains local variables of one function. |
Kostya Serebryany | 244384d | 2013-04-11 11:39:19 +0000 | [diff] [blame] | 23 | struct FakeFrame { |
| 24 | uptr magic; // Modified by the instrumented code. |
| 25 | uptr descr; // Modified by the instrumented code. |
Kostya Serebryany | ce0f7d1 | 2013-04-11 12:49:38 +0000 | [diff] [blame] | 26 | uptr pc; // Modified by the instrumented code. |
Kostya Serebryany | 0f22837 | 2013-09-13 07:50:44 +0000 | [diff] [blame] | 27 | uptr real_stack; |
Kostya Serebryany | 244384d | 2013-04-11 11:39:19 +0000 | [diff] [blame] | 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 |
Kostya Serebryany | ac3ae5d | 2013-09-12 07:11:58 +0000 | [diff] [blame] | 33 | // is not popped but remains there for quite some time until gets used again. |
Kostya Serebryany | 244384d | 2013-04-11 11:39:19 +0000 | [diff] [blame] | 34 | // So, we poison the objects on the fake stack when function returns. |
| 35 | // It helps us find use-after-return bugs. |
Kostya Serebryany | ac3ae5d | 2013-09-12 07:11:58 +0000 | [diff] [blame] | 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. |
Kostya Serebryany | 244384d | 2013-04-11 11:39:19 +0000 | [diff] [blame] | 57 | class FakeStack { |
Kostya Serebryany | ac3ae5d | 2013-09-12 07:11:58 +0000 | [diff] [blame] | 58 | static const uptr kMinStackFrameSizeLog = 6; // Min frame is 64B. |
| 59 | static const uptr kMaxStackFrameSizeLog = 16; // Max stack frame is 64K. |
| 60 | |
Kostya Serebryany | 244384d | 2013-04-11 11:39:19 +0000 | [diff] [blame] | 61 | public: |
Kostya Serebryany | ac3ae5d | 2013-09-12 07:11:58 +0000 | [diff] [blame] | 62 | static const uptr kNumberOfSizeClasses = |
| 63 | kMaxStackFrameSizeLog - kMinStackFrameSizeLog + 1; |
| 64 | |
| 65 | // CTOR: create the FakeStack as a single mmap-ed object. |
Kostya Serebryany | e1c68c3 | 2013-09-27 11:37:23 +0000 | [diff] [blame] | 66 | static FakeStack *Create(uptr stack_size_log); |
Kostya Serebryany | ac3ae5d | 2013-09-12 07:11:58 +0000 | [diff] [blame] | 67 | |
Kostya Serebryany | e1c68c3 | 2013-09-27 11:37:23 +0000 | [diff] [blame] | 68 | void Destroy(); |
Kostya Serebryany | ac3ae5d | 2013-09-12 07:11:58 +0000 | [diff] [blame] | 69 | |
| 70 | // stack_size_log is at least 15 (stack_size >= 32K). |
| 71 | static uptr SizeRequiredForFlags(uptr stack_size_log) { |
| 72 | return 1UL << (stack_size_log + 1 - kMinStackFrameSizeLog); |
| 73 | } |
| 74 | |
| 75 | // Each size class occupies stack_size bytes. |
| 76 | static uptr SizeRequiredForFrames(uptr stack_size_log) { |
| 77 | return (1ULL << stack_size_log) * kNumberOfSizeClasses; |
| 78 | } |
| 79 | |
| 80 | // Number of bytes requires for the whole object. |
| 81 | static uptr RequiredSize(uptr stack_size_log) { |
| 82 | return kFlagsOffset + SizeRequiredForFlags(stack_size_log) + |
| 83 | SizeRequiredForFrames(stack_size_log); |
| 84 | } |
| 85 | |
| 86 | // Offset of the given flag from the first flag. |
| 87 | // The flags for class 0 begin at offset 000000000 |
| 88 | // The flags for class 1 begin at offset 100000000 |
| 89 | // ....................2................ 110000000 |
| 90 | // ....................3................ 111000000 |
| 91 | // and so on. |
| 92 | static uptr FlagsOffset(uptr stack_size_log, uptr class_id) { |
| 93 | uptr t = kNumberOfSizeClasses - 1 - class_id; |
| 94 | const uptr all_ones = (1 << (kNumberOfSizeClasses - 1)) - 1; |
| 95 | return ((all_ones >> t) << t) << (stack_size_log - 15); |
| 96 | } |
| 97 | |
| 98 | static uptr NumberOfFrames(uptr stack_size_log, uptr class_id) { |
| 99 | return 1UL << (stack_size_log - kMinStackFrameSizeLog - class_id); |
| 100 | } |
| 101 | |
| 102 | // Divide n by the numbe of frames in size class. |
| 103 | static uptr ModuloNumberOfFrames(uptr stack_size_log, uptr class_id, uptr n) { |
| 104 | return n & (NumberOfFrames(stack_size_log, class_id) - 1); |
| 105 | } |
| 106 | |
| 107 | // The the pointer to the flags of the given class_id. |
| 108 | u8 *GetFlags(uptr stack_size_log, uptr class_id) { |
| 109 | return reinterpret_cast<u8 *>(this) + kFlagsOffset + |
| 110 | FlagsOffset(stack_size_log, class_id); |
| 111 | } |
| 112 | |
| 113 | // Get frame by class_id and pos. |
| 114 | u8 *GetFrame(uptr stack_size_log, uptr class_id, uptr pos) { |
| 115 | return reinterpret_cast<u8 *>(this) + kFlagsOffset + |
| 116 | SizeRequiredForFlags(stack_size_log) + |
| 117 | (1 << stack_size_log) * class_id + BytesInSizeClass(class_id) * pos; |
| 118 | } |
| 119 | |
| 120 | // Allocate the fake frame. |
| 121 | FakeFrame *Allocate(uptr stack_size_log, uptr class_id, uptr real_stack); |
| 122 | |
Kostya Serebryany | b388987 | 2013-09-17 07:42:54 +0000 | [diff] [blame] | 123 | // Deallocate the fake frame: read the saved flag address and write 0 there. |
| 124 | static void Deallocate(uptr x, uptr class_id) { |
| 125 | **SavedFlagPtr(x, class_id) = 0; |
| 126 | } |
Kostya Serebryany | ac3ae5d | 2013-09-12 07:11:58 +0000 | [diff] [blame] | 127 | |
| 128 | // Poison the entire FakeStack's shadow with the magic value. |
| 129 | void PoisonAll(u8 magic); |
| 130 | |
| 131 | // Return the beginning of the FakeFrame or 0 if the address is not ours. |
Kostya Serebryany | 244384d | 2013-04-11 11:39:19 +0000 | [diff] [blame] | 132 | uptr AddrIsInFakeStack(uptr addr); |
Kostya Serebryany | 244384d | 2013-04-11 11:39:19 +0000 | [diff] [blame] | 133 | |
Kostya Serebryany | ac3ae5d | 2013-09-12 07:11:58 +0000 | [diff] [blame] | 134 | // Number of bytes in a fake frame of this size class. |
| 135 | static uptr BytesInSizeClass(uptr class_id) { |
Kostya Serebryany | 34e3ed1 | 2013-09-10 13:16:26 +0000 | [diff] [blame] | 136 | return 1UL << (class_id + kMinStackFrameSizeLog); |
| 137 | } |
| 138 | |
Kostya Serebryany | b388987 | 2013-09-17 07:42:54 +0000 | [diff] [blame] | 139 | // The fake frame is guaranteed to have a right redzone. |
| 140 | // We use the last word of that redzone to store the address of the flag |
| 141 | // that corresponds to the current frame to make faster deallocation. |
| 142 | static u8 **SavedFlagPtr(uptr x, uptr class_id) { |
| 143 | return reinterpret_cast<u8 **>(x + BytesInSizeClass(class_id) - sizeof(x)); |
| 144 | } |
| 145 | |
Kostya Serebryany | ac3ae5d | 2013-09-12 07:11:58 +0000 | [diff] [blame] | 146 | uptr stack_size_log() const { return stack_size_log_; } |
| 147 | |
Kostya Serebryany | 89de457 | 2013-09-12 13:25:29 +0000 | [diff] [blame] | 148 | void HandleNoReturn(); |
| 149 | void GC(uptr real_stack); |
| 150 | |
Sergey Matveev | c519335 | 2013-10-14 14:04:50 +0000 | [diff] [blame] | 151 | void ForEachFakeFrame(RangeIteratorCallback callback, void *arg); |
| 152 | |
Kostya Serebryany | 244384d | 2013-04-11 11:39:19 +0000 | [diff] [blame] | 153 | private: |
Kostya Serebryany | ac3ae5d | 2013-09-12 07:11:58 +0000 | [diff] [blame] | 154 | FakeStack() { } |
Kostya Serebryany | 89de457 | 2013-09-12 13:25:29 +0000 | [diff] [blame] | 155 | static const uptr kFlagsOffset = 4096; // This is were the flags begin. |
Kostya Serebryany | 34e3ed1 | 2013-09-10 13:16:26 +0000 | [diff] [blame] | 156 | // Must match the number of uses of DEFINE_STACK_MALLOC_FREE_WITH_CLASS_ID |
| 157 | COMPILER_CHECK(kNumberOfSizeClasses == 11); |
| 158 | static const uptr kMaxStackMallocSize = 1 << kMaxStackFrameSizeLog; |
Kostya Serebryany | 244384d | 2013-04-11 11:39:19 +0000 | [diff] [blame] | 159 | |
Kostya Serebryany | ac3ae5d | 2013-09-12 07:11:58 +0000 | [diff] [blame] | 160 | uptr hint_position_[kNumberOfSizeClasses]; |
| 161 | uptr stack_size_log_; |
Kostya Serebryany | 89de457 | 2013-09-12 13:25:29 +0000 | [diff] [blame] | 162 | // a bit is set if something was allocated from the corresponding size class. |
Kostya Serebryany | 89de457 | 2013-09-12 13:25:29 +0000 | [diff] [blame] | 163 | bool needs_gc_; |
Kostya Serebryany | 244384d | 2013-04-11 11:39:19 +0000 | [diff] [blame] | 164 | }; |
| 165 | |
Kostya Serebryany | 9433af3 | 2013-09-13 06:32:26 +0000 | [diff] [blame] | 166 | FakeStack *GetTLSFakeStack(); |
| 167 | void SetTLSFakeStack(FakeStack *fs); |
| 168 | |
Kostya Serebryany | 244384d | 2013-04-11 11:39:19 +0000 | [diff] [blame] | 169 | } // namespace __asan |
| 170 | |
| 171 | #endif // ASAN_FAKE_STACK_H |