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
  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 class AsanChunkView {
  44  public:
  45   explicit AsanChunkView(AsanChunk *chunk) : chunk_(chunk) {}
  46   bool IsValid() { return chunk_ != 0; }
  47   uptr Beg();       // first byte of user memory.
  48   uptr End();       // last byte of user memory.
  49   uptr UsedSize();  // size requested by the user.
  50   uptr AllocTid();
  51   uptr FreeTid();
  52   void GetAllocStack(StackTrace *stack);
  53   void GetFreeStack(StackTrace *stack);
  54   bool AddrIsInside(uptr addr, uptr access_size, uptr *offset) {
  55     if (addr >= Beg() && (addr + access_size) <= End()) {
  56       *offset = addr - Beg();
  57       return true;
  58     }
  59     return false;
  60   }
  61   bool AddrIsAtLeft(uptr addr, uptr access_size, uptr *offset) {
  62     (void)access_size;
  63     if (addr < Beg()) {
  64       *offset = Beg() - addr;
  65       return true;
  66     }
  67     return false;
  68   }
  69   bool AddrIsAtRight(uptr addr, uptr access_size, uptr *offset) {
  70     if (addr + access_size >= End()) {
  71       if (addr <= End())
  72         *offset = 0;
  73       else
  74         *offset = addr - End();
  75       return true;
  76     }
  77     return false;
  78   }
  79
  80  private:
  81   AsanChunk *const chunk_;
  82 };
  83
  84 AsanChunkView FindHeapChunkByAddress(uptr address);
  85
  86 // List of AsanChunks with total size.
  87 class AsanChunkFifoList: public IntrusiveList<AsanChunk> {
  88  public:
  89   explicit AsanChunkFifoList(LinkerInitialized) { }
  90   AsanChunkFifoList() { clear(); }
  91   void Push(AsanChunk *n);
  92   void PushList(AsanChunkFifoList *q);
  93   AsanChunk *Pop();
  94   uptr size() { return size_; }
  95   void clear() {
  96     IntrusiveList<AsanChunk>::clear();
  97     size_ = 0;
  98   }
  99  private:
 100   uptr size_;
 101 };
 102
 103 struct AsanThreadLocalMallocStorage {
 104   explicit AsanThreadLocalMallocStorage(LinkerInitialized x)
 105 #if ASAN_ALLOCATOR_VERSION == 1
 106       : quarantine_(x)
 107 #endif
 108       { }
 109   AsanThreadLocalMallocStorage() {
 110     CHECK(REAL(memset));
 111     REAL(memset)(this, 0, sizeof(AsanThreadLocalMallocStorage));
 112   }
 113
 114 #if ASAN_ALLOCATOR_VERSION == 1
 115   AsanChunkFifoList quarantine_;
 116   AsanChunk *free_lists_[kNumberOfSizeClasses];
 117 #else
 118   uptr quarantine_cache[16];
 119   uptr allocator2_cache[96 * (512 * 8 + 16)];  // Opaque.
 120 #endif
 121   void CommitBack();
 122 };
 123
 124 // Fake stack frame contains local variables of one function.
 125 // This struct should fit into a stack redzone (32 bytes).
 126 struct FakeFrame {
 127   uptr magic;  // Modified by the instrumented code.
 128   uptr descr;  // Modified by the instrumented code.
 129   FakeFrame *next;
 130   u64 real_stack     : 48;
 131   u64 size_minus_one : 16;
 132 };
 133
 134 struct FakeFrameFifo {
 135  public:
 136   void FifoPush(FakeFrame *node);
 137   FakeFrame *FifoPop();
 138  private:
 139   FakeFrame *first_, *last_;
 140 };
 141
 142 class FakeFrameLifo {
 143  public:
 144   void LifoPush(FakeFrame *node) {
 145     node->next = top_;
 146     top_ = node;
 147   }
 148   void LifoPop() {
 149     CHECK(top_);
 150     top_ = top_->next;
 151   }
 152   FakeFrame *top() { return top_; }
 153  private:
 154   FakeFrame *top_;
 155 };
 156
 157 // For each thread we create a fake stack and place stack objects on this fake
 158 // stack instead of the real stack. The fake stack is not really a stack but
 159 // a fast malloc-like allocator so that when a function exits the fake stack
 160 // is not poped but remains there for quite some time until gets used again.
 161 // So, we poison the objects on the fake stack when function returns.
 162 // It helps us find use-after-return bugs.
 163 // We can not rely on __asan_stack_free being called on every function exit,
 164 // so we maintain a lifo list of all current fake frames and update it on every
 165 // call to __asan_stack_malloc.
 166 class FakeStack {
 167  public:
 168   FakeStack();
 169   explicit FakeStack(LinkerInitialized) {}
 170   void Init(uptr stack_size);
 171   void StopUsingFakeStack() { alive_ = false; }
 172   void Cleanup();
 173   uptr AllocateStack(uptr size, uptr real_stack);
 174   static void OnFree(uptr ptr, uptr size, uptr real_stack);
 175   // Return the bottom of the maped region.
 176   uptr AddrIsInFakeStack(uptr addr);
 177   bool StackSize() { return stack_size_; }
 178
 179  private:
 180   static const uptr kMinStackFrameSizeLog = 9;  // Min frame is 512B.
 181   static const uptr kMaxStackFrameSizeLog = 16;  // Max stack frame is 64K.
 182   static const uptr kMaxStackMallocSize = 1 << kMaxStackFrameSizeLog;
 183   static const uptr kNumberOfSizeClasses =
 184       kMaxStackFrameSizeLog - kMinStackFrameSizeLog + 1;
 185
 186   bool AddrIsInSizeClass(uptr addr, uptr size_class);
 187
 188   // Each size class should be large enough to hold all frames.
 189   uptr ClassMmapSize(uptr size_class);
 190
 191   uptr ClassSize(uptr size_class) {
 192     return 1UL << (size_class + kMinStackFrameSizeLog);
 193   }
 194
 195   void DeallocateFrame(FakeFrame *fake_frame);
 196
 197   uptr ComputeSizeClass(uptr alloc_size);
 198   void AllocateOneSizeClass(uptr size_class);
 199
 200   uptr stack_size_;
 201   bool   alive_;
 202
 203   uptr allocated_size_classes_[kNumberOfSizeClasses];
 204   FakeFrameFifo size_classes_[kNumberOfSizeClasses];
 205   FakeFrameLifo call_stack_;
 206 };
 207
 208 void *asan_memalign(uptr alignment, uptr size, StackTrace *stack,
 209                     AllocType alloc_type);
 210 void asan_free(void *ptr, StackTrace *stack, AllocType alloc_type);
 211
 212 void *asan_malloc(uptr size, StackTrace *stack);
 213 void *asan_calloc(uptr nmemb, uptr size, StackTrace *stack);
 214 void *asan_realloc(void *p, uptr size, StackTrace *stack);
 215 void *asan_valloc(uptr size, StackTrace *stack);
 216 void *asan_pvalloc(uptr size, StackTrace *stack);
 217
 218 int asan_posix_memalign(void **memptr, uptr alignment, uptr size,
 219                           StackTrace *stack);
 220 uptr asan_malloc_usable_size(void *ptr, StackTrace *stack);
 221
 222 uptr asan_mz_size(const void *ptr);
 223 void asan_mz_force_lock();
 224 void asan_mz_force_unlock();
 225
 226 void PrintInternalAllocatorStats();
 227
 228 // Log2 and RoundUpToPowerOfTwo should be inlined for performance.
 229 #if defined(_WIN32) && !defined(__clang__)
 230 extern "C" {
 231 unsigned char _BitScanForward(unsigned long *index, unsigned long mask);  // NOLINT
 232 unsigned char _BitScanReverse(unsigned long *index, unsigned long mask);  // NOLINT
 233 #if defined(_WIN64)
 234 unsigned char _BitScanForward64(unsigned long *index, unsigned __int64 mask);  // NOLINT
 235 unsigned char _BitScanReverse64(unsigned long *index, unsigned __int64 mask);  // NOLINT
 236 #endif
 237 }
 238 #endif
 239
 240 static inline uptr Log2(uptr x) {
 241   CHECK(IsPowerOfTwo(x));
 242 #if !defined(_WIN32) || defined(__clang__)
 243   return __builtin_ctzl(x);
 244 #elif defined(_WIN64)
 245   unsigned long ret;  // NOLINT
 246   _BitScanForward64(&ret, x);
 247   return ret;
 248 #else
 249   unsigned long ret;  // NOLINT
 250   _BitScanForward(&ret, x);
 251   return ret;
 252 #endif
 253 }
 254
 255 static inline uptr RoundUpToPowerOfTwo(uptr size) {
 256   CHECK(size);
 257   if (IsPowerOfTwo(size)) return size;
 258
 259   unsigned long up;  // NOLINT
 260 #if !defined(_WIN32) || defined(__clang__)
 261   up = SANITIZER_WORDSIZE - 1 - __builtin_clzl(size);
 262 #elif defined(_WIN64)
 263   _BitScanReverse64(&up, size);
 264 #else
 265   _BitScanReverse(&up, size);
 266 #endif
 267   CHECK(size < (1ULL << (up + 1)));
 268   CHECK(size > (1ULL << up));
 269   return 1UL << (up + 1);
 270 }
 271
 272
 273 }  // namespace __asan
 274 #endif  // ASAN_ALLOCATOR_H