[PATCH 04/40] Fix TAB-completion + .gdb_index slowness (generalize filename_seen_cache)

Pedro Alves
2017-06-02T12:31:39Z

Tab completion when debugging a program binary that uses GDB index is
surprisingly much slower than when GDB uses psymtabs instead. Around
1.5x/3x slower. That's surprising, because the whole point of GDB
index is to speed things up...

For example, with:

set pagination off
set $count = 0
while $count < 400
complete b string_prin # matches gdb's string_printf
printf "count = %d\n", $count
set $count = $count + 1
end

$ time ./gdb --batch -q ./gdb-with-index -ex "source script.cmd"
real 0m11.042s
user 0m10.920s
sys 0m0.042s

$ time ./gdb --batch -q ./gdb-without-index -ex "source script.cmd"
real 0m4.635s
user 0m4.590s
sys 0m0.037s

Same but with:
- complete b string_prin
+ complete b zzzzzz
to exercise the no-matches worse case, master currently gets you
something like:

with index without index
real 0m11.971s 0m8.413s
user 0m11.912s 0m8.355s
sys 0m0.035s 0m0.035s

Running gdb under perf shows 80% spent inside
maybe_add_partial_symtab_filename, and 20% spent in the lbasename
inside that.

The problem that tab completion walks over all compunit symtabs, and
for each, walks the contained file symtabs. And there a huge number
of file symtabs (each included system header, etc.) that appear in
each compunit symtab's file symtab list. As in, when debugging GDB, I
have 367381 symtabs iterated, when of those only 5371 filenames are
unique...

This was a regression from the earlier (nice) split of symtabs in
compunit symtabs + file symtabs.

The fix here is to add a cache of unique filenames per objfile so that
the walk / uniquing is only done once. There's already a abstraction
for this in symtab.c; this patch moves that code out to a separate
file and C++ifies it bit.

This makes the worse-case scenario above consistently drop to ~2.5s
(1.5s for the "string_prin" hit case), making it over 3.3x times
faster than psymtabs in this use case (7x in the "string_prin" hit
case).

gdb/ChangeLog:
yyyy-mm-dd Pedro Alves <palves@redhat.com>

* Makefile.in (COMMON_OBS): Add filename-seen-cache.o.
* dwarf2read.c: Include "filename-seen-cache.h".
* dwarf2read.c (dwarf2_per_objfile) <filenames_cache>: New field.
(dw2_map_symbol_filenames): Build and use a filenames_seen_cache.
* filename-seen-cache.c: New file.
* filename-seen-cache.h: New file.
* symtab.c: Include "filename-seen-cache.h".
(struct filename_seen_cache, INITIAL_FILENAME_SEEN_CACHE_SIZE)
(create_filename_seen_cache, clear_filename_seen_cache)
(delete_filename_seen_cache, filename_seen): Delete, parts moved
to filename-seen-cache.h/filename_seen_cache.c.
(output_source_filename, sources_info)
(maybe_add_partial_symtab_filename)
(make_source_files_completion_list): Adjust to use
filename_seen_cache.
---
gdb/Makefile.in | 1 +
gdb/dwarf2read.c | 105 ++++++++++++++++++++++++++--------------------
gdb/filename-seen-cache.c | 73 ++++++++++++++++++++++++++++++++
gdb/filename-seen-cache.h | 64 ++++++++++++++++++++++++++++
gdb/symtab.c | 100 ++++++-------------------------------------
5 files changed, 211 insertions(+), 132 deletions(-)
create mode 100644 gdb/filename-seen-cache.c
create mode 100644 gdb/filename-seen-cache.h

diff --git a/gdb/Makefile.in b/gdb/Makefile.in
index 8be73ba..380df11 100644
--- a/gdb/Makefile.in
+++ b/gdb/Makefile.in
@@ -1705,6 +1705,7 @@ COMMON_OBS = $(DEPFILES) $(CONFIG_OBS) $(YYOBJ) \
f-typeprint.o \
f-valprint.o \
fileio.o \
+ filename-seen-cache.o \
filestuff.o \
filesystem.o \
findcmd.o \
diff --git a/gdb/dwarf2read.c b/gdb/dwarf2read.c
index cb33fc9..439257f 100644
--- a/gdb/dwarf2read.c
+++ b/gdb/dwarf2read.c
@@ -73,10 +73,10 @@
#include "common/function-view.h"
#include "common/gdb_optional.h"
#include "common/underlying.h"
-
#include <fcntl.h>
#include <sys/types.h>
#include <algorithm>
+#include "filename-seen-cache.h"

typedef struct symbol *symbolp;
DEF_VEC_P (symbolp);
@@ -324,6 +324,9 @@ struct dwarf2_per_objfile

/* Table containing line_header indexed by offset and offset_in_dwz. */
htab_t line_header_hash;
+
+ /* Table containing all filenames. */
+ filename_seen_cache *filenames_cache;
};

static struct dwarf2_per_objfile *dwarf2_per_objfile;
@@ -4256,64 +4259,76 @@ static void
dw2_map_symbol_filenames (struct objfile *objfile, symbol_filename_ftype *fun,
void *data, int need_fullname)
{
- int i;
- htab_up visited (htab_create_alloc (10, htab_hash_pointer, htab_eq_pointer,
- NULL, xcalloc, xfree));
-
dw2_setup (objfile);

- /* The rule is CUs specify all the files, including those used by
- any TU, so there's no need to scan TUs here.
- We can ignore file names coming from already-expanded CUs. */
-
- for (i = 0; i < dwarf2_per_objfile->n_comp_units; ++i)
+ if (dwarf2_per_objfile->filenames_cache == NULL)
{
- struct dwarf2_per_cu_data *per_cu = dw2_get_cutu (i);
+ dwarf2_per_objfile->filenames_cache = new filename_seen_cache ();

- if (per_cu->v.quick->compunit_symtab)
- {
- void **slot = htab_find_slot (visited.get (),
- per_cu->v.quick->file_names,
- INSERT);
+ htab_up visited (htab_create_alloc (10,
+ htab_hash_pointer, htab_eq_pointer,
+ NULL, xcalloc, xfree));

- *slot = per_cu->v.quick->file_names;
- }
- }
-
- for (i = 0; i < dwarf2_per_objfile->n_comp_units; ++i)
- {
- int j;
- struct dwarf2_per_cu_data *per_cu = dw2_get_cu (i);
- struct quick_file_names *file_data;
- void **slot;
+ /* The rule is CUs specify all the files, including those used
+ by any TU, so there's no need to scan TUs here. We can
+ ignore file names coming from already-expanded CUs. */

- /* We only need to look at symtabs not already expanded. */
- if (per_cu->v.quick->compunit_symtab)
- continue;
+ for (int i = 0; i < dwarf2_per_objfile->n_comp_units; ++i)
+ {
+ struct dwarf2_per_cu_data *per_cu = dw2_get_cutu (i);

- file_data = dw2_get_file_names (per_cu);
- if (file_data == NULL)
- continue;
+ if (per_cu->v.quick->compunit_symtab)
+ {
+ void **slot = htab_find_slot (visited.get (),
+ per_cu->v.quick->file_names,
+ INSERT);

- slot = htab_find_slot (visited.get (), file_data, INSERT);
- if (*slot)
- {
- /* Already visited. */
- continue;
+ *slot = per_cu->v.quick->file_names;
+ }
}
- *slot = file_data;

- for (j = 0; j < file_data->num_file_names; ++j)
+ for (int i = 0; i < dwarf2_per_objfile->n_comp_units; ++i)
{
- const char *this_real_name;
+ int j;
+ struct dwarf2_per_cu_data *per_cu = dw2_get_cu (i);
+ struct quick_file_names *file_data;
+ void **slot;

- if (need_fullname)
- this_real_name = dw2_get_real_path (objfile, file_data, j);
- else
- this_real_name = NULL;
- (*fun) (file_data->file_names[j], this_real_name, data);
+ /* We only need to look at symtabs not already expanded. */
+ if (per_cu->v.quick->compunit_symtab)
+ continue;
+
+ file_data = dw2_get_file_names (per_cu);
+ if (file_data == NULL)
+ continue;
+
+ slot = htab_find_slot (visited.get (), file_data, INSERT);
+ if (*slot)
+ {
+ /* Already visited. */
+ continue;
+ }
+ *slot = file_data;
+
+ for (int j = 0; j < file_data->num_file_names; ++j)
+ {
+ const char *filename = file_data->file_names[j];
+ dwarf2_per_objfile->filenames_cache->filename_seen (filename,
+ true);
+ }
}
}
+
+ dwarf2_per_objfile->filenames_cache->traverse ([&] (const char *filename)
+ {
+ const char *this_real_name;
+
+ if (need_fullname)
+ this_real_name = gdb_realpath (filename);
+ else
+ this_real_name = NULL;
+ (*fun) (filename, this_real_name, data);
+ });
}

static int
diff --git a/gdb/filename-seen-cache.c b/gdb/filename-seen-cache.c
new file mode 100644
index 0000000..e04c7de
--- /dev/null
+++ b/gdb/filename-seen-cache.c
@@ -0,0 +1,73 @@
+/* Filename-seen cache for the GNU debugger, GDB.
+
+ Copyright (C) 1986-2017 Free Software Foundation, Inc.
+
+ This file is part of GDB.
+
+ This program is free software; you can redistribute it and/or modify
+ it under the terms of the GNU General Public License as published by
+ the Free Software Foundation; either version 3 of the License, or
+ (at your option) any later version.
+
+ This program is distributed in the hope that it will be useful,
+ but WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ GNU General Public License for more details.
+
+ You should have received a copy of the GNU General Public License
+ along with this program. If not, see <http://www.gnu.org/licenses/>. */
+
+#include "defs.h"
+#include "filename-seen-cache.h"
+#include "filenames.h"
+
+ /* Initial size of the table. It automagically grows from here. */
+#define INITIAL_FILENAME_SEEN_CACHE_SIZE 100
+
+/* filename_seen_cache constructor. */
+
+filename_seen_cache::filename_seen_cache ()
+{
+ m_tab = htab_create_alloc (INITIAL_FILENAME_SEEN_CACHE_SIZE,
+ filename_hash, filename_eq,
+ NULL, xcalloc, xfree);
+}
+
+/* Empty the cache, but do not delete it. */
+
+void
+filename_seen_cache::clear ()
+{
+ htab_empty (m_tab);
+}
+
+/* filename_seen_cache destructor. */
+
+filename_seen_cache::~filename_seen_cache ()
+{
+ htab_delete (m_tab);
+}
+
+/* If FILE is not already in the table of files in CACHE, return zero;
+ otherwise return non-zero. Optionally add FILE to the table if ADD
+ is non-zero.
+
+ NOTE: We don't manage space for FILE, we assume FILE lives as long
+ as the caller needs. */
+
+bool
+filename_seen_cache::filename_seen (const char *file, bool add)
+{
+ void **slot;
+
+ /* Is FILE in tab? */
+ slot = htab_find_slot (m_tab, file, add ? INSERT : NO_INSERT);
+ if (*slot != NULL)
+ return true;
+
+ /* No; maybe add it to tab. */
+ if (add)
+ *slot = (char *) file;
+
+ return false;
+}
diff --git a/gdb/filename-seen-cache.h b/gdb/filename-seen-cache.h
new file mode 100644
index 0000000..c041d3e
--- /dev/null
+++ b/gdb/filename-seen-cache.h
@@ -0,0 +1,64 @@
+/* Filename-seen cache for the GNU debugger, GDB.
+
+ Copyright (C) 1986-2017 Free Software Foundation, Inc.
+
+ This file is part of GDB.
+
+ This program is free software; you can redistribute it and/or modify
+ it under the terms of the GNU General Public License as published by
+ the Free Software Foundation; either version 3 of the License, or
+ (at your option) any later version.
+
+ This program is distributed in the hope that it will be useful,
+ but WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ GNU General Public License for more details.
+
+ You should have received a copy of the GNU General Public License
+ along with this program. If not, see <http://www.gnu.org/licenses/>. */
+
+#include "defs.h"
+#include "common/function-view.h"
+
+/* Cache to watch for file names already seen. */
+
+class filename_seen_cache
+{
+public:
+ filename_seen_cache ();
+ ~filename_seen_cache ();
+
+ /* Disable copy. */
+ filename_seen_cache (const filename_seen_cache &) = delete;
+ void operator= (const filename_seen_cache &) = delete;
+
+ /* Empty the cache, but do not delete it. */
+ void clear ();
+
+ /* If FILE is not already in the table of files in CACHE, return
+ false; otherwise return true. Optionally add FILE to the table
+ if ADD is true.
+
+ NOTE: We don't manage space for FILE, we assume FILE lives as
+ long as the caller needs. */
+ bool filename_seen (const char *file, bool add);
+
+ /* Traverse all cache entries, calling CALLBACK on each. The
+ filename is passed as argument to CALLBACK. */
+ void traverse (gdb::function_view<void (const char *)> callback)
+ {
+ htab_traverse_noresize (m_tab,
+ [] (void **slot, void *info) -> int
+ {
+ auto filename = (const char *) *slot;
+ auto cb = (gdb::function_view<void (const char *)> *) info;
+ (*cb) (filename);
+ return 1;
+ },
+ &callback);
+ }
+
+private:
+ /* Table of files seen so far. */
+ htab_t m_tab;
+};
diff --git a/gdb/symtab.c b/gdb/symtab.c
index 69f3bc2..4414d71 100644
--- a/gdb/symtab.c
+++ b/gdb/symtab.c
@@ -62,6 +62,7 @@
#include "parser-defs.h"
#include "completer.h"
#include "progspace-and-thread.h"
+#include "filename-seen-cache.h"

/* Forward declarations for local functions. */

@@ -3966,74 +3967,6 @@ operator_chars (const char *p, const char **end)
}
\f

-/* Cache to watch for file names already seen by filename_seen. */
-
-struct filename_seen_cache
-{
- /* Table of files seen so far. */
- htab_t tab;
- /* Initial size of the table. It automagically grows from here. */
-#define INITIAL_FILENAME_SEEN_CACHE_SIZE 100
-};
-
-/* filename_seen_cache constructor. */
-
-static struct filename_seen_cache *
-create_filename_seen_cache (void)
-{
- struct filename_seen_cache *cache = XNEW (struct filename_seen_cache);
-
- cache->tab = htab_create_alloc (INITIAL_FILENAME_SEEN_CACHE_SIZE,
- filename_hash, filename_eq,
- NULL, xcalloc, xfree);
-
- return cache;
-}
-
-/* Empty the cache, but do not delete it. */
-
-static void
-clear_filename_seen_cache (struct filename_seen_cache *cache)
-{
- htab_empty (cache->tab);
-}
-
-/* filename_seen_cache destructor.
- This takes a void * argument as it is generally used as a cleanup. */
-
-static void
-delete_filename_seen_cache (void *ptr)
-{
- struct filename_seen_cache *cache = (struct filename_seen_cache *) ptr;
-
- htab_delete (cache->tab);
- xfree (cache);
-}
-
-/* If FILE is not already in the table of files in CACHE, return zero;
- otherwise return non-zero. Optionally add FILE to the table if ADD
- is non-zero.
-
- NOTE: We don't manage space for FILE, we assume FILE lives as long
- as the caller needs. */
-
-static int
-filename_seen (struct filename_seen_cache *cache, const char *file, int add)
-{
- void **slot;
-
- /* Is FILE in tab? */
- slot = htab_find_slot (cache->tab, file, add ? INSERT : NO_INSERT);
- if (*slot != NULL)
- return 1;
-
- /* No; maybe add it to tab. */
- if (add)
- *slot = (char *) file;
-
- return 0;
-}
-
/* Data structure to maintain printing state for output_source_filename. */

struct output_source_filename_data
@@ -4063,7 +3996,7 @@ output_source_filename (const char *name,
symtabs; it doesn't hurt to check. */

/* Was NAME already seen? */
- if (filename_seen (data->filename_seen_cache, name, 1))
+ if (data->filename_seen_cache->filename_seen (name, true))
{
/* Yes; don't print it again. */
return;
@@ -4095,16 +4028,15 @@ sources_info (char *ignore, int from_tty)
struct symtab *s;
struct objfile *objfile;
struct output_source_filename_data data;
- struct cleanup *cleanups;

if (!have_full_symbols () && !have_partial_symbols ())
{
error (_("No symbol table is loaded. Use the \"file\" command."));
}

- data.filename_seen_cache = create_filename_seen_cache ();
- cleanups = make_cleanup (delete_filename_seen_cache,
- data.filename_seen_cache);
+ filename_seen_cache filenames_seen;
+
+ data.filename_seen_cache = &filenames_seen;

printf_filtered ("Source files for which symbols have been read in:\n\n");

@@ -4120,13 +4052,11 @@ sources_info (char *ignore, int from_tty)
printf_filtered ("Source files for which symbols "
"will be read in on demand:\n\n");

- clear_filename_seen_cache (data.filename_seen_cache);
+ filenames_seen.clear ();
data.first = 1;
map_symbol_filenames (output_partial_symbol_filename, &data,
1 /*need_fullname*/);
printf_filtered ("\n");
-
- do_cleanups (cleanups);
}

/* Compare FILE against all the NFILES entries of FILES. If BASENAMES is
@@ -5551,7 +5481,7 @@ maybe_add_partial_symtab_filename (const char *filename, const char *fullname,

if (not_interesting_fname (filename))
return;
- if (!filename_seen (data->filename_seen_cache, filename, 1)
+ if (!data->filename_seen_cache->filename_seen (filename, true)
&& filename_ncmp (filename, data->text, data->text_len) == 0)
{
/* This file matches for a completion; add it to the
@@ -5563,7 +5493,7 @@ maybe_add_partial_symtab_filename (const char *filename, const char *fullname,
const char *base_name = lbasename (filename);

if (base_name != filename
- && !filename_seen (data->filename_seen_cache, base_name, 1)
+ && !data->filename_seen_cache->filename_seen (base_name, true)
&& filename_ncmp (base_name, data->text, data->text_len) == 0)
add_filename_to_list (base_name, data->text, data->word, data->list);
}
@@ -5584,23 +5514,20 @@ make_source_files_completion_list (const char *text, const char *word)
VEC (char_ptr) *list = NULL;
const char *base_name;
struct add_partial_filename_data datum;
- struct filename_seen_cache *filename_seen_cache;
- struct cleanup *back_to, *cache_cleanup;
+ struct cleanup *back_to;

if (!have_full_symbols () && !have_partial_symbols ())
return list;

back_to = make_cleanup (do_free_completion_list, &list);

- filename_seen_cache = create_filename_seen_cache ();
- cache_cleanup = make_cleanup (delete_filename_seen_cache,
- filename_seen_cache);
+ filename_seen_cache filenames_seen;

ALL_FILETABS (objfile, cu, s)
{
if (not_interesting_fname (s->filename))
continue;
- if (!filename_seen (filename_seen_cache, s->filename, 1)
+ if (!filenames_seen.filename_seen (s->filename, true)
&& filename_ncmp (s->filename, text, text_len) == 0)
{
/* This file matches for a completion; add it to the current
@@ -5615,13 +5542,13 @@ make_source_files_completion_list (const char *text, const char *word)
command do when they parse file names. */
base_name = lbasename (s->filename);
if (base_name != s->filename
- && !filename_seen (filename_seen_cache, base_name, 1)
+ && !filenames_seen.filename_seen (base_name, true)
&& filename_ncmp (base_name, text, text_len) == 0)
add_filename_to_list (base_name, text, word, &list);
}
}

- datum.filename_seen_cache = filename_seen_cache;
+ datum.filename_seen_cache = &filenames_seen;
datum.text = text;
datum.word = word;
datum.text_len = text_len;
@@ -5629,7 +5556,6 @@ make_source_files_completion_list (const char *text, const char *word)
map_symbol_filenames (maybe_add_partial_symtab_filename, &datum,
0 /*need_fullname*/);

- do_cleanups (cache_cleanup);
discard_cleanups (back_to);

return list;
--
2.5.5