Implement simple garbage collection in SourceBufferStream

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 c2be6a79dbfd784672f48f27c5123f6fbfa53bbc..cb74864b902f36578af678b1651aa97fb74853ed 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,8 @@ 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.
+static int kDefaultMemoryLimit = 20 * 1024 * 1024;

[vrk (LEFT CHROMIUM), 2012/08/04 01:32:31]

Not sure what I should actually set this to.

Also, this sets a cap on the stream, but not the video tag, so if there are 3
streams then they could potentially take up 3 * kDefaultMemoryLimit.

[acolwell GONE FROM CHROMIUM, 2012/08/06 16:44:52]

I think we should have audio & video specific limits. I believe 12MB should be
enough for ~5 minutes of audio @ 320Kbps. 150MB appears to be enough for ~5
minutes of 4Mbps content which appears to be what YouTube's 1080p content is
encoded at. I'm fine w/ halving these values if you think they are too big.

[vrk (LEFT CHROMIUM), 2012/08/06 20:27:14]

Done.

 
 namespace media {
 
@@ -252,7 +277,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_(kDefaultMemoryLimit) {
   audio_configs_[0] = new AudioDecoderConfig();
   audio_configs_[0]->CopyFrom(audio_config);
 }
@@ -270,7 +296,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_(kDefaultMemoryLimit) {
   video_configs_[0] = new VideoDecoderConfig();
   video_configs_[0]->CopyFrom(video_config);
 }
@@ -389,6 +416,8 @@ bool SourceBufferStream::Append(
     }
   }
 
+  GarbageCollectIfNeeded();
+
   DCHECK(IsRangeListSorted(ranges_));
   DCHECK(OnlySelectedRangeIsSeeked());
   return true;
@@ -460,6 +489,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 +948,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 +961,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 +984,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 +1037,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 +1073,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 +1100,110 @@ 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());
+
+    // Delete buffers up until the next keyframe, i.e. the new front.
+    int start_index = front->second;
+    keyframe_map_.erase(front);
+
+    front = keyframe_map_.begin();
+    int end_index = start_index + buffers_.size();

[acolwell GONE FROM CHROMIUM, 2012/08/06 16:44:52]

Is this right? I'm assuming this is trying to specify deleting all the buffers.
Shouldn't it be end_index = buffers_.size() - 1?

[vrk (LEFT CHROMIUM), 2012/08/06 20:27:14]

Yes and yes. 
No. It's not obvious and that's actually what I had at first, but unit-testing
caught the bug :)

Here's an example. Say there are the following buffers:

0 - 0 KEYFRAME
1 - 33
2 - 66
3 - 100 KEYFRAME
4 - 133
5 - 166

Imagine we've deleted 0 through 2. Then what we have is:
3 - 100 KEYFRAME
4 - 133
5 - 166

Note that |keyframe_map_| has not been updated, so index 3 in |keyframe_map_|
refers to t=100 still. So start index is 3, and buffers.size() is 3, so you need
offset the buffers.size() by the start_index to get 6. The for loop goes from i
= 3 to i < 6, so start_index + buffers.size() is the proper expression.

+    if (front != keyframe_map_.end())
+      end_index = front->second;
+
+    // Note that the |keyframe_map_| points to the wrong indices after the first
+    // GOP is deleted. However, the distances between keyframes are the same, so

[acolwell GONE FROM CHROMIUM, 2012/08/06 16:44:52]

nit: Consider rewording "the distances between keyframes are the same" since it
implied to me a constant keyframe interval which we definitely don't want to
assume. I believe you are trying to indicate that the relative distance between
keyframes doesn't change so you can apply a constant offset to all of the
entries to reflect the deleted buffers. Is that correct?

[vrk (LEFT CHROMIUM), 2012/08/06 20:27:14]

Good point! Upon re-reading this morning, that's exactly what it sounds like.
Yes.
So that's true too, but the reason why I had the comment here was to attempt to
explain the for-loop bounds, i.e. to explain that we go from 3 to 6 instead of 0
to 3 (to use the example I gave above).

Looks like it was still confusing though! I changed the logic a bit and changed
the comment, so hopefully should be clearer what's going on.

+    // we can use the indices to calculate how many buffers to delete from the
+    // front.
+    for (int i = start_index; i < end_index; i++) {

[acolwell GONE FROM CHROMIUM, 2012/08/06 16:44:52]

I think it might be clearer if you changed this to a 0-buffers_to_delete loop
and just use the indices for computing buffers_to_delete above. I think that can
help ease worry about the fact that the data in keyframe_map_ becomes
temporarily invalid and prevents people from accidentally relying on the index
values. Putting the comment above next to a buffers_to_delete = front->second -
start_index; makes it much clearer you only care about the relative relationship
instead of the absolute values.

[vrk (LEFT CHROMIUM), 2012/08/06 20:27:14]

Made the loop 0-based but kept end_index; let me know if you think it's still
unclear!

+      int bytes_deleted = buffers_.front()->GetDataSize();
+      size_in_bytes_ -= bytes_deleted;
+      total_bytes_deleted += bytes_deleted;
+      buffers_.pop_front();
+      ++buffers_deleted;
+    }
+  }
+
+  // Update indexes 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 +1238,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;
 }