Changeset 255897 in webkit


Ignore:
Timestamp:
Feb 5, 2020 7:48:34 PM (4 years ago)
Author:
Justin Michaud
Message:

Deleting a property should not turn structures into uncacheable dictionaries
​https://bugs.webkit.org/show_bug.cgi?id=206430

Reviewed by Yusuke Suzuki.

JSTests:

  • microbenchmarks/delete-property-from-prototype-chain.js: Added.

(assert):
(noInline.assert.getZ):
(noInline.getZ.C):
(doTest):
(delete.C.prototype.z):

  • microbenchmarks/delete-property-keeps-cacheable-structure.js: Added.

(assert):
(C):
(doTest):

  • stress/cache-put-by-id-different-attributes.js:

(makePrototypeDict):
(set x):

  • stress/cache-put-by-id-different-offset.js:

(makePrototypeDict):
(set x):

  • stress/cache-put-by-id-poly-proto.js:

(makePrototypeDict):
(set _):

  • stress/delete-property-check-structure-transition.js: Added.

(assert):
(assert_eq):
(assert_neq):
(sd):
(sid):
(testDeleteIsNotUncacheable):
(testCanMaterializeDeletes):
(testCanFlatten):
(testDeleteWithInlineCache.Object.prototype.globalProperty.42.makeFoo):
(testDeleteWithInlineCache.noInline.doTest):
(testDeleteWithInlineCache):

  • stress/flatten-object-zero-unused-inline-properties.js:

Source/JavaScriptCore:

Right now, deleteProperty/removePropertyTransition causes a structure transition to uncacheable dictionary. Instead, we should allow it to transition to a new regular structure like adding a property does. This means that we have to:

1) Break the assumption that structure transition offsets increase monotonically

We add a new flag to tell that a structure has deleted its property, and update materializePropertyTable to use it.

2) Add a new transition map and transition kind for deletes

We cache the delete transition. We will not transition back to a previous structure if you add then immediately remove a property.

3) Find some heuristic for when we should actually transition to uncacheable dictionary.

Since deleting properties is expected to be rare, we just walk the structure list and count its size on removal.

This patch also fixes a related bug in addProperty, where we did not use a GCSafeConcurrentJSLocker, and adds an option to trigger the bug. Finally, we add some helper methods to dollarVM to test.

This gives a 24x speedup on delete-property-keeps-cacheable-structure.js, and is neutral on delete-property-from-prototype-chain.js (which was already generating code using the inline cache).

  • heap/HeapInlines.h:

(JSC::Heap::decrementDeferralDepthAndGCIfNeeded):

  • runtime/JSObject.cpp:

(JSC::JSObject::deleteProperty):

  • runtime/OptionsList.h:
  • runtime/PropertyMapHashTable.h:

(JSC::PropertyTable::get):
(JSC::PropertyTable::add):
(JSC::PropertyTable::addDeletedOffset):
(JSC::PropertyTable::reinsert):

  • runtime/Structure.cpp:

(JSC::StructureTransitionTable::contains const):
(JSC::StructureTransitionTable::get const):
(JSC::StructureTransitionTable::add):
(JSC::Structure::Structure):
(JSC::Structure::materializePropertyTable):
(JSC::Structure::addNewPropertyTransition):
(JSC::Structure::removePropertyTransition):
(JSC::Structure::removePropertyTransitionFromExistingStructure):
(JSC::Structure::removeNewPropertyTransition):
(JSC::Structure::toUncacheableDictionaryTransition):
(JSC::Structure::remove):
(JSC::Structure::visitChildren):

  • runtime/Structure.h:
  • runtime/StructureInlines.h:

(JSC::Structure::forEachPropertyConcurrently):
(JSC::Structure::add):
(JSC::Structure::remove):
(JSC::Structure::removePropertyWithoutTransition):

  • runtime/StructureTransitionTable.h:

(JSC::StructureTransitionTable::Hash::hash):

  • tools/JSDollarVM.cpp:

(JSC::JSDollarVMHelper::functionGetStructureTransitionList):
(JSC::functionGetConcurrently):
(JSC::JSDollarVM::finishCreation):

Location:
trunk
Files:
3 added
15 edited

Legend:

Unmodified
Added
Removed

  • trunk/JSTests/ChangeLog

    r255689 r255897  
     12020-02-05  Justin Michaud  <justin_michaud@apple.com>
     2
     3        Deleting a property should not turn structures into uncacheable dictionaries
     4        https://bugs.webkit.org/show_bug.cgi?id=206430
     5
     6        Reviewed by Yusuke Suzuki.
     7
     8        * microbenchmarks/delete-property-from-prototype-chain.js: Added.
     9        (assert):
     10        (noInline.assert.getZ):
     11        (noInline.getZ.C):
     12        (doTest):
     13        (delete.C.prototype.z):
     14        * microbenchmarks/delete-property-keeps-cacheable-structure.js: Added.
     15        (assert):
     16        (C):
     17        (doTest):
     18        * stress/cache-put-by-id-different-attributes.js:
     19        (makePrototypeDict):
     20        (set x):
     21        * stress/cache-put-by-id-different-offset.js:
     22        (makePrototypeDict):
     23        (set x):
     24        * stress/cache-put-by-id-poly-proto.js:
     25        (makePrototypeDict):
     26        (set _):
     27        * stress/delete-property-check-structure-transition.js: Added.
     28        (assert):
     29        (assert_eq):
     30        (assert_neq):
     31        (sd):
     32        (sid):
     33        (testDeleteIsNotUncacheable):
     34        (testCanMaterializeDeletes):
     35        (testCanFlatten):
     36        (testDeleteWithInlineCache.Object.prototype.globalProperty.42.makeFoo):
     37        (testDeleteWithInlineCache.noInline.doTest):
     38        (testDeleteWithInlineCache):
     39        * stress/flatten-object-zero-unused-inline-properties.js:
     40
    1412020-02-04  Alexey Shvayka  <shvaikalesh@gmail.com>
    242

  • trunk/JSTests/stress/cache-put-by-id-different-attributes.js

    r245018 r255897  
    44
    55Foo.prototype.x = 0;
     6
     7function makePrototypeDict() {
     8    for (let i=0; i<100; ++i) {
     9        Foo.prototype.a = i
     10        Foo.prototype.b = i
     11        delete Foo.prototype.a
     12        delete Foo.prototype.b
     13    }
     14}
     15noInline(makePrototypeDict)
    616
    717Object.defineProperty(Foo.prototype, 'y', {
    … …  
    1222                writable: true,
    1323            });
    14             if (typeof $vm !== 'undefined')
     24            if (typeof $vm !== 'undefined') {
     25                makePrototypeDict()
    1526                $vm.flattenDictionaryObject(Foo.prototype);
     27            }
    1628        }
    1729    },

  • trunk/JSTests/stress/cache-put-by-id-different-offset.js

    r245018 r255897  
    55Foo.prototype.x = 0;
    66
     7function makePrototypeDict() {
     8    for (let i=0; i<100; ++i) {
     9        Foo.prototype.a = i
     10        Foo.prototype.b = i
     11        delete Foo.prototype.a
     12        delete Foo.prototype.b
     13    }
     14}
     15noInline(makePrototypeDict)
     16
    717Object.defineProperty(Foo.prototype, 'y', {
    818    set(x) {
    919        if (Foo.prototype.x++ === 1) {
    1020            delete Foo.prototype.x;
    11             if (typeof $vm !== 'undefined')
     21            if (typeof $vm !== 'undefined') {
     22                makePrototypeDict()
    1223                $vm.flattenDictionaryObject(Foo.prototype);
     24            }
    1325        }
    1426    }

  • trunk/JSTests/stress/cache-put-by-id-poly-proto.js

    r245018 r255897  
    44
    55let x = 0;
     6
     7function makePrototypeDict() {
     8    for (let i=0; i<100; ++i) {
     9        Foo.prototype.a = i
     10        Foo.prototype.b = i
     11        delete Foo.prototype.a
     12        delete Foo.prototype.b
     13    }
     14}
     15noInline(makePrototypeDict)
    616
    717Object.defineProperty(Foo.prototype, 'y', {
    … …  
    1222                writable: true,
    1323            });
    14             if (typeof $vm !== 'undefined')
     24            if (typeof $vm !== 'undefined') {
     25                makePrototypeDict()
    1526                $vm.flattenDictionaryObject(Foo.prototype);
     27            }
    1628        }
    1729    },

  • trunk/JSTests/stress/flatten-object-zero-unused-inline-properties.js

    r233048 r255897  
    11let o = { foo: 1, bar: 2, baz: 3 };
     2for (let i=0; i<100; ++i) {
     3    o.a = i
     4    o.b = i
     5    delete o.a
     6    delete o.b
     7}
    28if ($vm.inlineCapacity(o) <= 3)
    39    throw new Error("There should be inline capacity");

  • trunk/Source/JavaScriptCore/ChangeLog

    r255887 r255897  
     12020-02-05  Justin Michaud  <justin_michaud@apple.com>
     2
     3        Deleting a property should not turn structures into uncacheable dictionaries
     4        https://bugs.webkit.org/show_bug.cgi?id=206430
     5
     6        Reviewed by Yusuke Suzuki.
     7
     8        Right now, deleteProperty/removePropertyTransition causes a structure transition to uncacheable dictionary. Instead, we should allow it to transition to a new regular structure like adding a property does. This means that we have to:
     9
     10        1) Break the assumption that structure transition offsets increase monotonically
     11
     12        We add a new flag to tell that a structure has deleted its property, and update materializePropertyTable to use it.
     13
     14        2) Add a new transition map and transition kind for deletes
     15
     16        We cache the delete transition. We will not transition back to a previous structure if you add then immediately remove a property.
     17
     18        3) Find some heuristic for when we should actually transition to uncacheable dictionary.
     19
     20        Since deleting properties is expected to be rare, we just walk the structure list and count its size on removal.
     21
     22        This patch also fixes a related bug in addProperty, where we did not use a GCSafeConcurrentJSLocker, and adds an option to trigger the bug. Finally, we add some helper methods to dollarVM to test.
     23
     24        This gives a 24x speedup on delete-property-keeps-cacheable-structure.js, and is neutral on delete-property-from-prototype-chain.js (which was already generating code using the inline cache).
     25
     26        * heap/HeapInlines.h:
     27        (JSC::Heap::decrementDeferralDepthAndGCIfNeeded):
     28        * runtime/JSObject.cpp:
     29        (JSC::JSObject::deleteProperty):
     30        * runtime/OptionsList.h:
     31        * runtime/PropertyMapHashTable.h:
     32        (JSC::PropertyTable::get):
     33        (JSC::PropertyTable::add):
     34        (JSC::PropertyTable::addDeletedOffset):
     35        (JSC::PropertyTable::reinsert):
     36        * runtime/Structure.cpp:
     37        (JSC::StructureTransitionTable::contains const):
     38        (JSC::StructureTransitionTable::get const):
     39        (JSC::StructureTransitionTable::add):
     40        (JSC::Structure::Structure):
     41        (JSC::Structure::materializePropertyTable):
     42        (JSC::Structure::addNewPropertyTransition):
     43        (JSC::Structure::removePropertyTransition):
     44        (JSC::Structure::removePropertyTransitionFromExistingStructure):
     45        (JSC::Structure::removeNewPropertyTransition):
     46        (JSC::Structure::toUncacheableDictionaryTransition):
     47        (JSC::Structure::remove):
     48        (JSC::Structure::visitChildren):
     49        * runtime/Structure.h:
     50        * runtime/StructureInlines.h:
     51        (JSC::Structure::forEachPropertyConcurrently):
     52        (JSC::Structure::add):
     53        (JSC::Structure::remove):
     54        (JSC::Structure::removePropertyWithoutTransition):
     55        * runtime/StructureTransitionTable.h:
     56        (JSC::StructureTransitionTable::Hash::hash):
     57        * tools/JSDollarVM.cpp:
     58        (JSC::JSDollarVMHelper::functionGetStructureTransitionList):
     59        (JSC::functionGetConcurrently):
     60        (JSC::JSDollarVM::finishCreation):
     61
    1622020-02-05  Devin Rousso  <drousso@apple.com>
    263

  • trunk/Source/JavaScriptCore/heap/HeapInlines.h

    r252302 r255897  
    189189    m_deferralDepth--;
    190190   
    191     if (UNLIKELY(m_didDeferGCWork)) {
     191    if (UNLIKELY(m_didDeferGCWork) || Options::forceDidDeferGCWork()) {
    192192        decrementDeferralDepthAndGCIfNeededSlow();
    193193       

  • trunk/Source/JavaScriptCore/runtime/JSObject.cpp

    r254760 r255897  
    20022002        if (attributes & PropertyAttribute::DontDelete && vm.deletePropertyMode() != VM::DeletePropertyMode::IgnoreConfigurable)
    20032003            return false;
    2004 
    2005         PropertyOffset offset;
     2004        DeferredStructureTransitionWatchpointFire deferredWatchpointFire(vm, structure);
     2005
     2006        PropertyOffset offset = invalidOffset;
    20062007        if (structure->isUncacheableDictionary())
    2007             offset = structure->removePropertyWithoutTransition(vm, propertyName, [] (const ConcurrentJSLocker&, PropertyOffset) { });
    2008         else
    2009             thisObject->setStructure(vm, Structure::removePropertyTransition(vm, structure, propertyName, offset));
     2008            offset = structure->removePropertyWithoutTransition(vm, propertyName, [] (const GCSafeConcurrentJSLocker&, PropertyOffset, PropertyOffset) { });
     2009        else {
     2010            structure = Structure::removePropertyTransition(vm, structure, propertyName, offset, &deferredWatchpointFire);
     2011            if (thisObject->m_butterfly && !structure->outOfLineCapacity() && !structure->hasIndexingHeader(thisObject)) {
     2012                thisObject->nukeStructureAndSetButterfly(vm, thisObject->structureID(), nullptr);
     2013                offset = invalidOffset;
     2014                ASSERT(structure->maxOffset() == invalidOffset);
     2015            }
     2016            thisObject->setStructure(vm, structure);
     2017        }
     2018
     2019        ASSERT(!isValidOffset(structure->get(vm, propertyName, attributes)));
    20102020
    20112021        if (offset != invalidOffset)

  • trunk/Source/JavaScriptCore/runtime/OptionsList.h

    r255406 r255897  
    348348    v(Bool, gcAtEnd, false, Normal, "If true, the jsc CLI will do a GC before exiting") \
    349349    v(Bool, forceGCSlowPaths, false, Normal, "If true, we will force all JIT fast allocations down their slow paths.") \
     350    v(Bool, forceDidDeferGCWork, false, Normal, "If true, we will force all DeferGC destructions to perform a GC.") \
    350351    v(Unsigned, gcMaxHeapSize, 0, Normal, nullptr) \
    351352    v(Unsigned, forceRAMSize, 0, Normal, nullptr) \

  • trunk/Source/JavaScriptCore/runtime/PropertyMapHashTable.h

    r253987 r255897  
    170170    ValueType* get(const KeyType&);
    171171    // Add a value to the table
    172     enum EffectOnPropertyOffset { PropertyOffsetMayChange, PropertyOffsetMustNotChange };
    173     std::pair<find_iterator, bool> add(const ValueType& entry, PropertyOffset&, EffectOnPropertyOffset);
     172    std::pair<find_iterator, bool> WARN_UNUSED_RETURN add(const ValueType& entry);
    174173    // Remove a value from the table.
    175174    void remove(const find_iterator& iter);
    … …  
    322321    ASSERT(key);
    323322    ASSERT(key->isAtom() || key->isSymbol());
     323    ASSERT(key != PROPERTY_MAP_DELETED_ENTRY_KEY);
    324324
    325325    if (!m_keyCount)
    … …  
    336336        if (entryIndex == EmptyEntryIndex)
    337337            return nullptr;
    338         if (key == table()[entryIndex - 1].key)
     338        if (key == table()[entryIndex - 1].key) {
     339            ASSERT(!m_deletedOffsets || !m_deletedOffsets->contains(table()[entryIndex - 1].offset));
    339340            return &table()[entryIndex - 1];
     341        }
    340342
    341343#if DUMP_PROPERTYMAP_STATS
    … …  
    347349}
    348350
    349 inline std::pair<PropertyTable::find_iterator, bool> PropertyTable::add(const ValueType& entry, PropertyOffset& offset, EffectOnPropertyOffset offsetEffect)
    350 {
     351inline std::pair<PropertyTable::find_iterator, bool> WARN_UNUSED_RETURN PropertyTable::add(const ValueType& entry)
     352{
     353    ASSERT(!m_deletedOffsets || !m_deletedOffsets->contains(entry.offset));
     354
    351355    // Look for a value with a matching key already in the array.
    352356    find_iterator iter = find(entry.key);
    353     if (iter.first) {
    354         RELEASE_ASSERT(iter.first->offset <= offset);
     357    if (iter.first)
    355358        return std::make_pair(iter, false);
    356     }
    357359
    358360#if DUMP_PROPERTYMAP_STATS
    … …  
    378380    ++m_keyCount;
    379381   
    380     if (offsetEffect == PropertyOffsetMayChange)
    381         offset = std::max(offset, entry.offset);
    382     else
    383         RELEASE_ASSERT(offset >= entry.offset);
    384    
    385382    return std::make_pair(iter, true);
    386383}
    … …  
    452449    if (!m_deletedOffsets)
    453450        m_deletedOffsets = makeUnique<Vector<PropertyOffset>>();
     451    ASSERT(!m_deletedOffsets->contains(offset));
    454452    m_deletedOffsets->append(offset);
    455453}

  • trunk/Source/JavaScriptCore/runtime/Structure.cpp

    r255365 r255897  
    8888}
    8989
    90 bool StructureTransitionTable::contains(UniquedStringImpl* rep, unsigned attributes) const
     90bool StructureTransitionTable::contains(UniquedStringImpl* rep, unsigned attributes, bool isAddition) const
    9191{
    9292    if (isUsingSingleSlot()) {
    9393        Structure* transition = singleTransition();
    94         return transition && transition->m_transitionPropertyName == rep && transition->transitionPropertyAttributes() == attributes;
    95     }
    96     return map()->get(std::make_pair(rep, attributes));
    97 }
    98 
    99 inline Structure* StructureTransitionTable::get(UniquedStringImpl* rep, unsigned attributes) const
     94        return transition && transition->m_transitionPropertyName == rep && transition->transitionPropertyAttributes() == attributes && transition->isPropertyDeletionTransition() == !isAddition;
     95    }
     96    return map()->get(std::make_tuple(rep, attributes, isAddition));
     97}
     98
     99inline Structure* StructureTransitionTable::get(UniquedStringImpl* rep, unsigned attributes, bool isAddition) const
    100100{
    101101    if (isUsingSingleSlot()) {
    102102        Structure* transition = singleTransition();
    103         return (transition && transition->m_transitionPropertyName == rep && transition->transitionPropertyAttributes() == attributes) ? transition : 0;
    104     }
    105     return map()->get(std::make_pair(rep, attributes));
     103        return (transition && transition->m_transitionPropertyName == rep && transition->transitionPropertyAttributes() == attributes && transition->isPropertyDeletionTransition() == !isAddition) ? transition : 0;
     104    }
     105    return map()->get(std::make_tuple(rep, attributes, isAddition));
    106106}
    107107
    … …  
    128128    // When either of the parameters are bitfields, the C++ compiler will try to bind them as lvalues, which is invalid. To work around this, use unary "+" to make the parameter an rvalue.
    129129    // See https://bugs.webkit.org/show_bug.cgi?id=59261 for more details
    130     map()->set(std::make_pair(structure->m_transitionPropertyName.get(), +structure->transitionPropertyAttributes()), structure);
     130    map()->set(std::make_tuple(structure->m_transitionPropertyName.get(), +structure->transitionPropertyAttributes(), !structure->isPropertyDeletionTransition()), structure);
    131131}
    132132
    … …  
    201201    setTransitionWatchpointIsLikelyToBeFired(false);
    202202    setHasBeenDictionary(false);
    203     setIsAddingPropertyForTransition(false);
     203    setProtectPropertyTableWhileTransitioning(false);
     204    setIsPropertyDeletionTransition(false);
    204205    setTransitionOffset(vm, invalidOffset);
    205206    setMaxOffset(vm, invalidOffset);
    … …  
    237238    setTransitionWatchpointIsLikelyToBeFired(false);
    238239    setHasBeenDictionary(false);
    239     setIsAddingPropertyForTransition(false);
     240    setProtectPropertyTableWhileTransitioning(false);
     241    setIsPropertyDeletionTransition(false);
    240242    setTransitionOffset(vm, invalidOffset);
    241243    setMaxOffset(vm, invalidOffset);
    … …  
    273275    setStaticPropertiesReified(previous->staticPropertiesReified());
    274276    setHasBeenDictionary(previous->hasBeenDictionary());
    275     setIsAddingPropertyForTransition(false);
     277    setProtectPropertyTableWhileTransitioning(false);
     278    setIsPropertyDeletionTransition(false);
    276279    setTransitionOffset(vm, invalidOffset);
    277280    setMaxOffset(vm, invalidOffset);
    … …  
    357360{
    358361    ASSERT(structure(vm)->classInfo() == info());
    359     ASSERT(!isAddingPropertyForTransition());
     362    ASSERT(!protectPropertyTableWhileTransitioning());
    360363   
    361364    DeferGC deferGC(vm.heap);
    … …  
    385388        if (!structure->m_transitionPropertyName)
    386389            continue;
    387         ASSERT(i == structures.size() - 1 || structure->maxOffset() > structures[i + 1]->maxOffset());
     390        if (structure->isPropertyDeletionTransition()) {
     391            auto item = table->find(structure->m_transitionPropertyName.get());
     392            ASSERT(item.first);
     393            table->remove(item);
     394            table->addDeletedOffset(structure->transitionOffset());
     395            continue;
     396        }
    388397        PropertyMapEntry entry(structure->m_transitionPropertyName.get(), structure->transitionOffset(), structure->transitionPropertyAttributes());
    389         auto maxOffset = this->maxOffset();
    390         table->add(entry, maxOffset, PropertyTable::PropertyOffsetMustNotChange);
     398        auto nextOffset = table->nextOffset(structure->inlineCapacity());
     399        ASSERT_UNUSED(nextOffset, nextOffset == structure->transitionOffset());
     400        auto result = table->add(entry);
     401        ASSERT_UNUSED(result, result.second);
     402        ASSERT_UNUSED(result, result.first.first->offset == nextOffset);
    391403    }
    392404   
    … …  
    411423    ASSERT(structure->isObject());
    412424
    413     if (Structure* existingTransition = structure->m_transitionTable.get(uid, attributes)) {
     425    constexpr bool isAddition = true;
     426    if (Structure* existingTransition = structure->m_transitionTable.get(uid, attributes, isAddition)) {
    414427        validateOffset(existingTransition->transitionOffset(), existingTransition->inlineCapacity());
    415428        offset = existingTransition->transitionOffset();
    … …  
    485498        ASSERT(structure != transition);
    486499        offset = transition->add(vm, propertyName, attributes);
    487         transition->setTransitionOffset(vm, offset);
    488500        return transition;
    489501    }
    … …  
    501513    // which case the GC will not blow the table away, or we do it after the GC already ran in which
    502514    // case all is well.  If it wasn't for the lock, the GC would have TOCTOU: if could read
    503     // isAddingPropertyForTransition before we set it to true, and then blow the table away after.
     515    // protectPropertyTableWhileTransitioning before we set it to true, and then blow the table away after.
    504516    {
    505517        ConcurrentJSLocker locker(transition->m_lock);
    506         transition->setIsAddingPropertyForTransition(true);
     518        transition->setProtectPropertyTableWhileTransitioning(true);
    507519    }
    508520
    … …  
    519531    // table away if it wants. We can now rebuild it fine.
    520532    WTF::storeStoreFence();
    521     transition->setIsAddingPropertyForTransition(false);
     533    transition->setProtectPropertyTableWhileTransitioning(false);
    522534
    523535    checkOffset(transition->transitionOffset(), transition->inlineCapacity());
    524536    {
    525         ConcurrentJSLocker locker(structure->m_lock);
    526         DeferGC deferGC(vm.heap);
     537        GCSafeConcurrentJSLocker locker(structure->m_lock, vm.heap);
    527538        structure->m_transitionTable.add(vm, transition);
    528539    }
    … …  
    532543}
    533544
    534 Structure* Structure::removePropertyTransition(VM& vm, Structure* structure, PropertyName propertyName, PropertyOffset& offset)
    535 {
    536     // NOTE: There are some good reasons why this goes directly to uncacheable dictionary rather than
    537     // caching the removal. We can fix all of these things, but we must remember to do so, if we ever try
    538     // to optimize this case.
    539     //
    540     // - Cached transitions usually steal the property table, and assume that this is possible because they
    541     //   can just rebuild the table by looking at past transitions. That code assumes that the table only
    542     //   grew and never shrank. To support removals, we'd have to change the property table materialization
    543     //   code to handle deletions. Also, we have logic to get the list of properties on a structure that
    544     //   lacks a property table by just looking back through the set of transitions since the last
    545     //   structure that had a pinned table. That logic would also have to be changed to handle cached
    546     //   removals.
    547     //
     545Structure* Structure::removePropertyTransition(VM& vm, Structure* structure, PropertyName propertyName, PropertyOffset& offset, DeferredStructureTransitionWatchpointFire* deferred)
     546{
     547    Structure* newStructure = removePropertyTransitionFromExistingStructure(
     548        vm, structure, propertyName, offset, deferred);
     549    if (newStructure)
     550        return newStructure;
     551
     552    return removeNewPropertyTransition(
     553        vm, structure, propertyName, offset, deferred);
     554}
     555
     556Structure* Structure::removePropertyTransitionFromExistingStructure(VM& vm, Structure* structure, PropertyName propertyName, PropertyOffset& offset, DeferredStructureTransitionWatchpointFire*)
     557{
     558    ASSERT(!isCompilationThread());
    548559    ASSERT(!structure->isUncacheableDictionary());
    549 
    550     Structure* transition = toUncacheableDictionaryTransition(vm, structure);
    551 
    552     offset = transition->remove(propertyName);
    553 
     560    ASSERT(structure->isObject());
     561
     562    unsigned attributes;
     563    structure->get(vm, propertyName, attributes);
     564
     565    constexpr bool isAddition = false;
     566    if (Structure* existingTransition = structure->m_transitionTable.get(propertyName.uid(), attributes, isAddition)) {
     567        validateOffset(existingTransition->transitionOffset(), existingTransition->inlineCapacity());
     568        offset = existingTransition->transitionOffset();
     569        return existingTransition;
     570    }
     571
     572    return nullptr;
     573}
     574
     575Structure* Structure::removeNewPropertyTransition(VM& vm, Structure* structure, PropertyName propertyName, PropertyOffset& offset, DeferredStructureTransitionWatchpointFire* deferred)
     576{
     577    ASSERT(!structure->isUncacheableDictionary());
     578    ASSERT(structure->isObject());
     579    ASSERT(!Structure::removePropertyTransitionFromExistingStructure(vm, structure, propertyName, offset, deferred));
     580
     581    int transitionCount = 0;
     582    for (auto* s = structure; s && transitionCount <= s_maxTransitionLength; s = s->previousID())
     583        ++transitionCount;
     584
     585    if (transitionCount > s_maxTransitionLength) {
     586        ASSERT(!isCopyOnWrite(structure->indexingMode()));
     587        Structure* transition = toUncacheableDictionaryTransition(vm, structure, deferred);
     588        ASSERT(structure != transition);
     589        offset = transition->remove(vm, propertyName);
     590        return transition;
     591    }
     592
     593    Structure* transition = create(vm, structure, deferred);
     594    transition->m_cachedPrototypeChain.setMayBeNull(vm, transition, structure->m_cachedPrototypeChain.get());
     595
     596    // While we are deleting the property, we need to make sure the table is not cleared.
     597    {
     598        ConcurrentJSLocker locker(transition->m_lock);
     599        transition->setProtectPropertyTableWhileTransitioning(true);
     600    }
     601
     602    transition->m_blob.setIndexingModeIncludingHistory(structure->indexingModeIncludingHistory() & ~CopyOnWrite);
     603    transition->m_transitionPropertyName = propertyName.uid();
     604    transition->setPropertyTable(vm, structure->takePropertyTableOrCloneIfPinned(vm));
     605    transition->setMaxOffset(vm, structure->maxOffset());
     606    transition->setIsPropertyDeletionTransition(true);
     607
     608    offset = transition->remove(vm, propertyName);
     609    ASSERT(offset != invalidOffset);
     610    transition->setTransitionOffset(vm, offset);
     611
     612    // Now that everything is fine with the new structure's bookkeeping, the GC is free to blow the
     613    // table away if it wants. We can now rebuild it fine.
     614    WTF::storeStoreFence();
     615    transition->setProtectPropertyTableWhileTransitioning(false);
     616
     617    checkOffset(transition->transitionOffset(), transition->inlineCapacity());
     618    {
     619        GCSafeConcurrentJSLocker locker(structure->m_lock, vm.heap);
     620        structure->m_transitionTable.add(vm, transition);
     621    }
    554622    transition->checkOffsetConsistency();
     623    structure->checkOffsetConsistency();
    555624    return transition;
    556625}
    … …  
    615684}
    616685
    617 Structure* Structure::toUncacheableDictionaryTransition(VM& vm, Structure* structure)
    618 {
    619     return toDictionaryTransition(vm, structure, UncachedDictionaryKind);
     686Structure* Structure::toUncacheableDictionaryTransition(VM& vm, Structure* structure, DeferredStructureTransitionWatchpointFire* deferred)
     687{
     688    return toDictionaryTransition(vm, structure, UncachedDictionaryKind, deferred);
    620689}
    621690
    … …  
    656725   
    657726    Structure* existingTransition;
    658     if (!structure->isDictionary() && (existingTransition = structure->m_transitionTable.get(0, attributes))) {
     727    constexpr bool isAddition = true;
     728    if (!structure->isDictionary() && (existingTransition = structure->m_transitionTable.get(0, attributes, isAddition))) {
    659729        ASSERT(existingTransition->transitionPropertyAttributes() == attributes);
    660730        ASSERT(existingTransition->indexingModeIncludingHistory() == indexingModeIncludingHistory);
    … …  
    9781048}
    9791049
    980 PropertyOffset Structure::remove(PropertyName propertyName)
    981 {
    982     return remove(propertyName, [] (const ConcurrentJSLocker&, PropertyOffset) { });
     1050PropertyOffset Structure::remove(VM& vm, PropertyName propertyName)
     1051{
     1052    return remove<ShouldPin::No>(vm, propertyName, [this, &vm] (const GCSafeConcurrentJSLocker&, PropertyOffset, PropertyOffset newMaxOffset) {
     1053        setMaxOffset(vm, newMaxOffset);
     1054    });
    9831055}
    9841056
    … …  
    10601132    visitor.append(thisObject->m_previousOrRareData);
    10611133
    1062     if (thisObject->isPinnedPropertyTable() || thisObject->isAddingPropertyForTransition()) {
     1134    if (thisObject->isPinnedPropertyTable() || thisObject->protectPropertyTableWhileTransitioning()) {
    10631135        // NOTE: This can interleave in pin(), in which case it may see a null property table.
    10641136        // That's fine, because then the barrier will fire and we will scan this again.

  • trunk/Source/JavaScriptCore/runtime/Structure.h

    r255788 r255897  
    190190    static Structure* addPropertyTransitionToExistingStructureConcurrently(Structure*, UniquedStringImpl* uid, unsigned attributes, PropertyOffset&);
    191191    JS_EXPORT_PRIVATE static Structure* addPropertyTransitionToExistingStructure(Structure*, PropertyName, unsigned attributes, PropertyOffset&);
    192     static Structure* removePropertyTransition(VM&, Structure*, PropertyName, PropertyOffset&);
     192    static Structure* removeNewPropertyTransition(VM&, Structure*, PropertyName, PropertyOffset&, DeferredStructureTransitionWatchpointFire* = nullptr);
     193    static Structure* removePropertyTransition(VM&, Structure*, PropertyName, PropertyOffset&, DeferredStructureTransitionWatchpointFire* = nullptr);
     194    static Structure* removePropertyTransitionFromExistingStructure(VM&, Structure*, PropertyName, PropertyOffset&, DeferredStructureTransitionWatchpointFire* = nullptr);
    193195    static Structure* changePrototypeTransition(VM&, Structure*, JSValue prototype, DeferredStructureTransitionWatchpointFire&);
    194196    JS_EXPORT_PRIVATE static Structure* attributeChangeTransition(VM&, Structure*, PropertyName, unsigned attributes);
    195197    JS_EXPORT_PRIVATE static Structure* toCacheableDictionaryTransition(VM&, Structure*, DeferredStructureTransitionWatchpointFire* = nullptr);
    196     static Structure* toUncacheableDictionaryTransition(VM&, Structure*);
     198    static Structure* toUncacheableDictionaryTransition(VM&, Structure*, DeferredStructureTransitionWatchpointFire* = nullptr);
    197199    JS_EXPORT_PRIVATE static Structure* sealTransition(VM&, Structure*);
    198200    JS_EXPORT_PRIVATE static Structure* freezeTransition(VM&, Structure*);
    … …  
    450452    {
    451453        return std::min<unsigned>(maxOffset() + 1, m_inlineCapacity);
    452     }
    453     unsigned totalStorageSize() const
    454     {
    455         return numberOfSlotsForMaxOffset(maxOffset(), m_inlineCapacity);
    456454    }
    457455    unsigned totalStorageCapacity() const
    … …  
    702700    DEFINE_BITFIELD(bool, transitionWatchpointIsLikelyToBeFired, TransitionWatchpointIsLikelyToBeFired, 1, 26);
    703701    DEFINE_BITFIELD(bool, hasBeenDictionary, HasBeenDictionary, 1, 27);
    704     DEFINE_BITFIELD(bool, isAddingPropertyForTransition, IsAddingPropertyForTransition, 1, 28);
     702    DEFINE_BITFIELD(bool, protectPropertyTableWhileTransitioning, ProtectPropertyTableWhileTransitioning, 1, 28);
    705703    DEFINE_BITFIELD(bool, hasUnderscoreProtoPropertyExcludingOriginalProto, HasUnderscoreProtoPropertyExcludingOriginalProto, 1, 29);
     704    DEFINE_BITFIELD(bool, isPropertyDeletionTransition, IsPropertyDeletionTransition, 1, 30);
    706705
    707706private:
    … …  
    728727    PropertyOffset add(VM&, PropertyName, unsigned attributes, const Func&);
    729728    PropertyOffset add(VM&, PropertyName, unsigned attributes);
    730     template<typename Func>
    731     PropertyOffset remove(PropertyName, const Func&);
    732     PropertyOffset remove(PropertyName);
     729    template<ShouldPin, typename Func>
     730    PropertyOffset remove(VM&, PropertyName, const Func&);
     731    PropertyOffset remove(VM&, PropertyName);
    733732
    734733    void checkConsistency();
    … …  
    842841
    843842    friend class VMInspector;
     843    friend class JSDollarVMHelper;
    844844};
    845845

  • trunk/Source/JavaScriptCore/runtime/StructureInlines.h

    r254760 r255897  
    164164{
    165165    Vector<Structure*, 8> structures;
    166     Structure* structure;
     166    Structure* tableStructure;
    167167    PropertyTable* table;
    168168   
    169     findStructuresAndMapForMaterialization(structures, structure, table);
     169    findStructuresAndMapForMaterialization(structures, tableStructure, table);
     170
     171    HashSet<UniquedStringImpl*> seenProperties;
     172
     173    for (auto* structure : structures) {
     174        if (!structure->m_transitionPropertyName || seenProperties.contains(structure->m_transitionPropertyName.get()))
     175            continue;
     176
     177        seenProperties.add(structure->m_transitionPropertyName.get());
     178
     179        if (structure->isPropertyDeletionTransition())
     180            continue;
     181
     182        if (!functor(PropertyMapEntry(structure->m_transitionPropertyName.get(), structure->transitionOffset(), structure->transitionPropertyAttributes()))) {
     183            if (table)
     184                tableStructure->m_lock.unlock();
     185            return;
     186        }
     187    }
    170188   
    171189    if (table) {
    172190        for (auto& entry : *table) {
     191            if (seenProperties.contains(entry.key))
     192                continue;
     193
    173194            if (!functor(entry)) {
    174                 structure->m_lock.unlock();
     195                tableStructure->m_lock.unlock();
    175196                return;
    176197            }
    177198        }
    178         structure->m_lock.unlock();
    179     }
    180    
    181     for (unsigned i = structures.size(); i--;) {
    182         structure = structures[i];
    183         if (!structure->m_transitionPropertyName)
    184             continue;
    185        
    186         if (!functor(PropertyMapEntry(structure->m_transitionPropertyName.get(), structure->transitionOffset(), structure->transitionPropertyAttributes())))
    187             return;
     199        tableStructure->m_lock.unlock();
    188200    }
    189201}
    … …  
    452464
    453465    m_propertyHash = m_propertyHash ^ rep->existingSymbolAwareHash();
    454 
    455466    m_seenProperties.add(bitwise_cast<uintptr_t>(rep));
    456    
    457     PropertyOffset newMaxOffset = maxOffset();
    458     table->add(PropertyMapEntry(rep, newOffset, attributes), newMaxOffset, PropertyTable::PropertyOffsetMayChange);
     467
     468    auto result = table->add(PropertyMapEntry(rep, newOffset, attributes));
     469    ASSERT_UNUSED(result, result.second);
     470    ASSERT_UNUSED(result, result.first.first->offset == newOffset);
     471    auto newMaxOffset = std::max(newOffset, maxOffset());
    459472   
    460473    func(locker, newOffset, newMaxOffset);
    … …  
    466479}
    467480
    468 template<typename Func>
    469 inline PropertyOffset Structure::remove(PropertyName propertyName, const Func& func)
    470 {
    471     ConcurrentJSLocker locker(m_lock);
    472    
     481template<Structure::ShouldPin shouldPin, typename Func>
     482inline PropertyOffset Structure::remove(VM& vm, PropertyName propertyName, const Func& func)
     483{
     484    PropertyTable* table = ensurePropertyTable(vm);
     485    GCSafeConcurrentJSLocker locker(m_lock, vm.heap);
     486
     487    switch (shouldPin) {
     488    case ShouldPin::Yes:
     489        pin(locker, vm, table);
     490        break;
     491    case ShouldPin::No:
     492        setPropertyTable(vm, table);
     493        break;
     494    }
     495
     496    ASSERT(JSC::isValidOffset(get(vm, propertyName)));
     497
    473498    checkConsistency();
    474499
    475500    auto rep = propertyName.uid();
    476    
    477     // We ONLY remove from uncacheable dictionaries, which will have a pinned property table.
    478     // The only way for them not to have a table is if they are empty.
    479     PropertyTable* table = propertyTableOrNull();
    480 
    481     if (!table)
    482         return invalidOffset;
    483501
    484502    PropertyTable::find_iterator position = table->find(rep);
    485503    if (!position.first)
    486504        return invalidOffset;
     505
     506    setIsQuickPropertyAccessAllowedForEnumeration(false);
    487507   
    488508    PropertyOffset offset = position.first->offset;
    … …  
    491511    table->addDeletedOffset(offset);
    492512
     513    PropertyOffset newMaxOffset = maxOffset();
     514
     515    func(locker, offset, newMaxOffset);
     516
     517    ASSERT(maxOffset() == newMaxOffset);
     518    ASSERT(!JSC::isValidOffset(get(vm, propertyName)));
     519
    493520    checkConsistency();
    494 
    495     func(locker, offset);
    496521    return offset;
    497522}
    … …  
    504529
    505530template<typename Func>
    506 inline PropertyOffset Structure::removePropertyWithoutTransition(VM&, PropertyName propertyName, const Func& func)
     531inline PropertyOffset Structure::removePropertyWithoutTransition(VM& vm, PropertyName propertyName, const Func& func)
    507532{
    508533    ASSERT(isUncacheableDictionary());
    … …  
    510535    ASSERT(propertyTableOrNull());
    511536   
    512     return remove(propertyName, func);
     537    return remove<ShouldPin::Yes>(vm, propertyName, func);
    513538}
    514539

  • trunk/Source/JavaScriptCore/runtime/StructureTransitionTable.h

    r250005 r255897  
    145145   
    146146    struct Hash {
    147         typedef std::pair<UniquedStringImpl*, unsigned> Key;
     147        typedef std::tuple<UniquedStringImpl*, unsigned, bool> Key;
    148148       
    149149        static unsigned hash(const Key& p)
    150150        {
    151             return PtrHash<UniquedStringImpl*>::hash(p.first) + p.second;
     151            return PtrHash<UniquedStringImpl*>::hash(std::get<0>(p)) + std::get<1>(p);
    152152        }
    153153
    … …  
    182182
    183183    void add(VM&, Structure*);
    184     bool contains(UniquedStringImpl*, unsigned attributes) const;
    185     Structure* get(UniquedStringImpl*, unsigned attributes) const;
     184    bool contains(UniquedStringImpl*, unsigned attributes, bool isAddition) const;
     185    Structure* get(UniquedStringImpl*, unsigned attributes, bool isAddition) const;
    186186
    187187private:

  • trunk/Source/JavaScriptCore/tools/JSDollarVM.cpp

    r255365 r255897  
    8282    void updateVMStackLimits() { return m_vm.updateStackLimits(); };
    8383
     84    static EncodedJSValue JSC_HOST_CALL functionGetStructureTransitionList(JSGlobalObject*, CallFrame*);
     85
    8486private:
    8587    VM& m_vm;
    … …  
    27702772}
    27712773
     2774EncodedJSValue JSC_HOST_CALL JSDollarVMHelper::functionGetStructureTransitionList(JSGlobalObject* globalObject, CallFrame* callFrame)
     2775{
     2776    DollarVMAssertScope assertScope;
     2777    VM& vm = globalObject->vm();
     2778    auto scope = DECLARE_THROW_SCOPE(vm);
     2779    JSObject* obj = callFrame->argument(0).toObject(globalObject);
     2780    RETURN_IF_EXCEPTION(scope, { });
     2781    if (!obj)
     2782        return JSValue::encode(jsNull());
     2783    Vector<Structure*, 8> structures;
     2784
     2785    for (auto* structure = obj->structure(); structure; structure = structure->previousID())
     2786        structures.append(structure);
     2787
     2788    JSArray* result = JSArray::tryCreate(vm, globalObject->arrayStructureForIndexingTypeDuringAllocation(ArrayWithContiguous), 0);
     2789    RETURN_IF_EXCEPTION(scope, { });
     2790
     2791    for (size_t i = 0; i < structures.size(); ++i) {
     2792        auto* structure = structures[structures.size() - i - 1];
     2793        result->push(globalObject, JSValue(structure->id()));
     2794        RETURN_IF_EXCEPTION(scope, { });
     2795        result->push(globalObject, JSValue(structure->transitionOffset()));
     2796        RETURN_IF_EXCEPTION(scope, { });
     2797        result->push(globalObject, JSValue(structure->maxOffset()));
     2798        RETURN_IF_EXCEPTION(scope, { });
     2799        if (structure->m_transitionPropertyName)
     2800            result->push(globalObject, jsString(vm, String(*structure->m_transitionPropertyName)));
     2801        else
     2802            result->push(globalObject, jsNull());
     2803        RETURN_IF_EXCEPTION(scope, { });
     2804        result->push(globalObject, JSValue(structure->isPropertyDeletionTransition()));
     2805        RETURN_IF_EXCEPTION(scope, { });
     2806    }
     2807
     2808    return JSValue::encode(result);
     2809}
     2810
     2811static EncodedJSValue JSC_HOST_CALL functionGetConcurrently(JSGlobalObject* globalObject, CallFrame* callFrame)
     2812{
     2813    DollarVMAssertScope assertScope;
     2814    VM& vm = globalObject->vm();
     2815    auto scope = DECLARE_THROW_SCOPE(vm);
     2816    JSObject* obj = callFrame->argument(0).toObject(globalObject);
     2817    RETURN_IF_EXCEPTION(scope, { });
     2818    if (!obj)
     2819        return JSValue::encode(jsNull());
     2820    String property = callFrame->argument(1).toWTFString(globalObject);
     2821    RETURN_IF_EXCEPTION(scope, { });
     2822    auto name = PropertyName(Identifier::fromString(vm, property));
     2823    auto offset = obj->structure()->getConcurrently(name.uid());
     2824    if (offset != invalidOffset)
     2825        ASSERT(JSValue::encode(obj->getDirect(offset)));
     2826    JSValue result = JSValue(offset != invalidOffset);
     2827    RETURN_IF_EXCEPTION(scope, { });
     2828    return JSValue::encode(result);
     2829}
     2830
    27722831void JSDollarVM::finishCreation(VM& vm)
    27732832{
    … …  
    28982957    addFunction(vm, "make16BitStringIfPossible", functionMake16BitStringIfPossible, 1);
    28992958
     2959    addFunction(vm, "getStructureTransitionList", JSDollarVMHelper::functionGetStructureTransitionList, 1);
     2960    addFunction(vm, "getConcurrently", functionGetConcurrently, 2);
     2961
    29002962    m_objectDoingSideEffectPutWithoutCorrectSlotStatusStructure.set(vm, this, ObjectDoingSideEffectPutWithoutCorrectSlotStatus::createStructure(vm, globalObject, jsNull()));
    29012963}
Note: See TracChangeset for help on using the changeset viewer.