431705 - Crash [@ nsStyleContext::Destroy] on reload with mtext and -moz-box-ordinal-group

Status: VERIFIED FIXED

(Core :: Layout, defect, P3)

Description

[Martijn Wargers (dead)]

Attachment: testcase

See testcase which crashes in current trunk build on reload.

It doesn't crash in a 2008-01-09 build, but does crash in a 2008-01-10 build:
http://bonsai.mozilla.org/cvsquery.cgi?treeid=default&module=all&branch=HEAD&branchtype=match&dir=&file=&filetype=match&who=&whotype=match&sortby=Date&hours=2&date=explicit&mindate=2008-01-09+15&maxdate=2008-01-10+07&cvsroot=%2Fcvsroot

http://crash-stats.mozilla.com/report/index/17f5d623-179f-11dd-9990-001cc45a2ce4?p=1
0  	 	@0x308e349

Stack from debug build:
 	dddddddd()	
>	gklayout.dll!nsCOMPtr<nsPresContext>::nsCOMPtr<nsPresContext>(nsPresContext * aRawPtr=0x0551d060)  Line 628	C++
 	gklayout.dll!nsStyleContext::Destroy()  Line 926	C++
 	gklayout.dll!nsStyleContext::Release()  Line 93	C++
 	gklayout.dll!nsStyleContext::~nsStyleContext()  Line 108	C++
 	gklayout.dll!nsStyleContext::`scalar deleting destructor'()  + 0xf bytes	C++
 	gklayout.dll!nsStyleContext::Destroy()  Line 930	C++
 	gklayout.dll!nsStyleContext::Release()  Line 93	C++
 	gklayout.dll!nsFrame::~nsFrame()  Line 351	C++
 	gklayout.dll!nsSplittableFrame::~nsSplittableFrame()  + 0xf bytes	C++
 	gklayout.dll!nsContainerFrame::~nsContainerFrame()  Line 82 + 0x13 bytes	C++
 	gklayout.dll!nsHTMLContainerFrame::~nsHTMLContainerFrame()  + 0xf bytes	C++
 	gklayout.dll!nsBlockFrame::~nsBlockFrame()  Line 282 + 0x1e bytes	C++
 	gklayout.dll!nsBlockFrame::`scalar deleting destructor'()  + 0xf bytes	C++
 	gklayout.dll!nsFrame::Destroy()  Line 510 + 0x24 bytes	C++
 	gklayout.dll!nsSplittableFrame::Destroy()  Line 74	C++
 	gklayout.dll!nsContainerFrame::Destroy()  Line 300	C++
 	gklayout.dll!nsBlockFrame::Destroy()  Line 314	C++
 	gklayout.dll!nsFrameList::DestroyFrames()  Line 68	C++
 	gklayout.dll!nsContainerFrame::Destroy()  Line 260	C++
 	gklayout.dll!nsBoxFrame::Destroy()  Line 963	C++
 	gklayout.dll!nsDocElementBoxFrame::Destroy()  Line 110	C++
 	gklayout.dll!nsFrameList::DestroyFrames()  Line 68	C++
 	gklayout.dll!nsContainerFrame::Destroy()  Line 260	C++
 	gklayout.dll!nsBoxFrame::Destroy()  Line 963	C++
 	gklayout.dll!nsFrameList::DestroyFrames()  Line 68	C++
 	gklayout.dll!nsContainerFrame::Destroy()  Line 260	C++
 	gklayout.dll!ViewportFrame::Destroy()  Line 69	C++
 	gklayout.dll!nsFrameManager::Destroy()  Line 284	C++
 	gklayout.dll!PresShell::Destroy()  Line 1708	C++
 	gklayout.dll!DocumentViewerImpl::Destroy()  Line 1526	C++
 	gklayout.dll!DocumentViewerImpl::Show()  Line 1848	C++
 	gklayout.dll!nsPresContext::EnsureVisible(int aUnsuppressFocus=0)  Line 1461	C++
 	gklayout.dll!PresShell::UnsuppressAndInvalidate()  Line 4316 + 0xd bytes	C++
 	gklayout.dll!PresShell::UnsuppressPainting()  Line 4365	C++
 	gklayout.dll!DocumentViewerImpl::LoadComplete(unsigned int aStatus=0)  Line 1015	C++
 	docshell.dll!nsDocShell::EndPageLoad(nsIWebProgress * aProgress=0x053b165c, nsIChannel * aChannel=0x0510d830, unsigned int aStatus=0)  Line 5069	C++
 	docshell.dll!nsWebShell::EndPageLoad(nsIWebProgress * aProgress=0x053b165c, nsIChannel * channel=0x0510d830, unsigned int aStatus=0)  Line 1016	C++
 	docshell.dll!nsDocShell::OnStateChange(nsIWebProgress * aProgress=0x053b165c, nsIRequest * aRequest=0x0510d830, unsigned int aStateFlags=131088, unsigned int aStatus=0)  Line 4974	C++
 	docshell.dll!nsDocLoader::FireOnStateChange(nsIWebProgress * aProgress=0x053b165c, nsIRequest * aRequest=0x0510d830, int aStateFlags=131088, unsigned int aStatus=0)  Line 1236	C++
 	docshell.dll!nsDocLoader::doStopDocumentLoad(nsIRequest * request=0x0510d830, unsigned int aStatus=0)  Line 869	C++
 	docshell.dll!nsDocLoader::DocLoaderIsEmpty()  Line 765	C++
 	docshell.dll!nsDocLoader::OnStopRequest(nsIRequest * aRequest=0x05553698, nsISupports * aCtxt=0x00000000, unsigned int aStatus=0)  Line 682	C++
 	necko.dll!nsLoadGroup::RemoveRequest(nsIRequest * request=0x05553698, nsISupports * ctxt=0x00000000, unsigned int aStatus=0)  Line 688 + 0x2e bytes	C++
 	gklayout.dll!nsDocument::DoUnblockOnload()  Line 5731	C++
 	gklayout.dll!nsDocument::UnblockOnload(int aFireSync=1)  Line 5679	C++
 	gklayout.dll!nsBindingManager::DoProcessAttachedQueue()  Line 963	C++
 	gklayout.dll!nsRunnableMethod<nsBindingManager>::Run()  Line 262	C++
 	xpcom_core.dll!nsThread::ProcessNextEvent(int mayWait=1, int * result=0x0012f848)  Line 511	C++
 	xpcom_core.dll!NS_ProcessNextEvent_P(nsIThread * thread=0x012b4098, int mayWait=1)  Line 227 + 0x16 bytes	C++
 	gkwidget.dll!nsBaseAppShell::Run()  Line 170 + 0xc bytes	C++
 	tkitcmps.dll!nsAppStartup::Run()  Line 181 + 0x1c bytes	C++
 	xul.dll!XRE_main(int argc=1, char * * argv=0x003ff7f0, const nsXREAppData * aAppData=0x003ffe98)  Line 3170 + 0x25 bytes	C++
 	firefox.exe!NS_internal_main(int argc=1, char * * argv=0x003ff7f0)  Line 158 + 0x12 bytes	C++
 	firefox.exe!wmain(int argc=1, unsigned short * * argv=0x003fa080)  Line 87 + 0xd bytes	C++
 	firefox.exe!__tmainCRTStartup()  Line 583 + 0x19 bytes	C
 	firefox.exe!wmainCRTStartup()  Line 403	C
 	kernel32.dll!_BaseProcessStart@4()  + 0x23 bytes

Comment 1

[Mats Palmgren (inactive)]

I got a slightly different regression range: 2008-01-08-04 -- 2008-01-09-04
http://bonsai.mozilla.org/cvsquery.cgi?treeid=default&module=all&branch=HEAD&branchtype=match&dir=&file=&filetype=match&who=&whotype=match&sortby=Date&hours=2&date=explicit&mindate=2008-01-08+03%3A00&maxdate=2008-01-09+05%3A00&cvsroot=%2Fcvsroot

It looks like bug 355548 uncovered an existing bug in reresolving
stylecontexts for special frames that was reordered by a 
-moz-box-ordinal-group.  I have a fix in my tree... more soon...

Comment 2

[Mats Palmgren (inactive)]

Attachment: Frame dumps #1

The block-in-inline situation makes us create three special frames but
the -moz-box-ordinal-group isn't propagated to all three. Then
nsBoxFrame::CheckBoxOrder() tries to sort the child list which reorders
the special frames (see the first two frame dumps).
Then nsCSSFrameConstructor::RebuildAllStyleData() is called:
http://bonsai.mozilla.org/cvsblame.cgi?file=/mozilla/layout/base/nsCSSFrameConstructor.cpp&rev=1.1473&mark=13408,13421,13430#13394
Since the style structs are deleted by EndConstruct it's essential that
ComputeStyleChangeFor() does not leave a reference to an old struct
behind, but since the special frames were reordered we do them in
the wrong order so we leave a style struct parent intact which is
later deleted.

Comment 3

[Mats Palmgren (inactive)]

Attachment: Frame dumps #2

Ok, so then I added -moz-box-ordinal-group:inherit in ua.css to make
the special frames have the same ordinal, but it turns out the current
sorting algorithm (Selection sort) isn't stable, i.e. it doesn't
maintain the relative order of frames with the same ordinal.

Comment 4

[Mats Palmgren (inactive)]

Attachment: Patch rev. 1

Patch overview:
1. add -moz-box-ordinal-group:inherit so that special frames
   have the same ordinal
2. make CheckBoxOrder() use a stable sorting alg. (I chose Strand sort)
3. to implement that it was convenient to use "struct nsFrameItems"
   from nsCSSFrameConstructor.cpp, so I moved it to nsFrameList.h.
   Note two minor changes I did: 1) the ctor assumes the frame arg
   has a null next-sibling:
http://bonsai.mozilla.org/cvsblame.cgi?file=/mozilla/layout/base/nsCSSFrameConstructor.cpp&rev=1.1473&root=/cvsroot&mark=752-755,785#733
   I removed that limitation and made it initialize 'lastChild' to
   the last frame in the list as is the invariant for this struct.
   2) I changed "!childList || (aAfter && !aAfter->GetNextSibling())" to 
      "!childList || aAfter == lastChild" which is the same thing if
       aAfter is on the list (implicit precondition for this method).
   No other changes, except the methods I added: RemoveFirstChild(),
   LastChild(),FirstChild(),IsEmpty().

Note: there is also a -moz-mathml-anonymous-block in mathml.css but
that can't end up in nsBoxFrame::CheckBoxOrder(), right?

Comment 5

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

I'd actually prefer a recursive mergesort here. It's still stable, but it's O(n log n) whereas strand sort is O(n^2) in the worst case. Also, recursive mergesort on singly-linked lists is really simple, probably simpler than what you have here.

Comment 6

[David Baron :dbaron: (⌚️UTC-4, no longer working on Mozilla)]

Mats, any chance of a new patch?

Comment 7

[Mats Palmgren (inactive)]

Attachment: crashtest.diff

Comment 8

[Mats Palmgren (inactive)]

Attachment: Patch rev. 2

Recursive mergesort does not fit linked lists very well since you need
to repeatedly iterate the list to split it in half, so I wrote a bottom-up
version instead.

Comment 9

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

Comment on attachment 329953 [details] [diff] [review]
Patch rev. 2

Make the helper functions static.

+      result = result ? SortedMerge(aState, *left, result) : *left;

Shouldn't the parameters be in the order result, *left to ensure stability?

I think it would probably be a lot simpler to just use the recursive sort --- look at Sort() in nsDisplayList.cpp --- and I don't think we care about constant-factor performance here. If we did, I think the version in nsDisplayList would still win since it has a nice already-sorted check which is going to make the common case (no box-ordinals set) O(N).

Comment 10

[Daniel Veditz [:dveditz]]

What's the status here: we've got r/sr on a patch but it hasn't landed. Do we need a new patch? just need to land this one?

Comment 11

[Mats Palmgren (inactive)]

(In reply to comment #9)
> Make the helper functions static.

Will do.

> +      result = result ? SortedMerge(aState, *left, result) : *left;
> 
> Shouldn't the parameters be in the order result, *left to ensure stability?

No, sorted[0] is the last result, ie. items from later in the list.

FYI, I wrote this code outside of Gecko in a test jig where I could
measure performance and verify correctness (including stability) with
input lists of various length, ordinal spread etc.

> nsDisplayList would still win since it has a nice already-sorted check

You might think so, but...

I gathered some statistics on the nsDisplayList input lists
(loading all Alexa Global Top 100 urls):
~90% of all calls take the "aCount < 2" early return.
The remaining lists that we actually sort:
  the average length is ~7.3
  ~70% are already fully ordered

Even with this high degree of sorted input the performance of a
recursive sort (with already-sorted check) is slightly slower than
the attached bottom-up iterative sort.

Statistics on the nsBoxFrame::CheckBoxOrder input lists
(just clicking around in the UI):
~70% of all calls take the "aCount < 2" early return.
For the remaining lists:
  the average length is ~3.3
  >99.9% are already fully ordered (and nearly all of those due to
    ordinal == DEFAULT_ORDINAL_GROUP)

Clearly, pruning already sorted lists will pay off in this case and
the patch does that.

Comment 12

[Mats Palmgren (inactive)]

(In reply to comment #10)
I'll land this one when the tree opens post beta2, with roc's nit about static.

Comment 13

[David Baron :dbaron: (⌚️UTC-4, no longer working on Mozilla)]

(In reply to comment #12)
> (In reply to comment #10)
> I'll land this one when the tree opens post beta2, with roc's nit about static.

If you add it to https://wiki.mozilla.org/MeteredCheckins according to the rules described there, the sheriff will even land it for you (although I think there's only about 12 hours of that left).

Comment 14

[Mats Palmgren (inactive)]

Made the helper functions static as suggested:
http://hg.mozilla.org/mozilla-central/rev/f7c410f03d0e

I'm holding the crashtest until Firefox 3.0.x is fixed.

-> FIXED

Comment 15

[Mats Palmgren (inactive)]

Attachment: crashtest2.diff

Now also includes the 2nd testcase from bug 467080.

Comment 16

[Daniel Veditz [:dveditz]]

(In reply to comment #14)
> I'm holding the crashtest until Firefox 3.0.x is fixed.
> 
> -> FIXED

This does not appear to have landed for 3.1, just 3.2. ugh, it's going to be murder trying to keep track of which "blocking1.9.1+" things need to have "fixed1.9.1" and which are OK without.

Comment 17

[Mats Palmgren (inactive)]

> This does not appear to have landed for 3.1, just 3.2.

Correct.  I assume the standard two day minimum baking period applies
(and explicit approval for 1.9.1 is required anyway).

Comment 18

[Martijn Wargers (dead)]

Verified fixed, using:
Mozilla/5.0 (Windows; U; Windows NT 5.1; en-US; rv:1.9.2a1pre) Gecko/20081208 Minefield/3.2a1pre

Comment 19

[Boris Zbarsky [:bzbarsky]]

This bug is blocking1.9.1+, so it doesn't need explicit approval to land on the 1.9.1 branch.

Comment 20

[Mats Palmgren (inactive)]

Thanks Boris, I see now that I misread the 2nd bullet of 1.9.1 rules at https://wiki.mozilla.org/TreeStatus

Comment 21

[Boris Zbarsky [:bzbarsky]]

I pushed http://hg.mozilla.org/releases/mozilla-1.9.1/rev/f3f47273e026 to fix this on 1.9.1.

Comment 22

[Mats Palmgren (inactive)]

Comment on attachment 329953 [details] [diff] [review]
Patch rev. 2

Low risk. No performance impact.

Comment 23

[Daniel Veditz [:dveditz]]

Comment on attachment 329953 [details] [diff] [review]
Patch rev. 2

Approved for 1.9.0.6, a=dveditz for release-drivers

Comment 24

[Mats Palmgren (inactive)]

Attachment: Additional patch, rev. 1

I see now that the last declaration became redundant between rev. 1 and 2 of
the patch above, so it can be removed:
http://mxr.mozilla.org/mozilla-central/source/layout/style/ua.css?mark=126,133,196,206#125

Comment 25

[Mats Palmgren (inactive)]

Attachment: 1.9.0 patch

This is the 1.9.0 version of the patch.  It's identical except for
layout/style/ua.css where the
  *|*::-moz-anonymous-block, *|*::-moz-anonymous-positioned-block {
rule isn't present so I'm adding it here to make it as close to
trunk/1.9.1 as possible.

Comment 26

[Mats Palmgren (inactive)]

Comment on attachment 353401 [details] [diff] [review]
Additional patch, rev. 1

http://hg.mozilla.org/mozilla-central/rev/1a08d472ccf5
http://hg.mozilla.org/releases/mozilla-1.9.1/rev/f9aa72fb3a6d

Comment 27

[Mats Palmgren (inactive)]

Comment on attachment 353403 [details] [diff] [review]
1.9.0 patch

Checked in on CVS trunk for 1.9.0.6:
mozilla/layout/style/ua.css 	3.235
mozilla/layout/xul/base/src/nsBoxFrame.cpp 	1.351

Comment 28

[Alexander Sack]

1.9 regression. probably not for 1.8 branches

Comment 29

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

Verified for 1.9.0.6 with Mozilla/5.0 (Macintosh; U; Intel Mac OS X 10.5; en-US; rv:1.9.0.6pre) Gecko/2009010504 GranParadiso/3.0.6pre.

Comment 30

[Tony Chung [:tchung]]

Verified fix on Mozilla/5.0 (Macintosh; U; Intel Mac OS X 10.5; en-US;
rv:1.9.1b3pre) Gecko/20090130 Shiretoko/3.1b3pre Ubiquity/0.1.5