Bug 4774

Summary: Filling shapes a lot arger than window size make cairo crawl
Product: cairo Reporter: Leonard Ritter <paniq>
Component: xlib backendAssignee: Carl Worth <cworth>
Status: RESOLVED FIXED QA Contact: cairo-bugs mailing list <cairo-bugs>
Severity: normal    
Priority: high CC: sven.herzberg
Version: 1.0.2   
Hardware: x86 (IA32)   
OS: Linux (All)   
Whiteboard:
i915 platform: i915 features:

Description Leonard Ritter 2005-10-13 11:54:51 UTC
When filling a circle of radius 2400 pixels in an 640x480 output window, drawing
that circle takes over a second, although only a pixelspace of 640x480 is being
filled.

Below is a python test case demonstrating this:

------------

#!/usr/bin/env python

import cairo
import gtk
from math import pi

from time import time

class MainWindow(gtk.Window):
	def __init__(self):
		gtk.Window.__init__(self)
		self.connect('destroy', lambda x: gtk.main_quit())
		self.set_default_size(640, 480)
		self.set_position(gtk.WIN_POS_CENTER)
		
		drawingarea = gtk.DrawingArea()
		self.add(drawingarea)
		drawingarea.connect('expose_event', self.expose)
		
		self.show_all()
		
	def expose(self, da, event):
		ctx = da.window.cairo_create()
		
		##################################
		# TEST CASE BEGIN
		##################################
		ctx.set_source_rgb(0, 0, 0)
		ctx.arc(240.0,240.0,4800.0,0,2*pi)
		ctx.fill()
		##################################
		# TEST CASE END
		##################################

def main():	
	mainwindow = MainWindow()
	gtk.main()

if __name__ == "__main__":
	main()
Comment 1 Leonard Ritter 2005-10-13 11:56:19 UTC
expected is no difference to filling a rectangle from 0,0 to 640,480, relating
to time.
Comment 2 Leonard Ritter 2005-10-13 11:57:12 UTC
i believe that given far more malicious parameters, this bug could be used to
lock up a machine.
Comment 3 Leonard Ritter 2005-10-13 11:59:25 UTC
<mpj> paniq: in that case could cairo do anything better than clip to the window
bounds?
<paniq> it could triangulate the shape and clip the triangles.
Comment 4 Leonard Ritter 2005-11-04 17:45:16 UTC
still waiting for this to be fixed ;)
Comment 5 Chris Wilson 2008-10-08 05:44:34 UTC
The tesselator current discards all edges above or below the clip area - which vastly speeds up this particular test case. The final trapezoids are again adjusted to fit within the limits so no more pixels are filled than required and I do not see a significant difference between filling the large arc and just painting the window. As part of my self-intersecting work, I have implemented full-clipping of edges and this generates just a single trapezoid covering the entire window. As it stands I believe 1.8.0 does not suffer from this DoS, and I expect it to only improve in future (either through clipping of edges or Janoos' spans work).

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.