Bug 161763 – [WTF] HashTable's rehash is not compatible to Ref<T> and ASan

• Component: Web Template Framework
• Status: RESOLVED FIXED

[Yusuke Suzuki]

In HashTable::rehash, we perform reinsert(WTFMove(oldTable[i])).
Of course, later, this oldTable[i]'s destructor should be called.
But unfortunately, we decide whether we should call the destructor for the given entry by checking (!isDeletedBucket(table[i])) in HashTable::deallocateTable().
At that case, if the target is already moved, we accidentally touch the poisoned entry!

[Yusuke Suzuki]

We can take the similar way to the Vector, I think.

[Yusuke Suzuki]

Created attachment 288382 [details]
Patch

[Mark Lam]

Comment on attachment 288382 [details]
Patch

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

r=me.

> Source/WTF/ChangeLog:8
> +        If we move a object, the location which the moved object used should not be touched anymore.

/a object/an object/

[Yusuke Suzuki]

Created attachment 288387 [details]
Patch for landing

[Yusuke Suzuki]

Committed r205694: <http://trac.webkit.org/changeset/205694>

[Darin Adler]

Comment on attachment 288387 [details]
Patch for landing

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

> Source/WTF/wtf/HashTable.h:1157
> -            if (!isDeletedBucket(table[i]))
> +            if (!isEmptyOrDeletedBucket(table[i]))
>                  table[i].~ValueType();

This breaks hash tables for types where empty objects need to be destroyed. Support for that is a feature. I understand it’s not helpful for Ref, but it’s not OK to just skip the destructor for an arbitrary type; perhaps this is not an issue with any of the existing types, but it’s wrong to do this globally for all types.

[Darin Adler]

We should come up with an alternate fix that doesn’t create the new requirement that empty objects don’t need destruction. Or we could double check that we don’t need the features of destroying empty objects and change the rules for hash tables.

[Yusuke Suzuki]

(In reply to comment #7)
> We should come up with an alternate fix that doesn’t create the new
> requirement that empty objects don’t need destruction. Or we could double
> check that we don’t need the features of destroying empty objects and change
> the rules for hash tables.

So, is Ref.h's comment "// Hash table deleted/empty values, which are only constructed and never copied or destroyed." invalid?

[Yusuke Suzuki]

Reopening to attach new patch.

[Yusuke Suzuki]

Created attachment 288533 [details]
Patch

[Yusuke Suzuki]

So, newly introducing the rule that empty value should not be destroyed is not good.
I've uploaded the patch, which ensures that destructors are also called for empty values.

[Yusuke Suzuki]

Comment on attachment 288533 [details]
Patch

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

> Source/WTF/wtf/HashTable.h:1212
>              oldTable[i].~ValueType();

Alternative implementation could be considered: making the bucket deleted (and calling deallocateTable later).

Pros:
    simple
Cons:
    unnecessary store happens here (to make this bucket deleted).

[Darin Adler]

(In reply to comment #8)
> (In reply to comment #7)
> > We should come up with an alternate fix that doesn’t create the new
> > requirement that empty objects don’t need destruction. Or we could double
> > check that we don’t need the features of destroying empty objects and change
> > the rules for hash tables.
> 
> So, is Ref.h's comment "// Hash table deleted/empty values, which are only
> constructed and never copied or destroyed." invalid?

Yes, I am pretty sure that comment is incorrect for empty values.

I am not saying we can’t change things if we like, but at present I believe deleted values are special and are never copied or destroyed but empty values are not.

[Darin Adler]

Comment on attachment 288533 [details]
Patch

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

>> Source/WTF/wtf/HashTable.h:1212
>>              oldTable[i].~ValueType();
> 
> Alternative implementation could be considered: making the bucket deleted (and calling deallocateTable later).
> 
> Pros:
>     simple
> Cons:
>     unnecessary store happens here (to make this bucket deleted).

Generally we have to destroy a value before marking a bucket deleted. So it seems that marking a bucket deleted would be in *addition* to the destructor, not instead of the destructor. So I am not sure there is any benefit there. I suppose we could drop all the code in this loop that calls destructors if we instead call deallocateTable on the old table after we are done, but I am not sure what benefit that would have; iterating the table a second time seems like unnecessary extra work.

What’s possibly missing, I think, is an optimization for classes like RefPtr and Ref. For those classes, it is safe to drop a moved-from value or an empty value without running the destructor. I am not sure if there is enough inlining for the compiler to discard the dead destructor code that checks the pointer for null and decrements the reference count. Maybe the compiler can see that the pointer is null and optimize all that code out. In both the empty bucket case above and in the "just moved from this bucket" case. But if the compiler doesn’t do that optimization, we could add a new trait and optimize that explicitly here in the C++ code. Either way, the destructor calls here should expand to no code at all in the Ref and RefPtr case.

[Yusuke Suzuki]

Comment on attachment 288533 [details]
Patch

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

Thank you for your review!

>>> Source/WTF/wtf/HashTable.h:1212
>>>              oldTable[i].~ValueType();
>> 
>> Alternative implementation could be considered: making the bucket deleted (and calling deallocateTable later).
>> 
>> Pros:
>>     simple
>> Cons:
>>     unnecessary store happens here (to make this bucket deleted).
> 
> Generally we have to destroy a value before marking a bucket deleted. So it seems that marking a bucket deleted would be in *addition* to the destructor, not instead of the destructor. So I am not sure there is any benefit there. I suppose we could drop all the code in this loop that calls destructors if we instead call deallocateTable on the old table after we are done, but I am not sure what benefit that would have; iterating the table a second time seems like unnecessary extra work.
> 
> What’s possibly missing, I think, is an optimization for classes like RefPtr and Ref. For those classes, it is safe to drop a moved-from value or an empty value without running the destructor. I am not sure if there is enough inlining for the compiler to discard the dead destructor code that checks the pointer for null and decrements the reference count. Maybe the compiler can see that the pointer is null and optimize all that code out. In both the empty bucket case above and in the "just moved from this bucket" case. But if the compiler doesn’t do that optimization, we could add a new trait and optimize that explicitly here in the C++ code. Either way, the destructor calls here should expand to no code at all in the Ref and RefPtr case.

The benefit is just dropping this isEmptyBucket branch here. It makes this loop super tight for isEmptyOrDeletedBucket case. But anyway, in that case, we need the additional loop after this loop, so I don't think it is good.

And interesting. Ideally, dead destructor should not be called. Currently, in WTF::Vector, such cases are handled by canMoveWithMemcpy: memcpy & memmove are used to move Ref & RefPtr and it does not call destructors.

[WebKit Commit Bot]

Comment on attachment 288533 [details]
Patch

Clearing flags on attachment: 288533

Committed r205836: <http://trac.webkit.org/changeset/205836>

[WebKit Commit Bot]

All reviewed patches have been landed.  Closing bug.