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