Bug 678362 - HashTable should not require callers to bounds-check initial capacity (r=waldo)
authorLuke Wagner <luke@mozilla.com>
Thu, 11 Aug 2011 18:10:16 -0700
changeset 76828 796b8466d549dc5db8df06f33210f8a1f02aaaf2
parent 76827 5bbc3615e3877e0d3fb047263cc995bc72e9cb73
child 76829 73aafae10571356aa17af47e922f1af6118de217
push id78
push userclegnitto@mozilla.com
push dateFri, 16 Dec 2011 17:32:24 +0000
treeherdermozilla-release@79d24e644fdd [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewerswaldo
bugs678362
milestone9.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 678362 - HashTable should not require callers to bounds-check initial capacity (r=waldo)
js/src/jit-test/tests/basic/bug666448.js
js/src/jshashtable.h
js/src/tests/ecma_5/extensions/JSON-string-replacer-overflow.js
js/src/tests/ecma_5/extensions/jstests.list
--- a/js/src/jshashtable.h
+++ b/js/src/jshashtable.h
@@ -293,26 +293,35 @@ class HashTable : private AllocPolicy
 #ifdef DEBUG
     friend class js::ReentrancyGuard;
     mutable bool entered;
     uint64       mutationCount;
 #endif
 
     static const unsigned sMinSizeLog2  = 4;
     static const unsigned sMinSize      = 1 << sMinSizeLog2;
-    static const unsigned sSizeLimit    = JS_BIT(24);
+    static const unsigned sMaxInit      = JS_BIT(23);
+    static const unsigned sMaxCapacity  = JS_BIT(24);
     static const unsigned sHashBits     = tl::BitSize<HashNumber>::result;
     static const uint8    sMinAlphaFrac = 64;  /* (0x100 * .25) taken from jsdhash.h */
     static const uint8    sMaxAlphaFrac = 192; /* (0x100 * .75) taken from jsdhash.h */
     static const uint8    sInvMaxAlpha  = 171; /* (ceil(0x100 / .75) >> 1) */
     static const HashNumber sGoldenRatio  = 0x9E3779B9U;       /* taken from jsdhash.h */
     static const HashNumber sFreeKey = Entry::sFreeKey;
     static const HashNumber sRemovedKey = Entry::sRemovedKey;
     static const HashNumber sCollisionBit = Entry::sCollisionBit;
 
+    static void staticAsserts()
+    {
+        /* Rely on compiler "constant overflow warnings". */
+        JS_STATIC_ASSERT(((sMaxInit * sInvMaxAlpha) >> 7) < sMaxCapacity);
+        JS_STATIC_ASSERT((sMaxCapacity * sInvMaxAlpha) <= UINT32_MAX);
+        JS_STATIC_ASSERT((sMaxCapacity * sizeof(Entry)) <= UINT32_MAX);
+    }
+
     static bool isLiveHash(HashNumber hash)
     {
         return Entry::isLiveHash(hash);
     }
 
     static HashNumber prepareHash(const Lookup& l)
     {
         HashNumber keyHash = HashPolicy::hash(l);
@@ -360,34 +369,34 @@ class HashTable : private AllocPolicy
     {
         /* Make sure that init isn't called twice. */
         JS_ASSERT(table == NULL);
 
         /*
          * Correct for sMaxAlphaFrac such that the table will not resize
          * when adding 'length' entries.
          */
-        JS_ASSERT(length < (uint32(1) << 23));
+        if (length > sMaxInit) {
+            this->reportAllocOverflow();
+            return false;
+        }
         uint32 capacity = (length * sInvMaxAlpha) >> 7;
 
         if (capacity < sMinSize)
             capacity = sMinSize;
 
         /* FIXME: use JS_CEILING_LOG2 when PGO stops crashing (bug 543034). */
         uint32 roundUp = sMinSize, roundUpLog2 = sMinSizeLog2;
         while (roundUp < capacity) {
             roundUp <<= 1;
             ++roundUpLog2;
         }
 
         capacity = roundUp;
-        if (capacity >= sSizeLimit) {
-            this->reportAllocOverflow();
-            return false;
-        }
+        JS_ASSERT(capacity <= sMaxCapacity);
 
         table = createTable(*this, capacity);
         if (!table)
             return false;
 
         setTableSizeLog2(roundUpLog2);
         METER(memset(&stats, 0, sizeof(stats)));
         return true;
@@ -531,17 +540,17 @@ class HashTable : private AllocPolicy
 
     bool changeTableSize(int deltaLog2)
     {
         /* Look, but don't touch, until we succeed in getting new entry store. */
         Entry *oldTable = table;
         uint32 oldCap = tableCapacity;
         uint32 newLog2 = sHashBits - hashShift + deltaLog2;
         uint32 newCapacity = JS_BIT(newLog2);
-        if (newCapacity >= sSizeLimit) {
+        if (newCapacity > sMaxCapacity) {
             this->reportAllocOverflow();
             return false;
         }
 
         Entry *newTable = createTable(*this, newCapacity);
         if (!newTable)
             return false;
 
new file mode 100644
--- /dev/null
+++ b/js/src/tests/ecma_5/extensions/JSON-string-replacer-overflow.js
@@ -0,0 +1,24 @@
+// Any copyright is dedicated to the Public Domain.
+// http://creativecommons.org/licenses/publicdomain/
+
+var r1 = [0, 1, 2, 3];
+Object.defineProperty(r1, (1 << 23) - 1, {});
+JSON.stringify({ 0: 0, 1: 1, 2: 2, 3: 3 }, r1)
+
+var r2 = [0, 1, 2, 3];
+Object.defineProperty(r2, (1 << 30), {});
+try
+{
+  JSON.stringify({ 0: 0, 1: 1, 2: 2, 3: 3 }, r2)
+}
+catch (e)
+{
+  assertEq(""+e, "InternalError: allocation size overflow");
+}
+
+/******************************************************************************/
+
+if (typeof reportCompare === "function")
+  reportCompare(true, true);
+
+print("Tests complete");
--- a/js/src/tests/ecma_5/extensions/jstests.list
+++ b/js/src/tests/ecma_5/extensions/jstests.list
@@ -11,16 +11,17 @@ script bug496985.js
 script bug566661.js
 script array-toString-recursion.js
 skip-if(!xulRuntime.shell) script cross-global-eval-is-indirect.js # needs newGlobal()
 script eval-native-callback-is-indirect.js
 script extension-methods-reject-null-undefined-this.js
 skip-if(!xulRuntime.shell) script function-definition-with.js # needs evaluate()
 script function-properties.js
 script iterator-in-catch.js
+script JSON-string-replacer-overflow.js
 skip-if(!xulRuntime.shell) script legacy-JSON.js # needs parseLegacyJSON
 fails script nested-delete-name-in-evalcode.js # bug 604301, at a minimum
 script proxy-strict.js
 script regress-bug567606.js
 script regress-bug607284.js
 script regress-bug629723.js
 script strict-function-statements.js
 script strict-option-redeclared-parameter.js