773247 - Find freezes for quite long on a certain website

Status: RESOLVED FIXED

(Core :: Find Backend, defect)

Description

[d]

User Agent: Mozilla/5.0 (Windows NT 6.1; rv:13.0) Gecko/20100101 Firefox/13.0.1
Build ID: 20120614114901

Steps to reproduce:

Visit https://aces01.nus.edu.sg/cors/jsp/report/ModuleInfoListing.jsp
Type {Ctrl-F}, "1234", {Backspace, 4 times}, "1"


Actual results:

Firefox freezes for 30 seconds.


Expected results:

It shouldn't have frozen.

Comment 1

[mjh563]

This may also be related to bug 429732 and/or bug 251862, which are about Firefox freezing when highlighting matches.

Comment 2

[d]

I can't be sure, but highlighting all matches is certainly going to take some time, which is reasonable. This is just about finding the first match from some point (actually I have no idea where Firefox places the start point of the search after I backspace). IE9 searches on the page with no problems at all, even with highlighting on.

Comment 3

[Jonah Ho (AAstar)]

Does starting Firefox in safe mode help?
Firefox -> Help -> Restart with add-ons disabled

Comment 4

[d]

Yes. Why don't you try it on your side?

Comment 5

[Jonah Ho (AAstar)]

I haven't been able to reproduce this on my side regardless of safe-mode.

Since it works in safe mode, that means one of your add-ons is causing the problem.  The next step is to enable safe-mode, and then enable each add-on until you find the one that is causing the freezing.  I hope that helps.

Comment 6

[Matthias Versen [:Matti]]

I can reproduce this issue with Firefox 14.0.1 on win7
I will try to generate a stack trace of the hang if I'm at home.

Comment 7

[d]

Sorry I misread your question... I actually meant restarting in safe mode still causes the problem.

Comment 8

[d]

For info, I have confirmed it on Firefox 13 on Windows 7, Firefox 13 on Windows XP and Firefox 5 on Windows XP.

Comment 9

[Matthias Versen [:Matti]]

The Profile isn't very useful
http://people.mozilla.com/~bgirard/cleopatra/?report=06a0e293d75dfa12f37377a9c78634e07ab0a744

mcsmurf could reproduce this with Seamonkey

Comment 10

[Frank Wein [:mcsmurf]]

Yes, SeaMonkey has the same problem on that page. I used Visual Studio 2010 Profiler in CPU sampling mode to profile this (with a current comm-central/mozilla-central debug build). Here are the top functions while it hangs with 100% CPU time:
Funktionsname	Inklusive Samplings	Exklusive Samplings	Inklusive Samplings in %	Exklusive Samplings in %
(Translation: Function name; Inclusive samples (so number of calls to this function plus calls to functions below this function); Exclusive samples; % Inclusive; % Exclusive)
_wmainCRTStartup	7.888	0	99,90	0,00
Unbekannte(r) Frame(s)(Unknown frame) 7.888	1.909	99,90	24,18
nsFrameIterator::Next(void)	5.091	528	64,48	6,69
nsFrameIterator::GetParentFrameNotPopup(class nsIFrame *)	2.328	240	29,48	3,04
nsFrameIterator::IsPopupFrame(class nsIFrame *)	2.088	158	26,44	2,00
nsIFrame::GetStyleDisplay(void)const 	1.927	689	24,40	8,73
nsStyleContext::DoGetStyleDisplay(bool)	1.226	192	15,53	2,43
nsRuleNode::GetStyleDisplay(class nsStyleContext *,bool)	1.030	368	13,04	4,66
nsFrameIterator::GetNextSibling(class nsIFrame *)	1.027	776	13,01	9,83

Comment 11

[Frank Wein [:mcsmurf]]

Can someone familiar with rendering code reassign this to the correct Layout(?) component based on the profiling I did in Comment 10? Or maybe reassign back to the Find Backend (or General)? I'm not sure which code is to blame for this. Thanks!

Comment 12

[Frank Wein [:mcsmurf]]

Actually now that I look at it again, probably related to/dupe of the bugs mentioned in Comment 1 (Bug 429732, Bug 251862)

Comment 13

[Frank Wein [:mcsmurf]]

Eh, sorry, forget Comment 12...

Comment 14

[Boris Zbarsky [:bzbarsky]]

Highlighting matches is unlikely to matter.

The profile just shows walking over the tree; the bug is in whoever is doing the walk in a dumb way.

Comment 15

[d]

Attachment: A simple test case that causes the freeze

I stripped down the original page to the bare minimum that causes the freeze, and came up with this. I think it is something to do with the calculation of the position of the occurrences.

Comment 16

[d]

Attachment: A simple test case that causes the freeze

I'm sorry to all those who have tried the earlier attachment... it must have crashed your Firefox session. I've changed the parameter to be dynamic. Entering a number on the order of 100000 or more will cause the rendering of that table to run forever (which should be another bug), so don't. Both bugs appear to run in O(n^2) time, which is why 10000 runs in a reasonable amount of time.

Comment 17

[Boris Zbarsky [:bzbarsky]]

The testcase in comment 16 doesn't appear to freeze for me, with the strings from comment 0.

Back to the comment 0 steps, though, all of the time is under IsRangeVisible() called from FindItNow().  Half of that is FrameIterator::Next() and the other half is PresShell::GetRectVisibility; a lot of this is under nsIFrame::GetOffsetTo.

It looks like what's going on here is that we search for "1", then check whether it's visible in the viewport, then keep repeating that until we find one that's inside the viewport?

Comment 18

[Boris Zbarsky [:bzbarsky]]

Oh, this is silly.  IsRangeVisible() _already_ finds the right range for us to use after it's called.  But then we go ahead and ignore that, which is what gives us the nasty O(N^2) behavior.

Comment 19

[Boris Zbarsky [:bzbarsky]]

Attachment: Don't keep looking forward for the first visible range and then just ignoring it.

Comment 20

[Masayuki Nakano [:masayuki] (he/him)(JST, +0900)]

bz:

Why did you request the review to me? I don't touch the find module for several years...

Comment 21

[Boris Zbarsky [:bzbarsky]]

Because no one else has either, and you were the last person to review code around the code I'm changing...  If you have a better suggestion for a reviewer, feel free to redirect, of course.  I just had no better ideas.  :(

Comment 22

[d]

Oh yeah I didn't mention how to produce the hang on the test case. Say you ran with parameter 10000. Find for 19999, backspace all the way, and then type 1. If you run with parameter 100000, it would already crash your Firefox session so it's another bug with the rendering.

Comment 23

[Boris Zbarsky [:bzbarsky]]

Masayuki-san, if you're not planning to review his, please do let me know and I'll look for someone else.

Comment 24

[Masayuki Nakano [:masayuki] (he/him)(JST, +0900)]

Oops, I'm sorry. I didn't realize your replay. Okay, I try to review it today.

Comment 25

[Masayuki Nakano [:masayuki] (he/him)(JST, +0900)]

Comment on attachment 667777 [details] [diff] [review]
Don't keep looking forward for the first visible range and then just ignoring it.

>@@ -702,16 +700,17 @@ nsTypeAheadFind::GetSearchContainers(nsI
> 
>   if (!currentSelectionRange) {
>     // Ensure visible range, move forward if necessary
>     // This uses ignores the return value, but usese the side effect of
>     // IsRangeVisible. It returns the first visible range after searchRange
>     IsRangeVisible(presShell, presContext, mSearchRange, 
>                    aIsFirstVisiblePreferred, true, 
>                    getter_AddRefs(mStartPointRange), nullptr);
>+    mStartPointRange->Collapse(true);  // Collapse to start
>   }
>   else {
>     int32_t startOffset;
>     nsCOMPtr<nsIDOMNode> startNode;
>     if (aFindPrev) {
>       currentSelectionRange->GetStartContainer(getter_AddRefs(startNode));
>       currentSelectionRange->GetStartOffset(&startOffset);
>     } else {

You don't need this change, it will be done after the if/else block.

>+  // *aNewRange may not be collapsed.  If you want to collapse it in a
>+  // *particular way, you need to do it yourself.
>   bool IsRangeVisible(nsIPresShell *aPresShell, nsPresContext *aPresContext,
>                         nsIDOMRange *aRange, bool aMustBeVisible, 
>                         bool aGetTopVisibleLeaf, nsIDOMRange **aNewRange,
>                         bool *aUsesIndependentSelection);

Why did you add the * at the start of the comment?

# Anyway, I don't like the name, though...

Comment 26

[Boris Zbarsky [:bzbarsky]]

> Why did you add the * at the start of the comment?

Editor malfunction.  I'll take it out.

> # Anyway, I don't like the name, though...

The name of which?

Thanks for the review!

Comment 27

[Masayuki Nakano [:masayuki] (he/him)(JST, +0900)]

(In reply to Boris Zbarsky (:bz) from comment #26)
> > # Anyway, I don't like the name, though...
> 
> The name of which?

The IsRangeVisible()... Of course, I didn't mean you should change it in this bug.

Comment 28

[Boris Zbarsky [:bzbarsky]]

Ah, ok.  I appreciate that.  And yeah, the name is not great.  :(

Comment 29

[Boris Zbarsky [:bzbarsky]]

https://hg.mozilla.org/integration/mozilla-inbound/rev/2efb9e5762ce

Comment 30

[Ed Morley [:emorley]]

https://hg.mozilla.org/mozilla-central/rev/2efb9e5762ce

Comment 31

[d]

Does this fix the other bug with the O(n^2) rendering? I think that's even more serious because a website can easily cause all Firefox users to have their session freeze up just by loading their site...

Comment 32

[Boris Zbarsky [:bzbarsky]]

> Does this fix the other bug with the O(n^2) rendering?

This fix only changed find behavior.  Please file a separate bug on the O(N^2) thing, with clear steps to reproduce?  One bug per issue.

Comment 33

[d]

Ok. See Bug #803940.

Comment 34

[IU]

My is the block removed?  This caused the regression, or am I missing something?

Comment 35

[Boris Zbarsky [:bzbarsky]]

You're missing something.  Like the fact that bug 803579 is not a regression as far as I can tell, and certainly not from this bug.  ;)

Comment 36

[IU]

How is that possible?  With cset 78c16f313547, searching the page referenced in that bug does not hang the browser.  From cset 2efb9e5762ce onward, the browser hangs.

The two landing within that range are bug 773247 and bug 798800.  Since I doubt bug 798800 would be the cause, that leaves this bug.

Comment 37

[Boris Zbarsky [:bzbarsky]]

> With cset 78c16f313547, searching the page referenced in that bug does not hang the
> browser.  From cset 2efb9e5762ce onward, the browser hangs.

Uh...  Are you sure you don't have it backwards?  This bug _fixed_ a "hang" while searching the page referenced in bug 803579.  Which happens to be the same exact page as the "simple testcase" attached in this bug.  

In any case, bug 803579 is about a hang _loading_ a page, not searching it.  So if you see any sort of hang while _searching_, please file a bug on that, with clear steps to reproduce.

Comment 38

[IU]

(In reply to Boris Zbarsky (:bz) from comment #37)
> Uh...  Are you sure you don't have it backwards?  This bug _fixed_ a "hang"
> while searching the page referenced in bug 803579.  Which happens to be the
> same exact page as the "simple testcase" attached in this bug.  

Incorrect.  The page referenced in bug 803579 is not attached to this bug.  Please double-check.
 
> In any case, bug 803579 is about a hang _loading_ a page, not searching it.

Incorrect again.  Please read bug 803579 comment 0

> So if you see any sort of hang while _searching_, please file a bug on that,
> with clear steps to reproduce.

That is precisely what bug 803579 comment 0 is all about.

I'm not sure what you're looking at, but unless I'm clearly out of my mind or something, I don't think you've been looking at bug 803579

Comment 39

[IU]

I see what's going on.  You're confusing bug 803940 with bug 803579.

Comment 40

[Boris Zbarsky [:bzbarsky]]

> I see what's going on.  You're confusing bug 803940 with bug 803579.

Ah, indeed.  My apologies.  :(

Comment 41

[Boris Zbarsky [:bzbarsky]]

Though in all fairness, it would have helped a lot if you'd actually cced me on bug 803579...

Comment 42

[IU]

(In reply to Boris Zbarsky (:bz) from comment #41)
> Though in all fairness, it would have helped a lot if you'd actually cced me
> on bug 803579...

I'll try and remember that.  Nevertheless, I do see that you are added to bug 803303 which, in all probability, is a dupe, so I'll leave that up to you. :-)