Skip to main content

asmkit/core/
linker.rs

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
15/// Links finalized sections and buffers into one in-memory image.
16///
17/// Sections are concatenated in insertion order, each starting at a multiple of
18/// its alignment. Symbols exported with
19/// [`CodeBuffer::bind_symbol`](crate::core::buffer::CodeBuffer::bind_symbol) are
20/// resolved against the final layout: a relocation in any module that references
21/// a defined [`ExternalName`] is rebound to the definition, so a symbol defined
22/// in module A can be called from module B. Remaining undefined symbols stay
23/// external and are resolved at load time with
24/// [`CodeBufferFinalized::load`](crate::core::buffer::CodeBufferFinalized::load).
25pub struct Linker {
26    sections: Vec<FinalizedSection>,
27}
28
29/// Context for an in-memory image-link failure.
30#[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    /// Adds a finalized section to the link. Returns the index that
104    /// [`CodeBufferFinalized::location_in`] takes for marks from this
105    /// section's buffer.
106    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    /// Adds a finalized buffer as a `.text` section aligned to the buffer's
113    /// own alignment. Returns the index that
114    /// [`CodeBufferFinalized::location_in`] takes for marks from `code`.
115    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    /// Number of sections added so far. A linked image added again brings one
124    /// per section it was linked from.
125    fn layout_count(&self) -> usize {
126        self.sections
127            .iter()
128            .map(|section| section.code.section_bases.len())
129            .sum()
130    }
131
132    /// Links all added sections into one image.
133    ///
134    /// Fails with [`AsmError::NoCodeGenerated`] when no sections were added or
135    /// [`AsmError::Link`] with the relevant section, symbol, or relocation.
136    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        // 1. Layout: assign each section a base offset.
153        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        // 2. Collect defined symbols (name -> global offset) in link order.
167        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 &section.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        // 3. Merge label spaces: each section's labels rebased, then one
196        // synthetic label per defined symbol. Relocations against defined
197        // symbols are rewritten to target these labels, which the loading
198        // path resolves internally.
199        let mut label_offsets: SmallVec<[CodeOffset; 16]> = SmallVec::new();
200        for (section, &base) in self.sections.iter().zip(&bases) {
201            for &local_offset in &section.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        // 4. Merge external symbol tables, deduplicating by name so GOT slots
216        // are shared across modules.
217        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 &section.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        // 5. Concatenate data and rebase relocations.
235        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(&section.code.data);
247
248            for reloc in &section.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 = &section
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                            // Defined in this link: bind to the synthetic label.
299                            Some(index) => RelocTarget::Label(Label::from_id(
300                                defined_label_base + index as u32,
301                            )),
302                            // Still external: remap to the merged symbol table.
303                            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        // 6. Record where each input section starts, so marks from its buffer
328        // can still be located.
329        let mut section_bases: SmallVec<[CodeOffset; 1]> = SmallVec::new();
330        let mut layout_maps = SmallVec::new();
331        for (section, &base) in self.sections.iter().zip(&bases) {
332            for &inner in &section.code.section_bases {
333                section_bases.push(base.checked_add(inner).ok_or(AsmError::TooLarge)?);
334            }
335            layout_maps.extend(section.code.layout_maps.iter().cloned());
336        }
337
338        Ok(CodeBufferFinalized {
339            data,
340            relocs,
341            symbols,
342            label_offsets,
343            defined_symbols: defined
344                .into_iter()
345                .map(|(name, offset, _)| (name, offset))
346                .collect(),
347            alignment,
348            arch,
349            section_bases,
350            layout_maps,
351        })
352    }
353}
354
355impl Default for Linker {
356    fn default() -> Self {
357        Self::new()
358    }
359}
360
361fn align_up(offset: CodeOffset, align: u32) -> Result<CodeOffset, AsmError> {
362    if !align.is_power_of_two() {
363        return Err(AsmError::InvalidArgument);
364    }
365    offset
366        .checked_add(align - 1)
367        .map(|offset| offset & !(align - 1))
368        .ok_or(AsmError::TooLarge)
369}