libsanitizer/asan/asan_allocator.h

   1 //===-- asan_allocator.h ----------------------------------------*- C++ -*-===//
   2 //
   3 // This file is distributed under the University of Illinois Open Source
   4 // License. See LICENSE.TXT for details.
   5 //
   6 //===----------------------------------------------------------------------===//
   7 //
   8 // This file is a part of AddressSanitizer, an address sanity checker.
   9 //
  10 // ASan-private header for asan_allocator.cc.
  11 //===----------------------------------------------------------------------===//
  12
  13 #ifndef ASAN_ALLOCATOR_H
  14 #define ASAN_ALLOCATOR_H
  15
  16 #include "asan_internal.h"
  17 #include "asan_interceptors.h"
  18 #include "sanitizer_common/sanitizer_list.h"
  19
  20 // We are in the process of transitioning from the old allocator (version 1)
  21 // to a new one (version 2). The change is quite intrusive so both allocators
  22 // will co-exist in the source base for a while. The actual allocator is chosen
  23 // at build time by redefining this macro.
  24 #ifndef ASAN_ALLOCATOR_VERSION
  25 # if (ASAN_LINUX && !ASAN_ANDROID) || ASAN_MAC || ASAN_WINDOWS
  26 #  define ASAN_ALLOCATOR_VERSION 2
  27 # else
  28 #  define ASAN_ALLOCATOR_VERSION 1
  29 # endif
  30 #endif  // ASAN_ALLOCATOR_VERSION
  31
  32 namespace __asan {
  33
  34 enum AllocType {
  35   FROM_MALLOC = 1,  // Memory block came from malloc, calloc, realloc, etc.
  36   FROM_NEW = 2,     // Memory block came from operator new.
  37   FROM_NEW_BR = 3   // Memory block came from operator new [ ]
  38 };
  39
  40 static const uptr kNumberOfSizeClasses = 255;
  41 struct AsanChunk;
  42
  43 void InitializeAllocator();
  44
  45 class AsanChunkView {
  46  public:
  47   explicit AsanChunkView(AsanChunk *chunk) : chunk_(chunk) {}
  48   bool IsValid() { return chunk_ != 0; }
  49   uptr Beg();       // first byte of user memory.
  50   uptr End();       // last byte of user memory.
  51   uptr UsedSize();  // size requested by the user.
  52   uptr AllocTid();
  53   uptr FreeTid();
  54   void GetAllocStack(StackTrace *stack);
  55   void GetFreeStack(StackTrace *stack);
  56   bool AddrIsInside(uptr addr, uptr access_size, sptr *offset) {
  57     if (addr >= Beg() && (addr + access_size) <= End()) {
  58       *offset = addr - Beg();
  59       return true;
  60     }
  61     return false;
  62   }
  63   bool AddrIsAtLeft(uptr addr, uptr access_size, sptr *offset) {
  64     (void)access_size;
  65     if (addr < Beg()) {
  66       *offset = Beg() - addr;
  67       return true;
  68     }
  69     return false;
  70   }
  71   bool AddrIsAtRight(uptr addr, uptr access_size, sptr *offset) {
  72     if (addr + access_size > End()) {
  73       *offset = addr - End();
  74       return true;
  75     }
  76     return false;
  77   }
  78
  79  private:
  80   AsanChunk *const chunk_;
  81 };
  82
  83 AsanChunkView FindHeapChunkByAddress(uptr address);
  84
  85 // List of AsanChunks with total size.
  86 class AsanChunkFifoList: public IntrusiveList<AsanChunk> {
  87  public:
  88   explicit AsanChunkFifoList(LinkerInitialized) { }
  89   AsanChunkFifoList() { clear(); }
  90   void Push(AsanChunk *n);
  91   void PushList(AsanChunkFifoList *q);
  92   AsanChunk *Pop();
  93   uptr size() { return size_; }
  94   void clear() {
  95     IntrusiveList<AsanChunk>::clear();
  96     size_ = 0;
  97   }
  98  private:
  99   uptr size_;
 100 };
 101
 102 struct AsanThreadLocalMallocStorage {
 103   explicit AsanThreadLocalMallocStorage(LinkerInitialized x)
 104 #if ASAN_ALLOCATOR_VERSION == 1
 105       : quarantine_(x)
 106 #endif
 107       { }
 108   AsanThreadLocalMallocStorage() {
 109     CHECK(REAL(memset));
 110     REAL(memset)(this, 0, sizeof(AsanThreadLocalMallocStorage));
 111   }
 112
 113 #if ASAN_ALLOCATOR_VERSION == 1
 114   AsanChunkFifoList quarantine_;
 115   AsanChunk *free_lists_[kNumberOfSizeClasses];
 116 #else
 117   uptr quarantine_cache[16];
 118   uptr allocator2_cache[96 * (512 * 8 + 16)];  // Opaque.
 119 #endif
 120   void CommitBack();
 121 };
 122
 123 // Fake stack frame contains local variables of one function.
 124 // This struct should fit into a stack redzone (32 bytes).
 125 struct FakeFrame {
 126   uptr magic;  // Modified by the instrumented code.
 127   uptr descr;  // Modified by the instrumented code.
 128   FakeFrame *next;
 129   u64 real_stack     : 48;
 130   u64 size_minus_one : 16;
 131 };
 132
 133 struct FakeFrameFifo {
 134  public:
 135   void FifoPush(FakeFrame *node);
 136   FakeFrame *FifoPop();
 137  private:
 138   FakeFrame *first_, *last_;
 139 };
 140
 141 class FakeFrameLifo {
 142  public:
 143   void LifoPush(FakeFrame *node) {
 144     node->next = top_;
 145     top_ = node;
 146   }
 147   void LifoPop() {
 148     CHECK(top_);
 149     top_ = top_->next;
 150   }
 151   FakeFrame *top() { return top_; }
 152  private:
 153   FakeFrame *top_;
 154 };
 155
 156 // For each thread we create a fake stack and place stack objects on this fake
 157 // stack instead of the real stack. The fake stack is not really a stack but
 158 // a fast malloc-like allocator so that when a function exits the fake stack
 159 // is not poped but remains there for quite some time until gets used again.
 160 // So, we poison the objects on the fake stack when function returns.
 161 // It helps us find use-after-return bugs.
 162 // We can not rely on __asan_stack_free being called on every function exit,
 163 // so we maintain a lifo list of all current fake frames and update it on every
 164 // call to __asan_stack_malloc.
 165 class FakeStack {
 166  public:
 167   FakeStack();
 168   explicit FakeStack(LinkerInitialized) {}
 169   void Init(uptr stack_size);
 170   void StopUsingFakeStack() { alive_ = false; }
 171   void Cleanup();
 172   uptr AllocateStack(uptr size, uptr real_stack);
 173   static void OnFree(uptr ptr, uptr size, uptr real_stack);
 174   // Return the bottom of the maped region.
 175   uptr AddrIsInFakeStack(uptr addr);
 176   bool StackSize() { return stack_size_; }
 177
 178  private:
 179   static const uptr kMinStackFrameSizeLog = 9;  // Min frame is 512B.
 180   static const uptr kMaxStackFrameSizeLog = 16;  // Max stack frame is 64K.
 181   static const uptr kMaxStackMallocSize = 1 << kMaxStackFrameSizeLog;
 182   static const uptr kNumberOfSizeClasses =
 183       kMaxStackFrameSizeLog - kMinStackFrameSizeLog + 1;
 184
 185   bool AddrIsInSizeClass(uptr addr, uptr size_class);
 186
 187   // Each size class should be large enough to hold all frames.
 188   uptr ClassMmapSize(uptr size_class);
 189
 190   uptr ClassSize(uptr size_class) {
 191     return 1UL << (size_class + kMinStackFrameSizeLog);
 192   }
 193
 194   void DeallocateFrame(FakeFrame *fake_frame);
 195
 196   uptr ComputeSizeClass(uptr alloc_size);
 197   void AllocateOneSizeClass(uptr size_class);
 198
 199   uptr stack_size_;
 200   bool   alive_;
 201
 202   uptr allocated_size_classes_[kNumberOfSizeClasses];
 203   FakeFrameFifo size_classes_[kNumberOfSizeClasses];
 204   FakeFrameLifo call_stack_;
 205 };
 206
 207 void *asan_memalign(uptr alignment, uptr size, StackTrace *stack,
 208                     AllocType alloc_type);
 209 void asan_free(void *ptr, StackTrace *stack, AllocType alloc_type);
 210
 211 void *asan_malloc(uptr size, StackTrace *stack);
 212 void *asan_calloc(uptr nmemb, uptr size, StackTrace *stack);
 213 void *asan_realloc(void *p, uptr size, StackTrace *stack);
 214 void *asan_valloc(uptr size, StackTrace *stack);
 215 void *asan_pvalloc(uptr size, StackTrace *stack);
 216
 217 int asan_posix_memalign(void **memptr, uptr alignment, uptr size,
 218                           StackTrace *stack);
 219 uptr asan_malloc_usable_size(void *ptr, StackTrace *stack);
 220
 221 uptr asan_mz_size(const void *ptr);
 222 void asan_mz_force_lock();
 223 void asan_mz_force_unlock();
 224
 225 void PrintInternalAllocatorStats();
 226
 227 }  // namespace __asan
 228 #endif  // ASAN_ALLOCATOR_H