Last Comment Bug 548495 - Eliminate sources of O(N^2) backtracking in the linebreaker.
: Eliminate sources of O(N^2) backtracking in the linebreaker.
Status: RESOLVED FIXED
: hang, perf, testcase, verified1.9.2
Product: Core
Classification: Components
Component: Layout: Text (show other bugs)
: Trunk
: x86_64 Windows 7
: -- critical (vote)
: ---
Assigned To: Boris Zbarsky [:bz] (still a bit busy)
:
:
Mentors:
http://www.securityfocus.com/data/vul...
: 550595 (view as bug list)
Depends on:
Blocks:
  Show dependency treegraph
 
Reported: 2010-02-24 22:14 PST by Kurt Seifried
Modified: 2010-03-30 11:18 PDT (History)
13 users (show)
bzbarsky: in‑testsuite?
See Also:
Crash Signature:
(edit)
QA Whiteboard:
Iteration: ---
Points: ---
Has Regression Range: ---
Has STR: ---
.2-fixed
.9-fixed


Attachments
Testcase text file (WILL HANG YOUR BROWSER) (552.83 KB, text/plain)
2010-02-25 10:54 PST, Boris Zbarsky [:bz] (still a bit busy)
no flags Details
Proposed fix (10.23 KB, patch)
2010-02-25 11:00 PST, Boris Zbarsky [:bz] (still a bit busy)
no flags Details | Diff | Splinter Review
diff -w for review (8.75 KB, patch)
2010-02-25 11:01 PST, Boris Zbarsky [:bz] (still a bit busy)
masayuki: review+
Details | Diff | Splinter Review
Said diff (1.79 KB, patch)
2010-02-26 19:25 PST, Boris Zbarsky [:bz] (still a bit busy)
masayuki: review+
Details | Diff | Splinter Review
roll-up fix for branches (10.53 KB, patch)
2010-02-26 19:59 PST, Boris Zbarsky [:bz] (still a bit busy)
dveditz: approval1.9.2.2+
dveditz: approval1.9.1.9+
Details | Diff | Splinter Review

Description Kurt Seifried 2010-02-24 22:14:09 PST
User-Agent:       Mozilla/5.0 (Windows; U; Windows NT 6.1; en-US; rv:1.9.2) Gecko/20100115 Firefox/3.6
Build Identifier: Mozilla/5.0 (Windows; U; Windows NT 6.1; en-US; rv:1.9.2) Gecko/20100115 Firefox/3.6

This was a supposed webkit dos, the file is about a half meg, no actual < or > characters, crashes Firefox 3.6 and 3.5.7 on Windows 7/XP 64 and 32 bit reliably. Turning off CSS causes it to crash slightly slower.

Reproducible: Always

Steps to Reproduce:
1. Open that file, from web server or local file, rename to .txt/,html still crashes Firefox. 
2. 
3.
Actual Results:  
Firefox crashes.

Expected Results:  
Firefox displays file.
Comment 1 Tyler Downer [:Tyler] 2010-02-25 00:07:03 PST
Well, no crash for me with Mozilla/5.0 (Windows; U; Windows NT 6.1; en-US; rv:1.9.3a2pre) Gecko/20100224 Minefield/3.7a2pre ID:20100224060607. I do get a hang, and I have to kill the process though. Please give a stacktrace. https://developer.mozilla.org/En/How_to_get_a_stacktrace_for_a_bug_report
Comment 2 Kurt Seifried 2010-02-25 00:51:24 PST
Apologies, I didn't realize using the term crash was incorrect within this context. I should have said it hangs (in my case I've let it sit for a while a few times but it never comes back, I have to kill it/etc.).
Comment 3 Ria Klaassen (not reading all bugmail) 2010-02-25 02:41:20 PST
I can confirm the hang with Mozilla/5.0 (Windows; U; Windows NT 6.0; en-US; rv:1.9.3a2pre) Gecko/20100224 Minefield/3.7a2pre

The hang is present with Firefox 3.0, 3.5. 3.6 and latest trunk, but not with Firefox 2.0. 
With Firefox 2 it breaks the lines and loads instantly.
Comment 5 Boris Zbarsky [:bz] (still a bit busy) 2010-02-25 07:50:31 PST
So just to make sure I'm reproducing this correctly....

1) I use wget to download http://www.securityfocus.com/data/vulnerabilities/exploits/38398.html to ~/test.html

2) I open ~/test.html in my web browser.

These steps work for me.  No hang.  Firefox 3.6 build on Mac.

This is not the same as the webkit steps to reproduce, which involve copying and pasting the text one sees if one loads that HTML file (which is mostly escapes) and then parsing the resulting file as HTML.  That also works for me.

So which steps are people using, and is this possibly Windows-only?
Comment 6 Simon Montagu :smontagu 2010-02-25 08:40:33 PST
I don't see the hang either with bz's STR, only when loading directly from securityfocus.com (which serves the file as text/plain), or if I download the file to a .txt file
Comment 7 Boris Zbarsky [:bz] (still a bit busy) 2010-02-25 08:58:58 PST
Aha!  That was the missing bit, ok.  Sounds like they're over-escaping (serving as text/plain _and_ html-escaping), but whatever.

I can reproduce when loading the file as text-plain.  Profile shows 100% of the time spent in ContextualAnalysis(unsigned short, unsigned short, unsigned short, ContextState&).
Comment 8 Boris Zbarsky [:bz] (still a bit busy) 2010-02-25 09:32:55 PST
14.3%	14.3%	0x11103438		dec      dword ptr [ebp-80]		Loop start[8]	
And the specific part of that function that takes up the time (sorry about the assembly; Shark's refusing to show me the source):

14.3% dec  dword ptr [ebp-80] Loop start[8]	
14.7% cmp  byte ptr [eax-2], byte 61			
0.4%  jz   _ZL18ContextualAnalysistttR12ContextState+753>			
0.0%  sub  eax, byte 2			
0.0%  mov  edx, dword ptr [ebp-80]			
56.2% test edx, edx			
14.3% jnz  <_ZL18ContextualAnalysistttR12ContextState+2008> Loop end[8]	

That jz is jumping to somewhere way before this code.
Comment 9 Boris Zbarsky [:bz] (still a bit busy) 2010-02-25 09:51:16 PST
Aha!  The relevant loop is inlined from HasCharacterAlready, with '=' as aCh (see the cmp instruction):

628   PRBool HasCharacterAlready(PRUnichar aCh) {
629     // Be careful for the index being unsigned.
630     for (PRUint32 i = mIndex; i > 0; --i) {
631       if (GetCharAt(i - 1) == aCh)
632         return PR_TRUE;
633     }
634     return PR_FALSE;
635   }

The jz is the |return PR_TRUE|.

The caller here is in ContextualAnalysis and looks like this:

723   } else if (cur == U_AMPERSAND || cur == U_SEMICOLON) {
724     // If this may be a separator of params of URL, we should break after.
725     if (!aState.UseConservativeBreaking(1) &&
726         aState.HasCharacterAlready(U_EQUAL))
727       return CLASS_CLOSE;

So every time we see an '&' or ';' we start scanning backwards from that point until we get to an '=' or to the beginning of the buffer.  In this case, there are lots of '&' and ';' but not '=', so we keep scanning back to buffer start all the time.  That makes the whole operation effectively O(N^2) in number of characters (and in particular makes the number of iterations of that loop O(N^2) in number of characters), and said number is 500,000 or so.  500,000^2 == 250,000,000,000, we and I would surprised if we can execute that loop faster than about 1ns per iteration, which gives us 250s as a lower bound for the entire operation.
Comment 10 Boris Zbarsky [:bz] (still a bit busy) 2010-02-25 09:53:28 PST
It looks like HasCharacterAlready is only called for U_EQUAL, U_SLASH, U_BACKSLASH.
Comment 11 Boris Zbarsky [:bz] (still a bit busy) 2010-02-25 10:54:31 PST
Created attachment 428951 [details]
Testcase text file (WILL HANG YOUR BROWSER)
Comment 12 Boris Zbarsky [:bz] (still a bit busy) 2010-02-25 11:00:58 PST
Created attachment 428953 [details] [diff] [review]
Proposed fix
Comment 13 Boris Zbarsky [:bz] (still a bit busy) 2010-02-25 11:01:33 PST
Created attachment 428954 [details] [diff] [review]
diff -w for review
Comment 14 Masayuki Nakano [:masayuki] (Mozilla Japan) 2010-02-25 19:37:39 PST
Comment on attachment 428954 [details] [diff] [review]
diff -w for review

Looks great, thank you for your work!
Comment 15 Boris Zbarsky [:bz] (still a bit busy) 2010-02-26 18:48:40 PST
Pushed http://hg.mozilla.org/mozilla-central/rev/c1cfc1bf7e52

Not sure how to write a test for this that will pass reliably...

Masayuki Nakano, do you think this patch is safe enough for the branches?
Comment 16 Masayuki Nakano [:masayuki] (Mozilla Japan) 2010-02-26 18:53:00 PST
(In reply to comment #15)
> Pushed http://hg.mozilla.org/mozilla-central/rev/c1cfc1bf7e52
> 
> Not sure how to write a test for this that will pass reliably...
> 
> Masayuki Nakano, do you think this patch is safe enough for the branches?

I think so, the line-breading is tested in http://mxr.mozilla.org/mozilla-central/source/layout/reftests/line-breaking/ . If all tests passed, it doesn't break most features (https://wiki.mozilla.org/Gecko:Line_Breaking)
Comment 17 Boris Zbarsky [:bz] (still a bit busy) 2010-02-26 19:08:44 PST
Er, in fact I was sure I had tested those... but I clearly hadn't.  Patch coming up to fix the issue this patch introduced due to notifying on slashes before checking for them.
Comment 18 Boris Zbarsky [:bz] (still a bit busy) 2010-02-26 19:21:22 PST
I pushed http://hg.mozilla.org/mozilla-central/rev/4e1b68ecf126 to fix that test failure.  Will attach that for review in a second.
Comment 19 Boris Zbarsky [:bz] (still a bit busy) 2010-02-26 19:25:01 PST
Created attachment 429285 [details] [diff] [review]
Said diff
Comment 20 Masayuki Nakano [:masayuki] (Mozilla Japan) 2010-02-26 19:28:29 PST
Comment on attachment 429285 [details] [diff] [review]
Said diff

thanks, and sorry for miscatch the mistake.
Comment 21 Boris Zbarsky [:bz] (still a bit busy) 2010-02-26 19:59:11 PST
Created attachment 429289 [details] [diff] [review]
roll-up fix for branches

This applies to both the 1.9.1 and 1.9.2 branches.  Should be safe (or at least passes tests!) and eliminates a possible hang.
Comment 22 Kurt Seifried 2010-03-02 16:14:53 PST
Can Mozilla please assign a CVE to this for tracking (congrats on you guys getting CNA status!).
Comment 23 Boris Zbarsky [:bz] (still a bit busy) 2010-03-02 18:33:57 PST
I'm not sure why this needs a CVE id, but ccing dveditz...
Comment 24 Kurt Seifried 2010-03-02 18:45:40 PST
Because it's a pretty effective DoS (you typically have to forcibly kill firefox, then restart it, kill it again, restart it, get the tab that shows which screens you want to load or not, uncheck the bad one, and then you're back to normal).
Comment 25 Tyler Downer [:Tyler] 2010-03-02 18:48:17 PST
That technically isn't a DoS, it's a hang. Not an exact DoS from firefox.
Comment 26 Boris Zbarsky [:bz] (still a bit busy) 2010-03-02 18:51:41 PST
I don't believe we typically assign CVEs to performance issues, though.  Anyway, dveditz is the one who'd know about that.
Comment 27 Kurt Seifried 2010-03-02 19:11:12 PST
CVE-2009-0773 crash
CVE-2009-1392 crash
CVE-2009-1827 hang
CVE-2009-1828 hang

You have in the last year (and before that as well).
Comment 28 Boris Zbarsky [:bz] (still a bit busy) 2010-03-02 19:16:55 PST
Both of those CVEs are about infinite loops.  There's no infinite loop in this bug; the browser becomes responsive after a minute or two of pegging the CPU.
Comment 29 Boris Zbarsky [:bz] (still a bit busy) 2010-03-02 19:17:33 PST
Well, more like 5-6 minutes, rather.  But definitely finite time.
Comment 30 Daniel Veditz [:dveditz] 2010-03-05 13:23:44 PST
Comment on attachment 429289 [details] [diff] [review]
roll-up fix for branches

Approved for 1.9.1.9 and 1.9.2.2, a=dveditz for release-drivers
Comment 32 Tyler Downer [:Tyler] 2010-03-06 05:38:04 PST
*** Bug 550595 has been marked as a duplicate of this bug. ***
Comment 33 Carsten Book [:Tomcat] 2010-03-22 12:49:04 PDT
verified for 1.9.2-2 with Windows 7 Mozilla/5.0 (Windows; U; Windows NT 6.1; en-US; rv:1.9.2.2) Gecko/20100316 Firefox/3.6.2 - no hang on testcase file --> verfied 1.9.2

Note You need to log in before you can comment on or make changes to this bug.