<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.1//EN"
"http://www.w3.org/TR/xhtml11/DTD/xhtml11.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head><meta http-equiv="content-type" content="text/html; charset=utf-8" />
<title>[183845] trunk/Source/WebCore</title>
</head>
<body>
<style type="text/css"><!--
#msg dl.meta { border: 1px #006 solid; background: #369; padding: 6px; color: #fff; }
#msg dl.meta dt { float: left; width: 6em; font-weight: bold; }
#msg dt:after { content:':';}
#msg dl, #msg dt, #msg ul, #msg li, #header, #footer, #logmsg { font-family: verdana,arial,helvetica,sans-serif; font-size: 10pt; }
#msg dl a { font-weight: bold}
#msg dl a:link { color:#fc3; }
#msg dl a:active { color:#ff0; }
#msg dl a:visited { color:#cc6; }
h3 { font-family: verdana,arial,helvetica,sans-serif; font-size: 10pt; font-weight: bold; }
#msg pre { overflow: auto; background: #ffc; border: 1px #fa0 solid; padding: 6px; }
#logmsg { background: #ffc; border: 1px #fa0 solid; padding: 1em 1em 0 1em; }
#logmsg p, #logmsg pre, #logmsg blockquote { margin: 0 0 1em 0; }
#logmsg p, #logmsg li, #logmsg dt, #logmsg dd { line-height: 14pt; }
#logmsg h1, #logmsg h2, #logmsg h3, #logmsg h4, #logmsg h5, #logmsg h6 { margin: .5em 0; }
#logmsg h1:first-child, #logmsg h2:first-child, #logmsg h3:first-child, #logmsg h4:first-child, #logmsg h5:first-child, #logmsg h6:first-child { margin-top: 0; }
#logmsg ul, #logmsg ol { padding: 0; list-style-position: inside; margin: 0 0 0 1em; }
#logmsg ul { text-indent: -1em; padding-left: 1em; }#logmsg ol { text-indent: -1.5em; padding-left: 1.5em; }
#logmsg > ul, #logmsg > ol { margin: 0 0 1em 0; }
#logmsg pre { background: #eee; padding: 1em; }
#logmsg blockquote { border: 1px solid #fa0; border-left-width: 10px; padding: 1em 1em 0 1em; background: white;}
#logmsg dl { margin: 0; }
#logmsg dt { font-weight: bold; }
#logmsg dd { margin: 0; padding: 0 0 0.5em 0; }
#logmsg dd:before { content:'\00bb';}
#logmsg table { border-spacing: 0px; border-collapse: collapse; border-top: 4px solid #fa0; border-bottom: 1px solid #fa0; background: #fff; }
#logmsg table th { text-align: left; font-weight: normal; padding: 0.2em 0.5em; border-top: 1px dotted #fa0; }
#logmsg table td { text-align: right; border-top: 1px dotted #fa0; padding: 0.2em 0.5em; }
#logmsg table thead th { text-align: center; border-bottom: 1px solid #fa0; }
#logmsg table th.Corner { text-align: left; }
#logmsg hr { border: none 0; border-top: 2px dashed #fa0; height: 1px; }
#header, #footer { color: #fff; background: #636; border: 1px #300 solid; padding: 6px; }
#patch { width: 100%; }
#patch h4 {font-family: verdana,arial,helvetica,sans-serif;font-size:10pt;padding:8px;background:#369;color:#fff;margin:0;}
#patch .propset h4, #patch .binary h4 {margin:0;}
#patch pre {padding:0;line-height:1.2em;margin:0;}
#patch .diff {width:100%;background:#eee;padding: 0 0 10px 0;overflow:auto;}
#patch .propset .diff, #patch .binary .diff {padding:10px 0;}
#patch span {display:block;padding:0 10px;}
#patch .modfile, #patch .addfile, #patch .delfile, #patch .propset, #patch .binary, #patch .copfile {border:1px solid #ccc;margin:10px 0;}
#patch ins {background:#dfd;text-decoration:none;display:block;padding:0 10px;}
#patch del {background:#fdd;text-decoration:none;display:block;padding:0 10px;}
#patch .lines, .info {color:#888;background:#fff;}
--></style>
<div id="msg">
<dl class="meta">
<dt>Revision</dt> <dd><a href="http://trac.webkit.org/projects/webkit/changeset/183845">183845</a></dd>
<dt>Author</dt> <dd>achristensen@apple.com</dd>
<dt>Date</dt> <dd>2015-05-05 18:12:49 -0700 (Tue, 05 May 2015)</dd>
</dl>
<h3>Log Message</h3>
<pre>[Content Extensions] Limit NFA size.
https://bugs.webkit.org/show_bug.cgi?id=144649
Reviewed by Benjamin Poulain.
* contentextensions/CombinedURLFilters.cpp:
(WebCore::ContentExtensions::generateNFAForSubtree):
(WebCore::ContentExtensions::CombinedURLFilters::processNFAs):
Add a maximum NFA size to ensure that we do not use too much memory when compiling.
* contentextensions/ContentExtensionCompiler.cpp:
(WebCore::ContentExtensions::compileRuleList):
Remove debugging code that doesn't compile any more.</pre>
<h3>Modified Paths</h3>
<ul>
<li><a href="#trunkSourceWebCoreChangeLog">trunk/Source/WebCore/ChangeLog</a></li>
<li><a href="#trunkSourceWebCorecontentextensionsCombinedURLFilterscpp">trunk/Source/WebCore/contentextensions/CombinedURLFilters.cpp</a></li>
<li><a href="#trunkSourceWebCorecontentextensionsContentExtensionCompilercpp">trunk/Source/WebCore/contentextensions/ContentExtensionCompiler.cpp</a></li>
</ul>
</div>
<div id="patch">
<h3>Diff</h3>
<a id="trunkSourceWebCoreChangeLog"></a>
<div class="modfile"><h4>Modified: trunk/Source/WebCore/ChangeLog (183844 => 183845)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WebCore/ChangeLog 2015-05-06 00:21:47 UTC (rev 183844)
+++ trunk/Source/WebCore/ChangeLog 2015-05-06 01:12:49 UTC (rev 183845)
</span><span class="lines">@@ -1,3 +1,18 @@
</span><ins>+2015-05-05 Alex Christensen <achristensen@webkit.org>
+
+ [Content Extensions] Limit NFA size.
+ https://bugs.webkit.org/show_bug.cgi?id=144649
+
+ Reviewed by Benjamin Poulain.
+
+ * contentextensions/CombinedURLFilters.cpp:
+ (WebCore::ContentExtensions::generateNFAForSubtree):
+ (WebCore::ContentExtensions::CombinedURLFilters::processNFAs):
+ Add a maximum NFA size to ensure that we do not use too much memory when compiling.
+ * contentextensions/ContentExtensionCompiler.cpp:
+ (WebCore::ContentExtensions::compileRuleList):
+ Remove debugging code that doesn't compile any more.
+
</ins><span class="cx"> 2015-05-05 Roger Fong <roger_fong@apple.com>
</span><span class="cx">
</span><span class="cx"> Unreviewed. Some assertion failures in compositing code after r183820.
</span></span></pre></div>
<a id="trunkSourceWebCorecontentextensionsCombinedURLFilterscpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/WebCore/contentextensions/CombinedURLFilters.cpp (183844 => 183845)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WebCore/contentextensions/CombinedURLFilters.cpp 2015-05-06 00:21:47 UTC (rev 183844)
+++ trunk/Source/WebCore/contentextensions/CombinedURLFilters.cpp 2015-05-06 01:12:49 UTC (rev 183845)
</span><span class="lines">@@ -170,15 +170,29 @@
</span><span class="cx"> Vector<ActiveSubtree> stack;
</span><span class="cx"> if (!root.edges.isEmpty())
</span><span class="cx"> stack.append(ActiveSubtree(root, nfaRootId, 0));
</span><ins>+ bool nfaTooBig = false;
</ins><span class="cx">
</span><span class="cx"> // Generate graphs for each subtree that does not contain any quantifiers.
</span><span class="cx"> while (!stack.isEmpty()) {
</span><span class="cx"> PrefixTreeVertex& vertex = stack.last().vertex;
</span><span class="cx"> const unsigned edgeIndex = stack.last().edgeIndex;
</span><span class="cx">
</span><ins>+ // FIXME: This can be tuned. More NFAs take longer to interpret, fewer use more memory and time to compile.
+ const unsigned maxNFASize = 50000;
+
+ // Only stop generating an NFA at a leaf to ensure we have a correct NFA. We could go slightly over the maxNFASize.
+ if (vertex.edges.isEmpty() && nfa.graphSize() > maxNFASize)
+ nfaTooBig = true;
+
</ins><span class="cx"> if (edgeIndex < vertex.edges.size()) {
</span><span class="cx"> auto& edge = vertex.edges[edgeIndex];
</span><span class="cx">
</span><ins>+ // Clean up any processed leaves and return early if we are past the maxNFASize.
+ if (nfaTooBig) {
+ stack.last().edgeIndex = stack.last().vertex.edges.size();
+ continue;
+ }
+
</ins><span class="cx"> // Quantified edges in the subtree will be a part of another NFA.
</span><span class="cx"> if (!edge.term.hasFixedLength()) {
</span><span class="cx"> stack.last().edgeIndex++;
</span></span></pre></div>
<a id="trunkSourceWebCorecontentextensionsContentExtensionCompilercpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/WebCore/contentextensions/ContentExtensionCompiler.cpp (183844 => 183845)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WebCore/contentextensions/ContentExtensionCompiler.cpp 2015-05-06 00:21:47 UTC (rev 183844)
+++ trunk/Source/WebCore/contentextensions/ContentExtensionCompiler.cpp 2015-05-06 01:12:49 UTC (rev 183845)
</span><span class="lines">@@ -207,25 +207,10 @@
</span><span class="cx">
</span><span class="cx"> LOG_LARGE_STRUCTURES(nfa, nfa.memoryUsed());
</span><span class="cx">
</span><del>-#if CONTENT_EXTENSIONS_PERFORMANCE_REPORTING
- double dfaBuildTimeStart = monotonicallyIncreasingTime();
-#endif
</del><span class="cx"> DFA dfa = NFAToDFA::convert(nfa);
</span><span class="cx"> LOG_LARGE_STRUCTURES(dfa, dfa.memoryUsed());
</span><span class="cx">
</span><del>-#if CONTENT_EXTENSIONS_PERFORMANCE_REPORTING
- double dfaBuildTimeEnd = monotonicallyIncreasingTime();
- dataLogF(" Time spent building the DFA: %f\n", (dfaBuildTimeEnd - dfaBuildTimeStart));
-#endif
-
-#if CONTENT_EXTENSIONS_PERFORMANCE_REPORTING
- double dfaMinimizationTimeStart = monotonicallyIncreasingTime();
-#endif
</del><span class="cx"> dfa.minimize();
</span><del>-#if CONTENT_EXTENSIONS_PERFORMANCE_REPORTING
- double dfaMinimizationTimeEnd = monotonicallyIncreasingTime();
- dataLogF(" Time spent miniminizing the DFA: %f\n", (dfaMinimizationTimeEnd - dfaMinimizationTimeStart));
-#endif
</del><span class="cx">
</span><span class="cx"> #if CONTENT_EXTENSIONS_STATE_MACHINE_DEBUGGING
</span><span class="cx"> WTFLogAlways("DFA");
</span><span class="lines">@@ -270,7 +255,6 @@
</span><span class="cx"> #if CONTENT_EXTENSIONS_PERFORMANCE_REPORTING
</span><span class="cx"> double totalNFAToByteCodeBuildTimeEnd = monotonicallyIncreasingTime();
</span><span class="cx"> dataLogF(" Time spent building and compiling the DFAs: %f\n", (totalNFAToByteCodeBuildTimeEnd - totalNFAToByteCodeBuildTimeStart));
</span><del>- dataLogF(" Bytecode size %zu\n", bytecode.size());
</del><span class="cx"> #endif
</span><span class="cx">
</span><span class="cx"> client.finalize();
</span></span></pre>
</div>
</div>
</body>
</html>