Diff
Modified: trunk/Source/bmalloc/ChangeLog (198570 => 198571)
--- trunk/Source/bmalloc/ChangeLog 2016-03-23 01:38:49 UTC (rev 198570)
+++ trunk/Source/bmalloc/ChangeLog 2016-03-23 01:39:36 UTC (rev 198571)
@@ -1,5 +1,75 @@
2016-03-22 Geoffrey Garen <[email protected]>
+ 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 <[email protected]>
+
bmalloc: shrink largeMax
https://bugs.webkit.org/show_bug.cgi?id=155759
Modified: trunk/Source/bmalloc/bmalloc/Algorithm.h (198570 => 198571)
--- trunk/Source/bmalloc/bmalloc/Algorithm.h 2016-03-23 01:38:49 UTC (rev 198570)
+++ trunk/Source/bmalloc/bmalloc/Algorithm.h 2016-03-23 01:39:36 UTC (rev 198571)
@@ -108,6 +108,11 @@
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
Modified: trunk/Source/bmalloc/bmalloc/Allocator.cpp (198570 => 198571)
--- trunk/Source/bmalloc/bmalloc/Allocator.cpp 2016-03-23 01:38:49 UTC (rev 198570)
+++ trunk/Source/bmalloc/bmalloc/Allocator.cpp 2016-03-23 01:39:36 UTC (rev 198571)
@@ -42,8 +42,8 @@
: 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::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 @@
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);
Modified: trunk/Source/bmalloc/bmalloc/Allocator.h (198570 => 198571)
--- trunk/Source/bmalloc/bmalloc/Allocator.h 2016-03-23 01:38:49 UTC (rev 198570)
+++ trunk/Source/bmalloc/bmalloc/Allocator.h 2016-03-23 01:39:36 UTC (rev 198571)
@@ -52,14 +52,15 @@
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 @@
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;
Modified: trunk/Source/bmalloc/bmalloc/BumpAllocator.h (198570 => 198571)
--- trunk/Source/bmalloc/bmalloc/BumpAllocator.h 2016-03-23 01:38:49 UTC (rev 198570)
+++ trunk/Source/bmalloc/bmalloc/BumpAllocator.h 2016-03-23 01:39:36 UTC (rev 198571)
@@ -50,8 +50,6 @@
void refill(const BumpRange&);
private:
- void validate(void*);
-
char* m_ptr;
unsigned short m_size;
unsigned short m_remaining;
@@ -71,18 +69,6 @@
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 @@
--m_remaining;
char* result = m_ptr;
m_ptr += m_size;
- validate(result);
+ BASSERT(isSmall(result));
return result;
}
Modified: trunk/Source/bmalloc/bmalloc/Heap.cpp (198570 => 198571)
--- trunk/Source/bmalloc/bmalloc/Heap.cpp 2016-03-23 01:38:49 UTC (rev 198570)
+++ trunk/Source/bmalloc/bmalloc/Heap.cpp 2016-03-23 01:39:36 UTC (rev 198571)
@@ -47,8 +47,8 @@
{
// 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;
Modified: trunk/Source/bmalloc/bmalloc/Heap.h (198570 => 198571)
--- trunk/Source/bmalloc/bmalloc/Heap.h 2016-03-23 01:38:49 UTC (rev 198570)
+++ trunk/Source/bmalloc/bmalloc/Heap.h 2016-03-23 01:39:36 UTC (rev 198571)
@@ -92,9 +92,9 @@
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;
Modified: trunk/Source/bmalloc/bmalloc/Sizes.h (198570 => 198571)
--- trunk/Source/bmalloc/bmalloc/Sizes.h 2016-03-23 01:38:49 UTC (rev 198570)
+++ trunk/Source/bmalloc/bmalloc/Sizes.h 2016-03-23 01:39:36 UTC (rev 198571)
@@ -60,10 +60,12 @@
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 @@
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;
Modified: trunk/Source/bmalloc/bmalloc/SmallLine.h (198570 => 198571)
--- trunk/Source/bmalloc/bmalloc/SmallLine.h 2016-03-23 01:38:49 UTC (rev 198570)
+++ trunk/Source/bmalloc/bmalloc/SmallLine.h 2016-03-23 01:39:36 UTC (rev 198571)
@@ -35,9 +35,6 @@
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 @@
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)
Modified: trunk/Source/bmalloc/bmalloc/SmallPage.h (198570 => 198571)
--- trunk/Source/bmalloc/bmalloc/SmallPage.h 2016-03-23 01:38:49 UTC (rev 198570)
+++ trunk/Source/bmalloc/bmalloc/SmallPage.h 2016-03-23 01:39:36 UTC (rev 198571)
@@ -36,9 +36,6 @@
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 @@
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>&)
Modified: trunk/Source/bmalloc/bmalloc/Zone.cpp (198570 => 198571)
--- trunk/Source/bmalloc/bmalloc/Zone.cpp 2016-03-23 01:38:49 UTC (rev 198570)
+++ trunk/Source/bmalloc/bmalloc/Zone.cpp 2016-03-23 01:39:36 UTC (rev 198571)
@@ -78,7 +78,7 @@
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 @@
// 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 @@
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);
}
