79866 - Segfault when flight availability checked

Status: VERIFIED FIXED

(Core :: CSS Parsing and Computation, defect, P1)

Description

[John Hayward-Warburton]

Select valid flight dates and destination, click "check availability and book",
browser segfaults. Before crashing, it says:

Error loading URL javascript:submitForm() : 2152398850

Also, the menu at the top left looks severely damaged.

This on build pulled at 1830 GMT today, 9th May.

Comment 1

[Tuukka Tolvanen (sp3000)]

Crashes on win98 too, 0.9 or 2001-05-08-17-trunk.
Talkback id TB30228147H.

Comment 2

[Asa Dotzler [:asa]]

DoDeletingFrameSubtree  
[d:\builds\seamonkey\mozilla\layout\html\style\src\nsCSSFrameConstructor.cpp,
line 8847]         DoDeletingFrameSubtree  
[d:\builds\seamonkey\mozilla\layout\html\style\src\nsCSSFrameConstructor.cpp,
line 8888]         DoDeletingFrameSubtree  
[d:\builds\seamonkey\mozilla\layout\html\style\src\nsCSSFrameConstructor.cpp,
line 8888]         DoDeletingFrameSubtree  
[d:\builds\seamonkey\mozilla\layout\html\style\src\nsCSSFrameConstructor.cpp,
line 8888]         DoDeletingFrameSubtree  
[d:\builds\seamonkey\mozilla\layout\html\style\src\nsCSSFrameConstructor.cpp,
line 8888]         DoDeletingFrameSubtree  
[d:\builds\seamonkey\mozilla\layout\html\style\src\nsCSSFrameConstructor.cpp,
line 8888]         DoDeletingFrameSubtree  
[d:\builds\seamonkey\mozilla\layout\html\style\src\nsCSSFrameConstructor.cpp,
line 8888]
DeletingFrameSubtree  
[d:\builds\seamonkey\mozilla\layout\html\style\src\nsCSSFrameConstructor.cpp,
line 8929]
nsCSSFrameConstructor::ContentRemoved  
[d:\builds\seamonkey\mozilla\layout\html\style\src\nsCSSFrameConstructor.cpp,
line 9170]
nsCSSFrameConstructor::ContentReplaced  
[d:\builds\seamonkey\mozilla\layout\html\style\src\nsCSSFrameConstructor.cpp,
line 8772]
nsCSSFrameConstructor::WipeContainingBlock  
[d:\builds\seamonkey\mozilla\layout\html\style\src\nsCSSFrameConstructor.cpp,
line 12901]
nsCSSFrameConstructor::ContentAppended  
[d:\builds\seamonkey\mozilla\layout\html\style\src\nsCSSFrameConstructor.cpp,
line 8187]
StyleSetImpl::ContentAppended  
[d:\builds\seamonkey\mozilla\content\base\src\nsStyleSet.cpp, line 1241]
PresShell::ContentAppended  
[d:\builds\seamonkey\mozilla\layout\html\base\src\nsPresShell.cpp, line 4725]
nsDocument::ContentAppended  
[d:\builds\seamonkey\mozilla\content\base\src\nsDocument.cpp, line 1535]
nsHTMLDocument::ContentAppended  
[d:\builds\seamonkey\mozilla\content\html\document\src\nsHTMLDocument.cpp, line
1272]
HTMLContentSink::NotifyAppend   [d:\builds\sea
monkey\mozilla\content\html\document\src\nsHTMLContentSink.cpp, line 4458]
SinkContext::CloseContainer  
[d:\builds\seamonkey\mozilla\content\html\document\src\nsHTMLContentSink.cpp,
line 1532]
HTMLContentSink::CloseContainer  
[d:\builds\seamonkey\mozilla\content\html\document\src\nsHTMLContentSink.cpp,
line 3202]
CNavDTD::CloseContainer  
[d:\builds\seamonkey\mozilla\htmlparser\src\CNavDTD.cpp, line 3525]
CNavDTD::CloseContainersTo  
[d:\builds\seamonkey\mozilla\htmlparser\src\CNavDTD.cpp, line 3557]
CNavDTD::CloseContainersTo  
[d:\builds\seamonkey\mozilla\htmlparser\src\CNavDTD.cpp, line 3740]
CNavDTD::DidBuildModel  
[d:\builds\seamonkey\mozilla\htmlparser\src\CNavDTD.cpp, line 614]
nsParser::DidBuildModel  
[d:\builds\seamonkey\mozilla\htmlparser\src\nsParser.cpp, line 1430]
nsParser::ResumeParse  
[d:\builds\seamonkey\mozilla\htmlparser\src\nsParser.cpp, line 1910]
nsParser::ContinueParsing  
[d:\builds\seamonkey\mozilla\htmlparser\src\nsParser.cpp, line 1530]
CSSLoaderImpl::Cleanup  
[d:\builds\seamonkey\mozilla\content\html\style\src\nsCSSLoader.cpp, line 709]
CSSLoaderImpl::SheetComplete  
[d:\builds\seamonkey\mozilla\content\html\style\src\nsCSSLoader.cpp, line 833]
CSSLoaderImpl::ParseSheet  
[d:\builds\seamonkey\mozilla\content\html\style\src\nsCSSLoader.cpp, line 868]
CSSLoaderImpl::DidLoadStyle  
[d:\builds\seamonkey\mozilla\content\html\style\src\nsCSSLoader.cpp, line 904]
SheetLoadData::OnStreamComplete  
[d:\builds\seamonkey\mozilla\content\html\style\src\nsCSSLoader.cpp, line 647]
nsStreamLoader::OnStopRequest  
[d:\builds\seamonkey\mozilla\netwerk\base\src\nsStreamLoader.cpp, line 122]
nsHTTPFinalListener::OnStopRequest  
[d:\builds\seamonkey\mozilla\netwerk\protocol\http\src\nsHTTPResponseListener.cpp,
line 1139]
nsStreamListenerTee::OnStopRequest  
[d:\builds\seamonkey\mozilla\netwerk\base\src\nsStreamListenerTee.cpp, line 25]
nsHTTPChannel::Respon
seCompleted  
[d:\builds\seamonkey\mozilla\netwerk\protocol\http\src\nsHTTPChannel.cpp, line 2356]
nsHTTPServerListener::OnStopRequest  
[d:\builds\seamonkey\mozilla\netwerk\protocol\http\src\nsHTTPResponseListener.cpp,
line 709]
nsOnStopRequestEvent::HandleEvent  
[d:\builds\seamonkey\mozilla\netwerk\base\src\nsRequestObserverProxy.cpp, line 159]
PL_HandleEvent   [d:\builds\seamonkey\mozilla\xpcom\threads\plevent.c, line 589]
PL_ProcessPendingEvents   [d:\builds\seamonkey\mozilla\xpcom\threads\plevent.c,
line 522]
_md_EventReceiverProc   [d:\builds\seamonkey\mozilla\xpcom\threads\plevent.c,
line 1070]
KERNEL32.DLL + 0x242e7 (0xbff942e7)
    0x00688b5a

Comment 3

[karnaze (gone)]

The url appears to be invalid. Marking invalid.

Comment 4

[John Hayward-Warburton]

URL had one too many http:// in it. Reopening - still crashes my browser (CVS on
Linux pulled early hours of 24th May).

Comment 5

[karnaze (gone)]

I'm not getting a crash on Win2K. Reassigning to waterson and moving to m0.9.2.

Comment 6

[John Hayward-Warburton]

Still segfaults on Linux CVS pulled on 3rd June. Don't forget to try to look up
the flight: the page, on its own, doesn't segfault.

Comment 7

[Chris Waterson]

Attachment: style sheet for minimized test case

Comment 8

[Chris Waterson]

Attachment: minimized test case

Comment 9

[Chris Waterson]

This is a righteous bug. It involves an absolutely positioned element within a
floated table inside an inline (for some {ib} love), with an external style
sheet loaded via <link> and  a form. Note that the table-containing-inline isn't
properly closed, so some parser-fu kicks in.

And I thought only Hixie could think up twisted stuff like this.

Comment 10

[Chris Waterson]

Attachment: simpler test case; no table, no form

Comment 11

[Chris Waterson]

Here is the frame model that's been constructed immediately before the crash
with the ``simpler test case'' (whitespace has been stripped):

Area(html)(-1)@02A182E0 <
  line 0118E04C: <
    Block(body)(1)@0118DDE8 <
      line 0118E754: <
        Inline(span)(0)@0118E2FC <
          Placeholder(div)(0)@0118E654 outOfFlowFrame=Area(div)(0)@0118E210
        >
      >
      Floater-list<
        Area(div)(0)@0118E210 <
          line 0118E62C: <
            Placeholder(div)(2)@029BADB8 outOfFlowFrame=Area(div)(2)@0118E548
          >
        >
      >
    >
  >
  Absolute-list<
    Area(div)(2)@0118E548 <
    >
  >
>

The problem that I'm seeing is that we're doing a WipeContainingBlock() when we
append the last <div> frame to the <body>. This causes us to remove the <body>'s
frame from the frame model, which is where we crash.

The crash occurs because we're calling DoDeletingFrameSubtree() twich on the
absolutely-positioned <div>. The second time we call it, it's been destroyed and
we bomb.

My first inclination would be to patch it as follows: simply move the
DoDeletingFrameSubtree() recursion under the protection of |!IsAncestorFrame()|.
(I'll attach a patch.) I'm gonna think about this for a bit longer though.

Comment 12

[Chris Waterson]

Attachment: only recursively |DoDeletingFrameSubtree()| when |!IsAncestorFrame()|

Comment 13

[Chris Waterson]

Attachment: click-to-crash test case that avoids weird {ib} logic

Comment 14

[Chris Waterson]

(Oops, you'll need to remove all the whitespace from the click-to-creash test case.)

Comment 15

[Hixie (not reading bugmail)]

Waterson: Hey now, they didn't do this on purpose, I'm sure. Now me, I do. ;-)

Comment 16

[Chris Waterson]

Okay, I actually think that I've convinced myself that the right thing to do
here is to revert r1.265 of nsCSSFrameConstructor.cpp. Here are the CVS comments
of that revision:

  Patch from [e-mail] r=[e-mail]
  Part of a fix for crash when expanding/collapsing toolbars. Change to
  DeletingFrameSubtree() to make sure it examines the additional child
  list as well as the principal child list

My big assumption here is that _every_ out-of-flow frame will have a placeholder
frame. If that is the case, then walking the auxiliary frame lists (e.g.,
floater, absolute) will result in out-of-flow frame being visited more than once
in the traversal. This will work fine so long as we never actually trip the code
that destroys the out-of-flow frame! (And is probably why we haven't seen this
bug more often: that code almost _never_ runs.)

If it's _not_ the case that an out-of-flow frame has a placeholder, then I'm
very confused and need enlightenment.

Comment 17

[Chris Waterson]

Attachment: do not walk auxilary frame lists (diff -wu)

Comment 18

[Chris Waterson]

Attachment: same patch, diff -u

Comment 19

[Chris Waterson]

Unfortunately, since troy didn't cite a bug, I can't go back to figure out what
he was trying to fix and see if this breaks anything.

Comment 20

[rbs]

======= with the help of groups.google.com ==========
From: Troy Chevalier ([e-mail])
Subject: Checkin (layout) - fix bug #16652 
Newsgroups: netscape.public.mozilla.layout.checkins
Date: 1999/10/18 

Fix for bug #16652. Patch from Johnny Stenbäck ([e-mail]) that
changes the pres shell's destructor to break the pres context's weak
link back to the pres shell

-Troy

Comment 21

[rbs]

Err... I copy-pasted the wrong one earlier. There is no bug number in the actual
message in layout.checkins as you pointed out. But here is a bugzilla entry 
which might be a starting point:
http://bugzilla.mozilla.org/show_bug.cgi?id=17315

Comment 22

[Johnny Stenback (:jst)]

Oh boy, that was along time ago, but I do vagely remember submitting those
patches, I don't however remember exactly what the deal was...

From what I remember, mozilla used to crash when toggling the show/collapse
state of a toolbar due to frames being left around with pointers to deleted
frames (or something), i.e. when a toolbar was collapsed we deleted most of the
frames in the toolbar but some frames were left around that had pointers to the
deleted frames, or something like that.

I don't mind having those changes backed out, but I know they were added for a
good reason, which might not be as good any more, of course :-). Make sure
backing those changes out doesn't cause crashes when showing/collapsing toolbars
tho (IIRC you hadto toggle the toolbars a number of times to trigger the crash).

Again, that was a long time ago so I could be completely wrong...

Comment 23

[Chris Waterson]

Okay, here's a detailed description of what is happening. We start
with this frame model:

Area(html)@0 <
  line: <
    Block(body)@1 <
      line: <
        Placeholder(div)@2 outOfFlowFrame=Area(div)@3
      >
      Floater-list<
        Area(div)(0)@3 <
          line: <
            Placeholder(div)@4 outOfFlowFrame=Area(div)@5
          >
        >
      >
    >
  >
  Absolute-list<
    Area(div)@5 <
    >
  >
>

We're going to remove Block(body)@1 from Area(html)@0, so we call
DoDeletingFrameSubtree(). Below is a trace of what happens with the
existing code:

  DoDeletingFrameSubtree(aRemovedFrame=Block(body)@1,
                         aFrame=Block(body)@1)

    [walk in-flow children]
      Clear primary-frame-for Block(body)@1, etc.

      firstChild <= Placeholder(div)@2
      outOfFlowFrame <= Area(div)@3

      DoDeletingFrameSubtree(aRemovedFrame=Block(body)@1,
                             aFrame=Area(div)@3)

        [walk in-flow children]
          Clear primary-frame-for Area(div)@3, etc.

          firstChild <= PlaceHolder(div)@4
          outOfFlowFrame <= Area(div)@5

          DoDeletingFrameSubtree(aRemovedFrame=Block(body)@1,
                                 aFrame=Area(div)@5)
            Clear primary-frame-for Area(div)@5, etc.

            [walk in-flow children] (none)
            [walk floated children] (none)
            [walk abspos children] (none)

          Block(body)@1 is _not_ an ancestor of Area(div)@5, so we now
          delete Area(div)@5.

        [walk floated children] (none)
        [walk abspos children] (none)

        Block(body)@1 is an ancestor of Area(div)@3, so we do not
          tell the frame manager to remove the frame.

    [walk floated children]
      firstChild <= Placeholder(div)@4
      outOfFlowFrame <= Area(div)@5<!!!DELETED!!!>

      DoDeletingFrameSubtree(aRemovedFrame=Block(body)@1,
                             aFrame=Area(div)@5<!!!DELETED!!!>)

        Clear primary-frame-for Area(div)@5<!!!DELETED!!!>
        (*CRASH HERE*)

As you can see, we re-walk part of the frame tree, because the floated
frame is accessable both from its placeholder and its container
frame's floater list. This tends to work most of the time, because:

1. This function is rarely called (usually we just tear down the frame
   tree from the top; this function is only invoked when doing DOM
   manipulation, or when parser or {ib} code kicks in to juggle
   malformed input).

2. Absolutely positioned elements are rare.

3. Absolutely positioned elements that would get promoted above the
   point of removal are even more rare.

My solution works in this case because we ensure that each frame is
only walked once, from its placeholder. That said, my assumption that
all out-of-flow frames have a place-holder is not valid, as dbaron
pointed out to me (e.g., list-item frames). Does this matter for this
function? It does if any of the following hold true:

  - We need to clear the primary-frame-for information for the
    out-of-flow frame.

  - We need to remove the frame's content's children from the
    undisplayed content map (i.e., the frame was built from a content
    node that has children which map to |display: none|).

  - The out-of-flow frame has a non-trivial frame hierarchy itself,
    which could lead to an absolutely positioned element that's
    promoted above the removed frame.

So, I guess what this means is that I need to go through the
out-of-flow frame lists and see which lists contain frames that have
no placeholders to see if any of the above apply. (Intuitively, it
seems that none of the above apply for the list-item frames.)

Does this reasoning seem sound?

Comment 24

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

Comments:

 1. it would be good to state in the comment that you only walk the primary
    child list because you assume all floaters / abs pos will be reached from
    placeholders within the tree

 2. It looks to me like you made a second unintended change, although I'm not
    sure.  In addition to not walking the additional child lists, it looks like
    you changed the recursive call to DoDeletingFrameSubtree to recur on the
    placeholder frame rather than the out-of-flow frame.  So I think this would
    change us from walking the subtree twice to not at all.

Comment 25

[Chris Waterson]

Attachment: diff -wu, be sure to descend into placeholder frame's subtree, not child subtree!

Comment 26

[Chris Waterson]

Attachment: ...and incoporate dbaron's first comment

Comment 27

[Chris Waterson]

Okay, so there are three frames that scare me; i.e., that probably bust my
assumption that an out-of-flow frame will have a placeholder:

- nsComboboxControlFrame, which has a popupList
- nsTableFrame, which has a colGroupList
- nsTableOuterFrame, which as a captionList.

karnaze, is there an in-flow placeholder for each of the colgroup and caption
frames? I'll dig into combobox, since rods is gone...

Comment 28

[rbs]

Since things are interwined in such a tricky manner, with pointers back and fro 
between child lists, and with placeholders that are optional... I will just 
throw in a food for thought... Change the algorithm as follows:
- linearize the sub-tree to be deleted, i.e., make DoDeletingFrameSubtree()
first walk the sub-tree, and append frames from all child lists in a running 
auto void array.
- fire a quick-sort on the resulting void array, and just delete the unique 
entries there.

Comment 29

[Chris Waterson]

Attachment: counter-example, <table> with a <caption> that crashes /with/ the patch

Comment 30

[Chris Waterson]

rbs, I like that idea. We probably don't even need to be that fancy, since it's
_exremely_ rare that we end up in a situation where we actually need to delete a
frame, and the other operations are idempotent.

Comment 31

[Chris Waterson]

Attachment: implement rbs's suggestion; enqueue nodes to destroy and kill them after the walk

Comment 32

[Chris Waterson]

Once again, rbs shows the way to Truth and Justice. The last patch restores us
to walking all of the additional child lists, but instead of immediately
destroying a frame, we enqueue the frame destruction and do it once the walk is
complete. I'm not too worried about the O(n**2) check we do to ensure uniqueness
at the time we enqueue the frame, because those sorts of frames will be
extremely rare.

I think this patch is ready for official r= and sr= love, if any of you on the
cc list would care to give it?

thanks...

Comment 33

[rbs]

r=rbs

Comment 34

[Marc Attinasi]

sr=attinasi

Comment 35

[Christopher Blizzard (:blizzard)]

I wonder if this will kill some of the Gtk warnings and occasional crashes that
I see on pages with frames.

a=blizzard on behalf of drivers for the trunk.

Comment 36

[Chris Waterson]

Fix checked in.

Comment 37

[Hixie (not reading bugmail)]

verified that these don't crash:
  http://bugzilla.mozilla.org/showattachment.cgi?attach_id=38681
  http://bugzilla.mozilla.org/showattachment.cgi?attach_id=37275
  http://bugzilla.mozilla.org/showattachment.cgi?attach_id=37194