618479 - Firefox freezes on various terre-adelice.eu pages (unresponsive script)

Status: RESOLVED FIXED

(Core :: XPCOM, defect, P2)

Description

[Vincent Lefevre]

User-Agent:       Mozilla/5.0 (Macintosh; U; PPC Mac OS X 10.4; en-GB; rv:1.9.2.13) Gecko/20101203 Firefox/3.6.13
Build Identifier: Mozilla/5.0 (Macintosh; U; PPC Mac OS X 10.4; en-GB; rv:1.9.2.13) Gecko/20101203 Firefox/3.6.1

Firefox freezes on various terre-adelice.eu pages, and during this time one cannot use it at all. Under Mac OS X, a dialog box appears after several seconds, saying "Unresponsive script". If I click on "Continue", same problem. I need to click on "Stop script". This is always reproducible.

Safari (on the same machine) doesn't have any problem. Thus it looks like more a Firefox bug than a problem with the web site (in any case, freezing the whole UI is not acceptable). Debian's Iceweasel 3.5.16 on a Linux machine also sometimes freezes for a few seconds (this is not always reproducible), then it is OK (without getting the dialog box). On the same Linux machine, I don't have any problem with chromium-browser.

Reproducible: Always

Steps to Reproduce:
1. Open http://www.terre-adelice.eu/accueil.php
Actual Results:  
Firefox freezes for several seconds, then a dialog box appears, saying "Unresponsive script".

Expected Results:  
The page should be loaded and Firefox shouldn't freeze (like with the other browsers).

Comment 1

[Vincent Lefevre]

Note: the Build Identifier should be:

Mozilla/5.0 (Macintosh; U; PPC Mac OS X 10.4; en-GB; rv:1.9.2.13) Gecko/20101203 Firefox/3.6.13

(the last character was missing - bad copy-paste...).

Comment 2

[Boris Zbarsky [:bzbarsky]]

> in any case, freezing the whole UI is not acceptable

Sure, but that's a consequence of having the web page and UI on the same thread.

The relevant part of the script looks like this:

var millisec = 5000;
var speed = Math.round(millisec / 100);
var timer = 0;
var id = "backgrounddiv";
if (navigator.userAgent.indexOf("MSIE") == -1) {

    for (k = 0; k <= 30; k++) {
        for (j = 0; j <= 2; j++) {
            for (i = 0; i <= 100; i++) {
                setTimeout("changeOpac(" + i + ",'" + id + "'," + j + ")",
                           (timer * speed));
                timer++;
            }
            for (i = 100; i >= 0; i--) {
                setTimeout("changeOpac(" + i + ",'" + id + "'," + j + ")",
                           (timer * speed));
                timer++;
            }
        }
    }
}

which sets up 30 * 2 * 200 = 12,000 timers to run this function:

  function changeOpac(opacity, id,CurrentPic)  
  {  
    var object = document.getElementById(id).style;  
    object.backgroundImage  = Pic[CurrentPic][0];
    object.opacity = (opacity / 100);  
    object.MozOpacity = (opacity / 100);  
    object.KhtmlOpacity = (opacity / 100);  
    object.filter = "alpha(opacity=" + opacity + ")";  
  }  

Most of these (if not all) fire before the div is actually in the DOM, thus throwing an exception when trying to get .style in changeOpac.

In any case, I don't get the slow script dialog in either 3.6 or current trunk, though 3.6 does have a slightly longer pause.  I did profile the pageload on trunk, and about 50% of pageload is spent in TimerThread::AddTimerInternal; that's something we should fix.

Comment 3

[Boris Zbarsky [:bzbarsky]]

Attachment: testcase for that

Output in a vanilla build:

90 ms to set 5000 timers
490 ms to set 10000 timers
1751 ms to set 15000 timers
7482 ms to set 20000 timers

Output in a build with my upcoming patch:

28 ms to set 5000 timers
64 ms to set 10000 timers
92 ms to set 15000 timers
139 ms to set 20000 timers

Comment 4

[Boris Zbarsky [:bzbarsky]]

Attachment: Witness the power of the logarithm.

Comment 5

[Boris Zbarsky [:bzbarsky]]

Comment on attachment 497018 [details] [diff] [review]
Witness the power of the logarithm.

cjones pointed out we have this in nsTArray already.

Comment 6

[Boris Zbarsky [:bzbarsky]]

Attachment: part 1. Clean up the nsTArray binary-insert code a little bit.

Comment 7

[Boris Zbarsky [:bzbarsky]]

Attachment: part 2. Use binary, not linear, search to determine timer insertion locations.

Comment 8

[Brendan Eich [:brendan]]

Comment on attachment 497025 [details] [diff] [review]
part 2.  Use binary, not linear, search to determine timer insertion locations.

>-    // XXXbz why?  Given our definition of overdue in terms of
>-    // mTimeoutAdjustment, aTimer might be overdue already!  Why not
>-    // just fire timers in order?
>-
>-    // XXX does this hold for TYPE_REPEATING_PRECISE?  /be
>-
>-    if (now < timer->mTimeout + mTimeoutAdjustment &&
>-        aTimer->mTimeout < timer->mTimeout) {
>-      break;
>-    }

>+  PRBool LessThan(nsTimerImpl *fromArray, nsTimerImpl *newTimer) const {
>+    NS_ABORT_IF_FALSE(newTimer == timerToInsert, "Unexpected timer ordering");
>+
>+    // Skip any overdue timers.
>+
>+    // XXXbz why?  Given our definition of overdue in terms of
>+    // mTimeoutAdjustment, aTimer might be overdue already!  Why not
>+    // just fire timers in order?
>+    return now >= fromArray->mTimeout + timeoutAdjustment ||
>+           fromArray->mTimeout <= newTimer->mTimeout;
>+  }

Moving the code and inverting the (&&) condition to get (||), and using >= instead of >, is cool, but I'd want both disjuncts to use the same "number line" order, so newTimer->mTimeout >= fromArray->mTimeout.

Is the XXXbz really a FIXME citing a filed bug? If not, file and cite.

r=me with these picked.

/be

Comment 9

[Chris Jones [:cjones] inactive; ni?/f?/r? if you need me]

Comment on attachment 497022 [details] [diff] [review]
part 1.  Clean up the nsTArray binary-insert code a little bit.

Yeah, this code needed some love :).  Thanks.

I think we agreed what we want here is the index i where, if x were
inserted at i, the array would stay sorted and x would be appended to
all elements == to x.  A reasonable name for such a function seems to
be

  IndexOfFirstElementGt(x):

with a comment about how ties are broken for == elements.

The current algorithm gives us the tie-breaking behavior opposite to
what we want.  The algorithm below is the one we want, I think.
(Worth double checking!)

  // Find the smallest i for which x < E[i].
  while (hi > lo)  {
    mid = (lo + hi) / 2
    if (<(x, E[mid]))
      hi = mid
    else
      lo = mid + 1
  }

It would also be nice to add a test for sorted insert of == elements.

Comment 10

[Boris Zbarsky [:bzbarsky]]

> I think we agreed what we want here is

Well, we hadn't gotten that far.  ;)  But those are reasonable semantics, yes.

> The algorithm below is the one we want, I think.

Agreed, for the append behavior.

Comment 11

[Chris Jones [:cjones] inactive; ni?/f?/r? if you need me]

Oh.  Guess we discussed your use case, and didn't get past trying to reconstruct wtf the original author was thinking :).

Comment 12

[Wayne Mery (:wsmwk)]

is this issue worse for v3.6 (gecko 1.9.2) vs v3.5 (gecko 1.9.1)?? 
The reason I ask, is we have way more script timeout reports in thunderbird 3.1 (1.9.2) vs TB3.0 (1.9.1).

FWIW, windows isn't mentioned in this bug - I can't reproduce timeout on windows with trunk with URL or testcase. Although I didn't try in safe mode.

Comment 13

[Vincent Lefevre]

(In reply to comment #12)
> is this issue worse for v3.6 (gecko 1.9.2) vs v3.5 (gecko 1.9.1)?? 

I don't know. With v3.5 under Linux, I notice a very short freeze (compared to other web sites), but the machine is much faster than my 6-year old Mac OS X machine. BTW I can reproduce the timeout on this Linux machine with cpulimit -p <pid_of_firefox-bin> -l 20 (i.e. to use 20% of the CPU). If you want to be able to reproduce the timeout, I suggest that you try on a "slow" machine (but note that rendering usual web sites is still very fast) or use some tool to limit the CPU usage.

Comment 14

[Wayne Mery (:wsmwk)]

bz, chris, is an updated patch needed?  or is this good for checkin?

Comment 15

[Boris Zbarsky [:bzbarsky]]

Wayne, this needs an updated patch.  What made you think this could possibly be good for checkin?

Comment 16

[Boris Zbarsky [:bzbarsky]]

Attachment: Part 1 updated to comments

Matthew, could you take a look at the WebMBufferedParser changes, please?

The only other thing that worries me here is the behavior change for RemoveElementSorted...

Comment 17

[Boris Zbarsky [:bzbarsky]]

Attachment: Part 2 merged to tip

Comment 18

[Matthew Gregan [:kinetik]]

Comment on attachment 703482 [details] [diff] [review]
Part 1 updated to comments

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

::: content/media/webm/WebMBufferedParser.cpp
@@ +141,5 @@
>          // duplicate WebMTimeDataOffset entries.
>          {
>            ReentrantMonitorAutoEnter mon(aReentrantMonitor);
> +          uint32_t idx = aMapping.IndexOfFirstElementGt(mBlockOffset);
> +          if (idx == 0 || !(aMapping[idx-1] == mBlockOffset)) {

aMapping[idx-1] != mBlockOffset

Comment 19

[Boris Zbarsky [:bzbarsky]]

> aMapping[idx-1] != mBlockOffset

That's what I first wrote, yes, but aMapping[idx-1] has an operator== that takes an int, but has no operator!=.  Want me to define one?

Comment 20

[Matthew Gregan [:kinetik]]

Oh, silly me, I looked at the type of mBlockOffset but not aMapping[idx-1].  The current way is fine with me, in that case.

Comment 21

[Boris Zbarsky [:bzbarsky]]

Sounds good.

Try run is green, for what that's worth.

Comment 22

[Justin Lebar (not reading bugmail)]

OOC what made you come back to this bug?

Comment 23

[Boris Zbarsky [:bzbarsky]]

Trying to clean out my inbox and coming across the old r-.  ;)

Comment 24

[Justin Lebar (not reading bugmail)]

Comment on attachment 703482 [details] [diff] [review]
Part 1 updated to comments

Not to revive years-old bikeshedding on this interface, but ISTM that it would
be helpful to have an InsertElementSortedIfNotPresent() method, since that's
what a majority of these callers are (clunkily) doing.

Although really, we should probably be using heaps for this stuff...

Just a thought; r=me with or without that change.

>diff --git a/xpcom/glue/nsTArray.h b/xpcom/glue/nsTArray.h
>--- a/xpcom/glue/nsTArray.h
>+++ b/xpcom/glue/nsTArray.h

>@@ -855,88 +855,65 @@ public:
>     if (!this->EnsureCapacity(Length() + 1, sizeof(elem_type)))
>       return nullptr;
>     this->ShiftData(index, 0, 1, sizeof(elem_type), MOZ_ALIGNOF(elem_type));
>     elem_type *elem = Elements() + index;
>     elem_traits::Construct(elem);
>     return elem;
>   }
> 
>-  // This method searches for the least index of the greatest
>-  // element less than or equal to |item|.  If |item| is inserted at
>-  // this index, the array will remain sorted.  True is returned iff
>-  // this index is also equal to |item|.  In this case, the returned
>-  // index may point to the start of multiple copies of |item|.
>+  // This method searches for the smallest index of an element that is strictly
>+  // greater than |item|.  If |item| is inserted at this index, the array will
>+  // remain sorted and |item| would come after all elements that are equal to
>+  // it.
>+  //
>+  // Note that consumers who want to know whether there are existing items equal
>+  // to |item| in the array can just check that the return value here is > 0 and
>+  // indexing into the previous slot gives something equal to |item|.
>+  //
>   // @param item   The item to search for.
>   // @param comp   The Comparator used.
>-  // @outparam idx The index of greatest element <= to |item|
>-  // @return       True iff |item == array[*idx]|.
>+  // @return        The index of greatest element <= to |item|
>   // @precondition The array is sorted

I think it would be helpful if we explicitly indicated what we return when
|item| is greater than all elements in the array.

We should also say that this method assumes that the list is sorted.  :)

>   template<class Item, class Comparator>
>+  index_type
>+  IndexOfFirstElementGt(const Item& item,
>+                        const Comparator& comp) const {
>+    // invariant: low <= [idx] <= high
>     index_type low = 0, high = Length();
>     while (high > low) {
>       index_type mid = (high + low) >> 1;

I know it's not your problem here, but this (and probably other TArray code) is
incorrect if high + low overflows.  It looks to me like we're safe because
EnsureCapacity bails if we try to alloc more than 2GB of memory, but I'd appreciate if you could double-check this.

>   template<class Item, class Comparator>
>   bool RemoveElementSorted(const Item& item, const Comparator& comp) {
>-    index_type index;
>-    bool found = GreatestIndexLtEq(item, comp, &index);
>-    if (found)
>-      RemoveElementAt(index);
>-    return found;
>+    index_type index = IndexOfFirstElementGt(item, comp);
>+    if (index > 0 && comp.Equals(ElementAt(index-1), item)) {
>+      RemoveElementAt(index-1);
>+      return true;
>+    }
>+    return false;
>   }

I don't care myself, but I think style is |index - 1|?

Comment 25

[Boris Zbarsky [:bzbarsky]]

> We should also say that this method assumes that the list is sorted.  :)

Is the @precondition there not enough?

> but I'd appreciate if you could double-check this.

You're right that EnsureCapacity saves us here.  That said, I could switch to uint64_t for all the indices if you'd like.

> I don't care myself, but I think style is |index - 1|?

Done.

Comment 26

[Boris Zbarsky [:bzbarsky]]

http://hg.mozilla.org/integration/mozilla-inbound/rev/32b985353206
https://hg.mozilla.org/integration/mozilla-inbound/rev/bffcfc510a9c

Comment 27

[Justin Lebar (not reading bugmail)]

> Is the @precondition there not enough?

Apparently I tend to ignore those.  Yes, that's fine.

> That said, I could switch to uint64_t for all the indices if you'd like.

What we're doing is fine with me.  We can pretend it's for efficiency.  :)

Comment 28

[Ed Morley [:emorley]]

https://hg.mozilla.org/mozilla-central/rev/32b985353206
https://hg.mozilla.org/mozilla-central/rev/bffcfc510a9c