goblin/elf/gnu_hash.rs
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220
//! A Gnu Hash table as 4 sections:
//!
//! 1. Header
//! 2. Bloom Filter
//! 3. Hash Buckets
//! 4. Chains
//!
//! The header has is an array of four `u32`s:
//!
//! 1. nbuckets
//! 2. symndx
//! 3. maskwords
//! 4. shift2
//!
//! See more:
//! * <http://www.linker-aliens.org/blogs/ali/entry/gnu_hash_elf_sections>
//! or <https://blogs.oracle.com/solaris/gnu-hash-elf-sections-v2>
//! * <https://flapenguin.me/2017/05/10/elf-lookup-dt-gnu-hash/>
/// GNU hash function: accepts a symbol name and returns a value that may be
/// used to compute a bucket index.
///
/// Consequently, if the hashing function returns the value `x` for some name,
/// `buckets[x % nbuckets]` gives an index, `y`, into both the symbol table
/// and the chain table.
pub fn hash(symbol: &str) -> u32 {
const HASH_SEED: u32 = 5381;
symbol.bytes().fold(HASH_SEED, |hash, b| {
hash.wrapping_mul(33).wrapping_add(u32::from(b))
})
}
#[cfg(test)]
mod tests {
use super::hash;
#[test]
fn test_hash() {
assert_eq!(hash(""), 0x0000_1505);
assert_eq!(hash("printf"), 0x156b_2bb8);
assert_eq!(hash("exit"), 0x7c96_7e3f);
assert_eq!(hash("syscall"), 0xbac2_12a0);
assert_eq!(hash("flapenguin.me"), 0x8ae9_f18e);
}
}
macro_rules! elf_gnu_hash_impl {
($IntTy:ty) => {
use crate::elf::sym::Sym;
use crate::strtab::Strtab;
use core::fmt;
use core::mem;
use core::slice;
const INT_SIZE: usize = mem::size_of::<$IntTy>();
const U32_SIZE: usize = mem::size_of::<u32>();
/// Size of a bits mask in bloom filter
const ELFCLASS_BITS: u32 = INT_SIZE as u32 * 8;
/// A better hash table for the ELF used by GNU systems in GNU-compatible software.
pub struct GnuHash<'a> {
/// Index of the first symbol in the `.dynsym` table which is accessible with
/// the hash table
symindex: u32,
/// Shift count used in the bloom filter
shift2: u32,
/// 2 bit bloom filter on `chains`
// Either 32 or 64-bit depending on the class of object
bloom_filter: &'a [$IntTy],
/// GNU hash table bucket array; indexes start at 0. This array holds symbol
/// table indexes and contains the index of hashes in `chains`
buckets: &'a [u32],
/// Hash values; indexes start at 0. This array holds symbol table indexes.
chains: &'a [u32], // => chains[dynsyms.len() - symindex]
dynsyms: &'a [Sym],
}
impl fmt::Debug for GnuHash<'_> {
fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
f.debug_struct("GnuHash")
.field("nbuckets", &self.buckets.len())
.field("symindex", &self.symindex)
.field("maskwords", &(self.bloom_filter.len() - 1))
.field("shift2", &self.shift2)
.field("bloom_filter", &self.bloom_filter.as_ptr())
.field("bucket", &self.buckets.as_ptr())
.field("chains", &self.chains.as_ptr())
.finish()
}
}
impl<'a> GnuHash<'a> {
/// Initialize a GnuHash from a pointer to `.hash` (or `.gnu.hash`) section
/// and total number of dynamic symbols.
/// # Safety
///
/// This function creates a `GnuHash` directly from a raw pointer
pub unsafe fn from_raw_table(
hashtab: &'a [u8],
dynsyms: &'a [Sym],
) -> Result<Self, &'static str> {
if hashtab.as_ptr() as usize % INT_SIZE != 0 {
return Err("hashtab is not aligned with 64-bit");
}
if hashtab.len() <= 16 {
return Err("failed to read in number of buckets");
}
let [nbuckets, symindex, maskwords, shift2] =
(hashtab.as_ptr() as *const u32 as *const [u32; 4]).read();
if !maskwords.is_power_of_two() {
return Err("maskwords must be a power of two");
}
let hashtab = &hashtab[16..];
{
// SAFETY: Condition to check for an overflow
// size_of(chains) + size_of(buckets) + size_of(bloom_filter) == size_of(hashtab)
if dynsyms.len() <= symindex as usize {
return Err("symindex must be smaller than dynsyms.len()");
}
let chains_size = (dynsyms.len() - symindex as usize).checked_mul(U32_SIZE);
let buckets_size = (nbuckets as usize).checked_mul(U32_SIZE);
let bloom_size = (maskwords as usize).checked_mul(INT_SIZE);
let total_size = match (chains_size, buckets_size, bloom_size) {
(Some(a), Some(b), Some(c)) => {
a.checked_add(b).and_then(|t| t.checked_add(c))
}
_ => None,
};
match total_size {
Some(size) if size == hashtab.len() => {}
_ => return Err("index out of bound or non-complete hash section"),
}
}
let bloom_filter_ptr = hashtab.as_ptr() as *const $IntTy;
let buckets_ptr = bloom_filter_ptr.add(maskwords as usize) as *const u32;
let chains_ptr = buckets_ptr.add(nbuckets as usize);
let bloom_filter = slice::from_raw_parts(bloom_filter_ptr, maskwords as usize);
let buckets = slice::from_raw_parts(buckets_ptr, nbuckets as usize);
let chains = slice::from_raw_parts(chains_ptr, dynsyms.len() - symindex as usize);
Ok(Self {
symindex,
shift2,
bloom_filter,
buckets,
chains,
dynsyms,
})
}
/// Locate the hash chain, and corresponding hash value element.
#[cold]
fn lookup(&self, symbol: &str, hash: u32, dynstrtab: &Strtab) -> Option<&'a Sym> {
const MASK_LOWEST_BIT: u32 = 0xffff_fffe;
let bucket = self.buckets[hash as usize % self.buckets.len()];
// Empty hash chain, symbol not present
if bucket < self.symindex {
return None;
}
// Walk the chain until the symbol is found or the chain is exhausted.
let chain_idx = bucket - self.symindex;
let hash = hash & MASK_LOWEST_BIT;
let chains = &self.chains.get((chain_idx as usize)..)?;
let dynsyms = &self.dynsyms.get((bucket as usize)..)?;
for (hash2, symb) in chains.iter().zip(dynsyms.iter()) {
if (hash == (hash2 & MASK_LOWEST_BIT))
&& (symbol == &dynstrtab[symb.st_name as usize])
{
return Some(symb);
}
// Chain ends with an element with the lowest bit set to 1.
if hash2 & 1 == 1 {
break;
}
}
None
}
/// Check if symbol maybe is in the hash table, or definitely not in it.
#[inline]
fn check_maybe_match(&self, hash: u32) -> bool {
const MASK: u32 = ELFCLASS_BITS - 1;
let hash2 = hash >> self.shift2;
// `x & (N - 1)` is equivalent to `x % N` iff `N = 2^y`.
let bitmask: $IntTy = 1 << (hash & (MASK)) | 1 << (hash2 & MASK);
let bloom_idx = (hash / ELFCLASS_BITS) & (self.bloom_filter.len() as u32 - 1);
let bitmask_word = self.bloom_filter[bloom_idx as usize];
(bitmask_word & bitmask) == bitmask
}
/// Given a symbol, a hash of that symbol, a dynamic string table and
/// a `dynstrtab` to cross-reference names, maybe returns a Sym.
pub fn find(&self, symbol: &str, dynstrtab: &Strtab) -> Option<&'a Sym> {
let hash = self::hash(symbol);
self.find_with_hash(symbol, hash, dynstrtab)
}
/// This function will not check if the passed `hash` is really
/// the hash of `symbol`
pub fn find_with_hash(
&self,
symbol: &str,
hash: u32,
dynstrtab: &Strtab,
) -> Option<&'a Sym> {
if self.check_maybe_match(hash) {
self.lookup(symbol, hash, dynstrtab)
} else {
None
}
}
}
};
}