Bug 923016 - Implementation of cache index, r=honzab
☠☠ backed out by ce0ac2767d13 ☠ ☠
authorMichal Novotny <michal.novotny@gmail.com>
Tue, 18 Feb 2014 16:05:07 +0100
changeset 189250 f514ab5c4b5bdb365af0fa83f65e5943dab1b958
parent 189249 615c92a6708909eecd7a9cdcf81900f2437baf66
child 189251 d8543551f12eb0f98b348a1b2ea5a21aa12b8bfe
push idunknown
push userunknown
push dateunknown
reviewershonzab
bugs923016
milestone30.0a1
Bug 923016 - Implementation of cache index, r=honzab
netwerk/cache2/CacheFile.cpp
netwerk/cache2/CacheFile.h
netwerk/cache2/CacheFileChunk.cpp
netwerk/cache2/CacheFileChunk.h
netwerk/cache2/CacheFileIOManager.cpp
netwerk/cache2/CacheFileIOManager.h
netwerk/cache2/CacheFileMetadata.cpp
netwerk/cache2/CacheFileMetadata.h
netwerk/cache2/CacheHashUtils.cpp
netwerk/cache2/CacheHashUtils.h
netwerk/cache2/CacheIOThread.h
netwerk/cache2/CacheIndex.cpp
netwerk/cache2/CacheIndex.h
netwerk/cache2/CacheStorageService.cpp
netwerk/cache2/moz.build
netwerk/cache2/nsICacheEntry.idl
--- a/netwerk/cache2/CacheFile.cpp
+++ b/netwerk/cache2/CacheFile.cpp
@@ -3,16 +3,17 @@
  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
 
 #include "CacheLog.h"
 #include "CacheFile.h"
 
 #include "CacheFileChunk.h"
 #include "CacheFileInputStream.h"
 #include "CacheFileOutputStream.h"
+#include "CacheIndex.h"
 #include "nsThreadUtils.h"
 #include "mozilla/DebugOnly.h"
 #include <algorithm>
 #include "nsComponentManagerUtils.h"
 #include "nsProxyRelease.h"
 
 namespace mozilla {
 namespace net {
@@ -130,16 +131,22 @@ public:
   }
 
   NS_IMETHOD OnEOFSet(CacheFileHandle *aHandle, nsresult aResult)
   {
     MOZ_CRASH("DoomFileHelper::OnEOFSet should not be called!");
     return NS_ERROR_UNEXPECTED;
   }
 
+  NS_IMETHOD OnFileRenamed(CacheFileHandle *aHandle, nsresult aResult)
+  {
+    MOZ_CRASH("DoomFileHelper::OnFileRenamed should not be called!");
+    return NS_ERROR_UNEXPECTED;
+  }
+
 private:
   virtual ~DoomFileHelper()
   {
     MOZ_COUNT_DTOR(DoomFileHelper);
   }
 
   nsCOMPtr<CacheFileListener>  mListener;
 };
@@ -221,19 +228,46 @@ CacheFile::Init(const nsACString &aKey,
       flags = CacheFileIOManager::CREATE_NEW;
 
       // make sure we can use this entry immediately
       MOZ_ASSERT(!mKeyIsHash);
       mMetadata = new CacheFileMetadata(mKey);
       mReady = true;
       mDataSize = mMetadata->Offset();
     }
-    else
+    else {
       flags = CacheFileIOManager::CREATE;
 
+      if (!mKeyIsHash) {
+        // Have a look into index and change to CREATE_NEW when we are sure
+        // that the entry does not exist.
+        CacheIndex::EntryStatus status;
+        rv = CacheIndex::HasEntry(mKey, &status);
+        if (status == CacheIndex::DOES_NOT_EXIST) {
+          LOG(("CacheFile::Init() - Forcing CREATE_NEW flag since we don't have"
+               " this entry according to index"));
+          flags = CacheFileIOManager::CREATE_NEW;
+
+          // make sure we can use this entry immediately
+          mMetadata = new CacheFileMetadata(mKey);
+          mReady = true;
+          mDataSize = mMetadata->Offset();
+
+          // Notify callback now and don't store it in mListener, no further
+          // operation can change the result.
+          nsRefPtr<NotifyCacheFileListenerEvent> ev;
+          ev = new NotifyCacheFileListenerEvent(aCallback, NS_OK, true);
+          rv = NS_DispatchToCurrentThread(ev);
+          NS_ENSURE_SUCCESS(rv, rv);
+
+          aCallback = nullptr;
+        }
+      }
+    }
+
     if (aPriority)
       flags |= CacheFileIOManager::PRIORITY;
     if (aKeyIsHash)
       flags |= CacheFileIOManager::NOHASH;
 
     mOpeningFile = true;
     mListener = aCallback;
     rv = CacheFileIOManager::OpenFile(mKey, flags, this);
@@ -469,20 +503,22 @@ CacheFile::OnFileOpened(CacheFileHandle 
       }
 
       mListener.swap(listener);
     }
     else {
       mHandle = aHandle;
 
       if (mMetadata) {
+        InitIndexEntry();
+
         // The entry was initialized as createNew, don't try to read metadata.
         mMetadata->SetHandle(mHandle);
 
-        // Write all cached chunks, otherwise thay may stay unwritten.
+        // Write all cached chunks, otherwise they may stay unwritten.
         mCachedChunks.Enumerate(&CacheFile::WriteAllCachedChunks, this);
 
         return NS_OK;
       }
     }
   }
 
   if (listener) {
@@ -537,16 +573,18 @@ CacheFile::OnMetadataRead(nsresult aResu
     }
 
     mReady = true;
     mDataSize = mMetadata->Offset();
     if (mDataSize == 0 && mMetadata->ElementsSize() == 0) {
       isNew = true;
       mMetadata->MarkDirty();
     }
+
+    InitIndexEntry();
   }
 
   nsCOMPtr<CacheFileListener> listener;
   mListener.swap(listener);
   listener->OnFileReady(aResult, isNew);
   return NS_OK;
 }
 
@@ -605,16 +643,23 @@ CacheFile::OnFileDoomed(CacheFileHandle 
 nsresult
 CacheFile::OnEOFSet(CacheFileHandle *aHandle, nsresult aResult)
 {
   MOZ_CRASH("CacheFile::OnEOFSet should not be called!");
   return NS_ERROR_UNEXPECTED;
 }
 
 nsresult
+CacheFile::OnFileRenamed(CacheFileHandle *aHandle, nsresult aResult)
+{
+  MOZ_CRASH("CacheFile::OnFileRenamed should not be called!");
+  return NS_ERROR_UNEXPECTED;
+}
+
+nsresult
 CacheFile::OpenInputStream(nsIInputStream **_retval)
 {
   CacheFileAutoLock lock(this);
 
   MOZ_ASSERT(mHandle || mMemoryOnly || mOpeningFile);
 
   if (!mReady) {
     LOG(("CacheFile::OpenInputStream() - CacheFile is not ready [this=%p]",
@@ -781,16 +826,20 @@ CacheFile::ElementsSize(uint32_t *_retva
 nsresult
 CacheFile::SetExpirationTime(uint32_t aExpirationTime)
 {
   CacheFileAutoLock lock(this);
   MOZ_ASSERT(mMetadata);
   NS_ENSURE_TRUE(mMetadata, NS_ERROR_UNEXPECTED);
 
   PostWriteTimer();
+
+  if (mHandle && !mHandle->IsDoomed())
+    CacheFileIOManager::UpdateIndexEntry(mHandle, nullptr, &aExpirationTime);
+
   return mMetadata->SetExpirationTime(aExpirationTime);
 }
 
 nsresult
 CacheFile::GetExpirationTime(uint32_t *_retval)
 {
   CacheFileAutoLock lock(this);
   MOZ_ASSERT(mMetadata);
@@ -823,16 +872,20 @@ CacheFile::GetLastModified(uint32_t *_re
 nsresult
 CacheFile::SetFrecency(uint32_t aFrecency)
 {
   CacheFileAutoLock lock(this);
   MOZ_ASSERT(mMetadata);
   NS_ENSURE_TRUE(mMetadata, NS_ERROR_UNEXPECTED);
 
   PostWriteTimer();
+
+  if (mHandle && !mHandle->IsDoomed())
+    CacheFileIOManager::UpdateIndexEntry(mHandle, &aFrecency, nullptr);
+
   return mMetadata->SetFrecency(aFrecency);
 }
 
 nsresult
 CacheFile::GetFrecency(uint32_t *_retval)
 {
   CacheFileAutoLock lock(this);
   MOZ_ASSERT(mMetadata);
@@ -1472,10 +1525,38 @@ CacheFile::PadChunkWithZeroes(uint32_t a
   chunk->UpdateDataSize(chunk->DataSize(), kChunkSize - chunk->DataSize(),
                         false);
 
   ReleaseOutsideLock(chunk.forget().get());
 
   return NS_OK;
 }
 
+nsresult
+CacheFile::InitIndexEntry()
+{
+  MOZ_ASSERT(mHandle);
+
+  if (mHandle->IsDoomed())
+    return NS_OK;
+
+  nsresult rv;
+
+  rv = CacheFileIOManager::InitIndexEntry(mHandle,
+                                          mMetadata->AppId(),
+                                          mMetadata->IsAnonymous(),
+                                          mMetadata->IsInBrowser());
+  NS_ENSURE_SUCCESS(rv, rv);
+
+  uint32_t expTime;
+  mMetadata->GetExpirationTime(&expTime);
+
+  uint32_t frecency;
+  mMetadata->GetFrecency(&frecency);
+
+  rv = CacheFileIOManager::UpdateIndexEntry(mHandle, &frecency, &expTime);
+  NS_ENSURE_SUCCESS(rv, rv);
+
+  return NS_OK;
+}
+
 } // net
 } // mozilla
--- a/netwerk/cache2/CacheFile.h
+++ b/netwerk/cache2/CacheFile.h
@@ -66,16 +66,17 @@ public:
   NS_IMETHOD OnChunkUpdated(CacheFileChunk *aChunk);
 
   NS_IMETHOD OnFileOpened(CacheFileHandle *aHandle, nsresult aResult);
   NS_IMETHOD OnDataWritten(CacheFileHandle *aHandle, const char *aBuf,
                            nsresult aResult);
   NS_IMETHOD OnDataRead(CacheFileHandle *aHandle, char *aBuf, nsresult aResult);
   NS_IMETHOD OnFileDoomed(CacheFileHandle *aHandle, nsresult aResult);
   NS_IMETHOD OnEOFSet(CacheFileHandle *aHandle, nsresult aResult);
+  NS_IMETHOD OnFileRenamed(CacheFileHandle *aHandle, nsresult aResult);
 
   NS_IMETHOD OnMetadataRead(nsresult aResult);
   NS_IMETHOD OnMetadataWritten(nsresult aResult);
 
   NS_IMETHOD OpenInputStream(nsIInputStream **_retval);
   NS_IMETHOD OpenOutputStream(CacheOutputCloseListener *aCloseListener, nsIOutputStream **_retval);
   NS_IMETHOD SetMemoryOnly();
   NS_IMETHOD Doom(CacheFileListener *aCallback);
@@ -150,16 +151,18 @@ private:
                            void* aClosure);
 
   static PLDHashOperator FailUpdateListeners(const uint32_t& aIdx,
                                              nsRefPtr<CacheFileChunk>& aChunk,
                                              void* aClosure);
 
   nsresult PadChunkWithZeroes(uint32_t aChunkIdx);
 
+  nsresult InitIndexEntry();
+
   mozilla::Mutex mLock;
   bool           mOpeningFile;
   bool           mReady;
   bool           mMemoryOnly;
   bool           mDataAccessed;
   bool           mDataIsDirty;
   bool           mWritingMetadata;
   bool           mKeyIsHash;
--- a/netwerk/cache2/CacheFileChunk.cpp
+++ b/netwerk/cache2/CacheFileChunk.cpp
@@ -177,17 +177,17 @@ CacheFileChunk::InitNew(CacheFileChunkLi
   mState = READY;
   mIsDirty = true;
 
   DoMemoryReport(MemorySize());
 }
 
 nsresult
 CacheFileChunk::Read(CacheFileHandle *aHandle, uint32_t aLen,
-                     CacheHashUtils::Hash16_t aHash,
+                     CacheHash::Hash16_t aHash,
                      CacheFileChunkListener *aCallback)
 {
   mFile->AssertOwnsLock();
 
   LOG(("CacheFileChunk::Read() [this=%p, handle=%p, len=%d, listener=%p]",
        this, aHandle, aLen, aCallback));
 
   MOZ_ASSERT(mState == INITIAL);
@@ -337,26 +337,26 @@ CacheFileChunk::NotifyUpdateListeners()
 }
 
 uint32_t
 CacheFileChunk::Index()
 {
   return mIndex;
 }
 
-CacheHashUtils::Hash16_t
+CacheHash::Hash16_t
 CacheFileChunk::Hash()
 {
   mFile->AssertOwnsLock();
 
   MOZ_ASSERT(mBuf);
   MOZ_ASSERT(!mListener);
   MOZ_ASSERT(IsReady());
 
-  return CacheHashUtils::Hash16(BufForReading(), mDataSize);
+  return CacheHash::Hash16(BufForReading(), mDataSize);
 }
 
 uint32_t
 CacheFileChunk::DataSize()
 {
   mFile->AssertOwnsLock();
   return mDataSize;
 }
@@ -512,18 +512,17 @@ CacheFileChunk::OnDataRead(CacheFileHand
 
   {
     CacheFileAutoLock lock(mFile);
 
     MOZ_ASSERT(mState == READING);
     MOZ_ASSERT(mListener);
 
     if (NS_SUCCEEDED(aResult)) {
-      CacheHashUtils::Hash16_t hash = CacheHashUtils::Hash16(mRWBuf,
-                                                             mRWBufSize);
+      CacheHash::Hash16_t hash = CacheHash::Hash16(mRWBuf, mRWBufSize);
       if (hash != mReadHash) {
         LOG(("CacheFileChunk::OnDataRead() - Hash mismatch! Hash of the data is"
              " %hx, hash in metadata is %hx. [this=%p, idx=%d]",
              hash, mReadHash, this, mIndex));
         aResult = NS_ERROR_FILE_CORRUPTED;
       }
       else {
         if (!mBuf) {
@@ -585,16 +584,23 @@ CacheFileChunk::OnFileDoomed(CacheFileHa
 
 nsresult
 CacheFileChunk::OnEOFSet(CacheFileHandle *aHandle, nsresult aResult)
 {
   MOZ_CRASH("CacheFileChunk::OnEOFSet should not be called!");
   return NS_ERROR_UNEXPECTED;
 }
 
+nsresult
+CacheFileChunk::OnFileRenamed(CacheFileHandle *aHandle, nsresult aResult)
+{
+  MOZ_CRASH("CacheFileChunk::OnFileRenamed should not be called!");
+  return NS_ERROR_UNEXPECTED;
+}
+
 bool
 CacheFileChunk::IsReady()
 {
   mFile->AssertOwnsLock();
 
   return (mState == READY || mState == WRITING);
 }
 
--- a/netwerk/cache2/CacheFileChunk.h
+++ b/netwerk/cache2/CacheFileChunk.h
@@ -68,35 +68,36 @@ class CacheFileChunk : public CacheFileI
 {
 public:
   NS_DECL_THREADSAFE_ISUPPORTS
 
   CacheFileChunk(CacheFile *aFile, uint32_t aIndex);
 
   void     InitNew(CacheFileChunkListener *aCallback);
   nsresult Read(CacheFileHandle *aHandle, uint32_t aLen,
-                CacheHashUtils::Hash16_t aHash,
+                CacheHash::Hash16_t aHash,
                 CacheFileChunkListener *aCallback);
   nsresult Write(CacheFileHandle *aHandle, CacheFileChunkListener *aCallback);
   void     WaitForUpdate(CacheFileChunkListener *aCallback);
   nsresult CancelWait(CacheFileChunkListener *aCallback);
   nsresult NotifyUpdateListeners();
 
-  uint32_t                 Index();
-  CacheHashUtils::Hash16_t Hash();
-  uint32_t                 DataSize();
-  void                     UpdateDataSize(uint32_t aOffset, uint32_t aLen,
-                                          bool aEOF);
+  uint32_t            Index();
+  CacheHash::Hash16_t Hash();
+  uint32_t            DataSize();
+  void                UpdateDataSize(uint32_t aOffset, uint32_t aLen,
+                                     bool aEOF);
 
   NS_IMETHOD OnFileOpened(CacheFileHandle *aHandle, nsresult aResult);
   NS_IMETHOD OnDataWritten(CacheFileHandle *aHandle, const char *aBuf,
                            nsresult aResult);
   NS_IMETHOD OnDataRead(CacheFileHandle *aHandle, char *aBuf, nsresult aResult);
   NS_IMETHOD OnFileDoomed(CacheFileHandle *aHandle, nsresult aResult);
   NS_IMETHOD OnEOFSet(CacheFileHandle *aHandle, nsresult aResult);
+  NS_IMETHOD OnFileRenamed(CacheFileHandle *aHandle, nsresult aResult);
 
   bool   IsReady();
   bool   IsDirty();
 
   char *       BufForWriting();
   const char * BufForReading();
   void         EnsureBufSize(uint32_t aBufSize);
   uint32_t     MemorySize() { return mRWBufSize + mBufSize; }
@@ -120,19 +121,19 @@ private:
   EState   mState;
   bool     mIsDirty;
   bool     mRemovingChunk;
   uint32_t mDataSize;
 
   char    *mBuf;
   uint32_t mBufSize;
 
-  char                    *mRWBuf;
-  uint32_t                 mRWBufSize;
-  CacheHashUtils::Hash16_t mReadHash;
+  char               *mRWBuf;
+  uint32_t            mRWBufSize;
+  CacheHash::Hash16_t mReadHash;
 
   nsRefPtr<CacheFile>              mFile; // is null if chunk is cached to
                                           // prevent reference cycles
   nsCOMPtr<CacheFileChunkListener> mListener;
   nsTArray<ChunkListenerItem *>    mUpdateListeners;
   nsTArray<ValidityPair>           mValidityMap;
 };
 
--- a/netwerk/cache2/CacheFileIOManager.cpp
+++ b/netwerk/cache2/CacheFileIOManager.cpp
@@ -3,16 +3,17 @@
  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
 
 #include "CacheLog.h"
 #include "CacheFileIOManager.h"
 
 #include "../cache/nsCacheUtils.h"
 #include "CacheHashUtils.h"
 #include "CacheStorageService.h"
+#include "CacheIndex.h"
 #include "nsThreadUtils.h"
 #include "CacheFile.h"
 #include "nsIFile.h"
 #include "mozilla/Telemetry.h"
 #include "mozilla/DebugOnly.h"
 #include "nsDirectoryServiceUtils.h"
 #include "nsAppDirectoryServiceDefs.h"
 #include "private/pprio.h"
@@ -80,42 +81,104 @@ CacheFileHandle::Release()
 
   return count;
 }
 
 NS_INTERFACE_MAP_BEGIN(CacheFileHandle)
   NS_INTERFACE_MAP_ENTRY(nsISupports)
 NS_INTERFACE_MAP_END_THREADSAFE
 
-CacheFileHandle::CacheFileHandle(const SHA1Sum::Hash *aHash,
-                                 bool aPriority)
+CacheFileHandle::CacheFileHandle(const SHA1Sum::Hash *aHash, bool aPriority)
   : mHash(aHash)
   , mIsDoomed(false)
   , mPriority(aPriority)
   , mClosed(false)
   , mInvalid(false)
   , mFileExists(false)
   , mFileSize(-1)
   , mFD(nullptr)
 {
-  LOG(("CacheFileHandle::CacheFileHandle() [this=%p]", this));
+  LOG(("CacheFileHandle::CacheFileHandle() [this=%p, hash=%08x%08x%08x%08x%08x]"
+       , this, LOGSHA1(aHash)));
+}
+
+CacheFileHandle::CacheFileHandle(const nsACString &aKey, bool aPriority)
+  : mHash(nullptr)
+  , mIsDoomed(false)
+  , mPriority(aPriority)
+  , mClosed(false)
+  , mInvalid(false)
+  , mFileExists(false)
+  , mFileSize(-1)
+  , mFD(nullptr)
+  , mKey(aKey)
+{
+  LOG(("CacheFileHandle::CacheFileHandle() [this=%p, key=%s]", this,
+       PromiseFlatCString(aKey).get()));
 }
 
 CacheFileHandle::~CacheFileHandle()
 {
   LOG(("CacheFileHandle::~CacheFileHandle() [this=%p]", this));
 
   MOZ_ASSERT(CacheFileIOManager::IsOnIOThreadOrCeased());
 
   nsRefPtr<CacheFileIOManager> ioMan = CacheFileIOManager::gInstance;
   if (ioMan) {
     ioMan->CloseHandleInternal(this);
   }
 }
 
+void
+CacheFileHandle::Log()
+{
+  nsAutoCString leafName;
+  if (mFile) {
+    mFile->GetNativeLeafName(leafName);
+  }
+
+  if (!mHash) {
+    // special file
+    LOG(("CacheFileHandle::Log() [this=%p, hash=nullptr, isDoomed=%d, "
+         "priority=%d, closed=%d, invalid=%d, "
+         "fileExists=%d, fileSize=%lld, leafName=%s, key=%s]",
+         this, mIsDoomed, mPriority, mClosed, mInvalid,
+         mFileExists, mFileSize, leafName.get(), mKey.get()));
+  }
+  else {
+    LOG(("CacheFileHandle::Log() [this=%p, hash=%08x%08x%08x%08x%08x, "
+         "isDoomed=%d, priority=%d, closed=%d, invalid=%d, "
+         "fileExists=%d, fileSize=%lld, leafName=%s, key=%s]",
+         this, LOGSHA1(mHash), mIsDoomed, mPriority, mClosed,
+         mInvalid, mFileExists, mFileSize, leafName.get(), mKey.get()));
+  }
+}
+
+uint32_t
+CacheFileHandle::FileSizeInK()
+{
+  MOZ_ASSERT(mFileSize != -1);
+  uint64_t size64 = mFileSize;
+
+  size64 += 0x3FF;
+  size64 >>= 10;
+
+  uint32_t size;
+  if (size64 >> 32) {
+    NS_WARNING("CacheFileHandle::FileSizeInK() - FileSize is too large, "
+               "truncating to PR_UINT32_MAX");
+    size = PR_UINT32_MAX;
+  }
+  else {
+    size = static_cast<uint32_t>(size64);
+  }
+
+  return size;
+}
+
 /******************************************************************************
  *  CacheFileHandles::HandleHashKey
  *****************************************************************************/
 
 void
 CacheFileHandles::HandleHashKey::AddHandle(CacheFileHandle* aHandle)
 {
   MOZ_ASSERT(CacheFileIOManager::IsOnIOThreadOrCeased());
@@ -188,24 +251,33 @@ CacheFileHandles::~CacheFileHandles()
 nsresult
 CacheFileHandles::GetHandle(const SHA1Sum::Hash *aHash,
                             bool aReturnDoomed,
                             CacheFileHandle **_retval)
 {
   MOZ_ASSERT(CacheFileIOManager::IsOnIOThreadOrCeased());
   MOZ_ASSERT(aHash);
 
+#ifdef DEBUG_HANDLES
+  LOG(("CacheFileHandles::GetHandle() [hash=%08x%08x%08x%08x%08x]",
+       LOGSHA1(aHash)));
+#endif
+
   // find hash entry for key
   HandleHashKey *entry = mTable.GetEntry(*aHash);
   if (!entry) {
     LOG(("CacheFileHandles::GetHandle() hash=%08x%08x%08x%08x%08x "
          "no handle entries found", LOGSHA1(aHash)));
     return NS_ERROR_NOT_AVAILABLE;
   }
 
+#ifdef DEBUG_HANDLES
+  Log(entry);
+#endif
+
   // Check if the entry is doomed
   nsRefPtr<CacheFileHandle> handle = entry->GetNewestHandle();
   if (!handle) {
     LOG(("CacheFileHandles::GetHandle() hash=%08x%08x%08x%08x%08x "
          "no handle found %p, entry %p", LOGSHA1(aHash), handle.get(), entry));
     return NS_ERROR_NOT_AVAILABLE;
   }
 
@@ -229,19 +301,27 @@ CacheFileHandles::GetHandle(const SHA1Su
 nsresult
 CacheFileHandles::NewHandle(const SHA1Sum::Hash *aHash,
                             bool aPriority,
                             CacheFileHandle **_retval)
 {
   MOZ_ASSERT(CacheFileIOManager::IsOnIOThreadOrCeased());
   MOZ_ASSERT(aHash);
 
+#ifdef DEBUG_HANDLES
+  LOG(("CacheFileHandles::NewHandle() [hash=%08x%08x%08x%08x%08x]", LOGSHA1(aHash)));
+#endif
+
   // find hash entry for key
   HandleHashKey *entry = mTable.PutEntry(*aHash);
 
+#ifdef DEBUG_HANDLES
+  Log(entry);
+#endif
+
 #ifdef DEBUG
   entry->AssertHandlesState();
 #endif
 
   nsRefPtr<CacheFileHandle> handle = new CacheFileHandle(entry->Hash(), aPriority);
   entry->AddHandle(handle);
 
   LOG(("CacheFileHandles::NewHandle() hash=%08x%08x%08x%08x%08x "
@@ -255,27 +335,36 @@ void
 CacheFileHandles::RemoveHandle(CacheFileHandle *aHandle)
 {
   MOZ_ASSERT(CacheFileIOManager::IsOnIOThreadOrCeased());
   MOZ_ASSERT(aHandle);
 
   if (!aHandle)
     return;
 
+#ifdef DEBUG_HANDLES
+  LOG(("CacheFileHandles::RemoveHandle() [handle=%p, hash=%08x%08x%08x%08x%08x]"
+       , aHandle, LOGSHA1(aHandle->Hash())));
+#endif
+
   // find hash entry for key
   HandleHashKey *entry = mTable.GetEntry(*aHandle->Hash());
   if (!entry) {
     MOZ_ASSERT(CacheFileIOManager::IsShutdown(),
       "Should find entry when removing a handle before shutdown");
 
     LOG(("CacheFileHandles::RemoveHandle() hash=%08x%08x%08x%08x%08x "
          "no entries found", LOGSHA1(aHandle->Hash())));
     return;
   }
 
+#ifdef DEBUG_HANDLES
+  Log(entry);
+#endif
+
   LOG(("CacheFileHandles::RemoveHandle() hash=%08x%08x%08x%08x%08x "
        "removing handle %p", LOGSHA1(entry->Hash()), aHandle));
   entry->RemoveHandle(aHandle);
 
   if (entry->IsEmpty()) {
     LOG(("CacheFileHandles::RemoveHandle() hash=%08x%08x%08x%08x%08x "
          "list is empty, removing entry %p", LOGSHA1(entry->Hash()), entry));
     mTable.RemoveEntry(*entry->Hash());
@@ -307,16 +396,34 @@ CacheFileHandles::ClearAll()
 }
 
 uint32_t
 CacheFileHandles::HandleCount()
 {
   return mTable.Count();
 }
 
+#ifdef DEBUG_HANDLES
+void
+CacheFileHandles::Log(CacheFileHandlesEntry *entry)
+{
+  LOG(("CacheFileHandles::Log() BEGIN [entry=%p]", entry));
+
+  nsTArray<nsRefPtr<CacheFileHandle> > array;
+  aEntry->GetHandles(array);
+
+  for (uint32_t i = 0; i < array.Length(); ++i) {
+    CacheFileHandle *handle = array[i];
+    handle->Log();
+  }
+
+  LOG(("CacheFileHandles::Log() END [entry=%p]", entry));
+}
+#endif
+
 // Events
 
 class ShutdownEvent : public nsRunnable {
 public:
   ShutdownEvent(mozilla::Mutex *aLock, mozilla::CondVar *aCondVar)
     : mLock(aLock)
     , mCondVar(aCondVar)
   {
@@ -368,17 +475,19 @@ public:
     MOZ_COUNT_DTOR(OpenFileEvent);
   }
 
   NS_IMETHOD Run()
   {
     if (mTarget) {
       mRV = NS_OK;
 
-      if (mFlags & CacheFileIOManager::NOHASH) {
+      if (mFlags & CacheFileIOManager::SPECIAL_FILE) {
+      }
+      else if (mFlags & CacheFileIOManager::NOHASH) {
         nsACString::const_char_iterator begin, end;
         begin = mKey.BeginReading();
         end = mKey.EndReading();
         uint32_t i = 0;
         while (begin != end && i < (SHA1Sum::HashSize << 1)) {
           if (!(i & 1))
             mHash[i >> 1] = 0;
           uint8_t shift = (i & 1) ? 0 : 4;
@@ -397,26 +506,33 @@ public:
           mRV = NS_ERROR_INVALID_ARG;
       }
       else {
         SHA1Sum sum;
         sum.update(mKey.BeginReading(), mKey.Length());
         sum.finish(mHash);
       }
 
-      MOZ_EVENT_TRACER_EXEC(static_cast<nsIRunnable*>(this), "net::cache::open-background");
+      MOZ_EVENT_TRACER_EXEC(static_cast<nsIRunnable*>(this),
+                            "net::cache::open-background");
       if (NS_SUCCEEDED(mRV)) {
         if (!mIOMan)
           mRV = NS_ERROR_NOT_INITIALIZED;
         else {
-          mRV = mIOMan->OpenFileInternal(&mHash, mFlags, getter_AddRefs(mHandle));
+          if (mFlags & CacheFileIOManager::SPECIAL_FILE)
+            mRV = mIOMan->OpenSpecialFileInternal(mKey, mFlags,
+                                                  getter_AddRefs(mHandle));
+          else
+            mRV = mIOMan->OpenFileInternal(&mHash, mFlags,
+                                           getter_AddRefs(mHandle));
           mIOMan = nullptr;
           if (mHandle) {
             MOZ_EVENT_TRACER_NAME_OBJECT(mHandle.get(), mKey.get());
-            mHandle->Key() = mKey;
+            if (mHandle->Key().IsEmpty())
+              mHandle->Key() = mKey;
           }
         }
       }
       MOZ_EVENT_TRACER_DONE(static_cast<nsIRunnable*>(this), "net::cache::open-background");
 
       MOZ_EVENT_TRACER_WAIT(static_cast<nsIRunnable*>(this), "net::cache::open-result");
       nsCOMPtr<nsIEventTarget> target;
       mTarget.swap(target);
@@ -516,16 +632,20 @@ public:
 
     MOZ_EVENT_TRACER_NAME_OBJECT(static_cast<nsIRunnable*>(this), aHandle->Key().get());
     MOZ_EVENT_TRACER_WAIT(static_cast<nsIRunnable*>(this), "net::cache::write-background");
   }
 
   ~WriteEvent()
   {
     MOZ_COUNT_DTOR(WriteEvent);
+
+    if (!mCallback && mBuf) {
+      free(const_cast<char *>(mBuf));
+    }
   }
 
   NS_IMETHOD Run()
   {
     if (mTarget) {
       MOZ_EVENT_TRACER_EXEC(static_cast<nsIRunnable*>(this), "net::cache::write-background");
       if (mHandle->IsClosed())
         mRV = NS_ERROR_NOT_INITIALIZED;
@@ -538,16 +658,20 @@ public:
       nsCOMPtr<nsIEventTarget> target;
       mTarget.swap(target);
       target->Dispatch(this, nsIEventTarget::DISPATCH_NORMAL);
     }
     else {
       MOZ_EVENT_TRACER_EXEC(static_cast<nsIRunnable*>(this), "net::cache::write-result");
       if (mCallback)
         mCallback->OnDataWritten(mHandle, mBuf, mRV);
+      else {
+        free(const_cast<char *>(mBuf));
+        mBuf = nullptr;
+      }
       MOZ_EVENT_TRACER_DONE(static_cast<nsIRunnable*>(this), "net::cache::write-result");
     }
     return NS_OK;
   }
 
 protected:
   nsRefPtr<CacheFileHandle>     mHandle;
   int64_t                       mOffset;
@@ -730,16 +854,146 @@ protected:
   nsRefPtr<CacheFileHandle>     mHandle;
   int64_t                       mTruncatePos;
   int64_t                       mEOFPos;
   nsCOMPtr<CacheFileIOListener> mCallback;
   nsCOMPtr<nsIEventTarget>      mTarget;
   nsresult                      mRV;
 };
 
+class RenameFileEvent : public nsRunnable {
+public:
+  RenameFileEvent(CacheFileHandle *aHandle, const nsACString &aNewName,
+                  CacheFileIOListener *aCallback)
+    : mHandle(aHandle)
+    , mNewName(aNewName)
+    , mCallback(aCallback)
+    , mRV(NS_ERROR_FAILURE)
+  {
+    MOZ_COUNT_CTOR(RenameFileEvent);
+    mTarget = static_cast<nsIEventTarget*>(NS_GetCurrentThread());
+  }
+
+  ~RenameFileEvent()
+  {
+    MOZ_COUNT_DTOR(RenameFileEvent);
+  }
+
+  NS_IMETHOD Run()
+  {
+    if (mTarget) {
+      if (mHandle->IsClosed())
+        mRV = NS_ERROR_NOT_INITIALIZED;
+      else
+        mRV = CacheFileIOManager::gInstance->RenameFileInternal(mHandle,
+                                                                mNewName);
+
+      nsCOMPtr<nsIEventTarget> target;
+      mTarget.swap(target);
+      target->Dispatch(this, nsIEventTarget::DISPATCH_NORMAL);
+    }
+    else {
+      if (mCallback)
+        mCallback->OnFileRenamed(mHandle, mRV);
+    }
+    return NS_OK;
+  }
+
+protected:
+  nsRefPtr<CacheFileHandle>     mHandle;
+  nsCString                     mNewName;
+  nsCOMPtr<CacheFileIOListener> mCallback;
+  nsCOMPtr<nsIEventTarget>      mTarget;
+  nsresult                      mRV;
+};
+
+class InitIndexEntryEvent : public nsRunnable {
+public:
+  InitIndexEntryEvent(CacheFileHandle *aHandle, uint32_t aAppId,
+                      bool aAnonymous, bool aInBrowser)
+    : mHandle(aHandle)
+    , mAppId(aAppId)
+    , mAnonymous(aAnonymous)
+    , mInBrowser(aInBrowser)
+  {
+    MOZ_COUNT_CTOR(InitIndexEntryEvent);
+  }
+
+  ~InitIndexEntryEvent()
+  {
+    MOZ_COUNT_DTOR(InitIndexEntryEvent);
+  }
+
+  NS_IMETHOD Run()
+  {
+    if (mHandle->IsClosed() || mHandle->IsDoomed())
+      return NS_OK;
+
+    CacheIndex::InitEntry(mHandle->Hash(), mAppId, mAnonymous, mInBrowser);
+
+    // We cannot set the filesize before we init the entry. If we're opening
+    // an existing entry file, frecency and expiration time will be set after
+    // parsing the entry file, but we must set the filesize here since nobody is
+    // going to set it if there is no write to the file.
+    uint32_t sizeInK = mHandle->FileSizeInK();
+    CacheIndex::UpdateEntry(mHandle->Hash(), nullptr, nullptr, &sizeInK);
+
+    return NS_OK;
+  }
+
+protected:
+  nsRefPtr<CacheFileHandle> mHandle;
+  uint32_t                  mAppId;
+  bool                      mAnonymous;
+  bool                      mInBrowser;
+};
+
+class UpdateIndexEntryEvent : public nsRunnable {
+public:
+  UpdateIndexEntryEvent(CacheFileHandle *aHandle, const uint32_t *aFrecency,
+                        const uint32_t *aExpirationTime)
+    : mHandle(aHandle)
+    , mHasFrecency(false)
+    , mHasExpirationTime(false)
+  {
+    MOZ_COUNT_CTOR(UpdateIndexEntryEvent);
+    if (aFrecency) {
+      mHasFrecency = true;
+      mFrecency = *aFrecency;
+    }
+    if (aExpirationTime) {
+      mHasExpirationTime = true;
+      mExpirationTime = *aExpirationTime;
+    }
+  }
+
+  ~UpdateIndexEntryEvent()
+  {
+    MOZ_COUNT_DTOR(UpdateIndexEntryEvent);
+  }
+
+  NS_IMETHOD Run()
+  {
+    if (mHandle->IsClosed() || mHandle->IsDoomed())
+      return NS_OK;
+
+    CacheIndex::UpdateEntry(mHandle->Hash(),
+                            mHasFrecency ? &mFrecency : nullptr,
+                            mHasExpirationTime ? &mExpirationTime : nullptr,
+                            nullptr);
+    return NS_OK;
+  }
+
+protected:
+  nsRefPtr<CacheFileHandle> mHandle;
+  bool                      mHasFrecency;
+  bool                      mHasExpirationTime;
+  uint32_t                  mFrecency;
+  uint32_t                  mExpirationTime;
+};
 
 class MetadataWriteScheduleEvent : public nsRunnable
 {
 public:
   enum EMode {
     SCHEDULE,
     UNSCHEDULE,
     SHUTDOWN
@@ -841,16 +1095,18 @@ CacheFileIOManager::Shutdown()
 
   MOZ_ASSERT(NS_IsMainThread());
 
   if (!gInstance)
     return NS_ERROR_NOT_INITIALIZED;
 
   Telemetry::AutoTimer<Telemetry::NETWORK_DISK_CACHE_SHUTDOWN_V2> shutdownTimer;
 
+  CacheIndex::PreShutdown();
+
   ShutdownMetadataWriteScheduling();
 
   {
     mozilla::Mutex lock("CacheFileIOManager::Shutdown() lock");
     mozilla::CondVar condVar(lock, "CacheFileIOManager::Shutdown() condVar");
 
     MutexAutoLock autoLock(lock);
     nsRefPtr<ShutdownEvent> ev = new ShutdownEvent(&lock, &condVar);
@@ -861,50 +1117,66 @@ CacheFileIOManager::Shutdown()
   }
 
   MOZ_ASSERT(gInstance->mHandles.HandleCount() == 0);
   MOZ_ASSERT(gInstance->mHandlesByLastUsed.Length() == 0);
 
   if (gInstance->mIOThread)
     gInstance->mIOThread->Shutdown();
 
+  CacheIndex::Shutdown();
+
   nsRefPtr<CacheFileIOManager> ioMan;
   ioMan.swap(gInstance);
 
   return NS_OK;
 }
 
 nsresult
 CacheFileIOManager::ShutdownInternal()
 {
+  LOG(("CacheFileIOManager::ShutdownInternal() [this=%p]", this));
+
   MOZ_ASSERT(mIOThread->IsCurrentThread());
 
   // No new handles can be created after this flag is set
   mShuttingDown = true;
 
   // close all handles and delete all associated files
   nsTArray<nsRefPtr<CacheFileHandle> > handles;
   mHandles.GetAllHandles(&handles);
+  handles.AppendElements(mSpecialHandles);
 
   for (uint32_t i=0 ; i<handles.Length() ; i++) {
     CacheFileHandle *h = handles[i];
     h->mClosed = true;
 
+    h->Log();
+
     // Close file handle
     if (h->mFD) {
       ReleaseNSPRHandleInternal(h);
     }
 
     // Remove file if entry is doomed or invalid
     if (h->mFileExists && (h->mIsDoomed || h->mInvalid)) {
+      LOG(("CacheFileIOManager::ShutdownInternal() - Removing file from disk"));
       h->mFile->Remove(false);
     }
 
-    // Remove the handle from hashtable
-    mHandles.RemoveHandle(h);
+    if (!h->IsSpecialFile() && !h->mIsDoomed &&
+        (h->mInvalid || !h->mFileExists)) {
+      CacheIndex::RemoveEntry(h->Hash());
+    }
+
+    // Remove the handle from mHandles/mSpecialHandles
+    if (h->IsSpecialFile())
+      mSpecialHandles.RemoveElement(h);
+    else
+      mHandles.RemoveHandle(h);
   }
 
   // Assert the table is empty. When we are here, no new handles can be added
   // and handles will no longer remove them self from this table and we don't 
   // want to keep invalid handles here. Also, there is no lookup after this 
   // point to happen.
   MOZ_ASSERT(mHandles.HandleCount() == 0);
 
@@ -941,21 +1213,23 @@ CacheFileIOManager::OnProfile()
   }
 
   if (!directory) {
     rv = NS_GetSpecialDirectory(NS_APP_USER_PROFILE_LOCAL_50_DIR,
                                 getter_AddRefs(directory));
   }
 
   if (directory) {
+    rv = directory->Append(NS_LITERAL_STRING("cache2"));
+    NS_ENSURE_SUCCESS(rv, rv);
+
     rv = directory->Clone(getter_AddRefs(ioMan->mCacheDirectory));
     NS_ENSURE_SUCCESS(rv, rv);
 
-    rv = ioMan->mCacheDirectory->Append(NS_LITERAL_STRING("cache2"));
-    NS_ENSURE_SUCCESS(rv, rv);
+    CacheIndex::Init(directory);
   }
 
   return NS_OK;
 }
 
 // static
 already_AddRefed<nsIEventTarget>
 CacheFileIOManager::IOTarget()
@@ -975,16 +1249,27 @@ CacheFileIOManager::IOThread()
   if (gInstance)
     thread = gInstance->mIOThread;
 
   return thread.forget();
 }
 
 // static
 bool
+CacheFileIOManager::IsOnIOThread()
+{
+  nsRefPtr<CacheFileIOManager> ioMan = gInstance;
+  if (ioMan && ioMan->mIOThread)
+    return ioMan->mIOThread->IsCurrentThread();
+
+  return false;
+}
+
+// static
+bool
 CacheFileIOManager::IsOnIOThreadOrCeased()
 {
   nsRefPtr<CacheFileIOManager> ioMan = gInstance;
   if (ioMan && ioMan->mIOThread)
     return ioMan->mIOThread->IsCurrentThread();
 
   // Ceased...
   return true;
@@ -1149,17 +1434,20 @@ CacheFileIOManager::OpenFile(const nsACS
   return NS_OK;
 }
 
 nsresult
 CacheFileIOManager::OpenFileInternal(const SHA1Sum::Hash *aHash,
                                      uint32_t aFlags,
                                      CacheFileHandle **_retval)
 {
-  MOZ_ASSERT(CacheFileIOManager::IsOnIOThreadOrCeased());
+  LOG(("CacheFileIOManager::OpenFileInternal() [hash=%08x%08x%08x%08x%08x, "
+       "flags=%d]", LOGSHA1(aHash), aFlags));
+
+  MOZ_ASSERT(CacheFileIOManager::IsOnIOThread());
 
   nsresult rv;
 
   if (mShuttingDown)
     return NS_ERROR_NOT_INITIALIZED;
 
   if (!mTreeCreated) {
     rv = CreateCacheTree();
@@ -1168,56 +1456,157 @@ CacheFileIOManager::OpenFileInternal(con
 
   nsCOMPtr<nsIFile> file;
   rv = GetFile(aHash, getter_AddRefs(file));
   NS_ENSURE_SUCCESS(rv, rv);
 
   nsRefPtr<CacheFileHandle> handle;
   mHandles.GetHandle(aHash, false, getter_AddRefs(handle));
 
-  if (aFlags == CREATE_NEW) {
+  if ((aFlags & (OPEN | CREATE | CREATE_NEW)) == CREATE_NEW) {
     if (handle) {
       rv = DoomFileInternal(handle);
       NS_ENSURE_SUCCESS(rv, rv);
       handle = nullptr;
     }
 
     rv = mHandles.NewHandle(aHash, aFlags & PRIORITY, getter_AddRefs(handle));
     NS_ENSURE_SUCCESS(rv, rv);
 
     bool exists;
     rv = file->Exists(&exists);
     NS_ENSURE_SUCCESS(rv, rv);
 
     if (exists) {
+      CacheIndex::RemoveEntry(aHash);
+
+      LOG(("CacheFileIOManager::OpenFileInternal() - Removing old file from "
+           "disk"));
       rv = file->Remove(false);
       if (NS_FAILED(rv)) {
         NS_WARNING("Cannot remove old entry from the disk");
-        // TODO log
+        LOG(("CacheFileIOManager::OpenFileInternal() - Removing old file failed"
+             ". [rv=0x%08x]", rv));
+      }
+    }
+
+    CacheIndex::AddEntry(aHash);
+    handle->mFile.swap(file);
+    handle->mFileSize = 0;
+  }
+
+  if (handle) {
+    handle.swap(*_retval);
+    return NS_OK;
+  }
+
+  bool exists;
+  rv = file->Exists(&exists);
+  NS_ENSURE_SUCCESS(rv, rv);
+
+  if (!exists && (aFlags & (OPEN | CREATE | CREATE_NEW)) == OPEN)
+    return NS_ERROR_NOT_AVAILABLE;
+
+  rv = mHandles.NewHandle(aHash, aFlags & PRIORITY, getter_AddRefs(handle));
+  NS_ENSURE_SUCCESS(rv, rv);
+
+  if (exists) {
+    rv = file->GetFileSize(&handle->mFileSize);
+    NS_ENSURE_SUCCESS(rv, rv);
+
+    handle->mFileExists = true;
+
+    CacheIndex::EnsureEntryExists(aHash);
+  }
+  else {
+    handle->mFileSize = 0;
+
+    CacheIndex::AddEntry(aHash);
+  }
+
+  handle->mFile.swap(file);
+  handle.swap(*_retval);
+  return NS_OK;
+}
+
+nsresult
+CacheFileIOManager::OpenSpecialFileInternal(const nsACString &aKey,
+                                            uint32_t aFlags,
+                                            CacheFileHandle **_retval)
+{
+  LOG(("CacheFileIOManager::OpenSpecialFileInternal() [key=%s, flags=%d]",
+       PromiseFlatCString(aKey).get(), aFlags));
+
+  MOZ_ASSERT(CacheFileIOManager::IsOnIOThread());
+
+  nsresult rv;
+
+  if (mShuttingDown)
+    return NS_ERROR_NOT_INITIALIZED;
+
+  if (!mTreeCreated) {
+    rv = CreateCacheTree();
+    if (NS_FAILED(rv)) return rv;
+  }
+
+  nsCOMPtr<nsIFile> file;
+  rv = GetSpecialFile(aKey, getter_AddRefs(file));
+  NS_ENSURE_SUCCESS(rv, rv);
+
+  nsRefPtr<CacheFileHandle> handle;
+  for (uint32_t i = 0 ; i < mSpecialHandles.Length() ; i++) {
+    if (!mSpecialHandles[i]->IsDoomed() && mSpecialHandles[i]->Key() == aKey) {
+      handle = mSpecialHandles[i];
+      break;
+    }
+  }
+
+  if ((aFlags & (OPEN | CREATE | CREATE_NEW)) == CREATE_NEW) {
+    if (handle) {
+      rv = DoomFileInternal(handle);
+      NS_ENSURE_SUCCESS(rv, rv);
+      handle = nullptr;
+    }
+
+    handle = new CacheFileHandle(aKey, aFlags & PRIORITY);
+    mSpecialHandles.AppendElement(handle);
+
+    bool exists;
+    rv = file->Exists(&exists);
+    NS_ENSURE_SUCCESS(rv, rv);
+
+    if (exists) {
+      LOG(("CacheFileIOManager::OpenSpecialFileInternal() - Removing file from "
+           "disk"));
+      rv = file->Remove(false);
+      if (NS_FAILED(rv)) {
+        NS_WARNING("Cannot remove old entry from the disk");
+        LOG(("CacheFileIOManager::OpenSpecialFileInternal() - Removing file "
+             "failed. [rv=0x%08x]", rv));
       }
     }
 
     handle->mFile.swap(file);
     handle->mFileSize = 0;
   }
 
   if (handle) {
     handle.swap(*_retval);
     return NS_OK;
   }
 
   bool exists;
   rv = file->Exists(&exists);
   NS_ENSURE_SUCCESS(rv, rv);
 
-  if (!exists && aFlags == OPEN)
+  if (!exists && (aFlags & (OPEN | CREATE | CREATE_NEW)) == OPEN)
     return NS_ERROR_NOT_AVAILABLE;
 
-  rv = mHandles.NewHandle(aHash, aFlags & PRIORITY, getter_AddRefs(handle));
-  NS_ENSURE_SUCCESS(rv, rv);
+  handle = new CacheFileHandle(aKey, aFlags & PRIORITY);
+  mSpecialHandles.AppendElement(handle);
 
   if (exists) {
     rv = file->GetFileSize(&handle->mFileSize);
     NS_ENSURE_SUCCESS(rv, rv);
 
     handle->mFileExists = true;
   }
   else {
@@ -1227,30 +1616,42 @@ CacheFileIOManager::OpenFileInternal(con
   handle->mFile.swap(file);
   handle.swap(*_retval);
   return NS_OK;
 }
 
 nsresult
 CacheFileIOManager::CloseHandleInternal(CacheFileHandle *aHandle)
 {
+  LOG(("CacheFileIOManager::CloseHandleInternal() [handle=%p]", aHandle));
+  aHandle->Log();
+
   MOZ_ASSERT(CacheFileIOManager::IsOnIOThreadOrCeased());
 
   // Close file handle
   if (aHandle->mFD) {
     ReleaseNSPRHandleInternal(aHandle);
   }
 
-  // If the entry was doomed delete the file
-  if (aHandle->IsDoomed()) {
+  // Delete the file if the entry was doomed or invalid
+  if (aHandle->mIsDoomed || aHandle->mInvalid) {
+    LOG(("CacheFileIOManager::CloseHandleInternal() - Removing file from "
+         "disk"));
     aHandle->mFile->Remove(false);
   }
 
+  if (!aHandle->IsSpecialFile() && !aHandle->mIsDoomed &&
+      (aHandle->mInvalid || !aHandle->mFileExists)) {
+    CacheIndex::RemoveEntry(aHandle->Hash());
+  }
+
   // Remove the handle from hashtable
-  if (!mShuttingDown) // Don't touch after shutdown
+  if (aHandle->IsSpecialFile())
+    mSpecialHandles.RemoveElement(aHandle);
+  else if (!mShuttingDown) // Don't touch after shutdown
     mHandles.RemoveHandle(aHandle);
 
   return NS_OK;
 }
 
 nsresult
 CacheFileIOManager::Read(CacheFileHandle *aHandle, int64_t aOffset,
                          char *aBuf, int32_t aCount,
@@ -1274,16 +1675,19 @@ CacheFileIOManager::Read(CacheFileHandle
 
   return NS_OK;
 }
 
 nsresult
 CacheFileIOManager::ReadInternal(CacheFileHandle *aHandle, int64_t aOffset,
                                  char *aBuf, int32_t aCount)
 {
+  LOG(("CacheFileIOManager::ReadInternal() [handle=%p, offset=%lld, count=%d]",
+       aHandle, aOffset, aCount));
+
   nsresult rv;
 
   if (!aHandle->mFileExists) {
     NS_WARNING("Trying to read from non-existent file");
     return NS_ERROR_NOT_AVAILABLE;
   }
 
   if (!aHandle->mFD) {
@@ -1334,16 +1738,19 @@ CacheFileIOManager::Write(CacheFileHandl
   return NS_OK;
 }
 
 nsresult
 CacheFileIOManager::WriteInternal(CacheFileHandle *aHandle, int64_t aOffset,
                                   const char *aBuf, int32_t aCount,
                                   bool aValidate)
 {
+  LOG(("CacheFileIOManager::WriteInternal() [handle=%p, offset=%lld, count=%d, "
+       "validate=%d]", aHandle, aOffset, aCount, aValidate));
+
   nsresult rv;
 
   if (!aHandle->mFileExists) {
     rv = CreateFile(aHandle);
     NS_ENSURE_SUCCESS(rv, rv);
   }
 
   if (!aHandle->mFD) {
@@ -1363,18 +1770,24 @@ CacheFileIOManager::WriteInternal(CacheF
   aHandle->mInvalid = true;
 
   int64_t offset = PR_Seek64(aHandle->mFD, aOffset, PR_SEEK_SET);
   if (offset == -1)
     return NS_ERROR_FAILURE;
 
   int32_t bytesWritten = PR_Write(aHandle->mFD, aBuf, aCount);
 
-  if (bytesWritten != -1 && aHandle->mFileSize < aOffset+bytesWritten)
-      aHandle->mFileSize = aOffset+bytesWritten;
+  if (bytesWritten != -1 && aHandle->mFileSize < aOffset+bytesWritten) {
+    aHandle->mFileSize = aOffset+bytesWritten;
+
+    if (!aHandle->IsDoomed() && !aHandle->IsSpecialFile()) {
+      uint32_t size = aHandle->FileSizeInK();
+      CacheIndex::UpdateEntry(aHandle->Hash(), nullptr, nullptr, &size);
+    }
+  }
 
   if (bytesWritten != aCount)
     return NS_ERROR_FAILURE;
 
   // Write was successful and this write validates the entry (i.e. metadata)
   if (aValidate)
     aHandle->mInvalid = false;
 
@@ -1401,16 +1814,19 @@ CacheFileIOManager::DoomFile(CacheFileHa
   NS_ENSURE_SUCCESS(rv, rv);
 
   return NS_OK;
 }
 
 nsresult
 CacheFileIOManager::DoomFileInternal(CacheFileHandle *aHandle)
 {
+  LOG(("CacheFileIOManager::DoomFileInternal() [handle=%p]", aHandle));
+  aHandle->Log();
+
   nsresult rv;
 
   if (aHandle->IsDoomed())
     return NS_OK;
 
   if (aHandle->mFileExists) {
     // we need to move the current file to the doomed directory
     if (aHandle->mFD)
@@ -1436,16 +1852,19 @@ CacheFileIOManager::DoomFileInternal(Cac
       rv = NS_OK;
     }
     else {
       NS_ENSURE_SUCCESS(rv, rv);
       aHandle->mFile.swap(file);
     }
   }
 
+  if (!aHandle->IsSpecialFile())
+    CacheIndex::RemoveEntry(aHandle->Hash());
+
   aHandle->mIsDoomed = true;
   return NS_OK;
 }
 
 nsresult
 CacheFileIOManager::DoomFileByKey(const nsACString &aKey,
                                   CacheFileIOListener *aCallback)
 {
@@ -1463,31 +1882,36 @@ CacheFileIOManager::DoomFileByKey(const 
   NS_ENSURE_SUCCESS(rv, rv);
 
   return NS_OK;
 }
 
 nsresult
 CacheFileIOManager::DoomFileByKeyInternal(const SHA1Sum::Hash *aHash)
 {
+  LOG(("CacheFileIOManager::DoomFileByKeyInternal() [hash=%08x%08x%08x%08x%08x]"
+       , LOGSHA1(aHash)));
+
   MOZ_ASSERT(CacheFileIOManager::IsOnIOThreadOrCeased());
 
   nsresult rv;
 
   if (mShuttingDown)
     return NS_ERROR_NOT_INITIALIZED;
 
   if (!mCacheDirectory)
     return NS_ERROR_FILE_INVALID_PATH;
 
   // Find active handle
   nsRefPtr<CacheFileHandle> handle;
   mHandles.GetHandle(aHash, true, getter_AddRefs(handle));
 
   if (handle) {
+    handle->Log();
+
     if (handle->IsDoomed())
       return NS_OK;
 
     return DoomFileInternal(handle);
   }
 
   // There is no handle for this file, delete the file if exists
   nsCOMPtr<nsIFile> file;
@@ -1496,22 +1920,27 @@ CacheFileIOManager::DoomFileByKeyInterna
 
   bool exists;
   rv = file->Exists(&exists);
   NS_ENSURE_SUCCESS(rv, rv);
 
   if (!exists)
     return NS_ERROR_NOT_AVAILABLE;
 
+  LOG(("CacheFileIOManager::DoomFileByKeyInternal() - Removing file from "
+       "disk"));
   rv = file->Remove(false);
   if (NS_FAILED(rv)) {
     NS_WARNING("Cannot remove old entry from the disk");
-    // TODO log
+    LOG(("CacheFileIOManager::DoomFileByKeyInternal() - Removing file failed. "
+         "[rv=0x%08x]", rv));
   }
 
+  CacheIndex::RemoveEntry(aHash);
+
   return NS_OK;
 }
 
 nsresult
 CacheFileIOManager::ReleaseNSPRHandle(CacheFileHandle *aHandle)
 {
   LOG(("CacheFileIOManager::ReleaseNSPRHandle() [handle=%p]", aHandle));
 
@@ -1526,16 +1955,18 @@ CacheFileIOManager::ReleaseNSPRHandle(Ca
   NS_ENSURE_SUCCESS(rv, rv);
 
   return NS_OK;
 }
 
 nsresult
 CacheFileIOManager::ReleaseNSPRHandleInternal(CacheFileHandle *aHandle)
 {
+  LOG(("CacheFileIOManager::ReleaseNSPRHandleInternal() [handle=%p]", aHandle));
+
   MOZ_ASSERT(CacheFileIOManager::IsOnIOThreadOrCeased());
   MOZ_ASSERT(aHandle->mFD);
 
   DebugOnly<bool> found;
   found = mHandlesByLastUsed.RemoveElement(aHandle);
   MOZ_ASSERT(found);
 
   PR_Close(aHandle->mFD);
@@ -1562,62 +1993,16 @@ CacheFileIOManager::TruncateSeekSetEOF(C
                                            aHandle, aTruncatePos, aEOFPos,
                                            aCallback);
   rv = ioMan->mIOThread->Dispatch(ev, CacheIOThread::WRITE);
   NS_ENSURE_SUCCESS(rv, rv);
 
   return NS_OK;
 }
 
-nsresult
-CacheFileIOManager::EnumerateEntryFiles(EEnumerateMode aMode,
-                                        CacheEntriesEnumerator** aEnumerator)
-{
-  LOG(("CacheFileIOManager::EnumerateEntryFiles(%d)", aMode));
-
-  nsresult rv;
-  nsRefPtr<CacheFileIOManager> ioMan = gInstance;
-
-  if (!ioMan)
-    return NS_ERROR_NOT_INITIALIZED;
-
-  if (!ioMan->mCacheDirectory)
-    return NS_ERROR_FILE_NOT_FOUND;
-
-  nsCOMPtr<nsIFile> file;
-  rv = ioMan->mCacheDirectory->Clone(getter_AddRefs(file));
-  NS_ENSURE_SUCCESS(rv, rv);
-
-  switch (aMode) {
-  case ENTRIES:
-    rv = file->AppendNative(NS_LITERAL_CSTRING("entries"));
-    NS_ENSURE_SUCCESS(rv, rv);
-
-    break;
-
-  case DOOMED:
-    rv = file->AppendNative(NS_LITERAL_CSTRING("doomed"));
-    NS_ENSURE_SUCCESS(rv, rv);
-
-    break;
-
-  default:
-    return NS_ERROR_INVALID_ARG;
-  }
-
-  nsAutoPtr<CacheEntriesEnumerator> enumerator(
-    new CacheEntriesEnumerator(file));
-
-  rv = enumerator->Init();
-  NS_ENSURE_SUCCESS(rv, rv);
-
-  *aEnumerator = enumerator.forget();
-  return NS_OK;
-}
-
 // static
 void CacheFileIOManager::GetCacheDirectory(nsIFile** result)
 {
   *result = nullptr;
 
   nsRefPtr<CacheFileIOManager> ioMan = gInstance;
   if (!ioMan)
     return;
@@ -1649,16 +2034,19 @@ TruncFile(PRFileDesc *aFD, uint32_t aEOF
   return NS_OK;
 }
 
 nsresult
 CacheFileIOManager::TruncateSeekSetEOFInternal(CacheFileHandle *aHandle,
                                                int64_t aTruncatePos,
                                                int64_t aEOFPos)
 {
+  LOG(("CacheFileIOManager::TruncateSeekSetEOFInternal() [handle=%p, "
+       "truncatePos=%lld, EOFPos=%lld]", aHandle, aTruncatePos, aEOFPos));
+
   nsresult rv;
 
   if (!aHandle->mFileExists) {
     rv = CreateFile(aHandle);
     NS_ENSURE_SUCCESS(rv, rv);
   }
 
   if (!aHandle->mFD) {
@@ -1682,85 +2070,311 @@ CacheFileIOManager::TruncateSeekSetEOFIn
 
   rv = TruncFile(aHandle->mFD, static_cast<uint32_t>(aEOFPos));
   NS_ENSURE_SUCCESS(rv, rv);
 
   return NS_OK;
 }
 
 nsresult
+CacheFileIOManager::RenameFile(CacheFileHandle *aHandle,
+                               const nsACString &aNewName,
+                               CacheFileIOListener *aCallback)
+{
+  LOG(("CacheFileIOManager::RenameFile() [handle=%p, newName=%s, listener=%p]",
+       aHandle, PromiseFlatCString(aNewName).get(), aCallback));
+
+  nsresult rv;
+  nsRefPtr<CacheFileIOManager> ioMan = gInstance;
+
+  if (aHandle->IsClosed() || !ioMan)
+    return NS_ERROR_NOT_INITIALIZED;
+
+  if (!aHandle->IsSpecialFile())
+    return NS_ERROR_UNEXPECTED;
+
+  nsRefPtr<RenameFileEvent> ev = new RenameFileEvent(aHandle, aNewName,
+                                                     aCallback);
+  rv = ioMan->mIOThread->Dispatch(ev, CacheIOThread::WRITE);
+  NS_ENSURE_SUCCESS(rv, rv);
+
+  return NS_OK;
+}
+
+nsresult
+CacheFileIOManager::RenameFileInternal(CacheFileHandle *aHandle,
+                                       const nsACString &aNewName)
+{
+  LOG(("CacheFileIOManager::RenameFileInternal() [handle=%p, newName=%s]",
+       aHandle, PromiseFlatCString(aNewName).get()));
+
+  nsresult rv;
+
+  MOZ_ASSERT(aHandle->IsSpecialFile());
+
+  if (aHandle->IsDoomed())
+    return NS_ERROR_NOT_AVAILABLE;
+
+  // Doom old handle if it exists and is not doomed
+  for (uint32_t i = 0 ; i < mSpecialHandles.Length() ; i++) {
+    if (!mSpecialHandles[i]->IsDoomed() &&
+        mSpecialHandles[i]->Key() == aNewName) {
+      MOZ_ASSERT(aHandle != mSpecialHandles[i]);
+      rv = DoomFileInternal(mSpecialHandles[i]);
+      NS_ENSURE_SUCCESS(rv, rv);
+      break;
+    }
+  }
+
+  nsCOMPtr<nsIFile> file;
+  rv = GetSpecialFile(aNewName, getter_AddRefs(file));
+  NS_ENSURE_SUCCESS(rv, rv);
+
+  bool exists;
+  rv = file->Exists(&exists);
+  NS_ENSURE_SUCCESS(rv, rv);
+
+  if (exists) {
+    LOG(("CacheFileIOManager::RenameFileInternal() - Removing old file from "
+         "disk"));
+    rv = file->Remove(false);
+    if (NS_FAILED(rv)) {
+      NS_WARNING("Cannot remove file from the disk");
+      LOG(("CacheFileIOManager::RenameFileInternal() - Removing old file failed"
+           ". [rv=0x%08x]", rv));
+    }
+  }
+
+  if (!aHandle->FileExists()) {
+    aHandle->mKey = aNewName;
+    return NS_OK;
+  }
+
+  if (aHandle->mFD)
+    ReleaseNSPRHandleInternal(aHandle);
+
+  rv = aHandle->mFile->MoveToNative(nullptr, aNewName);
+  NS_ENSURE_SUCCESS(rv, rv);
+
+  aHandle->mKey = aNewName;
+  return NS_OK;
+}
+
+nsresult
+CacheFileIOManager::InitIndexEntry(CacheFileHandle *aHandle,
+                                   uint32_t         aAppId,
+                                   bool             aAnonymous,
+                                   bool             aInBrowser)
+{
+  LOG(("CacheFileIOManager::InitIndexEntry() [handle=%p, appId=%u, anonymous=%d"
+       ", inBrowser=%d]", aHandle, aAppId, aAnonymous, aInBrowser));
+
+  nsresult rv;
+  nsRefPtr<CacheFileIOManager> ioMan = gInstance;
+
+  if (aHandle->IsClosed() || !ioMan)
+    return NS_ERROR_NOT_INITIALIZED;
+
+  if (aHandle->IsSpecialFile())
+    return NS_ERROR_UNEXPECTED;
+
+  nsRefPtr<InitIndexEntryEvent> ev =
+    new InitIndexEntryEvent(aHandle, aAppId, aAnonymous, aInBrowser);
+  rv = ioMan->mIOThread->Dispatch(ev, CacheIOThread::WRITE);
+  NS_ENSURE_SUCCESS(rv, rv);
+
+  return NS_OK;
+}
+
+nsresult
+CacheFileIOManager::UpdateIndexEntry(CacheFileHandle *aHandle,
+                                     const uint32_t  *aFrecency,
+                                     const uint32_t  *aExpirationTime)
+{
+  LOG(("CacheFileIOManager::UpdateIndexEntry() [handle=%p, frecency=%s, "
+       "expirationTime=%s]", aHandle,
+       aFrecency ? nsPrintfCString("%u", *aFrecency).get() : "",
+       aExpirationTime ? nsPrintfCString("%u", *aExpirationTime).get() : ""));
+
+  nsresult rv;
+  nsRefPtr<CacheFileIOManager> ioMan = gInstance;
+
+  if (aHandle->IsClosed() || !ioMan)
+    return NS_ERROR_NOT_INITIALIZED;
+
+  if (aHandle->IsSpecialFile())
+    return NS_ERROR_UNEXPECTED;
+
+  nsRefPtr<UpdateIndexEntryEvent> ev =
+    new UpdateIndexEntryEvent(aHandle, aFrecency, aExpirationTime);
+  rv = ioMan->mIOThread->Dispatch(ev, CacheIOThread::WRITE);
+  NS_ENSURE_SUCCESS(rv, rv);
+
+  return NS_OK;
+}
+
+nsresult
+CacheFileIOManager::EnumerateEntryFiles(EEnumerateMode aMode,
+                                        CacheEntriesEnumerator** aEnumerator)
+{
+  LOG(("CacheFileIOManager::EnumerateEntryFiles(%d)", aMode));
+
+  nsresult rv;
+  nsRefPtr<CacheFileIOManager> ioMan = gInstance;
+
+  if (!ioMan)
+    return NS_ERROR_NOT_INITIALIZED;
+
+  if (!ioMan->mCacheDirectory)
+    return NS_ERROR_FILE_NOT_FOUND;
+
+  nsCOMPtr<nsIFile> file;
+  rv = ioMan->mCacheDirectory->Clone(getter_AddRefs(file));
+  NS_ENSURE_SUCCESS(rv, rv);
+
+  switch (aMode) {
+  case ENTRIES:
+    rv = file->AppendNative(NS_LITERAL_CSTRING(kEntriesDir));
+    NS_ENSURE_SUCCESS(rv, rv);
+
+    break;
+
+  case DOOMED:
+    rv = file->AppendNative(NS_LITERAL_CSTRING(kDoomedDir));
+    NS_ENSURE_SUCCESS(rv, rv);
+
+    break;
+
+  default:
+    return NS_ERROR_INVALID_ARG;
+  }
+
+  nsAutoPtr<CacheEntriesEnumerator> enumerator(
+    new CacheEntriesEnumerator(file));
+
+  rv = enumerator->Init();
+  NS_ENSURE_SUCCESS(rv, rv);
+
+  *aEnumerator = enumerator.forget();
+  return NS_OK;
+}
+
+nsresult
 CacheFileIOManager::CreateFile(CacheFileHandle *aHandle)
 {
   MOZ_ASSERT(!aHandle->mFD);
+  MOZ_ASSERT(aHandle->mFile);
 
   nsresult rv;
 
-  nsCOMPtr<nsIFile> file;
   if (aHandle->IsDoomed()) {
+    nsCOMPtr<nsIFile> file;
+
     rv = GetDoomedFile(getter_AddRefs(file));
     NS_ENSURE_SUCCESS(rv, rv);
+
+    aHandle->mFile.swap(file);
   } else {
-    rv = GetFile(aHandle->Hash(), getter_AddRefs(file));
-    NS_ENSURE_SUCCESS(rv, rv);
-
     bool exists;
-    if (NS_SUCCEEDED(file->Exists(&exists)) && exists) {
+    if (NS_SUCCEEDED(aHandle->mFile->Exists(&exists)) && exists) {
       NS_WARNING("Found a file that should not exist!");
     }
   }
 
   rv = OpenNSPRHandle(aHandle, true);
   NS_ENSURE_SUCCESS(rv, rv);
 
   aHandle->mFileSize = 0;
   return NS_OK;
 }
 
 void
-CacheFileIOManager::GetHashStr(const SHA1Sum::Hash *aHash, nsACString &_retval)
+CacheFileIOManager::HashToStr(const SHA1Sum::Hash *aHash, nsACString &_retval)
 {
   _retval.Assign("");
   const char hexChars[] = {'0', '1', '2', '3', '4', '5', '6', '7',
                            '8', '9', 'A', 'B', 'C', 'D', 'E', 'F'};
   for (uint32_t i=0 ; i<sizeof(SHA1Sum::Hash) ; i++) {
     _retval.Append(hexChars[(*aHash)[i] >> 4]);
     _retval.Append(hexChars[(*aHash)[i] & 0xF]);
   }
 }
 
 nsresult
+CacheFileIOManager::StrToHash(const nsACString &aHash, SHA1Sum::Hash *_retval)
+{
+  if (aHash.Length() != 2*sizeof(SHA1Sum::Hash))
+    return NS_ERROR_INVALID_ARG;
+
+  for (uint32_t i=0 ; i<aHash.Length() ; i++) {
+    uint8_t value;
+
+    if (aHash[i] >= '0' && aHash[i] <= '9')
+      value = aHash[i] - '0';
+    else if (aHash[i] >= 'A' && aHash[i] <= 'F')
+      value = aHash[i] - 'A' + 10;
+    else if (aHash[i] >= 'a' && aHash[i] <= 'f')
+      value = aHash[i] - 'a' + 10;
+    else
+      return NS_ERROR_INVALID_ARG;
+
+    if (i%2 == 0)
+      (reinterpret_cast<uint8_t *>(_retval))[i/2] = value << 4;
+    else
+      (reinterpret_cast<uint8_t *>(_retval))[i/2] += value;
+  }
+
+  return NS_OK;
+}
+
+nsresult
 CacheFileIOManager::GetFile(const SHA1Sum::Hash *aHash, nsIFile **_retval)
 {
   nsresult rv;
   nsCOMPtr<nsIFile> file;
   rv = mCacheDirectory->Clone(getter_AddRefs(file));
   NS_ENSURE_SUCCESS(rv, rv);
 
-  rv = file->AppendNative(NS_LITERAL_CSTRING("entries"));
+  rv = file->AppendNative(NS_LITERAL_CSTRING(kEntriesDir));
   NS_ENSURE_SUCCESS(rv, rv);
 
   nsAutoCString leafName;
-  GetHashStr(aHash, leafName);
+  HashToStr(aHash, leafName);
 
   rv = file->AppendNative(leafName);
   NS_ENSURE_SUCCESS(rv, rv);
 
   file.swap(*_retval);
   return NS_OK;
 }
 
 nsresult
+CacheFileIOManager::GetSpecialFile(const nsACString &aKey, nsIFile **_retval)
+{
+  nsresult rv;
+  nsCOMPtr<nsIFile> file;
+  rv = mCacheDirectory->Clone(getter_AddRefs(file));
+  NS_ENSURE_SUCCESS(rv, rv);
+
+  rv = file->AppendNative(aKey);
+  NS_ENSURE_SUCCESS(rv, rv);
+
+  file.swap(*_retval);
+  return NS_OK;
+}
+
+nsresult
 CacheFileIOManager::GetDoomedFile(nsIFile **_retval)
 {
   nsresult rv;
   nsCOMPtr<nsIFile> file;
   rv = mCacheDirectory->Clone(getter_AddRefs(file));
   NS_ENSURE_SUCCESS(rv, rv);
 
-  rv = file->AppendNative(NS_LITERAL_CSTRING("doomed"));
+  rv = file->AppendNative(NS_LITERAL_CSTRING(kDoomedDir));
   NS_ENSURE_SUCCESS(rv, rv);
 
   rv = file->AppendNative(NS_LITERAL_CSTRING("dummyleaf"));
   NS_ENSURE_SUCCESS(rv, rv);
 
   srand(static_cast<unsigned>(PR_Now()));
   nsAutoCString leafName;
   uint32_t iter=0;
@@ -1828,34 +2442,36 @@ CacheFileIOManager::CreateCacheTree()
   rv = CheckAndCreateDir(parentDir, nullptr);
   NS_ENSURE_SUCCESS(rv, rv);
 
   // ensure cache directory exists
   rv = CheckAndCreateDir(mCacheDirectory, nullptr);
   NS_ENSURE_SUCCESS(rv, rv);
 
   // ensure entries directory exists
-  rv = CheckAndCreateDir(mCacheDirectory, "entries");
+  rv = CheckAndCreateDir(mCacheDirectory, kEntriesDir);
   NS_ENSURE_SUCCESS(rv, rv);
 
   // ensure doomed directory exists
-  rv = CheckAndCreateDir(mCacheDirectory, "doomed");
+  rv = CheckAndCreateDir(mCacheDirectory, kDoomedDir);
   NS_ENSURE_SUCCESS(rv, rv);
 
   mTreeCreated = true;
   return NS_OK;
 }
 
 nsresult
 CacheFileIOManager::OpenNSPRHandle(CacheFileHandle *aHandle, bool aCreate)
 {
   MOZ_ASSERT(CacheFileIOManager::IsOnIOThreadOrCeased());
   MOZ_ASSERT(!aHandle->mFD);
   MOZ_ASSERT(mHandlesByLastUsed.IndexOf(aHandle) == mHandlesByLastUsed.NoIndex);
   MOZ_ASSERT(mHandlesByLastUsed.Length() <= kOpenHandlesLimit);
+  MOZ_ASSERT((aCreate && !aHandle->mFileExists) ||
+             (!aCreate && aHandle->mFileExists));
 
   nsresult rv;
 
   if (mHandlesByLastUsed.Length() == kOpenHandlesLimit) {
     // close handle that hasn't been used for the longest time
     rv = ReleaseNSPRHandleInternal(mHandlesByLastUsed[0]);
     NS_ENSURE_SUCCESS(rv, rv);
   }
@@ -1867,18 +2483,17 @@ CacheFileIOManager::OpenNSPRHandle(Cache
 
     aHandle->mFileExists = true;
   }
   else {
     rv = aHandle->mFile->OpenNSPRFileDesc(PR_RDWR, 0600, &aHandle->mFD);
     if (NS_ERROR_FILE_NOT_FOUND == rv) {
       LOG(("  file doesn't exists"));
       aHandle->mFileExists = false;
-      aHandle->mIsDoomed = true;
-      return NS_OK;
+      return DoomFileInternal(aHandle);
     }
     NS_ENSURE_SUCCESS(rv, rv);
   }
 
   mHandlesByLastUsed.AppendElement(aHandle);
   return NS_OK;
 }
 
--- a/netwerk/cache2/CacheFileIOManager.h
+++ b/netwerk/cache2/CacheFileIOManager.h
@@ -11,35 +11,49 @@
 #include "nsITimer.h"
 #include "nsCOMPtr.h"
 #include "mozilla/SHA1.h"
 #include "nsTArray.h"
 #include "nsString.h"
 #include "nsTHashtable.h"
 #include "prio.h"
 
+//#define DEBUG_HANDLES 1
+
 class nsIFile;
 
 namespace mozilla {
 namespace net {
 
+#ifdef DEBUG_HANDLES
+class CacheFileHandlesEntry;
+#endif
+
+const char kEntriesDir[] = "entries";
+const char kDoomedDir[]  = "doomed";
+
+
 class CacheFileHandle : public nsISupports
 {
 public:
   NS_DECL_THREADSAFE_ISUPPORTS
   bool DispatchRelease();
 
   CacheFileHandle(const SHA1Sum::Hash *aHash, bool aPriority);
+  CacheFileHandle(const nsACString &aKey, bool aPriority);
   CacheFileHandle(const CacheFileHandle &aOther);
+  void Log();
   bool IsDoomed() { return mIsDoomed; }
   const SHA1Sum::Hash *Hash() { return mHash; }
   int64_t FileSize() { return mFileSize; }
+  uint32_t FileSizeInK();
   bool IsPriority() { return mPriority; }
   bool FileExists() { return mFileExists; }
   bool IsClosed() { return mClosed; }
+  bool IsSpecialFile() { return !mHash; }
   nsCString & Key() { return mKey; }
 
 private:
   friend class CacheFileIOManager;
   friend class CacheFileHandles;
   friend class ReleaseNSPRHandleEvent;
 
   virtual ~CacheFileHandle();
@@ -66,16 +80,20 @@ public:
 
   nsresult GetHandle(const SHA1Sum::Hash *aHash, bool aReturnDoomed, CacheFileHandle **_retval);
   nsresult NewHandle(const SHA1Sum::Hash *aHash, bool aPriority, CacheFileHandle **_retval);
   void     RemoveHandle(CacheFileHandle *aHandlle);
   void     GetAllHandles(nsTArray<nsRefPtr<CacheFileHandle> > *_retval);
   void     ClearAll();
   uint32_t HandleCount();
 
+#ifdef DEBUG_HANDLES
+  void     Log(CacheFileHandlesEntry *entry);
+#endif
+
   class HandleHashKey : public PLDHashEntryHdr
   {
   public:
     typedef const SHA1Sum::Hash& KeyType;
     typedef const SHA1Sum::Hash* KeyTypePointer;
 
     HandleHashKey(KeyTypePointer aKey)
     {
@@ -155,42 +173,45 @@ public:
 
   NS_IMETHOD OnFileOpened(CacheFileHandle *aHandle, nsresult aResult) = 0;
   NS_IMETHOD OnDataWritten(CacheFileHandle *aHandle, const char *aBuf,
                            nsresult aResult) = 0;
   NS_IMETHOD OnDataRead(CacheFileHandle *aHandle, char *aBuf,
                         nsresult aResult) = 0;
   NS_IMETHOD OnFileDoomed(CacheFileHandle *aHandle, nsresult aResult) = 0;
   NS_IMETHOD OnEOFSet(CacheFileHandle *aHandle, nsresult aResult) = 0;
+  NS_IMETHOD OnFileRenamed(CacheFileHandle *aHandle, nsresult aResult) = 0;
 };
 
 NS_DEFINE_STATIC_IID_ACCESSOR(CacheFileIOListener, CACHEFILEIOLISTENER_IID)
 
 
 class CacheFileIOManager : public nsITimerCallback
 {
 public:
   NS_DECL_THREADSAFE_ISUPPORTS
   NS_DECL_NSITIMERCALLBACK
 
   enum {
-    OPEN       = 0U,
-    CREATE     = 1U,
-    CREATE_NEW = 2U,
-    PRIORITY   = 4U,
-    NOHASH     = 8U
+    OPEN         = 0U,
+    CREATE       = 1U,
+    CREATE_NEW   = 2U,
+    PRIORITY     = 4U,
+    NOHASH       = 8U,
+    SPECIAL_FILE = 16U
   };
 
   CacheFileIOManager();
 
   static nsresult Init();
   static nsresult Shutdown();
   static nsresult OnProfile();
   static already_AddRefed<nsIEventTarget> IOTarget();
   static already_AddRefed<CacheIOThread> IOThread();
+  static bool IsOnIOThread();
   static bool IsOnIOThreadOrCeased();
   static bool IsShutdown();
 
   // Make aFile's WriteMetadataIfNeeded be called automatically after
   // a short interval.
   static nsresult ScheduleMetadataWrite(CacheFile * aFile);
   // Remove aFile from the scheduling registry array.
   // WriteMetadataIfNeeded will not be automatically called.
@@ -210,16 +231,28 @@ public:
   static nsresult DoomFile(CacheFileHandle *aHandle,
                            CacheFileIOListener *aCallback);
   static nsresult DoomFileByKey(const nsACString &aKey,
                                 CacheFileIOListener *aCallback);
   static nsresult ReleaseNSPRHandle(CacheFileHandle *aHandle);
   static nsresult TruncateSeekSetEOF(CacheFileHandle *aHandle,
                                      int64_t aTruncatePos, int64_t aEOFPos,
                                      CacheFileIOListener *aCallback);
+  static nsresult RenameFile(CacheFileHandle *aHandle,
+                             const nsACString &aNewName,
+                             CacheFileIOListener *aCallback);
+  static nsresult InitIndexEntry(CacheFileHandle *aHandle,
+                                 uint32_t         aAppId,
+                                 bool             aAnonymous,
+                                 bool             aInBrowser);
+  static nsresult UpdateIndexEntry(CacheFileHandle *aHandle,
+                                   const uint32_t  *aFrecency,
+                                   const uint32_t  *aExpirationTime);
+
+  static nsresult UpdateIndexEntry();
 
   enum EEnumerateMode {
     ENTRIES,
     DOOMED
   };
 
   static nsresult EnumerateEntryFiles(EEnumerateMode aMode,
                                       CacheEntriesEnumerator** aEnumerator);
@@ -234,57 +267,67 @@ private:
   friend class OpenFileEvent;
   friend class CloseHandleEvent;
   friend class ReadEvent;
   friend class WriteEvent;
   friend class DoomFileEvent;
   friend class DoomFileByKeyEvent;
   friend class ReleaseNSPRHandleEvent;
   friend class TruncateSeekSetEOFEvent;
+  friend class RenameFileEvent;
+  friend class CacheIndex;
   friend class MetadataWriteScheduleEvent;
 
   virtual ~CacheFileIOManager();
 
   nsresult InitInternal();
   nsresult ShutdownInternal();
 
   nsresult OpenFileInternal(const SHA1Sum::Hash *aHash,
                             uint32_t aFlags,
                             CacheFileHandle **_retval);
+  nsresult OpenSpecialFileInternal(const nsACString &aKey,
+                                   uint32_t aFlags,
+                                   CacheFileHandle **_retval);
   nsresult CloseHandleInternal(CacheFileHandle *aHandle);
   nsresult ReadInternal(CacheFileHandle *aHandle, int64_t aOffset,
                         char *aBuf, int32_t aCount);
   nsresult WriteInternal(CacheFileHandle *aHandle, int64_t aOffset,
                          const char *aBuf, int32_t aCount, bool aValidate);
   nsresult DoomFileInternal(CacheFileHandle *aHandle);
   nsresult DoomFileByKeyInternal(const SHA1Sum::Hash *aHash);
   nsresult ReleaseNSPRHandleInternal(CacheFileHandle *aHandle);
   nsresult TruncateSeekSetEOFInternal(CacheFileHandle *aHandle,
                                       int64_t aTruncatePos, int64_t aEOFPos);
+  nsresult RenameFileInternal(CacheFileHandle *aHandle,
+                              const nsACString &aNewName);
 
   nsresult CreateFile(CacheFileHandle *aHandle);
-  static void GetHashStr(const SHA1Sum::Hash *aHash, nsACString &_retval);
+  static void HashToStr(const SHA1Sum::Hash *aHash, nsACString &_retval);
+  static nsresult StrToHash(const nsACString &aHash, SHA1Sum::Hash *_retval);
   nsresult GetFile(const SHA1Sum::Hash *aHash, nsIFile **_retval);
+  nsresult GetSpecialFile(const nsACString &aKey, nsIFile **_retval);
   nsresult GetDoomedFile(nsIFile **_retval);
   nsresult CheckAndCreateDir(nsIFile *aFile, const char *aDir);
   nsresult CreateCacheTree();
   nsresult OpenNSPRHandle(CacheFileHandle *aHandle, bool aCreate = false);
   void     NSPRHandleUsed(CacheFileHandle *aHandle);
 
   nsresult ScheduleMetadataWriteInternal(CacheFile * aFile);
   nsresult UnscheduleMetadataWriteInternal(CacheFile * aFile);
   nsresult ShutdownMetadataWriteSchedulingInternal();
 
-  static CacheFileIOManager  *gInstance;
-  bool                        mShuttingDown;
-  nsRefPtr<CacheIOThread>     mIOThread;
-  nsCOMPtr<nsIFile>           mCacheDirectory;
-  bool                        mTreeCreated;
-  CacheFileHandles            mHandles;
-  nsTArray<CacheFileHandle *> mHandlesByLastUsed;
-  nsTArray<nsRefPtr<CacheFile> > mScheduledMetadataWrites;
-  nsCOMPtr<nsITimer>          mMetadataWritesTimer;
+  static CacheFileIOManager           *gInstance;
+  bool                                 mShuttingDown;
+  nsRefPtr<CacheIOThread>              mIOThread;
+  nsCOMPtr<nsIFile>                    mCacheDirectory;
+  bool                                 mTreeCreated;
+  CacheFileHandles                     mHandles;
+  nsTArray<CacheFileHandle *>          mHandlesByLastUsed;
+  nsTArray<nsRefPtr<CacheFileHandle> > mSpecialHandles;
+  nsTArray<nsRefPtr<CacheFile> >       mScheduledMetadataWrites;
+  nsCOMPtr<nsITimer>                   mMetadataWritesTimer;
 };
 
 } // net
 } // mozilla
 
 #endif
--- a/netwerk/cache2/CacheFileMetadata.cpp
+++ b/netwerk/cache2/CacheFileMetadata.cpp
@@ -1,53 +1,63 @@
 /* This Source Code Form is subject to the terms of the Mozilla Public
  * License, v. 2.0. If a copy of the MPL was not distributed with this
  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
 
 #include "CacheLog.h"
 #include "CacheFileMetadata.h"
 
 #include "CacheFileIOManager.h"
+#include "nsICacheEntry.h"
 #include "CacheHashUtils.h"
 #include "CacheFileChunk.h"
+#include "nsILoadContextInfo.h"
 #include "../cache/nsCacheUtils.h"
+#include "nsIFile.h"
 #include "mozilla/Telemetry.h"
+#include "mozilla/DebugOnly.h"
 #include "prnetdb.h"
 
 
 namespace mozilla {
 namespace net {
 
 #define kMinMetadataRead 1024  // TODO find optimal value from telemetry
 #define kAlignSize       4096
 
-#define NO_EXPIRATION_TIME 0xFFFFFFFF
-
 NS_IMPL_ISUPPORTS1(CacheFileMetadata, CacheFileIOListener)
 
 CacheFileMetadata::CacheFileMetadata(CacheFileHandle *aHandle, const nsACString &aKey, bool aKeyIsHash)
   : mHandle(aHandle)
   , mKeyIsHash(aKeyIsHash)
   , mHashArray(nullptr)
   , mHashArraySize(0)
   , mHashCount(0)
   , mOffset(-1)
   , mBuf(nullptr)
   , mBufSize(0)
   , mWriteBuf(nullptr)
   , mElementsSize(0)
   , mIsDirty(false)
+  , mAnonymous(false)
+  , mInBrowser(false)
+  , mAppId(nsILoadContextInfo::NO_APP_ID)
 {
   LOG(("CacheFileMetadata::CacheFileMetadata() [this=%p, handle=%p, key=%s]",
        this, aHandle, PromiseFlatCString(aKey).get()));
 
   MOZ_COUNT_CTOR(CacheFileMetadata);
   memset(&mMetaHdr, 0, sizeof(CacheFileMetadataHeader));
-  mMetaHdr.mExpirationTime = NO_EXPIRATION_TIME;
+  mMetaHdr.mExpirationTime = nsICacheEntry::NO_EXPIRATION_TIME;
   mKey = aKey;
+  if (!aKeyIsHash) {
+    DebugOnly<nsresult> rv;
+    rv = ParseKey(aKey);
+    MOZ_ASSERT(NS_SUCCEEDED(rv));
+  }
 }
 
 CacheFileMetadata::~CacheFileMetadata()
 {
   LOG(("CacheFileMetadata::~CacheFileMetadata() [this=%p]", this));
 
   MOZ_COUNT_DTOR(CacheFileMetadata);
   MOZ_ASSERT(!mListener);
@@ -74,26 +84,55 @@ CacheFileMetadata::CacheFileMetadata(con
   , mHashArraySize(0)
   , mHashCount(0)
   , mOffset(0)
   , mBuf(nullptr)
   , mBufSize(0)
   , mWriteBuf(nullptr)
   , mElementsSize(0)
   , mIsDirty(true)
+  , mAnonymous(false)
+  , mInBrowser(false)
+  , mAppId(nsILoadContextInfo::NO_APP_ID)
 {
   LOG(("CacheFileMetadata::CacheFileMetadata() [this=%p, key=%s]",
        this, PromiseFlatCString(aKey).get()));
 
   MOZ_COUNT_CTOR(CacheFileMetadata);
   memset(&mMetaHdr, 0, sizeof(CacheFileMetadataHeader));
-  mMetaHdr.mExpirationTime = NO_EXPIRATION_TIME;
+  mMetaHdr.mExpirationTime = nsICacheEntry::NO_EXPIRATION_TIME;
   mMetaHdr.mFetchCount++;
   mKey = aKey;
   mMetaHdr.mKeySize = mKey.Length();
+
+  DebugOnly<nsresult> rv;
+  rv = ParseKey(aKey);
+  MOZ_ASSERT(NS_SUCCEEDED(rv));
+}
+
+CacheFileMetadata::CacheFileMetadata()
+  : mHandle(nullptr)
+  , mKeyIsHash(false)
+  , mHashArray(nullptr)
+  , mHashArraySize(0)
+  , mHashCount(0)
+  , mOffset(0)
+  , mBuf(nullptr)
+  , mBufSize(0)
+  , mWriteBuf(nullptr)
+  , mElementsSize(0)
+  , mIsDirty(false)
+  , mAnonymous(false)
+  , mInBrowser(false)
+  , mAppId(nsILoadContextInfo::NO_APP_ID)
+{
+  LOG(("CacheFileMetadata::CacheFileMetadata() [this=%p]", this));
+
+  MOZ_COUNT_CTOR(CacheFileMetadata);
+  memset(&mMetaHdr, 0, sizeof(CacheFileMetadataHeader));
 }
 
 void
 CacheFileMetadata::SetHandle(CacheFileHandle *aHandle)
 {
   LOG(("CacheFileMetadata::SetHandle() [this=%p, handle=%p]", this, aHandle));
 
   MOZ_ASSERT(!mHandle);
@@ -216,35 +255,35 @@ CacheFileMetadata::WriteMetadata(uint32_
   MOZ_ASSERT(!mWriteBuf);
   MOZ_ASSERT(!mKeyIsHash);
 
   nsresult rv;
 
   mIsDirty = false;
 
   mWriteBuf = static_cast<char *>(moz_xmalloc(sizeof(uint32_t) +
-                mHashCount * sizeof(CacheHashUtils::Hash16_t) +
+                mHashCount * sizeof(CacheHash::Hash16_t) +
                 sizeof(CacheFileMetadataHeader) + mKey.Length() + 1 +
                 mElementsSize + sizeof(uint32_t)));
 
   char *p = mWriteBuf + sizeof(uint32_t);
-  memcpy(p, mHashArray, mHashCount * sizeof(CacheHashUtils::Hash16_t));
-  p += mHashCount * sizeof(CacheHashUtils::Hash16_t);
+  memcpy(p, mHashArray, mHashCount * sizeof(CacheHash::Hash16_t));
+  p += mHashCount * sizeof(CacheHash::Hash16_t);
   memcpy(p, &mMetaHdr, sizeof(CacheFileMetadataHeader));
   p += sizeof(CacheFileMetadataHeader);
   memcpy(p, mKey.get(), mKey.Length());
   p += mKey.Length();
   *p = 0;
   p++;
   memcpy(p, mBuf, mElementsSize);
   p += mElementsSize;
 
-  CacheHashUtils::Hash32_t hash;
-  hash = CacheHashUtils::Hash(mWriteBuf + sizeof(uint32_t),
-                              p - mWriteBuf - sizeof(uint32_t));
+  CacheHash::Hash32_t hash;
+  hash = CacheHash::Hash(mWriteBuf + sizeof(uint32_t),
+                         p - mWriteBuf - sizeof(uint32_t));
   *reinterpret_cast<uint32_t *>(mWriteBuf) = PR_htonl(hash);
 
   *reinterpret_cast<uint32_t *>(p) = PR_htonl(aOffset);
   p += sizeof(uint32_t);
 
   char * writeBuffer;
   if (aListener) {
     mListener = aListener;
@@ -275,16 +314,82 @@ CacheFileMetadata::WriteMetadata(uint32_
     NS_ENSURE_SUCCESS(rv, rv);
   }
 
   DoMemoryReport(MemoryUsage());
 
   return NS_OK;
 }
 
+nsresult
+CacheFileMetadata::SyncReadMetadata(nsIFile *aFile)
+{
+  LOG(("CacheFileMetadata::SyncReadMetadata() [this=%p]", this));
+
+  MOZ_ASSERT(!mListener);
+  MOZ_ASSERT(!mHandle);
+  MOZ_ASSERT(!mHashArray);
+  MOZ_ASSERT(!mBuf);
+  MOZ_ASSERT(!mWriteBuf);
+  MOZ_ASSERT(mKey.IsEmpty());
+
+  nsresult rv;
+
+  int64_t fileSize;
+  rv = aFile->GetFileSize(&fileSize);
+  NS_ENSURE_SUCCESS(rv, rv);
+
+  PRFileDesc *fd;
+  rv = aFile->OpenNSPRFileDesc(PR_RDONLY, 0600, &fd);
+  NS_ENSURE_SUCCESS(rv, rv);
+
+  int64_t offset = PR_Seek64(fd, fileSize - sizeof(uint32_t), PR_SEEK_SET);
+  if (offset == -1) {
+    PR_Close(fd);
+    return NS_ERROR_FAILURE;
+  }
+
+  uint32_t metaOffset;
+  int32_t bytesRead = PR_Read(fd, &metaOffset, sizeof(uint32_t));
+  if (bytesRead != sizeof(uint32_t)) {
+    PR_Close(fd);
+    return NS_ERROR_FAILURE;
+  }
+
+  metaOffset = PR_ntohl(metaOffset);
+  if (metaOffset > fileSize) {
+    PR_Close(fd);
+    return NS_ERROR_FAILURE;
+  }
+
+  mBufSize = fileSize - metaOffset;
+  mBuf = static_cast<char *>(moz_xmalloc(mBufSize));
+
+  DoMemoryReport(MemoryUsage());
+
+  offset = PR_Seek64(fd, metaOffset, PR_SEEK_SET);
+  if (offset == -1) {
+    PR_Close(fd);
+    return NS_ERROR_FAILURE;
+  }
+
+  bytesRead = PR_Read(fd, mBuf, mBufSize);
+  PR_Close(fd);
+  if (bytesRead != static_cast<int32_t>(mBufSize)) {
+    return NS_ERROR_FAILURE;
+  }
+
+  mKeyIsHash = true;
+
+  rv = ParseMetadata(metaOffset, 0);
+  NS_ENSURE_SUCCESS(rv, rv);
+
+  return NS_OK;
+}
+
 const char *
 CacheFileMetadata::GetElement(const char *aKey)
 {
   const char *data = mBuf;
   const char *limit = mBuf + mElementsSize;
 
   while (data < limit) {
     // Point to the value part
@@ -356,43 +461,43 @@ CacheFileMetadata::SetElement(const char
 
   // Update value
   memcpy(pos, aValue, valueSize);
   mElementsSize = newSize;
 
   return NS_OK;
 }
 
-CacheHashUtils::Hash16_t
+CacheHash::Hash16_t
 CacheFileMetadata::GetHash(uint32_t aIndex)
 {
   MOZ_ASSERT(aIndex < mHashCount);
   return PR_ntohs(mHashArray[aIndex]);
 }
 
 nsresult
-CacheFileMetadata::SetHash(uint32_t aIndex, CacheHashUtils::Hash16_t aHash)
+CacheFileMetadata::SetHash(uint32_t aIndex, CacheHash::Hash16_t aHash)
 {
   LOG(("CacheFileMetadata::SetHash() [this=%p, idx=%d, hash=%x]",
        this, aIndex, aHash));
 
   MarkDirty();
 
   MOZ_ASSERT(aIndex <= mHashCount);
 
   if (aIndex > mHashCount) {
     return NS_ERROR_INVALID_ARG;
   } else if (aIndex == mHashCount) {
-    if ((aIndex + 1) * sizeof(CacheHashUtils::Hash16_t) > mHashArraySize) {
+    if ((aIndex + 1) * sizeof(CacheHash::Hash16_t) > mHashArraySize) {
       // reallocate hash array buffer
       if (mHashArraySize == 0)
-        mHashArraySize = 32 * sizeof(CacheHashUtils::Hash16_t);
+        mHashArraySize = 32 * sizeof(CacheHash::Hash16_t);
       else
         mHashArraySize *= 2;
-      mHashArray = static_cast<CacheHashUtils::Hash16_t *>(
+      mHashArray = static_cast<CacheHash::Hash16_t *>(
                      moz_xrealloc(mHashArray, mHashArraySize));
     }
 
     mHashCount++;
   }
 
   mHashArray[aIndex] = PR_htons(aHash);
 
@@ -641,27 +746,34 @@ CacheFileMetadata::OnFileDoomed(CacheFil
 
 nsresult
 CacheFileMetadata::OnEOFSet(CacheFileHandle *aHandle, nsresult aResult)
 {
   MOZ_CRASH("CacheFileMetadata::OnEOFSet should not be called!");
   return NS_ERROR_UNEXPECTED;
 }
 
+nsresult
+CacheFileMetadata::OnFileRenamed(CacheFileHandle *aHandle, nsresult aResult)
+{
+  MOZ_CRASH("CacheFileMetadata::OnFileRenamed should not be called!");
+  return NS_ERROR_UNEXPECTED;
+}
+
 void
 CacheFileMetadata::InitEmptyMetadata()
 {
   if (mBuf) {
     free(mBuf);
     mBuf = nullptr;
     mBufSize = 0;
   }
   mOffset = 0;
   mMetaHdr.mFetchCount = 1;
-  mMetaHdr.mExpirationTime = NO_EXPIRATION_TIME;
+  mMetaHdr.mExpirationTime = nsICacheEntry::NO_EXPIRATION_TIME;
   mMetaHdr.mKeySize = mKey.Length();
 
   DoMemoryReport(MemoryUsage());
 }
 
 nsresult
 CacheFileMetadata::ParseMetadata(uint32_t aMetaOffset, uint32_t aBufOffset)
 {
@@ -670,17 +782,17 @@ CacheFileMetadata::ParseMetadata(uint32_
 
   nsresult rv;
 
   uint32_t metaposOffset = mBufSize - sizeof(uint32_t);
   uint32_t hashesOffset = aBufOffset + sizeof(uint32_t);
   uint32_t hashCount = aMetaOffset / kChunkSize;
   if (aMetaOffset % kChunkSize)
     hashCount++;
-  uint32_t hashesLen = hashCount * sizeof(CacheHashUtils::Hash16_t);
+  uint32_t hashesLen = hashCount * sizeof(CacheHash::Hash16_t);
   uint32_t hdrOffset = hashesOffset + hashesLen;
   uint32_t keyOffset = hdrOffset + sizeof(CacheFileMetadataHeader);
 
   LOG(("CacheFileMetadata::ParseMetadata() [this=%p]\n  metaposOffset=%d\n  "
        "hashesOffset=%d\n  hashCount=%d\n  hashesLen=%d\n  hdfOffset=%d\n  "
        "keyOffset=%d\n", this, metaposOffset, hashesOffset, hashCount,
        hashesLen,hdrOffset, keyOffset));
 
@@ -709,52 +821,55 @@ CacheFileMetadata::ParseMetadata(uint32_
   nsAutoCString origKey;
 
   uint32_t keySize = reinterpret_cast<CacheFileMetadataHeader *>(
                        mBuf + hdrOffset)->mKeySize;
 
   if (mKeyIsHash) {
     // get the original key
     origKey.Assign(mBuf + keyOffset, keySize);
+
+    rv = ParseKey(origKey);
+    if (NS_FAILED(rv))
+      return rv;
   }
   else {
     if (keySize != mKey.Length()) {
       LOG(("CacheFileMetadata::ParseMetadata() - Key collision (1), key=%s "
            "[this=%p]", nsCString(mBuf + keyOffset, keySize).get(), this));
       return NS_ERROR_FILE_CORRUPTED;
     }
 
     if (memcmp(mKey.get(), mBuf + keyOffset, mKey.Length()) != 0) {
       LOG(("CacheFileMetadata::ParseMetadata() - Key collision (2), key=%s "
            "[this=%p]", nsCString(mBuf + keyOffset, keySize).get(), this));
       return NS_ERROR_FILE_CORRUPTED;
     }
   }
 
   // check metadata hash (data from hashesOffset to metaposOffset)
-  CacheHashUtils::Hash32_t hash;
-  hash = CacheHashUtils::Hash(mBuf + hashesOffset,
-                              metaposOffset - hashesOffset);
+  CacheHash::Hash32_t hash;
+  hash = CacheHash::Hash(mBuf + hashesOffset, metaposOffset - hashesOffset);
 
   if (hash != PR_ntohl(*(reinterpret_cast<uint32_t *>(mBuf + aBufOffset)))) {
     LOG(("CacheFileMetadata::ParseMetadata() - Metadata hash mismatch! Hash of "
          "the metadata is %x, hash in file is %x [this=%p]", hash,
          PR_ntohl(*(reinterpret_cast<uint32_t *>(mBuf + aBufOffset))), this));
     return NS_ERROR_FILE_CORRUPTED;
   }
 
   // check elements
   rv = CheckElements(mBuf + elementsOffset, metaposOffset - elementsOffset);
   if (NS_FAILED(rv))
     return rv;
 
   mHashArraySize = hashesLen;
   mHashCount = hashCount;
   if (mHashArraySize) {
-    mHashArray = static_cast<CacheHashUtils::Hash16_t *>(
+    mHashArray = static_cast<CacheHash::Hash16_t *>(
                    moz_xmalloc(mHashArraySize));
     memcpy(mHashArray, mBuf + hashesOffset, mHashArraySize);
   }
 
   memcpy(&mMetaHdr, mBuf + hdrOffset, sizeof(CacheFileMetadataHeader));
   mMetaHdr.mFetchCount++;
   MarkDirty();
 
@@ -808,10 +923,62 @@ CacheFileMetadata::EnsureBuffer(uint32_t
   if (mBufSize < aSize) {
     mBufSize = aSize;
     mBuf = static_cast<char *>(moz_xrealloc(mBuf, mBufSize));
   }
 
   DoMemoryReport(MemoryUsage());
 }
 
+nsresult
+CacheFileMetadata::ParseKey(const nsACString &aKey)
+{
+  if (aKey.Length() < 4) {
+    return NS_ERROR_FAILURE;
+  }
+
+  if (aKey[1] == '-') {
+    mAnonymous = false;
+  }
+  else if (aKey[1] == 'A') {
+    mAnonymous = true;
+  }
+  else {
+    return NS_ERROR_FAILURE;
+  }
+
+  if (aKey[2] != ':') {
+    return NS_ERROR_FAILURE;
+  }
+
+  int32_t appIdEndIdx = aKey.FindChar(':', 3);
+  if (appIdEndIdx == kNotFound) {
+    return NS_ERROR_FAILURE;
+  }
+
+  if (aKey[appIdEndIdx - 1] == 'B') {
+    mInBrowser = true;
+    appIdEndIdx--;
+  } else {
+    mInBrowser = false;
+  }
+
+  if (appIdEndIdx < 3) {
+    return NS_ERROR_FAILURE;
+  }
+
+  if (appIdEndIdx == 3) {
+    mAppId = nsILoadContextInfo::NO_APP_ID;
+  }
+  else {
+    nsAutoCString appIdStr(Substring(aKey, 3, appIdEndIdx - 3));
+    nsresult rv;
+    int64_t appId64 = appIdStr.ToInteger64(&rv);
+    if (NS_FAILED(rv) || appId64 > PR_UINT32_MAX)
+      return NS_ERROR_FAILURE;
+    mAppId = appId64;
+  }
+
+  return NS_OK;
+}
+
 } // net
 } // mozilla
--- a/netwerk/cache2/CacheFileMetadata.h
+++ b/netwerk/cache2/CacheFileMetadata.h
@@ -60,32 +60,37 @@ class CacheFileMetadata : public CacheFi
 {
 public:
   NS_DECL_THREADSAFE_ISUPPORTS
 
   CacheFileMetadata(CacheFileHandle *aHandle,
                     const nsACString &aKey,
                     bool aKeyIsHash);
   CacheFileMetadata(const nsACString &aKey);
+  CacheFileMetadata();
 
   void SetHandle(CacheFileHandle *aHandle);
 
   nsresult GetKey(nsACString &_retval);
   bool     KeyIsHash();
 
   nsresult ReadMetadata(CacheFileMetadataListener *aListener);
   nsresult WriteMetadata(uint32_t aOffset,
                          CacheFileMetadataListener *aListener);
+  nsresult SyncReadMetadata(nsIFile *aFile);
+
+  bool     IsAnonymous() { return mAnonymous; }
+  bool     IsInBrowser() { return mInBrowser; }
+  uint32_t AppId()       { return mAppId; }
 
   const char * GetElement(const char *aKey);
   nsresult     SetElement(const char *aKey, const char *aValue);
 
-  CacheHashUtils::Hash16_t GetHash(uint32_t aIndex);
-  nsresult                 SetHash(uint32_t aIndex,
-                                   CacheHashUtils::Hash16_t aHash);
+  CacheHash::Hash16_t GetHash(uint32_t aIndex);
+  nsresult            SetHash(uint32_t aIndex, CacheHash::Hash16_t aHash);
 
   nsresult SetExpirationTime(uint32_t aExpirationTime);
   nsresult GetExpirationTime(uint32_t *_retval);
   nsresult SetLastModified(uint32_t aLastModified);
   nsresult GetLastModified(uint32_t *_retval);
   nsresult SetFrecency(uint32_t aFrecency);
   nsresult GetFrecency(uint32_t *_retval);
   nsresult GetLastFetched(uint32_t *_retval);
@@ -98,39 +103,44 @@ public:
   uint32_t MemoryUsage() { return mHashArraySize + mBufSize; }
 
   NS_IMETHOD OnFileOpened(CacheFileHandle *aHandle, nsresult aResult);
   NS_IMETHOD OnDataWritten(CacheFileHandle *aHandle, const char *aBuf,
                            nsresult aResult);
   NS_IMETHOD OnDataRead(CacheFileHandle *aHandle, char *aBuf, nsresult aResult);
   NS_IMETHOD OnFileDoomed(CacheFileHandle *aHandle, nsresult aResult);
   NS_IMETHOD OnEOFSet(CacheFileHandle *aHandle, nsresult aResult);
+  NS_IMETHOD OnFileRenamed(CacheFileHandle *aHandle, nsresult aResult);
 
 private:
   virtual ~CacheFileMetadata();
 
   void     InitEmptyMetadata();
   nsresult ParseMetadata(uint32_t aMetaOffset, uint32_t aBufOffset);
   nsresult CheckElements(const char *aBuf, uint32_t aSize);
   void     EnsureBuffer(uint32_t aSize);
+  nsresult ParseKey(const nsACString &aKey);
 
   nsRefPtr<CacheFileHandle>           mHandle;
   nsCString                           mKey;
   bool                                mKeyIsHash;
-  CacheHashUtils::Hash16_t           *mHashArray;
+  CacheHash::Hash16_t                *mHashArray;
   uint32_t                            mHashArraySize;
   uint32_t                            mHashCount;
   int64_t                             mOffset;
   char                               *mBuf; // used for parsing, then points
                                             // to elements
   uint32_t                            mBufSize;
   char                               *mWriteBuf;
   CacheFileMetadataHeader             mMetaHdr;
   uint32_t                            mElementsSize;
   bool                                mIsDirty;
+  bool                                mAnonymous;
+  bool                                mInBrowser;
+  uint32_t                            mAppId;
   nsCOMPtr<CacheFileMetadataListener> mListener;
 };
 
 
 } // net
 } // mozilla
 
 #endif
--- a/netwerk/cache2/CacheHashUtils.cpp
+++ b/netwerk/cache2/CacheHashUtils.cpp
@@ -5,17 +5,17 @@
 #include "CacheHashUtils.h"
 
 #include "plstr.h"
 
 namespace mozilla {
 namespace net {
 
 /**
- *  CacheHashUtils::Hash(const char * key, uint32_t initval)
+ *  CacheHash::Hash(const char * key, uint32_t initval)
  *
  *  See http://burtleburtle.net/bob/hash/evahash.html for more information
  *  about this hash function.
  *
  *  This algorithm is used to check the data integrity.
  */
 
 static inline void hashmix(uint32_t& a, uint32_t& b, uint32_t& c)
@@ -26,21 +26,21 @@ static inline void hashmix(uint32_t& a, 
   a -= b; a -= c; a ^= (c>>12);
   b -= c; b -= a; b ^= (a<<16);
   c -= a; c -= b; c ^= (b>>5);
   a -= b; a -= c; a ^= (c>>3);
   b -= c; b -= a; b ^= (a<<10);
   c -= a; c -= b; c ^= (b>>15);
 }
 
-CacheHashUtils::Hash32_t
-CacheHashUtils::Hash(const char *aData, uint32_t aSize, uint32_t aInitval)
+CacheHash::Hash32_t
+CacheHash::Hash(const char *aData, uint32_t aSize, uint32_t aInitval)
 {
   const uint8_t *k = reinterpret_cast<const uint8_t*>(aData);
-  uint32_t a, b, c, len/*, length*/;
+  uint32_t a, b, c, len;
 
 //  length = PL_strlen(key);
   /* Set up the internal state */
   len = aSize;
   a = b = 0x9e3779b9;  /* the golden ratio; an arbitrary value */
   c = aInitval;        /* variable initialization of internal state */
 
   /*---------------------------------------- handle most of the key */
@@ -70,18 +70,123 @@ CacheHashUtils::Hash(const char *aData, 
     case 1 : a += k[0];
     /* case 0: nothing left to add */
   }
   hashmix(a, b, c);
 
   return c;
 }
 
-CacheHashUtils::Hash16_t
-CacheHashUtils::Hash16(const char *aData, uint32_t aSize, uint32_t aInitval)
+CacheHash::Hash16_t
+CacheHash::Hash16(const char *aData, uint32_t aSize, uint32_t aInitval)
 {
   Hash32_t hash = Hash(aData, aSize, aInitval);
   return (hash & 0xFFFF);
 }
 
+NS_IMPL_ISUPPORTS0(CacheHash)
+
+CacheHash::CacheHash(uint32_t aInitval)
+  : mA(0x9e3779b9)
+  , mB(0x9e3779b9)
+  , mC(aInitval)
+  , mPos(0)
+  , mBuf(0)
+  , mBufPos(0)
+  , mLength(0)
+  , mFinalized(false)
+{}
+
+void
+CacheHash::Feed(uint32_t aVal, uint8_t aLen)
+{
+  switch (mPos) {
+  case 0:
+    mA += aVal;
+    mPos ++;
+    break;
+
+  case 1:
+    mB += aVal;
+    mPos ++;
+    break;
+
+  case 2:
+    mPos = 0;
+    if (aLen == 4) {
+      mC += aVal;
+      hashmix(mA, mB, mC);
+    }
+    else {
+      mC += aVal << 8;
+    }
+  }
+
+  mLength += aLen;
+}
+
+void
+CacheHash::Update(const char *aData, uint32_t aLen)
+{
+  const uint8_t *data = reinterpret_cast<const uint8_t*>(aData);
+
+  MOZ_ASSERT(!mFinalized);
+
+  if (mBufPos) {
+    while (mBufPos != 4 && aLen) {
+      mBuf += uint32_t(*data) << 8*mBufPos;
+      data++;
+      mBufPos++;
+      aLen--;
+    }
+
+    if (mBufPos == 4) {
+      mBufPos = 0;
+      Feed(mBuf);
+      mBuf = 0;
+    }
+  }
+
+  if (!aLen)
+    return;
+
+  while (aLen >= 4) {
+    Feed(data[0] + (uint32_t(data[1]) << 8) + (uint32_t(data[2]) << 16) +
+         (uint32_t(data[3]) << 24));
+    data += 4;
+    aLen -= 4;
+  }
+
+  switch (aLen) {
+    case 3: mBuf += data[2] << 16;
+    case 2: mBuf += data[1] << 8;
+    case 1: mBuf += data[0];
+  }
+
+  mBufPos = aLen;
+}
+
+CacheHash::Hash32_t
+CacheHash::GetHash()
+{
+  if (!mFinalized)
+  {
+    if (mBufPos) {
+      Feed(mBuf, mBufPos);
+    }
+    mC += mLength;
+    hashmix(mA, mB, mC);
+    mFinalized = true;
+  }
+
+  return mC;
+}
+
+CacheHash::Hash16_t
+CacheHash::GetHash16()
+{
+  Hash32_t hash = GetHash();
+  return (hash & 0xFFFF);
+}
+
 } // net
 } // mozilla
 
--- a/netwerk/cache2/CacheHashUtils.h
+++ b/netwerk/cache2/CacheHashUtils.h
@@ -1,15 +1,16 @@
 /* This Source Code Form is subject to the terms of the Mozilla Public
  * License, v. 2.0. If a copy of the MPL was not distributed with this
  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
 
 #ifndef CacheHashUtils__h__
 #define CacheHashUtils__h__
 
+#include "nsISupports.h"
 #include "mozilla/Types.h"
 #include "prnetdb.h"
 #include "nsPrintfCString.h"
 
 #define LOGSHA1(x) \
     PR_htonl((reinterpret_cast<const uint32_t *>(x))[0]), \
     PR_htonl((reinterpret_cast<const uint32_t *>(x))[1]), \
     PR_htonl((reinterpret_cast<const uint32_t *>(x))[2]), \
@@ -17,24 +18,44 @@
     PR_htonl((reinterpret_cast<const uint32_t *>(x))[4])
 
 #define SHA1STRING(x) \
     (nsPrintfCString("%08x%08x%08x%08x%08x", LOGSHA1(x)).get())
 
 namespace mozilla {
 namespace net {
 
-class CacheHashUtils
+class CacheHash : public nsISupports
 {
 public:
+  NS_DECL_THREADSAFE_ISUPPORTS
+
   typedef uint16_t Hash16_t;
   typedef uint32_t Hash32_t;
 
   static Hash32_t Hash(const char* aData, uint32_t aSize, uint32_t aInitval=0);
   static Hash16_t Hash16(const char* aData, uint32_t aSize,
                          uint32_t aInitval=0);
+
+  CacheHash(uint32_t aInitval=0);
+
+  void     Update(const char *aData, uint32_t aLen);
+  Hash32_t GetHash();
+  Hash16_t GetHash16();
+
+private:
+  virtual ~CacheHash() {}
+
+  void Feed(uint32_t aVal, uint8_t aLen = 4);
+
+  uint32_t mA, mB, mC;
+  uint8_t  mPos;
+  uint32_t mBuf;
+  uint8_t  mBufPos;
+  uint32_t mLength;
+  bool     mFinalized;
 };
 
 
 } // net
 } // mozilla
 
 #endif
--- a/netwerk/cache2/CacheIOThread.h
+++ b/netwerk/cache2/CacheIOThread.h
@@ -30,16 +30,17 @@ public:
     OPEN_PRIORITY,
     READ_PRIORITY,
     OPEN,
     READ,
     WRITE,
     MANAGEMENT,
     CLOSE,
     EVICT,
+    BUILD_OR_UPDATE_INDEX,
     LAST_LEVEL
   };
 
   nsresult Init();
   nsresult Dispatch(nsIRunnable* aRunnable, uint32_t aLevel);
   bool IsCurrentThread();
   nsresult Shutdown();
   already_AddRefed<nsIEventTarget> Target();
new file mode 100644
--- /dev/null
+++ b/netwerk/cache2/CacheIndex.cpp
@@ -0,0 +1,3178 @@
+/* This Source Code Form is subject to the terms of the Mozilla Public
+ * License, v. 2.0. If a copy of the MPL was not distributed with this
+ * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
+
+#include "CacheIndex.h"
+
+#include "CacheLog.h"
+#include "CacheFileIOManager.h"
+#include "CacheFileMetadata.h"
+#include "nsThreadUtils.h"
+#include "nsISimpleEnumerator.h"
+#include "nsIDirectoryEnumerator.h"
+#include "nsPrintfCString.h"
+#include "mozilla/DebugOnly.h"
+#include "prinrval.h"
+#include "nsIFile.h"
+#include "nsITimer.h"
+#include <algorithm>
+
+
+#define kMinUnwrittenChanges   300
+#define kMinDumpInterval       20000 // in milliseconds
+#define kMaxBufSize            16384
+#define kIndexVersion          0x00000001
+#define kBuildIndexStartDelay  10000 // in milliseconds
+#define kUpdateIndexStartDelay 10000 // in milliseconds
+#define kBuildIndexLoopLimit   40    // in milliseconds
+#define kUpdateIndexLoopLimit  40    // in milliseconds
+
+const char kIndexName[]     = "index";
+const char kTempIndexName[] = "index.tmp";
+const char kJournalName[]   = "index.log";
+
+namespace mozilla {
+namespace net {
+
+/**
+ * This helper class is responsible for keeping CacheIndex::mIndexStats,
+ * CacheIndex::mFrecencyArray and CacheIndex::mExpirationArray up to date.
+ */
+class CacheIndexEntryAutoManage
+{
+public:
+  CacheIndexEntryAutoManage(const SHA1Sum::Hash *aHash, CacheIndex *aIndex)
+    : mIndex(aIndex)
+    , mOldRecord(nullptr)
+    , mOldFrecency(0)
+    , mOldExpirationTime(nsICacheEntry::NO_EXPIRATION_TIME)
+    , mDoNotSearchInIndex(false)
+    , mDoNotSearchInUpdates(false)
+  {
+    mHash = aHash;
+    CacheIndexEntry *entry = FindEntry();
+    mIndex->mIndexStats.BeforeChange(entry);
+    if (entry && entry->IsInitialized() && !entry->IsRemoved()) {
+      mOldRecord = entry->mRec;
+      mOldFrecency = entry->mRec->mFrecency;
+      mOldExpirationTime = entry->mRec->mExpirationTime;
+    }
+  }
+
+  ~CacheIndexEntryAutoManage()
+  {
+    CacheIndexEntry *entry = FindEntry();
+    mIndex->mIndexStats.AfterChange(entry);
+    if (!entry || !entry->IsInitialized() || entry->IsRemoved()) {
+      entry = nullptr;
+    }
+
+    if (entry && !mOldRecord) {
+      mIndex->InsertRecordToFrecencyArray(entry->mRec);
+      mIndex->InsertRecordToExpirationArray(entry->mRec);
+    } else if (!entry && mOldRecord) {
+      mIndex->RemoveRecordFromFrecencyArray(mOldRecord);
+      mIndex->RemoveRecordFromExpirationArray(mOldRecord);
+    } else if (entry && mOldRecord) {
+      bool replaceFrecency = false;
+      bool replaceExpiration = false;
+
+      if (entry->mRec != mOldRecord) {
+        // record has a different address, we have to replace it
+        replaceFrecency = replaceExpiration = true;
+      } else {
+        if (entry->mRec->mFrecency != mOldFrecency) {
+          replaceFrecency = true;
+        }
+        if (entry->mRec->mExpirationTime != mOldExpirationTime) {
+          replaceExpiration = true;
+        }
+      }
+
+      if (replaceFrecency) {
+        mIndex->RemoveRecordFromFrecencyArray(mOldRecord);
+        mIndex->InsertRecordToFrecencyArray(entry->mRec);
+      }
+      if (replaceExpiration) {
+        mIndex->RemoveRecordFromExpirationArray(mOldRecord);
+        mIndex->InsertRecordToExpirationArray(entry->mRec);
+      }
+    } else {
+      // both entries were removed or not initialized, do nothing
+    }
+  }
+
+  // We cannot rely on nsTHashtable::GetEntry() in case we are enumerating the
+  // entries and returning PL_DHASH_REMOVE. Destructor is called before the
+  // entry is removed. Caller must call one of following methods to skip
+  // lookup in the hashtable.
+  void DoNotSearchInIndex()   { mDoNotSearchInIndex = true; }
+  void DoNotSearchInUpdates() { mDoNotSearchInUpdates = true; }
+
+private:
+  CacheIndexEntry * FindEntry()
+  {
+    CacheIndexEntry *entry = nullptr;
+
+    switch (mIndex->mState) {
+      case CacheIndex::READING:
+      case CacheIndex::WRITING:
+        if (!mDoNotSearchInUpdates) {
+          entry = mIndex->mPendingUpdates.GetEntry(*mHash);
+        }
+        // no break
+      case CacheIndex::BUILDING:
+      case CacheIndex::UPDATING:
+      case CacheIndex::READY:
+        if (!entry && !mDoNotSearchInIndex) {
+          entry = mIndex->mIndex.GetEntry(*mHash);
+        }
+        break;
+      case CacheIndex::INITIAL:
+      case CacheIndex::SHUTDOWN:
+      default:
+        MOZ_ASSERT(false, "Unexpected state!");
+    }
+
+    return entry;
+  }
+
+  const SHA1Sum::Hash *mHash;
+  nsRefPtr<CacheIndex> mIndex;
+  CacheIndexRecord    *mOldRecord;
+  uint32_t             mOldFrecency;
+  uint32_t             mOldExpirationTime;
+  bool                 mDoNotSearchInIndex;
+  bool                 mDoNotSearchInUpdates;
+};
+
+class CacheIndexAutoLock {
+public:
+  CacheIndexAutoLock(CacheIndex *aIndex)
+    : mIndex(aIndex)
+    , mLocked(true)
+  {
+    mIndex->Lock();
+  }
+  ~CacheIndexAutoLock()
+  {
+    if (mLocked) {
+      mIndex->Unlock();
+    }
+  }
+  void Lock()
+  {
+    MOZ_ASSERT(!mLocked);
+    mIndex->Lock();
+    mLocked = true;
+  }
+  void Unlock()
+  {
+    MOZ_ASSERT(mLocked);
+    mIndex->Unlock();
+    mLocked = false;
+  }
+
+private:
+  nsRefPtr<CacheIndex> mIndex;
+  bool mLocked;
+};
+
+class CacheIndexAutoUnlock {
+public:
+  CacheIndexAutoUnlock(CacheIndex *aIndex)
+    : mIndex(aIndex)
+    , mLocked(false)
+  {
+    mIndex->Unlock();
+  }
+  ~CacheIndexAutoUnlock()
+  {
+    if (!mLocked) {
+      mIndex->Lock();
+    }
+  }
+  void Lock()
+  {
+    MOZ_ASSERT(!mLocked);
+    mIndex->Lock();
+    mLocked = true;
+  }
+  void Unlock()
+  {
+    MOZ_ASSERT(mLocked);
+    mIndex->Unlock();
+    mLocked = false;
+  }
+
+private:
+  nsRefPtr<CacheIndex> mIndex;
+  bool mLocked;
+};
+
+
+CacheIndex * CacheIndex::gInstance = nullptr;
+
+
+NS_IMPL_ADDREF(CacheIndex)
+NS_IMPL_RELEASE(CacheIndex)
+
+NS_INTERFACE_MAP_BEGIN(CacheIndex)
+  NS_INTERFACE_MAP_ENTRY(mozilla::net::CacheFileIOListener)
+  NS_INTERFACE_MAP_ENTRY(nsIRunnable)
+NS_INTERFACE_MAP_END_THREADSAFE
+
+
+CacheIndex::CacheIndex()
+  : mLock("CacheFile.mLock")
+  , mState(INITIAL)
+  , mShuttingDown(false)
+  , mIndexNeedsUpdate(false)
+  , mIndexOnDiskIsValid(false)
+  , mDontMarkIndexClean(false)
+  , mIndexTimeStamp(0)
+  , mSkipEntries(0)
+  , mProcessEntries(0)
+  , mRWBuf(nullptr)
+  , mRWBufSize(0)
+  , mRWBufPos(0)
+  , mReadOpenCount(0)
+  , mReadFailed(false)
+  , mJournalReadSuccessfully(false)
+{
+  LOG(("CacheIndex::CacheIndex [this=%p]", this));
+  MOZ_COUNT_CTOR(CacheIndex);
+  MOZ_ASSERT(!gInstance, "multiple CacheIndex instances!");
+}
+
+CacheIndex::~CacheIndex()
+{
+  LOG(("CacheIndex::~CacheIndex [this=%p]", this));
+  MOZ_COUNT_DTOR(CacheIndex);
+
+  ReleaseBuffer();
+}
+
+inline void
+CacheIndex::Lock()
+{
+  mLock.Lock();
+
+  MOZ_ASSERT(!mIndexStats.StateLogged());
+}
+
+inline void
+CacheIndex::Unlock()
+{
+  MOZ_ASSERT(!mIndexStats.StateLogged());
+
+  mLock.Unlock();
+}
+
+inline void
+CacheIndex::AssertOwnsLock()
+{
+  mLock.AssertCurrentThreadOwns();
+}
+
+// static
+nsresult
+CacheIndex::Init(nsIFile *aCacheDirectory)
+{
+  LOG(("CacheIndex::Init()"));
+
+  MOZ_ASSERT(NS_IsMainThread());
+
+  if (gInstance) {
+    return NS_ERROR_ALREADY_INITIALIZED;
+  }
+
+  nsRefPtr<CacheIndex> idx = new CacheIndex();
+
+  nsresult rv = idx->InitInternal(aCacheDirectory);
+  NS_ENSURE_SUCCESS(rv, rv);
+
+  idx.swap(gInstance);
+  return NS_OK;
+}
+
+nsresult
+CacheIndex::InitInternal(nsIFile *aCacheDirectory)
+{
+  nsresult rv;
+
+  rv = aCacheDirectory->Clone(getter_AddRefs(mCacheDirectory));
+  NS_ENSURE_SUCCESS(rv, rv);
+
+  ChangeState(READING);
+
+  mStartTime = TimeStamp::NowLoRes();
+
+  // dispatch an event since IO manager's path is not initialized yet
+  nsCOMPtr<nsIRunnable> event;
+  event = NS_NewRunnableMethod(this, &CacheIndex::ReadIndexFromDisk);
+
+  rv = NS_DispatchToCurrentThread(event);
+  if (NS_FAILED(rv)) {
+    ChangeState(INITIAL);
+    LOG(("CacheIndex::InitInternal() - Cannot dispatch event"));
+    NS_ENSURE_SUCCESS(rv, rv);
+  }
+
+  return NS_OK;
+}
+
+// static
+nsresult
+CacheIndex::PreShutdown()
+{
+  LOG(("CacheIndex::PreShutdown() [gInstance=%p]", gInstance));
+
+  MOZ_ASSERT(NS_IsMainThread());
+
+  nsresult rv;
+  nsRefPtr<CacheIndex> index = gInstance;
+
+  if (!index) {
+    return NS_ERROR_NOT_INITIALIZED;
+  }
+
+  CacheIndexAutoLock lock(index);
+
+  LOG(("CacheIndex::PreShutdown() - [state=%d, indexOnDiskIsValid=%d, "
+       "dontMarkIndexClean=%d]", index->mState, index->mIndexOnDiskIsValid,
+       index->mDontMarkIndexClean));
+
+  index->mShuttingDown = true;
+
+  if (index->mState == READY) {
+    return NS_OK; // nothing to do
+  }
+
+  nsCOMPtr<nsIRunnable> event;
+  event = NS_NewRunnableMethod(index, &CacheIndex::PreShutdownInternal);
+
+  nsCOMPtr<nsIEventTarget> ioTarget = CacheFileIOManager::IOTarget();
+  MOZ_ASSERT(ioTarget);
+
+  // PreShutdownInternal() will be executed before any queued event on INDEX
+  // level. That's OK since we don't want to wait for any operation in progess.
+  // We need to interrupt it and save journal as quickly as possible.
+  rv = ioTarget->Dispatch(event, nsIEventTarget::DISPATCH_NORMAL);
+  if (NS_FAILED(rv)) {
+    NS_WARNING("CacheIndex::PreShutdown() - Can't dispatch event");
+    LOG(("CacheIndex::PreShutdown() - Can't dispatch event" ));
+    return rv;
+  }
+
+  return NS_OK;
+}
+
+void
+CacheIndex::PreShutdownInternal()
+{
+  CacheIndexAutoLock lock(this);
+
+  LOG(("CacheIndex::PreShutdownInternal() - [state=%d, indexOnDiskIsValid=%d, "
+       "dontMarkIndexClean=%d]", mState, mIndexOnDiskIsValid,
+       mDontMarkIndexClean));
+
+  MOZ_ASSERT(mShuttingDown);
+
+  if (mTimer) {
+    mTimer = nullptr;
+  }
+
+  switch (mState) {
+    case WRITING:
+      FinishWrite(false);
+      break;
+    case READY:
+      // nothing to do, write the journal in Shutdown()
+      break;
+    case READING:
+      FinishRead(false);
+      break;
+    case BUILDING:
+      FinishBuild(false);
+      break;
+    case UPDATING:
+      FinishUpdate(false);
+      break;
+    default:
+      MOZ_ASSERT(false, "Implement me!");
+  }
+
+  // We should end up in READY state
+  MOZ_ASSERT(mState == READY);
+}
+
+// static
+nsresult
+CacheIndex::Shutdown()
+{
+  LOG(("CacheIndex::Shutdown() [gInstance=%p]", gInstance));
+
+  MOZ_ASSERT(NS_IsMainThread());
+
+  nsRefPtr<CacheIndex> index;
+  index.swap(gInstance);
+
+  if (!index) {
+    return NS_ERROR_NOT_INITIALIZED;
+  }
+
+  CacheIndexAutoLock lock(index);
+
+  LOG(("CacheIndex::Shutdown() - [state=%d, indexOnDiskIsValid=%d, "
+       "dontMarkIndexClean=%d]", index->mState, index->mIndexOnDiskIsValid,
+       index->mDontMarkIndexClean));
+
+  MOZ_ASSERT(index->mShuttingDown);
+
+  EState oldState = index->mState;
+  index->ChangeState(SHUTDOWN);
+
+  if (oldState != READY) {
+    LOG(("CacheIndex::Shutdown() - Unexpected state. Did posting of "
+         "PreShutdownInternal() fail?"));
+  }
+
+  switch (oldState) {
+    case WRITING:
+      index->FinishWrite(false);
+      // no break
+    case READY:
+      if (index->mIndexOnDiskIsValid && !index->mDontMarkIndexClean) {
+        if (NS_FAILED(index->WriteLogToDisk())) {
+          index->RemoveIndexFromDisk();
+        }
+      } else {
+        index->RemoveIndexFromDisk();
+      }
+      break;
+    case READING:
+      index->FinishRead(false);
+      break;
+    case BUILDING:
+      index->FinishBuild(false);
+      break;
+    case UPDATING:
+      index->FinishUpdate(false);
+      break;
+    default:
+      MOZ_ASSERT(false, "Unexpected state!");
+  }
+
+  return NS_OK;
+}
+
+// static
+nsresult
+CacheIndex::AddEntry(const SHA1Sum::Hash *aHash)
+{
+  LOG(("CacheIndex::AddEntry() [hash=%08x%08x%08x%08x%08x]", LOGSHA1(aHash)));
+
+  nsRefPtr<CacheIndex> index = gInstance;
+
+  if (!index) {
+    return NS_ERROR_NOT_INITIALIZED;
+  }
+
+  MOZ_ASSERT(CacheFileIOManager::IsOnIOThread());
+
+  CacheIndexAutoLock lock(index);
+
+  if (!index->IsIndexUsable()) {
+    return NS_ERROR_NOT_AVAILABLE;
+  }
+
+  // Getters in CacheIndexStats assert when mStateLogged is true since the
+  // information is incomplete between calls to BeforeChange() and AfterChange()
+  // (i.e. while CacheIndexEntryAutoManage exists). We need to check whether
+  // non-fresh entries exists outside the scope of CacheIndexEntryAutoManage.
+  bool updateIfNonFreshEntriesExist = false;
+
+  {
+    CacheIndexEntryAutoManage entryMng(aHash, index);
+
+    CacheIndexEntry *entry = index->mIndex.GetEntry(*aHash);
+    bool entryRemoved = entry && entry->IsRemoved();
+
+    if (index->mState == READY || index->mState == UPDATING ||
+        index->mState == BUILDING) {
+      MOZ_ASSERT(index->mPendingUpdates.Count() == 0);
+
+      if (entry && !entryRemoved) {
+        // Found entry in index that shouldn't exist.
+
+        if (entry->IsFresh()) {
+          // Someone removed the file on disk while FF is running. Update
+          // process can fix only non-fresh entries (i.e. entries that were not
+          // added within this session). Start update only if we have such
+          // entries.
+          //
+          // TODO: This should be very rare problem. If it turns out not to be
+          // true, change the update process so that it also iterates all
+          // initialized non-empty entries and checks whether the file exists.
+
+          LOG(("CacheIndex::AddEntry() - Cache file was removed outside FF "
+               "process!"));
+
+          updateIfNonFreshEntriesExist = true;
+        } else if (index->mState == READY) {
+          // Index is outdated, update it.
+          LOG(("CacheIndex::AddEntry() - Found entry that shouldn't exist, "
+               "update is needed"));
+          index->mIndexNeedsUpdate = true;
+        } else {
+          // We cannot be here when building index since all entries are fresh
+          // during building.
+          MOZ_ASSERT(index->mState == UPDATING);
+        }
+      }
+
+      if (!entry) {
+        entry = index->mIndex.PutEntry(*aHash);
+      }
+    } else { // WRITING, READING
+      CacheIndexEntry *updated = index->mPendingUpdates.GetEntry(*aHash);
+      bool updatedRemoved = updated && updated->IsRemoved();
+
+      if ((updated && !updatedRemoved) ||
+          (!updated && entry && !entryRemoved && entry->IsFresh())) {
+        // Fresh entry found, so the file was removed outside FF
+        LOG(("CacheIndex::AddEntry() - Cache file was removed outside FF "
+             "process!"));
+
+        updateIfNonFreshEntriesExist = true;
+      } else if (!updated && entry && !entryRemoved) {
+        if (index->mState == WRITING) {
+          LOG(("CacheIndex::AddEntry() - Found entry that shouldn't exist, "
+               "update is needed"));
+          index->mIndexNeedsUpdate = true;
+        }
+        // Ignore if state is READING since the index information is partial
+      }
+
+      updated = index->mPendingUpdates.PutEntry(*aHash);
+      entry = updated;
+    }
+
+    entry->InitNew();
+    entry->MarkDirty();
+    entry->MarkFresh();
+  }
+
+  if (updateIfNonFreshEntriesExist &&
+      index->mIndexStats.Count() != index->mIndexStats.Fresh()) {
+    index->mIndexNeedsUpdate = true;
+  }
+
+  index->StartUpdatingIndexIfNeeded();
+  index->WriteIndexToDiskIfNeeded();
+
+  return NS_OK;
+}
+
+// static
+nsresult
+CacheIndex::EnsureEntryExists(const SHA1Sum::Hash *aHash)
+{
+  LOG(("CacheIndex::EnsureEntryExists() [hash=%08x%08x%08x%08x%08x]",
+       LOGSHA1(aHash)));
+
+  nsRefPtr<CacheIndex> index = gInstance;
+
+  if (!index) {
+    return NS_ERROR_NOT_INITIALIZED;
+  }
+
+  MOZ_ASSERT(CacheFileIOManager::IsOnIOThread());
+
+  CacheIndexAutoLock lock(index);
+
+  if (!index->IsIndexUsable()) {
+    return NS_ERROR_NOT_AVAILABLE;
+  }
+
+  {
+    CacheIndexEntryAutoManage entryMng(aHash, index);
+
+    CacheIndexEntry *entry = index->mIndex.GetEntry(*aHash);
+    bool entryRemoved = entry && entry->IsRemoved();
+
+    if (index->mState == READY || index->mState == UPDATING ||
+        index->mState == BUILDING) {
+      MOZ_ASSERT(index->mPendingUpdates.Count() == 0);
+
+      if (!entry || entryRemoved) {
+        if (entryRemoved && entry->IsFresh()) {
+          // This could happen only if somebody copies files to the entries
+          // directory while FF is running.
+          LOG(("CacheIndex::EnsureEntryExists() - Cache file was added outside "
+               "FF process! Update is needed."));
+          index->mIndexNeedsUpdate = true;
+        } else if (index->mState == READY ||
+                   (entryRemoved && !entry->IsFresh())) {
+          // Removed non-fresh entries can be present as a result of
+          // ProcessJournalEntry()
+          LOG(("CacheIndex::EnsureEntryExists() - Didn't find entry that should"
+               " exist, update is needed"));
+          index->mIndexNeedsUpdate = true;
+        }
+
+        if (!entry) {
+          entry = index->mIndex.PutEntry(*aHash);
+        }
+        entry->InitNew();
+        entry->MarkDirty();
+      }
+      entry->MarkFresh();
+    } else { // WRITING, READING
+      CacheIndexEntry *updated = index->mPendingUpdates.GetEntry(*aHash);
+      bool updatedRemoved = updated && updated->IsRemoved();
+
+      if (updatedRemoved ||
+          (!updated && entryRemoved && entry->IsFresh())) {
+        // Fresh information about missing entry found. This could happen only
+        // if somebody copies files to the entries directory while FF is running.
+        LOG(("CacheIndex::EnsureEntryExists() - Cache file was added outside "
+             "FF process! Update is needed."));
+        index->mIndexNeedsUpdate = true;
+      } else if (!updated && (!entry || entryRemoved)) {
+        if (index->mState == WRITING) {
+          LOG(("CacheIndex::EnsureEntryExists() - Didn't find entry that should"
+               " exist, update is needed"));
+          index->mIndexNeedsUpdate = true;
+        }
+        // Ignore if state is READING since the index information is partial
+      }
+
+      // We don't need entryRemoved and updatedRemoved info anymore
+      if (entryRemoved)   entry = nullptr;
+      if (updatedRemoved) updated = nullptr;
+
+      if (updated) {
+        updated->MarkFresh();
+      } else {
+        if (!entry) {
+          // Create a new entry
+          updated = index->mPendingUpdates.PutEntry(*aHash);
+          updated->InitNew();
+          updated->MarkFresh();
+          updated->MarkDirty();
+        } else {
+          if (!entry->IsFresh()) {
+            // To mark the entry fresh we must make a copy of index entry
+            // since the index is read-only.
+            updated = index->mPendingUpdates.PutEntry(*aHash);
+            *updated = *entry;
+            updated->MarkFresh();
+          }
+        }
+      }
+    }
+  }
+
+  index->StartUpdatingIndexIfNeeded();
+  index->WriteIndexToDiskIfNeeded();
+
+  return NS_OK;
+}
+
+// static
+nsresult
+CacheIndex::InitEntry(const SHA1Sum::Hash *aHash,
+                      uint32_t             aAppId,
+                      bool                 aAnonymous,
+                      bool                 aInBrowser)
+{
+  LOG(("CacheIndex::InitEntry() [hash=%08x%08x%08x%08x%08x, appId=%u, "
+       "anonymous=%d, inBrowser=%d]", LOGSHA1(aHash), aAppId, aAnonymous,
+       aInBrowser));
+
+  nsRefPtr<CacheIndex> index = gInstance;
+
+  if (!index) {
+    return NS_ERROR_NOT_INITIALIZED;
+  }
+
+  MOZ_ASSERT(CacheFileIOManager::IsOnIOThread());
+
+  CacheIndexAutoLock lock(index);
+
+  if (!index->IsIndexUsable()) {
+    return NS_ERROR_NOT_AVAILABLE;
+  }
+
+  {
+    CacheIndexEntryAutoManage entryMng(aHash, index);
+
+    CacheIndexEntry *entry = index->mIndex.GetEntry(*aHash);
+    bool reinitEntry = false;
+
+    if (entry && entry->IsRemoved()) {
+      entry = nullptr;
+    }
+
+    if (index->mState == READY || index->mState == UPDATING ||
+        index->mState == BUILDING) {
+      MOZ_ASSERT(index->mPendingUpdates.Count() == 0);
+      MOZ_ASSERT(entry);
+      MOZ_ASSERT(entry->IsFresh());
+
+      if (IsCollision(entry, aAppId, aAnonymous, aInBrowser)) {
+        index->mIndexNeedsUpdate = true; // TODO Does this really help in case of collision?
+        reinitEntry = true;
+      } else {
+        if (entry->IsInitialized()) {
+          return NS_OK;
+        }
+      }
+    } else {
+      CacheIndexEntry *updated = index->mPendingUpdates.GetEntry(*aHash);
+      DebugOnly<bool> removed = updated && updated->IsRemoved();
+
+      MOZ_ASSERT(updated || !removed);
+      MOZ_ASSERT(updated || entry);
+
+      if (updated) {
+        MOZ_ASSERT(updated->IsFresh());
+
+        if (IsCollision(updated, aAppId, aAnonymous, aInBrowser)) {
+          index->mIndexNeedsUpdate = true;
+          reinitEntry = true;
+        } else {
+          if (updated->IsInitialized()) {
+            return NS_OK;
+          }
+        }
+        entry = updated;
+      } else {
+        MOZ_ASSERT(entry->IsFresh());
+
+        if (IsCollision(entry, aAppId, aAnonymous, aInBrowser)) {
+          index->mIndexNeedsUpdate = true;
+          reinitEntry = true;
+        } else {
+          if (entry->IsInitialized()) {
+            return NS_OK;
+          }
+        }
+
+        // make a copy of a read-only entry
+        updated = index->mPendingUpdates.PutEntry(*aHash);
+        *updated = *entry;
+        entry = updated;
+      }
+    }
+
+    if (reinitEntry) {
+      // There is a collision and we are going to rewrite this entry. Initialize
+      // it as a new entry.
+      entry->InitNew();
+      entry->MarkFresh();
+    }
+    entry->Init(aAppId, aAnonymous, aInBrowser);
+    entry->MarkDirty();
+  }
+
+  index->StartUpdatingIndexIfNeeded();
+  index->WriteIndexToDiskIfNeeded();
+
+  return NS_OK;
+}
+
+// static
+nsresult
+CacheIndex::RemoveEntry(const SHA1Sum::Hash *aHash)
+{
+  LOG(("CacheIndex::RemoveEntry() [hash=%08x%08x%08x%08x%08x]",
+       LOGSHA1(aHash)));
+
+  nsRefPtr<CacheIndex> index = gInstance;
+
+  if (!index) {
+    return NS_ERROR_NOT_INITIALIZED;
+  }
+
+  MOZ_ASSERT(CacheFileIOManager::IsOnIOThread());
+
+  CacheIndexAutoLock lock(index);
+
+  if (!index->IsIndexUsable()) {
+    return NS_ERROR_NOT_AVAILABLE;
+  }
+
+  {
+    CacheIndexEntryAutoManage entryMng(aHash, index);
+
+    CacheIndexEntry *entry = index->mIndex.GetEntry(*aHash);
+    bool entryRemoved = entry && entry->IsRemoved();
+
+    if (index->mState == READY || index->mState == UPDATING ||
+        index->mState == BUILDING) {
+      MOZ_ASSERT(index->mPendingUpdates.Count() == 0);
+
+      if (!entry || entryRemoved) {
+        if (entryRemoved && entry->IsFresh()) {
+          // This could happen only if somebody copies files to the entries
+          // directory while FF is running.
+          LOG(("CacheIndex::RemoveEntry() - Cache file was added outside FF "
+               "process! Update is needed."));
+          index->mIndexNeedsUpdate = true;
+        } else if (index->mState == READY ||
+                   (entryRemoved && !entry->IsFresh())) {
+          // Removed non-fresh entries can be present as a result of
+          // ProcessJournalEntry()
+          LOG(("CacheIndex::RemoveEntry() - Didn't find entry that should exist"
+               ", update is needed"));
+          index->mIndexNeedsUpdate = true;
+        }
+      } else {
+        if (entry) {
+          if (!entry->IsDirty() && entry->IsFileEmpty()) {
+            index->mIndex.RemoveEntry(*aHash);
+            entry = nullptr;
+          } else {
+            entry->MarkRemoved();
+            entry->MarkDirty();
+            entry->MarkFresh();
+          }
+        }
+      }
+    } else { // WRITING, READING
+      CacheIndexEntry *updated = index->mPendingUpdates.GetEntry(*aHash);
+      bool updatedRemoved = updated && updated->IsRemoved();
+
+      if (updatedRemoved ||
+          (!updated && entryRemoved && entry->IsFresh())) {
+        // Fresh information about missing entry found. This could happen only
+        // if somebody copies files to the entries directory while FF is running.
+        LOG(("CacheIndex::RemoveEntry() - Cache file was added outside FF "
+             "process! Update is needed."));
+        index->mIndexNeedsUpdate = true;
+      } else if (!updated && (!entry || entryRemoved)) {
+        if (index->mState == WRITING) {
+          LOG(("CacheIndex::RemoveEntry() - Didn't find entry that should exist"
+               ", update is needed"));
+          index->mIndexNeedsUpdate = true;
+        }
+        // Ignore if state is READING since the index information is partial
+      }
+
+      if (!updated) {
+        updated = index->mPendingUpdates.PutEntry(*aHash);
+        updated->InitNew();
+      }
+
+      updated->MarkRemoved();
+      updated->MarkDirty();
+      updated->MarkFresh();
+    }
+  }
+
+  index->StartUpdatingIndexIfNeeded();
+  index->WriteIndexToDiskIfNeeded();
+
+  return NS_OK;
+}
+
+// static
+nsresult
+CacheIndex::UpdateEntry(const SHA1Sum::Hash *aHash,
+                        const uint32_t      *aFrecency,
+                        const uint32_t      *aExpirationTime,
+                        const uint32_t      *aSize)
+{
+  LOG(("CacheIndex::UpdateEntry() [hash=%08x%08x%08x%08x%08x, "
+       "frecency=%s, expirationTime=%s, size=%s]", LOGSHA1(aHash),
+       aFrecency ? nsPrintfCString("%u", *aFrecency).get() : "",
+       aExpirationTime ? nsPrintfCString("%u", *aExpirationTime).get() : "",
+       aSize ? nsPrintfCString("%u", *aSize).get() : ""));
+
+  nsRefPtr<CacheIndex> index = gInstance;
+
+  if (!index) {
+    return NS_ERROR_NOT_INITIALIZED;
+  }
+
+  MOZ_ASSERT(CacheFileIOManager::IsOnIOThread());
+
+  CacheIndexAutoLock lock(index);
+
+  if (!index->IsIndexUsable()) {
+    return NS_ERROR_NOT_AVAILABLE;
+  }
+
+  {
+    CacheIndexEntryAutoManage entryMng(aHash, index);
+
+    CacheIndexEntry *entry = index->mIndex.GetEntry(*aHash);
+
+    if (entry && entry->IsRemoved()) {
+      entry = nullptr;
+    }
+
+    if (index->mState == READY || index->mState == UPDATING ||
+        index->mState == BUILDING) {
+      MOZ_ASSERT(index->mPendingUpdates.Count() == 0);
+      MOZ_ASSERT(entry);
+
+      if (!HasEntryChanged(entry, aFrecency, aExpirationTime, aSize)) {
+        return NS_OK;
+      }
+    } else {
+      CacheIndexEntry *updated = index->mPendingUpdates.GetEntry(*aHash);
+      DebugOnly<bool> removed = updated && updated->IsRemoved();
+
+      MOZ_ASSERT(updated || !removed);
+      MOZ_ASSERT(updated || entry);
+
+      if (!updated) {
+        if (entry &&
+            HasEntryChanged(entry, aFrecency, aExpirationTime, aSize)) {
+          // make a copy of a read-only entry
+          updated = index->mPendingUpdates.PutEntry(*aHash);
+          *updated = *entry;
+          entry = updated;
+        } else {
+          return NS_ERROR_NOT_AVAILABLE;
+        }
+      } else {
+        entry = updated;
+      }
+    }
+
+    MOZ_ASSERT(entry->IsFresh());
+    MOZ_ASSERT(entry->IsInitialized());
+    entry->MarkDirty();
+
+    if (aFrecency) {
+      entry->SetFrecency(*aFrecency);
+    }
+
+    if (aExpirationTime) {
+      entry->SetExpirationTime(*aExpirationTime);
+    }
+
+    if (aSize) {
+      entry->SetFileSize(*aSize);
+    }
+  }
+
+  index->WriteIndexToDiskIfNeeded();
+
+  return NS_OK;
+}
+
+// static
+nsresult
+CacheIndex::HasEntry(const nsACString &aKey, EntryStatus *_retval)
+{
+  LOG(("CacheIndex::HasEntry() [key=%s]", PromiseFlatCString(aKey).get()));
+
+  nsRefPtr<CacheIndex> index = gInstance;
+
+  if (!index) {
+    return NS_ERROR_NOT_INITIALIZED;
+  }
+
+  CacheIndexAutoLock lock(index);
+
+  if (!index->IsIndexUsable()) {
+    return NS_ERROR_NOT_AVAILABLE;
+  }
+
+  SHA1Sum sum;
+  SHA1Sum::Hash hash;
+  sum.update(aKey.BeginReading(), aKey.Length());
+  sum.finish(hash);
+
+  CacheIndexEntry *entry = nullptr;
+
+  switch (index->mState) {
+    case READING:
+    case WRITING:
+      entry = index->mPendingUpdates.GetEntry(hash);
+      // no break
+    case BUILDING:
+    case UPDATING:
+    case READY:
+      if (!entry) {
+        entry = index->mIndex.GetEntry(hash);
+      }
+      break;
+    case INITIAL:
+    case SHUTDOWN:
+      MOZ_ASSERT(false, "Unexpected state!");
+  }
+
+  if (!entry) {
+    if (index->mState == READY || index->mState == WRITING) {
+      *_retval = DOES_NOT_EXIST;
+    } else {
+      *_retval = DO_NOT_KNOW;
+    }
+  } else {
+    if (entry->IsRemoved()) {
+      if (entry->IsFresh()) {
+        *_retval = DOES_NOT_EXIST;
+      } else {
+        *_retval = DO_NOT_KNOW;
+      }
+    } else {
+      *_retval = EXISTS;
+    }
+  }
+
+  LOG(("CacheIndex::HasEntry() - result is %u", *_retval));
+  return NS_OK;
+}
+
+bool
+CacheIndex::IsIndexUsable()
+{
+  MOZ_ASSERT(mState != INITIAL);
+
+  switch (mState) {
+    case INITIAL:
+    case SHUTDOWN:
+      return false;
+
+    case READING:
+    case WRITING:
+    case BUILDING:
+    case UPDATING:
+    case READY:
+      break;
+  }
+
+  return true;
+}
+
+// static
+bool
+CacheIndex::IsCollision(CacheIndexEntry *aEntry,
+                        uint32_t         aAppId,
+                        bool             aAnonymous,
+                        bool             aInBrowser)
+{
+  if (!aEntry->IsInitialized()) {
+    return false;
+  }
+
+  if (aEntry->AppId() != aAppId || aEntry->Anonymous() != aAnonymous ||
+      aEntry->InBrowser() != aInBrowser) {
+    LOG(("CacheIndex::IsCollision() - Collision detected for entry hash=%08x"
+         "%08x%08x%08x%08x, expected values: appId=%u, anonymous=%d, "
+         "inBrowser=%d; actual values: appId=%u, anonymous=%d, inBrowser=%d]",
+         LOGSHA1(aEntry->Hash()), aAppId, aAnonymous, aInBrowser,
+         aEntry->AppId(), aEntry->Anonymous(), aEntry->InBrowser()));
+    return true;
+  }
+
+  return false;
+}
+
+// static
+bool
+CacheIndex::HasEntryChanged(CacheIndexEntry *aEntry,
+                            const uint32_t  *aFrecency,
+                            const uint32_t  *aExpirationTime,
+                            const uint32_t  *aSize)
+{
+  if (aFrecency && *aFrecency != aEntry->GetFrecency()) {
+    return true;
+  }
+
+  if (aExpirationTime && *aExpirationTime != aEntry->GetExpirationTime()) {
+    return true;
+  }
+
+  if (aSize &&
+      (*aSize & CacheIndexEntry::kFileSizeMask) != aEntry->GetFileSize()) {
+    return true;
+  }
+
+  return false;
+}
+
+void
+CacheIndex::ProcessPendingOperations()
+{
+  LOG(("CacheIndex::ProcessPendingOperations()"));
+
+  AssertOwnsLock();
+
+  mPendingUpdates.EnumerateEntries(&CacheIndex::UpdateEntryInIndex, this);
+
+  MOZ_ASSERT(mPendingUpdates.Count() == 0);
+
+  EnsureCorrectStats();
+}
+
+// static
+PLDHashOperator
+CacheIndex::UpdateEntryInIndex(CacheIndexEntry *aEntry, void* aClosure)
+{
+  CacheIndex *index = static_cast<CacheIndex *>(aClosure);
+
+  LOG(("CacheFile::UpdateEntryInIndex() [hash=%08x%08x%08x%08x%08x]",
+       LOGSHA1(aEntry->Hash())));
+
+  MOZ_ASSERT(aEntry->IsFresh());
+  MOZ_ASSERT(aEntry->IsDirty());
+
+  CacheIndexEntry *entry = index->mIndex.GetEntry(*aEntry->Hash());
+
+  CacheIndexEntryAutoManage emng(aEntry->Hash(), index);
+  emng.DoNotSearchInUpdates();
+
+  if (aEntry->IsRemoved()) {
+    if (entry) {
+      if (entry->IsRemoved()) {
+        MOZ_ASSERT(entry->IsFresh());
+        MOZ_ASSERT(entry->IsDirty());
+      } else if (!entry->IsDirty() && entry->IsFileEmpty()) {
+        // Entries with empty file are not stored in index on disk. Just remove
+        // the entry, but only in case the entry is not dirty, i.e. the entry
+        // file was empty when we wrote the index.
+        index->mIndex.RemoveEntry(*aEntry->Hash());
+        entry = nullptr;
+      } else {
+        entry->MarkRemoved();
+        entry->MarkDirty();
+        entry->MarkFresh();
+      }
+    }
+
+    return PL_DHASH_REMOVE;
+  }
+
+  entry = index->mIndex.PutEntry(*aEntry->Hash());
+  *entry = *aEntry;
+
+  return PL_DHASH_REMOVE;
+}
+
+bool
+CacheIndex::WriteIndexToDiskIfNeeded()
+{
+  if (mState != READY || mShuttingDown) {
+    return false;
+  }
+
+  if (!mLastDumpTime.IsNull() &&
+      (TimeStamp::NowLoRes() - mLastDumpTime).ToMilliseconds() <
+      kMinDumpInterval) {
+    return false;
+  }
+
+  if (mIndexStats.Dirty() < kMinUnwrittenChanges) {
+    return false;
+  }
+
+  WriteIndexToDisk();
+  return true;
+}
+
+void
+CacheIndex::WriteIndexToDisk()
+{
+  LOG(("CacheIndex::WriteIndexToDisk()"));
+  mIndexStats.Log();
+
+  nsresult rv;
+
+  AssertOwnsLock();
+  MOZ_ASSERT(mState == READY);
+  MOZ_ASSERT(!mRWBuf);
+  MOZ_ASSERT(!mRWHash);
+
+  ChangeState(WRITING);
+
+  mProcessEntries = mIndexStats.ActiveEntriesCount();
+
+  rv = CacheFileIOManager::OpenFile(NS_LITERAL_CSTRING(kTempIndexName),
+                                    CacheFileIOManager::SPECIAL_FILE |
+                                    CacheFileIOManager::CREATE,
+                                    this);
+  if (NS_FAILED(rv)) {
+    LOG(("CacheIndex::WriteIndexToDisk() - Can't open file [rv=0x%08x]", rv));
+    FinishWrite(false);
+    return;
+  }
+
+  // Write index header to a buffer, it will be written to disk together with
+  // records in WriteRecords() once we open the file successfully.
+  AllocBuffer();
+  mRWHash = new CacheHash();
+
+  CacheIndexHeader *hdr = reinterpret_cast<CacheIndexHeader *>(mRWBuf);
+  NetworkEndian::writeUint32(&hdr->mVersion, kIndexVersion);
+  NetworkEndian::writeUint32(&hdr->mTimeStamp,
+                             static_cast<uint32_t>(PR_Now() / PR_USEC_PER_SEC));
+  NetworkEndian::writeUint32(&hdr->mIsDirty, 1);
+
+  mRWBufPos = sizeof(CacheIndexHeader);
+  mSkipEntries = 0;
+}
+
+namespace { // anon
+
+struct WriteRecordsHelper
+{
+  char    *mBuf;
+  uint32_t mSkip;
+  uint32_t mProcessMax;
+  uint32_t mProcessed;
+#ifdef DEBUG
+  bool     mHasMore;
+#endif
+};
+
+} // anon
+
+void
+CacheIndex::WriteRecords()
+{
+  LOG(("CacheIndex::WriteRecords()"));
+
+  nsresult rv;
+
+  AssertOwnsLock();
+  MOZ_ASSERT(mState == WRITING);
+
+  int64_t fileOffset;
+
+  if (mSkipEntries) {
+    MOZ_ASSERT(mRWBufPos == 0);
+    fileOffset = sizeof(CacheIndexHeader);
+    fileOffset += sizeof(CacheIndexRecord) * mSkipEntries;
+  } else {
+    MOZ_ASSERT(mRWBufPos == sizeof(CacheIndexHeader));
+    fileOffset = 0;
+  }
+  uint32_t hashOffset = mRWBufPos;
+
+  WriteRecordsHelper data;
+  data.mBuf = mRWBuf + mRWBufPos;
+  data.mSkip = mSkipEntries;
+  data.mProcessMax = (mRWBufSize - mRWBufPos) / sizeof(CacheIndexRecord);
+  MOZ_ASSERT(data.mProcessMax != 0 || mProcessEntries == 0); // TODO make sure we can write an empty index
+  data.mProcessed = 0;
+#ifdef DEBUG
+  data.mHasMore = false;
+#endif
+
+  mIndex.EnumerateEntries(&CacheIndex::CopyRecordsToRWBuf, &data);
+  MOZ_ASSERT(mRWBufPos != static_cast<uint32_t>(data.mBuf - mRWBuf) ||
+             mProcessEntries == 0);
+  mRWBufPos = data.mBuf - mRWBuf;
+  mSkipEntries += data.mProcessed;
+  MOZ_ASSERT(mSkipEntries <= mProcessEntries);
+
+  mRWHash->Update(mRWBuf + hashOffset, mRWBufPos - hashOffset);
+
+  if (mSkipEntries == mProcessEntries) {
+    MOZ_ASSERT(!data.mHasMore);
+
+    // We've processed all records
+    if (mRWBufPos + sizeof(CacheHash::Hash32_t) > mRWBufSize) {
+      // realloc buffer to spare another write cycle
+      mRWBufSize = mRWBufPos + sizeof(CacheHash::Hash32_t);
+      mRWBuf = static_cast<char *>(moz_xrealloc(mRWBuf, mRWBufSize));
+    }
+
+    NetworkEndian::writeUint32(mRWBuf + mRWBufPos, mRWHash->GetHash());
+    mRWBufPos += sizeof(CacheHash::Hash32_t);
+  } else {
+    MOZ_ASSERT(data.mHasMore);
+  }
+
+  rv = CacheFileIOManager::Write(mIndexHandle, fileOffset, mRWBuf, mRWBufPos,
+                                 mSkipEntries == mProcessEntries, this);
+  if (NS_FAILED(rv)) {
+    LOG(("CacheIndex::WriteRecords() - CacheFileIOManager::Write() failed "
+         "synchronously [rv=0x%08x]", rv));
+    FinishWrite(false);
+  }
+
+  mRWBufPos = 0;
+}
+
+void
+CacheIndex::FinishWrite(bool aSucceeded)
+{
+  LOG(("CacheIndex::FinishWrite() [succeeded=%d]", aSucceeded));
+
+  MOZ_ASSERT((!aSucceeded && mState == SHUTDOWN) || mState == WRITING);
+
+  AssertOwnsLock();
+
+  mIndexHandle = nullptr;
+  mRWHash = nullptr;
+  ReleaseBuffer();
+
+  if (aSucceeded) {
+    mIndex.EnumerateEntries(&CacheIndex::ApplyIndexChanges, this);
+    mIndexOnDiskIsValid = true;
+  }
+
+  ProcessPendingOperations();
+  mIndexStats.Log();
+
+  if (mState == WRITING) {
+    ChangeState(READY);
+    mLastDumpTime = TimeStamp::NowLoRes();
+  }
+}
+
+// static
+PLDHashOperator
+CacheIndex::CopyRecordsToRWBuf(CacheIndexEntry *aEntry, void* aClosure)
+{
+  if (aEntry->IsRemoved()) {
+    return PL_DHASH_NEXT;
+  }
+
+  if (!aEntry->IsInitialized()) {
+    return PL_DHASH_NEXT;
+  }
+
+  if (aEntry->IsFileEmpty()) {
+    return PL_DHASH_NEXT;
+  }
+
+  WriteRecordsHelper *data = static_cast<WriteRecordsHelper *>(aClosure);
+  if (data->mSkip) {
+    data->mSkip--;
+    return PL_DHASH_NEXT;
+  }
+
+  if (data->mProcessed == data->mProcessMax) {
+#ifdef DEBUG
+    data->mHasMore = true;
+#endif
+    return PL_DHASH_STOP;
+  }
+
+  aEntry->WriteToBuf(data->mBuf);
+  data->mBuf += sizeof(CacheIndexRecord);
+  data->mProcessed++;
+
+  return PL_DHASH_NEXT;
+}
+
+// static
+PLDHashOperator
+CacheIndex::ApplyIndexChanges(CacheIndexEntry *aEntry, void* aClosure)
+{
+  CacheIndex *index = static_cast<CacheIndex *>(aClosure);
+
+  CacheIndexEntryAutoManage emng(aEntry->Hash(), index);
+
+  if (aEntry->IsRemoved()) {
+    emng.DoNotSearchInIndex();
+    return PL_DHASH_REMOVE;
+  }
+
+  if (aEntry->IsDirty()) {
+    aEntry->ClearDirty();
+  }
+
+  return PL_DHASH_NEXT;
+}
+
+nsresult
+CacheIndex::GetFile(const nsACString &aName, nsIFile **_retval)
+{
+  nsresult rv;
+
+  nsCOMPtr<nsIFile> file;
+  rv = mCacheDirectory->Clone(getter_AddRefs(file));
+  NS_ENSURE_SUCCESS(rv, rv);
+
+  rv = file->AppendNative(aName);
+  NS_ENSURE_SUCCESS(rv, rv);
+
+  file.swap(*_retval);
+  return NS_OK;
+}
+
+nsresult
+CacheIndex::RemoveFile(const nsACString &aName)
+{
+  MOZ_ASSERT(mState == SHUTDOWN);
+
+  nsresult rv;
+
+  nsCOMPtr<nsIFile> file;
+  rv = GetFile(aName, getter_AddRefs(file));
+  NS_ENSURE_SUCCESS(rv, rv);
+
+  bool exists;
+  rv = file->Exists(&exists);
+  NS_ENSURE_SUCCESS(rv, rv);
+
+  if (exists) {
+    rv = file->Remove(false);
+    if (NS_FAILED(rv)) {
+      LOG(("CacheIndex::RemoveFile() - Cannot remove old entry file from disk."
+           "[name=%s]", PromiseFlatCString(aName).get()));
+      NS_WARNING("Cannot remove old entry file from the disk");
+      return rv;
+    }
+  }
+
+  return NS_OK;
+}
+
+void
+CacheIndex::RemoveIndexFromDisk()
+{
+  LOG(("CacheIndex::RemoveIndexFromDisk()"));
+
+  RemoveFile(NS_LITERAL_CSTRING(kIndexName));
+  RemoveFile(NS_LITERAL_CSTRING(kTempIndexName));
+  RemoveFile(NS_LITERAL_CSTRING(kJournalName));
+}
+
+class WriteLogHelper
+{
+public:
+  WriteLogHelper(PRFileDesc *aFD)
+    : mStatus(NS_OK)
+    , mFD(aFD)
+    , mBufSize(kMaxBufSize)
+    , mBufPos(0)
+  {
+    mHash = new CacheHash();
+    mBuf = static_cast<char *>(moz_xmalloc(mBufSize));
+  }
+
+  ~WriteLogHelper() {
+    free(mBuf);
+  }
+
+  nsresult AddEntry(CacheIndexEntry *aEntry);
+  nsresult Finish();
+
+private:
+
+  nsresult FlushBuffer();
+
+  nsresult            mStatus;
+  PRFileDesc         *mFD;
+  char               *mBuf;
+  uint32_t            mBufSize;
+  int32_t             mBufPos;
+  nsCOMPtr<CacheHash> mHash;
+};
+
+nsresult
+WriteLogHelper::AddEntry(CacheIndexEntry *aEntry)
+{
+  nsresult rv;
+
+  if (NS_FAILED(mStatus)) {
+    return mStatus;
+  }
+
+  if (mBufPos + sizeof(CacheIndexRecord) > mBufSize) {
+    mHash->Update(mBuf, mBufPos);
+
+    rv = FlushBuffer();
+    if (NS_FAILED(rv)) {
+      mStatus = rv;
+      return rv;
+    }
+    MOZ_ASSERT(mBufPos + sizeof(CacheIndexRecord) <= mBufSize);
+  }
+
+  aEntry->WriteToBuf(mBuf + mBufPos);
+  mBufPos += sizeof(CacheIndexRecord);
+
+  return NS_OK;
+}
+
+nsresult
+WriteLogHelper::Finish()
+{
+  nsresult rv;
+
+  if (NS_FAILED(mStatus)) {
+    return mStatus;
+  }
+
+  mHash->Update(mBuf, mBufPos);
+  if (mBufPos + sizeof(CacheHash::Hash32_t) > mBufSize) {
+    rv = FlushBuffer();
+    if (NS_FAILED(rv)) {
+      mStatus = rv;
+      return rv;
+    }
+    MOZ_ASSERT(mBufPos + sizeof(CacheHash::Hash32_t) <= mBufSize);
+  }
+
+  NetworkEndian::writeUint32(mBuf + mBufPos, mHash->GetHash());
+  mBufPos += sizeof(CacheHash::Hash32_t);
+
+  rv = FlushBuffer();
+  NS_ENSURE_SUCCESS(rv, rv);
+
+  mStatus = NS_ERROR_UNEXPECTED; // Don't allow any other operation
+  return NS_OK;
+}
+
+nsresult
+WriteLogHelper::FlushBuffer()
+{
+  MOZ_ASSERT(NS_SUCCEEDED(mStatus));
+
+  int32_t bytesWritten = PR_Write(mFD, mBuf, mBufPos);
+
+  if (bytesWritten != mBufPos) {
+    return NS_ERROR_FAILURE;
+  }
+
+  mBufPos = 0;
+  return NS_OK;
+}
+
+nsresult
+CacheIndex::WriteLogToDisk()
+{
+  LOG(("CacheIndex::WriteLogToDisk()"));
+
+  nsresult rv;
+
+  MOZ_ASSERT(mPendingUpdates.Count() == 0);
+  MOZ_ASSERT(mState == SHUTDOWN);
+
+  RemoveFile(NS_LITERAL_CSTRING(kTempIndexName));
+
+  nsCOMPtr<nsIFile> indexFile;
+  rv = GetFile(NS_LITERAL_CSTRING(kIndexName), getter_AddRefs(indexFile));
+  NS_ENSURE_SUCCESS(rv, rv);
+
+  nsCOMPtr<nsIFile> logFile;
+  rv = GetFile(NS_LITERAL_CSTRING(kJournalName), getter_AddRefs(logFile));
+  NS_ENSURE_SUCCESS(rv, rv);
+
+  mIndexStats.Log();
+
+  PRFileDesc *fd = nullptr;
+  rv = logFile->OpenNSPRFileDesc(PR_RDWR | PR_CREATE_FILE | PR_TRUNCATE,
+                                 0600, &fd);
+  NS_ENSURE_SUCCESS(rv, rv);
+
+  WriteLogHelper wlh(fd);
+  mIndex.EnumerateEntries(&CacheIndex::WriteEntryToLog, &wlh);
+
+  rv = wlh.Finish();
+  PR_Close(fd);
+  NS_ENSURE_SUCCESS(rv, rv);
+
+  rv = indexFile->OpenNSPRFileDesc(PR_RDWR, 0600, &fd);
+  NS_ENSURE_SUCCESS(rv, rv);
+
+  CacheIndexHeader header;
+  int32_t bytesRead = PR_Read(fd, &header, sizeof(CacheIndexHeader));
+  if (bytesRead != sizeof(CacheIndexHeader)) {
+    PR_Close(fd);
+    return NS_ERROR_FAILURE;
+  }
+
+  NetworkEndian::writeUint32(&header.mIsDirty, 0);
+
+  int64_t offset = PR_Seek64(fd, 0, PR_SEEK_SET);
+  if (offset == -1) {
+    PR_Close(fd);
+    return NS_ERROR_FAILURE;
+  }
+
+  int32_t bytesWritten = PR_Write(fd, &header, sizeof(CacheIndexHeader));
+  PR_Close(fd);
+  if (bytesWritten != sizeof(CacheIndexHeader)) {
+    return NS_ERROR_FAILURE;
+  }
+
+  return NS_OK;
+}
+
+// static
+PLDHashOperator
+CacheIndex::WriteEntryToLog(CacheIndexEntry *aEntry, void* aClosure)
+{
+  WriteLogHelper *wlh = static_cast<WriteLogHelper *>(aClosure);
+
+  if (aEntry->IsRemoved() || aEntry->IsDirty()) {
+    wlh->AddEntry(aEntry);
+  }
+
+  return PL_DHASH_REMOVE;
+}
+
+void
+CacheIndex::ReadIndexFromDisk()
+{
+  LOG(("CacheIndex::ReadIndexFromDisk()"));
+
+  nsresult rv;
+
+  CacheIndexAutoLock lock(this);
+
+  MOZ_ASSERT(mState == READING);
+
+  mReadFailed = false;
+  mReadOpenCount = 0;
+
+  rv = CacheFileIOManager::OpenFile(NS_LITERAL_CSTRING(kIndexName),
+                                    CacheFileIOManager::SPECIAL_FILE |
+                                    CacheFileIOManager::OPEN,
+                                    this);
+  if (NS_FAILED(rv)) {
+    LOG(("CacheIndex::ReadIndexFromDisk() - CacheFileIOManager::OpenFile() "
+         "failed [rv=0x%08x, file=%s]", rv, kIndexName));
+    mReadFailed = true;
+  } else {
+    mReadOpenCount++;
+  }
+
+  rv = CacheFileIOManager::OpenFile(NS_LITERAL_CSTRING(kJournalName),
+                                    CacheFileIOManager::SPECIAL_FILE |
+                                    CacheFileIOManager::OPEN,
+                                    this);
+  if (NS_FAILED(rv)) {
+    LOG(("CacheIndex::ReadIndexFromDisk() - CacheFileIOManager::OpenFile() "
+         "failed [rv=0x%08x, file=%s]", rv, kJournalName));
+    mReadFailed = true;
+  } else {
+    mReadOpenCount++;
+  }
+
+  rv = CacheFileIOManager::OpenFile(NS_LITERAL_CSTRING(kTempIndexName),
+                                    CacheFileIOManager::SPECIAL_FILE |
+                                    CacheFileIOManager::OPEN,
+                                    this);
+  if (NS_FAILED(rv)) {
+    LOG(("CacheIndex::ReadIndexFromDisk() - CacheFileIOManager::OpenFile() "
+         "failed [rv=0x%08x, file=%s]", rv, kTempIndexName));
+    mReadFailed = true;
+  } else {
+    mReadOpenCount++;
+  }
+
+  if (mReadOpenCount == 0) {
+    FinishRead(false);
+  }
+}
+
+void
+CacheIndex::StartReadingIndex()
+{
+  LOG(("CacheIndex::StartReadingIndex()"));
+
+  nsresult rv;
+
+  AssertOwnsLock();
+
+  MOZ_ASSERT(mIndexHandle);
+  MOZ_ASSERT(mState == READING);
+  MOZ_ASSERT(!mIndexOnDiskIsValid);
+  MOZ_ASSERT(!mDontMarkIndexClean);
+  MOZ_ASSERT(!mJournalReadSuccessfully);
+  MOZ_ASSERT(mIndexHandle->FileSize() >= 0);
+
+  int64_t entriesSize = mIndexHandle->FileSize() - sizeof(CacheIndexHeader) -
+                        sizeof(CacheHash::Hash32_t);
+
+  if (entriesSize < 0 || entriesSize % sizeof(CacheIndexRecord)) {
+    LOG(("CacheIndex::StartReadingIndex() - Index is corrupted"));
+    FinishRead(false);
+    return;
+  }
+
+  AllocBuffer();
+  mSkipEntries = 0;
+  mRWHash = new CacheHash();
+
+  mRWBufPos = std::min(mRWBufSize,
+                       static_cast<uint32_t>(mIndexHandle->FileSize()));
+
+  rv = CacheFileIOManager::Read(mIndexHandle, 0, mRWBuf, mRWBufPos, this);
+  if (NS_FAILED(rv)) {
+    LOG(("CacheIndex::StartReadingIndex() - CacheFileIOManager::Read() failed "
+         "synchronously [rv=0x%08x]", rv));
+    FinishRead(false);
+  }
+}
+
+void
+CacheIndex::ParseRecords()
+{
+  LOG(("CacheIndex::ParseRecords()"));
+
+  nsresult rv;
+
+  AssertOwnsLock();
+
+  uint32_t entryCnt = (mIndexHandle->FileSize() - sizeof(CacheIndexHeader) -
+                     sizeof(CacheHash::Hash32_t)) / sizeof(CacheIndexRecord);
+  uint32_t pos = 0;
+
+  if (!mSkipEntries) {
+    CacheIndexHeader *hdr = reinterpret_cast<CacheIndexHeader *>(
+                              moz_xmalloc(sizeof(CacheIndexHeader)));
+    memcpy(hdr, mRWBuf, sizeof(CacheIndexHeader));
+
+    if (NetworkEndian::readUint32(&hdr->mVersion) != kIndexVersion) {
+      free(hdr);
+      FinishRead(false);
+      return;
+    }
+
+    mIndexTimeStamp = NetworkEndian::readUint32(&hdr->mTimeStamp);
+
+    if (NetworkEndian::readUint32(&hdr->mIsDirty)) {
+      if (mJournalHandle) {
+        CacheFileIOManager::DoomFile(mJournalHandle, nullptr);
+        mJournalHandle = nullptr;
+      }
+      free(hdr);
+    } else {
+      NetworkEndian::writeUint32(&hdr->mIsDirty, 1);
+
+      // Mark index dirty. The buffer is freed by CacheFileIOManager when
+      // nullptr is passed as the listener and the call doesn't fail
+      // synchronously.
+      rv = CacheFileIOManager::Write(mIndexHandle, 0,
+                                     reinterpret_cast<char *>(hdr),
+                                     sizeof(CacheIndexHeader), true, nullptr);
+      if (NS_FAILED(rv)) {
+        // This is not fatal, just free the memory
+        free(hdr);
+      }
+    }
+
+    pos += sizeof(CacheIndexHeader);
+  }
+
+  uint32_t hashOffset = pos;
+
+  while (pos + sizeof(CacheIndexRecord) <= mRWBufPos &&
+         mSkipEntries != entryCnt) {
+    CacheIndexRecord *rec = reinterpret_cast<CacheIndexRecord *>(mRWBuf + pos);
+    CacheIndexEntry tmpEntry(&rec->mHash);
+    tmpEntry.ReadFromBuf(mRWBuf + pos);
+
+    if (tmpEntry.IsDirty() || !tmpEntry.IsInitialized() ||
+        tmpEntry.IsFileEmpty() || tmpEntry.IsFresh() || tmpEntry.IsRemoved()) {
+      LOG(("CacheIndex::ParseRecords() - Invalid entry found in index, removing"
+           " whole index [dirty=%d, initialized=%d, fileEmpty=%d, fresh=%d, "
+           "removed=%d]", tmpEntry.IsDirty(), tmpEntry.IsInitialized(),
+           tmpEntry.IsFileEmpty(), tmpEntry.IsFresh(), tmpEntry.IsRemoved()));
+      FinishRead(false);
+      return;
+    }
+
+    CacheIndexEntryAutoManage emng(tmpEntry.Hash(), this);
+
+    CacheIndexEntry *entry = mIndex.PutEntry(*tmpEntry.Hash());
+    *entry = tmpEntry;
+
+    pos += sizeof(CacheIndexRecord);
+    mSkipEntries++;
+  }
+
+  mRWHash->Update(mRWBuf + hashOffset, pos - hashOffset);
+
+  if (pos != mRWBufPos) {
+    memmove(mRWBuf, mRWBuf + pos, mRWBufPos - pos);
+    mRWBufPos -= pos;
+    pos = 0;
+  }
+
+  int64_t fileOffset = sizeof(CacheIndexHeader) +
+                       mSkipEntries * sizeof(CacheIndexRecord) + mRWBufPos;
+
+  MOZ_ASSERT(fileOffset <= mIndexHandle->FileSize());
+  if (fileOffset == mIndexHandle->FileSize()) {
+    if (mRWHash->GetHash() != NetworkEndian::readUint32(mRWBuf)) {
+      LOG(("CacheIndex::ParseRecords() - Hash mismatch, [is %x, should be %x]",
+           mRWHash->GetHash(),
+           NetworkEndian::readUint32(mRWBuf)));
+      FinishRead(false);
+      return;
+    }
+
+    mIndexOnDiskIsValid = true;
+    mJournalReadSuccessfully = false;
+
+    if (mJournalHandle) {
+      StartReadingJournal();
+    } else {
+      FinishRead(false);
+    }
+
+    return;
+  }
+
+  pos = mRWBufPos;
+  uint32_t toRead = std::min(mRWBufSize - pos,
+                             static_cast<uint32_t>(mIndexHandle->FileSize() -
+                                                   fileOffset));
+  mRWBufPos = pos + toRead;
+
+  rv = CacheFileIOManager::Read(mIndexHandle, fileOffset, mRWBuf + pos, toRead,
+                                this);
+  if (NS_FAILED(rv)) {
+    LOG(("CacheIndex::ParseRecords() - CacheFileIOManager::Read() failed "
+         "synchronously [rv=0x%08x]", rv));
+    FinishRead(false);
+    return;
+  }
+}
+
+void
+CacheIndex::StartReadingJournal()
+{
+  LOG(("CacheIndex::StartReadingJournal()"));
+
+  nsresult rv;
+
+  AssertOwnsLock();
+
+  MOZ_ASSERT(mJournalHandle);
+  MOZ_ASSERT(mIndexOnDiskIsValid);
+  MOZ_ASSERT(mTmpJournal.Count() == 0);
+  MOZ_ASSERT(mJournalHandle->FileSize() >= 0);
+
+  int64_t entriesSize = mJournalHandle->FileSize() -
+                        sizeof(CacheHash::Hash32_t);
+
+  if (entriesSize < 0 || entriesSize % sizeof(CacheIndexRecord)) {
+    LOG(("CacheIndex::StartReadingJournal() - Journal is corrupted"));
+    FinishRead(false);
+    return;
+  }
+
+  mSkipEntries = 0;
+  mRWHash = new CacheHash();
+
+  mRWBufPos = std::min(mRWBufSize,
+                       static_cast<uint32_t>(mJournalHandle->FileSize()));
+
+  rv = CacheFileIOManager::Read(mJournalHandle, 0, mRWBuf, mRWBufPos, this);
+  if (NS_FAILED(rv)) {
+    LOG(("CacheIndex::StartReadingJournal() - CacheFileIOManager::Read() failed"
+         " synchronously [rv=0x%08x]", rv));
+    FinishRead(false);
+  }
+}
+
+void
+CacheIndex::ParseJournal()
+{
+  LOG(("CacheIndex::ParseRecords()"));
+
+  nsresult rv;
+
+  AssertOwnsLock();
+
+  uint32_t entryCnt = (mJournalHandle->FileSize() -
+                       sizeof(CacheHash::Hash32_t)) / sizeof(CacheIndexRecord);
+
+  uint32_t pos = 0;
+
+  while (pos + sizeof(CacheIndexRecord) <= mRWBufPos &&
+         mSkipEntries != entryCnt) {
+    CacheIndexRecord *rec = reinterpret_cast<CacheIndexRecord *>(mRWBuf + pos);
+    CacheIndexEntry tmpEntry(&rec->mHash);
+    tmpEntry.ReadFromBuf(mRWBuf + pos);
+
+    CacheIndexEntry *entry = mTmpJournal.PutEntry(*tmpEntry.Hash());
+    *entry = tmpEntry;
+
+    if (entry->IsDirty() || entry->IsFresh()) {
+      LOG(("CacheIndex::ParseJournal() - Invalid entry found in journal, "
+           "ignoring whole journal [dirty=%d, fresh=%d]", entry->IsDirty(),
+           entry->IsFresh()));
+      FinishRead(false);
+      return;
+    }
+
+    pos += sizeof(CacheIndexRecord);
+    mSkipEntries++;
+  }
+
+  mRWHash->Update(mRWBuf, pos);
+
+  if (pos != mRWBufPos) {
+    memmove(mRWBuf, mRWBuf + pos, mRWBufPos - pos);
+    mRWBufPos -= pos;
+    pos = 0;
+  }
+
+  int64_t fileOffset = mSkipEntries * sizeof(CacheIndexRecord) + mRWBufPos;
+
+  MOZ_ASSERT(fileOffset <= mJournalHandle->FileSize());
+  if (fileOffset == mJournalHandle->FileSize()) {
+    if (mRWHash->GetHash() != NetworkEndian::readUint32(mRWBuf)) {
+      LOG(("CacheIndex::ParseJournal() - Hash mismatch, [is %x, should be %x]",
+           mRWHash->GetHash(),
+           NetworkEndian::readUint32(mRWBuf)));
+      FinishRead(false);
+      return;
+    }
+
+    mJournalReadSuccessfully = true;
+    FinishRead(true);
+    return;
+  }
+
+  pos = mRWBufPos;
+  uint32_t toRead = std::min(mRWBufSize - pos,
+                             static_cast<uint32_t>(mJournalHandle->FileSize() -
+                                                   fileOffset));
+  mRWBufPos = pos + toRead;
+
+  rv = CacheFileIOManager::Read(mJournalHandle, fileOffset, mRWBuf + pos,
+                                toRead, this);
+  if (NS_FAILED(rv)) {
+    LOG(("CacheIndex::ParseJournal() - CacheFileIOManager::Read() failed "
+         "synchronously [rv=0x%08x]", rv));
+    FinishRead(false);
+    return;
+  }
+}
+
+void
+CacheIndex::MergeJournal()
+{
+  LOG(("CacheIndex::MergeJournal()"));
+
+  AssertOwnsLock();
+
+  mTmpJournal.EnumerateEntries(&CacheIndex::ProcessJournalEntry, this);
+
+  MOZ_ASSERT(mTmpJournal.Count() == 0);
+}
+
+// static
+PLDHashOperator
+CacheIndex::ProcessJournalEntry(CacheIndexEntry *aEntry, void* aClosure)
+{
+  CacheIndex *index = static_cast<CacheIndex *>(aClosure);
+
+  LOG(("CacheFile::ProcessJournalEntry() [hash=%08x%08x%08x%08x%08x]",
+       LOGSHA1(aEntry->Hash())));
+
+  CacheIndexEntry *entry = index->mIndex.GetEntry(*aEntry->Hash());
+
+  CacheIndexEntryAutoManage emng(aEntry->Hash(), index);
+
+  if (aEntry->IsRemoved()) {
+    if (entry) {
+      entry->MarkRemoved();
+      entry->MarkDirty();
+    }
+  } else {
+    if (!entry) {
+      entry = index->mIndex.PutEntry(*aEntry->Hash());
+    }
+
+    *entry = *aEntry;
+    entry->MarkDirty();
+  }
+
+  return PL_DHASH_REMOVE;
+}
+
+void
+CacheIndex::EnsureNoFreshEntry()
+{
+#ifdef DEBUG_STATS
+  CacheIndexStats debugStats;
+  debugStats.DisableLogging();
+  mIndex.EnumerateEntries(&CacheIndex::SumIndexStats, &debugStats);
+  MOZ_ASSERT(debugStats.Fresh() == 0);
+#endif
+}
+
+void
+CacheIndex::EnsureCorrectStats()
+{
+#ifdef DEBUG_STATS
+  MOZ_ASSERT(mPendingUpdates.Count() == 0);
+  CacheIndexStats debugStats;
+  debugStats.DisableLogging();
+  mIndex.EnumerateEntries(&CacheIndex::SumIndexStats, &debugStats);
+  MOZ_ASSERT(debugStats == mIndexStats);
+#endif
+}
+
+// static
+PLDHashOperator
+CacheIndex::SumIndexStats(CacheIndexEntry *aEntry, void* aClosure)
+{
+  CacheIndexStats *stats = static_cast<CacheIndexStats *>(aClosure);
+  stats->BeforeChange(nullptr);
+  stats->AfterChange(aEntry);
+  return PL_DHASH_NEXT;
+}
+
+void
+CacheIndex::FinishRead(bool aSucceeded)
+{
+  LOG(("CacheIndex::FinishRead() [succeeded=%d]", aSucceeded));
+  AssertOwnsLock();
+
+  MOZ_ASSERT((!aSucceeded && mState == SHUTDOWN) || mState == READING);
+
+  MOZ_ASSERT(
+    // -> rebuild
+    (!aSucceeded && !mIndexOnDiskIsValid && !mJournalReadSuccessfully) ||
+    // -> update
+    (!aSucceeded && mIndexOnDiskIsValid && !mJournalReadSuccessfully) ||
+    // -> ready
+    (aSucceeded && mIndexOnDiskIsValid && mJournalReadSuccessfully));
+
+  if (mState == SHUTDOWN) {
+    RemoveFile(NS_LITERAL_CSTRING(kTempIndexName));
+    RemoveFile(NS_LITERAL_CSTRING(kJournalName));
+  } else {
+    if (mIndexHandle && !mIndexOnDiskIsValid) {
+      CacheFileIOManager::DoomFile(mIndexHandle, nullptr);
+    }
+
+    if (mJournalHandle) {
+      CacheFileIOManager::DoomFile(mJournalHandle, nullptr);
+    }
+  }
+
+  mIndexHandle = nullptr;
+  mJournalHandle = nullptr;
+  mRWHash = nullptr;
+  ReleaseBuffer();
+
+  if (mState == SHUTDOWN) {
+    return;
+  }
+
+  if (!mIndexOnDiskIsValid) {
+    MOZ_ASSERT(mTmpJournal.Count() == 0);
+    EnsureNoFreshEntry();
+    ProcessPendingOperations();
+    // Remove all entries that we haven't seen during this session
+    mIndex.EnumerateEntries(&CacheIndex::RemoveNonFreshEntries, this);
+    StartBuildingIndex();
+    return;
+  }
+
+  if (!mJournalReadSuccessfully) {
+    mTmpJournal.Clear();
+    EnsureNoFreshEntry();
+    ProcessPendingOperations();
+    StartUpdatingIndex();
+    return;
+  }
+
+  MergeJournal();
+  EnsureNoFreshEntry();
+  ProcessPendingOperations();
+  mIndexStats.Log();
+
+  ChangeState(READY);
+  mLastDumpTime = TimeStamp::NowLoRes(); // Do not dump new index immediately
+}
+
+// static
+void
+CacheIndex::DelayedBuildUpdate(nsITimer *aTimer, void *aClosure)
+{
+  LOG(("CacheIndex::DelayedBuildUpdate()"));
+
+  nsresult rv;
+  nsRefPtr<CacheIndex> index = gInstance;
+
+  if (!index) {
+    return;
+  }
+
+  CacheIndexAutoLock lock(index);
+
+  index->mTimer = nullptr;
+
+  if (!index->IsIndexUsable()) {
+    return;
+  }
+
+  if (index->mState == READY && index->mShuttingDown) {
+    return;
+  }
+
+  MOZ_ASSERT(index->mState == BUILDING || index->mState == UPDATING);
+
+  // We need to redispatch to run with lower priority
+  nsRefPtr<CacheIOThread> ioThread = CacheFileIOManager::IOThread();
+  MOZ_ASSERT(ioThread);
+
+  rv = ioThread->Dispatch(index, CacheIOThread::BUILD_OR_UPDATE_INDEX);
+  if (NS_FAILED(rv)) {
+    NS_WARNING("CacheIndex::DelayedBuildUpdate() - Can't dispatch event");
+    LOG(("CacheIndex::DelayedBuildUpdate() - Can't dispatch event" ));
+    if (index->mState == BUILDING) {
+      index->FinishBuild(false);
+    } else {
+      index->FinishUpdate(false);
+    }
+  }
+}
+
+nsresult
+CacheIndex::ScheduleBuildUpdateTimer(uint32_t aDelay)
+{
+  LOG(("CacheIndex::ScheduleBuildUpdateTimer() [delay=%u]", aDelay));
+
+  MOZ_ASSERT(!mTimer);
+
+  nsresult rv;
+
+  nsCOMPtr<nsITimer> timer = do_CreateInstance("@mozilla.org/timer;1", &rv);
+  NS_ENSURE_SUCCESS(rv, rv);
+
+  nsCOMPtr<nsIEventTarget> ioTarget = CacheFileIOManager::IOTarget();
+  MOZ_ASSERT(ioTarget);
+
+  rv = timer->SetTarget(ioTarget);
+  NS_ENSURE_SUCCESS(rv, rv);
+
+  rv = timer->InitWithFuncCallback(CacheIndex::DelayedBuildUpdate, nullptr,
+                                   aDelay, nsITimer::TYPE_ONE_SHOT);
+  NS_ENSURE_SUCCESS(rv, rv);
+
+  mTimer.swap(timer);
+  return NS_OK;
+}
+
+nsresult
+CacheIndex::SetupDirectoryEnumerator()
+{
+  MOZ_ASSERT(!NS_IsMainThread());
+  MOZ_ASSERT(!mDirEnumerator);
+
+  nsresult rv;
+  nsCOMPtr<nsIFile> file;
+
+  rv = mCacheDirectory->Clone(getter_AddRefs(file));
+  NS_ENSURE_SUCCESS(rv, rv);
+
+  rv = file->AppendNative(NS_LITERAL_CSTRING(kEntriesDir));
+  NS_ENSURE_SUCCESS(rv, rv);
+
+  bool exists;
+  rv = file->Exists(&exists);
+  NS_ENSURE_SUCCESS(rv, rv);
+
+  if (!exists) {
+    NS_WARNING("CacheIndex::SetupDirectoryEnumerator() - Entries directory "
+               "doesn't exist!");
+    LOG(("CacheIndex::SetupDirectoryEnumerator() - Entries directory doesn't "
+          "exist!" ));
+    return NS_ERROR_UNEXPECTED;
+  }
+
+  nsCOMPtr<nsISimpleEnumerator> enumerator;
+  rv = file->GetDirectoryEntries(getter_AddRefs(enumerator));
+  NS_ENSURE_SUCCESS(rv, rv);
+
+  mDirEnumerator = do_QueryInterface(enumerator, &rv);
+  NS_ENSURE_SUCCESS(rv, rv);
+
+  return NS_OK;
+}
+
+void
+CacheIndex::InitEntryFromDiskData(CacheIndexEntry *aEntry,
+                                  CacheFileMetadata *aMetaData,
+                                  int64_t aFileSize)
+{
+  aEntry->InitNew();
+  aEntry->MarkDirty();
+  aEntry->MarkFresh();
+  aEntry->Init(aMetaData->AppId(), aMetaData->IsAnonymous(),
+               aMetaData->IsInBrowser());
+
+  uint32_t expirationTime;
+  aMetaData->GetExpirationTime(&expirationTime);
+  aEntry->SetExpirationTime(expirationTime);
+
+  uint32_t frecency;
+  aMetaData->GetFrecency(&frecency);
+  aEntry->SetFrecency(frecency);
+
+  aEntry->SetFileSize(static_cast<uint32_t>(
+                        std::min(static_cast<int64_t>(PR_UINT32_MAX),
+                                 (aFileSize + 0x3FF) >> 10)));
+}
+
+void
+CacheIndex::StartBuildingIndex()
+{
+  LOG(("CacheIndex::StartBuildingIndex()"));
+
+  nsresult rv;
+
+  ChangeState(BUILDING);
+  mDontMarkIndexClean = false;
+
+  if (mShuttingDown) {
+    FinishBuild(false);
+    return;
+  }
+
+  uint32_t elapsed = (TimeStamp::NowLoRes() - mStartTime).ToMilliseconds();
+  if (elapsed < kBuildIndexStartDelay) {
+    rv = ScheduleBuildUpdateTimer(kBuildIndexStartDelay - elapsed);
+    if (NS_SUCCEEDED(rv)) {
+      return;
+    }
+
+    LOG(("CacheIndex::StartBuildingIndex() - ScheduleBuildUpdateTimer() failed."
+         " Starting build immediately."));
+  }
+
+  nsRefPtr<CacheIOThread> ioThread = CacheFileIOManager::IOThread();
+  MOZ_ASSERT(ioThread);
+
+  // We need to dispatch an event even if we are on IO thread since we need to
+  // build the inde with the correct priority.
+  rv = ioThread->Dispatch(this, CacheIOThread::BUILD_OR_UPDATE_INDEX);
+  if (NS_FAILED(rv)) {
+    NS_WARNING("CacheIndex::StartBuildingIndex() - Can't dispatch event");
+    LOG(("CacheIndex::StartBuildingIndex() - Can't dispatch event" ));
+    FinishBuild(false);
+  }
+}
+
+void
+CacheIndex::BuildIndex()
+{
+  LOG(("CacheIndex::BuildIndex()"));
+
+  AssertOwnsLock();
+
+  MOZ_ASSERT(mPendingUpdates.Count() == 0);
+
+  nsresult rv;
+
+  if (!mDirEnumerator) {
+    {
+      // Do not do IO under the lock.
+      CacheIndexAutoUnlock unlock(this);
+      rv = SetupDirectoryEnumerator();
+    }
+    if (mState == SHUTDOWN) {
+      // The index was shut down while we released the lock. FinishBuild() was
+      // already called from Shutdown(), so just simply return here.
+      return;
+    }
+
+    if (NS_FAILED(rv)) {
+      FinishBuild(false);
+      return;
+    }
+  }
+
+  TimeStamp start;
+
+  while (true) {
+    if (start.IsNull()) {
+      start = TimeStamp::NowLoRes();
+    } else {
+      static TimeDuration const kLimit = TimeDuration::FromMilliseconds(
+                                           kBuildIndexLoopLimit);
+      TimeDuration elapsed = TimeStamp::NowLoRes() - start;
+      if (elapsed >= kLimit) {
+        LOG(("CacheIndex::BuildIndex() - Breaking loop after %u ms.",
+             static_cast<uint32_t>(elapsed.ToMilliseconds())));
+        break;
+      }
+    }
+
+    nsCOMPtr<nsIFile> file;
+    {
+      // Do not do IO under the lock.
+      CacheIndexAutoUnlock unlock(this);
+      rv = mDirEnumerator->GetNextFile(getter_AddRefs(file));
+    }
+    if (mState == SHUTDOWN) {
+      return;
+    }
+    if (!file) {
+      FinishBuild(NS_SUCCEEDED(rv));
+      return;
+    }
+
+    nsAutoCString leaf;
+    rv = file->GetNativeLeafName(leaf);
+    if (NS_FAILED(rv)) {
+      LOG(("CacheIndex::BuildIndex() - GetNativeLeafName() failed! Skipping "
+           "file."));
+      mDontMarkIndexClean = true;
+      continue;
+    }
+
+    SHA1Sum::Hash hash;
+    rv = CacheFileIOManager::StrToHash(leaf, &hash);
+    if (NS_FAILED(rv)) {
+      LOG(("CacheIndex::BuildIndex() - Filename is not a hash, removing file. "
+           "[name=%s]", leaf.get()));
+      file->Remove(false);
+      continue;
+    }
+
+    CacheIndexEntry *entry = mIndex.GetEntry(hash);
+    if (entry && entry->IsRemoved()) {
+      LOG(("CacheIndex::BuildIndex() - Found file that should not exist. "
+           "[name=%s]", leaf.get()));
+      entry->Log();
+      MOZ_ASSERT(entry->IsFresh());
+      entry = nullptr;
+    }
+
+#ifdef DEBUG
+    nsRefPtr<CacheFileHandle> handle;
+    CacheFileIOManager::gInstance->mHandles.GetHandle(&hash, false,
+                                                      getter_AddRefs(handle));
+#endif
+
+    if (entry) {
+      // the entry is up to date
+      LOG(("CacheIndex::BuildIndex() - Skipping file because the entry is up to"
+           " date. [name=%s]", leaf.get()));
+      entry->Log();
+      MOZ_ASSERT(entry->IsFresh()); // The entry must be from this session
+      // there must be an active CacheFile if the entry is not initialized
+      MOZ_ASSERT(entry->IsInitialized() || handle);
+      continue;
+    }
+
+    MOZ_ASSERT(!handle);
+
+    nsRefPtr<CacheFileMetadata> meta = new CacheFileMetadata();
+    int64_t size = 0;
+
+    {
+      // Do not do IO under the lock.
+      CacheIndexAutoUnlock unlock(this);
+      rv = meta->SyncReadMetadata(file);
+
+      if (NS_SUCCEEDED(rv)) {
+        rv = file->GetFileSize(&size);
+        if (NS_FAILED(rv)) {
+          LOG(("CacheIndex::BuildIndex() - Cannot get filesize of file that was"
+               " successfully parsed. [name=%s]", leaf.get()));
+        }
+      }
+    }
+    if (mState == SHUTDOWN) {
+      return;
+    }
+
+    // Nobody could add the entry while the lock was released since we modify
+    // the index only on IO thread and this loop is executed on IO thread too.
+    entry = mIndex.GetEntry(hash);
+    MOZ_ASSERT(!entry || entry->IsRemoved());
+
+    if (NS_FAILED(rv)) {
+      LOG(("CacheIndex::BuildIndex() - CacheFileMetadata::SyncReadMetadata() "
+           "failed, removing file. [name=%s]", leaf.get()));
+      file->Remove(false);
+    } else {
+      CacheIndexEntryAutoManage entryMng(&hash, this);
+      entry = mIndex.PutEntry(hash);
+      InitEntryFromDiskData(entry, meta, size);
+      LOG(("CacheIndex::BuildIndex() - Added entry to index. [hash=%s]",
+           leaf.get()));
+      entry->Log();
+    }
+  }
+
+  nsRefPtr<CacheIOThread> ioThread = CacheFileIOManager::IOThread();
+  MOZ_ASSERT(ioThread);
+
+  rv = ioThread->Dispatch(this, CacheIOThread::BUILD_OR_UPDATE_INDEX);
+  if (NS_FAILED(rv)) {
+    NS_WARNING("CacheIndex::BuildIndex() - Can't dispatch event");
+    LOG(("CacheIndex::BuildIndex() - Can't dispatch event" ));
+    FinishBuild(false);
+    return;
+  }
+}
+
+void
+CacheIndex::FinishBuild(bool aSucceeded)
+{
+  LOG(("CacheIndex::FinishBuild() [succeeded=%d]", aSucceeded));
+
+  MOZ_ASSERT((!aSucceeded && mState == SHUTDOWN) || mState == BUILDING);
+
+  AssertOwnsLock();
+
+  if (mDirEnumerator) {
+    if (NS_IsMainThread()) {
+      LOG(("CacheIndex::FinishBuild() - posting of PreShutdownInternal failed? "
+           "Cannot safely release mDirEnumerator, leaking it!"));
+      NS_WARNING(("CacheIndex::FinishBuild() - Leaking mDirEnumerator!"));
+      // This can happen only in case dispatching event to IO thread failed in
+      // CacheIndex::PreShutdown().
+      mDirEnumerator.forget(); // Leak it since dir enumerator is not threadsafe
+    } else {
+      mDirEnumerator->Close();
+      mDirEnumerator = nullptr;
+    }
+  }
+
+  if (!aSucceeded) {
+    mDontMarkIndexClean = true;
+  }
+
+  if (mState == BUILDING) {
+    // Make sure we won't start update. Index should be up to date, if build
+    // was successful. If the build failed, there is no reason to believe that
+    // the update will succeed.
+    mIndexNeedsUpdate = false;
+
+    ChangeState(READY);
+    mLastDumpTime = TimeStamp::NowLoRes(); // Do not dump new index immediately
+  }
+}
+
+bool
+CacheIndex::StartUpdatingIndexIfNeeded(bool aSwitchingToReadyState)
+{
+  // Start updating process when we are in or we are switching to READY state
+  // and index needs update, but not during shutdown.
+  if ((mState == READY || aSwitchingToReadyState) && mIndexNeedsUpdate &&
+      !mShuttingDown) {
+    LOG(("CacheIndex::StartUpdatingIndexIfNeeded() - starting update process"));
+    mIndexNeedsUpdate = false;
+    StartUpdatingIndex();
+    return true;
+  }
+
+  return false;
+}
+
+void
+CacheIndex::StartUpdatingIndex()
+{
+  LOG(("CacheIndex::StartUpdatingIndex()"));
+
+  nsresult rv;
+
+  mIndexStats.Log();
+
+  ChangeState(UPDATING);
+  mDontMarkIndexClean = false;
+
+  if (mShuttingDown) {
+    FinishUpdate(false);
+    return;
+  }
+
+  uint32_t elapsed = (TimeStamp::NowLoRes() - mStartTime).ToMilliseconds();
+  if (elapsed < kUpdateIndexStartDelay) {
+    rv = ScheduleBuildUpdateTimer(kUpdateIndexStartDelay - elapsed);
+    if (NS_SUCCEEDED(rv)) {
+      return;
+    }
+
+    LOG(("CacheIndex::StartUpdatingIndex() - ScheduleBuildUpdateTimer() failed."
+         " Starting update immediately."));
+  }
+
+  nsRefPtr<CacheIOThread> ioThread = CacheFileIOManager::IOThread();
+  MOZ_ASSERT(ioThread);
+
+  // We need to dispatch an event even if we are on IO thread since we need to
+  // update the index with the correct priority.
+  rv = ioThread->Dispatch(this, CacheIOThread::BUILD_OR_UPDATE_INDEX);
+  if (NS_FAILED(rv)) {
+    NS_WARNING("CacheIndex::StartUpdatingIndex() - Can't dispatch event");
+    LOG(("CacheIndex::StartUpdatingIndex() - Can't dispatch event" ));
+    FinishUpdate(false);
+  }
+}
+
+void
+CacheIndex::UpdateIndex()
+{
+  LOG(("CacheIndex::UpdateIndex()"));
+
+  AssertOwnsLock();
+
+  MOZ_ASSERT(mPendingUpdates.Count() == 0);
+
+  nsresult rv;
+
+  if (!mDirEnumerator) {
+    {
+      // Do not do IO under the lock.
+      CacheIndexAutoUnlock unlock(this);
+      rv = SetupDirectoryEnumerator();
+    }
+    if (mState == SHUTDOWN) {
+      // The index was shut down while we released the lock. FinishBuild() was
+      // already called from Shutdown(), so just simply return here.
+      return;
+    }
+
+    if (NS_FAILED(rv)) {
+      FinishUpdate(false);
+      return;
+    }
+  }
+
+  TimeStamp start;
+
+  while (true) {
+    if (start.IsNull()) {
+      start = TimeStamp::NowLoRes();
+    } else {
+      static TimeDuration const kLimit = TimeDuration::FromMilliseconds(
+                                           kUpdateIndexLoopLimit);
+      TimeDuration elapsed = TimeStamp::NowLoRes() - start;
+      if (elapsed >= kLimit) {
+        LOG(("CacheIndex::UpdateIndex() - Breaking loop after %u ms.",
+             static_cast<uint32_t>(elapsed.ToMilliseconds())));
+        break;
+      }
+    }
+
+    nsCOMPtr<nsIFile> file;
+    {
+      // Do not do IO under the lock.
+      CacheIndexAutoUnlock unlock(this);
+      rv = mDirEnumerator->GetNextFile(getter_AddRefs(file));
+    }
+    if (mState == SHUTDOWN) {
+      return;
+    }
+    if (!file) {
+      FinishUpdate(NS_SUCCEEDED(rv));
+      return;
+    }
+
+    nsAutoCString leaf;
+    rv = file->GetNativeLeafName(leaf);
+    if (NS_FAILED(rv)) {
+      LOG(("CacheIndex::UpdateIndex() - GetNativeLeafName() failed! Skipping "
+           "file."));
+      mDontMarkIndexClean = true;
+      continue;
+    }
+
+    SHA1Sum::Hash hash;
+    rv = CacheFileIOManager::StrToHash(leaf, &hash);
+    if (NS_FAILED(rv)) {
+      LOG(("CacheIndex::UpdateIndex() - Filename is not a hash, removing file. "
+           "[name=%s]", leaf.get()));
+      file->Remove(false);
+      continue;
+    }
+
+    CacheIndexEntry *entry = mIndex.GetEntry(hash);
+    if (entry && entry->IsRemoved()) {
+      if (entry->IsFresh()) {
+        LOG(("CacheIndex::UpdateIndex() - Found file that should not exist. "
+             "[name=%s]", leaf.get()));
+        entry->Log();
+      }
+      entry = nullptr;
+    }
+
+#ifdef DEBUG
+    nsRefPtr<CacheFileHandle> handle;
+    CacheFileIOManager::gInstance->mHandles.GetHandle(&hash, false,
+                                                      getter_AddRefs(handle));
+#endif
+
+    if (entry && entry->IsFresh()) {
+      // the entry is up to date
+      LOG(("CacheIndex::UpdateIndex() - Skipping file because the entry is up "
+           " to date. [name=%s]", leaf.get()));
+      entry->Log();
+      // there must be an active CacheFile if the entry is not initialized
+      MOZ_ASSERT(entry->IsInitialized() || handle);
+      continue;
+    }
+
+    MOZ_ASSERT(!handle);
+
+    if (entry) {
+      PRTime lastModifiedTime;
+      {
+        // Do not do IO under the lock.
+        CacheIndexAutoUnlock unlock(this);
+        rv = file->GetLastModifiedTime(&lastModifiedTime);
+      }
+      if (mState == SHUTDOWN) {
+        return;
+      }
+      if (NS_FAILED(rv)) {
+        LOG(("CacheIndex::UpdateIndex() - Cannot get lastModifiedTime. "
+             "[name=%s]", leaf.get()));
+        // Assume the file is newer than index
+      } else {
+        if (mIndexTimeStamp > (lastModifiedTime / PR_MSEC_PER_SEC)) {
+          LOG(("CacheIndex::UpdateIndex() - Skipping file because of last "
+               "modified time. [name=%s, indexTimeStamp=%u, "
+               "lastModifiedTime=%u]", leaf.get(), mIndexTimeStamp,
+               lastModifiedTime / PR_MSEC_PER_SEC));
+
+          CacheIndexEntryAutoManage entryMng(&hash, this);
+          entry->MarkFresh();
+          continue;
+        }
+      }
+    }
+
+    nsRefPtr<CacheFileMetadata> meta = new CacheFileMetadata();
+    int64_t size = 0;
+
+    {
+      // Do not do IO under the lock.
+      CacheIndexAutoUnlock unlock(this);
+      rv = meta->SyncReadMetadata(file);
+
+      if (NS_SUCCEEDED(rv)) {
+        rv = file->GetFileSize(&size);
+        if (NS_FAILED(rv)) {
+          LOG(("CacheIndex::UpdateIndex() - Cannot get filesize of file that "
+               "was successfully parsed. [name=%s]", leaf.get()));
+        }
+      }
+    }
+    if (mState == SHUTDOWN) {
+      return;
+    }
+
+    // Nobody could add the entry while the lock was released since we modify
+    // the index only on IO thread and this loop is executed on IO thread too.
+    entry = mIndex.GetEntry(hash);
+    MOZ_ASSERT(!entry || !entry->IsFresh());
+
+    CacheIndexEntryAutoManage entryMng(&hash, this);
+
+    if (NS_FAILED(rv)) {
+      LOG(("CacheIndex::UpdateIndex() - CacheFileMetadata::SyncReadMetadata() "
+           "failed, removing file. [name=%s]", leaf.get()));
+      file->Remove(false);
+      if (entry) {
+        entry->MarkRemoved();
+        entry->MarkFresh();
+        entry->MarkDirty();
+      }
+    } else {
+      entry = mIndex.PutEntry(hash);
+      InitEntryFromDiskData(entry, meta, size);
+      LOG(("CacheIndex::UpdateIndex() - Added/updated entry to/in index. "
+           "[hash=%s]", leaf.get()));
+      entry->Log();
+    }
+  }
+
+  nsRefPtr<CacheIOThread> ioThread = CacheFileIOManager::IOThread();
+  MOZ_ASSERT(ioThread);
+
+  rv = ioThread->Dispatch(this, CacheIOThread::BUILD_OR_UPDATE_INDEX);
+  if (NS_FAILED(rv)) {
+    NS_WARNING("CacheIndex::UpdateIndex() - Can't dispatch event");
+    LOG(("CacheIndex::UpdateIndex() - Can't dispatch event" ));
+    FinishUpdate(false);
+    return;
+  }
+}
+
+void
+CacheIndex::FinishUpdate(bool aSucceeded)
+{
+  LOG(("CacheIndex::FinishUpdate() [succeeded=%d]", aSucceeded));
+
+  MOZ_ASSERT((!aSucceeded && mState == SHUTDOWN) || mState == UPDATING);
+
+  AssertOwnsLock();
+
+  if (mDirEnumerator) {
+    if (NS_IsMainThread()) {
+      LOG(("CacheIndex::FinishUpdate() - posting of PreShutdownInternal failed?"
+           " Cannot safely release mDirEnumerator, leaking it!"));
+      NS_WARNING(("CacheIndex::FinishUpdate() - Leaking mDirEnumerator!"));
+      // This can happen only in case dispatching event to IO thread failed in
+      // CacheIndex::PreShutdown().
+      mDirEnumerator.forget(); // Leak it since dir enumerator is not threadsafe
+    } else {
+      mDirEnumerator->Close();
+      mDirEnumerator = nullptr;
+    }
+  }
+
+  if (!aSucceeded) {
+    mDontMarkIndexClean = true;
+  }
+
+  if (mState == UPDATING) {
+    if (aSucceeded) {
+      // If we've iterated over all entries successfully then all entries that
+      // really exist on the disk are now marked as fresh. All non-fresh entries
+      // don't exist anymore and must be removed from the index.
+      mIndex.EnumerateEntries(&CacheIndex::RemoveNonFreshEntries, this);
+    }
+
+    // Make sure we won't start update again. If the update failed, there is no
+    // reason to believe that it will succeed next time.
+    mIndexNeedsUpdate = false;
+
+    ChangeState(READY);
+    mLastDumpTime = TimeStamp::NowLoRes(); // Do not dump new index immediately
+  }
+}
+
+// static
+PLDHashOperator
+CacheIndex::RemoveNonFreshEntries(CacheIndexEntry *aEntry, void* aClosure)
+{
+  if (aEntry->IsFresh()) {
+    return PL_DHASH_NEXT;
+  }
+
+  LOG(("CacheFile::RemoveNonFreshEntries() - Removing entry. "
+       "[hash=%08x%08x%08x%08x%08x]", LOGSHA1(aEntry->Hash())));
+
+  CacheIndex *index = static_cast<CacheIndex *>(aClosure);
+
+  CacheIndexEntryAutoManage emng(aEntry->Hash(), index);
+  emng.DoNotSearchInIndex();
+
+  return PL_DHASH_REMOVE;
+}
+
+#ifdef PR_LOGGING
+// static
+char const *
+CacheIndex::StateString(EState aState)
+{
+  switch (aState) {
+    case INITIAL:  return "INITIAL";
+    case READING:  return "READING";
+    case WRITING:  return "WRITING";
+    case BUILDING: return "BUILDING";
+    case UPDATING: return "UPDATING";
+    case READY:    return "READY";
+    case SHUTDOWN: return "SHUTDOWN";
+  }
+
+  MOZ_ASSERT(false, "Unexpected state!");
+  return "?";
+}
+#endif
+
+void
+CacheIndex::ChangeState(EState aNewState)
+{
+  LOG(("CacheIndex::ChangeState() changing state %s -> %s", StateString(mState),
+       StateString(aNewState)));
+
+  // All pending updates should be processed before changing state
+  MOZ_ASSERT(mPendingUpdates.Count() == 0);
+
+  // PreShutdownInternal() should change the state to READY from every state. It
+  // may go through different states, but once we are in READY state the only
+  // possible transition is to SHUTDOWN state.
+  MOZ_ASSERT(!mShuttingDown || mState != READY || aNewState == SHUTDOWN);
+
+  // Start updating process when switching to READY state if needed
+  if (aNewState == READY && StartUpdatingIndexIfNeeded(true)) {
+    return;
+  }
+
+  mState = aNewState;
+}
+
+void
+CacheIndex::AllocBuffer()
+{
+  switch (mState) {
+    case WRITING:
+      mRWBufSize = sizeof(CacheIndexHeader) + sizeof(CacheHash::Hash32_t) +
+                   mProcessEntries * sizeof(CacheIndexRecord);
+      if (mRWBufSize > kMaxBufSize) {
+        mRWBufSize = kMaxBufSize;
+      }
+      break;
+    case READING:
+      mRWBufSize = kMaxBufSize;
+      break;
+    default:
+      MOZ_ASSERT(false, "Unexpected state!");
+  }
+
+  mRWBuf = static_cast<char *>(moz_xmalloc(mRWBufSize));
+}
+
+void
+CacheIndex::ReleaseBuffer()
+{
+  if (!mRWBuf) {
+    return;
+  }
+
+  free(mRWBuf);
+  mRWBuf = nullptr;
+  mRWBufSize = 0;
+  mRWBufPos = 0;
+}
+
+namespace { // anon
+
+class FrecencyComparator
+{
+public:
+  bool Equals(CacheIndexRecord* a, CacheIndexRecord* b) const {
+    return a->mFrecency == b->mFrecency;
+  }
+  bool LessThan(CacheIndexRecord* a, CacheIndexRecord* b) const {
+    return a->mFrecency < b->mFrecency;
+  }
+};
+
+class ExpirationComparator
+{
+public:
+  bool Equals(CacheIndexRecord* a, CacheIndexRecord* b) const {
+    return a->mExpirationTime == b->mExpirationTime;
+  }
+  bool LessThan(CacheIndexRecord* a, CacheIndexRecord* b) const {
+    return a->mExpirationTime < b->mExpirationTime;
+  }
+};
+
+} // anon
+
+void
+CacheIndex::InsertRecordToFrecencyArray(CacheIndexRecord *aRecord)
+{
+  LOG(("CacheIndex::InsertRecordToFrecencyArray() [record=%p, hash=%08x%08x%08x"
+       "%08x%08x]", aRecord, LOGSHA1(aRecord->mHash)));
+
+  MOZ_ASSERT(!mFrecencyArray.Contains(aRecord));
+  mFrecencyArray.InsertElementSorted(aRecord, FrecencyComparator());
+}
+
+void
+CacheIndex::InsertRecordToExpirationArray(CacheIndexRecord *aRecord)
+{
+  LOG(("CacheIndex::InsertRecordToExpirationArray() [record=%p, hash=%08x%08x"
+       "%08x%08x%08x]", aRecord, LOGSHA1(aRecord->mHash)));
+
+  MOZ_ASSERT(!mExpirationArray.Contains(aRecord));
+  mExpirationArray.InsertElementSorted(aRecord, ExpirationComparator());
+}
+
+void
+CacheIndex::RemoveRecordFromFrecencyArray(CacheIndexRecord *aRecord)
+{
+  LOG(("CacheIndex::RemoveRecordFromFrecencyArray() [record=%p]", aRecord));
+
+  DebugOnly<bool> removed;
+  removed = mFrecencyArray.RemoveElement(aRecord);
+  MOZ_ASSERT(removed);
+}
+
+void
+CacheIndex::RemoveRecordFromExpirationArray(CacheIndexRecord *aRecord)
+{
+  LOG(("CacheIndex::RemoveRecordFromExpirationArray() [record=%p]", aRecord));
+
+  DebugOnly<bool> removed;
+  removed = mExpirationArray.RemoveElement(aRecord);
+  MOZ_ASSERT(removed);
+}
+
+nsresult
+CacheIndex::Run()
+{
+  LOG(("CacheIndex::Run()"));
+
+  CacheIndexAutoLock lock(this);
+
+  if (!IsIndexUsable()) {
+    return NS_ERROR_NOT_AVAILABLE;
+  }
+
+  if (mState == READY && mShuttingDown) {
+    return NS_OK;
+  }
+
+  switch (mState) {
+    case BUILDING:
+      BuildIndex();
+      break;
+    case UPDATING:
+      UpdateIndex();
+      break;
+    default:
+      MOZ_ASSERT(false, "Unexpected state!");
+  }
+
+  return NS_OK;
+}
+
+nsresult
+CacheIndex::OnFileOpened(CacheFileHandle *aHandle, nsresult aResult)
+{
+  LOG(("CacheIndex::OnFileOpened() [handle=%p, result=0x%08x]", aHandle,
+       aResult));
+
+  nsresult rv;
+
+  CacheIndexAutoLock lock(this);
+
+  if (!IsIndexUsable()) {
+    return NS_ERROR_NOT_AVAILABLE;
+  }
+
+  if (mState == READY && mShuttingDown) {
+    return NS_OK;
+  }
+
+  switch (mState) {
+    case WRITING:
+      if (NS_FAILED(aResult)) {
+        LOG(("CacheIndex::OnFileOpened() - Can't open index file for writing "
+             "[rv=0x%08x]", aResult));
+        FinishWrite(false);
+      } else {
+        mIndexHandle = aHandle;
+        WriteRecords();
+      }
+      break;
+    case READING:
+      mReadOpenCount--;
+
+      if (mReadFailed) {
+        if (NS_SUCCEEDED(aResult)) {
+          CacheFileIOManager::DoomFile(aHandle, nullptr);
+        }
+
+        if (mReadOpenCount == 0) {
+          FinishRead(false);
+        }
+
+        return NS_OK;
+      }
+
+      switch (mReadOpenCount) {
+        case 2: // kIndexName
+          if (NS_FAILED(aResult)) {
+            mReadFailed = true;
+          } else {
+            MOZ_ASSERT(aHandle->Key() == kIndexName);
+            if (aHandle->FileSize() == 0) {
+              mReadFailed = true;
+              CacheFileIOManager::DoomFile(aHandle, nullptr);
+            } else {
+              mIndexHandle = aHandle;
+            }
+          }
+          break;
+        case 1: // kJournalName
+          if (NS_SUCCEEDED(aResult)) {
+            MOZ_ASSERT(aHandle->Key() == kJournalName);
+            if (aHandle->FileSize() == 0) {
+              CacheFileIOManager::DoomFile(aHandle, nullptr);
+            } else {
+              mJournalHandle = aHandle;
+            }
+          }
+          break;
+        case 0: // kTempIndexName
+          if (NS_SUCCEEDED(aResult)) {
+            MOZ_ASSERT(aHandle->Key() == kTempIndexName);
+            CacheFileIOManager::DoomFile(aHandle, nullptr);
+
+            if (mJournalHandle) { // this should never happen
+              LOG(("CacheIndex::OnFileOpened() - Unexpected state, all files "
+                   "[%s, %s, %s] should never exist. Removing whole index.",
+                   kIndexName, kJournalName, kTempIndexName));
+              FinishRead(false);
+              break;
+            }
+          }
+
+          if (mJournalHandle) {
+            // Rename journal to make sure we update index on next start in case
+            // firefox crashes
+            rv = CacheFileIOManager::RenameFile(
+              mJournalHandle, NS_LITERAL_CSTRING(kTempIndexName), this);
+            if (NS_FAILED(rv)) {
+              LOG(("CacheIndex::OnFileOpened() - CacheFileIOManager::RenameFile"
+                   "() failed synchronously [rv=0x%08x]", rv));
+              FinishRead(false);
+              break;
+            }
+            break;
+          }
+
+          StartReadingIndex();
+      }
+      break;
+    default:
+      MOZ_ASSERT(false, "Unexpected state!");
+  }
+
+  return NS_OK;
+}
+
+nsresult
+CacheIndex::OnDataWritten(CacheFileHandle *aHandle, const char *aBuf,
+                          nsresult aResult)
+{
+  LOG(("CacheIndex::OnDataWritten() [handle=%p, result=0x%08x]", aHandle,
+       aResult));
+
+  nsresult rv;
+
+  CacheIndexAutoLock lock(this);
+
+  if (!IsIndexUsable()) {
+    return NS_ERROR_NOT_AVAILABLE;
+  }
+
+  if (mState == READY && mShuttingDown) {
+    return NS_OK;
+  }
+
+  switch (mState) {
+    case WRITING:
+      if (NS_FAILED(aResult)) {
+        FinishWrite(false);
+      } else {
+        if (mSkipEntries == mProcessEntries) {
+          rv = CacheFileIOManager::RenameFile(mIndexHandle,
+                                              NS_LITERAL_CSTRING(kIndexName),
+                                              this);
+          if (NS_FAILED(rv)) {
+            LOG(("CacheIndex::OnDataWritten() - CacheFileIOManager::"
+                 "RenameFile() failed synchronously [rv=0x%08x]", rv));
+            FinishWrite(false);
+          }
+        } else {
+          WriteRecords();
+        }
+      }
+      break;
+    default:
+      MOZ_ASSERT(false, "Unexpected state!");
+  }
+
+  return NS_OK;
+}
+
+nsresult
+CacheIndex::OnDataRead(CacheFileHandle *aHandle, char *aBuf, nsresult aResult)
+{
+  LOG(("CacheIndex::OnDataRead() [handle=%p, result=0x%08x]", aHandle,
+       aResult));
+
+  CacheIndexAutoLock lock(this);
+
+  if (!IsIndexUsable()) {
+    return NS_ERROR_NOT_AVAILABLE;
+  }
+
+  if (mState == READY && mShuttingDown) {
+    return NS_OK;
+  }
+
+  switch (mState) {
+    case READING:
+      if (NS_FAILED(aResult)) {
+        FinishRead(false);
+      } else {
+        if (!mIndexOnDiskIsValid) {
+          ParseRecords();
+        } else {
+          ParseJournal();
+        }
+      }
+      break;
+    default:
+      MOZ_ASSERT(false, "Unexpected state!");
+  }
+
+  return NS_OK;
+}
+
+nsresult
+CacheIndex::OnFileDoomed(CacheFileHandle *aHandle, nsresult aResult)
+{
+  MOZ_CRASH("CacheIndex::OnFileDoomed should not be called!");
+  return NS_ERROR_UNEXPECTED;
+}
+
+nsresult
+CacheIndex::OnEOFSet(CacheFileHandle *aHandle, nsresult aResult)
+{
+  MOZ_CRASH("CacheIndex::OnEOFSet should not be called!");
+  return NS_ERROR_UNEXPECTED;
+}
+
+nsresult
+CacheIndex::OnFileRenamed(CacheFileHandle *aHandle, nsresult aResult)
+{
+  LOG(("CacheIndex::OnFileRenamed() [handle=%p, result=0x%08x]", aHandle,
+       aResult));
+
+  CacheIndexAutoLock lock(this);
+
+  if (!IsIndexUsable()) {
+    return NS_ERROR_NOT_AVAILABLE;
+  }
+
+  if (mState == READY && mShuttingDown) {
+    return NS_OK;
+  }
+
+  switch (mState) {
+    case WRITING:
+      // This is a result of renaming the new index written to tmpfile to index
+      // file. This is the last step when writing the index and the whole
+      // writing process is successful iff renaming was successful.
+      FinishWrite(NS_SUCCEEDED(aResult));
+      break;
+    case READING:
+      // This is a result of renaming journal file to tmpfile. It is renamed
+      // before we start reading index and journal file and it should normally
+      // succeed. If it fails give up reading of index.
+      if (NS_FAILED(aResult)) {
+        FinishRead(false);
+      } else {
+        StartReadingIndex();
+      }
+      break;
+    default:
+      MOZ_ASSERT(false, "Unexpected state!");
+  }
+
+  return NS_OK;
+}
+
+} // net
+} // mozilla
new file mode 100644
--- /dev/null
+++ b/netwerk/cache2/CacheIndex.h
@@ -0,0 +1,853 @@
+/* This Source Code Form is subject to the terms of the Mozilla Public
+ * License, v. 2.0. If a copy of the MPL was not distributed with this
+ * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
+
+#ifndef CacheIndex__h__
+#define CacheIndex__h__
+
+#include "CacheLog.h"
+#include "CacheFileIOManager.h"
+#include "nsIRunnable.h"
+#include "CacheHashUtils.h"
+#include "nsICacheEntry.h"
+#include "nsILoadContextInfo.h"
+#include "nsTHashtable.h"
+#include "mozilla/SHA1.h"
+#include "mozilla/Mutex.h"
+#include "mozilla/Endian.h"
+#include "mozilla/TimeStamp.h"
+
+class nsIFile;
+class nsIDirectoryEnumerator;
+class nsITimer;
+
+
+#ifdef DEBUG
+#define DEBUG_STATS 1
+#endif
+
+namespace mozilla {
+namespace net {
+
+class CacheFileMetadata;
+
+typedef struct {
+  // Version of the index. The index must be ignored and deleted when the file
+  // on disk was written with a newer version.
+  uint32_t mVersion;
+
+  // Timestamp of time when the last successful write of the index started.
+  // During update process we use this timestamp for a quick validation of entry
+  // files. If last modified time of the file is lower than this timestamp, we
+  // skip parsing of such file since the information in index should be up to
+  // date.
+  uint32_t mTimeStamp;
+
+  // We set this flag as soon as possible after parsing index during startup
+  // and clean it after we write journal to disk during shutdown. We ignore the
+  // journal and start update process whenever this flag is set during index
+  // parsing.
+  uint32_t mIsDirty;
+} CacheIndexHeader;
+
+struct CacheIndexRecord {
+  SHA1Sum::Hash mHash;
+  uint32_t      mFrecency;
+  uint32_t      mExpirationTime;
+  uint32_t      mAppId;
+
+  /*
+   *    1000 0000 0000 0000 0000 0000 0000 0000 : initialized
+   *    0100 0000 0000 0000 0000 0000 0000 0000 : anonymous
+   *    0010 0000 0000 0000 0000 0000 0000 0000 : inBrowser
+   *    0001 0000 0000 0000 0000 0000 0000 0000 : removed
+   *    0000 1000 0000 0000 0000 0000 0000 0000 : dirty
+   *    0000 0100 0000 0000 0000 0000 0000 0000 : fresh
+   *    0000 0011 0000 0000 0000 0000 0000 0000 : reserved
+   *    0000 0000 1111 1111 1111 1111 1111 1111 : file size (in kB)
+   */
+  uint32_t      mFlags;
+
+  CacheIndexRecord()
+    : mFrecency(0)
+    , mExpirationTime(nsICacheEntry::NO_EXPIRATION_TIME)
+    , mAppId(nsILoadContextInfo::NO_APP_ID)
+    , mFlags(0)
+  {}
+};
+
+class CacheIndexEntry : public PLDHashEntryHdr
+{
+public:
+  typedef const SHA1Sum::Hash& KeyType;
+  typedef const SHA1Sum::Hash* KeyTypePointer;
+
+  CacheIndexEntry(KeyTypePointer aKey)
+  {
+    MOZ_COUNT_CTOR(CacheIndexEntry);
+    mRec = new CacheIndexRecord();
+    LOG(("CacheIndexEntry::CacheIndexEntry() - Created record [rec=%p]", mRec));
+    memcpy(&mRec->mHash, aKey, sizeof(SHA1Sum::Hash));
+  }
+  CacheIndexEntry(const CacheIndexEntry& aOther)
+  {
+    NS_NOTREACHED("CacheIndexEntry copy constructor is forbidden!");
+  }
+  ~CacheIndexEntry()
+  {
+    MOZ_COUNT_DTOR(CacheIndexEntry);
+    LOG(("CacheIndexEntry::~CacheIndexEntry() - Deleting record [rec=%p]",
+         mRec));
+    delete mRec;
+  }
+
+  // KeyEquals(): does this entry match this key?
+  bool KeyEquals(KeyTypePointer aKey) const
+  {
+    return memcmp(&mRec->mHash, aKey, sizeof(SHA1Sum::Hash)) == 0;
+  }
+
+  // KeyToPointer(): Convert KeyType to KeyTypePointer
+  static KeyTypePointer KeyToPointer(KeyType aKey) { return &aKey; }
+
+  // HashKey(): calculate the hash number
+  static PLDHashNumber HashKey(KeyTypePointer aKey)
+  {
+    return (reinterpret_cast<const uint32_t *>(aKey))[0];
+  }
+
+  // ALLOW_MEMMOVE can we move this class with memmove(), or do we have
+  // to use the copy constructor?
+  enum { ALLOW_MEMMOVE = true };
+
+  bool operator==(const CacheIndexEntry& aOther) const
+  {
+    return KeyEquals(&aOther.mRec->mHash);
+  }
+
+  CacheIndexEntry& operator=(const CacheIndexEntry& aOther)
+  {
+    MOZ_ASSERT(memcmp(&mRec->mHash, &aOther.mRec->mHash,
+               sizeof(SHA1Sum::Hash)) == 0);
+    mRec->mFrecency = aOther.mRec->mFrecency;
+    mRec->mExpirationTime = aOther.mRec->mExpirationTime;
+    mRec->mAppId = aOther.mRec->mAppId;
+    mRec->mFlags = aOther.mRec->mFlags;
+    return *this;
+  }
+
+  void InitNew()
+  {
+    mRec->mFrecency = 0;
+    mRec->mExpirationTime = nsICacheEntry::NO_EXPIRATION_TIME;
+    mRec->mAppId = nsILoadContextInfo::NO_APP_ID;
+    mRec->mFlags = 0;
+  }
+
+  void Init(uint32_t aAppId, bool aAnonymous, bool aInBrowser)
+  {
+    MOZ_ASSERT(mRec->mFrecency == 0);
+    MOZ_ASSERT(mRec->mExpirationTime == nsICacheEntry::NO_EXPIRATION_TIME);
+    MOZ_ASSERT(mRec->mAppId == nsILoadContextInfo::NO_APP_ID);
+    // When we init the entry it must be fresh and may be dirty
+    MOZ_ASSERT((mRec->mFlags & ~kDirtyMask) == kFreshMask);
+
+    mRec->mAppId = aAppId;
+    mRec->mFlags |= kInitializedMask;
+    if (aAnonymous) {
+      mRec->mFlags |= kAnonymousMask;
+    }
+    if (aInBrowser) {
+      mRec->mFlags |= kInBrowserMask;
+    }
+  }
+
+  const SHA1Sum::Hash * Hash() { return &mRec->mHash; }
+
+  bool IsInitialized() { return !!(mRec->mFlags & kInitializedMask); }
+
+  uint32_t AppId() { return mRec->mAppId; }
+  bool     Anonymous() { return !!(mRec->mFlags & kAnonymousMask); }
+  bool     InBrowser() { return !!(mRec->mFlags & kInBrowserMask); }
+
+  bool IsRemoved() { return !!(mRec->mFlags & kRemovedMask); }
+  void MarkRemoved() { mRec->mFlags |= kRemovedMask; }
+
+  bool IsDirty() { return !!(mRec->mFlags & kDirtyMask); }
+  void MarkDirty() { mRec->mFlags |= kDirtyMask; }
+  void ClearDirty() { mRec->mFlags &= ~kDirtyMask; }
+
+  bool IsFresh() { return !!(mRec->mFlags & kFreshMask); }
+  void MarkFresh() { mRec->mFlags |= kFreshMask; }
+
+  void     SetFrecency(uint32_t aFrecency) { mRec->mFrecency = aFrecency; }
+  uint32_t GetFrecency() { return mRec->mFrecency; }
+
+  void     SetExpirationTime(uint32_t aExpirationTime)
+  {
+    mRec->mExpirationTime = aExpirationTime;
+  }
+  uint32_t GetExpirationTime() { return mRec->mExpirationTime; }
+
+  // Sets filesize in kilobytes.
+  void     SetFileSize(uint32_t aFileSize)
+  {
+    if (aFileSize > kFileSizeMask) {
+      LOG(("CacheIndexEntry::SetFileSize() - FileSize is too large, "
+           "truncating to %u", kFileSizeMask));
+      aFileSize = kFileSizeMask;
+    }
+    mRec->mFlags &= ~kFileSizeMask;
+    mRec->mFlags |= aFileSize;
+  }
+  // Returns filesize in kilobytes.
+  uint32_t GetFileSize() { return mRec->mFlags & kFileSizeMask; }
+  bool     IsFileEmpty() { return GetFileSize() == 0; }
+
+  void WriteToBuf(void *aBuf)
+  {
+    CacheIndexRecord *dst = reinterpret_cast<CacheIndexRecord *>(aBuf);
+
+    // Copy the whole record to the buffer.
+    memcpy(aBuf, mRec, sizeof(CacheIndexRecord));
+
+    // Dirty and fresh flags should never go to disk, since they make sense only
+    // during current session.
+    dst->mFlags &= ~kDirtyMask;
+    dst->mFlags &= ~kFreshMask;
+
+#if defined(IS_LITTLE_ENDIAN)
+    // Data in the buffer are in machine byte order and we want them in network
+    // byte order.
+    NetworkEndian::writeUint32(&dst->mFrecency, dst->mFrecency);
+    NetworkEndian::writeUint32(&dst->mExpirationTime, dst->mExpirationTime);
+    NetworkEndian::writeUint32(&dst->mAppId, dst->mAppId);
+    NetworkEndian::writeUint32(&dst->mFlags, dst->mFlags);
+#endif
+  }
+
+  void ReadFromBuf(void *aBuf)
+  {
+    CacheIndexRecord *src= reinterpret_cast<CacheIndexRecord *>(aBuf);
+    MOZ_ASSERT(memcmp(&mRec->mHash, &src->mHash,
+               sizeof(SHA1Sum::Hash)) == 0);
+
+    mRec->mFrecency = NetworkEndian::readUint32(&src->mFrecency);
+    mRec->mExpirationTime = NetworkEndian::readUint32(&src->mExpirationTime);
+    mRec->mAppId = NetworkEndian::readUint32(&src->mAppId);
+    mRec->mFlags = NetworkEndian::readUint32(&src->mFlags);
+  }
+
+  void Log() {
+    LOG(("CacheIndexEntry::Log() [this=%p, hash=%08x%08x%08x%08x%08x, fresh=%u,"
+         " initialized=%u, removed=%u, dirty=%u, anonymous=%u, inBrowser=%u, "
+         "appId=%u, frecency=%u, expirationTime=%u, size=%u]",
+         this, LOGSHA1(mRec->mHash), IsFresh(), IsInitialized(), IsRemoved(),
+         IsDirty(), Anonymous(), InBrowser(), AppId(), GetFrecency(),
+         GetExpirationTime(), GetFileSize()));
+  }
+
+private:
+  friend class CacheIndex;
+  friend class CacheIndexEntryAutoManage;
+
+  static const uint32_t kInitializedMask = 0x80000000;
+  static const uint32_t kAnonymousMask   = 0x40000000;
+  static const uint32_t kInBrowserMask   = 0x20000000;
+
+  // This flag is set when the entry was removed. We need to keep this
+  // information in memory until we write the index file.
+  static const uint32_t kRemovedMask     = 0x10000000;
+
+  // This flag is set when the information in memory is not in sync with the
+  // information in index file on disk.
+  static const uint32_t kDirtyMask       = 0x08000000;
+
+  // This flag is set when the information about the entry is fresh, i.e.
+  // we've created or opened this entry during this session, or we've seen
+  // this entry during update or build process.
+  static const uint32_t kFreshMask       = 0x04000000;
+
+  static const uint32_t kReservedMask    = 0x03000000;
+
+  // FileSize in kilobytes
+  static const uint32_t kFileSizeMask    = 0x00FFFFFF;
+
+  CacheIndexRecord *mRec;
+};
+
+class CacheIndexStats
+{
+public:
+  CacheIndexStats()
+    : mCount(0)
+    , mNotInitialized(0)
+    , mRemoved(0)
+    , mDirty(0)
+    , mFresh(0)
+    , mEmpty(0)
+    , mSize(0)
+#ifdef DEBUG
+    , mStateLogged(false)
+    , mDisableLogging(false)
+#endif
+  {
+  }
+
+  bool operator==(const CacheIndexStats& aOther) const
+  {
+    return
+#ifdef DEBUG
+           aOther.mStateLogged == mStateLogged &&
+#endif
+           aOther.mCount == mCount &&
+           aOther.mNotInitialized == mNotInitialized &&
+           aOther.mRemoved == mRemoved &&
+           aOther.mDirty == mDirty &&
+           aOther.mFresh == mFresh &&
+           aOther.mEmpty == mEmpty &&
+           aOther.mSize == mSize;
+  }
+
+#ifdef DEBUG
+  void DisableLogging() {
+    mDisableLogging = true;
+  }
+#endif
+
+  void Log() {
+    LOG(("CacheIndexStats::Log() [count=%u, notInitialized=%u, removed=%u, "
+         "dirty=%u, fresh=%u, empty=%u, size=%lld]", mCount, mNotInitialized,
+         mRemoved, mDirty, mFresh, mEmpty, mSize));
+  }
+
+#ifdef DEBUG
+  bool StateLogged() {
+    return mStateLogged;
+  }
+#endif
+
+  uint32_t Count() {
+    MOZ_ASSERT(!mStateLogged, "CacheIndexStats::Count() - state logged!");
+    return mCount;
+  }
+
+  uint32_t Dirty() {
+    MOZ_ASSERT(!mStateLogged, "CacheIndexStats::Dirty() - state logged!");
+    return mDirty;
+  }
+
+  uint32_t Fresh() {
+    MOZ_ASSERT(!mStateLogged, "CacheIndexStats::Fresh() - state logged!");
+    return mFresh;
+  }
+
+  uint32_t ActiveEntriesCount() {
+    MOZ_ASSERT(!mStateLogged, "CacheIndexStats::ActiveEntriesCount() - state "
+               "logged!");
+    return mCount - mRemoved - mNotInitialized - mEmpty;
+  }
+
+  int64_t Size() {
+    MOZ_ASSERT(!mStateLogged, "CacheIndexStats::Size() - state logged!");
+    return mSize;
+  }
+
+  void BeforeChange(CacheIndexEntry *aEntry) {
+#ifdef DEBUG_STATS
+    if (!mDisableLogging) {
+      LOG(("CacheIndexStats::BeforeChange()"));
+      Log();
+    }
+#endif
+
+    MOZ_ASSERT(!mStateLogged, "CacheIndexStats::BeforeChange() - state "
+               "logged!");
+#ifdef DEBUG
+    mStateLogged = true;
+#endif
+    if (aEntry) {
+      MOZ_ASSERT(mCount);
+      mCount--;
+      if (aEntry->IsDirty()) {
+        MOZ_ASSERT(mDirty);
+        mDirty--;
+      }
+      if (aEntry->IsFresh()) {
+        MOZ_ASSERT(mFresh);
+        mFresh--;
+      }
+      if (aEntry->IsRemoved()) {
+        MOZ_ASSERT(mRemoved);
+        mRemoved--;
+      } else {
+        if (!aEntry->IsInitialized()) {
+          MOZ_ASSERT(mNotInitialized);
+          mNotInitialized--;
+        } else {
+          if (aEntry->IsFileEmpty()) {
+            MOZ_ASSERT(mEmpty);
+            mEmpty--;
+          } else {
+            MOZ_ASSERT(mSize);
+            mSize -= aEntry->GetFileSize();
+          }
+        }
+      }
+    }
+  }
+
+  void AfterChange(CacheIndexEntry *aEntry) {
+    MOZ_ASSERT(mStateLogged, "CacheIndexStats::AfterChange() - state not "
+               "logged!");
+#ifdef DEBUG
+    mStateLogged = false;
+#endif
+    if (aEntry) {
+      ++mCount;
+      if (aEntry->IsDirty()) {
+        mDirty++;
+      }
+      if (aEntry->IsFresh()) {
+        mFresh++;
+      }
+      if (aEntry->IsRemoved()) {
+        mRemoved++;
+      } else {
+        if (!aEntry->IsInitialized()) {
+          mNotInitialized++;
+        } else {
+          if (aEntry->IsFileEmpty()) {
+            mEmpty++;
+          } else {
+            mSize += aEntry->GetFileSize();
+          }
+        }
+      }
+    }
+
+#ifdef DEBUG_STATS
+    if (!mDisableLogging) {
+      LOG(("CacheIndexStats::AfterChange()"));
+      Log();
+    }
+#endif
+  }
+
+private:
+  uint32_t mCount;
+  uint32_t mNotInitialized;
+  uint32_t mRemoved;
+  uint32_t mDirty;
+  uint32_t mFresh;
+  uint32_t mEmpty;
+  int64_t  mSize;
+#ifdef DEBUG
+  // We completely remove the data about an entry from the stats in
+  // BeforeChange() and set this flag to true. The entry is then modified,
+  // deleted or created and the data is again put into the stats and this flag
+  // set to false. Statistics must not be read during this time since the
+  // information is not correct.
+  bool     mStateLogged;
+
+  // Disables logging in this instance of CacheIndexStats
+  bool     mDisableLogging;
+#endif
+};
+
+class CacheIndex : public CacheFileIOListener
+                 , public nsIRunnable
+{
+public:
+  NS_DECL_THREADSAFE_ISUPPORTS
+  NS_DECL_NSIRUNNABLE
+
+  CacheIndex();
+
+  static nsresult Init(nsIFile *aCacheDirectory);
+  static nsresult PreShutdown();
+  static nsresult Shutdown();
+
+  // Following methods can be called only on IO thread.
+
+  // Add entry to the index. The entry shouldn't be present in index. This
+  // method is called whenever a new handle for a new entry file is created. The
+  // newly created entry is not initialized and it must be either initialized
+  // with InitEntry() or removed with RemoveEntry().
+  static nsresult AddEntry(const SHA1Sum::Hash *aHash);
+
+  // Inform index about an existing entry that should be present in index. This
+  // method is called whenever a new handle for an existing entry file is
+  // created. Like in case of AddEntry(), either InitEntry() or RemoveEntry()
+  // must be called on the entry, since the entry is not initizlized if the
+  // index is outdated.
+  static nsresult EnsureEntryExists(const SHA1Sum::Hash *aHash);
+
+  // Initialize the entry. It MUST be present in index. Call to AddEntry() or
+  // EnsureEntryExists() must precede the call to this method.
+  static nsresult InitEntry(const SHA1Sum::Hash *aHash,
+                            uint32_t             aAppId,
+                            bool                 aAnonymous,
+                            bool                 aInBrowser);
+
+  // Remove entry from index. The entry should be present in index.
+  static nsresult RemoveEntry(const SHA1Sum::Hash *aHash);
+
+  // Update some information in entry. The entry MUST be present in index and
+  // MUST be initialized. Call to AddEntry() or EnsureEntryExists() and to
+  // InitEntry() must precede the call to this method.
+  // Pass nullptr if the value didn't change.
+  static nsresult UpdateEntry(const SHA1Sum::Hash *aHash,
+                              const uint32_t      *aFrecency,
+                              const uint32_t      *aExpirationTime,
+                              const uint32_t      *aSize);
+
+  enum EntryStatus {
+    EXISTS         = 0,
+    DOES_NOT_EXIST = 1,
+    DO_NOT_KNOW    = 2
+  };
+
+  // Returns status of the entry in index for the given key. It can be called
+  // on any thread.
+  static nsresult HasEntry(const nsACString &aKey, EntryStatus *_retval);
+
+private:
+  friend class CacheIndexEntryAutoManage;
+  friend class CacheIndexAutoLock;
+  friend class CacheIndexAutoUnlock;
+
+  virtual ~CacheIndex();
+
+  NS_IMETHOD OnFileOpened(CacheFileHandle *aHandle, nsresult aResult);
+  NS_IMETHOD OnDataWritten(CacheFileHandle *aHandle, const char *aBuf,
+                           nsresult aResult);
+  NS_IMETHOD OnDataRead(CacheFileHandle *aHandle, char *aBuf, nsresult aResult);
+  NS_IMETHOD OnFileDoomed(CacheFileHandle *aHandle, nsresult aResult);
+  NS_IMETHOD OnEOFSet(CacheFileHandle *aHandle, nsresult aResult);
+  NS_IMETHOD OnFileRenamed(CacheFileHandle *aHandle, nsresult aResult);
+
+  void     Lock();
+  void     Unlock();
+  void     AssertOwnsLock();
+
+  nsresult InitInternal(nsIFile *aCacheDirectory);
+  void     PreShutdownInternal();
+
+  // This method returns false when index is not initialized or is shut down.
+  bool IsIndexUsable();
+
+  // This method checks whether the entry has the same values of appId,
+  // isAnonymous and isInBrowser. We don't expect to find a collision since
+  // these values are part of the key that we hash and we use a strong hash
+  // function.
+  static bool IsCollision(CacheIndexEntry *aEntry,
+                          uint32_t         aAppId,
+                          bool             aAnonymous,
+                          bool             aInBrowser);
+
+  // Checks whether any of the information about the entry has changed.
+  static bool HasEntryChanged(CacheIndexEntry *aEntry,
+                              const uint32_t  *aFrecency,
+                              const uint32_t  *aExpirationTime,
+                              const uint32_t  *aSize);
+
+  // Merge all pending operations from mPendingUpdates into mIndex.
+  void ProcessPendingOperations();
+  static PLDHashOperator UpdateEntryInIndex(CacheIndexEntry *aEntry,
+                                            void* aClosure);
+
+  // Following methods perform writing of the index file.
+  //
+  // The index is written periodically, but not earlier than once in
+  // kMinDumpInterval and there must be at least kMinUnwrittenChanges
+  // differences between index on disk and in memory. Index is always first
+  // written to a temporary file and the old index file is replaced when the
+  // writing process succeeds.
+  //
+  // Starts writing of index when both limits (minimal delay between writes and
+  // minimum number of changes in index) were exceeded.
+  bool WriteIndexToDiskIfNeeded();
+  // Starts writing of index file.
+  void WriteIndexToDisk();
+  // Serializes part of mIndex hashtable to the write buffer a writes the buffer
+  // to the file.
+  void WriteRecords();
+  // Finalizes writing process.
+  void FinishWrite(bool aSucceeded);
+
+  static PLDHashOperator CopyRecordsToRWBuf(CacheIndexEntry *aEntry,
+                                            void* aClosure);
+  static PLDHashOperator ApplyIndexChanges(CacheIndexEntry *aEntry,
+                                           void* aClosure);
+
+  // Following methods perform writing of the journal during shutdown. All these
+  // methods must be called only during shutdown since they write/delete files
+  // directly on the main thread instead of using CacheFileIOManager that does
+  // it asynchronously on IO thread. Journal contains only entries that are
+  // dirty, i.e. changes that are not present in the index file on the disk.
+  // When the log is written successfully, the dirty flag in index file is
+  // cleared.
+  nsresult GetFile(const nsACString &aName, nsIFile **_retval);
+  nsresult RemoveFile(const nsACString &aName);
+  void     RemoveIndexFromDisk();
+  // Writes journal to the disk and clears dirty flag in index header.
+  nsresult WriteLogToDisk();
+
+  static PLDHashOperator WriteEntryToLog(CacheIndexEntry *aEntry,
+                                         void* aClosure);
+
+  // Following methods perform reading of the index from the disk.
+  //
+  // Index is read at startup just after initializing the CacheIndex. There are
+  // 3 files used when manipulating with index: index file, journal file and
+  // a temporary file. All files contain the hash of the data, so we can check
+  // whether the content is valid and complete. Index file contains also a dirty
+  // flag in the index header which is unset on a clean shutdown. During opening
+  // and reading of the files we determine the status of the whole index from
+  // the states of the separate files. Following table shows all possible
+  // combinations:
+  //
+  // index, journal, tmpfile
+  // M      *        *       - index is missing    -> BUILD
+  // I      *        *       - index is invalid    -> BUILD
+  // D      *        *       - index is dirty      -> UPDATE
+  // C      M        *       - index is dirty      -> UPDATE
+  // C      I        *       - unexpected state    -> UPDATE
+  // C      V        E       - unexpected state    -> UPDATE
+  // C      V        M       - index is up to date -> READY
+  //
+  // where the letters mean:
+  //   * - any state
+  //   E - file exists
+  //   M - file is missing
+  //   I - data is invalid (parsing failed or hash didn't match)
+  //   D - dirty (data in index file is correct, but dirty flag is set)
+  //   C - clean (index file is clean)
+  //   V - valid (data in journal file is correct)
+  //
+  // Note: We accept the data from journal only when the index is up to date as
+  // a whole (i.e. C,V,M state).
+  //
+  // We rename the journal file to the temporary file as soon as possible after
+  // initial test to ensure that we start update process on the next startup if
+  // FF crashes during parsing of the index.
+  //
+  // Initiates reading index from disk.
+  void ReadIndexFromDisk();
+  // Starts reading data from index file.
+  void StartReadingIndex();
+  // Parses data read from index file.
+  void ParseRecords();
+  // Starts reading data from journal file.
+  void StartReadingJournal();
+  // Parses data read from journal file.
+  void ParseJournal();
+  // Merges entries from journal into mIndex.
+  void MergeJournal();
+  // In debug build this method checks that we have no fresh entry in mIndex
+  // after we finish reading index and before we process pending operations.
+  void EnsureNoFreshEntry();
+  // In debug build this method is called after processing pending operations
+  // to make sure mIndexStats contains correct information.
+  void EnsureCorrectStats();
+  static PLDHashOperator SumIndexStats(CacheIndexEntry *aEntry, void* aClosure);
+  // Finalizes reading process.
+  void FinishRead(bool aSucceeded);
+
+  static PLDHashOperator ProcessJournalEntry(CacheIndexEntry *aEntry,
+                                             void* aClosure);
+
+  // Following methods perform updating and building of the index.
+  // Timer callback that starts update or build process.
+  static void DelayedBuildUpdate(nsITimer *aTimer, void *aClosure);
+  // Posts timer event that start update or build process.
+  nsresult ScheduleBuildUpdateTimer(uint32_t aDelay);
+  nsresult SetupDirectoryEnumerator();
+  void InitEntryFromDiskData(CacheIndexEntry *aEntry,
+                             CacheFileMetadata *aMetaData,
+                             int64_t aFileSize);
+  // Starts build process or fires a timer when it is too early after startup.
+  void StartBuildingIndex();
+  // Iterates through all files in entries directory that we didn't create/open
+  // during this session, parses them and adds the entries to the index.
+  void BuildIndex();
+  // Finalizes build process.
+  void FinishBuild(bool aSucceeded);
+
+  bool StartUpdatingIndexIfNeeded(bool aSwitchingToReadyState = false);
+  // Starts update process or fires a timer when it is too early after startup.
+  void StartUpdatingIndex();
+  // Iterates through all files in entries directory that we didn't create/open
+  // during this session and theirs last modified time is newer than timestamp
+  // in the index header. Parses the files and adds the entries to the index.
+  void UpdateIndex();
+  // Finalizes update process.
+  void FinishUpdate(bool aSucceeded);
+
+  static PLDHashOperator RemoveNonFreshEntries(CacheIndexEntry *aEntry,
+                                               void* aClosure);
+
+  enum EState {
+    // Initial state in which the index is not usable
+    // Possible transitions:
+    //  -> READING
+    INITIAL  = 0,
+
+    // Index is being read from the disk.
+    // Possible transitions:
+    //  -> INITIAL  - We failed to dispatch a read event.
+    //  -> BUILDING - No or corrupted index file was found.
+    //  -> UPDATING - No or corrupted journal file was found.
+    //              - Dirty flag was set in index header.
+    //  -> READY    - Index was read successfully or was interrupted by
+    //                pre-shutdown.
+    //  -> SHUTDOWN - This could happen only in case of pre-shutdown failure.
+    READING  = 1,
+
+    // Index is being written to the disk.
+    // Possible transitions:
+    //  -> READY    - Writing of index finished or was interrupted by
+    //                pre-shutdown..
+    //  -> UPDATING - Writing of index finished, but index was found outdated
+    //                during writing.
+    //  -> SHUTDOWN - This could happen only in case of pre-shutdown failure.
+    WRITING  = 2,
+
+    // Index is being build.
+    // Possible transitions:
+    //  -> READY    - Building of index finished or was interrupted by
+    //                pre-shutdown.
+    //  -> SHUTDOWN - This could happen only in case of pre-shutdown failure.
+    BUILDING = 3,
+
+    // Index is being updated.
+    // Possible transitions:
+    //  -> READY    - Updating of index finished or was interrupted by
+    //                pre-shutdown.
+    //  -> SHUTDOWN - This could happen only in case of pre-shutdown failure.
+    UPDATING = 4,
+
+    // Index is ready.
+    // Possible transitions:
+    //  -> UPDATING - Index was found outdated.
+    //  -> SHUTDOWN - Index is shutting down.
+    READY    = 5,
+
+    // Index is shutting down.
+    SHUTDOWN = 6
+  };
+
+#ifdef PR_LOGGING
+  static char const * StateString(EState aState);
+#endif
+  void ChangeState(EState aNewState);
+
+  // Allocates and releases buffer used for reading and writing index.
+  void AllocBuffer();
+  void ReleaseBuffer();
+
+  // Methods used by CacheIndexEntryAutoManage to keep the arrays up to date.
+  void InsertRecordToFrecencyArray(CacheIndexRecord *aRecord);
+  void InsertRecordToExpirationArray(CacheIndexRecord *aRecord);
+  void RemoveRecordFromFrecencyArray(CacheIndexRecord *aRecord);
+  void RemoveRecordFromExpirationArray(CacheIndexRecord *aRecord);
+
+  static CacheIndex *gInstance;
+
+  nsCOMPtr<nsIFile> mCacheDirectory;
+
+  mozilla::Mutex mLock;
+  EState         mState;
+  // Timestamp of time when the index was initialized. We use it to delay
+  // initial update or build of index.
+  TimeStamp      mStartTime;
+  // Set to true in PreShutdown(), it is checked on variaous places to prevent
+  // starting any process (write, update, etc.) during shutdown.
+  bool           mShuttingDown;
+  // When set to true, update process should start as soon as possible. This
+  // flag is set whenever we find some inconsistency which would be fixed by
+  // update process. The flag is checked always when switching to READY state.
+  // To make sure we start the update process as soon as possible, methods that
+  // set this flag should also call StartUpdatingIndexIfNeeded() to cover the
+  // case when we are currently in READY state.
+  bool           mIndexNeedsUpdate;
+  // Whether the index file on disk exists and is valid.
+  bool           mIndexOnDiskIsValid;
+  // When something goes wrong during updating or building process, we don't
+  // mark index clean (and also don't write journal) to ensure that update or
+  // build will be initiated on the next start.
+  bool           mDontMarkIndexClean;
+  // Timestamp value from index file. It is used during update process to skip
+  // entries that were last modified before this timestamp.
+  uint32_t       mIndexTimeStamp;
+  // Timestamp of last time the index was dumped to disk.
+  // NOTE: The index might not be necessarily dumped at this time. The value
+  // is used to schedule next dump of the index.
+  TimeStamp      mLastDumpTime;
+
+  // Timer of delayed update/build.
+  nsCOMPtr<nsITimer> mTimer;
+
+  // Helper members used when reading/writing index from/to disk.
+  // Contains number of entries that should be skipped:
+  //  - in hashtable when writing index because they were already written
+  //  - in index file when reading index because they were already read
+  uint32_t                  mSkipEntries;
+  // Number of entries that should be written to disk. This is number of entries
+  // in hashtable that are initialized and are not marked as removed when writing
+  // begins.
+  uint32_t                  mProcessEntries;
+  char                     *mRWBuf;
+  uint32_t                  mRWBufSize;
+  uint32_t                  mRWBufPos;
+  nsRefPtr<CacheHash>       mRWHash;
+
+  // When reading index from disk, we open index, journal and tmpindex files at
+  // the same time. This value tell us how many times CacheIndex::OnFileOpened()
+  // will be called and identifies the handle.
+  uint32_t                  mReadOpenCount;
+  // Reading of index failed completely if true.
+  bool                      mReadFailed;
+  // Reading of journal succeeded if true.
+  bool                      mJournalReadSuccessfully;
+
+  // Handle used for writing and reading index file.
+  nsRefPtr<CacheFileHandle> mIndexHandle;
+  // Handle used for reading journal file.
+  nsRefPtr<CacheFileHandle> mJournalHandle;
+
+  // Directory enumerator used when building and updating index.
+  nsCOMPtr<nsIDirectoryEnumerator> mDirEnumerator;
+
+  // Main index hashtable.
+  nsTHashtable<CacheIndexEntry> mIndex;
+
+  // We cannot add, remove or change any entry in mIndex in states READING and
+  // WRITING. We track all changes in mPendingUpdates during these states.
+  nsTHashtable<CacheIndexEntry> mPendingUpdates;
+
+  // Contains information statistics for mIndex + mPendingUpdates.
+  CacheIndexStats               mIndexStats;
+
+  // When reading journal, we must first parse the whole file and apply the
+  // changes iff the journal was read successfully. mTmpJournal is used to store
+  // entries from the journal file. We throw away all these entries if parsing
+  // of the journal fails or the hash does not match.
+  nsTHashtable<CacheIndexEntry> mTmpJournal;
+
+  // Arrays that keep entry records ordered by eviction preference. When looking
+  // for an entry to evict, we first try to find an expired entry. If there is
+  // no expired entry, we take the entry with lowest valid frecency. Zero
+  // frecency is an initial value and such entries are stored at the end of the
+  // array. Uninitialized entries and entries marked as deleted are not present
+  // in these arrays.
+  nsTArray<CacheIndexRecord *>  mFrecencyArray;
+  nsTArray<CacheIndexRecord *>  mExpirationArray;
+};
+
+
+} // net
+} // mozilla
+
+#endif
--- a/netwerk/cache2/CacheStorageService.cpp
+++ b/netwerk/cache2/CacheStorageService.cpp
@@ -1319,16 +1319,17 @@ public:
   virtual ~CacheEntryDoomByKeyCallback();
 
 private:
   NS_IMETHOD OnFileOpened(CacheFileHandle *aHandle, nsresult aResult) { return NS_OK; }
   NS_IMETHOD OnDataWritten(CacheFileHandle *aHandle, const char *aBuf, nsresult aResult) { return NS_OK; }
   NS_IMETHOD OnDataRead(CacheFileHandle *aHandle, char *aBuf, nsresult aResult) { return NS_OK; }
   NS_IMETHOD OnFileDoomed(CacheFileHandle *aHandle, nsresult aResult);
   NS_IMETHOD OnEOFSet(CacheFileHandle *aHandle, nsresult aResult) { return NS_OK; }
+  NS_IMETHOD OnFileRenamed(CacheFileHandle *aHandle, nsresult aResult) { return NS_OK; }
 
   nsCOMPtr<nsICacheEntryDoomCallback> mCallback;
 };
 
 CacheEntryDoomByKeyCallback::~CacheEntryDoomByKeyCallback()
 {
   if (mCallback)
     ProxyReleaseMainThread(mCallback);
--- a/netwerk/cache2/moz.build
+++ b/netwerk/cache2/moz.build
@@ -34,16 +34,17 @@ SOURCES += [
     'AppCacheStorage.cpp',
     'CacheEntry.cpp',
     'CacheFile.cpp',
     'CacheFileChunk.cpp',
     'CacheFileInputStream.cpp',
     'CacheFileIOManager.cpp',
     'CacheFileMetadata.cpp',
     'CacheFileOutputStream.cpp',
+    'CacheIndex.cpp',
     'CacheLog.cpp',
     'CacheStorage.cpp',
     'CacheStorageService.cpp',
     'OldWrappers.cpp',
 ]
 
 LOCAL_INCLUDES += [
     '../base/src',
--- a/netwerk/cache2/nsICacheEntry.idl
+++ b/netwerk/cache2/nsICacheEntry.idl
@@ -193,12 +193,15 @@ interface nsICacheEntry : nsISupports
    *    consumer indicates whether write to the entry is allowed for it
    *    depends on implementation how the flag is handled
    * @returns
    *    true when write access is acquired for this entry
    *    false otherwise
    */
   boolean hasWriteAccess(in boolean aWriteAllowed);
 
+
+  const unsigned long NO_EXPIRATION_TIME = 0xFFFFFFFF;
+
   // *************** GET RID OF THESE ??? ***************
   void setDataSize(in unsigned long size);
   attribute nsCacheStoragePolicy storagePolicy;
 };