use std::hash::{BuildHasher, Hasher};
use hashbrown::HashTable;
use rustc_hash::FxBuildHasher;
mod bulk;
use crate::{
elf::constants::{
STB_GNU_UNIQUE, STB_WEAK, STT_NOTYPE, STT_TLS, STV_DEFAULT, STV_HIDDEN,
STV_PROTECTED,
},
error::{Error, Result},
input::InputSymbol,
};
#[derive(Copy, Clone, Eq, PartialEq, Hash, Debug)]
pub struct SymbolId(pub usize);
#[derive(Copy, Clone, Eq, PartialEq, Debug)]
enum Class {
DefinedStrong,
DefinedWeak,
Common,
UndefStrong,
UndefWeak,
}
impl Class {
const fn rank(self) -> u8 {
match self {
Self::DefinedStrong => 1,
Self::Common => 2,
Self::DefinedWeak => 3,
Self::UndefStrong => 4,
Self::UndefWeak => 5,
}
}
}
#[derive(Clone, Debug)]
pub enum DefSource {
Section { index: u16, offset: u64 },
Absolute { value: u64 },
}
#[derive(Clone, Debug)]
pub struct Definition {
pub weak: bool,
pub unique: bool,
pub file: usize,
pub source: DefSource,
pub size: u64,
pub sym_type: u8,
}
#[derive(Clone, Debug)]
pub enum SymbolKind {
Undefined { weak: bool },
Defined(Definition),
Common { weak: bool, size: u64, align: u64 },
}
impl SymbolKind {
fn class(&self) -> Class {
match self {
Self::Defined(d) if d.weak || d.unique => Class::DefinedWeak,
Self::Defined(_) => Class::DefinedStrong,
Self::Common { .. } => Class::Common,
Self::Undefined { weak: true } => Class::UndefWeak,
Self::Undefined { .. } => Class::UndefStrong,
}
}
fn from_input(inc: &InputSymbol, file: usize) -> Self {
if inc.is_undefined() {
return Self::Undefined {
weak: inc.binding == STB_WEAK,
};
}
if inc.is_common() {
return Self::Common {
weak: inc.binding == STB_WEAK,
size: inc.size,
align: inc.value,
};
}
let source = if inc.is_absolute() {
DefSource::Absolute { value: inc.value }
} else {
DefSource::Section {
index: inc.shndx,
offset: inc.value,
}
};
Self::Defined(Definition {
weak: inc.binding == STB_WEAK,
unique: inc.binding == STB_GNU_UNIQUE,
file,
source,
size: inc.size,
sym_type: inc.type_,
})
}
}
fn input_class(inc: &InputSymbol) -> Class {
if inc.is_undefined() {
if inc.binding == STB_WEAK {
Class::UndefWeak
} else {
Class::UndefStrong
}
} else if inc.is_common() {
Class::Common
} else if ranks_weak(inc.binding) {
Class::DefinedWeak
} else {
Class::DefinedStrong
}
}
fn ranks_weak(binding: u8) -> bool {
binding == STB_WEAK || binding == STB_GNU_UNIQUE
}
#[derive(Clone, Debug)]
pub struct Symbol {
pub kind: SymbolKind,
pub visibility: u8,
}
impl Symbol {
pub fn is_preemptible(&self, shared: bool) -> bool {
if self.visibility != STV_DEFAULT {
return false;
}
if !matches!(
self.kind,
SymbolKind::Defined(_) | SymbolKind::Common { .. }
) {
return true;
}
shared
}
pub fn is_absolute_value(&self) -> bool {
match &self.kind {
SymbolKind::Defined(def) => {
def.sym_type == STT_TLS
|| matches!(def.source, DefSource::Absolute { .. })
}
SymbolKind::Common { .. } => false,
SymbolKind::Undefined { .. } => true,
}
}
fn from_input(inc: &InputSymbol, file: usize) -> Self {
Self {
kind: SymbolKind::from_input(inc, file),
visibility: inc.visibility,
}
}
}
pub const fn exports_to_dynsym(vis: u8) -> bool {
matches!(vis, STV_DEFAULT | STV_PROTECTED)
}
const fn merge_visibility(current: u8, incoming: u8) -> u8 {
if incoming == STV_DEFAULT {
return current;
}
if current == STV_DEFAULT {
return incoming;
}
if incoming < current {
incoming
} else {
current
}
}
pub(crate) const SHARDS: usize = 64;
pub struct SymbolTable<'data> {
names: Vec<NameRef<'data>>,
index: Vec<HashTable<SymbolId>>,
symbols: Vec<Symbol>,
}
impl Default for SymbolTable<'_> {
fn default() -> Self {
Self {
names: Vec::new(),
index: (0..SHARDS).map(|_| HashTable::new()).collect(),
symbols: Vec::new(),
}
}
}
#[allow(clippy::cast_possible_truncation)]
pub(crate) const fn shard_of(hash: u64) -> usize {
(hash as usize) & (SHARDS - 1)
}
pub(crate) fn partition_file(
syms: &mut Vec<InputSymbol<'_>>,
) -> Vec<(u32, u32)> {
bulk::partition_file(syms)
}
pub fn name_hash(name: &[u8]) -> u64 {
let mut h = FxBuildHasher.build_hasher();
h.write(name);
h.finish()
}
pub fn version_stem(name: &[u8]) -> &[u8] {
match name.iter().position(|&b| b == b'@') {
Some(0) | None => name,
Some(pos) => &name[..pos],
}
}
enum NameRef<'data> {
Slice(&'data [u8]),
Owned(Box<[u8]>),
}
impl NameRef<'_> {
fn bytes(&self) -> &[u8] {
match self {
Self::Slice(s) => s,
Self::Owned(o) => o,
}
}
}
fn arena_name<'a>(names: &'a [NameRef<'_>], id: SymbolId) -> &'a [u8] {
names.get(id.0).map(NameRef::bytes).unwrap_or_default()
}
impl<'data> SymbolTable<'data> {
pub fn new() -> Self {
Self::default()
}
pub fn reserve(&mut self, count: usize) {
let Self {
names,
index,
symbols,
} = self;
let per_shard = count.div_ceil(SHARDS);
for shard in index.iter_mut() {
shard.reserve(per_shard, |&id| name_hash(arena_name(names, id)));
}
symbols.reserve(count);
names.reserve(count);
}
pub fn intern_all(
&mut self,
files: &[Vec<InputSymbol<'data>>],
bins: &[Vec<(u32, u32)>],
) -> Result<Vec<Vec<Option<SymbolId>>>> {
bulk::intern_all(self, files, bins)
}
pub fn len(&self) -> usize {
self.symbols.len()
}
pub fn is_empty(&self) -> bool {
self.symbols.is_empty()
}
pub fn intern(
&mut self,
inc: &InputSymbol<'_>,
file: usize,
) -> Result<SymbolId> {
let hash = inc.name_hash;
let Self {
names,
index,
symbols,
} = self;
let Some(shard) = index.get_mut(shard_of(hash)) else {
return Err(Error::OutOfRange("symbol shard"));
};
if let Some(&id) =
shard.find(hash, |&other| arena_name(names, other) == inc.name)
{
let sym = symbols
.get_mut(id.0)
.ok_or(Error::OutOfRange("symbol arena index"))?;
merge_symbol(sym, inc, file)?;
return Ok(id);
}
let id = SymbolId(symbols.len());
names.push(NameRef::Owned(inc.name.into()));
shard.insert_unique(hash, id, |&other| {
name_hash(arena_name(names, other))
});
symbols.push(Symbol::from_input(inc, file));
Ok(id)
}
pub fn name(&self, id: SymbolId) -> &[u8] {
arena_name(&self.names, id)
}
pub fn ids(&self) -> impl Iterator<Item = SymbolId> {
(0..self.symbols.len()).map(SymbolId)
}
pub fn entries(&self) -> impl Iterator<Item = (&[u8], &Symbol)> {
self.ids()
.filter_map(move |id| Some((self.name(id), self.symbol(id)?)))
}
pub fn find(&self, name: &[u8]) -> Option<SymbolId> {
let hash = name_hash(name);
self.index
.get(shard_of(hash))?
.find(hash, |&id| arena_name(&self.names, id) == name)
.copied()
}
pub fn symbol(&self, id: SymbolId) -> Option<&Symbol> {
self.symbols.get(id.0)
}
pub fn hide(&mut self, id: SymbolId) {
if let Some(sym) = self.symbols.get_mut(id.0) {
sym.visibility = STV_HIDDEN;
}
}
pub fn define_absolute(
&mut self,
id: SymbolId,
sym_type: u8,
visibility: u8,
) -> bool {
let Some(sym) = self.symbols.get_mut(id.0) else {
return false;
};
if !matches!(sym.kind, SymbolKind::Undefined { .. }) {
return false;
}
sym.visibility = merge_visibility(sym.visibility, visibility);
sym.kind = SymbolKind::Defined(Definition {
weak: false,
unique: false,
file: 0,
source: DefSource::Absolute { value: 0 },
size: 0,
sym_type,
});
true
}
}
fn merge_symbol(
existing: &mut Symbol,
inc: &InputSymbol,
file: usize,
) -> Result<()> {
existing.visibility = merge_visibility(existing.visibility, inc.visibility);
check_tls_mismatch(existing, inc)?;
merge_kind(&mut existing.kind, inc, file)
}
fn check_tls_mismatch(existing: &Symbol, inc: &InputSymbol) -> Result<()> {
let tls = matches!(
&existing.kind,
SymbolKind::Defined(def) if def.sym_type == STT_TLS
);
if tls && inc.type_ != STT_TLS && inc.type_ != STT_NOTYPE {
return Err(Error::TlsMismatch(
String::from_utf8_lossy(inc.name).into_owned(),
));
}
Ok(())
}
fn merge_kind(
existing: &mut SymbolKind,
inc: &InputSymbol,
file: usize,
) -> Result<()> {
let prev = existing.class();
let next = input_class(inc);
match (prev, next) {
(Class::DefinedStrong, Class::DefinedStrong)
if defining_file(existing) == file && same_place(existing, inc) =>
{
Ok(())
}
(Class::DefinedStrong, Class::DefinedStrong)
if same_absolute_value(existing, inc) =>
{
Ok(())
}
(Class::DefinedStrong, Class::DefinedStrong) => {
Err(Error::duplicate_symbol(
String::from_utf8_lossy(inc.name).into_owned(),
defining_file(existing).to_string(),
file.to_string(),
))
}
(Class::Common, Class::Common) => {
merge_common(existing, inc);
Ok(())
}
(_, _) if next.rank() < prev.rank() => {
*existing = SymbolKind::from_input(inc, file);
Ok(())
}
_ => Ok(()),
}
}
fn merge_common(existing: &mut SymbolKind, inc: &InputSymbol) {
if let SymbolKind::Common { size, align, .. } = existing {
if inc.size > *size {
*size = inc.size;
}
if inc.value > *align {
*align = inc.value;
}
}
}
fn defining_file(kind: &SymbolKind) -> usize {
match kind {
SymbolKind::Defined(def) => def.file,
SymbolKind::Common { .. } | SymbolKind::Undefined { .. } => usize::MAX,
}
}
fn same_place(existing: &SymbolKind, inc: &InputSymbol) -> bool {
let SymbolKind::Defined(def) = existing else {
return false;
};
match def.source {
DefSource::Section { index, offset } => {
!inc.is_absolute() && index == inc.shndx && offset == inc.value
}
DefSource::Absolute { value } => {
inc.is_absolute() && value == inc.value
}
}
}
fn same_absolute_value(existing: &SymbolKind, inc: &InputSymbol) -> bool {
let SymbolKind::Defined(Definition {
source: DefSource::Absolute { value },
..
}) = existing
else {
return false;
};
inc.is_absolute() && inc.value == *value
}