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;
+// Max number of frames the buffer will hold.
+constexpr int kMaxFramesBuffered = 1000;

[stefan-webrtc, 2016/09/21 14:50:14]

Old jitter buffer had this limited to 300.

[philipel, 2016/09/22 11:18:38]

I think that is a bit low, at 60 fps that is 5 seconds, changed it to 600.

 
-// 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),
+      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) {}
 
 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;
-  while (true) {
-    std::map<FrameKey, std::unique_ptr<FrameObject>, FrameComp>::iterator
-        next_frame_it;
+  FrameMap::iterator next_frame_it;
+
+  do {
+    int64_t now_ms = clock_->TimeInMilliseconds();
     {
       rtc::CritScope lock(&crit_);
-      frame_inserted_event_.Reset();
+      new_countinuous_frame_event_.Reset();
       if (stopped_)
         return kStopped;
 
-      now = 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 lock unnecesserily.
       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;
+      // |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()) {
+        frame_it = frames_.begin();
+      } else {
+        frame_it = last_decoded_frame_it_;
+        ++frame_it;
+      }
 
-          break;
-        }
+      // |continuous_end_it| point to the first frame after the

[stefan-webrtc, 2016/09/21 14:50:13]

points

[philipel, 2016/09/22 11:18:38]

Done.

+      // |last_continuous_frame_it_|.
+      auto continuous_end_it = last_continuous_frame_it_;
+      if (continuous_end_it != frames_.end())
+        ++continuous_end_it;
+
+      for (; frame_it != continuous_end_it; ++frame_it) {
+        if (frame_it->second.num_missing_decodable > 0)
+          continue;
+
+        FrameObject* frame = frame_it->second.frame.get();
+        next_frame_it = frame_it;
+        int64_t render_time =

[danilchap, 2016/09/20 13:45:25]

may be shorten this block a bit:
if (frame->RenderTime() == -1)
  frame->SetRenderTime(timeing_->RenderTimeMs(frame->timestamp, now_ms);
wait_ms = timing_->MaxWaitingTime(frame->RenderTime(), now_ms);

[philipel, 2016/09/22 11:18:38]

Done.

+            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)
+          continue;
+
+        break;
       }
+    }  // rtc::Critscope lock(&crit_);
+
+    wait_ms = std::min<int64_t>(wait_ms, latest_return_time - now_ms);
+    wait_ms = std::max<int64_t>(wait_ms, 0);
+  } while (new_countinuous_frame_event_.Wait(wait_ms));
+
+  rtc::CritScope lock(&crit_);
+  if (next_frame_it != frames_.end()) {
+    std::unique_ptr<FrameObject> frame = std::move(next_frame_it->second.frame);
+    int64_t received_timestamp = frame->ReceivedTime();

[stefan-webrtc, 2016/09/21 14:50:14]

received_time instead of received_timestamp? The word "timestamp" is fairly
tightly coupled to the actual frame timestamp, which might be confusing.

[philipel, 2016/09/22 11:18:38]

Done.

+    uint32_t timestamp = frame->Timestamp();
+
+    int64_t frame_delay;
+    if (inter_frame_delay_.CalculateDelay(timestamp, &frame_delay,
+                                          received_timestamp)) {
+      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(frame->RenderTime(),
+                                clock_->TimeInMilliseconds());
 
-    wait_ms = std::min<int64_t>(wait_ms, latest_return_time - now);
-    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)) {
-      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();
-
-        int64_t frame_delay;
-        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);
-        std::unique_ptr<FrameObject> frame = std::move(next_frame_it->second);
-        frames_.erase(frames_.begin(), ++next_frame_it);
-        *frame_out = std::move(frame);
-        return kFrameFound;
-      } else {
-        return kTimeout;
-      }
-    }
+    PropagateDecodability(next_frame_it->second);
+    AdvanceLastDecodedFrame(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();
+  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

[stefan-webrtc, 2016/09/21 14:50:13]

Should these logs be warnings?

[philipel, 2016/09/22 11:18:38]

I think warnings are better since we don't expect this to be a part of normal
usage of the FrameBuffer, changed.

+                 << ":" << int(key.spatial_layer)

[stefan-webrtc, 2016/09/21 14:50:14]

static_cast<int>() here and below.

[philipel, 2016/09/22 11:18:38]

Done.

+                 << ") 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 = frames_.insert(std::make_pair(key, FrameInfo())).first;
+
+  if (!UpdateFrameInfoWithIncomingFrame(*frame, info)) {
+    frames_.erase(info);
+    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);

[stefan-webrtc, 2016/09/21 14:50:13]

I think it would be easier to read the code if you did

last_continuous_frame_it_ = PropagateContinuity(info);

That way you may even be able to make PropagateContinuity() static if you pass
in frames_

[philipel, 2016/09/22 11:18:38]

If a new frame became continuous then |last_continuous_frame_it_| might be
updated, so if we return an iterator we wont know if the new frames became
continuous or not.

+    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;
 }
 
-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(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;
+  continuous_frames.push(start);
+
+  // A simple BFS to traverse continuous frames.
+  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);
+      }
+    }
+  }
+}
+
+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(FrameMap::iterator decoded) {
+  if (last_decoded_frame_it_ == frames_.end()) {
+    last_decoded_frame_it_ = frames_.begin();
+  } else {
+    RTC_DCHECK(last_decoded_frame_it_->first < decoded->first);
+    ++last_decoded_frame_it_;
+  }
+  --num_frames_buffered_;
+  ++num_frames_history_;
+
+  // First, delete non-decoded frames from the history.
+  while (last_decoded_frame_it_ != decoded) {
+    if (last_decoded_frame_it_->second.frame)
+      --num_frames_buffered_;
+    last_decoded_frame_it_ = frames_.erase(last_decoded_frame_it_);
   }
 
-  // Have we decoded all frames that this frame depend on?
+  // Then remove old history if we have too much history saved.
+  if (num_frames_history_ > kMaxFramesHistory) {
+    frames_.erase(frames_.begin());
+    --num_frames_history_;
+  }
+}
+
+bool FrameBuffer::UpdateFrameInfoWithIncomingFrame(const FrameObject& frame,
+                                                   FrameMap::iterator info) {
+  FrameKey key(frame.picture_id, frame.spatial_layer);
+  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.

[stefan-webrtc, 2016/09/21 14:50:14]

have already

[philipel, 2016/09/22 11:18:38]

Done.

   for (size_t r = 0; r < frame.num_references; ++r) {

[stefan-webrtc, 2016/09/21 14:50:13]

use i instead of r.

[philipel, 2016/09/22 11:18:38]

Done.

     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) {
+      // Does |frame| depend on a frame that was never decoded?
+      if (ref_info == frames_.end()) {
+        LOG(LS_INFO) << "Frame with (picture_id:spatial_id) (" << key.picture_id
+                     << ":" << int(key.spatial_layer)
+                     << " depends on a non-decoded frame more previous than "
+                     << "the last decoded frame, dropping frame.";
+        return false;
+      }
+
+      --info->second.num_missing_continuous;

[stefan-webrtc, 2016/09/21 14:50:14]

Does this mean the frame has already been decoded? Add a comment.

[philipel, 2016/09/22 11:18:38]

Yes, since this |ref_key| refers to a frame more previous than
|last_decoded_frame_it_| and |ref_key| exist, it means that this frame has
already been decoded which also means that it is continuous.

+      --info->second.num_missing_decodable;
+

[stefan-webrtc, 2016/09/21 14:50:13]

Remove empty line

[philipel, 2016/09/22 11:18:38]

Done.

+    } 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);
+    ++info->second.num_missing_continuous;
+    ++info->second.num_missing_decodable;
+
     FrameKey ref_key(frame.picture_id, frame.spatial_layer - 1);
-    if (decoded_frames_.find(ref_key) == decoded_frames_.end())
-      return false;
+    auto ref_info = frames_.insert(std::make_pair(ref_key, FrameInfo())).first;

[stefan-webrtc, 2016/09/21 14:50:13]

When doing things like this I think it would be good to have a comment saying
"Find the reference frame or create an empty FrameInfo if it hasn't been
received yet."

[philipel, 2016/09/22 11:18:38]

Done.

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