Implement a new allocator for backing stores
authormhahnenberg@apple.com <mhahnenberg@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Thu, 19 Jan 2012 21:49:56 +0000 (21:49 +0000)
committermhahnenberg@apple.com <mhahnenberg@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Thu, 19 Jan 2012 21:49:56 +0000 (21:49 +0000)
commitfa03984666169311a6d1115e9620005a56472483
tree545d60096ba7c50e829d2567deada74ef495706e
parenta8f0a9a0a04d527412e7654d44ab3b46b95b2782
Implement a new allocator for backing stores
https://bugs.webkit.org/show_bug.cgi?id=75181

Reviewed by Filip Pizlo.

Source/JavaScriptCore:

We want to move away from using fastMalloc for the backing stores for
some of our objects (e.g. JSArray, JSObject, JSString, etc).  These backing
stores have a nice property in that they only have a single owner (i.e. a
single pointer to them at any one time).  One way that we can take advantage
of this property is to implement a simple bump allocator/copying collector,
which will run alongside our normal mark/sweep collector, that only needs to
update the single owner pointer rather than having to redirect an arbitrary
number of pointers in from-space to to-space.

This plan can give us a number of benefits. We can beat fastMalloc in terms
of both performance and memory usage, we can track how much memory we're using
far more accurately than our rough estimation now through the use of
reportExtraMemoryCost, and we can allocate arbitrary size objects (as opposed
to being limited to size classes like we have been historically). This is also
another step toward moving away from lazy destruction, which will improve our memory footprint.

We start by creating said allocator and moving the ArrayStorage for JSArray
to use it rather than fastMalloc.

The design of the collector is as follows:
Allocation:
-The collector allocates 64KB chunks from the OS to use for object allocation.
-Each chunk contains an offset, a flag indicating if the block has been pinned,
 and a payload, along with next and prev pointers so that they can be put in DoublyLinkedLists.
-Any allocation greater than 64KB gets its own separate oversize block, which
 is managed separately from the rest.
-If the allocator receives a request for more than the remaining amount in the
 current block, it grabs a fresh block.
-Grabbing a fresh block means grabbing one off of the global free list (which is now
 shared between the mark/sweep allocator and the bump allocator) if there is one.
 If there isn't a new one we do one of two things: allocate a new block from the OS
 if we're not ready for a GC yet, or run a GC and then try again. If we still don't
 have enough space after the GC, we allocate a new block from the OS.

Garbage collection:
-At the start of garbage collection during conservative stack scanning, if we encounter
 what appears to be a pointer to a bump-allocated block of memory, we pin that block so
 that it will not be copied for this round of collection.
-We also pin any oversize blocks that we encounter, which effectively doubles as a
 "mark bit" for that block. Any oversize blocks that aren't pinned at the end of copying
 are given back to the OS.
-Marking threads are now also responsible for copying bump-allocated objects to newSpace
-Each marking thread has a private 64KB block into which it copies bump-allocated objects that it encounters.
-When that block fills up, the marking thread gives it back to the allocator and requests a new one.
-When all marking has concluded, each thread gives back its copy block, even if it isn't full.
-At the conclusion of copying (which is done by the end of the marking phase), we un-pin
 any pinned blocks and give any blocks left in from-space to the global free list.

* CMakeLists.txt:
* GNUmakefile.list.am:
* JavaScriptCore.gypi:
* JavaScriptCore.vcproj/JavaScriptCore/JavaScriptCore.vcproj:
* JavaScriptCore.vcproj/WTF/WTF.vcproj:
* JavaScriptCore.xcodeproj/project.pbxproj:
* Target.pri:
* heap/AllocationSpace.cpp:
(JSC::AllocationSpace::allocateSlowCase):
(JSC::AllocationSpace::allocateBlock):
(JSC::AllocationSpace::freeBlocks):
* heap/AllocationSpace.h:
(JSC::AllocationSpace::waterMark):
* heap/BumpBlock.h: Added.
(JSC::BumpBlock::BumpBlock):
* heap/BumpSpace.cpp: Added.
(JSC::BumpSpace::tryAllocateSlowCase):
* heap/BumpSpace.h: Added.
(JSC::BumpSpace::isInCopyPhase):
(JSC::BumpSpace::totalMemoryAllocated):
(JSC::BumpSpace::totalMemoryUtilized):
* heap/BumpSpaceInlineMethods.h: Added.
(JSC::BumpSpace::BumpSpace):
(JSC::BumpSpace::init):
(JSC::BumpSpace::contains):
(JSC::BumpSpace::pin):
(JSC::BumpSpace::startedCopying):
(JSC::BumpSpace::doneCopying):
(JSC::BumpSpace::doneFillingBlock):
(JSC::BumpSpace::recycleBlock):
(JSC::BumpSpace::getFreshBlock):
(JSC::BumpSpace::borrowBlock):
(JSC::BumpSpace::addNewBlock):
(JSC::BumpSpace::allocateNewBlock):
(JSC::BumpSpace::fitsInBlock):
(JSC::BumpSpace::fitsInCurrentBlock):
(JSC::BumpSpace::tryAllocate):
(JSC::BumpSpace::tryAllocateOversize):
(JSC::BumpSpace::allocateFromBlock):
(JSC::BumpSpace::tryReallocate):
(JSC::BumpSpace::tryReallocateOversize):
(JSC::BumpSpace::isOversize):
(JSC::BumpSpace::isPinned):
(JSC::BumpSpace::oversizeBlockFor):
(JSC::BumpSpace::blockFor):
* heap/ConservativeRoots.cpp:
(JSC::ConservativeRoots::ConservativeRoots):
(JSC::ConservativeRoots::genericAddPointer):
(JSC::ConservativeRoots::add):
* heap/ConservativeRoots.h:
* heap/Heap.cpp:
(JSC::Heap::Heap):
(JSC::Heap::blockFreeingThreadMain):
(JSC::Heap::reportExtraMemoryCostSlowCase):
(JSC::Heap::getConservativeRegisterRoots):
(JSC::Heap::markRoots):
(JSC::Heap::collect):
(JSC::Heap::releaseFreeBlocks):
* heap/Heap.h:
(JSC::Heap::waterMark):
(JSC::Heap::highWaterMark):
(JSC::Heap::setHighWaterMark):
(JSC::Heap::tryAllocateStorage):
(JSC::Heap::tryReallocateStorage):
* heap/HeapBlock.h: Added.
(JSC::HeapBlock::HeapBlock):
* heap/MarkStack.cpp:
(JSC::MarkStackThreadSharedData::MarkStackThreadSharedData):
(JSC::SlotVisitor::drain):
(JSC::SlotVisitor::drainFromShared):
(JSC::SlotVisitor::startCopying):
(JSC::SlotVisitor::allocateNewSpace):
(JSC::SlotVisitor::copy):
(JSC::SlotVisitor::copyAndAppend):
(JSC::SlotVisitor::doneCopying):
* heap/MarkStack.h:
* heap/MarkedBlock.cpp:
(JSC::MarkedBlock::recycle):
(JSC::MarkedBlock::MarkedBlock):
* heap/MarkedBlock.h:
* heap/MarkedSpace.cpp:
(JSC::MarkedSpace::MarkedSpace):
* heap/MarkedSpace.h:
(JSC::MarkedSpace::allocate):
(JSC::MarkedSpace::forEachBlock):
(JSC::MarkedSpace::SizeClass::resetAllocator):
* heap/SlotVisitor.h:
(JSC::SlotVisitor::SlotVisitor):
* heap/TinyBloomFilter.h:
(JSC::TinyBloomFilter::reset):
* runtime/JSArray.cpp:
(JSC::JSArray::JSArray):
(JSC::JSArray::finishCreation):
(JSC::JSArray::tryFinishCreationUninitialized):
(JSC::JSArray::~JSArray):
(JSC::JSArray::enterSparseMode):
(JSC::JSArray::defineOwnNumericProperty):
(JSC::JSArray::setLengthWritable):
(JSC::JSArray::getOwnPropertySlotByIndex):
(JSC::JSArray::getOwnPropertyDescriptor):
(JSC::JSArray::putByIndexBeyondVectorLength):
(JSC::JSArray::deletePropertyByIndex):
(JSC::JSArray::getOwnPropertyNames):
(JSC::JSArray::increaseVectorLength):
(JSC::JSArray::unshiftCountSlowCase):
(JSC::JSArray::setLength):
(JSC::JSArray::pop):
(JSC::JSArray::unshiftCount):
(JSC::JSArray::visitChildren):
(JSC::JSArray::sortNumeric):
(JSC::JSArray::sort):
(JSC::JSArray::compactForSorting):
(JSC::JSArray::subclassData):
(JSC::JSArray::setSubclassData):
(JSC::JSArray::checkConsistency):
* runtime/JSArray.h:
(JSC::JSArray::inSparseMode):
(JSC::JSArray::isLengthWritable):
* wtf/CheckedBoolean.h: Added.
(CheckedBoolean::CheckedBoolean):
(CheckedBoolean::~CheckedBoolean):
(CheckedBoolean::operator bool):
* wtf/DoublyLinkedList.h:
(WTF::::push):
* wtf/StdLibExtras.h:
(WTF::isPointerAligned):

Source/JavaScriptGlue:

Added forwarding header for new CheckedBoolean used in the bump allocator.

* ForwardingHeaders/wtf/CheckedBoolean.h: Added.

Source/WebCore:

No new tests.

Added forwarding header for new CheckedBoolean used in the bump allocator.

* ForwardingHeaders/wtf/CheckedBoolean.h: Added.

git-svn-id: https://svn.webkit.org/repository/webkit/trunk@105442 268f45cc-cd09-0410-ab3c-d52691b4dbfc
36 files changed:
Source/JavaScriptCore/CMakeLists.txt
Source/JavaScriptCore/ChangeLog
Source/JavaScriptCore/GNUmakefile.list.am
Source/JavaScriptCore/JavaScriptCore.gypi
Source/JavaScriptCore/JavaScriptCore.vcproj/JavaScriptCore/JavaScriptCore.vcproj
Source/JavaScriptCore/JavaScriptCore.vcproj/WTF/WTF.vcproj
Source/JavaScriptCore/JavaScriptCore.xcodeproj/project.pbxproj
Source/JavaScriptCore/Target.pri
Source/JavaScriptCore/heap/AllocationSpace.cpp
Source/JavaScriptCore/heap/AllocationSpace.h
Source/JavaScriptCore/heap/BumpBlock.h [new file with mode: 0644]
Source/JavaScriptCore/heap/BumpSpace.cpp [new file with mode: 0644]
Source/JavaScriptCore/heap/BumpSpace.h [new file with mode: 0644]
Source/JavaScriptCore/heap/BumpSpaceInlineMethods.h [new file with mode: 0644]
Source/JavaScriptCore/heap/ConservativeRoots.cpp
Source/JavaScriptCore/heap/ConservativeRoots.h
Source/JavaScriptCore/heap/Heap.cpp
Source/JavaScriptCore/heap/Heap.h
Source/JavaScriptCore/heap/HeapBlock.h [new file with mode: 0644]
Source/JavaScriptCore/heap/MarkStack.cpp
Source/JavaScriptCore/heap/MarkStack.h
Source/JavaScriptCore/heap/MarkedBlock.cpp
Source/JavaScriptCore/heap/MarkedBlock.h
Source/JavaScriptCore/heap/MarkedSpace.cpp
Source/JavaScriptCore/heap/MarkedSpace.h
Source/JavaScriptCore/heap/SlotVisitor.h
Source/JavaScriptCore/heap/TinyBloomFilter.h
Source/JavaScriptCore/runtime/JSArray.cpp
Source/JavaScriptCore/runtime/JSArray.h
Source/JavaScriptCore/wtf/CheckedBoolean.h [new file with mode: 0644]
Source/JavaScriptCore/wtf/DoublyLinkedList.h
Source/JavaScriptCore/wtf/StdLibExtras.h
Source/JavaScriptGlue/ChangeLog
Source/JavaScriptGlue/ForwardingHeaders/wtf/CheckedBoolean.h [new file with mode: 0644]
Source/WebCore/ChangeLog
Source/WebCore/ForwardingHeaders/wtf/CheckedBoolean.h [new file with mode: 0644]