Cap length of an array with spread to MIN_ARRAY_STORAGE_CONSTRUCTION_LENGTH.
authormark.lam@apple.com <mark.lam@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Thu, 21 Mar 2019 07:51:12 +0000 (07:51 +0000)
committermark.lam@apple.com <mark.lam@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Thu, 21 Mar 2019 07:51:12 +0000 (07:51 +0000)
https://bugs.webkit.org/show_bug.cgi?id=196055
<rdar://problem/49067448>

Reviewed by Yusuke Suzuki.

JSTests:

* stress/new_array_with_spread-should-cap-array-size-to-MIN_ARRAY_STORAGE_CONSTRUCTION_LENGTH.js: Added.

Source/JavaScriptCore:

We are doing this because:
1. We expect the array to be densely packed.
2. SpeculativeJIT::compileAllocateNewArrayWithSize() (and the FTL equivalent)
   expects the array length to be less than MIN_ARRAY_STORAGE_CONSTRUCTION_LENGTH
   if we don't want to use an ArrayStorage shape.
3. There's no reason why an array with spread needs to be that large anyway.
   MIN_ARRAY_STORAGE_CONSTRUCTION_LENGTH is plenty.

In this patch, we also add a debug assert in compileAllocateNewArrayWithSize() and
emitAllocateButterfly() to check for overflows.

* assembler/AbortReason.h:
* dfg/DFGOperations.cpp:
* dfg/DFGSpeculativeJIT.cpp:
(JSC::DFG::SpeculativeJIT::compileCreateRest):
(JSC::DFG::SpeculativeJIT::compileNewArrayWithSpread):
(JSC::DFG::SpeculativeJIT::emitAllocateButterfly):
(JSC::DFG::SpeculativeJIT::compileAllocateNewArrayWithSize):
* ftl/FTLLowerDFGToB3.cpp:
(JSC::FTL::DFG::LowerDFGToB3::compileNewArrayWithSpread):
* runtime/ArrayConventions.h:
* runtime/CommonSlowPaths.cpp:
(JSC::SLOW_PATH_DECL):

git-svn-id: https://svn.webkit.org/repository/webkit/trunk@243280 268f45cc-cd09-0410-ab3c-d52691b4dbfc

JSTests/ChangeLog
JSTests/stress/new_array_with_spread-should-cap-array-size-to-MIN_ARRAY_STORAGE_CONSTRUCTION_LENGTH.js [new file with mode: 0644]
Source/JavaScriptCore/ChangeLog
Source/JavaScriptCore/assembler/AbortReason.h
Source/JavaScriptCore/dfg/DFGOperations.cpp
Source/JavaScriptCore/dfg/DFGSpeculativeJIT.cpp
Source/JavaScriptCore/ftl/FTLLowerDFGToB3.cpp
Source/JavaScriptCore/runtime/ArrayConventions.h
Source/JavaScriptCore/runtime/CommonSlowPaths.cpp

index c381164..90cffb1 100644 (file)
@@ -1,3 +1,13 @@
+2019-03-21  Mark Lam  <mark.lam@apple.com>
+
+        Cap length of an array with spread to MIN_ARRAY_STORAGE_CONSTRUCTION_LENGTH.
+        https://bugs.webkit.org/show_bug.cgi?id=196055
+        <rdar://problem/49067448>
+
+        Reviewed by Yusuke Suzuki.
+
+        * stress/new_array_with_spread-should-cap-array-size-to-MIN_ARRAY_STORAGE_CONSTRUCTION_LENGTH.js: Added.
+
 2019-03-20  Saam Barati  <sbarati@apple.com>
 
         typeOfDoubleSum is wrong for when NaN can be produced
diff --git a/JSTests/stress/new_array_with_spread-should-cap-array-size-to-MIN_ARRAY_STORAGE_CONSTRUCTION_LENGTH.js b/JSTests/stress/new_array_with_spread-should-cap-array-size-to-MIN_ARRAY_STORAGE_CONSTRUCTION_LENGTH.js
new file mode 100644 (file)
index 0000000..8e4ece8
--- /dev/null
@@ -0,0 +1,44 @@
+//@ skip if $memoryLimited or $buildType == "debug"
+
+function test() {
+    function makeFoo(n) {
+        let src = "return function(a, b) { for (let i = 0; i < 20000; i++); return [";
+        for (let i = 0; i < n; i++) {
+            src += "...a";
+            if (i < n-1)
+                src += ",";
+        }
+        src += ",...b];}";
+        return (new Function(src))();
+    }
+
+    var NUM_SPREAD_ARGS = 8;
+    var foo = makeFoo(NUM_SPREAD_ARGS);
+
+    var b = [1.1, 1.1];
+    for (let i = 0; i < 10; i++)
+        foo(b, b);
+
+    function makeArray(len, v = 1.234) {
+        let a = [];
+        while (a.length < len)
+            a[a.length] = v;
+        return a;
+    }
+
+    var a = makeArray(0x20000040 / NUM_SPREAD_ARGS);
+    var c = []; c.length = 1;
+
+    var arr = foo(a, c);
+    print(arr.length);
+}
+
+var exception;
+try {
+    test();
+} catch (e) {
+    exception = e;
+}
+
+if (exception != "Error: Out of memory")
+    throw "FAILED";
index d5221a1..53ea6c8 100644 (file)
@@ -1,3 +1,35 @@
+2019-03-21  Mark Lam  <mark.lam@apple.com>
+
+        Cap length of an array with spread to MIN_ARRAY_STORAGE_CONSTRUCTION_LENGTH.
+        https://bugs.webkit.org/show_bug.cgi?id=196055
+        <rdar://problem/49067448>
+
+        Reviewed by Yusuke Suzuki.
+
+        We are doing this because:
+        1. We expect the array to be densely packed.
+        2. SpeculativeJIT::compileAllocateNewArrayWithSize() (and the FTL equivalent)
+           expects the array length to be less than MIN_ARRAY_STORAGE_CONSTRUCTION_LENGTH
+           if we don't want to use an ArrayStorage shape.
+        3. There's no reason why an array with spread needs to be that large anyway.
+           MIN_ARRAY_STORAGE_CONSTRUCTION_LENGTH is plenty.
+
+        In this patch, we also add a debug assert in compileAllocateNewArrayWithSize() and
+        emitAllocateButterfly() to check for overflows.
+
+        * assembler/AbortReason.h:
+        * dfg/DFGOperations.cpp:
+        * dfg/DFGSpeculativeJIT.cpp:
+        (JSC::DFG::SpeculativeJIT::compileCreateRest):
+        (JSC::DFG::SpeculativeJIT::compileNewArrayWithSpread):
+        (JSC::DFG::SpeculativeJIT::emitAllocateButterfly):
+        (JSC::DFG::SpeculativeJIT::compileAllocateNewArrayWithSize):
+        * ftl/FTLLowerDFGToB3.cpp:
+        (JSC::FTL::DFG::LowerDFGToB3::compileNewArrayWithSpread):
+        * runtime/ArrayConventions.h:
+        * runtime/CommonSlowPaths.cpp:
+        (JSC::SLOW_PATH_DECL):
+
 2019-03-20  Yusuke Suzuki  <ysuzuki@apple.com>
 
         [JSC] Use finalizer in JSGlobalLexicalEnvironment and JSGlobalObject
index 4b7e766..a7fbef2 100644 (file)
@@ -1,5 +1,5 @@
 /*
- * Copyright (C) 2014-2016 Apple Inc. All rights reserved.
+ * Copyright (C) 2014-2019 Apple Inc. All rights reserved.
  *
  * Redistribution and use in source and binary forms, with or without
  * modification, are permitted provided that the following conditions
@@ -73,6 +73,7 @@ enum AbortReason {
     RepatchInsaneArgumentCount                        = 310,
     TGInvalidPointer                                  = 320,
     TGNotSupported                                    = 330,
+    UncheckedOverflow                                 = 335,
     YARRNoInputConsumed                               = 340,
 };
 
index 9f0e804..f542dd6 100644 (file)
@@ -1,5 +1,5 @@
 /*
- * Copyright (C) 2011-2018 Apple Inc. All rights reserved.
+ * Copyright (C) 2011-2019 Apple Inc. All rights reserved.
  *
  * Redistribution and use in source and binary forms, with or without
  * modification, are permitted provided that the following conditions
@@ -2721,6 +2721,11 @@ JSCell* JIT_OPERATION operationNewArrayWithSpreadSlow(ExecState* exec, void* buf
     }
 
     unsigned length = checkedLength.unsafeGet();
+    if (UNLIKELY(length >= MIN_ARRAY_STORAGE_CONSTRUCTION_LENGTH)) {
+        throwOutOfMemoryError(exec, scope);
+        return nullptr;
+    }
+
     JSGlobalObject* globalObject = exec->lexicalGlobalObject();
     Structure* structure = globalObject->arrayStructureForIndexingTypeDuringAllocation(ArrayWithContiguous);
 
index abb2d09..85a5a87 100644 (file)
@@ -7654,6 +7654,10 @@ void SpeculativeJIT::compileCreateRest(Node* node)
         GPRReg arrayLengthGPR = arrayLength.gpr();
         GPRReg arrayResultGPR = arrayResult.gpr();
 
+        // We can tell compileAllocateNewArrayWithSize() that it does not need to check
+        // for large arrays and use ArrayStorage structure because arrayLength here will
+        // always be bounded by stack size. Realistically, we won't be able to push enough
+        // arguments to have arrayLength exceed MIN_ARRAY_STORAGE_CONSTRUCTION_LENGTH.
         bool shouldAllowForArrayStorageStructureForLargeArrays = false;
         ASSERT(m_jit.graph().globalObjectFor(node->origin.semantic)->restParameterStructure()->indexingMode() == ArrayWithContiguous || m_jit.graph().globalObjectFor(node->origin.semantic)->isHavingABadTime());
         compileAllocateNewArrayWithSize(m_jit.graph().globalObjectFor(node->origin.semantic), arrayResultGPR, arrayLengthGPR, ArrayWithContiguous, shouldAllowForArrayStorageStructureForLargeArrays);
@@ -8007,7 +8011,12 @@ void SpeculativeJIT::compileNewArrayWithSpread(Node* node)
                 }
             }
 
+            speculationCheck(Overflow, JSValueRegs(), nullptr, m_jit.branch32(MacroAssembler::AboveOrEqual, lengthGPR, TrustedImm32(MIN_ARRAY_STORAGE_CONSTRUCTION_LENGTH)));
 
+            // We can tell compileAllocateNewArrayWithSize() that it does not need to
+            // check for large arrays and use ArrayStorage structure because we already
+            // ensured above that the spread array length will definitely fit in a
+            // non-ArrayStorage shaped array.
             bool shouldAllowForArrayStorageStructureForLargeArrays = false;
             ASSERT(m_jit.graph().globalObjectFor(node->origin.semantic)->restParameterStructure()->indexingType() == ArrayWithContiguous || m_jit.graph().globalObjectFor(node->origin.semantic)->isHavingABadTime());
             compileAllocateNewArrayWithSize(m_jit.graph().globalObjectFor(node->origin.semantic), resultGPR, lengthGPR, ArrayWithContiguous, shouldAllowForArrayStorageStructureForLargeArrays);
@@ -11674,6 +11683,11 @@ void SpeculativeJIT::emitAllocateButterfly(GPRReg storageResultGPR, GPRReg sizeG
     m_jit.zeroExtend32ToPtr(sizeGPR, scratch1);
     m_jit.lshift32(TrustedImm32(3), scratch1);
     m_jit.add32(TrustedImm32(sizeof(IndexingHeader)), scratch1, scratch2);
+#if !ASSERT_DISABLED
+    MacroAssembler::Jump didNotOverflow = m_jit.branch32(MacroAssembler::AboveOrEqual, scratch2, sizeGPR);
+    m_jit.abortWithReason(UncheckedOverflow);
+    didNotOverflow.link(&m_jit);
+#endif
     m_jit.emitAllocateVariableSized(
         storageResultGPR, m_jit.vm()->jsValueGigacageAuxiliarySpace, scratch2, scratch1, scratch3, slowCases);
     m_jit.addPtr(TrustedImm32(sizeof(IndexingHeader)), storageResultGPR);
@@ -12973,6 +12987,14 @@ void SpeculativeJIT::compileAllocateNewArrayWithSize(JSGlobalObject* globalObjec
     MacroAssembler::JumpList slowCases;
     if (shouldConvertLargeSizeToArrayStorage)
         slowCases.append(m_jit.branch32(MacroAssembler::AboveOrEqual, sizeGPR, TrustedImm32(MIN_ARRAY_STORAGE_CONSTRUCTION_LENGTH)));
+#if !ASSERT_DISABLED
+    else {
+        MacroAssembler::Jump lengthIsWithinLimits;
+        lengthIsWithinLimits = m_jit.branch32(MacroAssembler::Below, sizeGPR, TrustedImm32(MIN_ARRAY_STORAGE_CONSTRUCTION_LENGTH));
+        m_jit.abortWithReason(UncheckedOverflow);
+        lengthIsWithinLimits.link(&m_jit);
+    }
+#endif
 
     // We can use resultGPR as a scratch right now.
     emitAllocateButterfly(storageGPR, sizeGPR, scratchGPR, scratch2GPR, resultGPR, slowCases);
index 2d9b7d7..a688f2f 100644 (file)
@@ -5840,6 +5840,9 @@ private:
                 }
             }
 
+            LValue exceedsMaxAllowedLength = m_out.aboveOrEqual(length, m_out.constInt32(MIN_ARRAY_STORAGE_CONSTRUCTION_LENGTH));
+            blessSpeculation(m_out.speculate(exceedsMaxAllowedLength), Overflow, noValue(), nullptr, m_origin);
+
             RegisteredStructure structure = m_graph.registerStructure(m_graph.globalObjectFor(m_node->origin.semantic)->originalArrayStructureForIndexingType(ArrayWithContiguous));
             ArrayValues arrayValues = allocateUninitializedContiguousJSArray(length, structure);
             LValue result = arrayValues.array;
index aab19d0..37589d2 100644 (file)
@@ -1,6 +1,6 @@
 /*
  *  Copyright (C) 1999-2000 Harri Porten (porten@kde.org)
- *  Copyright (C) 2003-2017 Apple Inc. All rights reserved.
+ *  Copyright (C) 2003-2019 Apple Inc. All rights reserved.
  *
  *  This library is free software; you can redistribute it and/or
  *  modify it under the terms of the GNU Lesser General Public
@@ -65,7 +65,7 @@ namespace JSC {
 #define MIN_SPARSE_ARRAY_INDEX 100000U
 // If you try to allocate a contiguous array larger than this, then we will allocate an ArrayStorage
 // array instead. We allow for an array that occupies 1GB of VM.
-#define MIN_ARRAY_STORAGE_CONSTRUCTION_LENGTH 1024 * 1024 * 1024 / 8
+#define MIN_ARRAY_STORAGE_CONSTRUCTION_LENGTH (1024 * 1024 * 1024 / 8)
 #define MAX_STORAGE_VECTOR_INDEX (MAX_STORAGE_VECTOR_LENGTH - 1)
 // 0xFFFFFFFF is a bit weird -- is not an array index even though it's an integer.
 #define MAX_ARRAY_INDEX 0xFFFFFFFEU
index c5dfe1c..043baad 100644 (file)
@@ -1258,6 +1258,9 @@ SLOW_PATH_DECL(slow_path_new_array_with_spread)
         THROW(createOutOfMemoryError(exec));
 
     unsigned arraySize = checkedArraySize.unsafeGet();
+    if (UNLIKELY(arraySize >= MIN_ARRAY_STORAGE_CONSTRUCTION_LENGTH))
+        THROW(createOutOfMemoryError(exec));
+
     JSGlobalObject* globalObject = exec->lexicalGlobalObject();
     Structure* structure = globalObject->arrayStructureForIndexingTypeDuringAllocation(ArrayWithContiguous);