use rayon::prelude::*;
use rustc_hash::FxHashMap;
use super::cie::{CieKey, CiePool, CieRef, Claim};
use crate::{
elf::{Rela64, SymbolTable},
error::{Error, Result},
gc::reloc_target,
linker::{Context, in_input_order},
output::{OutKind, OutputSections},
};
const TERMINATOR: u64 = 4;
#[derive(Clone, Copy, Debug)]
pub struct Piece {
pub in_off: u64,
pub len: u64,
pub out_off: Option<u64>,
pub fde: bool,
}
impl Piece {
pub const fn covers(self, offset: u64) -> bool {
offset >= self.in_off && offset < self.in_off.saturating_add(self.len)
}
}
pub struct EhMember {
pieces: Vec<Piece>,
live_size: u64,
live_fdes: u64,
cie_redirect: Vec<(u64, CieRef)>,
}
impl EhMember {
pub fn pieces(&self) -> &[Piece] {
&self.pieces
}
pub fn cie_redirect(&self, in_off: u64) -> Option<CieRef> {
self.cie_redirect
.iter()
.find(|(off, _)| *off == in_off)
.map(|(_, at)| *at)
}
pub const fn live_size(&self) -> u64 {
self.live_size
}
pub fn piece_at(&self, offset: u64) -> Option<Piece> {
super::record_at(&self.pieces, offset)
.and_then(|i| self.pieces.get(i))
.copied()
}
}
#[derive(Default)]
pub struct EhFramePlan {
by_section: FxHashMap<(usize, u16), EhMember>,
sizes: Vec<u64>,
live_fdes: u64,
}
impl EhFramePlan {
pub fn member(&self, file: usize, section: u16) -> Option<&EhMember> {
self.by_section.get(&(file, section))
}
pub const fn live_fdes(&self) -> u64 {
self.live_fdes
}
pub fn sizes(&self) -> &[u64] {
&self.sizes
}
}
pub fn build(ctx: &Context<'_>) -> Result<EhFramePlan> {
let mut plan = EhFramePlan::default();
let Some(out) = ctx.outputs.section(OutKind::EhFrame) else {
return Ok(plan);
};
let live = LiveSections::new(&ctx.outputs);
let mut split: Vec<Result<SplitMember>> = Vec::new();
out.members
.par_iter()
.map(|m| split_member(ctx, &live, m.file, m.section))
.collect_into_vec(&mut split);
plan.sizes = Vec::with_capacity(out.members.len());
let mut pool = CiePool::default();
for (m, member) in out.members.iter().zip(in_input_order(split)?) {
let member = share_cies(&mut pool, m.file, m.section, member);
plan.live_fdes = plan.live_fdes.saturating_add(member.live_fdes);
plan.sizes.push(member.live_size);
plan.by_section.insert((m.file, m.section), member);
}
if let Some(last) = plan.sizes.last_mut() {
*last = last.saturating_add(TERMINATOR);
}
Ok(plan)
}
#[derive(Default)]
struct LiveSections {
rows: Vec<Vec<bool>>,
}
impl LiveSections {
fn new(outputs: &OutputSections) -> Self {
let mut live = Self::default();
for out in outputs.iter() {
for m in &out.members {
live.insert(m.file, m.section);
}
}
live
}
fn insert(&mut self, file: usize, section: u16) {
if self.rows.len() <= file {
self.rows.resize_with(file.saturating_add(1), Vec::new);
}
let Some(row) = self.rows.get_mut(file) else {
return;
};
let at = usize::from(section);
if row.len() <= at {
row.resize(at.saturating_add(1), false);
}
if let Some(flag) = row.get_mut(at) {
*flag = true;
}
}
fn contains(&self, (file, section): (usize, u16)) -> bool {
self.rows
.get(file)
.and_then(|row| row.get(usize::from(section)))
.copied()
.unwrap_or(false)
}
}
#[derive(Default)]
struct SplitMember {
pieces: Vec<Piece>,
fde: Vec<bool>,
keep: Vec<bool>,
keys: Vec<(usize, CieKey)>,
}
fn split_member(
ctx: &Context<'_>,
live: &LiveSections,
file: usize,
section: u16,
) -> Result<SplitMember> {
let mut pieces = Vec::new();
let mut fde = Vec::new();
let Some(input) = ctx.files.get(file) else {
return Ok(SplitMember::default());
};
let obj = input.object()?;
let Some(shdr) = obj.sections().get(usize::from(section)) else {
return Ok(SplitMember::default());
};
let data = obj.section_data(shdr)?;
let end = super::records(data, &mut pieces, &mut fde);
if data.get(end..).unwrap_or_default().iter().any(|&b| b != 0) {
return Err(Error::Format("undecodable .eh_frame record"));
}
let symtab = input.symbol_table()?;
let entries = input.relocations(section)?;
let keep =
keep_flags(ctx, live, file, symtab.as_ref(), entries, &pieces, &fde);
let keys = cie_keys(ctx, file, data, symtab.as_ref(), entries, &pieces);
Ok(SplitMember {
pieces,
fde,
keep,
keys,
})
}
fn cie_keys(
ctx: &Context<'_>,
file: usize,
data: &[u8],
symtab: Option<&SymbolTable<'_>>,
entries: Option<&[Rela64]>,
pieces: &[Piece],
) -> Vec<(usize, CieKey)> {
let Some(symtab) = symtab else {
return Vec::new();
};
let covering = cie_relocs(pieces, entries.unwrap_or_default());
let mut keys = Vec::new();
for (i, piece) in pieces.iter().enumerate() {
if piece.fde {
continue;
}
let start = usize::try_from(piece.in_off).unwrap_or(usize::MAX);
let len = usize::try_from(piece.len).unwrap_or(0);
let Some(bytes) = data.get(start..start.saturating_add(len)) else {
continue;
};
let from = covering.partition_point(|(p, _, _)| *p < i);
let to = covering.partition_point(|(p, _, _)| *p <= i);
let rels = covering.get(from..to).unwrap_or_default();
if let Some(key) = CieKey::new(ctx, symtab, file, bytes, rels) {
keys.push((i, key));
}
}
keys
}
fn cie_relocs(
pieces: &[Piece],
entries: &[Rela64],
) -> Vec<(usize, u64, Rela64)> {
let mut covering: Vec<(usize, u64, Rela64)> = Vec::new();
for r in entries {
let at = r.r_offset.get();
let Some(i) = super::record_at(pieces, at) else {
continue;
};
let Some(piece) = pieces.get(i).filter(|p| !p.fde) else {
continue;
};
covering.push((i, at.saturating_sub(piece.in_off), *r));
}
covering.sort_unstable_by_key(|(i, at, _)| (*i, *at));
covering
}
fn share_cies(
pool: &mut CiePool,
file: usize,
section: u16,
mut split: SplitMember,
) -> EhMember {
let mut claimed: Vec<(usize, usize)> = Vec::new();
let mut shared: Vec<(usize, CieRef)> = Vec::new();
for (i, key) in split.keys.drain(..) {
let at = CieRef {
file,
section,
out_off: 0,
};
match pool.claim(key, at) {
Claim::Kept(slot) => claimed.push((i, slot)),
Claim::Shared(found) => {
if let Some(flag) = split.keep.get_mut(i) {
*flag = false;
}
shared.push((i, found));
}
}
}
let mut member = assign_offsets(split.pieces, &split.fde, &split.keep);
for (i, slot) in claimed {
if let Some(off) = member.pieces.get(i).and_then(|p| p.out_off) {
pool.place(slot, off);
}
}
member.cie_redirect = shared
.into_iter()
.filter_map(|(i, at)| member.pieces.get(i).map(|p| (p.in_off, at)))
.collect();
member
}
#[allow(clippy::too_many_arguments)]
fn keep_flags(
ctx: &Context<'_>,
live: &LiveSections,
file: usize,
symtab: Option<&SymbolTable<'_>>,
entries: Option<&[Rela64]>,
pieces: &[Piece],
fde: &[bool],
) -> Vec<bool> {
let mut keep = vec![true; pieces.len()];
let is_fde = |i: usize| fde.get(i).copied().unwrap_or(false);
let (Some(symtab), Some(entries)) = (symtab, entries) else {
for (i, flag) in keep.iter_mut().enumerate() {
*flag = !is_fde(i);
}
return keep;
};
let first = super::first_reloc_syms(pieces, entries);
for (i, flag) in keep.iter_mut().enumerate() {
if !is_fde(i) {
continue;
}
*flag = first
.get(i)
.copied()
.flatten()
.and_then(|sym_idx| reloc_target(ctx, symtab, file, sym_idx))
.is_some_and(|target| live.contains(target));
}
keep
}
fn assign_offsets(
mut pieces: Vec<Piece>,
fde: &[bool],
keep: &[bool],
) -> EhMember {
debug_assert_eq!(pieces.len(), fde.len(), "one kind flag per record");
let mut cursor = 0u64;
let mut live_fdes = 0u64;
for (i, piece) in pieces.iter_mut().enumerate() {
if !keep.get(i).copied().unwrap_or(true) {
piece.out_off = None;
continue;
}
piece.out_off = Some(cursor);
cursor = cursor.saturating_add(piece.len);
if fde.get(i).copied().unwrap_or(false) {
live_fdes = live_fdes.saturating_add(1);
}
}
EhMember {
pieces,
live_size: cursor,
live_fdes,
cie_redirect: Vec::new(),
}
}