Find freezes for quite long on a certain website

RESOLVED FIXED in mozilla19

Status

()

Core
Find Backend
--
critical
RESOLVED FIXED
6 years ago
5 years ago

People

(Reporter: d, Assigned: bz)

Tracking

({hang})

13 Branch
mozilla19
x86
Windows 7
Points:
---
Dependency tree / graph
Bug Flags:
in-testsuite ?

Firefox Tracking Flags

(Not tracked)

Details

Attachments

(2 attachments, 1 obsolete attachment)

(Reporter)

Description

6 years ago
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.
(Reporter)

Updated

6 years ago
See Also: → bug 435810

Comment 1

6 years ago
This may also be related to bug 429732 and/or bug 251862, which are about Firefox freezing when highlighting matches.
(Reporter)

Comment 2

6 years ago
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.
Does starting Firefox in safe mode help?
Firefox -> Help -> Restart with add-ons disabled
(Reporter)

Comment 4

6 years ago
Yes. Why don't you try it on your side?
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.
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.
Severity: normal → critical
Status: UNCONFIRMED → NEW
Component: Untriaged → General
Ever confirmed: true
Product: Firefox → Core
(Reporter)

Comment 7

6 years ago
Sorry I misread your question... I actually meant restarting in safe mode still causes the problem.
(Reporter)

Comment 8

6 years ago
For info, I have confirmed it on Firefox 13 on Windows 7, Firefox 13 on Windows XP and Firefox 5 on Windows XP.
The Profile isn't very useful
http://people.mozilla.com/~bgirard/cleopatra/?report=06a0e293d75dfa12f37377a9c78634e07ab0a744

mcsmurf could reproduce this with Seamonkey
Component: General → Find Backend
Keywords: hang
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
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!
Component: Find Backend → Layout
Actually now that I look at it again, probably related to/dupe of the bugs mentioned in Comment 1 (Bug 429732, Bug 251862)
Eh, sorry, forget Comment 12...
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.
Component: Layout → Find Backend
(Reporter)

Comment 15

6 years ago
Created attachment 647080 [details]
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.
(Reporter)

Updated

6 years ago
Attachment #647080 - Attachment mime type: text/plain → text/html
(Reporter)

Comment 16

6 years ago
Created attachment 647085 [details]
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.
Attachment #647080 - Attachment is obsolete: true
(Reporter)

Updated

6 years ago
Attachment #647085 - Attachment mime type: text/plain → text/html
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?
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.
Created attachment 667777 [details] [diff] [review]
Don't keep looking forward for the first visible range and then just ignoring it.
Attachment #667777 - Flags: review?(masayuki)
Assignee: nobody → bzbarsky
Whiteboard: [need review]
bz:

Why did you request the review to me? I don't touch the find module for several years...
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.  :(
(Reporter)

Comment 22

6 years ago
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.
Masayuki-san, if you're not planning to review his, please do let me know and I'll look for someone else.
Oops, I'm sorry. I didn't realize your replay. Okay, I try to review it today.
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...
Attachment #667777 - Flags: review?(masayuki) → review+
> 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!
(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.
Ah, ok.  I appreciate that.  And yeah, the name is not great.  :(
https://hg.mozilla.org/integration/mozilla-inbound/rev/2efb9e5762ce
Flags: in-testsuite?
Whiteboard: [need review]
Target Milestone: --- → mozilla19
https://hg.mozilla.org/mozilla-central/rev/2efb9e5762ce
Status: NEW → RESOLVED
Last Resolved: 5 years ago
Resolution: --- → FIXED
(Reporter)

Comment 31

5 years ago
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...
> 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.
(Reporter)

Comment 33

5 years ago
Ok. See Bug #803940.

Updated

5 years ago
Depends on: 803579
No longer depends on: 803579

Comment 34

5 years ago
My is the block removed?  This caused the regression, or am I missing something?
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

5 years ago
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.
> 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

5 years ago
(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

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

Updated

5 years ago
Depends on: 803579

Updated

5 years ago
Depends on: 803303
> I see what's going on.  You're confusing bug 803940 with bug 803579.

Ah, indeed.  My apologies.  :(
Though in all fairness, it would have helped a lot if you'd actually cced me on bug 803579...

Comment 42

5 years ago
(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. :-)

Updated

5 years ago
Depends on: 804799

Updated

5 years ago
Duplicate of this bug: 833781
You need to log in before you can comment on or make changes to this bug.