TimeoutManager::RunTimeout() should not over-iterate if last expired timeout is canceled before its executed

RESOLVED FIXED in Firefox 55

Status

()

Core
DOM
RESOLVED FIXED
11 months ago
11 months ago

People

(Reporter: bkelly, Assigned: bkelly)

Tracking

unspecified
mozilla55
Points:
---

Firefox Tracking Flags

(firefox55 fixed)

Details

Attachments

(2 attachments)

(Assignee)

Description

11 months ago
We currently have a subtle de-optimization bug in TimeoutManager::RunTimeout().  Consider this list of timers:

* Timeout f() at time t
* Timeout g() at time t
* Timeout h() at time t
* One thousand timeouts at times > t

When RunTimeout() executes at time t it will select Timeout h() as its "last_expired_*_timeout".  It will then start executing them in order until Timeout h() has been executed.

Consider, though, what happens if Timeout f() calls `clearTimeout(hID)` using Timeout h()'s id?  Timeout h() will be removed from the list.  The second loop will never see it.

In this case we will iterate the entire timeout list.  We won't actually fire anything additional because of the firing ID check, but we will waste time iterating a potentially large list.

We should fix this code not to depend on data that can be mutated by javascript handlers.
(Assignee)

Comment 1

11 months ago
Created attachment 8874868 [details] [diff] [review]
P1 Stop iterating in TimeoutManager::RunTimeout() when we see an invalid firing ID. r=ehsan
(Assignee)

Comment 2

11 months ago
Created attachment 8874869 [details] [diff] [review]
P2 Remove TimeoutManager::RunTimeout()'s last expired timeout reference. r=ehsan

https://treeherder.mozilla.org/#/jobs?repo=try&revision=3d30fa4b5d9d9f58abd9037a27cc81c29a06cc3b
(Assignee)

Comment 3

11 months ago
Comment on attachment 8874868 [details] [diff] [review]
P1 Stop iterating in TimeoutManager::RunTimeout() when we see an invalid firing ID. r=ehsan

See comment 0 for a description of the problem.  The short version, though, is the sentinal values we pass to the iterator can be removed by a clearTimeout() in a callback handler.

This patch makes us terminate the RunTimeout() loop if we start seeing invalid FiringIds.  Since we don't let new Timeouts get inserted before valid FiringIds we should only see invalid ids if we iterate past our list of expired Timeouts.
Attachment #8874868 - Flags: review?(ehsan)
(Assignee)

Comment 4

11 months ago
Comment on attachment 8874869 [details] [diff] [review]
P2 Remove TimeoutManager::RunTimeout()'s last expired timeout reference. r=ehsan

This patch removes the "StopAt" iteration sentinal code completely.  As descrived previously it doesn't work in all situations.  It also adds to the complexity of the code which is already pretty complex.  Lets simplify by removing it.

To modify the code here I converted statements to function just as they would if StopAt was set to nullptr.
Attachment #8874869 - Flags: review?(ehsan)

Comment 5

11 months ago
(In reply to Ben Kelly [reviewing, but slowly][:bkelly] from comment #0)
> We currently have a subtle de-optimization bug in
> TimeoutManager::RunTimeout().  Consider this list of timers:
> 
> * Timeout f() at time t
> * Timeout g() at time t
> * Timeout h() at time t
> * One thousand timeouts at times > t
> 
> When RunTimeout() executes at time t it will select Timeout h() as its
> "last_expired_*_timeout".  It will then start executing them in order until
> Timeout h() has been executed.
> 
> Consider, though, what happens if Timeout f() calls `clearTimeout(hID)`
> using Timeout h()'s id?  Timeout h() will be removed from the list.  The
> second loop will never see it.
> 
> In this case we will iterate the entire timeout list.  We won't actually
> fire anything additional because of the firing ID check, but we will waste
> time iterating a potentially large list.

Nice find!

Updated

11 months ago
Attachment #8874868 - Flags: review?(ehsan) → review+

Comment 6

11 months ago
Comment on attachment 8874869 [details] [diff] [review]
P2 Remove TimeoutManager::RunTimeout()'s last expired timeout reference. r=ehsan

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

Great!
Attachment #8874869 - Flags: review?(ehsan) → review+

Comment 7

11 months ago
Pushed by bkelly@mozilla.com:
https://hg.mozilla.org/integration/mozilla-inbound/rev/505c2ccffae3
P1 Stop iterating in TimeoutManager::RunTimeout() when we see an invalid firing ID. r=ehsan
https://hg.mozilla.org/integration/mozilla-inbound/rev/e3fbe145dafc
P2 Remove TimeoutManager::RunTimeout()'s last expired timeout reference. r=ehsan

Comment 8

11 months ago
bugherder
https://hg.mozilla.org/mozilla-central/rev/505c2ccffae3
https://hg.mozilla.org/mozilla-central/rev/e3fbe145dafc
Status: ASSIGNED → RESOLVED
Last Resolved: 11 months ago
status-firefox55: --- → fixed
Resolution: --- → FIXED
Target Milestone: --- → mozilla55
You need to log in before you can comment on or make changes to this bug.