Attachment 368443 Details for Bug 186732 – Patch

[patch] Patch

bug-186732-20190428230443.patch (text/plain), 10.63 KB, created by Yusuke Suzuki on 2019-04-28 23:04:44 PDT

(hide)

Description:

Filename:

MIME Type:

Creator: Yusuke Suzuki

Created: 2019-04-28 23:04:44 PDT

Size: 10.63 KB

patch

obsolete

>Subversion Revision: 244723
>diff --git a/Source/JavaScriptCore/ChangeLog b/Source/JavaScriptCore/ChangeLog
>index 28aeca460ca65580a9ae60e98de7e15fada6d41b..404c87ff85e1c039bdd0d259cf1b1912c021b3b8 100644
>--- a/Source/JavaScriptCore/ChangeLog
>+++ b/Source/JavaScriptCore/ChangeLog
>@@ -1,3 +1,37 @@
>+2019-04-28  Yusuke Suzuki  <ysuzuki@apple.com>
>+
>+        JITStubRoutineSet wastes 180KB of HashTable capacity on can.com
>+        https://bugs.webkit.org/show_bug.cgi?id=186732
>+
>+        Reviewed by NOBODY (OOPS!).
>+
>+        Our current mechanism of JITStubRoutineSet is too memory consuming. Basically we have HashMap<uintptr_t, StubRoutine*> and register
>+        each executable address by 16 byte to this entry. So if your StubRoutine has 128bytes, it just adds 8 entries to this hash table.
>+        In Gmail, we see ~2MB table size.
>+
>+        Instead, this patch uses Vector<pair<uintptr_t, StubRoutine*>> and performs binary search onto this sorted vector. Before conservative
>+        scanning, we sort this vector. And doing binary search with the sorted vector to find executing stub routines from the conservative roots.
>+        This vector includes uintptr_t startAddress to make binary searching fast.
>+
>+        Large amount of conservative scan should be filtered by range check, so I think binary search here is OK, but we can decide based on what the
>+        performance bots say.
>+
>+        * heap/Heap.cpp:
>+        (JSC::Heap::addCoreConstraints):
>+        * heap/JITStubRoutineSet.cpp:
>+        (JSC::JITStubRoutineSet::~JITStubRoutineSet):
>+        (JSC::JITStubRoutineSet::add):
>+        (JSC::JITStubRoutineSet::prepareForConservativeScan):
>+        (JSC::JITStubRoutineSet::clearMarks):
>+        (JSC::JITStubRoutineSet::markSlow):
>+        (JSC::JITStubRoutineSet::deleteUnmarkedJettisonedStubRoutines):
>+        (JSC::JITStubRoutineSet::traceMarkedStubRoutines):
>+        * heap/JITStubRoutineSet.h:
>+        (JSC::JITStubRoutineSet::mark):
>+        (JSC::JITStubRoutineSet::prepareForConservativeScan):
>+        (JSC::JITStubRoutineSet::size const): Deleted.
>+        (JSC::JITStubRoutineSet::at const): Deleted.
>+
> 2019-04-26  Keith Rollin  <krollin@apple.com>
> 
>         Enable new build rule for post-processing headers when using XCBuild
>diff --git a/Source/WTF/ChangeLog b/Source/WTF/ChangeLog
>index 475cdd28b74cf6c19251851e75de9c279aebd116..f271456694b79c5ecb6e7184c97f04492e13bc42 100644
>--- a/Source/WTF/ChangeLog
>+++ b/Source/WTF/ChangeLog
>@@ -1,3 +1,13 @@
>+2019-04-28  Yusuke Suzuki  <ysuzuki@apple.com>
>+
>+        JITStubRoutineSet wastes 180KB of HashTable capacity on can.com
>+        https://bugs.webkit.org/show_bug.cgi?id=186732
>+
>+        Reviewed by NOBODY (OOPS!).
>+
>+        * wtf/Range.h:
>+        (WTF::Range::contains const):
>+
> 2019-04-26  Don Olmstead  <don.olmstead@sony.com>
> 
>         Add WTF::findIgnoringASCIICaseWithoutLength to replace strcasestr
>diff --git a/Source/JavaScriptCore/heap/Heap.cpp b/Source/JavaScriptCore/heap/Heap.cpp
>index 4953ac259223f32a1a0ad6e96182ffbc16aaa522..8d92313977d332bbebe3dcd7cebbe6336fa6073f 100644
>--- a/Source/JavaScriptCore/heap/Heap.cpp
>+++ b/Source/JavaScriptCore/heap/Heap.cpp
>@@ -2687,6 +2687,7 @@ void Heap::addCoreConstraints()
>             
>             TimingScope preConvergenceTimingScope(*this, "Constraint: conservative scan");
>             m_objectSpace.prepareForConservativeScan();
>+            m_jitStubRoutines->prepareForConservativeScan();
> 
>             {
>                 ConservativeRoots conservativeRoots(*this);
>diff --git a/Source/JavaScriptCore/heap/JITStubRoutineSet.cpp b/Source/JavaScriptCore/heap/JITStubRoutineSet.cpp
>index ae80595326e8ca99badc5736a99f1c0c01474b87..d4859a17547c2ee5926cfb204a83da091d49d925 100644
>--- a/Source/JavaScriptCore/heap/JITStubRoutineSet.cpp
>+++ b/Source/JavaScriptCore/heap/JITStubRoutineSet.cpp
>@@ -37,9 +37,8 @@ namespace JSC {
> JITStubRoutineSet::JITStubRoutineSet() { }
> JITStubRoutineSet::~JITStubRoutineSet()
> {
>-    for (size_t i = m_listOfRoutines.size(); i--;) {
>-        GCAwareJITStubRoutine* routine = m_listOfRoutines[i];
>-        
>+    for (auto& entry : m_routines) {
>+        GCAwareJITStubRoutine* routine = entry.routine;
>         routine->m_mayBeExecuting = false;
>         
>         if (!routine->m_isJettisoned) {
>@@ -57,62 +56,84 @@ void JITStubRoutineSet::add(GCAwareJITStubRoutine* routine)
> {
>     ASSERT(!routine->m_isJettisoned);
>     
>-    m_listOfRoutines.append(routine);
>-    
>-    uintptr_t start = routine->startAddress();
>-    uintptr_t end = routine->endAddress();
>-    uintptr_t step = JITStubRoutine::addressStep();
>-    for (uintptr_t iter = start; iter < end; iter += step) {
>-        ASSERT(m_addressToRoutineMap.find(iter) == m_addressToRoutineMap.end());
>-        m_addressToRoutineMap.add(iter, routine);
>+    m_routines.append(Routine {
>+        routine->startAddress(),
>+        routine
>+    });
>+}
>+
>+void JITStubRoutineSet::prepareForConservativeScan()
>+{
>+    if (m_routines.isEmpty()) {
>+        m_range = Range<uintptr_t> { 0, 0 };
>+        return;
>     }
>+    std::sort(
>+        m_routines.begin(), m_routines.end(),
>+        [&] (const Routine& a, const Routine& b) {
>+            return a.startAddress < b.startAddress;
>+        });
>+    m_range = Range<uintptr_t> {
>+        m_routines.first().startAddress,
>+        m_routines.last().routine->endAddress()
>+    };
> }
> 
> void JITStubRoutineSet::clearMarks()
> {
>-    for (size_t i = m_listOfRoutines.size(); i--;)
>-        m_listOfRoutines[i]->m_mayBeExecuting = false;
>+    for (auto& entry : m_routines)
>+        entry.routine->m_mayBeExecuting = false;
> }
> 
> void JITStubRoutineSet::markSlow(uintptr_t address)
> {
>-    HashMap<uintptr_t, GCAwareJITStubRoutine*>::iterator iter =
>-        m_addressToRoutineMap.find(address & ~(JITStubRoutine::addressStep() - 1));
>-    
>-    if (iter == m_addressToRoutineMap.end())
>-        return;
>-    
>-    iter->value->m_mayBeExecuting = true;
>+    ASSERT(isJITPC(bitwise_cast<void*>(address)));
>+    ASSERT(!m_routines.isEmpty());
>+
>+    Routine* result = approximateBinarySearch<Routine>(
>+        m_routines.begin(), m_routines.size(), address,
>+        [] (const Routine* routine) -> uintptr_t { return routine->startAddress; });
>+    if (result) {
>+        auto markIfContained = [&] (const Routine& routine, uintptr_t address) {
>+            if (routine.startAddress <= address && address < routine.routine->endAddress()) {
>+                routine.routine->m_mayBeExecuting = true;
>+                return true;
>+            }
>+            return false;
>+        };
>+
>+        if (result > m_routines.begin()) {
>+            if (markIfContained(result[-1], address))
>+                return;
>+        }
>+        if (markIfContained(result[0], address))
>+            return;
>+        if (result + 1 < m_routines.end()) {
>+            if (markIfContained(result[1], address))
>+                return;
>+        }
>+    }
> }
> 
> void JITStubRoutineSet::deleteUnmarkedJettisonedStubRoutines()
> {
>-    for (size_t i = 0; i < m_listOfRoutines.size(); i++) {
>-        GCAwareJITStubRoutine* routine = m_listOfRoutines[i];
>-        if (!routine->m_isJettisoned || routine->m_mayBeExecuting)
>+    unsigned srcIndex = 0;
>+    unsigned dstIndex = srcIndex;
>+    while (srcIndex < m_routines.size()) {
>+        Routine routine = m_routines[srcIndex++];
>+        if (!routine.routine->m_isJettisoned || routine.routine->m_mayBeExecuting) {
>+            m_routines[dstIndex++] = routine;
>             continue;
>-        
>-        uintptr_t start = routine->startAddress();
>-        uintptr_t end = routine->endAddress();
>-        uintptr_t step = JITStubRoutine::addressStep();
>-        for (uintptr_t iter = start; iter < end; iter += step) {
>-            ASSERT(m_addressToRoutineMap.find(iter) != m_addressToRoutineMap.end());
>-            ASSERT(m_addressToRoutineMap.find(iter)->value == routine);
>-            m_addressToRoutineMap.remove(iter);
>         }
>-        
>-        routine->deleteFromGC();
>-        
>-        m_listOfRoutines[i] = m_listOfRoutines.last();
>-        m_listOfRoutines.removeLast();
>-        i--;
>+        routine.routine->deleteFromGC();
>     }
>+    m_routines.shrink(dstIndex);
> }
> 
> void JITStubRoutineSet::traceMarkedStubRoutines(SlotVisitor& visitor)
> {
>-    for (size_t i = m_listOfRoutines.size(); i--;) {
>-        GCAwareJITStubRoutine* routine = m_listOfRoutines[i];
>+    for (auto& entry : m_routines) {
>+        GCAwareJITStubRoutine* routine = entry.routine;
>         if (!routine->m_mayBeExecuting)
>             continue;
>         
>diff --git a/Source/JavaScriptCore/heap/JITStubRoutineSet.h b/Source/JavaScriptCore/heap/JITStubRoutineSet.h
>index 44a393fecbdad7d351b3b42d73830acfcbbb4722..4ecceb0e21286bbd01c3ce3c43a8ea7f5658781b 100644
>--- a/Source/JavaScriptCore/heap/JITStubRoutineSet.h
>+++ b/Source/JavaScriptCore/heap/JITStubRoutineSet.h
>@@ -28,6 +28,7 @@
> #include "JITStubRoutine.h"
> #include <wtf/FastMalloc.h>
> #include <wtf/HashMap.h>
>+#include <wtf/Range.h>
> #include <wtf/Vector.h>
> 
> namespace JSC {
>@@ -52,24 +53,26 @@ class JITStubRoutineSet {
>     void mark(void* candidateAddress)
>     {
>         uintptr_t address = removeCodePtrTag<uintptr_t>(candidateAddress);
>-        if (!JITStubRoutine::passesFilter(address))
>+        if (!m_range.contains(address))
>             return;
>-        
>         markSlow(address);
>     }
>+
>+    void prepareForConservativeScan();
>     
>     void deleteUnmarkedJettisonedStubRoutines();
>     
>     void traceMarkedStubRoutines(SlotVisitor&);
>     
>-    unsigned size() const { return m_listOfRoutines.size(); }
>-    GCAwareJITStubRoutine* at(unsigned i) const { return m_listOfRoutines[i]; }
>-    
> private:
>     void markSlow(uintptr_t address);
>     
>-    HashMap<uintptr_t, GCAwareJITStubRoutine*> m_addressToRoutineMap;
>-    Vector<GCAwareJITStubRoutine*> m_listOfRoutines;
>+    struct Routine {
>+        uintptr_t startAddress;
>+        GCAwareJITStubRoutine* routine;
>+    };
>+    Vector<Routine> m_routines;
>+    Range<uintptr_t> m_range { 0, 0 };
> };
> 
> #else // !ENABLE(JIT)
>@@ -85,6 +88,7 @@ class JITStubRoutineSet {
>     void add(GCAwareJITStubRoutine*) { }
>     void clearMarks() { }
>     void mark(void*) { }
>+    void prepareForConservativeScan() { }
>     void deleteUnmarkedJettisonedStubRoutines() { }
>     void traceMarkedStubRoutines(SlotVisitor&) { }
> };
>diff --git a/Source/WTF/wtf/Range.h b/Source/WTF/wtf/Range.h
>index deba7e29dde8f2e38a97d9dce2d63aa65d5fa038..23d0263b26945cf32ed3cded1e4e9b5ebab91388 100644
>--- a/Source/WTF/wtf/Range.h
>+++ b/Source/WTF/wtf/Range.h
>@@ -109,6 +109,11 @@ class Range {
>         return WTF::rangesOverlap(m_begin, m_end, other.m_begin, other.m_end);
>     }
> 
>+    bool contains(Type point) const
>+    {
>+        return m_begin <= point && point < m_end;
>+    }
>+
>     void dump(PrintStream& out) const
>     {
>         if (*this == Range()) {

Flags:

saam: review+

Actions: View | Formatted Diff | Diff

Attachments on bug 186732: 368393 | 368406 | 368408 | 368410 | 368411 | 368420 | 368421 | 368422 | 368443