1244384d1a8a518c0b1ceaa5809333a91db1104b6Kostya Serebryany//===-- asan_fake_stack.h ---------------------------------------*- C++ -*-===// 2244384d1a8a518c0b1ceaa5809333a91db1104b6Kostya Serebryany// 3244384d1a8a518c0b1ceaa5809333a91db1104b6Kostya Serebryany// The LLVM Compiler Infrastructure 4244384d1a8a518c0b1ceaa5809333a91db1104b6Kostya Serebryany// 5244384d1a8a518c0b1ceaa5809333a91db1104b6Kostya Serebryany// This file is distributed under the University of Illinois Open Source 6244384d1a8a518c0b1ceaa5809333a91db1104b6Kostya Serebryany// License. See LICENSE.TXT for details. 7244384d1a8a518c0b1ceaa5809333a91db1104b6Kostya Serebryany// 8244384d1a8a518c0b1ceaa5809333a91db1104b6Kostya Serebryany//===----------------------------------------------------------------------===// 9244384d1a8a518c0b1ceaa5809333a91db1104b6Kostya Serebryany// 10244384d1a8a518c0b1ceaa5809333a91db1104b6Kostya Serebryany// This file is a part of AddressSanitizer, an address sanity checker. 11244384d1a8a518c0b1ceaa5809333a91db1104b6Kostya Serebryany// 12ac3ae5dc29d3623ada2bcb0db22ee88b0382e3b1Kostya Serebryany// ASan-private header for asan_fake_stack.cc, implements FakeStack. 13244384d1a8a518c0b1ceaa5809333a91db1104b6Kostya Serebryany//===----------------------------------------------------------------------===// 14244384d1a8a518c0b1ceaa5809333a91db1104b6Kostya Serebryany 15244384d1a8a518c0b1ceaa5809333a91db1104b6Kostya Serebryany#ifndef ASAN_FAKE_STACK_H 16244384d1a8a518c0b1ceaa5809333a91db1104b6Kostya Serebryany#define ASAN_FAKE_STACK_H 17244384d1a8a518c0b1ceaa5809333a91db1104b6Kostya Serebryany 18ac3ae5dc29d3623ada2bcb0db22ee88b0382e3b1Kostya Serebryany#include "sanitizer_common/sanitizer_common.h" 19ac3ae5dc29d3623ada2bcb0db22ee88b0382e3b1Kostya Serebryany 20244384d1a8a518c0b1ceaa5809333a91db1104b6Kostya Serebryanynamespace __asan { 21244384d1a8a518c0b1ceaa5809333a91db1104b6Kostya Serebryany 22244384d1a8a518c0b1ceaa5809333a91db1104b6Kostya Serebryany// Fake stack frame contains local variables of one function. 23244384d1a8a518c0b1ceaa5809333a91db1104b6Kostya Serebryanystruct FakeFrame { 24244384d1a8a518c0b1ceaa5809333a91db1104b6Kostya Serebryany uptr magic; // Modified by the instrumented code. 25244384d1a8a518c0b1ceaa5809333a91db1104b6Kostya Serebryany uptr descr; // Modified by the instrumented code. 26ce0f7d13a6d2f1c141bc247aa75770cb88b38cb6Kostya Serebryany uptr pc; // Modified by the instrumented code. 270f2283742e1d37ebf0c5ac034dab704a7d9af099Kostya Serebryany uptr real_stack; 28244384d1a8a518c0b1ceaa5809333a91db1104b6Kostya Serebryany}; 29244384d1a8a518c0b1ceaa5809333a91db1104b6Kostya Serebryany 30244384d1a8a518c0b1ceaa5809333a91db1104b6Kostya Serebryany// For each thread we create a fake stack and place stack objects on this fake 31244384d1a8a518c0b1ceaa5809333a91db1104b6Kostya Serebryany// stack instead of the real stack. The fake stack is not really a stack but 32244384d1a8a518c0b1ceaa5809333a91db1104b6Kostya Serebryany// a fast malloc-like allocator so that when a function exits the fake stack 33ac3ae5dc29d3623ada2bcb0db22ee88b0382e3b1Kostya Serebryany// is not popped but remains there for quite some time until gets used again. 34244384d1a8a518c0b1ceaa5809333a91db1104b6Kostya Serebryany// So, we poison the objects on the fake stack when function returns. 35244384d1a8a518c0b1ceaa5809333a91db1104b6Kostya Serebryany// It helps us find use-after-return bugs. 36ac3ae5dc29d3623ada2bcb0db22ee88b0382e3b1Kostya Serebryany// 37ac3ae5dc29d3623ada2bcb0db22ee88b0382e3b1Kostya Serebryany// The FakeStack objects is allocated by a single mmap call and has no other 38ac3ae5dc29d3623ada2bcb0db22ee88b0382e3b1Kostya Serebryany// pointers. The size of the fake stack depends on the actual thread stack size 39ac3ae5dc29d3623ada2bcb0db22ee88b0382e3b1Kostya Serebryany// and thus can not be a constant. 40ac3ae5dc29d3623ada2bcb0db22ee88b0382e3b1Kostya Serebryany// stack_size is a power of two greater or equal to the thread's stack size; 41ac3ae5dc29d3623ada2bcb0db22ee88b0382e3b1Kostya Serebryany// we store it as its logarithm (stack_size_log). 42ac3ae5dc29d3623ada2bcb0db22ee88b0382e3b1Kostya Serebryany// FakeStack has kNumberOfSizeClasses (11) size classes, each size class 43ac3ae5dc29d3623ada2bcb0db22ee88b0382e3b1Kostya Serebryany// is a power of two, starting from 64 bytes. Each size class occupies 44ac3ae5dc29d3623ada2bcb0db22ee88b0382e3b1Kostya Serebryany// stack_size bytes and thus can allocate 45ac3ae5dc29d3623ada2bcb0db22ee88b0382e3b1Kostya Serebryany// NumberOfFrames=(stack_size/BytesInSizeClass) fake frames (also a power of 2). 46ac3ae5dc29d3623ada2bcb0db22ee88b0382e3b1Kostya Serebryany// For each size class we have NumberOfFrames allocation flags, 47ac3ae5dc29d3623ada2bcb0db22ee88b0382e3b1Kostya Serebryany// each flag indicates whether the given frame is currently allocated. 48ac3ae5dc29d3623ada2bcb0db22ee88b0382e3b1Kostya Serebryany// All flags for size classes 0 .. 10 are stored in a single contiguous region 49ac3ae5dc29d3623ada2bcb0db22ee88b0382e3b1Kostya Serebryany// followed by another contiguous region which contains the actual memory for 50ac3ae5dc29d3623ada2bcb0db22ee88b0382e3b1Kostya Serebryany// size classes. The addresses are computed by GetFlags and GetFrame without 51ac3ae5dc29d3623ada2bcb0db22ee88b0382e3b1Kostya Serebryany// any memory accesses solely based on 'this' and stack_size_log. 52ac3ae5dc29d3623ada2bcb0db22ee88b0382e3b1Kostya Serebryany// Allocate() flips the appropriate allocation flag atomically, thus achieving 53ac3ae5dc29d3623ada2bcb0db22ee88b0382e3b1Kostya Serebryany// async-signal safety. 54ac3ae5dc29d3623ada2bcb0db22ee88b0382e3b1Kostya Serebryany// This allocator does not have quarantine per se, but it tries to allocate the 55ac3ae5dc29d3623ada2bcb0db22ee88b0382e3b1Kostya Serebryany// frames in round robin fasion to maximize the delay between a deallocation 56ac3ae5dc29d3623ada2bcb0db22ee88b0382e3b1Kostya Serebryany// and the next allocation. 57244384d1a8a518c0b1ceaa5809333a91db1104b6Kostya Serebryanyclass FakeStack { 58ac3ae5dc29d3623ada2bcb0db22ee88b0382e3b1Kostya Serebryany static const uptr kMinStackFrameSizeLog = 6; // Min frame is 64B. 59ac3ae5dc29d3623ada2bcb0db22ee88b0382e3b1Kostya Serebryany static const uptr kMaxStackFrameSizeLog = 16; // Max stack frame is 64K. 60ac3ae5dc29d3623ada2bcb0db22ee88b0382e3b1Kostya Serebryany 61244384d1a8a518c0b1ceaa5809333a91db1104b6Kostya Serebryany public: 62ac3ae5dc29d3623ada2bcb0db22ee88b0382e3b1Kostya Serebryany static const uptr kNumberOfSizeClasses = 63ac3ae5dc29d3623ada2bcb0db22ee88b0382e3b1Kostya Serebryany kMaxStackFrameSizeLog - kMinStackFrameSizeLog + 1; 64ac3ae5dc29d3623ada2bcb0db22ee88b0382e3b1Kostya Serebryany 65ac3ae5dc29d3623ada2bcb0db22ee88b0382e3b1Kostya Serebryany // CTOR: create the FakeStack as a single mmap-ed object. 66e1c68c319a0113be832da17a777892353a8b5f23Kostya Serebryany static FakeStack *Create(uptr stack_size_log); 67244384d1a8a518c0b1ceaa5809333a91db1104b6Kostya Serebryany 682d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines void Destroy(int tid); 6934e3ed1db94c5ce9784d7ffb8d66a54cf523e09cKostya Serebryany 70ac3ae5dc29d3623ada2bcb0db22ee88b0382e3b1Kostya Serebryany // stack_size_log is at least 15 (stack_size >= 32K). 71ac3ae5dc29d3623ada2bcb0db22ee88b0382e3b1Kostya Serebryany static uptr SizeRequiredForFlags(uptr stack_size_log) { 72ac3ae5dc29d3623ada2bcb0db22ee88b0382e3b1Kostya Serebryany return 1UL << (stack_size_log + 1 - kMinStackFrameSizeLog); 7334e3ed1db94c5ce9784d7ffb8d66a54cf523e09cKostya Serebryany } 7434e3ed1db94c5ce9784d7ffb8d66a54cf523e09cKostya Serebryany 75ac3ae5dc29d3623ada2bcb0db22ee88b0382e3b1Kostya Serebryany // Each size class occupies stack_size bytes. 76ac3ae5dc29d3623ada2bcb0db22ee88b0382e3b1Kostya Serebryany static uptr SizeRequiredForFrames(uptr stack_size_log) { 77ac3ae5dc29d3623ada2bcb0db22ee88b0382e3b1Kostya Serebryany return (1ULL << stack_size_log) * kNumberOfSizeClasses; 78ac3ae5dc29d3623ada2bcb0db22ee88b0382e3b1Kostya Serebryany } 79244384d1a8a518c0b1ceaa5809333a91db1104b6Kostya Serebryany 80ac3ae5dc29d3623ada2bcb0db22ee88b0382e3b1Kostya Serebryany // Number of bytes requires for the whole object. 81ac3ae5dc29d3623ada2bcb0db22ee88b0382e3b1Kostya Serebryany static uptr RequiredSize(uptr stack_size_log) { 82ac3ae5dc29d3623ada2bcb0db22ee88b0382e3b1Kostya Serebryany return kFlagsOffset + SizeRequiredForFlags(stack_size_log) + 83ac3ae5dc29d3623ada2bcb0db22ee88b0382e3b1Kostya Serebryany SizeRequiredForFrames(stack_size_log); 84ac3ae5dc29d3623ada2bcb0db22ee88b0382e3b1Kostya Serebryany } 85244384d1a8a518c0b1ceaa5809333a91db1104b6Kostya Serebryany 86ac3ae5dc29d3623ada2bcb0db22ee88b0382e3b1Kostya Serebryany // Offset of the given flag from the first flag. 87ac3ae5dc29d3623ada2bcb0db22ee88b0382e3b1Kostya Serebryany // The flags for class 0 begin at offset 000000000 88ac3ae5dc29d3623ada2bcb0db22ee88b0382e3b1Kostya Serebryany // The flags for class 1 begin at offset 100000000 89ac3ae5dc29d3623ada2bcb0db22ee88b0382e3b1Kostya Serebryany // ....................2................ 110000000 90ac3ae5dc29d3623ada2bcb0db22ee88b0382e3b1Kostya Serebryany // ....................3................ 111000000 91ac3ae5dc29d3623ada2bcb0db22ee88b0382e3b1Kostya Serebryany // and so on. 92ac3ae5dc29d3623ada2bcb0db22ee88b0382e3b1Kostya Serebryany static uptr FlagsOffset(uptr stack_size_log, uptr class_id) { 93ac3ae5dc29d3623ada2bcb0db22ee88b0382e3b1Kostya Serebryany uptr t = kNumberOfSizeClasses - 1 - class_id; 94ac3ae5dc29d3623ada2bcb0db22ee88b0382e3b1Kostya Serebryany const uptr all_ones = (1 << (kNumberOfSizeClasses - 1)) - 1; 95ac3ae5dc29d3623ada2bcb0db22ee88b0382e3b1Kostya Serebryany return ((all_ones >> t) << t) << (stack_size_log - 15); 96ac3ae5dc29d3623ada2bcb0db22ee88b0382e3b1Kostya Serebryany } 97244384d1a8a518c0b1ceaa5809333a91db1104b6Kostya Serebryany 98ac3ae5dc29d3623ada2bcb0db22ee88b0382e3b1Kostya Serebryany static uptr NumberOfFrames(uptr stack_size_log, uptr class_id) { 99ac3ae5dc29d3623ada2bcb0db22ee88b0382e3b1Kostya Serebryany return 1UL << (stack_size_log - kMinStackFrameSizeLog - class_id); 100ac3ae5dc29d3623ada2bcb0db22ee88b0382e3b1Kostya Serebryany } 101244384d1a8a518c0b1ceaa5809333a91db1104b6Kostya Serebryany 102ac3ae5dc29d3623ada2bcb0db22ee88b0382e3b1Kostya Serebryany // Divide n by the numbe of frames in size class. 103ac3ae5dc29d3623ada2bcb0db22ee88b0382e3b1Kostya Serebryany static uptr ModuloNumberOfFrames(uptr stack_size_log, uptr class_id, uptr n) { 104ac3ae5dc29d3623ada2bcb0db22ee88b0382e3b1Kostya Serebryany return n & (NumberOfFrames(stack_size_log, class_id) - 1); 105ac3ae5dc29d3623ada2bcb0db22ee88b0382e3b1Kostya Serebryany } 106244384d1a8a518c0b1ceaa5809333a91db1104b6Kostya Serebryany 107ac3ae5dc29d3623ada2bcb0db22ee88b0382e3b1Kostya Serebryany // The the pointer to the flags of the given class_id. 108ac3ae5dc29d3623ada2bcb0db22ee88b0382e3b1Kostya Serebryany u8 *GetFlags(uptr stack_size_log, uptr class_id) { 109ac3ae5dc29d3623ada2bcb0db22ee88b0382e3b1Kostya Serebryany return reinterpret_cast<u8 *>(this) + kFlagsOffset + 110ac3ae5dc29d3623ada2bcb0db22ee88b0382e3b1Kostya Serebryany FlagsOffset(stack_size_log, class_id); 111ac3ae5dc29d3623ada2bcb0db22ee88b0382e3b1Kostya Serebryany } 112244384d1a8a518c0b1ceaa5809333a91db1104b6Kostya Serebryany 113ac3ae5dc29d3623ada2bcb0db22ee88b0382e3b1Kostya Serebryany // Get frame by class_id and pos. 114ac3ae5dc29d3623ada2bcb0db22ee88b0382e3b1Kostya Serebryany u8 *GetFrame(uptr stack_size_log, uptr class_id, uptr pos) { 115ac3ae5dc29d3623ada2bcb0db22ee88b0382e3b1Kostya Serebryany return reinterpret_cast<u8 *>(this) + kFlagsOffset + 116ac3ae5dc29d3623ada2bcb0db22ee88b0382e3b1Kostya Serebryany SizeRequiredForFlags(stack_size_log) + 117ac3ae5dc29d3623ada2bcb0db22ee88b0382e3b1Kostya Serebryany (1 << stack_size_log) * class_id + BytesInSizeClass(class_id) * pos; 118ac3ae5dc29d3623ada2bcb0db22ee88b0382e3b1Kostya Serebryany } 119ac3ae5dc29d3623ada2bcb0db22ee88b0382e3b1Kostya Serebryany 120ac3ae5dc29d3623ada2bcb0db22ee88b0382e3b1Kostya Serebryany // Allocate the fake frame. 121ac3ae5dc29d3623ada2bcb0db22ee88b0382e3b1Kostya Serebryany FakeFrame *Allocate(uptr stack_size_log, uptr class_id, uptr real_stack); 122ac3ae5dc29d3623ada2bcb0db22ee88b0382e3b1Kostya Serebryany 123b388987bf988435ee87dc4848ea8e62ebfa942ebKostya Serebryany // Deallocate the fake frame: read the saved flag address and write 0 there. 124b388987bf988435ee87dc4848ea8e62ebfa942ebKostya Serebryany static void Deallocate(uptr x, uptr class_id) { 125b388987bf988435ee87dc4848ea8e62ebfa942ebKostya Serebryany **SavedFlagPtr(x, class_id) = 0; 126b388987bf988435ee87dc4848ea8e62ebfa942ebKostya Serebryany } 127244384d1a8a518c0b1ceaa5809333a91db1104b6Kostya Serebryany 128ac3ae5dc29d3623ada2bcb0db22ee88b0382e3b1Kostya Serebryany // Poison the entire FakeStack's shadow with the magic value. 129ac3ae5dc29d3623ada2bcb0db22ee88b0382e3b1Kostya Serebryany void PoisonAll(u8 magic); 130ac3ae5dc29d3623ada2bcb0db22ee88b0382e3b1Kostya Serebryany 131ac3ae5dc29d3623ada2bcb0db22ee88b0382e3b1Kostya Serebryany // Return the beginning of the FakeFrame or 0 if the address is not ours. 1322d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines uptr AddrIsInFakeStack(uptr addr, uptr *frame_beg, uptr *frame_end); 1332d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines USED uptr AddrIsInFakeStack(uptr addr) { 1342d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines uptr t1, t2; 1352d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines return AddrIsInFakeStack(addr, &t1, &t2); 1362d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 137ac3ae5dc29d3623ada2bcb0db22ee88b0382e3b1Kostya Serebryany 138ac3ae5dc29d3623ada2bcb0db22ee88b0382e3b1Kostya Serebryany // Number of bytes in a fake frame of this size class. 139ac3ae5dc29d3623ada2bcb0db22ee88b0382e3b1Kostya Serebryany static uptr BytesInSizeClass(uptr class_id) { 140ac3ae5dc29d3623ada2bcb0db22ee88b0382e3b1Kostya Serebryany return 1UL << (class_id + kMinStackFrameSizeLog); 141ac3ae5dc29d3623ada2bcb0db22ee88b0382e3b1Kostya Serebryany } 142ac3ae5dc29d3623ada2bcb0db22ee88b0382e3b1Kostya Serebryany 143b388987bf988435ee87dc4848ea8e62ebfa942ebKostya Serebryany // The fake frame is guaranteed to have a right redzone. 144b388987bf988435ee87dc4848ea8e62ebfa942ebKostya Serebryany // We use the last word of that redzone to store the address of the flag 145b388987bf988435ee87dc4848ea8e62ebfa942ebKostya Serebryany // that corresponds to the current frame to make faster deallocation. 146b388987bf988435ee87dc4848ea8e62ebfa942ebKostya Serebryany static u8 **SavedFlagPtr(uptr x, uptr class_id) { 147b388987bf988435ee87dc4848ea8e62ebfa942ebKostya Serebryany return reinterpret_cast<u8 **>(x + BytesInSizeClass(class_id) - sizeof(x)); 148b388987bf988435ee87dc4848ea8e62ebfa942ebKostya Serebryany } 149b388987bf988435ee87dc4848ea8e62ebfa942ebKostya Serebryany 150ac3ae5dc29d3623ada2bcb0db22ee88b0382e3b1Kostya Serebryany uptr stack_size_log() const { return stack_size_log_; } 151ac3ae5dc29d3623ada2bcb0db22ee88b0382e3b1Kostya Serebryany 15289de457bd3ec40d38bc7860f88f1d4da473eacc4Kostya Serebryany void HandleNoReturn(); 15389de457bd3ec40d38bc7860f88f1d4da473eacc4Kostya Serebryany void GC(uptr real_stack); 15489de457bd3ec40d38bc7860f88f1d4da473eacc4Kostya Serebryany 155c519335c2d6d32acaac32c0595f08a05081567e7Sergey Matveev void ForEachFakeFrame(RangeIteratorCallback callback, void *arg); 156c519335c2d6d32acaac32c0595f08a05081567e7Sergey Matveev 157ac3ae5dc29d3623ada2bcb0db22ee88b0382e3b1Kostya Serebryany private: 158ac3ae5dc29d3623ada2bcb0db22ee88b0382e3b1Kostya Serebryany FakeStack() { } 15989de457bd3ec40d38bc7860f88f1d4da473eacc4Kostya Serebryany static const uptr kFlagsOffset = 4096; // This is were the flags begin. 160ac3ae5dc29d3623ada2bcb0db22ee88b0382e3b1Kostya Serebryany // Must match the number of uses of DEFINE_STACK_MALLOC_FREE_WITH_CLASS_ID 161ac3ae5dc29d3623ada2bcb0db22ee88b0382e3b1Kostya Serebryany COMPILER_CHECK(kNumberOfSizeClasses == 11); 162ac3ae5dc29d3623ada2bcb0db22ee88b0382e3b1Kostya Serebryany static const uptr kMaxStackMallocSize = 1 << kMaxStackFrameSizeLog; 163ac3ae5dc29d3623ada2bcb0db22ee88b0382e3b1Kostya Serebryany 164ac3ae5dc29d3623ada2bcb0db22ee88b0382e3b1Kostya Serebryany uptr hint_position_[kNumberOfSizeClasses]; 165ac3ae5dc29d3623ada2bcb0db22ee88b0382e3b1Kostya Serebryany uptr stack_size_log_; 16689de457bd3ec40d38bc7860f88f1d4da473eacc4Kostya Serebryany // a bit is set if something was allocated from the corresponding size class. 16789de457bd3ec40d38bc7860f88f1d4da473eacc4Kostya Serebryany bool needs_gc_; 168ac3ae5dc29d3623ada2bcb0db22ee88b0382e3b1Kostya Serebryany}; 1697a0bba457ee05ced3adf37a0c0790d0ed23a5446Kostya Serebryany 1709433af375c7813486be91d2ac76f5072ee41818dKostya SerebryanyFakeStack *GetTLSFakeStack(); 1719433af375c7813486be91d2ac76f5072ee41818dKostya Serebryanyvoid SetTLSFakeStack(FakeStack *fs); 1729433af375c7813486be91d2ac76f5072ee41818dKostya Serebryany 173244384d1a8a518c0b1ceaa5809333a91db1104b6Kostya Serebryany} // namespace __asan 174244384d1a8a518c0b1ceaa5809333a91db1104b6Kostya Serebryany 175244384d1a8a518c0b1ceaa5809333a91db1104b6Kostya Serebryany#endif // ASAN_FAKE_STACK_H 176