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