--- a/dom/media/mediasource/TrackBuffersManager.cpp
+++ b/dom/media/mediasource/TrackBuffersManager.cpp
@@ -269,32 +269,45 @@ TrackBuffersManager::EvictData(const Tim
   MOZ_ASSERT(NS_IsMainThread());
 
   if (aSize > EvictionThreshold()) {
     // We're adding more data than we can hold.
     return EvictDataResult::BUFFER_FULL;
   }
   const int64_t toEvict = GetSize() + aSize - EvictionThreshold();
 
-  MSE_DEBUG("buffered=%lldkb, eviction threshold=%ukb, evict=%lldkb",
-            GetSize() / 1024, EvictionThreshold() / 1024, toEvict / 1024);
+  uint32_t canEvict;
+  {
+    MonitorAutoLock mon(mMonitor);
+    if (HasVideo()) {
+      canEvict = mVideoTracks.mEvictionIndex.mEvictable;
+    } else {
+      canEvict = mAudioTracks.mEvictionIndex.mEvictable;
+    }
+  }
+
+  MSE_DEBUG(
+    "buffered=%lldkB, eviction threshold=%ukB, evict=%lldkB canevict=%ukB",
+    GetSize() / 1024, EvictionThreshold() / 1024, toEvict / 1024,
+    canEvict / 1024);
 
   if (toEvict <= 0) {
     mEvictionState = EvictionState::NO_EVICTION_NEEDED;
     return EvictDataResult::NO_DATA_EVICTED;
   }
   if (toEvict <= 512*1024) {
     // Don't bother evicting less than 512KB.
     mEvictionState = EvictionState::NO_EVICTION_NEEDED;
     return EvictDataResult::CANT_EVICT;
   }
 
   EvictDataResult result;
 
-  if (mBufferFull && mEvictionState == EvictionState::EVICTION_COMPLETED) {
+  if (mBufferFull && mEvictionState == EvictionState::EVICTION_COMPLETED &&
+      canEvict < uint32_t(toEvict)) {
     // Our buffer is currently full. We will make another eviction attempt.
     // However, the current appendBuffer will fail as we can't know ahead of
     // time if the eviction will later succeed.
     result = EvictDataResult::BUFFER_FULL;
   } else {
     mEvictionState = EvictionState::EVICTION_NEEDED;
     result = EvictDataResult::NO_DATA_EVICTED;
   }
@@ -417,17 +430,17 @@ void
 TrackBuffersManager::DoEvictData(const TimeUnit& aPlaybackTime,
                                  int64_t aSizeToEvict)
 {
   MOZ_ASSERT(OnTaskQueue());
 
   mEvictionState = EvictionState::EVICTION_COMPLETED;
 
   // Video is what takes the most space, only evict there if we have video.
-  const auto& track = HasVideo() ? mVideoTracks : mAudioTracks;
+  auto& track = HasVideo() ? mVideoTracks : mAudioTracks;
   const auto& buffer = track.mBuffers.LastElement();
   // Remove any data we've already played, or before the next sample to be
   // demuxed whichever is lowest.
   TimeUnit lowerLimit = std::min(track.mNextSampleTime, aPlaybackTime);
   uint32_t lastKeyFrameIndex = 0;
   int64_t toEvict = aSizeToEvict;
   int64_t partialEvict = 0;
   for (uint32_t i = 0; i < buffer.Length(); i++) {
@@ -1701,18 +1714,25 @@ TrackBuffersManager::InsertFrames(TrackB
   }
 
   // Adjust our demuxing index if necessary.
   if (trackBuffer.mNextGetSampleIndex.isSome()) {
     if (trackBuffer.mNextInsertionIndex.ref() == trackBuffer.mNextGetSampleIndex.ref() &&
         aIntervals.GetEnd() >= trackBuffer.mNextSampleTime) {
       MSE_DEBUG("Next sample to be played got overwritten");
       trackBuffer.mNextGetSampleIndex.reset();
+      ResetEvictionIndex(trackBuffer);
     } else if (trackBuffer.mNextInsertionIndex.ref() <= trackBuffer.mNextGetSampleIndex.ref()) {
       trackBuffer.mNextGetSampleIndex.ref() += aSamples.Length();
+      // We could adjust the eviction index so that the new data gets added to
+      // the evictable amount (as it is prior currentTime). However, considering
+      // new data is being added prior the current playback, it's likely that
+      // this data will be played next, and as such we probably don't want to
+      // have it evicted too early. So instead reset the eviction index instead.
+      ResetEvictionIndex(trackBuffer);
     }
   }
 
   TrackBuffer& data = trackBuffer.mBuffers.LastElement();
   data.InsertElementsAt(trackBuffer.mNextInsertionIndex.ref(), aSamples);
   trackBuffer.mNextInsertionIndex.ref() += aSamples.Length();
 
   // Update our buffered range with new sample interval.
@@ -1778,43 +1798,57 @@ TrackBuffersManager::RemoveFrames(const 
     const RefPtr<MediaRawData>& sample = data[i];
     if (sample->mKeyframe) {
       break;
     }
     lastRemovedIndex = i;
   }
 
   int64_t maxSampleDuration = 0;
+  uint32_t sizeRemoved = 0;
   TimeIntervals removedIntervals;
   for (uint32_t i = firstRemovedIndex.ref(); i <= lastRemovedIndex; i++) {
     const RefPtr<MediaRawData> sample = data[i];
     TimeInterval sampleInterval =
       TimeInterval(TimeUnit::FromMicroseconds(sample->mTime),
                    TimeUnit::FromMicroseconds(sample->GetEndTime()));
     removedIntervals += sampleInterval;
     if (sample->mDuration > maxSampleDuration) {
       maxSampleDuration = sample->mDuration;
     }
-    aTrackData.mSizeBuffer -= sample->ComputedSizeOfIncludingThis();
+    sizeRemoved += sample->ComputedSizeOfIncludingThis();
   }
+  aTrackData.mSizeBuffer -= sizeRemoved;
 
   MSE_DEBUG("Removing frames from:%u (frames:%u) ([%f, %f))",
             firstRemovedIndex.ref(),
             lastRemovedIndex - firstRemovedIndex.ref() + 1,
             removedIntervals.GetStart().ToSeconds(),
             removedIntervals.GetEnd().ToSeconds());
 
   if (aTrackData.mNextGetSampleIndex.isSome()) {
     if (aTrackData.mNextGetSampleIndex.ref() >= firstRemovedIndex.ref() &&
         aTrackData.mNextGetSampleIndex.ref() <= lastRemovedIndex) {
       MSE_DEBUG("Next sample to be played got evicted");
       aTrackData.mNextGetSampleIndex.reset();
+      ResetEvictionIndex(aTrackData);
     } else if (aTrackData.mNextGetSampleIndex.ref() > lastRemovedIndex) {
-      aTrackData.mNextGetSampleIndex.ref() -=
-        lastRemovedIndex - firstRemovedIndex.ref() + 1;
+      uint32_t samplesRemoved = lastRemovedIndex - firstRemovedIndex.ref() + 1;
+      aTrackData.mNextGetSampleIndex.ref() -= samplesRemoved;
+      if (aTrackData.mEvictionIndex.mLastIndex > lastRemovedIndex) {
+        MOZ_DIAGNOSTIC_ASSERT(
+          aTrackData.mEvictionIndex.mLastIndex >= samplesRemoved &&
+          aTrackData.mEvictionIndex.mEvictable >= sizeRemoved,
+          "Invalid eviction index");
+        MonitorAutoLock mon(mMonitor);
+        aTrackData.mEvictionIndex.mLastIndex -= samplesRemoved;
+        aTrackData.mEvictionIndex.mEvictable -= sizeRemoved;
+      } else {
+        ResetEvictionIndex(aTrackData);
+      }
     }
   }
 
   if (aTrackData.mNextInsertionIndex.isSome()) {
     if (aTrackData.mNextInsertionIndex.ref() > firstRemovedIndex.ref() &&
         aTrackData.mNextInsertionIndex.ref() <= lastRemovedIndex + 1) {
       aTrackData.ResetAppendState();
       MSE_DEBUG("NextInsertionIndex got reset.");
@@ -1946,16 +1980,43 @@ TrackBuffersManager::HighestEndTime()
     tracks.AppendElement(&mAudioBufferedRanges);
   }
   for (auto trackRanges : tracks) {
     highestEndTime = std::max(trackRanges->GetEnd(), highestEndTime);
   }
   return highestEndTime;
 }
 
+void
+TrackBuffersManager::ResetEvictionIndex(TrackData& aTrackData)
+{
+  MonitorAutoLock mon(mMonitor);
+  aTrackData.mEvictionIndex.Reset();
+}
+
+void
+TrackBuffersManager::UpdateEvictionIndex(TrackData& aTrackData,
+                                         uint32_t currentIndex)
+{
+  uint32_t evictable = 0;
+  TrackBuffer& data = aTrackData.mBuffers.LastElement();
+  MOZ_DIAGNOSTIC_ASSERT(currentIndex >= aTrackData.mEvictionIndex.mLastIndex,
+                        "Invalid call");
+  MOZ_DIAGNOSTIC_ASSERT(currentIndex == data.Length() ||
+                        data[currentIndex]->mKeyframe,"Must stop at keyframe");
+
+  for (uint32_t i = aTrackData.mEvictionIndex.mLastIndex; i < currentIndex;
+       i++) {
+    evictable += data[i]->ComputedSizeOfIncludingThis();
+  }
+  aTrackData.mEvictionIndex.mLastIndex = currentIndex;
+  MonitorAutoLock mon(mMonitor);
+  aTrackData.mEvictionIndex.mEvictable += evictable;
+}
+
 const TrackBuffersManager::TrackBuffer&
 TrackBuffersManager::GetTrackBuffer(TrackInfo::TrackType aTrack)
 {
   MOZ_ASSERT(OnTaskQueue());
   return GetTracksData(aTrack).mBuffers.LastElement();
 }
 
 uint32_t TrackBuffersManager::FindSampleIndex(const TrackBuffer& aTrackBuffer,
@@ -1984,16 +2045,17 @@ TrackBuffersManager::Seek(TrackInfo::Tra
   auto& trackBuffer = GetTracksData(aTrack);
   const TrackBuffersManager::TrackBuffer& track = GetTrackBuffer(aTrack);
 
   if (!track.Length()) {
     // This a reset. It will be followed by another valid seek.
     trackBuffer.mNextGetSampleIndex = Some(uint32_t(0));
     trackBuffer.mNextSampleTimecode = TimeUnit();
     trackBuffer.mNextSampleTime = TimeUnit();
+    ResetEvictionIndex(trackBuffer);
     return TimeUnit();
   }
 
   uint32_t i = 0;
 
   if (aTime != TimeUnit()) {
     // Determine the interval of samples we're attempting to seek to.
     TimeIntervals buffered = trackBuffer.mBufferedRanges;
@@ -2022,23 +2084,26 @@ TrackBuffersManager::Seek(TrackInfo::Tra
       lastKeyFrameTime = Some(sampleTime);
       lastKeyFrameIndex = i;
     }
     if (sampleTime == aTime ||
         (sampleTime > aTime && lastKeyFrameTime.isSome())) {
       break;
     }
   }
-  MSE_DEBUG("Keyframe %s found at %lld",
+  MSE_DEBUG("Keyframe %s found at %lld @ %u",
             lastKeyFrameTime.isSome() ? "" : "not",
-            lastKeyFrameTime.refOr(TimeUnit()).ToMicroseconds());
+            lastKeyFrameTime.refOr(TimeUnit()).ToMicroseconds(),
+            lastKeyFrameIndex);
 
   trackBuffer.mNextGetSampleIndex = Some(lastKeyFrameIndex);
   trackBuffer.mNextSampleTimecode = lastKeyFrameTimecode;
   trackBuffer.mNextSampleTime = lastKeyFrameTime.refOr(TimeUnit());
+  ResetEvictionIndex(trackBuffer);
+  UpdateEvictionIndex(trackBuffer, lastKeyFrameIndex);
 
   return lastKeyFrameTime.refOr(TimeUnit());
 }
 
 uint32_t
 TrackBuffersManager::SkipToNextRandomAccessPoint(TrackInfo::TrackType aTrack,
                                                  const TimeUnit& aTimeThreadshold,
                                                  const media::TimeUnit& aFuzz,
@@ -2116,16 +2181,21 @@ TrackBuffersManager::SkipToNextRandomAcc
         // we are speeding up decoding by dropping the unplayable frames.
         // So we can mark aFound as true.
         aFound = true;
         break;
       }
       parsed--;
     }
   }
+
+  if (aFound) {
+    UpdateEvictionIndex(trackData, trackData.mNextGetSampleIndex.ref());
+  }
+
   return parsed;
 }
 
 const MediaRawData*
 TrackBuffersManager::GetSample(TrackInfo::TrackType aTrack,
                                size_t aIndex,
                                const TimeUnit& aExpectedDts,
                                const TimeUnit& aExpectedPts,
@@ -2188,16 +2258,19 @@ TrackBuffersManager::GetSample(TrackInfo
       return nullptr;
     }
 
     RefPtr<MediaRawData> p = sample->Clone();
     if (!p) {
       aResult = MediaResult(NS_ERROR_OUT_OF_MEMORY, __func__);
       return nullptr;
     }
+    if (p->mKeyframe) {
+      UpdateEvictionIndex(trackData, trackData.mNextGetSampleIndex.ref());
+    }
     trackData.mNextGetSampleIndex.ref()++;
     // Estimate decode timestamp and timestamp of the next sample.
     TimeUnit nextSampleTimecode =
       TimeUnit::FromMicroseconds(sample->mTimecode + sample->mDuration);
     TimeUnit nextSampleTime =
       TimeUnit::FromMicroseconds(sample->GetEndTime());
     const MediaRawData* nextSample =
       GetSample(aTrack,
@@ -2239,16 +2312,23 @@ TrackBuffersManager::GetSample(TrackInfo
 
   const RefPtr<MediaRawData>& sample = track[pos];
   RefPtr<MediaRawData> p = sample->Clone();
   if (!p) {
     // OOM
     aResult = MediaResult(NS_ERROR_OUT_OF_MEMORY, __func__);
     return nullptr;
   }
+
+  // Find the previous keyframe to calculate the evictable amount.
+  int32_t i = pos;
+  for (; !track[i]->mKeyframe; i--) {
+  }
+  UpdateEvictionIndex(trackData, i);
+
   trackData.mNextGetSampleIndex = Some(uint32_t(pos)+1);
   trackData.mNextSampleTimecode =
     TimeUnit::FromMicroseconds(sample->mTimecode + sample->mDuration);
   trackData.mNextSampleTime =
     TimeUnit::FromMicroseconds(sample->GetEndTime());
   aResult = NS_OK;
   return p.forget();
 }

--- a/dom/media/mediasource/TrackBuffersManager.h
+++ b/dom/media/mediasource/TrackBuffersManager.h
@@ -329,16 +329,36 @@ private:
     // If the position is equal to the TrackBuffer's length, it indicates that
     // we've reached EOS.
     Maybe<uint32_t> mNextGetSampleIndex;
     // Approximation of the next sample's decode timestamp.
     media::TimeUnit mNextSampleTimecode;
     // Approximation of the next sample's presentation timestamp.
     media::TimeUnit mNextSampleTime;
 
+    struct EvictionIndex
+    {
+      EvictionIndex() { Reset(); }
+      void Reset()
+      {
+        mEvictable = 0;
+        mLastIndex = 0;
+      }
+      uint32_t mEvictable;
+      uint32_t mLastIndex;
+    };
+    // Size of data that can be safely evicted during the next eviction
+    // cycle.
+    // We consider as evictable all frames up to the last keyframe prior to
+    // mNextGetSampleIndex. If mNextGetSampleIndex isn't set, then we assume
+    // that we can't yet evict data.
+    // Protected by global monitor, except when reading on the task queue as it
+    // is only written there.
+    EvictionIndex mEvictionIndex;
+
     void ResetAppendState()
     {
       mLastDecodeTimestamp.reset();
       mLastFrameDuration.reset();
       mHighestEndTimestamp.reset();
       mNeedRandomAccessPoint = true;
 
       mNextInsertionIndex.reset();
@@ -358,16 +378,19 @@ private:
   void UpdateHighestTimestamp(TrackData& aTrackData,
                               const media::TimeUnit& aHighestTime);
   // Remove all frames and their dependencies contained in aIntervals.
   // Return the index at which frames were first removed or 0 if no frames
   // removed.
   size_t RemoveFrames(const media::TimeIntervals& aIntervals,
                       TrackData& aTrackData,
                       uint32_t aStartIndex);
+  // Recalculate track's evictable amount.
+  void ResetEvictionIndex(TrackData& aTrackData);
+  void UpdateEvictionIndex(TrackData& aTrackData, uint32_t aCurrentIndex);
   // Find index of sample. Return a negative value if not found.
   uint32_t FindSampleIndex(const TrackBuffer& aTrackBuffer,
                            const media::TimeInterval& aInterval);
   const MediaRawData* GetSample(TrackInfo::TrackType aTrack,
                                 size_t aIndex,
                                 const media::TimeUnit& aExpectedDts,
                                 const media::TimeUnit& aExpectedPts,
                                 const media::TimeUnit& aFuzz);
@@ -431,17 +454,17 @@ private:
   enum class EvictionState
   {
     NO_EVICTION_NEEDED,
     EVICTION_NEEDED,
     EVICTION_COMPLETED,
   };
   Atomic<EvictionState> mEvictionState;
 
-  // Monitor to protect following objects accessed across multipple threads.
+  // Monitor to protect following objects accessed across multiple threads.
   mutable Monitor mMonitor;
   // Stable audio and video track time ranges.
   media::TimeIntervals mVideoBufferedRanges;
   media::TimeIntervals mAudioBufferedRanges;
   // MediaInfo of the first init segment read.
   MediaInfo mInfo;
 };