wasmtime_internal_cranelift/debug/
gc.rs

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

wasmtime_internal_cranelift/debug/
gc.rs
