Home | History | Annotate | Download | only in scheduler 
      1 // Copyright 2011 The Chromium Authors. All rights reserved.
      2 // Use of this source code is governed by a BSD-style license that can be
      3 // found in the LICENSE file.
      4 
      5 #include "cc/scheduler/delay_based_time_source.h"
      6 
      7 #include <algorithm>
      8 #include <cmath>
      9 
     10 #include "base/bind.h"
     11 #include "base/debug/trace_event.h"
     12 #include "base/location.h"
     13 #include "base/logging.h"
     14 #include "base/single_thread_task_runner.h"
     15 
     16 namespace cc {
     17 
     18 namespace {
     19 
     20 // kDoubleTickThreshold prevents ticks from running within the specified
     21 // fraction of an interval.  This helps account for jitter in the timebase as
     22 // well as quick timer reactivation.
     23 static const double kDoubleTickThreshold = 0.25;
     24 
     25 // kIntervalChangeThreshold is the fraction of the interval that will trigger an
     26 // immediate interval change.  kPhaseChangeThreshold is the fraction of the
     27 // interval that will trigger an immediate phase change.  If the changes are
     28 // within the thresholds, the change will take place on the next tick.  If
     29 // either change is outside the thresholds, the next tick will be canceled and
     30 // reissued immediately.
     31 static const double kIntervalChangeThreshold = 0.25;
     32 static const double kPhaseChangeThreshold = 0.25;
     33 
     34 }  // namespace
     35 
     36 scoped_refptr<DelayBasedTimeSource> DelayBasedTimeSource::Create(
     37     base::TimeDelta interval,
     38     base::SingleThreadTaskRunner* task_runner) {
     39   return make_scoped_refptr(new DelayBasedTimeSource(interval, task_runner));
     40 }
     41 
     42 DelayBasedTimeSource::DelayBasedTimeSource(
     43     base::TimeDelta interval, base::SingleThreadTaskRunner* task_runner)
     44     : client_(NULL),
     45       has_tick_target_(false),
     46       current_parameters_(interval, base::TimeTicks()),
     47       next_parameters_(interval, base::TimeTicks()),
     48       state_(STATE_INACTIVE),
     49       task_runner_(task_runner),
     50       weak_factory_(this) {}
     51 
     52 DelayBasedTimeSource::~DelayBasedTimeSource() {}
     53 
     54 void DelayBasedTimeSource::SetActive(bool active) {
     55   TRACE_EVENT1("cc", "DelayBasedTimeSource::SetActive", "active", active);
     56   if (!active) {
     57     state_ = STATE_INACTIVE;
     58     weak_factory_.InvalidateWeakPtrs();
     59     return;
     60   }
     61 
     62   if (state_ == STATE_STARTING || state_ == STATE_ACTIVE)
     63     return;
     64 
     65   if (!has_tick_target_) {
     66     // Becoming active the first time is deferred: we post a 0-delay task.
     67     // When it runs, we use that to establish the timebase, become truly
     68     // active, and fire the first tick.
     69     state_ = STATE_STARTING;
     70     task_runner_->PostTask(FROM_HERE,
     71                            base::Bind(&DelayBasedTimeSource::OnTimerFired,
     72                                       weak_factory_.GetWeakPtr()));
     73     return;
     74   }
     75 
     76   state_ = STATE_ACTIVE;
     77 
     78   PostNextTickTask(Now());
     79 }
     80 
     81 bool DelayBasedTimeSource::Active() const { return state_ != STATE_INACTIVE; }
     82 
     83 base::TimeTicks DelayBasedTimeSource::LastTickTime() { return last_tick_time_; }
     84 
     85 base::TimeTicks DelayBasedTimeSource::NextTickTime() {
     86   return Active() ? current_parameters_.tick_target : base::TimeTicks();
     87 }
     88 
     89 void DelayBasedTimeSource::OnTimerFired() {
     90   DCHECK(state_ != STATE_INACTIVE);
     91 
     92   base::TimeTicks now = this->Now();
     93   last_tick_time_ = now;
     94 
     95   if (state_ == STATE_STARTING) {
     96     SetTimebaseAndInterval(now, current_parameters_.interval);
     97     state_ = STATE_ACTIVE;
     98   }
     99 
    100   PostNextTickTask(now);
    101 
    102   // Fire the tick.
    103   if (client_)
    104     client_->OnTimerTick();
    105 }
    106 
    107 void DelayBasedTimeSource::SetClient(TimeSourceClient* client) {
    108   client_ = client;
    109 }
    110 
    111 void DelayBasedTimeSource::SetTimebaseAndInterval(base::TimeTicks timebase,
    112                                                   base::TimeDelta interval) {
    113   next_parameters_.interval = interval;
    114   next_parameters_.tick_target = timebase;
    115   has_tick_target_ = true;
    116 
    117   if (state_ != STATE_ACTIVE) {
    118     // If we aren't active, there's no need to reset the timer.
    119     return;
    120   }
    121 
    122   // If the change in interval is larger than the change threshold,
    123   // request an immediate reset.
    124   double interval_delta =
    125       std::abs((interval - current_parameters_.interval).InSecondsF());
    126   double interval_change = interval_delta / interval.InSecondsF();
    127   if (interval_change > kIntervalChangeThreshold) {
    128     SetActive(false);
    129     SetActive(true);
    130     return;
    131   }
    132 
    133   // If the change in phase is greater than the change threshold in either
    134   // direction, request an immediate reset. This logic might result in a false
    135   // negative if there is a simultaneous small change in the interval and the
    136   // fmod just happens to return something near zero. Assuming the timebase
    137   // is very recent though, which it should be, we'll still be ok because the
    138   // old clock and new clock just happen to line up.
    139   double target_delta =
    140       std::abs((timebase - current_parameters_.tick_target).InSecondsF());
    141   double phase_change =
    142       fmod(target_delta, interval.InSecondsF()) / interval.InSecondsF();
    143   if (phase_change > kPhaseChangeThreshold &&
    144       phase_change < (1.0 - kPhaseChangeThreshold)) {
    145     SetActive(false);
    146     SetActive(true);
    147     return;
    148   }
    149 }
    150 
    151 base::TimeTicks DelayBasedTimeSource::Now() const {
    152   return base::TimeTicks::Now();
    153 }
    154 
    155 // This code tries to achieve an average tick rate as close to interval_ as
    156 // possible.  To do this, it has to deal with a few basic issues:
    157 //   1. PostDelayedTask can delay only at a millisecond granularity. So, 16.666
    158 //   has to posted as 16 or 17.
    159 //   2. A delayed task may come back a bit late (a few ms), or really late
    160 //   (frames later)
    161 //
    162 // The basic idea with this scheduler here is to keep track of where we *want*
    163 // to run in tick_target_. We update this with the exact interval.
    164 //
    165 // Then, when we post our task, we take the floor of (tick_target_ and Now()).
    166 // If we started at now=0, and 60FPs (all times in milliseconds):
    167 //      now=0    target=16.667   PostDelayedTask(16)
    168 //
    169 // When our callback runs, we figure out how far off we were from that goal.
    170 // Because of the flooring operation, and assuming our timer runs exactly when
    171 // it should, this yields:
    172 //      now=16   target=16.667
    173 //
    174 // Since we can't post a 0.667 ms task to get to now=16, we just treat this as a
    175 // tick. Then, we update target to be 33.333. We now post another task based on
    176 // the difference between our target and now:
    177 //      now=16   tick_target=16.667  new_target=33.333   -->
    178 //          PostDelayedTask(floor(33.333 - 16)) --> PostDelayedTask(17)
    179 //
    180 // Over time, with no late tasks, this leads to us posting tasks like this:
    181 //      now=0    tick_target=0       new_target=16.667   -->
    182 //          tick(), PostDelayedTask(16)
    183 //      now=16   tick_target=16.667  new_target=33.333   -->
    184 //          tick(), PostDelayedTask(17)
    185 //      now=33   tick_target=33.333  new_target=50.000   -->
    186 //          tick(), PostDelayedTask(17)
    187 //      now=50   tick_target=50.000  new_target=66.667   -->
    188 //          tick(), PostDelayedTask(16)
    189 //
    190 // We treat delays in tasks differently depending on the amount of delay we
    191 // encounter. Suppose we posted a task with a target=16.667:
    192 //   Case 1: late but not unrecoverably-so
    193 //      now=18 tick_target=16.667
    194 //
    195 //   Case 2: so late we obviously missed the tick
    196 //      now=25.0 tick_target=16.667
    197 //
    198 // We treat the first case as a tick anyway, and assume the delay was unusual.
    199 // Thus, we compute the new_target based on the old timebase:
    200 //      now=18   tick_target=16.667  new_target=33.333   -->
    201 //          tick(), PostDelayedTask(floor(33.333-18)) --> PostDelayedTask(15)
    202 // This brings us back to 18+15 = 33, which was where we would have been if the
    203 // task hadn't been late.
    204 //
    205 // For the really late delay, we we move to the next logical tick. The timebase
    206 // is not reset.
    207 //      now=37   tick_target=16.667  new_target=50.000  -->
    208 //          tick(), PostDelayedTask(floor(50.000-37)) --> PostDelayedTask(13)
    209 base::TimeTicks DelayBasedTimeSource::NextTickTarget(base::TimeTicks now) {
    210   base::TimeDelta new_interval = next_parameters_.interval;
    211   int intervals_elapsed =
    212       static_cast<int>(floor((now - next_parameters_.tick_target).InSecondsF() /
    213                              new_interval.InSecondsF()));
    214   base::TimeTicks last_effective_tick =
    215       next_parameters_.tick_target + new_interval * intervals_elapsed;
    216   base::TimeTicks new_tick_target = last_effective_tick + new_interval;
    217   DCHECK(now < new_tick_target)
    218       << "now = " << now.ToInternalValue()
    219       << "; new_tick_target = " << new_tick_target.ToInternalValue()
    220       << "; new_interval = " << new_interval.InMicroseconds()
    221       << "; tick_target = " << next_parameters_.tick_target.ToInternalValue()
    222       << "; intervals_elapsed = " << intervals_elapsed
    223       << "; last_effective_tick = " << last_effective_tick.ToInternalValue();
    224 
    225   // Avoid double ticks when:
    226   // 1) Turning off the timer and turning it right back on.
    227   // 2) Jittery data is passed to SetTimebaseAndInterval().
    228   if (new_tick_target - last_tick_time_ <=
    229       new_interval / static_cast<int>(1.0 / kDoubleTickThreshold))
    230     new_tick_target += new_interval;
    231 
    232   return new_tick_target;
    233 }
    234 
    235 void DelayBasedTimeSource::PostNextTickTask(base::TimeTicks now) {
    236   base::TimeTicks new_tick_target = NextTickTarget(now);
    237 
    238   // Post another task *before* the tick and update state
    239   base::TimeDelta delay = new_tick_target - now;
    240   DCHECK(delay.InMillisecondsF() <=
    241          next_parameters_.interval.InMillisecondsF() *
    242          (1.0 + kDoubleTickThreshold));
    243   task_runner_->PostDelayedTask(FROM_HERE,
    244                                 base::Bind(&DelayBasedTimeSource::OnTimerFired,
    245                                            weak_factory_.GetWeakPtr()),
    246                                 delay);
    247 
    248   next_parameters_.tick_target = new_tick_target;
    249   current_parameters_ = next_parameters_;
    250 }
    251 
    252 }  // namespace cc
    253