use rayon::prelude::*;
use rustc_hash::FxHashSet;
use self::absolute::classify_absolute;
use crate::{
dynamic::LinkMode,
elf::{
Shdr64,
constants::{SHF_ALLOC, SHF_WRITE, STT_GNU_IFUNC},
},
error::{Error, Result},
layout::{CopySlot, GotKey, GotKind, GotOwner, Layout},
linker::{Context, DepAddr},
output::OutKind,
reloc::{
Target, relax_drops_got_target, relax_lead_target, relax_trail_target,
scan_target, spec_target,
x86_64::{
R_X86_64_GOTPC32_TLSDESC, R_X86_64_TLSDESC_CALL, R_X86_64_TLSGD,
R_X86_64_TLSLD,
},
},
symbol::{SymbolId, SymbolKind, exports_to_dynsym},
};
mod absolute;
pub(super) fn scan_relocations(
ctx: &Context<'_>,
target: Target,
mode: LinkMode,
sym_id: &[Vec<Option<SymbolId>>],
relax: bool,
layout: &mut Layout,
) -> Result<()> {
let items = scan_work_items(ctx);
let undef = UndefFlags::build(ctx, mode);
let per_item: Vec<ScanNeeds> = items
.par_iter()
.map(|item| {
scan_work_item(ctx, target, mode, sym_id, &undef, relax, item)
})
.collect::<Result<Vec<_>>>()?;
let mut totals = ScanTotals::default();
for s in per_item {
totals.merge(s);
}
totals.freeze(layout);
Ok(())
}
#[derive(Default)]
struct ScanTotals {
got: Vec<GotKey>,
seen_got: FxHashSet<GotKey>,
plt: Vec<GotKey>,
seen_plt: FxHashSet<GotKey>,
copy_slots: Vec<CopySlot>,
seen_copy: FxHashSet<DepAddr>,
canonical_plt: FxHashSet<SymbolId>,
ifunc: Vec<SymbolId>,
seen_ifunc: FxHashSet<SymbolId>,
referenced: FxHashSet<SymbolId>,
has_absolute_refs: bool,
needs_sym_sizes: bool,
abs_candidates: Vec<Vec<u16>>,
}
impl ScanTotals {
fn merge(&mut self, s: ScanNeeds) {
for key in s.got {
if self.seen_got.insert(key) {
self.got.push(key);
}
}
for key in s.plt {
if self.seen_plt.insert(key) {
self.plt.push(key);
}
}
for slot in s.copy {
if self.seen_copy.insert(slot.origin) {
self.copy_slots.push(slot);
}
}
self.canonical_plt.extend(s.canonical_plt);
for id in s.ifunc {
if self.seen_ifunc.insert(id) {
self.ifunc.push(id);
}
}
self.referenced.extend(s.referenced);
self.has_absolute_refs |= s.has_abs;
self.needs_sym_sizes |= s.needs_sizes;
self.abs_candidates.push(s.abs_sections);
}
fn freeze(self, layout: &mut Layout) {
let mut slot = 0u64;
for key in &self.got {
layout
.got_index
.insert(*key, u32::try_from(slot).unwrap_or(u32::MAX));
slot = slot.saturating_add(key.kind.slots());
}
layout.got_values = vec![0u64; usize::try_from(slot).unwrap_or(0)];
layout.got_keys = self.got;
for (i, key) in self.plt.iter().enumerate() {
layout
.plt_index
.insert(*key, u32::try_from(i).unwrap_or(u32::MAX));
}
layout.plt_keys = self.plt;
layout.copy_slots = self.copy_slots;
layout.canonical_plt = self.canonical_plt;
layout.ifunc = self.ifunc;
layout.referenced = self.referenced;
layout.has_absolute_refs = self.has_absolute_refs;
layout.needs_sym_sizes = self.needs_sym_sizes;
layout.abs_candidates = self.abs_candidates;
for row in &mut layout.abs_candidates {
row.sort_unstable();
}
}
}
struct UndefFlags {
bits: Vec<u8>,
tls_helper: Option<SymbolId>,
}
impl UndefFlags {
const UNDEF: u8 = 1;
const WEAK: u8 = 2;
const PRIVATE: u8 = 4;
const PREEMPTIBLE: u8 = 8;
const IMPORTABLE: u8 = 16;
fn build(ctx: &Context<'_>, mode: LinkMode) -> Self {
let shared = mode == LinkMode::Shared;
let mut bits = vec![0u8; ctx.symbols.len()];
for (slot, id) in bits.iter_mut().zip(ctx.symbols.ids()) {
let Some(sym) = ctx.symbols.symbol(id) else {
continue;
};
if sym.is_preemptible(shared) {
*slot |= Self::PREEMPTIBLE;
}
if let SymbolKind::Undefined { weak } = sym.kind {
*slot |= Self::UNDEF;
if weak {
*slot |= Self::WEAK;
}
if !exports_to_dynsym(sym.visibility) {
*slot |= Self::PRIVATE;
}
if ctx.dep_exports.contains(ctx.symbols.name(id)) {
*slot |= Self::IMPORTABLE;
}
}
}
Self {
bits,
tls_helper: ctx.symbols.find(TLS_GET_ADDR),
}
}
fn is_tls_helper(&self, id: Option<SymbolId>) -> bool {
id.is_some() && id == self.tls_helper
}
fn is_undefined(&self, id: Option<SymbolId>) -> bool {
self.flags(id) & Self::UNDEF != 0
}
fn is_strong_undefined(&self, id: Option<SymbolId>) -> bool {
self.flags(id) & (Self::UNDEF | Self::WEAK) == Self::UNDEF
}
fn is_preemptible(&self, id: Option<SymbolId>) -> bool {
self.flags(id) & Self::PREEMPTIBLE != 0
}
fn is_private(&self, id: Option<SymbolId>) -> bool {
self.flags(id) & Self::PRIVATE != 0
}
fn is_unresolvable(&self, mode: LinkMode, id: Option<SymbolId>) -> bool {
if !self.is_strong_undefined(id) {
return false;
}
match mode {
LinkMode::Static => true,
LinkMode::Shared => self.is_private(id),
LinkMode::DynExec => self.is_private(id) || !self.is_importable(id),
}
}
fn is_importable(&self, id: Option<SymbolId>) -> bool {
self.flags(id) & Self::IMPORTABLE != 0
}
fn flags(&self, id: Option<SymbolId>) -> u8 {
id.and_then(|i| self.bits.get(i.0)).copied().unwrap_or(0)
}
}
struct ScanItem {
file: usize,
sections: Vec<u16>,
}
struct ScanNeeds {
got: Vec<GotKey>,
plt: Vec<GotKey>,
copy: Vec<CopySlot>,
canonical_plt: Vec<SymbolId>,
ifunc: Vec<SymbolId>,
referenced: Vec<SymbolId>,
seen_referenced: FxHashSet<SymbolId>,
has_abs: bool,
needs_sizes: bool,
abs_sections: Vec<u16>,
}
fn scan_work_items(ctx: &Context<'_>) -> Vec<ScanItem> {
let mut by_file: Vec<Vec<u16>> = vec![Vec::new(); ctx.files.len()];
for section in ctx.outputs.iter() {
if section.kind == OutKind::Bss {
continue;
}
for m in §ion.members {
if let Some(bucket) = by_file.get_mut(m.file) {
bucket.push(m.section);
}
}
}
by_file
.into_iter()
.enumerate()
.map(|(file, sections)| ScanItem { file, sections })
.collect()
}
fn scan_work_item(
ctx: &Context<'_>,
target: Target,
mode: LinkMode,
sym_id: &[Vec<Option<SymbolId>>],
undef: &UndefFlags,
relax: bool,
item: &ScanItem,
) -> Result<ScanNeeds> {
let mut needs = ScanNeeds {
got: Vec::new(),
plt: Vec::new(),
copy: Vec::new(),
canonical_plt: Vec::new(),
ifunc: Vec::new(),
referenced: Vec::new(),
seen_referenced: FxHashSet::default(),
has_abs: false,
needs_sizes: false,
abs_sections: Vec::new(),
};
let Some(input) = ctx.files.get(item.file) else {
return Ok(needs);
};
if item.sections.is_empty() {
return Ok(needs);
}
let obj = input.object()?;
let Some(symtab) = input.symbol_table()? else {
return Ok(needs);
};
let sections = obj.sections();
let abs64 = target.dyn_relocs().abs64;
let sym_id_row =
sym_id.get(item.file).map(Vec::as_slice).unwrap_or_default();
let mut seen_got: FxHashSet<GotKey> = FxHashSet::default();
let mut seen_plt: FxHashSet<GotKey> = FxHashSet::default();
let mut seen_copy: FxHashSet<SymbolId> = FxHashSet::default();
let mut seen_canonical: FxHashSet<SymbolId> = FxHashSet::default();
let mut seen_ifunc: FxHashSet<SymbolId> = FxHashSet::default();
for §ion in &item.sections {
let Some(entries) = input.relocations(section)? else {
continue;
};
let shdr = sections.get(usize::from(section));
let flags = shdr.map_or(0, |s| s.sh_flags.get());
let writable = flags & SHF_ALLOC != 0 && flags & SHF_WRITE != 0;
let site = RelocSite {
symtab: &symtab,
sections,
sym_id_row,
writable,
relax,
data: shdr
.and_then(|s| obj.section_data(s).ok())
.unwrap_or_default(),
};
let mut work = ScanWork {
file: item.file,
got: &mut needs.got,
plt: &mut needs.plt,
copy: &mut needs.copy,
canonical_plt: &mut needs.canonical_plt,
seen_got: &mut seen_got,
seen_plt: &mut seen_plt,
seen_copy: &mut seen_copy,
seen_canonical: &mut seen_canonical,
ifunc: &mut needs.ifunc,
seen_ifunc: &mut seen_ifunc,
referenced: &mut needs.referenced,
seen_referenced: &mut needs.seen_referenced,
has_abs: &mut needs.has_abs,
needs_sizes: &mut needs.needs_sizes,
};
let mut has_abs64 = false;
for (i, r) in entries.iter().enumerate() {
has_abs64 |= r.r_type() == abs64;
let pair = RelocPair {
r,
prev: i.checked_sub(1).and_then(|k| entries.get(k)),
};
classify_reloc(ctx, target, mode, &site, undef, pair, &mut work)?;
}
if has_abs64 {
needs.abs_sections.push(section);
}
}
Ok(needs)
}
fn relaxes_away_got(
ctx: &Context<'_>,
target: Target,
mode: LinkMode,
site: &RelocSite<'_>,
id_opt: Option<SymbolId>,
r: &crate::elf::Rela64,
) -> bool {
if !site.relax {
return false;
}
let Some(id) = id_opt else {
return false;
};
let Some(sym) = ctx.symbols.symbol(id) else {
return false;
};
if sym.is_preemptible(mode == LinkMode::Shared) || sym.is_absolute_value() {
return false;
}
let lead = relax_lead_target(target, r.r_type());
let at = usize::try_from(r.r_offset.get()).unwrap_or(usize::MAX);
let Some(start) = at.checked_sub(lead) else {
return false;
};
let Some(window) = site.data.get(start..at) else {
return false;
};
relax_drops_got_target(target, r.r_type(), r.r_addend.get(), window)
}
struct ScanWork<'a> {
file: usize,
got: &'a mut Vec<GotKey>,
plt: &'a mut Vec<GotKey>,
copy: &'a mut Vec<CopySlot>,
canonical_plt: &'a mut Vec<SymbolId>,
seen_got: &'a mut FxHashSet<GotKey>,
seen_plt: &'a mut FxHashSet<GotKey>,
seen_copy: &'a mut FxHashSet<SymbolId>,
seen_canonical: &'a mut FxHashSet<SymbolId>,
ifunc: &'a mut Vec<SymbolId>,
seen_ifunc: &'a mut FxHashSet<SymbolId>,
referenced: &'a mut Vec<SymbolId>,
seen_referenced: &'a mut FxHashSet<SymbolId>,
has_abs: &'a mut bool,
needs_sizes: &'a mut bool,
}
struct RelocSite<'a> {
symtab: &'a crate::elf::SymbolTable<'a>,
sections: &'a [Shdr64],
sym_id_row: &'a [Option<SymbolId>],
writable: bool,
relax: bool,
data: &'a [u8],
}
#[derive(Copy, Clone)]
struct RelocPair<'a> {
r: &'a crate::elf::Rela64,
prev: Option<&'a crate::elf::Rela64>,
}
fn classify_reloc(
ctx: &Context<'_>,
target: Target,
mode: LinkMode,
site: &RelocSite<'_>,
undef: &UndefFlags,
pair: RelocPair<'_>,
work: &mut ScanWork<'_>,
) -> Result<()> {
let RelocPair { r, prev } = pair;
let symtab = site.symtab;
let sym_id_row = site.sym_id_row;
let needs = scan_target(target, r.r_type())?;
*work.needs_sizes |= needs.size;
let sym_idx = r.sym();
let id_opt = cached_global_id(sym_id_row, sym_idx);
if is_lowered_tls_call(target, mode, undef, id_opt, needs, r, prev) {
return Ok(());
}
if let Some(id) = id_opt
&& work.seen_referenced.insert(id)
{
work.referenced.push(id);
}
let owner = GotOwner::of(id_opt, work.file, sym_idx);
if needs.got && !relaxes_away_got(ctx, target, mode, site, id_opt, r) {
push_got(work, GotKey::new(GotKind::Addr, owner));
}
if needs.tls_got {
if mode == LinkMode::Shared && id_opt.is_none() {
return Err(unresolvable_tls(
symtab,
sym_idx,
"an initial-exec reference to a thread-local a shared object \
does not export has no name for the loader to resolve",
));
}
if mode == LinkMode::Static && undef.is_strong_undefined(id_opt) {
return Err(unresolvable_tls(symtab, sym_idx, NO_LOADER));
}
push_got(work, GotKey::new(GotKind::TlsOffset, owner));
}
if is_local_dynamic(target, r.r_type()) {
if mode == LinkMode::Shared {
push_got(work, GotKey::MODULE);
}
return Ok(());
}
if is_tls_desc(target, r.r_type()) {
if mode == LinkMode::Shared {
return Err(unresolvable_tls(symtab, sym_idx, NO_TLSDESC));
}
if r.r_type() == R_X86_64_GOTPC32_TLSDESC && undef.is_undefined(id_opt)
{
if mode == LinkMode::Static && undef.is_strong_undefined(id_opt) {
return Err(unresolvable_tls(symtab, sym_idx, NO_LOADER));
}
push_got(work, GotKey::new(GotKind::TlsOffset, owner));
}
return Ok(());
}
if is_general_dynamic(target, r.r_type()) {
if mode == LinkMode::Shared {
push_got(work, GotKey::new(GotKind::TlsModule, owner));
} else if undef.is_undefined(id_opt) {
if mode == LinkMode::Static && undef.is_strong_undefined(id_opt) {
return Err(unresolvable_tls(symtab, sym_idx, NO_LOADER));
}
push_got(work, GotKey::new(GotKind::TlsOffset, owner));
}
return Ok(());
}
if let Some(id) = id_opt.filter(|&id| is_ifunc(ctx, id)) {
push_plt(work, GotKey::addr(id));
if work.seen_ifunc.insert(id) {
work.ifunc.push(id);
}
return Ok(());
}
if needs.plt
&& undef.is_preemptible(id_opt)
&& !undef.is_private(id_opt)
&& mode != LinkMode::Static
{
push_plt(work, GotKey::new(GotKind::Addr, owner));
}
if mode == LinkMode::DynExec && !needs.got && !needs.plt {
classify_absolute(ctx, target, site, undef, r, work)?;
}
if undef.is_unresolvable(mode, id_opt) {
return Err(undefined_reference(symtab, sym_idx));
}
Ok(())
}
fn is_ifunc(ctx: &Context<'_>, id: SymbolId) -> bool {
ctx.symbols.symbol(id).is_some_and(|sym| {
matches!(&sym.kind, SymbolKind::Defined(def)
if def.sym_type == STT_GNU_IFUNC)
})
}
fn is_general_dynamic(target: Target, r_type: u32) -> bool {
target == Target::X86_64 && r_type == R_X86_64_TLSGD
}
fn is_tls_desc(target: Target, r_type: u32) -> bool {
target == Target::X86_64
&& matches!(r_type, R_X86_64_GOTPC32_TLSDESC | R_X86_64_TLSDESC_CALL)
}
fn is_local_dynamic(target: Target, r_type: u32) -> bool {
target == Target::X86_64 && r_type == R_X86_64_TLSLD
}
fn push_got(work: &mut ScanWork<'_>, key: GotKey) {
if work.seen_got.insert(key) {
work.got.push(key);
}
}
fn push_plt(work: &mut ScanWork<'_>, key: GotKey) {
if work.seen_plt.insert(key) {
work.plt.push(key);
}
}
fn symbol_name<'data>(
symtab: &crate::elf::SymbolTable<'data>,
sym_idx: u32,
) -> &'data [u8] {
symtab
.syms
.get(sym_idx as usize)
.map_or(&[] as &[u8], |sym| symtab.name(sym))
}
fn unresolvable_tls(
symtab: &crate::elf::SymbolTable<'_>,
sym_idx: u32,
reason: &'static str,
) -> Error {
let name = symbol_name(symtab, sym_idx);
Error::unresolvable_tls(String::from_utf8_lossy(name).into_owned(), reason)
}
const NO_LOADER: &str = "it is defined by a shared object, and a static link has no loader to \
place it";
const NO_TLSDESC: &str = "a shared object's TLS descriptors are filled by the loader through \
R_X86_64_TLSDESC relocations this linker does not emit; rebuild the \
input with -mtls-dialect=gnu";
const TLS_GET_ADDR: &[u8] = b"__tls_get_addr";
fn is_lowered_tls_call(
target: Target,
mode: LinkMode,
undef: &UndefFlags,
id: Option<SymbolId>,
needs: crate::reloc::Needs,
r: &crate::elf::Rela64,
prev: Option<&crate::elf::Rela64>,
) -> bool {
if mode == LinkMode::Shared
|| !(needs.plt || needs.got)
|| !undef.is_tls_helper(id)
{
return false;
}
prev.is_some_and(|p| consumes(target, p, r.r_offset.get()))
}
fn consumes(target: Target, p: &crate::elf::Rela64, at: u64) -> bool {
let trail = relax_trail_target(target, p.r_type(), &[], &[]);
if trail == 0 {
return false;
}
let Ok(spec) = spec_target(target, p.r_type()) else {
return false;
};
let slot_end = p.r_offset.get().wrapping_add(spec.write.width() as u64);
(slot_end..slot_end.wrapping_add(trail as u64)).contains(&at)
}
fn undefined_reference(
symtab: &crate::elf::SymbolTable<'_>,
sym_idx: u32,
) -> Error {
let name = symbol_name(symtab, sym_idx);
Error::UndefinedReference(String::from_utf8_lossy(name).into_owned())
}
fn cached_global_id(
sym_id_row: &[Option<SymbolId>],
sym_idx: u32,
) -> Option<SymbolId> {
sym_id_row.get(sym_idx as usize).copied().flatten()
}