Bug 42079 - SVG Large curve path segment OOM crash
Summary: SVG Large curve path segment OOM crash
Status: RESOLVED FIXED
Alias: None
Product: WebKit
Classification: Unclassified
Component: SVG (show other bugs)
Version: 528+ (Nightly build)
Hardware: PC Windows Vista
: P1 Normal
Assignee: Dirk Schulze
URL: http://code.google.com/p/chromium/iss...
Keywords:
Depends on:
Blocks:
 
Reported: 2010-07-12 07:44 PDT by Berend-Jan Wever
Modified: 2011-05-20 05:44 PDT (History)
6 users (show)

See Also:


Attachments
Repro with inline analysis (24.06 KB, text/html)
2010-07-12 08:24 PDT, Berend-Jan Wever
no flags Details
Recursive version of curveLength in PathTraversalState (4.21 KB, patch)
2010-08-11 12:27 PDT, Dirk Schulze
no flags Details | Formatted Diff | Diff
Test (653 bytes, text/html)
2010-08-11 12:29 PDT, Dirk Schulze
no flags Details
Patch (31.29 KB, patch)
2011-05-19 08:43 PDT, Dirk Schulze
no flags Details | Formatted Diff | Diff
I believe this patch is equivalent (4.93 KB, patch)
2011-05-19 09:43 PDT, Eric Seidel
no flags Details | Formatted Diff | Diff
Patch (27.64 KB, patch)
2011-05-19 10:45 PDT, Dirk Schulze
eric: review+
eric: commit-queue-
Details | Formatted Diff | Diff
Archive of layout-test-results from ec2-cr-linux-03 (1.21 MB, application/zip)
2011-05-19 11:09 PDT, WebKit Review Bot
no flags Details

Note You need to log in before you can comment on or make changes to this bug.
Description Berend-Jan Wever 2010-07-12 07:44:33 PDT
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.
Comment 1 Eric Seidel 2010-07-12 08:18:57 PDT
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.
Comment 2 Eric Seidel 2010-07-12 08:19:36 PDT
Ok, my comment above is bogus.  This has little to do with Skia.
Comment 3 Berend-Jan Wever 2010-07-12 08:24:39 PDT
Created attachment 61233 [details]
Repro with inline analysis

Repro file with inline analysis of code path that leads to OOM crash.
Comment 4 Dirk Schulze 2010-08-11 03:49:23 PDT
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
Comment 5 Dirk Schulze 2010-08-11 04:54:27 PDT
(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.
Comment 6 Dirk Schulze 2010-08-11 12:27:00 PDT
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.
Comment 7 Dirk Schulze 2010-08-11 12:29:05 PDT
Created attachment 64149 [details]
Test

same test as above, cleaned up and workable in Opera and FF.
Comment 8 Nikolas Zimmermann 2010-08-11 23:31:04 PDT
(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?
Comment 9 Dirk Schulze 2010-08-11 23:44:39 PDT
(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.
Comment 10 Dirk Schulze 2011-05-19 05:43:20 PDT
Have a patch for this issue soon by using recursion and a limited recursion depth.
Comment 11 Dirk Schulze 2011-05-19 08:43:35 PDT
Created attachment 94073 [details]
Patch
Comment 12 Eric Seidel 2011-05-19 08:47:04 PDT
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.
Comment 13 Dirk Schulze 2011-05-19 08:54:23 PDT
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.
Comment 14 Eric Seidel 2011-05-19 08:56:52 PDT
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.
Comment 15 Eric Seidel 2011-05-19 08:57:14 PDT
Why can't we just abort the loop if we go over the length limit?
Comment 16 Dirk Schulze 2011-05-19 09:05:10 PDT
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.
Comment 17 Eric Seidel 2011-05-19 09:10:22 PDT
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.
Comment 18 Eric Seidel 2011-05-19 09:12:04 PDT
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. :)
Comment 19 Eric Seidel 2011-05-19 09:13:01 PDT
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.
Comment 20 Eric Seidel 2011-05-19 09:19:53 PDT
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?
Comment 21 Eric Seidel 2011-05-19 09:43:56 PDT
Created attachment 94079 [details]
I believe this patch is equivalent
Comment 22 Dirk Schulze 2011-05-19 10:45:40 PDT
Created attachment 94088 [details]
Patch
Comment 23 Eric Seidel 2011-05-19 10:48:16 PDT
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.
Comment 24 WebKit Review Bot 2011-05-19 11:09:00 PDT
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
Comment 25 WebKit Review Bot 2011-05-19 11:09:17 PDT
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
Comment 26 Dirk Schulze 2011-05-20 01:01:46 PDT
Committed r86928: <http://trac.webkit.org/changeset/86928>
Comment 27 Ademar Reis 2011-05-20 05:44:40 PDT
Revision r86928 cherry-picked into qtwebkit-2.2 with commit 6b501ad <http://gitorious.org/webkit/qtwebkit/commit/6b501ad>