wasmtime_cranelift/debug/
gc.rs

1use crate::debug::transform::AddressTransform;
2use crate::debug::{Compilation, Reader};
3use gimli::constants;
4use gimli::read;
5use gimli::UnitSectionOffset;
6use std::collections::{HashMap, HashSet};
7use wasmtime_environ::{PrimaryMap, StaticModuleIndex};
8
9#[derive(Debug)]
10pub struct Dependencies {
11    edges: HashMap<UnitSectionOffset, HashSet<UnitSectionOffset>>,
12    roots: HashSet<UnitSectionOffset>,
13}
14
15impl Dependencies {
16    fn new() -> Dependencies {
17        Dependencies {
18            edges: HashMap::new(),
19            roots: HashSet::new(),
20        }
21    }
22
23    fn add_edge(&mut self, a: UnitSectionOffset, b: UnitSectionOffset) {
24        use std::collections::hash_map::Entry;
25        match self.edges.entry(a) {
26            Entry::Occupied(mut o) => {
27                o.get_mut().insert(b);
28            }
29            Entry::Vacant(v) => {
30                let mut set = HashSet::new();
31                set.insert(b);
32                v.insert(set);
33            }
34        }
35    }
36
37    fn add_root(&mut self, root: UnitSectionOffset) {
38        self.roots.insert(root);
39    }
40
41    pub fn get_reachable(&self) -> HashSet<UnitSectionOffset> {
42        let mut reachable = self.roots.clone();
43        let mut queue = Vec::new();
44        for i in self.roots.iter() {
45            if let Some(deps) = self.edges.get(i) {
46                for j in deps {
47                    if reachable.contains(j) {
48                        continue;
49                    }
50                    reachable.insert(*j);
51                    queue.push(*j);
52                }
53            }
54        }
55        while let Some(i) = queue.pop() {
56            if let Some(deps) = self.edges.get(&i) {
57                for j in deps {
58                    if reachable.contains(j) {
59                        continue;
60                    }
61                    reachable.insert(*j);
62                    queue.push(*j);
63                }
64            }
65        }
66        reachable
67    }
68}
69
70pub fn build_dependencies(
71    compilation: &mut Compilation<'_>,
72    dwp: &Option<read::DwarfPackage<Reader<'_>>>,
73    at: &PrimaryMap<StaticModuleIndex, AddressTransform>,
74) -> read::Result<Dependencies> {
75    let mut deps = Dependencies::new();
76    for (i, translation) in compilation.translations.iter() {
77        let dwarf = &translation.debuginfo.dwarf;
78        let mut units = dwarf.units();
79        while let Some(unit) = units.next()? {
80            build_unit_dependencies(unit, dwarf, dwp, &at[i], &mut deps)?;
81        }
82    }
83    Ok(deps)
84}
85
86fn build_unit_dependencies(
87    header: read::UnitHeader<Reader<'_>>,
88    dwarf: &read::Dwarf<Reader<'_>>,
89    dwp: &Option<read::DwarfPackage<Reader<'_>>>,
90    at: &AddressTransform,
91    deps: &mut Dependencies,
92) -> read::Result<()> {
93    let unit = dwarf.unit(header)?;
94    let mut tree = unit.entries_tree(None)?;
95    let root = tree.root()?;
96    build_die_dependencies(root, dwarf, &unit, at, deps)?;
97
98    if let Some(dwarf_package) = dwp {
99        if let Some(dwo_id) = unit.dwo_id {
100            if let Some(cu) = dwarf_package.find_cu(dwo_id, dwarf)? {
101                if let Some(unit_header) = cu.debug_info.units().next()? {
102                    build_unit_dependencies(unit_header, &cu, &None, at, deps)?;
103                }
104            }
105        }
106    }
107
108    Ok(())
109}
110
111fn has_die_back_edge(die: &read::DebuggingInformationEntry<Reader<'_>>) -> read::Result<bool> {
112    // DIEs can be broadly divided into three categories:
113    // 1. Extensions of their parents; effectively attributes: DW_TAG_variable, DW_TAG_member, etc.
114    // 2. Standalone entities referred to by other DIEs via 'reference' class attributes: types.
115    // 3. Structural entities that organize how the above relate to each other: namespaces.
116    // Here, we must make sure to return 'true' for DIEs in the first category since stripping them,
117    // provided their parent is alive, is always wrong. To be conservatively correct in the face
118    // of new/vendor tags, we maintain a "(mostly) known good" list of tags of the latter categories.
119    let result = match die.tag() {
120        constants::DW_TAG_array_type
121        | constants::DW_TAG_atomic_type
122        | constants::DW_TAG_base_type
123        | constants::DW_TAG_class_type
124        | constants::DW_TAG_const_type
125        | constants::DW_TAG_dwarf_procedure
126        | constants::DW_TAG_entry_point
127        | constants::DW_TAG_enumeration_type
128        | constants::DW_TAG_pointer_type
129        | constants::DW_TAG_ptr_to_member_type
130        | constants::DW_TAG_reference_type
131        | constants::DW_TAG_restrict_type
132        | constants::DW_TAG_rvalue_reference_type
133        | constants::DW_TAG_string_type
134        | constants::DW_TAG_structure_type
135        | constants::DW_TAG_typedef
136        | constants::DW_TAG_union_type
137        | constants::DW_TAG_unspecified_type
138        | constants::DW_TAG_volatile_type
139        | constants::DW_TAG_coarray_type
140        | constants::DW_TAG_common_block
141        | constants::DW_TAG_dynamic_type
142        | constants::DW_TAG_file_type
143        | constants::DW_TAG_immutable_type
144        | constants::DW_TAG_interface_type
145        | constants::DW_TAG_set_type
146        | constants::DW_TAG_shared_type
147        | constants::DW_TAG_subroutine_type
148        | constants::DW_TAG_packed_type
149        | constants::DW_TAG_template_alias
150        | constants::DW_TAG_namelist
151        | constants::DW_TAG_namespace
152        | constants::DW_TAG_imported_unit
153        | constants::DW_TAG_imported_declaration
154        | constants::DW_TAG_imported_module
155        | constants::DW_TAG_module => false,
156        constants::DW_TAG_subprogram => die.attr(constants::DW_AT_declaration)?.is_some(),
157        _ => true,
158    };
159    Ok(result)
160}
161
162fn has_valid_code_range(
163    die: &read::DebuggingInformationEntry<Reader<'_>>,
164    dwarf: &read::Dwarf<Reader<'_>>,
165    unit: &read::Unit<Reader<'_>>,
166    at: &AddressTransform,
167) -> read::Result<bool> {
168    match die.tag() {
169        constants::DW_TAG_subprogram => {
170            if let Some(ranges_attr) = die.attr_value(constants::DW_AT_ranges)? {
171                let offset = match ranges_attr {
172                    read::AttributeValue::RangeListsRef(val) => {
173                        dwarf.ranges_offset_from_raw(unit, val)
174                    }
175                    read::AttributeValue::DebugRngListsIndex(index) => {
176                        dwarf.ranges_offset(unit, index)?
177                    }
178                    _ => return Ok(false),
179                };
180                let mut has_valid_base = if let Some(read::AttributeValue::Addr(low_pc)) =
181                    die.attr_value(constants::DW_AT_low_pc)?
182                {
183                    Some(at.can_translate_address(low_pc))
184                } else {
185                    None
186                };
187                let mut it = dwarf.ranges.raw_ranges(offset, unit.encoding())?;
188                while let Some(range) = it.next()? {
189                    // If at least one of the range addresses can be converted,
190                    // declaring code range as valid.
191                    match range {
192                        read::RawRngListEntry::AddressOrOffsetPair { .. }
193                            if has_valid_base.is_some() =>
194                        {
195                            if has_valid_base.unwrap() {
196                                return Ok(true);
197                            }
198                        }
199                        read::RawRngListEntry::StartEnd { begin, .. }
200                        | read::RawRngListEntry::StartLength { begin, .. }
201                        | read::RawRngListEntry::AddressOrOffsetPair { begin, .. } => {
202                            if at.can_translate_address(begin) {
203                                return Ok(true);
204                            }
205                        }
206                        read::RawRngListEntry::StartxEndx { begin, .. }
207                        | read::RawRngListEntry::StartxLength { begin, .. } => {
208                            let addr = dwarf.address(unit, begin)?;
209                            if at.can_translate_address(addr) {
210                                return Ok(true);
211                            }
212                        }
213                        read::RawRngListEntry::BaseAddress { addr } => {
214                            has_valid_base = Some(at.can_translate_address(addr));
215                        }
216                        read::RawRngListEntry::BaseAddressx { addr } => {
217                            let addr = dwarf.address(unit, addr)?;
218                            has_valid_base = Some(at.can_translate_address(addr));
219                        }
220                        read::RawRngListEntry::OffsetPair { .. } => (),
221                    }
222                }
223                return Ok(false);
224            } else if let Some(low_pc) = die.attr_value(constants::DW_AT_low_pc)? {
225                if let read::AttributeValue::Addr(a) = low_pc {
226                    return Ok(at.can_translate_address(a));
227                } else if let read::AttributeValue::DebugAddrIndex(i) = low_pc {
228                    let a = dwarf.debug_addr.get_address(4, unit.addr_base, i)?;
229                    return Ok(at.can_translate_address(a));
230                }
231            }
232        }
233        _ => (),
234    }
235    Ok(false)
236}
237
238fn build_die_dependencies(
239    die: read::EntriesTreeNode<Reader<'_>>,
240    dwarf: &read::Dwarf<Reader<'_>>,
241    unit: &read::Unit<Reader<'_>>,
242    at: &AddressTransform,
243    deps: &mut Dependencies,
244) -> read::Result<()> {
245    let entry = die.entry();
246    let offset = entry.offset().to_unit_section_offset(unit);
247    let mut attrs = entry.attrs();
248    while let Some(attr) = attrs.next()? {
249        build_attr_dependencies(&attr, offset, dwarf, unit, at, deps)?;
250    }
251
252    let mut children = die.children();
253    while let Some(child) = children.next()? {
254        let child_entry = child.entry();
255        let child_offset = child_entry.offset().to_unit_section_offset(unit);
256        deps.add_edge(child_offset, offset);
257        if has_die_back_edge(child_entry)? {
258            deps.add_edge(offset, child_offset);
259        }
260        if has_valid_code_range(child_entry, dwarf, unit, at)? {
261            deps.add_root(child_offset);
262        }
263        build_die_dependencies(child, dwarf, unit, at, deps)?;
264    }
265    Ok(())
266}
267
268fn build_attr_dependencies(
269    attr: &read::Attribute<Reader<'_>>,
270    offset: UnitSectionOffset,
271    _dwarf: &read::Dwarf<Reader<'_>>,
272    unit: &read::Unit<Reader<'_>>,
273    _at: &AddressTransform,
274    deps: &mut Dependencies,
275) -> read::Result<()> {
276    match attr.value() {
277        read::AttributeValue::UnitRef(val) => {
278            let ref_offset = val.to_unit_section_offset(unit);
279            deps.add_edge(offset, ref_offset);
280        }
281        read::AttributeValue::DebugInfoRef(val) => {
282            let ref_offset = UnitSectionOffset::DebugInfoOffset(val);
283            deps.add_edge(offset, ref_offset);
284        }
285        _ => (),
286    }
287    Ok(())
288}
wasmtime_cranelift/debug/gc.rs

wasmtime_cranelift/debug/
gc.rs
