Bug 235192

Summary: Update ARM64EHash
Product: WebKit Reporter: Saam Barati <saam>
Component: JavaScriptCoreAssignee: Saam Barati <saam>
Status: RESOLVED FIXED    
Severity: Normal CC: annulen, benjamin, cdumez, cmarcelo, darin, ews-watchlist, gyuyoung.kim, keith_miller, mark.lam, msaboff, ryuan.choi, sergio, tzagallo, webkit-bug-importer
Priority: P2 Keywords: InRadar
Version: WebKit Nightly Build   
Hardware: Unspecified   
OS: Unspecified   
Bug Depends on: 235201, 235241    
Bug Blocks:    
Attachments:
Description Flags
patch
ews-feeder: commit-queue-
patch
none
patch
ews-feeder: commit-queue-
patch
ews-feeder: commit-queue-
patch
none
patch
mark.lam: review+
patch for landing
ews-feeder: commit-queue-
patch for landing
none
patch for landing none

Description Saam Barati 2022-01-13 11:12:37 PST
...
Comment 1 Saam Barati 2022-01-14 08:29:42 PST
Created attachment 449175 [details]
patch
Comment 2 Saam Barati 2022-01-14 10:00:51 PST
Created attachment 449179 [details]
patch
Comment 3 Mark Lam 2022-01-14 11:37:29 PST
Comment on attachment 449179 [details]
patch

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

Some comments for now.  Will continue reviewing on new patch.

> Source/JavaScriptCore/assembler/AssemblerBuffer.h:231
> +                if (shouldSign) {

`constexpr (shouldSign)`?

> Source/JavaScriptCore/assembler/AssemblerBuffer.h:269
> +            if (shouldSign)

constexpr (shouldSign)

> Source/JavaScriptCore/assembler/AssemblerBuffer.h:276
> +            if (shouldSign)

Ditto.

> Source/WTF/wtf/Bitmap.h:398
> +                if constexpr (std::is_same_v<bool, decltype(func(base + j))>) {

I suggest moving JSC's IterationStatus to WTF, and checking if this returns that instead of a bool.  That way, we can check for Continue or Done instead of true / false.
Comment 4 Saam Barati 2022-01-14 12:14:45 PST
Created attachment 449198 [details]
patch
Comment 5 Saam Barati 2022-01-14 12:18:43 PST
Created attachment 449201 [details]
patch
Comment 6 Saam Barati 2022-01-14 12:27:21 PST
Created attachment 449206 [details]
patch
Comment 7 Mark Lam 2022-01-14 14:21:15 PST
Comment on attachment 449179 [details]
patch

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

Posting my comments so far while I think about this patch some more.

> Source/JavaScriptCore/assembler/AssemblerBuffer.h:211
> +        ARM64EHash(void*)

Let's remove the diversifier arg altogether.  This reduces to ARM64EHash() = default;

> Source/JavaScriptCore/assembler/AssemblerBuffer.h:228
>          ALWAYS_INLINE uint32_t update(uint32_t instruction, uint32_t index, void* diversifier)

Let's remove the diversifier arg altogether.

> Source/JavaScriptCore/assembler/AssemblerBuffer.h:234
> +                    setUpdatedHash(0, 0, diversifier);

Let's remove the unused diversifier arg.

> Source/JavaScriptCore/assembler/AssemblerBuffer.h:239
>              uint32_t currentHash = this->currentHash(index, diversifier);

Let's not pass a diversifier anymore since we don't need it.

> Source/JavaScriptCore/assembler/AssemblerBuffer.h:267
> +        ALWAYS_INLINE uint32_t currentHash(uint32_t index, void*)

Let's remove the 2nd arg (the diversifier) altogether since it is completely unused.

> Source/JavaScriptCore/assembler/AssemblerBuffer.h:274
> +        ALWAYS_INLINE void setUpdatedHash(uint32_t value, uint32_t index, void*)

Let's remove the unused diversifier arg altogether.

> Source/JavaScriptCore/assembler/SecureARM64EHashPins.cpp:40
> +    WriteToJITRegionScope()

ALWAYS_INLINE

> Source/JavaScriptCore/assembler/SecureARM64EHashPins.cpp:45
> +    ~WriteToJITRegionScope()

ALWAYS_INLINE

> Source/JavaScriptCore/assembler/SecureARM64EHashPins.cpp:51
> +struct ValidateAtomicityScope {

How about call this `ValidateHasEnteredLockedRegion` or just `ValidateHasEntered` instead.

> Source/JavaScriptCore/assembler/SecureARM64EHashPins.cpp:56
> +        uint32_t validateAtomicity = m_metadata->assertNotReentrant.exchange(1, std::memory_order_seq_cst);
> +        RELEASE_ASSERT(!validateAtomicity);

Let's rename `assertNotReentrant` to `hasEnteredLockedRegion`, or just `hasEntered` if you prefer it shorter.
Let's rename 'validateAtomicity` to `previouslyHasEnteredLockedRegion`.

Instead of using a passed in metadata, can we fetch/compute this metadata pointer from the jscConfig instead.  That will guarantee the integrity of the metadata pointer.

> Source/JavaScriptCore/assembler/SecureARM64EHashPins.cpp:62
> +        uint32_t validateAtomicity = m_metadata->assertNotReentrant.exchange(0, std::memory_order_seq_cst);
> +        RELEASE_ASSERT(validateAtomicity == 1);

Ditto.  The RELEASE_ASSERT can not become `RELEASE_ASSERT(previouslyHasEnteredLockedRegion)`.

Same: instead of using a cached metadata pointer, can we fetch/compute this metadata pointer from the jscConfig instead.  That will guarantee the integrity of the metadata pointer.

> Source/JavaScriptCore/assembler/SecureARM64EHashPins.cpp:87
> +static void initializePage(const WriteToJITRegionScope&, SecureARM64EHashPins::Page* page)
> +{
> +    new (page) SecureARM64EHashPins::Page;
> +    for (unsigned i = 0; i < SecureARM64EHashPins::numEntriesPerPage; ++i) {
> +        auto& entry = page->entry(i);
> +        entry.pin = 0;
> +        entry.key = 0;
> +    }
> +}

You could have moved this into the SecureARM64EHashPins::Page constructor.  This is more C++ idiomatic then using an external initializer.  And instead of a for loop, you have the SecureARM64EHashPins::Page constructor just do a memset over that regions (maybe faster?).

> Source/JavaScriptCore/assembler/SecureARM64EHashPins.cpp:91
> +    RELEASE_ASSERT(!m_memory);

Let's change this to: RELEASE_ASSERT(!g_jscConfig.arm64eHashPins.m_memory);

> Source/JavaScriptCore/assembler/SecureARM64EHashPins.cpp:93
> +    m_memory = bitwise_cast<char*>(allocateInExecutableMemory(sizeof(Metadata) + Page::allocationSize())) + sizeof(Metadata);

Do we need a compilerFence() after this to make sure it doesn't get moved inside the writeScope?

> Source/JavaScriptCore/assembler/SecureARM64EHashPins.cpp:99
> +        initializePage(writeScope, firstPage());

If you moved the initializePage() code into the SecureARM64EHashPins::Page constructor, you can change this to:
    new (firstPage()) SecureARM64EHashPins::Page(writeScope);

> Source/JavaScriptCore/assembler/SecureARM64EHashPins.cpp:107
> +    auto* metadata = this->metadata();

Remove this.  See below for details.

> Source/JavaScriptCore/assembler/SecureARM64EHashPins.cpp:114
> +    size_t newEntry;

nit: should call this newEntryIndex to be consistent with terminology above: preexistingEntryIndex vs preexistingEntry.

> Source/JavaScriptCore/assembler/SecureARM64EHashPins.cpp:118
> +        size_t baseIndex = 0;

Remove this.

> Source/JavaScriptCore/assembler/SecureARM64EHashPins.cpp:121
> +            size_t bit = page.findClearBit();

nit: /findClearBit/findFirstEmpty/ and /bit/index/

> Source/JavaScriptCore/assembler/SecureARM64EHashPins.cpp:124
> +                newEntry = baseIndex + bit;

newEntry = Page::globalIndex(index);

See comment in SecureARM64EHashPins::findEntry below.

> Source/JavaScriptCore/assembler/SecureARM64EHashPins.cpp:129
> +            baseIndex += numEntriesPerPage;

Remove this.

> Source/JavaScriptCore/assembler/SecureARM64EHashPins.cpp:139
> +                ValidateAtomicityScope validateAtomicity(metadata);

No longer need to pass metadata to the scope.

> Source/JavaScriptCore/assembler/SecureARM64EHashPins.cpp:157
> +        ValidateAtomicityScope validateAtomicity(metadata);

No longer need to pass metadata to the scope.

> Source/JavaScriptCore/assembler/SecureARM64EHashPins.cpp:159
> +        RELEASE_ASSERT(isJITPC(metadata));

Don't need this.

> Source/JavaScriptCore/assembler/SecureARM64EHashPins.cpp:161
> +        pin = metadata->nextPin.exchangeAdd(1, std::memory_order_seq_cst);

Let's make the metadata() method a static method that computes the metadata pointer from jscConfig instead of the `this` pointer.  You can just "fetch" metadata here (instead of up above):
     pin = metadata().nextPin.exchangeAdd(...

The metadata should be a singleton, and using a static method expresses that idiom.

> Source/JavaScriptCore/assembler/SecureARM64EHashPins.cpp:164
> +        newEntryPage->setIsInUse(newEntry);

Make sure to use the page local index here.  Maybe can have a Page::localIndex() that does the inverse mapping of Page::globalndex().

> Source/JavaScriptCore/assembler/SecureARM64EHashPins.cpp:169
> +            newEntryPage->entry(newEntry) = *preexistingEntry;

Make sure to use the page local index here.

> Source/JavaScriptCore/assembler/SecureARM64EHashPins.h:52
> +        static_assert(!(mask & numEntriesPerPage));

I think we can make a strong assert here:

1. Add this (based on existing code) to MathExtras.h:

template<typename IntType, typename = std::enable_if_t<std::is_integral<IntType>::value>>>
inline bool isPowerOf2(IntType v)
{
    return hasOneBitSet(v);
}

2. use isPowerOf2 in your assert.

> Source/JavaScriptCore/assembler/SecureARM64EHashPins.h:57
> +            return entries[index & mask];

I suggest adding a baseIndex field to Page.  With that you can:
1. get rid of the use of mask everywhere in Page's code.
2. SecureARM64EHashPins::forEachEntry() can now with tracking baseIndex and adding it to index only to be masked back out.
3. SecureARM64EHashPins::findEntry() will just set `result.index = page.baseIndex + index;`

This should speed up findEntry at the cost of a bit more memory usage.  If you want to avoid the incremental memory usage, you can convert the next field into a 32-bit nextOffset.  The next page can be computed as:
     bitwise_cast<uint32_t*>(this) + nextOffset.

That will give you 32-bits for the baseIndex.  If you like, you can also store a right shifted baseIndex such that SecureARM64EHashPins::findEntry() will just set:
    result.index = (page.baseIndex << baseIndexShift) + index;

That will give more use a much higher 38-bit index range.  I think 32-bit should be plenty already.

> Source/JavaScriptCore/assembler/SecureARM64EHashPins.h:62
> +            isInUseMap.set(index & mask);

Remove the `& mask`.

> Source/JavaScriptCore/assembler/SecureARM64EHashPins.h:67
> +            isInUseMap.set(index & mask, false);

Remove the `& mask`.

> Source/JavaScriptCore/assembler/SecureARM64EHashPins.h:72
> +            return isInUseMap.get(index & mask);

Remove the `& mask`.

> Source/JavaScriptCore/assembler/SecureARM64EHashPins.h:75
> +        size_t findClearBit()

nit: Let's call this findFirstEmpty.

> Source/JavaScriptCore/assembler/SecureARM64EHashPins.h:81
> +        void forEachSetBit(Function function)

nit: Let's call this forEachEntry.

> Source/JavaScriptCore/assembler/SecureARM64EHashPins.h:95
> +        Atomic<uint32_t> assertNotReentrant { 0 };

Let's call this `hasEnteredLockedRegion`.  `assertNotReentrant` is a verb and doesn't quite convey what this field means.

> Source/JavaScriptCore/assembler/SecureARM64EHashPins.h:110
> +    inline Metadata* metadata() { return bitwise_cast<Metadata*>(bitwise_cast<char*>(m_memory) - sizeof(Metadata)); }

nit: could have expressed this as: bitwise_cast<MetaData*>(m_memory) - 1;

> Source/JavaScriptCore/assembler/SecureARM64EHashPinsInlines.h:63
> +        page.forEachSetBit([&] (size_t bitIndex) {

Let's change this to: page.forEachEntry([&] (size_t index) {

> Source/JavaScriptCore/assembler/SecureARM64EHashPinsInlines.h:64
> +            size_t index = baseIndex + bitIndex;

remove this.

> Source/JavaScriptCore/assembler/SecureARM64EHashPinsInlines.h:70
> +        baseIndex += numEntriesPerPage;

remove this.

> Source/JavaScriptCore/assembler/SecureARM64EHashPinsInlines.h:91
> +            result.index = index;

Change this to:
    result.index = Page::globalndex(index);
where:
    size_t Page::globalndex(size_t index) { return this->baseIndex << baseIndexShift + index; }
Comment 8 Mark Lam 2022-01-14 14:31:59 PST
>> Source/JavaScriptCore/assembler/SecureARM64EHashPins.h:57
>> +            return entries[index & mask];
>
>I suggest adding a baseIndex field to Page.  With that you can:
>1. get rid of the use of mask everywhere in Page's code.
>2. SecureARM64EHashPins::forEachEntry() can now with tracking baseIndex and adding it to index only to be masked back out.

I meant to say "can now do away with tracking baseIndex ...".
Comment 9 Saam Barati 2022-01-14 17:45:54 PST
Created attachment 449236 [details]
patch
Comment 10 Saam Barati 2022-01-14 18:59:58 PST
Comment on attachment 449179 [details]
patch

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

>> Source/JavaScriptCore/assembler/SecureARM64EHashPins.cpp:51
>> +struct ValidateAtomicityScope {
> 
> How about call this `ValidateHasEnteredLockedRegion` or just `ValidateHasEntered` instead.

This isn't quite right. I'm going with "ValidateNonReentrancyScope" since there are multiple per locked region.

>> Source/JavaScriptCore/assembler/SecureARM64EHashPins.h:57
>> +            return entries[index & mask];
> 
> I suggest adding a baseIndex field to Page.  With that you can:
> 1. get rid of the use of mask everywhere in Page's code.
> 2. SecureARM64EHashPins::forEachEntry() can now with tracking baseIndex and adding it to index only to be masked back out.
> 3. SecureARM64EHashPins::findEntry() will just set `result.index = page.baseIndex + index;`
> 
> This should speed up findEntry at the cost of a bit more memory usage.  If you want to avoid the incremental memory usage, you can convert the next field into a 32-bit nextOffset.  The next page can be computed as:
>      bitwise_cast<uint32_t*>(this) + nextOffset.
> 
> That will give you 32-bits for the baseIndex.  If you like, you can also store a right shifted baseIndex such that SecureARM64EHashPins::findEntry() will just set:
>     result.index = (page.baseIndex << baseIndexShift) + index;
> 
> That will give more use a much higher 38-bit index range.  I think 32-bit should be plenty already.

Spoke with Mark, not doing this. Instead we'll just add a fastEntry function we use inside forEachEntry

>> Source/JavaScriptCore/assembler/SecureARM64EHashPins.h:81
>> +        void forEachSetBit(Function function)
> 
> nit: Let's call this forEachEntry.

It's vending a bit, forEachSetBit makes more sense as a name IMO
Comment 11 Darin Adler 2022-01-16 07:51:40 PST
Comment on attachment 449236 [details]
patch

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

> Source/JavaScriptCore/assembler/AssemblerBuffer.h:207
> +    template <bool shouldSign>

Perfect place for our “named enum instead of boolean” technique. ARM64Hash<true> is obscure where ARM64Hash<Sign> and ARM64Hash<DoNotSign> would be clear.
Comment 12 Saam Barati 2022-01-16 11:26:08 PST
Comment on attachment 449236 [details]
patch

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

>> Source/JavaScriptCore/assembler/AssemblerBuffer.h:207
>> +    template <bool shouldSign>
> 
> Perfect place for our “named enum instead of boolean” technique. ARM64Hash<true> is obscure where ARM64Hash<Sign> and ARM64Hash<DoNotSign> would be clear.

Good point. I can fix.
Comment 13 Mark Lam 2022-01-18 15:01:55 PST
Comment on attachment 449236 [details]
patch

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

r=me with comments.

> Source/JavaScriptCore/assembler/AssemblerBuffer.h:211
> +        ARM64EHash()

nit: you can just express this is as `ARM64EHash() = default;`

> Source/JavaScriptCore/assembler/SecureARM64EHashPins.cpp:76
> +    return memory;

Let's return the tagged memory instead, and untag it just before use.

> Source/JavaScriptCore/assembler/SecureARM64EHashPins.cpp:79
> +SecureARM64EHashPins::Page::Page()

Let's make this ALWAYS_INLINE.

> Source/JavaScriptCore/assembler/SecureARM64EHashPins.cpp:88
> +static void initializePage(const WriteToJITRegionScope&, SecureARM64EHashPins::Page* page)

Make ALWAYS_INLINE.

> Source/JavaScriptCore/assembler/SecureARM64EHashPins.cpp:116
> +bool SecureARM64EHashPins::allocatePinForCurrentThreadImpl(const AbstractLocker&)

nit: maybe make the hashPinsLock a static field and make this method WTF_GUARDED_BY_LOCK by the static lock?

> Source/JavaScriptCore/assembler/SecureARM64EHashPins.cpp:141
> +    auto findResult = findEntry();

Let's rename findEntry() to findFirstEntry().  It'll document better what we're actually aiming to do here.

> Source/JavaScriptCore/assembler/SecureARM64EHashPins.cpp:195
> +            initializePage(writeScope, nextPage);

Let's init nextPage by untagging the return value of allocateInExecutableMemory() here just before we use it.

> Source/JavaScriptCore/assembler/SecureARM64EHashPins.cpp:234
> +    // like data structure. The in use pin (top of the stack) will always be at the lowest
> +    // page and lowest index in the bit vector. So when we deallocate the current top of the

"the lowest page and lowest index in the bit vector" reads like it's always in entry 0.  How about adding a qualifier: "the lowest page and lowest index in the bit vector for that thread key."?

> Source/JavaScriptCore/assembler/SecureARM64EHashPins.cpp:238
> +    // Addition also maintains this invariant by always placing the newest entry for

/Addition/Allocation/

> Source/JavaScriptCore/assembler/SecureARM64EHashPins.h:39
> +    JS_EXPORT_PRIVATE uint64_t pinForCurrentThread();

This `JS_EXPORT_PRIVATE` is deceptive since this is an ALWAYS_INLINE function.

> Source/JavaScriptCore/assembler/SecureARM64EHashPins.h:63
> +        inline Entry& fastEntryUnchecked(size_t index)

ALWAYS_INLINE.

> Source/JavaScriptCore/assembler/SecureARM64EHashPins.h:69
> +        void setIsInUse(size_t index)

ALWAYS_INLINE.

> Source/JavaScriptCore/assembler/SecureARM64EHashPins.h:74
> +        void clearIsInUse(size_t index)

ALWAYS_INLINE.

> Source/JavaScriptCore/assembler/SecureARM64EHashPins.h:79
> +        bool isInUse(size_t index)

ALWAYS_INLINE.

> Source/JavaScriptCore/assembler/SecureARM64EHashPins.h:90
> +        void forEachSetBit(Function function)

ALWAYS_INLINE?

> Source/JavaScriptCore/assembler/SecureARM64EHashPins.h:105
> +        Atomic<uint64_t> nextPin { 1 };
> +        Atomic<uint32_t> assertNotReentrant { 0 };

Can you static_assert that nextPin comes before assertNotReentrant?  I think part of our algorithm relies on this.
Comment 14 Mark Lam 2022-01-18 15:23:47 PST
Comment on attachment 449236 [details]
patch

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

> Source/JavaScriptCore/assembler/SecureARM64EHashPins.cpp:154
> +        uint64_t nextPin = metadata->nextPin.exchangeAdd(1, std::memory_order_seq_cst);
> +        RELEASE_ASSERT(nextPin);

I also suggest that we PACGA nextPin with &metadata and store the result in the unused 32-bit in Metadata.  We should recompute the PACGA result here and validate it against the copy stored in Metadata before using nextPin.  After this, we compute the PACGA result for the next nextPin and store that in the Metadata.
Comment 15 Saam Barati 2022-01-19 10:56:26 PST
Created attachment 449496 [details]
patch for landing
Comment 16 Saam Barati 2022-01-19 11:23:47 PST
Created attachment 449500 [details]
patch for landing
Comment 17 Mark Lam 2022-01-19 14:42:29 PST
Comment on attachment 449500 [details]
patch for landing

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

> Source/JavaScriptCore/ChangeLog:8
> +        * CMakeLists.txt:

Your ChangeLog file list need to be updated.  It's missing files.

> Source/JavaScriptCore/assembler/AssemblerBuffer.h:225
> +        ALWAYS_INLINE void prepareForEmittingInstructions()

nit: maybe it'd be better to call this something like `allocatePinForCurrentThreadAndInitializeHash` to reflect that it's the complement of `deallocatePinForCurrentThread`.  We certainly use it that way.

> Source/JavaScriptCore/assembler/SecureARM64EHashPins.cpp:212
> +    auto clear = [&] (Entry& entry) {

/[&]/[]/.  No need to capture anything here.

> Source/WTF/ChangeLog:9
> +        * wtf/Bitmap.h:
> +        (WTF::WordType>::forEachSetBit const):

Your ChangeLog file list need to be updated.  It's missing files.
Comment 18 Mark Lam 2022-01-19 15:00:57 PST
Comment on attachment 449500 [details]
patch for landing

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

> Source/WTF/wtf/Bitmap.h:79
>      void forEachSetBit(const Func&) const;

Should this be ALWAYS_INLINE?
Comment 19 Saam Barati 2022-01-19 15:18:00 PST
Created attachment 449523 [details]
patch for landing
Comment 20 EWS 2022-01-19 17:40:41 PST
Committed r288261 (246205@main): <https://commits.webkit.org/246205@main>

All reviewed patches have been landed. Closing bug and clearing flags on attachment 449523 [details].
Comment 21 Radar WebKit Bug Importer 2022-01-19 17:41:27 PST
<rdar://problem/87801650>