wasmtime_cranelift/debug/
gc.rs

1use crate::debug::transform::AddressTransform;
2use gimli::constants;
3use gimli::read;
4use gimli::{Reader, UnitSectionOffset};
5use std::collections::{HashMap, HashSet};
6
7#[derive(Debug)]
8pub struct Dependencies {
9    edges: HashMap<UnitSectionOffset, HashSet<UnitSectionOffset>>,
10    roots: HashSet<UnitSectionOffset>,
11}
12
13impl Dependencies {
14    fn new() -> Dependencies {
15        Dependencies {
16            edges: HashMap::new(),
17            roots: HashSet::new(),
18        }
19    }
20
21    fn add_edge(&mut self, a: UnitSectionOffset, b: UnitSectionOffset) {
22        use std::collections::hash_map::Entry;
23        match self.edges.entry(a) {
24            Entry::Occupied(mut o) => {
25                o.get_mut().insert(b);
26            }
27            Entry::Vacant(v) => {
28                let mut set = HashSet::new();
29                set.insert(b);
30                v.insert(set);
31            }
32        }
33    }
34
35    fn add_root(&mut self, root: UnitSectionOffset) {
36        self.roots.insert(root);
37    }
38
39    pub fn get_reachable(&self) -> HashSet<UnitSectionOffset> {
40        let mut reachable = self.roots.clone();
41        let mut queue = Vec::new();
42        for i in self.roots.iter() {
43            if let Some(deps) = self.edges.get(i) {
44                for j in deps {
45                    if reachable.contains(j) {
46                        continue;
47                    }
48                    reachable.insert(*j);
49                    queue.push(*j);
50                }
51            }
52        }
53        while let Some(i) = queue.pop() {
54            if let Some(deps) = self.edges.get(&i) {
55                for j in deps {
56                    if reachable.contains(j) {
57                        continue;
58                    }
59                    reachable.insert(*j);
60                    queue.push(*j);
61                }
62            }
63        }
64        reachable
65    }
66}
67
68pub fn build_dependencies<R: Reader<Offset = usize>>(
69    dwarf: &read::Dwarf<R>,
70    at: &AddressTransform,
71) -> read::Result<Dependencies> {
72    let mut deps = Dependencies::new();
73    let mut units = dwarf.units();
74    while let Some(unit) = units.next()? {
75        build_unit_dependencies(unit, dwarf, at, &mut deps)?;
76    }
77    Ok(deps)
78}
79
80fn build_unit_dependencies<R: Reader<Offset = usize>>(
81    header: read::UnitHeader<R>,
82    dwarf: &read::Dwarf<R>,
83    at: &AddressTransform,
84    deps: &mut Dependencies,
85) -> read::Result<()> {
86    let unit = dwarf.unit(header)?;
87    let mut tree = unit.entries_tree(None)?;
88    let root = tree.root()?;
89    build_die_dependencies(root, dwarf, &unit, at, deps)?;
90    Ok(())
91}
92
93fn has_die_back_edge<R: Reader<Offset = usize>>(die: &read::DebuggingInformationEntry<R>) -> bool {
94    match die.tag() {
95        constants::DW_TAG_variable
96        | constants::DW_TAG_constant
97        | constants::DW_TAG_inlined_subroutine
98        | constants::DW_TAG_lexical_block
99        | constants::DW_TAG_label
100        | constants::DW_TAG_with_stmt
101        | constants::DW_TAG_try_block
102        | constants::DW_TAG_catch_block
103        | constants::DW_TAG_template_type_parameter
104        | constants::DW_TAG_enumerator
105        | constants::DW_TAG_member
106        | constants::DW_TAG_variant_part
107        | constants::DW_TAG_variant
108        | constants::DW_TAG_formal_parameter => true,
109        _ => false,
110    }
111}
112
113fn has_valid_code_range<R: Reader<Offset = usize>>(
114    die: &read::DebuggingInformationEntry<R>,
115    dwarf: &read::Dwarf<R>,
116    unit: &read::Unit<R>,
117    at: &AddressTransform,
118) -> read::Result<bool> {
119    match die.tag() {
120        constants::DW_TAG_subprogram => {
121            if let Some(ranges_attr) = die.attr_value(constants::DW_AT_ranges)? {
122                let offset = match ranges_attr {
123                    read::AttributeValue::RangeListsRef(val) => {
124                        dwarf.ranges_offset_from_raw(unit, val)
125                    }
126                    read::AttributeValue::DebugRngListsIndex(index) => {
127                        dwarf.ranges_offset(unit, index)?
128                    }
129                    _ => return Ok(false),
130                };
131                let mut has_valid_base = if let Some(read::AttributeValue::Addr(low_pc)) =
132                    die.attr_value(constants::DW_AT_low_pc)?
133                {
134                    Some(at.can_translate_address(low_pc))
135                } else {
136                    None
137                };
138                let mut it = dwarf.ranges.raw_ranges(offset, unit.encoding())?;
139                while let Some(range) = it.next()? {
140                    // If at least one of the range addresses can be converted,
141                    // declaring code range as valid.
142                    match range {
143                        read::RawRngListEntry::AddressOrOffsetPair { .. }
144                            if has_valid_base.is_some() =>
145                        {
146                            if has_valid_base.unwrap() {
147                                return Ok(true);
148                            }
149                        }
150                        read::RawRngListEntry::StartEnd { begin, .. }
151                        | read::RawRngListEntry::StartLength { begin, .. }
152                        | read::RawRngListEntry::AddressOrOffsetPair { begin, .. } => {
153                            if at.can_translate_address(begin) {
154                                return Ok(true);
155                            }
156                        }
157                        read::RawRngListEntry::StartxEndx { begin, .. }
158                        | read::RawRngListEntry::StartxLength { begin, .. } => {
159                            let addr = dwarf.address(unit, begin)?;
160                            if at.can_translate_address(addr) {
161                                return Ok(true);
162                            }
163                        }
164                        read::RawRngListEntry::BaseAddress { addr } => {
165                            has_valid_base = Some(at.can_translate_address(addr));
166                        }
167                        read::RawRngListEntry::BaseAddressx { addr } => {
168                            let addr = dwarf.address(unit, addr)?;
169                            has_valid_base = Some(at.can_translate_address(addr));
170                        }
171                        read::RawRngListEntry::OffsetPair { .. } => (),
172                    }
173                }
174                return Ok(false);
175            } else if let Some(low_pc) = die.attr_value(constants::DW_AT_low_pc)? {
176                if let read::AttributeValue::Addr(a) = low_pc {
177                    return Ok(at.can_translate_address(a));
178                } else if let read::AttributeValue::DebugAddrIndex(i) = low_pc {
179                    let a = dwarf.debug_addr.get_address(4, unit.addr_base, i)?;
180                    return Ok(at.can_translate_address(a));
181                }
182            }
183        }
184        _ => (),
185    }
186    Ok(false)
187}
188
189fn build_die_dependencies<R: Reader<Offset = usize>>(
190    die: read::EntriesTreeNode<R>,
191    dwarf: &read::Dwarf<R>,
192    unit: &read::Unit<R>,
193    at: &AddressTransform,
194    deps: &mut Dependencies,
195) -> read::Result<()> {
196    let entry = die.entry();
197    let offset = entry.offset().to_unit_section_offset(unit);
198    let mut attrs = entry.attrs();
199    while let Some(attr) = attrs.next()? {
200        build_attr_dependencies(&attr, offset, dwarf, unit, at, deps)?;
201    }
202
203    let mut children = die.children();
204    while let Some(child) = children.next()? {
205        let child_entry = child.entry();
206        let child_offset = child_entry.offset().to_unit_section_offset(unit);
207        deps.add_edge(child_offset, offset);
208        if has_die_back_edge(child_entry) {
209            deps.add_edge(offset, child_offset);
210        }
211        if has_valid_code_range(child_entry, dwarf, unit, at)? {
212            deps.add_root(child_offset);
213        }
214        build_die_dependencies(child, dwarf, unit, at, deps)?;
215    }
216    Ok(())
217}
218
219fn build_attr_dependencies<R: Reader<Offset = usize>>(
220    attr: &read::Attribute<R>,
221    offset: UnitSectionOffset,
222    _dwarf: &read::Dwarf<R>,
223    unit: &read::Unit<R>,
224    _at: &AddressTransform,
225    deps: &mut Dependencies,
226) -> read::Result<()> {
227    match attr.value() {
228        read::AttributeValue::UnitRef(val) => {
229            let ref_offset = val.to_unit_section_offset(unit);
230            deps.add_edge(offset, ref_offset);
231        }
232        read::AttributeValue::DebugInfoRef(val) => {
233            let ref_offset = UnitSectionOffset::DebugInfoOffset(val);
234            deps.add_edge(offset, ref_offset);
235        }
236        _ => (),
237    }
238    Ok(())
239}
wasmtime_cranelift/debug/gc.rs

wasmtime_cranelift/debug/
gc.rs
