1use alloc::borrow::Cow;
2use alloc::vec::Vec;
3use core::fmt;
4
5use smallvec::SmallVec;
6
7use crate::AsmError;
8use crate::core::buffer::{
9 AsmReloc, CodeBufferFinalized, CodeOffset, ExternalName, Reloc, RelocTarget, SymData,
10 relocation_patch_size,
11};
12use crate::core::operand::{Label, Sym};
13use crate::core::section::FinalizedSection;
14
15pub struct Linker {
26 sections: Vec<FinalizedSection>,
27}
28
29#[derive(Clone, PartialEq, Eq, PartialOrd, Ord, Debug)]
31pub enum LinkError {
32 IncompatibleArch {
33 first_section: Cow<'static, str>,
34 section: Cow<'static, str>,
35 },
36 DuplicateSymbol {
37 name: ExternalName,
38 first_section: Cow<'static, str>,
39 section: Cow<'static, str>,
40 },
41 UnboundSymbol {
42 name: ExternalName,
43 section: Cow<'static, str>,
44 },
45 InvalidRelocation {
46 section: Cow<'static, str>,
47 offset: CodeOffset,
48 kind: Reloc,
49 target: &'static str,
50 id: u32,
51 reason: &'static str,
52 },
53}
54
55impl fmt::Display for LinkError {
56 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
57 match self {
58 Self::IncompatibleArch {
59 first_section,
60 section,
61 } => write!(
62 f,
63 "section {section:?} has an incompatible target (first section: {first_section:?})"
64 ),
65 Self::DuplicateSymbol {
66 name,
67 first_section,
68 section,
69 } => write!(
70 f,
71 "symbol {name} is defined by both {first_section:?} and {section:?}"
72 ),
73 Self::UnboundSymbol { name, section } => {
74 write!(
75 f,
76 "symbol {name} in section {section:?} is bound to no label"
77 )
78 }
79 Self::InvalidRelocation {
80 section,
81 offset,
82 kind,
83 target,
84 id,
85 reason,
86 } => write!(
87 f,
88 "relocation {kind:?} at {offset} in section {section:?} has invalid {target} target {id}: {reason}"
89 ),
90 }
91 }
92}
93
94impl core::error::Error for LinkError {}
95
96impl Linker {
97 pub fn new() -> Self {
98 Self {
99 sections: Vec::new(),
100 }
101 }
102
103 pub fn add_section(&mut self, section: FinalizedSection) -> usize {
107 let index = self.layout_count();
108 self.sections.push(section);
109 index
110 }
111
112 pub fn add_buffer(&mut self, code: CodeBufferFinalized) -> usize {
116 self.add_section(FinalizedSection {
117 name: Cow::Borrowed(".text"),
118 align: code.alignment,
119 code,
120 })
121 }
122
123 fn layout_count(&self) -> usize {
126 self.sections
127 .iter()
128 .map(|section| section.code.section_bases.len())
129 .sum()
130 }
131
132 pub fn link(self) -> Result<CodeBufferFinalized, AsmError> {
137 if self.sections.is_empty() {
138 return Err(AsmError::NoCodeGenerated);
139 }
140 let arch = self.sections[0].code.arch;
141 if let Some(section) = self
142 .sections
143 .iter()
144 .find(|section| section.code.arch != arch)
145 {
146 return Err(AsmError::Link(LinkError::IncompatibleArch {
147 first_section: self.sections[0].name.clone(),
148 section: section.name.clone(),
149 }));
150 }
151
152 let mut bases = Vec::with_capacity(self.sections.len());
154 let mut offset: CodeOffset = 0;
155 let mut alignment = 1u32;
156 for section in &self.sections {
157 offset = align_up(offset, section.align)?;
158 bases.push(offset);
159 let section_size =
160 CodeOffset::try_from(section.code.data.len()).map_err(|_| AsmError::TooLarge)?;
161 offset = offset.checked_add(section_size).ok_or(AsmError::TooLarge)?;
162 alignment = alignment.max(section.align).max(section.code.alignment);
163 }
164 let total_size = offset;
165
166 let mut defined: Vec<(ExternalName, CodeOffset, Cow<'static, str>)> = Vec::new();
168 for (section, &base) in self.sections.iter().zip(&bases) {
169 for (name, local_offset) in §ion.code.defined_symbols {
170 let local_offset = *local_offset;
171 if local_offset == u32::MAX {
172 return Err(AsmError::Link(LinkError::UnboundSymbol {
173 name: name.clone(),
174 section: section.name.clone(),
175 }));
176 }
177 if let Some((_, _, first_section)) = defined
178 .iter()
179 .find(|(defined_name, _, _)| defined_name == name)
180 {
181 return Err(AsmError::Link(LinkError::DuplicateSymbol {
182 name: name.clone(),
183 first_section: first_section.clone(),
184 section: section.name.clone(),
185 }));
186 }
187 defined.push((
188 name.clone(),
189 base.checked_add(local_offset).ok_or(AsmError::TooLarge)?,
190 section.name.clone(),
191 ));
192 }
193 }
194
195 let mut label_offsets: SmallVec<[CodeOffset; 16]> = SmallVec::new();
200 for (section, &base) in self.sections.iter().zip(&bases) {
201 for &local_offset in §ion.code.label_offsets {
202 label_offsets.push(if local_offset == u32::MAX {
203 u32::MAX
204 } else {
205 base.checked_add(local_offset).ok_or(AsmError::TooLarge)?
206 });
207 }
208 }
209 let defined_label_base =
210 u32::try_from(label_offsets.len()).map_err(|_| AsmError::TooLarge)?;
211 for (_, global_offset, _) in &defined {
212 label_offsets.push(*global_offset);
213 }
214
215 let mut symbols: SmallVec<[SymData; 16]> = SmallVec::new();
218 let mut sym_maps: Vec<SmallVec<[u32; 16]>> = Vec::with_capacity(self.sections.len());
219 for section in &self.sections {
220 let mut map: SmallVec<[u32; 16]> = SmallVec::new();
221 for sym in §ion.code.symbols {
222 let id = match symbols.iter().position(|merged| merged.name == sym.name) {
223 Some(index) => index as u32,
224 None => {
225 symbols.push(sym.clone());
226 (symbols.len() - 1) as u32
227 }
228 };
229 map.push(id);
230 }
231 sym_maps.push(map);
232 }
233
234 let mut data: SmallVec<[u8; 1024]> = SmallVec::new();
236 data.resize(total_size as usize, 0);
237 let mut relocs: SmallVec<[AsmReloc; 16]> = SmallVec::new();
238 let mut label_base: u32 = 0;
239 for (section_index, (section, &base)) in self.sections.iter().zip(&bases).enumerate() {
240 let start = base as usize;
241 let end = start
242 .checked_add(section.code.data.len())
243 .ok_or(AsmError::TooLarge)?;
244 data.get_mut(start..end)
245 .ok_or(AsmError::InvalidState)?
246 .copy_from_slice(§ion.code.data);
247
248 for reloc in §ion.code.relocs {
249 let (target, target_id) = match &reloc.target {
250 RelocTarget::Label(label) => ("label", label.id()),
251 RelocTarget::Sym(sym) => ("symbol", sym.id()),
252 };
253 let invalid_reloc = |reason| {
254 AsmError::Link(LinkError::InvalidRelocation {
255 section: section.name.clone(),
256 offset: reloc.offset,
257 kind: reloc.kind,
258 target,
259 id: target_id,
260 reason,
261 })
262 };
263 let patch_size = relocation_patch_size(reloc.kind)
264 .map_err(|_| invalid_reloc("unsupported relocation kind"))?;
265 let patch_end = (reloc.offset as usize)
266 .checked_add(patch_size)
267 .ok_or_else(|| invalid_reloc("patch range overflows"))?;
268 if patch_end > section.code.data.len() {
269 return Err(invalid_reloc("patch range is outside the section"));
270 }
271 let target = match &reloc.target {
272 RelocTarget::Label(label) => {
273 if section
274 .code
275 .label_offsets
276 .get(label.id() as usize)
277 .is_none()
278 {
279 return Err(invalid_reloc("label id is outside the section"));
280 }
281 RelocTarget::Label(Label::from_id(
282 label_base
283 .checked_add(label.id())
284 .ok_or(AsmError::TooLarge)?,
285 ))
286 }
287 RelocTarget::Sym(sym) => {
288 let name = §ion
289 .code
290 .symbols
291 .get(sym.id() as usize)
292 .ok_or_else(|| invalid_reloc("symbol id is outside the section"))?
293 .name;
294 let defined_index = defined
295 .iter()
296 .position(|(defined_name, _, _)| defined_name == name);
297 match defined_index {
298 Some(index) => RelocTarget::Label(Label::from_id(
300 defined_label_base + index as u32,
301 )),
302 None => RelocTarget::Sym(Sym::from_id(
304 *sym_maps[section_index].get(sym.id() as usize).ok_or_else(
305 || invalid_reloc("symbol id is outside the section"),
306 )?,
307 )),
308 }
309 }
310 };
311 relocs.push(AsmReloc {
312 offset: base.checked_add(reloc.offset).ok_or(AsmError::TooLarge)?,
313 kind: reloc.kind,
314 addend: reloc.addend,
315 target,
316 });
317 }
318
319 label_base = label_base
320 .checked_add(
321 u32::try_from(section.code.label_offsets.len())
322 .map_err(|_| AsmError::TooLarge)?,
323 )
324 .ok_or(AsmError::TooLarge)?;
325 }
326
327 let mut section_bases: SmallVec<[CodeOffset; 1]> = SmallVec::new();
330 for (section, &base) in self.sections.iter().zip(&bases) {
331 for &inner in §ion.code.section_bases {
332 section_bases.push(base.checked_add(inner).ok_or(AsmError::TooLarge)?);
333 }
334 }
335
336 Ok(CodeBufferFinalized {
337 data,
338 relocs,
339 symbols,
340 label_offsets,
341 defined_symbols: defined
342 .into_iter()
343 .map(|(name, offset, _)| (name, offset))
344 .collect(),
345 alignment,
346 arch,
347 section_bases,
348 })
349 }
350}
351
352impl Default for Linker {
353 fn default() -> Self {
354 Self::new()
355 }
356}
357
358fn align_up(offset: CodeOffset, align: u32) -> Result<CodeOffset, AsmError> {
359 if !align.is_power_of_two() {
360 return Err(AsmError::InvalidArgument);
361 }
362 offset
363 .checked_add(align - 1)
364 .map(|offset| offset & !(align - 1))
365 .ok_or(AsmError::TooLarge)
366}