Fix seeking back in the new MSE GC algorithm

media/filters/source_buffer_stream.cc

Index: media/filters/source_buffer_stream.cc
diff --git a/media/filters/source_buffer_stream.cc b/media/filters/source_buffer_stream.cc
index e17a4f1c91952b64cf280a9777404e4adeec71d2..fd1dd14f8415e879285fa22a873f6e6252127385 100644
--- a/media/filters/source_buffer_stream.cc
+++ b/media/filters/source_buffer_stream.cc
@@ -619,8 +619,12 @@ bool SourceBufferStream::GarbageCollectIfNeeded(DecodeTimestamp media_time,
 
   // Sanity and overflow checks
   if ((newDataSize > memory_limit_) ||
-      (ranges_size + newDataSize < ranges_size))
+      (ranges_size + newDataSize < ranges_size)) {
+    LOG(WARNING) << "GarbageCollectIfNeeded: memory_limit_=" << memory_limit_

[wolenetz, 2015/09/17 18:57:54]

Please change to LIMITED_MEDIA_LOG(DEBUG...), so chrome://media-internals can
get detail on at least desktop builds when this path is reached.

I'll save other nit-like comments for later.

[servolk, 2015/09/18 01:29:28]

Done.

+                 << " ranges_size=" << ranges_size << " newDataSize="
+                 << newDataSize;
     return false;
+  }
 
   // Return if we're under or at the memory limit.
   if (ranges_size + newDataSize <= memory_limit_)
@@ -628,9 +632,22 @@ bool SourceBufferStream::GarbageCollectIfNeeded(DecodeTimestamp media_time,
 
   size_t bytes_to_free = ranges_size + newDataSize - memory_limit_;
 
+  // If media_time is not within one of the currently buffered ranges, then we
+  // likely have a pending seek and we should allow GC to remove data more
+  // aggressively for the upcoming append to allow seeking to proceed.
+  bool seek_pending = true;
+  for (auto& r : ranges_) {

[wolenetz, 2015/09/17 18:57:54]

Bear with me. I think the tl;dr is this is ok.

I wonder if we're possibly being too greedy: this logic could remove the
keyframe upon which media_time depends. It is a hard problem to determine if
this is the case, though, since MSE spec allows (and Chrome will soon) media
segments to begin with a non-keyframe. |media_time| could be within one of these
dependent media segments that follows an existing buffered media range that
contains the prerequisite keyframe data.

To be safest, if there is a buffered range prior to |media_time|, then it must
contain a keyframe. Maybe we should not collect the last keyframe (nor its
dependent frames) from that buffered range, in case the
eventually-appended-media at |media_time| depends upon it.

Granted, I think this level of protection may be also going too far, since the
MSE coded frame processing algorithm drops non-keyframes following a
discontinuity, and such a discontinuity would occur if appends go out of order.
So, last append would need to be < media_time for CFP to allow newly appended
non-keyframes to possibly become buffered following the last append.

Soooooo.... For now, I think this logic seems ok.

A couple other comments:
Is there a reason to not initialize seek_pending (local) to whatever the current
value of |seek_pending_| (member) is prior to this loop?
IIUC, media_time (when seeking) is a secondary indicator: seek_pending_ should
be the true knowledge within the SBS of whether or not there is currently an
unsatisfied seek. How might media_time have more "correct" indication? Does
seek_buffer_timestamp_ differ from media_time when there's an unsatisfied seek
and GC is called?

Finally:
If we need to find if there is a potential range for which media_time is a
member, we might be able to use
https://code.google.com/p/chromium/codesearch#chromium/src/media/filters/sour...
although this method allows for returning true when |media_time_| is "next in
sequence" to the end of the matched range, so I don't think using that helper
as-is would be viable. Is there not some other helper that does this loop
already? (and if not, perhaps making this loop a helper or modifying the
existing helper to conditionally be more strict, might be a better way to reuse
existing code).

[servolk, 2015/09/18 01:29:28]

Wait, as far as I understand GOP handling is already done by FreeBuffers (which
uses SourceBufferRange::DeleteGOP* methods, so we always delete GOP at a time,
i.e. key frame and all data that depends on it). I'm not sure how this should
work in cases where newly appended segments are allowed to start with
non-keyframes. I agree that for now this logic is probably ok, since we don't
currently allow that.
Re seek_pending - I just didn't know that SBS already keeps track of that, we
can indeed just use the IsSeekPending flag instead of trying to detect pending
seek by checking media_time against buffered ranges. So then we don't need to
use iteration over ranges and don't need to use FindExistingRangeFor.

+    if (media_time >= r->GetStartTimestamp() &&
+        media_time <= r->GetEndTimestamp()) {
+      seek_pending = false;
+      break;
+    }
+  }
+
   DVLOG(2) << __FUNCTION__ << " " << GetStreamTypeName() << ": Before GC"
            << " media_time=" << media_time.InSecondsF()
            << " ranges_=" << RangesToString(ranges_)
+           << " seek_pending=" << seek_pending
            << " ranges_size=" << ranges_size
            << " newDataSize=" << newDataSize
            << " memory_limit_=" << memory_limit_
@@ -649,22 +666,60 @@ bool SourceBufferStream::GarbageCollectIfNeeded(DecodeTimestamp media_time,
              << " ranges_=" << RangesToString(ranges_);
     bytes_freed += between;
 
-    // If the last append happened before the current playback position
-    // |media_time|, then JS player is probably preparing to seek back and we
-    // should try to preserve all most recently appended data (which is in
-    // range_for_next_append_) from being removed by GC (see crbug.com/440173)
-    if (range_for_next_append_ != ranges_.end()) {
+    // Some players start appending data at the new seek target position before
+    // actually initiating the seek operation (i.e. they try to improve seek
+    // performance by prebuffering some data at the seek target position and
+    // initiating seek once enough data is pre-buffered. In those cases we'll
+    // see that data is being appended at some new position, but |media_time| is
+    // still going to be in some buffered range and the logic for detecting
+    // |pending_seek| is not going to work. In this situation we need to try
+    // preserving the most recently appended data, i.e. data belonging to the
+    // same buffered range as the most recent append.
+    if (range_for_next_append_ != ranges_.end() && !seek_pending) {
       DCHECK((*range_for_next_append_)->GetStartTimestamp() <= media_time);
       media_time = (*range_for_next_append_)->GetStartTimestamp();
     }
   }
 
+  // If there is an unsatisfied pending seek, we can safely remove all data that
+  // is earlier than seek target, then remove from the back until we reach the
+  // most recently appended GOP and then remove from the front if we still don't
+  // have enough space for the upcoming append.
+  if (bytes_freed < bytes_to_free && seek_pending) {
+    DCHECK(!ranges_.empty());
+    // All data earlier than the seek target |media_time| can be removed safely
+    size_t front = FreeBuffers(bytes_to_free - bytes_freed, media_time, false);
+    DVLOG(3) << __FUNCTION__ << " Removed " << front << " bytes from the"
+             << " front. ranges_=" << RangesToString(ranges_);
+    bytes_freed += front;
+
+    // If removing data earlier than |media_time| didn't free up enough space,
+    // then try deleting from the back until we reach most recently appended GOP
+    if (bytes_freed < bytes_to_free) {
+      size_t back = FreeBuffers(bytes_to_free - bytes_freed, media_time, true);
+      DVLOG(3) << __FUNCTION__ << " Removed " << back << " bytes from the back"
+               << " ranges_=" << RangesToString(ranges_);
+      bytes_freed += back;
+    }
+
+    // If even that wasn't enough, then try greedily deleting from the front,
+    // that should allow us to remove as much data as necessary to succeed.
+    if (bytes_freed < bytes_to_free) {
+      size_t front2 = FreeBuffers(bytes_to_free - bytes_freed,
+                                  ranges_.back()->GetEndTimestamp(), false);
+      DVLOG(3) << __FUNCTION__ << " Removed " << front << " bytes from the"
+               << " front. ranges_=" << RangesToString(ranges_);
+      bytes_freed += front2;
+    }
+    DCHECK(bytes_freed >= bytes_to_free);
+  }
+
   // Try removing data from the front of the SourceBuffer up to |media_time|
   // position.
   if (bytes_freed < bytes_to_free) {
     size_t front = FreeBuffers(bytes_to_free - bytes_freed, media_time, false);
-    DVLOG(3) << __FUNCTION__ << " Removed " << front << " bytes from the front"
-             << " ranges_=" << RangesToString(ranges_);
+    DVLOG(3) << __FUNCTION__ << " Removed " << front << " bytes from the"
+             << " front. ranges_=" << RangesToString(ranges_);
     bytes_freed += front;
   }
 
@@ -672,7 +727,7 @@ bool SourceBufferStream::GarbageCollectIfNeeded(DecodeTimestamp media_time,
   // most recent append position.
   if (bytes_freed < bytes_to_free) {
     size_t back = FreeBuffers(bytes_to_free - bytes_freed, media_time, true);
-    DVLOG(3) << __FUNCTION__ << " Removed " << back << " bytes from the back"
+    DVLOG(3) << __FUNCTION__ << " Removed " << back << " bytes from the back."
              << " ranges_=" << RangesToString(ranges_);
     bytes_freed += back;
   }