Bug 203936 - Add a stack overflow check in Yarr::ByteCompiler::emitDisjunction().
Summary: Add a stack overflow check in Yarr::ByteCompiler::emitDisjunction().
Status: RESOLVED FIXED
Alias: None
Product: WebKit
Classification: Unclassified
Component: JavaScriptCore (show other bugs)
Version: WebKit Nightly Build
Hardware: Unspecified Unspecified
: P2 Normal
Assignee: Mark Lam
URL:
Keywords: InRadar
Depends on:
Blocks:
 
Reported: 2019-11-06 18:15 PST by Mark Lam
Modified: 2019-11-08 20:09 PST (History)
17 users (show)

See Also:


Attachments
proposed patch. (2.75 KB, patch)
2019-11-06 18:20 PST, Mark Lam
sbarati: review+
Details | Formatted Diff | Diff
work in progress for EWS testing. (7.16 KB, patch)
2019-11-07 00:30 PST, Mark Lam
no flags Details | Formatted Diff | Diff
work in progress for EWS testing. (6.70 KB, patch)
2019-11-07 00:32 PST, Mark Lam
no flags Details | Formatted Diff | Diff
work in progress for EWS testing. (7.61 KB, patch)
2019-11-07 01:17 PST, Mark Lam
no flags Details | Formatted Diff | Diff
proposed patch. (26.11 KB, patch)
2019-11-07 17:34 PST, Mark Lam
sbarati: review+
Details | Formatted Diff | Diff
patch for landing. (21.83 KB, patch)
2019-11-07 22:21 PST, Mark Lam
no flags Details | Formatted Diff | Diff
patch for landing. (21.93 KB, patch)
2019-11-07 23:00 PST, Mark Lam
no flags Details | Formatted Diff | Diff

Note You need to log in before you can comment on or make changes to this bug.
Description Mark Lam 2019-11-06 18:15:02 PST
<rdar://problem/56624724>
Comment 1 Mark Lam 2019-11-06 18:20:23 PST
Created attachment 382998 [details]
proposed patch.
Comment 2 Saam Barati 2019-11-06 18:25:52 PST
Comment on attachment 382998 [details]
proposed patch.

View in context: https://bugs.webkit.org/attachment.cgi?id=382998&action=review

r=me

> Source/JavaScriptCore/ChangeLog:8
> +

can you add a test that fails on x86 by making the stack limit small?
(Also worth noting that we already have an instance of this failing elsewhere too)

> Source/JavaScriptCore/yarr/YarrInterpreter.cpp:2416
> +    inline bool isSafeToRecurse() { return currentStackPointer() >= m_stackLimit; }

please ASSERT(Thread::current().stack().isGrowingDownward());

or maybe turn VM's isSafeToRecurse into a static public function and call that. (Or abstract it in WTF somewhere)
Comment 3 Saam Barati 2019-11-06 18:26:50 PST
Comment on attachment 382998 [details]
proposed patch.

View in context: https://bugs.webkit.org/attachment.cgi?id=382998&action=review

> Source/JavaScriptCore/yarr/YarrInterpreter.cpp:2036
> +        if (UNLIKELY(!isSafeToRecurse()))

does this need to be done elsewhere in the regex compiler?
Comment 4 Mark Lam 2019-11-07 00:30:28 PST
Created attachment 383027 [details]
work in progress for EWS testing.
Comment 5 Mark Lam 2019-11-07 00:32:55 PST
Created attachment 383028 [details]
work in progress for EWS testing.
Comment 6 Mark Lam 2019-11-07 01:10:29 PST
(In reply to Saam Barati from comment #2)
> > Source/JavaScriptCore/ChangeLog:8
> > +
> 
> can you add a test that fails on x86 by making the stack limit small?
> (Also worth noting that we already have an instance of this failing
> elsewhere too)

In order to do this, I'll need to add a utility to (1) exhaust physical stack space quickly, and (2) make the VM think it's working with stack limits near the physical edge of the stack.  I'll see what I can do.

> > Source/JavaScriptCore/yarr/YarrInterpreter.cpp:2416
> > +    inline bool isSafeToRecurse() { return currentStackPointer() >= m_stackLimit; }
> 
> please ASSERT(Thread::current().stack().isGrowingDownward());

I've removed isGrowingDownward() as a public method in r252177.  This is now moot.

> or maybe turn VM's isSafeToRecurse into a static public function and call
> that. (Or abstract it in WTF somewhere)

I've created a WTF::StackCheck class because I anticipate we'll want to reuse this same logic elsewhere.  It does have slightly different behavior than the VM one.  Some special properties of the VM stack checks include:
1. artificially limiting the useable stack size to a potentially smaller limit than that which is provided by the physical stack.
2. having 2 separate limits: a soft limit (with some extra space reserved to handle a JS StackOverflow error) and a hard limit.

There's a chance the VM one can be refactored to work on top of the WTF::StackCheck class, but I don't think it's worth the effort for now.  So, I'm leaving the VM one alone for now.

(In reply to Saam Barati from comment #3)
> Comment on attachment 382998 [details]
> proposed patch.
> 
> View in context:
> https://bugs.webkit.org/attachment.cgi?id=382998&action=review
> 
> > Source/JavaScriptCore/yarr/YarrInterpreter.cpp:2036
> > +        if (UNLIKELY(!isSafeToRecurse()))
> 
> does this need to be done elsewhere in the regex compiler?

The entry to ByteCompiler is via its compile() function.  I've added a stack check there.  The only other place we need this is in emitDisjunction(), which appears to be the only recursive method called from compile().  All other methods appear to be leaf methods, or may call a few functions (with shallow-ish stack usage) but will not recurse.

I'll leave the analysis of RegExp functions / methods outside of ByteCompiler as a separate exercise.
Comment 7 Mark Lam 2019-11-07 01:17:48 PST
Created attachment 383029 [details]
work in progress for EWS testing.
Comment 8 Mark Lam 2019-11-07 17:34:32 PST
Created attachment 383097 [details]
proposed patch.
Comment 9 Saam Barati 2019-11-07 18:14:19 PST
Comment on attachment 383097 [details]
proposed patch.

View in context: https://bugs.webkit.org/attachment.cgi?id=383097&action=review

> JSTests/stress/stack-overflow-in-yarr-byteCompile.js:1
> +//@ requireOptions(""--disableOptionsFreezingForTesting"")

should be one quote

> Source/JavaScriptCore/tools/JSDollarVM.cpp:2046
> +    JSFunction* function = bitwise_cast<JSFunction*>(arg0.toObject(globalObject));

jsCast

> Source/JavaScriptCore/tools/JSDollarVM.cpp:2047
> +    size_t desiredStackSize = arg1.toNumber(globalObject);

this should be calling .asNumber()
Comment 10 Mark Lam 2019-11-07 22:03:52 PST
Comment on attachment 383097 [details]
proposed patch.

View in context: https://bugs.webkit.org/attachment.cgi?id=383097&action=review

Thanks for the review.

> Source/JavaScriptCore/runtime/VM.cpp:-884
> -inline void VM::updateStackLimits()

I've opted to undo this because: 1. VM::updateStackLimits() isn't in a perf critical path anyway, and we rarely call it, 2. putting it in VMInlines.h has other complications (that caused a lot of the red EWS bots).  While the build breakage is fixable, it's not worth doing.  I can get the functionality I need simply my making it not an inline function.  I'll apply that change in the patch for landing.
Comment 11 Mark Lam 2019-11-07 22:21:55 PST
Created attachment 383111 [details]
patch for landing.
Comment 12 Mark Lam 2019-11-07 23:00:37 PST
Created attachment 383114 [details]
patch for landing.
Comment 13 Mark Lam 2019-11-08 08:59:34 PST
Landed in r252239: <http://trac.webkit.org/r252239>.
Comment 14 Yusuke Suzuki 2019-11-08 20:09:47 PST
Committed r252304: <https://trac.webkit.org/changeset/252304>