Index: lib/sanitizer_common/sanitizer_allocator_local_cache.h =================================================================== --- lib/sanitizer_common/sanitizer_allocator_local_cache.h +++ lib/sanitizer_common/sanitizer_allocator_local_cache.h @@ -26,9 +26,6 @@ template struct SizeClassAllocator64LocalCache { typedef SizeClassAllocator Allocator; - static const uptr kNumClasses = SizeClassAllocator::kNumClasses; - typedef typename Allocator::SizeClassMapT SizeClassMap; - typedef typename Allocator::CompactPtrT CompactPtrT; void Init(AllocatorGlobalStats *s) { stats_.Init(); @@ -76,14 +73,18 @@ } void Drain(SizeClassAllocator *allocator) { - for (uptr class_id = 0; class_id < kNumClasses; class_id++) { - PerClass *c = &per_class_[class_id]; + for (uptr i = 0; i < kNumClasses; i++) { + PerClass *c = &per_class_[i]; while (c->count > 0) - Drain(c, allocator, class_id, c->count); + Drain(c, allocator, i, c->count); } } - // private: + private: + static const uptr kNumClasses = SizeClassAllocator::kNumClasses; + typedef typename Allocator::SizeClassMapT SizeClassMap; + typedef typename Allocator::CompactPtrT CompactPtrT; + struct PerClass { u32 count; u32 max_count; @@ -94,7 +95,7 @@ AllocatorStats stats_; void InitCache() { - if (per_class_[1].max_count) + if (LIKELY(per_class_[1].max_count)) return; for (uptr i = 0; i < kNumClasses; i++) { PerClass *c = &per_class_[i]; @@ -130,7 +131,6 @@ struct SizeClassAllocator32LocalCache { typedef SizeClassAllocator Allocator; typedef typename Allocator::TransferBatch TransferBatch; - static const uptr kNumClasses = SizeClassAllocator::kNumClasses; void Init(AllocatorGlobalStats *s) { stats_.Init(); @@ -138,6 +138,21 @@ s->Register(&stats_); } + // Returns a TransferBatch suitable for class_id. + TransferBatch *CreateBatch(uptr class_id, SizeClassAllocator *allocator, + TransferBatch *b) { + if (uptr batch_class_id = per_class_[class_id].batch_class_id) + return (TransferBatch*)Allocate(allocator, batch_class_id); + return b; + } + + // Destroys TransferBatch b. + void DestroyBatch(uptr class_id, SizeClassAllocator *allocator, + TransferBatch *b) { + if (uptr batch_class_id = per_class_[class_id].batch_class_id) + Deallocate(allocator, batch_class_id, b); + } + void Destroy(SizeClassAllocator *allocator, AllocatorGlobalStats *s) { Drain(allocator); if (s) @@ -173,66 +188,57 @@ } void Drain(SizeClassAllocator *allocator) { - for (uptr class_id = 0; class_id < kNumClasses; class_id++) { - PerClass *c = &per_class_[class_id]; + for (uptr i = 0; i < kNumClasses; i++) { + PerClass *c = &per_class_[i]; while (c->count > 0) - Drain(allocator, class_id); + Drain(allocator, i); } } - // private: - typedef typename SizeClassAllocator::SizeClassMapT SizeClassMap; + private: + typedef typename Allocator::SizeClassMapT SizeClassMap; + static const uptr kBatchClassID = SizeClassMap::kBatchClassID; + static const uptr kNumClasses = SizeClassMap::kNumClasses; + // If kUseSeparateSizeClassForBatch is true, all TransferBatch objects are + // allocated from kBatchClassID size class (except for those that are needed + // for kBatchClassID itself). The goal is to have TransferBatches in a totally + // different region of RAM to improve security. + static const bool kUseSeparateSizeClassForBatch = + Allocator::kUseSeparateSizeClassForBatch; + struct PerClass { uptr count; uptr max_count; uptr class_size; - uptr class_id_for_transfer_batch; + uptr batch_class_id; void *batch[2 * TransferBatch::kMaxNumCached]; }; PerClass per_class_[kNumClasses]; AllocatorStats stats_; void InitCache() { - if (per_class_[1].max_count) + if (LIKELY(per_class_[1].max_count)) return; - // TransferBatch class is declared in SizeClassAllocator. - uptr class_id_for_transfer_batch = - SizeClassMap::ClassID(sizeof(TransferBatch)); + const uptr batch_class_id = SizeClassMap::ClassID(sizeof(TransferBatch)); for (uptr i = 0; i < kNumClasses; i++) { PerClass *c = &per_class_[i]; uptr max_cached = TransferBatch::MaxCached(i); c->max_count = 2 * max_cached; c->class_size = Allocator::ClassIdToSize(i); - // We transfer chunks between central and thread-local free lists in - // batches. For small size classes we allocate batches separately. For - // large size classes we may use one of the chunks to store the batch. - // sizeof(TransferBatch) must be a power of 2 for more efficient - // allocation. - c->class_id_for_transfer_batch = (c->class_size < + // Precompute the class id to use to store batches for the current class + // id. 0 means the class size is large enough to store a batch within one + // of the chunks. If using a separate size class, it will always be + // kBatchClassID, except for kBatchClassID itself. + if (kUseSeparateSizeClassForBatch) { + c->batch_class_id = (i == kBatchClassID) ? 0 : kBatchClassID; + } else { + c->batch_class_id = (c->class_size < TransferBatch::AllocationSizeRequiredForNElements(max_cached)) ? - class_id_for_transfer_batch : 0; + batch_class_id : 0; + } } } - // Returns a TransferBatch suitable for class_id. - // For small size classes allocates the batch from the allocator. - // For large size classes simply returns b. - TransferBatch *CreateBatch(uptr class_id, SizeClassAllocator *allocator, - TransferBatch *b) { - if (uptr batch_class_id = per_class_[class_id].class_id_for_transfer_batch) - return (TransferBatch*)Allocate(allocator, batch_class_id); - return b; - } - - // Destroys TransferBatch b. - // For small size classes deallocates b to the allocator. - // Does notthing for large size classes. - void DestroyBatch(uptr class_id, SizeClassAllocator *allocator, - TransferBatch *b) { - if (uptr batch_class_id = per_class_[class_id].class_id_for_transfer_batch) - Deallocate(allocator, batch_class_id, b); - } - NOINLINE bool Refill(SizeClassAllocator *allocator, uptr class_id) { InitCache(); PerClass *c = &per_class_[class_id]; Index: lib/sanitizer_common/sanitizer_allocator_primary32.h =================================================================== --- lib/sanitizer_common/sanitizer_allocator_primary32.h +++ lib/sanitizer_common/sanitizer_allocator_primary32.h @@ -41,6 +41,7 @@ struct SizeClassAllocator32FlagMasks { // Bit masks. enum { kRandomShuffleChunks = 1, + kUseSeparateSizeClassForBatch = 2, }; }; @@ -55,8 +56,10 @@ typedef typename Params::ByteMap ByteMap; typedef typename Params::MapUnmapCallback MapUnmapCallback; - static const bool kRandomShuffleChunks = - Params::kFlags & SizeClassAllocator32FlagMasks::kRandomShuffleChunks; + static const bool kRandomShuffleChunks = Params::kFlags & + SizeClassAllocator32FlagMasks::kRandomShuffleChunks; + static const bool kUseSeparateSizeClassForBatch = Params::kFlags & + SizeClassAllocator32FlagMasks::kUseSeparateSizeClassForBatch; struct TransferBatch { static const uptr kMaxNumCached = SizeClassMap::kMaxNumCachedHint - 2; @@ -94,11 +97,11 @@ static const uptr kBatchSize = sizeof(TransferBatch); COMPILER_CHECK((kBatchSize & (kBatchSize - 1)) == 0); - COMPILER_CHECK(sizeof(TransferBatch) == - SizeClassMap::kMaxNumCachedHint * sizeof(uptr)); + COMPILER_CHECK(kBatchSize == SizeClassMap::kMaxNumCachedHint * sizeof(uptr)); static uptr ClassIdToSize(uptr class_id) { - return SizeClassMap::Size(class_id); + return (class_id == SizeClassMap::kBatchClassID) ? + kBatchSize : SizeClassMap::Size(class_id); } typedef SizeClassAllocator32 ThisT; @@ -161,9 +164,9 @@ NOINLINE void DeallocateBatch(AllocatorStats *stat, uptr class_id, TransferBatch *b) { CHECK_LT(class_id, kNumClasses); + CHECK_GT(b->Count(), 0); SizeClassInfo *sci = GetSizeClassInfo(class_id); SpinMutexLock l(&sci->mutex); - CHECK_GT(b->Count(), 0); sci->free_list.push_front(b); } Index: lib/sanitizer_common/sanitizer_allocator_size_class_map.h =================================================================== --- lib/sanitizer_common/sanitizer_allocator_size_class_map.h +++ lib/sanitizer_common/sanitizer_allocator_size_class_map.h @@ -134,8 +134,9 @@ static const uptr kMaxSize = 1UL << kMaxSizeLog; static const uptr kNumClasses = - kMidClass + ((kMaxSizeLog - kMidSizeLog) << S) + 1; + kMidClass + ((kMaxSizeLog - kMidSizeLog) << S) + 1 + 1; static const uptr kLargestClassID = kNumClasses - 2; + static const uptr kBatchClassID = kNumClasses - 1; COMPILER_CHECK(kNumClasses >= 16 && kNumClasses <= 256); static const uptr kNumClassesRounded = kNumClasses <= 32 ? 32 : @@ -143,6 +144,11 @@ kNumClasses <= 128 ? 128 : 256; static uptr Size(uptr class_id) { + // Estimate the result for kBatchClassID because this class does not know + // the exact size of TransferBatch. It's OK since we are using the actual + // sizeof(TransferBatch) where it matters. + if (UNLIKELY(class_id == kBatchClassID)) + return kMaxNumCachedHint * sizeof(uptr); if (class_id <= kMidClass) return kMinSize * class_id; class_id -= kMidClass; @@ -151,9 +157,10 @@ } static uptr ClassID(uptr size) { + if (UNLIKELY(size > kMaxSize)) + return 0; if (size <= kMidSize) return (size + kMinSize - 1) >> kMinSizeLog; - if (size > kMaxSize) return 0; uptr l = MostSignificantSetBitIndex(size); uptr hbits = (size >> (l - S)) & M; uptr lbits = size & ((1 << (l - S)) - 1); @@ -162,7 +169,13 @@ } static uptr MaxCachedHint(uptr class_id) { - if (class_id == 0) return 0; + // Estimate the result for kBatchClassID because this class does not know + // the exact size of TransferBatch. We need to cache fewer batches than user + // chunks, so this number can be small. + if (UNLIKELY(class_id == kBatchClassID)) + return 16; + if (UNLIKELY(class_id == 0)) + return 0; uptr n = (1UL << kMaxBytesCachedLog) / Size(class_id); return Max(1, Min(kMaxNumCachedHint, n)); } @@ -178,6 +191,8 @@ uptr p = prev_s ? (d * 100 / prev_s) : 0; uptr l = s ? MostSignificantSetBitIndex(s) : 0; uptr cached = MaxCachedHint(i) * s; + if (i == kBatchClassID) + d = p = l = 0; Printf("c%02zd => s: %zd diff: +%zd %02zd%% l %zd " "cached: %zd %zd; id %zd\n", i, Size(i), d, p, l, MaxCachedHint(i), cached, ClassID(s)); @@ -188,16 +203,15 @@ } static void Validate() { - for (uptr c = 1; c < kNumClasses; c++) { + for (uptr c = 1; c <= kLargestClassID; c++) { // Printf("Validate: c%zd\n", c); uptr s = Size(c); CHECK_NE(s, 0U); CHECK_EQ(ClassID(s), c); - if (c != kNumClasses - 1) + if (c != kLargestClassID) CHECK_EQ(ClassID(s + 1), c + 1); CHECK_EQ(ClassID(s - 1), c); - if (c) - CHECK_GT(Size(c), Size(c-1)); + CHECK_GT(Size(c), Size(c - 1)); } CHECK_EQ(ClassID(kMaxSize + 1), 0); @@ -207,7 +221,7 @@ CHECK_LT(c, kNumClasses); CHECK_GE(Size(c), s); if (c > 0) - CHECK_LT(Size(c-1), s); + CHECK_LT(Size(c - 1), s); } } }; Index: lib/sanitizer_common/tests/sanitizer_allocator_test.cc =================================================================== --- lib/sanitizer_common/tests/sanitizer_allocator_test.cc +++ lib/sanitizer_common/tests/sanitizer_allocator_test.cc @@ -240,6 +240,23 @@ TestSizeClassAllocator(); } +struct AP32SeparateBatches { + static const uptr kSpaceBeg = 0; + static const u64 kSpaceSize = kAddressSpaceSize; + static const uptr kMetadataSize = 16; + typedef DefaultSizeClassMap SizeClassMap; + static const uptr kRegionSizeLog = ::kRegionSizeLog; + typedef FlatByteMap ByteMap; + typedef NoOpMapUnmapCallback MapUnmapCallback; + static const uptr kFlags = + SizeClassAllocator32FlagMasks::kUseSeparateSizeClassForBatch; +}; +typedef SizeClassAllocator32 Allocator32SeparateBatches; + +TEST(SanitizerCommon, SizeClassAllocator32SeparateBatches) { + TestSizeClassAllocator(); +} + template void SizeClassAllocatorMetadataStress() { Allocator *a = new Allocator; Index: lib/scudo/scudo_allocator.h =================================================================== --- lib/scudo/scudo_allocator.h +++ lib/scudo/scudo_allocator.h @@ -23,10 +23,10 @@ namespace __scudo { enum AllocType : u8 { - FromMalloc = 0, // Memory block came from malloc, realloc, calloc, etc. - FromNew = 1, // Memory block came from operator new. - FromNewArray = 2, // Memory block came from operator new []. - FromMemalign = 3, // Memory block came from memalign, posix_memalign, etc. + FromMalloc = 0, // Memory block came from malloc, realloc, calloc, etc. + FromNew = 1, // Memory block came from operator new. + FromNewArray = 2, // Memory block came from operator new []. + FromMemalign = 3, // Memory block came from memalign, posix_memalign, etc. }; enum ChunkState : u8 { @@ -43,15 +43,15 @@ typedef u64 PackedHeader; struct UnpackedHeader { u64 Checksum : 16; - u64 SizeOrUnusedBytes : 19; // Size for Primary backed allocations, amount of - // unused bytes in the chunk for Secondary ones. + u64 SizeOrUnusedBytes : 19; // Size for Primary backed allocations, amount of + // unused bytes in the chunk for Secondary ones. u64 FromPrimary : 1; - u64 State : 2; // available, allocated, or quarantined - u64 AllocType : 2; // malloc, new, new[], or memalign - u64 Offset : 16; // Offset from the beginning of the backend - // allocation to the beginning of the chunk - // itself, in multiples of MinAlignment. See - // comment about its maximum value and in init(). + u64 State : 2; // available, allocated, or quarantined + u64 AllocType : 2; // malloc, new, new[], or memalign + u64 Offset : 16; // Offset from the beginning of the backend + // allocation to the beginning of the chunk + // itself, in multiples of MinAlignment. See + // comment about its maximum value and in init(). u64 Salt : 8; }; @@ -109,7 +109,8 @@ typedef __scudo::ByteMap ByteMap; typedef NoOpMapUnmapCallback MapUnmapCallback; static const uptr kFlags = - SizeClassAllocator32FlagMasks::kRandomShuffleChunks; + SizeClassAllocator32FlagMasks::kRandomShuffleChunks | + SizeClassAllocator32FlagMasks::kUseSeparateSizeClassForBatch; }; typedef SizeClassAllocator32 PrimaryAllocator; #endif // SANITIZER_CAN_USE_ALLOCATOR64