diff options
Diffstat (limited to 'vendor/thorin-dwp/src/index.rs')
| -rw-r--r-- | vendor/thorin-dwp/src/index.rs | 333 |
1 files changed, 333 insertions, 0 deletions
diff --git a/vendor/thorin-dwp/src/index.rs b/vendor/thorin-dwp/src/index.rs new file mode 100644 index 000000000..8a65483c5 --- /dev/null +++ b/vendor/thorin-dwp/src/index.rs @@ -0,0 +1,333 @@ +use std::fmt; + +use gimli::{ + write::{EndianVec, Writer}, + Encoding, +}; +use tracing::{debug, trace}; + +use crate::{ + error::{Error, Result}, + ext::PackageFormatExt, + package::DwarfObject, +}; + +/// Helper trait for types that can be used in creating the `.debug_{cu,tu}_index` hash table. +pub(crate) trait Bucketable { + fn index(&self) -> u64; +} + +/// Returns a hash table computed for `elements`. Used in the `.debug_{cu,tu}_index` sections. +#[tracing::instrument(level = "trace", skip_all)] +fn bucket<B: Bucketable + fmt::Debug>(elements: &[B]) -> Vec<u32> { + let unit_count: u32 = elements.len().try_into().expect("unit count larger than u32"); + let num_buckets = if elements.len() < 2 { 2 } else { (3 * unit_count / 2).next_power_of_two() }; + let mask: u64 = num_buckets as u64 - 1; + trace!(?mask); + + let mut buckets = vec![0u32; num_buckets as usize]; + trace!(?buckets); + for (elem, i) in elements.iter().zip(0u32..) { + trace!(?i, ?elem); + let s = elem.index(); + let mut h = s & mask; + let hp = ((s >> 32) & mask) | 1; + trace!(?s, ?h, ?hp); + + while buckets[h as usize] > 0 { + assert!(elements[(buckets[h as usize] - 1) as usize].index() != elem.index()); + h = (h + hp) & mask; + trace!(?h); + } + + buckets[h as usize] = i + 1; + trace!(?buckets); + } + + buckets +} + +/// New-type'd offset into a section of a compilation/type unit's contribution. +#[derive(Copy, Clone, Eq, Hash, PartialEq)] +pub(crate) struct ContributionOffset(pub(crate) u64); + +impl fmt::Debug for ContributionOffset { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + write!(f, "ContributionOffset({:#x})", self.0) + } +} + +/// Type alias for the size of a compilation/type unit's contribution. +type ContributionSize = u64; + +/// Contribution to a section - offset and size. +#[derive(Copy, Clone, Debug, Eq, Hash, PartialEq)] +pub(crate) struct Contribution { + /// Offset of this contribution into its containing section. + pub(crate) offset: ContributionOffset, + /// Size of this contribution in its containing section. + pub(crate) size: ContributionSize, +} + +/// Populated columns in the `.debug_cu_index` or `.debug_tu_index` section. +#[derive(Copy, Clone, Debug, Default)] +pub(crate) struct IndexColumns { + pub(crate) debug_info: bool, + pub(crate) debug_types: bool, + pub(crate) debug_abbrev: bool, + pub(crate) debug_line: bool, + pub(crate) debug_loc: bool, + pub(crate) debug_loclists: bool, + pub(crate) debug_rnglists: bool, + pub(crate) debug_str_offsets: bool, + pub(crate) debug_macinfo: bool, + pub(crate) debug_macro: bool, +} + +impl IndexColumns { + /// Return the number of columns required for all index entries. + fn number_of_columns(&self) -> u32 { + self.debug_info as u32 + + self.debug_types as u32 + + self.debug_abbrev as u32 + + self.debug_line as u32 + + self.debug_loc as u32 + + self.debug_loclists as u32 + + self.debug_rnglists as u32 + + self.debug_str_offsets as u32 + + self.debug_macinfo as u32 + + self.debug_macro as u32 + } + + /// Update the columns to include the columns required for an index entry. + fn add_entry(&mut self, entry: &IndexEntry) { + self.debug_info |= entry.debug_info.is_some(); + self.debug_types |= entry.debug_types.is_some(); + self.debug_abbrev |= entry.debug_abbrev.is_some(); + self.debug_line |= entry.debug_line.is_some(); + self.debug_loc |= entry.debug_loc.is_some(); + self.debug_loclists |= entry.debug_loclists.is_some(); + self.debug_rnglists |= entry.debug_rnglists.is_some(); + self.debug_str_offsets |= entry.debug_str_offsets.is_some(); + self.debug_macinfo |= entry.debug_macinfo.is_some(); + self.debug_macro |= entry.debug_macro.is_some(); + } + + /// Write the header row for the columns. + /// + /// There is only a single header row in any index section, its contents depend on the output + /// format and the columns from contributions so the complete index entries are required to + /// know what header to write. + fn write_header<Endian: gimli::Endianity>( + &self, + out: &mut EndianVec<Endian>, + encoding: Encoding, + ) -> Result<()> { + if encoding.is_gnu_extension_dwarf_package_format() { + if self.debug_info { + out.write_u32(gimli::DW_SECT_V2_INFO.0)?; + } + if self.debug_types { + out.write_u32(gimli::DW_SECT_V2_TYPES.0)?; + } + if self.debug_abbrev { + out.write_u32(gimli::DW_SECT_V2_ABBREV.0)?; + } + if self.debug_line { + out.write_u32(gimli::DW_SECT_V2_LINE.0)?; + } + if self.debug_loc { + out.write_u32(gimli::DW_SECT_V2_LOC.0)?; + } + if self.debug_str_offsets { + out.write_u32(gimli::DW_SECT_V2_STR_OFFSETS.0)?; + } + if self.debug_macinfo { + out.write_u32(gimli::DW_SECT_V2_MACINFO.0)?; + } + if self.debug_macro { + out.write_u32(gimli::DW_SECT_V2_MACRO.0)?; + } + } else { + if self.debug_info { + out.write_u32(gimli::DW_SECT_INFO.0)?; + } + if self.debug_abbrev { + out.write_u32(gimli::DW_SECT_ABBREV.0)?; + } + if self.debug_line { + out.write_u32(gimli::DW_SECT_LINE.0)?; + } + if self.debug_loclists { + out.write_u32(gimli::DW_SECT_LOCLISTS.0)?; + } + if self.debug_rnglists { + out.write_u32(gimli::DW_SECT_RNGLISTS.0)?; + } + if self.debug_str_offsets { + out.write_u32(gimli::DW_SECT_STR_OFFSETS.0)?; + } + if self.debug_macro { + out.write_u32(gimli::DW_SECT_MACRO.0)?; + } + } + + Ok(()) + } +} + +/// Entry into the `.debug_cu_index` or `.debug_tu_index` section. +/// +/// Contributions from `.debug_loclists.dwo` and `.debug_rnglists.dwo` from type units aren't +/// defined in the DWARF 5 specification but are tested by `llvm-dwp`'s test suite. +#[derive(Copy, Clone, Debug, Eq, Hash, PartialEq)] +pub(crate) struct IndexEntry { + pub(crate) encoding: Encoding, + pub(crate) id: DwarfObject, + pub(crate) debug_info: Option<Contribution>, + pub(crate) debug_types: Option<Contribution>, + pub(crate) debug_abbrev: Option<Contribution>, + pub(crate) debug_line: Option<Contribution>, + pub(crate) debug_loc: Option<Contribution>, + pub(crate) debug_loclists: Option<Contribution>, + pub(crate) debug_rnglists: Option<Contribution>, + pub(crate) debug_str_offsets: Option<Contribution>, + pub(crate) debug_macinfo: Option<Contribution>, + pub(crate) debug_macro: Option<Contribution>, +} + +impl IndexEntry { + /// Visit each contribution in an entry, calling `proj` to write a specific field. + #[tracing::instrument(level = "trace", skip(out, proj))] + fn write_contribution<Endian, Proj>( + &self, + out: &mut EndianVec<Endian>, + proj: Proj, + columns: &IndexColumns, + ) -> Result<()> + where + Endian: gimli::Endianity, + Proj: Copy + Fn(Contribution) -> u32, + { + let proj = |contrib: Option<Contribution>| contrib.map(proj).unwrap_or(0); + if columns.debug_info { + out.write_u32(proj(self.debug_info))?; + } + if columns.debug_types { + out.write_u32(proj(self.debug_types))?; + } + if columns.debug_abbrev { + out.write_u32(proj(self.debug_abbrev))?; + } + if columns.debug_line { + out.write_u32(proj(self.debug_line))?; + } + if columns.debug_loc { + out.write_u32(proj(self.debug_loc))?; + } + if columns.debug_loclists { + out.write_u32(proj(self.debug_loclists))?; + } + if columns.debug_rnglists { + out.write_u32(proj(self.debug_rnglists))?; + } + if columns.debug_str_offsets { + out.write_u32(proj(self.debug_str_offsets))?; + } + if columns.debug_macinfo { + out.write_u32(proj(self.debug_macinfo))?; + } + if columns.debug_macro { + out.write_u32(proj(self.debug_macro))?; + } + + Ok(()) + } +} + +impl Bucketable for IndexEntry { + fn index(&self) -> u64 { + self.id.index() + } +} + +/// Write a `.debug_{cu,tu}_index` section given `IndexEntry`s. +#[tracing::instrument(level = "trace")] +pub(crate) fn write_index<'output, Endian: gimli::Endianity>( + endianness: Endian, + entries: &[IndexEntry], +) -> Result<EndianVec<Endian>> { + let mut out = EndianVec::new(endianness); + + if entries.len() == 0 { + return Ok(out); + } + + let buckets = bucket(entries); + debug!(?buckets); + + let encoding = entries[0].encoding; + if !entries.iter().all(|e| e.encoding == encoding) { + return Err(Error::MixedInputEncodings); + } + debug!(?encoding); + + let mut columns = IndexColumns::default(); + for entry in entries { + columns.add_entry(entry); + } + let num_columns = columns.number_of_columns(); + debug!(?entries, ?columns, ?num_columns); + + // Write header.. + if encoding.is_gnu_extension_dwarf_package_format() { + // GNU Extension + out.write_u32(2)?; + } else { + // DWARF 5 + out.write_u16(5)?; + // Reserved padding + out.write_u16(0)?; + } + + // Columns (e.g. info, abbrev, loc, etc.) + out.write_u32(num_columns)?; + // Number of units + out.write_u32(entries.len().try_into().expect("number of units larger than u32"))?; + // Number of buckets + out.write_u32(buckets.len().try_into().expect("number of buckets larger than u32"))?; + + // Write signatures.. + for i in &buckets { + if *i > 0 { + out.write_u64(entries[(*i - 1) as usize].index())?; + } else { + out.write_u64(0)?; + } + } + + // Write indices.. + for i in &buckets { + out.write_u32(*i)?; + } + + // Write column headers.. + columns.write_header(&mut out, encoding)?; + + // Write offsets.. + let write_offset = |contrib: Contribution| { + contrib.offset.0.try_into().expect("contribution offset larger than u32") + }; + for entry in entries { + entry.write_contribution(&mut out, write_offset, &columns)?; + } + + // Write sizes.. + let write_size = + |contrib: Contribution| contrib.size.try_into().expect("contribution size larger than u32"); + for entry in entries { + entry.write_contribution(&mut out, write_size, &columns)?; + } + + Ok(out) +} |