asan_allocator.h revision 245614
1229109Sed//===-- asan_allocator.h ----------------------------------------*- C++ -*-===// 2229109Sed// 3229109Sed// The LLVM Compiler Infrastructure 4229109Sed// 5229109Sed// This file is distributed under the University of Illinois Open Source 6229109Sed// License. See LICENSE.TXT for details. 7229109Sed// 8229109Sed//===----------------------------------------------------------------------===// 9229109Sed// 10229109Sed// This file is a part of AddressSanitizer, an address sanity checker. 11229109Sed// 12229109Sed// ASan-private header for asan_allocator.cc. 13229109Sed//===----------------------------------------------------------------------===// 14229109Sed 15229109Sed#ifndef ASAN_ALLOCATOR_H 16229109Sed#define ASAN_ALLOCATOR_H 17229109Sed 18229109Sed#include "asan_internal.h" 19229109Sed#include "asan_interceptors.h" 20245614Sandrew#include "sanitizer_common/sanitizer_list.h" 21229109Sed 22245614Sandrew// We are in the process of transitioning from the old allocator (version 1) 23245614Sandrew// to a new one (version 2). The change is quite intrusive so both allocators 24245614Sandrew// will co-exist in the source base for a while. The actual allocator is chosen 25245614Sandrew// at build time by redefining this macro. 26245614Sandrew#ifndef ASAN_ALLOCATOR_VERSION 27245614Sandrew# if ASAN_LINUX && !ASAN_ANDROID 28245614Sandrew# define ASAN_ALLOCATOR_VERSION 2 29245614Sandrew# else 30245614Sandrew# define ASAN_ALLOCATOR_VERSION 1 31245614Sandrew# endif 32245614Sandrew#endif // ASAN_ALLOCATOR_VERSION 33245614Sandrew 34229109Sednamespace __asan { 35229109Sed 36245614Sandrewenum AllocType { 37245614Sandrew FROM_MALLOC = 1, // Memory block came from malloc, calloc, realloc, etc. 38245614Sandrew FROM_NEW = 2, // Memory block came from operator new. 39245614Sandrew FROM_NEW_BR = 3 // Memory block came from operator new [ ] 40245614Sandrew}; 41245614Sandrew 42238901Sandrewstatic const uptr kNumberOfSizeClasses = 255; 43229109Sedstruct AsanChunk; 44229109Sed 45245614Sandrewclass AsanChunkView { 46229109Sed public: 47245614Sandrew explicit AsanChunkView(AsanChunk *chunk) : chunk_(chunk) {} 48245614Sandrew bool IsValid() { return chunk_ != 0; } 49245614Sandrew uptr Beg(); // first byte of user memory. 50245614Sandrew uptr End(); // last byte of user memory. 51245614Sandrew uptr UsedSize(); // size requested by the user. 52245614Sandrew uptr AllocTid(); 53245614Sandrew uptr FreeTid(); 54245614Sandrew void GetAllocStack(StackTrace *stack); 55245614Sandrew void GetFreeStack(StackTrace *stack); 56245614Sandrew bool AddrIsInside(uptr addr, uptr access_size, uptr *offset) { 57245614Sandrew if (addr >= Beg() && (addr + access_size) <= End()) { 58245614Sandrew *offset = addr - Beg(); 59245614Sandrew return true; 60245614Sandrew } 61245614Sandrew return false; 62245614Sandrew } 63245614Sandrew bool AddrIsAtLeft(uptr addr, uptr access_size, uptr *offset) { 64245614Sandrew (void)access_size; 65245614Sandrew if (addr < Beg()) { 66245614Sandrew *offset = Beg() - addr; 67245614Sandrew return true; 68245614Sandrew } 69245614Sandrew return false; 70245614Sandrew } 71245614Sandrew bool AddrIsAtRight(uptr addr, uptr access_size, uptr *offset) { 72245614Sandrew if (addr + access_size >= End()) { 73245614Sandrew if (addr <= End()) 74245614Sandrew *offset = 0; 75245614Sandrew else 76245614Sandrew *offset = addr - End(); 77245614Sandrew return true; 78245614Sandrew } 79245614Sandrew return false; 80245614Sandrew } 81245614Sandrew 82245614Sandrew private: 83245614Sandrew AsanChunk *const chunk_; 84245614Sandrew}; 85245614Sandrew 86245614SandrewAsanChunkView FindHeapChunkByAddress(uptr address); 87245614Sandrew 88245614Sandrew// List of AsanChunks with total size. 89245614Sandrewclass AsanChunkFifoList: public IntrusiveList<AsanChunk> { 90245614Sandrew public: 91229109Sed explicit AsanChunkFifoList(LinkerInitialized) { } 92229109Sed AsanChunkFifoList() { clear(); } 93229109Sed void Push(AsanChunk *n); 94229109Sed void PushList(AsanChunkFifoList *q); 95229109Sed AsanChunk *Pop(); 96238901Sandrew uptr size() { return size_; } 97229109Sed void clear() { 98245614Sandrew IntrusiveList<AsanChunk>::clear(); 99229109Sed size_ = 0; 100229109Sed } 101229109Sed private: 102238901Sandrew uptr size_; 103229109Sed}; 104229109Sed 105229109Sedstruct AsanThreadLocalMallocStorage { 106229109Sed explicit AsanThreadLocalMallocStorage(LinkerInitialized x) 107245614Sandrew#if ASAN_ALLOCATOR_VERSION == 1 108245614Sandrew : quarantine_(x) 109245614Sandrew#endif 110245614Sandrew { } 111229109Sed AsanThreadLocalMallocStorage() { 112238901Sandrew CHECK(REAL(memset)); 113238901Sandrew REAL(memset)(this, 0, sizeof(AsanThreadLocalMallocStorage)); 114229109Sed } 115229109Sed 116245614Sandrew#if ASAN_ALLOCATOR_VERSION == 1 117229109Sed AsanChunkFifoList quarantine_; 118229109Sed AsanChunk *free_lists_[kNumberOfSizeClasses]; 119245614Sandrew#else 120245614Sandrew uptr quarantine_cache[16]; 121245614Sandrew uptr allocator2_cache[96 * (512 * 8 + 16)]; // Opaque. 122245614Sandrew#endif 123229109Sed void CommitBack(); 124229109Sed}; 125229109Sed 126229109Sed// Fake stack frame contains local variables of one function. 127229109Sed// This struct should fit into a stack redzone (32 bytes). 128229109Sedstruct FakeFrame { 129238901Sandrew uptr magic; // Modified by the instrumented code. 130238901Sandrew uptr descr; // Modified by the instrumented code. 131229109Sed FakeFrame *next; 132238901Sandrew u64 real_stack : 48; 133238901Sandrew u64 size_minus_one : 16; 134229109Sed}; 135229109Sed 136229109Sedstruct FakeFrameFifo { 137229109Sed public: 138229109Sed void FifoPush(FakeFrame *node); 139229109Sed FakeFrame *FifoPop(); 140229109Sed private: 141229109Sed FakeFrame *first_, *last_; 142229109Sed}; 143229109Sed 144229109Sedclass FakeFrameLifo { 145229109Sed public: 146229109Sed void LifoPush(FakeFrame *node) { 147229109Sed node->next = top_; 148229109Sed top_ = node; 149229109Sed } 150229109Sed void LifoPop() { 151229109Sed CHECK(top_); 152229109Sed top_ = top_->next; 153229109Sed } 154229109Sed FakeFrame *top() { return top_; } 155229109Sed private: 156229109Sed FakeFrame *top_; 157229109Sed}; 158229109Sed 159229109Sed// For each thread we create a fake stack and place stack objects on this fake 160229109Sed// stack instead of the real stack. The fake stack is not really a stack but 161229109Sed// a fast malloc-like allocator so that when a function exits the fake stack 162229109Sed// is not poped but remains there for quite some time until gets used again. 163229109Sed// So, we poison the objects on the fake stack when function returns. 164229109Sed// It helps us find use-after-return bugs. 165229109Sed// We can not rely on __asan_stack_free being called on every function exit, 166229109Sed// so we maintain a lifo list of all current fake frames and update it on every 167229109Sed// call to __asan_stack_malloc. 168229109Sedclass FakeStack { 169229109Sed public: 170229109Sed FakeStack(); 171229109Sed explicit FakeStack(LinkerInitialized) {} 172238901Sandrew void Init(uptr stack_size); 173229109Sed void StopUsingFakeStack() { alive_ = false; } 174229109Sed void Cleanup(); 175238901Sandrew uptr AllocateStack(uptr size, uptr real_stack); 176238901Sandrew static void OnFree(uptr ptr, uptr size, uptr real_stack); 177229109Sed // Return the bottom of the maped region. 178238901Sandrew uptr AddrIsInFakeStack(uptr addr); 179238901Sandrew bool StackSize() { return stack_size_; } 180245614Sandrew 181229109Sed private: 182238901Sandrew static const uptr kMinStackFrameSizeLog = 9; // Min frame is 512B. 183238901Sandrew static const uptr kMaxStackFrameSizeLog = 16; // Max stack frame is 64K. 184238901Sandrew static const uptr kMaxStackMallocSize = 1 << kMaxStackFrameSizeLog; 185238901Sandrew static const uptr kNumberOfSizeClasses = 186229109Sed kMaxStackFrameSizeLog - kMinStackFrameSizeLog + 1; 187229109Sed 188238901Sandrew bool AddrIsInSizeClass(uptr addr, uptr size_class); 189229109Sed 190229109Sed // Each size class should be large enough to hold all frames. 191238901Sandrew uptr ClassMmapSize(uptr size_class); 192229109Sed 193238901Sandrew uptr ClassSize(uptr size_class) { 194229109Sed return 1UL << (size_class + kMinStackFrameSizeLog); 195229109Sed } 196229109Sed 197229109Sed void DeallocateFrame(FakeFrame *fake_frame); 198229109Sed 199238901Sandrew uptr ComputeSizeClass(uptr alloc_size); 200238901Sandrew void AllocateOneSizeClass(uptr size_class); 201229109Sed 202238901Sandrew uptr stack_size_; 203229109Sed bool alive_; 204229109Sed 205238901Sandrew uptr allocated_size_classes_[kNumberOfSizeClasses]; 206229109Sed FakeFrameFifo size_classes_[kNumberOfSizeClasses]; 207229109Sed FakeFrameLifo call_stack_; 208229109Sed}; 209229109Sed 210245614Sandrewvoid *asan_memalign(uptr alignment, uptr size, StackTrace *stack, 211245614Sandrew AllocType alloc_type); 212245614Sandrewvoid asan_free(void *ptr, StackTrace *stack, AllocType alloc_type); 213229109Sed 214245614Sandrewvoid *asan_malloc(uptr size, StackTrace *stack); 215245614Sandrewvoid *asan_calloc(uptr nmemb, uptr size, StackTrace *stack); 216245614Sandrewvoid *asan_realloc(void *p, uptr size, StackTrace *stack); 217245614Sandrewvoid *asan_valloc(uptr size, StackTrace *stack); 218245614Sandrewvoid *asan_pvalloc(uptr size, StackTrace *stack); 219229109Sed 220238901Sandrewint asan_posix_memalign(void **memptr, uptr alignment, uptr size, 221245614Sandrew StackTrace *stack); 222245614Sandrewuptr asan_malloc_usable_size(void *ptr, StackTrace *stack); 223229109Sed 224238901Sandrewuptr asan_mz_size(const void *ptr); 225238901Sandrewvoid asan_mz_force_lock(); 226238901Sandrewvoid asan_mz_force_unlock(); 227229109Sed 228245614Sandrewvoid PrintInternalAllocatorStats(); 229245614Sandrew 230245614Sandrew// Log2 and RoundUpToPowerOfTwo should be inlined for performance. 231245614Sandrew#if defined(_WIN32) && !defined(__clang__) 232245614Sandrewextern "C" { 233245614Sandrewunsigned char _BitScanForward(unsigned long *index, unsigned long mask); // NOLINT 234245614Sandrewunsigned char _BitScanReverse(unsigned long *index, unsigned long mask); // NOLINT 235245614Sandrew#if defined(_WIN64) 236245614Sandrewunsigned char _BitScanForward64(unsigned long *index, unsigned __int64 mask); // NOLINT 237245614Sandrewunsigned char _BitScanReverse64(unsigned long *index, unsigned __int64 mask); // NOLINT 238245614Sandrew#endif 239245614Sandrew} 240245614Sandrew#endif 241245614Sandrew 242245614Sandrewstatic inline uptr Log2(uptr x) { 243245614Sandrew CHECK(IsPowerOfTwo(x)); 244245614Sandrew#if !defined(_WIN32) || defined(__clang__) 245245614Sandrew return __builtin_ctzl(x); 246245614Sandrew#elif defined(_WIN64) 247245614Sandrew unsigned long ret; // NOLINT 248245614Sandrew _BitScanForward64(&ret, x); 249245614Sandrew return ret; 250245614Sandrew#else 251245614Sandrew unsigned long ret; // NOLINT 252245614Sandrew _BitScanForward(&ret, x); 253245614Sandrew return ret; 254245614Sandrew#endif 255245614Sandrew} 256245614Sandrew 257245614Sandrewstatic inline uptr RoundUpToPowerOfTwo(uptr size) { 258245614Sandrew CHECK(size); 259245614Sandrew if (IsPowerOfTwo(size)) return size; 260245614Sandrew 261245614Sandrew unsigned long up; // NOLINT 262245614Sandrew#if !defined(_WIN32) || defined(__clang__) 263245614Sandrew up = SANITIZER_WORDSIZE - 1 - __builtin_clzl(size); 264245614Sandrew#elif defined(_WIN64) 265245614Sandrew _BitScanReverse64(&up, size); 266245614Sandrew#else 267245614Sandrew _BitScanReverse(&up, size); 268245614Sandrew#endif 269245614Sandrew CHECK(size < (1ULL << (up + 1))); 270245614Sandrew CHECK(size > (1ULL << up)); 271245614Sandrew return 1UL << (up + 1); 272245614Sandrew} 273245614Sandrew 274245614Sandrew 275229109Sed} // namespace __asan 276229109Sed#endif // ASAN_ALLOCATOR_H 277