sanitizer_allocator.h revision 567ad078d73babb2c8addfbebb1ddd6cd0085c53
1//===-- sanitizer_allocator.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// Specialized memory allocator for ThreadSanitizer, MemorySanitizer, etc. 11// 12//===----------------------------------------------------------------------===// 13 14#ifndef SANITIZER_ALLOCATOR_H 15#define SANITIZER_ALLOCATOR_H 16 17#include "sanitizer_internal_defs.h" 18#include "sanitizer_common.h" 19#include "sanitizer_libc.h" 20#include "sanitizer_list.h" 21#include "sanitizer_mutex.h" 22 23namespace __sanitizer { 24 25// Maps size class id to size and back. 26template <uptr l0, uptr l1, uptr l2, uptr l3, uptr l4, uptr l5, 27 uptr s0, uptr s1, uptr s2, uptr s3, uptr s4, 28 uptr c0, uptr c1, uptr c2, uptr c3, uptr c4> 29class SplineSizeClassMap { 30 private: 31 // Here we use a spline composed of 5 polynomials of oder 1. 32 // The first size class is l0, then the classes go with step s0 33 // untill they reach l1, after which they go with step s1 and so on. 34 // Steps should be powers of two for cheap division. 35 // The size of the last size class should be a power of two. 36 // There should be at most 256 size classes. 37 static const uptr u0 = 0 + (l1 - l0) / s0; 38 static const uptr u1 = u0 + (l2 - l1) / s1; 39 static const uptr u2 = u1 + (l3 - l2) / s2; 40 static const uptr u3 = u2 + (l4 - l3) / s3; 41 static const uptr u4 = u3 + (l5 - l4) / s4; 42 43 public: 44 // The number of size classes should be a power of two for fast division. 45 static const uptr kNumClasses = u4 + 1; 46 static const uptr kMaxSize = l5; 47 static const uptr kMinSize = l0; 48 49 COMPILER_CHECK(kNumClasses <= 256); 50 COMPILER_CHECK((kNumClasses & (kNumClasses - 1)) == 0); 51 COMPILER_CHECK((kMaxSize & (kMaxSize - 1)) == 0); 52 53 static uptr Size(uptr class_id) { 54 if (class_id <= u0) return l0 + s0 * (class_id - 0); 55 if (class_id <= u1) return l1 + s1 * (class_id - u0); 56 if (class_id <= u2) return l2 + s2 * (class_id - u1); 57 if (class_id <= u3) return l3 + s3 * (class_id - u2); 58 if (class_id <= u4) return l4 + s4 * (class_id - u3); 59 return 0; 60 } 61 static uptr ClassID(uptr size) { 62 if (size <= l1) return 0 + (size - l0 + s0 - 1) / s0; 63 if (size <= l2) return u0 + (size - l1 + s1 - 1) / s1; 64 if (size <= l3) return u1 + (size - l2 + s2 - 1) / s2; 65 if (size <= l4) return u2 + (size - l3 + s3 - 1) / s3; 66 if (size <= l5) return u3 + (size - l4 + s4 - 1) / s4; 67 return 0; 68 } 69 70 static uptr MaxCached(uptr class_id) { 71 if (class_id <= u0) return c0; 72 if (class_id <= u1) return c1; 73 if (class_id <= u2) return c2; 74 if (class_id <= u3) return c3; 75 if (class_id <= u4) return c4; 76 return 0; 77 } 78}; 79 80class DefaultSizeClassMap: public SplineSizeClassMap< 81 /* l: */1 << 4, 1 << 9, 1 << 12, 1 << 15, 1 << 18, 1 << 21, 82 /* s: */1 << 4, 1 << 6, 1 << 9, 1 << 12, 1 << 15, 83 /* c: */256, 64, 16, 4, 1> { 84 private: 85 COMPILER_CHECK(kNumClasses == 256); 86}; 87 88class CompactSizeClassMap: public SplineSizeClassMap< 89 /* l: */1 << 3, 1 << 4, 1 << 7, 1 << 8, 1 << 12, 1 << 15, 90 /* s: */1 << 3, 1 << 4, 1 << 7, 1 << 8, 1 << 12, 91 /* c: */256, 64, 16, 4, 1> { 92 private: 93 COMPILER_CHECK(kNumClasses <= 32); 94}; 95 96struct AllocatorListNode { 97 AllocatorListNode *next; 98}; 99 100typedef IntrusiveList<AllocatorListNode> AllocatorFreeList; 101 102// Move at most max_count chunks from allocate_from to allocate_to. 103// This function is better be a method of AllocatorFreeList, but we can't 104// inherit it from IntrusiveList as the ancient gcc complains about non-PODness. 105static inline void BulkMove(uptr max_count, 106 AllocatorFreeList *allocate_from, 107 AllocatorFreeList *allocate_to) { 108 CHECK(!allocate_from->empty()); 109 CHECK(allocate_to->empty()); 110 if (allocate_from->size() <= max_count) { 111 allocate_to->append_front(allocate_from); 112 CHECK(allocate_from->empty()); 113 } else { 114 for (uptr i = 0; i < max_count; i++) { 115 AllocatorListNode *node = allocate_from->front(); 116 allocate_from->pop_front(); 117 allocate_to->push_front(node); 118 } 119 CHECK(!allocate_from->empty()); 120 } 121 CHECK(!allocate_to->empty()); 122} 123 124// Allocators call these callbacks on mmap/munmap. 125struct NoOpMapUnmapCallback { 126 void OnMap(uptr p, uptr size) const { } 127 void OnUnmap(uptr p, uptr size) const { } 128}; 129 130// SizeClassAllocator64 -- allocator for 64-bit address space. 131// 132// Space: a portion of address space of kSpaceSize bytes starting at 133// a fixed address (kSpaceBeg). Both constants are powers of two and 134// kSpaceBeg is kSpaceSize-aligned. 135// At the beginning the entire space is mprotect-ed, then small parts of it 136// are mapped on demand. 137// 138// Region: a part of Space dedicated to a single size class. 139// There are kNumClasses Regions of equal size. 140// 141// UserChunk: a piece of memory returned to user. 142// MetaChunk: kMetadataSize bytes of metadata associated with a UserChunk. 143// 144// A Region looks like this: 145// UserChunk1 ... UserChunkN <gap> MetaChunkN ... MetaChunk1 146template <const uptr kSpaceBeg, const uptr kSpaceSize, 147 const uptr kMetadataSize, class SizeClassMap, 148 class MapUnmapCallback = NoOpMapUnmapCallback> 149class SizeClassAllocator64 { 150 public: 151 void Init() { 152 CHECK_EQ(kSpaceBeg, 153 reinterpret_cast<uptr>(Mprotect(kSpaceBeg, kSpaceSize))); 154 MapWithCallback(kSpaceEnd, AdditionalSize()); 155 } 156 157 void MapWithCallback(uptr beg, uptr size) { 158 CHECK_EQ(beg, reinterpret_cast<uptr>(MmapFixedNoReserve(beg, size))); 159 MapUnmapCallback().OnMap(beg, size); 160 } 161 162 void UnmapWithCallback(uptr beg, uptr size) { 163 MapUnmapCallback().OnUnmap(beg, size); 164 UnmapOrDie(reinterpret_cast<void *>(beg), size); 165 } 166 167 bool CanAllocate(uptr size, uptr alignment) { 168 return size <= SizeClassMap::kMaxSize && 169 alignment <= SizeClassMap::kMaxSize; 170 } 171 172 void *Allocate(uptr size, uptr alignment) { 173 if (size < alignment) size = alignment; 174 CHECK(CanAllocate(size, alignment)); 175 return AllocateBySizeClass(ClassID(size)); 176 } 177 178 void Deallocate(void *p) { 179 CHECK(PointerIsMine(p)); 180 DeallocateBySizeClass(p, GetSizeClass(p)); 181 } 182 183 // Allocate several chunks of the given class_id. 184 void BulkAllocate(uptr class_id, AllocatorFreeList *free_list) { 185 CHECK_LT(class_id, kNumClasses); 186 RegionInfo *region = GetRegionInfo(class_id); 187 SpinMutexLock l(®ion->mutex); 188 if (region->free_list.empty()) { 189 PopulateFreeList(class_id, region); 190 } 191 BulkMove(SizeClassMap::MaxCached(class_id), ®ion->free_list, free_list); 192 } 193 194 // Swallow the entire free_list for the given class_id. 195 void BulkDeallocate(uptr class_id, AllocatorFreeList *free_list) { 196 CHECK_LT(class_id, kNumClasses); 197 RegionInfo *region = GetRegionInfo(class_id); 198 SpinMutexLock l(®ion->mutex); 199 region->free_list.append_front(free_list); 200 } 201 202 static bool PointerIsMine(void *p) { 203 return reinterpret_cast<uptr>(p) / kSpaceSize == kSpaceBeg / kSpaceSize; 204 } 205 206 static uptr GetSizeClass(void *p) { 207 return (reinterpret_cast<uptr>(p) / kRegionSize) % kNumClasses; 208 } 209 210 static void *GetBlockBegin(void *p) { 211 uptr class_id = GetSizeClass(p); 212 uptr size = SizeClassMap::Size(class_id); 213 uptr chunk_idx = GetChunkIdx((uptr)p, size); 214 uptr reg_beg = (uptr)p & ~(kRegionSize - 1); 215 uptr begin = reg_beg + chunk_idx * size; 216 return reinterpret_cast<void*>(begin); 217 } 218 219 static uptr GetActuallyAllocatedSize(void *p) { 220 CHECK(PointerIsMine(p)); 221 return SizeClassMap::Size(GetSizeClass(p)); 222 } 223 224 uptr ClassID(uptr size) { return SizeClassMap::ClassID(size); } 225 226 void *GetMetaData(void *p) { 227 uptr class_id = GetSizeClass(p); 228 uptr size = SizeClassMap::Size(class_id); 229 uptr chunk_idx = GetChunkIdx(reinterpret_cast<uptr>(p), size); 230 return reinterpret_cast<void*>(kSpaceBeg + (kRegionSize * (class_id + 1)) - 231 (1 + chunk_idx) * kMetadataSize); 232 } 233 234 uptr TotalMemoryUsed() { 235 uptr res = 0; 236 for (uptr i = 0; i < kNumClasses; i++) 237 res += GetRegionInfo(i)->allocated_user; 238 return res; 239 } 240 241 // Test-only. 242 void TestOnlyUnmap() { 243 UnmapWithCallback(kSpaceBeg, kSpaceSize + AdditionalSize()); 244 } 245 246 typedef SizeClassMap SizeClassMapT; 247 static const uptr kNumClasses = SizeClassMap::kNumClasses; // 2^k <= 256 248 249 private: 250 static const uptr kRegionSize = kSpaceSize / kNumClasses; 251 static const uptr kSpaceEnd = kSpaceBeg + kSpaceSize; 252 COMPILER_CHECK(kSpaceBeg % kSpaceSize == 0); 253 // kRegionSize must be >= 2^32. 254 COMPILER_CHECK((kRegionSize) >= (1ULL << (SANITIZER_WORDSIZE / 2))); 255 // Populate the free list with at most this number of bytes at once 256 // or with one element if its size is greater. 257 static const uptr kPopulateSize = 1 << 18; 258 // Call mmap for user memory with this size. 259 static const uptr kUserMapSize = 1 << 22; 260 // Call mmap for metadata memory with this size. 261 static const uptr kMetaMapSize = 1 << 20; 262 263 struct RegionInfo { 264 SpinMutex mutex; 265 AllocatorFreeList free_list; 266 uptr allocated_user; // Bytes allocated for user memory. 267 uptr allocated_meta; // Bytes allocated for metadata. 268 uptr mapped_user; // Bytes mapped for user memory. 269 uptr mapped_meta; // Bytes mapped for metadata. 270 }; 271 COMPILER_CHECK(sizeof(RegionInfo) >= kCacheLineSize); 272 273 static uptr AdditionalSize() { 274 uptr PageSize = GetPageSizeCached(); 275 uptr res = Max(sizeof(RegionInfo) * kNumClasses, PageSize); 276 CHECK_EQ(res % PageSize, 0); 277 return res; 278 } 279 280 RegionInfo *GetRegionInfo(uptr class_id) { 281 CHECK_LT(class_id, kNumClasses); 282 RegionInfo *regions = reinterpret_cast<RegionInfo*>(kSpaceBeg + kSpaceSize); 283 return ®ions[class_id]; 284 } 285 286 static uptr GetChunkIdx(uptr chunk, uptr size) { 287 u32 offset = chunk % kRegionSize; 288 // Here we divide by a non-constant. This is costly. 289 // We require that kRegionSize is at least 2^32 so that offset is 32-bit. 290 // We save 2x by using 32-bit div, but may need to use a 256-way switch. 291 return offset / (u32)size; 292 } 293 294 void PopulateFreeList(uptr class_id, RegionInfo *region) { 295 CHECK(region->free_list.empty()); 296 uptr size = SizeClassMap::Size(class_id); 297 uptr beg_idx = region->allocated_user; 298 uptr end_idx = beg_idx + kPopulateSize; 299 uptr region_beg = kSpaceBeg + kRegionSize * class_id; 300 if (end_idx > region->mapped_user) { 301 // Do the mmap for the user memory. 302 CHECK_GT(region->mapped_user + kUserMapSize, end_idx); 303 MapWithCallback(region_beg + region->mapped_user, kUserMapSize); 304 region->mapped_user += kUserMapSize; 305 } 306 uptr idx = beg_idx; 307 uptr i = 0; 308 do { // do-while loop because we need to put at least one item. 309 uptr p = region_beg + idx; 310 region->free_list.push_front(reinterpret_cast<AllocatorListNode*>(p)); 311 idx += size; 312 i++; 313 } while (idx < end_idx); 314 region->allocated_user += idx - beg_idx; 315 region->allocated_meta += i * kMetadataSize; 316 if (region->allocated_meta > region->mapped_meta) { 317 // Do the mmap for the metadata. 318 CHECK_GT(region->mapped_meta + kMetaMapSize, region->allocated_meta); 319 MapWithCallback(region_beg + kRegionSize - 320 region->mapped_meta - kMetaMapSize, kMetaMapSize); 321 region->mapped_meta += kMetaMapSize; 322 } 323 if (region->allocated_user + region->allocated_meta > kRegionSize) { 324 Printf("Out of memory. Dying.\n"); 325 Printf("The process has exhausted %zuMB for size class %zu.\n", 326 kRegionSize / 1024 / 1024, size); 327 Die(); 328 } 329 } 330 331 void *AllocateBySizeClass(uptr class_id) { 332 CHECK_LT(class_id, kNumClasses); 333 RegionInfo *region = GetRegionInfo(class_id); 334 SpinMutexLock l(®ion->mutex); 335 if (region->free_list.empty()) { 336 PopulateFreeList(class_id, region); 337 } 338 CHECK(!region->free_list.empty()); 339 AllocatorListNode *node = region->free_list.front(); 340 region->free_list.pop_front(); 341 return reinterpret_cast<void*>(node); 342 } 343 344 void DeallocateBySizeClass(void *p, uptr class_id) { 345 RegionInfo *region = GetRegionInfo(class_id); 346 SpinMutexLock l(®ion->mutex); 347 region->free_list.push_front(reinterpret_cast<AllocatorListNode*>(p)); 348 } 349}; 350 351// SizeClassAllocator32 -- allocator for 32-bit address space. 352// This allocator can theoretically be used on 64-bit arch, but there it is less 353// efficient than SizeClassAllocator64. 354// 355// [kSpaceBeg, kSpaceBeg + kSpaceSize) is the range of addresses which can 356// be returned by MmapOrDie(). 357// 358// Region: 359// a result of a single call to MmapAlignedOrDie(kRegionSize, kRegionSize). 360// Since the regions are aligned by kRegionSize, there are exactly 361// kNumPossibleRegions possible regions in the address space and so we keep 362// an u8 array possible_regions[kNumPossibleRegions] to store the size classes. 363// 0 size class means the region is not used by the allocator. 364// 365// One Region is used to allocate chunks of a single size class. 366// A Region looks like this: 367// UserChunk1 .. UserChunkN <gap> MetaChunkN .. MetaChunk1 368// 369// In order to avoid false sharing the objects of this class should be 370// chache-line aligned. 371template <const uptr kSpaceBeg, const u64 kSpaceSize, 372 const uptr kMetadataSize, class SizeClassMap, 373 class MapUnmapCallback = NoOpMapUnmapCallback> 374class SizeClassAllocator32 { 375 public: 376 void Init() { 377 state_ = reinterpret_cast<State *>(MapWithCallback(sizeof(State))); 378 } 379 380 void *MapWithCallback(uptr size) { 381 size = RoundUpTo(size, GetPageSizeCached()); 382 void *res = MmapOrDie(size, "SizeClassAllocator32"); 383 MapUnmapCallback().OnMap((uptr)res, size); 384 return res; 385 } 386 void UnmapWithCallback(uptr beg, uptr size) { 387 MapUnmapCallback().OnUnmap(beg, size); 388 UnmapOrDie(reinterpret_cast<void *>(beg), size); 389 } 390 391 bool CanAllocate(uptr size, uptr alignment) { 392 return size <= SizeClassMap::kMaxSize && 393 alignment <= SizeClassMap::kMaxSize; 394 } 395 396 void *Allocate(uptr size, uptr alignment) { 397 if (size < alignment) size = alignment; 398 CHECK(CanAllocate(size, alignment)); 399 return AllocateBySizeClass(ClassID(size)); 400 } 401 402 void Deallocate(void *p) { 403 CHECK(PointerIsMine(p)); 404 DeallocateBySizeClass(p, GetSizeClass(p)); 405 } 406 407 void *GetMetaData(void *p) { 408 CHECK(PointerIsMine(p)); 409 uptr mem = reinterpret_cast<uptr>(p); 410 uptr beg = ComputeRegionBeg(mem); 411 uptr size = SizeClassMap::Size(GetSizeClass(p)); 412 u32 offset = mem - beg; 413 uptr n = offset / (u32)size; // 32-bit division 414 uptr meta = (beg + kRegionSize) - (n + 1) * kMetadataSize; 415 return reinterpret_cast<void*>(meta); 416 } 417 418 // Allocate several chunks of the given class_id. 419 void BulkAllocate(uptr class_id, AllocatorFreeList *free_list) { 420 SizeClassInfo *sci = GetSizeClassInfo(class_id); 421 SpinMutexLock l(&sci->mutex); 422 EnsureSizeClassHasAvailableChunks(sci, class_id); 423 CHECK(!sci->free_list.empty()); 424 BulkMove(SizeClassMap::MaxCached(class_id), &sci->free_list, free_list); 425 } 426 427 // Swallow the entire free_list for the given class_id. 428 void BulkDeallocate(uptr class_id, AllocatorFreeList *free_list) { 429 SizeClassInfo *sci = GetSizeClassInfo(class_id); 430 SpinMutexLock l(&sci->mutex); 431 sci->free_list.append_front(free_list); 432 } 433 434 bool PointerIsMine(void *p) { 435 return 436 state_->possible_regions[ComputeRegionId(reinterpret_cast<uptr>(p))] != 0; 437 } 438 439 uptr GetSizeClass(void *p) { 440 return 441 state_->possible_regions[ComputeRegionId(reinterpret_cast<uptr>(p))] - 1; 442 } 443 444 void *GetBlockBegin(void *p) { 445 CHECK(PointerIsMine(p)); 446 uptr mem = reinterpret_cast<uptr>(p); 447 uptr beg = ComputeRegionBeg(mem); 448 uptr size = SizeClassMap::Size(GetSizeClass(p)); 449 u32 offset = mem - beg; 450 u32 n = offset / (u32)size; // 32-bit division 451 uptr res = beg + (n * (u32)size); 452 return reinterpret_cast<void*>(res); 453 } 454 455 uptr GetActuallyAllocatedSize(void *p) { 456 CHECK(PointerIsMine(p)); 457 return SizeClassMap::Size(GetSizeClass(p)); 458 } 459 460 uptr ClassID(uptr size) { return SizeClassMap::ClassID(size); } 461 462 uptr TotalMemoryUsed() { 463 // No need to lock here. 464 uptr res = 0; 465 for (uptr i = 0; i < kNumPossibleRegions; i++) 466 if (state_->possible_regions[i]) 467 res += kRegionSize; 468 return res; 469 } 470 471 void TestOnlyUnmap() { 472 for (uptr i = 0; i < kNumPossibleRegions; i++) 473 if (state_->possible_regions[i]) 474 UnmapWithCallback((i * kRegionSize), kRegionSize); 475 UnmapWithCallback(reinterpret_cast<uptr>(state_), sizeof(State)); 476 } 477 478 typedef SizeClassMap SizeClassMapT; 479 static const uptr kNumClasses = SizeClassMap::kNumClasses; // 2^k <= 128 480 481 private: 482 static const uptr kRegionSizeLog = SANITIZER_WORDSIZE == 64 ? 24 : 20; 483 static const uptr kRegionSize = 1 << kRegionSizeLog; 484 static const uptr kNumPossibleRegions = kSpaceSize / kRegionSize; 485 COMPILER_CHECK(kNumClasses <= 128); 486 487 struct SizeClassInfo { 488 SpinMutex mutex; 489 AllocatorFreeList free_list; 490 char padding[kCacheLineSize - sizeof(uptr) - sizeof(AllocatorFreeList)]; 491 }; 492 COMPILER_CHECK(sizeof(SizeClassInfo) == kCacheLineSize); 493 494 uptr ComputeRegionId(uptr mem) { 495 uptr res = mem >> kRegionSizeLog; 496 CHECK_LT(res, kNumPossibleRegions); 497 return res; 498 } 499 500 uptr ComputeRegionBeg(uptr mem) { 501 return mem & ~(kRegionSize - 1); 502 } 503 504 uptr AllocateRegion(uptr class_id) { 505 CHECK_LT(class_id, kNumClasses); 506 uptr res = reinterpret_cast<uptr>(MmapAlignedOrDie(kRegionSize, kRegionSize, 507 "SizeClassAllocator32")); 508 MapUnmapCallback().OnMap(res, kRegionSize); 509 CHECK_EQ(0U, (res & (kRegionSize - 1))); 510 CHECK_EQ(0U, state_->possible_regions[ComputeRegionId(res)]); 511 state_->possible_regions[ComputeRegionId(res)] = class_id + 1; 512 return res; 513 } 514 515 SizeClassInfo *GetSizeClassInfo(uptr class_id) { 516 CHECK_LT(class_id, kNumClasses); 517 return &state_->size_class_info_array[class_id]; 518 } 519 520 void EnsureSizeClassHasAvailableChunks(SizeClassInfo *sci, uptr class_id) { 521 if (!sci->free_list.empty()) return; 522 uptr size = SizeClassMap::Size(class_id); 523 uptr reg = AllocateRegion(class_id); 524 uptr n_chunks = kRegionSize / (size + kMetadataSize); 525 for (uptr i = reg; i < reg + n_chunks * size; i += size) 526 sci->free_list.push_back(reinterpret_cast<AllocatorListNode*>(i)); 527 } 528 529 void *AllocateBySizeClass(uptr class_id) { 530 CHECK_LT(class_id, kNumClasses); 531 SizeClassInfo *sci = GetSizeClassInfo(class_id); 532 SpinMutexLock l(&sci->mutex); 533 EnsureSizeClassHasAvailableChunks(sci, class_id); 534 CHECK(!sci->free_list.empty()); 535 AllocatorListNode *node = sci->free_list.front(); 536 sci->free_list.pop_front(); 537 return reinterpret_cast<void*>(node); 538 } 539 540 void DeallocateBySizeClass(void *p, uptr class_id) { 541 CHECK_LT(class_id, kNumClasses); 542 SizeClassInfo *sci = GetSizeClassInfo(class_id); 543 SpinMutexLock l(&sci->mutex); 544 sci->free_list.push_front(reinterpret_cast<AllocatorListNode*>(p)); 545 } 546 547 struct State { 548 u8 possible_regions[kNumPossibleRegions]; 549 SizeClassInfo size_class_info_array[kNumClasses]; 550 }; 551 State *state_; 552}; 553 554// Objects of this type should be used as local caches for SizeClassAllocator64. 555// Since the typical use of this class is to have one object per thread in TLS, 556// is has to be POD. 557template<class SizeClassAllocator> 558struct SizeClassAllocatorLocalCache { 559 typedef SizeClassAllocator Allocator; 560 static const uptr kNumClasses = SizeClassAllocator::kNumClasses; 561 // Don't need to call Init if the object is a global (i.e. zero-initialized). 562 void Init() { 563 internal_memset(this, 0, sizeof(*this)); 564 } 565 566 void *Allocate(SizeClassAllocator *allocator, uptr class_id) { 567 CHECK_LT(class_id, kNumClasses); 568 AllocatorFreeList *free_list = &free_lists_[class_id]; 569 if (free_list->empty()) 570 allocator->BulkAllocate(class_id, free_list); 571 CHECK(!free_list->empty()); 572 void *res = free_list->front(); 573 free_list->pop_front(); 574 return res; 575 } 576 577 void Deallocate(SizeClassAllocator *allocator, uptr class_id, void *p) { 578 CHECK_LT(class_id, kNumClasses); 579 AllocatorFreeList *free_list = &free_lists_[class_id]; 580 free_list->push_front(reinterpret_cast<AllocatorListNode*>(p)); 581 if (free_list->size() >= 2 * SizeClassMap::MaxCached(class_id)) 582 DrainHalf(allocator, class_id); 583 } 584 585 void Drain(SizeClassAllocator *allocator) { 586 for (uptr i = 0; i < kNumClasses; i++) { 587 allocator->BulkDeallocate(i, &free_lists_[i]); 588 CHECK(free_lists_[i].empty()); 589 } 590 } 591 592 // private: 593 typedef typename SizeClassAllocator::SizeClassMapT SizeClassMap; 594 AllocatorFreeList free_lists_[kNumClasses]; 595 596 void DrainHalf(SizeClassAllocator *allocator, uptr class_id) { 597 AllocatorFreeList *free_list = &free_lists_[class_id]; 598 AllocatorFreeList half; 599 half.clear(); 600 const uptr count = free_list->size() / 2; 601 for (uptr i = 0; i < count; i++) { 602 AllocatorListNode *node = free_list->front(); 603 free_list->pop_front(); 604 half.push_front(node); 605 } 606 allocator->BulkDeallocate(class_id, &half); 607 } 608}; 609 610// This class can (de)allocate only large chunks of memory using mmap/unmap. 611// The main purpose of this allocator is to cover large and rare allocation 612// sizes not covered by more efficient allocators (e.g. SizeClassAllocator64). 613template <class MapUnmapCallback = NoOpMapUnmapCallback> 614class LargeMmapAllocator { 615 public: 616 void Init() { 617 internal_memset(this, 0, sizeof(*this)); 618 page_size_ = GetPageSizeCached(); 619 } 620 void *Allocate(uptr size, uptr alignment) { 621 CHECK(IsPowerOfTwo(alignment)); 622 uptr map_size = RoundUpMapSize(size); 623 if (alignment > page_size_) 624 map_size += alignment; 625 if (map_size < size) return 0; // Overflow. 626 uptr map_beg = reinterpret_cast<uptr>( 627 MmapOrDie(map_size, "LargeMmapAllocator")); 628 MapUnmapCallback().OnMap(map_beg, map_size); 629 uptr map_end = map_beg + map_size; 630 uptr res = map_beg + page_size_; 631 if (res & (alignment - 1)) // Align. 632 res += alignment - (res & (alignment - 1)); 633 CHECK_EQ(0, res & (alignment - 1)); 634 CHECK_LE(res + size, map_end); 635 Header *h = GetHeader(res); 636 h->size = size; 637 h->map_beg = map_beg; 638 h->map_size = map_size; 639 { 640 SpinMutexLock l(&mutex_); 641 h->next = list_; 642 h->prev = 0; 643 if (list_) 644 list_->prev = h; 645 list_ = h; 646 } 647 return reinterpret_cast<void*>(res); 648 } 649 650 void Deallocate(void *p) { 651 Header *h = GetHeader(p); 652 { 653 SpinMutexLock l(&mutex_); 654 Header *prev = h->prev; 655 Header *next = h->next; 656 if (prev) 657 prev->next = next; 658 if (next) 659 next->prev = prev; 660 if (h == list_) 661 list_ = next; 662 } 663 MapUnmapCallback().OnUnmap(h->map_beg, h->map_size); 664 UnmapOrDie(reinterpret_cast<void*>(h->map_beg), h->map_size); 665 } 666 667 uptr TotalMemoryUsed() { 668 SpinMutexLock l(&mutex_); 669 uptr res = 0; 670 for (Header *l = list_; l; l = l->next) { 671 res += RoundUpMapSize(l->size); 672 } 673 return res; 674 } 675 676 bool PointerIsMine(void *p) { 677 // Fast check. 678 if ((reinterpret_cast<uptr>(p) & (page_size_ - 1))) return false; 679 SpinMutexLock l(&mutex_); 680 for (Header *l = list_; l; l = l->next) { 681 if (GetUser(l) == p) return true; 682 } 683 return false; 684 } 685 686 uptr GetActuallyAllocatedSize(void *p) { 687 return RoundUpMapSize(GetHeader(p)->size) - page_size_; 688 } 689 690 // At least page_size_/2 metadata bytes is available. 691 void *GetMetaData(void *p) { 692 return GetHeader(p) + 1; 693 } 694 695 void *GetBlockBegin(void *p) { 696 SpinMutexLock l(&mutex_); 697 for (Header *l = list_; l; l = l->next) { 698 void *b = GetUser(l); 699 if (p >= b && p < (u8*)b + l->size) 700 return b; 701 } 702 return 0; 703 } 704 705 private: 706 struct Header { 707 uptr map_beg; 708 uptr map_size; 709 uptr size; 710 Header *next; 711 Header *prev; 712 }; 713 714 Header *GetHeader(uptr p) { 715 CHECK_EQ(p % page_size_, 0); 716 return reinterpret_cast<Header*>(p - page_size_); 717 } 718 Header *GetHeader(void *p) { return GetHeader(reinterpret_cast<uptr>(p)); } 719 720 void *GetUser(Header *h) { 721 CHECK_EQ((uptr)h % page_size_, 0); 722 return reinterpret_cast<void*>(reinterpret_cast<uptr>(h) + page_size_); 723 } 724 725 uptr RoundUpMapSize(uptr size) { 726 return RoundUpTo(size, page_size_) + page_size_; 727 } 728 729 uptr page_size_; 730 Header *list_; 731 SpinMutex mutex_; 732}; 733 734// This class implements a complete memory allocator by using two 735// internal allocators: 736// PrimaryAllocator is efficient, but may not allocate some sizes (alignments). 737// When allocating 2^x bytes it should return 2^x aligned chunk. 738// PrimaryAllocator is used via a local AllocatorCache. 739// SecondaryAllocator can allocate anything, but is not efficient. 740template <class PrimaryAllocator, class AllocatorCache, 741 class SecondaryAllocator> // NOLINT 742class CombinedAllocator { 743 public: 744 void Init() { 745 primary_.Init(); 746 secondary_.Init(); 747 } 748 749 void *Allocate(AllocatorCache *cache, uptr size, uptr alignment, 750 bool cleared = false) { 751 // Returning 0 on malloc(0) may break a lot of code. 752 if (size == 0) 753 size = 1; 754 if (size + alignment < size) 755 return 0; 756 if (alignment > 8) 757 size = RoundUpTo(size, alignment); 758 void *res; 759 if (primary_.CanAllocate(size, alignment)) 760 res = cache->Allocate(&primary_, primary_.ClassID(size)); 761 else 762 res = secondary_.Allocate(size, alignment); 763 if (alignment > 8) 764 CHECK_EQ(reinterpret_cast<uptr>(res) & (alignment - 1), 0); 765 if (cleared && res) 766 internal_memset(res, 0, size); 767 return res; 768 } 769 770 void Deallocate(AllocatorCache *cache, void *p) { 771 if (!p) return; 772 if (primary_.PointerIsMine(p)) 773 cache->Deallocate(&primary_, primary_.GetSizeClass(p), p); 774 else 775 secondary_.Deallocate(p); 776 } 777 778 void *Reallocate(AllocatorCache *cache, void *p, uptr new_size, 779 uptr alignment) { 780 if (!p) 781 return Allocate(cache, new_size, alignment); 782 if (!new_size) { 783 Deallocate(cache, p); 784 return 0; 785 } 786 CHECK(PointerIsMine(p)); 787 uptr old_size = GetActuallyAllocatedSize(p); 788 uptr memcpy_size = Min(new_size, old_size); 789 void *new_p = Allocate(cache, new_size, alignment); 790 if (new_p) 791 internal_memcpy(new_p, p, memcpy_size); 792 Deallocate(cache, p); 793 return new_p; 794 } 795 796 bool PointerIsMine(void *p) { 797 if (primary_.PointerIsMine(p)) 798 return true; 799 return secondary_.PointerIsMine(p); 800 } 801 802 void *GetMetaData(void *p) { 803 if (primary_.PointerIsMine(p)) 804 return primary_.GetMetaData(p); 805 return secondary_.GetMetaData(p); 806 } 807 808 void *GetBlockBegin(void *p) { 809 if (primary_.PointerIsMine(p)) 810 return primary_.GetBlockBegin(p); 811 return secondary_.GetBlockBegin(p); 812 } 813 814 uptr GetActuallyAllocatedSize(void *p) { 815 if (primary_.PointerIsMine(p)) 816 return primary_.GetActuallyAllocatedSize(p); 817 return secondary_.GetActuallyAllocatedSize(p); 818 } 819 820 uptr TotalMemoryUsed() { 821 return primary_.TotalMemoryUsed() + secondary_.TotalMemoryUsed(); 822 } 823 824 void TestOnlyUnmap() { primary_.TestOnlyUnmap(); } 825 826 void SwallowCache(AllocatorCache *cache) { 827 cache->Drain(&primary_); 828 } 829 830 private: 831 PrimaryAllocator primary_; 832 SecondaryAllocator secondary_; 833}; 834 835} // namespace __sanitizer 836 837#endif // SANITIZER_ALLOCATOR_H 838 839