From patchwork Wed Nov 8 16:14:39 2017 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Pedro Alves X-Patchwork-Id: 24155 Received: (qmail 716 invoked by alias); 8 Nov 2017 16:14:47 -0000 Mailing-List: contact gdb-patches-help@sourceware.org; run by ezmlm Precedence: bulk List-Id: List-Unsubscribe: List-Subscribe: List-Archive: List-Post: List-Help: , Sender: gdb-patches-owner@sourceware.org Delivered-To: mailing list gdb-patches@sourceware.org Received: (qmail 588 invoked by uid 89); 8 Nov 2017 16:14:47 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-26.8 required=5.0 tests=BAYES_00, GIT_PATCH_0, GIT_PATCH_1, GIT_PATCH_2, GIT_PATCH_3, KAM_STOCKGEN, RP_MATCHES_RCVD, SPF_HELO_PASS autolearn=ham version=3.3.2 spammy= X-HELO: mx1.redhat.com Received: from mx1.redhat.com (HELO mx1.redhat.com) (209.132.183.28) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Wed, 08 Nov 2017 16:14:42 +0000 Received: from smtp.corp.redhat.com (int-mx04.intmail.prod.int.phx2.redhat.com [10.5.11.14]) (using TLSv1.2 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by mx1.redhat.com (Postfix) with ESMTPS id 5AED75D9E0 for ; Wed, 8 Nov 2017 16:14:41 +0000 (UTC) Received: from [127.0.0.1] (ovpn04.gateway.prod.ext.ams2.redhat.com [10.39.146.4]) by smtp.corp.redhat.com (Postfix) with ESMTP id 43DBA5D9C6; Wed, 8 Nov 2017 16:14:40 +0000 (UTC) Subject: Re: [PATCH 26/40] Optimize .gdb_index symbol name searching To: Keith Seitz , gdb-patches@sourceware.org References: <1496406158-12663-1-git-send-email-palves@redhat.com> <1496406158-12663-27-git-send-email-palves@redhat.com> From: Pedro Alves Message-ID: Date: Wed, 8 Nov 2017 16:14:39 +0000 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:45.0) Gecko/20100101 Thunderbird/45.4.0 MIME-Version: 1.0 In-Reply-To: On 08/08/2017 09:31 PM, Keith Seitz wrote: > On 06/02/2017 05:22 AM, Pedro Alves wrote: > >> I got, before the previous patch (-O2, x86-64): >> >> real 0m1.773s >> user 0m1.737s >> sys 0m0.040s >> >> and after this patch: >> >> real 0m1.361s >> user 0m1.315s >> sys 0m0.040s > > The results on my computer are slightly more dramatic, running with no > optimization, your test case (using Fedora 21 system gdb w/index debuginfo) > goes from about 15 seconds down to about 2.5 seconds. Very nice! > >> That resulted in 1351355 name_components. Each entry takes 8 bytes, >> so that's 10810840 bytes (ignoring std::vector overhead), or ~10.3 MB. >> That's IMO too small to worry about, given GDB was using over 7400MB >> total at that point. I.e., we're talking about 0.1% increase. > > Indeed. I'd sacrifice that kind of memory for the kind of speed increase > you've achieved -- in a heartbeat! > >> with only 8-bit and 32-bit tables, that'd be: >> >> 1349057 * 1 + 2298 * 4 + 4 * 1351355 = 6763669 bytes, or ~6.5MB. >> >> I don't think we need to bother though. > > I'm all for memory usage optimization and whatnot, but since the benefit is > so small (55% of these new tables saved but only 0.06% of total memory), > I prefer simplicity. So you won't get anything but agreement from me on this. > >> I also timed: >> >> $ time gdb --batch -q -p `pidof firefox` >> $ time gdb --batch -q -p `pidof firefox` -ex "b main" >> $ time gdb --batch -q -p `pidof firefox` -ex "set max-completion unlimited" -ex "complete b " > > I'd like to reproduce this, but my computer is incapable of running this test. > I'll take your word for it. ;-) :-) > >> gdb/ChangeLog: >> yyyy-mm-dd Pedro Alves >> >> * dwarf2read.c >> (mapped_index::name_components): New field. >> (mapped_index::symbol_name_at): New method. > > Silly nit: Isn't the form most are using "(tag name) : New field."? > I know I've relied on this several times to find changes in the ChangeLog. That made sense in C, since is used to specify the part of (foo) that changed: https://www.gnu.org/prep/standards/html_node/Indicating-the-Part-Changed.html#Indicating-the-Part-Changed ... and '::' does not exist in C. But it exists in C++, and it just feels natural to use it, since that's the way in C++ you'd name the 'foo' being referred to in '(foo)'. If you look at the GCCs ChangeLogs, you'll see they've been using this form too: grep "::" gcc/ChangeLog libstdc++-v3/ChangeLog >> (create_addrmap_from_index): Call mapped_index ctor. > > I don't see any changes to this function in the patch -- attributed to wrong > function? Indeed. It should have been dwarf2_read_index. Fixed, thanks. > >> diff --git a/gdb/dwarf2read.c b/gdb/dwarf2read.c >> index f523326..e955131 100644 >> --- a/gdb/dwarf2read.c >> +++ b/gdb/dwarf2read.c >> @@ -178,6 +178,51 @@ DEF_VEC_I (offset_type); > [snip] >> + >> +/* An index into a (C++) symbol name component in a symbol name as >> + recorded in the mapped_index's symbol table. For each C++ symbol >> + in the symbol table, we record one entry for the start of each >> + component in the symbol in a table of name components, and then >> + sort the table, in order to be able to binary search symbol names, >> + ignoring leading namespaces, both completion and regular look up. >> + For example, for symbol "A::B::C", we'll have an entry that points >> + to "A::B::C", another that points to "B::C", and another for "C". >> + Note that function symbols in GDB index have no parameter >> + information, just the function/method names. You can convert a >> + name_component to a "const char *" using the >> + 'mapped_index::symbol_name_at(offset_type)' method. */ > > missing nl? > Fixed. >> +struct name_component >> +{ >> + /* Offset in the symbol name where the component starts. Stored as >> + a (32-bit) offset instead of a pointer to save memory and improve >> + locality on 64-bit architectures. */ >> + offset_type name_offset; >> + >> + /* The symbol's index in the symbol and constant pool tables of a >> + mapped_index. */ >> + offset_type idx; >> +}; >> + >> /* A description of the mapped index. The file format is described in >> a comment by the code that writes the index. */ >> struct mapped_index >> @@ -3390,6 +3424,7 @@ dwarf2_read_index (struct objfile *objfile) >> create_addrmap_from_index (objfile, &local_map); >> >> map = XOBNEW (&objfile->objfile_obstack, struct mapped_index); >> + map = new (map) mapped_index (); >> *map = local_map; >> >> dwarf2_per_objfile->index_table = map; > > This function (dwarf2_read_index) is not mentioned in the ChangeLog. Could > this actually be incorrectly listed in the ChangeLog under > create_addrmap_from_index? Indeed. Fixed. > >> @@ -4095,6 +4134,22 @@ gdb_index_symbol_name_matcher::matches (const char *symbol_name) >> } >> >> static void >> +dw2_expand_marked_cus >> + (mapped_index &index, offset_type idx, >> + struct objfile *objfile, >> + gdb::function_view file_matcher, >> + gdb::function_view expansion_notify, >> + search_domain kind); >> + >> +static void >> +dw2_expand_symtabs_matching_symbol >> + (mapped_index &index, >> + const lookup_name_info &lookup_name_in, >> + gdb::function_view symbol_matcher, >> + enum search_domain kind, >> + gdb::function_view on_match); > > Isn't it rather unusual for us to have forward decls in the middle of a file? > Right, I should have mentioned -- I'd like to move the new dw2_expand_symtabs_matching_symbol and dw2_expand_marked_cus above dw2_expand_symtabs_matching, but I didn't do that here to make the patch easier to read and maintain. Likewise with the reindenting dw2_expand_marked_cus where I had marked with: /* XXX reindent code below before pushing. */ I'll move the code around in the following patch (a new patch), getting rid of the forward declarations. Since I'm doing that as a separate patch, it was also easier to leave the reindentation to that patch too. >> + >> +static void >> dw2_expand_symtabs_matching >> (struct objfile *objfile, >> gdb::function_view file_matcher, >> @@ -4186,30 +4239,214 @@ dw2_expand_symtabs_matching > [snip] >> +static void >> +dw2_expand_symtabs_matching_symbol >> + (mapped_index &index, >> + const lookup_name_info &lookup_name, >> + gdb::function_view symbol_matcher, >> + enum search_domain kind, >> + gdb::function_view match_callback) >> +{ > [snip] >> + >> + /* Sort name_comp elements by name. */ > > I presume that "name_comp" is really "name_components"? Indeed. Fixed. > I admit, I'm a little surprised by the number of steps involved here: push > every element in the range into a vector, sort, then de-dup & perform callback. > Had I implemented this, my initial attempt would have been to use a htab_up > and take the sorting time on insertion. > I can imagine that for very large ranges, your approach could outperform > an htab; do you expect these ranges to be that large? Have I overlooked > something? [I'm just curious. Not suggesting any changes need to be made.] Yeah, this is a hot path in completion lookup, and I'm trying to squeeze every cycle here. But the complexity is also needed because for completion, we need the symbols sorted, while an htab doesn't have a predictable iteration order. We want to find the lower / upper bounds starting with a needle that doesn't exist in the name_components vector/set. E.g., looking for what symbols complete "fun", when you have symbols named {... "bar", "func", "function", "xfunc" ... }, we want to consider "func", "function" as potential matches without wasting time with "bar" and "xfunc" (and others). So while using something like a std::set instead of a std::vector + sort would take the sorting out of view, I don't think that'd simplify that much, while it'd certainly perform worse. (See for example.) For the record, below's what I pushed. From 3f563c840a2c891ec2868b3e08bfaecb6f7aa57f Mon Sep 17 00:00:00 2001 From: Pedro Alves Date: Wed, 8 Nov 2017 14:22:32 +0000 Subject: [PATCH] Optimize .gdb_index symbol name searching As mentioned in the previous patch, .gdb_index name lookup got significantly slower with the previous patch. This patch addresses that, and in the process makes .gdb_index name searching faster than what we had before the previous patch, even. Using the same test: $ cat script.cmd set pagination off set $count = 0 while $count < 400 complete b string_prin printf "count = %d\n", $count set $count = $count + 1 end $ time gdb --batch -q ./gdb-with-index -ex "source script.cmd" I got, before the previous patch (-O2, x86-64): real 0m1.773s user 0m1.737s sys 0m0.040s and after this patch: real 0m1.361s user 0m1.315s sys 0m0.040s The basic idea here is simple: instead of always iterating over all the symbol names in the index, we build an accelerator/sorted name table and binary search names in it. Later in the series, we'll want to support wild matching for C++ too, so this mechanism already considers that. For example, say that you're looking up functions/methods named "func", no matter the containing namespace/class. If we sorted the table by qualified name, then we obviously wouldn't be able to find those symbols with a binary search: func ns1::a::b::func ns1::b::func ns2::func (function symbol names in .gdb_index have no parameter info, like psymbols) To address that out, we put an entry for each name component in the sorted table. something like this: Table Entry Actual symbol --------------------------------- func func func ns1::a::b::func b::func ns1::a::b::func a::b::func ns1::a::b::func ns1::a::b::func ns1::a::b::func func ns1::b::func b::func ns1::b::func ns1::b::func ns1::b::func func ns2::func ns2::func ns2::func Which sorted results in this: Table Entry Actual symbol --------------------------------- a::b::func ns1::a::b::func b::func ns1::a::b::func b::func ns1::b::func func func func ns1::a::b::func func ns1::b::func func ns2::func ns1::a::b::func ns1::a::b::func ns1::b::func ns1::b::func ns2::func ns2::func And we can binary search this. Note that a binary search approach works for both completion and regular lookup, while a name hashing approach only works for normal symbol looking, since obviously "fun" and "func" have different hashes. At first I was a bit wary of these tables potentially growing GDB's memory significantly. But I did an experiment that convinced it's not a worry at all. I hacked gdb to count the total number of entries in all the tables, attached that gdb to my system/Fedora's Firefox (Fedora's debug packages uses .gdb_index), did "set max-completions unlimited", and then hit "b [TAB]" to cause everything to expand. That resulted in 1351355 name_components. Each entry takes 8 bytes, so that's 10810840 bytes (ignoring std::vector overhead), or ~10.3 MB. That's IMO too small to worry about, given GDB was using over 7400MB total at that point. I.e., we're talking about 0.1% increase. dw2_expand_symtabs_matching unit tests covering this will be added in a follow up patch. If the size of this table turns out to be a concern, I have an idea to reduce the size of the table further at the expense of a bit more code -- the vast majority of the name offsets are either 0 or fit in 8-bits: total name_component = 1351355, of which, name_component::name_offset instances need 0 bits = 679531 name_component::name_offset instances need 8 bits = 669526 name_component::name_offset instances need 16 bits = 2298 name_component::name_offset instances need 32 bits = 0 name_component::idx instances need 0 bits = 51 name_component::idx instances need 8 bits = 8361 name_component::idx instances need 16 bits = 280329 name_component::idx instances need 32 bits = 1062614 so we could have separate tables for 0 name_offset, 8-bit name_offset and 32-bit name_offset. That'd give us roughly: 679531 * 0 + 669526 * 1 + 2298 * 4 + 1062614 * 4 = 4929174, or ~4.7MB with only 8-bit and 32-bit tables, that'd be: 1349057 * 1 + 2298 * 4 + 4 * 1351355 = 6763669 bytes, or ~6.5MB. I don't think we need to bother though. I also timed: $ time gdb --batch -q -p `pidof firefox` $ time gdb --batch -q -p `pidof firefox` -ex "b main" $ time gdb --batch -q -p `pidof firefox` -ex "set max-completion unlimited" -ex "complete b " and compared before previous patch vs this patch, and I didn't see a significant difference, seemingly because time to read debug info dominates. The "complete b " variant of the test takes ~2min currently... (I have a follow up series that speeds that up somewhat.) gdb/ChangeLog: 2017-11-08 Pedro Alves * dwarf2read.c (byte_swap, MAYBE_SWAP): Move higher up in file. (struct name_component): New. (mapped_index::name_components): New field. (mapped_index::symbol_name_at): New method. (dwarf2_read_index): Call mapped_index ctor. (dw2_map_matching_symbols): Add comment about name_components table. (dw2_expand_symtabs_matching): Factor part to... (dw2_expand_symtabs_matching_symbol): ... this new function. Build name components table, and lookup symbols in it before calling the name matcher. (dw2_expand_marked_cus): New, factored out from dw2_expand_symtabs_matching. (dwarf2_per_objfile_free): Call the mapped_index's dtor. --- gdb/ChangeLog | 17 +++ gdb/dwarf2read.c | 323 +++++++++++++++++++++++++++++++++++++++++++++++-------- 2 files changed, 298 insertions(+), 42 deletions(-) diff --git a/gdb/ChangeLog b/gdb/ChangeLog index 06ababc..deb1614 100644 --- a/gdb/ChangeLog +++ b/gdb/ChangeLog @@ -1,3 +1,20 @@ +2017-11-08 Pedro Alves + + * dwarf2read.c (byte_swap, MAYBE_SWAP): Move higher up in file. + (struct name_component): New. + (mapped_index::name_components): New field. + (mapped_index::symbol_name_at): New method. + (dwarf2_read_index): Call mapped_index ctor. + (dw2_map_matching_symbols): Add comment about name_components + table. + (dw2_expand_symtabs_matching): Factor part to... + (dw2_expand_symtabs_matching_symbol): ... this new function. + Build name components table, and lookup symbols in it before + calling the name matcher. + (dw2_expand_marked_cus): New, factored out from + dw2_expand_symtabs_matching. + (dwarf2_per_objfile_free): Call the mapped_index's dtor. + 2017-11-08 Pedro Alves * ada-lang.c (ada_encode): Rename to .. diff --git a/gdb/dwarf2read.c b/gdb/dwarf2read.c index f37d51f..6f88091 100644 --- a/gdb/dwarf2read.c +++ b/gdb/dwarf2read.c @@ -182,6 +182,53 @@ DEF_VEC_I (offset_type); GDB_INDEX_CU_SET_VALUE((cu_index), (value)); \ } while (0) +#if WORDS_BIGENDIAN + +/* Convert VALUE between big- and little-endian. */ + +static offset_type +byte_swap (offset_type value) +{ + offset_type result; + + result = (value & 0xff) << 24; + result |= (value & 0xff00) << 8; + result |= (value & 0xff0000) >> 8; + result |= (value & 0xff000000) >> 24; + return result; +} + +#define MAYBE_SWAP(V) byte_swap (V) + +#else +#define MAYBE_SWAP(V) static_cast (V) +#endif /* WORDS_BIGENDIAN */ + +/* An index into a (C++) symbol name component in a symbol name as + recorded in the mapped_index's symbol table. For each C++ symbol + in the symbol table, we record one entry for the start of each + component in the symbol in a table of name components, and then + sort the table, in order to be able to binary search symbol names, + ignoring leading namespaces, both completion and regular look up. + For example, for symbol "A::B::C", we'll have an entry that points + to "A::B::C", another that points to "B::C", and another for "C". + Note that function symbols in GDB index have no parameter + information, just the function/method names. You can convert a + name_component to a "const char *" using the + 'mapped_index::symbol_name_at(offset_type)' method. */ + +struct name_component +{ + /* Offset in the symbol name where the component starts. Stored as + a (32-bit) offset instead of a pointer to save memory and improve + locality on 64-bit architectures. */ + offset_type name_offset; + + /* The symbol's index in the symbol and constant pool tables of a + mapped_index. */ + offset_type idx; +}; + /* A description of the mapped index. The file format is described in a comment by the code that writes the index. */ struct mapped_index @@ -206,6 +253,15 @@ struct mapped_index /* A pointer to the constant pool. */ const char *constant_pool; + + /* The name_component table (a sorted vector). See name_component's + description above. */ + std::vector name_components; + + /* Convenience method to get at the name of the symbol at IDX in the + symbol table. */ + const char *symbol_name_at (offset_type idx) const + { return this->constant_pool + MAYBE_SWAP (this->symbol_table[idx]); } }; typedef struct dwarf2_per_cu_data *dwarf2_per_cu_ptr; @@ -2160,26 +2216,6 @@ line_header_eq_voidp (const void *item_lhs, const void *item_rhs) } -#if WORDS_BIGENDIAN - -/* Convert VALUE between big- and little-endian. */ -static offset_type -byte_swap (offset_type value) -{ - offset_type result; - - result = (value & 0xff) << 24; - result |= (value & 0xff00) << 8; - result |= (value & 0xff0000) >> 8; - result |= (value & 0xff000000) >> 24; - return result; -} - -#define MAYBE_SWAP(V) byte_swap (V) - -#else -#define MAYBE_SWAP(V) static_cast (V) -#endif /* WORDS_BIGENDIAN */ /* Read the given attribute value as an address, taking the attribute's form into account. */ @@ -3444,6 +3480,7 @@ dwarf2_read_index (struct objfile *objfile) create_addrmap_from_index (objfile, &local_map); map = XOBNEW (&objfile->objfile_obstack, struct mapped_index); + map = new (map) mapped_index (); *map = local_map; dwarf2_per_objfile->index_table = map; @@ -4070,7 +4107,11 @@ dw2_map_matching_symbols (struct objfile *objfile, Since each language has its own symbol name matching algorithm, and we don't know which language is the right one, we must match - each symbol against all languages. + each symbol against all languages. This would be a potential + performance problem if it were not mitigated by the + mapped_index::name_components lookup table, which significantly + reduces the number of times we need to call into this matcher, + making it a non-issue. - Symbol names in the index have no overload (parameter) information. I.e., in C++, "foo(int)" and "foo(long)" both @@ -4148,6 +4189,22 @@ gdb_index_symbol_name_matcher::matches (const char *symbol_name) } static void +dw2_expand_marked_cus + (mapped_index &index, offset_type idx, + struct objfile *objfile, + gdb::function_view file_matcher, + gdb::function_view expansion_notify, + search_domain kind); + +static void +dw2_expand_symtabs_matching_symbol + (mapped_index &index, + const lookup_name_info &lookup_name_in, + gdb::function_view symbol_matcher, + enum search_domain kind, + gdb::function_view on_match); + +static void dw2_expand_symtabs_matching (struct objfile *objfile, gdb::function_view file_matcher, @@ -4158,14 +4215,12 @@ dw2_expand_symtabs_matching { int i; offset_type iter; - struct mapped_index *index; dw2_setup (objfile); /* index_table is NULL if OBJF_READNOW. */ if (!dwarf2_per_objfile->index_table) return; - index = dwarf2_per_objfile->index_table; if (file_matcher != NULL) { @@ -4239,30 +4294,212 @@ dw2_expand_symtabs_matching } } - gdb_index_symbol_name_matcher lookup_name_matcher (lookup_name); + mapped_index &index = *dwarf2_per_objfile->index_table; - for (iter = 0; iter < index->symbol_table_slots; ++iter) + dw2_expand_symtabs_matching_symbol (index, lookup_name, + symbol_matcher, + kind, [&] (offset_type idx) { - offset_type idx = 2 * iter; - const char *name; - offset_type *vec, vec_len, vec_idx; - int global_seen = 0; + dw2_expand_marked_cus (index, idx, objfile, file_matcher, + expansion_notify, kind); + }); +} - QUIT; +/* Helper for dw2_expand_symtabs_matching that works with a + mapped_index instead of the containing objfile. This is split to a + separate function in order to be able to unit test the + name_components matching using a mock mapped_index. For each + symbol name that matches, calls MATCH_CALLBACK, passing it the + symbol's index in the mapped_index symbol table. */ - if (index->symbol_table[idx] == 0 && index->symbol_table[idx + 1] == 0) - continue; +static void +dw2_expand_symtabs_matching_symbol + (mapped_index &index, + const lookup_name_info &lookup_name, + gdb::function_view symbol_matcher, + enum search_domain kind, + gdb::function_view match_callback) +{ + gdb_index_symbol_name_matcher lookup_name_matcher + (lookup_name); + + auto *name_cmp = case_sensitivity == case_sensitive_on ? strcmp : strcasecmp; + + /* Build the symbol name component sorted vector, if we haven't yet. + The code below only knows how to break apart components of C++ + symbol names (and other languages that use '::' as + namespace/module separator). If we add support for wild matching + to some language that uses some other operator (E.g., Ada, Go and + D use '.'), then we'll need to try splitting the symbol name + according to that language too. Note that Ada does support wild + matching, but doesn't currently support .gdb_index. */ + if (index.name_components.empty ()) + { + for (size_t iter = 0; iter < index.symbol_table_slots; ++iter) + { + offset_type idx = 2 * iter; + + if (index.symbol_table[idx] == 0 + && index.symbol_table[idx + 1] == 0) + continue; + + const char *name = index.symbol_name_at (idx); + + /* Add each name component to the name component table. */ + unsigned int previous_len = 0; + for (unsigned int current_len = cp_find_first_component (name); + name[current_len] != '\0'; + current_len += cp_find_first_component (name + current_len)) + { + gdb_assert (name[current_len] == ':'); + index.name_components.push_back ({previous_len, idx}); + /* Skip the '::'. */ + current_len += 2; + previous_len = current_len; + } + index.name_components.push_back ({previous_len, idx}); + } - name = index->constant_pool + MAYBE_SWAP (index->symbol_table[idx]); + /* Sort name_components elements by name. */ + auto name_comp_compare = [&] (const name_component &left, + const name_component &right) + { + const char *left_qualified = index.symbol_name_at (left.idx); + const char *right_qualified = index.symbol_name_at (right.idx); + + const char *left_name = left_qualified + left.name_offset; + const char *right_name = right_qualified + right.name_offset; + + return name_cmp (left_name, right_name) < 0; + }; + + std::sort (index.name_components.begin (), + index.name_components.end (), + name_comp_compare); + } + + const char *cplus + = lookup_name.cplus ().lookup_name ().c_str (); - if (!lookup_name_matcher.matches (name) - || (symbol_matcher != NULL && !symbol_matcher (name))) + /* Comparison function object for lower_bound that matches against a + given symbol name. */ + auto lookup_compare_lower = [&] (const name_component &elem, + const char *name) + { + const char *elem_qualified = index.symbol_name_at (elem.idx); + const char *elem_name = elem_qualified + elem.name_offset; + return name_cmp (elem_name, name) < 0; + }; + + /* Comparison function object for upper_bound that matches against a + given symbol name. */ + auto lookup_compare_upper = [&] (const char *name, + const name_component &elem) + { + const char *elem_qualified = index.symbol_name_at (elem.idx); + const char *elem_name = elem_qualified + elem.name_offset; + return name_cmp (name, elem_name) < 0; + }; + + auto begin = index.name_components.begin (); + auto end = index.name_components.end (); + + /* Find the lower bound. */ + auto lower = [&] () + { + if (lookup_name.completion_mode () && cplus[0] == '\0') + return begin; + else + return std::lower_bound (begin, end, cplus, lookup_compare_lower); + } (); + + /* Find the upper bound. */ + auto upper = [&] () + { + if (lookup_name.completion_mode ()) + { + /* The string frobbing below won't work if the string is + empty. We don't need it then, anyway -- if we're + completing an empty string, then we want to iterate over + the whole range. */ + if (cplus[0] == '\0') + return end; + + /* In completion mode, increment the last character because + we want UPPER to point past all symbols names that have + the same prefix. */ + std::string after = cplus; + + gdb_assert (after.back () != 0xff); + after.back ()++; + + return std::upper_bound (lower, end, after.c_str (), + lookup_compare_upper); + } + else + return std::upper_bound (lower, end, cplus, lookup_compare_upper); + } (); + + /* Now for each symbol name in range, check to see if we have a name + match, and if so, call the MATCH_CALLBACK callback. */ + + /* The same symbol may appear more than once in the range though. + E.g., if we're looking for symbols that complete "w", and we have + a symbol named "w1::w2", we'll find the two name components for + that same symbol in the range. To be sure we only call the + callback once per symbol, we first collect the symbol name + indexes that matched in a temporary vector and ignore + duplicates. */ + std::vector matches; + matches.reserve (std::distance (lower, upper)); + + for (;lower != upper; ++lower) + { + const char *qualified = index.symbol_name_at (lower->idx); + + if (!lookup_name_matcher.matches (qualified) + || (symbol_matcher != NULL && !symbol_matcher (qualified))) continue; - /* The name was matched, now expand corresponding CUs that were - marked. */ - vec = (offset_type *) (index->constant_pool - + MAYBE_SWAP (index->symbol_table[idx + 1])); + matches.push_back (lower->idx); + } + + std::sort (matches.begin (), matches.end ()); + + /* Finally call the callback, once per match. */ + ULONGEST prev = -1; + for (offset_type idx : matches) + { + if (prev != idx) + { + match_callback (idx); + prev = idx; + } + } + + /* Above we use a type wider than idx's for 'prev', since 0 and + (offset_type)-1 are both possible values. */ + static_assert (sizeof (prev) > sizeof (offset_type), ""); +} + +/* Helper for dw2_expand_matching symtabs. Called on each symbol + matched, to expand corresponding CUs that were marked. IDX is the + index of the symbol name that matched. */ + +static void +dw2_expand_marked_cus + (mapped_index &index, offset_type idx, + struct objfile *objfile, + gdb::function_view file_matcher, + gdb::function_view expansion_notify, + search_domain kind) +{ + const char *name; + offset_type *vec, vec_len, vec_idx; + bool global_seen = false; + + vec = (offset_type *) (index.constant_pool + + MAYBE_SWAP (index.symbol_table[idx + 1])); vec_len = MAYBE_SWAP (vec[0]); for (vec_idx = 0; vec_idx < vec_len; ++vec_idx) { @@ -4278,7 +4515,7 @@ dw2_expand_symtabs_matching and indices >= 7 may elide them for certain symbols (gold does this). */ int attrs_valid = - (index->version >= 7 + (index.version >= 7 && symbol_kind != GDB_INDEX_SYMBOL_KIND_NONE); /* Work around gold/15646. */ @@ -4287,7 +4524,7 @@ dw2_expand_symtabs_matching if (!is_static && global_seen) continue; if (!is_static) - global_seen = 1; + global_seen = true; } /* Only check the symbol's kind if it has one. */ @@ -4338,7 +4575,6 @@ dw2_expand_symtabs_matching } } } - } } /* A helper for dw2_find_pc_sect_compunit_symtab which finds the most specific @@ -23362,6 +23598,9 @@ dwarf2_per_objfile_free (struct objfile *objfile, void *d) if (data->dwz_file && data->dwz_file->dwz_bfd) gdb_bfd_unref (data->dwz_file->dwz_bfd); + + if (data->index_table != NULL) + data->index_table->~mapped_index (); }