thorin/
index.rs

1use std::fmt;
2
3use gimli::{
4    write::{EndianVec, Writer},
5    Encoding,
6};
7use tracing::{debug, trace};
8
9use crate::{
10    error::{Error, Result},
11    ext::PackageFormatExt,
12    package::DwarfObject,
13};
14
15/// Helper trait for types that can be used in creating the `.debug_{cu,tu}_index` hash table.
16pub(crate) trait Bucketable {
17    fn index(&self) -> u64;
18}
19
20/// Returns a hash table computed for `elements`. Used in the `.debug_{cu,tu}_index` sections.
21#[tracing::instrument(level = "trace", skip_all)]
22fn bucket<B: Bucketable + fmt::Debug>(elements: &[B]) -> Vec<u32> {
23    let unit_count: u32 = elements.len().try_into().expect("unit count larger than u32");
24    let num_buckets = if elements.len() < 2 { 2 } else { (3 * unit_count / 2).next_power_of_two() };
25    let mask: u64 = num_buckets as u64 - 1;
26    trace!(?mask);
27
28    let mut buckets = vec![0u32; num_buckets as usize];
29    trace!(?buckets);
30    for (elem, i) in elements.iter().zip(0u32..) {
31        trace!(?i, ?elem);
32        let s = elem.index();
33        let mut h = s & mask;
34        let hp = ((s >> 32) & mask) | 1;
35        trace!(?s, ?h, ?hp);
36
37        while buckets[h as usize] > 0 {
38            assert!(elements[(buckets[h as usize] - 1) as usize].index() != elem.index());
39            h = (h + hp) & mask;
40            trace!(?h);
41        }
42
43        buckets[h as usize] = i + 1;
44        trace!(?buckets);
45    }
46
47    buckets
48}
49
50/// New-type'd offset into a section of a compilation/type unit's contribution.
51#[derive(Copy, Clone, Eq, Hash, PartialEq)]
52pub(crate) struct ContributionOffset(pub(crate) u64);
53
54impl fmt::Debug for ContributionOffset {
55    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
56        write!(f, "ContributionOffset({:#x})", self.0)
57    }
58}
59
60/// Type alias for the size of a compilation/type unit's contribution.
61type ContributionSize = u64;
62
63/// Contribution to a section - offset and size.
64#[derive(Copy, Clone, Debug, Eq, Hash, PartialEq)]
65pub(crate) struct Contribution {
66    /// Offset of this contribution into its containing section.
67    pub(crate) offset: ContributionOffset,
68    /// Size of this contribution in its containing section.
69    pub(crate) size: ContributionSize,
70}
71
72/// Populated columns in the `.debug_cu_index` or `.debug_tu_index` section.
73#[derive(Copy, Clone, Debug, Default)]
74pub(crate) struct IndexColumns {
75    pub(crate) debug_info: bool,
76    pub(crate) debug_types: bool,
77    pub(crate) debug_abbrev: bool,
78    pub(crate) debug_line: bool,
79    pub(crate) debug_loc: bool,
80    pub(crate) debug_loclists: bool,
81    pub(crate) debug_rnglists: bool,
82    pub(crate) debug_str_offsets: bool,
83    pub(crate) debug_macinfo: bool,
84    pub(crate) debug_macro: bool,
85}
86
87impl IndexColumns {
88    /// Return the number of columns required for all index entries.
89    fn number_of_columns(&self) -> u32 {
90        self.debug_info as u32
91            + self.debug_types as u32
92            + self.debug_abbrev as u32
93            + self.debug_line as u32
94            + self.debug_loc as u32
95            + self.debug_loclists as u32
96            + self.debug_rnglists as u32
97            + self.debug_str_offsets as u32
98            + self.debug_macinfo as u32
99            + self.debug_macro as u32
100    }
101
102    /// Update the columns to include the columns required for an index entry.
103    fn add_entry(&mut self, entry: &IndexEntry) {
104        self.debug_info |= entry.debug_info.is_some();
105        self.debug_types |= entry.debug_types.is_some();
106        self.debug_abbrev |= entry.debug_abbrev.is_some();
107        self.debug_line |= entry.debug_line.is_some();
108        self.debug_loc |= entry.debug_loc.is_some();
109        self.debug_loclists |= entry.debug_loclists.is_some();
110        self.debug_rnglists |= entry.debug_rnglists.is_some();
111        self.debug_str_offsets |= entry.debug_str_offsets.is_some();
112        self.debug_macinfo |= entry.debug_macinfo.is_some();
113        self.debug_macro |= entry.debug_macro.is_some();
114    }
115
116    /// Write the header row for the columns.
117    ///
118    /// There is only a single header row in any index section, its contents depend on the output
119    /// format and the columns from contributions so the complete index entries are required to
120    /// know what header to write.
121    fn write_header<Endian: gimli::Endianity>(
122        &self,
123        out: &mut EndianVec<Endian>,
124        encoding: Encoding,
125    ) -> Result<()> {
126        if encoding.is_gnu_extension_dwarf_package_format() {
127            if self.debug_info {
128                out.write_u32(gimli::DW_SECT_V2_INFO.0)?;
129            }
130            if self.debug_types {
131                out.write_u32(gimli::DW_SECT_V2_TYPES.0)?;
132            }
133            if self.debug_abbrev {
134                out.write_u32(gimli::DW_SECT_V2_ABBREV.0)?;
135            }
136            if self.debug_line {
137                out.write_u32(gimli::DW_SECT_V2_LINE.0)?;
138            }
139            if self.debug_loc {
140                out.write_u32(gimli::DW_SECT_V2_LOC.0)?;
141            }
142            if self.debug_str_offsets {
143                out.write_u32(gimli::DW_SECT_V2_STR_OFFSETS.0)?;
144            }
145            if self.debug_macinfo {
146                out.write_u32(gimli::DW_SECT_V2_MACINFO.0)?;
147            }
148            if self.debug_macro {
149                out.write_u32(gimli::DW_SECT_V2_MACRO.0)?;
150            }
151        } else {
152            if self.debug_info {
153                out.write_u32(gimli::DW_SECT_INFO.0)?;
154            }
155            if self.debug_abbrev {
156                out.write_u32(gimli::DW_SECT_ABBREV.0)?;
157            }
158            if self.debug_line {
159                out.write_u32(gimli::DW_SECT_LINE.0)?;
160            }
161            if self.debug_loclists {
162                out.write_u32(gimli::DW_SECT_LOCLISTS.0)?;
163            }
164            if self.debug_rnglists {
165                out.write_u32(gimli::DW_SECT_RNGLISTS.0)?;
166            }
167            if self.debug_str_offsets {
168                out.write_u32(gimli::DW_SECT_STR_OFFSETS.0)?;
169            }
170            if self.debug_macro {
171                out.write_u32(gimli::DW_SECT_MACRO.0)?;
172            }
173        }
174
175        Ok(())
176    }
177}
178
179/// Entry into the `.debug_cu_index` or `.debug_tu_index` section.
180///
181/// Contributions from `.debug_loclists.dwo` and `.debug_rnglists.dwo` from type units aren't
182/// defined in the DWARF 5 specification but are tested by `llvm-dwp`'s test suite.
183#[derive(Copy, Clone, Debug, Eq, Hash, PartialEq)]
184pub(crate) struct IndexEntry {
185    pub(crate) encoding: Encoding,
186    pub(crate) id: DwarfObject,
187    pub(crate) debug_info: Option<Contribution>,
188    pub(crate) debug_types: Option<Contribution>,
189    pub(crate) debug_abbrev: Option<Contribution>,
190    pub(crate) debug_line: Option<Contribution>,
191    pub(crate) debug_loc: Option<Contribution>,
192    pub(crate) debug_loclists: Option<Contribution>,
193    pub(crate) debug_rnglists: Option<Contribution>,
194    pub(crate) debug_str_offsets: Option<Contribution>,
195    pub(crate) debug_macinfo: Option<Contribution>,
196    pub(crate) debug_macro: Option<Contribution>,
197}
198
199impl IndexEntry {
200    /// Visit each contribution in an entry, calling `proj` to write a specific field.
201    #[tracing::instrument(level = "trace", skip(out, proj))]
202    fn write_contribution<Endian, Proj>(
203        &self,
204        out: &mut EndianVec<Endian>,
205        proj: Proj,
206        columns: &IndexColumns,
207    ) -> Result<()>
208    where
209        Endian: gimli::Endianity,
210        Proj: Copy + Fn(Contribution) -> u32,
211    {
212        let proj = |contrib: Option<Contribution>| contrib.map(proj).unwrap_or(0);
213        if columns.debug_info {
214            out.write_u32(proj(self.debug_info))?;
215        }
216        if columns.debug_types {
217            out.write_u32(proj(self.debug_types))?;
218        }
219        if columns.debug_abbrev {
220            out.write_u32(proj(self.debug_abbrev))?;
221        }
222        if columns.debug_line {
223            out.write_u32(proj(self.debug_line))?;
224        }
225        if columns.debug_loc {
226            out.write_u32(proj(self.debug_loc))?;
227        }
228        if columns.debug_loclists {
229            out.write_u32(proj(self.debug_loclists))?;
230        }
231        if columns.debug_rnglists {
232            out.write_u32(proj(self.debug_rnglists))?;
233        }
234        if columns.debug_str_offsets {
235            out.write_u32(proj(self.debug_str_offsets))?;
236        }
237        if columns.debug_macinfo {
238            out.write_u32(proj(self.debug_macinfo))?;
239        }
240        if columns.debug_macro {
241            out.write_u32(proj(self.debug_macro))?;
242        }
243
244        Ok(())
245    }
246}
247
248impl Bucketable for IndexEntry {
249    fn index(&self) -> u64 {
250        self.id.index()
251    }
252}
253
254/// Write a `.debug_{cu,tu}_index` section given `IndexEntry`s.
255#[tracing::instrument(level = "trace")]
256pub(crate) fn write_index<'output, Endian: gimli::Endianity>(
257    endianness: Endian,
258    entries: &[IndexEntry],
259) -> Result<EndianVec<Endian>> {
260    let mut out = EndianVec::new(endianness);
261
262    if entries.len() == 0 {
263        return Ok(out);
264    }
265
266    let buckets = bucket(entries);
267    debug!(?buckets);
268
269    let encoding = entries[0].encoding;
270    if !entries.iter().all(|e| e.encoding == encoding) {
271        return Err(Error::MixedInputEncodings);
272    }
273    debug!(?encoding);
274
275    let mut columns = IndexColumns::default();
276    for entry in entries {
277        columns.add_entry(entry);
278    }
279    let num_columns = columns.number_of_columns();
280    debug!(?entries, ?columns, ?num_columns);
281
282    // Write header..
283    if encoding.is_gnu_extension_dwarf_package_format() {
284        // GNU Extension
285        out.write_u32(2)?;
286    } else {
287        // DWARF 5
288        out.write_u16(5)?;
289        // Reserved padding
290        out.write_u16(0)?;
291    }
292
293    // Columns (e.g. info, abbrev, loc, etc.)
294    out.write_u32(num_columns)?;
295    // Number of units
296    out.write_u32(entries.len().try_into().expect("number of units larger than u32"))?;
297    // Number of buckets
298    out.write_u32(buckets.len().try_into().expect("number of buckets larger than u32"))?;
299
300    // Write signatures..
301    for i in &buckets {
302        if *i > 0 {
303            out.write_u64(entries[(*i - 1) as usize].index())?;
304        } else {
305            out.write_u64(0)?;
306        }
307    }
308
309    // Write indices..
310    for i in &buckets {
311        out.write_u32(*i)?;
312    }
313
314    // Write column headers..
315    columns.write_header(&mut out, encoding)?;
316
317    // Write offsets..
318    let write_offset = |contrib: Contribution| {
319        contrib.offset.0.try_into().expect("contribution offset larger than u32")
320    };
321    for entry in entries {
322        entry.write_contribution(&mut out, write_offset, &columns)?;
323    }
324
325    // Write sizes..
326    let write_size =
327        |contrib: Contribution| contrib.size.try_into().expect("contribution size larger than u32");
328    for entry in entries {
329        entry.write_contribution(&mut out, write_size, &columns)?;
330    }
331
332    Ok(out)
333}
thorin/index.rs

thorin/
index.rs
