addr2line/
function.rs

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

addr2line/
function.rs
