Implement simple garbage collection in SourceBufferStream

Start freeing buffers after Append() calls if total size of the stream goes
above a hard cap. This caps per-stream, not per-video tag.

BUG=125070

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

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

3 files changed, 509 insertions, 13 deletions

diff --git a/media/filters/source_buffer_stream.cc b/media/filters/source_buffer_stream.cc
index c2be6a7..c768423 100644
--- a/media/filters/source_buffer_stream.cc
+++ b/media/filters/source_buffer_stream.cc
@@ -86,6 +86,15 @@ 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);
+
+  // 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);
+
   // Updates |out_buffer| with the next buffer in presentation order. Seek()
   // must be called before calls to GetNextBuffer(), and buffers are returned
   // in order from the last call to Seek(). Returns true if |out_buffer| is
@@ -144,6 +153,8 @@ class SourceBufferRange {
       const scoped_refptr<media::StreamParserBuffer>& buffer,
       base::TimeDelta timestamp) const;
 
+  int size_in_bytes() const { return size_in_bytes_; }
+
  private:
   typedef std::map<base::TimeDelta, size_t> KeyframeMap;
 
@@ -158,11 +169,20 @@ class SourceBufferRange {
   KeyframeMap::iterator GetFirstKeyframeAt(
       base::TimeDelta timestamp, bool skip_given_timestamp);
 
+  // Returns an iterator in |keyframe_map_| pointing to the first keyframe
+  // before or at |timestamp|.
+  KeyframeMap::iterator GetFirstKeyframeBefore(base::TimeDelta timestamp);
+
   // Helper method to delete buffers in |buffers_| starting at
   // |starting_point|, an iterator in |buffers_|.
   bool TruncateAt(const BufferQueue::iterator& starting_point,
                   BufferQueue* deleted_buffers);
 
+  // Frees the buffers in |buffers_| from [|start_point|,|ending_point|) and
+  // updates the |size_in_bytes_| accordingly. Does not update |keyframe_map_|.
+  void FreeBufferRange(const BufferQueue::iterator& starting_point,
+                       const BufferQueue::iterator& ending_point);
+
   // Returns the distance in time estimating how far from the beginning or end
   // of this range a buffer can be to considered in the range.
   base::TimeDelta GetFudgeRoom() const;
@@ -201,6 +221,9 @@ class SourceBufferRange {
   // Called to get the largest interbuffer distance seen so far in the stream.
   InterbufferDistanceCB interbuffer_distance_cb_;
 
+  // Stores the amount of memory taken up by the data in |buffers_|.
+  int size_in_bytes_;
+
   DISALLOW_COPY_AND_ASSIGN(SourceBufferRange);
 };
 
@@ -236,6 +259,11 @@ static int kDefaultBufferDurationInMs = 125;
 static base::TimeDelta kSeekToStartFudgeRoom() {
   return base::TimeDelta::FromMilliseconds(1000);
 }
+// The maximum amount of data in bytes the stream will keep in memory.
+// 12MB: approximately 5 minutes of 320Kbps content.
+// 150MB: approximately 5 minutes of 4Mbps content.
+static int kDefaultAudioMemoryLimit = 12 * 1024 * 1024;
+static int kDefaultVideoMemoryLimit = 150 * 1024 * 1024;
 
 namespace media {
 
@@ -252,7 +280,8 @@ SourceBufferStream::SourceBufferStream(const AudioDecoderConfig& audio_config)
       range_for_next_append_(ranges_.end()),
       new_media_segment_(false),
       last_buffer_timestamp_(kNoTimestamp()),
-      max_interbuffer_distance_(kNoTimestamp()) {
+      max_interbuffer_distance_(kNoTimestamp()),
+      memory_limit_(kDefaultAudioMemoryLimit) {
   audio_configs_[0] = new AudioDecoderConfig();
   audio_configs_[0]->CopyFrom(audio_config);
 }
@@ -270,7 +299,8 @@ SourceBufferStream::SourceBufferStream(const VideoDecoderConfig& video_config)
       range_for_next_append_(ranges_.end()),
       new_media_segment_(false),
       last_buffer_timestamp_(kNoTimestamp()),
-      max_interbuffer_distance_(kNoTimestamp()) {
+      max_interbuffer_distance_(kNoTimestamp()),
+      memory_limit_(kDefaultVideoMemoryLimit) {
   video_configs_[0] = new VideoDecoderConfig();
   video_configs_[0]->CopyFrom(video_config);
 }
@@ -389,6 +419,8 @@ bool SourceBufferStream::Append(
     }
   }
 
+  GarbageCollectIfNeeded();
+
   DCHECK(IsRangeListSorted(ranges_));
   DCHECK(OnlySelectedRangeIsSeeked());
   return true;
@@ -460,6 +492,49 @@ void SourceBufferStream::SetConfigIds(const BufferQueue& buffers) {
   }
 }
 
+void SourceBufferStream::GarbageCollectIfNeeded() {
+  // Compute size of |ranges_|.
+  int 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;
+
+  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);
+
+    // 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;
+
+    DCHECK_NE(current_range, selected_range_);
+    delete current_range;
+    ranges_.pop_front();
+  }
+
+  // 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;
+
+    DCHECK_NE(current_range, selected_range_);
+    delete current_range;
+    ranges_.pop_back();
+  }
+}
+
 void SourceBufferStream::InsertIntoExistingRange(
     const RangeList::iterator& range_for_new_buffers_itr,
     const BufferQueue& new_buffers,
@@ -876,7 +951,8 @@ SourceBufferRange::SourceBufferRange(
       waiting_for_keyframe_(false),
       next_keyframe_timestamp_(kNoTimestamp()),
       media_segment_start_time_(media_segment_start_time),
-      interbuffer_distance_cb_(interbuffer_distance_cb) {
+      interbuffer_distance_cb_(interbuffer_distance_cb),
+      size_in_bytes_(0) {
   DCHECK(!new_buffers.empty());
   DCHECK(new_buffers.front()->IsKeyframe());
   DCHECK(!interbuffer_distance_cb.is_null());
@@ -888,6 +964,8 @@ void SourceBufferRange::AppendBuffersToEnd(const BufferQueue& new_buffers) {
        itr != new_buffers.end(); ++itr) {
     DCHECK((*itr)->GetDecodeTimestamp() != kNoTimestamp());
     buffers_.push_back(*itr);
+    size_in_bytes_ += (*itr)->GetDataSize();
+
     if ((*itr)->IsKeyframe()) {
       keyframe_map_.insert(
           std::make_pair((*itr)->GetDecodeTimestamp(), buffers_.size() - 1));
@@ -909,14 +987,7 @@ void SourceBufferRange::Seek(base::TimeDelta timestamp) {
   next_keyframe_timestamp_ = base::TimeDelta();
   waiting_for_keyframe_ = false;
 
-  KeyframeMap::iterator result = keyframe_map_.lower_bound(timestamp);
-  // lower_bound() returns the first element >= |timestamp|, so we want the
-  // previous element if it did not return the element exactly equal to
-  // |timestamp|.
-  if (result != keyframe_map_.begin() &&
-      (result == keyframe_map_.end() || result->first != timestamp)) {
-    result--;
-  }
+  KeyframeMap::iterator result = GetFirstKeyframeBefore(timestamp);
   next_buffer_index_ = result->second;
   DCHECK_LT(next_buffer_index_, static_cast<int>(buffers_.size()));
 }
@@ -969,7 +1040,7 @@ SourceBufferRange* SourceBufferRange::SplitRange(base::TimeDelta timestamp) {
   BufferQueue::iterator starting_point = buffers_.begin() + keyframe_index;
   BufferQueue removed_buffers(starting_point, buffers_.end());
   keyframe_map_.erase(new_beginning_keyframe, keyframe_map_.end());
-  buffers_.erase(starting_point, buffers_.end());
+  FreeBufferRange(starting_point, buffers_.end());
 
   // Create a new range with |removed_buffers|.
   SourceBufferRange* split_range =
@@ -1005,6 +1076,19 @@ SourceBufferRange::GetFirstKeyframeAt(base::TimeDelta timestamp,
   return result;
 }
 
+SourceBufferRange::KeyframeMap::iterator
+SourceBufferRange::GetFirstKeyframeBefore(base::TimeDelta timestamp) {
+  KeyframeMap::iterator result = keyframe_map_.lower_bound(timestamp);
+  // lower_bound() returns the first element >= |timestamp|, so we want the
+  // previous element if it did not return the element exactly equal to
+  // |timestamp|.
+  if (result != keyframe_map_.begin() &&
+      (result == keyframe_map_.end() || result->first != timestamp)) {
+    --result;
+  }
+  return result;
+}
+
 bool SourceBufferRange::DeleteAll(BufferQueue* removed_buffers) {
   return TruncateAt(buffers_.begin(), removed_buffers);
 }
@@ -1019,6 +1103,115 @@ 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 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;
+    }
+
+    // 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;
+    }
+  }
+
+  // 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);
+  }
+  if (next_buffer_index_ > -1) {
+    next_buffer_index_ -= buffers_deleted;
+    DCHECK_GE(next_buffer_index_, 0);
+  }
+
+  // Invalidate media segment start time if we've deleted the first buffer of
+  // the range.
+  if (buffers_deleted > 0)
+    media_segment_start_time_ = kNoTimestamp();
+
+  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;
+
+  // 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);
+
+  int total_bytes_deleted = 0;
+  while (total_bytes_deleted < bytes &&
+         static_cast<int>(buffers_.size() - 1) > deletion_limit) {
+    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());
+    }
+
+    buffers_.pop_back();
+  }
+  return total_bytes_deleted;
+}
+
+void SourceBufferRange::FreeBufferRange(
+    const BufferQueue::iterator& starting_point,
+    const BufferQueue::iterator& ending_point) {
+  for (BufferQueue::iterator itr = starting_point;
+       itr != ending_point; ++itr) {
+    size_in_bytes_ -= (*itr)->GetDataSize();
+    DCHECK_GE(size_in_bytes_, 0);
+  }
+  buffers_.erase(starting_point, ending_point);
+}
+
 bool SourceBufferRange::TruncateAt(
     const BufferQueue::iterator& starting_point, BufferQueue* removed_buffers) {
   DCHECK(removed_buffers);
@@ -1053,7 +1246,7 @@ bool SourceBufferRange::TruncateAt(
   keyframe_map_.erase(starting_point_keyframe, keyframe_map_.end());
 
   // Remove everything from |starting_point| onward.
-  buffers_.erase(starting_point, buffers_.end());
+  FreeBufferRange(starting_point, buffers_.end());
   return removed_next_buffer;
 }
 
diff --git a/media/filters/source_buffer_stream.h b/media/filters/source_buffer_stream.h
index 1c72c23..e67a84d 100644
--- a/media/filters/source_buffer_stream.h
+++ b/media/filters/source_buffer_stream.h
@@ -103,8 +103,14 @@ class MEDIA_EXPORT SourceBufferStream {
   base::TimeDelta GetMaxInterbufferDistance() const;
 
  private:
+  friend class SourceBufferStreamTest;
   typedef std::list<SourceBufferRange*> RangeList;
 
+  void set_memory_limit(int memory_limit) { memory_limit_ = memory_limit; }
+
+  // Frees up space if the SourceBufferStream is taking up too much memory.
+  void GarbageCollectIfNeeded();
+
   // 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
@@ -252,6 +258,9 @@ class MEDIA_EXPORT SourceBufferStream {
   // Stores the largest distance between two adjacent buffers in this stream.
   base::TimeDelta max_interbuffer_distance_;
 
+// The maximum amount of data in bytes the stream will keep in memory.
+  int memory_limit_;
+
   DISALLOW_COPY_AND_ASSIGN(SourceBufferStream);
 };
 
diff --git a/media/filters/source_buffer_stream_unittest.cc b/media/filters/source_buffer_stream_unittest.cc
index 35161c1..4033869 100644
--- a/media/filters/source_buffer_stream_unittest.cc
+++ b/media/filters/source_buffer_stream_unittest.cc
@@ -26,6 +26,10 @@ class SourceBufferStreamTest : public testing::Test {
     stream_->SetStartTime(base::TimeDelta());
   }
 
+  void SetMemoryLimit(int buffers_of_data) {
+    stream_->set_memory_limit(buffers_of_data * kDataSize);
+  }
+
   void SetStreamInfo(int frames_per_second, int keyframes_per_second) {
     frames_per_second_ = frames_per_second;
     keyframes_per_second_ = keyframes_per_second;
@@ -1528,6 +1532,296 @@ TEST_F(SourceBufferStreamTest, PresentationTimestampIndependence) {
   }
 }
 
+TEST_F(SourceBufferStreamTest, GarbageCollection_DeleteFront) {
+  // Set memory limit to 20 buffers.
+  SetMemoryLimit(20);
+
+  // Append 20 buffers at positions 0 through 19.
+  NewSegmentAppend(0, 1, &kDataA);
+  for (int i = 1; i < 20; i++)
+    AppendBuffers(i, 1, &kDataA);
+
+  // None of the buffers should trigger garbage collection, so all data should
+  // be there as expected.
+  CheckExpectedRanges("{ [0,19) }");
+  Seek(0);
+  CheckExpectedBuffers(0, 19, &kDataA);
+
+  // Seek to the middle of the stream.
+  Seek(10);
+
+  // Append 5 buffers to the end of the stream.
+  AppendBuffers(20, 5, &kDataA);
+
+  // GC should have deleted the first 5 buffers.
+  CheckExpectedRanges("{ [5,24) }");
+  CheckExpectedBuffers(10, 24, &kDataA);
+  Seek(5);
+  CheckExpectedBuffers(5, 9, &kDataA);
+}
+
+TEST_F(SourceBufferStreamTest, GarbageCollection_DeleteFrontGOPsAtATime) {
+  // Set memory limit to 20 buffers.
+  SetMemoryLimit(20);
+
+  // Append 20 buffers at positions 0 through 19.
+  NewSegmentAppend(0, 20, &kDataA);
+
+  // Seek to position 10.
+  Seek(10);
+
+  // Add one buffer to put the memory over the cap.
+  AppendBuffers(20, 1, &kDataA);
+
+  // GC should have deleted the first 5 buffers so that the range still begins
+  // with a keyframe.
+  CheckExpectedRanges("{ [5,20) }");
+  CheckExpectedBuffers(10, 20, &kDataA);
+  Seek(5);
+  CheckExpectedBuffers(5, 9, &kDataA);
+}
+
+TEST_F(SourceBufferStreamTest, GarbageCollection_DeleteBack) {
+  // Set memory limit to 5 buffers.
+  SetMemoryLimit(5);
+
+  // Seek to position 0.
+  Seek(0);
+
+  // 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) }");
+  CheckExpectedBuffers(0, 4, &kDataA);
+}
+
+TEST_F(SourceBufferStreamTest, GarbageCollection_DeleteFrontAndBack) {
+  // Set memory limit to 3 buffers.
+  SetMemoryLimit(3);
+
+  // Seek to position 15.
+  Seek(15);
+
+  // Append 20 buffers at positions 0 through 19.
+  NewSegmentAppend(0, 20, &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);
+  CheckNoNextBuffer();
+}
+
+TEST_F(SourceBufferStreamTest, GarbageCollection_DeleteSeveralRanges) {
+  // Append 5 buffers at positions 0 through 4.
+  NewSegmentAppend(0, 5, &kDataA);
+
+  // Append 5 buffers at positions 10 through 14.
+  NewSegmentAppend(10, 5, &kDataA);
+
+  // Append 5 buffers at positions 20 through 24.
+  NewSegmentAppend(20, 5, &kDataA);
+
+  // Append 5 buffers at positions 30 through 34.
+  NewSegmentAppend(30, 5, &kDataA);
+
+  CheckExpectedRanges("{ [0,4) [10,14) [20,24) [30,34) }");
+
+  // Seek to position 21.
+  Seek(20);
+  CheckExpectedBuffers(20, 20, &kDataA);
+
+  // Set memory limit to 1 buffer.
+  SetMemoryLimit(1);
+
+  // Append 5 buffers at positions 40 through 44. This will trigger GC.
+  NewSegmentAppend(40, 5, &kDataA);
+
+  // Should delete everything except current buffer and the keyframe before it.
+  CheckExpectedRanges("{ [20,21) }");
+  CheckExpectedBuffers(21, 21, &kDataA);
+  CheckNoNextBuffer();
+
+  // Make sure appending before and after the ranges didn't somehow break.
+  SetMemoryLimit(100);
+  NewSegmentAppend(0, 10, &kDataA);
+  CheckExpectedRanges("{ [0,9) [20,21) }");
+  Seek(0);
+  CheckExpectedBuffers(0, 9, &kDataA);
+
+  NewSegmentAppend(30, 10, &kDataA);
+  CheckExpectedRanges("{ [0,9) [20,21) [30,39) }");
+  Seek(30);
+  CheckExpectedBuffers(30, 39, &kDataA);
+}
+
+TEST_F(SourceBufferStreamTest, GarbageCollection_NoSeek) {
+  // Set memory limit to 20 buffers.
+  SetMemoryLimit(20);
+
+  // Append 25 buffers at positions 0 through 24.
+  NewSegmentAppend(0, 25, &kDataA);
+
+  // GC deletes the first 5 buffers to keep the memory limit within cap.
+  CheckExpectedRanges("{ [5,24) }");
+  CheckNoNextBuffer();
+  Seek(5);
+  CheckExpectedBuffers(5, 24, &kDataA);
+}
+
+TEST_F(SourceBufferStreamTest, GarbageCollection_PendingSeek) {
+  // Append 10 buffers at positions 0 through 9.
+  NewSegmentAppend(0, 10, &kDataA);
+
+  // Append 5 buffers at positions 25 through 29.
+  NewSegmentAppend(25, 5, &kDataA);
+
+  // Seek to position 15.
+  Seek(15);
+  CheckNoNextBuffer();
+
+  CheckExpectedRanges("{ [0,9) [25,29) }");
+
+  // Set memory limit to 5 buffers.
+  SetMemoryLimit(5);
+
+  // Append 5 buffers as positions 30 to 34 to trigger GC.
+  AppendBuffers(30, 5, &kDataA);
+
+  // The current algorithm will delete from the beginning until the memory is
+  // under cap.
+  CheckExpectedRanges("{ [30,34) }");
+
+  // Expand memory limit again so that GC won't be triggered.
+  SetMemoryLimit(100);
+
+  // Append data to fulfill seek.
+  NewSegmentAppend(15, 5, &kDataA);
+
+  // Check to make sure all is well.
+  CheckExpectedRanges("{ [15,19) [30,34) }");
+  CheckExpectedBuffers(15, 19, &kDataA);
+  Seek(30);
+  CheckExpectedBuffers(30, 34, &kDataA);
+}
+
+TEST_F(SourceBufferStreamTest, GarbageCollection_NeedsMoreData) {
+  // Set memory limit to 10 buffers.
+  SetMemoryLimit(10);
+
+  // Append 10 buffers at positions 0 through 9.
+  NewSegmentAppend(0, 10, &kDataA);
+
+  // Advance next buffer position to 10.
+  Seek(0);
+  CheckExpectedBuffers(0, 9, &kDataA);
+  CheckNoNextBuffer();
+
+  // Append 20 buffers at positions 15 through 34.
+  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) }");
+
+  // 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) }");
+  CheckExpectedBuffers(10, 19, &kDataA);
+}
+
+TEST_F(SourceBufferStreamTest, GarbageCollection_TrackBuffer) {
+  // Set memory limit to 3 buffers.
+  SetMemoryLimit(3);
+
+  // Seek to position 15.
+  Seek(15);
+
+  // Append 20 buffers at positions 0 through 19.
+  NewSegmentAppend(0, 20, &kDataA);
+
+  // Should leave 3 buffers starting at 15.
+  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.
+  CheckExpectedRanges("{ [15,19) }");
+  CheckExpectedBuffers(16, 17, &kDataA);
+  CheckNoNextBuffer();
+
+  // Now add a keyframe at position 20.
+  AppendBuffers(20, 5, &kDataB);
+
+  // Should garbage collect such that there are 3 frames remaining, starting at
+  // the keyframe.
+  CheckExpectedRanges("{ [20,22) }");
+  CheckExpectedBuffers(20, 22, &kDataB);
+  CheckNoNextBuffer();
+}
+
+// Currently disabled because of bug: crbug.com/140875.
+TEST_F(SourceBufferStreamTest, DISABLED_GarbageCollection_WaitingForKeyframe) {
+  // Set memory limit to 10 buffers.
+  SetMemoryLimit(10);
+
+  // Append 5 buffers at positions 10 through 14 and exhaust the buffers.
+  NewSegmentAppend(10, 5, &kDataA);
+  Seek(10);
+  CheckExpectedBuffers(10, 14, &kDataA);
+  CheckExpectedRanges("{ [10,14) }");
+
+  // We are now stalled at position 15.
+  CheckNoNextBuffer();
+
+  // Do an end overlap that causes the latter half of the range to be deleted.
+  NewSegmentAppend(5, 6, &kDataA);
+  CheckNoNextBuffer();
+  CheckExpectedRanges("{ [5,10) }");
+
+  // Append buffers from position 20 to 29. This should trigger GC.
+  NewSegmentAppend(20, 10, &kDataA);
+
+  // GC should keep the keyframe before the seek position 15, and the next 9
+  // buffers closest to the seek position.
+  CheckNoNextBuffer();
+  CheckExpectedRanges("{ [10,10) [20,28) }");
+
+  // Fulfill the seek by appending one buffer at 15.
+  NewSegmentAppend(15, 1, &kDataA);
+  CheckExpectedBuffers(15, 15, &kDataA);
+  CheckExpectedRanges("{ [15,15) [20,28) }");
+}
+
 // TODO(vrk): Add unit tests where keyframes are unaligned between streams.
 // (crbug.com/133557)