Fix missing edge cases with JSGlobalObjects having a bad time.
authormark.lam@apple.com <mark.lam@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Fri, 26 Oct 2018 18:30:13 +0000 (18:30 +0000)
committermark.lam@apple.com <mark.lam@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Fri, 26 Oct 2018 18:30:13 +0000 (18:30 +0000)
https://bugs.webkit.org/show_bug.cgi?id=189028
<rdar://problem/45204939>

Reviewed by Saam Barati.

JSTests:

* stress/regress-189028.js: Added.

Source/JavaScriptCore:

Consider the following scenario:

    let object O1 (of global G1) have an indexing type that is not SlowPut.
    let global G2 have a bad time.
    let object O2 (of global G2) be set as the prototype of O1.
    let object O3 (of global G2) have indexed accessors.

In the existing code, if we set O3 as O2's prototype, we'll have a bug where
O1 will not be made aware that that there are indexed accessors in its prototype
chain.

In this patch, we solve this issue by introducing a new invariant:

    A prototype chain is considered to possibly have indexed accessors if any
    object in the chain belongs to a global object that is having a bad time.

We apply this invariant as follows:

1. Enhance JSGlobalObject::haveABadTime() to also check if other global objects are
   affected by it having a bad time.  If so, it also ensures that those affected
   global objects have a bad time.

   The original code for JSGlobalObject::haveABadTime() uses a ObjectsWithBrokenIndexingFinder
   to find all objects affected by the global object having a bad time.  We enhance
   ObjectsWithBrokenIndexingFinder to also check for the possibility that any global
   objects may be affected by other global objects having a bad time i.e.

        let g1 = global1
        let g2 = global2
        let o1 = an object in g1
        let o2 = an object in g2

        let g1 have a bad time
        g2 is affected if
            o1 is in the prototype chain of o2,
            and o2 may be a prototype.

   If the ObjectsWithBrokenIndexingFinder does find the possibility of other global
   objects being affected, it will abort its heap scan and let haveABadTime() take
   a slow path to do a more complete multi global object scan.

   The slow path works as follows:

   1. Iterate the heap and record the graph of all global object dependencies.

      For each global object, record the list of other global objects that are
      affected by it.

   2. Compute a list of global objects that need to have a bad time using the
      current global object dependency graph.

   3. For each global object in the list of affected global objects, fire their
      HaveABadTime watchpoint and convert all their array structures to the
      SlowPut alternatives.

   4. Re-run ObjectsWithBrokenIndexingFinder to find all objects that are affected
      by any of the globals in the list from (2).

2. Enhance Structure::mayInterceptIndexedAccesses() to also return true if the
   structure's global object is having a bad time.

Note: there are 3 scenarios that we need to consider:

    let g1 = global1
    let g2 = global2
    let o1 = an object in g1
    let o2 = an object in g2

    Scenario 1: o2 is a prototype, and
                g1 has a bad time after o1 is inserted into the o2's prototype chain.

    Scenario 2: o2 is a prototype, and
                o1 is inserted into the o2's prototype chain after g1 has a bad time.

    Scenario 3: o2 is NOT a prototype, and
                o1 is inserted into the o2's prototype chain after g1 has a bad time.

    For scenario 1, when g1 has a bad time, we need to also make sure g2 has
    a bad time.  This is handled by enhancement 1 above.

    For scenario 2, when o1 is inserted into o2's prototype chain, we need to check
    if o1's global object has a bad time.  If so, then we need to make sure o2's
    global also has a bad time (because o2 is a prototype) and convert o2's
    storage type to SlowPut.  This is handled by enhancement 2 above in conjunction
    with JSObject::setPrototypeDirect().

    For scenario 3, when o1 is inserted into o2's prototype chain, we need to check
    if o1's global object has a bad time.  If so, then we only need to convert o2's
    storage type to SlowPut (because o2 is NOT a prototype).  This is handled by
    enhancement 2 above.

3. Also add $vm.isHavingABadTime(), $vm.createGlobalObject() to enable us to
   write some tests for this issue.

* runtime/JSGlobalObject.cpp:
(JSC::JSGlobalObject::fireWatchpointAndMakeAllArrayStructuresSlowPut):
(JSC::JSGlobalObject::haveABadTime):
* runtime/JSGlobalObject.h:
* runtime/JSObject.h:
(JSC::JSObject::mayInterceptIndexedAccesses): Deleted.
* runtime/JSObjectInlines.h:
(JSC::JSObject::mayInterceptIndexedAccesses):
* runtime/Structure.h:
* runtime/StructureInlines.h:
(JSC::Structure::mayInterceptIndexedAccesses const):
* tools/JSDollarVM.cpp:
(JSC::functionHaveABadTime):
(JSC::functionIsHavingABadTime):
(JSC::functionCreateGlobalObject):
(JSC::JSDollarVM::finishCreation):

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

JSTests/ChangeLog
JSTests/stress/regress-189028.js [new file with mode: 0644]
Source/JavaScriptCore/ChangeLog
Source/JavaScriptCore/runtime/JSGlobalObject.cpp
Source/JavaScriptCore/runtime/JSGlobalObject.h
Source/JavaScriptCore/runtime/JSObject.h
Source/JavaScriptCore/runtime/JSObjectInlines.h
Source/JavaScriptCore/runtime/Structure.h
Source/JavaScriptCore/runtime/StructureInlines.h
Source/JavaScriptCore/tools/JSDollarVM.cpp

index 97a5e3a..40fdee9 100644 (file)
@@ -1,3 +1,13 @@
+2018-10-26  Mark Lam  <mark.lam@apple.com>
+
+        Fix missing edge cases with JSGlobalObjects having a bad time.
+        https://bugs.webkit.org/show_bug.cgi?id=189028
+        <rdar://problem/45204939>
+
+        Reviewed by Saam Barati.
+
+        * stress/regress-189028.js: Added.
+
 2018-10-22  Mark Lam  <mark.lam@apple.com>
 
         DFGAbstractValue::m_arrayModes expects IndexingMode values, not IndexingType.
diff --git a/JSTests/stress/regress-189028.js b/JSTests/stress/regress-189028.js
new file mode 100644 (file)
index 0000000..b66db45
--- /dev/null
@@ -0,0 +1,242 @@
+function assert(x, y) {
+    if (x != y) {
+        $vm.print("actual: ", x);
+        $vm.print("expected: ", y);
+        throw "FAILED\n" + new Error().stack;
+    }
+}
+
+(function() {
+    let arr = [1.1, 2.2];
+    let arr2 = [1.1, 2.2];
+
+    assert($vm.isHavingABadTime(arr), false);
+    assert($vm.indexingMode(arr), "CopyOnWriteArrayWithDouble");
+    assert($vm.isHavingABadTime(arr2), false);
+    assert($vm.indexingMode(arr2), "CopyOnWriteArrayWithDouble");
+
+    let o = $vm.createGlobalObject();
+
+    $vm.haveABadTime(o);
+
+    let proto = new o.Object();
+    assert($vm.isHavingABadTime(o), true);
+    assert($vm.isHavingABadTime(proto), true);
+
+    arr2.__proto__ = proto;
+
+    assert($vm.isHavingABadTime(arr), false);
+    assert($vm.indexingMode(arr), "CopyOnWriteArrayWithDouble");
+    assert($vm.isHavingABadTime(arr2), false);
+    assert($vm.indexingMode(arr2), "ArrayWithSlowPutArrayStorage");
+})();
+
+gc();
+
+(function() {
+    let arr = [1.1, 2.2];
+    let arr2 = [1.1, 2.2];
+
+    assert($vm.isHavingABadTime(arr), false);
+    assert($vm.indexingMode(arr), "CopyOnWriteArrayWithDouble");
+    assert($vm.isHavingABadTime(arr2), false);
+    assert($vm.indexingMode(arr2), "CopyOnWriteArrayWithDouble");
+
+    let o = $vm.createGlobalObject();
+
+    let proto = new o.Object();
+    assert($vm.isHavingABadTime(o), false);
+    assert($vm.isHavingABadTime(proto), false);
+
+    arr2.__proto__ = proto;
+
+    assert($vm.isHavingABadTime(arr), false);
+    assert($vm.indexingMode(arr), "CopyOnWriteArrayWithDouble");
+    assert($vm.isHavingABadTime(arr2), false);
+    assert($vm.indexingMode(arr2), "ArrayWithDouble");
+
+    $vm.haveABadTime(o);
+
+    assert($vm.isHavingABadTime(o), true);
+    assert($vm.isHavingABadTime(proto), true);
+
+    assert($vm.isHavingABadTime(arr), false);
+    assert($vm.indexingMode(arr), "CopyOnWriteArrayWithDouble");
+    assert($vm.isHavingABadTime(arr2), false);
+    assert($vm.indexingMode(arr2), "ArrayWithSlowPutArrayStorage");
+})();
+
+gc();
+
+(function() {
+    let arr = [1.1, 2.2];
+    let arr2 = {};
+
+    assert($vm.isHavingABadTime(arr), false);
+    assert($vm.indexingMode(arr), "CopyOnWriteArrayWithDouble");
+    assert($vm.isHavingABadTime(arr2), false);
+    assert($vm.indexingMode(arr2), "NonArray");
+
+    let o = $vm.createGlobalObject();
+
+    $vm.haveABadTime(o);
+
+    let proto = new o.Object();
+    assert($vm.isHavingABadTime(o), true);
+    assert($vm.isHavingABadTime(proto), true);
+
+    arr2.__proto__ = proto;
+
+    assert($vm.isHavingABadTime(arr), false);
+    assert($vm.indexingMode(arr), "CopyOnWriteArrayWithDouble");
+    assert($vm.isHavingABadTime(arr2), false);
+    assert($vm.indexingMode(arr2), "NonArray");
+
+    arr2[0] = 1.1;
+
+    assert($vm.isHavingABadTime(arr), false);
+    assert($vm.indexingMode(arr), "CopyOnWriteArrayWithDouble");
+    assert($vm.isHavingABadTime(arr2), false);
+    assert($vm.indexingMode(arr2), "NonArrayWithSlowPutArrayStorage");
+})();
+
+gc();
+
+(function() {
+    let arr = [1.1, 2.2];
+    let arr2 = {};
+
+    assert($vm.isHavingABadTime(arr), false);
+    assert($vm.indexingMode(arr), "CopyOnWriteArrayWithDouble");
+    assert($vm.isHavingABadTime(arr2), false);
+    assert($vm.indexingMode(arr2), "NonArray");
+
+    let o = $vm.createGlobalObject();
+    let proto = new o.Object();
+
+    assert($vm.isHavingABadTime(o), false);
+    assert($vm.isHavingABadTime(proto), false);
+
+    arr2.__proto__ = proto;
+
+    assert($vm.isHavingABadTime(arr), false);
+    assert($vm.indexingMode(arr), "CopyOnWriteArrayWithDouble");
+    assert($vm.isHavingABadTime(arr2), false);
+    assert($vm.indexingMode(arr2), "NonArray");
+
+    arr2[0] = 1.1;
+
+    assert($vm.isHavingABadTime(arr), false);
+    assert($vm.indexingMode(arr), "CopyOnWriteArrayWithDouble");
+    assert($vm.isHavingABadTime(arr2), false);
+    assert($vm.indexingMode(arr2), "NonArrayWithDouble");
+
+    $vm.haveABadTime(o);
+
+    assert($vm.isHavingABadTime(o), true);
+    assert($vm.isHavingABadTime(proto), true);
+
+    assert($vm.isHavingABadTime(arr), false);
+    assert($vm.indexingMode(arr), "CopyOnWriteArrayWithDouble");
+    assert($vm.isHavingABadTime(arr2), false);
+    assert($vm.indexingMode(arr2), "NonArrayWithSlowPutArrayStorage");
+})();
+
+gc();
+
+(function() {
+    let g0 = $vm.createGlobalObject();
+    let o0 = new g0.Object(); 
+    assert($vm.isHavingABadTime(g0), false);
+    assert($vm.isHavingABadTime(o0), false);
+
+    let g1 = $vm.createGlobalObject();
+    let o1 = new g1.Object();
+    assert($vm.isHavingABadTime(g1), false);
+    assert($vm.isHavingABadTime(o1), false);
+
+    let g2 = $vm.createGlobalObject();
+    assert($vm.isHavingABadTime(g2), false);
+
+    $vm.haveABadTime(g1);
+    assert($vm.isHavingABadTime(g1), true);
+
+    o1.__proto__ = null;
+    g2.Array.prototype.__proto__ = o1;
+    o0.__proto__ = o1;
+
+    assert($vm.indexingMode(o0), "NonArray");
+    assert($vm.isHavingABadTime(g0), false);
+    assert($vm.isHavingABadTime(g2), true);
+})();
+
+gc();
+
+(function() {
+    let g0 = $vm.createGlobalObject();
+    let o0 = new g0.Object(); 
+    assert($vm.isHavingABadTime(g0), false);
+    assert($vm.isHavingABadTime(o0), false);
+
+    let g1 = $vm.createGlobalObject();
+    let o1 = new g1.Object();
+    assert($vm.isHavingABadTime(g1), false);
+    assert($vm.isHavingABadTime(o1), false);
+
+    let g2 = $vm.createGlobalObject();
+    assert($vm.isHavingABadTime(g2), false);
+
+    o1.__proto__ = null;
+    g2.Array.prototype.__proto__ = o1;
+    o0.__proto__ = o1;
+    assert($vm.isHavingABadTime(g0), false);
+    assert($vm.isHavingABadTime(g1), false);
+    assert($vm.isHavingABadTime(g2), false);
+
+    $vm.haveABadTime(g1);
+
+    assert($vm.indexingMode(o0), "NonArray");
+    assert($vm.isHavingABadTime(g0), false);
+    assert($vm.isHavingABadTime(g1), true);
+    assert($vm.isHavingABadTime(g2), true);
+})();
+
+gc();
+
+(function() {
+    let g0 = $vm.createGlobalObject();
+    let o0 = new g0.Object(); 
+    assert($vm.isHavingABadTime(g0), false);
+    assert($vm.isHavingABadTime(o0), false);
+
+    let g1 = $vm.createGlobalObject();
+    let o1 = new g1.Object();
+    assert($vm.isHavingABadTime(g1), false);
+    assert($vm.isHavingABadTime(o1), false);
+
+    let g2 = $vm.createGlobalObject();
+    let o2 = new g2.Object();
+    assert($vm.isHavingABadTime(g2), false);
+    assert($vm.isHavingABadTime(o2), false);
+
+    let g3 = $vm.createGlobalObject();
+    assert($vm.isHavingABadTime(g3), false);
+
+    o1.__proto__ = null;
+    g2.Array.prototype.__proto__ = o1;
+    o2.__proto__ = o1;
+    g3.Array.prototype.__proto__ = o2;
+    o0.__proto__ = o1;
+    assert($vm.isHavingABadTime(g0), false);
+    assert($vm.isHavingABadTime(g1), false);
+    assert($vm.isHavingABadTime(g2), false);
+    assert($vm.isHavingABadTime(g3), false);
+
+    $vm.haveABadTime(g1);
+
+    assert($vm.indexingMode(o0), "NonArray");
+    assert($vm.isHavingABadTime(g0), false);
+    assert($vm.isHavingABadTime(g1), true);
+    assert($vm.isHavingABadTime(g2), true);
+    assert($vm.isHavingABadTime(g2), true);
+})();
\ No newline at end of file
index 4cb359f..de666d4 100644 (file)
@@ -1,3 +1,122 @@
+2018-10-26  Mark Lam  <mark.lam@apple.com>
+
+        Fix missing edge cases with JSGlobalObjects having a bad time.
+        https://bugs.webkit.org/show_bug.cgi?id=189028
+        <rdar://problem/45204939>
+
+        Reviewed by Saam Barati.
+
+        Consider the following scenario:
+
+            let object O1 (of global G1) have an indexing type that is not SlowPut.
+            let global G2 have a bad time.
+            let object O2 (of global G2) be set as the prototype of O1.
+            let object O3 (of global G2) have indexed accessors.
+
+        In the existing code, if we set O3 as O2's prototype, we'll have a bug where
+        O1 will not be made aware that that there are indexed accessors in its prototype
+        chain.
+
+        In this patch, we solve this issue by introducing a new invariant:
+
+            A prototype chain is considered to possibly have indexed accessors if any
+            object in the chain belongs to a global object that is having a bad time.
+
+        We apply this invariant as follows:
+
+        1. Enhance JSGlobalObject::haveABadTime() to also check if other global objects are
+           affected by it having a bad time.  If so, it also ensures that those affected
+           global objects have a bad time.
+
+           The original code for JSGlobalObject::haveABadTime() uses a ObjectsWithBrokenIndexingFinder
+           to find all objects affected by the global object having a bad time.  We enhance
+           ObjectsWithBrokenIndexingFinder to also check for the possibility that any global
+           objects may be affected by other global objects having a bad time i.e.
+
+                let g1 = global1
+                let g2 = global2
+                let o1 = an object in g1
+                let o2 = an object in g2
+
+                let g1 have a bad time
+                g2 is affected if
+                    o1 is in the prototype chain of o2,
+                    and o2 may be a prototype.
+
+           If the ObjectsWithBrokenIndexingFinder does find the possibility of other global
+           objects being affected, it will abort its heap scan and let haveABadTime() take
+           a slow path to do a more complete multi global object scan.
+
+           The slow path works as follows:
+
+           1. Iterate the heap and record the graph of all global object dependencies.
+
+              For each global object, record the list of other global objects that are
+              affected by it.
+
+           2. Compute a list of global objects that need to have a bad time using the
+              current global object dependency graph.
+
+           3. For each global object in the list of affected global objects, fire their
+              HaveABadTime watchpoint and convert all their array structures to the
+              SlowPut alternatives.
+
+           4. Re-run ObjectsWithBrokenIndexingFinder to find all objects that are affected
+              by any of the globals in the list from (2).
+
+        2. Enhance Structure::mayInterceptIndexedAccesses() to also return true if the
+           structure's global object is having a bad time.
+
+        Note: there are 3 scenarios that we need to consider:
+
+            let g1 = global1
+            let g2 = global2
+            let o1 = an object in g1
+            let o2 = an object in g2
+
+            Scenario 1: o2 is a prototype, and
+                        g1 has a bad time after o1 is inserted into the o2's prototype chain.
+
+            Scenario 2: o2 is a prototype, and
+                        o1 is inserted into the o2's prototype chain after g1 has a bad time.
+
+            Scenario 3: o2 is NOT a prototype, and
+                        o1 is inserted into the o2's prototype chain after g1 has a bad time.
+
+            For scenario 1, when g1 has a bad time, we need to also make sure g2 has
+            a bad time.  This is handled by enhancement 1 above.
+
+            For scenario 2, when o1 is inserted into o2's prototype chain, we need to check
+            if o1's global object has a bad time.  If so, then we need to make sure o2's
+            global also has a bad time (because o2 is a prototype) and convert o2's
+            storage type to SlowPut.  This is handled by enhancement 2 above in conjunction
+            with JSObject::setPrototypeDirect().
+
+            For scenario 3, when o1 is inserted into o2's prototype chain, we need to check
+            if o1's global object has a bad time.  If so, then we only need to convert o2's
+            storage type to SlowPut (because o2 is NOT a prototype).  This is handled by
+            enhancement 2 above.
+
+        3. Also add $vm.isHavingABadTime(), $vm.createGlobalObject() to enable us to
+           write some tests for this issue.
+
+        * runtime/JSGlobalObject.cpp:
+        (JSC::JSGlobalObject::fireWatchpointAndMakeAllArrayStructuresSlowPut):
+        (JSC::JSGlobalObject::haveABadTime):
+        * runtime/JSGlobalObject.h:
+        * runtime/JSObject.h:
+        (JSC::JSObject::mayInterceptIndexedAccesses): Deleted.
+        * runtime/JSObjectInlines.h:
+        (JSC::JSObject::mayInterceptIndexedAccesses):
+        * runtime/Structure.h:
+        * runtime/StructureInlines.h:
+        (JSC::Structure::mayInterceptIndexedAccesses const):
+        * tools/JSDollarVM.cpp:
+        (JSC::functionHaveABadTime):
+        (JSC::functionIsHavingABadTime):
+        (JSC::functionCreateGlobalObject):
+        (JSC::JSDollarVM::finishCreation):
+
 2018-10-26  Keith Miller  <keith_miller@apple.com>
 
         JSC xcconfig should set DEFINES_MODULE
index 7bceaf2..a4fb84c 100644 (file)
@@ -1165,25 +1165,111 @@ static inline JSObject* lastInPrototypeChain(VM& vm, JSObject* object)
 // Private namespace for helpers for JSGlobalObject::haveABadTime()
 namespace {
 
+class GlobalObjectDependencyFinder : public MarkedBlock::VoidFunctor {
+public:
+    GlobalObjectDependencyFinder(VM& vm)
+        : m_vm(vm)
+    { }
+
+    IterationStatus operator()(HeapCell*, HeapCell::Kind) const;
+
+    void addDependency(JSGlobalObject* key, JSGlobalObject* dependent);
+    HashSet<JSGlobalObject*>* dependentsFor(JSGlobalObject* key);
+
+private:
+    void visit(JSObject*);
+
+    VM& m_vm;
+    HashMap<JSGlobalObject*, HashSet<JSGlobalObject*>> m_dependencies;
+};
+
+inline void GlobalObjectDependencyFinder::addDependency(JSGlobalObject* key, JSGlobalObject* dependent)
+{
+    auto keyResult = m_dependencies.add(key, HashSet<JSGlobalObject*>());
+    keyResult.iterator->value.add(dependent);
+}
+
+inline HashSet<JSGlobalObject*>* GlobalObjectDependencyFinder::dependentsFor(JSGlobalObject* key)
+{
+    auto iterator = m_dependencies.find(key);
+    if (iterator == m_dependencies.end())
+        return nullptr;
+    return &iterator->value;
+}
+
+inline void GlobalObjectDependencyFinder::visit(JSObject* object)
+{
+    VM& vm = m_vm;
+
+    if (!object->mayBePrototype())
+        return;
+
+    JSObject* current = object;
+    JSGlobalObject* objectGlobalObject = object->globalObject(vm);
+    do {
+        JSValue prototypeValue = current->getPrototypeDirect(vm);
+        if (prototypeValue.isNull())
+            return;
+        current = asObject(prototypeValue);
+
+        JSGlobalObject* protoGlobalObject = current->globalObject(vm);
+        if (protoGlobalObject != objectGlobalObject)
+            addDependency(protoGlobalObject, objectGlobalObject);
+    } while (true);
+}
+
+IterationStatus GlobalObjectDependencyFinder::operator()(HeapCell* cell, HeapCell::Kind kind) const
+{
+    if (isJSCellKind(kind) && static_cast<JSCell*>(cell)->isObject()) {
+        // FIXME: This const_cast exists because this isn't a C++ lambda.
+        // https://bugs.webkit.org/show_bug.cgi?id=159644
+        const_cast<GlobalObjectDependencyFinder*>(this)->visit(jsCast<JSObject*>(static_cast<JSCell*>(cell)));
+    }
+    return IterationStatus::Continue;
+}
+
+enum class BadTimeFinderMode {
+    SingleGlobal,
+    MultipleGlobals
+};
+
+template<BadTimeFinderMode mode>
 class ObjectsWithBrokenIndexingFinder : public MarkedBlock::VoidFunctor {
 public:
-    ObjectsWithBrokenIndexingFinder(MarkedArgumentBuffer&, JSGlobalObject*);
+    ObjectsWithBrokenIndexingFinder(VM&, Vector<JSObject*>&, JSGlobalObject*);
+    ObjectsWithBrokenIndexingFinder(VM&, Vector<JSObject*>&, HashSet<JSGlobalObject*>&);
+
+    bool needsMultiGlobalsScan() const { return m_needsMultiGlobalsScan; }
     IterationStatus operator()(HeapCell*, HeapCell::Kind) const;
 
 private:
-    void visit(JSCell*);
+    IterationStatus visit(JSObject*);
 
-    MarkedArgumentBuffer& m_foundObjects;
-    JSGlobalObject* m_globalObject;
+    VM& m_vm;
+    Vector<JSObject*>& m_foundObjects;
+    JSGlobalObject* m_globalObject { nullptr }; // Only used for SingleBadTimeGlobal mode.
+    HashSet<JSGlobalObject*>* m_globalObjects { nullptr }; // Only used for BadTimeGlobalGraph mode;
+    bool m_needsMultiGlobalsScan { false };
 };
 
-ObjectsWithBrokenIndexingFinder::ObjectsWithBrokenIndexingFinder(
-    MarkedArgumentBuffer& foundObjects, JSGlobalObject* globalObject)
-    : m_foundObjects(foundObjects)
+template<>
+ObjectsWithBrokenIndexingFinder<BadTimeFinderMode::SingleGlobal>::ObjectsWithBrokenIndexingFinder(
+    VM& vm, Vector<JSObject*>& foundObjects, JSGlobalObject* globalObject)
+    : m_vm(vm)
+    , m_foundObjects(foundObjects)
     , m_globalObject(globalObject)
 {
 }
 
+template<>
+ObjectsWithBrokenIndexingFinder<BadTimeFinderMode::MultipleGlobals>::ObjectsWithBrokenIndexingFinder(
+    VM& vm, Vector<JSObject*>& foundObjects, HashSet<JSGlobalObject*>& globalObjects)
+    : m_vm(vm)
+    , m_foundObjects(foundObjects)
+    , m_globalObjects(&globalObjects)
+{
+}
+
 inline bool hasBrokenIndexing(IndexingType type)
 {
     return type && !hasSlowPutArrayStorage(type);
@@ -1195,21 +1281,38 @@ inline bool hasBrokenIndexing(JSObject* object)
     return hasBrokenIndexing(type);
 }
 
-inline void ObjectsWithBrokenIndexingFinder::visit(JSCell* cell)
+template<BadTimeFinderMode mode>
+inline IterationStatus ObjectsWithBrokenIndexingFinder<mode>::visit(JSObject* object)
 {
-    if (!cell->isObject())
-        return;
-    
-    VM& vm = m_globalObject->vm();
+    VM& vm = m_vm;
 
     // We only want to have a bad time in the affected global object, not in the entire
     // VM. But we have to be careful, since there may be objects that claim to belong to
     // a different global object that have prototypes from our global object.
-    auto isInEffectedGlobalObject = [&] (JSObject* object) {
-        for (JSObject* current = object; ;) {
-            if (current->globalObject(vm) == m_globalObject)
+    auto isInAffectedGlobalObject = [&] (JSObject* object) {
+        JSGlobalObject* objectGlobalObject { nullptr };
+        bool objectMayBePrototype { false };
+
+        if (mode == BadTimeFinderMode::SingleGlobal) {
+            objectGlobalObject = object->globalObject(vm);
+            if (objectGlobalObject == m_globalObject)
                 return true;
-            
+
+            objectMayBePrototype = object->mayBePrototype();
+        }
+
+        for (JSObject* current = object; ;) {
+            JSGlobalObject* currentGlobalObject = current->globalObject(vm);
+            if (mode == BadTimeFinderMode::SingleGlobal) {
+                if (objectMayBePrototype && currentGlobalObject != objectGlobalObject)
+                    m_needsMultiGlobalsScan = true;
+                if (currentGlobalObject == m_globalObject)
+                    return true;
+            } else {
+                if (m_globalObjects->contains(currentGlobalObject))
+                    return true;
+            }
+
             JSValue prototypeValue = current->getPrototypeDirect(vm);
             if (prototypeValue.isNull())
                 return false;
@@ -1218,8 +1321,6 @@ inline void ObjectsWithBrokenIndexingFinder::visit(JSCell* cell)
         RELEASE_ASSERT_NOT_REACHED();
     };
 
-    JSObject* object = asObject(cell);
-
     if (JSFunction* function = jsDynamicCast<JSFunction*>(vm, object)) {
         if (FunctionRareData* rareData = function->rareData()) {
             // We only use this to cache JSFinalObjects. They do not start off with a broken indexing type.
@@ -1227,8 +1328,13 @@ inline void ObjectsWithBrokenIndexingFinder::visit(JSCell* cell)
 
             if (Structure* structure = rareData->internalFunctionAllocationStructure()) {
                 if (hasBrokenIndexing(structure->indexingType())) {
-                    bool isRelevantGlobalObject = (structure->globalObject() == m_globalObject)
-                        || (structure->hasMonoProto() && !structure->storedPrototype().isNull() && isInEffectedGlobalObject(asObject(structure->storedPrototype())));
+                    bool isRelevantGlobalObject =
+                        (mode == BadTimeFinderMode::SingleGlobal
+                            ? m_globalObject == structure->globalObject()
+                            : m_globalObjects->contains(structure->globalObject()))
+                        || (structure->hasMonoProto() && !structure->storedPrototype().isNull() && isInAffectedGlobalObject(asObject(structure->storedPrototype())));
+                    if (mode == BadTimeFinderMode::SingleGlobal && m_needsMultiGlobalsScan)
+                        return IterationStatus::Done; // Bailing early and let the MultipleGlobals path handle everything.
                     if (isRelevantGlobalObject)
                         rareData->clearInternalFunctionAllocationProfile();
                 }
@@ -1238,33 +1344,35 @@ inline void ObjectsWithBrokenIndexingFinder::visit(JSCell* cell)
 
     // Run this filter first, since it's cheap, and ought to filter out a lot of objects.
     if (!hasBrokenIndexing(object))
-        return;
-    
-    if (isInEffectedGlobalObject(object))
+        return IterationStatus::Continue;
+
+    if (isInAffectedGlobalObject(object))
         m_foundObjects.append(object);
+
+    if (mode == BadTimeFinderMode::SingleGlobal && m_needsMultiGlobalsScan)
+        return IterationStatus::Done; // Bailing early and let the MultipleGlobals path handle everything.
+
+    return IterationStatus::Continue;
 }
 
-IterationStatus ObjectsWithBrokenIndexingFinder::operator()(HeapCell* cell, HeapCell::Kind kind) const
+template<BadTimeFinderMode mode>
+IterationStatus ObjectsWithBrokenIndexingFinder<mode>::operator()(HeapCell* cell, HeapCell::Kind kind) const
 {
-    if (isJSCellKind(kind)) {
+    if (isJSCellKind(kind) && static_cast<JSCell*>(cell)->isObject()) {
         // FIXME: This const_cast exists because this isn't a C++ lambda.
         // https://bugs.webkit.org/show_bug.cgi?id=159644
-        const_cast<ObjectsWithBrokenIndexingFinder*>(this)->visit(static_cast<JSCell*>(cell));
+        return const_cast<ObjectsWithBrokenIndexingFinder*>(this)->visit(jsCast<JSObject*>(static_cast<JSCell*>(cell)));
     }
     return IterationStatus::Continue;
 }
 
 } // end private namespace for helpers for JSGlobalObject::haveABadTime()
 
-void JSGlobalObject::haveABadTime(VM& vm)
+void JSGlobalObject::fireWatchpointAndMakeAllArrayStructuresSlowPut(VM& vm)
 {
-    ASSERT(&vm == &this->vm());
-    
     if (isHavingABadTime())
         return;
 
-    vm.structureCache.clear(); // We may be caching array structures in here.
-
     // Make sure that all allocations or indexed storage transitions that are inlining
     // the assumption that it's safe to transition to a non-SlowPut array storage don't
     // do so anymore.
@@ -1284,16 +1392,118 @@ void JSGlobalObject::haveABadTime(VM& vm)
     m_regExpMatchesArrayWithGroupsStructure.set(vm, this, slowPutStructure);
     slowPutStructure = ClonedArguments::createSlowPutStructure(vm, this, m_objectPrototype.get());
     m_clonedArgumentsStructure.set(vm, this, slowPutStructure);
+};
+
+void JSGlobalObject::haveABadTime(VM& vm)
+{
+    ASSERT(&vm == &this->vm());
+    
+    if (isHavingABadTime())
+        return;
+
+    vm.structureCache.clear(); // We may be caching array structures in here.
 
-    // Make sure that all objects that have indexed storage switch to the slow kind of
-    // indexed storage.
-    MarkedArgumentBuffer foundObjects; // Use MarkedArgumentBuffer because switchToSlowPutArrayStorage() may GC.
-    ObjectsWithBrokenIndexingFinder finder(foundObjects, this);
+    DeferGC deferGC(vm.heap);
+
+    // Consider the following objects and prototype chains:
+    //    O (of global G1) -> A (of global G1)
+    //    B (of global G2) where G2 has a bad time
+    //
+    // If we set B as the prototype of A, G1 will need to have a bad time.
+    // See comments in Structure::mayInterceptIndexedAccesses() for why.
+    //
+    // Now, consider the following objects and prototype chains:
+    //    O1 (of global G1) -> A1 (of global G1) -> B1 (of global G2)
+    //    O2 (of global G2) -> A2 (of global G2)
+    //    B2 (of global G3) where G3 has a bad time.
+    //
+    // G1 and G2 does not have a bad time, but G3 already has a bad time.
+    // If we set B2 as the prototype of A2, then G2 needs to have a bad time.
+    // Note that by induction, G1 also now needs to have a bad time because of
+    // O1 -> A1 -> B1.
+    //
+    // We describe this as global G1 being affected by global G2, and G2 by G3.
+    // Similarly, we say that G1 is dependent on G2, and G2 on G3.
+    // Hence, when G3 has a bad time, we need to ensure that all globals that
+    // are transitively dependent on it also have a bad time (G2 and G1 in this
+    // example).
+    //
+    // Apart from clearing the VM structure cache above, there are 2 more things
+    // that we have to do when globals have a bad time:
+    // 1. For each affected global:
+    //    a. Fire its HaveABadTime watchpoint.
+    //    b. Convert all of its array structures to SlowPutArrayStorage.
+    // 2. Make sure that all affected objects  switch to the slow kind of
+    //    indexed storage. An object is considered to be affected if it has
+    //    indexed storage and has a prototype object which may have indexed
+    //    accessors. If the prototype object belongs to a global having a bad
+    //    time, then the prototype object is considered to possibly have indexed
+    //    accessors. See comments in Structure::mayInterceptIndexedAccesses()
+    //    for details.
+    //
+    // Note: step 1 must be completed before step 2 because step 2 relies on
+    // the HaveABadTime watchpoint having already been fired on all affected
+    // globals.
+    //
+    // In the common case, only this global will start having a bad time here,
+    // and no other globals are affected by it. So, we first proceed on this assumption
+    // with a simpler ObjectsWithBrokenIndexingFinder scan to find heap objects
+    // affected by this global that need to be converted to SlowPutArrayStorage.
+    // We'll also have the finder check for the presence of other global objects
+    // depending on this one.
+    //
+    // If we do discover other globals depending on this one, we'll abort this
+    // first ObjectsWithBrokenIndexingFinder scan because it will be insufficient
+    // to find all affected objects that need to be converted to SlowPutArrayStorage.
+    // It also does not make dependent globals have a bad time. Instead, we'll
+    // take a more comprehensive approach of first creating a dependency graph
+    // between globals, and then using that graph to determine all affected
+    // globals and objects. With that, we can make all affected globals have a
+    // bad time, and convert all affected objects to SlowPutArrayStorage.
+
+    fireWatchpointAndMakeAllArrayStructuresSlowPut(vm); // Step 1 above.
+    
+    Vector<JSObject*> foundObjects;
+    ObjectsWithBrokenIndexingFinder<BadTimeFinderMode::SingleGlobal> finder(vm, foundObjects, this);
     {
         HeapIterationScope iterationScope(vm.heap);
-        vm.heap.objectSpace().forEachLiveCell(iterationScope, finder);
+        vm.heap.objectSpace().forEachLiveCell(iterationScope, finder); // Attempt step 2 above.
+    }
+
+    if (finder.needsMultiGlobalsScan()) {
+        foundObjects.clear();
+
+        // Find all globals that will also have a bad time as a side effect of
+        // this global having a bad time.
+        GlobalObjectDependencyFinder dependencies(vm);
+        {
+            HeapIterationScope iterationScope(vm.heap);
+            vm.heap.objectSpace().forEachLiveCell(iterationScope, dependencies);
+        }
+
+        HashSet<JSGlobalObject*> globalsHavingABadTime;
+        Deque<JSGlobalObject*> globals;
+
+        globals.append(this);
+        while (!globals.isEmpty()) {
+            JSGlobalObject* global = globals.takeFirst();
+            global->fireWatchpointAndMakeAllArrayStructuresSlowPut(vm); // Step 1 above.
+            auto result = globalsHavingABadTime.add(global);
+            if (result.isNewEntry) {
+                if (HashSet<JSGlobalObject*>* dependents = dependencies.dependentsFor(global)) {
+                    for (JSGlobalObject* dependentGlobal : *dependents)
+                        globals.append(dependentGlobal);
+                }
+            }
+        }
+
+        ObjectsWithBrokenIndexingFinder<BadTimeFinderMode::MultipleGlobals> finder(vm, foundObjects, globalsHavingABadTime);
+        {
+            HeapIterationScope iterationScope(vm.heap);
+            vm.heap.objectSpace().forEachLiveCell(iterationScope, finder); // Step 2 above.
+        }
     }
-    RELEASE_ASSERT(!foundObjects.hasOverflowed());
+
     while (!foundObjects.isEmpty()) {
         JSObject* object = asObject(foundObjects.last());
         foundObjects.removeLast();
index b92606d..2cf557d 100644 (file)
@@ -962,6 +962,7 @@ protected:
 private:
     friend class LLIntOffsetsExtractor;
 
+    void fireWatchpointAndMakeAllArrayStructuresSlowPut(VM&);
     void setGlobalThis(VM&, JSObject* globalThis);
 
     JS_EXPORT_PRIVATE void init(VM&);
index 4d5fc83..12745e0 100644 (file)
@@ -159,11 +159,8 @@ public:
     bool setPrototype(VM&, ExecState*, JSValue prototype, bool shouldThrowIfCantSet = false);
     JS_EXPORT_PRIVATE static bool setPrototype(JSObject*, ExecState*, JSValue prototype, bool shouldThrowIfCantSet);
         
-    bool mayInterceptIndexedAccesses(VM& vm)
-    {
-        return structure(vm)->mayInterceptIndexedAccesses();
-    }
-        
+    inline bool mayInterceptIndexedAccesses(VM&);
+
     JSValue get(ExecState*, PropertyName) const;
     JSValue get(ExecState*, unsigned propertyName) const;
 
index 8cced91..1948479 100644 (file)
@@ -27,6 +27,7 @@
 #include "Error.h"
 #include "JSObject.h"
 #include "Lookup.h"
+#include "StructureInlines.h"
 
 namespace JSC {
 
@@ -172,6 +173,11 @@ inline bool JSObject::getOwnPropertySlotInline(ExecState* exec, PropertyName pro
     return JSObject::getOwnPropertySlot(this, exec, propertyName, slot);
 }
 
+inline bool JSObject::mayInterceptIndexedAccesses(VM& vm)
+{
+    return structure(vm)->mayInterceptIndexedAccesses();
+}
+
 inline void JSObject::putDirectWithoutTransition(VM& vm, PropertyName propertyName, JSValue value, unsigned attributes)
 {
     ASSERT(!value.isGetterSetter() && !(attributes & PropertyAttribute::Accessor));
index c73b5e3..b64e23a 100644 (file)
@@ -263,11 +263,8 @@ public:
     IndexingType indexingMode() const  { return m_blob.indexingModeIncludingHistory() & AllArrayTypes; }
     IndexingType indexingModeIncludingHistory() const { return m_blob.indexingModeIncludingHistory(); }
         
-    bool mayInterceptIndexedAccesses() const
-    {
-        return !!(indexingModeIncludingHistory() & MayHaveIndexedAccessors);
-    }
-        
+    inline bool mayInterceptIndexedAccesses() const;
+    
     bool holesMustForwardToPrototype(VM&, JSObject*) const;
         
     JSGlobalObject* globalObject() const { return m_globalObject.get(); }
index 1c94628..d76df87 100644 (file)
@@ -59,6 +59,29 @@ inline Structure* Structure::create(VM& vm, Structure* previous, DeferredStructu
     return newStructure;
 }
 
+inline bool Structure::mayInterceptIndexedAccesses() const
+{
+    if (indexingModeIncludingHistory() & MayHaveIndexedAccessors)
+        return true;
+
+    // Consider a scenario where object O (of global G1)'s prototype is set to A
+    // (of global G2), and G2 is already having a bad time. If an object B with
+    // indexed accessors is then set as the prototype of A:
+    //      O -> A -> B
+    // Then, O should be converted to SlowPutArrayStorage (because it now has an
+    // object with indexed accessors in its prototype chain). But it won't be
+    // converted because this conversion is done by JSGlobalObject::haveAbadTime(),
+    // but G2 is already having a bad time. We solve this by conservatively
+    // treating A as potentially having indexed accessors if its global is already
+    // having a bad time. Hence, when A is set as O's prototype, O will be
+    // converted to SlowPutArrayStorage.
+
+    JSGlobalObject* globalObject = this->globalObject();
+    if (!globalObject)
+        return false;
+    return globalObject->isHavingABadTime();
+}
+
 inline JSObject* Structure::storedPrototypeObject() const
 {
     ASSERT(hasMonoProto());
index f967781..add8f18 100644 (file)
@@ -1651,6 +1651,57 @@ static EncodedJSValue JSC_HOST_CALL functionGetPID(ExecState*)
     return JSValue::encode(jsNumber(getCurrentProcessID()));
 }
 
+// Make the globalObject have a bad time. Does nothing if the object is not a JSGlobalObject.
+// Usage: $vm.haveABadTime(globalObject)
+static EncodedJSValue JSC_HOST_CALL functionHaveABadTime(ExecState* exec)
+{
+    VM& vm = exec->vm();
+    JSLockHolder lock(vm);
+    JSValue objValue = exec->argument(0);
+    if (!objValue.isObject())
+        return JSValue::encode(jsBoolean(false));
+
+    JSObject* obj = asObject(objValue.asCell());
+    JSGlobalObject* globalObject = jsDynamicCast<JSGlobalObject*>(vm, obj);
+    if (!globalObject)
+        JSValue::encode(jsBoolean(false));
+
+    globalObject->haveABadTime(vm);
+    return JSValue::encode(jsBoolean(true));
+}
+
+// Checks if the object (or its global if the object is not a global) is having a bad time.
+// Usage: $vm.isHavingABadTime(obj)
+static EncodedJSValue JSC_HOST_CALL functionIsHavingABadTime(ExecState* exec)
+{
+    VM& vm = exec->vm();
+    JSLockHolder lock(vm);
+    JSValue objValue = exec->argument(0);
+    if (!objValue.isObject())
+        return JSValue::encode(jsUndefined());
+
+    JSObject* obj = asObject(objValue.asCell());
+    JSGlobalObject* globalObject = jsDynamicCast<JSGlobalObject*>(vm, obj);
+    if (globalObject)
+        JSValue::encode(jsBoolean(globalObject->isHavingABadTime()));
+
+    globalObject = obj->globalObject();
+    if (!globalObject)
+        return JSValue::encode(jsUndefined());
+
+    return JSValue::encode(jsBoolean(globalObject->isHavingABadTime()));
+}
+
+// Creates a new global object.
+// Usage: $vm.createGlobalObject()
+static EncodedJSValue JSC_HOST_CALL functionCreateGlobalObject(ExecState* exec)
+{
+    VM& vm = exec->vm();
+    JSLockHolder lock(vm);
+    JSGlobalObject* globalObject = JSGlobalObject::create(vm, JSGlobalObject::createStructure(vm, jsNull()));
+    return JSValue::encode(globalObject);
+}
+
 static EncodedJSValue JSC_HOST_CALL functionCreateProxy(ExecState* exec)
 {
     VM& vm = exec->vm();
@@ -2144,6 +2195,10 @@ void JSDollarVM::finishCreation(VM& vm)
     addFunction(vm, "value", functionValue, 1);
     addFunction(vm, "getpid", functionGetPID, 0);
 
+    addFunction(vm, "haveABadTime", functionHaveABadTime, 1);
+    addFunction(vm, "isHavingABadTime", functionIsHavingABadTime, 1);
+
+    addFunction(vm, "createGlobalObject", functionCreateGlobalObject, 0);
     addFunction(vm, "createProxy", functionCreateProxy, 1);
     addFunction(vm, "createRuntimeArray", functionCreateRuntimeArray, 0);