sanitizer_allocator_primary64.h revision 311697
1//===-- sanitizer_allocator_primary64.h -------------------------*- C++ -*-===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file is distributed under the University of Illinois Open Source 6// License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// 9// 10// Part of the Sanitizer Allocator. 11// 12//===----------------------------------------------------------------------===// 13#ifndef SANITIZER_ALLOCATOR_H 14#error This file must be included inside sanitizer_allocator.h 15#endif 16 17template<class SizeClassAllocator> struct SizeClassAllocator64LocalCache; 18 19// SizeClassAllocator64 -- allocator for 64-bit address space. 20// The template parameter Params is a class containing the actual parameters. 21// 22// Space: a portion of address space of kSpaceSize bytes starting at SpaceBeg. 23// If kSpaceBeg is ~0 then SpaceBeg is chosen dynamically my mmap. 24// Otherwise SpaceBeg=kSpaceBeg (fixed address). 25// kSpaceSize is a power of two. 26// At the beginning the entire space is mprotect-ed, then small parts of it 27// are mapped on demand. 28// 29// Region: a part of Space dedicated to a single size class. 30// There are kNumClasses Regions of equal size. 31// 32// UserChunk: a piece of memory returned to user. 33// MetaChunk: kMetadataSize bytes of metadata associated with a UserChunk. 34 35// FreeArray is an array free-d chunks (stored as 4-byte offsets) 36// 37// A Region looks like this: 38// UserChunk1 ... UserChunkN <gap> MetaChunkN ... MetaChunk1 FreeArray 39 40struct SizeClassAllocator64FlagMasks { // Bit masks. 41 enum { 42 kRandomShuffleChunks = 1, 43 }; 44}; 45 46template <class Params> 47class SizeClassAllocator64 { 48 public: 49 static const uptr kSpaceBeg = Params::kSpaceBeg; 50 static const uptr kSpaceSize = Params::kSpaceSize; 51 static const uptr kMetadataSize = Params::kMetadataSize; 52 typedef typename Params::SizeClassMap SizeClassMap; 53 typedef typename Params::MapUnmapCallback MapUnmapCallback; 54 55 static const bool kRandomShuffleChunks = 56 Params::kFlags & SizeClassAllocator64FlagMasks::kRandomShuffleChunks; 57 58 typedef SizeClassAllocator64<Params> ThisT; 59 typedef SizeClassAllocator64LocalCache<ThisT> AllocatorCache; 60 61 // When we know the size class (the region base) we can represent a pointer 62 // as a 4-byte integer (offset from the region start shifted right by 4). 63 typedef u32 CompactPtrT; 64 static const uptr kCompactPtrScale = 4; 65 CompactPtrT PointerToCompactPtr(uptr base, uptr ptr) { 66 return static_cast<CompactPtrT>((ptr - base) >> kCompactPtrScale); 67 } 68 uptr CompactPtrToPointer(uptr base, CompactPtrT ptr32) { 69 return base + (static_cast<uptr>(ptr32) << kCompactPtrScale); 70 } 71 72 void Init(s32 release_to_os_interval_ms) { 73 uptr TotalSpaceSize = kSpaceSize + AdditionalSize(); 74 if (kUsingConstantSpaceBeg) { 75 CHECK_EQ(kSpaceBeg, reinterpret_cast<uptr>( 76 MmapFixedNoAccess(kSpaceBeg, TotalSpaceSize))); 77 } else { 78 NonConstSpaceBeg = 79 reinterpret_cast<uptr>(MmapNoAccess(TotalSpaceSize)); 80 CHECK_NE(NonConstSpaceBeg, ~(uptr)0); 81 } 82 SetReleaseToOSIntervalMs(release_to_os_interval_ms); 83 MapWithCallback(SpaceEnd(), AdditionalSize()); 84 } 85 86 s32 ReleaseToOSIntervalMs() const { 87 return atomic_load(&release_to_os_interval_ms_, memory_order_relaxed); 88 } 89 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 95 void MapWithCallback(uptr beg, uptr size) { 96 CHECK_EQ(beg, reinterpret_cast<uptr>(MmapFixedOrDie(beg, size))); 97 MapUnmapCallback().OnMap(beg, size); 98 } 99 100 void UnmapWithCallback(uptr beg, uptr size) { 101 MapUnmapCallback().OnUnmap(beg, size); 102 UnmapOrDie(reinterpret_cast<void *>(beg), size); 103 } 104 105 static bool CanAllocate(uptr size, uptr alignment) { 106 return size <= SizeClassMap::kMaxSize && 107 alignment <= SizeClassMap::kMaxSize; 108 } 109 110 NOINLINE void ReturnToAllocator(AllocatorStats *stat, uptr class_id, 111 const CompactPtrT *chunks, uptr n_chunks) { 112 RegionInfo *region = GetRegionInfo(class_id); 113 uptr region_beg = GetRegionBeginBySizeClass(class_id); 114 CompactPtrT *free_array = GetFreeArray(region_beg); 115 116 BlockingMutexLock l(®ion->mutex); 117 uptr old_num_chunks = region->num_freed_chunks; 118 uptr new_num_freed_chunks = old_num_chunks + n_chunks; 119 EnsureFreeArraySpace(region, region_beg, new_num_freed_chunks); 120 for (uptr i = 0; i < n_chunks; i++) 121 free_array[old_num_chunks + i] = chunks[i]; 122 region->num_freed_chunks = new_num_freed_chunks; 123 region->n_freed += n_chunks; 124 125 MaybeReleaseToOS(class_id); 126 } 127 128 NOINLINE void GetFromAllocator(AllocatorStats *stat, uptr class_id, 129 CompactPtrT *chunks, uptr n_chunks) { 130 RegionInfo *region = GetRegionInfo(class_id); 131 uptr region_beg = GetRegionBeginBySizeClass(class_id); 132 CompactPtrT *free_array = GetFreeArray(region_beg); 133 134 BlockingMutexLock l(®ion->mutex); 135 if (UNLIKELY(region->num_freed_chunks < n_chunks)) { 136 PopulateFreeArray(stat, class_id, region, 137 n_chunks - region->num_freed_chunks); 138 CHECK_GE(region->num_freed_chunks, n_chunks); 139 } 140 region->num_freed_chunks -= n_chunks; 141 uptr base_idx = region->num_freed_chunks; 142 for (uptr i = 0; i < n_chunks; i++) 143 chunks[i] = free_array[base_idx + i]; 144 region->n_allocated += n_chunks; 145 } 146 147 148 bool PointerIsMine(const void *p) { 149 uptr P = reinterpret_cast<uptr>(p); 150 if (kUsingConstantSpaceBeg && (kSpaceBeg % kSpaceSize) == 0) 151 return P / kSpaceSize == kSpaceBeg / kSpaceSize; 152 return P >= SpaceBeg() && P < SpaceEnd(); 153 } 154 155 uptr GetRegionBegin(const void *p) { 156 if (kUsingConstantSpaceBeg) 157 return reinterpret_cast<uptr>(p) & ~(kRegionSize - 1); 158 uptr space_beg = SpaceBeg(); 159 return ((reinterpret_cast<uptr>(p) - space_beg) & ~(kRegionSize - 1)) + 160 space_beg; 161 } 162 163 uptr GetRegionBeginBySizeClass(uptr class_id) { 164 return SpaceBeg() + kRegionSize * class_id; 165 } 166 167 uptr GetSizeClass(const void *p) { 168 if (kUsingConstantSpaceBeg && (kSpaceBeg % kSpaceSize) == 0) 169 return ((reinterpret_cast<uptr>(p)) / kRegionSize) % kNumClassesRounded; 170 return ((reinterpret_cast<uptr>(p) - SpaceBeg()) / kRegionSize) % 171 kNumClassesRounded; 172 } 173 174 void *GetBlockBegin(const void *p) { 175 uptr class_id = GetSizeClass(p); 176 uptr size = ClassIdToSize(class_id); 177 if (!size) return nullptr; 178 uptr chunk_idx = GetChunkIdx((uptr)p, size); 179 uptr reg_beg = GetRegionBegin(p); 180 uptr beg = chunk_idx * size; 181 uptr next_beg = beg + size; 182 if (class_id >= kNumClasses) return nullptr; 183 RegionInfo *region = GetRegionInfo(class_id); 184 if (region->mapped_user >= next_beg) 185 return reinterpret_cast<void*>(reg_beg + beg); 186 return nullptr; 187 } 188 189 uptr GetActuallyAllocatedSize(void *p) { 190 CHECK(PointerIsMine(p)); 191 return ClassIdToSize(GetSizeClass(p)); 192 } 193 194 uptr ClassID(uptr size) { return SizeClassMap::ClassID(size); } 195 196 void *GetMetaData(const void *p) { 197 uptr class_id = GetSizeClass(p); 198 uptr size = ClassIdToSize(class_id); 199 uptr chunk_idx = GetChunkIdx(reinterpret_cast<uptr>(p), size); 200 uptr region_beg = GetRegionBeginBySizeClass(class_id); 201 return reinterpret_cast<void *>(GetMetadataEnd(region_beg) - 202 (1 + chunk_idx) * kMetadataSize); 203 } 204 205 uptr TotalMemoryUsed() { 206 uptr res = 0; 207 for (uptr i = 0; i < kNumClasses; i++) 208 res += GetRegionInfo(i)->allocated_user; 209 return res; 210 } 211 212 // Test-only. 213 void TestOnlyUnmap() { 214 UnmapWithCallback(SpaceBeg(), kSpaceSize + AdditionalSize()); 215 } 216 217 static void FillMemoryProfile(uptr start, uptr rss, bool file, uptr *stats, 218 uptr stats_size) { 219 for (uptr class_id = 0; class_id < stats_size; class_id++) 220 if (stats[class_id] == start) 221 stats[class_id] = rss; 222 } 223 224 void PrintStats(uptr class_id, uptr rss) { 225 RegionInfo *region = GetRegionInfo(class_id); 226 if (region->mapped_user == 0) return; 227 uptr in_use = region->n_allocated - region->n_freed; 228 uptr avail_chunks = region->allocated_user / ClassIdToSize(class_id); 229 Printf( 230 " %02zd (%6zd): mapped: %6zdK allocs: %7zd frees: %7zd inuse: %6zd " 231 "num_freed_chunks %7zd avail: %6zd rss: %6zdK releases: %6zd\n", 232 class_id, ClassIdToSize(class_id), region->mapped_user >> 10, 233 region->n_allocated, region->n_freed, in_use, 234 region->num_freed_chunks, avail_chunks, rss >> 10, 235 region->rtoi.num_releases); 236 } 237 238 void PrintStats() { 239 uptr total_mapped = 0; 240 uptr n_allocated = 0; 241 uptr n_freed = 0; 242 for (uptr class_id = 1; class_id < kNumClasses; class_id++) { 243 RegionInfo *region = GetRegionInfo(class_id); 244 total_mapped += region->mapped_user; 245 n_allocated += region->n_allocated; 246 n_freed += region->n_freed; 247 } 248 Printf("Stats: SizeClassAllocator64: %zdM mapped in %zd allocations; " 249 "remains %zd\n", 250 total_mapped >> 20, n_allocated, n_allocated - n_freed); 251 uptr rss_stats[kNumClasses]; 252 for (uptr class_id = 0; class_id < kNumClasses; class_id++) 253 rss_stats[class_id] = SpaceBeg() + kRegionSize * class_id; 254 GetMemoryProfile(FillMemoryProfile, rss_stats, kNumClasses); 255 for (uptr class_id = 1; class_id < kNumClasses; class_id++) 256 PrintStats(class_id, rss_stats[class_id]); 257 } 258 259 // ForceLock() and ForceUnlock() are needed to implement Darwin malloc zone 260 // introspection API. 261 void ForceLock() { 262 for (uptr i = 0; i < kNumClasses; i++) { 263 GetRegionInfo(i)->mutex.Lock(); 264 } 265 } 266 267 void ForceUnlock() { 268 for (int i = (int)kNumClasses - 1; i >= 0; i--) { 269 GetRegionInfo(i)->mutex.Unlock(); 270 } 271 } 272 273 // Iterate over all existing chunks. 274 // The allocator must be locked when calling this function. 275 void ForEachChunk(ForEachChunkCallback callback, void *arg) { 276 for (uptr class_id = 1; class_id < kNumClasses; class_id++) { 277 RegionInfo *region = GetRegionInfo(class_id); 278 uptr chunk_size = ClassIdToSize(class_id); 279 uptr region_beg = SpaceBeg() + class_id * kRegionSize; 280 for (uptr chunk = region_beg; 281 chunk < region_beg + region->allocated_user; 282 chunk += chunk_size) { 283 // Too slow: CHECK_EQ((void *)chunk, GetBlockBegin((void *)chunk)); 284 callback(chunk, arg); 285 } 286 } 287 } 288 289 static uptr ClassIdToSize(uptr class_id) { 290 return SizeClassMap::Size(class_id); 291 } 292 293 static uptr AdditionalSize() { 294 return RoundUpTo(sizeof(RegionInfo) * kNumClassesRounded, 295 GetPageSizeCached()); 296 } 297 298 typedef SizeClassMap SizeClassMapT; 299 static const uptr kNumClasses = SizeClassMap::kNumClasses; 300 static const uptr kNumClassesRounded = SizeClassMap::kNumClassesRounded; 301 302 private: 303 static const uptr kRegionSize = kSpaceSize / kNumClassesRounded; 304 // FreeArray is the array of free-d chunks (stored as 4-byte offsets). 305 // In the worst case it may reguire kRegionSize/SizeClassMap::kMinSize 306 // elements, but in reality this will not happen. For simplicity we 307 // dedicate 1/8 of the region's virtual space to FreeArray. 308 static const uptr kFreeArraySize = kRegionSize / 8; 309 310 static const bool kUsingConstantSpaceBeg = kSpaceBeg != ~(uptr)0; 311 uptr NonConstSpaceBeg; 312 uptr SpaceBeg() const { 313 return kUsingConstantSpaceBeg ? kSpaceBeg : NonConstSpaceBeg; 314 } 315 uptr SpaceEnd() const { return SpaceBeg() + kSpaceSize; } 316 // kRegionSize must be >= 2^32. 317 COMPILER_CHECK((kRegionSize) >= (1ULL << (SANITIZER_WORDSIZE / 2))); 318 // kRegionSize must be <= 2^36, see CompactPtrT. 319 COMPILER_CHECK((kRegionSize) <= (1ULL << (SANITIZER_WORDSIZE / 2 + 4))); 320 // Call mmap for user memory with at least this size. 321 static const uptr kUserMapSize = 1 << 16; 322 // Call mmap for metadata memory with at least this size. 323 static const uptr kMetaMapSize = 1 << 16; 324 // Call mmap for free array memory with at least this size. 325 static const uptr kFreeArrayMapSize = 1 << 16; 326 327 atomic_sint32_t release_to_os_interval_ms_; 328 329 struct ReleaseToOsInfo { 330 uptr n_freed_at_last_release; 331 uptr num_releases; 332 u64 last_release_at_ns; 333 }; 334 335 struct RegionInfo { 336 BlockingMutex mutex; 337 uptr num_freed_chunks; // Number of elements in the freearray. 338 uptr mapped_free_array; // Bytes mapped for freearray. 339 uptr allocated_user; // Bytes allocated for user memory. 340 uptr allocated_meta; // Bytes allocated for metadata. 341 uptr mapped_user; // Bytes mapped for user memory. 342 uptr mapped_meta; // Bytes mapped for metadata. 343 u32 rand_state; // Seed for random shuffle, used if kRandomShuffleChunks. 344 uptr n_allocated, n_freed; // Just stats. 345 ReleaseToOsInfo rtoi; 346 }; 347 COMPILER_CHECK(sizeof(RegionInfo) >= kCacheLineSize); 348 349 u32 Rand(u32 *state) { // ANSI C linear congruential PRNG. 350 return (*state = *state * 1103515245 + 12345) >> 16; 351 } 352 353 u32 RandN(u32 *state, u32 n) { return Rand(state) % n; } // [0, n) 354 355 void RandomShuffle(u32 *a, u32 n, u32 *rand_state) { 356 if (n <= 1) return; 357 for (u32 i = n - 1; i > 0; i--) 358 Swap(a[i], a[RandN(rand_state, i + 1)]); 359 } 360 361 RegionInfo *GetRegionInfo(uptr class_id) { 362 CHECK_LT(class_id, kNumClasses); 363 RegionInfo *regions = 364 reinterpret_cast<RegionInfo *>(SpaceBeg() + kSpaceSize); 365 return ®ions[class_id]; 366 } 367 368 uptr GetMetadataEnd(uptr region_beg) { 369 return region_beg + kRegionSize - kFreeArraySize; 370 } 371 372 uptr GetChunkIdx(uptr chunk, uptr size) { 373 if (!kUsingConstantSpaceBeg) 374 chunk -= SpaceBeg(); 375 376 uptr offset = chunk % kRegionSize; 377 // Here we divide by a non-constant. This is costly. 378 // size always fits into 32-bits. If the offset fits too, use 32-bit div. 379 if (offset >> (SANITIZER_WORDSIZE / 2)) 380 return offset / size; 381 return (u32)offset / (u32)size; 382 } 383 384 CompactPtrT *GetFreeArray(uptr region_beg) { 385 return reinterpret_cast<CompactPtrT *>(region_beg + kRegionSize - 386 kFreeArraySize); 387 } 388 389 void EnsureFreeArraySpace(RegionInfo *region, uptr region_beg, 390 uptr num_freed_chunks) { 391 uptr needed_space = num_freed_chunks * sizeof(CompactPtrT); 392 if (region->mapped_free_array < needed_space) { 393 CHECK_LE(needed_space, kFreeArraySize); 394 uptr new_mapped_free_array = RoundUpTo(needed_space, kFreeArrayMapSize); 395 uptr current_map_end = reinterpret_cast<uptr>(GetFreeArray(region_beg)) + 396 region->mapped_free_array; 397 uptr new_map_size = new_mapped_free_array - region->mapped_free_array; 398 MapWithCallback(current_map_end, new_map_size); 399 region->mapped_free_array = new_mapped_free_array; 400 } 401 } 402 403 404 NOINLINE void PopulateFreeArray(AllocatorStats *stat, uptr class_id, 405 RegionInfo *region, uptr requested_count) { 406 // region->mutex is held. 407 uptr size = ClassIdToSize(class_id); 408 uptr beg_idx = region->allocated_user; 409 uptr end_idx = beg_idx + requested_count * size; 410 uptr region_beg = GetRegionBeginBySizeClass(class_id); 411 if (end_idx > region->mapped_user) { 412 if (!kUsingConstantSpaceBeg && region->mapped_user == 0) 413 region->rand_state = static_cast<u32>(region_beg >> 12); // From ASLR. 414 // Do the mmap for the user memory. 415 uptr map_size = kUserMapSize; 416 while (end_idx > region->mapped_user + map_size) 417 map_size += kUserMapSize; 418 CHECK_GE(region->mapped_user + map_size, end_idx); 419 MapWithCallback(region_beg + region->mapped_user, map_size); 420 stat->Add(AllocatorStatMapped, map_size); 421 region->mapped_user += map_size; 422 } 423 CompactPtrT *free_array = GetFreeArray(region_beg); 424 uptr total_count = (region->mapped_user - beg_idx) / size; 425 uptr num_freed_chunks = region->num_freed_chunks; 426 EnsureFreeArraySpace(region, region_beg, num_freed_chunks + total_count); 427 for (uptr i = 0; i < total_count; i++) { 428 uptr chunk = beg_idx + i * size; 429 free_array[num_freed_chunks + total_count - 1 - i] = 430 PointerToCompactPtr(0, chunk); 431 } 432 if (kRandomShuffleChunks) 433 RandomShuffle(&free_array[num_freed_chunks], total_count, 434 ®ion->rand_state); 435 region->num_freed_chunks += total_count; 436 region->allocated_user += total_count * size; 437 CHECK_LE(region->allocated_user, region->mapped_user); 438 439 region->allocated_meta += total_count * kMetadataSize; 440 if (region->allocated_meta > region->mapped_meta) { 441 uptr map_size = kMetaMapSize; 442 while (region->allocated_meta > region->mapped_meta + map_size) 443 map_size += kMetaMapSize; 444 // Do the mmap for the metadata. 445 CHECK_GE(region->mapped_meta + map_size, region->allocated_meta); 446 MapWithCallback(GetMetadataEnd(region_beg) - 447 region->mapped_meta - map_size, map_size); 448 region->mapped_meta += map_size; 449 } 450 CHECK_LE(region->allocated_meta, region->mapped_meta); 451 if (region->mapped_user + region->mapped_meta > 452 kRegionSize - kFreeArraySize) { 453 Printf("%s: Out of memory. Dying. ", SanitizerToolName); 454 Printf("The process has exhausted %zuMB for size class %zu.\n", 455 kRegionSize / 1024 / 1024, size); 456 Die(); 457 } 458 } 459 460 void MaybeReleaseChunkRange(uptr region_beg, uptr chunk_size, 461 CompactPtrT first, CompactPtrT last) { 462 uptr beg_ptr = CompactPtrToPointer(region_beg, first); 463 uptr end_ptr = CompactPtrToPointer(region_beg, last) + chunk_size; 464 ReleaseMemoryPagesToOS(beg_ptr, end_ptr); 465 } 466 467 // Attempts to release some RAM back to OS. The region is expected to be 468 // locked. 469 // Algorithm: 470 // * Sort the chunks. 471 // * Find ranges fully covered by free-d chunks 472 // * Release them to OS with madvise. 473 void MaybeReleaseToOS(uptr class_id) { 474 RegionInfo *region = GetRegionInfo(class_id); 475 const uptr chunk_size = ClassIdToSize(class_id); 476 const uptr page_size = GetPageSizeCached(); 477 478 uptr n = region->num_freed_chunks; 479 if (n * chunk_size < page_size) 480 return; // No chance to release anything. 481 if ((region->n_freed - region->rtoi.n_freed_at_last_release) * chunk_size < 482 page_size) { 483 return; // Nothing new to release. 484 } 485 486 s32 interval_ms = ReleaseToOSIntervalMs(); 487 if (interval_ms < 0) 488 return; 489 490 u64 now_ns = NanoTime(); 491 if (region->rtoi.last_release_at_ns + interval_ms * 1000000ULL > now_ns) 492 return; // Memory was returned recently. 493 region->rtoi.last_release_at_ns = now_ns; 494 495 uptr region_beg = GetRegionBeginBySizeClass(class_id); 496 CompactPtrT *free_array = GetFreeArray(region_beg); 497 SortArray(free_array, n); 498 499 const uptr scaled_chunk_size = chunk_size >> kCompactPtrScale; 500 const uptr kScaledGranularity = page_size >> kCompactPtrScale; 501 502 uptr range_beg = free_array[0]; 503 uptr prev = free_array[0]; 504 for (uptr i = 1; i < n; i++) { 505 uptr chunk = free_array[i]; 506 CHECK_GT(chunk, prev); 507 if (chunk - prev != scaled_chunk_size) { 508 CHECK_GT(chunk - prev, scaled_chunk_size); 509 if (prev + scaled_chunk_size - range_beg >= kScaledGranularity) { 510 MaybeReleaseChunkRange(region_beg, chunk_size, range_beg, prev); 511 region->rtoi.n_freed_at_last_release = region->n_freed; 512 region->rtoi.num_releases++; 513 } 514 range_beg = chunk; 515 } 516 prev = chunk; 517 } 518 } 519}; 520 521 522