libsanitizer/asan/asan_allocator2.cc

   1 //===-- asan_allocator2.cc ------------------------------------------------===//
   2 //
   3 // This file is distributed under the University of Illinois Open Source
   4 // License. See LICENSE.TXT for details.
   5 //
   6 //===----------------------------------------------------------------------===//
   7 //
   8 // This file is a part of AddressSanitizer, an address sanity checker.
   9 //
  10 // Implementation of ASan's memory allocator, 2-nd version.
  11 // This variant uses the allocator from sanitizer_common, i.e. the one shared
  12 // with ThreadSanitizer and MemorySanitizer.
  13 //
  14 //===----------------------------------------------------------------------===//
  15 #include "asan_allocator.h"
  16
  17 #include "asan_mapping.h"
  18 #include "asan_poisoning.h"
  19 #include "asan_report.h"
  20 #include "asan_thread.h"
  21 #include "sanitizer_common/sanitizer_allocator.h"
  22 #include "sanitizer_common/sanitizer_flags.h"
  23 #include "sanitizer_common/sanitizer_internal_defs.h"
  24 #include "sanitizer_common/sanitizer_list.h"
  25 #include "sanitizer_common/sanitizer_stackdepot.h"
  26 #include "sanitizer_common/sanitizer_quarantine.h"
  27 #include "lsan/lsan_common.h"
  28
  29 namespace __asan {
  30
  31 struct AsanMapUnmapCallback {
  32   void OnMap(uptr p, uptr size) const {
  33     PoisonShadow(p, size, kAsanHeapLeftRedzoneMagic);
  34     // Statistics.
  35     AsanStats &thread_stats = GetCurrentThreadStats();
  36     thread_stats.mmaps++;
  37     thread_stats.mmaped += size;
  38   }
  39   void OnUnmap(uptr p, uptr size) const {
  40     PoisonShadow(p, size, 0);
  41     // We are about to unmap a chunk of user memory.
  42     // Mark the corresponding shadow memory as not needed.
  43     // Since asan's mapping is compacting, the shadow chunk may be
  44     // not page-aligned, so we only flush the page-aligned portion.
  45     uptr page_size = GetPageSizeCached();
  46     uptr shadow_beg = RoundUpTo(MemToShadow(p), page_size);
  47     uptr shadow_end = RoundDownTo(MemToShadow(p + size), page_size);
  48     FlushUnneededShadowMemory(shadow_beg, shadow_end - shadow_beg);
  49     // Statistics.
  50     AsanStats &thread_stats = GetCurrentThreadStats();
  51     thread_stats.munmaps++;
  52     thread_stats.munmaped += size;
  53   }
  54 };
  55
  56 #if SANITIZER_WORDSIZE == 64
  57 #if defined(__powerpc64__)
  58 const uptr kAllocatorSpace =  0xa0000000000ULL;
  59 const uptr kAllocatorSize  =  0x20000000000ULL;  // 2T.
  60 #else
  61 const uptr kAllocatorSpace = 0x600000000000ULL;
  62 const uptr kAllocatorSize  =  0x40000000000ULL;  // 4T.
  63 #endif
  64 typedef DefaultSizeClassMap SizeClassMap;
  65 typedef SizeClassAllocator64<kAllocatorSpace, kAllocatorSize, 0 /*metadata*/,
  66     SizeClassMap, AsanMapUnmapCallback> PrimaryAllocator;
  67 #elif SANITIZER_WORDSIZE == 32
  68 static const u64 kAddressSpaceSize = 1ULL << 32;
  69 typedef CompactSizeClassMap SizeClassMap;
  70 static const uptr kRegionSizeLog = 20;
  71 static const uptr kFlatByteMapSize = kAddressSpaceSize >> kRegionSizeLog;
  72 typedef SizeClassAllocator32<0, kAddressSpaceSize, 16,
  73   SizeClassMap, kRegionSizeLog,
  74   FlatByteMap<kFlatByteMapSize>,
  75   AsanMapUnmapCallback> PrimaryAllocator;
  76 #endif
  77
  78 typedef SizeClassAllocatorLocalCache<PrimaryAllocator> AllocatorCache;
  79 typedef LargeMmapAllocator<AsanMapUnmapCallback> SecondaryAllocator;
  80 typedef CombinedAllocator<PrimaryAllocator, AllocatorCache,
  81     SecondaryAllocator> Allocator;
  82
  83 // We can not use THREADLOCAL because it is not supported on some of the
  84 // platforms we care about (OSX 10.6, Android).
  85 // static THREADLOCAL AllocatorCache cache;
  86 AllocatorCache *GetAllocatorCache(AsanThreadLocalMallocStorage *ms) {
  87   CHECK(ms);
  88   CHECK_LE(sizeof(AllocatorCache), sizeof(ms->allocator2_cache));
  89   return reinterpret_cast<AllocatorCache *>(ms->allocator2_cache);
  90 }
  91
  92 static Allocator allocator;
  93
  94 static const uptr kMaxAllowedMallocSize =
  95   FIRST_32_SECOND_64(3UL << 30, 64UL << 30);
  96
  97 static const uptr kMaxThreadLocalQuarantine =
  98   FIRST_32_SECOND_64(1 << 18, 1 << 20);
  99
 100 // Every chunk of memory allocated by this allocator can be in one of 3 states:
 101 // CHUNK_AVAILABLE: the chunk is in the free list and ready to be allocated.
 102 // CHUNK_ALLOCATED: the chunk is allocated and not yet freed.
 103 // CHUNK_QUARANTINE: the chunk was freed and put into quarantine zone.
 104 enum {
 105   CHUNK_AVAILABLE  = 0,  // 0 is the default value even if we didn't set it.
 106   CHUNK_ALLOCATED  = 2,
 107   CHUNK_QUARANTINE = 3
 108 };
 109
 110 // Valid redzone sizes are 16, 32, 64, ... 2048, so we encode them in 3 bits.
 111 // We use adaptive redzones: for larger allocation larger redzones are used.
 112 static u32 RZLog2Size(u32 rz_log) {
 113   CHECK_LT(rz_log, 8);
 114   return 16 << rz_log;
 115 }
 116
 117 static u32 RZSize2Log(u32 rz_size) {
 118   CHECK_GE(rz_size, 16);
 119   CHECK_LE(rz_size, 2048);
 120   CHECK(IsPowerOfTwo(rz_size));
 121   u32 res = Log2(rz_size) - 4;
 122   CHECK_EQ(rz_size, RZLog2Size(res));
 123   return res;
 124 }
 125
 126 static uptr ComputeRZLog(uptr user_requested_size) {
 127   u32 rz_log =
 128     user_requested_size <= 64        - 16   ? 0 :
 129     user_requested_size <= 128       - 32   ? 1 :
 130     user_requested_size <= 512       - 64   ? 2 :
 131     user_requested_size <= 4096      - 128  ? 3 :
 132     user_requested_size <= (1 << 14) - 256  ? 4 :
 133     user_requested_size <= (1 << 15) - 512  ? 5 :
 134     user_requested_size <= (1 << 16) - 1024 ? 6 : 7;
 135   return Max(rz_log, RZSize2Log(flags()->redzone));
 136 }
 137
 138 // The memory chunk allocated from the underlying allocator looks like this:
 139 // L L L L L L H H U U U U U U R R
 140 //   L -- left redzone words (0 or more bytes)
 141 //   H -- ChunkHeader (16 bytes), which is also a part of the left redzone.
 142 //   U -- user memory.
 143 //   R -- right redzone (0 or more bytes)
 144 // ChunkBase consists of ChunkHeader and other bytes that overlap with user
 145 // memory.
 146
 147 // If the left redzone is greater than the ChunkHeader size we store a magic
 148 // value in the first uptr word of the memory block and store the address of
 149 // ChunkBase in the next uptr.
 150 // M B L L L L L L L L L  H H U U U U U U
 151 //   |                    ^
 152 //   ---------------------|
 153 //   M -- magic value kAllocBegMagic
 154 //   B -- address of ChunkHeader pointing to the first 'H'
 155 static const uptr kAllocBegMagic = 0xCC6E96B9;
 156
 157 struct ChunkHeader {
 158   // 1-st 8 bytes.
 159   u32 chunk_state       : 8;  // Must be first.
 160   u32 alloc_tid         : 24;
 161
 162   u32 free_tid          : 24;
 163   u32 from_memalign     : 1;
 164   u32 alloc_type        : 2;
 165   u32 rz_log            : 3;
 166   u32 lsan_tag          : 2;
 167   // 2-nd 8 bytes
 168   // This field is used for small sizes. For large sizes it is equal to
 169   // SizeClassMap::kMaxSize and the actual size is stored in the
 170   // SecondaryAllocator's metadata.
 171   u32 user_requested_size;
 172   u32 alloc_context_id;
 173 };
 174
 175 struct ChunkBase : ChunkHeader {
 176   // Header2, intersects with user memory.
 177   u32 free_context_id;
 178 };
 179
 180 static const uptr kChunkHeaderSize = sizeof(ChunkHeader);
 181 static const uptr kChunkHeader2Size = sizeof(ChunkBase) - kChunkHeaderSize;
 182 COMPILER_CHECK(kChunkHeaderSize == 16);
 183 COMPILER_CHECK(kChunkHeader2Size <= 16);
 184
 185 struct AsanChunk: ChunkBase {
 186   uptr Beg() { return reinterpret_cast<uptr>(this) + kChunkHeaderSize; }
 187   uptr UsedSize(bool locked_version = false) {
 188     if (user_requested_size != SizeClassMap::kMaxSize)
 189       return user_requested_size;
 190     return *reinterpret_cast<uptr *>(
 191                 allocator.GetMetaData(AllocBeg(locked_version)));
 192   }
 193   void *AllocBeg(bool locked_version = false) {
 194     if (from_memalign) {
 195       if (locked_version)
 196         return allocator.GetBlockBeginFastLocked(
 197             reinterpret_cast<void *>(this));
 198       return allocator.GetBlockBegin(reinterpret_cast<void *>(this));
 199     }
 200     return reinterpret_cast<void*>(Beg() - RZLog2Size(rz_log));
 201   }
 202   // If we don't use stack depot, we store the alloc/free stack traces
 203   // in the chunk itself.
 204   u32 *AllocStackBeg() {
 205     return (u32*)(Beg() - RZLog2Size(rz_log));
 206   }
 207   uptr AllocStackSize() {
 208     CHECK_LE(RZLog2Size(rz_log), kChunkHeaderSize);
 209     return (RZLog2Size(rz_log) - kChunkHeaderSize) / sizeof(u32);
 210   }
 211   u32 *FreeStackBeg() {
 212     return (u32*)(Beg() + kChunkHeader2Size);
 213   }
 214   uptr FreeStackSize() {
 215     if (user_requested_size < kChunkHeader2Size) return 0;
 216     uptr available = RoundUpTo(user_requested_size, SHADOW_GRANULARITY);
 217     return (available - kChunkHeader2Size) / sizeof(u32);
 218   }
 219   bool AddrIsInside(uptr addr, bool locked_version = false) {
 220     return (addr >= Beg()) && (addr < Beg() + UsedSize(locked_version));
 221   }
 222 };
 223
 224 bool AsanChunkView::IsValid() {
 225   return chunk_ != 0 && chunk_->chunk_state != CHUNK_AVAILABLE;
 226 }
 227 uptr AsanChunkView::Beg() { return chunk_->Beg(); }
 228 uptr AsanChunkView::End() { return Beg() + UsedSize(); }
 229 uptr AsanChunkView::UsedSize() { return chunk_->UsedSize(); }
 230 uptr AsanChunkView::AllocTid() { return chunk_->alloc_tid; }
 231 uptr AsanChunkView::FreeTid() { return chunk_->free_tid; }
 232
 233 static void GetStackTraceFromId(u32 id, StackTrace *stack) {
 234   CHECK(id);
 235   uptr size = 0;
 236   const uptr *trace = StackDepotGet(id, &size);
 237   CHECK(trace);
 238   stack->CopyFrom(trace, size);
 239 }
 240
 241 void AsanChunkView::GetAllocStack(StackTrace *stack) {
 242   GetStackTraceFromId(chunk_->alloc_context_id, stack);
 243 }
 244
 245 void AsanChunkView::GetFreeStack(StackTrace *stack) {
 246   GetStackTraceFromId(chunk_->free_context_id, stack);
 247 }
 248
 249 struct QuarantineCallback;
 250 typedef Quarantine<QuarantineCallback, AsanChunk> AsanQuarantine;
 251 typedef AsanQuarantine::Cache QuarantineCache;
 252 static AsanQuarantine quarantine(LINKER_INITIALIZED);
 253 static QuarantineCache fallback_quarantine_cache(LINKER_INITIALIZED);
 254 static AllocatorCache fallback_allocator_cache;
 255 static SpinMutex fallback_mutex;
 256
 257 QuarantineCache *GetQuarantineCache(AsanThreadLocalMallocStorage *ms) {
 258   CHECK(ms);
 259   CHECK_LE(sizeof(QuarantineCache), sizeof(ms->quarantine_cache));
 260   return reinterpret_cast<QuarantineCache *>(ms->quarantine_cache);
 261 }
 262
 263 struct QuarantineCallback {
 264   explicit QuarantineCallback(AllocatorCache *cache)
 265       : cache_(cache) {
 266   }
 267
 268   void Recycle(AsanChunk *m) {
 269     CHECK_EQ(m->chunk_state, CHUNK_QUARANTINE);
 270     atomic_store((atomic_uint8_t*)m, CHUNK_AVAILABLE, memory_order_relaxed);
 271     CHECK_NE(m->alloc_tid, kInvalidTid);
 272     CHECK_NE(m->free_tid, kInvalidTid);
 273     PoisonShadow(m->Beg(),
 274                  RoundUpTo(m->UsedSize(), SHADOW_GRANULARITY),
 275                  kAsanHeapLeftRedzoneMagic);
 276     void *p = reinterpret_cast<void *>(m->AllocBeg());
 277     if (p != m) {
 278       uptr *alloc_magic = reinterpret_cast<uptr *>(p);
 279       CHECK_EQ(alloc_magic[0], kAllocBegMagic);
 280       // Clear the magic value, as allocator internals may overwrite the
 281       // contents of deallocated chunk, confusing GetAsanChunk lookup.
 282       alloc_magic[0] = 0;
 283       CHECK_EQ(alloc_magic[1], reinterpret_cast<uptr>(m));
 284     }
 285
 286     // Statistics.
 287     AsanStats &thread_stats = GetCurrentThreadStats();
 288     thread_stats.real_frees++;
 289     thread_stats.really_freed += m->UsedSize();
 290
 291     allocator.Deallocate(cache_, p);
 292   }
 293
 294   void *Allocate(uptr size) {
 295     return allocator.Allocate(cache_, size, 1, false);
 296   }
 297
 298   void Deallocate(void *p) {
 299     allocator.Deallocate(cache_, p);
 300   }
 301
 302   AllocatorCache *cache_;
 303 };
 304
 305 void InitializeAllocator() {
 306   allocator.Init();
 307   quarantine.Init((uptr)flags()->quarantine_size, kMaxThreadLocalQuarantine);
 308 }
 309
 310 static void *Allocate(uptr size, uptr alignment, StackTrace *stack,
 311                       AllocType alloc_type, bool can_fill) {
 312   if (!asan_inited)
 313     __asan_init();
 314   Flags &fl = *flags();
 315   CHECK(stack);
 316   const uptr min_alignment = SHADOW_GRANULARITY;
 317   if (alignment < min_alignment)
 318     alignment = min_alignment;
 319   if (size == 0) {
 320     // We'd be happy to avoid allocating memory for zero-size requests, but
 321     // some programs/tests depend on this behavior and assume that malloc would
 322     // not return NULL even for zero-size allocations. Moreover, it looks like
 323     // operator new should never return NULL, and results of consecutive "new"
 324     // calls must be different even if the allocated size is zero.
 325     size = 1;
 326   }
 327   CHECK(IsPowerOfTwo(alignment));
 328   uptr rz_log = ComputeRZLog(size);
 329   uptr rz_size = RZLog2Size(rz_log);
 330   uptr rounded_size = RoundUpTo(Max(size, kChunkHeader2Size), alignment);
 331   uptr needed_size = rounded_size + rz_size;
 332   if (alignment > min_alignment)
 333     needed_size += alignment;
 334   bool using_primary_allocator = true;
 335   // If we are allocating from the secondary allocator, there will be no
 336   // automatic right redzone, so add the right redzone manually.
 337   if (!PrimaryAllocator::CanAllocate(needed_size, alignment)) {
 338     needed_size += rz_size;
 339     using_primary_allocator = false;
 340   }
 341   CHECK(IsAligned(needed_size, min_alignment));
 342   if (size > kMaxAllowedMallocSize || needed_size > kMaxAllowedMallocSize) {
 343     Report("WARNING: AddressSanitizer failed to allocate %p bytes\n",
 344            (void*)size);
 345     return AllocatorReturnNull();
 346   }
 347
 348   AsanThread *t = GetCurrentThread();
 349   void *allocated;
 350   if (t) {
 351     AllocatorCache *cache = GetAllocatorCache(&t->malloc_storage());
 352     allocated = allocator.Allocate(cache, needed_size, 8, false);
 353   } else {
 354     SpinMutexLock l(&fallback_mutex);
 355     AllocatorCache *cache = &fallback_allocator_cache;
 356     allocated = allocator.Allocate(cache, needed_size, 8, false);
 357   }
 358   uptr alloc_beg = reinterpret_cast<uptr>(allocated);
 359   uptr alloc_end = alloc_beg + needed_size;
 360   uptr beg_plus_redzone = alloc_beg + rz_size;
 361   uptr user_beg = beg_plus_redzone;
 362   if (!IsAligned(user_beg, alignment))
 363     user_beg = RoundUpTo(user_beg, alignment);
 364   uptr user_end = user_beg + size;
 365   CHECK_LE(user_end, alloc_end);
 366   uptr chunk_beg = user_beg - kChunkHeaderSize;
 367   AsanChunk *m = reinterpret_cast<AsanChunk *>(chunk_beg);
 368   m->alloc_type = alloc_type;
 369   m->rz_log = rz_log;
 370   u32 alloc_tid = t ? t->tid() : 0;
 371   m->alloc_tid = alloc_tid;
 372   CHECK_EQ(alloc_tid, m->alloc_tid);  // Does alloc_tid fit into the bitfield?
 373   m->free_tid = kInvalidTid;
 374   m->from_memalign = user_beg != beg_plus_redzone;
 375   if (alloc_beg != chunk_beg) {
 376     CHECK_LE(alloc_beg+ 2 * sizeof(uptr), chunk_beg);
 377     reinterpret_cast<uptr *>(alloc_beg)[0] = kAllocBegMagic;
 378     reinterpret_cast<uptr *>(alloc_beg)[1] = chunk_beg;
 379   }
 380   if (using_primary_allocator) {
 381     CHECK(size);
 382     m->user_requested_size = size;
 383     CHECK(allocator.FromPrimary(allocated));
 384   } else {
 385     CHECK(!allocator.FromPrimary(allocated));
 386     m->user_requested_size = SizeClassMap::kMaxSize;
 387     uptr *meta = reinterpret_cast<uptr *>(allocator.GetMetaData(allocated));
 388     meta[0] = size;
 389     meta[1] = chunk_beg;
 390   }
 391
 392   m->alloc_context_id = StackDepotPut(stack->trace, stack->size);
 393
 394   uptr size_rounded_down_to_granularity = RoundDownTo(size, SHADOW_GRANULARITY);
 395   // Unpoison the bulk of the memory region.
 396   if (size_rounded_down_to_granularity)
 397     PoisonShadow(user_beg, size_rounded_down_to_granularity, 0);
 398   // Deal with the end of the region if size is not aligned to granularity.
 399   if (size != size_rounded_down_to_granularity && fl.poison_heap) {
 400     u8 *shadow = (u8*)MemToShadow(user_beg + size_rounded_down_to_granularity);
 401     *shadow = fl.poison_partial ? (size & (SHADOW_GRANULARITY - 1)) : 0;
 402   }
 403
 404   AsanStats &thread_stats = GetCurrentThreadStats();
 405   thread_stats.mallocs++;
 406   thread_stats.malloced += size;
 407   thread_stats.malloced_redzones += needed_size - size;
 408   uptr class_id = Min(kNumberOfSizeClasses, SizeClassMap::ClassID(needed_size));
 409   thread_stats.malloced_by_size[class_id]++;
 410   if (needed_size > SizeClassMap::kMaxSize)
 411     thread_stats.malloc_large++;
 412
 413   void *res = reinterpret_cast<void *>(user_beg);
 414   if (can_fill && fl.max_malloc_fill_size) {
 415     uptr fill_size = Min(size, (uptr)fl.max_malloc_fill_size);
 416     REAL(memset)(res, fl.malloc_fill_byte, fill_size);
 417   }
 418 #if CAN_SANITIZE_LEAKS
 419   m->lsan_tag = __lsan::DisabledInThisThread() ? __lsan::kIgnored
 420                                                : __lsan::kDirectlyLeaked;
 421 #endif
 422   // Must be the last mutation of metadata in this function.
 423   atomic_store((atomic_uint8_t *)m, CHUNK_ALLOCATED, memory_order_release);
 424   ASAN_MALLOC_HOOK(res, size);
 425   return res;
 426 }
 427
 428 static void ReportInvalidFree(void *ptr, u8 chunk_state, StackTrace *stack) {
 429   if (chunk_state == CHUNK_QUARANTINE)
 430     ReportDoubleFree((uptr)ptr, stack);
 431   else
 432     ReportFreeNotMalloced((uptr)ptr, stack);
 433 }
 434
 435 static void AtomicallySetQuarantineFlag(AsanChunk *m,
 436                                         void *ptr, StackTrace *stack) {
 437   u8 old_chunk_state = CHUNK_ALLOCATED;
 438   // Flip the chunk_state atomically to avoid race on double-free.
 439   if (!atomic_compare_exchange_strong((atomic_uint8_t*)m, &old_chunk_state,
 440                                       CHUNK_QUARANTINE, memory_order_acquire))
 441     ReportInvalidFree(ptr, old_chunk_state, stack);
 442   CHECK_EQ(CHUNK_ALLOCATED, old_chunk_state);
 443 }
 444
 445 // Expects the chunk to already be marked as quarantined by using
 446 // AtomicallySetQuarantineFlag.
 447 static void QuarantineChunk(AsanChunk *m, void *ptr,
 448                             StackTrace *stack, AllocType alloc_type) {
 449   CHECK_EQ(m->chunk_state, CHUNK_QUARANTINE);
 450
 451   if (m->alloc_type != alloc_type && flags()->alloc_dealloc_mismatch)
 452     ReportAllocTypeMismatch((uptr)ptr, stack,
 453                             (AllocType)m->alloc_type, (AllocType)alloc_type);
 454
 455   CHECK_GE(m->alloc_tid, 0);
 456   if (SANITIZER_WORDSIZE == 64)  // On 32-bits this resides in user area.
 457     CHECK_EQ(m->free_tid, kInvalidTid);
 458   AsanThread *t = GetCurrentThread();
 459   m->free_tid = t ? t->tid() : 0;
 460   m->free_context_id = StackDepotPut(stack->trace, stack->size);
 461   // Poison the region.
 462   PoisonShadow(m->Beg(),
 463                RoundUpTo(m->UsedSize(), SHADOW_GRANULARITY),
 464                kAsanHeapFreeMagic);
 465
 466   AsanStats &thread_stats = GetCurrentThreadStats();
 467   thread_stats.frees++;
 468   thread_stats.freed += m->UsedSize();
 469
 470   // Push into quarantine.
 471   if (t) {
 472     AsanThreadLocalMallocStorage *ms = &t->malloc_storage();
 473     AllocatorCache *ac = GetAllocatorCache(ms);
 474     quarantine.Put(GetQuarantineCache(ms), QuarantineCallback(ac),
 475                    m, m->UsedSize());
 476   } else {
 477     SpinMutexLock l(&fallback_mutex);
 478     AllocatorCache *ac = &fallback_allocator_cache;
 479     quarantine.Put(&fallback_quarantine_cache, QuarantineCallback(ac),
 480                    m, m->UsedSize());
 481   }
 482 }
 483
 484 static void Deallocate(void *ptr, StackTrace *stack, AllocType alloc_type) {
 485   uptr p = reinterpret_cast<uptr>(ptr);
 486   if (p == 0) return;
 487
 488   uptr chunk_beg = p - kChunkHeaderSize;
 489   AsanChunk *m = reinterpret_cast<AsanChunk *>(chunk_beg);
 490   ASAN_FREE_HOOK(ptr);
 491   // Must mark the chunk as quarantined before any changes to its metadata.
 492   AtomicallySetQuarantineFlag(m, ptr, stack);
 493   QuarantineChunk(m, ptr, stack, alloc_type);
 494 }
 495
 496 static void *Reallocate(void *old_ptr, uptr new_size, StackTrace *stack) {
 497   CHECK(old_ptr && new_size);
 498   uptr p = reinterpret_cast<uptr>(old_ptr);
 499   uptr chunk_beg = p - kChunkHeaderSize;
 500   AsanChunk *m = reinterpret_cast<AsanChunk *>(chunk_beg);
 501
 502   AsanStats &thread_stats = GetCurrentThreadStats();
 503   thread_stats.reallocs++;
 504   thread_stats.realloced += new_size;
 505
 506   void *new_ptr = Allocate(new_size, 8, stack, FROM_MALLOC, true);
 507   if (new_ptr) {
 508     u8 chunk_state = m->chunk_state;
 509     if (chunk_state != CHUNK_ALLOCATED)
 510       ReportInvalidFree(old_ptr, chunk_state, stack);
 511     CHECK_NE(REAL(memcpy), (void*)0);
 512     uptr memcpy_size = Min(new_size, m->UsedSize());
 513     // If realloc() races with free(), we may start copying freed memory.
 514     // However, we will report racy double-free later anyway.
 515     REAL(memcpy)(new_ptr, old_ptr, memcpy_size);
 516     Deallocate(old_ptr, stack, FROM_MALLOC);
 517   }
 518   return new_ptr;
 519 }
 520
 521 // Assumes alloc_beg == allocator.GetBlockBegin(alloc_beg).
 522 static AsanChunk *GetAsanChunk(void *alloc_beg) {
 523   if (!alloc_beg) return 0;
 524   if (!allocator.FromPrimary(alloc_beg)) {
 525     uptr *meta = reinterpret_cast<uptr *>(allocator.GetMetaData(alloc_beg));
 526     AsanChunk *m = reinterpret_cast<AsanChunk *>(meta[1]);
 527     return m;
 528   }
 529   uptr *alloc_magic = reinterpret_cast<uptr *>(alloc_beg);
 530   if (alloc_magic[0] == kAllocBegMagic)
 531     return reinterpret_cast<AsanChunk *>(alloc_magic[1]);
 532   return reinterpret_cast<AsanChunk *>(alloc_beg);
 533 }
 534
 535 static AsanChunk *GetAsanChunkByAddr(uptr p) {
 536   void *alloc_beg = allocator.GetBlockBegin(reinterpret_cast<void *>(p));
 537   return GetAsanChunk(alloc_beg);
 538 }
 539
 540 // Allocator must be locked when this function is called.
 541 static AsanChunk *GetAsanChunkByAddrFastLocked(uptr p) {
 542   void *alloc_beg =
 543       allocator.GetBlockBeginFastLocked(reinterpret_cast<void *>(p));
 544   return GetAsanChunk(alloc_beg);
 545 }
 546
 547 static uptr AllocationSize(uptr p) {
 548   AsanChunk *m = GetAsanChunkByAddr(p);
 549   if (!m) return 0;
 550   if (m->chunk_state != CHUNK_ALLOCATED) return 0;
 551   if (m->Beg() != p) return 0;
 552   return m->UsedSize();
 553 }
 554
 555 // We have an address between two chunks, and we want to report just one.
 556 AsanChunk *ChooseChunk(uptr addr,
 557                        AsanChunk *left_chunk, AsanChunk *right_chunk) {
 558   // Prefer an allocated chunk over freed chunk and freed chunk
 559   // over available chunk.
 560   if (left_chunk->chunk_state != right_chunk->chunk_state) {
 561     if (left_chunk->chunk_state == CHUNK_ALLOCATED)
 562       return left_chunk;
 563     if (right_chunk->chunk_state == CHUNK_ALLOCATED)
 564       return right_chunk;
 565     if (left_chunk->chunk_state == CHUNK_QUARANTINE)
 566       return left_chunk;
 567     if (right_chunk->chunk_state == CHUNK_QUARANTINE)
 568       return right_chunk;
 569   }
 570   // Same chunk_state: choose based on offset.
 571   sptr l_offset = 0, r_offset = 0;
 572   CHECK(AsanChunkView(left_chunk).AddrIsAtRight(addr, 1, &l_offset));
 573   CHECK(AsanChunkView(right_chunk).AddrIsAtLeft(addr, 1, &r_offset));
 574   if (l_offset < r_offset)
 575     return left_chunk;
 576   return right_chunk;
 577 }
 578
 579 AsanChunkView FindHeapChunkByAddress(uptr addr) {
 580   AsanChunk *m1 = GetAsanChunkByAddr(addr);
 581   if (!m1) return AsanChunkView(m1);
 582   sptr offset = 0;
 583   if (AsanChunkView(m1).AddrIsAtLeft(addr, 1, &offset)) {
 584     // The address is in the chunk's left redzone, so maybe it is actually
 585     // a right buffer overflow from the other chunk to the left.
 586     // Search a bit to the left to see if there is another chunk.
 587     AsanChunk *m2 = 0;
 588     for (uptr l = 1; l < GetPageSizeCached(); l++) {
 589       m2 = GetAsanChunkByAddr(addr - l);
 590       if (m2 == m1) continue;  // Still the same chunk.
 591       break;
 592     }
 593     if (m2 && AsanChunkView(m2).AddrIsAtRight(addr, 1, &offset))
 594       m1 = ChooseChunk(addr, m2, m1);
 595   }
 596   return AsanChunkView(m1);
 597 }
 598
 599 void AsanThreadLocalMallocStorage::CommitBack() {
 600   AllocatorCache *ac = GetAllocatorCache(this);
 601   quarantine.Drain(GetQuarantineCache(this), QuarantineCallback(ac));
 602   allocator.SwallowCache(GetAllocatorCache(this));
 603 }
 604
 605 void PrintInternalAllocatorStats() {
 606   allocator.PrintStats();
 607 }
 608
 609 void *asan_memalign(uptr alignment, uptr size, StackTrace *stack,
 610                     AllocType alloc_type) {
 611   return Allocate(size, alignment, stack, alloc_type, true);
 612 }
 613
 614 void asan_free(void *ptr, StackTrace *stack, AllocType alloc_type) {
 615   Deallocate(ptr, stack, alloc_type);
 616 }
 617
 618 void *asan_malloc(uptr size, StackTrace *stack) {
 619   return Allocate(size, 8, stack, FROM_MALLOC, true);
 620 }
 621
 622 void *asan_calloc(uptr nmemb, uptr size, StackTrace *stack) {
 623   if (CallocShouldReturnNullDueToOverflow(size, nmemb))
 624     return AllocatorReturnNull();
 625   void *ptr = Allocate(nmemb * size, 8, stack, FROM_MALLOC, false);
 626   // If the memory comes from the secondary allocator no need to clear it
 627   // as it comes directly from mmap.
 628   if (ptr && allocator.FromPrimary(ptr))
 629     REAL(memset)(ptr, 0, nmemb * size);
 630   return ptr;
 631 }
 632
 633 void *asan_realloc(void *p, uptr size, StackTrace *stack) {
 634   if (p == 0)
 635     return Allocate(size, 8, stack, FROM_MALLOC, true);
 636   if (size == 0) {
 637     Deallocate(p, stack, FROM_MALLOC);
 638     return 0;
 639   }
 640   return Reallocate(p, size, stack);
 641 }
 642
 643 void *asan_valloc(uptr size, StackTrace *stack) {
 644   return Allocate(size, GetPageSizeCached(), stack, FROM_MALLOC, true);
 645 }
 646
 647 void *asan_pvalloc(uptr size, StackTrace *stack) {
 648   uptr PageSize = GetPageSizeCached();
 649   size = RoundUpTo(size, PageSize);
 650   if (size == 0) {
 651     // pvalloc(0) should allocate one page.
 652     size = PageSize;
 653   }
 654   return Allocate(size, PageSize, stack, FROM_MALLOC, true);
 655 }
 656
 657 int asan_posix_memalign(void **memptr, uptr alignment, uptr size,
 658                         StackTrace *stack) {
 659   void *ptr = Allocate(size, alignment, stack, FROM_MALLOC, true);
 660   CHECK(IsAligned((uptr)ptr, alignment));
 661   *memptr = ptr;
 662   return 0;
 663 }
 664
 665 uptr asan_malloc_usable_size(void *ptr, uptr pc, uptr bp) {
 666   if (ptr == 0) return 0;
 667   uptr usable_size = AllocationSize(reinterpret_cast<uptr>(ptr));
 668   if (flags()->check_malloc_usable_size && (usable_size == 0)) {
 669     GET_STACK_TRACE_FATAL(pc, bp);
 670     ReportMallocUsableSizeNotOwned((uptr)ptr, &stack);
 671   }
 672   return usable_size;
 673 }
 674
 675 uptr asan_mz_size(const void *ptr) {
 676   return AllocationSize(reinterpret_cast<uptr>(ptr));
 677 }
 678
 679 void asan_mz_force_lock() {
 680   allocator.ForceLock();
 681   fallback_mutex.Lock();
 682 }
 683
 684 void asan_mz_force_unlock() {
 685   fallback_mutex.Unlock();
 686   allocator.ForceUnlock();
 687 }
 688
 689 }  // namespace __asan
 690
 691 // --- Implementation of LSan-specific functions --- {{{1
 692 namespace __lsan {
 693 void LockAllocator() {
 694   __asan::allocator.ForceLock();
 695 }
 696
 697 void UnlockAllocator() {
 698   __asan::allocator.ForceUnlock();
 699 }
 700
 701 void GetAllocatorGlobalRange(uptr *begin, uptr *end) {
 702   *begin = (uptr)&__asan::allocator;
 703   *end = *begin + sizeof(__asan::allocator);
 704 }
 705
 706 uptr PointsIntoChunk(void* p) {
 707   uptr addr = reinterpret_cast<uptr>(p);
 708   __asan::AsanChunk *m = __asan::GetAsanChunkByAddrFastLocked(addr);
 709   if (!m) return 0;
 710   uptr chunk = m->Beg();
 711   if ((m->chunk_state == __asan::CHUNK_ALLOCATED) &&
 712       m->AddrIsInside(addr, /*locked_version=*/true))
 713     return chunk;
 714   return 0;
 715 }
 716
 717 uptr GetUserBegin(uptr chunk) {
 718   __asan::AsanChunk *m =
 719       __asan::GetAsanChunkByAddrFastLocked(chunk);
 720   CHECK(m);
 721   return m->Beg();
 722 }
 723
 724 LsanMetadata::LsanMetadata(uptr chunk) {
 725   metadata_ = reinterpret_cast<void *>(chunk - __asan::kChunkHeaderSize);
 726 }
 727
 728 bool LsanMetadata::allocated() const {
 729   __asan::AsanChunk *m = reinterpret_cast<__asan::AsanChunk *>(metadata_);
 730   return m->chunk_state == __asan::CHUNK_ALLOCATED;
 731 }
 732
 733 ChunkTag LsanMetadata::tag() const {
 734   __asan::AsanChunk *m = reinterpret_cast<__asan::AsanChunk *>(metadata_);
 735   return static_cast<ChunkTag>(m->lsan_tag);
 736 }
 737
 738 void LsanMetadata::set_tag(ChunkTag value) {
 739   __asan::AsanChunk *m = reinterpret_cast<__asan::AsanChunk *>(metadata_);
 740   m->lsan_tag = value;
 741 }
 742
 743 uptr LsanMetadata::requested_size() const {
 744   __asan::AsanChunk *m = reinterpret_cast<__asan::AsanChunk *>(metadata_);
 745   return m->UsedSize(/*locked_version=*/true);
 746 }
 747
 748 u32 LsanMetadata::stack_trace_id() const {
 749   __asan::AsanChunk *m = reinterpret_cast<__asan::AsanChunk *>(metadata_);
 750   return m->alloc_context_id;
 751 }
 752
 753 void ForEachChunk(ForEachChunkCallback callback, void *arg) {
 754   __asan::allocator.ForEachChunk(callback, arg);
 755 }
 756
 757 IgnoreObjectResult IgnoreObjectLocked(const void *p) {
 758   uptr addr = reinterpret_cast<uptr>(p);
 759   __asan::AsanChunk *m = __asan::GetAsanChunkByAddr(addr);
 760   if (!m) return kIgnoreObjectInvalid;
 761   if ((m->chunk_state == __asan::CHUNK_ALLOCATED) && m->AddrIsInside(addr)) {
 762     if (m->lsan_tag == kIgnored)
 763       return kIgnoreObjectAlreadyIgnored;
 764     m->lsan_tag = __lsan::kIgnored;
 765     return kIgnoreObjectSuccess;
 766   } else {
 767     return kIgnoreObjectInvalid;
 768   }
 769 }
 770 }  // namespace __lsan
 771
 772 // ---------------------- Interface ---------------- {{{1
 773 using namespace __asan;  // NOLINT
 774
 775 // ASan allocator doesn't reserve extra bytes, so normally we would
 776 // just return "size". We don't want to expose our redzone sizes, etc here.
 777 uptr __asan_get_estimated_allocated_size(uptr size) {
 778   return size;
 779 }
 780
 781 bool __asan_get_ownership(const void *p) {
 782   uptr ptr = reinterpret_cast<uptr>(p);
 783   return (AllocationSize(ptr) > 0);
 784 }
 785
 786 uptr __asan_get_allocated_size(const void *p) {
 787   if (p == 0) return 0;
 788   uptr ptr = reinterpret_cast<uptr>(p);
 789   uptr allocated_size = AllocationSize(ptr);
 790   // Die if p is not malloced or if it is already freed.
 791   if (allocated_size == 0) {
 792     GET_STACK_TRACE_FATAL_HERE;
 793     ReportAsanGetAllocatedSizeNotOwned(ptr, &stack);
 794   }
 795   return allocated_size;
 796 }
 797
 798 #if !SANITIZER_SUPPORTS_WEAK_HOOKS
 799 // Provide default (no-op) implementation of malloc hooks.
 800 extern "C" {
 801 SANITIZER_INTERFACE_ATTRIBUTE SANITIZER_WEAK_ATTRIBUTE
 802 void __asan_malloc_hook(void *ptr, uptr size) {
 803   (void)ptr;
 804   (void)size;
 805 }
 806 SANITIZER_INTERFACE_ATTRIBUTE SANITIZER_WEAK_ATTRIBUTE
 807 void __asan_free_hook(void *ptr) {
 808   (void)ptr;
 809 }
 810 }  // extern "C"
 811 #endif