asan_allocator.h revision 2679f1904dc5d5eb2ce82014116764c5f5131a2b 
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
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
27namespace __asan {
28
29static const uptr kNumberOfSizeClasses = 255;
30struct AsanChunk;
31
32class 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);
43  bool AddrIsInside(uptr addr, uptr access_size, uptr *offset);
44  bool AddrIsAtLeft(uptr addr, uptr access_size, uptr *offset);
45  bool AddrIsAtRight(uptr addr, uptr access_size, uptr *offset);
46 private:
47  AsanChunk *const chunk_;
48};
49
50AsanChunkView FindHeapChunkByAddress(uptr address);
51
52class AsanChunkFifoList {
53 public:
54  explicit AsanChunkFifoList(LinkerInitialized) { }
55  AsanChunkFifoList() { clear(); }
56  void Push(AsanChunk *n);
57  void PushList(AsanChunkFifoList *q);
58  AsanChunk *Pop();
59  uptr size() { return size_; }
60  void clear() {
61    first_ = last_ = 0;
62    size_ = 0;
63  }
64 private:
65  AsanChunk *first_;
66  AsanChunk *last_;
67  uptr size_;
68};
69
70struct AsanThreadLocalMallocStorage {
71  explicit AsanThreadLocalMallocStorage(LinkerInitialized x)
72      : quarantine_(x) { }
73  AsanThreadLocalMallocStorage() {
74    CHECK(REAL(memset));
75    REAL(memset)(this, 0, sizeof(AsanThreadLocalMallocStorage));
76  }
77
78  AsanChunkFifoList quarantine_;
79  AsanChunk *free_lists_[kNumberOfSizeClasses];
80  void CommitBack();
81};
82
83// Fake stack frame contains local variables of one function.
84// This struct should fit into a stack redzone (32 bytes).
85struct FakeFrame {
86  uptr magic;  // Modified by the instrumented code.
87  uptr descr;  // Modified by the instrumented code.
88  FakeFrame *next;
89  u64 real_stack     : 48;
90  u64 size_minus_one : 16;
91};
92
93struct FakeFrameFifo {
94 public:
95  void FifoPush(FakeFrame *node);
96  FakeFrame *FifoPop();
97 private:
98  FakeFrame *first_, *last_;
99};
100
101class FakeFrameLifo {
102 public:
103  void LifoPush(FakeFrame *node) {
104    node->next = top_;
105    top_ = node;
106  }
107  void LifoPop() {
108    CHECK(top_);
109    top_ = top_->next;
110  }
111  FakeFrame *top() { return top_; }
112 private:
113  FakeFrame *top_;
114};
115
116// For each thread we create a fake stack and place stack objects on this fake
117// stack instead of the real stack. The fake stack is not really a stack but
118// a fast malloc-like allocator so that when a function exits the fake stack
119// is not poped but remains there for quite some time until gets used again.
120// So, we poison the objects on the fake stack when function returns.
121// It helps us find use-after-return bugs.
122// We can not rely on __asan_stack_free being called on every function exit,
123// so we maintain a lifo list of all current fake frames and update it on every
124// call to __asan_stack_malloc.
125class FakeStack {
126 public:
127  FakeStack();
128  explicit FakeStack(LinkerInitialized) {}
129  void Init(uptr stack_size);
130  void StopUsingFakeStack() { alive_ = false; }
131  void Cleanup();
132  uptr AllocateStack(uptr size, uptr real_stack);
133  static void OnFree(uptr ptr, uptr size, uptr real_stack);
134  // Return the bottom of the maped region.
135  uptr AddrIsInFakeStack(uptr addr);
136  bool StackSize() { return stack_size_; }
137
138 private:
139  static const uptr kMinStackFrameSizeLog = 9;  // Min frame is 512B.
140  static const uptr kMaxStackFrameSizeLog = 16;  // Max stack frame is 64K.
141  static const uptr kMaxStackMallocSize = 1 << kMaxStackFrameSizeLog;
142  static const uptr kNumberOfSizeClasses =
143      kMaxStackFrameSizeLog - kMinStackFrameSizeLog + 1;
144
145  bool AddrIsInSizeClass(uptr addr, uptr size_class);
146
147  // Each size class should be large enough to hold all frames.
148  uptr ClassMmapSize(uptr size_class);
149
150  uptr ClassSize(uptr size_class) {
151    return 1UL << (size_class + kMinStackFrameSizeLog);
152  }
153
154  void DeallocateFrame(FakeFrame *fake_frame);
155
156  uptr ComputeSizeClass(uptr alloc_size);
157  void AllocateOneSizeClass(uptr size_class);
158
159  uptr stack_size_;
160  bool   alive_;
161
162  uptr allocated_size_classes_[kNumberOfSizeClasses];
163  FakeFrameFifo size_classes_[kNumberOfSizeClasses];
164  FakeFrameLifo call_stack_;
165};
166
167void *asan_memalign(uptr alignment, uptr size, StackTrace *stack);
168void asan_free(void *ptr, StackTrace *stack);
169
170void *asan_malloc(uptr size, StackTrace *stack);
171void *asan_calloc(uptr nmemb, uptr size, StackTrace *stack);
172void *asan_realloc(void *p, uptr size, StackTrace *stack);
173void *asan_valloc(uptr size, StackTrace *stack);
174void *asan_pvalloc(uptr size, StackTrace *stack);
175
176int asan_posix_memalign(void **memptr, uptr alignment, uptr size,
177                          StackTrace *stack);
178uptr asan_malloc_usable_size(void *ptr, StackTrace *stack);
179
180uptr asan_mz_size(const void *ptr);
181void asan_mz_force_lock();
182void asan_mz_force_unlock();
183
184// Log2 and RoundUpToPowerOfTwo should be inlined for performance.
185
186static inline uptr Log2(uptr x) {
187  CHECK(IsPowerOfTwo(x));
188#if !defined(_WIN32) || defined(__clang__)
189  return __builtin_ctzl(x);
190#elif defined(_WIN64)
191  unsigned long ret;  // NOLINT
192  _BitScanForward64(&ret, x);
193  return ret;
194#else
195  unsigned long ret;  // NOLINT
196  _BitScanForward(&ret, x);
197  return ret;
198#endif
199}
200
201static inline uptr RoundUpToPowerOfTwo(uptr size) {
202  CHECK(size);
203  if (IsPowerOfTwo(size)) return size;
204
205  unsigned long up;  // NOLINT
206#if !defined(_WIN32) || defined(__clang__)
207  up = SANITIZER_WORDSIZE - 1 - __builtin_clzl(size);
208#elif defined(_WIN64)
209  _BitScanReverse64(&up, size);
210#else
211  _BitScanReverse(&up, size);
212#endif
213  CHECK(size < (1ULL << (up + 1)));
214  CHECK(size > (1ULL << up));
215  return 1UL << (up + 1);
216}
217
218
219}  // namespace __asan
220#endif  // ASAN_ALLOCATOR_H
221