JavaScriptCore:
authormjs@apple.com <mjs@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Wed, 28 Nov 2007 11:03:10 +0000 (11:03 +0000)
committermjs@apple.com <mjs@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Wed, 28 Nov 2007 11:03:10 +0000 (11:03 +0000)
        Add files missing from previous commit.

        * kjs/MarkStack.h: Added.

LayoutTests:

        add files missing from previous commit.

        * fast/js/gc-breadth-2-expected.txt: Added.
        * fast/js/gc-breadth-2.html: Added.
        * fast/js/gc-breadth-expected.txt: Added.
        * fast/js/gc-breadth.html: Added.
        * fast/js/gc-depth-expected.txt: Added.
        * fast/js/gc-depth.html: Added.
        * fast/js/resources/gc-breadth-2.js: Added.
        * fast/js/resources/gc-breadth.js: Added.
        * fast/js/resources/gc-depth.js: Added.

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

12 files changed:
JavaScriptCore/ChangeLog
JavaScriptCore/kjs/MarkStack.h [new file with mode: 0644]
LayoutTests/ChangeLog
LayoutTests/fast/js/gc-breadth-2-expected.txt [new file with mode: 0644]
LayoutTests/fast/js/gc-breadth-2.html [new file with mode: 0644]
LayoutTests/fast/js/gc-breadth-expected.txt [new file with mode: 0644]
LayoutTests/fast/js/gc-breadth.html [new file with mode: 0644]
LayoutTests/fast/js/gc-depth-expected.txt [new file with mode: 0644]
LayoutTests/fast/js/gc-depth.html [new file with mode: 0644]
LayoutTests/fast/js/resources/gc-breadth-2.js [new file with mode: 0644]
LayoutTests/fast/js/resources/gc-breadth.js [new file with mode: 0644]
LayoutTests/fast/js/resources/gc-depth.js [new file with mode: 0644]

index dc7d94db82e7343c5e73049a15336f29ec086858..7a0b62aef97970698123b707d91e69f0ff51a950 100644 (file)
@@ -1,3 +1,102 @@
+2007-11-28  Maciej Stachowiak  <mjs@apple.com>
+
+        Add files missing from previous commit.
+
+        * kjs/MarkStack.h: Added.
+
+2007-11-28  Maciej Stachowiak  <mjs@apple.com>
+
+        Not reviewed.
+
+        - Fixed "Stack overflow crash in JavaScript garbage collector mark pass"
+        http://bugs.webkit.org/show_bug.cgi?id=12216
+        
+        Implement mark stack. This version is not suitable for prime time because it makes a
+        huge allocation on every collect, and potentially makes marking of detached subtrees
+        slow. But it is a .2% - .4% speedup even without much tweaking.
+        
+        The basic approach is to replace mark() methods with
+        markChildren(MarkStack&) methods. Reachable references are pushed
+        onto a mark stack (which encapsulates ignoring already-marked
+        references). 
+        
+        Objects are no longer responsible for actually setting their own
+        mark bits, the collector does that. This means that for objects on
+        the number heap we don't have to call markChildren() at all since
+        we know there aren't any.
+        
+        The mark phase of collect pushes roots onto the mark stack
+        and drains it as often as possible.
+        
+        To make this approach viable requires a constant-size mark stack
+        and a slow fallback approach for when the stack size is exceeded,
+        plus optimizations to make the required stack small in common
+        cases. This should be doable.
+
+        * JavaScriptCore.exp: Export new symbols.
+        * JavaScriptCore.xcodeproj/project.pbxproj: Add new file.
+        * kjs/collector.cpp:
+        (KJS::Collector::heapAllocate):
+        (KJS::drainMarkStack): Helper for all of the below.
+        (KJS::Collector::markStackObjectsConservatively): Use mark stack.
+        (KJS::Collector::markCurrentThreadConservatively): ditto
+        (KJS::Collector::markOtherThreadConservatively): ditto
+        (KJS::Collector::markProtectedObjects): ditto
+        (KJS::Collector::markMainThreadOnlyObjects): ditto
+        (KJS::Collector::collect): ditto
+        * kjs/collector.h:
+        (KJS::Collector::cellMayHaveRefs): Helper for MarkStack.
+
+        * kjs/MarkStack.h: Added. The actual mark stack implementation.
+        (KJS::MarkStack::push):
+        (KJS::MarkStack::pushAtom):
+        (KJS::MarkStack::pop):
+        (KJS::MarkStack::isEmpty):
+        (KJS::MarkStack::reserveCapacity):
+
+        Changed mark() methods to markChildren() methods:
+        
+        * kjs/ExecState.cpp:
+        (KJS::ExecState::markChildren):
+        * kjs/ExecState.h:
+        * kjs/JSWrapperObject.cpp:
+        (KJS::JSWrapperObject::markChildren):
+        * kjs/JSWrapperObject.h:
+        * kjs/array_instance.cpp:
+        (KJS::ArrayInstance::markChildren):
+        * kjs/array_instance.h:
+        * kjs/bool_object.cpp:
+        (BooleanInstance::markChildren):
+        * kjs/bool_object.h:
+        * kjs/error_object.cpp:
+        * kjs/error_object.h:
+        * kjs/function.cpp:
+        (KJS::FunctionImp::markChildren):
+        (KJS::Arguments::Arguments):
+        (KJS::Arguments::markChildren):
+        (KJS::ActivationImp::markChildren):
+        * kjs/function.h:
+        * kjs/internal.cpp:
+        (KJS::GetterSetterImp::markChildren):
+        * kjs/interpreter.cpp:
+        (KJS::Interpreter::markRoots):
+        * kjs/interpreter.h:
+        * kjs/list.cpp:
+        (KJS::List::markProtectedListsSlowCase):
+        * kjs/list.h:
+        (KJS::List::markProtectedLists):
+        * kjs/object.cpp:
+        (KJS::JSObject::markChildren):
+        * kjs/object.h:
+        (KJS::ScopeChain::markChildren):
+        * kjs/property_map.cpp:
+        (KJS::PropertyMap::markChildren):
+        * kjs/property_map.h:
+        * kjs/scope_chain.h:
+        * kjs/string_object.cpp:
+        (KJS::StringInstance::markChildren):
+        * kjs/string_object.h:
+
 2007-11-28  Maciej Stachowiak  <mjs@apple.com>
 
         Reviewed by Darin and Geoff.
diff --git a/JavaScriptCore/kjs/MarkStack.h b/JavaScriptCore/kjs/MarkStack.h
new file mode 100644 (file)
index 0000000..c96b4af
--- /dev/null
@@ -0,0 +1,96 @@
+// -*- mode: c++; c-basic-offset: 4 -*-
+/*
+ *  Copyright (C) 2007 Apple Inc. All rights reserved.
+ *
+ *  This library is free software; you can redistribute it and/or
+ *  modify it under the terms of the GNU Library General Public
+ *  License as published by the Free Software Foundation; either
+ *  version 2 of the License, or (at your option) any later version.
+ *
+ *  This library is distributed in the hope that it will be useful,
+ *  but WITHOUT ANY WARRANTY; without even the implied warranty of
+ *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ *  Library General Public License for more details.
+ *
+ *  You should have received a copy of the GNU Library General Public License
+ *  along with this library; see the file COPYING.LIB.  If not, write to
+ *  the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
+ *  Boston, MA 02110-1301, USA.
+ *
+ */
+
+#ifndef MarkStack_h
+#define MarkStack_h
+
+#include <wtf/Vector.h>
+#include "collector.h"
+#include "value.h"
+#include <stdio.h>
+
+namespace KJS {
+
+    class MarkStack {
+    public:
+        void push(JSValue* value)
+        {
+            if (value->marked())
+                return;
+            JSCell* cell = value->asCell();
+            Collector::markCell(cell);
+            if (!Collector::cellMayHaveRefs(cell))
+                return;
+            ASSERT(m_stack.size() < m_stack.capacity());
+            m_stack.uncheckedAppend(cell);
+        }
+
+        void push(JSCell* cell)
+        {
+            if (cell->marked())
+                return;
+            Collector::markCell(cell);
+            if (!Collector::cellMayHaveRefs(cell))
+                return;
+            ASSERT(m_stack.size() < m_stack.capacity());
+            m_stack.uncheckedAppend(cell);
+        }
+
+        void pushAtom(JSValue* value)
+        {
+            if (value->marked())
+                return;
+            JSCell* cell = value->asCell();
+            Collector::markCell(cell);
+        }
+
+        void pushAtom(JSCell* cell)
+        {
+            if (cell->marked())
+                return;
+            Collector::markCell(cell);
+        }
+
+        JSCell* pop()
+        {
+            ASSERT(m_stack.size() > 0);
+            JSCell* cell = m_stack.last();
+            m_stack.removeLast();
+            return cell;
+        }
+
+        bool isEmpty()
+        {
+            return m_stack.isEmpty();
+        }
+
+        void reserveCapacity(size_t size) 
+        {
+            m_stack.reserveCapacity(size);
+        }
+
+    private:
+        Vector<JSCell*> m_stack;
+    };
+
+}
+
+#endif // MarkStack_h
index 1058310baee263b31a41c0782e3d80325e1fd88e..989dba30cea00941e71aec14a774750531800b42 100644 (file)
@@ -1,3 +1,36 @@
+2007-11-28  Maciej Stachowiak  <mjs@apple.com>
+
+        add files missing from previous commit.
+
+        * fast/js/gc-breadth-2-expected.txt: Added.
+        * fast/js/gc-breadth-2.html: Added.
+        * fast/js/gc-breadth-expected.txt: Added.
+        * fast/js/gc-breadth.html: Added.
+        * fast/js/gc-depth-expected.txt: Added.
+        * fast/js/gc-depth.html: Added.
+        * fast/js/resources/gc-breadth-2.js: Added.
+        * fast/js/resources/gc-breadth.js: Added.
+        * fast/js/resources/gc-depth.js: Added.
+
+2007-11-28  Maciej Stachowiak  <mjs@apple.com>
+
+        Not reviewed.
+        
+        - Test cases for "Stack overflow crash in JavaScript garbage collector mark pass"
+        http://bugs.webkit.org/show_bug.cgi?id=12216
+
+        I have fixed this with the mark stack work.
+        
+        * fast/js/gc-breadth-2-expected.txt: Added.
+        * fast/js/gc-breadth-2.html: Added.
+        * fast/js/gc-breadth-expected.txt: Added.
+        * fast/js/gc-breadth.html: Added.
+        * fast/js/gc-depth-expected.txt: Added.
+        * fast/js/gc-depth.html: Added.
+        * fast/js/resources/gc-breadth-2.js: Added.
+        * fast/js/resources/gc-breadth.js: Added.
+        * fast/js/resources/gc-depth.js: Added.
+
 2007-11-28  Maciej Stachowiak  <mjs@apple.com>
 
         Not reviewed.
diff --git a/LayoutTests/fast/js/gc-breadth-2-expected.txt b/LayoutTests/fast/js/gc-breadth-2-expected.txt
new file mode 100644 (file)
index 0000000..fe88aae
--- /dev/null
@@ -0,0 +1,18 @@
+This test makes sure that wide object structures don't lead to GC crashes.
+
+On success, you will see a series of "PASS" messages, followed by "TEST COMPLETE".
+
+
+PASS successfullyParsed is true
+
+TEST COMPLETE
+
+This test makes sure that wide object structures don't lead to GC crashes.
+
+On success, you will see a series of "PASS" messages, followed by "TEST COMPLETE".
+
+
+PASS successfullyParsed is true
+
+TEST COMPLETE
+
diff --git a/LayoutTests/fast/js/gc-breadth-2.html b/LayoutTests/fast/js/gc-breadth-2.html
new file mode 100644 (file)
index 0000000..4a6c1d2
--- /dev/null
@@ -0,0 +1,26 @@
+<!DOCTYPE HTML PUBLIC "-//IETF//DTD HTML//EN">
+<html>
+<head>
+<link rel="stylesheet" href="resources/js-test-style.css">
+<script src="resources/js-test-pre.js"></script>
+</head>
+<body>
+<p id="description"></p>
+<div id="console"></div>
+<script src="resources/gc-breadth-2.js"></script>
+<script src="resources/js-test-post.js"></script>
+</body>
+</html>
+<!DOCTYPE HTML PUBLIC "-//IETF//DTD HTML//EN">
+<html>
+<head>
+<link rel="stylesheet" href="resources/js-test-style.css">
+<script src="resources/js-test-pre.js"></script>
+</head>
+<body>
+<p id="description"></p>
+<div id="console"></div>
+<script src="resources/gc-breadth-2.js"></script>
+<script src="resources/js-test-post.js"></script>
+</body>
+</html>
diff --git a/LayoutTests/fast/js/gc-breadth-expected.txt b/LayoutTests/fast/js/gc-breadth-expected.txt
new file mode 100644 (file)
index 0000000..fe88aae
--- /dev/null
@@ -0,0 +1,18 @@
+This test makes sure that wide object structures don't lead to GC crashes.
+
+On success, you will see a series of "PASS" messages, followed by "TEST COMPLETE".
+
+
+PASS successfullyParsed is true
+
+TEST COMPLETE
+
+This test makes sure that wide object structures don't lead to GC crashes.
+
+On success, you will see a series of "PASS" messages, followed by "TEST COMPLETE".
+
+
+PASS successfullyParsed is true
+
+TEST COMPLETE
+
diff --git a/LayoutTests/fast/js/gc-breadth.html b/LayoutTests/fast/js/gc-breadth.html
new file mode 100644 (file)
index 0000000..8d631d7
--- /dev/null
@@ -0,0 +1,26 @@
+<!DOCTYPE HTML PUBLIC "-//IETF//DTD HTML//EN">
+<html>
+<head>
+<link rel="stylesheet" href="resources/js-test-style.css">
+<script src="resources/js-test-pre.js"></script>
+</head>
+<body>
+<p id="description"></p>
+<div id="console"></div>
+<script src="resources/gc-breadth.js"></script>
+<script src="resources/js-test-post.js"></script>
+</body>
+</html>
+<!DOCTYPE HTML PUBLIC "-//IETF//DTD HTML//EN">
+<html>
+<head>
+<link rel="stylesheet" href="resources/js-test-style.css">
+<script src="resources/js-test-pre.js"></script>
+</head>
+<body>
+<p id="description"></p>
+<div id="console"></div>
+<script src="resources/gc-breadth.js"></script>
+<script src="resources/js-test-post.js"></script>
+</body>
+</html>
diff --git a/LayoutTests/fast/js/gc-depth-expected.txt b/LayoutTests/fast/js/gc-depth-expected.txt
new file mode 100644 (file)
index 0000000..25ba143
--- /dev/null
@@ -0,0 +1,18 @@
+This test makes sure that deep object structures don't lead to GC crashes.
+
+On success, you will see a series of "PASS" messages, followed by "TEST COMPLETE".
+
+
+PASS successfullyParsed is true
+
+TEST COMPLETE
+
+This test makes sure that deep object structures don't lead to GC crashes.
+
+On success, you will see a series of "PASS" messages, followed by "TEST COMPLETE".
+
+
+PASS successfullyParsed is true
+
+TEST COMPLETE
+
diff --git a/LayoutTests/fast/js/gc-depth.html b/LayoutTests/fast/js/gc-depth.html
new file mode 100644 (file)
index 0000000..dfb58a1
--- /dev/null
@@ -0,0 +1,26 @@
+<!DOCTYPE HTML PUBLIC "-//IETF//DTD HTML//EN">
+<html>
+<head>
+<link rel="stylesheet" href="resources/js-test-style.css">
+<script src="resources/js-test-pre.js"></script>
+</head>
+<body>
+<p id="description"></p>
+<div id="console"></div>
+<script src="resources/gc-depth.js"></script>
+<script src="resources/js-test-post.js"></script>
+</body>
+</html>
+<!DOCTYPE HTML PUBLIC "-//IETF//DTD HTML//EN">
+<html>
+<head>
+<link rel="stylesheet" href="resources/js-test-style.css">
+<script src="resources/js-test-pre.js"></script>
+</head>
+<body>
+<p id="description"></p>
+<div id="console"></div>
+<script src="resources/gc-depth.js"></script>
+<script src="resources/js-test-post.js"></script>
+</body>
+</html>
diff --git a/LayoutTests/fast/js/resources/gc-breadth-2.js b/LayoutTests/fast/js/resources/gc-breadth-2.js
new file mode 100644 (file)
index 0000000..38455b0
--- /dev/null
@@ -0,0 +1,26 @@
+description("This test makes sure that wide object structures don't lead to GC crashes.")
+
+var a = {};
+for (var i = 0; i < 200000; i++) {
+    a[i] = {};
+}
+
+var b = "";
+for (var i = 0; i < 80000; i++) {
+    b += "b";
+}
+
+var successfullyParsed = true;
+description("This test makes sure that wide object structures don't lead to GC crashes.")
+
+var a = {};
+for (var i = 0; i < 200000; i++) {
+    a[i] = {};
+}
+
+var b = "";
+for (var i = 0; i < 80000; i++) {
+    b += "b";
+}
+
+var successfullyParsed = true;
diff --git a/LayoutTests/fast/js/resources/gc-breadth.js b/LayoutTests/fast/js/resources/gc-breadth.js
new file mode 100644 (file)
index 0000000..45df7bb
--- /dev/null
@@ -0,0 +1,26 @@
+description("This test makes sure that wide object structures don't lead to GC crashes.")
+
+var a = [];
+for (var i = 0; i < 200000; i++) {
+    a[i] = [];
+}
+
+var b = "";
+for (var i = 0; i < 80000; i++) {
+    b += "b";
+}
+
+var successfullyParsed = true;
+description("This test makes sure that wide object structures don't lead to GC crashes.")
+
+var a = [];
+for (var i = 0; i < 200000; i++) {
+    a[i] = [];
+}
+
+var b = "";
+for (var i = 0; i < 80000; i++) {
+    b += "b";
+}
+
+var successfullyParsed = true;
diff --git a/LayoutTests/fast/js/resources/gc-depth.js b/LayoutTests/fast/js/resources/gc-depth.js
new file mode 100644 (file)
index 0000000..f6fe7f2
--- /dev/null
@@ -0,0 +1,26 @@
+description("This test makes sure that deep object structures don't lead to GC crashes.")
+
+var a = [];
+for (var i = 0; i < 200000; i++) {
+    a = [a];
+}
+
+var b = "";
+for (var i = 0; i < 80000; i++) {
+    b += "b";
+}
+
+var successfullyParsed = true;
+description("This test makes sure that deep object structures don't lead to GC crashes.")
+
+var a = [];
+for (var i = 0; i < 200000; i++) {
+    a = [a];
+}
+
+var b = "";
+for (var i = 0; i < 80000; i++) {
+    b += "b";
+}
+
+var successfullyParsed = true;