1//===-- asan_allocator.cc -------------------------------------------------===//
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// Implementation of ASan's memory allocator.
13// Evey piece of memory (AsanChunk) allocated by the allocator
14// has a left redzone of REDZONE bytes and
15// a right redzone such that the end of the chunk is aligned by REDZONE
16// (i.e. the right redzone is between 0 and REDZONE-1).
17// The left redzone is always poisoned.
18// The right redzone is poisoned on malloc, the body is poisoned on free.
19// Once freed, a chunk is moved to a quarantine (fifo list).
20// After quarantine, a chunk is returned to freelists.
21//
22// The left redzone contains ASan's internal data and the stack trace of
23// the malloc call.
24// Once freed, the body of the chunk contains the stack trace of the free call.
25//
26//===----------------------------------------------------------------------===//
27
28#include "asan_allocator.h"
29#include "asan_interceptors.h"
30#include "asan_internal.h"
31#include "asan_lock.h"
32#include "asan_mapping.h"
33#include "asan_stats.h"
34#include "asan_report.h"
35#include "asan_thread.h"
36#include "asan_thread_registry.h"
37#include "sanitizer/asan_interface.h"
38#include "sanitizer_common/sanitizer_atomic.h"
39
40#if defined(_WIN32) && !defined(__clang__)
41#include <intrin.h>
42#endif
43
44namespace __asan {
45
46#define REDZONE ((uptr)(flags()->redzone))
47static const uptr kMinAllocSize = REDZONE * 2;
48static const u64 kMaxAvailableRam = 128ULL << 30;  // 128G
49static const uptr kMaxThreadLocalQuarantine = 1 << 20;  // 1M
50
51static const uptr kMinMmapSize = (ASAN_LOW_MEMORY) ? 4UL << 17 : 4UL << 20;
52static const uptr kMaxSizeForThreadLocalFreeList =
53    (ASAN_LOW_MEMORY) ? 1 << 15 : 1 << 17;
54
55// Size classes less than kMallocSizeClassStep are powers of two.
56// All other size classes are multiples of kMallocSizeClassStep.
57static const uptr kMallocSizeClassStepLog = 26;
58static const uptr kMallocSizeClassStep = 1UL << kMallocSizeClassStepLog;
59
60static const uptr kMaxAllowedMallocSize =
61    (__WORDSIZE == 32) ? 3UL << 30 : 8UL << 30;
62
63static inline bool IsAligned(uptr a, uptr alignment) {
64  return (a & (alignment - 1)) == 0;
65}
66
67static inline uptr Log2(uptr x) {
68  CHECK(IsPowerOfTwo(x));
69#if !defined(_WIN32) || defined(__clang__)
70  return __builtin_ctzl(x);
71#elif defined(_WIN64)
72  unsigned long ret;  // NOLINT
73  _BitScanForward64(&ret, x);
74  return ret;
75#else
76  unsigned long ret;  // NOLINT
77  _BitScanForward(&ret, x);
78  return ret;
79#endif
80}
81
82static inline uptr RoundUpToPowerOfTwo(uptr size) {
83  CHECK(size);
84  if (IsPowerOfTwo(size)) return size;
85
86  unsigned long up;  // NOLINT
87#if !defined(_WIN32) || defined(__clang__)
88  up = __WORDSIZE - 1 - __builtin_clzl(size);
89#elif defined(_WIN64)
90  _BitScanReverse64(&up, size);
91#else
92  _BitScanReverse(&up, size);
93#endif
94  CHECK(size < (1ULL << (up + 1)));
95  CHECK(size > (1ULL << up));
96  return 1UL << (up + 1);
97}
98
99static inline uptr SizeClassToSize(u8 size_class) {
100  CHECK(size_class < kNumberOfSizeClasses);
101  if (size_class <= kMallocSizeClassStepLog) {
102    return 1UL << size_class;
103  } else {
104    return (size_class - kMallocSizeClassStepLog) * kMallocSizeClassStep;
105  }
106}
107
108static inline u8 SizeToSizeClass(uptr size) {
109  u8 res = 0;
110  if (size <= kMallocSizeClassStep) {
111    uptr rounded = RoundUpToPowerOfTwo(size);
112    res = Log2(rounded);
113  } else {
114    res = ((size + kMallocSizeClassStep - 1) / kMallocSizeClassStep)
115        + kMallocSizeClassStepLog;
116  }
117  CHECK(res < kNumberOfSizeClasses);
118  CHECK(size <= SizeClassToSize(res));
119  return res;
120}
121
122// Given REDZONE bytes, we need to mark first size bytes
123// as addressable and the rest REDZONE-size bytes as unaddressable.
124static void PoisonHeapPartialRightRedzone(uptr mem, uptr size) {
125  CHECK(size <= REDZONE);
126  CHECK(IsAligned(mem, REDZONE));
127  CHECK(IsPowerOfTwo(SHADOW_GRANULARITY));
128  CHECK(IsPowerOfTwo(REDZONE));
129  CHECK(REDZONE >= SHADOW_GRANULARITY);
130  PoisonShadowPartialRightRedzone(mem, size, REDZONE,
131                                  kAsanHeapRightRedzoneMagic);
132}
133
134static u8 *MmapNewPagesAndPoisonShadow(uptr size) {
135  CHECK(IsAligned(size, kPageSize));
136  u8 *res = (u8*)MmapOrDie(size, __FUNCTION__);
137  PoisonShadow((uptr)res, size, kAsanHeapLeftRedzoneMagic);
138  if (flags()->debug) {
139    Printf("ASAN_MMAP: [%p, %p)\n", res, res + size);
140  }
141  return res;
142}
143
144// Every chunk of memory allocated by this allocator can be in one of 3 states:
145// CHUNK_AVAILABLE: the chunk is in the free list and ready to be allocated.
146// CHUNK_ALLOCATED: the chunk is allocated and not yet freed.
147// CHUNK_QUARANTINE: the chunk was freed and put into quarantine zone.
148//
149// The pseudo state CHUNK_MEMALIGN is used to mark that the address is not
150// the beginning of a AsanChunk (in which the actual chunk resides at
151// this - this->used_size).
152//
153// The magic numbers for the enum values are taken randomly.
154enum {
155  CHUNK_AVAILABLE  = 0x57,
156  CHUNK_ALLOCATED  = 0x32,
157  CHUNK_QUARANTINE = 0x19,
158  CHUNK_MEMALIGN   = 0xDC
159};
160
161struct ChunkBase {
162  // First 8 bytes.
163  uptr  chunk_state : 8;
164  uptr  alloc_tid   : 24;
165  uptr  size_class  : 8;
166  uptr  free_tid    : 24;
167
168  // Second 8 bytes.
169  uptr alignment_log : 8;
170  uptr used_size : FIRST_32_SECOND_64(32, 56);  // Size requested by the user.
171
172  // This field may overlap with the user area and thus should not
173  // be used while the chunk is in CHUNK_ALLOCATED state.
174  AsanChunk *next;
175
176  // Typically the beginning of the user-accessible memory is 'this'+REDZONE
177  // and is also aligned by REDZONE. However, if the memory is allocated
178  // by memalign, the alignment might be higher and the user-accessible memory
179  // starts at the first properly aligned address after 'this'.
180  uptr Beg() { return RoundUpTo((uptr)this + 1, 1 << alignment_log); }
181  uptr Size() { return SizeClassToSize(size_class); }
182  u8 SizeClass() { return size_class; }
183};
184
185struct AsanChunk: public ChunkBase {
186  u32 *compressed_alloc_stack() {
187    return (u32*)((uptr)this + sizeof(ChunkBase));
188  }
189  u32 *compressed_free_stack() {
190    return (u32*)((uptr)this + Max((uptr)REDZONE, (uptr)sizeof(ChunkBase)));
191  }
192
193  // The left redzone after the ChunkBase is given to the alloc stack trace.
194  uptr compressed_alloc_stack_size() {
195    if (REDZONE < sizeof(ChunkBase)) return 0;
196    return (REDZONE - sizeof(ChunkBase)) / sizeof(u32);
197  }
198  uptr compressed_free_stack_size() {
199    if (REDZONE < sizeof(ChunkBase)) return 0;
200    return (REDZONE) / sizeof(u32);
201  }
202
203  bool AddrIsInside(uptr addr, uptr access_size, uptr *offset) {
204    if (addr >= Beg() && (addr + access_size) <= (Beg() + used_size)) {
205      *offset = addr - Beg();
206      return true;
207    }
208    return false;
209  }
210
211  bool AddrIsAtLeft(uptr addr, uptr access_size, uptr *offset) {
212    if (addr < Beg()) {
213      *offset = Beg() - addr;
214      return true;
215    }
216    return false;
217  }
218
219  bool AddrIsAtRight(uptr addr, uptr access_size, uptr *offset) {
220    if (addr + access_size >= Beg() + used_size) {
221      if (addr <= Beg() + used_size)
222        *offset = 0;
223      else
224        *offset = addr - (Beg() + used_size);
225      return true;
226    }
227    return false;
228  }
229
230  void DescribeAddress(uptr addr, uptr access_size) {
231    uptr offset;
232    Printf("%p is located ", (void*)addr);
233    if (AddrIsInside(addr, access_size, &offset)) {
234      Printf("%zu bytes inside of", offset);
235    } else if (AddrIsAtLeft(addr, access_size, &offset)) {
236      Printf("%zu bytes to the left of", offset);
237    } else if (AddrIsAtRight(addr, access_size, &offset)) {
238      Printf("%zu bytes to the right of", offset);
239    } else {
240      Printf(" somewhere around (this is AddressSanitizer bug!)");
241    }
242    Printf(" %zu-byte region [%p,%p)\n",
243               used_size, (void*)Beg(), (void*)(Beg() + used_size));
244  }
245};
246
247static AsanChunk *PtrToChunk(uptr ptr) {
248  AsanChunk *m = (AsanChunk*)(ptr - REDZONE);
249  if (m->chunk_state == CHUNK_MEMALIGN) {
250    m = (AsanChunk*)((uptr)m - m->used_size);
251  }
252  return m;
253}
254
255
256void AsanChunkFifoList::PushList(AsanChunkFifoList *q) {
257  CHECK(q->size() > 0);
258  if (last_) {
259    CHECK(first_);
260    CHECK(!last_->next);
261    last_->next = q->first_;
262    last_ = q->last_;
263  } else {
264    CHECK(!first_);
265    last_ = q->last_;
266    first_ = q->first_;
267    CHECK(first_);
268  }
269  CHECK(last_);
270  CHECK(!last_->next);
271  size_ += q->size();
272  q->clear();
273}
274
275void AsanChunkFifoList::Push(AsanChunk *n) {
276  CHECK(n->next == 0);
277  if (last_) {
278    CHECK(first_);
279    CHECK(!last_->next);
280    last_->next = n;
281    last_ = n;
282  } else {
283    CHECK(!first_);
284    last_ = first_ = n;
285  }
286  size_ += n->Size();
287}
288
289// Interesting performance observation: this function takes up to 15% of overal
290// allocator time. That's because *first_ has been evicted from cache long time
291// ago. Not sure if we can or want to do anything with this.
292AsanChunk *AsanChunkFifoList::Pop() {
293  CHECK(first_);
294  AsanChunk *res = first_;
295  first_ = first_->next;
296  if (first_ == 0)
297    last_ = 0;
298  CHECK(size_ >= res->Size());
299  size_ -= res->Size();
300  if (last_) {
301    CHECK(!last_->next);
302  }
303  return res;
304}
305
306// All pages we ever allocated.
307struct PageGroup {
308  uptr beg;
309  uptr end;
310  uptr size_of_chunk;
311  uptr last_chunk;
312  bool InRange(uptr addr) {
313    return addr >= beg && addr < end;
314  }
315};
316
317class MallocInfo {
318 public:
319  explicit MallocInfo(LinkerInitialized x) : mu_(x) { }
320
321  AsanChunk *AllocateChunks(u8 size_class, uptr n_chunks) {
322    AsanChunk *m = 0;
323    AsanChunk **fl = &free_lists_[size_class];
324    {
325      ScopedLock lock(&mu_);
326      for (uptr i = 0; i < n_chunks; i++) {
327        if (!(*fl)) {
328          *fl = GetNewChunks(size_class);
329        }
330        AsanChunk *t = *fl;
331        *fl = t->next;
332        t->next = m;
333        CHECK(t->chunk_state == CHUNK_AVAILABLE);
334        m = t;
335      }
336    }
337    return m;
338  }
339
340  void SwallowThreadLocalMallocStorage(AsanThreadLocalMallocStorage *x,
341                                       bool eat_free_lists) {
342    CHECK(flags()->quarantine_size > 0);
343    ScopedLock lock(&mu_);
344    AsanChunkFifoList *q = &x->quarantine_;
345    if (q->size() > 0) {
346      quarantine_.PushList(q);
347      while (quarantine_.size() > (uptr)flags()->quarantine_size) {
348        QuarantinePop();
349      }
350    }
351    if (eat_free_lists) {
352      for (uptr size_class = 0; size_class < kNumberOfSizeClasses;
353           size_class++) {
354        AsanChunk *m = x->free_lists_[size_class];
355        while (m) {
356          AsanChunk *t = m->next;
357          m->next = free_lists_[size_class];
358          free_lists_[size_class] = m;
359          m = t;
360        }
361        x->free_lists_[size_class] = 0;
362      }
363    }
364  }
365
366  void BypassThreadLocalQuarantine(AsanChunk *chunk) {
367    ScopedLock lock(&mu_);
368    quarantine_.Push(chunk);
369  }
370
371  AsanChunk *FindMallocedOrFreed(uptr addr, uptr access_size) {
372    ScopedLock lock(&mu_);
373    return FindChunkByAddr(addr);
374  }
375
376  uptr AllocationSize(uptr ptr) {
377    if (!ptr) return 0;
378    ScopedLock lock(&mu_);
379
380    // Make sure this is our chunk and |ptr| actually points to the beginning
381    // of the allocated memory.
382    AsanChunk *m = FindChunkByAddr(ptr);
383    if (!m || m->Beg() != ptr) return 0;
384
385    if (m->chunk_state == CHUNK_ALLOCATED) {
386      return m->used_size;
387    } else {
388      return 0;
389    }
390  }
391
392  void ForceLock() {
393    mu_.Lock();
394  }
395
396  void ForceUnlock() {
397    mu_.Unlock();
398  }
399
400  void PrintStatus() {
401    ScopedLock lock(&mu_);
402    uptr malloced = 0;
403
404    Printf(" MallocInfo: in quarantine: %zu malloced: %zu; ",
405           quarantine_.size() >> 20, malloced >> 20);
406    for (uptr j = 1; j < kNumberOfSizeClasses; j++) {
407      AsanChunk *i = free_lists_[j];
408      if (!i) continue;
409      uptr t = 0;
410      for (; i; i = i->next) {
411        t += i->Size();
412      }
413      Printf("%zu:%zu ", j, t >> 20);
414    }
415    Printf("\n");
416  }
417
418  PageGroup *FindPageGroup(uptr addr) {
419    ScopedLock lock(&mu_);
420    return FindPageGroupUnlocked(addr);
421  }
422
423 private:
424  PageGroup *FindPageGroupUnlocked(uptr addr) {
425    int n = atomic_load(&n_page_groups_, memory_order_relaxed);
426    // If the page groups are not sorted yet, sort them.
427    if (n_sorted_page_groups_ < n) {
428      SortArray((uptr*)page_groups_, n);
429      n_sorted_page_groups_ = n;
430    }
431    // Binary search over the page groups.
432    int beg = 0, end = n;
433    while (beg < end) {
434      int med = (beg + end) / 2;
435      uptr g = (uptr)page_groups_[med];
436      if (addr > g) {
437        // 'g' points to the end of the group, so 'addr'
438        // may not belong to page_groups_[med] or any previous group.
439        beg = med + 1;
440      } else {
441        // 'addr' may belong to page_groups_[med] or a previous group.
442        end = med;
443      }
444    }
445    if (beg >= n)
446      return 0;
447    PageGroup *g = page_groups_[beg];
448    CHECK(g);
449    if (g->InRange(addr))
450      return g;
451    return 0;
452  }
453
454  // We have an address between two chunks, and we want to report just one.
455  AsanChunk *ChooseChunk(uptr addr,
456                         AsanChunk *left_chunk, AsanChunk *right_chunk) {
457    // Prefer an allocated chunk or a chunk from quarantine.
458    if (left_chunk->chunk_state == CHUNK_AVAILABLE &&
459        right_chunk->chunk_state != CHUNK_AVAILABLE)
460      return right_chunk;
461    if (right_chunk->chunk_state == CHUNK_AVAILABLE &&
462        left_chunk->chunk_state != CHUNK_AVAILABLE)
463      return left_chunk;
464    // Choose based on offset.
465    uptr l_offset = 0, r_offset = 0;
466    CHECK(left_chunk->AddrIsAtRight(addr, 1, &l_offset));
467    CHECK(right_chunk->AddrIsAtLeft(addr, 1, &r_offset));
468    if (l_offset < r_offset)
469      return left_chunk;
470    return right_chunk;
471  }
472
473  AsanChunk *FindChunkByAddr(uptr addr) {
474    PageGroup *g = FindPageGroupUnlocked(addr);
475    if (!g) return 0;
476    CHECK(g->size_of_chunk);
477    uptr offset_from_beg = addr - g->beg;
478    uptr this_chunk_addr = g->beg +
479        (offset_from_beg / g->size_of_chunk) * g->size_of_chunk;
480    CHECK(g->InRange(this_chunk_addr));
481    AsanChunk *m = (AsanChunk*)this_chunk_addr;
482    CHECK(m->chunk_state == CHUNK_ALLOCATED ||
483          m->chunk_state == CHUNK_AVAILABLE ||
484          m->chunk_state == CHUNK_QUARANTINE);
485    uptr offset = 0;
486    if (m->AddrIsInside(addr, 1, &offset))
487      return m;
488
489    if (m->AddrIsAtRight(addr, 1, &offset)) {
490      if (this_chunk_addr == g->last_chunk)  // rightmost chunk
491        return m;
492      uptr right_chunk_addr = this_chunk_addr + g->size_of_chunk;
493      CHECK(g->InRange(right_chunk_addr));
494      return ChooseChunk(addr, m, (AsanChunk*)right_chunk_addr);
495    } else {
496      CHECK(m->AddrIsAtLeft(addr, 1, &offset));
497      if (this_chunk_addr == g->beg)  // leftmost chunk
498        return m;
499      uptr left_chunk_addr = this_chunk_addr - g->size_of_chunk;
500      CHECK(g->InRange(left_chunk_addr));
501      return ChooseChunk(addr, (AsanChunk*)left_chunk_addr, m);
502    }
503  }
504
505  void QuarantinePop() {
506    CHECK(quarantine_.size() > 0);
507    AsanChunk *m = quarantine_.Pop();
508    CHECK(m);
509    // if (F_v >= 2) Printf("MallocInfo::pop %p\n", m);
510
511    CHECK(m->chunk_state == CHUNK_QUARANTINE);
512    m->chunk_state = CHUNK_AVAILABLE;
513    PoisonShadow((uptr)m, m->Size(), kAsanHeapLeftRedzoneMagic);
514    CHECK(m->alloc_tid >= 0);
515    CHECK(m->free_tid >= 0);
516
517    uptr size_class = m->SizeClass();
518    m->next = free_lists_[size_class];
519    free_lists_[size_class] = m;
520
521    // Statistics.
522    AsanStats &thread_stats = asanThreadRegistry().GetCurrentThreadStats();
523    thread_stats.real_frees++;
524    thread_stats.really_freed += m->used_size;
525    thread_stats.really_freed_redzones += m->Size() - m->used_size;
526    thread_stats.really_freed_by_size[m->SizeClass()]++;
527  }
528
529  // Get a list of newly allocated chunks.
530  AsanChunk *GetNewChunks(u8 size_class) {
531    uptr size = SizeClassToSize(size_class);
532    CHECK(IsPowerOfTwo(kMinMmapSize));
533    CHECK(size < kMinMmapSize || (size % kMinMmapSize) == 0);
534    uptr mmap_size = Max(size, kMinMmapSize);
535    uptr n_chunks = mmap_size / size;
536    CHECK(n_chunks * size == mmap_size);
537    if (size < kPageSize) {
538      // Size is small, just poison the last chunk.
539      n_chunks--;
540    } else {
541      // Size is large, allocate an extra page at right and poison it.
542      mmap_size += kPageSize;
543    }
544    CHECK(n_chunks > 0);
545    u8 *mem = MmapNewPagesAndPoisonShadow(mmap_size);
546
547    // Statistics.
548    AsanStats &thread_stats = asanThreadRegistry().GetCurrentThreadStats();
549    thread_stats.mmaps++;
550    thread_stats.mmaped += mmap_size;
551    thread_stats.mmaped_by_size[size_class] += n_chunks;
552
553    AsanChunk *res = 0;
554    for (uptr i = 0; i < n_chunks; i++) {
555      AsanChunk *m = (AsanChunk*)(mem + i * size);
556      m->chunk_state = CHUNK_AVAILABLE;
557      m->size_class = size_class;
558      m->next = res;
559      res = m;
560    }
561    PageGroup *pg = (PageGroup*)(mem + n_chunks * size);
562    // This memory is already poisoned, no need to poison it again.
563    pg->beg = (uptr)mem;
564    pg->end = pg->beg + mmap_size;
565    pg->size_of_chunk = size;
566    pg->last_chunk = (uptr)(mem + size * (n_chunks - 1));
567    int idx = atomic_fetch_add(&n_page_groups_, 1, memory_order_relaxed);
568    CHECK(idx < (int)ARRAY_SIZE(page_groups_));
569    page_groups_[idx] = pg;
570    return res;
571  }
572
573  AsanChunk *free_lists_[kNumberOfSizeClasses];
574  AsanChunkFifoList quarantine_;
575  AsanLock mu_;
576
577  PageGroup *page_groups_[kMaxAvailableRam / kMinMmapSize];
578  atomic_uint32_t n_page_groups_;
579  int n_sorted_page_groups_;
580};
581
582static MallocInfo malloc_info(LINKER_INITIALIZED);
583
584void AsanThreadLocalMallocStorage::CommitBack() {
585  malloc_info.SwallowThreadLocalMallocStorage(this, true);
586}
587
588void DescribeHeapAddress(uptr addr, uptr access_size) {
589  AsanChunk *m = malloc_info.FindMallocedOrFreed(addr, access_size);
590  if (!m) return;
591  m->DescribeAddress(addr, access_size);
592  CHECK(m->alloc_tid >= 0);
593  AsanThreadSummary *alloc_thread =
594      asanThreadRegistry().FindByTid(m->alloc_tid);
595  StackTrace alloc_stack;
596  StackTrace::UncompressStack(&alloc_stack, m->compressed_alloc_stack(),
597                                  m->compressed_alloc_stack_size());
598  AsanThread *t = asanThreadRegistry().GetCurrent();
599  CHECK(t);
600  if (m->free_tid != kInvalidTid) {
601    AsanThreadSummary *free_thread =
602        asanThreadRegistry().FindByTid(m->free_tid);
603    Printf("freed by thread T%d here:\n", free_thread->tid());
604    StackTrace free_stack;
605    StackTrace::UncompressStack(&free_stack, m->compressed_free_stack(),
606                                    m->compressed_free_stack_size());
607    PrintStack(&free_stack);
608    Printf("previously allocated by thread T%d here:\n",
609               alloc_thread->tid());
610
611    PrintStack(&alloc_stack);
612    DescribeThread(t->summary());
613    DescribeThread(free_thread);
614    DescribeThread(alloc_thread);
615  } else {
616    Printf("allocated by thread T%d here:\n", alloc_thread->tid());
617    PrintStack(&alloc_stack);
618    DescribeThread(t->summary());
619    DescribeThread(alloc_thread);
620  }
621}
622
623static u8 *Allocate(uptr alignment, uptr size, StackTrace *stack) {
624  __asan_init();
625  CHECK(stack);
626  if (size == 0) {
627    size = 1;  // TODO(kcc): do something smarter
628  }
629  CHECK(IsPowerOfTwo(alignment));
630  uptr rounded_size = RoundUpTo(size, REDZONE);
631  uptr needed_size = rounded_size + REDZONE;
632  if (alignment > REDZONE) {
633    needed_size += alignment;
634  }
635  CHECK(IsAligned(needed_size, REDZONE));
636  if (size > kMaxAllowedMallocSize || needed_size > kMaxAllowedMallocSize) {
637    Report("WARNING: AddressSanitizer failed to allocate %p bytes\n",
638           (void*)size);
639    return 0;
640  }
641
642  u8 size_class = SizeToSizeClass(needed_size);
643  uptr size_to_allocate = SizeClassToSize(size_class);
644  CHECK(size_to_allocate >= kMinAllocSize);
645  CHECK(size_to_allocate >= needed_size);
646  CHECK(IsAligned(size_to_allocate, REDZONE));
647
648  if (flags()->verbosity >= 3) {
649    Printf("Allocate align: %zu size: %zu class: %u real: %zu\n",
650         alignment, size, size_class, size_to_allocate);
651  }
652
653  AsanThread *t = asanThreadRegistry().GetCurrent();
654  AsanStats &thread_stats = asanThreadRegistry().GetCurrentThreadStats();
655  // Statistics
656  thread_stats.mallocs++;
657  thread_stats.malloced += size;
658  thread_stats.malloced_redzones += size_to_allocate - size;
659  thread_stats.malloced_by_size[size_class]++;
660
661  AsanChunk *m = 0;
662  if (!t || size_to_allocate >= kMaxSizeForThreadLocalFreeList) {
663    // get directly from global storage.
664    m = malloc_info.AllocateChunks(size_class, 1);
665    thread_stats.malloc_large++;
666  } else {
667    // get from the thread-local storage.
668    AsanChunk **fl = &t->malloc_storage().free_lists_[size_class];
669    if (!*fl) {
670      uptr n_new_chunks = kMaxSizeForThreadLocalFreeList / size_to_allocate;
671      *fl = malloc_info.AllocateChunks(size_class, n_new_chunks);
672      thread_stats.malloc_small_slow++;
673    }
674    m = *fl;
675    *fl = (*fl)->next;
676  }
677  CHECK(m);
678  CHECK(m->chunk_state == CHUNK_AVAILABLE);
679  m->chunk_state = CHUNK_ALLOCATED;
680  m->next = 0;
681  CHECK(m->Size() == size_to_allocate);
682  uptr addr = (uptr)m + REDZONE;
683  CHECK(addr <= (uptr)m->compressed_free_stack());
684
685  if (alignment > REDZONE && (addr & (alignment - 1))) {
686    addr = RoundUpTo(addr, alignment);
687    CHECK((addr & (alignment - 1)) == 0);
688    AsanChunk *p = (AsanChunk*)(addr - REDZONE);
689    p->chunk_state = CHUNK_MEMALIGN;
690    p->used_size = (uptr)p - (uptr)m;
691    m->alignment_log = Log2(alignment);
692    CHECK(m->Beg() == addr);
693  } else {
694    m->alignment_log = Log2(REDZONE);
695  }
696  CHECK(m == PtrToChunk(addr));
697  m->used_size = size;
698  CHECK(m->Beg() == addr);
699  m->alloc_tid = t ? t->tid() : 0;
700  m->free_tid   = kInvalidTid;
701  StackTrace::CompressStack(stack, m->compressed_alloc_stack(),
702                                m->compressed_alloc_stack_size());
703  PoisonShadow(addr, rounded_size, 0);
704  if (size < rounded_size) {
705    PoisonHeapPartialRightRedzone(addr + rounded_size - REDZONE,
706                                  size & (REDZONE - 1));
707  }
708  if (size <= (uptr)(flags()->max_malloc_fill_size)) {
709    REAL(memset)((void*)addr, 0, rounded_size);
710  }
711  return (u8*)addr;
712}
713
714static void Deallocate(u8 *ptr, StackTrace *stack) {
715  if (!ptr) return;
716  CHECK(stack);
717
718  if (flags()->debug) {
719    CHECK(malloc_info.FindPageGroup((uptr)ptr));
720  }
721
722  // Printf("Deallocate %p\n", ptr);
723  AsanChunk *m = PtrToChunk((uptr)ptr);
724
725  // Flip the chunk_state atomically to avoid race on double-free.
726  u8 old_chunk_state = atomic_exchange((atomic_uint8_t*)m, CHUNK_QUARANTINE,
727                                       memory_order_acq_rel);
728
729  if (old_chunk_state == CHUNK_QUARANTINE) {
730    ReportDoubleFree((uptr)ptr, stack);
731  } else if (old_chunk_state != CHUNK_ALLOCATED) {
732    ReportFreeNotMalloced((uptr)ptr, stack);
733  }
734  CHECK(old_chunk_state == CHUNK_ALLOCATED);
735  // With REDZONE==16 m->next is in the user area, otherwise it should be 0.
736  CHECK(REDZONE <= 16 || !m->next);
737  CHECK(m->free_tid == kInvalidTid);
738  CHECK(m->alloc_tid >= 0);
739  AsanThread *t = asanThreadRegistry().GetCurrent();
740  m->free_tid = t ? t->tid() : 0;
741  StackTrace::CompressStack(stack, m->compressed_free_stack(),
742                                m->compressed_free_stack_size());
743  uptr rounded_size = RoundUpTo(m->used_size, REDZONE);
744  PoisonShadow((uptr)ptr, rounded_size, kAsanHeapFreeMagic);
745
746  // Statistics.
747  AsanStats &thread_stats = asanThreadRegistry().GetCurrentThreadStats();
748  thread_stats.frees++;
749  thread_stats.freed += m->used_size;
750  thread_stats.freed_by_size[m->SizeClass()]++;
751
752  CHECK(m->chunk_state == CHUNK_QUARANTINE);
753
754  if (t) {
755    AsanThreadLocalMallocStorage *ms = &t->malloc_storage();
756    ms->quarantine_.Push(m);
757
758    if (ms->quarantine_.size() > kMaxThreadLocalQuarantine) {
759      malloc_info.SwallowThreadLocalMallocStorage(ms, false);
760    }
761  } else {
762    malloc_info.BypassThreadLocalQuarantine(m);
763  }
764}
765
766static u8 *Reallocate(u8 *old_ptr, uptr new_size,
767                           StackTrace *stack) {
768  CHECK(old_ptr && new_size);
769
770  // Statistics.
771  AsanStats &thread_stats = asanThreadRegistry().GetCurrentThreadStats();
772  thread_stats.reallocs++;
773  thread_stats.realloced += new_size;
774
775  AsanChunk *m = PtrToChunk((uptr)old_ptr);
776  CHECK(m->chunk_state == CHUNK_ALLOCATED);
777  uptr old_size = m->used_size;
778  uptr memcpy_size = Min(new_size, old_size);
779  u8 *new_ptr = Allocate(0, new_size, stack);
780  if (new_ptr) {
781    CHECK(REAL(memcpy) != 0);
782    REAL(memcpy)(new_ptr, old_ptr, memcpy_size);
783    Deallocate(old_ptr, stack);
784  }
785  return new_ptr;
786}
787
788}  // namespace __asan
789
790// Default (no-op) implementation of malloc hooks.
791extern "C" {
792SANITIZER_WEAK_ATTRIBUTE SANITIZER_INTERFACE_ATTRIBUTE
793void __asan_malloc_hook(void *ptr, uptr size) {
794  (void)ptr;
795  (void)size;
796}
797SANITIZER_WEAK_ATTRIBUTE SANITIZER_INTERFACE_ATTRIBUTE
798void __asan_free_hook(void *ptr) {
799  (void)ptr;
800}
801}  // extern "C"
802
803namespace __asan {
804
805SANITIZER_INTERFACE_ATTRIBUTE
806void *asan_memalign(uptr alignment, uptr size, StackTrace *stack) {
807  void *ptr = (void*)Allocate(alignment, size, stack);
808  __asan_malloc_hook(ptr, size);
809  return ptr;
810}
811
812SANITIZER_INTERFACE_ATTRIBUTE
813void asan_free(void *ptr, StackTrace *stack) {
814  __asan_free_hook(ptr);
815  Deallocate((u8*)ptr, stack);
816}
817
818SANITIZER_INTERFACE_ATTRIBUTE
819void *asan_malloc(uptr size, StackTrace *stack) {
820  void *ptr = (void*)Allocate(0, size, stack);
821  __asan_malloc_hook(ptr, size);
822  return ptr;
823}
824
825void *asan_calloc(uptr nmemb, uptr size, StackTrace *stack) {
826  void *ptr = (void*)Allocate(0, nmemb * size, stack);
827  if (ptr)
828    REAL(memset)(ptr, 0, nmemb * size);
829  __asan_malloc_hook(ptr, nmemb * size);
830  return ptr;
831}
832
833void *asan_realloc(void *p, uptr size, StackTrace *stack) {
834  if (p == 0) {
835    void *ptr = (void*)Allocate(0, size, stack);
836    __asan_malloc_hook(ptr, size);
837    return ptr;
838  } else if (size == 0) {
839    __asan_free_hook(p);
840    Deallocate((u8*)p, stack);
841    return 0;
842  }
843  return Reallocate((u8*)p, size, stack);
844}
845
846void *asan_valloc(uptr size, StackTrace *stack) {
847  void *ptr = (void*)Allocate(kPageSize, size, stack);
848  __asan_malloc_hook(ptr, size);
849  return ptr;
850}
851
852void *asan_pvalloc(uptr size, StackTrace *stack) {
853  size = RoundUpTo(size, kPageSize);
854  if (size == 0) {
855    // pvalloc(0) should allocate one page.
856    size = kPageSize;
857  }
858  void *ptr = (void*)Allocate(kPageSize, size, stack);
859  __asan_malloc_hook(ptr, size);
860  return ptr;
861}
862
863int asan_posix_memalign(void **memptr, uptr alignment, uptr size,
864                          StackTrace *stack) {
865  void *ptr = Allocate(alignment, size, stack);
866  CHECK(IsAligned((uptr)ptr, alignment));
867  __asan_malloc_hook(ptr, size);
868  *memptr = ptr;
869  return 0;
870}
871
872uptr asan_malloc_usable_size(void *ptr, StackTrace *stack) {
873  CHECK(stack);
874  if (ptr == 0) return 0;
875  uptr usable_size = malloc_info.AllocationSize((uptr)ptr);
876  if (flags()->check_malloc_usable_size && (usable_size == 0)) {
877    ReportMallocUsableSizeNotOwned((uptr)ptr, stack);
878  }
879  return usable_size;
880}
881
882uptr asan_mz_size(const void *ptr) {
883  return malloc_info.AllocationSize((uptr)ptr);
884}
885
886void asan_mz_force_lock() {
887  malloc_info.ForceLock();
888}
889
890void asan_mz_force_unlock() {
891  malloc_info.ForceUnlock();
892}
893
894// ---------------------- Fake stack-------------------- {{{1
895FakeStack::FakeStack() {
896  CHECK(REAL(memset) != 0);
897  REAL(memset)(this, 0, sizeof(*this));
898}
899
900bool FakeStack::AddrIsInSizeClass(uptr addr, uptr size_class) {
901  uptr mem = allocated_size_classes_[size_class];
902  uptr size = ClassMmapSize(size_class);
903  bool res = mem && addr >= mem && addr < mem + size;
904  return res;
905}
906
907uptr FakeStack::AddrIsInFakeStack(uptr addr) {
908  for (uptr i = 0; i < kNumberOfSizeClasses; i++) {
909    if (AddrIsInSizeClass(addr, i)) return allocated_size_classes_[i];
910  }
911  return 0;
912}
913
914// We may want to compute this during compilation.
915inline uptr FakeStack::ComputeSizeClass(uptr alloc_size) {
916  uptr rounded_size = RoundUpToPowerOfTwo(alloc_size);
917  uptr log = Log2(rounded_size);
918  CHECK(alloc_size <= (1UL << log));
919  if (!(alloc_size > (1UL << (log-1)))) {
920    Printf("alloc_size %zu log %zu\n", alloc_size, log);
921  }
922  CHECK(alloc_size > (1UL << (log-1)));
923  uptr res = log < kMinStackFrameSizeLog ? 0 : log - kMinStackFrameSizeLog;
924  CHECK(res < kNumberOfSizeClasses);
925  CHECK(ClassSize(res) >= rounded_size);
926  return res;
927}
928
929void FakeFrameFifo::FifoPush(FakeFrame *node) {
930  CHECK(node);
931  node->next = 0;
932  if (first_ == 0 && last_ == 0) {
933    first_ = last_ = node;
934  } else {
935    CHECK(first_);
936    CHECK(last_);
937    last_->next = node;
938    last_ = node;
939  }
940}
941
942FakeFrame *FakeFrameFifo::FifoPop() {
943  CHECK(first_ && last_ && "Exhausted fake stack");
944  FakeFrame *res = 0;
945  if (first_ == last_) {
946    res = first_;
947    first_ = last_ = 0;
948  } else {
949    res = first_;
950    first_ = first_->next;
951  }
952  return res;
953}
954
955void FakeStack::Init(uptr stack_size) {
956  stack_size_ = stack_size;
957  alive_ = true;
958}
959
960void FakeStack::Cleanup() {
961  alive_ = false;
962  for (uptr i = 0; i < kNumberOfSizeClasses; i++) {
963    uptr mem = allocated_size_classes_[i];
964    if (mem) {
965      PoisonShadow(mem, ClassMmapSize(i), 0);
966      allocated_size_classes_[i] = 0;
967      UnmapOrDie((void*)mem, ClassMmapSize(i));
968    }
969  }
970}
971
972uptr FakeStack::ClassMmapSize(uptr size_class) {
973  return RoundUpToPowerOfTwo(stack_size_);
974}
975
976void FakeStack::AllocateOneSizeClass(uptr size_class) {
977  CHECK(ClassMmapSize(size_class) >= kPageSize);
978  uptr new_mem = (uptr)MmapOrDie(
979      ClassMmapSize(size_class), __FUNCTION__);
980  // Printf("T%d new_mem[%zu]: %p-%p mmap %zu\n",
981  //       asanThreadRegistry().GetCurrent()->tid(),
982  //       size_class, new_mem, new_mem + ClassMmapSize(size_class),
983  //       ClassMmapSize(size_class));
984  uptr i;
985  for (i = 0; i < ClassMmapSize(size_class);
986       i += ClassSize(size_class)) {
987    size_classes_[size_class].FifoPush((FakeFrame*)(new_mem + i));
988  }
989  CHECK(i == ClassMmapSize(size_class));
990  allocated_size_classes_[size_class] = new_mem;
991}
992
993uptr FakeStack::AllocateStack(uptr size, uptr real_stack) {
994  if (!alive_) return real_stack;
995  CHECK(size <= kMaxStackMallocSize && size > 1);
996  uptr size_class = ComputeSizeClass(size);
997  if (!allocated_size_classes_[size_class]) {
998    AllocateOneSizeClass(size_class);
999  }
1000  FakeFrame *fake_frame = size_classes_[size_class].FifoPop();
1001  CHECK(fake_frame);
1002  fake_frame->size_minus_one = size - 1;
1003  fake_frame->real_stack = real_stack;
1004  while (FakeFrame *top = call_stack_.top()) {
1005    if (top->real_stack > real_stack) break;
1006    call_stack_.LifoPop();
1007    DeallocateFrame(top);
1008  }
1009  call_stack_.LifoPush(fake_frame);
1010  uptr ptr = (uptr)fake_frame;
1011  PoisonShadow(ptr, size, 0);
1012  return ptr;
1013}
1014
1015void FakeStack::DeallocateFrame(FakeFrame *fake_frame) {
1016  CHECK(alive_);
1017  uptr size = fake_frame->size_minus_one + 1;
1018  uptr size_class = ComputeSizeClass(size);
1019  CHECK(allocated_size_classes_[size_class]);
1020  uptr ptr = (uptr)fake_frame;
1021  CHECK(AddrIsInSizeClass(ptr, size_class));
1022  CHECK(AddrIsInSizeClass(ptr + size - 1, size_class));
1023  size_classes_[size_class].FifoPush(fake_frame);
1024}
1025
1026void FakeStack::OnFree(uptr ptr, uptr size, uptr real_stack) {
1027  FakeFrame *fake_frame = (FakeFrame*)ptr;
1028  CHECK(fake_frame->magic = kRetiredStackFrameMagic);
1029  CHECK(fake_frame->descr != 0);
1030  CHECK(fake_frame->size_minus_one == size - 1);
1031  PoisonShadow(ptr, size, kAsanStackAfterReturnMagic);
1032}
1033
1034}  // namespace __asan
1035
1036// ---------------------- Interface ---------------- {{{1
1037using namespace __asan;  // NOLINT
1038
1039uptr __asan_stack_malloc(uptr size, uptr real_stack) {
1040  if (!flags()->use_fake_stack) return real_stack;
1041  AsanThread *t = asanThreadRegistry().GetCurrent();
1042  if (!t) {
1043    // TSD is gone, use the real stack.
1044    return real_stack;
1045  }
1046  uptr ptr = t->fake_stack().AllocateStack(size, real_stack);
1047  // Printf("__asan_stack_malloc %p %zu %p\n", ptr, size, real_stack);
1048  return ptr;
1049}
1050
1051void __asan_stack_free(uptr ptr, uptr size, uptr real_stack) {
1052  if (!flags()->use_fake_stack) return;
1053  if (ptr != real_stack) {
1054    FakeStack::OnFree(ptr, size, real_stack);
1055  }
1056}
1057
1058// ASan allocator doesn't reserve extra bytes, so normally we would
1059// just return "size".
1060uptr __asan_get_estimated_allocated_size(uptr size) {
1061  if (size == 0) return 1;
1062  return Min(size, kMaxAllowedMallocSize);
1063}
1064
1065bool __asan_get_ownership(const void *p) {
1066  return malloc_info.AllocationSize((uptr)p) > 0;
1067}
1068
1069uptr __asan_get_allocated_size(const void *p) {
1070  if (p == 0) return 0;
1071  uptr allocated_size = malloc_info.AllocationSize((uptr)p);
1072  // Die if p is not malloced or if it is already freed.
1073  if (allocated_size == 0) {
1074    GET_STACK_TRACE_HERE(kStackTraceMax);
1075    ReportAsanGetAllocatedSizeNotOwned((uptr)p, &stack);
1076  }
1077  return allocated_size;
1078}
1079