libsanitizer/asan/asan_fake_stack.h

   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