203 lines · c
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-exception6//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_H15#define ASAN_FAKE_STACK_H16 17#include "sanitizer_common/sanitizer_common.h"18 19namespace __asan {20 21// Fake stack frame contains local variables of one function.22struct 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 fake30// stack instead of the real stack. The fake stack is not really a stack but31// a fast malloc-like allocator so that when a function exits the fake stack32// 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// The FakeStack objects is allocated by a single mmap call and has no other36// pointers. The size of the fake stack depends on the actual thread stack size37// 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 is padded such that GetFrame() is aligned to BytesInSizeClass().41// FakeStack has kNumberOfSizeClasses (11) size classes, each size class42// is a power of two, starting from 64 bytes. Each size class occupies43// stack_size bytes and thus can allocate44// 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 region48// followed by another contiguous region which contains the actual memory for49// size classes. The addresses are computed by GetFlags and GetFrame without50// any memory accesses solely based on 'this' and stack_size_log.51// Allocate() flips the appropriate allocation flag atomically, thus achieving52// async-signal safety.53// This allocator does not have quarantine per se, but it tries to allocate the54// frames in round robin fashion to maximize the delay between a deallocation55// and the next allocation.56class FakeStack {57 static const uptr kMinStackFrameSizeLog = 6; // Min frame is 64B.58 static const uptr kMaxStackFrameSizeLog = 16; // Max stack frame is 64K.59 static_assert(kMaxStackFrameSizeLog >= kMinStackFrameSizeLog);60 61 static const u64 kMaxStackFrameSize = 1 << kMaxStackFrameSizeLog;62 63 public:64 static const uptr kNumberOfSizeClasses =65 kMaxStackFrameSizeLog - kMinStackFrameSizeLog + 1;66 67 // CTOR: create the FakeStack as a single mmap-ed object.68 static FakeStack *Create(uptr stack_size_log);69 70 void Destroy(int tid);71 72 // min_uar_stack_size_log is 16 (stack_size >= 64KB)73 static uptr SizeRequiredForFlags(uptr stack_size_log) {74 return ((uptr)1) << (stack_size_log + 1 - kMinStackFrameSizeLog);75 }76 77 // Each size class occupies stack_size bytes.78 static uptr SizeRequiredForFrames(uptr stack_size_log) {79 return (((uptr)1) << stack_size_log) * kNumberOfSizeClasses;80 }81 82 // Number of bytes requires for the whole object.83 static uptr RequiredSize(uptr stack_size_log) {84 return kFlagsOffset + SizeRequiredForFlags(stack_size_log) +85 SizeRequiredForFrames(stack_size_log);86 }87 88 // Offset of the given flag from the first flag.89 // The flags for class 0 begin at offset 00000000090 // The flags for class 1 begin at offset 10000000091 // ....................2................ 11000000092 // ....................3................ 11100000093 // and so on.94 static uptr FlagsOffset(uptr stack_size_log, uptr class_id) {95 uptr t = kNumberOfSizeClasses - 1 - class_id;96 const uptr all_ones = (((uptr)1) << (kNumberOfSizeClasses - 1)) - 1;97 return ((all_ones >> t) << t) << (stack_size_log - 15);98 }99 100 static uptr NumberOfFrames(uptr stack_size_log, uptr class_id) {101 return ((uptr)1) << (stack_size_log - kMinStackFrameSizeLog - class_id);102 }103 104 // Divide n by the number of frames in size class.105 static uptr ModuloNumberOfFrames(uptr stack_size_log, uptr class_id, uptr n) {106 return n & (NumberOfFrames(stack_size_log, class_id) - 1);107 }108 109 // The pointer to the flags of the given class_id.110 u8 *GetFlags(uptr stack_size_log, uptr class_id) {111 return reinterpret_cast<u8 *>(this) + kFlagsOffset +112 FlagsOffset(stack_size_log, class_id);113 }114 115 // Get frame by class_id and pos.116 // Return values are guaranteed to be aligned to BytesInSizeClass(class_id),117 // which is useful in combination with118 // ASanStackFrameLayout::ComputeASanStackFrameLayout().119 //120 // Note that alignment to 1<<kMaxStackFrameSizeLog (aka121 // BytesInSizeClass(max_class_id)) implies alignment to BytesInSizeClass()122 // for any class_id, since the class sizes are increasing powers of 2.123 //124 // 1) (this + kFlagsOffset + SizeRequiredForFlags())) is aligned to125 // 1<<kMaxStackFrameSizeLog (see FakeStack::Create)126 //127 // Note that SizeRequiredForFlags(16) == 2048. If FakeStack::Create() had128 // merely returned an address from mmap (4K-aligned), the addition would129 // not be 4K-aligned.130 // 2) We know that stack_size_log >= kMaxStackFrameSizeLog (otherwise you131 // couldn't store a single frame of that size in the entire stack)132 // hence (1<<stack_size_log) is aligned to 1<<kMaxStackFrameSizeLog133 // and ((1<<stack_size_log) * class_id) is aligned to134 // 1<<kMaxStackFrameSizeLog135 // 3) BytesInSizeClass(class_id) * pos is aligned to136 // BytesInSizeClass(class_id)137 // The sum of these is aligned to BytesInSizeClass(class_id).138 u8 *GetFrame(uptr stack_size_log, uptr class_id, uptr pos) {139 return reinterpret_cast<u8 *>(this) + kFlagsOffset +140 SizeRequiredForFlags(stack_size_log) +141 (((uptr)1) << stack_size_log) * class_id +142 BytesInSizeClass(class_id) * pos;143 }144 145 // Allocate the fake frame.146 FakeFrame *Allocate(uptr stack_size_log, uptr class_id, uptr real_stack);147 148 // Deallocate the fake frame: read the saved flag address and write 0 there.149 static void Deallocate(uptr x, uptr class_id) {150 **SavedFlagPtr(x, class_id) = 0;151 }152 153 // Poison the entire FakeStack's shadow with the magic value.154 void PoisonAll(u8 magic);155 156 // Return the beginning of the FakeFrame or 0 if the address is not ours.157 uptr AddrIsInFakeStack(uptr addr, uptr *frame_beg, uptr *frame_end);158 USED uptr AddrIsInFakeStack(uptr addr) {159 uptr t1, t2;160 return AddrIsInFakeStack(addr, &t1, &t2);161 }162 163 // Number of bytes in a fake frame of this size class.164 static uptr BytesInSizeClass(uptr class_id) {165 return ((uptr)1) << (class_id + kMinStackFrameSizeLog);166 }167 168 // The fake frame is guaranteed to have a right redzone.169 // We use the last word of that redzone to store the address of the flag170 // that corresponds to the current frame to make faster deallocation.171 static u8 **SavedFlagPtr(uptr x, uptr class_id) {172 return reinterpret_cast<u8 **>(x + BytesInSizeClass(class_id) - sizeof(x));173 }174 175 uptr stack_size_log() const { return stack_size_log_; }176 177 void HandleNoReturn();178 void GC(uptr real_stack);179 180 void ForEachFakeFrame(RangeIteratorCallback callback, void *arg);181 182 private:183 FakeStack() { }184 static const uptr kFlagsOffset = 4096; // This is where the flags begin.185 // Must match the number of uses of DEFINE_STACK_MALLOC_FREE_WITH_CLASS_ID186 COMPILER_CHECK(kNumberOfSizeClasses == 11);187 static const uptr kMaxStackMallocSize = ((uptr)1) << kMaxStackFrameSizeLog;188 189 uptr hint_position_[kNumberOfSizeClasses];190 uptr stack_size_log_;191 bool needs_gc_;192 // We allocated more memory than needed to ensure the FakeStack (and, by193 // extension, each of the fake stack frames) is aligned. We keep track of the194 // true start so that we can unmap it.195 void *true_start;196};197 198void ResetTLSFakeStack();199 200} // namespace __asan201 202#endif // ASAN_FAKE_STACK_H203