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::patch::{PatchBlock, PatchCatalog, PatchSite};
14use crate::core::section::FinalizedSection;
15
16pub struct Linker {
34 sections: Vec<FinalizedSection>,
35}
36
37#[derive(Clone, PartialEq, Eq, PartialOrd, Ord, Debug)]
39pub enum LinkError {
40 IncompatibleArch {
41 first_section: Cow<'static, str>,
42 section: Cow<'static, str>,
43 },
44 DuplicateSymbol {
45 name: ExternalName,
46 first_section: Cow<'static, str>,
47 section: Cow<'static, str>,
48 },
49 UnboundSymbol {
50 name: ExternalName,
51 section: Cow<'static, str>,
52 },
53 InvalidRelocation {
54 section: Cow<'static, str>,
55 offset: CodeOffset,
56 kind: Reloc,
57 target: &'static str,
58 id: u32,
59 reason: &'static str,
60 },
61}
62
63impl fmt::Display for LinkError {
64 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
65 match self {
66 Self::IncompatibleArch {
67 first_section,
68 section,
69 } => write!(
70 f,
71 "section {section:?} has an incompatible target (first section: {first_section:?})"
72 ),
73 Self::DuplicateSymbol {
74 name,
75 first_section,
76 section,
77 } => write!(
78 f,
79 "symbol {name} is defined by both {first_section:?} and {section:?}"
80 ),
81 Self::UnboundSymbol { name, section } => {
82 write!(
83 f,
84 "symbol {name} in section {section:?} is bound to no label"
85 )
86 }
87 Self::InvalidRelocation {
88 section,
89 offset,
90 kind,
91 target,
92 id,
93 reason,
94 } => write!(
95 f,
96 "relocation {kind:?} at {offset} in section {section:?} has invalid {target} target {id}: {reason}"
97 ),
98 }
99 }
100}
101
102impl core::error::Error for LinkError {}
103
104impl Linker {
105 pub fn new() -> Self {
106 Self {
107 sections: Vec::new(),
108 }
109 }
110
111 pub fn add_section(&mut self, section: FinalizedSection) {
113 self.sections.push(section);
114 }
115
116 pub fn add_buffer(&mut self, code: CodeBufferFinalized) {
119 self.sections.push(FinalizedSection {
120 name: Cow::Borrowed(".text"),
121 align: code.alignment,
122 code,
123 });
124 }
125
126 pub fn link(self) -> Result<CodeBufferFinalized, AsmError> {
131 if self.sections.is_empty() {
132 return Err(AsmError::NoCodeGenerated);
133 }
134 let arch = self.sections[0].code.patch_catalog.arch();
135 if let Some(section) = self
136 .sections
137 .iter()
138 .find(|section| section.code.patch_catalog.arch() != arch)
139 {
140 return Err(AsmError::Link(LinkError::IncompatibleArch {
141 first_section: self.sections[0].name.clone(),
142 section: section.name.clone(),
143 }));
144 }
145
146 let mut bases = Vec::with_capacity(self.sections.len());
148 let mut offset: CodeOffset = 0;
149 let mut alignment = 1u32;
150 for section in &self.sections {
151 offset = align_up(offset, section.align)?;
152 bases.push(offset);
153 let section_size =
154 CodeOffset::try_from(section.code.data.len()).map_err(|_| AsmError::TooLarge)?;
155 offset = offset.checked_add(section_size).ok_or(AsmError::TooLarge)?;
156 alignment = alignment.max(section.align).max(section.code.alignment);
157 }
158 let total_size = offset;
159
160 let mut defined: Vec<(ExternalName, CodeOffset, Cow<'static, str>)> = Vec::new();
162 for (section, &base) in self.sections.iter().zip(&bases) {
163 for (name, local_offset) in §ion.code.defined_symbols {
164 let local_offset = *local_offset;
165 if local_offset == u32::MAX {
166 return Err(AsmError::Link(LinkError::UnboundSymbol {
167 name: name.clone(),
168 section: section.name.clone(),
169 }));
170 }
171 if let Some((_, _, first_section)) = defined
172 .iter()
173 .find(|(defined_name, _, _)| defined_name == name)
174 {
175 return Err(AsmError::Link(LinkError::DuplicateSymbol {
176 name: name.clone(),
177 first_section: first_section.clone(),
178 section: section.name.clone(),
179 }));
180 }
181 defined.push((
182 name.clone(),
183 base.checked_add(local_offset).ok_or(AsmError::TooLarge)?,
184 section.name.clone(),
185 ));
186 }
187 }
188
189 let mut label_offsets: SmallVec<[CodeOffset; 16]> = SmallVec::new();
194 for (section, &base) in self.sections.iter().zip(&bases) {
195 for &local_offset in §ion.code.label_offsets {
196 label_offsets.push(if local_offset == u32::MAX {
197 u32::MAX
198 } else {
199 base.checked_add(local_offset).ok_or(AsmError::TooLarge)?
200 });
201 }
202 }
203 let defined_label_base =
204 u32::try_from(label_offsets.len()).map_err(|_| AsmError::TooLarge)?;
205 for (_, global_offset, _) in &defined {
206 label_offsets.push(*global_offset);
207 }
208
209 let mut symbols: SmallVec<[SymData; 16]> = SmallVec::new();
212 let mut sym_maps: Vec<SmallVec<[u32; 16]>> = Vec::with_capacity(self.sections.len());
213 for section in &self.sections {
214 let mut map: SmallVec<[u32; 16]> = SmallVec::new();
215 for sym in §ion.code.symbols {
216 let id = match symbols.iter().position(|merged| merged.name == sym.name) {
217 Some(index) => index as u32,
218 None => {
219 symbols.push(sym.clone());
220 (symbols.len() - 1) as u32
221 }
222 };
223 map.push(id);
224 }
225 sym_maps.push(map);
226 }
227
228 let mut data: SmallVec<[u8; 1024]> = SmallVec::new();
230 data.resize(total_size as usize, 0);
231 let mut relocs: SmallVec<[AsmReloc; 16]> = SmallVec::new();
232 let mut label_base: u32 = 0;
233 for (section_index, (section, &base)) in self.sections.iter().zip(&bases).enumerate() {
234 let start = base as usize;
235 let end = start
236 .checked_add(section.code.data.len())
237 .ok_or(AsmError::TooLarge)?;
238 data.get_mut(start..end)
239 .ok_or(AsmError::InvalidState)?
240 .copy_from_slice(§ion.code.data);
241
242 for reloc in §ion.code.relocs {
243 let (target, target_id) = match &reloc.target {
244 RelocTarget::Label(label) => ("label", label.id()),
245 RelocTarget::Sym(sym) => ("symbol", sym.id()),
246 };
247 let invalid_reloc = |reason| {
248 AsmError::Link(LinkError::InvalidRelocation {
249 section: section.name.clone(),
250 offset: reloc.offset,
251 kind: reloc.kind,
252 target,
253 id: target_id,
254 reason,
255 })
256 };
257 let patch_size = relocation_patch_size(reloc.kind)
258 .map_err(|_| invalid_reloc("unsupported relocation kind"))?;
259 let patch_end = (reloc.offset as usize)
260 .checked_add(patch_size)
261 .ok_or_else(|| invalid_reloc("patch range overflows"))?;
262 if patch_end > section.code.data.len() {
263 return Err(invalid_reloc("patch range is outside the section"));
264 }
265 let target = match &reloc.target {
266 RelocTarget::Label(label) => {
267 if section
268 .code
269 .label_offsets
270 .get(label.id() as usize)
271 .is_none()
272 {
273 return Err(invalid_reloc("label id is outside the section"));
274 }
275 RelocTarget::Label(Label::from_id(
276 label_base
277 .checked_add(label.id())
278 .ok_or(AsmError::TooLarge)?,
279 ))
280 }
281 RelocTarget::Sym(sym) => {
282 let name = §ion
283 .code
284 .symbols
285 .get(sym.id() as usize)
286 .ok_or_else(|| invalid_reloc("symbol id is outside the section"))?
287 .name;
288 let defined_index = defined
289 .iter()
290 .position(|(defined_name, _, _)| defined_name == name);
291 match defined_index {
292 Some(index) => RelocTarget::Label(Label::from_id(
294 defined_label_base + index as u32,
295 )),
296 None => RelocTarget::Sym(Sym::from_id(
298 *sym_maps[section_index].get(sym.id() as usize).ok_or_else(
299 || invalid_reloc("symbol id is outside the section"),
300 )?,
301 )),
302 }
303 }
304 };
305 relocs.push(AsmReloc {
306 offset: base.checked_add(reloc.offset).ok_or(AsmError::TooLarge)?,
307 kind: reloc.kind,
308 addend: reloc.addend,
309 target,
310 });
311 }
312
313 label_base = label_base
314 .checked_add(
315 u32::try_from(section.code.label_offsets.len())
316 .map_err(|_| AsmError::TooLarge)?,
317 )
318 .ok_or(AsmError::TooLarge)?;
319 }
320
321 let mut blocks: SmallVec<[PatchBlock; 4]> = SmallVec::new();
323 let mut sites: SmallVec<[PatchSite; 8]> = SmallVec::new();
324 for (section, &base) in self.sections.iter().zip(&bases) {
325 let catalog = §ion.code.patch_catalog;
326 for block in catalog.blocks() {
327 blocks.push(PatchBlock {
328 offset: base.checked_add(block.offset).ok_or(AsmError::TooLarge)?,
329 ..*block
330 });
331 }
332 for site in catalog.sites() {
333 sites.push(PatchSite {
334 offset: base.checked_add(site.offset).ok_or(AsmError::TooLarge)?,
335 current_target: base
336 .checked_add(site.current_target)
337 .ok_or(AsmError::TooLarge)?,
338 ..*site
339 });
340 }
341 }
342
343 Ok(CodeBufferFinalized {
344 data,
345 relocs,
346 symbols,
347 label_offsets,
348 defined_symbols: defined
349 .into_iter()
350 .map(|(name, offset, _)| (name, offset))
351 .collect(),
352 alignment,
353 patch_catalog: PatchCatalog::with_parts(arch, blocks, sites),
354 })
355 }
356}
357
358impl Default for Linker {
359 fn default() -> Self {
360 Self::new()
361 }
362}
363
364fn align_up(offset: CodeOffset, align: u32) -> Result<CodeOffset, AsmError> {
365 if !align.is_power_of_two() {
366 return Err(AsmError::InvalidArgument);
367 }
368 offset
369 .checked_add(align - 1)
370 .map(|offset| offset & !(align - 1))
371 .ok_or(AsmError::TooLarge)
372}
373
374#[cfg(test)]
375mod tests {
376 use super::*;
377 use crate::core::arch_traits::Arch;
378 use crate::core::buffer::{CodeBuffer, Reloc, RelocDistance};
379 use crate::core::section::Section;
380 use crate::core::target::Environment;
381
382 fn defined_label(buf: &mut CodeBuffer, name: &'static str) -> Label {
383 let label = buf.get_label();
384 buf.bind_label(label);
385 buf.bind_symbol(name, label);
386 label
387 }
388
389 #[test]
390 fn section_layout_respects_alignment() {
391 let mut text = Section::new(".text", 16).unwrap();
392 let text_entry = defined_label(text.buffer_mut(), "entry");
393 text.buffer_mut().write_u8(0xC3);
394 assert_eq!(text.buffer().label_offset(text_entry), 0);
395
396 let mut data = Section::new(".data", 16).unwrap();
397 let data_sym = defined_label(data.buffer_mut(), "data_sym");
398 data.buffer_mut().write_u8(0xAA);
399 assert_eq!(data.buffer().label_offset(data_sym), 0);
400
401 let mut linker = Linker::new();
402 linker.add_section(text.finish().unwrap());
403 linker.add_section(data.finish().unwrap());
404
405 let image = linker.link().unwrap();
406 assert_eq!(image.total_size(), 17);
408 assert_eq!(image.alignment(), 32);
411 assert_eq!(image.defined_symbol_str("entry"), Some(0));
412 assert_eq!(image.defined_symbol_str("data_sym"), Some(16));
413 assert_eq!(image.data()[0], 0xC3);
414 assert_eq!(image.data()[16], 0xAA);
415 }
416
417 #[test]
418 fn cross_module_symbol_resolution() {
419 let mut a = CodeBuffer::new(Environment::new(Arch::X64));
421 defined_label(&mut a, "callee");
422 a.write_u8(0xC3); let mut b = CodeBuffer::new(Environment::new(Arch::X64));
427 let callee = b.extern_sym("callee", RelocDistance::Far);
428 let missing = b.extern_sym("missing", RelocDistance::Far);
429 b.add_reloc(Reloc::Abs8, RelocTarget::Sym(callee), 0);
430 b.write_u64(0);
431 b.add_reloc(Reloc::Abs8, RelocTarget::Sym(missing), 0);
432 b.write_u64(0);
433
434 let mut linker = Linker::new();
435 linker.add_buffer(a.finish().unwrap());
436 linker.add_buffer(b.finish().unwrap());
437
438 let image = linker.link().unwrap();
439 assert_eq!(image.defined_symbol_str("callee"), Some(0));
440 assert_eq!(image.relocs().len(), 2);
441
442 match &image.relocs()[0].target {
444 RelocTarget::Label(label) => {
445 assert_eq!(image.label_offsets[label.id() as usize], 0);
446 }
447 target => panic!("expected label target, got {target:?}"),
448 }
449 match &image.relocs()[1].target {
452 RelocTarget::Sym(sym) => {
453 assert_eq!(
454 image.symbol_name(*sym),
455 Some(&crate::core::buffer::ExternalName::Symbol("missing".into()))
456 );
457 }
458 target => panic!("expected symbol target, got {target:?}"),
459 }
460 }
461
462 #[test]
463 fn label_relocs_are_rebased_to_the_section_base() {
464 let mut a = CodeBuffer::new(Environment::new(Arch::X64));
467 a.write_u64(0);
468
469 let mut b = CodeBuffer::new(Environment::new(Arch::X64));
470 let target = b.get_label();
471 b.add_reloc(Reloc::Abs8, RelocTarget::Label(target), 0);
472 b.write_u64(0);
473 b.bind_label(target);
474
475 let mut linker = Linker::new();
476 linker.add_buffer(a.finish().unwrap());
477 linker.add_buffer(b.finish().unwrap());
478
479 let image = linker.link().unwrap();
480 match &image.relocs()[0].target {
481 RelocTarget::Label(label) => {
482 assert_eq!(image.label_offsets[label.id() as usize], 32 + 8);
486 }
487 target => panic!("expected label target, got {target:?}"),
488 }
489 }
490
491 #[test]
492 fn cross_module_user_symbol_resolution() {
493 const FUNC: u32 = 0;
494 let mut a = CodeBuffer::new(Environment::new(Arch::X64));
496 let label = a.get_label();
497 a.bind_label(label);
498 a.bind_symbol(ExternalName::user(FUNC, 1), label);
499 a.write_u8(0xC3);
500
501 let mut b = CodeBuffer::new(Environment::new(Arch::X64));
503 let callee = b.extern_user(FUNC, 1, RelocDistance::Far);
504 let missing = b.extern_user(FUNC, 2, RelocDistance::Far);
505 b.add_reloc(Reloc::Abs8, RelocTarget::Sym(callee), 0);
506 b.write_u64(0);
507 b.add_reloc(Reloc::Abs8, RelocTarget::Sym(missing), 0);
508 b.write_u64(0);
509
510 let mut linker = Linker::new();
511 linker.add_buffer(a.finish().unwrap());
512 linker.add_buffer(b.finish().unwrap());
513
514 let image = linker.link().unwrap();
515 assert_eq!(
516 image.defined_symbol_offset(&ExternalName::user(FUNC, 1)),
517 Some(0)
518 );
519 assert_eq!(image.relocs().len(), 2);
520
521 match &image.relocs()[0].target {
522 RelocTarget::Label(label) => {
523 assert_eq!(image.label_offsets[label.id() as usize], 0);
524 }
525 target => panic!("expected label target, got {target:?}"),
526 }
527 match &image.relocs()[1].target {
528 RelocTarget::Sym(sym) => {
529 assert_eq!(image.symbol_name(*sym), Some(&ExternalName::user(FUNC, 2)));
530 }
531 target => panic!("expected symbol target, got {target:?}"),
532 }
533 }
534
535 #[test]
536 fn duplicate_user_definition_is_an_error() {
537 const FUNC: u32 = 0;
538 let mut a = CodeBuffer::new(Environment::new(Arch::X64));
539 let label = a.get_label();
540 a.bind_label(label);
541 a.bind_symbol(ExternalName::user(FUNC, 7), label);
542
543 let mut b = CodeBuffer::new(Environment::new(Arch::X64));
544 let label = b.get_label();
545 b.bind_label(label);
546 b.bind_symbol(ExternalName::user(FUNC, 7), label);
547
548 let mut linker = Linker::new();
549 linker.add_buffer(a.finish().unwrap());
550 linker.add_buffer(b.finish().unwrap());
551
552 assert_eq!(
553 linker.link().err(),
554 Some(AsmError::Link(LinkError::DuplicateSymbol {
555 name: ExternalName::user(FUNC, 7),
556 first_section: ".text".into(),
557 section: ".text".into(),
558 }))
559 );
560 }
561
562 #[test]
563 fn duplicate_definition_is_an_error() {
564 let mut a = CodeBuffer::new(Environment::new(Arch::X64));
565 defined_label(&mut a, "dup");
566 let mut b = CodeBuffer::new(Environment::new(Arch::X64));
567 defined_label(&mut b, "dup");
568
569 let mut linker = Linker::new();
570 linker.add_buffer(a.finish().unwrap());
571 linker.add_buffer(b.finish().unwrap());
572
573 assert_eq!(
574 linker.link().err(),
575 Some(AsmError::Link(LinkError::DuplicateSymbol {
576 name: "dup".into(),
577 first_section: ".text".into(),
578 section: ".text".into(),
579 }))
580 );
581 }
582
583 #[test]
584 fn empty_link_is_an_error() {
585 assert_eq!(Linker::new().link().err(), Some(AsmError::NoCodeGenerated));
586 }
587
588 #[test]
589 fn mixed_target_sections_are_rejected() {
590 let x64 = Section::with_env(".x64", 1, Environment::new(Arch::X64))
591 .unwrap()
592 .finish()
593 .unwrap();
594 let aarch64 = Section::with_env(".a64", 4, Environment::new(Arch::AArch64))
595 .unwrap()
596 .finish()
597 .unwrap();
598 let mut linker = Linker::new();
599 linker.add_section(x64);
600 linker.add_section(aarch64);
601
602 assert_eq!(
603 linker.link().err(),
604 Some(AsmError::Link(LinkError::IncompatibleArch {
605 first_section: ".x64".into(),
606 section: ".a64".into(),
607 }))
608 );
609 }
610
611 #[test]
612 fn defined_symbol_bound_to_unbound_label_is_an_error() {
613 let mut a = CodeBuffer::new(Environment::new(Arch::X64));
614 let label = a.get_label();
615 a.bind_symbol("dangling", label);
616 a.write_u8(0xC3);
617
618 assert_eq!(a.finish().err(), Some(AsmError::UnboundLabel));
619 }
620
621 #[test]
622 fn unbound_symbol_reports_its_name_and_section() {
623 let mut buffer = CodeBuffer::new(Environment::new(Arch::X64));
624 buffer.write_u8(0xC3);
625 let mut code = buffer.finish().unwrap();
626 code.defined_symbols.push(("dangling".into(), u32::MAX));
627
628 let mut linker = Linker::new();
629 linker.add_section(FinalizedSection {
630 name: Cow::Borrowed(".text"),
631 align: 1,
632 code,
633 });
634
635 assert_eq!(
636 linker.link().err(),
637 Some(AsmError::Link(LinkError::UnboundSymbol {
638 name: "dangling".into(),
639 section: ".text".into(),
640 }))
641 );
642 }
643
644 #[test]
645 fn invalid_relocation_reports_its_section_and_target() {
646 let mut buffer = CodeBuffer::new(Environment::new(Arch::X64));
647 buffer.write_u32(0);
648 let mut code = buffer.finish().unwrap();
649 code.relocs.push(AsmReloc {
650 offset: 0,
651 kind: Reloc::Abs4,
652 addend: 0,
653 target: RelocTarget::Label(Label::from_id(7)),
654 });
655
656 let mut linker = Linker::new();
657 linker.add_section(FinalizedSection {
658 name: Cow::Borrowed(".bad"),
659 align: 1,
660 code,
661 });
662
663 assert_eq!(
664 linker.link().err(),
665 Some(AsmError::Link(LinkError::InvalidRelocation {
666 section: ".bad".into(),
667 offset: 0,
668 kind: Reloc::Abs4,
669 target: "label",
670 id: 7,
671 reason: "label id is outside the section",
672 }))
673 );
674 }
675
676 #[test]
677 fn out_of_section_relocation_is_rejected_before_linking() {
678 let mut buffer = CodeBuffer::new(Environment::new(Arch::X64));
679 let label = buffer.get_label();
680 buffer.bind_label(label);
681 buffer.write_u32(0);
682 let mut code = buffer.finish().unwrap();
683 code.relocs.push(AsmReloc {
684 offset: 1,
685 kind: Reloc::Abs4,
686 addend: 0,
687 target: RelocTarget::Label(label),
688 });
689
690 let mut linker = Linker::new();
691 linker.add_section(FinalizedSection {
692 name: Cow::Borrowed(".bad"),
693 align: 1,
694 code,
695 });
696
697 assert_eq!(
698 linker.link().err(),
699 Some(AsmError::Link(LinkError::InvalidRelocation {
700 section: ".bad".into(),
701 offset: 1,
702 kind: Reloc::Abs4,
703 target: "label",
704 id: label.id(),
705 reason: "patch range is outside the section",
706 }))
707 );
708 }
709
710 #[cfg(all(feature = "jit", target_arch = "x86_64"))]
711 #[test]
712 fn got_based_extern_call_across_modules() {
713 use crate::core::jit_allocator::JitAllocator;
714
715 let mut a = CodeBuffer::new(Environment::new(Arch::X64));
717 defined_label(&mut a, "callee");
718 a.write_u8(0xB8);
719 a.write_u32(42);
720 a.write_u8(0xC3);
721
722 let mut b = CodeBuffer::new(Environment::new(Arch::X64));
725 defined_label(&mut b, "main");
726 let callee = b.extern_sym("callee", RelocDistance::Far);
727 b.write_u8(0xFF);
728 b.write_u8(0x15);
729 b.add_reloc(Reloc::X86GOTPCRel4, RelocTarget::Sym(callee), -4);
730 b.write_u32(0);
731 b.write_u8(0xC3);
732
733 let mut linker = Linker::new();
734 linker.add_buffer(a.finish().unwrap());
735 linker.add_buffer(b.finish().unwrap());
736 let image = linker.link().unwrap();
737
738 let entry = image.defined_symbol_str("main").unwrap();
739 let mut jit = JitAllocator::new(Default::default());
740 let loaded = image
741 .allocate_resolved(&mut jit, |name| {
742 panic!("unexpected undefined symbol: {name}")
743 })
744 .unwrap();
745
746 assert_eq!(loaded.got_targets().len(), 1);
748 unsafe {
749 let got_entry = core::ptr::read_unaligned(loaded.got_rx() as *const usize);
750 assert_eq!(got_entry, loaded.rx() as usize);
751
752 let main: extern "C" fn() -> u32 =
753 core::mem::transmute(loaded.rx().add(entry as usize));
754 assert_eq!(main(), 42);
755 }
756 }
757}