Tweak Garbage Collection algorithm in MediaSource to save last GOP appended

This CL changes the GC algorithm to also preserve the last GOP appended to
prevent crashing/garbage output.

BUG=150946

Review URL: https://codereview.chromium.org/11035013

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

3 files changed, 413 insertions, 159 deletions

diff --git a/media/filters/source_buffer_stream.cc b/media/filters/source_buffer_stream.cc
index 888934a..acdcebf 100644
--- a/media/filters/source_buffer_stream.cc
+++ b/media/filters/source_buffer_stream.cc
@@ -87,14 +87,16 @@ class SourceBufferRange {
   // Deletes all buffers in range.
   bool DeleteAll(BufferQueue* deleted_buffers);
 
-  // Attempts to free |bytes| data from the range, preferring to delete at the
-  // beginning of the range. Deletes data in GOPS at a time so that the range
-  // always begins with a keyframe. Returns the number of bytes freed.
-  int FreeFromStart(int bytes);
+  // Deletes a GOP from the front or back of the range and moves these
+  // buffers into |deleted_buffers|. Returns the number of bytes deleted from
+  // the range (i.e. the size in bytes of |deleted_buffers|).
+  int DeleteGOPFromFront(BufferQueue* deleted_buffers);
+  int DeleteGOPFromBack(BufferQueue* deleted_buffers);
 
-  // Attempts to free |bytes| data from the range, preferring to delete at the
-  // end of the range. Returns the number of bytes freed.
-  int FreeFromEnd(int bytes);
+  // Indicates whether the GOP at the beginning or end of the range contains the
+  // next buffer position.
+  bool FirstGOPContainsNextBufferPosition() const;
+  bool LastGOPContainsNextBufferPosition() const;
 
   // Updates |out_buffer| with the next buffer in presentation order. Seek()
   // must be called before calls to GetNextBuffer(), and buffers are returned
@@ -157,7 +159,7 @@ class SourceBufferRange {
   int size_in_bytes() const { return size_in_bytes_; }
 
  private:
-  typedef std::map<base::TimeDelta, size_t> KeyframeMap;
+  typedef std::map<base::TimeDelta, int> KeyframeMap;
 
   // Seeks the range to the next keyframe after |timestamp|. If
   // |skip_given_timestamp| is true, the seek will go to a keyframe with a
@@ -532,34 +534,87 @@ void SourceBufferStream::GarbageCollectIfNeeded() {
   int bytes_to_free = ranges_size - memory_limit_;
 
   // Begin deleting from the front.
-  while (!ranges_.empty() && bytes_to_free > 0) {
-    SourceBufferRange* current_range = ranges_.front();
-    bytes_to_free -= current_range->FreeFromStart(bytes_to_free);
+  int bytes_freed = FreeBuffers(bytes_to_free, false);
 
-    // If the |current_range| still has data left after freeing, we should not
-    // delete any more data in this direction.
-    if (current_range->size_in_bytes() > 0)
-      break;
+  // Begin deleting from the back.
+  if (bytes_to_free - bytes_freed > 0)
+    FreeBuffers(bytes_to_free - bytes_freed, true);
+}
 
-    DCHECK_NE(current_range, selected_range_);
-    delete current_range;
-    ranges_.pop_front();
-  }
+int SourceBufferStream::FreeBuffers(int total_bytes_to_free,
+                                    bool reverse_direction) {
+  DCHECK_GT(total_bytes_to_free, 0);
+  int bytes_to_free = total_bytes_to_free;
+  int 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;
 
-  // Begin deleting from the back.
   while (!ranges_.empty() && bytes_to_free > 0) {
-    SourceBufferRange* current_range = ranges_.back();
-    bytes_to_free -= current_range->FreeFromEnd(bytes_to_free);
 
-    // If the |current_range| still has data left after freeing, we should not
-    // delete any more data in this direction.
-    if (current_range->size_in_bytes() > 0)
-      break;
+    SourceBufferRange* current_range = NULL;
+    BufferQueue buffers;
+    int bytes_deleted = 0;
+
+    if (reverse_direction) {
+      current_range = ranges_.back();
+      if (current_range->LastGOPContainsNextBufferPosition()) {
+        DCHECK_EQ(current_range, selected_range_);
+        break;
+      }
+      bytes_deleted = current_range->DeleteGOPFromBack(&buffers);
+    } else {
+      current_range = ranges_.front();
+      if (current_range->FirstGOPContainsNextBufferPosition()) {
+        DCHECK_EQ(current_range, selected_range_);
+        break;
+      }
+      bytes_deleted = current_range->DeleteGOPFromFront(&buffers);
+    }
 
-    DCHECK_NE(current_range, selected_range_);
-    delete current_range;
-    ranges_.pop_back();
+    // Check to see if we've just deleted the GOP that was last appended.
+    if (buffers.back()->GetDecodeTimestamp() == last_buffer_timestamp_) {
+      DCHECK(last_buffer_timestamp_ != kNoTimestamp());
+      DCHECK(!new_range_for_append);
+      // Create a new range containing these buffers.
+      new_range_for_append = new SourceBufferRange(
+            buffers, kNoTimestamp(),
+            base::Bind(&SourceBufferStream::GetMaxInterbufferDistance,
+                       base::Unretained(this)));
+      range_for_next_append_ = ranges_.end();
+    } else {
+      bytes_to_free -= bytes_deleted;
+      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();
+    }
   }
+
+  // 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
+    // are ultimately deleted. Merging is necessary if there were no buffers
+    // (or very few buffers) deleted after creating |new_range_for_append|.
+    if (range_for_next_append_ != ranges_.begin()) {
+      RangeList::iterator range_before_next = range_for_next_append_;
+      --range_before_next;
+      MergeWithAdjacentRangeIfNecessary(range_before_next);
+    }
+    MergeWithAdjacentRangeIfNecessary(range_for_next_append_);
+  }
+  return bytes_freed;
 }
 
 void SourceBufferStream::InsertIntoExistingRange(
@@ -794,6 +849,9 @@ void SourceBufferStream::MergeWithAdjacentRangeIfNecessary(
     if (transfer_current_position)
       SetSelectedRange(range_with_new_buffers);
 
+    if (next_range_itr == range_for_next_append_)
+      range_for_next_append_ = range_with_new_buffers_itr;
+
     delete *next_range_itr;
     ranges_.erase(next_range_itr);
   }
@@ -1226,60 +1284,40 @@ bool SourceBufferRange::TruncateAt(
   return TruncateAt(starting_point, removed_buffers);
 }
 
-int SourceBufferRange::FreeFromStart(int bytes) {
-  KeyframeMap::iterator deletion_limit = keyframe_map_.end();
-  if (HasNextBufferPosition()) {
-    base::TimeDelta next_timestamp = GetNextTimestamp();
-    if (next_timestamp != kNoTimestamp()) {
-      deletion_limit = GetFirstKeyframeBefore(next_timestamp);
-    } else {
-      // If |next_timestamp| is kNoTimestamp(), that means that the next buffer
-      // hasn't been buffered yet, so just save the keyframe before the end.
-      --deletion_limit;
-    }
-  }
+int SourceBufferRange::DeleteGOPFromFront(BufferQueue* deleted_buffers) {
+  DCHECK(!FirstGOPContainsNextBufferPosition());
+  DCHECK(deleted_buffers);
 
   int buffers_deleted = 0;
   int total_bytes_deleted = 0;
 
-  while (total_bytes_deleted < bytes) {
-    KeyframeMap::iterator front = keyframe_map_.begin();
-    if (front == deletion_limit)
-      break;
-    DCHECK(front != keyframe_map_.end());
-
-    // If we haven't reached |deletion_limit|, we begin by deleting the
-    // keyframe at the start of |keyframe_map_|.
-    keyframe_map_.erase(front);
-    front = keyframe_map_.begin();
-
-    // Now we need to delete all the buffers that depend on the keyframe we've
-    // just deleted. Determine the index in |buffers_| at which we should stop
-    // deleting.
-    int end_index = buffers_.size();
-    if (front != keyframe_map_.end()) {
-      // The indexes in |keyframe_map_| will be out of date after the first GOP
-      // is deleted, so adjust |front->second| by the |buffers_deleted| to get
-      // the proper index value.
-      end_index = front->second - buffers_deleted;
-    }
+  KeyframeMap::iterator front = keyframe_map_.begin();
+  DCHECK(front != keyframe_map_.end());
 
-    // Delete buffers from the beginning of the buffered range up until (but not
-    // including) the next keyframe.
-    for (int i = 0; i < end_index; i++) {
-      int bytes_deleted = buffers_.front()->GetDataSize();
-      size_in_bytes_ -= bytes_deleted;
-      total_bytes_deleted += bytes_deleted;
-      buffers_.pop_front();
-      ++buffers_deleted;
-    }
+  // Delete the keyframe at the start of |keyframe_map_|.
+  keyframe_map_.erase(front);
+
+  // Now we need to delete all the buffers that depend on the keyframe we've
+  // just deleted.
+  int end_index = keyframe_map_.size() > 0 ?
+      keyframe_map_.begin()->second : buffers_.size();
+
+  // Delete buffers from the beginning of the buffered range up until (but not
+  // including) the next keyframe.
+  for (int i = 0; i < end_index; i++) {
+    int bytes_deleted = buffers_.front()->GetDataSize();
+    size_in_bytes_ -= bytes_deleted;
+    total_bytes_deleted += bytes_deleted;
+    deleted_buffers->push_back(buffers_.front());
+    buffers_.pop_front();
+    ++buffers_deleted;
   }
 
   // Update indices to account for the deleted buffers.
   for (KeyframeMap::iterator itr = keyframe_map_.begin();
        itr != keyframe_map_.end(); ++itr) {
     itr->second -= buffers_deleted;
-    DCHECK_GE(itr->second, 0u);
+    DCHECK_GE(itr->second, 0);
   }
   if (next_buffer_index_ > -1) {
     next_buffer_index_ -= buffers_deleted;
@@ -1294,36 +1332,61 @@ int SourceBufferRange::FreeFromStart(int bytes) {
   return total_bytes_deleted;
 }
 
-int SourceBufferRange::FreeFromEnd(int bytes) {
-  // Don't delete anything if we're stalled waiting for more data.
-  if (HasNextBufferPosition() && !HasNextBuffer())
-    return 0;
+int SourceBufferRange::DeleteGOPFromBack(BufferQueue* deleted_buffers) {
+  DCHECK(!LastGOPContainsNextBufferPosition());
+  DCHECK(deleted_buffers);
+
+  // Remove the last GOP's keyframe from the |keyframe_map_|.
+  KeyframeMap::iterator back = keyframe_map_.end();
+  DCHECK_GT(keyframe_map_.size(), 0u);
+  --back;
 
-  // Delete until the current buffer or until we reach the beginning of the
-  // range.
-  int deletion_limit = next_buffer_index_;
-  DCHECK(HasNextBufferPosition() || next_buffer_index_ == -1);
+  // The index of the first buffer in the last GOP is equal to the new size of
+  // |buffers_| after that GOP is deleted.
+  size_t goal_size = back->second;
+  keyframe_map_.erase(back);
 
   int total_bytes_deleted = 0;
-  while (total_bytes_deleted < bytes &&
-         static_cast<int>(buffers_.size() - 1) > deletion_limit) {
+  while (buffers_.size() != goal_size) {
     int bytes_deleted = buffers_.back()->GetDataSize();
     size_in_bytes_ -= bytes_deleted;
     total_bytes_deleted += bytes_deleted;
-
-    // Delete the corresponding |keyframe_map_| entry if we're about to delete a
-    // keyframe buffer.
-    if (buffers_.back()->IsKeyframe()) {
-      DCHECK(keyframe_map_.rbegin()->first ==
-             buffers_.back()->GetDecodeTimestamp());
-      keyframe_map_.erase(buffers_.back()->GetDecodeTimestamp());
-    }
-
+    // We're removing buffers from the back, so push each removed buffer to the
+    // front of |deleted_buffers| so that |deleted_buffers| are in nondecreasing
+    // order.
+    deleted_buffers->push_front(buffers_.back());
     buffers_.pop_back();
   }
+
   return total_bytes_deleted;
 }
 
+bool SourceBufferRange::FirstGOPContainsNextBufferPosition() const {
+  if (!HasNextBufferPosition())
+    return false;
+
+  // If there is only one GOP, it must contain the next buffer position.
+  if (keyframe_map_.size() == 1u)
+    return true;
+
+  KeyframeMap::const_iterator second_gop = keyframe_map_.begin();
+  ++second_gop;
+  return !waiting_for_keyframe_ && next_buffer_index_ < second_gop->second;
+}
+
+bool SourceBufferRange::LastGOPContainsNextBufferPosition() const {
+  if (!HasNextBufferPosition())
+    return false;
+
+  // If there is only one GOP, it must contain the next buffer position.
+  if (keyframe_map_.size() == 1u)
+    return true;
+
+  KeyframeMap::const_iterator last_gop = keyframe_map_.end();
+  --last_gop;
+  return waiting_for_keyframe_ || last_gop->second <= next_buffer_index_;
+}
+
 void SourceBufferRange::FreeBufferRange(
     const BufferQueue::iterator& starting_point,
     const BufferQueue::iterator& ending_point) {
diff --git a/media/filters/source_buffer_stream.h b/media/filters/source_buffer_stream.h
index 1c3514b..a3757cb 100644
--- a/media/filters/source_buffer_stream.h
+++ b/media/filters/source_buffer_stream.h
@@ -112,6 +112,12 @@ class MEDIA_EXPORT SourceBufferStream {
   // Frees up space if the SourceBufferStream is taking up too much memory.
   void GarbageCollectIfNeeded();
 
+  // Attempts to delete approximately |total_bytes_to_free| amount of data
+  // |ranges_|, starting at the front of |ranges_| and moving linearly forward
+  // through the buffers. Deletes starting from the back if |reverse_direction|
+  // is true. Returns the number of bytes freed.
+  int FreeBuffers(int total_bytes_to_free, bool reverse_direction);
+
   // Appends |new_buffers| into |range_for_new_buffers_itr|, handling start and
   // end overlaps if necessary.
   // |deleted_next_buffer| is an output parameter that is true if the next
diff --git a/media/filters/source_buffer_stream_unittest.cc b/media/filters/source_buffer_stream_unittest.cc
index e46a703..dd272d6 100644
--- a/media/filters/source_buffer_stream_unittest.cc
+++ b/media/filters/source_buffer_stream_unittest.cc
@@ -44,7 +44,7 @@ class SourceBufferStreamTest : public testing::Test {
 
   void NewSegmentAppend(int starting_position, int number_of_buffers) {
     AppendBuffers(starting_position, number_of_buffers, true,
-                  base::TimeDelta(), true, NULL, 0);
+                  base::TimeDelta(), true, &kDataA, kDataSize);
   }
 
   void NewSegmentAppend(int starting_position, int number_of_buffers,
@@ -57,18 +57,18 @@ class SourceBufferStreamTest : public testing::Test {
       int starting_position, int number_of_buffers,
       base::TimeDelta first_buffer_offset) {
     AppendBuffers(starting_position, number_of_buffers, true,
-                  first_buffer_offset, true, NULL, 0);
+                  first_buffer_offset, true, &kDataA, kDataSize);
   }
 
   void NewSegmentAppend_ExpectFailure(
       int starting_position, int number_of_buffers) {
     AppendBuffers(starting_position, number_of_buffers, true,
-                  base::TimeDelta(), false, NULL, 0);
+                  base::TimeDelta(), false, &kDataA, kDataSize);
   }
 
   void AppendBuffers(int starting_position, int number_of_buffers) {
     AppendBuffers(starting_position, number_of_buffers, false,
-                  base::TimeDelta(), true, NULL, 0);
+                  base::TimeDelta(), true, &kDataA, kDataSize);
   }
 
   void AppendBuffers(int starting_position, int number_of_buffers,
@@ -77,12 +77,20 @@ class SourceBufferStreamTest : public testing::Test {
                   base::TimeDelta(), true, data, kDataSize);
   }
 
+  void NewSegmentAppend(const std::string& buffers_to_append) {
+    AppendBuffers(buffers_to_append, true, false);
+  }
+
+  void AppendBuffers(const std::string& buffers_to_append) {
+    AppendBuffers(buffers_to_append, false, false);
+  }
+
   void NewSegmentAppendOneByOne(const std::string& buffers_to_append) {
-    AppendBuffersOneByOne(buffers_to_append, true);
+    AppendBuffers(buffers_to_append, true, true);
   }
 
   void AppendBuffersOneByOne(const std::string& buffers_to_append) {
-    AppendBuffersOneByOne(buffers_to_append, false);
+    AppendBuffers(buffers_to_append, false, true);
   }
 
   void Seek(int position) {
@@ -263,13 +271,14 @@ class SourceBufferStreamTest : public testing::Test {
       EXPECT_EQ(expect_success, stream_->Append(queue));
   }
 
-  void AppendBuffersOneByOne(const std::string& buffers_to_append,
-                             bool start_new_segment) {
+  void AppendBuffers(const std::string& buffers_to_append,
+                     bool start_new_segment, bool one_by_one) {
     std::vector<std::string> timestamps;
     base::SplitString(buffers_to_append, ' ', &timestamps);
 
     CHECK_GT(timestamps.size(), 0u);
 
+    SourceBufferStream::BufferQueue buffers;
     for (size_t i = 0; i < timestamps.size(); i++) {
       bool is_keyframe = false;
       if (EndsWith(timestamps[i], "K", true)) {
@@ -290,9 +299,19 @@ class SourceBufferStreamTest : public testing::Test {
       if (i == 0u && start_new_segment)
         stream_->OnNewMediaSegment(timestamp);
 
-      SourceBufferStream::BufferQueue queue;
-      queue.push_back(buffer);
-      EXPECT_TRUE(stream_->Append(queue));
+      buffers.push_back(buffer);
+    }
+
+    if (!one_by_one) {
+      EXPECT_TRUE(stream_->Append(buffers));
+      return;
+    }
+
+    // Append each buffer one by one.
+    for (size_t i = 0; i < buffers.size(); i++) {
+      SourceBufferStream::BufferQueue wrapper;
+      wrapper.push_back(buffers[i]);
+      EXPECT_TRUE(stream_->Append(wrapper));
     }
   }
 
@@ -1932,8 +1951,8 @@ TEST_F(SourceBufferStreamTest, GarbageCollection_DeleteBack) {
   // Append 20 buffers at positions 0 through 19.
   NewSegmentAppend(0, 20, &kDataA);
 
-  // Should leave the first 5 buffers from 0 to 4.
-  CheckExpectedRanges("{ [0,4) }");
+  // Should leave the first 5 buffers from 0 to 4 and the last GOP appended.
+  CheckExpectedRanges("{ [0,4) [15,19) }");
   CheckExpectedBuffers(0, 4, &kDataA);
 }
 
@@ -1944,72 +1963,67 @@ TEST_F(SourceBufferStreamTest, GarbageCollection_DeleteFrontAndBack) {
   // Seek to position 15.
   Seek(15);
 
-  // Append 20 buffers at positions 0 through 19.
-  NewSegmentAppend(0, 20, &kDataA);
+  // Append 40 buffers at positions 0 through 39.
+  NewSegmentAppend(0, 40, &kDataA);
 
-  // Should leave 3 buffers, starting at the seek position.
-  CheckExpectedRanges("{ [15,17) }");
-  CheckExpectedBuffers(15, 17, &kDataA);
-  CheckNoNextBuffer();
-}
-
-TEST_F(SourceBufferStreamTest, GarbageCollection_DeleteFrontAndBack2) {
-  // Set memory limit to 1 buffer.
-  SetMemoryLimit(1);
-
-  // Seek to position 15.
-  Seek(15);
-
-  // Append 20 buffers at positions 0 through 19.
-  NewSegmentAppend(0, 20, &kDataA);
-
-  // Should leave just the buffer at position 15.
-  CheckExpectedRanges("{ [15,15) }");
-  CheckExpectedBuffers(15, 15, &kDataA);
+  // Should leave the GOP containing the seek position and the last GOP
+  // appended.
+  CheckExpectedRanges("{ [15,19) [35,39) }");
+  CheckExpectedBuffers(15, 19, &kDataA);
   CheckNoNextBuffer();
 }
 
 TEST_F(SourceBufferStreamTest, GarbageCollection_DeleteSeveralRanges) {
   // Append 5 buffers at positions 0 through 4.
-  NewSegmentAppend(0, 5, &kDataA);
+  NewSegmentAppend(0, 5);
 
   // Append 5 buffers at positions 10 through 14.
-  NewSegmentAppend(10, 5, &kDataA);
+  NewSegmentAppend(10, 5);
 
   // Append 5 buffers at positions 20 through 24.
-  NewSegmentAppend(20, 5, &kDataA);
+  NewSegmentAppend(20, 5);
 
   // Append 5 buffers at positions 30 through 34.
-  NewSegmentAppend(30, 5, &kDataA);
+  NewSegmentAppend(30, 5);
 
   CheckExpectedRanges("{ [0,4) [10,14) [20,24) [30,34) }");
 
   // Seek to position 21.
   Seek(20);
-  CheckExpectedBuffers(20, 20, &kDataA);
+  CheckExpectedBuffers(20, 20);
 
   // Set memory limit to 1 buffer.
   SetMemoryLimit(1);
 
   // Append 5 buffers at positions 40 through 44. This will trigger GC.
-  NewSegmentAppend(40, 5, &kDataA);
+  NewSegmentAppend(40, 5);
 
-  // Should delete everything except current buffer and the keyframe before it.
-  CheckExpectedRanges("{ [20,21) }");
-  CheckExpectedBuffers(21, 21, &kDataA);
+  // Should delete everything except the GOP containing the current buffer and
+  // the last GOP appended.
+  CheckExpectedRanges("{ [20,24) [40,44) }");
+  CheckExpectedBuffers(21, 24);
   CheckNoNextBuffer();
 
+  // Continue appending into the last range to make sure it didn't break.
+  AppendBuffers(45, 10);
+  // Should only save last GOP appended.
+  CheckExpectedRanges("{ [20,24) [50,54) }");
+
   // Make sure appending before and after the ranges didn't somehow break.
   SetMemoryLimit(100);
-  NewSegmentAppend(0, 10, &kDataA);
-  CheckExpectedRanges("{ [0,9) [20,21) }");
+  NewSegmentAppend(0, 10);
+  CheckExpectedRanges("{ [0,9) [20,24) [50,54) }");
   Seek(0);
-  CheckExpectedBuffers(0, 9, &kDataA);
+  CheckExpectedBuffers(0, 9);
 
-  NewSegmentAppend(30, 10, &kDataA);
-  CheckExpectedRanges("{ [0,9) [20,21) [30,39) }");
-  Seek(30);
-  CheckExpectedBuffers(30, 39, &kDataA);
+  NewSegmentAppend(90, 10);
+  CheckExpectedRanges("{ [0,9) [20,24) [50,54) [90,99) }");
+  Seek(50);
+  CheckExpectedBuffers(50, 54);
+  CheckNoNextBuffer();
+  Seek(90);
+  CheckExpectedBuffers(90, 99);
+  CheckNoNextBuffer();
 }
 
 TEST_F(SourceBufferStreamTest, GarbageCollection_NoSeek) {
@@ -2063,8 +2077,8 @@ TEST_F(SourceBufferStreamTest, GarbageCollection_PendingSeek) {
 }
 
 TEST_F(SourceBufferStreamTest, GarbageCollection_NeedsMoreData) {
-  // Set memory limit to 10 buffers.
-  SetMemoryLimit(10);
+  // Set memory limit to 15 buffers.
+  SetMemoryLimit(15);
 
   // Append 10 buffers at positions 0 through 9.
   NewSegmentAppend(0, 10, &kDataA);
@@ -2078,13 +2092,14 @@ TEST_F(SourceBufferStreamTest, GarbageCollection_NeedsMoreData) {
   NewSegmentAppend(15, 20, &kDataA);
 
   // GC should have saved the keyframe before the current seek position and the
-  // data closest to the current seek position.
-  CheckExpectedRanges("{ [5,9) [15,19) }");
+  // data closest to the current seek position. It will also save the last GOP
+  // appended.
+  CheckExpectedRanges("{ [5,9) [15,19) [30,34) }");
 
   // Now fulfill the seek at position 10. This will make GC delete the data
   // before position 10 to keep it within cap.
   NewSegmentAppend(10, 5, &kDataA);
-  CheckExpectedRanges("{ [10,19) }");
+  CheckExpectedRanges("{ [10,19) [30,34) }");
   CheckExpectedBuffers(10, 19, &kDataA);
 }
 
@@ -2095,27 +2110,21 @@ TEST_F(SourceBufferStreamTest, GarbageCollection_TrackBuffer) {
   // Seek to position 15.
   Seek(15);
 
-  // Append 20 buffers at positions 0 through 19.
-  NewSegmentAppend(0, 20, &kDataA);
+  // Append 18 buffers at positions 0 through 17.
+  NewSegmentAppend(0, 18, &kDataA);
 
-  // Should leave 3 buffers starting at 15.
+  // Should leave GOP containing seek position.
   CheckExpectedRanges("{ [15,17) }");
 
   // Seek ahead to position 16.
   CheckExpectedBuffers(15, 15, &kDataA);
 
-  // Add 5 buffers from position 20 to 24.
-  NewSegmentAppend(20, 5, &kDataA);
-
-  // The newly added buffers should be garbage collected immediately.
-  CheckExpectedRanges("{ [15,17) }");
-
   // Completely overlap the existing buffers.
   NewSegmentAppend(0, 20, &kDataB);
 
   // Because buffers 16 and 17 are not keyframes, they are moved to the track
   // buffer upon overlap. The source buffer (i.e. not the track buffer) is now
-  // waiting for the next keyframe, which is why buffers 18 and 19 are not GC'd.
+  // waiting for the next keyframe.
   CheckExpectedRanges("{ [15,19) }");
   CheckExpectedBuffers(16, 17, &kDataA);
   CheckNoNextBuffer();
@@ -2123,10 +2132,186 @@ TEST_F(SourceBufferStreamTest, GarbageCollection_TrackBuffer) {
   // Now add a keyframe at position 20.
   AppendBuffers(20, 5, &kDataB);
 
-  // Should garbage collect such that there are 3 frames remaining, starting at
+  // Should garbage collect such that there are 5 frames remaining, starting at
   // the keyframe.
-  CheckExpectedRanges("{ [20,22) }");
-  CheckExpectedBuffers(20, 22, &kDataB);
+  CheckExpectedRanges("{ [20,24) }");
+  CheckExpectedBuffers(20, 24, &kDataB);
+  CheckNoNextBuffer();
+}
+
+// Test saving the last GOP appended when this GOP is the only GOP in its range.
+TEST_F(SourceBufferStreamTest, GarbageCollection_SaveAppendGOP) {
+  // Set memory limit to 3 and make sure the 4-byte GOP is not garbage
+  // collected.
+  SetMemoryLimit(3);
+  NewSegmentAppend("0K 30 60 90");
+  CheckExpectedRangesByTimestamp("{ [0,120) }");
+
+  // Make sure you can continue appending data to this GOP; again, GC should not
+  // wipe out anything.
+  AppendBuffers("120");
+  CheckExpectedRangesByTimestamp("{ [0,150) }");
+
+  // Set memory limit to 100 and append a 2nd range after this without
+  // triggering GC.
+  SetMemoryLimit(100);
+  NewSegmentAppend("200K 230 260 290K 320 350");
+  CheckExpectedRangesByTimestamp("{ [0,150) [200,380) }");
+
+  // Seek to 290ms.
+  SeekToTimestamp(base::TimeDelta::FromMilliseconds(290));
+
+  // Now set memory limit to 3 and append a GOP in a separate range after the
+  // selected range. Because it is after 290ms, this tests that the GOP is saved
+  // when deleting from the back.
+  SetMemoryLimit(3);
+  NewSegmentAppend("500K 530 560 590");
+
+  // Should save GOP with 290ms and last GOP appended.
+  CheckExpectedRangesByTimestamp("{ [290,380) [500,620) }");
+
+  // Continue appending to this GOP after GC.
+  AppendBuffers("620");
+  CheckExpectedRangesByTimestamp("{ [290,380) [500,650) }");
+}
+
+// Test saving the last GOP appended when this GOP is in the middle of a
+// non-selected range.
+TEST_F(SourceBufferStreamTest, GarbageCollection_SaveAppendGOP_Middle) {
+  // Append 3 GOPs starting at 0ms, 30ms apart.
+  NewSegmentAppend("0K 30 60 90K 120 150 180K 210 240");
+  CheckExpectedRangesByTimestamp("{ [0,270) }");
+
+  // Now set the memory limit to 1 and overlap the middle of the range with a
+  // new GOP.
+  SetMemoryLimit(1);
+  NewSegmentAppend("80K 110 140");
+
+  // This whole GOP should be saved, and should be able to continue appending
+  // data to it.
+  CheckExpectedRangesByTimestamp("{ [80,170) }");
+  AppendBuffers("170");
+  CheckExpectedRangesByTimestamp("{ [80,200) }");
+
+  // Set memory limit to 100 and append a 2nd range after this without
+  // triggering GC.
+  SetMemoryLimit(100);
+  NewSegmentAppend("400K 430 460 490K 520 550 580K 610 640");
+  CheckExpectedRangesByTimestamp("{ [80,200) [400,670) }");
+
+  // Seek to 80ms to make the first range the selected range.
+  SeekToTimestamp(base::TimeDelta::FromMilliseconds(80));
+
+  // Now set memory limit to 3 and append a GOP in the middle of the second
+  // range. Because it is after the selected range, this tests that the GOP is
+  // saved when deleting from the back.
+  SetMemoryLimit(3);
+  NewSegmentAppend("500K 530 560 590");
+
+  // Should save the GOP containing the seek point and GOP that was last
+  // appended.
+  CheckExpectedRangesByTimestamp("{ [80,200) [500,620) }");
+
+  // Continue appending to this GOP after GC.
+  AppendBuffers("620");
+  CheckExpectedRangesByTimestamp("{ [80,200) [500,650) }");
+}
+
+// Test saving the last GOP appended when the GOP containing the next buffer is
+// adjacent to the last GOP appended.
+TEST_F(SourceBufferStreamTest, GarbageCollection_SaveAppendGOP_Selected1) {
+  // Append 3 GOPs at 0ms, 90ms, and 180ms.
+  NewSegmentAppend("0K 30 60 90K 120 150 180K 210 240");
+  CheckExpectedRangesByTimestamp("{ [0,270) }");
+
+  // Seek to the GOP at 90ms.
+  SeekToTimestamp(base::TimeDelta::FromMilliseconds(90));
+
+  // Set the memory limit to 1, then overlap the GOP at 0.
+  SetMemoryLimit(1);
+  NewSegmentAppend("0K 30 60");
+
+  // Should save the GOP at 0ms and 90ms.
+  CheckExpectedRangesByTimestamp("{ [0,180) }");
+
+  // Seek to 0 and check all buffers.
+  SeekToTimestamp(base::TimeDelta::FromMilliseconds(0));
+  CheckExpectedBuffers("0K 30 60 90K 120 150");
+  CheckNoNextBuffer();
+
+  // Now seek back to 90ms and append a GOP at 180ms.
+  SeekToTimestamp(base::TimeDelta::FromMilliseconds(90));
+  NewSegmentAppend("180K 210 240");
+
+  // Should save the GOP at 90ms and the GOP at 180ms.
+  CheckExpectedRangesByTimestamp("{ [90,270) }");
+  CheckExpectedBuffers("90K 120 150 180K 210 240");
+  CheckNoNextBuffer();
+}
+
+// Test saving the last GOP appended when it is at the beginning or end of the
+// selected range. This tests when the last GOP appended is before or after the
+// GOP containing the next buffer, but not directly adjacent to this GOP.
+TEST_F(SourceBufferStreamTest, GarbageCollection_SaveAppendGOP_Selected2) {
+  // Append 4 GOPs starting at positions 0ms, 90ms, 180ms, 270ms.
+  NewSegmentAppend("0K 30 60 90K 120 150 180K 210 240 270K 300 330");
+  CheckExpectedRangesByTimestamp("{ [0,360) }");
+
+  // Seek to the last GOP at 270ms.
+  SeekToTimestamp(base::TimeDelta::FromMilliseconds(270));
+
+  // Set the memory limit to 1, then overlap the GOP at 90ms.
+  SetMemoryLimit(1);
+  NewSegmentAppend("90K 120 150");
+
+  // Should save the GOP at 90ms and the GOP at 270ms.
+  CheckExpectedRangesByTimestamp("{ [90,180) [270,360) }");
+
+  // Set memory limit to 100 and add 3 GOPs to the end of the selected range
+  // at 360ms, 450ms, and 540ms.
+  SetMemoryLimit(100);
+  NewSegmentAppend("360K 390 420 450K 480 510 540K 570 600");
+  CheckExpectedRangesByTimestamp("{ [90,180) [270,630) }");
+
+  // Constrain the memory limit again and overlap the GOP at 450ms to test
+  // deleting from the back.
+  SetMemoryLimit(1);
+  NewSegmentAppend("450K 480 510");
+
+  // Should save GOP at 270ms and the GOP at 450ms.
+  CheckExpectedRangesByTimestamp("{ [270,360) [450,540) }");
+}
+
+// Test saving the last GOP appended when it is the same as the GOP containing
+// the next buffer.
+TEST_F(SourceBufferStreamTest, GarbageCollection_SaveAppendGOP_Selected3) {
+  // Seek to start of stream.
+  SeekToTimestamp(base::TimeDelta::FromMilliseconds(0));
+
+  // Append 3 GOPs starting at 0ms, 90ms, 180ms.
+  NewSegmentAppend("0K 30 60 90K 120 150 180K 210 240");
+  CheckExpectedRangesByTimestamp("{ [0,270) }");
+
+  // Set the memory limit to 1 then begin appending the start of a GOP starting
+  // at 0ms.
+  SetMemoryLimit(1);
+  NewSegmentAppend("0K 30");
+
+  // Should save the newly appended GOP, which is also the next GOP that will be
+  // returned from the seek request.
+  CheckExpectedRangesByTimestamp("{ [0,60) }");
+
+  // Check the buffers in the range.
+  CheckExpectedBuffers("0K 30");
+  CheckNoNextBuffer();
+
+  // Continue appending to this buffer.
+  AppendBuffers("60 90");
+
+  // Should still save the rest of this GOP and should be able to fulfill the
+  // read.
+  CheckExpectedRangesByTimestamp("{ [0,120) }");
+  CheckExpectedBuffers("60 90");
   CheckNoNextBuffer();
 }