From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-wm1-f68.google.com (mail-wm1-f68.google.com [209.85.128.68]) by sourceware.org (Postfix) with ESMTPS id 39B0B385702C for ; Fri, 24 Jul 2020 01:53:33 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.3.2 sourceware.org 39B0B385702C Authentication-Results: sourceware.org; dmarc=none (p=none dis=none) header.from=palves.net Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=alves.ped@gmail.com Received: by mail-wm1-f68.google.com with SMTP id t142so484909wmt.4 for ; Thu, 23 Jul 2020 18:53:33 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:subject:to:references:cc:from:message-id:date :user-agent:mime-version:in-reply-to:content-language; bh=Xg1hrSXyveHFsvpSsUDNuS5FtHn41An68hBWo3f9zWg=; b=AuRiTFO+vRFKNGGovjFAWG3/PlC3zLRsJUUQVHZSUFsVpVZmhMKi2Q1cWTiyarz1g4 MRjUDuXMzAsC2sjdhOkfgz+1vy0QlosPu4gSvhqRf7chl4mHf96anisMqjhvuVFkP0AI IaGJwjSBj++Hn4XUWJE5FiUrEE47btHfiGvvYRn5g6MDVE3Pa2ohaFSJUVD5eXLkrb9D /d2ouRdGhNkmXcQpvX6gmM+j0+yCh2xPtL8vPyuOEpcEpBjyQ352RtV9dwKLYcp4Urdu 89JCr96/kiORbsc6XlgujcNyA6d5p0py9g0rGX0umzzcBDiTn6E48wV5AjIff10QUs+R am6Q== X-Gm-Message-State: AOAM530eauLaIVVuqaNfbPxymtiZWwSUe/UGY2X14xgm4tiKbBIpRcWy 8p2wbWiCVdZvUy/DhfmV/Qo= X-Google-Smtp-Source: ABdhPJzpUpwQ7rr3PLPNLnCy4otFXdA7grkZutsxeJDm3yll2LpHdgGGlXGliPT2bRp9VxMMjjXqyw== X-Received: by 2002:a7b:c952:: with SMTP id i18mr6919466wml.65.1595555611838; Thu, 23 Jul 2020 18:53:31 -0700 (PDT) Received: from ?IPv6:2001:8a0:f91a:c400:56ee:75ff:fe8d:232b? ([2001:8a0:f91a:c400:56ee:75ff:fe8d:232b]) by smtp.gmail.com with ESMTPSA id z11sm5472849wrw.93.2020.07.23.18.53.30 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Thu, 23 Jul 2020 18:53:30 -0700 (PDT) Subject: Re: [PATCH 4/4] gdb: change regcache list to be a map To: Simon Marchi , gdb-patches@sourceware.org References: <20200720204101.2849535-1-simon.marchi@efficios.com> <20200720204101.2849535-5-simon.marchi@efficios.com> Cc: Laurent From: Pedro Alves Message-ID: <5b521483-2f09-3424-943d-40f83b3080af@palves.net> Date: Fri, 24 Jul 2020 02:53:27 +0100 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:60.0) Gecko/20100101 Thunderbird/60.2.1 MIME-Version: 1.0 In-Reply-To: <20200720204101.2849535-5-simon.marchi@efficios.com> Content-Type: multipart/mixed; boundary="------------BF8EAD3DB7E118A148DA7CB9" Content-Language: en-US X-Spam-Status: No, score=-8.6 required=5.0 tests=BAYES_00, FREEMAIL_FORGED_FROMDOMAIN, FREEMAIL_FROM, GIT_PATCH_0, HEADER_FROM_DIFFERENT_DOMAINS, KAM_DMARC_STATUS, KAM_LOTSOFHASH, RCVD_IN_DNSWL_NONE, RCVD_IN_MSPIKE_H2, SPF_HELO_NONE, SPF_PASS, TXREP autolearn=ham autolearn_force=no version=3.4.2 X-Spam-Checker-Version: SpamAssassin 3.4.2 (2018-09-13) on server2.sourceware.org X-BeenThere: gdb-patches@sourceware.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Gdb-patches mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Fri, 24 Jul 2020 01:53:37 -0000 This is a multi-part message in MIME format. --------------BF8EAD3DB7E118A148DA7CB9 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: 7bit 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; using target_ptid_regcache_map = std::unordered_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; 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 > +#include > > /* > * 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 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; > + > +/* 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; > - > - 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 ®cache : regcaches) > + /* Find all the regcaches to updates. */ typo: to update. > + std::vector 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 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 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 > + > 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_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 --------------BF8EAD3DB7E118A148DA7CB9 Content-Type: text/x-patch; name="0001-no-std-vector.patch" Content-Transfer-Encoding: 7bit Content-Disposition: attachment; filename="0001-no-std-vector.patch" >From 3d992e83fc36296fd9ab8f43d24a607996468bd1 Mon Sep 17 00:00:00 2001 From: Pedro Alves 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 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 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 --------------BF8EAD3DB7E118A148DA7CB9 Content-Type: text/x-patch; name="0002-std-unique_ptr.patch" Content-Transfer-Encoding: 7bit Content-Disposition: attachment; filename="0002-std-unique_ptr.patch" >From 6e4f88234d940b082f0e40c616a14e225ee6f58d Mon Sep 17 00:00:00 2001 From: Pedro Alves 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; + = std::unordered_multimap, + 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 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 --------------BF8EAD3DB7E118A148DA7CB9 Content-Type: text/x-patch; name="0003-Two-level-map.patch" Content-Transfer-Encoding: 7bit Content-Disposition: attachment; filename="0003-Two-level-map.patch" >From e14a1156fc04601d6eb5b4edcb31395facad86ba Mon Sep 17 00:00:00 2001 From: Pedro Alves 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 h_long; - hash_ptid h_ptid; - - return h_long ((long) val.target) + h_ptid (val.ptid); - } -}; +using ptid_regcache_map + = std::unordered_multimap, + hash_ptid>; /* Type to map a (target, ptid) tuple to a regcache. */ using target_ptid_regcache_map - = std::unordered_multimap, - hash_target_ptid>; + = std::unordered_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 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 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 --------------BF8EAD3DB7E118A148DA7CB9--