306649 - SVG rectangle hangs Firefox when scaled really big

Status: RESOLVED WORKSFORME

(Core :: SVG, defect, P2)

Description

[Jesse Ruderman]

Steps to reproduce:
1. Load the testcase, which draws a rectangle transformed with scale(1e10).

Result: Firefox hangs.

With a scale of 1e5, it hangs Firefox for a few seconds. with a scale of 1e10,
it hangs Firefox for a long enough for me to give up waiting and force-quit.

Comment 1

[Jesse Ruderman]

Attachment: testcase (makes Firefox hang)

Comment 2

[tor]

This is a cairo performance issue; not sure we can generally work around it
without causing issues for some legitimate content.

Comment 3

[Carl Worth]

This is likely due to a known performance bug in the X server, (it creates an
intermediate surface large enough to rasterize all trapezoids that it is handed
rather than restricting the intermediate surface size based on the bounds of
the destination).

There's a fix for this in pixman for which a coresponding fix can be pushed
up into the X server.

But we can also fix cairo to clip the geometry it sends to the X server to
eliminate this problem.

It'd be nice to have a "send this bug to cairo's bugzilla" button. But if
nothing else, you can know that we're aware of this performance issue over
in cairo land. I'll try to make sure this ends up on the cairo ROADMAP which
we are just now starting to put together post-1.0:

    http://cairographics.org/ROADMAP

Comment 4

[tor]

Jesse reported this bug on the Mac, where we use the image backend.  Would you
happen to know what version of cairo/libpixman this fix went in for?  We're
currently running 0.5.0 on the FF-1.5 branch and 0.9.0 on trunk.

Comment 5

[tor]

To be more precise, we use the cairo quartz backend, which internally falls back
to the image backend.

Comment 6

[Carl Worth]

OK, for the image backend, the fix I described was first in the pixman 0.1.4
snapshot:

    Performance improvement
    -----------------------
    Restrict size of intermediate surface used while compositing
    trapezoids based on the bounds of the desination surface.

and first landed in CVS a few days before that:

    2005-03-04  Carl Worth  <[e-mail]>

        * src/ictrap.c (pixman_composite_trapezoids): Intersect bounds of
        trapezoids with the bounds of the destination surface before
        creating an intermediate surface.

Are you using a pixman later than that? (Cairo 0.5.0 was a couple months
later, so you "should" have upgraded pixman too, but if you did then I'm
not sure what the bug is).

Comment 7

[tor]

Just random sampling when it's hung, the problem looks like it might reside on
the cairo side rather than libpixman, with the hull having a rather large number
of vertices:

#0  0x05822340 in _cairo_slope_compare (a=0x24ba5fa8, b=0x24ba5fbc) at
/mozilla/trunk/mozilla/gfx/cairo/cairo/src/cairo-slope.c:67
#1  0x05822720 in _cairo_hull_vertex_compare (av=0x24ba5fa0, bv=0x24ba5fb4) at
/mozilla/trunk/mozilla/gfx/cairo/cairo/src/cairo-hull.c:89
#2  0x90005950 in qsort ()
#3  0x90005abc in qsort ()
#4  0x05822cb8 in _cairo_hull_compute (vertices=0x20d4b000,
num_vertices=0xbfffcefc) at
/mozilla/trunk/mozilla/gfx/cairo/cairo/src/cairo-hull.c:192
#5  0x05803c6c in _cairo_pen_add_points (pen=0xbfffcee8, point=0xbfffcf60,
num_points=4) at /mozilla/trunk/mozilla/gfx/cairo/cairo/src/cairo-pen.c:162
#6  0x05803358 in _cairo_stroker_curve_to (closure=0xbfffd08c, b=0xbfffd004,
c=0xbfffd00c, d=0xbfffd014) at
/mozilla/trunk/mozilla/gfx/cairo/cairo/src/cairo-path-stroke.c:752
#7  0x057f94cc in _cairo_path_fixed_interpret (path=0x1ce16bf8,
dir=CAIRO_DIRECTION_FORWARD, move_to=0x58029b8 <_cairo_stroker_move_to>,
line_to=0x5802a3c <_cairo_stroker_line_to>, curve_to=0x58030d8
<_cairo_stroker_curve_to>, close_path=0x58033f4 <_cairo_stroker_close_path>,
closure=0xbfffd08c) at /mozilla/trunk/mozilla/gfx/cairo/cairo/src/cairo-path.c:519
#8  0x058035f8 in _cairo_path_fixed_stroke_to_traps (path=0x1ce16bf8,
gstate=0x1ce16c20, traps=0xbfffd18c) at
/mozilla/trunk/mozilla/gfx/cairo/cairo/src/cairo-path-stroke.c:817
#9  0x057e7b24 in _cairo_gstate_stroke_extents (gstate=0x1ce16c20,
path=0x1ce16bf8, x1=0xbfffd268, y1=0xbfffd270, x2=0xbfffd278, y2=0xbfffd280) at
/mozilla/trunk/mozilla/gfx/cairo/cairo/src/cairo-gstate.c:1487
#10 0x057db140 in cairo_stroke_extents (cr=0x1ce16bf0, x1=0xbfffd268,
y1=0xbfffd270, x2=0xbfffd278, y2=0xbfffd280) at
/mozilla/trunk/mozilla/gfx/cairo/cairo/src/cairo.c:1596
(More stack frames follow...)
(gdb) f 4
#4  0x05822cb8 in _cairo_hull_compute (vertices=0x20d4b000,
num_vertices=0xbfffcefc) at
/mozilla/trunk/mozilla/gfx/cairo/cairo/src/cairo-hull.c:192
192         qsort (hull + 1, num_hull - 1,
(gdb) p *num_vertices
$2 = 2720658

Comment 8

[Carl Worth]

Ahah!

This is a new bug then. This is enormous-line-width for stroke rather than
enormous-shape-for-fill which is the performance bug fix that I referred to
above.

That's an interesting one, so I'll think for a bit on what the right fix is
for this.

Thanks for the report and the careful examination!

Comment 9

[Jesse Ruderman]

Mozilla/5.0 (Windows; U; Windows NT 5.1; en-US; rv:1.8b4) Gecko/20050901
Firefox/1.0+

The testcase hangs Firefox on my Windows machine for about 15 seconds, then
Firefox recovers.  Increasing the scale in the testcase might make it hang
longer; I haven't tried.

Comment 10

[Brian Birtles (:birtles)]

I'm seeing the same thing when testing animation. It only occurs during the
initial render (i.e. not during animation) and never in debug builds. The call
stacks I'm getting are similar, i.e. a lot of time in qsort. Although most of
them seem to come through cairo-traps rather than cairo-hull.

I'm getting it on this:

http://brian.sol1.net/svg/tests/opt-3-motion-and-idle.xhtml

which you'll notice doesn't have a large scale factor.

I'm working off the trunk and compiling with VC7. Checking out the latest
version of cairo from the trunk (1.1.1) didn't change anything.

I only get this problem occasionally, sometimes after 50 attempts and only when
I'm switching from one SVG file to the next.

I know it sounds like a different bug but I suspect it's related as the symptoms
are the same as well. It hangs for about 15s and then picks up again (but
nothing is rendered).

I'll let you know if I discover a more consistent way of reproducing it but for
now I thought the info might help.

Comment 11

[Jonathan Watt [:jwatt]]

Yikes! This testcase hangs trunk builds on Windows too! Seems like cairo still has a major performance issue on this tiny testcase.

Comment 12

[Jonathan Watt [:jwatt]]

Since performance degrades rapidly with decreasing scale, I'm wondering if in generally the root cause of this is causing cairo to do more work than it needs to in more general cases.

Comment 13

[Jonathan Watt [:jwatt]]

CC'ing vlad and pav since they know cairo too.

Comment 14

[Jonathan Watt [:jwatt]]

So the testcase only draws one rect with rounded corners, but it's scaled up massively. The problem seems to be that cairo_pen_vertices_needed returns 2720654 for just one rounded corner - with so so many vertices it's no wonder that qsort and and the hull methods chew the CPU for so long.

Clearly, with such large scaling, most of the rect is outside of the viewport/clipped area and cairo is doing way more work than it needs to. I'm not familiar enough with cairo to know how it could be made smart enough to not do that, but perhaps as a temporary measure we could put a cap on the value returned by cairo_pen_vertices_needed? Clearly computing 2720654 vertices for one curve is never going to make sense.

Any thoughts from any of you guys who are familiar with cairo?


_cairo_pen_vertices_needed(double 0.10000000000000001, double 15.000000000000000, _cairo_matrix * 0x0012e610) Line 270
_cairo_pen_init(_cairo_pen * 0x0012e218, double 15.000000000000000, double 0.10000000000000001, _cairo_matrix * 0x0012e610) Line 79
_cairo_stroker_init(cairo_stroker * 0x0012e1f0, _cairo_stroke_style * 0x06456ce8, _cairo_matrix * 0x0012e610, _cairo_matrix * 0x0012e3d0, double 0.10000000000000001, _cairo_traps * 0x0012e338) Line 180
_cairo_path_fixed_stroke_to_traps(_cairo_path_fixed * 0x062d5968, _cairo_stroke_style * 0x06456ce8, _cairo_matrix * 0x0012e610, _cairo_matrix * 0x0012e3d0, double 0.10000000000000001, _cairo_traps * 0x0012e338) Line 1145
_cairo_surface_fallback_stroke(_cairo_surface * 0x06445568, _cairo_operator CAIRO_OPERATOR_OVER, _cairo_pattern * 0x05232840, _cairo_path_fixed * 0x062d5968, _cairo_stroke_style * 0x06456ce8, _cairo_matrix * 0x0012e610, _cairo_matrix * 0x0012e3d0, double 0.10000000000000001, _cairo_antialias CAIRO_ANTIALIAS_DEFAULT) Line 837
_cairo_surface_stroke(_cairo_surface * 0x06445568, _cairo_operator CAIRO_OPERATOR_OVER, _cairo_pattern * 0x0012e67c, _cairo_path_fixed * 0x062d5968, _cairo_stroke_style * 0x06456ce8, _cairo_matrix * 0x06456da0, _cairo_matrix * 0x06456dd0, double 0.10000000000000001, _cairo_antialias CAIRO_ANTIALIAS_DEFAULT) Line 1554
_cairo_gstate_stroke(_cairo_gstate * 0x06456cd0, _cairo_path_fixed * 0x062d5968) Line 969

Comment 15

[Jonathan Watt [:jwatt]]

Sorry, that's the number of vertices for the pen, not the rounded corner of the rect. :-/

Comment 16

[Carl Worth]

(In reply to comment #14)
> So the testcase only draws one rect with rounded corners, but it's scaled up
> massively. The problem seems to be that cairo_pen_vertices_needed returns
> 2720654 for just one rounded corner - with so so many vertices it's no wonder
> that qsort and and the hull methods chew the CPU for so long.

Right, that's obviously massive overkill here.

There was a very similar performance bug in mozilla earlier, (where the line width was getting massively scaled and the cairo hull function would run forever trying to compute a pen).

For that one, it was hard to decide what limit would be reasonable to put into cairo. And we decided to put a fix into cairo to make it cap line widths at some reasonable value, (given the size of the destination window etc.).

We could do the same here, but we'll close off more problems if we can get a similar cap into cairo. It's still hard to figure out a proper value though. If someone keeps zooming in repeatedly to some curved shape, cairo should always compute a correct curve (according to the specified tolerance) and not just start drawing some non-smooth shape at some arbitrary scale.

But millions of pen vertices is always ridiculous. Maybe in a case like this it shouldn't compute a pen at all and should instead just run the trig functions to compute pen positions as neeeded when actually stroking?

-Carl

Comment 17

[Jonathan Watt [:jwatt]]

Sorry Carl, I missed your comments. Do you recall where the discussion regarding the stroke cap was (mozilla or cairo list)?

I agree that drawing some non-smooth shape is undesirable, but "hanging" is even more undesirable I'd say. ;-) I don't have the time or knowledge of cairo to change it to just "run the trig functions" I'm afraid. Would you be willing and able to look into doing that? If not, we'll just go with figuring out some reasonable cap on the number of pen vertices as the least of two evils.

Comment 18

[Jonathan Watt [:jwatt]]

Moving tracking1.9+ to blocking1.9+ and marking P2 since we can safely cap the number of pen vertices without requiring that change to be in a beta before release.

Comment 19

[Jonathan Watt [:jwatt]]

(In reply to comment #18)
> we can safely cap the number of pen vertices

Hah! I wish! In actual fact that crashes, so it's not that simple.

Comment 20

[Carl Worth]

(In reply to comment #19)
> (In reply to comment #18)
> > we can safely cap the number of pen vertices
> 
> Hah! I wish! In actual fact that crashes, so it's not that simple.

Could you provide some more detail here?

I too would think that capping the number of pen vertices would be a fairly safe change. I'm intrigued to know what I'm missing.

-Carl

Comment 21

[Jonathan Watt [:jwatt]]

I capped the number of vertices at 10,000. The crash happens inside _cairo_hull_prev_valid because _cairo_hull_eliminate_concave passes in zero to index (so it decrements into negative offsets recursively until it crashes). Stack is:

  _cairo_hull_prev_valid(cairo_hull * 0x071e2d00, int 10004, int -18231) Line 130 C
  _cairo_hull_eliminate_concave(cairo_hull * 0x071e2d00, int 10004) Line 165 C
  _cairo_hull_compute(_cairo_pen_vertex * 0x071217c0, int * 0x0012e944) Line 203 C
  _cairo_pen_add_points(_cairo_pen * 0x0012e930, _cairo_point * 0x0012ea38, int 4) Line 154 C
  _cairo_stroker_curve_to(void * 0x0012eae8, _cairo_point * 0x070d4250, _cairo_point * 0x070d4258, _cairo_point * 0x070d4260) Line 997 C
  _cairo_path_fixed_interpret(_cairo_path_fixed * 0x070d41b0, _cairo_direction CAIRO_DIRECTION_FORWARD, _cairo_status (void *, _cairo_point *)* 0x011a1000, _cairo_status (void *, _cairo_point *)* 0x011a10a0, _cairo_status (void *, _cairo_point *, _cairo_point *, _cairo_point *)* 0x011a1ea0, _cairo_status (void *)* 0x011a2360, void * 0x0012eae8) Line 524 C
  _cairo_path_fixed_stroke_to_traps(_cairo_path_fixed * 0x070d41b0, _cairo_stroke_style * 0x070d4060, _cairo_matrix * 0x070d4118, _cairo_matrix * 0x070d4148, double 0.10000000000000001, _cairo_traps * 0x0012ec00) Line 1164 C
  _cairo_gstate_stroke_extents(_cairo_gstate * 0x070d4048, _cairo_path_fixed * 0x070d41b0, double * 0x0012ecac, double * 0x0012ecbc, double * 0x0012ecb4, double * 0x0012eca4) Line 1148 C
  _moz_cairo_stroke_extents(_cairo * 0x070d4028, double * 0x0012ecac, double * 0x0012ecbc, double * 0x0012ecb4, double * 0x0012eca4) Line 2323 C

Comment 22

[Mike Schroepfer]

(In reply to comment #18)
> Moving tracking1.9+ to blocking1.9+ and marking P2 since we can safely cap the
> number of pen vertices without requiring that change to be in a beta before
> release.
> 

JWatt can you get us this fix?  Beta5 freeze comin up next week..

Comment 23

[Jonathan Watt [:jwatt]]

I certainly hope so. I've got Joost stuff that I don't think I can avoid running over my weekend, but I'll do my best.

Comment 24

[Brian Crowder]

Assigning jwatt as an owner, if for no other reason than to make this bug look less unowned.  If you can't own it, jwatt, please say so?

Comment 25

[Mike Schroepfer]

Given the age of this bug I'm going to take off the blocker list - jwatt if you get a fix together we'll definitely consider it for FF3 or beyond.

Comment 26

[Jonathan Watt [:jwatt]]

I'm not sure quite how the age of a bug has any bearing on whether it should block or not.

Anyway, I've still got three bugs I consider blockers on my list, and all three are cairo bugs. Since I'm not so quick at debugging cairo code, and the other two are actual 1.9 blockers, I don't expect to get to this one in time. Help from the cairo guys would be very gratefully received.

Comment 27

[Brian Crowder]

I think the "age" remarks are more to do with addressing whether or not the bug is a regression.

Comment 28

[Jonathan Watt [:jwatt]]

Fair enough.

Comment 29

[Carl Worth]

(In reply to comment #26)
> Anyway, I've still got three bugs I consider blockers on my list, and all three
> are cairo bugs. Since I'm not so quick at debugging cairo code, and the other
> two are actual 1.9 blockers, I don't expect to get to this one in time. Help
> from the cairo guys would be very gratefully received.

Jonathan,

What are the three bugs? We've been working on wrapping up cairo 1.6
for quite some time now, and have been asking for issues that people
want fixed for a very long time. I was under the distinct impression,
(from talking with Vladimir), that mozilla was now happy with the
state of cairo.

Can you please make sure we get the bugs you care about listed on our
roadmap. I've been keeping this up-to-date recently with everything
I've been told, so if something seems missing from this, please tell
me again:

	http://cairographics.org/roadmap

Looking back on this bug now, I do see that you had pointed out the
infinite-recursion bug of _cairo_hull_prev_valid to me earlier. I've
now added that to the cairo 1.6 roadmap.

What else do you have for me?

-Carl

Comment 30

[Jonathan Watt [:jwatt]]

Hi Carl. Actually, weird, I seem to be confused about the number - there are only two bugs. There's this one and there's the clipping issue I reported to the cairo list (bug 409227):

  http://lists.cairographics.org/archives/cairo/2008-March/thread.html#13344

That turned out to be a Windows only bug, but I think you said on IRC that part of the clipping code was obviously wrong and messy and you were going to fix it up (or something like that). I'll work on reducing a cairo regression testcase and figuring out what's really going wrong again tomorrow so your fix up won't hide the issue, but having your "fix up" patch would still be great.

Comment 31

[Carl Worth]

(In reply to comment #30)
> Hi Carl. Actually, weird, I seem to be confused about the number - there are
> only two bugs. There's this one and there's the clipping issue I reported to
> the cairo list (bug 409227):
> 
>   http://lists.cairographics.org/archives/cairo/2008-March/thread.html#13344

Thanks Jonathan,

I've put both of those issues on cairo's 1.6 roadmap now.

-Carl

Comment 32

[Vladimir Vukicevic [:vlad] [:vladv] (needinfo me, slow to respond)]

The fix for the cairo hull crash in comment #21 just went in as part of a cairo rollup.

Comment 33

[Jesse Ruderman]

WFM with the testcase in comment 1.

Mozilla/5.0 (Macintosh; U; Intel Mac OS X 10.5; en-US; rv:1.9.3a1pre) Gecko/20090823 Minefield/3.7a1pre

Comment 34

[Jesse Ruderman]

Crashtest: http://hg.mozilla.org/mozilla-central/rev/b64a7e4a35e2