aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorChristian Biesinger <cbiesinger@google.com>2019-09-26 14:45:47 -0500
committerChristian Biesinger <cbiesinger@google.com>2019-09-26 14:46:16 -0500
commitf55c45b19bbfa2ab3a9d0ff703e4ad589e5fe4df (patch)
tree2de7e76fb1819a51b3f0cee972f565e579c09368
parentececd218c5254902db3301d700546f6702112c85 (diff)
downloadgdb-users/cbiesinger/stl_minsyms_hash.zip
gdb-users/cbiesinger/stl_minsyms_hash.tar.gz
gdb-users/cbiesinger/stl_minsyms_hash.tar.bz2
Try converting ad-hoc msymbol hash tables to STL containersusers/cbiesinger/stl_minsyms_hash
I went with multimap (also tried unordered_multimap) to keep the behavior where we have a special hash key and want to iterate over everything with that hash using specialized compare functions. Unfortunately this is a 10% regression. real 0m56.538s user 0m34.304s sys 0m22.380s real 0m51.655s user 0m32.194s sys 0m19.528s
-rw-r--r--gdb/minsyms.c107
-rw-r--r--gdb/objfiles.h10
-rw-r--r--gdb/symtab.h10
3 files changed, 51 insertions, 76 deletions
diff --git a/gdb/minsyms.c b/gdb/minsyms.c
index f06de4d..871a281 100644
--- a/gdb/minsyms.c
+++ b/gdb/minsyms.c
@@ -136,16 +136,12 @@ msymbol_hash (const char *string)
/* Add the minimal symbol SYM to an objfile's minsym hash table, TABLE. */
static void
add_minsym_to_hash_table (struct minimal_symbol *sym,
- struct minimal_symbol **table)
+ minsym_hash_table *table)
{
- if (sym->hash_next == NULL)
- {
- unsigned int hash
- = msymbol_hash (MSYMBOL_LINKAGE_NAME (sym)) % MINIMAL_SYMBOL_HASH_SIZE;
+ unsigned int hash
+ = msymbol_hash (MSYMBOL_LINKAGE_NAME (sym)) % MINIMAL_SYMBOL_HASH_SIZE;
- sym->hash_next = table[hash];
- table[hash] = sym;
- }
+ table->insert (std::make_pair (hash, sym));
}
/* Add the minimal symbol SYM to an objfile's minsym demangled hash table,
@@ -154,19 +150,11 @@ static void
add_minsym_to_demangled_hash_table (struct minimal_symbol *sym,
struct objfile *objfile)
{
- if (sym->demangled_hash_next == NULL)
- {
- unsigned int hash = search_name_hash (MSYMBOL_LANGUAGE (sym),
- MSYMBOL_SEARCH_NAME (sym));
-
- objfile->per_bfd->demangled_hash_languages.set (MSYMBOL_LANGUAGE (sym));
+ unsigned int hash = search_name_hash (MSYMBOL_LANGUAGE (sym),
+ MSYMBOL_SEARCH_NAME (sym));
- struct minimal_symbol **table
- = objfile->per_bfd->msymbol_demangled_hash;
- unsigned int hash_index = hash % MINIMAL_SYMBOL_HASH_SIZE;
- sym->demangled_hash_next = table[hash_index];
- table[hash_index] = sym;
- }
+ objfile->per_bfd->demangled_hash_languages.set (MSYMBOL_LANGUAGE (sym));
+ objfile->per_bfd->msymbol_demangled_hash.insert (std::make_pair (hash, sym));
}
/* Worker object for lookup_minimal_symbol. Stores temporary results
@@ -243,19 +231,18 @@ static void
lookup_minimal_symbol_mangled (const char *lookup_name,
const char *sfile,
struct objfile *objfile,
- struct minimal_symbol **table,
+ minsym_hash_table *table,
unsigned int hash,
int (*namecmp) (const char *, const char *),
found_minimal_symbols &found)
{
- for (minimal_symbol *msymbol = table[hash];
- msymbol != NULL;
- msymbol = msymbol->hash_next)
+ auto range = table->equal_range(hash);
+ for (auto it = range.first; it != range.second; ++it)
{
- const char *symbol_name = MSYMBOL_LINKAGE_NAME (msymbol);
+ const char *symbol_name = MSYMBOL_LINKAGE_NAME (it->second);
if (namecmp (symbol_name, lookup_name) == 0
- && found.maybe_collect (sfile, objfile, msymbol))
+ && found.maybe_collect (sfile, objfile, it->second))
return;
}
}
@@ -267,19 +254,18 @@ static void
lookup_minimal_symbol_demangled (const lookup_name_info &lookup_name,
const char *sfile,
struct objfile *objfile,
- struct minimal_symbol **table,
+ minsym_hash_table *table,
unsigned int hash,
symbol_name_matcher_ftype *matcher,
found_minimal_symbols &found)
{
- for (minimal_symbol *msymbol = table[hash];
- msymbol != NULL;
- msymbol = msymbol->demangled_hash_next)
+ auto range = table->equal_range(hash);
+ for (auto it = range.first; it != range.second; ++it)
{
- const char *symbol_name = MSYMBOL_SEARCH_NAME (msymbol);
+ const char *symbol_name = MSYMBOL_SEARCH_NAME (it->second);
- if (matcher (symbol_name, lookup_name, NULL)
- && found.maybe_collect (sfile, objfile, msymbol))
+ if (matcher (symbol_name, lookup_name, NULL) == 0
+ && found.maybe_collect (sfile, objfile, it->second))
return;
}
}
@@ -341,7 +327,7 @@ lookup_minimal_symbol (const char *name, const char *sfile,
/* Do two passes: the first over the ordinary hash table,
and the second over the demangled hash table. */
lookup_minimal_symbol_mangled (name, sfile, objfile,
- objfile->per_bfd->msymbol_hash,
+ &objfile->per_bfd->msymbol_hash,
mangled_hash, mangled_cmp, found);
/* If not found, try the demangled hash table. */
@@ -362,8 +348,8 @@ lookup_minimal_symbol (const char *name, const char *sfile,
symbol_name_matcher_ftype *match
= get_symbol_name_matcher (language_def (lang),
lookup_name);
- struct minimal_symbol **msymbol_demangled_hash
- = objfile->per_bfd->msymbol_demangled_hash;
+ minsym_hash_table *msymbol_demangled_hash
+ = &objfile->per_bfd->msymbol_demangled_hash;
lookup_minimal_symbol_demangled (lookup_name, sfile, objfile,
msymbol_demangled_hash,
@@ -483,12 +469,11 @@ iterate_over_minimal_symbols
? strcmp
: strcasecmp);
- for (minimal_symbol *iter = objf->per_bfd->msymbol_hash[hash];
- iter != NULL;
- iter = iter->hash_next)
+ auto range = objf->per_bfd->msymbol_hash.equal_range(hash);
+ for (auto iter = range.first; iter != range.second; ++iter)
{
- if (mangled_cmp (MSYMBOL_LINKAGE_NAME (iter), name) == 0)
- if (callback (iter))
+ if (mangled_cmp (MSYMBOL_LINKAGE_NAME (iter->second), name) == 0)
+ if (callback (iter->second))
return;
}
}
@@ -505,15 +490,15 @@ iterate_over_minimal_symbols
const language_defn *lang_def = language_def (lang);
symbol_name_matcher_ftype *name_match
= get_symbol_name_matcher (lang_def, lookup_name);
-
unsigned int hash
= lookup_name.search_name_hash (lang) % MINIMAL_SYMBOL_HASH_SIZE;
- for (minimal_symbol *iter = objf->per_bfd->msymbol_demangled_hash[hash];
- iter != NULL;
- iter = iter->demangled_hash_next)
- if (name_match (MSYMBOL_SEARCH_NAME (iter), lookup_name, NULL))
- if (callback (iter))
- return;
+ auto range = objf->per_bfd->msymbol_demangled_hash.equal_range(hash);
+ for (auto iter = range.first; iter != range.second; ++iter)
+ {
+ if (name_match (MSYMBOL_SEARCH_NAME (iter->second), lookup_name, NULL) == 0)
+ if (callback (iter->second))
+ return;
+ }
}
}
@@ -536,10 +521,10 @@ lookup_minimal_symbol_text (const char *name, struct objfile *objf)
if (objf == NULL || objf == objfile
|| objf == objfile->separate_debug_objfile_backlink)
{
- for (msymbol = objfile->per_bfd->msymbol_hash[hash];
- msymbol != NULL && found_symbol.minsym == NULL;
- msymbol = msymbol->hash_next)
+ auto range = objfile->per_bfd->msymbol_hash.equal_range(hash);
+ for (auto it = range.first; it != range.second; ++it)
{
+ msymbol = it->second;
if (strcmp (MSYMBOL_LINKAGE_NAME (msymbol), name) == 0 &&
(MSYMBOL_TYPE (msymbol) == mst_text
|| MSYMBOL_TYPE (msymbol) == mst_text_gnu_ifunc
@@ -583,10 +568,10 @@ lookup_minimal_symbol_by_pc_name (CORE_ADDR pc, const char *name,
if (objf == NULL || objf == objfile
|| objf == objfile->separate_debug_objfile_backlink)
{
- for (msymbol = objfile->per_bfd->msymbol_hash[hash];
- msymbol != NULL;
- msymbol = msymbol->hash_next)
+ auto range = objfile->per_bfd->msymbol_hash.equal_range(hash);
+ for (auto it = range.first; it != range.second; ++it)
{
+ msymbol = it->second;
if (MSYMBOL_VALUE_ADDRESS (objfile, msymbol) == pc
&& strcmp (MSYMBOL_LINKAGE_NAME (msymbol), name) == 0)
return msymbol;
@@ -1222,7 +1207,7 @@ compact_minimal_symbols (struct minimal_symbol *msymbol, int mcount,
return (mcount);
}
-/* Build (or rebuild) the minimal symbol hash tables. This is necessary
+/* Build the minimal symbol hash tables. This is necessary
after compacting or sorting the table since the entries move around
thus causing the internal minimal_symbol pointers to become jumbled. */
@@ -1232,12 +1217,8 @@ build_minimal_symbol_hash_tables (struct objfile *objfile)
int i;
struct minimal_symbol *msym;
- /* Clear the hash tables. */
- for (i = 0; i < MINIMAL_SYMBOL_HASH_SIZE; i++)
- {
- objfile->per_bfd->msymbol_hash[i] = 0;
- objfile->per_bfd->msymbol_demangled_hash[i] = 0;
- }
+ gdb_assert (objfile->per_bfd->msymbol_hash.empty ());
+ gdb_assert (objfile->per_bfd->msymbol_demangled_hash.empty ());
/* Now, (re)insert the actual entries. */
for ((i = objfile->per_bfd->minimal_symbol_count,
@@ -1245,10 +1226,8 @@ build_minimal_symbol_hash_tables (struct objfile *objfile)
i > 0;
i--, msym++)
{
- msym->hash_next = 0;
- add_minsym_to_hash_table (msym, objfile->per_bfd->msymbol_hash);
+ add_minsym_to_hash_table (msym, &objfile->per_bfd->msymbol_hash);
- msym->demangled_hash_next = 0;
if (MSYMBOL_SEARCH_NAME (msym) != MSYMBOL_LINKAGE_NAME (msym))
add_minsym_to_demangled_hash_table (msym, objfile);
}
diff --git a/gdb/objfiles.h b/gdb/objfiles.h
index 68d36d4..4d55a86 100644
--- a/gdb/objfiles.h
+++ b/gdb/objfiles.h
@@ -29,6 +29,8 @@
#include "gdb_bfd.h"
#include "psymtab.h"
#include <bitset>
+#include <map>
+#include <unordered_map>
#include <vector>
#include "gdbsupport/next-iterator.h"
#include "gdbsupport/safe-iterator.h"
@@ -230,10 +232,14 @@ private:
instance of this structure, and associated with the BFD using the
registry system. */
+// Maps hash -> symbol
+typedef std::unordered_multimap<unsigned int, struct minimal_symbol *> minsym_hash_table;
struct objfile_per_bfd_storage
{
objfile_per_bfd_storage ()
: minsyms_read (false)
+ , msymbol_hash(MINIMAL_SYMBOL_HASH_SIZE)
+ , msymbol_demangled_hash(MINIMAL_SYMBOL_HASH_SIZE)
{}
~objfile_per_bfd_storage ();
@@ -307,12 +313,12 @@ struct objfile_per_bfd_storage
/* This is a hash table used to index the minimal symbols by name. */
- minimal_symbol *msymbol_hash[MINIMAL_SYMBOL_HASH_SIZE] {};
+ minsym_hash_table msymbol_hash;
/* This hash table is used to index the minimal symbols by their
demangled names. */
- minimal_symbol *msymbol_demangled_hash[MINIMAL_SYMBOL_HASH_SIZE] {};
+ minsym_hash_table msymbol_demangled_hash;
/* All the different languages of symbols found in the demangled
hash table. */
diff --git a/gdb/symtab.h b/gdb/symtab.h
index 1f0fc62..f53cfa0 100644
--- a/gdb/symtab.h
+++ b/gdb/symtab.h
@@ -669,16 +669,6 @@ struct minimal_symbol : public general_symbol_info
the object file format may not carry that piece of information. */
unsigned int has_size : 1;
- /* Minimal symbols with the same hash key are kept on a linked
- list. This is the link. */
-
- struct minimal_symbol *hash_next;
-
- /* Minimal symbols are stored in two different hash tables. This is
- the `next' pointer for the demangled hash table. */
-
- struct minimal_symbol *demangled_hash_next;
-
/* True if this symbol is of some data type. */
bool data_p () const;