822906 - Crash [@ mozilla::css::OverflowChangedTracker::Flush] with table and transform

Status: VERIFIED FIXED

(Core :: Layout, defect)

Description

[Jesse Ruderman]

Attachment: testcase (crashes Firefox when loaded)

Comment 1

[Jesse Ruderman]

Attachment: stack

Comment 2

[Jesse Ruderman]

Nightly: bp-08da0359-f8e6-419c-ab9d-6f4cc2121219

(Btw, this crash signature is #86 for Nightly.  But I don't know if my testcase demonstrates the same bug that other people are hitting.)

Comment 3

[Alice0775 White]

bp-66ded069-f032-49e8-b237-e268f2121219

Regression window(m-c)
Good:
http://hg.mozilla.org/mozilla-central/rev/c6970a82a686
Mozilla/5.0 (Windows NT 6.1; WOW64; rv:20.0) Gecko/20121210 Firefox/20.0 ID:20121210104701
Bad:
http://hg.mozilla.org/mozilla-central/rev/00e26dece6ea
Mozilla/5.0 (Windows NT 6.1; WOW64; rv:20.0) Gecko/20121210 Firefox/20.0 ID:20121210105701
Pushlog:
http://hg.mozilla.org/mozilla-central/pushloghtml?fromchange=c6970a82a686&tochange=00e26dece6ea


Regression window(m-c)
Good:
http://hg.mozilla.org/integration/mozilla-inbound/rev/fe0abb4decb6
Mozilla/5.0 (Windows NT 6.1; WOW64; rv:20.0) Gecko/20121209 Firefox/20.0 ID:20121209173350
Bad:
http://hg.mozilla.org/integration/mozilla-inbound/rev/0319dd845d53
Mozilla/5.0 (Windows NT 6.1; WOW64; rv:20.0) Gecko/20121209 Firefox/20.0 ID:20121209183350
Pushlog:
http://hg.mozilla.org/integration/mozilla-inbound/pushloghtml?fromchange=fe0abb4decb6&tochange=0319dd845d53

Suspected: Bug 815666

Comment 4

[Matt Woodrow (:mattwoodrow)]

Attachment: Use nsWeakFrame

Looks like something is updating the overflow of a frame, and then we delete the frame in the same set of style changes.

Comment 5

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

Comment on attachment 693707 [details] [diff] [review]
Use nsWeakFrame

Review of attachment 693707 [details] [diff] [review]:
-----------------------------------------------------------------

I don't think nsWeakFrame scales to large numbers of frames so we probably don't want to use it here.

Could you be more specific about what exactly happens here? Is something doing frame reconstruction for frames that are in OverflowChangedTracker? Perhaps we should explicitly notify the OverflowChangedTracker to delete entries for all descendants of a given frame?

Comment 6

[Matt Woodrow (:mattwoodrow)]

Attachment: Remove deleted frames

Yes, that's exactly what happens. Seems like a reasonable approach.

My first ever use case for 'mutable'! I think it's actually legitimate in this case.

Comment 7

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

Comment on attachment 693744 [details] [diff] [review]
Remove deleted frames

Review of attachment 693744 [details] [diff] [review]:
-----------------------------------------------------------------

This seems a bit scary performance-wise ... for every reconstructed frame, we iterate over all the entries in the tracker. That could be O(N^2) in the number of restyled frames.

It seems to me that it would be safer to iterate through all the descendants of the reconstructed frame, checking each one to see if it's in the tracker. Each check is O(log N), so that would be O(D log N) where D is the number of frames we're going to destroy (so we're already doing O(D) work at least).

Also I'm pretty sure you can remove entries from the heap in O(log N) time.

Comment 8

[Matt Woodrow (:mattwoodrow)]

I guess so, I assumed that the number of reconstructed frames would be small, whereas the number of descendants could be a lot if we reconstruct of the root frames for a document.

Comment 9

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

I would hesitate to guess. I think we should plan for the worst case.

If you're reconstructing the root frame for a document then I guess we shouldn't have any entries in OverflowChangedTracker. We can skip traversing descendants if OverflowChangedTracker is already empty or becomes so during traversal.

Comment 10

[Matt Woodrow (:mattwoodrow)]

Attachment: Remove deleted frames v2

Comment 11

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

Comment on attachment 694263 [details] [diff] [review]
Remove deleted frames v2

Review of attachment 694263 [details] [diff] [review]:
-----------------------------------------------------------------

::: xpcom/glue/nsTPriorityQueue.h
@@ +108,4 @@
>  
> +  bool Remove(const T& aElement)
> +  {
> +    size_type index = mElements.IndexOf(aElement);

This is an O(N) lookup.

Actually I think I was wrong :-(. We can't search the heap in O(log N) time :-(.

@@ +137,5 @@
>    }
>  
>  protected:
> +  T RemoveIndex(size_type aIndex)
> +  {

This should be an nsTArray method.

Comment 12

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

So I think the most straightforward approach here would be to use a balanced binary tree, which gives us add/remove/search/find-min all in O(log N) time. JS has a SplayTree implementation you could steal.

Comment 13

[Matt Woodrow (:mattwoodrow)]

Attachment: Removed deleted frames v3

Takes SplayTree from js, and adds it to mfbt. I also changed the allocation code to match what LinkedList.h does.

Seems to work, probably needs more cleaning up to pass review for mfbt/ though.

Comment 14

[Abhishek Arya]

This is the top crasher in my fuzzing as well, will be great to see it go away.

Comment 15

[Abhishek Arya]

(In reply to Abhishek Arya from comment #14)
> This is the top crasher in my fuzzing as well, will be great to see it go
> away.

Not the right time for this comment. Enjoy the holidays!!

Comment 16

[Alex Keybl [:akeybl]]

(In reply to Matt Woodrow (:mattwoodrow) from comment #13)
> Created attachment 694697 [details] [diff] [review]
> Removed deleted frames v3
> 
> Takes SplayTree from js, and adds it to mfbt. I also changed the allocation
> code to match what LinkedList.h does.
> 
> Seems to work, probably needs more cleaning up to pass review for mfbt/
> though.

Any updates here? Firefox 20 is now on Aurora, and bug 815666 is blocked on uplift by this.

Comment 17

[Matt Woodrow (:mattwoodrow)]

Attachment: Add SplayTree to mfbt

Takes the SplayTree.h file from js/src/ds and converts it to match the style used by LinkedList.h

Comment 18

[Matt Woodrow (:mattwoodrow)]

Attachment: Use SplayTree to remove deleted frames.

https://tbpl.mozilla.org/?tree=Try&rev=592b4607949c

Comment 19

[Jeff Walden [:Waldo]]

Comment on attachment 699501 [details] [diff] [review]
Add SplayTree to mfbt

Review of attachment 699501 [details] [diff] [review]:
-----------------------------------------------------------------

No comments on the correctness of this implementation -- I didn't look, haven't taken the time to grok splay trees previously, and assume this was mostly copied from the JS implementation anyway, so correctness concerns should have been dealt with already, inductively.

::: mfbt/SplayTree.h
@@ +3,5 @@
> + *
> + * This Source Code Form is subject to the terms of the Mozilla Public
> + * License, v. 2.0. If a copy of the MPL was not distributed with this
> + * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
> +

Add a one-line description comment to show up in MXR listings, perhaps describing what a splay tree does, since SplayTree.h is obviously going to contain a splay tree implementation ;-) :

/* A sorted tree with optimal access times, where recently-accessed elements are faster to access again. */

@@ +7,5 @@
> +
> +#ifndef mozilla_SplayTree_h_
> +#define mozilla_SplayTree_h_
> +
> +#include "mozilla/Assertions.h"

Add a #include "mozilla/NullPtr.h" here, and use nullptr instead of NULL throughout here.  (mfbt hasn't yet switched to nullptr totally, but it will.)

@@ +9,5 @@
> +#define mozilla_SplayTree_h_
> +
> +#include "mozilla/Assertions.h"
> +
> +#ifdef __cplusplus

You can get rid of this; we had it in the past mostly for JS's sake, when jsapi.h was C-compatible.  Now that we've dropped it I don't believe there's reason to #ifdef __cplusplus for C++-specific stuff.

@@ +13,5 @@
> +#ifdef __cplusplus
> +
> +namespace mozilla {
> +
> +template <class T, class C>

template<typename T, class Comparator> (typename because it's not a misnomer when T isn't a class, Comparator for more clarity)

@@ +29,5 @@
> +  {}
> +
> +private:
> +
> +  T *left, *right, *parent;

These should be |T* foo| and all on separate lines.  Really, every place that has |T *foo| should be |T* foo| (and same for &, so |T& bar| rather than |T &bar|.  I'd suggest searching for " *" and " &" to find all the places to adjust.

@@ +30,5 @@
> +
> +private:
> +
> +  T *left, *right, *parent;
> +};

Indentation should look like this:

class SplayTreeNode
{
  public:
    ...
    ...
  private:
    ...
    ...
    ...
};

@@ +36,5 @@
> +
> +/*
> + * Class which represents a splay tree with nodes allocated from a LifoAlloc.
> + * Splay trees are balanced binary search trees for which search, insert and
> + * remove are all amortized O(log n).

That comment doesn't really capture the cases where play trees can be useful -- it should say something additional like ", but where accessing a node makes it faster to access that node in the future."

@@ +39,5 @@
> + * Splay trees are balanced binary search trees for which search, insert and
> + * remove are all amortized O(log n).
> + *
> + * T indicates the type of tree elements, C must have a static
> + * compare(const T&, const T&) method ordering the elements. As for LifoAlloc

Please note that compare() must be side-effect-free.  (Because we're using it in assertions -- but don't put that in the comment, no reason the user has to know that.)

@@ +40,5 @@
> + * remove are all amortized O(log n).
> + *
> + * T indicates the type of tree elements, C must have a static
> + * compare(const T&, const T&) method ordering the elements. As for LifoAlloc
> + * objects, T objects stored in the tree will not be explicitly destroyed.

These comments still mention the LifoAlloc bits from the JS version of this.  I guess just remove the last sentence of the second paragraph, and remove "with...LifoAlloc" from the first paragraph.

@@ +45,5 @@
> + */
> +template <class T, class C>
> +class SplayTree
> +{
> +    T *root, *freeList;

As a corollary to the *-goes-by-type rule, these should be two separate declarations.  Same a couple other places.

@@ +48,5 @@
> +{
> +    T *root, *freeList;
> +
> +    SplayTree(const SplayTree &) MOZ_DELETE;
> +    SplayTree &operator=(const SplayTree &) MOZ_DELETE;

Make the operator= return void -- that'll make accidental assignments into compile errors even when MOZ_DELETE doesn't expand to anything, I think.

Also, move these deleted methods to the end of the class to get them out of the way for the interested reader.

@@ +51,5 @@
> +    SplayTree(const SplayTree &) MOZ_DELETE;
> +    SplayTree &operator=(const SplayTree &) MOZ_DELETE;
> +
> +  public:
> +

No blank line needed at the start of a public:/private:/protected: section.

@@ +54,5 @@
> +  public:
> +
> +    SplayTree()
> +      : root(NULL), freeList(NULL)
> +    {}

You could make this whole constructor a one-liner if you wanted, doesn't really matter, tho.

@@ +57,5 @@
> +      : root(NULL), freeList(NULL)
> +    {}
> +
> +    bool empty() const {
> +        return !root;

The contents of methods should be two-space-indented, throughout the whole patch.  Right now indentation everywhere's pretty inconsistent.

@@ +63,5 @@
> +
> +    bool contains(const T &v)
> +    {
> +        if (!root)
> +            return false;

Let's make this:

if (empty())
    return false;

for a little more clarity.  And since this special-ish case is logically separate from the rest of the method, let's add a blank line between this and the rest.

@@ +69,5 @@
> +        splay(last);
> +        checkCoherency(root, NULL);
> +        if (C::compare(v, *last) == 0) {
> +            return true;
> +        }

mfbt doesn't brace single-line anything (at least, not unless the head -- the condition of the if, the stuff in parens for a for-loop, etc. -- occupies multiple lines).  (Well, except do-while loops, because who doesn't brace those?)

@@ +70,5 @@
> +        checkCoherency(root, NULL);
> +        if (C::compare(v, *last) == 0) {
> +            return true;
> +        }
> +        return false;

return Comparator::compare(v, *last) == 0;

@@ +83,5 @@
> +        T *last = lookup(*v);
> +        int cmp = C::compare(*v, *last);
> +
> +        // Don't tolerate duplicate elements.
> +        MOZ_ASSERT(cmp);

MOZ_ASSERT(cmp != 0, "Duplicate elements are not allowed.");

Or perhaps, since this is really a precondition, we should make it

MOZ_ASSERT(!contains(*v), "Duplicate elements are not allowed.");

and put it right at the start of insert().  Actually, yeah, that's better -- do that.

@@ +85,5 @@
> +
> +        // Don't tolerate duplicate elements.
> +        MOZ_ASSERT(cmp);
> +
> +        T *&parentPointer = (cmp < 0) ? last->left : last->right;

It's less obvious there's mutation going on when a reference is assigned to, so let's make this |T** parentPointer = ... &last->left : &last->right;|, adding explicit dereferences below as needed.

@@ +98,5 @@
> +
> +    T* remove(const T &v)
> +    {
> +        T *last = lookup(v);
> +        MOZ_ASSERT(last && C::compare(v, *last) == 0);

MOZ_ASSERT(last, "This tree must contain the element being removed.");
MOZ_ASSERT(Comparator::compare(v, *last) == 0);

This makes the reason for the first assertion obvious if it's hit in, say, tinderbox debug-testing runs, and it splits them so that the reader doesn't have to guess which condition failed, if a failure were to happen.

@@ +149,5 @@
> +        checkCoherency(root, NULL);
> +        return last;
> +    }
> +
> +    T* remove_min()

This should be removeMin (camelCaps like all method names).

@@ +161,5 @@
> +    }
> +
> +  private:
> +
> +    T *lookup(const T &v)

There should be a comment by this explaining what it returns, I think something like this if I understand the code:

/* Returns the node in this comparing equal to |v|, or a node just greater or just less than |v| if there is no such node. */

@@ +163,5 @@
> +  private:
> +
> +    T *lookup(const T &v)
> +    {
> +        MOZ_ASSERT(root);

MOZ_ASSERT(!isEmpty());

@@ +164,5 @@
> +
> +    T *lookup(const T &v)
> +    {
> +        MOZ_ASSERT(root);
> +        T *node = root, *parent;

Separate decls for these.

@@ +178,5 @@
> +        } while (node);
> +        return parent;
> +    }
> +
> +    void splay(T *node)

/* Reorganizes this tree to improve access speeds to |node|. */ or somesuch.

@@ +269,5 @@
> +
> +}  /* namespace mozilla */
> +
> +#endif /* ifdef __cplusplus */
> +#endif /* ifdef mozilla_SplayTree_h_ */

Don't put the "ifdef " part here.

::: mfbt/exported_headers.mk
@@ +29,5 @@
>    RefPtr.h \
>    Scoped.h \
>    StandardInteger.h \
>    SHA1.h \
> +  SplayTree.h \

Let's realphabetize while we're here -- Scoped, SHA1, SplayTree, StandardInteger.

Comment 20

[Matt Woodrow (:mattwoodrow)]

Attachment: Add SplayTree to mfbt v2

Thanks Waldo!

Hopefully this addresses all your review comments.

Comment 21

[Alex Keybl [:akeybl]]

Let's leave the status flag for FF19 untouched for now, so that this doesn't fall off of our tracking queries. Uplifting this fix to mozilla-beta is blocking bug 815666 from landing.

Comment 22

[Jeff Walden [:Waldo]]

Comment on attachment 701631 [details] [diff] [review]
Add SplayTree to mfbt v2

Review of attachment 701631 [details] [diff] [review]:
-----------------------------------------------------------------

Feel free to make the class-overview comment, and the method-overview comments, doxygen-style if you want:

/**
 * line one...
 * line two...
 */

We take either that style or the single-star style right now, to accommodate Gecko people used to the doxygen format.

::: mfbt/SplayTree.h
@@ +5,5 @@
> + * License, v. 2.0. If a copy of the MPL was not distributed with this
> + * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
> +
> +/* A sorted tree with optimal access times, where recently-accessed elements
> + * are faster to access again. */

/*
 * line one...
 * line two...
 */

@@ +16,5 @@
> +
> +namespace mozilla {
> +
> +template <class T, class C>
> +class SplayTree;

Super-nitpick: template<class T, class C>

@@ +23,5 @@
> +class SplayTreeNode
> +{
> +  public:
> +    template <class A, class B>
> +    friend class SplayTree;

template<... here too

@@ +47,5 @@
> + * compare(const T&, const T&) method ordering the elements. The compare
> + * method must be free from side effects.
> + */
> +template <typename T, class Comparator>
> +class SplayTree

template<

@@ +75,5 @@
> +
> +    bool insert(T* v)
> +    {
> +      // Don't tolerate duplicate elements.
> +      MOZ_ASSERT(!contains(*v), "Duplicate elements are not allowed.");

The assertion reason makes the comment redundant.  :-)  (And if I do say so myself, it's a prime example of how assertion reasons can be occasionally useful.)

@@ +150,5 @@
> +      checkCoherency(root, nullptr);
> +      return last;
> +    }
> +
> +    T* removeMin()

Just to get it on the record, I had thought of requesting removeMax be added, too, but figured someone would request it when they wanted it.  No need to add it here.

@@ +152,5 @@
> +    }
> +
> +    T* removeMin()
> +    {
> +      MOZ_ASSERT(root);

MOZ_ASSERT(!empty(), "No min to remove!"); is again clearer about what's being done.

Add a blank line after it, too, since it's separate from the actual lookup/remove steps.  Actually, if you could do that on all the precondition-ish sequences of assertions, that'd be great.

@@ +156,5 @@
> +      MOZ_ASSERT(root);
> +      T* min = root;
> +      while (min->left) {
> +        min = min->left;
> +      }

Remove the braces.

@@ +162,5 @@
> +    }
> +
> +  private:
> +    /* Returns the node in this comparing equal to |v|, or a node just greater or
> +     * just less than |v| if there is no such node. */

/*
 * line one
 * line two
 */

@@ +181,5 @@
> +      } while (node);
> +      return parent;
> +    }
> +    
> +    /** 

Remove the trailing whitespace.

@@ +269,5 @@
> +#else
> +      return nullptr;
> +#endif
> +    }
> +    

Remove the trailing whitespace.

Comment 23

[Matt Woodrow (:mattwoodrow)]

https://hg.mozilla.org/integration/mozilla-inbound/rev/5afe6e43be75
https://hg.mozilla.org/integration/mozilla-inbound/rev/d8a11c7c37b5

Comment 24

[Ed Morley [:emorley]]

https://hg.mozilla.org/mozilla-central/rev/5afe6e43be75
https://hg.mozilla.org/mozilla-central/rev/d8a11c7c37b5

Comment 25

[Lukas Blakk [:lsblakk] use ?needinfo]

Please nominate for aurora uplift since we're waiting on this for bug 815666

Comment 26

[Scoobidiver (away)]

It's not fixed. See https://crash-stats.mozilla.com/report/list?version=Firefox:21.0a1&signature=mozilla%3A%3Acss%3A%3AOverflowChangedTracker%3A%3AFlush%28%29

Comment 27

[Jesse Ruderman]

Scoobidiver, please file a new bug for the topcrash.  This bug is fixed.

Comment 28

[Matt Woodrow (:mattwoodrow)]

Comment on attachment 699503 [details] [diff] [review]
Use SplayTree to remove deleted frames.

[Approval Request Comment]
Bug caused by (feature/regressing bug #): Bug 815666
User impact if declined: Crashes.
Testing completed (on m-c, etc.): Been on m-c for a few days
Risk to taking this patch (and alternatives if risky): Low risk, just avoids processing deleted frames.
String or UUID changes made by this patch: None

Comment 29

[Alex Keybl [:akeybl]]

Comment on attachment 699503 [details] [diff] [review]
Use SplayTree to remove deleted frames.

Approving for Beta alongside bug 815666. Please land asap today to make it into Beta 3.

Comment 30

[Jesse Ruderman]

(In reply to Jesse Ruderman from comment #27)
> Scoobidiver, please file a new bug for the topcrash.  This bug is fixed.

Thanks for filing bug 832611 to track the topcrash.

Comment 31

[Matt Woodrow (:mattwoodrow)]

https://hg.mozilla.org/releases/mozilla-aurora/rev/e9bdaf8cf48c
https://hg.mozilla.org/releases/mozilla-aurora/rev/6be57140550d

https://hg.mozilla.org/releases/mozilla-beta/rev/a3a21c01dab8
https://hg.mozilla.org/releases/mozilla-beta/rev/7f84bf06751d

Comment 32

[Phil Ringnalda (:philor)]

Backed out in http://hg.mozilla.org/releases/mozilla-beta/rev/24dc8d9b0a3a

Comment 33

[Alex Keybl [:akeybl]]

We're going to be backing out bug 806256 and bug 807563 from FF19, so this bug won't be necessary.

Comment 34

[Paul Silaghi, QA [:pauly]]

Verified fixed using the testcase on FF 20b6, FF 21.0a2 (2013-03-20) on Win 7, Ubuntu 12.04 and Mac OS X 10.7.5