Bug 1415723 - back out bug 853881 and follow-up bug 1368786 for causing a performance regression. a=jorgk
authorJorg K <jorgk@jorgk.com>
Fri, 10 Nov 2017 21:37:18 +0100
changeset 29375 a53e3e2a9ba92ac4d8d4190d03222043004afa48
parent 29374 6f76f5fde0e74e0ced0a65356d746aab99aa2395
child 29376 778fc98a593fac351fedb4477fd2ce39629bc9cd
push id2070
push usermozilla@jorgk.com
push dateTue, 14 Nov 2017 11:58:12 +0000
treeherdercomm-beta@a53e3e2a9ba9 [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewersjorgk
bugs1415723, 853881, 1368786
Bug 1415723 - back out bug 853881 and follow-up bug 1368786 for causing a performance regression. a=jorgk Backed out changeset a0bd8f2b70be - bug 853881 Backed out changeset 5c3191edbbd4 - bug 853881 Backed out changeset 62bfaab2731f - bug 1368786
mailnews/db/msgdb/public/nsMsgDatabase.h
mailnews/db/msgdb/src/nsMsgDatabase.cpp
mailnews/db/msgdb/src/nsMsgHdr.cpp
--- a/mailnews/db/msgdb/public/nsMsgDatabase.h
+++ b/mailnews/db/msgdb/public/nsMsgDatabase.h
@@ -19,18 +19,16 @@
 #include "nsIMutableArray.h"
 #include "nsDBFolderInfo.h"
 #include "nsICollation.h"
 #include "nsIMsgSearchSession.h"
 #include "nsIMimeConverter.h"
 #include "nsCOMPtr.h"
 #include "nsCOMArray.h"
 #include "PLDHashTable.h"
-#include "nsDataHashtable.h"
-#include "nsInterfaceHashtable.h"
 #include "nsTArray.h"
 #include "nsTObserverArray.h"
 class ListContext;
 class nsMsgKeySet;
 class nsMsgThread;
 class nsMsgDatabase;
 class nsIMsgThread;
 class nsIDBFolderInfo;
@@ -121,44 +119,19 @@ protected:
 
   nsCOMPtr <nsIMsgSearchSession> m_searchSession;
 
 };
 
 namespace mozilla {
 namespace mailnews {
 class MsgDBReporter;
-
-class MsgKeyHashKey : public PLDHashEntryHdr {
-public:
-  typedef const nsMsgKey &KeyType;
-  typedef const nsMsgKey *KeyTypePointer;
-
-  MsgKeyHashKey(KeyTypePointer aKey) : mValue(*aKey) {}
-  MsgKeyHashKey(const MsgKeyHashKey &o) : mValue(o.mValue) {}
-  ~MsgKeyHashKey() {}
-
-  KeyType GetKey() const { return mValue; }
-  bool KeyEquals(KeyTypePointer aKey) const { return *aKey == mValue; }
-
-  static KeyTypePointer KeyToPointer(KeyType aKey) { return &aKey; }
-  static PLDHashNumber HashKey(KeyTypePointer aKey) { return *aKey; }
-  enum { ALLOW_MEMMOVE = true };
-
-private:
-  const nsMsgKey mValue;
-};
-
-static_assert(sizeof(nsMsgKey) == sizeof(uint32_t),
-   "Hashing algorithm for nsMsgKey only good for 32-bit numbers");
 }
 }
 
-typedef mozilla::mailnews::MsgKeyHashKey nsMsgKeyHashKey;
-
 class nsMsgDatabase : public nsIMsgDatabase
 {
 public:
   friend class nsMsgDBService;
   friend class nsMsgPropertyEnumerator; // accesses m_mdbEnv and m_mdbStore
 
   NS_DECL_ISUPPORTS
   NS_DECL_NSIDBCHANGEANNOUNCER
@@ -273,16 +246,17 @@ protected:
   nsresult        GetIntPref(const char *prefName, int32_t *result);
   virtual void    GetGlobalPrefs();
     // retrieval methods
   nsIMsgThread *  GetThreadForReference(nsCString &msgID, nsIMsgDBHdr **pMsgHdr);
   nsIMsgThread *  GetThreadForSubject(nsCString &subject);
   nsIMsgThread *  GetThreadForMessageId(nsCString &msgId);
   nsIMsgThread *  GetThreadForThreadId(nsMsgKey threadId);
   nsMsgHdr     *  GetMsgHdrForReference(nsCString &reference);
+  nsIMsgDBHdr  *  GetMsgHdrForSubject(nsCString &subject);
   // threading interfaces
   virtual nsresult CreateNewThread(nsMsgKey key, const char *subject, nsMsgThread **newThread);
   virtual bool    ThreadBySubjectWithoutRe();
   virtual bool    UseStrictThreading();
   virtual bool    UseCorrectThreading();
   virtual nsresult ThreadNewHdr(nsMsgHdr* hdr, bool &newThread);
   virtual nsresult AddNewThread(nsMsgHdr *msgHdr);
   virtual nsresult AddToThread(nsMsgHdr *newHdr, nsIMsgThread *thread, nsIMsgDBHdr *pMsgHdr, bool threadInThread);
@@ -372,74 +346,88 @@ protected:
   mdb_token     m_threadSubjectColumnToken;
   mdb_token     m_messageCharSetColumnToken;
   mdb_token     m_threadParentColumnToken;
   mdb_token     m_threadRootKeyColumnToken;
   mdb_token     m_threadNewestMsgDateColumnToken;
   mdb_token     m_offlineMsgOffsetColumnToken;
   mdb_token     m_offlineMessageSizeColumnToken;
 
-  // The following methods use m_cachedHeaders to keep strong references to
-  // recent header objects around.
-  void AddHdrToCache(nsIMsgDBHdr *hdr, nsMsgKey key);
-  void ClearHdrCache();
-  void RemoveHdrFromCache(nsIMsgDBHdr *hdr, nsMsgKey key);
-
-  // These methods maintain a cache of all headers for the same message key.
-  // Adding and removing headers should only be called by the nsMsgHdr
-  // constructor and destructor
-  bool GetHdrFromUseCache(nsMsgKey key, nsIMsgDBHdr* *result);
-  void AddHdrToUseCache(nsMsgHdr *hdr, nsMsgKey key);
-  void ClearUseHdrCache();
-  void RemoveHdrFromUseCache(nsMsgHdr *hdr, nsMsgKey key);
+  // header caching stuff - MRU headers, keeps them around in memory
+  nsresult      AddHdrToCache(nsIMsgDBHdr *hdr, nsMsgKey key);
+  nsresult      ClearHdrCache(bool reInit);
+  nsresult      RemoveHdrFromCache(nsIMsgDBHdr *hdr, nsMsgKey key);
+  // all headers currently instantiated, doesn't hold refs
+  // these get added when msg hdrs get constructed, and removed when they get destroyed.
+  nsresult      GetHdrFromUseCache(nsMsgKey key, nsIMsgDBHdr* *result);
+  nsresult      AddHdrToUseCache(nsIMsgDBHdr *hdr, nsMsgKey key);
+  nsresult      ClearUseHdrCache();
+  nsresult      RemoveHdrFromUseCache(nsIMsgDBHdr *hdr, nsMsgKey key);
 
   // not-reference holding array of threads we've handed out.
   // If a db goes away, it will clean up the outstanding threads.
   // We use an nsTArray because we don't expect to ever have very many
   // of these, rarely more than 5.
   nsTArray<nsMsgThread *> m_threads;
   // Clear outstanding thread objects
   void ClearThreads();
   nsMsgThread *FindExistingThread(nsMsgKey threadId);
 
   mdb_pos       FindInsertIndexInSortedTable(nsIMdbTable *table, mdb_id idToInsert);
 
   void          ClearCachedObjects(bool dbGoingAway);
   void          ClearEnumerators();
+  // all instantiated headers, but doesn't hold refs.
+  PLDHashTable  *m_headersInUse;
+  static PLDHashNumber HashKey(const void* aKey);
+  static bool MatchEntry(const PLDHashEntryHdr* aEntry, const void* aKey);
+  static void MoveEntry(PLDHashTable* aTable, const PLDHashEntryHdr* aFrom, PLDHashEntryHdr* aTo);
+  static void ClearEntry(PLDHashTable* aTable, PLDHashEntryHdr* aEntry);
+  static PLDHashTableOps gMsgDBHashTableOps;
+  struct MsgHdrHashElement : public PLDHashEntryHdr {
+    nsMsgKey       mKey;
+    nsIMsgDBHdr     *mHdr;
+  };
+  PLDHashTable  *m_cachedHeaders;
+  bool          m_bCacheHeaders;
   nsMsgKey  m_cachedThreadId;
   nsCOMPtr <nsIMsgThread> m_cachedThread;
   nsCOMPtr<nsIMdbFactory> mMdbFactory;
 
-  // This contains a lookup key of message IDs to thread IDs so we can quickly
-  // add messages to threads.
-  nsDataHashtable<nsCStringHashKey, nsMsgKey> m_msgReferences;
+  // Message reference hash table
+  static PLDHashTableOps gRefHashTableOps;
+  struct RefHashElement : public PLDHashEntryHdr {
+    const char     *mRef;       // Hash entry key, must come first
+    nsMsgKey        mThreadId;
+    uint32_t        mCount;
+  };
+  PLDHashTable *m_msgReferences;
   nsresult GetRefFromHash(nsCString &reference, nsMsgKey *threadId);
-  void AddRefToHash(nsCString &reference, nsMsgKey threadId);
-  void AddMsgRefsToHash(nsIMsgDBHdr *msgHdr);
-  void RemoveRefFromHash(nsCString &reference);
-  void RemoveMsgRefsFromHash(nsIMsgDBHdr *msgHdr);
+  nsresult AddRefToHash(nsCString &reference, nsMsgKey threadId);
+  nsresult AddMsgRefsToHash(nsIMsgDBHdr *msgHdr);
+  nsresult RemoveRefFromHash(nsCString &reference);
+  nsresult RemoveMsgRefsFromHash(nsIMsgDBHdr *msgHdr);
   nsresult InitRefHash();
 
   // not-reference holding array of enumerators we've handed out.
   // If a db goes away, it will clean up the outstanding enumerators.
   nsTArray<nsMsgDBEnumerator *> m_enumerators;
 
   // Memory reporter details
 public:
+  static size_t HeaderHashSizeOf(PLDHashEntryHdr *hdr,
+                                 mozilla::MallocSizeOf aMallocSizeOf,
+                                 void *arg);
   virtual size_t SizeOfExcludingThis(mozilla::MallocSizeOf aMallocSizeOf) const;
   virtual size_t SizeOfIncludingThis(mozilla::MallocSizeOf aMallocSizeOf) const
   {
     return aMallocSizeOf(this) + SizeOfExcludingThis(aMallocSizeOf);
   }
 private:
   uint32_t m_cacheSize;
-  nsInterfaceHashtable<nsMsgKeyHashKey, nsIMsgDBHdr> m_cachedHeaders;
-  // This table contains a non-refcounted reference to all headers that will be
-  // given out.
-  nsDataHashtable<nsMsgKeyHashKey, nsMsgHdr *> m_headersInUse;
   RefPtr<mozilla::mailnews::MsgDBReporter> mMemReporter;
 };
 
 class nsMsgRetentionSettings : public nsIMsgRetentionSettings
 {
 public:
   nsMsgRetentionSettings();
 
--- a/mailnews/db/msgdb/src/nsMsgDatabase.cpp
+++ b/mailnews/db/msgdb/src/nsMsgDatabase.cpp
@@ -37,17 +37,16 @@
 #include "nsIPrefService.h"
 #include "nsIPrefBranch.h"
 #include "nsIMsgPluggableStore.h"
 #include "nsAlgorithm.h"
 #include "nsArrayEnumerator.h"
 #include "nsIMemoryReporter.h"
 #include "mozilla/mailnews/MimeHeaderParser.h"
 #include "mozilla/mailnews/Services.h"
-#include "mozilla/Unused.h"
 #include <algorithm>
 
 using namespace mozilla::mailnews;
 using namespace mozilla;
 
 #if defined(DEBUG_sspitzer_) || defined(DEBUG_seth_)
 #define DEBUG_MSGKEYSET 1
 #endif
@@ -487,25 +486,42 @@ void nsMsgDatabase::GetGlobalPrefs()
   {
     GetBoolPref("mail.thread_without_re", &gThreadWithoutRe);
     GetBoolPref("mail.strict_threading", &gStrictThreading);
     GetBoolPref("mail.correct_threading", &gCorrectThreading);
     gGotGlobalPrefs = true;
   }
 }
 
-void nsMsgDatabase::AddHdrToCache(nsIMsgDBHdr *hdr, nsMsgKey key)
-{
-  if (key == nsMsgKey_None)
-    hdr->GetMessageKey(&key);
-  // TODO: Implement LRU replacement.
-  if (m_cachedHeaders.Count() > m_cacheSize)
-    ClearHdrCache();
-  Unused << m_cachedHeaders.Put(key, hdr, mozilla::fallible_t());
-}
+nsresult nsMsgDatabase::AddHdrToCache(nsIMsgDBHdr *hdr, nsMsgKey key) // do we want key? We could get it from hdr
+{
+  if (m_bCacheHeaders)
+  {
+    if (!m_cachedHeaders)
+      m_cachedHeaders = new PLDHashTable(&gMsgDBHashTableOps, sizeof(struct MsgHdrHashElement), m_cacheSize);
+    if (m_cachedHeaders)
+    {
+      if (key == nsMsgKey_None)
+        hdr->GetMessageKey(&key);
+      if (m_cachedHeaders->EntryCount() > m_cacheSize)
+        ClearHdrCache(true);
+      PLDHashEntryHdr *entry = m_cachedHeaders->Add((void *)(uintptr_t) key, mozilla::fallible);
+      if (!entry)
+        return NS_ERROR_OUT_OF_MEMORY; // XXX out of memory
+
+      MsgHdrHashElement* element = static_cast<MsgHdrHashElement*>(entry);
+      element->mHdr = hdr;
+      element->mKey = key;
+      NS_ADDREF(hdr);     // make the cache hold onto the header
+      return NS_OK;
+    }
+  }
+  return NS_ERROR_FAILURE;
+}
+
 
 NS_IMETHODIMP nsMsgDatabase::SetMsgHdrCacheSize(uint32_t aSize)
 {
   m_cacheSize = aSize;
   return NS_OK;
 }
 
 NS_IMETHODIMP nsMsgDatabase::GetMsgHdrCacheSize(uint32_t *aSize)
@@ -593,100 +609,235 @@ void nsMsgDatabase::ClearThreads()
 
   uint32_t numThreads = copyThreads.Length();
   for (uint32_t i = 0; i < numThreads; i++)
     copyThreads[i]->Clear();
 }
 
 void nsMsgDatabase::ClearCachedObjects(bool dbGoingAway)
 {
-  ClearHdrCache();
+  ClearHdrCache(false);
 #ifdef DEBUG_DavidBienvenu
-  if (m_headersInUse && m_headersInUse->entryCount > 0)
+  if (m_headersInUse && m_headersInUse->EntryCount() > 0)
   {
     NS_ASSERTION(false, "leaking headers");
-    printf("leaking %d headers in %s\n", m_headersInUse.Count(), (const char *) m_dbName);
+    printf("leaking %d headers in %s\n", m_headersInUse->EntryCount(), (const char *) m_dbName);
   }
 #endif
   m_cachedThread = nullptr;
   m_cachedThreadId = nsMsgKey_None;
   // We should only clear the use hdr cache when the db is going away, or we could
   // end up with multiple copies of the same logical msg hdr, which will lead to
   // ref-counting problems.
   if (dbGoingAway)
   {
     ClearUseHdrCache();
     ClearThreads();
   }
   m_thumb = nullptr;
 }
 
-void nsMsgDatabase::ClearHdrCache()
-{
-  m_cachedHeaders.Clear();
-}
-
-void nsMsgDatabase::RemoveHdrFromCache(nsIMsgDBHdr *hdr, nsMsgKey key)
-{
-  if (key == nsMsgKey_None)
-    hdr->GetMessageKey(&key);
-
-  m_cachedHeaders.Remove(key);
-}
-
-bool nsMsgDatabase::GetHdrFromUseCache(nsMsgKey key, nsIMsgDBHdr* *result)
-{
-  MOZ_ASSERT(result, "This parameter must be non-null!");
-
-  nsMsgHdr *hdr = m_headersInUse.Get(key);
-  NS_IF_ADDREF(*result = hdr);
-
-  return !!hdr;
-}
-
-void nsMsgDatabase::AddHdrToUseCache(nsMsgHdr *hdr, nsMsgKey key)
-{
-  if (key == nsMsgKey_None)
-    hdr->GetMessageKey(&key);
-  m_headersInUse.Put(key, hdr);
-}
-
-void nsMsgDatabase::ClearUseHdrCache()
-{
-  // Clear out m_mdbRow member variable - the db is going away, which means
-  // that this member variable might very well point to a mork db that is gone.
-  for (auto iter = m_headersInUse.ConstIter(); !iter.Done(); iter.Next()) {
-    NS_IF_RELEASE(iter.Data()->m_mdbRow);
+nsresult nsMsgDatabase::ClearHdrCache(bool reInit)
+{
+  if (m_cachedHeaders)
+  {
+    // save this away in case we renter this code.
+    PLDHashTable  *saveCachedHeaders = m_cachedHeaders;
+    m_cachedHeaders = nullptr;
+    for (auto iter = saveCachedHeaders->Iter(); !iter.Done(); iter.Next()) {
+      auto element = static_cast<MsgHdrHashElement*>(iter.Get());
+      if (element)
+        NS_IF_RELEASE(element->mHdr);
+    }
+
+    if (reInit)
+    {
+      saveCachedHeaders->ClearAndPrepareForLength(m_cacheSize);
+      m_cachedHeaders = saveCachedHeaders;
+    }
+    else
+    {
+      delete saveCachedHeaders;
+    }
+  }
+  return NS_OK;
+}
+
+nsresult nsMsgDatabase::RemoveHdrFromCache(nsIMsgDBHdr *hdr, nsMsgKey key)
+{
+  if (m_cachedHeaders)
+  {
+    if (key == nsMsgKey_None)
+      hdr->GetMessageKey(&key);
+
+    PLDHashEntryHdr *entry =
+      m_cachedHeaders->Search((const void *)(uintptr_t) key);
+    if (entry)
+    {
+      m_cachedHeaders->Remove((void *)(uintptr_t) key);
+      NS_RELEASE(hdr); // get rid of extra ref the cache was holding.
+    }
+
+  }
+  return NS_OK;
+}
+
+
+nsresult nsMsgDatabase::GetHdrFromUseCache(nsMsgKey key, nsIMsgDBHdr* *result)
+{
+  if (!result)
+    return NS_ERROR_NULL_POINTER;
+
+  nsresult rv = NS_ERROR_FAILURE;
+
+  *result = nullptr;
+
+  if (m_headersInUse)
+  {
+    PLDHashEntryHdr *entry =
+      m_headersInUse->Search((const void *)(uintptr_t) key);
+    if (entry)
+    {
+      MsgHdrHashElement* element = static_cast<MsgHdrHashElement*>(entry);
+      *result = element->mHdr;
+    }
+    if (*result)
+    {
+      NS_ADDREF(*result);
+      rv = NS_OK;
+    }
   }
-  m_headersInUse.Clear();
-}
-
-void nsMsgDatabase::RemoveHdrFromUseCache(nsMsgHdr *hdr, nsMsgKey key)
-{
-  if (key == nsMsgKey_None)
-    hdr->GetMessageKey(&key);
-
-  m_headersInUse.Remove(key);
-}
+  return rv;
+}
+
+PLDHashTableOps nsMsgDatabase::gMsgDBHashTableOps =
+{
+  HashKey,
+  MatchEntry,
+  MoveEntry,
+  ClearEntry,
+  nullptr
+};
+
+// HashKey is supposed to maximize entropy in the low order bits, and the key
+// as is, should do that.
+PLDHashNumber
+nsMsgDatabase::HashKey(const void* aKey)
+{
+  return PLDHashNumber(NS_PTR_TO_INT32(aKey));
+}
+
+bool
+nsMsgDatabase::MatchEntry(const PLDHashEntryHdr* aEntry, const void* aKey)
+{
+  const MsgHdrHashElement* hdr = static_cast<const MsgHdrHashElement*>(aEntry);
+  return aKey == (const void *)(uintptr_t) hdr->mKey; // ### or get the key from the hdr...
+}
+
+void
+nsMsgDatabase::MoveEntry(PLDHashTable* aTable, const PLDHashEntryHdr* aFrom, PLDHashEntryHdr* aTo)
+{
+  const MsgHdrHashElement* from = static_cast<const MsgHdrHashElement*>(aFrom);
+  MsgHdrHashElement* to = static_cast<MsgHdrHashElement*>(aTo);
+  // ### eh? Why is this needed? I don't think we have a copy operator?
+  *to = *from;
+}
+
+void
+nsMsgDatabase::ClearEntry(PLDHashTable* aTable, PLDHashEntryHdr* aEntry)
+{
+  MsgHdrHashElement* element = static_cast<MsgHdrHashElement*>(aEntry);
+  element->mHdr = nullptr; // eh? Need to release this or not?
+  element->mKey = nsMsgKey_None; // eh?
+}
+
+
+nsresult nsMsgDatabase::AddHdrToUseCache(nsIMsgDBHdr *hdr, nsMsgKey key)
+{
+  if (!m_headersInUse)
+  {
+    mdb_count numHdrs = MSG_HASH_SIZE;
+    if (m_mdbAllMsgHeadersTable)
+      m_mdbAllMsgHeadersTable->GetCount(GetEnv(), &numHdrs);
+    m_headersInUse = new PLDHashTable(&gMsgDBHashTableOps, sizeof(struct MsgHdrHashElement), std::max((mdb_count)MSG_HASH_SIZE, numHdrs));
+  }
+  if (m_headersInUse)
+  {
+    if (key == nsMsgKey_None)
+      hdr->GetMessageKey(&key);
+    PLDHashEntryHdr *entry = m_headersInUse->Add((void *)(uintptr_t) key, mozilla::fallible);
+    if (!entry)
+      return NS_ERROR_OUT_OF_MEMORY; // XXX out of memory
+
+    MsgHdrHashElement* element = static_cast<MsgHdrHashElement*>(entry);
+    element->mHdr = hdr;
+    element->mKey = key;
+    // the hash table won't add ref, we'll do it ourselves
+    // stand for the addref that CreateMsgHdr normally does.
+    NS_ADDREF(hdr);
+    return NS_OK;
+  }
+
+  return NS_ERROR_OUT_OF_MEMORY;
+}
+
+nsresult nsMsgDatabase::ClearUseHdrCache()
+{
+  if (m_headersInUse)
+  {
+    // clear mdb row pointers of any headers still in use, because the
+    // underlying db is going away.
+    for (auto iter = m_headersInUse->Iter(); !iter.Done(); iter.Next()) {
+      auto element = static_cast<const MsgHdrHashElement*>(iter.Get());
+      if (element && element->mHdr) {
+        nsMsgHdr* msgHdr = static_cast<nsMsgHdr*>(element->mHdr);  // closed system, so this is ok
+        // clear out m_mdbRow member variable - the db is going away, which means that this member
+        // variable might very well point to a mork db that is gone.
+        NS_IF_RELEASE(msgHdr->m_mdbRow);
+    //    NS_IF_RELEASE(msgHdr->m_mdb);
+      }
+    }
+    delete m_headersInUse;
+    m_headersInUse = nullptr;
+  }
+  return NS_OK;
+}
+
+nsresult nsMsgDatabase::RemoveHdrFromUseCache(nsIMsgDBHdr *hdr, nsMsgKey key)
+{
+  if (m_headersInUse)
+  {
+    if (key == nsMsgKey_None)
+      hdr->GetMessageKey(&key);
+
+    m_headersInUse->Remove((void *)(uintptr_t) key);
+  }
+  return NS_OK;
+}
+
 
 nsresult
 nsMsgDatabase::CreateMsgHdr(nsIMdbRow* hdrRow, nsMsgKey key, nsIMsgDBHdr* *result)
 {
   NS_ENSURE_ARG_POINTER(hdrRow);
   NS_ENSURE_ARG_POINTER(result);
 
-  if (GetHdrFromUseCache(key, result))
+  nsresult rv = GetHdrFromUseCache(key, result);
+  if (NS_SUCCEEDED(rv) && *result)
   {
     hdrRow->Release();
-    return NS_OK;
+    return rv;
   }
 
   nsMsgHdr *msgHdr = new nsMsgHdr(this, hdrRow);
+  if(!msgHdr)
+    return NS_ERROR_OUT_OF_MEMORY;
   msgHdr->SetMessageKey(key);
-  NS_ADDREF(*result = msgHdr);
+  // don't need to addref here; GetHdrFromUseCache addrefs.
+  *result = msgHdr;
 
   AddHdrToCache(msgHdr, key);
 
   return NS_OK;
 }
 
 NS_IMETHODIMP nsMsgDatabase::AddListener(nsIDBChangeListener *aListener)
 {
@@ -815,17 +966,18 @@ void nsMsgDBService::AddToCache(nsMsgDat
 void nsMsgDBService::DumpCache()
 {
   nsMsgDatabase* db = nullptr;
   MOZ_LOG(DBLog, LogLevel::Info, ("%zu open DBs\n", m_dbCache.Length()));
   for (uint32_t i = 0; i < m_dbCache.Length(); i++)
   {
     db = m_dbCache.ElementAt(i);
     MOZ_LOG(DBLog, LogLevel::Info, ("%s - %" PRIu32 " hdrs in use\n",
-      db->m_dbName.get(), db->m_headersInUse.Count()));
+      db->m_dbName.get(),
+      db->m_headersInUse ? db->m_headersInUse->EntryCount() : 0));
   }
 }
 
 // Memory Reporting implementations
 
 size_t nsMsgDatabase::SizeOfExcludingThis(mozilla::MallocSizeOf aMallocSizeOf) const
 {
   size_t totalSize = 0;
@@ -839,22 +991,30 @@ size_t nsMsgDatabase::SizeOfExcludingThi
       totalSize += morkHeap->GetUsedSize();
   }
   totalSize += m_newSet.ShallowSizeOfExcludingThis(aMallocSizeOf);
   totalSize += m_ChangeListeners.ShallowSizeOfExcludingThis(aMallocSizeOf);
   totalSize += m_threads.ShallowSizeOfExcludingThis(aMallocSizeOf);
   // We have two tables of header objects, but every header in m_cachedHeaders
   // should be in m_headersInUse.
   // double-counting...
-  totalSize += m_headersInUse.ShallowSizeOfExcludingThis(aMallocSizeOf);
-  totalSize += m_msgReferences.ShallowSizeOfExcludingThis(aMallocSizeOf);
-  for (auto iter = m_headersInUse.ConstIter(); !iter.Done(); iter.Next()) {
-    totalSize += iter.Data()->SizeOfIncludingThis(aMallocSizeOf);
+  size_t headerSize = 0;
+  if (m_headersInUse)
+  {
+    headerSize = m_headersInUse->ShallowSizeOfIncludingThis(aMallocSizeOf);
+    for (auto iter = m_headersInUse->Iter(); !iter.Done(); iter.Next()) {
+      auto entry = static_cast<MsgHdrHashElement*>(iter.Get());
+      // Sigh, this is dangerous, but so long as this is a closed system, this
+      // is safe.
+      headerSize += static_cast<nsMsgHdr*>(entry->mHdr)->SizeOfIncludingThis(aMallocSizeOf);
+    }
   }
-
+  totalSize += headerSize;
+  if (m_msgReferences)
+    totalSize += m_msgReferences->ShallowSizeOfIncludingThis(aMallocSizeOf);
   return totalSize;
 }
 
 namespace mozilla {
 namespace mailnews {
 
 MOZ_DEFINE_MALLOC_SIZE_OF(GetMallocSize)
 
@@ -948,31 +1108,41 @@ nsMsgDatabase::nsMsgDatabase()
         m_messageThreadIdColumnToken(0),
         m_threadSubjectColumnToken(0),
         m_messageCharSetColumnToken(0),
         m_threadParentColumnToken(0),
         m_threadRootKeyColumnToken(0),
         m_threadNewestMsgDateColumnToken(0),
         m_offlineMsgOffsetColumnToken(0),
         m_offlineMessageSizeColumnToken(0),
+        m_headersInUse(nullptr),
+        m_cachedHeaders(nullptr),
+        m_bCacheHeaders(true),
         m_cachedThreadId(nsMsgKey_None),
-        m_cacheSize(kMaxHdrsInCache),
-        m_cachedHeaders(MSG_HASH_SIZE),
-        m_headersInUse(MSG_HASH_SIZE)
+        m_msgReferences(nullptr),
+        m_cacheSize(kMaxHdrsInCache)
 {
   mMemReporter = new mozilla::mailnews::MsgDBReporter(this);
   mozilla::RegisterWeakMemoryReporter(mMemReporter);
 }
 
 nsMsgDatabase::~nsMsgDatabase()
 {
   mozilla::UnregisterWeakMemoryReporter(mMemReporter);
   //  Close(FALSE);  // better have already been closed.
   ClearCachedObjects(true);
   ClearEnumerators();
+  delete m_cachedHeaders;
+  delete m_headersInUse;
+
+  if (m_msgReferences)
+  {
+    delete m_msgReferences;
+    m_msgReferences = nullptr;
+  }
 
   MOZ_LOG(DBLog, LogLevel::Info, ("closing database    %s\n", m_dbName.get()));
 
   nsCOMPtr<nsIMsgDBService> serv(do_GetService(NS_MSGDB_SERVICE_CONTRACTID));
   if (serv)
     static_cast<nsMsgDBService*>(serv.get())->RemoveFromCache(this);
 
   // if the db folder info refers to the mdb db, we must clear it because
@@ -1709,18 +1879,19 @@ NS_IMETHODIMP nsMsgDatabase::GetMsgHdrFo
 #ifdef DEBUG_bienvenu1
   NS_ASSERTION(m_folder, "folder should be set");
 #endif
 
   if (!pmsgHdr || !m_mdbAllMsgHeadersTable || !m_mdbStore)
     return NS_ERROR_NULL_POINTER;
 
   *pmsgHdr = NULL;
-  if (GetHdrFromUseCache(key, pmsgHdr))
-    return NS_OK;
+  err = GetHdrFromUseCache(key, pmsgHdr);
+  if (NS_SUCCEEDED(err) && *pmsgHdr)
+    return err;
 
   rowObjectId.mOid_Id = key;
   rowObjectId.mOid_Scope = m_hdrRowScopeToken;
   err = m_mdbAllMsgHeadersTable->HasOid(GetEnv(), &rowObjectId, &hasOid);
   if (NS_SUCCEEDED(err) /* && hasOid */)
   {
     nsIMdbRow *hdrRow;
     err = m_mdbStore->GetRow(GetEnv(), &rowObjectId, &hdrRow);
@@ -2734,19 +2905,24 @@ nsresult nsMsgDBEnumerator::PrefetchNext
     //Get key from row
     mdbOid outOid;
     nsMsgKey key = nsMsgKey_None;
     rv = hdrRow->GetOid(mDB->GetEnv(), &outOid);
     if (NS_WARN_IF(NS_FAILED(rv)))
       return rv;
     key = outOid.mOid_Id;
 
-    rv = mDB->CreateMsgHdr(hdrRow, key, getter_AddRefs(mResultHdr));
-    if (NS_WARN_IF(NS_FAILED(rv)))
-      return rv;
+    rv = mDB->GetHdrFromUseCache(key, getter_AddRefs(mResultHdr));
+    if (NS_SUCCEEDED(rv) && mResultHdr)
+      hdrRow->Release();
+    else {
+      rv = mDB->CreateMsgHdr(hdrRow, key, getter_AddRefs(mResultHdr));
+      if (NS_WARN_IF(NS_FAILED(rv)))
+        return rv;
+    }
 
     if (mResultHdr)
       mResultHdr->GetFlags(&flags);
     else
       flags = 0;
   }
   while (mFilter && NS_FAILED(mFilter(mResultHdr, mClosure)) && !(flags & nsMsgMessageFlags::Expunged));
 
@@ -3334,17 +3510,17 @@ NS_IMETHODIMP nsMsgDatabase::AddNewHdrTo
     {
       nsMsgKey threadParent;
 
       newHdr->GetThreadParent(&threadParent);
       NotifyHdrAddedAll(newHdr, threadParent, flags, NULL);
     }
 
     if (UseCorrectThreading())
-      AddMsgRefsToHash(newHdr);
+      err = AddMsgRefsToHash(newHdr);
   }
   NS_ASSERTION(NS_SUCCEEDED(err), "error creating thread");
   return err;
 }
 
 NS_IMETHODIMP nsMsgDatabase::CopyHdrFromExistingHdr(nsMsgKey key, nsIMsgDBHdr *existingHdr, bool addHdrToDB, nsIMsgDBHdr **newHdr)
 {
   nsresult  err = NS_OK;
@@ -3925,98 +4101,179 @@ bool nsMsgDatabase::UseStrictThreading()
 
 // Should we make sure messages are always threaded correctly (see bug 181446)
 bool nsMsgDatabase::UseCorrectThreading()
 {
   GetGlobalPrefs();
   return gCorrectThreading;
 }
 
+// adapted from removed PL_DHashFreeStringKey
+static void
+msg_DHashFreeStringKey(PLDHashTable* aTable, PLDHashEntryHdr* aEntry)
+{
+  const PLDHashEntryStub* stub = (const PLDHashEntryStub*)aEntry;
+  free((void*)stub->key);
+  PLDHashTable::ClearEntryStub(aTable, aEntry);
+}
+
+PLDHashTableOps nsMsgDatabase::gRefHashTableOps =
+{
+  PLDHashTable::HashStringKey,
+  PLDHashTable::MatchStringKey,
+  PLDHashTable::MoveEntryStub,
+  msg_DHashFreeStringKey,
+  nullptr
+};
+
 nsresult nsMsgDatabase::GetRefFromHash(nsCString &reference, nsMsgKey *threadId)
 {
-  nsresult rv = InitRefHash();
-  NS_ENSURE_SUCCESS(rv, rv);
+  // Initialize the reference hash
+  if (!m_msgReferences)
+  {
+    nsresult rv = InitRefHash();
+    if (NS_FAILED(rv))
+      return rv;
+  }
 
   // Find reference from the hash
-  return m_msgReferences.Get(reference, threadId) ? NS_OK : NS_ERROR_FAILURE;
-}
-
-void nsMsgDatabase::AddRefToHash(nsCString &reference, nsMsgKey threadId)
-{
-  m_msgReferences.Put(reference, threadId);
-}
-
-void nsMsgDatabase::AddMsgRefsToHash(nsIMsgDBHdr *msgHdr)
+  PLDHashEntryHdr *entry =
+    m_msgReferences->Search((const void *) reference.get());
+  if (entry)
+  {
+    RefHashElement *element = static_cast<RefHashElement *>(entry);
+    *threadId = element->mThreadId;
+    return NS_OK;
+  }
+
+  return NS_ERROR_FAILURE;
+}
+
+nsresult nsMsgDatabase::AddRefToHash(nsCString &reference, nsMsgKey threadId)
+{
+  if (m_msgReferences)
+  {
+    PLDHashEntryHdr *entry = m_msgReferences->Add((void *) reference.get(), mozilla::fallible);
+    if (!entry)
+      return NS_ERROR_OUT_OF_MEMORY; // XXX out of memory
+
+    RefHashElement *element = static_cast<RefHashElement *>(entry);
+    if (!element->mRef)
+    {
+      element->mRef = ToNewCString(reference);  // Will be freed in msg_DHashFreeStringKey()
+      element->mThreadId = threadId;
+      element->mCount = 1;
+    }
+    else
+      element->mCount++;
+  }
+
+  return NS_OK;
+}
+
+nsresult nsMsgDatabase::AddMsgRefsToHash(nsIMsgDBHdr *msgHdr)
 {
   uint16_t numReferences = 0;
   nsMsgKey threadId;
+  nsresult rv = NS_OK;
 
   msgHdr->GetThreadId(&threadId);
   msgHdr->GetNumReferences(&numReferences);
 
   for (int32_t i = 0; i < numReferences; i++)
   {
     nsAutoCString reference;
 
     msgHdr->GetStringReference(i, reference);
     if (reference.IsEmpty())
       break;
 
-    AddRefToHash(reference, threadId);
+    rv = AddRefToHash(reference, threadId);
+    if (NS_FAILED(rv))
+      break;
   }
-}
-
-void nsMsgDatabase::RemoveRefFromHash(nsCString &reference)
-{
-  m_msgReferences.Remove(reference);
+
+  return rv;
+}
+
+nsresult nsMsgDatabase::RemoveRefFromHash(nsCString &reference)
+{
+  if (m_msgReferences)
+  {
+    PLDHashEntryHdr *entry =
+     m_msgReferences->Search((const void *) reference.get());
+    if (entry)
+    {
+      RefHashElement *element = static_cast<RefHashElement *>(entry);
+      if (--element->mCount == 0)
+        m_msgReferences->Remove((void *) reference.get());
+    }
+  }
+  return NS_OK;
 }
 
 // Filter only messages with one or more references
-void nsMsgDatabase::RemoveMsgRefsFromHash(nsIMsgDBHdr *msgHdr)
+nsresult nsMsgDatabase::RemoveMsgRefsFromHash(nsIMsgDBHdr *msgHdr)
 {
   uint16_t numReferences = 0;
+  nsresult rv = NS_OK;
 
   msgHdr->GetNumReferences(&numReferences);
 
   for (int32_t i = 0; i < numReferences; i++)
   {
     nsAutoCString reference;
 
     msgHdr->GetStringReference(i, reference);
     if (reference.IsEmpty())
       break;
 
-    RemoveRefFromHash(reference);
+    rv = RemoveRefFromHash(reference);
+    if (NS_FAILED(rv))
+      break;
   }
+
+  return rv;
 }
 
 static nsresult nsReferencesOnlyFilter(nsIMsgDBHdr *msg, void *closure)
 {
   uint16_t numReferences = 0;
   msg->GetNumReferences(&numReferences);
   return (numReferences) ? NS_OK : NS_ERROR_FAILURE;
 }
 
 nsresult nsMsgDatabase::InitRefHash()
 {
+  // Delete an existing table just in case
+  if (m_msgReferences)
+    delete m_msgReferences;
+
+  // Create new table
+  m_msgReferences = new PLDHashTable(&gRefHashTableOps, sizeof(struct RefHashElement), MSG_HASH_SIZE);
+  if (!m_msgReferences)
+    return NS_ERROR_OUT_OF_MEMORY;
+
   // Create enumerator to go through all messages with references
-  nsCOMPtr<nsISimpleEnumerator> enumerator;
+  nsCOMPtr <nsISimpleEnumerator> enumerator;
   enumerator = new nsMsgDBEnumerator(this, m_mdbAllMsgHeadersTable, nsReferencesOnlyFilter, nullptr);
+  if (enumerator == nullptr)
+    return NS_ERROR_OUT_OF_MEMORY;
 
   // Populate table with references of existing messages
   bool hasMore;
   nsresult rv = NS_OK;
   while (NS_SUCCEEDED(rv = enumerator->HasMoreElements(&hasMore)) && hasMore)
   {
     nsCOMPtr <nsISupports> supports;
     rv = enumerator->GetNext(getter_AddRefs(supports));
     NS_ASSERTION(NS_SUCCEEDED(rv), "nsMsgDBEnumerator broken");
     nsCOMPtr <nsIMsgDBHdr> msgHdr = do_QueryInterface(supports);
     if (msgHdr && NS_SUCCEEDED(rv))
-      AddMsgRefsToHash(msgHdr);
+      rv = AddMsgRefsToHash(msgHdr);
     if (NS_FAILED(rv))
       break;
   }
 
   return rv;
 }
 
 nsresult nsMsgDatabase::CreateNewThread(nsMsgKey threadId, const char *subject, nsMsgThread **pnewThread)
@@ -4346,19 +4603,24 @@ NS_IMETHODIMP nsMsgDatabase::GetMsgHdrFo
     //Get key from row
     mdbOid outOid;
     nsMsgKey key = nsMsgKey_None;
     rv = hdrRow->GetOid(GetEnv(), &outOid);
     if (NS_WARN_IF(NS_FAILED(rv)))
       return rv;
     key = outOid.mOid_Id;
 
-    rv = CreateMsgHdr(hdrRow, key, &msgHdr);
-    if (NS_WARN_IF(NS_FAILED(rv)))
-      return rv;
+    rv = GetHdrFromUseCache(key, &msgHdr);
+    if (NS_SUCCEEDED(rv) && msgHdr)
+      hdrRow->Release();
+    else {
+      rv = CreateMsgHdr(hdrRow, key, &msgHdr);
+      if (NS_WARN_IF(NS_FAILED(rv)))
+        return rv;
+    }
   }
   *aHdr = msgHdr; // already addreffed above.
   return NS_OK; // it's not an error not to find a msg hdr.
 }
 
 NS_IMETHODIMP nsMsgDatabase::GetMsgHdrForGMMsgID(const char *aGMMsgId, nsIMsgDBHdr **aHdr)
 {
   NS_ENSURE_ARG_POINTER(aGMMsgId);
@@ -4383,24 +4645,67 @@ NS_IMETHODIMP nsMsgDatabase::GetMsgHdrFo
     property_token, &gMailMessageIdYarn, &outRowId, &hdrRow);
   if (NS_SUCCEEDED(result) && hdrRow)
   {
     // Get key from row
     mdbOid outOid;
     rv = hdrRow->GetOid(GetEnv(), &outOid);
     NS_ENSURE_SUCCESS(rv, rv);
     nsMsgKey key = outOid.mOid_Id;
-    rv = CreateMsgHdr(hdrRow, key, &msgHdr);
-    if (NS_WARN_IF(NS_FAILED(rv)))
-      return rv;
+    rv = GetHdrFromUseCache(key, &msgHdr);
+    if ((NS_SUCCEEDED(rv) && msgHdr))
+      hdrRow->Release();
+    else {
+      rv = CreateMsgHdr(hdrRow, key, &msgHdr);
+      if (NS_WARN_IF(NS_FAILED(rv)))
+        return rv;
+    }
   }
   *aHdr = msgHdr;
   return NS_OK; // it's not an error not to find a msg hdr.
 }
 
+nsIMsgDBHdr *nsMsgDatabase::GetMsgHdrForSubject(nsCString &subject)
+{
+  nsIMsgDBHdr *msgHdr = nullptr;
+  nsresult rv = NS_OK;
+  mdbYarn subjectYarn;
+
+  subjectYarn.mYarn_Buf = (void*)subject.get();
+  subjectYarn.mYarn_Fill = PL_strlen(subject.get());
+  subjectYarn.mYarn_Form = 0;
+  subjectYarn.mYarn_Size = subjectYarn.mYarn_Fill;
+
+  nsIMdbRow *hdrRow;
+  mdbOid outRowId;
+  nsresult result = GetStore()->FindRow(GetEnv(), m_hdrRowScopeToken,
+    m_subjectColumnToken, &subjectYarn,  &outRowId,
+    &hdrRow);
+  if (NS_SUCCEEDED(result) && hdrRow)
+  {
+    //Get key from row
+    mdbOid outOid;
+    nsMsgKey key = nsMsgKey_None;
+    rv = hdrRow->GetOid(GetEnv(), &outOid);
+    if (NS_WARN_IF(NS_FAILED(rv)))
+      return nullptr;
+    key = outOid.mOid_Id;
+
+    rv = GetHdrFromUseCache(key, &msgHdr);
+    if (NS_SUCCEEDED(rv) && msgHdr)
+      hdrRow->Release();
+    else {
+      rv = CreateMsgHdr(hdrRow, key, &msgHdr);
+      if (NS_WARN_IF(NS_FAILED(rv)))
+        return nullptr;
+    }
+  }
+  return msgHdr;
+}
+
 NS_IMETHODIMP nsMsgDatabase::GetThreadContainingMsgHdr(nsIMsgDBHdr *msgHdr, nsIMsgThread **result)
 {
   NS_ENSURE_ARG_POINTER(msgHdr);
   NS_ENSURE_ARG_POINTER(result);
 
   *result = nullptr;
   nsMsgKey threadId = nsMsgKey_None;
   (void)msgHdr->GetThreadId(&threadId);
@@ -5317,17 +5622,17 @@ NS_IMETHODIMP nsMsgDatabase::GetDefaultS
   return NS_OK;
 }
 
 NS_IMETHODIMP nsMsgDatabase::ResetHdrCacheSize(uint32_t aSize)
 {
   if (m_cacheSize > aSize)
   {
     m_cacheSize = aSize;
-    ClearHdrCache();
+    ClearHdrCache(false);
   }
   return NS_OK;
 }
 
 /**
   void getNewList(out unsigned long count, [array, size_is(count)] out long newKeys);
  */
 NS_IMETHODIMP
--- a/mailnews/db/msgdb/src/nsMsgHdr.cpp
+++ b/mailnews/db/msgdb/src/nsMsgHdr.cpp
@@ -29,31 +29,31 @@ nsMsgHdr::nsMsgHdr(nsMsgDatabase *db, ns
   m_mdbRow = dbRow;
   if(m_mdb)
   {
     NS_ADDREF(m_mdb);  // Released in DTOR.
     mdbOid outOid;
     if (dbRow && NS_SUCCEEDED(dbRow->GetOid(m_mdb->GetEnv(), &outOid)))
     {
       m_messageKey = outOid.mOid_Id;
-      m_mdb->AddHdrToUseCache(this, m_messageKey);
+      m_mdb->AddHdrToUseCache((nsIMsgDBHdr *) this, m_messageKey);
     }
   }
 }
 
 
 void nsMsgHdr::Init()
 {
   m_initedValues = 0;
   m_statusOffset = 0xffffffff;
   m_messageKey = nsMsgKey_None;
   m_messageSize = 0;
   m_date = 0;
   m_flags = 0;
-  m_mdbRow = nullptr;
+  m_mdbRow = NULL;
   m_threadId = nsMsgKey_None;
   m_threadParent = nsMsgKey_None;
 }
 
 nsresult nsMsgHdr::InitCachedValues()
 {
   nsresult err = NS_OK;
 
@@ -98,25 +98,30 @@ nsresult nsMsgHdr::InitFlags()
   }
 
   return err;
 
 }
 
 nsMsgHdr::~nsMsgHdr()
 {
-  NS_IF_RELEASE(m_mdbRow);
-  if (m_mdb)
-    m_mdb->RemoveHdrFromUseCache(this, m_messageKey);
+  if (m_mdbRow)
+  {
+    if (m_mdb)
+    {
+      NS_RELEASE(m_mdbRow);
+      m_mdb->RemoveHdrFromUseCache((nsIMsgDBHdr *) this, m_messageKey);
+    }
+  }
   NS_IF_RELEASE(m_mdb);
 }
 
 NS_IMETHODIMP nsMsgHdr::GetMessageKey(nsMsgKey *result)
 {
-  if (m_messageKey == nsMsgKey_None && m_mdbRow != nullptr)
+  if (m_messageKey == nsMsgKey_None && m_mdbRow != NULL)
   {
     mdbOid outOid;
     if (NS_SUCCEEDED(m_mdbRow->GetOid(m_mdb->GetEnv(), &outOid)))
       m_messageKey = outOid.mOid_Id;
 
   }
   *result = m_messageKey;
   return NS_OK;