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