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