- Revision
- 198827
- Author
- commit-qu...@webkit.org
- Date
- 2016-03-29 22:13:04 -0700 (Tue, 29 Mar 2016)
Log Message
[WTF] Removing a smart pointer from HashTable issues two stores to the same location
https://bugs.webkit.org/show_bug.cgi?id=155676
Patch by Benjamin Poulain <bpoul...@apple.com> on 2016-03-29
Reviewed by Darin Adler.
Source/WTF:
While working on the hot loop of r198376, I noticed something
weird...
Every time we removed a smart pointer from the hash table,
the code generated was something like:
Load([bucket]) -> Tmp
Store(0 -> [bucket])
JumpIfZero(Tmp, ->End)
Call fastFree()
Store(-1 -> [bucket])
-> End:
The useless store before the branch is annoying, especially on ARM.
Here is what happens:
1) The destructor of the smart pointer swaps its internal value with nullptr.
2) Since the smart pointer is not a local in-register value, that nullptr
is stored in memory because it could be observable from fastFree().
3) The destructor destroy the value if not zero (or deref for RefPtr).
The "if-not-zero" may or may not be eliminated depending on what
is between getting the iterator and the call to remove().
4) fastFree() is called.
5) The deleted value is set in the bucket.
This patch adds custom deletion for those cases to avoid the useless
store. The useless null check is still eliminated when we are lucky.
I went this path instead of changing the destructor of RefPtr for two reasons:
-I need this to work in unique_ptr for JSC.
-Nulling the memory may have security advantages in the cases where we do not immediately
write over that memory again.
This patch removes 13kb out of x86_64 WebCore.
* wtf/HashTable.h:
(WTF::HashTable::deleteBucket):
(WTF::KeyTraits>::removeIf):
* wtf/HashTraits.h:
(WTF::HashTraits<RefPtr<P>>::customDeleteBucket):
(WTF::hashTraitsDeleteBucket):
(WTF::KeyValuePairHashTraits::customDeleteBucket):
* wtf/text/AtomicStringHash.h:
(WTF::HashTraits<WTF::AtomicString>::isEmptyValue):
(WTF::HashTraits<WTF::AtomicString>::customDeleteBucket):
* wtf/text/StringHash.h:
(WTF::HashTraits<String>::customDeleteBucket):
Tools:
* TestWebKitAPI/Tests/WTF/HashMap.cpp:
* TestWebKitAPI/Tests/WTF/HashSet.cpp:
Modified Paths
Diff
Modified: trunk/Source/WTF/ChangeLog (198826 => 198827)
--- trunk/Source/WTF/ChangeLog 2016-03-30 04:16:48 UTC (rev 198826)
+++ trunk/Source/WTF/ChangeLog 2016-03-30 05:13:04 UTC (rev 198827)
@@ -1,3 +1,56 @@
+2016-03-29 Benjamin Poulain <bpoul...@apple.com>
+
+ [WTF] Removing a smart pointer from HashTable issues two stores to the same location
+ https://bugs.webkit.org/show_bug.cgi?id=155676
+
+ Reviewed by Darin Adler.
+
+ While working on the hot loop of r198376, I noticed something
+ weird...
+ Every time we removed a smart pointer from the hash table,
+ the code generated was something like:
+ Load([bucket]) -> Tmp
+ Store(0 -> [bucket])
+ JumpIfZero(Tmp, ->End)
+ Call fastFree()
+ Store(-1 -> [bucket])
+ -> End:
+
+ The useless store before the branch is annoying, especially on ARM.
+
+ Here is what happens:
+ 1) The destructor of the smart pointer swaps its internal value with nullptr.
+ 2) Since the smart pointer is not a local in-register value, that nullptr
+ is stored in memory because it could be observable from fastFree().
+ 3) The destructor destroy the value if not zero (or deref for RefPtr).
+ The "if-not-zero" may or may not be eliminated depending on what
+ is between getting the iterator and the call to remove().
+ 4) fastFree() is called.
+ 5) The deleted value is set in the bucket.
+
+ This patch adds custom deletion for those cases to avoid the useless
+ store. The useless null check is still eliminated when we are lucky.
+
+ I went this path instead of changing the destructor of RefPtr for two reasons:
+ -I need this to work in unique_ptr for JSC.
+ -Nulling the memory may have security advantages in the cases where we do not immediately
+ write over that memory again.
+
+ This patch removes 13kb out of x86_64 WebCore.
+
+ * wtf/HashTable.h:
+ (WTF::HashTable::deleteBucket):
+ (WTF::KeyTraits>::removeIf):
+ * wtf/HashTraits.h:
+ (WTF::HashTraits<RefPtr<P>>::customDeleteBucket):
+ (WTF::hashTraitsDeleteBucket):
+ (WTF::KeyValuePairHashTraits::customDeleteBucket):
+ * wtf/text/AtomicStringHash.h:
+ (WTF::HashTraits<WTF::AtomicString>::isEmptyValue):
+ (WTF::HashTraits<WTF::AtomicString>::customDeleteBucket):
+ * wtf/text/StringHash.h:
+ (WTF::HashTraits<String>::customDeleteBucket):
+
2016-03-28 Brian Burg <bb...@apple.com>
Web Automation: implement Automation.performMouseInteraction
Modified: trunk/Source/WTF/wtf/HashTable.h (198826 => 198827)
--- trunk/Source/WTF/wtf/HashTable.h 2016-03-30 04:16:48 UTC (rev 198826)
+++ trunk/Source/WTF/wtf/HashTable.h 2016-03-30 05:13:04 UTC (rev 198827)
@@ -456,7 +456,7 @@
ValueType* reinsert(ValueType&&);
static void initializeBucket(ValueType& bucket);
- static void deleteBucket(ValueType& bucket) { bucket.~ValueType(); Traits::constructDeletedValue(bucket); }
+ static void deleteBucket(ValueType& bucket) { hashTraitsDeleteBucket<Traits>(bucket); }
FullLookupType makeLookupResult(ValueType* position, bool found, unsigned hash)
{ return FullLookupType(LookupType(position, found), hash); }
@@ -1108,18 +1108,26 @@
template<typename Functor>
inline void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::removeIf(const Functor& functor)
{
+ // We must use local copies in case "functor" or "deleteBucket"
+ // make a function call, which prevents the compiler from keeping
+ // the values in register.
+ unsigned removedBucketCount = 0;
+ ValueType* table = m_table;
+
for (unsigned i = m_tableSize; i--;) {
- if (isEmptyOrDeletedBucket(m_table[i]))
+ ValueType& bucket = table[i];
+ if (isEmptyOrDeletedBucket(bucket))
continue;
- if (!functor(m_table[i]))
+ if (!functor(bucket))
continue;
- deleteBucket(m_table[i]);
- ++m_deletedCount;
- --m_keyCount;
+ deleteBucket(bucket);
+ ++removedBucketCount;
}
-
+ m_deletedCount += removedBucketCount;
+ m_keyCount -= removedBucketCount;
+
if (shouldShrink())
shrink();
Modified: trunk/Source/WTF/wtf/HashTraits.h (198826 => 198827)
--- trunk/Source/WTF/wtf/HashTraits.h 2016-03-30 04:16:48 UTC (rev 198826)
+++ trunk/Source/WTF/wtf/HashTraits.h 2016-03-30 05:13:04 UTC (rev 198827)
@@ -123,6 +123,30 @@
typedef T* PeekType;
static T* peek(const std::unique_ptr<T, Deleter>& value) { return value.get(); }
static T* peek(std::nullptr_t) { return nullptr; }
+
+ static void customDeleteBucket(std::unique_ptr<T, Deleter>& value)
+ {
+ // The custom delete function exists to avoid a dead store before the value is destructed.
+ // The normal destruction sequence of a bucket would be:
+ // 1) Call the destructor of unique_ptr.
+ // 2) unique_ptr store a zero for its internal pointer.
+ // 3) unique_ptr destroys its value.
+ // 4) Call constructDeletedValue() to set the bucket as destructed.
+ //
+ // The problem is the call in (3) prevents the compile from eliminating the dead store in (2)
+ // becase a side effect of free() could be observing the value.
+ //
+ // This version of deleteBucket() ensures the dead 2 stores changing "value"
+ // are on the same side of the function call.
+ ASSERT(!isDeletedValue(value));
+ T* pointer = value.release();
+ constructDeletedValue(value);
+
+ // The null case happens if a caller uses std::move() to remove the pointer before calling remove()
+ // with an iterator. This is very uncommon.
+ if (LIKELY(pointer))
+ Deleter()(pointer);
+ }
};
template<typename P> struct HashTraits<RefPtr<P>> : SimpleClassHashTraits<RefPtr<P>> {
@@ -131,11 +155,21 @@
typedef P* PeekType;
static PeekType peek(const RefPtr<P>& value) { return value.get(); }
static PeekType peek(P* value) { return value; }
+
+ static void customDeleteBucket(RefPtr<P>& value)
+ {
+ // See unique_ptr's customDeleteBucket() for an explanation.
+ ASSERT(!SimpleClassHashTraits<RefPtr<P>>::isDeletedValue(value));
+ auto valueToBeDestroyed = WTFMove(value);
+ SimpleClassHashTraits<RefPtr<P>>::constructDeletedValue(value);
+ }
};
template<> struct HashTraits<String> : SimpleClassHashTraits<String> {
static const bool hasIsEmptyValueFunction = true;
static bool isEmptyValue(const String&);
+
+ static void customDeleteBucket(String&);
};
// This struct template is an implementation detail of the isHashTraitsEmptyValue function,
@@ -152,6 +186,30 @@
return HashTraitsEmptyValueChecker<Traits, Traits::hasIsEmptyValueFunction>::isEmptyValue(value);
}
+template<typename Traits, typename T>
+struct HashTraitHasCustomDelete {
+ static T& bucketArg;
+ template<typename X> static std::true_type TestHasCustomDelete(X*, decltype(X::customDeleteBucket(bucketArg))* = nullptr);
+ static std::false_type TestHasCustomDelete(...);
+ typedef decltype(TestHasCustomDelete(static_cast<Traits*>(nullptr))) ResultType;
+ static const bool value = ResultType::value;
+};
+
+template<typename Traits, typename T>
+typename std::enable_if<HashTraitHasCustomDelete<Traits, T>::value>::type
+hashTraitsDeleteBucket(T& value)
+{
+ Traits::customDeleteBucket(value);
+}
+
+template<typename Traits, typename T>
+typename std::enable_if<!HashTraitHasCustomDelete<Traits, T>::value>::type
+hashTraitsDeleteBucket(T& value)
+{
+ value.~T();
+ Traits::constructDeletedValue(value);
+}
+
template<typename FirstTraitsArg, typename SecondTraitsArg>
struct PairHashTraits : GenericHashTraits<std::pair<typename FirstTraitsArg::TraitType, typename SecondTraitsArg::TraitType>> {
typedef FirstTraitsArg FirstTraits;
@@ -203,6 +261,7 @@
typedef ValueTraitsArg ValueTraits;
typedef KeyValuePair<typename KeyTraits::TraitType, typename ValueTraits::TraitType> TraitType;
typedef KeyValuePair<typename KeyTraits::EmptyValueType, typename ValueTraits::EmptyValueType> EmptyValueType;
+ typedef typename ValueTraitsArg::TraitType ValueType;
static const bool emptyValueIsZero = KeyTraits::emptyValueIsZero && ValueTraits::emptyValueIsZero;
static EmptyValueType emptyValue() { return KeyValuePair<typename KeyTraits::EmptyValueType, typename ValueTraits::EmptyValueType>(KeyTraits::emptyValue(), ValueTraits::emptyValue()); }
@@ -211,6 +270,15 @@
static void constructDeletedValue(TraitType& slot) { KeyTraits::constructDeletedValue(slot.key); }
static bool isDeletedValue(const TraitType& value) { return KeyTraits::isDeletedValue(value.key); }
+
+ static void customDeleteBucket(TraitType& value)
+ {
+ static_assert(std::is_trivially_destructible<KeyValuePair<int, int>>::value,
+ "The wrapper itself has to be trivially destructible for customDeleteBucket() to make sense, since we do not destruct the wrapper itself.");
+
+ hashTraitsDeleteBucket<KeyTraits>(value.key);
+ value.value.~ValueType();
+ }
};
template<typename Key, typename Value>
Modified: trunk/Source/WTF/wtf/text/AtomicStringHash.h (198826 => 198827)
--- trunk/Source/WTF/wtf/text/AtomicStringHash.h 2016-03-30 04:16:48 UTC (rev 198826)
+++ trunk/Source/WTF/wtf/text/AtomicStringHash.h 2016-03-30 05:13:04 UTC (rev 198827)
@@ -48,9 +48,22 @@
static const bool safeToCompareToEmptyOrDeleted = false;
};
- // AtomicStringHash is the default hash for AtomicString
- template<> struct HashTraits<WTF::AtomicString> : SimpleClassHashTraits<WTF::AtomicString> { };
+ template<> struct HashTraits<WTF::AtomicString> : SimpleClassHashTraits<WTF::AtomicString> {
+ static const bool hasIsEmptyValueFunction = true;
+ static bool isEmptyValue(const AtomicString& value)
+ {
+ return value.isNull();
+ }
+ static void customDeleteBucket(AtomicString& value)
+ {
+ // See unique_ptr's customDeleteBucket() for an explanation.
+ ASSERT(!isDeletedValue(value));
+ AtomicString valueToBeDestroyed = WTFMove(value);
+ constructDeletedValue(value);
+ }
+ };
+
}
using WTF::AtomicStringHash;
Modified: trunk/Source/WTF/wtf/text/StringHash.h (198826 => 198827)
--- trunk/Source/WTF/wtf/text/StringHash.h 2016-03-30 04:16:48 UTC (rev 198826)
+++ trunk/Source/WTF/wtf/text/StringHash.h 2016-03-30 05:13:04 UTC (rev 198827)
@@ -33,6 +33,14 @@
return value.isNull();
}
+ inline void HashTraits<String>::customDeleteBucket(String& value)
+ {
+ // See unique_ptr's customDeleteBucket() for an explanation.
+ ASSERT(!isDeletedValue(value));
+ String valueToBeDestroyed = WTFMove(value);
+ constructDeletedValue(value);
+ }
+
// The hash() functions on StringHash and ASCIICaseInsensitiveHash do not support
// null strings. get(), contains(), and add() on HashMap<String,..., StringHash>
// cause a null-pointer dereference when passed null strings.
Modified: trunk/Tools/ChangeLog (198826 => 198827)
--- trunk/Tools/ChangeLog 2016-03-30 04:16:48 UTC (rev 198826)
+++ trunk/Tools/ChangeLog 2016-03-30 05:13:04 UTC (rev 198827)
@@ -1,3 +1,13 @@
+2016-03-29 Benjamin Poulain <bpoul...@apple.com>
+
+ [WTF] Removing a smart pointer from HashTable issues two stores to the same location
+ https://bugs.webkit.org/show_bug.cgi?id=155676
+
+ Reviewed by Darin Adler.
+
+ * TestWebKitAPI/Tests/WTF/HashMap.cpp:
+ * TestWebKitAPI/Tests/WTF/HashSet.cpp:
+
2016-03-29 Srinivasan Vijayaraghavan <svijayaragha...@apple.com>
Add machine-readable results for JSC stress tests
Modified: trunk/Tools/TestWebKitAPI/Tests/WTF/HashMap.cpp (198826 => 198827)
--- trunk/Tools/TestWebKitAPI/Tests/WTF/HashMap.cpp 2016-03-30 04:16:48 UTC (rev 198826)
+++ trunk/Tools/TestWebKitAPI/Tests/WTF/HashMap.cpp 2016-03-30 05:13:04 UTC (rev 198827)
@@ -617,4 +617,88 @@
}
}
+
+TEST(WTF_HashMap, ValueIsDestructedOnRemove)
+{
+ struct DestructorObserver {
+ DestructorObserver() = default;
+
+ DestructorObserver(bool* destructed)
+ : destructed(destructed)
+ {
+ }
+
+ ~DestructorObserver()
+ {
+ if (destructed)
+ *destructed = true;
+ }
+
+ DestructorObserver(DestructorObserver&& other)
+ : destructed(other.destructed)
+ {
+ other.destructed = nullptr;
+ }
+
+ DestructorObserver& operator=(DestructorObserver&& other)
+ {
+ destructed = other.destructed;
+ other.destructed = nullptr;
+ return *this;
+ }
+
+ bool* destructed { nullptr };
+ };
+
+ HashMap<int, DestructorObserver> map;
+
+ bool destructed = false;
+ map.add(5, DestructorObserver { &destructed });
+
+ EXPECT_FALSE(destructed);
+
+ bool removeResult = map.remove(5);
+
+ EXPECT_TRUE(removeResult);
+ EXPECT_TRUE(destructed);
+}
+
+TEST(WTF_HashMap, RefPtrNotZeroedBeforeDeref)
+{
+ struct DerefObserver {
+ NEVER_INLINE void ref()
+ {
+ ++count;
+ }
+ NEVER_INLINE void deref()
+ {
+ --count;
+ observedBucket = bucketAddress->get();
+ }
+ unsigned count { 1 };
+ const RefPtr<DerefObserver>* bucketAddress { nullptr };
+ const DerefObserver* observedBucket { nullptr };
+ };
+
+ auto observer = std::make_unique<DerefObserver>();
+
+ HashMap<RefPtr<DerefObserver>, int> map;
+ map.add(adoptRef(observer.get()), 5);
+
+ auto iterator = map.find(observer.get());
+ EXPECT_TRUE(iterator != map.end());
+
+ observer->bucketAddress = &iterator->key;
+
+ EXPECT_TRUE(observer->observedBucket == nullptr);
+ EXPECT_TRUE(map.remove(observer.get()));
+
+ // It if fine to either leave the old value intact at deletion or already set it to the deleted
+ // value.
+ // A zero would be a incorrect outcome as it would mean we nulled the bucket before an opaque
+ // call.
+ EXPECT_TRUE(observer->observedBucket == observer.get() || observer->observedBucket == RefPtr<DerefObserver>::hashTableDeletedValue());
+ EXPECT_EQ(observer->count, 0u);
+}
+
} // namespace TestWebKitAPI
Modified: trunk/Tools/TestWebKitAPI/Tests/WTF/HashSet.cpp (198826 => 198827)
--- trunk/Tools/TestWebKitAPI/Tests/WTF/HashSet.cpp 2016-03-30 04:16:48 UTC (rev 198826)
+++ trunk/Tools/TestWebKitAPI/Tests/WTF/HashSet.cpp 2016-03-30 05:13:04 UTC (rev 198827)
@@ -28,6 +28,7 @@
#include "Counters.h"
#include "MoveOnly.h"
#include <wtf/HashSet.h>
+#include <wtf/RefPtr.h>
namespace TestWebKitAPI {
@@ -276,5 +277,76 @@
}
}
+TEST(WTF_HashSet, RefPtrNotZeroedBeforeDeref)
+{
+ struct DerefObserver {
+ NEVER_INLINE void ref()
+ {
+ ++count;
+ }
+ NEVER_INLINE void deref()
+ {
+ --count;
+ observedBucket = bucketAddress->get();
+ }
+ unsigned count { 1 };
+ const RefPtr<DerefObserver>* bucketAddress { nullptr };
+ const DerefObserver* observedBucket { nullptr };
+ };
+ auto observer = std::make_unique<DerefObserver>();
+
+ HashSet<RefPtr<DerefObserver>> set;
+ set.add(adoptRef(observer.get()));
+
+ auto iterator = set.find(observer.get());
+ EXPECT_TRUE(iterator != set.end());
+
+ observer->bucketAddress = iterator.get();
+
+ EXPECT_TRUE(observer->observedBucket == nullptr);
+ EXPECT_TRUE(set.remove(observer.get()));
+
+ // It if fine to either leave the old value intact at deletion or already set it to the deleted
+ // value.
+ // A zero would be a incorrect outcome as it would mean we nulled the bucket before an opaque
+ // call.
+ EXPECT_TRUE(observer->observedBucket == observer.get() || observer->observedBucket == RefPtr<DerefObserver>::hashTableDeletedValue());
+ EXPECT_EQ(observer->count, 0u);
+}
+
+
+TEST(WTF_HashSet, UniquePtrNotZeroedBeforeDestructor)
+{
+ struct DestructorObserver {
+ ~DestructorObserver()
+ {
+ observe();
+ }
+ std::function<void()> observe;
+ };
+
+ const std::unique_ptr<DestructorObserver>* bucketAddress = nullptr;
+ const DestructorObserver* observedBucket = nullptr;
+ std::unique_ptr<DestructorObserver> observer(new DestructorObserver { [&]() {
+ observedBucket = bucketAddress->get();
+ }});
+
+ const DestructorObserver* observerAddress = observer.get();
+
+ HashSet<std::unique_ptr<DestructorObserver>> set;
+ auto addResult = set.add(WTFMove(observer));
+
+ EXPECT_TRUE(addResult.isNewEntry);
+ EXPECT_TRUE(observedBucket == nullptr);
+
+ bucketAddress = addResult.iterator.get();
+
+ EXPECT_TRUE(observedBucket == nullptr);
+ EXPECT_TRUE(set.remove(*addResult.iterator));
+
+ EXPECT_TRUE(observedBucket == observerAddress || observedBucket == reinterpret_cast<const DestructorObserver*>(-1));
+}
+
+
} // namespace TestWebKitAPI
