bmalloc: Renamed LargeChunk => Chunk
[WebKit-https.git] / Source / bmalloc / ChangeLog
index eb6f0cb..401f45d 100644 (file)
@@ -1,3 +1,905 @@
+2016-03-25  Geoffrey Garen  <ggaren@apple.com>
+
+        bmalloc: Renamed LargeChunk => Chunk
+        https://bugs.webkit.org/show_bug.cgi?id=155894
+
+        Reviewed by Michael Saboff.
+
+        A Chunk can contain both small and large objects now.
+
+        * bmalloc.xcodeproj/project.pbxproj:
+        * bmalloc/Allocator.cpp:
+        (bmalloc::Allocator::allocate):
+        * bmalloc/BoundaryTag.h:
+        (bmalloc::BoundaryTag::isFree):
+        * bmalloc/Chunk.h: Copied from Source/bmalloc/bmalloc/LargeChunk.h.
+        (bmalloc::Chunk::pages):
+        (bmalloc::Chunk::begin):
+        (bmalloc::Chunk::end):
+        (bmalloc::Chunk::Chunk):
+        (bmalloc::Chunk::get):
+        (bmalloc::Chunk::beginTag):
+        (bmalloc::Chunk::endTag):
+        (bmalloc::Chunk::offset):
+        (bmalloc::Chunk::object):
+        (bmalloc::Chunk::page):
+        (bmalloc::Chunk::line):
+        (bmalloc::SmallLine::begin):
+        (bmalloc::SmallPage::begin):
+        (bmalloc::SmallPage::end):
+        (bmalloc::Object::Object):
+        (bmalloc::Object::begin):
+        (bmalloc::LargeChunk::pages): Deleted.
+        (bmalloc::LargeChunk::begin): Deleted.
+        (bmalloc::LargeChunk::end): Deleted.
+        (bmalloc::LargeChunk::LargeChunk): Deleted.
+        (bmalloc::LargeChunk::get): Deleted.
+        (bmalloc::LargeChunk::beginTag): Deleted.
+        (bmalloc::LargeChunk::endTag): Deleted.
+        (bmalloc::LargeChunk::offset): Deleted.
+        (bmalloc::LargeChunk::object): Deleted.
+        (bmalloc::LargeChunk::page): Deleted.
+        (bmalloc::LargeChunk::line): Deleted.
+        * bmalloc/Deallocator.cpp:
+        * bmalloc/FreeList.cpp:
+        * bmalloc/Heap.cpp:
+        (bmalloc::Heap::allocateLarge):
+        * bmalloc/LargeChunk.h: Removed.
+        * bmalloc/LargeObject.h:
+        (bmalloc::LargeObject::LargeObject):
+        (bmalloc::LargeObject::merge):
+        (bmalloc::LargeObject::split):
+        * bmalloc/Object.h:
+        (bmalloc::Object::chunk):
+        * bmalloc/ObjectType.cpp:
+        * bmalloc/Sizes.h:
+        * bmalloc/SmallAllocator.h: Removed.
+        * bmalloc/VMHeap.cpp:
+        (bmalloc::VMHeap::VMHeap):
+        (bmalloc::VMHeap::allocateChunk):
+        (bmalloc::VMHeap::allocateLargeChunk): Deleted.
+        * bmalloc/VMHeap.h:
+        (bmalloc::VMHeap::allocateLargeObject):
+        (bmalloc::VMHeap::deallocateLargeObject):
+        * bmalloc/Zone.cpp:
+        (bmalloc::enumerator):
+        * bmalloc/Zone.h:
+        (bmalloc::Zone::chunks):
+        (bmalloc::Zone::addChunk):
+        (bmalloc::Zone::largeChunks): Deleted.
+        (bmalloc::Zone::addLargeChunk): Deleted.
+
+2016-03-24  Geoffrey Garen  <ggaren@apple.com>
+
+        bmalloc: small and large objects should share memory
+        https://bugs.webkit.org/show_bug.cgi?id=155866
+
+        Reviewed by Andreas Kling.
+
+        This patch cuts our VM footprint in half. (VM footprint usually doesn't
+        matter, but on iOS there's an artificial VM limit around 700MB, and if
+        you hit it you jetsam / crash.)
+
+        It's also a step toward honoring the hardware page size at runtime,
+        which will reduce memory usage on iOS.
+
+        This patch is a small improvement in peak memory usage because it allows
+        small and large objects to recycle each other's memory. The tradeoff is
+        that we require more metadata, which causes more memory usage after
+        shrinking down from peak memory usage. In the end, we have some memory
+        wins and some losses, and a small win in the mean on our standard memory
+        benchmarks.
+
+        * bmalloc.xcodeproj/project.pbxproj: Removed SuperChunk.
+
+        * bmalloc/Allocator.cpp:
+        (bmalloc::Allocator::reallocate): Adopt a new Heap API for shrinking
+        large objects because it's a little more complicated than it used to be.
+
+        Don't check for equality in the XLarge case because we don't do it in
+        other cases, and it's unlikely that we'll be called for no reason.
+
+        * bmalloc/BumpAllocator.h:
+        (bmalloc::BumpAllocator::allocate): Don't ASSERT isSmall because that's
+        an old concept from when small and large objects were in distinct memory
+        regions.
+
+        * bmalloc/Deallocator.cpp:
+        (bmalloc::Deallocator::deallocateSlowCase): Large objects are not
+        segregated anymore.
+
+        (bmalloc::Deallocator::deallocateLarge): Deleted.
+
+        * bmalloc/Deallocator.h:
+        (bmalloc::Deallocator::deallocateFastCase): Don't ASSERT isSmall(). See
+        above.
+
+        * bmalloc/Heap.cpp:
+        (bmalloc::Heap::scavenge):
+        (bmalloc::Heap::scavengeSmallPage):
+        (bmalloc::Heap::scavengeSmallPages): New helpers for returning cached
+        small pages to the large object heap.
+
+        (bmalloc::Heap::allocateSmallPage): Allocate small pages from the large
+        object heap. This is how we accomplish sharing.
+
+        (bmalloc::Heap::deallocateSmallLine): Handle large objects since we can
+        encounter them on this code path now.
+
+        (bmalloc::Heap::splitAndAllocate): Fixed a bug where we would sometimes
+        not split even though we could.
+
+        Allocating a large object also requires ref'ing its small line so that
+        we can alias memory between small and large objects.
+
+        (bmalloc::Heap::allocateLarge): Return cached small pages before
+        allocating a large object that would fit in a cached small page. This
+        allows some large allocations to reuse small object memory.
+
+        (bmalloc::Heap::shrinkLarge): New helper.
+
+        (bmalloc::Heap::deallocateLarge): Deleted.
+
+        * bmalloc/Heap.h:
+
+        * bmalloc/LargeChunk.h:
+        (bmalloc::LargeChunk::pageBegin):
+        (bmalloc::LargeChunk::pageEnd):
+        (bmalloc::LargeChunk::lines):
+        (bmalloc::LargeChunk::pages):
+        (bmalloc::LargeChunk::begin):
+        (bmalloc::LargeChunk::end):
+        (bmalloc::LargeChunk::LargeChunk):
+        (bmalloc::LargeChunk::get):
+        (bmalloc::LargeChunk::endTag):
+        (bmalloc::LargeChunk::offset):
+        (bmalloc::LargeChunk::object):
+        (bmalloc::LargeChunk::page):
+        (bmalloc::LargeChunk::line):
+        (bmalloc::SmallLine::begin):
+        (bmalloc::SmallLine::end):
+        (bmalloc::SmallPage::begin):
+        (bmalloc::SmallPage::end):
+        (bmalloc::Object::Object):
+        (bmalloc::Object::begin):
+        (bmalloc::Object::pageBegin):
+        (bmalloc::Object::line):
+        (bmalloc::Object::page): I merged all the SmallChunk metadata and code
+        into LargeChunk. Now we use a single class to track both small and large
+        metadata, so we can share memory between small and large objects.
+
+        I'm going to rename this class to Chunk in a follow-up patch.
+
+        * bmalloc/Object.h:
+        (bmalloc::Object::chunk): Updated for LargeChunk transition.
+
+        * bmalloc/ObjectType.cpp:
+        (bmalloc::objectType):
+        * bmalloc/ObjectType.h:
+        (bmalloc::isXLarge):
+        (bmalloc::isSmall): Deleted. The difference between small and large
+        objects is now stored in metadata and is not a property of their
+        virtual address range.
+
+        * bmalloc/SegregatedFreeList.h: One more entry because we cover all of
+        what used to be the super chunk in a large chunk now.
+
+        * bmalloc/Sizes.h: Removed bit masking helpers because we don't use
+        address masks to distinguish small vs large object type anymore.
+
+        * bmalloc/SmallChunk.h: Removed.
+
+        * bmalloc/SmallPage.h:
+        (bmalloc::SmallPage::SmallPage): Store object type per page because any
+        given page can be used for large objects or small objects.
+
+        * bmalloc/SuperChunk.h: Removed.
+
+        * bmalloc/VMHeap.cpp:
+        (bmalloc::VMHeap::VMHeap):
+        (bmalloc::VMHeap::allocateLargeChunk):
+        (bmalloc::VMHeap::allocateSmallChunk): Deleted.
+        (bmalloc::VMHeap::allocateSuperChunk): Deleted.
+        * bmalloc/VMHeap.h:
+        (bmalloc::VMHeap::allocateLargeObject):
+        (bmalloc::VMHeap::deallocateLargeObject):
+        (bmalloc::VMHeap::allocateSmallPage): Deleted.
+        (bmalloc::VMHeap::deallocateSmallPage): Deleted. Removed super chunk and
+        small chunk support.
+
+        * bmalloc/Zone.cpp:
+        (bmalloc::enumerator):
+        * bmalloc/Zone.h:
+        (bmalloc::Zone::largeChunks):
+        (bmalloc::Zone::addLargeChunk):
+        (bmalloc::Zone::superChunks): Deleted.
+        (bmalloc::Zone::addSuperChunk): Deleted. Removed super chunk and
+        small chunk support.
+
+2016-03-23  Geoffrey Garen  <ggaren@apple.com>
+
+        bmalloc: Added an Object helper class
+        https://bugs.webkit.org/show_bug.cgi?id=155818
+
+        Reviewed by Gavin Barraclough.
+
+        Object is an abstraction that breaks out a void* into its component
+        metadata pointers.
+
+        This is slightly faster than recomputing them, and it enables a future
+        patch in which Object will tell us whether it is small or large.
+
+        * bmalloc.xcodeproj/project.pbxproj: Added to the project.
+
+        * bmalloc/Allocator.cpp:
+        (bmalloc::Allocator::reallocate): Use Object to compute size.
+
+        * bmalloc/Deallocator.cpp:
+        (bmalloc::Deallocator::processObjectLog):
+        * bmalloc/Heap.cpp:
+        (bmalloc::Heap::allocateSmallPage):
+        (bmalloc::Heap::deallocateSmallLine):
+        * bmalloc/Heap.h:
+        (bmalloc::Heap::derefSmallLine): Use Object to deallocate.
+
+        * bmalloc/Object.h: Added.
+        (bmalloc::Object::Object):
+        (bmalloc::Object::chunk):
+        (bmalloc::Object::line):
+        (bmalloc::Object::page): Helper class to break out a void* into its
+        component metadata pointers.
+
+        * bmalloc/SmallChunk.h:
+        (bmalloc::SmallChunk::SmallChunk): SmallPage::get doesn't exist anymore
+        so we use our new helper functions instead.
+
+        (bmalloc::SmallChunk::offset):
+        (bmalloc::SmallChunk::object):
+        (bmalloc::SmallChunk::page):
+        (bmalloc::SmallChunk::line):
+        (bmalloc::SmallLine::begin):
+        (bmalloc::SmallLine::end):
+        (bmalloc::SmallPage::begin): New helpers that operate on the data
+        stored in Object.
+
+        (bmalloc::SmallLine::get): Deleted.
+        (bmalloc::SmallPage::get): Deleted.
+
+        * bmalloc/SmallLine.h:
+        (bmalloc::SmallLine::refCount): Added a default ref value for convenience.
+
+        * bmalloc/SmallPage.h:
+        (bmalloc::SmallPage::SmallPage):
+
+2016-03-23  Geoffrey Garen  <ggaren@apple.com>
+
+        bmalloc: process the object log before asking for new memory
+        https://bugs.webkit.org/show_bug.cgi?id=155801
+
+        Reviewed by Gavin Barraclough.
+
+        This is a step toward merging large and small objects: In future, if we
+        have large objects in the log, we need to process them right away to
+        avoid pushing up peak memory use.
+
+        But it also appears to be a speedup and memory use improvement now.
+
+        * bmalloc/Allocator.cpp:
+        (bmalloc::Allocator::allocate):
+        (bmalloc::Allocator::refillAllocatorSlowCase):
+        (bmalloc::Allocator::allocateLarge): Process the log before asking for
+        more memory.
+
+        * bmalloc/Deallocator.cpp:
+        (bmalloc::Deallocator::processObjectLog):
+        (bmalloc::Deallocator::deallocateSlowCase):
+        * bmalloc/Deallocator.h: Provide a public API for processing the object log.
+
+        * bmalloc/Heap.cpp:
+        (bmalloc::Heap::allocateSmallPage): Pop fragmented pages from the front
+        instead of from the back. This resolves a regression on tree_churn
+        --parallel. Popping from the front gives us the oldest pages. The oldest
+        pages have had the most time to accumulate free lines. They are therefore
+        the least fragmented on average.
+
+        * bmalloc/List.h:
+        (bmalloc::List::popFront):
+        (bmalloc::List::insertAfter): New API to pop from front.
+
+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
+
+        Reviewed by Michael Saboff.
+
+        If a largeChunk contains N bytes and we allocate objects of size
+        N / 2 + 8 bytes, then we waste 50% of physical memory at peak.
+
+        This patch sets largeMax to N / 2, reducing maximum waste to 25%.
+
+        * bmalloc/BoundaryTag.h:
+        * bmalloc/LargeChunk.h:
+        (bmalloc::LargeChunk::LargeChunk):
+        * bmalloc/SegregatedFreeList.cpp:
+        (bmalloc::SegregatedFreeList::SegregatedFreeList):
+        (bmalloc::SegregatedFreeList::insert): Honor largeMax vs largeObjectMax.
+
+        * bmalloc/Sizes.h: Distinguish between the largest thing we can store
+        in a free list (largeObjectMax) and the largest thing we're willing to
+        allocate (largeMax).
+
+2016-03-20  Dan Bernstein  <mitz@apple.com>
+
+        [Mac] Determine TARGET_MAC_OS_X_VERSION_MAJOR from MACOSX_DEPLOYMENT_TARGET rather than from MAC_OS_X_VERSION_MAJOR
+        https://bugs.webkit.org/show_bug.cgi?id=155707
+        <rdar://problem/24980691>
+
+        Reviewed by Darin Adler.
+
+        * Configurations/Base.xcconfig: Set TARGET_MAC_OS_X_VERSION_MAJOR based on the last
+          component of MACOSX_DEPLOYMENT_TARGET.
+        * Configurations/DebugRelease.xcconfig: For engineering builds, preserve the behavior of
+          TARGET_MAC_OS_X_VERSION_MAJOR being the host’s OS version.
+
+2016-03-20  Dan Bernstein  <mitz@apple.com>
+
+        Update build settings
+
+        Rubber-stamped by Andy Estes.
+
+        * Configurations/DebugRelease.xcconfig:
+
+2016-03-14  Geoffrey Garen  <ggaren@apple.com>
+
+        Unreviewed, rolling out r197955.
+
+        I decided to go in another direction
+
+        Reverted changeset:
+
+        "bmalloc: Rename SmallPage to SmallRun"
+        https://bugs.webkit.org/show_bug.cgi?id=155320
+        http://trac.webkit.org/changeset/197955
+
+2016-03-10  Geoffrey Garen  <ggaren@apple.com>
+
+        bmalloc: Rename SmallPage to SmallRun
+        https://bugs.webkit.org/show_bug.cgi?id=155320
+
+        Reviewed by Alex Christensen.
+
+        A page is a fixed-size set of lines.
+
+        A run is an variable-sized set of lines.
+
+        We want to start using runs because:
+
+            (a) we want to support varying the hardware page size by OS;
+
+            (b) we want to support allocations larger than our current page size.
+
+        * bmalloc.xcodeproj/project.pbxproj:
+        * bmalloc/Allocator.cpp:
+        (bmalloc::Allocator::reallocate):
+        * bmalloc/Heap.cpp:
+        (bmalloc::Heap::Heap):
+        (bmalloc::Heap::initializeSmallRunMetadata):
+        (bmalloc::Heap::scavenge):
+        (bmalloc::Heap::scavengeSmallRuns):
+        (bmalloc::Heap::allocateSmallBumpRanges):
+        (bmalloc::Heap::allocateSmallRun):
+        (bmalloc::Heap::deallocateSmallLine):
+        (bmalloc::Heap::initializeLineMetadata): Deleted.
+        (bmalloc::Heap::scavengeSmallPages): Deleted.
+        (bmalloc::Heap::allocateSmallPage): Deleted.
+        * bmalloc/Heap.h:
+        * bmalloc/LineMetadata.h:
+        * bmalloc/SmallChunk.h:
+        (bmalloc::SmallChunk::begin):
+        (bmalloc::SmallChunk::end):
+        (bmalloc::SmallChunk::lines):
+        (bmalloc::SmallChunk::runs):
+        (bmalloc::SmallChunk::SmallChunk):
+        (bmalloc::SmallLine::end):
+        (bmalloc::SmallRun::get):
+        (bmalloc::SmallRun::begin):
+        (bmalloc::SmallRun::end):
+        (bmalloc::SmallChunk::pages): Deleted.
+        (bmalloc::SmallPage::get): Deleted.
+        (bmalloc::SmallPage::begin): Deleted.
+        (bmalloc::SmallPage::end): Deleted.
+        * bmalloc/SmallPage.h: Removed.
+        * bmalloc/SmallRun.h: Copied from Source/bmalloc/bmalloc/SmallPage.h.
+        (bmalloc::SmallRun::SmallRun):
+        (bmalloc::SmallRun::ref):
+        (bmalloc::SmallRun::deref):
+        (bmalloc::SmallPage::SmallPage): Deleted.
+        (bmalloc::SmallPage::ref): Deleted.
+        (bmalloc::SmallPage::deref): Deleted.
+        * bmalloc/VMHeap.cpp:
+        (bmalloc::VMHeap::allocateSmallChunk):
+        (bmalloc::VMHeap::allocateLargeChunk):
+        * bmalloc/VMHeap.h:
+        (bmalloc::VMHeap::allocateSmallRun):
+        (bmalloc::VMHeap::allocateLargeObject):
+        (bmalloc::VMHeap::deallocateSmallRun):
+        (bmalloc::VMHeap::deallocateLargeObject):
+        (bmalloc::VMHeap::allocateSmallPage): Deleted.
+        (bmalloc::VMHeap::deallocateSmallPage): Deleted.
+
+2016-03-08  Geoffrey Garen  <ggaren@apple.com>
+
+        Unreviewed, rolling in r197722.
+        https://bugs.webkit.org/show_bug.cgi?id=155171
+
+        The right calculation for our static_assert is actually:
+
+            sizeof(SmallChunk) % vmPageSize + 2 * smallMax <= vmPageSize
+
+        instead of:
+
+            sizeof(SmallChunk) % vmPageSize + smallMax <= vmPageSize
+
+        smallMax is not enough because line metadata might require us to begin
+        allocation at an offset as large as smallMax, so we need 2 * smallMax.
+
+        Once correct, this static_assert fires, and we fix it by increasing
+        the alignment of SmallChunk.
+
+        Restored changeset:
+
+        "bmalloc: Use List<T> instead of Vector<T> in some places"
+        https://bugs.webkit.org/show_bug.cgi?id=155150
+        http://trac.webkit.org/changeset/197722
+
+2016-03-08  Commit Queue  <commit-queue@webkit.org>
+
+        Unreviewed, rolling out r197722.
+        https://bugs.webkit.org/show_bug.cgi?id=155171
+
+        This change caused 800+ JSC test failures (Requested by
+        ryanhaddad on #webkit).
+
+        Reverted changeset:
+
+        "bmalloc: Use List<T> instead of Vector<T> in some places"
+        https://bugs.webkit.org/show_bug.cgi?id=155150
+        http://trac.webkit.org/changeset/197722
+
+2016-03-07  Geoffrey Garen  <ggaren@apple.com>
+
+        bmalloc: Use List<T> instead of Vector<T> in some places
+        https://bugs.webkit.org/show_bug.cgi?id=155150
+
+        Reviewed by Andreas Kling.
+
+        Vector<T> is expensive when you want a lot of them because our minimum
+        allocation size is the system page size.
+
+        * bmalloc.xcodeproj/project.pbxproj: Added a List<T> class.
+
+        * bmalloc/Heap.cpp:
+        (bmalloc::Heap::scavengeSmallPages):
+        (bmalloc::Heap::allocateSmallPage): Use the List<T> API. No need to check
+        for stale entries anymore because List<T> supports O(1) eager removal
+        and we remove eagerly now.
+
+        (bmalloc::Heap::deallocateSmallLine): Remove eagerly. This simplifies
+        the allocation code and it is also required for correctness since we
+        only have enough metadata to be in one list at a time.
+
+        * bmalloc/Heap.h: List!
+
+        * bmalloc/SmallChunk.h: Made this assert a little more precise since this
+        patch triggered the old version in a benign way.
+
+        (bmalloc::SmallChunk::SmallChunk): This code moved to the SmallPage
+        constructor.
+
+        * bmalloc/SmallPage.h:
+        (bmalloc::SmallPage::SmallPage): Accomodate the List<T> data structure.
+        This is a net memory savings on Mac for heaps smaller than ~128MB and on
+        iOS for heaps smaller than ~512MB. The maximum memory saved is 512kB on
+        Mac and 2MB on iOS. For larger heaps, there's a memory cost of 0.4% on
+        Mac and 0.1% on iOS.
+
+        * bmalloc/VMHeap.h:
+        (bmalloc::VMHeap::allocateSmallPage): Use List<T> API.
+
+2016-03-03  Geoffrey Garen  <ggaren@apple.com>
+
+        Unreviewed, rolling in r197174.
+        https://bugs.webkit.org/show_bug.cgi?id=154762
+
+        The right calculation for alignment is actually:
+
+            vmAlignment - getpagesize() + vmSize
+
+        instead of:
+
+            vmAlignment - vmPageSize + vmSize
+
+        The vmPageSize might be larger than getpagesize().
+
+        Restored changeset:
+
+        "bmalloc: Added a fast XLarge allocator"
+        https://bugs.webkit.org/show_bug.cgi?id=154720
+        http://trac.webkit.org/changeset/197174
+
+2016-02-26  Commit Queue  <commit-queue@webkit.org>
+
+        Unreviewed, rolling out r197174.
+        https://bugs.webkit.org/show_bug.cgi?id=154762
+
+        This change caused LayoutTests to crash on iOS simulator
+        (Requested by ryanhaddad on #webkit).
+
+        Reverted changeset:
+
+        "bmalloc: Added a fast XLarge allocator"
+        https://bugs.webkit.org/show_bug.cgi?id=154720
+        http://trac.webkit.org/changeset/197174
+
+2016-02-25  Geoffrey Garen  <ggaren@apple.com>
+
+        bmalloc: Added a fast XLarge allocator
+        https://bugs.webkit.org/show_bug.cgi?id=154720
+
+        Reviewed by Andreas Kling.
+
+        This is a big speedup for XLarge allocations because it avoids mmap
+        and page fault churn. It also enables future design changes to handle
+        a smaller size range on the fast path.
+
+        * bmalloc.xcodeproj/project.pbxproj:
+
+        * bmalloc/Algorithm.h:
+        (bmalloc::roundUpToMultipleOf):
+        (bmalloc::roundDownToMultipleOf): Added a non-constant round down.
+
+        * bmalloc/Allocator.cpp:
+        (bmalloc::Allocator::tryAllocate): XLarge no longer requires the caller
+        to align things.
+
+        (bmalloc::Allocator::allocate): Tweaked the alignment calculation for
+        clarity. When alignment and largeAlignment are equal, no adjustment
+        is necessary since all allocations guarantee largeAlignment.
+
+        (bmalloc::Allocator::reallocate): Updated for interface change.
+
+        Note that the new interface fixes some concurrency bugs. The old code
+        kept an iterator into the XLarge allocator across lock drop and acquisition,
+        which is not cool.
+
+        (bmalloc::Allocator::allocateXLarge): XLarge no longer requires the caller
+        to align things.
+
+        * bmalloc/Heap.cpp:
+        (bmalloc::Heap::scavengeXLargeObjects): Added scavenging for XLarge.
+
+        (bmalloc::Heap::allocateXLarge):
+
+        (bmalloc::Heap::splitAndAllocate): Split XLarge objects to xLargeAlignment.
+
+        (bmalloc::Heap::tryAllocateXLarge):
+        (bmalloc::Heap::xLargeSize):
+        (bmalloc::Heap::shrinkXLarge):
+        (bmalloc::Heap::deallocateXLarge): Allocate from our map before going
+        to the OS.
+
+        (bmalloc::Heap::findXLarge): Deleted.
+
+        * bmalloc/Heap.h:
+
+        * bmalloc/LargeObject.h:
+        (bmalloc::LargeObject::split):
+
+        * bmalloc/ObjectType.h:
+        (bmalloc::isXLarge): Give XLarge objects an explicit alignment for clarity.
+
+        * bmalloc/Range.h:
+        (bmalloc::Range::size):
+        (bmalloc::Range::operator!):
+        (bmalloc::Range::operator bool):
+        (bmalloc::Range::operator<):
+        (bmalloc::canMerge):
+        (bmalloc::merge): Some helpers that were useful in writing this patch.
+
+        * bmalloc/Sizes.h:
+
+        * bmalloc/SortedVector.h: Added.
+        (bmalloc::SortedVector::Bucket::Bucket):
+        (bmalloc::SortedVector::Bucket::operator<):
+        (bmalloc::SortedVector::iterator::iterator):
+        (bmalloc::SortedVector::iterator::operator++):
+        (bmalloc::SortedVector::iterator::operator!=):
+        (bmalloc::SortedVector::iterator::operator*):
+        (bmalloc::SortedVector::iterator::operator->):
+        (bmalloc::SortedVector::iterator::skipDeletedBuckets):
+        (bmalloc::SortedVector::begin):
+        (bmalloc::SortedVector::end):
+        (bmalloc::SortedVector<T>::insert):
+        (bmalloc::SortedVector<T>::find):
+        (bmalloc::SortedVector<T>::get):
+        (bmalloc::SortedVector<T>::take):
+        (bmalloc::SortedVector<T>::shrinkToFit): A simple abstraction for keeping
+        a sorted vector. Insertion is average amortized log(n) because we keep
+        deleted buckets that we can reuse.
+
+        This is better than a tree because we get better locality, less memory
+        use, and simpler code. Also, trees require a node memory allocator, and
+        implementing a memory allocator in a memory allocator is no fun.
+
+        Arguably we should use a hash table instead. But that's more code, and
+        sorted vector has other nice properties that we might want to take
+        adavantage of in the future.
+
+        * bmalloc/VMAllocate.h:
+        (bmalloc::tryVMAllocate): Fixed an inaccuracy in the alignment calculation
+        here. This code was sort of trying to enforce the alignment that the
+        XLarge allocator enforces -- but it's better to enforce that alignment
+        there.
+
+        The right calculation is:
+
+            vmAlignment - vmPageSize + vmSize
+
+        because the worst case is when you are aligned to 0 + vmPageSize, and
+        you must walk forward vmAlignment - vmPageSize to reach the next
+        vmAlignment.
+
+        (bmalloc::tryVMExtend): Deleted. No need to go back to the OS for VM
+        since we manage our own.
+
+        * bmalloc/VMHeap.cpp:
+        (bmalloc::VMHeap::allocateLargeChunk): Updated for clarity. When we
+        grow the large heap we know that grown region is where the next allocation
+        will take place, so we return it directly instead of pushing it to the
+        free list.
+
+        This fixes a subtle bug where an overly conservative aligned allocation
+        algorithm can fail to allocate at all when it grows the heap.
+
+        * bmalloc/VMHeap.h:
+        (bmalloc::VMHeap::allocateLargeObject): Ditto.
+        (bmalloc::VMHeap::allocateLargeObject): Ditto.
+
+        * bmalloc/VMState.h:
+        (bmalloc::merge): Added a helper.
+
+        * bmalloc/Vector.h:
+        (bmalloc::Vector::begin):
+        (bmalloc::Vector::end):
+        (bmalloc::Vector::size):
+        (bmalloc::Vector::capacity):
+        (bmalloc::Vector::last):
+        (bmalloc::Vector::pop):
+        (bmalloc::Vector<T>::push):
+        (bmalloc::Vector<T>::pop):
+        (bmalloc::Vector<T>::shrink): Use a proper iterator API to play nice
+        with std algorithms.
+
+        (bmalloc::Vector<T>::insert): New function required by SortedVector.
+
+        (bmalloc::Vector<T>::reallocateBuffer):
+        (bmalloc::Vector<T>::shrinkCapacity): Allow for shrinking back all the way
+        to 0 because that's what shrinkToFit wants.
+        (bmalloc::Vector<T>::growCapacity):
+        (bmalloc::Vector<T>::shrinkToFit):
+
+        * bmalloc/XLargeMap.cpp: Added. Helper data structure for managing XLarge
+        objects. We have enough granularity in our metadata to represent any
+        kind of address range.
+
+        We store free ranges in a flat vector because most programs have very
+        few individual free XLarge ranges. (They usually merge.)
+
+        We store allocated ranges in a sorted vector because programs might
+        allocate lots of XLarge ranges. For example, if the XLarge minimum is
+        128kB, and you have a 1GB process, that's 8192 ranges. Linear scan would
+        examine 8192 items but binary search only 13.
+
+        Empirically, this is 1.5X faster than our current large allocator if you
+        modify MallocBench/big to allocate XLarge objects and not to initialize
+        objects and you allocate 128kB-256kB objects in a 1GB address space.
+
+        (bmalloc::XLargeMap::takeFree): Be careful about overflow in this function
+        because we support super huge pointers, alignments, and sizes.
+
+        (bmalloc::XLargeMap::addFree): Merge eagerly on free because the cost
+        of missing an XLarge opportunity is catastrophic. Also, I discovered
+        by experiment that any allocator that doesn't merge eagerly can create
+        lots of subtle opportunities for snowballing fragmentation, as
+        fragmentation in range A forces you to chop up range B, and so on.
+
+        We allocate "first fit" (allocating the lowest address) because someone
+        wrote a paper once that said that it's the best algorithm to combat
+        fragmentation (even though worst case fragmentation is unavoidable
+        regardless of algorithm).
+
+        (bmalloc::XLargeMap::addAllocated):
+        (bmalloc::XLargeMap::getAllocated):
+        (bmalloc::XLargeMap::takeAllocated):
+        (bmalloc::XLargeMap::shrinkToFit):
+        (bmalloc::XLargeMap::takePhysical):
+        (bmalloc::XLargeMap::addVirtual):
+        * bmalloc/XLargeMap.h: Added.
+        (bmalloc::XLargeMap::Allocation::operator<):
+
+        * bmalloc/XLargeRange.h: Added.
+        (bmalloc::XLargeRange::XLargeRange):
+        (bmalloc::XLargeRange::vmState):
+        (bmalloc::XLargeRange::setVMState):
+        (bmalloc::canMerge):
+        (bmalloc::merge):
+        (bmalloc::XLargeRange::split): Helper for tracking VMState in a range.
+
+2016-02-23  Dan Bernstein  <mitz@apple.com>
+
+        [Xcode] Linker errors display mangled names, but no longer should
+        https://bugs.webkit.org/show_bug.cgi?id=154632
+
+        Reviewed by Sam Weinig.
+
+        * Configurations/Base.xcconfig: Stop setting LINKER_DISPLAYS_MANGLED_NAMES to YES.
+
+2016-02-22  Konstantin Tokarev  <annulen@yandex.ru>
+
+        Fixed compilation of bmalloc with GCC 4.8 after r196873.
+        https://bugs.webkit.org/show_bug.cgi?id=154534
+
+        Reviewed by Mark Lam.
+
+        See https://gcc.gnu.org/bugzilla/show_bug.cgi?id=55382.
+
+        * bmalloc/LargeChunk.h:
+        * bmalloc/SmallChunk.h:
+
+2016-02-21  Geoffrey Garen  <ggaren@apple.com>
+
+        bmalloc: Don't use a whole page for metadata
+        https://bugs.webkit.org/show_bug.cgi?id=154510
+
+        Reviewed by Andreas Kling.
+
+        (1) Don't round up metadata to a page boundary. This saves 1.5% dirty
+        memory on iOS and 0.2% on Mac. It also enables a future patch to allocate
+        smaller chunks without wasting memory.
+
+        (2) Initialize metadata lazily. This saves dirty memory when the program
+        allocates primarily small or large objects (but not both), leaving some
+        metadata uninitialized.
+
+        * bmalloc.xcodeproj/project.pbxproj: Medium objects are gone now.
+
+        * bmalloc/BumpAllocator.h:
+        (bmalloc::BumpAllocator::refill): Added an ASSERT to help debug a bug
+        I cause while working on this patch.
+
+        * bmalloc/Heap.cpp:
+        (bmalloc::Heap::allocateSmallBumpRanges): Ditto.
+
+        (bmalloc::Heap::splitAndAllocate):
+        (bmalloc::Heap::allocateLarge): Updated for interface change.
+
+        * bmalloc/LargeChunk.h: Changed the boundaryTagCount calculation to
+        a static_assert.
+
+        Don't round up to page boundary. (See above.)
+
+        (bmalloc::LargeChunk::LargeChunk): Moved code here from LargeChunk::init.
+        A constructor is a more natural / automatic way to do this initialization.
+
+        * bmalloc/LargeObject.h:
+        (bmalloc::LargeObject::init): Deleted. Moved to LargeChunk.
+
+        * bmalloc/Sizes.h: Chagned largeChunkMetadataSize to a simpler constant
+        because metadata size no longer varies by page size.
+
+        * bmalloc/SmallChunk.h:
+        (bmalloc::SmallChunk::begin):
+        (bmalloc::SmallChunk::end):
+        (bmalloc::SmallChunk::lines):
+        (bmalloc::SmallChunk::pages): Use std::array to make begin/end
+        calculations easier.
+
+        (bmalloc::SmallChunk::SmallChunk): Treat our metadata like a series
+        of allocated objects. We used to avoid trampling our metadata by
+        starting object memory at the next page. Now we share the first page
+        between metadata and objects, and we account for metadata explicitly.
+
+        * bmalloc/SuperChunk.h:
+        (bmalloc::SuperChunk::SuperChunk):
+        (bmalloc::SuperChunk::smallChunk):
+        (bmalloc::SuperChunk::largeChunk):
+        (bmalloc::SuperChunk::create): Deleted. Don't eagerly run the SmallChunk
+        and LargeChunk constructors. We'll run them lazily as needed.
+
+        * bmalloc/VMHeap.cpp:
+        (bmalloc::VMHeap::VMHeap):
+        (bmalloc::VMHeap::allocateSmallChunk):
+        (bmalloc::VMHeap::allocateLargeChunk):
+        (bmalloc::VMHeap::allocateSuperChunk):
+        (bmalloc::VMHeap::grow): Deleted. Track small and large chunks explicitly
+        so we can initialize them lazily.
+
+        * bmalloc/VMHeap.h:
+        (bmalloc::VMHeap::allocateSmallPage):
+        (bmalloc::VMHeap::allocateLargeObject): Specify whether we're allocating
+        a small or large chunk since we don't allocate both at once anymore.
+
 2016-02-20  Mark Lam  <mark.lam@apple.com>
 
         Use of inlined asm statements causes problems for -std=c99 builds.