It should be possible to flag a cell for unconditional finalization
authorfpizlo@apple.com <fpizlo@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Wed, 13 Dec 2017 02:35:54 +0000 (02:35 +0000)
committerfpizlo@apple.com <fpizlo@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Wed, 13 Dec 2017 02:35:54 +0000 (02:35 +0000)
commit762287df4ef810683a735318422c077c72e90c90
treed46d91dc8c015a4ff1d9a07ea2e24ec21e4771b4
parent4716301c0e5353697969d24a4cf23bb1d30dd248
It should be possible to flag a cell for unconditional finalization
https://bugs.webkit.org/show_bug.cgi?id=180636

Reviewed by Saam Barati.

Source/JavaScriptCore:

UnconditionalFinalizers were annoying - you had to allocate them and you had to manage a
global linked list - but they had some nice properties:

- You only did the hardest work (creating the UnconditionalFinalizer) on first GC where you
  survived and needed it.
    -> Just needing it wasn't enough.
    -> Just surviving wasn't enough.

The new API based on IsoSubspaces meant that just surviving was enough to cause unconditional
finalizer logic to be invoked. I think that's not great. InferredType got around this by
making InferredStructure a cell, but this was a gross hack. For one, it meant that
InferredStructure would survive during the GC in which its finalizer obviated the need for its
existence. It's not really an idiom I want us to repeat because it sounds like the sort of
thing that turns out to be subtly broken.

We really need to have a way of indicating when you have entered into the state that requires
your unconditional finalizer to be invoked. Basically, we want to be able to track the set of
objects that need unconditional finalizers. Only the subset of that set that overlaps with the
set of marked objects needs to be accurate. The easiest way to do this is a hierarchy of
bitvectors: one to say which MarkedBlocks have objects that have unconditional finalizers, and
another level to say which atoms within a MarkedBlock have unconditional finalizers.

This change introduces IsoCellSet, which couples itself to the MarkedAllocator of some
IsoSubspace to allow maintaining a set of objects (well, cells - you could do this with
auxiliaries) that belong to that IsoSubspace. It'll have undefined behavior if you try to
add/remove/contains an object that isn't in that IsoSubspace. For objects in that subspace,
you can add/remove/contains and forEachMarkedCell. The cost of each IsoCellSet is at worst
about 0.8% increase in size to every object in the subspace that the set is attached to. So,
it makes sense to have a handful per subspace max. This change only needs one per subspace,
but you could imagine more if we do this for WeakReferenceHarvester.

To absolutely minimize the possibility that this incurs costs, the add/remove/contains
functions can be used from any thread so long as forEachMarkedCell isn't running. This means
that InferredType only needs to add itself to the set during visitChildren. Thus, it needs to
both survive and need it for the hardest work to take place. The work of adding does involve
a gnarly load chain that ends in a CAS: load block handle from block, load index, load
segment, load bitvector, load bit -> if not set, then CAS. That's five dependent loads!
However, it's perfect for running in parallel since the only write operations are to widely
dispersed cache lines that contain the bits underlying the set.

The best part is how forEachMarkedCell works. That skips blocks that don't have any objects
that need unconditional finalizers, and only touches the memory of marked objects that have
the unconditional finalizer bit set. It will walk those objects in roughly address order. I
previously found that this speeds up walking over a lot of objects when I made similar changes
for DOM GC (calling visitAdditionalChildren via forEachMarkedCell rather than by walking a
HashSet).

This change makes InferredStructure be a malloc object again, but now it's in an IsoHeap.

My expectation for this change is that it's perf-neutral. Long-term, it gives us a path
forward for eliminating UnconditionalFinalizer and WeakReferenceHarvester while using
IsoSubspace in more places.

* JavaScriptCore.xcodeproj/project.pbxproj:
* Sources.txt:
* heap/AtomIndices.h: Added.
(JSC::AtomIndices::AtomIndices):
* heap/Heap.cpp:
(JSC::Heap::finalizeUnconditionalFinalizers):
* heap/Heap.h:
* heap/IsoCellSet.cpp: Added.
(JSC::IsoCellSet::IsoCellSet):
(JSC::IsoCellSet::~IsoCellSet):
(JSC::IsoCellSet::addSlow):
(JSC::IsoCellSet::didResizeBits):
(JSC::IsoCellSet::didRemoveBlock):
(JSC::IsoCellSet::sweepToFreeList):
* heap/IsoCellSet.h: Added.
* heap/IsoCellSetInlines.h: Added.
(JSC::IsoCellSet::add):
(JSC::IsoCellSet::remove):
(JSC::IsoCellSet::contains const):
(JSC::IsoCellSet::forEachMarkedCell):
* heap/IsoSubspace.cpp:
(JSC::IsoSubspace::didResizeBits):
(JSC::IsoSubspace::didRemoveBlock):
(JSC::IsoSubspace::didBeginSweepingToFreeList):
* heap/IsoSubspace.h:
* heap/MarkedAllocator.cpp:
(JSC::MarkedAllocator::addBlock):
(JSC::MarkedAllocator::removeBlock):
* heap/MarkedAllocator.h:
* heap/MarkedAllocatorInlines.h:
* heap/MarkedBlock.cpp:
(JSC::MarkedBlock::Handle::sweep):
(JSC::MarkedBlock::Handle::isEmpty): Deleted.
* heap/MarkedBlock.h:
(JSC::MarkedBlock::marks const):
(JSC::MarkedBlock::Handle::newlyAllocated const):
* heap/MarkedBlockInlines.h:
(JSC::MarkedBlock::Handle::isAllocated):
(JSC::MarkedBlock::Handle::isEmpty):
(JSC::MarkedBlock::Handle::emptyMode):
(JSC::MarkedBlock::Handle::forEachMarkedCell):
* heap/Subspace.cpp:
(JSC::Subspace::didResizeBits):
(JSC::Subspace::didRemoveBlock):
(JSC::Subspace::didBeginSweepingToFreeList):
* heap/Subspace.h:
* heap/SubspaceInlines.h:
(JSC::Subspace::forEachMarkedCell):
* runtime/InferredStructure.cpp:
(JSC::InferredStructure::InferredStructure):
(JSC::InferredStructure::create): Deleted.
(JSC::InferredStructure::destroy): Deleted.
(JSC::InferredStructure::createStructure): Deleted.
(JSC::InferredStructure::visitChildren): Deleted.
(JSC::InferredStructure::finalizeUnconditionally): Deleted.
(JSC::InferredStructure::finishCreation): Deleted.
* runtime/InferredStructure.h:
* runtime/InferredStructureWatchpoint.cpp:
(JSC::InferredStructureWatchpoint::fireInternal):
* runtime/InferredType.cpp:
(JSC::InferredType::visitChildren):
(JSC::InferredType::willStoreValueSlow):
(JSC::InferredType::makeTopSlow):
(JSC::InferredType::set):
(JSC::InferredType::removeStructure):
(JSC::InferredType::finalizeUnconditionally):
* runtime/InferredType.h:
* runtime/VM.cpp:
(JSC::VM::VM):
* runtime/VM.h:

Source/WTF:

This adds ConcurrentVector, which is like SegmentedVector, but wastes some space to allow
resizing to proceed concurrently to access. It's not possible to resize concurrently to
resizing, concurrent read/writes aren't protected from racing if they access the same element,
and who knows what you'll get if you iterate up to size() while someone else append()s. The
key insight is to stash all prior copies of the spine, so that nobody crashes trying to access
a stale spine.

I'm going to want to do the same thing for FastBitVector, by creating a segmented WordOwner
class. That would require repeating the dance of having a spine that can resize while stashing
old versions. So, the spine resizing logic is abstracted behind ConcurrentBuffer. You could
use that as a kind of "concurrent vector" for immutable data. That's how ConcurrentVector uses
it: it's an immutable array of segment pointers.

* WTF.xcodeproj/project.pbxproj:
* wtf/ConcurrentBuffer.h: Added.
(WTF::ConcurrentBuffer::ConcurrentBuffer):
(WTF::ConcurrentBuffer::~ConcurrentBuffer):
(WTF::ConcurrentBuffer::growExact):
(WTF::ConcurrentBuffer::grow):
(WTF::ConcurrentBuffer::array const):
(WTF::ConcurrentBuffer::operator[]):
(WTF::ConcurrentBuffer::operator[] const):
(WTF::ConcurrentBuffer::createArray):
* wtf/ConcurrentVector.h: Added.
(WTF::ConcurrentVectorIterator::~ConcurrentVectorIterator):
(WTF::ConcurrentVectorIterator::operator* const):
(WTF::ConcurrentVectorIterator::operator-> const):
(WTF::ConcurrentVectorIterator::operator++):
(WTF::ConcurrentVectorIterator::operator== const):
(WTF::ConcurrentVectorIterator::operator!= const):
(WTF::ConcurrentVectorIterator::operator=):
(WTF::ConcurrentVectorIterator::ConcurrentVectorIterator):
(WTF::ConcurrentVector::~ConcurrentVector):
(WTF::ConcurrentVector::size const):
(WTF::ConcurrentVector::isEmpty const):
(WTF::ConcurrentVector::at):
(WTF::ConcurrentVector::at const):
(WTF::ConcurrentVector::operator[]):
(WTF::ConcurrentVector::operator[] const):
(WTF::ConcurrentVector::first):
(WTF::ConcurrentVector::first const):
(WTF::ConcurrentVector::last):
(WTF::ConcurrentVector::last const):
(WTF::ConcurrentVector::takeLast):
(WTF::ConcurrentVector::append):
(WTF::ConcurrentVector::alloc):
(WTF::ConcurrentVector::removeLast):
(WTF::ConcurrentVector::grow):
(WTF::ConcurrentVector::begin):
(WTF::ConcurrentVector::end):
(WTF::ConcurrentVector::segmentExistsFor):
(WTF::ConcurrentVector::segmentFor):
(WTF::ConcurrentVector::subscriptFor):
(WTF::ConcurrentVector::ensureSegmentsFor):
(WTF::ConcurrentVector::ensureSegment):
(WTF::ConcurrentVector::allocateSegment):

git-svn-id: https://svn.webkit.org/repository/webkit/trunk@225831 268f45cc-cd09-0410-ab3c-d52691b4dbfc
34 files changed:
Source/JavaScriptCore/ChangeLog
Source/JavaScriptCore/JavaScriptCore.xcodeproj/project.pbxproj
Source/JavaScriptCore/Sources.txt
Source/JavaScriptCore/heap/AtomIndices.h [new file with mode: 0644]
Source/JavaScriptCore/heap/Heap.cpp
Source/JavaScriptCore/heap/Heap.h
Source/JavaScriptCore/heap/IsoCellSet.cpp [new file with mode: 0644]
Source/JavaScriptCore/heap/IsoCellSet.h [new file with mode: 0644]
Source/JavaScriptCore/heap/IsoCellSetInlines.h [new file with mode: 0644]
Source/JavaScriptCore/heap/IsoSubspace.cpp
Source/JavaScriptCore/heap/IsoSubspace.h
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/runtime/InferredStructure.cpp
Source/JavaScriptCore/runtime/InferredStructure.h
Source/JavaScriptCore/runtime/InferredStructureWatchpoint.cpp
Source/JavaScriptCore/runtime/InferredType.cpp
Source/JavaScriptCore/runtime/InferredType.h
Source/JavaScriptCore/runtime/InferredTypeInlines.h [new file with mode: 0644]
Source/JavaScriptCore/runtime/VM.cpp
Source/JavaScriptCore/runtime/VM.h
Source/WTF/ChangeLog
Source/WTF/WTF.xcodeproj/project.pbxproj
Source/WTF/wtf/Bitmap.h
Source/WTF/wtf/CMakeLists.txt
Source/WTF/wtf/ConcurrentBuffer.h [new file with mode: 0644]
Source/WTF/wtf/ConcurrentVector.h [new file with mode: 0644]