diff options
Diffstat (limited to 'lib/asan/asan_fake_stack.h')
| -rw-r--r-- | lib/asan/asan_fake_stack.h | 196 |
1 files changed, 125 insertions, 71 deletions
diff --git a/lib/asan/asan_fake_stack.h b/lib/asan/asan_fake_stack.h index 308b4c571832..f17ee0268917 100644 --- a/lib/asan/asan_fake_stack.h +++ b/lib/asan/asan_fake_stack.h @@ -9,12 +9,14 @@ // // This file is a part of AddressSanitizer, an address sanity checker. // -// ASan-private header for asan_fake_stack.cc +// ASan-private header for asan_fake_stack.cc, implements FakeStack. //===----------------------------------------------------------------------===// #ifndef ASAN_FAKE_STACK_H #define ASAN_FAKE_STACK_H +#include "sanitizer_common/sanitizer_common.h" + namespace __asan { // Fake stack frame contains local variables of one function. @@ -22,96 +24,148 @@ struct FakeFrame { uptr magic; // Modified by the instrumented code. uptr descr; // Modified by the instrumented code. uptr pc; // Modified by the instrumented code. - u64 real_stack : 48; - u64 size_minus_one : 16; - // End of the first 32 bytes. - // The rest should not be used when the frame is active. - FakeFrame *next; -}; - -struct FakeFrameFifo { - public: - void FifoPush(FakeFrame *node); - FakeFrame *FifoPop(); - private: - FakeFrame *first_, *last_; -}; - -template<uptr kMaxNumberOfFrames> -class FakeFrameLifo { - public: - explicit FakeFrameLifo(LinkerInitialized) {} - FakeFrameLifo() : n_frames_(0) {} - void LifoPush(FakeFrame *node) { - CHECK_LT(n_frames_, kMaxNumberOfFrames); - frames_[n_frames_++] = node; - } - void LifoPop() { - CHECK(n_frames_); - n_frames_--; - } - FakeFrame *top() { - if (n_frames_ == 0) - return 0; - return frames_[n_frames_ - 1]; - } - private: - uptr n_frames_; - FakeFrame *frames_[kMaxNumberOfFrames]; + uptr real_stack; }; // For each thread we create a fake stack and place stack objects on this fake // stack instead of the real stack. The fake stack is not really a stack but // a fast malloc-like allocator so that when a function exits the fake stack -// is not poped but remains there for quite some time until gets used again. +// is not popped but remains there for quite some time until gets used again. // So, we poison the objects on the fake stack when function returns. // It helps us find use-after-return bugs. -// We can not rely on __asan_stack_free being called on every function exit, -// so we maintain a lifo list of all current fake frames and update it on every -// call to __asan_stack_malloc. +// +// The FakeStack objects is allocated by a single mmap call and has no other +// pointers. The size of the fake stack depends on the actual thread stack size +// and thus can not be a constant. +// stack_size is a power of two greater or equal to the thread's stack size; +// we store it as its logarithm (stack_size_log). +// FakeStack has kNumberOfSizeClasses (11) size classes, each size class +// is a power of two, starting from 64 bytes. Each size class occupies +// stack_size bytes and thus can allocate +// NumberOfFrames=(stack_size/BytesInSizeClass) fake frames (also a power of 2). +// For each size class we have NumberOfFrames allocation flags, +// each flag indicates whether the given frame is currently allocated. +// All flags for size classes 0 .. 10 are stored in a single contiguous region +// followed by another contiguous region which contains the actual memory for +// size classes. The addresses are computed by GetFlags and GetFrame without +// any memory accesses solely based on 'this' and stack_size_log. +// Allocate() flips the appropriate allocation flag atomically, thus achieving +// async-signal safety. +// This allocator does not have quarantine per se, but it tries to allocate the +// frames in round robin fasion to maximize the delay between a deallocation +// and the next allocation. class FakeStack { - public: - FakeStack(); - explicit FakeStack(LinkerInitialized x) : call_stack_(x) {} - void Init(uptr stack_size); - void StopUsingFakeStack() { alive_ = false; } - void Cleanup(); - uptr AllocateStack(uptr size, uptr real_stack); - static void OnFree(uptr ptr, uptr size, uptr real_stack); - // Return the bottom of the maped region. - uptr AddrIsInFakeStack(uptr addr); - bool StackSize() { return stack_size_; } - - private: - static const uptr kMinStackFrameSizeLog = 9; // Min frame is 512B. + static const uptr kMinStackFrameSizeLog = 6; // Min frame is 64B. static const uptr kMaxStackFrameSizeLog = 16; // Max stack frame is 64K. - static const uptr kMaxStackMallocSize = 1 << kMaxStackFrameSizeLog; + + public: static const uptr kNumberOfSizeClasses = - kMaxStackFrameSizeLog - kMinStackFrameSizeLog + 1; - static const uptr kMaxRecursionDepth = 1023; + kMaxStackFrameSizeLog - kMinStackFrameSizeLog + 1; + + // CTOR: create the FakeStack as a single mmap-ed object. + static FakeStack *Create(uptr stack_size_log); + + void Destroy(); + + // stack_size_log is at least 15 (stack_size >= 32K). + static uptr SizeRequiredForFlags(uptr stack_size_log) { + return 1UL << (stack_size_log + 1 - kMinStackFrameSizeLog); + } - bool AddrIsInSizeClass(uptr addr, uptr size_class); + // Each size class occupies stack_size bytes. + static uptr SizeRequiredForFrames(uptr stack_size_log) { + return (1ULL << stack_size_log) * kNumberOfSizeClasses; + } + + // Number of bytes requires for the whole object. + static uptr RequiredSize(uptr stack_size_log) { + return kFlagsOffset + SizeRequiredForFlags(stack_size_log) + + SizeRequiredForFrames(stack_size_log); + } + + // Offset of the given flag from the first flag. + // The flags for class 0 begin at offset 000000000 + // The flags for class 1 begin at offset 100000000 + // ....................2................ 110000000 + // ....................3................ 111000000 + // and so on. + static uptr FlagsOffset(uptr stack_size_log, uptr class_id) { + uptr t = kNumberOfSizeClasses - 1 - class_id; + const uptr all_ones = (1 << (kNumberOfSizeClasses - 1)) - 1; + return ((all_ones >> t) << t) << (stack_size_log - 15); + } + + static uptr NumberOfFrames(uptr stack_size_log, uptr class_id) { + return 1UL << (stack_size_log - kMinStackFrameSizeLog - class_id); + } + + // Divide n by the numbe of frames in size class. + static uptr ModuloNumberOfFrames(uptr stack_size_log, uptr class_id, uptr n) { + return n & (NumberOfFrames(stack_size_log, class_id) - 1); + } + + // The the pointer to the flags of the given class_id. + u8 *GetFlags(uptr stack_size_log, uptr class_id) { + return reinterpret_cast<u8 *>(this) + kFlagsOffset + + FlagsOffset(stack_size_log, class_id); + } + + // Get frame by class_id and pos. + u8 *GetFrame(uptr stack_size_log, uptr class_id, uptr pos) { + return reinterpret_cast<u8 *>(this) + kFlagsOffset + + SizeRequiredForFlags(stack_size_log) + + (1 << stack_size_log) * class_id + BytesInSizeClass(class_id) * pos; + } + + // Allocate the fake frame. + FakeFrame *Allocate(uptr stack_size_log, uptr class_id, uptr real_stack); + + // Deallocate the fake frame: read the saved flag address and write 0 there. + static void Deallocate(uptr x, uptr class_id) { + **SavedFlagPtr(x, class_id) = 0; + } + + // Poison the entire FakeStack's shadow with the magic value. + void PoisonAll(u8 magic); + + // Return the beginning of the FakeFrame or 0 if the address is not ours. + uptr AddrIsInFakeStack(uptr addr); - // Each size class should be large enough to hold all frames. - uptr ClassMmapSize(uptr size_class); + // Number of bytes in a fake frame of this size class. + static uptr BytesInSizeClass(uptr class_id) { + return 1UL << (class_id + kMinStackFrameSizeLog); + } - uptr ClassSize(uptr size_class) { - return 1UL << (size_class + kMinStackFrameSizeLog); + // The fake frame is guaranteed to have a right redzone. + // We use the last word of that redzone to store the address of the flag + // that corresponds to the current frame to make faster deallocation. + static u8 **SavedFlagPtr(uptr x, uptr class_id) { + return reinterpret_cast<u8 **>(x + BytesInSizeClass(class_id) - sizeof(x)); } - void DeallocateFrame(FakeFrame *fake_frame); + uptr stack_size_log() const { return stack_size_log_; } + + void HandleNoReturn(); + void GC(uptr real_stack); - uptr ComputeSizeClass(uptr alloc_size); - void AllocateOneSizeClass(uptr size_class); + void ForEachFakeFrame(RangeIteratorCallback callback, void *arg); - uptr stack_size_; - bool alive_; + private: + FakeStack() { } + static const uptr kFlagsOffset = 4096; // This is were the flags begin. + // Must match the number of uses of DEFINE_STACK_MALLOC_FREE_WITH_CLASS_ID + COMPILER_CHECK(kNumberOfSizeClasses == 11); + static const uptr kMaxStackMallocSize = 1 << kMaxStackFrameSizeLog; - uptr allocated_size_classes_[kNumberOfSizeClasses]; - FakeFrameFifo size_classes_[kNumberOfSizeClasses]; - FakeFrameLifo<kMaxRecursionDepth> call_stack_; + uptr hint_position_[kNumberOfSizeClasses]; + uptr stack_size_log_; + // a bit is set if something was allocated from the corresponding size class. + bool needs_gc_; }; +FakeStack *GetTLSFakeStack(); +void SetTLSFakeStack(FakeStack *fs); + } // namespace __asan #endif // ASAN_FAKE_STACK_H |