asan_allocator.h revision 245614
15455Sdg//===-- asan_allocator.h ----------------------------------------*- C++ -*-===// 21541Srgrimes// 31541Srgrimes// The LLVM Compiler Infrastructure 41549Srgrimes// 51549Srgrimes// This file is distributed under the University of Illinois Open Source 61549Srgrimes// License. See LICENSE.TXT for details. 71549Srgrimes// 81541Srgrimes//===----------------------------------------------------------------------===// 91549Srgrimes// 101541Srgrimes// This file is a part of AddressSanitizer, an address sanity checker. 111541Srgrimes// 121541Srgrimes// ASan-private header for asan_allocator.cc. 131541Srgrimes//===----------------------------------------------------------------------===// 141541Srgrimes 151541Srgrimes#ifndef ASAN_ALLOCATOR_H 161541Srgrimes#define ASAN_ALLOCATOR_H 171541Srgrimes 181541Srgrimes#include "asan_internal.h" 191541Srgrimes#include "asan_interceptors.h" 201541Srgrimes#include "sanitizer_common/sanitizer_list.h" 211541Srgrimes 221541Srgrimes// We are in the process of transitioning from the old allocator (version 1) 231541Srgrimes// to a new one (version 2). The change is quite intrusive so both allocators 241541Srgrimes// will co-exist in the source base for a while. The actual allocator is chosen 251541Srgrimes// at build time by redefining this macro. 261541Srgrimes#ifndef ASAN_ALLOCATOR_VERSION 271541Srgrimes# if ASAN_LINUX && !ASAN_ANDROID 281541Srgrimes# define ASAN_ALLOCATOR_VERSION 2 291541Srgrimes# else 301541Srgrimes# define ASAN_ALLOCATOR_VERSION 1 311541Srgrimes# endif 321541Srgrimes#endif // ASAN_ALLOCATOR_VERSION 331541Srgrimes 341541Srgrimesnamespace __asan { 351541Srgrimes 361541Srgrimesenum AllocType { 371541Srgrimes FROM_MALLOC = 1, // Memory block came from malloc, calloc, realloc, etc. 381541Srgrimes FROM_NEW = 2, // Memory block came from operator new. 391541Srgrimes FROM_NEW_BR = 3 // Memory block came from operator new [ ] 401541Srgrimes}; 411817Sdg 421541Srgrimesstatic const uptr kNumberOfSizeClasses = 255; 431541Srgrimesstruct AsanChunk; 441541Srgrimes 451541Srgrimesclass AsanChunkView { 461541Srgrimes public: 471541Srgrimes explicit AsanChunkView(AsanChunk *chunk) : chunk_(chunk) {} 485455Sdg bool IsValid() { return chunk_ != 0; } 491541Srgrimes uptr Beg(); // first byte of user memory. 501541Srgrimes uptr End(); // last byte of user memory. 511541Srgrimes uptr UsedSize(); // size requested by the user. 521541Srgrimes uptr AllocTid(); 531541Srgrimes uptr FreeTid(); 545455Sdg void GetAllocStack(StackTrace *stack); 555455Sdg void GetFreeStack(StackTrace *stack); 565455Sdg bool AddrIsInside(uptr addr, uptr access_size, uptr *offset) { 571541Srgrimes if (addr >= Beg() && (addr + access_size) <= End()) { 585455Sdg *offset = addr - Beg(); 591541Srgrimes return true; 601541Srgrimes } 611541Srgrimes return false; 621541Srgrimes } 631541Srgrimes bool AddrIsAtLeft(uptr addr, uptr access_size, uptr *offset) { 641541Srgrimes (void)access_size; 651541Srgrimes if (addr < Beg()) { 661541Srgrimes *offset = Beg() - addr; 671541Srgrimes return true; 681817Sdg } 6942957Sdillon return false; 701541Srgrimes } 711541Srgrimes bool AddrIsAtRight(uptr addr, uptr access_size, uptr *offset) { 721541Srgrimes if (addr + access_size >= End()) { 731541Srgrimes if (addr <= End()) 741541Srgrimes *offset = 0; 751541Srgrimes else 761541Srgrimes *offset = addr - End(); 771541Srgrimes return true; 781549Srgrimes } 799507Sdg return false; 801549Srgrimes } 8112662Sdg 821541Srgrimes private: 831541Srgrimes AsanChunk *const chunk_; 8412662Sdg}; 8512662Sdg 8622521SdysonAsanChunkView FindHeapChunkByAddress(uptr address); 8712662Sdg 8812662Sdg// List of AsanChunks with total size. 8912662Sdgclass AsanChunkFifoList: public IntrusiveList<AsanChunk> { 901541Srgrimes public: 911541Srgrimes explicit AsanChunkFifoList(LinkerInitialized) { } 924207Sdg AsanChunkFifoList() { clear(); } 939507Sdg void Push(AsanChunk *n); 949507Sdg void PushList(AsanChunkFifoList *q); 9512662Sdg AsanChunk *Pop(); 961541Srgrimes uptr size() { return size_; } 9733181Seivind void clear() { 9833181Seivind IntrusiveList<AsanChunk>::clear(); 991549Srgrimes size_ = 0; 10032585Sdyson } 10132585Sdyson private: 1021549Srgrimes uptr size_; 1031549Srgrimes}; 10434202Sdyson 10534202Sdysonstruct AsanThreadLocalMallocStorage { 10634202Sdyson explicit AsanThreadLocalMallocStorage(LinkerInitialized x) 10734202Sdyson#if ASAN_ALLOCATOR_VERSION == 1 10834202Sdyson : quarantine_(x) 10934202Sdyson#endif 11034202Sdyson { } 11134202Sdyson AsanThreadLocalMallocStorage() { 11234202Sdyson CHECK(REAL(memset)); 11334202Sdyson REAL(memset)(this, 0, sizeof(AsanThreadLocalMallocStorage)); 11434202Sdyson } 11534202Sdyson 11634202Sdyson#if ASAN_ALLOCATOR_VERSION == 1 11742957Sdillon AsanChunkFifoList quarantine_; 11834202Sdyson AsanChunk *free_lists_[kNumberOfSizeClasses]; 11934202Sdyson#else 12038799Sdfr uptr quarantine_cache[16]; 12134202Sdyson uptr allocator2_cache[96 * (512 * 8 + 16)]; // Opaque. 12234202Sdyson#endif 12334202Sdyson void CommitBack(); 12434202Sdyson}; 12542957Sdillon 12634202Sdyson// Fake stack frame contains local variables of one function. 12734202Sdyson// This struct should fit into a stack redzone (32 bytes). 12834202Sdysonstruct FakeFrame { 12934202Sdyson uptr magic; // Modified by the instrumented code. 13034202Sdyson uptr descr; // Modified by the instrumented code. 13134202Sdyson FakeFrame *next; 13234202Sdyson u64 real_stack : 48; 13334202Sdyson u64 size_minus_one : 16; 13434202Sdyson}; 13534202Sdyson 13634202Sdysonstruct FakeFrameFifo { 13734202Sdyson public: 13834202Sdyson void FifoPush(FakeFrame *node); 13934202Sdyson FakeFrame *FifoPop(); 14034202Sdyson private: 14134202Sdyson FakeFrame *first_, *last_; 14234202Sdyson}; 14334202Sdyson 14434202Sdysonclass FakeFrameLifo { 14534202Sdyson public: 14634202Sdyson void LifoPush(FakeFrame *node) { 14734202Sdyson node->next = top_; 14834202Sdyson top_ = node; 14934202Sdyson } 15034202Sdyson void LifoPop() { 15134202Sdyson CHECK(top_); 15234202Sdyson top_ = top_->next; 15334202Sdyson } 15434202Sdyson FakeFrame *top() { return top_; } 15534202Sdyson private: 1561541Srgrimes FakeFrame *top_; 1571541Srgrimes}; 1581541Srgrimes 1591541Srgrimes// For each thread we create a fake stack and place stack objects on this fake 1601541Srgrimes// stack instead of the real stack. The fake stack is not really a stack but 1611541Srgrimes// a fast malloc-like allocator so that when a function exits the fake stack 1621541Srgrimes// is not poped but remains there for quite some time until gets used again. 1631541Srgrimes// So, we poison the objects on the fake stack when function returns. 1641541Srgrimes// It helps us find use-after-return bugs. 1651541Srgrimes// We can not rely on __asan_stack_free being called on every function exit, 1661541Srgrimes// so we maintain a lifo list of all current fake frames and update it on every 1671541Srgrimes// call to __asan_stack_malloc. 1681541Srgrimesclass FakeStack { 1691541Srgrimes public: 1701541Srgrimes FakeStack(); 1711541Srgrimes explicit FakeStack(LinkerInitialized) {} 1721541Srgrimes void Init(uptr stack_size); 1731541Srgrimes void StopUsingFakeStack() { alive_ = false; } 1741541Srgrimes void Cleanup(); 17528751Sbde uptr AllocateStack(uptr size, uptr real_stack); 1761541Srgrimes static void OnFree(uptr ptr, uptr size, uptr real_stack); 1775455Sdg // Return the bottom of the maped region. 1785455Sdg uptr AddrIsInFakeStack(uptr addr); 1795455Sdg bool StackSize() { return stack_size_; } 18032702Sdyson 1815455Sdg private: 1825455Sdg static const uptr kMinStackFrameSizeLog = 9; // Min frame is 512B. 1835455Sdg static const uptr kMaxStackFrameSizeLog = 16; // Max stack frame is 64K. 18434202Sdyson static const uptr kMaxStackMallocSize = 1 << kMaxStackFrameSizeLog; 18532702Sdyson static const uptr kNumberOfSizeClasses = 18634202Sdyson kMaxStackFrameSizeLog - kMinStackFrameSizeLog + 1; 1871541Srgrimes 1885455Sdg bool AddrIsInSizeClass(uptr addr, uptr size_class); 18934202Sdyson 1901541Srgrimes // Each size class should be large enough to hold all frames. 1915455Sdg uptr ClassMmapSize(uptr size_class); 19234202Sdyson 1931541Srgrimes uptr ClassSize(uptr size_class) { 1941541Srgrimes return 1UL << (size_class + kMinStackFrameSizeLog); 1955455Sdg } 1965455Sdg 1971541Srgrimes void DeallocateFrame(FakeFrame *fake_frame); 19834202Sdyson 19934202Sdyson uptr ComputeSizeClass(uptr alloc_size); 20034202Sdyson void AllocateOneSizeClass(uptr size_class); 20132585Sdyson 20232585Sdyson uptr stack_size_; 20332585Sdyson bool alive_; 20432585Sdyson 20532585Sdyson uptr allocated_size_classes_[kNumberOfSizeClasses]; 20632585Sdyson FakeFrameFifo size_classes_[kNumberOfSizeClasses]; 20732585Sdyson FakeFrameLifo call_stack_; 20832585Sdyson}; 20932585Sdyson 21032585Sdysonvoid *asan_memalign(uptr alignment, uptr size, StackTrace *stack, 21132585Sdyson AllocType alloc_type); 21232585Sdysonvoid asan_free(void *ptr, StackTrace *stack, AllocType alloc_type); 21334202Sdyson 21432585Sdysonvoid *asan_malloc(uptr size, StackTrace *stack); 21534202Sdysonvoid *asan_calloc(uptr nmemb, uptr size, StackTrace *stack); 21632585Sdysonvoid *asan_realloc(void *p, uptr size, StackTrace *stack); 21732585Sdysonvoid *asan_valloc(uptr size, StackTrace *stack); 21832585Sdysonvoid *asan_pvalloc(uptr size, StackTrace *stack); 21932585Sdyson 22032585Sdysonint asan_posix_memalign(void **memptr, uptr alignment, uptr size, 22132585Sdyson StackTrace *stack); 22232585Sdysonuptr asan_malloc_usable_size(void *ptr, StackTrace *stack); 22332585Sdyson 22432585Sdysonuptr asan_mz_size(const void *ptr); 22534202Sdysonvoid asan_mz_force_lock(); 22634202Sdysonvoid asan_mz_force_unlock(); 2271541Srgrimes 2287695Sdgvoid PrintInternalAllocatorStats(); 22934202Sdyson 23032702Sdyson// Log2 and RoundUpToPowerOfTwo should be inlined for performance. 23134202Sdyson#if defined(_WIN32) && !defined(__clang__) 23220054Sdysonextern "C" { 23337563Sbdeunsigned char _BitScanForward(unsigned long *index, unsigned long mask); // NOLINT 23420054Sdysonunsigned char _BitScanReverse(unsigned long *index, unsigned long mask); // NOLINT 23520054Sdyson#if defined(_WIN64) 23620449Sdysonunsigned char _BitScanForward64(unsigned long *index, unsigned __int64 mask); // NOLINT 23732286Sdysonunsigned char _BitScanReverse64(unsigned long *index, unsigned __int64 mask); // NOLINT 23832286Sdyson#endif 23932286Sdyson} 24032286Sdyson#endif 24132286Sdyson 24234202Sdysonstatic inline uptr Log2(uptr x) { 24338135Sdfr CHECK(IsPowerOfTwo(x)); 24432286Sdyson#if !defined(_WIN32) || defined(__clang__) 24534202Sdyson return __builtin_ctzl(x); 24631853Sdyson#elif defined(_WIN64) 24734202Sdyson unsigned long ret; // NOLINT 24834202Sdyson _BitScanForward64(&ret, x); 24934202Sdyson return ret; 25031853Sdyson#else 2517695Sdg unsigned long ret; // NOLINT 25234202Sdyson _BitScanForward(&ret, x); 2531541Srgrimes return ret; 2541541Srgrimes#endif 2551541Srgrimes} 2561541Srgrimes 25734202Sdysonstatic inline uptr RoundUpToPowerOfTwo(uptr size) { 2581541Srgrimes CHECK(size); 2595455Sdg if (IsPowerOfTwo(size)) return size; 2605455Sdg 2611541Srgrimes unsigned long up; // NOLINT 2621541Srgrimes#if !defined(_WIN32) || defined(__clang__) 26334202Sdyson up = SANITIZER_WORDSIZE - 1 - __builtin_clzl(size); 26434202Sdyson#elif defined(_WIN64) 2651541Srgrimes _BitScanReverse64(&up, size); 2661541Srgrimes#else 26742957Sdillon _BitScanReverse(&up, size); 26842957Sdillon#endif 26942957Sdillon CHECK(size < (1ULL << (up + 1))); 27032585Sdyson CHECK(size > (1ULL << up)); 27134202Sdyson return 1UL << (up + 1); 27234202Sdyson} 27332585Sdyson 27432585Sdyson 27542957Sdillon} // namespace __asan 27642957Sdillon#endif // ASAN_ALLOCATOR_H 27742957Sdillon