diff options
Diffstat (limited to 'vendor/addr2line/src/function.rs')
| -rw-r--r-- | vendor/addr2line/src/function.rs | 555 |
1 files changed, 555 insertions, 0 deletions
diff --git a/vendor/addr2line/src/function.rs b/vendor/addr2line/src/function.rs new file mode 100644 index 0000000..09c19e0 --- /dev/null +++ b/vendor/addr2line/src/function.rs @@ -0,0 +1,555 @@ +use alloc::boxed::Box; +use alloc::vec::Vec; +use core::cmp::Ordering; +use core::iter; + +use crate::lazy::LazyCell; +use crate::maybe_small; +use crate::{Context, DebugFile, Error, RangeAttributes}; + +pub(crate) struct Functions<R: gimli::Reader> { + /// List of all `DW_TAG_subprogram` details in the unit. + pub(crate) functions: Box< + [( + gimli::UnitOffset<R::Offset>, + LazyCell<Result<Function<R>, Error>>, + )], + >, + /// List of `DW_TAG_subprogram` address ranges in the unit. + pub(crate) addresses: Box<[FunctionAddress]>, +} + +/// A single address range for a function. +/// +/// It is possible for a function to have multiple address ranges; this +/// is handled by having multiple `FunctionAddress` entries with the same +/// `function` field. +pub(crate) struct FunctionAddress { + range: gimli::Range, + /// An index into `Functions::functions`. + pub(crate) function: usize, +} + +pub(crate) struct Function<R: gimli::Reader> { + pub(crate) dw_die_offset: gimli::UnitOffset<R::Offset>, + pub(crate) name: Option<R>, + /// List of all `DW_TAG_inlined_subroutine` details in this function. + inlined_functions: Box<[InlinedFunction<R>]>, + /// List of `DW_TAG_inlined_subroutine` address ranges in this function. + inlined_addresses: Box<[InlinedFunctionAddress]>, +} + +pub(crate) struct InlinedFunctionAddress { + range: gimli::Range, + call_depth: usize, + /// An index into `Function::inlined_functions`. + function: usize, +} + +pub(crate) struct InlinedFunction<R: gimli::Reader> { + pub(crate) dw_die_offset: gimli::UnitOffset<R::Offset>, + pub(crate) name: Option<R>, + pub(crate) call_file: Option<u64>, + pub(crate) call_line: u32, + pub(crate) call_column: u32, +} + +impl<R: gimli::Reader> Functions<R> { + pub(crate) fn parse( + unit: &gimli::Unit<R>, + sections: &gimli::Dwarf<R>, + ) -> Result<Functions<R>, Error> { + let mut functions = Vec::new(); + let mut addresses = Vec::new(); + let mut entries = unit.entries_raw(None)?; + while !entries.is_empty() { + let dw_die_offset = entries.next_offset(); + if let Some(abbrev) = entries.read_abbreviation()? { + if abbrev.tag() == gimli::DW_TAG_subprogram { + let mut ranges = RangeAttributes::default(); + for spec in abbrev.attributes() { + match entries.read_attribute(*spec) { + Ok(ref attr) => { + match attr.name() { + gimli::DW_AT_low_pc => match attr.value() { + gimli::AttributeValue::Addr(val) => { + ranges.low_pc = Some(val) + } + gimli::AttributeValue::DebugAddrIndex(index) => { + ranges.low_pc = Some(sections.address(unit, index)?); + } + _ => {} + }, + gimli::DW_AT_high_pc => match attr.value() { + gimli::AttributeValue::Addr(val) => { + ranges.high_pc = Some(val) + } + gimli::AttributeValue::DebugAddrIndex(index) => { + ranges.high_pc = Some(sections.address(unit, index)?); + } + gimli::AttributeValue::Udata(val) => { + ranges.size = Some(val) + } + _ => {} + }, + gimli::DW_AT_ranges => { + ranges.ranges_offset = + sections.attr_ranges_offset(unit, attr.value())?; + } + _ => {} + }; + } + Err(e) => return Err(e), + } + } + + let function_index = functions.len(); + if ranges.for_each_range(sections, unit, |range| { + addresses.push(FunctionAddress { + range, + function: function_index, + }); + })? { + functions.push((dw_die_offset, LazyCell::new())); + } + } else { + entries.skip_attributes(abbrev.attributes())?; + } + } + } + + // The binary search requires the addresses to be sorted. + // + // It also requires them to be non-overlapping. In practice, overlapping + // function ranges are unlikely, so we don't try to handle that yet. + // + // It's possible for multiple functions to have the same address range if the + // compiler can detect and remove functions with identical code. In that case + // we'll nondeterministically return one of them. + addresses.sort_by_key(|x| x.range.begin); + + Ok(Functions { + functions: functions.into_boxed_slice(), + addresses: addresses.into_boxed_slice(), + }) + } + + pub(crate) fn find_address(&self, probe: u64) -> Option<usize> { + self.addresses + .binary_search_by(|address| { + if probe < address.range.begin { + Ordering::Greater + } else if probe >= address.range.end { + Ordering::Less + } else { + Ordering::Equal + } + }) + .ok() + } + + pub(crate) fn parse_inlined_functions( + &self, + file: DebugFile, + unit: &gimli::Unit<R>, + ctx: &Context<R>, + sections: &gimli::Dwarf<R>, + ) -> Result<(), Error> { + for function in &*self.functions { + function + .1 + .borrow_with(|| Function::parse(function.0, file, unit, ctx, sections)) + .as_ref() + .map_err(Error::clone)?; + } + Ok(()) + } +} + +impl<R: gimli::Reader> Function<R> { + pub(crate) fn parse( + dw_die_offset: gimli::UnitOffset<R::Offset>, + file: DebugFile, + unit: &gimli::Unit<R>, + ctx: &Context<R>, + sections: &gimli::Dwarf<R>, + ) -> Result<Self, Error> { + let mut entries = unit.entries_raw(Some(dw_die_offset))?; + let depth = entries.next_depth(); + let abbrev = entries.read_abbreviation()?.unwrap(); + debug_assert_eq!(abbrev.tag(), gimli::DW_TAG_subprogram); + + let mut name = None; + for spec in abbrev.attributes() { + match entries.read_attribute(*spec) { + Ok(ref attr) => { + match attr.name() { + gimli::DW_AT_linkage_name | gimli::DW_AT_MIPS_linkage_name => { + if let Ok(val) = sections.attr_string(unit, attr.value()) { + name = Some(val); + } + } + gimli::DW_AT_name => { + if name.is_none() { + name = sections.attr_string(unit, attr.value()).ok(); + } + } + gimli::DW_AT_abstract_origin | gimli::DW_AT_specification => { + if name.is_none() { + name = name_attr(attr.value(), file, unit, ctx, sections, 16)?; + } + } + _ => {} + }; + } + Err(e) => return Err(e), + } + } + + let mut inlined_functions = Vec::new(); + let mut inlined_addresses = Vec::new(); + Function::parse_children( + &mut entries, + depth, + file, + unit, + ctx, + sections, + &mut inlined_functions, + &mut inlined_addresses, + 0, + )?; + + // Sort ranges in "breadth-first traversal order", i.e. first by call_depth + // and then by range.begin. This allows finding the range containing an + // address at a certain depth using binary search. + // Note: Using DFS order, i.e. ordering by range.begin first and then by + // call_depth, would not work! Consider the two examples + // "[0..10 at depth 0], [0..2 at depth 1], [6..8 at depth 1]" and + // "[0..5 at depth 0], [0..2 at depth 1], [5..10 at depth 0], [6..8 at depth 1]". + // In this example, if you want to look up address 7 at depth 0, and you + // encounter [0..2 at depth 1], are you before or after the target range? + // You don't know. + inlined_addresses.sort_by(|r1, r2| { + if r1.call_depth < r2.call_depth { + Ordering::Less + } else if r1.call_depth > r2.call_depth { + Ordering::Greater + } else if r1.range.begin < r2.range.begin { + Ordering::Less + } else if r1.range.begin > r2.range.begin { + Ordering::Greater + } else { + Ordering::Equal + } + }); + + Ok(Function { + dw_die_offset, + name, + inlined_functions: inlined_functions.into_boxed_slice(), + inlined_addresses: inlined_addresses.into_boxed_slice(), + }) + } + + fn parse_children( + entries: &mut gimli::EntriesRaw<'_, '_, R>, + depth: isize, + file: DebugFile, + unit: &gimli::Unit<R>, + ctx: &Context<R>, + sections: &gimli::Dwarf<R>, + inlined_functions: &mut Vec<InlinedFunction<R>>, + inlined_addresses: &mut Vec<InlinedFunctionAddress>, + inlined_depth: usize, + ) -> Result<(), Error> { + loop { + let dw_die_offset = entries.next_offset(); + let next_depth = entries.next_depth(); + if next_depth <= depth { + return Ok(()); + } + if let Some(abbrev) = entries.read_abbreviation()? { + match abbrev.tag() { + gimli::DW_TAG_subprogram => { + Function::skip(entries, abbrev, next_depth)?; + } + gimli::DW_TAG_inlined_subroutine => { + InlinedFunction::parse( + dw_die_offset, + entries, + abbrev, + next_depth, + file, + unit, + ctx, + sections, + inlined_functions, + inlined_addresses, + inlined_depth, + )?; + } + _ => { + entries.skip_attributes(abbrev.attributes())?; + } + } + } + } + } + + fn skip( + entries: &mut gimli::EntriesRaw<'_, '_, R>, + abbrev: &gimli::Abbreviation, + depth: isize, + ) -> Result<(), Error> { + // TODO: use DW_AT_sibling + entries.skip_attributes(abbrev.attributes())?; + while entries.next_depth() > depth { + if let Some(abbrev) = entries.read_abbreviation()? { + entries.skip_attributes(abbrev.attributes())?; + } + } + Ok(()) + } + + /// Build the list of inlined functions that contain `probe`. + pub(crate) fn find_inlined_functions( + &self, + probe: u64, + ) -> iter::Rev<maybe_small::IntoIter<&InlinedFunction<R>>> { + // `inlined_functions` is ordered from outside to inside. + let mut inlined_functions = maybe_small::Vec::new(); + let mut inlined_addresses = &self.inlined_addresses[..]; + loop { + let current_depth = inlined_functions.len(); + // Look up (probe, current_depth) in inline_ranges. + // `inlined_addresses` is sorted in "breadth-first traversal order", i.e. + // by `call_depth` first, and then by `range.begin`. See the comment at + // the sort call for more information about why. + let search = inlined_addresses.binary_search_by(|range| { + if range.call_depth > current_depth { + Ordering::Greater + } else if range.call_depth < current_depth { + Ordering::Less + } else if range.range.begin > probe { + Ordering::Greater + } else if range.range.end <= probe { + Ordering::Less + } else { + Ordering::Equal + } + }); + if let Ok(index) = search { + let function_index = inlined_addresses[index].function; + inlined_functions.push(&self.inlined_functions[function_index]); + inlined_addresses = &inlined_addresses[index + 1..]; + } else { + break; + } + } + inlined_functions.into_iter().rev() + } +} + +impl<R: gimli::Reader> InlinedFunction<R> { + fn parse( + dw_die_offset: gimli::UnitOffset<R::Offset>, + entries: &mut gimli::EntriesRaw<'_, '_, R>, + abbrev: &gimli::Abbreviation, + depth: isize, + file: DebugFile, + unit: &gimli::Unit<R>, + ctx: &Context<R>, + sections: &gimli::Dwarf<R>, + inlined_functions: &mut Vec<InlinedFunction<R>>, + inlined_addresses: &mut Vec<InlinedFunctionAddress>, + inlined_depth: usize, + ) -> Result<(), Error> { + let mut ranges = RangeAttributes::default(); + let mut name = None; + let mut call_file = None; + let mut call_line = 0; + let mut call_column = 0; + for spec in abbrev.attributes() { + match entries.read_attribute(*spec) { + Ok(ref attr) => match attr.name() { + gimli::DW_AT_low_pc => match attr.value() { + gimli::AttributeValue::Addr(val) => ranges.low_pc = Some(val), + gimli::AttributeValue::DebugAddrIndex(index) => { + ranges.low_pc = Some(sections.address(unit, index)?); + } + _ => {} + }, + gimli::DW_AT_high_pc => match attr.value() { + gimli::AttributeValue::Addr(val) => ranges.high_pc = Some(val), + gimli::AttributeValue::DebugAddrIndex(index) => { + ranges.high_pc = Some(sections.address(unit, index)?); + } + gimli::AttributeValue::Udata(val) => ranges.size = Some(val), + _ => {} + }, + gimli::DW_AT_ranges => { + ranges.ranges_offset = sections.attr_ranges_offset(unit, attr.value())?; + } + gimli::DW_AT_linkage_name | gimli::DW_AT_MIPS_linkage_name => { + if let Ok(val) = sections.attr_string(unit, attr.value()) { + name = Some(val); + } + } + gimli::DW_AT_name => { + if name.is_none() { + name = sections.attr_string(unit, attr.value()).ok(); + } + } + gimli::DW_AT_abstract_origin | gimli::DW_AT_specification => { + if name.is_none() { + name = name_attr(attr.value(), file, unit, ctx, sections, 16)?; + } + } + gimli::DW_AT_call_file => { + // There is a spec issue [1] with how DW_AT_call_file is specified in DWARF 5. + // Before, a file index of 0 would indicate no source file, however in + // DWARF 5 this could be a valid index into the file table. + // + // Implementations such as LLVM generates a file index of 0 when DWARF 5 is + // used. + // + // Thus, if we see a version of 5 or later, treat a file index of 0 as such. + // [1]: http://wiki.dwarfstd.org/index.php?title=DWARF5_Line_Table_File_Numbers + if let gimli::AttributeValue::FileIndex(fi) = attr.value() { + if fi > 0 || unit.header.version() >= 5 { + call_file = Some(fi); + } + } + } + gimli::DW_AT_call_line => { + call_line = attr.udata_value().unwrap_or(0) as u32; + } + gimli::DW_AT_call_column => { + call_column = attr.udata_value().unwrap_or(0) as u32; + } + _ => {} + }, + Err(e) => return Err(e), + } + } + + let function_index = inlined_functions.len(); + inlined_functions.push(InlinedFunction { + dw_die_offset, + name, + call_file, + call_line, + call_column, + }); + + ranges.for_each_range(sections, unit, |range| { + inlined_addresses.push(InlinedFunctionAddress { + range, + call_depth: inlined_depth, + function: function_index, + }); + })?; + + Function::parse_children( + entries, + depth, + file, + unit, + ctx, + sections, + inlined_functions, + inlined_addresses, + inlined_depth + 1, + ) + } +} + +fn name_attr<R>( + attr: gimli::AttributeValue<R>, + mut file: DebugFile, + unit: &gimli::Unit<R>, + ctx: &Context<R>, + sections: &gimli::Dwarf<R>, + recursion_limit: usize, +) -> Result<Option<R>, Error> +where + R: gimli::Reader, +{ + if recursion_limit == 0 { + return Ok(None); + } + + match attr { + gimli::AttributeValue::UnitRef(offset) => { + name_entry(file, unit, offset, ctx, sections, recursion_limit) + } + gimli::AttributeValue::DebugInfoRef(dr) => { + let (unit, offset) = ctx.find_unit(dr, file)?; + name_entry(file, unit, offset, ctx, sections, recursion_limit) + } + gimli::AttributeValue::DebugInfoRefSup(dr) => { + if let Some(sup_sections) = sections.sup.as_ref() { + file = DebugFile::Supplementary; + let (unit, offset) = ctx.find_unit(dr, file)?; + name_entry(file, unit, offset, ctx, sup_sections, recursion_limit) + } else { + Ok(None) + } + } + _ => Ok(None), + } +} + +fn name_entry<R>( + file: DebugFile, + unit: &gimli::Unit<R>, + offset: gimli::UnitOffset<R::Offset>, + ctx: &Context<R>, + sections: &gimli::Dwarf<R>, + recursion_limit: usize, +) -> Result<Option<R>, Error> +where + R: gimli::Reader, +{ + let mut entries = unit.entries_raw(Some(offset))?; + let abbrev = if let Some(abbrev) = entries.read_abbreviation()? { + abbrev + } else { + return Err(gimli::Error::NoEntryAtGivenOffset); + }; + + let mut name = None; + let mut next = None; + for spec in abbrev.attributes() { + match entries.read_attribute(*spec) { + Ok(ref attr) => match attr.name() { + gimli::DW_AT_linkage_name | gimli::DW_AT_MIPS_linkage_name => { + if let Ok(val) = sections.attr_string(unit, attr.value()) { + return Ok(Some(val)); + } + } + gimli::DW_AT_name => { + if let Ok(val) = sections.attr_string(unit, attr.value()) { + name = Some(val); + } + } + gimli::DW_AT_abstract_origin | gimli::DW_AT_specification => { + next = Some(attr.value()); + } + _ => {} + }, + Err(e) => return Err(e), + } + } + + if name.is_some() { + return Ok(name); + } + + if let Some(next) = next { + return name_attr(next, file, unit, ctx, sections, recursion_limit - 1); + } + + Ok(None) +} |