Fix MSE GC, make it less aggressive, more spec-compliant

media/filters/source_buffer_stream.cc

 // Copyright (c) 2012 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 "media/filters/source_buffer_stream.h"
 
 #include <algorithm>
 #include <map>
 #include <sstream>
 
@@ skipping 374 matching lines @@
   // are appended to the range covered by |track_buffer_|.
   if (!track_buffer_.empty()) {
     DecodeTimestamp keyframe_timestamp =
         FindKeyframeAfterTimestamp(track_buffer_.front()->GetDecodeTimestamp());
     if (keyframe_timestamp != kNoDecodeTimestamp())
       PruneTrackBuffer(keyframe_timestamp);
   }
 
   SetSelectedRangeIfNeeded(next_buffer_timestamp);
 
-  GarbageCollectIfNeeded();
-
   DVLOG(1) << __FUNCTION__ << " " << GetStreamTypeName()
            << ": done. ranges_=" << RangesToString(ranges_);
   DCHECK(IsRangeListSorted(ranges_));
   DCHECK(OnlySelectedRangeIsSeeked());
   return true;
 }
 
 void SourceBufferStream::Remove(base::TimeDelta start, base::TimeDelta end,
                                 base::TimeDelta duration) {
   DVLOG(1) << __FUNCTION__ << " " << GetStreamTypeName()
@@ skipping 227 matching lines @@
   }
 }
 
 void SourceBufferStream::SetConfigIds(const BufferQueue& buffers) {
   for (BufferQueue::const_iterator itr = buffers.begin();
        itr != buffers.end(); ++itr) {
     (*itr)->SetConfigId(append_config_index_);
   }
 }
 
-void SourceBufferStream::GarbageCollectIfNeeded() {
+bool SourceBufferStream::GarbageCollectIfNeeded(DecodeTimestamp media_time) {
+  DCHECK(media_time != kNoDecodeTimestamp());
   // Compute size of |ranges_|.
   size_t ranges_size = 0;
   for (RangeList::iterator itr = ranges_.begin(); itr != ranges_.end(); ++itr)
     ranges_size += (*itr)->size_in_bytes();
 
   // Return if we're under or at the memory limit.
   if (ranges_size <= memory_limit_)
-    return;
+    return true;
 
   size_t bytes_to_free = ranges_size - memory_limit_;
 
   DVLOG(2) << __FUNCTION__ << " " << GetStreamTypeName() << ": Before GC"
+           << " media_time=" << media_time.InSecondsF()
+           << " ranges_=" << RangesToString(ranges_)
            << " ranges_size=" << ranges_size
-           << " ranges_=" << RangesToString(ranges_)
-           << " memory_limit_=" << memory_limit_;
+           << " memory_limit_=" << memory_limit_
+           << " last_appended_buffer_timestamp_="
+           << last_appended_buffer_timestamp_.InSecondsF();
 
-  // Begin deleting after the last appended buffer.
-  size_t bytes_freed = FreeBuffersAfterLastAppended(bytes_to_free);
+  size_t bytes_freed = 0;
 
-  // Begin deleting from the front.
-  if (bytes_freed < bytes_to_free)
-    bytes_freed += FreeBuffers(bytes_to_free - bytes_freed, false);
+  // If last appended buffer position was earlier than the current playback time
+  // then try deleting data between last append and current media_time.
+  if (last_appended_buffer_timestamp_ != kNoDecodeTimestamp() &&
+      last_appended_buffer_timestamp_ < media_time) {
+    size_t between = FreeBuffersAfterLastAppended(bytes_to_free, media_time);
+    DVLOG(3) << __FUNCTION__ << " FreeBuffersAfterLastAppended "
+             << " released " << between << " bytes"
+             << " ranges_=" << RangesToString(ranges_);
+    bytes_freed += between;
 
-  // Begin deleting from the back.
-  if (bytes_freed < bytes_to_free)
-    bytes_freed += FreeBuffers(bytes_to_free - bytes_freed, true);
+    // 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()) {
+      DCHECK((*range_for_next_append_)->GetStartTimestamp() <= media_time);
+      media_time = (*range_for_next_append_)->GetStartTimestamp();

[wolenetz, 2015/08/12 21:09:57]

This may be too lax, though web apps can follow-up a failed (Prepare)Append's
"QuotaExceededError" with app-directed Remove(). How often do you think this
might break existing apps that may not expect built-in GC to not be so
aggressive any longer?  For instance, media_time could very frequently become
time 0 in this case, though the app may have only re-appended some buffers much
later than time 0 most recently.

Have you run this change by YouTube, Shaka, dash.js, etc folks to see if there
already exist robust app-directed Remove() implementations in common players
when the API gives QuotaExceededError on Append{Buffer,Stream}?

Also, note that this change along with the Blink change, while compliant with
spec in only GC'ing prior to main AppendBuffer() [and not incrementally across
each asynch append], substantially increases the risk of the hardcoded stream
buffer limits being exceeded due to arbitrarily sized stream or buffer appends.
Ditto my question: have you run this expectation change by the common player
folks to make sure we're not breaking major players with this change, especially
on memory-limited devices? (Solution for this paragraph would be to communicate
clearly with major players that appends should be granular, especially on
memory-limited platforms.)

[servolk, 2015/08/13 00:31:42]

Wait, we will only adjust media time here if range_for_next_append_ is valid
(not ranges_.end()) and only when last_appended_buffer_timestamp_ is less than
the current media_time (see the condition of the outer if). So I think we are
going to hit this code path relatively infrequently and only for players that
start appending data at the new position before issuing a seek request (Netflix
app is one example I'm aware of). And even in those cases, we are not resetting
media_time to 0, we are resetting it to
(*range_for_next_append_)->GetStartTimestamp(), which should be the beginning of
the range where the most recent append happened.
This will indeed make the GC algorithm less aggressive, but that's the point of
this CL! Previously apps were breaking in this case anyway, because they didn't
expect the newly appended data to be removed (crbug.com/440173 happened exactly
because of this excessive aggressiveness). But now we'll throw a
QuotaExceededErr exception, instead of removing unconsumed data, to give the
apps a chance to recover (e.g. by issuing a seek to the new position, which is
now guaranteed to have some data buffered).

I have reached out to strobe@ who works on YouTube player, I'll add you to that
mail thread shortly. I haven't contacted anyone else yet. I certainly agree that
we should notify MSE API users about this, but I'm not sure what would be the
best way to reach them. Do you know who would be the right people to follow up
on this from Shaka team and dash.js?

Re your last point - I'm not sure I understand your concern. It doesn't matter
if we do GC incrementally for each async append or if we do it once before a big
append. What matters is the total size of data being appended. If the total size
is enough to bring memory usage over the MSE buffer limits, then it will trigger
GC sooner or later anyway and current GC will remove some data that shouldn't be
removed. The problem is that currently GC just removes this data and leaves the
SB in a bad state (with gaps or data missing where the JS app expects it to be
present), and then we are toasted anyway. After this change we'll notify the app
(by throwing the QuotaExceeded exception) that there's not enough space in SB.
And then it's up to the app to either remove some data or wait a little bit
until more data is consumed and then attempt to append again.

+    }
+  }
+
+  // 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_);
+    bytes_freed += front;
+  }
+
+  // Try removing data from the back of the SourceBuffer, until we reach the
+  // 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"
+             << " ranges_=" << RangesToString(ranges_);
+    bytes_freed += back;
+  }
 
   DVLOG(2) << __FUNCTION__ << " " << GetStreamTypeName() << ": After GC"
+           << " bytes_to_free=" << bytes_to_free
            << " bytes_freed=" << bytes_freed
            << " ranges_=" << RangesToString(ranges_);
+
+  return bytes_freed >= bytes_to_free;
 }
 
 size_t SourceBufferStream::FreeBuffersAfterLastAppended(
-    size_t total_bytes_to_free) {
-  DecodeTimestamp next_buffer_timestamp = GetNextBufferTimestamp();
-  if (last_appended_buffer_timestamp_ == kNoDecodeTimestamp() ||
-      next_buffer_timestamp == kNoDecodeTimestamp() ||
-      last_appended_buffer_timestamp_ >= next_buffer_timestamp) {
-    return 0;
-  }
+    size_t total_bytes_to_free, DecodeTimestamp media_time) {
+  DVLOG(4) << __FUNCTION__ << " last_appended_buffer_timestamp_="
+            << last_appended_buffer_timestamp_.InSecondsF()
+            << " media_time=" << media_time.InSecondsF();
 
   DecodeTimestamp remove_range_start = last_appended_buffer_timestamp_;
   if (last_appended_buffer_is_keyframe_)
     remove_range_start += GetMaxInterbufferDistance();
 
   DecodeTimestamp remove_range_start_keyframe = FindKeyframeAfterTimestamp(
       remove_range_start);
   if (remove_range_start_keyframe != kNoDecodeTimestamp())
     remove_range_start = remove_range_start_keyframe;
-  if (remove_range_start >= next_buffer_timestamp)
+  if (remove_range_start >= media_time)
     return 0;
 
   DecodeTimestamp remove_range_end;
   size_t bytes_freed = GetRemovalRange(remove_range_start,
-                                       next_buffer_timestamp,
+                                       media_time,
                                        total_bytes_to_free,
                                        &remove_range_end);
   if (bytes_freed > 0) {
+    DVLOG(4) << __FUNCTION__ << " removing ["
+             << remove_range_start.ToPresentationTime().InSecondsF() << ";"
+             << remove_range_end.ToPresentationTime().InSecondsF() << "]";
     Remove(remove_range_start.ToPresentationTime(),
            remove_range_end.ToPresentationTime(),
-           next_buffer_timestamp.ToPresentationTime());
+           media_time.ToPresentationTime());
   }
 
   return bytes_freed;
 }
 
 size_t SourceBufferStream::GetRemovalRange(
     DecodeTimestamp start_timestamp, DecodeTimestamp end_timestamp,
     size_t total_bytes_to_free, DecodeTimestamp* removal_end_timestamp) {
   DCHECK(start_timestamp >= DecodeTimestamp()) << start_timestamp.InSecondsF();
   DCHECK(start_timestamp < end_timestamp)
@@ skipping 12 matching lines @@
 
     size_t bytes_to_free = total_bytes_to_free - bytes_freed;
     size_t bytes_removed = range->GetRemovalGOP(
         start_timestamp, end_timestamp, bytes_to_free, removal_end_timestamp);
     bytes_freed += bytes_removed;
   }
   return bytes_freed;
 }
 
 size_t SourceBufferStream::FreeBuffers(size_t total_bytes_to_free,
+                                       DecodeTimestamp media_time,
                                        bool reverse_direction) {
   TRACE_EVENT2("media", "SourceBufferStream::FreeBuffers",
                "total bytes to free", total_bytes_to_free,
                "reverse direction", reverse_direction);
 
   DCHECK_GT(total_bytes_to_free, 0u);
   size_t bytes_freed = 0;
 
   // This range will save the last GOP appended to |range_for_next_append_|
   // if the buffers surrounding it get deleted during garbage collection.
   SourceBufferRange* new_range_for_append = NULL;
 
   while (!ranges_.empty() && bytes_freed < total_bytes_to_free) {
     SourceBufferRange* current_range = NULL;
     BufferQueue buffers;
     size_t bytes_deleted = 0;
 
     if (reverse_direction) {
       current_range = ranges_.back();
+      DVLOG(5) << "current_range=" << RangeToString(*current_range);
       if (current_range->LastGOPContainsNextBufferPosition()) {
         DCHECK_EQ(current_range, selected_range_);
+        DVLOG(5) << "current_range contains next read position, stopping GC";
         break;
       }
+      DVLOG(5) << "Deleting GOP from back: " << RangeToString(*current_range);
       bytes_deleted = current_range->DeleteGOPFromBack(&buffers);
     } else {
       current_range = ranges_.front();
-      if (current_range->FirstGOPContainsNextBufferPosition()) {
-        DCHECK_EQ(current_range, selected_range_);
+      DVLOG(5) << "current_range=" << RangeToString(*current_range);
+      if (!current_range->FirstGOPEarlierThanMediaTime(media_time)) {
+        // We have removed all data up to the GOP that contains current playback
+        // position, we can't delete any further.
+        DVLOG(5) << "current_range contains playback position, stopping GC";
         break;
       }
+      DVLOG(4) << "Deleting GOP from front: " << RangeToString(*current_range);
       bytes_deleted = current_range->DeleteGOPFromFront(&buffers);
     }
 
     // Check to see if we've just deleted the GOP that was last appended.
     DecodeTimestamp end_timestamp = buffers.back()->GetDecodeTimestamp();
     if (end_timestamp == last_appended_buffer_timestamp_) {
       DCHECK(last_appended_buffer_timestamp_ != kNoDecodeTimestamp());
       DCHECK(!new_range_for_append);
+
       // Create a new range containing these buffers.
       new_range_for_append = new SourceBufferRange(
           TypeToGapPolicy(GetType()),
           buffers, kNoDecodeTimestamp(),
           base::Bind(&SourceBufferStream::GetMaxInterbufferDistance,
                      base::Unretained(this)));
       range_for_next_append_ = ranges_.end();
     } else {
       bytes_freed += bytes_deleted;
     }
 
     if (current_range->size_in_bytes() == 0) {
       DCHECK_NE(current_range, selected_range_);
       DCHECK(range_for_next_append_ == ranges_.end() ||
              *range_for_next_append_ != current_range);
       delete current_range;
       reverse_direction ? ranges_.pop_back() : ranges_.pop_front();
     }
+
+    if (reverse_direction && new_range_for_append) {
+      // We don't want to delete any further, or we'll be creating gaps
+      break;
+    }
   }
 
   // Insert |new_range_for_append| into |ranges_|, if applicable.
   if (new_range_for_append) {
     range_for_next_append_ = AddToRanges(new_range_for_append);
     DCHECK(range_for_next_append_ != ranges_.end());
 
     // Check to see if we need to merge |new_range_for_append| with the range
     // before or after it. |new_range_for_append| is created whenever the last
     // GOP appended is encountered, regardless of whether any buffers after it
@@ skipping 409 matching lines @@
 }
 
 void SourceBufferStream::SeekAndSetSelectedRange(
     SourceBufferRange* range, DecodeTimestamp seek_timestamp) {
   if (range)
     range->Seek(seek_timestamp);
   SetSelectedRange(range);
 }
 
 void SourceBufferStream::SetSelectedRange(SourceBufferRange* range) {
-  DVLOG(1) << __FUNCTION__ << " " << GetStreamTypeName()
-           << ": " << selected_range_ << " -> " << range;
+  DVLOG(1) << __FUNCTION__ << " " << GetStreamTypeName() << ": "
+           << selected_range_ << " "
+           << (selected_range_ ? RangeToString(*selected_range_) : "")
+           << " -> " << range << " " << (range ? RangeToString(*range) : "");
   if (selected_range_)
     selected_range_->ResetNextBufferPosition();
   DCHECK(!range || range->HasNextBufferPosition());
   selected_range_ = range;
 }
 
 Ranges<base::TimeDelta> SourceBufferStream::GetBufferedTime() const {
   Ranges<base::TimeDelta> ranges;
   for (RangeList::const_iterator itr = ranges_.begin();
        itr != ranges_.end(); ++itr) {
@@ skipping 432 matching lines @@
     return false;
 
   DCHECK_NE(have_splice_buffers, have_preroll_buffer);
   splice_buffers_index_ = 0;
   pending_buffer_.swap(*out_buffer);
   pending_buffers_complete_ = false;
   return true;
 }
 
 }  // namespace media