[Content Extensions] Process NFAs individually to avoid having all NFAs live at the...
authorweinig@apple.com <weinig@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Wed, 29 Apr 2015 00:22:33 +0000 (00:22 +0000)
committerweinig@apple.com <weinig@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Wed, 29 Apr 2015 00:22:33 +0000 (00:22 +0000)
https://bugs.webkit.org/show_bug.cgi?id=144363

Reviewed by Alex Christensen.

Source/WebCore:

This brings dirty memory use when compiling our test content extension down from ~300MB to ~100MB.

* contentextensions/CombinedURLFilters.cpp:
(WebCore::ContentExtensions::CombinedURLFilters::processNFAs):
(WebCore::ContentExtensions::CombinedURLFilters::createNFAs): Deleted.
* contentextensions/CombinedURLFilters.h:
Replace function that creates a Vector of all the NFAs with one that allows incremental processing
as they are created.

* contentextensions/ContentExtensionCompiler.cpp:
(WebCore::ContentExtensions::addUniversalActionsToDFA):
Extract code to add universal actions into a helper, since we need to call it in two places now.

(WebCore::ContentExtensions::compileRuleList):
Adopt CombinedURLFilters::processNFAs. Now that we don't have a Vector of NFAs, we need to keep track
of whether or not any NFAs were processed and if we are currently processing the first NFA so we can
ensure that we have some bytecode generated event for empty rule sets, and that universal actions are
placed on the first DFA.

Tools:

* TestWebKitAPI/Tests/WebCore/ContentExtensions.cpp:
(TestWebKitAPI::createNFAs):
(TestWebKitAPI::TEST_F):
* TestWebKitAPI/Tests/WebCore/DFAMinimizer.cpp:
(TestWebKitAPI::countLiveNodes):
(TestWebKitAPI::createNFAs):
(TestWebKitAPI::buildDFAFromPatterns):
Update tests to use a hand rolled createNFAs function on top of CombinedURLFilters::processNFAs.

git-svn-id: https://svn.webkit.org/repository/webkit/trunk@183518 268f45cc-cd09-0410-ab3c-d52691b4dbfc

Source/WebCore/ChangeLog
Source/WebCore/contentextensions/CombinedURLFilters.cpp
Source/WebCore/contentextensions/CombinedURLFilters.h
Source/WebCore/contentextensions/ContentExtensionCompiler.cpp
Tools/ChangeLog
Tools/TestWebKitAPI/Tests/WebCore/ContentExtensions.cpp
Tools/TestWebKitAPI/Tests/WebCore/DFAMinimizer.cpp

index 62d4bde..68ab154 100644 (file)
@@ -1,3 +1,29 @@
+2015-04-28  Sam Weinig  <sam@webkit.org>
+
+        [Content Extensions] Process NFAs individually to avoid having all NFAs live at the same time
+        https://bugs.webkit.org/show_bug.cgi?id=144363
+
+        Reviewed by Alex Christensen.
+
+        This brings dirty memory use when compiling our test content extension down from ~300MB to ~100MB.
+
+        * contentextensions/CombinedURLFilters.cpp:
+        (WebCore::ContentExtensions::CombinedURLFilters::processNFAs):
+        (WebCore::ContentExtensions::CombinedURLFilters::createNFAs): Deleted.
+        * contentextensions/CombinedURLFilters.h:
+        Replace function that creates a Vector of all the NFAs with one that allows incremental processing
+        as they are created.
+
+        * contentextensions/ContentExtensionCompiler.cpp:
+        (WebCore::ContentExtensions::addUniversalActionsToDFA):
+        Extract code to add universal actions into a helper, since we need to call it in two places now.
+
+        (WebCore::ContentExtensions::compileRuleList):
+        Adopt CombinedURLFilters::processNFAs. Now that we don't have a Vector of NFAs, we need to keep track
+        of whether or not any NFAs were processed and if we are currently processing the first NFA so we can
+        ensure that we have some bytecode generated event for empty rule sets, and that universal actions are
+        placed on the first DFA.
+
 2015-04-28  Timothy Horton  <timothy_horton@apple.com>
 
         [TextIndicator] Yellow highlight takes too long to fade out on scroll
index 13e7760..479d3d7 100644 (file)
@@ -169,13 +169,11 @@ static void generateNFAForSubtree(NFA& nfa, unsigned rootId, const PrefixTreeVer
     }
 }
 
-Vector<NFA> CombinedURLFilters::createNFAs() const
+void CombinedURLFilters::processNFAs(std::function<void(NFA&&)> handler) const
 {
     Vector<ActiveSubtree> activeStack;
     activeStack.append(ActiveSubtree({ m_prefixTreeRoot.get(), m_prefixTreeRoot->edges.begin() }));
 
-    Vector<NFA> nfas;
-
     while (true) {
     ProcessSubtree:
         ActiveSubtree& activeSubtree = activeStack.last();
@@ -202,23 +200,24 @@ Vector<NFA> CombinedURLFilters::createNFAs() const
         }
 
         if (needToGenerate) {
-            nfas.append(NFA());
-            NFA& generatingNFA = nfas.last();
+            NFA nfa;
 
-            unsigned prefixEnd = generatingNFA.root();
+            unsigned prefixEnd = nfa.root();
 
             for (unsigned i = 0; i < activeStack.size() - 1; ++i) {
                 const Term& term = activeStack[i].iterator->first;
-                prefixEnd = term.generateGraph(generatingNFA, prefixEnd, activeStack[i].iterator->second->finalActions);
+                prefixEnd = term.generateGraph(nfa, prefixEnd, activeStack[i].iterator->second->finalActions);
             }
 
             for (const auto& edge : activeSubtree.vertex->edges) {
                 if (!edge.second->inVariableLengthPrefix) {
                     const Term& term = edge.first;
-                    unsigned newSubtreeStart = term.generateGraph(generatingNFA, prefixEnd, edge.second->finalActions);
-                    generateNFAForSubtree(generatingNFA, newSubtreeStart, *edge.second);
+                    unsigned newSubtreeStart = term.generateGraph(nfa, prefixEnd, edge.second->finalActions);
+                    generateNFAForSubtree(nfa, newSubtreeStart, *edge.second);
                 }
             }
+            
+            handler(WTF::move(nfa));
         }
 
         // We have processed all the subtrees of this level, pop the stack and move on to the next sibling.
@@ -227,8 +226,6 @@ Vector<NFA> CombinedURLFilters::createNFAs() const
             break;
         ++activeStack.last().iterator;
     }
-
-    return nfas;
 }
 
 } // namespace ContentExtensions
index 0f3ca7c..2b0847f 100644 (file)
@@ -42,9 +42,10 @@ class WEBCORE_EXPORT CombinedURLFilters {
 public:
     CombinedURLFilters();
     ~CombinedURLFilters();
+
     void addPattern(uint64_t patternId, const Vector<Term>& pattern);
 
-    Vector<NFA> createNFAs() const;
+    void processNFAs(std::function<void(NFA&&)> handler) const;
     void clear();
 
     size_t memoryUsed() const;
index df04038..060cef8 100644 (file)
@@ -119,6 +119,22 @@ static Vector<unsigned> serializeActions(const Vector<ContentExtensionRule>& rul
     return actionLocations;
 }
 
+typedef HashSet<uint64_t, DefaultHash<uint64_t>::Hash, WTF::UnsignedWithZeroKeyHashTraits<uint64_t>> UniversalActionLocationsSet;
+
+static void addUniversalActionsToDFA(DFA& dfa, const UniversalActionLocationsSet& universalActionLocations)
+{
+    if (universalActionLocations.isEmpty())
+        return;
+
+    unsigned actionsStart = dfa.actions.size();
+    dfa.actions.reserveCapacity(dfa.actions.size() + universalActionLocations.size());
+    for (uint64_t actionLocation : universalActionLocations)
+        dfa.actions.uncheckedAppend(actionLocation);
+    unsigned actionsEnd = dfa.actions.size();
+    unsigned actionsLength = actionsEnd - actionsStart;
+    RELEASE_ASSERT_WITH_MESSAGE(actionsLength < std::numeric_limits<uint16_t>::max(), "Too many uncombined actions that match everything");
+    dfa.nodes[dfa.root].setActions(actionsStart, static_cast<uint16_t>(actionsLength));
+}
 
 std::error_code compileRuleList(ContentExtensionCompilationClient& client, const String& ruleList)
 {
@@ -137,7 +153,7 @@ std::error_code compileRuleList(ContentExtensionCompilationClient& client, const
     LOG_LARGE_STRUCTURES(actions, actions.capacity() * sizeof(SerializedActionByte));
     actions.clear();
 
-    HashSet<uint64_t, DefaultHash<uint64_t>::Hash, WTF::UnsignedWithZeroKeyHashTraits<uint64_t>> universalActionLocations;
+    UniversalActionLocationsSet universalActionLocations;
 
     CombinedURLFilters combinedURLFilters;
     URLFilterParser urlFilterParser(combinedURLFilters);
@@ -175,40 +191,27 @@ std::error_code compileRuleList(ContentExtensionCompilationClient& client, const
     dataLogF("    Time spent partitioning the rules into groups: %f\n", (patternPartitioningEnd - patternPartitioningStart));
 #endif
 
-#if CONTENT_EXTENSIONS_PERFORMANCE_REPORTING
-    double nfaBuildTimeStart = monotonicallyIncreasingTime();
-#endif
-
-    Vector<NFA> nfas = combinedURLFilters.createNFAs();
     LOG_LARGE_STRUCTURES(combinedURLFilters, combinedURLFilters.memoryUsed());
-    combinedURLFilters.clear();
-    if (!nfas.size() && universalActionLocations.size())
-        nfas.append(NFA());
 
 #if CONTENT_EXTENSIONS_PERFORMANCE_REPORTING
-    double nfaBuildTimeEnd = monotonicallyIncreasingTime();
-    dataLogF("    Time spent building the NFAs: %f\n", (nfaBuildTimeEnd - nfaBuildTimeStart));
+    double totalNFAToByteCodeBuildTimeStart = monotonicallyIncreasingTime();
 #endif
 
+    Vector<DFABytecode> bytecode;
+    bool firstNFASeen = false;
+    combinedURLFilters.processNFAs([&](NFA&& nfa) {
 #if CONTENT_EXTENSIONS_STATE_MACHINE_DEBUGGING
-    for (size_t i = 0; i < nfas.size(); ++i) {
-        WTFLogAlways("NFA %zu", i);
-        const NFA& nfa = nfas[i];
         nfa.debugPrintDot();
-    }
 #endif
 
-#if CONTENT_EXTENSIONS_PERFORMANCE_REPORTING
-    double totalNFAToByteCodeBuildTimeStart = monotonicallyIncreasingTime();
-#endif
+        LOG_LARGE_STRUCTURES(nfa, nfa.memoryUsed());
 
-    Vector<DFABytecode> bytecode;
-    for (size_t i = 0; i < nfas.size(); ++i) {
 #if CONTENT_EXTENSIONS_PERFORMANCE_REPORTING
         double dfaBuildTimeStart = monotonicallyIncreasingTime();
 #endif
-        DFA dfa = NFAToDFA::convert(nfas[i]);
+        DFA dfa = NFAToDFA::convert(nfa);
         LOG_LARGE_STRUCTURES(dfa, dfa.memoryUsed());
+
 #if CONTENT_EXTENSIONS_PERFORMANCE_REPORTING
         double dfaBuildTimeEnd = monotonicallyIncreasingTime();
         dataLogF("    Time spent building the DFA %zu: %f\n", i, (dfaBuildTimeEnd - dfaBuildTimeStart));
@@ -228,20 +231,34 @@ std::error_code compileRuleList(ContentExtensionCompilationClient& client, const
         dfa.debugPrintDot();
 #endif
         ASSERT_WITH_MESSAGE(!dfa.nodes[dfa.root].hasActions(), "All actions on the DFA root should come from regular expressions that match everything.");
-        if (!i) {
+
+        if (!firstNFASeen) {
             // Put all the universal actions on the first DFA.
-            unsigned actionsStart = dfa.actions.size();
-            dfa.actions.reserveCapacity(dfa.actions.size() + universalActionLocations.size());
-            for (uint64_t actionLocation : universalActionLocations)
-                dfa.actions.uncheckedAppend(actionLocation);
-            unsigned actionsEnd = dfa.actions.size();
-            unsigned actionsLength = actionsEnd - actionsStart;
-            RELEASE_ASSERT_WITH_MESSAGE(actionsLength < std::numeric_limits<uint16_t>::max(), "Too many uncombined actions that match everything");
-            dfa.nodes[dfa.root].setActions(actionsStart, static_cast<uint16_t>(actionsLength));
+            addUniversalActionsToDFA(dfa, universalActionLocations);
         }
+
         DFABytecodeCompiler compiler(dfa, bytecode);
         compiler.compile();
+
+        firstNFASeen = true;
+    });
+
+    if (!firstNFASeen) {
+        // Our bytecode interpreter expects to have at least one DFA, so if we haven't seen any
+        // create a dummy one and add any universal actions.
+
+        NFA dummyNFA;
+        DFA dummyDFA = NFAToDFA::convert(dummyNFA);
+
+        addUniversalActionsToDFA(dummyDFA, universalActionLocations);
+
+        DFABytecodeCompiler compiler(dummyDFA, bytecode);
+        compiler.compile();
     }
+
+    // FIXME: combinedURLFilters should be cleared incrementally as it is processing NFAs. 
+    combinedURLFilters.clear();
+
     LOG_LARGE_STRUCTURES(universalActionLocations, universalActionLocations.capacity() * sizeof(unsigned));
     universalActionLocations.clear();
 
@@ -251,11 +268,6 @@ std::error_code compileRuleList(ContentExtensionCompilationClient& client, const
     dataLogF("    Bytecode size %zu\n", bytecode.size());
     dataLogF("    DFA count %zu\n", nfas.size());
 #endif
-    size_t nfaMemoryUsed = 0;
-    for (const NFA& nfa : nfas)
-        nfaMemoryUsed += sizeof(NFA) + nfa.memoryUsed();
-    LOG_LARGE_STRUCTURES(nfas, nfaMemoryUsed);
-    nfas.clear();
 
     LOG_LARGE_STRUCTURES(bytecode, bytecode.capacity() * sizeof(uint8_t));
     client.writeBytecode(WTF::move(bytecode));
index a17b599..02eced9 100644 (file)
@@ -1,3 +1,19 @@
+2015-04-28  Sam Weinig  <sam@webkit.org>
+
+        [Content Extensions] Process NFAs individually to avoid having all NFAs live at the same time
+        https://bugs.webkit.org/show_bug.cgi?id=144363
+
+        Reviewed by Alex Christensen.
+
+        * TestWebKitAPI/Tests/WebCore/ContentExtensions.cpp:
+        (TestWebKitAPI::createNFAs):
+        (TestWebKitAPI::TEST_F):
+        * TestWebKitAPI/Tests/WebCore/DFAMinimizer.cpp:
+        (TestWebKitAPI::countLiveNodes):
+        (TestWebKitAPI::createNFAs):
+        (TestWebKitAPI::buildDFAFromPatterns):
+        Update tests to use a hand rolled createNFAs function on top of CombinedURLFilters::processNFAs.
+
 2015-04-28  Michael Catanzaro  <mcatanzaro@igalia.com>
 
         Fully replace ENABLE_LLINT_C_LOOP with ENABLE_JIT
index 620d91a..983cb64 100644 (file)
@@ -163,6 +163,17 @@ ContentExtensions::ContentExtensionsBackend makeBackend(const char* json)
     return backend;
 }
 
+static Vector<ContentExtensions::NFA> createNFAs(ContentExtensions::CombinedURLFilters& combinedURLFilters)
+{
+    Vector<ContentExtensions::NFA> nfas;
+
+    combinedURLFilters.processNFAs([&](ContentExtensions::NFA&& nfa) {
+        nfas.append(WTF::move(nfa));
+    });
+
+    return nfas;
+}
+
 TEST_F(ContentExtensionTest, Basic)
 {
     auto backend = makeBackend("[{\"action\":{\"type\":\"block\"},\"trigger\":{\"url-filter\":\"webkit.org\"}}]");
@@ -599,7 +610,7 @@ TEST_F(ContentExtensionTest, StrictPrefixSeparatedMachines1Partitioning)
     // Not this one.
     EXPECT_EQ(ContentExtensions::URLFilterParser::ParseStatus::Ok, parser.addPattern("^[ab]+bang", false, 0));
 
-    EXPECT_EQ(2ul, combinedURLFilters.createNFAs().size());
+    EXPECT_EQ(2ul, createNFAs(combinedURLFilters).size());
 }
 
 TEST_F(ContentExtensionTest, StrictPrefixSeparatedMachines2)
@@ -632,7 +643,7 @@ TEST_F(ContentExtensionTest, StrictPrefixSeparatedMachines2Partitioning)
     EXPECT_EQ(ContentExtensions::URLFilterParser::ParseStatus::Ok, parser.addPattern("[a-c]+b+oom", false, 3));
 
     // "^foo" and "^webkit:" can be grouped, the other two have a variable prefix.
-    EXPECT_EQ(3ul, combinedURLFilters.createNFAs().size());
+    EXPECT_EQ(3ul, createNFAs(combinedURLFilters).size());
 }
 
 static void testPatternStatus(String pattern, ContentExtensions::URLFilterParser::ParseStatus status)
index e678390..ea8c43c 100644 (file)
@@ -43,7 +43,7 @@ public:
     }
 };
 
-unsigned countLiveNodes(const ContentExtensions::DFA& dfa)
+static unsigned countLiveNodes(const ContentExtensions::DFA& dfa)
 {
     unsigned counter = 0;
     for (const auto& node : dfa.nodes) {
@@ -53,6 +53,17 @@ unsigned countLiveNodes(const ContentExtensions::DFA& dfa)
     return counter;
 }
 
+static Vector<ContentExtensions::NFA> createNFAs(ContentExtensions::CombinedURLFilters& combinedURLFilters)
+{
+    Vector<ContentExtensions::NFA> nfas;
+
+    combinedURLFilters.processNFAs([&](ContentExtensions::NFA&& nfa) {
+        nfas.append(WTF::move(nfa));
+    });
+
+    return nfas;
+}
+
 ContentExtensions::DFA buildDFAFromPatterns(Vector<const char*> patterns)
 {
     ContentExtensions::CombinedURLFilters combinedURLFilters;
@@ -60,7 +71,7 @@ ContentExtensions::DFA buildDFAFromPatterns(Vector<const char*> patterns)
 
     for (const char* pattern : patterns)
         parser.addPattern(pattern, false, 0);
-    Vector<ContentExtensions::NFA> nfas = combinedURLFilters.createNFAs();
+    Vector<ContentExtensions::NFA> nfas = createNFAs(combinedURLFilters);
     return ContentExtensions::NFAToDFA::convert(nfas[0]);
 }