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

Status: RESOLVED FIXED

(Core :: DOM: Core & HTML, enhancement)

Description

[Ben Kelly [:bkelly, not reviewing]]

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.

Comment 1

[Ben Kelly [:bkelly, not reviewing]]

Attachment: P1 Stop iterating in TimeoutManager::RunTimeout() when we see an invalid firing ID. r=ehsan

Comment 2

[Ben Kelly [:bkelly, not reviewing]]

Attachment: P2 Remove TimeoutManager::RunTimeout()'s last expired timeout reference. r=ehsan

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

Comment 3

[Ben Kelly [:bkelly, not reviewing]]

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.

Comment 4

[Ben Kelly [:bkelly, not reviewing]]

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.

Comment 5

[(no longer active)]

(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!

Comment 6

[(no longer active)]

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!

Comment 7

[Pulsebot]

Pushed by [e-mail]:
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

[Wes Kocher (:KWierso) (Not reading bugmail; email directly if needed)]

https://hg.mozilla.org/mozilla-central/rev/505c2ccffae3
https://hg.mozilla.org/mozilla-central/rev/e3fbe145dafc