diff options
Diffstat (limited to 'contrib/llvm-project/compiler-rt/lib/scudo')
39 files changed, 3710 insertions, 1066 deletions
diff --git a/contrib/llvm-project/compiler-rt/lib/scudo/standalone/allocator_config.h b/contrib/llvm-project/compiler-rt/lib/scudo/standalone/allocator_config.h index 63eb325c9b87..315a04f7635d 100644 --- a/contrib/llvm-project/compiler-rt/lib/scudo/standalone/allocator_config.h +++ b/contrib/llvm-project/compiler-rt/lib/scudo/standalone/allocator_config.h @@ -19,6 +19,22 @@ #include "tsd_exclusive.h" #include "tsd_shared.h" +// To import a custom configuration, define `SCUDO_USE_CUSTOM_CONFIG` and +// aliasing the `Config` like: +// +// namespace scudo { +// // The instance of Scudo will be initiated with `Config`. +// typedef CustomConfig Config; +// // Aliasing as default configuration to run the tests with this config. +// typedef CustomConfig DefaultConfig; +// } // namespace scudo +// +// Put them in the header `custom_scudo_config.h` then you will be using the +// custom configuration and able to run all the tests as well. +#ifdef SCUDO_USE_CUSTOM_CONFIG +#include "custom_scudo_config.h" +#endif + namespace scudo { // The combined allocator uses a structure as a template argument that @@ -26,185 +42,262 @@ namespace scudo { // allocator. // // struct ExampleConfig { -// // SizeClasMmap to use with the Primary. -// using SizeClassMap = DefaultSizeClassMap; // // Indicates possible support for Memory Tagging. // static const bool MaySupportMemoryTagging = false; -// // Defines the Primary allocator to use. -// typedef SizeClassAllocator64<ExampleConfig> Primary; -// // Log2 of the size of a size class region, as used by the Primary. -// static const uptr PrimaryRegionSizeLog = 30U; -// // Log2 of the size of block group, as used by the Primary. Each group -// // contains a range of memory addresses, blocks in the range will belong to -// // the same group. In general, single region may have 1 or 2MB group size. -// // Multiple regions will have the group size equal to the region size -// // because the region size is usually smaller than 1 MB. -// // Smaller value gives fine-grained control of memory usage but the trade -// // off is that it may take longer time of deallocation. -// static const uptr PrimaryGroupSizeLog = 20U; -// // Defines the type and scale of a compact pointer. A compact pointer can -// // be understood as the offset of a pointer within the region it belongs -// // to, in increments of a power-of-2 scale. -// // eg: Ptr = Base + (CompactPtr << Scale). -// typedef u32 PrimaryCompactPtrT; -// static const uptr PrimaryCompactPtrScale = SCUDO_MIN_ALIGNMENT_LOG; -// // Indicates support for offsetting the start of a region by -// // a random number of pages. Only used with primary64. -// static const bool PrimaryEnableRandomOffset = true; -// // Call map for user memory with at least this size. Only used with -// // primary64. -// static const uptr PrimaryMapSizeIncrement = 1UL << 18; -// // Defines the minimal & maximal release interval that can be set. -// static const s32 PrimaryMinReleaseToOsIntervalMs = INT32_MIN; -// static const s32 PrimaryMaxReleaseToOsIntervalMs = INT32_MAX; -// // Defines the type of cache used by the Secondary. Some additional -// // configuration entries can be necessary depending on the Cache. -// typedef MapAllocatorNoCache SecondaryCache; +// // // Thread-Specific Data Registry used, shared or exclusive. // template <class A> using TSDRegistryT = TSDRegistrySharedT<A, 8U, 4U>; +// +// struct Primary { +// // SizeClassMap to use with the Primary. +// using SizeClassMap = DefaultSizeClassMap; +// +// // Log2 of the size of a size class region, as used by the Primary. +// static const uptr RegionSizeLog = 30U; +// +// // Log2 of the size of block group, as used by the Primary. Each group +// // contains a range of memory addresses, blocks in the range will belong +// // to the same group. In general, single region may have 1 or 2MB group +// // size. Multiple regions will have the group size equal to the region +// // size because the region size is usually smaller than 1 MB. +// // Smaller value gives fine-grained control of memory usage but the +// // trade-off is that it may take longer time of deallocation. +// static const uptr GroupSizeLog = 20U; +// +// // Defines the type and scale of a compact pointer. A compact pointer can +// // be understood as the offset of a pointer within the region it belongs +// // to, in increments of a power-of-2 scale. +// // eg: Ptr = Base + (CompactPtr << Scale). +// typedef u32 CompactPtrT; +// static const uptr CompactPtrScale = SCUDO_MIN_ALIGNMENT_LOG; +// +// // Indicates support for offsetting the start of a region by +// // a random number of pages. Only used with primary64. +// static const bool EnableRandomOffset = true; +// +// // Call map for user memory with at least this size. Only used with +// // primary64. +// static const uptr MapSizeIncrement = 1UL << 18; +// +// // Defines the minimal & maximal release interval that can be set. +// static const s32 MinReleaseToOsIntervalMs = INT32_MIN; +// static const s32 MaxReleaseToOsIntervalMs = INT32_MAX; +// }; +// // Defines the type of Primary allocator to use. +// template <typename Config> using PrimaryT = SizeClassAllocator64<Config>; +// +// // Defines the type of cache used by the Secondary. Some additional +// // configuration entries can be necessary depending on the Cache. +// struct Secondary { +// struct Cache { +// static const u32 EntriesArraySize = 32U; +// static const u32 QuarantineSize = 0U; +// static const u32 DefaultMaxEntriesCount = 32U; +// static const uptr DefaultMaxEntrySize = 1UL << 19; +// static const s32 MinReleaseToOsIntervalMs = INT32_MIN; +// static const s32 MaxReleaseToOsIntervalMs = INT32_MAX; +// }; +// // Defines the type of Secondary Cache to use. +// template <typename Config> using CacheT = MapAllocatorCache<Config>; +// }; +// // Defines the type of Secondary allocator to use. +// template <typename Config> using SecondaryT = MapAllocator<Config>; // }; -// Default configurations for various platforms. +#ifndef SCUDO_USE_CUSTOM_CONFIG +// Default configurations for various platforms. Note this is only enabled when +// there's no custom configuration in the build system. struct DefaultConfig { - using SizeClassMap = DefaultSizeClassMap; static const bool MaySupportMemoryTagging = true; + template <class A> using TSDRegistryT = TSDRegistryExT<A>; // Exclusive + struct Primary { + using SizeClassMap = DefaultSizeClassMap; #if SCUDO_CAN_USE_PRIMARY64 - typedef SizeClassAllocator64<DefaultConfig> Primary; - static const uptr PrimaryRegionSizeLog = 32U; - static const uptr PrimaryGroupSizeLog = 21U; - typedef uptr PrimaryCompactPtrT; - static const uptr PrimaryCompactPtrScale = 0; - static const bool PrimaryEnableRandomOffset = true; - static const uptr PrimaryMapSizeIncrement = 1UL << 18; + static const uptr RegionSizeLog = 32U; + static const uptr GroupSizeLog = 21U; + typedef uptr CompactPtrT; + static const uptr CompactPtrScale = 0; + static const bool EnableRandomOffset = true; + static const uptr MapSizeIncrement = 1UL << 18; #else - typedef SizeClassAllocator32<DefaultConfig> Primary; - static const uptr PrimaryRegionSizeLog = 19U; - static const uptr PrimaryGroupSizeLog = 19U; - typedef uptr PrimaryCompactPtrT; + static const uptr RegionSizeLog = 19U; + static const uptr GroupSizeLog = 19U; + typedef uptr CompactPtrT; +#endif + static const s32 MinReleaseToOsIntervalMs = INT32_MIN; + static const s32 MaxReleaseToOsIntervalMs = INT32_MAX; + }; +#if SCUDO_CAN_USE_PRIMARY64 + template <typename Config> using PrimaryT = SizeClassAllocator64<Config>; +#else + template <typename Config> using PrimaryT = SizeClassAllocator32<Config>; #endif - static const s32 PrimaryMinReleaseToOsIntervalMs = INT32_MIN; - static const s32 PrimaryMaxReleaseToOsIntervalMs = INT32_MAX; - typedef MapAllocatorCache<DefaultConfig> SecondaryCache; - static const u32 SecondaryCacheEntriesArraySize = 32U; - static const u32 SecondaryCacheQuarantineSize = 0U; - static const u32 SecondaryCacheDefaultMaxEntriesCount = 32U; - static const uptr SecondaryCacheDefaultMaxEntrySize = 1UL << 19; - static const s32 SecondaryCacheMinReleaseToOsIntervalMs = INT32_MIN; - static const s32 SecondaryCacheMaxReleaseToOsIntervalMs = INT32_MAX; + struct Secondary { + struct Cache { + static const u32 EntriesArraySize = 32U; + static const u32 QuarantineSize = 0U; + static const u32 DefaultMaxEntriesCount = 32U; + static const uptr DefaultMaxEntrySize = 1UL << 19; + static const s32 MinReleaseToOsIntervalMs = INT32_MIN; + static const s32 MaxReleaseToOsIntervalMs = INT32_MAX; + }; + template <typename Config> using CacheT = MapAllocatorCache<Config>; + }; - template <class A> using TSDRegistryT = TSDRegistryExT<A>; // Exclusive + template <typename Config> using SecondaryT = MapAllocator<Config>; }; + +#endif // SCUDO_USE_CUSTOM_CONFIG + struct AndroidConfig { - using SizeClassMap = AndroidSizeClassMap; static const bool MaySupportMemoryTagging = true; + template <class A> + using TSDRegistryT = TSDRegistrySharedT<A, 8U, 2U>; // Shared, max 8 TSDs. + struct Primary { + using SizeClassMap = AndroidSizeClassMap; #if SCUDO_CAN_USE_PRIMARY64 - typedef SizeClassAllocator64<AndroidConfig> Primary; - static const uptr PrimaryRegionSizeLog = 28U; - typedef u32 PrimaryCompactPtrT; - static const uptr PrimaryCompactPtrScale = SCUDO_MIN_ALIGNMENT_LOG; - static const uptr PrimaryGroupSizeLog = 20U; - static const bool PrimaryEnableRandomOffset = true; - static const uptr PrimaryMapSizeIncrement = 1UL << 18; + static const uptr RegionSizeLog = 28U; + typedef u32 CompactPtrT; + static const uptr CompactPtrScale = SCUDO_MIN_ALIGNMENT_LOG; + static const uptr GroupSizeLog = 20U; + static const bool EnableRandomOffset = true; + static const uptr MapSizeIncrement = 1UL << 18; #else - typedef SizeClassAllocator32<AndroidConfig> Primary; - static const uptr PrimaryRegionSizeLog = 18U; - static const uptr PrimaryGroupSizeLog = 18U; - typedef uptr PrimaryCompactPtrT; + static const uptr RegionSizeLog = 18U; + static const uptr GroupSizeLog = 18U; + typedef uptr CompactPtrT; +#endif + static const s32 MinReleaseToOsIntervalMs = 1000; + static const s32 MaxReleaseToOsIntervalMs = 1000; + }; +#if SCUDO_CAN_USE_PRIMARY64 + template <typename Config> using PrimaryT = SizeClassAllocator64<Config>; +#else + template <typename Config> using PrimaryT = SizeClassAllocator32<Config>; #endif - static const s32 PrimaryMinReleaseToOsIntervalMs = 1000; - static const s32 PrimaryMaxReleaseToOsIntervalMs = 1000; - typedef MapAllocatorCache<AndroidConfig> SecondaryCache; - static const u32 SecondaryCacheEntriesArraySize = 256U; - static const u32 SecondaryCacheQuarantineSize = 32U; - static const u32 SecondaryCacheDefaultMaxEntriesCount = 32U; - static const uptr SecondaryCacheDefaultMaxEntrySize = 2UL << 20; - static const s32 SecondaryCacheMinReleaseToOsIntervalMs = 0; - static const s32 SecondaryCacheMaxReleaseToOsIntervalMs = 1000; + struct Secondary { + struct Cache { + static const u32 EntriesArraySize = 256U; + static const u32 QuarantineSize = 32U; + static const u32 DefaultMaxEntriesCount = 32U; + static const uptr DefaultMaxEntrySize = 2UL << 20; + static const s32 MinReleaseToOsIntervalMs = 0; + static const s32 MaxReleaseToOsIntervalMs = 1000; + }; + template <typename Config> using CacheT = MapAllocatorCache<Config>; + }; - template <class A> - using TSDRegistryT = TSDRegistrySharedT<A, 8U, 2U>; // Shared, max 8 TSDs. + template <typename Config> using SecondaryT = MapAllocator<Config>; }; struct AndroidSvelteConfig { - using SizeClassMap = SvelteSizeClassMap; static const bool MaySupportMemoryTagging = false; + template <class A> + using TSDRegistryT = TSDRegistrySharedT<A, 2U, 1U>; // Shared, max 2 TSDs. + struct Primary { + using SizeClassMap = SvelteSizeClassMap; #if SCUDO_CAN_USE_PRIMARY64 - typedef SizeClassAllocator64<AndroidSvelteConfig> Primary; - static const uptr PrimaryRegionSizeLog = 27U; - typedef u32 PrimaryCompactPtrT; - static const uptr PrimaryCompactPtrScale = SCUDO_MIN_ALIGNMENT_LOG; - static const uptr PrimaryGroupSizeLog = 18U; - static const bool PrimaryEnableRandomOffset = true; - static const uptr PrimaryMapSizeIncrement = 1UL << 18; + static const uptr RegionSizeLog = 27U; + typedef u32 CompactPtrT; + static const uptr CompactPtrScale = SCUDO_MIN_ALIGNMENT_LOG; + static const uptr GroupSizeLog = 18U; + static const bool EnableRandomOffset = true; + static const uptr MapSizeIncrement = 1UL << 18; #else - typedef SizeClassAllocator32<AndroidSvelteConfig> Primary; - static const uptr PrimaryRegionSizeLog = 16U; - static const uptr PrimaryGroupSizeLog = 16U; - typedef uptr PrimaryCompactPtrT; + static const uptr RegionSizeLog = 16U; + static const uptr GroupSizeLog = 16U; + typedef uptr CompactPtrT; #endif - static const s32 PrimaryMinReleaseToOsIntervalMs = 1000; - static const s32 PrimaryMaxReleaseToOsIntervalMs = 1000; + static const s32 MinReleaseToOsIntervalMs = 1000; + static const s32 MaxReleaseToOsIntervalMs = 1000; + }; - typedef MapAllocatorCache<AndroidSvelteConfig> SecondaryCache; - static const u32 SecondaryCacheEntriesArraySize = 16U; - static const u32 SecondaryCacheQuarantineSize = 32U; - static const u32 SecondaryCacheDefaultMaxEntriesCount = 4U; - static const uptr SecondaryCacheDefaultMaxEntrySize = 1UL << 18; - static const s32 SecondaryCacheMinReleaseToOsIntervalMs = 0; - static const s32 SecondaryCacheMaxReleaseToOsIntervalMs = 0; +#if SCUDO_CAN_USE_PRIMARY64 + template <typename Config> using PrimaryT = SizeClassAllocator64<Config>; +#else + template <typename Config> using PrimaryT = SizeClassAllocator32<Config>; +#endif - template <class A> - using TSDRegistryT = TSDRegistrySharedT<A, 2U, 1U>; // Shared, max 2 TSDs. + struct Secondary { + struct Cache { + static const u32 EntriesArraySize = 16U; + static const u32 QuarantineSize = 32U; + static const u32 DefaultMaxEntriesCount = 4U; + static const uptr DefaultMaxEntrySize = 1UL << 18; + static const s32 MinReleaseToOsIntervalMs = 0; + static const s32 MaxReleaseToOsIntervalMs = 0; + }; + template <typename Config> using CacheT = MapAllocatorCache<Config>; + }; + + template <typename Config> using SecondaryT = MapAllocator<Config>; }; #if SCUDO_CAN_USE_PRIMARY64 struct FuchsiaConfig { - using SizeClassMap = FuchsiaSizeClassMap; static const bool MaySupportMemoryTagging = false; - - typedef SizeClassAllocator64<FuchsiaConfig> Primary; - static const uptr PrimaryRegionSizeLog = 30U; - static const uptr PrimaryGroupSizeLog = 21U; - typedef u32 PrimaryCompactPtrT; - static const bool PrimaryEnableRandomOffset = true; - static const uptr PrimaryMapSizeIncrement = 1UL << 18; - static const uptr PrimaryCompactPtrScale = SCUDO_MIN_ALIGNMENT_LOG; - static const s32 PrimaryMinReleaseToOsIntervalMs = INT32_MIN; - static const s32 PrimaryMaxReleaseToOsIntervalMs = INT32_MAX; - - typedef MapAllocatorNoCache SecondaryCache; template <class A> using TSDRegistryT = TSDRegistrySharedT<A, 8U, 4U>; // Shared, max 8 TSDs. + + struct Primary { + using SizeClassMap = FuchsiaSizeClassMap; +#if SCUDO_RISCV64 + // Support 39-bit VMA for riscv-64 + static const uptr RegionSizeLog = 28U; + static const uptr GroupSizeLog = 19U; +#else + static const uptr RegionSizeLog = 30U; + static const uptr GroupSizeLog = 21U; +#endif + typedef u32 CompactPtrT; + static const bool EnableRandomOffset = true; + static const uptr MapSizeIncrement = 1UL << 18; + static const uptr CompactPtrScale = SCUDO_MIN_ALIGNMENT_LOG; + static const s32 MinReleaseToOsIntervalMs = INT32_MIN; + static const s32 MaxReleaseToOsIntervalMs = INT32_MAX; + }; + template <typename Config> using PrimaryT = SizeClassAllocator64<Config>; + + struct Secondary { + template <typename Config> using CacheT = MapAllocatorNoCache<Config>; + }; + template <typename Config> using SecondaryT = MapAllocator<Config>; }; struct TrustyConfig { - using SizeClassMap = TrustySizeClassMap; - static const bool MaySupportMemoryTagging = false; - - typedef SizeClassAllocator64<TrustyConfig> Primary; - // Some apps have 1 page of heap total so small regions are necessary. - static const uptr PrimaryRegionSizeLog = 10U; - static const uptr PrimaryGroupSizeLog = 10U; - typedef u32 PrimaryCompactPtrT; - static const bool PrimaryEnableRandomOffset = false; - // Trusty is extremely memory-constrained so minimally round up map calls. - static const uptr PrimaryMapSizeIncrement = 1UL << 4; - static const uptr PrimaryCompactPtrScale = SCUDO_MIN_ALIGNMENT_LOG; - static const s32 PrimaryMinReleaseToOsIntervalMs = INT32_MIN; - static const s32 PrimaryMaxReleaseToOsIntervalMs = INT32_MAX; - - typedef MapAllocatorNoCache SecondaryCache; + static const bool MaySupportMemoryTagging = true; template <class A> using TSDRegistryT = TSDRegistrySharedT<A, 1U, 1U>; // Shared, max 1 TSD. + + struct Primary { + using SizeClassMap = TrustySizeClassMap; + static const uptr RegionSizeLog = 28U; + static const uptr GroupSizeLog = 20U; + typedef u32 CompactPtrT; + static const bool EnableRandomOffset = false; + static const uptr MapSizeIncrement = 1UL << 12; + static const uptr CompactPtrScale = SCUDO_MIN_ALIGNMENT_LOG; + static const s32 MinReleaseToOsIntervalMs = INT32_MIN; + static const s32 MaxReleaseToOsIntervalMs = INT32_MAX; + }; + template <typename Config> using PrimaryT = SizeClassAllocator64<Config>; + + struct Secondary { + template <typename Config> using CacheT = MapAllocatorNoCache<Config>; + }; + + template <typename Config> using SecondaryT = MapAllocator<Config>; }; #endif +#ifndef SCUDO_USE_CUSTOM_CONFIG + #if SCUDO_ANDROID typedef AndroidConfig Config; #elif SCUDO_FUCHSIA @@ -215,6 +308,8 @@ typedef TrustyConfig Config; typedef DefaultConfig Config; #endif +#endif // SCUDO_USE_CUSTOM_CONFIG + } // namespace scudo #endif // SCUDO_ALLOCATOR_CONFIG_H_ diff --git a/contrib/llvm-project/compiler-rt/lib/scudo/standalone/chunk.h b/contrib/llvm-project/compiler-rt/lib/scudo/standalone/chunk.h index 88bada8c2d19..32874a8df642 100644 --- a/contrib/llvm-project/compiler-rt/lib/scudo/standalone/chunk.h +++ b/contrib/llvm-project/compiler-rt/lib/scudo/standalone/chunk.h @@ -85,7 +85,7 @@ constexpr uptr OffsetMask = (1UL << 16) - 1; constexpr uptr ChecksumMask = (1UL << 16) - 1; constexpr uptr getHeaderSize() { - return roundUpTo(sizeof(PackedHeader), 1U << SCUDO_MIN_ALIGNMENT_LOG); + return roundUp(sizeof(PackedHeader), 1U << SCUDO_MIN_ALIGNMENT_LOG); } inline AtomicPackedHeader *getAtomicHeader(void *Ptr) { diff --git a/contrib/llvm-project/compiler-rt/lib/scudo/standalone/combined.h b/contrib/llvm-project/compiler-rt/lib/scudo/standalone/combined.h index b6d74ab451b6..b17acc71f892 100644 --- a/contrib/llvm-project/compiler-rt/lib/scudo/standalone/combined.h +++ b/contrib/llvm-project/compiler-rt/lib/scudo/standalone/combined.h @@ -43,13 +43,14 @@ extern "C" size_t android_unsafe_frame_pointer_chase(scudo::uptr *buf, namespace scudo { -template <class Params, void (*PostInitCallback)(void) = EmptyCallback> +template <class Config, void (*PostInitCallback)(void) = EmptyCallback> class Allocator { public: - using PrimaryT = typename Params::Primary; + using PrimaryT = typename Config::template PrimaryT<Config>; + using SecondaryT = typename Config::template SecondaryT<Config>; using CacheT = typename PrimaryT::CacheT; - typedef Allocator<Params, PostInitCallback> ThisT; - typedef typename Params::template TSDRegistryT<ThisT> TSDRegistryT; + typedef Allocator<Config, PostInitCallback> ThisT; + typedef typename Config::template TSDRegistryT<ThisT> TSDRegistryT; void callPostInitCallback() { pthread_once(&PostInitNonce, PostInitCallback); @@ -71,7 +72,7 @@ public: NewHeader.State = Chunk::State::Available; Chunk::compareExchangeHeader(Allocator.Cookie, Ptr, &NewHeader, &Header); - if (allocatorSupportsMemoryTagging<Params>()) + if (allocatorSupportsMemoryTagging<Config>()) Ptr = untagPointer(Ptr); void *BlockBegin = Allocator::getBlockBegin(Ptr, &NewHeader); Cache.deallocate(NewHeader.ClassId, BlockBegin); @@ -98,7 +99,7 @@ public: // Reset tag to 0 as this chunk may have been previously used for a tagged // user allocation. - if (UNLIKELY(useMemoryTagging<Params>(Allocator.Primary.Options.load()))) + if (UNLIKELY(useMemoryTagging<Config>(Allocator.Primary.Options.load()))) storeTags(reinterpret_cast<uptr>(Ptr), reinterpret_cast<uptr>(Ptr) + sizeof(QuarantineBatch)); @@ -162,10 +163,9 @@ public: Primary.Options.set(OptionBit::DeallocTypeMismatch); if (getFlags()->delete_size_mismatch) Primary.Options.set(OptionBit::DeleteSizeMismatch); - if (allocatorSupportsMemoryTagging<Params>() && + if (allocatorSupportsMemoryTagging<Config>() && systemSupportsMemoryTagging()) Primary.Options.set(OptionBit::UseMemoryTagging); - Primary.Options.set(OptionBit::UseOddEvenTags); QuarantineMaxChunkSize = static_cast<u32>(getFlags()->quarantine_max_chunk_size); @@ -178,7 +178,7 @@ public: static_cast<uptr>(getFlags()->quarantine_size_kb << 10), static_cast<uptr>(getFlags()->thread_local_quarantine_size_kb << 10)); - initRingBuffer(); + mapAndInitializeRingBuffer(); } // Initialize the embedded GWP-ASan instance. Requires the main allocator to @@ -228,6 +228,7 @@ public: } void unmapTestOnly() { + unmapRingBuffer(); TSDRegistry.unmapTestOnly(this); Primary.unmapTestOnly(); Secondary.unmapTestOnly(); @@ -239,6 +240,7 @@ public: } TSDRegistryT *getTSDRegistry() { return &TSDRegistry; } + QuarantineT *getQuarantine() { return &Quarantine; } // The Cache must be provided zero-initialized. void initCache(CacheT *Cache) { Cache->init(&Stats, &Primary); } @@ -249,13 +251,20 @@ public: // - unlinking the local stats from the global ones (destroying the cache does // the last two items). void commitBack(TSD<ThisT> *TSD) { - Quarantine.drain(&TSD->QuarantineCache, - QuarantineCallback(*this, TSD->Cache)); - TSD->Cache.destroy(&Stats); + Quarantine.drain(&TSD->getQuarantineCache(), + QuarantineCallback(*this, TSD->getCache())); + TSD->getCache().destroy(&Stats); } + void drainCache(TSD<ThisT> *TSD) { + Quarantine.drainAndRecycle(&TSD->getQuarantineCache(), + QuarantineCallback(*this, TSD->getCache())); + TSD->getCache().drain(); + } + void drainCaches() { TSDRegistry.drainCaches(this); } + ALWAYS_INLINE void *getHeaderTaggedPointer(void *Ptr) { - if (!allocatorSupportsMemoryTagging<Params>()) + if (!allocatorSupportsMemoryTagging<Config>()) return Ptr; auto UntaggedPtr = untagPointer(Ptr); if (UntaggedPtr != Ptr) @@ -267,7 +276,7 @@ public: } ALWAYS_INLINE uptr addHeaderTag(uptr Ptr) { - if (!allocatorSupportsMemoryTagging<Params>()) + if (!allocatorSupportsMemoryTagging<Config>()) return Ptr; return addFixedTag(Ptr, 2); } @@ -305,7 +314,7 @@ public: NOINLINE void *allocate(uptr Size, Chunk::Origin Origin, uptr Alignment = MinAlignment, - bool ZeroContents = false) { + bool ZeroContents = false) NO_THREAD_SAFETY_ANALYSIS { initThreadMaybe(); const Options Options = Primary.Options.load(); @@ -342,7 +351,7 @@ public: // to be sure that there will be an address in the block that will satisfy // the alignment. const uptr NeededSize = - roundUpTo(Size, MinAlignment) + + roundUp(Size, MinAlignment) + ((Alignment > MinAlignment) ? Alignment : Chunk::getHeaderSize()); // Takes care of extravagantly large sizes as well as integer overflows. @@ -375,23 +384,24 @@ public: DCHECK_NE(ClassId, 0U); bool UnlockRequired; auto *TSD = TSDRegistry.getTSDAndLock(&UnlockRequired); - Block = TSD->Cache.allocate(ClassId); + Block = TSD->getCache().allocate(ClassId); // If the allocation failed, the most likely reason with a 32-bit primary // is the region being full. In that event, retry in each successively // larger class until it fits. If it fails to fit in the largest class, // fallback to the Secondary. if (UNLIKELY(!Block)) { while (ClassId < SizeClassMap::LargestClassId && !Block) - Block = TSD->Cache.allocate(++ClassId); + Block = TSD->getCache().allocate(++ClassId); if (!Block) ClassId = 0; } if (UnlockRequired) TSD->unlock(); } - if (UNLIKELY(ClassId == 0)) + if (UNLIKELY(ClassId == 0)) { Block = Secondary.allocate(Options, Size, Alignment, &SecondaryBlockEnd, FillContents); + } if (UNLIKELY(!Block)) { if (Options.get(OptionBit::MayReturnNull)) @@ -401,7 +411,7 @@ public: const uptr BlockUptr = reinterpret_cast<uptr>(Block); const uptr UnalignedUserPtr = BlockUptr + Chunk::getHeaderSize(); - const uptr UserPtr = roundUpTo(UnalignedUserPtr, Alignment); + const uptr UserPtr = roundUp(UnalignedUserPtr, Alignment); void *Ptr = reinterpret_cast<void *>(UserPtr); void *TaggedPtr = Ptr; @@ -417,7 +427,7 @@ public: // // When memory tagging is enabled, zeroing the contents is done as part of // setting the tag. - if (UNLIKELY(useMemoryTagging<Params>(Options))) { + if (UNLIKELY(useMemoryTagging<Config>(Options))) { uptr PrevUserPtr; Chunk::UnpackedHeader Header; const uptr BlockSize = PrimaryT::getSizeByClassId(ClassId); @@ -460,7 +470,7 @@ public: PrevUserPtr == UserPtr && (TaggedUserPtr = loadTag(UserPtr)) != UserPtr) { uptr PrevEnd = TaggedUserPtr + Header.SizeOrUnusedBytes; - const uptr NextPage = roundUpTo(TaggedUserPtr, getPageSizeCached()); + const uptr NextPage = roundUp(TaggedUserPtr, getPageSizeCached()); if (NextPage < PrevEnd && loadTag(NextPage) != NextPage) PrevEnd = NextPage; TaggedPtr = reinterpret_cast<void *>(TaggedUserPtr); @@ -473,8 +483,8 @@ public: // was freed, it would not have been retagged and thus zeroed, and // therefore it needs to be zeroed now. memset(TaggedPtr, 0, - Min(Size, roundUpTo(PrevEnd - TaggedUserPtr, - archMemoryTagGranuleSize()))); + Min(Size, roundUp(PrevEnd - TaggedUserPtr, + archMemoryTagGranuleSize()))); } else if (Size) { // Clear any stack metadata that may have previously been stored in // the chunk data. @@ -499,7 +509,7 @@ public: } else { Block = addHeaderTag(Block); Ptr = addHeaderTag(Ptr); - if (UNLIKELY(useMemoryTagging<Params>(Options))) { + if (UNLIKELY(useMemoryTagging<Config>(Options))) { storeTags(reinterpret_cast<uptr>(Block), reinterpret_cast<uptr>(Ptr)); storeSecondaryAllocationStackMaybe(Options, Ptr, Size); } @@ -666,7 +676,7 @@ public: (reinterpret_cast<uptr>(OldTaggedPtr) + NewSize)) & Chunk::SizeOrUnusedBytesMask; Chunk::compareExchangeHeader(Cookie, OldPtr, &NewHeader, &OldHeader); - if (UNLIKELY(useMemoryTagging<Params>(Options))) { + if (UNLIKELY(useMemoryTagging<Config>(Options))) { if (ClassId) { resizeTaggedChunk(reinterpret_cast<uptr>(OldTaggedPtr) + OldSize, reinterpret_cast<uptr>(OldTaggedPtr) + NewSize, @@ -687,6 +697,8 @@ public: void *NewPtr = allocate(NewSize, Chunk::Origin::Malloc, Alignment); if (LIKELY(NewPtr)) { memcpy(NewPtr, OldTaggedPtr, Min(NewSize, OldSize)); + if (UNLIKELY(&__scudo_deallocate_hook)) + __scudo_deallocate_hook(OldTaggedPtr); quarantineOrDeallocateChunk(Options, OldTaggedPtr, &OldHeader, OldSize); } return NewPtr; @@ -695,7 +707,7 @@ public: // TODO(kostyak): disable() is currently best-effort. There are some small // windows of time when an allocation could still succeed after // this function finishes. We will revisit that later. - void disable() { + void disable() NO_THREAD_SAFETY_ANALYSIS { initThreadMaybe(); #ifdef GWP_ASAN_HOOKS GuardedAlloc.disable(); @@ -707,7 +719,7 @@ public: Secondary.disable(); } - void enable() { + void enable() NO_THREAD_SAFETY_ANALYSIS { initThreadMaybe(); Secondary.enable(); Primary.enable(); @@ -726,9 +738,7 @@ public: // sizing purposes. uptr getStats(char *Buffer, uptr Size) { ScopedString Str; - disable(); const uptr Length = getStats(&Str) + 1; - enable(); if (Length < Size) Size = Length; if (Buffer && Size) { @@ -740,15 +750,15 @@ public: void printStats() { ScopedString Str; - disable(); getStats(&Str); - enable(); Str.output(); } - void releaseToOS() { + void releaseToOS(ReleaseToOS ReleaseType) { initThreadMaybe(); - Primary.releaseToOS(); + if (ReleaseType == ReleaseToOS::ForceAll) + drainCaches(); + Primary.releaseToOS(ReleaseType); Secondary.releaseToOS(); } @@ -762,7 +772,7 @@ public: Base = untagPointer(Base); const uptr From = Base; const uptr To = Base + Size; - bool MayHaveTaggedPrimary = allocatorSupportsMemoryTagging<Params>() && + bool MayHaveTaggedPrimary = allocatorSupportsMemoryTagging<Config>() && systemSupportsMemoryTagging(); auto Lambda = [this, From, To, MayHaveTaggedPrimary, Callback, Arg](uptr Block) { @@ -784,9 +794,9 @@ public: } if (Header.State == Chunk::State::Allocated) { uptr TaggedChunk = Chunk; - if (allocatorSupportsMemoryTagging<Params>()) + if (allocatorSupportsMemoryTagging<Config>()) TaggedChunk = untagPointer(TaggedChunk); - if (useMemoryTagging<Params>(Primary.Options.load())) + if (useMemoryTagging<Config>(Primary.Options.load())) TaggedChunk = loadTag(Chunk); Callback(TaggedChunk, getSize(reinterpret_cast<void *>(Chunk), &Header), Arg); @@ -885,7 +895,7 @@ public: } bool useMemoryTaggingTestOnly() const { - return useMemoryTagging<Params>(Primary.Options.load()); + return useMemoryTagging<Config>(Primary.Options.load()); } void disableMemoryTagging() { // If we haven't been initialized yet, we need to initialize now in order to @@ -895,7 +905,7 @@ public: // callback), which may cause mappings to be created with memory tagging // enabled. TSDRegistry.initOnceMaybe(this); - if (allocatorSupportsMemoryTagging<Params>()) { + if (allocatorSupportsMemoryTagging<Config>()) { Secondary.disableMemoryTagging(); Primary.Options.clear(OptionBit::UseMemoryTagging); } @@ -979,7 +989,7 @@ public: const char *Memory, const char *MemoryTags, uintptr_t MemoryAddr, size_t MemorySize) { *ErrorInfo = {}; - if (!allocatorSupportsMemoryTagging<Params>() || + if (!allocatorSupportsMemoryTagging<Config>() || MemoryAddr + MemorySize < MemoryAddr) return; @@ -1007,7 +1017,6 @@ public: } private: - using SecondaryT = MapAllocator<Params>; typedef typename PrimaryT::SizeClassMap SizeClassMap; static const uptr MinAlignmentLog = SCUDO_MIN_ALIGNMENT_LOG; @@ -1019,7 +1028,7 @@ private: static_assert(MinAlignment >= sizeof(Chunk::PackedHeader), "Minimal alignment must at least cover a chunk header."); - static_assert(!allocatorSupportsMemoryTagging<Params>() || + static_assert(!allocatorSupportsMemoryTagging<Config>() || MinAlignment >= archMemoryTagGranuleSize(), ""); @@ -1119,14 +1128,15 @@ private: const uptr SizeOrUnusedBytes = Header->SizeOrUnusedBytes; if (LIKELY(Header->ClassId)) return SizeOrUnusedBytes; - if (allocatorSupportsMemoryTagging<Params>()) + if (allocatorSupportsMemoryTagging<Config>()) Ptr = untagPointer(const_cast<void *>(Ptr)); return SecondaryT::getBlockEnd(getBlockBegin(Ptr, Header)) - reinterpret_cast<uptr>(Ptr) - SizeOrUnusedBytes; } void quarantineOrDeallocateChunk(Options Options, void *TaggedPtr, - Chunk::UnpackedHeader *Header, uptr Size) { + Chunk::UnpackedHeader *Header, + uptr Size) NO_THREAD_SAFETY_ANALYSIS { void *Ptr = getHeaderTaggedPointer(TaggedPtr); Chunk::UnpackedHeader NewHeader = *Header; // If the quarantine is disabled, the actual size of a chunk is 0 or larger @@ -1139,12 +1149,12 @@ private: NewHeader.State = Chunk::State::Available; else NewHeader.State = Chunk::State::Quarantined; - NewHeader.OriginOrWasZeroed = useMemoryTagging<Params>(Options) && + NewHeader.OriginOrWasZeroed = useMemoryTagging<Config>(Options) && NewHeader.ClassId && !TSDRegistry.getDisableMemInit(); Chunk::compareExchangeHeader(Cookie, Ptr, &NewHeader, Header); - if (UNLIKELY(useMemoryTagging<Params>(Options))) { + if (UNLIKELY(useMemoryTagging<Config>(Options))) { u8 PrevTag = extractTag(reinterpret_cast<uptr>(TaggedPtr)); storeDeallocationStackMaybe(Options, Ptr, PrevTag, Size); if (NewHeader.ClassId) { @@ -1161,18 +1171,25 @@ private: } } if (BypassQuarantine) { - if (allocatorSupportsMemoryTagging<Params>()) + if (allocatorSupportsMemoryTagging<Config>()) Ptr = untagPointer(Ptr); void *BlockBegin = getBlockBegin(Ptr, &NewHeader); const uptr ClassId = NewHeader.ClassId; if (LIKELY(ClassId)) { bool UnlockRequired; auto *TSD = TSDRegistry.getTSDAndLock(&UnlockRequired); - TSD->Cache.deallocate(ClassId, BlockBegin); + const bool CacheDrained = + TSD->getCache().deallocate(ClassId, BlockBegin); if (UnlockRequired) TSD->unlock(); + // When we have drained some blocks back to the Primary from TSD, that + // implies that we may have the chance to release some pages as well. + // Note that in order not to block other thread's accessing the TSD, + // release the TSD first then try the page release. + if (CacheDrained) + Primary.tryReleaseToOS(ClassId, ReleaseToOS::Normal); } else { - if (UNLIKELY(useMemoryTagging<Params>(Options))) + if (UNLIKELY(useMemoryTagging<Config>(Options))) storeTags(reinterpret_cast<uptr>(BlockBegin), reinterpret_cast<uptr>(Ptr)); Secondary.deallocate(Options, BlockBegin); @@ -1180,8 +1197,8 @@ private: } else { bool UnlockRequired; auto *TSD = TSDRegistry.getTSDAndLock(&UnlockRequired); - Quarantine.put(&TSD->QuarantineCache, - QuarantineCallback(*this, TSD->Cache), Ptr, Size); + Quarantine.put(&TSD->getQuarantineCache(), + QuarantineCallback(*this, TSD->getCache()), Ptr, Size); if (UnlockRequired) TSD->unlock(); } @@ -1241,15 +1258,15 @@ private: void resizeTaggedChunk(uptr OldPtr, uptr NewPtr, uptr NewSize, uptr BlockEnd) { - uptr RoundOldPtr = roundUpTo(OldPtr, archMemoryTagGranuleSize()); + uptr RoundOldPtr = roundUp(OldPtr, archMemoryTagGranuleSize()); uptr RoundNewPtr; if (RoundOldPtr >= NewPtr) { // If the allocation is shrinking we just need to set the tag past the end // of the allocation to 0. See explanation in storeEndMarker() above. - RoundNewPtr = roundUpTo(NewPtr, archMemoryTagGranuleSize()); + RoundNewPtr = roundUp(NewPtr, archMemoryTagGranuleSize()); } else { // Set the memory tag of the region - // [RoundOldPtr, roundUpTo(NewPtr, archMemoryTagGranuleSize())) + // [RoundOldPtr, roundUp(NewPtr, archMemoryTagGranuleSize())) // to the pointer tag stored in OldPtr. RoundNewPtr = storeTags(RoundOldPtr, NewPtr); } @@ -1483,6 +1500,7 @@ private: Primary.getStats(Str); Secondary.getStats(Str); Quarantine.getStats(Str); + TSDRegistry.getStats(Str); return Str->length(); } @@ -1497,16 +1515,16 @@ private: &RawRingBuffer[sizeof(AllocationRingBuffer)])[N]; } - void initRingBuffer() { + void mapAndInitializeRingBuffer() { u32 AllocationRingBufferSize = static_cast<u32>(getFlags()->allocation_ring_buffer_size); if (AllocationRingBufferSize < 1) return; - MapPlatformData Data = {}; RawRingBuffer = static_cast<char *>( map(/*Addr=*/nullptr, - roundUpTo(ringBufferSizeInBytes(AllocationRingBufferSize), getPageSizeCached()), - "AllocatorRingBuffer", /*Flags=*/0, &Data)); + roundUp(ringBufferSizeInBytes(AllocationRingBufferSize), + getPageSizeCached()), + "AllocatorRingBuffer")); auto *RingBuffer = reinterpret_cast<AllocationRingBuffer *>(RawRingBuffer); RingBuffer->Size = AllocationRingBufferSize; static_assert(sizeof(AllocationRingBuffer) % @@ -1515,6 +1533,11 @@ private: "invalid alignment"); } + void unmapRingBuffer() { + unmap(RawRingBuffer, roundUp(getRingBufferSize(), getPageSizeCached())); + RawRingBuffer = nullptr; + } + static constexpr size_t ringBufferSizeInBytes(u32 AllocationRingBufferSize) { return sizeof(AllocationRingBuffer) + AllocationRingBufferSize * diff --git a/contrib/llvm-project/compiler-rt/lib/scudo/standalone/common.h b/contrib/llvm-project/compiler-rt/lib/scudo/standalone/common.h index 2ec9a630359a..82e6cf4aee61 100644 --- a/contrib/llvm-project/compiler-rt/lib/scudo/standalone/common.h +++ b/contrib/llvm-project/compiler-rt/lib/scudo/standalone/common.h @@ -27,17 +27,31 @@ template <class Dest, class Source> inline Dest bit_cast(const Source &S) { return D; } -inline constexpr uptr roundUpTo(uptr X, uptr Boundary) { +inline constexpr bool isPowerOfTwo(uptr X) { return (X & (X - 1)) == 0; } + +inline constexpr uptr roundUp(uptr X, uptr Boundary) { + DCHECK(isPowerOfTwo(Boundary)); return (X + Boundary - 1) & ~(Boundary - 1); } +inline constexpr uptr roundUpSlow(uptr X, uptr Boundary) { + return ((X + Boundary - 1) / Boundary) * Boundary; +} -inline constexpr uptr roundDownTo(uptr X, uptr Boundary) { +inline constexpr uptr roundDown(uptr X, uptr Boundary) { + DCHECK(isPowerOfTwo(Boundary)); return X & ~(Boundary - 1); } +inline constexpr uptr roundDownSlow(uptr X, uptr Boundary) { + return (X / Boundary) * Boundary; +} inline constexpr bool isAligned(uptr X, uptr Alignment) { + DCHECK(isPowerOfTwo(Alignment)); return (X & (Alignment - 1)) == 0; } +inline constexpr bool isAlignedSlow(uptr X, uptr Alignment) { + return X % Alignment == 0; +} template <class T> constexpr T Min(T A, T B) { return A < B ? A : B; } @@ -49,14 +63,12 @@ template <class T> void Swap(T &A, T &B) { B = Tmp; } -inline bool isPowerOfTwo(uptr X) { return (X & (X - 1)) == 0; } - inline uptr getMostSignificantSetBitIndex(uptr X) { DCHECK_NE(X, 0U); return SCUDO_WORDSIZE - 1U - static_cast<uptr>(__builtin_clzl(X)); } -inline uptr roundUpToPowerOfTwo(uptr Size) { +inline uptr roundUpPowerOfTwo(uptr Size) { DCHECK(Size); if (isPowerOfTwo(Size)) return Size; @@ -135,6 +147,9 @@ const char *getEnv(const char *Name); uptr GetRSS(); u64 getMonotonicTime(); +// Gets the time faster but with less accuracy. Can call getMonotonicTime +// if no fast version is available. +u64 getMonotonicTimeFast(); u32 getThreadID(); @@ -200,6 +215,13 @@ enum class Option : u8 { MaxTSDsCount, // Number of usable TSDs for the shared registry. }; +enum class ReleaseToOS : u8 { + Normal, // Follow the normal rules for releasing pages to the OS + Force, // Force release pages to the OS, but avoid cases that take too long. + ForceAll, // Force release every page possible regardless of how long it will + // take. +}; + constexpr unsigned char PatternFillByte = 0xAB; enum FillContentsMode { diff --git a/contrib/llvm-project/compiler-rt/lib/scudo/standalone/fuchsia.cpp b/contrib/llvm-project/compiler-rt/lib/scudo/standalone/fuchsia.cpp index 70e4e714f2cb..0788c4198e53 100644 --- a/contrib/llvm-project/compiler-rt/lib/scudo/standalone/fuchsia.cpp +++ b/contrib/llvm-project/compiler-rt/lib/scudo/standalone/fuchsia.cpp @@ -19,6 +19,7 @@ #include <zircon/compiler.h> #include <zircon/process.h> #include <zircon/sanitizer.h> +#include <zircon/status.h> #include <zircon/syscalls.h> namespace scudo { @@ -31,6 +32,16 @@ void NORETURN die() { __builtin_trap(); } // with ZX_HANDLE_INVALID. static_assert(ZX_HANDLE_INVALID == 0, ""); +static void NORETURN dieOnError(zx_status_t Status, const char *FnName, + uptr Size) { + char Error[128]; + formatString(Error, sizeof(Error), + "SCUDO ERROR: %s failed with size %zuKB (%s)", FnName, + Size >> 10, zx_status_get_string(Status)); + outputRaw(Error); + die(); +} + static void *allocateVmar(uptr Size, MapPlatformData *Data, bool AllowNoMem) { // Only scenario so far. DCHECK(Data); @@ -42,7 +53,7 @@ static void *allocateVmar(uptr Size, MapPlatformData *Data, bool AllowNoMem) { Size, &Data->Vmar, &Data->VmarBase); if (UNLIKELY(Status != ZX_OK)) { if (Status != ZX_ERR_NO_MEMORY || !AllowNoMem) - dieOnMapUnmapError(Status == ZX_ERR_NO_MEMORY ? Size : 0); + dieOnError(Status, "zx_vmar_allocate", Size); return nullptr; } return reinterpret_cast<void *>(Data->VmarBase); @@ -73,7 +84,7 @@ void *map(void *Addr, uptr Size, const char *Name, uptr Flags, Status = _zx_vmo_set_size(Vmo, VmoSize + Size); if (Status != ZX_OK) { if (Status != ZX_ERR_NO_MEMORY || !AllowNoMem) - dieOnMapUnmapError(Status == ZX_ERR_NO_MEMORY ? Size : 0); + dieOnError(Status, "zx_vmo_set_size", VmoSize + Size); return nullptr; } } else { @@ -81,7 +92,7 @@ void *map(void *Addr, uptr Size, const char *Name, uptr Flags, Status = _zx_vmo_create(Size, ZX_VMO_RESIZABLE, &Vmo); if (UNLIKELY(Status != ZX_OK)) { if (Status != ZX_ERR_NO_MEMORY || !AllowNoMem) - dieOnMapUnmapError(Status == ZX_ERR_NO_MEMORY ? Size : 0); + dieOnError(Status, "zx_vmo_create", Size); return nullptr; } _zx_object_set_property(Vmo, ZX_PROP_NAME, Name, strlen(Name)); @@ -99,7 +110,7 @@ void *map(void *Addr, uptr Size, const char *Name, uptr Flags, Status = _zx_vmar_map(Vmar, MapFlags, Offset, Vmo, VmoSize, Size, &P); if (UNLIKELY(Status != ZX_OK)) { if (Status != ZX_ERR_NO_MEMORY || !AllowNoMem) - dieOnMapUnmapError(Status == ZX_ERR_NO_MEMORY ? Size : 0); + dieOnError(Status, "zx_vmar_map", Size); return nullptr; } @@ -120,7 +131,7 @@ void *map(void *Addr, uptr Size, const char *Name, uptr Flags, } if (UNLIKELY(Status != ZX_OK)) { if (Status != ZX_ERR_NO_MEMORY || !AllowNoMem) - dieOnMapUnmapError(Status == ZX_ERR_NO_MEMORY ? Size : 0); + dieOnError(Status, "zx_vmar_op_range", Size); return nullptr; } @@ -145,7 +156,7 @@ void unmap(void *Addr, uptr Size, uptr Flags, MapPlatformData *Data) { const zx_status_t Status = _zx_vmar_unmap(Vmar, reinterpret_cast<uintptr_t>(Addr), Size); if (UNLIKELY(Status != ZX_OK)) - dieOnMapUnmapError(); + dieOnError(Status, "zx_vmar_unmap", Size); } if (Data) { if (Data->Vmo != ZX_HANDLE_INVALID) @@ -160,12 +171,15 @@ void setMemoryPermission(UNUSED uptr Addr, UNUSED uptr Size, UNUSED uptr Flags, (Flags & MAP_NOACCESS) ? 0 : (ZX_VM_PERM_READ | ZX_VM_PERM_WRITE); DCHECK(Data); DCHECK_NE(Data->Vmar, ZX_HANDLE_INVALID); - if (_zx_vmar_protect(Data->Vmar, Prot, Addr, Size) != ZX_OK) - dieOnMapUnmapError(); + const zx_status_t Status = _zx_vmar_protect(Data->Vmar, Prot, Addr, Size); + if (Status != ZX_OK) + dieOnError(Status, "zx_vmar_protect", Size); } void releasePagesToOS(UNUSED uptr BaseAddress, uptr Offset, uptr Size, MapPlatformData *Data) { + // TODO: DCHECK the BaseAddress is consistent with the data in + // MapPlatformData. DCHECK(Data); DCHECK_NE(Data->Vmar, ZX_HANDLE_INVALID); DCHECK_NE(Data->Vmo, ZX_HANDLE_INVALID); @@ -195,7 +209,10 @@ void HybridMutex::unlock() __TA_NO_THREAD_SAFETY_ANALYSIS { sync_mutex_unlock(&M); } +void HybridMutex::assertHeldImpl() __TA_NO_THREAD_SAFETY_ANALYSIS {} + u64 getMonotonicTime() { return _zx_clock_get_monotonic(); } +u64 getMonotonicTimeFast() { return _zx_clock_get_monotonic(); } u32 getNumberOfCPUs() { return _zx_system_get_num_cpus(); } diff --git a/contrib/llvm-project/compiler-rt/lib/scudo/standalone/include/scudo/interface.h b/contrib/llvm-project/compiler-rt/lib/scudo/standalone/include/scudo/interface.h index 23bcfba3982a..6c0c521f8d82 100644 --- a/contrib/llvm-project/compiler-rt/lib/scudo/standalone/include/scudo/interface.h +++ b/contrib/llvm-project/compiler-rt/lib/scudo/standalone/include/scudo/interface.h @@ -118,6 +118,10 @@ size_t __scudo_get_ring_buffer_size(void); #define M_PURGE -101 #endif +#ifndef M_PURGE_ALL +#define M_PURGE_ALL -104 +#endif + // Tune the allocator's choice of memory tags to make it more likely that // a certain class of memory errors will be detected. The value argument should // be one of the M_MEMTAG_TUNING_* constants below. @@ -155,6 +159,11 @@ size_t __scudo_get_ring_buffer_size(void); #define M_MEMTAG_TUNING_UAF 1 #endif +// Print internal stats to the log. +#ifndef M_LOG_STATS +#define M_LOG_STATS -205 +#endif + } // extern "C" #endif // SCUDO_INTERFACE_H_ diff --git a/contrib/llvm-project/compiler-rt/lib/scudo/standalone/linux.cpp b/contrib/llvm-project/compiler-rt/lib/scudo/standalone/linux.cpp index 9c5755af5750..e285d8a3d2d2 100644 --- a/contrib/llvm-project/compiler-rt/lib/scudo/standalone/linux.cpp +++ b/contrib/llvm-project/compiler-rt/lib/scudo/standalone/linux.cpp @@ -11,6 +11,7 @@ #if SCUDO_LINUX #include "common.h" +#include "internal_defs.h" #include "linux.h" #include "mutex.h" #include "string_utils.h" @@ -128,6 +129,10 @@ void HybridMutex::unlock() { } } +void HybridMutex::assertHeldImpl() { + CHECK(atomic_load(&M, memory_order_acquire) != Unlocked); +} + u64 getMonotonicTime() { timespec TS; clock_gettime(CLOCK_MONOTONIC, &TS); @@ -135,6 +140,17 @@ u64 getMonotonicTime() { static_cast<u64>(TS.tv_nsec); } +u64 getMonotonicTimeFast() { +#if defined(CLOCK_MONOTONIC_COARSE) + timespec TS; + clock_gettime(CLOCK_MONOTONIC_COARSE, &TS); + return static_cast<u64>(TS.tv_sec) * (1000ULL * 1000 * 1000) + + static_cast<u64>(TS.tv_nsec); +#else + return getMonotonicTime(); +#endif +} + u32 getNumberOfCPUs() { cpu_set_t CPUs; // sched_getaffinity can fail for a variety of legitimate reasons (lack of diff --git a/contrib/llvm-project/compiler-rt/lib/scudo/standalone/local_cache.h b/contrib/llvm-project/compiler-rt/lib/scudo/standalone/local_cache.h index 6e84158659ae..1095eb5f186d 100644 --- a/contrib/llvm-project/compiler-rt/lib/scudo/standalone/local_cache.h +++ b/contrib/llvm-project/compiler-rt/lib/scudo/standalone/local_cache.h @@ -14,6 +14,7 @@ #include "platform.h" #include "report.h" #include "stats.h" +#include "string_utils.h" namespace scudo { @@ -34,6 +35,15 @@ template <class SizeClassAllocator> struct SizeClassAllocatorLocalCache { // u16 will be promoted to int by arithmetic type conversion. Count = static_cast<u16>(Count + N); } + void appendFromTransferBatch(TransferBatch *B, u16 N) { + DCHECK_LE(N, MaxNumCached - Count); + DCHECK_GE(B->Count, N); + // Append from the back of `B`. + memcpy(Batch + Count, B->Batch + (B->Count - N), sizeof(Batch[0]) * N); + // u16 will be promoted to int by arithmetic type conversion. + Count = static_cast<u16>(Count + N); + B->Count = static_cast<u16>(B->Count - N); + } void clear() { Count = 0; } void add(CompactPtrT P) { DCHECK_LT(Count, MaxNumCached); @@ -43,6 +53,7 @@ template <class SizeClassAllocator> struct SizeClassAllocatorLocalCache { memcpy(Array, Batch, sizeof(Batch[0]) * Count); } u16 getCount() const { return Count; } + bool isEmpty() const { return Count == 0U; } CompactPtrT get(u16 I) const { DCHECK_LE(I, Count); return Batch[I]; @@ -62,17 +73,16 @@ template <class SizeClassAllocator> struct SizeClassAllocatorLocalCache { struct BatchGroup { // `Next` is used by IntrusiveList. BatchGroup *Next; - // The identifier of each group - uptr GroupId; + // The compact base address of each group + uptr CompactPtrGroupBase; // Cache value of TransferBatch::getMaxCached() u16 MaxCachedPerBatch; // Number of blocks pushed into this group. This is an increment-only // counter. uptr PushedBlocks; - // This is used to track how many blocks are pushed since last time we - // checked `PushedBlocks`. It's useful for page releasing to determine the - // usage of a BatchGroup. - uptr PushedBlocksAtLastCheckpoint; + // This is used to track how many bytes are not in-use since last time we + // tried to release pages. + uptr BytesInBGAtLastCheckpoint; // Blocks are managed by TransferBatch in a list. SinglyLinkedList<TransferBatch> Batches; }; @@ -112,13 +122,16 @@ template <class SizeClassAllocator> struct SizeClassAllocatorLocalCache { return Allocator->decompactPtr(ClassId, CompactP); } - void deallocate(uptr ClassId, void *P) { + bool deallocate(uptr ClassId, void *P) { CHECK_LT(ClassId, NumClasses); PerClass *C = &PerClassArray[ClassId]; // We still have to initialize the cache in the event that the first heap // operation in a thread is a deallocation. initCacheMaybe(C); - if (C->Count == C->MaxCount) + + // If the cache is full, drain half of blocks back to the main allocator. + const bool NeedToDrainCache = C->Count == C->MaxCount; + if (NeedToDrainCache) drain(C, ClassId); // See comment in allocate() about memory accesses. const uptr ClassSize = C->ClassSize; @@ -126,6 +139,8 @@ template <class SizeClassAllocator> struct SizeClassAllocatorLocalCache { Allocator->compactPtr(ClassId, reinterpret_cast<uptr>(P)); Stats.sub(StatAllocated, ClassSize); Stats.add(StatFree, ClassSize); + + return NeedToDrainCache; } bool isEmpty() const { @@ -165,6 +180,29 @@ template <class SizeClassAllocator> struct SizeClassAllocatorLocalCache { LocalStats &getStats() { return Stats; } + void getStats(ScopedString *Str) { + bool EmptyCache = true; + for (uptr I = 0; I < NumClasses; ++I) { + if (PerClassArray[I].Count == 0) + continue; + + EmptyCache = false; + // The size of BatchClass is set to 0 intentionally. See the comment in + // initCache() for more details. + const uptr ClassSize = I == BatchClassId + ? SizeClassAllocator::getSizeByClassId(I) + : PerClassArray[I].ClassSize; + // Note that the string utils don't support printing u16 thus we cast it + // to a common use type uptr. + Str->append(" %02zu (%6zu): cached: %4zu max: %4zu\n", I, ClassSize, + static_cast<uptr>(PerClassArray[I].Count), + static_cast<uptr>(PerClassArray[I].MaxCount)); + } + + if (EmptyCache) + Str->append(" No block is cached.\n"); + } + private: static const uptr NumClasses = SizeClassMap::NumClasses; static const uptr BatchClassId = SizeClassMap::BatchClassId; diff --git a/contrib/llvm-project/compiler-rt/lib/scudo/standalone/mem_map.cpp b/contrib/llvm-project/compiler-rt/lib/scudo/standalone/mem_map.cpp new file mode 100644 index 000000000000..115cc34e7060 --- /dev/null +++ b/contrib/llvm-project/compiler-rt/lib/scudo/standalone/mem_map.cpp @@ -0,0 +1,84 @@ +//===-- mem_map.cpp ---------------------------------------------*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#include "mem_map.h" + +#include "common.h" + +namespace scudo { + +bool MemMapDefault::mapImpl(uptr Addr, uptr Size, const char *Name, + uptr Flags) { + void *MappedAddr = + ::scudo::map(reinterpret_cast<void *>(Addr), Size, Name, Flags, &Data); + if (MappedAddr == nullptr) + return false; + Base = reinterpret_cast<uptr>(MappedAddr); + MappedBase = Base; + Capacity = Size; + return true; +} + +void MemMapDefault::unmapImpl(uptr Addr, uptr Size) { + if (Size == Capacity) { + Base = MappedBase = Capacity = 0; + } else { + if (Base == Addr) { + Base = Addr + Size; + MappedBase = MappedBase == 0 ? Base : Max(MappedBase, Base); + } + Capacity -= Size; + } + + ::scudo::unmap(reinterpret_cast<void *>(Addr), Size, UNMAP_ALL, &Data); +} + +bool MemMapDefault::remapImpl(uptr Addr, uptr Size, const char *Name, + uptr Flags) { + void *RemappedPtr = + ::scudo::map(reinterpret_cast<void *>(Addr), Size, Name, Flags, &Data); + const uptr RemappedAddr = reinterpret_cast<uptr>(RemappedPtr); + MappedBase = MappedBase == 0 ? RemappedAddr : Min(MappedBase, RemappedAddr); + return RemappedAddr == Addr; +} + +void MemMapDefault::releaseAndZeroPagesToOSImpl(uptr From, uptr Size) { + DCHECK_NE(MappedBase, 0U); + DCHECK_GE(From, MappedBase); + return ::scudo::releasePagesToOS(MappedBase, From - MappedBase, Size, &Data); +} + +void MemMapDefault::setMemoryPermissionImpl(uptr Addr, uptr Size, uptr Flags) { + return ::scudo::setMemoryPermission(Addr, Size, Flags); +} + +void ReservedMemoryDefault::releaseImpl() { + ::scudo::unmap(reinterpret_cast<void *>(Base), Capacity, UNMAP_ALL, &Data); +} + +bool ReservedMemoryDefault::createImpl(uptr Addr, uptr Size, const char *Name, + uptr Flags) { + void *Reserved = ::scudo::map(reinterpret_cast<void *>(Addr), Size, Name, + Flags | MAP_NOACCESS, &Data); + if (Reserved == nullptr) + return false; + + Base = reinterpret_cast<uptr>(Reserved); + Capacity = Size; + + return true; +} + +ReservedMemoryDefault::MemMapT ReservedMemoryDefault::dispatchImpl(uptr Addr, + uptr Size) { + ReservedMemoryDefault::MemMapT NewMap(Addr, Size); + NewMap.setMapPlatformData(Data); + return NewMap; +} + +} // namespace scudo diff --git a/contrib/llvm-project/compiler-rt/lib/scudo/standalone/mem_map.h b/contrib/llvm-project/compiler-rt/lib/scudo/standalone/mem_map.h new file mode 100644 index 000000000000..409e4dbbe04b --- /dev/null +++ b/contrib/llvm-project/compiler-rt/lib/scudo/standalone/mem_map.h @@ -0,0 +1,91 @@ +//===-- mem_map.h -----------------------------------------------*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#ifndef SCUDO_MEM_MAP_H_ +#define SCUDO_MEM_MAP_H_ + +#include "mem_map_base.h" + +#include "common.h" +#include "internal_defs.h" + +// TODO: This is only used for `MapPlatformData`. Remove these includes when we +// have all three platform specific `MemMap` and `ReservedMemory` +// implementations. +#include "fuchsia.h" +#include "linux.h" +#include "trusty.h" + +#include "mem_map_fuchsia.h" + +namespace scudo { + +// This will be deprecated when every allocator has been supported by each +// platform's `MemMap` implementation. +class MemMapDefault final : public MemMapBase<MemMapDefault> { +public: + constexpr MemMapDefault() = default; + MemMapDefault(uptr Base, uptr Capacity) : Base(Base), Capacity(Capacity) {} + + // Impls for base functions. + bool mapImpl(uptr Addr, uptr Size, const char *Name, uptr Flags); + void unmapImpl(uptr Addr, uptr Size); + bool remapImpl(uptr Addr, uptr Size, const char *Name, uptr Flags); + void setMemoryPermissionImpl(uptr Addr, uptr Size, uptr Flags); + void releasePagesToOSImpl(uptr From, uptr Size) { + return releaseAndZeroPagesToOSImpl(From, Size); + } + void releaseAndZeroPagesToOSImpl(uptr From, uptr Size); + uptr getBaseImpl() { return Base; } + uptr getCapacityImpl() { return Capacity; } + + void setMapPlatformData(MapPlatformData &NewData) { Data = NewData; } + +private: + uptr Base = 0; + uptr Capacity = 0; + uptr MappedBase = 0; + MapPlatformData Data = {}; +}; + +// This will be deprecated when every allocator has been supported by each +// platform's `MemMap` implementation. +class ReservedMemoryDefault final + : public ReservedMemory<ReservedMemoryDefault, MemMapDefault> { +public: + constexpr ReservedMemoryDefault() = default; + + bool createImpl(uptr Addr, uptr Size, const char *Name, uptr Flags); + void releaseImpl(); + MemMapT dispatchImpl(uptr Addr, uptr Size); + uptr getBaseImpl() { return Base; } + uptr getCapacityImpl() { return Capacity; } + +private: + uptr Base = 0; + uptr Capacity = 0; + MapPlatformData Data = {}; +}; + +#if SCUDO_LINUX +using ReservedMemoryT = ReservedMemoryDefault; +using MemMapT = ReservedMemoryT::MemMapT; +#elif SCUDO_FUCHSIA +using ReservedMemoryT = ReservedMemoryDefault; +using MemMapT = ReservedMemoryT::MemMapT; +#elif SCUDO_TRUSTY +using ReservedMemoryT = ReservedMemoryDefault; +using MemMapT = ReservedMemoryT::MemMapT; +#else +#error \ + "Unsupported platform, please implement the ReservedMemory for your platform!" +#endif + +} // namespace scudo + +#endif // SCUDO_MEM_MAP_H_ diff --git a/contrib/llvm-project/compiler-rt/lib/scudo/standalone/mem_map_base.h b/contrib/llvm-project/compiler-rt/lib/scudo/standalone/mem_map_base.h new file mode 100644 index 000000000000..99ab0cba604f --- /dev/null +++ b/contrib/llvm-project/compiler-rt/lib/scudo/standalone/mem_map_base.h @@ -0,0 +1,129 @@ +//===-- mem_map_base.h ------------------------------------------*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#ifndef SCUDO_MEM_MAP_BASE_H_ +#define SCUDO_MEM_MAP_BASE_H_ + +#include "common.h" + +namespace scudo { + +// In Scudo, every memory operation will be fulfilled through a +// platform-specific `MemMap` instance. The essential APIs are listed in the +// `MemMapBase` below. This is implemented in CRTP, so for each implementation, +// it has to implement all of the 'Impl' named functions. +template <class Derived> class MemMapBase { +public: + constexpr MemMapBase() = default; + + // This is used to map a new set of contiguous pages. Note that the `Addr` is + // only a suggestion to the system. + bool map(uptr Addr, uptr Size, const char *Name, uptr Flags = 0) { + DCHECK(!isAllocated()); + return invokeImpl(&Derived::mapImpl, Addr, Size, Name, Flags); + } + + // This is used to unmap partial/full pages from the beginning or the end. + // I.e., the result pages are expected to be still contiguous. + void unmap(uptr Addr, uptr Size) { + DCHECK(isAllocated()); + DCHECK((Addr == getBase()) || (Addr + Size == getBase() + getCapacity())); + invokeImpl(&Derived::unmapImpl, Addr, Size); + } + + // This is used to remap a mapped range (either from map() or dispatched from + // ReservedMemory). For example, we have reserved several pages and then we + // want to remap them with different accessibility. + bool remap(uptr Addr, uptr Size, const char *Name, uptr Flags = 0) { + DCHECK(isAllocated()); + DCHECK((Addr >= getBase()) && (Addr + Size <= getBase() + getCapacity())); + return invokeImpl(&Derived::remapImpl, Addr, Size, Name, Flags); + } + + // This is used to update the pages' access permission. For example, mark + // pages as no read/write permission. + void setMemoryPermission(uptr Addr, uptr Size, uptr Flags) { + DCHECK(isAllocated()); + DCHECK((Addr >= getBase()) && (Addr + Size <= getBase() + getCapacity())); + return invokeImpl(&Derived::setMemoryPermissionImpl, Addr, Size, Flags); + } + + // Suggest releasing a set of contiguous physical pages back to the OS. Note + // that only physical pages are supposed to be released. Any release of + // virtual pages may lead to undefined behavior. + void releasePagesToOS(uptr From, uptr Size) { + DCHECK(isAllocated()); + DCHECK((From >= getBase()) && (From + Size <= getBase() + getCapacity())); + invokeImpl(&Derived::releasePagesToOSImpl, From, Size); + } + // This is similar to the above one except that any subsequent access to the + // released pages will return with zero-filled pages. + void releaseAndZeroPagesToOS(uptr From, uptr Size) { + DCHECK(isAllocated()); + DCHECK((From >= getBase()) && (From + Size <= getBase() + getCapacity())); + invokeImpl(&Derived::releaseAndZeroPagesToOSImpl, From, Size); + } + + uptr getBase() { return invokeImpl(&Derived::getBaseImpl); } + uptr getCapacity() { return invokeImpl(&Derived::getCapacityImpl); } + + bool isAllocated() { return getBase() != 0U; } + +protected: + template <typename R, typename... Args> + R invokeImpl(R (Derived::*MemFn)(Args...), Args... args) { + return (static_cast<Derived *>(this)->*MemFn)(args...); + } +}; + +// `ReservedMemory` is a special memory handle which can be viewed as a page +// allocator. `ReservedMemory` will reserve a contiguous pages and the later +// page request can be fulfilled at the designated address. This is used when +// we want to ensure the virtual address of the MemMap will be in a known range. +// This is implemented in CRTP, so for each +// implementation, it has to implement all of the 'Impl' named functions. +template <class Derived, typename MemMapTy> class ReservedMemory { +public: + using MemMapT = MemMapTy; + constexpr ReservedMemory() = default; + + // Reserve a chunk of memory at a suggested address. + bool create(uptr Addr, uptr Size, const char *Name, uptr Flags = 0) { + DCHECK(!isCreated()); + return invokeImpl(&Derived::createImpl, Addr, Size, Name, Flags); + } + + // Release the entire reserved memory. + void release() { + DCHECK(isCreated()); + invokeImpl(&Derived::releaseImpl); + } + + // Dispatch a sub-range of reserved memory. Note that any fragmentation of + // the reserved pages is managed by each implementation. + MemMapT dispatch(uptr Addr, uptr Size) { + DCHECK(isCreated()); + DCHECK((Addr >= getBase()) && (Addr + Size <= getBase() + getCapacity())); + return invokeImpl(&Derived::dispatchImpl, Addr, Size); + } + + uptr getBase() { return invokeImpl(&Derived::getBaseImpl); } + uptr getCapacity() { return invokeImpl(&Derived::getCapacityImpl); } + + bool isCreated() { return getBase() != 0U; } + +protected: + template <typename R, typename... Args> + R invokeImpl(R (Derived::*MemFn)(Args...), Args... args) { + return (static_cast<Derived *>(this)->*MemFn)(args...); + } +}; + +} // namespace scudo + +#endif // SCUDO_MEM_MAP_BASE_H_ diff --git a/contrib/llvm-project/compiler-rt/lib/scudo/standalone/mem_map_fuchsia.cpp b/contrib/llvm-project/compiler-rt/lib/scudo/standalone/mem_map_fuchsia.cpp new file mode 100644 index 000000000000..9ace1fef7ad4 --- /dev/null +++ b/contrib/llvm-project/compiler-rt/lib/scudo/standalone/mem_map_fuchsia.cpp @@ -0,0 +1,252 @@ +//===-- mem_map_fuchsia.cpp -------------------------------------*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#include "mem_map_fuchsia.h" + +#include "atomic_helpers.h" +#include "common.h" +#include "string_utils.h" + +#if SCUDO_FUCHSIA + +#include <zircon/process.h> +#include <zircon/status.h> +#include <zircon/syscalls.h> + +namespace scudo { + +static void NORETURN dieOnError(zx_status_t Status, const char *FnName, + uptr Size) { + char Error[128]; + formatString(Error, sizeof(Error), + "SCUDO ERROR: %s failed with size %zuKB (%s)", FnName, + Size >> 10, _zx_status_get_string(Status)); + outputRaw(Error); + die(); +} + +static void setVmoName(zx_handle_t Vmo, const char *Name) { + size_t Len = strlen(Name); + DCHECK_LT(Len, ZX_MAX_NAME_LEN); + zx_status_t Status = _zx_object_set_property(Vmo, ZX_PROP_NAME, Name, Len); + CHECK_EQ(Status, ZX_OK); +} + +// Returns the (cached) base address of the root VMAR. +static uptr getRootVmarBase() { + static atomic_uptr CachedResult = {0}; + + uptr Result = atomic_load_relaxed(&CachedResult); + if (UNLIKELY(!Result)) { + zx_info_vmar_t VmarInfo; + zx_status_t Status = + _zx_object_get_info(_zx_vmar_root_self(), ZX_INFO_VMAR, &VmarInfo, + sizeof(VmarInfo), nullptr, nullptr); + CHECK_EQ(Status, ZX_OK); + CHECK_NE(VmarInfo.base, 0); + + atomic_store_relaxed(&CachedResult, VmarInfo.base); + Result = VmarInfo.base; + } + + return Result; +} + +// Lazily creates and then always returns the same zero-sized VMO. +static zx_handle_t getPlaceholderVmo() { + static atomic_u32 StoredVmo = {ZX_HANDLE_INVALID}; + + zx_handle_t Vmo = atomic_load_relaxed(&StoredVmo); + if (UNLIKELY(Vmo == ZX_HANDLE_INVALID)) { + // Create a zero-sized placeholder VMO. + zx_status_t Status = _zx_vmo_create(0, 0, &Vmo); + if (UNLIKELY(Status != ZX_OK)) + dieOnError(Status, "zx_vmo_create", 0); + + setVmoName(Vmo, "scudo:reserved"); + + // Atomically store its handle. If some other thread wins the race, use its + // handle and discard ours. + zx_handle_t OldValue = + atomic_compare_exchange(&StoredVmo, ZX_HANDLE_INVALID, Vmo); + if (OldValue != ZX_HANDLE_INVALID) { + Status = _zx_handle_close(Vmo); + CHECK_EQ(Status, ZX_OK); + + Vmo = OldValue; + } + } + + return Vmo; +} + +MemMapFuchsia::MemMapFuchsia(uptr Base, uptr Capacity) + : MapAddr(Base), WindowBase(Base), WindowSize(Capacity) { + // Create the VMO. + zx_status_t Status = _zx_vmo_create(Capacity, 0, &Vmo); + if (UNLIKELY(Status != ZX_OK)) + dieOnError(Status, "zx_vmo_create", Capacity); +} + +bool MemMapFuchsia::mapImpl(UNUSED uptr Addr, uptr Size, const char *Name, + uptr Flags) { + const bool AllowNoMem = !!(Flags & MAP_ALLOWNOMEM); + const bool PreCommit = !!(Flags & MAP_PRECOMMIT); + const bool NoAccess = !!(Flags & MAP_NOACCESS); + + // Create the VMO. + zx_status_t Status = _zx_vmo_create(Size, 0, &Vmo); + if (UNLIKELY(Status != ZX_OK)) { + if (Status != ZX_ERR_NO_MEMORY || !AllowNoMem) + dieOnError(Status, "zx_vmo_create", Size); + return false; + } + + if (Name != nullptr) + setVmoName(Vmo, Name); + + // Map it. + zx_vm_option_t MapFlags = ZX_VM_ALLOW_FAULTS; + if (!NoAccess) + MapFlags |= ZX_VM_PERM_READ | ZX_VM_PERM_WRITE; + Status = + _zx_vmar_map(_zx_vmar_root_self(), MapFlags, 0, Vmo, 0, Size, &MapAddr); + if (UNLIKELY(Status != ZX_OK)) { + if (Status != ZX_ERR_NO_MEMORY || !AllowNoMem) + dieOnError(Status, "zx_vmar_map", Size); + + Status = _zx_handle_close(Vmo); + CHECK_EQ(Status, ZX_OK); + + MapAddr = 0; + Vmo = ZX_HANDLE_INVALID; + return false; + } + + if (PreCommit) { + Status = _zx_vmar_op_range(_zx_vmar_root_self(), ZX_VMAR_OP_COMMIT, MapAddr, + Size, nullptr, 0); + CHECK_EQ(Status, ZX_OK); + } + + WindowBase = MapAddr; + WindowSize = Size; + return true; +} + +void MemMapFuchsia::unmapImpl(uptr Addr, uptr Size) { + zx_status_t Status; + + if (Size == WindowSize) { + // NOTE: Closing first and then unmapping seems slightly faster than doing + // the same operations in the opposite order. + Status = _zx_handle_close(Vmo); + CHECK_EQ(Status, ZX_OK); + Status = _zx_vmar_unmap(_zx_vmar_root_self(), Addr, Size); + CHECK_EQ(Status, ZX_OK); + + MapAddr = WindowBase = WindowSize = 0; + Vmo = ZX_HANDLE_INVALID; + } else { + // Unmap the subrange. + Status = _zx_vmar_unmap(_zx_vmar_root_self(), Addr, Size); + CHECK_EQ(Status, ZX_OK); + + // Decommit the pages that we just unmapped. + Status = _zx_vmo_op_range(Vmo, ZX_VMO_OP_DECOMMIT, Addr - MapAddr, Size, + nullptr, 0); + CHECK_EQ(Status, ZX_OK); + + if (Addr == WindowBase) + WindowBase += Size; + WindowSize -= Size; + } +} + +bool MemMapFuchsia::remapImpl(uptr Addr, uptr Size, const char *Name, + uptr Flags) { + const bool AllowNoMem = !!(Flags & MAP_ALLOWNOMEM); + const bool PreCommit = !!(Flags & MAP_PRECOMMIT); + const bool NoAccess = !!(Flags & MAP_NOACCESS); + + // NOTE: This will rename the *whole* VMO, not only the requested portion of + // it. But we cannot do better than this given the MemMap API. In practice, + // the upper layers of Scudo always pass the same Name for a given MemMap. + if (Name != nullptr) + setVmoName(Vmo, Name); + + uptr MappedAddr; + zx_vm_option_t MapFlags = ZX_VM_ALLOW_FAULTS | ZX_VM_SPECIFIC_OVERWRITE; + if (!NoAccess) + MapFlags |= ZX_VM_PERM_READ | ZX_VM_PERM_WRITE; + zx_status_t Status = + _zx_vmar_map(_zx_vmar_root_self(), MapFlags, Addr - getRootVmarBase(), + Vmo, Addr - MapAddr, Size, &MappedAddr); + if (UNLIKELY(Status != ZX_OK)) { + if (Status != ZX_ERR_NO_MEMORY || !AllowNoMem) + dieOnError(Status, "zx_vmar_map", Size); + return false; + } + DCHECK_EQ(Addr, MappedAddr); + + if (PreCommit) { + Status = _zx_vmar_op_range(_zx_vmar_root_self(), ZX_VMAR_OP_COMMIT, MapAddr, + Size, nullptr, 0); + CHECK_EQ(Status, ZX_OK); + } + + return true; +} + +void MemMapFuchsia::releaseAndZeroPagesToOSImpl(uptr From, uptr Size) { + zx_status_t Status = _zx_vmo_op_range(Vmo, ZX_VMO_OP_DECOMMIT, From - MapAddr, + Size, nullptr, 0); + CHECK_EQ(Status, ZX_OK); +} + +void MemMapFuchsia::setMemoryPermissionImpl(uptr Addr, uptr Size, uptr Flags) { + const bool NoAccess = !!(Flags & MAP_NOACCESS); + + zx_vm_option_t MapFlags = 0; + if (!NoAccess) + MapFlags |= ZX_VM_PERM_READ | ZX_VM_PERM_WRITE; + zx_status_t Status = + _zx_vmar_protect(_zx_vmar_root_self(), MapFlags, Addr, Size); + CHECK_EQ(Status, ZX_OK); +} + +bool ReservedMemoryFuchsia::createImpl(UNUSED uptr Addr, uptr Size, + UNUSED const char *Name, uptr Flags) { + const bool AllowNoMem = !!(Flags & MAP_ALLOWNOMEM); + + // Reserve memory by mapping the placeholder VMO without any permission. + zx_status_t Status = _zx_vmar_map(_zx_vmar_root_self(), ZX_VM_ALLOW_FAULTS, 0, + getPlaceholderVmo(), 0, Size, &Base); + if (UNLIKELY(Status != ZX_OK)) { + if (Status != ZX_ERR_NO_MEMORY || !AllowNoMem) + dieOnError(Status, "zx_vmar_map", Size); + return false; + } + + Capacity = Size; + return true; +} + +void ReservedMemoryFuchsia::releaseImpl() { + zx_status_t Status = _zx_vmar_unmap(_zx_vmar_root_self(), Base, Capacity); + CHECK_EQ(Status, ZX_OK); +} + +ReservedMemoryFuchsia::MemMapT ReservedMemoryFuchsia::dispatchImpl(uptr Addr, + uptr Size) { + return ReservedMemoryFuchsia::MemMapT(Addr, Size); +} + +} // namespace scudo + +#endif // SCUDO_FUCHSIA diff --git a/contrib/llvm-project/compiler-rt/lib/scudo/standalone/mem_map_fuchsia.h b/contrib/llvm-project/compiler-rt/lib/scudo/standalone/mem_map_fuchsia.h new file mode 100644 index 000000000000..2e66f89cfca5 --- /dev/null +++ b/contrib/llvm-project/compiler-rt/lib/scudo/standalone/mem_map_fuchsia.h @@ -0,0 +1,75 @@ +//===-- mem_map_fuchsia.h ---------------------------------------*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#ifndef SCUDO_MEM_MAP_FUCHSIA_H_ +#define SCUDO_MEM_MAP_FUCHSIA_H_ + +#include "mem_map_base.h" + +#if SCUDO_FUCHSIA + +#include <stdint.h> +#include <zircon/types.h> + +namespace scudo { + +class MemMapFuchsia final : public MemMapBase<MemMapFuchsia> { +public: + constexpr MemMapFuchsia() = default; + + // Impls for base functions. + bool mapImpl(uptr Addr, uptr Size, const char *Name, uptr Flags); + void unmapImpl(uptr Addr, uptr Size); + bool remapImpl(uptr Addr, uptr Size, const char *Name, uptr Flags); + void setMemoryPermissionImpl(uptr Addr, uptr Size, uptr Flags); + void releasePagesToOSImpl(uptr From, uptr Size) { + return releaseAndZeroPagesToOSImpl(From, Size); + } + void releaseAndZeroPagesToOSImpl(uptr From, uptr Size); + uptr getBaseImpl() { return WindowBase; } + uptr getCapacityImpl() { return WindowSize; } + +private: + friend class ReservedMemoryFuchsia; + + // Used by ReservedMemoryFuchsia::dispatch. + MemMapFuchsia(uptr Base, uptr Capacity); + + // Virtual memory address corresponding to VMO offset 0. + uptr MapAddr = 0; + + // Virtual memory base address and size of the VMO subrange that is still in + // use. unmapImpl() can shrink this range, either at the beginning or at the + // end. + uptr WindowBase = 0; + uptr WindowSize = 0; + + zx_handle_t Vmo = ZX_HANDLE_INVALID; +}; + +class ReservedMemoryFuchsia final + : public ReservedMemory<ReservedMemoryFuchsia, MemMapFuchsia> { +public: + constexpr ReservedMemoryFuchsia() = default; + + bool createImpl(uptr Addr, uptr Size, const char *Name, uptr Flags); + void releaseImpl(); + MemMapT dispatchImpl(uptr Addr, uptr Size); + uptr getBaseImpl() { return Base; } + uptr getCapacityImpl() { return Capacity; } + +private: + uptr Base = 0; + uptr Capacity = 0; +}; + +} // namespace scudo + +#endif // SCUDO_FUCHSIA + +#endif // SCUDO_MEM_MAP_FUCHSIA_H_ diff --git a/contrib/llvm-project/compiler-rt/lib/scudo/standalone/memtag.h b/contrib/llvm-project/compiler-rt/lib/scudo/standalone/memtag.h index 7f14a30fee12..aaed2192ad75 100644 --- a/contrib/llvm-project/compiler-rt/lib/scudo/standalone/memtag.h +++ b/contrib/llvm-project/compiler-rt/lib/scudo/standalone/memtag.h @@ -11,7 +11,7 @@ #include "internal_defs.h" -#if SCUDO_LINUX +#if SCUDO_CAN_USE_MTE #include <sys/auxv.h> #include <sys/prctl.h> #endif @@ -25,7 +25,7 @@ namespace scudo { // tagging. Not all operating systems enable TBI, so we only claim architectural // support for memory tagging if the operating system enables TBI. // HWASan uses the top byte for its own purpose and Scudo should not touch it. -#if SCUDO_LINUX && !defined(SCUDO_DISABLE_TBI) && \ +#if SCUDO_CAN_USE_MTE && !defined(SCUDO_DISABLE_TBI) && \ !__has_feature(hwaddress_sanitizer) inline constexpr bool archSupportsMemoryTagging() { return true; } #else @@ -60,7 +60,7 @@ inline NORETURN uint8_t extractTag(uptr Ptr) { #if __clang_major__ >= 12 && defined(__aarch64__) && !defined(__ILP32__) -#if SCUDO_LINUX +#if SCUDO_CAN_USE_MTE inline bool systemSupportsMemoryTagging() { #ifndef HWCAP2_MTE @@ -106,7 +106,7 @@ inline void enableSystemMemoryTaggingTestOnly() { 0, 0, 0); } -#else // !SCUDO_LINUX +#else // !SCUDO_CAN_USE_MTE inline bool systemSupportsMemoryTagging() { return false; } @@ -118,7 +118,7 @@ inline NORETURN void enableSystemMemoryTaggingTestOnly() { UNREACHABLE("memory tagging not supported"); } -#endif // SCUDO_LINUX +#endif // SCUDO_CAN_USE_MTE class ScopedDisableMemoryTagChecks { uptr PrevTCO; diff --git a/contrib/llvm-project/compiler-rt/lib/scudo/standalone/mutex.h b/contrib/llvm-project/compiler-rt/lib/scudo/standalone/mutex.h index c8504c040914..05340de3e12d 100644 --- a/contrib/llvm-project/compiler-rt/lib/scudo/standalone/mutex.h +++ b/contrib/llvm-project/compiler-rt/lib/scudo/standalone/mutex.h @@ -11,6 +11,7 @@ #include "atomic_helpers.h" #include "common.h" +#include "thread_annotations.h" #include <string.h> @@ -20,10 +21,10 @@ namespace scudo { -class HybridMutex { +class CAPABILITY("mutex") HybridMutex { public: - bool tryLock(); - NOINLINE void lock() { + bool tryLock() TRY_ACQUIRE(true); + NOINLINE void lock() ACQUIRE() { if (LIKELY(tryLock())) return; // The compiler may try to fully unroll the loop, ending up in a @@ -40,9 +41,20 @@ public: } lockSlow(); } - void unlock(); + void unlock() RELEASE(); + + // TODO(chiahungduan): In general, we may want to assert the owner of lock as + // well. Given the current uses of HybridMutex, it's acceptable without + // asserting the owner. Re-evaluate this when we have certain scenarios which + // requires a more fine-grained lock granularity. + ALWAYS_INLINE void assertHeld() ASSERT_CAPABILITY(this) { + if (SCUDO_DEBUG) + assertHeldImpl(); + } private: + void assertHeldImpl(); + static constexpr u8 NumberOfTries = 8U; static constexpr u8 NumberOfYields = 8U; @@ -52,13 +64,13 @@ private: sync_mutex_t M = {}; #endif - void lockSlow(); + void lockSlow() ACQUIRE(); }; -class ScopedLock { +class SCOPED_CAPABILITY ScopedLock { public: - explicit ScopedLock(HybridMutex &M) : Mutex(M) { Mutex.lock(); } - ~ScopedLock() { Mutex.unlock(); } + explicit ScopedLock(HybridMutex &M) ACQUIRE(M) : Mutex(M) { Mutex.lock(); } + ~ScopedLock() RELEASE() { Mutex.unlock(); } private: HybridMutex &Mutex; diff --git a/contrib/llvm-project/compiler-rt/lib/scudo/standalone/platform.h b/contrib/llvm-project/compiler-rt/lib/scudo/standalone/platform.h index db4217ddab9f..7c7024ff570e 100644 --- a/contrib/llvm-project/compiler-rt/lib/scudo/standalone/platform.h +++ b/contrib/llvm-project/compiler-rt/lib/scudo/standalone/platform.h @@ -37,6 +37,12 @@ #define SCUDO_TRUSTY 0 #endif +#if defined(__riscv) && (__riscv_xlen == 64) +#define SCUDO_RISCV64 1 +#else +#define SCUDO_RISCV64 0 +#endif + #if defined(__LP64__) #define SCUDO_WORDSIZE 64U #else @@ -53,6 +59,10 @@ #define SCUDO_CAN_USE_PRIMARY64 (SCUDO_WORDSIZE == 64U) #endif +#ifndef SCUDO_CAN_USE_MTE +#define SCUDO_CAN_USE_MTE (SCUDO_LINUX || SCUDO_TRUSTY) +#endif + #ifndef SCUDO_MIN_ALIGNMENT_LOG // We force malloc-type functions to be aligned to std::max_align_t, but there // is no reason why the minimum alignment for all other functions can't be 8 diff --git a/contrib/llvm-project/compiler-rt/lib/scudo/standalone/primary32.h b/contrib/llvm-project/compiler-rt/lib/scudo/standalone/primary32.h index a3d908cee9e5..1d8a34ec65d6 100644 --- a/contrib/llvm-project/compiler-rt/lib/scudo/standalone/primary32.h +++ b/contrib/llvm-project/compiler-rt/lib/scudo/standalone/primary32.h @@ -18,6 +18,7 @@ #include "report.h" #include "stats.h" #include "string_utils.h" +#include "thread_annotations.h" namespace scudo { @@ -41,13 +42,14 @@ namespace scudo { template <typename Config> class SizeClassAllocator32 { public: - typedef typename Config::PrimaryCompactPtrT CompactPtrT; - typedef typename Config::SizeClassMap SizeClassMap; - static const uptr GroupSizeLog = Config::PrimaryGroupSizeLog; + typedef typename Config::Primary::CompactPtrT CompactPtrT; + typedef typename Config::Primary::SizeClassMap SizeClassMap; + static const uptr GroupSizeLog = Config::Primary::GroupSizeLog; // The bytemap can only track UINT8_MAX - 1 classes. static_assert(SizeClassMap::LargestClassId <= (UINT8_MAX - 1), ""); // Regions should be large enough to hold the largest Block. - static_assert((1UL << Config::PrimaryRegionSizeLog) >= SizeClassMap::MaxSize, + static_assert((1UL << Config::Primary::RegionSizeLog) >= + SizeClassMap::MaxSize, ""); typedef SizeClassAllocator32<Config> ThisT; typedef SizeClassAllocatorLocalCache<ThisT> CacheT; @@ -62,7 +64,7 @@ public: static bool canAllocate(uptr Size) { return Size <= SizeClassMap::MaxSize; } - void init(s32 ReleaseToOsInterval) { + void init(s32 ReleaseToOsInterval) NO_THREAD_SAFETY_ANALYSIS { if (SCUDO_FUCHSIA) reportError("SizeClassAllocator32 is not supported on Fuchsia"); @@ -72,7 +74,7 @@ public: DCHECK(isAligned(reinterpret_cast<uptr>(this), alignof(ThisT))); PossibleRegions.init(); u32 Seed; - const u64 Time = getMonotonicTime(); + const u64 Time = getMonotonicTimeFast(); if (!getRandom(reinterpret_cast<void *>(&Seed), sizeof(Seed))) Seed = static_cast<u32>( Time ^ (reinterpret_cast<uptr>(SizeClassInfoArray) >> 6)); @@ -87,24 +89,77 @@ public: } void unmapTestOnly() { - while (NumberOfStashedRegions > 0) - unmap(reinterpret_cast<void *>(RegionsStash[--NumberOfStashedRegions]), - RegionSize); + { + ScopedLock L(RegionsStashMutex); + while (NumberOfStashedRegions > 0) { + unmap(reinterpret_cast<void *>(RegionsStash[--NumberOfStashedRegions]), + RegionSize); + } + } + uptr MinRegionIndex = NumRegions, MaxRegionIndex = 0; for (uptr I = 0; I < NumClasses; I++) { SizeClassInfo *Sci = getSizeClassInfo(I); + ScopedLock L(Sci->Mutex); if (Sci->MinRegionIndex < MinRegionIndex) MinRegionIndex = Sci->MinRegionIndex; if (Sci->MaxRegionIndex > MaxRegionIndex) MaxRegionIndex = Sci->MaxRegionIndex; *Sci = {}; } - for (uptr I = MinRegionIndex; I < MaxRegionIndex; I++) + + ScopedLock L(ByteMapMutex); + for (uptr I = MinRegionIndex; I <= MaxRegionIndex; I++) if (PossibleRegions[I]) unmap(reinterpret_cast<void *>(I * RegionSize), RegionSize); PossibleRegions.unmapTestOnly(); } + // When all blocks are freed, it has to be the same size as `AllocatedUser`. + void verifyAllBlocksAreReleasedTestOnly() { + // `BatchGroup` and `TransferBatch` also use the blocks from BatchClass. + uptr BatchClassUsedInFreeLists = 0; + for (uptr I = 0; I < NumClasses; I++) { + // We have to count BatchClassUsedInFreeLists in other regions first. + if (I == SizeClassMap::BatchClassId) + continue; + SizeClassInfo *Sci = getSizeClassInfo(I); + ScopedLock L1(Sci->Mutex); + uptr TotalBlocks = 0; + for (BatchGroup &BG : Sci->FreeListInfo.BlockList) { + // `BG::Batches` are `TransferBatches`. +1 for `BatchGroup`. + BatchClassUsedInFreeLists += BG.Batches.size() + 1; + for (const auto &It : BG.Batches) + TotalBlocks += It.getCount(); + } + + const uptr BlockSize = getSizeByClassId(I); + DCHECK_EQ(TotalBlocks, Sci->AllocatedUser / BlockSize); + DCHECK_EQ(Sci->FreeListInfo.PushedBlocks, Sci->FreeListInfo.PoppedBlocks); + } + + SizeClassInfo *Sci = getSizeClassInfo(SizeClassMap::BatchClassId); + ScopedLock L1(Sci->Mutex); + uptr TotalBlocks = 0; + for (BatchGroup &BG : Sci->FreeListInfo.BlockList) { + if (LIKELY(!BG.Batches.empty())) { + for (const auto &It : BG.Batches) + TotalBlocks += It.getCount(); + } else { + // `BatchGroup` with empty freelist doesn't have `TransferBatch` record + // itself. + ++TotalBlocks; + } + } + + const uptr BlockSize = getSizeByClassId(SizeClassMap::BatchClassId); + DCHECK_EQ(TotalBlocks + BatchClassUsedInFreeLists, + Sci->AllocatedUser / BlockSize); + const uptr BlocksInUse = + Sci->FreeListInfo.PoppedBlocks - Sci->FreeListInfo.PushedBlocks; + DCHECK_EQ(BlocksInUse, BatchClassUsedInFreeLists); + } + CompactPtrT compactPtr(UNUSED uptr ClassId, uptr Ptr) const { return static_cast<CompactPtrT>(Ptr); } @@ -113,23 +168,37 @@ public: return reinterpret_cast<void *>(static_cast<uptr>(CompactPtr)); } - uptr compactPtrGroup(CompactPtrT CompactPtr) { - return CompactPtr >> GroupSizeLog; + uptr compactPtrGroupBase(CompactPtrT CompactPtr) { + const uptr Mask = (static_cast<uptr>(1) << GroupSizeLog) - 1; + return CompactPtr & ~Mask; + } + + uptr decompactGroupBase(uptr CompactPtrGroupBase) { + return CompactPtrGroupBase; + } + + ALWAYS_INLINE static bool isSmallBlock(uptr BlockSize) { + const uptr PageSize = getPageSizeCached(); + return BlockSize < PageSize / 16U; + } + + ALWAYS_INLINE static bool isLargeBlock(uptr BlockSize) { + const uptr PageSize = getPageSizeCached(); + return BlockSize > PageSize; } TransferBatch *popBatch(CacheT *C, uptr ClassId) { DCHECK_LT(ClassId, NumClasses); SizeClassInfo *Sci = getSizeClassInfo(ClassId); ScopedLock L(Sci->Mutex); - TransferBatch *B = popBatchImpl(C, ClassId); + TransferBatch *B = popBatchImpl(C, ClassId, Sci); if (UNLIKELY(!B)) { if (UNLIKELY(!populateFreeList(C, ClassId, Sci))) return nullptr; - B = popBatchImpl(C, ClassId); + B = popBatchImpl(C, ClassId, Sci); // if `populateFreeList` succeeded, we are supposed to get free blocks. DCHECK_NE(B, nullptr); } - Sci->Stats.PoppedBlocks += B->getCount(); return B; } @@ -141,16 +210,7 @@ public: SizeClassInfo *Sci = getSizeClassInfo(ClassId); if (ClassId == SizeClassMap::BatchClassId) { ScopedLock L(Sci->Mutex); - // Constructing a batch group in the free list will use two blocks in - // BatchClassId. If we are pushing BatchClassId blocks, we will use the - // blocks in the array directly (can't delegate local cache which will - // cause a recursive allocation). However, The number of free blocks may - // be less than two. Therefore, populate the free list before inserting - // the blocks. - if (Size == 1 && !populateFreeList(C, ClassId, Sci)) - return; - pushBlocksImpl(C, ClassId, Array, Size); - Sci->Stats.PushedBlocks += Size; + pushBatchClassBlocks(Sci, Array, Size); return; } @@ -161,11 +221,12 @@ public: // together. bool SameGroup = true; for (u32 I = 1; I < Size; ++I) { - if (compactPtrGroup(Array[I - 1]) != compactPtrGroup(Array[I])) + if (compactPtrGroupBase(Array[I - 1]) != compactPtrGroupBase(Array[I])) SameGroup = false; CompactPtrT Cur = Array[I]; u32 J = I; - while (J > 0 && compactPtrGroup(Cur) < compactPtrGroup(Array[J - 1])) { + while (J > 0 && + compactPtrGroupBase(Cur) < compactPtrGroupBase(Array[J - 1])) { Array[J] = Array[J - 1]; --J; } @@ -173,14 +234,10 @@ public: } ScopedLock L(Sci->Mutex); - pushBlocksImpl(C, ClassId, Array, Size, SameGroup); - - Sci->Stats.PushedBlocks += Size; - if (ClassId != SizeClassMap::BatchClassId) - releaseToOSMaybe(Sci, ClassId); + pushBlocksImpl(C, ClassId, Sci, Array, Size, SameGroup); } - void disable() { + void disable() NO_THREAD_SAFETY_ANALYSIS { // The BatchClassId must be locked last since other classes can use it. for (sptr I = static_cast<sptr>(NumClasses) - 1; I >= 0; I--) { if (static_cast<uptr>(I) == SizeClassMap::BatchClassId) @@ -189,11 +246,11 @@ public: } getSizeClassInfo(SizeClassMap::BatchClassId)->Mutex.lock(); RegionsStashMutex.lock(); - PossibleRegions.disable(); + ByteMapMutex.lock(); } - void enable() { - PossibleRegions.enable(); + void enable() NO_THREAD_SAFETY_ANALYSIS { + ByteMapMutex.unlock(); RegionsStashMutex.unlock(); getSizeClassInfo(SizeClassMap::BatchClassId)->Mutex.unlock(); for (uptr I = 0; I < NumClasses; I++) { @@ -207,12 +264,20 @@ public: uptr MinRegionIndex = NumRegions, MaxRegionIndex = 0; for (uptr I = 0; I < NumClasses; I++) { SizeClassInfo *Sci = getSizeClassInfo(I); + // TODO: The call of `iterateOverBlocks` requires disabling + // SizeClassAllocator32. We may consider locking each region on demand + // only. + Sci->Mutex.assertHeld(); if (Sci->MinRegionIndex < MinRegionIndex) MinRegionIndex = Sci->MinRegionIndex; if (Sci->MaxRegionIndex > MaxRegionIndex) MaxRegionIndex = Sci->MaxRegionIndex; } - for (uptr I = MinRegionIndex; I <= MaxRegionIndex; I++) + + // SizeClassAllocator32 is disabled, i.e., ByteMapMutex is held. + ByteMapMutex.assertHeld(); + + for (uptr I = MinRegionIndex; I <= MaxRegionIndex; I++) { if (PossibleRegions[I] && (PossibleRegions[I] - 1U) != SizeClassMap::BatchClassId) { const uptr BlockSize = getSizeByClassId(PossibleRegions[I] - 1U); @@ -221,6 +286,7 @@ public: for (uptr Block = From; Block < To; Block += BlockSize) Callback(Block); } + } } void getStats(ScopedString *Str) { @@ -230,22 +296,26 @@ public: uptr PushedBlocks = 0; for (uptr I = 0; I < NumClasses; I++) { SizeClassInfo *Sci = getSizeClassInfo(I); + ScopedLock L(Sci->Mutex); TotalMapped += Sci->AllocatedUser; - PoppedBlocks += Sci->Stats.PoppedBlocks; - PushedBlocks += Sci->Stats.PushedBlocks; + PoppedBlocks += Sci->FreeListInfo.PoppedBlocks; + PushedBlocks += Sci->FreeListInfo.PushedBlocks; } Str->append("Stats: SizeClassAllocator32: %zuM mapped in %zu allocations; " "remains %zu\n", TotalMapped >> 20, PoppedBlocks, PoppedBlocks - PushedBlocks); - for (uptr I = 0; I < NumClasses; I++) - getStats(Str, I, 0); + for (uptr I = 0; I < NumClasses; I++) { + SizeClassInfo *Sci = getSizeClassInfo(I); + ScopedLock L(Sci->Mutex); + getStats(Str, I, Sci); + } } bool setOption(Option O, sptr Value) { if (O == Option::ReleaseInterval) { - const s32 Interval = Max( - Min(static_cast<s32>(Value), Config::PrimaryMaxReleaseToOsIntervalMs), - Config::PrimaryMinReleaseToOsIntervalMs); + const s32 Interval = Max(Min(static_cast<s32>(Value), + Config::Primary::MaxReleaseToOsIntervalMs), + Config::Primary::MinReleaseToOsIntervalMs); atomic_store_relaxed(&ReleaseToOsIntervalMs, Interval); return true; } @@ -253,14 +323,22 @@ public: return true; } - uptr releaseToOS() { + uptr tryReleaseToOS(uptr ClassId, ReleaseToOS ReleaseType) { + SizeClassInfo *Sci = getSizeClassInfo(ClassId); + // TODO: Once we have separate locks like primary64, we may consider using + // tryLock() as well. + ScopedLock L(Sci->Mutex); + return releaseToOSMaybe(Sci, ClassId, ReleaseType); + } + + uptr releaseToOS(ReleaseToOS ReleaseType) { uptr TotalReleasedBytes = 0; for (uptr I = 0; I < NumClasses; I++) { if (I == SizeClassMap::BatchClassId) continue; SizeClassInfo *Sci = getSizeClassInfo(I); ScopedLock L(Sci->Mutex); - TotalReleasedBytes += releaseToOSMaybe(Sci, I, /*Force=*/true); + TotalReleasedBytes += releaseToOSMaybe(Sci, I, ReleaseType); } return TotalReleasedBytes; } @@ -277,42 +355,42 @@ public: private: static const uptr NumClasses = SizeClassMap::NumClasses; - static const uptr RegionSize = 1UL << Config::PrimaryRegionSizeLog; + static const uptr RegionSize = 1UL << Config::Primary::RegionSizeLog; static const uptr NumRegions = - SCUDO_MMAP_RANGE_SIZE >> Config::PrimaryRegionSizeLog; + SCUDO_MMAP_RANGE_SIZE >> Config::Primary::RegionSizeLog; static const u32 MaxNumBatches = SCUDO_ANDROID ? 4U : 8U; typedef FlatByteMap<NumRegions> ByteMap; - struct SizeClassStats { - uptr PoppedBlocks; - uptr PushedBlocks; - }; - struct ReleaseToOsInfo { - uptr PushedBlocksAtLastRelease; + uptr BytesInFreeListAtLastCheckpoint; uptr RangesReleased; uptr LastReleasedBytes; u64 LastReleaseAtNs; }; + struct BlocksInfo { + SinglyLinkedList<BatchGroup> BlockList = {}; + uptr PoppedBlocks = 0; + uptr PushedBlocks = 0; + }; + struct alignas(SCUDO_CACHE_LINE_SIZE) SizeClassInfo { HybridMutex Mutex; - SinglyLinkedList<BatchGroup> FreeList; - uptr CurrentRegion; - uptr CurrentRegionAllocated; - SizeClassStats Stats; + BlocksInfo FreeListInfo GUARDED_BY(Mutex); + uptr CurrentRegion GUARDED_BY(Mutex); + uptr CurrentRegionAllocated GUARDED_BY(Mutex); u32 RandState; - uptr AllocatedUser; + uptr AllocatedUser GUARDED_BY(Mutex); // Lowest & highest region index allocated for this size class, to avoid // looping through the whole NumRegions. - uptr MinRegionIndex; - uptr MaxRegionIndex; - ReleaseToOsInfo ReleaseInfo; + uptr MinRegionIndex GUARDED_BY(Mutex); + uptr MaxRegionIndex GUARDED_BY(Mutex); + ReleaseToOsInfo ReleaseInfo GUARDED_BY(Mutex); }; static_assert(sizeof(SizeClassInfo) % SCUDO_CACHE_LINE_SIZE == 0, ""); uptr computeRegionId(uptr Mem) { - const uptr Id = Mem >> Config::PrimaryRegionSizeLog; + const uptr Id = Mem >> Config::Primary::RegionSizeLog; CHECK_LT(Id, NumRegions); return Id; } @@ -332,17 +410,22 @@ private: else MapSize = RegionSize; } else { - Region = roundUpTo(MapBase, RegionSize); + Region = roundUp(MapBase, RegionSize); unmap(reinterpret_cast<void *>(MapBase), Region - MapBase); MapSize = RegionSize; } const uptr End = Region + MapSize; if (End != MapEnd) unmap(reinterpret_cast<void *>(End), MapEnd - End); + + DCHECK_EQ(Region % RegionSize, 0U); + static_assert(Config::Primary::RegionSizeLog == GroupSizeLog, + "Memory group should be the same size as Region"); + return Region; } - uptr allocateRegion(SizeClassInfo *Sci, uptr ClassId) { + uptr allocateRegion(SizeClassInfo *Sci, uptr ClassId) REQUIRES(Sci->Mutex) { DCHECK_LT(ClassId, NumClasses); uptr Region = 0; { @@ -359,6 +442,7 @@ private: Sci->MinRegionIndex = RegionIndex; if (RegionIndex > Sci->MaxRegionIndex) Sci->MaxRegionIndex = RegionIndex; + ScopedLock L(ByteMapMutex); PossibleRegions.set(RegionIndex, static_cast<u8>(ClassId + 1U)); } return Region; @@ -369,15 +453,125 @@ private: return &SizeClassInfoArray[ClassId]; } + void pushBatchClassBlocks(SizeClassInfo *Sci, CompactPtrT *Array, u32 Size) + REQUIRES(Sci->Mutex) { + DCHECK_EQ(Sci, getSizeClassInfo(SizeClassMap::BatchClassId)); + + // Free blocks are recorded by TransferBatch in freelist for all + // size-classes. In addition, TransferBatch is allocated from BatchClassId. + // In order not to use additional block to record the free blocks in + // BatchClassId, they are self-contained. I.e., A TransferBatch records the + // block address of itself. See the figure below: + // + // TransferBatch at 0xABCD + // +----------------------------+ + // | Free blocks' addr | + // | +------+------+------+ | + // | |0xABCD|... |... | | + // | +------+------+------+ | + // +----------------------------+ + // + // When we allocate all the free blocks in the TransferBatch, the block used + // by TransferBatch is also free for use. We don't need to recycle the + // TransferBatch. Note that the correctness is maintained by the invariant, + // + // The unit of each popBatch() request is entire TransferBatch. Return + // part of the blocks in a TransferBatch is invalid. + // + // This ensures that TransferBatch won't leak the address itself while it's + // still holding other valid data. + // + // Besides, BatchGroup is also allocated from BatchClassId and has its + // address recorded in the TransferBatch too. To maintain the correctness, + // + // The address of BatchGroup is always recorded in the last TransferBatch + // in the freelist (also imply that the freelist should only be + // updated with push_front). Once the last TransferBatch is popped, + // the block used by BatchGroup is also free for use. + // + // With this approach, the blocks used by BatchGroup and TransferBatch are + // reusable and don't need additional space for them. + + Sci->FreeListInfo.PushedBlocks += Size; + BatchGroup *BG = Sci->FreeListInfo.BlockList.front(); + + if (BG == nullptr) { + // Construct `BatchGroup` on the last element. + BG = reinterpret_cast<BatchGroup *>( + decompactPtr(SizeClassMap::BatchClassId, Array[Size - 1])); + --Size; + BG->Batches.clear(); + // BatchClass hasn't enabled memory group. Use `0` to indicate there's no + // memory group here. + BG->CompactPtrGroupBase = 0; + // `BG` is also the block of BatchClassId. Note that this is different + // from `CreateGroup` in `pushBlocksImpl` + BG->PushedBlocks = 1; + BG->BytesInBGAtLastCheckpoint = 0; + BG->MaxCachedPerBatch = TransferBatch::getMaxCached( + getSizeByClassId(SizeClassMap::BatchClassId)); + + Sci->FreeListInfo.BlockList.push_front(BG); + } + + if (UNLIKELY(Size == 0)) + return; + + // This happens under 2 cases. + // 1. just allocated a new `BatchGroup`. + // 2. Only 1 block is pushed when the freelist is empty. + if (BG->Batches.empty()) { + // Construct the `TransferBatch` on the last element. + TransferBatch *TB = reinterpret_cast<TransferBatch *>( + decompactPtr(SizeClassMap::BatchClassId, Array[Size - 1])); + TB->clear(); + // As mentioned above, addresses of `TransferBatch` and `BatchGroup` are + // recorded in the TransferBatch. + TB->add(Array[Size - 1]); + TB->add( + compactPtr(SizeClassMap::BatchClassId, reinterpret_cast<uptr>(BG))); + --Size; + DCHECK_EQ(BG->PushedBlocks, 1U); + // `TB` is also the block of BatchClassId. + BG->PushedBlocks += 1; + BG->Batches.push_front(TB); + } + + TransferBatch *CurBatch = BG->Batches.front(); + DCHECK_NE(CurBatch, nullptr); + + for (u32 I = 0; I < Size;) { + u16 UnusedSlots = + static_cast<u16>(BG->MaxCachedPerBatch - CurBatch->getCount()); + if (UnusedSlots == 0) { + CurBatch = reinterpret_cast<TransferBatch *>( + decompactPtr(SizeClassMap::BatchClassId, Array[I])); + CurBatch->clear(); + // Self-contained + CurBatch->add(Array[I]); + ++I; + // TODO(chiahungduan): Avoid the use of push_back() in `Batches` of + // BatchClassId. + BG->Batches.push_front(CurBatch); + UnusedSlots = static_cast<u16>(BG->MaxCachedPerBatch - 1); + } + // `UnusedSlots` is u16 so the result will be also fit in u16. + const u16 AppendSize = static_cast<u16>(Min<u32>(UnusedSlots, Size - I)); + CurBatch->appendFromArray(&Array[I], AppendSize); + I += AppendSize; + } + + BG->PushedBlocks += Size; + } // Push the blocks to their batch group. The layout will be like, // - // FreeList - > BG -> BG -> BG - // | | | - // v v v - // TB TB TB - // | - // v - // TB + // FreeListInfo.BlockList - > BG -> BG -> BG + // | | | + // v v v + // TB TB TB + // | + // v + // TB // // Each BlockGroup(BG) will associate with unique group id and the free blocks // are managed by a list of TransferBatch(TB). To reduce the time of inserting @@ -386,44 +580,23 @@ private: // Use `SameGroup=true` to indicate that all blocks in the array are from the // same group then we will skip checking the group id of each block. // - // Note that this aims to have a better management of dirty pages, i.e., the - // RSS usage won't grow indefinitely. There's an exception that we may not put - // a block to its associated group. While populating new blocks, we may have - // blocks cross different groups. However, most cases will fall into same - // group and they are supposed to be popped soon. In that case, it's not worth - // sorting the array with the almost-sorted property. Therefore, we use - // `SameGroup=true` instead. - // // The region mutex needs to be held while calling this method. - void pushBlocksImpl(CacheT *C, uptr ClassId, CompactPtrT *Array, u32 Size, - bool SameGroup = false) { + void pushBlocksImpl(CacheT *C, uptr ClassId, SizeClassInfo *Sci, + CompactPtrT *Array, u32 Size, bool SameGroup = false) + REQUIRES(Sci->Mutex) { + DCHECK_NE(ClassId, SizeClassMap::BatchClassId); DCHECK_GT(Size, 0U); - SizeClassInfo *Sci = getSizeClassInfo(ClassId); - auto CreateGroup = [&](uptr GroupId) { - BatchGroup *BG = nullptr; - TransferBatch *TB = nullptr; - if (ClassId == SizeClassMap::BatchClassId) { - DCHECK_GE(Size, 2U); - BG = reinterpret_cast<BatchGroup *>( - decompactPtr(ClassId, Array[Size - 1])); - BG->Batches.clear(); - - TB = reinterpret_cast<TransferBatch *>( - decompactPtr(ClassId, Array[Size - 2])); - TB->clear(); - } else { - BG = C->createGroup(); - BG->Batches.clear(); + auto CreateGroup = [&](uptr CompactPtrGroupBase) { + BatchGroup *BG = C->createGroup(); + BG->Batches.clear(); + TransferBatch *TB = C->createBatch(ClassId, nullptr); + TB->clear(); - TB = C->createBatch(ClassId, nullptr); - TB->clear(); - } - - BG->GroupId = GroupId; + BG->CompactPtrGroupBase = CompactPtrGroupBase; BG->Batches.push_front(TB); BG->PushedBlocks = 0; - BG->PushedBlocksAtLastCheckpoint = 0; + BG->BytesInBGAtLastCheckpoint = 0; BG->MaxCachedPerBatch = TransferBatch::getMaxCached(getSizeByClassId(ClassId)); @@ -456,38 +629,34 @@ private: BG->PushedBlocks += Size; }; - BatchGroup *Cur = Sci->FreeList.front(); - - if (ClassId == SizeClassMap::BatchClassId) { - if (Cur == nullptr) { - // Don't need to classify BatchClassId. - Cur = CreateGroup(/*GroupId=*/0); - Sci->FreeList.push_front(Cur); - } - InsertBlocks(Cur, Array, Size); - return; - } + Sci->FreeListInfo.PushedBlocks += Size; + BatchGroup *Cur = Sci->FreeListInfo.BlockList.front(); // In the following, `Cur` always points to the BatchGroup for blocks that // will be pushed next. `Prev` is the element right before `Cur`. BatchGroup *Prev = nullptr; - while (Cur != nullptr && compactPtrGroup(Array[0]) > Cur->GroupId) { + while (Cur != nullptr && + compactPtrGroupBase(Array[0]) > Cur->CompactPtrGroupBase) { Prev = Cur; Cur = Cur->Next; } - if (Cur == nullptr || compactPtrGroup(Array[0]) != Cur->GroupId) { - Cur = CreateGroup(compactPtrGroup(Array[0])); + if (Cur == nullptr || + compactPtrGroupBase(Array[0]) != Cur->CompactPtrGroupBase) { + Cur = CreateGroup(compactPtrGroupBase(Array[0])); if (Prev == nullptr) - Sci->FreeList.push_front(Cur); + Sci->FreeListInfo.BlockList.push_front(Cur); else - Sci->FreeList.insert(Prev, Cur); + Sci->FreeListInfo.BlockList.insert(Prev, Cur); } // All the blocks are from the same group, just push without checking group // id. if (SameGroup) { + for (u32 I = 0; I < Size; ++I) + DCHECK_EQ(compactPtrGroupBase(Array[I]), Cur->CompactPtrGroupBase); + InsertBlocks(Cur, Array, Size); return; } @@ -496,19 +665,21 @@ private: // push them to their group together. u32 Count = 1; for (u32 I = 1; I < Size; ++I) { - if (compactPtrGroup(Array[I - 1]) != compactPtrGroup(Array[I])) { - DCHECK_EQ(compactPtrGroup(Array[I - 1]), Cur->GroupId); + if (compactPtrGroupBase(Array[I - 1]) != compactPtrGroupBase(Array[I])) { + DCHECK_EQ(compactPtrGroupBase(Array[I - 1]), Cur->CompactPtrGroupBase); InsertBlocks(Cur, Array + I - Count, Count); - while (Cur != nullptr && compactPtrGroup(Array[I]) > Cur->GroupId) { + while (Cur != nullptr && + compactPtrGroupBase(Array[I]) > Cur->CompactPtrGroupBase) { Prev = Cur; Cur = Cur->Next; } - if (Cur == nullptr || compactPtrGroup(Array[I]) != Cur->GroupId) { - Cur = CreateGroup(compactPtrGroup(Array[I])); + if (Cur == nullptr || + compactPtrGroupBase(Array[I]) != Cur->CompactPtrGroupBase) { + Cur = CreateGroup(compactPtrGroupBase(Array[I])); DCHECK_NE(Prev, nullptr); - Sci->FreeList.insert(Prev, Cur); + Sci->FreeListInfo.BlockList.insert(Prev, Cur); } Count = 1; @@ -524,13 +695,28 @@ private: // group id will be considered first. // // The region mutex needs to be held while calling this method. - TransferBatch *popBatchImpl(CacheT *C, uptr ClassId) { - SizeClassInfo *Sci = getSizeClassInfo(ClassId); - if (Sci->FreeList.empty()) + TransferBatch *popBatchImpl(CacheT *C, uptr ClassId, SizeClassInfo *Sci) + REQUIRES(Sci->Mutex) { + if (Sci->FreeListInfo.BlockList.empty()) return nullptr; - SinglyLinkedList<TransferBatch> &Batches = Sci->FreeList.front()->Batches; - DCHECK(!Batches.empty()); + SinglyLinkedList<TransferBatch> &Batches = + Sci->FreeListInfo.BlockList.front()->Batches; + + if (Batches.empty()) { + DCHECK_EQ(ClassId, SizeClassMap::BatchClassId); + BatchGroup *BG = Sci->FreeListInfo.BlockList.front(); + Sci->FreeListInfo.BlockList.pop_front(); + + // Block used by `BatchGroup` is from BatchClassId. Turn the block into + // `TransferBatch` with single block. + TransferBatch *TB = reinterpret_cast<TransferBatch *>(BG); + TB->clear(); + TB->add( + compactPtr(SizeClassMap::BatchClassId, reinterpret_cast<uptr>(TB))); + Sci->FreeListInfo.PoppedBlocks += 1; + return TB; + } TransferBatch *B = Batches.front(); Batches.pop_front(); @@ -538,8 +724,8 @@ private: DCHECK_GT(B->getCount(), 0U); if (Batches.empty()) { - BatchGroup *BG = Sci->FreeList.front(); - Sci->FreeList.pop_front(); + BatchGroup *BG = Sci->FreeListInfo.BlockList.front(); + Sci->FreeListInfo.BlockList.pop_front(); // We don't keep BatchGroup with zero blocks to avoid empty-checking while // allocating. Note that block used by constructing BatchGroup is recorded @@ -550,10 +736,12 @@ private: C->deallocate(SizeClassMap::BatchClassId, BG); } + Sci->FreeListInfo.PoppedBlocks += B->getCount(); return B; } - NOINLINE bool populateFreeList(CacheT *C, uptr ClassId, SizeClassInfo *Sci) { + NOINLINE bool populateFreeList(CacheT *C, uptr ClassId, SizeClassInfo *Sci) + REQUIRES(Sci->Mutex) { uptr Region; uptr Offset; // If the size-class currently has a region associated to it, use it. The @@ -598,20 +786,35 @@ private: uptr P = Region + Offset; for (u32 I = 0; I < NumberOfBlocks; I++, P += Size) ShuffleArray[I] = reinterpret_cast<CompactPtrT>(P); - // No need to shuffle the batches size class. - if (ClassId != SizeClassMap::BatchClassId) - shuffle(ShuffleArray, NumberOfBlocks, &Sci->RandState); - for (u32 I = 0; I < NumberOfBlocks;) { - // `MaxCount` is u16 so the result will also fit in u16. - const u16 N = static_cast<u16>(Min<u32>(MaxCount, NumberOfBlocks - I)); - // Note that the N blocks here may have different group ids. Given that - // it only happens when it crosses the group size boundary. Instead of - // sorting them, treat them as same group here to avoid sorting the - // almost-sorted blocks. - pushBlocksImpl(C, ClassId, &ShuffleArray[I], N, /*SameGroup=*/true); - I += N; + + if (ClassId != SizeClassMap::BatchClassId) { + u32 N = 1; + uptr CurGroup = compactPtrGroupBase(ShuffleArray[0]); + for (u32 I = 1; I < NumberOfBlocks; I++) { + if (UNLIKELY(compactPtrGroupBase(ShuffleArray[I]) != CurGroup)) { + shuffle(ShuffleArray + I - N, N, &Sci->RandState); + pushBlocksImpl(C, ClassId, Sci, ShuffleArray + I - N, N, + /*SameGroup=*/true); + N = 1; + CurGroup = compactPtrGroupBase(ShuffleArray[I]); + } else { + ++N; + } + } + + shuffle(ShuffleArray + NumberOfBlocks - N, N, &Sci->RandState); + pushBlocksImpl(C, ClassId, Sci, &ShuffleArray[NumberOfBlocks - N], N, + /*SameGroup=*/true); + } else { + pushBatchClassBlocks(Sci, ShuffleArray, NumberOfBlocks); } + // Note that `PushedBlocks` and `PoppedBlocks` are supposed to only record + // the requests from `PushBlocks` and `PopBatch` which are external + // interfaces. `populateFreeList` is the internal interface so we should set + // the values back to avoid incorrectly setting the stats. + Sci->FreeListInfo.PushedBlocks -= NumberOfBlocks; + const uptr AllocatedUser = Size * NumberOfBlocks; C->getStats().add(StatFree, AllocatedUser); DCHECK_LE(Sci->CurrentRegionAllocated + AllocatedUser, RegionSize); @@ -629,55 +832,98 @@ private: return true; } - void getStats(ScopedString *Str, uptr ClassId, uptr Rss) { - SizeClassInfo *Sci = getSizeClassInfo(ClassId); + void getStats(ScopedString *Str, uptr ClassId, SizeClassInfo *Sci) + REQUIRES(Sci->Mutex) { if (Sci->AllocatedUser == 0) return; - const uptr InUse = Sci->Stats.PoppedBlocks - Sci->Stats.PushedBlocks; - const uptr AvailableChunks = Sci->AllocatedUser / getSizeByClassId(ClassId); + const uptr BlockSize = getSizeByClassId(ClassId); + const uptr InUse = + Sci->FreeListInfo.PoppedBlocks - Sci->FreeListInfo.PushedBlocks; + const uptr BytesInFreeList = Sci->AllocatedUser - InUse * BlockSize; + uptr PushedBytesDelta = 0; + if (BytesInFreeList >= Sci->ReleaseInfo.BytesInFreeListAtLastCheckpoint) { + PushedBytesDelta = + BytesInFreeList - Sci->ReleaseInfo.BytesInFreeListAtLastCheckpoint; + } + const uptr AvailableChunks = Sci->AllocatedUser / BlockSize; Str->append(" %02zu (%6zu): mapped: %6zuK popped: %7zu pushed: %7zu " - "inuse: %6zu avail: %6zu rss: %6zuK releases: %6zu\n", + "inuse: %6zu avail: %6zu releases: %6zu last released: %6zuK " + "latest pushed bytes: %6zuK\n", ClassId, getSizeByClassId(ClassId), Sci->AllocatedUser >> 10, - Sci->Stats.PoppedBlocks, Sci->Stats.PushedBlocks, InUse, - AvailableChunks, Rss >> 10, Sci->ReleaseInfo.RangesReleased); + Sci->FreeListInfo.PoppedBlocks, Sci->FreeListInfo.PushedBlocks, + InUse, AvailableChunks, Sci->ReleaseInfo.RangesReleased, + Sci->ReleaseInfo.LastReleasedBytes >> 10, + PushedBytesDelta >> 10); } NOINLINE uptr releaseToOSMaybe(SizeClassInfo *Sci, uptr ClassId, - bool Force = false) { + ReleaseToOS ReleaseType = ReleaseToOS::Normal) + REQUIRES(Sci->Mutex) { const uptr BlockSize = getSizeByClassId(ClassId); const uptr PageSize = getPageSizeCached(); - DCHECK_GE(Sci->Stats.PoppedBlocks, Sci->Stats.PushedBlocks); + DCHECK_GE(Sci->FreeListInfo.PoppedBlocks, Sci->FreeListInfo.PushedBlocks); const uptr BytesInFreeList = Sci->AllocatedUser - - (Sci->Stats.PoppedBlocks - Sci->Stats.PushedBlocks) * BlockSize; - if (BytesInFreeList < PageSize) - return 0; // No chance to release anything. - const uptr BytesPushed = - (Sci->Stats.PushedBlocks - Sci->ReleaseInfo.PushedBlocksAtLastRelease) * - BlockSize; - if (BytesPushed < PageSize) - return 0; // Nothing new to release. - - const bool CheckDensity = BlockSize < PageSize / 16U; + (Sci->FreeListInfo.PoppedBlocks - Sci->FreeListInfo.PushedBlocks) * + BlockSize; + + if (UNLIKELY(BytesInFreeList == 0)) + return 0; + + if (BytesInFreeList <= Sci->ReleaseInfo.BytesInFreeListAtLastCheckpoint) + Sci->ReleaseInfo.BytesInFreeListAtLastCheckpoint = BytesInFreeList; + + // Always update `BytesInFreeListAtLastCheckpoint` with the smallest value + // so that we won't underestimate the releasable pages. For example, the + // following is the region usage, + // + // BytesInFreeListAtLastCheckpoint AllocatedUser + // v v + // |---------------------------------------> + // ^ ^ + // BytesInFreeList ReleaseThreshold + // + // In general, if we have collected enough bytes and the amount of free + // bytes meets the ReleaseThreshold, we will try to do page release. If we + // don't update `BytesInFreeListAtLastCheckpoint` when the current + // `BytesInFreeList` is smaller, we may take longer time to wait for enough + // freed blocks because we miss the bytes between + // (BytesInFreeListAtLastCheckpoint - BytesInFreeList). + const uptr PushedBytesDelta = + BytesInFreeList - Sci->ReleaseInfo.BytesInFreeListAtLastCheckpoint; + if (PushedBytesDelta < PageSize && ReleaseType != ReleaseToOS::ForceAll) + return 0; + + const bool CheckDensity = + isSmallBlock(BlockSize) && ReleaseType != ReleaseToOS::ForceAll; // Releasing smaller blocks is expensive, so we want to make sure that a // significant amount of bytes are free, and that there has been a good // amount of batches pushed to the freelist before attempting to release. - if (CheckDensity) { - if (!Force && BytesPushed < Sci->AllocatedUser / 16U) + if (CheckDensity && ReleaseType == ReleaseToOS::Normal) + if (PushedBytesDelta < Sci->AllocatedUser / 16U) return 0; - } - if (!Force) { + if (ReleaseType == ReleaseToOS::Normal) { const s32 IntervalMs = atomic_load_relaxed(&ReleaseToOsIntervalMs); if (IntervalMs < 0) return 0; - if (Sci->ReleaseInfo.LastReleaseAtNs + - static_cast<u64>(IntervalMs) * 1000000 > - getMonotonicTime()) { - return 0; // Memory was returned recently. + + // The constant 8 here is selected from profiling some apps and the number + // of unreleased pages in the large size classes is around 16 pages or + // more. Choose half of it as a heuristic and which also avoids page + // release every time for every pushBlocks() attempt by large blocks. + const bool ByPassReleaseInterval = + isLargeBlock(BlockSize) && PushedBytesDelta > 8 * PageSize; + if (!ByPassReleaseInterval) { + if (Sci->ReleaseInfo.LastReleaseAtNs + + static_cast<u64>(IntervalMs) * 1000000 > + getMonotonicTimeFast()) { + // Memory was returned recently. + return 0; + } } - } + } // if (ReleaseType == ReleaseToOS::Normal) const uptr First = Sci->MinRegionIndex; const uptr Last = Sci->MaxRegionIndex; @@ -687,24 +933,24 @@ private: const uptr Base = First * RegionSize; const uptr NumberOfRegions = Last - First + 1U; const uptr GroupSize = (1U << GroupSizeLog); - const uptr CurRegionGroupId = - compactPtrGroup(compactPtr(ClassId, Sci->CurrentRegion)); + const uptr CurGroupBase = + compactPtrGroupBase(compactPtr(ClassId, Sci->CurrentRegion)); ReleaseRecorder Recorder(Base); - PageReleaseContext Context(BlockSize, RegionSize, NumberOfRegions); + PageReleaseContext Context(BlockSize, NumberOfRegions, + /*ReleaseSize=*/RegionSize); auto DecompactPtr = [](CompactPtrT CompactPtr) { return reinterpret_cast<uptr>(CompactPtr); }; - for (BatchGroup &BG : Sci->FreeList) { - const uptr PushedBytesDelta = - BG.PushedBlocks - BG.PushedBlocksAtLastCheckpoint; - if (PushedBytesDelta * BlockSize < PageSize) - continue; - - uptr AllocatedGroupSize = BG.GroupId == CurRegionGroupId + for (BatchGroup &BG : Sci->FreeListInfo.BlockList) { + const uptr GroupBase = decompactGroupBase(BG.CompactPtrGroupBase); + // The `GroupSize` may not be divided by `BlockSize`, which means there is + // an unused space at the end of Region. Exclude that space to avoid + // unused page map entry. + uptr AllocatedGroupSize = GroupBase == CurGroupBase ? Sci->CurrentRegionAllocated - : GroupSize; + : roundDownSlow(GroupSize, BlockSize); if (AllocatedGroupSize == 0) continue; @@ -713,6 +959,16 @@ private: const uptr NumBlocks = (BG.Batches.size() - 1) * BG.MaxCachedPerBatch + BG.Batches.front()->getCount(); const uptr BytesInBG = NumBlocks * BlockSize; + + if (ReleaseType != ReleaseToOS::ForceAll && + BytesInBG <= BG.BytesInBGAtLastCheckpoint) { + BG.BytesInBGAtLastCheckpoint = BytesInBG; + continue; + } + const uptr PushedBytesDelta = BytesInBG - BG.BytesInBGAtLastCheckpoint; + if (ReleaseType != ReleaseToOS::ForceAll && PushedBytesDelta < PageSize) + continue; + // Given the randomness property, we try to release the pages only if the // bytes used by free blocks exceed certain proportion of allocated // spaces. @@ -721,42 +977,70 @@ private: continue; } - BG.PushedBlocksAtLastCheckpoint = BG.PushedBlocks; - // Note that we don't always visit blocks in each BatchGroup so that we - // may miss the chance of releasing certain pages that cross BatchGroups. - Context.markFreeBlocks(BG.Batches, DecompactPtr, Base); + // TODO: Consider updating this after page release if `ReleaseRecorder` + // can tell the releasd bytes in each group. + BG.BytesInBGAtLastCheckpoint = BytesInBG; + + const uptr MaxContainedBlocks = AllocatedGroupSize / BlockSize; + const uptr RegionIndex = (GroupBase - Base) / RegionSize; + + if (NumBlocks == MaxContainedBlocks) { + for (const auto &It : BG.Batches) + for (u16 I = 0; I < It.getCount(); ++I) + DCHECK_EQ(compactPtrGroupBase(It.get(I)), BG.CompactPtrGroupBase); + + const uptr To = GroupBase + AllocatedGroupSize; + Context.markRangeAsAllCounted(GroupBase, To, GroupBase, RegionIndex, + AllocatedGroupSize); + } else { + DCHECK_LT(NumBlocks, MaxContainedBlocks); + + // Note that we don't always visit blocks in each BatchGroup so that we + // may miss the chance of releasing certain pages that cross + // BatchGroups. + Context.markFreeBlocksInRegion(BG.Batches, DecompactPtr, GroupBase, + RegionIndex, AllocatedGroupSize, + /*MayContainLastBlockInRegion=*/true); + } + + // We may not be able to do the page release In a rare case that we may + // fail on PageMap allocation. + if (UNLIKELY(!Context.hasBlockMarked())) + return 0; } if (!Context.hasBlockMarked()) return 0; auto SkipRegion = [this, First, ClassId](uptr RegionIndex) { + ScopedLock L(ByteMapMutex); return (PossibleRegions[First + RegionIndex] - 1U) != ClassId; }; releaseFreeMemoryToOS(Context, Recorder, SkipRegion); if (Recorder.getReleasedRangesCount() > 0) { - Sci->ReleaseInfo.PushedBlocksAtLastRelease = Sci->Stats.PushedBlocks; + Sci->ReleaseInfo.BytesInFreeListAtLastCheckpoint = BytesInFreeList; Sci->ReleaseInfo.RangesReleased += Recorder.getReleasedRangesCount(); Sci->ReleaseInfo.LastReleasedBytes = Recorder.getReleasedBytes(); TotalReleasedBytes += Sci->ReleaseInfo.LastReleasedBytes; } - Sci->ReleaseInfo.LastReleaseAtNs = getMonotonicTime(); + Sci->ReleaseInfo.LastReleaseAtNs = getMonotonicTimeFast(); return TotalReleasedBytes; } SizeClassInfo SizeClassInfoArray[NumClasses] = {}; + HybridMutex ByteMapMutex; // Track the regions in use, 0 is unused, otherwise store ClassId + 1. - ByteMap PossibleRegions = {}; + ByteMap PossibleRegions GUARDED_BY(ByteMapMutex) = {}; atomic_s32 ReleaseToOsIntervalMs = {}; // Unless several threads request regions simultaneously from different size // classes, the stash rarely contains more than 1 entry. static constexpr uptr MaxStashedRegions = 4; HybridMutex RegionsStashMutex; - uptr NumberOfStashedRegions = 0; - uptr RegionsStash[MaxStashedRegions] = {}; + uptr NumberOfStashedRegions GUARDED_BY(RegionsStashMutex) = 0; + uptr RegionsStash[MaxStashedRegions] GUARDED_BY(RegionsStashMutex) = {}; }; } // namespace scudo diff --git a/contrib/llvm-project/compiler-rt/lib/scudo/standalone/primary64.h b/contrib/llvm-project/compiler-rt/lib/scudo/standalone/primary64.h index b653bc802022..fd7a1f9e80cd 100644 --- a/contrib/llvm-project/compiler-rt/lib/scudo/standalone/primary64.h +++ b/contrib/llvm-project/compiler-rt/lib/scudo/standalone/primary64.h @@ -13,11 +13,13 @@ #include "common.h" #include "list.h" #include "local_cache.h" +#include "mem_map.h" #include "memtag.h" #include "options.h" #include "release.h" #include "stats.h" #include "string_utils.h" +#include "thread_annotations.h" namespace scudo { @@ -43,10 +45,11 @@ namespace scudo { template <typename Config> class SizeClassAllocator64 { public: - typedef typename Config::PrimaryCompactPtrT CompactPtrT; - static const uptr CompactPtrScale = Config::PrimaryCompactPtrScale; - static const uptr GroupSizeLog = Config::PrimaryGroupSizeLog; - typedef typename Config::SizeClassMap SizeClassMap; + typedef typename Config::Primary::CompactPtrT CompactPtrT; + typedef typename Config::Primary::SizeClassMap SizeClassMap; + static const uptr CompactPtrScale = Config::Primary::CompactPtrScale; + static const uptr GroupSizeLog = Config::Primary::GroupSizeLog; + static const uptr GroupScale = GroupSizeLog - CompactPtrScale; typedef SizeClassAllocator64<Config> ThisT; typedef SizeClassAllocatorLocalCache<ThisT> CacheT; typedef typename CacheT::TransferBatch TransferBatch; @@ -54,62 +57,202 @@ public: static uptr getSizeByClassId(uptr ClassId) { return (ClassId == SizeClassMap::BatchClassId) - ? roundUpTo(sizeof(TransferBatch), 1U << CompactPtrScale) + ? roundUp(sizeof(TransferBatch), 1U << CompactPtrScale) : SizeClassMap::getSizeByClassId(ClassId); } static bool canAllocate(uptr Size) { return Size <= SizeClassMap::MaxSize; } - void init(s32 ReleaseToOsInterval) { + void init(s32 ReleaseToOsInterval) NO_THREAD_SAFETY_ANALYSIS { DCHECK(isAligned(reinterpret_cast<uptr>(this), alignof(ThisT))); - DCHECK_EQ(PrimaryBase, 0U); + + const uptr PageSize = getPageSizeCached(); + const uptr GroupSize = (1U << GroupSizeLog); + const uptr PagesInGroup = GroupSize / PageSize; + const uptr MinSizeClass = getSizeByClassId(1); + // When trying to release pages back to memory, visiting smaller size + // classes is expensive. Therefore, we only try to release smaller size + // classes when the amount of free blocks goes over a certain threshold (See + // the comment in releaseToOSMaybe() for more details). For example, for + // size class 32, we only do the release when the size of free blocks is + // greater than 97% of pages in a group. However, this may introduce another + // issue that if the number of free blocks is bouncing between 97% ~ 100%. + // Which means we may try many page releases but only release very few of + // them (less than 3% in a group). Even though we have + // `&ReleaseToOsIntervalMs` which slightly reduce the frequency of these + // calls but it will be better to have another guard to mitigate this issue. + // + // Here we add another constraint on the minimum size requirement. The + // constraint is determined by the size of in-use blocks in the minimal size + // class. Take size class 32 as an example, + // + // +- one memory group -+ + // +----------------------+------+ + // | 97% of free blocks | | + // +----------------------+------+ + // \ / + // 3% in-use blocks + // + // * The release size threshold is 97%. + // + // The 3% size in a group is about 7 pages. For two consecutive + // releaseToOSMaybe(), we require the difference between `PushedBlocks` + // should be greater than 7 pages. This mitigates the page releasing + // thrashing which is caused by memory usage bouncing around the threshold. + // The smallest size class takes longest time to do the page release so we + // use its size of in-use blocks as a heuristic. + SmallerBlockReleasePageDelta = + PagesInGroup * (1 + MinSizeClass / 16U) / 100; + // Reserve the space required for the Primary. - PrimaryBase = reinterpret_cast<uptr>( - map(nullptr, PrimarySize, nullptr, MAP_NOACCESS, &Data)); + CHECK(ReservedMemory.create(/*Addr=*/0U, PrimarySize, + "scudo:primary_reserve")); + PrimaryBase = ReservedMemory.getBase(); + DCHECK_NE(PrimaryBase, 0U); u32 Seed; - const u64 Time = getMonotonicTime(); + const u64 Time = getMonotonicTimeFast(); if (!getRandom(reinterpret_cast<void *>(&Seed), sizeof(Seed))) Seed = static_cast<u32>(Time ^ (PrimaryBase >> 12)); - const uptr PageSize = getPageSizeCached(); + for (uptr I = 0; I < NumClasses; I++) { RegionInfo *Region = getRegionInfo(I); // The actual start of a region is offset by a random number of pages // when PrimaryEnableRandomOffset is set. - Region->RegionBeg = getRegionBaseByClassId(I) + - (Config::PrimaryEnableRandomOffset - ? ((getRandomModN(&Seed, 16) + 1) * PageSize) - : 0); + Region->RegionBeg = + (PrimaryBase + (I << Config::Primary::RegionSizeLog)) + + (Config::Primary::EnableRandomOffset + ? ((getRandomModN(&Seed, 16) + 1) * PageSize) + : 0); Region->RandState = getRandomU32(&Seed); + // Releasing small blocks is expensive, set a higher threshold to avoid + // frequent page releases. + if (isSmallBlock(getSizeByClassId(I))) + Region->TryReleaseThreshold = PageSize * SmallerBlockReleasePageDelta; + else + Region->TryReleaseThreshold = PageSize; Region->ReleaseInfo.LastReleaseAtNs = Time; + + Region->MemMapInfo.MemMap = ReservedMemory.dispatch( + PrimaryBase + (I << Config::Primary::RegionSizeLog), RegionSize); + CHECK(Region->MemMapInfo.MemMap.isAllocated()); } + shuffle(RegionInfoArray, NumClasses, &Seed); + setOption(Option::ReleaseInterval, static_cast<sptr>(ReleaseToOsInterval)); } - void unmapTestOnly() { + void unmapTestOnly() NO_THREAD_SAFETY_ANALYSIS { for (uptr I = 0; I < NumClasses; I++) { RegionInfo *Region = getRegionInfo(I); *Region = {}; } if (PrimaryBase) - unmap(reinterpret_cast<void *>(PrimaryBase), PrimarySize, UNMAP_ALL, - &Data); + ReservedMemory.release(); PrimaryBase = 0U; } + // When all blocks are freed, it has to be the same size as `AllocatedUser`. + void verifyAllBlocksAreReleasedTestOnly() { + // `BatchGroup` and `TransferBatch` also use the blocks from BatchClass. + uptr BatchClassUsedInFreeLists = 0; + for (uptr I = 0; I < NumClasses; I++) { + // We have to count BatchClassUsedInFreeLists in other regions first. + if (I == SizeClassMap::BatchClassId) + continue; + RegionInfo *Region = getRegionInfo(I); + ScopedLock ML(Region->MMLock); + ScopedLock FL(Region->FLLock); + const uptr BlockSize = getSizeByClassId(I); + uptr TotalBlocks = 0; + for (BatchGroup &BG : Region->FreeListInfo.BlockList) { + // `BG::Batches` are `TransferBatches`. +1 for `BatchGroup`. + BatchClassUsedInFreeLists += BG.Batches.size() + 1; + for (const auto &It : BG.Batches) + TotalBlocks += It.getCount(); + } + + DCHECK_EQ(TotalBlocks, Region->MemMapInfo.AllocatedUser / BlockSize); + DCHECK_EQ(Region->FreeListInfo.PushedBlocks, + Region->FreeListInfo.PoppedBlocks); + } + + RegionInfo *Region = getRegionInfo(SizeClassMap::BatchClassId); + ScopedLock ML(Region->MMLock); + ScopedLock FL(Region->FLLock); + const uptr BlockSize = getSizeByClassId(SizeClassMap::BatchClassId); + uptr TotalBlocks = 0; + for (BatchGroup &BG : Region->FreeListInfo.BlockList) { + if (LIKELY(!BG.Batches.empty())) { + for (const auto &It : BG.Batches) + TotalBlocks += It.getCount(); + } else { + // `BatchGroup` with empty freelist doesn't have `TransferBatch` record + // itself. + ++TotalBlocks; + } + } + DCHECK_EQ(TotalBlocks + BatchClassUsedInFreeLists, + Region->MemMapInfo.AllocatedUser / BlockSize); + DCHECK_GE(Region->FreeListInfo.PoppedBlocks, + Region->FreeListInfo.PushedBlocks); + const uptr BlocksInUse = + Region->FreeListInfo.PoppedBlocks - Region->FreeListInfo.PushedBlocks; + DCHECK_EQ(BlocksInUse, BatchClassUsedInFreeLists); + } + TransferBatch *popBatch(CacheT *C, uptr ClassId) { DCHECK_LT(ClassId, NumClasses); RegionInfo *Region = getRegionInfo(ClassId); - ScopedLock L(Region->Mutex); - TransferBatch *B = popBatchImpl(C, ClassId); - if (UNLIKELY(!B)) { - if (UNLIKELY(!populateFreeList(C, ClassId, Region))) - return nullptr; - B = popBatchImpl(C, ClassId); - // if `populateFreeList` succeeded, we are supposed to get free blocks. - DCHECK_NE(B, nullptr); + + { + ScopedLock L(Region->FLLock); + TransferBatch *B = popBatchImpl(C, ClassId, Region); + if (LIKELY(B)) + return B; } - Region->Stats.PoppedBlocks += B->getCount(); + + bool PrintStats = false; + TransferBatch *B = nullptr; + + while (true) { + // When two threads compete for `Region->MMLock`, we only want one of them + // does the populateFreeListAndPopBatch(). To avoid both of them doing + // that, always check the freelist before mapping new pages. + // + // TODO(chiahungduan): Use a condition variable so that we don't need to + // hold `Region->MMLock` here. + ScopedLock ML(Region->MMLock); + { + ScopedLock FL(Region->FLLock); + B = popBatchImpl(C, ClassId, Region); + if (LIKELY(B)) + return B; + } + + const bool RegionIsExhausted = Region->Exhausted; + if (!RegionIsExhausted) + B = populateFreeListAndPopBatch(C, ClassId, Region); + PrintStats = !RegionIsExhausted && Region->Exhausted; + break; + } + + // Note that `getStats()` requires locking each region so we can't call it + // while locking the Region->Mutex in the above. + if (UNLIKELY(PrintStats)) { + ScopedString Str; + getStats(&Str); + Str.append( + "Scudo OOM: The process has exhausted %zuM for size class %zu.\n", + RegionSize >> 20, getSizeByClassId(ClassId)); + Str.output(); + + // Theoretically, BatchClass shouldn't be used up. Abort immediately when + // it happens. + if (ClassId == SizeClassMap::BatchClassId) + reportOutOfBatchClass(); + } + return B; } @@ -120,17 +263,8 @@ public: RegionInfo *Region = getRegionInfo(ClassId); if (ClassId == SizeClassMap::BatchClassId) { - ScopedLock L(Region->Mutex); - // Constructing a batch group in the free list will use two blocks in - // BatchClassId. If we are pushing BatchClassId blocks, we will use the - // blocks in the array directly (can't delegate local cache which will - // cause a recursive allocation). However, The number of free blocks may - // be less than two. Therefore, populate the free list before inserting - // the blocks. - if (Size == 1 && UNLIKELY(!populateFreeList(C, ClassId, Region))) - return; - pushBlocksImpl(C, ClassId, Array, Size); - Region->Stats.PushedBlocks += Size; + ScopedLock L(Region->FLLock); + pushBatchClassBlocks(Region, Array, Size); return; } @@ -152,30 +286,32 @@ public: Array[J] = Cur; } - ScopedLock L(Region->Mutex); - pushBlocksImpl(C, ClassId, Array, Size, SameGroup); - - Region->Stats.PushedBlocks += Size; - if (ClassId != SizeClassMap::BatchClassId) - releaseToOSMaybe(Region, ClassId); + { + ScopedLock L(Region->FLLock); + pushBlocksImpl(C, ClassId, Region, Array, Size, SameGroup); + } } - void disable() { + void disable() NO_THREAD_SAFETY_ANALYSIS { // The BatchClassId must be locked last since other classes can use it. for (sptr I = static_cast<sptr>(NumClasses) - 1; I >= 0; I--) { if (static_cast<uptr>(I) == SizeClassMap::BatchClassId) continue; - getRegionInfo(static_cast<uptr>(I))->Mutex.lock(); + getRegionInfo(static_cast<uptr>(I))->MMLock.lock(); + getRegionInfo(static_cast<uptr>(I))->FLLock.lock(); } - getRegionInfo(SizeClassMap::BatchClassId)->Mutex.lock(); + getRegionInfo(SizeClassMap::BatchClassId)->MMLock.lock(); + getRegionInfo(SizeClassMap::BatchClassId)->FLLock.lock(); } - void enable() { - getRegionInfo(SizeClassMap::BatchClassId)->Mutex.unlock(); + void enable() NO_THREAD_SAFETY_ANALYSIS { + getRegionInfo(SizeClassMap::BatchClassId)->FLLock.unlock(); + getRegionInfo(SizeClassMap::BatchClassId)->MMLock.unlock(); for (uptr I = 0; I < NumClasses; I++) { if (I == SizeClassMap::BatchClassId) continue; - getRegionInfo(I)->Mutex.unlock(); + getRegionInfo(I)->FLLock.unlock(); + getRegionInfo(I)->MMLock.unlock(); } } @@ -183,10 +319,15 @@ public: for (uptr I = 0; I < NumClasses; I++) { if (I == SizeClassMap::BatchClassId) continue; - const RegionInfo *Region = getRegionInfo(I); + RegionInfo *Region = getRegionInfo(I); + // TODO: The call of `iterateOverBlocks` requires disabling + // SizeClassAllocator64. We may consider locking each region on demand + // only. + Region->FLLock.assertHeld(); + Region->MMLock.assertHeld(); const uptr BlockSize = getSizeByClassId(I); const uptr From = Region->RegionBeg; - const uptr To = From + Region->AllocatedUser; + const uptr To = From + Region->MemMapInfo.AllocatedUser; for (uptr Block = From; Block < To; Block += BlockSize) Callback(Block); } @@ -199,25 +340,34 @@ public: uptr PushedBlocks = 0; for (uptr I = 0; I < NumClasses; I++) { RegionInfo *Region = getRegionInfo(I); - if (Region->MappedUser) - TotalMapped += Region->MappedUser; - PoppedBlocks += Region->Stats.PoppedBlocks; - PushedBlocks += Region->Stats.PushedBlocks; + { + ScopedLock L(Region->MMLock); + TotalMapped += Region->MemMapInfo.MappedUser; + } + { + ScopedLock L(Region->FLLock); + PoppedBlocks += Region->FreeListInfo.PoppedBlocks; + PushedBlocks += Region->FreeListInfo.PushedBlocks; + } } Str->append("Stats: SizeClassAllocator64: %zuM mapped (%uM rss) in %zu " "allocations; remains %zu\n", TotalMapped >> 20, 0U, PoppedBlocks, PoppedBlocks - PushedBlocks); - for (uptr I = 0; I < NumClasses; I++) - getStats(Str, I, 0); + for (uptr I = 0; I < NumClasses; I++) { + RegionInfo *Region = getRegionInfo(I); + ScopedLock L1(Region->MMLock); + ScopedLock L2(Region->FLLock); + getStats(Str, I, Region); + } } bool setOption(Option O, sptr Value) { if (O == Option::ReleaseInterval) { - const s32 Interval = Max( - Min(static_cast<s32>(Value), Config::PrimaryMaxReleaseToOsIntervalMs), - Config::PrimaryMinReleaseToOsIntervalMs); + const s32 Interval = Max(Min(static_cast<s32>(Value), + Config::Primary::MaxReleaseToOsIntervalMs), + Config::Primary::MinReleaseToOsIntervalMs); atomic_store_relaxed(&ReleaseToOsIntervalMs, Interval); return true; } @@ -225,14 +375,27 @@ public: return true; } - uptr releaseToOS() { + uptr tryReleaseToOS(uptr ClassId, ReleaseToOS ReleaseType) { + RegionInfo *Region = getRegionInfo(ClassId); + // Note that the tryLock() may fail spuriously, given that it should rarely + // happen and page releasing is fine to skip, we don't take certain + // approaches to ensure one page release is done. + if (Region->MMLock.tryLock()) { + uptr BytesReleased = releaseToOSMaybe(Region, ClassId, ReleaseType); + Region->MMLock.unlock(); + return BytesReleased; + } + return 0; + } + + uptr releaseToOS(ReleaseToOS ReleaseType) { uptr TotalReleasedBytes = 0; for (uptr I = 0; I < NumClasses; I++) { if (I == SizeClassMap::BatchClassId) continue; RegionInfo *Region = getRegionInfo(I); - ScopedLock L(Region->Mutex); - TotalReleasedBytes += releaseToOSMaybe(Region, I, /*Force=*/true); + ScopedLock L(Region->MMLock); + TotalReleasedBytes += releaseToOSMaybe(Region, I, ReleaseType); } return TotalReleasedBytes; } @@ -244,9 +407,6 @@ public: static uptr getRegionInfoArraySize() { return sizeof(RegionInfoArray); } uptr getCompactPtrBaseByClassId(uptr ClassId) { - // If we are not compacting pointers, base everything off of 0. - if (sizeof(CompactPtrT) == sizeof(uptr) && CompactPtrScale == 0) - return 0; return getRegionInfo(ClassId)->RegionBeg; } @@ -261,16 +421,24 @@ public: decompactPtrInternal(getCompactPtrBaseByClassId(ClassId), CompactPtr)); } - static BlockInfo findNearestBlock(const char *RegionInfoData, uptr Ptr) { + static BlockInfo findNearestBlock(const char *RegionInfoData, + uptr Ptr) NO_THREAD_SAFETY_ANALYSIS { const RegionInfo *RegionInfoArray = reinterpret_cast<const RegionInfo *>(RegionInfoData); + uptr ClassId; uptr MinDistance = -1UL; for (uptr I = 0; I != NumClasses; ++I) { if (I == SizeClassMap::BatchClassId) continue; uptr Begin = RegionInfoArray[I].RegionBeg; - uptr End = Begin + RegionInfoArray[I].AllocatedUser; + // TODO(chiahungduan): In fact, We need to lock the RegionInfo::MMLock. + // However, the RegionInfoData is passed with const qualifier and lock the + // mutex requires modifying RegionInfoData, which means we need to remove + // the const qualifier. This may lead to another undefined behavior (The + // first one is accessing `AllocatedUser` without locking. It's better to + // pass `RegionInfoData` as `void *` then we can lock the mutex properly. + uptr End = Begin + RegionInfoArray[I].MemMapInfo.AllocatedUser; if (Begin > End || End - Begin < SizeClassMap::getSizeByClassId(I)) continue; uptr RegionDistance; @@ -292,7 +460,8 @@ public: BlockInfo B = {}; if (MinDistance <= 8192) { B.RegionBegin = RegionInfoArray[ClassId].RegionBeg; - B.RegionEnd = B.RegionBegin + RegionInfoArray[ClassId].AllocatedUser; + B.RegionEnd = + B.RegionBegin + RegionInfoArray[ClassId].MemMapInfo.AllocatedUser; B.BlockSize = SizeClassMap::getSizeByClassId(ClassId); B.BlockBegin = B.RegionBegin + uptr(sptr(Ptr - B.RegionBegin) / sptr(B.BlockSize) * @@ -308,37 +477,49 @@ public: AtomicOptions Options; private: - static const uptr RegionSize = 1UL << Config::PrimaryRegionSizeLog; + static const uptr RegionSize = 1UL << Config::Primary::RegionSizeLog; static const uptr NumClasses = SizeClassMap::NumClasses; static const uptr PrimarySize = RegionSize * NumClasses; - static const uptr MapSizeIncrement = Config::PrimaryMapSizeIncrement; + static const uptr MapSizeIncrement = Config::Primary::MapSizeIncrement; // Fill at most this number of batches from the newly map'd memory. static const u32 MaxNumBatches = SCUDO_ANDROID ? 4U : 8U; - struct RegionStats { - uptr PoppedBlocks; - uptr PushedBlocks; - }; - struct ReleaseToOsInfo { - uptr PushedBlocksAtLastRelease; + uptr BytesInFreeListAtLastCheckpoint; uptr RangesReleased; uptr LastReleasedBytes; u64 LastReleaseAtNs; }; + struct BlocksInfo { + SinglyLinkedList<BatchGroup> BlockList = {}; + uptr PoppedBlocks = 0; + uptr PushedBlocks = 0; + }; + + struct PagesInfo { + MemMapT MemMap = {}; + // Bytes mapped for user memory. + uptr MappedUser = 0; + // Bytes allocated for user memory. + uptr AllocatedUser = 0; + }; + struct UnpaddedRegionInfo { - HybridMutex Mutex; - SinglyLinkedList<BatchGroup> FreeList; + // Mutex for operations on freelist + HybridMutex FLLock; + // Mutex for memmap operations + HybridMutex MMLock ACQUIRED_BEFORE(FLLock); + // `RegionBeg` is initialized before thread creation and won't be changed. uptr RegionBeg = 0; - RegionStats Stats = {}; - u32 RandState = 0; - uptr MappedUser = 0; // Bytes mapped for user memory. - uptr AllocatedUser = 0; // Bytes allocated for user memory. - MapPlatformData Data = {}; - ReleaseToOsInfo ReleaseInfo = {}; - bool Exhausted = false; + u32 RandState GUARDED_BY(MMLock) = 0; + BlocksInfo FreeListInfo GUARDED_BY(FLLock); + PagesInfo MemMapInfo GUARDED_BY(MMLock); + // The minimum size of pushed blocks to trigger page release. + uptr TryReleaseThreshold GUARDED_BY(MMLock) = 0; + ReleaseToOsInfo ReleaseInfo GUARDED_BY(MMLock) = {}; + bool Exhausted GUARDED_BY(MMLock) = false; }; struct RegionInfo : UnpaddedRegionInfo { char Padding[SCUDO_CACHE_LINE_SIZE - @@ -346,18 +527,15 @@ private: }; static_assert(sizeof(RegionInfo) % SCUDO_CACHE_LINE_SIZE == 0, ""); - uptr PrimaryBase = 0; - MapPlatformData Data = {}; - atomic_s32 ReleaseToOsIntervalMs = {}; - alignas(SCUDO_CACHE_LINE_SIZE) RegionInfo RegionInfoArray[NumClasses]; - RegionInfo *getRegionInfo(uptr ClassId) { DCHECK_LT(ClassId, NumClasses); return &RegionInfoArray[ClassId]; } - uptr getRegionBaseByClassId(uptr ClassId) const { - return PrimaryBase + (ClassId << Config::PrimaryRegionSizeLog); + uptr getRegionBaseByClassId(uptr ClassId) { + return roundDown(getRegionInfo(ClassId)->RegionBeg - PrimaryBase, + RegionSize) + + PrimaryBase; } static CompactPtrT compactPtrInternal(uptr Base, uptr Ptr) { @@ -369,21 +547,144 @@ private: } static uptr compactPtrGroup(CompactPtrT CompactPtr) { - return static_cast<uptr>(CompactPtr) >> (GroupSizeLog - CompactPtrScale); + const uptr Mask = (static_cast<uptr>(1) << GroupScale) - 1; + return static_cast<uptr>(CompactPtr) & ~Mask; + } + static uptr decompactGroupBase(uptr Base, uptr CompactPtrGroupBase) { + DCHECK_EQ(CompactPtrGroupBase % (static_cast<uptr>(1) << (GroupScale)), 0U); + return Base + (CompactPtrGroupBase << CompactPtrScale); + } + + ALWAYS_INLINE static bool isSmallBlock(uptr BlockSize) { + const uptr PageSize = getPageSizeCached(); + return BlockSize < PageSize / 16U; } - static uptr batchGroupBase(uptr Base, uptr GroupId) { - return (GroupId << GroupSizeLog) + Base; + + ALWAYS_INLINE static bool isLargeBlock(uptr BlockSize) { + const uptr PageSize = getPageSizeCached(); + return BlockSize > PageSize; + } + + void pushBatchClassBlocks(RegionInfo *Region, CompactPtrT *Array, u32 Size) + REQUIRES(Region->FLLock) { + DCHECK_EQ(Region, getRegionInfo(SizeClassMap::BatchClassId)); + + // Free blocks are recorded by TransferBatch in freelist for all + // size-classes. In addition, TransferBatch is allocated from BatchClassId. + // In order not to use additional block to record the free blocks in + // BatchClassId, they are self-contained. I.e., A TransferBatch records the + // block address of itself. See the figure below: + // + // TransferBatch at 0xABCD + // +----------------------------+ + // | Free blocks' addr | + // | +------+------+------+ | + // | |0xABCD|... |... | | + // | +------+------+------+ | + // +----------------------------+ + // + // When we allocate all the free blocks in the TransferBatch, the block used + // by TransferBatch is also free for use. We don't need to recycle the + // TransferBatch. Note that the correctness is maintained by the invariant, + // + // The unit of each popBatch() request is entire TransferBatch. Return + // part of the blocks in a TransferBatch is invalid. + // + // This ensures that TransferBatch won't leak the address itself while it's + // still holding other valid data. + // + // Besides, BatchGroup is also allocated from BatchClassId and has its + // address recorded in the TransferBatch too. To maintain the correctness, + // + // The address of BatchGroup is always recorded in the last TransferBatch + // in the freelist (also imply that the freelist should only be + // updated with push_front). Once the last TransferBatch is popped, + // the block used by BatchGroup is also free for use. + // + // With this approach, the blocks used by BatchGroup and TransferBatch are + // reusable and don't need additional space for them. + + Region->FreeListInfo.PushedBlocks += Size; + BatchGroup *BG = Region->FreeListInfo.BlockList.front(); + + if (BG == nullptr) { + // Construct `BatchGroup` on the last element. + BG = reinterpret_cast<BatchGroup *>( + decompactPtr(SizeClassMap::BatchClassId, Array[Size - 1])); + --Size; + BG->Batches.clear(); + // BatchClass hasn't enabled memory group. Use `0` to indicate there's no + // memory group here. + BG->CompactPtrGroupBase = 0; + // `BG` is also the block of BatchClassId. Note that this is different + // from `CreateGroup` in `pushBlocksImpl` + BG->PushedBlocks = 1; + BG->BytesInBGAtLastCheckpoint = 0; + BG->MaxCachedPerBatch = TransferBatch::getMaxCached( + getSizeByClassId(SizeClassMap::BatchClassId)); + + Region->FreeListInfo.BlockList.push_front(BG); + } + + if (UNLIKELY(Size == 0)) + return; + + // This happens under 2 cases. + // 1. just allocated a new `BatchGroup`. + // 2. Only 1 block is pushed when the freelist is empty. + if (BG->Batches.empty()) { + // Construct the `TransferBatch` on the last element. + TransferBatch *TB = reinterpret_cast<TransferBatch *>( + decompactPtr(SizeClassMap::BatchClassId, Array[Size - 1])); + TB->clear(); + // As mentioned above, addresses of `TransferBatch` and `BatchGroup` are + // recorded in the TransferBatch. + TB->add(Array[Size - 1]); + TB->add( + compactPtr(SizeClassMap::BatchClassId, reinterpret_cast<uptr>(BG))); + --Size; + DCHECK_EQ(BG->PushedBlocks, 1U); + // `TB` is also the block of BatchClassId. + BG->PushedBlocks += 1; + BG->Batches.push_front(TB); + } + + TransferBatch *CurBatch = BG->Batches.front(); + DCHECK_NE(CurBatch, nullptr); + + for (u32 I = 0; I < Size;) { + u16 UnusedSlots = + static_cast<u16>(BG->MaxCachedPerBatch - CurBatch->getCount()); + if (UnusedSlots == 0) { + CurBatch = reinterpret_cast<TransferBatch *>( + decompactPtr(SizeClassMap::BatchClassId, Array[I])); + CurBatch->clear(); + // Self-contained + CurBatch->add(Array[I]); + ++I; + // TODO(chiahungduan): Avoid the use of push_back() in `Batches` of + // BatchClassId. + BG->Batches.push_front(CurBatch); + UnusedSlots = static_cast<u16>(BG->MaxCachedPerBatch - 1); + } + // `UnusedSlots` is u16 so the result will be also fit in u16. + const u16 AppendSize = static_cast<u16>(Min<u32>(UnusedSlots, Size - I)); + CurBatch->appendFromArray(&Array[I], AppendSize); + I += AppendSize; + } + + BG->PushedBlocks += Size; } // Push the blocks to their batch group. The layout will be like, // - // FreeList - > BG -> BG -> BG - // | | | - // v v v - // TB TB TB - // | - // v - // TB + // FreeListInfo.BlockList - > BG -> BG -> BG + // | | | + // v v v + // TB TB TB + // | + // v + // TB // // Each BlockGroup(BG) will associate with unique group id and the free blocks // are managed by a list of TransferBatch(TB). To reduce the time of inserting @@ -391,45 +692,22 @@ private: // that we can get better performance of maintaining sorted property. // Use `SameGroup=true` to indicate that all blocks in the array are from the // same group then we will skip checking the group id of each block. - // - // Note that this aims to have a better management of dirty pages, i.e., the - // RSS usage won't grow indefinitely. There's an exception that we may not put - // a block to its associated group. While populating new blocks, we may have - // blocks cross different groups. However, most cases will fall into same - // group and they are supposed to be popped soon. In that case, it's not worth - // sorting the array with the almost-sorted property. Therefore, we use - // `SameGroup=true` instead. - // - // The region mutex needs to be held while calling this method. - void pushBlocksImpl(CacheT *C, uptr ClassId, CompactPtrT *Array, u32 Size, - bool SameGroup = false) { + void pushBlocksImpl(CacheT *C, uptr ClassId, RegionInfo *Region, + CompactPtrT *Array, u32 Size, bool SameGroup = false) + REQUIRES(Region->FLLock) { + DCHECK_NE(ClassId, SizeClassMap::BatchClassId); DCHECK_GT(Size, 0U); - RegionInfo *Region = getRegionInfo(ClassId); - auto CreateGroup = [&](uptr GroupId) { - BatchGroup *BG = nullptr; - TransferBatch *TB = nullptr; - if (ClassId == SizeClassMap::BatchClassId) { - DCHECK_GE(Size, 2U); - BG = reinterpret_cast<BatchGroup *>( - decompactPtr(ClassId, Array[Size - 1])); - BG->Batches.clear(); - - TB = reinterpret_cast<TransferBatch *>( - decompactPtr(ClassId, Array[Size - 2])); - TB->clear(); - } else { - BG = C->createGroup(); - BG->Batches.clear(); - - TB = C->createBatch(ClassId, nullptr); - TB->clear(); - } + auto CreateGroup = [&](uptr CompactPtrGroupBase) { + BatchGroup *BG = C->createGroup(); + BG->Batches.clear(); + TransferBatch *TB = C->createBatch(ClassId, nullptr); + TB->clear(); - BG->GroupId = GroupId; + BG->CompactPtrGroupBase = CompactPtrGroupBase; BG->Batches.push_front(TB); BG->PushedBlocks = 0; - BG->PushedBlocksAtLastCheckpoint = 0; + BG->BytesInBGAtLastCheckpoint = 0; BG->MaxCachedPerBatch = TransferBatch::getMaxCached(getSizeByClassId(ClassId)); @@ -462,13 +740,14 @@ private: BG->PushedBlocks += Size; }; - BatchGroup *Cur = Region->FreeList.front(); + Region->FreeListInfo.PushedBlocks += Size; + BatchGroup *Cur = Region->FreeListInfo.BlockList.front(); if (ClassId == SizeClassMap::BatchClassId) { if (Cur == nullptr) { // Don't need to classify BatchClassId. - Cur = CreateGroup(/*GroupId=*/0); - Region->FreeList.push_front(Cur); + Cur = CreateGroup(/*CompactPtrGroupBase=*/0); + Region->FreeListInfo.BlockList.push_front(Cur); } InsertBlocks(Cur, Array, Size); return; @@ -478,22 +757,27 @@ private: // will be pushed next. `Prev` is the element right before `Cur`. BatchGroup *Prev = nullptr; - while (Cur != nullptr && compactPtrGroup(Array[0]) > Cur->GroupId) { + while (Cur != nullptr && + compactPtrGroup(Array[0]) > Cur->CompactPtrGroupBase) { Prev = Cur; Cur = Cur->Next; } - if (Cur == nullptr || compactPtrGroup(Array[0]) != Cur->GroupId) { + if (Cur == nullptr || + compactPtrGroup(Array[0]) != Cur->CompactPtrGroupBase) { Cur = CreateGroup(compactPtrGroup(Array[0])); if (Prev == nullptr) - Region->FreeList.push_front(Cur); + Region->FreeListInfo.BlockList.push_front(Cur); else - Region->FreeList.insert(Prev, Cur); + Region->FreeListInfo.BlockList.insert(Prev, Cur); } // All the blocks are from the same group, just push without checking group // id. if (SameGroup) { + for (u32 I = 0; I < Size; ++I) + DCHECK_EQ(compactPtrGroup(Array[I]), Cur->CompactPtrGroupBase); + InsertBlocks(Cur, Array, Size); return; } @@ -503,18 +787,20 @@ private: u32 Count = 1; for (u32 I = 1; I < Size; ++I) { if (compactPtrGroup(Array[I - 1]) != compactPtrGroup(Array[I])) { - DCHECK_EQ(compactPtrGroup(Array[I - 1]), Cur->GroupId); + DCHECK_EQ(compactPtrGroup(Array[I - 1]), Cur->CompactPtrGroupBase); InsertBlocks(Cur, Array + I - Count, Count); - while (Cur != nullptr && compactPtrGroup(Array[I]) > Cur->GroupId) { + while (Cur != nullptr && + compactPtrGroup(Array[I]) > Cur->CompactPtrGroupBase) { Prev = Cur; Cur = Cur->Next; } - if (Cur == nullptr || compactPtrGroup(Array[I]) != Cur->GroupId) { + if (Cur == nullptr || + compactPtrGroup(Array[I]) != Cur->CompactPtrGroupBase) { Cur = CreateGroup(compactPtrGroup(Array[I])); DCHECK_NE(Prev, nullptr); - Region->FreeList.insert(Prev, Cur); + Region->FreeListInfo.BlockList.insert(Prev, Cur); } Count = 1; @@ -530,14 +816,28 @@ private: // group id will be considered first. // // The region mutex needs to be held while calling this method. - TransferBatch *popBatchImpl(CacheT *C, uptr ClassId) { - RegionInfo *Region = getRegionInfo(ClassId); - if (Region->FreeList.empty()) + TransferBatch *popBatchImpl(CacheT *C, uptr ClassId, RegionInfo *Region) + REQUIRES(Region->FLLock) { + if (Region->FreeListInfo.BlockList.empty()) return nullptr; SinglyLinkedList<TransferBatch> &Batches = - Region->FreeList.front()->Batches; - DCHECK(!Batches.empty()); + Region->FreeListInfo.BlockList.front()->Batches; + + if (Batches.empty()) { + DCHECK_EQ(ClassId, SizeClassMap::BatchClassId); + BatchGroup *BG = Region->FreeListInfo.BlockList.front(); + Region->FreeListInfo.BlockList.pop_front(); + + // Block used by `BatchGroup` is from BatchClassId. Turn the block into + // `TransferBatch` with single block. + TransferBatch *TB = reinterpret_cast<TransferBatch *>(BG); + TB->clear(); + TB->add( + compactPtr(SizeClassMap::BatchClassId, reinterpret_cast<uptr>(TB))); + Region->FreeListInfo.PoppedBlocks += 1; + return TB; + } TransferBatch *B = Batches.front(); Batches.pop_front(); @@ -545,8 +845,8 @@ private: DCHECK_GT(B->getCount(), 0U); if (Batches.empty()) { - BatchGroup *BG = Region->FreeList.front(); - Region->FreeList.pop_front(); + BatchGroup *BG = Region->FreeListInfo.BlockList.front(); + Region->FreeListInfo.BlockList.pop_front(); // We don't keep BatchGroup with zero blocks to avoid empty-checking while // allocating. Note that block used by constructing BatchGroup is recorded @@ -557,51 +857,49 @@ private: C->deallocate(SizeClassMap::BatchClassId, BG); } + Region->FreeListInfo.PoppedBlocks += B->getCount(); + return B; } - NOINLINE bool populateFreeList(CacheT *C, uptr ClassId, RegionInfo *Region) { + // Refill the freelist and return one batch. + NOINLINE TransferBatch *populateFreeListAndPopBatch(CacheT *C, uptr ClassId, + RegionInfo *Region) + REQUIRES(Region->MMLock) EXCLUDES(Region->FLLock) { const uptr Size = getSizeByClassId(ClassId); const u16 MaxCount = TransferBatch::getMaxCached(Size); const uptr RegionBeg = Region->RegionBeg; - const uptr MappedUser = Region->MappedUser; - const uptr TotalUserBytes = Region->AllocatedUser + MaxCount * Size; + const uptr MappedUser = Region->MemMapInfo.MappedUser; + const uptr TotalUserBytes = + Region->MemMapInfo.AllocatedUser + MaxCount * Size; // Map more space for blocks, if necessary. if (TotalUserBytes > MappedUser) { // Do the mmap for the user memory. const uptr MapSize = - roundUpTo(TotalUserBytes - MappedUser, MapSizeIncrement); + roundUp(TotalUserBytes - MappedUser, MapSizeIncrement); const uptr RegionBase = RegionBeg - getRegionBaseByClassId(ClassId); if (UNLIKELY(RegionBase + MappedUser + MapSize > RegionSize)) { - if (!Region->Exhausted) { - Region->Exhausted = true; - ScopedString Str; - getStats(&Str); - Str.append( - "Scudo OOM: The process has exhausted %zuM for size class %zu.\n", - RegionSize >> 20, Size); - Str.output(); - } - return false; + Region->Exhausted = true; + return nullptr; } - if (MappedUser == 0) - Region->Data = Data; - if (UNLIKELY(!map( - reinterpret_cast<void *>(RegionBeg + MappedUser), MapSize, - "scudo:primary", + + if (UNLIKELY(!Region->MemMapInfo.MemMap.remap( + RegionBeg + MappedUser, MapSize, "scudo:primary", MAP_ALLOWNOMEM | MAP_RESIZABLE | - (useMemoryTagging<Config>(Options.load()) ? MAP_MEMTAG : 0), - &Region->Data))) { - return false; + (useMemoryTagging<Config>(Options.load()) ? MAP_MEMTAG + : 0)))) { + return nullptr; } - Region->MappedUser += MapSize; + Region->MemMapInfo.MappedUser += MapSize; C->getStats().add(StatMapped, MapSize); } - const u32 NumberOfBlocks = Min( - MaxNumBatches * MaxCount, - static_cast<u32>((Region->MappedUser - Region->AllocatedUser) / Size)); + const u32 NumberOfBlocks = + Min(MaxNumBatches * MaxCount, + static_cast<u32>((Region->MemMapInfo.MappedUser - + Region->MemMapInfo.AllocatedUser) / + Size)); DCHECK_GT(NumberOfBlocks, 0); constexpr u32 ShuffleArraySize = @@ -610,173 +908,634 @@ private: DCHECK_LE(NumberOfBlocks, ShuffleArraySize); const uptr CompactPtrBase = getCompactPtrBaseByClassId(ClassId); - uptr P = RegionBeg + Region->AllocatedUser; + uptr P = RegionBeg + Region->MemMapInfo.AllocatedUser; for (u32 I = 0; I < NumberOfBlocks; I++, P += Size) ShuffleArray[I] = compactPtrInternal(CompactPtrBase, P); - // No need to shuffle the batches size class. - if (ClassId != SizeClassMap::BatchClassId) - shuffle(ShuffleArray, NumberOfBlocks, &Region->RandState); - for (u32 I = 0; I < NumberOfBlocks;) { - // `MaxCount` is u16 so the result will also fit in u16. - const u16 N = static_cast<u16>(Min<u32>(MaxCount, NumberOfBlocks - I)); - // Note that the N blocks here may have different group ids. Given that - // it only happens when it crosses the group size boundary. Instead of - // sorting them, treat them as same group here to avoid sorting the - // almost-sorted blocks. - pushBlocksImpl(C, ClassId, &ShuffleArray[I], N, /*SameGroup=*/true); - I += N; + + ScopedLock L(Region->FLLock); + + if (ClassId != SizeClassMap::BatchClassId) { + u32 N = 1; + uptr CurGroup = compactPtrGroup(ShuffleArray[0]); + for (u32 I = 1; I < NumberOfBlocks; I++) { + if (UNLIKELY(compactPtrGroup(ShuffleArray[I]) != CurGroup)) { + shuffle(ShuffleArray + I - N, N, &Region->RandState); + pushBlocksImpl(C, ClassId, Region, ShuffleArray + I - N, N, + /*SameGroup=*/true); + N = 1; + CurGroup = compactPtrGroup(ShuffleArray[I]); + } else { + ++N; + } + } + + shuffle(ShuffleArray + NumberOfBlocks - N, N, &Region->RandState); + pushBlocksImpl(C, ClassId, Region, &ShuffleArray[NumberOfBlocks - N], N, + /*SameGroup=*/true); + } else { + pushBatchClassBlocks(Region, ShuffleArray, NumberOfBlocks); } + TransferBatch *B = popBatchImpl(C, ClassId, Region); + DCHECK_NE(B, nullptr); + + // Note that `PushedBlocks` and `PoppedBlocks` are supposed to only record + // the requests from `PushBlocks` and `PopBatch` which are external + // interfaces. `populateFreeListAndPopBatch` is the internal interface so we + // should set the values back to avoid incorrectly setting the stats. + Region->FreeListInfo.PushedBlocks -= NumberOfBlocks; + const uptr AllocatedUser = Size * NumberOfBlocks; C->getStats().add(StatFree, AllocatedUser); - Region->AllocatedUser += AllocatedUser; + Region->MemMapInfo.AllocatedUser += AllocatedUser; - return true; + return B; } - void getStats(ScopedString *Str, uptr ClassId, uptr Rss) { - RegionInfo *Region = getRegionInfo(ClassId); - if (Region->MappedUser == 0) + void getStats(ScopedString *Str, uptr ClassId, RegionInfo *Region) + REQUIRES(Region->MMLock, Region->FLLock) { + if (Region->MemMapInfo.MappedUser == 0) return; - const uptr InUse = Region->Stats.PoppedBlocks - Region->Stats.PushedBlocks; - const uptr TotalChunks = Region->AllocatedUser / getSizeByClassId(ClassId); - Str->append("%s %02zu (%6zu): mapped: %6zuK popped: %7zu pushed: %7zu " - "inuse: %6zu total: %6zu rss: %6zuK releases: %6zu last " - "released: %6zuK region: 0x%zx (0x%zx)\n", - Region->Exhausted ? "F" : " ", ClassId, - getSizeByClassId(ClassId), Region->MappedUser >> 10, - Region->Stats.PoppedBlocks, Region->Stats.PushedBlocks, InUse, - TotalChunks, Rss >> 10, Region->ReleaseInfo.RangesReleased, - Region->ReleaseInfo.LastReleasedBytes >> 10, Region->RegionBeg, - getRegionBaseByClassId(ClassId)); + const uptr BlockSize = getSizeByClassId(ClassId); + const uptr InUse = + Region->FreeListInfo.PoppedBlocks - Region->FreeListInfo.PushedBlocks; + const uptr BytesInFreeList = + Region->MemMapInfo.AllocatedUser - InUse * BlockSize; + uptr RegionPushedBytesDelta = 0; + if (BytesInFreeList >= + Region->ReleaseInfo.BytesInFreeListAtLastCheckpoint) { + RegionPushedBytesDelta = + BytesInFreeList - Region->ReleaseInfo.BytesInFreeListAtLastCheckpoint; + } + const uptr TotalChunks = Region->MemMapInfo.AllocatedUser / BlockSize; + Str->append( + "%s %02zu (%6zu): mapped: %6zuK popped: %7zu pushed: %7zu " + "inuse: %6zu total: %6zu releases: %6zu last " + "released: %6zuK latest pushed bytes: %6zuK region: 0x%zx (0x%zx)\n", + Region->Exhausted ? "F" : " ", ClassId, getSizeByClassId(ClassId), + Region->MemMapInfo.MappedUser >> 10, Region->FreeListInfo.PoppedBlocks, + Region->FreeListInfo.PushedBlocks, InUse, TotalChunks, + Region->ReleaseInfo.RangesReleased, + Region->ReleaseInfo.LastReleasedBytes >> 10, + RegionPushedBytesDelta >> 10, Region->RegionBeg, + getRegionBaseByClassId(ClassId)); } NOINLINE uptr releaseToOSMaybe(RegionInfo *Region, uptr ClassId, - bool Force = false) { + ReleaseToOS ReleaseType = ReleaseToOS::Normal) + REQUIRES(Region->MMLock) EXCLUDES(Region->FLLock) { + ScopedLock L(Region->FLLock); + const uptr BlockSize = getSizeByClassId(ClassId); + const uptr BytesInFreeList = + Region->MemMapInfo.AllocatedUser - (Region->FreeListInfo.PoppedBlocks - + Region->FreeListInfo.PushedBlocks) * + BlockSize; + if (UNLIKELY(BytesInFreeList == 0)) + return false; + + const uptr AllocatedUserEnd = + Region->MemMapInfo.AllocatedUser + Region->RegionBeg; + const uptr CompactPtrBase = getCompactPtrBaseByClassId(ClassId); + + // ====================================================================== // + // 1. Check if we have enough free blocks and if it's worth doing a page + // release. + // ====================================================================== // + if (ReleaseType != ReleaseToOS::ForceAll && + !hasChanceToReleasePages(Region, BlockSize, BytesInFreeList, + ReleaseType)) { + return 0; + } + + // ====================================================================== // + // 2. Determine which groups can release the pages. Use a heuristic to + // gather groups that are candidates for doing a release. + // ====================================================================== // + SinglyLinkedList<BatchGroup> GroupsToRelease; + if (ReleaseType == ReleaseToOS::ForceAll) { + GroupsToRelease = Region->FreeListInfo.BlockList; + Region->FreeListInfo.BlockList.clear(); + } else { + GroupsToRelease = collectGroupsToRelease( + Region, BlockSize, AllocatedUserEnd, CompactPtrBase); + } + if (GroupsToRelease.empty()) + return 0; + + // Ideally, we should use a class like `ScopedUnlock`. However, this form of + // unlocking is not supported by the thread-safety analysis. See + // https://clang.llvm.org/docs/ThreadSafetyAnalysis.html#no-alias-analysis + // for more details. + // Put it as local class so that we can mark the ctor/dtor with proper + // annotations associated to the target lock. Note that accessing the + // function variable in local class only works in thread-safety annotations. + // TODO: Implement general `ScopedUnlock` when it's supported. + class FLLockScopedUnlock { + public: + FLLockScopedUnlock(RegionInfo *Region) RELEASE(Region->FLLock) + : R(Region) { + R->FLLock.assertHeld(); + R->FLLock.unlock(); + } + ~FLLockScopedUnlock() ACQUIRE(Region->FLLock) { R->FLLock.lock(); } + + private: + RegionInfo *R; + }; + + // Note that we have extracted the `GroupsToRelease` from region freelist. + // It's safe to let pushBlocks()/popBatches() access the remaining region + // freelist. In the steps 3 and 4, we will temporarily release the FLLock + // and lock it again before step 5. + + uptr ReleasedBytes = 0; + { + FLLockScopedUnlock UL(Region); + // ==================================================================== // + // 3. Mark the free blocks in `GroupsToRelease` in the + // `PageReleaseContext`. Then we can tell which pages are in-use by + // querying `PageReleaseContext`. + // ==================================================================== // + PageReleaseContext Context = markFreeBlocks( + Region, BlockSize, AllocatedUserEnd, CompactPtrBase, GroupsToRelease); + if (UNLIKELY(!Context.hasBlockMarked())) { + ScopedLock L(Region->FLLock); + mergeGroupsToReleaseBack(Region, GroupsToRelease); + return 0; + } + + // ==================================================================== // + // 4. Release the unused physical pages back to the OS. + // ==================================================================== // + RegionReleaseRecorder<MemMapT> Recorder(&Region->MemMapInfo.MemMap, + Region->RegionBeg, + Context.getReleaseOffset()); + auto SkipRegion = [](UNUSED uptr RegionIndex) { return false; }; + releaseFreeMemoryToOS(Context, Recorder, SkipRegion); + if (Recorder.getReleasedRangesCount() > 0) { + Region->ReleaseInfo.BytesInFreeListAtLastCheckpoint = BytesInFreeList; + Region->ReleaseInfo.RangesReleased += Recorder.getReleasedRangesCount(); + Region->ReleaseInfo.LastReleasedBytes = Recorder.getReleasedBytes(); + } + Region->ReleaseInfo.LastReleaseAtNs = getMonotonicTimeFast(); + ReleasedBytes = Recorder.getReleasedBytes(); + } + + // ====================================================================== // + // 5. Merge the `GroupsToRelease` back to the freelist. + // ====================================================================== // + mergeGroupsToReleaseBack(Region, GroupsToRelease); + + return ReleasedBytes; + } + + bool hasChanceToReleasePages(RegionInfo *Region, uptr BlockSize, + uptr BytesInFreeList, ReleaseToOS ReleaseType) + REQUIRES(Region->MMLock, Region->FLLock) { + DCHECK_GE(Region->FreeListInfo.PoppedBlocks, + Region->FreeListInfo.PushedBlocks); const uptr PageSize = getPageSizeCached(); - DCHECK_GE(Region->Stats.PoppedBlocks, Region->Stats.PushedBlocks); - const uptr BytesInFreeList = - Region->AllocatedUser - - (Region->Stats.PoppedBlocks - Region->Stats.PushedBlocks) * BlockSize; - if (BytesInFreeList < PageSize) - return 0; // No chance to release anything. - const uptr BytesPushed = (Region->Stats.PushedBlocks - - Region->ReleaseInfo.PushedBlocksAtLastRelease) * - BlockSize; - if (BytesPushed < PageSize) - return 0; // Nothing new to release. - - bool CheckDensity = BlockSize < PageSize / 16U; + // Always update `BytesInFreeListAtLastCheckpoint` with the smallest value + // so that we won't underestimate the releasable pages. For example, the + // following is the region usage, + // + // BytesInFreeListAtLastCheckpoint AllocatedUser + // v v + // |---------------------------------------> + // ^ ^ + // BytesInFreeList ReleaseThreshold + // + // In general, if we have collected enough bytes and the amount of free + // bytes meets the ReleaseThreshold, we will try to do page release. If we + // don't update `BytesInFreeListAtLastCheckpoint` when the current + // `BytesInFreeList` is smaller, we may take longer time to wait for enough + // freed blocks because we miss the bytes between + // (BytesInFreeListAtLastCheckpoint - BytesInFreeList). + if (BytesInFreeList <= + Region->ReleaseInfo.BytesInFreeListAtLastCheckpoint) { + Region->ReleaseInfo.BytesInFreeListAtLastCheckpoint = BytesInFreeList; + } + + const uptr RegionPushedBytesDelta = + BytesInFreeList - Region->ReleaseInfo.BytesInFreeListAtLastCheckpoint; + if (RegionPushedBytesDelta < PageSize) + return false; + // Releasing smaller blocks is expensive, so we want to make sure that a // significant amount of bytes are free, and that there has been a good // amount of batches pushed to the freelist before attempting to release. - if (CheckDensity) { - if (!Force && BytesPushed < Region->AllocatedUser / 16U) - return 0; - } + if (isSmallBlock(BlockSize) && ReleaseType == ReleaseToOS::Normal) + if (RegionPushedBytesDelta < Region->TryReleaseThreshold) + return false; - if (!Force) { + if (ReleaseType == ReleaseToOS::Normal) { const s32 IntervalMs = atomic_load_relaxed(&ReleaseToOsIntervalMs); if (IntervalMs < 0) - return 0; - if (Region->ReleaseInfo.LastReleaseAtNs + - static_cast<u64>(IntervalMs) * 1000000 > - getMonotonicTime()) { - return 0; // Memory was returned recently. + return false; + + // The constant 8 here is selected from profiling some apps and the number + // of unreleased pages in the large size classes is around 16 pages or + // more. Choose half of it as a heuristic and which also avoids page + // release every time for every pushBlocks() attempt by large blocks. + const bool ByPassReleaseInterval = + isLargeBlock(BlockSize) && RegionPushedBytesDelta > 8 * PageSize; + if (!ByPassReleaseInterval) { + if (Region->ReleaseInfo.LastReleaseAtNs + + static_cast<u64>(IntervalMs) * 1000000 > + getMonotonicTimeFast()) { + // Memory was returned recently. + return false; + } } - } + } // if (ReleaseType == ReleaseToOS::Normal) + return true; + } + + SinglyLinkedList<BatchGroup> + collectGroupsToRelease(RegionInfo *Region, const uptr BlockSize, + const uptr AllocatedUserEnd, const uptr CompactPtrBase) + REQUIRES(Region->MMLock, Region->FLLock) { const uptr GroupSize = (1U << GroupSizeLog); - const uptr AllocatedUserEnd = Region->AllocatedUser + Region->RegionBeg; - ReleaseRecorder Recorder(Region->RegionBeg, &Region->Data); - PageReleaseContext Context(BlockSize, Region->AllocatedUser, - /*NumberOfRegions=*/1U); + const uptr PageSize = getPageSizeCached(); + SinglyLinkedList<BatchGroup> GroupsToRelease; + + // We are examining each group and will take the minimum distance to the + // release threshold as the next Region::TryReleaseThreshold(). Note that if + // the size of free blocks has reached the release threshold, the distance + // to the next release will be PageSize * SmallerBlockReleasePageDelta. See + // the comment on `SmallerBlockReleasePageDelta` for more details. + uptr MinDistToThreshold = GroupSize; + + for (BatchGroup *BG = Region->FreeListInfo.BlockList.front(), + *Prev = nullptr; + BG != nullptr;) { + // Group boundary is always GroupSize-aligned from CompactPtr base. The + // layout of memory groups is like, + // + // (CompactPtrBase) + // #1 CompactPtrGroupBase #2 CompactPtrGroupBase ... + // | | | + // v v v + // +-----------------------+-----------------------+ + // \ / \ / + // --- GroupSize --- --- GroupSize --- + // + // After decompacting the CompactPtrGroupBase, we expect the alignment + // property is held as well. + const uptr BatchGroupBase = + decompactGroupBase(CompactPtrBase, BG->CompactPtrGroupBase); + DCHECK_LE(Region->RegionBeg, BatchGroupBase); + DCHECK_GE(AllocatedUserEnd, BatchGroupBase); + DCHECK_EQ((Region->RegionBeg - BatchGroupBase) % GroupSize, 0U); + // TransferBatches are pushed in front of BG.Batches. The first one may + // not have all caches used. + const uptr NumBlocks = (BG->Batches.size() - 1) * BG->MaxCachedPerBatch + + BG->Batches.front()->getCount(); + const uptr BytesInBG = NumBlocks * BlockSize; - const uptr CompactPtrBase = getCompactPtrBaseByClassId(ClassId); - auto DecompactPtr = [CompactPtrBase](CompactPtrT CompactPtr) { - return decompactPtrInternal(CompactPtrBase, CompactPtr); - }; - for (BatchGroup &BG : Region->FreeList) { - const uptr PushedBytesDelta = - BG.PushedBlocks - BG.PushedBlocksAtLastCheckpoint; - if (PushedBytesDelta * BlockSize < PageSize) + if (BytesInBG <= BG->BytesInBGAtLastCheckpoint) { + BG->BytesInBGAtLastCheckpoint = BytesInBG; + Prev = BG; + BG = BG->Next; continue; + } + + const uptr PushedBytesDelta = BG->BytesInBGAtLastCheckpoint - BytesInBG; + + // Given the randomness property, we try to release the pages only if the + // bytes used by free blocks exceed certain proportion of group size. Note + // that this heuristic only applies when all the spaces in a BatchGroup + // are allocated. + if (isSmallBlock(BlockSize)) { + const uptr BatchGroupEnd = BatchGroupBase + GroupSize; + const uptr AllocatedGroupSize = AllocatedUserEnd >= BatchGroupEnd + ? GroupSize + : AllocatedUserEnd - BatchGroupBase; + const uptr ReleaseThreshold = + (AllocatedGroupSize * (100 - 1U - BlockSize / 16U)) / 100U; + const bool HighDensity = BytesInBG >= ReleaseThreshold; + const bool MayHaveReleasedAll = NumBlocks >= (GroupSize / BlockSize); + // If all blocks in the group are released, we will do range marking + // which is fast. Otherwise, we will wait until we have accumulated + // a certain amount of free memory. + const bool ReachReleaseDelta = + MayHaveReleasedAll + ? true + : PushedBytesDelta >= PageSize * SmallerBlockReleasePageDelta; + + if (!HighDensity) { + DCHECK_LE(BytesInBG, ReleaseThreshold); + // The following is the usage of a memroy group, + // + // BytesInBG ReleaseThreshold + // / \ v + // +---+---------------------------+-----+ + // | | | | | + // +---+---------------------------+-----+ + // \ / ^ + // PushedBytesDelta GroupEnd + MinDistToThreshold = + Min(MinDistToThreshold, + ReleaseThreshold - BytesInBG + PushedBytesDelta); + } else { + // If it reaches high density at this round, the next time we will try + // to release is based on SmallerBlockReleasePageDelta + MinDistToThreshold = + Min(MinDistToThreshold, PageSize * SmallerBlockReleasePageDelta); + } - // Group boundary does not necessarily have the same alignment as Region. - // It may sit across a Region boundary. Which means that we may have the - // following two cases, + if (!HighDensity || !ReachReleaseDelta) { + Prev = BG; + BG = BG->Next; + continue; + } + } + + // If `BG` is the first BatchGroup in the list, we only need to advance + // `BG` and call FreeListInfo.BlockList::pop_front(). No update is needed + // for `Prev`. + // + // (BG) (BG->Next) + // Prev Cur BG + // | | | + // v v v + // nil +--+ +--+ + // |X | -> | | -> ... + // +--+ +--+ // - // 1. Group boundary sits before RegionBeg. + // Otherwise, `Prev` will be used to extract the `Cur` from the + // `FreeListInfo.BlockList`. // - // (BatchGroupBeg) - // batchGroupBase RegionBeg BatchGroupEnd - // | | | - // v v v - // +------------+----------------+ - // \ / - // ------ GroupSize ------ + // (BG) (BG->Next) + // Prev Cur BG + // | | | + // v v v + // +--+ +--+ +--+ + // | | -> |X | -> | | -> ... + // +--+ +--+ +--+ // - // 2. Group boundary sits after RegionBeg. + // After FreeListInfo.BlockList::extract(), // - // (BatchGroupBeg) - // RegionBeg batchGroupBase BatchGroupEnd - // | | | - // v v v - // +-----------+-----------------------------+ - // \ / - // ------ GroupSize ------ + // Prev Cur BG + // | | | + // v v v + // +--+ +--+ +--+ + // | |-+ |X | +->| | -> ... + // +--+ | +--+ | +--+ + // +--------+ // - // Note that in the first case, the group range before RegionBeg is never - // used. Therefore, while calculating the used group size, we should - // exclude that part to get the correct size. - const uptr BatchGroupBeg = - Max(batchGroupBase(CompactPtrBase, BG.GroupId), Region->RegionBeg); - DCHECK_GE(AllocatedUserEnd, BatchGroupBeg); - const uptr BatchGroupEnd = - batchGroupBase(CompactPtrBase, BG.GroupId) + GroupSize; + // Note that we need to advance before pushing this BatchGroup to + // GroupsToRelease because it's a destructive operation. + + BatchGroup *Cur = BG; + BG = BG->Next; + + // Ideally, we may want to update this only after successful release. + // However, for smaller blocks, each block marking is a costly operation. + // Therefore, we update it earlier. + // TODO: Consider updating this after releasing pages if `ReleaseRecorder` + // can tell the released bytes in each group. + Cur->BytesInBGAtLastCheckpoint = BytesInBG; + + if (Prev != nullptr) + Region->FreeListInfo.BlockList.extract(Prev, Cur); + else + Region->FreeListInfo.BlockList.pop_front(); + GroupsToRelease.push_back(Cur); + } + + // Only small blocks have the adaptive `TryReleaseThreshold`. + if (isSmallBlock(BlockSize)) { + // If the MinDistToThreshold is not updated, that means each memory group + // may have only pushed less than a page size. In that case, just set it + // back to normal. + if (MinDistToThreshold == GroupSize) + MinDistToThreshold = PageSize * SmallerBlockReleasePageDelta; + Region->TryReleaseThreshold = MinDistToThreshold; + } + + return GroupsToRelease; + } + + PageReleaseContext + markFreeBlocks(RegionInfo *Region, const uptr BlockSize, + const uptr AllocatedUserEnd, const uptr CompactPtrBase, + SinglyLinkedList<BatchGroup> &GroupsToRelease) + REQUIRES(Region->MMLock) EXCLUDES(Region->FLLock) { + const uptr GroupSize = (1U << GroupSizeLog); + auto DecompactPtr = [CompactPtrBase](CompactPtrT CompactPtr) { + return decompactPtrInternal(CompactPtrBase, CompactPtr); + }; + + const uptr ReleaseBase = decompactGroupBase( + CompactPtrBase, GroupsToRelease.front()->CompactPtrGroupBase); + const uptr LastGroupEnd = + Min(decompactGroupBase(CompactPtrBase, + GroupsToRelease.back()->CompactPtrGroupBase) + + GroupSize, + AllocatedUserEnd); + // The last block may straddle the group boundary. Rounding up to BlockSize + // to get the exact range. + const uptr ReleaseEnd = + roundUpSlow(LastGroupEnd - Region->RegionBeg, BlockSize) + + Region->RegionBeg; + const uptr ReleaseRangeSize = ReleaseEnd - ReleaseBase; + const uptr ReleaseOffset = ReleaseBase - Region->RegionBeg; + + PageReleaseContext Context(BlockSize, /*NumberOfRegions=*/1U, + ReleaseRangeSize, ReleaseOffset); + // We may not be able to do the page release in a rare case that we may + // fail on PageMap allocation. + if (UNLIKELY(!Context.ensurePageMapAllocated())) + return Context; + + for (BatchGroup &BG : GroupsToRelease) { + const uptr BatchGroupBase = + decompactGroupBase(CompactPtrBase, BG.CompactPtrGroupBase); + const uptr BatchGroupEnd = BatchGroupBase + GroupSize; const uptr AllocatedGroupSize = AllocatedUserEnd >= BatchGroupEnd - ? BatchGroupEnd - BatchGroupBeg - : AllocatedUserEnd - BatchGroupBeg; - if (AllocatedGroupSize == 0) - continue; + ? GroupSize + : AllocatedUserEnd - BatchGroupBase; + const uptr BatchGroupUsedEnd = BatchGroupBase + AllocatedGroupSize; + const bool MayContainLastBlockInRegion = + BatchGroupUsedEnd == AllocatedUserEnd; + const bool BlockAlignedWithUsedEnd = + (BatchGroupUsedEnd - Region->RegionBeg) % BlockSize == 0; + + uptr MaxContainedBlocks = AllocatedGroupSize / BlockSize; + if (!BlockAlignedWithUsedEnd) + ++MaxContainedBlocks; - // TransferBatches are pushed in front of BG.Batches. The first one may - // not have all caches used. const uptr NumBlocks = (BG.Batches.size() - 1) * BG.MaxCachedPerBatch + BG.Batches.front()->getCount(); - const uptr BytesInBG = NumBlocks * BlockSize; - // Given the randomness property, we try to release the pages only if the - // bytes used by free blocks exceed certain proportion of group size. Note - // that this heuristic only applies when all the spaces in a BatchGroup - // are allocated. - if (CheckDensity && (BytesInBG * 100U) / AllocatedGroupSize < - (100U - 1U - BlockSize / 16U)) { + + if (NumBlocks == MaxContainedBlocks) { + for (const auto &It : BG.Batches) { + if (&It != BG.Batches.front()) + DCHECK_EQ(It.getCount(), BG.MaxCachedPerBatch); + for (u16 I = 0; I < It.getCount(); ++I) + DCHECK_EQ(compactPtrGroup(It.get(I)), BG.CompactPtrGroupBase); + } + + Context.markRangeAsAllCounted(BatchGroupBase, BatchGroupUsedEnd, + Region->RegionBeg, /*RegionIndex=*/0, + Region->MemMapInfo.AllocatedUser); + } else { + DCHECK_LT(NumBlocks, MaxContainedBlocks); + // Note that we don't always visit blocks in each BatchGroup so that we + // may miss the chance of releasing certain pages that cross + // BatchGroups. + Context.markFreeBlocksInRegion( + BG.Batches, DecompactPtr, Region->RegionBeg, /*RegionIndex=*/0, + Region->MemMapInfo.AllocatedUser, MayContainLastBlockInRegion); + } + } + + DCHECK(Context.hasBlockMarked()); + + return Context; + } + + void mergeGroupsToReleaseBack(RegionInfo *Region, + SinglyLinkedList<BatchGroup> &GroupsToRelease) + REQUIRES(Region->MMLock, Region->FLLock) { + // After merging two freelists, we may have redundant `BatchGroup`s that + // need to be recycled. The number of unused `BatchGroup`s is expected to be + // small. Pick a constant which is inferred from real programs. + constexpr uptr MaxUnusedSize = 8; + CompactPtrT Blocks[MaxUnusedSize]; + u32 Idx = 0; + RegionInfo *BatchClassRegion = getRegionInfo(SizeClassMap::BatchClassId); + // We can't call pushBatchClassBlocks() to recycle the unused `BatchGroup`s + // when we are manipulating the freelist of `BatchClassRegion`. Instead, we + // should just push it back to the freelist when we merge two `BatchGroup`s. + // This logic hasn't been implemented because we haven't supported releasing + // pages in `BatchClassRegion`. + DCHECK_NE(BatchClassRegion, Region); + + // Merge GroupsToRelease back to the Region::FreeListInfo.BlockList. Note + // that both `Region->FreeListInfo.BlockList` and `GroupsToRelease` are + // sorted. + for (BatchGroup *BG = Region->FreeListInfo.BlockList.front(), + *Prev = nullptr; + ;) { + if (BG == nullptr || GroupsToRelease.empty()) { + if (!GroupsToRelease.empty()) + Region->FreeListInfo.BlockList.append_back(&GroupsToRelease); + break; + } + + DCHECK(!BG->Batches.empty()); + + if (BG->CompactPtrGroupBase < + GroupsToRelease.front()->CompactPtrGroupBase) { + Prev = BG; + BG = BG->Next; continue; } - BG.PushedBlocksAtLastCheckpoint = BG.PushedBlocks; - // Note that we don't always visit blocks in each BatchGroup so that we - // may miss the chance of releasing certain pages that cross BatchGroups. - Context.markFreeBlocks(BG.Batches, DecompactPtr, Region->RegionBeg); - } + BatchGroup *Cur = GroupsToRelease.front(); + TransferBatch *UnusedTransferBatch = nullptr; + GroupsToRelease.pop_front(); + + if (BG->CompactPtrGroupBase == Cur->CompactPtrGroupBase) { + BG->PushedBlocks += Cur->PushedBlocks; + // We have updated `BatchGroup::BytesInBGAtLastCheckpoint` while + // collecting the `GroupsToRelease`. + BG->BytesInBGAtLastCheckpoint = Cur->BytesInBGAtLastCheckpoint; + const uptr MaxCachedPerBatch = BG->MaxCachedPerBatch; + + // Note that the first TransferBatches in both `Batches` may not be + // full and only the first TransferBatch can have non-full blocks. Thus + // we have to merge them before appending one to another. + if (Cur->Batches.front()->getCount() == MaxCachedPerBatch) { + BG->Batches.append_back(&Cur->Batches); + } else { + TransferBatch *NonFullBatch = Cur->Batches.front(); + Cur->Batches.pop_front(); + const u16 NonFullBatchCount = NonFullBatch->getCount(); + // The remaining Batches in `Cur` are full. + BG->Batches.append_back(&Cur->Batches); + + if (BG->Batches.front()->getCount() == MaxCachedPerBatch) { + // Only 1 non-full TransferBatch, push it to the front. + BG->Batches.push_front(NonFullBatch); + } else { + const u16 NumBlocksToMove = static_cast<u16>( + Min(static_cast<u16>(MaxCachedPerBatch - + BG->Batches.front()->getCount()), + NonFullBatchCount)); + BG->Batches.front()->appendFromTransferBatch(NonFullBatch, + NumBlocksToMove); + if (NonFullBatch->isEmpty()) + UnusedTransferBatch = NonFullBatch; + else + BG->Batches.push_front(NonFullBatch); + } + } - if (!Context.hasBlockMarked()) - return 0; + const u32 NeededSlots = UnusedTransferBatch == nullptr ? 1U : 2U; + if (UNLIKELY(Idx + NeededSlots > MaxUnusedSize)) { + ScopedLock L(BatchClassRegion->FLLock); + pushBatchClassBlocks(BatchClassRegion, Blocks, Idx); + Idx = 0; + } + Blocks[Idx++] = + compactPtr(SizeClassMap::BatchClassId, reinterpret_cast<uptr>(Cur)); + if (UnusedTransferBatch) { + Blocks[Idx++] = + compactPtr(SizeClassMap::BatchClassId, + reinterpret_cast<uptr>(UnusedTransferBatch)); + } + Prev = BG; + BG = BG->Next; + continue; + } + + // At here, the `BG` is the first BatchGroup with CompactPtrGroupBase + // larger than the first element in `GroupsToRelease`. We need to insert + // `GroupsToRelease::front()` (which is `Cur` below) before `BG`. + // + // 1. If `Prev` is nullptr, we simply push `Cur` to the front of + // FreeListInfo.BlockList. + // 2. Otherwise, use `insert()` which inserts an element next to `Prev`. + // + // Afterwards, we don't need to advance `BG` because the order between + // `BG` and the new `GroupsToRelease::front()` hasn't been checked. + if (Prev == nullptr) + Region->FreeListInfo.BlockList.push_front(Cur); + else + Region->FreeListInfo.BlockList.insert(Prev, Cur); + DCHECK_EQ(Cur->Next, BG); + Prev = Cur; + } - auto SkipRegion = [](UNUSED uptr RegionIndex) { return false; }; - releaseFreeMemoryToOS(Context, Recorder, SkipRegion); + if (Idx != 0) { + ScopedLock L(BatchClassRegion->FLLock); + pushBatchClassBlocks(BatchClassRegion, Blocks, Idx); + } - if (Recorder.getReleasedRangesCount() > 0) { - Region->ReleaseInfo.PushedBlocksAtLastRelease = - Region->Stats.PushedBlocks; - Region->ReleaseInfo.RangesReleased += Recorder.getReleasedRangesCount(); - Region->ReleaseInfo.LastReleasedBytes = Recorder.getReleasedBytes(); + if (SCUDO_DEBUG) { + BatchGroup *Prev = Region->FreeListInfo.BlockList.front(); + for (BatchGroup *Cur = Prev->Next; Cur != nullptr; + Prev = Cur, Cur = Cur->Next) { + CHECK_LT(Prev->CompactPtrGroupBase, Cur->CompactPtrGroupBase); + } } - Region->ReleaseInfo.LastReleaseAtNs = getMonotonicTime(); - return Recorder.getReleasedBytes(); } + + // TODO: `PrimaryBase` can be obtained from ReservedMemory. This needs to be + // deprecated. + uptr PrimaryBase = 0; + ReservedMemoryT ReservedMemory = {}; + // The minimum size of pushed blocks that we will try to release the pages in + // that size class. + uptr SmallerBlockReleasePageDelta = 0; + atomic_s32 ReleaseToOsIntervalMs = {}; + alignas(SCUDO_CACHE_LINE_SIZE) RegionInfo RegionInfoArray[NumClasses]; }; } // namespace scudo diff --git a/contrib/llvm-project/compiler-rt/lib/scudo/standalone/quarantine.h b/contrib/llvm-project/compiler-rt/lib/scudo/standalone/quarantine.h index 2d231c3a28db..b5f8db0e87c2 100644 --- a/contrib/llvm-project/compiler-rt/lib/scudo/standalone/quarantine.h +++ b/contrib/llvm-project/compiler-rt/lib/scudo/standalone/quarantine.h @@ -12,6 +12,7 @@ #include "list.h" #include "mutex.h" #include "string_utils.h" +#include "thread_annotations.h" namespace scudo { @@ -172,7 +173,7 @@ public: typedef QuarantineCache<Callback> CacheT; using ThisT = GlobalQuarantine<Callback, Node>; - void init(uptr Size, uptr CacheSize) { + void init(uptr Size, uptr CacheSize) NO_THREAD_SAFETY_ANALYSIS { DCHECK(isAligned(reinterpret_cast<uptr>(this), alignof(ThisT))); DCHECK_EQ(atomic_load_relaxed(&MaxSize), 0U); DCHECK_EQ(atomic_load_relaxed(&MinSize), 0U); @@ -191,22 +192,31 @@ public: uptr getMaxSize() const { return atomic_load_relaxed(&MaxSize); } uptr getCacheSize() const { return atomic_load_relaxed(&MaxCacheSize); } + // This is supposed to be used in test only. + bool isEmpty() { + ScopedLock L(CacheMutex); + return Cache.getSize() == 0U; + } + void put(CacheT *C, Callback Cb, Node *Ptr, uptr Size) { C->enqueue(Cb, Ptr, Size); if (C->getSize() > getCacheSize()) drain(C, Cb); } - void NOINLINE drain(CacheT *C, Callback Cb) { + void NOINLINE drain(CacheT *C, Callback Cb) EXCLUDES(CacheMutex) { + bool needRecycle = false; { ScopedLock L(CacheMutex); Cache.transfer(C); + needRecycle = Cache.getSize() > getMaxSize(); } - if (Cache.getSize() > getMaxSize() && RecycleMutex.tryLock()) + + if (needRecycle && RecycleMutex.tryLock()) recycle(atomic_load_relaxed(&MinSize), Cb); } - void NOINLINE drainAndRecycle(CacheT *C, Callback Cb) { + void NOINLINE drainAndRecycle(CacheT *C, Callback Cb) EXCLUDES(CacheMutex) { { ScopedLock L(CacheMutex); Cache.transfer(C); @@ -215,20 +225,21 @@ public: recycle(0, Cb); } - void getStats(ScopedString *Str) const { + void getStats(ScopedString *Str) EXCLUDES(CacheMutex) { + ScopedLock L(CacheMutex); // It assumes that the world is stopped, just as the allocator's printStats. Cache.getStats(Str); Str->append("Quarantine limits: global: %zuK; thread local: %zuK\n", getMaxSize() >> 10, getCacheSize() >> 10); } - void disable() { + void disable() NO_THREAD_SAFETY_ANALYSIS { // RecycleMutex must be locked 1st since we grab CacheMutex within recycle. RecycleMutex.lock(); CacheMutex.lock(); } - void enable() { + void enable() NO_THREAD_SAFETY_ANALYSIS { CacheMutex.unlock(); RecycleMutex.unlock(); } @@ -236,13 +247,14 @@ public: private: // Read-only data. alignas(SCUDO_CACHE_LINE_SIZE) HybridMutex CacheMutex; - CacheT Cache; + CacheT Cache GUARDED_BY(CacheMutex); alignas(SCUDO_CACHE_LINE_SIZE) HybridMutex RecycleMutex; atomic_uptr MinSize = {}; atomic_uptr MaxSize = {}; alignas(SCUDO_CACHE_LINE_SIZE) atomic_uptr MaxCacheSize = {}; - void NOINLINE recycle(uptr MinSize, Callback Cb) { + void NOINLINE recycle(uptr MinSize, Callback Cb) RELEASE(RecycleMutex) + EXCLUDES(CacheMutex) { CacheT Tmp; Tmp.init(); { diff --git a/contrib/llvm-project/compiler-rt/lib/scudo/standalone/release.cpp b/contrib/llvm-project/compiler-rt/lib/scudo/standalone/release.cpp index 3f40dbec6d7a..938bb41faf69 100644 --- a/contrib/llvm-project/compiler-rt/lib/scudo/standalone/release.cpp +++ b/contrib/llvm-project/compiler-rt/lib/scudo/standalone/release.cpp @@ -10,7 +10,7 @@ namespace scudo { -HybridMutex RegionPageMap::Mutex = {}; -uptr RegionPageMap::StaticBuffer[RegionPageMap::StaticBufferCount]; +BufferPool<RegionPageMap::StaticBufferCount, RegionPageMap::StaticBufferSize> + RegionPageMap::Buffers; } // namespace scudo diff --git a/contrib/llvm-project/compiler-rt/lib/scudo/standalone/release.h b/contrib/llvm-project/compiler-rt/lib/scudo/standalone/release.h index 6de3b15534d0..5bf963d0f26f 100644 --- a/contrib/llvm-project/compiler-rt/lib/scudo/standalone/release.h +++ b/contrib/llvm-project/compiler-rt/lib/scudo/standalone/release.h @@ -11,14 +11,46 @@ #include "common.h" #include "list.h" +#include "mem_map.h" #include "mutex.h" +#include "thread_annotations.h" namespace scudo { +template <typename MemMapT> class RegionReleaseRecorder { +public: + RegionReleaseRecorder(MemMapT *RegionMemMap, uptr Base, uptr Offset = 0) + : RegionMemMap(RegionMemMap), Base(Base), Offset(Offset) {} + + uptr getReleasedRangesCount() const { return ReleasedRangesCount; } + + uptr getReleasedBytes() const { return ReleasedBytes; } + + uptr getBase() const { return Base; } + + // Releases [From, To) range of pages back to OS. Note that `From` and `To` + // are offseted from `Base` + Offset. + void releasePageRangeToOS(uptr From, uptr To) { + const uptr Size = To - From; + RegionMemMap->releasePagesToOS(getBase() + Offset + From, Size); + ReleasedRangesCount++; + ReleasedBytes += Size; + } + +private: + uptr ReleasedRangesCount = 0; + uptr ReleasedBytes = 0; + MemMapT *RegionMemMap = nullptr; + uptr Base = 0; + // The release offset from Base. This is used when we know a given range after + // Base will not be released. + uptr Offset = 0; +}; + class ReleaseRecorder { public: - ReleaseRecorder(uptr Base, MapPlatformData *Data = nullptr) - : Base(Base), Data(Data) {} + ReleaseRecorder(uptr Base, uptr Offset = 0, MapPlatformData *Data = nullptr) + : Base(Base), Offset(Offset), Data(Data) {} uptr getReleasedRangesCount() const { return ReleasedRangesCount; } @@ -29,7 +61,7 @@ public: // Releases [From, To) range of pages back to OS. void releasePageRangeToOS(uptr From, uptr To) { const uptr Size = To - From; - releasePagesToOS(Base, From, Size, Data); + releasePagesToOS(Base, From + Offset, Size, Data); ReleasedRangesCount++; ReleasedBytes += Size; } @@ -37,10 +69,110 @@ public: private: uptr ReleasedRangesCount = 0; uptr ReleasedBytes = 0; + // The starting address to release. Note that we may want to combine (Base + + // Offset) as a new Base. However, the Base is retrieved from + // `MapPlatformData` on Fuchsia, which means the offset won't be aware. + // Therefore, store them separately to make it work on all the platforms. uptr Base = 0; + // The release offset from Base. This is used when we know a given range after + // Base will not be released. + uptr Offset = 0; MapPlatformData *Data = nullptr; }; +// A buffer pool which holds a fixed number of static buffers for fast buffer +// allocation. If the request size is greater than `StaticBufferSize`, it'll +// delegate the allocation to map(). +template <uptr StaticBufferCount, uptr StaticBufferSize> class BufferPool { +public: + // Preserve 1 bit in the `Mask` so that we don't need to do zero-check while + // extracting the least significant bit from the `Mask`. + static_assert(StaticBufferCount < SCUDO_WORDSIZE, ""); + static_assert(isAligned(StaticBufferSize, SCUDO_CACHE_LINE_SIZE), ""); + + // Return a buffer which is at least `BufferSize`. + uptr *getBuffer(const uptr BufferSize) { + if (UNLIKELY(BufferSize > StaticBufferSize)) + return getDynamicBuffer(BufferSize); + + uptr index; + { + // TODO: In general, we expect this operation should be fast so the + // waiting thread won't be put into sleep. The HybridMutex does implement + // the busy-waiting but we may want to review the performance and see if + // we need an explict spin lock here. + ScopedLock L(Mutex); + index = getLeastSignificantSetBitIndex(Mask); + if (index < StaticBufferCount) + Mask ^= static_cast<uptr>(1) << index; + } + + if (index >= StaticBufferCount) + return getDynamicBuffer(BufferSize); + + const uptr Offset = index * StaticBufferSize; + memset(&RawBuffer[Offset], 0, StaticBufferSize); + return &RawBuffer[Offset]; + } + + void releaseBuffer(uptr *Buffer, const uptr BufferSize) { + const uptr index = getStaticBufferIndex(Buffer, BufferSize); + if (index < StaticBufferCount) { + ScopedLock L(Mutex); + DCHECK_EQ((Mask & (static_cast<uptr>(1) << index)), 0U); + Mask |= static_cast<uptr>(1) << index; + } else { + unmap(reinterpret_cast<void *>(Buffer), + roundUp(BufferSize, getPageSizeCached())); + } + } + + bool isStaticBufferTestOnly(uptr *Buffer, uptr BufferSize) { + return getStaticBufferIndex(Buffer, BufferSize) < StaticBufferCount; + } + +private: + uptr getStaticBufferIndex(uptr *Buffer, uptr BufferSize) { + if (UNLIKELY(BufferSize > StaticBufferSize)) + return StaticBufferCount; + + const uptr BufferBase = reinterpret_cast<uptr>(Buffer); + const uptr RawBufferBase = reinterpret_cast<uptr>(RawBuffer); + + if (BufferBase < RawBufferBase || + BufferBase >= RawBufferBase + sizeof(RawBuffer)) { + return StaticBufferCount; + } + + DCHECK_LE(BufferSize, StaticBufferSize); + DCHECK_LE(BufferBase + BufferSize, RawBufferBase + sizeof(RawBuffer)); + DCHECK_EQ((BufferBase - RawBufferBase) % StaticBufferSize, 0U); + + const uptr index = + (BufferBase - RawBufferBase) / (StaticBufferSize * sizeof(uptr)); + DCHECK_LT(index, StaticBufferCount); + return index; + } + + uptr *getDynamicBuffer(const uptr BufferSize) { + // When using a heap-based buffer, precommit the pages backing the + // Vmar by passing |MAP_PRECOMMIT| flag. This allows an optimization + // where page fault exceptions are skipped as the allocated memory + // is accessed. So far, this is only enabled on Fuchsia. It hasn't proven a + // performance benefit on other platforms. + const uptr MmapFlags = MAP_ALLOWNOMEM | (SCUDO_FUCHSIA ? MAP_PRECOMMIT : 0); + return reinterpret_cast<uptr *>( + map(nullptr, roundUp(BufferSize, getPageSizeCached()), "scudo:counters", + MmapFlags, &MapData)); + } + + HybridMutex Mutex; + // '1' means that buffer index is not used. '0' means the buffer is in use. + uptr Mask GUARDED_BY(Mutex) = ~static_cast<uptr>(0); + uptr RawBuffer[StaticBufferCount * StaticBufferSize] GUARDED_BY(Mutex); + [[no_unique_address]] MapPlatformData MapData = {}; +}; + // A Region page map is used to record the usage of pages in the regions. It // implements a packed array of Counters. Each counter occupies 2^N bits, enough // to store counter's MaxValue. Ctor will try to use a static buffer first, and @@ -68,14 +200,14 @@ public: ~RegionPageMap() { if (!isAllocated()) return; - if (Buffer == &StaticBuffer[0]) - Mutex.unlock(); - else - unmap(reinterpret_cast<void *>(Buffer), - roundUpTo(BufferSize, getPageSizeCached())); + Buffers.releaseBuffer(Buffer, BufferSize); Buffer = nullptr; } + // Lock of `StaticBuffer` is acquired conditionally and there's no easy way to + // specify the thread-safety attribute properly in current code structure. + // Besides, it's the only place we may want to check thread safety. Therefore, + // it's fine to bypass the thread-safety analysis now. void reset(uptr NumberOfRegion, uptr CountersPerRegion, uptr MaxValue) { DCHECK_GT(NumberOfRegion, 0); DCHECK_GT(CountersPerRegion, 0); @@ -88,7 +220,7 @@ public: // Rounding counter storage size up to the power of two allows for using // bit shifts calculating particular counter's Index and offset. const uptr CounterSizeBits = - roundUpToPowerOfTwo(getMostSignificantSetBitIndex(MaxValue) + 1); + roundUpPowerOfTwo(getMostSignificantSetBitIndex(MaxValue) + 1); DCHECK_LE(CounterSizeBits, MaxCounterBits); CounterSizeBitsLog = getLog2(CounterSizeBits); CounterMask = ~(static_cast<uptr>(0)) >> (MaxCounterBits - CounterSizeBits); @@ -99,24 +231,10 @@ public: BitOffsetMask = PackingRatio - 1; SizePerRegion = - roundUpTo(NumCounters, static_cast<uptr>(1U) << PackingRatioLog) >> + roundUp(NumCounters, static_cast<uptr>(1U) << PackingRatioLog) >> PackingRatioLog; BufferSize = SizePerRegion * sizeof(*Buffer) * Regions; - if (BufferSize <= (StaticBufferCount * sizeof(Buffer[0])) && - Mutex.tryLock()) { - Buffer = &StaticBuffer[0]; - memset(Buffer, 0, BufferSize); - } else { - // When using a heap-based buffer, precommit the pages backing the - // Vmar by passing |MAP_PRECOMMIT| flag. This allows an optimization - // where page fault exceptions are skipped as the allocated memory - // is accessed. - const uptr MmapFlags = - MAP_ALLOWNOMEM | (SCUDO_FUCHSIA ? MAP_PRECOMMIT : 0); - Buffer = reinterpret_cast<uptr *>( - map(nullptr, roundUpTo(BufferSize, getPageSizeCached()), - "scudo:counters", MmapFlags, &MapData)); - } + Buffer = Buffers.getBuffer(BufferSize); } bool isAllocated() const { return !!Buffer; } @@ -141,6 +259,17 @@ public: << BitOffset; } + void incN(uptr Region, uptr I, uptr N) const { + DCHECK_GT(N, 0U); + DCHECK_LE(N, CounterMask); + DCHECK_LE(get(Region, I), CounterMask - N); + const uptr Index = I >> PackingRatioLog; + const uptr BitOffset = (I & BitOffsetMask) << CounterSizeBitsLog; + DCHECK_LT(BitOffset, SCUDO_WORDSIZE); + DCHECK_EQ(isAllCounted(Region, I), false); + Buffer[Region * SizePerRegion + Index] += N << BitOffset; + } + void incRange(uptr Region, uptr From, uptr To) const { DCHECK_LE(From, To); const uptr Top = Min(To + 1, NumCounters); @@ -159,14 +288,29 @@ public: DCHECK_LT(BitOffset, SCUDO_WORDSIZE); Buffer[Region * SizePerRegion + Index] |= CounterMask << BitOffset; } + void setAsAllCountedRange(uptr Region, uptr From, uptr To) const { + DCHECK_LE(From, To); + const uptr Top = Min(To + 1, NumCounters); + for (uptr I = From; I < Top; I++) + setAsAllCounted(Region, I); + } + + bool updateAsAllCountedIf(uptr Region, uptr I, uptr MaxCount) { + const uptr Count = get(Region, I); + if (Count == CounterMask) + return true; + if (Count == MaxCount) { + setAsAllCounted(Region, I); + return true; + } + return false; + } bool isAllCounted(uptr Region, uptr I) const { return get(Region, I) == CounterMask; } uptr getBufferSize() const { return BufferSize; } - static const uptr StaticBufferCount = 2048U; - private: uptr Regions; uptr NumCounters; @@ -178,10 +322,12 @@ private: uptr SizePerRegion; uptr BufferSize; uptr *Buffer; - [[no_unique_address]] MapPlatformData MapData = {}; - static HybridMutex Mutex; - static uptr StaticBuffer[StaticBufferCount]; + // We may consider making this configurable if there are cases which may + // benefit from this. + static const uptr StaticBufferCount = 2U; + static const uptr StaticBufferSize = 512U; + static BufferPool<StaticBufferCount, StaticBufferSize> Buffers; }; template <class ReleaseRecorderT> class FreePagesRangeTracker { @@ -225,10 +371,9 @@ private: }; struct PageReleaseContext { - PageReleaseContext(uptr BlockSize, uptr RegionSize, uptr NumberOfRegions) : - BlockSize(BlockSize), - RegionSize(RegionSize), - NumberOfRegions(NumberOfRegions) { + PageReleaseContext(uptr BlockSize, uptr NumberOfRegions, uptr ReleaseSize, + uptr ReleaseOffset = 0) + : BlockSize(BlockSize), NumberOfRegions(NumberOfRegions) { PageSize = getPageSizeCached(); if (BlockSize <= PageSize) { if (PageSize % BlockSize == 0) { @@ -260,10 +405,16 @@ struct PageReleaseContext { } } - PagesCount = roundUpTo(RegionSize, PageSize) / PageSize; + // TODO: For multiple regions, it's more complicated to support partial + // region marking (which includes the complexity of how to handle the last + // block in a region). We may consider this after markFreeBlocks() accepts + // only free blocks from the same region. + if (NumberOfRegions != 1) + DCHECK_EQ(ReleaseOffset, 0U); + + PagesCount = roundUp(ReleaseSize, PageSize) / PageSize; PageSizeLog = getLog2(PageSize); - RoundedRegionSize = PagesCount << PageSizeLog; - RoundedSize = NumberOfRegions * RoundedRegionSize; + ReleasePageOffset = ReleaseOffset >> PageSizeLog; } // PageMap is lazily allocated when markFreeBlocks() is invoked. @@ -271,17 +422,147 @@ struct PageReleaseContext { return PageMap.isAllocated(); } - void ensurePageMapAllocated() { + bool ensurePageMapAllocated() { if (PageMap.isAllocated()) - return; + return true; PageMap.reset(NumberOfRegions, PagesCount, FullPagesBlockCountMax); - DCHECK(PageMap.isAllocated()); + // TODO: Log some message when we fail on PageMap allocation. + return PageMap.isAllocated(); } - template<class TransferBatchT, typename DecompactPtrT> - void markFreeBlocks(const IntrusiveList<TransferBatchT> &FreeList, - DecompactPtrT DecompactPtr, uptr Base) { - ensurePageMapAllocated(); + // Mark all the blocks in the given range [From, to). Instead of visiting all + // the blocks, we will just mark the page as all counted. Note the `From` and + // `To` has to be page aligned but with one exception, if `To` is equal to the + // RegionSize, it's not necessary to be aligned with page size. + bool markRangeAsAllCounted(uptr From, uptr To, uptr Base, + const uptr RegionIndex, const uptr RegionSize) { + DCHECK_LT(From, To); + DCHECK_LE(To, Base + RegionSize); + DCHECK_EQ(From % PageSize, 0U); + DCHECK_LE(To - From, RegionSize); + + if (!ensurePageMapAllocated()) + return false; + + uptr FromInRegion = From - Base; + uptr ToInRegion = To - Base; + uptr FirstBlockInRange = roundUpSlow(FromInRegion, BlockSize); + + // The straddling block sits across entire range. + if (FirstBlockInRange >= ToInRegion) + return true; + + // First block may not sit at the first pape in the range, move + // `FromInRegion` to the first block page. + FromInRegion = roundDown(FirstBlockInRange, PageSize); + + // When The first block is not aligned to the range boundary, which means + // there is a block sitting acorss `From`, that looks like, + // + // From To + // V V + // +-----------------------------------------------+ + // +-----+-----+-----+-----+ + // | | | | | ... + // +-----+-----+-----+-----+ + // |- first page -||- second page -||- ... + // + // Therefore, we can't just mark the first page as all counted. Instead, we + // increment the number of blocks in the first page in the page map and + // then round up the `From` to the next page. + if (FirstBlockInRange != FromInRegion) { + DCHECK_GT(FromInRegion + PageSize, FirstBlockInRange); + uptr NumBlocksInFirstPage = + (FromInRegion + PageSize - FirstBlockInRange + BlockSize - 1) / + BlockSize; + PageMap.incN(RegionIndex, getPageIndex(FromInRegion), + NumBlocksInFirstPage); + FromInRegion = roundUp(FromInRegion + 1, PageSize); + } + + uptr LastBlockInRange = roundDownSlow(ToInRegion - 1, BlockSize); + + // Note that LastBlockInRange may be smaller than `FromInRegion` at this + // point because it may contain only one block in the range. + + // When the last block sits across `To`, we can't just mark the pages + // occupied by the last block as all counted. Instead, we increment the + // counters of those pages by 1. The exception is that if it's the last + // block in the region, it's fine to mark those pages as all counted. + if (LastBlockInRange + BlockSize != RegionSize) { + DCHECK_EQ(ToInRegion % PageSize, 0U); + // The case below is like, + // + // From To + // V V + // +----------------------------------------+ + // +-----+-----+-----+-----+ + // | | | | | ... + // +-----+-----+-----+-----+ + // ... -||- last page -||- next page -| + // + // The last block is not aligned to `To`, we need to increment the + // counter of `next page` by 1. + if (LastBlockInRange + BlockSize != ToInRegion) { + PageMap.incRange(RegionIndex, getPageIndex(ToInRegion), + getPageIndex(LastBlockInRange + BlockSize - 1)); + } + } else { + ToInRegion = RegionSize; + } + + // After handling the first page and the last block, it's safe to mark any + // page in between the range [From, To). + if (FromInRegion < ToInRegion) { + PageMap.setAsAllCountedRange(RegionIndex, getPageIndex(FromInRegion), + getPageIndex(ToInRegion - 1)); + } + + return true; + } + + template <class TransferBatchT, typename DecompactPtrT> + bool markFreeBlocksInRegion(const IntrusiveList<TransferBatchT> &FreeList, + DecompactPtrT DecompactPtr, const uptr Base, + const uptr RegionIndex, const uptr RegionSize, + bool MayContainLastBlockInRegion) { + if (!ensurePageMapAllocated()) + return false; + + if (MayContainLastBlockInRegion) { + const uptr LastBlockInRegion = + ((RegionSize / BlockSize) - 1U) * BlockSize; + // The last block in a region may not use the entire page, we mark the + // following "pretend" memory block(s) as free in advance. + // + // Region Boundary + // v + // -----+-----------------------+ + // | Last Page | <- Rounded Region Boundary + // -----+-----------------------+ + // |-----||- trailing blocks -| + // ^ + // last block + const uptr RoundedRegionSize = roundUp(RegionSize, PageSize); + const uptr TrailingBlockBase = LastBlockInRegion + BlockSize; + // If the difference between `RoundedRegionSize` and + // `TrailingBlockBase` is larger than a page, that implies the reported + // `RegionSize` may not be accurate. + DCHECK_LT(RoundedRegionSize - TrailingBlockBase, PageSize); + + // Only the last page touched by the last block needs to mark the trailing + // blocks. Note that if the last "pretend" block straddles the boundary, + // we still have to count it in so that the logic of counting the number + // of blocks on a page is consistent. + uptr NumTrailingBlocks = + (roundUpSlow(RoundedRegionSize - TrailingBlockBase, BlockSize) + + BlockSize - 1) / + BlockSize; + if (NumTrailingBlocks > 0) { + PageMap.incN(RegionIndex, getPageIndex(TrailingBlockBase), + NumTrailingBlocks); + } + } // Iterate over free chunks and count how many free chunks affect each // allocated page. @@ -289,51 +570,37 @@ struct PageReleaseContext { // Each chunk affects one page only. for (const auto &It : FreeList) { for (u16 I = 0; I < It.getCount(); I++) { - const uptr P = DecompactPtr(It.get(I)) - Base; - if (P >= RoundedSize) - continue; - const uptr RegionIndex = NumberOfRegions == 1U ? 0 : P / RegionSize; - const uptr PInRegion = P - RegionIndex * RegionSize; - PageMap.inc(RegionIndex, PInRegion >> PageSizeLog); + const uptr PInRegion = DecompactPtr(It.get(I)) - Base; + DCHECK_LT(PInRegion, RegionSize); + PageMap.inc(RegionIndex, getPageIndex(PInRegion)); } } } else { // In all other cases chunks might affect more than one page. DCHECK_GE(RegionSize, BlockSize); - const uptr LastBlockInRegion = - ((RegionSize / BlockSize) - 1U) * BlockSize; for (const auto &It : FreeList) { for (u16 I = 0; I < It.getCount(); I++) { - const uptr P = DecompactPtr(It.get(I)) - Base; - if (P >= RoundedSize) - continue; - const uptr RegionIndex = NumberOfRegions == 1U ? 0 : P / RegionSize; - uptr PInRegion = P - RegionIndex * RegionSize; - PageMap.incRange(RegionIndex, PInRegion >> PageSizeLog, - (PInRegion + BlockSize - 1) >> PageSizeLog); - // The last block in a region might straddle a page, so if it's - // free, we mark the following "pretend" memory block(s) as free. - if (PInRegion == LastBlockInRegion) { - PInRegion += BlockSize; - while (PInRegion < RoundedRegionSize) { - PageMap.incRange(RegionIndex, PInRegion >> PageSizeLog, - (PInRegion + BlockSize - 1) >> PageSizeLog); - PInRegion += BlockSize; - } - } + const uptr PInRegion = DecompactPtr(It.get(I)) - Base; + PageMap.incRange(RegionIndex, getPageIndex(PInRegion), + getPageIndex(PInRegion + BlockSize - 1)); } } } + + return true; } + uptr getPageIndex(uptr P) { return (P >> PageSizeLog) - ReleasePageOffset; } + uptr getReleaseOffset() { return ReleasePageOffset << PageSizeLog; } + uptr BlockSize; - uptr RegionSize; uptr NumberOfRegions; + // For partial region marking, some pages in front are not needed to be + // counted. + uptr ReleasePageOffset; uptr PageSize; uptr PagesCount; uptr PageSizeLog; - uptr RoundedRegionSize; - uptr RoundedSize; uptr FullPagesBlockCountMax; bool SameBlockCountPerPage; RegionPageMap PageMap; @@ -350,6 +617,7 @@ releaseFreeMemoryToOS(PageReleaseContext &Context, const uptr BlockSize = Context.BlockSize; const uptr PagesCount = Context.PagesCount; const uptr NumberOfRegions = Context.NumberOfRegions; + const uptr ReleasePageOffset = Context.ReleasePageOffset; const uptr FullPagesBlockCountMax = Context.FullPagesBlockCountMax; const bool SameBlockCountPerPage = Context.SameBlockCountPerPage; RegionPageMap &PageMap = Context.PageMap; @@ -365,9 +633,8 @@ releaseFreeMemoryToOS(PageReleaseContext &Context, continue; } for (uptr J = 0; J < PagesCount; J++) { - const bool CanRelease = PageMap.get(I, J) == FullPagesBlockCountMax; - if (CanRelease) - PageMap.setAsAllCounted(I, J); + const bool CanRelease = + PageMap.updateAsAllCountedIf(I, J, FullPagesBlockCountMax); RangeTracker.processNextPage(CanRelease); } } @@ -388,6 +655,10 @@ releaseFreeMemoryToOS(PageReleaseContext &Context, } uptr PrevPageBoundary = 0; uptr CurrentBoundary = 0; + if (ReleasePageOffset > 0) { + PrevPageBoundary = ReleasePageOffset * PageSize; + CurrentBoundary = roundUpSlow(PrevPageBoundary, BlockSize); + } for (uptr J = 0; J < PagesCount; J++) { const uptr PageBoundary = PrevPageBoundary + PageSize; uptr BlocksPerPage = Pn; @@ -401,9 +672,8 @@ releaseFreeMemoryToOS(PageReleaseContext &Context, } } PrevPageBoundary = PageBoundary; - const bool CanRelease = PageMap.get(I, J) == BlocksPerPage; - if (CanRelease) - PageMap.setAsAllCounted(I, J); + const bool CanRelease = + PageMap.updateAsAllCountedIf(I, J, BlocksPerPage); RangeTracker.processNextPage(CanRelease); } } @@ -411,20 +681,6 @@ releaseFreeMemoryToOS(PageReleaseContext &Context, RangeTracker.finish(); } -// An overload releaseFreeMemoryToOS which doesn't require the page usage -// information after releasing. -template <class TransferBatchT, class ReleaseRecorderT, typename DecompactPtrT, - typename SkipRegionT> -NOINLINE void -releaseFreeMemoryToOS(const IntrusiveList<TransferBatchT> &FreeList, - uptr RegionSize, uptr NumberOfRegions, uptr BlockSize, - ReleaseRecorderT &Recorder, DecompactPtrT DecompactPtr, - SkipRegionT SkipRegion) { - PageReleaseContext Context(BlockSize, RegionSize, NumberOfRegions); - Context.markFreeBlocks(FreeList, DecompactPtr, Recorder.getBase()); - releaseFreeMemoryToOS(Context, Recorder, SkipRegion); -} - } // namespace scudo #endif // SCUDO_RELEASE_H_ diff --git a/contrib/llvm-project/compiler-rt/lib/scudo/standalone/report.cpp b/contrib/llvm-project/compiler-rt/lib/scudo/standalone/report.cpp index a37faacbb932..81b3dce4e02c 100644 --- a/contrib/llvm-project/compiler-rt/lib/scudo/standalone/report.cpp +++ b/contrib/llvm-project/compiler-rt/lib/scudo/standalone/report.cpp @@ -21,7 +21,7 @@ public: void append(const char *Format, ...) { va_list Args; va_start(Args, Format); - Message.append(Format, Args); + Message.vappend(Format, Args); va_end(Args); } NORETURN ~ScopedErrorReport() { @@ -112,6 +112,11 @@ void NORETURN reportAllocationSizeTooBig(uptr UserSize, uptr TotalSize, UserSize, TotalSize, MaxSize); } +void NORETURN reportOutOfBatchClass() { + ScopedErrorReport Report; + Report.append("BatchClass region is used up, can't hold any free block\n"); +} + void NORETURN reportOutOfMemory(uptr RequestedSize) { ScopedErrorReport Report; Report.append("out of memory trying to allocate %zu bytes\n", RequestedSize); diff --git a/contrib/llvm-project/compiler-rt/lib/scudo/standalone/report.h b/contrib/llvm-project/compiler-rt/lib/scudo/standalone/report.h index d38451da0988..3a78ab64b13f 100644 --- a/contrib/llvm-project/compiler-rt/lib/scudo/standalone/report.h +++ b/contrib/llvm-project/compiler-rt/lib/scudo/standalone/report.h @@ -32,6 +32,7 @@ void NORETURN reportSanityCheckError(const char *Field); void NORETURN reportAlignmentTooBig(uptr Alignment, uptr MaxAlignment); void NORETURN reportAllocationSizeTooBig(uptr UserSize, uptr TotalSize, uptr MaxSize); +void NORETURN reportOutOfBatchClass(); void NORETURN reportOutOfMemory(uptr RequestedSize); void NORETURN reportSoftRSSLimit(uptr RssLimitMb); void NORETURN reportHardRSSLimit(uptr RssLimitMb); diff --git a/contrib/llvm-project/compiler-rt/lib/scudo/standalone/secondary.h b/contrib/llvm-project/compiler-rt/lib/scudo/standalone/secondary.h index 2d1775762588..105b154b5de2 100644 --- a/contrib/llvm-project/compiler-rt/lib/scudo/standalone/secondary.h +++ b/contrib/llvm-project/compiler-rt/lib/scudo/standalone/secondary.h @@ -12,11 +12,13 @@ #include "chunk.h" #include "common.h" #include "list.h" +#include "mem_map.h" #include "memtag.h" #include "mutex.h" #include "options.h" #include "stats.h" #include "string_utils.h" +#include "thread_annotations.h" namespace scudo { @@ -36,9 +38,7 @@ struct alignas(Max<uptr>(archSupportsMemoryTagging() LargeBlock::Header *Next; uptr CommitBase; uptr CommitSize; - uptr MapBase; - uptr MapSize; - [[no_unique_address]] MapPlatformData Data; + MemMapT MemMap; }; static_assert(sizeof(Header) % (1U << SCUDO_MIN_ALIGNMENT_LOG) == 0, ""); @@ -64,12 +64,15 @@ template <typename Config> static Header *getHeader(const void *Ptr) { } // namespace LargeBlock -static void unmap(LargeBlock::Header *H) { - MapPlatformData Data = H->Data; - unmap(reinterpret_cast<void *>(H->MapBase), H->MapSize, UNMAP_ALL, &Data); +static inline void unmap(LargeBlock::Header *H) { + // Note that the `H->MapMap` is stored on the pages managed by itself. Take + // over the ownership before unmap() so that any operation along with unmap() + // won't touch inaccessible pages. + MemMapT MemMap = H->MemMap; + MemMap.unmap(MemMap.getBase(), MemMap.getCapacity()); } -class MapAllocatorNoCache { +template <typename Config> class MapAllocatorNoCache { public: void init(UNUSED s32 ReleaseToOsInterval) {} bool retrieve(UNUSED Options Options, UNUSED uptr Size, UNUSED uptr Alignment, @@ -90,26 +93,29 @@ public: // Not supported by the Secondary Cache, but not an error either. return true; } + + void getStats(UNUSED ScopedString *Str) { + Str->append("Secondary Cache Disabled\n"); + } }; static const uptr MaxUnusedCachePages = 4U; template <typename Config> void mapSecondary(Options Options, uptr CommitBase, uptr CommitSize, - uptr AllocPos, uptr Flags, MapPlatformData *Data) { + uptr AllocPos, uptr Flags, MemMapT &MemMap) { const uptr MaxUnusedCacheBytes = MaxUnusedCachePages * getPageSizeCached(); if (useMemoryTagging<Config>(Options) && CommitSize > MaxUnusedCacheBytes) { const uptr UntaggedPos = Max(AllocPos, CommitBase + MaxUnusedCacheBytes); - map(reinterpret_cast<void *>(CommitBase), UntaggedPos - CommitBase, - "scudo:secondary", MAP_RESIZABLE | MAP_MEMTAG | Flags, Data); - map(reinterpret_cast<void *>(UntaggedPos), - CommitBase + CommitSize - UntaggedPos, "scudo:secondary", - MAP_RESIZABLE | Flags, Data); + MemMap.remap(CommitBase, UntaggedPos - CommitBase, "scudo:secondary", + MAP_RESIZABLE | MAP_MEMTAG | Flags); + MemMap.remap(UntaggedPos, CommitBase + CommitSize - UntaggedPos, + "scudo:secondary", MAP_RESIZABLE | Flags); } else { - map(reinterpret_cast<void *>(CommitBase), CommitSize, "scudo:secondary", + const uptr RemapFlags = MAP_RESIZABLE | (useMemoryTagging<Config>(Options) ? MAP_MEMTAG : 0) | - Flags, - Data); + Flags; + MemMap.remap(CommitBase, CommitSize, "scudo:secondary", RemapFlags); } } @@ -128,36 +134,52 @@ public: template <typename Config> class MapAllocatorCache { public: + using CacheConfig = typename Config::Secondary::Cache; + + void getStats(ScopedString *Str) { + ScopedLock L(Mutex); + Str->append("Stats: MapAllocatorCache: EntriesCount: %d, " + "MaxEntriesCount: %u, MaxEntrySize: %zu\n", + EntriesCount, atomic_load_relaxed(&MaxEntriesCount), + atomic_load_relaxed(&MaxEntrySize)); + for (CachedBlock Entry : Entries) { + if (!Entry.CommitBase) + continue; + Str->append("StartBlockAddress: 0x%zx, EndBlockAddress: 0x%zx, " + "BlockSize: %zu\n", + Entry.CommitBase, Entry.CommitBase + Entry.CommitSize, + Entry.CommitSize); + } + } + // Ensure the default maximum specified fits the array. - static_assert(Config::SecondaryCacheDefaultMaxEntriesCount <= - Config::SecondaryCacheEntriesArraySize, + static_assert(CacheConfig::DefaultMaxEntriesCount <= + CacheConfig::EntriesArraySize, ""); - void init(s32 ReleaseToOsInterval) { + void init(s32 ReleaseToOsInterval) NO_THREAD_SAFETY_ANALYSIS { DCHECK_EQ(EntriesCount, 0U); setOption(Option::MaxCacheEntriesCount, - static_cast<sptr>(Config::SecondaryCacheDefaultMaxEntriesCount)); + static_cast<sptr>(CacheConfig::DefaultMaxEntriesCount)); setOption(Option::MaxCacheEntrySize, - static_cast<sptr>(Config::SecondaryCacheDefaultMaxEntrySize)); + static_cast<sptr>(CacheConfig::DefaultMaxEntrySize)); setOption(Option::ReleaseInterval, static_cast<sptr>(ReleaseToOsInterval)); } - void store(Options Options, LargeBlock::Header *H) { + void store(Options Options, LargeBlock::Header *H) EXCLUDES(Mutex) { if (!canCache(H->CommitSize)) return unmap(H); bool EntryCached = false; bool EmptyCache = false; const s32 Interval = atomic_load_relaxed(&ReleaseToOsIntervalMs); - const u64 Time = getMonotonicTime(); + const u64 Time = getMonotonicTimeFast(); const u32 MaxCount = atomic_load_relaxed(&MaxEntriesCount); CachedBlock Entry; Entry.CommitBase = H->CommitBase; Entry.CommitSize = H->CommitSize; - Entry.MapBase = H->MapBase; - Entry.MapSize = H->MapSize; Entry.BlockBegin = reinterpret_cast<uptr>(H + 1); - Entry.Data = H->Data; + Entry.MemMap = H->MemMap; Entry.Time = Time; if (useMemoryTagging<Config>(Options)) { if (Interval == 0 && !SCUDO_FUCHSIA) { @@ -167,13 +189,13 @@ public: // on top so we just do the two syscalls there. Entry.Time = 0; mapSecondary<Config>(Options, Entry.CommitBase, Entry.CommitSize, - Entry.CommitBase, MAP_NOACCESS, &Entry.Data); + Entry.CommitBase, MAP_NOACCESS, Entry.MemMap); } else { - setMemoryPermission(Entry.CommitBase, Entry.CommitSize, MAP_NOACCESS, - &Entry.Data); + Entry.MemMap.setMemoryPermission(Entry.CommitBase, Entry.CommitSize, + MAP_NOACCESS); } } else if (Interval == 0) { - releasePagesToOS(Entry.CommitBase, 0, Entry.CommitSize, &Entry.Data); + Entry.MemMap.releasePagesToOS(Entry.CommitBase, Entry.CommitSize); Entry.Time = 0; } do { @@ -185,10 +207,9 @@ public: // just unmap it. break; } - if (Config::SecondaryCacheQuarantineSize && - useMemoryTagging<Config>(Options)) { + if (CacheConfig::QuarantineSize && useMemoryTagging<Config>(Options)) { QuarantinePos = - (QuarantinePos + 1) % Max(Config::SecondaryCacheQuarantineSize, 1u); + (QuarantinePos + 1) % Max(CacheConfig::QuarantineSize, 1u); if (!Quarantine[QuarantinePos].CommitBase) { Quarantine[QuarantinePos] = Entry; return; @@ -222,12 +243,11 @@ public: else if (Interval >= 0) releaseOlderThan(Time - static_cast<u64>(Interval) * 1000000); if (!EntryCached) - unmap(reinterpret_cast<void *>(Entry.MapBase), Entry.MapSize, UNMAP_ALL, - &Entry.Data); + Entry.MemMap.unmap(Entry.MemMap.getBase(), Entry.MemMap.getCapacity()); } bool retrieve(Options Options, uptr Size, uptr Alignment, - LargeBlock::Header **H, bool *Zeroed) { + LargeBlock::Header **H, bool *Zeroed) EXCLUDES(Mutex) { const uptr PageSize = getPageSizeCached(); const u32 MaxCount = atomic_load_relaxed(&MaxEntriesCount); bool Found = false; @@ -243,45 +263,46 @@ public: continue; const uptr CommitSize = Entries[I].CommitSize; const uptr AllocPos = - roundDownTo(CommitBase + CommitSize - Size, Alignment); + roundDown(CommitBase + CommitSize - Size, Alignment); HeaderPos = AllocPos - Chunk::getHeaderSize() - LargeBlock::getHeaderSize(); if (HeaderPos > CommitBase + CommitSize) continue; if (HeaderPos < CommitBase || - AllocPos > CommitBase + PageSize * MaxUnusedCachePages) + AllocPos > CommitBase + PageSize * MaxUnusedCachePages) { continue; + } Found = true; Entry = Entries[I]; Entries[I].CommitBase = 0; + EntriesCount--; break; } } - if (Found) { - *H = reinterpret_cast<LargeBlock::Header *>( - LargeBlock::addHeaderTag<Config>(HeaderPos)); - *Zeroed = Entry.Time == 0; - if (useMemoryTagging<Config>(Options)) - setMemoryPermission(Entry.CommitBase, Entry.CommitSize, 0, &Entry.Data); - uptr NewBlockBegin = reinterpret_cast<uptr>(*H + 1); - if (useMemoryTagging<Config>(Options)) { - if (*Zeroed) - storeTags(LargeBlock::addHeaderTag<Config>(Entry.CommitBase), - NewBlockBegin); - else if (Entry.BlockBegin < NewBlockBegin) - storeTags(Entry.BlockBegin, NewBlockBegin); - else - storeTags(untagPointer(NewBlockBegin), - untagPointer(Entry.BlockBegin)); + if (!Found) + return false; + + *H = reinterpret_cast<LargeBlock::Header *>( + LargeBlock::addHeaderTag<Config>(HeaderPos)); + *Zeroed = Entry.Time == 0; + if (useMemoryTagging<Config>(Options)) + Entry.MemMap.setMemoryPermission(Entry.CommitBase, Entry.CommitSize, 0); + uptr NewBlockBegin = reinterpret_cast<uptr>(*H + 1); + if (useMemoryTagging<Config>(Options)) { + if (*Zeroed) { + storeTags(LargeBlock::addHeaderTag<Config>(Entry.CommitBase), + NewBlockBegin); + } else if (Entry.BlockBegin < NewBlockBegin) { + storeTags(Entry.BlockBegin, NewBlockBegin); + } else { + storeTags(untagPointer(NewBlockBegin), + untagPointer(Entry.BlockBegin)); } - (*H)->CommitBase = Entry.CommitBase; - (*H)->CommitSize = Entry.CommitSize; - (*H)->MapBase = Entry.MapBase; - (*H)->MapSize = Entry.MapSize; - (*H)->Data = Entry.Data; - EntriesCount--; } - return Found; + (*H)->CommitBase = Entry.CommitBase; + (*H)->CommitSize = Entry.CommitSize; + (*H)->MemMap = Entry.MemMap; + return true; } bool canCache(uptr Size) { @@ -291,16 +312,15 @@ public: bool setOption(Option O, sptr Value) { if (O == Option::ReleaseInterval) { - const s32 Interval = - Max(Min(static_cast<s32>(Value), - Config::SecondaryCacheMaxReleaseToOsIntervalMs), - Config::SecondaryCacheMinReleaseToOsIntervalMs); + const s32 Interval = Max( + Min(static_cast<s32>(Value), CacheConfig::MaxReleaseToOsIntervalMs), + CacheConfig::MinReleaseToOsIntervalMs); atomic_store_relaxed(&ReleaseToOsIntervalMs, Interval); return true; } if (O == Option::MaxCacheEntriesCount) { const u32 MaxCount = static_cast<u32>(Value); - if (MaxCount > Config::SecondaryCacheEntriesArraySize) + if (MaxCount > CacheConfig::EntriesArraySize) return false; atomic_store_relaxed(&MaxEntriesCount, MaxCount); return true; @@ -315,67 +335,62 @@ public: void releaseToOS() { releaseOlderThan(UINT64_MAX); } - void disableMemoryTagging() { + void disableMemoryTagging() EXCLUDES(Mutex) { ScopedLock L(Mutex); - for (u32 I = 0; I != Config::SecondaryCacheQuarantineSize; ++I) { + for (u32 I = 0; I != CacheConfig::QuarantineSize; ++I) { if (Quarantine[I].CommitBase) { - unmap(reinterpret_cast<void *>(Quarantine[I].MapBase), - Quarantine[I].MapSize, UNMAP_ALL, &Quarantine[I].Data); + MemMapT &MemMap = Quarantine[I].MemMap; + MemMap.unmap(MemMap.getBase(), MemMap.getCapacity()); Quarantine[I].CommitBase = 0; } } const u32 MaxCount = atomic_load_relaxed(&MaxEntriesCount); - for (u32 I = 0; I < MaxCount; I++) - if (Entries[I].CommitBase) - setMemoryPermission(Entries[I].CommitBase, Entries[I].CommitSize, 0, - &Entries[I].Data); + for (u32 I = 0; I < MaxCount; I++) { + if (Entries[I].CommitBase) { + Entries[I].MemMap.setMemoryPermission(Entries[I].CommitBase, + Entries[I].CommitSize, 0); + } + } QuarantinePos = -1U; } - void disable() { Mutex.lock(); } + void disable() NO_THREAD_SAFETY_ANALYSIS { Mutex.lock(); } - void enable() { Mutex.unlock(); } + void enable() NO_THREAD_SAFETY_ANALYSIS { Mutex.unlock(); } void unmapTestOnly() { empty(); } private: void empty() { - struct { - void *MapBase; - uptr MapSize; - MapPlatformData Data; - } MapInfo[Config::SecondaryCacheEntriesArraySize]; + MemMapT MapInfo[CacheConfig::EntriesArraySize]; uptr N = 0; { ScopedLock L(Mutex); - for (uptr I = 0; I < Config::SecondaryCacheEntriesArraySize; I++) { + for (uptr I = 0; I < CacheConfig::EntriesArraySize; I++) { if (!Entries[I].CommitBase) continue; - MapInfo[N].MapBase = reinterpret_cast<void *>(Entries[I].MapBase); - MapInfo[N].MapSize = Entries[I].MapSize; - MapInfo[N].Data = Entries[I].Data; + MapInfo[N] = Entries[I].MemMap; Entries[I].CommitBase = 0; N++; } EntriesCount = 0; IsFullEvents = 0; } - for (uptr I = 0; I < N; I++) - unmap(MapInfo[I].MapBase, MapInfo[I].MapSize, UNMAP_ALL, - &MapInfo[I].Data); + for (uptr I = 0; I < N; I++) { + MemMapT &MemMap = MapInfo[I]; + MemMap.unmap(MemMap.getBase(), MemMap.getCapacity()); + } } struct CachedBlock { - uptr CommitBase; - uptr CommitSize; - uptr MapBase; - uptr MapSize; - uptr BlockBegin; - [[no_unique_address]] MapPlatformData Data; - u64 Time; + uptr CommitBase = 0; + uptr CommitSize = 0; + uptr BlockBegin = 0; + MemMapT MemMap = {}; + u64 Time = 0; }; - void releaseIfOlderThan(CachedBlock &Entry, u64 Time) { + void releaseIfOlderThan(CachedBlock &Entry, u64 Time) REQUIRES(Mutex) { if (!Entry.CommitBase || !Entry.Time) return; if (Entry.Time > Time) { @@ -383,38 +398,39 @@ private: OldestTime = Entry.Time; return; } - releasePagesToOS(Entry.CommitBase, 0, Entry.CommitSize, &Entry.Data); + Entry.MemMap.releasePagesToOS(Entry.CommitBase, Entry.CommitSize); Entry.Time = 0; } - void releaseOlderThan(u64 Time) { + void releaseOlderThan(u64 Time) EXCLUDES(Mutex) { ScopedLock L(Mutex); if (!EntriesCount || OldestTime == 0 || OldestTime > Time) return; OldestTime = 0; - for (uptr I = 0; I < Config::SecondaryCacheQuarantineSize; I++) + for (uptr I = 0; I < CacheConfig::QuarantineSize; I++) releaseIfOlderThan(Quarantine[I], Time); - for (uptr I = 0; I < Config::SecondaryCacheEntriesArraySize; I++) + for (uptr I = 0; I < CacheConfig::EntriesArraySize; I++) releaseIfOlderThan(Entries[I], Time); } HybridMutex Mutex; - u32 EntriesCount = 0; - u32 QuarantinePos = 0; + u32 EntriesCount GUARDED_BY(Mutex) = 0; + u32 QuarantinePos GUARDED_BY(Mutex) = 0; atomic_u32 MaxEntriesCount = {}; atomic_uptr MaxEntrySize = {}; - u64 OldestTime = 0; - u32 IsFullEvents = 0; + u64 OldestTime GUARDED_BY(Mutex) = 0; + u32 IsFullEvents GUARDED_BY(Mutex) = 0; atomic_s32 ReleaseToOsIntervalMs = {}; - CachedBlock Entries[Config::SecondaryCacheEntriesArraySize] = {}; - NonZeroLengthArray<CachedBlock, Config::SecondaryCacheQuarantineSize> - Quarantine = {}; + CachedBlock Entries[CacheConfig::EntriesArraySize] GUARDED_BY(Mutex) = {}; + NonZeroLengthArray<CachedBlock, CacheConfig::QuarantineSize> + Quarantine GUARDED_BY(Mutex) = {}; }; template <typename Config> class MapAllocator { public: - void init(GlobalStats *S, s32 ReleaseToOsInterval = -1) { + void init(GlobalStats *S, + s32 ReleaseToOsInterval = -1) NO_THREAD_SAFETY_ANALYSIS { DCHECK_EQ(AllocatedBytes, 0U); DCHECK_EQ(FreedBytes, 0U); Cache.init(ReleaseToOsInterval); @@ -438,19 +454,19 @@ public: return getBlockEnd(Ptr) - reinterpret_cast<uptr>(Ptr); } - void getStats(ScopedString *Str) const; - - void disable() { + void disable() NO_THREAD_SAFETY_ANALYSIS { Mutex.lock(); Cache.disable(); } - void enable() { + void enable() NO_THREAD_SAFETY_ANALYSIS { Cache.enable(); Mutex.unlock(); } template <typename F> void iterateOverBlocks(F Callback) const { + Mutex.assertHeld(); + for (const auto &H : InUseBlocks) { uptr Ptr = reinterpret_cast<uptr>(&H) + LargeBlock::getHeaderSize(); if (allocatorSupportsMemoryTagging<Config>()) @@ -469,17 +485,19 @@ public: void unmapTestOnly() { Cache.unmapTestOnly(); } -private: - typename Config::SecondaryCache Cache; + void getStats(ScopedString *Str); - HybridMutex Mutex; - DoublyLinkedList<LargeBlock::Header> InUseBlocks; - uptr AllocatedBytes = 0; - uptr FreedBytes = 0; - uptr LargestSize = 0; - u32 NumberOfAllocs = 0; - u32 NumberOfFrees = 0; - LocalStats Stats; +private: + typename Config::Secondary::template CacheT<Config> Cache; + + mutable HybridMutex Mutex; + DoublyLinkedList<LargeBlock::Header> InUseBlocks GUARDED_BY(Mutex); + uptr AllocatedBytes GUARDED_BY(Mutex) = 0; + uptr FreedBytes GUARDED_BY(Mutex) = 0; + uptr LargestSize GUARDED_BY(Mutex) = 0; + u32 NumberOfAllocs GUARDED_BY(Mutex) = 0; + u32 NumberOfFrees GUARDED_BY(Mutex) = 0; + LocalStats Stats GUARDED_BY(Mutex); }; // As with the Primary, the size passed to this function includes any desired @@ -502,9 +520,9 @@ void *MapAllocator<Config>::allocate(Options Options, uptr Size, uptr Alignment, Alignment = Max(Alignment, uptr(1U) << SCUDO_MIN_ALIGNMENT_LOG); const uptr PageSize = getPageSizeCached(); uptr RoundedSize = - roundUpTo(roundUpTo(Size, Alignment) + LargeBlock::getHeaderSize() + - Chunk::getHeaderSize(), - PageSize); + roundUp(roundUp(Size, Alignment) + LargeBlock::getHeaderSize() + + Chunk::getHeaderSize(), + PageSize); if (Alignment > PageSize) RoundedSize += Alignment - PageSize; @@ -523,23 +541,26 @@ void *MapAllocator<Config>::allocate(Options Options, uptr Size, uptr Alignment, if (FillContents && !Zeroed) memset(Ptr, FillContents == ZeroFill ? 0 : PatternFillByte, BlockEnd - PtrInt); - const uptr BlockSize = BlockEnd - HInt; { ScopedLock L(Mutex); InUseBlocks.push_back(H); - AllocatedBytes += BlockSize; + AllocatedBytes += H->CommitSize; NumberOfAllocs++; - Stats.add(StatAllocated, BlockSize); - Stats.add(StatMapped, H->MapSize); + Stats.add(StatAllocated, H->CommitSize); + Stats.add(StatMapped, H->MemMap.getCapacity()); } return Ptr; } } - MapPlatformData Data = {}; + ReservedMemoryT ReservedMemory; const uptr MapSize = RoundedSize + 2 * PageSize; - uptr MapBase = reinterpret_cast<uptr>( - map(nullptr, MapSize, nullptr, MAP_NOACCESS | MAP_ALLOWNOMEM, &Data)); + ReservedMemory.create(/*Addr=*/0U, MapSize, nullptr, MAP_ALLOWNOMEM); + + // Take the entire ownership of reserved region. + MemMapT MemMap = ReservedMemory.dispatch(ReservedMemory.getBase(), + ReservedMemory.getCapacity()); + uptr MapBase = MemMap.getBase(); if (UNLIKELY(!MapBase)) return nullptr; uptr CommitBase = MapBase + PageSize; @@ -551,27 +572,27 @@ void *MapAllocator<Config>::allocate(Options Options, uptr Size, uptr Alignment, // For alignments greater than or equal to a page, the user pointer (eg: the // pointer that is returned by the C or C++ allocation APIs) ends up on a // page boundary , and our headers will live in the preceding page. - CommitBase = roundUpTo(MapBase + PageSize + 1, Alignment) - PageSize; + CommitBase = roundUp(MapBase + PageSize + 1, Alignment) - PageSize; const uptr NewMapBase = CommitBase - PageSize; DCHECK_GE(NewMapBase, MapBase); // We only trim the extra memory on 32-bit platforms: 64-bit platforms // are less constrained memory wise, and that saves us two syscalls. if (SCUDO_WORDSIZE == 32U && NewMapBase != MapBase) { - unmap(reinterpret_cast<void *>(MapBase), NewMapBase - MapBase, 0, &Data); + MemMap.unmap(MapBase, NewMapBase - MapBase); MapBase = NewMapBase; } const uptr NewMapEnd = - CommitBase + PageSize + roundUpTo(Size, PageSize) + PageSize; + CommitBase + PageSize + roundUp(Size, PageSize) + PageSize; DCHECK_LE(NewMapEnd, MapEnd); if (SCUDO_WORDSIZE == 32U && NewMapEnd != MapEnd) { - unmap(reinterpret_cast<void *>(NewMapEnd), MapEnd - NewMapEnd, 0, &Data); + MemMap.unmap(NewMapEnd, MapEnd - NewMapEnd); MapEnd = NewMapEnd; } } const uptr CommitSize = MapEnd - PageSize - CommitBase; - const uptr AllocPos = roundDownTo(CommitBase + CommitSize - Size, Alignment); - mapSecondary<Config>(Options, CommitBase, CommitSize, AllocPos, 0, &Data); + const uptr AllocPos = roundDown(CommitBase + CommitSize - Size, Alignment); + mapSecondary<Config>(Options, CommitBase, CommitSize, AllocPos, 0, MemMap); const uptr HeaderPos = AllocPos - Chunk::getHeaderSize() - LargeBlock::getHeaderSize(); LargeBlock::Header *H = reinterpret_cast<LargeBlock::Header *>( @@ -579,11 +600,9 @@ void *MapAllocator<Config>::allocate(Options Options, uptr Size, uptr Alignment, if (useMemoryTagging<Config>(Options)) storeTags(LargeBlock::addHeaderTag<Config>(CommitBase), reinterpret_cast<uptr>(H + 1)); - H->MapBase = MapBase; - H->MapSize = MapEnd - MapBase; H->CommitBase = CommitBase; H->CommitSize = CommitSize; - H->Data = Data; + H->MemMap = MemMap; if (BlockEndPtr) *BlockEndPtr = CommitBase + CommitSize; { @@ -594,13 +613,14 @@ void *MapAllocator<Config>::allocate(Options Options, uptr Size, uptr Alignment, LargestSize = CommitSize; NumberOfAllocs++; Stats.add(StatAllocated, CommitSize); - Stats.add(StatMapped, H->MapSize); + Stats.add(StatMapped, H->MemMap.getCapacity()); } return reinterpret_cast<void *>(HeaderPos + LargeBlock::getHeaderSize()); } template <typename Config> -void MapAllocator<Config>::deallocate(Options Options, void *Ptr) { +void MapAllocator<Config>::deallocate(Options Options, void *Ptr) + EXCLUDES(Mutex) { LargeBlock::Header *H = LargeBlock::getHeader<Config>(Ptr); const uptr CommitSize = H->CommitSize; { @@ -609,18 +629,20 @@ void MapAllocator<Config>::deallocate(Options Options, void *Ptr) { FreedBytes += CommitSize; NumberOfFrees++; Stats.sub(StatAllocated, CommitSize); - Stats.sub(StatMapped, H->MapSize); + Stats.sub(StatMapped, H->MemMap.getCapacity()); } Cache.store(Options, H); } template <typename Config> -void MapAllocator<Config>::getStats(ScopedString *Str) const { +void MapAllocator<Config>::getStats(ScopedString *Str) EXCLUDES(Mutex) { + ScopedLock L(Mutex); Str->append("Stats: MapAllocator: allocated %u times (%zuK), freed %u times " "(%zuK), remains %u (%zuK) max %zuM\n", NumberOfAllocs, AllocatedBytes >> 10, NumberOfFrees, FreedBytes >> 10, NumberOfAllocs - NumberOfFrees, (AllocatedBytes - FreedBytes) >> 10, LargestSize >> 20); + Cache.getStats(Str); } } // namespace scudo diff --git a/contrib/llvm-project/compiler-rt/lib/scudo/standalone/size_class_map.h b/contrib/llvm-project/compiler-rt/lib/scudo/standalone/size_class_map.h index 766562495ec7..2a6e298f9366 100644 --- a/contrib/llvm-project/compiler-rt/lib/scudo/standalone/size_class_map.h +++ b/contrib/llvm-project/compiler-rt/lib/scudo/standalone/size_class_map.h @@ -311,13 +311,11 @@ struct SvelteSizeClassConfig { typedef FixedSizeClassMap<SvelteSizeClassConfig> SvelteSizeClassMap; -// Trusty is configured to only have one region containing blocks of size -// 2^7 bytes. struct TrustySizeClassConfig { static const uptr NumBits = 1; - static const uptr MinSizeLog = 7; - static const uptr MidSizeLog = 7; - static const uptr MaxSizeLog = 7; + static const uptr MinSizeLog = 5; + static const uptr MidSizeLog = 5; + static const uptr MaxSizeLog = 15; static const u16 MaxNumCachedHint = 12; static const uptr MaxBytesCachedLog = 10; static const uptr SizeDelta = 0; diff --git a/contrib/llvm-project/compiler-rt/lib/scudo/standalone/stats.h b/contrib/llvm-project/compiler-rt/lib/scudo/standalone/stats.h index be5bf2d3720a..658b75863ade 100644 --- a/contrib/llvm-project/compiler-rt/lib/scudo/standalone/stats.h +++ b/contrib/llvm-project/compiler-rt/lib/scudo/standalone/stats.h @@ -12,6 +12,7 @@ #include "atomic_helpers.h" #include "list.h" #include "mutex.h" +#include "thread_annotations.h" #include <string.h> @@ -60,19 +61,19 @@ class GlobalStats : public LocalStats { public: void init() { LocalStats::init(); } - void link(LocalStats *S) { + void link(LocalStats *S) EXCLUDES(Mutex) { ScopedLock L(Mutex); StatsList.push_back(S); } - void unlink(LocalStats *S) { + void unlink(LocalStats *S) EXCLUDES(Mutex) { ScopedLock L(Mutex); StatsList.remove(S); for (uptr I = 0; I < StatCount; I++) add(static_cast<StatType>(I), S->get(static_cast<StatType>(I))); } - void get(uptr *S) const { + void get(uptr *S) const EXCLUDES(Mutex) { ScopedLock L(Mutex); for (uptr I = 0; I < StatCount; I++) S[I] = LocalStats::get(static_cast<StatType>(I)); @@ -85,15 +86,15 @@ public: S[I] = static_cast<sptr>(S[I]) >= 0 ? S[I] : 0; } - void lock() { Mutex.lock(); } - void unlock() { Mutex.unlock(); } + void lock() ACQUIRE(Mutex) { Mutex.lock(); } + void unlock() RELEASE(Mutex) { Mutex.unlock(); } - void disable() { lock(); } - void enable() { unlock(); } + void disable() ACQUIRE(Mutex) { lock(); } + void enable() RELEASE(Mutex) { unlock(); } private: mutable HybridMutex Mutex; - DoublyLinkedList<LocalStats> StatsList; + DoublyLinkedList<LocalStats> StatsList GUARDED_BY(Mutex); }; } // namespace scudo diff --git a/contrib/llvm-project/compiler-rt/lib/scudo/standalone/string_utils.cpp b/contrib/llvm-project/compiler-rt/lib/scudo/standalone/string_utils.cpp index 13fdb9c6ca6c..d4e4e3becd0e 100644 --- a/contrib/llvm-project/compiler-rt/lib/scudo/standalone/string_utils.cpp +++ b/contrib/llvm-project/compiler-rt/lib/scudo/standalone/string_utils.cpp @@ -195,6 +195,28 @@ static int formatString(char *Buffer, uptr BufferLength, const char *Format, appendChar(&Buffer, BufferEnd, static_cast<char>(va_arg(Args, int))); break; } + // In Scudo, `s64`/`u64` are supposed to use `lld` and `llu` respectively. + // However, `-Wformat` doesn't know we have a different parser for those + // placeholders and it keeps complaining the type mismatch on 64-bit + // platform which uses `ld`/`lu` for `s64`/`u64`. Therefore, in order to + // silence the warning, we turn to use `PRId64`/`PRIu64` for printing + // `s64`/`u64` and handle the `ld`/`lu` here. + case 'l': { + ++Cur; + RAW_CHECK(*Cur == 'd' || *Cur == 'u'); + + if (*Cur == 'd') { + DVal = va_arg(Args, s64); + Res += + appendSignedDecimal(&Buffer, BufferEnd, DVal, Width, PadWithZero); + } else { + UVal = va_arg(Args, u64); + Res += appendUnsigned(&Buffer, BufferEnd, UVal, 10, Width, PadWithZero, + false); + } + + break; + } case '%': { RAW_CHECK_MSG(!HaveFlags, PrintfFormatsHelp); Res += appendChar(&Buffer, BufferEnd, '%'); @@ -218,7 +240,7 @@ int formatString(char *Buffer, uptr BufferLength, const char *Format, ...) { return Res; } -void ScopedString::append(const char *Format, va_list Args) { +void ScopedString::vappend(const char *Format, va_list Args) { va_list ArgsCopy; va_copy(ArgsCopy, Args); // formatString doesn't currently support a null buffer or zero buffer length, @@ -239,7 +261,7 @@ void ScopedString::append(const char *Format, va_list Args) { void ScopedString::append(const char *Format, ...) { va_list Args; va_start(Args, Format); - append(Format, Args); + vappend(Format, Args); va_end(Args); } @@ -247,7 +269,7 @@ void Printf(const char *Format, ...) { va_list Args; va_start(Args, Format); ScopedString Msg; - Msg.append(Format, Args); + Msg.vappend(Format, Args); outputRaw(Msg.data()); va_end(Args); } diff --git a/contrib/llvm-project/compiler-rt/lib/scudo/standalone/string_utils.h b/contrib/llvm-project/compiler-rt/lib/scudo/standalone/string_utils.h index 41901194dfdc..a4cab5268ede 100644 --- a/contrib/llvm-project/compiler-rt/lib/scudo/standalone/string_utils.h +++ b/contrib/llvm-project/compiler-rt/lib/scudo/standalone/string_utils.h @@ -25,7 +25,7 @@ public: String.clear(); String.push_back('\0'); } - void append(const char *Format, va_list Args); + void vappend(const char *Format, va_list Args); void append(const char *Format, ...) FORMAT(2, 3); void output() const { outputRaw(String.data()); } void reserve(size_t Size) { String.reserve(Size + 1); } diff --git a/contrib/llvm-project/compiler-rt/lib/scudo/standalone/thread_annotations.h b/contrib/llvm-project/compiler-rt/lib/scudo/standalone/thread_annotations.h new file mode 100644 index 000000000000..68a1087c2034 --- /dev/null +++ b/contrib/llvm-project/compiler-rt/lib/scudo/standalone/thread_annotations.h @@ -0,0 +1,70 @@ +//===-- thread_annotations.h ------------------------------------*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#ifndef SCUDO_THREAD_ANNOTATIONS_ +#define SCUDO_THREAD_ANNOTATIONS_ + +// Enable thread safety attributes only with clang. +// The attributes can be safely ignored when compiling with other compilers. +#if defined(__clang__) +#define THREAD_ANNOTATION_ATTRIBUTE_(x) __attribute__((x)) +#else +#define THREAD_ANNOTATION_ATTRIBUTE_(x) // no-op +#endif + +#define CAPABILITY(x) THREAD_ANNOTATION_ATTRIBUTE_(capability(x)) + +#define SCOPED_CAPABILITY THREAD_ANNOTATION_ATTRIBUTE_(scoped_lockable) + +#define GUARDED_BY(x) THREAD_ANNOTATION_ATTRIBUTE_(guarded_by(x)) + +#define PT_GUARDED_BY(x) THREAD_ANNOTATION_ATTRIBUTE_(pt_guarded_by(x)) + +#define ACQUIRED_BEFORE(...) \ + THREAD_ANNOTATION_ATTRIBUTE_(acquired_before(__VA_ARGS__)) + +#define ACQUIRED_AFTER(...) \ + THREAD_ANNOTATION_ATTRIBUTE_(acquired_after(__VA_ARGS__)) + +#define REQUIRES(...) \ + THREAD_ANNOTATION_ATTRIBUTE_(requires_capability(__VA_ARGS__)) + +#define REQUIRES_SHARED(...) \ + THREAD_ANNOTATION_ATTRIBUTE_(requires_shared_capability(__VA_ARGS__)) + +#define ACQUIRE(...) \ + THREAD_ANNOTATION_ATTRIBUTE_(acquire_capability(__VA_ARGS__)) + +#define ACQUIRE_SHARED(...) \ + THREAD_ANNOTATION_ATTRIBUTE_(acquire_shared_capability(__VA_ARGS__)) + +#define RELEASE(...) \ + THREAD_ANNOTATION_ATTRIBUTE_(release_capability(__VA_ARGS__)) + +#define RELEASE_SHARED(...) \ + THREAD_ANNOTATION_ATTRIBUTE_(release_shared_capability(__VA_ARGS__)) + +#define TRY_ACQUIRE(...) \ + THREAD_ANNOTATION_ATTRIBUTE_(try_acquire_capability(__VA_ARGS__)) + +#define TRY_ACQUIRE_SHARED(...) \ + THREAD_ANNOTATION_ATTRIBUTE_(try_acquire_shared_capability(__VA_ARGS__)) + +#define EXCLUDES(...) THREAD_ANNOTATION_ATTRIBUTE_(locks_excluded(__VA_ARGS__)) + +#define ASSERT_CAPABILITY(x) THREAD_ANNOTATION_ATTRIBUTE_(assert_capability(x)) + +#define ASSERT_SHARED_CAPABILITY(x) \ + THREAD_ANNOTATION_ATTRIBUTE_(assert_shared_capability(x)) + +#define RETURN_CAPABILITY(x) THREAD_ANNOTATION_ATTRIBUTE_(lock_returned(x)) + +#define NO_THREAD_SAFETY_ANALYSIS \ + THREAD_ANNOTATION_ATTRIBUTE_(no_thread_safety_analysis) + +#endif // SCUDO_THREAD_ANNOTATIONS_ diff --git a/contrib/llvm-project/compiler-rt/lib/scudo/standalone/timing.cpp b/contrib/llvm-project/compiler-rt/lib/scudo/standalone/timing.cpp new file mode 100644 index 000000000000..59ae21d10f0f --- /dev/null +++ b/contrib/llvm-project/compiler-rt/lib/scudo/standalone/timing.cpp @@ -0,0 +1,29 @@ +//===-- timing.cpp ----------------------------------------------*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#include "timing.h" + +namespace scudo { + +Timer::~Timer() { + if (Manager) + Manager->report(*this); +} + +ScopedTimer::ScopedTimer(TimingManager &Manager, const char *Name) + : Timer(Manager.getOrCreateTimer(Name)) { + start(); +} + +ScopedTimer::ScopedTimer(TimingManager &Manager, const Timer &Nest, + const char *Name) + : Timer(Manager.nest(Nest, Name)) { + start(); +} + +} // namespace scudo diff --git a/contrib/llvm-project/compiler-rt/lib/scudo/standalone/timing.h b/contrib/llvm-project/compiler-rt/lib/scudo/standalone/timing.h new file mode 100644 index 000000000000..84caa79e5c3a --- /dev/null +++ b/contrib/llvm-project/compiler-rt/lib/scudo/standalone/timing.h @@ -0,0 +1,221 @@ +//===-- timing.h ------------------------------------------------*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#ifndef SCUDO_TIMING_H_ +#define SCUDO_TIMING_H_ + +#include "common.h" +#include "mutex.h" +#include "string_utils.h" +#include "thread_annotations.h" + +#include <inttypes.h> +#include <string.h> + +namespace scudo { + +class TimingManager; + +// A simple timer for evaluating execution time of code snippets. It can be used +// along with TimingManager or standalone. +class Timer { +public: + // The use of Timer without binding to a TimingManager is supposed to do the + // timer logging manually. Otherwise, TimingManager will do the logging stuff + // for you. + Timer() = default; + Timer(Timer &&Other) + : StartTime(0), AccTime(Other.AccTime), Manager(Other.Manager), + HandleId(Other.HandleId) { + Other.Manager = nullptr; + } + + Timer(const Timer &) = delete; + + ~Timer(); + + void start() { + CHECK_EQ(StartTime, 0U); + StartTime = getMonotonicTime(); + } + void stop() { + AccTime += getMonotonicTime() - StartTime; + StartTime = 0; + } + u64 getAccumulatedTime() const { return AccTime; } + + // Unset the bound TimingManager so that we don't report the data back. This + // is useful if we only want to track subset of certain scope events. + void ignore() { + StartTime = 0; + AccTime = 0; + Manager = nullptr; + } + +protected: + friend class TimingManager; + Timer(TimingManager &Manager, u32 HandleId) + : Manager(&Manager), HandleId(HandleId) {} + + u64 StartTime = 0; + u64 AccTime = 0; + TimingManager *Manager = nullptr; + u32 HandleId; +}; + +// A RAII-style wrapper for easy scope execution measurement. Note that in order +// not to take additional space for the message like `Name`. It only works with +// TimingManager. +class ScopedTimer : public Timer { +public: + ScopedTimer(TimingManager &Manager, const char *Name); + ScopedTimer(TimingManager &Manager, const Timer &Nest, const char *Name); + ~ScopedTimer() { stop(); } +}; + +// In Scudo, the execution time of single run of code snippets may not be +// useful, we are more interested in the average time from several runs. +// TimingManager lets the registered timer report their data and reports the +// average execution time for each timer periodically. +class TimingManager { +public: + TimingManager(u32 PrintingInterval = DefaultPrintingInterval) + : PrintingInterval(PrintingInterval) {} + ~TimingManager() { + if (NumAllocatedTimers != 0) + printAll(); + } + + Timer getOrCreateTimer(const char *Name) EXCLUDES(Mutex) { + ScopedLock L(Mutex); + + CHECK_LT(strlen(Name), MaxLenOfTimerName); + for (u32 I = 0; I < NumAllocatedTimers; ++I) { + if (strncmp(Name, Timers[I].Name, MaxLenOfTimerName) == 0) + return Timer(*this, I); + } + + CHECK_LT(NumAllocatedTimers, MaxNumberOfTimers); + strncpy(Timers[NumAllocatedTimers].Name, Name, MaxLenOfTimerName); + TimerRecords[NumAllocatedTimers].AccumulatedTime = 0; + TimerRecords[NumAllocatedTimers].Occurrence = 0; + return Timer(*this, NumAllocatedTimers++); + } + + // Add a sub-Timer associated with another Timer. This is used when we want to + // detail the execution time in the scope of a Timer. + // For example, + // void Foo() { + // // T1 records the time spent in both first and second tasks. + // ScopedTimer T1(getTimingManager(), "Task1"); + // { + // // T2 records the time spent in first task + // ScopedTimer T2(getTimingManager, T1, "Task2"); + // // Do first task. + // } + // // Do second task. + // } + // + // The report will show proper indents to indicate the nested relation like, + // -- Average Operation Time -- -- Name (# of Calls) -- + // 10.0(ns) Task1 (1) + // 5.0(ns) Task2 (1) + Timer nest(const Timer &T, const char *Name) EXCLUDES(Mutex) { + CHECK_EQ(T.Manager, this); + Timer Nesting = getOrCreateTimer(Name); + + ScopedLock L(Mutex); + CHECK_NE(Nesting.HandleId, T.HandleId); + Timers[Nesting.HandleId].Nesting = T.HandleId; + return Nesting; + } + + void report(const Timer &T) EXCLUDES(Mutex) { + ScopedLock L(Mutex); + + const u32 HandleId = T.HandleId; + CHECK_LT(HandleId, MaxNumberOfTimers); + TimerRecords[HandleId].AccumulatedTime += T.getAccumulatedTime(); + ++TimerRecords[HandleId].Occurrence; + ++NumEventsReported; + if (NumEventsReported % PrintingInterval == 0) + printAllImpl(); + } + + void printAll() EXCLUDES(Mutex) { + ScopedLock L(Mutex); + printAllImpl(); + } + +private: + void printAllImpl() REQUIRES(Mutex) { + static char NameHeader[] = "-- Name (# of Calls) --"; + static char AvgHeader[] = "-- Average Operation Time --"; + ScopedString Str; + Str.append("%-15s %-15s\n", AvgHeader, NameHeader); + + for (u32 I = 0; I < NumAllocatedTimers; ++I) { + if (Timers[I].Nesting != MaxNumberOfTimers) + continue; + printImpl(Str, I); + } + + Str.output(); + } + + void printImpl(ScopedString &Str, const u32 HandleId, + const u32 ExtraIndent = 0) REQUIRES(Mutex) { + const u64 AccumulatedTime = TimerRecords[HandleId].AccumulatedTime; + const u64 Occurrence = TimerRecords[HandleId].Occurrence; + const u64 Integral = Occurrence == 0 ? 0 : AccumulatedTime / Occurrence; + // Only keep single digit of fraction is enough and it enables easier layout + // maintenance. + const u64 Fraction = + Occurrence == 0 ? 0 + : ((AccumulatedTime % Occurrence) * 10) / Occurrence; + + Str.append("%14" PRId64 ".%" PRId64 "(ns) %-11s", Integral, Fraction, " "); + + for (u32 I = 0; I < ExtraIndent; ++I) + Str.append("%s", " "); + Str.append("%s (%" PRId64 ")\n", Timers[HandleId].Name, Occurrence); + + for (u32 I = 0; I < NumAllocatedTimers; ++I) + if (Timers[I].Nesting == HandleId) + printImpl(Str, I, ExtraIndent + 1); + } + + // Instead of maintaining pages for timer registration, a static buffer is + // sufficient for most use cases in Scudo. + static constexpr u32 MaxNumberOfTimers = 50; + static constexpr u32 MaxLenOfTimerName = 50; + static constexpr u32 DefaultPrintingInterval = 100; + + struct Record { + u64 AccumulatedTime = 0; + u64 Occurrence = 0; + }; + + struct TimerInfo { + char Name[MaxLenOfTimerName + 1]; + u32 Nesting = MaxNumberOfTimers; + }; + + HybridMutex Mutex; + // The frequency of proactively dumping the timer statistics. For example, the + // default setting is to dump the statistics every 100 reported events. + u32 PrintingInterval GUARDED_BY(Mutex); + u64 NumEventsReported GUARDED_BY(Mutex) = 0; + u32 NumAllocatedTimers GUARDED_BY(Mutex) = 0; + TimerInfo Timers[MaxNumberOfTimers] GUARDED_BY(Mutex); + Record TimerRecords[MaxNumberOfTimers] GUARDED_BY(Mutex); +}; + +} // namespace scudo + +#endif // SCUDO_TIMING_H_ diff --git a/contrib/llvm-project/compiler-rt/lib/scudo/standalone/trusty.cpp b/contrib/llvm-project/compiler-rt/lib/scudo/standalone/trusty.cpp index 81d6bc585f09..3191091e1b96 100644 --- a/contrib/llvm-project/compiler-rt/lib/scudo/standalone/trusty.cpp +++ b/contrib/llvm-project/compiler-rt/lib/scudo/standalone/trusty.cpp @@ -12,17 +12,17 @@ #include "common.h" #include "mutex.h" -#include "string_utils.h" #include "trusty.h" #include <errno.h> // for errno +#include <lk/err_ptr.h> // for PTR_ERR and IS_ERR #include <stdio.h> // for printf() #include <stdlib.h> // for getenv() #include <sys/auxv.h> // for getauxval() #include <time.h> // for clock_gettime() +#include <trusty_err.h> // for lk_err_to_errno() #include <trusty_syscalls.h> // for _trusty_brk() - -#define SBRK_ALIGN 32 +#include <uapi/mm.h> // for MMAP flags namespace scudo { @@ -30,35 +30,38 @@ uptr getPageSize() { return getauxval(AT_PAGESZ); } void NORETURN die() { abort(); } -void *map(UNUSED void *Addr, uptr Size, UNUSED const char *Name, uptr Flags, +void *map(void *Addr, uptr Size, const char *Name, uptr Flags, UNUSED MapPlatformData *Data) { - // Calling _trusty_brk(0) returns the current program break. - uptr ProgramBreak = reinterpret_cast<uptr>(_trusty_brk(0)); - uptr Start; - uptr End; - - Start = roundUpTo(ProgramBreak, SBRK_ALIGN); - // Don't actually extend the heap if MAP_NOACCESS flag is set since this is - // the case where Scudo tries to reserve a memory region without mapping - // physical pages. + uint32_t MmapFlags = + MMAP_FLAG_ANONYMOUS | MMAP_FLAG_PROT_READ | MMAP_FLAG_PROT_WRITE; + + // If the MAP_NOACCESS flag is set, Scudo tries to reserve + // a memory region without mapping physical pages. This corresponds + // to MMAP_FLAG_NO_PHYSICAL in Trusty. if (Flags & MAP_NOACCESS) - return reinterpret_cast<void *>(Start); - - // Attempt to extend the heap by Size bytes using _trusty_brk. - End = roundUpTo(Start + Size, SBRK_ALIGN); - ProgramBreak = - reinterpret_cast<uptr>(_trusty_brk(reinterpret_cast<void *>(End))); - if (ProgramBreak < End) { - errno = ENOMEM; + MmapFlags |= MMAP_FLAG_NO_PHYSICAL; + if (Addr) + MmapFlags |= MMAP_FLAG_FIXED_NOREPLACE; + + if (Flags & MAP_MEMTAG) + MmapFlags |= MMAP_FLAG_PROT_MTE; + + void *P = (void *)_trusty_mmap(Addr, Size, MmapFlags, 0); + + if (IS_ERR(P)) { + errno = lk_err_to_errno(PTR_ERR(P)); dieOnMapUnmapError(Size); return nullptr; } - return reinterpret_cast<void *>(Start); // Base of new reserved region. + + return P; } -// Unmap is a no-op since Trusty uses sbrk instead of memory mapping. void unmap(UNUSED void *Addr, UNUSED uptr Size, UNUSED uptr Flags, - UNUSED MapPlatformData *Data) {} + UNUSED MapPlatformData *Data) { + if (_trusty_munmap(Addr, Size) != 0) + dieOnMapUnmapError(); +} void setMemoryPermission(UNUSED uptr Addr, UNUSED uptr Size, UNUSED uptr Flags, UNUSED MapPlatformData *Data) {} @@ -76,6 +79,8 @@ void HybridMutex::lockSlow() {} void HybridMutex::unlock() {} +void HybridMutex::assertHeldImpl() {} + u64 getMonotonicTime() { timespec TS; clock_gettime(CLOCK_MONOTONIC, &TS); @@ -83,6 +88,17 @@ u64 getMonotonicTime() { static_cast<u64>(TS.tv_nsec); } +u64 getMonotonicTimeFast() { +#if defined(CLOCK_MONOTONIC_COARSE) + timespec TS; + clock_gettime(CLOCK_MONOTONIC_COARSE, &TS); + return static_cast<u64>(TS.tv_sec) * (1000ULL * 1000 * 1000) + + static_cast<u64>(TS.tv_nsec); +#else + return getMonotonicTime(); +#endif +} + u32 getNumberOfCPUs() { return 0; } u32 getThreadID() { return 0; } diff --git a/contrib/llvm-project/compiler-rt/lib/scudo/standalone/tsd.h b/contrib/llvm-project/compiler-rt/lib/scudo/standalone/tsd.h index b400a3b56da9..f4fa545de5e0 100644 --- a/contrib/llvm-project/compiler-rt/lib/scudo/standalone/tsd.h +++ b/contrib/llvm-project/compiler-rt/lib/scudo/standalone/tsd.h @@ -12,6 +12,7 @@ #include "atomic_helpers.h" #include "common.h" #include "mutex.h" +#include "thread_annotations.h" #include <limits.h> // for PTHREAD_DESTRUCTOR_ITERATIONS #include <pthread.h> @@ -24,41 +25,61 @@ namespace scudo { template <class Allocator> struct alignas(SCUDO_CACHE_LINE_SIZE) TSD { - typename Allocator::CacheT Cache; - typename Allocator::QuarantineCacheT QuarantineCache; using ThisT = TSD<Allocator>; u8 DestructorIterations = 0; - void init(Allocator *Instance) { + void init(Allocator *Instance) NO_THREAD_SAFETY_ANALYSIS { DCHECK_EQ(DestructorIterations, 0U); DCHECK(isAligned(reinterpret_cast<uptr>(this), alignof(ThisT))); Instance->initCache(&Cache); DestructorIterations = PTHREAD_DESTRUCTOR_ITERATIONS; } - void commitBack(Allocator *Instance) { Instance->commitBack(this); } - - inline bool tryLock() { + inline bool tryLock() NO_THREAD_SAFETY_ANALYSIS { if (Mutex.tryLock()) { atomic_store_relaxed(&Precedence, 0); return true; } if (atomic_load_relaxed(&Precedence) == 0) - atomic_store_relaxed( - &Precedence, - static_cast<uptr>(getMonotonicTime() >> FIRST_32_SECOND_64(16, 0))); + atomic_store_relaxed(&Precedence, + static_cast<uptr>(getMonotonicTimeFast() >> + FIRST_32_SECOND_64(16, 0))); return false; } - inline void lock() { + inline void lock() NO_THREAD_SAFETY_ANALYSIS { atomic_store_relaxed(&Precedence, 0); Mutex.lock(); } - inline void unlock() { Mutex.unlock(); } + inline void unlock() NO_THREAD_SAFETY_ANALYSIS { Mutex.unlock(); } inline uptr getPrecedence() { return atomic_load_relaxed(&Precedence); } + void commitBack(Allocator *Instance) ASSERT_CAPABILITY(Mutex) { + Instance->commitBack(this); + } + + // Ideally, we may want to assert that all the operations on + // Cache/QuarantineCache always have the `Mutex` acquired. However, the + // current architecture of accessing TSD is not easy to cooperate with the + // thread-safety analysis because of pointer aliasing. So now we just add the + // assertion on the getters of Cache/QuarantineCache. + // + // TODO(chiahungduan): Ideally, we want to do `Mutex.assertHeld` but acquiring + // TSD doesn't always require holding the lock. Add this assertion while the + // lock is always acquired. + typename Allocator::CacheT &getCache() ASSERT_CAPABILITY(Mutex) { + return Cache; + } + typename Allocator::QuarantineCacheT &getQuarantineCache() + ASSERT_CAPABILITY(Mutex) { + return QuarantineCache; + } + private: HybridMutex Mutex; atomic_uptr Precedence = {}; + + typename Allocator::CacheT Cache GUARDED_BY(Mutex); + typename Allocator::QuarantineCacheT QuarantineCache GUARDED_BY(Mutex); }; } // namespace scudo diff --git a/contrib/llvm-project/compiler-rt/lib/scudo/standalone/tsd_exclusive.h b/contrib/llvm-project/compiler-rt/lib/scudo/standalone/tsd_exclusive.h index d49427b2005b..238367420238 100644 --- a/contrib/llvm-project/compiler-rt/lib/scudo/standalone/tsd_exclusive.h +++ b/contrib/llvm-project/compiler-rt/lib/scudo/standalone/tsd_exclusive.h @@ -11,6 +11,8 @@ #include "tsd.h" +#include "string_utils.h" + namespace scudo { struct ThreadState { @@ -25,7 +27,7 @@ struct ThreadState { template <class Allocator> void teardownThread(void *Ptr); template <class Allocator> struct TSDRegistryExT { - void init(Allocator *Instance) { + void init(Allocator *Instance) REQUIRES(Mutex) { DCHECK(!Initialized); Instance->init(); CHECK_EQ(pthread_key_create(&PThreadKey, teardownThread<Allocator>), 0); @@ -33,14 +35,14 @@ template <class Allocator> struct TSDRegistryExT { Initialized = true; } - void initOnceMaybe(Allocator *Instance) { + void initOnceMaybe(Allocator *Instance) EXCLUDES(Mutex) { ScopedLock L(Mutex); if (LIKELY(Initialized)) return; init(Instance); // Sets Initialized. } - void unmapTestOnly(Allocator *Instance) { + void unmapTestOnly(Allocator *Instance) EXCLUDES(Mutex) { DCHECK(Instance); if (reinterpret_cast<Allocator *>(pthread_getspecific(PThreadKey))) { DCHECK_EQ(reinterpret_cast<Allocator *>(pthread_getspecific(PThreadKey)), @@ -53,16 +55,32 @@ template <class Allocator> struct TSDRegistryExT { FallbackTSD.commitBack(Instance); FallbackTSD = {}; State = {}; + ScopedLock L(Mutex); Initialized = false; } + void drainCaches(Allocator *Instance) { + // We don't have a way to iterate all thread local `ThreadTSD`s. Simply + // drain the `ThreadTSD` of current thread and `FallbackTSD`. + Instance->drainCache(&ThreadTSD); + FallbackTSD.lock(); + Instance->drainCache(&FallbackTSD); + FallbackTSD.unlock(); + } + ALWAYS_INLINE void initThreadMaybe(Allocator *Instance, bool MinimalInit) { if (LIKELY(State.InitState != ThreadState::NotInitialized)) return; initThread(Instance, MinimalInit); } - ALWAYS_INLINE TSD<Allocator> *getTSDAndLock(bool *UnlockRequired) { + // TODO(chiahungduan): Consider removing the argument `UnlockRequired` by + // embedding the logic into TSD or always locking the TSD. It will enable us + // to properly mark thread annotation here and adding proper runtime + // assertions in the member functions of TSD. For example, assert the lock is + // acquired before calling TSD::commitBack(). + ALWAYS_INLINE TSD<Allocator> * + getTSDAndLock(bool *UnlockRequired) NO_THREAD_SAFETY_ANALYSIS { if (LIKELY(State.InitState == ThreadState::Initialized && !atomic_load(&Disabled, memory_order_acquire))) { *UnlockRequired = false; @@ -75,13 +93,13 @@ template <class Allocator> struct TSDRegistryExT { // To disable the exclusive TSD registry, we effectively lock the fallback TSD // and force all threads to attempt to use it instead of their local one. - void disable() { + void disable() NO_THREAD_SAFETY_ANALYSIS { Mutex.lock(); FallbackTSD.lock(); atomic_store(&Disabled, 1U, memory_order_release); } - void enable() { + void enable() NO_THREAD_SAFETY_ANALYSIS { atomic_store(&Disabled, 0U, memory_order_release); FallbackTSD.unlock(); Mutex.unlock(); @@ -97,6 +115,13 @@ template <class Allocator> struct TSDRegistryExT { bool getDisableMemInit() { return State.DisableMemInit; } + void getStats(ScopedString *Str) { + // We don't have a way to iterate all thread local `ThreadTSD`s. Instead of + // printing only self `ThreadTSD` which may mislead the usage, we just skip + // it. + Str->append("Exclusive TSD don't support iterating each TSD\n"); + } + private: // Using minimal initialization allows for global initialization while keeping // the thread specific structure untouched. The fallback structure will be @@ -113,7 +138,7 @@ private: } pthread_key_t PThreadKey = {}; - bool Initialized = false; + bool Initialized GUARDED_BY(Mutex) = false; atomic_u8 Disabled = {}; TSD<Allocator> FallbackTSD; HybridMutex Mutex; @@ -128,7 +153,8 @@ thread_local TSD<Allocator> TSDRegistryExT<Allocator>::ThreadTSD; template <class Allocator> thread_local ThreadState TSDRegistryExT<Allocator>::State; -template <class Allocator> void teardownThread(void *Ptr) { +template <class Allocator> +void teardownThread(void *Ptr) NO_THREAD_SAFETY_ANALYSIS { typedef TSDRegistryExT<Allocator> TSDRegistryT; Allocator *Instance = reinterpret_cast<Allocator *>(Ptr); // The glibc POSIX thread-local-storage deallocation routine calls user diff --git a/contrib/llvm-project/compiler-rt/lib/scudo/standalone/tsd_shared.h b/contrib/llvm-project/compiler-rt/lib/scudo/standalone/tsd_shared.h index 1c2a880416b9..dcb0948ad78f 100644 --- a/contrib/llvm-project/compiler-rt/lib/scudo/standalone/tsd_shared.h +++ b/contrib/llvm-project/compiler-rt/lib/scudo/standalone/tsd_shared.h @@ -11,6 +11,8 @@ #include "tsd.h" +#include "string_utils.h" + #if SCUDO_HAS_PLATFORM_TLS_SLOT // This is a platform-provided header that needs to be on the include path when // Scudo is compiled. It must declare a function with the prototype: @@ -24,7 +26,7 @@ namespace scudo { template <class Allocator, u32 TSDsArraySize, u32 DefaultTSDCount> struct TSDRegistrySharedT { - void init(Allocator *Instance) { + void init(Allocator *Instance) REQUIRES(Mutex) { DCHECK(!Initialized); Instance->init(); for (u32 I = 0; I < TSDsArraySize; I++) @@ -35,22 +37,32 @@ struct TSDRegistrySharedT { Initialized = true; } - void initOnceMaybe(Allocator *Instance) { + void initOnceMaybe(Allocator *Instance) EXCLUDES(Mutex) { ScopedLock L(Mutex); if (LIKELY(Initialized)) return; init(Instance); // Sets Initialized. } - void unmapTestOnly(Allocator *Instance) { + void unmapTestOnly(Allocator *Instance) EXCLUDES(Mutex) { for (u32 I = 0; I < TSDsArraySize; I++) { TSDs[I].commitBack(Instance); TSDs[I] = {}; } setCurrentTSD(nullptr); + ScopedLock L(Mutex); Initialized = false; } + void drainCaches(Allocator *Instance) { + ScopedLock L(MutexTSDs); + for (uptr I = 0; I < NumberOfTSDs; ++I) { + TSDs[I].lock(); + Instance->drainCache(&TSDs[I]); + TSDs[I].unlock(); + } + } + ALWAYS_INLINE void initThreadMaybe(Allocator *Instance, UNUSED bool MinimalInit) { if (LIKELY(getCurrentTSD())) @@ -58,7 +70,10 @@ struct TSDRegistrySharedT { initThread(Instance); } - ALWAYS_INLINE TSD<Allocator> *getTSDAndLock(bool *UnlockRequired) { + // TSDs is an array of locks and which is not supported for marking + // thread-safety capability. + ALWAYS_INLINE TSD<Allocator> * + getTSDAndLock(bool *UnlockRequired) NO_THREAD_SAFETY_ANALYSIS { TSD<Allocator> *TSD = getCurrentTSD(); DCHECK(TSD); *UnlockRequired = true; @@ -75,13 +90,13 @@ struct TSDRegistrySharedT { return getTSDAndLockSlow(TSD); } - void disable() { + void disable() NO_THREAD_SAFETY_ANALYSIS { Mutex.lock(); for (u32 I = 0; I < TSDsArraySize; I++) TSDs[I].lock(); } - void enable() { + void enable() NO_THREAD_SAFETY_ANALYSIS { for (s32 I = static_cast<s32>(TSDsArraySize - 1); I >= 0; I--) TSDs[I].unlock(); Mutex.unlock(); @@ -98,6 +113,19 @@ struct TSDRegistrySharedT { bool getDisableMemInit() const { return *getTlsPtr() & 1; } + void getStats(ScopedString *Str) EXCLUDES(MutexTSDs) { + ScopedLock L(MutexTSDs); + + Str->append("Stats: SharedTSDs: %u available; total %u\n", NumberOfTSDs, + TSDsArraySize); + for (uptr I = 0; I < NumberOfTSDs; ++I) { + TSDs[I].lock(); + Str->append(" Shared TSD[%zu]:\n", I); + TSDs[I].getCache().getStats(Str); + TSDs[I].unlock(); + } + } + private: ALWAYS_INLINE uptr *getTlsPtr() const { #if SCUDO_HAS_PLATFORM_TLS_SLOT @@ -119,7 +147,7 @@ private: return reinterpret_cast<TSD<Allocator> *>(*getTlsPtr() & ~1ULL); } - bool setNumberOfTSDs(u32 N) { + bool setNumberOfTSDs(u32 N) EXCLUDES(MutexTSDs) { ScopedLock L(MutexTSDs); if (N < NumberOfTSDs) return false; @@ -150,7 +178,7 @@ private: *getTlsPtr() |= B; } - NOINLINE void initThread(Allocator *Instance) { + NOINLINE void initThread(Allocator *Instance) NO_THREAD_SAFETY_ANALYSIS { initOnceMaybe(Instance); // Initial context assignment is done in a plain round-robin fashion. const u32 Index = atomic_fetch_add(&CurrentIndex, 1U, memory_order_relaxed); @@ -158,7 +186,10 @@ private: Instance->callPostInitCallback(); } - NOINLINE TSD<Allocator> *getTSDAndLockSlow(TSD<Allocator> *CurrentTSD) { + // TSDs is an array of locks which is not supported for marking thread-safety + // capability. + NOINLINE TSD<Allocator> *getTSDAndLockSlow(TSD<Allocator> *CurrentTSD) + EXCLUDES(MutexTSDs) { // Use the Precedence of the current TSD as our random seed. Since we are // in the slow path, it means that tryLock failed, and as a result it's // very likely that said Precedence is non-zero. @@ -202,10 +233,10 @@ private: } atomic_u32 CurrentIndex = {}; - u32 NumberOfTSDs = 0; - u32 NumberOfCoPrimes = 0; - u32 CoPrimes[TSDsArraySize] = {}; - bool Initialized = false; + u32 NumberOfTSDs GUARDED_BY(MutexTSDs) = 0; + u32 NumberOfCoPrimes GUARDED_BY(MutexTSDs) = 0; + u32 CoPrimes[TSDsArraySize] GUARDED_BY(MutexTSDs) = {}; + bool Initialized GUARDED_BY(Mutex) = false; HybridMutex Mutex; HybridMutex MutexTSDs; TSD<Allocator> TSDs[TSDsArraySize]; diff --git a/contrib/llvm-project/compiler-rt/lib/scudo/standalone/vector.h b/contrib/llvm-project/compiler-rt/lib/scudo/standalone/vector.h index d43205a7111d..9f2c200958fe 100644 --- a/contrib/llvm-project/compiler-rt/lib/scudo/standalone/vector.h +++ b/contrib/llvm-project/compiler-rt/lib/scudo/standalone/vector.h @@ -40,7 +40,7 @@ public: void push_back(const T &Element) { DCHECK_LE(Size, capacity()); if (Size == capacity()) { - const uptr NewCapacity = roundUpToPowerOfTwo(Size + 1); + const uptr NewCapacity = roundUpPowerOfTwo(Size + 1); reallocate(NewCapacity); } memcpy(&Data[Size++], &Element, sizeof(T)); @@ -82,7 +82,7 @@ private: void reallocate(uptr NewCapacity) { DCHECK_GT(NewCapacity, 0); DCHECK_LE(Size, NewCapacity); - NewCapacity = roundUpTo(NewCapacity * sizeof(T), getPageSizeCached()); + NewCapacity = roundUp(NewCapacity * sizeof(T), getPageSizeCached()); T *NewData = reinterpret_cast<T *>( map(nullptr, NewCapacity, "scudo:vector", 0, &MapData)); memcpy(NewData, Data, Size * sizeof(T)); diff --git a/contrib/llvm-project/compiler-rt/lib/scudo/standalone/wrappers_c.inc b/contrib/llvm-project/compiler-rt/lib/scudo/standalone/wrappers_c.inc index bbe3617dd0d6..2c8e382dba0b 100644 --- a/contrib/llvm-project/compiler-rt/lib/scudo/standalone/wrappers_c.inc +++ b/contrib/llvm-project/compiler-rt/lib/scudo/standalone/wrappers_c.inc @@ -54,6 +54,8 @@ INTERFACE WEAK struct SCUDO_MALLINFO SCUDO_PREFIX(mallinfo)(void) { return Info; } +// On Android, mallinfo2 is an alias of mallinfo, so don't define both. +#if !SCUDO_ANDROID INTERFACE WEAK struct __scudo_mallinfo2 SCUDO_PREFIX(mallinfo2)(void) { struct __scudo_mallinfo2 Info = {}; scudo::StatCounters Stats; @@ -70,6 +72,7 @@ INTERFACE WEAK struct __scudo_mallinfo2 SCUDO_PREFIX(mallinfo2)(void) { Info.fordblks = Info.fsmblks; return Info; } +#endif INTERFACE WEAK void *SCUDO_PREFIX(malloc)(size_t size) { return scudo::setErrnoOnNull(SCUDO_ALLOCATOR.allocate( @@ -91,7 +94,7 @@ INTERFACE WEAK void *SCUDO_PREFIX(memalign)(size_t alignment, size_t size) { alignment = 1U; } else { if (UNLIKELY(!scudo::isPowerOfTwo(alignment))) - alignment = scudo::roundUpToPowerOfTwo(alignment); + alignment = scudo::roundUpPowerOfTwo(alignment); } } else { if (UNLIKELY(!scudo::isPowerOfTwo(alignment))) { @@ -131,9 +134,9 @@ INTERFACE WEAK void *SCUDO_PREFIX(pvalloc)(size_t size) { scudo::reportPvallocOverflow(size); } // pvalloc(0) should allocate one page. - return scudo::setErrnoOnNull(SCUDO_ALLOCATOR.allocate( - size ? scudo::roundUpTo(size, PageSize) : PageSize, - scudo::Chunk::Origin::Memalign, PageSize)); + return scudo::setErrnoOnNull( + SCUDO_ALLOCATOR.allocate(size ? scudo::roundUp(size, PageSize) : PageSize, + scudo::Chunk::Origin::Memalign, PageSize)); } INTERFACE WEAK void *SCUDO_PREFIX(realloc)(void *ptr, size_t size) { @@ -188,7 +191,13 @@ INTERFACE WEAK int SCUDO_PREFIX(mallopt)(int param, int value) { static_cast<scudo::sptr>(value)); return 1; } else if (param == M_PURGE) { - SCUDO_ALLOCATOR.releaseToOS(); + SCUDO_ALLOCATOR.releaseToOS(scudo::ReleaseToOS::Force); + return 1; + } else if (param == M_PURGE_ALL) { + SCUDO_ALLOCATOR.releaseToOS(scudo::ReleaseToOS::ForceAll); + return 1; + } else if (param == M_LOG_STATS) { + SCUDO_ALLOCATOR.printStats(); return 1; } else { scudo::Option option; @@ -238,7 +247,10 @@ INTERFACE WEAK int SCUDO_PREFIX(malloc_info)(UNUSED int options, FILE *stream) { if (size < max_size) sizes[size]++; }; + + SCUDO_ALLOCATOR.disable(); SCUDO_ALLOCATOR.iterateOverChunks(0, -1ul, callback, sizes); + SCUDO_ALLOCATOR.enable(); fputs("<malloc version=\"scudo-1\">\n", stream); for (scudo::uptr i = 0; i != max_size; ++i) diff --git a/contrib/llvm-project/compiler-rt/lib/scudo/standalone/wrappers_c_bionic.cpp b/contrib/llvm-project/compiler-rt/lib/scudo/standalone/wrappers_c_bionic.cpp index 18c3bf2c0edf..1b9fe67d920c 100644 --- a/contrib/llvm-project/compiler-rt/lib/scudo/standalone/wrappers_c_bionic.cpp +++ b/contrib/llvm-project/compiler-rt/lib/scudo/standalone/wrappers_c_bionic.cpp @@ -32,21 +32,6 @@ static scudo::Allocator<scudo::AndroidConfig, SCUDO_PREFIX(malloc_postinit)> #undef SCUDO_ALLOCATOR #undef SCUDO_PREFIX -// Svelte MallocDispatch definitions. -#define SCUDO_PREFIX(name) CONCATENATE(scudo_svelte_, name) -#define SCUDO_ALLOCATOR SvelteAllocator - -extern "C" void SCUDO_PREFIX(malloc_postinit)(); -SCUDO_REQUIRE_CONSTANT_INITIALIZATION -static scudo::Allocator<scudo::AndroidSvelteConfig, - SCUDO_PREFIX(malloc_postinit)> - SCUDO_ALLOCATOR; - -#include "wrappers_c.inc" - -#undef SCUDO_ALLOCATOR -#undef SCUDO_PREFIX - // TODO(kostyak): support both allocators. INTERFACE void __scudo_print_stats(void) { Allocator.printStats(); } diff --git a/contrib/llvm-project/compiler-rt/lib/scudo/standalone/wrappers_c_checks.h b/contrib/llvm-project/compiler-rt/lib/scudo/standalone/wrappers_c_checks.h index 815d40023b6a..9cd48e82792e 100644 --- a/contrib/llvm-project/compiler-rt/lib/scudo/standalone/wrappers_c_checks.h +++ b/contrib/llvm-project/compiler-rt/lib/scudo/standalone/wrappers_c_checks.h @@ -64,7 +64,7 @@ inline bool checkForCallocOverflow(uptr Size, uptr N, uptr *Product) { // Returns true if the size passed to pvalloc overflows when rounded to the next // multiple of PageSize. inline bool checkForPvallocOverflow(uptr Size, uptr PageSize) { - return roundUpTo(Size, PageSize) < Size; + return roundUp(Size, PageSize) < Size; } } // namespace scudo |