1322537 - SVG: hang & memory exhaustion inside of mozilla::gfx::Path::EnsureFlattenedPath(), with animateMotion

Status: RESOLVED FIXED

(Core :: SVG, defect, P3)

Description

[Tyson Smith [:tsmith]]

Attachment: testcase 1 (WARNING, hangs your browser)

Comment 1

[Daniel Holbert [:dholbert]]

Attachment: backtrace during the hang

Here's a backtrace from during the hang. We're inside of gfx::FlattenBezierCurveSegment's call to gfx::SplitBezier. I know we've had death-spirals in that code in the past, from trying to approximate a curve to a certain degree of precision and requiring zillions of tiny straight lines to do so...

Comment 2

[Daniel Holbert [:dholbert]]

CC'ing Bas & Tom Klein who have worked on this Bezier-flattening code before (in bug 1134549).

Comment 3

[Daniel Holbert [:dholbert]]

Attachment: testcase 2 (using <path> & getTotalLength)

Here's a testcase with no SMIL, using the getTotalLength() API to trigger the same GFX path-flattening code.

Comment 4

[Tom Klein]

The path in testcase 2 is:

<path id="myPath" d="M8,0l69,97m45,-17592186044414A71,23 46,0,0 16382,98Q50,10 48,72T21,0Z"/>

-17592186044414 is a 14 digit number - is that supported/expected to work?  We don't want to crash even if it isn't supported of course.

Comment 5

[Tom Klein]

Attachment: testcase 3 (reduced version of testcase 2)

The reduced path

<path id="myPath" d="M45,-17592186044414A71,23 46,0,0 16382,98"/>

with just a single arc also causes a hang.

Comment 6

[Tom Klein]

Oh, that's what Grizzly is: https://en.wikipedia.org/wiki/Fuzz_testing (I guess?).  14 digits makes more sense then :-)

Comment 7

[Robert Longson [:longsonr]]

(In reply to Tom Klein from comment #4)
> The path in testcase 2 is:
> 
> <path id="myPath" d="M8,0l69,97m45,-17592186044414A71,23 46,0,0
> 16382,98Q50,10 48,72T21,0Z"/>
> 
> -17592186044414 is a 14 digit number - is that supported/expected to work? 
> We don't want to crash even if it isn't supported of course.

you can also use e notation to have numbers as large as a float will store; something around 1e38. In theory we're supposed to use doubles but that would double our memory cost.

Comment 8

[Tyson Smith [:tsmith]]

This bug is coming up quite frequently while fuzzing.

Comment 9

[Daniel Holbert [:dholbert]]

Perhaps we could set some reasonable limit on how many splits we'll let ourselves make when flattening a bezier segment?

e.g. maybe we could pick some arbitrary maximum loop count for this loop here:
  https://dxr.mozilla.org/mozilla-central/rev/6f8f10f48ace5692256efd91f011bd23054ee2ec/gfx/2d/Path.cpp#246,261
...which is large enough for accuracy in common cases, but small enough to prevent us from letting a small testcase eat up all the memory.

Comment 10

[Bas Schouten (:bas.schouten)]

(In reply to Daniel Holbert [:dholbert] from comment #9)
> Perhaps we could set some reasonable limit on how many splits we'll let
> ourselves make when flattening a bezier segment?
> 
> e.g. maybe we could pick some arbitrary maximum loop count for this loop
> here:
>  
> https://dxr.mozilla.org/mozilla-central/rev/
> 6f8f10f48ace5692256efd91f011bd23054ee2ec/gfx/2d/Path.cpp#246,261
> ...which is large enough for accuracy in common cases, but small enough to
> prevent us from letting a small testcase eat up all the memory.

That seems like a fine idea, in practice it's impossible to achieve sufficient accuracy for every conceivable curve. So this seems like a good solution.

Comment 11

[Kevin Hsieh]

Attachment: Bug 1322537 - Increase tolerance when splitting Bezier curves to prevent hang.

Review commit: https://reviewboard.mozilla.org/r/161776/diff/#index_header
See other reviews: https://reviewboard.mozilla.org/r/161776/

Comment 12

[Kevin Hsieh]

Comment on attachment 8890621 [details]
Bug 1322537 - Increase tolerance when splitting Bezier curves to prevent hang.

Review request updated; see interdiff: https://reviewboard.mozilla.org/r/161776/diff/1-2/

Comment 13

[Kevin Hsieh]

I added a little bit of code to increase the tolerance slightly (but multiplicatively) every time the loop that Daniel mentioned gets executed. Reproducing my code comment regarding this change:

    // Increase tolerance every iteration to prevent this loop from executing
    // too many times. This approximates the length of large curves more
    // roughly. In practice, aTolerance is the constant kFlatteningTolerance
    // which has value 0.0001. With this value, it takes 6,932 splits to double
    // currentTolerance (to 0.0002) and 23,028 splits to increase
    // currentTolerance by an order of magnitude (to 0.001).

With this, the test cases do not produce any noticeable hang or excessive memory usage. Hopefully this addition doesn't affect non-pathological SVG's, but maybe Bas can comment on that. I also added the first and third testcases to layout/svg/crashtests as 1322537-1.html and 1322537-2.html (skipping the second testcase since it uses the same path as the first testcase and the same API entry point as the third testcase).

Comment 14

[Daniel Holbert [:dholbert]]

Comment on attachment 8890621 [details]
Bug 1322537 - Increase tolerance when splitting Bezier curves to prevent hang.

https://reviewboard.mozilla.org/r/161776/#review167118

::: layout/svg/crashtests/1322537-2.html:11
(Diff revision 2)
> +<svg>
> +  <path id="myPath" d="M45,-17592186044414A71,23 46,0,0 16382,98"/>
> +</svg>
> +<body onload="go()">

Drive-by nit: you should put the <svg> inside of (i.e. after) the <body> here.

Comment 15

[Kevin Hsieh]

Comment on attachment 8890621 [details]
Bug 1322537 - Increase tolerance when splitting Bezier curves to prevent hang.

Review request updated; see interdiff: https://reviewboard.mozilla.org/r/161776/diff/2-3/

Comment 16

[Bas Schouten (:bas.schouten)]

Comment on attachment 8890621 [details]
Bug 1322537 - Increase tolerance when splitting Bezier curves to prevent hang.

https://reviewboard.mozilla.org/r/161776/#review167800

::: gfx/2d/Path.cpp:260
(Diff revision 3)
>     * then be approximated by a quadratic equation for which the maximum
>     * difference from a linear approximation can be much more easily determined.
>     */
>    BezierControlPoints currentCP = aControlPoints;
>  
> -  double t = 0;
> +  double t = 0, currentTolerance = aTolerance;

nit: Put this on a separate line.

::: layout/svg/crashtests/1322537-1.html:1
(Diff revision 3)
> +<svg>

I don't see this being added to the manifest file so it won't actually be run afaict :-).

Comment 17

[Kevin Hsieh]

Comment on attachment 8890621 [details]
Bug 1322537 - Increase tolerance when splitting Bezier curves to prevent hang.

Review request updated; see interdiff: https://reviewboard.mozilla.org/r/161776/diff/3-4/

Comment 18

[Daniel Holbert [:dholbert]]

This looks ready to land (review nits addressed, successful-looking try run, with new crashtests definitely running in the try run [which I verified by inspecting crashtest log])

 --> triggered autoland.

Comment 19

[Pulsebot]

Pushed by [e-mail]:
https://hg.mozilla.org/integration/autoland/rev/6df0dd7948ad
Increase tolerance when splitting Bezier curves to prevent hang. r=bas

Comment 20

[Sebastian Hengst [:aryx] (needinfo me if it's about an intermittent or backout)]

https://hg.mozilla.org/mozilla-central/rev/6df0dd7948ad