Xorg crashes drawing complex geometries

[Tim Keitt]

Binary package hint: xserver-xorg-core

I have uncovered a bug in the X server on both Gutsy and Hardy. I have been able to reproduce the bug on two different machines using three different drivers (nvidia, vesa, intel) and with two different software packages. The problem appears related to drawing large numbers of very small filled polygons. The fact that two different software packages trigger the bug and that it occurs on different machines using different video drivers suggests that the bug is deep in the X server code.

How to reproduce the crash:

Scenario 1:

1) wget http://www.keittlab.org/~tkeitt/melanesia.tgz -O- | tar zxvf -
2) qgis melanesia.shp # qgis 0.9.2-rc2 from www.qgis.org

Note that qgis is not packaged for Hardy, but I was able to run it on Gutsy (chrooted) and redirect the display to Hardy and was able to crash the X server in Hardy.

Scenario 2:

1) wget http://www.keittlab.org/~tkeitt/melanesia.tgz -O- | tar zxvf -
2) R # www.r-project.org

then in R (instruction below on setting up R)

> library(rgdal)
> x <- readOGR('melanesia.shp', 'melanesia')
> plot(x) # OK! Polygons _not_ filled
> spplot(x) # crash

This also crashes the X server. I cannot tell whether it is filling the polygons or simply using color to display the polygons that triggers the core dump.

Obviously it is rather difficult to debug the X server. I've tried several approaches, but without much insight.

Setting up R:

1) apt-get install r-base-dev
2) R

in R

install.packages('rgdal', dep = T)

[backtrace]
#0 miFillGeneralPoly (dst=0x836be60, pgc=0x8377e60, count=213031,
    ptsIn=0xb7b3601c) at ../../mi/mipolygen.c:99
 pAET = <value optimized out>
 y = <value optimized out>
 nPts = <value optimized out>
 pWETE = <value optimized out>
 pSLL = <value optimized out>
 ptsOut = <value optimized out>
 width = <value optimized out>
 FirstPoint = {{x = -8832, y = -16458}, {x = -8320, y = -16458}, {
    x = 100, y = 0}, {x = -3680, y = -16458}, {x = 256, y = 0}, {x = 256,
    y = 0}, {x = 257, y = 0}, {x = -7296, y = -16458}, {x = -7808,
    y = -16458}, {x = 256, y = 0}, {x = 100, y = 0}, {x = 27, y = 0}, {
    x = 2000, y = 0}, {x = -10560, y = -16458}, {x = 27, y = 0}, {x = 100,
    y = 0}, {x = -3256, y = -16458}, {x = 31042, y = 2076}, {x = 256, y = 0}, {
    x = -6824, y = -16458}, {x = 3072, y = 0}, {x = -3680, y = -16458}, {
    x = 0, y = 0}, {x = -11920, y = -18446}, {x = -25656, y = 2102}, {
    x = -13376, y = -18436} <repeats 31 times>, {x = -25640, y = 2102}, {
    x = -25624, y = 2102}, {x = -25608, y = 2102}, {x = -25592, y = 2102}, {
    x = -3224, y = -16458}, {x = 0, y = 0}, {x = -3244, y = -16458}, {
    x = -15351, y = -18458}, {x = -31968, y = 2078}, {x = 13257, y = 2076}, {
    x = 0, y = 0}, {x = -3244, y = -16458}, {x = 0, y = 0}, {x = -25432,
    y = 2102}, {x = -25416, y = 2102}, {x = 0, y = 0}, {x = 0, y = 0}, {x = 0,
    y = 0}, {x = 0, y = 0}, {x = -31968, y = 2078}, {x = -3192, y = -16458}, {
    x = 13588, y = 2076}, {x = -25288, y = 2102}, {x = -25272, y = 2102}, {
    x = -25256, y = 2102}, {x = 256, y = 0}, {x = 0, y = 0}, {x = -1856,
    y = -16458}, {x = -1832, y = -16458}, {x = -7136, y = -1}, {x = 14,
    y = 0}, {x = 51, y = 0}, {x = 0, y = 0}, {x = 123, y = 0}, {x = 123,
    y = 0}, {x = -1856, y = -16458}, {x = 0, y = 0}, {x = -1832, y = -16458}, {
    x = -2448, y = -16458}, {x = 256, y = 0}, {x = 0, y = 0}, {x = 16736,
    y = 2080}, {x = -4, y = -1}, {x = 0, y = 0}, {x = 0, y = 0}, {x = -7152,
    y = -1}, {x = 115, y = 0}, {x = 12870, y = 32}, {x = -2448, y = -16458}, {
    x = 123, y = 0}, {x = -3092, y = -16458}, {x = 0, y = 0}, {x = 0, y = 0}, {
    x = 895, y = -1}, {x = 32, y = -1}, {x = -1, y = -1}, {x = 12030,
    y = -18438}, {x = 115, y = 457}, {x = -7648, y = -16458}, {x = 123,
    y = 0}, {x = 0, y = 0}, {x = 0, y = 0}, {x = 0, y = 0}, {x = 18608,
    y = -3020}, {x = -6122, y = 16382}, {x = 500, y = 5849}, {x = -12351,
    y = -31531}, {x = 16387, y = 0}, {x = 0, y = 0}, {x = 0, y = 0}, {x = 0,
    y = 0}, {x = 0, y = -32768}, {x = 16383, y = 0}, {x = 0, y = 0}, {x = 0,
    y = 0}, {x = 0, y = 0}, {x = 0, y = -24576}, {x = 16386, y = 0}, {x = 0,
    y = 0}, {x = -14080, y = 16389}, {x = 32, y = 0}, {x = 895, y = 32}, {
    x = 0, y = 457}, {x = 12030, y = -18438}, {x = 115, y = 0}, {x = -7648,
    y = -16458}, {x = 123, y = 0}, {x = 8064, y = 0}, {x = -1, y = 0}, {x = 0,
    y = 0}, {x = 0, y = 0}, {x = 0, y = 0}, {x = 0, y = 0}, {x = 0,
    y = 18608}, {x = -3020, y = -6122}, {x = 16382, y = 0}, {x = 0, y = 0}, {
    x = 500, y = 5849}, {x = -12351, y = -31531}, {x = 16387, y = 0}, {x = 0,
    y = 0}, {x = 0, y = 0}, {x = 0, y = 0}, {x = 0, y = 0}, {x = 0, y = 0}, {
    x = 0, y = 0}, {x = 0, y = -32768}, {x = 16383, y = 0}, {x = 0, y = 0}, {
    x = 0, y = 0}, {x = 0, y = 0}, {x = 0, y = 0}, {x = 0, y = 0}, {x = 0,
    y = 0}, {x = 0, y = -24576}, {x = 16386, y = 0}, {x = 0, y = 0}, {x = 0,
    y = 0}, {x = 0, y = -14080}, {x = 16389, y = 0}, {x = 0,
    y = 0} <repeats 16 times>, {x = -14533, y = -18781}, {x = -2624,
    y = -16458}, {x = 18840, y = 2081}, {x = -2692, y = -16458}, {x = -13132,
    y = -18434}, {x = 15818, y = 2054}, {x = -14547, y = -18781}, {x = 0,
    y = 0}}
 FirstWidth = {524289, 917513, 0, 524289, 851977, 0, 196609, 917508, 0,
  262146, 917508, 0, 327681, 917508, 0, 327680, 851972, 0, 589824, 720906, 0,
  589825, 917514, 0, 655361, 917515, 0, 655361, 917515, 0, 655361, 917515, 0,
  655361, 917515, 0, 655361, 851979, 0, 524289, 524297, 65535, 720896, 720907,
  0, 589825, 917514, 0, 589825, 917514, 0, 589825, 917514, 0, 589825, 851978,
  0, 589824, 917513, 0, 524289, 720905, 0, 393217, 720903, 0, 524289, 720904,
  0, 524289, 720904, 0, 524289, 720904, 0, 524289, 720904, 0, 524289, 720904,
  0, 524289, 786440, 0, 786433, 524301, 0, 458753, 524296, 3, 458753, 720904,
  0, 458753, 720904, 0, 458753, 720904, 0, 458753, 720904, 0, 196609, 720899,
  0, 196609, 720899, 0, 262144, 720899, 0, 196608, 720899, 0, 458753, 720904,
  0, 458753, 720904, 0, 458753, 720904, 0, 458753, 720904, 0, 458753, 720904,
  0, 458753, 720904, 0, 458753, 720904, 0, 524289, 524297, 65535, 524288,
  524296, 0, 458753, 720904, 0, 458753, 720904, 0, 458753, 720904, 0, 458753,
  720904, 0, 458752, 720903, 3, 458753, 720904, 3, 458752, 720903, 3,
  -1078591486, -1208017767, 134623369, -1208558992, -1207963660, -1078529536,
  -1209728911, 137856748, -1208037440, 0, 6422528, 1, -1078529384, 0,
  -1078528356, -1078528360, 67127296, -1078534784, 137794904, 257, 7,
  -1548602414, 0, 0, 7, 0, 1, 1216, 742480, 3, 198, 31402076, 137856616, 0,
  256, -1, 0, -1078532704}
 pPrevAET = <value optimized out>
 ET = {ymax = -1078528272, ymin = -1208021389, scanlines = {
    scanline = 136419304, edgelist = 0x0, next = 0x1}}
 AET = {ymax = -1078527784, bres = {minor = 136039663, d = 1024,
    m = 136331616, m1 = 134573424, incr1 = -1207962008, incr2 = -1078527808},
  next = 0xffffffff, back = 0xb7ffeff4, nextWETE = 0xb6a3a16c,
  ClockWise = 136418864}
 SLLBlock = {SLLs = {{scanline = 0, edgelist = 0x8056d70, next = 0x0}, {
      scanline = 0, edgelist = 0x0, next = 0x0}, {scanline = -1207963660,
      edgelist = 0xbfb6f5c0, next = 0x8214998}, {scanline = -1078528524,
      edgelist = 0xb7fecfc0, next = 0x0}, {scanline = -1078528584,
      edgelist = 0x8136dde, next = 0x0}, {scanline = -1207980100,
      edgelist = 0xbfb6f5c0, next = 0xbfb6f6a4}, {scanline = 1430146762,
      edgelist = 0x1b, next = 0x8054100}, {scanline = 134550068,
      edgelist = 0x82156b8, next = 0x553e4eca}, {scanline = -1078528536,
      edgelist = 0xb7c4a926, next = 0x0}, {scanline = 0, edgelist = 0x1,
      next = 0x2c7}, {scanline = 0, edgelist = 0xb7fff668, next = 0xb6a3c72d},
    {scanline = 134621344, edgelist = 0xb6a3a16c, next = 0x1}, {
      scanline = -1207963660, edgelist = 0x82197e8, next = 0xbfb6f698}, {
      scanline = -1078528332, edgelist = 0xb7fed166, next = 0xb6a3a16c}, {
      scanline = -1078528360, edgelist = 0xb7fff7c4, next = 0x0}, {
      scanline = 0, edgelist = 0x1, next = 0x0}, {scanline = 1,
      edgelist = 0x0, next = 0x0}, {scanline = 0, edgelist = 0x0, next = 0x0},
    {scanline = 0, edgelist = 0x0, next = 0xbfb6f6a4}, {
      scanline = -1078528288, edgelist = 0x8219630, next = 0xb6a3c72d}, {
      scanline = 1430146762, edgelist = 0x0, next = 0x0}, {scanline = 0,
      edgelist = 0xb7e69e56, next = 0x81c40ea}, {scanline = -1078528392,
      edgelist = 0x0, next = 0x1}, {scanline = 136331616, edgelist = 0x2,
      next = 0x0}, {scanline = 1207072341, edgelist = 0x5f54e,
      next = 0x81e8320}}, next = 0x1}
 fixWAET = <value optimized out>
#1 0x0812fbd3 in miFillPolygon (dst=0x836be60, pgc=0x8377e60, shape=0,
    mode=0, count=213031, pPts=0xb7b3601c) at ../../mi/mipoly.c:127
 i = -1078528680
 xorg = 1
 yorg = <value optimized out>
#2 0xb6a57c88 in XAAFillPolygonSolid (pDraw=0x836be60, pGC=0x8377e60,
    shape=0, mode=0, count=213031, ptsIn=0xb7b3601c)
    at ../../../../hw/xfree86/xaa/xaaFillPoly.c:239
 infoRec = (XAAInfoRecPtr) 0x821fb30
 origin = <value optimized out>
 vertex1 = <value optimized out>
 vertex2 = <value optimized out>
 vertex1p = <value optimized out>
 vertex2p = <value optimized out>
 endp = <value optimized out>
 x1 = <value optimized out>
 x2 = <value optimized out>
 dx1 = <value optimized out>
 dx2 = <value optimized out>
 dy1 = <value optimized out>
 dy2 = <value optimized out>
 DX1 = <value optimized out>
 DX2 = <value optimized out>
 e1 = <value optimized out>
 e2 = <value optimized out>
 step1 = <value optimized out>
 step2 = <value optimized out>
 sign1 = <value optimized out>
 sign2 = <value optimized out>
 c = <value optimized out>
 y = <value optimized out>
 maxy = <value optimized out>
 h = <value optimized out>
 yoffset = <value optimized out>
 topPoint = <value optimized out>
#3 0x0817d671 in cwFillPolygon (pDst=0x836be60, pGC=0x8377e60, shape=0,
    mode=0, npt=213031, ppt=0xb7b3601c) at ../../../miext/cw/cw_ops.c:331
 pGCPrivate = (cwGCPtr) 0x8377f14
 dst_off_x = 0
 dst_off_y = 0
 pBackingDst = (DrawablePtr) 0x836be60
 pBackingGC = (GCPtr) 0x8377e60

[Marcel Stimberg (marcelstimberg)]

I can confirm this crash, using the OP's "scenario 2" (I needed to additionally install the libgdal1-dev package to get it running) on a notebook with intel graphics.

[Tim Keitt (tkeitt)]

Yes, you need 'apt-get install libgdal1-dev' to install 'rgdal'. Thanks for pointing that out.

I have confirmed the crash with other datasets as well. I was able to bring down X trying to plot the World Vector Shoreline data in QGIS (actually rc1 not rc2). I am trying to see if the same happens in R.

I hope someone will mark this release critical!

[Tim Keitt (tkeitt)]

Created an attachment (id=15609)
GDB backtrace

When using GIS software to plot complex filled polygons, I can consistently crash the X server. I have tried this with Ubuntu Gutsy and Hardy, and I believe it applies to earlier versions as well. I have seen this on three different machines and with three different video drivers (nvidia, vesa, intel). I am attaching a full backtrace. I can provide detailed instruction on how to trigger the bug if needed.

This is the output of X -version. I believe this applies to many recent Xorg releases.

X Window System Version 1.3.0
Release Date: 19 April 2007
X Protocol Version 11, Revision 0, Release 1.3
Build Operating System: Linux Ubuntu (xorg-server 2:1.3.0.0.dfsg-12ubuntu8.3)
Current Operating System: Linux patagonicus 2.6.22-14-generic #1 SMP Tue Dec 18 08:02:57 UTC 2007 i686
Build Date: 18 January 2008

[Tim Keitt (tkeitt)]

Here is a stack trace. I've filed a bug with Xorg.

[Tim Keitt (tkeitt)]

If you want to reproduce the bug on Ubuntu, try

wget http://www.keittlab.org/~tkeitt/melanesia.tgz -O- | tar zxvf -
apt-get install r-base-core, libgdal1-dev
sudo R

(in R)

install.packages('rgdal', dep = T)
q()

(restart R as ordinary user)

R

(in R)

library(rgdal)
x <- readOGR('melanesia.shp', 'melanesia')
plot(x) # OK!
plot(x, col = 'grey') # segfaults Xorg

[Tim Keitt (tkeitt)]

I did an experiment to see whether the segfault results from the properties of the individual polygons or instead has something to do with the scale at which the polygon is drawn. What I did was plot each polygon (filled) in the dataset separately. This did not cause X to crash. What that means is that no single polygon in the set is pathological. What I believe is happening is that some of the polygons are tiny compared to the overall geographic extent of the data. When you plot the entire dataset, some polygons are below the size of a single pixel and therefore there is nothing to fill. That I suspect may trigger the bug.

[Drf-vims (drf-vims)]

I reliably get this crash as well, using qgis-1.1.0 on a Debian Lenny with X 1.4.2. with one of my own shapefiles and the previously posted micronesia example.

I see similar reports on https://bugs.launchpad.net/ubuntu/+source/xorg-server/+bug/208899

[Bryce Harrington (bryce)]

[This is an automatic notification.]

Hi Tim,

This bug was reported against an earlier version of Ubuntu, can you
test if it still occurs on Lucid?

Please note we also provide technical support for older versions of
Ubuntu, but not in the bug tracker. Instead, to raise the issue through
normal support channels, please see:

    http://www.ubuntu.com/support

If you are the original reporter and can still reproduce the issue on
Lucid, please run the following command to refresh the report:

  apport-collect 208899

If you are not the original reporter, please file a new bug report, so
we can work with you as the original reporter instead (you can reference
bug 208899 in your report if you think it may be related):

  ubuntu-bug xorg

If by chance you can no longer reproduce the issue on Lucid or if you
feel it is no longer relevant, please mark the bug report 'Fix Released'
or 'Invalid' as appropriate, at the following URL:

  https://bugs.launchpad.net/ubuntu/+bug/208899

[Ingo Breßler (ibressler)]

Hello,

I passed by (because having some xorg difficulties recently) and tested Scenario 2 just out of curiosity on Lucid.
I don't experience the described behaviour, no crashes.

Tested the non-ubuntu nvidia driver 'nvidia-current-195.36.15' from nvidia website
but also the xorg default driver 'nv'

My hardware is a Lenovo Thinkpad T61.

$ lspci | grep -i nvidia
01:00.0 VGA compatible controller: nVidia Corporation Quadro NVS 140M (rev a1)

[Tim Keitt (tkeitt)]

That's great. I just displayed the data in QGIS and it does not crash
either in lucid. Would be interesting to check the change log for the
file with the function where the protection error was occurring.

THK

On Tue, Jun 22, 2010 at 11:56 AM, Ingo B. <email address hidden> wrote:
> Hello,
>
> I passed by (because having some xorg difficulties recently) and tested Scenario 2 just out of curiosity on Lucid.
> I don't experience the described behaviour, no crashes.
>
> Tested the non-ubuntu nvidia driver 'nvidia-current-195.36.15' from nvidia website
> but also the xorg default driver 'nv'
>
> My hardware is a Lenovo Thinkpad T61.
>
> $ lspci | grep -i nvidia
> 01:00.0 VGA compatible controller: nVidia Corporation Quadro NVS 140M (rev a1)
>
> ** Attachment added: "dpkg -l | grep -E '(xorg| r-|proj)'"
>   http://launchpadlibrarian.net/50751571/dpkg-l.txt
>
> --
> Xorg crashes drawing complex geometries
> https://bugs.launchpad.net/bugs/208899
> You received this bug notification because you are a direct subscriber
> of the bug.
>

--
Timothy H. Keitt
http://www.keittlab.org/

[Marcel Stimberg (marcelstimberg)]

This bug report is being closed due to your last comment regarding this being fixed with an update. For future reference you can manage the status of your own bugs by clicking on the current status in the yellow line and then choosing a new status in the revealed drop down box. You can learn more about bug statuses at https://wiki.ubuntu.com/Bugs/Status. Thank you again for taking the time to report this bug and helping to make Ubuntu better. Please submit any future bugs you may find.