Bug 13378 - miComputeWideEllipse with tall arcs (>10000 height) thrashes the server.
Summary: miComputeWideEllipse with tall arcs (>10000 height) thrashes the server.
Status: RESOLVED FIXED
Alias: None
Product: xorg
Classification: Unclassified
Component: Server/General (show other bugs)
Version: 7.3 (2007.09)
Hardware: Other All
: medium normal
Assignee: Adam Jackson
QA Contact: Xorg Project Team
URL: http://bugs.debian.org/cgi-bin/bugrep...
Whiteboard:
Keywords:
Depends on:
Blocks:
 
Reported: 2007-11-24 05:13 UTC by Brice Goglin
Modified: 2017-05-23 15:23 UTC (History)
2 users (show)

See Also:
i915 platform:
i915 features:


Attachments

Description Brice Goglin 2007-11-24 05:13:41 UTC
Bug reported 2 months ago by David Schmitt on the Debian BTS, reproduced with Xserver 1.3 and 1.4.

When using digikam's 'Aspect Ratio Crop' function, the xserver goes to 100% CPU and stops responding to input (only mouse moves, no screen refreshes, no key strokes / clicks accepted). Ctrl+Alt+F1 still works to get to a text console, although it takes a while.

He initially found the bug with the ATI driver, but he then also reproduced with the vesa driver and only a xterm and digikam running.

Even when killing digikam, the xserver doesn't recover. Killing and restarting the xserver returned the machine into a normal state.

He finally manage to get a backtrace with gdb to find out where the server was stuck:

#0  0x00000000004c0e01 in miComputeWideEllipse (lw=1, parc=0x7ffff27ad550, mustFree=<value optimized out>) at ../../mi/miarc.c:555
	spdata = (miArcSpanData *) 0x13805a0
	cent = <value optimized out>
	lruent = <value optimized out>
	k = <value optimized out>
	fakeent = {lrustamp = 28308, lw = 1, width = 295, height = 33791, spdata = 0x13805a0}
#1  0x00000000004c4549 in miArcSegment (pDraw=0x12ea530, pGC=<value optimized out>, tarc={x = 61, y = 15955, width = 295, height = 33791, angle1 = 13092, angle2 = 1}, right=0x34fb280, left=0x34fb2b0) at ../../mi/miarc.c:3368
	l = 1
	a0 = <value optimized out>
	a1 = 0
	startAngle = 13092
	endAngle = 13093
#2  0x00000000004c6804 in miPolyArc (pDraw=0x12ea530, pGC=0x2cf99c0, narcs=1, parcs=<value optimized out>) at ../../mi/miarc.c:1202
	arcData = <value optimized out>
	i = 786
	parc = <value optimized out>
	xMin = <value optimized out>
	xMax = <value optimized out>
	yMin = <value optimized out>
	yMax = <value optimized out>
	pixmapWidth = 0
	pixmapHeight = 0
	xOrg = 0
	yOrg = 0
	fTricky = 0
	pDrawTo = (DrawablePtr) 0x12ea530
	fg = 4294638335
	bg = 4294967295
	pGCTo = (GCPtr) 0x2cf99c0
	polyArcs = (miPolyArcPtr) 0x1132000
	cap = {0, 0}
	join = {0, 0}
	iphase = 0
	halfWidth = <value optimized out>
#3  0x00002ac4bbfc4967 in fbPolyArc (pDrawable=0x12ea530, pGC=0x2ac4b938cab8, narcs=1, parcs=0xec06c8) at ../../fb/fbarc.c:117
	_pPix = <value optimized out>
	dstStride = <value optimized out>
	box = {x1 = 1, y1 = 0, x2 = 0, y2 = 0}
	pPriv = <value optimized out>
	dstXoff = <value optimized out>
	x2 = <value optimized out>
	cclip = <value optimized out>
	dst = <value optimized out>
	dstBpp = <value optimized out>
	dstYoff = <value optimized out>
	y2 = <value optimized out>
	arc = <value optimized out>
#4  0x00000000005234af in damagePolyArc (pDrawable=0x12ea530, pGC=0x2cf99c0, nArcs=1, pArcs=0xec06c8) at ../../../miext/damage/damage.c:1191
	pGCPriv = (DamageGCPrivPtr) 0x2cf9aa0
	oldFuncs = (GCFuncs *) 0x7bc1e0
#5  0x000000000044b3d0 in ProcPolyArc (client=0x28007d0) at ../../dix/dispatch.c:1965
	narcs = -1187460448
	pGC = (GC *) 0x2cf99c0
	pDraw = (DrawablePtr) 0x12ea530
#6  0x000000000044e210 in Dispatch () at ../../dix/dispatch.c:502
	clientReady = <value optimized out>
	result = <value optimized out>
	client = (ClientPtr) 0x28007d0
	nready = 0
	start_tick = 432440
#7  0x0000000000436a1c in main (argc=8, argv=0x7ffff27ae198, envp=<value optimized out>) at ../../dix/main.c:452
	pScreen = <value optimized out>
	i = 1
	error = 0
	xauthfile = <value optimized out>
	alwaysCheckForInput = {0, 1}
Comment 1 Jesse Adkins 2010-12-01 18:06:15 UTC
(In reply to comment #0)
>     fakeent = {lrustamp = 28308, lw = 1, width = 295, height = 33791, spdata =
> 0x13805a0}

This is the line that stands out for me. Specifically :

height = 33791.

This results in about 21118 loops within miComputeSpans. This ends up in miComputeEllipseSpans with a K of 21118. That's 21118 loops in a VERY math intense loop.

I'm assuming the solution is to either outright reject really tall arcs based on some arbitrary number, or to check that the arc isn't bigger than the screen before applying.

Keith, I'm adding you to CC (or I should be), because you helped write the file this is in and probably know of a solution.
Comment 2 Adam Jackson 2017-05-23 15:23:23 UTC
Pretty sure this is fixed by:

commit 0d7f05ed99b71a4641415c9f26e245c3bb24a9a0
Author: Adam Jackson <ajax@redhat.com>
Date:   Wed Mar 1 16:13:59 2017 -0500

    miarc: "Cache" arc span data for dashed arcs
    
    This avoids recomputing the span data for every dash. x11perf thinks
    this is a pretty modest speedup:
    
        832919.4       840471.1 ( 1.009)   100-pixel dashed ellipse
        672353.1       680652.2 ( 1.012)   100-pixel double-dashed ellipse
         13748.9        24287.9 ( 1.767)   100-pixel wide dashed ellipse
          9236.3        21298.2 ( 2.306)   100-pixel wide double-dashed ellipse
    
    But part of the reason it's so modest there is that the arcs are
    relatively small (100 pixel diameter at line width 10, so ~6000 pixels)
    and the dashes relatively large (30 on 20 off so ~6 dashes per
    quadrant).
    
    With larger arcs and finer dashes this is much more impressive. A fairly
    trivial testcase of a single 15000x13000 arc with the default {2, 2}
    dash pattern drops from ~3500 milliseconds to 10 milliseconds.
    
    Reviewed-by: Keith Packard <keithp@keithp.com>
    Signed-off-by: Adam Jackson <ajax@redhat.com>


Use of freedesktop.org services, including Bugzilla, is subject to our Code of Conduct. How we collect and use information is described in our Privacy Policy.