<!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>[203802] trunk/Source/JavaScriptCore</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/203802">203802</a></dd>
<dt>Author</dt> <dd>benjamin@webkit.org</dd>
<dt>Date</dt> <dd>2016-07-27 16:22:55 -0700 (Wed, 27 Jul 2016)</dd>
</dl>
<h3>Log Message</h3>
<pre>[JSC] Fix a bunch of use-after-free of DFG::Node
https://bugs.webkit.org/show_bug.cgi?id=160228
Patch by Benjamin Poulain <bpoulain@apple.com> on 2016-07-27
Reviewed by Mark Lam.
FTL had a few places where we use a node after it has been
deleted. The dangling pointers come from the SSA liveness information
kept on the basic blocks.
This patch fixes the issues I could find and adds liveness invalidation
to help finding dependencies like these.
* dfg/DFGBasicBlock.h:
(JSC::DFG::BasicBlock::SSAData::invalidate):
* dfg/DFGConstantFoldingPhase.cpp:
(JSC::DFG::ConstantFoldingPhase::run):
Constant folding phase was deleting nodes in the loop over basic blocks.
The problem is the deleted nodes can be referenced by other blocks.
When the abstract interpreter was manipulating the abstract values of those
it was doing so on the dead nodes.
* dfg/DFGConstantHoistingPhase.cpp:
Just invalidation. Nothing wrong here since the useless nodes were
kept live while iterating the blocks.
* dfg/DFGGraph.cpp:
(JSC::DFG::Graph::killBlockAndItsContents):
(JSC::DFG::Graph::killUnreachableBlocks):
(JSC::DFG::Graph::invalidateNodeLiveness):
* dfg/DFGGraph.h:
* dfg/DFGPlan.cpp:
(JSC::DFG::Plan::compileInThreadImpl):
We had a lot of use-after-free in LCIM because we were using the stale
live nodes deleted by previous phases.</pre>
<h3>Modified Paths</h3>
<ul>
<li><a href="#trunkSourceJavaScriptCoreChangeLog">trunk/Source/JavaScriptCore/ChangeLog</a></li>
<li><a href="#trunkSourceJavaScriptCoredfgDFGBasicBlockh">trunk/Source/JavaScriptCore/dfg/DFGBasicBlock.h</a></li>
<li><a href="#trunkSourceJavaScriptCoredfgDFGConstantFoldingPhasecpp">trunk/Source/JavaScriptCore/dfg/DFGConstantFoldingPhase.cpp</a></li>
<li><a href="#trunkSourceJavaScriptCoredfgDFGConstantHoistingPhasecpp">trunk/Source/JavaScriptCore/dfg/DFGConstantHoistingPhase.cpp</a></li>
<li><a href="#trunkSourceJavaScriptCoredfgDFGGraphcpp">trunk/Source/JavaScriptCore/dfg/DFGGraph.cpp</a></li>
<li><a href="#trunkSourceJavaScriptCoredfgDFGGraphh">trunk/Source/JavaScriptCore/dfg/DFGGraph.h</a></li>
<li><a href="#trunkSourceJavaScriptCoredfgDFGPlancpp">trunk/Source/JavaScriptCore/dfg/DFGPlan.cpp</a></li>
</ul>
</div>
<div id="patch">
<h3>Diff</h3>
<a id="trunkSourceJavaScriptCoreChangeLog"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/ChangeLog (203801 => 203802)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/ChangeLog 2016-07-27 22:34:02 UTC (rev 203801)
+++ trunk/Source/JavaScriptCore/ChangeLog 2016-07-27 23:22:55 UTC (rev 203802)
</span><span class="lines">@@ -1,3 +1,42 @@
</span><ins>+2016-07-27 Benjamin Poulain <bpoulain@apple.com>
+
+ [JSC] Fix a bunch of use-after-free of DFG::Node
+ https://bugs.webkit.org/show_bug.cgi?id=160228
+
+ Reviewed by Mark Lam.
+
+ FTL had a few places where we use a node after it has been
+ deleted. The dangling pointers come from the SSA liveness information
+ kept on the basic blocks.
+
+ This patch fixes the issues I could find and adds liveness invalidation
+ to help finding dependencies like these.
+
+ * dfg/DFGBasicBlock.h:
+ (JSC::DFG::BasicBlock::SSAData::invalidate):
+
+ * dfg/DFGConstantFoldingPhase.cpp:
+ (JSC::DFG::ConstantFoldingPhase::run):
+ Constant folding phase was deleting nodes in the loop over basic blocks.
+ The problem is the deleted nodes can be referenced by other blocks.
+ When the abstract interpreter was manipulating the abstract values of those
+ it was doing so on the dead nodes.
+
+ * dfg/DFGConstantHoistingPhase.cpp:
+ Just invalidation. Nothing wrong here since the useless nodes were
+ kept live while iterating the blocks.
+
+ * dfg/DFGGraph.cpp:
+ (JSC::DFG::Graph::killBlockAndItsContents):
+ (JSC::DFG::Graph::killUnreachableBlocks):
+ (JSC::DFG::Graph::invalidateNodeLiveness):
+
+ * dfg/DFGGraph.h:
+ * dfg/DFGPlan.cpp:
+ (JSC::DFG::Plan::compileInThreadImpl):
+ We had a lot of use-after-free in LCIM because we were using the stale
+ live nodes deleted by previous phases.
+
</ins><span class="cx"> 2016-07-27 Keith Miller <keith_miller@apple.com>
</span><span class="cx">
</span><span class="cx"> concatAppendOne should allocate using the indexing type of the array if it cannot merge
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoredfgDFGBasicBlockh"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/dfg/DFGBasicBlock.h (203801 => 203802)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/dfg/DFGBasicBlock.h 2016-07-27 22:34:02 UTC (rev 203801)
+++ trunk/Source/JavaScriptCore/dfg/DFGBasicBlock.h 2016-07-27 23:22:55 UTC (rev 203802)
</span><span class="lines">@@ -239,6 +239,14 @@
</span><span class="cx"> struct SSAData {
</span><span class="cx"> WTF_MAKE_FAST_ALLOCATED;
</span><span class="cx"> public:
</span><ins>+ void invalidate()
+ {
+ liveAtTail.clear();
+ liveAtHead.clear();
+ valuesAtHead.clear();
+ valuesAtTail.clear();
+ }
+
</ins><span class="cx"> AvailabilityMap availabilityAtHead;
</span><span class="cx"> AvailabilityMap availabilityAtTail;
</span><span class="cx">
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoredfgDFGConstantFoldingPhasecpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/dfg/DFGConstantFoldingPhase.cpp (203801 => 203802)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/dfg/DFGConstantFoldingPhase.cpp 2016-07-27 22:34:02 UTC (rev 203801)
+++ trunk/Source/JavaScriptCore/dfg/DFGConstantFoldingPhase.cpp 2016-07-27 23:22:55 UTC (rev 203802)
</span><span class="lines">@@ -71,6 +71,7 @@
</span><span class="cx"> // It's now possible to simplify basic blocks by placing an Unreachable terminator right
</span><span class="cx"> // after anything that invalidates AI.
</span><span class="cx"> bool didClipBlock = false;
</span><ins>+ Vector<Node*> nodesToDelete;
</ins><span class="cx"> for (BasicBlock* block : m_graph.blocksInNaturalOrder()) {
</span><span class="cx"> m_state.beginBasicBlock(block);
</span><span class="cx"> for (unsigned nodeIndex = 0; nodeIndex < block->size(); ++nodeIndex) {
</span><span class="lines">@@ -83,7 +84,7 @@
</span><span class="cx"> if (!m_state.isValid()) {
</span><span class="cx"> NodeOrigin origin = block->at(nodeIndex)->origin;
</span><span class="cx"> for (unsigned killIndex = nodeIndex; killIndex < block->size(); ++killIndex)
</span><del>- m_graph.m_allocator.free(block->at(killIndex));
</del><ins>+ nodesToDelete.append(block->at(killIndex));
</ins><span class="cx"> block->resize(nodeIndex);
</span><span class="cx"> block->appendNode(m_graph, SpecNone, Unreachable, origin);
</span><span class="cx"> didClipBlock = true;
</span><span class="lines">@@ -96,6 +97,12 @@
</span><span class="cx">
</span><span class="cx"> if (didClipBlock) {
</span><span class="cx"> changed = true;
</span><ins>+
+ m_graph.invalidateNodeLiveness();
+
+ for (Node* node : nodesToDelete)
+ m_graph.m_allocator.free(node);
+
</ins><span class="cx"> m_graph.invalidateCFG();
</span><span class="cx"> m_graph.resetReachability();
</span><span class="cx"> m_graph.killUnreachableBlocks();
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoredfgDFGConstantHoistingPhasecpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/dfg/DFGConstantHoistingPhase.cpp (203801 => 203802)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/dfg/DFGConstantHoistingPhase.cpp 2016-07-27 22:34:02 UTC (rev 203801)
+++ trunk/Source/JavaScriptCore/dfg/DFGConstantHoistingPhase.cpp 2016-07-27 23:22:55 UTC (rev 203802)
</span><span class="lines">@@ -128,6 +128,7 @@
</span><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> // And finally free the constants that we removed.
</span><ins>+ m_graph.invalidateNodeLiveness();
</ins><span class="cx"> for (Node* node : toFree)
</span><span class="cx"> m_graph.m_allocator.free(node);
</span><span class="cx">
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoredfgDFGGraphcpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/dfg/DFGGraph.cpp (203801 => 203802)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/dfg/DFGGraph.cpp 2016-07-27 22:34:02 UTC (rev 203801)
+++ trunk/Source/JavaScriptCore/dfg/DFGGraph.cpp 2016-07-27 23:22:55 UTC (rev 203802)
</span><span class="lines">@@ -744,6 +744,8 @@
</span><span class="cx">
</span><span class="cx"> void Graph::killBlockAndItsContents(BasicBlock* block)
</span><span class="cx"> {
</span><ins>+ if (auto& ssaData = block->ssa)
+ ssaData->invalidate();
</ins><span class="cx"> for (unsigned phiIndex = block->phis.size(); phiIndex--;)
</span><span class="cx"> m_allocator.free(block->phis[phiIndex]);
</span><span class="cx"> for (unsigned nodeIndex = block->size(); nodeIndex--;)
</span><span class="lines">@@ -754,9 +756,8 @@
</span><span class="cx">
</span><span class="cx"> void Graph::killUnreachableBlocks()
</span><span class="cx"> {
</span><del>- // FIXME: This probably creates dangling references from Upsilons to Phis in SSA.
- // https://bugs.webkit.org/show_bug.cgi?id=159164
-
</del><ins>+ invalidateNodeLiveness();
+
</ins><span class="cx"> for (BlockIndex blockIndex = 0; blockIndex < numBlocks(); ++blockIndex) {
</span><span class="cx"> BasicBlock* block = this->block(blockIndex);
</span><span class="cx"> if (!block)
</span><span class="lines">@@ -778,6 +779,15 @@
</span><span class="cx"> m_backwardsCFG = nullptr;
</span><span class="cx"> }
</span><span class="cx">
</span><ins>+void Graph::invalidateNodeLiveness()
+{
+ if (m_form != SSA)
+ return;
+
+ for (BasicBlock* block : blocksInNaturalOrder())
+ block->ssa->invalidate();
+}
+
</ins><span class="cx"> void Graph::substituteGetLocal(BasicBlock& block, unsigned startIndexInBlock, VariableAccessData* variableAccessData, Node* newGetLocal)
</span><span class="cx"> {
</span><span class="cx"> for (unsigned indexInBlock = startIndexInBlock; indexInBlock < block.size(); ++indexInBlock) {
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoredfgDFGGraphh"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/dfg/DFGGraph.h (203801 => 203802)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/dfg/DFGGraph.h 2016-07-27 22:34:02 UTC (rev 203801)
+++ trunk/Source/JavaScriptCore/dfg/DFGGraph.h 2016-07-27 23:22:55 UTC (rev 203802)
</span><span class="lines">@@ -533,6 +533,7 @@
</span><span class="cx"> void substituteGetLocal(BasicBlock& block, unsigned startIndexInBlock, VariableAccessData* variableAccessData, Node* newGetLocal);
</span><span class="cx">
</span><span class="cx"> void invalidateCFG();
</span><ins>+ void invalidateNodeLiveness();
</ins><span class="cx">
</span><span class="cx"> void clearFlagsOnAllNodes(NodeFlags);
</span><span class="cx">
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoredfgDFGPlancpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/dfg/DFGPlan.cpp (203801 => 203802)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/dfg/DFGPlan.cpp 2016-07-27 22:34:02 UTC (rev 203801)
+++ trunk/Source/JavaScriptCore/dfg/DFGPlan.cpp 2016-07-27 23:22:55 UTC (rev 203802)
</span><span class="lines">@@ -428,6 +428,8 @@
</span><span class="cx"> // wrong with running LICM earlier, if we wanted to put other CFG transforms above this point.
</span><span class="cx"> // Alternatively, we could run loop pre-header creation after SSA conversion - but if we did that
</span><span class="cx"> // then we'd need to do some simple SSA fix-up.
</span><ins>+ performLivenessAnalysis(dfg);
+ performCFA(dfg);
</ins><span class="cx"> performLICM(dfg);
</span><span class="cx">
</span><span class="cx"> // FIXME: Currently: IntegerRangeOptimization *must* be run after LICM.
</span></span></pre>
</div>
</div>
</body>
</html>