From f55c45b19bbfa2ab3a9d0ff703e4ad589e5fe4df Mon Sep 17 00:00:00 2001 From: Christian Biesinger Date: Thu, 26 Sep 2019 14:45:47 -0500 Subject: Try converting ad-hoc msymbol hash tables to STL containers 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 --- gdb/minsyms.c | 107 +++++++++++++++++++++++---------------------------------- gdb/objfiles.h | 10 ++++-- gdb/symtab.h | 10 ------ 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 +#include +#include #include #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 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; -- cgit v1.1