Changeset 234879 in webkit

Timestamp:

Aug 14, 2018 9:08:08 PM (6 years ago)

Author:

sbarati@apple.com

Message:

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.

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):

Location:

trunk

Files:

• Source/JavaScriptCore/ChangeLog (modified) (1 diff)
• Source/JavaScriptCore/runtime/SparseArrayValueMap.h (modified) (1 diff)
• Source/WTF/ChangeLog (modified) (1 diff)
• Source/WTF/wtf/HashTable.h (modified) (1 diff)
• Source/WTF/wtf/HashTraits.h (modified) (3 diffs)
• Tools/ChangeLog (modified) (1 diff)
• Tools/TestWebKitAPI/Tests/WTF/HashMap.cpp (modified) (1 diff)

trunk/Source/JavaScriptCore/ChangeLog

@@ +1 @@
+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>
 

trunk/Source/JavaScriptCore/runtime/SparseArrayValueMap.h

@@ -38 +38 @@
 
 class SparseArrayEntry : private WriteBarrier<Unknown> {
+    WTF_MAKE_FAST_ALLOCATED;
 public:
     using Base = WriteBarrier<Unknown>;

trunk/Source/WTF/ChangeLog

@@ +1 @@
+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>
 

trunk/Source/WTF/wtf/HashTable.h

@@ -838 +838 @@
         template<typename Traits, typename Value> static void initialize(Value& bucket)
         {
-            new (NotNull, std::addressof(bucket)) Value(Traits::emptyValue());
+            Traits::template constructEmptyValue<Traits>(bucket);
         }
     };

trunk/Source/WTF/wtf/HashTraits.h

@@ -71 +71 @@
     }
 
+    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;
@@ -192 +198 @@
     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(); }
@@ -303 +315 @@
     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;
 

trunk/Tools/ChangeLog

@@ +1 @@
+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>
 

trunk/Tools/TestWebKitAPI/Tests/WTF/HashMap.cpp

@@ -946 +946 @@
 }
 
+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