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

[Pedro Alves <pedro@palves.net>]

[-- 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