use std::hash::{Hash, Hasher};
use rustc_hash::{FxHashMap, FxHashSet, FxHasher};
use crate::{
dynamic::LinkMode,
elf::{Shdr64, constants::SHF_ALLOC},
error::Result,
gc::real_section,
linker::Context,
output::OutKind,
reloc::{RelExpr, Target, spec_target},
symbol::{DefSource, SymbolId, SymbolKind},
util::is_c_identifier,
};
#[derive(Clone, Copy, PartialEq, Eq, Debug)]
pub enum IcfMode {
None,
All,
Safe,
}
impl IcfMode {
pub const fn is_active(self) -> bool {
!matches!(self, Self::None)
}
}
#[derive(Default)]
pub struct FoldMap {
by: FxHashMap<(usize, u16), (usize, u16)>,
rev: FxHashMap<(usize, u16), Vec<(usize, u16)>>,
}
impl FoldMap {
pub fn alias(
&mut self,
folded: (usize, u16),
representative: (usize, u16),
) {
let target = self.resolve(representative);
self.record(folded, target);
self.collapse_onto(folded);
}
fn record(&mut self, folded: (usize, u16), target: (usize, u16)) {
self.by.insert(folded, target);
self.rev.entry(target).or_default().push(folded);
}
fn resolve(&self, section: (usize, u16)) -> (usize, u16) {
let mut at = section;
for _ in 0..self.by.len() {
match self.by.get(&at) {
Some(&next) if next != at => at = next,
_ => break,
}
}
at
}
fn collapse_onto(&mut self, folded: (usize, u16)) {
let Some(&target) = self.by.get(&folded) else {
return;
};
let Some(sources) = self.rev.remove(&folded) else {
return;
};
for source in sources {
if self.by.get(&source) == Some(&folded) {
self.record(source, target);
}
}
}
pub fn is_folded(&self, section: (usize, u16)) -> bool {
self.by.contains_key(§ion)
}
pub fn iter(
&self,
) -> impl Iterator<Item = ((usize, u16), (usize, u16))> + '_ {
self.by.iter().map(|(&k, &v)| (k, v))
}
}
pub fn run(ctx: &mut Context<'_>, mode: IcfMode, link: LinkMode) -> Result<()> {
if !mode.is_active() {
return Ok(());
}
let folds = compute(ctx, mode, link)?;
if folds.is_empty() {
return Ok(());
}
ctx.outputs.absorb_alignments(|file, section| {
folds.get(&(file, section)).copied()
});
let folded: FxHashSet<(usize, u16)> = folds.keys().copied().collect();
ctx.outputs.drop_members(&folded);
for (&folded, &rep) in &folds {
ctx.folding.alias(folded, rep);
}
Ok(())
}
struct Sig<'a> {
file: usize,
section: u16,
out: OutKind,
flags: u64,
content: &'a [u8],
relocs: Vec<RelocSig>,
}
struct RelocSig {
offset: u64,
r_type: u32,
kind: TargetKind,
}
#[derive(Clone, Copy, Eq, PartialEq)]
enum TargetKind {
Sec { target: (usize, u16), val: u64 },
Abs(u64),
Ext { id: SymbolId, val: u64 },
LocalExt { at: (usize, u32), val: u64 },
}
fn compute(
ctx: &Context<'_>,
mode: IcfMode,
link: LinkMode,
) -> Result<FxHashMap<(usize, u16), (usize, u16)>> {
let target = crate::linker::derive_target(ctx)?;
let shared = link == LinkMode::Shared;
let rule = Eligibility {
mode,
lsda: crate::ehframe::sections_with_lsda(ctx)?,
address_taken: if mode == IcfMode::Safe {
scan_address_taken(ctx, target, link)?
} else {
FxHashSet::default()
},
};
let mut class: FxHashMap<(usize, u16), u64> = FxHashMap::default();
let mut sigs = collect_sigs(ctx, shared, &rule, &mut class)?;
if sigs.len() < 2 {
return Ok(FxHashMap::default());
}
propagate_classes(&sigs, &mut class);
segregate_to_fixpoint(&mut sigs, &mut class);
Ok(build_folds(&sigs, &class))
}
fn collect_sigs<'a>(
ctx: &'a Context<'_>,
shared: bool,
rule: &Eligibility,
class: &mut FxHashMap<(usize, u16), u64>,
) -> Result<Vec<Sig<'a>>> {
let mut next_unique = 1u64;
let mut sigs = Vec::new();
for out in ctx.outputs.iter() {
for m in &out.members {
let key = (m.file, m.section);
let Some(shdr) = section_shdr(ctx, m.file, m.section)? else {
set_unique(class, key, &mut next_unique);
continue;
};
let name = section_name(ctx, m.file, m.section);
if rule.admits(&shdr, &name, key) {
if let Some(sig) =
make_sig(ctx, shared, out.kind, m.file, m.section, &shdr)?
{
class.insert(key, content_hash(&sig));
sigs.push(sig);
} else {
set_unique(class, key, &mut next_unique);
}
} else {
set_unique(class, key, &mut next_unique);
}
}
}
Ok(sigs)
}
fn set_unique(
class: &mut FxHashMap<(usize, u16), u64>,
key: (usize, u16),
next: &mut u64,
) {
let id = *next;
*next = next.wrapping_add(1);
class.insert(key, id);
}
struct Eligibility {
mode: IcfMode,
lsda: FxHashSet<(usize, u16)>,
address_taken: FxHashSet<(usize, u16)>,
}
impl Eligibility {
fn admits(&self, shdr: &Shdr64, name: &[u8], key: (usize, u16)) -> bool {
use crate::elf::constants::{
SHF_EXECINSTR, SHF_LINK_ORDER, SHF_WRITE, SHT_PROGBITS,
};
let flags = shdr.sh_flags.get();
if flags & SHF_ALLOC == 0
|| flags & SHF_EXECINSTR == 0
|| flags & SHF_WRITE != 0
|| shdr.sh_type.get() != SHT_PROGBITS
|| shdr.sh_size.get() == 0
{
return false;
}
if flags & SHF_LINK_ORDER != 0 {
return false;
}
if name == b".init" || name == b".fini" || is_c_identifier(name) {
return false;
}
if self.lsda.contains(&key) {
return false;
}
if self.mode == IcfMode::Safe && self.address_taken.contains(&key) {
return false;
}
true
}
}
fn make_sig<'a>(
ctx: &'a Context<'_>,
shared: bool,
out: OutKind,
file: usize,
section: u16,
shdr: &Shdr64,
) -> Result<Option<Sig<'a>>> {
let Some(input) = ctx.files.get(file) else {
return Ok(None);
};
let content = input.section_bytes(shdr)?;
let relocs = reloc_signatures(ctx, shared, file, section)?;
Ok(Some(Sig {
file,
section,
out,
flags: shdr.sh_flags.get(),
content,
relocs,
}))
}
fn reloc_signatures(
ctx: &Context<'_>,
shared: bool,
file: usize,
section: u16,
) -> Result<Vec<RelocSig>> {
let Some(input) = ctx.files.get(file) else {
return Ok(Vec::new());
};
let Some(entries) = input.relocations(section)? else {
return Ok(Vec::new());
};
let Some(symtab) = input.symbol_table()? else {
return Ok(entries
.iter()
.map(|r| RelocSig {
offset: r.r_offset.get(),
r_type: r.r_type(),
kind: TargetKind::Abs(r.r_addend.get().cast_unsigned()),
})
.collect());
};
let mut out = Vec::with_capacity(entries.len());
for r in entries {
let site = RelocRef {
file,
sym_idx: r.sym(),
addend: r.r_addend.get(),
};
let kind = resolve_target(ctx, shared, &symtab, site);
out.push(RelocSig {
offset: r.r_offset.get(),
r_type: r.r_type(),
kind,
});
}
Ok(out)
}
#[derive(Clone, Copy)]
struct RelocRef {
file: usize,
sym_idx: u32,
addend: i64,
}
fn merged_sec(
ctx: &Context<'_>,
target: (usize, u16),
inside: u64,
bias: i64,
) -> TargetKind {
let raw = inside.wrapping_add(bias.cast_unsigned());
if !ctx.merge.file_has_merges(target.0) {
return TargetKind::Sec { target, val: raw };
}
let moved = ctx.merge.remap(target.0, target.1, inside);
let carrier = ctx.merge.carrier_of(target.0, target.1);
match (moved, carrier) {
(Some(moved), Some(carrier)) => TargetKind::Sec {
target: carrier,
val: moved.wrapping_add(bias.cast_unsigned()),
},
_ => TargetKind::Sec { target, val: raw },
}
}
fn resolve_target(
ctx: &Context<'_>,
shared: bool,
symtab: &crate::elf::SymbolTable<'_>,
site: RelocRef,
) -> TargetKind {
use crate::elf::constants::SHN_ABS;
let RelocRef {
file,
sym_idx,
addend,
} = site;
let add = addend.cast_unsigned();
let Some(sym) = symtab.syms.get(sym_idx as usize) else {
return TargetKind::LocalExt {
at: (file, sym_idx),
val: add,
};
};
let local = TargetKind::LocalExt {
at: (file, sym_idx),
val: add,
};
if sym.bind() == crate::elf::constants::STB_LOCAL {
return match sym.st_shndx.get() {
SHN_ABS => TargetKind::Abs(sym.st_value.get().wrapping_add(add)),
shndx if real_section(shndx).is_none() => local,
shndx => {
let section_symbol =
sym.type_() == crate::elf::constants::STT_SECTION;
let (inside, bias) = if section_symbol {
(sym.st_value.get().wrapping_add(add), 0)
} else {
(sym.st_value.get(), addend)
};
merged_sec(ctx, (file, shndx), inside, bias)
}
};
}
let name = crate::symbol::version_stem(symtab.name(sym));
let Some(id) = ctx.symbols.find(name) else {
return local;
};
let Some(resolved) = ctx.symbols.symbol(id) else {
return local;
};
let external = TargetKind::Ext { id, val: add };
if resolved.is_preemptible(shared) {
return external;
}
match &resolved.kind {
SymbolKind::Defined(def) => match def.source {
DefSource::Section { index, offset } => {
merged_sec(ctx, (def.file, index), offset, addend)
}
DefSource::Absolute { value } => {
TargetKind::Abs(value.wrapping_add(add))
}
},
SymbolKind::Common { .. } | SymbolKind::Undefined { .. } => external,
}
}
const PROPAGATION_ROUNDS: usize = 2;
fn propagate_classes(
sigs: &[Sig<'_>],
class: &mut FxHashMap<(usize, u16), u64>,
) {
let mut next = Vec::with_capacity(sigs.len());
for _ in 0..PROPAGATION_ROUNDS {
next.clear();
for s in sigs {
let base = class.get(&(s.file, s.section)).copied().unwrap_or(0);
let mut h = base.wrapping_mul(0x9e37_79b9_7f4a_7c15);
for r in &s.relocs {
if let TargetKind::Sec { target, .. } = r.kind {
let tc = class.get(&target).copied().unwrap_or(0);
h = h
.wrapping_mul(31)
.wrapping_add(tc.wrapping_mul(0x100_0000_01b3));
}
}
next.push(h | (1u64 << 62));
}
debug_assert_eq!(next.len(), sigs.len(), "one new class per section");
for (s, &h) in sigs.iter().zip(next.iter()) {
class.insert((s.file, s.section), h);
}
}
}
fn content_hash(sig: &Sig<'_>) -> u64 {
let mut h = FxHasher::default();
sig.content.hash(&mut h);
h.finish() | (1u64 << 62)
}
fn segregate_to_fixpoint(
sigs: &mut [Sig],
class: &mut FxHashMap<(usize, u16), u64>,
) {
sigs.sort_by_key(|s| class.get(&(s.file, s.section)).copied().unwrap_or(0));
let mut base = next_base(class);
let mut scratch: FxHashMap<(usize, u16), u64> = FxHashMap::default();
segregate_pass(sigs, class, &mut scratch, base, true);
for _ in 0..sigs.len() {
base = base.wrapping_add(sigs.len() as u64 + 1);
if !segregate_pass(sigs, class, &mut scratch, base, false) {
break;
}
}
}
fn segregate_pass(
sigs: &mut [Sig<'_>],
class: &mut FxHashMap<(usize, u16), u64>,
scratch: &mut FxHashMap<(usize, u16), u64>,
base: u64,
constant: bool,
) -> bool {
if constant {
scratch.clear();
} else {
scratch.clone_from(class);
}
let snapshot = (!constant).then_some(&*scratch);
let lookup =
|key: (usize, u16)| -> Option<u64> { snapshot?.get(&key).copied() };
let mut changed = false;
let mut i = 0;
while i < sigs.len() {
let cur = class
.get(&(sigs[i].file, sigs[i].section))
.copied()
.unwrap_or(0);
let mut end = i + 1;
while end < sigs.len()
&& class
.get(&(sigs[end].file, sigs[end].section))
.copied()
.unwrap_or(0)
== cur
{
end += 1;
}
let mut subgroups = 0u64;
for k in i..end {
let rep = first_equal(sigs, i, k, constant, &lookup);
let id = base.wrapping_add(rep as u64);
class.insert((sigs[k].file, sigs[k].section), id);
if rep == k {
subgroups += 1;
}
}
if subgroups > 1 {
changed = true;
}
i = end;
}
sigs.sort_by_key(|s| class.get(&(s.file, s.section)).copied().unwrap_or(0));
changed
}
fn first_equal(
sigs: &[Sig<'_>],
begin: usize,
k: usize,
constant: bool,
lookup: &impl Fn((usize, u16)) -> Option<u64>,
) -> usize {
for m in begin..=k {
if m == k || sections_equal(&sigs[m], &sigs[k], constant, lookup) {
return m;
}
}
k
}
fn sections_equal(
a: &Sig<'_>,
b: &Sig<'_>,
constant: bool,
lookup: &impl Fn((usize, u16)) -> Option<u64>,
) -> bool {
if a.out != b.out || a.flags != b.flags || a.relocs.len() != b.relocs.len()
{
return false;
}
if constant && a.content != b.content {
return false;
}
for (ra, rb) in a.relocs.iter().zip(b.relocs.iter()) {
if ra.offset != rb.offset || ra.r_type != rb.r_type {
return false;
}
if !targets_equal(ra.kind, rb.kind, constant, lookup) {
return false;
}
}
true
}
fn targets_equal(
a: TargetKind,
b: TargetKind,
constant: bool,
lookup: &impl Fn((usize, u16)) -> Option<u64>,
) -> bool {
match (a, b) {
(
TargetKind::Sec {
target: ta,
val: va,
},
TargetKind::Sec {
target: tb,
val: vb,
},
) => {
if constant {
return va == vb;
}
match (lookup(ta), lookup(tb)) {
(Some(ca), Some(cb)) => ca == cb,
_ => false,
}
}
(TargetKind::Abs(va), TargetKind::Abs(vb)) => !constant || va == vb,
(
TargetKind::Ext { id: ia, val: va },
TargetKind::Ext { id: ib, val: vb },
) => !constant || (ia == ib && va == vb),
(
TargetKind::LocalExt { at: aa, val: va },
TargetKind::LocalExt { at: ab, val: vb },
) => !constant || (aa == ab && va == vb),
_ => false,
}
}
fn build_folds(
sigs: &[Sig],
class: &FxHashMap<(usize, u16), u64>,
) -> FxHashMap<(usize, u16), (usize, u16)> {
let mut groups: FxHashMap<u64, Vec<(usize, u16)>> = FxHashMap::default();
for s in sigs {
let c = class.get(&(s.file, s.section)).copied().unwrap_or(0);
groups.entry(c).or_default().push((s.file, s.section));
}
let mut folds = FxHashMap::default();
for (_c, mut members) in groups {
if members.len() < 2 {
continue;
}
members.sort_unstable();
let rep = members[0];
for m in members.into_iter().skip(1) {
folds.insert(m, rep);
}
}
folds
}
fn next_base(class: &FxHashMap<(usize, u16), u64>) -> u64 {
let max = class.values().copied().max().unwrap_or(0);
max.wrapping_add(1)
}
fn scan_address_taken(
ctx: &Context<'_>,
target: Target,
link: LinkMode,
) -> Result<FxHashSet<(usize, u16)>> {
let mut taken: FxHashSet<(usize, u16)> = FxHashSet::default();
for out in ctx.outputs.iter() {
if out.kind == OutKind::EhFrame {
continue;
}
for m in &out.members {
mark_address_taken(ctx, target, m.file, m.section, &mut taken)?;
}
}
mark_exported(ctx, link, &mut taken);
Ok(taken)
}
fn mark_exported(
ctx: &Context<'_>,
link: LinkMode,
taken: &mut FxHashSet<(usize, u16)>,
) {
if link == LinkMode::Static {
return;
}
for (name, sym) in ctx.symbols.entries() {
let SymbolKind::Defined(def) = &sym.kind else {
continue;
};
let DefSource::Section { index, .. } = def.source else {
continue;
};
if crate::dynamic::exports_definition(ctx, link, sym.visibility, name) {
taken.insert((def.file, index));
}
}
}
fn mark_address_taken(
ctx: &Context<'_>,
target: Target,
file: usize,
section: u16,
taken: &mut FxHashSet<(usize, u16)>,
) -> Result<()> {
let Some(input) = ctx.files.get(file) else {
return Ok(());
};
let Some(entries) = input.relocations(section)? else {
return Ok(());
};
let Some(symtab) = input.symbol_table()? else {
return Ok(());
};
for r in entries {
if is_call_reloc(target, r.r_type())? {
continue;
}
let Some(sym) = symtab.syms.get(r.sym() as usize) else {
continue;
};
let key = reloc_target_section(ctx, file, &symtab, sym);
if let Some(k) = key {
taken.insert(k);
}
}
Ok(())
}
fn is_call_reloc(target: Target, r_type: u32) -> Result<bool> {
let expr = spec_target(target, r_type)?.expr;
Ok(matches!(expr, RelExpr::Plt | RelExpr::PltPc))
}
fn reloc_target_section(
ctx: &Context<'_>,
file: usize,
symtab: &crate::elf::SymbolTable<'_>,
sym: &crate::elf::Sym64,
) -> Option<(usize, u16)> {
if sym.bind() == crate::elf::constants::STB_LOCAL {
return real_section(sym.st_shndx.get()).map(|shndx| (file, shndx));
}
let name = crate::symbol::version_stem(symtab.name(sym));
let id = ctx.symbols.find(name)?;
let resolved = ctx.symbols.symbol(id)?;
if let SymbolKind::Defined(def) = &resolved.kind
&& let DefSource::Section { index, .. } = def.source
{
Some((def.file, index))
} else {
None
}
}
fn section_shdr(
ctx: &Context<'_>,
file: usize,
section: u16,
) -> Result<Option<Shdr64>> {
let Some(input) = ctx.files.get(file) else {
return Ok(None);
};
let obj = input.object()?;
Ok(obj.sections().get(usize::from(section)).copied())
}
fn section_name(ctx: &Context<'_>, file: usize, section: u16) -> Vec<u8> {
let Some(input) = ctx.files.get(file) else {
return Vec::new();
};
input.object().map_or_else(
|_| Vec::new(),
|obj| {
obj.sections()
.get(usize::from(section))
.map_or_else(Vec::new, |s| obj.section_name(s).to_vec())
},
)
}