[PATCH 04/11] gdb: use intrusive list for step-over chain

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

The threads that need a step-over are currently linked using an
hand-written intrusive doubly-linked list, so that seems a very good
candidate for intrusive_list, convert it.

For this, we have a use case of appending a list to another one (in
start_step_over).  Based on the std::list and Boost APIs, add a splice
method.  However, only support splicing the other list at the end of the
`this` list, since that's all we need.

gdb/ChangeLog:

	* gdbthread.h (class thread_info) <step_over_next,
	step_over_prev>: Remove.
	<step_over_list_node>: New.
	(thread_step_over_list_node, thread_step_over_list): New.
	(global_thread_step_over_chain_enqueue): Change parameter type.
	(thread_step_over_chain_remove): Remove.
	(thread_step_over_chain_next): Remove.
	(global_thread_step_over_chain_next): Remove.
	(thread_step_over_chain_length): Change parameter type.
	* thread.c (set_thread_exited): Adjust.
	(step_over_chain_enqueue): Remove.
	(thread_step_over_chain_remove): Remove.
	(thread_step_over_chain_next): Remove.
	(global_thread_step_over_chain_next): Remove.
	(thread_is_in_step_over_chain): Change parameter type.
	(thread_step_over_chain_length): Change parameter type.
	(global_thread_step_over_chain_enqueue_chain):
	(global_thread_step_over_chain_remove): Adjust.
	(set_running_thread): Adjust.
	* infrun.h (global_thread_step_over_chain_head): Rename to...
	(global_thread_step_over_list): ... this, change type.
	* infrun.c (global_thread_step_over_chain_head): Rename to...
	(global_thread_step_over_list): ... this, change type.
	(start_step_over): Adjust.
	(prepare_for_detach): Adjust.
	* unittests/intrusive_list-selftests.c (struct intrusive_list_test)
	<test_splice>: New.
	(test_intrusive_list): Call test_splice.

gdbsupport/ChangeLog:

	* intrusive_list.h (class intrusive_list) <splice>: New.
	* reference-to-pointer-iterator.h (struct
	reference_to_pointer_iterator): Add default assignment
	operators.

Change-Id: I31b2ff67c7b78251314646b31887ef1dfebe510c
---
 gdb/gdbthread.h                            |  52 +++++-----
 gdb/infrun.c                               |  39 ++++----
 gdb/infrun.h                               |   4 +-
 gdb/thread.c                               | 106 +++------------------
 gdb/unittests/intrusive_list-selftests.c   |  84 ++++++++++++++++
 gdbsupport/intrusive_list.h                |  27 ++++++
 gdbsupport/reference-to-pointer-iterator.h |   3 +
 7 files changed, 177 insertions(+), 138 deletions(-)

diff --git a/gdb/gdbthread.h b/gdb/gdbthread.h
index 0e28b1de9ff0..54c097206d16 100644
--- a/gdb/gdbthread.h
+++ b/gdb/gdbthread.h
@@ -387,11 +387,9 @@ class thread_info : public refcounted_object,
      expressions.  */
   std::vector<struct value *> stack_temporaries;
 
-  /* Step-over chain.  A thread is in the step-over queue if these are
-     non-NULL.  If only a single thread is in the chain, then these
-     fields point to self.  */
-  struct thread_info *step_over_prev = NULL;
-  struct thread_info *step_over_next = NULL;
+  /* Step-over chain.  A thread is in the step-over queue if this node is
+     linked.  */
+  intrusive_list_node<thread_info> step_over_list_node;
 
   /* Displaced-step state for this thread.  */
   displaced_step_thread_state displaced_step_state;
@@ -746,36 +744,42 @@ extern value *get_last_thread_stack_temporary (struct thread_info *tp);
 extern bool value_in_thread_stack_temporaries (struct value *,
 					       struct thread_info *thr);
 
+/* Thread step-over list type.  */
+using thread_step_over_list_node
+  = intrusive_member_node<thread_info, &thread_info::step_over_list_node>;
+using thread_step_over_list
+  = intrusive_list<thread_info, thread_step_over_list_node>;
+using thread_step_over_list_iterator
+  = reference_to_pointer_iterator<thread_step_over_list::iterator>;
+using thread_step_over_list_safe_iterator
+  = basic_safe_iterator<thread_step_over_list_iterator>;
+using thread_step_over_list_safe_range
+  = iterator_range<thread_step_over_list_safe_iterator>;
+
+static inline thread_step_over_list_safe_range
+make_thread_step_over_list_safe_range (thread_step_over_list &list)
+{
+  return thread_step_over_list_safe_range
+    (thread_step_over_list_safe_iterator (list.begin (),
+					  list.end ()),
+     thread_step_over_list_safe_iterator (list.end (),
+					  list.end ()));
+}
+
 /* Add TP to the end of the global pending step-over chain.  */
 
 extern void global_thread_step_over_chain_enqueue (thread_info *tp);
 
-/* Append the thread step over chain CHAIN_HEAD to the global thread step over
+/* Append the thread step over list LIST to the global thread step over
    chain. */
 
 extern void global_thread_step_over_chain_enqueue_chain
-  (thread_info *chain_head);
-
-/* Remove TP from step-over chain LIST_P.  */
-
-extern void thread_step_over_chain_remove (thread_info **list_p,
-					   thread_info *tp);
+  (thread_step_over_list &&list);
 
 /* Remove TP from the global pending step-over chain.  */
 
 extern void global_thread_step_over_chain_remove (thread_info *tp);
 
-/* Return the thread following TP in the step-over chain whose head is
-   CHAIN_HEAD.  Return NULL if TP is the last entry in the chain.  */
-
-extern thread_info *thread_step_over_chain_next (thread_info *chain_head,
-						 thread_info *tp);
-
-/* Return the thread following TP in the global step-over chain, or NULL if TP
-   is the last entry in the chain.  */
-
-extern thread_info *global_thread_step_over_chain_next (thread_info *tp);
-
 /* Return true if TP is in any step-over chain.  */
 
 extern int thread_is_in_step_over_chain (struct thread_info *tp);
@@ -786,7 +790,7 @@ extern int thread_is_in_step_over_chain (struct thread_info *tp);
    TP may be nullptr, in which case it denotes an empty list, so a length of
    0.  */
 
-extern int thread_step_over_chain_length (thread_info *tp);
+extern int thread_step_over_chain_length (const thread_step_over_list &l);
 
 /* Cancel any ongoing execution command.  */
 
diff --git a/gdb/infrun.c b/gdb/infrun.c
index 3f7e80216b82..fcd0f4e10ced 100644
--- a/gdb/infrun.c
+++ b/gdb/infrun.c
@@ -1245,7 +1245,7 @@ follow_exec (ptid_t ptid, const char *exec_file_target)
    to avoid starvation, otherwise, we could e.g., find ourselves
    constantly stepping the same couple threads past their breakpoints
    over and over, if the single-step finish fast enough.  */
-struct thread_info *global_thread_step_over_chain_head;
+thread_step_over_list global_thread_step_over_list;
 
 /* Bit flags indicating what the thread needs to step over.  */
 
@@ -1843,8 +1843,6 @@ start_step_over (void)
 {
   INFRUN_SCOPED_DEBUG_ENTER_EXIT;
 
-  thread_info *next;
-
   /* Don't start a new step-over if we already have an in-line
      step-over operation ongoing.  */
   if (step_over_info_valid_p ())
@@ -1854,8 +1852,8 @@ start_step_over (void)
      steps, threads will be enqueued in the global chain if no buffers are
      available.  If we iterated on the global chain directly, we might iterate
      indefinitely.  */
-  thread_info *threads_to_step = global_thread_step_over_chain_head;
-  global_thread_step_over_chain_head = NULL;
+  thread_step_over_list threads_to_step
+    = std::move (global_thread_step_over_list);
 
   infrun_debug_printf ("stealing global queue of threads to step, length = %d",
 		       thread_step_over_chain_length (threads_to_step));
@@ -1867,18 +1865,22 @@ start_step_over (void)
      global list.  */
   SCOPE_EXIT
     {
-      if (threads_to_step == nullptr)
+      if (threads_to_step.empty ())
 	infrun_debug_printf ("step-over queue now empty");
       else
 	{
 	  infrun_debug_printf ("putting back %d threads to step in global queue",
 			       thread_step_over_chain_length (threads_to_step));
 
-	  global_thread_step_over_chain_enqueue_chain (threads_to_step);
+	  global_thread_step_over_chain_enqueue_chain
+	    (std::move (threads_to_step));
 	}
     };
 
-  for (thread_info *tp = threads_to_step; tp != NULL; tp = next)
+  thread_step_over_list_safe_range range
+    = make_thread_step_over_list_safe_range (threads_to_step);
+
+  for (thread_info *tp : range)
     {
       struct execution_control_state ecss;
       struct execution_control_state *ecs = &ecss;
@@ -1887,8 +1889,6 @@ start_step_over (void)
 
       gdb_assert (!tp->stop_requested);
 
-      next = thread_step_over_chain_next (threads_to_step, tp);
-
       if (tp->inf->displaced_step_state.unavailable)
 	{
 	  /* The arch told us to not even try preparing another displaced step
@@ -1903,7 +1903,7 @@ start_step_over (void)
 	 step over chain indefinitely if something goes wrong when resuming it
 	 If the error is intermittent and it still needs a step over, it will
 	 get enqueued again when we try to resume it normally.  */
-      thread_step_over_chain_remove (&threads_to_step, tp);
+      threads_to_step.erase (threads_to_step.iterator_to (*tp));
 
       step_what = thread_still_needs_step_over (tp);
       must_be_in_line = ((step_what & STEP_OVER_WATCHPOINT)
@@ -3793,15 +3793,16 @@ prepare_for_detach (void)
 
   /* Remove all threads of INF from the global step-over chain.  We
      want to stop any ongoing step-over, not start any new one.  */
-  thread_info *next;
-  for (thread_info *tp = global_thread_step_over_chain_head;
-       tp != nullptr;
-       tp = next)
-    {
-      next = global_thread_step_over_chain_next (tp);
-      if (tp->inf == inf)
+  thread_step_over_list_safe_range range
+    = make_thread_step_over_list_safe_range (global_thread_step_over_list);
+
+  for (thread_info *tp : range)
+    if (tp->inf == inf)
+      {
+	infrun_debug_printf ("removing thread %s from global step over chain",
+			     target_pid_to_str (tp->ptid).c_str ());
 	global_thread_step_over_chain_remove (tp);
-    }
+      }
 
   /* If we were already in the middle of an inline step-over, and the
      thread stepping belongs to the inferior we're detaching, we need
diff --git a/gdb/infrun.h b/gdb/infrun.h
index 7ebb9fc9f4e6..5a577365f946 100644
--- a/gdb/infrun.h
+++ b/gdb/infrun.h
@@ -18,8 +18,10 @@
 #ifndef INFRUN_H
 #define INFRUN_H 1
 
+#include "gdbthread.h"
 #include "symtab.h"
 #include "gdbsupport/byte-vector.h"
+#include "gdbsupport/intrusive_list.h"
 
 struct target_waitstatus;
 struct frame_info;
@@ -253,7 +255,7 @@ extern void mark_infrun_async_event_handler (void);
 
 /* The global chain of threads that need to do a step-over operation
    to get past e.g., a breakpoint.  */
-extern struct thread_info *global_thread_step_over_chain_head;
+extern thread_step_over_list global_thread_step_over_list;
 
 /* Remove breakpoints if possible (usually that means, if everything
    is stopped).  On failure, print a message.  */
diff --git a/gdb/thread.c b/gdb/thread.c
index 506e93cf4016..925ed96c3d83 100644
--- a/gdb/thread.c
+++ b/gdb/thread.c
@@ -183,7 +183,7 @@ void
 set_thread_exited (thread_info *tp, bool silent)
 {
   /* Dead threads don't need to step-over.  Remove from chain.  */
-  if (tp->step_over_next != NULL)
+  if (thread_is_in_step_over_chain (tp))
     global_thread_step_over_chain_remove (tp);
 
   if (tp->state != THREAD_EXITED)
@@ -293,93 +293,22 @@ thread_info::deletable () const
   return refcount () == 0 && !is_current_thread (this);
 }
 
-/* Add TP to the end of the step-over chain LIST_P.  */
-
-static void
-step_over_chain_enqueue (struct thread_info **list_p, struct thread_info *tp)
-{
-  gdb_assert (tp->step_over_next == NULL);
-  gdb_assert (tp->step_over_prev == NULL);
-
-  if (*list_p == NULL)
-    {
-      *list_p = tp;
-      tp->step_over_prev = tp->step_over_next = tp;
-    }
-  else
-    {
-      struct thread_info *head = *list_p;
-      struct thread_info *tail = head->step_over_prev;
-
-      tp->step_over_prev = tail;
-      tp->step_over_next = head;
-      head->step_over_prev = tp;
-      tail->step_over_next = tp;
-    }
-}
-
-/* See gdbthread.h.  */
-
-void
-thread_step_over_chain_remove (thread_info **list_p, thread_info *tp)
-{
-  gdb_assert (tp->step_over_next != NULL);
-  gdb_assert (tp->step_over_prev != NULL);
-
-  if (*list_p == tp)
-    {
-      if (tp == tp->step_over_next)
-	*list_p = NULL;
-      else
-	*list_p = tp->step_over_next;
-    }
-
-  tp->step_over_prev->step_over_next = tp->step_over_next;
-  tp->step_over_next->step_over_prev = tp->step_over_prev;
-  tp->step_over_prev = tp->step_over_next = NULL;
-}
-
-/* See gdbthread.h.  */
-
-thread_info *
-thread_step_over_chain_next (thread_info *chain_head, thread_info *tp)
-{
-  thread_info *next = tp->step_over_next;
-
-  return next == chain_head ? NULL : next;
-}
-
-/* See gdbthread.h.  */
-
-struct thread_info *
-global_thread_step_over_chain_next (struct thread_info *tp)
-{
-  return thread_step_over_chain_next (global_thread_step_over_chain_head, tp);
-}
-
 /* See gdbthread.h.  */
 
 int
 thread_is_in_step_over_chain (struct thread_info *tp)
 {
-  return (tp->step_over_next != NULL);
+  return tp->step_over_list_node.is_linked ();
 }
 
 /* See gdbthread.h.  */
 
 int
-thread_step_over_chain_length (thread_info *tp)
+thread_step_over_chain_length (const thread_step_over_list &l)
 {
-  if (tp == nullptr)
-    return 0;
-
-  gdb_assert (thread_is_in_step_over_chain (tp));
-
   int num = 1;
 
-  for (thread_info *iter = tp->step_over_next;
-       iter != tp;
-       iter = iter->step_over_next)
+  for (const thread_info &thread ATTRIBUTE_UNUSED : l)
     ++num;
 
   return num;
@@ -393,29 +322,16 @@ global_thread_step_over_chain_enqueue (struct thread_info *tp)
   infrun_debug_printf ("enqueueing thread %s in global step over chain",
 		       target_pid_to_str (tp->ptid).c_str ());
 
-  step_over_chain_enqueue (&global_thread_step_over_chain_head, tp);
+  gdb_assert (!thread_is_in_step_over_chain (tp));
+  global_thread_step_over_list.push_back (*tp);
 }
 
 /* See gdbthread.h.  */
 
 void
-global_thread_step_over_chain_enqueue_chain (thread_info *chain_head)
+global_thread_step_over_chain_enqueue_chain (thread_step_over_list &&list)
 {
-  gdb_assert (chain_head->step_over_next != nullptr);
-  gdb_assert (chain_head->step_over_prev != nullptr);
-
-  if (global_thread_step_over_chain_head == nullptr)
-    global_thread_step_over_chain_head = chain_head;
-  else
-    {
-      thread_info *global_last = global_thread_step_over_chain_head->step_over_prev;
-      thread_info *chain_last = chain_head->step_over_prev;
-
-      chain_last->step_over_next = global_thread_step_over_chain_head;
-      global_last->step_over_next = chain_head;
-      global_thread_step_over_chain_head->step_over_prev = chain_last;
-      chain_head->step_over_prev = global_last;
-    }
+  global_thread_step_over_list.splice (std::move (list));
 }
 
 /* See gdbthread.h.  */
@@ -426,7 +342,9 @@ global_thread_step_over_chain_remove (struct thread_info *tp)
   infrun_debug_printf ("removing thread %s from global step over chain",
 		       target_pid_to_str (tp->ptid).c_str ());
 
-  thread_step_over_chain_remove (&global_thread_step_over_chain_head, tp);
+  gdb_assert (thread_is_in_step_over_chain (tp));
+  auto it = global_thread_step_over_list.iterator_to (*tp);
+  global_thread_step_over_list.erase (it);
 }
 
 /* Delete the thread referenced by THR.  If SILENT, don't notify
@@ -810,7 +728,7 @@ set_running_thread (struct thread_info *tp, bool running)
       /* If the thread is now marked stopped, remove it from
 	 the step-over queue, so that we don't try to resume
 	 it until the user wants it to.  */
-      if (tp->step_over_next != NULL)
+      if (thread_is_in_step_over_chain (tp))
 	global_thread_step_over_chain_remove (tp);
     }
 
diff --git a/gdb/unittests/intrusive_list-selftests.c b/gdb/unittests/intrusive_list-selftests.c
index 3ccff54b5ff9..fd2e1fb51af7 100644
--- a/gdb/unittests/intrusive_list-selftests.c
+++ b/gdb/unittests/intrusive_list-selftests.c
@@ -503,6 +503,89 @@ struct intrusive_list_test
     }
   }
 
+  static void
+  test_splice ()
+  {
+    {
+      /* Two non-empty lists.  */
+      item_type a ("a"), b ("b"), c ("c"), d ("d"), e ("e");
+      ListType list1;
+      ListType list2;
+      std::vector<const item_type *> expected;
+
+      list1.push_back (a);
+      list1.push_back (b);
+      list1.push_back (c);
+
+      list2.push_back (d);
+      list2.push_back (e);
+
+      list1.splice (std::move (list2));
+
+      expected = {&a, &b, &c, &d, &e};
+      verify_items (list1, expected);
+
+      expected = {};
+      verify_items (list2, expected);
+    }
+
+    {
+      /* Receiving list empty.  */
+      item_type a ("a"), b ("b"), c ("c");
+      ListType list1;
+      ListType list2;
+      std::vector<const item_type *> expected;
+
+      list2.push_back (a);
+      list2.push_back (b);
+      list2.push_back (c);
+
+      list1.splice (std::move (list2));
+
+      expected = {&a, &b, &c};
+      verify_items (list1, expected);
+
+      expected = {};
+      verify_items (list2, expected);
+    }
+
+    {
+      /* Giving list empty.  */
+      item_type a ("a"), b ("b"), c ("c");
+      ListType list1;
+      ListType list2;
+      std::vector<const item_type *> expected;
+
+      list1.push_back (a);
+      list1.push_back (b);
+      list1.push_back (c);
+
+      list1.splice (std::move (list2));
+
+      expected = {&a, &b, &c};
+      verify_items (list1, expected);
+
+      expected = {};
+      verify_items (list2, expected);
+    }
+
+    {
+      /* Both lists empty.  */
+      item_type a ("a"), b ("b"), c ("c");
+      ListType list1;
+      ListType list2;
+      std::vector<const item_type *> expected;
+
+      list1.splice (std::move (list2));
+
+      expected = {};
+      verify_items (list1, expected);
+
+      expected = {};
+      verify_items (list2, expected);
+    }
+  }
+
   static void
   test_pop_front ()
   {
@@ -682,6 +765,7 @@ test_intrusive_list ()
   tests.test_push_front ();
   tests.test_push_back ();
   tests.test_insert ();
+  tests.test_splice ();
   tests.test_pop_front ();
   tests.test_pop_back ();
   tests.test_erase ();
diff --git a/gdbsupport/intrusive_list.h b/gdbsupport/intrusive_list.h
index 8e98e5b2c1a5..e369a8fcf1dc 100644
--- a/gdbsupport/intrusive_list.h
+++ b/gdbsupport/intrusive_list.h
@@ -350,6 +350,33 @@ class intrusive_list
     pos_node->prev = &elem;
   }
 
+  /* Move elements from LIST at the end of the current list.  */
+  void splice (intrusive_list &&other)
+  {
+    if (other.empty ())
+      return;
+
+    if (this->empty ())
+      {
+	*this = std::move (other);
+	return;
+      }
+
+    /* [A ... B] + [C ... D] */
+    T *b_elem = m_back;
+    node_type *b_node = as_node (b_elem);
+    T *c_elem = other.m_front;
+    node_type *c_node = as_node (c_elem);
+    T *d_elem = other.m_back;
+
+    b_node->next = c_elem;
+    c_node->prev = b_elem;
+    m_back = d_elem;
+
+    other.m_front = nullptr;
+    other.m_back = nullptr;
+  }
+
   void pop_front ()
   {
     gdb_assert (!this->empty ());
diff --git a/gdbsupport/reference-to-pointer-iterator.h b/gdbsupport/reference-to-pointer-iterator.h
index 7303fa4a04ae..9210426adccc 100644
--- a/gdbsupport/reference-to-pointer-iterator.h
+++ b/gdbsupport/reference-to-pointer-iterator.h
@@ -56,6 +56,9 @@ struct reference_to_pointer_iterator
   reference_to_pointer_iterator (const reference_to_pointer_iterator &) = default;
   reference_to_pointer_iterator (reference_to_pointer_iterator &&) = default;
 
+  reference_to_pointer_iterator &operator= (const reference_to_pointer_iterator &) = default;
+  reference_to_pointer_iterator &operator= (reference_to_pointer_iterator &&) = default;
+
   value_type operator* () const
   { return &*m_it; }
 
-- 
2.32.0