1055402 - pasting a long data uri in the location bar causes hang with certain add-on installed (regexp test with ".*" at both beginning and end against a long string hangs)

Status: RESOLVED FIXED

(Core :: JavaScript Engine, defect)

Description

[nick]

User Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10_9_4) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/36.0.1985.143 Safari/537.36

Steps to reproduce:

copy the image location from an image that's been inserted into the page as a data URI (in some cases, this will be a very long data URI)
open a new tab and paste the data uri into the location bar
hit enter


Actual results:

Firefox (Nightly 34) hangs.


Expected results:

don't hang!

if Firefox could load the URI quickly and show me the image, that'd be great. but if it's too long, then tell me so, rather than hanging/crashing the entire browser.

Comment 1

[Loic]

Do you have an example of such a data URI? (you can copy the data URI in a .txt file attached to the bug if it's too long)

Comment 2

[nick]

Attachment: A data URI representing an image, that when pasted caused the browser to crash.

I haven't tested to find the minimal case, but the attached data-uri-test.txt contains the image that caused the crash in question.

Comment 3

[Loic]

I tested with Nightly on Win 7, it doesn't hang.
Did you test with a clean profile?
https://support.mozilla.org/en-US/kb/profile-manager-create-and-remove-firefox-profiles

Comment 4

[nick]

I can confirm that it happens repeatedly on my installation (Nightly 34 on OS X 10.9.4). Is there any reason to suspect that a clean profile would make a difference?

Comment 5

[:Gijs (he/him)]

(In reply to nick from comment #4)
> I can confirm that it happens repeatedly on my installation (Nightly 34 on
> OS X 10.9.4). Is there any reason to suspect that a clean profile would make
> a difference?

The fact that other people try your testcase and can't reproduce the problem is a reasonable reason, yeah. :-)

(fwiw, I can't reproduce on OS X either)

Note that you can create a clean profile without deleting your old one, and if a clean profile helps, it might be worth figuring out why it's broken on your other one - could be an add-on, but could be a specific setting under which it's broken which we need to fix. Either way, it'd help narrow down the cause here. See the link Loic shared earlier for more details.

Comment 6

[nick]

You are of course right, and my apologies for hesitating.

It doesn't reproduce on a clean profile! And continues to reproduce on my default profile.

Any advice for steps to narrow down what in my profile is causing it to hang? Just disabling/re-enabling add-ons? Or is there any way for me to know which settings I've changed that would be worth testing?

Comment 7

[nick]

Through a little trial and error, it seems that (with my clean profile or my default profile), installing this add-on causes the hang on loading the particular data-uri in the Location Bar:
https://s3.amazonaws.com/releases.disconnect.me/icons/icons.xpi

I'll report an issue to the extension developers, but I don't actually know the root cause. Is there something Firefox should do differently to prevent this? Also, for what it's worth, the hang isn't caused by loading the URI at all (if it's loading it in the background on launch it works fine), but on navigating to the URI when pasted into the Location Bar.

Comment 8

[nick]

(In reply to nick from comment #7)
> I'll report an issue to the extension developers, but I don't actually know
> the root cause. Is there something Firefox should do differently to prevent
> this? Also, for what it's worth, the hang isn't caused by loading the URI at
> all (if it's loading it in the background on launch it works fine), but on
> navigating to the URI when pasted into the Location Bar.

If it's useful to anyone, the Github issue I've opened for the Disconnect developers: https://github.com/disconnectme/privacy-icons/issues/2

Comment 9

[:Gijs (he/him)]

This is bizarre. I can't find anything wrong with the add-on from a cursory look. I can reproduce the hang with the add-on installed. I've tried using the JS debugger and couldn't really figure out where it's getting stuck.

Now I attempted to debug the hang using xcode, and the results are weird:

1. Run Firefox, copy-paste the data: uri from the attachment: hang.
2. Run Firefox, attach xcode, copy-paste the data: uri from the attachment: no hang.
 2b. detach xcode, hit cmd-shift-refresh: hangs again.
3. Run Firefox, copy-paste the data: uri from the attachment, and wait for the hang. After some seconds, attach xcode while Firefox is hung - and Firefox magically recovers.


If I do the following:

0. install the add-on from https://disconnect.me/icons
1. install gecko profiler
2. open the page in the attachment
3 [review]. wait for a while (say, 10 seconds)
4. Attach XCode to get control over your browser back
5. Inspect the gecko profiler results

Then I see this:

http://people.mozilla.org/~bgirard/cleopatra/#report=458b0b9df473dc6e93eb7c3ffe376b8a607395f1

it seems like it's getting stuck in the SDK's page-mod module, and specifically in MatchPattern.test. That function looks like this:

http://mxr.mozilla.org/mozilla-central/source/addon-sdk/source/lib/sdk/util/match-pattern.js#75

75   test: function MatchPattern_test(urlStr) {
76     try {
77       var url = URL(urlStr);
78     }
79     catch (err) {
80       return false;
81     }
82 
83     // Test the URL against a RegExp pattern.  For compatibility with
84     // -moz-document rules, we require the RegExp to match the entire URL,
85     // so we not only test for a match, we also make sure the matched string
86     // is the entire URL string.
87     //
88     // Assuming most URLs don't match most match patterns, we call `test` for
89     // speed when determining whether or not the URL matches, then call `exec`
90     // for the small subset that match to make sure the entire URL matches.
91     //
92     if (this.regexp && this.regexp.test(urlStr) &&
93         this.regexp.exec(urlStr)[0] == urlStr)
94       return true;
95 
96     if (this.anyWebPage && /^(https?|ftp)$/.test(url.scheme))
97       return true;
98     if (this.exactURL && this.exactURL == urlStr)
99       return true;
100 
101     // Tests the urlStr against domain and check if
102     // wildcard submitted (*.domain.com), it only allows
103     // subdomains (sub.domain.com) or from the root (http://domain.com)
104     // and reject non-matching domains (otherdomain.com)
105     // bug 856913
106     if (this.domain && url.host &&
107          (url.host === this.domain ||
108           url.host.slice(-this.domain.length - 1) === "." + this.domain))
109       return true;
110     if (this.urlPrefix && 0 == urlStr.indexOf(this.urlPrefix))
111       return true;
112 
113     return false;
114   },

If I debug the JS in this function (without having XCode attached), I see it getting hit twice in the debugger (which makes sense, because the add-on registers two pagemods - one with an exactURL, and one with a regexp for google).

It seems that the second hit is on the this.regexp.test(urlStr) case, which gets hit with

/.*www\.google.*/

as the regexp. 

Turning off native regexp support or ion/baseline doesn't seem to help. However, this ends up seeming like a JS issue per the last stage of my comment... Jan, can you have a look and/or do you know someone who could have a look?

And indeed, I can reproduce the issue with the following minimal testcase:

http://jsbin.com/zexuvabewuca/1/edit

Comment 10

[:Gijs (he/him)]

(In reply to :Gijs Kruitbosch from comment #9)
> It seems that the second hit is on the this.regexp.test(urlStr) case, which
> gets hit with
> 
> /.*www\.google.*/
> 
> as the regexp. 
> 
> Turning off native regexp support or ion/baseline doesn't seem to help.
> However, this ends up seeming like a JS issue per the last stage of my
> comment... Jan, can you have a look and/or do you know someone who could
> have a look?
> 
> And indeed, I can reproduce the issue with the following minimal testcase:
> 
> http://jsbin.com/zexuvabewuca/1/edit

Now with needinfo...

Comment 11

[:Gijs (he/him)]

The simple testcase also hangs 31, but in content both there and on 34 it produces a slow script warning, whereas in chrome things simply go bust.

I still find it very curious that debugging this in xcode causes the hang to just disappear...

Comment 12

[:Gijs (he/him)]

(I've submitted a pull request for disconnect.me to use a less crazy regex)

Comment 13

[Jan de Mooij [:jandem]]

Forwarding to Brian since this is most likely in irregexp.

Comment 14

[Brian Hackett [Laid off!]]

(In reply to :Gijs Kruitbosch from comment #9)
> And indeed, I can reproduce the issue with the following minimal testcase:
> 
> http://jsbin.com/zexuvabewuca/1/edit

I can't reproduce this.  Can you give some exact instructions on what you're doing and what your system is for how to repro this with a clean profile?

Comment 15

[:Gijs (he/him)]

(In reply to Brian Hackett (:bhackett) from comment #14)
> (In reply to :Gijs Kruitbosch from comment #9)
> > And indeed, I can reproduce the issue with the following minimal testcase:
> > 
> > http://jsbin.com/zexuvabewuca/1/edit
> 
> I can't reproduce this.  Can you give some exact instructions on what you're
> doing and what your system is for how to repro this with a clean profile?

Against a home-built nightly from fx-team of earlier today, on OS X 10.9:

1) ./mach run -P
2) create the new profile
3) start with that new profile
4) dismiss the "make this your default browser" prompt
5) copy/paste the testcase link into a new tab, hit enter
6) click the button in the test frame once the tab has loaded

Expected:
the button goes back to not being active and the cursor remains a pointer cursor

Actual:
the button stays blue (active), the cursor goes into beachball mode, and eventually I get an unresponsive script warning

Comment 16

[:Gijs (he/him)]

In case this is helpful, I get a lot of warnings in the console that look like:

2014-08-26 21:48:36: basic_code_modules.cc:88: INFO: No module at 0x10fd18020

with various byte addresses (but always the same file and line number)

and one of:

2014-08-26 21:48:36: stackwalker.cc:125: INFO: Couldn't load symbols for: /Users/gkruitbosch/dev/builds/inbound-x86_64-apple-darwin13.3.0/dist/Nightly.app/Contents/MacOS/firefox|9A5349C1D0EF3F2087031621E67D6DC50

Comment 17

[Brian Hackett [Laid off!]]

OK, I was expecting an actual hang rather than the slow script dialog.  If you're getting that dialog things are working about as well as they can right now.  Since we landed a port of irregexp (v8's regexp engine) a few months ago there have been several reports of regexps taking inordinately long / forever to execute, which seems to be an issue with irregexp itself.  See bug 1012491 and bug 1015677.  It would be great if this got fixed but it's likely a problem in this upstream code base and the bug that Till filed against v8 in bug 1015677 comment 1 does not seem to be getting traction.  We could fix it ourselves but I don't know what timeframe that would have.

Comment 18

[:Gijs (he/him)]

(In reply to Brian Hackett (:bhackett) from comment #17)
> OK, I was expecting an actual hang rather than the slow script dialog.

I see. Steps similar to those at the top of comment #9 produce an actual hang:

0. on a fresh profile, install the add-on from https://disconnect.me/icons
1. copy the URL from the attachment
2 [review]. open a new tab, paste the URL, hit enter

I'm not sure why the slow script dialog doesn't show up there (max script runtime is longer for chrome, but still "only" 20 seconds for chrome, and waiting a full 2 minutes I'm still looking at a beachball. As I noted earlier, when I try to attach a debugger, the issue goes away, and the profile points at the regexp taking a long time to be matched as the culprit.

Comment 19

[Brian Hackett [Laid off!]]

OK, thanks.  I'm still not able to reproduce this but suspect it is the same issue as bug 1012491.  If we are executing the regexp while trying to show the slow script dialog, we end up hanging without ever showing the dialog.

Comment 20

[Till Schneidereit [:till]]

Attachment: shell benchmark of some variations of /*.www\.google*./

As discussed on IRC, there is an issue on our side: at the very least, we should have an ".*"-stripping optimization that doesn't only hit if the calling code is Ion-compiled. V8 has this for .test calls, but not for .exec ones.

Ideally, though, leading or trailing ".*" shouldn't cause such a substantial slowdown in the regexp engine itself.

Comment 21

[Robert Kaiser]

Hmm, I thought we already did a patch for stripping leading and trailing .* in bug 1024132, did I misunderstand that?

Comment 22

[Till Schneidereit [:till]]

(In reply to Robert Kaiser (:[e-mail]) from comment #21)
> Hmm, I thought we already did a patch for stripping leading and trailing .*
> in bug 1024132, did I misunderstand that?

IIUC, that only kicks in if the code calling the regexp is Ion-compiled. The problem is that there's lots of otherwise cold code that calls regexps that would really benefit from this optimization.

Comment 23

[Brian Hackett [Laid off!]]

Attachment: patch

This patch backs out bug 1024132 and its limited approach (which was intentional, to make for an easier uplift) and handles stripping leading/trailing .* from a regexp in a much better way.  The new mechanism makes match-only behavior an option in irregexp compilation/execution, where the RegExp only determines whether there is a match, not the matched string itself.  This is similar to the old match-only mode which YARR had, except that iirc YARR's version still determined the outer matched string.  When executing in this mode, leading and trailing .* can be stripped from RegExps, as this doesn't affect whether there is a match, and the output MatchPairs vector doesn't need to be written to either.  This speeds up our time running the PeaceKeeper stringFilter microbenchmark 10000x from 203ms to 173ms.  For this bug, it also means we will always do the .* removal on test() calls, so should avoid the reported hang.  And, finally, this simplifies the C++ code for RegExp.test a lot, which will make it easier to optimize these calls in Ion and do the test entirely in jitcode.

Comment 24

[Brian Hackett [Laid off!]]

(In reply to Till Schneidereit [:till] from comment #20)
> Created attachment 8479392 [details]
> shell benchmark of some variations of /*.www\.google*./
> 
> As discussed on IRC, there is an issue on our side: at the very least, we
> should have an ".*"-stripping optimization that doesn't only hit if the
> calling code is Ion-compiled. V8 has this for .test calls, but not for .exec
> ones.
> 
> Ideally, though, leading or trailing ".*" shouldn't cause such a substantial
> slowdown in the regexp engine itself.

Unfortunately, I think there needs to be some difference in behavior for .test vs. .exec.  The problem is that a leading .* does actually change the RegExp's semantics --- /foo/ will match the first foo in a string, but /.*foo/ will match the last --- and .exec and most other RegExp calls can't just strip out the .* without changing their behavior.  Now, I don't know why irregexp is so slow on these leading-.* RegExps in general, but understanding why and fixing it is probably a tall order.

Comment 25

[Till Schneidereit [:till]]

(In reply to Brian Hackett (:bhackett) from comment #24)
> Unfortunately, I think there needs to be some difference in behavior for
> .test vs. .exec.  The problem is that a leading .* does actually change the
> RegExp's semantics --- /foo/ will match the first foo in a string, but
> /.*foo/ will match the last [..]

Oh, of course. I guess we could strip a leading .*?, but then the question is how frequently that pattern is actually used. (It's the more efficient pattern, but most regexp users probably don't know that or don't care because things are fast enough.

Comment 26

[Jan de Mooij [:jandem]]

Comment on attachment 8485578 [details] [diff] [review]
patch

Review of attachment 8485578 [details] [diff] [review]:
-----------------------------------------------------------------

::: js/src/irregexp/RegExpMacroAssembler.cpp
@@ +84,5 @@
>      js_free(buffer_);
>  }
>  
>  RegExpCode
> +InterpretedRegExpMacroAssembler::GenerateCode(JSContext *cx, bool match_only)

Using match_only instead of matchOnly to match (no pun intended) v8 style of this file?

::: js/src/irregexp/RegExpParser.cpp
@@ +1001,5 @@
>  
>  template <typename CharT>
>  static bool
>  ParsePattern(frontend::TokenStream &ts, LifoAlloc &alloc, const CharT *chars, size_t length,
> +             bool multiline, bool match_only, RegExpCompileData *data)

Nit: matchOnly

::: js/src/jit-test/tests/basic/regexp-removed-dot-star.js
@@ -1,4 @@
> -
> -// Test that removal of leading or trailing .* from RegExp test() calls
> -// does not affect lastMatch or other RegExpStatics info.
> -

I'd prefer just keeping this jit-test.

::: js/src/vm/RegExpObject.h
@@ +113,5 @@
>  
> +    struct RegExpCompilation
> +    {
> +        HeapPtrJitCode jitCode;
> +        uint8_t *byteCode;

Nice refactoring.

Comment 27

[Brian Hackett [Laid off!]]

https://hg.mozilla.org/integration/mozilla-inbound/rev/c599b5ffe376

Comment 28

[Phil Ringnalda (:philor)]

https://hg.mozilla.org/mozilla-central/rev/c599b5ffe376

Comment 29

[Erik Corry]

If you are stripping .* at both ends for the test-only case, you don't have to test for the '.'.  You can strip a* and b* as well, or even (?:whatever)*.

However, see https://code.google.com/p/v8/issues/detail?id=3560 - V8 does this optimization, and perhaps it shouldn't.  It looks like you solved this problem by just deleting the equivalent test?!

Lots more detail about regexp hangs on https://code.google.com/p/v8/issues/detail?id=430
It would be cool to make irregexp more robust on this issue and I _may_ have time to do that soon.

Comment 30

[Brian Hackett [Laid off!]]

(In reply to Erik Corry from comment #29)
> However, see https://code.google.com/p/v8/issues/detail?id=3560 - V8 does
> this optimization, and perhaps it shouldn't.  It looks like you solved this
> problem by just deleting the equivalent test?!

The test removal in the patch was inadvertent and the final landing preserves all our tests.  Even with this optimization we handle RegExp.lastMatch consistently; when the test() occurs, we just record the last input and regexp and will reevaluate the regexp (without test() optimizations) if anyone accesses RegExp.lastMatch or the other RegExp object properties.

> Lots more detail about regexp hangs on
> https://code.google.com/p/v8/issues/detail?id=430
> It would be cool to make irregexp more robust on this issue and I _may_ have
> time to do that soon.

Thanks!