diff options
author | Dimitry Andric <dim@FreeBSD.org> | 2017-01-02 19:18:27 +0000 |
---|---|---|
committer | Dimitry Andric <dim@FreeBSD.org> | 2017-01-02 19:18:27 +0000 |
commit | 316d58822dada9440bd06ecfc758dcc2364d617c (patch) | |
tree | fe72ec2e6ce9a360dda74d9d57f7acdb0e3c39d6 /lib/sanitizer_common/sanitizer_allocator.h | |
parent | 0230fcf22fe7d19f03d981c9c2c59a3db0b72ea5 (diff) | |
download | src-316d58822dada9440bd06ecfc758dcc2364d617c.tar.gz src-316d58822dada9440bd06ecfc758dcc2364d617c.zip |
Vendor import of compiler-rt trunk r290819:vendor/compiler-rt/compiler-rt-trunk-r290819
Notes
Notes:
svn path=/vendor/compiler-rt/dist/; revision=311120
svn path=/vendor/compiler-rt/compiler-rt-trunk-r290819/; revision=311121; tag=vendor/compiler-rt/compiler-rt-trunk-r290819
Diffstat (limited to 'lib/sanitizer_common/sanitizer_allocator.h')
-rw-r--r-- | lib/sanitizer_common/sanitizer_allocator.h | 1452 |
1 files changed, 15 insertions, 1437 deletions
diff --git a/lib/sanitizer_common/sanitizer_allocator.h b/lib/sanitizer_common/sanitizer_allocator.h index f0f002004709..9a37a2f2145f 100644 --- a/lib/sanitizer_common/sanitizer_allocator.h +++ b/lib/sanitizer_common/sanitizer_allocator.h @@ -20,271 +20,16 @@ #include "sanitizer_list.h" #include "sanitizer_mutex.h" #include "sanitizer_lfstack.h" +#include "sanitizer_procmaps.h" namespace __sanitizer { -// Prints error message and kills the program. -void NORETURN ReportAllocatorCannotReturnNull(); - -// SizeClassMap maps allocation sizes into size classes and back. -// Class 0 corresponds to size 0. -// Classes 1 - 16 correspond to sizes 16 to 256 (size = class_id * 16). -// Next 4 classes: 256 + i * 64 (i = 1 to 4). -// Next 4 classes: 512 + i * 128 (i = 1 to 4). -// ... -// Next 4 classes: 2^k + i * 2^(k-2) (i = 1 to 4). -// Last class corresponds to kMaxSize = 1 << kMaxSizeLog. -// -// This structure of the size class map gives us: -// - Efficient table-free class-to-size and size-to-class functions. -// - Difference between two consequent size classes is betweed 14% and 25% -// -// This class also gives a hint to a thread-caching allocator about the amount -// of chunks that need to be cached per-thread: -// - kMaxNumCached is the maximal number of chunks per size class. -// - (1 << kMaxBytesCachedLog) is the maximal number of bytes per size class. -// -// Part of output of SizeClassMap::Print(): -// c00 => s: 0 diff: +0 00% l 0 cached: 0 0; id 0 -// c01 => s: 16 diff: +16 00% l 4 cached: 256 4096; id 1 -// c02 => s: 32 diff: +16 100% l 5 cached: 256 8192; id 2 -// c03 => s: 48 diff: +16 50% l 5 cached: 256 12288; id 3 -// c04 => s: 64 diff: +16 33% l 6 cached: 256 16384; id 4 -// c05 => s: 80 diff: +16 25% l 6 cached: 256 20480; id 5 -// c06 => s: 96 diff: +16 20% l 6 cached: 256 24576; id 6 -// c07 => s: 112 diff: +16 16% l 6 cached: 256 28672; id 7 -// -// c08 => s: 128 diff: +16 14% l 7 cached: 256 32768; id 8 -// c09 => s: 144 diff: +16 12% l 7 cached: 256 36864; id 9 -// c10 => s: 160 diff: +16 11% l 7 cached: 256 40960; id 10 -// c11 => s: 176 diff: +16 10% l 7 cached: 256 45056; id 11 -// c12 => s: 192 diff: +16 09% l 7 cached: 256 49152; id 12 -// c13 => s: 208 diff: +16 08% l 7 cached: 256 53248; id 13 -// c14 => s: 224 diff: +16 07% l 7 cached: 256 57344; id 14 -// c15 => s: 240 diff: +16 07% l 7 cached: 256 61440; id 15 -// -// c16 => s: 256 diff: +16 06% l 8 cached: 256 65536; id 16 -// c17 => s: 320 diff: +64 25% l 8 cached: 204 65280; id 17 -// c18 => s: 384 diff: +64 20% l 8 cached: 170 65280; id 18 -// c19 => s: 448 diff: +64 16% l 8 cached: 146 65408; id 19 -// -// c20 => s: 512 diff: +64 14% l 9 cached: 128 65536; id 20 -// c21 => s: 640 diff: +128 25% l 9 cached: 102 65280; id 21 -// c22 => s: 768 diff: +128 20% l 9 cached: 85 65280; id 22 -// c23 => s: 896 diff: +128 16% l 9 cached: 73 65408; id 23 -// -// c24 => s: 1024 diff: +128 14% l 10 cached: 64 65536; id 24 -// c25 => s: 1280 diff: +256 25% l 10 cached: 51 65280; id 25 -// c26 => s: 1536 diff: +256 20% l 10 cached: 42 64512; id 26 -// c27 => s: 1792 diff: +256 16% l 10 cached: 36 64512; id 27 -// -// ... -// -// c48 => s: 65536 diff: +8192 14% l 16 cached: 1 65536; id 48 -// c49 => s: 81920 diff: +16384 25% l 16 cached: 1 81920; id 49 -// c50 => s: 98304 diff: +16384 20% l 16 cached: 1 98304; id 50 -// c51 => s: 114688 diff: +16384 16% l 16 cached: 1 114688; id 51 -// -// c52 => s: 131072 diff: +16384 14% l 17 cached: 1 131072; id 52 - -template <uptr kMaxSizeLog, uptr kMaxNumCachedT, uptr kMaxBytesCachedLog> -class SizeClassMap { - static const uptr kMinSizeLog = 4; - static const uptr kMidSizeLog = kMinSizeLog + 4; - static const uptr kMinSize = 1 << kMinSizeLog; - static const uptr kMidSize = 1 << kMidSizeLog; - static const uptr kMidClass = kMidSize / kMinSize; - static const uptr S = 2; - static const uptr M = (1 << S) - 1; - - public: - static const uptr kMaxNumCached = kMaxNumCachedT; - // We transfer chunks between central and thread-local free lists in batches. - // For small size classes we allocate batches separately. - // For large size classes we use one of the chunks to store the batch. - struct TransferBatch { - TransferBatch *next; - uptr count; - void *batch[kMaxNumCached]; - }; - - static const uptr kMaxSize = 1UL << kMaxSizeLog; - static const uptr kNumClasses = - kMidClass + ((kMaxSizeLog - kMidSizeLog) << S) + 1; - COMPILER_CHECK(kNumClasses >= 32 && kNumClasses <= 256); - static const uptr kNumClassesRounded = - kNumClasses == 32 ? 32 : - kNumClasses <= 64 ? 64 : - kNumClasses <= 128 ? 128 : 256; - - static uptr Size(uptr class_id) { - if (class_id <= kMidClass) - return kMinSize * class_id; - class_id -= kMidClass; - uptr t = kMidSize << (class_id >> S); - return t + (t >> S) * (class_id & M); - } - - static uptr ClassID(uptr size) { - if (size <= kMidSize) - return (size + kMinSize - 1) >> kMinSizeLog; - if (size > kMaxSize) return 0; - uptr l = MostSignificantSetBitIndex(size); - uptr hbits = (size >> (l - S)) & M; - uptr lbits = size & ((1 << (l - S)) - 1); - uptr l1 = l - kMidSizeLog; - return kMidClass + (l1 << S) + hbits + (lbits > 0); - } - - static uptr MaxCached(uptr class_id) { - if (class_id == 0) return 0; - uptr n = (1UL << kMaxBytesCachedLog) / Size(class_id); - return Max<uptr>(1, Min(kMaxNumCached, n)); - } - - static void Print() { - uptr prev_s = 0; - uptr total_cached = 0; - for (uptr i = 0; i < kNumClasses; i++) { - uptr s = Size(i); - if (s >= kMidSize / 2 && (s & (s - 1)) == 0) - Printf("\n"); - uptr d = s - prev_s; - uptr p = prev_s ? (d * 100 / prev_s) : 0; - uptr l = s ? MostSignificantSetBitIndex(s) : 0; - uptr cached = MaxCached(i) * s; - Printf("c%02zd => s: %zd diff: +%zd %02zd%% l %zd " - "cached: %zd %zd; id %zd\n", - i, Size(i), d, p, l, MaxCached(i), cached, ClassID(s)); - total_cached += cached; - prev_s = s; - } - Printf("Total cached: %zd\n", total_cached); - } - - static bool SizeClassRequiresSeparateTransferBatch(uptr class_id) { - return Size(class_id) < sizeof(TransferBatch) - - sizeof(uptr) * (kMaxNumCached - MaxCached(class_id)); - } - - static void Validate() { - for (uptr c = 1; c < kNumClasses; c++) { - // Printf("Validate: c%zd\n", c); - uptr s = Size(c); - CHECK_NE(s, 0U); - CHECK_EQ(ClassID(s), c); - if (c != kNumClasses - 1) - CHECK_EQ(ClassID(s + 1), c + 1); - CHECK_EQ(ClassID(s - 1), c); - if (c) - CHECK_GT(Size(c), Size(c-1)); - } - CHECK_EQ(ClassID(kMaxSize + 1), 0); - - for (uptr s = 1; s <= kMaxSize; s++) { - uptr c = ClassID(s); - // Printf("s%zd => c%zd\n", s, c); - CHECK_LT(c, kNumClasses); - CHECK_GE(Size(c), s); - if (c > 0) - CHECK_LT(Size(c-1), s); - } - } -}; +// Returns true if ReportAllocatorCannotReturnNull(true) was called. +// Can be use to avoid memory hungry operations. +bool IsReportingOOM(); -typedef SizeClassMap<17, 128, 16> DefaultSizeClassMap; -typedef SizeClassMap<17, 64, 14> CompactSizeClassMap; -template<class SizeClassAllocator> struct SizeClassAllocatorLocalCache; - -// Memory allocator statistics -enum AllocatorStat { - AllocatorStatAllocated, - AllocatorStatMapped, - AllocatorStatCount -}; - -typedef uptr AllocatorStatCounters[AllocatorStatCount]; - -// Per-thread stats, live in per-thread cache. -class AllocatorStats { - public: - void Init() { - internal_memset(this, 0, sizeof(*this)); - } - void InitLinkerInitialized() {} - - void Add(AllocatorStat i, uptr v) { - v += atomic_load(&stats_[i], memory_order_relaxed); - atomic_store(&stats_[i], v, memory_order_relaxed); - } - - void Sub(AllocatorStat i, uptr v) { - v = atomic_load(&stats_[i], memory_order_relaxed) - v; - atomic_store(&stats_[i], v, memory_order_relaxed); - } - - void Set(AllocatorStat i, uptr v) { - atomic_store(&stats_[i], v, memory_order_relaxed); - } - - uptr Get(AllocatorStat i) const { - return atomic_load(&stats_[i], memory_order_relaxed); - } - - private: - friend class AllocatorGlobalStats; - AllocatorStats *next_; - AllocatorStats *prev_; - atomic_uintptr_t stats_[AllocatorStatCount]; -}; - -// Global stats, used for aggregation and querying. -class AllocatorGlobalStats : public AllocatorStats { - public: - void InitLinkerInitialized() { - next_ = this; - prev_ = this; - } - void Init() { - internal_memset(this, 0, sizeof(*this)); - InitLinkerInitialized(); - } - - void Register(AllocatorStats *s) { - SpinMutexLock l(&mu_); - s->next_ = next_; - s->prev_ = this; - next_->prev_ = s; - next_ = s; - } - - void Unregister(AllocatorStats *s) { - SpinMutexLock l(&mu_); - s->prev_->next_ = s->next_; - s->next_->prev_ = s->prev_; - for (int i = 0; i < AllocatorStatCount; i++) - Add(AllocatorStat(i), s->Get(AllocatorStat(i))); - } - - void Get(AllocatorStatCounters s) const { - internal_memset(s, 0, AllocatorStatCount * sizeof(uptr)); - SpinMutexLock l(&mu_); - const AllocatorStats *stats = this; - for (;;) { - for (int i = 0; i < AllocatorStatCount; i++) - s[i] += stats->Get(AllocatorStat(i)); - stats = stats->next_; - if (stats == this) - break; - } - // All stats must be non-negative. - for (int i = 0; i < AllocatorStatCount; i++) - s[i] = ((sptr)s[i]) >= 0 ? s[i] : 0; - } - - private: - mutable SpinMutex mu_; -}; +// Prints error message and kills the program. +void NORETURN ReportAllocatorCannotReturnNull(bool out_of_memory); // Allocators call these callbacks on mmap/munmap. struct NoOpMapUnmapCallback { @@ -295,1185 +40,18 @@ struct NoOpMapUnmapCallback { // Callback type for iterating over chunks. typedef void (*ForEachChunkCallback)(uptr chunk, void *arg); -// SizeClassAllocator64 -- allocator for 64-bit address space. -// -// Space: a portion of address space of kSpaceSize bytes starting at SpaceBeg. -// If kSpaceBeg is ~0 then SpaceBeg is chosen dynamically my mmap. -// Otherwise SpaceBeg=kSpaceBeg (fixed address). -// kSpaceSize is a power of two. -// At the beginning the entire space is mprotect-ed, then small parts of it -// are mapped on demand. -// -// Region: a part of Space dedicated to a single size class. -// There are kNumClasses Regions of equal size. -// -// UserChunk: a piece of memory returned to user. -// MetaChunk: kMetadataSize bytes of metadata associated with a UserChunk. -// -// A Region looks like this: -// UserChunk1 ... UserChunkN <gap> MetaChunkN ... MetaChunk1 -template <const uptr kSpaceBeg, const uptr kSpaceSize, - const uptr kMetadataSize, class SizeClassMap, - class MapUnmapCallback = NoOpMapUnmapCallback> -class SizeClassAllocator64 { - public: - typedef typename SizeClassMap::TransferBatch Batch; - typedef SizeClassAllocator64<kSpaceBeg, kSpaceSize, kMetadataSize, - SizeClassMap, MapUnmapCallback> ThisT; - typedef SizeClassAllocatorLocalCache<ThisT> AllocatorCache; - - void Init() { - uptr TotalSpaceSize = kSpaceSize + AdditionalSize(); - if (kUsingConstantSpaceBeg) { - CHECK_EQ(kSpaceBeg, reinterpret_cast<uptr>( - MmapFixedNoAccess(kSpaceBeg, TotalSpaceSize))); - } else { - NonConstSpaceBeg = - reinterpret_cast<uptr>(MmapNoAccess(TotalSpaceSize)); - CHECK_NE(NonConstSpaceBeg, ~(uptr)0); - } - MapWithCallback(SpaceEnd(), AdditionalSize()); - } - - void MapWithCallback(uptr beg, uptr size) { - CHECK_EQ(beg, reinterpret_cast<uptr>(MmapFixedOrDie(beg, size))); - MapUnmapCallback().OnMap(beg, size); - } - - void UnmapWithCallback(uptr beg, uptr size) { - MapUnmapCallback().OnUnmap(beg, size); - UnmapOrDie(reinterpret_cast<void *>(beg), size); - } - - static bool CanAllocate(uptr size, uptr alignment) { - return size <= SizeClassMap::kMaxSize && - alignment <= SizeClassMap::kMaxSize; - } - - NOINLINE Batch* AllocateBatch(AllocatorStats *stat, AllocatorCache *c, - uptr class_id) { - CHECK_LT(class_id, kNumClasses); - RegionInfo *region = GetRegionInfo(class_id); - Batch *b = region->free_list.Pop(); - if (!b) - b = PopulateFreeList(stat, c, class_id, region); - region->n_allocated += b->count; - return b; - } - - NOINLINE void DeallocateBatch(AllocatorStats *stat, uptr class_id, Batch *b) { - RegionInfo *region = GetRegionInfo(class_id); - CHECK_GT(b->count, 0); - region->free_list.Push(b); - region->n_freed += b->count; - } - - bool PointerIsMine(const void *p) { - uptr P = reinterpret_cast<uptr>(p); - if (kUsingConstantSpaceBeg && (kSpaceBeg % kSpaceSize) == 0) - return P / kSpaceSize == kSpaceBeg / kSpaceSize; - return P >= SpaceBeg() && P < SpaceEnd(); - } - - uptr GetSizeClass(const void *p) { - if (kUsingConstantSpaceBeg && (kSpaceBeg % kSpaceSize) == 0) - return ((reinterpret_cast<uptr>(p)) / kRegionSize) % kNumClassesRounded; - return ((reinterpret_cast<uptr>(p) - SpaceBeg()) / kRegionSize) % - kNumClassesRounded; - } - - void *GetBlockBegin(const void *p) { - uptr class_id = GetSizeClass(p); - uptr size = SizeClassMap::Size(class_id); - if (!size) return nullptr; - uptr chunk_idx = GetChunkIdx((uptr)p, size); - uptr reg_beg = (uptr)p & ~(kRegionSize - 1); - uptr beg = chunk_idx * size; - uptr next_beg = beg + size; - if (class_id >= kNumClasses) return nullptr; - RegionInfo *region = GetRegionInfo(class_id); - if (region->mapped_user >= next_beg) - return reinterpret_cast<void*>(reg_beg + beg); - return nullptr; - } - - uptr GetActuallyAllocatedSize(void *p) { - CHECK(PointerIsMine(p)); - return SizeClassMap::Size(GetSizeClass(p)); - } - - uptr ClassID(uptr size) { return SizeClassMap::ClassID(size); } - - void *GetMetaData(const void *p) { - uptr class_id = GetSizeClass(p); - uptr size = SizeClassMap::Size(class_id); - uptr chunk_idx = GetChunkIdx(reinterpret_cast<uptr>(p), size); - return reinterpret_cast<void *>(SpaceBeg() + - (kRegionSize * (class_id + 1)) - - (1 + chunk_idx) * kMetadataSize); - } - - uptr TotalMemoryUsed() { - uptr res = 0; - for (uptr i = 0; i < kNumClasses; i++) - res += GetRegionInfo(i)->allocated_user; - return res; - } - - // Test-only. - void TestOnlyUnmap() { - UnmapWithCallback(SpaceBeg(), kSpaceSize + AdditionalSize()); - } - - void PrintStats() { - uptr total_mapped = 0; - uptr n_allocated = 0; - uptr n_freed = 0; - for (uptr class_id = 1; class_id < kNumClasses; class_id++) { - RegionInfo *region = GetRegionInfo(class_id); - total_mapped += region->mapped_user; - n_allocated += region->n_allocated; - n_freed += region->n_freed; - } - Printf("Stats: SizeClassAllocator64: %zdM mapped in %zd allocations; " - "remains %zd\n", - total_mapped >> 20, n_allocated, n_allocated - n_freed); - for (uptr class_id = 1; class_id < kNumClasses; class_id++) { - RegionInfo *region = GetRegionInfo(class_id); - if (region->mapped_user == 0) continue; - Printf(" %02zd (%zd): total: %zd K allocs: %zd remains: %zd\n", - class_id, - SizeClassMap::Size(class_id), - region->mapped_user >> 10, - region->n_allocated, - region->n_allocated - region->n_freed); - } - } - - // ForceLock() and ForceUnlock() are needed to implement Darwin malloc zone - // introspection API. - void ForceLock() { - for (uptr i = 0; i < kNumClasses; i++) { - GetRegionInfo(i)->mutex.Lock(); - } - } - - void ForceUnlock() { - for (int i = (int)kNumClasses - 1; i >= 0; i--) { - GetRegionInfo(i)->mutex.Unlock(); - } - } - - // Iterate over all existing chunks. - // The allocator must be locked when calling this function. - void ForEachChunk(ForEachChunkCallback callback, void *arg) { - for (uptr class_id = 1; class_id < kNumClasses; class_id++) { - RegionInfo *region = GetRegionInfo(class_id); - uptr chunk_size = SizeClassMap::Size(class_id); - uptr region_beg = SpaceBeg() + class_id * kRegionSize; - for (uptr chunk = region_beg; - chunk < region_beg + region->allocated_user; - chunk += chunk_size) { - // Too slow: CHECK_EQ((void *)chunk, GetBlockBegin((void *)chunk)); - callback(chunk, arg); - } - } - } - - static uptr AdditionalSize() { - return RoundUpTo(sizeof(RegionInfo) * kNumClassesRounded, - GetPageSizeCached()); - } - - typedef SizeClassMap SizeClassMapT; - static const uptr kNumClasses = SizeClassMap::kNumClasses; - static const uptr kNumClassesRounded = SizeClassMap::kNumClassesRounded; - - private: - static const uptr kRegionSize = kSpaceSize / kNumClassesRounded; - - static const bool kUsingConstantSpaceBeg = kSpaceBeg != ~(uptr)0; - uptr NonConstSpaceBeg; - uptr SpaceBeg() const { - return kUsingConstantSpaceBeg ? kSpaceBeg : NonConstSpaceBeg; - } - uptr SpaceEnd() const { return SpaceBeg() + kSpaceSize; } - // kRegionSize must be >= 2^32. - COMPILER_CHECK((kRegionSize) >= (1ULL << (SANITIZER_WORDSIZE / 2))); - // Populate the free list with at most this number of bytes at once - // or with one element if its size is greater. - static const uptr kPopulateSize = 1 << 14; - // Call mmap for user memory with at least this size. - static const uptr kUserMapSize = 1 << 16; - // Call mmap for metadata memory with at least this size. - static const uptr kMetaMapSize = 1 << 16; - - struct RegionInfo { - BlockingMutex mutex; - LFStack<Batch> free_list; - uptr allocated_user; // Bytes allocated for user memory. - uptr allocated_meta; // Bytes allocated for metadata. - uptr mapped_user; // Bytes mapped for user memory. - uptr mapped_meta; // Bytes mapped for metadata. - uptr n_allocated, n_freed; // Just stats. - }; - COMPILER_CHECK(sizeof(RegionInfo) >= kCacheLineSize); - - RegionInfo *GetRegionInfo(uptr class_id) { - CHECK_LT(class_id, kNumClasses); - RegionInfo *regions = - reinterpret_cast<RegionInfo *>(SpaceBeg() + kSpaceSize); - return ®ions[class_id]; - } - - static uptr GetChunkIdx(uptr chunk, uptr size) { - uptr offset = chunk % kRegionSize; - // Here we divide by a non-constant. This is costly. - // size always fits into 32-bits. If the offset fits too, use 32-bit div. - if (offset >> (SANITIZER_WORDSIZE / 2)) - return offset / size; - return (u32)offset / (u32)size; - } - - NOINLINE Batch* PopulateFreeList(AllocatorStats *stat, AllocatorCache *c, - uptr class_id, RegionInfo *region) { - BlockingMutexLock l(®ion->mutex); - Batch *b = region->free_list.Pop(); - if (b) - return b; - uptr size = SizeClassMap::Size(class_id); - uptr count = size < kPopulateSize ? SizeClassMap::MaxCached(class_id) : 1; - uptr beg_idx = region->allocated_user; - uptr end_idx = beg_idx + count * size; - uptr region_beg = SpaceBeg() + kRegionSize * class_id; - if (end_idx + size > region->mapped_user) { - // Do the mmap for the user memory. - uptr map_size = kUserMapSize; - while (end_idx + size > region->mapped_user + map_size) - map_size += kUserMapSize; - CHECK_GE(region->mapped_user + map_size, end_idx); - MapWithCallback(region_beg + region->mapped_user, map_size); - stat->Add(AllocatorStatMapped, map_size); - region->mapped_user += map_size; - } - uptr total_count = (region->mapped_user - beg_idx - size) - / size / count * count; - region->allocated_meta += total_count * kMetadataSize; - if (region->allocated_meta > region->mapped_meta) { - uptr map_size = kMetaMapSize; - while (region->allocated_meta > region->mapped_meta + map_size) - map_size += kMetaMapSize; - // Do the mmap for the metadata. - CHECK_GE(region->mapped_meta + map_size, region->allocated_meta); - MapWithCallback(region_beg + kRegionSize - - region->mapped_meta - map_size, map_size); - region->mapped_meta += map_size; - } - CHECK_LE(region->allocated_meta, region->mapped_meta); - if (region->mapped_user + region->mapped_meta > kRegionSize) { - Printf("%s: Out of memory. Dying. ", SanitizerToolName); - Printf("The process has exhausted %zuMB for size class %zu.\n", - kRegionSize / 1024 / 1024, size); - Die(); - } - for (;;) { - if (SizeClassMap::SizeClassRequiresSeparateTransferBatch(class_id)) - b = (Batch*)c->Allocate(this, SizeClassMap::ClassID(sizeof(Batch))); - else - b = (Batch*)(region_beg + beg_idx); - b->count = count; - for (uptr i = 0; i < count; i++) - b->batch[i] = (void*)(region_beg + beg_idx + i * size); - region->allocated_user += count * size; - CHECK_LE(region->allocated_user, region->mapped_user); - beg_idx += count * size; - if (beg_idx + count * size + size > region->mapped_user) - break; - CHECK_GT(b->count, 0); - region->free_list.Push(b); - } - return b; - } -}; - -// Maps integers in rage [0, kSize) to u8 values. -template<u64 kSize> -class FlatByteMap { - public: - void TestOnlyInit() { - internal_memset(map_, 0, sizeof(map_)); - } - - void set(uptr idx, u8 val) { - CHECK_LT(idx, kSize); - CHECK_EQ(0U, map_[idx]); - map_[idx] = val; - } - u8 operator[] (uptr idx) { - CHECK_LT(idx, kSize); - // FIXME: CHECK may be too expensive here. - return map_[idx]; - } - private: - u8 map_[kSize]; -}; - -// TwoLevelByteMap maps integers in range [0, kSize1*kSize2) to u8 values. -// It is implemented as a two-dimensional array: array of kSize1 pointers -// to kSize2-byte arrays. The secondary arrays are mmaped on demand. -// Each value is initially zero and can be set to something else only once. -// Setting and getting values from multiple threads is safe w/o extra locking. -template <u64 kSize1, u64 kSize2, class MapUnmapCallback = NoOpMapUnmapCallback> -class TwoLevelByteMap { - public: - void TestOnlyInit() { - internal_memset(map1_, 0, sizeof(map1_)); - mu_.Init(); - } - - void TestOnlyUnmap() { - for (uptr i = 0; i < kSize1; i++) { - u8 *p = Get(i); - if (!p) continue; - MapUnmapCallback().OnUnmap(reinterpret_cast<uptr>(p), kSize2); - UnmapOrDie(p, kSize2); - } - } - - uptr size() const { return kSize1 * kSize2; } - uptr size1() const { return kSize1; } - uptr size2() const { return kSize2; } - - void set(uptr idx, u8 val) { - CHECK_LT(idx, kSize1 * kSize2); - u8 *map2 = GetOrCreate(idx / kSize2); - CHECK_EQ(0U, map2[idx % kSize2]); - map2[idx % kSize2] = val; - } - - u8 operator[] (uptr idx) const { - CHECK_LT(idx, kSize1 * kSize2); - u8 *map2 = Get(idx / kSize2); - if (!map2) return 0; - return map2[idx % kSize2]; - } - - private: - u8 *Get(uptr idx) const { - CHECK_LT(idx, kSize1); - return reinterpret_cast<u8 *>( - atomic_load(&map1_[idx], memory_order_acquire)); - } - - u8 *GetOrCreate(uptr idx) { - u8 *res = Get(idx); - if (!res) { - SpinMutexLock l(&mu_); - if (!(res = Get(idx))) { - res = (u8*)MmapOrDie(kSize2, "TwoLevelByteMap"); - MapUnmapCallback().OnMap(reinterpret_cast<uptr>(res), kSize2); - atomic_store(&map1_[idx], reinterpret_cast<uptr>(res), - memory_order_release); - } - } - return res; - } - - atomic_uintptr_t map1_[kSize1]; - StaticSpinMutex mu_; -}; - -// SizeClassAllocator32 -- allocator for 32-bit address space. -// This allocator can theoretically be used on 64-bit arch, but there it is less -// efficient than SizeClassAllocator64. -// -// [kSpaceBeg, kSpaceBeg + kSpaceSize) is the range of addresses which can -// be returned by MmapOrDie(). -// -// Region: -// a result of a single call to MmapAlignedOrDie(kRegionSize, kRegionSize). -// Since the regions are aligned by kRegionSize, there are exactly -// kNumPossibleRegions possible regions in the address space and so we keep -// a ByteMap possible_regions to store the size classes of each Region. -// 0 size class means the region is not used by the allocator. -// -// One Region is used to allocate chunks of a single size class. -// A Region looks like this: -// UserChunk1 .. UserChunkN <gap> MetaChunkN .. MetaChunk1 -// -// In order to avoid false sharing the objects of this class should be -// chache-line aligned. -template <const uptr kSpaceBeg, const u64 kSpaceSize, - const uptr kMetadataSize, class SizeClassMap, - const uptr kRegionSizeLog, - class ByteMap, - class MapUnmapCallback = NoOpMapUnmapCallback> -class SizeClassAllocator32 { - public: - typedef typename SizeClassMap::TransferBatch Batch; - typedef SizeClassAllocator32<kSpaceBeg, kSpaceSize, kMetadataSize, - SizeClassMap, kRegionSizeLog, ByteMap, MapUnmapCallback> ThisT; - typedef SizeClassAllocatorLocalCache<ThisT> AllocatorCache; - - void Init() { - possible_regions.TestOnlyInit(); - internal_memset(size_class_info_array, 0, sizeof(size_class_info_array)); - } - - void *MapWithCallback(uptr size) { - size = RoundUpTo(size, GetPageSizeCached()); - void *res = MmapOrDie(size, "SizeClassAllocator32"); - MapUnmapCallback().OnMap((uptr)res, size); - return res; - } - - void UnmapWithCallback(uptr beg, uptr size) { - MapUnmapCallback().OnUnmap(beg, size); - UnmapOrDie(reinterpret_cast<void *>(beg), size); - } - - static bool CanAllocate(uptr size, uptr alignment) { - return size <= SizeClassMap::kMaxSize && - alignment <= SizeClassMap::kMaxSize; - } - - void *GetMetaData(const void *p) { - CHECK(PointerIsMine(p)); - uptr mem = reinterpret_cast<uptr>(p); - uptr beg = ComputeRegionBeg(mem); - uptr size = SizeClassMap::Size(GetSizeClass(p)); - u32 offset = mem - beg; - uptr n = offset / (u32)size; // 32-bit division - uptr meta = (beg + kRegionSize) - (n + 1) * kMetadataSize; - return reinterpret_cast<void*>(meta); - } - - NOINLINE Batch* AllocateBatch(AllocatorStats *stat, AllocatorCache *c, - uptr class_id) { - CHECK_LT(class_id, kNumClasses); - SizeClassInfo *sci = GetSizeClassInfo(class_id); - SpinMutexLock l(&sci->mutex); - if (sci->free_list.empty()) - PopulateFreeList(stat, c, sci, class_id); - CHECK(!sci->free_list.empty()); - Batch *b = sci->free_list.front(); - sci->free_list.pop_front(); - return b; - } - - NOINLINE void DeallocateBatch(AllocatorStats *stat, uptr class_id, Batch *b) { - CHECK_LT(class_id, kNumClasses); - SizeClassInfo *sci = GetSizeClassInfo(class_id); - SpinMutexLock l(&sci->mutex); - CHECK_GT(b->count, 0); - sci->free_list.push_front(b); - } - - bool PointerIsMine(const void *p) { - uptr mem = reinterpret_cast<uptr>(p); - if (mem < kSpaceBeg || mem >= kSpaceBeg + kSpaceSize) - return false; - return GetSizeClass(p) != 0; - } - - uptr GetSizeClass(const void *p) { - return possible_regions[ComputeRegionId(reinterpret_cast<uptr>(p))]; - } - - void *GetBlockBegin(const void *p) { - CHECK(PointerIsMine(p)); - uptr mem = reinterpret_cast<uptr>(p); - uptr beg = ComputeRegionBeg(mem); - uptr size = SizeClassMap::Size(GetSizeClass(p)); - u32 offset = mem - beg; - u32 n = offset / (u32)size; // 32-bit division - uptr res = beg + (n * (u32)size); - return reinterpret_cast<void*>(res); - } - - uptr GetActuallyAllocatedSize(void *p) { - CHECK(PointerIsMine(p)); - return SizeClassMap::Size(GetSizeClass(p)); - } - - uptr ClassID(uptr size) { return SizeClassMap::ClassID(size); } - - uptr TotalMemoryUsed() { - // No need to lock here. - uptr res = 0; - for (uptr i = 0; i < kNumPossibleRegions; i++) - if (possible_regions[i]) - res += kRegionSize; - return res; - } - - void TestOnlyUnmap() { - for (uptr i = 0; i < kNumPossibleRegions; i++) - if (possible_regions[i]) - UnmapWithCallback((i * kRegionSize), kRegionSize); - } - - // ForceLock() and ForceUnlock() are needed to implement Darwin malloc zone - // introspection API. - void ForceLock() { - for (uptr i = 0; i < kNumClasses; i++) { - GetSizeClassInfo(i)->mutex.Lock(); - } - } - - void ForceUnlock() { - for (int i = kNumClasses - 1; i >= 0; i--) { - GetSizeClassInfo(i)->mutex.Unlock(); - } - } - - // Iterate over all existing chunks. - // The allocator must be locked when calling this function. - void ForEachChunk(ForEachChunkCallback callback, void *arg) { - for (uptr region = 0; region < kNumPossibleRegions; region++) - if (possible_regions[region]) { - uptr chunk_size = SizeClassMap::Size(possible_regions[region]); - uptr max_chunks_in_region = kRegionSize / (chunk_size + kMetadataSize); - uptr region_beg = region * kRegionSize; - for (uptr chunk = region_beg; - chunk < region_beg + max_chunks_in_region * chunk_size; - chunk += chunk_size) { - // Too slow: CHECK_EQ((void *)chunk, GetBlockBegin((void *)chunk)); - callback(chunk, arg); - } - } - } - - void PrintStats() { - } - - static uptr AdditionalSize() { - return 0; - } - - typedef SizeClassMap SizeClassMapT; - static const uptr kNumClasses = SizeClassMap::kNumClasses; - - private: - static const uptr kRegionSize = 1 << kRegionSizeLog; - static const uptr kNumPossibleRegions = kSpaceSize / kRegionSize; - - struct SizeClassInfo { - SpinMutex mutex; - IntrusiveList<Batch> free_list; - char padding[kCacheLineSize - sizeof(uptr) - sizeof(IntrusiveList<Batch>)]; - }; - COMPILER_CHECK(sizeof(SizeClassInfo) == kCacheLineSize); - - uptr ComputeRegionId(uptr mem) { - uptr res = mem >> kRegionSizeLog; - CHECK_LT(res, kNumPossibleRegions); - return res; - } - - uptr ComputeRegionBeg(uptr mem) { - return mem & ~(kRegionSize - 1); - } - - uptr AllocateRegion(AllocatorStats *stat, uptr class_id) { - CHECK_LT(class_id, kNumClasses); - uptr res = reinterpret_cast<uptr>(MmapAlignedOrDie(kRegionSize, kRegionSize, - "SizeClassAllocator32")); - MapUnmapCallback().OnMap(res, kRegionSize); - stat->Add(AllocatorStatMapped, kRegionSize); - CHECK_EQ(0U, (res & (kRegionSize - 1))); - possible_regions.set(ComputeRegionId(res), static_cast<u8>(class_id)); - return res; - } - - SizeClassInfo *GetSizeClassInfo(uptr class_id) { - CHECK_LT(class_id, kNumClasses); - return &size_class_info_array[class_id]; - } - - void PopulateFreeList(AllocatorStats *stat, AllocatorCache *c, - SizeClassInfo *sci, uptr class_id) { - uptr size = SizeClassMap::Size(class_id); - uptr reg = AllocateRegion(stat, class_id); - uptr n_chunks = kRegionSize / (size + kMetadataSize); - uptr max_count = SizeClassMap::MaxCached(class_id); - Batch *b = nullptr; - for (uptr i = reg; i < reg + n_chunks * size; i += size) { - if (!b) { - if (SizeClassMap::SizeClassRequiresSeparateTransferBatch(class_id)) - b = (Batch*)c->Allocate(this, SizeClassMap::ClassID(sizeof(Batch))); - else - b = (Batch*)i; - b->count = 0; - } - b->batch[b->count++] = (void*)i; - if (b->count == max_count) { - CHECK_GT(b->count, 0); - sci->free_list.push_back(b); - b = nullptr; - } - } - if (b) { - CHECK_GT(b->count, 0); - sci->free_list.push_back(b); - } - } - - ByteMap possible_regions; - SizeClassInfo size_class_info_array[kNumClasses]; -}; - -// Objects of this type should be used as local caches for SizeClassAllocator64 -// or SizeClassAllocator32. Since the typical use of this class is to have one -// object per thread in TLS, is has to be POD. -template<class SizeClassAllocator> -struct SizeClassAllocatorLocalCache { - typedef SizeClassAllocator Allocator; - static const uptr kNumClasses = SizeClassAllocator::kNumClasses; - - void Init(AllocatorGlobalStats *s) { - stats_.Init(); - if (s) - s->Register(&stats_); - } - - void Destroy(SizeClassAllocator *allocator, AllocatorGlobalStats *s) { - Drain(allocator); - if (s) - s->Unregister(&stats_); - } - - void *Allocate(SizeClassAllocator *allocator, uptr class_id) { - CHECK_NE(class_id, 0UL); - CHECK_LT(class_id, kNumClasses); - stats_.Add(AllocatorStatAllocated, SizeClassMap::Size(class_id)); - PerClass *c = &per_class_[class_id]; - if (UNLIKELY(c->count == 0)) - Refill(allocator, class_id); - void *res = c->batch[--c->count]; - PREFETCH(c->batch[c->count - 1]); - return res; - } - - void Deallocate(SizeClassAllocator *allocator, uptr class_id, void *p) { - CHECK_NE(class_id, 0UL); - CHECK_LT(class_id, kNumClasses); - // If the first allocator call on a new thread is a deallocation, then - // max_count will be zero, leading to check failure. - InitCache(); - stats_.Sub(AllocatorStatAllocated, SizeClassMap::Size(class_id)); - PerClass *c = &per_class_[class_id]; - CHECK_NE(c->max_count, 0UL); - if (UNLIKELY(c->count == c->max_count)) - Drain(allocator, class_id); - c->batch[c->count++] = p; - } - - void Drain(SizeClassAllocator *allocator) { - for (uptr class_id = 0; class_id < kNumClasses; class_id++) { - PerClass *c = &per_class_[class_id]; - while (c->count > 0) - Drain(allocator, class_id); - } - } - - // private: - typedef typename SizeClassAllocator::SizeClassMapT SizeClassMap; - typedef typename SizeClassMap::TransferBatch Batch; - struct PerClass { - uptr count; - uptr max_count; - void *batch[2 * SizeClassMap::kMaxNumCached]; - }; - PerClass per_class_[kNumClasses]; - AllocatorStats stats_; - - void InitCache() { - if (per_class_[1].max_count) - return; - for (uptr i = 0; i < kNumClasses; i++) { - PerClass *c = &per_class_[i]; - c->max_count = 2 * SizeClassMap::MaxCached(i); - } - } - - NOINLINE void Refill(SizeClassAllocator *allocator, uptr class_id) { - InitCache(); - PerClass *c = &per_class_[class_id]; - Batch *b = allocator->AllocateBatch(&stats_, this, class_id); - CHECK_GT(b->count, 0); - for (uptr i = 0; i < b->count; i++) - c->batch[i] = b->batch[i]; - c->count = b->count; - if (SizeClassMap::SizeClassRequiresSeparateTransferBatch(class_id)) - Deallocate(allocator, SizeClassMap::ClassID(sizeof(Batch)), b); - } - - NOINLINE void Drain(SizeClassAllocator *allocator, uptr class_id) { - InitCache(); - PerClass *c = &per_class_[class_id]; - Batch *b; - if (SizeClassMap::SizeClassRequiresSeparateTransferBatch(class_id)) - b = (Batch*)Allocate(allocator, SizeClassMap::ClassID(sizeof(Batch))); - else - b = (Batch*)c->batch[0]; - uptr cnt = Min(c->max_count / 2, c->count); - for (uptr i = 0; i < cnt; i++) { - b->batch[i] = c->batch[i]; - c->batch[i] = c->batch[i + c->max_count / 2]; - } - b->count = cnt; - c->count -= cnt; - CHECK_GT(b->count, 0); - allocator->DeallocateBatch(&stats_, class_id, b); - } -}; - -// This class can (de)allocate only large chunks of memory using mmap/unmap. -// The main purpose of this allocator is to cover large and rare allocation -// sizes not covered by more efficient allocators (e.g. SizeClassAllocator64). -template <class MapUnmapCallback = NoOpMapUnmapCallback> -class LargeMmapAllocator { - public: - void InitLinkerInitialized(bool may_return_null) { - page_size_ = GetPageSizeCached(); - atomic_store(&may_return_null_, may_return_null, memory_order_relaxed); - } - - void Init(bool may_return_null) { - internal_memset(this, 0, sizeof(*this)); - InitLinkerInitialized(may_return_null); - } - - void *Allocate(AllocatorStats *stat, uptr size, uptr alignment) { - CHECK(IsPowerOfTwo(alignment)); - uptr map_size = RoundUpMapSize(size); - if (alignment > page_size_) - map_size += alignment; - // Overflow. - if (map_size < size) - return ReturnNullOrDie(); - uptr map_beg = reinterpret_cast<uptr>( - MmapOrDie(map_size, "LargeMmapAllocator")); - CHECK(IsAligned(map_beg, page_size_)); - MapUnmapCallback().OnMap(map_beg, map_size); - uptr map_end = map_beg + map_size; - uptr res = map_beg + page_size_; - if (res & (alignment - 1)) // Align. - res += alignment - (res & (alignment - 1)); - CHECK(IsAligned(res, alignment)); - CHECK(IsAligned(res, page_size_)); - CHECK_GE(res + size, map_beg); - CHECK_LE(res + size, map_end); - Header *h = GetHeader(res); - h->size = size; - h->map_beg = map_beg; - h->map_size = map_size; - uptr size_log = MostSignificantSetBitIndex(map_size); - CHECK_LT(size_log, ARRAY_SIZE(stats.by_size_log)); - { - SpinMutexLock l(&mutex_); - uptr idx = n_chunks_++; - chunks_sorted_ = false; - CHECK_LT(idx, kMaxNumChunks); - h->chunk_idx = idx; - chunks_[idx] = h; - stats.n_allocs++; - stats.currently_allocated += map_size; - stats.max_allocated = Max(stats.max_allocated, stats.currently_allocated); - stats.by_size_log[size_log]++; - stat->Add(AllocatorStatAllocated, map_size); - stat->Add(AllocatorStatMapped, map_size); - } - return reinterpret_cast<void*>(res); - } - - void *ReturnNullOrDie() { - if (atomic_load(&may_return_null_, memory_order_acquire)) - return nullptr; - ReportAllocatorCannotReturnNull(); - } - - void SetMayReturnNull(bool may_return_null) { - atomic_store(&may_return_null_, may_return_null, memory_order_release); - } - - void Deallocate(AllocatorStats *stat, void *p) { - Header *h = GetHeader(p); - { - SpinMutexLock l(&mutex_); - uptr idx = h->chunk_idx; - CHECK_EQ(chunks_[idx], h); - CHECK_LT(idx, n_chunks_); - chunks_[idx] = chunks_[n_chunks_ - 1]; - chunks_[idx]->chunk_idx = idx; - n_chunks_--; - chunks_sorted_ = false; - stats.n_frees++; - stats.currently_allocated -= h->map_size; - stat->Sub(AllocatorStatAllocated, h->map_size); - stat->Sub(AllocatorStatMapped, h->map_size); - } - MapUnmapCallback().OnUnmap(h->map_beg, h->map_size); - UnmapOrDie(reinterpret_cast<void*>(h->map_beg), h->map_size); - } - - uptr TotalMemoryUsed() { - SpinMutexLock l(&mutex_); - uptr res = 0; - for (uptr i = 0; i < n_chunks_; i++) { - Header *h = chunks_[i]; - CHECK_EQ(h->chunk_idx, i); - res += RoundUpMapSize(h->size); - } - return res; - } - - bool PointerIsMine(const void *p) { - return GetBlockBegin(p) != nullptr; - } - - uptr GetActuallyAllocatedSize(void *p) { - return RoundUpTo(GetHeader(p)->size, page_size_); - } - - // At least page_size_/2 metadata bytes is available. - void *GetMetaData(const void *p) { - // Too slow: CHECK_EQ(p, GetBlockBegin(p)); - if (!IsAligned(reinterpret_cast<uptr>(p), page_size_)) { - Printf("%s: bad pointer %p\n", SanitizerToolName, p); - CHECK(IsAligned(reinterpret_cast<uptr>(p), page_size_)); - } - return GetHeader(p) + 1; - } - - void *GetBlockBegin(const void *ptr) { - uptr p = reinterpret_cast<uptr>(ptr); - SpinMutexLock l(&mutex_); - uptr nearest_chunk = 0; - // Cache-friendly linear search. - for (uptr i = 0; i < n_chunks_; i++) { - uptr ch = reinterpret_cast<uptr>(chunks_[i]); - if (p < ch) continue; // p is at left to this chunk, skip it. - if (p - ch < p - nearest_chunk) - nearest_chunk = ch; - } - if (!nearest_chunk) - return nullptr; - Header *h = reinterpret_cast<Header *>(nearest_chunk); - CHECK_GE(nearest_chunk, h->map_beg); - CHECK_LT(nearest_chunk, h->map_beg + h->map_size); - CHECK_LE(nearest_chunk, p); - if (h->map_beg + h->map_size <= p) - return nullptr; - return GetUser(h); - } - - // This function does the same as GetBlockBegin, but is much faster. - // Must be called with the allocator locked. - void *GetBlockBeginFastLocked(void *ptr) { - mutex_.CheckLocked(); - uptr p = reinterpret_cast<uptr>(ptr); - uptr n = n_chunks_; - if (!n) return nullptr; - if (!chunks_sorted_) { - // Do one-time sort. chunks_sorted_ is reset in Allocate/Deallocate. - SortArray(reinterpret_cast<uptr*>(chunks_), n); - for (uptr i = 0; i < n; i++) - chunks_[i]->chunk_idx = i; - chunks_sorted_ = true; - min_mmap_ = reinterpret_cast<uptr>(chunks_[0]); - max_mmap_ = reinterpret_cast<uptr>(chunks_[n - 1]) + - chunks_[n - 1]->map_size; - } - if (p < min_mmap_ || p >= max_mmap_) - return nullptr; - uptr beg = 0, end = n - 1; - // This loop is a log(n) lower_bound. It does not check for the exact match - // to avoid expensive cache-thrashing loads. - while (end - beg >= 2) { - uptr mid = (beg + end) / 2; // Invariant: mid >= beg + 1 - if (p < reinterpret_cast<uptr>(chunks_[mid])) - end = mid - 1; // We are not interested in chunks_[mid]. - else - beg = mid; // chunks_[mid] may still be what we want. - } - - if (beg < end) { - CHECK_EQ(beg + 1, end); - // There are 2 chunks left, choose one. - if (p >= reinterpret_cast<uptr>(chunks_[end])) - beg = end; - } - - Header *h = chunks_[beg]; - if (h->map_beg + h->map_size <= p || p < h->map_beg) - return nullptr; - return GetUser(h); - } - - void PrintStats() { - Printf("Stats: LargeMmapAllocator: allocated %zd times, " - "remains %zd (%zd K) max %zd M; by size logs: ", - stats.n_allocs, stats.n_allocs - stats.n_frees, - stats.currently_allocated >> 10, stats.max_allocated >> 20); - for (uptr i = 0; i < ARRAY_SIZE(stats.by_size_log); i++) { - uptr c = stats.by_size_log[i]; - if (!c) continue; - Printf("%zd:%zd; ", i, c); - } - Printf("\n"); - } - - // ForceLock() and ForceUnlock() are needed to implement Darwin malloc zone - // introspection API. - void ForceLock() { - mutex_.Lock(); - } - - void ForceUnlock() { - mutex_.Unlock(); - } - - // Iterate over all existing chunks. - // The allocator must be locked when calling this function. - void ForEachChunk(ForEachChunkCallback callback, void *arg) { - for (uptr i = 0; i < n_chunks_; i++) - callback(reinterpret_cast<uptr>(GetUser(chunks_[i])), arg); - } - - private: - static const int kMaxNumChunks = 1 << FIRST_32_SECOND_64(15, 18); - struct Header { - uptr map_beg; - uptr map_size; - uptr size; - uptr chunk_idx; - }; - - Header *GetHeader(uptr p) { - CHECK(IsAligned(p, page_size_)); - return reinterpret_cast<Header*>(p - page_size_); - } - Header *GetHeader(const void *p) { - return GetHeader(reinterpret_cast<uptr>(p)); - } - - void *GetUser(Header *h) { - CHECK(IsAligned((uptr)h, page_size_)); - return reinterpret_cast<void*>(reinterpret_cast<uptr>(h) + page_size_); - } - - uptr RoundUpMapSize(uptr size) { - return RoundUpTo(size, page_size_) + page_size_; - } - - uptr page_size_; - Header *chunks_[kMaxNumChunks]; - uptr n_chunks_; - uptr min_mmap_, max_mmap_; - bool chunks_sorted_; - struct Stats { - uptr n_allocs, n_frees, currently_allocated, max_allocated, by_size_log[64]; - } stats; - atomic_uint8_t may_return_null_; - SpinMutex mutex_; -}; - -// This class implements a complete memory allocator by using two -// internal allocators: -// PrimaryAllocator is efficient, but may not allocate some sizes (alignments). -// When allocating 2^x bytes it should return 2^x aligned chunk. -// PrimaryAllocator is used via a local AllocatorCache. -// SecondaryAllocator can allocate anything, but is not efficient. -template <class PrimaryAllocator, class AllocatorCache, - class SecondaryAllocator> // NOLINT -class CombinedAllocator { - public: - void InitCommon(bool may_return_null) { - primary_.Init(); - atomic_store(&may_return_null_, may_return_null, memory_order_relaxed); - } - - void InitLinkerInitialized(bool may_return_null) { - secondary_.InitLinkerInitialized(may_return_null); - stats_.InitLinkerInitialized(); - InitCommon(may_return_null); - } - - void Init(bool may_return_null) { - secondary_.Init(may_return_null); - stats_.Init(); - InitCommon(may_return_null); - } - - void *Allocate(AllocatorCache *cache, uptr size, uptr alignment, - bool cleared = false, bool check_rss_limit = false) { - // Returning 0 on malloc(0) may break a lot of code. - if (size == 0) - size = 1; - if (size + alignment < size) - return ReturnNullOrDie(); - if (check_rss_limit && RssLimitIsExceeded()) - return ReturnNullOrDie(); - if (alignment > 8) - size = RoundUpTo(size, alignment); - void *res; - bool from_primary = primary_.CanAllocate(size, alignment); - if (from_primary) - res = cache->Allocate(&primary_, primary_.ClassID(size)); - else - res = secondary_.Allocate(&stats_, size, alignment); - if (alignment > 8) - CHECK_EQ(reinterpret_cast<uptr>(res) & (alignment - 1), 0); - if (cleared && res && from_primary) - internal_bzero_aligned16(res, RoundUpTo(size, 16)); - return res; - } - - bool MayReturnNull() const { - return atomic_load(&may_return_null_, memory_order_acquire); - } - - void *ReturnNullOrDie() { - if (MayReturnNull()) - return nullptr; - ReportAllocatorCannotReturnNull(); - } - - void SetMayReturnNull(bool may_return_null) { - secondary_.SetMayReturnNull(may_return_null); - atomic_store(&may_return_null_, may_return_null, memory_order_release); - } - - bool RssLimitIsExceeded() { - return atomic_load(&rss_limit_is_exceeded_, memory_order_acquire); - } - - void SetRssLimitIsExceeded(bool rss_limit_is_exceeded) { - atomic_store(&rss_limit_is_exceeded_, rss_limit_is_exceeded, - memory_order_release); - } - - void Deallocate(AllocatorCache *cache, void *p) { - if (!p) return; - if (primary_.PointerIsMine(p)) - cache->Deallocate(&primary_, primary_.GetSizeClass(p), p); - else - secondary_.Deallocate(&stats_, p); - } - - void *Reallocate(AllocatorCache *cache, void *p, uptr new_size, - uptr alignment) { - if (!p) - return Allocate(cache, new_size, alignment); - if (!new_size) { - Deallocate(cache, p); - return nullptr; - } - CHECK(PointerIsMine(p)); - uptr old_size = GetActuallyAllocatedSize(p); - uptr memcpy_size = Min(new_size, old_size); - void *new_p = Allocate(cache, new_size, alignment); - if (new_p) - internal_memcpy(new_p, p, memcpy_size); - Deallocate(cache, p); - return new_p; - } - - bool PointerIsMine(void *p) { - if (primary_.PointerIsMine(p)) - return true; - return secondary_.PointerIsMine(p); - } - - bool FromPrimary(void *p) { - return primary_.PointerIsMine(p); - } - - void *GetMetaData(const void *p) { - if (primary_.PointerIsMine(p)) - return primary_.GetMetaData(p); - return secondary_.GetMetaData(p); - } - - void *GetBlockBegin(const void *p) { - if (primary_.PointerIsMine(p)) - return primary_.GetBlockBegin(p); - return secondary_.GetBlockBegin(p); - } - - // This function does the same as GetBlockBegin, but is much faster. - // Must be called with the allocator locked. - void *GetBlockBeginFastLocked(void *p) { - if (primary_.PointerIsMine(p)) - return primary_.GetBlockBegin(p); - return secondary_.GetBlockBeginFastLocked(p); - } - - uptr GetActuallyAllocatedSize(void *p) { - if (primary_.PointerIsMine(p)) - return primary_.GetActuallyAllocatedSize(p); - return secondary_.GetActuallyAllocatedSize(p); - } - - uptr TotalMemoryUsed() { - return primary_.TotalMemoryUsed() + secondary_.TotalMemoryUsed(); - } - - void TestOnlyUnmap() { primary_.TestOnlyUnmap(); } - - void InitCache(AllocatorCache *cache) { - cache->Init(&stats_); - } - - void DestroyCache(AllocatorCache *cache) { - cache->Destroy(&primary_, &stats_); - } - - void SwallowCache(AllocatorCache *cache) { - cache->Drain(&primary_); - } - - void GetStats(AllocatorStatCounters s) const { - stats_.Get(s); - } - - void PrintStats() { - primary_.PrintStats(); - secondary_.PrintStats(); - } - - // ForceLock() and ForceUnlock() are needed to implement Darwin malloc zone - // introspection API. - void ForceLock() { - primary_.ForceLock(); - secondary_.ForceLock(); - } - - void ForceUnlock() { - secondary_.ForceUnlock(); - primary_.ForceUnlock(); - } - - // Iterate over all existing chunks. - // The allocator must be locked when calling this function. - void ForEachChunk(ForEachChunkCallback callback, void *arg) { - primary_.ForEachChunk(callback, arg); - secondary_.ForEachChunk(callback, arg); - } - - private: - PrimaryAllocator primary_; - SecondaryAllocator secondary_; - AllocatorGlobalStats stats_; - atomic_uint8_t may_return_null_; - atomic_uint8_t rss_limit_is_exceeded_; -}; - // Returns true if calloc(size, n) should return 0 due to overflow in size*n. bool CallocShouldReturnNullDueToOverflow(uptr size, uptr n); +#include "sanitizer_allocator_size_class_map.h" +#include "sanitizer_allocator_stats.h" +#include "sanitizer_allocator_primary64.h" +#include "sanitizer_allocator_bytemap.h" +#include "sanitizer_allocator_primary32.h" +#include "sanitizer_allocator_local_cache.h" +#include "sanitizer_allocator_secondary.h" +#include "sanitizer_allocator_combined.h" + } // namespace __sanitizer #endif // SANITIZER_ALLOCATOR_H |