addr2line/
function.rs

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

addr2line/
function.rs
