[1/1] gdbserver: add process specific thread list and map.

  Replace the servers global thread list with a process specific thread
list and a ptid -> thread map similar to 'inferior::ptid_thread_map' on
GDB side.  Optimize the 'find_thread' and 'find_thread_ptid' functions
to use std::unordered_map::find for faster lookup of threads without
iterating over all processes and threads, if applicable.  This becomes
important when debugging applications with a large thread count, e.g.,
in the context of GPU debugging.

Add the following functions for performance improvements by
limiting the iterator range, if applicable:

  - for_each_thread (ptid_t ptid, Func func)
  - for_each_thread (process_info *process, Func func)
  - find_thread_in_random (ptid_t ptid, Func func)
---
 gdbserver/gdbthread.h  | 142 +++++++++++++++++++++++++++++++----------
 gdbserver/inferiors.cc |  46 +++++++++----
 gdbserver/inferiors.h  |   7 ++
 gdbserver/server.cc    |  52 ++++++++++++---
 4 files changed, 193 insertions(+), 54 deletions(-)
  

Hi Stephan,

Thanks for working on this.  I have a couple of comments, see below...

Stephan Rohr <stephan.rohr@intel.com> writes:

> Replace the servers global thread list with a process specific thread
> list and a ptid -> thread map similar to 'inferior::ptid_thread_map' on
> GDB side.  Optimize the 'find_thread' and 'find_thread_ptid' functions
> to use std::unordered_map::find for faster lookup of threads without
> iterating over all processes and threads, if applicable.  This becomes
> important when debugging applications with a large thread count, e.g.,
> in the context of GPU debugging.
>
> Add the following functions for performance improvements by
> limiting the iterator range, if applicable:
>
>   - for_each_thread (ptid_t ptid, Func func)
>   - for_each_thread (process_info *process, Func func)
>   - find_thread_in_random (ptid_t ptid, Func func)
> ---
>  gdbserver/gdbthread.h  | 142 +++++++++++++++++++++++++++++++----------
>  gdbserver/inferiors.cc |  46 +++++++++----
>  gdbserver/inferiors.h  |   7 ++
>  gdbserver/server.cc    |  52 ++++++++++++---
>  4 files changed, 193 insertions(+), 54 deletions(-)
>
> diff --git a/gdbserver/gdbthread.h b/gdbserver/gdbthread.h
> index c5a5498088f..02e99b76c65 100644
> --- a/gdbserver/gdbthread.h
> +++ b/gdbserver/gdbthread.h
> @@ -85,7 +85,7 @@ struct thread_info
>    gdb_thread_options thread_options = 0;
>  };
>  
> -extern std::list<thread_info *> all_threads;
> +extern std::list<process_info *> all_processes;
>  
>  void remove_thread (struct thread_info *thread);
>  struct thread_info *add_thread (ptid_t ptid, void *target_data);
> @@ -100,17 +100,19 @@ struct thread_info *find_thread_ptid (ptid_t ptid);
>     found.  */
>  struct thread_info *find_any_thread_of_pid (int pid);
>  
> -/* Find the first thread for which FUNC returns true.  Return NULL if no thread
> -   satisfying FUNC is found.  */
> +/* Find the first thread for which FUNC returns true, only consider
> +   threads in the thread list of PROCESS.  Return NULL if no thread
> +   that satisfies FUNC is found.  */
>  
>  template <typename Func>
>  static thread_info *
> -find_thread (Func func)
> +find_thread (process_info *process, Func func)
>  {
> -  std::list<thread_info *>::iterator next, cur = all_threads.begin ();
> +  std::list<thread_info *>::iterator next, cur = process->thread_list.begin ();
>  
> -  while (cur != all_threads.end ())
> +  while (cur != process->thread_list.end ())
>      {
> +      /* FUNC may alter the current iterator.  */
>        next = cur;
>        next++;
>  
> @@ -120,7 +122,23 @@ find_thread (Func func)
>        cur = next;
>      }
>  
> -  return NULL;
> +  return nullptr;
> +}
> +
> +/* Like the above, but consider all threads of all processes.  */
> +
> +template <typename Func>
> +static thread_info *
> +find_thread (Func func)
> +{
> +  for (process_info *proc : all_processes)
> +    {
> +      thread_info *thread = find_thread (proc, func);
> +      if (thread != nullptr)
> +	return thread;
> +    }
> +
> +  return nullptr;
>  }
>  
>  /* Like the above, but only consider threads with pid PID.  */
> @@ -129,10 +147,11 @@ template <typename Func>
>  static thread_info *
>  find_thread (int pid, Func func)
>  {
> -  return find_thread ([&] (thread_info *thread)
> -    {
> -      return thread->id.pid () == pid && func (thread);
> -    });
> +  process_info *process = find_process_pid (pid);
> +  if (process == nullptr)
> +    return nullptr;
> +
> +  return find_thread (process, func);
>  }
>  
>  /* Find the first thread that matches FILTER for which FUNC returns true.
> @@ -142,21 +161,36 @@ template <typename Func>
>  static thread_info *
>  find_thread (ptid_t filter, Func func)
>  {
> -  return find_thread ([&] (thread_info *thread) {
> -    return thread->id.matches (filter) && func (thread);
> -  });
> +  if (filter == minus_one_ptid)
> +    return find_thread (func);
> +
> +  process_info *process = find_process_pid (filter.pid ());
> +  if (process == nullptr)
> +    return nullptr;
> +
> +  if (filter.is_pid ())
> +    return find_thread (process, func);
> +
> +  std::unordered_map<ptid_t, thread_info *>::iterator it
> +    = process->ptid_thread_map.find (filter);
> +  if (it != process->ptid_thread_map.end () && func (it->second))
> +    return it->second;
> +
> +  return nullptr;
>  }
>  
> -/* Invoke FUNC for each thread.  */
> +/* Invoke FUNC for each thread in the thread list of PROCESS.  */
>  
>  template <typename Func>
>  static void
> -for_each_thread (Func func)
> +for_each_thread (process_info *process, Func func)
>  {
> -  std::list<thread_info *>::iterator next, cur = all_threads.begin ();
> +  std::list<thread_info *>::iterator next, cur
> +    = process->thread_list.begin ();
>  
> -  while (cur != all_threads.end ())
> +  while (cur != process->thread_list.end ())
>      {
> +      /* FUNC may alter the current iterator.  */
>        next = cur;
>        next++;
>        func (*cur);
> @@ -164,51 +198,93 @@ for_each_thread (Func func)
>      }
>  }
>  
> +/* Invoke FUNC for each thread.  */
> +
> +template <typename Func>
> +static void
> +for_each_thread (Func func)
> +{
> +  for_each_process ([&] (process_info *proc)
> +    {
> +      for_each_thread (proc, func);
> +    });
> +}
> +
>  /* Like the above, but only consider threads with pid PID.  */
>  
>  template <typename Func>
>  static void
>  for_each_thread (int pid, Func func)
>  {
> -  for_each_thread ([&] (thread_info *thread)
> -    {
> -      if (pid == thread->id.pid ())
> +  process_info *process = find_process_pid (pid);
> +  if (process == nullptr)
> +    return;
> +
> +  for_each_thread (process, func);
> +}
> +
> +/* Like the above, but only consider threads matching PTID.  */
> +
> +template <typename Func>
> +static void
> +for_each_thread (ptid_t ptid, Func func)
> +{
> +  if (ptid == minus_one_ptid)
> +    for_each_thread (func);
> +  else if (ptid.is_pid ())
> +    for_each_thread (ptid.pid (), func);
> +  else
> +    find_thread (ptid, [func] (thread_info *thread)
> +      {
>  	func (thread);
> -    });
> +	return false;
> +      });
>  }
>  
> -/* Find the a random thread for which FUNC (THREAD) returns true.  If
> -   no entry is found then return NULL.  */
> +/* Find a random thread that matches PTID and FUNC (THREAD)
> +   returns true.  If no entry is found then return NULL.  */
>  
>  template <typename Func>
>  static thread_info *
> -find_thread_in_random (Func func)
> +find_thread_in_random (ptid_t ptid, Func func)
>  {
>    int count = 0;
>    int random_selector;
>  
>    /* First count how many interesting entries we have.  */
> -  for_each_thread ([&] (thread_info *thread) {
> -    if (func (thread))
> -      count++;
> -  });
> +  for_each_thread (ptid, [&] (thread_info *thread)
> +    {
> +      if (func (thread))
> +	count++;
> +    });
>  
>    if (count == 0)
> -    return NULL;
> +    return nullptr;
>  
>    /* Now randomly pick an entry out of those.  */
>    random_selector = (int)
>      ((count * (double) rand ()) / (RAND_MAX + 1.0));
>  
> -  thread_info *thread = find_thread ([&] (thread_info *thr_arg) {
> -    return func (thr_arg) && (random_selector-- == 0);
> -  });
> +  thread_info *thread = find_thread (ptid, [&] (thread_info *thr_arg)
> +    {
> +      return func (thr_arg) && (random_selector-- == 0);
> +    });
>  
>    gdb_assert (thread != NULL);
>  
>    return thread;
>  }
>  
> +/* Find the a random thread for which FUNC (THREAD) returns true.  If
> +   no entry is found then return NULL.  */

Typo, drop the 'a' in 'Find the a random'.

> +
> +template <typename Func>
> +static thread_info *
> +find_thread_in_random (Func func)
> +{
> +  return find_thread_in_random (minus_one_ptid, func);
> +}
> +
>  /* Get current thread ID (Linux task ID).  */
>  #define current_ptid (current_thread->id)
>  
> diff --git a/gdbserver/inferiors.cc b/gdbserver/inferiors.cc
> index d088340474f..b3fe6b60fe2 100644
> --- a/gdbserver/inferiors.cc
> +++ b/gdbserver/inferiors.cc
> @@ -23,7 +23,6 @@
>  #include "dll.h"
>  
>  std::list<process_info *> all_processes;
> -std::list<thread_info *> all_threads;
>  
>  /* The current process.  */
>  static process_info *current_process_;
> @@ -41,8 +40,15 @@ struct thread_info *
>  add_thread (ptid_t thread_id, void *target_data)
>  {
>    thread_info *new_thread = new thread_info (thread_id, target_data);
> +  process_info *process = get_thread_process (new_thread);
>  
> -  all_threads.push_back (new_thread);
> +  gdb_assert (process != nullptr);
> +  /* A thread with this ptid should not exist in the map yet.  */
> +  gdb_assert (process->ptid_thread_map.find (thread_id)
> +	      == process->ptid_thread_map.end ());
> +
> +  process->thread_list.push_back (new_thread);
> +  process->ptid_thread_map.insert ({thread_id, new_thread});

Things like this always raise an alarm for me: two data structures
within process_info need to be updated.  And as far as I can tell these
will always need to be updated together, and it would be a mistake to
only update one of these. Continued below....

>  
>    if (current_thread == NULL)
>      switch_to_thread (new_thread);
> @@ -55,18 +61,25 @@ add_thread (ptid_t thread_id, void *target_data)
>  struct thread_info *
>  get_first_thread (void)
>  {
> -  if (!all_threads.empty ())
> -    return all_threads.front ();
> -  else
> -    return NULL;
> +  return find_thread ([] (thread_info *thread)
> +    {
> +      return true;
> +    });
>  }
>  
>  struct thread_info *
>  find_thread_ptid (ptid_t ptid)
>  {
> -  return find_thread ([&] (thread_info *thread) {
> -    return thread->id == ptid;
> -  });
> +  process_info *process = find_process_pid (ptid.pid ());
> +  if (process == nullptr)
> +    return nullptr;
> +
> +  std::unordered_map<ptid_t, thread_info *>::iterator it
> +    = process->ptid_thread_map.find (ptid);
> +  if (it != process->ptid_thread_map.end ())
> +    return it->second;
> +
> +  return nullptr;
>  }
>  
>  /* Find a thread associated with the given PROCESS, or NULL if no
> @@ -101,7 +114,13 @@ remove_thread (struct thread_info *thread)
>      target_disable_btrace (thread->btrace);
>  
>    discard_queued_stop_replies (ptid_of (thread));
> -  all_threads.remove (thread);
> +  process_info *process = get_thread_process (thread);
> +  gdb_assert (process != nullptr);
> +
> +  /* We should not try to remove a thread that was not added.  */
> +  int num_erased = process->ptid_thread_map.erase (thread->id);
> +  gdb_assert (num_erased > 0);
> +  process->thread_list.remove (thread);
>    if (current_thread == thread)
>      switch_to_thread (nullptr);
>    free_one_thread (thread);
> @@ -129,7 +148,12 @@ void
>  clear_inferiors (void)
>  {
>    for_each_thread (free_one_thread);
> -  all_threads.clear ();
> +
> +  for_each_process ([&] (process_info *proc)
> +    {
> +      proc->thread_list.clear ();
> +      proc->ptid_thread_map.clear ();
> +    });
>  
>    clear_dlls ();
>  
> diff --git a/gdbserver/inferiors.h b/gdbserver/inferiors.h
> index 00e42335014..59af3da635f 100644
> --- a/gdbserver/inferiors.h
> +++ b/gdbserver/inferiors.h
> @@ -73,6 +73,13 @@ struct process_info
>    /* DLLs that are loaded for this proc.  */
>    std::list<dll_info> all_dlls;
>  
> +  /* This processes' thread list, sorted by creation order.  */
> +  std::list<thread_info *> thread_list;
> +
> +  /* A map of ptid_t to thread_info*, for average O(1) ptid_t lookup.
> +     Exited threads do not appear in the map.  */
> +  std::unordered_map<ptid_t, thread_info *> ptid_thread_map;

... I think that these should be made private (renaming with the m_
prefix).  Then you'd add some API for accessing and updating the
contents.

> +
>    /* Flag to mark that the DLL list has changed.  */
>    bool dlls_changed = false;
>  
> diff --git a/gdbserver/server.cc b/gdbserver/server.cc
> index 30d05177452..497a1e7249d 100644
> --- a/gdbserver/server.cc
> +++ b/gdbserver/server.cc
> @@ -1329,12 +1329,8 @@ handle_detach (char *own_buf)
>       another process might delete the next thread in the iteration, which is
>       the one saved by the safe iterator.  We will never delete the currently
>       iterated on thread, so standard iteration should be safe.  */
> -  for (thread_info *thread : all_threads)
> +  for (thread_info *thread : process->thread_list)
>      {
> -      /* Only threads that are of the process we are detaching.  */
> -      if (thread->id.pid () != pid)
> -	continue;
> -
>        /* Only threads that have a pending fork event.  */
>        target_waitkind kind;
>        thread_info *child = target_thread_pending_child (thread, &kind);
> @@ -2495,8 +2491,42 @@ static void
>  handle_query (char *own_buf, int packet_len, int *new_packet_len_p)
>  {
>    client_state &cs = get_client_state ();
> +  static std::list<process_info *>::const_iterator process_iter;
>    static std::list<thread_info *>::const_iterator thread_iter;
>  
> +  auto init_thread_iter = [&] ()
> +    {
> +      process_iter = all_processes.begin ();
> +      for (; process_iter != all_processes.end (); ++process_iter)
> +	{
> +	  thread_iter = (*process_iter)->thread_list.begin ();
> +	  if (thread_iter != (*process_iter)->thread_list.end ())
> +	    break;
> +	}
> +      /* Make sure that there is at least one thread to iterate.  */
> +      gdb_assert (process_iter != all_processes.end ());
> +      gdb_assert (thread_iter != (*process_iter)->thread_list.end ());
> +    };
> +
> +  auto advance_thread_iter = [&] ()
> +    {
> +      /* The loop below is written in the natural way as-if we'd always
> +	 start at the beginning of the inferior list.  This fast forwards
> +	 the algorithm to the actual current position.  */
> +      goto start;

My first thought was: "Yuck, there must be a better way to do this.
Doesn't GDB have an all threads iterator?"  Then I went to look for the
all_threads_iterator .... and now I see where you got this from :)

I think in an ideal world what I'd like to see here is the
all_threads_iterator moved into gdbsupport/ then have GDB and gdbserver
both use the class from there.  The problem with that would be that the
current all_threads_iterator mentions things like the 'inferior' class,
which obviously doesn't apply for gdbserver.

But I wonder, maybe we could make a templated version of
all_threads_iterator which takes some kind-of adaptor class?  Name it
abstract_all_threads_iterator or something.  Then GDB and gdbserver
would provide an adaptor and typedef the abstract class + the adaptor to
make an all_threads_iterator class...

Thanks,
Andrew

> +
> +      for (; process_iter != all_processes.end (); ++process_iter)
> +	{
> +	  thread_iter = (*process_iter)->thread_list.begin ();
> +	  while (thread_iter != (*process_iter)->thread_list.end ())
> +	    {
> +	      return;
> +	    start:
> +	      ++thread_iter;
> +	    }
> +	}
> +    };
> +
>    /* Reply the current thread id.  */
>    if (strcmp ("qC", own_buf) == 0 && !disable_packet_qC)
>      {
> @@ -2507,7 +2537,7 @@ handle_query (char *own_buf, int packet_len, int *new_packet_len_p)
>  	ptid = cs.general_thread;
>        else
>  	{
> -	  thread_iter = all_threads.begin ();
> +	  init_thread_iter ();
>  	  ptid = (*thread_iter)->id;
>  	}
>  
> @@ -2568,24 +2598,26 @@ handle_query (char *own_buf, int packet_len, int *new_packet_len_p)
>        if (strcmp ("qfThreadInfo", own_buf) == 0)
>  	{
>  	  require_running_or_return (own_buf);
> -	  thread_iter = all_threads.begin ();
> +	  init_thread_iter ();
>  
>  	  *own_buf++ = 'm';
>  	  ptid_t ptid = (*thread_iter)->id;
>  	  write_ptid (own_buf, ptid);
> -	  thread_iter++;
> +	  advance_thread_iter ();
>  	  return;
>  	}
>  
>        if (strcmp ("qsThreadInfo", own_buf) == 0)
>  	{
>  	  require_running_or_return (own_buf);
> -	  if (thread_iter != all_threads.end ())
> +	  /* We're done if the process iterator hit the end of the
> +	     process list.  */
> +	  if (process_iter != all_processes.end ())
>  	    {
>  	      *own_buf++ = 'm';
>  	      ptid_t ptid = (*thread_iter)->id;
>  	      write_ptid (own_buf, ptid);
> -	      thread_iter++;
> +	      advance_thread_iter ();
>  	      return;
>  	    }
>  	  else
> -- 
> 2.34.1
>
> Intel Deutschland GmbH
> Registered Address: Am Campeon 10, 85579 Neubiberg, Germany
> Tel: +49 89 99 8853-0, www.intel.de
> Managing Directors: Sean Fennelly, Jeffrey Schneiderman, Tiffany Doon Silva
> Chairperson of the Supervisory Board: Nicole Lau
> Registered Office: Munich
> Commercial Register: Amtsgericht Muenchen HRB 186928
  

Hi Andrew,

thank you for your feedback.  I have some questions on the abstract all threads
iterator.  I added my comments below your feedback.

> -----Original Message-----
> From: Andrew Burgess <aburgess@redhat.com>
> Sent: Tuesday, 23 July 2024 16:02
> To: Rohr, Stephan <stephan.rohr@intel.com>; gdb-patches@sourceware.org
> Subject: Re: [PATCH 1/1] gdbserver: add process specific thread list and map.
> 
> 
> Hi Stephan,
> 
> Thanks for working on this.  I have a couple of comments, see below...
> 
> Stephan Rohr <stephan.rohr@intel.com> writes:
> 
> > Replace the servers global thread list with a process specific thread
> > list and a ptid -> thread map similar to 'inferior::ptid_thread_map' on
> > GDB side.  Optimize the 'find_thread' and 'find_thread_ptid' functions
> > to use std::unordered_map::find for faster lookup of threads without
> > iterating over all processes and threads, if applicable.  This becomes
> > important when debugging applications with a large thread count, e.g.,
> > in the context of GPU debugging.
> >
> > Add the following functions for performance improvements by
> > limiting the iterator range, if applicable:
> >
> >   - for_each_thread (ptid_t ptid, Func func)
> >   - for_each_thread (process_info *process, Func func)
> >   - find_thread_in_random (ptid_t ptid, Func func)
> > ---
> >  gdbserver/gdbthread.h  | 142 +++++++++++++++++++++++++++++++-----
> -----
> >  gdbserver/inferiors.cc |  46 +++++++++----
> >  gdbserver/inferiors.h  |   7 ++
> >  gdbserver/server.cc    |  52 ++++++++++++---
> >  4 files changed, 193 insertions(+), 54 deletions(-)
> >
> > diff --git a/gdbserver/gdbthread.h b/gdbserver/gdbthread.h
> > index c5a5498088f..02e99b76c65 100644
> > --- a/gdbserver/gdbthread.h
> > +++ b/gdbserver/gdbthread.h
> > @@ -85,7 +85,7 @@ struct thread_info
> >    gdb_thread_options thread_options = 0;
> >  };
> >
> > -extern std::list<thread_info *> all_threads;
> > +extern std::list<process_info *> all_processes;
> >
> >  void remove_thread (struct thread_info *thread);
> >  struct thread_info *add_thread (ptid_t ptid, void *target_data);
> > @@ -100,17 +100,19 @@ struct thread_info *find_thread_ptid (ptid_t
> ptid);
> >     found.  */
> >  struct thread_info *find_any_thread_of_pid (int pid);
> >
> > -/* Find the first thread for which FUNC returns true.  Return NULL if no
> thread
> > -   satisfying FUNC is found.  */
> > +/* Find the first thread for which FUNC returns true, only consider
> > +   threads in the thread list of PROCESS.  Return NULL if no thread
> > +   that satisfies FUNC is found.  */
> >
> >  template <typename Func>
> >  static thread_info *
> > -find_thread (Func func)
> > +find_thread (process_info *process, Func func)
> >  {
> > -  std::list<thread_info *>::iterator next, cur = all_threads.begin ();
> > +  std::list<thread_info *>::iterator next, cur = process->thread_list.begin ();
> >
> > -  while (cur != all_threads.end ())
> > +  while (cur != process->thread_list.end ())
> >      {
> > +      /* FUNC may alter the current iterator.  */
> >        next = cur;
> >        next++;
> >
> > @@ -120,7 +122,23 @@ find_thread (Func func)
> >        cur = next;
> >      }
> >
> > -  return NULL;
> > +  return nullptr;
> > +}
> > +
> > +/* Like the above, but consider all threads of all processes.  */
> > +
> > +template <typename Func>
> > +static thread_info *
> > +find_thread (Func func)
> > +{
> > +  for (process_info *proc : all_processes)
> > +    {
> > +      thread_info *thread = find_thread (proc, func);
> > +      if (thread != nullptr)
> > +	return thread;
> > +    }
> > +
> > +  return nullptr;
> >  }
> >
> >  /* Like the above, but only consider threads with pid PID.  */
> > @@ -129,10 +147,11 @@ template <typename Func>
> >  static thread_info *
> >  find_thread (int pid, Func func)
> >  {
> > -  return find_thread ([&] (thread_info *thread)
> > -    {
> > -      return thread->id.pid () == pid && func (thread);
> > -    });
> > +  process_info *process = find_process_pid (pid);
> > +  if (process == nullptr)
> > +    return nullptr;
> > +
> > +  return find_thread (process, func);
> >  }
> >
> >  /* Find the first thread that matches FILTER for which FUNC returns true.
> > @@ -142,21 +161,36 @@ template <typename Func>
> >  static thread_info *
> >  find_thread (ptid_t filter, Func func)
> >  {
> > -  return find_thread ([&] (thread_info *thread) {
> > -    return thread->id.matches (filter) && func (thread);
> > -  });
> > +  if (filter == minus_one_ptid)
> > +    return find_thread (func);
> > +
> > +  process_info *process = find_process_pid (filter.pid ());
> > +  if (process == nullptr)
> > +    return nullptr;
> > +
> > +  if (filter.is_pid ())
> > +    return find_thread (process, func);
> > +
> > +  std::unordered_map<ptid_t, thread_info *>::iterator it
> > +    = process->ptid_thread_map.find (filter);
> > +  if (it != process->ptid_thread_map.end () && func (it->second))
> > +    return it->second;
> > +
> > +  return nullptr;
> >  }
> >
> > -/* Invoke FUNC for each thread.  */
> > +/* Invoke FUNC for each thread in the thread list of PROCESS.  */
> >
> >  template <typename Func>
> >  static void
> > -for_each_thread (Func func)
> > +for_each_thread (process_info *process, Func func)
> >  {
> > -  std::list<thread_info *>::iterator next, cur = all_threads.begin ();
> > +  std::list<thread_info *>::iterator next, cur
> > +    = process->thread_list.begin ();
> >
> > -  while (cur != all_threads.end ())
> > +  while (cur != process->thread_list.end ())
> >      {
> > +      /* FUNC may alter the current iterator.  */
> >        next = cur;
> >        next++;
> >        func (*cur);
> > @@ -164,51 +198,93 @@ for_each_thread (Func func)
> >      }
> >  }
> >
> > +/* Invoke FUNC for each thread.  */
> > +
> > +template <typename Func>
> > +static void
> > +for_each_thread (Func func)
> > +{
> > +  for_each_process ([&] (process_info *proc)
> > +    {
> > +      for_each_thread (proc, func);
> > +    });
> > +}
> > +
> >  /* Like the above, but only consider threads with pid PID.  */
> >
> >  template <typename Func>
> >  static void
> >  for_each_thread (int pid, Func func)
> >  {
> > -  for_each_thread ([&] (thread_info *thread)
> > -    {
> > -      if (pid == thread->id.pid ())
> > +  process_info *process = find_process_pid (pid);
> > +  if (process == nullptr)
> > +    return;
> > +
> > +  for_each_thread (process, func);
> > +}
> > +
> > +/* Like the above, but only consider threads matching PTID.  */
> > +
> > +template <typename Func>
> > +static void
> > +for_each_thread (ptid_t ptid, Func func)
> > +{
> > +  if (ptid == minus_one_ptid)
> > +    for_each_thread (func);
> > +  else if (ptid.is_pid ())
> > +    for_each_thread (ptid.pid (), func);
> > +  else
> > +    find_thread (ptid, [func] (thread_info *thread)
> > +      {
> >  	func (thread);
> > -    });
> > +	return false;
> > +      });
> >  }
> >
> > -/* Find the a random thread for which FUNC (THREAD) returns true.  If
> > -   no entry is found then return NULL.  */
> > +/* Find a random thread that matches PTID and FUNC (THREAD)
> > +   returns true.  If no entry is found then return NULL.  */
> >
> >  template <typename Func>
> >  static thread_info *
> > -find_thread_in_random (Func func)
> > +find_thread_in_random (ptid_t ptid, Func func)
> >  {
> >    int count = 0;
> >    int random_selector;
> >
> >    /* First count how many interesting entries we have.  */
> > -  for_each_thread ([&] (thread_info *thread) {
> > -    if (func (thread))
> > -      count++;
> > -  });
> > +  for_each_thread (ptid, [&] (thread_info *thread)
> > +    {
> > +      if (func (thread))
> > +	count++;
> > +    });
> >
> >    if (count == 0)
> > -    return NULL;
> > +    return nullptr;
> >
> >    /* Now randomly pick an entry out of those.  */
> >    random_selector = (int)
> >      ((count * (double) rand ()) / (RAND_MAX + 1.0));
> >
> > -  thread_info *thread = find_thread ([&] (thread_info *thr_arg) {
> > -    return func (thr_arg) && (random_selector-- == 0);
> > -  });
> > +  thread_info *thread = find_thread (ptid, [&] (thread_info *thr_arg)
> > +    {
> > +      return func (thr_arg) && (random_selector-- == 0);
> > +    });
> >
> >    gdb_assert (thread != NULL);
> >
> >    return thread;
> >  }
> >
> > +/* Find the a random thread for which FUNC (THREAD) returns true.  If
> > +   no entry is found then return NULL.  */
> 
> Typo, drop the 'a' in 'Find the a random'.
> 
> > +
> > +template <typename Func>
> > +static thread_info *
> > +find_thread_in_random (Func func)
> > +{
> > +  return find_thread_in_random (minus_one_ptid, func);
> > +}
> > +
> >  /* Get current thread ID (Linux task ID).  */
> >  #define current_ptid (current_thread->id)
> >
> > diff --git a/gdbserver/inferiors.cc b/gdbserver/inferiors.cc
> > index d088340474f..b3fe6b60fe2 100644
> > --- a/gdbserver/inferiors.cc
> > +++ b/gdbserver/inferiors.cc
> > @@ -23,7 +23,6 @@
> >  #include "dll.h"
> >
> >  std::list<process_info *> all_processes;
> > -std::list<thread_info *> all_threads;
> >
> >  /* The current process.  */
> >  static process_info *current_process_;
> > @@ -41,8 +40,15 @@ struct thread_info *
> >  add_thread (ptid_t thread_id, void *target_data)
> >  {
> >    thread_info *new_thread = new thread_info (thread_id, target_data);
> > +  process_info *process = get_thread_process (new_thread);
> >
> > -  all_threads.push_back (new_thread);
> > +  gdb_assert (process != nullptr);
> > +  /* A thread with this ptid should not exist in the map yet.  */
> > +  gdb_assert (process->ptid_thread_map.find (thread_id)
> > +	      == process->ptid_thread_map.end ());
> > +
> > +  process->thread_list.push_back (new_thread);
> > +  process->ptid_thread_map.insert ({thread_id, new_thread});
> 
> Things like this always raise an alarm for me: two data structures
> within process_info need to be updated.  And as far as I can tell these
> will always need to be updated together, and it would be a mistake to
> only update one of these. Continued below....
> 
> >
> >    if (current_thread == NULL)
> >      switch_to_thread (new_thread);
> > @@ -55,18 +61,25 @@ add_thread (ptid_t thread_id, void *target_data)
> >  struct thread_info *
> >  get_first_thread (void)
> >  {
> > -  if (!all_threads.empty ())
> > -    return all_threads.front ();
> > -  else
> > -    return NULL;
> > +  return find_thread ([] (thread_info *thread)
> > +    {
> > +      return true;
> > +    });
> >  }
> >
> >  struct thread_info *
> >  find_thread_ptid (ptid_t ptid)
> >  {
> > -  return find_thread ([&] (thread_info *thread) {
> > -    return thread->id == ptid;
> > -  });
> > +  process_info *process = find_process_pid (ptid.pid ());
> > +  if (process == nullptr)
> > +    return nullptr;
> > +
> > +  std::unordered_map<ptid_t, thread_info *>::iterator it
> > +    = process->ptid_thread_map.find (ptid);
> > +  if (it != process->ptid_thread_map.end ())
> > +    return it->second;
> > +
> > +  return nullptr;
> >  }
> >
> >  /* Find a thread associated with the given PROCESS, or NULL if no
> > @@ -101,7 +114,13 @@ remove_thread (struct thread_info *thread)
> >      target_disable_btrace (thread->btrace);
> >
> >    discard_queued_stop_replies (ptid_of (thread));
> > -  all_threads.remove (thread);
> > +  process_info *process = get_thread_process (thread);
> > +  gdb_assert (process != nullptr);
> > +
> > +  /* We should not try to remove a thread that was not added.  */
> > +  int num_erased = process->ptid_thread_map.erase (thread->id);
> > +  gdb_assert (num_erased > 0);
> > +  process->thread_list.remove (thread);
> >    if (current_thread == thread)
> >      switch_to_thread (nullptr);
> >    free_one_thread (thread);
> > @@ -129,7 +148,12 @@ void
> >  clear_inferiors (void)
> >  {
> >    for_each_thread (free_one_thread);
> > -  all_threads.clear ();
> > +
> > +  for_each_process ([&] (process_info *proc)
> > +    {
> > +      proc->thread_list.clear ();
> > +      proc->ptid_thread_map.clear ();
> > +    });
> >
> >    clear_dlls ();
> >
> > diff --git a/gdbserver/inferiors.h b/gdbserver/inferiors.h
> > index 00e42335014..59af3da635f 100644
> > --- a/gdbserver/inferiors.h
> > +++ b/gdbserver/inferiors.h
> > @@ -73,6 +73,13 @@ struct process_info
> >    /* DLLs that are loaded for this proc.  */
> >    std::list<dll_info> all_dlls;
> >
> > +  /* This processes' thread list, sorted by creation order.  */
> > +  std::list<thread_info *> thread_list;
> > +
> > +  /* A map of ptid_t to thread_info*, for average O(1) ptid_t lookup.
> > +     Exited threads do not appear in the map.  */
> > +  std::unordered_map<ptid_t, thread_info *> ptid_thread_map;
> 
> ... I think that these should be made private (renaming with the m_
> prefix).  Then you'd add some API for accessing and updating the
> contents.
> 
> > +
> >    /* Flag to mark that the DLL list has changed.  */
> >    bool dlls_changed = false;
> >
> > diff --git a/gdbserver/server.cc b/gdbserver/server.cc
> > index 30d05177452..497a1e7249d 100644
> > --- a/gdbserver/server.cc
> > +++ b/gdbserver/server.cc
> > @@ -1329,12 +1329,8 @@ handle_detach (char *own_buf)
> >       another process might delete the next thread in the iteration, which is
> >       the one saved by the safe iterator.  We will never delete the currently
> >       iterated on thread, so standard iteration should be safe.  */
> > -  for (thread_info *thread : all_threads)
> > +  for (thread_info *thread : process->thread_list)
> >      {
> > -      /* Only threads that are of the process we are detaching.  */
> > -      if (thread->id.pid () != pid)
> > -	continue;
> > -
> >        /* Only threads that have a pending fork event.  */
> >        target_waitkind kind;
> >        thread_info *child = target_thread_pending_child (thread, &kind);
> > @@ -2495,8 +2491,42 @@ static void
> >  handle_query (char *own_buf, int packet_len, int *new_packet_len_p)
> >  {
> >    client_state &cs = get_client_state ();
> > +  static std::list<process_info *>::const_iterator process_iter;
> >    static std::list<thread_info *>::const_iterator thread_iter;
> >
> > +  auto init_thread_iter = [&] ()
> > +    {
> > +      process_iter = all_processes.begin ();
> > +      for (; process_iter != all_processes.end (); ++process_iter)
> > +	{
> > +	  thread_iter = (*process_iter)->thread_list.begin ();
> > +	  if (thread_iter != (*process_iter)->thread_list.end ())
> > +	    break;
> > +	}
> > +      /* Make sure that there is at least one thread to iterate.  */
> > +      gdb_assert (process_iter != all_processes.end ());
> > +      gdb_assert (thread_iter != (*process_iter)->thread_list.end ());
> > +    };
> > +
> > +  auto advance_thread_iter = [&] ()
> > +    {
> > +      /* The loop below is written in the natural way as-if we'd always
> > +	 start at the beginning of the inferior list.  This fast forwards
> > +	 the algorithm to the actual current position.  */
> > +      goto start;
> 
> My first thought was: "Yuck, there must be a better way to do this.
> Doesn't GDB have an all threads iterator?"  Then I went to look for the
> all_threads_iterator .... and now I see where you got this from :)
> 
> I think in an ideal world what I'd like to see here is the
> all_threads_iterator moved into gdbsupport/ then have GDB and gdbserver
> both use the class from there.  The problem with that would be that the
> current all_threads_iterator mentions things like the 'inferior' class,
> which obviously doesn't apply for gdbserver.
> 
> But I wonder, maybe we could make a templated version of
> all_threads_iterator which takes some kind-of adaptor class?  Name it
> abstract_all_threads_iterator or something.  Then GDB and gdbserver
> would provide an adaptor and typedef the abstract class + the adaptor to
> make an all_threads_iterator class...
> 

I implemented an abstract all threads iterator class with the necessary adaptors
using the CRTP pattern for both GDB and gdbserver.  I did some modifications
on gdbserver side and change the type of 'all_processes' and the thread list to use
an 'intrusive_list' like the GDB implementation.  This simplifies the adaptor on
gdbserver side.  Is this what you had in mind?  I would then test and submit a new
version of the patch (including the type change as separate commit). 

> Thanks,
> Andrew
> 

Thanks
Stephan

> > +
> > +      for (; process_iter != all_processes.end (); ++process_iter)
> > +	{
> > +	  thread_iter = (*process_iter)->thread_list.begin ();
> > +	  while (thread_iter != (*process_iter)->thread_list.end ())
> > +	    {
> > +	      return;
> > +	    start:
> > +	      ++thread_iter;
> > +	    }
> > +	}
> > +    };
> > +
> >    /* Reply the current thread id.  */
> >    if (strcmp ("qC", own_buf) == 0 && !disable_packet_qC)
> >      {
> > @@ -2507,7 +2537,7 @@ handle_query (char *own_buf, int packet_len, int
> *new_packet_len_p)
> >  	ptid = cs.general_thread;
> >        else
> >  	{
> > -	  thread_iter = all_threads.begin ();
> > +	  init_thread_iter ();
> >  	  ptid = (*thread_iter)->id;
> >  	}
> >
> > @@ -2568,24 +2598,26 @@ handle_query (char *own_buf, int packet_len,
> int *new_packet_len_p)
> >        if (strcmp ("qfThreadInfo", own_buf) == 0)
> >  	{
> >  	  require_running_or_return (own_buf);
> > -	  thread_iter = all_threads.begin ();
> > +	  init_thread_iter ();
> >
> >  	  *own_buf++ = 'm';
> >  	  ptid_t ptid = (*thread_iter)->id;
> >  	  write_ptid (own_buf, ptid);
> > -	  thread_iter++;
> > +	  advance_thread_iter ();
> >  	  return;
> >  	}
> >
> >        if (strcmp ("qsThreadInfo", own_buf) == 0)
> >  	{
> >  	  require_running_or_return (own_buf);
> > -	  if (thread_iter != all_threads.end ())
> > +	  /* We're done if the process iterator hit the end of the
> > +	     process list.  */
> > +	  if (process_iter != all_processes.end ())
> >  	    {
> >  	      *own_buf++ = 'm';
> >  	      ptid_t ptid = (*thread_iter)->id;
> >  	      write_ptid (own_buf, ptid);
> > -	      thread_iter++;
> > +	      advance_thread_iter ();
> >  	      return;
> >  	    }
> >  	  else
> > --
> > 2.34.1
> >
> > Intel Deutschland GmbH
> > Registered Address: Am Campeon 10, 85579 Neubiberg, Germany
> > Tel: +49 89 99 8853-0, www.intel.de
> > Managing Directors: Sean Fennelly, Jeffrey Schneiderman, Tiffany Doon Silva
> > Chairperson of the Supervisory Board: Nicole Lau
> > Registered Office: Munich
> > Commercial Register: Amtsgericht Muenchen HRB 186928

Intel Deutschland GmbH
Registered Address: Am Campeon 10, 85579 Neubiberg, Germany
Tel: +49 89 99 8853-0, www.intel.de
Managing Directors: Sean Fennelly, Jeffrey Schneiderman, Tiffany Doon Silva
Chairperson of the Supervisory Board: Nicole Lau
Registered Office: Munich
Commercial Register: Amtsgericht Muenchen HRB 186928