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.
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.
Ok, my comment above is bogus. This has little to do with Skia.
Created attachment 61233 [details] Repro with inline analysis Repro file with inline analysis of code path that leads to OOM crash.
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
(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.
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.
Created attachment 64149 [details] Test same test as above, cleaned up and workable in Opera and FF.
(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?
(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.
Have a patch for this issue soon by using recursion and a limited recursion depth.
Created attachment 94073 [details] Patch
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.
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.
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.
Why can't we just abort the loop if we go over the length limit?
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.
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 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 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 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?
Created attachment 94079 [details] I believe this patch is equivalent
Created attachment 94088 [details] Patch
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 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
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
Committed r86928: <http://trac.webkit.org/changeset/86928>
Revision r86928 cherry-picked into qtwebkit-2.2 with commit 6b501ad <http://gitorious.org/webkit/qtwebkit/commit/6b501ad>