[10/11] gdb: maintain ptid -> thread map, optimize find_thread_ptid

Message ID 20210622165704.2404007-11-simon.marchi@polymtl.ca
State New
Headers show
Series
  • Various thread lists optimizations
Related show

Commit Message

Rustam Kovhaev via Gdb-patches June 22, 2021, 4:57 p.m.
When debugging a large number of threads (thousands), looking up a
thread by ptid_t using the inferior::thread_list linked list can add up.

Add inferior::thread_map, an std::unordered_map indexed by ptid_t, and
change the find_thread_ptid function to look up a thread using
std::unordered_map::find, instead of iterating on all of the
inferior's threads.  This should make it faster to look up a thread
from its ptid.

gdb/ChangeLog:
yyyy-mm-dd  Simon Marchi  <simon.marchi@efficios.com>
      	    Pedro Alves  <palves@palves.net>

	* gdbarch-selftests.c (register_to_value_test): Update the mock
	inferior's thread map as well.
	* inferior.c (inferior::clear_thread_list): Clear the thread map.
	* inferior.h: Include <unordered_map>.
	(class inferior::thread_map): New field.
	* regcache.c (cooked_read_test): Update the mock inferior's thread
	map as well.
	* thread.c (set_thread_exited): Remove the thread from the thread
	map.
	(new_thread): Insert the thread in the ptid map.
	(find_thread_ptid): Lookup up the thread in the ptid map.
	(thread_change_ptid): Update ptid map entry.

Change-Id: I3a8da0a839e18dee5bb98b8b7dbeb7f3dfa8ae1c
---
 gdb/inferior.c            |  1 +
 gdb/inferior.h            |  6 ++++++
 gdb/infrun.c              | 10 ++++++++++
 gdb/regcache.c            |  5 +++++
 gdb/scoped-mock-context.h |  1 +
 gdb/thread.c              | 29 ++++++++++++++++++++++++-----
 6 files changed, 47 insertions(+), 5 deletions(-)

-- 
2.32.0

Comments

Pedro Alves July 5, 2021, 3:52 p.m. | #1
On 2021-06-22 5:57 p.m., Simon Marchi via Gdb-patches wrote:
> When debugging a large number of threads (thousands), looking up a

> thread by ptid_t using the inferior::thread_list linked list can add up.

> 

> Add inferior::thread_map, an std::unordered_map indexed by ptid_t, and

> change the find_thread_ptid function to look up a thread using

> std::unordered_map::find, instead of iterating on all of the

> inferior's threads.  This should make it faster to look up a thread

> from its ptid.

> 

> gdb/ChangeLog:

> yyyy-mm-dd  Simon Marchi  <simon.marchi@efficios.com>

>       	    Pedro Alves  <palves@palves.net>

> 

> 	* gdbarch-selftests.c (register_to_value_test): Update the mock

> 	inferior's thread map as well.

> 	* inferior.c (inferior::clear_thread_list): Clear the thread map.

> 	* inferior.h: Include <unordered_map>.

> 	(class inferior::thread_map): New field.

> 	* regcache.c (cooked_read_test): Update the mock inferior's thread

> 	map as well.

> 	* thread.c (set_thread_exited): Remove the thread from the thread

> 	map.

> 	(new_thread): Insert the thread in the ptid map.

> 	(find_thread_ptid): Lookup up the thread in the ptid map.

> 	(thread_change_ptid): Update ptid map entry.

> 


( Should this have Co-Authored-By: ? )

OK.

> Change-Id: I3a8da0a839e18dee5bb98b8b7dbeb7f3dfa8ae1c

> ---
Rustam Kovhaev via Gdb-patches July 6, 2021, 9:31 p.m. | #2
> ( Should this have Co-Authored-By: ? )


Yes, and probably not just this patch.  I'll go over the series and add
them where needed.

When picking up somebody else's patch like this, or the intrusive_list
patch, is it better to keep the original author as the Author and add
ourselves with Co-Authored-By, or set the "final" Author as the git
Author and add previous Authors with Co-Authored-By?

Simon
Pedro Alves July 7, 2021, 12:13 p.m. | #3
On 2021-07-06 10:31 p.m., Simon Marchi wrote:
>> ( Should this have Co-Authored-By: ? )

> 

> Yes, and probably not just this patch.  I'll go over the series and add

> them where needed.

> 

> When picking up somebody else's patch like this, or the intrusive_list

> patch, is it better to keep the original author as the Author and add

> ourselves with Co-Authored-By, or set the "final" Author as the git

> Author and add previous Authors with Co-Authored-By?


I don't know whether there's an established de facto rule.  I think I'd normally
tend to go more by who's the main author of the change, though that's a
judgement call.  It wouldn't make sense to me to tweak someone else's change
in a minor way, add a couple lines, and then make myself "main git author".
If the workload was more balanced, I'd just keep the original author and add
myself to Co-Authored-By.  E.g., today my version of Luis's tag verification
change, the actual code change I posted was all written by me from scratch, but
the essence of the change isn't that different from Luis's original, so I kept
him as main author.

In this particular thread map patch, I don't even remember who did what in
the patch, I'm fine with how you had it.

Patch

diff --git a/gdb/inferior.c b/gdb/inferior.c
index e07a8f88422a..8705c0f7f4b7 100644
--- a/gdb/inferior.c
+++ b/gdb/inferior.c
@@ -184,6 +184,7 @@  inferior::clear_thread_list (bool silent)
       if (thr->deletable ())
 	delete thr;
     });
+  ptid_thread_map.clear ();
 }
 
 void
diff --git a/gdb/inferior.h b/gdb/inferior.h
index 2bfe29afed3f..6662a3bde463 100644
--- a/gdb/inferior.h
+++ b/gdb/inferior.h
@@ -63,6 +63,8 @@  struct thread_info;
 #include "process-stratum-target.h"
 #include "displaced-stepping.h"
 
+#include <unordered_map>
+
 struct infcall_suspend_state;
 struct infcall_control_state;
 
@@ -391,6 +393,10 @@  class inferior : public refcounted_object,
   /* This inferior's thread list, sorted by creation order.  */
   intrusive_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 *, hash_ptid> ptid_thread_map;
+
   /* Returns a range adapter covering the inferior's threads,
      including exited threads.  Used like this:
 
diff --git a/gdb/infrun.c b/gdb/infrun.c
index 80834fed1e3b..1f290b7fa7a6 100644
--- a/gdb/infrun.c
+++ b/gdb/infrun.c
@@ -9421,8 +9421,13 @@  infrun_thread_ptid_changed ()
 
     target1.mock_inferior.pid = old_ptid.pid ();
     target1.mock_thread.ptid = old_ptid;
+    target1.mock_inferior.ptid_thread_map.clear ();
+    target1.mock_inferior.ptid_thread_map[old_ptid] = &target1.mock_thread;
+
     target2.mock_inferior.pid = old_ptid.pid ();
     target2.mock_thread.ptid = old_ptid;
+    target2.mock_inferior.ptid_thread_map.clear ();
+    target2.mock_inferior.ptid_thread_map[old_ptid] = &target2.mock_thread;
 
     auto restore_inferior_ptid = make_scoped_restore (&inferior_ptid, old_ptid);
     set_current_inferior (&target1.mock_inferior);
@@ -9445,8 +9450,13 @@  infrun_thread_ptid_changed ()
 
     target1.mock_inferior.pid = old_ptid.pid ();
     target1.mock_thread.ptid = old_ptid;
+    target1.mock_inferior.ptid_thread_map.clear ();
+    target1.mock_inferior.ptid_thread_map[old_ptid] = &target1.mock_thread;
+
     target2.mock_inferior.pid = old_ptid.pid ();
     target2.mock_thread.ptid = old_ptid;
+    target2.mock_inferior.ptid_thread_map.clear ();
+    target2.mock_inferior.ptid_thread_map[old_ptid] = &target2.mock_thread;
 
     auto restore_inferior_ptid = make_scoped_restore (&inferior_ptid, old_ptid);
     set_current_inferior (&target2.mock_inferior);
diff --git a/gdb/regcache.c b/gdb/regcache.c
index 21fa25d31553..ac44d714ddc1 100644
--- a/gdb/regcache.c
+++ b/gdb/regcache.c
@@ -2044,8 +2044,13 @@  regcache_thread_ptid_changed ()
 
   target1.mock_inferior.pid = old_ptid.pid ();
   target1.mock_thread.ptid = old_ptid;
+  target1.mock_inferior.ptid_thread_map.clear ();
+  target1.mock_inferior.ptid_thread_map[old_ptid] = &target1.mock_thread;
+
   target2.mock_inferior.pid = old_ptid.pid ();
   target2.mock_thread.ptid = old_ptid;
+  target2.mock_inferior.ptid_thread_map.clear ();
+  target2.mock_inferior.ptid_thread_map[old_ptid] = &target2.mock_thread;
 
   gdb_assert (regcaches.empty ());
 
diff --git a/gdb/scoped-mock-context.h b/gdb/scoped-mock-context.h
index ba3b81ed12a5..48fdbacbb14f 100644
--- a/gdb/scoped-mock-context.h
+++ b/gdb/scoped-mock-context.h
@@ -51,6 +51,7 @@  struct scoped_mock_context
     inferior_list.push_back (mock_inferior);
 
     mock_inferior.thread_list.push_back (mock_thread);
+    mock_inferior.ptid_thread_map[mock_ptid] = &mock_thread;
     mock_inferior.gdbarch = gdbarch;
     mock_inferior.aspace = mock_pspace.aspace;
     mock_inferior.pspace = &mock_pspace;
diff --git a/gdb/thread.c b/gdb/thread.c
index 26974e1b8cbc..0d5ec48691a0 100644
--- a/gdb/thread.c
+++ b/gdb/thread.c
@@ -199,6 +199,14 @@  set_thread_exited (thread_info *tp, bool silent)
 
       /* Clear breakpoints, etc. associated with this thread.  */
       clear_thread_inferior_resources (tp);
+
+      /* Remove from the ptid_t map.  We don't want for
+	 find_thread_ptid to find exited threads.  Also, the target
+	 may reuse the ptid for a new thread, and there can only be
+	 one value per key; adding a new thread with the same ptid_t
+	 would overwrite the exited thread's ptid entry.  */
+      size_t nr_deleted = tp->inf->ptid_thread_map.erase (tp->ptid);
+      gdb_assert (nr_deleted == 1);
     }
 }
 
@@ -221,6 +229,11 @@  new_thread (struct inferior *inf, ptid_t ptid)
 
   inf->thread_list.push_back (*tp);
 
+  /* A thread with this ptid should not exist in the map yet.  */
+  gdb_assert (inf->ptid_thread_map.find (ptid) == inf->ptid_thread_map.end ());
+
+  inf->ptid_thread_map[ptid] = tp;
+
   return tp;
 }
 
@@ -477,11 +490,11 @@  find_thread_ptid (inferior *inf, ptid_t ptid)
 {
   gdb_assert (inf != nullptr);
 
-  for (thread_info *tp : inf->non_exited_threads ())
-    if (tp->ptid == ptid)
-      return tp;
-
-  return NULL;
+  auto it = inf->ptid_thread_map.find (ptid);
+  if (it != inf->ptid_thread_map.end ())
+    return it->second;
+  else
+    return nullptr;
 }
 
 /* See gdbthread.h.  */
@@ -751,7 +764,13 @@  thread_change_ptid (process_stratum_target *targ,
   inf->pid = new_ptid.pid ();
 
   tp = find_thread_ptid (inf, old_ptid);
+  gdb_assert (tp != nullptr);
+
+  int num_erased = inf->ptid_thread_map.erase (old_ptid);
+  gdb_assert (num_erased == 1);
+
   tp->ptid = new_ptid;
+  inf->ptid_thread_map[new_ptid] = tp;
 
   gdb::observers::thread_ptid_changed.notify (targ, old_ptid, new_ptid);
 }