Bug 161763 - [WTF] HashTable's rehash is not compatible to Ref<T> and ASan
Summary: [WTF] HashTable's rehash is not compatible to Ref<T> and ASan
Status: RESOLVED FIXED
Alias: None
Product: WebKit
Classification: Unclassified
Component: Web Template Framework (show other bugs)
Version: WebKit Nightly Build
Hardware: Unspecified Unspecified
: P2 Normal
Assignee: Yusuke Suzuki
URL:
Keywords:
Depends on:
Blocks: 161726
  Show dependency treegraph
 
Reported: 2016-09-08 15:05 PDT by Yusuke Suzuki
Modified: 2016-09-12 16:11 PDT (History)
12 users (show)

See Also:


Attachments
Patch (7.15 KB, patch)
2016-09-08 20:07 PDT, Yusuke Suzuki
no flags Details | Formatted Diff | Diff
Patch for landing (8.34 KB, patch)
2016-09-08 22:06 PDT, Yusuke Suzuki
no flags Details | Formatted Diff | Diff
Patch (2.78 KB, patch)
2016-09-11 15:26 PDT, Yusuke Suzuki
no flags Details | Formatted Diff | Diff

Note You need to log in before you can comment on or make changes to this bug.
Description Yusuke Suzuki 2016-09-08 15:05:57 PDT
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!
Comment 1 Yusuke Suzuki 2016-09-08 15:49:36 PDT
We can take the similar way to the Vector, I think.
Comment 2 Yusuke Suzuki 2016-09-08 20:07:01 PDT
Created attachment 288382 [details]
Patch
Comment 3 Mark Lam 2016-09-08 21:36:50 PDT
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/
Comment 4 Yusuke Suzuki 2016-09-08 22:06:47 PDT
Created attachment 288387 [details]
Patch for landing
Comment 5 Yusuke Suzuki 2016-09-08 22:13:30 PDT
Committed r205694: <http://trac.webkit.org/changeset/205694>
Comment 6 Darin Adler 2016-09-11 09:28:55 PDT
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.
Comment 7 Darin Adler 2016-09-11 09:30:09 PDT
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.
Comment 8 Yusuke Suzuki 2016-09-11 15:17:18 PDT
(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?
Comment 9 Yusuke Suzuki 2016-09-11 15:26:19 PDT
Reopening to attach new patch.
Comment 10 Yusuke Suzuki 2016-09-11 15:26:24 PDT
Created attachment 288533 [details]
Patch
Comment 11 Yusuke Suzuki 2016-09-11 15:31:24 PDT
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.
Comment 12 Yusuke Suzuki 2016-09-11 16:01:57 PDT
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).
Comment 13 Darin Adler 2016-09-12 12:13:09 PDT
(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.
Comment 14 Darin Adler 2016-09-12 12:24:47 PDT
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.
Comment 15 Yusuke Suzuki 2016-09-12 15:49:54 PDT
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.
Comment 16 WebKit Commit Bot 2016-09-12 16:10:54 PDT
Comment on attachment 288533 [details]
Patch

Clearing flags on attachment: 288533

Committed r205836: <http://trac.webkit.org/changeset/205836>
Comment 17 WebKit Commit Bot 2016-09-12 16:11:00 PDT
All reviewed patches have been landed.  Closing bug.