use hashbrown::HashTable;
use rustc_hash::FxHashMap;
use crate::{
elf::{
ObjectFile, Rela64, Shdr64, SymbolTable,
constants::{
SHF_MERGE, SHF_STRINGS, SHT_NOBITS, STB_LOCAL, STT_SECTION,
},
},
error::{Error, Result},
input::InputFile,
linker::Context,
output::OutKind,
symbol::name_hash,
util::is_c_identifier,
};
#[derive(Copy, Clone, Eq, PartialEq, Hash, Debug)]
enum Pieces {
Strings,
Fixed(u64),
}
#[derive(Copy, Clone, Eq, PartialEq, Hash, Debug)]
pub enum Scope {
Out(OutKind),
Debug(u32),
}
#[derive(Copy, Clone, Eq, PartialEq, Hash, Debug)]
struct PoolKey {
scope: Scope,
pieces: Pieces,
align: u64,
}
struct SectionPieces {
pool: u32,
map: Vec<(u32, u32)>,
end: u32,
}
#[derive(Default)]
struct PoolIndex {
table: HashTable<(u64, u32, u32)>,
}
impl PoolIndex {
fn find(&self, pool: &[u8], piece: &[u8], hash: u64) -> Option<u32> {
self.table
.find(hash, |&(h, at, len)| {
h == hash
&& pool.get(at as usize..at as usize + len as usize)
== Some(piece)
})
.map(|&(_, at, _)| at)
}
fn insert(&mut self, at: u32, len: u32, hash: u64) {
self.table
.insert_unique(hash, (hash, at, len), |&(h, ..)| h);
}
fn reserve(&mut self, extra: usize) {
self.table.reserve(extra, |&(h, ..)| h);
}
}
pub struct Pool {
bytes: Vec<u8>,
carrier: (usize, u16),
scope: Scope,
}
impl Pool {
pub fn bytes(&self) -> &[u8] {
&self.bytes
}
}
#[derive(Default)]
pub struct MergePlan {
pools: Vec<Pool>,
sections: Vec<SectionPieces>,
rows: Vec<Vec<u32>>,
local_bits: Vec<Vec<u64>>,
carriers: FxHashMap<u64, u32>,
}
const NOT_MERGED: u32 = u32::MAX;
const fn section_key(file: usize, section: u16) -> u64 {
((file as u64) << 16) | section as u64
}
impl MergePlan {
pub fn is_empty(&self) -> bool {
self.pools.is_empty()
}
pub fn carried_bytes(&self, file: usize, section: u16) -> Option<&[u8]> {
let &pool = self.carriers.get(§ion_key(file, section))?;
self.pools.get(pool as usize).map(Pool::bytes)
}
fn entry(&self, file: usize, section: u16) -> Option<&SectionPieces> {
let &idx = self.rows.get(file)?.get(usize::from(section))?;
if idx == NOT_MERGED {
return None;
}
self.sections.get(idx as usize)
}
pub fn is_merged(&self, file: usize, section: u16) -> bool {
self.entry(file, section).is_some()
}
pub fn file_has_merges(&self, file: usize) -> bool {
self.rows.get(file).is_some_and(|row| !row.is_empty())
}
pub fn names_merged(&self, file: usize, sym_idx: u32) -> bool {
let Some(bits) = self.local_bits.get(file) else {
return false;
};
let word = (sym_idx / 64) as usize;
bits.get(word).is_some_and(|w| w >> (sym_idx % 64) & 1 != 0)
}
pub fn remap(&self, file: usize, section: u16, offset: u64) -> Option<u64> {
let entry = self.entry(file, section)?;
let at = u32::try_from(offset).ok()?;
if at >= entry.end {
return None;
}
debug_assert!(
entry.map.first().is_none_or(|&(first, _)| first == 0),
"a merged section's pieces tile it from byte zero"
);
let idx = match entry.map.binary_search_by_key(&at, |&(i, _)| i) {
Ok(i) => i,
Err(0) => return None,
Err(i) => i.saturating_sub(1),
};
let &(in_off, out_off) = entry.map.get(idx)?;
Some(u64::from(out_off).wrapping_add(u64::from(at - in_off)))
}
pub fn addend(
&self,
symtab: &SymbolTable<'_>,
file: usize,
r: &Rela64,
) -> i64 {
self.moved_addend(symtab, file, r)
.unwrap_or_else(|| r.r_addend.get())
}
fn moved_addend(
&self,
symtab: &SymbolTable<'_>,
file: usize,
r: &Rela64,
) -> Option<i64> {
let sym = symtab.syms.get(r.sym() as usize)?;
if sym.bind() != STB_LOCAL {
return None;
}
let addend = r.r_addend.get();
let shndx = sym.st_shndx.get();
if sym.type_() == STT_SECTION {
let inside =
sym.st_value.get().wrapping_add(addend.cast_unsigned());
return self.remap(file, shndx, inside).map(u64::cast_signed);
}
let moved = self.remap(file, shndx, sym.st_value.get())?;
Some(moved.cast_signed().wrapping_add(addend))
}
pub fn carrier_of(
&self,
file: usize,
section: u16,
) -> Option<(usize, u16)> {
let entry = self.entry(file, section)?;
self.pools.get(entry.pool as usize).map(|p| p.carrier)
}
pub fn folded(&self) -> Vec<((usize, u16), (usize, u16))> {
let mut out = Vec::new();
for (file, row) in self.rows.iter().enumerate() {
for (section, &idx) in row.iter().enumerate() {
if idx == NOT_MERGED {
continue;
}
let Some(pool) = self
.sections
.get(idx as usize)
.and_then(|e| self.pools.get(e.pool as usize))
else {
continue;
};
if !matches!(pool.scope, Scope::Out(_)) {
continue;
}
let at = (file, u16::try_from(section).unwrap_or(u16::MAX));
if pool.carrier != at {
out.push((at, pool.carrier));
}
}
}
out.sort_unstable();
out
}
pub fn carrier_sizes(&self) -> Vec<(usize, u16, u64)> {
self.pools
.iter()
.filter(|p| matches!(p.scope, Scope::Out(_)))
.map(|p| {
let (file, section) = p.carrier;
(file, section, u64::try_from(p.bytes.len()).unwrap_or(0))
})
.collect()
}
pub fn member_size(&self, file: usize, section: u16) -> Option<u64> {
let entry = self.entry(file, section)?;
let pool = self.pools.get(entry.pool as usize)?;
Some(if pool.carrier == (file, section) {
u64::try_from(pool.bytes.len()).unwrap_or(0)
} else {
0
})
}
}
fn pieces_of(shdr: &Shdr64, relocated: bool) -> Option<Pieces> {
if relocated {
return None;
}
if shdr.sh_flags.get() & SHF_MERGE == 0 || shdr.sh_size.get() == 0 {
return None;
}
if shdr.sh_type.get() == SHT_NOBITS {
return None;
}
if shdr.sh_flags.get() & SHF_STRINGS != 0 {
return (shdr.sh_entsize.get() == 1).then_some(Pieces::Strings);
}
let entsize = shdr.sh_entsize.get();
if entsize == 0 || !shdr.sh_size.get().is_multiple_of(entsize) {
return None;
}
Some(Pieces::Fixed(entsize))
}
fn split(data: &[u8], pieces: Pieces) -> Result<Vec<Piece>> {
let piece = |start: usize, end: usize| {
let off = u32::try_from(start)
.map_err(|_| Error::Format("merged piece offset"))?;
let len = u32::try_from(end - start)
.map_err(|_| Error::Format("merge piece length"))?;
Ok(Piece {
off,
len,
hash: name_hash(data.get(start..end).unwrap_or_default()),
})
};
match pieces {
Pieces::Strings => {
if data.last() != Some(&0) {
return Err(Error::Format(
"mergeable string section is not NUL terminated",
));
}
let mut out = Vec::new();
let mut start = 0usize;
for (i, &b) in data.iter().enumerate() {
if b == 0 {
let end = i.saturating_add(1);
out.push(piece(start, end)?);
start = end;
}
}
Ok(out)
}
Pieces::Fixed(size) => {
let n = usize::try_from(size).unwrap_or(1).max(1);
data.chunks_exact(n)
.enumerate()
.map(|(i, _)| {
let start = i.saturating_mul(n);
piece(start, start + n)
})
.collect()
}
}
}
struct Piece {
off: u32,
len: u32,
hash: u64,
}
struct Prepared<'data> {
scope: Scope,
file: usize,
section: u16,
align: u64,
pieces: Pieces,
reserve: u64,
data: &'data [u8],
split: Vec<Piece>,
}
pub fn build_plan(ctx: &Context<'_>) -> Result<MergePlan> {
use rayon::prelude::*;
let mut plan = MergePlan::default();
let mut pool_of: FxHashMap<PoolKey, u32> = FxHashMap::default();
let mut seen: Vec<PoolIndex> = Vec::new();
let objs = ctx
.files
.iter()
.map(|f| f.object().ok())
.collect::<Vec<_>>();
let allocated = ctx.outputs.iter().flat_map(|out| {
out.members
.iter()
.map(move |m| (Scope::Out(out.kind), m.file, m.section))
});
let debug_count = fits_u32(ctx.debug.sections.len(), "debug sections")?;
let debug =
(0..debug_count)
.zip(&ctx.debug.sections)
.flat_map(|(i, sec)| {
let scope = Scope::Debug(i);
sec.members.iter().map(move |m| (scope, m.file, m.section))
});
let members: Vec<(Scope, usize, u16)> = allocated.chain(debug).collect();
let prepared: Vec<Result<Option<Prepared<'_>>>> = members
.par_iter()
.map(|&(scope, file, section)| {
prepare(ctx, &objs, scope, file, section)
})
.collect();
for entry in prepared {
let Some(p) = entry? else { continue };
let key = PoolKey {
scope: p.scope,
pieces: p.pieces,
align: p.align,
};
let next = fits_u32(plan.pools.len(), "merge pools")?;
let pool = *pool_of.entry(key).or_insert_with(|| {
let idx = next;
plan.pools.push(Pool {
bytes: Vec::new(),
carrier: (p.file, p.section),
scope: p.scope,
});
plan.carriers
.entry(section_key(p.file, p.section))
.or_insert(idx);
seen.push(PoolIndex::default());
idx
});
if let Some(dst) = plan.pools.get_mut(pool as usize)
&& dst.bytes.capacity() == 0
{
dst.bytes.reserve(usize::try_from(p.reserve).unwrap_or(0));
}
let (Some(dst), Some(index)) = (
plan.pools.get_mut(pool as usize),
seen.get_mut(pool as usize),
) else {
continue;
};
let mut map = Vec::new();
absorb(&mut dst.bytes, index, &p, &mut map)?;
let end = u32::try_from(p.data.len())
.map_err(|_| Error::Format("mergeable section size"))?;
let entry = fits_u32(plan.sections.len(), "merged sections")?;
plan.sections.push(SectionPieces { pool, map, end });
if plan.rows.len() <= p.file {
plan.rows.resize_with(p.file.saturating_add(1), Vec::new);
}
if let Some(row) = plan.rows.get_mut(p.file) {
let at = usize::from(p.section);
if row.len() <= at {
row.resize(at.saturating_add(1), NOT_MERGED);
}
if let Some(slot) = row.get_mut(at) {
*slot = entry;
}
}
}
plan.local_bits = local_bits(ctx, &plan)?;
Ok(plan)
}
fn local_bits(ctx: &Context<'_>, plan: &MergePlan) -> Result<Vec<Vec<u64>>> {
use rayon::prelude::*;
(0..plan.rows.len())
.into_par_iter()
.map(|file| {
if !plan.file_has_merges(file) {
return Ok(Vec::new());
}
let Some(symtab) = ctx
.files
.get(file)
.map(InputFile::symbol_table)
.transpose()?
else {
return Ok(Vec::new());
};
let Some(symtab) = symtab else {
return Ok(Vec::new());
};
let mut bits = vec![0u64; symtab.syms.len().div_ceil(64)];
for (i, sym) in symtab.syms.iter().enumerate() {
if sym.bind() == STB_LOCAL
&& plan.is_merged(file, sym.st_shndx.get())
&& let Some(word) = bits.get_mut(i / 64)
{
*word |= 1u64 << (i % 64);
}
}
Ok(bits)
})
.collect()
}
fn prepare<'data>(
ctx: &Context<'data>,
objs: &[Option<ObjectFile<'data>>],
scope: Scope,
file: usize,
section: u16,
) -> Result<Option<Prepared<'data>>> {
let (Some(input), Some(obj)) =
(ctx.files.get(file), objs.get(file).and_then(Option::as_ref))
else {
return Ok(None);
};
let Some(shdr) = obj.sections().get(usize::from(section)) else {
return Ok(None);
};
let mergeable = shdr.sh_flags.get() & SHF_MERGE != 0
&& !is_c_identifier(obj.section_name(shdr));
let relocated = mergeable && input.relocations(section)?.is_some();
let Some(pieces) = pieces_of(shdr, relocated).filter(|_| mergeable) else {
return Ok(None);
};
let data = obj.section_data(shdr)?;
let split = split(data, pieces)?;
Ok(Some(Prepared {
scope,
file,
section,
align: shdr.sh_addralign.get().max(1),
pieces,
reserve: shdr.sh_size.get(),
data,
split,
}))
}
fn absorb(
pool: &mut Vec<u8>,
index: &mut PoolIndex,
p: &Prepared<'_>,
map: &mut Vec<(u32, u32)>,
) -> Result<()> {
map.clear();
map.reserve(p.split.len());
index.reserve(p.split.len());
let align = usize::try_from(p.align).unwrap_or(1).max(1);
for piece in &p.split {
let start = piece.off as usize;
let bytes = p
.data
.get(start..start.saturating_add(piece.len as usize))
.ok_or(Error::OutOfRange("merge piece bounds"))?;
let mut out_off = index.find(pool, bytes, piece.hash);
if out_off.is_none() {
pool.resize(pool.len().next_multiple_of(align), 0);
let at = fits_u32(pool.len(), "merge pool offset")?;
let len = fits_u32(bytes.len(), "merge piece length")?;
pool.extend_from_slice(bytes);
index.insert(at, len, piece.hash);
out_off = Some(at);
}
let Some(out_off) = out_off else {
return Err(Error::OutOfRange("merge piece placement"));
};
map.push((piece.off, out_off));
}
Ok(())
}
fn fits_u32(value: usize, what: &'static str) -> Result<u32> {
u32::try_from(value).map_err(|_| Error::OutOfRange(what))
}