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