Index: third_party/WebKit/Source/platform/heap/HeapCompact.cpp |
diff --git a/third_party/WebKit/Source/platform/heap/HeapCompact.cpp b/third_party/WebKit/Source/platform/heap/HeapCompact.cpp |
new file mode 100644 |
index 0000000000000000000000000000000000000000..c33b56f5b05adbf0fecdf20445684d7da524fdf2 |
--- /dev/null |
+++ b/third_party/WebKit/Source/platform/heap/HeapCompact.cpp |
@@ -0,0 +1,542 @@ |
+// Copyright 2016 Opera Software AS. All rights reserved. |
+// Use of this source code is governed by a BSD-style license that can be |
+// found in the LICENSE file. |
+ |
+#include "platform/heap/HeapCompact.h" |
+ |
+#include "platform/RuntimeEnabledFeatures.h" |
+#include "platform/heap/Heap.h" |
+#include "platform/heap/SparseHeapBitmap.h" |
+#include "wtf/CurrentTime.h" |
+#include "wtf/HashMap.h" |
+#include "wtf/HashSet.h" |
+#include "wtf/Vector.h" |
+ |
+namespace blink { |
+ |
+bool HeapCompact::s_forceCompactionGC = false; |
+ |
+// The real worker behind heap compaction, recording references to movable |
+// objects ("slots".) When the objects end up being compacted and moved, |
+// relocate() will adjust the slots to point to the new location of the |
+// object along with handling fixups for interior pointers. |
+// |
+// The "fixups" object is created and maintained for the lifetime of one |
+// heap compaction-enhanced GC. |
+class HeapCompact::MovableObjectFixups final { |
+ public: |
+ static std::unique_ptr<MovableObjectFixups> create() { |
+ return std::unique_ptr<MovableObjectFixups>(new MovableObjectFixups); |
+ } |
+ |
+ ~MovableObjectFixups() {} |
+ |
+ void addCompactablePage(BasePage* p) { |
+ // Add all pages belonging to arena to the set of relocatable pages. |
+ m_relocatablePages.add(p); |
+ } |
+ |
+ void add(MovableReference* slot) { |
+ MovableReference reference = *slot; |
+ BasePage* refPage = pageFromObject(reference); |
+ // Nothing to compact on a large object's page. |
+ if (refPage->isLargeObjectPage()) |
+ return; |
+ |
+#if DCHECK_IS_ON() |
+ auto it = m_fixups.find(reference); |
+ DCHECK(it == m_fixups.end() || it->value == slot); |
+#endif |
+ Address slotAddress = reinterpret_cast<Address>(slot); |
+ BasePage* slotPage = reinterpret_cast<BasePage*>( |
+ blinkPageAddress(slotAddress) + blinkGuardPageSize); |
+ if (m_relocatablePages.contains(slotPage)) { |
haraken
2016/11/30 06:29:53
Does the interior pointer problem happen only in L
sof
2016/11/30 06:52:43
Interior pointers can happen in a number of places
haraken
2016/11/30 07:09:49
I think I'm failing at understanding the problem :
sof
2016/11/30 07:26:38
Consider HeapHashMap<int, HeapVector<Member<someth
haraken
2016/11/30 08:51:19
But no matter what order the backing store is trac
sof
2016/11/30 09:22:14
Yes, but where are the relocatable slots - have th
|
+ // Slot resides on a compactable heap's page. |
+ // => It is an interior slot (interior to some other backing store.) |
+ // Record it as an interior slot, which entails: |
+ // |
+ // - Storing it in the interior map, which maps the slot to |
+ // its (eventual) location. Initially nullptr. |
+ // - Mark it as being interior pointer within the page's |
+ // "interior" bitmap. This bitmap is used when moving a backing |
+ // store, quickly/ier checking if interior slots will have to |
+ // be redirected. |
+ |
+ // Large object pages aren't compactable by definition, so shouldn't |
+ // encounter any here. |
+ DCHECK(!slotPage->isLargeObjectPage()); |
+ if (HeapCompact::isCompactableArena(slotPage->arena()->arenaIndex())) |
+ addInteriorFixup(slotAddress, slot); |
+ } |
+ m_fixups.add(reference, slot); |
+ } |
+ |
+ void addFixupCallback(MovableReference reference, |
+ MovingObjectCallback callback, |
+ void* callbackData) { |
+ DCHECK(!m_fixupCallbacks.contains(reference)); |
+ m_fixupCallbacks.add(reference, std::pair<void*, MovingObjectCallback>( |
+ callbackData, callback)); |
+ } |
+ |
+ size_t size() const { return m_fixups.size(); } |
+ |
+ void relocateInteriorFixups(Address from, Address to, size_t size) { |
+ SparseHeapBitmap* range = m_interiors->hasRange(from, size); |
+ if (LIKELY(!range)) |
+ return; |
+ |
+ // Scan through the payload, looking for interior pointer slots |
+ // to adjust. If the backing store of such an interior slot hasn't |
+ // been moved already, update the slot -> real location mapping. |
+ // When the backing store is eventually moved, it'll use that location. |
+ // |
+ for (size_t i = 0; i < size; i += sizeof(void*)) { |
+ if (!range->isSet(from + i)) |
+ continue; |
+ MovableReference* fromRef = reinterpret_cast<MovableReference*>(from + i); |
+ auto it = m_interiorFixups.find(fromRef); |
+ if (it == m_interiorFixups.end()) |
+ continue; |
+ |
+ // TODO: with the right sparse bitmap representation, it could be possible |
+ // to quickly determine if we've now stepped past the last address |
+ // that needed fixup in [address, address + size). Breaking out of this |
+ // loop might be worth doing for hash table backing stores with a very |
+ // low load factor. But interior fixups are rare. |
+ |
+ // If |slot|'s mapping is set, then the slot has been adjusted already. |
+ if (it->value) |
+ continue; |
+ LOG_HEAP_COMPACTION("Range interior fixup: %p %p %p\n", from + i, |
+ it->value, to + i); |
+ Address fixup = to + i; |
+ // Fill in the relocated location of the original slot at |from + i|; |
+ // when the backing store corresponding to |from + i| is eventually |
+ // moved/compacted, it'll update |to + i| with a pointer to the |
+ // moved backing store. |
+ m_interiorFixups.set(fromRef, fixup); |
+ } |
+ } |
+ |
+ void relocate(Address from, Address to) { |
+ auto it = m_fixups.find(from); |
+ DCHECK(it != m_fixups.end()); |
+ MovableReference* slot = reinterpret_cast<MovableReference*>(it->value); |
+ auto interior = m_interiorFixups.find(slot); |
+ if (interior != m_interiorFixups.end()) { |
+ MovableReference* slotLocation = |
+ reinterpret_cast<MovableReference*>(interior->value); |
+ if (!slotLocation) { |
+ m_interiorFixups.set(slot, to); |
+ } else { |
+ LOG_HEAP_COMPACTION("Redirected slot: %p => %p\n", slot, slotLocation); |
+ slot = slotLocation; |
+ } |
+ } |
+ // If the slot has subsequently been updated, a prefinalizer or |
+ // a destructor having mutated and expanded/shrunk the collection, |
+ // do not update and relocate the slot -- |from| is no longer valid |
+ // and referenced. |
+ // |
+ // The slot's contents may also have been cleared during weak processing; |
+ // no work to be done in that case either. |
+ if (UNLIKELY(*slot != from)) { |
+ LOG_HEAP_COMPACTION( |
+ "No relocation: slot = %p, *slot = %p, from = %p, to = %p\n", slot, |
+ *slot, from, to); |
+ return; |
+ } |
+ *slot = to; |
+ |
+ size_t size = 0; |
+ auto callback = m_fixupCallbacks.find(from); |
+ if (UNLIKELY(callback != m_fixupCallbacks.end())) { |
+ size = HeapObjectHeader::fromPayload(to)->payloadSize(); |
+ callback->value.second(callback->value.first, from, to, size); |
+ } |
+ |
+ if (LIKELY(!m_interiors)) |
+ return; |
+ |
+ if (!size) |
+ size = HeapObjectHeader::fromPayload(to)->payloadSize(); |
+ relocateInteriorFixups(from, to, size); |
+ } |
+ |
+ void addInteriorFixup(Address interior, MovableReference* slot) { |
+ auto it = m_interiorFixups.find(slot); |
+ // Ephemeron fixpoint iterations may cause repeated |
+ // registrations. |
+ DCHECK(it == m_interiorFixups.end() || !it->value); |
+ if (UNLIKELY(it != m_interiorFixups.end() && !it->value)) |
+ return; |
+ m_interiorFixups.add(slot, nullptr); |
+ addInteriorMapping(interior); |
+ } |
+ |
+ void addInteriorMapping(Address interior) { |
+ LOG_HEAP_COMPACTION("Interior: %p\n", interior); |
+ if (!m_interiors) { |
+ m_interiors = SparseHeapBitmap::create(interior); |
+ return; |
+ } |
+ m_interiors->add(interior); |
+ } |
+ |
+ void addRelocation(MovableReference* slot) { |
+ MovableReference reference = *slot; |
+ if (!m_fixups.contains(reference)) { |
+ // Record the interior pointer. |
+ addInteriorFixup(reinterpret_cast<Address>(reference), slot); |
+ } |
+ |
+ BasePage* heapPage = pageFromObject(reference); |
+ DCHECK(heapPage); |
+ DCHECK(!heapPage->isLargeObjectPage()); |
+ // For now, the heap objects we're adding relocations for are assumed |
+ // to be residing in a compactable heap. There's no reason why it must be |
+ // so, just a sanity checking assert while phasing in this extra set of |
+ // relocations. |
+ DCHECK(m_relocatablePages.contains(heapPage)); |
+ |
+ NormalPage* normalPage = static_cast<NormalPage*>(heapPage); |
+ auto perHeap = m_externalRelocations.find(normalPage->arenaForNormalPage()); |
+ if (perHeap == m_externalRelocations.end()) { |
+ Vector<MovableReference*> relocations; |
+ relocations.append(slot); |
+ ExternalRelocations table; |
+ table.add(*slot, relocations); |
+ m_externalRelocations.add(normalPage->arenaForNormalPage(), table); |
+ return; |
+ } |
+ auto entry = perHeap->value.find(*slot); |
+ if (entry == perHeap->value.end()) { |
+ Vector<MovableReference*> relocations; |
+ relocations.append(slot); |
+ perHeap->value.add(*slot, relocations); |
+ return; |
+ } |
+ entry->value.append(slot); |
+ } |
+ |
+ void fixupExternalRelocations(NormalPageArena* arena) { |
+ auto perHeap = m_externalRelocations.find(arena); |
+ if (LIKELY(perHeap == m_externalRelocations.end())) |
+ return; |
+ for (const auto& entry : perHeap->value) { |
+ MovableReference heapObject = entry.key; |
+ // |heapObject| will either be in |m_fixups| or have been recorded as |
+ // an internal fixup. |
+ auto heapEntry = m_fixups.find(heapObject); |
+ if (heapEntry != m_fixups.end()) { |
+ for (auto slot : entry.value) |
+ *slot = reinterpret_cast<MovableReference>(heapEntry->value); |
+ continue; |
+ } |
+ // The movement of the containing object will have moved the |
+ // interior slot. |
+ auto it = m_interiorFixups.find( |
+ reinterpret_cast<MovableReference*>(heapObject)); |
+ DCHECK(it != m_interiorFixups.end()); |
+ for (auto slot : entry.value) |
+ *slot = reinterpret_cast<MovableReference>(it->value); |
+ } |
+ } |
+ |
+#if DEBUG_HEAP_COMPACTION |
+ void dumpDebugStats() { |
+ LOG_HEAP_COMPACTION( |
+ "Fixups: pages=%u objects=%u callbacks=%u interior-size=%zu" |
+ " interiors-f=%u externals=%u\n", |
+ m_relocatablePages.size(), m_fixups.size(), m_fixupCallbacks.size(), |
+ m_interiors ? m_interiors->intervalCount() : 0, m_interiorFixups.size(), |
+ m_externalRelocations.size()); |
+ } |
+#endif |
+ |
+ private: |
+ MovableObjectFixups() {} |
+ |
+ // Tracking movable and updatable references. For now, we keep a |
+ // map which for each movable object, recording the slot that |
+ // points to it. Upon moving the object, that slot needs to be |
+ // updated. |
+ // |
+ // (TODO: consider in-place updating schemes.) |
+ HashMap<MovableReference, MovableReference*> m_fixups; |
+ |
+ // Map from movable reference to callbacks that need to be invoked |
+ // when the object moves. |
+ HashMap<MovableReference, std::pair<void*, MovingObjectCallback>> |
+ m_fixupCallbacks; |
+ |
+ // Slot => relocated slot/final location. |
+ HashMap<MovableReference*, Address> m_interiorFixups; |
+ |
+ // All pages that are being compacted. |
+ HashSet<BasePage*> m_relocatablePages; |
+ |
+ std::unique_ptr<SparseHeapBitmap> m_interiors; |
+ |
+ // Each heap/arena may have additional slots pointing into it, |
+ // which must be fixed up & relocated after compaction has happened. |
+ // |
+ // This is currently not needed for Blink, but functionality is kept |
+ // around to be able to support this should the need arise.. |
+ using ExternalRelocations = |
+ HashMap<MovableReference, Vector<MovableReference*>>; |
+ |
+ HashMap<NormalPageArena*, ExternalRelocations> m_externalRelocations; |
+}; |
+ |
+#if DEBUG_HEAP_COMPACTION |
+namespace { |
+ |
+const char* gcReasonString(BlinkGC::GCReason reason) { |
+ switch (reason) { |
+ case blink::BlinkGC::IdleGC: |
+ return "IdleGC"; |
+ case BlinkGC::PreciseGC: |
+ return "PreciseGC"; |
+ case BlinkGC::ConservativeGC: |
+ return "ConservativeGC"; |
+ case BlinkGC::ForcedGC: |
+ return "ForcedGC"; |
+ case BlinkGC::MemoryPressureGC: |
+ return "MemoryPressureGC"; |
+ case BlinkGC::PageNavigationGC: |
+ return "PageNavigationGC"; |
+ default: |
+ NOTREACHED(); |
+ } |
+ return "<Unknown>"; |
+} |
+ |
+} // namespace |
+#endif |
+ |
+HeapCompact::HeapCompact() |
+ : m_doCompact(false), |
+ m_gcCountSinceLastCompaction(0), |
+ m_threadCount(0), |
+ m_freeListAllocations(0), |
+ m_compactableHeaps(0u), |
+ m_freedPages(0), |
+ m_freedSize(0) |
+#if DEBUG_LOG_HEAP_COMPACTION_RUNNING_TIME |
+ , |
+ m_startCompaction(0), |
+ m_startCompactionTimeMS(0) |
+#endif |
+{ |
+} |
+ |
+HeapCompact::~HeapCompact() {} |
+ |
+HeapCompact::MovableObjectFixups& HeapCompact::fixups() { |
+ if (!m_fixups) |
+ m_fixups = MovableObjectFixups::create(); |
+ return *m_fixups; |
+} |
+ |
+// checkIfCompacting() is called when a GC is initiated |
+// (by ThreadState::collectGarbage()), checking if there's sufficient |
+// reason to do a compaction pass on completion of the GC (but before |
+// lazy sweeping), and that this can be safely done (i.e., it is not a |
+// conservative GC.) |
+// |
+// TODO(sof): reconsider what is an effective policy for when compaction |
+// is required. Both in terms of frequency and freelist residency. |
+void HeapCompact::checkIfCompacting(ThreadHeap* heap, |
+ Visitor* visitor, |
+ BlinkGC::GCType gcType, |
+ BlinkGC::GCReason reason) { |
+#if ENABLE_HEAP_COMPACTION |
+ if (!RuntimeEnabledFeatures::heapCompactionEnabled()) |
+ return; |
+ |
+ m_doCompact = false; |
+ LOG_HEAP_COMPACTION("check if compacting: gc=%s count=%zu free=%zu\n", |
+ gcReasonString(reason), m_gcCountSinceLastCompaction, |
+ m_freeListAllocations); |
+ m_gcCountSinceLastCompaction++; |
+ // It is only safe to compact during non-conservative GCs. |
+ if (reason != BlinkGC::IdleGC && reason != BlinkGC::PreciseGC && |
+ reason != BlinkGC::ForcedGC) |
+ return; |
+ |
+ // If any of the participating threads require a stack scan, |
+ // do not compact. |
+ // |
+ // Why? Should the stack contain an iterator pointing into its |
+ // associated backing store, its references wouldn't be |
+ // correctly relocated. |
+ for (ThreadState* state : heap->threads()) { |
+ if (state->stackState() == BlinkGC::HeapPointersOnStack) { |
+ return; |
+ } |
+ } |
+ |
+ m_freedPages = 0; |
+ m_freedSize = 0; |
+ |
+// Compaction enable rules: |
+// - It's been a while since the last time. |
+// - "Considerable" amount of heap bound up in freelist allocations. |
+// For now, use a fixed limit irrespective of heap size. |
+// |
+// As this isn't compacting all heaps/arenas, the cost of doing compaction |
+// isn't a worry as it will additionally only be done by idle GCs. |
+// TODO: add some form of compaction overhead estimate to the marking |
+// time estimate. |
+ |
+#if STRESS_TEST_HEAP_COMPACTION |
+ // Exercise the handling of object movement by compacting as |
+ // often as possible. |
+ m_doCompact = true; |
+#else |
+ m_doCompact = s_forceCompactionGC || |
+ (m_gcCountSinceLastCompaction > kCompactIntervalThreshold && |
+ m_freeListAllocations > kFreeThreshold); |
+#endif |
+ if (m_doCompact) { |
+ LOG_HEAP_COMPACTION("Compacting: free=%zu\n", m_freeListAllocations); |
+ m_threadCount = heap->threads().size(); |
+ visitor->setMarkCompactionMode(); |
+ m_fixups.reset(); |
+ m_gcCountSinceLastCompaction = 0; |
+ s_forceCompactionGC = false; |
+ } |
+#endif // ENABLE_HEAP_COMPACTION |
+} |
+ |
+void HeapCompact::registerMovingObjectReference(MovableReference* slot) { |
+ if (!m_doCompact) |
+ return; |
+ |
+ fixups().add(slot); |
+} |
+ |
+void HeapCompact::registerMovingObjectCallback(MovableReference reference, |
+ MovingObjectCallback callback, |
+ void* callbackData) { |
+ if (!m_doCompact) |
+ return; |
+ |
+ fixups().addFixupCallback(reference, callback, callbackData); |
+} |
+ |
+void HeapCompact::registerRelocation(MovableReference* slot) { |
+ if (!m_doCompact) |
+ return; |
+ |
+ if (!*slot) |
+ return; |
+ |
+ fixups().addRelocation(slot); |
+} |
+ |
+void HeapCompact::setHeapResidency( |
+ size_t liveSize, |
+ size_t freeSize, |
+ const Vector<std::pair<size_t, size_t>>& heapResidencies) { |
+#if DEBUG_HEAP_FREELIST |
+ LOG_HEAP_FREELIST("Heap residencies: {"); |
+ for (int i = 0; i < heapResidencies.size(); ++i) { |
+ LOG_HEAP_FREELIST("%d: [%zu, %zu], ", i, heapResidencies[i].first, |
+ heapResidencies[i].second); |
+ } |
+ LOG_HEAP_FREELIST("}\nFree + live size: %zu %zu\n", freeSize, liveSize); |
+#endif |
+ // Mark the sub heaps that are viable compaction candidates; |
+ // or, rather, not mark those that aren't. |
+ size_t subHeapCount = |
+ BlinkGC::HashTableArenaIndex - BlinkGC::Vector1ArenaIndex + 1; |
+ DCHECK(heapResidencies.size() == subHeapCount); |
+ m_compactableHeaps = 0; |
+ for (size_t i = 0; i < subHeapCount; ++i) { |
+ // TODO: be more discriminating and consider sub-heap |
+ // load factor, effectiveness of past compactions etc. |
+ if (heapResidencies[i].first == 0) { |
+ if (m_doCompact) { |
+ LOG_HEAP_COMPACTION("Not compacting heap: %zu\n", |
+ BlinkGC::Vector1ArenaIndex + i); |
+ } |
+ continue; |
+ } |
+ m_compactableHeaps |= (0x1u << (BlinkGC::Vector1ArenaIndex + i)); |
+ } |
+ if (m_doCompact) { |
+ // Reset the total freelist allocation if we're about to compact. |
+ // TODO(sof): re-record the actual (but very low) freelist size |
+ // after the compaction has completed. |
+ m_freeListAllocations = 0; |
+ return; |
+ } |
+ // TODO(sof): consider smoothing the reported sizes. |
+ m_freeListAllocations = freeSize; |
+} |
+ |
+void HeapCompact::finishedArenaCompaction(NormalPageArena* arena, |
+ size_t freedPages, |
+ size_t freedSize) { |
+ if (!m_doCompact) |
+ return; |
+ |
+ fixups().fixupExternalRelocations(arena); |
+ m_freedPages += freedPages; |
+ m_freedSize += freedSize; |
+} |
+ |
+void HeapCompact::movedObject(Address from, Address to) { |
+ DCHECK(m_fixups); |
+ m_fixups->relocate(from, to); |
+} |
+ |
+void HeapCompact::startCompacting(ThreadState*) { |
+#if DEBUG_LOG_HEAP_COMPACTION_RUNNING_TIME |
+ if (!atomicTestAndSetToOne(&m_startCompaction)) |
+ m_startCompactionTimeMS = WTF::currentTimeMS(); |
+#endif |
+} |
+ |
+void HeapCompact::finishedCompacting(ThreadState*) { |
+ if (!m_doCompact) |
+ return; |
+ |
+ // Final one clears out. |
+ if (!atomicDecrement(&m_threadCount)) { |
+#if DEBUG_HEAP_COMPACTION |
+ if (m_fixups) |
+ m_fixups->dumpDebugStats(); |
+#endif |
+ m_fixups.reset(); |
+ m_doCompact = false; |
+#if DEBUG_LOG_HEAP_COMPACTION_RUNNING_TIME |
+ double end = WTF::currentTimeMS(); |
+ LOG_HEAP_COMPACTION_INTERNAL( |
+ "Compaction stats: time=%gms, pages=%zu, size=%zu\n", |
+ end - m_startCompactionTimeMS, m_freedPages, m_freedSize); |
+ m_startCompaction = 0; |
+ m_startCompactionTimeMS = 0; |
+#else |
+ LOG_HEAP_COMPACTION("Compaction stats: freed pages=%zu size=%zu\n", |
+ m_freedPages, m_freedSize); |
+#endif |
+ } |
+} |
+ |
+void HeapCompact::addCompactablePage(BasePage* page) { |
+ if (!m_doCompact) |
+ return; |
+ fixups().addCompactablePage(page); |
+} |
+ |
+bool HeapCompact::scheduleCompactionGCForTesting(bool value) { |
+ bool current = s_forceCompactionGC; |
+ s_forceCompactionGC = value; |
+ return current; |
+} |
+ |
+} // namespace blink |