Last Comment Bug 686497 - Hang [@ _cairo_bo_point32_compare] when spellchecking large string
: Hang [@ _cairo_bo_point32_compare] when spellchecking large string
Status: RESOLVED FIXED
: hang, regression, testcase
Product: Core
Classification: Components
Component: Graphics (show other bugs)
: Trunk
: x86 Windows 7
: -- critical (vote)
: mozilla9
Assigned To: Jonathan Kew (:jfkthame)
:
Mentors:
https://bugzilla.mozilla.org/attachme...
Depends on:
Blocks: 629719
  Show dependency treegraph
 
Reported: 2011-09-13 10:48 PDT by Martijn Wargers [:mwargers] (not working for Mozilla)
Modified: 2011-09-17 02:08 PDT (History)
7 users (show)
See Also:
Crash Signature:
(edit)
QA Whiteboard:
Iteration: ---
Points: ---
Has Regression Range: ---
Has STR: ---


Attachments
log of hang (11.66 KB, text/plain)
2011-09-13 10:48 PDT, Martijn Wargers [:mwargers] (not working for Mozilla)
no flags Details
testcase with -moz-text-decoration-style: wavy; (70.78 KB, text/html)
2011-09-13 23:24 PDT, arno renevier
no flags Details
patch: call restore at each iteration (916 bytes, patch)
2011-09-14 14:26 PDT, arno renevier
no flags Details | Diff | Review
patch, pass dirtyRect to nsCSSRendering::PaintDecorationLine and use it to limit the number of waves (22.53 KB, patch)
2011-09-16 08:50 PDT, Jonathan Kew (:jfkthame)
roc: review+
Details | Diff | Review

Description Martijn Wargers [:mwargers] (not working for Mozilla) 2011-09-13 10:48:29 PDT
Created attachment 559990 [details]
log of hang

See url testcase, which is from bug 334814:
https://bugzilla.mozilla.org/attachment.cgi?id=219142 

Right-click on the the text input and click on "Check Spelling".

Result:
Hang

See hang log, that I attached from a Firefox debug build.
This is a regression from bug 629719.
Comment 1 :Ehsan Akhgari (busy, don't ask for review please) 2011-09-13 12:03:44 PDT
Can you only reproduce this on Windows?  From the log, it seems like this is a bug in Cairo...
Comment 2 arno renevier 2011-09-13 23:24:12 PDT
Created attachment 560106 [details]
testcase with -moz-text-decoration-style: wavy;

I can reproduce on linux.
Actually, painting the wavy text decorations under the mispelled words results in a drawing many small segments (nearly 500000). Then, in cairo, _cairo_bo_event_queue_sort performs a n^2 sort. It's not an infinite loop, just a really long one. Probably after a few hours, paint will be finished :)

This can be reproduced, independently of bug 629719 by setting a -moz-text-decoration-style: wavy; to a long element. I'm attaching a testcase which does not rely on spellcheck.
Comment 3 arno renevier 2011-09-14 14:25:22 PDT
For whatever reason, in this specific case, when this sort is performed, cairo still considers paths outside its clip region. That's why the bug appears even in first testcase when an important part of the string is not painted.

A first solution is therefore to not extend path outside the clip extent. But that would not fix the problem for second testcase, or for a big textarea.

Another solution is to work around the n^2 behaviour by stroking often. For example, if I call aGfxContext->Stroke() at the end of each while (pt.x < rightMost) loop, testcase (1 and 2) loads correctly without hanging Firefox. The painting of the waves takes about 120ms. But if I stroke less often, for example, every 10 loop iteration, it takes less time (about 45ms). So, there is probably a balance between calling stroke once, and hang because of the n^2 sort, and the overhead of stroking each time.
Here are the results I get on my system on testcase2:
stroking every 1 iteration : 120ms
         every 5 iterations: 60ms
              10 iterations: 45ms
              50 iterations: 40ms
             100 iterations: 33ms
             500 iterations: 43ms
            1000 iterations: 50ms
            5000 iterations: 577ms
           10000 iterations: 2300ms
But how to get a value correct on every system ?
Comment 4 arno renevier 2011-09-14 14:26:42 PDT
Created attachment 560249 [details] [diff] [review]
patch: call restore at each iteration
Comment 5 Robert O'Callahan (:roc) (Exited; email my personal email if necessary) 2011-09-15 11:49:08 PDT
I think this patch changes the rendering if the color of the wavy line was partially transparent; overlapping line ends will be drawn differently from before.

Jeff, can you say anything about comment #2 or #3? Why is cairo doing an O(N^2) sort?
Comment 6 Jonathan Kew (:jfkthame) 2011-09-15 14:54:10 PDT
I don't think it's true that cairo is doing an O(n^2) sort - it uses combsort11, which should be O(n log n). The problem is simply that the testcase ends up with an "event queue" of a couple of million cairo_bo_event_t records, and that's enough to bring the machine to its knees for a significant period.

While it's true that "flushing" the line instead of constructing the entire thing and then stroking it all at once could alter the rendering at overlapping ends, I think we could reasonably pick a number like 1000 iterations and stroke when we reach this. It's hard to imagine a real-world use case where the potential visual glitch after 1000 waves of the line would really be significant.
Comment 7 Robert O'Callahan (:roc) (Exited; email my personal email if necessary) 2011-09-16 00:20:38 PDT
True.

Another option is to pass in the dirty rect and skip path segments that we know are outside the dirty rect. There's no need to construct such a huge path.
Comment 8 Jonathan Kew (:jfkthame) 2011-09-16 08:50:14 PDT
Created attachment 560552 [details] [diff] [review]
patch, pass dirtyRect to nsCSSRendering::PaintDecorationLine and use it to limit the number of waves

Something like this, maybe? Using the dirty rect to trim the wavy underline requires propagating it down through the callers of this function, so it ends up impacting several classes, but it's probably worth doing, as the performance win in extreme cases is huge - we end up constructing a path of a few hundred segments, instead of hundreds of thousands, or even millions.

I'd like to retain the idea of stroking the wavy-line path and starting afresh if it reaches 1000 iterations, just as a safety measure. This shouldn't ever happen in "normal" cases, but I expect there may be ways to construct a diabolical testcase (perhaps using a transform, to effectively make the visible section of the text much longer) that would still run into problems, and the precautionary fix is simple and cheap.
Comment 9 Robert O'Callahan (:roc) (Exited; email my personal email if necessary) 2011-09-16 09:27:19 PDT
Comment on attachment 560552 [details] [diff] [review]
patch, pass dirtyRect to nsCSSRendering::PaintDecorationLine and use it to limit the number of waves

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

Fantastic!

::: layout/generic/nsTextFrameThebes.cpp
@@ +5030,5 @@
>        pt.x = (aFramePt.x + xOffset -
>               (mTextRun->IsRightToLeft() ? advance : 0)) / app;
>        gfxFloat width = NS_ABS(advance) / app;
> +      gfxRect dirtyRect(aDirtyRect.x / app, aDirtyRect.y / app,
> +                        aDirtyRect.width / app, aDirtyRect.height / app);

Hoist this out of the loop

::: layout/xul/base/src/nsTextBoxFrame.cpp
@@ +501,5 @@
>  
> +    gfxRect dirtyRect(presContext->AppUnitsToGfxUnits(aDirtyRect.x),
> +                      presContext->AppUnitsToGfxUnits(aDirtyRect.y),
> +                      presContext->AppUnitsToGfxUnits(aDirtyRect.width),
> +                      presContext->AppUnitsToGfxUnits(aDirtyRect.height));

presContext->AppUnitsToGfxUnits(aDirtyRect)
Comment 10 Jonathan Kew (:jfkthame) 2011-09-16 12:25:51 PDT
Pushed to -inbound, with fixes as per comment 9:
https://hg.mozilla.org/integration/mozilla-inbound/rev/1fc426aa485c
Comment 11 Ed Morley [:emorley] 2011-09-17 02:08:50 PDT
https://hg.mozilla.org/mozilla-central/rev/1fc426aa485c

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