[PATCH 0/4] Regcache fix and optimization

[PATCH 0/4] Regcache fix and optimization

[Simon Marchi]

The main goal of this series is patch 4, and is about changing the
regcache storage from a linked list to a map, to make lookups and
removals more efficient.

Patches 1 and 2 are cleanups.  They are not necessary, but I think they
would be nice to have.

Patch 3 addresses a potential bug I spotted while reading the code.

Simon Marchi (4):
  gdb: rename regcache::current_regcache to regcache::regcaches
  gdb: move regcache::regcaches to regcache.c
  gdb: pass target to thread_ptid_changed observable
  gdb: change regcache list to be a map

 gdb/dwarf2/index-write.c |   1 +
 gdb/infrun.c             |  78 +++++++++++-
 gdb/observable.h         |   6 +-
 gdb/record-btrace.c      |   1 +
 gdb/regcache.c           | 259 +++++++++++++++++++++++++++++----------
 gdb/regcache.h           |   7 --
 gdb/sparc64-tdep.c       |   2 +-
 gdb/thread.c             |   2 +-
 gdbsupport/ptid.h        |  16 +++
 9 files changed, 291 insertions(+), 81 deletions(-)

-- 
2.26.2

[PATCH 1/4] gdb: rename regcache::current_regcache to regcache::regcaches

[Simon Marchi]

The name `current_regcache` for the list of currently-existing regcaches
sounds wrong.  The name is singular, but it holds multiple regcaches, so
it could at least be `current_regcaches`.

But in other places in GDB, "current" usually means "the object we are
working with right now".  For example, we swap the "current thread" when
we want to operate on a given thread.  This is not the case here, this
variable just holds all regcaches that exist at any given time, not "the
regcache we are working with right now".

So, I think calling it `regcaches` is better.  I also considered
`regcache_list`, but a subsequent patch will make it a map and not a
list, so it would sound wrong again.  `regcaches` sounds right for any
collection of regcache, whatever the type.

Rename a few other things that were related to this `current_regcache`
field.  Note that there is a `get_current_regcache` function, which
returns the regcache of the current thread.  That one is fine, because
it returns the regcache for the current thread.

gdb/ChangeLog:

	* regcache.h (class regcache) <current_regcache>: Rename to...
	<regcaches>: ... this.  Move doc here.
	* regcache.c (regcache::current_regcache) Rename to...
	(regcache::regcaches): ... this.  Move doc to header.
	(get_thread_arch_aspace_regcache): Update.
	(regcache::regcache_thread_ptid_changed): Update.
	(registers_changed_ptid): Update.
	(class regcache_access) <current_regcache_size>: Rename to...
	<regcaches_size>: ... this.
	(current_regcache_test): Rename to...
	(regcaches_test): ... this.
	(_initialize_regcache): Update.

Change-Id: I87de67154f5fe17a1f6aee7c4f2036647ee27b99
---
 gdb/regcache.c | 60 ++++++++++++++++++++++++--------------------------
 gdb/regcache.h |  2 +-
 2 files changed, 30 insertions(+), 32 deletions(-)

diff --git a/gdb/regcache.c b/gdb/regcache.c
index 4ebb8cb04527..3d8e4adf0efd 100644
--- a/gdb/regcache.c
+++ b/gdb/regcache.c
@@ -319,7 +319,7 @@ reg_buffer::assert_regnum (int regnum) const
    recording if the register values have been changed (eg. by the
    user).  Therefore all registers must be written back to the
    target when appropriate.  */
-std::forward_list<regcache *> regcache::current_regcache;
+std::forward_list<regcache *> regcache::regcaches;
 
 struct regcache *
 get_thread_arch_aspace_regcache (process_stratum_target *target,
@@ -328,7 +328,7 @@ get_thread_arch_aspace_regcache (process_stratum_target *target,
 {
   gdb_assert (target != nullptr);
 
-  for (const auto &regcache : regcache::current_regcache)
+  for (const auto &regcache : regcache::regcaches)
     if (regcache->target () == target
 	&& regcache->ptid () == ptid
 	&& regcache->arch () == gdbarch)
@@ -336,7 +336,7 @@ get_thread_arch_aspace_regcache (process_stratum_target *target,
 
   regcache *new_regcache = new regcache (target, gdbarch, aspace);
 
-  regcache::current_regcache.push_front (new_regcache);
+  regcache::regcaches.push_front (new_regcache);
   new_regcache->set_ptid (ptid);
 
   return new_regcache;
@@ -417,7 +417,7 @@ regcache_observer_target_changed (struct target_ops *target)
 void
 regcache::regcache_thread_ptid_changed (ptid_t old_ptid, ptid_t new_ptid)
 {
-  for (auto &regcache : regcache::current_regcache)
+  for (auto &regcache : regcache::regcaches)
     {
       if (regcache->ptid () == old_ptid)
 	regcache->set_ptid (new_ptid);
@@ -438,17 +438,15 @@ regcache::regcache_thread_ptid_changed (ptid_t old_ptid, ptid_t new_ptid)
 void
 registers_changed_ptid (process_stratum_target *target, ptid_t ptid)
 {
-  for (auto oit = regcache::current_regcache.before_begin (),
-	 it = std::next (oit);
-       it != regcache::current_regcache.end ();
-       )
+  for (auto oit = regcache::regcaches.before_begin (), it = std::next (oit);
+       it != regcache::regcaches.end (); )
     {
       struct regcache *regcache = *it;
       if ((target == nullptr || regcache->target () == target)
 	  && regcache->ptid ().matches (ptid))
 	{
 	  delete regcache;
-	  it = regcache::current_regcache.erase_after (oit);
+	  it = regcache::regcaches.erase_after (oit);
 	}
       else
 	oit = it++;
@@ -1437,13 +1435,13 @@ class regcache_access : public regcache
 {
 public:
 
-  /* Return the number of elements in current_regcache.  */
+  /* Return the number of elements in regcache::regcaches.  */
 
   static size_t
-  current_regcache_size ()
+  regcaches_size ()
   {
-    return std::distance (regcache::current_regcache.begin (),
-			  regcache::current_regcache.end ());
+    return std::distance (regcache::regcaches.begin (),
+			  regcache::regcaches.end ());
   }
 };
 
@@ -1463,10 +1461,10 @@ test_get_thread_arch_aspace_regcache (process_stratum_target *target,
 }
 
 static void
-current_regcache_test (void)
+regcaches_test (void)
 {
   /* It is empty at the start.  */
-  SELF_CHECK (regcache_access::current_regcache_size () == 0);
+  SELF_CHECK (regcache_access::regcaches_size () == 0);
 
   ptid_t ptid1 (1), ptid2 (2), ptid3 (3);
 
@@ -1474,57 +1472,57 @@ current_regcache_test (void)
   test_target_ops test_target2;
 
   /* Get regcache from (target1,ptid1), a new regcache is added to
-     current_regcache.  */
+     regcache::regcaches.  */
   test_get_thread_arch_aspace_regcache (&test_target1, ptid1,
 					target_gdbarch (),
 					NULL);
-  SELF_CHECK (regcache_access::current_regcache_size () == 1);
+  SELF_CHECK (regcache_access::regcaches_size () == 1);
 
   /* Get regcache from (target1,ptid2), a new regcache is added to
-     current_regcache.  */
+     regcache::regcaches.  */
   test_get_thread_arch_aspace_regcache (&test_target1, ptid2,
 					target_gdbarch (),
 					NULL);
-  SELF_CHECK (regcache_access::current_regcache_size () == 2);
+  SELF_CHECK (regcache_access::regcaches_size () == 2);
 
   /* Get regcache from (target1,ptid3), a new regcache is added to
-     current_regcache.  */
+     regcache::regcaches.  */
   test_get_thread_arch_aspace_regcache (&test_target1, ptid3,
 					target_gdbarch (),
 					NULL);
-  SELF_CHECK (regcache_access::current_regcache_size () == 3);
+  SELF_CHECK (regcache_access::regcaches_size () == 3);
 
   /* Get regcache from (target1,ptid2) again, nothing is added to
-     current_regcache.  */
+     regcache::regcaches.  */
   test_get_thread_arch_aspace_regcache (&test_target1, ptid2,
 					target_gdbarch (),
 					NULL);
-  SELF_CHECK (regcache_access::current_regcache_size () == 3);
+  SELF_CHECK (regcache_access::regcaches_size () == 3);
 
   /* Get regcache from (target2,ptid2), a new regcache is added to
-     current_regcache, since this time we're using a differen
+     regcache::regcaches, since this time we're using a differen
      target.  */
   test_get_thread_arch_aspace_regcache (&test_target2, ptid2,
 					target_gdbarch (),
 					NULL);
-  SELF_CHECK (regcache_access::current_regcache_size () == 4);
+  SELF_CHECK (regcache_access::regcaches_size () == 4);
 
   /* Mark that (target1,ptid2) changed.  The regcache of (target1,
-     ptid2) should be removed from current_regcache.  */
+     ptid2) should be removed from regcache::regcaches.  */
   registers_changed_ptid (&test_target1, ptid2);
-  SELF_CHECK (regcache_access::current_regcache_size () == 3);
+  SELF_CHECK (regcache_access::regcaches_size () == 3);
 
   /* Get the regcache from (target2,ptid2) again, confirming the
      registers_changed_ptid call above did not delete it.  */
   test_get_thread_arch_aspace_regcache (&test_target2, ptid2,
 					target_gdbarch (),
 					NULL);
-  SELF_CHECK (regcache_access::current_regcache_size () == 3);
+  SELF_CHECK (regcache_access::regcaches_size () == 3);
 
   /* Confirm that marking all regcaches of all targets as changed
-     clears current_regcache.  */
+     clears regcache::regcaches.  */
   registers_changed_ptid (nullptr, minus_one_ptid);
-  SELF_CHECK (regcache_access::current_regcache_size () == 0);
+  SELF_CHECK (regcache_access::regcaches_size () == 0);
 }
 
 class target_ops_no_register : public test_target_ops
@@ -1846,7 +1844,7 @@ _initialize_regcache ()
 	   _("Force gdb to flush its register cache (maintainer command)."));
 
 #if GDB_SELF_TEST
-  selftests::register_test ("current_regcache", selftests::current_regcache_test);
+  selftests::register_test ("regcaches", selftests::regcaches_test);
 
   selftests::register_test_foreach_arch ("regcache::cooked_read_test",
 					 selftests::cooked_read_test);
diff --git a/gdb/regcache.h b/gdb/regcache.h
index b8561d714c9e..f2627958aa12 100644
--- a/gdb/regcache.h
+++ b/gdb/regcache.h
@@ -402,7 +402,7 @@ class regcache : public detached_regcache
   regcache (process_stratum_target *target, gdbarch *gdbarch,
 	    const address_space *aspace);
 
-  static std::forward_list<regcache *> current_regcache;
+  static std::forward_list<regcache *> regcaches;
 
 private:
 
-- 
2.26.2

[PATCH 2/4] gdb: move regcache::regcaches to regcache.c

[Simon Marchi]

I don't really understand why `regcache_thread_ptid_changed` is a static
method of `struct regcache` instead of being a static free function in
regcache.c.  And I don't understand why `current_regcache` is a static
member of `struct regcache` instead of being a static global in
regcache.c.  It's not wrong per-se, but there's no other place where we
do it like this in GDB (as far as I remember) and it just exposes things
unnecessarily in the .h.

Move them to be just static in regcache.c.  As a result,
registers_changed_ptid doesn't need to be friend of the regcache class
anymore.

Removing the include of forward_list in regcache.h showed that we were
missing an include for it in dwarf2/index-write.c, record-btrace.c and
sparc64-tdep.c.

gdb/ChangeLog:

	* regcache.h (class regcache): Remove friend
	registers_changed_ptid.
	<regcache_thread_ptid_changed>: Remove.
	<regcaches>: Remove.
	* regcache.c (regcache::regcaches): Rename to...
	(regcaches): ... this.  Make static.
	(get_thread_arch_aspace_regcache): Update.
	(regcache::regcache_thread_ptid_changed): Rename to...
	(regcache_thread_ptid_changed): ... this.  Update.
	(class regcache_access): Remove.
	(regcaches_test): Update.
	(_initialize_regcache): Update.
	* sparc64-tdep.c, dwarf2/index-write.c, record-btrace.c: Include
	<forward_list>.

Change-Id: Iabc25759848010cfbb7ee7e27f60eaca17d61c12
---
 gdb/dwarf2/index-write.c |  1 +
 gdb/record-btrace.c      |  1 +
 gdb/regcache.c           | 74 +++++++++++++++++-----------------------
 gdb/regcache.h           |  7 ----
 gdb/sparc64-tdep.c       |  2 +-
 5 files changed, 35 insertions(+), 50 deletions(-)

diff --git a/gdb/dwarf2/index-write.c b/gdb/dwarf2/index-write.c
index 97b2310656ca..aa7a37e4ef2a 100644
--- a/gdb/dwarf2/index-write.c
+++ b/gdb/dwarf2/index-write.c
@@ -41,6 +41,7 @@
 
 #include <algorithm>
 #include <cmath>
+#include <forward_list>
 #include <set>
 #include <unordered_map>
 #include <unordered_set>
diff --git a/gdb/record-btrace.c b/gdb/record-btrace.c
index 36ae671fa904..2a0bf7979582 100644
--- a/gdb/record-btrace.c
+++ b/gdb/record-btrace.c
@@ -43,6 +43,7 @@
 #include "gdbarch.h"
 #include "cli/cli-style.h"
 #include "async-event.h"
+#include <forward_list>
 
 static const target_info record_btrace_target_info = {
   "record-btrace",
diff --git a/gdb/regcache.c b/gdb/regcache.c
index 3d8e4adf0efd..54354fe2c161 100644
--- a/gdb/regcache.c
+++ b/gdb/regcache.c
@@ -319,7 +319,7 @@ reg_buffer::assert_regnum (int regnum) const
    recording if the register values have been changed (eg. by the
    user).  Therefore all registers must be written back to the
    target when appropriate.  */
-std::forward_list<regcache *> regcache::regcaches;
+static std::forward_list<regcache *> regcaches;
 
 struct regcache *
 get_thread_arch_aspace_regcache (process_stratum_target *target,
@@ -328,7 +328,7 @@ get_thread_arch_aspace_regcache (process_stratum_target *target,
 {
   gdb_assert (target != nullptr);
 
-  for (const auto &regcache : regcache::regcaches)
+  for (const auto &regcache : regcaches)
     if (regcache->target () == target
 	&& regcache->ptid () == ptid
 	&& regcache->arch () == gdbarch)
@@ -336,7 +336,7 @@ get_thread_arch_aspace_regcache (process_stratum_target *target,
 
   regcache *new_regcache = new regcache (target, gdbarch, aspace);
 
-  regcache::regcaches.push_front (new_regcache);
+  regcaches.push_front (new_regcache);
   new_regcache->set_ptid (ptid);
 
   return new_regcache;
@@ -412,12 +412,11 @@ regcache_observer_target_changed (struct target_ops *target)
   registers_changed ();
 }
 
-/* Update global variables old ptids to hold NEW_PTID if they were
-   holding OLD_PTID.  */
-void
-regcache::regcache_thread_ptid_changed (ptid_t old_ptid, ptid_t new_ptid)
+/* Update regcaches related to OLD_PTID to now use NEW_PTID.  */
+static void
+regcache_thread_ptid_changed (ptid_t old_ptid, ptid_t new_ptid)
 {
-  for (auto &regcache : regcache::regcaches)
+  for (auto &regcache : regcaches)
     {
       if (regcache->ptid () == old_ptid)
 	regcache->set_ptid (new_ptid);
@@ -438,15 +437,15 @@ regcache::regcache_thread_ptid_changed (ptid_t old_ptid, ptid_t new_ptid)
 void
 registers_changed_ptid (process_stratum_target *target, ptid_t ptid)
 {
-  for (auto oit = regcache::regcaches.before_begin (), it = std::next (oit);
-       it != regcache::regcaches.end (); )
+  for (auto oit = regcaches.before_begin (), it = std::next (oit);
+       it != regcaches.end (); )
     {
       struct regcache *regcache = *it;
       if ((target == nullptr || regcache->target () == target)
 	  && regcache->ptid ().matches (ptid))
 	{
 	  delete regcache;
-	  it = regcache::regcaches.erase_after (oit);
+	  it = regcaches.erase_after (oit);
 	}
       else
 	oit = it++;
@@ -1431,19 +1430,12 @@ register_dump::dump (ui_file *file)
 
 namespace selftests {
 
-class regcache_access : public regcache
+static size_t
+regcaches_size ()
 {
-public:
-
-  /* Return the number of elements in regcache::regcaches.  */
-
-  static size_t
-  regcaches_size ()
-  {
-    return std::distance (regcache::regcaches.begin (),
-			  regcache::regcaches.end ());
-  }
-};
+  return std::distance (regcaches.begin (),
+			  regcaches.end ());
+}
 
 /* Wrapper around get_thread_arch_aspace_regcache that does some self checks.  */
 
@@ -1464,7 +1456,7 @@ static void
 regcaches_test (void)
 {
   /* It is empty at the start.  */
-  SELF_CHECK (regcache_access::regcaches_size () == 0);
+  SELF_CHECK (regcaches_size () == 0);
 
   ptid_t ptid1 (1), ptid2 (2), ptid3 (3);
 
@@ -1472,57 +1464,56 @@ regcaches_test (void)
   test_target_ops test_target2;
 
   /* Get regcache from (target1,ptid1), a new regcache is added to
-     regcache::regcaches.  */
+     REGCACHES.  */
   test_get_thread_arch_aspace_regcache (&test_target1, ptid1,
 					target_gdbarch (),
 					NULL);
-  SELF_CHECK (regcache_access::regcaches_size () == 1);
+  SELF_CHECK (regcaches_size () == 1);
 
   /* Get regcache from (target1,ptid2), a new regcache is added to
-     regcache::regcaches.  */
+     REGCACHES.  */
   test_get_thread_arch_aspace_regcache (&test_target1, ptid2,
 					target_gdbarch (),
 					NULL);
-  SELF_CHECK (regcache_access::regcaches_size () == 2);
+  SELF_CHECK (regcaches_size () == 2);
 
   /* Get regcache from (target1,ptid3), a new regcache is added to
-     regcache::regcaches.  */
+     REGCACHES.  */
   test_get_thread_arch_aspace_regcache (&test_target1, ptid3,
 					target_gdbarch (),
 					NULL);
-  SELF_CHECK (regcache_access::regcaches_size () == 3);
+  SELF_CHECK (regcaches_size () == 3);
 
   /* Get regcache from (target1,ptid2) again, nothing is added to
-     regcache::regcaches.  */
+     REGCACHES.  */
   test_get_thread_arch_aspace_regcache (&test_target1, ptid2,
 					target_gdbarch (),
 					NULL);
-  SELF_CHECK (regcache_access::regcaches_size () == 3);
+  SELF_CHECK (regcaches_size () == 3);
 
   /* Get regcache from (target2,ptid2), a new regcache is added to
-     regcache::regcaches, since this time we're using a differen
-     target.  */
+     REGCACHES, since this time we're using a different target.  */
   test_get_thread_arch_aspace_regcache (&test_target2, ptid2,
 					target_gdbarch (),
 					NULL);
-  SELF_CHECK (regcache_access::regcaches_size () == 4);
+  SELF_CHECK (regcaches_size () == 4);
 
   /* Mark that (target1,ptid2) changed.  The regcache of (target1,
-     ptid2) should be removed from regcache::regcaches.  */
+     ptid2) should be removed from REGCACHES.  */
   registers_changed_ptid (&test_target1, ptid2);
-  SELF_CHECK (regcache_access::regcaches_size () == 3);
+  SELF_CHECK (regcaches_size () == 3);
 
   /* Get the regcache from (target2,ptid2) again, confirming the
      registers_changed_ptid call above did not delete it.  */
   test_get_thread_arch_aspace_regcache (&test_target2, ptid2,
 					target_gdbarch (),
 					NULL);
-  SELF_CHECK (regcache_access::regcaches_size () == 3);
+  SELF_CHECK (regcaches_size () == 3);
 
   /* Confirm that marking all regcaches of all targets as changed
-     clears regcache::regcaches.  */
+     clears REGCACHES.  */
   registers_changed_ptid (nullptr, minus_one_ptid);
-  SELF_CHECK (regcache_access::regcaches_size () == 0);
+  SELF_CHECK (regcaches_size () == 0);
 }
 
 class target_ops_no_register : public test_target_ops
@@ -1837,8 +1828,7 @@ _initialize_regcache ()
     = gdbarch_data_register_post_init (init_regcache_descr);
 
   gdb::observers::target_changed.attach (regcache_observer_target_changed);
-  gdb::observers::thread_ptid_changed.attach
-    (regcache::regcache_thread_ptid_changed);
+  gdb::observers::thread_ptid_changed.attach (regcache_thread_ptid_changed);
 
   add_com ("flushregs", class_maintenance, reg_flush_command,
 	   _("Force gdb to flush its register cache (maintainer command)."));
diff --git a/gdb/regcache.h b/gdb/regcache.h
index f2627958aa12..dd0c2f27f95a 100644
--- a/gdb/regcache.h
+++ b/gdb/regcache.h
@@ -22,7 +22,6 @@
 
 #include "gdbsupport/common-regcache.h"
 #include "gdbsupport/function-view.h"
-#include <forward_list>
 
 struct regcache;
 struct regset;
@@ -397,13 +396,10 @@ class regcache : public detached_regcache
    debug.  */
   void debug_print_register (const char *func, int regno);
 
-  static void regcache_thread_ptid_changed (ptid_t old_ptid, ptid_t new_ptid);
 protected:
   regcache (process_stratum_target *target, gdbarch *gdbarch,
 	    const address_space *aspace);
 
-  static std::forward_list<regcache *> regcaches;
-
 private:
 
   /* Helper function for transfer_regset.  Copies across a single register.  */
@@ -437,9 +433,6 @@ class regcache : public detached_regcache
   get_thread_arch_aspace_regcache (process_stratum_target *target, ptid_t ptid,
 				   struct gdbarch *gdbarch,
 				   struct address_space *aspace);
-
-  friend void
-  registers_changed_ptid (process_stratum_target *target, ptid_t ptid);
 };
 
 class readonly_detached_regcache : public readable_regcache
diff --git a/gdb/sparc64-tdep.c b/gdb/sparc64-tdep.c
index f4810523dfaa..95979ab76f50 100644
--- a/gdb/sparc64-tdep.c
+++ b/gdb/sparc64-tdep.c
@@ -33,8 +33,8 @@
 #include "target-descriptions.h"
 #include "target.h"
 #include "value.h"
-
 #include "sparc64-tdep.h"
+#include <forward_list>
 
 /* This file implements the SPARC 64-bit ABI as defined by the
    section "Low-Level System Information" of the SPARC Compliance
-- 
2.26.2

[PATCH 3/4] gdb: pass target to thread_ptid_changed observable

[Simon Marchi]

I noticed what I think is a potential bug.  I did not observe it nor was
I able to reproduce it using actual debugging.  It's quite unlikely,
because it involves multi-target and ptid clashes.  I added selftests
that demonstrate it though.

The thread_ptid_changed observer says that thread with OLD_PTID now has
NEW_PTID.  Now, if for some reason we happen to have two targets
defining a thread with OLD_PTID, the observers don't know which thread
this is about.

regcache::regcache_thread_ptid_changed changes all regcaches with
OLD_PTID.  If there is a regcache for a thread with ptid OLD_PTID, but
that belongs to a different target, this regcache will be erroneously
changed.

Similarly, infrun_thread_ptid_changed updates inferior_ptid if
inferior_ptid matches OLD_PTID.  But if inferior_ptid currently refers
not to the thread is being changed, but to a thread with the same ptid
belonging to a different target, then inferior_ptid will erroneously be
changed.

This patch adds a `process_stratum_target *` parameter to the
`thread_ptid_changed` observable and makes the two observers use it.
Tests for both are added, which would fail if the corresponding fix
wasn't done.

gdb/ChangeLog:

	* observable.h (thread_ptid_changed): Add parameter
	`process_stratum_target *`.
	* infrun.c (infrun_thread_ptid_changed): Add parameter
	`process_stratum_target *` and use it.
	(selftests): New namespace.
	(infrun_thread_ptid_changed): New function.
	(_initialize_infrun): Register selftest.
	* regcache.c (regcache_thread_ptid_changed): Add parameter
	`process_stratum_target *` and use it.
	(regcache_thread_ptid_changed): New function.
	(_initialize_regcache): Register selftest.
	* thread.c (thread_change_ptid): Pass target to
	thread_ptid_changed observable.

Change-Id: I0599e61224b6d154a7b55088a894cb88298c3c71
---
 gdb/infrun.c     | 78 ++++++++++++++++++++++++++++++++++++++++++++++--
 gdb/observable.h |  6 ++--
 gdb/regcache.c   | 59 ++++++++++++++++++++++++++++++++++--
 gdb/thread.c     |  2 +-
 4 files changed, 138 insertions(+), 7 deletions(-)

diff --git a/gdb/infrun.c b/gdb/infrun.c
index 31266109a6d3..3fbe45efb8ca 100644
--- a/gdb/infrun.c
+++ b/gdb/infrun.c
@@ -67,6 +67,9 @@
 #include "gdbsupport/gdb_select.h"
 #include <unordered_map>
 #include "async-event.h"
+#include "gdbsupport/selftest.h"
+#include "scoped-mock-context.h"
+#include "test-target.h"
 
 /* Prototypes for local functions */
 
@@ -2068,9 +2071,11 @@ start_step_over (void)
 /* Update global variables holding ptids to hold NEW_PTID if they were
    holding OLD_PTID.  */
 static void
-infrun_thread_ptid_changed (ptid_t old_ptid, ptid_t new_ptid)
+infrun_thread_ptid_changed (process_stratum_target *target,
+			    ptid_t old_ptid, ptid_t new_ptid)
 {
-  if (inferior_ptid == old_ptid)
+  if (inferior_ptid == old_ptid
+      && current_inferior ()->process_target () == target)
     inferior_ptid = new_ptid;
 }
 
@@ -9467,6 +9472,70 @@ infrun_async_inferior_event_handler (gdb_client_data data)
   inferior_event_handler (INF_REG_EVENT);
 }
 
+namespace selftests
+{
+
+/* Verify that when two threads with the same ptid exist (from two different
+   targets) and one of them changes ptid, we only update inferior_ptid if
+   it is appropriate.  */
+
+static void
+infrun_thread_ptid_changed ()
+{
+  gdbarch *arch = current_inferior ()->gdbarch;
+
+  /* The thread which inferior_ptid represents changes ptid.  */
+  {
+    scoped_restore_current_pspace_and_thread restore;
+
+    scoped_mock_context<test_target_ops> target1 (arch);
+    scoped_mock_context<test_target_ops> target2 (arch);
+    target2.mock_inferior.next = &target1.mock_inferior;
+
+    ptid_t old_ptid (111, 222);
+    ptid_t new_ptid (111, 333);
+
+    target1.mock_inferior.pid = old_ptid.pid ();
+    target1.mock_thread.ptid = old_ptid;
+    target2.mock_inferior.pid = old_ptid.pid ();
+    target2.mock_thread.ptid = old_ptid;
+
+    auto restore_inferior_ptid = make_scoped_restore (&inferior_ptid, old_ptid);
+    set_current_inferior (&target1.mock_inferior);
+
+    thread_change_ptid (&target1.mock_target, old_ptid, new_ptid);
+
+    gdb_assert (inferior_ptid == new_ptid);
+  }
+
+  /* A thread with the same ptid as inferior_ptid, but from another target,
+     changes ptid.  */
+  {
+    scoped_restore_current_pspace_and_thread restore;
+
+    scoped_mock_context<test_target_ops> target1 (arch);
+    scoped_mock_context<test_target_ops> target2 (arch);
+    target2.mock_inferior.next = &target1.mock_inferior;
+
+    ptid_t old_ptid (111, 222);
+    ptid_t new_ptid (111, 333);
+
+    target1.mock_inferior.pid = old_ptid.pid ();
+    target1.mock_thread.ptid = old_ptid;
+    target2.mock_inferior.pid = old_ptid.pid ();
+    target2.mock_thread.ptid = old_ptid;
+
+    auto restore_inferior_ptid = make_scoped_restore (&inferior_ptid, old_ptid);
+    set_current_inferior (&target2.mock_inferior);
+
+    thread_change_ptid (&target1.mock_target, old_ptid, new_ptid);
+
+    gdb_assert (inferior_ptid == old_ptid);
+  }
+}
+
+} /* namespace selftests */
+
 void _initialize_infrun ();
 void
 _initialize_infrun ()
@@ -9768,4 +9837,9 @@ or signalled."),
 			   show_observer_mode,
 			   &setlist,
 			   &showlist);
+
+#if GDB_SELF_TEST
+  selftests::register_test ("infrun_thread_ptid_changed",
+			    selftests::infrun_thread_ptid_changed);
+#endif
 }
diff --git a/gdb/observable.h b/gdb/observable.h
index 070cf0f18e51..da0a9b12f74c 100644
--- a/gdb/observable.h
+++ b/gdb/observable.h
@@ -27,6 +27,7 @@ struct so_list;
 struct objfile;
 struct thread_info;
 struct inferior;
+struct process_stratum_target;
 struct trace_state_variable;
 
 namespace gdb
@@ -165,8 +166,9 @@ extern observable<struct gdbarch */* newarch */> architecture_changed;
 
 /* The thread's ptid has changed.  The OLD_PTID parameter specifies
    the old value, and NEW_PTID specifies the new value.  */
-extern observable<ptid_t /* old_ptid */, ptid_t /* new_ptid */>
-    thread_ptid_changed;
+extern observable<process_stratum_target * /* target */,
+		  ptid_t /* old_ptid */, ptid_t /* new_ptid */>
+  thread_ptid_changed;
 
 /* The inferior INF has been added to the list of inferiors.  At
    this point, it might not be associated with any process.  */
diff --git a/gdb/regcache.c b/gdb/regcache.c
index 54354fe2c161..fb20250d20f0 100644
--- a/gdb/regcache.c
+++ b/gdb/regcache.c
@@ -414,11 +414,12 @@ regcache_observer_target_changed (struct target_ops *target)
 
 /* Update regcaches related to OLD_PTID to now use NEW_PTID.  */
 static void
-regcache_thread_ptid_changed (ptid_t old_ptid, ptid_t new_ptid)
+regcache_thread_ptid_changed (process_stratum_target *target,
+			      ptid_t old_ptid, ptid_t new_ptid)
 {
   for (auto &regcache : regcaches)
     {
-      if (regcache->ptid () == old_ptid)
+      if (regcache->ptid () == old_ptid && regcache->target () == target)
 	regcache->set_ptid (new_ptid);
     }
 }
@@ -1817,6 +1818,58 @@ cooked_write_test (struct gdbarch *gdbarch)
     }
 }
 
+/* Verify that when two threads with the same ptid exist (from two different
+   targets) and one of them changes ptid, we only update the appropriate
+   regcaches.  */
+
+static void
+regcache_thread_ptid_changed ()
+{
+  /* Any arch will do.  */
+  gdbarch *arch = current_inferior ()->gdbarch;
+
+  /* Prepare two targets with one thread each, with the same ptid.  */
+  scoped_mock_context<test_target_ops> target1 (arch);
+  scoped_mock_context<test_target_ops> target2 (arch);
+  target2.mock_inferior.next = &target1.mock_inferior;
+
+  ptid_t old_ptid (111, 222);
+  ptid_t new_ptid (111, 333);
+
+  target1.mock_inferior.pid = old_ptid.pid ();
+  target1.mock_thread.ptid = old_ptid;
+  target2.mock_inferior.pid = old_ptid.pid ();
+  target2.mock_thread.ptid = old_ptid;
+
+  gdb_assert (regcaches.empty ());
+
+  /* Populate the regcaches container.  */
+  get_thread_arch_aspace_regcache (&target1.mock_target, old_ptid, arch, NULL);
+  get_thread_arch_aspace_regcache (&target2.mock_target, old_ptid, arch, NULL);
+
+  /* Return whether a regcache for (TARGET, PTID) exists in REGCACHES.  */
+  auto regcache_exists = [] (process_stratum_target *target, ptid_t ptid)
+    {
+      for (regcache *rc : regcaches)
+	{
+	  if (rc->target () == target && rc->ptid () == ptid)
+	    return true;
+	}
+
+      return false;
+    };
+
+  gdb_assert (regcaches_size () == 2);
+  gdb_assert (regcache_exists (&target1.mock_target, old_ptid));
+  gdb_assert (regcache_exists (&target2.mock_target, old_ptid));
+
+  thread_change_ptid (&target1.mock_target, old_ptid, new_ptid);
+
+  gdb_assert (regcaches_size () == 2);
+  gdb_assert (regcache_exists (&target1.mock_target, new_ptid));
+  gdb_assert (regcache_exists (&target2.mock_target, old_ptid));
+}
+
 } // namespace selftests
 #endif /* GDB_SELF_TEST */
 
@@ -1840,5 +1893,7 @@ _initialize_regcache ()
 					 selftests::cooked_read_test);
   selftests::register_test_foreach_arch ("regcache::cooked_write_test",
 					 selftests::cooked_write_test);
+  selftests::register_test ("regcache_thread_ptid_changed",
+			    selftests::regcache_thread_ptid_changed);
 #endif
 }
diff --git a/gdb/thread.c b/gdb/thread.c
index 4dce1ef82aaf..c915407581fb 100644
--- a/gdb/thread.c
+++ b/gdb/thread.c
@@ -775,7 +775,7 @@ thread_change_ptid (process_stratum_target *targ,
   tp = find_thread_ptid (inf, old_ptid);
   tp->ptid = new_ptid;
 
-  gdb::observers::thread_ptid_changed.notify (old_ptid, new_ptid);
+  gdb::observers::thread_ptid_changed.notify (targ, old_ptid, new_ptid);
 }
 
 /* See gdbthread.h.  */
-- 
2.26.2

[PATCH 4/4] gdb: change regcache list to be a map

[Simon Marchi]

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).  It becomes noticeable when
debugging thousands of threads, which is typical with GPU targets.  This
patch replaces the linked list with an std::unordered_multimap, indexed
by (target, ptid).

I originally designed it 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.  Using (target, ptid) as a key allows to do this more
efficiently (see exception below).  If the key of the map was (target,
ptid, arch), we'd have to walk all items of the map.

The lookup (in get_thread_arch_aspace_regcache), walks over all existing
regcaches belonging to this (target, ptid), looking to find the one with
the right arch.  This is ok, as there will be very few regcaches for a
given key (typically one).  Lookups 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 a map lookup 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).  We 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, this is done efficiently
- a non-NULL target and minus_one_ptid: we delete all the entries
  associated to that target, whatever the ptid.  This is the slightly
  annoying case, as we can't easily look up all items having this target
  in their key.  I implemented it by walking the list, which is not
  ideal.

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.

Note: In hash_target_ptid, I am combining hash values from std::hash by
summing them.  I don't think it's ideal, since std::hash is just the
identity function for base types.  But I don't know what would be better
to reduce the change of collisions.  If anybody has a better idea, I'd
be interested.

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 (struct target_ptid): New struct.
	(hash_target_ptid): New struct.
	(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.
	* gdbsupport/ptid.h (hash_ptid): New struct.

Change-Id: Iabb0a1111707936ca111ddb13f3b09efa83d3402
---
 gdb/regcache.c    | 192 ++++++++++++++++++++++++++++++++--------------
 gdbsupport/ptid.h |  16 ++++
 2 files changed, 152 insertions(+), 56 deletions(-)

diff --git a/gdb/regcache.c b/gdb/regcache.c
index fb20250d20f0..eed8a8bde6e5 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,32 +313,73 @@ reg_buffer::assert_regnum (int regnum) const
     gdb_assert (regnum < gdbarch_num_regs (arch ()));
 }
 
-/* Global structure containing the current regcache.  */
+/* Key type for target_ptid_regcache_map.  */
+
+struct target_ptid
+{
+  target_ptid (process_stratum_target *target, ptid_t ptid)
+    : target (target), ptid (ptid)
+  {}
+
+  process_stratum_target *target;
+  ptid_t ptid;
+
+  bool operator== (const target_ptid &other) const
+  {
+    return (this->target == other.target
+	    && this->ptid == other.ptid);
+  }
+};
+
+/* Hash function for target_ptid.  */
+
+struct hash_target_ptid
+{
+  size_t operator() (const target_ptid &val) const
+  {
+    std::hash<long> h_long;
+    hash_ptid h_ptid;
+
+    return h_long ((long) val.target) + h_ptid (val.ptid);
+  }
+};
+
+/* Type to map a (target, ptid) tuple to a regcache.  */
+
+using target_ptid_regcache_map
+  = std::unordered_multimap<target_ptid, regcache *, hash_target_ptid>;
+
+/* 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;
-
-  regcache *new_regcache = new regcache (target, gdbarch, aspace);
+  /* Look up the regcache for this (target, ptid, arch).  */
+  target_ptid key (target, ptid);
+  auto range = regcaches.equal_range (key);
+  for (auto it = range.first; it != range.second; it++)
+    {
+      if (it->second->arch () == arch)
+	return it->second;
+    }
 
-  regcaches.push_front (new_regcache);
+  /* It does not exist, create it.  */
+  regcache *new_regcache = new regcache (target, arch, aspace);
   new_regcache->set_ptid (ptid);
 
+  /* Insert it in the map.  */
+  regcaches.insert (std::make_pair (key, new_regcache));
+
   return new_regcache;
 }
 
@@ -417,10 +458,25 @@ static void
 regcache_thread_ptid_changed (process_stratum_target *target,
 			      ptid_t old_ptid, ptid_t new_ptid)
 {
-  for (auto &regcache : regcaches)
+  /* Find all the regcaches to updates.  */
+  std::vector<regcache *> regcaches_to_update;
+  target_ptid old_key (target, old_ptid);
+  auto range = regcaches.equal_range (old_key);
+  for (auto it = range.first; it != range.second; it++)
+    regcaches_to_update.push_back (it->second);
+
+  /* Remove all entries associated to OLD_KEY.  We could have erased the items
+     in the previous `for`, but it is only safe to erase items while iterating
+     starting with C++14.  */
+  regcaches.erase (old_key);
+
+  /* Update the regcaches' ptid, insert them back in the map with an updated
+     key.  */
+  target_ptid new_key (target, new_ptid);
+  for (regcache *rc : regcaches_to_update)
     {
-      if (regcache->ptid () == old_ptid && regcache->target () == target)
-	regcache->set_ptid (new_ptid);
+      rc->set_ptid (new_ptid);
+      regcaches.insert (std::make_pair (new_key, rc));
     }
 }
 
@@ -438,19 +494,53 @@ 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)
     {
-      struct regcache *regcache = *it;
-      if ((target == nullptr || regcache->target () == target)
-	  && regcache->ptid ().matches (ptid))
-	{
-	  delete regcache;
-	  it = regcaches.erase_after (oit);
-	}
-      else
-	oit = it++;
+      /* 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.  */
+      for (auto pair : regcaches)
+	delete pair.second;
+
+      regcaches.clear ();
     }
+  else if (ptid != minus_one_ptid)
+    {
+      /* Non-NULL target and non-minus_one_ptid, delete all regcaches belonging
+         to this (TARGET, PTID).  */
+      target_ptid key (target, ptid);
+      auto range = regcaches.equal_range (key);
+      for (auto it = range.first; it != range.second; it++)
+	delete it->second;
+
+      regcaches.erase (key);
+    }
+  else
+    {
+       /* Non-NULL target and minus_one_ptid, delete all regcaches associated
+          to this target.
+
+          We unfortunately don't have an efficient way to do this.  Fall back
+          to iterating all items to find all those belonging to TARGET.
+
+          Note that in C++11, it's not safe to erase map entries while
+          iterating, so we keep track of them and delete them at the end.  */
+       std::vector<target_ptid> keys;
+
+       for (auto pair : regcaches)
+	 {
+	   if (pair.second->target () == target)
+	     {
+	       keys.push_back (pair.first);
+	       delete pair.second;
+	     }
+	 }
+
+       for (auto key : keys)
+	 regcaches.erase (key);
+     }
 
   if ((target == nullptr || current_thread_target == target)
       && current_thread_ptid.matches (ptid))
@@ -1431,13 +1521,6 @@ register_dump::dump (ui_file *file)
 
 namespace selftests {
 
-static size_t
-regcaches_size ()
-{
-  return std::distance (regcaches.begin (),
-			  regcaches.end ());
-}
-
 /* Wrapper around get_thread_arch_aspace_regcache that does some self checks.  */
 
 static void
@@ -1457,7 +1540,7 @@ static void
 regcaches_test (void)
 {
   /* It is empty at the start.  */
-  SELF_CHECK (regcaches_size () == 0);
+  SELF_CHECK (regcaches.size () == 0);
 
   ptid_t ptid1 (1), ptid2 (2), ptid3 (3);
 
@@ -1469,52 +1552,52 @@ regcaches_test (void)
   test_get_thread_arch_aspace_regcache (&test_target1, ptid1,
 					target_gdbarch (),
 					NULL);
-  SELF_CHECK (regcaches_size () == 1);
+  SELF_CHECK (regcaches.size () == 1);
 
   /* Get regcache from (target1,ptid2), a new regcache is added to
      REGCACHES.  */
   test_get_thread_arch_aspace_regcache (&test_target1, ptid2,
 					target_gdbarch (),
 					NULL);
-  SELF_CHECK (regcaches_size () == 2);
+  SELF_CHECK (regcaches.size () == 2);
 
   /* Get regcache from (target1,ptid3), a new regcache is added to
      REGCACHES.  */
   test_get_thread_arch_aspace_regcache (&test_target1, ptid3,
 					target_gdbarch (),
 					NULL);
-  SELF_CHECK (regcaches_size () == 3);
+  SELF_CHECK (regcaches.size () == 3);
 
   /* Get regcache from (target1,ptid2) again, nothing is added to
      REGCACHES.  */
   test_get_thread_arch_aspace_regcache (&test_target1, ptid2,
 					target_gdbarch (),
 					NULL);
-  SELF_CHECK (regcaches_size () == 3);
+  SELF_CHECK (regcaches.size () == 3);
 
   /* Get regcache from (target2,ptid2), a new regcache is added to
      REGCACHES, since this time we're using a different target.  */
   test_get_thread_arch_aspace_regcache (&test_target2, ptid2,
 					target_gdbarch (),
 					NULL);
-  SELF_CHECK (regcaches_size () == 4);
+  SELF_CHECK (regcaches.size () == 4);
 
   /* Mark that (target1,ptid2) changed.  The regcache of (target1,
      ptid2) should be removed from REGCACHES.  */
   registers_changed_ptid (&test_target1, ptid2);
-  SELF_CHECK (regcaches_size () == 3);
+  SELF_CHECK (regcaches.size () == 3);
 
   /* Get the regcache from (target2,ptid2) again, confirming the
      registers_changed_ptid call above did not delete it.  */
   test_get_thread_arch_aspace_regcache (&test_target2, ptid2,
 					target_gdbarch (),
 					NULL);
-  SELF_CHECK (regcaches_size () == 3);
+  SELF_CHECK (regcaches.size () == 3);
 
   /* Confirm that marking all regcaches of all targets as changed
      clears REGCACHES.  */
   registers_changed_ptid (nullptr, minus_one_ptid);
-  SELF_CHECK (regcaches_size () == 0);
+  SELF_CHECK (regcaches.size () == 0);
 }
 
 class target_ops_no_register : public test_target_ops
@@ -1847,27 +1930,24 @@ regcache_thread_ptid_changed ()
   get_thread_arch_aspace_regcache (&target1.mock_target, old_ptid, arch, NULL);
   get_thread_arch_aspace_regcache (&target2.mock_target, old_ptid, arch, NULL);
 
-  /* 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)
     {
-      for (regcache *rc : regcaches)
-	{
-	  if (rc->target () == target && rc->ptid () == ptid)
-	    return true;
-	}
+      target_ptid key (target, ptid);
 
-      return false;
+      auto range = regcaches.equal_range (key);
+      return std::distance (range.first, range.second);
     };
 
-  gdb_assert (regcaches_size () == 2);
-  gdb_assert (regcache_exists (&target1.mock_target, old_ptid));
-  gdb_assert (regcache_exists (&target2.mock_target, old_ptid));
+  gdb_assert (regcaches.size () == 2);
+  gdb_assert (regcache_count (&target1.mock_target, old_ptid) == 1);
+  gdb_assert (regcache_count (&target2.mock_target, old_ptid) == 1);
 
   thread_change_ptid (&target1.mock_target, old_ptid, new_ptid);
 
-  gdb_assert (regcaches_size () == 2);
-  gdb_assert (regcache_exists (&target1.mock_target, new_ptid));
-  gdb_assert (regcache_exists (&target2.mock_target, old_ptid));
+  gdb_assert (regcaches.size () == 2);
+  gdb_assert (regcache_count (&target1.mock_target, new_ptid) == 1);
+  gdb_assert (regcache_count (&target2.mock_target, old_ptid) == 1);
 }
 
 } // namespace selftests
diff --git a/gdbsupport/ptid.h b/gdbsupport/ptid.h
index ef52d5551260..a528312bad5e 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 @@ class ptid_t
   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;
-- 
2.26.2

Re: [PATCH 1/4] gdb: rename regcache::current_regcache to regcache::regcaches

[Pedro Alves]

Hi!

On 7/20/20 9:40 PM, Simon Marchi via Gdb-patches wrote:
> The name `current_regcache` for the list of currently-existing regcaches
> sounds wrong.  The name is singular, but it holds multiple regcaches, so
> it could at least be `current_regcaches`.
> 
> But in other places in GDB, "current" usually means "the object we are
> working with right now".  For example, we swap the "current thread" when
> we want to operate on a given thread.  This is not the case here, this
> variable just holds all regcaches that exist at any given time, not "the
> regcache we are working with right now".

It used to hold a single regcache, and then it was made a list:

 https://sourceware.org/pipermail/gdb-patches/2009-June/065986.html

... but the name wasn't changed.

> 
> So, I think calling it `regcaches` is better.  I also considered
> `regcache_list`, but a subsequent patch will make it a map and not a
> list, so it would sound wrong again.  `regcaches` sounds right for any
> collection of regcache, whatever the type.
> 
> Rename a few other things that were related to this `current_regcache`
> field.  Note that there is a `get_current_regcache` function, which
> returns the regcache of the current thread.  That one is fine, because
> it returns the regcache for the current thread.
> 
> gdb/ChangeLog:
> 
> 	* regcache.h (class regcache) <current_regcache>: Rename to...
> 	<regcaches>: ... this.  Move doc here.
> 	* regcache.c (regcache::current_regcache) Rename to...
> 	(regcache::regcaches): ... this.  Move doc to header.
> 	(get_thread_arch_aspace_regcache): Update.
> 	(regcache::regcache_thread_ptid_changed): Update.
> 	(registers_changed_ptid): Update.
> 	(class regcache_access) <current_regcache_size>: Rename to...
> 	<regcaches_size>: ... this.
> 	(current_regcache_test): Rename to...
> 	(regcaches_test): ... this.
> 	(_initialize_regcache): Update.

OK.

Thanks,
Pedro Alves

Re: [PATCH 2/4] gdb: move regcache::regcaches to regcache.c

[Pedro Alves]

On 7/20/20 9:40 PM, Simon Marchi via Gdb-patches wrote:
> I don't really understand why `regcache_thread_ptid_changed` is a static
> method of `struct regcache` instead of being a static free function in
> regcache.c.  And I don't understand why `current_regcache` is a static
> member of `struct regcache` instead of being a static global in
> regcache.c.  It's not wrong per-se, but there's no other place where we
> do it like this in GDB (as far as I remember) and it just exposes things
> unnecessarily in the .h.

current_regcache was made a static member of struct regcache in:

 commit e521e87e8514b9d3497208b70bcd067f132c58ed
 Author:     Yao Qi <yao.qi@linaro.org>
 AuthorDate: Wed May 24 22:15:23 2017 +0100

    Move current_regcache to regcache::current_regcache

 https://sourceware.org/pipermail/gdb-patches/2017-May/140583.html

which was needed for:

 commit b77b02a5ca5a021ee8b5e5453e8843447d1132b2
 Author:     Yao Qi <yao.qi@linaro.org>
 AuthorDate: Wed May 24 22:15:23 2017 +0100

    Add unit test to gdbarch methods register_to_value and value_to_register

 https://sourceware.org/pipermail/gdb-patches/2017-May/140589.html

But then later I redesigned the mocking environment:

 commit 55b11ddf16b97b9c50ed480bc9da8b3e1c6c4198
 Author:     Pedro Alves <palves@redhat.com>
 AuthorDate: Wed Oct 4 18:21:09 2017 +0100

    Redesign mock environment for gdbarch selftests

 https://sourceware.org/legacy-ml/gdb-patches/2017-10/msg00022.html

... and that got rid of the need to expose current_regcache.

> 
> Move them to be just static in regcache.c.  As a result,
> registers_changed_ptid doesn't need to be friend of the regcache class
> anymore.
> 
> Removing the include of forward_list in regcache.h showed that we were
> missing an include for it in dwarf2/index-write.c, record-btrace.c and
> sparc64-tdep.c.
> 
> gdb/ChangeLog:
> 
> 	* regcache.h (class regcache): Remove friend
> 	registers_changed_ptid.
> 	<regcache_thread_ptid_changed>: Remove.
> 	<regcaches>: Remove.
> 	* regcache.c (regcache::regcaches): Rename to...
> 	(regcaches): ... this.  Make static.
> 	(get_thread_arch_aspace_regcache): Update.
> 	(regcache::regcache_thread_ptid_changed): Rename to...
> 	(regcache_thread_ptid_changed): ... this.  Update.
> 	(class regcache_access): Remove.
> 	(regcaches_test): Update.
> 	(_initialize_regcache): Update.
> 	* sparc64-tdep.c, dwarf2/index-write.c, record-btrace.c: Include
> 	<forward_list>.
> 

OK.

Thanks,
Pedro Alves

Re: [PATCH 3/4] gdb: pass target to thread_ptid_changed observable

[Pedro Alves]

On 7/20/20 9:41 PM, Simon Marchi via Gdb-patches wrote:
> I noticed what I think is a potential bug.  I did not observe it nor was
> I able to reproduce it using actual debugging.  It's quite unlikely,
> because it involves multi-target and ptid clashes.  I added selftests
> that demonstrate it though.

Yes, it's definitely a bug.  Thanks for fixing this.

> 
> The thread_ptid_changed observer says that thread with OLD_PTID now has
> NEW_PTID.  Now, if for some reason we happen to have two targets
> defining a thread with OLD_PTID, the observers don't know which thread
> this is about.
> 
> regcache::regcache_thread_ptid_changed changes all regcaches with
> OLD_PTID.  If there is a regcache for a thread with ptid OLD_PTID, but
> that belongs to a different target, this regcache will be erroneously
> changed.
> 
> Similarly, infrun_thread_ptid_changed updates inferior_ptid if
> inferior_ptid matches OLD_PTID.  But if inferior_ptid currently refers
> not to the thread is being changed, but to a thread with the same ptid
> belonging to a different target, then inferior_ptid will erroneously be
> changed.

I think the latter is unlikely to be a bug in practice, because inferior_ptid
will be pointing at a thread of the current target, and thread_change_ptid
will be called in the context of the same target.  But it doesn't hurt to
make it explicit, of course.

> 
> This patch adds a `process_stratum_target *` parameter to the
> `thread_ptid_changed` observable and makes the two observers use it.
> Tests for both are added, which would fail if the corresponding fix
> wasn't done.
> 
> gdb/ChangeLog:
> 
> 	* observable.h (thread_ptid_changed): Add parameter
> 	`process_stratum_target *`.
> 	* infrun.c (infrun_thread_ptid_changed): Add parameter
> 	`process_stratum_target *` and use it.
> 	(selftests): New namespace.
> 	(infrun_thread_ptid_changed): New function.
> 	(_initialize_infrun): Register selftest.
> 	* regcache.c (regcache_thread_ptid_changed): Add parameter
> 	`process_stratum_target *` and use it.
> 	(regcache_thread_ptid_changed): New function.
> 	(_initialize_regcache): Register selftest.
> 	* thread.c (thread_change_ptid): Pass target to
> 	thread_ptid_changed observable.
> 
> Change-Id: I0599e61224b6d154a7b55088a894cb88298c3c71
> ---
>  gdb/infrun.c     | 78 ++++++++++++++++++++++++++++++++++++++++++++++--
>  gdb/observable.h |  6 ++--
>  gdb/regcache.c   | 59 ++++++++++++++++++++++++++++++++++--
>  gdb/thread.c     |  2 +-
>  4 files changed, 138 insertions(+), 7 deletions(-)
> 
> diff --git a/gdb/infrun.c b/gdb/infrun.c
> index 31266109a6d3..3fbe45efb8ca 100644
> --- a/gdb/infrun.c
> +++ b/gdb/infrun.c
> @@ -67,6 +67,9 @@
>  #include "gdbsupport/gdb_select.h"
>  #include <unordered_map>
>  #include "async-event.h"
> +#include "gdbsupport/selftest.h"
> +#include "scoped-mock-context.h"
> +#include "test-target.h"
>  
>  /* Prototypes for local functions */
>  
> @@ -2068,9 +2071,11 @@ start_step_over (void)
>  /* Update global variables holding ptids to hold NEW_PTID if they were
>     holding OLD_PTID.  */
>  static void
> -infrun_thread_ptid_changed (ptid_t old_ptid, ptid_t new_ptid)
> +infrun_thread_ptid_changed (process_stratum_target *target,
> +			    ptid_t old_ptid, ptid_t new_ptid)
>  {
> -  if (inferior_ptid == old_ptid)
> +  if (inferior_ptid == old_ptid
> +      && current_inferior ()->process_target () == target)
>      inferior_ptid = new_ptid;
>  }
>  
> @@ -9467,6 +9472,70 @@ infrun_async_inferior_event_handler (gdb_client_data data)
>    inferior_event_handler (INF_REG_EVENT);
>  }
>  
> +namespace selftests
> +{
> +
> +/* Verify that when two threads with the same ptid exist (from two different
> +   targets) and one of them changes ptid, we only update inferior_ptid if
> +   it is appropriate.  */
> +
> +static void
> +infrun_thread_ptid_changed ()
> +{
> +  gdbarch *arch = current_inferior ()->gdbarch;
> +
> +  /* The thread which inferior_ptid represents changes ptid.  */
> +  {
> +    scoped_restore_current_pspace_and_thread restore;
> +
> +    scoped_mock_context<test_target_ops> target1 (arch);
> +    scoped_mock_context<test_target_ops> target2 (arch);
> +    target2.mock_inferior.next = &target1.mock_inferior;
> +
> +    ptid_t old_ptid (111, 222);
> +    ptid_t new_ptid (111, 333);
> +
> +    target1.mock_inferior.pid = old_ptid.pid ();
> +    target1.mock_thread.ptid = old_ptid;
> +    target2.mock_inferior.pid = old_ptid.pid ();
> +    target2.mock_thread.ptid = old_ptid;
> +
> +    auto restore_inferior_ptid = make_scoped_restore (&inferior_ptid, old_ptid);
> +    set_current_inferior (&target1.mock_inferior);
> +
> +    thread_change_ptid (&target1.mock_target, old_ptid, new_ptid);
> +
> +    gdb_assert (inferior_ptid == new_ptid);
> +  }
> +
> +  /* A thread with the same ptid as inferior_ptid, but from another target,
> +     changes ptid.  */
> +  {
> +    scoped_restore_current_pspace_and_thread restore;
> +
> +    scoped_mock_context<test_target_ops> target1 (arch);
> +    scoped_mock_context<test_target_ops> target2 (arch);
> +    target2.mock_inferior.next = &target1.mock_inferior;
> +
> +    ptid_t old_ptid (111, 222);
> +    ptid_t new_ptid (111, 333);
> +
> +    target1.mock_inferior.pid = old_ptid.pid ();
> +    target1.mock_thread.ptid = old_ptid;
> +    target2.mock_inferior.pid = old_ptid.pid ();
> +    target2.mock_thread.ptid = old_ptid;
> +
> +    auto restore_inferior_ptid = make_scoped_restore (&inferior_ptid, old_ptid);
> +    set_current_inferior (&target2.mock_inferior);
> +
> +    thread_change_ptid (&target1.mock_target, old_ptid, new_ptid);
> +
> +    gdb_assert (inferior_ptid == old_ptid);
> +  }
> +}
> +
> +} /* namespace selftests */
> +
>  void _initialize_infrun ();
>  void
>  _initialize_infrun ()
> @@ -9768,4 +9837,9 @@ or signalled."),
>  			   show_observer_mode,
>  			   &setlist,
>  			   &showlist);
> +
> +#if GDB_SELF_TEST
> +  selftests::register_test ("infrun_thread_ptid_changed",
> +			    selftests::infrun_thread_ptid_changed);
> +#endif
>  }
> diff --git a/gdb/observable.h b/gdb/observable.h
> index 070cf0f18e51..da0a9b12f74c 100644
> --- a/gdb/observable.h
> +++ b/gdb/observable.h
> @@ -27,6 +27,7 @@ struct so_list;
>  struct objfile;
>  struct thread_info;
>  struct inferior;
> +struct process_stratum_target;
>  struct trace_state_variable;
>  
>  namespace gdb
> @@ -165,8 +166,9 @@ extern observable<struct gdbarch */* newarch */> architecture_changed;
>  
>  /* The thread's ptid has changed.  The OLD_PTID parameter specifies
>     the old value, and NEW_PTID specifies the new value.  */
> -extern observable<ptid_t /* old_ptid */, ptid_t /* new_ptid */>
> -    thread_ptid_changed;
> +extern observable<process_stratum_target * /* target */,
> +		  ptid_t /* old_ptid */, ptid_t /* new_ptid */>
> +  thread_ptid_changed;
>  
>  /* The inferior INF has been added to the list of inferiors.  At
>     this point, it might not be associated with any process.  */
> diff --git a/gdb/regcache.c b/gdb/regcache.c
> index 54354fe2c161..fb20250d20f0 100644
> --- a/gdb/regcache.c
> +++ b/gdb/regcache.c
> @@ -414,11 +414,12 @@ regcache_observer_target_changed (struct target_ops *target)
>  
>  /* Update regcaches related to OLD_PTID to now use NEW_PTID.  */
>  static void
> -regcache_thread_ptid_changed (ptid_t old_ptid, ptid_t new_ptid)
> +regcache_thread_ptid_changed (process_stratum_target *target,
> +			      ptid_t old_ptid, ptid_t new_ptid)
>  {
>    for (auto &regcache : regcaches)
>      {
> -      if (regcache->ptid () == old_ptid)
> +      if (regcache->ptid () == old_ptid && regcache->target () == target)
>  	regcache->set_ptid (new_ptid);
>      }
>  }
> @@ -1817,6 +1818,58 @@ cooked_write_test (struct gdbarch *gdbarch)
>      }
>  }
>  
> +/* Verify that when two threads with the same ptid exist (from two different
> +   targets) and one of them changes ptid, we only update the appropriate
> +   regcaches.  */
> +
> +static void
> +regcache_thread_ptid_changed ()
> +{
> +  /* Any arch will do.  */
> +  gdbarch *arch = current_inferior ()->gdbarch;
> +
> +  /* Prepare two targets with one thread each, with the same ptid.  */
> +  scoped_mock_context<test_target_ops> target1 (arch);
> +  scoped_mock_context<test_target_ops> target2 (arch);
> +  target2.mock_inferior.next = &target1.mock_inferior;
> +
> +  ptid_t old_ptid (111, 222);
> +  ptid_t new_ptid (111, 333);
> +
> +  target1.mock_inferior.pid = old_ptid.pid ();
> +  target1.mock_thread.ptid = old_ptid;
> +  target2.mock_inferior.pid = old_ptid.pid ();
> +  target2.mock_thread.ptid = old_ptid;
> +
> +  gdb_assert (regcaches.empty ());

This will fail if you debug something, e.g., run to main,
and then do:

 (gdb) maint selftest regcache_thread_ptid_changed

Maybe call registers_changed() before ?

Actually trying that made me notice that I completely missed
making cooked_write_test in 236ef0346d88efffd1ca1da1a5d80724cb145660 ...
Fixing that would get rid of these fails:

 Self test failed: arch i386: target already pushed
 ...

> +
> +  /* Populate the regcaches container.  */
> +  get_thread_arch_aspace_regcache (&target1.mock_target, old_ptid, arch, NULL);
> +  get_thread_arch_aspace_regcache (&target2.mock_target, old_ptid, arch, NULL);

nullptr? ;-)

> +
> +  /* Return whether a regcache for (TARGET, PTID) exists in REGCACHES.  */
> +  auto regcache_exists = [] (process_stratum_target *target, ptid_t ptid)
> +    {
> +      for (regcache *rc : regcaches)
> +	{
> +	  if (rc->target () == target && rc->ptid () == ptid)
> +	    return true;
> +	}
> +
> +      return false;
> +    };
> +
> +  gdb_assert (regcaches_size () == 2);
> +  gdb_assert (regcache_exists (&target1.mock_target, old_ptid));
> +  gdb_assert (regcache_exists (&target2.mock_target, old_ptid));

For completeness, I'd add:

  gdb_assert (!regcache_exists (&target1.mock_target, new_ptid));
  gdb_assert (!regcache_exists (&target2.mock_target, new_ptid));

> +
> +  thread_change_ptid (&target1.mock_target, old_ptid, new_ptid);
> +
> +  gdb_assert (regcaches_size () == 2);
> +  gdb_assert (regcache_exists (&target1.mock_target, new_ptid));
> +  gdb_assert (regcache_exists (&target2.mock_target, old_ptid));

Similarly here.

> +}
> +
>  } // namespace selftests
>  #endif /* GDB_SELF_TEST */
>  
> @@ -1840,5 +1893,7 @@ _initialize_regcache ()
>  					 selftests::cooked_read_test);
>    selftests::register_test_foreach_arch ("regcache::cooked_write_test",
>  					 selftests::cooked_write_test);
> +  selftests::register_test ("regcache_thread_ptid_changed",
> +			    selftests::regcache_thread_ptid_changed);
>  #endif
>  }
> diff --git a/gdb/thread.c b/gdb/thread.c
> index 4dce1ef82aaf..c915407581fb 100644
> --- a/gdb/thread.c
> +++ b/gdb/thread.c
> @@ -775,7 +775,7 @@ thread_change_ptid (process_stratum_target *targ,
>    tp = find_thread_ptid (inf, old_ptid);
>    tp->ptid = new_ptid;
>  
> -  gdb::observers::thread_ptid_changed.notify (old_ptid, new_ptid);
> +  gdb::observers::thread_ptid_changed.notify (targ, old_ptid, new_ptid);
>  }
>  
>  /* See gdbthread.h.  */
> 

Otherwise LGTM.

Thanks,
Pedro Alves

Re: [PATCH 4/4] gdb: change regcache list to be a map

[Pedro Alves]

[-- Attachment #1: Type: text/plain, Size: 19696 bytes --]

On 7/20/20 9:41 PM, Simon Marchi via Gdb-patches wrote:
> 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).  It becomes noticeable when
> debugging thousands of threads, which is typical with GPU targets.  This
> patch replaces the linked list with an std::unordered_multimap, indexed
> by (target, ptid).
> 
> I originally designed it 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.  Using (target, ptid) as a key allows to do this more
> efficiently (see exception below).  If the key of the map was (target,
> ptid, arch), we'd have to walk all items of the map.
> 
> The lookup (in get_thread_arch_aspace_regcache), walks over all existing
> regcaches belonging to this (target, ptid), looking to find the one with
> the right arch.  This is ok, as there will be very few regcaches for a
> given key (typically one).  Lookups 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 a map lookup 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).  We 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, this is done efficiently
> - a non-NULL target and minus_one_ptid: we delete all the entries
>   associated to that target, whatever the ptid.  This is the slightly
>   annoying case, as we can't easily look up all items having this target
>   in their key.  I implemented it by walking the list, which is not
>   ideal.

Given the last case, did you consider using a two-level map instead?

  using ptid_regcache_map 
    = std::unordered_multimap<ptid_t, regcache *>;

  using target_ptid_regcache_map 
    = std::unordered_map<process_stratum_target *, ptid_regcache_map>;

  static target_ptid_regcache_map regcaches;

The result for registers_changed_ptid would be:

 - NULL target and minus_one_ptid: we delete all the REGCACHES entries,

 - NULL target and non-minus_one_ptid: invalid (checked by assert)

 - non-NULL target and non-minus_one_ptid: we lookup the target
   in REGCACHES, and then delete all the entries in that map
   associated to that ptid.

 - a non-NULL target and minus_one_ptid: we delete the map entry
   in REGCACHES associated to that target.

Looking up a regcache does two map lookups instead of one, but
that is 2x amortized O(1), so should be a constant hit.

I gave this a try, to see how feasible it would be.  See attached
patches on top of yours (the first two address comments I'll make below).
I've also put these in the users/palves/regcache-map branch on
sourceware.org.

I did not run performance tests, though.  It may be that in
registers_changed_ptid, it would be more efficient to
not clear the first level map entry for a given target (i.e.,
destroy the second level map object completely), but instead
clear the second level map entry.  I.e., avoid destroying the
unordered_multimap for a given target, only to recreate it soon
enough.  But I kept it simple in case that isn't noticeable.

A similar two-level data structure would be to put an instance of:

  using ptid_regcache_map 
    = std::unordered_multimap<ptid_t, regcache *>;

in process_stratum_target directly.

IOW, target-connection.c:process_targets has a list of open targets,
which could be used to walk over all targets in the
"NULL target and minus_one_ptid" scenario.

> 
> 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.
> 
> Note: In hash_target_ptid, I am combining hash values from std::hash by
> summing them.  I don't think it's ideal, since std::hash is just the
> identity function for base types.  But I don't know what would be better
> to reduce the change of collisions.  If anybody has a better idea, I'd
> be interested.

I'd maybe look in some kernel sources, e.g., Linux or BSD, what they
use as hash function for pids.

> 
> 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 (struct target_ptid): New struct.
> 	(hash_target_ptid): New struct.
> 	(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.
> 	* gdbsupport/ptid.h (hash_ptid): New struct.
> 
> Change-Id: Iabb0a1111707936ca111ddb13f3b09efa83d3402
> ---
>  gdb/regcache.c    | 192 ++++++++++++++++++++++++++++++++--------------
>  gdbsupport/ptid.h |  16 ++++
>  2 files changed, 152 insertions(+), 56 deletions(-)
> 
> diff --git a/gdb/regcache.c b/gdb/regcache.c
> index fb20250d20f0..eed8a8bde6e5 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,32 +313,73 @@ reg_buffer::assert_regnum (int regnum) const
>      gdb_assert (regnum < gdbarch_num_regs (arch ()));
>  }
>  
> -/* Global structure containing the current regcache.  */
> +/* Key type for target_ptid_regcache_map.  */
> +
> +struct target_ptid
> +{
> +  target_ptid (process_stratum_target *target, ptid_t ptid)
> +    : target (target), ptid (ptid)
> +  {}
> +
> +  process_stratum_target *target;
> +  ptid_t ptid;
> +
> +  bool operator== (const target_ptid &other) const
> +  {
> +    return (this->target == other.target
> +	    && this->ptid == other.ptid);
> +  }
> +};
> +
> +/* Hash function for target_ptid.  */
> +
> +struct hash_target_ptid
> +{
> +  size_t operator() (const target_ptid &val) const
> +  {
> +    std::hash<long> h_long;
> +    hash_ptid h_ptid;
> +
> +    return h_long ((long) val.target) + h_ptid (val.ptid);

Note that on 64-bit Windows, long is 32-bit, so pointers don't
fit.  It just means you're only hashing half the bits.
I wonder whether using libiberty's htab_hash_pointer would be
a good idea here.

> +  }
> +};
> +
> +/* Type to map a (target, ptid) tuple to a regcache.  */
> +
> +using target_ptid_regcache_map
> +  = std::unordered_multimap<target_ptid, regcache *, hash_target_ptid>;
> +
> +/* 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;
> -
> -  regcache *new_regcache = new regcache (target, gdbarch, aspace);
> +  /* Look up the regcache for this (target, ptid, arch).  */
> +  target_ptid key (target, ptid);
> +  auto range = regcaches.equal_range (key);
> +  for (auto it = range.first; it != range.second; it++)
> +    {
> +      if (it->second->arch () == arch)
> +	return it->second;
> +    }
>  
> -  regcaches.push_front (new_regcache);
> +  /* It does not exist, create it.  */
> +  regcache *new_regcache = new regcache (target, arch, aspace);
>    new_regcache->set_ptid (ptid);
>  
> +  /* Insert it in the map.  */
> +  regcaches.insert (std::make_pair (key, new_regcache));
> +
>    return new_regcache;
>  }
>  
> @@ -417,10 +458,25 @@ static void
>  regcache_thread_ptid_changed (process_stratum_target *target,
>  			      ptid_t old_ptid, ptid_t new_ptid)
>  {
> -  for (auto &regcache : regcaches)
> +  /* Find all the regcaches to updates.  */

typo: to update.

> +  std::vector<regcache *> regcaches_to_update;
> +  target_ptid old_key (target, old_ptid);
> +  auto range = regcaches.equal_range (old_key);
> +  for (auto it = range.first; it != range.second; it++)
> +    regcaches_to_update.push_back (it->second);
> +
> +  /* Remove all entries associated to OLD_KEY.  We could have erased the items
> +     in the previous `for`, but it is only safe to erase items while iterating
> +     starting with C++14.  */
> +  regcaches.erase (old_key);

I don't think that's really true in practice.  The idiom used pretty
much by everyone is:

  for (auto it = range.first; it != range.second;)
    {
      regcaches_to_update.push_back (it->second);
      it = regcaches.erase (it);
    }

Note that even the resolution of the C++ issue at:

 https://wg21.cmeerw.net/lwg/issue2356 

says:

 "not that any actual implementation does that, anyway"

There's no need to be super pedantic wrt to an issue
that no compiler is going to miscompile.

See here as well:
 https://stackoverflow.com/questions/25047241/c11-is-it-safe-to-remove-individual-elements-from-stdunordered-map-while-it

And then, given we know that there are no entries for
new_ptid in the map, I think we could instead do it all in
one iteration, like:

  target_ptid old_key (target, old_ptid);
  target_ptid new_key (target, new_ptid);

  auto range = regcaches.equal_range (old_key);
  for (auto it = range.first; it != range.second;)
    {
      regcache *rc = it->second;
      rc->set_ptid (new_ptid);

      /* Remove old before inserting new, to avoid rehashing, which
         would invalidate iterators.  */
      it = regcaches.erase (it);
      regcaches.insert (std::make_pair (new_key, rc));
    }

> +
> +  /* Update the regcaches' ptid, insert them back in the map with an updated
> +     key.  */
> +  target_ptid new_key (target, new_ptid);
> +  for (regcache *rc : regcaches_to_update)
>      {
> -      if (regcache->ptid () == old_ptid && regcache->target () == target)
> -	regcache->set_ptid (new_ptid);
> +      rc->set_ptid (new_ptid);
> +      regcaches.insert (std::make_pair (new_key, rc));
>      }
>  }
>  
> @@ -438,19 +494,53 @@ 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)
>      {
> -      struct regcache *regcache = *it;
> -      if ((target == nullptr || regcache->target () == target)
> -	  && regcache->ptid ().matches (ptid))
> -	{
> -	  delete regcache;
> -	  it = regcaches.erase_after (oit);
> -	}
> -      else
> -	oit = it++;
> +      /* 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.  */
> +      for (auto pair : regcaches)
> +	delete pair.second;

We could store a std::unique_ptr<regcache> in the map instead
to avoid all these manual deletes.

> +
> +      regcaches.clear ();
>      }
> +  else if (ptid != minus_one_ptid)
> +    {
> +      /* Non-NULL target and non-minus_one_ptid, delete all regcaches belonging
> +         to this (TARGET, PTID).  */
> +      target_ptid key (target, ptid);
> +      auto range = regcaches.equal_range (key);
> +      for (auto it = range.first; it != range.second; it++)
> +	delete it->second;

Like this one.

> +
> +      regcaches.erase (key);

Here as well could do:

      for (auto it = range.first; it != range.second;)
        {
	  delete it->second;
	  it = regcaches.erase (it);
        }

> +    }
> +  else
> +    {
> +       /* Non-NULL target and minus_one_ptid, delete all regcaches associated
> +          to this target.
> +
> +          We unfortunately don't have an efficient way to do this.  Fall back
> +          to iterating all items to find all those belonging to TARGET.
> +
> +          Note that in C++11, it's not safe to erase map entries while
> +          iterating, so we keep track of them and delete them at the end.  */

Here as well.

> +       std::vector<target_ptid> keys;
> +
> +       for (auto pair : regcaches)
> +	 {
> +	   if (pair.second->target () == target)
> +	     {
> +	       keys.push_back (pair.first);
> +	       delete pair.second;
> +	     }
> +	 }
> +
> +       for (auto key : keys)
> +	 regcaches.erase (key);
> +     }
>  
>    if ((target == nullptr || current_thread_target == target)
>        && current_thread_ptid.matches (ptid))
> @@ -1431,13 +1521,6 @@ register_dump::dump (ui_file *file)
>  
>  namespace selftests {
>  
> -static size_t
> -regcaches_size ()
> -{
> -  return std::distance (regcaches.begin (),
> -			  regcaches.end ());
> -}
> -
>  /* Wrapper around get_thread_arch_aspace_regcache that does some self checks.  */
>  
>  static void
> @@ -1457,7 +1540,7 @@ static void
>  regcaches_test (void)
>  {
>    /* It is empty at the start.  */
> -  SELF_CHECK (regcaches_size () == 0);
> +  SELF_CHECK (regcaches.size () == 0);
>  
>    ptid_t ptid1 (1), ptid2 (2), ptid3 (3);
>  
> @@ -1469,52 +1552,52 @@ regcaches_test (void)
>    test_get_thread_arch_aspace_regcache (&test_target1, ptid1,
>  					target_gdbarch (),
>  					NULL);
> -  SELF_CHECK (regcaches_size () == 1);
> +  SELF_CHECK (regcaches.size () == 1);
>  
>    /* Get regcache from (target1,ptid2), a new regcache is added to
>       REGCACHES.  */
>    test_get_thread_arch_aspace_regcache (&test_target1, ptid2,
>  					target_gdbarch (),
>  					NULL);
> -  SELF_CHECK (regcaches_size () == 2);
> +  SELF_CHECK (regcaches.size () == 2);
>  
>    /* Get regcache from (target1,ptid3), a new regcache is added to
>       REGCACHES.  */
>    test_get_thread_arch_aspace_regcache (&test_target1, ptid3,
>  					target_gdbarch (),
>  					NULL);
> -  SELF_CHECK (regcaches_size () == 3);
> +  SELF_CHECK (regcaches.size () == 3);
>  
>    /* Get regcache from (target1,ptid2) again, nothing is added to
>       REGCACHES.  */
>    test_get_thread_arch_aspace_regcache (&test_target1, ptid2,
>  					target_gdbarch (),
>  					NULL);
> -  SELF_CHECK (regcaches_size () == 3);
> +  SELF_CHECK (regcaches.size () == 3);
>  
>    /* Get regcache from (target2,ptid2), a new regcache is added to
>       REGCACHES, since this time we're using a different target.  */
>    test_get_thread_arch_aspace_regcache (&test_target2, ptid2,
>  					target_gdbarch (),
>  					NULL);
> -  SELF_CHECK (regcaches_size () == 4);
> +  SELF_CHECK (regcaches.size () == 4);
>  
>    /* Mark that (target1,ptid2) changed.  The regcache of (target1,
>       ptid2) should be removed from REGCACHES.  */
>    registers_changed_ptid (&test_target1, ptid2);
> -  SELF_CHECK (regcaches_size () == 3);
> +  SELF_CHECK (regcaches.size () == 3);
>  
>    /* Get the regcache from (target2,ptid2) again, confirming the
>       registers_changed_ptid call above did not delete it.  */
>    test_get_thread_arch_aspace_regcache (&test_target2, ptid2,
>  					target_gdbarch (),
>  					NULL);
> -  SELF_CHECK (regcaches_size () == 3);
> +  SELF_CHECK (regcaches.size () == 3);
>  
>    /* Confirm that marking all regcaches of all targets as changed
>       clears REGCACHES.  */
>    registers_changed_ptid (nullptr, minus_one_ptid);
> -  SELF_CHECK (regcaches_size () == 0);
> +  SELF_CHECK (regcaches.size () == 0);
>  }
>  
>  class target_ops_no_register : public test_target_ops
> @@ -1847,27 +1930,24 @@ regcache_thread_ptid_changed ()
>    get_thread_arch_aspace_regcache (&target1.mock_target, old_ptid, arch, NULL);
>    get_thread_arch_aspace_regcache (&target2.mock_target, old_ptid, arch, NULL);
>  
> -  /* 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)
>      {
> -      for (regcache *rc : regcaches)
> -	{
> -	  if (rc->target () == target && rc->ptid () == ptid)
> -	    return true;
> -	}
> +      target_ptid key (target, ptid);
>  
> -      return false;
> +      auto range = regcaches.equal_range (key);
> +      return std::distance (range.first, range.second);
>      };
>  
> -  gdb_assert (regcaches_size () == 2);
> -  gdb_assert (regcache_exists (&target1.mock_target, old_ptid));
> -  gdb_assert (regcache_exists (&target2.mock_target, old_ptid));
> +  gdb_assert (regcaches.size () == 2);
> +  gdb_assert (regcache_count (&target1.mock_target, old_ptid) == 1);
> +  gdb_assert (regcache_count (&target2.mock_target, old_ptid) == 1);
>  
>    thread_change_ptid (&target1.mock_target, old_ptid, new_ptid);
>  
> -  gdb_assert (regcaches_size () == 2);
> -  gdb_assert (regcache_exists (&target1.mock_target, new_ptid));
> -  gdb_assert (regcache_exists (&target2.mock_target, old_ptid));
> +  gdb_assert (regcaches.size () == 2);
> +  gdb_assert (regcache_count (&target1.mock_target, new_ptid) == 1);
> +  gdb_assert (regcache_count (&target2.mock_target, old_ptid) == 1);
>  }
>  
>  } // namespace selftests
> diff --git a/gdbsupport/ptid.h b/gdbsupport/ptid.h
> index ef52d5551260..a528312bad5e 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 @@ class ptid_t
>    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;
> 

Thanks,
Pedro Alves

[-- Attachment #2: 0001-no-std-vector.patch --]
[-- Type: text/x-patch, Size: 2998 bytes --]

From 3d992e83fc36296fd9ab8f43d24a607996468bd1 Mon Sep 17 00:00:00 2001
From: Pedro Alves <pedro@palves.net>
Date: Fri, 24 Jul 2020 02:06:39 +0100
Subject: [PATCH 1/3] no std::vector

---
 gdb/regcache.c | 39 +++++++++++++--------------------------
 1 file changed, 13 insertions(+), 26 deletions(-)

diff --git a/gdb/regcache.c b/gdb/regcache.c
index eed8a8bde6e..2ddbcd372a2 100644
--- a/gdb/regcache.c
+++ b/gdb/regcache.c
@@ -458,24 +458,18 @@ static void
 regcache_thread_ptid_changed (process_stratum_target *target,
 			      ptid_t old_ptid, ptid_t new_ptid)
 {
-  /* Find all the regcaches to updates.  */
-  std::vector<regcache *> regcaches_to_update;
   target_ptid old_key (target, old_ptid);
-  auto range = regcaches.equal_range (old_key);
-  for (auto it = range.first; it != range.second; it++)
-    regcaches_to_update.push_back (it->second);
-
-  /* Remove all entries associated to OLD_KEY.  We could have erased the items
-     in the previous `for`, but it is only safe to erase items while iterating
-     starting with C++14.  */
-  regcaches.erase (old_key);
-
-  /* Update the regcaches' ptid, insert them back in the map with an updated
-     key.  */
   target_ptid new_key (target, new_ptid);
-  for (regcache *rc : regcaches_to_update)
+
+  auto range = regcaches.equal_range (old_key);
+  for (auto it = range.first; it != range.second;)
     {
+      regcache *rc = it->second;
       rc->set_ptid (new_ptid);
+
+      /* Remove old before inserting new, to avoid rehashing, which
+         would invalidate iterators.  */
+      it = regcaches.erase (it);
       regcaches.insert (std::make_pair (new_key, rc));
     }
 }
@@ -523,23 +517,16 @@ registers_changed_ptid (process_stratum_target *target, ptid_t ptid)
           to this target.
 
           We unfortunately don't have an efficient way to do this.  Fall back
-          to iterating all items to find all those belonging to TARGET.
+          to iterating all items to find all those belonging to TARGET.  */
 
-          Note that in C++11, it's not safe to erase map entries while
-          iterating, so we keep track of them and delete them at the end.  */
-       std::vector<target_ptid> keys;
-
-       for (auto pair : regcaches)
+       for (auto it = regcaches.begin (); it != regcaches.end ();)
 	 {
-	   if (pair.second->target () == target)
+	   if (it->second->target () == target)
 	     {
-	       keys.push_back (pair.first);
-	       delete pair.second;
+	       delete it->second;
+	       it = regcaches.erase (it);
 	     }
 	 }
-
-       for (auto key : keys)
-	 regcaches.erase (key);
      }
 
   if ((target == nullptr || current_thread_target == target)

base-commit: 4b495c31c14087e851662e790e4ca12bce37dab1
prerequisite-patch-id: 0f6d344d7b55ebdfdb8d2f500ffbee89aac00bab
prerequisite-patch-id: 2075fdb60412fbf24a74b15a5d7c9ae9e7c24c79
prerequisite-patch-id: 5da77748b9d245ea2d0749db7101dd5a373a1000
prerequisite-patch-id: 1098d63f68aaf6553b2884838125dcc0ad5b5766
-- 
2.14.5


[-- Attachment #3: 0002-std-unique_ptr.patch --]
[-- Type: text/x-patch, Size: 2793 bytes --]

From 6e4f88234d940b082f0e40c616a14e225ee6f58d Mon Sep 17 00:00:00 2001
From: Pedro Alves <pedro@palves.net>
Date: Fri, 24 Jul 2020 02:06:39 +0100
Subject: [PATCH 2/3] std::unique_ptr

---
 gdb/regcache.c | 26 ++++++++------------------
 1 file changed, 8 insertions(+), 18 deletions(-)

diff --git a/gdb/regcache.c b/gdb/regcache.c
index 2ddbcd372a2..3fc93c5a150 100644
--- a/gdb/regcache.c
+++ b/gdb/regcache.c
@@ -347,7 +347,9 @@ struct hash_target_ptid
 /* Type to map a (target, ptid) tuple to a regcache.  */
 
 using target_ptid_regcache_map
-  = std::unordered_multimap<target_ptid, regcache *, hash_target_ptid>;
+  = std::unordered_multimap<target_ptid,
+			    std::unique_ptr<regcache>,
+			    hash_target_ptid>;
 
 /* Global structure containing the existing regcaches.  */
 
@@ -370,7 +372,7 @@ get_thread_arch_aspace_regcache (process_stratum_target *target,
   for (auto it = range.first; it != range.second; it++)
     {
       if (it->second->arch () == arch)
-	return it->second;
+	return it->second.get ();
     }
 
   /* It does not exist, create it.  */
@@ -464,13 +466,13 @@ regcache_thread_ptid_changed (process_stratum_target *target,
   auto range = regcaches.equal_range (old_key);
   for (auto it = range.first; it != range.second;)
     {
-      regcache *rc = it->second;
+      std::unique_ptr<regcache> rc = std::move (it->second);
       rc->set_ptid (new_ptid);
 
       /* Remove old before inserting new, to avoid rehashing, which
          would invalidate iterators.  */
       it = regcaches.erase (it);
-      regcaches.insert (std::make_pair (new_key, rc));
+      regcaches.insert (std::make_pair (new_key, std::move (rc)));
     }
 }
 
@@ -494,22 +496,13 @@ registers_changed_ptid (process_stratum_target *target, ptid_t ptid)
          pass a ptid without saying to which target it belongs.  */
       gdb_assert (ptid == minus_one_ptid);
 
-      /* Delete all the regcaches.  */
-      for (auto pair : regcaches)
-	delete pair.second;
-
       regcaches.clear ();
     }
   else if (ptid != minus_one_ptid)
     {
       /* Non-NULL target and non-minus_one_ptid, delete all regcaches belonging
          to this (TARGET, PTID).  */
-      target_ptid key (target, ptid);
-      auto range = regcaches.equal_range (key);
-      for (auto it = range.first; it != range.second; it++)
-	delete it->second;
-
-      regcaches.erase (key);
+      regcaches.erase ({target, ptid});
     }
   else
     {
@@ -522,10 +515,7 @@ registers_changed_ptid (process_stratum_target *target, ptid_t ptid)
        for (auto it = regcaches.begin (); it != regcaches.end ();)
 	 {
 	   if (it->second->target () == target)
-	     {
-	       delete it->second;
-	       it = regcaches.erase (it);
-	     }
+	     it = regcaches.erase (it);
 	 }
      }
 
-- 
2.14.5


[-- Attachment #4: 0003-Two-level-map.patch --]
[-- Type: text/x-patch, Size: 8519 bytes --]

From e14a1156fc04601d6eb5b4edcb31395facad86ba Mon Sep 17 00:00:00 2001
From: Pedro Alves <pedro@palves.net>
Date: Fri, 24 Jul 2020 02:06:39 +0100
Subject: [PATCH 3/3] Two-level map

---
 gdb/regcache.c | 136 +++++++++++++++++++++++++++++++++------------------------
 1 file changed, 79 insertions(+), 57 deletions(-)

diff --git a/gdb/regcache.c b/gdb/regcache.c
index 3fc93c5a150..7c3a84caf5a 100644
--- a/gdb/regcache.c
+++ b/gdb/regcache.c
@@ -331,25 +331,14 @@ struct target_ptid
   }
 };
 
-/* Hash function for target_ptid.  */
-
-struct hash_target_ptid
-{
-  size_t operator() (const target_ptid &val) const
-  {
-    std::hash<long> h_long;
-    hash_ptid h_ptid;
-
-    return h_long ((long) val.target) + h_ptid (val.ptid);
-  }
-};
+using ptid_regcache_map
+  = std::unordered_multimap<ptid_t, std::unique_ptr<regcache>,
+			    hash_ptid>;
 
 /* Type to map a (target, ptid) tuple to a regcache.  */
 
 using target_ptid_regcache_map
-  = std::unordered_multimap<target_ptid,
-			    std::unique_ptr<regcache>,
-			    hash_target_ptid>;
+  = std::unordered_map<process_stratum_target *, ptid_regcache_map>;
 
 /* Global structure containing the existing regcaches.  */
 
@@ -367,12 +356,27 @@ get_thread_arch_aspace_regcache (process_stratum_target *target,
   gdb_assert (target != nullptr);
 
   /* Look up the regcache for this (target, ptid, arch).  */
-  target_ptid key (target, ptid);
-  auto range = regcaches.equal_range (key);
-  for (auto it = range.first; it != range.second; it++)
+
+  auto ptid_regc_map_it = regcaches.find (target);
+
+  if (ptid_regc_map_it != regcaches.end ())
     {
-      if (it->second->arch () == arch)
-	return it->second.get ();
+      auto &ptid_regc_map = ptid_regc_map_it->second;
+
+      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 ();
+	}
+    }
+
+  if (ptid_regc_map_it == regcaches.end ())
+    {
+      auto res_pair
+	= regcaches.insert (std::make_pair (target,
+					    ptid_regcache_map {}));
+      ptid_regc_map_it = res_pair.first;
     }
 
   /* It does not exist, create it.  */
@@ -380,7 +384,8 @@ get_thread_arch_aspace_regcache (process_stratum_target *target,
   new_regcache->set_ptid (ptid);
 
   /* Insert it in the map.  */
-  regcaches.insert (std::make_pair (key, new_regcache));
+  auto &ptid_regc_map = ptid_regc_map_it->second;
+  ptid_regc_map.insert (std::make_pair (ptid, new_regcache));
 
   return new_regcache;
 }
@@ -460,19 +465,22 @@ static void
 regcache_thread_ptid_changed (process_stratum_target *target,
 			      ptid_t old_ptid, ptid_t new_ptid)
 {
-  target_ptid old_key (target, old_ptid);
-  target_ptid new_key (target, new_ptid);
+  auto ptid_regc_map_it = regcaches.find (target);
 
-  auto range = regcaches.equal_range (old_key);
-  for (auto it = range.first; it != range.second;)
+  if (ptid_regc_map_it != regcaches.end ())
     {
-      std::unique_ptr<regcache> rc = std::move (it->second);
-      rc->set_ptid (new_ptid);
+      auto &ptid_regc_map = ptid_regc_map_it->second;
 
-      /* Remove old before inserting new, to avoid rehashing, which
-         would invalidate iterators.  */
-      it = regcaches.erase (it);
-      regcaches.insert (std::make_pair (new_key, std::move (rc)));
+      auto range = ptid_regc_map.equal_range (old_ptid);
+      for (auto it = range.first; it != range.second;)
+	{
+	  std::unique_ptr<regcache> 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)));
+	}
     }
 }
 
@@ -502,22 +510,19 @@ registers_changed_ptid (process_stratum_target *target, ptid_t ptid)
     {
       /* Non-NULL target and non-minus_one_ptid, delete all regcaches belonging
          to this (TARGET, PTID).  */
-      regcaches.erase ({target, ptid});
+      auto ptid_regc_map_it = regcaches.find (target);
+      if (ptid_regc_map_it != regcaches.end ())
+	{
+	  auto &ptid_regc_map = ptid_regc_map_it->second;
+	  ptid_regc_map.erase (ptid);
+	}
     }
   else
     {
-       /* Non-NULL target and minus_one_ptid, delete all regcaches associated
-          to this target.
-
-          We unfortunately don't have an efficient way to do this.  Fall back
-          to iterating all items to find all those belonging to TARGET.  */
-
-       for (auto it = regcaches.begin (); it != regcaches.end ();)
-	 {
-	   if (it->second->target () == target)
-	     it = regcaches.erase (it);
-	 }
-     }
+       /* Non-NULL target and minus_one_ptid, delete all regcaches
+          associated to this target.  */
+      regcaches.erase (target);
+    }
 
   if ((target == nullptr || current_thread_target == target)
       && current_thread_ptid.matches (ptid))
@@ -1498,6 +1503,18 @@ register_dump::dump (ui_file *file)
 
 namespace selftests {
 
+static size_t
+regcaches_size ()
+{
+  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.  */
 
 static void
@@ -1517,7 +1534,7 @@ static void
 regcaches_test (void)
 {
   /* It is empty at the start.  */
-  SELF_CHECK (regcaches.size () == 0);
+  SELF_CHECK (regcaches_size () == 0);
 
   ptid_t ptid1 (1), ptid2 (2), ptid3 (3);
 
@@ -1529,52 +1546,52 @@ regcaches_test (void)
   test_get_thread_arch_aspace_regcache (&test_target1, ptid1,
 					target_gdbarch (),
 					NULL);
-  SELF_CHECK (regcaches.size () == 1);
+  SELF_CHECK (regcaches_size () == 1);
 
   /* Get regcache from (target1,ptid2), a new regcache is added to
      REGCACHES.  */
   test_get_thread_arch_aspace_regcache (&test_target1, ptid2,
 					target_gdbarch (),
 					NULL);
-  SELF_CHECK (regcaches.size () == 2);
+  SELF_CHECK (regcaches_size () == 2);
 
   /* Get regcache from (target1,ptid3), a new regcache is added to
      REGCACHES.  */
   test_get_thread_arch_aspace_regcache (&test_target1, ptid3,
 					target_gdbarch (),
 					NULL);
-  SELF_CHECK (regcaches.size () == 3);
+  SELF_CHECK (regcaches_size () == 3);
 
   /* Get regcache from (target1,ptid2) again, nothing is added to
      REGCACHES.  */
   test_get_thread_arch_aspace_regcache (&test_target1, ptid2,
 					target_gdbarch (),
 					NULL);
-  SELF_CHECK (regcaches.size () == 3);
+  SELF_CHECK (regcaches_size () == 3);
 
   /* Get regcache from (target2,ptid2), a new regcache is added to
      REGCACHES, since this time we're using a different target.  */
   test_get_thread_arch_aspace_regcache (&test_target2, ptid2,
 					target_gdbarch (),
 					NULL);
-  SELF_CHECK (regcaches.size () == 4);
+  SELF_CHECK (regcaches_size () == 4);
 
   /* Mark that (target1,ptid2) changed.  The regcache of (target1,
      ptid2) should be removed from REGCACHES.  */
   registers_changed_ptid (&test_target1, ptid2);
-  SELF_CHECK (regcaches.size () == 3);
+  SELF_CHECK (regcaches_size () == 3);
 
   /* Get the regcache from (target2,ptid2) again, confirming the
      registers_changed_ptid call above did not delete it.  */
   test_get_thread_arch_aspace_regcache (&test_target2, ptid2,
 					target_gdbarch (),
 					NULL);
-  SELF_CHECK (regcaches.size () == 3);
+  SELF_CHECK (regcaches_size () == 3);
 
   /* Confirm that marking all regcaches of all targets as changed
      clears REGCACHES.  */
   registers_changed_ptid (nullptr, minus_one_ptid);
-  SELF_CHECK (regcaches.size () == 0);
+  SELF_CHECK (regcaches_size () == 0);
 }
 
 class target_ops_no_register : public test_target_ops
@@ -1909,11 +1926,16 @@ regcache_thread_ptid_changed ()
 
   /* Return the count of regcaches for (TARGET, PTID) in REGCACHES.  */
   auto regcache_count = [] (process_stratum_target *target, ptid_t ptid)
+    -> int
     {
-      target_ptid key (target, ptid);
-
-      auto range = regcaches.equal_range (key);
-      return std::distance (range.first, range.second);
+      auto ptid_regc_map_it = regcaches.find (target);
+      if (ptid_regc_map_it != regcaches.end ())
+	{
+	  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 0;
     };
 
   gdb_assert (regcaches.size () == 2);
-- 
2.14.5

Re: [PATCH 4/4] gdb: change regcache list to be a map

[John Baldwin]

On 7/23/20 6:53 PM, Pedro Alves wrote:
> On 7/20/20 9:41 PM, Simon Marchi via Gdb-patches wrote:
>> 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.
>>
>> Note: In hash_target_ptid, I am combining hash values from std::hash by
>> summing them.  I don't think it's ideal, since std::hash is just the
>> identity function for base types.  But I don't know what would be better
>> to reduce the change of collisions.  If anybody has a better idea, I'd
>> be interested.
> 
> I'd maybe look in some kernel sources, e.g., Linux or BSD, what they
> use as hash function for pids.

FreeBSD just does a very simple and with a power of 2 based on the
maximum number of processes (set via a boot-time tunable).

However, it has separate hash tables for pids and thread ids (tids).
It doesn't have a single hash table of threads indexed by (pid, tid)
because the tid namespace is independent and a tid is a fully unique
name to a kernel thread (lwp).

>> +/* 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 ()));
>> +  }
>> +};

I think summing the three components might be the best option.
Presumably the low bits of the hash are what actually get used and
so the goal would be to have more entropy there.  This means you
probably would _not_ want to do something like:

pid << 32 | lwp << 16 | tid

since many native backends will have tid of all zeroes.  It would
also not be ideal for backends that only do processes (so only
pid is non-zero).  The sum approach degrades to the right thing
for those targets without needing extra complication or conditionals.

-- 
John Baldwin

Re: [PATCH 3/4] gdb: pass target to thread_ptid_changed observable

[Simon Marchi]

On 2020-07-23 4:42 p.m., Pedro Alves wrote:
>> @@ -1817,6 +1818,58 @@ cooked_write_test (struct gdbarch *gdbarch)
>>      }
>>  }
>>  
>> +/* Verify that when two threads with the same ptid exist (from two different
>> +   targets) and one of them changes ptid, we only update the appropriate
>> +   regcaches.  */
>> +
>> +static void
>> +regcache_thread_ptid_changed ()
>> +{
>> +  /* Any arch will do.  */
>> +  gdbarch *arch = current_inferior ()->gdbarch;
>> +
>> +  /* Prepare two targets with one thread each, with the same ptid.  */
>> +  scoped_mock_context<test_target_ops> target1 (arch);
>> +  scoped_mock_context<test_target_ops> target2 (arch);
>> +  target2.mock_inferior.next = &target1.mock_inferior;
>> +
>> +  ptid_t old_ptid (111, 222);
>> +  ptid_t new_ptid (111, 333);
>> +
>> +  target1.mock_inferior.pid = old_ptid.pid ();
>> +  target1.mock_thread.ptid = old_ptid;
>> +  target2.mock_inferior.pid = old_ptid.pid ();
>> +  target2.mock_thread.ptid = old_ptid;
>> +
>> +  gdb_assert (regcaches.empty ());
> 
> This will fail if you debug something, e.g., run to main,
> and then do:
> 
>  (gdb) maint selftest regcache_thread_ptid_changed

I don't know, do we really want to support this?  I don't really see the point.  We can design
the selftests to make it possible, but is there any advantage?  In the selftests command, we
could ensure that you are not debugging something, and otherwise error out with "You can't run
selftests while debugging.".

> Maybe call registers_changed() before ?
> 
> Actually trying that made me notice that I completely missed
> making cooked_write_test in 236ef0346d88efffd1ca1da1a5d80724cb145660 ...
> Fixing that would get rid of these fails:
> 
>  Self test failed: arch i386: target already pushed
>  ...

I can do this, but I'll wait for your reply on the suggestion above to disallow running selftests
while debugging first.

>> +
>> +  /* Populate the regcaches container.  */
>> +  get_thread_arch_aspace_regcache (&target1.mock_target, old_ptid, arch, NULL);
>> +  get_thread_arch_aspace_regcache (&target2.mock_target, old_ptid, arch, NULL);
> 
> nullptr? ;-)

Yes!  I actually appreciate you pointing it out, if we chose one convention and follow it, we
don't have to always wonder which one to use!

>> +
>> +  /* Return whether a regcache for (TARGET, PTID) exists in REGCACHES.  */
>> +  auto regcache_exists = [] (process_stratum_target *target, ptid_t ptid)
>> +    {
>> +      for (regcache *rc : regcaches)
>> +	{
>> +	  if (rc->target () == target && rc->ptid () == ptid)
>> +	    return true;
>> +	}
>> +
>> +      return false;
>> +    };
>> +
>> +  gdb_assert (regcaches_size () == 2);
>> +  gdb_assert (regcache_exists (&target1.mock_target, old_ptid));
>> +  gdb_assert (regcache_exists (&target2.mock_target, old_ptid));
> 
> For completeness, I'd add:
> 
>   gdb_assert (!regcache_exists (&target1.mock_target, new_ptid));
>   gdb_assert (!regcache_exists (&target2.mock_target, new_ptid));
> 
>> +
>> +  thread_change_ptid (&target1.mock_target, old_ptid, new_ptid);
>> +
>> +  gdb_assert (regcaches_size () == 2);
>> +  gdb_assert (regcache_exists (&target1.mock_target, new_ptid));
>> +  gdb_assert (regcache_exists (&target2.mock_target, old_ptid));
> 
> Similarly here.

I thought that with `gdb_assert (regcaches_size () == 2)`, but more asserts
is not bad, it could catch some bug, we never know.  I've added them.

Simon

Re: [PATCH 4/4] gdb: change regcache list to be a map

[Simon Marchi]

On 2020-07-24 12:59 p.m., John Baldwin wrote:
> On 7/23/20 6:53 PM, Pedro Alves wrote:
>> On 7/20/20 9:41 PM, Simon Marchi via Gdb-patches wrote:
>>> 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.
>>>
>>> Note: In hash_target_ptid, I am combining hash values from std::hash by
>>> summing them.  I don't think it's ideal, since std::hash is just the
>>> identity function for base types.  But I don't know what would be better
>>> to reduce the change of collisions.  If anybody has a better idea, I'd
>>> be interested.
>>
>> I'd maybe look in some kernel sources, e.g., Linux or BSD, what they
>> use as hash function for pids.
> 
> FreeBSD just does a very simple and with a power of 2 based on the
> maximum number of processes (set via a boot-time tunable).
> 
> However, it has separate hash tables for pids and thread ids (tids).
> It doesn't have a single hash table of threads indexed by (pid, tid)
> because the tid namespace is independent and a tid is a fully unique
> name to a kernel thread (lwp).
> 
>>> +/* 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 ()));
>>> +  }
>>> +};
> 
> I think summing the three components might be the best option.
> Presumably the low bits of the hash are what actually get used and
> so the goal would be to have more entropy there.  This means you
> probably would _not_ want to do something like:
> 
> pid << 32 | lwp << 16 | tid
> 
> since many native backends will have tid of all zeroes.  It would
> also not be ideal for backends that only do processes (so only
> pid is non-zero).  The sum approach degrades to the right thing
> for those targets without needing extra complication or conditionals.

Ok, thanks for the tips.  So I'll probably keep it like this for now then.

I'll still take a look at the kernel implementations like Pedro suggested.

Simon

Re: [PATCH 4/4] gdb: change regcache list to be a map

[Simon Marchi]

On 2020-07-23 9:53 p.m., Pedro Alves wrote:
> On 7/20/20 9:41 PM, Simon Marchi via Gdb-patches wrote:
>> 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).  It becomes noticeable when
>> debugging thousands of threads, which is typical with GPU targets.  This
>> patch replaces the linked list with an std::unordered_multimap, indexed
>> by (target, ptid).
>>
>> I originally designed it 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.  Using (target, ptid) as a key allows to do this more
>> efficiently (see exception below).  If the key of the map was (target,
>> ptid, arch), we'd have to walk all items of the map.
>>
>> The lookup (in get_thread_arch_aspace_regcache), walks over all existing
>> regcaches belonging to this (target, ptid), looking to find the one with
>> the right arch.  This is ok, as there will be very few regcaches for a
>> given key (typically one).  Lookups 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 a map lookup 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).  We 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, this is done efficiently
>> - a non-NULL target and minus_one_ptid: we delete all the entries
>>   associated to that target, whatever the ptid.  This is the slightly
>>   annoying case, as we can't easily look up all items having this target
>>   in their key.  I implemented it by walking the list, which is not
>>   ideal.
> 
> Given the last case, did you consider using a two-level map instead?
> 
>   using ptid_regcache_map 
>     = std::unordered_multimap<ptid_t, regcache *>;
> 
>   using target_ptid_regcache_map 
>     = std::unordered_map<process_stratum_target *, ptid_regcache_map>;
> 
>   static target_ptid_regcache_map regcaches;
> 
> The result for registers_changed_ptid would be:
> 
>  - NULL target and minus_one_ptid: we delete all the REGCACHES entries,
> 
>  - NULL target and non-minus_one_ptid: invalid (checked by assert)
> 
>  - non-NULL target and non-minus_one_ptid: we lookup the target
>    in REGCACHES, and then delete all the entries in that map
>    associated to that ptid.
> 
>  - a non-NULL target and minus_one_ptid: we delete the map entry
>    in REGCACHES associated to that target.

I thought about it early on, but dismissed it thinking it would be too heavy
for nothing, having a map of maps.  But I didn't think it would help that last
case, that might be a good reason to go with that.

> Looking up a regcache does two map lookups instead of one, but
> that is 2x amortized O(1), so should be a constant hit.
> 
> I gave this a try, to see how feasible it would be.  See attached
> patches on top of yours (the first two address comments I'll make below).
> I've also put these in the users/palves/regcache-map branch on
> sourceware.org.

Thanks, I'll run with that.

> I did not run performance tests, though.  It may be that in
> registers_changed_ptid, it would be more efficient to
> not clear the first level map entry for a given target (i.e.,
> destroy the second level map object completely), but instead
> clear the second level map entry.  I.e., avoid destroying the
> unordered_multimap for a given target, only to recreate it soon
> enough.  But I kept it simple in case that isn't noticeable.

Will try.

> A similar two-level data structure would be to put an instance of:
> 
>   using ptid_regcache_map 
>     = std::unordered_multimap<ptid_t, regcache *>;
> 
> in process_stratum_target directly.
> 
> IOW, target-connection.c:process_targets has a list of open targets,
> which could be used to walk over all targets in the
> "NULL target and minus_one_ptid" scenario.

Ok, that would be an extra step, I suggest we keep it in mind for a subsequent
refactor.

>> 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.
>>
>> Note: In hash_target_ptid, I am combining hash values from std::hash by
>> summing them.  I don't think it's ideal, since std::hash is just the
>> identity function for base types.  But I don't know what would be better
>> to reduce the change of collisions.  If anybody has a better idea, I'd
>> be interested.
> 
> I'd maybe look in some kernel sources, e.g., Linux or BSD, what they
> use as hash function for pids.

Ok.

>> +/* Hash function for target_ptid.  */
>> +
>> +struct hash_target_ptid
>> +{
>> +  size_t operator() (const target_ptid &val) const
>> +  {
>> +    std::hash<long> h_long;
>> +    hash_ptid h_ptid;
>> +
>> +    return h_long ((long) val.target) + h_ptid (val.ptid);
> 
> Note that on 64-bit Windows, long is 32-bit, so pointers don't
> fit.  It just means you're only hashing half the bits.
> I wonder whether using libiberty's htab_hash_pointer would be
> a good idea here.

Huh, I did that because there's no std::hash overload for uintptr_t.  But
I just saw there is:

  template< class T > struct hash<T*>;

which seems to be for hashing pointers.  It is implemented as:

  return reinterpret_cast<size_t>(__p);

So I'll just use that.  Otherwise, htab_hash_pointer would be good too.

>> @@ -417,10 +458,25 @@ static void
>>  regcache_thread_ptid_changed (process_stratum_target *target,
>>  			      ptid_t old_ptid, ptid_t new_ptid)
>>  {
>> -  for (auto &regcache : regcaches)
>> +  /* Find all the regcaches to updates.  */
> 
> typo: to update.

Fixed.
>> +  std::vector<regcache *> regcaches_to_update;
>> +  target_ptid old_key (target, old_ptid);
>> +  auto range = regcaches.equal_range (old_key);
>> +  for (auto it = range.first; it != range.second; it++)
>> +    regcaches_to_update.push_back (it->second);
>> +
>> +  /* Remove all entries associated to OLD_KEY.  We could have erased the items
>> +     in the previous `for`, but it is only safe to erase items while iterating
>> +     starting with C++14.  */
>> +  regcaches.erase (old_key);
> 
> I don't think that's really true in practice.  The idiom used pretty
> much by everyone is:
> 
>   for (auto it = range.first; it != range.second;)
>     {
>       regcaches_to_update.push_back (it->second);
>       it = regcaches.erase (it);
>     }
> 
> Note that even the resolution of the C++ issue at:
> 
>  https://wg21.cmeerw.net/lwg/issue2356 
> 
> says:
> 
>  "not that any actual implementation does that, anyway"
> 
> There's no need to be super pedantic wrt to an issue
> that no compiler is going to miscompile.

Ok, didn't know about that.

> See here as well:
>  https://stackoverflow.com/questions/25047241/c11-is-it-safe-to-remove-individual-elements-from-stdunordered-map-while-it
> 
> And then, given we know that there are no entries for
> new_ptid in the map, I think we could instead do it all in
> one iteration, like:
> 
>   target_ptid old_key (target, old_ptid);
>   target_ptid new_key (target, new_ptid);
> 
>   auto range = regcaches.equal_range (old_key);
>   for (auto it = range.first; it != range.second;)
>     {
>       regcache *rc = it->second;
>       rc->set_ptid (new_ptid);
> 
>       /* Remove old before inserting new, to avoid rehashing, which
>          would invalidate iterators.  */
>       it = regcaches.erase (it);
>       regcaches.insert (std::make_pair (new_key, rc));
>     }

Thanks, I used this.

>> +
>> +  /* Update the regcaches' ptid, insert them back in the map with an updated
>> +     key.  */
>> +  target_ptid new_key (target, new_ptid);
>> +  for (regcache *rc : regcaches_to_update)
>>      {
>> -      if (regcache->ptid () == old_ptid && regcache->target () == target)
>> -	regcache->set_ptid (new_ptid);
>> +      rc->set_ptid (new_ptid);
>> +      regcaches.insert (std::make_pair (new_key, rc));
>>      }
>>  }
>>  
>> @@ -438,19 +494,53 @@ 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)
>>      {
>> -      struct regcache *regcache = *it;
>> -      if ((target == nullptr || regcache->target () == target)
>> -	  && regcache->ptid ().matches (ptid))
>> -	{
>> -	  delete regcache;
>> -	  it = regcaches.erase_after (oit);
>> -	}
>> -      else
>> -	oit = it++;
>> +      /* 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.  */
>> +      for (auto pair : regcaches)
>> +	delete pair.second;
> 
> We could store a std::unique_ptr<regcache> in the map instead
> to avoid all these manual deletes.

Indeed, I'll do that.

>> +
>> +      regcaches.clear ();
>>      }
>> +  else if (ptid != minus_one_ptid)
>> +    {
>> +      /* Non-NULL target and non-minus_one_ptid, delete all regcaches belonging
>> +         to this (TARGET, PTID).  */
>> +      target_ptid key (target, ptid);
>> +      auto range = regcaches.equal_range (key);
>> +      for (auto it = range.first; it != range.second; it++)
>> +	delete it->second;
> 
> Like this one.

Done.

>> +
>> +      regcaches.erase (key);
> 
> Here as well could do:
> 
>       for (auto it = range.first; it != range.second;)
>         {
> 	  delete it->second;
> 	  it = regcaches.erase (it);
>         }

With the unique_ptr, it's now just:

  regcaches.erase (target_ptid (target, ptid));

>> +    }
>> +  else
>> +    {
>> +       /* Non-NULL target and minus_one_ptid, delete all regcaches associated
>> +          to this target.
>> +
>> +          We unfortunately don't have an efficient way to do this.  Fall back
>> +          to iterating all items to find all those belonging to TARGET.
>> +
>> +          Note that in C++11, it's not safe to erase map entries while
>> +          iterating, so we keep track of them and delete them at the end.  */
> 
> Here as well.

It's down to:

       for (auto it = regcaches.begin (); it != regcaches.end ();)
	 {
	   if (it->second->target () == target)
	     it = regcaches.erase (it);
	   else
	     it++;
	 }

Thanks for the comments.  I'll try the multi-level map thing and come back with
another version.

Simon

Re: [PATCH 4/4] gdb: change regcache list to be a map

[Simon Marchi]

On 2020-07-30 12:58 p.m., Simon Marchi wrote:
> It's down to:
> 
>        for (auto it = regcaches.begin (); it != regcaches.end ();)
> 	 {
> 	   if (it->second->target () == target)
> 	     it = regcaches.erase (it);
> 	   else
> 	     it++;
> 	 }

Ah, I see that you've provided me a patch for that too (I thought you only
did the multi-level map thing).  Your code is:

        for (auto it = regcaches.begin (); it != regcaches.end ();)
          {
            if (it->second->target () == target)
              {
                delete it->second;
                it = regcaches.erase (it);
              }
          }

I think you are missing an it++ in the else?  Otherwise, when the target doesn't
match, we'll get into an infinite loop I presume.

Simon

Re: [PATCH 4/4] gdb: change regcache list to be a map

[Simon Marchi]

On 2020-07-30 12:58 p.m., Simon Marchi wrote:
> Huh, I did that because there's no std::hash overload for uintptr_t.  But
> I just saw there is:
> 
>   template< class T > struct hash<T*>;
> 
> which seems to be for hashing pointers.  It is implemented as:
> 
>   return reinterpret_cast<size_t>(__p);
> 
> So I'll just use that.  Otherwise, htab_hash_pointer would be good too.

And I just realized that it makes sense for this to exist, since you can use
pointers as keys in a map without doing anything special.

Simon

Re: [PATCH 4/4] gdb: change regcache list to be a map

[Simon Marchi]

Just a note, I think your implementation of get_thread_arch_aspace_regcache could
be simplified by using the top map's operator[].  When we look up a regcache, we'll
want to create it if it doesn't exist, which means that if the ptid_regcache_map
doesn't exist for a given target, we'll want to create it.

I'll do that change, but I wanted to tell you in case you see a problem with it.

Simon

Re: [PATCH 3/4] gdb: pass target to thread_ptid_changed observable

[Pedro Alves]

On 7/30/20 4:27 PM, Simon Marchi wrote:
> On 2020-07-23 4:42 p.m., Pedro Alves wrote:
>>> @@ -1817,6 +1818,58 @@ cooked_write_test (struct gdbarch *gdbarch)
>>>      }
>>>  }
>>>  
>>> +/* Verify that when two threads with the same ptid exist (from two different
>>> +   targets) and one of them changes ptid, we only update the appropriate
>>> +   regcaches.  */
>>> +
>>> +static void
>>> +regcache_thread_ptid_changed ()
>>> +{
>>> +  /* Any arch will do.  */
>>> +  gdbarch *arch = current_inferior ()->gdbarch;
>>> +
>>> +  /* Prepare two targets with one thread each, with the same ptid.  */
>>> +  scoped_mock_context<test_target_ops> target1 (arch);
>>> +  scoped_mock_context<test_target_ops> target2 (arch);
>>> +  target2.mock_inferior.next = &target1.mock_inferior;
>>> +
>>> +  ptid_t old_ptid (111, 222);
>>> +  ptid_t new_ptid (111, 333);
>>> +
>>> +  target1.mock_inferior.pid = old_ptid.pid ();
>>> +  target1.mock_thread.ptid = old_ptid;
>>> +  target2.mock_inferior.pid = old_ptid.pid ();
>>> +  target2.mock_thread.ptid = old_ptid;
>>> +
>>> +  gdb_assert (regcaches.empty ());
>>
>> This will fail if you debug something, e.g., run to main,
>> and then do:
>>
>>  (gdb) maint selftest regcache_thread_ptid_changed
> 
> I don't know, do we really want to support this?  I don't really see the point.  We can design
> the selftests to make it possible, but is there any advantage?  In the selftests command, we
> could ensure that you are not debugging something, and otherwise error out with "You can't run
> selftests while debugging.".

I don't see why we shouldn't.  Assuming that the regcaches are empty
like in the current patch can also fail is someone inserts some test
before this new test that ends up filling in the regcache.  I see it as
your new test being fragile because of that, and running the
"maint selftest" while some program is running is just a way
to trigger it.  To me, not allowing selftests while the
program is running is just an admission that the tests
aren't well isolated enough.

Re: [PATCH 4/4] gdb: change regcache list to be a map

[Pedro Alves]

On 7/30/20 6:03 PM, Simon Marchi wrote:
> On 2020-07-30 12:58 p.m., Simon Marchi wrote:
>> It's down to:
>>
>>        for (auto it = regcaches.begin (); it != regcaches.end ();)
>> 	 {
>> 	   if (it->second->target () == target)
>> 	     it = regcaches.erase (it);
>> 	   else
>> 	     it++;
>> 	 }
> Ah, I see that you've provided me a patch for that too (I thought you only
> did the multi-level map thing).

Note that it's idiomatic to write ++it instead of it++, to avoid
creating a temporary.  It's possible that compilers nowadays optimize
it away, but it still looks odd to not write ++it to me.


  Your code is:
> 
>         for (auto it = regcaches.begin (); it != regcaches.end ();)
>           {
>             if (it->second->target () == target)
>               {
>                 delete it->second;
>                 it = regcaches.erase (it);
>               }
>           }
> 
> I think you are missing an it++ in the else?  Otherwise, when the target doesn't
> match, we'll get into an infinite loop I presume.

Yes, I was.  I didn't notice because I jumped straight to the multi-map
patch on top, which deletes that code, IIRC.

Thanks,
Pedro Alves

Re: [PATCH 4/4] gdb: change regcache list to be a map

[Pedro Alves]

On 7/30/20 7:17 PM, Simon Marchi wrote:
> Just a note, I think your implementation of get_thread_arch_aspace_regcache could
> be simplified by using the top map's operator[].  When we look up a regcache, we'll
> want to create it if it doesn't exist, which means that if the ptid_regcache_map
> doesn't exist for a given target, we'll want to create it.
> 
> I'll do that change, but I wanted to tell you in case you see a problem with it.

I think you're right.  I don't see a problem offhand.

Pedro

Re: [PATCH 3/4] gdb: pass target to thread_ptid_changed observable

[Simon Marchi]

On 2020-08-05 10:50 a.m., Pedro Alves wrote:
> I don't see why we shouldn't.

I'd say because it's not worth the trouble.

>Assuming that the regcaches are empty
> like in the current patch can also fail is someone inserts some test
> before this new test that ends up filling in the regcache.  I see it as
> your new test being fragile because of that, and running the
> "maint selftest" while some program is running is just a way
> to trigger it.  To me, not allowing selftests while the
> program is running is just an admission that the tests
> aren't well isolated enough.
> 

I think it would make more sense to require that each test cleans up
properly after itself.

But anyhow, I'll do as you suggest, I don't mind.

Simon

Re: [PATCH 4/4] gdb: change regcache list to be a map

[Simon Marchi]

On 2020-08-05 2:02 p.m., Pedro Alves wrote:
> On 7/30/20 6:03 PM, Simon Marchi wrote:
>> On 2020-07-30 12:58 p.m., Simon Marchi wrote:
>>> It's down to:
>>>
>>>        for (auto it = regcaches.begin (); it != regcaches.end ();)
>>> 	 {
>>> 	   if (it->second->target () == target)
>>> 	     it = regcaches.erase (it);
>>> 	   else
>>> 	     it++;
>>> 	 }
>> Ah, I see that you've provided me a patch for that too (I thought you only
>> did the multi-level map thing).
> Note that it's idiomatic to write ++it instead of it++, to avoid
> creating a temporary.  It's possible that compilers nowadays optimize
> it away, but it still looks odd to not write ++it to me.

Ack.

>
>   Your code is:
>>         for (auto it = regcaches.begin (); it != regcaches.end ();)
>>           {
>>             if (it->second->target () == target)
>>               {
>>                 delete it->second;
>>                 it = regcaches.erase (it);
>>               }
>>           }
>>
>> I think you are missing an it++ in the else?  Otherwise, when the target doesn't
>> match, we'll get into an infinite loop I presume.
> Yes, I was.  I didn't notice because I jumped straight to the multi-map
> patch on top, which deletes that code, IIRC.
>
Thanks.

Simon

Re: [PATCH 3/4] gdb: pass target to thread_ptid_changed observable

[Pedro Alves]

On 8/5/20 8:08 PM, Simon Marchi wrote:
> On 2020-08-05 10:50 a.m., Pedro Alves wrote:
>> I don't see why we shouldn't.
> 
> I'd say because it's not worth the trouble.

But there's really no trouble.

> 
>> Assuming that the regcaches are empty
>> like in the current patch can also fail is someone inserts some test
>> before this new test that ends up filling in the regcache.  I see it as
>> your new test being fragile because of that, and running the
>> "maint selftest" while some program is running is just a way
>> to trigger it.  To me, not allowing selftests while the
>> program is running is just an admission that the tests
>> aren't well isolated enough.
>>
> 
> I think it would make more sense to require that each test cleans up
> properly after itself.

scoped_mock_context creates a new inferior list, adds a new inferior
to it with its own test target, adds new thread, and switches to it.  
The destructor restores the previous state.  When we switch to the mock
context, the running inferior is not reachable in the inferior list.
Whether an inferior was running or not, it shouldn't make a difference.
Maybe it should be both scoped_mock_context's constructor and destructor
that call registers_changed.  But I do think we should put a call to
registers_changed somewhere, to maintain invariants properly.

> But anyhow, I'll do as you suggest, I don't mind.

Thanks.

Re: [PATCH 0/4] Regcache fix and optimization

[Simon Marchi]

On 2020-07-20 4:40 p.m., Simon Marchi via Gdb-patches wrote:
> The main goal of this series is patch 4, and is about changing the
> regcache storage from a linked list to a map, to make lookups and
> removals more efficient.
> 
> Patches 1 and 2 are cleanups.  They are not necessary, but I think they
> would be nice to have.
> 
> Patch 3 addresses a potential bug I spotted while reading the code.
> 
> Simon Marchi (4):
>   gdb: rename regcache::current_regcache to regcache::regcaches
>   gdb: move regcache::regcaches to regcache.c
>   gdb: pass target to thread_ptid_changed observable
>   gdb: change regcache list to be a map
> 
>  gdb/dwarf2/index-write.c |   1 +
>  gdb/infrun.c             |  78 +++++++++++-
>  gdb/observable.h         |   6 +-
>  gdb/record-btrace.c      |   1 +
>  gdb/regcache.c           | 259 +++++++++++++++++++++++++++++----------
>  gdb/regcache.h           |   7 --
>  gdb/sparc64-tdep.c       |   2 +-
>  gdb/thread.c             |   2 +-
>  gdbsupport/ptid.h        |  16 +++
>  9 files changed, 291 insertions(+), 81 deletions(-)
> 
> -- 
> 2.26.2
> 

I pushed the first two patches, since they had the ack of Pedro.

Simon

Re: [PATCH 4/4] gdb: change regcache list to be a map

[Tom Tromey]

>>>>> "Simon" == Simon Marchi via Gdb-patches <gdb-patches@sourceware.org> writes:

A bit late on this thread, but OTOH nothing too urgent to say...

Simon> Note: In hash_target_ptid, I am combining hash values from std::hash by
Simon> summing them.  I don't think it's ideal, since std::hash is just the
Simon> identity function for base types.  But I don't know what would be better
Simon> to reduce the change of collisions.  If anybody has a better idea, I'd
Simon> be interested.

You can use fast_hash iteratively.  It may not matter though.

Simon> +/* Hash function for target_ptid.  */
Simon> +
Simon> +struct hash_target_ptid
Simon> +{
Simon> +  size_t operator() (const target_ptid &val) const
Simon> +  {

It seems to me that for types that have a single "natural" hash, or a
useful "canonical" hash (i.e., a hash we'd be likely to want to use by
default in the normal case), we could specialize std::hash.  For
example, this code could do that.

Tom

Re: [PATCH 4/4] gdb: change regcache list to be a map

[Simon Marchi]

On 2020-08-10 3:15 p.m., Tom Tromey wrote:
>>>>>> "Simon" == Simon Marchi via Gdb-patches <gdb-patches@sourceware.org> writes:
> 
> A bit late on this thread, but OTOH nothing too urgent to say...
> 
> Simon> Note: In hash_target_ptid, I am combining hash values from std::hash by
> Simon> summing them.  I don't think it's ideal, since std::hash is just the
> Simon> identity function for base types.  But I don't know what would be better
> Simon> to reduce the change of collisions.  If anybody has a better idea, I'd
> Simon> be interested.
> 
> You can use fast_hash iteratively.  It may not matter though.
> 
> Simon> +/* Hash function for target_ptid.  */
> Simon> +
> Simon> +struct hash_target_ptid
> Simon> +{
> Simon> +  size_t operator() (const target_ptid &val) const
> Simon> +  {
> 
> It seems to me that for types that have a single "natural" hash, or a
> useful "canonical" hash (i.e., a hash we'd be likely to want to use by
> default in the normal case), we could specialize std::hash.  For
> example, this code could do that.

Thanks, I'll consider doing these two changes.

Simon

Re: [PATCH 4/4] gdb: change regcache list to be a map

[Tom Tromey]

>>>>> "Simon" == Simon Marchi via Gdb-patches <gdb-patches@sourceware.org> writes:

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

[...]
Simon> - non-NULL target and non-minus_one_ptid: we delete all the entries
Simon>   associated to that tuple, this is done efficiently
Simon> - a non-NULL target and minus_one_ptid: we delete all the entries
Simon>   associated to that target, whatever the ptid.  This is the slightly
Simon>   annoying case, as we can't easily look up all items having this target
Simon>   in their key.  I implemented it by walking the list, which is not
Simon>   ideal.

This patch caused a regression for Ravenscar targets.  I spent a bit of
time tracking it down, and I think the issue is that there was a change
in the semantics in registers_changed_ptid.

Formerly it did this:

Simon> -      if ((target == nullptr || regcache->target () == target)
Simon> -	  && regcache->ptid ().matches (ptid))
Simon> -	{
Simon> -	  delete regcache;
Simon> -	  it = regcaches.erase_after (oit);

But now it does:

      if (target == nullptr)
    ...
      else if (ptid != minus_one_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 ())
            {
              auto &ptid_regc_map = ptid_regc_map_it->second;
              ptid_regc_map.erase (ptid);
            }
        }
      else
    ...

The difference being the call to ptid::matches.  This method will return
true if the ptid in question is a PID:

	    || (filter.is_pid () && m_pid == filter.pid ())

... but in the new code, no provision is made for the PID case.

This comes up because, at least in the case I am debugging,
target_resume is called with a PID and not -1.  See
user_visible_resume_ptid:

  else if (!sched_multi && target_supports_multi_process ())
    {
      /* Resume all threads of the current process (and none of other
	 processes).  */
      resume_ptid = ptid_t (inferior_ptid.pid ());
    }

At first I wasn't sure if this semantic change was really a bug; but now
it seems to me that it must be.  The non-stop and scheduler-locking
cases are handled earlier in user_visible_resume_ptid, so at this point
it intends to resume all the threads of the process.  And, in this
situation, I think the register caches for all threads in the process
ought to be cleared by the registers_changed_ptid call in target_resume.

A simple fix would be to fall back to iterating over the map in the
is_pid case.  I don't know whether this would reintroduce the
performance issue that prompted the patch, though.

I'd like to know whether you agree with this analysis ... if so, what
should we do; and if not, what is incorrect?

thanks,
Tom

Re: [PATCH 4/4] gdb: change regcache list to be a map

[Tom Tromey]

Tom> A simple fix would be to fall back to iterating over the map in the
Tom> is_pid case.  I don't know whether this would reintroduce the
Tom> performance issue that prompted the patch, though.

FWIW this worked for my test case.

I also have some ravenscar-thread changes, though I'm not sure yet if
those are really needed.

Tom

diff --git a/gdb/regcache.c b/gdb/regcache.c
index cd54bc6b5f9..d409b8c2f25 100644
--- a/gdb/regcache.c
+++ b/gdb/regcache.c
@@ -486,7 +486,15 @@ registers_changed_ptid (process_stratum_target *target, ptid_t ptid)
       if (ptid_regc_map_it != regcaches.end ())
 	{
 	  auto &ptid_regc_map = ptid_regc_map_it->second;
-	  ptid_regc_map.erase (ptid);
+
+	  auto last = ptid_regc_map.end ();
+	  for (auto i = ptid_regc_map.begin (); i != last; )
+	    {
+	      if (i->first.matches (ptid))
+		i = ptid_regc_map.erase (i);
+	      else
+		++i;
+	    }
 	}
     }
   else