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 #if _LP64 568 COMPILER_CHECK((kRegionSize) >= (1ULL << (SANITIZER_WORDSIZE / 2))); 569 // kRegionSize must be <= 2^36, see CompactPtrT. 570 COMPILER_CHECK((kRegionSize) <= (1ULL << (SANITIZER_WORDSIZE / 2 + 4))); 571 #endif 572 // Call mmap for user memory with at least this size. 573 static const uptr kUserMapSize = 1 << 16; 574 // Call mmap for metadata memory with at least this size. 575 static const uptr kMetaMapSize = 1 << 16; 576 // Call mmap for free array memory with at least this size. 577 static const uptr kFreeArrayMapSize = 1 << 16; 578 579 atomic_sint32_t release_to_os_interval_ms_; 580 581 struct Stats { 582 uptr n_allocated; 583 uptr n_freed; 584 }; 585 586 struct ReleaseToOsInfo { 587 uptr n_freed_at_last_release; 588 uptr num_releases; 589 u64 last_release_at_ns; 590 u64 last_released_bytes; 591 }; 592 ALIGNED(SANITIZER_CACHE_LINE_SIZE)593 struct ALIGNED(SANITIZER_CACHE_LINE_SIZE) RegionInfo { 594 BlockingMutex mutex; 595 uptr num_freed_chunks; // Number of elements in the freearray. 596 uptr mapped_free_array; // Bytes mapped for freearray. 597 uptr allocated_user; // Bytes allocated for user memory. 598 uptr allocated_meta; // Bytes allocated for metadata. 599 uptr mapped_user; // Bytes mapped for user memory. 600 uptr mapped_meta; // Bytes mapped for metadata. 601 u32 rand_state; // Seed for random shuffle, used if kRandomShuffleChunks. 602 bool exhausted; // Whether region is out of space for new chunks. 603 Stats stats; 604 ReleaseToOsInfo rtoi; 605 }; 606 COMPILER_CHECK(sizeof(RegionInfo) % kCacheLineSize == 0); 607 GetRegionInfo(uptr class_id)608 RegionInfo *GetRegionInfo(uptr class_id) const { 609 DCHECK_LT(class_id, kNumClasses); 610 RegionInfo *regions = reinterpret_cast<RegionInfo *>(SpaceEnd()); 611 return ®ions[class_id]; 612 } 613 GetMetadataEnd(uptr region_beg)614 uptr GetMetadataEnd(uptr region_beg) const { 615 return region_beg + kRegionSize - kFreeArraySize; 616 } 617 GetChunkIdx(uptr chunk,uptr size)618 uptr GetChunkIdx(uptr chunk, uptr size) const { 619 if (!kUsingConstantSpaceBeg) 620 chunk -= SpaceBeg(); 621 622 uptr offset = chunk % kRegionSize; 623 // Here we divide by a non-constant. This is costly. 624 // size always fits into 32-bits. If the offset fits too, use 32-bit div. 625 if (offset >> (SANITIZER_WORDSIZE / 2)) 626 return offset / size; 627 return (u32)offset / (u32)size; 628 } 629 GetFreeArray(uptr region_beg)630 CompactPtrT *GetFreeArray(uptr region_beg) const { 631 return reinterpret_cast<CompactPtrT *>(GetMetadataEnd(region_beg)); 632 } 633 MapWithCallback(uptr beg,uptr size)634 bool MapWithCallback(uptr beg, uptr size) { 635 uptr mapped = address_range.Map(beg, size); 636 if (UNLIKELY(!mapped)) 637 return false; 638 CHECK_EQ(beg, mapped); 639 MapUnmapCallback().OnMap(beg, size); 640 return true; 641 } 642 MapWithCallbackOrDie(uptr beg,uptr size)643 void MapWithCallbackOrDie(uptr beg, uptr size) { 644 CHECK_EQ(beg, address_range.MapOrDie(beg, size)); 645 MapUnmapCallback().OnMap(beg, size); 646 } 647 UnmapWithCallbackOrDie(uptr beg,uptr size)648 void UnmapWithCallbackOrDie(uptr beg, uptr size) { 649 MapUnmapCallback().OnUnmap(beg, size); 650 address_range.Unmap(beg, size); 651 } 652 EnsureFreeArraySpace(RegionInfo * region,uptr region_beg,uptr num_freed_chunks)653 bool EnsureFreeArraySpace(RegionInfo *region, uptr region_beg, 654 uptr num_freed_chunks) { 655 uptr needed_space = num_freed_chunks * sizeof(CompactPtrT); 656 if (region->mapped_free_array < needed_space) { 657 uptr new_mapped_free_array = RoundUpTo(needed_space, kFreeArrayMapSize); 658 CHECK_LE(new_mapped_free_array, kFreeArraySize); 659 uptr current_map_end = reinterpret_cast<uptr>(GetFreeArray(region_beg)) + 660 region->mapped_free_array; 661 uptr new_map_size = new_mapped_free_array - region->mapped_free_array; 662 if (UNLIKELY(!MapWithCallback(current_map_end, new_map_size))) 663 return false; 664 region->mapped_free_array = new_mapped_free_array; 665 } 666 return true; 667 } 668 669 // Check whether this size class is exhausted. IsRegionExhausted(RegionInfo * region,uptr class_id,uptr additional_map_size)670 bool IsRegionExhausted(RegionInfo *region, uptr class_id, 671 uptr additional_map_size) { 672 if (LIKELY(region->mapped_user + region->mapped_meta + 673 additional_map_size <= kRegionSize - kFreeArraySize)) 674 return false; 675 if (!region->exhausted) { 676 region->exhausted = true; 677 Printf("%s: Out of memory. ", SanitizerToolName); 678 Printf("The process has exhausted %zuMB for size class %zu.\n", 679 kRegionSize >> 20, ClassIdToSize(class_id)); 680 } 681 return true; 682 } 683 PopulateFreeArray(AllocatorStats * stat,uptr class_id,RegionInfo * region,uptr requested_count)684 NOINLINE bool PopulateFreeArray(AllocatorStats *stat, uptr class_id, 685 RegionInfo *region, uptr requested_count) { 686 // region->mutex is held. 687 const uptr region_beg = GetRegionBeginBySizeClass(class_id); 688 const uptr size = ClassIdToSize(class_id); 689 690 const uptr total_user_bytes = 691 region->allocated_user + requested_count * size; 692 // Map more space for chunks, if necessary. 693 if (LIKELY(total_user_bytes > region->mapped_user)) { 694 if (UNLIKELY(region->mapped_user == 0)) { 695 if (!kUsingConstantSpaceBeg && kRandomShuffleChunks) 696 // The random state is initialized from ASLR. 697 region->rand_state = static_cast<u32>(region_beg >> 12); 698 // Postpone the first release to OS attempt for ReleaseToOSIntervalMs, 699 // preventing just allocated memory from being released sooner than 700 // necessary and also preventing extraneous ReleaseMemoryPagesToOS calls 701 // for short lived processes. 702 // Do it only when the feature is turned on, to avoid a potentially 703 // extraneous syscall. 704 if (ReleaseToOSIntervalMs() >= 0) 705 region->rtoi.last_release_at_ns = MonotonicNanoTime(); 706 } 707 // Do the mmap for the user memory. 708 const uptr user_map_size = 709 RoundUpTo(total_user_bytes - region->mapped_user, kUserMapSize); 710 if (UNLIKELY(IsRegionExhausted(region, class_id, user_map_size))) 711 return false; 712 if (UNLIKELY(!MapWithCallback(region_beg + region->mapped_user, 713 user_map_size))) 714 return false; 715 stat->Add(AllocatorStatMapped, user_map_size); 716 region->mapped_user += user_map_size; 717 } 718 const uptr new_chunks_count = 719 (region->mapped_user - region->allocated_user) / size; 720 721 if (kMetadataSize) { 722 // Calculate the required space for metadata. 723 const uptr total_meta_bytes = 724 region->allocated_meta + new_chunks_count * kMetadataSize; 725 const uptr meta_map_size = (total_meta_bytes > region->mapped_meta) ? 726 RoundUpTo(total_meta_bytes - region->mapped_meta, kMetaMapSize) : 0; 727 // Map more space for metadata, if necessary. 728 if (meta_map_size) { 729 if (UNLIKELY(IsRegionExhausted(region, class_id, meta_map_size))) 730 return false; 731 if (UNLIKELY(!MapWithCallback( 732 GetMetadataEnd(region_beg) - region->mapped_meta - meta_map_size, 733 meta_map_size))) 734 return false; 735 region->mapped_meta += meta_map_size; 736 } 737 } 738 739 // If necessary, allocate more space for the free array and populate it with 740 // newly allocated chunks. 741 const uptr total_freed_chunks = region->num_freed_chunks + new_chunks_count; 742 if (UNLIKELY(!EnsureFreeArraySpace(region, region_beg, total_freed_chunks))) 743 return false; 744 CompactPtrT *free_array = GetFreeArray(region_beg); 745 for (uptr i = 0, chunk = region->allocated_user; i < new_chunks_count; 746 i++, chunk += size) 747 free_array[total_freed_chunks - 1 - i] = PointerToCompactPtr(0, chunk); 748 if (kRandomShuffleChunks) 749 RandomShuffle(&free_array[region->num_freed_chunks], new_chunks_count, 750 ®ion->rand_state); 751 752 // All necessary memory is mapped and now it is safe to advance all 753 // 'allocated_*' counters. 754 region->num_freed_chunks += new_chunks_count; 755 region->allocated_user += new_chunks_count * size; 756 CHECK_LE(region->allocated_user, region->mapped_user); 757 region->allocated_meta += new_chunks_count * kMetadataSize; 758 CHECK_LE(region->allocated_meta, region->mapped_meta); 759 region->exhausted = false; 760 761 // TODO(alekseyshl): Consider bumping last_release_at_ns here to prevent 762 // MaybeReleaseToOS from releasing just allocated pages or protect these 763 // not yet used chunks some other way. 764 765 return true; 766 } 767 768 class MemoryMapper { 769 public: MemoryMapper(const ThisT & base_allocator,uptr class_id)770 MemoryMapper(const ThisT& base_allocator, uptr class_id) 771 : allocator(base_allocator), 772 region_base(base_allocator.GetRegionBeginBySizeClass(class_id)), 773 released_ranges_count(0), 774 released_bytes(0) { 775 } 776 GetReleasedRangesCount()777 uptr GetReleasedRangesCount() const { 778 return released_ranges_count; 779 } 780 GetReleasedBytes()781 uptr GetReleasedBytes() const { 782 return released_bytes; 783 } 784 MapPackedCounterArrayBuffer(uptr buffer_size)785 uptr MapPackedCounterArrayBuffer(uptr buffer_size) { 786 // TODO(alekseyshl): The idea to explore is to check if we have enough 787 // space between num_freed_chunks*sizeof(CompactPtrT) and 788 // mapped_free_array to fit buffer_size bytes and use that space instead 789 // of mapping a temporary one. 790 return reinterpret_cast<uptr>( 791 MmapOrDieOnFatalError(buffer_size, "ReleaseToOSPageCounters")); 792 } 793 UnmapPackedCounterArrayBuffer(uptr buffer,uptr buffer_size)794 void UnmapPackedCounterArrayBuffer(uptr buffer, uptr buffer_size) { 795 UnmapOrDie(reinterpret_cast<void *>(buffer), buffer_size); 796 } 797 798 // Releases [from, to) range of pages back to OS. ReleasePageRangeToOS(CompactPtrT from,CompactPtrT to)799 void ReleasePageRangeToOS(CompactPtrT from, CompactPtrT to) { 800 const uptr from_page = allocator.CompactPtrToPointer(region_base, from); 801 const uptr to_page = allocator.CompactPtrToPointer(region_base, to); 802 ReleaseMemoryPagesToOS(from_page, to_page); 803 released_ranges_count++; 804 released_bytes += to_page - from_page; 805 } 806 807 private: 808 const ThisT& allocator; 809 const uptr region_base; 810 uptr released_ranges_count; 811 uptr released_bytes; 812 }; 813 814 // Attempts to release RAM occupied by freed chunks back to OS. The region is 815 // expected to be locked. MaybeReleaseToOS(uptr class_id,bool force)816 void MaybeReleaseToOS(uptr class_id, bool force) { 817 RegionInfo *region = GetRegionInfo(class_id); 818 const uptr chunk_size = ClassIdToSize(class_id); 819 const uptr page_size = GetPageSizeCached(); 820 821 uptr n = region->num_freed_chunks; 822 if (n * chunk_size < page_size) 823 return; // No chance to release anything. 824 if ((region->stats.n_freed - 825 region->rtoi.n_freed_at_last_release) * chunk_size < page_size) { 826 return; // Nothing new to release. 827 } 828 829 if (!force) { 830 s32 interval_ms = ReleaseToOSIntervalMs(); 831 if (interval_ms < 0) 832 return; 833 834 if (region->rtoi.last_release_at_ns + interval_ms * 1000000ULL > 835 MonotonicNanoTime()) { 836 return; // Memory was returned recently. 837 } 838 } 839 840 MemoryMapper memory_mapper(*this, class_id); 841 842 ReleaseFreeMemoryToOS<MemoryMapper>( 843 GetFreeArray(GetRegionBeginBySizeClass(class_id)), n, chunk_size, 844 RoundUpTo(region->allocated_user, page_size) / page_size, 845 &memory_mapper); 846 847 if (memory_mapper.GetReleasedRangesCount() > 0) { 848 region->rtoi.n_freed_at_last_release = region->stats.n_freed; 849 region->rtoi.num_releases += memory_mapper.GetReleasedRangesCount(); 850 region->rtoi.last_released_bytes = memory_mapper.GetReleasedBytes(); 851 } 852 region->rtoi.last_release_at_ns = MonotonicNanoTime(); 853 } 854 }; 855