Re: [PATCH 26/40] Optimize .gdb_index symbol name searching

Simon Marchi
2017-11-18T05:23:09Z

On 2017-06-02 08:22 AM, Pedro Alves wrote:
> @@ -4186,30 +4239,214 @@ 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<expand_symtabs_symbol_matcher_ftype> symbol_matcher,
> + enum search_domain kind,
> + gdb::function_view<void (offset_type)> 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});
> + }
> +
> + /* Sort name_comp 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 ();
>
> - name = index->constant_pool + MAYBE_SWAP (index->symbol_table[idx]);
> + /* 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);
> + } ();
>
> - if (!lookup_name_matcher.matches (name)
> - || (symbol_matcher != NULL && !symbol_matcher (name)))
> + /* 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);

Hi Pedro,

With Clang, I get this warning:

/home/simark/src/binutils-gdb/gdb/dwarf2read.c:4316:30: error: comparison of constant 255 with expression of type '__gnu_cxx::__alloc_traits<std::allocator<char> >::value_type' (aka 'char') is always true [-Werror,-Wtautological-constant-out-of-range-compare]
gdb_assert (after.back () != 0xff);
~~~~~~~~~~~~~ ^ ~~~~
/home/simark/src/binutils-gdb/gdb/common/gdb_assert.h:34:13: note: expanded from macro 'gdb_assert'
((void) ((expr) ? 0 : \
^~~~

Simon