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 172059 f514ab5c4b5bdb365af0fa83f65e5943dab1b958
parent 172058 615c92a6708909eecd7a9cdcf81900f2437baf66
child 172060 d8543551f12eb0f98b348a1b2ea5a21aa12b8bfe
push id26349
push userkwierso@gmail.com
push dateThu, 06 Mar 2014 02:08:58 +0000
treeherdermozilla-central@c7d401d189e0 [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewershonzab
bugs923016
milestone30.0a1
first release with
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
last release without
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
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;
 };