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