Tweak GC algorithm in MSE to remove the buffers after last appended first.

BUG=293408

Review URL: https://chromiumcodereview.appspot.com/23919008

git-svn-id: svn://svn.chromium.org/chrome/trunk/src@224975 0039d316-1c4b-4281-b951-d872f2087c98

3 files changed, 305 insertions, 1 deletions

diff --git a/media/filters/source_buffer_stream.cc b/media/filters/source_buffer_stream.cc
index 15f894c..0f46f71 100644
--- a/media/filters/source_buffer_stream.cc
+++ b/media/filters/source_buffer_stream.cc
@@ -88,6 +88,15 @@ class SourceBufferRange {
   int DeleteGOPFromFront(BufferQueue* deleted_buffers);
   int DeleteGOPFromBack(BufferQueue* deleted_buffers);
 
+  // Gets the range of GOP to secure at least |bytes_to_free| from
+  // [|start_timestamp|, |end_timestamp|).
+  // Returns the size of the buffers to secure if the buffers of
+  // [|start_timestamp|, |end_removal_timestamp|) is removed.
+  // Will not update |end_removal_timestamp| if the returned size is 0.
+  int GetRemovalGOP(
+      base::TimeDelta start_timestamp, base::TimeDelta end_timestamp,
+      int bytes_to_free, base::TimeDelta* end_removal_timestamp);
+
   // Indicates whether the GOP at the beginning or end of the range contains the
   // next buffer position.
   bool FirstGOPContainsNextBufferPosition() const;
@@ -653,14 +662,73 @@ void SourceBufferStream::GarbageCollectIfNeeded() {
 
   int bytes_to_free = ranges_size - memory_limit_;
 
+  // Begin deleting after the last appended buffer.
+  int bytes_freed = FreeBuffersAfterLastAppended(bytes_to_free);
+
   // Begin deleting from the front.
-  int bytes_freed = FreeBuffers(bytes_to_free, false);
+  if (bytes_to_free - bytes_freed > 0)
+    bytes_freed += FreeBuffers(bytes_to_free - bytes_freed, false);
 
   // Begin deleting from the back.
   if (bytes_to_free - bytes_freed > 0)
     FreeBuffers(bytes_to_free - bytes_freed, true);
 }
 
+int SourceBufferStream::FreeBuffersAfterLastAppended(int total_bytes_to_free) {
+  base::TimeDelta next_buffer_timestamp = GetNextBufferTimestamp();
+  if (last_appended_buffer_timestamp_ == kNoTimestamp() ||
+      next_buffer_timestamp == kNoTimestamp() ||
+      last_appended_buffer_timestamp_ >= next_buffer_timestamp) {
+    return 0;
+  }
+
+  base::TimeDelta remove_range_start = last_appended_buffer_timestamp_;
+  if (last_appended_buffer_is_keyframe_)
+    remove_range_start += GetMaxInterbufferDistance();
+
+  base::TimeDelta remove_range_start_keyframe = FindKeyframeAfterTimestamp(
+      remove_range_start);
+  if (remove_range_start_keyframe != kNoTimestamp())
+    remove_range_start = remove_range_start_keyframe;
+  if (remove_range_start >= next_buffer_timestamp)
+    return 0;
+
+  base::TimeDelta remove_range_end;
+  int bytes_freed = GetRemovalRange(
+      remove_range_start, next_buffer_timestamp, total_bytes_to_free,
+      &remove_range_end);
+  if (bytes_freed > 0)
+    Remove(remove_range_start, remove_range_end, next_buffer_timestamp);
+  return bytes_freed;
+}
+
+int SourceBufferStream::GetRemovalRange(
+    base::TimeDelta start_timestamp, base::TimeDelta end_timestamp,
+    int total_bytes_to_free, base::TimeDelta* removal_end_timestamp) {
+  DCHECK(start_timestamp >= base::TimeDelta()) << start_timestamp.InSecondsF();
+  DCHECK(start_timestamp < end_timestamp)
+      << "start " << start_timestamp.InSecondsF()
+      << ", end " << end_timestamp.InSecondsF();
+
+  int bytes_to_free = total_bytes_to_free;
+  int bytes_freed = 0;
+
+  for (RangeList::iterator itr = ranges_.begin();
+       itr != ranges_.end() && bytes_to_free > 0; ++itr) {
+    SourceBufferRange* range = *itr;
+    if (range->GetStartTimestamp() >= end_timestamp)
+      break;
+    if (range->GetEndTimestamp() < start_timestamp)
+      continue;
+
+    int bytes_removed = range->GetRemovalGOP(
+        start_timestamp, end_timestamp, bytes_to_free, removal_end_timestamp);
+    bytes_to_free -= bytes_removed;
+    bytes_freed += bytes_removed;
+  }
+  return bytes_freed;
+}
+
 int SourceBufferStream::FreeBuffers(int total_bytes_to_free,
                                     bool reverse_direction) {
   TRACE_EVENT2("mse", "SourceBufferStream::FreeBuffers",
@@ -1627,6 +1695,45 @@ int SourceBufferRange::DeleteGOPFromBack(BufferQueue* deleted_buffers) {
   return total_bytes_deleted;
 }
 
+int SourceBufferRange::GetRemovalGOP(
+    base::TimeDelta start_timestamp, base::TimeDelta end_timestamp,
+    int total_bytes_to_free, base::TimeDelta* removal_end_timestamp) {
+  int bytes_to_free = total_bytes_to_free;
+  int bytes_removed = 0;
+
+  KeyframeMap::iterator gop_itr = GetFirstKeyframeAt(start_timestamp, false);
+  int keyframe_index = gop_itr->second - keyframe_map_index_base_;
+  BufferQueue::iterator buffer_itr = buffers_.begin() + keyframe_index;
+  KeyframeMap::iterator gop_end = keyframe_map_.end();
+  if (end_timestamp < GetBufferedEndTimestamp())
+    gop_end = GetFirstKeyframeBefore(end_timestamp);
+
+  // Check if the removal range is within a GOP and skip the loop if so.
+  // [keyframe]...[start_timestamp]...[end_timestamp]...[keyframe]
+  KeyframeMap::iterator gop_itr_prev = gop_itr;
+  if (gop_itr_prev != keyframe_map_.begin() && --gop_itr_prev == gop_end)
+    gop_end = gop_itr;
+
+  while (gop_itr != gop_end && bytes_to_free > 0) {
+    ++gop_itr;
+
+    int gop_size = 0;
+    int next_gop_index = gop_itr == keyframe_map_.end() ?
+        buffers_.size() : gop_itr->second - keyframe_map_index_base_;
+    BufferQueue::iterator next_gop_start = buffers_.begin() + next_gop_index;
+    for (; buffer_itr != next_gop_start; ++buffer_itr)
+      gop_size += (*buffer_itr)->data_size();
+
+    bytes_removed += gop_size;
+    bytes_to_free -= gop_size;
+  }
+  if (bytes_removed > 0) {
+    *removal_end_timestamp = gop_itr == keyframe_map_.end() ?
+        GetBufferedEndTimestamp() : gop_itr->first;
+  }
+  return bytes_removed;
+}
+
 bool SourceBufferRange::FirstGOPContainsNextBufferPosition() const {
   if (!HasNextBufferPosition())
     return false;
diff --git a/media/filters/source_buffer_stream.h b/media/filters/source_buffer_stream.h
index 6167e51..b218b31 100644
--- a/media/filters/source_buffer_stream.h
+++ b/media/filters/source_buffer_stream.h
@@ -126,6 +126,8 @@ class MEDIA_EXPORT SourceBufferStream {
   }
 
  private:
+  friend class SourceBufferStreamTest;
+
   typedef std::list<SourceBufferRange*> RangeList;
 
   // Frees up space if the SourceBufferStream is taking up too much memory.
@@ -137,6 +139,20 @@ class MEDIA_EXPORT SourceBufferStream {
   // is true. Returns the number of bytes freed.
   int FreeBuffers(int total_bytes_to_free, bool reverse_direction);
 
+  // Attempts to delete approximately |total_bytes_to_free| amount of data from
+  // |ranges_|, starting after the last appended buffer before the current
+  // playback position.
+  int FreeBuffersAfterLastAppended(int total_bytes_to_free);
+
+  // Gets the removal range to secure |byte_to_free| from
+  // [|start_timestamp|, |end_timestamp|).
+  // Returns the size of buffers to secure if future
+  // Remove(|start_timestamp|, |removal_end_timestamp|, duration) is called.
+  // Will not update |removal_end_timestamp| if the returned size is 0.
+  int GetRemovalRange(base::TimeDelta start_timestamp,
+      base::TimeDelta end_timestamp, int byte_to_free,
+      base::TimeDelta* removal_end_timestamp);
+
   // Appends |new_buffers| into |range_for_new_buffers_itr|, handling start and
   // end overlaps if necessary.
   // |deleted_buffers| is an output parameter containing candidates for
diff --git a/media/filters/source_buffer_stream_unittest.cc b/media/filters/source_buffer_stream_unittest.cc
index 0507175..d0d4df2 100644
--- a/media/filters/source_buffer_stream_unittest.cc
+++ b/media/filters/source_buffer_stream_unittest.cc
@@ -119,6 +119,18 @@ class SourceBufferStreamTest : public testing::Test {
     stream_->Remove(start, end, duration);
   }
 
+  int GetRemovalRangeInMs(int start, int end, int bytes_to_free,
+                          int* removal_end) {
+    base::TimeDelta removal_end_timestamp =
+        base::TimeDelta::FromMilliseconds(*removal_end);
+    int bytes_removed = stream_->GetRemovalRange(
+        base::TimeDelta::FromMilliseconds(start),
+        base::TimeDelta::FromMilliseconds(end), bytes_to_free,
+        &removal_end_timestamp);
+    *removal_end = removal_end_timestamp.InMilliseconds();
+    return bytes_removed;
+  }
+
   void CheckExpectedRanges(const std::string& expected) {
     Ranges<base::TimeDelta> r = stream_->GetBufferedTime();
 
@@ -2136,6 +2148,47 @@ TEST_F(SourceBufferStreamTest, GarbageCollection_DeleteSeveralRanges) {
   CheckNoNextBuffer();
 }
 
+TEST_F(SourceBufferStreamTest, GarbageCollection_DeleteAfterLastAppend) {
+  // Set memory limit to 10 buffers.
+  SetMemoryLimit(10);
+
+  // Append 1 GOP starting at 310ms, 30ms apart.
+  NewSegmentAppend("310K 340 370");
+
+  // Append 2 GOPs starting at 490ms, 30ms apart.
+  NewSegmentAppend("490K 520 550 580K 610 640");
+
+  CheckExpectedRangesByTimestamp("{ [310,400) [490,670) }");
+
+  // Seek to the GOP at 580ms.
+  SeekToTimestamp(base::TimeDelta::FromMilliseconds(580));
+
+  // Append 2 GOPs before the existing ranges.
+  // So the ranges before GC are "{ [100,280) [310,400) [490,670) }".
+  NewSegmentAppend("100K 130 160 190K 220 250K");
+
+  // Should save the newly appended GOPs.
+  CheckExpectedRangesByTimestamp("{ [100,280) [580,670) }");
+}
+
+TEST_F(SourceBufferStreamTest, GarbageCollection_DeleteAfterLastAppendMerged) {
+  // Set memory limit to 10 buffers.
+  SetMemoryLimit(10);
+
+  // Append 3 GOPs starting at 400ms, 30ms apart.
+  NewSegmentAppend("400K 430 460 490K 520 550 580K 610 640");
+
+  // Seek to the GOP at 580ms.
+  SeekToTimestamp(base::TimeDelta::FromMilliseconds(580));
+
+  // Append 2 GOPs starting at 220ms, and they will be merged with the existing
+  // range.  So the range before GC is "{ [220,670) }".
+  NewSegmentAppend("220K 250 280 310K 340 370");
+
+  // Should save the newly appended GOPs.
+  CheckExpectedRangesByTimestamp("{ [220,400) [580,670) }");
+}
+
 TEST_F(SourceBufferStreamTest, GarbageCollection_NoSeek) {
   // Set memory limit to 20 buffers.
   SetMemoryLimit(20);
@@ -2479,6 +2532,134 @@ TEST_F(SourceBufferStreamTest, GarbageCollection_Performance) {
   }
 }
 
+TEST_F(SourceBufferStreamTest, GetRemovalRange_BytesToFree) {
+  // Append 2 GOPs starting at 300ms, 30ms apart.
+  NewSegmentAppend("300K 330 360 390K 420 450");
+
+  // Append 2 GOPs starting at 600ms, 30ms apart.
+  NewSegmentAppend("600K 630 660 690K 720 750");
+
+  // Append 2 GOPs starting at 900ms, 30ms apart.
+  NewSegmentAppend("900K 930 960 990K 1020 1050");
+
+  CheckExpectedRangesByTimestamp("{ [300,480) [600,780) [900,1080) }");
+
+  int remove_range_end = -1;
+  int bytes_removed = -1;
+
+  // Size 0.
+  bytes_removed = GetRemovalRangeInMs(300, 1080, 0, &remove_range_end);
+  EXPECT_EQ(-1, remove_range_end);
+  EXPECT_EQ(0, bytes_removed);
+
+  // Smaller than the size of GOP.
+  bytes_removed = GetRemovalRangeInMs(300, 1080, 1, &remove_range_end);
+  EXPECT_EQ(390, remove_range_end);
+  // Remove as the size of GOP.
+  EXPECT_EQ(3, bytes_removed);
+
+  // The same size with a GOP.
+  bytes_removed = GetRemovalRangeInMs(300, 1080, 3, &remove_range_end);
+  EXPECT_EQ(390, remove_range_end);
+  EXPECT_EQ(3, bytes_removed);
+
+  // The same size with a range.
+  bytes_removed = GetRemovalRangeInMs(300, 1080, 6, &remove_range_end);
+  EXPECT_EQ(480, remove_range_end);
+  EXPECT_EQ(6, bytes_removed);
+
+  // A frame larger than a range.
+  bytes_removed = GetRemovalRangeInMs(300, 1080, 7, &remove_range_end);
+  EXPECT_EQ(690, remove_range_end);
+  EXPECT_EQ(9, bytes_removed);
+
+  // The same size with two ranges.
+  bytes_removed = GetRemovalRangeInMs(300, 1080, 12, &remove_range_end);
+  EXPECT_EQ(780, remove_range_end);
+  EXPECT_EQ(12, bytes_removed);
+
+  // Larger than two ranges.
+  bytes_removed = GetRemovalRangeInMs(300, 1080, 14, &remove_range_end);
+  EXPECT_EQ(990, remove_range_end);
+  EXPECT_EQ(15, bytes_removed);
+
+  // The same size with the whole ranges.
+  bytes_removed = GetRemovalRangeInMs(300, 1080, 18, &remove_range_end);
+  EXPECT_EQ(1080, remove_range_end);
+  EXPECT_EQ(18, bytes_removed);
+
+  // Larger than the whole ranges.
+  bytes_removed = GetRemovalRangeInMs(300, 1080, 20, &remove_range_end);
+  EXPECT_EQ(1080, remove_range_end);
+  EXPECT_EQ(18, bytes_removed);
+}
+
+TEST_F(SourceBufferStreamTest, GetRemovalRange_Range) {
+  // Append 2 GOPs starting at 300ms, 30ms apart.
+  NewSegmentAppend("300K 330 360 390K 420 450");
+
+  // Append 2 GOPs starting at 600ms, 30ms apart.
+  NewSegmentAppend("600K 630 660 690K 720 750");
+
+  // Append 2 GOPs starting at 900ms, 30ms apart.
+  NewSegmentAppend("900K 930 960 990K 1020 1050");
+
+  CheckExpectedRangesByTimestamp("{ [300,480) [600,780) [900,1080) }");
+
+  int remove_range_end = -1;
+  int bytes_removed = -1;
+
+  // Within a GOP and no keyframe.
+  bytes_removed = GetRemovalRangeInMs(630, 660, 20, &remove_range_end);
+  EXPECT_EQ(-1, remove_range_end);
+  EXPECT_EQ(0, bytes_removed);
+
+  // Across a GOP and no keyframe.
+  bytes_removed = GetRemovalRangeInMs(630, 750, 20, &remove_range_end);
+  EXPECT_EQ(-1, remove_range_end);
+  EXPECT_EQ(0, bytes_removed);
+
+  // The same size with a range.
+  bytes_removed = GetRemovalRangeInMs(600, 780, 20, &remove_range_end);
+  EXPECT_EQ(780, remove_range_end);
+  EXPECT_EQ(6, bytes_removed);
+
+  // One frame larger than a range.
+  bytes_removed = GetRemovalRangeInMs(570, 810, 20, &remove_range_end);
+  EXPECT_EQ(780, remove_range_end);
+  EXPECT_EQ(6, bytes_removed);
+
+  // Facing the other ranges.
+  bytes_removed = GetRemovalRangeInMs(480, 900, 20, &remove_range_end);
+  EXPECT_EQ(780, remove_range_end);
+  EXPECT_EQ(6, bytes_removed);
+
+  // In the midle of the other ranges, but not including any GOP.
+  bytes_removed = GetRemovalRangeInMs(420, 960, 20, &remove_range_end);
+  EXPECT_EQ(780, remove_range_end);
+  EXPECT_EQ(6, bytes_removed);
+
+  // In the middle of the other ranges.
+  bytes_removed = GetRemovalRangeInMs(390, 990, 20, &remove_range_end);
+  EXPECT_EQ(990, remove_range_end);
+  EXPECT_EQ(12, bytes_removed);
+
+  // A frame smaller than the whole ranges.
+  bytes_removed = GetRemovalRangeInMs(330, 1050, 20, &remove_range_end);
+  EXPECT_EQ(990, remove_range_end);
+  EXPECT_EQ(12, bytes_removed);
+
+  // The same with the whole ranges.
+  bytes_removed = GetRemovalRangeInMs(300, 1080, 20, &remove_range_end);
+  EXPECT_EQ(1080, remove_range_end);
+  EXPECT_EQ(18, bytes_removed);
+
+  // Larger than the whole ranges.
+  bytes_removed = GetRemovalRangeInMs(270, 1110, 20, &remove_range_end);
+  EXPECT_EQ(1080, remove_range_end);
+  EXPECT_EQ(18, bytes_removed);
+}
+
 TEST_F(SourceBufferStreamTest, ConfigChange_Basic) {
   VideoDecoderConfig new_config = TestVideoConfig::Large();
   ASSERT_FALSE(new_config.Matches(config_));