Fix frame expiry with cadence based rendering.

Cadence based rendering never expired the last frame based on
calls to RemoveExpiredFrames.  Fixed and removed repeated calc
of end time everywhere in favor of stored calculation.

BUG=439548
TEST=modified tests.

Review URL: https://codereview.chromium.org/1116253005

Cr-Commit-Position: refs/heads/master@{#328230}

5 files changed, 103 insertions, 62 deletions

diff --git a/media/base/moving_average.cc b/media/base/moving_average.cc
index c8ca7dd..b78f4c0 100644
--- a/media/base/moving_average.cc
+++ b/media/base/moving_average.cc
@@ -29,7 +29,7 @@ base::TimeDelta MovingAverage::Average() const {
   // TODO(dalecurtis): Consider limiting |depth| to powers of two so that we can
   // replace the integer divide with a bit shift operation.
 
-  return total_ / std::min(depth_, count_);
+  return total_ / std::min(static_cast<uint64_t>(depth_), count_);
 }
 
 void MovingAverage::Reset() {
diff --git a/media/base/moving_average.h b/media/base/moving_average.h
index aa69750..18a934e 100644
--- a/media/base/moving_average.h
+++ b/media/base/moving_average.h
@@ -29,12 +29,14 @@ class MEDIA_EXPORT MovingAverage {
   // Resets the state of the class to its initial post-construction state.
   void Reset();
 
+  size_t count() const { return count_; }
+
  private:
   // Maximum number of elements allowed in the average.
   const size_t depth_;
 
   // Number of elements seen thus far.
-  size_t count_;
+  uint64_t count_;
 
   std::vector<base::TimeDelta> samples_;
   base::TimeDelta total_;
diff --git a/media/filters/video_renderer_algorithm.cc b/media/filters/video_renderer_algorithm.cc
index 0a2bc57..a78342a 100644
--- a/media/filters/video_renderer_algorithm.cc
+++ b/media/filters/video_renderer_algorithm.cc
@@ -80,7 +80,7 @@ scoped_refptr<VideoFrame> VideoRendererAlgorithm::Render(
     // If duration is unknown, we don't have enough frames to make a good guess
     // about which frame to use, so always choose the first.
     if (average_frame_duration_ == base::TimeDelta() &&
-        !ready_frame.wall_clock_time.is_null()) {
+        !ready_frame.start_time.is_null()) {
       ++ready_frame.render_count;
     }
 
@@ -173,7 +173,7 @@ scoped_refptr<VideoFrame> VideoRendererAlgorithm::Render(
 
         DVLOG(2) << "Dropping unrendered (or always dropped) frame "
                  << frame.frame->timestamp()
-                 << ", wall clock: " << frame.wall_clock_time.ToInternalValue()
+                 << ", wall clock: " << frame.start_time.ToInternalValue()
                  << " (" << frame.render_count << ", " << frame.drop_count
                  << ")";
         ++(*frames_dropped);
@@ -215,10 +215,10 @@ size_t VideoRendererAlgorithm::RemoveExpiredFrames(base::TimeTicks deadline) {
   // their render interval is further than |max_acceptable_drift_| from the
   // given |deadline|.
   size_t frames_to_expire = 0;
-  const base::TimeTicks minimum_frame_time =
+  const base::TimeTicks minimum_start_time =
       deadline - max_acceptable_drift_ - average_frame_duration_;
   for (; frames_to_expire < frame_queue_.size() - 1; ++frames_to_expire) {
-    if (frame_queue_[frames_to_expire].wall_clock_time >= minimum_frame_time)
+    if (frame_queue_[frames_to_expire].start_time >= minimum_start_time)
       break;
   }
 
@@ -235,12 +235,16 @@ size_t VideoRendererAlgorithm::RemoveExpiredFrames(base::TimeTicks deadline) {
 }
 
 void VideoRendererAlgorithm::OnLastFrameDropped() {
-  DCHECK(have_rendered_frames_);
-  DCHECK(!frame_queue_.empty());
+  // Since compositing is disconnected from the algorithm, the algorithm may be
+  // Reset() in between ticks of the compositor, so discard notifications which
+  // are invalid.
+  //
   // If frames were expired by RemoveExpiredFrames() this count may be zero when
   // the OnLastFrameDropped() call comes in.
-  if (!frame_queue_[last_frame_index_].render_count)
+  if (!have_rendered_frames_ || frame_queue_.empty() ||
+      !frame_queue_[last_frame_index_].render_count) {
     return;
+  }
 
   ++frame_queue_[last_frame_index_].drop_count;
   DCHECK_LE(frame_queue_[last_frame_index_].drop_count,
@@ -273,10 +277,9 @@ size_t VideoRendererAlgorithm::EffectiveFramesQueued() const {
     size_t expired_frames = last_frame_index_;
     DCHECK_LT(last_frame_index_, frame_queue_.size());
     for (; expired_frames < frame_queue_.size(); ++expired_frames) {
-      if (frame_queue_[expired_frames].wall_clock_time.is_null() ||
-          EndTimeForFrame(expired_frames) > last_deadline_max_) {
+      const ReadyFrame& frame = frame_queue_[expired_frames];
+      if (frame.end_time.is_null() || frame.end_time > last_deadline_max_)
         break;
-      }
     }
     return frame_queue_.size() - expired_frames;
   }
@@ -286,10 +289,15 @@ size_t VideoRendererAlgorithm::EffectiveFramesQueued() const {
   if (start_index < 0)
     return 0;
 
+  const base::TimeTicks minimum_start_time =
+      last_deadline_max_ - max_acceptable_drift_;
   size_t renderable_frame_count = 0;
   for (size_t i = start_index; i < frame_queue_.size(); ++i) {
-    if (frame_queue_[i].render_count < frame_queue_[i].ideal_render_count)
+    const ReadyFrame& frame = frame_queue_[i];
+    if (frame.render_count < frame.ideal_render_count &&
+        (frame.end_time.is_null() || frame.end_time > minimum_start_time)) {
       ++renderable_frame_count;
+    }
   }
 
   return renderable_frame_count;
@@ -372,34 +380,39 @@ bool VideoRendererAlgorithm::UpdateFrameStatistics() {
   // relative to real time as the code below executes.
   for (size_t i = 0; i < frame_queue_.size(); ++i) {
     ReadyFrame& frame = frame_queue_[i];
-    const bool new_frame = frame.wall_clock_time.is_null();
-    frame.wall_clock_time = time_converter_cb_.Run(frame.frame->timestamp());
+    const bool new_frame = frame.start_time.is_null();
+    frame.start_time = time_converter_cb_.Run(frame.frame->timestamp());
 
     // If time stops or never started, exit immediately.
-    if (frame.wall_clock_time.is_null())
+    if (frame.start_time.is_null()) {
+      frame.end_time = base::TimeTicks();
       return false;
+    }
 
     // TODO(dalecurtis): An unlucky tick of a playback rate change could cause
     // this to skew so much that time goes backwards between calls.  Fix this by
     // either converting all timestamps at once or with some retry logic.
     if (i > 0) {
+      frame_queue_[i - 1].end_time = frame.start_time;
       const base::TimeDelta delta =
-          frame.wall_clock_time - frame_queue_[i - 1].wall_clock_time;
+          frame.start_time - frame_queue_[i - 1].start_time;
       CHECK_GT(delta, base::TimeDelta());
       if (new_frame)
         frame_duration_calculator_.AddSample(delta);
     }
   }
 
-  // Do we have enough frames to compute statistics?
-  const bool have_frame_duration = average_frame_duration_ != base::TimeDelta();
-  if (frame_queue_.size() < 2 && !have_frame_duration)
+  if (!frame_duration_calculator_.count())
     return false;
 
   // Compute |average_frame_duration_|, a moving average of the last few frames;
   // see kMovingAverageSamples for the exact number.
   average_frame_duration_ = frame_duration_calculator_.Average();
 
+  // Update the frame end time for the last frame based on the average.
+  frame_queue_.back().end_time =
+      frame_queue_.back().start_time + average_frame_duration_;
+
   // ITU-R BR.265 recommends a maximum acceptable drift of +/- half of the frame
   // duration; there are other asymmetric, more lenient measures, that we're
   // forgoing in favor of simplicity.
@@ -513,23 +526,23 @@ int VideoRendererAlgorithm::FindBestFrameByCoverage(
   base::TimeDelta best_coverage;
   std::vector<base::TimeDelta> coverage(frame_queue_.size(), base::TimeDelta());
   for (size_t i = last_frame_index_; i < frame_queue_.size(); ++i) {
+    const ReadyFrame& frame = frame_queue_[i];
+
     // Frames which start after the deadline interval have zero coverage.
-    if (frame_queue_[i].wall_clock_time > deadline_max)
+    if (frame.start_time > deadline_max)
       break;
 
     // Clamp frame end times to a maximum of |deadline_max|.
-    const base::TimeTicks frame_end_time =
-        std::min(deadline_max, EndTimeForFrame(i));
+    const base::TimeTicks end_time = std::min(deadline_max, frame.end_time);
 
     // Frames entirely before the deadline interval have zero coverage.
-    if (frame_end_time < deadline_min)
+    if (end_time < deadline_min)
       continue;
 
     // If we're here, the current frame overlaps the deadline in some way; so
     // compute the duration of the interval which is covered.
     const base::TimeDelta duration =
-        frame_end_time -
-        std::max(deadline_min, frame_queue_[i].wall_clock_time);
+        end_time - std::max(deadline_min, frame.start_time);
 
     coverage[i] = duration;
     if (coverage[i] > best_coverage) {
@@ -596,32 +609,21 @@ int VideoRendererAlgorithm::FindBestFrameByDrift(
 base::TimeDelta VideoRendererAlgorithm::CalculateAbsoluteDriftForFrame(
     base::TimeTicks deadline_min,
     int frame_index) const {
+  const ReadyFrame& frame = frame_queue_[frame_index];
   // If the frame lies before the deadline, compute the delta against the end
   // of the frame's duration.
-  const base::TimeTicks frame_end_time = EndTimeForFrame(frame_index);
-  if (frame_end_time < deadline_min)
-    return deadline_min - frame_end_time;
+  if (frame.end_time < deadline_min)
+    return deadline_min - frame.end_time;
 
   // If the frame lies after the deadline, compute the delta against the frame's
-  // wall clock time.
-  const ReadyFrame& frame = frame_queue_[frame_index];
-  if (frame.wall_clock_time > deadline_min)
-    return frame.wall_clock_time - deadline_min;
+  // start time.
+  if (frame.start_time > deadline_min)
+    return frame.start_time - deadline_min;
 
   // Drift is zero for frames which overlap the deadline interval.
-  DCHECK_GE(deadline_min, frame.wall_clock_time);
-  DCHECK_GE(frame_end_time, deadline_min);
+  DCHECK_GE(deadline_min, frame.start_time);
+  DCHECK_GE(frame.end_time, deadline_min);
   return base::TimeDelta();
 }
 
-base::TimeTicks VideoRendererAlgorithm::EndTimeForFrame(
-    size_t frame_index) const {
-  DCHECK_LT(frame_index, frame_queue_.size());
-  DCHECK_GT(average_frame_duration_, base::TimeDelta());
-  return frame_index + 1 < frame_queue_.size()
-             ? frame_queue_[frame_index + 1].wall_clock_time
-             : frame_queue_[frame_index].wall_clock_time +
-                   average_frame_duration_;
-}
-
 }  // namespace media
diff --git a/media/filters/video_renderer_algorithm.h b/media/filters/video_renderer_algorithm.h
index 83276e7..61603b3 100644
--- a/media/filters/video_renderer_algorithm.h
+++ b/media/filters/video_renderer_algorithm.h
@@ -152,7 +152,12 @@ class MEDIA_EXPORT VideoRendererAlgorithm {
     bool operator<(const ReadyFrame& other) const;
 
     scoped_refptr<VideoFrame> frame;
-    base::TimeTicks wall_clock_time;
+
+    // |start_time| is only available after UpdateFrameStatistics() has been
+    // called and |end_time| only after we have more than one frame.
+    base::TimeTicks start_time;
+    base::TimeTicks end_time;
+
     int ideal_render_count;
     int render_count;
     int drop_count;
@@ -219,18 +224,14 @@ class MEDIA_EXPORT VideoRendererAlgorithm {
                            base::TimeDelta* selected_frame_drift) const;
 
   // Calculates the drift from |deadline_min| for the given |frame_index|.  If
-  // the [wall_clock_time, wall_clock_time + average_frame_duration_] lies
-  // before |deadline_min| the drift is the delta between |deadline_min| and
-  // |wall_clock_time + average_frame_duration_|. If the frame overlaps
-  // |deadline_min| the drift is zero. If the frame lies after |deadline_min|
-  // the drift is the delta between |deadline_min| and |wall_clock_time|.
+  // the [start_time, end_time] lies before |deadline_min| the drift is
+  // the delta between |deadline_min| and |end_time|. If the frame
+  // overlaps |deadline_min| the drift is zero. If the frame lies after
+  // |deadline_min| the drift is the delta between |deadline_min| and
+  // |start_time|.
   base::TimeDelta CalculateAbsoluteDriftForFrame(base::TimeTicks deadline_min,
                                                  int frame_index) const;
 
-  // Returns the wall clock time of the next frame if it exists, otherwise it
-  // returns the time of the requested frame plus |average_frame_duration_|.
-  base::TimeTicks EndTimeForFrame(size_t frame_index) const;
-
   // Queue of incoming frames waiting for rendering.
   using VideoFrameQueue = std::deque<ReadyFrame>;
   VideoFrameQueue frame_queue_;
diff --git a/media/filters/video_renderer_algorithm_unittest.cc b/media/filters/video_renderer_algorithm_unittest.cc
index 9082d26..3fb658a 100644
--- a/media/filters/video_renderer_algorithm_unittest.cc
+++ b/media/filters/video_renderer_algorithm_unittest.cc
@@ -161,7 +161,7 @@ class VideoRendererAlgorithmTest : public testing::Test {
 
     const bool fresh_algorithm = !algorithm_.have_rendered_frames_;
 
-    base::TimeDelta last_frame_timestamp = kNoTimestamp();
+    base::TimeDelta last_start_timestamp = kNoTimestamp();
     bool should_use_cadence = false;
     int glitch_count = 0;
     const base::TimeTicks start_time = tick_clock_->NowTicks();
@@ -192,10 +192,10 @@ class VideoRendererAlgorithmTest : public testing::Test {
       // If we have a frame, the timestamps should always be monotonically
       // increasing.
       if (frame) {
-        if (last_frame_timestamp != kNoTimestamp())
-          ASSERT_LE(last_frame_timestamp, frame->timestamp());
+        if (last_start_timestamp != kNoTimestamp())
+          ASSERT_LE(last_start_timestamp, frame->timestamp());
         else
-          last_frame_timestamp = frame->timestamp();
+          last_start_timestamp = frame->timestamp();
       }
 
       // Only verify certain properties for fresh instances.
@@ -219,8 +219,9 @@ class VideoRendererAlgorithmTest : public testing::Test {
       // within the last render interval.
       if (!is_using_cadence() || !frames_queued() ||
           GetCurrentFrameDisplayCount() < GetCurrentFrameIdealDisplayCount()) {
-        ASSERT_EQ(GetUsableFrameCount(deadline_max),
-                  algorithm_.EffectiveFramesQueued());
+        ASSERT_NEAR(GetUsableFrameCount(deadline_max),
+                    algorithm_.EffectiveFramesQueued(),
+                    fresh_algorithm ? 0 : 1);
       } else if (is_using_cadence() && !IsUsingFractionalCadence()) {
         // If there was no glitch in the last render, the two queue sizes should
         // be off by exactly one frame; i.e., the current frame doesn't count.
@@ -293,7 +294,7 @@ class VideoRendererAlgorithmTest : public testing::Test {
       return frames_queued();
 
     for (size_t i = 0; i < frames_queued(); ++i)
-      if (algorithm_.EndTimeForFrame(i) > deadline_max)
+      if (algorithm_.frame_queue_[i].end_time > deadline_max)
         return frames_queued() - i;
     return 0;
   }
@@ -986,6 +987,41 @@ TEST_F(VideoRendererAlgorithmTest, RemoveExpiredFrames) {
   EXPECT_EQ(0u, algorithm_.EffectiveFramesQueued());
 }
 
+TEST_F(VideoRendererAlgorithmTest, RemoveExpiredFramesCadence) {
+  TickGenerator tg(tick_clock_->NowTicks(), 50);
+  disable_cadence_hysteresis();
+
+  algorithm_.EnqueueFrame(CreateFrame(tg.interval(0)));
+  algorithm_.EnqueueFrame(CreateFrame(tg.interval(1)));
+  algorithm_.EnqueueFrame(CreateFrame(tg.interval(2)));
+
+  ASSERT_EQ(0u, algorithm_.RemoveExpiredFrames(tg.current()));
+  EXPECT_EQ(3u, algorithm_.EffectiveFramesQueued());
+
+  time_source_.StartTicking();
+
+  size_t frames_dropped = 0;
+  scoped_refptr<VideoFrame> frame = RenderAndStep(&tg, &frames_dropped);
+  ASSERT_TRUE(frame);
+  EXPECT_EQ(tg.interval(0), frame->timestamp());
+  EXPECT_EQ(0u, frames_dropped);
+  ASSERT_TRUE(is_using_cadence());
+  EXPECT_EQ(2u, algorithm_.EffectiveFramesQueued());
+
+  // Advance expiry enough that some frames are removed, but one remains and is
+  // still counted as effective.
+  ASSERT_EQ(2u, algorithm_.RemoveExpiredFrames(tg.current() + tg.interval(1) +
+                                               max_acceptable_drift() * 1.25));
+  EXPECT_EQ(1u, frames_queued());
+  EXPECT_EQ(1u, algorithm_.EffectiveFramesQueued());
+
+  // Advancing expiry once more should mark the frame as ineffective.
+  tg.step(3);
+  ASSERT_EQ(0u, algorithm_.RemoveExpiredFrames(tg.current()));
+  EXPECT_EQ(1u, frames_queued());
+  EXPECT_EQ(0u, algorithm_.EffectiveFramesQueued());
+}
+
 TEST_F(VideoRendererAlgorithmTest, CadenceBasedTest) {
   // Common display rates.
   const double kDisplayRates[] = {