[v2,1/1] gdbserver: add process specific thread list and map.
Checks
| Context |
Check |
Description |
| linaro-tcwg-bot/tcwg_gdb_build--master-aarch64 |
success
|
Build passed
|
| linaro-tcwg-bot/tcwg_gdb_build--master-arm |
success
|
Build passed
|
| linaro-tcwg-bot/tcwg_gdb_check--master-aarch64 |
success
|
Test passed
|
Commit Message
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 | 146 +++++++++++++++++++++++++++++++----------
gdbserver/inferiors.cc | 49 ++++++++++----
gdbserver/inferiors.h | 29 +++++++-
gdbserver/server.cc | 59 ++++++++++++++---
4 files changed, 226 insertions(+), 57 deletions(-)
Comments
Hi Stephan,
Here's a first pass, non exhaustive, but I feel like there are enough
comments for now.
On 2024-09-03 07:34, Stephan Rohr wrote:
> 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 | 146 +++++++++++++++++++++++++++++++----------
> gdbserver/inferiors.cc | 49 ++++++++++----
> gdbserver/inferiors.h | 29 +++++++-
> gdbserver/server.cc | 59 ++++++++++++++---
> 4 files changed, 226 insertions(+), 57 deletions(-)
>
> diff --git a/gdbserver/gdbthread.h b/gdbserver/gdbthread.h
> index c5a5498088f..f7562ac54a1 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;
Since all_processes is defined in inferiors.cc, can you puts its
declaration in inferiors.h?
>
> void remove_thread (struct thread_info *thread);
> struct thread_info *add_thread (ptid_t ptid, void *target_data);
> @@ -100,17 +100,20 @@ 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. */
I suggest this more concise formulation:
/* Find the first thread of PROCESS for which FUNC returns true.
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 *> *thread_list = get_thread_list (process);
> + std::list<thread_info *>::iterator next, cur = thread_list->begin ();
>
> - while (cur != all_threads.end ())
> + while (cur != thread_list->end ())
> {
> + /* FUNC may alter the current iterator. */
> next = cur;
> next++;
It seems weird for a find_thread callback to change things, you'd think
that "find" is a read only operation. Suggestion for subsequent
cleanup: I think this can be made simple by using basic_safe_iterator.
>
> @@ -120,7 +123,23 @@ find_thread (Func func)
> cur = next;
> }
>
> - return NULL;
> + return nullptr;
> +}
> +
> +/* Like the above, but consider all threads of all processes. */
I would say just "consider 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);
Should this function (and maybe the other find_thread) take
`Func &&func`, and should this find_thread std::forward it to the other
find_thread (perfect forwarding)?
I'm not too sure why this code uses templating anyway, instead of
gdb::function_view, this seems like an overkill use of templates...
> @@ -142,21 +162,39 @@ 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 *> *thread_map
> + = get_thread_map (process);
> + std::unordered_map<ptid_t, thread_info *>::iterator it
> + = thread_map->find (filter);
> + if (it != 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. */
I would suggest "for each thread of PROCESS", to be more concise.
> @@ -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->m_ptid_thread_map.find (thread_id)
> + == process->m_ptid_thread_map.end ());
Please add a blank line before the comment.
> diff --git a/gdbserver/inferiors.h b/gdbserver/inferiors.h
> index 00e42335014..289954412fe 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. */
Just wondering, is the "sorted by creation order" aspect important to
any part of gdbserver?
> + std::list<thread_info *> m_thread_list;
Could you try to use gdb::intrusive_list for this? It could be as a
follow-up patch, or in this patch, I don't mind. It will be a bit more
lightweight than `std::list`. I think that most uses of std::list in
gdbserver could be replaced with gdb::intrusive_list (or
gdb::owning_intrusive_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 *> m_ptid_thread_map;
I'm wondering if we could just have the map, and not the list. The
"downside" is that it won't be sorted by creation order, which is why
I'm asking above.
> @@ -92,9 +99,25 @@ pid_of (const process_info *proc)
> return proc->pid;
> }
>
> -/* Return a pointer to the process that corresponds to the current
> - thread (current_thread). It is an error to call this if there is
> - no current thread selected. */
> +/* Accessors for a processes' thread list and map. */
> +
> +inline std::list<thread_info *> *
> +get_thread_list (struct process_info *process)
> +{
> + gdb_assert (process != nullptr);
> + return &(process->m_thread_list);
> +}
> +
> +inline std::unordered_map<ptid_t, thread_info *> *
> +get_thread_map (struct process_info *process)
> +{
> + gdb_assert (process != nullptr);
> + return &(process->m_ptid_thread_map);
> +}
Can these be methods of process_info instead? For getter methods, we usually
omit the `get_` prefix. You could then make the `m_*` fields actually
private.
> +
> +/* Return a pointer to the current process. Note that the current
> + process may be non-null while the current thread (current_thread)
> + is null. */
Is this comment change related to this patch? If not, put it in a
separate patch.
> @@ -2509,8 +2506,48 @@ 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 ();
> + std::list<thread_info *> *thread_list;
> +
> + for (; process_iter != all_processes.end (); ++process_iter)
> + {
> + thread_list = get_thread_list (*process_iter);
> + thread_iter = thread_list->begin ();
> + if (thread_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 != 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. */
I was like... this algorithm reminds me of gdb/thread-iter.h... oh, this
comment is from gdb/thread-iter.h :).
I saw Andrew's comment on v1, about sharing this algorithm in
gdbsupport. I agree on the principle, but it doesn't sound easy.
Simon
@@ -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,20 @@ 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 *> *thread_list = get_thread_list (process);
+ std::list<thread_info *>::iterator next, cur = thread_list->begin ();
- while (cur != all_threads.end ())
+ while (cur != thread_list->end ())
{
+ /* FUNC may alter the current iterator. */
next = cur;
next++;
@@ -120,7 +123,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 +148,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 +162,39 @@ 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 *> *thread_map
+ = get_thread_map (process);
+ std::unordered_map<ptid_t, thread_info *>::iterator it
+ = thread_map->find (filter);
+ if (it != 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 *> *thread_list = get_thread_list (process);
+ std::list<thread_info *>::iterator next, cur
+ = thread_list->begin ();
- while (cur != all_threads.end ())
+ while (cur != thread_list->end ())
{
+ /* FUNC may alter the current iterator. */
next = cur;
next++;
func (*cur);
@@ -164,51 +202,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 random thread for which FUNC (THREAD) returns true. If
+ no entry is found then return NULL. */
+
+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)
@@ -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->m_ptid_thread_map.find (thread_id)
+ == process->m_ptid_thread_map.end ());
+
+ process->m_thread_list.push_back (new_thread);
+ process->m_ptid_thread_map.insert ({thread_id, new_thread});
if (current_thread == NULL)
switch_to_thread (new_thread);
@@ -55,18 +61,28 @@ 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 *> * thread_map
+ = get_thread_map (process);
+
+ std::unordered_map<ptid_t, thread_info *>::iterator it
+ = thread_map->find (ptid);
+ if (it != thread_map->end ())
+ return it->second;
+
+ return nullptr;
}
/* Find a thread associated with the given PROCESS, or NULL if no
@@ -101,7 +117,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->m_ptid_thread_map.erase (thread->id);
+ gdb_assert (num_erased > 0);
+ process->m_thread_list.remove (thread);
if (current_thread == thread)
switch_to_thread (nullptr);
free_one_thread (thread);
@@ -129,7 +151,12 @@ void
clear_inferiors (void)
{
for_each_thread (free_one_thread);
- all_threads.clear ();
+
+ for_each_process ([&] (process_info *proc)
+ {
+ proc->m_thread_list.clear ();
+ proc->m_ptid_thread_map.clear ();
+ });
clear_dlls ();
@@ -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 *> m_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 *> m_ptid_thread_map;
+
/* Flag to mark that the DLL list has changed. */
bool dlls_changed = false;
@@ -92,9 +99,25 @@ pid_of (const process_info *proc)
return proc->pid;
}
-/* Return a pointer to the process that corresponds to the current
- thread (current_thread). It is an error to call this if there is
- no current thread selected. */
+/* Accessors for a processes' thread list and map. */
+
+inline std::list<thread_info *> *
+get_thread_list (struct process_info *process)
+{
+ gdb_assert (process != nullptr);
+ return &(process->m_thread_list);
+}
+
+inline std::unordered_map<ptid_t, thread_info *> *
+get_thread_map (struct process_info *process)
+{
+ gdb_assert (process != nullptr);
+ return &(process->m_ptid_thread_map);
+}
+
+/* Return a pointer to the current process. Note that the current
+ process may be non-null while the current thread (current_thread)
+ is null. */
struct process_info *current_process (void);
struct process_info *get_thread_process (const struct thread_info *);
@@ -1342,12 +1342,9 @@ 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)
+ std::list<thread_info *> *thread_list = get_thread_list (process);
+ for (thread_info *thread : *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);
@@ -2509,8 +2506,48 @@ 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 ();
+ std::list<thread_info *> *thread_list;
+
+ for (; process_iter != all_processes.end (); ++process_iter)
+ {
+ thread_list = get_thread_list (*process_iter);
+ thread_iter = thread_list->begin ();
+ if (thread_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 != 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. */
+ std::list<thread_info *> *thread_list
+ = get_thread_list (*process_iter);
+ goto start;
+
+ for (; process_iter != all_processes.end (); ++process_iter)
+ {
+ thread_list = get_thread_list (*process_iter);
+ thread_iter = thread_list->begin ();
+ while (thread_iter != thread_list->end ())
+ {
+ return;
+ start:
+ ++thread_iter;
+ }
+ }
+ };
+
/* Reply the current thread id. */
if (strcmp ("qC", own_buf) == 0 && !disable_packet_qC)
{
@@ -2521,7 +2558,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;
}
@@ -2582,24 +2619,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