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 idunknown
push userunknown
push dateunknown
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