Frame continuity is now tested as soon as a frame is inserted into the FrameBuffer.

webrtc/modules/video_coding/frame_buffer2.cc

Index: webrtc/modules/video_coding/frame_buffer2.cc
diff --git a/webrtc/modules/video_coding/frame_buffer2.cc b/webrtc/modules/video_coding/frame_buffer2.cc
index 766e6a05d722ddc2811f47763d9a1f49711093ec..4a6f23f4b7b7510885fecc4a8404a19a55a85815 100644
--- a/webrtc/modules/video_coding/frame_buffer2.cc
+++ b/webrtc/modules/video_coding/frame_buffer2.cc
@@ -11,11 +11,12 @@
 #include "webrtc/modules/video_coding/frame_buffer2.h"
 
 #include <algorithm>
+#include <cstring>
+#include <queue>
 
 #include "webrtc/base/checks.h"
-#include "webrtc/modules/video_coding/frame_object.h"
+#include "webrtc/base/logging.h"
 #include "webrtc/modules/video_coding/jitter_estimator.h"
-#include "webrtc/modules/video_coding/sequence_number_util.h"
 #include "webrtc/modules/video_coding/timing.h"
 #include "webrtc/system_wrappers/include/clock.h"
 
@@ -23,32 +24,26 @@ namespace webrtc {
 namespace video_coding {
 
 namespace {
-// The maximum age of decoded frames tracked by frame buffer, compared to
-// |newest_picture_id_|.
-constexpr int kMaxFrameAge = 4096;
+// Max number of frames the buffer will hold.
+constexpr int kMaxFramesBuffered = 1000;
 
-// The maximum number of decoded frames being tracked by the frame buffer.
-constexpr int kMaxNumHistoryFrames = 256;
+// Max number of decoded frame info that will be saved.
+constexpr int kMaxFramesHistory = 20;
 }  // namespace
 
-bool FrameBuffer::FrameComp::operator()(const FrameKey& f1,
-                                        const FrameKey& f2) const {
-  // first = picture id
-  // second = spatial layer
-  if (f1.first == f2.first)
-    return f1.second < f2.second;
-  return AheadOf(f2.first, f1.first);
-}
-
 FrameBuffer::FrameBuffer(Clock* clock,
                          VCMJitterEstimator* jitter_estimator,
                          VCMTiming* timing)
-    : clock_(clock),
-      frame_inserted_event_(false, false),
+    : frames_(),

[danilchap, 2016/09/19 12:21:50]

may be do not mention member if you create it with default constructor.

[philipel, 2016/09/19 15:36:57]

Done.

+      clock_(clock),
+      new_countinuous_frame_event_(false, false),
       jitter_estimator_(jitter_estimator),
       timing_(timing),
       inter_frame_delay_(clock_->TimeInMilliseconds()),
-      newest_picture_id_(-1),
+      last_decoded_frame_it_(frames_.end()),
+      last_continuous_frame_it_(frames_.end()),
+      num_frames_history_(0),
+      num_frames_buffered_(0),
       stopped_(false),
       protection_mode_(kProtectionNack) {}
 
@@ -56,67 +51,92 @@ FrameBuffer::ReturnReason FrameBuffer::NextFrame(
     int64_t max_wait_time_ms,
     std::unique_ptr<FrameObject>* frame_out) {
   int64_t latest_return_time = clock_->TimeInMilliseconds() + max_wait_time_ms;
-  int64_t now = clock_->TimeInMilliseconds();
+  int64_t now_ms = clock_->TimeInMilliseconds();
   int64_t wait_ms = max_wait_time_ms;
+  FrameMap::iterator next_frame_it;
+
   while (true) {
-    std::map<FrameKey, std::unique_ptr<FrameObject>, FrameComp>::iterator
-        next_frame_it;
     {
       rtc::CritScope lock(&crit_);
-      frame_inserted_event_.Reset();
+      new_countinuous_frame_event_.Reset();
       if (stopped_)
         return kStopped;
 
-      now = clock_->TimeInMilliseconds();
+      now_ms = clock_->TimeInMilliseconds();
       wait_ms = max_wait_time_ms;
+
+      // Need to hold |crit_| in order to use |frames_|, therefore we
+      // set it here in the loop instead of outside the loop in order to not
+      // acquire the look unnecesserily.

[danilchap, 2016/09/19 12:21:50]

s/look/lock/

[philipel, 2016/09/19 15:36:57]

Done.

       next_frame_it = frames_.end();
-      for (auto frame_it = frames_.begin(); frame_it != frames_.end();
-           ++frame_it) {
-        const FrameObject& frame = *frame_it->second;
-        if (IsContinuous(frame)) {
-          next_frame_it = frame_it;
-          int64_t render_time =
-              next_frame_it->second->RenderTime() == -1
-                  ? timing_->RenderTimeMs(frame.timestamp, now)
-                  : next_frame_it->second->RenderTime();
-          wait_ms = timing_->MaxWaitingTime(render_time, now);
-          frame_it->second->SetRenderTime(render_time);
-
-          // This will cause the frame buffer to prefer high framerate rather
-          // than high resolution in the case of the decoder not decoding fast
-          // enough and the stream has multiple spatial and temporal layers.
-          if (wait_ms == 0)
-            continue;
-
-          break;
+
+      // |frame_it| points to the first frame after the
+      // |last_decoded_frame_it_|.
+      auto frame_it = frames_.end();
+      if (last_decoded_frame_it_ == frames_.end()) {

[danilchap, 2016/09/19 12:21:50]

you use this construction twice, may be add a small helper methods:
iterator FirstUndecoded() const LOCK_REQUIRED;

[philipel, 2016/09/19 15:36:57]

I guess you are thinking of line 263? It's similar but not the same.

+        frame_it = frames_.begin();
+      } else {
+        frame_it = last_decoded_frame_it_;
+        ++frame_it;
+      }
+
+      // |continuous_end_it| point to the first frame after the
+      // |last_continuous_frame_it_|.
+      auto continuous_end_it = last_continuous_frame_it_;
+      if (continuous_end_it != frames_.end())
+        ++continuous_end_it;
+
+      while (frame_it != continuous_end_it) {

[danilchap, 2016/09/19 12:21:50]

since you ++frame_it before both continue, may be turn while into for loop:
for (;frame_it != continuous_end_it; ++frame_it) {
}

[philipel, 2016/09/19 15:36:57]

Done.

+        if (frame_it->second.num_missing_decodable > 0) {
+          ++frame_it;
+          continue;
         }
+
+        FrameObject* frame = frame_it->second.frame.get();
+        next_frame_it = frame_it;
+        int64_t render_time =
+            frame->RenderTime() == -1
+                ? timing_->RenderTimeMs(frame->timestamp, now_ms)
+                : frame->RenderTime();
+        wait_ms = timing_->MaxWaitingTime(render_time, now_ms);
+        frame->SetRenderTime(render_time);
+
+        // This will cause the frame buffer to prefer high framerate rather
+        // than high resolution in the case of the decoder not decoding fast
+        // enough and the stream has multiple spatial and temporal layers.
+        if (wait_ms == 0) {
+          ++frame_it;
+          continue;
+        }
+
+        break;
       }
-    }
+    }  // rtc::Critscope lock(&crit_);
 
-    wait_ms = std::min<int64_t>(wait_ms, latest_return_time - now);
+    wait_ms = std::min<int64_t>(wait_ms, latest_return_time - now_ms);
     wait_ms = std::max<int64_t>(wait_ms, 0);
     // If the timeout occurs, return. Otherwise a new frame has been inserted
     // and the best frame to decode next will be selected again.
-    if (!frame_inserted_event_.Wait(wait_ms)) {
+    if (!new_countinuous_frame_event_.Wait(wait_ms)) {

[danilchap, 2016/09/19 12:21:50]

though unrelated to this cl, may be cleaner to turn while(true) loop into
do {
} while (new_continous_frame_event.Wait(wait_ms));

...Same post wait code that return kTimeout or kFrameFound

[philipel, 2016/09/19 15:36:57]

Much cleaner, thank you!

       rtc::CritScope lock(&crit_);
       if (next_frame_it != frames_.end()) {
-        int64_t received_timestamp = next_frame_it->second->ReceivedTime();
-        uint32_t timestamp = next_frame_it->second->Timestamp();
+        std::unique_ptr<FrameObject> frame =
+            std::move(next_frame_it->second.frame);
+        int64_t received_timestamp = frame->ReceivedTime();
+        uint32_t timestamp = frame->Timestamp();
 
         int64_t frame_delay;
         if (inter_frame_delay_.CalculateDelay(timestamp, &frame_delay,
                                               received_timestamp)) {
-          jitter_estimator_->UpdateEstimate(frame_delay,
-                                            next_frame_it->second->size);
+          jitter_estimator_->UpdateEstimate(frame_delay, frame->size);
         }
         float rtt_mult = protection_mode_ == kProtectionNackFEC ? 0.0 : 1.0;
         timing_->SetJitterDelay(jitter_estimator_->GetJitterEstimate(rtt_mult));
-        timing_->UpdateCurrentDelay(next_frame_it->second->RenderTime(),
+        timing_->UpdateCurrentDelay(frame->RenderTime(),
                                     clock_->TimeInMilliseconds());
 
-        decoded_frames_.insert(next_frame_it->first);
-        std::unique_ptr<FrameObject> frame = std::move(next_frame_it->second);
-        frames_.erase(frames_.begin(), ++next_frame_it);
+        PropagateDecodability(next_frame_it->second);
+        AdvanceLastDecodedFrame(next_frame_it);
         *frame_out = std::move(frame);
         return kFrameFound;
       } else {
@@ -139,58 +159,185 @@ void FrameBuffer::Start() {
 void FrameBuffer::Stop() {
   rtc::CritScope lock(&crit_);
   stopped_ = true;
-  frame_inserted_event_.Set();
+  new_countinuous_frame_event_.Set();
 }
 
-void FrameBuffer::InsertFrame(std::unique_ptr<FrameObject> frame) {
+int FrameBuffer::InsertFrame(std::unique_ptr<FrameObject> frame) {
   rtc::CritScope lock(&crit_);
-  // If |newest_picture_id_| is -1 then this is the first frame we received.
-  if (newest_picture_id_ == -1)
-    newest_picture_id_ = frame->picture_id;
+  FrameKey key(frame->picture_id, frame->spatial_layer);
+  int last_continuous_picture_id =
+      last_continuous_frame_it_ == frames_.end()
+          ? -1
+          : last_continuous_frame_it_->first.picture_id;
 
-  if (AheadOf<uint16_t>(frame->picture_id, newest_picture_id_))
-    newest_picture_id_ = frame->picture_id;
+  if (num_frames_buffered_ >= kMaxFramesBuffered) {
+    LOG(LS_INFO) << "Frame with (picture_id:spatial_id) (" << key.picture_id
+                 << ":" << int(key.spatial_layer)
+                 << ") could not be inserted due to the frame "
+                 << "buffer being full, dropping frame.";
+    return last_continuous_picture_id;
+  }
 
-  // Remove frames as long as we have too many, |kMaxNumHistoryFrames|.
-  while (decoded_frames_.size() > kMaxNumHistoryFrames)
-    decoded_frames_.erase(decoded_frames_.begin());
+  if (frame->inter_layer_predicted && frame->spatial_layer == 0) {
+    LOG(LS_INFO) << "Frame with (picture_id:spatial_id) (" << key.picture_id
+                 << ":" << int(key.spatial_layer)
+                 << ") is marked as inter layer predicted, dropping frame.";
+    return last_continuous_picture_id;
+  }
 
-  // Remove frames that are too old.
-  uint16_t old_picture_id = Subtract<1 << 16>(newest_picture_id_, kMaxFrameAge);
-  auto old_decoded_it =
-      decoded_frames_.lower_bound(FrameKey(old_picture_id, 0));
-  decoded_frames_.erase(decoded_frames_.begin(), old_decoded_it);
+  if (last_decoded_frame_it_ != frames_.end() &&
+      key < last_decoded_frame_it_->first) {
+    LOG(LS_INFO) << "Frame with (picture_id:spatial_id) (" << key.picture_id
+                 << ":" << int(key.spatial_layer) << ") inserted after frame ("
+                 << last_decoded_frame_it_->first.picture_id << ":"
+                 << int(last_decoded_frame_it_->first.spatial_layer)
+                 << ") was handed off for decoding, dropping frame.";
+    return last_continuous_picture_id;
+  }
 
-  FrameKey key(frame->picture_id, frame->spatial_layer);
-  frames_[key] = std::move(frame);
-  frame_inserted_event_.Set();
+  auto info = UpdateFrameInfo(*frame.get());

[danilchap, 2016/09/19 12:21:50]

no need to .get():
UpdateFrameInfo(*frame);
should work.

[philipel, 2016/09/19 15:36:57]

Done.

+
+  if (info == frames_.end()) {
+    LOG(LS_INFO) << "Frame with (picture_id:spatial_id) (" << key.picture_id

[danilchap, 2016/09/19 12:21:50]

may be move this log inside UpdateFrameInfo, closer to the code that explain why
info == frames_.end() means unresolvable dependency.

Here it uses hidden knowledge that there is no other reason for UpdateFrameInfo
to fail.

[philipel, 2016/09/19 15:36:57]

UpdateFrameInfoWithIncomingFrame now returns false if |frame| will never become
continuous.

+                 << ":" << int(key.spatial_layer)
+                 << " depends on a non-decoded frame more previous than "
+                 << "the last decoded frame, dropping frame.";
+    return last_continuous_picture_id;
+  }
+
+  info->second.frame = std::move(frame);
+  ++num_frames_buffered_;
+
+  if (info->second.num_missing_continuous == 0) {
+    info->second.continuous = true;
+    PropagateContinuity(info);
+    last_continuous_picture_id = last_continuous_frame_it_->first.picture_id;
+
+    // Since we now have new continuous frames there might be a better frame
+    // to return from NextFrame. Signal that thread so that it again can choose
+    // which frame to return.
+    new_countinuous_frame_event_.Set();
+  }
+
+  return last_continuous_picture_id;
+}
+
+void FrameBuffer::PropagateContinuity(const FrameMap::iterator& start) {
+  RTC_DCHECK(start->second.continuous);
+  if (last_continuous_frame_it_ == frames_.end())
+    last_continuous_frame_it_ = start;
+
+  std::queue<FrameMap::iterator> continuous_frames_;

[danilchap, 2016/09/19 12:21:50]

remove last '_' in the variable name.

[philipel, 2016/09/19 15:36:57]

Done.

+  continuous_frames_.push(start);
+
+  while (!continuous_frames_.empty()) {
+    auto frame = continuous_frames_.front();
+    continuous_frames_.pop();
+
+    if (last_continuous_frame_it_->first < frame->first)
+      last_continuous_frame_it_ = frame;
+
+    // Loop through all dependent frames, and if that frame no longer has
+    // any unfulfilled dependencies then that frame is continuous as well.
+    for (size_t d = 0; d < frame->second.num_dependent_frames; ++d) {
+      auto frame_ref = frames_.find(frame->second.dependent_frames[d]);
+      --frame_ref->second.num_missing_continuous;
+
+      if (frame_ref->second.num_missing_continuous == 0) {
+        frame_ref->second.continuous = true;
+        continuous_frames_.push(frame_ref);
+      }
+    }
+  }
 }
 
-bool FrameBuffer::IsContinuous(const FrameObject& frame) const {
-  // If a frame with an earlier picture id was inserted compared to the last
-  // decoded frames picture id then that frame arrived too late.
-  if (!decoded_frames_.empty() &&
-      AheadOf(decoded_frames_.rbegin()->first, frame.picture_id)) {
-    return false;
+void FrameBuffer::PropagateDecodability(const FrameInfo& info) {
+  for (size_t d = 0; d < info.num_dependent_frames; ++d) {
+    auto ref_info = frames_.find(info.dependent_frames[d]);
+    RTC_DCHECK_GT(ref_info->second.num_missing_decodable, 0U);
+    --ref_info->second.num_missing_decodable;
+  }
+}
+
+void FrameBuffer::AdvanceLastDecodedFrame(const FrameMap::iterator& decoded) {
+  if (last_decoded_frame_it_ == frames_.end()) {
+    last_decoded_frame_it_ = frames_.begin();
+  } else {
+    ++last_decoded_frame_it_;

[danilchap, 2016/09/19 12:21:50]

May be add DCHECK(last_decoded_frame_it_->first < decoded->first)
Without it one can wonder 'what would happen if last_decoded_frame_it_ points to
the last [not end] element in the map'.

[philipel, 2016/09/19 15:36:56]

Done.

+  }
+  --num_frames_buffered_;

[danilchap, 2016/09/19 12:21:50]

probably join this with another lonely
++num_frames_history;
move to top and add a comment that |decoded| changed it state from 'buffered' to
'history'

[philipel, 2016/09/19 15:36:57]

Done.

+
+  // First, delete non-decoded frames from the history.
+  while (last_decoded_frame_it_ != decoded) {

[danilchap, 2016/09/19 12:21:50]

may be do not use this variable to iterate over undecoded frames, but rather
introduce a new one, just for better name:
non_decoded or next_frame or frame.
loop while (frame != decoded) would look more natural then.

[philipel, 2016/09/19 15:36:56]

I don't think this is unexpected considering the function name
AdvanceLastDecodedFrame. Maybe AdvanceLastDecodedFrameIterator is clearer?

+    last_decoded_frame_it_ = frames_.erase(last_decoded_frame_it_);
+    --num_frames_buffered_;
   }
 
-  // Have we decoded all frames that this frame depend on?
+  // Then remove old history if we have too much history saved.
+  ++num_frames_history_;
+  if (num_frames_history_ > kMaxFramesHistory) {
+    frames_.erase(frames_.begin());
+    --num_frames_history_;
+  }
+}
+
+FrameBuffer::FrameMap::iterator FrameBuffer::UpdateFrameInfo(
+    const FrameObject& frame) {
+  FrameKey key(frame.picture_id, frame.spatial_layer);
+  auto info = frames_.insert(std::make_pair(key, FrameInfo())).first;
+  info->second.num_missing_continuous = frame.num_references;
+  info->second.num_missing_decodable = frame.num_references;
+
+  RTC_DCHECK(last_decoded_frame_it_ == frames_.end() ||
+             last_decoded_frame_it_->first < info->first);
+
+  // Check how many dependencies that has already been fulfilled.
   for (size_t r = 0; r < frame.num_references; ++r) {
     FrameKey ref_key(frame.references[r], frame.spatial_layer);
-    if (decoded_frames_.find(ref_key) == decoded_frames_.end())
-      return false;
+    auto ref_info = frames_.find(ref_key);
+
+    // Does |frame| depend on a frame earlier than the last decoded frame?
+    if (last_decoded_frame_it_ != frames_.end() &&
+        (ref_key < last_decoded_frame_it_->first ||

[danilchap, 2016/09/19 12:21:50]

may be
!(last_decoded_frame_it_->first < ref_key)
or prefer to have extra operator for clarity here?:
(ref_key <= last_decoded_frame_it_->first)

[philipel, 2016/09/19 15:36:57]

Done.

+         ref_key == last_decoded_frame_it_->first)) {
+      // Do we depend on a frame that was never decoded?

[danilchap, 2016/09/19 12:21:50]

s/Do we/Does |frame|/

[philipel, 2016/09/19 15:36:57]

Done.

+      if (ref_info == frames_.end())
+        return frames_.end();
+
+      --info->second.num_missing_continuous;
+      --info->second.num_missing_decodable;
+
+    } else {
+      if (ref_info == frames_.end())
+        ref_info = frames_.insert(std::make_pair(ref_key, FrameInfo())).first;
+
+      if (ref_info->second.continuous)
+        --info->second.num_missing_continuous;
+
+      // Add backwards reference so |frame| can be updated when new
+      // frames are inserted or decoded.
+      ref_info->second.dependent_frames[ref_info->second.num_dependent_frames] =
+          key;
+      ++ref_info->second.num_dependent_frames;
+    }
   }
 
-  // If this is a layer frame, have we decoded the lower layer of this
-  // super frame.
+  // Check if we have the lower spatial layer frame.
   if (frame.inter_layer_predicted) {
-    RTC_DCHECK_GT(frame.spatial_layer, 0);
-    FrameKey ref_key(frame.picture_id, frame.spatial_layer - 1);
-    if (decoded_frames_.find(ref_key) == decoded_frames_.end())
-      return false;
+    ++info->second.num_missing_continuous;
+    ++info->second.num_missing_decodable;
+
+    FrameKey ref_key = FrameKey(frame.picture_id, frame.spatial_layer - 1);

[danilchap, 2016/09/19 12:21:50]

FrameKey ref_key(frame.picture_id, frame.spatial_layer - 1);

[philipel, 2016/09/19 15:36:57]

Done.

+    auto ref_info = frames_.insert(std::make_pair(ref_key, FrameInfo())).first;

[danilchap, 2016/09/19 12:21:50]

this ref_info is not used outside as iterator, may be
FrameInfo* ref_info = &frames_[ref_key];
if (ref_info->continnuous)...
ref_info->dependent_frames[ref_info->num_dependent_frames] = key;
++ref_info->num_denepdent_frames;

[philipel, 2016/09/19 15:36:57]

Using an iterator is more in style with the rest of the function I think.

+    if (ref_info->second.continuous)
+      --info->second.num_missing_continuous;
+
+    ref_info->second.dependent_frames[ref_info->second.num_dependent_frames] =
+        key;
+    ++ref_info->second.num_dependent_frames;
   }
 
-  return true;
+  return info;
 }
 
 }  // namespace video_coding