Bug 179929 – [JSC] Implement optimized WeakMap and WeakSet

• Status: RESOLVED
• Resolution: FIXED
• Component: JavaScriptCore

[Yusuke Suzuki]

We should do the similar thing to JSMap and JSSet.

Notes.

1. WeakMap does not have iterators. Thus, we do not need to maintain bucket's links.
2. Since we do not have iterators, we do not need to have bucket as cell.
3. Key is only JSObject*.

[Yusuke Suzuki]

Created attachment 327510 [details]
Patch

[Yusuke Suzuki]

Created attachment 327532 [details]
Patch

[Yusuke Suzuki]

Created attachment 327533 [details]
Patch

[Yusuke Suzuki]

Comment on attachment 327533 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=327533&action=review

> Source/JavaScriptCore/inspector/JSInjectedScriptHost.cpp:513
> +    weakSet->forEach([&] (JSObject* key, JSValue) {

Not good. We should not have such interface in WeakMap since functor can cause GC.
I think this is pre-existing bug. Old WeakMap implementaiton is also broken.
If we would like to iterate it, once we should buffer all the entries and we should put it to the result object.

[Yusuke Suzuki]

Created attachment 327535 [details]
Patch

[EWS Watchlist]

Comment on attachment 327535 [details]
Patch

Attachment 327535 [details] did not pass mac-debug-ews (mac):
Output: http://webkit-queues.webkit.org/results/5348290

New failing tests:
js/dom/basic-weakset.html
js/dom/basic-weakmap.html

[EWS Watchlist]

Created attachment 327542 [details]
Archive of layout-test-results from ews114 for mac-elcapitan

The attached test failures were seen while running run-webkit-tests on the mac-debug-ews.
Bot: ews114  Port: mac-elcapitan  Platform: Mac OS X 10.11.6

[Yusuke Suzuki]

Created attachment 327545 [details]
Patch

[Yusuke Suzuki]

Created attachment 327547 [details]
Patch

[EWS Watchlist]

Comment on attachment 327547 [details]
Patch

Attachment 327547 [details] did not pass mac-debug-ews (mac):
Output: http://webkit-queues.webkit.org/results/5349509

New failing tests:
js/dom/basic-weakset.html
js/dom/basic-weakmap.html

[EWS Watchlist]

Created attachment 327549 [details]
Archive of layout-test-results from ews117 for mac-elcapitan

The attached test failures were seen while running run-webkit-tests on the mac-debug-ews.
Bot: ews117  Port: mac-elcapitan  Platform: Mac OS X 10.11.6

[Yusuke Suzuki]

Created attachment 327551 [details]
Patch

[Yusuke Suzuki]

Created attachment 327552 [details]
Patch

[Yusuke Suzuki]

Created attachment 327727 [details]
Patch

[Yusuke Suzuki]

Ping?

[Yusuke Suzuki]

There is ongoing effort removing UnconditionalFinalizer & WeakReferenceHarvester. I think we can apply them to WeakMap/WeakSet.

[Saam Barati]

Comment on attachment 327727 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=327727&action=review

r=me. Nice patch!

> Source/JavaScriptCore/ChangeLog:17
> +        2. WeakMapImpl's buffer is allocated in JSValue Gigacage instead
> +        of auxiliary buffer. This is because we would like to allocate buffer
> +        when finalizing GC. At that time, WeakMapImpl prunes dead entries and
> +        shrink it if necessary.

Is this because we can't allocate from the GC Heap during finalization? If so I'd just write that.

> Source/JavaScriptCore/inspector/JSInjectedScriptHost.cpp:468
> +        array->putDirectIndex(exec, index >> 1, entry);

let's do / 2. LLVM/GCC will emit the right code

> Source/JavaScriptCore/runtime/WeakMapImpl.cpp:95
> +        ASSERT(m_keyCount > 0);

I vote for RELEASE_ASSERT

> Source/JavaScriptCore/runtime/WeakMapImpl.cpp:131
> +// takeSnapshot must not invoke garbage collection since iterating WeakMap may be modified.
> +template <>
> +void WeakMapImpl<WeakMapBucket<WeakMapBucketDataKey>>::takeSnapshot(MarkedArgumentBuffer& buffer, unsigned limit)
> +{
> +    DisallowGC disallowGC;
> +    unsigned fetched = 0;
> +    forEach([&] (JSObject* key, JSValue) {
> +        buffer.append(key);
> +        ++fetched;
> +        if (limit && fetched >= limit)
> +            return IterationState::Stop;
> +        return IterationState::Continue;
> +    });
> +}
> +
> +template <>
> +void WeakMapImpl<WeakMapBucket<WeakMapBucketDataKeyValue>>::takeSnapshot(MarkedArgumentBuffer& buffer, unsigned limit)
> +{
> +    DisallowGC disallowGC;
> +    unsigned fetched = 0;
> +    forEach([&] (JSObject* key, JSValue value) {
> +        buffer.append(key);
> +        buffer.append(value);
> +        ++fetched;
> +        if (limit && fetched >= limit)
> +            return IterationState::Stop;
> +        return IterationState::Continue;
> +    });
> +}

You could combine these methods and just have a helper that either adds both key and value or just key

> Source/JavaScriptCore/runtime/WeakMapImpl.h:58
> +ALWAYS_INLINE uint32_t nextCapacityAfterRemoveBatching(uint32_t capacity, uint32_t keyCount)

style nit: I'd name this: "nextCapacityAfterBatchRemoval"

> Source/JavaScriptCore/runtime/WeakMapImpl.h:184
> +        auto buffer = MallocPtr<WeakMapBuffer, JSValueMalloc>::malloc(allocationSize);
> +        RELEASE_ASSERT_WITH_MESSAGE(buffer, "If buffer is failed to allocate during GC, WeakMap becomes completely broken");

Shouldn't this malloc() call ensure we get a result? e.g, it should crash if it can't allocate. I'd expect ::malloc to guarantee a result, and something like tryMalloc to perhaps return null.

> Source/JavaScriptCore/runtime/WeakMapImpl.h:228
> +        DisallowGC disallowGC;

Why would findBucket() GC? Seems like this isn't needed.

> Source/JavaScriptCore/runtime/WeakMapImpl.h:236
> +        DisallowGC disallowGC;

ditto

> Source/JavaScriptCore/runtime/WeakMapImpl.h:266
> +        ASSERT(m_keyCount > 0);

I got for RELEASE_ASSERT

> Source/JavaScriptCore/runtime/WeakMapImpl.h:310
> +    IterationState forEach(Functor functor)

Style nit: Why does this return anything? Seems weird. It makes sense for functor to return this, but I don't see why we'd return that from forEach.

> Source/JavaScriptCore/runtime/WeakMapImpl.h:387
> +        MallocPtr<WeakMapBufferType, JSValueMalloc> oldBuffer;
> +        oldBuffer.swap(m_buffer);

Why not  `oldBuffer = WTFMove(m_buffer)`?

> Source/JavaScriptCore/runtime/WeakMapImpl.h:412
> +            auto* bucket = buffer + index;
> +            bucket->copyFrom(*entry);

If you do this in the above you don't need to do the add twice. You can just use bucket.

[Yusuke Suzuki]

Comment on attachment 327727 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=327727&action=review

Thank you!

>> Source/JavaScriptCore/ChangeLog:17
>> +        shrink it if necessary.
> 
> Is this because we can't allocate from the GC Heap during finalization? If so I'd just write that.

Yeah, added this description.

>> Source/JavaScriptCore/inspector/JSInjectedScriptHost.cpp:468
>> +        array->putDirectIndex(exec, index >> 1, entry);
> 
> let's do / 2. LLVM/GCC will emit the right code

Fixed.

>> Source/JavaScriptCore/runtime/WeakMapImpl.cpp:95
>> +        ASSERT(m_keyCount > 0);
> 
> I vote for RELEASE_ASSERT

Replaced!

>> Source/JavaScriptCore/runtime/WeakMapImpl.cpp:131
>> +}
> 
> You could combine these methods and just have a helper that either adds both key and value or just key

Yeah, sounds nice to me too. Fixed.

>> Source/JavaScriptCore/runtime/WeakMapImpl.h:58
>> +ALWAYS_INLINE uint32_t nextCapacityAfterRemoveBatching(uint32_t capacity, uint32_t keyCount)
> 
> style nit: I'd name this: "nextCapacityAfterBatchRemoval"

Fixed.

>> Source/JavaScriptCore/runtime/WeakMapImpl.h:184
>> +        RELEASE_ASSERT_WITH_MESSAGE(buffer, "If buffer is failed to allocate during GC, WeakMap becomes completely broken");
> 
> Shouldn't this malloc() call ensure we get a result? e.g, it should crash if it can't allocate. I'd expect ::malloc to guarantee a result, and something like tryMalloc to perhaps return null.

Yeah, I removed this. This assertion should be done in malloc side.

>> Source/JavaScriptCore/runtime/WeakMapImpl.h:228
>> +        DisallowGC disallowGC;
> 
> Why would findBucket() GC? Seems like this isn't needed.

This is different from DisableGC. This DisallowGC ensures that the following operation does not cause GC. If operation causing GC occurs, assertion fires.

>> Source/JavaScriptCore/runtime/WeakMapImpl.h:236
>> +        DisallowGC disallowGC;
> 
> ditto

Ditto.

>> Source/JavaScriptCore/runtime/WeakMapImpl.h:266
>> +        ASSERT(m_keyCount > 0);
> 
> I got for RELEASE_ASSERT

Replaced.

>> Source/JavaScriptCore/runtime/WeakMapImpl.h:310
>> +    IterationState forEach(Functor functor)
> 
> Style nit: Why does this return anything? Seems weird. It makes sense for functor to return this, but I don't see why we'd return that from forEach.

OK, changed to making it void.

>> Source/JavaScriptCore/runtime/WeakMapImpl.h:387
>> +        oldBuffer.swap(m_buffer);
> 
> Why not  `oldBuffer = WTFMove(m_buffer)`?

Nice, fixed.

>> Source/JavaScriptCore/runtime/WeakMapImpl.h:412
>> +            bucket->copyFrom(*entry);
> 
> If you do this in the above you don't need to do the add twice. You can just use bucket.

Yeah, nice. Fixed.

[Yusuke Suzuki]

Committed r225832: <https://trac.webkit.org/changeset/225832>

[Radar WebKit Bug Importer]

<rdar://problem/36011741>

[Guillaume Emont]

All these weakmap/weakset tests seem to fail on linux testbots. Any idea of what could cause that?

[Yusuke Suzuki]

WeakMapGet exhausts the registers. Checking.

[Yusuke Suzuki]

(In reply to Yusuke Suzuki from comment #22)
> WeakMapGet exhausts the registers. Checking.

https://bugs.webkit.org/show_bug.cgi?id=180804