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() {

[Sami, 2016/12/06 12:41:06]

Fancy :)

[Eric Seckler, 2016/12/06 17:34:00]

I'd call this rather ugly ;)

[Sami, 2016/12/07 16:59:40]

Let's settle on "elaborate".

+  // 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_(0),
+      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)
     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_(0) {
   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_++;

[Sami, 2016/12/06 12:41:06]

Not sure why we don't just always increment this? IIRC that was needed to
distinguish otherwise duplicate frames?

[Eric Seckler, 2016/12/06 17:33:59]

Not only. We also use the number to distinguish which frame an observer
acknowledges in DisplayBFS - to detect when all observers have responded and
then trigger an early deadline in DisplayScheduler.

We may end up here in two slightly different situations:
a) An observer adds themselves for the first time after no-one was listening for
a while. In this case, the missed frame it receives will be a "new" one that
wasn't sent to anyone else yet. In that case, we need a new sequence number.
b) An observer adds themselves while other observers were already listening. In
that case, we should send the same BeginFrame to the new observer (with same
sequence number) that the other observers already received. If we incremented in
that case, the other observers would answer with the old frame's number, even
though they are responding to the latest frame.

[Sami, 2016/12/07 16:59:40]

Thanks for the explanation, that makes sense. However I'm not sure if comparing
against current_begin_frame_time_ is equivalent to what you wrote. Could we
instead more explicitly check what the state it at the time the observer was
added? In any case I think this deserves a comment :)

[Eric Seckler, 2016/12/08 17:54:28]

Updated the code & comment. I think it's a bit clearer now...

We only discover the state ("is the last frame we sent still active?") during
AddObserver(), so the only way to figure out if we should send that same frame
or a different one is to compare frame times there. I'm now also checking that
the interval hasn't changed between frames to ensure that we don't send
BeginFrames with different intervals and the same 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_(0),
+      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_ > 0 ? current_sequence_number_ - 1 : 0;
+  }
+}
+
+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] =

[Sami, 2016/12/06 12:41:06]

Does it make sense to look at this if !has_updates?

[Eric Seckler, 2016/12/06 17:33:59]

Yup, see comment in begin_frame_args.h.

+      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_ > 0 ? current_sequence_number_ - 1 : 0;

[Sami, 2016/12/06 12:41:06]

nit: Alternatively we could start sequence numbering from 1 to avoid the edge
case.

[Eric Seckler, 2016/12/06 17:33:59]

Done.

+}
+
+void BeginFrameObserverAckTracker::OnObserverRemoved(BeginFrameObserver* obs) {
+  observers_.erase(obs);
+  finished_observers_.erase(obs);
+  oldest_incorporated_frames_.erase(obs);
+}
+
+bool BeginFrameObserverAckTracker::ObserversFinishedFrame() {
+  return base::STLIncludes(finished_observers_, observers_);
+}
+
+bool BeginFrameObserverAckTracker::ObserversHadUpdates() {
+  return observers_had_updates_;
+}
+
+uint64_t BeginFrameObserverAckTracker::OldestIncorporatedFrame() {
+  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_.ObserversFinishedFrame())
+    return;
+  FinishFrame();
+}
+
+void ExternalBeginFrameSource::FinishFrame() {
+  frame_active_ = false;
+
+  BeginFrameAck ack(missed_begin_frame_args_.source_id,
+                    missed_begin_frame_args_.sequence_number,
+                    ack_tracker_.ObserversHadUpdates(),
+                    ack_tracker_.OldestIncorporatedFrame(), 0);
+  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