v8: fix stack overflow in recursive method by bnoordhuis · Pull Request #12460 · nodejs/node · GitHub

HGlobalValueNumberingPhase::CollectSideEffectsOnPathsToDominatedBlock()
used to self-recurse before this commit, causing stack overflows on
systems with small stack sizes. Make it non-recursive by storing
intermediate results in a heap-allocated list.

The first commit is the obvious way to implement it, the second commit optimizes a bit.

Switching to heap allocations might in theory have performance implications but, as a data point, it doesn't seem to affect the running time of the node.js test suite.

V8 CI (1st commit): https://ci.nodejs.org/job/node-test-commit-v8-linux/651/ (green)
V8 CI (2nd commit): https://ci.nodejs.org/job/node-test-commit-v8-linux/652/ (green)
V8 CI (3rd commit): https://ci.nodejs.org/job/node-test-commit-v8-linux/653/
Node CI (2nd commit): https://ci.nodejs.org/job/node-test-pull-request/7439/
Node CI (3rd commit): https://ci.nodejs.org/job/node-test-pull-request/7466/

See #11991.

I don't expect any performance impact because this part of Crankshaft should run on the background thread anyways.

You probably can use the list as a stack (instead of queue) and just pop the last element at the end of the loop? That would lessen the peak memory use.

Made the suggested change. I wasn't sure if walking them in a different order was sound but it computes the union so I suppose it must be.

V8 CI: https://ci.nodejs.org/job/node-test-commit-v8-linux/653/
Node CI: https://ci.nodejs.org/job/node-test-pull-request/7466/

LGTM.

FWIW 2nd commit didn't traverse the same order as the recursion did either (BFS vs DFS).

LGTM but is this a backport of a change in V8? or should this land upstream first?

V8 is not likely to ship a version with this patch anymore, and Crankshaft is being deprecated, so I'm not sure how much value upstreaming has. I would give lgtm if @bnoordhuis provides a CL for upstream though.

I'm fine with floating it as a patch. Upstreaming it would be make-work for the both of us.

HGlobalValueNumberingPhase::CollectSideEffectsOnPathsToDominatedBlock() used to self-recurse before this commit, causing stack overflows on systems with small stack sizes. Make it non-recursive by storing intermediate results in a heap-allocated list. Fixes: nodejs#11991 PR-URL: nodejs#12460 Reviewed-By: James M Snell <jasnell@gmail.com> Reviewed-By: Yang Guo <yangguo@chromium.org>

HGlobalValueNumberingPhase::CollectSideEffectsOnPathsToDominatedBlock() used to self-recurse before this commit, causing stack overflows on systems with small stack sizes. Make it non-recursive by storing intermediate results in a heap-allocated list. Fixes: #11991 PR-URL: #12460 Reviewed-By: James M Snell <jasnell@gmail.com> Reviewed-By: Yang Guo <yangguo@chromium.org>

Should this be backported to v6.x? Please apply dont-land if not.

@gibfahn Yes, v6.x and v4.x. The filename is deps/v8/src/hydrogen-gvn.cc in v4.x but the patch should otherwise apply cleanly.

HGlobalValueNumberingPhase::CollectSideEffectsOnPathsToDominatedBlock() used to self-recurse before this commit, causing stack overflows on systems with small stack sizes. Make it non-recursive by storing intermediate results in a heap-allocated list. Fixes: #11991 PR-URL: #12460 Reviewed-By: James M Snell <jasnell@gmail.com> Reviewed-By: Yang Guo <yangguo@chromium.org>

Didn't apply cleanly in v4.x with the filename changed. Would you be willing to backport (assuming you think it's worth getting into a v4.x release).

It's possible I messed up the patch modification of course.

.git/rebase-apply/patch contents:

---
 deps/v8/src/hydrogen-gvn.cc | 28 +++++++++++++++++-----------
 1 file changed, 17 insertions(+), 11 deletions(-)

diff --git a/deps/v8/src/hydrogen-gvn.cc b/deps/v8/src/hydrogen-gvn.cc
index e6ddd75..bf51bad 100644
--- a/deps/v8/src/hydrogen-gvn.cc
+++ b/deps/v8/src/hydrogen-gvn.cc
@@ -5,6 +5,8 @@
 #include "src/crankshaft/hydrogen-gvn.h"
 
 #include "src/crankshaft/hydrogen.h"
+#include "src/list.h"
+#include "src/list-inl.h"
 #include "src/v8.h"
 
 namespace v8 {
@@ -650,19 +652,23 @@ SideEffects
 HGlobalValueNumberingPhase::CollectSideEffectsOnPathsToDominatedBlock(
     HBasicBlock* dominator, HBasicBlock* dominated) {
   SideEffects side_effects;
-  for (int i = 0; i < dominated->predecessors()->length(); ++i) {
-    HBasicBlock* block = dominated->predecessors()->at(i);
-    if (dominator->block_id() < block->block_id() &&
-        block->block_id() < dominated->block_id() &&
-        !visited_on_paths_.Contains(block->block_id())) {
-      visited_on_paths_.Add(block->block_id());
-      side_effects.Add(block_side_effects_[block->block_id()]);
-      if (block->IsLoopHeader()) {
-        side_effects.Add(loop_side_effects_[block->block_id()]);
+  List<HBasicBlock*> blocks;
+  for (;;) {
+    for (int i = 0; i < dominated->predecessors()->length(); ++i) {
+      HBasicBlock* block = dominated->predecessors()->at(i);
+      if (dominator->block_id() < block->block_id() &&
+          block->block_id() < dominated->block_id() &&
+          !visited_on_paths_.Contains(block->block_id())) {
+        visited_on_paths_.Add(block->block_id());
+        side_effects.Add(block_side_effects_[block->block_id()]);
+        if (block->IsLoopHeader()) {
+          side_effects.Add(loop_side_effects_[block->block_id()]);
+        }
+        blocks.Add(block);
       }
-      side_effects.Add(CollectSideEffectsOnPathsToDominatedBlock(
-          dominator, block));
     }
+    if (blocks.is_empty()) break;
+    dominated = blocks.RemoveLast();
   }
   return side_effects;
 }

HGlobalValueNumberingPhase::CollectSideEffectsOnPathsToDominatedBlock() used to self-recurse before this commit, causing stack overflows on systems with small stack sizes. Make it non-recursive by storing intermediate results in a heap-allocated list. Fixes: nodejs#11991 PR-URL: nodejs#12460 Reviewed-By: James M Snell <jasnell@gmail.com> Reviewed-By: Yang Guo <yangguo@chromium.org>

Benign conflict in the includes. v4.x PR: #13080

HGlobalValueNumberingPhase::CollectSideEffectsOnPathsToDominatedBlock() used to self-recurse before this commit, causing stack overflows on systems with small stack sizes. Make it non-recursive by storing intermediate results in a heap-allocated list. Fixes: #11991 PR-URL: #12460 Reviewed-By: James M Snell <jasnell@gmail.com> Reviewed-By: Yang Guo <yangguo@chromium.org>

HGlobalValueNumberingPhase::CollectSideEffectsOnPathsToDominatedBlock() used to self-recurse before this commit, causing stack overflows on systems with small stack sizes. Make it non-recursive by storing intermediate results in a heap-allocated list. Fixes: nodejs#11991 PR-URL: nodejs#12460 Reviewed-By: James M Snell <jasnell@gmail.com> Reviewed-By: Yang Guo <yangguo@chromium.org>

nodejs-github-bot added the v8 engine Issues and PRs related to the V8 dependency. label Apr 17, 2017

bnoordhuis changed the title Fix11991 v8: fix stack overflow in recursive method Apr 17, 2017

bnoordhuis mentioned this pull request Apr 17, 2017

Crashes when using ajv on Alpine Linux #11991

Closed

hashseed reviewed Apr 17, 2017

View reviewed changes

bnoordhuis force-pushed the fix11991 branch from 2068233 to 790986f Compare April 18, 2017 08:17

jasnell approved these changes Apr 19, 2017

View reviewed changes

bnoordhuis force-pushed the fix11991 branch from 790986f to 30989d3 Compare April 21, 2017 08:50

bnoordhuis closed this Apr 21, 2017

bnoordhuis deleted the fix11991 branch April 21, 2017 08:50

bnoordhuis merged commit 30989d3 into nodejs:master Apr 21, 2017

bnoordhuis mentioned this pull request Apr 21, 2017

v8: update v8 patch version number (v7.x) #12542

Closed

evanlucas mentioned this pull request May 1, 2017

v7.10.0 proposal #12775

Merged

gibfahn added the lts-watch-v6.x label May 16, 2017

gibfahn added lts-watch-v4.x and removed lts-watch-v6.x labels May 16, 2017

gibfahn added the backport-requested-v4.x label May 16, 2017

bnoordhuis mentioned this pull request May 17, 2017

v8: fix stack overflow in recursive method (v4.x) #13080

Closed

MylesBorins mentioned this pull request May 23, 2017

v6.11.0 proposal #13059

Merged

addaleax mentioned this pull request Jun 17, 2017

v8.2.0 proposal #13744

Merged

addaleax mentioned this pull request Jul 24, 2017

v8.3.0 proposal #14452

Closed

MylesBorins mentioned this pull request Sep 20, 2017

v4.8.5 proposal #15507

Closed

MylesBorins mentioned this pull request Oct 25, 2017

v4.8.6 proposal #16500

Merged

jasnell mentioned this pull request Oct 30, 2017

Proposal: 2017-10-31, Version 9.0.0 (Current) #15135

Merged

v8: fix stack overflow in recursive method by bnoordhuis · Pull Request #12460 · nodejs/node · GitHub

Uh oh!

Uh oh!

v8: fix stack overflow in recursive method - #12460

v8: fix stack overflow in recursive method #12460
bnoordhuis merged 1 commit into
nodejs:masterfrom
bnoordhuis:fix11991

bnoordhuis commented Apr 17, 2017 •
edited
Loading

Uh oh!

Uh oh!

hashseed commented Apr 17, 2017

Uh oh!

hashseed left a comment

Uh oh!

bnoordhuis commented Apr 18, 2017

Uh oh!

hashseed commented Apr 18, 2017

Uh oh!

jasnell left a comment

Uh oh!

hashseed commented Apr 19, 2017

Uh oh!

bnoordhuis commented Apr 19, 2017

Uh oh!

gibfahn commented May 16, 2017

Uh oh!

bnoordhuis commented May 16, 2017

Uh oh!

gibfahn commented May 16, 2017 •
edited
Loading

Uh oh!

Uh oh!

bnoordhuis commented May 17, 2017

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

6 participants

v8: fix stack overflow in recursive method by bnoordhuis · Pull Request #12460 · nodejs/node · GitHub

Uh oh!

Uh oh!

v8: fix stack overflow in recursive method - #12460

v8: fix stack overflow in recursive method #12460bnoordhuis merged 1 commit intonodejs:masternodejs/node:masterfrom bnoordhuis:fix11991bnoordhuis/io.js:fix11991Copy head branch name to clipboard

Conversation

bnoordhuis commented Apr 17, 2017 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

hashseed commented Apr 17, 2017

Uh oh!

hashseed left a comment

Choose a reason for hiding this comment

Uh oh!

bnoordhuis commented Apr 18, 2017

Uh oh!

hashseed commented Apr 18, 2017

Uh oh!

jasnell left a comment

Choose a reason for hiding this comment

Uh oh!

hashseed commented Apr 19, 2017

Uh oh!

bnoordhuis commented Apr 19, 2017

Uh oh!

gibfahn commented May 16, 2017

Uh oh!

bnoordhuis commented May 16, 2017

Uh oh!

gibfahn commented May 16, 2017 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

bnoordhuis commented May 17, 2017

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

6 participants

v8: fix stack overflow in recursive method #12460
bnoordhuis merged 1 commit into
nodejs:masterfrom
bnoordhuis:fix11991

bnoordhuis commented Apr 17, 2017 •
edited
Loading

gibfahn commented May 16, 2017 •
edited
Loading