vendor/addr2line/src/function.rs

   1 use alloc::boxed::Box;
   2 use alloc::vec::Vec;
   3 use core::cmp::Ordering;
   4 use core::iter;
   5
   6 use crate::lazy::LazyCell;
   7 use crate::maybe_small;
   8 use crate::{Error, RangeAttributes, ResDwarf};
   9
  10 pub(crate) struct Functions<R: gimli::Reader> {
  11     /// List of all `DW_TAG_subprogram` details in the unit.
  12     pub(crate) functions: Box<
  13         [(
  14             gimli::UnitOffset<R::Offset>,
  15             LazyCell<Result<Function<R>, Error>>,
  16         )],
  17     >,
  18     /// List of `DW_TAG_subprogram` address ranges in the unit.
  19     pub(crate) addresses: Box<[FunctionAddress]>,
  20 }
  21
  22 /// A single address range for a function.
  23 ///
  24 /// It is possible for a function to have multiple address ranges; this
  25 /// is handled by having multiple `FunctionAddress` entries with the same
  26 /// `function` field.
  27 pub(crate) struct FunctionAddress {
  28     range: gimli::Range,
  29     /// An index into `Functions::functions`.
  30     pub(crate) function: usize,
  31 }
  32
  33 pub(crate) struct Function<R: gimli::Reader> {
  34     pub(crate) dw_die_offset: gimli::UnitOffset<R::Offset>,
  35     pub(crate) name: Option<R>,
  36     /// List of all `DW_TAG_inlined_subroutine` details in this function.
  37     inlined_functions: Box<[InlinedFunction<R>]>,
  38     /// List of `DW_TAG_inlined_subroutine` address ranges in this function.
  39     inlined_addresses: Box<[InlinedFunctionAddress]>,
  40 }
  41
  42 pub(crate) struct InlinedFunctionAddress {
  43     range: gimli::Range,
  44     call_depth: usize,
  45     /// An index into `Function::inlined_functions`.
  46     function: usize,
  47 }
  48
  49 pub(crate) struct InlinedFunction<R: gimli::Reader> {
  50     pub(crate) dw_die_offset: gimli::UnitOffset<R::Offset>,
  51     pub(crate) name: Option<R>,
  52     pub(crate) call_file: u64,
  53     pub(crate) call_line: u32,
  54     pub(crate) call_column: u32,
  55 }
  56
  57 impl<R: gimli::Reader> Functions<R> {
  58     pub(crate) fn parse(unit: &gimli::Unit<R>, dwarf: &ResDwarf<R>) -> Result<Functions<R>, Error> {
  59         let mut functions = Vec::new();
  60         let mut addresses = Vec::new();
  61         let mut entries = unit.entries_raw(None)?;
  62         while !entries.is_empty() {
  63             let dw_die_offset = entries.next_offset();
  64             if let Some(abbrev) = entries.read_abbreviation()? {
  65                 if abbrev.tag() == gimli::DW_TAG_subprogram {
  66                     let mut ranges = RangeAttributes::default();
  67                     for spec in abbrev.attributes() {
  68                         match entries.read_attribute(*spec) {
  69                             Ok(ref attr) => {
  70                                 match attr.name() {
  71                                     gimli::DW_AT_low_pc => {
  72                                         if let gimli::AttributeValue::Addr(val) = attr.value() {
  73                                             ranges.low_pc = Some(val);
  74                                         }
  75                                     }
  76                                     gimli::DW_AT_high_pc => match attr.value() {
  77                                         gimli::AttributeValue::Addr(val) => {
  78                                             ranges.high_pc = Some(val)
  79                                         }
  80                                         gimli::AttributeValue::Udata(val) => {
  81                                             ranges.size = Some(val)
  82                                         }
  83                                         _ => {}
  84                                     },
  85                                     gimli::DW_AT_ranges => {
  86                                         ranges.ranges_offset = dwarf
  87                                             .sections
  88                                             .attr_ranges_offset(unit, attr.value())?;
  89                                     }
  90                                     _ => {}
  91                                 };
  92                             }
  93                             Err(e) => return Err(e),
  94                         }
  95                     }
  96
  97                     let function_index = functions.len();
  98                     if ranges.for_each_range(&dwarf.sections, unit, |range| {
  99                         addresses.push(FunctionAddress {
 100                             range,
 101                             function: function_index,
 102                         });
 103                     })? {
 104                         functions.push((dw_die_offset, LazyCell::new()));
 105                     }
 106                 } else {
 107                     for spec in abbrev.attributes() {
 108                         match entries.read_attribute(*spec) {
 109                             Ok(_) => {}
 110                             Err(e) => return Err(e),
 111                         }
 112                     }
 113                 }
 114             }
 115         }
 116
 117         // The binary search requires the addresses to be sorted.
 118         //
 119         // It also requires them to be non-overlapping.  In practice, overlapping
 120         // function ranges are unlikely, so we don't try to handle that yet.
 121         //
 122         // It's possible for multiple functions to have the same address range if the
 123         // compiler can detect and remove functions with identical code.  In that case
 124         // we'll nondeterministically return one of them.
 125         addresses.sort_by_key(|x| x.range.begin);
 126
 127         Ok(Functions {
 128             functions: functions.into_boxed_slice(),
 129             addresses: addresses.into_boxed_slice(),
 130         })
 131     }
 132
 133     pub(crate) fn find_address(&self, probe: u64) -> Option<usize> {
 134         self.addresses
 135             .binary_search_by(|address| {
 136                 if probe < address.range.begin {
 137                     Ordering::Greater
 138                 } else if probe >= address.range.end {
 139                     Ordering::Less
 140                 } else {
 141                     Ordering::Equal
 142                 }
 143             })
 144             .ok()
 145     }
 146
 147     pub(crate) fn parse_inlined_functions(
 148         &self,
 149         unit: &gimli::Unit<R>,
 150         dwarf: &ResDwarf<R>,
 151     ) -> Result<(), Error> {
 152         for function in &*self.functions {
 153             function
 154                 .1
 155                 .borrow_with(|| Function::parse(function.0, unit, dwarf))
 156                 .as_ref()
 157                 .map_err(Error::clone)?;
 158         }
 159         Ok(())
 160     }
 161 }
 162
 163 impl<R: gimli::Reader> Function<R> {
 164     pub(crate) fn parse(
 165         dw_die_offset: gimli::UnitOffset<R::Offset>,
 166         unit: &gimli::Unit<R>,
 167         dwarf: &ResDwarf<R>,
 168     ) -> Result<Self, Error> {
 169         let mut entries = unit.entries_raw(Some(dw_die_offset))?;
 170         let depth = entries.next_depth();
 171         let abbrev = entries.read_abbreviation()?.unwrap();
 172         debug_assert_eq!(abbrev.tag(), gimli::DW_TAG_subprogram);
 173
 174         let mut name = None;
 175         for spec in abbrev.attributes() {
 176             match entries.read_attribute(*spec) {
 177                 Ok(ref attr) => {
 178                     match attr.name() {
 179                         gimli::DW_AT_linkage_name | gimli::DW_AT_MIPS_linkage_name => {
 180                             if let Ok(val) = dwarf.sections.attr_string(unit, attr.value()) {
 181                                 name = Some(val);
 182                             }
 183                         }
 184                         gimli::DW_AT_name => {
 185                             if name.is_none() {
 186                                 name = dwarf.sections.attr_string(unit, attr.value()).ok();
 187                             }
 188                         }
 189                         gimli::DW_AT_abstract_origin | gimli::DW_AT_specification => {
 190                             if name.is_none() {
 191                                 name = name_attr(attr.value(), unit, dwarf, 16)?;
 192                             }
 193                         }
 194                         _ => {}
 195                     };
 196                 }
 197                 Err(e) => return Err(e),
 198             }
 199         }
 200
 201         let mut inlined_functions = Vec::new();
 202         let mut inlined_addresses = Vec::new();
 203         Function::parse_children(
 204             &mut entries,
 205             depth,
 206             unit,
 207             dwarf,
 208             &mut inlined_functions,
 209             &mut inlined_addresses,
 210             0,
 211         )?;
 212
 213         // Sort ranges in "breadth-first traversal order", i.e. first by call_depth
 214         // and then by range.begin. This allows finding the range containing an
 215         // address at a certain depth using binary search.
 216         // Note: Using DFS order, i.e. ordering by range.begin first and then by
 217         // call_depth, would not work! Consider the two examples
 218         // "[0..10 at depth 0], [0..2 at depth 1], [6..8 at depth 1]"  and
 219         // "[0..5 at depth 0], [0..2 at depth 1], [5..10 at depth 0], [6..8 at depth 1]".
 220         // In this example, if you want to look up address 7 at depth 0, and you
 221         // encounter [0..2 at depth 1], are you before or after the target range?
 222         // You don't know.
 223         inlined_addresses.sort_by(|r1, r2| {
 224             if r1.call_depth < r2.call_depth {
 225                 Ordering::Less
 226             } else if r1.call_depth > r2.call_depth {
 227                 Ordering::Greater
 228             } else if r1.range.begin < r2.range.begin {
 229                 Ordering::Less
 230             } else if r1.range.begin > r2.range.begin {
 231                 Ordering::Greater
 232             } else {
 233                 Ordering::Equal
 234             }
 235         });
 236
 237         Ok(Function {
 238             dw_die_offset,
 239             name,
 240             inlined_functions: inlined_functions.into_boxed_slice(),
 241             inlined_addresses: inlined_addresses.into_boxed_slice(),
 242         })
 243     }
 244
 245     fn parse_children(
 246         entries: &mut gimli::EntriesRaw<R>,
 247         depth: isize,
 248         unit: &gimli::Unit<R>,
 249         dwarf: &ResDwarf<R>,
 250         inlined_functions: &mut Vec<InlinedFunction<R>>,
 251         inlined_addresses: &mut Vec<InlinedFunctionAddress>,
 252         inlined_depth: usize,
 253     ) -> Result<(), Error> {
 254         loop {
 255             let dw_die_offset = entries.next_offset();
 256             let next_depth = entries.next_depth();
 257             if next_depth <= depth {
 258                 return Ok(());
 259             }
 260             if let Some(abbrev) = entries.read_abbreviation()? {
 261                 match abbrev.tag() {
 262                     gimli::DW_TAG_subprogram => {
 263                         Function::skip(entries, abbrev, next_depth)?;
 264                     }
 265                     gimli::DW_TAG_inlined_subroutine => {
 266                         InlinedFunction::parse(
 267                             dw_die_offset,
 268                             entries,
 269                             abbrev,
 270                             next_depth,
 271                             unit,
 272                             dwarf,
 273                             inlined_functions,
 274                             inlined_addresses,
 275                             inlined_depth,
 276                         )?;
 277                     }
 278                     _ => {
 279                         for spec in abbrev.attributes() {
 280                             match entries.read_attribute(*spec) {
 281                                 Ok(_) => {}
 282                                 Err(e) => return Err(e),
 283                             }
 284                         }
 285                     }
 286                 }
 287             }
 288         }
 289     }
 290
 291     fn skip(
 292         entries: &mut gimli::EntriesRaw<R>,
 293         abbrev: &gimli::Abbreviation,
 294         depth: isize,
 295     ) -> Result<(), Error> {
 296         // TODO: use DW_AT_sibling
 297         for spec in abbrev.attributes() {
 298             match entries.read_attribute(*spec) {
 299                 Ok(_) => {}
 300                 Err(e) => return Err(e),
 301             }
 302         }
 303         while entries.next_depth() > depth {
 304             if let Some(abbrev) = entries.read_abbreviation()? {
 305                 for spec in abbrev.attributes() {
 306                     match entries.read_attribute(*spec) {
 307                         Ok(_) => {}
 308                         Err(e) => return Err(e),
 309                     }
 310                 }
 311             }
 312         }
 313         Ok(())
 314     }
 315
 316     /// Build the list of inlined functions that contain `probe`.
 317     pub(crate) fn find_inlined_functions(
 318         &self,
 319         probe: u64,
 320     ) -> iter::Rev<maybe_small::IntoIter<&InlinedFunction<R>>> {
 321         // `inlined_functions` is ordered from outside to inside.
 322         let mut inlined_functions = maybe_small::Vec::new();
 323         let mut inlined_addresses = &self.inlined_addresses[..];
 324         loop {
 325             let current_depth = inlined_functions.len();
 326             // Look up (probe, current_depth) in inline_ranges.
 327             // `inlined_addresses` is sorted in "breadth-first traversal order", i.e.
 328             // by `call_depth` first, and then by `range.begin`. See the comment at
 329             // the sort call for more information about why.
 330             let search = inlined_addresses.binary_search_by(|range| {
 331                 if range.call_depth > current_depth {
 332                     Ordering::Greater
 333                 } else if range.call_depth < current_depth {
 334                     Ordering::Less
 335                 } else if range.range.begin > probe {
 336                     Ordering::Greater
 337                 } else if range.range.end <= probe {
 338                     Ordering::Less
 339                 } else {
 340                     Ordering::Equal
 341                 }
 342             });
 343             if let Ok(index) = search {
 344                 let function_index = inlined_addresses[index].function;
 345                 inlined_functions.push(&self.inlined_functions[function_index]);
 346                 inlined_addresses = &inlined_addresses[index + 1..];
 347             } else {
 348                 break;
 349             }
 350         }
 351         inlined_functions.into_iter().rev()
 352     }
 353 }
 354
 355 impl<R: gimli::Reader> InlinedFunction<R> {
 356     fn parse(
 357         dw_die_offset: gimli::UnitOffset<R::Offset>,
 358         entries: &mut gimli::EntriesRaw<R>,
 359         abbrev: &gimli::Abbreviation,
 360         depth: isize,
 361         unit: &gimli::Unit<R>,
 362         dwarf: &ResDwarf<R>,
 363         inlined_functions: &mut Vec<InlinedFunction<R>>,
 364         inlined_addresses: &mut Vec<InlinedFunctionAddress>,
 365         inlined_depth: usize,
 366     ) -> Result<(), Error> {
 367         let mut ranges = RangeAttributes::default();
 368         let mut name = None;
 369         let mut call_file = 0;
 370         let mut call_line = 0;
 371         let mut call_column = 0;
 372         for spec in abbrev.attributes() {
 373             match entries.read_attribute(*spec) {
 374                 Ok(ref attr) => match attr.name() {
 375                     gimli::DW_AT_low_pc => {
 376                         if let gimli::AttributeValue::Addr(val) = attr.value() {
 377                             ranges.low_pc = Some(val);
 378                         }
 379                     }
 380                     gimli::DW_AT_high_pc => match attr.value() {
 381                         gimli::AttributeValue::Addr(val) => ranges.high_pc = Some(val),
 382                         gimli::AttributeValue::Udata(val) => ranges.size = Some(val),
 383                         _ => {}
 384                     },
 385                     gimli::DW_AT_ranges => {
 386                         ranges.ranges_offset =
 387                             dwarf.sections.attr_ranges_offset(unit, attr.value())?;
 388                     }
 389                     gimli::DW_AT_linkage_name | gimli::DW_AT_MIPS_linkage_name => {
 390                         if let Ok(val) = dwarf.sections.attr_string(unit, attr.value()) {
 391                             name = Some(val);
 392                         }
 393                     }
 394                     gimli::DW_AT_name => {
 395                         if name.is_none() {
 396                             name = dwarf.sections.attr_string(unit, attr.value()).ok();
 397                         }
 398                     }
 399                     gimli::DW_AT_abstract_origin | gimli::DW_AT_specification => {
 400                         if name.is_none() {
 401                             name = name_attr(attr.value(), unit, dwarf, 16)?;
 402                         }
 403                     }
 404                     gimli::DW_AT_call_file => {
 405                         if let gimli::AttributeValue::FileIndex(fi) = attr.value() {
 406                             call_file = fi;
 407                         }
 408                     }
 409                     gimli::DW_AT_call_line => {
 410                         call_line = attr.udata_value().unwrap_or(0) as u32;
 411                     }
 412                     gimli::DW_AT_call_column => {
 413                         call_column = attr.udata_value().unwrap_or(0) as u32;
 414                     }
 415                     _ => {}
 416                 },
 417                 Err(e) => return Err(e),
 418             }
 419         }
 420
 421         let function_index = inlined_functions.len();
 422         inlined_functions.push(InlinedFunction {
 423             dw_die_offset,
 424             name,
 425             call_file,
 426             call_line,
 427             call_column,
 428         });
 429
 430         ranges.for_each_range(&dwarf.sections, unit, |range| {
 431             inlined_addresses.push(InlinedFunctionAddress {
 432                 range,
 433                 call_depth: inlined_depth,
 434                 function: function_index,
 435             });
 436         })?;
 437
 438         Function::parse_children(
 439             entries,
 440             depth,
 441             unit,
 442             dwarf,
 443             inlined_functions,
 444             inlined_addresses,
 445             inlined_depth + 1,
 446         )
 447     }
 448 }
 449
 450 fn name_attr<R>(
 451     attr: gimli::AttributeValue<R>,
 452     unit: &gimli::Unit<R>,
 453     dwarf: &ResDwarf<R>,
 454     recursion_limit: usize,
 455 ) -> Result<Option<R>, Error>
 456 where
 457     R: gimli::Reader,
 458 {
 459     if recursion_limit == 0 {
 460         return Ok(None);
 461     }
 462
 463     match attr {
 464         gimli::AttributeValue::UnitRef(offset) => name_entry(unit, offset, dwarf, recursion_limit),
 465         gimli::AttributeValue::DebugInfoRef(dr) => {
 466             let res_unit = dwarf.find_unit(dr)?;
 467             name_entry(
 468                 &res_unit.dw_unit,
 469                 gimli::UnitOffset(dr.0 - res_unit.offset.0),
 470                 dwarf,
 471                 recursion_limit,
 472             )
 473         }
 474         gimli::AttributeValue::DebugInfoRefSup(dr) => {
 475             if let Some(sup_dwarf) = dwarf.sup.as_ref() {
 476                 let res_unit = sup_dwarf.find_unit(dr)?;
 477                 name_entry(
 478                     &res_unit.dw_unit,
 479                     gimli::UnitOffset(dr.0 - res_unit.offset.0),
 480                     sup_dwarf,
 481                     recursion_limit,
 482                 )
 483             } else {
 484                 Ok(None)
 485             }
 486         }
 487         _ => Ok(None),
 488     }
 489 }
 490
 491 fn name_entry<R>(
 492     unit: &gimli::Unit<R>,
 493     offset: gimli::UnitOffset<R::Offset>,
 494     dwarf: &ResDwarf<R>,
 495     recursion_limit: usize,
 496 ) -> Result<Option<R>, Error>
 497 where
 498     R: gimli::Reader,
 499 {
 500     let mut entries = unit.entries_raw(Some(offset))?;
 501     let abbrev = if let Some(abbrev) = entries.read_abbreviation()? {
 502         abbrev
 503     } else {
 504         return Err(gimli::Error::NoEntryAtGivenOffset);
 505     };
 506
 507     let mut name = None;
 508     let mut next = None;
 509     for spec in abbrev.attributes() {
 510         match entries.read_attribute(*spec) {
 511             Ok(ref attr) => match attr.name() {
 512                 gimli::DW_AT_linkage_name | gimli::DW_AT_MIPS_linkage_name => {
 513                     if let Ok(val) = dwarf.sections.attr_string(unit, attr.value()) {
 514                         return Ok(Some(val));
 515                     }
 516                 }
 517                 gimli::DW_AT_name => {
 518                     if let Ok(val) = dwarf.sections.attr_string(unit, attr.value()) {
 519                         name = Some(val);
 520                     }
 521                 }
 522                 gimli::DW_AT_abstract_origin | gimli::DW_AT_specification => {
 523                     next = Some(attr.value());
 524                 }
 525                 _ => {}
 526             },
 527             Err(e) => return Err(e),
 528         }
 529     }
 530
 531     if name.is_some() {
 532         return Ok(name);
 533     }
 534
 535     if let Some(next) = next {
 536         return name_attr(next, unit, dwarf, recursion_limit - 1);
 537     }
 538
 539     Ok(None)
 540 }