use core::mem; use crate::elf; use crate::read::{ReadError, ReadRef, Result}; use crate::{U32, U64}; use super::{FileHeader, Sym, SymbolTable, Version, VersionTable}; /// A SysV symbol hash table in an ELF file. #[derive(Debug)] pub struct HashTable<'data, Elf: FileHeader> { buckets: &'data [U32], chains: &'data [U32], } impl<'data, Elf: FileHeader> HashTable<'data, Elf> { /// Parse a SysV hash table. /// /// `data` should be from a `SHT_HASH` section, or from a /// segment pointed to via the `DT_HASH` entry. /// /// The header is read at offset 0 in the given `data`. pub fn parse(endian: Elf::Endian, data: &'data [u8]) -> Result { let mut offset = 0; let header = data .read::>(&mut offset) .read_error("Invalid hash header")?; let buckets = data .read_slice(&mut offset, header.bucket_count.get(endian) as usize) .read_error("Invalid hash buckets")?; let chains = data .read_slice(&mut offset, header.chain_count.get(endian) as usize) .read_error("Invalid hash chains")?; Ok(HashTable { buckets, chains }) } /// Return the symbol table length. pub fn symbol_table_length(&self) -> u32 { self.chains.len() as u32 } /// Use the hash table to find the symbol table entry with the given name, hash and version. pub fn find>( &self, endian: Elf::Endian, name: &[u8], hash: u32, version: Option<&Version>, symbols: &SymbolTable<'data, Elf, R>, versions: &VersionTable<'data, Elf>, ) -> Option<(usize, &'data Elf::Sym)> { // Get the chain start from the bucket for this hash. let mut index = self.buckets[(hash as usize) % self.buckets.len()].get(endian) as usize; // Avoid infinite loop. let mut i = 0; let strings = symbols.strings(); while index != 0 && i < self.chains.len() { if let Ok(symbol) = symbols.symbol(index) { if symbol.name(endian, strings) == Ok(name) && versions.matches(endian, index, version) { return Some((index, symbol)); } } index = self.chains.get(index)?.get(endian) as usize; i += 1; } None } } /// A GNU symbol hash table in an ELF file. #[derive(Debug)] pub struct GnuHashTable<'data, Elf: FileHeader> { symbol_base: u32, bloom_shift: u32, bloom_filters: &'data [u8], buckets: &'data [U32], values: &'data [U32], } impl<'data, Elf: FileHeader> GnuHashTable<'data, Elf> { /// Parse a GNU hash table. /// /// `data` should be from a `SHT_GNU_HASH` section, or from a /// segment pointed to via the `DT_GNU_HASH` entry. /// /// The header is read at offset 0 in the given `data`. /// /// The header does not contain a length field, and so all of `data` /// will be used as the hash table values. It does not matter if this /// is longer than needed, and this will often the case when accessing /// the hash table via the `DT_GNU_HASH` entry. pub fn parse(endian: Elf::Endian, data: &'data [u8]) -> Result { let mut offset = 0; let header = data .read::>(&mut offset) .read_error("Invalid GNU hash header")?; let bloom_len = u64::from(header.bloom_count.get(endian)) * mem::size_of::() as u64; let bloom_filters = data .read_bytes(&mut offset, bloom_len) .read_error("Invalid GNU hash bloom filters")?; let buckets = data .read_slice(&mut offset, header.bucket_count.get(endian) as usize) .read_error("Invalid GNU hash buckets")?; let chain_count = (data.len() - offset as usize) / 4; let values = data .read_slice(&mut offset, chain_count) .read_error("Invalid GNU hash values")?; Ok(GnuHashTable { symbol_base: header.symbol_base.get(endian), bloom_shift: header.bloom_shift.get(endian), bloom_filters, buckets, values, }) } /// Return the symbol table index of the first symbol in the hash table. pub fn symbol_base(&self) -> u32 { self.symbol_base } /// Determine the symbol table length by finding the last entry in the hash table. /// /// Returns `None` if the hash table is empty or invalid. pub fn symbol_table_length(&self, endian: Elf::Endian) -> Option { // Ensure we find a non-empty bucket. if self.symbol_base == 0 { return None; } // Find the highest chain index in a bucket. let mut max_symbol = 0; for bucket in self.buckets { let bucket = bucket.get(endian); if max_symbol < bucket { max_symbol = bucket; } } // Find the end of the chain. for value in self .values .get(max_symbol.checked_sub(self.symbol_base)? as usize..)? { max_symbol += 1; if value.get(endian) & 1 != 0 { return Some(max_symbol); } } None } /// Use the hash table to find the symbol table entry with the given name, hash, and version. pub fn find>( &self, endian: Elf::Endian, name: &[u8], hash: u32, version: Option<&Version>, symbols: &SymbolTable<'data, Elf, R>, versions: &VersionTable<'data, Elf>, ) -> Option<(usize, &'data Elf::Sym)> { let word_bits = mem::size_of::() as u32 * 8; // Test against bloom filter. let bloom_count = self.bloom_filters.len() / mem::size_of::(); let offset = ((hash / word_bits) & (bloom_count as u32 - 1)) * mem::size_of::() as u32; let filter = if word_bits == 64 { self.bloom_filters .read_at::>(offset.into()) .ok()? .get(endian) } else { self.bloom_filters .read_at::>(offset.into()) .ok()? .get(endian) .into() }; if filter & (1 << (hash % word_bits)) == 0 { return None; } if filter & (1 << ((hash >> self.bloom_shift) % word_bits)) == 0 { return None; } // Get the chain start from the bucket for this hash. let mut index = self.buckets[(hash as usize) % self.buckets.len()].get(endian) as usize; if index == 0 { return None; } // Test symbols in the chain. let strings = symbols.strings(); let symbols = symbols.symbols().get(index..)?; let values = self .values .get(index.checked_sub(self.symbol_base as usize)?..)?; for (symbol, value) in symbols.iter().zip(values.iter()) { let value = value.get(endian); if value | 1 == hash | 1 { if symbol.name(endian, strings) == Ok(name) && versions.matches(endian, index, version) { return Some((index, symbol)); } } if value & 1 != 0 { break; } index += 1; } None } }