use alloc::borrow::Cow;
use alloc::vec::Vec;
use core::fmt;
use smallvec::SmallVec;
use crate::AsmError;
use crate::core::buffer::{
AsmReloc, CodeBufferFinalized, CodeOffset, ExternalName, Reloc, RelocTarget, SymData,
relocation_patch_size,
};
use crate::core::operand::{Label, Sym};
use crate::core::section::FinalizedSection;
pub struct Linker {
sections: Vec<FinalizedSection>,
}
#[derive(Clone, PartialEq, Eq, PartialOrd, Ord, Debug)]
pub enum LinkError {
IncompatibleArch {
first_section: Cow<'static, str>,
section: Cow<'static, str>,
},
DuplicateSymbol {
name: ExternalName,
first_section: Cow<'static, str>,
section: Cow<'static, str>,
},
UnboundSymbol {
name: ExternalName,
section: Cow<'static, str>,
},
InvalidRelocation {
section: Cow<'static, str>,
offset: CodeOffset,
kind: Reloc,
target: &'static str,
id: u32,
reason: &'static str,
},
}
impl fmt::Display for LinkError {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
match self {
Self::IncompatibleArch {
first_section,
section,
} => write!(
f,
"section {section:?} has an incompatible target (first section: {first_section:?})"
),
Self::DuplicateSymbol {
name,
first_section,
section,
} => write!(
f,
"symbol {name} is defined by both {first_section:?} and {section:?}"
),
Self::UnboundSymbol { name, section } => {
write!(
f,
"symbol {name} in section {section:?} is bound to no label"
)
}
Self::InvalidRelocation {
section,
offset,
kind,
target,
id,
reason,
} => write!(
f,
"relocation {kind:?} at {offset} in section {section:?} has invalid {target} target {id}: {reason}"
),
}
}
}
impl core::error::Error for LinkError {}
impl Linker {
pub fn new() -> Self {
Self {
sections: Vec::new(),
}
}
pub fn add_section(&mut self, section: FinalizedSection) -> usize {
let index = self.layout_count();
self.sections.push(section);
index
}
pub fn add_buffer(&mut self, code: CodeBufferFinalized) -> usize {
self.add_section(FinalizedSection {
name: Cow::Borrowed(".text"),
align: code.alignment,
code,
})
}
fn layout_count(&self) -> usize {
self.sections
.iter()
.map(|section| section.code.section_bases.len())
.sum()
}
pub fn link(self) -> Result<CodeBufferFinalized, AsmError> {
if self.sections.is_empty() {
return Err(AsmError::NoCodeGenerated);
}
let arch = self.sections[0].code.arch;
if let Some(section) = self
.sections
.iter()
.find(|section| section.code.arch != arch)
{
return Err(AsmError::Link(LinkError::IncompatibleArch {
first_section: self.sections[0].name.clone(),
section: section.name.clone(),
}));
}
let mut bases = Vec::with_capacity(self.sections.len());
let mut offset: CodeOffset = 0;
let mut alignment = 1u32;
for section in &self.sections {
offset = align_up(offset, section.align)?;
bases.push(offset);
let section_size =
CodeOffset::try_from(section.code.data.len()).map_err(|_| AsmError::TooLarge)?;
offset = offset.checked_add(section_size).ok_or(AsmError::TooLarge)?;
alignment = alignment.max(section.align).max(section.code.alignment);
}
let total_size = offset;
let mut defined: Vec<(ExternalName, CodeOffset, Cow<'static, str>)> = Vec::new();
for (section, &base) in self.sections.iter().zip(&bases) {
for (name, local_offset) in §ion.code.defined_symbols {
let local_offset = *local_offset;
if local_offset == u32::MAX {
return Err(AsmError::Link(LinkError::UnboundSymbol {
name: name.clone(),
section: section.name.clone(),
}));
}
if let Some((_, _, first_section)) = defined
.iter()
.find(|(defined_name, _, _)| defined_name == name)
{
return Err(AsmError::Link(LinkError::DuplicateSymbol {
name: name.clone(),
first_section: first_section.clone(),
section: section.name.clone(),
}));
}
defined.push((
name.clone(),
base.checked_add(local_offset).ok_or(AsmError::TooLarge)?,
section.name.clone(),
));
}
}
let mut label_offsets: SmallVec<[CodeOffset; 16]> = SmallVec::new();
for (section, &base) in self.sections.iter().zip(&bases) {
for &local_offset in §ion.code.label_offsets {
label_offsets.push(if local_offset == u32::MAX {
u32::MAX
} else {
base.checked_add(local_offset).ok_or(AsmError::TooLarge)?
});
}
}
let defined_label_base =
u32::try_from(label_offsets.len()).map_err(|_| AsmError::TooLarge)?;
for (_, global_offset, _) in &defined {
label_offsets.push(*global_offset);
}
let mut symbols: SmallVec<[SymData; 16]> = SmallVec::new();
let mut sym_maps: Vec<SmallVec<[u32; 16]>> = Vec::with_capacity(self.sections.len());
for section in &self.sections {
let mut map: SmallVec<[u32; 16]> = SmallVec::new();
for sym in §ion.code.symbols {
let id = match symbols.iter().position(|merged| merged.name == sym.name) {
Some(index) => index as u32,
None => {
symbols.push(sym.clone());
(symbols.len() - 1) as u32
}
};
map.push(id);
}
sym_maps.push(map);
}
let mut data: SmallVec<[u8; 1024]> = SmallVec::new();
data.resize(total_size as usize, 0);
let mut relocs: SmallVec<[AsmReloc; 16]> = SmallVec::new();
let mut label_base: u32 = 0;
for (section_index, (section, &base)) in self.sections.iter().zip(&bases).enumerate() {
let start = base as usize;
let end = start
.checked_add(section.code.data.len())
.ok_or(AsmError::TooLarge)?;
data.get_mut(start..end)
.ok_or(AsmError::InvalidState)?
.copy_from_slice(§ion.code.data);
for reloc in §ion.code.relocs {
let (target, target_id) = match &reloc.target {
RelocTarget::Label(label) => ("label", label.id()),
RelocTarget::Sym(sym) => ("symbol", sym.id()),
};
let invalid_reloc = |reason| {
AsmError::Link(LinkError::InvalidRelocation {
section: section.name.clone(),
offset: reloc.offset,
kind: reloc.kind,
target,
id: target_id,
reason,
})
};
let patch_size = relocation_patch_size(reloc.kind)
.map_err(|_| invalid_reloc("unsupported relocation kind"))?;
let patch_end = (reloc.offset as usize)
.checked_add(patch_size)
.ok_or_else(|| invalid_reloc("patch range overflows"))?;
if patch_end > section.code.data.len() {
return Err(invalid_reloc("patch range is outside the section"));
}
let target = match &reloc.target {
RelocTarget::Label(label) => {
if section
.code
.label_offsets
.get(label.id() as usize)
.is_none()
{
return Err(invalid_reloc("label id is outside the section"));
}
RelocTarget::Label(Label::from_id(
label_base
.checked_add(label.id())
.ok_or(AsmError::TooLarge)?,
))
}
RelocTarget::Sym(sym) => {
let name = §ion
.code
.symbols
.get(sym.id() as usize)
.ok_or_else(|| invalid_reloc("symbol id is outside the section"))?
.name;
let defined_index = defined
.iter()
.position(|(defined_name, _, _)| defined_name == name);
match defined_index {
Some(index) => RelocTarget::Label(Label::from_id(
defined_label_base + index as u32,
)),
None => RelocTarget::Sym(Sym::from_id(
*sym_maps[section_index].get(sym.id() as usize).ok_or_else(
|| invalid_reloc("symbol id is outside the section"),
)?,
)),
}
}
};
relocs.push(AsmReloc {
offset: base.checked_add(reloc.offset).ok_or(AsmError::TooLarge)?,
kind: reloc.kind,
addend: reloc.addend,
target,
});
}
label_base = label_base
.checked_add(
u32::try_from(section.code.label_offsets.len())
.map_err(|_| AsmError::TooLarge)?,
)
.ok_or(AsmError::TooLarge)?;
}
let mut section_bases: SmallVec<[CodeOffset; 1]> = SmallVec::new();
let mut layout_maps = SmallVec::new();
for (section, &base) in self.sections.iter().zip(&bases) {
for &inner in §ion.code.section_bases {
section_bases.push(base.checked_add(inner).ok_or(AsmError::TooLarge)?);
}
layout_maps.extend(section.code.layout_maps.iter().cloned());
}
Ok(CodeBufferFinalized {
data,
relocs,
symbols,
label_offsets,
defined_symbols: defined
.into_iter()
.map(|(name, offset, _)| (name, offset))
.collect(),
alignment,
arch,
section_bases,
layout_maps,
})
}
}
impl Default for Linker {
fn default() -> Self {
Self::new()
}
}
fn align_up(offset: CodeOffset, align: u32) -> Result<CodeOffset, AsmError> {
if !align.is_power_of_two() {
return Err(AsmError::InvalidArgument);
}
offset
.checked_add(align - 1)
.map(|offset| offset & !(align - 1))
.ok_or(AsmError::TooLarge)
}