bmalloc: use a log scale for large-ish size classes
authorggaren@apple.com <ggaren@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Wed, 23 Mar 2016 01:39:36 +0000 (01:39 +0000)
committerggaren@apple.com <ggaren@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Wed, 23 Mar 2016 01:39:36 +0000 (01:39 +0000)
https://bugs.webkit.org/show_bug.cgi?id=155770

Reviewed by Michael Saboff.

At larger sizes, precise allocation sizes don't save much memory -- and
they can cost memory when objects of distinct size classes can't
allocate together.

This is a small savings up to our current allocation limits, and it may
enable changing those limits in the long term.

* bmalloc/Algorithm.h:
(bmalloc::log2): We use this to compute large-ish size classes.

* bmalloc/Allocator.cpp:
(bmalloc::Allocator::Allocator): Iterate by size class instead of by
object size so we can change object size limits without breaking stuff.

(bmalloc::Allocator::scavenge): Ditto.

(bmalloc::Allocator::allocateLogSizeClass): New helper function for
allocating based on log size classes.

(bmalloc::Allocator::allocateSlowCase): Account for extra size class
possibilities.

* bmalloc/Allocator.h:
(bmalloc::Allocator::allocateFastCase): We only handle up to 512b on
the fastest fast path now.

* bmalloc/BumpAllocator.h:
(bmalloc::BumpAllocator::validate): Deleted. I noticed that this function
had been refactored not to do anything anymore.

* bmalloc/Heap.cpp:
(bmalloc::Heap::initializeLineMetadata): Iterate by size class. (See
Allocator::Allocator.)

* bmalloc/Heap.h: Use the sizeClassCount constant instead of hard coding
things.

* bmalloc/Sizes.h:
(bmalloc::Sizes::maskSizeClass):
(bmalloc::Sizes::maskObjectSize):
(bmalloc::Sizes::logSizeClass):
(bmalloc::Sizes::logObjectSize):
(bmalloc::Sizes::sizeClass):
(bmalloc::Sizes::objectSize): Separate size class calculation between
simple size classes that can be computed with a mask and are 8-byte-precise
and complex size classes that require more math and are less precise.

* bmalloc/SmallLine.h:
(bmalloc::SmallLine::ref):
* bmalloc/SmallPage.h:
(bmalloc::SmallPage::SmallPage):
(bmalloc::SmallPage::ref):
(bmalloc::SmallPage::deref): Cleaned up some ASSERTs that triggered
while working on this patch.

* bmalloc/Zone.cpp:
(bmalloc::statistics):
(bmalloc::zoneSize):
(bmalloc::Zone::Zone):
(bmalloc::size): Deleted. Renamed these symbols to work around an lldb
bug that makes it impossible to print out variables named 'size' -- which
can be a problem when working on malloc.

git-svn-id: https://svn.webkit.org/repository/webkit/trunk@198571 268f45cc-cd09-0410-ab3c-d52691b4dbfc

Source/bmalloc/ChangeLog
Source/bmalloc/bmalloc/Algorithm.h
Source/bmalloc/bmalloc/Allocator.cpp
Source/bmalloc/bmalloc/Allocator.h
Source/bmalloc/bmalloc/BumpAllocator.h
Source/bmalloc/bmalloc/Heap.cpp
Source/bmalloc/bmalloc/Heap.h
Source/bmalloc/bmalloc/Sizes.h
Source/bmalloc/bmalloc/SmallLine.h
Source/bmalloc/bmalloc/SmallPage.h
Source/bmalloc/bmalloc/Zone.cpp

index b539e29..4f1f7cd 100644 (file)
@@ -1,5 +1,75 @@
 2016-03-22  Geoffrey Garen  <ggaren@apple.com>
 
+        bmalloc: use a log scale for large-ish size classes
+        https://bugs.webkit.org/show_bug.cgi?id=155770
+
+        Reviewed by Michael Saboff.
+
+        At larger sizes, precise allocation sizes don't save much memory -- and
+        they can cost memory when objects of distinct size classes can't
+        allocate together.
+
+        This is a small savings up to our current allocation limits, and it may
+        enable changing those limits in the long term.
+
+        * bmalloc/Algorithm.h:
+        (bmalloc::log2): We use this to compute large-ish size classes.
+
+        * bmalloc/Allocator.cpp:
+        (bmalloc::Allocator::Allocator): Iterate by size class instead of by
+        object size so we can change object size limits without breaking stuff.
+
+        (bmalloc::Allocator::scavenge): Ditto.
+
+        (bmalloc::Allocator::allocateLogSizeClass): New helper function for
+        allocating based on log size classes.
+
+        (bmalloc::Allocator::allocateSlowCase): Account for extra size class
+        possibilities.
+
+        * bmalloc/Allocator.h:
+        (bmalloc::Allocator::allocateFastCase): We only handle up to 512b on
+        the fastest fast path now.
+
+        * bmalloc/BumpAllocator.h:
+        (bmalloc::BumpAllocator::validate): Deleted. I noticed that this function
+        had been refactored not to do anything anymore.
+
+        * bmalloc/Heap.cpp:
+        (bmalloc::Heap::initializeLineMetadata): Iterate by size class. (See
+        Allocator::Allocator.)
+
+        * bmalloc/Heap.h: Use the sizeClassCount constant instead of hard coding
+        things.
+
+        * bmalloc/Sizes.h:
+        (bmalloc::Sizes::maskSizeClass):
+        (bmalloc::Sizes::maskObjectSize):
+        (bmalloc::Sizes::logSizeClass):
+        (bmalloc::Sizes::logObjectSize):
+        (bmalloc::Sizes::sizeClass):
+        (bmalloc::Sizes::objectSize): Separate size class calculation between
+        simple size classes that can be computed with a mask and are 8-byte-precise
+        and complex size classes that require more math and are less precise.
+
+        * bmalloc/SmallLine.h:
+        (bmalloc::SmallLine::ref):
+        * bmalloc/SmallPage.h:
+        (bmalloc::SmallPage::SmallPage):
+        (bmalloc::SmallPage::ref):
+        (bmalloc::SmallPage::deref): Cleaned up some ASSERTs that triggered
+        while working on this patch.
+
+        * bmalloc/Zone.cpp:
+        (bmalloc::statistics):
+        (bmalloc::zoneSize):
+        (bmalloc::Zone::Zone):
+        (bmalloc::size): Deleted. Renamed these symbols to work around an lldb
+        bug that makes it impossible to print out variables named 'size' -- which
+        can be a problem when working on malloc.
+
+2016-03-22  Geoffrey Garen  <ggaren@apple.com>
+
         bmalloc: shrink largeMax
         https://bugs.webkit.org/show_bug.cgi?id=155759
 
index 30ed141..277a1b0 100644 (file)
@@ -108,6 +108,11 @@ template<typename T> inline constexpr size_t bitCount()
     return sizeof(T) * 8;
 }
 
+inline constexpr unsigned long log2(unsigned long value)
+{
+    return bitCount<unsigned long>() - 1 - __builtin_clzl(value);
+}
+
 } // namespace bmalloc
 
 #endif // Algorithm_h
index 23514eb..c9190e9 100644 (file)
@@ -42,8 +42,8 @@ Allocator::Allocator(Heap* heap, Deallocator& deallocator)
     : m_isBmallocEnabled(heap->environment().isBmallocEnabled())
     , m_deallocator(deallocator)
 {
-    for (unsigned short size = alignment; size <= smallMax; size += alignment)
-        m_bumpAllocators[sizeClass(size)].init(size);
+    for (size_t sizeClass = 0; sizeClass < sizeClassCount; ++sizeClass)
+        m_bumpAllocators[sizeClass].init(objectSize(sizeClass));
 }
 
 Allocator::~Allocator()
@@ -164,9 +164,9 @@ void* Allocator::reallocate(void* object, size_t newSize)
 
 void Allocator::scavenge()
 {
-    for (unsigned short i = alignment; i <= smallMax; i += alignment) {
-        BumpAllocator& allocator = m_bumpAllocators[sizeClass(i)];
-        BumpRangeCache& bumpRangeCache = m_bumpRangeCaches[sizeClass(i)];
+    for (size_t sizeClass = 0; sizeClass < sizeClassCount; ++sizeClass) {
+        BumpAllocator& allocator = m_bumpAllocators[sizeClass];
+        BumpRangeCache& bumpRangeCache = m_bumpRangeCaches[sizeClass];
 
         while (allocator.canAllocate())
             m_deallocator.deallocate(allocator.allocate());
@@ -210,18 +210,30 @@ NO_INLINE void* Allocator::allocateXLarge(size_t size)
     return PerProcess<Heap>::getFastCase()->allocateXLarge(lock, size);
 }
 
+NO_INLINE void* Allocator::allocateLogSizeClass(size_t size)
+{
+    size_t sizeClass = bmalloc::sizeClass(size);
+    BumpAllocator& allocator = m_bumpAllocators[sizeClass];
+    if (!allocator.canAllocate())
+        refillAllocator(allocator, sizeClass);
+    return allocator.allocate();
+}
+
 void* Allocator::allocateSlowCase(size_t size)
 {
     if (!m_isBmallocEnabled)
         return malloc(size);
 
-    if (size <= smallMax) {
-        size_t sizeClass = bmalloc::sizeClass(size);
+    if (size <= maskSizeClassMax) {
+        size_t sizeClass = bmalloc::maskSizeClass(size);
         BumpAllocator& allocator = m_bumpAllocators[sizeClass];
         refillAllocator(allocator, sizeClass);
         return allocator.allocate();
     }
 
+    if (size <= smallMax)
+        return allocateLogSizeClass(size);
+
     if (size <= largeMax)
         return allocateLarge(size);
 
index 5731837..206c786 100644 (file)
@@ -52,14 +52,15 @@ private:
     bool allocateFastCase(size_t, void*&);
     void* allocateSlowCase(size_t);
     
+    void* allocateLogSizeClass(size_t);
     void* allocateLarge(size_t);
     void* allocateXLarge(size_t);
     
     void refillAllocator(BumpAllocator&, size_t sizeClass);
     void refillAllocatorSlowCase(BumpAllocator&, size_t sizeClass);
     
-    std::array<BumpAllocator, smallMax / alignment> m_bumpAllocators;
-    std::array<BumpRangeCache, smallMax / alignment> m_bumpRangeCaches;
+    std::array<BumpAllocator, sizeClassCount> m_bumpAllocators;
+    std::array<BumpRangeCache, sizeClassCount> m_bumpRangeCaches;
 
     bool m_isBmallocEnabled;
     Deallocator& m_deallocator;
@@ -67,10 +68,10 @@ private:
 
 inline bool Allocator::allocateFastCase(size_t size, void*& object)
 {
-    if (size > smallMax)
+    if (size > maskSizeClassMax)
         return false;
 
-    BumpAllocator& allocator = m_bumpAllocators[sizeClass(size)];
+    BumpAllocator& allocator = m_bumpAllocators[maskSizeClass(size)];
     if (!allocator.canAllocate())
         return false;
 
index a8a1cea..87e920a 100644 (file)
@@ -50,8 +50,6 @@ public:
     void refill(const BumpRange&);
 
 private:
-    void validate(void*);
-
     char* m_ptr;
     unsigned short m_size;
     unsigned short m_remaining;
@@ -71,18 +69,6 @@ inline void BumpAllocator::init(size_t size)
     m_remaining = 0;
 }
 
-inline void BumpAllocator::validate(void* ptr)
-{
-    UNUSED(ptr);
-    if (m_size <= smallMax) {
-        BASSERT(isSmall(ptr));
-        return;
-    }
-    
-    BASSERT(m_size <= smallMax);
-    BASSERT(isSmall(ptr));
-}
-
 inline void* BumpAllocator::allocate()
 {
     BASSERT(m_remaining);
@@ -90,7 +76,7 @@ inline void* BumpAllocator::allocate()
     --m_remaining;
     char* result = m_ptr;
     m_ptr += m_size;
-    validate(result);
+    BASSERT(isSmall(result));
     return result;
 }
 
index c6cc510..f653529 100644 (file)
@@ -47,8 +47,8 @@ void Heap::initializeLineMetadata()
 {
     // We assume that m_smallLineMetadata is zero-filled.
 
-    for (size_t size = alignment; size <= smallMax; size += alignment) {
-        size_t sizeClass = bmalloc::sizeClass(size);
+    for (size_t sizeClass = 0; sizeClass < sizeClassCount; ++sizeClass) {
+        size_t size = objectSize(sizeClass);
         auto& metadata = m_smallLineMetadata[sizeClass];
 
         size_t object = 0;
index 1e680af..b257bee 100644 (file)
@@ -92,9 +92,9 @@ private:
     void scavengeLargeObjects(std::unique_lock<StaticMutex>&, std::chrono::milliseconds);
     void scavengeXLargeObjects(std::unique_lock<StaticMutex>&, std::chrono::milliseconds);
 
-    std::array<std::array<LineMetadata, smallLineCount>, smallMax / alignment> m_smallLineMetadata;
+    std::array<std::array<LineMetadata, smallLineCount>, sizeClassCount> m_smallLineMetadata;
 
-    std::array<List<SmallPage>, smallMax / alignment> m_smallPagesWithFreeLines;
+    std::array<List<SmallPage>, sizeClassCount> m_smallPagesWithFreeLines;
 
     List<SmallPage> m_smallPages;
 
index 5032467..291bcc2 100644 (file)
@@ -60,10 +60,12 @@ namespace Sizes {
     static const size_t smallChunkOffset = superChunkSize / 2;
     static const size_t smallChunkMask = ~(smallChunkSize - 1ul);
 
-    static const size_t smallMax = 1024;
     static const size_t smallLineSize = 256;
     static const size_t smallLineCount = vmPageSize / smallLineSize;
 
+    static const size_t smallMax = 1 * kB;
+    static const size_t maskSizeClassMax = 512;
+
     static const size_t largeChunkSize = superChunkSize / 2;
     static const size_t largeChunkOffset = 0;
     static const size_t largeChunkMask = ~(largeChunkSize - 1ul);
@@ -90,17 +92,54 @@ namespace Sizes {
     
     static const std::chrono::milliseconds scavengeSleepDuration = std::chrono::milliseconds(512);
 
+    static const size_t maskSizeClassCount = maskSizeClassMax / alignment;
+
+    inline constexpr size_t maskSizeClass(size_t size)
+    {
+        // We mask to accommodate zero.
+        return mask((size - 1) / alignment, maskSizeClassCount - 1);
+    }
+
+    inline size_t maskObjectSize(size_t maskSizeClass)
+    {
+        return (maskSizeClass + 1) * alignment;
+    }
+
+    static const size_t logWasteFactor = 8;
+    static const size_t logAlignmentMin = maskSizeClassMax / logWasteFactor;
+
+    static const size_t logSizeClassCount = (log2(smallMax) - log2(maskSizeClassMax)) * logWasteFactor;
+
+    inline size_t logSizeClass(size_t size)
+    {
+        size_t base = log2(size - 1) - log2(maskSizeClassMax);
+        size_t offset = (size - 1 - (maskSizeClassMax << base));
+        return base * logWasteFactor + offset / (logAlignmentMin << base);
+    }
+
+    inline size_t logObjectSize(size_t logSizeClass)
+    {
+        size_t base = logSizeClass / logWasteFactor;
+        size_t offset = logSizeClass % logWasteFactor;
+        return (maskSizeClassMax << base) + (offset + 1) * (logAlignmentMin << base);
+    }
+
+    static const size_t sizeClassCount = maskSizeClassCount + logSizeClassCount;
+
     inline size_t sizeClass(size_t size)
     {
-        static const size_t sizeClassMask = (smallMax / alignment) - 1;
-        return mask((size - 1) / alignment, sizeClassMask);
+        if (size <= maskSizeClassMax)
+            return maskSizeClass(size);
+        return maskSizeClassCount + logSizeClass(size);
     }
 
     inline size_t objectSize(size_t sizeClass)
     {
-        return (sizeClass + 1) * alignment;
+        if (sizeClass < maskSizeClassCount)
+            return maskObjectSize(sizeClass);
+        return logObjectSize(sizeClass - maskSizeClassCount);
     }
-};
+}
 
 using namespace Sizes;
 
index e044e70..70824d6 100644 (file)
@@ -35,9 +35,6 @@ namespace bmalloc {
 
 class SmallLine {
 public:
-    static const unsigned char maxRefCount = std::numeric_limits<unsigned char>::max();
-    static_assert(smallLineSize / alignment < maxRefCount, "maximum object count must fit in Line");
-
     static SmallLine* get(void*);
 
     void ref(std::lock_guard<StaticMutex>&, unsigned char);
@@ -49,6 +46,11 @@ public:
 
 private:
     unsigned char m_refCount;
+
+static_assert(
+    smallLineSize / alignment <= std::numeric_limits<decltype(m_refCount)>::max(),
+    "maximum object count must fit in SmallLine::m_refCount");
+
 };
 
 inline void SmallLine::ref(std::lock_guard<StaticMutex>&, unsigned char refCount)
index 21aa461..6a0d6e0 100644 (file)
@@ -36,9 +36,6 @@ namespace bmalloc {
 
 class SmallPage : public ListNode<SmallPage> {
 public:
-    static const unsigned char maxRefCount = std::numeric_limits<unsigned char>::max();
-    static_assert(smallLineCount < maxRefCount, "maximum line count must fit in SmallPage");
-    
     static SmallPage* get(SmallLine*);
 
     SmallPage()
@@ -63,12 +60,16 @@ private:
     unsigned char m_hasFreeLines: 1;
     unsigned char m_refCount: 7;
     unsigned char m_sizeClass;
+
+static_assert(
+    sizeClassCount <= std::numeric_limits<decltype(m_sizeClass)>::max(),
+    "Largest size class must fit in SmallPage metadata");
 };
 
 inline void SmallPage::ref(std::lock_guard<StaticMutex>&)
 {
-    BASSERT(m_refCount < maxRefCount);
     ++m_refCount;
+    BASSERT(m_refCount);
 }
 
 inline bool SmallPage::deref(std::lock_guard<StaticMutex>&)
index 72c6aea..6eb7dac 100644 (file)
@@ -78,7 +78,7 @@ static void statistics(malloc_zone_t*, malloc_statistics_t* statistics)
     memset(statistics, 0, sizeof(malloc_statistics_t));
 }
 
-static size_t size(malloc_zone_t*, const void*)
+static size_t zoneSize(malloc_zone_t*, const void*)
 {
     // Our zone is not public API, so no pointer can belong to us.
     return 0;
@@ -104,7 +104,7 @@ static kern_return_t enumerator(task_t task, void* context, unsigned type_mask,
 // The memory analysis API requires the contents of this struct to be a static
 // constant in the program binary. The leaks process will load this struct
 // out of the program binary (and not out of the running process).
-static malloc_introspection_t introspect = {
+static malloc_introspection_t zoneIntrospect = {
     .enumerator = bmalloc::enumerator,
     .good_size = bmalloc::good_size,
     .check = bmalloc::check,
@@ -117,9 +117,9 @@ static malloc_introspection_t introspect = {
 
 Zone::Zone()
 {
-    malloc_zone_t::size = &bmalloc::size;
+    malloc_zone_t::size = &bmalloc::zoneSize;
     malloc_zone_t::zone_name = "WebKit Malloc";
-    malloc_zone_t::introspect = &bmalloc::introspect;
+    malloc_zone_t::introspect = &bmalloc::zoneIntrospect;
     malloc_zone_t::version = 4;
     malloc_zone_register(this);
 }