symbolic_debuginfo/function_builder.rs
1//! Contains [`FunctionBuilder`], which can be used to create a [`Function`]
2//! with inlinees and line records in the right structure.
3
4use std::{cmp::Reverse, collections::BinaryHeap};
5
6use crate::base::{FileInfo, Function, LineInfo};
7use symbolic_common::Name;
8
9/// Allows creating a [`Function`] from unordered line and inlinee records.
10///
11/// The created function will have the correct tree structure, all the line records will be on the
12/// correct function node within the tree, and all lines and inlinees will be sorted by address.
13pub struct FunctionBuilder<'s> {
14 /// The name of the outer function.
15 name: Name<'s>,
16 /// The compilation dir of the function.
17 compilation_dir: &'s [u8],
18 /// The address of the outer function.
19 address: u64,
20 /// The size of the outer function.
21 size: u64,
22 /// All inlinees at any depth inside this function.
23 ///
24 /// These are stored in a `BinaryHeap<Reverse<_>>` so that `.pop()` returns them ordered by
25 /// address, from low to high. (A [`BinaryHeap`] by itself is a max-heap, so we use [`Reverse`]
26 /// to make this a min-heap). We use a heap instead of a sorted `Vec` because we may need to
27 /// insert new elements during iteration, for inlinee splitting in `ensure_proper_nesting`.
28 inlinees: BinaryHeap<Reverse<FunctionBuilderInlinee<'s>>>,
29 /// The lines, in any order. They will be sorted in `finish()`. These record specify locations
30 /// at the innermost level of the inline stack at the line record's address.
31 lines: Vec<LineInfo<'s>>,
32 max_inline_depth: Option<u32>,
33}
34
35impl<'s> FunctionBuilder<'s> {
36 /// Create a new builder for a given outer function.
37 pub fn new(name: Name<'s>, compilation_dir: &'s [u8], address: u64, size: u64) -> Self {
38 Self {
39 name,
40 compilation_dir,
41 address,
42 size,
43 inlinees: BinaryHeap::new(),
44 lines: Vec::new(),
45 max_inline_depth: None,
46 }
47 }
48
49 /// Sets the maximum inline nesting depth to process.
50 ///
51 /// Inline records nested deeper than this are dropped.
52 pub fn max_inline_depth(mut self, max_inline_depth: Option<u32>) -> Self {
53 self.max_inline_depth = max_inline_depth;
54 self
55 }
56
57 /// Add an inlinee record. This method can be called in any order.
58 ///
59 /// Inlinees which are called directly from the outer function have depth 0.
60 pub fn add_inlinee(
61 &mut self,
62 depth: u32,
63 name: Name<'s>,
64 address: u64,
65 size: u64,
66 call_file: FileInfo<'s>,
67 call_line: u64,
68 ) {
69 // An inlinee that starts before the function is obviously bogus same for an inlinee that
70 // has a depth deeper than the limit.
71 if address < self.address || depth > self.max_inline_depth.unwrap_or(u32::MAX) {
72 return;
73 }
74
75 self.inlinees.push(Reverse(FunctionBuilderInlinee {
76 depth,
77 address,
78 size,
79 name,
80 call_file,
81 call_line,
82 }));
83 }
84
85 /// Add a line record, specifying the line at this address inside the innermost inlinee that
86 /// covers that address. This method can be called in any order.
87 pub fn add_leaf_line(
88 &mut self,
89 address: u64,
90 size: Option<u64>,
91 file: FileInfo<'s>,
92 line: u64,
93 ) {
94 // A line record that starts before the function is obviously bogus.
95 if address < self.address {
96 return;
97 }
98
99 self.lines.push(LineInfo {
100 address,
101 size,
102 file,
103 line,
104 });
105 }
106
107 /// Create the `Function`, consuming the builder.
108 pub fn finish(self) -> Function<'s> {
109 // Convert our data into the right shape.
110 // There are two big differences between what we have and what we want:
111 // - We have all inlinees in a flat list, but we want to create nested functions for them,
112 // forming a tree structure.
113 // - Our line records are in a flat list but they describe lines at different levels of
114 // inlining. We need to assign the line records to the correct function, at the correct
115 // level.
116 let FunctionBuilder {
117 name,
118 compilation_dir,
119 address,
120 size,
121 inlinees,
122 mut lines,
123 max_inline_depth: _,
124 } = self;
125
126 let inlinees = ensure_proper_nesting(inlinees);
127
128 // Sort the lines by address.
129 lines.sort_by_key(|line| line.address);
130
131 let outer_function = Function {
132 address,
133 size,
134 name,
135 compilation_dir,
136 lines: Vec::new(),
137 inlinees: Vec::new(),
138 inline: false,
139 };
140 let outer_function_end = address + size;
141 let mut stack = FunctionBuilderStack::new(outer_function);
142
143 let mut inlinee_iter = inlinees.into_iter();
144 let mut line_iter = lines.into_iter();
145
146 let mut next_inlinee = inlinee_iter.next();
147 let mut next_line = line_iter.next();
148
149 // Iterate over lines and inlinees.
150 loop {
151 // If we have both a line and an inlinee at the same address, process the inlinee first.
152 // The line belongs "inside" that inlinee.
153 if next_inlinee.is_some()
154 && (next_line.is_none()
155 || next_inlinee.as_ref().unwrap().address
156 <= next_line.as_ref().unwrap().address)
157 {
158 let inlinee = next_inlinee.take().unwrap();
159 stack.flush_address(inlinee.address);
160 stack.flush_depth(inlinee.depth);
161
162 if inlinee.address >= outer_function_end {
163 break;
164 }
165
166 stack.last_mut().lines.push(LineInfo {
167 address: inlinee.address,
168 size: Some(inlinee.size),
169 file: inlinee.call_file,
170 line: inlinee.call_line,
171 });
172 stack.push(Function {
173 address: inlinee.address,
174 size: inlinee.size,
175 name: inlinee.name,
176 compilation_dir,
177 lines: Vec::new(),
178 inlinees: Vec::new(),
179 inline: true,
180 });
181 next_inlinee = inlinee_iter.next();
182 continue;
183 }
184
185 // Process the line.
186 if let Some(mut line) = next_line.take() {
187 stack.flush_address(line.address);
188
189 if line.address >= outer_function_end {
190 break;
191 }
192
193 // Ensure that Function lines are non-overlapping, by splitting lines so that they
194 // don't cross inlinee boundaries. If lines were overlapping across inlinee
195 // boundaries, then they would overlap with the lines that we create for the calls
196 // to those inlinees.
197 // We have to split up a line in two cases: If it overlaps with the end of the
198 // current inlinee, or if it overlaps with the start of the next inlinee.
199 if let Some(size) = line.size {
200 let line_end = line.address.saturating_add(size);
201 let current_innermost_fun_end = stack.last_mut().end_address();
202 let split_address = if let Some(next_inlinee) = next_inlinee.as_ref() {
203 next_inlinee.address.min(current_innermost_fun_end)
204 } else {
205 current_innermost_fun_end
206 };
207 if split_address < line_end {
208 // We have overlap! Split the line up.
209 let mut split_line = line.clone();
210 split_line.address = split_address;
211 split_line.size = Some(line_end - split_address);
212 line.size = Some(split_address - line.address);
213 stack.last_mut().lines.push(line);
214
215 next_line = Some(split_line);
216 continue;
217 }
218 }
219
220 // Handle the case where no overlap was detected.
221 stack.last_mut().lines.push(line);
222 next_line = line_iter.next();
223 continue;
224 }
225
226 // If we get here, we have run out of both lines and inlinees, and we're done.
227 break;
228 }
229
230 stack.finish()
231 }
232}
233
234/// Represents a contiguous address range which is covered by an inlined function call.
235#[derive(PartialEq, Eq, Clone, Debug)]
236struct FunctionBuilderInlinee<'s> {
237 /// The inline nesting level of this inline call. Calls from the outer function have depth 0.
238 pub depth: u32,
239 /// The start address.
240 pub address: u64,
241 /// The size in bytes.
242 pub size: u64,
243 /// The name of the function which is called.
244 pub name: Name<'s>,
245 /// The file name of the location of the call.
246 pub call_file: FileInfo<'s>,
247 /// The line number of the location of the call.
248 pub call_line: u64,
249}
250
251/// Implement ordering in DFS order, i.e. first by address and then by depth.
252impl PartialOrd for FunctionBuilderInlinee<'_> {
253 fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
254 Some(self.cmp(other))
255 }
256}
257
258/// Implement ordering in DFS order, i.e. first by address and then by depth.
259impl Ord for FunctionBuilderInlinee<'_> {
260 fn cmp(&self, other: &Self) -> std::cmp::Ordering {
261 (self.address, self.depth).cmp(&(other.address, other.depth))
262 }
263}
264
265/// Keeps track of the current inline stack, when iterating inlinees in DFS order.
266struct FunctionBuilderStack<'s> {
267 /// The current inline stack, elements are (end_address, function).
268 ///
269 /// Always contains at least one element: `stack[0].1` is the outer function.
270 stack: Vec<(u64, Function<'s>)>,
271}
272
273impl<'s> FunctionBuilderStack<'s> {
274 /// Creates a new stack, initialized with the outer function.
275 pub fn new(outer_function: Function<'s>) -> Self {
276 let end_address = outer_function.address.saturating_add(outer_function.size);
277 let stack = vec![(end_address, outer_function)];
278 Self { stack }
279 }
280
281 /// Returns an exclusive reference to the function at the top of the stack, i.e. the "deepest"
282 /// function.
283 pub fn last_mut(&mut self) -> &mut Function<'s> {
284 &mut self.stack.last_mut().unwrap().1
285 }
286
287 /// Pops the deepest function from the stack and adds it to the inlinees of its caller.
288 fn pop(&mut self) {
289 assert!(self.stack.len() > 1);
290
291 // Pop the function and add it to its parent function's list of inlinees.
292 let fun = self.stack.pop().unwrap().1;
293 self.stack.last_mut().unwrap().1.inlinees.push(fun);
294 }
295
296 /// Finish and pop all functions that end at or before this address.
297 pub fn flush_address(&mut self, address: u64) {
298 while self.stack.len() > 1 && self.stack.last().unwrap().0 <= address {
299 self.pop();
300 }
301 }
302
303 /// Finish and pop all functions that are at the given depth / "nesting level" or deeper.
304 pub fn flush_depth(&mut self, depth: u32) {
305 while self.stack.len() > depth as usize + 1 {
306 self.pop();
307 }
308 }
309
310 /// Push an inlinee to the stack.
311 pub fn push(&mut self, inlinee: Function<'s>) {
312 let end_address = inlinee.address.saturating_add(inlinee.size);
313 self.stack.push((end_address, inlinee));
314 }
315
316 /// Finish the entire stack and return the outer function.
317 pub fn finish(mut self) -> Function<'s> {
318 while self.stack.len() > 1 {
319 self.pop();
320 }
321 self.stack.pop().unwrap().1
322 }
323}
324
325/// Converts the `BinaryHeap` of inlinees into a sorted `Vec` of inlinees, while ensuring proper
326/// inlinee nesting.
327///
328/// # Background
329///
330/// Inlinees are organized in a tree, where each node has a start address and an end address.
331/// For this tree to be well-formed, sibling nodes need to have non-overlapping address ranges, and
332/// child nodes must not extend beyond their parent nodes.
333///
334/// Overlapping siblings are always considered malformed data; if the input data has overlapping
335/// siblings there is a bug in the system which produced the input data.
336///
337/// However, child nodes may legitimately extend beyond their parents in the input data.
338/// This happens when `FunctionBuilder` is used for Breakpad .sym files.
339///
340/// This function splits and redistributes such nodes over other parents. In the output data from
341/// this function, child nodes will not extend beyond their parents.
342///
343/// Example:
344///
345/// ```plain
346/// 0x0..0x8: a() @ a.cpp:10 -> b() @ b.cpp:20 -> c() @ c.cpp:30
347/// 0x8..0xd: a() @ a.cpp:15 -> b() @ b.cpp:20 -> c() @ c.cpp:30
348///
349/// may be equivalently expressed as:
350///
351/// Representation A: Properly nested
352/// - b() called from a.cpp:10 at 0x0..0x8
353/// - c() called from b.cpp:20 at 0x0..0x8
354/// - b() called from a.cpp:15 at 0x8..0xd
355/// - c() called from b.cpp:20 at 0x8..0xd
356///
357/// or as:
358///
359/// Representation B: Improperly nested, but unambiguous and compact
360/// - b() called from a.cpp:10 at 0x0..0x8
361/// - c() called from b.cpp:20 at 0x0..0xd <-- extends beyond parent
362/// - b() called from a.cpp:10 at 0x0..0x8
363///
364/// In Representation B, the two c() inlinees were merged into one, even though they have different
365/// parents. This is valid input.
366///
367/// This function will convert Representation B into Representation A.
368/// ```
369///
370/// To create a well-formed tree, this function does the following:
371///
372/// - If a node overlaps with its previous sibling, the node's start address is adjusted to avoid
373/// overlap.
374/// - If a node extends beyond its parent, it is split into two nodes.
375/// - Free-floating nodes are removed, i.e. a node at depth N+1 at an address at which there is no
376/// node at depth N.
377fn ensure_proper_nesting(
378 mut inlinees: BinaryHeap<Reverse<FunctionBuilderInlinee>>,
379) -> Vec<FunctionBuilderInlinee> {
380 let mut result = Vec::with_capacity(inlinees.len());
381
382 // This stack contains, at index i, the end address of the most recent inlinee at depth i.
383 // The length of this stack is the current depth. During the iteration we traverse the inlinee
384 // tree in DFS order, so the "current depth" changes as we enter and exit inlinees.
385 let mut end_address_stack = Vec::new();
386
387 // Iterate the inlinees, ordered by (address, depth), in order of increasing address.
388 // We take each inlinee out of `inlinees`, check it, and then append it to `result`.
389 while let Some(Reverse(mut inlinee)) = inlinees.pop() {
390 let depth = inlinee.depth as usize;
391 let start_address = inlinee.address;
392 let mut end_address = match start_address.checked_add(inlinee.size) {
393 Some(end_address) => end_address,
394 None => continue,
395 };
396
397 if end_address_stack.len() < depth {
398 // This node has no parent. Skip it.
399 continue;
400 }
401
402 if let Some(&previous_sibling_end_address) = end_address_stack.get(depth) {
403 if end_address <= previous_sibling_end_address {
404 // This node is completely engulfed by its previous sibling.
405 // Skip this node.
406 continue;
407 }
408 if start_address < previous_sibling_end_address {
409 let new_start_address = previous_sibling_end_address;
410 // Resolve overlap by adjusting this node's start address and size, keeping its
411 // end address unchanged.
412 inlinee.address = new_start_address;
413 inlinee.size = end_address - new_start_address;
414 // Put it back into the heap so that it is processed in the correct order.
415 inlinees.push(Reverse(inlinee));
416 continue;
417 }
418 }
419
420 end_address_stack.truncate(depth);
421 debug_assert_eq!(end_address_stack.len(), depth, "due to len() check + trunc");
422
423 if let Some(&caller_end_address) = end_address_stack.last() {
424 // We know: start_address >= caller_start_address, ensured by the sort order.
425 // But is start_address < caller_end_address?
426 if start_address >= caller_end_address {
427 // This node is completely outside its parent. This must mean that it does not have
428 // a parent, otherwise we would have encountered its parent.
429 // Skip this node.
430 continue;
431 }
432 if end_address > caller_end_address {
433 // This node extends beyond its caller. Split it into two.
434 let split_address = caller_end_address;
435 let mut split_inlinee = inlinee.clone();
436 split_inlinee.address = split_address;
437 split_inlinee.size = end_address - split_address;
438 inlinees.push(Reverse(split_inlinee));
439
440 // Shorten the current inlinee.
441 inlinee.size = split_address - start_address;
442 end_address = split_address;
443 }
444 } else {
445 // This is an inlinee at depth 0, i.e. this inlinee is directly called by the outer
446 // function. Those inlinees can be as long as they want; we don't try to
447 // force them to stay within the outer function's address range here.
448 }
449 result.push(inlinee);
450 end_address_stack.push(end_address); // this goes into end_address_stack[depth]
451 }
452 result
453}
454
455#[cfg(test)]
456mod tests {
457 use super::*;
458
459 #[test]
460 fn test_simple() {
461 // 0x10 - 0x40: foo in foo.c on line 1
462 let mut builder = FunctionBuilder::new(Name::from("foo"), &[], 0x10, 0x30);
463 builder.add_leaf_line(0x10, Some(0x30), FileInfo::from_filename(b"foo.c"), 1);
464 let func = builder.finish();
465
466 assert_eq!(func.name.as_str(), "foo");
467 assert_eq!(&func.lines, &[LineInfo::new(0x10, 0x30, b"foo.c", 1)]);
468 }
469
470 #[test]
471 fn test_inlinee() {
472 // 0x10 - 0x20: foo in foo.c on line 1
473 // 0x20 - 0x40: bar in bar.c on line 1
474 // - inlined into: foo in foo.c on line 2
475 let mut builder = FunctionBuilder::new(Name::from("foo"), &[], 0x10, 0x30);
476 builder.add_inlinee(
477 0,
478 Name::from("bar"),
479 0x20,
480 0x20,
481 FileInfo::from_filename(b"foo.c"),
482 2,
483 );
484 builder.add_leaf_line(0x10, Some(0x10), FileInfo::from_filename(b"foo.c"), 1);
485 builder.add_leaf_line(0x20, Some(0x20), FileInfo::from_filename(b"bar.c"), 1);
486 let func = builder.finish();
487
488 // the outer function has two line records, one for itself, the other for the inlined call
489 assert_eq!(func.name.as_str(), "foo");
490 assert_eq!(
491 &func.lines,
492 &[
493 LineInfo::new(0x10, 0x10, b"foo.c", 1),
494 LineInfo::new(0x20, 0x20, b"foo.c", 2)
495 ]
496 );
497
498 assert_eq!(func.inlinees.len(), 1);
499 assert_eq!(func.inlinees[0].name.as_str(), "bar");
500 assert_eq!(
501 &func.inlinees[0].lines,
502 &[LineInfo::new(0x20, 0x20, b"bar.c", 1)]
503 );
504 }
505
506 #[test]
507 fn test_longer_line_record() {
508 // Consider the following code:
509 //
510 // ```
511 // | fn parent() {
512 // 1 | child1();
513 // 2 | child2();
514 // | }
515 // 1 | fn child1() { child2() }
516 // 1 | fn child2() {}
517 // ```
518 //
519 // we assume here that we transitively inline `child2` all the way into `parent`.
520 // but we only have a single line record for that whole chunk of code,
521 // even though the inlining hierarchy specifies two different call sites
522 //
523 // addr: 0x10 0x20 0x30 0x40 0x50
524 // v v v v v
525 // # DWARF hierarchy
526 // parent: |-------------------|
527 // child1: |----| (called from parent.c line 1)
528 // child2: |----| (called from child1.c line 1)
529 // |----| (called from parent.c line 2)
530 // # line records
531 // |----| |----| (parent.c line 1)
532 // |---------| (child2.c line 1)
533
534 let mut builder = FunctionBuilder::new(Name::from("parent"), &[], 0x10, 0x40);
535 builder.add_inlinee(
536 0,
537 Name::from("child1"),
538 0x20,
539 0x10,
540 FileInfo::from_filename(b"parent.c"),
541 1,
542 );
543 builder.add_inlinee(
544 1,
545 Name::from("child2"),
546 0x20,
547 0x10,
548 FileInfo::from_filename(b"child1.c"),
549 1,
550 );
551 builder.add_inlinee(
552 0,
553 Name::from("child2"),
554 0x30,
555 0x10,
556 FileInfo::from_filename(b"parent.c"),
557 2,
558 );
559 builder.add_leaf_line(0x10, Some(0x10), FileInfo::from_filename(b"parent.c"), 1);
560 builder.add_leaf_line(0x20, Some(0x20), FileInfo::from_filename(b"child2.c"), 1);
561 builder.add_leaf_line(0x40, Some(0x10), FileInfo::from_filename(b"parent.c"), 1);
562 let func = builder.finish();
563
564 assert_eq!(func.name.as_str(), "parent");
565 assert_eq!(
566 &func.lines,
567 &[
568 LineInfo::new(0x10, 0x10, b"parent.c", 1),
569 LineInfo::new(0x20, 0x10, b"parent.c", 1),
570 LineInfo::new(0x30, 0x10, b"parent.c", 2),
571 LineInfo::new(0x40, 0x10, b"parent.c", 1),
572 ]
573 );
574
575 assert_eq!(func.inlinees.len(), 2);
576 assert_eq!(func.inlinees[0].name.as_str(), "child1");
577 assert_eq!(
578 &func.inlinees[0].lines,
579 &[LineInfo::new(0x20, 0x10, b"child1.c", 1),]
580 );
581 assert_eq!(func.inlinees[0].inlinees.len(), 1);
582 assert_eq!(func.inlinees[0].inlinees[0].name.as_str(), "child2");
583 assert_eq!(
584 &func.inlinees[0].inlinees[0].lines,
585 &[LineInfo::new(0x20, 0x10, b"child2.c", 1),]
586 );
587
588 assert_eq!(func.inlinees[1].name.as_str(), "child2");
589 assert_eq!(
590 &func.inlinees[1].lines,
591 &[LineInfo::new(0x30, 0x10, b"child2.c", 1),]
592 );
593 }
594}