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}
334