cc: Introduce BeginFrame sequence numbers and acknowledgements.

cc/scheduler/begin_frame_source.cc

 // Copyright 2014 The Chromium Authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 #include "cc/scheduler/begin_frame_source.h"
 
 #include <stddef.h>
 
+#include "base/atomic_sequence_num.h"
 #include "base/auto_reset.h"
 #include "base/location.h"
 #include "base/logging.h"
 #include "base/memory/ptr_util.h"
+#include "base/process/process_handle.h"
+#include "base/stl_util.h"
 #include "base/strings/string_number_conversions.h"
 #include "base/strings/stringprintf.h"
 #include "base/trace_event/trace_event.h"
 #include "base/trace_event/trace_event_argument.h"
 #include "cc/scheduler/delay_based_time_source.h"
 #include "cc/scheduler/scheduler.h"
 
 namespace cc {
 
 namespace {
 // kDoubleTickDivisor prevents the SyntheticBFS from sending BeginFrames too
 // often to an observer.
 static const double kDoubleTickDivisor = 2.0;
 }
 
-// BeginFrameObserverBase -----------------------------------------------
+// BeginFrameObserverBase -------------------------------------------------
 BeginFrameObserverBase::BeginFrameObserverBase()
-    : last_begin_frame_args_(), dropped_begin_frame_args_(0) {
-}
+    : last_begin_frame_args_(), dropped_begin_frame_args_(0) {}
 
 const BeginFrameArgs& BeginFrameObserverBase::LastUsedBeginFrameArgs() const {
   return last_begin_frame_args_;
 }
+
 void BeginFrameObserverBase::OnBeginFrame(const BeginFrameArgs& args) {
-  DCHECK(args.IsValid());
+  DCHECK(args.IsValid()) << "args: " << BeginFrameArgs::TypeToString(args.type)
+                         << " " << args.source_id << " " << args.sequence_number
+                         << " " << args.frame_time.ToInternalValue() << " "
+                         << args.interval.ToInternalValue() << " "
+                         << args.deadline.ToInternalValue();
+  DCHECK(args.sequence_number > last_begin_frame_args_.sequence_number ||
+         args.source_id != last_begin_frame_args_.source_id);
   DCHECK(args.frame_time >= last_begin_frame_args_.frame_time);
   bool used = OnBeginFrameDerivedImpl(args);
   if (used) {
     last_begin_frame_args_ = args;
   } else {
     ++dropped_begin_frame_args_;
   }
 }
 
+// BeginFrameSource -------------------------------------------------------
+namespace {
+static base::StaticAtomicSequenceNumber next_source_id_;
+
+uint64_t CreateSourceId() {
+  // Create a FNV hash from the process id for XORing.
+  // See http://isthe.com/chongo/tech/comp/fnv/ for algorithm details.
+  const uint64_t kOffsetBasis = 14695981039346656037ull;
+  const uint64_t kFnvPrime = 1099511628211ull;
+  const uint64_t pid = static_cast<uint64_t>(base::GetUniqueIdForProcess());
+  const uint64_t process_id_hash = (kOffsetBasis ^ pid) * kFnvPrime;
+
+  const uint64_t source_id = static_cast<uint64_t>(next_source_id_.GetNext());
+  // Make source id unlikely to collide with other processes.
+  return source_id ^ process_id_hash;
+}
+}  // namespace
+
+BeginFrameSource::BeginFrameSource() : source_id_(CreateSourceId()) {}
+
+uint64_t BeginFrameSource::source_id() const {
+  return source_id_;
+}
+
+// StubBeginFrameSource ---------------------------------------------------
 bool StubBeginFrameSource::IsThrottled() const {
   return true;
 }
 
-// SyntheticBeginFrameSource ---------------------------------------------
+// SyntheticBeginFrameSource ----------------------------------------------
 SyntheticBeginFrameSource::~SyntheticBeginFrameSource() = default;
 
-// BackToBackBeginFrameSource --------------------------------------------
+// BackToBackBeginFrameSource ---------------------------------------------
 BackToBackBeginFrameSource::BackToBackBeginFrameSource(
     std::unique_ptr<DelayBasedTimeSource> time_source)
-    : time_source_(std::move(time_source)), weak_factory_(this) {
+    : time_source_(std::move(time_source)),
+      next_sequence_number_(1),
+      weak_factory_(this) {
   time_source_->SetClient(this);
   // The time_source_ ticks immediately, so we SetActive(true) for a single
   // tick when we need it, and keep it as SetActive(false) otherwise.
   time_source_->SetTimebaseAndInterval(base::TimeTicks(), base::TimeDelta());
 }
 
 BackToBackBeginFrameSource::~BackToBackBeginFrameSource() = default;
 
 void BackToBackBeginFrameSource::AddObserver(BeginFrameObserver* obs) {
   DCHECK(obs);
   DCHECK(observers_.find(obs) == observers_.end());
   observers_.insert(obs);
   pending_begin_frame_observers_.insert(obs);
   obs->OnBeginFrameSourcePausedChanged(false);
   time_source_->SetActive(true);
 }
 
 void BackToBackBeginFrameSource::RemoveObserver(BeginFrameObserver* obs) {
   DCHECK(obs);
   DCHECK(observers_.find(obs) != observers_.end());
   observers_.erase(obs);
   pending_begin_frame_observers_.erase(obs);
-  if (observers_.empty())
+  if (pending_begin_frame_observers_.empty())
     time_source_->SetActive(false);
 }
 
 void BackToBackBeginFrameSource::DidFinishFrame(BeginFrameObserver* obs,
-                                                size_t remaining_frames) {
-  if (remaining_frames == 0 && observers_.find(obs) != observers_.end()) {
+                                                const BeginFrameAck& ack) {
+  if (ack.remaining_frames == 0 && observers_.find(obs) != observers_.end()) {
     pending_begin_frame_observers_.insert(obs);
     time_source_->SetActive(true);
   }
 }
 
 bool BackToBackBeginFrameSource::IsThrottled() const {
   return false;
 }
 
 void BackToBackBeginFrameSource::OnTimerTick() {
   base::TimeTicks frame_time = time_source_->LastTickTime();
   base::TimeDelta default_interval = BeginFrameArgs::DefaultInterval();
   BeginFrameArgs args = BeginFrameArgs::Create(
-      BEGINFRAME_FROM_HERE, frame_time, frame_time + default_interval,
-      default_interval, BeginFrameArgs::NORMAL);
+      BEGINFRAME_FROM_HERE, source_id(), next_sequence_number_++, frame_time,
+      frame_time + default_interval, default_interval, BeginFrameArgs::NORMAL);
 
   // This must happen after getting the LastTickTime() from the time source.
   time_source_->SetActive(false);
 
   std::unordered_set<BeginFrameObserver*> pending_observers;
   pending_observers.swap(pending_begin_frame_observers_);
-  for (BeginFrameObserver* obs : pending_observers)
+  for (BeginFrameObserver* obs : pending_observers) {
     obs->OnBeginFrame(args);
+  }
 }
 
 // DelayBasedBeginFrameSource ---------------------------------------------
 DelayBasedBeginFrameSource::DelayBasedBeginFrameSource(
     std::unique_ptr<DelayBasedTimeSource> time_source)
-    : time_source_(std::move(time_source)) {
+    : time_source_(std::move(time_source)), current_sequence_number_(1) {
   time_source_->SetClient(this);
 }
 
 DelayBasedBeginFrameSource::~DelayBasedBeginFrameSource() = default;
 
 void DelayBasedBeginFrameSource::OnUpdateVSyncParameters(
     base::TimeTicks timebase,
     base::TimeDelta interval) {
   if (!authoritative_interval_.is_zero()) {
     interval = authoritative_interval_;
   } else if (interval.is_zero()) {
     // TODO(brianderson): We should not be receiving 0 intervals.
     interval = BeginFrameArgs::DefaultInterval();
   }
 
   last_timebase_ = timebase;
   time_source_->SetTimebaseAndInterval(timebase, interval);
 }
 
 void DelayBasedBeginFrameSource::SetAuthoritativeVSyncInterval(
     base::TimeDelta interval) {
   authoritative_interval_ = interval;
   OnUpdateVSyncParameters(last_timebase_, interval);
 }
 
 BeginFrameArgs DelayBasedBeginFrameSource::CreateBeginFrameArgs(
+    uint64_t sequence_number,
     base::TimeTicks frame_time,
     BeginFrameArgs::BeginFrameArgsType type) {
-  return BeginFrameArgs::Create(BEGINFRAME_FROM_HERE, frame_time,
-                                time_source_->NextTickTime(),
-                                time_source_->Interval(), type);
+  return BeginFrameArgs::Create(
+      BEGINFRAME_FROM_HERE, source_id(), sequence_number, frame_time,
+      time_source_->NextTickTime(), time_source_->Interval(), type);
 }
 
 void DelayBasedBeginFrameSource::AddObserver(BeginFrameObserver* obs) {
   DCHECK(obs);
   DCHECK(observers_.find(obs) == observers_.end());
 
   observers_.insert(obs);
   obs->OnBeginFrameSourcePausedChanged(false);
   time_source_->SetActive(true);
+  base::TimeTicks frame_time =
+      time_source_->NextTickTime() - time_source_->Interval();
+  if (current_begin_frame_time_ != frame_time) {
+    // Increment the sequence number if we are producing a frame that is
+    // different from the latest one we sent out.
+    current_sequence_number_++;
+    current_begin_frame_time_ = frame_time;
+  }
   BeginFrameArgs args = CreateBeginFrameArgs(
-      time_source_->NextTickTime() - time_source_->Interval(),
-      BeginFrameArgs::MISSED);
+      current_sequence_number_, frame_time, BeginFrameArgs::MISSED);
   BeginFrameArgs last_args = obs->LastUsedBeginFrameArgs();
   if (!last_args.IsValid() ||
       (args.frame_time >
        last_args.frame_time + args.interval / kDoubleTickDivisor)) {
     obs->OnBeginFrame(args);
   }
 }
 
 void DelayBasedBeginFrameSource::RemoveObserver(BeginFrameObserver* obs) {
   DCHECK(obs);
   DCHECK(observers_.find(obs) != observers_.end());
 
   observers_.erase(obs);
   if (observers_.empty())
     time_source_->SetActive(false);
 }
 
 bool DelayBasedBeginFrameSource::IsThrottled() const {
   return true;
 }
 
 void DelayBasedBeginFrameSource::OnTimerTick() {
-  BeginFrameArgs args = CreateBeginFrameArgs(time_source_->LastTickTime(),
+  BeginFrameArgs args = CreateBeginFrameArgs(++current_sequence_number_,
+                                             time_source_->LastTickTime(),
                                              BeginFrameArgs::NORMAL);
+  current_begin_frame_time_ = args.frame_time;
   std::unordered_set<BeginFrameObserver*> observers(observers_);
   for (auto* obs : observers) {
     BeginFrameArgs last_args = obs->LastUsedBeginFrameArgs();
     if (!last_args.IsValid() ||
         (args.frame_time >
          last_args.frame_time + args.interval / kDoubleTickDivisor))
       obs->OnBeginFrame(args);
   }
 }
 
+// BeginFrameObserverAckTracker -------------------------------------------
+BeginFrameObserverAckTracker::BeginFrameObserverAckTracker()
+    : current_source_id_(0),
+      current_sequence_number_(1),
+      observers_had_updates_(false) {}
+
+BeginFrameObserverAckTracker::~BeginFrameObserverAckTracker() {}
+
+void BeginFrameObserverAckTracker::OnBeginFrame(const BeginFrameArgs& args) {
+  if (current_source_id_ != args.source_id)
+    SourceChanged(args);
+
+  DCHECK_GE(args.sequence_number, current_sequence_number_);
+  // Reset for new BeginFrame.
+  current_sequence_number_ = args.sequence_number;
+  finished_observers_.clear();
+  observers_had_updates_ = false;
+}
+
+void BeginFrameObserverAckTracker::OnObserverBeginFrame(
+    BeginFrameObserver* obs,
+    const BeginFrameArgs& args) {
+  if (current_source_id_ != args.source_id)
+    SourceChanged(args);
+
+  DCHECK_EQ(args.sequence_number, current_sequence_number_);
+  // Observer may choose not to use the BeginFrame.
+  if (obs->LastUsedBeginFrameArgs().sequence_number != current_sequence_number_)
+    finished_observers_.insert(obs);
+}
+
+void BeginFrameObserverAckTracker::SourceChanged(const BeginFrameArgs& args) {
+  current_source_id_ = args.source_id;
+  current_sequence_number_ = args.sequence_number;
+
+  // We have no choice but to consider everyone up to date up to the last frame.
+  for (auto& entry : oldest_incorporated_frames_) {
+    entry.second = current_sequence_number_ - 1;
+  }
+}
+
+void BeginFrameObserverAckTracker::OnObserverFinishedFrame(
+    BeginFrameObserver* obs,
+    const BeginFrameAck& ack) {
+  if (ack.source_id != current_source_id_)
+    return;
+
+  DCHECK_LE(ack.sequence_number, current_sequence_number_);
+  // Only consider acks for the current frame.
+  if (ack.sequence_number != current_sequence_number_)
+    return;
+
+  finished_observers_.insert(obs);
+  observers_had_updates_ |= ack.has_updates;
+
+  // We max() with the current value in |oldest_incorporated_frames_| to handle
+  // situations where an observer just started observing (again) and may
+  // acknowledge with an ancient oldest_incorporated_frame.
+  oldest_incorporated_frames_[obs] =
+      std::max(ack.oldest_incorporated_frame, oldest_incorporated_frames_[obs]);
+}
+
+void BeginFrameObserverAckTracker::OnObserverAdded(BeginFrameObserver* obs) {
+  observers_.insert(obs);
+
+  // Since the observer didn't want BeginFrames before, we consider it "fresh"
+  // up to the last BeginFrame.
+  oldest_incorporated_frames_[obs] = current_sequence_number_ - 1;
+}
+
+void BeginFrameObserverAckTracker::OnObserverRemoved(BeginFrameObserver* obs) {
+  observers_.erase(obs);
+  finished_observers_.erase(obs);
+  oldest_incorporated_frames_.erase(obs);
+}
+
+bool BeginFrameObserverAckTracker::AllObserversFinishedFrame() const {
+  return base::STLIncludes(finished_observers_, observers_);
+}
+
+bool BeginFrameObserverAckTracker::AnyObserversHadUpdates() const {
+  return observers_had_updates_;
+}
+
+uint64_t BeginFrameObserverAckTracker::OldestIncorporatedFrame() const {
+  uint64_t oldest_incorporated_frame = current_sequence_number_;
+  for (const auto& entry : oldest_incorporated_frames_) {
+    oldest_incorporated_frame =
+        std::min(oldest_incorporated_frame, entry.second);
+  }
+  return oldest_incorporated_frame;
+}
+
+// ExternalBeginFrameSource -----------------------------------------------
 ExternalBeginFrameSource::ExternalBeginFrameSource(
     ExternalBeginFrameSourceClient* client)
     : client_(client) {
   DCHECK(client_);
 }
 
 ExternalBeginFrameSource::~ExternalBeginFrameSource() = default;
 
 void ExternalBeginFrameSource::AddObserver(BeginFrameObserver* obs) {
   DCHECK(obs);
   DCHECK(observers_.find(obs) == observers_.end());
 
   bool observers_was_empty = observers_.empty();
   observers_.insert(obs);
+  ack_tracker_.OnObserverAdded(obs);
   obs->OnBeginFrameSourcePausedChanged(paused_);
   if (observers_was_empty)
     client_->OnNeedsBeginFrames(true);
 
   // Send a MISSED begin frame if necessary.
   if (missed_begin_frame_args_.IsValid()) {
     BeginFrameArgs last_args = obs->LastUsedBeginFrameArgs();
     if (!last_args.IsValid() ||
-        (missed_begin_frame_args_.frame_time > last_args.frame_time)) {
+        (missed_begin_frame_args_.source_id != last_args.source_id) ||
+        (missed_begin_frame_args_.sequence_number >
+         last_args.sequence_number)) {
       obs->OnBeginFrame(missed_begin_frame_args_);
+      ack_tracker_.OnObserverBeginFrame(obs, missed_begin_frame_args_);
     }
   }
 }
 
 void ExternalBeginFrameSource::RemoveObserver(BeginFrameObserver* obs) {
   DCHECK(obs);
   DCHECK(observers_.find(obs) != observers_.end());
 
   observers_.erase(obs);
+  ack_tracker_.OnObserverRemoved(obs);
+  MaybeFinishFrame();
   if (observers_.empty()) {
     missed_begin_frame_args_ = BeginFrameArgs();
     client_->OnNeedsBeginFrames(false);
   }
 }
 
+void ExternalBeginFrameSource::DidFinishFrame(BeginFrameObserver* obs,
+                                              const BeginFrameAck& ack) {
+  ack_tracker_.OnObserverFinishedFrame(obs, ack);
+  MaybeFinishFrame();
+}
+
 bool ExternalBeginFrameSource::IsThrottled() const {
   return true;
 }
 
 void ExternalBeginFrameSource::OnSetBeginFrameSourcePaused(bool paused) {
   if (paused_ == paused)
     return;
   paused_ = paused;
   std::unordered_set<BeginFrameObserver*> observers(observers_);
   for (auto* obs : observers)
     obs->OnBeginFrameSourcePausedChanged(paused_);
 }
 
 void ExternalBeginFrameSource::OnBeginFrame(const BeginFrameArgs& args) {
+  if (frame_active_)
+    FinishFrame();
+
+  frame_active_ = true;
   missed_begin_frame_args_ = args;
   missed_begin_frame_args_.type = BeginFrameArgs::MISSED;
+  ack_tracker_.OnBeginFrame(args);
   std::unordered_set<BeginFrameObserver*> observers(observers_);
-  for (auto* obs : observers)
+  for (auto* obs : observers) {
     obs->OnBeginFrame(args);
+    ack_tracker_.OnObserverBeginFrame(obs, args);
+  }
+  MaybeFinishFrame();
+}
+
+void ExternalBeginFrameSource::MaybeFinishFrame() {
+  if (!frame_active_ || !ack_tracker_.AllObserversFinishedFrame())
+    return;
+  FinishFrame();
+}
+
+void ExternalBeginFrameSource::FinishFrame() {
+  frame_active_ = false;
+
+  BeginFrameAck ack(missed_begin_frame_args_.source_id,
+                    missed_begin_frame_args_.sequence_number,
+                    ack_tracker_.OldestIncorporatedFrame(), 0,
+                    ack_tracker_.AnyObserversHadUpdates());
+  client_->OnDidFinishFrame(ack);
+}
+
+// DelegatingBeginFrameSource ---------------------------------------------
+DelegatingBeginFrameSource::DelegatingBeginFrameSource(
+    BeginFrameSource* delegate)
+    : delegate_(delegate) {
+  DCHECK(delegate_);
+}
+
+void DelegatingBeginFrameSource::DidFinishFrame(BeginFrameObserver* obs,
+                                                const BeginFrameAck& ack) {
+  delegate_->DidFinishFrame(obs, ack);
+}
+
+void DelegatingBeginFrameSource::AddObserver(BeginFrameObserver* obs) {
+  delegate_->AddObserver(obs);
+}
+
+void DelegatingBeginFrameSource::RemoveObserver(BeginFrameObserver* obs) {
+  delegate_->RemoveObserver(obs);
+}
+
+bool DelegatingBeginFrameSource::IsThrottled() const {
+  return delegate_->IsThrottled();
+}
+
+uint64_t DelegatingBeginFrameSource::source_id() const {
+  return delegate_->source_id();
 }
 
 }  // namespace cc