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 Linker {
103 pub fn new() -> Self {
104 Self {
105 sections: Vec::new(),
106 }
107 }
108
109 pub fn add_section(&mut self, section: FinalizedSection) {
111 self.sections.push(section);
112 }
113
114 pub fn add_buffer(&mut self, code: CodeBufferFinalized) {
117 self.sections.push(FinalizedSection {
118 name: Cow::Borrowed(".text"),
119 align: code.alignment,
120 code,
121 });
122 }
123
124 pub fn link(self) -> Result<CodeBufferFinalized, AsmError> {
129 if self.sections.is_empty() {
130 return Err(AsmError::NoCodeGenerated);
131 }
132 let arch = self.sections[0].code.patch_catalog.arch();
133 if let Some(section) = self
134 .sections
135 .iter()
136 .find(|section| section.code.patch_catalog.arch() != arch)
137 {
138 return Err(AsmError::Link(LinkError::IncompatibleArch {
139 first_section: self.sections[0].name.clone(),
140 section: section.name.clone(),
141 }));
142 }
143
144 let mut bases = Vec::with_capacity(self.sections.len());
146 let mut offset: CodeOffset = 0;
147 let mut alignment = 1u32;
148 for section in &self.sections {
149 offset = align_up(offset, section.align)?;
150 bases.push(offset);
151 let section_size =
152 CodeOffset::try_from(section.code.data.len()).map_err(|_| AsmError::TooLarge)?;
153 offset = offset.checked_add(section_size).ok_or(AsmError::TooLarge)?;
154 alignment = alignment.max(section.align).max(section.code.alignment);
155 }
156 let total_size = offset;
157
158 let mut defined: Vec<(ExternalName, CodeOffset, Cow<'static, str>)> = Vec::new();
160 for (section, &base) in self.sections.iter().zip(&bases) {
161 for (name, local_offset) in §ion.code.defined_symbols {
162 let local_offset = *local_offset;
163 if local_offset == u32::MAX {
164 return Err(AsmError::Link(LinkError::UnboundSymbol {
165 name: name.clone(),
166 section: section.name.clone(),
167 }));
168 }
169 if let Some((_, _, first_section)) = defined
170 .iter()
171 .find(|(defined_name, _, _)| defined_name == name)
172 {
173 return Err(AsmError::Link(LinkError::DuplicateSymbol {
174 name: name.clone(),
175 first_section: first_section.clone(),
176 section: section.name.clone(),
177 }));
178 }
179 defined.push((
180 name.clone(),
181 base.checked_add(local_offset).ok_or(AsmError::TooLarge)?,
182 section.name.clone(),
183 ));
184 }
185 }
186
187 let mut label_offsets: SmallVec<[CodeOffset; 16]> = SmallVec::new();
192 for (section, &base) in self.sections.iter().zip(&bases) {
193 for &local_offset in §ion.code.label_offsets {
194 label_offsets.push(if local_offset == u32::MAX {
195 u32::MAX
196 } else {
197 base.checked_add(local_offset).ok_or(AsmError::TooLarge)?
198 });
199 }
200 }
201 let defined_label_base =
202 u32::try_from(label_offsets.len()).map_err(|_| AsmError::TooLarge)?;
203 for (_, global_offset, _) in &defined {
204 label_offsets.push(*global_offset);
205 }
206
207 let mut symbols: SmallVec<[SymData; 16]> = SmallVec::new();
210 let mut sym_maps: Vec<SmallVec<[u32; 16]>> = Vec::with_capacity(self.sections.len());
211 for section in &self.sections {
212 let mut map: SmallVec<[u32; 16]> = SmallVec::new();
213 for sym in §ion.code.symbols {
214 let id = match symbols.iter().position(|merged| merged.name == sym.name) {
215 Some(index) => index as u32,
216 None => {
217 symbols.push(sym.clone());
218 (symbols.len() - 1) as u32
219 }
220 };
221 map.push(id);
222 }
223 sym_maps.push(map);
224 }
225
226 let mut data: SmallVec<[u8; 1024]> = SmallVec::new();
228 data.resize(total_size as usize, 0);
229 let mut relocs: SmallVec<[AsmReloc; 16]> = SmallVec::new();
230 let mut label_base: u32 = 0;
231 for (section_index, (section, &base)) in self.sections.iter().zip(&bases).enumerate() {
232 let start = base as usize;
233 let end = start
234 .checked_add(section.code.data.len())
235 .ok_or(AsmError::TooLarge)?;
236 data.get_mut(start..end)
237 .ok_or(AsmError::InvalidState)?
238 .copy_from_slice(§ion.code.data);
239
240 for reloc in §ion.code.relocs {
241 let (target, target_id) = match &reloc.target {
242 RelocTarget::Label(label) => ("label", label.id()),
243 RelocTarget::Sym(sym) => ("symbol", sym.id()),
244 };
245 let invalid_reloc = |reason| {
246 AsmError::Link(LinkError::InvalidRelocation {
247 section: section.name.clone(),
248 offset: reloc.offset,
249 kind: reloc.kind,
250 target,
251 id: target_id,
252 reason,
253 })
254 };
255 let patch_size = relocation_patch_size(reloc.kind)
256 .map_err(|_| invalid_reloc("unsupported relocation kind"))?;
257 let patch_end = (reloc.offset as usize)
258 .checked_add(patch_size)
259 .ok_or_else(|| invalid_reloc("patch range overflows"))?;
260 if patch_end > section.code.data.len() {
261 return Err(invalid_reloc("patch range is outside the section"));
262 }
263 let target = match &reloc.target {
264 RelocTarget::Label(label) => {
265 if section
266 .code
267 .label_offsets
268 .get(label.id() as usize)
269 .is_none()
270 {
271 return Err(invalid_reloc("label id is outside the section"));
272 }
273 RelocTarget::Label(Label::from_id(
274 label_base
275 .checked_add(label.id())
276 .ok_or(AsmError::TooLarge)?,
277 ))
278 }
279 RelocTarget::Sym(sym) => {
280 let name = §ion
281 .code
282 .symbols
283 .get(sym.id() as usize)
284 .ok_or_else(|| invalid_reloc("symbol id is outside the section"))?
285 .name;
286 let defined_index =
287 defined.iter().position(|(defined_name, _, _)| defined_name == name);
288 match defined_index {
289 Some(index) => RelocTarget::Label(Label::from_id(
291 defined_label_base + index as u32,
292 )),
293 None => RelocTarget::Sym(Sym::from_id(
295 *sym_maps[section_index].get(sym.id() as usize).ok_or_else(
296 || invalid_reloc("symbol id is outside the section"),
297 )?,
298 )),
299 }
300 }
301 };
302 relocs.push(AsmReloc {
303 offset: base.checked_add(reloc.offset).ok_or(AsmError::TooLarge)?,
304 kind: reloc.kind,
305 addend: reloc.addend,
306 target,
307 });
308 }
309
310 label_base = label_base
311 .checked_add(
312 u32::try_from(section.code.label_offsets.len())
313 .map_err(|_| AsmError::TooLarge)?,
314 )
315 .ok_or(AsmError::TooLarge)?;
316 }
317
318 let mut blocks: SmallVec<[PatchBlock; 4]> = SmallVec::new();
320 let mut sites: SmallVec<[PatchSite; 8]> = SmallVec::new();
321 for (section, &base) in self.sections.iter().zip(&bases) {
322 let catalog = §ion.code.patch_catalog;
323 for block in catalog.blocks() {
324 blocks.push(PatchBlock {
325 offset: base.checked_add(block.offset).ok_or(AsmError::TooLarge)?,
326 ..*block
327 });
328 }
329 for site in catalog.sites() {
330 sites.push(PatchSite {
331 offset: base.checked_add(site.offset).ok_or(AsmError::TooLarge)?,
332 current_target: base
333 .checked_add(site.current_target)
334 .ok_or(AsmError::TooLarge)?,
335 ..*site
336 });
337 }
338 }
339
340 Ok(CodeBufferFinalized {
341 data,
342 relocs,
343 symbols,
344 label_offsets,
345 defined_symbols: defined
346 .into_iter()
347 .map(|(name, offset, _)| (name, offset))
348 .collect(),
349 alignment,
350 patch_catalog: PatchCatalog::with_parts(arch, blocks, sites),
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}
370
371#[cfg(test)]
372mod tests {
373 use super::*;
374 use crate::core::arch_traits::Arch;
375 use crate::core::buffer::{CodeBuffer, Reloc, RelocDistance};
376 use crate::core::section::Section;
377 use crate::core::target::Environment;
378
379 fn defined_label(buf: &mut CodeBuffer, name: &'static str) -> Label {
380 let label = buf.get_label();
381 buf.bind_label(label);
382 buf.bind_symbol(name, label);
383 label
384 }
385
386 #[test]
387 fn section_layout_respects_alignment() {
388 let mut text = Section::new(".text", 16).unwrap();
389 let text_entry = defined_label(text.buffer_mut(), "entry");
390 text.buffer_mut().write_u8(0xC3);
391 assert_eq!(text.buffer().label_offset(text_entry), 0);
392
393 let mut data = Section::new(".data", 16).unwrap();
394 let data_sym = defined_label(data.buffer_mut(), "data_sym");
395 data.buffer_mut().write_u8(0xAA);
396 assert_eq!(data.buffer().label_offset(data_sym), 0);
397
398 let mut linker = Linker::new();
399 linker.add_section(text.finish().unwrap());
400 linker.add_section(data.finish().unwrap());
401
402 let image = linker.link().unwrap();
403 assert_eq!(image.total_size(), 17);
405 assert_eq!(image.alignment(), 32);
408 assert_eq!(image.defined_symbol_str("entry"), Some(0));
409 assert_eq!(image.defined_symbol_str("data_sym"), Some(16));
410 assert_eq!(image.data()[0], 0xC3);
411 assert_eq!(image.data()[16], 0xAA);
412 }
413
414 #[test]
415 fn cross_module_symbol_resolution() {
416 let mut a = CodeBuffer::new(Environment::new(Arch::X64));
418 defined_label(&mut a, "callee");
419 a.write_u8(0xC3); let mut b = CodeBuffer::new(Environment::new(Arch::X64));
424 let callee = b.extern_sym("callee", RelocDistance::Far);
425 let missing = b.extern_sym("missing", RelocDistance::Far);
426 b.add_reloc(Reloc::Abs8, RelocTarget::Sym(callee), 0);
427 b.write_u64(0);
428 b.add_reloc(Reloc::Abs8, RelocTarget::Sym(missing), 0);
429 b.write_u64(0);
430
431 let mut linker = Linker::new();
432 linker.add_buffer(a.finish().unwrap());
433 linker.add_buffer(b.finish().unwrap());
434
435 let image = linker.link().unwrap();
436 assert_eq!(image.defined_symbol_str("callee"), Some(0));
437 assert_eq!(image.relocs().len(), 2);
438
439 match &image.relocs()[0].target {
441 RelocTarget::Label(label) => {
442 assert_eq!(image.label_offsets[label.id() as usize], 0);
443 }
444 target => panic!("expected label target, got {target:?}"),
445 }
446 match &image.relocs()[1].target {
449 RelocTarget::Sym(sym) => {
450 assert_eq!(
451 image.symbol_name(*sym),
452 Some(&crate::core::buffer::ExternalName::Symbol("missing".into()))
453 );
454 }
455 target => panic!("expected symbol target, got {target:?}"),
456 }
457 }
458
459 #[test]
460 fn label_relocs_are_rebased_to_the_section_base() {
461 let mut a = CodeBuffer::new(Environment::new(Arch::X64));
464 a.write_u64(0);
465
466 let mut b = CodeBuffer::new(Environment::new(Arch::X64));
467 let target = b.get_label();
468 b.add_reloc(Reloc::Abs8, RelocTarget::Label(target), 0);
469 b.write_u64(0);
470 b.bind_label(target);
471
472 let mut linker = Linker::new();
473 linker.add_buffer(a.finish().unwrap());
474 linker.add_buffer(b.finish().unwrap());
475
476 let image = linker.link().unwrap();
477 match &image.relocs()[0].target {
478 RelocTarget::Label(label) => {
479 assert_eq!(image.label_offsets[label.id() as usize], 32 + 8);
483 }
484 target => panic!("expected label target, got {target:?}"),
485 }
486 }
487
488 #[test]
489 fn cross_module_user_symbol_resolution() {
490 const FUNC: u32 = 0;
491 let mut a = CodeBuffer::new(Environment::new(Arch::X64));
493 let label = a.get_label();
494 a.bind_label(label);
495 a.bind_symbol(ExternalName::user(FUNC, 1), label);
496 a.write_u8(0xC3);
497
498 let mut b = CodeBuffer::new(Environment::new(Arch::X64));
500 let callee = b.extern_user(FUNC, 1, RelocDistance::Far);
501 let missing = b.extern_user(FUNC, 2, RelocDistance::Far);
502 b.add_reloc(Reloc::Abs8, RelocTarget::Sym(callee), 0);
503 b.write_u64(0);
504 b.add_reloc(Reloc::Abs8, RelocTarget::Sym(missing), 0);
505 b.write_u64(0);
506
507 let mut linker = Linker::new();
508 linker.add_buffer(a.finish().unwrap());
509 linker.add_buffer(b.finish().unwrap());
510
511 let image = linker.link().unwrap();
512 assert_eq!(
513 image.defined_symbol_offset(&ExternalName::user(FUNC, 1)),
514 Some(0)
515 );
516 assert_eq!(image.relocs().len(), 2);
517
518 match &image.relocs()[0].target {
519 RelocTarget::Label(label) => {
520 assert_eq!(image.label_offsets[label.id() as usize], 0);
521 }
522 target => panic!("expected label target, got {target:?}"),
523 }
524 match &image.relocs()[1].target {
525 RelocTarget::Sym(sym) => {
526 assert_eq!(
527 image.symbol_name(*sym),
528 Some(&ExternalName::user(FUNC, 2))
529 );
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}