Fix a race in Broadcaster/Listener interaction

[labath]

Summary

The following problem was occuring:

• broadcaster B had two listeners: L1 and L2 (thread T1)
• (T1) B has started to broadcast an event, it has locked a shared_ptr to L1 (in ListenerIterator())
• on another thread T2 the penultimate reference to L1 was destroyed (the transient object in B is now the last reference)
• (T2) the last reference to L2 was destroyed as well
• (T1) B has finished broadcasting the event to L1 and destroyed the last shared_ptr
• (T1) this triggered the destructor, which called into B->RemoveListener()
• (T1) all pointers in the m_listeners list were now stale, so RemoveListener emptied the list
• (T1) Eventually control returned to the ListenerIterator() for doing broadcasting, which was still in the middle of iterating through the list
• (T1) Only now, it was holding onto a dangling iterator. BOOM.

I fix this issue by making sure nothing can interfere with the
iterate-and-remove-expired-pointers loop, by moving this logic into a single function, which
first locks (or clears) the whole list and then returns the list of valid and locked Listeners
for further processing. Instead of std::list I use an llvm::SmallVector which should hopefully
offset the fact that we create a copy of the list for the common case where we have only a few
listeners (no heap allocations).

A slight difference in behaviour is that now RemoveListener does not remove an element from the
list -- it only sets it's mask to 0, which means it will be removed during the next iteration of
GetListeners(). This is purely an implementation detail and it should not be externally
noticable.

I was not able to reproduce this bug reliably without inserting sleep statements into the code,
so I do not add a test for it. Instead, I add some unit tests for the functions that I do modify.

[clayborg]

My only issue with this patch is that is uses llvm::SmallVector. Although the class is nice, we don't have visibility into this class when debugging like we do when we use STL collections. I would rather not move to SmallVector if we don't need to. Jim, thoughts?

[jingham]

The patch seems correct to me.

I don't have a strong opinion about std::vector vrs. SmallVector. These are temporary objects, so the size of the container doesn't matter, and I doubt this code is hot enough in normal lldb sessions that the difference in performance between the two will matter. Maybe the SmallVector data formatter (llvm/utils/lldbDataFormatters.py) works, or if it doesn't we should fix it?

[clayborg]

Ok. Jim says the patch is OK, so I will OK it also.

[labath]

Jim, just to double-check. Was that an "approve" then?

My feeling is that the lack of visibility into the SmallVector, means more that we should resurrect the formatter than that we should stop using it. Especially considering the whole "let's integrate closer with llvm" idea. (Although I agree than in this case in probably doesn't matter much.

[jingham]

Yes, sorry. I seem to have trouble with remembering the Action dropdown... Thanks for figuring this out - and apologies for any hair loss we inadvertently caused you!

I doubt it is important to use SmallVector rather than std::vector in this case, but not doing it because the thing is opaque does not seem the right deciding factor. There will clearly be cases where it is beneficial. Along with all the other testing improvements we need to do in our spare time, it might be good to write some tests for these formatters so they don't regress if they have.

gdb's build process writes a .gdbinit file into the build products that set up a convenient environment for debugging gdb with gdb. To use the gdb ones, you have to cd into the gdb directory, and debug from there. That works but is a little inelegant. I don't have a better idea right now, but it would be cool to come up with a way to do the same thing in lldb, so that if you're debugging lldb you get both useful formatters for lldb & llvm/clang.

Another in the continuing series of "What other people should do with their spare time..."

Jim

[labath]

In D23406#513927, @jingham wrote:

Yes, sorry. I seem to have trouble with remembering the Action dropdown... Thanks for figuring this out - and apologies for any hair loss we inadvertently caused you!

No worries.

I doubt it is important to use SmallVector rather than std::vector in this case, but not doing it because the thing is opaque does not seem the right deciding factor. There will clearly be cases where it is beneficial. Along with all the other testing improvements we need to do in our spare time, it might be good to write some tests for these formatters so they don't regress if they have.

gdb's build process writes a .gdbinit file into the build products that set up a convenient environment for debugging gdb with gdb. To use the gdb ones, you have to cd into the gdb directory, and debug from there. That works but is a little inelegant. I don't have a better idea right now, but it would be cool to come up with a way to do the same thing in lldb, so that if you're debugging lldb you get both useful formatters for lldb & llvm/clang.

Another in the continuing series of "What other people should do with their spare time..."

:)

The .lldbinit thing would work for me pretty well. When doing debugging from the console, I generally cd into the build directory already. If xcode has some "initial debugger commands" option we could use it to load that file and make that use case work as well. I'll see if I can get around to doing that.

lldb/trunk/include/lldb/Core/Broadcaster.h

 #include <string>
 #include <vector>
 
 // Other libraries and framework includes
 // Project includes
 #include "lldb/lldb-private.h"
 #include "lldb/Core/ConstString.h"
 
+#include "llvm/ADT/SmallVector.h"
+
 namespace lldb_private {
 
 //----------------------------------------------------------------------
 // lldb::BroadcastEventSpec
 //
 // This class is used to specify a kind of event to register for.  The Debugger
 // maintains a list of BroadcastEventSpec's and when it is made
 //----------------------------------------------------------------------
protected:
         PrivateBroadcastEvent (lldb::EventSP &event_sp, bool unique);
 
         const char *
         GetHijackingListenerName();
 
         //------------------------------------------------------------------
         //
         //------------------------------------------------------------------
-        typedef std::list< std::pair<lldb::ListenerWP,uint32_t> > collection;
+        typedef llvm::SmallVector<std::pair<lldb::ListenerWP, uint32_t>, 4> collection;
         typedef std::map<uint32_t, std::string> event_names_map;
 
-        void
-        ListenerIterator (std::function <bool (const lldb::ListenerSP &listener_sp, uint32_t &event_mask)> const &callback);
-
+        llvm::SmallVector<std::pair<lldb::ListenerSP, uint32_t&>, 4>
+        GetListeners();
 
         Broadcaster &m_broadcaster;                     ///< The broadcsater that this implements
         event_names_map m_event_names;                  ///< Optionally define event names for readability and logging for each event bit
         collection m_listeners;                         ///< A list of Listener / event_mask pairs that are listening to this broadcaster.
         std::recursive_mutex m_listeners_mutex;         ///< A mutex that protects \a m_listeners.
         std::vector<lldb::ListenerSP> m_hijacking_listeners;  // A simple mechanism to intercept events from a broadcaster
         std::vector<uint32_t> m_hijacking_masks;        // At some point we may want to have a stack or Listener
                                                         // collections, but for now this is just for private hijacking.

lldb/trunk/source/Core/Broadcaster.cpp

 Broadcaster::CheckInWithManager ()
 {
     if (m_manager_sp)
     {
         m_manager_sp->SignUpListenersForBroadcaster(*this);
     }
 }
 
-void
-Broadcaster::BroadcasterImpl::ListenerIterator (std::function <bool (const lldb::ListenerSP &listener_sp, uint32_t &event_mask)> const &callback)
+llvm::SmallVector<std::pair<ListenerSP, uint32_t &>, 4>
+Broadcaster::BroadcasterImpl::GetListeners()
 {
-    // Private iterator that should be used by everyone except BroadcasterImpl::RemoveListener().
-    // We have weak pointers to our listeners which means that at any point the listener can
-    // expire which means we will need to take it out of our list. To take care of this, we
-    // iterate and check that the weak pointer can be made into a valid shared pointer before
-    // we call the callback. If the weak pointer has expired, we remove it from our list.
-    collection::iterator pos = m_listeners.begin();
-    while (pos != m_listeners.end())
+    llvm::SmallVector<std::pair<ListenerSP, uint32_t &>, 4> listeners;
+    listeners.reserve(m_listeners.size());
+
+    for (auto it = m_listeners.begin(); it != m_listeners.end();)
     {
-        lldb::ListenerSP curr_listener_sp(pos->first.lock());
-        if (curr_listener_sp)
+        lldb::ListenerSP curr_listener_sp(it->first.lock());
+        if (curr_listener_sp && it->second)
         {
-            if (callback(curr_listener_sp, pos->second))
-                ++pos;  // Keep iterating
-            else
-                return; // Done iterating
+            listeners.emplace_back(std::move(curr_listener_sp), it->second);
+            ++it;
         }
         else
-        {
-            // The listener has been expired. Remove this entry.
-            pos = m_listeners.erase(pos);
-        }
+            it = m_listeners.erase(it);
     }
+
+    return listeners;
 }
 
 void
 Broadcaster::BroadcasterImpl::Clear()
 {
     std::lock_guard<std::recursive_mutex> guard(m_listeners_mutex);
 
     // Make sure the listener forgets about this broadcaster. We do
     // this in the broadcaster in case the broadcaster object initiates
     // the removal.
-
-    ListenerIterator([this](const lldb::ListenerSP &curr_listener_sp, uint32_t &curr_event_mask) -> bool {
-        curr_listener_sp->BroadcasterWillDestruct (&m_broadcaster);
-        return true; // Keep iterating
-    });
+    for(auto &pair : GetListeners())
+        pair.first->BroadcasterWillDestruct (&m_broadcaster);
     
     m_listeners.clear();
 }
 
 Broadcaster *
 Broadcaster::BroadcasterImpl::GetBroadcaster()
 {
     return &m_broadcaster;
if (!listener_sp)
         return 0;
 
     std::lock_guard<std::recursive_mutex> guard(m_listeners_mutex);
 
     // See if we already have this listener, and if so, update its mask
 
     bool handled = false;
 
-    ListenerIterator([this, &listener_sp, &handled, event_mask](const lldb::ListenerSP &curr_listener_sp, uint32_t &curr_event_mask) -> bool {
-        if (curr_listener_sp == listener_sp)
+    for(auto &pair: GetListeners())
+    {
+        if (pair.first == listener_sp)
         {
             handled = true;
-            curr_event_mask |= event_mask;
+            pair.second |= event_mask;
             m_broadcaster.AddInitialEventsToListener (listener_sp, event_mask);
-            return false; // Stop iterating
-        }
-        return true; // Keep iterating
-    });
+            break;
+        }
 
     if (!handled)
     {
         // Grant a new listener the available event bits
         m_listeners.push_back(std::make_pair(lldb::ListenerWP(listener_sp), event_mask));
 
         // Individual broadcasters decide whether they have outstanding data when a
         // listener attaches, and insert it into the listener with this method.
         m_broadcaster.AddInitialEventsToListener (listener_sp, event_mask);
     }
 
     // Return the event bits that were granted to the listener
     return event_mask;
 }
 
 bool
 Broadcaster::BroadcasterImpl::EventTypeHasListeners (uint32_t event_type)
 {
     std::lock_guard<std::recursive_mutex> guard(m_listeners_mutex);
 
     if (!m_hijacking_listeners.empty() && event_type & m_hijacking_masks.back())
         return true;
         
-    if (m_listeners.empty())
-        return false;
-
-    bool result = false;
-    ListenerIterator([this, event_type, &result](const lldb::ListenerSP &curr_listener_sp, uint32_t &curr_event_mask) -> bool {
-
-        if (curr_event_mask & event_type)
-        {
-            result = true;
-            return false; // Stop iterating
-        }
-        else
-        {
-            return true; // Keep iterating
-        }
-    });
-    return result;
+    for(auto &pair: GetListeners())
+        if (pair.second & event_type)
+            return true;
+    return false;
 }
 
 bool
 Broadcaster::BroadcasterImpl::RemoveListener (lldb_private::Listener *listener, uint32_t event_mask)
 {
-    if (listener)
-    {
-        std::lock_guard<std::recursive_mutex> guard(m_listeners_mutex);
-        collection::iterator pos = m_listeners.begin();
-        // See if we already have this listener, and if so, update its mask
-        while (pos != m_listeners.end())
-        {
-            lldb::ListenerSP curr_listener_sp(pos->first.lock());
-            if (curr_listener_sp)
-            {
-                if (curr_listener_sp.get() == listener)
-                {
-                    // Relinquish all event bits in "event_mask"
-                    pos->second &= ~event_mask;
-                    // If all bits have been relinquished then remove this listener
-                    if (pos->second == 0)
-                        m_listeners.erase (pos);
-                    return true;
-                }
-                ++pos;
-            }
-            else
-            {
-                // The listener has been destroyed since we couldn't turn the std::weak_ptr
-                // into a valid shared pointer, so we can remove it.
-                pos = m_listeners.erase (pos);
-            }
-        }
+    if (!listener)
+        return false;
+
+    for (auto &pair : GetListeners())
+        if (pair.first.get() == listener)
+            pair.second &= ~event_mask;
     }
     return false;
 }
 
 bool
 Broadcaster::BroadcasterImpl::RemoveListener (const lldb::ListenerSP &listener_sp, uint32_t event_mask)
 {
     return RemoveListener (listener_sp.get(), event_mask);
Broadcaster::BroadcasterImpl::PrivateBroadcastEvent (EventSP &event_sp, bool unique)
     if (hijacking_listener_sp)
     {
         if (unique && hijacking_listener_sp->PeekAtNextEventForBroadcasterWithType (&m_broadcaster, event_type))
             return;
         hijacking_listener_sp->AddEvent (event_sp);
     }
     else
     {
-
-        ListenerIterator([this, unique, event_type, &event_sp](const lldb::ListenerSP &curr_listener_sp, uint32_t &curr_event_mask) -> bool {
-
-            if (event_type & curr_event_mask)
-            {
-                if (!unique || curr_listener_sp->PeekAtNextEventForBroadcasterWithType (&m_broadcaster, event_type) == nullptr)
-                    curr_listener_sp->AddEvent (event_sp);
-            }
-            return true; // Keep iterating
-        });
+        for (auto &pair : GetListeners())
+            if (!(pair.second & event_type))
+                continue;
+            if (unique && pair.first->PeekAtNextEventForBroadcasterWithType (&m_broadcaster, event_type))
+                continue;
+
+            pair.first->AddEvent (event_sp);
     }
 }
 
 void
 Broadcaster::BroadcasterImpl::BroadcastEvent (uint32_t event_type, EventData *event_data)
 {
     EventSP event_sp (new Event (event_type, event_data));
     PrivateBroadcastEvent (event_sp, false);

lldb/trunk/unittests/Core/BroadcasterTest.cpp

+//===-- BroadcasterTest.cpp -------------------------------------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#include "gtest/gtest.h"
+
+#include "lldb/Core/Broadcaster.h"
+#include "lldb/Core/Listener.h"
+#include "lldb/Host/Predicate.h"
+
+#include <thread>
+
+using namespace lldb;
+using namespace lldb_private;
+
+TEST(BroadcasterTest, BroadcastEvent)
+{
+    EventSP event_sp;
+    Broadcaster broadcaster(nullptr, "test-broadcaster");
+
+    // Create a listener, sign it up, make sure it recieves an event.
+    ListenerSP listener1_sp = Listener::MakeListener("test-listener1");
+    const uint32_t event_mask1 = 1;
+    EXPECT_EQ(event_mask1, listener1_sp->StartListeningForEvents(&broadcaster, event_mask1));
+    broadcaster.BroadcastEvent(event_mask1, nullptr);
+    EXPECT_TRUE(listener1_sp->GetNextEvent(event_sp));
+    EXPECT_EQ(event_mask1, event_sp->GetType());
+
+    {
+        // Add one more listener, make sure it works as well.
+        ListenerSP listener2_sp = Listener::MakeListener("test-listener2");
+        const uint32_t event_mask2 = 1;
+        EXPECT_EQ(event_mask2, listener2_sp->StartListeningForEvents(&broadcaster, event_mask1 | event_mask2));
+        broadcaster.BroadcastEvent(event_mask2, nullptr);
+        EXPECT_TRUE(listener2_sp->GetNextEvent(event_sp));
+        EXPECT_EQ(event_mask2, event_sp->GetType());
+
+        // Both listeners should get this event.
+        broadcaster.BroadcastEvent(event_mask1, nullptr);
+        EXPECT_TRUE(listener1_sp->GetNextEvent(event_sp));
+        EXPECT_EQ(event_mask1, event_sp->GetType());
+        EXPECT_TRUE(listener2_sp->GetNextEvent(event_sp));
+        EXPECT_EQ(event_mask2, event_sp->GetType());
+    }
+
+    // Now again only one listener should be active.
+    broadcaster.BroadcastEvent(event_mask1, nullptr);
+    EXPECT_TRUE(listener1_sp->GetNextEvent(event_sp));
+    EXPECT_EQ(event_mask1, event_sp->GetType());
+}
+
+TEST(BroadcasterTest, EventTypeHasListeners)
+{
+    EventSP event_sp;
+    Broadcaster broadcaster(nullptr, "test-broadcaster");
+
+    const uint32_t event_mask = 1;
+    EXPECT_FALSE(broadcaster.EventTypeHasListeners(event_mask));
+
+    {
+        ListenerSP listener_sp = Listener::MakeListener("test-listener");
+        EXPECT_EQ(event_mask, listener_sp->StartListeningForEvents(&broadcaster, event_mask));
+        EXPECT_TRUE(broadcaster.EventTypeHasListeners(event_mask));
+    }
+
+    EXPECT_FALSE(broadcaster.EventTypeHasListeners(event_mask));
+}

lldb/trunk/unittests/Core/CMakeLists.txt

 add_lldb_unittest(LLDBCoreTests
+  BroadcasterTest.cpp
   DataExtractorTest.cpp
   ScalarTest.cpp
   )