Bug 1460674 - part 1 - change PLDHashTable internals to work on slots; r=njn
authorNathan Froyd <froydnj@mozilla.com>
Mon, 26 Nov 2018 16:24:50 -0500
changeset 507277 90e48634e1c329829854028465d311e2156196e3
parent 507276 927af324b93d51639dc24c09e6bb0eb9ace40613
child 507278 0c938490f21c626d84b00903fb6fcb4d94386ce5
push id1905
push userffxbld-merge
push dateMon, 21 Jan 2019 12:33:13 +0000
treeherdermozilla-release@c2fca1944d8c [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewersnjn
bugs1460674
milestone65.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 1460674 - part 1 - change PLDHashTable internals to work on slots; r=njn PLDHashTable requires that all items stored therein inherit from PLDHashEntryHdr: struct PLDHashEntryHdr { // PLDHashNumber is a uint32_t. PLDHashNumber mKeyHash; // Cached hash key for object. }; class MyType : public PLDHashEntryHdr { // Data members, etc. }; PLDHashEntryHdr::mKeyHash is used to cache the computed hash value of the entry, so we aren't rehashing entries on every lookup/add/etc. Because of structure layout requirements on 64-bit platforms, the data members of MyType will typically start at offset 8: MyType, offset 0: mKeyHash MyType, offset 4: padding required by alignment MyType, offset 8: first data member of MyType MyType, offset N: ... The padding at offset 4 is dead, unused space. We'd like to change this state of affairs by having PLDHashTable manage the cached hash key itself, which would eliminate the dead space in the object and would enable packing the table storage more tightly. But PLDHashTable pervasively assumes that its internal storage is an array of PLDHashEntryHdrs (with an associated object size to account for subclassing). As a first step to laying out the hash table storage differently, we have to make the internals of PLDHashTable not access PLDHashEntryHdr items directly, but layer an abstraction on top. We call this abstraction "slots": a slot represents storage for the cached hash key and the associated entry, and can produce a PLDHashEntryHdr* on demand.
xpcom/ds/PLDHashTable.cpp
xpcom/ds/PLDHashTable.h
--- a/xpcom/ds/PLDHashTable.cpp
+++ b/xpcom/ds/PLDHashTable.cpp
@@ -11,16 +11,17 @@
 #include "PLDHashTable.h"
 #include "mozilla/HashFunctions.h"
 #include "mozilla/MathAlgorithms.h"
 #include "mozilla/OperatorNewExtensions.h"
 #include "nsAlgorithm.h"
 #include "nsPointerHashKeys.h"
 #include "mozilla/Likely.h"
 #include "mozilla/MemoryReporting.h"
+#include "mozilla/Maybe.h"
 #include "mozilla/ChaosMode.h"
 
 using namespace mozilla;
 
 #ifdef DEBUG
 
 class AutoReadOp
 {
@@ -295,51 +296,58 @@ PLDHashTable::Hash2(PLDHashNumber aHash0
 // that a removed-entry sentinel need be stored only if the removed entry had
 // a colliding entry added after it. Therefore we can use 1 as the collision
 // flag in addition to the removed-entry sentinel value. Multiplicative hash
 // uses the high order bits of mKeyHash, so this least-significant reservation
 // should not hurt the hash function's effectiveness much.
 
 // Match an entry's mKeyHash against an unstored one computed from a key.
 /* static */ bool
+PLDHashTable::MatchSlotKeyhash(Slot& aSlot, const PLDHashNumber aKeyHash)
+{
+  return (aSlot.KeyHash() & ~kCollisionFlag) == aKeyHash;
+}
+
+/* static */ bool
 PLDHashTable::MatchEntryKeyhash(const PLDHashEntryHdr* aEntry,
                                 const PLDHashNumber aKeyHash)
 {
   return (aEntry->mKeyHash & ~kCollisionFlag) == aKeyHash;
 }
 
 // Compute the address of the indexed entry in table.
+auto
+PLDHashTable::SlotForIndex(uint32_t aIndex) const -> Slot
+{
+  return mEntryStore.SlotForIndex(aIndex, mEntrySize);
+}
+
 PLDHashEntryHdr*
 PLDHashTable::AddressEntry(uint32_t aIndex) const
 {
-  return reinterpret_cast<PLDHashEntryHdr*>(
-      mEntryStore.Get() + aIndex * mEntrySize);
+  return SlotForIndex(aIndex).ToEntry();
 }
 
 PLDHashTable::~PLDHashTable()
 {
 #ifdef DEBUG
   AutoDestructorOp op(mChecker);
 #endif
 
   if (!mEntryStore.Get()) {
     recordreplay::DestroyPLDHashTableCallbacks(mOps);
     return;
   }
 
   // Clear any remaining live entries.
-  char* entryAddr = mEntryStore.Get();
-  char* entryLimit = entryAddr + Capacity() * mEntrySize;
-  while (entryAddr < entryLimit) {
-    PLDHashEntryHdr* entry = (PLDHashEntryHdr*)entryAddr;
-    if (EntryIsLive(entry)) {
-      mOps->clearEntry(this, entry);
+  mEntryStore.ForEachSlot(Capacity(), mEntrySize, [&](const Slot& aSlot) {
+    if (aSlot.IsLive()) {
+      mOps->clearEntry(this, aSlot.ToEntry());
     }
-    entryAddr += mEntrySize;
-  }
+  });
 
   recordreplay::DestroyPLDHashTableCallbacks(mOps);
 
   // Entry storage is freed last, by ~EntryStore().
 }
 
 void
 PLDHashTable::ClearAndPrepareForLength(uint32_t aLength)
@@ -359,116 +367,123 @@ PLDHashTable::Clear()
 }
 
 // If |Reason| is |ForAdd|, the return value is always non-null and it may be
 // a previously-removed entry. If |Reason| is |ForSearchOrRemove|, the return
 // value is null on a miss, and will never be a previously-removed entry on a
 // hit. This distinction is a bit grotty but this function is hot enough that
 // these differences are worthwhile. (It's also hot enough that
 // MOZ_ALWAYS_INLINE makes a significant difference.)
-template <PLDHashTable::SearchReason Reason>
-MOZ_ALWAYS_INLINE PLDHashEntryHdr*
-PLDHashTable::SearchTable(const void* aKey, PLDHashNumber aKeyHash) const
+template <PLDHashTable::SearchReason Reason, typename Success, typename Failure>
+MOZ_ALWAYS_INLINE
+auto
+PLDHashTable::SearchTable(const void* aKey, PLDHashNumber aKeyHash,
+                          Success&& aSuccess, Failure&& aFailure) const
 {
   MOZ_ASSERT(mEntryStore.Get());
   NS_ASSERTION(!(aKeyHash & kCollisionFlag),
                "!(aKeyHash & kCollisionFlag)");
 
   // Compute the primary hash address.
   PLDHashNumber hash1 = Hash1(aKeyHash);
-  PLDHashEntryHdr* entry = AddressEntry(hash1);
+  Slot slot = SlotForIndex(hash1);
 
   // Miss: return space for a new entry.
-  if (EntryIsFree(entry)) {
-    return (Reason == ForAdd) ? entry : nullptr;
+  if (slot.IsFree()) {
+    return (Reason == ForAdd) ? aSuccess(slot) : aFailure();
   }
 
   // Hit: return entry.
   PLDHashMatchEntry matchEntry = mOps->matchEntry;
-  if (MatchEntryKeyhash(entry, aKeyHash) &&
-      matchEntry(entry, aKey)) {
-    return entry;
+  if (MatchSlotKeyhash(slot, aKeyHash)) {
+    PLDHashEntryHdr* e = slot.ToEntry();
+    if (matchEntry(e, aKey)) {
+      return aSuccess(slot);
+    }
   }
 
   // Collision: double hash.
   PLDHashNumber hash2;
   uint32_t sizeMask;
   Hash2(aKeyHash, hash2, sizeMask);
 
-  // Save the first removed entry pointer so Add() can recycle it. (Only used
+  // Save the first removed entry slot so Add() can recycle it. (Only used
   // if Reason==ForAdd.)
-  PLDHashEntryHdr* firstRemoved = nullptr;
+  Maybe<Slot> firstRemoved;
 
   for (;;) {
     if (Reason == ForAdd && !firstRemoved) {
-      if (MOZ_UNLIKELY(EntryIsRemoved(entry))) {
-        firstRemoved = entry;
+      if (MOZ_UNLIKELY(slot.IsRemoved())) {
+        firstRemoved.emplace(slot);
       } else {
-        entry->mKeyHash |= kCollisionFlag;
+        slot.MarkColliding();
       }
     }
 
     hash1 -= hash2;
     hash1 &= sizeMask;
 
-    entry = AddressEntry(hash1);
-    if (EntryIsFree(entry)) {
-      return (Reason == ForAdd) ? (firstRemoved ? firstRemoved : entry)
-                                : nullptr;
+    slot = SlotForIndex(hash1);
+    if (slot.IsFree()) {
+      if (Reason != ForAdd) {
+        return aFailure();
+      }
+      return aSuccess(firstRemoved.refOr(slot));
     }
 
-    if (MatchEntryKeyhash(entry, aKeyHash) &&
-        matchEntry(entry, aKey)) {
-      return entry;
+    if (MatchSlotKeyhash(slot, aKeyHash)) {
+      PLDHashEntryHdr* e = slot.ToEntry();
+      if (matchEntry(e, aKey)) {
+        return aSuccess(slot);
+      }
     }
   }
 
   // NOTREACHED
-  return nullptr;
+  return aFailure();
 }
 
 // This is a copy of SearchTable(), used by ChangeTable(), hardcoded to
 //   1. assume |Reason| is |ForAdd|,
 //   2. assume that |aKey| will never match an existing entry, and
 //   3. assume that no entries have been removed from the current table
 //      structure.
 // Avoiding the need for |aKey| means we can avoid needing a way to map entries
 // to keys, which means callers can use complex key types more easily.
-MOZ_ALWAYS_INLINE PLDHashEntryHdr*
-PLDHashTable::FindFreeEntry(PLDHashNumber aKeyHash) const
+MOZ_ALWAYS_INLINE auto
+PLDHashTable::FindFreeSlot(PLDHashNumber aKeyHash) const -> Slot
 {
   MOZ_ASSERT(mEntryStore.Get());
   NS_ASSERTION(!(aKeyHash & kCollisionFlag),
                "!(aKeyHash & kCollisionFlag)");
 
   // Compute the primary hash address.
   PLDHashNumber hash1 = Hash1(aKeyHash);
-  PLDHashEntryHdr* entry = AddressEntry(hash1);
+  Slot slot = SlotForIndex(hash1);
 
   // Miss: return space for a new entry.
-  if (EntryIsFree(entry)) {
-    return entry;
+  if (slot.IsFree()) {
+    return slot;
   }
 
   // Collision: double hash.
   PLDHashNumber hash2;
   uint32_t sizeMask;
   Hash2(aKeyHash, hash2, sizeMask);
 
   for (;;) {
-    NS_ASSERTION(!EntryIsRemoved(entry),
-                 "!EntryIsRemoved(entry)");
-    entry->mKeyHash |= kCollisionFlag;
+    MOZ_ASSERT(!slot.IsRemoved());
+    slot.MarkColliding();
 
     hash1 -= hash2;
     hash1 &= sizeMask;
 
-    entry = AddressEntry(hash1);
-    if (EntryIsFree(entry)) {
-      return entry;
+    slot = SlotForIndex(hash1);
+    if (slot.IsFree()) {
+      return slot;
     }
   }
 
   // NOTREACHED
 }
 
 bool
 PLDHashTable::ChangeTable(int32_t aDeltaLog2)
@@ -493,35 +508,31 @@ PLDHashTable::ChangeTable(int32_t aDelta
     return false;
   }
 
   // We can't fail from here on, so update table parameters.
   mHashShift = kPLDHashNumberBits - newLog2;
   mRemovedCount = 0;
 
   // Assign the new entry store to table.
-  char* oldEntryStore;
-  char* oldEntryAddr;
-  oldEntryAddr = oldEntryStore = mEntryStore.Get();
+  char* oldEntryStore = mEntryStore.Get();
   mEntryStore.Set(newEntryStore, &mGeneration);
   PLDHashMoveEntry moveEntry = mOps->moveEntry;
 
   // Copy only live entries, leaving removed ones behind.
   uint32_t oldCapacity = 1u << oldLog2;
-  for (uint32_t i = 0; i < oldCapacity; ++i) {
-    PLDHashEntryHdr* oldEntry = (PLDHashEntryHdr*)oldEntryAddr;
-    if (EntryIsLive(oldEntry)) {
-      const PLDHashNumber key = oldEntry->mKeyHash & ~kCollisionFlag;
-      PLDHashEntryHdr* newEntry = FindFreeEntry(key);
-      NS_ASSERTION(EntryIsFree(newEntry), "EntryIsFree(newEntry)");
-      moveEntry(this, oldEntry, newEntry);
-      newEntry->mKeyHash = key;
+  EntryStore::ForEachSlot(oldEntryStore, oldCapacity, mEntrySize, [&](const Slot& slot) {
+    if (slot.IsLive()) {
+      const PLDHashNumber key = slot.KeyHash() & ~kCollisionFlag;
+      Slot newSlot = FindFreeSlot(key);
+      MOZ_ASSERT(newSlot.IsFree());
+      moveEntry(this, slot.ToEntry(), newSlot.ToEntry());
+      newSlot.SetKeyHash(key);
     }
-    oldEntryAddr += mEntrySize;
-  }
+  });
 
   free(oldEntryStore);
   return true;
 }
 
 MOZ_ALWAYS_INLINE PLDHashNumber
 PLDHashTable::ComputeKeyHash(const void* aKey) const
 {
@@ -540,21 +551,28 @@ PLDHashTable::ComputeKeyHash(const void*
 
 PLDHashEntryHdr*
 PLDHashTable::Search(const void* aKey) const
 {
 #ifdef DEBUG
   AutoReadOp op(mChecker);
 #endif
 
-  PLDHashEntryHdr* entry = mEntryStore.Get()
-                         ? SearchTable<ForSearchOrRemove>(aKey,
-                                                          ComputeKeyHash(aKey))
-                         : nullptr;
-  return entry;
+  if (!mEntryStore.Get()) {
+    return nullptr;
+  }
+
+  return SearchTable<ForSearchOrRemove>(aKey,
+                                        ComputeKeyHash(aKey),
+                                        [&](Slot& slot) -> PLDHashEntryHdr* {
+                                          return slot.ToEntry();
+                                        },
+                                        [&]() -> PLDHashEntryHdr* {
+                                          return nullptr;
+                                        });
 }
 
 PLDHashEntryHdr*
 PLDHashTable::Add(const void* aKey, const mozilla::fallible_t&)
 {
 #ifdef DEBUG
   AutoWriteOp op(mChecker);
 #endif
@@ -590,31 +608,36 @@ PLDHashTable::Add(const void* aKey, cons
         mEntryCount + mRemovedCount >= MaxLoadOnGrowthFailure(capacity)) {
       return nullptr;
     }
   }
 
   // Look for entry after possibly growing, so we don't have to add it,
   // then skip it while growing the table and re-add it after.
   PLDHashNumber keyHash = ComputeKeyHash(aKey);
-  PLDHashEntryHdr* entry = SearchTable<ForAdd>(aKey, keyHash);
-  if (!EntryIsLive(entry)) {
-    // Initialize the entry, indicating that it's no longer free.
-    if (EntryIsRemoved(entry)) {
+  Slot slot = SearchTable<ForAdd>(aKey, keyHash,
+                                  [&](Slot& found) -> Slot { return found; },
+                                  [&]() -> Slot {
+                                    MOZ_CRASH("Nope");
+                                    return Slot(nullptr);
+                                  });
+  if (!slot.IsLive()) {
+    // Initialize the slot, indicating that it's no longer free.
+    if (slot.IsRemoved()) {
       mRemovedCount--;
       keyHash |= kCollisionFlag;
     }
     if (mOps->initEntry) {
-      mOps->initEntry(entry, aKey);
+      mOps->initEntry(slot.ToEntry(), aKey);
     }
-    entry->mKeyHash = keyHash;
+    slot.SetKeyHash(keyHash);
     mEntryCount++;
   }
 
-  return entry;
+  return slot.ToEntry();
 }
 
 PLDHashEntryHdr*
 PLDHashTable::Add(const void* aKey)
 {
   PLDHashEntryHdr* entry = Add(aKey, fallible);
   if (!entry) {
     if (!mEntryStore.Get()) {
@@ -635,57 +658,70 @@ PLDHashTable::Add(const void* aKey)
 
 void
 PLDHashTable::Remove(const void* aKey)
 {
 #ifdef DEBUG
   AutoWriteOp op(mChecker);
 #endif
 
-  PLDHashEntryHdr* entry = mEntryStore.Get()
-                         ? SearchTable<ForSearchOrRemove>(aKey,
-                                                          ComputeKeyHash(aKey))
-                         : nullptr;
-  if (entry) {
-    RawRemove(entry);
-    ShrinkIfAppropriate();
+  if (!mEntryStore.Get()) {
+    return;
   }
+
+  PLDHashNumber keyHash = ComputeKeyHash(aKey);
+  SearchTable<ForSearchOrRemove>(aKey, keyHash,
+                                 [&](Slot& slot) {
+                                   RawRemove(slot);
+                                   ShrinkIfAppropriate();
+                                 },
+                                 [&]() {
+                                   // Do nothing.
+                                 });
 }
 
 void
 PLDHashTable::RemoveEntry(PLDHashEntryHdr* aEntry)
 {
 #ifdef DEBUG
   AutoWriteOp op(mChecker);
 #endif
 
   RawRemove(aEntry);
   ShrinkIfAppropriate();
 }
 
 void
 PLDHashTable::RawRemove(PLDHashEntryHdr* aEntry)
 {
+  Slot slot(aEntry);
+  RawRemove(slot);
+}
+
+void
+PLDHashTable::RawRemove(Slot& aSlot)
+{
   // Unfortunately, we can only do weak checking here. That's because
   // RawRemove() can be called legitimately while an Enumerate() call is
   // active, which doesn't fit well into how Checker's mState variable works.
   MOZ_ASSERT(mChecker.IsWritable());
 
   MOZ_ASSERT(mEntryStore.Get());
 
-  MOZ_ASSERT(EntryIsLive(aEntry), "EntryIsLive(aEntry)");
+  MOZ_ASSERT(aSlot.IsLive());
 
   // Load keyHash first in case clearEntry() goofs it.
-  PLDHashNumber keyHash = aEntry->mKeyHash;
-  mOps->clearEntry(this, aEntry);
+  PLDHashEntryHdr* entry = aSlot.ToEntry();
+  PLDHashNumber keyHash = aSlot.KeyHash();
+  mOps->clearEntry(this, entry);
   if (keyHash & kCollisionFlag) {
-    MarkEntryRemoved(aEntry);
+    aSlot.MarkRemoved();
     mRemovedCount++;
   } else {
-    MarkEntryFree(aEntry);
+    aSlot.MarkFree();
   }
   mEntryCount--;
 }
 
 // Shrink or compress if a quarter or more of all entries are removed, or if the
 // table is underloaded according to the minimum alpha, and is not minimal-size
 // already.
 void
@@ -726,43 +762,42 @@ PLDHashTable::Iterator::Iterator(Iterato
   , mCurrent(aOther.mCurrent)
   , mNexts(aOther.mNexts)
   , mNextsLimit(aOther.mNextsLimit)
   , mHaveRemoved(aOther.mHaveRemoved)
   , mEntrySize(aOther.mEntrySize)
 {
   // No need to change |mChecker| here.
   aOther.mTable = nullptr;
-  aOther.mLimit = nullptr;
-  aOther.mCurrent = nullptr;
+  // We don't really have the concept of a null slot, so leave mLimit/mCurrent.
   aOther.mNexts = 0;
   aOther.mNextsLimit = 0;
   aOther.mHaveRemoved = false;
   aOther.mEntrySize = 0;
 }
 
 PLDHashTable::Iterator::Iterator(PLDHashTable* aTable)
   : mTable(aTable)
-  , mLimit(mTable->mEntryStore.Get() + mTable->Capacity() * mTable->mEntrySize)
-  , mCurrent(mTable->mEntryStore.Get())
+  , mLimit(mTable->mEntryStore.SlotForIndex(mTable->Capacity(), mTable->mEntrySize))
+  , mCurrent(mTable->mEntryStore.SlotForIndex(0, mTable->mEntrySize))
   , mNexts(0)
   , mNextsLimit(mTable->EntryCount())
   , mHaveRemoved(false)
   , mEntrySize(aTable->mEntrySize)
 {
 #ifdef DEBUG
   mTable->mChecker.StartReadOp();
 #endif
 
   if (ChaosMode::isActive(ChaosFeature::HashTableIteration) &&
       mTable->Capacity() > 0) {
     // Start iterating at a random entry. It would be even more chaotic to
     // iterate in fully random order, but that's harder.
-    mCurrent += ChaosMode::randomUint32LessThan(mTable->Capacity()) *
-                mTable->mEntrySize;
+    uint32_t i = ChaosMode::randomUint32LessThan(mTable->Capacity());
+    mCurrent = mTable->mEntryStore.SlotForIndex(i, mTable->mEntrySize);
   }
 
   // Advance to the first live entry, if there is one.
   if (!Done()) {
     while (IsOnNonLiveEntry()) {
       MoveToNextEntry();
     }
   }
@@ -779,25 +814,26 @@ PLDHashTable::Iterator::~Iterator()
 #endif
   }
 }
 
 MOZ_ALWAYS_INLINE bool
 PLDHashTable::Iterator::IsOnNonLiveEntry() const
 {
   MOZ_ASSERT(!Done());
-  return !EntryIsLive(reinterpret_cast<PLDHashEntryHdr*>(mCurrent));
+  return !mCurrent.IsLive();
 }
 
 MOZ_ALWAYS_INLINE void
 PLDHashTable::Iterator::MoveToNextEntry()
 {
-  mCurrent += mEntrySize;
+  mCurrent.Next(mEntrySize);
   if (mCurrent == mLimit) {
-    mCurrent = mTable->mEntryStore.Get();  // Wrap-around. Possible due to Chaos Mode.
+    // We wrapped around.  Possible due to chaos mode.
+    mCurrent = mTable->mEntryStore.SlotForIndex(0, mEntrySize);
   }
 }
 
 void
 PLDHashTable::Iterator::Next()
 {
   MOZ_ASSERT(!Done());
 
@@ -809,18 +845,17 @@ PLDHashTable::Iterator::Next()
       MoveToNextEntry();
     } while (IsOnNonLiveEntry());
   }
 }
 
 void
 PLDHashTable::Iterator::Remove()
 {
-  // This cast is needed for the same reason as the one in the destructor.
-  mTable->RawRemove(Get());
+  mTable->RawRemove(mCurrent);
   mHaveRemoved = true;
 }
 
 #ifdef DEBUG
 void
 PLDHashTable::MarkImmutable()
 {
   mChecker.SetNonWritable();
--- a/xpcom/ds/PLDHashTable.h
+++ b/xpcom/ds/PLDHashTable.h
@@ -8,16 +8,17 @@
 // PLDHashTable and mozilla::HashTable.
 
 #ifndef PLDHashTable_h
 #define PLDHashTable_h
 
 #include "mozilla/Atomics.h"
 #include "mozilla/Attributes.h" // for MOZ_ALWAYS_INLINE
 #include "mozilla/fallible.h"
+#include "mozilla/FunctionTypeTraits.h"
 #include "mozilla/HashFunctions.h"
 #include "mozilla/MemoryReporting.h"
 #include "mozilla/Move.h"
 #include "mozilla/Types.h"
 #include "nscore.h"
 
 using PLDHashNumber = mozilla::HashNumber;
 static const uint32_t kPLDHashNumberBits = mozilla::kHashNumberBits;
@@ -217,38 +218,107 @@ private:
 // case you should keep using double hashing but switch to using pointer
 // elements). Also, with double hashing, you can't safely hold an entry pointer
 // and use it after an add or remove operation, unless you sample Generation()
 // before adding or removing, and compare the sample after, dereferencing the
 // entry pointer only if Generation() has not changed.
 class PLDHashTable
 {
 private:
+  // A slot represents a cached hash value and its associated entry stored
+  // in the hash table.  While they currently belong to the same object,
+  // PLDHashEntryHdr, they do not necessarily need to be contiguous in memory,
+  // and this abstraction helps enforce the separation between the two.
+  struct Slot
+  {
+    Slot(PLDHashEntryHdr* aEntry)
+      : mEntry(aEntry)
+    {}
+
+    Slot(const Slot&) = default;
+    Slot(Slot&& aOther)
+      : mEntry(aOther.mEntry)
+    {}
+
+    Slot& operator=(Slot&& aOther) {
+      this->~Slot();
+      new (this) Slot(std::move(aOther));
+      return *this;
+    }
+
+    bool operator==(const Slot& aOther)
+    {
+      return mEntry == aOther.mEntry;
+    }
+
+    PLDHashNumber KeyHash() const { return mEntry->mKeyHash; }
+    void SetKeyHash(PLDHashNumber aHash) { mEntry->mKeyHash = aHash; }
+
+    PLDHashEntryHdr* ToEntry() const { return mEntry; }
+
+    bool IsFree() const { return KeyHash() == 0; }
+    bool IsRemoved() const { return KeyHash() == 1; }
+    bool IsLive() const { return KeyHash() >= 2; }
+
+    void MarkFree() { mEntry->mKeyHash = 0; }
+    void MarkRemoved() { mEntry->mKeyHash = 1; }
+    void MarkColliding() { mEntry->mKeyHash |= kCollisionFlag; }
+
+    void Next(uint32_t aEntrySize) {
+      char* p = reinterpret_cast<char*>(mEntry);
+      p += aEntrySize;
+      mEntry = reinterpret_cast<PLDHashEntryHdr*>(p);
+    }
+  private:
+    PLDHashEntryHdr* mEntry;
+  };
+
   // This class maintains the invariant that every time the entry store is
   // changed, the generation is updated.
   //
   // Note: It would be natural to store the generation within this class, but
   // we can't do that without bloating sizeof(PLDHashTable) on 64-bit machines.
   // So instead we store it outside this class, and Set() takes a pointer to it
   // and ensures it is updated as necessary.
   class EntryStore
   {
   private:
     char* mEntryStore;
 
+    PLDHashEntryHdr* EntryAt(uint32_t aIndex, uint32_t aEntrySize) const {
+      return reinterpret_cast<PLDHashEntryHdr*>(Get() + aIndex * aEntrySize);
+    }
   public:
     EntryStore() : mEntryStore(nullptr) {}
 
     ~EntryStore()
     {
       free(mEntryStore);
       mEntryStore = nullptr;
     }
 
     char* Get() const { return mEntryStore; }
+    Slot SlotForIndex(uint32_t aIndex, uint32_t aEntrySize) const {
+      return Slot(EntryAt(aIndex, aEntrySize));
+    }
+
+    template<typename F>
+    void ForEachSlot(uint32_t aCapacity, uint32_t aEntrySize, F&& aFunc) {
+      ForEachSlot(Get(), aCapacity, aEntrySize, std::move(aFunc));
+    }
+
+    template<typename F>
+    static void ForEachSlot(char* aStore, uint32_t aCapacity, uint32_t aEntrySize,
+                            F&& aFunc) {
+      Slot slot(reinterpret_cast<PLDHashEntryHdr*>(aStore));
+      for (size_t i = 0; i < aCapacity; ++i) {
+        aFunc(slot);
+        slot.Next(aEntrySize);
+      }
+    }
 
     void Set(char* aEntryStore, uint16_t* aGeneration)
     {
       mEntryStore = aEntryStore;
       *aGeneration += 1;
     }
   };
 
@@ -462,35 +532,33 @@ public:
 
     // Have we finished?
     bool Done() const { return mNexts == mNextsLimit; }
 
     // Get the current entry.
     PLDHashEntryHdr* Get() const
     {
       MOZ_ASSERT(!Done());
-
-      PLDHashEntryHdr* entry = reinterpret_cast<PLDHashEntryHdr*>(mCurrent);
-      MOZ_ASSERT(EntryIsLive(entry));
-      return entry;
+      MOZ_ASSERT(mCurrent.IsLive());
+      return mCurrent.ToEntry();
     }
 
     // Advance to the next entry.
     void Next();
 
     // Remove the current entry. Must only be called once per entry, and Get()
     // must not be called on that entry afterwards.
     void Remove();
 
   protected:
     PLDHashTable* mTable;             // Main table pointer.
 
   private:
-    char* mLimit;                     // One past the last entry.
-    char* mCurrent;                   // Pointer to the current entry.
+    Slot mLimit;                      // One past the last entry.
+    Slot mCurrent;                    // Pointer to the current entry.
     uint32_t mNexts;                  // Number of Next() calls.
     uint32_t mNextsLimit;             // Next() call limit.
 
     bool mHaveRemoved;                // Have any elements been removed?
     uint8_t mEntrySize;               // Size of entries.
 
     bool IsOnNonLiveEntry() const;
     void MoveToNextEntry();
@@ -536,39 +604,45 @@ private:
   {
     aEntry->mKeyHash = 1;
   }
 
   PLDHashNumber Hash1(PLDHashNumber aHash0) const;
   void Hash2(PLDHashNumber aHash,
              uint32_t& aHash2Out, uint32_t& aSizeMaskOut) const;
 
+  static bool MatchSlotKeyhash(Slot& aSlot, const PLDHashNumber aHash);
   static bool MatchEntryKeyhash(const PLDHashEntryHdr* aEntry,
                                 const PLDHashNumber aHash);
+  Slot SlotForIndex(uint32_t aIndex) const;
   PLDHashEntryHdr* AddressEntry(uint32_t aIndex) const;
 
   // We store mHashShift rather than sizeLog2 to optimize the collision-free
   // case in SearchTable.
   uint32_t CapacityFromHashShift() const
   {
     return ((uint32_t)1 << (kPLDHashNumberBits - mHashShift));
   }
 
   PLDHashNumber ComputeKeyHash(const void* aKey) const;
 
   enum SearchReason { ForSearchOrRemove, ForAdd };
 
-  template <SearchReason Reason>
-  PLDHashEntryHdr* NS_FASTCALL
-    SearchTable(const void* aKey, PLDHashNumber aKeyHash) const;
+  // Avoid using bare `Success` and `Failure`, as those names are commonly
+  // defined as macros.
+  template <SearchReason Reason, typename PLDSuccess, typename PLDFailure>
+  auto
+  SearchTable(const void* aKey, PLDHashNumber aKeyHash,
+              PLDSuccess&& aSucess, PLDFailure&& aFailure) const;
 
-  PLDHashEntryHdr* FindFreeEntry(PLDHashNumber aKeyHash) const;
+  Slot FindFreeSlot(PLDHashNumber aKeyHash) const;
 
   bool ChangeTable(int aDeltaLog2);
 
+  void RawRemove(Slot& aSlot);
   void ShrinkIfAppropriate();
 
   PLDHashTable(const PLDHashTable& aOther) = delete;
   PLDHashTable& operator=(const PLDHashTable& aOther) = delete;
 };
 
 // Compute the hash code for a given key to be looked up, added, or removed.
 // A hash code may have any PLDHashNumber value.