Repository: gimli-rs/addr2line
Pull request #163 (2020-05-12 21:53:51)

Don't truncate ranges of units
This commit is an attempt to fix rust-lang/backtrace-rs#327. The
behavior seen there was that CGUs would often overlap each other which
would cause a previous loop which tried to ensure CGUs didn't overlap to
avoid some CGUs being candidates for symbolizing.

To fix the issue this commit removes the loop which alters the range of
each CGU. Instead CGUs are only sorted by their starting function
address. When looking up a CGU for a function the CGU's address range is
used to initially filter the sort but afterwards the units function
address table is also consulted. The first CGU which contains the
function address is what ends up getting returned.

alexcrichton: Ok and now with tests for macos!
alexcrichton: Nah this isn't urgent, just something I noticed. Should be fine to defer a release!

Patch:
diff --git a/Cargo.toml b/Cargo.toml
index 24b702e..0d9c751 100644
--- a/Cargo.toml
+++ b/Cargo.toml
@@ -28,6 +28,7 @@ clap = "2"
 backtrace = "0.3.13"
 findshlibs = "0.5"
 rustc-test = "0.3"
+aux = { path = "tests/aux" }
 
 [profile.release]
 debug = true
diff --git a/ci/script.sh b/ci/script.sh
index 0b9f0f7..e0764cb 100755
--- a/ci/script.sh
+++ b/ci/script.sh
@@ -4,13 +4,8 @@ set -ex
 
 case "$GIMLI_JOB" in
     "build")
-        if [ "$TRAVIS_OS_NAME" = "linux" ]; then
-            cargo test
-            cargo test --release
-        else
-            cargo build
-            cargo build --release
-        fi
+        cargo test
+        cargo test --release
         ;;
 
     "features")
diff --git a/src/lib.rs b/src/lib.rs
index 4d8c73f..ecb330d 100644
--- a/src/lib.rs
+++ b/src/lib.rs
@@ -75,11 +75,17 @@ pub struct Context<R>
 where
     R: gimli::Reader,
 {
-    unit_ranges: Vec<(gimli::Range, usize)>,
+    unit_ranges: Vec<UnitRange>,
     units: Vec<ResUnit<R>>,
     sections: gimli::Dwarf<R>,
 }
 
+struct UnitRange {
+    unit_id: usize,
+    max_end: u64,
+    range: gimli::Range,
+}
+
 /// The type of `Context` that supports the `new` method.
 #[cfg(feature = "std-object")]
 pub type ObjectContext = Context<gimli::EndianRcSlice<gimli::RunTimeEndian>>;
@@ -228,7 +234,11 @@ impl<R: gimli::Reader> Context<R> {
 
                 let mut add_range = |range: gimli::Range| {
                     if range.begin < range.end {
-                        unit_ranges.push((range, unit_id));
+                        unit_ranges.push(UnitRange {
+                            range,
+                            unit_id,
+                            max_end: 0,
+                        });
                     }
                 };
                 if let Some(offset) = ranges {
@@ -254,23 +264,16 @@ impl<R: gimli::Reader> Context<R> {
             });
         }
 
-        unit_ranges.sort_by_key(|x| x.0.begin);
+        // Sort this for faster lookup in `find_unit_id_and_address` below.
+        unit_ranges.sort_by_key(|i| i.range.begin);
 
-        // Ranges need to be disjoint so that we can binary search, but weak symbols can
-        // cause overlap. In this case, we don't care which unit is used, so ignore the
-        // beginning of the subseqent range to avoid overlap.
-        let mut prev_end = 0;
-        for range in &mut unit_ranges {
-            if range.0.begin < prev_end {
-                range.0.begin = prev_end;
-            }
-            if range.0.end < prev_end {
-                range.0.end = prev_end;
-            } else {
-                prev_end = range.0.end;
-            }
+        // Calculate the `max_end` field now that we've determined the order of
+        // CUs.
+        let mut max = 0;
+        for i in unit_ranges.iter_mut() {
+            max = max.max(i.range.end);
+            i.max_end = max;
         }
-        debug_assert!(unit_ranges.windows(2).all(|w| w[0].0.end <= w[1].0.begin));
 
         Ok(Context {
             units: res_units,
@@ -284,35 +287,79 @@ impl<R: gimli::Reader> Context<R> {
         &self.sections
     }
 
-    fn find_unit_id(&self, probe: u64) -> Option<usize> {
-        let idx = self.unit_ranges.binary_search_by(|r| {
-            if probe < r.0.begin {
-                Ordering::Greater
-            } else if probe >= r.0.end {
-                Ordering::Less
-            } else {
-                Ordering::Equal
-            }
-        });
-        let idx = match idx {
-            Ok(x) => x,
-            Err(_) => return None,
+    // Finds the CU id (index in `self.units`) for the function address given.
+    // The index of the address in the CU's address table is also returned
+    // because this is calculated here to ensure the function address actually
+    // resides in the functions of the CU.
+    fn find_unit_id_and_address(&self, probe: u64) -> Option<(usize, usize)> {
+        // First up find the position in the array which could have our function
+        // address.
+        let pos = match self
+            .unit_ranges
+            .binary_search_by_key(&probe, |i| i.range.begin)
+        {
+            // Although unlikely, we could find an exact match.
+            Ok(i) => i + 1,
+            // No exact match was found, but this probe would fit at slot `i`.
+            // This means that slot `i` is bigger than `probe`, along with all
+            // indices greater than `i`, so we need to search all previous
+            // entries.
+            Err(i) => i,
         };
 
-        let (_, unit_id) = self.unit_ranges[idx];
-        Some(unit_id)
+        // Once we have our index we iterate backwards from that position
+        // looking for a matching CU.
+        for i in self.unit_ranges[..pos].iter().rev() {
+            // We know that this CU's start is beneath the probe already because
+            // of our sorted array.
+            debug_assert!(i.range.begin <= probe);
+
+            // Each entry keeps track of the maximum end address seen so far,
+            // starting from the beginning of the array of unit ranges. We're
+            // iterating in reverse so if our probe is beyond the maximum range
+            // of this entry, then it's guaranteed to not fit in any prior
+            // entries, so we break out.
+            if probe > i.max_end {
+                break;
+            }
+
+            // If this CU doesn't actually contain this address, move to the
+            // next CU.
+            if probe > i.range.end {
+                continue;
+            }
+
+            // There might be multiple CUs whose range contains this address.
+            // Weak symbols have shown up in the wild which cause this to happen
+            // but otherwise this happened in rust-lang/backtrace-rs#327 too. In
+            // any case we assume that might happen, and as a result we need to
+            // find a CU which actually contains this function.
+            //
+            // Consequently we consult the function address table here, and only
+            // if there's actually a function in this CU which contains this
+            // address do we return this unit.
+            let funcs = match self.units[i.unit_id].parse_functions(&self.sections, &self.units) {
+                Ok(func) => func,
+                Err(_) => continue,
+            };
+            if let Some(addr) = funcs.find_address(probe) {
+                return Some((i.unit_id, addr));
+            }
+        }
+
+        None
     }
 
     /// Find the DWARF unit corresponding to the given virtual memory address.
     pub fn find_dwarf_unit(&self, probe: u64) -> Option<&gimli::Unit<R>> {
-        self.find_unit_id(probe)
-            .map(|unit_id| &self.units[unit_id].dw_unit)
+        self.find_unit_id_and_address(probe)
+            .map(|(unit_id, _)| &self.units[unit_id].dw_unit)
     }
 
     /// Find the source file and line corresponding to the given virtual memory address.
     pub fn find_location(&self, probe: u64) -> Result<Option<Location<'_>>, Error> {
-        match self.find_unit_id(probe) {
-            Some(unit_id) => self.units[unit_id].find_location(probe, &self.sections),
+        match self.find_unit_id_and_address(probe) {
+            Some((unit_id, _)) => self.units[unit_id].find_location(probe, &self.sections),
             None => Ok(None),
         }
     }
@@ -327,21 +374,13 @@ impl<R: gimli::Reader> Context<R> {
     /// to the innermost inline function.  Subsequent frames contain the caller and call
     /// location, until an non-inline caller is reached.
     pub fn find_frames(&self, probe: u64) -> Result<FrameIter<R>, Error> {
-        let (unit_id, loc, funcs) = match self.find_unit_id(probe) {
-            Some(unit_id) => {
-                let unit = &self.units[unit_id];
-                let loc = unit.find_location(probe, &self.sections)?;
-                let functions = unit.parse_functions(&self.sections, &self.units)?;
-                let mut res = maybe_small::Vec::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 (unit_id, loc, funcs) =
+            match self.find_unit_id_and_address(probe) {
+                Some((unit_id, address)) => {
+                    let unit = &self.units[unit_id];
+                    let loc = unit.find_location(probe, &self.sections)?;
+                    let functions = unit.parse_functions(&self.sections, &self.units)?;
+                    let mut res = maybe_small::Vec::new();
                     let mut function_index = functions.addresses[address].function;
                     loop {
                         let function = &functions.functions[function_index];
@@ -355,11 +394,10 @@ impl<R: gimli::Reader> Context<R> {
                             break;
                         }
                     }
+                    (unit_id, loc, res)
                 }
-                (unit_id, loc, res)
-            }
-            None => (0, None, maybe_small::Vec::new()),
-        };
+                None => (0, None, maybe_small::Vec::new()),
+            };
 
         Ok(FrameIter {
             unit_id,
@@ -748,6 +786,20 @@ impl<R: gimli::Reader> Functions<R> {
             addresses: addresses.into_boxed_slice(),
         })
     }
+
+    fn find_address(&self, probe: u64) -> Option<usize> {
+        self.addresses
+            .binary_search_by(|address| {
+                if probe < address.range.begin {
+                    Ordering::Greater
+                } else if probe >= address.range.end {
+                    Ordering::Less
+                } else {
+                    Ordering::Equal
+                }
+            })
+            .ok()
+    }
 }
 
 impl<R: gimli::Reader> Function<R> {


Test patch:
diff --git a/tests/aux/Cargo.toml b/tests/aux/Cargo.toml
new file mode 100644
index 0000000..d1d7b94
--- /dev/null
+++ b/tests/aux/Cargo.toml
@@ -0,0 +1,6 @@
+[package]
+name = "aux"
+version = "0.1.0"
+authors = []
+edition = "2018"
+publish = false
diff --git a/tests/aux/src/lib.rs b/tests/aux/src/lib.rs
new file mode 100644
index 0000000..eab0f34
--- /dev/null
+++ b/tests/aux/src/lib.rs
@@ -0,0 +1,6 @@
+use std::collections::HashMap;
+pub fn foo() {
+    println!("x");
+    let mut map = HashMap::new();
+    map.insert(1, "foo");
+}
diff --git a/tests/correctness.rs b/tests/correctness.rs
index 125eb45..9510923 100644
--- a/tests/correctness.rs
+++ b/tests/correctness.rs
@@ -5,15 +5,41 @@ extern crate gimli;
 extern crate memmap;
 extern crate object;
 
-use std::fs::File;
-
 use addr2line::Context;
+use fallible_iterator::FallibleIterator;
 use findshlibs::{IterationControl, SharedLibrary, TargetSharedLibrary};
+use object::Object;
+use std::fs::File;
+
+fn find_debuginfo() -> memmap::Mmap {
+    let path = std::env::current_exe().unwrap();
+    let file = File::open(&path).unwrap();
+    let map = unsafe { memmap::Mmap::map(&file).unwrap() };
+    let file = &object::File::parse(&*map).unwrap();
+    if let Ok(uuid) = file.mach_uuid() {
+        for candidate in path.parent().unwrap().read_dir().unwrap() {
+            let path = candidate.unwrap().path();
+            if !path.to_str().unwrap().ends_with(".dSYM") {
+                continue;
+            }
+            for candidate in path.join("Contents/Resources/DWARF").read_dir().unwrap() {
+                let path = candidate.unwrap().path();
+                let file = File::open(&path).unwrap();
+                let map = unsafe { memmap::Mmap::map(&file).unwrap() };
+                let file = &object::File::parse(&*map).unwrap();
+                if file.mach_uuid().unwrap() == uuid {
+                    return map;
+                }
+            }
+        }
+    }
+
+    return map;
+}
 
 #[test]
 fn correctness() {
-    let file = File::open("/proc/self/exe").unwrap();
-    let map = unsafe { memmap::Mmap::map(&file).unwrap() };
+    let map = find_debuginfo();
     let file = &object::File::parse(&*map).unwrap();
     let ctx = Context::new(file).unwrap();
 
@@ -23,24 +49,40 @@ fn correctness() {
         IterationControl::Break
     });
 
-    let ip = (test_function as u64).wrapping_sub(bias.unwrap());
+    let test = |sym: u64, expected_prefix: &str| {
+        let ip = sym.wrapping_sub(bias.unwrap());
+
+        let frames = ctx.find_frames(ip).unwrap();
+        let frame = frames.last().unwrap().unwrap();
+        let name = frame.function.as_ref().unwrap().demangle().unwrap();
+        // Old rust versions generate DWARF with wrong linkage name,
+        // so only check the start.
+        if !name.starts_with(expected_prefix) {
+            panic!("incorrect name '{}', expected {:?}", name, expected_prefix);
+        }
+    };
+
+    test(test_function as u64, "correctness::test_function");
+    test(
+        small::test_function as u64,
+        "correctness::small::test_function",
+    );
+    test(aux::foo as u64, "aux::foo");
+}
 
-    let mut frames = ctx.find_frames(ip).unwrap();
-    let frame = frames.next().unwrap().unwrap();
-    let name = frame.function.as_ref().unwrap().demangle().unwrap();
-    // Old rust versions generate DWARF with wrong linkage name,
-    // so only check the start.
-    if !name.starts_with("correctness::test_function") {
-        panic!("incorrect name '{}'", name);
+mod small {
+    pub fn test_function() {
+        println!("y");
     }
 }
 
-fn test_function() {}
+fn test_function() {
+    println!("x");
+}
 
 #[test]
 fn zero_sequence() {
-    let file = File::open("/proc/self/exe").unwrap();
-    let map = unsafe { memmap::Mmap::map(&file).unwrap() };
+    let map = find_debuginfo();
     let file = &object::File::parse(&*map).unwrap();
     let ctx = Context::new(file).unwrap();
     for probe in 0..10 {
@@ -50,8 +92,7 @@ fn zero_sequence() {
 
 #[test]
 fn zero_function() {
-    let file = File::open("/proc/self/exe").unwrap();
-    let map = unsafe { memmap::Mmap::map(&file).unwrap() };
+    let map = find_debuginfo();
     let file = &object::File::parse(&*map).unwrap();
     let ctx = Context::new(file).unwrap();
     for probe in 0..10 {
diff --git a/tests/output_equivalence.rs b/tests/output_equivalence.rs
index 905861f..729250f 100644
--- a/tests/output_equivalence.rs
+++ b/tests/output_equivalence.rs
@@ -136,6 +136,9 @@ fn make_tests() -> Vec<TestDescAndFn> {
 }
 
 fn main() {
+    if !cfg!(target_os = "linux") {
+        return;
+    }
     let args: Vec<_> = env::args().collect();
     test::test_main(&args, make_tests());
 }