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