HashMap<Ref<P>, V> asserts when V is not zero for its empty value
authorsbarati@apple.com <sbarati@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Wed, 15 Aug 2018 04:08:08 +0000 (04:08 +0000)
committersbarati@apple.com <sbarati@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Wed, 15 Aug 2018 04:08:08 +0000 (04:08 +0000)
https://bugs.webkit.org/show_bug.cgi?id=188582

Reviewed by Sam Weinig.

Source/JavaScriptCore:

* runtime/SparseArrayValueMap.h:

Source/WTF:

The issue happened when we'd fill the hash table buffer with empty values. We
would iterate the buffer and invoke placement new with the incoming value being the
empty value. For Ref, this means that, we'd call its move constructor, which calls
leakRef(), which asserts that the Ref's pointer is not null. We'd like to keep
this assert since it catches bugs where you leakRef() more than once or WTFMove
an already moved Ref.

This patch fixes this issue by adding a new trait for constructing an empty
value. We use that in HashTable instead of directly calling placement new.

* wtf/HashTable.h:
(WTF::HashTableBucketInitializer<false>::initialize):
* wtf/HashTraits.h:
(WTF::GenericHashTraits::constructEmptyValue):
(WTF::HashTraits<Ref<P>>::constructEmptyValue):
(WTF::KeyValuePairHashTraits::constructEmptyValue):

Tools:

* TestWebKitAPI/Tests/WTF/HashMap.cpp:
(TestWebKitAPI::TEST):

git-svn-id: https://svn.webkit.org/repository/webkit/trunk@234879 268f45cc-cd09-0410-ab3c-d52691b4dbfc

Source/JavaScriptCore/ChangeLog
Source/JavaScriptCore/runtime/SparseArrayValueMap.h
Source/WTF/ChangeLog
Source/WTF/wtf/HashTable.h
Source/WTF/wtf/HashTraits.h
Tools/ChangeLog
Tools/TestWebKitAPI/Tests/WTF/HashMap.cpp

index eb702fe..ebd0774 100644 (file)
@@ -1,3 +1,12 @@
+2018-08-14  Saam barati  <sbarati@apple.com>
+
+        HashMap<Ref<P>, V> asserts when V is not zero for its empty value
+        https://bugs.webkit.org/show_bug.cgi?id=188582
+
+        Reviewed by Sam Weinig.
+
+        * runtime/SparseArrayValueMap.h:
+
 2018-08-14  Yusuke Suzuki  <yusukesuzuki@slowstart.org>
 
         Unreviewed, attempt to fix CLoop build
index 771097b..4c160b7 100644 (file)
@@ -37,6 +37,7 @@ namespace JSC {
 class SparseArrayValueMap;
 
 class SparseArrayEntry : private WriteBarrier<Unknown> {
+    WTF_MAKE_FAST_ALLOCATED;
 public:
     using Base = WriteBarrier<Unknown>;
 
index a65ff5f..37d41f2 100644 (file)
@@ -1,3 +1,27 @@
+2018-08-14  Saam barati  <sbarati@apple.com>
+
+        HashMap<Ref<P>, V> asserts when V is not zero for its empty value
+        https://bugs.webkit.org/show_bug.cgi?id=188582
+
+        Reviewed by Sam Weinig.
+
+        The issue happened when we'd fill the hash table buffer with empty values. We
+        would iterate the buffer and invoke placement new with the incoming value being the
+        empty value. For Ref, this means that, we'd call its move constructor, which calls
+        leakRef(), which asserts that the Ref's pointer is not null. We'd like to keep
+        this assert since it catches bugs where you leakRef() more than once or WTFMove
+        an already moved Ref.
+        
+        This patch fixes this issue by adding a new trait for constructing an empty
+        value. We use that in HashTable instead of directly calling placement new.
+
+        * wtf/HashTable.h:
+        (WTF::HashTableBucketInitializer<false>::initialize):
+        * wtf/HashTraits.h:
+        (WTF::GenericHashTraits::constructEmptyValue):
+        (WTF::HashTraits<Ref<P>>::constructEmptyValue):
+        (WTF::KeyValuePairHashTraits::constructEmptyValue):
+
 2018-08-14  Fujii Hironori  <Hironori.Fujii@sony.com>
 
         Unreviewed, rolling out r234859.
index e6a950f..809adbf 100644 (file)
@@ -837,7 +837,7 @@ namespace WTF {
     template<> struct HashTableBucketInitializer<false> {
         template<typename Traits, typename Value> static void initialize(Value& bucket)
         {
-            new (NotNull, std::addressof(bucket)) Value(Traits::emptyValue());
+            Traits::template constructEmptyValue<Traits>(bucket);
         }
     };
 
index ebf3905..dec59f6 100644 (file)
@@ -70,6 +70,12 @@ template<typename T> struct GenericHashTraits : GenericHashTraitsBase<std::is_in
         emptyValue = std::forward<V>(value);
     }
 
+    template <typename Traits>
+    static void constructEmptyValue(T& slot)
+    {
+        new (NotNull, std::addressof(slot)) T(Traits::emptyValue());
+    }
+
     // Type for return value of functions that do not transfer ownership, such as get.
     typedef T PeekType;
     template<typename U> static U&& peek(U&& value) { return std::forward<U>(value); }
@@ -191,6 +197,12 @@ template<typename P> struct HashTraits<Ref<P>> : SimpleClassHashTraits<Ref<P>> {
     static const bool emptyValueIsZero = true;
     static Ref<P> emptyValue() { return HashTableEmptyValue; }
 
+    template <typename>
+    static void constructEmptyValue(Ref<P>& slot)
+    {
+        new (NotNull, std::addressof(slot)) Ref<P>(HashTableEmptyValue);
+    }
+
     static const bool hasIsEmptyValueFunction = true;
     static bool isEmptyValue(const Ref<P>& value) { return value.isHashTableEmptyValue(); }
 
@@ -302,6 +314,13 @@ struct KeyValuePairHashTraits : GenericHashTraits<KeyValuePair<typename KeyTrait
     static const bool emptyValueIsZero = KeyTraits::emptyValueIsZero && ValueTraits::emptyValueIsZero;
     static EmptyValueType emptyValue() { return KeyValuePair<typename KeyTraits::EmptyValueType, typename ValueTraits::EmptyValueType>(KeyTraits::emptyValue(), ValueTraits::emptyValue()); }
 
+    template <typename>
+    static void constructEmptyValue(TraitType& slot)
+    {
+        KeyTraits::template constructEmptyValue<KeyTraits>(slot.key);
+        ValueTraits::template constructEmptyValue<ValueTraits>(slot.value);
+    }
+
     static const unsigned minimumTableSize = KeyTraits::minimumTableSize;
 
     static void constructDeletedValue(TraitType& slot) { KeyTraits::constructDeletedValue(slot.key); }
index d763dc2..b410a92 100644 (file)
@@ -1,3 +1,13 @@
+2018-08-14  Saam barati  <sbarati@apple.com>
+
+        HashMap<Ref<P>, V> asserts when V is not zero for its empty value
+        https://bugs.webkit.org/show_bug.cgi?id=188582
+
+        Reviewed by Sam Weinig.
+
+        * TestWebKitAPI/Tests/WTF/HashMap.cpp:
+        (TestWebKitAPI::TEST):
+
 2018-08-14  Zalan Bujtas  <zalan@apple.com>
 
         [LFC][Floating] Add support for negative clearance.
index cb13c93..4399da8 100644 (file)
@@ -945,4 +945,47 @@ TEST(WTF_HashMap, DeletedAddressOfOperator)
         (void)value;
 }
 
+TEST(WTF_HashMap, RefMappedToNonZeroEmptyValue)
+{
+    class Value {
+    public:
+        Value() = default;
+        Value(Value&&) = default;
+        Value(const Value&) = default;
+        Value& operator=(Value&&) = default;
+
+        Value(int32_t f)
+            : m_field(f)
+        { }
+
+        int32_t field() { return m_field; }
+
+    private:
+        int32_t m_field { 0xbadbeef };
+    };
+
+    class Key : public RefCounted<Key> {
+        Key() = default;
+    public:
+        static Ref<Key> create() { return adoptRef(*new Key); }
+    };
+
+    static_assert(!WTF::HashTraits<Value>::emptyValueIsZero, "");
+
+    HashMap<Ref<Key>, Value> map;
+    Vector<std::pair<Ref<Key>, int32_t>> vectorMap;
+
+    for (int32_t i = 0; i < 160; ++i) {
+        Ref<Key> key = Key::create();
+        map.add(Ref<Key>(key.get()), Value { i });
+        vectorMap.append({ WTFMove(key), i });
+    }
+
+    for (auto& pair : vectorMap)
+        ASSERT_EQ(pair.second, map.get(pair.first).field());
+
+    for (auto& pair : vectorMap)
+        ASSERT_TRUE(map.remove(pair.first));
+}
+
 } // namespace TestWebKitAPI