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