bmalloc uses 8X more virtual memory than necessary
authorggaren@apple.com <ggaren@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Fri, 7 Nov 2014 18:12:40 +0000 (18:12 +0000)
committerggaren@apple.com <ggaren@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Fri, 7 Nov 2014 18:12:40 +0000 (18:12 +0000)
https://bugs.webkit.org/show_bug.cgi?id=138495

Reviewed by Mark Lam.

iOS has a per-process virtual memory cap around 1GB, so there's some
value to not going totally ham with virtual memory.

We currently use about 8X the necessary amount:
    - 2X to align our VM allocation
    - 4X to reserve small / medium / (2) large chunk VM ranges per superchunk

We can cut that down:
    - Return the unaligned portion of our VM allocation (-2X)
    - Use all the chunks in a superchunk, instead of allocating one
      chunk per superchunk (-4X)

* bmalloc/Algorithm.h:
(bmalloc::roundUpToMultipleOf): Added a non-constant version of this
function so we can call it with getpagesize() at runtime.

* bmalloc/Chunk.h:
* bmalloc/LargeChunk.h:
(bmalloc::LargeChunk::create): Deleted. Instead of each chunk allocating
its own VM, VMHeap allocates the superchunk and all the chunks in it at a time.

* bmalloc/VMAllocate.h:
(bmalloc::vmValidate):
(bmalloc::vmAllocate): ASSERT that mmap succeeds to make crashes clearer
if it does not succeed. Allocate precisely, and give back the extra.

* bmalloc/VMHeap.cpp:
(bmalloc::VMHeap::allocateSuperChunk):
(bmalloc::VMHeap::allocateSmallChunk): Deleted.
(bmalloc::VMHeap::allocateMediumChunk): Deleted.
(bmalloc::VMHeap::allocateLargeChunk): Deleted. Use all the chunks
in a superchunk, instead of just one.

* bmalloc/VMHeap.h:
(bmalloc::VMHeap::allocateSmallPage):
(bmalloc::VMHeap::allocateMediumPage):
(bmalloc::VMHeap::allocateLargeRange):
* bmalloc/XLargeChunk.h:
(bmalloc::XLargeChunk::create): Updated to match changes above.

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

Source/bmalloc/ChangeLog
Source/bmalloc/bmalloc/Algorithm.h
Source/bmalloc/bmalloc/Chunk.h
Source/bmalloc/bmalloc/LargeChunk.h
Source/bmalloc/bmalloc/VMAllocate.h
Source/bmalloc/bmalloc/VMHeap.cpp
Source/bmalloc/bmalloc/VMHeap.h
Source/bmalloc/bmalloc/XLargeChunk.h

index 0f8da7b..46d1e6e 100644 (file)
@@ -1,3 +1,50 @@
+2014-11-07  Geoffrey Garen  <ggaren@apple.com>
+
+        bmalloc uses 8X more virtual memory than necessary
+        https://bugs.webkit.org/show_bug.cgi?id=138495
+
+        Reviewed by Mark Lam.
+
+        iOS has a per-process virtual memory cap around 1GB, so there's some
+        value to not going totally ham with virtual memory.
+
+        We currently use about 8X the necessary amount:
+            - 2X to align our VM allocation
+            - 4X to reserve small / medium / (2) large chunk VM ranges per superchunk
+
+        We can cut that down:
+            - Return the unaligned portion of our VM allocation (-2X)
+            - Use all the chunks in a superchunk, instead of allocating one
+              chunk per superchunk (-4X)
+
+        * bmalloc/Algorithm.h:
+        (bmalloc::roundUpToMultipleOf): Added a non-constant version of this
+        function so we can call it with getpagesize() at runtime.
+
+        * bmalloc/Chunk.h:
+        * bmalloc/LargeChunk.h:
+        (bmalloc::LargeChunk::create): Deleted. Instead of each chunk allocating
+        its own VM, VMHeap allocates the superchunk and all the chunks in it at a time.
+
+        * bmalloc/VMAllocate.h:
+        (bmalloc::vmValidate):
+        (bmalloc::vmAllocate): ASSERT that mmap succeeds to make crashes clearer
+        if it does not succeed. Allocate precisely, and give back the extra.
+
+        * bmalloc/VMHeap.cpp:
+        (bmalloc::VMHeap::allocateSuperChunk):
+        (bmalloc::VMHeap::allocateSmallChunk): Deleted.
+        (bmalloc::VMHeap::allocateMediumChunk): Deleted.
+        (bmalloc::VMHeap::allocateLargeChunk): Deleted. Use all the chunks
+        in a superchunk, instead of just one.
+
+        * bmalloc/VMHeap.h:
+        (bmalloc::VMHeap::allocateSmallPage):
+        (bmalloc::VMHeap::allocateMediumPage):
+        (bmalloc::VMHeap::allocateLargeRange):
+        * bmalloc/XLargeChunk.h:
+        (bmalloc::XLargeChunk::create): Updated to match changes above.
+
 2014-11-01  David Kilzer  <ddkilzer@apple.com>
 
         JavaScriptCore is missing debug info for bmalloc because libbmalloc.a is stripped
index c6b3912..f476634 100644 (file)
@@ -62,10 +62,16 @@ template<typename T> inline constexpr bool test(T value, uintptr_t mask)
     return !!(reinterpret_cast<uintptr_t>(value) & mask);
 }
 
+template<typename T> inline T roundUpToMultipleOf(size_t divisor, T x)
+{
+    BASSERT(divisor && !(divisor & (divisor - 1)));
+    return reinterpret_cast<T>((reinterpret_cast<uintptr_t>(x) + (divisor - 1ul)) & ~(divisor - 1ul));
+}
+
 template<size_t divisor, typename T> inline constexpr T roundUpToMultipleOf(T x)
 {
     static_assert(divisor && !(divisor & (divisor - 1)), "'divisor' must be a power of two.");
-    return reinterpret_cast<T>((reinterpret_cast<uintptr_t>(x) + (divisor - 1ul)) & ~(divisor - 1ul));
+    return roundUpToMultipleOf(divisor, x);
 }
 
 template<size_t divisor, typename T> inline constexpr T roundDownToMultipleOf(T x)
index 8b9d561..0c4d1d2 100644 (file)
@@ -42,7 +42,6 @@ public:
     static const size_t chunkOffset = Traits::chunkOffset;
     static const uintptr_t chunkMask = Traits::chunkMask;
 
-    static Chunk* create();
     static Chunk* get(void*);
 
     Page* begin() { return Page::get(Line::get(m_memory)); }
@@ -67,14 +66,6 @@ private:
 };
 
 template<class Traits>
-inline auto Chunk<Traits>::create() -> Chunk*
-{
-    size_t vmSize = bmalloc::vmSize(chunkSize);
-    std::pair<void*, Range> result = vmAllocate(vmSize, superChunkSize, chunkOffset);
-    return new (result.first) Chunk;
-}
-
-template<class Traits>
 inline auto Chunk<Traits>::get(void* object) -> Chunk*
 {
     BASSERT(isSmallOrMedium(object));
index d002794..aa55281 100644 (file)
@@ -70,13 +70,6 @@ private:
     alignas(vmPageSize) char m_memory[];
 };
 
-inline LargeChunk* LargeChunk::create()
-{
-    size_t vmSize = bmalloc::vmSize(largeChunkSize);
-    std::pair<void*, Range> result = vmAllocate(vmSize, superChunkSize, largeChunkOffset);
-    return new (result.first) LargeChunk;
-}
-
 inline LargeChunk* LargeChunk::get(void* object)
 {
     BASSERT(!isSmallOrMedium(object));
index 7f41dd4..8016931 100644 (file)
@@ -43,20 +43,24 @@ inline size_t vmSize(size_t size)
 {
     return roundUpToMultipleOf<vmPageSize>(size);
 }
-    
+
 inline void vmValidate(size_t vmSize)
 {
+    // We use getpagesize() here instead of vmPageSize because vmPageSize is
+    // allowed to be larger than the OS's true page size.
+
     UNUSED(vmSize);
     BASSERT(vmSize);
-    BASSERT(vmSize == bmalloc::vmSize(vmSize));
+    BASSERT(vmSize == roundUpToMultipleOf(static_cast<size_t>(getpagesize()), vmSize));
 }
 
 inline void vmValidate(void* p, size_t vmSize)
 {
-    vmValidate(vmSize);
-    
     // We use getpagesize() here instead of vmPageSize because vmPageSize is
     // allowed to be larger than the OS's true page size.
+
+    vmValidate(vmSize);
+    
     UNUSED(p);
     BASSERT(p);
     BASSERT(p == mask(p, ~(getpagesize() - 1)));
@@ -65,7 +69,9 @@ inline void vmValidate(void* p, size_t vmSize)
 inline void* vmAllocate(size_t vmSize)
 {
     vmValidate(vmSize);
-    return mmap(0, vmSize, PROT_READ | PROT_WRITE, MAP_PRIVATE | MAP_ANON, BMALLOC_VM_TAG, 0);
+    void* result = mmap(0, vmSize, PROT_READ | PROT_WRITE, MAP_PRIVATE | MAP_ANON, BMALLOC_VM_TAG, 0);
+    RELEASE_BASSERT(result != MAP_FAILED);
+    return result;
 }
 
 inline void vmDeallocate(void* p, size_t vmSize)
@@ -74,30 +80,28 @@ inline void vmDeallocate(void* p, size_t vmSize)
     munmap(p, vmSize);
 }
 
-// Allocates vmSize bytes at a specified offset from a power-of-two alignment.
-// Use this function to create pointer masks that aren't simple powers of two.
+// Allocates vmSize bytes at a specified power-of-two alignment.
+// Use this function to create maskable memory regions.
 
-inline std::pair<void*, Range> vmAllocate(size_t vmSize, size_t alignment, size_t offset)
+inline void* vmAllocate(size_t vmSize, size_t vmAlignment)
 {
     vmValidate(vmSize);
-    BASSERT(isPowerOfTwo(alignment));
+    vmValidate(vmAlignment);
 
-    size_t mappedSize = std::max(vmSize, alignment) + alignment;
+    size_t mappedSize = std::max(vmSize, vmAlignment) + vmAlignment;
     char* mapped = static_cast<char*>(vmAllocate(mappedSize));
+    char* mappedEnd = mapped + mappedSize;
+
+    char* aligned = roundUpToMultipleOf(vmAlignment, mapped);
+    char* alignedEnd = aligned + vmSize;
+    
+    if (size_t leftExtra = aligned - mapped)
+        vmDeallocate(mapped, leftExtra);
     
-    uintptr_t alignmentMask = alignment - 1;
-    if (!test(mapped, alignmentMask) && offset + vmSize <= alignment) {
-        // We got two perfectly aligned regions. Give one back to avoid wasting
-        // VM unnecessarily. This isn't costly because we aren't making holes.
-        vmDeallocate(mapped + alignment, alignment);
-        return std::make_pair(mapped + offset, Range(mapped, alignment));
-    }
-
-    // We got an unaligned region. Keep the whole thing to avoid creating holes,
-    // and hopefully realign the VM allocator for future allocations. On Darwin,
-    // VM holes trigger O(N^2) behavior in mmap, so we want to minimize them.
-    char* mappedAligned = mask(mapped, ~alignmentMask) + alignment;
-    return std::make_pair(mappedAligned + offset, Range(mapped, mappedSize));
+    if (size_t rightExtra = mappedEnd - alignedEnd)
+        vmDeallocate(alignedEnd, rightExtra);
+
+    return aligned;
 }
 
 inline void vmDeallocatePhysicalPages(void* p, size_t vmSize)
index b46dcdb..ed39ebd 100644 (file)
@@ -36,24 +36,20 @@ VMHeap::VMHeap()
 {
 }
 
-void VMHeap::allocateSmallChunk()
+void VMHeap::allocateSuperChunk()
 {
-    SmallChunk* chunk = SmallChunk::create();
-    for (auto* it = chunk->begin(); it != chunk->end(); ++it)
+    char* superChunk = static_cast<char*>(vmAllocate(superChunkSize, superChunkSize));
+
+    SmallChunk* smallChunk = new (superChunk + smallChunkOffset) SmallChunk;
+    for (auto* it = smallChunk->begin(); it != smallChunk->end(); ++it)
         m_smallPages.push(it);
-}
 
-void VMHeap::allocateMediumChunk()
-{
-    MediumChunk* chunk = MediumChunk::create();
-    for (auto* it = chunk->begin(); it != chunk->end(); ++it)
+    MediumChunk* mediumChunk = new (superChunk + mediumChunkOffset) MediumChunk;
+    for (auto* it = mediumChunk->begin(); it != mediumChunk->end(); ++it)
         m_mediumPages.push(it);
-}
 
-Range VMHeap::allocateLargeChunk()
-{
-    LargeChunk* chunk = LargeChunk::create();
-    return BoundaryTag::init(chunk);
+    LargeChunk* largeChunk = new (superChunk + largeChunkOffset) LargeChunk;
+    m_largeRanges.insert(BoundaryTag::init(largeChunk));
 }
 
 } // namespace bmalloc
index 3ec2d5d..99f1a24 100644 (file)
@@ -54,9 +54,7 @@ public:
     void deallocateLargeRange(std::unique_lock<StaticMutex>&, Range);
 
 private:
-    void allocateSmallChunk();
-    void allocateMediumChunk();
-    Range allocateLargeChunk();
+    void allocateSuperChunk();
 
     Vector<SmallPage*> m_smallPages;
     Vector<MediumPage*> m_mediumPages;
@@ -66,7 +64,7 @@ private:
 inline SmallPage* VMHeap::allocateSmallPage()
 {
     if (!m_smallPages.size())
-        allocateSmallChunk();
+        allocateSuperChunk();
 
     return m_smallPages.pop();
 }
@@ -74,7 +72,7 @@ inline SmallPage* VMHeap::allocateSmallPage()
 inline MediumPage* VMHeap::allocateMediumPage()
 {
     if (!m_mediumPages.size())
-        allocateMediumChunk();
+        allocateSuperChunk();
 
     return m_mediumPages.pop();
 }
@@ -82,8 +80,11 @@ inline MediumPage* VMHeap::allocateMediumPage()
 inline Range VMHeap::allocateLargeRange(size_t size)
 {
     Range range = m_largeRanges.take(size);
-    if (!range)
-        range = allocateLargeChunk();
+    if (!range) {
+        allocateSuperChunk();
+        range = m_largeRanges.take(size);
+        BASSERT(range);
+    }
     return range;
 }
 
index 878b2a0..275d0df 100644 (file)
@@ -56,8 +56,8 @@ inline XLargeChunk::XLargeChunk(const Range& range, size_t size)
 inline XLargeChunk* XLargeChunk::create(size_t size)
 {
     size_t vmSize = bmalloc::vmSize(sizeof(XLargeChunk) + size);
-    std::pair<void*, Range> result = vmAllocate(vmSize, superChunkSize, largeChunkOffset);
-    return new (result.first) XLargeChunk(result.second, size);
+    auto xlargeChunk = vmAllocate(vmSize, superChunkSize);
+    return new (xlargeChunk) XLargeChunk(Range(xlargeChunk, vmSize), size);
 }
 
 inline void XLargeChunk::destroy(XLargeChunk* chunk)