vendor/goblin/src/elf/gnu_hash.rs

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