Bug 215100 – IndexSparseSet::sort() should update m_map

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

[Robin Morisset]

IndexSparseSet is made of two fields: m_values and m_map, and the two must be kept in sync.
But its sort routine currently only sorts m_values.
This might be related to a random crash that seems to occasionally occur in the vicinity of this code in the wild.

[Robin Morisset]

Created attachment 405862 [details]
Patch

[Mark Lam]

Comment on attachment 405862 [details]
Patch

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

r=me.  Please also fix the case in IndexSparseSet::remove() where it is doing a comparison of (m_values[position] == value) when it should be comparing (EntryTypeTraits::key(m_values[position]) == value).

> Source/WTF/wtf/IndexSparseSet.h:103
> +    void validate();

Can you make this a no-op on !ASSERT_ENABLED builds i.e. an empty ALWAYS_INLINE function on release builds?  I'm not sure it makes sense to pay the price of this validation on a release build (and paying it twice too).

> Source/WTF/wtf/IndexSparseSet.h:240
> +template<typename EntryType, typename EntryTypeTraits, typename OverflowHandler>
> +void IndexSparseSet<EntryType, EntryTypeTraits, OverflowHandler>::validate()
> +{
> +    for (unsigned val : *this)
> +        RELEASE_ASSERT(contains(val));
>  }

Make this conditional on #if ASSERT_ENABLED.

While you're at it, can you also ASSERT that m_values.size() <= m_map.size()?

[Yusuke Suzuki]

Comment on attachment 405862 [details]
Patch

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

r=me too.

> Source/WTF/ChangeLog:10
> +        This might be related to a random crash that seems to occasionally occur in the vicinity of this code in the wild (rdar://problem/64594569)

Can you add it as a part of TestWTF test which test does not crash with this change?

> Source/WTF/wtf/IndexSparseSet.h:225
> +    // Bring m_map back in sync with m_values
> +    // Should fix rdar://problem/64594569

I think these comments are not necessary if we have a test.

[Robin Morisset]

(In reply to Mark Lam from comment #2)
> Comment on attachment 405862 [details]
> Patch
> 
> View in context:
> https://bugs.webkit.org/attachment.cgi?id=405862&action=review
> 
> r=me.  Please also fix the case in IndexSparseSet::remove() where it is
> doing a comparison of (m_values[position] == value) when it should be
> comparing (EntryTypeTraits::key(m_values[position]) == value).

Done, good catch.

> > Source/WTF/wtf/IndexSparseSet.h:103
> > +    void validate();
> 
> Can you make this a no-op on !ASSERT_ENABLED builds i.e. an empty
> ALWAYS_INLINE function on release builds?  I'm not sure it makes sense to
> pay the price of this validation on a release build (and paying it twice
> too).

I wanted this as a RELEASE_ASSERT so it could catch possible remaining problems in seed. But since this code no longer appears as a top-crasher in telemetry, I'm ok with making it limited to debug builds.
Instead of changing validate() itself, I am making the calls to it conditional on ASSERT_ENABLED. This way we can still run validate() in the debugger, even if on a release build.
> > Source/WTF/wtf/IndexSparseSet.h:240
> > +template<typename EntryType, typename EntryTypeTraits, typename OverflowHandler>
> > +void IndexSparseSet<EntryType, EntryTypeTraits, OverflowHandler>::validate()
> > +{
> > +    for (unsigned val : *this)
> > +        RELEASE_ASSERT(contains(val));
> >  }
> 
> Make this conditional on #if ASSERT_ENABLED.
> 
> While you're at it, can you also ASSERT that m_values.size() <= m_map.size()?

Added.

[Robin Morisset]

Created attachment 406102 [details]
Patch

[Robin Morisset]

(In reply to Yusuke Suzuki from comment #3)
> Comment on attachment 405862 [details]
> Patch
> 
> View in context:
> https://bugs.webkit.org/attachment.cgi?id=405862&action=review
> 
> r=me too.
> 
> > Source/WTF/ChangeLog:10
> > +        This might be related to a random crash that seems to occasionally occur in the vicinity of this code in the wild (rdar://problem/64594569)
> 
> Can you add it as a part of TestWTF test which test does not crash with this
> change?

Thanks, I had forgotten the existence of TestWTF. I found out that IndexSparseSet was fully untested, so I wrote a suite of tests for it.

> > Source/WTF/wtf/IndexSparseSet.h:225
> > +    // Bring m_map back in sync with m_values
> > +    // Should fix rdar://problem/64594569
> 
> I think these comments are not necessary if we have a test.

I removed most comments, but left some which I felt were more useful.

[Yusuke Suzuki]

Comment on attachment 406102 [details]
Patch

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

r=me

> Source/WTF/wtf/IndexSparseSet.h:225
> +    }

It is nice if we have

#if ASSERT_ENABLED
validate();
#endif

here.

[Mark Lam]

Comment on attachment 406102 [details]
Patch

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

r=me too.

>> Source/WTF/wtf/IndexSparseSet.h:225
>> +    }
> 
> It is nice if we have
> 
> #if ASSERT_ENABLED
> validate();
> #endif
> 
> here.

+1.

[Robin Morisset]

Created attachment 406168 [details]
Patch for landing

[Robin Morisset]

(In reply to Yusuke Suzuki from comment #7)
> Comment on attachment 406102 [details]
> Patch
> 
> View in context:
> https://bugs.webkit.org/attachment.cgi?id=406102&action=review
> 
> r=me
> 
> > Source/WTF/wtf/IndexSparseSet.h:225
> > +    }
> 
> It is nice if we have
> 
> #if ASSERT_ENABLED
> validate();
> #endif
> 
> here.

Thanks for the review. I assumed that this validation was no longer necessary now that we have dedicated tests, but since both Mark and you want it I've added it back in.

[EWS]

Committed r265371: <https://trac.webkit.org/changeset/265371>

All reviewed patches have been landed. Closing bug and clearing flags on attachment 406168 [details].

[Radar WebKit Bug Importer]

<rdar://problem/66679684>

[Truitt Savell]

It looks like the changes in https://trac.webkit.org/changeset/265371/webkit

has caused 50+ crashes on Mac Debug: https://build.webkit.org/builders/Apple%20Mojave%20Debug%20WK1%20%28Tests%29/builds/12763