gdb: change regcache list to be a map

One regcache object is created for each stopped thread and is stored in
the regcache::regcaches linked list.  Looking up a regcache for a given
thread is therefore in O(number of threads).  Stopping all threads then
becomes O((number of threads) ^ 2).  Same goes for resuming a thread
(need to delete the regcache of a given ptid) and resuming all threads.
It becomes noticeable when debugging thousands of threads, which is
typical with GPU targets.  This patch replaces the linked list with some
maps to reduce that complexity.

The first design was using an std::unordered_map with (target, ptid,
arch) as the key, because that's how lookups are done (in
get_thread_arch_aspace_regcache).  However, the registers_changed_ptid
function, also somewhat on the hot path (it is used when resuming
threads), needs to delete all regcaches associated to a given (target,
ptid) tuple.  If the key of the map is (target, ptid, arch), we have to
walk all items of the map, not good.

The second design was therefore using an std::unordered_multimap with
(target, ptid) as the key.  One key could be associated to multiple
regcaches, all with different gdbarches.  When looking up, we would have
to walk all these regcaches.  This would be ok, because there will
usually be actually one matching regcache.  In the exceptional
multi-arch thread cases, there will be maybe two.  However, in
registers_changed_ptid, we sometimes need to remove all regcaches
matching a given target.  We would then have to talk all items of the
map again, not good.

The design as implemented in this patch therefore uses two levels of
map.  One std::unordered_map uses the target as the key.  The value type
is an std::unordered_multimap that itself uses the ptid as the key.  The
values of the multimap are the regcaches themselves.  Again, we expect
to have one or very few regcaches per (target, ptid).

So, in summary:

* The lookups (in get_thread_arch_aspace_regcache), become faster when
  the number of threads grows, compared to the linked list.  With a
  small number of threads, it will probably be a bit slower to do map
  lookups than to walk a few linked list nodes, but I don't think it
  will be noticeable in practice.

* The function registers_changed_ptid deletes all regcaches related to a
  given (target, ptid).  It must now handle the different cases separately:

    - NULL target and minus_one_ptid: we delete all the entries
    - NULL target and non-minus_one_ptid: invalid (checked by assert)
    - non-NULL target and non-minus_one_ptid: we delete all the entries
      associated to that tuple
    - a non-NULL target and minus_one_ptid: we delete all the entries
      associated to that target

* The function regcache_thread_ptid_changed is called when a thread
  changes ptid.  It is implemented efficiently using the map, although
  that's not very important: it is not called often, mostly when
  creating an inferior, on some specific platforms.

This patch is a tiny bit from ROCm GDB [1] we would like to merge
upstream.  Laurent Morichetti gave be these performance numbers:

The benchmark used is:

  time ./gdb --data-directory=data-directory /extra/lmoriche/hip/samples/0_Intro/bit_extract/bit_extract -ex "set pagination off" -ex "set breakpoint pending on" -ex "b bit_extract_kernel if \$_thread == 5" -ex run -ex c -batch

It measures the time it takes to continue from a conditional breakpoint with
2048 threads at that breakpoint, one of them reporting the breakpoint.

baseline:
real    0m10.227s
real    0m10.177s
real    0m10.362s

with patch:
real    0m8.356s
real    0m8.424s
real    0m8.494s

[1] https://github.com/ROCm-Developer-Tools/ROCgdb

gdb/ChangeLog:

	* regcache.c (ptid_regcache_map): New type.
	(target_ptid_regcache_map): New type.
	(regcaches): Change type to target_ptid_regcache_map.
	(get_thread_arch_aspace_regcache): Update to regcaches' new
	type.
	(regcache_thread_ptid_changed): Likewise.
	(registers_changed_ptid): Likewise.
	(regcaches_size): Likewise.
	(regcaches_test): Update.
	(regcache_thread_ptid_changed): Update.
	* regcache.h (regcache_up): New type.
	* gdbsupport/ptid.h (hash_ptid): New struct.

Change-Id: Iabb0a1111707936ca111ddb13f3b09efa83d3402

4 files changed, 125 insertions, 42 deletions

diff --git a/gdb/ChangeLog b/gdb/ChangeLog
index fa1120e8..88583bd 100644
--- a/gdb/ChangeLog
+++ b/gdb/ChangeLog
@@ -1,3 +1,18 @@
+2020-08-07  Simon Marchi  <simon.marchi@polymtl.ca>
+
+	* regcache.c (ptid_regcache_map): New type.
+	(target_ptid_regcache_map): New type.
+	(regcaches): Change type to target_ptid_regcache_map.
+	(get_thread_arch_aspace_regcache): Update to regcaches' new
+	type.
+	(regcache_thread_ptid_changed): Likewise.
+	(registers_changed_ptid): Likewise.
+	(regcaches_size): Likewise.
+	(regcaches_test): Update.
+	(regcache_thread_ptid_changed): Update.
+	* regcache.h (regcache_up): New type.
+	* gdbsupport/ptid.h (hash_ptid): New struct.
+
 2020-08-07  Simon Marchi  <simon.marchi@efficios.com>
 
 	* observable.h (thread_ptid_changed): Add parameter
diff --git a/gdb/regcache.c b/gdb/regcache.c
index 71e528f..b8fcc52 100644
--- a/gdb/regcache.c
+++ b/gdb/regcache.c
@@ -29,7 +29,7 @@
 #include "reggroups.h"
 #include "observable.h"
 #include "regset.h"
-#include <forward_list>
+#include <unordered_map>
 
 /*
  * DATA STRUCTURE
@@ -313,31 +313,48 @@ reg_buffer::assert_regnum (int regnum) const
     gdb_assert (regnum < gdbarch_num_regs (arch ()));
 }
 
-/* Global structure containing the current regcache.  */
+/* Type to map a ptid to a list of regcaches (one thread may have multiple
+   regcaches, associated to different gdbarches).  */
+
+using ptid_regcache_map
+  = std::unordered_multimap<ptid_t, regcache_up, hash_ptid>;
+
+/* Type to map a target to a ptid_regcache_map, holding the regcaches for the
+   threads defined by that target.  */
+
+using target_ptid_regcache_map
+  = std::unordered_map<process_stratum_target *, ptid_regcache_map>;
+
+/* Global structure containing the existing regcaches.  */
 
 /* NOTE: this is a write-through cache.  There is no "dirty" bit for
    recording if the register values have been changed (eg. by the
    user).  Therefore all registers must be written back to the
    target when appropriate.  */
-static std::forward_list<regcache *> regcaches;
+static target_ptid_regcache_map regcaches;
 
 struct regcache *
 get_thread_arch_aspace_regcache (process_stratum_target *target,
-				 ptid_t ptid, struct gdbarch *gdbarch,
+				 ptid_t ptid, gdbarch *arch,
 				 struct address_space *aspace)
 {
   gdb_assert (target != nullptr);
 
-  for (const auto &regcache : regcaches)
-    if (regcache->target () == target
-	&& regcache->ptid () == ptid
-	&& regcache->arch () == gdbarch)
-      return regcache;
+  /* Find the ptid -> regcache map for this target.  */
+  auto &ptid_regc_map = regcaches[target];
 
-  regcache *new_regcache = new regcache (target, gdbarch, aspace);
+  /* Check first if a regcache for this arch already exists.  */
+  auto range = ptid_regc_map.equal_range (ptid);
+  for (auto it = range.first; it != range.second; ++it)
+    {
+      if (it->second->arch () == arch)
+	return it->second.get ();
+    }
 
-  regcaches.push_front (new_regcache);
+  /* It does not exist, create it.  */
+  regcache *new_regcache = new regcache (target, arch, aspace);
   new_regcache->set_ptid (ptid);
+  ptid_regc_map.insert (std::make_pair (ptid, new_regcache));
 
   return new_regcache;
 }
@@ -417,10 +434,22 @@ static void
 regcache_thread_ptid_changed (process_stratum_target *target,
 			      ptid_t old_ptid, ptid_t new_ptid)
 {
-  for (auto &regcache : regcaches)
+  auto ptid_regc_map_it = regcaches.find (target);
+
+  if (ptid_regc_map_it == regcaches.end ())
+    return;
+
+  auto &ptid_regc_map = ptid_regc_map_it->second;
+  auto range = ptid_regc_map.equal_range (old_ptid);
+  for (auto it = range.first; it != range.second;)
     {
-      if (regcache->ptid () == old_ptid && regcache->target () == target)
-	regcache->set_ptid (new_ptid);
+      regcache_up rc = std::move (it->second);
+      rc->set_ptid (new_ptid);
+
+      /* Remove old before inserting new, to avoid rehashing,
+	 which would invalidate iterators.  */
+      it = ptid_regc_map.erase (it);
+      ptid_regc_map.insert (std::make_pair (new_ptid, std::move (rc)));
     }
 }
 
@@ -438,18 +467,31 @@ regcache_thread_ptid_changed (process_stratum_target *target,
 void
 registers_changed_ptid (process_stratum_target *target, ptid_t ptid)
 {
-  for (auto oit = regcaches.before_begin (), it = std::next (oit);
-       it != regcaches.end (); )
+  if (target == nullptr)
+    {
+      /* Since there can be ptid clashes between targets, it's not valid to
+	 pass a ptid without saying to which target it belongs.  */
+      gdb_assert (ptid == minus_one_ptid);
+
+      /* Delete all the regcaches of all targets.  */
+      regcaches.clear ();
+    }
+  else if (ptid != minus_one_ptid)
     {
-      struct regcache *regcache = *it;
-      if ((target == nullptr || regcache->target () == target)
-	  && regcache->ptid ().matches (ptid))
+      /* Non-NULL target and non-minus_one_ptid, delete all regcaches belonging
+	to this (TARGET, PTID).  */
+      auto ptid_regc_map_it = regcaches.find (target);
+      if (ptid_regc_map_it != regcaches.end ())
 	{
-	  delete regcache;
-	  it = regcaches.erase_after (oit);
+	  auto &ptid_regc_map = ptid_regc_map_it->second;
+	  ptid_regc_map.erase (ptid);
 	}
-      else
-	oit = it++;
+    }
+  else
+    {
+       /* Non-NULL target and minus_one_ptid, delete all regcaches
+	  associated to this target.  */
+      regcaches.erase (target);
     }
 
   if ((target == nullptr || current_thread_target == target)
@@ -1434,8 +1476,14 @@ namespace selftests {
 static size_t
 regcaches_size ()
 {
-  return std::distance (regcaches.begin (),
-			  regcaches.end ());
+  size_t size = 0;
+  for (auto it = regcaches.begin (); it != regcaches.end (); ++it)
+    {
+      auto &ptid_regc_map = it->second;
+      size += ptid_regc_map.size ();
+    }
+
+  return size;
 }
 
 /* Wrapper around get_thread_arch_aspace_regcache that does some self checks.  */
@@ -1852,31 +1900,33 @@ regcache_thread_ptid_changed ()
   get_thread_arch_aspace_regcache (&target2.mock_target, old_ptid, arch,
 				   nullptr);
 
-  /* Return whether a regcache for (TARGET, PTID) exists in REGCACHES.  */
-  auto regcache_exists = [] (process_stratum_target *target, ptid_t ptid)
+  /* Return the count of regcaches for (TARGET, PTID) in REGCACHES.  */
+  auto regcache_count = [] (process_stratum_target *target, ptid_t ptid)
+    -> int
     {
-      for (regcache *rc : regcaches)
+      auto ptid_regc_map_it = regcaches.find (target);
+      if (ptid_regc_map_it != regcaches.end ())
 	{
-	  if (rc->target () == target && rc->ptid () == ptid)
-	    return true;
+	  auto &ptid_regc_map = ptid_regc_map_it->second;
+	  auto range = ptid_regc_map.equal_range (ptid);
+	  return std::distance (range.first, range.second);
 	}
-
-      return false;
+      return 0;
     };
 
-  gdb_assert (regcaches_size () == 2);
-  gdb_assert (regcache_exists (&target1.mock_target, old_ptid));
-  gdb_assert (!regcache_exists (&target1.mock_target, new_ptid));
-  gdb_assert (regcache_exists (&target2.mock_target, old_ptid));
-  gdb_assert (!regcache_exists (&target2.mock_target, new_ptid));
+  gdb_assert (regcaches.size () == 2);
+  gdb_assert (regcache_count (&target1.mock_target, old_ptid) == 1);
+  gdb_assert (regcache_count (&target1.mock_target, new_ptid) == 0);
+  gdb_assert (regcache_count (&target2.mock_target, old_ptid) == 1);
+  gdb_assert (regcache_count (&target2.mock_target, new_ptid) == 0);
 
   thread_change_ptid (&target1.mock_target, old_ptid, new_ptid);
 
-  gdb_assert (regcaches_size () == 2);
-  gdb_assert (!regcache_exists (&target1.mock_target, old_ptid));
-  gdb_assert (regcache_exists (&target1.mock_target, new_ptid));
-  gdb_assert (regcache_exists (&target2.mock_target, old_ptid));
-  gdb_assert (!regcache_exists (&target2.mock_target, new_ptid));
+  gdb_assert (regcaches.size () == 2);
+  gdb_assert (regcache_count (&target1.mock_target, old_ptid) == 0);
+  gdb_assert (regcache_count (&target1.mock_target, new_ptid) == 1);
+  gdb_assert (regcache_count (&target2.mock_target, old_ptid) == 1);
+  gdb_assert (regcache_count (&target2.mock_target, new_ptid) == 0);
 
   /* Leave the regcache list empty.  */
   registers_changed ();
diff --git a/gdb/regcache.h b/gdb/regcache.h
index dd0c2f2..9390f57 100644
--- a/gdb/regcache.h
+++ b/gdb/regcache.h
@@ -435,6 +435,8 @@ private:
 				   struct address_space *aspace);
 };
 
+using regcache_up = std::unique_ptr<regcache>;
+
 class readonly_detached_regcache : public readable_regcache
 {
 public:
diff --git a/gdbsupport/ptid.h b/gdbsupport/ptid.h
index ef52d55..a528312 100644
--- a/gdbsupport/ptid.h
+++ b/gdbsupport/ptid.h
@@ -32,6 +32,8 @@
    thread_stratum target that might want to sit on top.
 */
 
+#include <functional>
+
 class ptid_t
 {
 public:
@@ -143,6 +145,20 @@ private:
   long m_tid;
 };
 
+/* Functor to hash a ptid.  */
+
+struct hash_ptid
+{
+  size_t operator() (const ptid_t &ptid) const
+  {
+    std::hash<long> long_hash;
+
+    return (long_hash (ptid.pid ())
+	    + long_hash (ptid.lwp ())
+	    + long_hash (ptid.tid ()));
+  }
+};
+
 /* The null or zero ptid, often used to indicate no process. */
 
 extern const ptid_t null_ptid;