From 2b5a48b6a9dddd6a2f7d189f3fa906adcab51b92 Mon Sep 17 00:00:00 2001 From: Simon Marchi Date: Tue, 25 Feb 2025 15:54:55 -0500 Subject: [PATCH] gdb/dwarf: convert dwarf2_per_bfd::signatured_types to a gdb::unordered_set I'd like to add these asserts in dwarf2_per_cu_data's constructor: gdb_assert (per_bfd != nullptr); gdb_assert (section != nullptr); However, these dummy instances of signatured_type, used as hash table lookup keys, are in the way: signatured_type find_sig_entry (nullptr, nullptr, sect_offset {}, sig); This motivated me to convert the dwarf2_per_bfd::signatured_types hash table to a gdb::unordered_set. This allows finding an entry by simply passing the signature (an integer) and removes the need to create dummy signatured_type objects. There is one small unfortunate pessimization: lookup_dwo_signatured_type, for instance, does a lookup by signature to find an existing signatured_type. If not found, it adds a new one by calling add_type_unit. The current code passes down the slot where to put the new element, avoiding an extra hash when inserting the new signatured_type. With the new code, I don't see a way to do that. This is probably negligible, but it bugs me. If we used a map of signature -> signatured_type, I would see a way, but then it would waste space. I see one change in behavior, that is not really important IMO. In read_comp_units_from_section, if duplicate signature type entries are detected, the code prior to this patch overwrites the existing signatured_type in the hash table with the new one. With this patch, the existing signatured_type is kept: the call to emplace does not insert the value if an existing equal value exists. Other than that, no behavior change expected. Change-Id: I0bef1b49cc63dbdf4e32fa9d4ea37f83025efc3e Approved-By: Tom Tromey --- gdb/dwarf2/read-gdb-index.c | 18 ++-- gdb/dwarf2/read.c | 177 ++++++++++++------------------------ gdb/dwarf2/read.h | 43 +++++++-- 3 files changed, 102 insertions(+), 136 deletions(-) diff --git a/gdb/dwarf2/read-gdb-index.c b/gdb/dwarf2/read-gdb-index.c index 6c01c7ad64e..ff60e9b862c 100644 --- a/gdb/dwarf2/read-gdb-index.c +++ b/gdb/dwarf2/read-gdb-index.c @@ -1360,31 +1360,25 @@ create_signatured_type_table_from_gdb_index (dwarf2_per_bfd *per_bfd, struct dwarf2_section_info *section, const gdb_byte *bytes, offset_type elements) { - htab_up sig_types_hash = allocate_signatured_type_table (); + signatured_type_set sig_types_hash; for (offset_type i = 0; i < elements; i += 3) { - signatured_type_up sig_type; - ULONGEST signature; - void **slot; - cu_offset type_offset_in_tu; - static_assert (sizeof (ULONGEST) >= 8); sect_offset sect_off = (sect_offset) extract_unsigned_integer (bytes, 8, BFD_ENDIAN_LITTLE); - type_offset_in_tu + cu_offset type_offset_in_tu = (cu_offset) extract_unsigned_integer (bytes + 8, 8, BFD_ENDIAN_LITTLE); - signature = extract_unsigned_integer (bytes + 16, 8, BFD_ENDIAN_LITTLE); + ULONGEST signature + = extract_unsigned_integer (bytes + 16, 8, BFD_ENDIAN_LITTLE); bytes += 3 * 8; - sig_type + signatured_type_up sig_type = per_bfd->allocate_signatured_type (section, sect_off, signature); sig_type->type_offset_in_tu = type_offset_in_tu; - slot = htab_find_slot (sig_types_hash.get (), sig_type.get (), INSERT); - *slot = sig_type.get (); - + sig_types_hash.emplace (sig_type.get ()); per_bfd->all_units.emplace_back (sig_type.release ()); } diff --git a/gdb/dwarf2/read.c b/gdb/dwarf2/read.c index d115ff39928..27f4f09685f 100644 --- a/gdb/dwarf2/read.c +++ b/gdb/dwarf2/read.c @@ -2570,36 +2570,6 @@ read_abbrev_offset (dwarf2_per_objfile *per_objfile, return (sect_offset) read_offset (abfd, info_ptr, offset_size); } -static hashval_t -hash_signatured_type (const void *item) -{ - const struct signatured_type *sig_type - = (const struct signatured_type *) item; - - /* This drops the top 32 bits of the signature, but is ok for a hash. */ - return sig_type->signature; -} - -static int -eq_signatured_type (const void *item_lhs, const void *item_rhs) -{ - const struct signatured_type *lhs = (const struct signatured_type *) item_lhs; - const struct signatured_type *rhs = (const struct signatured_type *) item_rhs; - - return lhs->signature == rhs->signature; -} - -/* See read.h. */ - -htab_up -allocate_signatured_type_table () -{ - return htab_up (htab_create_alloc (41, - hash_signatured_type, - eq_signatured_type, - NULL, xcalloc, xfree)); -} - /* A helper for create_debug_types_hash_table. Read types from SECTION and fill them into TYPES_HTAB. It will process only type units, therefore DW_UT_type. */ @@ -2716,13 +2686,11 @@ create_debug_types_hash_table (dwarf2_per_objfile *per_objfile, rcuh_kind::TYPE); } -/* Add an entry for signature SIG to per_bfd->signatured_types. - If SLOT is non-NULL, it is the entry to use in the hash table. - Otherwise we find one. */ +/* Add an entry for signature SIG to per_bfd->signatured_types. */ -static struct signatured_type * +static signatured_type_set::iterator add_type_unit (dwarf2_per_bfd *per_bfd, dwarf2_section_info *section, - sect_offset sect_off, ULONGEST sig, void **slot) + sect_offset sect_off, ULONGEST sig) { if (per_bfd->all_units.size () == per_bfd->all_units.capacity ()) ++per_bfd->tu_stats.nr_all_type_units_reallocs; @@ -2732,14 +2700,14 @@ add_type_unit (dwarf2_per_bfd *per_bfd, dwarf2_section_info *section, signatured_type *sig_type = sig_type_holder.get (); per_bfd->all_units.emplace_back (sig_type_holder.release ()); + auto emplace_ret = per_bfd->signatured_types.emplace (sig_type); - if (slot == NULL) - slot = htab_find_slot (per_bfd->signatured_types.get (), sig_type, INSERT); + /* Assert that an insertion took place - that there wasn't a type unit with + that signature already. */ + gdb_assert (emplace_ret.second); - gdb_assert (*slot == NULL); - *slot = sig_type; /* The rest of sig_type must be filled in by the caller. */ - return sig_type; + return emplace_ret.first; } /* Subroutine of lookup_dwo_signatured_type and lookup_dwp_signatured_type. @@ -2785,27 +2753,16 @@ lookup_dwo_signatured_type (struct dwarf2_cu *cu, ULONGEST sig) { dwarf2_per_objfile *per_objfile = cu->per_objfile; dwarf2_per_bfd *per_bfd = per_objfile->per_bfd; - struct dwo_file *dwo_file; - struct dwo_unit find_dwo_entry, *dwo_entry; - void **slot; gdb_assert (cu->dwo_unit); - /* If TU skeletons have been removed then we may not have read in any - TUs yet. */ - if (per_bfd->signatured_types == NULL) - per_bfd->signatured_types = allocate_signatured_type_table (); - /* We only ever need to read in one copy of a signatured type. Use the global signatured_types array to do our own comdat-folding of types. If this is the first time we're reading this TU, and the TU has an entry in .gdb_index, replace the recorded data from .gdb_index with this TU. */ - signatured_type find_sig_entry (nullptr, nullptr, sect_offset {}, sig); - slot = htab_find_slot (per_bfd->signatured_types.get (), &find_sig_entry, - INSERT); - signatured_type *sig_entry = (struct signatured_type *) *slot; + auto sig_type_it = per_bfd->signatured_types.find (sig); /* We can get here with the TU already read, *or* in the process of being read. Don't reassign the global entry to point to this DWO if that's @@ -2816,31 +2773,36 @@ lookup_dwo_signatured_type (struct dwarf2_cu *cu, ULONGEST sig) /* Have we already tried to read this TU? Note: sig_entry can be NULL if the skeleton TU was removed (thus it needn't exist in the global table yet). */ - if (sig_entry != NULL && sig_entry->tu_read) - return sig_entry; + if (sig_type_it != per_bfd->signatured_types.end () + && (*sig_type_it)->tu_read) + return *sig_type_it; /* Note: cu->dwo_unit is the dwo_unit that references this TU, not the dwo_unit of the TU itself. */ - dwo_file = cu->dwo_unit->dwo_file; + dwo_file *dwo_file = cu->dwo_unit->dwo_file; /* Ok, this is the first time we're reading this TU. */ if (dwo_file->tus == NULL) return NULL; + + dwo_unit find_dwo_entry; find_dwo_entry.signature = sig; - dwo_entry = (struct dwo_unit *) htab_find (dwo_file->tus.get (), - &find_dwo_entry); + auto dwo_entry + = (struct dwo_unit *) htab_find (dwo_file->tus.get (), &find_dwo_entry); + if (dwo_entry == NULL) return NULL; /* If the global table doesn't have an entry for this TU, add one. */ - if (sig_entry == NULL) - sig_entry = add_type_unit (per_bfd, dwo_entry->section, dwo_entry->sect_off, - sig, slot); + if (sig_type_it == per_bfd->signatured_types.end ()) + sig_type_it + = add_type_unit (per_bfd, dwo_entry->section, dwo_entry->sect_off, sig); - if (sig_entry->dwo_unit == nullptr) - fill_in_sig_entry_from_dwo_entry (per_objfile, sig_entry, dwo_entry); - sig_entry->tu_read = 1; - return sig_entry; + if ((*sig_type_it)->dwo_unit == nullptr) + fill_in_sig_entry_from_dwo_entry (per_objfile, *sig_type_it, dwo_entry); + + (*sig_type_it)->tu_read = 1; + return *sig_type_it; } /* Subroutine of lookup_signatured_type. @@ -2854,39 +2816,30 @@ lookup_dwp_signatured_type (struct dwarf2_cu *cu, ULONGEST sig) dwarf2_per_objfile *per_objfile = cu->per_objfile; dwarf2_per_bfd *per_bfd = per_objfile->per_bfd; struct dwp_file *dwp_file = get_dwp_file (per_objfile); - struct dwo_unit *dwo_entry; - void **slot; gdb_assert (cu->dwo_unit); gdb_assert (dwp_file != NULL); - /* If TU skeletons have been removed then we may not have read in any - TUs yet. */ - if (per_bfd->signatured_types == NULL) - per_bfd->signatured_types = allocate_signatured_type_table (); - - signatured_type find_sig_entry (nullptr, nullptr, sect_offset {}, sig); - slot = htab_find_slot (per_bfd->signatured_types.get (), &find_sig_entry, - INSERT); - signatured_type *sig_entry = (struct signatured_type *) *slot; + auto sig_type_it = per_bfd->signatured_types.find (sig); /* Have we already tried to read this TU? Note: sig_entry can be NULL if the skeleton TU was removed (thus it needn't exist in the global table yet). */ - if (sig_entry != NULL) - return sig_entry; + if (sig_type_it != per_bfd->signatured_types.end ()) + return *sig_type_it; if (dwp_file->tus == NULL) return NULL; - dwo_entry = lookup_dwo_unit_in_dwp (per_bfd, dwp_file, NULL, sig, - 1 /* is_debug_types */); + + auto dwo_entry = lookup_dwo_unit_in_dwp (per_bfd, dwp_file, NULL, sig, + 1 /* is_debug_types */); if (dwo_entry == NULL) return NULL; - sig_entry = add_type_unit (per_bfd, nullptr, dwo_entry->sect_off, sig, slot); - fill_in_sig_entry_from_dwo_entry (per_objfile, sig_entry, dwo_entry); + sig_type_it = add_type_unit (per_bfd, nullptr, dwo_entry->sect_off, sig); + fill_in_sig_entry_from_dwo_entry (per_objfile, *sig_type_it, dwo_entry); - return sig_entry; + return *sig_type_it; } /* Lookup a signature based type for DW_FORM_ref_sig8. @@ -2897,6 +2850,7 @@ static struct signatured_type * lookup_signatured_type (struct dwarf2_cu *cu, ULONGEST sig) { dwarf2_per_objfile *per_objfile = cu->per_objfile; + dwarf2_per_bfd *per_bfd = per_objfile->per_bfd; if (cu->dwo_unit) { @@ -2909,12 +2863,12 @@ lookup_signatured_type (struct dwarf2_cu *cu, ULONGEST sig) } else { - if (per_objfile->per_bfd->signatured_types == NULL) - return NULL; - signatured_type find_entry (nullptr, nullptr, sect_offset {}, sig); - return ((struct signatured_type *) - htab_find (per_objfile->per_bfd->signatured_types.get (), - &find_entry)); + auto sig_type_it = per_bfd->signatured_types.find (sig); + + if (sig_type_it != per_bfd->signatured_types.end ()) + return *sig_type_it; + + return nullptr; } } @@ -4057,29 +4011,21 @@ process_skeletonless_type_unit (void **slot, void *info) dwarf2_per_bfd *per_bfd = per_objfile->per_bfd; /* If this TU doesn't exist in the global table, add it and read it in. */ - - if (per_bfd->signatured_types == NULL) - per_bfd->signatured_types = allocate_signatured_type_table (); - - signatured_type find_entry (nullptr, nullptr, sect_offset {}, - dwo_unit->signature); - slot = htab_find_slot (per_bfd->signatured_types.get (), &find_entry, INSERT); + auto sig_type_it = per_bfd->signatured_types.find (dwo_unit->signature); /* If we've already seen this type there's nothing to do. What's happening is we're doing our own version of comdat-folding here. */ - if (*slot != NULL) + if (sig_type_it != per_bfd->signatured_types.end ()) return 1; /* This does the job that create_all_units would have done for this TU. */ - signatured_type *entry - = add_type_unit (per_bfd, dwo_unit->section, dwo_unit->sect_off, - dwo_unit->signature, slot); - fill_in_sig_entry_from_dwo_entry (per_objfile, entry, dwo_unit); - *slot = entry; + sig_type_it = add_type_unit (per_bfd, dwo_unit->section, dwo_unit->sect_off, + dwo_unit->signature); + fill_in_sig_entry_from_dwo_entry (per_objfile, *sig_type_it, dwo_unit); /* This does the job that build_type_psymtabs would have done. */ - cutu_reader reader (entry, per_objfile, nullptr, nullptr, false, + cutu_reader reader (*sig_type_it, per_objfile, nullptr, nullptr, false, language_minimal); if (!reader.dummy_p) build_type_psymtabs_reader (&reader, data->storage); @@ -4311,7 +4257,7 @@ read_comp_units_from_section (dwarf2_per_objfile *per_objfile, struct dwarf2_section_info *section, struct dwarf2_section_info *abbrev_section, unsigned int is_dwz, - htab_up &types_htab, + signatured_type_set &sig_types, rcuh_kind section_kind) { const gdb_byte *info_ptr; @@ -4341,24 +4287,20 @@ read_comp_units_from_section (dwarf2_per_objfile *per_objfile, this_cu = per_objfile->per_bfd->allocate_per_cu (section, sect_off); else { - if (types_htab == nullptr) - types_htab = allocate_signatured_type_table (); - auto sig_type = per_objfile->per_bfd->allocate_signatured_type (section, sect_off, cu_header.signature); signatured_type *sig_ptr = sig_type.get (); sig_type->type_offset_in_tu = cu_header.type_cu_offset_in_tu; this_cu.reset (sig_type.release ()); - void **slot = htab_find_slot (types_htab.get (), sig_ptr, INSERT); - gdb_assert (slot != nullptr); - if (*slot != nullptr) + auto [sig_type_it, inserted] = sig_types.emplace (sig_ptr); + + if (!inserted) complaint (_("debug type entry at offset %s is duplicate to" " the entry at offset %s, signature %s"), sect_offset_str (sect_off), sect_offset_str (sig_ptr->sect_off), hex_string (sig_ptr->signature)); - *slot = sig_ptr; } this_cu->set_length (cu_header.get_length_with_initial ()); @@ -4390,23 +4332,24 @@ finalize_all_units (dwarf2_per_bfd *per_bfd) void create_all_units (dwarf2_per_objfile *per_objfile) { - htab_up types_htab; gdb_assert (per_objfile->per_bfd->all_units.empty ()); + signatured_type_set sig_types; + for (dwarf2_section_info §ion : per_objfile->per_bfd->infos) read_comp_units_from_section (per_objfile, §ion, - &per_objfile->per_bfd->abbrev, 0, - types_htab, rcuh_kind::COMPILE); + &per_objfile->per_bfd->abbrev, 0, sig_types, + rcuh_kind::COMPILE); for (dwarf2_section_info §ion : per_objfile->per_bfd->types) read_comp_units_from_section (per_objfile, §ion, - &per_objfile->per_bfd->abbrev, 0, - types_htab, rcuh_kind::TYPE); + &per_objfile->per_bfd->abbrev, 0, sig_types, + rcuh_kind::TYPE); dwz_file *dwz = dwarf2_get_dwz_file (per_objfile->per_bfd); if (dwz != NULL) { read_comp_units_from_section (per_objfile, &dwz->info, &dwz->abbrev, 1, - types_htab, rcuh_kind::COMPILE); + sig_types, rcuh_kind::COMPILE); if (!dwz->types.empty ()) { @@ -4418,7 +4361,7 @@ create_all_units (dwarf2_per_objfile *per_objfile) } } - per_objfile->per_bfd->signatured_types = std::move (types_htab); + per_objfile->per_bfd->signatured_types = std::move (sig_types); finalize_all_units (per_objfile->per_bfd); } diff --git a/gdb/dwarf2/read.h b/gdb/dwarf2/read.h index 24decd761c1..596578919c8 100644 --- a/gdb/dwarf2/read.h +++ b/gdb/dwarf2/read.h @@ -405,6 +405,40 @@ struct signatured_type : public dwarf2_per_cu_data using signatured_type_up = std::unique_ptr; +/* Hash a signatured_type object based on its signature. */ + +struct signatured_type_hash +{ + using is_transparent = void; + + std::size_t operator() (ULONGEST signature) const noexcept + { return signature; } + + std::size_t operator() (const signatured_type *sig_type) const noexcept + { return (*this) (sig_type->signature); } +}; + +/* Compare signatured_type objects based on their signatures. */ + +struct signatured_type_eq +{ + using is_transparent = void; + + bool operator() (ULONGEST sig, const signatured_type *sig_type) const noexcept + { return sig == sig_type->signature; } + + bool operator() (const signatured_type *sig_type_a, + const signatured_type *sig_type_b) const noexcept + { return (*this) (sig_type_a->signature, sig_type_b); } +}; + +/* Unordered set of signatured_type objects using their signature as the + key. */ + +using signatured_type_set + = gdb::unordered_set; + struct dwp_file; using dwp_file_up = std::unique_ptr; @@ -523,9 +557,8 @@ public: The hash key is the DW_AT_stmt_list value. */ htab_up type_unit_groups; - /* A table mapping .debug_types signatures to its signatured_type entry. - This is NULL if the .debug_types section hasn't been read in yet. */ - htab_up signatured_types; + /* Set of signatured_types, used to look up by signature. */ + signatured_type_set signatured_types; /* Type unit statistics, to see how well the scaling improvements are doing. */ @@ -958,10 +991,6 @@ extern void dw_expand_symtabs_matching_file_matcher extern const char *read_indirect_string_at_offset (dwarf2_per_objfile *per_objfile, LONGEST str_offset); -/* Allocate a hash table for signatured types. */ - -extern htab_up allocate_signatured_type_table (); - /* Return a new dwarf2_per_cu_data allocated on the per-bfd obstack, and constructed with the specified field values. */ -- 2.47.2