541869 - Hang [@ nsRegion::InsertInPlace] with position:fixed

Status: RESOLVED FIXED

(Core :: Graphics, defect)

Description

[Jesse Ruderman]

Attachment: testcase (hangs Firefox)

Hangs in this loop in nsRegion::InsertInPlace:

  while (aRect->y == mCurRect->prev->y && aRect->x < mCurRect->prev->x)
    mCurRect = mCurRect->prev;

In this hang, mCurRect->prev->prev == mCurRect, and it just keeps looping between the two.

Comment 1

[Jesse Ruderman]

Attachment: stack trace and some debugging info

Comment 3

[Robert O'Callahan (:roc) (email my personal email if necessary)]

Ooof. Assuming the author isn't around, we need someone to dig into the region code and figure this out. Let's try Mats :-).

Comment 4

[Dainis Jonitis]

FYI: I am still around, but I think I forgot all the details over these years good enough :) Have not compiled Mozilla since switch to mercurial.
I will also look at the code, but Mats should be able to identify problem not worse than me.

Comment 5

[Dainis Jonitis]

The idea is that rectangles in the region list are linked in the double-linked list ordered first by y and then by x coordinate of left-upper corner of rectangle. mRectListHead is special dummy head rectangle initialized to point to self when list is empty (thus saving checks for NULL next/prev pointers). 

mRectListHead.y is set to PR_INT32_MAX when you are look for smaller y values. Thus it works as a sentinel that protects infinitely wrapping around when traversing list. 

Similarly mRectListHead.y is set to PR_INT32_MIN when you are look for larger y values.

I think the problem is in fact that original code never assumed that you will insert rectangle for which any of coordinates is one of PR_INT32_MIN or PR_INT32_MAX - it was designed for OS/2 just to overcome 16bit physical pixel limitation and I have not thought that it will be used with logical 32 twips that reach min/max values of 32bit numbers. In such case setting stopping limit in mRectListHead.y will not work. 

You have to explicitly check for:

mCurRect->prev != &mRectListHead

in all while loops

Hope this helps

The

Comment 6

[Jesse Ruderman]

Attachment: testcase 2 (also hangs Firefox)

Comment 7

[Dainis Jonitis]

As it will take some time until I will be able to build Mozilla source code again, can someone post the values of mRectListHead and aRect rectangles (x, y, width, height) so I can look what is wrong in algorithm.

One possible problem is that when setting up sentinel values in mRectListHead only y is initialized with PR_INT32_MAX / PR_INT32_MIN (e.g. lines 352, 364, 377, 385). To cover all edge cases actually the same values must be set also for x coordinate.

Comment 8

[Dainis Jonitis]

After little pondering I am almost sure that also setting x sentinel values should fix the problem by preventing mCurRect being initialized with address of mRectListHead and then endlessly looping. Mats, can you please check if this will help:

line 352: Add mRectListHead.x = PR_INT32_MAX;
line 364: Add mRectListHead.x = PR_INT32_MIN;
line 377: Add mRectListHead.x = PR_INT32_MAX;
line 385: Add mRectListHead.x = PR_INT32_MIN;

Comment 9

[Mats Palmgren (inactive)]

Thanks Dainis, that's very helpful.  I agree with you suggested fixes, the
last two can be "Replace" rather than "Add" though.  I will do a review
of the rest of this file as well for similar problems.  Patch coming...

There's also the issue of why we are given an nsRect with y = PR_INT32_MIN
because that shouldn't happen, since it's outside the range
nscoord_MIN .. nscoord_MAX.  I've tracked this down to nsLayoutUtils,
I'll fix that too.

Third issue, nsRegion.cpp doesn't handle NS_COORD_IS_FLOAT, but I guess
that's known.

Comment 10

[Mats Palmgren (inactive)]

Attachment: Patch rev. 1

Fix the above three issues.  It fixes the hang for both test cases.
The NSToCoordFloorClamped changes in nsLayoutUtils fixes the out-of-range
values for the first test case.  I haven't tracked down the cause for the
second test case, but it doesn't seem worth the time fixing all of those...
assuming we'll move to using float nscoord in near future.

Comment 11

[Mats Palmgren (inactive)]

Comment on attachment 423603 [details] [diff] [review]
Patch rev. 1

Dainis, please have a look at the nsRegion changes as well if they make
sense to you.  Thanks.

Comment 12

[Dainis Jonitis]

Looks good!

Comment 13

[Robert O'Callahan (:roc) (email my personal email if necessary)]

Comment on attachment 423603 [details] [diff] [review]
Patch rev. 1

wonderful, thanks

Comment 14

[Mats Palmgren (inactive)]

http://hg.mozilla.org/mozilla-central/rev/f155f3050875
http://hg.mozilla.org/mozilla-central/rev/5f631340007c

Comment 15

[Mike Beltzner [:beltzner, not reading bugmail]]

Comment on attachment 423603 [details] [diff] [review]
Patch rev. 1

a=beltzner for 1.9.1 and 1.9.2

Comment 16

[timeless]

http://hg.mozilla.org/releases/mozilla-1.9.2/rev/39676a222968
http://hg.mozilla.org/releases/mozilla-1.9.2/rev/956e710bd1bf
http://hg.mozilla.org/releases/mozilla-1.9.1/rev/d9d8c0372d4e
http://hg.mozilla.org/releases/mozilla-1.9.1/rev/3c8ea850ffb4

Comment 17

[Al Billings [:abillings - ex-MoCo]]

Verified for 1.9.1 with Mozilla/5.0 (Windows; U; Windows NT 5.1; en-US; rv:1.9.1.9pre) Gecko/20100311 Shiretoko/3.5.9pre (.NET CLR 3.5.30729) and the first attached testcase. It no longer hangs 1.9.1. The second case doesn't hang 1.9.1 pre-patch at all.

Verified for 1.9.2 with Mozilla/5.0 (Windows; U; Windows NT 5.1; en-US; rv:1.9.2.2pre) Gecko/20100311 Namoroka/3.6.2pre (.NET CLR 3.5.30729). The second testcase doesn't hang pre-fix 1.9.2 either.