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