Changeset 34204 in webkit

Timestamp:

May 29, 2008 10:14:02 AM (16 years ago)

Author:

ap@webkit.org

Message:

Reviewed by Darin.

​https://bugs.webkit.org/show_bug.cgi?id=19294
<rdar://problem/5969062> A crash when iterating over a sparse array backwards.

• kjs/array_instance.cpp: Turned sparseArrayCutoff into a macro, so that using max() on it doesn't cause a PIC branch. (KJS::ArrayInstance::increaseVectorLength): Added a comment about this function not preserving class invariants. (KJS::ArrayInstance::put): Update m_storage after reallocation. Move values that fit to the vector from the map in all code paths.

Location:

trunk

Files:

• JavaScriptCore/ChangeLog (modified) (1 diff)
• JavaScriptCore/kjs/array_instance.cpp (modified) (6 diffs)
• LayoutTests/ChangeLog (modified) (1 diff)
• LayoutTests/fast/js/array-iterate-backwards-expected.txt (added)
• LayoutTests/fast/js/array-iterate-backwards.html (added)
• LayoutTests/fast/js/resources/array-iterate-backwards.js (added)

trunk/JavaScriptCore/ChangeLog

@@ +1 @@
+2008-05-29  Alexey Proskuryakov  <ap@webkit.org>
+
+        Reviewed by Darin.
+
+        https://bugs.webkit.org/show_bug.cgi?id=19294
+        <rdar://problem/5969062> A crash when iterating over a sparse array backwards.
+
+        * kjs/array_instance.cpp: Turned sparseArrayCutoff into a macro, so that using max() on it
+        doesn't cause a PIC branch.
+        (KJS::ArrayInstance::increaseVectorLength): Added a comment about this function not
+        preserving class invariants.
+        (KJS::ArrayInstance::put): Update m_storage after reallocation. Move values that fit to
+        the vector from the map in all code paths.
+
 2008-05-29  Thiago Macieira  <tjmaciei@trolltech.com>
 

trunk/JavaScriptCore/kjs/array_instance.cpp

@@ -48 +48 @@
 // When indices greater than sparseArrayCutoff are involved, we use a vector
 // as long as it is 1/8 full. If more sparse than that, we use a map.
-static const unsigned sparseArrayCutoff = 10000;
+// This value has to be a macro to be used in max() and min() without introducing
+// a PIC branch in Mach-O binaries, see <rdar://problem/5971391>.
+#define sparseArrayCutoff 10000U
 static const unsigned minDensityMultiplier = 8;
 
@@ -227 +229 @@
     }
 
-    if (i < sparseArrayCutoff) {
+    SparseArrayValueMap* map = storage->m_sparseValueMap;
+
+    if (i >= sparseArrayCutoff) {
+        // We miss some cases where we could compact the storage, such as a large array that is being filled from the end
+        // (which will only be compacted as we reach indices that are less than cutoff) - but this makes the check much faster.
+        if (!isDenseEnoughForVector(i + 1, storage->m_numValuesInVector + 1)) {
+            if (!map) {
+                map = new SparseArrayValueMap;
+                storage->m_sparseValueMap = map;
+            }
+            map->set(i, value);
+            return;
+        }
+    }
+
+    // We have decided that we'll put the new item into the vector.
+    // Fast case is when there is no sparse map, so we can increase the vector size without moving values from it.
+    if (!map || map->isEmpty()) {
         increaseVectorLength(i + 1);
         storage = m_storage;
@@ -235 +254 @@
     }
 
-    SparseArrayValueMap* map = storage->m_sparseValueMap;
-    if (!map || map->isEmpty()) {
-        if (isDenseEnoughForVector(i + 1, storage->m_numValuesInVector + 1)) {
-            increaseVectorLength(i + 1);
-            storage = m_storage;
-            ++storage->m_numValuesInVector;
-            storage->m_vector[i] = value;
-            return;
-        }
-        if (!map) {
-            map = new SparseArrayValueMap;
-            storage->m_sparseValueMap = map;
-        }
-        map->set(i, value);
-        return;
-    }
-
+    // Decide how many values it would be best to move from the map.
     unsigned newNumValuesInVector = storage->m_numValuesInVector + 1;
-    if (!isDenseEnoughForVector(i + 1, newNumValuesInVector)) {
-        map->set(i, value);
-        return;
-    }
-
     unsigned newVectorLength = increasedVectorLength(i + 1);
-    for (unsigned j = m_vectorLength; j < newVectorLength; ++j)
+    for (unsigned j = max(m_vectorLength, sparseArrayCutoff); j < newVectorLength; ++j)
         newNumValuesInVector += map->contains(j);
-    newNumValuesInVector -= map->contains(i);
+    if (i >= sparseArrayCutoff)
+        newNumValuesInVector -= map->contains(i);
     if (isDenseEnoughForVector(newVectorLength, newNumValuesInVector)) {
         unsigned proposedNewNumValuesInVector = newNumValuesInVector;
         while (true) {
             unsigned proposedNewVectorLength = increasedVectorLength(newVectorLength + 1);
-            for (unsigned j = newVectorLength; j < proposedNewVectorLength; ++j)
+            for (unsigned j = max(newVectorLength, sparseArrayCutoff); j < proposedNewVectorLength; ++j)
                 proposedNewNumValuesInVector += map->contains(j);
             if (!isDenseEnoughForVector(proposedNewVectorLength, proposedNewNumValuesInVector))
@@ -281 +280 @@
         for (unsigned j = vectorLength; j < newVectorLength; ++j)
             storage->m_vector[j] = 0;
-        map->remove(i);
+        if (i > sparseArrayCutoff)
+            map->remove(i);
     } else {
-        for (unsigned j = vectorLength; j < newVectorLength; ++j)
+        for (unsigned j = vectorLength; j < max(vectorLength, sparseArrayCutoff); ++j)
+            storage->m_vector[j] = 0;
+        for (unsigned j = max(vectorLength, sparseArrayCutoff); j < newVectorLength; ++j)
             storage->m_vector[j] = map->take(j);
     }
@@ -291 +293 @@
     m_vectorLength = newVectorLength;
     storage->m_numValuesInVector = newNumValuesInVector;
+
+    m_storage = storage;
 }
 
@@ -358 +362 @@
 bool ArrayInstance::increaseVectorLength(unsigned newLength)
 {
+    // This function leaves the array in an internally inconsistent state, because it does not move any values from sparse value map
+    // to the vector. Callers have to account for that, because they can do it more efficiently.
+
     ArrayStorage* storage = m_storage;
 

trunk/LayoutTests/ChangeLog

@@ +1 @@
+2008-05-29  Alexey Proskuryakov  <ap@webkit.org>
+
+        Reviewed by Darin.
+
+        https://bugs.webkit.org/show_bug.cgi?id=19294
+        <rdar://problem/5969062> A crash when iterating over a sparse array backwards.
+
+        * fast/js/array-iterate-backwards-expected.txt: Added.
+        * fast/js/array-iterate-backwards.html: Added.
+        * fast/js/resources/array-iterate-backwards.js: Added.
+
 2008-05-29  Alexey Proskuryakov  <ap@webkit.org>