Silence leaks in ParkingLot
authorfpizlo@apple.com <fpizlo@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Thu, 17 Mar 2016 18:54:15 +0000 (18:54 +0000)
committerfpizlo@apple.com <fpizlo@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Thu, 17 Mar 2016 18:54:15 +0000 (18:54 +0000)
https://bugs.webkit.org/show_bug.cgi?id=155510

Reviewed by Alexey Proskuryakov.

ParkingLot has a concurrent hashtable that it reallocates on demand. It will not reallocate
it in steady state. The hashtable is sized to accommodate the high watermark of the number
of active threads - so long as the program doesn't just keep starting an unbounded number
of threads that are all active, the hashtable will stop resizing. Each resize operation is
designed to stay out of the way of the data-access-parallel normal path, in which two
threads operating on different lock addresses don't have to synchronize. To do this, it
simply drops the old hashtable without deleting it, so that threads that were still using
it don't crash. They will realize that they have the wrong hashtable before doing anything
bad, but we don't have a way of proving when all of those threads are no longer going to
read from the old hashtables. So, we just leak them.

This is a bounded leak, since the hashtable resizes exponentially. Thus the total memory
utilization of all hashtables, including the leaked ones, converges to a linear function of
the current hashtable's size (it's 2 * size of current hashtable).

But this leak is a problem for leaks tools, which will always report this leak. This is not
useful. It's better to silence the leak. That's what this patch does by ensuring that all
hashtables, including leaked ones, end up in a global vector. This is perf-neutral.

This requires making a StaticWordLock variant of WordLock. That's probably the biggest part
of this change.

* wtf/ParkingLot.cpp:
* wtf/WordLock.cpp:
(WTF::WordLockBase::lockSlow):
(WTF::WordLockBase::unlockSlow):
(WTF::WordLock::lockSlow): Deleted.
(WTF::WordLock::unlockSlow): Deleted.
* wtf/WordLock.h:
(WTF::WordLockBase::lock):
(WTF::WordLockBase::isLocked):
(WTF::WordLock::WordLock):
(WTF::WordLock::lock): Deleted.
(WTF::WordLock::isLocked): Deleted.

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

Source/WTF/ChangeLog
Source/WTF/wtf/ParkingLot.cpp
Source/WTF/wtf/WordLock.cpp
Source/WTF/wtf/WordLock.h

index 0d4c776..01815a0 100644 (file)
@@ -1,3 +1,45 @@
+2016-03-17  Filip Pizlo  <fpizlo@apple.com>
+
+        Silence leaks in ParkingLot
+        https://bugs.webkit.org/show_bug.cgi?id=155510
+
+        Reviewed by Alexey Proskuryakov.
+
+        ParkingLot has a concurrent hashtable that it reallocates on demand. It will not reallocate
+        it in steady state. The hashtable is sized to accommodate the high watermark of the number
+        of active threads - so long as the program doesn't just keep starting an unbounded number
+        of threads that are all active, the hashtable will stop resizing. Each resize operation is
+        designed to stay out of the way of the data-access-parallel normal path, in which two
+        threads operating on different lock addresses don't have to synchronize. To do this, it
+        simply drops the old hashtable without deleting it, so that threads that were still using
+        it don't crash. They will realize that they have the wrong hashtable before doing anything
+        bad, but we don't have a way of proving when all of those threads are no longer going to
+        read from the old hashtables. So, we just leak them.
+
+        This is a bounded leak, since the hashtable resizes exponentially. Thus the total memory
+        utilization of all hashtables, including the leaked ones, converges to a linear function of
+        the current hashtable's size (it's 2 * size of current hashtable).
+
+        But this leak is a problem for leaks tools, which will always report this leak. This is not
+        useful. It's better to silence the leak. That's what this patch does by ensuring that all
+        hashtables, including leaked ones, end up in a global vector. This is perf-neutral.
+
+        This requires making a StaticWordLock variant of WordLock. That's probably the biggest part
+        of this change.
+
+        * wtf/ParkingLot.cpp:
+        * wtf/WordLock.cpp:
+        (WTF::WordLockBase::lockSlow):
+        (WTF::WordLockBase::unlockSlow):
+        (WTF::WordLock::lockSlow): Deleted.
+        (WTF::WordLock::unlockSlow): Deleted.
+        * wtf/WordLock.h:
+        (WTF::WordLockBase::lock):
+        (WTF::WordLockBase::isLocked):
+        (WTF::WordLock::WordLock):
+        (WTF::WordLock::lock): Deleted.
+        (WTF::WordLock::isLocked): Deleted.
+
 2016-03-16  Chris Dumez  <cdumez@apple.com>
 
         Unreviewed, rolling out r198235, r198240, r198241, and
index f16d5d2..62db4be 100644 (file)
@@ -1,5 +1,5 @@
 /*
- * Copyright (C) 2015 Apple Inc. All rights reserved.
+ * Copyright (C) 2015-2016 Apple Inc. All rights reserved.
  *
  * Redistribution and use in source and binary forms, with or without
  * modification, are permitted provided that the following conditions
@@ -177,6 +177,12 @@ public:
     char padding[64];
 };
 
+struct Hashtable;
+
+// We track all allocated hashtables so that hashtable resizing doesn't anger leak detectors.
+Vector<Hashtable*>* hashtables;
+StaticWordLock hashtablesLock;
+
 struct Hashtable {
     unsigned size;
     Atomic<Bucket*> data[1];
@@ -188,11 +194,28 @@ struct Hashtable {
         Hashtable* result = static_cast<Hashtable*>(
             fastZeroedMalloc(sizeof(Hashtable) + sizeof(Atomic<Bucket*>) * (size - 1)));
         result->size = size;
+
+        {
+            // This is not fast and it's not data-access parallel, but that's fine, because
+            // hashtable resizing is guaranteed to be rare and it will never happen in steady
+            // state.
+            WordLockHolder locker(hashtablesLock);
+            if (!hashtables)
+                hashtables = new Vector<Hashtable*>();
+            hashtables->append(result);
+        }
+        
         return result;
     }
 
     static void destroy(Hashtable* hashtable)
     {
+        {
+            // This is not fast, but that's OK. See comment in create().
+            WordLockHolder locker(hashtablesLock);
+            hashtables->removeFirst(hashtable);
+        }
+        
         fastFree(hashtable);
     }
 };
index 65981bb..215e2ea 100644 (file)
@@ -1,5 +1,5 @@
 /*
- * Copyright (C) 2015 Apple Inc. All rights reserved.
+ * Copyright (C) 2015-2016 Apple Inc. All rights reserved.
  *
  * Redistribution and use in source and binary forms, with or without
  * modification, are permitted provided that the following conditions
@@ -77,7 +77,7 @@ ThreadData* myThreadData()
 
 } // anonymous namespace
 
-NEVER_INLINE void WordLock::lockSlow()
+NEVER_INLINE void WordLockBase::lockSlow()
 {
     unsigned spinCount = 0;
 
@@ -178,7 +178,7 @@ NEVER_INLINE void WordLock::lockSlow()
     }
 }
 
-NEVER_INLINE void WordLock::unlockSlow()
+NEVER_INLINE void WordLockBase::unlockSlow()
 {
     // The fast path can fail either because of spurious weak CAS failure, or because someone put a
     // thread on the queue, or the queue lock is held. If the queue lock is held, it can only be
index c7e208b..59fe38f 100644 (file)
@@ -1,5 +1,5 @@
 /*
- * Copyright (C) 2015 Apple Inc. All rights reserved.
+ * Copyright (C) 2015-2016 Apple Inc. All rights reserved.
  *
  * Redistribution and use in source and binary forms, with or without
  * modification, are permitted provided that the following conditions
@@ -42,14 +42,7 @@ namespace WTF {
 // Lock instead. WordLock sits lower in the stack and is used to implement Lock, so Lock is the main
 // client of WordLock.
 
-class WordLock {
-    WTF_MAKE_NONCOPYABLE(WordLock);
-public:
-    WordLock()
-    {
-        m_word.store(0, std::memory_order_relaxed);
-    }
-
+struct WordLockBase {
     void lock()
     {
         if (LIKELY(m_word.compareExchangeWeak(0, isLockedBit, std::memory_order_acquire))) {
@@ -80,7 +73,7 @@ public:
         return isHeld();
     }
 
-private:
+protected:
     friend struct TestWebKitAPI::LockInspector;
     
     static const uintptr_t isLockedBit = 1;
@@ -99,12 +92,23 @@ private:
     Atomic<uintptr_t> m_word;
 };
 
-typedef Locker<WordLock> WordLockHolder;
+class WordLock : public WordLockBase {
+    WTF_MAKE_NONCOPYABLE(WordLock);
+public:
+    WordLock()
+    {
+        m_word.store(0, std::memory_order_relaxed);
+    }
+};
+
+typedef WordLockBase StaticWordLock;
+typedef Locker<WordLockBase> WordLockHolder;
 
 } // namespace WTF
 
 using WTF::WordLock;
 using WTF::WordLockHolder;
+using WTF::StaticWordLock;
 
 #endif // WTF_WordLock_h