Implement simple garbage collection in SourceBufferStream

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 "base/bind.h"
@@ skipping 68 matching lines @@
   // starting at the buffer that had been at |next_buffer_index_|.
   // Returns true if the |next_buffer_index_| is reset. Note that this method
   // may return true even if it does not add any buffers to |deleted_buffers|.
   // This indicates that the range had not buffered |next_buffer_index_|, but
   // a buffer at that position would have been deleted.
   bool TruncateAt(scoped_refptr<StreamParserBuffer> buffer,
                   BufferQueue* deleted_buffers);
   // 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
   // filled with a valid buffer, false if there is not enough data to fulfill
   // the request.
   bool GetNextBuffer(scoped_refptr<StreamParserBuffer>* out_buffer);
   bool HasNextBuffer() const;
 
   // Returns the config ID for the buffer that will be returned by
   // GetNextBuffer().
@@ skipping 38 matching lines @@
   // Returns true if the end of this range contains buffers that overlaps with
   // the beginning of |range|.
   bool EndOverlaps(const SourceBufferRange& range) const;
 
   // Returns true if |timestamp| is the timestamp of the next buffer in
   // sequence after |buffer|, false otherwise.
   bool IsNextInSequence(
       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;
 
   // Seeks the range to the next keyframe after |timestamp|. If
   // |skip_given_timestamp| is true, the seek will go to a keyframe with a
   // timestamp strictly greater than |timestamp|.
   void SeekAhead(base::TimeDelta timestamp, bool skip_given_timestamp);
 
   // Returns an iterator in |keyframe_map_| pointing to the next keyframe after
   // |timestamp|. If |skip_given_timestamp| is true, this returns the first
   // keyframe with a timestamp strictly greater than |timestamp|.
   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;
 
   // Returns the approximate duration of a buffer in this range.
   base::TimeDelta GetApproximateDuration() const;
 
   // An ordered list of buffers in this range.
   BufferQueue buffers_;
 
@@ skipping 18 matching lines @@
   // |buffers_|. |media_segment_start_time_| is kNoTimestamp() if this range
   // does not start at the beginning of a media segment, which can only happen
   // garbage collection or after an end overlap that results in a split range
   // (we don't have a way of knowing the media segment timestamp for the new
   // range).
   base::TimeDelta media_segment_start_time_;
 
   // 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);
 };
 
 }  // namespace media
 
 // Helper method that returns true if |ranges| is sorted in increasing order,
 // false otherwise.
 static bool IsRangeListSorted(
     const std::list<media::SourceBufferRange*>& ranges) {
   base::TimeDelta prev = media::kNoTimestamp();
@@ skipping 15 matching lines @@
 
 // An arbitrarily-chosen number to estimate the duration of a buffer if none
 // is set and there's not enough information to get a better estimate.
 static int kDefaultBufferDurationInMs = 125;
 
 // The amount of time the beginning of the buffered data can differ from the
 // start time in order to still be considered the start of stream.
 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 {
 
 SourceBufferStream::SourceBufferStream(const AudioDecoderConfig& audio_config)
     : current_config_index_(0),
       append_config_index_(0),
       audio_configs_(1),
       video_configs_(0),
       stream_start_time_(kNoTimestamp()),
       seek_pending_(false),
       seek_buffer_timestamp_(kNoTimestamp()),
       selected_range_(NULL),
       media_segment_start_time_(kNoTimestamp()),
       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);
 }
 
 SourceBufferStream::SourceBufferStream(const VideoDecoderConfig& video_config)
     : current_config_index_(0),
       append_config_index_(0),
       audio_configs_(0),
       video_configs_(1),
       stream_start_time_(kNoTimestamp()),
       seek_pending_(false),
       seek_buffer_timestamp_(kNoTimestamp()),
       selected_range_(NULL),
       media_segment_start_time_(kNoTimestamp()),
       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);
 }
 
 SourceBufferStream::~SourceBufferStream() {
   while (!ranges_.empty()) {
     delete ranges_.front();
     ranges_.pop_front();
   }
 
@@ skipping 98 matching lines @@
       UpdateTrackBuffer(deleted_buffers);
     } else {
       // If we've deleted the next buffer but |deleted_buffers| is empty,
       // that means we need to seek past the timestamp of the last buffer in
       // the range (i.e. the keyframe timestamp needs to be strictly greater
       // than |end_buffer_timestamp|).
       selected_range_->SeekAheadPast(end_buffer_timestamp);
     }
   }
 
+  GarbageCollectIfNeeded();
+
   DCHECK(IsRangeListSorted(ranges_));
   DCHECK(OnlySelectedRangeIsSeeked());
   return true;
 }
 
 bool SourceBufferStream::ShouldSeekToStartOfBuffered(
     base::TimeDelta seek_timestamp) const {
   if (ranges_.empty())
     return false;
   base::TimeDelta beginning_of_buffered =
@@ skipping 51 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() {
+  // 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,
     bool* deleted_next_buffer, BufferQueue* deleted_buffers) {
   DCHECK(deleted_next_buffer);
   DCHECK(deleted_buffers);
 
   SourceBufferRange* range_for_new_buffers = *range_for_new_buffers_itr;
 
   // If this is a simple case where we can just append to the end of the range,
@@ skipping 396 matching lines @@
   current_config_index_ = selected_range_->GetNextConfigId();
 }
 
 SourceBufferRange::SourceBufferRange(
     const BufferQueue& new_buffers, base::TimeDelta media_segment_start_time,
     const InterbufferDistanceCB& interbuffer_distance_cb)
     : next_buffer_index_(-1),
       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());
   AppendBuffersToEnd(new_buffers);
 }
 
 void SourceBufferRange::AppendBuffersToEnd(const BufferQueue& new_buffers) {
   for (BufferQueue::const_iterator itr = new_buffers.begin();
        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));
 
       if (waiting_for_keyframe_ &&
           (*itr)->GetDecodeTimestamp() >= next_keyframe_timestamp_) {
         next_buffer_index_ = buffers_.size() - 1;
         next_keyframe_timestamp_ = base::TimeDelta();
         waiting_for_keyframe_ = false;
       }
     }
   }
 }
 
 void SourceBufferRange::Seek(base::TimeDelta timestamp) {
   DCHECK(CanSeekTo(timestamp));
   DCHECK(!keyframe_map_.empty());
 
   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()));
 }
 
 void SourceBufferRange::SeekAheadTo(base::TimeDelta timestamp) {
   SeekAhead(timestamp, false);
 }
 
 void SourceBufferRange::SeekAheadPast(base::TimeDelta timestamp) {
   SeekAhead(timestamp, true);
@@ skipping 32 matching lines @@
   if (new_beginning_keyframe == keyframe_map_.end())
     return NULL;
 
   // Remove the data beginning at |keyframe_index| from |buffers_| and save it
   // into |removed_buffers|.
   int keyframe_index = new_beginning_keyframe->second;
   DCHECK_LT(keyframe_index, static_cast<int>(buffers_.size()));
   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 =
       new SourceBufferRange(
           removed_buffers, kNoTimestamp(), interbuffer_distance_cb_);
 
   // If the next buffer position is now in |split_range|, update the state of
   // this range and |split_range| accordingly.
   if (next_buffer_index_ >= static_cast<int>(buffers_.size())) {
     DCHECK(!waiting_for_keyframe_);
@@ skipping 15 matching lines @@
   // lower_bound() returns the first element >= |timestamp|, so if we don't want
   // to include keyframes == |timestamp|, we have to increment the iterator
   // accordingly.
   if (skip_given_timestamp &&
       result != keyframe_map_.end() && result->first == timestamp) {
     ++result;
   }
   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);
 }
 
 bool SourceBufferRange::TruncateAt(
     scoped_refptr<StreamParserBuffer> buffer, BufferQueue* removed_buffers) {
   // Find the place in |buffers_| where we will begin deleting data.
   BufferQueue::iterator starting_point =
       std::lower_bound(buffers_.begin(), buffers_.end(),
                        buffer,
                        BufferComparator);
   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 the |end_index| by the |buffers_deleted| to get

[acolwell GONE FROM CHROMIUM, 2012/08/06 20:48:02]

nit: s/end_index/front->second/ since that is what actually comes out of
keyframe_map_?

[vrk (LEFT CHROMIUM), 2012/08/06 20:52:46]

Done.

+      // 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);
   DCHECK(removed_buffers->empty());
 
   // Return if we're not deleting anything.
   if (starting_point == buffers_.end())
     return false;
 
   // Reset the next buffer index if we will be deleting the buffer that's next
@@ skipping 14 matching lines @@
       removed_next_buffer = true;
     }
   }
 
   // Remove keyframes from |starting_point| onward.
   KeyframeMap::iterator starting_point_keyframe =
       keyframe_map_.lower_bound((*starting_point)->GetDecodeTimestamp());
   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;
 }
 
 bool SourceBufferRange::GetNextBuffer(
     scoped_refptr<StreamParserBuffer>* out_buffer) {
   if (!HasNextBuffer())
     return false;
 
   *out_buffer = buffers_.at(next_buffer_index_);
   next_buffer_index_++;
@@ skipping 118 matching lines @@
   return 2 * GetApproximateDuration();
 }
 
 base::TimeDelta SourceBufferRange::GetApproximateDuration() const {
   base::TimeDelta max_interbuffer_distance = interbuffer_distance_cb_.Run();
   DCHECK(max_interbuffer_distance != kNoTimestamp());
   return max_interbuffer_distance;
 }
 
 }  // namespace media