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-exception 6// 7//===----------------------------------------------------------------------===// 8// 9// Part of the Sanitizer Allocator. 10// 11//===----------------------------------------------------------------------===// 12#ifndef SANITIZER_ALLOCATOR_H 13#error This file must be included inside sanitizer_allocator.h 14#endif 15 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 my 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 it 26// 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 FreeArray 38 39struct SizeClassAllocator64FlagMasks { // Bit masks. 40 enum { 41 kRandomShuffleChunks = 1, 42 }; 43}; 44 45template <class Params> 46class SizeClassAllocator64 { 47 public: 48 using AddressSpaceView = typename Params::AddressSpaceView; 49 static const uptr kSpaceBeg = Params::kSpaceBeg; 50 static const uptr kSpaceSize = Params::kSpaceSize; 51 static const uptr kMetadataSize = Params::kMetadataSize; 52 typedef typename Params::SizeClassMap SizeClassMap; 53 typedef typename Params::MapUnmapCallback MapUnmapCallback; 54 55 static const bool kRandomShuffleChunks = 56 Params::kFlags & SizeClassAllocator64FlagMasks::kRandomShuffleChunks; 57 58 typedef SizeClassAllocator64<Params> ThisT; 59 typedef SizeClassAllocator64LocalCache<ThisT> AllocatorCache; 60 61 // When we know the size class (the region base) we can represent a pointer 62 // as a 4-byte integer (offset from the region start shifted right by 4). 63 typedef u32 CompactPtrT; 64 static const uptr kCompactPtrScale = 4; 65 CompactPtrT PointerToCompactPtr(uptr base, uptr ptr) const { 66 return static_cast<CompactPtrT>((ptr - base) >> kCompactPtrScale); 67 } 68 uptr CompactPtrToPointer(uptr base, CompactPtrT ptr32) const { 69 return base + (static_cast<uptr>(ptr32) << kCompactPtrScale); 70 } 71 72 void Init(s32 release_to_os_interval_ms) { 73 uptr TotalSpaceSize = kSpaceSize + AdditionalSize(); 74 if (kUsingConstantSpaceBeg) { 75 CHECK(IsAligned(kSpaceBeg, SizeClassMap::kMaxSize)); 76 CHECK_EQ(kSpaceBeg, address_range.Init(TotalSpaceSize, 77 PrimaryAllocatorName, kSpaceBeg)); 78 } else { 79 // Combined allocator expects that an 2^N allocation is always aligned to 80 // 2^N. For this to work, the start of the space needs to be aligned as 81 // high as the largest size class (which also needs to be a power of 2). 82 NonConstSpaceBeg = address_range.InitAligned( 83 TotalSpaceSize, SizeClassMap::kMaxSize, PrimaryAllocatorName); 84 CHECK_NE(NonConstSpaceBeg, ~(uptr)0); 85 } 86 SetReleaseToOSIntervalMs(release_to_os_interval_ms); 87 MapWithCallbackOrDie(SpaceEnd(), AdditionalSize(), 88 "SizeClassAllocator: region info"); 89 // Check that the RegionInfo array is aligned on the CacheLine size. 90 DCHECK_EQ(SpaceEnd() % kCacheLineSize, 0); 91 } 92 93 s32 ReleaseToOSIntervalMs() const { 94 return atomic_load(&release_to_os_interval_ms_, memory_order_relaxed); 95 } 96 97 void SetReleaseToOSIntervalMs(s32 release_to_os_interval_ms) { 98 atomic_store(&release_to_os_interval_ms_, release_to_os_interval_ms, 99 memory_order_relaxed); 100 } 101 102 void ForceReleaseToOS() { 103 for (uptr class_id = 1; class_id < kNumClasses; class_id++) { 104 BlockingMutexLock l(&GetRegionInfo(class_id)->mutex); 105 MaybeReleaseToOS(class_id, true /*force*/); 106 } 107 } 108 109 static bool CanAllocate(uptr size, uptr alignment) { 110 return size <= SizeClassMap::kMaxSize && 111 alignment <= SizeClassMap::kMaxSize; 112 } 113 114 NOINLINE void ReturnToAllocator(AllocatorStats *stat, uptr class_id, 115 const CompactPtrT *chunks, uptr n_chunks) { 116 RegionInfo *region = GetRegionInfo(class_id); 117 uptr region_beg = GetRegionBeginBySizeClass(class_id); 118 CompactPtrT *free_array = GetFreeArray(region_beg); 119 120 BlockingMutexLock l(®ion->mutex); 121 uptr old_num_chunks = region->num_freed_chunks; 122 uptr new_num_freed_chunks = old_num_chunks + n_chunks; 123 // Failure to allocate free array space while releasing memory is non 124 // recoverable. 125 if (UNLIKELY(!EnsureFreeArraySpace(region, region_beg, 126 new_num_freed_chunks))) { 127 Report("FATAL: Internal error: %s's allocator exhausted the free list " 128 "space for size class %zd (%zd bytes).\n", SanitizerToolName, 129 class_id, ClassIdToSize(class_id)); 130 Die(); 131 } 132 for (uptr i = 0; i < n_chunks; i++) 133 free_array[old_num_chunks + i] = chunks[i]; 134 region->num_freed_chunks = new_num_freed_chunks; 135 region->stats.n_freed += n_chunks; 136 137 MaybeReleaseToOS(class_id, false /*force*/); 138 } 139 140 NOINLINE bool GetFromAllocator(AllocatorStats *stat, uptr class_id, 141 CompactPtrT *chunks, uptr n_chunks) { 142 RegionInfo *region = GetRegionInfo(class_id); 143 uptr region_beg = GetRegionBeginBySizeClass(class_id); 144 CompactPtrT *free_array = GetFreeArray(region_beg); 145 146 BlockingMutexLock l(®ion->mutex); 147 if (UNLIKELY(region->num_freed_chunks < n_chunks)) { 148 if (UNLIKELY(!PopulateFreeArray(stat, class_id, region, 149 n_chunks - region->num_freed_chunks))) 150 return false; 151 CHECK_GE(region->num_freed_chunks, n_chunks); 152 } 153 region->num_freed_chunks -= n_chunks; 154 uptr base_idx = region->num_freed_chunks; 155 for (uptr i = 0; i < n_chunks; i++) 156 chunks[i] = free_array[base_idx + i]; 157 region->stats.n_allocated += n_chunks; 158 return true; 159 } 160 161 bool PointerIsMine(const void *p) const { 162 uptr P = reinterpret_cast<uptr>(p); 163 if (kUsingConstantSpaceBeg && (kSpaceBeg % kSpaceSize) == 0) 164 return P / kSpaceSize == kSpaceBeg / kSpaceSize; 165 return P >= SpaceBeg() && P < SpaceEnd(); 166 } 167 168 uptr GetRegionBegin(const void *p) { 169 if (kUsingConstantSpaceBeg) 170 return reinterpret_cast<uptr>(p) & ~(kRegionSize - 1); 171 uptr space_beg = SpaceBeg(); 172 return ((reinterpret_cast<uptr>(p) - space_beg) & ~(kRegionSize - 1)) + 173 space_beg; 174 } 175 176 uptr GetRegionBeginBySizeClass(uptr class_id) const { 177 return SpaceBeg() + kRegionSize * class_id; 178 } 179 180 uptr GetSizeClass(const void *p) { 181 if (kUsingConstantSpaceBeg && (kSpaceBeg % kSpaceSize) == 0) 182 return ((reinterpret_cast<uptr>(p)) / kRegionSize) % kNumClassesRounded; 183 return ((reinterpret_cast<uptr>(p) - SpaceBeg()) / kRegionSize) % 184 kNumClassesRounded; 185 } 186 187 void *GetBlockBegin(const void *p) { 188 uptr class_id = GetSizeClass(p); 189 uptr size = ClassIdToSize(class_id); 190 if (!size) return nullptr; 191 uptr chunk_idx = GetChunkIdx((uptr)p, size); 192 uptr reg_beg = GetRegionBegin(p); 193 uptr beg = chunk_idx * size; 194 uptr next_beg = beg + size; 195 if (class_id >= kNumClasses) return nullptr; 196 const RegionInfo *region = AddressSpaceView::Load(GetRegionInfo(class_id)); 197 if (region->mapped_user >= next_beg) 198 return reinterpret_cast<void*>(reg_beg + beg); 199 return nullptr; 200 } 201 202 uptr GetActuallyAllocatedSize(void *p) { 203 CHECK(PointerIsMine(p)); 204 return ClassIdToSize(GetSizeClass(p)); 205 } 206 207 static uptr ClassID(uptr size) { return SizeClassMap::ClassID(size); } 208 209 void *GetMetaData(const void *p) { 210 uptr class_id = GetSizeClass(p); 211 uptr size = ClassIdToSize(class_id); 212 uptr chunk_idx = GetChunkIdx(reinterpret_cast<uptr>(p), size); 213 uptr region_beg = GetRegionBeginBySizeClass(class_id); 214 return reinterpret_cast<void *>(GetMetadataEnd(region_beg) - 215 (1 + chunk_idx) * kMetadataSize); 216 } 217 218 uptr TotalMemoryUsed() { 219 uptr res = 0; 220 for (uptr i = 0; i < kNumClasses; i++) 221 res += GetRegionInfo(i)->allocated_user; 222 return res; 223 } 224 225 // Test-only. 226 void TestOnlyUnmap() { 227 UnmapWithCallbackOrDie((uptr)address_range.base(), address_range.size()); 228 } 229 230 static void FillMemoryProfile(uptr start, uptr rss, bool file, uptr *stats, 231 uptr stats_size) { 232 for (uptr class_id = 0; class_id < stats_size; class_id++) 233 if (stats[class_id] == start) 234 stats[class_id] = rss; 235 } 236 237 void PrintStats(uptr class_id, uptr rss) { 238 RegionInfo *region = GetRegionInfo(class_id); 239 if (region->mapped_user == 0) return; 240 uptr in_use = region->stats.n_allocated - region->stats.n_freed; 241 uptr avail_chunks = region->allocated_user / ClassIdToSize(class_id); 242 Printf( 243 "%s %02zd (%6zd): mapped: %6zdK allocs: %7zd frees: %7zd inuse: %6zd " 244 "num_freed_chunks %7zd avail: %6zd rss: %6zdK releases: %6zd " 245 "last released: %6zdK region: 0x%zx\n", 246 region->exhausted ? "F" : " ", class_id, ClassIdToSize(class_id), 247 region->mapped_user >> 10, region->stats.n_allocated, 248 region->stats.n_freed, in_use, region->num_freed_chunks, avail_chunks, 249 rss >> 10, region->rtoi.num_releases, 250 region->rtoi.last_released_bytes >> 10, 251 SpaceBeg() + kRegionSize * class_id); 252 } 253 254 void PrintStats() { 255 uptr rss_stats[kNumClasses]; 256 for (uptr class_id = 0; class_id < kNumClasses; class_id++) 257 rss_stats[class_id] = SpaceBeg() + kRegionSize * class_id; 258 GetMemoryProfile(FillMemoryProfile, rss_stats, kNumClasses); 259 260 uptr total_mapped = 0; 261 uptr total_rss = 0; 262 uptr n_allocated = 0; 263 uptr n_freed = 0; 264 for (uptr class_id = 1; class_id < kNumClasses; class_id++) { 265 RegionInfo *region = GetRegionInfo(class_id); 266 if (region->mapped_user != 0) { 267 total_mapped += region->mapped_user; 268 total_rss += rss_stats[class_id]; 269 } 270 n_allocated += region->stats.n_allocated; 271 n_freed += region->stats.n_freed; 272 } 273 274 Printf("Stats: SizeClassAllocator64: %zdM mapped (%zdM rss) in " 275 "%zd allocations; remains %zd\n", total_mapped >> 20, 276 total_rss >> 20, n_allocated, n_allocated - n_freed); 277 for (uptr class_id = 1; class_id < kNumClasses; class_id++) 278 PrintStats(class_id, rss_stats[class_id]); 279 } 280 281 // ForceLock() and ForceUnlock() are needed to implement Darwin malloc zone 282 // introspection API. 283 void ForceLock() { 284 for (uptr i = 0; i < kNumClasses; i++) { 285 GetRegionInfo(i)->mutex.Lock(); 286 } 287 } 288 289 void ForceUnlock() { 290 for (int i = (int)kNumClasses - 1; i >= 0; i--) { 291 GetRegionInfo(i)->mutex.Unlock(); 292 } 293 } 294 295 // Iterate over all existing chunks. 296 // The allocator must be locked when calling this function. 297 void ForEachChunk(ForEachChunkCallback callback, void *arg) { 298 for (uptr class_id = 1; class_id < kNumClasses; class_id++) { 299 RegionInfo *region = GetRegionInfo(class_id); 300 uptr chunk_size = ClassIdToSize(class_id); 301 uptr region_beg = SpaceBeg() + class_id * kRegionSize; 302 uptr region_allocated_user_size = 303 AddressSpaceView::Load(region)->allocated_user; 304 for (uptr chunk = region_beg; 305 chunk < region_beg + region_allocated_user_size; 306 chunk += chunk_size) { 307 // Too slow: CHECK_EQ((void *)chunk, GetBlockBegin((void *)chunk)); 308 callback(chunk, arg); 309 } 310 } 311 } 312 313 static uptr ClassIdToSize(uptr class_id) { 314 return SizeClassMap::Size(class_id); 315 } 316 317 static uptr AdditionalSize() { 318 return RoundUpTo(sizeof(RegionInfo) * kNumClassesRounded, 319 GetPageSizeCached()); 320 } 321 322 typedef SizeClassMap SizeClassMapT; 323 static const uptr kNumClasses = SizeClassMap::kNumClasses; 324 static const uptr kNumClassesRounded = SizeClassMap::kNumClassesRounded; 325 326 // A packed array of counters. Each counter occupies 2^n bits, enough to store 327 // counter's max_value. Ctor will try to allocate the required buffer via 328 // mapper->MapPackedCounterArrayBuffer and the caller is expected to check 329 // whether the initialization was successful by checking IsAllocated() result. 330 // For the performance sake, none of the accessors check the validity of the 331 // arguments, it is assumed that index is always in [0, n) range and the value 332 // is not incremented past max_value. 333 template<class MemoryMapperT> 334 class PackedCounterArray { 335 public: 336 PackedCounterArray(u64 num_counters, u64 max_value, MemoryMapperT *mapper) 337 : n(num_counters), memory_mapper(mapper) { 338 CHECK_GT(num_counters, 0); 339 CHECK_GT(max_value, 0); 340 constexpr u64 kMaxCounterBits = sizeof(*buffer) * 8ULL; 341 // Rounding counter storage size up to the power of two allows for using 342 // bit shifts calculating particular counter's index and offset. 343 uptr counter_size_bits = 344 RoundUpToPowerOfTwo(MostSignificantSetBitIndex(max_value) + 1); 345 CHECK_LE(counter_size_bits, kMaxCounterBits); 346 counter_size_bits_log = Log2(counter_size_bits); 347 counter_mask = ~0ULL >> (kMaxCounterBits - counter_size_bits); 348 349 uptr packing_ratio = kMaxCounterBits >> counter_size_bits_log; 350 CHECK_GT(packing_ratio, 0); 351 packing_ratio_log = Log2(packing_ratio); 352 bit_offset_mask = packing_ratio - 1; 353 354 buffer_size = 355 (RoundUpTo(n, 1ULL << packing_ratio_log) >> packing_ratio_log) * 356 sizeof(*buffer); 357 buffer = reinterpret_cast<u64*>( 358 memory_mapper->MapPackedCounterArrayBuffer(buffer_size)); 359 } 360 ~PackedCounterArray() { 361 if (buffer) { 362 memory_mapper->UnmapPackedCounterArrayBuffer( 363 reinterpret_cast<uptr>(buffer), buffer_size); 364 } 365 } 366 367 bool IsAllocated() const { 368 return !!buffer; 369 } 370 371 u64 GetCount() const { 372 return n; 373 } 374 375 uptr Get(uptr i) const { 376 DCHECK_LT(i, n); 377 uptr index = i >> packing_ratio_log; 378 uptr bit_offset = (i & bit_offset_mask) << counter_size_bits_log; 379 return (buffer[index] >> bit_offset) & counter_mask; 380 } 381 382 void Inc(uptr i) const { 383 DCHECK_LT(Get(i), counter_mask); 384 uptr index = i >> packing_ratio_log; 385 uptr bit_offset = (i & bit_offset_mask) << counter_size_bits_log; 386 buffer[index] += 1ULL << bit_offset; 387 } 388 389 void IncRange(uptr from, uptr to) const { 390 DCHECK_LE(from, to); 391 for (uptr i = from; i <= to; i++) 392 Inc(i); 393 } 394 395 private: 396 const u64 n; 397 u64 counter_size_bits_log; 398 u64 counter_mask; 399 u64 packing_ratio_log; 400 u64 bit_offset_mask; 401 402 MemoryMapperT* const memory_mapper; 403 u64 buffer_size; 404 u64* buffer; 405 }; 406 407 template<class MemoryMapperT> 408 class FreePagesRangeTracker { 409 public: 410 explicit FreePagesRangeTracker(MemoryMapperT* mapper) 411 : memory_mapper(mapper), 412 page_size_scaled_log(Log2(GetPageSizeCached() >> kCompactPtrScale)), 413 in_the_range(false), current_page(0), current_range_start_page(0) {} 414 415 void NextPage(bool freed) { 416 if (freed) { 417 if (!in_the_range) { 418 current_range_start_page = current_page; 419 in_the_range = true; 420 } 421 } else { 422 CloseOpenedRange(); 423 } 424 current_page++; 425 } 426 427 void Done() { 428 CloseOpenedRange(); 429 } 430 431 private: 432 void CloseOpenedRange() { 433 if (in_the_range) { 434 memory_mapper->ReleasePageRangeToOS( 435 current_range_start_page << page_size_scaled_log, 436 current_page << page_size_scaled_log); 437 in_the_range = false; 438 } 439 } 440 441 MemoryMapperT* const memory_mapper; 442 const uptr page_size_scaled_log; 443 bool in_the_range; 444 uptr current_page; 445 uptr current_range_start_page; 446 }; 447 448 // Iterates over the free_array to identify memory pages containing freed 449 // chunks only and returns these pages back to OS. 450 // allocated_pages_count is the total number of pages allocated for the 451 // current bucket. 452 template<class MemoryMapperT> 453 static void ReleaseFreeMemoryToOS(CompactPtrT *free_array, 454 uptr free_array_count, uptr chunk_size, 455 uptr allocated_pages_count, 456 MemoryMapperT *memory_mapper) { 457 const uptr page_size = GetPageSizeCached(); 458 459 // Figure out the number of chunks per page and whether we can take a fast 460 // path (the number of chunks per page is the same for all pages). 461 uptr full_pages_chunk_count_max; 462 bool same_chunk_count_per_page; 463 if (chunk_size <= page_size && page_size % chunk_size == 0) { 464 // Same number of chunks per page, no cross overs. 465 full_pages_chunk_count_max = page_size / chunk_size; 466 same_chunk_count_per_page = true; 467 } else if (chunk_size <= page_size && page_size % chunk_size != 0 && 468 chunk_size % (page_size % chunk_size) == 0) { 469 // Some chunks are crossing page boundaries, which means that the page 470 // contains one or two partial chunks, but all pages contain the same 471 // number of chunks. 472 full_pages_chunk_count_max = page_size / chunk_size + 1; 473 same_chunk_count_per_page = true; 474 } else if (chunk_size <= page_size) { 475 // Some chunks are crossing page boundaries, which means that the page 476 // contains one or two partial chunks. 477 full_pages_chunk_count_max = page_size / chunk_size + 2; 478 same_chunk_count_per_page = false; 479 } else if (chunk_size > page_size && chunk_size % page_size == 0) { 480 // One chunk covers multiple pages, no cross overs. 481 full_pages_chunk_count_max = 1; 482 same_chunk_count_per_page = true; 483 } else if (chunk_size > page_size) { 484 // One chunk covers multiple pages, Some chunks are crossing page 485 // boundaries. Some pages contain one chunk, some contain two. 486 full_pages_chunk_count_max = 2; 487 same_chunk_count_per_page = false; 488 } else { 489 UNREACHABLE("All chunk_size/page_size ratios must be handled."); 490 } 491 492 PackedCounterArray<MemoryMapperT> counters(allocated_pages_count, 493 full_pages_chunk_count_max, 494 memory_mapper); 495 if (!counters.IsAllocated()) 496 return; 497 498 const uptr chunk_size_scaled = chunk_size >> kCompactPtrScale; 499 const uptr page_size_scaled = page_size >> kCompactPtrScale; 500 const uptr page_size_scaled_log = Log2(page_size_scaled); 501 502 // Iterate over free chunks and count how many free chunks affect each 503 // allocated page. 504 if (chunk_size <= page_size && page_size % chunk_size == 0) { 505 // Each chunk affects one page only. 506 for (uptr i = 0; i < free_array_count; i++) 507 counters.Inc(free_array[i] >> page_size_scaled_log); 508 } else { 509 // In all other cases chunks might affect more than one page. 510 for (uptr i = 0; i < free_array_count; i++) { 511 counters.IncRange( 512 free_array[i] >> page_size_scaled_log, 513 (free_array[i] + chunk_size_scaled - 1) >> page_size_scaled_log); 514 } 515 } 516 517 // Iterate over pages detecting ranges of pages with chunk counters equal 518 // to the expected number of chunks for the particular page. 519 FreePagesRangeTracker<MemoryMapperT> range_tracker(memory_mapper); 520 if (same_chunk_count_per_page) { 521 // Fast path, every page has the same number of chunks affecting it. 522 for (uptr i = 0; i < counters.GetCount(); i++) 523 range_tracker.NextPage(counters.Get(i) == full_pages_chunk_count_max); 524 } else { 525 // Show path, go through the pages keeping count how many chunks affect 526 // each page. 527 const uptr pn = 528 chunk_size < page_size ? page_size_scaled / chunk_size_scaled : 1; 529 const uptr pnc = pn * chunk_size_scaled; 530 // The idea is to increment the current page pointer by the first chunk 531 // size, middle portion size (the portion of the page covered by chunks 532 // except the first and the last one) and then the last chunk size, adding 533 // up the number of chunks on the current page and checking on every step 534 // whether the page boundary was crossed. 535 uptr prev_page_boundary = 0; 536 uptr current_boundary = 0; 537 for (uptr i = 0; i < counters.GetCount(); i++) { 538 uptr page_boundary = prev_page_boundary + page_size_scaled; 539 uptr chunks_per_page = pn; 540 if (current_boundary < page_boundary) { 541 if (current_boundary > prev_page_boundary) 542 chunks_per_page++; 543 current_boundary += pnc; 544 if (current_boundary < page_boundary) { 545 chunks_per_page++; 546 current_boundary += chunk_size_scaled; 547 } 548 } 549 prev_page_boundary = page_boundary; 550 551 range_tracker.NextPage(counters.Get(i) == chunks_per_page); 552 } 553 } 554 range_tracker.Done(); 555 } 556 557 private: 558 friend class MemoryMapper; 559 560 ReservedAddressRange address_range; 561 562 static const uptr kRegionSize = kSpaceSize / kNumClassesRounded; 563 // FreeArray is the array of free-d chunks (stored as 4-byte offsets). 564 // In the worst case it may reguire kRegionSize/SizeClassMap::kMinSize 565 // elements, but in reality this will not happen. For simplicity we 566 // dedicate 1/8 of the region's virtual space to FreeArray. 567 static const uptr kFreeArraySize = kRegionSize / 8; 568 569 static const bool kUsingConstantSpaceBeg = kSpaceBeg != ~(uptr)0; 570 uptr NonConstSpaceBeg; 571 uptr SpaceBeg() const { 572 return kUsingConstantSpaceBeg ? kSpaceBeg : NonConstSpaceBeg; 573 } 574 uptr SpaceEnd() const { return SpaceBeg() + kSpaceSize; } 575 // kRegionSize must be >= 2^32. 576 COMPILER_CHECK((kRegionSize) >= (1ULL << (SANITIZER_WORDSIZE / 2))); 577 // kRegionSize must be <= 2^36, see CompactPtrT. 578 COMPILER_CHECK((kRegionSize) <= (1ULL << (SANITIZER_WORDSIZE / 2 + 4))); 579 // Call mmap for user memory with at least this size. 580 static const uptr kUserMapSize = 1 << 16; 581 // Call mmap for metadata memory with at least this size. 582 static const uptr kMetaMapSize = 1 << 16; 583 // Call mmap for free array memory with at least this size. 584 static const uptr kFreeArrayMapSize = 1 << 16; 585 586 atomic_sint32_t release_to_os_interval_ms_; 587 588 struct Stats { 589 uptr n_allocated; 590 uptr n_freed; 591 }; 592 593 struct ReleaseToOsInfo { 594 uptr n_freed_at_last_release; 595 uptr num_releases; 596 u64 last_release_at_ns; 597 u64 last_released_bytes; 598 }; 599 600 struct ALIGNED(SANITIZER_CACHE_LINE_SIZE) RegionInfo { 601 BlockingMutex mutex; 602 uptr num_freed_chunks; // Number of elements in the freearray. 603 uptr mapped_free_array; // Bytes mapped for freearray. 604 uptr allocated_user; // Bytes allocated for user memory. 605 uptr allocated_meta; // Bytes allocated for metadata. 606 uptr mapped_user; // Bytes mapped for user memory. 607 uptr mapped_meta; // Bytes mapped for metadata. 608 u32 rand_state; // Seed for random shuffle, used if kRandomShuffleChunks. 609 bool exhausted; // Whether region is out of space for new chunks. 610 Stats stats; 611 ReleaseToOsInfo rtoi; 612 }; 613 COMPILER_CHECK(sizeof(RegionInfo) % kCacheLineSize == 0); 614 615 RegionInfo *GetRegionInfo(uptr class_id) const { 616 DCHECK_LT(class_id, kNumClasses); 617 RegionInfo *regions = reinterpret_cast<RegionInfo *>(SpaceEnd()); 618 return ®ions[class_id]; 619 } 620 621 uptr GetMetadataEnd(uptr region_beg) const { 622 return region_beg + kRegionSize - kFreeArraySize; 623 } 624 625 uptr GetChunkIdx(uptr chunk, uptr size) const { 626 if (!kUsingConstantSpaceBeg) 627 chunk -= SpaceBeg(); 628 629 uptr offset = chunk % kRegionSize; 630 // Here we divide by a non-constant. This is costly. 631 // size always fits into 32-bits. If the offset fits too, use 32-bit div. 632 if (offset >> (SANITIZER_WORDSIZE / 2)) 633 return offset / size; 634 return (u32)offset / (u32)size; 635 } 636 637 CompactPtrT *GetFreeArray(uptr region_beg) const { 638 return reinterpret_cast<CompactPtrT *>(GetMetadataEnd(region_beg)); 639 } 640 641 bool MapWithCallback(uptr beg, uptr size, const char *name) { 642 uptr mapped = address_range.Map(beg, size, name); 643 if (UNLIKELY(!mapped)) 644 return false; 645 CHECK_EQ(beg, mapped); 646 MapUnmapCallback().OnMap(beg, size); 647 return true; 648 } 649 650 void MapWithCallbackOrDie(uptr beg, uptr size, const char *name) { 651 CHECK_EQ(beg, address_range.MapOrDie(beg, size, name)); 652 MapUnmapCallback().OnMap(beg, size); 653 } 654 655 void UnmapWithCallbackOrDie(uptr beg, uptr size) { 656 MapUnmapCallback().OnUnmap(beg, size); 657 address_range.Unmap(beg, size); 658 } 659 660 bool EnsureFreeArraySpace(RegionInfo *region, uptr region_beg, 661 uptr num_freed_chunks) { 662 uptr needed_space = num_freed_chunks * sizeof(CompactPtrT); 663 if (region->mapped_free_array < needed_space) { 664 uptr new_mapped_free_array = RoundUpTo(needed_space, kFreeArrayMapSize); 665 CHECK_LE(new_mapped_free_array, kFreeArraySize); 666 uptr current_map_end = reinterpret_cast<uptr>(GetFreeArray(region_beg)) + 667 region->mapped_free_array; 668 uptr new_map_size = new_mapped_free_array - region->mapped_free_array; 669 if (UNLIKELY(!MapWithCallback(current_map_end, new_map_size, 670 "SizeClassAllocator: freearray"))) 671 return false; 672 region->mapped_free_array = new_mapped_free_array; 673 } 674 return true; 675 } 676 677 // Check whether this size class is exhausted. 678 bool IsRegionExhausted(RegionInfo *region, uptr class_id, 679 uptr additional_map_size) { 680 if (LIKELY(region->mapped_user + region->mapped_meta + 681 additional_map_size <= kRegionSize - kFreeArraySize)) 682 return false; 683 if (!region->exhausted) { 684 region->exhausted = true; 685 Printf("%s: Out of memory. ", SanitizerToolName); 686 Printf("The process has exhausted %zuMB for size class %zu.\n", 687 kRegionSize >> 20, ClassIdToSize(class_id)); 688 } 689 return true; 690 } 691 692 NOINLINE bool PopulateFreeArray(AllocatorStats *stat, uptr class_id, 693 RegionInfo *region, uptr requested_count) { 694 // region->mutex is held. 695 const uptr region_beg = GetRegionBeginBySizeClass(class_id); 696 const uptr size = ClassIdToSize(class_id); 697 698 const uptr total_user_bytes = 699 region->allocated_user + requested_count * size; 700 // Map more space for chunks, if necessary. 701 if (LIKELY(total_user_bytes > region->mapped_user)) { 702 if (UNLIKELY(region->mapped_user == 0)) { 703 if (!kUsingConstantSpaceBeg && kRandomShuffleChunks) 704 // The random state is initialized from ASLR. 705 region->rand_state = static_cast<u32>(region_beg >> 12); 706 // Postpone the first release to OS attempt for ReleaseToOSIntervalMs, 707 // preventing just allocated memory from being released sooner than 708 // necessary and also preventing extraneous ReleaseMemoryPagesToOS calls 709 // for short lived processes. 710 // Do it only when the feature is turned on, to avoid a potentially 711 // extraneous syscall. 712 if (ReleaseToOSIntervalMs() >= 0) 713 region->rtoi.last_release_at_ns = MonotonicNanoTime(); 714 } 715 // Do the mmap for the user memory. 716 const uptr user_map_size = 717 RoundUpTo(total_user_bytes - region->mapped_user, kUserMapSize); 718 if (UNLIKELY(IsRegionExhausted(region, class_id, user_map_size))) 719 return false; 720 if (UNLIKELY(!MapWithCallback(region_beg + region->mapped_user, 721 user_map_size, 722 "SizeClassAllocator: region data"))) 723 return false; 724 stat->Add(AllocatorStatMapped, user_map_size); 725 region->mapped_user += user_map_size; 726 } 727 const uptr new_chunks_count = 728 (region->mapped_user - region->allocated_user) / size; 729 730 if (kMetadataSize) { 731 // Calculate the required space for metadata. 732 const uptr total_meta_bytes = 733 region->allocated_meta + new_chunks_count * kMetadataSize; 734 const uptr meta_map_size = (total_meta_bytes > region->mapped_meta) ? 735 RoundUpTo(total_meta_bytes - region->mapped_meta, kMetaMapSize) : 0; 736 // Map more space for metadata, if necessary. 737 if (meta_map_size) { 738 if (UNLIKELY(IsRegionExhausted(region, class_id, meta_map_size))) 739 return false; 740 if (UNLIKELY(!MapWithCallback( 741 GetMetadataEnd(region_beg) - region->mapped_meta - meta_map_size, 742 meta_map_size, "SizeClassAllocator: region metadata"))) 743 return false; 744 region->mapped_meta += meta_map_size; 745 } 746 } 747 748 // If necessary, allocate more space for the free array and populate it with 749 // newly allocated chunks. 750 const uptr total_freed_chunks = region->num_freed_chunks + new_chunks_count; 751 if (UNLIKELY(!EnsureFreeArraySpace(region, region_beg, total_freed_chunks))) 752 return false; 753 CompactPtrT *free_array = GetFreeArray(region_beg); 754 for (uptr i = 0, chunk = region->allocated_user; i < new_chunks_count; 755 i++, chunk += size) 756 free_array[total_freed_chunks - 1 - i] = PointerToCompactPtr(0, chunk); 757 if (kRandomShuffleChunks) 758 RandomShuffle(&free_array[region->num_freed_chunks], new_chunks_count, 759 ®ion->rand_state); 760 761 // All necessary memory is mapped and now it is safe to advance all 762 // 'allocated_*' counters. 763 region->num_freed_chunks += new_chunks_count; 764 region->allocated_user += new_chunks_count * size; 765 CHECK_LE(region->allocated_user, region->mapped_user); 766 region->allocated_meta += new_chunks_count * kMetadataSize; 767 CHECK_LE(region->allocated_meta, region->mapped_meta); 768 region->exhausted = false; 769 770 // TODO(alekseyshl): Consider bumping last_release_at_ns here to prevent 771 // MaybeReleaseToOS from releasing just allocated pages or protect these 772 // not yet used chunks some other way. 773 774 return true; 775 } 776 777 class MemoryMapper { 778 public: 779 MemoryMapper(const ThisT& base_allocator, uptr class_id) 780 : allocator(base_allocator), 781 region_base(base_allocator.GetRegionBeginBySizeClass(class_id)), 782 released_ranges_count(0), 783 released_bytes(0) { 784 } 785 786 uptr GetReleasedRangesCount() const { 787 return released_ranges_count; 788 } 789 790 uptr GetReleasedBytes() const { 791 return released_bytes; 792 } 793 794 uptr MapPackedCounterArrayBuffer(uptr buffer_size) { 795 // TODO(alekseyshl): The idea to explore is to check if we have enough 796 // space between num_freed_chunks*sizeof(CompactPtrT) and 797 // mapped_free_array to fit buffer_size bytes and use that space instead 798 // of mapping a temporary one. 799 return reinterpret_cast<uptr>( 800 MmapOrDieOnFatalError(buffer_size, "ReleaseToOSPageCounters")); 801 } 802 803 void UnmapPackedCounterArrayBuffer(uptr buffer, uptr buffer_size) { 804 UnmapOrDie(reinterpret_cast<void *>(buffer), buffer_size); 805 } 806 807 // Releases [from, to) range of pages back to OS. 808 void ReleasePageRangeToOS(CompactPtrT from, CompactPtrT to) { 809 const uptr from_page = allocator.CompactPtrToPointer(region_base, from); 810 const uptr to_page = allocator.CompactPtrToPointer(region_base, to); 811 ReleaseMemoryPagesToOS(from_page, to_page); 812 released_ranges_count++; 813 released_bytes += to_page - from_page; 814 } 815 816 private: 817 const ThisT& allocator; 818 const uptr region_base; 819 uptr released_ranges_count; 820 uptr released_bytes; 821 }; 822 823 // Attempts to release RAM occupied by freed chunks back to OS. The region is 824 // expected to be locked. 825 void MaybeReleaseToOS(uptr class_id, bool force) { 826 RegionInfo *region = GetRegionInfo(class_id); 827 const uptr chunk_size = ClassIdToSize(class_id); 828 const uptr page_size = GetPageSizeCached(); 829 830 uptr n = region->num_freed_chunks; 831 if (n * chunk_size < page_size) 832 return; // No chance to release anything. 833 if ((region->stats.n_freed - 834 region->rtoi.n_freed_at_last_release) * chunk_size < page_size) { 835 return; // Nothing new to release. 836 } 837 838 if (!force) { 839 s32 interval_ms = ReleaseToOSIntervalMs(); 840 if (interval_ms < 0) 841 return; 842 843 if (region->rtoi.last_release_at_ns + interval_ms * 1000000ULL > 844 MonotonicNanoTime()) { 845 return; // Memory was returned recently. 846 } 847 } 848 849 MemoryMapper memory_mapper(*this, class_id); 850 851 ReleaseFreeMemoryToOS<MemoryMapper>( 852 GetFreeArray(GetRegionBeginBySizeClass(class_id)), n, chunk_size, 853 RoundUpTo(region->allocated_user, page_size) / page_size, 854 &memory_mapper); 855 856 if (memory_mapper.GetReleasedRangesCount() > 0) { 857 region->rtoi.n_freed_at_last_release = region->stats.n_freed; 858 region->rtoi.num_releases += memory_mapper.GetReleasedRangesCount(); 859 region->rtoi.last_released_bytes = memory_mapper.GetReleasedBytes(); 860 } 861 region->rtoi.last_release_at_ns = MonotonicNanoTime(); 862 } 863}; 864