--- a/netwerk/dns/nsHostResolver.cpp
+++ b/netwerk/dns/nsHostResolver.cpp
@@ -190,16 +190,17 @@ nsHostRecord::nsHostRecord(const nsHostK
     , mTRRUsed(false)
     , mNativeUsed(false)
     , onQueue(false)
     , usingAnyThread(false)
     , mDoomed(false)
     , mDidCallbacks(false)
     , mGetTtl(false)
     , mResolveAgain(false)
+    , mInEvictQ(false)
     , mTrrAUsed(INIT)
     , mTrrAAAAUsed(INIT)
     , mTrrLock("nsHostRecord.mTrrLock")
     , mBlacklistedCount(0)
 {
 }
 
 void
@@ -221,20 +222,25 @@ nsHostRecord::Invalidate()
 {
     mDoomed = true;
 }
 
 void
 nsHostRecord::SetExpiration(const mozilla::TimeStamp& now, unsigned int valid, unsigned int grace)
 {
     mValidStart = now;
+    if ((valid + grace) < 60) {
+        grace = 60 - valid;
+        LOG(("SetExpiration: artificially bumped grace to %d\n", valid));
+    }
     mGraceStart = now + TimeDuration::FromSeconds(valid);
     mValidEnd = now + TimeDuration::FromSeconds(valid + grace);
 }
 
+// The record might still be in the eviction queue when this method is called
 void
 nsHostRecord::CopyExpirationTimesAndFlagsFrom(const nsHostRecord *aFromHostRecord)
 {
     // This is used to copy information from a cache entry to a record. All
     // information necessary for HasUsableRecord needs to be copied.
     mValidStart = aFromHostRecord->mValidStart;
     mValidEnd = aFromHostRecord->mValidEnd;
     mGraceStart = aFromHostRecord->mGraceStart;
@@ -523,16 +529,17 @@ nsHostResolver::nsHostResolver(uint32_t 
     , mLock("nsHostResolver.mLock")
     , mIdleThreadCV(mLock, "nsHostResolver.mIdleThreadCV")
     , mEvictionQSize(0)
     , mShutdown(true)
     , mNumIdleThreads(0)
     , mThreadCount(0)
     , mActiveAnyThreadCount(0)
     , mPendingCount(0)
+    , mEvictCounter(0)
 {
     mCreationTime = PR_Now();
 
     mLongIdleTimeout  = TimeDuration::FromSeconds(LongIdleTimeoutSeconds);
     mShortIdleTimeout = TimeDuration::FromSeconds(ShortIdleTimeoutSeconds);
 }
 
 nsHostResolver::~nsHostResolver() = default;
@@ -575,53 +582,98 @@ nsHostResolver::Init()
         LOG(("Calling 'res_ninit'.\n"));
         res_ninit(&_res);
     }
 #endif
 
     return NS_OK;
 }
 
+
+// For SplayTree, primary compare on expiry time. secondary on salt.
+int
+nsHostRecord::compare(const nsHostRecord & aOne, const nsHostRecord & aTwo)
+{
+    if (aOne.mEvictTime < aTwo.mEvictTime) {
+        return -1;
+    } else if (aOne.mEvictTime > aTwo.mEvictTime) {
+        return 1;
+    } else if (aOne.mEvictSalt < aTwo.mEvictSalt) {
+        return -1;
+    } else if (aOne.mEvictSalt > aTwo.mEvictSalt) {
+        return 1;
+    }
+    return 0;
+}
+
+bool
+nsHostRecord::IsInEvictionQ()
+{
+    return mInEvictQ;
+}
+
+void
+nsHostRecord::FlagAsEvicted(uint32_t aSalt)
+{
+    MOZ_ASSERT(mEvictTime);
+    MOZ_ASSERT(!mInEvictQ);
+    mEvictSalt = aSalt;
+    mInEvictQ = true;
+}
+
+void
+nsHostRecord::UnflagAsEvicted()
+{
+    MOZ_ASSERT(mInEvictQ);
+    mInEvictQ = false;
+}
+
 void
 nsHostResolver::ClearPendingQueue(LinkedList<RefPtr<nsHostRecord>>& aPendingQ)
 {
     // loop through pending queue, erroring out pending lookups.
     if (!aPendingQ.isEmpty()) {
         for (RefPtr<nsHostRecord> rec : aPendingQ) {
             rec->Cancel();
             CompleteLookup(rec, NS_ERROR_ABORT, nullptr, rec->pb);
         }
     }
 }
 
+// Assumes mLock is held!
+void nsHostResolver::FlushEvictionQ()
+{
+    // Clear the eviction queue and purge the corresponding entries from the
+    // cache. Entries in the eviction queue are not resolving so no need to
+    // ->Cancel()
+    nsHostRecord *rec;
+    while (!mEvictionTree.empty() && (rec = mEvictionTree.removeMin())) {
+        MOZ_ASSERT(!rec->mTrrA);
+        MOZ_ASSERT(!rec->mTrrAAAA);
+        rec->UnflagAsEvicted();
+        mRecordDB.Remove(*static_cast<nsHostKey *>(rec));
+    }
+    mEvictionQSize = 0; // nothing left
+}
+
 //
 // FlushCache() is what we call when the network has changed. We must not
 // trust names that were resolved before this change. They may resolve
 // differently now.
 //
 // This function removes all existing resolved host entries from the hash.
 // Names that are in the pending queues can be left there. Entries in the
 // cache that have 'Resolve' set true but not 'onQueue' are being resolved
 // right now, so we need to mark them to get re-resolved on completion!
 
 void
 nsHostResolver::FlushCache()
 {
     MutexAutoLock lock(mLock);
-    mEvictionQSize = 0;
-
-    // Clear the evictionQ and remove all its corresponding entries from
-    // the cache first
-    if (!mEvictionQ.isEmpty()) {
-        for (RefPtr<nsHostRecord> rec : mEvictionQ) {
-            rec->Cancel();
-            mRecordDB.Remove(*static_cast<nsHostKey *>(rec));
-        }
-        mEvictionQ.clear();
-    }
+    FlushEvictionQ();
 
     // Refresh the cache entries that are resolving RIGHT now, remove the rest.
     for (auto iter = mRecordDB.Iter(); !iter.Done(); iter.Next()) {
         nsHostRecord* record = iter.UserData();
         // Try to remove the record, or mark it for refresh.
         if (record->RemoveOrRefresh()) {
             if (record->isInList()) {
                 record->remove();
@@ -638,53 +690,47 @@ nsHostResolver::Shutdown()
 
     {
         DebugOnly<nsresult> rv = Preferences::UnregisterCallback(
             &DnsPrefChanged, kPrefGetTtl, this);
         NS_WARNING_ASSERTION(NS_SUCCEEDED(rv),
                              "Could not unregister DNS TTL pref callback.");
     }
 
-    LinkedList<RefPtr<nsHostRecord>> pendingQHigh, pendingQMed, pendingQLow, evictionQ;
+    LinkedList<RefPtr<nsHostRecord>> pendingQHigh, pendingQMed, pendingQLow;
 
     {
         MutexAutoLock lock(mLock);
 
         mShutdown = true;
 
         // Move queues to temporary lists.
         pendingQHigh = std::move(mHighQ);
         pendingQMed = std::move(mMediumQ);
         pendingQLow = std::move(mLowQ);
-        evictionQ = std::move(mEvictionQ);
 
         mEvictionQSize = 0;
         mPendingCount = 0;
 
+        FlushEvictionQ();
+
         if (mNumIdleThreads)
             mIdleThreadCV.NotifyAll();
 
         // empty host database
         mRecordDB.Clear();
     }
 
     ClearPendingQueue(pendingQHigh);
     ClearPendingQueue(pendingQMed);
     ClearPendingQueue(pendingQLow);
 
-    if (!evictionQ.isEmpty()) {
-        for (RefPtr<nsHostRecord> rec : evictionQ) {
-            rec->Cancel();
-        }
-    }
-
     pendingQHigh.clear();
     pendingQMed.clear();
     pendingQLow.clear();
-    evictionQ.clear();
 
     for (auto iter = mRecordDB.Iter(); !iter.Done(); iter.Next()) {
         iter.UserData()->Cancel();
     }
 #ifdef NS_BUILD_REFCNT_LOGGING
 
     // Logically join the outstanding worker threads with a timeout.
     // Use this approach instead of PR_JoinThread() because that does
@@ -1089,22 +1135,23 @@ nsHostResolver::TrrLookup(nsHostRecord *
 #endif
     MOZ_ASSERT(!rec->mResolving);
 
     if (!gTRRService || !gTRRService->Enabled()) {
         LOG(("TrrLookup:: %s service not enabled\n", rec->host.get()));
         return NS_ERROR_UNKNOWN_HOST;
     }
 
-    if (rec->isInList()) {
-        // we're already on the eviction queue. This is a renewal
+    if (rec->IsInEvictionQ()) {
+        // we're already in the eviction queue. This is a renewal
         MOZ_ASSERT(mEvictionQSize);
-        AssertOnQ(rec, mEvictionQ);
-
-        rec->remove();
+        rec->UnflagAsEvicted();
+        mEvictionTree.remove(*aRec);
+        LOG(("TrrLookup: removed rec %p %s from evictq\n", (void *)aRec,
+             rec->addr_info->mHostName));
         mEvictionQSize--;
     }
 
     rec->mTRRSuccess = 0; // bump for each successful TRR response
     rec->mTrrAUsed = nsHostRecord::INIT;
     rec->mTrrAAAAUsed = nsHostRecord::INIT;
     rec->mTrrStart = TimeStamp::Now();
     rec->mTRRUsed = true; // this record gets TRR treatment
@@ -1147,44 +1194,31 @@ nsHostResolver::TrrLookup(nsHostRecord *
                 sendAgain = true;
             }
         }
     } while (sendAgain);
 
     return madeQuery ? NS_OK : NS_ERROR_UNKNOWN_HOST;
 }
 
-void
-nsHostResolver::AssertOnQ(nsHostRecord *rec, LinkedList<RefPtr<nsHostRecord>>& q)
-{
-#ifdef DEBUG
-    MOZ_ASSERT(!q.isEmpty());
-    MOZ_ASSERT(rec->isInList());
-    for (RefPtr<nsHostRecord> r: q) {
-        if (rec == r) {
-            return;
-        }
-    }
-    MOZ_ASSERT(false, "Did not find element");
-#endif
-}
-
 nsresult
 nsHostResolver::NativeLookup(nsHostRecord *aRec)
 {
     mLock.AssertCurrentThreadOwns();
     RefPtr<nsHostRecord> rec(aRec);
 
     rec->mNativeStart = TimeStamp::Now();
 
     // Add rec to one of the pending queues, possibly removing it from mEvictionQ.
-    if (rec->isInList()) {
+    if (rec->IsInEvictionQ()) {
         MOZ_ASSERT(mEvictionQSize);
-        AssertOnQ(rec, mEvictionQ);
-        rec->remove(); // was on the eviction queue
+        rec->UnflagAsEvicted();
+        mEvictionTree.remove(*rec);
+        LOG(("NativeLookup: removed rec %p %s from evictq\n", (void *)rec,
+             rec->addr_info->mHostName));
         mEvictionQSize--;
     }
 
     switch (nsHostRecord::GetPriority(rec->flags)) {
         case nsHostRecord::DNS_PRIORITY_HIGH:
             mHighQ.insertBack(rec);
             break;
 
@@ -1458,16 +1492,70 @@ different_rrset(AddrInfo *rrset1, AddrIn
             LOG(("different_rrset true due to content change\n"));
             return true;
         }
     }
     LOG(("different_rrset false\n"));
     return false;
 }
 
+void
+nsHostResolver::EvictTelemetry(nsHostRecord *rec, TimeStamp now)
+{
+    if (!rec->negative) {
+        // record the age of the entry upon eviction.
+        TimeDuration age = now - rec->mValidStart;
+        Telemetry::Accumulate(Telemetry::DNS_CLEANUP_AGE,
+                              static_cast<uint32_t>(age.ToSeconds() / 60));
+        if (rec->CheckExpiration(now) != nsHostRecord::EXP_EXPIRED) {
+            Telemetry::Accumulate(Telemetry::DNS_PREMATURE_EVICTION,
+                                  static_cast<uint32_t>(age.ToSeconds() / 60));
+        }
+    }
+}
+
+// AddToEvictQ() - adds the record to the eviction queue. If it reaches the
+// max cache limit, evict the entry that is next in line.
+// Assumes the mlock is held.
+void
+nsHostResolver::AddToEvictQ(nsHostRecord *rec)
+{
+    LOG(("AddToEvictQ: Add %s (%d entries)\n", rec->addr_info->mHostName,
+         mEvictionQSize));
+    MOZ_ASSERT(!rec->IsInEvictionQ());
+    TimeStamp now = TimeStamp::NowLoRes();
+    // set evicttime before .insert()
+    rec->mEvictTime = rec->mValidEnd;
+    rec->mEvictAdd = now;
+    mEvictionTree.insert(rec);
+    rec->FlagAsEvicted(mEvictCounter++);
+    if (mEvictionQSize == mMaxCacheEntries) {
+        nsHostRecord *evicted = mEvictionTree.removeMin();
+        // timeleft: positive time means premature eviction
+        TimeDuration timeleft = evicted->mValidEnd - now;
+        TimeDuration age = now - evicted->mEvictAdd;
+        MOZ_ASSERT(evicted);
+        evicted->UnflagAsEvicted();
+        LOG(("AddToEvictQ: evicted %s (age %.1f secs, timeleft: %.1f secs)\n",
+             evicted->addr_info->mHostName,
+             age.ToSeconds(), timeleft.ToSeconds()));
+        if (!evicted->negative) {
+            // record the age of the entry upon eviction.
+            Telemetry::Accumulate(Telemetry::DNS_CLEANUP_AGE,
+                                  static_cast<uint32_t>(age.ToSeconds() / 60));
+            if (evicted->CheckExpiration(now) != nsHostRecord::EXP_EXPIRED) {
+                Telemetry::Accumulate(Telemetry::DNS_PREMATURE_EVICTION,
+                                      static_cast<uint32_t>(age.ToSeconds() / 60));
+            }
+        }
+    } else {
+        mEvictionQSize++;
+    }
+}
+
 //
 // CompleteLookup() checks if the resolving should be redone and if so it
 // returns LOOKUP_RESOLVEAGAIN, but only if 'status' is not NS_ERROR_ABORT.
 // takes ownership of AddrInfo parameter
 nsHostResolver::LookupStatus
 nsHostResolver::CompleteLookup(nsHostRecord* rec, nsresult status, AddrInfo* aNewRRSet, bool pb)
 {
     MutexAutoLock lock(mLock);
@@ -1649,37 +1737,18 @@ nsHostResolver::CompleteLookup(nsHostRec
             c->OnResolveHostComplete(this, rec, status);
         }
         rec->mDidCallbacks = true;
     }
 
     if (!rec->mResolving && !mShutdown) {
         rec->ResolveComplete();
 
-        // add to mEvictionQ
-        MOZ_ASSERT(!rec->isInList());
-        mEvictionQ.insertBack(rec);
-        if (mEvictionQSize < mMaxCacheEntries) {
-            mEvictionQSize++;
-        } else {
-            // remove first element on mEvictionQ
-            RefPtr<nsHostRecord> head = mEvictionQ.popFirst();
-            mRecordDB.Remove(*static_cast<nsHostKey *>(head.get()));
-
-            if (!head->negative) {
-                // record the age of the entry upon eviction.
-                TimeDuration age = TimeStamp::NowLoRes() - head->mValidStart;
-                Telemetry::Accumulate(Telemetry::DNS_CLEANUP_AGE,
-                                      static_cast<uint32_t>(age.ToSeconds() / 60));
-                if (head->CheckExpiration(TimeStamp::Now()) !=
-                    nsHostRecord::EXP_EXPIRED) {
-                  Telemetry::Accumulate(Telemetry::DNS_PREMATURE_EVICTION,
-                                        static_cast<uint32_t>(age.ToSeconds() / 60));
-                }
-            }
+        if (rec->addr_info) {
+            AddToEvictQ(rec);
         }
     }
 
 #ifdef DNSQUERY_AVAILABLE
     // Unless the result is from TRR, resolve again to get TTL
     bool fromTRR = false;
     {
         MutexAutoLock lock(rec->addr_info_lock);
@@ -1733,18 +1802,19 @@ nsHostResolver::CancelAsyncRequest(const
                 break;
             }
         }
 
         // If there are no more callbacks, remove the hash table entry
         if (recPtr && recPtr->mCallbacks.isEmpty()) {
             mRecordDB.Remove(*static_cast<nsHostKey *>(recPtr));
             // If record is on a Queue, remove it and then deref it
-            if (recPtr->isInList()) {
-                recPtr->remove();
+            if (recPtr->IsInEvictionQ()) {
+                recPtr->UnflagAsEvicted();
+                mEvictionTree.remove(*recPtr);
             }
         }
     }
 }
 
 size_t
 nsHostResolver::SizeOfIncludingThis(MallocSizeOf mallocSizeOf) const
 {
@@ -1792,17 +1862,17 @@ nsHostResolver::ThreadFunc(void *arg)
             }
             // GetHostToLookup() returns an owning reference
             MOZ_ASSERT(tmpRec);
             rec.swap(tmpRec);
         }
 
         LOG(("DNS lookup thread - Calling getaddrinfo for host [%s].\n",
              rec->host.get()));
-        
+
         TimeStamp startTime = TimeStamp::Now();
         bool getTtl = rec->mGetTtl;
         nsresult status = GetAddrInfo(rec->host.get(), rec->af,
                                       rec->flags, &ai,
                                       getTtl);
 #if defined(RES_RETRY_ON_FAILURE)
         if (NS_FAILED(status) && rs.Reset()) {
             status = GetAddrInfo(rec->host.get(), rec->af,

--- a/netwerk/dns/nsHostResolver.h
+++ b/netwerk/dns/nsHostResolver.h
@@ -17,16 +17,17 @@
 #include "nsTArray.h"
 #include "GetAddrInfo.h"
 #include "mozilla/net/DNS.h"
 #include "mozilla/net/DashboardTypes.h"
 #include "mozilla/Atomics.h"
 #include "mozilla/LinkedList.h"
 #include "mozilla/TimeStamp.h"
 #include "mozilla/UniquePtr.h"
+#include "mozilla/SplayTree.h"
 #include "nsRefPtrHashtable.h"
 
 class nsHostResolver;
 class nsResolveHostCallback;
 namespace mozilla { namespace net {
 class TRR;
 enum ResolverMode {
   MODE_NATIVEONLY, // 0 - TRR OFF (by default)
@@ -71,17 +72,18 @@ struct nsHostKey
     PLDHashNumber Hash() const;
 };
 
 /**
  * nsHostRecord - ref counted object type stored in host resolver cache.
  */
 class nsHostRecord :
     public mozilla::LinkedListElement<RefPtr<nsHostRecord>>,
-    public nsHostKey
+    public nsHostKey,
+    public mozilla::SplayTreeNode<nsHostRecord>
 {
     typedef mozilla::Mutex Mutex;
 
 public:
     NS_INLINE_DECL_THREADSAFE_REFCOUNTING(nsHostRecord)
 
     /* a fully resolved host record has either a non-null |addr_info| or |addr|
      * field.  if |addr_info| is null, it implies that the |host| is an IP
@@ -163,16 +165,27 @@ public:
     bool RemoveOrRefresh(); // Mark records currently being resolved as needed
                             // to resolve again.
     bool IsTRR() { return mTRRUsed; }
     void ResolveComplete();
     void Cancel();
 
     mozilla::net::ResolverMode mResolverMode;
 
+    // SplayTree comparison
+    static int compare(const nsHostRecord & aOne, const nsHostRecord & aTwo);
+    bool IsInEvictionQ();
+    void FlagAsEvicted(uint32_t aSalt);
+    void UnflagAsEvicted();
+    // The original eviction timestamp. Separate from mValidEnd to allow the
+    // end time to get updated while the record is still in the queue without
+    // messing up the splay.
+    mozilla::TimeStamp mEvictTime;
+    mozilla::TimeStamp mEvictAdd;
+
 private:
     friend class nsHostResolver;
 
     explicit nsHostRecord(const nsHostKey& key);
     mozilla::LinkedList<RefPtr<nsResolveHostCallback>> mCallbacks;
     nsAutoPtr<mozilla::net::AddrInfo> mFirstTRR; // partial TRR storage
 
     uint16_t  mResolving;  // counter of outstanding resolving calls
@@ -188,16 +201,17 @@ private:
     uint16_t    usingAnyThread : 1; // true if off queue and contributing to mActiveAnyThreadCount
     uint16_t    mDoomed : 1;    // explicitly expired
     uint16_t    mDidCallbacks : 1;
     uint16_t    mGetTtl : 1;
 
     // when the results from this resolve is returned, it is not to be
     // trusted, but instead a new resolve must be made!
     uint16_t    mResolveAgain : 1;
+    uint16_t    mInEvictQ : 1; // present in the eviction queue
 
     enum {
         INIT, STARTED, OK, FAILED
     } mTrrAUsed, mTrrAAAAUsed;
 
     Mutex mTrrLock; // lock when accessing the mTrrA[AAA] pointers
     RefPtr<mozilla::net::TRR> mTrrA;
     RefPtr<mozilla::net::TRR> mTrrAAAA;
@@ -206,16 +220,19 @@ private:
     // lifetime.
     uint32_t mBlacklistedCount;
 
     // a list of addresses associated with this record that have been reported
     // as unusable. the list is kept as a set of strings to make it independent
     // of gencnt.
     nsTArray<nsCString> mBlacklistedItems;
 
+    // identifier to allow multiple nodes with the same expire time in the
+    // splay tree
+    uint32_t mEvictSalt;
    ~nsHostRecord();
 };
 
 /**
  * This class is used to notify listeners when a ResolveHost operation is
  * complete. Classes that derive it must implement threadsafe nsISupports
  * to be able to use RefPtr with this class.
  */
@@ -379,16 +396,17 @@ public:
         //RES_DISABLE_IPv4 = nsIDNSService::RESOLVE_DISABLE_IPV4, // Not Used
         RES_ALLOW_NAME_COLLISION = nsIDNSService::RESOLVE_ALLOW_NAME_COLLISION,
         RES_DISABLE_TRR = nsIDNSService::RESOLVE_DISABLE_TRR,
         RES_REFRESH_CACHE = nsIDNSService::RESOLVE_REFRESH_CACHE
     };
 
     size_t SizeOfIncludingThis(mozilla::MallocSizeOf mallocSizeOf) const;
 
+    void FlushEvictionQ();
     /**
      * Flush the DNS cache.
      */
     void FlushCache();
 
     LookupStatus CompleteLookup(nsHostRecord *, nsresult, mozilla::net::AddrInfo *, bool pb) override;
     nsresult GetHostRecord(const char *host,
                            uint16_t flags, uint16_t af, bool pb,
@@ -398,18 +416,16 @@ public:
 
 private:
    explicit nsHostResolver(uint32_t maxCacheEntries,
                            uint32_t defaultCacheEntryLifetime,
                            uint32_t defaultGracePeriod);
    virtual ~nsHostResolver();
 
     nsresult Init();
-    // In debug builds it asserts that the element is in the list.
-    void AssertOnQ(nsHostRecord *, mozilla::LinkedList<RefPtr<nsHostRecord>>&);
     mozilla::net::ResolverMode Mode();
     nsresult NativeLookup(nsHostRecord *);
     nsresult TrrLookup(nsHostRecord *, mozilla::net::TRR *pushedTRR = nullptr);
 
     // Kick-off a name resolve operation, using native resolver and/or TRR
     nsresult NameLookup(nsHostRecord *);
     bool     GetHostToLookup(nsHostRecord **m);
 
@@ -443,30 +459,35 @@ private:
     uint32_t      mDefaultCacheLifetime; // granularity seconds
     uint32_t      mDefaultGracePeriod; // granularity seconds
     mutable Mutex mLock;    // mutable so SizeOfIncludingThis can be const
     CondVar       mIdleThreadCV;
     nsRefPtrHashtable<nsGenericHashKey<nsHostKey>, nsHostRecord> mRecordDB;
     mozilla::LinkedList<RefPtr<nsHostRecord>> mHighQ;
     mozilla::LinkedList<RefPtr<nsHostRecord>> mMediumQ;
     mozilla::LinkedList<RefPtr<nsHostRecord>> mLowQ;
-    mozilla::LinkedList<RefPtr<nsHostRecord>> mEvictionQ;
+    mozilla::SplayTree<nsHostRecord, nsHostRecord> mEvictionTree;
     uint32_t      mEvictionQSize;
     PRTime        mCreationTime;
     mozilla::TimeDuration mLongIdleTimeout;
     mozilla::TimeDuration mShortIdleTimeout;
 
     mozilla::Atomic<bool>     mShutdown;
     mozilla::Atomic<uint32_t> mNumIdleThreads;
     mozilla::Atomic<uint32_t> mThreadCount;
     mozilla::Atomic<uint32_t> mActiveAnyThreadCount;
     mozilla::Atomic<uint32_t> mPendingCount;
 
     // Set the expiration time stamps appropriately.
     void PrepareRecordExpiration(nsHostRecord* rec) const;
+    void EvictTelemetry(nsHostRecord *rec, mozilla::TimeStamp now);
+    void AddToEvictQ(nsHostRecord *rec);
+
+    // monotonic counter to pass to nodes in the eviction queue
+    uint32_t mEvictCounter;
 
 public:
     /*
      * Called by the networking dashboard via the DnsService2
      */
     void GetDNSCacheEntries(nsTArray<mozilla::net::DNSCacheEntries> *);
 };