Repository: gimli-rs/addr2line
Pull request #151 (2019-12-04 09:06:11)

Replace IntervalTree with Vec
`IntervalTree` doesn't perform as well as a simple tree of `Vec`s. Note that a `Vec` tree can't handle partially overlapping intervals, but we don't need that.

```
 name                                        before ns/iter  after ns/iter  diff ns/iter   diff %  speedup
 context_new_and_query_location_rc           2,427,320       2,432,182             4,862    0.20%   x 1.00
 context_new_and_query_location_slice        765,873         758,006              -7,867   -1.03%   x 1.01
 context_new_and_query_with_functions_rc     2,993,102       2,959,278           -33,824   -1.13%   x 1.01
 context_new_and_query_with_functions_slice  1,133,112       1,152,324            19,212    1.70%   x 0.98
 context_new_parse_functions_rc              31,235,025      33,387,535        2,152,510    6.89%   x 0.94
 context_new_parse_functions_slice           23,754,161      26,858,657        3,104,496   13.07%   x 0.88
 context_new_parse_lines_rc                  11,725,686      11,711,061          -14,625   -0.12%   x 1.00
 context_new_parse_lines_slice               7,337,852       7,283,802           -54,050   -0.74%   x 1.01
 context_new_rc                              2,207,283       2,162,930           -44,353   -2.01%   x 1.02
 context_new_slice                           613,189         603,892              -9,297   -1.52%   x 1.02
 context_query_location_rc                   728,349         733,083               4,734    0.65%   x 0.99
 context_query_location_slice                721,907         729,294               7,387    1.02%   x 0.99
 context_query_with_functions_rc             4,292,707       1,952,886        -2,339,821  -54.51%   x 2.20
 context_query_with_functions_slice          4,302,388       1,744,765        -2,557,623  -59.45%   x 2.47
 new                                         28,964          27,013               -1,951   -6.74%   x 1.07
 new_unresolved_and_resolve_separate         29,332          26,986               -2,346   -8.00%   x 1.09
 trace_and_resolve_callback                  13,379          11,471               -1,908  -14.26%   x 1.17
 trace_and_resolve_separate                  11,013          9,801                -1,212  -11.01%   x 1.12
```

For the test `parse_functions_slice`, memory usage increased from 17.4MB to 19.7MB.

Also save some memory by using `Box` for line rows.


Patch:
diff --git a/Cargo.toml b/Cargo.toml
index 2f325d0..6b24458 100644
--- a/Cargo.toml
+++ b/Cargo.toml
@@ -18,7 +18,6 @@ travis-ci = { repository = "gimli-rs/addr2line" }
 gimli = { version = "0.19", default-features = false, features = ["read"], git = "https://github.com/gimli-rs/gimli.git", rev = "1b7706bc87938916b4df4cda0c7d1346e938fe86" }
 fallible-iterator = { version = "0.2", default-features = false }
 object = { version = "0.16", default-features = false, features = ["read"], optional = true }
-intervaltree = { version = "0.2", default-features = false }
 smallvec = { version = "1", default-features = false }
 lazycell = "1"
 rustc-demangle = { version = "0.1", optional = true }
@@ -39,7 +38,7 @@ codegen-units = 1
 
 [features]
 default = ["rustc-demangle", "cpp_demangle", "std-object"]
-std = ["gimli/std", "intervaltree/std"]
+std = ["gimli/std"]
 std-object = ["std", "object", "object/std"]
 alloc = ["gimli/alloc"]
 
@@ -49,3 +48,6 @@ harness = false
 
 [[test]]
 name = "correctness"
+
+[[test]]
+name = "parse"
diff --git a/src/lib.rs b/src/lib.rs
index 41565d0..c63be5e 100644
--- a/src/lib.rs
+++ b/src/lib.rs
@@ -38,7 +38,6 @@ extern crate core as std;
 extern crate cpp_demangle;
 pub extern crate fallible_iterator;
 pub extern crate gimli;
-extern crate intervaltree;
 extern crate lazycell;
 #[cfg(feature = "object")]
 pub extern crate object;
@@ -48,21 +47,22 @@ extern crate smallvec;
 
 #[cfg(feature = "std")]
 mod alloc {
-    pub use std::{borrow, rc, string, vec};
+    pub use std::{borrow, boxed, rc, string, vec};
 }
 
 use alloc::borrow::Cow;
+use alloc::boxed::Box;
 #[cfg(feature = "object")]
 use alloc::rc::Rc;
 use alloc::string::{String, ToString};
 use alloc::vec::Vec;
 
 use std::cmp::Ordering;
+use std::iter;
 use std::mem;
 use std::u64;
 
 use fallible_iterator::FallibleIterator;
-use intervaltree::{Element, IntervalTree};
 use lazycell::LazyCell;
 use smallvec::SmallVec;
 
@@ -314,10 +314,31 @@ impl<R: gimli::Reader> Context<R> {
             Some(unit_id) => {
                 let unit = &self.units[unit_id];
                 let loc = unit.find_location(probe, &self.sections)?;
-                let funcs = unit.parse_functions(&self.sections)?;
-                let mut res: SmallVec<[_; 16]> =
-                    funcs.query_point(probe).map(|x| &x.value).collect();
-                res.sort_by_key(|x| -x.depth);
+                let functions = unit.parse_functions(&self.sections)?;
+                let mut res: SmallVec<[_; 16]> = SmallVec::new();
+                if let Ok(address) = functions.addresses.binary_search_by(|address| {
+                    if probe < address.range.begin {
+                        Ordering::Greater
+                    } else if probe >= address.range.end {
+                        Ordering::Less
+                    } else {
+                        Ordering::Equal
+                    }
+                }) {
+                    let mut function_index = functions.addresses[address].function;
+                    loop {
+                        let function = &functions.functions[function_index];
+                        res.push(function);
+                        if let Some(inlined) = function.inlined.iter().find(|inlined| {
+                            probe >= inlined.range.begin && probe < inlined.range.end
+                        }) {
+                            function_index = inlined.function;
+                            continue;
+                        } else {
+                            break;
+                        }
+                    }
+                }
                 (unit_id, loc, res)
             }
             None => (0, None, SmallVec::new()),
@@ -327,7 +348,7 @@ impl<R: gimli::Reader> Context<R> {
             unit_id,
             units: &self.units,
             sections: &self.sections,
-            funcs: funcs.into_iter(),
+            funcs: funcs.into_iter().rev(),
             next: loc,
         })
     }
@@ -352,14 +373,14 @@ impl<R: gimli::Reader> Context<R> {
 }
 
 struct Lines {
-    files: Vec<String>,
-    sequences: Vec<LineSequence>,
+    files: Box<[String]>,
+    sequences: Box<[LineSequence]>,
 }
 
 struct LineSequence {
     start: u64,
     end: u64,
-    rows: Vec<LineRow>,
+    rows: Box<[LineRow]>,
 }
 
 struct LineRow {
@@ -369,12 +390,6 @@ struct LineRow {
     column: Option<u64>,
 }
 
-#[derive(Clone, Copy)]
-struct Func<T> {
-    entry_off: gimli::UnitOffset<T>,
-    depth: isize,
-}
-
 struct ResUnit<R>
 where
     R: gimli::Reader,
@@ -382,7 +397,7 @@ where
     dw_unit: gimli::Unit<R>,
     lang: Option<gimli::DwLang>,
     lines: LazyCell<Result<Lines, Error>>,
-    funcs: LazyCell<Result<IntervalTree<u64, Func<R::Offset>>, Error>>,
+    funcs: LazyCell<Result<Functions<R::Offset>, Error>>,
 }
 
 impl<R> ResUnit<R>
@@ -406,7 +421,11 @@ where
                             let mut rows = Vec::new();
                             mem::swap(&mut rows, &mut sequence_rows);
                             if start != 0 {
-                                sequences.push(LineSequence { start, end, rows });
+                                sequences.push(LineSequence {
+                                    start,
+                                    end,
+                                    rows: rows.into_boxed_slice(),
+                                });
                             }
                         }
                         continue;
@@ -446,98 +465,19 @@ where
                     index += 1;
                 }
 
-                Ok(Lines { files, sequences })
+                Ok(Lines {
+                    files: files.into_boxed_slice(),
+                    sequences: sequences.into_boxed_slice(),
+                })
             })
             .as_ref()
             .map(Some)
             .map_err(Error::clone)
     }
 
-    fn parse_functions(
-        &self,
-        sections: &gimli::Dwarf<R>,
-    ) -> Result<&IntervalTree<u64, Func<R::Offset>>, Error> {
+    fn parse_functions(&self, sections: &gimli::Dwarf<R>) -> Result<&Functions<R::Offset>, Error> {
         self.funcs
-            .borrow_with(|| {
-                let mut results = Vec::new();
-                let mut entries = self.dw_unit.entries_raw(None)?;
-                while !entries.is_empty() {
-                    let value = Func {
-                        entry_off: entries.next_offset(),
-                        depth: entries.next_depth(),
-                    };
-                    if let Some(abbrev) = entries.read_abbreviation()? {
-                        match abbrev.tag() {
-                            gimli::DW_TAG_subprogram | gimli::DW_TAG_inlined_subroutine => {
-                                let mut low_pc = None;
-                                let mut high_pc = None;
-                                let mut size = None;
-                                let mut ranges = None;
-                                for spec in abbrev.attributes() {
-                                    match entries.read_attribute(*spec) {
-                                        Ok(ref attr) => match attr.name() {
-                                            gimli::DW_AT_low_pc => {
-                                                if let gimli::AttributeValue::Addr(val) =
-                                                    attr.value()
-                                                {
-                                                    low_pc = Some(val);
-                                                }
-                                            }
-                                            gimli::DW_AT_high_pc => match attr.value() {
-                                                gimli::AttributeValue::Addr(val) => {
-                                                    high_pc = Some(val)
-                                                }
-                                                gimli::AttributeValue::Udata(val) => {
-                                                    size = Some(val)
-                                                }
-                                                _ => {}
-                                            },
-                                            gimli::DW_AT_ranges => {
-                                                ranges = sections.attr_ranges_offset(
-                                                    &self.dw_unit,
-                                                    attr.value(),
-                                                )?;
-                                            }
-                                            _ => {}
-                                        },
-                                        Err(e) => return Err(e),
-                                    }
-                                }
-
-                                let mut add_range = |range: std::ops::Range<_>| {
-                                    // Ignore invalid DWARF so that a query of 0 does not give
-                                    // a long list of matches.
-                                    // TODO: don't ignore if there is a section at this address
-                                    if range.start != 0 && range.start < range.end {
-                                        results.push(Element { range, value });
-                                    }
-                                };
-                                if let Some(offset) = ranges {
-                                    let mut ranges = sections.ranges(&self.dw_unit, offset)?;
-                                    while let Some(range) = ranges.next()? {
-                                        add_range(range.begin..range.end);
-                                    }
-                                } else if let (Some(begin), Some(end)) = (low_pc, high_pc) {
-                                    add_range(begin..end);
-                                } else if let (Some(begin), Some(size)) = (low_pc, size) {
-                                    add_range(begin..(begin + size));
-                                }
-                            }
-                            _ => {
-                                for spec in abbrev.attributes() {
-                                    match entries.read_attribute(*spec) {
-                                        Ok(_) => {}
-                                        Err(e) => return Err(e),
-                                    }
-                                }
-                            }
-                        }
-                    }
-                }
-
-                let tree: IntervalTree<_, _> = results.into_iter().collect();
-                Ok(tree)
-            })
+            .borrow_with(|| Functions::parse(&self.dw_unit, sections))
             .as_ref()
             .map_err(Error::clone)
     }
@@ -705,6 +645,191 @@ where
     Ok(None)
 }
 
+/// A single address range for a function.
+///
+/// It is possible for a function to have multiple address ranges; this
+/// is handled by having multiple `FunctionAddress` entries with the same
+/// `function` field.
+struct FunctionAddress {
+    range: gimli::Range,
+    /// An index into `Functions::functions`.
+    function: usize,
+}
+
+struct Functions<T> {
+    /// List of all `DW_TAG_subprogram` and `DW_TAG_inlined_subroutine` details.
+    functions: Box<[Function<T>]>,
+    /// List of `DW_TAG_subprogram` address ranges in the unit.
+    addresses: Box<[FunctionAddress]>,
+}
+
+struct Function<T> {
+    offset: gimli::UnitOffset<T>,
+    /// List of `DW_TAG_inlined_subroutine` address ranges in this function.
+    // TODO: this is often empty, so we could save more memory by storing the
+    // length in the allocated memory.
+    inlined: Box<[FunctionAddress]>,
+}
+
+impl<T: gimli::ReaderOffset> Functions<T> {
+    fn parse<R: gimli::Reader<Offset = T>>(
+        unit: &gimli::Unit<R>,
+        sections: &gimli::Dwarf<R>,
+    ) -> Result<Functions<T>, Error> {
+        let mut functions = Vec::new();
+        let mut addresses = Vec::new();
+        // These are ignored.
+        let mut inlined = Vec::new();
+        let mut entries = unit.entries_raw(None)?;
+        while !entries.is_empty() {
+            let offset = entries.next_offset();
+            let depth = entries.next_depth();
+            if let Some(abbrev) = entries.read_abbreviation()? {
+                if abbrev.tag() == gimli::DW_TAG_subprogram {
+                    Function::parse(
+                        &mut entries,
+                        abbrev,
+                        offset,
+                        depth,
+                        unit,
+                        sections,
+                        &mut functions,
+                        &mut addresses,
+                        &mut inlined,
+                    )?;
+                } else {
+                    for spec in abbrev.attributes() {
+                        match entries.read_attribute(*spec) {
+                            Ok(_) => {}
+                            Err(e) => return Err(e),
+                        }
+                    }
+                }
+            }
+        }
+        addresses.sort_by_key(|x| x.range.begin);
+        debug_assert!(addresses
+            .windows(2)
+            .all(|w| w[0].range.end <= w[1].range.begin));
+
+        Ok(Functions {
+            functions: functions.into_boxed_slice(),
+            addresses: addresses.into_boxed_slice(),
+        })
+    }
+}
+
+impl<T: gimli::ReaderOffset> Function<T> {
+    fn parse<R: gimli::Reader<Offset = T>>(
+        entries: &mut gimli::EntriesRaw<R>,
+        abbrev: &gimli::Abbreviation,
+        offset: gimli::UnitOffset<R::Offset>,
+        depth: isize,
+        unit: &gimli::Unit<R>,
+        sections: &gimli::Dwarf<R>,
+        functions: &mut Vec<Function<T>>,
+        addresses: &mut Vec<FunctionAddress>,
+        inlined: &mut Vec<FunctionAddress>,
+    ) -> Result<(), Error> {
+        let mut low_pc = None;
+        let mut high_pc = None;
+        let mut size = None;
+        let mut ranges = None;
+        for spec in abbrev.attributes() {
+            match entries.read_attribute(*spec) {
+                Ok(ref attr) => match attr.name() {
+                    gimli::DW_AT_low_pc => {
+                        if let gimli::AttributeValue::Addr(val) = attr.value() {
+                            low_pc = Some(val);
+                        }
+                    }
+                    gimli::DW_AT_high_pc => match attr.value() {
+                        gimli::AttributeValue::Addr(val) => high_pc = Some(val),
+                        gimli::AttributeValue::Udata(val) => size = Some(val),
+                        _ => {}
+                    },
+                    gimli::DW_AT_ranges => {
+                        ranges = sections.attr_ranges_offset(unit, attr.value())?;
+                    }
+                    _ => {}
+                },
+                Err(e) => return Err(e),
+            }
+        }
+
+        let mut local_inlined = Vec::new();
+        loop {
+            let next_depth = entries.next_depth();
+            if next_depth <= depth {
+                break;
+            }
+            let next_offset = entries.next_offset();
+            if let Some(abbrev) = entries.read_abbreviation()? {
+                if abbrev.tag() == gimli::DW_TAG_subprogram
+                    || abbrev.tag() == gimli::DW_TAG_inlined_subroutine
+                {
+                    Function::parse(
+                        entries,
+                        abbrev,
+                        next_offset,
+                        next_depth,
+                        unit,
+                        sections,
+                        functions,
+                        addresses,
+                        &mut local_inlined,
+                    )?;
+                } else {
+                    for spec in abbrev.attributes() {
+                        match entries.read_attribute(*spec) {
+                            Ok(_) => {}
+                            Err(e) => return Err(e),
+                        }
+                    }
+                }
+            }
+        }
+
+        let function_index = functions.len();
+        functions.push(Function {
+            offset,
+            inlined: local_inlined.into_boxed_slice(),
+        });
+
+        let addresses = if abbrev.tag() == gimli::DW_TAG_inlined_subroutine {
+            inlined
+        } else {
+            addresses
+        };
+        let mut add_range = |range: gimli::Range| {
+            // Ignore invalid DWARF so that a query of 0 does not give
+            // a long list of matches.
+            // TODO: don't ignore if there is a section at this address
+            if range.begin != 0 && range.begin < range.end {
+                addresses.push(FunctionAddress {
+                    range,
+                    function: function_index,
+                });
+            }
+        };
+        if let Some(offset) = ranges {
+            let mut ranges = sections.ranges(unit, offset)?;
+            while let Some(range) = ranges.next()? {
+                add_range(range);
+            }
+        } else if let (Some(begin), Some(end)) = (low_pc, high_pc) {
+            add_range(gimli::Range { begin, end });
+        } else if let (Some(begin), Some(size)) = (low_pc, size) {
+            add_range(gimli::Range {
+                begin,
+                end: begin + size,
+            });
+        }
+
+        Ok(())
+    }
+}
+
 /// An iterator over function frames.
 pub struct FrameIter<'ctx, R>
 where
@@ -713,7 +838,7 @@ where
     unit_id: usize,
     units: &'ctx Vec<ResUnit<R>>,
     sections: &'ctx gimli::Dwarf<R>,
-    funcs: smallvec::IntoIter<[&'ctx Func<R::Offset>; 16]>,
+    funcs: iter::Rev<smallvec::IntoIter<[&'ctx Function<R::Offset>; 16]>>,
     next: Option<Location<'ctx>>,
 }
 
@@ -736,7 +861,7 @@ where
 
         let unit = &self.units[self.unit_id];
 
-        let mut entries = unit.dw_unit.entries_raw(Some(func.entry_off))?;
+        let mut entries = unit.dw_unit.entries_raw(Some(func.offset))?;
         let abbrev = entries
             .read_abbreviation()?
             .expect("DIE we read a while ago is no longer readable??");


Test patch:
diff --git a/tests/parse.rs b/tests/parse.rs
new file mode 100644
index 0000000..b97aa5c
--- /dev/null
+++ b/tests/parse.rs
@@ -0,0 +1,115 @@
+extern crate addr2line;
+extern crate memmap;
+extern crate object;
+
+use std::borrow::Cow;
+use std::env;
+use std::fs::File;
+use std::path::{self, PathBuf};
+
+use object::Object;
+
+fn release_fixture_path() -> PathBuf {
+    if let Ok(p) = env::var("ADDR2LINE_FIXTURE_PATH") {
+        return p.into();
+    }
+
+    let mut path = PathBuf::new();
+    if let Ok(dir) = env::var("CARGO_MANIFEST_DIR") {
+        path.push(dir);
+    }
+    path.push("fixtures");
+    path.push("addr2line-release");
+    path
+}
+
+fn with_file<F: FnOnce(&object::File)>(target: &path::Path, f: F) {
+    let file = File::open(target).unwrap();
+    let map = unsafe { memmap::Mmap::map(&file).unwrap() };
+    let file = object::File::parse(&*map).unwrap();
+    f(&file)
+}
+
+fn dwarf_load<'a>(object: &object::File<'a>) -> gimli::Dwarf<Cow<'a, [u8]>> {
+    let load_section = |id: gimli::SectionId| -> Result<Cow<'a, [u8]>, gimli::Error> {
+        Ok(object
+            .section_data_by_name(id.name())
+            .unwrap_or(Cow::Borrowed(&[][..])))
+    };
+    let load_section_sup = |_| Ok(Cow::Borrowed(&[][..]));
+    gimli::Dwarf::load(&load_section, &load_section_sup).unwrap()
+}
+
+fn dwarf_borrow<'a>(
+    dwarf: &'a gimli::Dwarf<Cow<[u8]>>,
+) -> gimli::Dwarf<gimli::EndianSlice<'a, gimli::LittleEndian>> {
+    let borrow_section: &dyn for<'b> Fn(
+        &'b Cow<[u8]>,
+    ) -> gimli::EndianSlice<'b, gimli::LittleEndian> =
+        &|section| gimli::EndianSlice::new(&*section, gimli::LittleEndian);
+    dwarf.borrow(&borrow_section)
+}
+
+#[test]
+fn parse_base_rc() {
+    let target = release_fixture_path();
+
+    with_file(&target, |file| {
+        addr2line::Context::new(file).unwrap();
+    });
+}
+
+#[test]
+fn parse_base_slice() {
+    let target = release_fixture_path();
+
+    with_file(&target, |file| {
+        let dwarf = dwarf_load(file);
+        let dwarf = dwarf_borrow(&dwarf);
+        addr2line::Context::from_dwarf(dwarf).unwrap();
+    });
+}
+
+#[test]
+fn parse_lines_rc() {
+    let target = release_fixture_path();
+
+    with_file(&target, |file| {
+        let context = addr2line::Context::new(file).unwrap();
+        context.parse_lines().unwrap();
+    });
+}
+
+#[test]
+fn parse_lines_slice() {
+    let target = release_fixture_path();
+
+    with_file(&target, |file| {
+        let dwarf = dwarf_load(file);
+        let dwarf = dwarf_borrow(&dwarf);
+        let context = addr2line::Context::from_dwarf(dwarf).unwrap();
+        context.parse_lines().unwrap();
+    });
+}
+
+#[test]
+fn parse_functions_rc() {
+    let target = release_fixture_path();
+
+    with_file(&target, |file| {
+        let context = addr2line::Context::new(file).unwrap();
+        context.parse_functions().unwrap();
+    });
+}
+
+#[test]
+fn parse_functions_slice() {
+    let target = release_fixture_path();
+
+    with_file(&target, |file| {
+        let dwarf = dwarf_load(file);
+        let dwarf = dwarf_borrow(&dwarf);
+        let context = addr2line::Context::from_dwarf(dwarf).unwrap();
+        context.parse_functions().unwrap();
+    });
+}