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