use bytemuck::Zeroable;
use rustc_hash::FxHashMap;
use crate::{
elf::{
Sym64,
constants::{
SHN_UNDEF, STB_GLOBAL, STB_GNU_UNIQUE, STB_WEAK, STT_NOTYPE,
STT_OBJECT, STT_TLS, STV_DEFAULT,
},
},
endian::{U16, U32, U64},
layout::{CopyName, CopySlot, Export, GotKind, Layout, Sect},
linker::Context,
symbol::{SymbolId, SymbolKind},
util::{cstr_at, push_u32},
};
#[derive(Clone, Copy)]
pub(super) struct DynSymEntry {
pub name_off: u32,
pub info: u8,
pub other: u8,
pub shndx: u16,
pub value: u64,
pub size: u64,
}
impl DynSymEntry {
const fn is_hashable(&self) -> bool {
self.shndx != SHN_UNDEF || self.value != 0
}
}
#[derive(Clone, Copy, Default)]
pub(super) struct ImportRow {
sym_type: u8,
value: u64,
size: u64,
}
pub(super) struct DynSym {
pub entries: Vec<DynSymEntry>,
pub by_name: FxHashMap<Vec<u8>, u32>,
pub strtab: Vec<u8>,
pub soname_off: Option<u32>,
}
impl DynSym {
pub(super) fn new() -> Self {
Self {
entries: Vec::new(),
by_name: FxHashMap::default(),
strtab: vec![0],
soname_off: None,
}
}
#[allow(clippy::too_many_arguments)]
fn add_row(
&mut self,
name: &[u8],
weak: bool,
unique: bool,
sym_type: u8,
other: u8,
shndx: u16,
value: u64,
size: u64,
) -> u32 {
let idx = next_index(self.entries.len());
let name_off = intern(&mut self.strtab, name);
let bind = if weak {
STB_WEAK
} else if unique {
STB_GNU_UNIQUE
} else {
STB_GLOBAL
};
self.entries.push(DynSymEntry {
name_off,
info: (bind << 4) | sym_type,
other,
shndx,
value,
size,
});
self.by_name.insert(name.to_vec(), idx);
idx
}
pub(super) fn add_export(&mut self, e: &Export, name: &[u8]) -> u32 {
self.add_row(
name,
e.weak,
e.unique,
e.sym_type,
e.visibility,
e.shndx,
e.addr,
e.size,
)
}
pub(super) fn add_import(
&mut self,
name: &[u8],
weak: bool,
row: ImportRow,
) -> u32 {
self.add_row(
name,
weak,
false,
row.sym_type,
STV_DEFAULT,
SHN_UNDEF,
row.value,
row.size,
)
}
pub(super) fn add_copy(
&mut self,
name: &[u8],
weak: bool,
shndx: u16,
value: u64,
size: u64,
) -> u32 {
self.add_row(
name,
weak,
false,
STT_OBJECT,
STV_DEFAULT,
shndx,
value,
size,
)
}
pub(super) fn index_of(&self, name: &[u8]) -> Option<u32> {
self.by_name.get(name).copied()
}
pub(super) fn materialise(self) -> Vec<Sym64> {
let mut out = Vec::with_capacity(self.entries.len().saturating_add(1));
out.push(Sym64::zeroed());
for e in self.entries {
out.push(Sym64 {
st_name: U32::new(e.name_off),
st_info: e.info,
st_other: e.other,
st_shndx: U16::new(e.shndx),
st_value: U64::new(e.value),
st_size: U64::new(e.size),
});
}
out
}
pub(super) fn reorder_for_gnu_hash(&mut self) -> GnuHashOrdering {
let n = self.entries.len();
let mut undef_old: Vec<usize> = Vec::new();
let mut def_old: Vec<usize> = Vec::new();
for (i, e) in self.entries.iter().enumerate() {
if e.is_hashable() {
def_old.push(i);
} else {
undef_old.push(i);
}
}
let n_defined = def_old.len();
let n_buckets = buckets_for(n_defined);
let mask_words = bloom_words(n_defined as u64);
let mut keyed: Vec<(u32, u32, usize)> = def_old
.iter()
.map(|&i| {
let e = &self.entries[i];
(bucket_of(e, &self.strtab, n_buckets), e.name_off, i)
})
.collect();
keyed.sort_unstable_by_key(|&(bucket, name_off, _)| (bucket, name_off));
for (slot, &(_, _, i)) in def_old.iter_mut().zip(&keyed) {
*slot = i;
}
let mut perm = Vec::with_capacity(n);
perm.extend(undef_old.iter().copied());
perm.extend(def_old.iter().copied());
let mut remap = vec![0u32; n.saturating_add(1)];
for (new0, &old0) in perm.iter().enumerate() {
remap[old0.saturating_add(1)] =
u32::try_from(new0.saturating_add(1)).unwrap_or(u32::MAX);
}
let old_entries = core::mem::take(&mut self.entries);
self.entries = perm.iter().map(|&i| old_entries[i]).collect();
self.by_name.clear();
for (k, e) in self.entries.iter().enumerate() {
let name = cstr_at(&self.strtab, e.name_off);
let idx = u32::try_from(k.saturating_add(1)).unwrap_or(u32::MAX);
self.by_name.insert(name.to_vec(), idx);
}
GnuHashOrdering {
symoffset: u32::try_from(perm.len() - n_defined + 1)
.unwrap_or(u32::MAX),
mask_words,
n_buckets,
bloom_shift: GNU_BLOOM_SHIFT,
remap,
}
}
}
pub(super) struct GnuHashOrdering {
pub symoffset: u32,
pub mask_words: u32,
pub n_buckets: u32,
pub bloom_shift: u32,
pub remap: Vec<u32>,
}
fn next_index(len: usize) -> u32 {
u32::try_from(len + 1).unwrap_or(u32::MAX)
}
pub(super) fn names_by_id<'ctx>(ctx: &'ctx Context<'_>) -> Vec<&'ctx [u8]> {
ctx.symbols.ids().map(|id| ctx.symbols.name(id)).collect()
}
pub(super) fn copy_rows(
layout: &Layout,
) -> impl Iterator<Item = (&CopySlot, &CopyName)> {
layout
.copy_slots
.iter()
.flat_map(|slot| slot.names.iter().map(move |name| (slot, name)))
}
pub(super) fn intern(bytes: &mut Vec<u8>, name: &[u8]) -> u32 {
let off = u32::try_from(bytes.len()).unwrap_or(u32::MAX);
bytes.extend_from_slice(name);
bytes.push(0);
off
}
pub(super) fn add_imports(
ctx: &Context<'_>,
layout: &Layout,
names: &[&[u8]],
data_ids: &[SymbolId],
table: &mut DynSym,
) -> FxHashMap<SymbolId, u32> {
let mut index: FxHashMap<SymbolId, u32> = FxHashMap::default();
let copy_ids = super::copy_id_set(layout);
for (slot, name) in copy_rows(layout) {
let weak = name.id.is_some_and(|id| {
ctx.symbols.symbol(id).is_some_and(|s| {
matches!(s.kind, SymbolKind::Undefined { weak: true })
})
});
let idx = table.add_copy(
&name.name,
weak,
layout.shndx(Sect::Bss),
slot.addr,
name.size,
);
if let Some(id) = name.id {
index.insert(id, idx);
}
}
for keys in [&layout.got_keys, &layout.plt_keys] {
for key in keys {
let Some(id) = key.global_id() else {
continue;
};
let Some(name) = names.get(id.0) else {
continue;
};
if copy_ids.contains(&id) {
continue;
}
let row = import_row(ctx, layout, id, name, key.kind);
add_import_row(ctx, id, name, row, table, &mut index);
}
}
for &id in data_ids {
let Some(name) = names.get(id.0) else {
continue;
};
let row = import_row(ctx, layout, id, name, GotKind::Addr);
add_import_row(ctx, id, name, row, table, &mut index);
}
index
}
fn add_import_row(
ctx: &Context<'_>,
id: SymbolId,
name: &[u8],
row: ImportRow,
table: &mut DynSym,
index: &mut FxHashMap<SymbolId, u32>,
) {
if name.is_empty() || !super::is_runtime_import(ctx, id) {
return;
}
let Some(sym) = ctx.symbols.symbol(id) else {
return;
};
let idx = table.index_of(name).unwrap_or_else(|| {
let weak = matches!(sym.kind, SymbolKind::Undefined { weak: true });
table.add_import(name, weak, row)
});
index.insert(id, idx);
}
fn import_row(
ctx: &Context<'_>,
layout: &Layout,
id: SymbolId,
name: &[u8],
kind: GotKind,
) -> ImportRow {
if matches!(kind, GotKind::TlsOffset | GotKind::TlsModule) {
return ImportRow {
sym_type: STT_TLS,
..ImportRow::default()
};
}
let mut row = ImportRow {
sym_type: dep_sym_type(ctx, name),
..ImportRow::default()
};
if layout.canonical_plt.contains(&id) {
row.value = layout.plt_entry_addr(id).unwrap_or_default();
row.size = ctx.dep_exports.get(name).map_or(0, |e| e.size);
}
row
}
fn dep_sym_type(ctx: &Context<'_>, name: &[u8]) -> u8 {
ctx.dep_exports.get(name).map_or(STT_NOTYPE, |e| e.sym_type)
}
pub(super) fn build_dynstr(
table: &mut DynSym,
soname: Option<&[u8]>,
) -> Vec<u8> {
if let Some(s) = soname {
let off = intern(&mut table.strtab, s);
table.soname_off = Some(off);
}
table.strtab.clone()
}
pub(super) fn build_hash(table: &DynSym) -> Vec<u8> {
let nsyms = table.entries.len().saturating_add(1);
let nbucket = nsyms.max(1);
let mut buckets = vec![0u32; nbucket];
let mut chain = vec![0u32; nsyms];
for (i, e) in table.entries.iter().enumerate() {
let sym_idx = u32::try_from(i + 1).unwrap_or(u32::MAX);
let name = cstr_at(&table.strtab, e.name_off);
let b = (elf_hash(name) as usize) % nbucket;
chain[sym_idx as usize] = buckets[b];
buckets[b] = sym_idx;
}
let mut bytes = Vec::with_capacity(
(2usize + nbucket + nsyms) * core::mem::size_of::<u32>(),
);
push_u32(&mut bytes, u32::try_from(nbucket).unwrap_or(u32::MAX));
push_u32(&mut bytes, u32::try_from(nsyms).unwrap_or(u32::MAX));
for b in &buckets {
push_u32(&mut bytes, *b);
}
for c in &chain {
push_u32(&mut bytes, *c);
}
bytes
}
const GNU_BLOOM_SHIFT: u32 = 6;
fn buckets_for(n_defined: usize) -> u32 {
u32::try_from(n_defined / 4).unwrap_or(u32::MAX).max(1)
}
fn bloom_words(n_defined: u64) -> u32 {
let words = n_defined.saturating_mul(12) / 64;
let pow = words.checked_next_power_of_two().unwrap_or(1 << 30);
u32::try_from(pow.max(1)).unwrap_or(1)
}
pub(super) fn gnu_hash_size(n_defined: u64) -> u64 {
let mask_words = u64::from(bloom_words(n_defined));
let n_buckets = n_defined / 4;
let n_buckets = n_buckets.max(1);
16 + 8 * mask_words + 4 * n_buckets + 4 * n_defined
}
fn bucket_of(e: &DynSymEntry, strtab: &[u8], n_buckets: u32) -> u32 {
let name = cstr_at(strtab, e.name_off);
dl_new_hash(name) % n_buckets
}
pub(super) fn build_gnu_hash(
table: &DynSym,
order: &GnuHashOrdering,
) -> Vec<u8> {
let mask_words = order.mask_words;
let n_buckets = order.n_buckets.max(1);
let symoffset = order.symoffset as usize;
let start = symoffset.saturating_sub(1);
let defined: &[DynSymEntry] = table.entries.get(start..).unwrap_or(&[]);
let hb: Vec<(u32, u32)> = defined
.iter()
.map(|e| {
let name = cstr_at(&table.strtab, e.name_off);
let h = dl_new_hash(name);
(h, h % n_buckets)
})
.collect();
let word_mask = u64::from(mask_words).saturating_sub(1);
let mut bloom = vec![0u64; mask_words as usize];
for &(h, _) in &hb {
let word_idx = ((u64::from(h) / 64) & word_mask) as usize;
let bit1 = u64::from(h % 64);
let bit2 = u64::from((h >> order.bloom_shift) % 64);
if let Some(w) = bloom.get_mut(word_idx) {
*w |= 1u64 << bit1;
*w |= 1u64 << bit2;
}
}
let mut buckets = vec![0u32; n_buckets as usize];
let mut chain: Vec<u32> = Vec::with_capacity(hb.len());
let mut prev_bucket: i64 = -1;
for (k, &(h, bucket)) in hb.iter().enumerate() {
let continues = hb.get(k + 1).is_some_and(|&(_, nb)| nb == bucket);
let val = if continues { h & !1 } else { h | 1 };
chain.push(val);
if i64::from(bucket) != prev_bucket {
let idx = u32::try_from(symoffset + k).unwrap_or(u32::MAX);
if let Some(b) = buckets.get_mut(bucket as usize) {
*b = idx;
}
prev_bucket = i64::from(bucket);
}
}
let mut bytes = Vec::with_capacity(
16 + 8 * mask_words as usize + 4 * n_buckets as usize + 4 * hb.len(),
);
push_u32(&mut bytes, order.n_buckets);
push_u32(&mut bytes, order.symoffset);
push_u32(&mut bytes, order.mask_words);
push_u32(&mut bytes, order.bloom_shift);
for w in &bloom {
bytes.extend_from_slice(&w.to_le_bytes());
}
for b in &buckets {
push_u32(&mut bytes, *b);
}
for c in &chain {
push_u32(&mut bytes, *c);
}
bytes
}
#[allow(clippy::cast_possible_truncation)]
fn dl_new_hash(name: &[u8]) -> u32 {
let mut h: u32 = 5381;
for &c in name {
h = h.wrapping_shl(5).wrapping_add(h).wrapping_add(u32::from(c));
}
h
}
#[allow(clippy::cast_possible_truncation)]
fn elf_hash(name: &[u8]) -> u32 {
let mut h: u32 = 0;
for &c in name {
h = h.wrapping_shl(4).wrapping_add(u32::from(c));
let g = h & 0xf000_0000;
if g != 0 {
h ^= g >> 24;
}
h &= !g;
}
h
}