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 75519 796b8466d549dc5db8df06f33210f8a1f02aaaf2
parent 75518 5bbc3615e3877e0d3fb047263cc995bc72e9cb73
child 75520 73aafae10571356aa17af47e922f1af6118de217
push id2
push userbsmedberg@mozilla.com
push dateFri, 19 Aug 2011 14:38:13 +0000
reviewerswaldo
bugs678362
milestone9.0a1
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