Bug 1546723 - Part 7: Fix ordering of items in special cases; r=asuth draft
authorJan Varga <jan.varga@gmail.com>
Wed, 15 May 2019 06:11:11 +0200
changeset 2008609 309c90d2fdeafa75e5e75a209f4a9b06e0bd7c16
parent 2008608 09948cf7595a69c4a9fb160d5de4cc614b9404c5
child 2008610 3ce1b3eb8cdf0eec839042d648280dfcafaabaf1
push id363926
push userjvarga@mozilla.com
push dateSat, 18 May 2019 08:19:45 +0000
treeherdertry@e89baae86dd1 [default view] [failures only]
reviewersasuth
bugs1546723
milestone68.0a1
Bug 1546723 - Part 7: Fix ordering of items in special cases; r=asuth Differential Revision: https://phabricator.services.mozilla.com/D31202
dom/localstorage/ActorsParent.cpp
dom/localstorage/LSSnapshot.cpp
dom/localstorage/LSWriteOptimizer.cpp
dom/localstorage/LSWriteOptimizer.h
dom/localstorage/test/unit/test_orderingAfterRemoveAdd.js
dom/localstorage/test/unit/test_snapshotting.js
dom/localstorage/test/unit/xpcshell.ini
--- a/dom/localstorage/ActorsParent.cpp
+++ b/dom/localstorage/ActorsParent.cpp
@@ -3698,33 +3698,41 @@ void DatastoreWriteOptimizer::ApplyAndRe
       switch (writeInfo->GetType()) {
         case WriteInfo::DeleteItem:
           aOrderedItems.RemoveElementAt(index);
           entry.Remove();
           break;
 
         case WriteInfo::UpdateItem: {
           auto updateItemInfo = static_cast<UpdateItemInfo*>(writeInfo);
-          item.value() = updateItemInfo->GetValue();
-          entry.Remove();
+          if (updateItemInfo->UpdateWithMove()) {
+            aOrderedItems.RemoveElementAt(index);
+            entry.Data() = new InsertItemInfo(updateItemInfo->SerialNumber(),
+                                              updateItemInfo->GetKey(),
+                                              updateItemInfo->GetValue());
+          } else {
+            item.value() = updateItemInfo->GetValue();
+            entry.Remove();
+          }
           break;
         }
 
         case WriteInfo::InsertItem:
           break;
 
         default:
           MOZ_CRASH("Bad type!");
       }
     }
   }
 
-  for (auto iter = mWriteInfos.ConstIter(); !iter.Done(); iter.Next()) {
-    WriteInfo* writeInfo = iter.Data();
-
+  nsTArray<WriteInfo*> writeInfos;
+  GetSortedWriteInfos(writeInfos);
+
+  for (WriteInfo* writeInfo : writeInfos) {
     MOZ_ASSERT(writeInfo->GetType() == WriteInfo::InsertItem);
 
     auto insertItemInfo = static_cast<InsertItemInfo*>(writeInfo);
 
     LSItemInfo* itemInfo = aOrderedItems.AppendElement();
     itemInfo->key() = insertItemInfo->GetKey();
     itemInfo->value() = insertItemInfo->GetValue();
   }
--- a/dom/localstorage/LSSnapshot.cpp
+++ b/dom/localstorage/LSSnapshot.cpp
@@ -27,50 +27,71 @@ class SnapshotWriteOptimizer final
     : public LSWriteOptimizer<nsAString, nsString> {
  public:
   void Enumerate(nsTArray<LSWriteInfo>& aWriteInfos);
 };
 
 void SnapshotWriteOptimizer::Enumerate(nsTArray<LSWriteInfo>& aWriteInfos) {
   AssertIsOnOwningThread();
 
-  if (mTruncateInfo) {
-    LSClearInfo clearInfo;
-
-    aWriteInfos.AppendElement(std::move(clearInfo));
-  }
+  nsTArray<WriteInfo*> writeInfos;
+  GetSortedWriteInfos(writeInfos);
 
-  for (auto iter = mWriteInfos.ConstIter(); !iter.Done(); iter.Next()) {
-    WriteInfo* writeInfo = iter.Data();
-
+  for (WriteInfo* writeInfo : writeInfos) {
     switch (writeInfo->GetType()) {
-      case WriteInfo::InsertItem:
-      case WriteInfo::UpdateItem: {
+      case WriteInfo::InsertItem: {
         auto insertItemInfo = static_cast<InsertItemInfo*>(writeInfo);
 
         LSSetItemInfo setItemInfo;
         setItemInfo.key() = insertItemInfo->GetKey();
         setItemInfo.value() = LSValue(insertItemInfo->GetValue());
 
         aWriteInfos.AppendElement(std::move(setItemInfo));
 
         break;
       }
 
+      case WriteInfo::UpdateItem: {
+        auto updateItemInfo = static_cast<UpdateItemInfo*>(writeInfo);
+
+        if (updateItemInfo->UpdateWithMove()) {
+          LSRemoveItemInfo removeItemInfo;
+          removeItemInfo.key() = updateItemInfo->GetKey();
+
+          aWriteInfos.AppendElement(std::move(removeItemInfo));
+        }
+
+        LSSetItemInfo setItemInfo;
+        setItemInfo.key() = updateItemInfo->GetKey();
+        setItemInfo.value() = LSValue(updateItemInfo->GetValue());
+
+        aWriteInfos.AppendElement(std::move(setItemInfo));
+
+        break;
+      }
+
       case WriteInfo::DeleteItem: {
         auto deleteItemInfo = static_cast<DeleteItemInfo*>(writeInfo);
 
         LSRemoveItemInfo removeItemInfo;
         removeItemInfo.key() = deleteItemInfo->GetKey();
 
         aWriteInfos.AppendElement(std::move(removeItemInfo));
 
         break;
       }
 
+      case WriteInfo::Truncate: {
+        LSClearInfo clearInfo;
+
+        aWriteInfos.AppendElement(std::move(clearInfo));
+
+        break;
+      }
+
       default:
         MOZ_CRASH("Bad type!");
     }
   }
 }
 
 LSSnapshot::LSSnapshot(LSDatabase* aDatabase)
     : mDatabase(aDatabase),
--- a/dom/localstorage/LSWriteOptimizer.cpp
+++ b/dom/localstorage/LSWriteOptimizer.cpp
@@ -4,73 +4,103 @@
  * 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 "LSWriteOptimizer.h"
 
 namespace mozilla {
 namespace dom {
 
+class LSWriteOptimizerBase::WriteInfoComparator {
+ public:
+  bool Equals(const WriteInfo* a, const WriteInfo* b) const {
+    return a && b ? a->SerialNumber() == b->SerialNumber()
+                  : !a && !b ? true : false;
+  }
+
+  bool LessThan(const WriteInfo* a, const WriteInfo* b) const {
+    return a && b ? a->SerialNumber() < b->SerialNumber() : b ? true : false;
+  }
+};
+
 void LSWriteOptimizerBase::DeleteItem(const nsAString& aKey, int64_t aDelta) {
   AssertIsOnOwningThread();
 
   WriteInfo* existingWriteInfo;
   if (mWriteInfos.Get(aKey, &existingWriteInfo) &&
       existingWriteInfo->GetType() == WriteInfo::InsertItem) {
     mWriteInfos.Remove(aKey);
   } else {
-    nsAutoPtr<WriteInfo> newWriteInfo(new DeleteItemInfo(aKey));
+    nsAutoPtr<WriteInfo> newWriteInfo(
+        new DeleteItemInfo(NextSerialNumber(), aKey));
     mWriteInfos.Put(aKey, newWriteInfo.forget());
   }
 
   mTotalDelta += aDelta;
 }
 
 void LSWriteOptimizerBase::Truncate(int64_t aDelta) {
   AssertIsOnOwningThread();
 
   mWriteInfos.Clear();
 
   if (!mTruncateInfo) {
-    mTruncateInfo = new TruncateInfo();
+    mTruncateInfo = new TruncateInfo(NextSerialNumber());
   }
 
   mTotalDelta += aDelta;
 }
 
+void LSWriteOptimizerBase::GetSortedWriteInfos(
+    nsTArray<WriteInfo*>& aWriteInfos) {
+  AssertIsOnOwningThread();
+
+  if (mTruncateInfo) {
+    aWriteInfos.InsertElementSorted(mTruncateInfo, WriteInfoComparator());
+  }
+
+  for (auto iter = mWriteInfos.ConstIter(); !iter.Done(); iter.Next()) {
+    WriteInfo* writeInfo = iter.Data();
+
+    aWriteInfos.InsertElementSorted(writeInfo, WriteInfoComparator());
+  }
+}
+
 template <typename T, typename U>
 void LSWriteOptimizer<T, U>::InsertItem(const nsAString& aKey, const T& aValue,
                                         int64_t aDelta) {
   AssertIsOnOwningThread();
 
   WriteInfo* existingWriteInfo;
   nsAutoPtr<WriteInfo> newWriteInfo;
   if (mWriteInfos.Get(aKey, &existingWriteInfo) &&
       existingWriteInfo->GetType() == WriteInfo::DeleteItem) {
-    newWriteInfo = new UpdateItemInfo(aKey, aValue);
+    newWriteInfo = new UpdateItemInfo(NextSerialNumber(), aKey, aValue,
+                                      /* aUpdateWithMove */ true);
   } else {
-    newWriteInfo = new InsertItemInfo(aKey, aValue);
+    newWriteInfo = new InsertItemInfo(NextSerialNumber(), aKey, aValue);
   }
   mWriteInfos.Put(aKey, newWriteInfo.forget());
 
   mTotalDelta += aDelta;
 }
 
 template <typename T, typename U>
 void LSWriteOptimizer<T, U>::UpdateItem(const nsAString& aKey, const T& aValue,
                                         int64_t aDelta) {
   AssertIsOnOwningThread();
 
   WriteInfo* existingWriteInfo;
   nsAutoPtr<WriteInfo> newWriteInfo;
   if (mWriteInfos.Get(aKey, &existingWriteInfo) &&
       existingWriteInfo->GetType() == WriteInfo::InsertItem) {
-    newWriteInfo = new InsertItemInfo(aKey, aValue);
+    newWriteInfo = new InsertItemInfo(NextSerialNumber(), aKey, aValue);
   } else {
-    newWriteInfo = new UpdateItemInfo(aKey, aValue);
+    newWriteInfo = new UpdateItemInfo(NextSerialNumber(), aKey, aValue,
+                                      /* aUpdateWithMove */ false);
   }
   mWriteInfos.Put(aKey, newWriteInfo.forget());
 
   mTotalDelta += aDelta;
 }
 
 }  // namespace dom
 }  // namespace mozilla
--- a/dom/localstorage/LSWriteOptimizer.h
+++ b/dom/localstorage/LSWriteOptimizer.h
@@ -2,36 +2,41 @@
 /* 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 mozilla_dom_localstorage_LSWriteOptimizer_h
 #define mozilla_dom_localstorage_LSWriteOptimizer_h
 
+#include "mozilla/CheckedInt.h"
+
 namespace mozilla {
 namespace dom {
 
 /**
  * Base class for coalescing manipulation queue.
  */
 class LSWriteOptimizerBase {
+  class WriteInfoComparator;
+
  protected:
   class WriteInfo;
   class DeleteItemInfo;
   class TruncateInfo;
 
   nsAutoPtr<WriteInfo> mTruncateInfo;
   nsClassHashtable<nsStringHashKey, WriteInfo> mWriteInfos;
+  CheckedUint64 mLastSerialNumber;
   int64_t mTotalDelta;
 
   NS_DECL_OWNINGTHREAD
 
  public:
-  LSWriteOptimizerBase() : mTotalDelta(0) {}
+  LSWriteOptimizerBase() : mLastSerialNumber(0), mTotalDelta(0) {}
 
   LSWriteOptimizerBase(LSWriteOptimizerBase&& aWriteOptimizer)
       : mTruncateInfo(std::move(aWriteOptimizer.mTruncateInfo)) {
     AssertIsOnOwningThread();
     MOZ_ASSERT(&aWriteOptimizer != this);
 
     mWriteInfos.SwapElements(aWriteOptimizer.mWriteInfos);
     mTotalDelta = aWriteOptimizer.mTotalDelta;
@@ -53,48 +58,68 @@ class LSWriteOptimizerBase {
   }
 
   void Reset() {
     AssertIsOnOwningThread();
 
     mTruncateInfo = nullptr;
     mWriteInfos.Clear();
   }
+
+ protected:
+  uint64_t NextSerialNumber() {
+    AssertIsOnOwningThread();
+
+    mLastSerialNumber++;
+
+    MOZ_ASSERT(mLastSerialNumber.isValid());
+
+    return mLastSerialNumber.value();
+  }
+
+  void GetSortedWriteInfos(nsTArray<WriteInfo*>& aWriteInfos);
 };
 
 /**
  * Base class for specific mutations.
  */
 class LSWriteOptimizerBase::WriteInfo {
+  uint64_t mSerialNumber;
+
  public:
+  WriteInfo(uint64_t aSerialNumber) : mSerialNumber(aSerialNumber) {}
+
   virtual ~WriteInfo() = default;
 
+  uint64_t SerialNumber() const { return mSerialNumber; }
+
   enum Type { InsertItem = 0, UpdateItem, DeleteItem, Truncate };
 
   virtual Type GetType() = 0;
 };
 
 class LSWriteOptimizerBase::DeleteItemInfo final : public WriteInfo {
   nsString mKey;
 
  public:
-  explicit DeleteItemInfo(const nsAString& aKey) : mKey(aKey) {}
+  DeleteItemInfo(uint64_t aSerialNumber, const nsAString& aKey)
+      : WriteInfo(aSerialNumber), mKey(aKey) {}
 
   const nsAString& GetKey() const { return mKey; }
 
  private:
   Type GetType() override { return DeleteItem; }
 };
 
 /**
  * Truncate mutation.
  */
 class LSWriteOptimizerBase::TruncateInfo final : public WriteInfo {
  public:
-  TruncateInfo() {}
+  explicit TruncateInfo(uint64_t aSerialNumber) : WriteInfo(aSerialNumber) {}
 
  private:
   Type GetType() override { return Truncate; }
 };
 
 /**
  * Coalescing manipulation queue.
  */
@@ -117,35 +142,41 @@ class LSWriteOptimizer : public LSWriteO
  * Insert mutation (the key did not previously exist).
  */
 template <typename T, typename U>
 class LSWriteOptimizer<T, U>::InsertItemInfo : public WriteInfo {
   nsString mKey;
   U mValue;
 
  public:
-  InsertItemInfo(const nsAString& aKey, const T& aValue)
-      : mKey(aKey), mValue(aValue) {}
+  InsertItemInfo(uint64_t aSerialNumber, const nsAString& aKey, const T& aValue)
+      : WriteInfo(aSerialNumber), mKey(aKey), mValue(aValue) {}
 
   const nsAString& GetKey() const { return mKey; }
 
   const T& GetValue() const { return mValue; }
 
  private:
   WriteInfo::Type GetType() override { return InsertItem; }
 };
 
 /**
  * Update mutation (the key already existed).
  */
 template <typename T, typename U>
 class LSWriteOptimizer<T, U>::UpdateItemInfo final : public InsertItemInfo {
+  bool mUpdateWithMove;
+
  public:
-  UpdateItemInfo(const nsAString& aKey, const T& aValue)
-      : InsertItemInfo(aKey, aValue) {}
+  UpdateItemInfo(uint64_t aSerialNumber, const nsAString& aKey, const T& aValue,
+                 bool aUpdateWithMove)
+      : InsertItemInfo(aSerialNumber, aKey, aValue),
+        mUpdateWithMove(aUpdateWithMove) {}
+
+  bool UpdateWithMove() const { return mUpdateWithMove; }
 
  private:
   WriteInfo::Type GetType() override { return WriteInfo::UpdateItem; }
 };
 
 }  // namespace dom
 }  // namespace mozilla
 
new file mode 100644
--- /dev/null
+++ b/dom/localstorage/test/unit/test_orderingAfterRemoveAdd.js
@@ -0,0 +1,70 @@
+/**
+ * Any copyright is dedicated to the Public Domain.
+ * http://creativecommons.org/publicdomain/zero/1.0/
+ */
+
+async function testSteps() {
+  const url = "http://example.com";
+
+  info("Setting pref");
+
+  Services.prefs.setBoolPref("dom.storage.snapshot_reusing", false);
+
+  const items = [
+    { key: "key01", value: "value01" },
+    { key: "key02", value: "value02" },
+    { key: "key03", value: "value03" },
+    { key: "key04", value: "value04" },
+    { key: "key05", value: "value05" },
+  ];
+
+  info("Getting storage");
+
+  let storage = getLocalStorage(getPrincipal(url));
+
+  // 1st snapshot
+
+  info("Adding data");
+
+  for (let item of items) {
+    storage.setItem(item.key, item.value);
+  }
+
+  info("Returning to event loop");
+
+  await returnToEventLoop();
+
+  // 2nd snapshot
+
+  // Remove first two items, add some new items and add the two items back.
+
+  storage.removeItem("key01");
+  storage.removeItem("key02");
+
+  storage.setItem("key06", "value06");
+  storage.setItem("key07", "value07");
+  storage.setItem("key08", "value08");
+
+  storage.setItem("key01", "value01");
+  storage.setItem("key02", "value02");
+
+  info("Saving key order");
+
+  let savedKeys = Object.keys(storage);
+
+  info("Returning to event loop");
+
+  await returnToEventLoop();
+
+  // 3rd snapshot
+
+  info("Verifying key order");
+
+  let keys = Object.keys(storage);
+
+  is(keys.length, savedKeys.length);
+
+  for (let i = 0; i < keys.length; i++) {
+    is(keys[i], savedKeys[i], "Correct key");
+  }
+}
--- a/dom/localstorage/test/unit/test_snapshotting.js
+++ b/dom/localstorage/test/unit/test_snapshotting.js
@@ -6,25 +6,25 @@
 async function testSteps() {
   const url = "http://example.com";
 
   info("Setting pref");
 
   Services.prefs.setBoolPref("dom.storage.snapshot_reusing", false);
 
   const items = [
-    { key: "key1", value: "value1" },
-    { key: "key2", value: "value2" },
-    { key: "key3", value: "value3" },
-    { key: "key4", value: "value4" },
-    { key: "key5", value: "value5" },
-    { key: "key6", value: "value6" },
-    { key: "key7", value: "value7" },
-    { key: "key8", value: "value8" },
-    { key: "key9", value: "value9" },
+    { key: "key01", value: "value01" },
+    { key: "key02", value: "value02" },
+    { key: "key03", value: "value03" },
+    { key: "key04", value: "value04" },
+    { key: "key05", value: "value05" },
+    { key: "key06", value: "value06" },
+    { key: "key07", value: "value07" },
+    { key: "key08", value: "value08" },
+    { key: "key09", value: "value09" },
     { key: "key10", value: "value10" },
   ];
 
   let sizeOfOneKey;
   let sizeOfOneValue;
   let sizeOfOneItem;
   let sizeOfKeys = 0;
   let sizeOfItems = 0;
@@ -189,24 +189,24 @@ async function testSteps() {
 
       info("Returning to event loop");
 
       await returnToEventLoop();
 
       // 3rd snapshot
 
       // Force key2 to load.
-      storage.getItem("key2");
+      storage.getItem("key02");
 
       // Fill out write infos a bit.
-      storage.removeItem("key5");
-      storage.setItem("key5", "value5");
-      storage.removeItem("key5");
+      storage.removeItem("key05");
+      storage.setItem("key05", "value05");
+      storage.removeItem("key05");
       storage.setItem("key11", "value11");
-      storage.setItem("key5", "value5");
+      storage.setItem("key05", "value05");
 
       items.push({ key: "key11", value: "value11" });
 
       info("Verifying length");
 
       is(storage.length, items.length, "Correct length");
 
       // This forces to get all keys from the parent and then apply write infos
--- a/dom/localstorage/test/unit/xpcshell.ini
+++ b/dom/localstorage/test/unit/xpcshell.ini
@@ -30,15 +30,16 @@ run-sequentially = this test depends on 
 [test_databaseShadowing_clearOriginsByPrefix1.js]
 run-sequentially = test_databaseShadowing_clearOriginsByPrefix2.js depends on a file produced by this test
 [test_databaseShadowing_clearOriginsByPrefix2.js]
 run-sequentially = this test depends on a file produced by test_databaseShadowing_clearOriginsByPrefix1.js
 [test_eviction.js]
 [test_groupLimit.js]
 [test_groupMismatch.js]
 [test_migration.js]
+[test_orderingAfterRemoveAdd.js]
 [test_originInit.js]
 [test_schema3upgrade.js]
 [test_snapshotting.js]
 requesttimeoutfactor = 4
 [test_stringLength.js]
 [test_stringLength2.js]
 [test_usage.js]