GC should use scrambled free-lists
authorfpizlo@apple.com <fpizlo@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Fri, 2 Jun 2017 15:59:22 +0000 (15:59 +0000)
committerfpizlo@apple.com <fpizlo@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Fri, 2 Jun 2017 15:59:22 +0000 (15:59 +0000)
commit3927308e1cd63bce46f5e642ac6a5c34bcf2e99b
tree16bac1bc49ea5f5728678e0d99ed6eda96f6f912
parent72d5836077ec6cc2cf6c649b4329fa4dce0f0ca9
GC should use scrambled free-lists
https://bugs.webkit.org/show_bug.cgi?id=172793

Reviewed by Mark Lam.

Previously, our bump'n'pop allocator would use a conventional linked-list for the free-list.
The linked-list would be threaded through free memory, as is the usual convention.

This scrambles the next pointers of that free-list. It also scrambles the head pointer, because
this leads to a more natural fast-path structure and saves one register on ARM64.

The secret with which pointers are scrambled is per-allocator. Allocators choose a new secret
every time they do a sweep-to-pop.

This doesn't change the behavior of the bump part of bump'n'pop, but it does refactor the code
quite a bit. Previously, there were four copies of the allocator fast path: two in
MarkedAllocatorInlines.h, one in MarkedAllocator.cpp, and one in AssemblyHelpers.h. The JIT one
was obviously different-looking, but the other three were almost identical. This moves all of
that logic into FreeList. There are now just two copies of the allocator: FreeListInlines.h and
AssemblyHelpers.h.

This appears to be just as fast as our previously allocator.

* JavaScriptCore.xcodeproj/project.pbxproj:
* heap/FreeList.cpp:
(JSC::FreeList::FreeList):
(JSC::FreeList::~FreeList):
(JSC::FreeList::clear):
(JSC::FreeList::initializeList):
(JSC::FreeList::initializeBump):
(JSC::FreeList::contains):
(JSC::FreeList::dump):
* heap/FreeList.h:
(JSC::FreeList::allocationWillFail):
(JSC::FreeList::originalSize):
(JSC::FreeList::addressOfList):
(JSC::FreeList::offsetOfBlock):
(JSC::FreeList::offsetOfList):
(JSC::FreeList::offsetOfIndex):
(JSC::FreeList::offsetOfPayloadEnd):
(JSC::FreeList::offsetOfRemaining):
(JSC::FreeList::offsetOfOriginalSize):
(JSC::FreeList::FreeList): Deleted.
(JSC::FreeList::list): Deleted.
(JSC::FreeList::bump): Deleted.
(JSC::FreeList::operator==): Deleted.
(JSC::FreeList::operator!=): Deleted.
(JSC::FreeList::operator bool): Deleted.
* heap/FreeListInlines.h: Added.
(JSC::FreeList::addFreeCell):
(JSC::FreeList::allocate):
(JSC::FreeList::forEach):
(JSC::FreeList::toOffset):
(JSC::FreeList::fromOffset):
* heap/IncrementalSweeper.cpp:
(JSC::IncrementalSweeper::sweepNextBlock):
* heap/MarkedAllocator.cpp:
(JSC::MarkedAllocator::MarkedAllocator):
(JSC::MarkedAllocator::didConsumeFreeList):
(JSC::MarkedAllocator::tryAllocateWithoutCollecting):
(JSC::MarkedAllocator::tryAllocateIn):
(JSC::MarkedAllocator::allocateSlowCaseImpl):
(JSC::MarkedAllocator::stopAllocating):
(JSC::MarkedAllocator::prepareForAllocation):
(JSC::MarkedAllocator::resumeAllocating):
(JSC::MarkedAllocator::sweep):
(JSC::MarkedAllocator::setFreeList): Deleted.
* heap/MarkedAllocator.h:
(JSC::MarkedAllocator::freeList):
(JSC::MarkedAllocator::isFreeListedCell): Deleted.
* heap/MarkedAllocatorInlines.h:
(JSC::MarkedAllocator::isFreeListedCell):
(JSC::MarkedAllocator::tryAllocate):
(JSC::MarkedAllocator::allocate):
* heap/MarkedBlock.cpp:
(JSC::MarkedBlock::Handle::stopAllocating):
(JSC::MarkedBlock::Handle::lastChanceToFinalize):
(JSC::MarkedBlock::Handle::resumeAllocating):
(JSC::MarkedBlock::Handle::zap):
(JSC::MarkedBlock::Handle::sweep):
(JSC::MarkedBlock::Handle::isFreeListedCell):
(JSC::MarkedBlock::Handle::forEachFreeCell): Deleted.
* heap/MarkedBlock.h:
* heap/MarkedBlockInlines.h:
(JSC::MarkedBlock::Handle::specializedSweep):
(JSC::MarkedBlock::Handle::finishSweepKnowingSubspace):
(JSC::MarkedBlock::Handle::isFreeListedCell): Deleted.
* heap/Subspace.cpp:
(JSC::Subspace::finishSweep):
* heap/Subspace.h:
* jit/AssemblyHelpers.h:
(JSC::AssemblyHelpers::emitAllocateWithNonNullAllocator):
* runtime/JSDestructibleObjectSubspace.cpp:
(JSC::JSDestructibleObjectSubspace::finishSweep):
* runtime/JSDestructibleObjectSubspace.h:
* runtime/JSSegmentedVariableObjectSubspace.cpp:
(JSC::JSSegmentedVariableObjectSubspace::finishSweep):
* runtime/JSSegmentedVariableObjectSubspace.h:
* runtime/JSStringSubspace.cpp:
(JSC::JSStringSubspace::finishSweep):
* runtime/JSStringSubspace.h:
* wasm/js/JSWebAssemblyCodeBlockSubspace.cpp:
(JSC::JSWebAssemblyCodeBlockSubspace::finishSweep):
* wasm/js/JSWebAssemblyCodeBlockSubspace.h:

git-svn-id: https://svn.webkit.org/repository/webkit/trunk@217711 268f45cc-cd09-0410-ab3c-d52691b4dbfc
28 files changed:
Source/JavaScriptCore/ChangeLog
Source/JavaScriptCore/JavaScriptCore.xcodeproj/project.pbxproj
Source/JavaScriptCore/assembler/MacroAssembler.h
Source/JavaScriptCore/assembler/MacroAssemblerARM64.h
Source/JavaScriptCore/assembler/MacroAssemblerARMv7.h
Source/JavaScriptCore/heap/FreeList.cpp
Source/JavaScriptCore/heap/FreeList.h
Source/JavaScriptCore/heap/FreeListInlines.h [new file with mode: 0644]
Source/JavaScriptCore/heap/IncrementalSweeper.cpp
Source/JavaScriptCore/heap/MarkedAllocator.cpp
Source/JavaScriptCore/heap/MarkedAllocator.h
Source/JavaScriptCore/heap/MarkedAllocatorInlines.h
Source/JavaScriptCore/heap/MarkedBlock.cpp
Source/JavaScriptCore/heap/MarkedBlock.h
Source/JavaScriptCore/heap/MarkedBlockInlines.h
Source/JavaScriptCore/heap/Subspace.cpp
Source/JavaScriptCore/heap/Subspace.h
Source/JavaScriptCore/heap/SubspaceInlines.h
Source/JavaScriptCore/jit/AssemblyHelpers.h
Source/JavaScriptCore/runtime/JSDestructibleObjectSubspace.cpp
Source/JavaScriptCore/runtime/JSDestructibleObjectSubspace.h
Source/JavaScriptCore/runtime/JSSegmentedVariableObjectSubspace.cpp
Source/JavaScriptCore/runtime/JSSegmentedVariableObjectSubspace.h
Source/JavaScriptCore/runtime/JSStringSubspace.cpp
Source/JavaScriptCore/runtime/JSStringSubspace.h
Source/JavaScriptCore/runtime/Options.h
Source/JavaScriptCore/wasm/js/JSWebAssemblyCodeBlockSubspace.cpp
Source/JavaScriptCore/wasm/js/JSWebAssemblyCodeBlockSubspace.h