From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from us-smtp-delivery-124.mimecast.com (us-smtp-delivery-124.mimecast.com [170.10.129.124]) by sourceware.org (Postfix) with ESMTPS id 84A7F3858C00 for ; Fri, 27 Jan 2023 10:15:26 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 84A7F3858C00 Authentication-Results: sourceware.org; dmarc=pass (p=none dis=none) header.from=redhat.com Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=redhat.com DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=redhat.com; s=mimecast20190719; t=1674814526; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:cc:mime-version:mime-version:content-type:content-type: in-reply-to:in-reply-to:references:references; bh=bZkTcgbxAcYcWBHf2qIrp1YQ3lCl9iL1z8EBkL7oLx0=; b=ACeooXfG3t4uaO1iTX7jq6q4pTknj1b89ftRSTMZykLdVs4ol9xmtcd+JTbBPX3/9OzlcG K9RDiAzhL2/1a9LDDmb4povbnPd0b77IoWENV+Vub0SNSi3Gtyd9SKaeyiNu94vYnG8gEj 94CLd76+k71nvyF1M5GVWSu0ryqHadA= Received: from mail-qt1-f200.google.com (mail-qt1-f200.google.com [209.85.160.200]) by relay.mimecast.com with ESMTP with STARTTLS (version=TLSv1.3, cipher=TLS_AES_128_GCM_SHA256) id us-mta-501-sEKhpA1ZNqOix131Gi0Qlw-1; Fri, 27 Jan 2023 05:15:24 -0500 X-MC-Unique: sEKhpA1ZNqOix131Gi0Qlw-1 Received: by mail-qt1-f200.google.com with SMTP id m7-20020ac807c7000000b003b80b35c136so1920208qth.5 for ; Fri, 27 Jan 2023 02:15:24 -0800 (PST) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=mime-version:message-id:date:references:in-reply-to:subject:cc:to :from:x-gm-message-state:from:to:cc:subject:date:message-id:reply-to; bh=bZkTcgbxAcYcWBHf2qIrp1YQ3lCl9iL1z8EBkL7oLx0=; b=HUrLevNq/MiTm/b+j3x/8wZ8MJtQ+8v8PLrAVZ+jZhVrOURcqyjXJSeQBrHkc8AjHw 9ArLFZPGf3JncNsnWH2e/Mwx6HyOvhlUUeLI3joRJawYkYolDyTwn1KO+qHSSSE20F4v aKfIfuOS4ndq0WT7M4uMmWdJJVxMY0eneONIQNOsfZMdRq0ThmDwszSt3ZmWv3st/1ja IcLCc12phQDKXeLT2CbIl7BC2Hs05vyjO227SZs3URdDaDM2bUdNkwWsF8bBvtyUAv4k 0ttBKZX9sdXzpJo0510L6RsTQcHjzvT59o6wWZ+3W35I3Voq3g1l1jqQsOpK0E7R2ttO zNmA== X-Gm-Message-State: AO0yUKWbZtaXbVXcADgMrYjFhqG4gJrog1Asc56ri7aCZBIheezg9Egt QYp194mb1YXCGm4lYwi7Vz+pFKT9uY/Fh6JygwRYKC4YM2dPxNW8lSjKUTvIawtO8O60CMmc5jd U6G5WzvEfweFhXEllyrOLVw== X-Received: by 2002:a0c:edaf:0:b0:537:6583:1408 with SMTP id h15-20020a0cedaf000000b0053765831408mr20509351qvr.17.1674814523993; Fri, 27 Jan 2023 02:15:23 -0800 (PST) X-Google-Smtp-Source: AK7set/rcsfOXc2T4Y6ZiEWNd2HI4XHj/KSCmUfky5Z8Ymn0GnelJA9/+hPSMrj4+yAlbVHqhn+Aqw== X-Received: by 2002:a0c:edaf:0:b0:537:6583:1408 with SMTP id h15-20020a0cedaf000000b0053765831408mr20509326qvr.17.1674814523579; Fri, 27 Jan 2023 02:15:23 -0800 (PST) Received: from localhost (95.72.115.87.dyn.plus.net. [87.115.72.95]) by smtp.gmail.com with ESMTPSA id y27-20020a37f61b000000b006eeb3165565sm2588367qkj.80.2023.01.27.02.15.22 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Fri, 27 Jan 2023 02:15:23 -0800 (PST) From: Andrew Burgess To: Simon Marchi , Tom Tromey Cc: gdb-patches@sourceware.org Subject: Re: [PATCH v2 4/4] Fix parameter-less template regression in new DWARF reader In-Reply-To: <26ba8dcf-3f4e-983d-bbb8-a61c4b94c47d@simark.ca> References: <20230110183338.2623088-1-tromey@adacore.com> <20230110183338.2623088-5-tromey@adacore.com> <871qnt2bob.fsf@tromey.com> <26ba8dcf-3f4e-983d-bbb8-a61c4b94c47d@simark.ca> Date: Fri, 27 Jan 2023 10:15:21 +0000 Message-ID: <87wn58uvuu.fsf@redhat.com> MIME-Version: 1.0 X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com Content-Type: text/plain X-Spam-Status: No, score=-11.8 required=5.0 tests=BAYES_00,DKIMWL_WL_HIGH,DKIM_SIGNED,DKIM_VALID,DKIM_VALID_AU,DKIM_VALID_EF,GIT_PATCH_0,RCVD_IN_DNSWL_NONE,RCVD_IN_MSPIKE_H2,SPF_HELO_NONE,SPF_NONE,TXREP autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on server2.sourceware.org List-Id: Simon Marchi via Gdb-patches writes: > On 1/17/23 14:39, Tom Tromey wrote: >>>>>>> "Simon" == Simon Marchi writes: >> >> Simon> Starting with this patch, I get (using _GLIBCXX_DEBUG): >> [...] >> >> Ugh, sorry about that. >> I've reproduce it and I'm working on a fix. >> >> Tom > > I started to look into this, using that other patch I sent that dumps > the contents of the cooked index. You probably already know this, as > you have been looking at the problem already, but it can perhaps help > pothers. The specific instance I look at is: > > $ ./gdb -nx -q --data-directory=data-directory testsuite/outputs/gdb.cp/cpexprs/cpexprs -ex start -ex "print policy1::function" -batch > > When searching in the cooked index, the search string (canonicalized > version of the input, I think) is: > > "policy >::function" > > The problem is that the lower bound function used in > cooked_index::find (cooked_index_entry::compare) is invalid for these > two consecutive entries: > > [365] ((cooked_index_entry *) 0x621000115080) > name: policy > canonical: policy > DWARF tag: DW_TAG_subprogram > flags: 0x0 [] > DIE offset: 0x3951 > parent: ((cooked_index_entry *) 0x6210001137a0) [policy >] > > [366] ((cooked_index_entry *) 0x621000113740) > name: policy > > canonical: policy > > DWARF tag: DW_TAG_class_type > flags: 0x0 [] > DIE offset: 0x22a3 > parent: ((cooked_index_entry *) 0) > > It returns that [365] greater or equal to our search string, but also > that [366] is less than our search string. This is a contradiction, > because elements are supposed to be sorted according to the comparison > function. I've been carrying a patch to work around this issue since the issue was introduced. I've included the patch below, but I don't see it as a permanent fix, though it might help some folk in the short term as a work around. The underlying problem is that we use a different sort predicate for the std::lower_bound and std::upper_bound calls (in some cases) than when we sorted this list. I'm not sure this can ever work correctly. The patch below replaces the lower/upper bound calls with a linear walk of the cooked_index, but this is pretty slow, so much so I had to extend a timeout in one test to avoid it timing out. I also started looking into this more seriously yesterday as I was getting fed up having to port this patch to all my dev branches. Thanks, Andrew --- commit 8094b570486c6a9af4b3223ac7dc42227064cd10 Author: Andrew Burgess Date: Thu Jan 19 18:16:07 2023 +0000 [wip] gdb: temporary fix for the cooked index issue Issue introduced in commit: commit ac37b79cc440e37fc704d425a6e450afb3c7ee89 Date: Wed Dec 14 14:37:41 2022 -0700 Fix parameter-less template regression in new DWARF reader Problem is a use of std::lower_bound with a comparison function that is different to the one used to sort the vector. This changes seems to slow down GDB a fair bit though, this can be seen by the need to adjust gdb.gdb/python-helper.exp. diff --git a/gdb/dwarf2/cooked-index.c b/gdb/dwarf2/cooked-index.c index 09b3fd70b26..48f58f70b0f 100644 --- a/gdb/dwarf2/cooked-index.c +++ b/gdb/dwarf2/cooked-index.c @@ -30,7 +30,7 @@ /* See cooked-index.h. */ -bool +int cooked_index_entry::compare (const char *stra, const char *strb, bool completing) { @@ -58,7 +58,7 @@ cooked_index_entry::compare (const char *stra, const char *strb, consider them as equal. Also, completion mode ignores the special '<' handling. */ if (c1 == '\0' || c2 == '\0') - return false; + return 0; /* Fall through to the generic case. */ } else if (seen_lt) @@ -69,17 +69,31 @@ cooked_index_entry::compare (const char *stra, const char *strb, { /* Maybe they both end at the same spot. */ if (c2 == '\0' || c2 == '<') - return false; + return 0; /* First string ended earlier. */ - return true; + return -1; } else if (c2 == '\0' || c2 == '<') { /* Second string ended earlier. */ - return false; + return 1; } - return c1 < c2; + if (c1 < c2) + return -1; + else if (c1 == c2) + return 0; + else + return 1; +} + +/* See cooked-index.h. */ + +bool +cooked_index_entry::is_equal (const char *stra, const char *strb, + bool completing) +{ + return compare (stra, strb, completing) == 0; } #if GDB_SELF_TEST @@ -89,45 +103,45 @@ namespace { void test_compare () { - SELF_CHECK (!cooked_index_entry::compare ("abcd", "abcd", false)); - SELF_CHECK (!cooked_index_entry::compare ("abcd", "abcd", false)); - SELF_CHECK (!cooked_index_entry::compare ("abcd", "abcd", true)); - SELF_CHECK (!cooked_index_entry::compare ("abcd", "abcd", true)); - - SELF_CHECK (cooked_index_entry::compare ("abcd", "ABCDE", false)); - SELF_CHECK (!cooked_index_entry::compare ("ABCDE", "abcd", false)); - SELF_CHECK (!cooked_index_entry::compare ("abcd", "ABCDE", true)); - SELF_CHECK (!cooked_index_entry::compare ("ABCDE", "abcd", true)); - - SELF_CHECK (!cooked_index_entry::compare ("name", "name<>", false)); - SELF_CHECK (!cooked_index_entry::compare ("name<>", "name", false)); - SELF_CHECK (!cooked_index_entry::compare ("name", "name<>", true)); - SELF_CHECK (!cooked_index_entry::compare ("name<>", "name", true)); - - SELF_CHECK (!cooked_index_entry::compare ("name", "name", false)); - SELF_CHECK (!cooked_index_entry::compare ("name", "name", false)); - SELF_CHECK (!cooked_index_entry::compare ("name", "name", true)); - SELF_CHECK (!cooked_index_entry::compare ("name", "name", true)); - - SELF_CHECK (!cooked_index_entry::compare ("name>", - "name>", false)); - - SELF_CHECK (!cooked_index_entry::compare ("name", "name>", false)); - SELF_CHECK (!cooked_index_entry::compare ("name>", "name", false)); + SELF_CHECK (cooked_index_entry::compare ("abcd", "abcd", false) == 0); + SELF_CHECK (cooked_index_entry::compare ("abcd", "abcd", false) == 0); + SELF_CHECK (cooked_index_entry::compare ("abcd", "abcd", true) == 0); + SELF_CHECK (cooked_index_entry::compare ("abcd", "abcd", true) == 0); + + SELF_CHECK (cooked_index_entry::compare ("abcd", "ABCDE", false) < 0); + SELF_CHECK (cooked_index_entry::compare ("ABCDE", "abcd", false) > 0); + SELF_CHECK (cooked_index_entry::compare ("abcd", "ABCDE", true) == 0); + SELF_CHECK (cooked_index_entry::compare ("ABCDE", "abcd", true) == 0); + + SELF_CHECK (cooked_index_entry::compare ("name", "name<>", false) == 0); + SELF_CHECK (cooked_index_entry::compare ("name<>", "name", false) == 0); + SELF_CHECK (cooked_index_entry::compare ("name", "name<>", true) == 0); + SELF_CHECK (cooked_index_entry::compare ("name<>", "name", true) == 0); + + SELF_CHECK (cooked_index_entry::compare ("name", "name", false) == 0); + SELF_CHECK (cooked_index_entry::compare ("name", "name", false) == 0); + SELF_CHECK (cooked_index_entry::compare ("name", "name", true) == 0); + SELF_CHECK (cooked_index_entry::compare ("name", "name", true) > 0); + + SELF_CHECK (cooked_index_entry::compare ("name>", + "name>", false) == 0); + + SELF_CHECK (cooked_index_entry::compare ("name", "name>", false) == 0); + SELF_CHECK (cooked_index_entry::compare ("name>", "name", false) == 0); SELF_CHECK (cooked_index_entry::compare ("name>", - false)); - SELF_CHECK (!cooked_index_entry::compare ("name>", - true)); - SELF_CHECK (!cooked_index_entry::compare ("name>", "name>", "name>", + true) == 0); + SELF_CHECK (cooked_index_entry::compare ("name>", "name 0); + SELF_CHECK (cooked_index_entry::compare ("name>", "name 0); + SELF_CHECK (cooked_index_entry::compare ("abcd", "", true) == 0); } } /* anonymous namespace */ @@ -352,32 +366,6 @@ cooked_index::do_finalize () }); } -/* See cooked-index.h. */ - -cooked_index::range -cooked_index::find (const std::string &name, bool completing) -{ - wait (); - - auto lower = std::lower_bound (m_entries.begin (), m_entries.end (), name, - [=] (const cooked_index_entry *entry, - const std::string &n) - { - return cooked_index_entry::compare (entry->canonical, n.c_str (), - completing); - }); - - auto upper = std::upper_bound (m_entries.begin (), m_entries.end (), name, - [=] (const std::string &n, - const cooked_index_entry *entry) - { - return cooked_index_entry::compare (n.c_str (), entry->canonical, - completing); - }); - - return range (lower, upper); -} - cooked_index_vector::cooked_index_vector (vec_type &&vec) : m_vector (std::move (vec)) { @@ -417,8 +405,31 @@ cooked_index_vector::find (const std::string &name, bool completing) { std::vector result_range; result_range.reserve (m_vector.size ()); - for (auto &entry : m_vector) - result_range.push_back (entry->find (name, completing)); + + for (auto &cooked_index : m_vector) + { + auto entry_range = cooked_index->all_entries (); + for (auto it = entry_range.begin (); + it < entry_range.end (); + ++it) + { + auto start_it = it; + while (it < entry_range.end () + && cooked_index_entry::is_equal ((*it)->canonical, + name.c_str (), + completing)) + ++it; + + if (start_it != it) + { + cooked_index::range r { start_it, it }; + result_range.push_back (r); + } + + if (it == entry_range.end ()) + break; + } + } return range (std::move (result_range)); } diff --git a/gdb/dwarf2/cooked-index.h b/gdb/dwarf2/cooked-index.h index 55eaf9955ab..b1e4859f6aa 100644 --- a/gdb/dwarf2/cooked-index.h +++ b/gdb/dwarf2/cooked-index.h @@ -143,16 +143,25 @@ struct cooked_index_entry : public allocate_on_obstack STORAGE. */ const char *full_name (struct obstack *storage) const; + /* Compare two strings, case-insensitively. Return -1 if STRA is + less than STRB, 0 if STRA equals STRB, and 1 if STRA is greater than + STRB. + + If one string has template parameters, but the other does not, then + they are considered to be equal; so for example "t" == "t", + "t" < "t", but "t" == "t". */ + static int compare (const char *stra, const char *strb, bool completing); + /* Compare two strings, case-insensitively. Return true if STRA is - less than STRB. If one string has template parameters, but the + equal to STRB. If one string has template parameters, but the other does not, then they are considered to be equal; so for example "t" == "t", "t" < "t", but "t" == "t". */ - static bool compare (const char *stra, const char *strb, bool completing); + static bool is_equal (const char *stra, const char *strb, bool completing); /* Compare two entries by canonical name. */ bool operator< (const cooked_index_entry &other) const { - return compare (canonical, other.canonical, false); + return compare (canonical, other.canonical, false) < 0; } /* The name as it appears in DWARF. This always points into one of @@ -234,11 +243,6 @@ class cooked_index return { m_entries.begin (), m_entries.end () }; } - /* Look up an entry by name. Returns a range of all matching - results. If COMPLETING is true, then a larger range, suitable - for completion, will be returned. */ - range find (const std::string &name, bool completing); - private: /* Return the entry that is believed to represent the program's diff --git a/gdb/testsuite/gdb.gdb/python-helper.exp b/gdb/testsuite/gdb.gdb/python-helper.exp index 98f03ef456f..186ae4eed56 100644 --- a/gdb/testsuite/gdb.gdb/python-helper.exp +++ b/gdb/testsuite/gdb.gdb/python-helper.exp @@ -211,5 +211,7 @@ proc test_python_helper {} { return 0 } -# Use the self-test framework to run the test. -do_self_tests captured_main test_python_helper +with_timeout_factor 3 { + # Use the self-test framework to run the test. + do_self_tests captured_main test_python_helper +}