use rustc_hash::{FxHashMap, FxHashSet};
use crate::{
dynamic::{FINI_SYMBOL, INIT_SYMBOL, LinkMode, exports_definition},
ehframe::{Piece, is_fde_offset, records},
elf::{
ObjectFile, Shdr64, SymbolTable,
constants::{SHF_ALLOC, SHF_EXECINSTR, SHF_LINK_ORDER},
},
error::Result,
linker::Context,
output::OutKind,
symbol::{DefSource, Definition, SymbolKind},
};
const INIT_SECTION: &[u8] = OutKind::Init.name().as_bytes();
const FINI_SECTION: &[u8] = OutKind::Fini.name().as_bytes();
const EXACT_ROOTS: [&[u8]; 3] = [INIT_SECTION, FINI_SECTION, b".jcr"];
const PREFIX_ROOTS: [&[u8]; 3] = [b".init_array", b".ctors", b".dtors"];
pub(crate) fn real_section(shndx: u16) -> Option<u16> {
use crate::elf::constants::{
SHN_ABS, SHN_COMMON, SHN_LORESERVE, SHN_UNDEF,
};
match shndx {
SHN_UNDEF | SHN_ABS | SHN_COMMON => None,
s if s >= SHN_LORESERVE => None,
s => Some(s),
}
}
fn is_root_section(obj: ObjectFile<'_>, shdr: &Shdr64) -> bool {
use crate::elf::constants::{
SHF_GNU_RETAIN, SHT_FINI_ARRAY, SHT_INIT_ARRAY, SHT_NOTE,
SHT_PREINIT_ARRAY,
};
let ty = shdr.sh_type.get();
if shdr.sh_flags.get() & SHF_GNU_RETAIN != 0
|| ty == SHT_INIT_ARRAY
|| ty == SHT_FINI_ARRAY
|| ty == SHT_PREINIT_ARRAY
|| ty == SHT_NOTE
{
return true;
}
EXACT_ROOTS.iter().any(|&n| obj.section_name_is(shdr, n))
|| PREFIX_ROOTS
.iter()
.any(|&p| obj.section_name_starts_with(shdr, p))
}
fn enqueue(
file: usize,
section: u16,
live: &mut FxHashSet<(usize, u16)>,
work: &mut Vec<(usize, u16)>,
) {
if live.insert((file, section)) {
work.push((file, section));
}
}
fn mark_definition(
def: &Definition,
live: &mut FxHashSet<(usize, u16)>,
work: &mut Vec<(usize, u16)>,
) {
if let DefSource::Section { index, .. } = def.source {
enqueue(def.file, index, live, work);
}
}
fn mark_named(
ctx: &Context<'_>,
name: &[u8],
live: &mut FxHashSet<(usize, u16)>,
work: &mut Vec<(usize, u16)>,
) {
let Some(id) = ctx.symbols.find(name) else {
return;
};
let Some(sym) = ctx.symbols.symbol(id) else {
return;
};
if let SymbolKind::Defined(def) = &sym.kind {
mark_definition(def, live, work);
}
}
fn collect_roots(
ctx: &Context<'_>,
entry: &[u8],
undefined: &[&[u8]],
mode: LinkMode,
live: &mut FxHashSet<(usize, u16)>,
work: &mut Vec<(usize, u16)>,
) {
for (file, input) in ctx.files.iter().enumerate() {
let Ok(obj) = input.object() else { continue };
for (i, shdr) in obj.sections().iter().enumerate() {
if shdr.sh_flags.get() & SHF_ALLOC == 0 {
continue;
}
let Ok(section) = u16::try_from(i) else {
continue;
};
if ctx.groups.is_discarded(file, section) {
continue;
}
if is_root_section(obj, shdr)
|| ctx.start_stop.run_of_section(file, section).is_some()
{
enqueue(file, section, live, work);
}
}
}
if let Some(out) = ctx.outputs.section(OutKind::EhFrame) {
for m in &out.members {
enqueue(m.file, m.section, live, work);
}
}
if !entry.is_empty() {
mark_named(ctx, entry, live, work);
}
for &name in undefined {
mark_named(ctx, name, live, work);
}
mark_named(ctx, INIT_SYMBOL, live, work);
mark_named(ctx, FINI_SYMBOL, live, work);
mark_exports(ctx, mode, live, work);
}
fn mark_exports(
ctx: &Context<'_>,
mode: LinkMode,
live: &mut FxHashSet<(usize, u16)>,
work: &mut Vec<(usize, u16)>,
) {
for (name, sym) in ctx.symbols.entries() {
if let SymbolKind::Defined(def) = &sym.kind
&& exports_definition(ctx, mode, sym.visibility, name)
{
mark_definition(def, live, work);
}
}
}
pub(crate) fn reloc_target(
ctx: &Context<'_>,
symtab: &SymbolTable<'_>,
file: usize,
sym_idx: u32,
) -> Option<(usize, u16)> {
use crate::elf::constants::STB_LOCAL;
let sym = symtab.syms.get(sym_idx as usize)?;
if sym.bind() == STB_LOCAL {
return real_section(sym.st_shndx.get()).map(|section| (file, section));
}
let name = crate::symbol::version_stem(symtab.name(sym));
let id = ctx.symbols.find(name)?;
let SymbolKind::Defined(def) = &ctx.symbols.symbol(id)?.kind else {
return None;
};
match def.source {
DefSource::Section { index, .. } => Some((def.file, index)),
DefSource::Absolute { .. } => None,
}
}
fn fde_target_travels_with_its_text(
ctx: &Context<'_>,
(file, section): (usize, u16),
) -> bool {
has_flag(ctx, (file, section), SHF_EXECINSTR)
|| ctx.groups.is_grouped(file, section)
|| has_flag(ctx, (file, section), SHF_LINK_ORDER)
}
fn has_flag(
ctx: &Context<'_>,
(file, section): (usize, u16),
flag: u64,
) -> bool {
ctx.files.get(file).is_some_and(|input| {
input.object().is_ok_and(|obj| {
obj.sections()
.get(usize::from(section))
.is_some_and(|s| s.sh_flags.get() & flag != 0)
})
})
}
fn eh_frame_records(
ctx: &Context<'_>,
file: usize,
section: u16,
pieces: &mut Vec<Piece>,
fde: &mut Vec<bool>,
) -> Result<bool> {
let Some(input) = ctx.files.get(file) else {
return Ok(false);
};
let obj = input.object()?;
let Some(shdr) = obj.sections().get(usize::from(section)) else {
return Ok(false);
};
if !crate::ehframe::is_eh_frame_name(obj.section_name(shdr)) {
return Ok(false);
}
records(obj.section_data(shdr)?, pieces, fde);
Ok(true)
}
fn propagate(
ctx: &Context<'_>,
live: &mut FxHashSet<(usize, u16)>,
work: &mut Vec<(usize, u16)>,
) -> Result<()> {
let dependents = link_order_map(ctx)?;
let mut pieces: Vec<Piece> = Vec::new();
let mut fde: Vec<bool> = Vec::new();
while let Some((file, section)) = work.pop() {
for &sibling in ctx.groups.group_members(file, section) {
enqueue(file, sibling, live, work);
}
if !dependents.is_empty()
&& let Some(deps) = dependents.get(&(file, section))
{
for &dep in deps {
enqueue(file, dep, live, work);
}
}
let Some(input) = ctx.files.get(file) else {
continue;
};
let Some(symtab) = input.symbol_table()? else {
continue;
};
let Some(entries) = input.relocations(section)? else {
continue;
};
let is_eh =
eh_frame_records(ctx, file, section, &mut pieces, &mut fde)?;
for r in entries {
let Some(target) = reloc_target(ctx, &symtab, file, r.sym()) else {
continue;
};
if is_eh
&& is_fde_offset(&pieces, &fde, r.r_offset.get())
&& fde_target_travels_with_its_text(ctx, target)
{
continue;
}
enqueue(target.0, target.1, live, work);
}
}
Ok(())
}
fn link_order_map(
ctx: &Context<'_>,
) -> Result<FxHashMap<(usize, u16), Vec<u16>>> {
let mut out: FxHashMap<(usize, u16), Vec<u16>> = FxHashMap::default();
for (file, input) in ctx.files.iter().enumerate() {
let obj = input.object()?;
for (index, shdr) in obj.sections().iter().enumerate() {
if shdr.sh_flags.get() & (SHF_LINK_ORDER | SHF_ALLOC)
!= SHF_LINK_ORDER | SHF_ALLOC
{
continue;
}
let Ok(section) = u16::try_from(index) else {
continue;
};
let Ok(target) = u16::try_from(shdr.sh_link.get()) else {
continue;
};
if target == 0 {
continue;
}
out.entry((file, target)).or_default().push(section);
}
}
Ok(out)
}
pub fn run(
ctx: &mut Context<'_>,
entry: &[u8],
undefined: &[&[u8]],
mode: LinkMode,
) -> Result<()> {
let mut live: FxHashSet<(usize, u16)> = FxHashSet::default();
let mut work: Vec<(usize, u16)> = Vec::new();
collect_roots(ctx, entry, undefined, mode, &mut live, &mut work);
propagate(ctx, &mut live, &mut work)?;
ctx.outputs.retain_live(&live);
Ok(())
}