Bug 1685677 - Harmonize LockedGetOriginInfosExceedingGroupLimit and LockedGetOriginInfosExceedingGlobalLimit. r=dom-workers-and-storage-reviewers,janv
☠☠ backed out by 49fff125656d ☠ ☠
authorSimon Giesecke <sgiesecke@mozilla.com>
Tue, 02 Feb 2021 12:53:39 +0000
changeset 565611 cc4f20677a7e28acc58e49bd212e4e09260018c3
parent 565610 bcbba85964cb5177fb754449fd83324f080b8154
child 565612 3c1b1f51f19cf459c858d89484d591e5b593257e
push id135529
push usersgiesecke@mozilla.com
push dateTue, 02 Feb 2021 14:30:08 +0000
treeherderautoland@129b45a961fb [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewersdom-workers-and-storage-reviewers, janv
bugs1685677
milestone87.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 1685677 - Harmonize LockedGetOriginInfosExceedingGroupLimit and LockedGetOriginInfosExceedingGlobalLimit. r=dom-workers-and-storage-reviewers,janv Instead of inserting all elements into OriginInfo array, and then removing or skipping irrelevant entries, only insert the relevant ones in the first place, using a new utility function template MaybeAppendOriginInfos. Sort them by in least-recently used order according to the access timestamp. Iterate over them to identify the threshold. Finally, truncate the array to the threshold position. Differential Revision: https://phabricator.services.mozilla.com/D101146
dom/quota/ActorsParent.cpp
dom/quota/QuotaManager.h
--- a/dom/quota/ActorsParent.cpp
+++ b/dom/quota/ActorsParent.cpp
@@ -945,17 +945,17 @@ class OriginInfo final {
    * the origin actually needs to be created. It is possible for mUsage to be
    * greater than zero while mDirectoryExists is false, representing a state
    * where a client like LocalStorage has reserved quota for disk writes, but
    * has not yet flushed the data to disk.
    */
   bool mDirectoryExists;
 };
 
-class OriginInfoLRUComparator {
+class OriginInfoAccessTimeComparator {
  public:
   bool Equals(const NotNull<RefPtr<const OriginInfo>>& a,
               const NotNull<RefPtr<const OriginInfo>>& b) const {
     return a->LockedAccessTime() == b->LockedAccessTime();
   }
 
   bool LessThan(const NotNull<RefPtr<const OriginInfo>>& a,
                 const NotNull<RefPtr<const OriginInfo>>& b) const {
@@ -1018,24 +1018,21 @@ class GroupInfoPair {
   friend class QuotaObject;
 
  public:
   MOZ_COUNTED_DEFAULT_CTOR(GroupInfoPair)
 
   MOZ_COUNTED_DTOR(GroupInfoPair)
 
  private:
-  already_AddRefed<GroupInfo> LockedGetGroupInfo(
-      PersistenceType aPersistenceType) {
+  RefPtr<GroupInfo> LockedGetGroupInfo(PersistenceType aPersistenceType) {
     AssertCurrentThreadOwnsQuotaMutex();
     MOZ_ASSERT(aPersistenceType != PERSISTENCE_TYPE_PERSISTENT);
 
-    RefPtr<GroupInfo> groupInfo =
-        GetGroupInfoForPersistenceType(aPersistenceType);
-    return groupInfo.forget();
+    return GetGroupInfoForPersistenceType(aPersistenceType);
   }
 
   void LockedSetGroupInfo(PersistenceType aPersistenceType,
                           GroupInfo* aGroupInfo) {
     AssertCurrentThreadOwnsQuotaMutex();
     MOZ_ASSERT(aPersistenceType != PERSISTENCE_TYPE_PERSISTENT);
 
     RefPtr<GroupInfo>& groupInfo =
@@ -3798,18 +3795,18 @@ uint64_t QuotaManager::CollectOriginsFor
             std::any_of(aLocks.begin(), aLocks.end(),
                         [&originScope](const DirectoryLockImpl* const lock) {
                           return originScope.Matches(lock->GetOriginScope());
                         });
 
         if (!match) {
           MOZ_ASSERT(!originInfo->mQuotaObjects.Count(),
                      "Inactive origin shouldn't have open files!");
-          aInactiveOriginInfos.InsertElementSorted(originInfo,
-                                                   OriginInfoLRUComparator());
+          aInactiveOriginInfos.InsertElementSorted(
+              originInfo, OriginInfoAccessTimeComparator());
         }
       }
     }
   };
 
   // Split locks into separate arrays and filter out locks for persistent
   // storage, they can't block us.
   nsTArray<NotNull<DirectoryLockImpl*>> temporaryStorageLocks;
@@ -7086,16 +7083,56 @@ already_AddRefed<OriginInfo> QuotaManage
     if (groupInfo) {
       return groupInfo->LockedGetOriginInfo(aGroupAndOrigin.mOrigin);
     }
   }
 
   return nullptr;
 }
 
+template <typename Iterator, typename Pred>
+void QuotaManager::MaybeInsertOriginInfos(
+    Iterator aDest, const RefPtr<GroupInfo>& aTemporaryGroupInfo,
+    const RefPtr<GroupInfo>& aDefaultGroupInfo, Pred&& aPred) {
+  const auto copy = [&aDest, &aPred](const GroupInfo& groupInfo) {
+    std::copy_if(groupInfo.mOriginInfos.cbegin(), groupInfo.mOriginInfos.cend(),
+                 aDest, aPred);
+  };
+
+  if (aTemporaryGroupInfo) {
+    MOZ_ASSERT(PERSISTENCE_TYPE_TEMPORARY ==
+               aTemporaryGroupInfo->GetPersistenceType());
+
+    copy(*aTemporaryGroupInfo);
+  }
+  if (aDefaultGroupInfo) {
+    MOZ_ASSERT(PERSISTENCE_TYPE_DEFAULT ==
+               aDefaultGroupInfo->GetPersistenceType());
+
+    copy(*aDefaultGroupInfo);
+  }
+}
+
+template <typename Collect, typename Pred>
+QuotaManager::OriginInfosFlatTraversable
+QuotaManager::CollectLRUOriginInfosUntil(Collect&& aCollect, Pred&& aPred) {
+  OriginInfosFlatTraversable originInfos;
+
+  std::forward<Collect>(aCollect)(MakeBackInserter(originInfos));
+
+  originInfos.Sort(OriginInfoAccessTimeComparator());
+
+  const auto foundIt = std::find_if(originInfos.cbegin(), originInfos.cend(),
+                                    std::forward<Pred>(aPred));
+
+  originInfos.TruncateLength(foundIt - originInfos.cbegin());
+
+  return originInfos;
+}
+
 QuotaManager::OriginInfosFlatTraversable
 QuotaManager::LockedGetOriginInfosExceedingGroupLimit() const {
   mQuotaMutex.AssertCurrentThreadOwns();
 
   OriginInfosFlatTraversable originInfos;
 
   for (const auto& entry : mGroupInfoPairs) {
     const auto& pair = entry.GetData();
@@ -7117,95 +7154,71 @@ QuotaManager::LockedGetOriginInfosExceed
       groupUsage += defaultGroupInfo->mUsage;
     }
 
     if (groupUsage > 0) {
       QuotaManager* quotaManager = QuotaManager::Get();
       MOZ_ASSERT(quotaManager, "Shouldn't be null!");
 
       if (groupUsage > quotaManager->GetGroupLimit()) {
-        const auto allOriginInfosLRUSorted = [&temporaryGroupInfo,
-                                              &defaultGroupInfo] {
-          OriginInfosFlatTraversable originInfos;
-          if (temporaryGroupInfo) {
-            originInfos.AppendElements(temporaryGroupInfo->mOriginInfos);
-          }
-          if (defaultGroupInfo) {
-            originInfos.AppendElements(defaultGroupInfo->mOriginInfos);
-          }
-          originInfos.Sort(OriginInfoLRUComparator());
-          return originInfos;
-        }();
-
-        for (const auto& originInfo : allOriginInfosLRUSorted) {
-          // XXX We can remove these before sorting and then just truncate the
-          // existing array at the right point.
-          if (originInfo->LockedPersisted()) {
-            continue;
-          }
-
-          originInfos.AppendElement(originInfo);
-          groupUsage -= originInfo->LockedUsage();
-
-          if (groupUsage <= quotaManager->GetGroupLimit()) {
-            break;
-          }
-        }
+        // XXX Instead of appending into a flat array, return an array of
+        // arrays.
+        originInfos.AppendElements(CollectLRUOriginInfosUntil(
+            [&temporaryGroupInfo, &defaultGroupInfo](auto inserter) {
+              MaybeInsertOriginInfos(std::move(inserter), temporaryGroupInfo,
+                                     defaultGroupInfo,
+                                     [](const auto& originInfo) {
+                                       return !originInfo->LockedPersisted();
+                                     });
+            },
+            [&groupUsage, quotaManager](const auto& originInfo) {
+              groupUsage -= originInfo->LockedUsage();
+
+              return groupUsage <= quotaManager->GetGroupLimit();
+            }));
       }
     }
   }
 
   return originInfos;
 }
 
 QuotaManager::OriginInfosFlatTraversable
 QuotaManager::LockedGetOriginInfosExceedingGlobalLimit(
     const OriginInfosFlatTraversable& aAlreadyDoomedOriginInfos,
     const uint64_t aAlreadyDoomedUsage) const {
   mQuotaMutex.AssertCurrentThreadOwns();
 
-  OriginInfosFlatTraversable originInfos;
-  for (const auto& entry : mGroupInfoPairs) {
-    const auto& pair = entry.GetData();
-
-    MOZ_ASSERT(!entry.GetKey().IsEmpty());
-    MOZ_ASSERT(pair);
-
-    RefPtr<GroupInfo> groupInfo =
-        pair->LockedGetGroupInfo(PERSISTENCE_TYPE_TEMPORARY);
-    if (groupInfo) {
-      originInfos.AppendElements(groupInfo->mOriginInfos);
-    }
-
-    groupInfo = pair->LockedGetGroupInfo(PERSISTENCE_TYPE_DEFAULT);
-    if (groupInfo) {
-      originInfos.AppendElements(groupInfo->mOriginInfos);
-    }
-  }
-
-  originInfos.RemoveElementsBy(
-      [&aAlreadyDoomedOriginInfos](const auto& originInfo) {
-        return aAlreadyDoomedOriginInfos.Contains(originInfo) ||
-               originInfo->LockedPersisted();
+  return CollectLRUOriginInfosUntil(
+      [this, &aAlreadyDoomedOriginInfos](auto inserter) {
+        for (const auto& entry : mGroupInfoPairs) {
+          const auto& pair = entry.GetData();
+
+          MOZ_ASSERT(!entry.GetKey().IsEmpty());
+          MOZ_ASSERT(pair);
+
+          MaybeInsertOriginInfos(
+              inserter, pair->LockedGetGroupInfo(PERSISTENCE_TYPE_TEMPORARY),
+              pair->LockedGetGroupInfo(PERSISTENCE_TYPE_DEFAULT),
+              [&aAlreadyDoomedOriginInfos](const auto& originInfo) {
+                return !aAlreadyDoomedOriginInfos.Contains(originInfo) &&
+                       !originInfo->LockedPersisted();
+              });
+        }
+      },
+      [temporaryStorageUsage = mTemporaryStorageUsage - aAlreadyDoomedUsage,
+       temporaryStorageLimit = mTemporaryStorageLimit,
+       doomedUsage = uint64_t{0}](const auto& originInfo) mutable {
+        if (temporaryStorageUsage - doomedUsage <= temporaryStorageLimit) {
+          return true;
+        }
+
+        doomedUsage += originInfo->LockedUsage();
+        return false;
       });
-
-  originInfos.Sort(OriginInfoLRUComparator());
-
-  uint64_t doomedUsage = 0;
-  for (uint32_t i = 0; i < originInfos.Length(); i++) {
-    if (mTemporaryStorageUsage - aAlreadyDoomedUsage - doomedUsage <=
-        mTemporaryStorageLimit) {
-      originInfos.TruncateLength(i);
-      break;
-    }
-
-    doomedUsage += originInfos[i]->LockedUsage();
-  }
-
-  return originInfos;
 }
 
 QuotaManager::OriginInfosFlatTraversable
 QuotaManager::GetOriginInfosExceedingLimits() const {
   MutexAutoLock lock(mQuotaMutex);
 
   auto originInfos = LockedGetOriginInfosExceedingGroupLimit();
 
--- a/dom/quota/QuotaManager.h
+++ b/dom/quota/QuotaManager.h
@@ -590,16 +590,25 @@ class QuotaManager final : public Backgr
 
   bool IsSanitizedOriginValid(const nsACString& aSanitizedOrigin);
 
   int64_t GenerateDirectoryLockId();
 
   void MaybeRecordShutdownStep(Maybe<Client::Type> aClientType,
                                const nsACString& aStepDescription);
 
+  template <typename Iterator, typename Pred>
+  static void MaybeInsertOriginInfos(
+      Iterator aDest, const RefPtr<GroupInfo>& aTemporaryGroupInfo,
+      const RefPtr<GroupInfo>& aDefaultGroupInfo, Pred&& aPred);
+
+  template <typename Collect, typename Pred>
+  static OriginInfosFlatTraversable CollectLRUOriginInfosUntil(
+      Collect&& aCollect, Pred&& aPred);
+
   // Thread on which IO is performed.
   LazyInitializedOnceNotNull<const nsCOMPtr<nsIThread>> mIOThread;
 
   nsCOMPtr<mozIStorageConnection> mStorageConnection;
 
   // A timer that gets activated at shutdown to ensure we close all storages.
   LazyInitializedOnceNotNull<const nsCOMPtr<nsITimer>> mShutdownTimer;