921 lines · c
1//===-- sanitizer_allocator_primary64.h -------------------------*- C++ -*-===//2//3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.4// See https://llvm.org/LICENSE.txt for license information.5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception6//7//===----------------------------------------------------------------------===//8//9// Part of the Sanitizer Allocator.10//11//===----------------------------------------------------------------------===//12#ifndef SANITIZER_ALLOCATOR_H13#error This file must be included inside sanitizer_allocator.h14#endif15 16template<class SizeClassAllocator> struct SizeClassAllocator64LocalCache;17 18// SizeClassAllocator64 -- allocator for 64-bit address space.19// The template parameter Params is a class containing the actual parameters.20//21// Space: a portion of address space of kSpaceSize bytes starting at SpaceBeg.22// If kSpaceBeg is ~0 then SpaceBeg is chosen dynamically by mmap.23// Otherwise SpaceBeg=kSpaceBeg (fixed address).24// kSpaceSize is a power of two.25// At the beginning the entire space is mprotect-ed, then small parts of it26// are mapped on demand.27//28// Region: a part of Space dedicated to a single size class.29// There are kNumClasses Regions of equal size.30//31// UserChunk: a piece of memory returned to user.32// MetaChunk: kMetadataSize bytes of metadata associated with a UserChunk.33 34// FreeArray is an array free-d chunks (stored as 4-byte offsets)35//36// A Region looks like this:37// UserChunk1 ... UserChunkN <gap> MetaChunkN ... MetaChunk1 FreeArray38 39struct SizeClassAllocator64FlagMasks { // Bit masks.40 enum {41 kRandomShuffleChunks = 1,42 };43};44 45template <typename Allocator>46class MemoryMapper {47 public:48 typedef typename Allocator::CompactPtrT CompactPtrT;49 50 explicit MemoryMapper(const Allocator &allocator) : allocator_(allocator) {}51 52 bool GetAndResetStats(uptr &ranges, uptr &bytes) {53 ranges = released_ranges_count_;54 released_ranges_count_ = 0;55 bytes = released_bytes_;56 released_bytes_ = 0;57 return ranges != 0;58 }59 60 u64 *MapPackedCounterArrayBuffer(uptr count) {61 buffer_.clear();62 buffer_.resize(count);63 return buffer_.data();64 }65 66 // Releases [from, to) range of pages back to OS.67 void ReleasePageRangeToOS(uptr class_id, CompactPtrT from, CompactPtrT to) {68 const uptr region_base = allocator_.GetRegionBeginBySizeClass(class_id);69 const uptr from_page = allocator_.CompactPtrToPointer(region_base, from);70 const uptr to_page = allocator_.CompactPtrToPointer(region_base, to);71 ReleaseMemoryPagesToOS(from_page, to_page);72 released_ranges_count_++;73 released_bytes_ += to_page - from_page;74 }75 76 private:77 const Allocator &allocator_;78 uptr released_ranges_count_ = 0;79 uptr released_bytes_ = 0;80 InternalMmapVector<u64> buffer_;81};82 83template <class Params>84class SizeClassAllocator64 {85 public:86 using AddressSpaceView = typename Params::AddressSpaceView;87 static const uptr kSpaceBeg = Params::kSpaceBeg;88 static const uptr kSpaceSize = Params::kSpaceSize;89 static const uptr kMetadataSize = Params::kMetadataSize;90 typedef typename Params::SizeClassMap SizeClassMap;91 typedef typename Params::MapUnmapCallback MapUnmapCallback;92 93 static const bool kRandomShuffleChunks =94 Params::kFlags & SizeClassAllocator64FlagMasks::kRandomShuffleChunks;95 96 typedef SizeClassAllocator64<Params> ThisT;97 typedef SizeClassAllocator64LocalCache<ThisT> AllocatorCache;98 typedef MemoryMapper<ThisT> MemoryMapperT;99 100 // When we know the size class (the region base) we can represent a pointer101 // as a 4-byte integer (offset from the region start shifted right by 4).102 typedef u32 CompactPtrT;103 static const uptr kCompactPtrScale = 4;104 CompactPtrT PointerToCompactPtr(uptr base, uptr ptr) const {105 return static_cast<CompactPtrT>((ptr - base) >> kCompactPtrScale);106 }107 uptr CompactPtrToPointer(uptr base, CompactPtrT ptr32) const {108 return base + (static_cast<uptr>(ptr32) << kCompactPtrScale);109 }110 111 // If heap_start is nonzero, assumes kSpaceSize bytes are already mapped R/W112 // at heap_start and places the heap there. This mode requires kSpaceBeg ==113 // ~(uptr)0.114 void Init(s32 release_to_os_interval_ms, uptr heap_start = 0) {115 uptr TotalSpaceSize = kSpaceSize + AdditionalSize();116 117 uptr MaxAddr = GetMaxUserVirtualAddress();118 // VReport does not call the sanitizer allocator.119 VReport(3, "Max user virtual address: 0x%zx\n", MaxAddr);120 VReport(3, "Total space size for primary allocator: 0x%zx\n",121 TotalSpaceSize);122 // TODO: revise the check if we ever configure sanitizers to deliberately123 // map beyond the 2**48 barrier (note that Linux pretends the VMA is124 // limited to 48-bit for backwards compatibility, but allows apps to125 // explicitly specify an address beyond that).126 if (heap_start + TotalSpaceSize >= MaxAddr) {127 // We can't easily adjust the requested heap size, because kSpaceSize is128 // const (for optimization) and used throughout the code.129 VReport(0, "Error: heap size %zx exceeds max user virtual address %zx\n",130 TotalSpaceSize, MaxAddr);131 VReport(132 0, "Try using a kernel that allows a larger virtual address space\n");133 }134 PremappedHeap = heap_start != 0;135 if (PremappedHeap) {136 CHECK(!kUsingConstantSpaceBeg);137 NonConstSpaceBeg = heap_start;138 uptr RegionInfoSize = AdditionalSize();139 RegionInfoSpace =140 address_range.Init(RegionInfoSize, PrimaryAllocatorName);141 CHECK_NE(RegionInfoSpace, ~(uptr)0);142 CHECK_EQ(RegionInfoSpace,143 address_range.MapOrDie(RegionInfoSpace, RegionInfoSize,144 "SizeClassAllocator: region info"));145 MapUnmapCallback().OnMap(RegionInfoSpace, RegionInfoSize);146 } else {147 if (kUsingConstantSpaceBeg) {148 CHECK(IsAligned(kSpaceBeg, SizeClassMap::kMaxSize));149 CHECK_EQ(kSpaceBeg,150 address_range.Init(TotalSpaceSize, PrimaryAllocatorName,151 kSpaceBeg));152 } else {153 // Combined allocator expects that an 2^N allocation is always aligned154 // to 2^N. For this to work, the start of the space needs to be aligned155 // as high as the largest size class (which also needs to be a power of156 // 2).157 NonConstSpaceBeg = address_range.InitAligned(158 TotalSpaceSize, SizeClassMap::kMaxSize, PrimaryAllocatorName);159 CHECK_NE(NonConstSpaceBeg, ~(uptr)0);160 }161 RegionInfoSpace = SpaceEnd();162 MapWithCallbackOrDie(RegionInfoSpace, AdditionalSize(),163 "SizeClassAllocator: region info");164 }165 SetReleaseToOSIntervalMs(release_to_os_interval_ms);166 // Check that the RegionInfo array is aligned on the CacheLine size.167 DCHECK_EQ(RegionInfoSpace % kCacheLineSize, 0);168 }169 170 s32 ReleaseToOSIntervalMs() const {171 return atomic_load(&release_to_os_interval_ms_, memory_order_relaxed);172 }173 174 void SetReleaseToOSIntervalMs(s32 release_to_os_interval_ms) {175 atomic_store(&release_to_os_interval_ms_, release_to_os_interval_ms,176 memory_order_relaxed);177 }178 179 void ForceReleaseToOS() {180 MemoryMapperT memory_mapper(*this);181 for (uptr class_id = 1; class_id < kNumClasses; class_id++) {182 Lock l(&GetRegionInfo(class_id)->mutex);183 MaybeReleaseToOS(&memory_mapper, class_id, true /*force*/);184 }185 }186 187 static bool CanAllocate(uptr size, uptr alignment) {188 return size <= SizeClassMap::kMaxSize &&189 alignment <= SizeClassMap::kMaxSize;190 }191 192 NOINLINE void ReturnToAllocator(MemoryMapperT *memory_mapper,193 AllocatorStats *stat, uptr class_id,194 const CompactPtrT *chunks, uptr n_chunks) {195 RegionInfo *region = GetRegionInfo(class_id);196 uptr region_beg = GetRegionBeginBySizeClass(class_id);197 CompactPtrT *free_array = GetFreeArray(region_beg);198 199 Lock l(®ion->mutex);200 uptr old_num_chunks = region->num_freed_chunks;201 uptr new_num_freed_chunks = old_num_chunks + n_chunks;202 // Failure to allocate free array space while releasing memory is non203 // recoverable.204 if (UNLIKELY(!EnsureFreeArraySpace(region, region_beg,205 new_num_freed_chunks))) {206 Report(207 "FATAL: Internal error: %s's allocator exhausted the free list "208 "space for size class %zu (%zu bytes).\n",209 SanitizerToolName, class_id, ClassIdToSize(class_id));210 Die();211 }212 for (uptr i = 0; i < n_chunks; i++)213 free_array[old_num_chunks + i] = chunks[i];214 region->num_freed_chunks = new_num_freed_chunks;215 region->stats.n_freed += n_chunks;216 217 MaybeReleaseToOS(memory_mapper, class_id, false /*force*/);218 }219 220 NOINLINE bool GetFromAllocator(AllocatorStats *stat, uptr class_id,221 CompactPtrT *chunks, uptr n_chunks) {222 RegionInfo *region = GetRegionInfo(class_id);223 uptr region_beg = GetRegionBeginBySizeClass(class_id);224 CompactPtrT *free_array = GetFreeArray(region_beg);225 226 Lock l(®ion->mutex);227#if SANITIZER_WINDOWS228 /* On Windows unmapping of memory during __sanitizer_purge_allocator is229 explicit and immediate, so unmapped regions must be explicitly mapped back230 in when they are accessed again. */231 if (region->rtoi.last_released_bytes > 0) {232 MmapFixedOrDie(region_beg, region->mapped_user,233 "SizeClassAllocator: region data");234 region->rtoi.n_freed_at_last_release = 0;235 region->rtoi.last_released_bytes = 0;236 }237#endif238 if (UNLIKELY(region->num_freed_chunks < n_chunks)) {239 if (UNLIKELY(!PopulateFreeArray(stat, class_id, region,240 n_chunks - region->num_freed_chunks)))241 return false;242 CHECK_GE(region->num_freed_chunks, n_chunks);243 }244 region->num_freed_chunks -= n_chunks;245 uptr base_idx = region->num_freed_chunks;246 for (uptr i = 0; i < n_chunks; i++)247 chunks[i] = free_array[base_idx + i];248 region->stats.n_allocated += n_chunks;249 return true;250 }251 252 bool PointerIsMine(const void *p) const {253 uptr P = reinterpret_cast<uptr>(p);254 if (kUsingConstantSpaceBeg && (kSpaceBeg % kSpaceSize) == 0)255 return P / kSpaceSize == kSpaceBeg / kSpaceSize;256 return P >= SpaceBeg() && P < SpaceEnd();257 }258 259 uptr GetRegionBegin(const void *p) {260 if (kUsingConstantSpaceBeg)261 return reinterpret_cast<uptr>(p) & ~(kRegionSize - 1);262 uptr space_beg = SpaceBeg();263 return ((reinterpret_cast<uptr>(p) - space_beg) & ~(kRegionSize - 1)) +264 space_beg;265 }266 267 uptr GetRegionBeginBySizeClass(uptr class_id) const {268 return SpaceBeg() + kRegionSize * class_id;269 }270 271 uptr GetSizeClass(const void *p) {272 if (kUsingConstantSpaceBeg && (kSpaceBeg % kSpaceSize) == 0)273 return ((reinterpret_cast<uptr>(p)) / kRegionSize) % kNumClassesRounded;274 return ((reinterpret_cast<uptr>(p) - SpaceBeg()) / kRegionSize) %275 kNumClassesRounded;276 }277 278 void *GetBlockBegin(const void *p) {279 uptr class_id = GetSizeClass(p);280 if (class_id >= kNumClasses) return nullptr;281 uptr size = ClassIdToSize(class_id);282 if (!size) return nullptr;283 uptr chunk_idx = GetChunkIdx((uptr)p, size);284 uptr reg_beg = GetRegionBegin(p);285 uptr beg = chunk_idx * size;286 uptr next_beg = beg + size;287 const RegionInfo *region = AddressSpaceView::Load(GetRegionInfo(class_id));288 if (region->mapped_user >= next_beg)289 return reinterpret_cast<void*>(reg_beg + beg);290 return nullptr;291 }292 293 uptr GetActuallyAllocatedSize(void *p) {294 CHECK(PointerIsMine(p));295 return ClassIdToSize(GetSizeClass(p));296 }297 298 static uptr ClassID(uptr size) { return SizeClassMap::ClassID(size); }299 300 void *GetMetaData(const void *p) {301 CHECK(kMetadataSize);302 uptr class_id = GetSizeClass(p);303 uptr size = ClassIdToSize(class_id);304 if (!size)305 return nullptr;306 uptr chunk_idx = GetChunkIdx(reinterpret_cast<uptr>(p), size);307 uptr region_beg = GetRegionBeginBySizeClass(class_id);308 return reinterpret_cast<void *>(GetMetadataEnd(region_beg) -309 (1 + chunk_idx) * kMetadataSize);310 }311 312 uptr TotalMemoryUsed() {313 uptr res = 0;314 for (uptr i = 0; i < kNumClasses; i++)315 res += GetRegionInfo(i)->allocated_user;316 return res;317 }318 319 // Test-only.320 void TestOnlyUnmap() {321 UnmapWithCallbackOrDie((uptr)address_range.base(), address_range.size());322 }323 324 static void FillMemoryProfile(uptr start, uptr rss, bool file, uptr *stats) {325 for (uptr class_id = 0; class_id < kNumClasses; class_id++)326 if (stats[class_id] == start)327 stats[class_id] = rss;328 }329 330 void PrintStats(uptr class_id, uptr rss) {331 RegionInfo *region = GetRegionInfo(class_id);332 if (region->mapped_user == 0) return;333 uptr in_use = region->stats.n_allocated - region->stats.n_freed;334 uptr avail_chunks = region->allocated_user / ClassIdToSize(class_id);335 Printf(336 "%s %02zd (%6zd): mapped: %6zdK allocs: %7zd frees: %7zd inuse: %6zd "337 "num_freed_chunks %7zd avail: %6zd rss: %6zdK releases: %6zd "338 "last released: %6lldK region: %p\n",339 region->exhausted ? "F" : " ", class_id, ClassIdToSize(class_id),340 region->mapped_user >> 10, region->stats.n_allocated,341 region->stats.n_freed, in_use, region->num_freed_chunks, avail_chunks,342 rss >> 10, region->rtoi.num_releases,343 region->rtoi.last_released_bytes >> 10,344 (void *)(SpaceBeg() + kRegionSize * class_id));345 }346 347 void PrintStats() {348 uptr rss_stats[kNumClasses];349 for (uptr class_id = 0; class_id < kNumClasses; class_id++)350 rss_stats[class_id] = SpaceBeg() + kRegionSize * class_id;351 GetMemoryProfile(FillMemoryProfile, rss_stats);352 353 uptr total_mapped = 0;354 uptr total_rss = 0;355 uptr n_allocated = 0;356 uptr n_freed = 0;357 for (uptr class_id = 1; class_id < kNumClasses; class_id++) {358 RegionInfo *region = GetRegionInfo(class_id);359 if (region->mapped_user != 0) {360 total_mapped += region->mapped_user;361 total_rss += rss_stats[class_id];362 }363 n_allocated += region->stats.n_allocated;364 n_freed += region->stats.n_freed;365 }366 367 Printf("Stats: SizeClassAllocator64: %zdM mapped (%zdM rss) in "368 "%zd allocations; remains %zd\n", total_mapped >> 20,369 total_rss >> 20, n_allocated, n_allocated - n_freed);370 for (uptr class_id = 1; class_id < kNumClasses; class_id++)371 PrintStats(class_id, rss_stats[class_id]);372 }373 374 // ForceLock() and ForceUnlock() are needed to implement Darwin malloc zone375 // introspection API.376 void ForceLock() SANITIZER_NO_THREAD_SAFETY_ANALYSIS {377 for (uptr i = 0; i < kNumClasses; i++) {378 GetRegionInfo(i)->mutex.Lock();379 }380 }381 382 void ForceUnlock() SANITIZER_NO_THREAD_SAFETY_ANALYSIS {383 for (int i = (int)kNumClasses - 1; i >= 0; i--) {384 GetRegionInfo(i)->mutex.Unlock();385 }386 }387 388 // Iterate over all existing chunks.389 // The allocator must be locked when calling this function.390 void ForEachChunk(ForEachChunkCallback callback, void *arg) {391 for (uptr class_id = 1; class_id < kNumClasses; class_id++) {392 RegionInfo *region = GetRegionInfo(class_id);393 uptr chunk_size = ClassIdToSize(class_id);394 uptr region_beg = SpaceBeg() + class_id * kRegionSize;395 uptr region_allocated_user_size =396 AddressSpaceView::Load(region)->allocated_user;397 for (uptr chunk = region_beg;398 chunk < region_beg + region_allocated_user_size;399 chunk += chunk_size) {400 // Too slow: CHECK_EQ((void *)chunk, GetBlockBegin((void *)chunk));401 callback(chunk, arg);402 }403 }404 }405 406 static uptr ClassIdToSize(uptr class_id) {407 return SizeClassMap::Size(class_id);408 }409 410 static uptr AdditionalSize() {411 return RoundUpTo(sizeof(RegionInfo) * kNumClassesRounded,412 GetPageSizeCached());413 }414 415 typedef SizeClassMap SizeClassMapT;416 static const uptr kNumClasses = SizeClassMap::kNumClasses;417 static const uptr kNumClassesRounded = SizeClassMap::kNumClassesRounded;418 419 // A packed array of counters. Each counter occupies 2^n bits, enough to store420 // counter's max_value. Ctor will try to allocate the required buffer via421 // mapper->MapPackedCounterArrayBuffer and the caller is expected to check422 // whether the initialization was successful by checking IsAllocated() result.423 // For the performance sake, none of the accessors check the validity of the424 // arguments, it is assumed that index is always in [0, n) range and the value425 // is not incremented past max_value.426 class PackedCounterArray {427 public:428 template <typename MemoryMapper>429 PackedCounterArray(u64 num_counters, u64 max_value, MemoryMapper *mapper)430 : n(num_counters) {431 CHECK_GT(num_counters, 0);432 CHECK_GT(max_value, 0);433 constexpr u64 kMaxCounterBits = sizeof(*buffer) * 8ULL;434 // Rounding counter storage size up to the power of two allows for using435 // bit shifts calculating particular counter's index and offset.436 uptr counter_size_bits =437 RoundUpToPowerOfTwo(MostSignificantSetBitIndex(max_value) + 1);438 CHECK_LE(counter_size_bits, kMaxCounterBits);439 counter_size_bits_log = Log2(counter_size_bits);440 counter_mask = ~0ULL >> (kMaxCounterBits - counter_size_bits);441 442 uptr packing_ratio = kMaxCounterBits >> counter_size_bits_log;443 CHECK_GT(packing_ratio, 0);444 packing_ratio_log = Log2(packing_ratio);445 bit_offset_mask = packing_ratio - 1;446 447 buffer = mapper->MapPackedCounterArrayBuffer(448 RoundUpTo(n, 1ULL << packing_ratio_log) >> packing_ratio_log);449 }450 451 bool IsAllocated() const {452 return !!buffer;453 }454 455 u64 GetCount() const {456 return n;457 }458 459 uptr Get(uptr i) const {460 DCHECK_LT(i, n);461 uptr index = i >> packing_ratio_log;462 uptr bit_offset = (i & bit_offset_mask) << counter_size_bits_log;463 return (buffer[index] >> bit_offset) & counter_mask;464 }465 466 void Inc(uptr i) const {467 DCHECK_LT(Get(i), counter_mask);468 uptr index = i >> packing_ratio_log;469 uptr bit_offset = (i & bit_offset_mask) << counter_size_bits_log;470 buffer[index] += 1ULL << bit_offset;471 }472 473 void IncRange(uptr from, uptr to) const {474 DCHECK_LE(from, to);475 for (uptr i = from; i <= to; i++)476 Inc(i);477 }478 479 private:480 const u64 n;481 u64 counter_size_bits_log;482 u64 counter_mask;483 u64 packing_ratio_log;484 u64 bit_offset_mask;485 u64* buffer;486 };487 488 template <class MemoryMapperT>489 class FreePagesRangeTracker {490 public:491 FreePagesRangeTracker(MemoryMapperT *mapper, uptr class_id)492 : memory_mapper(mapper),493 class_id(class_id),494 page_size_scaled_log(Log2(GetPageSizeCached() >> kCompactPtrScale)) {}495 496 void NextPage(bool freed) {497 if (freed) {498 if (!in_the_range) {499 current_range_start_page = current_page;500 in_the_range = true;501 }502 } else {503 CloseOpenedRange();504 }505 current_page++;506 }507 508 void Done() {509 CloseOpenedRange();510 }511 512 private:513 void CloseOpenedRange() {514 if (in_the_range) {515 memory_mapper->ReleasePageRangeToOS(516 class_id, current_range_start_page << page_size_scaled_log,517 current_page << page_size_scaled_log);518 in_the_range = false;519 }520 }521 522 MemoryMapperT *const memory_mapper = nullptr;523 const uptr class_id = 0;524 const uptr page_size_scaled_log = 0;525 bool in_the_range = false;526 uptr current_page = 0;527 uptr current_range_start_page = 0;528 };529 530 // Iterates over the free_array to identify memory pages containing freed531 // chunks only and returns these pages back to OS.532 // allocated_pages_count is the total number of pages allocated for the533 // current bucket.534 template <typename MemoryMapper>535 static void ReleaseFreeMemoryToOS(CompactPtrT *free_array,536 uptr free_array_count, uptr chunk_size,537 uptr allocated_pages_count,538 MemoryMapper *memory_mapper,539 uptr class_id) {540 const uptr page_size = GetPageSizeCached();541 542 // Figure out the number of chunks per page and whether we can take a fast543 // path (the number of chunks per page is the same for all pages).544 uptr full_pages_chunk_count_max;545 bool same_chunk_count_per_page;546 if (chunk_size <= page_size && page_size % chunk_size == 0) {547 // Same number of chunks per page, no cross overs.548 full_pages_chunk_count_max = page_size / chunk_size;549 same_chunk_count_per_page = true;550 } else if (chunk_size <= page_size && page_size % chunk_size != 0 &&551 chunk_size % (page_size % chunk_size) == 0) {552 // Some chunks are crossing page boundaries, which means that the page553 // contains one or two partial chunks, but all pages contain the same554 // number of chunks.555 full_pages_chunk_count_max = page_size / chunk_size + 1;556 same_chunk_count_per_page = true;557 } else if (chunk_size <= page_size) {558 // Some chunks are crossing page boundaries, which means that the page559 // contains one or two partial chunks.560 full_pages_chunk_count_max = page_size / chunk_size + 2;561 same_chunk_count_per_page = false;562 } else if (chunk_size > page_size && chunk_size % page_size == 0) {563 // One chunk covers multiple pages, no cross overs.564 full_pages_chunk_count_max = 1;565 same_chunk_count_per_page = true;566 } else if (chunk_size > page_size) {567 // One chunk covers multiple pages, Some chunks are crossing page568 // boundaries. Some pages contain one chunk, some contain two.569 full_pages_chunk_count_max = 2;570 same_chunk_count_per_page = false;571 } else {572 UNREACHABLE("All chunk_size/page_size ratios must be handled.");573 }574 575 PackedCounterArray counters(allocated_pages_count,576 full_pages_chunk_count_max, memory_mapper);577 if (!counters.IsAllocated())578 return;579 580 const uptr chunk_size_scaled = chunk_size >> kCompactPtrScale;581 const uptr page_size_scaled = page_size >> kCompactPtrScale;582 const uptr page_size_scaled_log = Log2(page_size_scaled);583 584 // Iterate over free chunks and count how many free chunks affect each585 // allocated page.586 if (chunk_size <= page_size && page_size % chunk_size == 0) {587 // Each chunk affects one page only.588 for (uptr i = 0; i < free_array_count; i++)589 counters.Inc(free_array[i] >> page_size_scaled_log);590 } else {591 // In all other cases chunks might affect more than one page.592 for (uptr i = 0; i < free_array_count; i++) {593 counters.IncRange(594 free_array[i] >> page_size_scaled_log,595 (free_array[i] + chunk_size_scaled - 1) >> page_size_scaled_log);596 }597 }598 599 // Iterate over pages detecting ranges of pages with chunk counters equal600 // to the expected number of chunks for the particular page.601 FreePagesRangeTracker<MemoryMapper> range_tracker(memory_mapper, class_id);602 if (same_chunk_count_per_page) {603 // Fast path, every page has the same number of chunks affecting it.604 for (uptr i = 0; i < counters.GetCount(); i++)605 range_tracker.NextPage(counters.Get(i) == full_pages_chunk_count_max);606 } else {607 // Show path, go through the pages keeping count how many chunks affect608 // each page.609 const uptr pn =610 chunk_size < page_size ? page_size_scaled / chunk_size_scaled : 1;611 const uptr pnc = pn * chunk_size_scaled;612 // The idea is to increment the current page pointer by the first chunk613 // size, middle portion size (the portion of the page covered by chunks614 // except the first and the last one) and then the last chunk size, adding615 // up the number of chunks on the current page and checking on every step616 // whether the page boundary was crossed.617 uptr prev_page_boundary = 0;618 uptr current_boundary = 0;619 for (uptr i = 0; i < counters.GetCount(); i++) {620 uptr page_boundary = prev_page_boundary + page_size_scaled;621 uptr chunks_per_page = pn;622 if (current_boundary < page_boundary) {623 if (current_boundary > prev_page_boundary)624 chunks_per_page++;625 current_boundary += pnc;626 if (current_boundary < page_boundary) {627 chunks_per_page++;628 current_boundary += chunk_size_scaled;629 }630 }631 prev_page_boundary = page_boundary;632 633 range_tracker.NextPage(counters.Get(i) == chunks_per_page);634 }635 }636 range_tracker.Done();637 }638 639 private:640 friend class MemoryMapper<ThisT>;641 642 ReservedAddressRange address_range;643 644 static const uptr kRegionSize = kSpaceSize / kNumClassesRounded;645 // FreeArray is the array of free-d chunks (stored as 4-byte offsets).646 // In the worst case it may require kRegionSize/SizeClassMap::kMinSize647 // elements, but in reality this will not happen. For simplicity we648 // dedicate 1/8 of the region's virtual space to FreeArray.649 static const uptr kFreeArraySize = kRegionSize / 8;650 651 static const bool kUsingConstantSpaceBeg = kSpaceBeg != ~(uptr)0;652 uptr NonConstSpaceBeg;653 uptr SpaceBeg() const {654 return kUsingConstantSpaceBeg ? kSpaceBeg : NonConstSpaceBeg;655 }656 uptr SpaceEnd() const { return SpaceBeg() + kSpaceSize; }657 // kRegionSize should be able to satisfy the largest size class.658 static_assert(kRegionSize >= SizeClassMap::kMaxSize,659 "Region size exceed largest size");660 // kRegionSize must be <= 2^36, see CompactPtrT.661 COMPILER_CHECK((kRegionSize) <=662 (1ULL << (sizeof(CompactPtrT) * 8 + kCompactPtrScale)));663 // Call mmap for user memory with at least this size.664 static const uptr kUserMapSize = 1 << 18;665 // Call mmap for metadata memory with at least this size.666 static const uptr kMetaMapSize = 1 << 16;667 // Call mmap for free array memory with at least this size.668 static const uptr kFreeArrayMapSize = 1 << 18;669 670 atomic_sint32_t release_to_os_interval_ms_;671 672 uptr RegionInfoSpace;673 674 // True if the user has already mapped the entire heap R/W.675 bool PremappedHeap;676 677 struct Stats {678 uptr n_allocated;679 uptr n_freed;680 };681 682 struct ReleaseToOsInfo {683 uptr n_freed_at_last_release;684 uptr num_releases;685 u64 last_release_at_ns;686 u64 last_released_bytes;687 };688 689 struct alignas(SANITIZER_CACHE_LINE_SIZE) RegionInfo {690 Mutex mutex;691 uptr num_freed_chunks; // Number of elements in the freearray.692 uptr mapped_free_array; // Bytes mapped for freearray.693 uptr allocated_user; // Bytes allocated for user memory.694 uptr allocated_meta; // Bytes allocated for metadata.695 uptr mapped_user; // Bytes mapped for user memory.696 uptr mapped_meta; // Bytes mapped for metadata.697 u32 rand_state; // Seed for random shuffle, used if kRandomShuffleChunks.698 bool exhausted; // Whether region is out of space for new chunks.699 Stats stats;700 ReleaseToOsInfo rtoi;701 };702 COMPILER_CHECK(sizeof(RegionInfo) % kCacheLineSize == 0);703 704 RegionInfo *GetRegionInfo(uptr class_id) const {705 DCHECK_LT(class_id, kNumClasses);706 RegionInfo *regions = reinterpret_cast<RegionInfo *>(RegionInfoSpace);707 return ®ions[class_id];708 }709 710 uptr GetMetadataEnd(uptr region_beg) const {711 return region_beg + kRegionSize - kFreeArraySize;712 }713 714 uptr GetChunkIdx(uptr chunk, uptr size) const {715 if (!kUsingConstantSpaceBeg)716 chunk -= SpaceBeg();717 718 uptr offset = chunk % kRegionSize;719 // Here we divide by a non-constant. This is costly.720 // size always fits into 32-bits. If the offset fits too, use 32-bit div.721 if (offset >> (SANITIZER_WORDSIZE / 2))722 return offset / size;723 return (u32)offset / (u32)size;724 }725 726 CompactPtrT *GetFreeArray(uptr region_beg) const {727 return reinterpret_cast<CompactPtrT *>(GetMetadataEnd(region_beg));728 }729 730 bool MapWithCallback(uptr beg, uptr size, const char *name) {731 if (PremappedHeap)732 return beg >= NonConstSpaceBeg &&733 beg + size <= NonConstSpaceBeg + kSpaceSize;734 uptr mapped = address_range.Map(beg, size, name);735 if (UNLIKELY(!mapped))736 return false;737 CHECK_EQ(beg, mapped);738 MapUnmapCallback().OnMap(beg, size);739 return true;740 }741 742 void MapWithCallbackOrDie(uptr beg, uptr size, const char *name) {743 if (PremappedHeap) {744 CHECK_GE(beg, NonConstSpaceBeg);745 CHECK_LE(beg + size, NonConstSpaceBeg + kSpaceSize);746 return;747 }748 CHECK_EQ(beg, address_range.MapOrDie(beg, size, name));749 MapUnmapCallback().OnMap(beg, size);750 }751 752 void UnmapWithCallbackOrDie(uptr beg, uptr size) {753 if (PremappedHeap)754 return;755 MapUnmapCallback().OnUnmap(beg, size);756 address_range.Unmap(beg, size);757 }758 759 bool EnsureFreeArraySpace(RegionInfo *region, uptr region_beg,760 uptr num_freed_chunks) {761 uptr needed_space = num_freed_chunks * sizeof(CompactPtrT);762 if (region->mapped_free_array < needed_space) {763 uptr new_mapped_free_array = RoundUpTo(needed_space, kFreeArrayMapSize);764 CHECK_LE(new_mapped_free_array, kFreeArraySize);765 uptr current_map_end = reinterpret_cast<uptr>(GetFreeArray(region_beg)) +766 region->mapped_free_array;767 uptr new_map_size = new_mapped_free_array - region->mapped_free_array;768 if (UNLIKELY(!MapWithCallback(current_map_end, new_map_size,769 "SizeClassAllocator: freearray")))770 return false;771 region->mapped_free_array = new_mapped_free_array;772 }773 return true;774 }775 776 // Check whether this size class is exhausted.777 bool IsRegionExhausted(RegionInfo *region, uptr class_id,778 uptr additional_map_size) {779 if (LIKELY(region->mapped_user + region->mapped_meta +780 additional_map_size <= kRegionSize - kFreeArraySize))781 return false;782 if (!region->exhausted) {783 region->exhausted = true;784 Printf("%s: Out of memory. ", SanitizerToolName);785 Printf(786 "The process has exhausted %zu MB for size class %zu (%zu bytes).\n",787 kRegionSize >> 20, class_id, ClassIdToSize(class_id));788 }789 return true;790 }791 792 NOINLINE bool PopulateFreeArray(AllocatorStats *stat, uptr class_id,793 RegionInfo *region, uptr requested_count) {794 // region->mutex is held.795 const uptr region_beg = GetRegionBeginBySizeClass(class_id);796 const uptr size = ClassIdToSize(class_id);797 798 const uptr total_user_bytes =799 region->allocated_user + requested_count * size;800 // Map more space for chunks, if necessary.801 if (LIKELY(total_user_bytes > region->mapped_user)) {802 if (UNLIKELY(region->mapped_user == 0)) {803 if (!kUsingConstantSpaceBeg && kRandomShuffleChunks)804 // The random state is initialized from ASLR.805 region->rand_state = static_cast<u32>(region_beg >> 12);806 // Postpone the first release to OS attempt for ReleaseToOSIntervalMs,807 // preventing just allocated memory from being released sooner than808 // necessary and also preventing extraneous ReleaseMemoryPagesToOS calls809 // for short lived processes.810 // Do it only when the feature is turned on, to avoid a potentially811 // extraneous syscall.812 if (ReleaseToOSIntervalMs() >= 0)813 region->rtoi.last_release_at_ns = MonotonicNanoTime();814 }815 // Do the mmap for the user memory.816 const uptr user_map_size =817 RoundUpTo(total_user_bytes - region->mapped_user, kUserMapSize);818 if (UNLIKELY(IsRegionExhausted(region, class_id, user_map_size)))819 return false;820 if (UNLIKELY(!MapWithCallback(region_beg + region->mapped_user,821 user_map_size,822 "SizeClassAllocator: region data")))823 return false;824 stat->Add(AllocatorStatMapped, user_map_size);825 region->mapped_user += user_map_size;826 }827 const uptr new_chunks_count =828 (region->mapped_user - region->allocated_user) / size;829 830 if (kMetadataSize) {831 // Calculate the required space for metadata.832 const uptr total_meta_bytes =833 region->allocated_meta + new_chunks_count * kMetadataSize;834 const uptr meta_map_size = (total_meta_bytes > region->mapped_meta) ?835 RoundUpTo(total_meta_bytes - region->mapped_meta, kMetaMapSize) : 0;836 // Map more space for metadata, if necessary.837 if (meta_map_size) {838 if (UNLIKELY(IsRegionExhausted(region, class_id, meta_map_size)))839 return false;840 if (UNLIKELY(!MapWithCallback(841 GetMetadataEnd(region_beg) - region->mapped_meta - meta_map_size,842 meta_map_size, "SizeClassAllocator: region metadata")))843 return false;844 region->mapped_meta += meta_map_size;845 }846 }847 848 // If necessary, allocate more space for the free array and populate it with849 // newly allocated chunks.850 const uptr total_freed_chunks = region->num_freed_chunks + new_chunks_count;851 if (UNLIKELY(!EnsureFreeArraySpace(region, region_beg, total_freed_chunks)))852 return false;853 CompactPtrT *free_array = GetFreeArray(region_beg);854 for (uptr i = 0, chunk = region->allocated_user; i < new_chunks_count;855 i++, chunk += size)856 free_array[total_freed_chunks - 1 - i] = PointerToCompactPtr(0, chunk);857 if (kRandomShuffleChunks)858 RandomShuffle(&free_array[region->num_freed_chunks], new_chunks_count,859 ®ion->rand_state);860 861 // All necessary memory is mapped and now it is safe to advance all862 // 'allocated_*' counters.863 region->num_freed_chunks += new_chunks_count;864 region->allocated_user += new_chunks_count * size;865 CHECK_LE(region->allocated_user, region->mapped_user);866 region->allocated_meta += new_chunks_count * kMetadataSize;867 CHECK_LE(region->allocated_meta, region->mapped_meta);868 region->exhausted = false;869 870 // TODO(alekseyshl): Consider bumping last_release_at_ns here to prevent871 // MaybeReleaseToOS from releasing just allocated pages or protect these872 // not yet used chunks some other way.873 874 return true;875 }876 877 // Attempts to release RAM occupied by freed chunks back to OS. The region is878 // expected to be locked.879 //880 // TODO(morehouse): Support a callback on memory release so HWASan can release881 // aliases as well.882 void MaybeReleaseToOS(MemoryMapperT *memory_mapper, uptr class_id,883 bool force) {884 RegionInfo *region = GetRegionInfo(class_id);885 const uptr chunk_size = ClassIdToSize(class_id);886 const uptr page_size = GetPageSizeCached();887 888 uptr n = region->num_freed_chunks;889 if (n * chunk_size < page_size)890 return; // No chance to release anything.891 if ((region->stats.n_freed -892 region->rtoi.n_freed_at_last_release) * chunk_size < page_size) {893 return; // Nothing new to release.894 }895 896 if (!force) {897 s32 interval_ms = ReleaseToOSIntervalMs();898 if (interval_ms < 0)899 return;900 901 if (region->rtoi.last_release_at_ns + interval_ms * 1000000ULL >902 MonotonicNanoTime()) {903 return; // Memory was returned recently.904 }905 }906 907 ReleaseFreeMemoryToOS(908 GetFreeArray(GetRegionBeginBySizeClass(class_id)), n, chunk_size,909 RoundUpTo(region->allocated_user, page_size) / page_size, memory_mapper,910 class_id);911 912 uptr ranges, bytes;913 if (memory_mapper->GetAndResetStats(ranges, bytes)) {914 region->rtoi.n_freed_at_last_release = region->stats.n_freed;915 region->rtoi.num_releases += ranges;916 region->rtoi.last_released_bytes = bytes;917 }918 region->rtoi.last_release_at_ns = MonotonicNanoTime();919 }920};921