Fix incorrect capacity delta calculation reported in SparseArrayValueMap::add().
authormark.lam@apple.com <mark.lam@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Tue, 4 Apr 2017 00:42:02 +0000 (00:42 +0000)
committermark.lam@apple.com <mark.lam@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Tue, 4 Apr 2017 00:42:02 +0000 (00:42 +0000)
https://bugs.webkit.org/show_bug.cgi?id=170412
<rdar://problem/29697336>

Reviewed by Filip Pizlo.

JSTests:

* stress/regress-170412.js: Added.

Source/JavaScriptCore:

Here's an example of code that will trigger underflow in the "deprecatedExtraMemory"
reported by SparseArrayValueMap::add() that is added to Heap::m_deprecatedExtraMemorySize:

    arr = new Array;
    Object.defineProperty(arr, 18, ({writable: true, configurable: true}));
    for (var i = 0; i < 3; ++i) {
        Array.prototype.push.apply(arr, ["", () => {}, {}]);
        Array.prototype.sort.apply(arr, [() => {}, []]);
    }

However, Heap::m_deprecatedExtraMemorySize is only 1 of 3 values that are added
up to form the result of Heap::extraMemorySize().  Heap::m_extraMemorySize and
Heap::m_arrayBuffers.size() are the other 2.

While Heap::m_arrayBuffers.size() is bounded by actual allocated memory, both
Heap::m_deprecatedExtraMemorySize and Heap::m_extraMemorySize are added to
without any bounds checks, and they are only reset to 0 at the start of a full
GC.  As a result, if we have a long sequence of eden GCs with a lot of additions
to Heap::m_extraMemorySize and/or Heap::m_deprecatedExtraMemorySize, then these
values could theoretically overflow.  Coupling this with the underflow from
SparseArrayValueMap::add(), the result for Heap::extraMemorySize() can easily
overflow.  Note: Heap::extraMemorySize() is used to compute the value
currentHeapSize.

If multiple conditions line up just right, the above overflows can result in this
debug assertion failure during an eden GC:

    ASSERT(currentHeapSize >= m_sizeAfterLastCollect);

Otherwise, the effects of the overflows will only result in the computed
currentHeapSize not being representative of actual memory usage, and therefore,
a full GC may be triggered earlier or later than is ideal.

This patch ensures that SparseArrayValueMap::add() cannot underflow
Heap::m_deprecatedExtraMemorySize.  It also adds overflows checks in the
calculations of Heap::m_deprecatedExtraMemorySize, Heap::m_extraMemorySize, and
Heap::extraMemorySize() so that their values are saturated appropriately to
ensure that GC collections are triggered based on representative memory usage.

* heap/Heap.cpp:
(JSC::Heap::deprecatedReportExtraMemorySlowCase):
(JSC::Heap::extraMemorySize):
(JSC::Heap::updateAllocationLimits):
(JSC::Heap::reportExtraMemoryVisited):
* runtime/SparseArrayValueMap.cpp:
(JSC::SparseArrayValueMap::add):

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

JSTests/ChangeLog
JSTests/stress/regress-170412.js [new file with mode: 0644]
Source/JavaScriptCore/ChangeLog
Source/JavaScriptCore/heap/Heap.cpp
Source/JavaScriptCore/runtime/SparseArrayValueMap.cpp

index b4496b6..e832ead 100644 (file)
@@ -1,3 +1,13 @@
+2017-04-03  Mark Lam  <mark.lam@apple.com>
+
+        Fix incorrect capacity delta calculation reported in SparseArrayValueMap::add().
+        https://bugs.webkit.org/show_bug.cgi?id=170412
+        <rdar://problem/29697336>
+
+        Reviewed by Filip Pizlo.
+
+        * stress/regress-170412.js: Added.
+
 2017-04-03  Keith Miller  <keith_miller@apple.com>
 
         WebAssembly: Update spec tests
diff --git a/JSTests/stress/regress-170412.js b/JSTests/stress/regress-170412.js
new file mode 100644 (file)
index 0000000..bf288b9
--- /dev/null
@@ -0,0 +1,8 @@
+// This test passes if it does not crash.
+
+arr = new Array;
+Object.defineProperty(arr, 18, ({writable: true, configurable: true}));
+for (var i = 0; i < 3; ++i) {
+    Array.prototype.push.apply(arr, ["", () => { }, {}]);
+    Array.prototype.sort.apply(arr, [edenGC, []]);
+}
index 46cdcd8..65f86d8 100644 (file)
@@ -1,3 +1,58 @@
+2017-04-03  Mark Lam  <mark.lam@apple.com>
+
+        Fix incorrect capacity delta calculation reported in SparseArrayValueMap::add().
+        https://bugs.webkit.org/show_bug.cgi?id=170412
+        <rdar://problem/29697336>
+
+        Reviewed by Filip Pizlo.
+
+        Here's an example of code that will trigger underflow in the "deprecatedExtraMemory"
+        reported by SparseArrayValueMap::add() that is added to Heap::m_deprecatedExtraMemorySize:
+        
+            arr = new Array;
+            Object.defineProperty(arr, 18, ({writable: true, configurable: true}));
+            for (var i = 0; i < 3; ++i) {
+                Array.prototype.push.apply(arr, ["", () => {}, {}]);
+                Array.prototype.sort.apply(arr, [() => {}, []]);
+            }
+
+        However, Heap::m_deprecatedExtraMemorySize is only 1 of 3 values that are added
+        up to form the result of Heap::extraMemorySize().  Heap::m_extraMemorySize and
+        Heap::m_arrayBuffers.size() are the other 2.
+
+        While Heap::m_arrayBuffers.size() is bounded by actual allocated memory, both
+        Heap::m_deprecatedExtraMemorySize and Heap::m_extraMemorySize are added to
+        without any bounds checks, and they are only reset to 0 at the start of a full
+        GC.  As a result, if we have a long sequence of eden GCs with a lot of additions
+        to Heap::m_extraMemorySize and/or Heap::m_deprecatedExtraMemorySize, then these
+        values could theoretically overflow.  Coupling this with the underflow from
+        SparseArrayValueMap::add(), the result for Heap::extraMemorySize() can easily
+        overflow.  Note: Heap::extraMemorySize() is used to compute the value
+        currentHeapSize.
+
+        If multiple conditions line up just right, the above overflows can result in this
+        debug assertion failure during an eden GC:
+
+            ASSERT(currentHeapSize >= m_sizeAfterLastCollect);
+
+        Otherwise, the effects of the overflows will only result in the computed
+        currentHeapSize not being representative of actual memory usage, and therefore,
+        a full GC may be triggered earlier or later than is ideal.
+
+        This patch ensures that SparseArrayValueMap::add() cannot underflow
+        Heap::m_deprecatedExtraMemorySize.  It also adds overflows checks in the
+        calculations of Heap::m_deprecatedExtraMemorySize, Heap::m_extraMemorySize, and
+        Heap::extraMemorySize() so that their values are saturated appropriately to
+        ensure that GC collections are triggered based on representative memory usage.
+
+        * heap/Heap.cpp:
+        (JSC::Heap::deprecatedReportExtraMemorySlowCase):
+        (JSC::Heap::extraMemorySize):
+        (JSC::Heap::updateAllocationLimits):
+        (JSC::Heap::reportExtraMemoryVisited):
+        * runtime/SparseArrayValueMap.cpp:
+        (JSC::SparseArrayValueMap::add):
+
 2017-04-03  Filip Pizlo  <fpizlo@apple.com>
 
         Move the Liveness<> adapters from AirLiveness.h to AirLivenessAdapter.h.
index df713c5..3aee301 100644 (file)
@@ -458,7 +458,11 @@ void Heap::reportExtraMemoryAllocatedSlowCase(size_t size)
 
 void Heap::deprecatedReportExtraMemorySlowCase(size_t size)
 {
-    m_deprecatedExtraMemorySize += size;
+    // FIXME: Change this to use SaturatedArithmetic when available.
+    // https://bugs.webkit.org/show_bug.cgi?id=170411
+    Checked<size_t, RecordOverflow> checkedNewSize = m_deprecatedExtraMemorySize;
+    checkedNewSize += size;
+    m_deprecatedExtraMemorySize = UNLIKELY(checkedNewSize.hasOverflowed()) ? std::numeric_limits<size_t>::max() : checkedNewSize.unsafeGet();
     reportExtraMemoryAllocatedSlowCase(size);
 }
 
@@ -706,7 +710,15 @@ size_t Heap::objectCount()
 
 size_t Heap::extraMemorySize()
 {
-    return m_extraMemorySize + m_deprecatedExtraMemorySize + m_arrayBuffers.size();
+    // FIXME: Change this to use SaturatedArithmetic when available.
+    // https://bugs.webkit.org/show_bug.cgi?id=170411
+    Checked<size_t, RecordOverflow> checkedTotal = m_extraMemorySize;
+    checkedTotal += m_deprecatedExtraMemorySize;
+    checkedTotal += m_arrayBuffers.size();
+    size_t total = UNLIKELY(checkedTotal.hasOverflowed()) ? std::numeric_limits<size_t>::max() : checkedTotal.unsafeGet();
+
+    ASSERT(m_objectSpace.capacity() >= m_objectSpace.size());
+    return std::min(total, std::numeric_limits<size_t>::max() - m_objectSpace.capacity());
 }
 
 size_t Heap::size()
@@ -2112,6 +2124,11 @@ void Heap::updateAllocationLimits()
     // It's up to the user to ensure that extraMemorySize() ends up corresponding to allocation-time
     // extra memory reporting.
     currentHeapSize += extraMemorySize();
+    if (!ASSERT_DISABLED) {
+        Checked<size_t, RecordOverflow> checkedCurrentHeapSize = m_totalBytesVisited;
+        checkedCurrentHeapSize += extraMemorySize();
+        ASSERT(!checkedCurrentHeapSize.hasOverflowed() && checkedCurrentHeapSize.unsafeGet() == currentHeapSize);
+    }
 
     if (verbose)
         dataLog("extraMemorySize() = ", extraMemorySize(), ", currentHeapSize = ", currentHeapSize, "\n");
@@ -2386,7 +2403,12 @@ void Heap::reportExtraMemoryVisited(size_t size)
     
     for (;;) {
         size_t oldSize = *counter;
-        if (WTF::atomicCompareExchangeWeakRelaxed(counter, oldSize, oldSize + size))
+        // FIXME: Change this to use SaturatedArithmetic when available.
+        // https://bugs.webkit.org/show_bug.cgi?id=170411
+        Checked<size_t, RecordOverflow> checkedNewSize = oldSize;
+        checkedNewSize += size;
+        size_t newSize = UNLIKELY(checkedNewSize.hasOverflowed()) ? std::numeric_limits<size_t>::max() : checkedNewSize.unsafeGet();
+        if (WTF::atomicCompareExchangeWeakRelaxed(counter, oldSize, newSize))
             return;
     }
 }
index daa56ad..97c9cb6 100644 (file)
@@ -1,5 +1,5 @@
 /*
- * Copyright (C) 2011-2016 Apple Inc. All rights reserved.
+ * Copyright (C) 2011-2017 Apple Inc. All rights reserved.
  *
  * Redistribution and use in source and binary forms, with or without
  * modification, are permitted provided that the following conditions
@@ -84,7 +84,7 @@ SparseArrayValueMap::AddResult SparseArrayValueMap::add(JSObject* array, unsigne
         result = m_map.add(i, entry);
         capacity = m_map.capacity();
     }
-    if (capacity != m_reportedCapacity) {
+    if (capacity > m_reportedCapacity) {
         // FIXME: Adopt reportExtraMemoryVisited, and switch to reportExtraMemoryAllocated.
         // https://bugs.webkit.org/show_bug.cgi?id=142595
         Heap::heap(array)->deprecatedReportExtraMemory((capacity - m_reportedCapacity) * (sizeof(unsigned) + sizeof(WriteBarrier<Unknown>)));