Bug 1530311 - Add a length check to HashTable::reserve(). r=luke
authorNicholas Nethercote <nnethercote@mozilla.com>
Wed, 27 Feb 2019 00:08:13 +0000
changeset 519160 b4cc238408111d01cf9230debb2bf0c6cb235c92
parent 519159 8f0627e655a9a1aacce3134cc848fc9c81916d4a
child 519161 b3e646df6c5e74f625bae22528ab6a6ff739033f
push id10862
push userffxbld-merge
push dateMon, 11 Mar 2019 13:01:11 +0000
treeherdermozilla-beta@a2e7f5c935da [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewersluke
bugs1530311
milestone67.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 1530311 - Add a length check to HashTable::reserve(). r=luke Also add an assertion to a similar function in PLDHashTable.cpp. Differential Revision: https://phabricator.services.mozilla.com/D21167
js/src/jsapi-tests/testHashTable.cpp
mfbt/HashTable.h
xpcom/ds/PLDHashTable.cpp
--- a/js/src/jsapi-tests/testHashTable.cpp
+++ b/js/src/jsapi-tests/testHashTable.cpp
@@ -518,11 +518,18 @@ BEGIN_TEST(testHashLazyStorage) {
   }
   CHECK(set.count() == 16);
   CHECK(set.capacity() == 32);
   set.clear();
   CHECK(set.capacity() == 32);
   set.compact();
   CHECK(set.capacity() == 0);
 
+  // Lowest length for which reserve() will fail.
+  static const uint32_t toobig = (1 << 29) + 1;
+  CHECK(!set.reserve(toobig));
+  CHECK(set.capacity() == 0);  // unchanged
+  CHECK(set.reserve(16));
+  CHECK(set.capacity() == 32);
+
   return true;
 }
 END_TEST(testHashLazyStorage)
--- a/mfbt/HashTable.h
+++ b/mfbt/HashTable.h
@@ -1564,16 +1564,19 @@ class HashTable : private AllocPolicy {
   static uint32_t bestCapacity(uint32_t aLen) {
     static_assert(
         (sMaxInit * sAlphaDenominator) / sAlphaDenominator == sMaxInit,
         "multiplication in numerator below could overflow");
     static_assert(
         sMaxInit * sAlphaDenominator <= UINT32_MAX - sMaxAlphaNumerator,
         "numerator calculation below could potentially overflow");
 
+    // Callers should ensure this is true.
+    MOZ_ASSERT(aLen <= sMaxInit);
+
     // Compute the smallest capacity allowing |aLen| elements to be
     // inserted without rehashing: ceil(aLen / max-alpha).  (Ceiling
     // integral division: <http://stackoverflow.com/a/2745086>.)
     uint32_t capacity = (aLen * sAlphaDenominator + sMaxAlphaNumerator - 1) /
                         sMaxAlphaNumerator;
     capacity = (capacity < sMinCapacity) ? sMinCapacity : RoundUpPow2(capacity);
 
     MOZ_ASSERT(capacity >= aLen);
@@ -1983,16 +1986,20 @@ class HashTable : private AllocPolicy {
     compact();
   }
 
   MOZ_MUST_USE bool reserve(uint32_t aLen) {
     if (aLen == 0) {
       return true;
     }
 
+    if (MOZ_UNLIKELY(aLen > sMaxInit)) {
+      return false;
+    }
+
     uint32_t bestCapacity = this->bestCapacity(aLen);
     if (bestCapacity <= capacity()) {
       return true;  // Capacity is already sufficient.
     }
 
     RebuildStatus status = changeTableSize(bestCapacity, ReportFailure);
     MOZ_ASSERT(status != NotOverloaded);
     return status != RehashFailed;
--- a/xpcom/ds/PLDHashTable.cpp
+++ b/xpcom/ds/PLDHashTable.cpp
@@ -130,16 +130,19 @@ static inline uint32_t MinLoad(uint32_t 
 
 // Compute the minimum capacity (and the Log2 of that capacity) for a table
 // containing |aLength| elements while respecting the following contraints:
 // - table must be at most 75% full;
 // - capacity must be a power of two;
 // - capacity cannot be too small.
 static inline void BestCapacity(uint32_t aLength, uint32_t* aCapacityOut,
                                 uint32_t* aLog2CapacityOut) {
+  // Callers should ensure this is true.
+  MOZ_ASSERT(aLength <= PLDHashTable::kMaxInitialLength);
+
   // Compute the smallest capacity allowing |aLength| elements to be inserted
   // without rehashing.
   uint32_t capacity = (aLength * 4 + (3 - 1)) / 3;  // == ceil(aLength * 4 / 3)
   if (capacity < PLDHashTable::kMinCapacity) {
     capacity = PLDHashTable::kMinCapacity;
   }
 
   // Round up capacity to next power-of-two.