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