Bug 42079 – SVG Large curve path segment OOM crash

• Component: SVG
• Status: RESOLVED FIXED

[Berend-Jan Wever]

Code for determining SVG path lengths does not handle very large curves well: when calculating the length of a curve, it attempts to split up a large curve into smaller curves. Each split causes extra memory to be allocated and large curves require several splits. This can leads to OOM and a renderer crash in Chromium, but it does not appear to affect Safari.

Repro:
<script>
  var path = document.createElementNS("http://www.w3.org/2000/svg", "path");
  // Large values cause a large curve:
  var x   = -764285429.594597,  y = -4016805151.510674,
      x1  = -1.227687,          y1 = -4089196561.699610,
      x2  = -2172808631,        y2 = .990756267;
  pathSeg = path.createSVGPathSegCurvetoCubicAbs(x, y, x1 ,y1 ,x2 ,y2);
  pathSegList = path.pathSegList;
  pathSegList.insertItemBefore(pathSeg, 0);
  path.getPointAtLength();
</script>

Code:
http://trac.webkit.org/browser/trunk/WebCore/platform/graphics/PathTraversalState.cpp#L119
119	template<class CurveType>
120	static float curveLength(PathTraversalState& traversalState, CurveType curve)
121	{
122	    Vector<CurveType> curveStack;
123	    curveStack.append(curve);
124	
125	    float totalLength = 0.0f;
126	    do {
127	        float length = curve.approximateDistance();
// If the curve is large, split it and handle each part separately:
128	        if ((length - distanceLine(curve.start, curve.end)) > kPathSegmentLengthTolerance) {
129	            CurveType left, right;
130	            curve.split(left, right);
131	            curve = left;
132	            curveStack.append(right);
// If both left and right are still very large, they will get split as well, and again, and again, etc...
133	        } else {
134	            totalLength += length;
135	            if (traversalState.m_action == PathTraversalState::TraversalPointAtLength
136	             || traversalState.m_action == PathTraversalState::TraversalNormalAngleAtLength) {
137	                traversalState.m_previous = curve.start;
138	                traversalState.m_current = curve.end;
139	                if (traversalState.m_totalLength + totalLength > traversalState.m_desiredLength)
140	                    return totalLength;
141	            }
142	            curve = curveStack.last();
143	            curveStack.removeLast();
144	        }
145	    } while (!curveStack.isEmpty());
146	   
147	    return totalLength;
148	}
Luckily, we detect the OOM and crash the renderer cleanly with an int3 on line 132.

[Eric Seidel (no email)]

Sounds like something that the SKIA Seatbelt is supposed to protect against.  CoreGraphics (Safari's graphics engine) has had a bit more practice at defending itself against input like this.

[Eric Seidel (no email)]

Ok, my comment above is bogus.  This has little to do with Skia.

[Berend-Jan Wever]

Created attachment 61233 [details]
Repro with inline analysis

Repro file with inline analysis of code path that leads to OOM crash.

[Dirk Schulze]

Firefox seems to use the algorithm, but with a higher precision. The main difference is, that they use rekursive calls instead of a stack:
http://mxr.mozilla.org/mozilla-central/source/content/svg/content/src/nsSVGPathSeg.cpp#129

[Dirk Schulze]

(In reply to comment #4)
> Firefox seems to use the algorithm, but with a higher precision. The main difference is, that they use rekursive calls instead of a stack:
> http://mxr.mozilla.org/mozilla-central/source/content/svg/content/src/nsSVGPathSeg.cpp#129

Hmm. We could use the recursive version for getTotalLength or getPathSegAtLength. But I forgot, that we use this algorithm for getPointAtLength as well :-/
Firefox has another codePath for getPointAtLength and getTotalLength. Firefox flattens the Path, so that you just have moveTo's and lineTo's and goes throug all path segments one by the other and calculates the length. This is all done by cairo, except the adding of path length.

[Dirk Schulze]

Created attachment 64147 [details]
Recursive version of curveLength in PathTraversalState

Recursive version of curveLength in PathTraversalState. It avoids the stack and returns earlier, if length is reached in getPointAtLength.

The patch is for testing and not for review. Can someone test it on Skia please? I'd like to know, if the test works now, and how long it takes to get the totalLength of a path.

[Dirk Schulze]

Created attachment 64149 [details]
Test

same test as above, cleaned up and workable in Opera and FF.

[Nikolas Zimmermann]

(In reply to comment #6)
> Created an attachment (id=64147) [details]
> Recursive version of curveLength in PathTraversalState
> 
> Recursive version of curveLength in PathTraversalState. It avoids the stack and returns earlier, if length is reached in getPointAtLength.
> 
> The patch is for testing and not for review. Can someone test it on Skia please? I'd like to know, if the test works now, and how long it takes to get the totalLength of a path.

Can you explain why you want to test this on different platforms? This is cross-platform code, AFAIK?

[Dirk Schulze]

(In reply to comment #8)
> (In reply to comment #6)
> > Created an attachment (id=64147) [details] [details]
> > Recursive version of curveLength in PathTraversalState
> > 
> > Recursive version of curveLength in PathTraversalState. It avoids the stack and returns earlier, if length is reached in getPointAtLength.
> > 
> > The patch is for testing and not for review. Can someone test it on Skia please? I'd like to know, if the test works now, and how long it takes to get the totalLength of a path.
> 
> Can you explain why you want to test this on different platforms? This is cross-platform code, AFAIK?

Just on the first few.
The problem is, that we use the data of the platform path on pointAtLength as well as on getTotalLength. E.g. Cairo reduces the curve, so that the curve fits into the internal bounds of the canvas. That means we'll get different results across platforms (at least on very big shapes, like the curve in the example).
You may noticed, that for the repro test, opera and FF give different results for the length. This is the reason why.
On WebKitGtk I get the same results like FireFox, because both are using cairo as graphic engine.

[Dirk Schulze]

Have a patch for this issue soon by using recursion and a limited recursion depth.

[Dirk Schulze]

Created attachment 94073 [details]
Patch

[Eric Seidel (no email)]

Comment on attachment 94073 [details]
Patch

This seems strictly worse.  We should just limit the loop, instead of adding all the overhead of recursive calls.

[Dirk Schulze]

First it was the vector that crashed, second, it is hard to skip the current segment if you don't know how much segments are lef, it is easier to estimate this with the recursion limit. Third, I tried the same counts of segments on both versions (stack and recursion) and the recursion was faster. Something that is really subjective to messure: I think the new code is more readable. Why is the recursion more worse than the stack? You did not give arguments for your conclusion.

[Eric Seidel (no email)]

Well, recursion uses The Stack, meaning normally a manual stack will be leaner/faster.  All of the arguments for the function, including the return pointer are pushed to the stack, instead of just the CurveType which gets pushed to your manual stack.

[Eric Seidel (no email)]

Why can't we just abort the loop if we go over the length limit?

[Dirk Schulze]

Not the length of the path is the limit her, but the count of segements (splitted segments). Of course you can return earlier if the count reaches a predefined point. But your length result might be totally wriong. If you limit the splitts, by limiting the recursion depth, it is much easier to control where you limit the splitts. With your stack solution, you get very detailed results on the first half of the segment and very inaccurate results for the second half of the segment. This would be completely wrong, if the second half has a big dilation, but you have to estimate it with a simple line, because the count of segments reached the limit. The recursion would be more accurate here.

[Eric Seidel (no email)]

Lets talk on #webkit.  I think we're doing two things with this patch and I think you're commenting on one thing and I'm on another. :)

The current loop could be written as recusion (effectively using The Stack) as our stack.  But I'm not sure that your new version couldn't also be written as a tail-recursive loop with a manual stack.  I'm not sure that it matters that much, but I'm always wary of using The Stack when we don't need to.

[Eric Seidel (no email)]

Comment on attachment 94073 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=94073&action=review

> Source/WebCore/platform/graphics/PathTraversalState.cpp:177
> +    float distance = curveLength<QuadraticBezier>(*this, QuadraticBezier(m_current, newControl, newEnd), 0, kMaxRecursionDepth);

I suspect that kMaxRecursionDepth is too generic a name for this constant. :)

[Eric Seidel (no email)]

Comment on attachment 94073 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=94073&action=review

> Source/WebCore/platform/graphics/PathTraversalState.cpp:31
> +static const unsigned kMaxRecursionDepth = 20; // Maxmimum count of curveLength calls: 1.048.575

English usually uses , instead of . as a thousands delimiter.

[Eric Seidel (no email)]

Comment on attachment 94073 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=94073&action=review

> Source/WebCore/platform/graphics/PathTraversalState.cpp:35
> +    return FloatPoint((first.x() + second.x()) * 0.5f, (first.y() + second.y()) * 0.5f);

I assume this is for floating point operational speed?  Don't compilers/processors do this automagically?

[Eric Seidel (no email)]

Created attachment 94079 [details]
I believe this patch is equivalent

[Dirk Schulze]

Created attachment 94088 [details]
Patch

[Eric Seidel (no email)]

Comment on attachment 94088 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=94088&action=review

> Source/WebCore/platform/graphics/PathTraversalState.cpp:31
> +static const unsigned kCurveStackDepthLimit = 20;

This should just be local to the function, no need to have it global here.

> Source/WebCore/platform/graphics/PathTraversalState.cpp:128
> +        if ((length - distanceLine(curve.start, curve.end)) > kPathSegmentLengthTolerance && curveStack.size() < kCurveStackDepthLimit) {

If you wanted this to match your other results, I think you'll have to make this <= instead of <.

> LayoutTests/svg/custom/path-getTotalLength-on-big-segment-crash.svg:15
> +<text x="10" y="30">Test passes if it does not crash.</text>

Lets make this dumpAsText then.

[WebKit Review Bot]

Comment on attachment 94088 [details]
Patch

Attachment 94088 [details] did not pass chromium-ews (chromium-xvfb):
Output: http://queues.webkit.org/results/8719134

New failing tests:
svg/custom/path-getTotalLength-on-big-segment-crash.svg

[WebKit Review Bot]

Created attachment 94091 [details]
Archive of layout-test-results from ec2-cr-linux-03

The attached test failures were seen while running run-webkit-tests on the chromium-ews.
Bot: ec2-cr-linux-03  Port: Chromium  Platform: Linux-2.6.35-28-virtual-x86_64-with-Ubuntu-10.10-maverick

[Dirk Schulze]

Committed r86928: <http://trac.webkit.org/changeset/86928>

[Ademar Reis]

Revision r86928 cherry-picked into qtwebkit-2.2 with commit 6b501ad <http://gitorious.org/webkit/qtwebkit/commit/6b501ad>