[PATCH 07/11] gdb: maintain per-process-target list of resumed threads with pending wait status

[Simon Marchi via Gdb-patches <gdb-patches@sourceware.org>]

Looking up threads that are both resumed and have a pending wait
status to report is something that we do quite often in the fast path
and is expensive if there are many threads, since it currently requires
walking whole thread lists.

The first instance is in maybe_set_commit_resumed_all_targets.  This is
called after handling each event in fetch_inferior_event, to see if we
should ask targets to commit their resumed threads or not.  If at least
one thread is resumed but has a pending wait status, we don't ask the
targets to commit their resumed threads, because we want to consume and
handle the pending wait status first.

The second instance is in random_pending_event_thread, where we want to
select a random thread among all those that are resumed and have a
pending wait status.  This is called every time we try to consume
events, to see if there are any pending events that we we want to
consume, before asking the targets for more events.

To allow optimizing these cases, maintain a per-process-target list of
threads that are resumed and have a pending wait status.

In maybe_set_commit_resumed_all_targets, we'll be able to check in O(1)
if there are any such threads simply by checking whether the list is
empty.

In random_pending_event_thread, we'll be able to use that list, which
will be quicker than iterating the list of threads, especially when
there are no resumed with pending wait status threads.

About implementation details: using the new setters on class
thread_info, it's relatively easy to maintain that list.  Any time the
"resumed" or "pending wait status" property is changed, we check whether
that should cause the thread to be added or removed from the list.

In set_thread_exited, we try to remove the thread from the list, because
keeping an exited thread in that list would make no sense (especially if
the thread is freed).  My first implementation assumed that a process
stratum target was always present when set_thread_exited is called.
That's however, not the case: in some cases, targets unpush themselves
from an inferior and then call "exit_inferior", which exits all the
threads.  If the target is unpushed before set_thread_exited is called
on the threads, it means we could mistakenly leave some threads in the
list.  I tried to see how hard it would be to make it such that targets
have to exit all threads before unpushing themselves from the inferior
(that would seem logical to me, we don't want threads belonging to an
inferior that has no process target).  That seem quite difficult and not
worth the time.  Instead, I changed inferior::unpush_target to remove an
threads of that inferior from the list.

As of this patch, the list is not used, this is done in the subsequent
patches.

gdb/ChangeLog:

	* process-stratum-target.h (class process_stratum_target)
	<maybe_add_resumed_with_pending_wait_status,
	maybe_remove_resumed_with_pending_wait_status>: New.
	<m_resumed_with_pending_wait_status>: New.
	* process-stratum-target.c
	(process_stratum_target::maybe_add_resumed_with_pending_wait_status,
	process_stratum_target::maybe_remove_resumed_with_pending_wait_status):
	New.
	* gdbthread.h (class thread_info) <set_resumed>: Remove
	definition.
	<resumed_with_pending_wait_status_node>: New.
	(thread_info_resumed_with_pending_wait_status_node,
	thread_info_resumed_with_pending_wait_status_list): New.
	(set_thread_exited): Call
	maybe_remove_resumed_with_pending_wait_status.
	(thread_info::set_resumed): New definition.
	(thread_info::set_pending_waitstatus): Call
	maybe_add_resumed_with_pending_wait_status.
	(thread_info::clear_pending_waitstatus): Call
	maybe_remove_resumed_with_pending_wait_status.
	* inferior.h (class inferior) <unpush_target>: Remove
	definition.
	* inferior.c (inferior::unpush_target): New definition.

Change-Id: Iad8f93db2d13984dd5aa5867db940ed1169dbb67
---
 gdb/gdbthread.h              | 14 ++++++++++++--
 gdb/inferior.c               | 19 +++++++++++++++++++
 gdb/inferior.h               |  3 +--
 gdb/process-stratum-target.c | 34 ++++++++++++++++++++++++++++++++++
 gdb/process-stratum-target.h | 16 ++++++++++++++++
 gdb/thread.c                 | 33 +++++++++++++++++++++++++++++++++
 6 files changed, 115 insertions(+), 4 deletions(-)

diff --git a/gdb/gdbthread.h b/gdb/gdbthread.h
index 5ea08a13ee5f..47d7f40eaa08 100644
--- a/gdb/gdbthread.h
+++ b/gdb/gdbthread.h
@@ -296,8 +296,7 @@ class thread_info : public refcounted_object,
   bool resumed () const
   { return m_resumed; }
 
-  void set_resumed (bool resumed)
-  { m_resumed = resumed; }
+  void set_resumed (bool resumed);
 
   /* Frontend view of the thread state.  Note that the THREAD_RUNNING/
      THREAD_STOPPED states are different from EXECUTING.  When the
@@ -470,6 +469,10 @@ class thread_info : public refcounted_object,
      linked.  */
   intrusive_list_node<thread_info> step_over_list_node;
 
+  /* Node for list of threads that are resumed and have a pending wait
+     status.  */
+  intrusive_list_node<thread_info> resumed_with_pending_wait_status_node;
+
   /* Displaced-step state for this thread.  */
   displaced_step_thread_state displaced_step_state;
 
@@ -488,6 +491,13 @@ class thread_info : public refcounted_object,
   thread_suspend_state m_suspend;
 };
 
+using thread_info_resumed_with_pending_wait_status_node
+  = intrusive_member_node<thread_info,
+			  &thread_info::resumed_with_pending_wait_status_node>;
+using thread_info_resumed_with_pending_wait_status_list
+  = intrusive_list<thread_info,
+		   thread_info_resumed_with_pending_wait_status_node>;
+
 /* A gdb::ref_ptr pointer to a thread_info.  */
 
 using thread_info_ref
diff --git a/gdb/inferior.c b/gdb/inferior.c
index f1b0bdde554b..e07a8f88422a 100644
--- a/gdb/inferior.c
+++ b/gdb/inferior.c
@@ -89,6 +89,25 @@ inferior::inferior (int pid_)
   m_target_stack.push (get_dummy_target ());
 }
 
+/* See inferior.h.  */
+
+int
+inferior::unpush_target (struct target_ops *t)
+{
+  /* If unpushing the process stratum target while threads exists, ensure that
+     we don't leave any threads of this inferior in the target's "resumed with
+     pending wait status" list.  */
+  if (t->stratum () == process_stratum)
+    {
+      process_stratum_target *proc_target = as_process_stratum_target (t);
+
+      for (thread_info *thread : this->non_exited_threads ())
+	proc_target->maybe_remove_resumed_with_pending_wait_status (thread);
+    }
+
+  return m_target_stack.unpush (t);
+}
+
 void
 inferior::set_tty (const char *terminal_name)
 {
diff --git a/gdb/inferior.h b/gdb/inferior.h
index 830dec3ebbaa..2bfe29afed3f 100644
--- a/gdb/inferior.h
+++ b/gdb/inferior.h
@@ -362,8 +362,7 @@ class inferior : public refcounted_object,
   }
 
   /* Unpush T from this inferior's target stack.  */
-  int unpush_target (struct target_ops *t)
-  { return m_target_stack.unpush (t); }
+  int unpush_target (struct target_ops *t);
 
   /* Returns true if T is pushed in this inferior's target stack.  */
   bool target_is_pushed (target_ops *t)
diff --git a/gdb/process-stratum-target.c b/gdb/process-stratum-target.c
index c851090a7f2e..44e138273b2f 100644
--- a/gdb/process-stratum-target.c
+++ b/gdb/process-stratum-target.c
@@ -106,6 +106,40 @@ process_stratum_target::follow_exec (inferior *follow_inf, ptid_t ptid,
 
 /* See process-stratum-target.h.  */
 
+void
+process_stratum_target::maybe_add_resumed_with_pending_wait_status
+  (thread_info *thread)
+{
+  gdb_assert (!thread->resumed_with_pending_wait_status_node.is_linked ());
+
+  if (thread->resumed () && thread->has_pending_waitstatus ())
+    {
+      infrun_debug_printf ("adding to resumed threads with event list: %s",
+			   target_pid_to_str (thread->ptid).c_str ());
+      m_resumed_with_pending_wait_status.push_back (*thread);
+    }
+}
+
+/* See process-stratum-target.h.  */
+
+void
+process_stratum_target::maybe_remove_resumed_with_pending_wait_status
+  (thread_info *thread)
+{
+  if (thread->resumed () && thread->has_pending_waitstatus ())
+    {
+      infrun_debug_printf ("removing from resumed threads with event list: %s",
+			   target_pid_to_str (thread->ptid).c_str ());
+      gdb_assert (thread->resumed_with_pending_wait_status_node.is_linked ());
+      auto it = m_resumed_with_pending_wait_status.iterator_to (*thread);
+      m_resumed_with_pending_wait_status.erase (it);
+    }
+  else
+    gdb_assert (!thread->resumed_with_pending_wait_status_node.is_linked ());
+}
+
+/* See process-stratum-target.h.  */
+
 std::set<process_stratum_target *>
 all_non_exited_process_targets ()
 {
diff --git a/gdb/process-stratum-target.h b/gdb/process-stratum-target.h
index 31a97753db9c..d79efbee8f2c 100644
--- a/gdb/process-stratum-target.h
+++ b/gdb/process-stratum-target.h
@@ -22,6 +22,8 @@
 
 #include "target.h"
 #include <set>
+#include "gdbsupport/intrusive_list.h"
+#include "gdbthread.h"
 
 /* Abstract base class inherited by all process_stratum targets.  */
 
@@ -78,6 +80,14 @@ class process_stratum_target : public target_ops
      may have spawned new threads we haven't heard of yet.  */
   bool threads_executing = false;
 
+  /* If THREAD is resumed and has a pending wait status, add it to the
+     target's "resumed with pending wait status" list.  */
+  void maybe_add_resumed_with_pending_wait_status (thread_info *thread);
+
+  /* If THREAD is resumed and has a pending wait status, remove it from the
+     target's "resumed with pending wait status" list.  */
+  void maybe_remove_resumed_with_pending_wait_status (thread_info *thread);
+
   /* The connection number.  Visible in "info connections".  */
   int connection_number = 0;
 
@@ -112,6 +122,12 @@ class process_stratum_target : public target_ops
      coalesce multiple resumption requests in a single vCont
      packet.  */
   bool commit_resumed_state = false;
+
+private:
+  /* List of threads managed by this target which simultaneously are resumed
+     and have a pending wait status.  */
+  thread_info_resumed_with_pending_wait_status_list
+    m_resumed_with_pending_wait_status;
 };
 
 /* Downcast TARGET to process_stratum_target.  */
diff --git a/gdb/thread.c b/gdb/thread.c
index 289d33c74c3b..26974e1b8cbc 100644
--- a/gdb/thread.c
+++ b/gdb/thread.c
@@ -188,6 +188,10 @@ set_thread_exited (thread_info *tp, bool silent)
 
   if (tp->state != THREAD_EXITED)
     {
+      process_stratum_target *proc_target = tp->inf->process_target ();
+      if (proc_target != nullptr)
+	proc_target->maybe_remove_resumed_with_pending_wait_status (tp);
+
       gdb::observers::thread_exit.notify (tp, silent);
 
       /* Tag it as exited.  */
@@ -295,6 +299,29 @@ thread_info::deletable () const
 
 /* See gdbthread.h.  */
 
+void
+thread_info::set_resumed (bool resumed)
+{
+  if (resumed == m_resumed)
+    return;
+
+  process_stratum_target *proc_target = this->inf->process_target ();
+
+  /* If we transition from resumed to not resumed, we might need to remove
+     the thread from the resumed threads with pending statuses list.  */
+  if (!resumed)
+    proc_target->maybe_remove_resumed_with_pending_wait_status (this);
+
+  m_resumed = resumed;
+
+  /* If we transition from not resumed to resumed, we might need to add
+     the thread to the resumed threads with pending statuses list.  */
+  if (resumed)
+    proc_target->maybe_add_resumed_with_pending_wait_status (this);
+}
+
+/* See gdbthread.h.  */
+
 void
 thread_info::set_pending_waitstatus (const target_waitstatus &ws)
 {
@@ -302,6 +329,9 @@ thread_info::set_pending_waitstatus (const target_waitstatus &ws)
 
   m_suspend.waitstatus = ws;
   m_suspend.waitstatus_pending_p = 1;
+
+  process_stratum_target *proc_target = this->inf->process_target ();
+  proc_target->maybe_add_resumed_with_pending_wait_status (this);
 }
 
 /* See gdbthread.h.  */
@@ -311,6 +341,9 @@ thread_info::clear_pending_waitstatus ()
 {
   gdb_assert (this->has_pending_waitstatus ());
 
+  process_stratum_target *proc_target = this->inf->process_target ();
+  proc_target->maybe_remove_resumed_with_pending_wait_status (this);
+
   m_suspend.waitstatus_pending_p = 0;
 }
 
-- 
2.32.0