Closed Bug 1370537 Opened 2 years ago Closed 2 years ago

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

Categories

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

enhancement
Not set

Tracking

()

RESOLVED FIXED
mozilla55
Tracking Status
firefox55 --- fixed

People

(Reporter: bkelly, Assigned: bkelly)

Details

Attachments

(2 files)

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 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)
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)
(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!
Attachment #8874868 - Flags: review?(ehsan) → review+
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+
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
https://hg.mozilla.org/mozilla-central/rev/505c2ccffae3
https://hg.mozilla.org/mozilla-central/rev/e3fbe145dafc
Status: ASSIGNED → RESOLVED
Closed: 2 years ago
Resolution: --- → FIXED
Target Milestone: --- → mozilla55
Component: DOM → DOM: Core & HTML
You need to log in before you can comment on or make changes to this bug.