2014-09-16 02:24:35 +00:00
|
|
|
/*
|
2019-09-06 17:04:13 +00:00
|
|
|
* Copyright (C) 2014-2019 Apple Inc. All rights reserved.
|
2014-09-16 02:24:35 +00:00
|
|
|
*
|
|
|
|
|
* Redistribution and use in source and binary forms, with or without
|
|
|
|
|
* modification, are permitted provided that the following conditions
|
|
|
|
|
* are met:
|
|
|
|
|
* 1. Redistributions of source code must retain the above copyright
|
|
|
|
|
* notice, this list of conditions and the following disclaimer.
|
|
|
|
|
* 2. Redistributions in binary form must reproduce the above copyright
|
|
|
|
|
* notice, this list of conditions and the following disclaimer in the
|
|
|
|
|
* documentation and/or other materials provided with the distribution.
|
|
|
|
|
*
|
|
|
|
|
* THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
|
|
|
|
|
* EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
|
|
|
|
|
* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
|
|
|
|
|
* PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR
|
|
|
|
|
* CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
|
|
|
|
|
* EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
|
|
|
|
|
* PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
|
|
|
|
|
* PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
|
|
|
|
|
* OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
|
|
|
|
|
* (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
|
|
|
|
|
* OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
|
|
|
|
|
*/
|
|
|
|
|
|
|
|
|
|
#ifndef BumpAllocator_h
|
|
|
|
|
#define BumpAllocator_h
|
|
|
|
|
|
|
|
|
|
#include "BAssert.h"
|
bmalloc: Allocation should be more precise
https://bugs.webkit.org/show_bug.cgi?id=136993
Reviewed by Gavin Barraclough.
13% reduction in heap size on the MallocBench *_memory_warning benchmarks.
This patch teaches the allocator to merge adjacent free lines into a
single allocatable range. This allows us to shrink the size of an
individual line without increasing fragmentation or the rate of allocator
slow paths.
We'll only take more slow paths when available memory is sparse, which
is exactly when it's worth it. When available memory is dense, we'll
take fewer slow paths.
* bmalloc.xcodeproj/project.pbxproj:
* bmalloc/Algorithm.h:
(bmalloc::divideRoundingUp):
* bmalloc/Allocator.cpp:
(bmalloc::Allocator::Allocator): Updated for interface changes.
(bmalloc::Allocator::scavenge): Scavenge by object instead of by line.
Now that we merge lines, it's not convenient to scavenge by line.
(bmalloc::Allocator::allocateSmallBumpRange):
(bmalloc::Allocator::allocateMediumBumpRange): Allocate whole ranges
instead of individual lines.
(bmalloc::Allocator::allocateSlowCase):
(bmalloc::Allocator::allocateSmallLine): Deleted.
(bmalloc::Allocator::allocateMediumLine): Deleted.
(bmalloc::Allocator::allocateMedium): Deleted.
* bmalloc/Allocator.h:
(bmalloc::Allocator::allocateFastCase): Folded medium allocations
into the standard fast path with small allocations. Since a BumpAllocator
just allocates out of an arbitrary range, it doesn't need to distinguish
between small and medium lines.
* bmalloc/BumpAllocator.h:
(bmalloc::BumpAllocator::size):
(bmalloc::BumpAllocator::BumpAllocator):
(bmalloc::BumpAllocator::init):
(bmalloc::BumpAllocator::refill):
(bmalloc::BumpAllocator::line): Deleted. No need to track line information
anymore: the heap just gives us a pointer and a pre-computed number of
objects, and we allocate them.
* bmalloc/Deallocator.cpp:
(bmalloc::Deallocator::processObjectLog): Updated for interface changes.
* bmalloc/Heap.cpp:
(bmalloc::Heap::Heap):
(bmalloc::Heap::initializeLineMetadata): Pre-compute precise metadata
detailing where all objects will lie in memory. After we merge two lines,
we might allocate an object that spans from one line to the next. This
metadata details which bits of memory overlap in that way, and how they
overlap.
(bmalloc::Heap::refillSmallBumpRangeCache):
(bmalloc::Heap::refillMediumBumpRangeCache): Scan a whole page at a time,
and merge adjacent free lines into BumpRanges.
(bmalloc::Heap::allocateSmallPage):
(bmalloc::Heap::allocateMediumPage):
(bmalloc::Heap::deallocateSmallLine):
(bmalloc::Heap::deallocateMediumLine): Track pages rather than lines,
since we scan for free memory a page at a time.
(bmalloc::Heap::allocateSmallLineSlowCase): Deleted.
(bmalloc::Heap::allocateMediumLineSlowCase): Deleted. Folded into the
fast path.
* bmalloc/Heap.h:
(bmalloc::Heap::derefSmallLine):
(bmalloc::Heap::derefMediumLine):
(bmalloc::Heap::deallocateSmallLine): Deleted.
(bmalloc::Heap::allocateSmallLine): Deleted.
(bmalloc::Heap::deallocateMediumLine): Deleted.
(bmalloc::Heap::allocateMediumLine): Deleted. Updated for interface changes.
* bmalloc/Line.h:
(bmalloc::Line<Traits>::ref):
(bmalloc::Line<Traits>::deref):
(bmalloc::Line<Traits>::concurrentRef): Deleted. We don't pass a derefCount
anymore, since we only ever deref by 1 now.
* bmalloc/MediumAllocator.h:
(bmalloc::MediumAllocator::isNull): Deleted.
(bmalloc::MediumAllocator::MediumAllocator): Deleted.
(bmalloc::MediumAllocator::line): Deleted.
(bmalloc::MediumAllocator::allocate): Deleted.
(bmalloc::MediumAllocator::derefCount): Deleted.
(bmalloc::MediumAllocator::refill): Deleted.
(bmalloc::MediumAllocator::clear): Deleted. Deleted some code that's
been dead for a while, since it doesn't build anymore with this patch.
* bmalloc/Page.h:
(bmalloc::Page::sizeClass):
(bmalloc::Page::setSizeClass):
(bmalloc::Page::smallSizeClass): Deleted.
(bmalloc::Page::setSmallSizeClass): Deleted. Renamed setSmallSizeClass
to sizeClass, since we use it for medium sizes too.
* bmalloc/Sizes.h:
(bmalloc::Sizes::sizeClass):
(bmalloc::Sizes::objectSize): Shrank line sizes to save memory.
(bmalloc::Sizes::smallSizeClassFor): Deleted.
(bmalloc::Sizes::mediumSizeClassFor): Deleted.
* bmalloc/bmalloc.h:
(bmalloc::api::realloc): Now that we have precise objects sizes, realloc
can be a bit more precise. It also has to be, since we can't guarantee
that an object ends at the end of a line anymore.
Canonical link: https://commits.webkit.org/154856@main
git-svn-id: https://svn.webkit.org/repository/webkit/trunk@173881 268f45cc-cd09-0410-ab3c-d52691b4dbfc
2014-09-23 18:24:02 +00:00
|
|
|
#include "BumpRange.h"
|
2014-09-16 02:24:35 +00:00
|
|
|
#include "ObjectType.h"
|
|
|
|
|
|
|
|
|
|
namespace bmalloc {
|
|
|
|
|
|
bmalloc: Remove the concept of medium objects
https://bugs.webkit.org/show_bug.cgi?id=154436
Reviewed by Sam Weinig.
There's no need to distinguish medium objects from small: Small object
metadata works naturally for both as long as we allow an object to
span more than two small lines. (We already allow an object to span
more than one small line.)
This change reduces memory use because it eliminates the 1kB line size,
so we don't have to hold down 1kB lines for individual 264+ byte objects.
1kB lines were always a bit of a compromise. The main point of bump
allocation is to take advantage of cache lines. Cache lines are usually
64 bytes, so line sizes above 256 bytes are a bit of a stretch.
This change speeds up small object benchmarks because it eliminates the
branch to detect medium objects in deallocation log processing.
This change reduces virtual memory use from worst cast 4X to worst case
2X because the medium chunk is gone. iOS cares about virtual memory use
and terminates apps above ~1GB, so this change gives us more breathing room.
This change slows down medium benchmarks a bit because we end up doing
more work to recycle fragmented medium objects. Overall, the tradeoff
seems justified, since we have a net speedup and a memory use savings.
* bmalloc.xcodeproj/project.pbxproj: Removed all the medium files. We
can simplify even further in a follow-up patch, removing the base class
templates for Chunk, Page, and Line as well.
* bmalloc/Allocator.cpp:
(bmalloc::Allocator::Allocator):
(bmalloc::Allocator::allocate):
(bmalloc::Allocator::reallocate):
(bmalloc::Allocator::scavenge):
(bmalloc::Allocator::refillAllocatorSlowCase):
(bmalloc::Allocator::refillAllocator):
(bmalloc::Allocator::allocateSlowCase): Medium is gone. Small max is the
new medium max.
* bmalloc/Allocator.h:
(bmalloc::Allocator::allocateFastCase): Ditto.
* bmalloc/BumpAllocator.h:
(bmalloc::BumpAllocator::validate):
(bmalloc::BumpAllocator::allocate): No more medium.
* bmalloc/Chunk.h: No more medium.
* bmalloc/Deallocator.cpp:
(bmalloc::Deallocator::processObjectLog): No check for medium. This is
a speedup.
(bmalloc::Deallocator::deallocateSlowCase): No more medium.
* bmalloc/Deallocator.h:
(bmalloc::Deallocator::deallocateFastCase): Ditto.
* bmalloc/Heap.cpp:
(bmalloc::Heap::initializeLineMetadata): The algorithm here changed from
iterating each line to iterating each object. This helps us accomodate
objects that might span more than two lines -- i.e., all objects between
(512 bytes, 1024 bytes].
(bmalloc::Heap::scavenge):
(bmalloc::Heap::scavengeSmallPages):
(bmalloc::Heap::scavengeLargeObjects): Medium is gone.
(bmalloc::Heap::allocateSmallBumpRanges): Allow for lines that allocate
zero objects. This happens when an object spans more than two lines --
the middle lines allocate zero objects.
Also set the "has free lines" bit to false if we consume the last free
line. This needs to be a bit now because not all pages agree on their
maximum refcount anymore, so we need an explicit signal for the transition
from maximum to maximum - 1.
(bmalloc::Heap::allocateSmallPage): This code didn't change; I just removed
the medium code.
(bmalloc::Heap::deallocateSmallLine): Changed the algorithm to check
hasFreeLines. See allocateSmallBumpRanges.
(bmalloc::Heap::scavengeMediumPages): Deleted.
(bmalloc::Heap::allocateMediumBumpRanges): Deleted.
(bmalloc::Heap::allocateMediumPage): Deleted.
(bmalloc::Heap::deallocateMediumLine): Deleted.
* bmalloc/Heap.h:
(bmalloc::Heap::derefMediumLine): Deleted.
* bmalloc/LargeChunk.h:
(bmalloc::LargeChunk::get):
(bmalloc::LargeChunk::endTag):
* bmalloc/Line.h: No more medium.
* bmalloc/MediumChunk.h: Removed.
* bmalloc/MediumLine.h: Removed.
* bmalloc/MediumPage.h: Removed.
* bmalloc/MediumTraits.h: Removed.
* bmalloc/ObjectType.cpp:
(bmalloc::objectType):
* bmalloc/ObjectType.h:
(bmalloc::isSmall):
(bmalloc::isXLarge):
(bmalloc::isSmallOrMedium): Deleted.
(bmalloc::isMedium): Deleted. No more medium.
* bmalloc/Page.h:
(bmalloc::Page::sizeClass):
(bmalloc::Page::setSizeClass):
(bmalloc::Page::hasFreeLines):
(bmalloc::Page::setHasFreeLines): Add the free lines bit. You get better
codegen if you make it the low bit, since ref / deref can then add / sub
2. So do that.
* bmalloc/Sizes.h:
(bmalloc::Sizes::sizeClass): Expand the small size class to include the
medium size class.
* bmalloc/SuperChunk.h:
(bmalloc::SuperChunk::SuperChunk):
(bmalloc::SuperChunk::smallChunk):
(bmalloc::SuperChunk::largeChunk):
(bmalloc::SuperChunk::mediumChunk): Deleted. No more medium.
* bmalloc/VMHeap.cpp:
(bmalloc::VMHeap::grow):
* bmalloc/VMHeap.h:
(bmalloc::VMHeap::allocateSmallPage): Set the has free lines bit before
returning a Page to the Heap since this is the correct default state
when we first allocate a page.
(bmalloc::VMHeap::allocateMediumPage): Deleted.
(bmalloc::VMHeap::deallocateMediumPage): Deleted.
Canonical link: https://commits.webkit.org/172587@main
git-svn-id: https://svn.webkit.org/repository/webkit/trunk@196845 268f45cc-cd09-0410-ab3c-d52691b4dbfc
2016-02-20 00:03:56 +00:00
|
|
|
// Helper object for allocating small objects.
|
2014-09-16 02:24:35 +00:00
|
|
|
|
|
|
|
|
class BumpAllocator {
|
|
|
|
|
public:
|
|
|
|
|
BumpAllocator();
|
bmalloc: Allocation should be more precise
https://bugs.webkit.org/show_bug.cgi?id=136993
Reviewed by Gavin Barraclough.
13% reduction in heap size on the MallocBench *_memory_warning benchmarks.
This patch teaches the allocator to merge adjacent free lines into a
single allocatable range. This allows us to shrink the size of an
individual line without increasing fragmentation or the rate of allocator
slow paths.
We'll only take more slow paths when available memory is sparse, which
is exactly when it's worth it. When available memory is dense, we'll
take fewer slow paths.
* bmalloc.xcodeproj/project.pbxproj:
* bmalloc/Algorithm.h:
(bmalloc::divideRoundingUp):
* bmalloc/Allocator.cpp:
(bmalloc::Allocator::Allocator): Updated for interface changes.
(bmalloc::Allocator::scavenge): Scavenge by object instead of by line.
Now that we merge lines, it's not convenient to scavenge by line.
(bmalloc::Allocator::allocateSmallBumpRange):
(bmalloc::Allocator::allocateMediumBumpRange): Allocate whole ranges
instead of individual lines.
(bmalloc::Allocator::allocateSlowCase):
(bmalloc::Allocator::allocateSmallLine): Deleted.
(bmalloc::Allocator::allocateMediumLine): Deleted.
(bmalloc::Allocator::allocateMedium): Deleted.
* bmalloc/Allocator.h:
(bmalloc::Allocator::allocateFastCase): Folded medium allocations
into the standard fast path with small allocations. Since a BumpAllocator
just allocates out of an arbitrary range, it doesn't need to distinguish
between small and medium lines.
* bmalloc/BumpAllocator.h:
(bmalloc::BumpAllocator::size):
(bmalloc::BumpAllocator::BumpAllocator):
(bmalloc::BumpAllocator::init):
(bmalloc::BumpAllocator::refill):
(bmalloc::BumpAllocator::line): Deleted. No need to track line information
anymore: the heap just gives us a pointer and a pre-computed number of
objects, and we allocate them.
* bmalloc/Deallocator.cpp:
(bmalloc::Deallocator::processObjectLog): Updated for interface changes.
* bmalloc/Heap.cpp:
(bmalloc::Heap::Heap):
(bmalloc::Heap::initializeLineMetadata): Pre-compute precise metadata
detailing where all objects will lie in memory. After we merge two lines,
we might allocate an object that spans from one line to the next. This
metadata details which bits of memory overlap in that way, and how they
overlap.
(bmalloc::Heap::refillSmallBumpRangeCache):
(bmalloc::Heap::refillMediumBumpRangeCache): Scan a whole page at a time,
and merge adjacent free lines into BumpRanges.
(bmalloc::Heap::allocateSmallPage):
(bmalloc::Heap::allocateMediumPage):
(bmalloc::Heap::deallocateSmallLine):
(bmalloc::Heap::deallocateMediumLine): Track pages rather than lines,
since we scan for free memory a page at a time.
(bmalloc::Heap::allocateSmallLineSlowCase): Deleted.
(bmalloc::Heap::allocateMediumLineSlowCase): Deleted. Folded into the
fast path.
* bmalloc/Heap.h:
(bmalloc::Heap::derefSmallLine):
(bmalloc::Heap::derefMediumLine):
(bmalloc::Heap::deallocateSmallLine): Deleted.
(bmalloc::Heap::allocateSmallLine): Deleted.
(bmalloc::Heap::deallocateMediumLine): Deleted.
(bmalloc::Heap::allocateMediumLine): Deleted. Updated for interface changes.
* bmalloc/Line.h:
(bmalloc::Line<Traits>::ref):
(bmalloc::Line<Traits>::deref):
(bmalloc::Line<Traits>::concurrentRef): Deleted. We don't pass a derefCount
anymore, since we only ever deref by 1 now.
* bmalloc/MediumAllocator.h:
(bmalloc::MediumAllocator::isNull): Deleted.
(bmalloc::MediumAllocator::MediumAllocator): Deleted.
(bmalloc::MediumAllocator::line): Deleted.
(bmalloc::MediumAllocator::allocate): Deleted.
(bmalloc::MediumAllocator::derefCount): Deleted.
(bmalloc::MediumAllocator::refill): Deleted.
(bmalloc::MediumAllocator::clear): Deleted. Deleted some code that's
been dead for a while, since it doesn't build anymore with this patch.
* bmalloc/Page.h:
(bmalloc::Page::sizeClass):
(bmalloc::Page::setSizeClass):
(bmalloc::Page::smallSizeClass): Deleted.
(bmalloc::Page::setSmallSizeClass): Deleted. Renamed setSmallSizeClass
to sizeClass, since we use it for medium sizes too.
* bmalloc/Sizes.h:
(bmalloc::Sizes::sizeClass):
(bmalloc::Sizes::objectSize): Shrank line sizes to save memory.
(bmalloc::Sizes::smallSizeClassFor): Deleted.
(bmalloc::Sizes::mediumSizeClassFor): Deleted.
* bmalloc/bmalloc.h:
(bmalloc::api::realloc): Now that we have precise objects sizes, realloc
can be a bit more precise. It also has to be, since we can't guarantee
that an object ends at the end of a line anymore.
Canonical link: https://commits.webkit.org/154856@main
git-svn-id: https://svn.webkit.org/repository/webkit/trunk@173881 268f45cc-cd09-0410-ab3c-d52691b4dbfc
2014-09-23 18:24:02 +00:00
|
|
|
void init(size_t);
|
|
|
|
|
|
|
|
|
|
size_t size() { return m_size; }
|
2014-09-16 02:24:35 +00:00
|
|
|
|
|
|
|
|
bool isNull() { return !m_ptr; }
|
bmalloc: Allocation should be more precise
https://bugs.webkit.org/show_bug.cgi?id=136993
Reviewed by Gavin Barraclough.
13% reduction in heap size on the MallocBench *_memory_warning benchmarks.
This patch teaches the allocator to merge adjacent free lines into a
single allocatable range. This allows us to shrink the size of an
individual line without increasing fragmentation or the rate of allocator
slow paths.
We'll only take more slow paths when available memory is sparse, which
is exactly when it's worth it. When available memory is dense, we'll
take fewer slow paths.
* bmalloc.xcodeproj/project.pbxproj:
* bmalloc/Algorithm.h:
(bmalloc::divideRoundingUp):
* bmalloc/Allocator.cpp:
(bmalloc::Allocator::Allocator): Updated for interface changes.
(bmalloc::Allocator::scavenge): Scavenge by object instead of by line.
Now that we merge lines, it's not convenient to scavenge by line.
(bmalloc::Allocator::allocateSmallBumpRange):
(bmalloc::Allocator::allocateMediumBumpRange): Allocate whole ranges
instead of individual lines.
(bmalloc::Allocator::allocateSlowCase):
(bmalloc::Allocator::allocateSmallLine): Deleted.
(bmalloc::Allocator::allocateMediumLine): Deleted.
(bmalloc::Allocator::allocateMedium): Deleted.
* bmalloc/Allocator.h:
(bmalloc::Allocator::allocateFastCase): Folded medium allocations
into the standard fast path with small allocations. Since a BumpAllocator
just allocates out of an arbitrary range, it doesn't need to distinguish
between small and medium lines.
* bmalloc/BumpAllocator.h:
(bmalloc::BumpAllocator::size):
(bmalloc::BumpAllocator::BumpAllocator):
(bmalloc::BumpAllocator::init):
(bmalloc::BumpAllocator::refill):
(bmalloc::BumpAllocator::line): Deleted. No need to track line information
anymore: the heap just gives us a pointer and a pre-computed number of
objects, and we allocate them.
* bmalloc/Deallocator.cpp:
(bmalloc::Deallocator::processObjectLog): Updated for interface changes.
* bmalloc/Heap.cpp:
(bmalloc::Heap::Heap):
(bmalloc::Heap::initializeLineMetadata): Pre-compute precise metadata
detailing where all objects will lie in memory. After we merge two lines,
we might allocate an object that spans from one line to the next. This
metadata details which bits of memory overlap in that way, and how they
overlap.
(bmalloc::Heap::refillSmallBumpRangeCache):
(bmalloc::Heap::refillMediumBumpRangeCache): Scan a whole page at a time,
and merge adjacent free lines into BumpRanges.
(bmalloc::Heap::allocateSmallPage):
(bmalloc::Heap::allocateMediumPage):
(bmalloc::Heap::deallocateSmallLine):
(bmalloc::Heap::deallocateMediumLine): Track pages rather than lines,
since we scan for free memory a page at a time.
(bmalloc::Heap::allocateSmallLineSlowCase): Deleted.
(bmalloc::Heap::allocateMediumLineSlowCase): Deleted. Folded into the
fast path.
* bmalloc/Heap.h:
(bmalloc::Heap::derefSmallLine):
(bmalloc::Heap::derefMediumLine):
(bmalloc::Heap::deallocateSmallLine): Deleted.
(bmalloc::Heap::allocateSmallLine): Deleted.
(bmalloc::Heap::deallocateMediumLine): Deleted.
(bmalloc::Heap::allocateMediumLine): Deleted. Updated for interface changes.
* bmalloc/Line.h:
(bmalloc::Line<Traits>::ref):
(bmalloc::Line<Traits>::deref):
(bmalloc::Line<Traits>::concurrentRef): Deleted. We don't pass a derefCount
anymore, since we only ever deref by 1 now.
* bmalloc/MediumAllocator.h:
(bmalloc::MediumAllocator::isNull): Deleted.
(bmalloc::MediumAllocator::MediumAllocator): Deleted.
(bmalloc::MediumAllocator::line): Deleted.
(bmalloc::MediumAllocator::allocate): Deleted.
(bmalloc::MediumAllocator::derefCount): Deleted.
(bmalloc::MediumAllocator::refill): Deleted.
(bmalloc::MediumAllocator::clear): Deleted. Deleted some code that's
been dead for a while, since it doesn't build anymore with this patch.
* bmalloc/Page.h:
(bmalloc::Page::sizeClass):
(bmalloc::Page::setSizeClass):
(bmalloc::Page::smallSizeClass): Deleted.
(bmalloc::Page::setSmallSizeClass): Deleted. Renamed setSmallSizeClass
to sizeClass, since we use it for medium sizes too.
* bmalloc/Sizes.h:
(bmalloc::Sizes::sizeClass):
(bmalloc::Sizes::objectSize): Shrank line sizes to save memory.
(bmalloc::Sizes::smallSizeClassFor): Deleted.
(bmalloc::Sizes::mediumSizeClassFor): Deleted.
* bmalloc/bmalloc.h:
(bmalloc::api::realloc): Now that we have precise objects sizes, realloc
can be a bit more precise. It also has to be, since we can't guarantee
that an object ends at the end of a line anymore.
Canonical link: https://commits.webkit.org/154856@main
git-svn-id: https://svn.webkit.org/repository/webkit/trunk@173881 268f45cc-cd09-0410-ab3c-d52691b4dbfc
2014-09-23 18:24:02 +00:00
|
|
|
void clear();
|
2014-09-16 02:24:35 +00:00
|
|
|
|
|
|
|
|
bool canAllocate() { return !!m_remaining; }
|
|
|
|
|
void* allocate();
|
|
|
|
|
|
bmalloc: Allocation should be more precise
https://bugs.webkit.org/show_bug.cgi?id=136993
Reviewed by Gavin Barraclough.
13% reduction in heap size on the MallocBench *_memory_warning benchmarks.
This patch teaches the allocator to merge adjacent free lines into a
single allocatable range. This allows us to shrink the size of an
individual line without increasing fragmentation or the rate of allocator
slow paths.
We'll only take more slow paths when available memory is sparse, which
is exactly when it's worth it. When available memory is dense, we'll
take fewer slow paths.
* bmalloc.xcodeproj/project.pbxproj:
* bmalloc/Algorithm.h:
(bmalloc::divideRoundingUp):
* bmalloc/Allocator.cpp:
(bmalloc::Allocator::Allocator): Updated for interface changes.
(bmalloc::Allocator::scavenge): Scavenge by object instead of by line.
Now that we merge lines, it's not convenient to scavenge by line.
(bmalloc::Allocator::allocateSmallBumpRange):
(bmalloc::Allocator::allocateMediumBumpRange): Allocate whole ranges
instead of individual lines.
(bmalloc::Allocator::allocateSlowCase):
(bmalloc::Allocator::allocateSmallLine): Deleted.
(bmalloc::Allocator::allocateMediumLine): Deleted.
(bmalloc::Allocator::allocateMedium): Deleted.
* bmalloc/Allocator.h:
(bmalloc::Allocator::allocateFastCase): Folded medium allocations
into the standard fast path with small allocations. Since a BumpAllocator
just allocates out of an arbitrary range, it doesn't need to distinguish
between small and medium lines.
* bmalloc/BumpAllocator.h:
(bmalloc::BumpAllocator::size):
(bmalloc::BumpAllocator::BumpAllocator):
(bmalloc::BumpAllocator::init):
(bmalloc::BumpAllocator::refill):
(bmalloc::BumpAllocator::line): Deleted. No need to track line information
anymore: the heap just gives us a pointer and a pre-computed number of
objects, and we allocate them.
* bmalloc/Deallocator.cpp:
(bmalloc::Deallocator::processObjectLog): Updated for interface changes.
* bmalloc/Heap.cpp:
(bmalloc::Heap::Heap):
(bmalloc::Heap::initializeLineMetadata): Pre-compute precise metadata
detailing where all objects will lie in memory. After we merge two lines,
we might allocate an object that spans from one line to the next. This
metadata details which bits of memory overlap in that way, and how they
overlap.
(bmalloc::Heap::refillSmallBumpRangeCache):
(bmalloc::Heap::refillMediumBumpRangeCache): Scan a whole page at a time,
and merge adjacent free lines into BumpRanges.
(bmalloc::Heap::allocateSmallPage):
(bmalloc::Heap::allocateMediumPage):
(bmalloc::Heap::deallocateSmallLine):
(bmalloc::Heap::deallocateMediumLine): Track pages rather than lines,
since we scan for free memory a page at a time.
(bmalloc::Heap::allocateSmallLineSlowCase): Deleted.
(bmalloc::Heap::allocateMediumLineSlowCase): Deleted. Folded into the
fast path.
* bmalloc/Heap.h:
(bmalloc::Heap::derefSmallLine):
(bmalloc::Heap::derefMediumLine):
(bmalloc::Heap::deallocateSmallLine): Deleted.
(bmalloc::Heap::allocateSmallLine): Deleted.
(bmalloc::Heap::deallocateMediumLine): Deleted.
(bmalloc::Heap::allocateMediumLine): Deleted. Updated for interface changes.
* bmalloc/Line.h:
(bmalloc::Line<Traits>::ref):
(bmalloc::Line<Traits>::deref):
(bmalloc::Line<Traits>::concurrentRef): Deleted. We don't pass a derefCount
anymore, since we only ever deref by 1 now.
* bmalloc/MediumAllocator.h:
(bmalloc::MediumAllocator::isNull): Deleted.
(bmalloc::MediumAllocator::MediumAllocator): Deleted.
(bmalloc::MediumAllocator::line): Deleted.
(bmalloc::MediumAllocator::allocate): Deleted.
(bmalloc::MediumAllocator::derefCount): Deleted.
(bmalloc::MediumAllocator::refill): Deleted.
(bmalloc::MediumAllocator::clear): Deleted. Deleted some code that's
been dead for a while, since it doesn't build anymore with this patch.
* bmalloc/Page.h:
(bmalloc::Page::sizeClass):
(bmalloc::Page::setSizeClass):
(bmalloc::Page::smallSizeClass): Deleted.
(bmalloc::Page::setSmallSizeClass): Deleted. Renamed setSmallSizeClass
to sizeClass, since we use it for medium sizes too.
* bmalloc/Sizes.h:
(bmalloc::Sizes::sizeClass):
(bmalloc::Sizes::objectSize): Shrank line sizes to save memory.
(bmalloc::Sizes::smallSizeClassFor): Deleted.
(bmalloc::Sizes::mediumSizeClassFor): Deleted.
* bmalloc/bmalloc.h:
(bmalloc::api::realloc): Now that we have precise objects sizes, realloc
can be a bit more precise. It also has to be, since we can't guarantee
that an object ends at the end of a line anymore.
Canonical link: https://commits.webkit.org/154856@main
git-svn-id: https://svn.webkit.org/repository/webkit/trunk@173881 268f45cc-cd09-0410-ab3c-d52691b4dbfc
2014-09-23 18:24:02 +00:00
|
|
|
void refill(const BumpRange&);
|
2014-09-16 02:24:35 +00:00
|
|
|
|
|
|
|
|
private:
|
|
|
|
|
char* m_ptr;
|
bmalloc: segregate small and large objects again, and allocate more objects on the small path
https://bugs.webkit.org/show_bug.cgi?id=156152
Reviewed by Sam Weinig.
Microbenchmark data suggested that it was a good idea for small and large
objects to share memory. But r198675 did not improve memory use in
full browser benchmarks.
This patch reverts to segregating small and large objects -- but without
going back to doubled VM usage -- in order to capture a few benefits:
(*) Small pages fragment the large heap. Separating them out saves a lot
of memory in our worst case fragmentation recording:
nimlang 276,076kB 209,636kB ^ 1.32x smaller
(*) Small objects are common enough that even their slow paths benefit
from simpler code:
Execution Time:
...
facebook 234ms 216ms ^ 1.08x faster
reddit 114ms 108ms ^ 1.06x faster
flickr 118ms 111ms ^ 1.06x faster
theverge 146ms 140ms ^ 1.04x faster
...
<arithmetic mean> 107ms 102ms ^ 1.04x faster
(*) We can use less metadata:
Memory at End:
...
list_allocate 460kB 384kB ^ 1.2x smaller
tree_allocate 492kB 424kB ^ 1.16x smaller
tree_churn 480kB 404kB ^ 1.19x smaller
fragment 532kB 452kB ^ 1.18x smaller
fragment_iterate 712kB 588kB ^ 1.21x smaller
medium 15,152kB 11,796kB ^ 1.28x smaller
big 15,044kB 10,976kB ^ 1.37x smaller
...
<arithmetic mean> 7,724kB 7,190kB ^ 1.07x smaller
This patch also takes advantage of our support for varying the page size
at runtime by allocating more objects on the small object path:
medium 178ms 150ms ^ 1.19x faster
Some microbenchmarks report memory use increases from this change -- like
they reported memory use decreases from r198675 -- but I'm ignoring them
for now because I expect our full browser memory benchmarks to confirm
that this patch is fine.
* bmalloc/BumpAllocator.h:
(bmalloc::BumpAllocator::BumpAllocator): Use a full unsigned because we
can allocate objects larger than 16kB - 1, and a full unsigned does not
make BumpAllocator any larger on 64bit systems.
* bmalloc/Chunk.h:
(bmalloc::Chunk::begin):
(bmalloc::Chunk::end):
(bmalloc::Chunk::size):
(bmalloc::Chunk::objectType): Store ObjectType in the Chunk, since it only
varies by Chunk now, and not from page to page within a Chunk. Also,
union together small and large object metadata, since we will only use
one or the other. This saves memory.
(bmalloc::Chunk::Chunk): Conditionalize initialization based on object
type, since only one kind of metadata or the other can be used at runtime.
(bmalloc::Object::Object):
(bmalloc::Object::begin):
(bmalloc::SmallPage::end): Deleted.
* bmalloc/Heap.cpp:
(bmalloc::Heap::Heap):
(bmalloc::Heap::initializeLineMetadata): Save a little space, since we
know that lines are only 256 bytes long.
(bmalloc::Heap::initializePageMetadata): Store a dynamic page size for
each size class. We used to use only one page size (the system page size)
but that limited our ability to allocate objects larger than 1kB on the
small object path. Now we can handle any object size we want by storing
objects of that size in a custom page size.
(bmalloc::Heap::concurrentScavenge):
(bmalloc::Heap::scavenge):
(bmalloc::Heap::scavengeSmallPages): Revert to our old linked list
strategy for storing small pages.
(bmalloc::Heap::splitAndAllocate): Object type is per Chunk now.
(bmalloc::Heap::allocateLarge): Don't nuke the small page list when
allocating a large object because the two don't share memory anymore.
(bmalloc::Heap::allocateSmallPage): Revert to our old linked list
strategy for storing small pages.
(bmalloc::Heap::deallocateSmallLine): Don't return early in the case
where this is the first free object in the page. In the case of large-ish
objects, the first free object might also be the last free object,
since there's one object per page.
(bmalloc::Heap::allocateSmallBumpRangesByMetadata): Split out some helper
lambdas to make this code clearer.
(bmalloc::Heap::allocateSmallBumpRangesByObject): Added a fast scan
for objects larger than the line size. When multiple objects fit in
a single line, it's an optimization to scan a line at a time. But when
it's one object per line, or one object per 64 lines, it's better just
to scan an object at a time.
* bmalloc/Heap.h:
(bmalloc::Heap::allocateSmallBumpRanges):
(bmalloc::Heap::derefSmallLine): Match the changes above.
* bmalloc/LineMetadata.h: We weren't using all those bits.
* bmalloc/List.h:
(bmalloc::List::remove): Put a removed Node fully back into the default
(empty) state it was in before it entered the list. This change is not
observable, but it makes things clearer when you're debugging.
* bmalloc/Object.h:
(bmalloc::Object::Object):
(bmalloc::Object::chunk):
(bmalloc::Object::offset):
(bmalloc::Object::operator+):
(bmalloc::Object::operator<=): Added some helpers for iterating by object.
* bmalloc/ObjectType.cpp:
(bmalloc::objectType): Updated for API change.
* bmalloc/Sizes.h:
(bmalloc::Sizes::maskObjectSize):
(bmalloc::Sizes::objectSize):
(bmalloc::Sizes::pageSize): Support more page sizes.
* bmalloc/SmallPage.h:
(bmalloc::SmallPage::SmallPage):
(bmalloc::SmallPage::objectType): Deleted.
(bmalloc::SmallPage::setObjectType): Deleted.
(bmalloc::SmallPage::smallPageCount): Deleted.
(bmalloc::SmallPage::setSmallPageCount): Deleted. Object type is per
Chunk now, and we can infer page count from size class.
* bmalloc/VMHeap.cpp:
(bmalloc::VMHeap::allocateChunk):
(bmalloc::VMHeap::allocateSmallChunk):
* bmalloc/VMHeap.h:
(bmalloc::VMHeap::allocateSmallPage):
(bmalloc::VMHeap::deallocateSmallPage):
(bmalloc::VMHeap::allocateLargeObject): Support our old behavior of
storing free pages in linked lists.
Canonical link: https://commits.webkit.org/174274@main
git-svn-id: https://svn.webkit.org/repository/webkit/trunk@198995 268f45cc-cd09-0410-ab3c-d52691b4dbfc
2016-04-04 05:26:43 +00:00
|
|
|
unsigned m_size;
|
|
|
|
|
unsigned m_remaining;
|
2014-09-16 02:24:35 +00:00
|
|
|
};
|
|
|
|
|
|
|
|
|
|
inline BumpAllocator::BumpAllocator()
|
|
|
|
|
: m_ptr()
|
|
|
|
|
, m_size()
|
|
|
|
|
, m_remaining()
|
|
|
|
|
{
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
inline void BumpAllocator::init(size_t size)
|
|
|
|
|
{
|
|
|
|
|
m_ptr = nullptr;
|
|
|
|
|
m_size = size;
|
|
|
|
|
m_remaining = 0;
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
inline void* BumpAllocator::allocate()
|
|
|
|
|
{
|
|
|
|
|
BASSERT(m_remaining);
|
|
|
|
|
|
|
|
|
|
--m_remaining;
|
|
|
|
|
char* result = m_ptr;
|
|
|
|
|
m_ptr += m_size;
|
|
|
|
|
return result;
|
|
|
|
|
}
|
|
|
|
|
|
bmalloc: Allocation should be more precise
https://bugs.webkit.org/show_bug.cgi?id=136993
Reviewed by Gavin Barraclough.
13% reduction in heap size on the MallocBench *_memory_warning benchmarks.
This patch teaches the allocator to merge adjacent free lines into a
single allocatable range. This allows us to shrink the size of an
individual line without increasing fragmentation or the rate of allocator
slow paths.
We'll only take more slow paths when available memory is sparse, which
is exactly when it's worth it. When available memory is dense, we'll
take fewer slow paths.
* bmalloc.xcodeproj/project.pbxproj:
* bmalloc/Algorithm.h:
(bmalloc::divideRoundingUp):
* bmalloc/Allocator.cpp:
(bmalloc::Allocator::Allocator): Updated for interface changes.
(bmalloc::Allocator::scavenge): Scavenge by object instead of by line.
Now that we merge lines, it's not convenient to scavenge by line.
(bmalloc::Allocator::allocateSmallBumpRange):
(bmalloc::Allocator::allocateMediumBumpRange): Allocate whole ranges
instead of individual lines.
(bmalloc::Allocator::allocateSlowCase):
(bmalloc::Allocator::allocateSmallLine): Deleted.
(bmalloc::Allocator::allocateMediumLine): Deleted.
(bmalloc::Allocator::allocateMedium): Deleted.
* bmalloc/Allocator.h:
(bmalloc::Allocator::allocateFastCase): Folded medium allocations
into the standard fast path with small allocations. Since a BumpAllocator
just allocates out of an arbitrary range, it doesn't need to distinguish
between small and medium lines.
* bmalloc/BumpAllocator.h:
(bmalloc::BumpAllocator::size):
(bmalloc::BumpAllocator::BumpAllocator):
(bmalloc::BumpAllocator::init):
(bmalloc::BumpAllocator::refill):
(bmalloc::BumpAllocator::line): Deleted. No need to track line information
anymore: the heap just gives us a pointer and a pre-computed number of
objects, and we allocate them.
* bmalloc/Deallocator.cpp:
(bmalloc::Deallocator::processObjectLog): Updated for interface changes.
* bmalloc/Heap.cpp:
(bmalloc::Heap::Heap):
(bmalloc::Heap::initializeLineMetadata): Pre-compute precise metadata
detailing where all objects will lie in memory. After we merge two lines,
we might allocate an object that spans from one line to the next. This
metadata details which bits of memory overlap in that way, and how they
overlap.
(bmalloc::Heap::refillSmallBumpRangeCache):
(bmalloc::Heap::refillMediumBumpRangeCache): Scan a whole page at a time,
and merge adjacent free lines into BumpRanges.
(bmalloc::Heap::allocateSmallPage):
(bmalloc::Heap::allocateMediumPage):
(bmalloc::Heap::deallocateSmallLine):
(bmalloc::Heap::deallocateMediumLine): Track pages rather than lines,
since we scan for free memory a page at a time.
(bmalloc::Heap::allocateSmallLineSlowCase): Deleted.
(bmalloc::Heap::allocateMediumLineSlowCase): Deleted. Folded into the
fast path.
* bmalloc/Heap.h:
(bmalloc::Heap::derefSmallLine):
(bmalloc::Heap::derefMediumLine):
(bmalloc::Heap::deallocateSmallLine): Deleted.
(bmalloc::Heap::allocateSmallLine): Deleted.
(bmalloc::Heap::deallocateMediumLine): Deleted.
(bmalloc::Heap::allocateMediumLine): Deleted. Updated for interface changes.
* bmalloc/Line.h:
(bmalloc::Line<Traits>::ref):
(bmalloc::Line<Traits>::deref):
(bmalloc::Line<Traits>::concurrentRef): Deleted. We don't pass a derefCount
anymore, since we only ever deref by 1 now.
* bmalloc/MediumAllocator.h:
(bmalloc::MediumAllocator::isNull): Deleted.
(bmalloc::MediumAllocator::MediumAllocator): Deleted.
(bmalloc::MediumAllocator::line): Deleted.
(bmalloc::MediumAllocator::allocate): Deleted.
(bmalloc::MediumAllocator::derefCount): Deleted.
(bmalloc::MediumAllocator::refill): Deleted.
(bmalloc::MediumAllocator::clear): Deleted. Deleted some code that's
been dead for a while, since it doesn't build anymore with this patch.
* bmalloc/Page.h:
(bmalloc::Page::sizeClass):
(bmalloc::Page::setSizeClass):
(bmalloc::Page::smallSizeClass): Deleted.
(bmalloc::Page::setSmallSizeClass): Deleted. Renamed setSmallSizeClass
to sizeClass, since we use it for medium sizes too.
* bmalloc/Sizes.h:
(bmalloc::Sizes::sizeClass):
(bmalloc::Sizes::objectSize): Shrank line sizes to save memory.
(bmalloc::Sizes::smallSizeClassFor): Deleted.
(bmalloc::Sizes::mediumSizeClassFor): Deleted.
* bmalloc/bmalloc.h:
(bmalloc::api::realloc): Now that we have precise objects sizes, realloc
can be a bit more precise. It also has to be, since we can't guarantee
that an object ends at the end of a line anymore.
Canonical link: https://commits.webkit.org/154856@main
git-svn-id: https://svn.webkit.org/repository/webkit/trunk@173881 268f45cc-cd09-0410-ab3c-d52691b4dbfc
2014-09-23 18:24:02 +00:00
|
|
|
inline void BumpAllocator::refill(const BumpRange& bumpRange)
|
2014-09-16 02:24:35 +00:00
|
|
|
{
|
|
|
|
|
BASSERT(!canAllocate());
|
bmalloc: Allocation should be more precise
https://bugs.webkit.org/show_bug.cgi?id=136993
Reviewed by Gavin Barraclough.
13% reduction in heap size on the MallocBench *_memory_warning benchmarks.
This patch teaches the allocator to merge adjacent free lines into a
single allocatable range. This allows us to shrink the size of an
individual line without increasing fragmentation or the rate of allocator
slow paths.
We'll only take more slow paths when available memory is sparse, which
is exactly when it's worth it. When available memory is dense, we'll
take fewer slow paths.
* bmalloc.xcodeproj/project.pbxproj:
* bmalloc/Algorithm.h:
(bmalloc::divideRoundingUp):
* bmalloc/Allocator.cpp:
(bmalloc::Allocator::Allocator): Updated for interface changes.
(bmalloc::Allocator::scavenge): Scavenge by object instead of by line.
Now that we merge lines, it's not convenient to scavenge by line.
(bmalloc::Allocator::allocateSmallBumpRange):
(bmalloc::Allocator::allocateMediumBumpRange): Allocate whole ranges
instead of individual lines.
(bmalloc::Allocator::allocateSlowCase):
(bmalloc::Allocator::allocateSmallLine): Deleted.
(bmalloc::Allocator::allocateMediumLine): Deleted.
(bmalloc::Allocator::allocateMedium): Deleted.
* bmalloc/Allocator.h:
(bmalloc::Allocator::allocateFastCase): Folded medium allocations
into the standard fast path with small allocations. Since a BumpAllocator
just allocates out of an arbitrary range, it doesn't need to distinguish
between small and medium lines.
* bmalloc/BumpAllocator.h:
(bmalloc::BumpAllocator::size):
(bmalloc::BumpAllocator::BumpAllocator):
(bmalloc::BumpAllocator::init):
(bmalloc::BumpAllocator::refill):
(bmalloc::BumpAllocator::line): Deleted. No need to track line information
anymore: the heap just gives us a pointer and a pre-computed number of
objects, and we allocate them.
* bmalloc/Deallocator.cpp:
(bmalloc::Deallocator::processObjectLog): Updated for interface changes.
* bmalloc/Heap.cpp:
(bmalloc::Heap::Heap):
(bmalloc::Heap::initializeLineMetadata): Pre-compute precise metadata
detailing where all objects will lie in memory. After we merge two lines,
we might allocate an object that spans from one line to the next. This
metadata details which bits of memory overlap in that way, and how they
overlap.
(bmalloc::Heap::refillSmallBumpRangeCache):
(bmalloc::Heap::refillMediumBumpRangeCache): Scan a whole page at a time,
and merge adjacent free lines into BumpRanges.
(bmalloc::Heap::allocateSmallPage):
(bmalloc::Heap::allocateMediumPage):
(bmalloc::Heap::deallocateSmallLine):
(bmalloc::Heap::deallocateMediumLine): Track pages rather than lines,
since we scan for free memory a page at a time.
(bmalloc::Heap::allocateSmallLineSlowCase): Deleted.
(bmalloc::Heap::allocateMediumLineSlowCase): Deleted. Folded into the
fast path.
* bmalloc/Heap.h:
(bmalloc::Heap::derefSmallLine):
(bmalloc::Heap::derefMediumLine):
(bmalloc::Heap::deallocateSmallLine): Deleted.
(bmalloc::Heap::allocateSmallLine): Deleted.
(bmalloc::Heap::deallocateMediumLine): Deleted.
(bmalloc::Heap::allocateMediumLine): Deleted. Updated for interface changes.
* bmalloc/Line.h:
(bmalloc::Line<Traits>::ref):
(bmalloc::Line<Traits>::deref):
(bmalloc::Line<Traits>::concurrentRef): Deleted. We don't pass a derefCount
anymore, since we only ever deref by 1 now.
* bmalloc/MediumAllocator.h:
(bmalloc::MediumAllocator::isNull): Deleted.
(bmalloc::MediumAllocator::MediumAllocator): Deleted.
(bmalloc::MediumAllocator::line): Deleted.
(bmalloc::MediumAllocator::allocate): Deleted.
(bmalloc::MediumAllocator::derefCount): Deleted.
(bmalloc::MediumAllocator::refill): Deleted.
(bmalloc::MediumAllocator::clear): Deleted. Deleted some code that's
been dead for a while, since it doesn't build anymore with this patch.
* bmalloc/Page.h:
(bmalloc::Page::sizeClass):
(bmalloc::Page::setSizeClass):
(bmalloc::Page::smallSizeClass): Deleted.
(bmalloc::Page::setSmallSizeClass): Deleted. Renamed setSmallSizeClass
to sizeClass, since we use it for medium sizes too.
* bmalloc/Sizes.h:
(bmalloc::Sizes::sizeClass):
(bmalloc::Sizes::objectSize): Shrank line sizes to save memory.
(bmalloc::Sizes::smallSizeClassFor): Deleted.
(bmalloc::Sizes::mediumSizeClassFor): Deleted.
* bmalloc/bmalloc.h:
(bmalloc::api::realloc): Now that we have precise objects sizes, realloc
can be a bit more precise. It also has to be, since we can't guarantee
that an object ends at the end of a line anymore.
Canonical link: https://commits.webkit.org/154856@main
git-svn-id: https://svn.webkit.org/repository/webkit/trunk@173881 268f45cc-cd09-0410-ab3c-d52691b4dbfc
2014-09-23 18:24:02 +00:00
|
|
|
m_ptr = bumpRange.begin;
|
|
|
|
|
m_remaining = bumpRange.objectCount;
|
2016-02-21 18:43:22 +00:00
|
|
|
BASSERT(canAllocate());
|
2014-09-16 02:24:35 +00:00
|
|
|
}
|
|
|
|
|
|
|
|
|
|
inline void BumpAllocator::clear()
|
|
|
|
|
{
|
|
|
|
|
m_ptr = nullptr;
|
|
|
|
|
m_remaining = 0;
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
} // namespace bmalloc
|
|
|
|
|
|
|
|
|
|
#endif // BumpAllocator_h
|