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

webrtc/modules/video_coding/frame_buffer2.cc

 /*
  *  Copyright (c) 2016 The WebRTC project authors. All Rights Reserved.
  *
  *  Use of this source code is governed by a BSD-style license
  *  that can be found in the LICENSE file in the root of the source
  *  tree. An additional intellectual property rights grant can be found
  *  in the file PATENTS.  All contributing project authors may
  *  be found in the AUTHORS file in the root of the source tree.
  */
 
 #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"
 
 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;
+constexpr int kMaxHistoryFrameAge = 4096;
 
 // The maximum number of decoded frames being tracked by the frame buffer.
 constexpr int kMaxNumHistoryFrames = 256;
 }  // 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),
       jitter_estimator_(jitter_estimator),
       timing_(timing),
       inter_frame_delay_(clock_->TimeInMilliseconds()),
       newest_picture_id_(-1),
+      last_continuous_picture_id_(-1),
+      last_decoded_picture_id_(-1),
       stopped_(false),
       protection_mode_(kProtectionNack) {}
 
 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 wait_ms = max_wait_time_ms;
+  decltype(frames_.end()) next_frame_it;

[danilchap, 2016/09/12 12:20:14]

may be add
using Frames = std::map<FrameKey, FrameObject>;
into .h file right after all struct definitions,
then you can write here more explicit:
Frames::iterator next_frame_it;

(I think decltype more when you are not sure what type is, i.e. template
metaprogramming. 
Here you know exact type, it is just too long. Creating alias with using feels
more appropriate in this case)

[philipel, 2016/09/16 14:01:20]

Done.

+
   while (true) {
-    std::map<FrameKey, std::unique_ptr<FrameObject>, FrameComp>::iterator
-        next_frame_it;
     {
       rtc::CritScope lock(&crit_);
       frame_inserted_event_.Reset();
       if (stopped_)
         return kStopped;
 
       now = clock_->TimeInMilliseconds();
       wait_ms = max_wait_time_ms;
       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;
+      for (auto it = frames_.begin(); it != frames_.end(); ++it) {
+        const FrameKey& frame_key = it->first;
+        const FrameInfo& frame_info = frame_history_.find(frame_key)->second;

[danilchap, 2016/09/12 12:20:14]

frame_history_ can through out frames when there are too many of them.
Can that lead to situation where you have key in frames_ but not in
frame_history_?
i.e. may be add a DCHECK or check frame_key is in the history.

[philipel, 2016/09/16 14:01:20]

Done, rewrote FrameBuffer to only have one map for frames.

+        FrameObject* frame = it->second.get();
+
+        if (frame_info.num_missing_decodable == 0) {
+          next_frame_it = it;
           int64_t render_time =
-              next_frame_it->second->RenderTime() == -1
-                  ? timing_->RenderTimeMs(frame.timestamp, now)
-                  : next_frame_it->second->RenderTime();
+              frame->RenderTime() == -1
+                  ? timing_->RenderTimeMs(frame->timestamp, now)
+                  : frame->RenderTime();
           wait_ms = timing_->MaxWaitingTime(render_time, now);
-          frame_it->second->SetRenderTime(render_time);
+          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)
             continue;
 
           break;
         }
       }
@@ skipping 13 matching lines @@
         if (inter_frame_delay_.CalculateDelay(timestamp, &frame_delay,
                                               received_timestamp)) {
           jitter_estimator_->UpdateEstimate(frame_delay,
                                             next_frame_it->second->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(),
                                     clock_->TimeInMilliseconds());
 
-        decoded_frames_.insert(next_frame_it->first);
+        PropagateDecodability(next_frame_it->first);
         std::unique_ptr<FrameObject> frame = std::move(next_frame_it->second);
+        last_decoded_picture_id_ = frame->picture_id;
         frames_.erase(frames_.begin(), ++next_frame_it);
         *frame_out = std::move(frame);
         return kFrameFound;
       } else {
         return kTimeout;
       }
     }
   }
 }
 
 void FrameBuffer::SetProtectionMode(VCMVideoProtection mode) {
   rtc::CritScope lock(&crit_);
   protection_mode_ = mode;
 }
 
 void FrameBuffer::Start() {
   rtc::CritScope lock(&crit_);
   stopped_ = false;
 }
 
 void FrameBuffer::Stop() {
   rtc::CritScope lock(&crit_);
   stopped_ = true;
   frame_inserted_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)
+  if (frame->inter_layer_predicted && frame->spatial_layer == 0) {
+    LOG(LS_INFO) << "Spatial layer 0 frame with picture id "
+                 << frame->picture_id
+                 << " is marked as inter layer predicted, dropping frame.";
+    return last_continuous_picture_id_;
+  }
+
+  if (last_decoded_picture_id_ != -1 &&
+      AheadOf<uint16_t>(last_decoded_picture_id_, frame->picture_id)) {
+    LOG(LS_INFO) << "Frame with picture id " << frame->picture_id
+                 << " inserted after frame with picture id "
+                 << last_decoded_picture_id_
+                 << " was handed off for decoding, dropping frame.";
+    return last_continuous_picture_id_;
+  }
+
+  if (newest_picture_id_ == -1 ||
+      AheadOf<uint16_t>(frame->picture_id, newest_picture_id_)) {
     newest_picture_id_ = frame->picture_id;
+  }
 
-  if (AheadOf<uint16_t>(frame->picture_id, newest_picture_id_))
-    newest_picture_id_ = frame->picture_id;
-
-  // Remove frames as long as we have too many, |kMaxNumHistoryFrames|.
-  while (decoded_frames_.size() > kMaxNumHistoryFrames)
-    decoded_frames_.erase(decoded_frames_.begin());
-
-  // 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);
+  // Remove frames while we have too many or if they are too old.
+  while (frame_history_.size() > kMaxNumHistoryFrames ||

[danilchap, 2016/09/12 12:20:14]

probably cleaner to have two loops like before.
The erase code is small enough not to worry about code duplication.

[philipel, 2016/09/16 14:01:20]

Clear logic moved to new function ClearOldInfo.

+         (!frame_history_.empty() &&
+          AheadOf<uint16_t>(newest_picture_id_ - kMaxHistoryFrameAge,
+                            frame_history_.begin()->first.picture_id))) {
+    frame_history_.erase(frame_history_.begin());
+  }
 
   FrameKey key(frame->picture_id, frame->spatial_layer);
+  auto info = frame_history_.insert(std::make_pair(key, FrameInfo())).first;

[danilchap, 2016/09/12 12:20:14]

since your ignore .second anyway, may be cleaner 
FrameInfo* info = &frame_history_[key];

[philipel, 2016/09/16 14:01:20]

I can't rely on the pointers being stable since I insert items into the map as I
iterate over it.

+  info->second.num_missing_continuous = frame->num_references;
+  info->second.num_missing_decodable = frame->num_references;
+
+  // 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);
+    auto ref_info =
+        frame_history_.insert(std::make_pair(ref_key, FrameInfo())).first;
+    if (ref_info->second.continuous) {
+      --info->second.num_missing_continuous;
+      if (ref_info->second.decoded) {

[danilchap, 2016/09/12 12:20:14]

do you distinguish decoded (returned by NextFrame) and decodable (has enough
packet to decode a frame, enough packet for NextFrame to return it)?
what does continuous mean? decodable?

[philipel, 2016/09/16 14:01:20]

Since a FrameInfo can be inserted without the corresponding frame actually being
inserted into the FrameBuffer we have to separate the case where
num_missing_continuous is zero because we don't have the frame and the case
where num_missing_continuous is zero due to all dependencies being fulfilled.

With the new changes FrameInfo::decoded wont be needed any more.

+        --info->second.num_missing_decodable;
+        continue;
+      }
+    }
+
+    // If either the frame isn't continuous or not decodable or both then we
+    // add the backwards reference so this 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;
+  }
+
   frames_[key] = std::move(frame);
-  frame_inserted_event_.Set();
+
+  if (info->second.num_missing_continuous == 0) {
+    info->second.continuous = true;
+    PropagateContinuity(key);
+
+    // Since we now have new continuous frames there might be a better frame
+    // to return from NextFrame. Signal that thread so that it can again choose
+    // which frame to return.
+    frame_inserted_event_.Set();
+  }
+
+  return last_continuous_picture_id_;
 }
 
-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::PropagateContinuity(const FrameKey& key) {
+  std::queue<decltype(frame_history_.end())> continuous_frames_;
+
+  auto start_frame = frame_history_.find(key);
+  RTC_DCHECK(start_frame->second.continuous);
+  continuous_frames_.push(start_frame);
+
+  while (!continuous_frames_.empty()) {
+    auto frame = continuous_frames_.front();
+    continuous_frames_.pop();
+
+    if (last_continuous_picture_id_ == -1 ||
+        AheadOf<uint16_t>(frame->first.picture_id,
+                          last_continuous_picture_id_)) {
+      last_continuous_picture_id_ = frame->first.picture_id;
+    }
+
+    // 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 = frame_history_.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);
+      }
+    }
   }
+}
 
-  // Have we decoded all frames that this frame depend on?
-  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;
+void FrameBuffer::PropagateDecodability(const FrameKey& key) {
+  auto info = frame_history_.find(key);
+  info->second.decoded = true;
+
+  for (size_t d = 0; d < info->second.num_dependent_frames; ++d) {
+    auto ref_info = frame_history_.find(info->second.dependent_frames[d]);

[danilchap, 2016/09/12 12:20:14]

You sure info->second.dependent_frames[d] is in the history?

+    --ref_info->second.num_missing_decodable;
   }
-
-  // If this is a layer frame, have we decoded the lower layer of this
-  // super 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;
-  }
-
-  return true;
 }
 
 }  // namespace video_coding
 }  // namespace webrtc