Bug 1685677 - Don't unnecessarily materialize a flattened array of OriginInfo*. r=dom-workers-and-storage-reviewers,janv
☠☠ backed out by b10d7b687fd4 ☠ ☠
authorSimon Giesecke <sgiesecke@mozilla.com>
Tue, 02 Feb 2021 11:33:52 +0000
changeset 565599 e3223c39895961b01363017131a1dae57f7be7a5
parent 565598 d1fbaf6882a3a9b01dd26323495e9dcf0ff2629d
child 565600 0110eb26213b9498d9695866275847cdbece4c69
push id135520
push usersgiesecke@mozilla.com
push dateTue, 02 Feb 2021 12:18:25 +0000
treeherderautoland@0110eb26213b [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 - Don't unnecessarily materialize a flattened array of OriginInfo*. r=dom-workers-and-storage-reviewers,janv Differential Revision: https://phabricator.services.mozilla.com/D101151
dom/quota/ActorsParent.cpp
dom/quota/Flatten.h
dom/quota/QuotaManager.h
dom/quota/test/gtest/TestFlatten.cpp
dom/quota/test/gtest/moz.build
--- a/dom/quota/ActorsParent.cpp
+++ b/dom/quota/ActorsParent.cpp
@@ -2,16 +2,17 @@
 /* vim: set ts=8 sts=2 et sw=2 tw=80: */
 /* This Source Code Form is subject to the terms of the Mozilla Public
  * License, v. 2.0. If a copy of the MPL was not distributed with this file,
  * You can obtain one at http://mozilla.org/MPL/2.0/. */
 
 #include "ActorsParent.h"
 
 // Local includes
+#include "Flatten.h"
 #include "InitializationTypes.h"
 #include "OriginScope.h"
 #include "QuotaCommon.h"
 #include "QuotaManager.h"
 #include "QuotaObject.h"
 #include "UsageInfo.h"
 
 // Global includes
@@ -7123,21 +7124,21 @@ QuotaManager::CollectLRUOriginInfosUntil
   const auto foundIt = std::find_if(originInfos.cbegin(), originInfos.cend(),
                                     std::forward<Pred>(aPred));
 
   originInfos.TruncateLength(foundIt - originInfos.cbegin());
 
   return originInfos;
 }
 
-QuotaManager::OriginInfosFlatTraversable
+QuotaManager::OriginInfosNestedTraversable
 QuotaManager::LockedGetOriginInfosExceedingGroupLimit() const {
   mQuotaMutex.AssertCurrentThreadOwns();
 
-  OriginInfosFlatTraversable originInfos;
+  OriginInfosNestedTraversable originInfos;
 
   for (const auto& entry : mGroupInfoPairs) {
     const auto& pair = entry.GetData();
 
     MOZ_ASSERT(!entry.GetKey().IsEmpty());
     MOZ_ASSERT(pair);
 
     uint64_t groupUsage = 0;
@@ -7154,19 +7155,17 @@ QuotaManager::LockedGetOriginInfosExceed
       groupUsage += defaultGroupInfo->mUsage;
     }
 
     if (groupUsage > 0) {
       QuotaManager* quotaManager = QuotaManager::Get();
       MOZ_ASSERT(quotaManager, "Shouldn't be null!");
 
       if (groupUsage > quotaManager->GetGroupLimit()) {
-        // XXX Instead of appending into a flat array, return an array of
-        // arrays.
-        originInfos.AppendElements(CollectLRUOriginInfosUntil(
+        originInfos.AppendElement(CollectLRUOriginInfosUntil(
             [&temporaryGroupInfo, &defaultGroupInfo](auto inserter) {
               MaybeInsertOriginInfos(std::move(inserter), temporaryGroupInfo,
                                      defaultGroupInfo,
                                      [](const auto& originInfo) {
                                        return !originInfo->LockedPersisted();
                                      });
             },
             [&groupUsage, quotaManager](const auto& originInfo) {
@@ -7178,81 +7177,90 @@ QuotaManager::LockedGetOriginInfosExceed
     }
   }
 
   return originInfos;
 }
 
 QuotaManager::OriginInfosFlatTraversable
 QuotaManager::LockedGetOriginInfosExceedingGlobalLimit(
-    const OriginInfosFlatTraversable& aAlreadyDoomedOriginInfos,
+    const OriginInfosNestedTraversable& aAlreadyDoomedOriginInfos,
     const uint64_t aAlreadyDoomedUsage) const {
   mQuotaMutex.AssertCurrentThreadOwns();
 
   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) &&
+                return !std::any_of(aAlreadyDoomedOriginInfos.cbegin(),
+                                    aAlreadyDoomedOriginInfos.cend(),
+                                    // XXX This should capture originInfo by
+                                    // value, but it can't due to Bug 1421435.
+                                    [&originInfo](const auto& array) {
+                                      return array.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;
       });
 }
 
-QuotaManager::OriginInfosFlatTraversable
+QuotaManager::OriginInfosNestedTraversable
 QuotaManager::GetOriginInfosExceedingLimits() const {
   MutexAutoLock lock(mQuotaMutex);
 
   auto originInfos = LockedGetOriginInfosExceedingGroupLimit();
 
-  const uint64_t doomedUsage =
-      std::accumulate(originInfos.cbegin(), originInfos.cend(), uint64_t(0),
-                      [](uint64_t oldValue, const auto& originInfo) {
-                        return oldValue + originInfo->LockedUsage();
-                      });
+  const uint64_t doomedUsage = std::accumulate(
+      originInfos.cbegin(), originInfos.cend(), uint64_t(0),
+      [](uint64_t oldValue, const auto& currentOriginInfos) {
+        return std::accumulate(currentOriginInfos.cbegin(),
+                               currentOriginInfos.cend(), oldValue,
+                               [](uint64_t oldValue, const auto& originInfo) {
+                                 return oldValue + originInfo->LockedUsage();
+                               });
+      });
 
   // Evicting origins that exceed their group limit also affects the global
   // temporary storage usage. If the global temporary storage limit would still
   // be exceeded after evicting the origins that were already selected, we need
   // to specifically evict origins to get below the global limit.
   if (mTemporaryStorageUsage - doomedUsage > mTemporaryStorageLimit) {
-    originInfos.AppendElements(
+    originInfos.AppendElement(
         LockedGetOriginInfosExceedingGlobalLimit(originInfos, doomedUsage));
   }
 
   return originInfos;
 }
 
 void QuotaManager::ClearOrigins(
-    const OriginInfosFlatTraversable& aDoomedOriginInfos) {
+    const OriginInfosNestedTraversable& aDoomedOriginInfos) {
   AssertIsOnIOThread();
 
   // XXX Does this need to be done a) in order and/or b) sequentially?
-  // XXX We don't need to concatenate the results of the two steps. It would be
-  // sufficient to chain the ranges for iteration.
-  for (const auto& doomedOriginInfo : aDoomedOriginInfos) {
+  for (const auto& doomedOriginInfo :
+       Flatten<OriginInfosFlatTraversable::elem_type>(aDoomedOriginInfos)) {
 #ifdef DEBUG
     {
       MutexAutoLock lock(mQuotaMutex);
       MOZ_ASSERT(!doomedOriginInfo->LockedPersisted());
     }
 #endif
 
     DeleteFilesForOrigin(doomedOriginInfo->mGroupInfo->mPersistenceType,
@@ -7264,17 +7272,18 @@ void QuotaManager::ClearOrigins(
     PersistenceType mPersistenceType;
   };
 
   nsTArray<OriginParams> clearedOrigins;
 
   {
     MutexAutoLock lock(mQuotaMutex);
 
-    for (const auto& doomedOriginInfo : aDoomedOriginInfos) {
+    for (const auto& doomedOriginInfo :
+         Flatten<OriginInfosFlatTraversable::elem_type>(aDoomedOriginInfos)) {
       // LockedRemoveQuotaForOrigin might remove the group info;
       // OriginInfo::mGroupInfo is only a raw pointer, so we need to store the
       // information for calling OriginClearCompleted below in a separate array.
       clearedOrigins.AppendElement(
           OriginParams{doomedOriginInfo->mOrigin,
                        doomedOriginInfo->mGroupInfo->mPersistenceType});
 
       LockedRemoveQuotaForOrigin(
new file mode 100644
--- /dev/null
+++ b/dom/quota/Flatten.h
@@ -0,0 +1,118 @@
+/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
+/* vim: set ts=8 sts=2 et sw=2 tw=80: */
+/* This Source Code Form is subject to the terms of the Mozilla Public
+ * License, v. 2.0. If a copy of the MPL was not distributed with this file,
+ * You can obtain one at http://mozilla.org/MPL/2.0/. */
+
+#ifndef DOM_QUOTA_FLATTEN_H_
+#define DOM_QUOTA_FLATTEN_H_
+
+#include <iterator>
+#include <type_traits>
+#include <utility>
+
+// XXX This should be moved to MFBT.
+
+namespace mozilla::dom::quota {
+
+namespace detail {
+
+using std::begin;
+using std::end;
+
+template <typename T, typename NestedRange>
+auto Flatten(NestedRange&& aRange) -> std::enable_if_t<
+    std::is_same_v<T, std::decay_t<typename decltype(begin(
+                          std::declval<const NestedRange&>()))::value_type>>,
+    std::conditional_t<std::is_rvalue_reference_v<NestedRange>,
+                       std::decay_t<NestedRange>, NestedRange>> {
+  return std::forward<NestedRange>(aRange);
+}
+
+template <typename T, typename NestedRange>
+struct FlatIter {
+  using OuterIterator =
+      decltype(begin(std::declval<const std::decay_t<NestedRange>&>()));
+  using InnerIterator =
+      decltype(begin(*begin(std::declval<const std::decay_t<NestedRange>&>())));
+
+  explicit FlatIter(const NestedRange& aRange, OuterIterator aIter)
+      : mOuterIter{std::move(aIter)}, mOuterEnd{end(aRange)} {
+    InitInner();
+  }
+
+  const T& operator*() const { return *mInnerIter; }
+
+  FlatIter& operator++() {
+    ++mInnerIter;
+    if (mInnerIter == mInnerEnd) {
+      ++mOuterIter;
+      InitInner();
+    }
+    return *this;
+  }
+
+  bool operator!=(const FlatIter& aOther) const {
+    return mOuterIter != aOther.mOuterIter ||
+           (mOuterIter != mOuterEnd && mInnerIter != aOther.mInnerIter);
+  }
+
+ private:
+  void InitInner() {
+    while (mOuterIter != mOuterEnd) {
+      const typename OuterIterator::value_type& innerRange = *mOuterIter;
+
+      mInnerIter = begin(innerRange);
+      mInnerEnd = end(innerRange);
+
+      if (mInnerIter != mInnerEnd) {
+        break;
+      }
+
+      ++mOuterIter;
+    }
+  }
+
+  OuterIterator mOuterIter;
+  const OuterIterator mOuterEnd;
+
+  InnerIterator mInnerIter;
+  InnerIterator mInnerEnd;
+};
+
+template <typename T, typename NestedRange>
+struct FlatRange {
+  explicit FlatRange(NestedRange aRange) : mRange{std::move(aRange)} {}
+
+  auto begin() const {
+    using std::begin;
+    return FlatIter<T, NestedRange>{mRange, begin(mRange)};
+  }
+  auto end() const {
+    using std::end;
+    return FlatIter<T, NestedRange>{mRange, end(mRange)};
+  }
+
+ private:
+  NestedRange mRange;
+};
+
+template <typename T, typename NestedRange>
+auto Flatten(NestedRange&& aRange) -> std::enable_if_t<
+    !std::is_same_v<
+        T, std::decay_t<typename decltype(begin(
+               std::declval<const std::decay_t<NestedRange>&>()))::value_type>>,
+    FlatRange<T, NestedRange>> {
+  return FlatRange<T, NestedRange>{std::forward<NestedRange>(aRange)};
+}
+
+}  // namespace detail
+
+template <typename T, typename NestedRange>
+auto Flatten(NestedRange&& aRange) -> decltype(auto) {
+  return detail::Flatten<T>(std::forward<NestedRange>(aRange));
+}
+
+}  // namespace mozilla::dom::quota
+
+#endif
--- a/dom/quota/QuotaManager.h
+++ b/dom/quota/QuotaManager.h
@@ -556,25 +556,28 @@ class QuotaManager final : public Backgr
   nsresult InitializeOrigin(PersistenceType aPersistenceType,
                             const GroupAndOrigin& aGroupAndOrigin,
                             int64_t aAccessTime, bool aPersisted,
                             nsIFile* aDirectory);
 
   using OriginInfosFlatTraversable =
       nsTArray<NotNull<RefPtr<const OriginInfo>>>;
 
-  OriginInfosFlatTraversable LockedGetOriginInfosExceedingGroupLimit() const;
+  using OriginInfosNestedTraversable =
+      nsTArray<nsTArray<NotNull<RefPtr<const OriginInfo>>>>;
+
+  OriginInfosNestedTraversable LockedGetOriginInfosExceedingGroupLimit() const;
 
   OriginInfosFlatTraversable LockedGetOriginInfosExceedingGlobalLimit(
-      const OriginInfosFlatTraversable& aAlreadyDoomedOriginInfos,
+      const OriginInfosNestedTraversable& aAlreadyDoomedOriginInfos,
       uint64_t aAlreadyDoomedUsage) const;
 
-  OriginInfosFlatTraversable GetOriginInfosExceedingLimits() const;
+  OriginInfosNestedTraversable GetOriginInfosExceedingLimits() const;
 
-  void ClearOrigins(const OriginInfosFlatTraversable& aDoomedOriginInfos);
+  void ClearOrigins(const OriginInfosNestedTraversable& aDoomedOriginInfos);
 
   void CleanupTemporaryStorage();
 
   void DeleteFilesForOrigin(PersistenceType aPersistenceType,
                             const nsACString& aOrigin);
 
   void FinalizeOriginEviction(nsTArray<RefPtr<DirectoryLockImpl>>&& aLocks);
 
new file mode 100644
--- /dev/null
+++ b/dom/quota/test/gtest/TestFlatten.cpp
@@ -0,0 +1,74 @@
+/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
+/* vim: set ts=8 sts=2 et sw=2 tw=80: */
+/* This Source Code Form is subject to the terms of the Mozilla Public
+ * License, v. 2.0. If a copy of the MPL was not distributed with this file,
+ * You can obtain one at http://mozilla.org/MPL/2.0/. */
+
+#include "Flatten.h"
+
+#include "gtest/gtest.h"
+
+#include "mozilla/Unused.h"
+#include "nsTArray.h"
+
+namespace mozilla::dom::quota {
+
+TEST(Flatten, FlatEmpty)
+{
+  for (const auto& item : Flatten<int>(nsTArray<int>{})) {
+    Unused << item;
+    FAIL();
+  }
+}
+
+TEST(Flatten, NestedOuterEmpty)
+{
+  for (const auto& item : Flatten<int>(nsTArray<CopyableTArray<int>>{})) {
+    Unused << item;
+    FAIL();
+  }
+}
+
+TEST(Flatten, NestedInnerEmpty)
+{
+  for (const auto& item :
+       Flatten<int>(nsTArray<CopyableTArray<int>>{CopyableTArray<int>{}})) {
+    Unused << item;
+    FAIL();
+  }
+}
+
+TEST(Flatten, NestedInnerSingular)
+{
+  nsTArray<int> flattened;
+  for (const auto& item :
+       Flatten<int>(nsTArray<CopyableTArray<int>>{CopyableTArray<int>{1}})) {
+    flattened.AppendElement(item);
+  }
+
+  EXPECT_EQ(nsTArray{1}, flattened);
+}
+
+TEST(Flatten, NestedInnerSingulars)
+{
+  nsTArray<int> flattened;
+  for (const auto& item : Flatten<int>(nsTArray<CopyableTArray<int>>{
+           CopyableTArray<int>{1}, CopyableTArray<int>{2}})) {
+    flattened.AppendElement(item);
+  }
+
+  EXPECT_EQ((nsTArray{1, 2}), flattened);
+}
+
+TEST(Flatten, NestedInnerNonSingulars)
+{
+  nsTArray<int> flattened;
+  for (const auto& item : Flatten<int>(nsTArray<CopyableTArray<int>>{
+           CopyableTArray<int>{1, 2}, CopyableTArray<int>{3, 4}})) {
+    flattened.AppendElement(item);
+  }
+
+  EXPECT_EQ((nsTArray{1, 2, 3, 4}), flattened);
+}
+
+}  // namespace mozilla::dom::quota
--- a/dom/quota/test/gtest/moz.build
+++ b/dom/quota/test/gtest/moz.build
@@ -2,16 +2,17 @@
 # vim: set filetype=python:
 # This Source Code Form is subject to the terms of the Mozilla Public
 # License, v. 2.0. If a copy of the MPL was not distributed with this
 # file, you can obtain one at http://mozilla.org/MPL/2.0/.
 
 UNIFIED_SOURCES = [
     "TestCheckedUnsafePtr.cpp",
     "TestEncryptedStream.cpp",
+    "TestFlatten.cpp",
     "TestQuotaCommon.cpp",
     "TestQuotaManager.cpp",
     "TestUsageInfo.cpp",
 ]
 
 include("/ipc/chromium/chromium-config.mozbuild")
 
 FINAL_LIBRARY = "xul-gtest"