From 888bdb2b744515d111953a0a3aa674ea822416f9 Mon Sep 17 00:00:00 2001 From: Simon Marchi Date: Fri, 7 Aug 2020 11:28:52 -0400 Subject: [PATCH] gdb: change regcache list to be a map One regcache object is created for each stopped thread and is stored in the regcache::regcaches linked list. Looking up a regcache for a given thread is therefore in O(number of threads). Stopping all threads then becomes O((number of threads) ^ 2). Same goes for resuming a thread (need to delete the regcache of a given ptid) and resuming all threads. It becomes noticeable when debugging thousands of threads, which is typical with GPU targets. This patch replaces the linked list with some maps to reduce that complexity. The first design was using an std::unordered_map with (target, ptid, arch) as the key, because that's how lookups are done (in get_thread_arch_aspace_regcache). However, the registers_changed_ptid function, also somewhat on the hot path (it is used when resuming threads), needs to delete all regcaches associated to a given (target, ptid) tuple. If the key of the map is (target, ptid, arch), we have to walk all items of the map, not good. The second design was therefore using an std::unordered_multimap with (target, ptid) as the key. One key could be associated to multiple regcaches, all with different gdbarches. When looking up, we would have to walk all these regcaches. This would be ok, because there will usually be actually one matching regcache. In the exceptional multi-arch thread cases, there will be maybe two. However, in registers_changed_ptid, we sometimes need to remove all regcaches matching a given target. We would then have to talk all items of the map again, not good. The design as implemented in this patch therefore uses two levels of map. One std::unordered_map uses the target as the key. The value type is an std::unordered_multimap that itself uses the ptid as the key. The values of the multimap are the regcaches themselves. Again, we expect to have one or very few regcaches per (target, ptid). So, in summary: * The lookups (in get_thread_arch_aspace_regcache), become faster when the number of threads grows, compared to the linked list. With a small number of threads, it will probably be a bit slower to do map lookups than to walk a few linked list nodes, but I don't think it will be noticeable in practice. * The function registers_changed_ptid deletes all regcaches related to a given (target, ptid). It must now handle the different cases separately: - NULL target and minus_one_ptid: we delete all the entries - NULL target and non-minus_one_ptid: invalid (checked by assert) - non-NULL target and non-minus_one_ptid: we delete all the entries associated to that tuple - a non-NULL target and minus_one_ptid: we delete all the entries associated to that target * The function regcache_thread_ptid_changed is called when a thread changes ptid. It is implemented efficiently using the map, although that's not very important: it is not called often, mostly when creating an inferior, on some specific platforms. This patch is a tiny bit from ROCm GDB [1] we would like to merge upstream. Laurent Morichetti gave be these performance numbers: The benchmark used is: time ./gdb --data-directory=data-directory /extra/lmoriche/hip/samples/0_Intro/bit_extract/bit_extract -ex "set pagination off" -ex "set breakpoint pending on" -ex "b bit_extract_kernel if \$_thread == 5" -ex run -ex c -batch It measures the time it takes to continue from a conditional breakpoint with 2048 threads at that breakpoint, one of them reporting the breakpoint. baseline: real 0m10.227s real 0m10.177s real 0m10.362s with patch: real 0m8.356s real 0m8.424s real 0m8.494s [1] https://github.com/ROCm-Developer-Tools/ROCgdb gdb/ChangeLog: * regcache.c (ptid_regcache_map): New type. (target_ptid_regcache_map): New type. (regcaches): Change type to target_ptid_regcache_map. (get_thread_arch_aspace_regcache): Update to regcaches' new type. (regcache_thread_ptid_changed): Likewise. (registers_changed_ptid): Likewise. (regcaches_size): Likewise. (regcaches_test): Update. (regcache_thread_ptid_changed): Update. * regcache.h (regcache_up): New type. * gdbsupport/ptid.h (hash_ptid): New struct. Change-Id: Iabb0a1111707936ca111ddb13f3b09efa83d3402 --- gdb/ChangeLog | 15 ++++++ gdb/regcache.c | 134 +++++++++++++++++++++++++++++++--------------- gdb/regcache.h | 2 + gdbsupport/ptid.h | 16 ++++++ 4 files changed, 125 insertions(+), 42 deletions(-) diff --git a/gdb/ChangeLog b/gdb/ChangeLog index fa1120e89e..88583bd73d 100644 --- a/gdb/ChangeLog +++ b/gdb/ChangeLog @@ -1,3 +1,18 @@ +2020-08-07 Simon Marchi + + * regcache.c (ptid_regcache_map): New type. + (target_ptid_regcache_map): New type. + (regcaches): Change type to target_ptid_regcache_map. + (get_thread_arch_aspace_regcache): Update to regcaches' new + type. + (regcache_thread_ptid_changed): Likewise. + (registers_changed_ptid): Likewise. + (regcaches_size): Likewise. + (regcaches_test): Update. + (regcache_thread_ptid_changed): Update. + * regcache.h (regcache_up): New type. + * gdbsupport/ptid.h (hash_ptid): New struct. + 2020-08-07 Simon Marchi * observable.h (thread_ptid_changed): Add parameter diff --git a/gdb/regcache.c b/gdb/regcache.c index 71e528f9b6..b8fcc52860 100644 --- a/gdb/regcache.c +++ b/gdb/regcache.c @@ -29,7 +29,7 @@ #include "reggroups.h" #include "observable.h" #include "regset.h" -#include +#include /* * DATA STRUCTURE @@ -313,31 +313,48 @@ reg_buffer::assert_regnum (int regnum) const gdb_assert (regnum < gdbarch_num_regs (arch ())); } -/* Global structure containing the current regcache. */ +/* Type to map a ptid to a list of regcaches (one thread may have multiple + regcaches, associated to different gdbarches). */ + +using ptid_regcache_map + = std::unordered_multimap; + +/* Type to map a target to a ptid_regcache_map, holding the regcaches for the + threads defined by that target. */ + +using target_ptid_regcache_map + = std::unordered_map; + +/* 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 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 ®cache : regcaches) - if (regcache->target () == target - && regcache->ptid () == ptid - && regcache->arch () == gdbarch) - return regcache; + /* Find the ptid -> regcache map for this target. */ + auto &ptid_regc_map = regcaches[target]; - regcache *new_regcache = new regcache (target, gdbarch, aspace); + /* Check first if a regcache for this arch already exists. */ + auto range = ptid_regc_map.equal_range (ptid); + for (auto it = range.first; it != range.second; ++it) + { + if (it->second->arch () == arch) + return it->second.get (); + } - regcaches.push_front (new_regcache); + /* It does not exist, create it. */ + regcache *new_regcache = new regcache (target, arch, aspace); new_regcache->set_ptid (ptid); + ptid_regc_map.insert (std::make_pair (ptid, new_regcache)); return new_regcache; } @@ -417,10 +434,22 @@ static void regcache_thread_ptid_changed (process_stratum_target *target, ptid_t old_ptid, ptid_t new_ptid) { - for (auto ®cache : regcaches) + auto ptid_regc_map_it = regcaches.find (target); + + if (ptid_regc_map_it == regcaches.end ()) + return; + + auto &ptid_regc_map = ptid_regc_map_it->second; + auto range = ptid_regc_map.equal_range (old_ptid); + for (auto it = range.first; it != range.second;) { - if (regcache->ptid () == old_ptid && regcache->target () == target) - regcache->set_ptid (new_ptid); + regcache_up rc = std::move (it->second); + rc->set_ptid (new_ptid); + + /* Remove old before inserting new, to avoid rehashing, + which would invalidate iterators. */ + it = ptid_regc_map.erase (it); + ptid_regc_map.insert (std::make_pair (new_ptid, std::move (rc))); } } @@ -438,18 +467,31 @@ regcache_thread_ptid_changed (process_stratum_target *target, void registers_changed_ptid (process_stratum_target *target, ptid_t ptid) { - for (auto oit = regcaches.before_begin (), it = std::next (oit); - it != regcaches.end (); ) + if (target == nullptr) + { + /* Since there can be ptid clashes between targets, it's not valid to + pass a ptid without saying to which target it belongs. */ + gdb_assert (ptid == minus_one_ptid); + + /* Delete all the regcaches of all targets. */ + regcaches.clear (); + } + else if (ptid != minus_one_ptid) { - struct regcache *regcache = *it; - if ((target == nullptr || regcache->target () == target) - && regcache->ptid ().matches (ptid)) + /* Non-NULL target and non-minus_one_ptid, delete all regcaches belonging + to this (TARGET, PTID). */ + auto ptid_regc_map_it = regcaches.find (target); + if (ptid_regc_map_it != regcaches.end ()) { - delete regcache; - it = regcaches.erase_after (oit); + auto &ptid_regc_map = ptid_regc_map_it->second; + ptid_regc_map.erase (ptid); } - else - oit = it++; + } + else + { + /* Non-NULL target and minus_one_ptid, delete all regcaches + associated to this target. */ + regcaches.erase (target); } if ((target == nullptr || current_thread_target == target) @@ -1434,8 +1476,14 @@ namespace selftests { static size_t regcaches_size () { - return std::distance (regcaches.begin (), - regcaches.end ()); + size_t size = 0; + for (auto it = regcaches.begin (); it != regcaches.end (); ++it) + { + auto &ptid_regc_map = it->second; + size += ptid_regc_map.size (); + } + + return size; } /* Wrapper around get_thread_arch_aspace_regcache that does some self checks. */ @@ -1852,31 +1900,33 @@ regcache_thread_ptid_changed () get_thread_arch_aspace_regcache (&target2.mock_target, old_ptid, arch, nullptr); - /* Return whether a regcache for (TARGET, PTID) exists in REGCACHES. */ - auto regcache_exists = [] (process_stratum_target *target, ptid_t ptid) + /* Return the count of regcaches for (TARGET, PTID) in REGCACHES. */ + auto regcache_count = [] (process_stratum_target *target, ptid_t ptid) + -> int { - for (regcache *rc : regcaches) + auto ptid_regc_map_it = regcaches.find (target); + if (ptid_regc_map_it != regcaches.end ()) { - if (rc->target () == target && rc->ptid () == ptid) - return true; + auto &ptid_regc_map = ptid_regc_map_it->second; + auto range = ptid_regc_map.equal_range (ptid); + return std::distance (range.first, range.second); } - - return false; + return 0; }; - gdb_assert (regcaches_size () == 2); - gdb_assert (regcache_exists (&target1.mock_target, old_ptid)); - gdb_assert (!regcache_exists (&target1.mock_target, new_ptid)); - gdb_assert (regcache_exists (&target2.mock_target, old_ptid)); - gdb_assert (!regcache_exists (&target2.mock_target, new_ptid)); + gdb_assert (regcaches.size () == 2); + gdb_assert (regcache_count (&target1.mock_target, old_ptid) == 1); + gdb_assert (regcache_count (&target1.mock_target, new_ptid) == 0); + gdb_assert (regcache_count (&target2.mock_target, old_ptid) == 1); + gdb_assert (regcache_count (&target2.mock_target, new_ptid) == 0); thread_change_ptid (&target1.mock_target, old_ptid, new_ptid); - gdb_assert (regcaches_size () == 2); - gdb_assert (!regcache_exists (&target1.mock_target, old_ptid)); - gdb_assert (regcache_exists (&target1.mock_target, new_ptid)); - gdb_assert (regcache_exists (&target2.mock_target, old_ptid)); - gdb_assert (!regcache_exists (&target2.mock_target, new_ptid)); + gdb_assert (regcaches.size () == 2); + gdb_assert (regcache_count (&target1.mock_target, old_ptid) == 0); + gdb_assert (regcache_count (&target1.mock_target, new_ptid) == 1); + gdb_assert (regcache_count (&target2.mock_target, old_ptid) == 1); + gdb_assert (regcache_count (&target2.mock_target, new_ptid) == 0); /* Leave the regcache list empty. */ registers_changed (); diff --git a/gdb/regcache.h b/gdb/regcache.h index dd0c2f27f9..9390f5708e 100644 --- a/gdb/regcache.h +++ b/gdb/regcache.h @@ -435,6 +435,8 @@ private: struct address_space *aspace); }; +using regcache_up = std::unique_ptr; + class readonly_detached_regcache : public readable_regcache { public: diff --git a/gdbsupport/ptid.h b/gdbsupport/ptid.h index ef52d55512..a528312bad 100644 --- a/gdbsupport/ptid.h +++ b/gdbsupport/ptid.h @@ -32,6 +32,8 @@ thread_stratum target that might want to sit on top. */ +#include + class ptid_t { public: @@ -143,6 +145,20 @@ private: long m_tid; }; +/* Functor to hash a ptid. */ + +struct hash_ptid +{ + size_t operator() (const ptid_t &ptid) const + { + std::hash long_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.34.1