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