Bug 513144. Allow nsMediaCache blocks to be owned by multiple streams at the same time. r=doublec
authorRobert O'Callahan <robert@ocallahan.org>
Tue, 15 Sep 2009 14:30:44 +1200
changeset 32903 a4ef15912d218af253eefa53cba30e0376a64349
parent 32902 857725884e1e74fde2ee0f4b3110e3a29c970dfb
child 32904 aea350f323885028993916ee73b7ae7e2e3e6d0c
push id1
push userroot
push dateMon, 20 Oct 2014 17:29:22 +0000
reviewersdoublec
bugs513144
milestone1.9.3a1pre
Bug 513144. Allow nsMediaCache blocks to be owned by multiple streams at the same time. r=doublec
content/media/nsMediaCache.cpp
content/media/nsMediaCache.h
--- a/content/media/nsMediaCache.cpp
+++ b/content/media/nsMediaCache.cpp
@@ -1,9 +1,9 @@
- /* -*- Mode: C++; tab-width: 2; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
+/* -*- Mode: C++; tab-width: 2; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
 /* vim:set ts=2 sw=2 sts=2 et cindent: */
 /* ***** BEGIN LICENSE BLOCK *****
  * Version: MPL 1.1/GPL 2.0/LGPL 2.1
  *
  * The contents of this file are subject to the Mozilla Public License Version
  * 1.1 (the "License"); you may not use this file except in compliance with
  * the License. You may obtain a copy of the License at
  * http://www.mozilla.org/MPL/
@@ -152,18 +152,18 @@ public:
   // will do that if necessary. The caller will call QueueUpdate().
   void NoteSeek(nsMediaCacheStream* aStream, PRInt64 aOldOffset);
   // Notify the cache that a block has been read from. This is used
   // to update last-use times. The block may not actually have a
   // cache entry yet since Read can read data from a stream's
   // in-memory mPartialBlockBuffer while the block is only partly full,
   // and thus hasn't yet been committed to the cache. The caller will
   // call QueueUpdate().
-  void NoteBlockUsage(PRInt32 aBlockIndex, nsMediaCacheStream::ReadMode aMode,
-                      TimeStamp aNow);
+  void NoteBlockUsage(nsMediaCacheStream* aStream, PRInt32 aBlockIndex,
+                      nsMediaCacheStream::ReadMode aMode, TimeStamp aNow);
 
   // This queues a call to Update() on the main thread.
   void QueueUpdate();
 
   // Updates the cache state asynchronously on the main thread:
   // -- try to trim the cache back to its desired size, if necessary
   // -- suspend channels that are going to read data that's lower priority
   // than anything currently cached
@@ -192,67 +192,79 @@ protected:
   // aMaxSearchBlockIndex are considered. If aForStream is non-null,
   // then aForStream and aForStreamBlock indicate what media data will
   // be placed; FindReusableBlock will favour returning free blocks
   // near other blocks for that point in the stream.
   PRInt32 FindReusableBlock(TimeStamp aNow,
                             nsMediaCacheStream* aForStream,
                             PRInt32 aForStreamBlock,
                             PRInt32 aMaxSearchBlockIndex);
+  PRBool BlockIsReusable(PRInt32 aBlockIndex);
   // Given a list of blocks sorted with the most reusable blocks at the
   // end, find the last block whose stream is not pinned (if any)
   // and whose cache entry index is less than aBlockIndexLimit
   // and append it to aResult.
   void AppendMostReusableBlock(BlockList* aBlockList,
                                nsTArray<PRUint32>* aResult,
                                PRInt32 aBlockIndexLimit);
 
   enum BlockClass {
-    // block belongs to mFreeBlockList because it's free
-    FREE_BLOCK,
     // block belongs to mMetadataBlockList because data has been consumed
     // from it in "metadata mode" --- in particular blocks read during
     // Ogg seeks go into this class. These blocks may have played data
     // in them too.
     METADATA_BLOCK,
     // block belongs to mPlayedBlockList because its offset is
     // less than the stream's current reader position
     PLAYED_BLOCK,
     // block belongs to the stream's mReadaheadBlockList because its
     // offset is greater than or equal to the stream's current
     // reader position
     READAHEAD_BLOCK
   };
 
-  struct Block {
-    Block() : mStream(nsnull), mClass(FREE_BLOCK) {}
+  struct BlockOwner {
+    BlockOwner() : mStream(nsnull), mClass(READAHEAD_BLOCK) {}
 
     // The stream that owns this block, or null if the block is free.
     nsMediaCacheStream* mStream;
     // The block index in the stream. Valid only if mStream is non-null.
     PRUint32            mStreamBlock;
     // Time at which this block was last used. Valid only if
     // mClass is METADATA_BLOCK or PLAYED_BLOCK.
     TimeStamp           mLastUseTime;
-    // The class is FREE_BLOCK if and only if mStream is null
     BlockClass          mClass;
   };
 
+  struct Block {
+    // Free blocks have an empty mOwners array
+    nsTArray<BlockOwner> mOwners;
+  };
+
   // Get the BlockList that the block should belong to given its
-  // current mClass and mStream
-  BlockList* GetListForBlock(Block* aBlock);
-  // Add the block to the free list, mark it FREE_BLOCK, and mark
-  // its stream (if any) as not having the block in cache
+  // current owner
+  BlockList* GetListForBlock(BlockOwner* aBlock);
+  // Get the BlockOwner for the given block index and owning stream
+  // (returns null if the stream does not own the block)
+  BlockOwner* GetBlockOwner(PRInt32 aBlockIndex, nsMediaCacheStream* aStream);
+  // Returns true iff the block is free
+  PRBool IsBlockFree(PRInt32 aBlockIndex)
+  { return mIndex[aBlockIndex].mOwners.IsEmpty(); }
+  // Add the block to the free list and mark its streams as not having
+  // the block in cache
   void FreeBlock(PRInt32 aBlock);
+  // Mark aStream as not having the block, removing it as an owner. If
+  // the block has no more owners it's added to the free list.
+  void RemoveBlockOwner(PRInt32 aBlockIndex, nsMediaCacheStream* aStream);
   // Swap all metadata associated with the two blocks. The caller
   // is responsible for swapping up any cache file state.
   void SwapBlocks(PRInt32 aBlockIndex1, PRInt32 aBlockIndex2);
-  // Insert the block into the readahead block list for its stream
+  // Insert the block into the readahead block list for the stream
   // at the right point in the list.
-  void InsertReadaheadBlock(PRInt32 aBlockIndex);
+  void InsertReadaheadBlock(BlockOwner* aBlockOwner, PRInt32 aBlockIndex);
 
   // Guess the duration until block aBlock will be next used
   TimeDuration PredictNextUse(TimeStamp aNow, PRInt32 aBlock);
   // Guess the duration until the next incoming data on aStream will be used
   TimeDuration PredictNextUseForIncomingData(nsMediaCacheStream* aStream);
 
   // Truncate the file and index array if there are free blocks at the
   // end
@@ -269,20 +281,16 @@ protected:
   nsTArray<Block> mIndex;
   // The file descriptor of the cache file. The file will be deleted
   // by the operating system when this is closed.
   PRFileDesc*     mFD;
   // The current file offset in the cache file.
   PRInt64         mFDCurrentPos;
   // The list of free blocks; they are not ordered.
   BlockList       mFreeBlocks;
-  // The list of metadata blocks; the first block is the most recently used
-  BlockList       mMetadataBlocks;
-  // The list of played-back blocks; the first block is the most recently used
-  BlockList       mPlayedBlocks;
   // True if an event to run Update() has been queued but not processed
   PRPackedBool    mUpdateQueued;
 #ifdef DEBUG
   PRPackedBool    mInUpdate;
 #endif
 };
 
 // There is at most one media cache (although that could quite easily be
@@ -611,17 +619,17 @@ PRInt32
 nsMediaCache::FindBlockForIncomingData(TimeStamp aNow,
                                        nsMediaCacheStream* aStream)
 {
   PR_ASSERT_CURRENT_THREAD_IN_MONITOR(mMonitor);
 
   PRInt32 blockIndex = FindReusableBlock(aNow, aStream,
       aStream->mChannelOffset/BLOCK_SIZE, PR_INT32_MAX);
 
-  if (blockIndex < 0 || mIndex[blockIndex].mStream) {
+  if (blockIndex < 0 || !IsBlockFree(blockIndex)) {
     // The block returned is already allocated.
     // Don't reuse it if a) there's room to expand the cache or
     // b) the data we're going to store in the free block is not higher
     // priority than the data already stored in the free block.
     // The latter can lead us to go over the cache limit a bit.
     if ((mIndex.Length() < PRUint32(GetMaxBlocks()) || blockIndex < 0 ||
          PredictNextUseForIncomingData(aStream) >= PredictNextUse(aNow, blockIndex))) {
       blockIndex = mIndex.Length();
@@ -630,34 +638,46 @@ nsMediaCache::FindBlockForIncomingData(T
       mFreeBlocks.AddFirstBlock(blockIndex);
       return blockIndex;
     }
   }
 
   return blockIndex;
 }
 
+PRBool
+nsMediaCache::BlockIsReusable(PRInt32 aBlockIndex)
+{
+  Block* block = &mIndex[aBlockIndex];
+  for (PRUint32 i = 0; i < block->mOwners.Length(); ++i) {
+    nsMediaCacheStream* stream = block->mOwners[i].mStream;
+    if (stream->mPinCount >= 0 ||
+        stream->mStreamOffset/BLOCK_SIZE == block->mOwners[i].mStreamBlock) {
+      return PR_FALSE;
+    }
+  }
+  return PR_TRUE;
+}
+
 void
 nsMediaCache::AppendMostReusableBlock(BlockList* aBlockList,
                                       nsTArray<PRUint32>* aResult,
                                       PRInt32 aBlockIndexLimit)
 {
   PR_ASSERT_CURRENT_THREAD_IN_MONITOR(mMonitor);
 
   PRInt32 blockIndex = aBlockList->GetLastBlock();
   if (blockIndex < 0)
     return;
   do {
     // Don't consider blocks for pinned streams, or blocks that are
-    // beyond the specified limit, or the block that contains its stream's
+    // beyond the specified limit, or a block that contains a stream's
     // current read position (such a block contains both played data
     // and readahead data)
-    nsMediaCacheStream* stream = mIndex[blockIndex].mStream;
-    if (stream->mPinCount == 0 && blockIndex < aBlockIndexLimit &&
-        stream->mStreamOffset/BLOCK_SIZE != mIndex[blockIndex].mStreamBlock) {
+    if (blockIndex < aBlockIndexLimit && BlockIsReusable(blockIndex)) {
       aResult->AppendElement(blockIndex);
       return;
     }
     blockIndex = aBlockList->GetPrevBlock(blockIndex);
   } while (blockIndex >= 0);
 }
 
 PRInt32
@@ -672,17 +692,17 @@ nsMediaCache::FindReusableBlock(TimeStam
 
   if (aForStream && aForStreamBlock > 0 &&
       PRUint32(aForStreamBlock) <= aForStream->mBlocks.Length()) {
     PRInt32 prevCacheBlock = aForStream->mBlocks[aForStreamBlock - 1];
     if (prevCacheBlock >= 0) {
       PRUint32 freeBlockScanEnd =
         PR_MIN(length, prevCacheBlock + FREE_BLOCK_SCAN_LIMIT);
       for (PRUint32 i = prevCacheBlock; i < freeBlockScanEnd; ++i) {
-        if (mIndex[i].mClass == FREE_BLOCK)
+        if (IsBlockFree(i))
           return i;
       }
     }
   }
 
   if (!mFreeBlocks.IsEmpty()) {
     PRInt32 blockIndex = mFreeBlocks.GetFirstBlock();
     do {
@@ -692,168 +712,210 @@ nsMediaCache::FindReusableBlock(TimeStam
     } while (blockIndex >= 0);
   }
 
   // Build a list of the blocks we should consider for the "latest
   // predicted time of next use". We can exploit the fact that the block
   // linked lists are ordered by increasing time of next use. This is
   // actually the whole point of having the linked lists.
   nsAutoTArray<PRUint32,8> candidates;
-  AppendMostReusableBlock(&mMetadataBlocks, &candidates, length);
-  AppendMostReusableBlock(&mPlayedBlocks, &candidates, length);
   for (PRUint32 i = 0; i < mStreams.Length(); ++i) {
     nsMediaCacheStream* stream = mStreams[i];
-    // Don't consider a) blocks for pinned streams or b) blocks in
-    // non-seekable streams that contain data ahead of the current reader
-    // position. In the latter case, if we remove the block we won't be
-    // able to seek back to read it later.
-    if (!stream->mReadaheadBlocks.IsEmpty() && stream->mIsSeekable &&
-        stream->mPinCount == 0) {
-      // Find a readahead block that's in the given limit
-      PRInt32 blockIndex = stream->mReadaheadBlocks.GetLastBlock();
-      do {
-        if (PRUint32(blockIndex) < length) {
-          candidates.AppendElement(blockIndex);
-          break;
-        }
-        blockIndex = stream->mReadaheadBlocks.GetPrevBlock(blockIndex);
-      } while (blockIndex >= 0);
+    if (stream->mPinCount > 0) {
+      // No point in even looking at this stream's blocks
+      continue;
+    }
+
+    AppendMostReusableBlock(&stream->mMetadataBlocks, &candidates, length);
+    AppendMostReusableBlock(&stream->mPlayedBlocks, &candidates, length);
+
+    // Don't consider readahead blocks in non-seekable streams. If we
+    // remove the block we won't be able to seek back to read it later.
+    if (stream->mIsSeekable) {
+      AppendMostReusableBlock(&stream->mReadaheadBlocks, &candidates, length);
     }
   }
 
   TimeDuration latestUse;
   PRInt32 latestUseBlock = -1;
   for (PRUint32 i = 0; i < candidates.Length(); ++i) {
     TimeDuration nextUse = PredictNextUse(aNow, candidates[i]);
     if (nextUse > latestUse) {
       latestUse = nextUse;
       latestUseBlock = candidates[i];
     }
   }
 
-#ifdef DEBUG
-  for (PRUint32 blockIndex = 0; blockIndex < length; ++blockIndex) {
-    Block* block = &mIndex[blockIndex];
-    nsMediaCacheStream* stream = block->mStream;
-    NS_ASSERTION(!stream || stream->mPinCount > 0 ||
-                 (!stream->mIsSeekable && block->mClass == READAHEAD_BLOCK) ||
-                 stream->mStreamOffset/BLOCK_SIZE == block->mStreamBlock ||
-                 PredictNextUse(aNow, blockIndex) <= latestUse,
-                 "We missed a block that should be replaced");
-  }
-#endif
-
   return latestUseBlock;
 }
 
 nsMediaCache::BlockList*
-nsMediaCache::GetListForBlock(Block* aBlock)
+nsMediaCache::GetListForBlock(BlockOwner* aBlock)
 {
   switch (aBlock->mClass) {
-  case FREE_BLOCK:
-    NS_ASSERTION(!aBlock->mStream, "Free block has a stream?");
-    return &mFreeBlocks;
   case METADATA_BLOCK:
     NS_ASSERTION(aBlock->mStream, "Metadata block has no stream?");
-    return &mMetadataBlocks;
+    return &aBlock->mStream->mMetadataBlocks;
   case PLAYED_BLOCK:
     NS_ASSERTION(aBlock->mStream, "Metadata block has no stream?");
-    return &mPlayedBlocks;
+    return &aBlock->mStream->mPlayedBlocks;
   case READAHEAD_BLOCK:
     NS_ASSERTION(aBlock->mStream, "Readahead block has no stream?");
     return &aBlock->mStream->mReadaheadBlocks;
   default:
     NS_ERROR("Invalid block class");
     return nsnull;
   }
 }
 
+nsMediaCache::BlockOwner*
+nsMediaCache::GetBlockOwner(PRInt32 aBlockIndex, nsMediaCacheStream* aStream)
+{
+  Block* block = &mIndex[aBlockIndex];
+  for (PRUint32 i = 0; i < block->mOwners.Length(); ++i) {
+    if (block->mOwners[i].mStream == aStream)
+      return &block->mOwners[i];
+  }
+  return nsnull;
+}
+
 void
 nsMediaCache::SwapBlocks(PRInt32 aBlockIndex1, PRInt32 aBlockIndex2)
 {
   PR_ASSERT_CURRENT_THREAD_IN_MONITOR(mMonitor);
 
   Block* block1 = &mIndex[aBlockIndex1];
   Block* block2 = &mIndex[aBlockIndex2];
 
-  Block tmp = *block1;
-  *block1 = *block2;
-  *block2 = tmp;
+  block1->mOwners.SwapElements(block2->mOwners);
 
   // Now all references to block1 have to be replaced with block2 and
-  // vice versa
-
-  if (block1->mStream) {
-    block1->mStream->mBlocks[block1->mStreamBlock] = aBlockIndex1;
-  }
-  if (block2->mStream) {
-    block2->mStream->mBlocks[block2->mStreamBlock] = aBlockIndex2;
+  // vice versa.
+  // First update stream references to blocks via mBlocks.
+  const Block* blocks[] = { block1, block2 };
+  PRInt32 blockIndices[] = { aBlockIndex1, aBlockIndex2 };
+  for (PRInt32 i = 0; i < 2; ++i) {
+    for (PRUint32 j = 0; j < blocks[i]->mOwners.Length(); ++j) {
+      const BlockOwner* b = &blocks[i]->mOwners[j];
+      b->mStream->mBlocks[b->mStreamBlock] = blockIndices[i];
+    }
   }
 
-  BlockList* list1 = GetListForBlock(block1);
-  list1->NotifyBlockSwapped(aBlockIndex1, aBlockIndex2);
-  BlockList* list2 = GetListForBlock(block2);
-  // We have to be careful we don't swap the same reference twice!
-  if (list1 != list2) {
-    list2->NotifyBlockSwapped(aBlockIndex1, aBlockIndex2);
+  // Now update references to blocks in block lists.
+  mFreeBlocks.NotifyBlockSwapped(aBlockIndex1, aBlockIndex2);
+
+  nsTHashtable<nsPtrHashKey<nsMediaCacheStream> > visitedStreams;
+  visitedStreams.Init();
+
+  for (PRInt32 i = 0; i < 2; ++i) {
+    for (PRUint32 j = 0; j < blocks[i]->mOwners.Length(); ++j) {
+      nsMediaCacheStream* stream = blocks[i]->mOwners[j].mStream;
+      // Make sure that we don't update the same stream twice --- that
+      // would result in swapping the block references back again!
+      if (visitedStreams.GetEntry(stream))
+        continue;
+      visitedStreams.PutEntry(stream);
+      stream->mReadaheadBlocks.NotifyBlockSwapped(aBlockIndex1, aBlockIndex2);
+      stream->mPlayedBlocks.NotifyBlockSwapped(aBlockIndex1, aBlockIndex2);
+      stream->mMetadataBlocks.NotifyBlockSwapped(aBlockIndex1, aBlockIndex2);
+    }
   }
 
   Verify();
 }
 
 void
+nsMediaCache::RemoveBlockOwner(PRInt32 aBlockIndex, nsMediaCacheStream* aStream)
+{
+  Block* block = &mIndex[aBlockIndex];
+  for (PRUint32 i = 0; i < block->mOwners.Length(); ++i) {
+    BlockOwner* bo = &block->mOwners[i];
+    if (bo->mStream == aStream) {
+      GetListForBlock(bo)->RemoveBlock(aBlockIndex);
+      bo->mStream->mBlocks[bo->mStreamBlock] = -1;
+      block->mOwners.RemoveElementAt(i);
+      if (block->mOwners.IsEmpty()) {
+        mFreeBlocks.AddFirstBlock(aBlockIndex);
+      }
+      return;
+    }
+  }
+}
+
+void
 nsMediaCache::FreeBlock(PRInt32 aBlock)
 {
   PR_ASSERT_CURRENT_THREAD_IN_MONITOR(mMonitor);
 
   Block* block = &mIndex[aBlock];
-  GetListForBlock(block)->RemoveBlock(aBlock);
-  if (block->mStream) {
-    block->mStream->mBlocks[block->mStreamBlock] = -1;
+  if (block->mOwners.IsEmpty()) {
+    // already free
+    return;
   }
-  block->mStream = nsnull;
-  block->mClass = FREE_BLOCK;
+
+  LOG(PR_LOG_DEBUG, ("Released block %d", aBlock));
+
+  for (PRUint32 i = 0; i < block->mOwners.Length(); ++i) {
+    BlockOwner* bo = &block->mOwners[i];
+    GetListForBlock(bo)->RemoveBlock(aBlock);
+    bo->mStream->mBlocks[bo->mStreamBlock] = -1;
+  }
+  block->mOwners.Clear();
   mFreeBlocks.AddFirstBlock(aBlock);
   Verify();
 }
 
 TimeDuration
 nsMediaCache::PredictNextUse(TimeStamp aNow, PRInt32 aBlock)
 {
   PR_ASSERT_CURRENT_THREAD_IN_MONITOR(mMonitor);
+  NS_ASSERTION(!IsBlockFree(aBlock), "aBlock is free");
 
   Block* block = &mIndex[aBlock];
-
-  switch (block->mClass) {
-  case METADATA_BLOCK:
-    // This block should be managed in LRU mode. For metadata we predict
-    // that the time until the next use is the time since the last use.
-    return aNow - block->mLastUseTime;
-  case PLAYED_BLOCK:
-    // This block should be managed in LRU mode, and we should impose
-    // a "replay delay" to reflect the likelihood of replay happening
-    NS_ASSERTION(PRInt64(block->mStreamBlock)*BLOCK_SIZE <
-                 block->mStream->mStreamOffset,
-                 "Played block after the current stream position?");
-    return aNow - block->mLastUseTime +
+  // Blocks can be belong to multiple streams. The predicted next use
+  // time is the earliest time predicted by any of the streams.
+  TimeDuration result;
+  for (PRUint32 i = 0; i < block->mOwners.Length(); ++i) {
+    BlockOwner* bo = &block->mOwners[i];
+    TimeDuration prediction;
+    switch (bo->mClass) {
+    case METADATA_BLOCK:
+      // This block should be managed in LRU mode. For metadata we predict
+      // that the time until the next use is the time since the last use.
+      prediction = aNow - bo->mLastUseTime;
+      break;
+    case PLAYED_BLOCK:
+      // This block should be managed in LRU mode, and we should impose
+      // a "replay delay" to reflect the likelihood of replay happening
+      NS_ASSERTION(PRInt64(bo->mStreamBlock)*BLOCK_SIZE <
+                   bo->mStream->mStreamOffset,
+                   "Played block after the current stream position?");
+      prediction = aNow - bo->mLastUseTime +
         TimeDuration::FromSeconds(REPLAY_DELAY);
-  case READAHEAD_BLOCK: {
-    PRInt64 bytesAhead =
-      PRInt64(block->mStreamBlock)*BLOCK_SIZE - block->mStream->mStreamOffset;
-    NS_ASSERTION(bytesAhead >= 0,
-                 "Readahead block before the current stream position?");
-    PRInt64 millisecondsAhead =
-      bytesAhead*1000/block->mStream->mPlaybackBytesPerSecond;
-    return TimeDuration::FromMilliseconds(
-        PR_MIN(millisecondsAhead, PR_INT32_MAX));
+      break;
+    case READAHEAD_BLOCK: {
+      PRInt64 bytesAhead =
+        PRInt64(bo->mStreamBlock)*BLOCK_SIZE - bo->mStream->mStreamOffset;
+      NS_ASSERTION(bytesAhead >= 0,
+                   "Readahead block before the current stream position?");
+      PRInt64 millisecondsAhead =
+        bytesAhead*1000/bo->mStream->mPlaybackBytesPerSecond;
+      prediction = TimeDuration::FromMilliseconds(
+          PR_MIN(millisecondsAhead, PR_INT32_MAX));
+      break;
+    }
+    default:
+      NS_ERROR("Invalid class for predicting next use");
+      return TimeDuration(0);
+    }
+    if (i == 0 || prediction < result) {
+      result = prediction;
+    }
   }
-  default:
-    NS_ERROR("Invalid class for predicting next use");
-    return TimeDuration(0);
-  }
+  return result;
 }
 
 TimeDuration
 nsMediaCache::PredictNextUseForIncomingData(nsMediaCacheStream* aStream)
 {
   PR_ASSERT_CURRENT_THREAD_IN_MONITOR(mMonitor);
 
   PRInt64 bytesAhead = aStream->mChannelOffset - aStream->mStreamOffset;
@@ -895,44 +957,45 @@ nsMediaCache::Update()
   // blocks (by moving an overflowing block to the main part of the cache,
   // and then overwriting it with another overflowing block), and we try
   // to avoid that since it requires HTTP seeks.
   // We also use this loop to eliminate overflowing blocks from
   // freeBlockCount.
   TimeDuration latestPredictedUseForOverflow = 0;
   for (PRInt32 blockIndex = mIndex.Length() - 1; blockIndex >= maxBlocks;
        --blockIndex) {
-    nsMediaCacheStream* stream = mIndex[blockIndex].mStream;
-    if (!stream) {
+    if (IsBlockFree(blockIndex)) {
       // Don't count overflowing free blocks in our free block count
       --freeBlockCount;
       continue;
     }
     TimeDuration predictedUse = PredictNextUse(now, blockIndex);
     latestPredictedUseForOverflow = PR_MAX(latestPredictedUseForOverflow, predictedUse);
   }
 
   // Now try to move overflowing blocks to the main part of the cache.
   for (PRInt32 blockIndex = mIndex.Length() - 1; blockIndex >= maxBlocks;
        --blockIndex) {
-    Block* block = &mIndex[blockIndex];
-    nsMediaCacheStream* stream = block->mStream;
-    if (!stream)
+    if (IsBlockFree(blockIndex))
       continue;
 
+    Block* block = &mIndex[blockIndex];
+    // Try to relocate the block close to other blocks for the first stream.
+    // There is no point in trying ot make it close to other blocks in
+    // *all* the streams it might belong to.
     PRInt32 destinationBlockIndex =
-      FindReusableBlock(now, stream, block->mStreamBlock, maxBlocks);
+      FindReusableBlock(now, block->mOwners[0].mStream,
+                        block->mOwners[0].mStreamBlock, maxBlocks);
     if (destinationBlockIndex < 0) {
       // Nowhere to place this overflow block. We won't be able to
       // place any more overflow blocks.
       break;
     }
 
-    Block* destinationBlock = &mIndex[destinationBlockIndex];
-    if (destinationBlock->mClass == FREE_BLOCK ||
+    if (IsBlockFree(destinationBlockIndex) ||
         PredictNextUse(now, destinationBlockIndex) > latestPredictedUseForOverflow) {
       // Reuse blocks in the main part of the cache that are less useful than
       // the least useful overflow blocks
       char buf[BLOCK_SIZE];
       nsresult rv = ReadCacheFileAllBytes(blockIndex*BLOCK_SIZE, buf, sizeof(buf));
       if (NS_SUCCEEDED(rv)) {
         rv = WriteCacheFile(destinationBlockIndex*BLOCK_SIZE, buf, BLOCK_SIZE);
         if (NS_SUCCEEDED(rv)) {
@@ -940,29 +1003,24 @@ nsMediaCache::Update()
           LOG(PR_LOG_DEBUG, ("Swapping blocks %d and %d (trimming cache)",
               blockIndex, destinationBlockIndex));
           // Swapping the block metadata here lets us maintain the
           // correct positions in the linked lists
           SwapBlocks(blockIndex, destinationBlockIndex);
         } else {
           // If the write fails we may have corrupted the destination
           // block. Free it now.
-          LOG(PR_LOG_DEBUG, ("Released block %d from stream %p block %d(%lld) (trimming cache)",
-              destinationBlockIndex, destinationBlock->mStream,
-              destinationBlock->mStreamBlock,
-              (long long)destinationBlock->mStreamBlock*BLOCK_SIZE));
+          LOG(PR_LOG_DEBUG, ("Released block %d (trimming cache)",
+              destinationBlockIndex));
           FreeBlock(destinationBlockIndex);
         }
         // Free the overflowing block even if the copy failed.
-        if (block->mClass != FREE_BLOCK) {
-          LOG(PR_LOG_DEBUG, ("Released block %d from stream %p block %d(%lld) (trimming cache)",
-              blockIndex, block->mStream, block->mStreamBlock,
-              (long long)block->mStreamBlock*BLOCK_SIZE));
-          FreeBlock(blockIndex);
-        }
+        LOG(PR_LOG_DEBUG, ("Released block %d (trimming cache)",
+            blockIndex));
+        FreeBlock(blockIndex);
       }
     }
   }
   // Try chopping back the array of cache entries and the cache file.
   Truncate();
 
   // Count the blocks allocated for readahead of non-seekable streams
   // (these blocks can't be freed but we don't want them to monopolize the
@@ -1140,116 +1198,117 @@ nsMediaCache::QueueUpdate()
 
 #ifdef DEBUG_VERIFY_CACHE
 void
 nsMediaCache::Verify()
 {
   PR_ASSERT_CURRENT_THREAD_IN_MONITOR(mMonitor);
 
   mFreeBlocks.Verify();
-  mPlayedBlocks.Verify();
-  mMetadataBlocks.Verify();
   for (PRUint32 i = 0; i < mStreams.Length(); ++i) {
     nsMediaCacheStream* stream = mStreams[i];
     stream->mReadaheadBlocks.Verify();
-    if (!stream->mReadaheadBlocks.IsEmpty()) {
-      // Verify that the readahead blocks are listed in stream block order
-      PRInt32 block = stream->mReadaheadBlocks.GetFirstBlock();
-      PRInt32 lastStreamBlock = -1;
-      do {
-        NS_ASSERTION(mIndex[block].mStream == stream, "Bad stream");
-        NS_ASSERTION(lastStreamBlock < PRInt32(mIndex[block].mStreamBlock),
-                     "Blocks not increasing in readahead stream");
-        lastStreamBlock = PRInt32(mIndex[block].mStreamBlock);
-        block = stream->mReadaheadBlocks.GetNextBlock(block);
-      } while (block >= 0);
+    stream->mPlayedBlocks.Verify();
+    stream->mMetadataBlocks.Verify();
+
+    // Verify that the readahead blocks are listed in stream block order
+    PRInt32 block = stream->mReadaheadBlocks.GetFirstBlock();
+    PRInt32 lastStreamBlock = -1;
+    while (block >= 0) {
+      PRUint32 j = 0;
+      while (mIndex[block].mOwners[j].mStream != stream) {
+        ++j;
+      }
+      PRInt32 nextStreamBlock =
+        PRInt32(mIndex[block].mOwners[j].mStreamBlock);
+      NS_ASSERTION(lastStreamBlock < nextStreamBlock,
+                   "Blocks not increasing in readahead stream");
+      lastStreamBlock = nextStreamBlock;
+      block = stream->mReadaheadBlocks.GetNextBlock(block);
     }
   }
 }
 #endif
 
 void
-nsMediaCache::InsertReadaheadBlock(PRInt32 aBlockIndex)
+nsMediaCache::InsertReadaheadBlock(BlockOwner* aBlockOwner,
+                                   PRInt32 aBlockIndex)
 {
   PR_ASSERT_CURRENT_THREAD_IN_MONITOR(mMonitor);
 
-  Block* block = &mIndex[aBlockIndex];
-  nsMediaCacheStream* stream = block->mStream;
-  if (stream->mReadaheadBlocks.IsEmpty()) {
-    stream->mReadaheadBlocks.AddFirstBlock(aBlockIndex);
-    return;
-  }
-
   // Find the last block whose stream block is before aBlockIndex's
   // stream block, and insert after it
+  nsMediaCacheStream* stream = aBlockOwner->mStream;
   PRInt32 readaheadIndex = stream->mReadaheadBlocks.GetLastBlock();
-  do {
-    if (mIndex[readaheadIndex].mStreamBlock < block->mStreamBlock) {
+  while (readaheadIndex >= 0) {
+    BlockOwner* bo = GetBlockOwner(readaheadIndex, stream);
+    NS_ASSERTION(bo, "stream must own its blocks");
+    if (bo->mStreamBlock < aBlockOwner->mStreamBlock) {
       stream->mReadaheadBlocks.AddAfter(aBlockIndex, readaheadIndex);
       return;
     }
-    NS_ASSERTION(mIndex[readaheadIndex].mStreamBlock > block->mStreamBlock,
+    NS_ASSERTION(bo->mStreamBlock > aBlockOwner->mStreamBlock,
                  "Duplicated blocks??");
     readaheadIndex = stream->mReadaheadBlocks.GetPrevBlock(readaheadIndex);
-  } while (readaheadIndex >= 0);
+  }
+
   stream->mReadaheadBlocks.AddFirstBlock(aBlockIndex);
   Verify();
 }
 
 void
 nsMediaCache::AllocateAndWriteBlock(nsMediaCacheStream* aStream, const void* aData,
                                     nsMediaCacheStream::ReadMode aMode)
 {
   PR_ASSERT_CURRENT_THREAD_IN_MONITOR(mMonitor);
 
   PRInt32 streamBlockIndex = aStream->mChannelOffset/BLOCK_SIZE;
   // Extend the mBlocks array as necessary
   while (streamBlockIndex >= PRInt32(aStream->mBlocks.Length())) {
     aStream->mBlocks.AppendElement(-1);
   }
   if (aStream->mBlocks[streamBlockIndex] >= 0) {
-    // Release the existing cache entry for this stream block
+    // We no longer want to own this block
     PRInt32 globalBlockIndex = aStream->mBlocks[streamBlockIndex];
     LOG(PR_LOG_DEBUG, ("Released block %d from stream %p block %d(%lld)",
         globalBlockIndex, aStream, streamBlockIndex, (long long)streamBlockIndex*BLOCK_SIZE));
-    FreeBlock(globalBlockIndex);
+    RemoveBlockOwner(globalBlockIndex, aStream);
   }
 
   TimeStamp now = TimeStamp::Now();
   PRInt32 blockIndex = FindBlockForIncomingData(now, aStream);
   if (blockIndex >= 0) {
-    Block* block = &mIndex[blockIndex];
-    if (block->mClass != FREE_BLOCK) {
-      LOG(PR_LOG_DEBUG, ("Released block %d from stream %p block %d(%lld)",
-          blockIndex, block->mStream, block->mStreamBlock, (long long)block->mStreamBlock*BLOCK_SIZE));
-      FreeBlock(blockIndex);
-    }
-    NS_ASSERTION(block->mClass == FREE_BLOCK, "Block should be free now!");
+    FreeBlock(blockIndex);
 
+    Block* block = &mIndex[blockIndex];    
     LOG(PR_LOG_DEBUG, ("Allocated block %d to stream %p block %d(%lld)",
         blockIndex, aStream, streamBlockIndex, (long long)streamBlockIndex*BLOCK_SIZE));
-    block->mStream = aStream;
-    block->mStreamBlock = streamBlockIndex;
-    block->mLastUseTime = now;
+    BlockOwner* bo = block->mOwners.AppendElement();
+    if (!bo)
+      return;
+
+    bo->mStream = aStream;
+    bo->mStreamBlock = streamBlockIndex;
+    bo->mLastUseTime = now;
     aStream->mBlocks[streamBlockIndex] = blockIndex;
     mFreeBlocks.RemoveBlock(blockIndex);
     if (streamBlockIndex*BLOCK_SIZE < aStream->mStreamOffset) {
-      block->mClass = aMode == nsMediaCacheStream::MODE_PLAYBACK
+      bo->mClass = aMode == nsMediaCacheStream::MODE_PLAYBACK
         ? PLAYED_BLOCK : METADATA_BLOCK;
       // This must be the most-recently-used block, since we
       // marked it as used now (which may be slightly bogus, but we'll
       // treat it as used for simplicity).
-      GetListForBlock(block)->AddFirstBlock(blockIndex);
+      GetListForBlock(bo)->AddFirstBlock(blockIndex);
       Verify();
     } else {
       // This may not be the latest readahead block, although it usually
       // will be. We may have to scan for the right place to insert
       // the block in the list.
-      block->mClass = READAHEAD_BLOCK;
-      InsertReadaheadBlock(blockIndex);
+      bo->mClass = READAHEAD_BLOCK;
+      InsertReadaheadBlock(bo, blockIndex);
     }
 
     nsresult rv = WriteCacheFile(blockIndex*BLOCK_SIZE, aData, BLOCK_SIZE);
     if (NS_FAILED(rv)) {
       LOG(PR_LOG_DEBUG, ("Released block %d from stream %p block %d(%lld)",
           blockIndex, aStream, streamBlockIndex, (long long)streamBlockIndex*BLOCK_SIZE));
       FreeBlock(blockIndex);
     }
@@ -1287,71 +1346,71 @@ nsMediaCache::ReleaseStreamBlocks(nsMedi
   // is cached, but the only easy alternative is to scan the entire cache
   // which isn't better
   PRUint32 length = aStream->mBlocks.Length();
   for (PRUint32 i = 0; i < length; ++i) {
     PRInt32 blockIndex = aStream->mBlocks[i];
     if (blockIndex >= 0) {
       LOG(PR_LOG_DEBUG, ("Released block %d from stream %p block %d(%lld)",
           blockIndex, aStream, i, (long long)i*BLOCK_SIZE));
-      FreeBlock(blockIndex);
+      RemoveBlockOwner(blockIndex, aStream);
     }
   }
 }
 
 void
 nsMediaCache::Truncate()
 {
   PRUint32 end;
   for (end = mIndex.Length(); end > 0; --end) {
-    if (mIndex[end - 1].mStream)
+    if (!IsBlockFree(end - 1))
       break;
     mFreeBlocks.RemoveBlock(end - 1);
   }
 
   if (end < mIndex.Length()) {
     mIndex.TruncateLength(end);
     // XXX We could truncate the cache file here, but we don't seem
     // to have a cross-platform API for doing that. At least when all
     // streams are closed we shut down the cache, which erases the
     // file at that point.
   }
 }
 
 void
-nsMediaCache::NoteBlockUsage(PRInt32 aBlockIndex,
+nsMediaCache::NoteBlockUsage(nsMediaCacheStream* aStream, PRInt32 aBlockIndex,
                              nsMediaCacheStream::ReadMode aMode,
                              TimeStamp aNow)
 {
   PR_ASSERT_CURRENT_THREAD_IN_MONITOR(mMonitor);
 
   if (aBlockIndex < 0) {
     // this block is not in the cache yet
     return;
   }
 
-  Block* block = &mIndex[aBlockIndex];
-  if (block->mClass == FREE_BLOCK) {
+  BlockOwner* bo = GetBlockOwner(aBlockIndex, aStream);
+  if (!bo) {
     // this block is not in the cache yet
     return;
   }
 
   // The following check has to be <= because the stream offset has
   // not yet been updated for the data read from this block
-  NS_ASSERTION(block->mStreamBlock*BLOCK_SIZE <= block->mStream->mStreamOffset,
+  NS_ASSERTION(bo->mStreamBlock*BLOCK_SIZE <= bo->mStream->mStreamOffset,
                "Using a block that's behind the read position?");
 
-  GetListForBlock(block)->RemoveBlock(aBlockIndex);
-  block->mClass =
-    (aMode == nsMediaCacheStream::MODE_METADATA || block->mClass == METADATA_BLOCK)
+  GetListForBlock(bo)->RemoveBlock(aBlockIndex);
+  bo->mClass =
+    (aMode == nsMediaCacheStream::MODE_METADATA || bo->mClass == METADATA_BLOCK)
     ? METADATA_BLOCK : PLAYED_BLOCK;
   // Since this is just being used now, it can definitely be at the front
   // of mMetadataBlocks or mPlayedBlocks
-  GetListForBlock(block)->AddFirstBlock(aBlockIndex);
-  block->mLastUseTime = aNow;
+  GetListForBlock(bo)->AddFirstBlock(aBlockIndex);
+  bo->mLastUseTime = aNow;
   Verify();
 }
 
 void
 nsMediaCache::NoteSeek(nsMediaCacheStream* aStream, PRInt64 aOldOffset)
 {
   PR_ASSERT_CURRENT_THREAD_IN_MONITOR(mMonitor);
 
@@ -1364,42 +1423,43 @@ nsMediaCache::NoteSeek(nsMediaCacheStrea
       PR_MIN((aStream->mStreamOffset + BLOCK_SIZE - 1)/BLOCK_SIZE,
              aStream->mBlocks.Length());
     TimeStamp now = TimeStamp::Now();
     while (blockIndex < endIndex) {
       PRInt32 cacheBlockIndex = aStream->mBlocks[blockIndex];
       if (cacheBlockIndex >= 0) {
         // Marking the block used may not be exactly what we want but
         // it's simple
-        NoteBlockUsage(cacheBlockIndex, nsMediaCacheStream::MODE_PLAYBACK,
+        NoteBlockUsage(aStream, cacheBlockIndex, nsMediaCacheStream::MODE_PLAYBACK,
                        now);
       }
       ++blockIndex;
     }
   } else {
     // We seeked backward. Convert from played to readahead.
     // Any played block that is entirely after the start of the seeked-over
     // range must be converted.
     PRInt32 blockIndex =
       (aStream->mStreamOffset + BLOCK_SIZE - 1)/BLOCK_SIZE;
     PRInt32 endIndex =
       PR_MIN((aOldOffset + BLOCK_SIZE - 1)/BLOCK_SIZE,
              aStream->mBlocks.Length());
     while (blockIndex < endIndex) {
       PRInt32 cacheBlockIndex = aStream->mBlocks[endIndex - 1];
       if (cacheBlockIndex >= 0) {
-        Block* block = &mIndex[cacheBlockIndex];
-        if (block->mClass != METADATA_BLOCK) {
-          mPlayedBlocks.RemoveBlock(cacheBlockIndex);
-          block->mClass = READAHEAD_BLOCK;
+        BlockOwner* bo = GetBlockOwner(cacheBlockIndex, aStream);
+        NS_ASSERTION(bo, "Stream doesn't own its blocks?");
+        if (bo->mClass == PLAYED_BLOCK) {
+          aStream->mPlayedBlocks.RemoveBlock(cacheBlockIndex);
+          bo->mClass = READAHEAD_BLOCK;
           // Adding this as the first block is sure to be OK since
           // this must currently be the earliest readahead block
           // (that's why we're proceeding backwards from the end of
           // the seeked range to the start)
-          GetListForBlock(block)->AddFirstBlock(cacheBlockIndex);
+          aStream->mReadaheadBlocks.AddFirstBlock(cacheBlockIndex);
           Verify();
         }
       }
       --endIndex;
     }
   }
 }
 
@@ -1826,17 +1886,17 @@ nsMediaCacheStream::Read(char* aBuffer, 
       // use it rather than waiting for the block to fill and land in
       // the cache.
       bytes = PR_MIN(size, mChannelOffset - mStreamOffset);
       memcpy(aBuffer + count,
         reinterpret_cast<char*>(mPartialBlockBuffer) + offsetInStreamBlock, bytes);
       if (mCurrentMode == MODE_METADATA) {
         mMetadataInPartialBlockBuffer = PR_TRUE;
       }
-      gMediaCache->NoteBlockUsage(cacheBlock, mCurrentMode, TimeStamp::Now());
+      gMediaCache->NoteBlockUsage(this, cacheBlock, mCurrentMode, TimeStamp::Now());
     } else {
       if (cacheBlock < 0) {
         if (count > 0) {
           // Some data has been read, so return what we've got instead of
           // blocking
           break;
         }
 
@@ -1845,17 +1905,17 @@ nsMediaCacheStream::Read(char* aBuffer, 
         if (mClosed) {
           // We may have successfully read some data, but let's just throw
           // that out.
           return NS_ERROR_FAILURE;
         }
         continue;
       }
 
-      gMediaCache->NoteBlockUsage(cacheBlock, mCurrentMode, TimeStamp::Now());
+      gMediaCache->NoteBlockUsage(this, cacheBlock, mCurrentMode, TimeStamp::Now());
 
       PRInt64 offset = cacheBlock*BLOCK_SIZE + offsetInStreamBlock;
       nsresult rv = gMediaCache->ReadCacheFile(offset, aBuffer + count, size, &bytes);
       if (NS_FAILED(rv)) {
         if (count == 0)
           return rv;
         // If we did successfully read some data, may as well return it
         break;
--- a/content/media/nsMediaCache.h
+++ b/content/media/nsMediaCache.h
@@ -431,16 +431,20 @@ private:
   PRInt64           mStreamLength;
   // For each block in the stream data, maps to the cache entry for the
   // block, or -1 if the block is not cached.
   nsTArray<PRInt32> mBlocks;
   // The list of read-ahead blocks, ordered by stream offset; the first
   // block is the earliest in the stream (so the last block will be the
   // least valuable).
   BlockList         mReadaheadBlocks;
+  // The list of metadata blocks; the first block is the most recently used
+  BlockList         mMetadataBlocks;
+  // The list of played-back blocks; the first block is the most recently used
+  BlockList         mPlayedBlocks;
   // The last reported estimate of the decoder's playback rate
   PRUint32          mPlaybackBytesPerSecond;
   // The number of times this stream has been Pinned without a
   // corresponding Unpin
   PRUint32          mPinCount;
   // The last reported read mode
   ReadMode          mCurrentMode;
   // Set to true when the stream has been closed either explicitly or