GeezerVison

The World Wide Web, restored to 800 pixels of glory.

GeezerVison is showing github.com — v8: fix stack overflow in recursive method by bnoordhuis · Pull Request #12460 · nodejs/node

Conversation

bnoordhuis commented Apr 17, 2017 •

edited

Loading

Uh oh!

There was an error while loading. Please reload this page.

Copy link

Copy Markdown

Member

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.

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.

johan13 reacted with thumbs up emoji

All reactions

👍 1 reaction

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 commented Apr 17, 2017

Copy link

Copy Markdown

Member

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

All reactions

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.

hashseed reviewed

Apr 17, 2017

View reviewed changes

hashseed left a comment

Copy link

Copy Markdown

Member

There was a problem hiding this comment.

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

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.

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.

All reactions

bnoordhuis force-pushed the fix11991 branch from 2068233 to 790986f Compare

April 18, 2017 08:17

bnoordhuis commented Apr 18, 2017

Copy link

Copy Markdown

Member Author

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/

All reactions

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.

hashseed commented Apr 18, 2017

Copy link

Copy Markdown

Member

LGTM.

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

All reactions

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.

jasnell approved these changes

Apr 19, 2017

View reviewed changes

jasnell left a comment

Copy link

Copy Markdown

Member

There was a problem hiding this comment.

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

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

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.

All reactions

hashseed commented Apr 19, 2017

Copy link

Copy Markdown

Member

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.

All reactions

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.

bnoordhuis commented Apr 19, 2017

Copy link

Copy Markdown

Member Author

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

jasnell reacted with thumbs up emoji

All reactions

👍 1 reaction

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.


          v8: fix stack overflow in recursive method

30989d3

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 <[email protected]>
Reviewed-By: Yang Guo <[email protected]>

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

targos pushed a commit that referenced this pull request

Apr 24, 2017


          v8: fix stack overflow in recursive method

c31690a

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 <[email protected]>
Reviewed-By: Yang Guo <[email protected]>

evanlucas pushed a commit that referenced this pull request

Apr 25, 2017


          v8: fix stack overflow in recursive method

a54e7cd

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 <[email protected]>
Reviewed-By: Yang Guo <[email protected]>

targos pushed a commit that referenced this pull request

Apr 26, 2017


          v8: fix stack overflow in recursive method

d111fe7

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 <[email protected]>
Reviewed-By: Yang Guo <[email protected]>

targos pushed a commit that referenced this pull request

Apr 27, 2017


          v8: fix stack overflow in recursive method

df619b4

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 <[email protected]>
Reviewed-By: Yang Guo <[email protected]>

targos pushed a commit that referenced this pull request

Apr 28, 2017


          v8: fix stack overflow in recursive method

b44e1a8

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 <[email protected]>
Reviewed-By: Yang Guo <[email protected]>

targos pushed a commit that referenced this pull request

May 1, 2017


          v8: fix stack overflow in recursive method

af3a4c6

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 <[email protected]>
Reviewed-By: Yang Guo <[email protected]>

evanlucas mentioned this pull request

May 1, 2017

v7.10.0 proposal #12775

Merged

evanlucas pushed a commit that referenced this pull request

May 1, 2017


          v8: fix stack overflow in recursive method

6361fed

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 <[email protected]>
Reviewed-By: Yang Guo <[email protected]>

evanlucas pushed a commit that referenced this pull request

May 2, 2017


          v8: fix stack overflow in recursive method

e77f1e2

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 <[email protected]>
Reviewed-By: Yang Guo <[email protected]>

gibfahn commented May 16, 2017

Copy link

Copy Markdown

Member

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

All reactions

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.

gibfahn added the lts-watch-v6.x label

May 16, 2017

bnoordhuis commented May 16, 2017

Copy link

Copy Markdown

Member Author

@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.

All reactions

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.

gibfahn added lts-watch-v4.x and removed lts-watch-v6.x labels

May 16, 2017

gibfahn pushed a commit that referenced this pull request

May 16, 2017


          v8: fix stack overflow in recursive method

72fe2b8

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 <[email protected]>
Reviewed-By: Yang Guo <[email protected]>

gibfahn commented May 16, 2017 •

edited

Loading

Uh oh!

There was an error while loading. Please reload this page.

Copy link

Copy Markdown

Member

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;
 }

All reactions

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.

gibfahn added the backport-requested-v4.x label

May 16, 2017

bnoordhuis added a commit to bnoordhuis/io.js that referenced this pull request

May 17, 2017


          v8: fix stack overflow in recursive method

75aa079

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 <[email protected]>
Reviewed-By: Yang Guo <[email protected]>

bnoordhuis mentioned this pull request

May 17, 2017

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

Closed

bnoordhuis commented May 17, 2017

Copy link

Copy Markdown

Member Author

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

gibfahn reacted with thumbs up emoji

All reactions

👍 1 reaction

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.

MylesBorins pushed a commit that referenced this pull request

May 18, 2017


          v8: fix stack overflow in recursive method

a0f9d59

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 <[email protected]>
Reviewed-By: Yang Guo <[email protected]>

anchnk pushed a commit to anchnk/node that referenced this pull request

May 19, 2017


          v8: fix stack overflow in recursive method

7132bbb

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 <[email protected]>
Reviewed-By: Yang Guo <[email protected]>

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

Reviewers

jasnell

jasnell approved these changes

+1 more reviewer

hashseed

hashseed left review comments

Reviewers whose approvals may not affect merge requirements

Uh oh!

There was an error while loading. Please reload this page.

Assignees

No one assigned

Labels

v8 engine

Issues and PRs related to the V8 dependency.

Projects

None yet

Milestone

No milestone

Development

Successfully merging this pull request may close these issues.

Uh oh!

There was an error while loading. Please reload this page.

6 participants

Add this suggestion to a batch that can be applied as a single commit.This suggestion is invalid because no changes were made to the code.Suggestions cannot be applied while the pull request is closed.Suggestions cannot be applied while viewing a subset of changes.Only one suggestion per line can be applied in a batch.Add this suggestion to a batch that can be applied as a single commit.Applying suggestions on deleted lines is not supported.You must change the existing code in this line in order to create a valid suggestion.Outdated suggestions cannot be applied.This suggestion has been applied or marked resolved.Suggestions cannot be applied from pending reviews.Suggestions cannot be applied on multi-line comments.Suggestions cannot be applied while the pull request is queued to merge.Suggestion cannot be applied right now. Please check back later.

You are visitor 01402503 — GeezerVison does not store the pages you look up.
Best viewed with Netscape Navigator 4.7 or Internet Explorer 6 at 800×600. No cookies required.

GeezerVison

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

Uh oh!

Assignees

Labels

Projects

Milestone

Development

Uh oh!

6 participants

bnoordhuis commented Apr 17, 2017 •

edited

Loading

Uh oh!

There was an error while loading. Please reload this page.

gibfahn commented May 16, 2017 •

edited

Loading

Uh oh!

There was an error while loading. Please reload this page.