Bug 1483182 - Don't allocate in HashTable::lookupOrAdd(). r=luke
authorNicholas Nethercote <nnethercote@mozilla.com>
Tue, 21 Aug 2018 13:49:17 +1000
changeset 432749 8116d3ee3a5a5564eb0aae5cd2cea501e728deb9
parent 432748 33c2e19cd74f32c65bfd048a9cc8e732ff631ca0
child 432750 c3bb26f985552814f9e35639a15acd10a15878bb
push id106855
push usernnethercote@mozilla.com
push dateWed, 22 Aug 2018 06:55:19 +0000
treeherdermozilla-inbound@c3bb26f98555 [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewersluke
bugs1483182
milestone63.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 1483182 - Don't allocate in HashTable::lookupOrAdd(). r=luke Currently lookupOrAdd() will allocate if the table has no storage. But it doesn't report an error if the allocation fails, which can cause problems. This patch changes things so that lookupOrAdd() doesn't allocate when the table has no storage. Instead, it returns an AddPtr that is not *valid* (its mTable is empty) but it is *live*, and can be used in add(), whereupon the allocation will occur. The patch also makes Ptr::isValid() and AddPtr::isValid() non-public, because the valid vs. live distinction is non-obvious and best kept hidden within the classes.
js/src/ds/Bitmap.cpp
js/src/jit-test/tests/basic/bug1483182.js
js/src/jsapi-tests/testHashTable.cpp
mfbt/HashTable.h
--- a/js/src/ds/Bitmap.cpp
+++ b/js/src/ds/Bitmap.cpp
@@ -23,17 +23,17 @@ SparseBitmap::sizeOfExcludingThis(mozill
     for (Data::Range r(data.all()); !r.empty(); r.popFront())
         size += mallocSizeOf(r.front().value());
     return size;
 }
 
 SparseBitmap::BitBlock&
 SparseBitmap::createBlock(Data::AddPtr p, size_t blockId, AutoEnterOOMUnsafeRegion& oomUnsafe)
 {
-    MOZ_ASSERT(!p && p.isValid());
+    MOZ_ASSERT(!p);
     BitBlock* block = js_new<BitBlock>();
     if (!block || !data.add(p, blockId, block))
         oomUnsafe.crash("Bitmap OOM");
     std::fill(block->begin(), block->end(), 0);
     return *block;
 }
 
 bool
new file mode 100644
--- /dev/null
+++ b/js/src/jit-test/tests/basic/bug1483182.js
@@ -0,0 +1,15 @@
+var lfLogBuffer = `
+  function testOuterForInVar() {
+    return eval("for (var x in {}); (function() { return delete x; })");
+  }
+  testOuterForInVar();
+`;
+loadFile(lfLogBuffer);
+loadFile(lfLogBuffer);
+function loadFile(lfVarx) {
+    try {
+        oomTest(function() {
+            eval(lfVarx);
+        });
+    } catch (lfVare) {}
+}
--- a/js/src/jsapi-tests/testHashTable.cpp
+++ b/js/src/jsapi-tests/testHashTable.cpp
@@ -443,18 +443,44 @@ BEGIN_TEST(testHashLazyStorage)
 
     CHECK(set.putNew(1));
     CHECK(set.capacity() == minCap);
 
     set.clear();
     set.compact();
     CHECK(set.capacity() == 0);
 
-    // lookupForAdd() instantiates, even if not followed by add().
-    set.lookupForAdd(1);
+    auto p = set.lookupForAdd(1);
+    CHECK(set.capacity() == 0);
+    CHECK(set.add(p, 1));
+    CHECK(set.capacity() == minCap);
+    CHECK(set.has(1));
+
+    set.clear();
+    set.compact();
+    CHECK(set.capacity() == 0);
+
+    p = set.lookupForAdd(1);
+    CHECK(set.putNew(2));
+    CHECK(set.capacity() == minCap);
+    CHECK(set.relookupOrAdd(p, 1, 1));
+    CHECK(set.capacity() == minCap);
+    CHECK(set.has(1));
+
+    set.clear();
+    set.compact();
+    CHECK(set.capacity() == 0);
+
+    CHECK(set.putNew(1));
+    p = set.lookupForAdd(1);
+    set.clear();
+    set.compact();
+    CHECK(set.count() == 0);
+    CHECK(set.relookupOrAdd(p, 1, 1));
+    CHECK(set.count() == 1);
     CHECK(set.capacity() == minCap);
 
     set.clear();
     set.compact();
     CHECK(set.capacity() == 0);
 
     CHECK(set.reserve(0));          // a no-op
     CHECK(set.capacity() == 0);
--- a/mfbt/HashTable.h
+++ b/mfbt/HashTable.h
@@ -1204,28 +1204,38 @@ public:
       : mEntry(&aEntry)
 #ifdef DEBUG
       , mTable(&aTable)
       , mGeneration(aTable.generation())
 #endif
     {
     }
 
+    // This constructor is used only by AddPtr() within lookupForAdd().
+    explicit Ptr(const HashTable& aTable)
+      : mEntry(nullptr)
+#ifdef DEBUG
+      , mTable(&aTable)
+      , mGeneration(aTable.generation())
+#endif
+    {
+    }
+
+    bool isValid() const { return !!mEntry; }
+
   public:
     Ptr()
       : mEntry(nullptr)
 #ifdef DEBUG
       , mTable(nullptr)
       , mGeneration(0)
 #endif
     {
     }
 
-    bool isValid() const { return !!mEntry; }
-
     bool found() const
     {
       if (!isValid()) {
         return false;
       }
 #ifdef DEBUG
       MOZ_ASSERT(mGeneration == mTable->generation());
 #endif
@@ -1281,16 +1291,31 @@ public:
       : Ptr(aEntry, aTable)
       , mKeyHash(aHashNumber)
 #ifdef DEBUG
       , mMutationCount(aTable.mMutationCount)
 #endif
     {
     }
 
+    // This constructor is used when lookupForAdd() is performed on a table
+    // lacking entry storage; it leaves mEntry null but initializes everything
+    // else.
+    AddPtr(const HashTable& aTable, HashNumber aHashNumber)
+      : Ptr(aTable)
+      , mKeyHash(aHashNumber)
+#ifdef DEBUG
+      , mMutationCount(aTable.mMutationCount)
+#endif
+    {
+      MOZ_ASSERT(isLive());
+    }
+
+    bool isLive() const { return isLiveHash(mKeyHash); }
+
   public:
     AddPtr()
       : mKeyHash(0)
     {
     }
   };
 
   // A hash table iterator that (mostly) doesn't allow table modifications.
@@ -2102,59 +2127,66 @@ public:
 
   MOZ_ALWAYS_INLINE AddPtr lookupForAdd(const Lookup& aLookup)
   {
     ReentrancyGuard g(*this);
     if (!EnsureHash<HashPolicy>(aLookup)) {
       return AddPtr();
     }
 
+    HashNumber keyHash = prepareHash(aLookup);
+
     if (!mTable) {
-      uint32_t newCapacity = rawCapacity();
-      RebuildStatus status = changeTableSize(newCapacity, ReportFailure);
-      MOZ_ASSERT(status != NotOverloaded);
-      if (status == RehashFailed) {
-        return AddPtr();
-      }
+      return AddPtr(*this, keyHash);
     }
 
-    HashNumber keyHash = prepareHash(aLookup);
     // Directly call the constructor in the return statement to avoid
     // excess copying when building with Visual Studio 2017.
     // See bug 1385181.
     return AddPtr(lookup<ForAdd>(aLookup, keyHash), *this, keyHash);
   }
 
   template<typename... Args>
   MOZ_MUST_USE bool add(AddPtr& aPtr, Args&&... aArgs)
   {
     ReentrancyGuard g(*this);
     MOZ_ASSERT_IF(aPtr.isValid(), mTable);
     MOZ_ASSERT_IF(aPtr.isValid(), aPtr.mTable == this);
     MOZ_ASSERT(!aPtr.found());
     MOZ_ASSERT(!(aPtr.mKeyHash & sCollisionBit));
 
     // Check for error from ensureHash() here.
-    if (!aPtr.isValid()) {
+    if (!aPtr.isLive()) {
       return false;
     }
 
     MOZ_ASSERT(aPtr.mGeneration == generation());
 #ifdef DEBUG
     MOZ_ASSERT(aPtr.mMutationCount == mMutationCount);
 #endif
 
-    // Changing an entry from removed to live does not affect whether we
-    // are overloaded and can be handled separately.
-    if (aPtr.mEntry->isRemoved()) {
+    if (!aPtr.isValid()) {
+      MOZ_ASSERT(!mTable && mEntryCount == 0);
+      uint32_t newCapacity = rawCapacity();
+      RebuildStatus status = changeTableSize(newCapacity, ReportFailure);
+      MOZ_ASSERT(status != NotOverloaded);
+      if (status == RehashFailed) {
+        return false;
+      }
+      aPtr.mEntry = &findNonLiveEntry(aPtr.mKeyHash);
+
+    } else if (aPtr.mEntry->isRemoved()) {
+      // Changing an entry from removed to live does not affect whether we are
+      // overloaded and can be handled separately.
       if (!this->checkSimulatedOOM()) {
         return false;
       }
       mRemovedCount--;
       aPtr.mKeyHash |= sCollisionBit;
+
     } else {
       // Preserve the validity of |aPtr.mEntry|.
       RebuildStatus status = rehashIfOverloaded();
       if (status == RehashFailed) {
         return false;
       }
       if (status == NotOverloaded && !this->checkSimulatedOOM()) {
         return false;
@@ -2205,30 +2237,37 @@ public:
   // Note: |aLookup| may be a reference to a piece of |u|, so this function
   // must take care not to use |aLookup| after moving |u|.
   template<typename... Args>
   MOZ_MUST_USE bool relookupOrAdd(AddPtr& aPtr,
                                   const Lookup& aLookup,
                                   Args&&... aArgs)
   {
     // Check for error from ensureHash() here.
-    if (!aPtr.isValid()) {
+    if (!aPtr.isLive()) {
       return false;
     }
 #ifdef DEBUG
     aPtr.mGeneration = generation();
     aPtr.mMutationCount = mMutationCount;
 #endif
-    {
+    if (mTable) {
       ReentrancyGuard g(*this);
       // Check that aLookup has not been destroyed.
       MOZ_ASSERT(prepareHash(aLookup) == aPtr.mKeyHash);
       aPtr.mEntry = &lookup<ForAdd>(aLookup, aPtr.mKeyHash);
+      if (aPtr.found()) {
+        return true;
+      }
+    } else {
+      // Clear aPtr so it's invalid; add() will allocate storage and redo the
+      // lookup.
+      aPtr.mEntry = nullptr;
     }
-    return aPtr.found() || add(aPtr, std::forward<Args>(aArgs)...);
+    return add(aPtr, std::forward<Args>(aArgs)...);
   }
 
   void remove(Ptr aPtr)
   {
     MOZ_ASSERT(mTable);
     ReentrancyGuard g(*this);
     MOZ_ASSERT(aPtr.found());
     MOZ_ASSERT(aPtr.mGeneration == generation());