1 use core::mem; 2 3 use crate::elf; 4 use crate::read::{ReadError, ReadRef, Result}; 5 use crate::{U32, U64}; 6 7 use super::{FileHeader, Sym, SymbolTable}; 8 9 /// A SysV symbol hash table in an ELF file. 10 #[derive(Debug)] 11 pub struct HashTable<'data, Elf: FileHeader> { 12 buckets: &'data [U32<Elf::Endian>], 13 chains: &'data [U32<Elf::Endian>], 14 } 15 16 impl<'data, Elf: FileHeader> HashTable<'data, Elf> { 17 /// Parse a SysV hash table. 18 /// 19 /// `data` should be from a `SHT_HASH` section, or from a 20 /// segment pointed to via the `DT_HASH` entry. 21 /// 22 /// The header is read at offset 0 in the given `data`. parse(endian: Elf::Endian, data: &'data [u8]) -> Result<Self>23 pub fn parse(endian: Elf::Endian, data: &'data [u8]) -> Result<Self> { 24 let mut offset = 0; 25 let header = data 26 .read::<elf::HashHeader<Elf::Endian>>(&mut offset) 27 .read_error("Invalid hash header")?; 28 let buckets = data 29 .read_slice(&mut offset, header.bucket_count.get(endian) as usize) 30 .read_error("Invalid hash buckets")?; 31 let chains = data 32 .read_slice(&mut offset, header.chain_count.get(endian) as usize) 33 .read_error("Invalid hash chains")?; 34 Ok(HashTable { buckets, chains }) 35 } 36 37 /// Return the symbol table length. symbol_table_length(&self) -> u3238 pub fn symbol_table_length(&self) -> u32 { 39 self.chains.len() as u32 40 } 41 42 /// Use the hash table to find the symbol table entry with the given name and hash. find<R: ReadRef<'data>>( &self, endian: Elf::Endian, name: &[u8], hash: u32, symbols: &SymbolTable<'data, Elf, R>, ) -> Option<&'data Elf::Sym>43 pub fn find<R: ReadRef<'data>>( 44 &self, 45 endian: Elf::Endian, 46 name: &[u8], 47 hash: u32, 48 symbols: &SymbolTable<'data, Elf, R>, 49 ) -> Option<&'data Elf::Sym> { 50 // Get the chain start from the bucket for this hash. 51 let mut index = self.buckets[(hash as usize) % self.buckets.len()].get(endian) as usize; 52 // Avoid infinite loop. 53 let mut i = 0; 54 let strings = symbols.strings(); 55 while index != 0 && i < self.chains.len() { 56 if let Ok(symbol) = symbols.symbol(index) { 57 if symbol.name(endian, strings) == Ok(name) { 58 return Some(symbol); 59 } 60 } 61 index = self.chains.get(index)?.get(endian) as usize; 62 i += 1; 63 } 64 None 65 } 66 } 67 68 /// A GNU symbol hash table in an ELF file. 69 #[derive(Debug)] 70 pub struct GnuHashTable<'data, Elf: FileHeader> { 71 symbol_base: u32, 72 bloom_shift: u32, 73 bloom_filters: &'data [u8], 74 buckets: &'data [U32<Elf::Endian>], 75 values: &'data [U32<Elf::Endian>], 76 } 77 78 impl<'data, Elf: FileHeader> GnuHashTable<'data, Elf> { 79 /// Parse a GNU hash table. 80 /// 81 /// `data` should be from a `SHT_GNU_HASH` section, or from a 82 /// segment pointed to via the `DT_GNU_HASH` entry. 83 /// 84 /// The header is read at offset 0 in the given `data`. 85 /// 86 /// The header does not contain a length field, and so all of `data` 87 /// will be used as the hash table values. It does not matter if this 88 /// is longer than needed, and this will often the case when accessing 89 /// the hash table via the `DT_GNU_HASH` entry. parse(endian: Elf::Endian, data: &'data [u8]) -> Result<Self>90 pub fn parse(endian: Elf::Endian, data: &'data [u8]) -> Result<Self> { 91 let mut offset = 0; 92 let header = data 93 .read::<elf::GnuHashHeader<Elf::Endian>>(&mut offset) 94 .read_error("Invalid GNU hash header")?; 95 let bloom_len = 96 u64::from(header.bloom_count.get(endian)) * mem::size_of::<Elf::Word>() as u64; 97 let bloom_filters = data 98 .read_bytes(&mut offset, bloom_len) 99 .read_error("Invalid GNU hash bloom filters")?; 100 let buckets = data 101 .read_slice(&mut offset, header.bucket_count.get(endian) as usize) 102 .read_error("Invalid GNU hash buckets")?; 103 let chain_count = (data.len() - offset as usize) / 4; 104 let values = data 105 .read_slice(&mut offset, chain_count) 106 .read_error("Invalid GNU hash values")?; 107 Ok(GnuHashTable { 108 symbol_base: header.symbol_base.get(endian), 109 bloom_shift: header.bloom_shift.get(endian), 110 bloom_filters, 111 buckets, 112 values, 113 }) 114 } 115 116 /// Return the symbol table index of the first symbol in the hash table. symbol_base(&self) -> u32117 pub fn symbol_base(&self) -> u32 { 118 self.symbol_base 119 } 120 121 /// Determine the symbol table length by finding the last entry in the hash table. 122 /// 123 /// Returns `None` if the hash table is empty or invalid. symbol_table_length(&self, endian: Elf::Endian) -> Option<u32>124 pub fn symbol_table_length(&self, endian: Elf::Endian) -> Option<u32> { 125 // Ensure we find a non-empty bucket. 126 if self.symbol_base == 0 { 127 return None; 128 } 129 130 // Find the highest chain index in a bucket. 131 let mut max_symbol = 0; 132 for bucket in self.buckets { 133 let bucket = bucket.get(endian); 134 if max_symbol < bucket { 135 max_symbol = bucket; 136 } 137 } 138 139 // Find the end of the chain. 140 for value in self 141 .values 142 .get(max_symbol.checked_sub(self.symbol_base)? as usize..)? 143 { 144 max_symbol += 1; 145 if value.get(endian) & 1 != 0 { 146 return Some(max_symbol); 147 } 148 } 149 150 None 151 } 152 153 /// Use the hash table to find the symbol table entry with the given name and hash. find<R: ReadRef<'data>>( &self, endian: Elf::Endian, name: &[u8], hash: u32, symbols: &SymbolTable<'data, Elf, R>, ) -> Option<&'data Elf::Sym>154 pub fn find<R: ReadRef<'data>>( 155 &self, 156 endian: Elf::Endian, 157 name: &[u8], 158 hash: u32, 159 symbols: &SymbolTable<'data, Elf, R>, 160 ) -> Option<&'data Elf::Sym> { 161 let word_bits = mem::size_of::<Elf::Word>() as u32 * 8; 162 163 // Test against bloom filter. 164 let bloom_count = self.bloom_filters.len() / mem::size_of::<Elf::Word>(); 165 let offset = 166 ((hash / word_bits) & (bloom_count as u32 - 1)) * mem::size_of::<Elf::Word>() as u32; 167 let filter = if word_bits == 64 { 168 self.bloom_filters 169 .read_at::<U64<Elf::Endian>>(offset.into()) 170 .ok()? 171 .get(endian) 172 } else { 173 self.bloom_filters 174 .read_at::<U32<Elf::Endian>>(offset.into()) 175 .ok()? 176 .get(endian) 177 .into() 178 }; 179 if filter & (1 << (hash % word_bits)) == 0 { 180 return None; 181 } 182 if filter & (1 << ((hash >> self.bloom_shift) % word_bits)) == 0 { 183 return None; 184 } 185 186 // Get the chain start from the bucket for this hash. 187 let index = self.buckets[(hash as usize) % self.buckets.len()].get(endian) as usize; 188 if index == 0 { 189 return None; 190 } 191 192 // Test symbols in the chain. 193 let strings = symbols.strings(); 194 let symbols = symbols.symbols().get(index..)?; 195 let values = self 196 .values 197 .get(index.checked_sub(self.symbol_base as usize)?..)?; 198 for (symbol, value) in symbols.iter().zip(values.iter()) { 199 let value = value.get(endian); 200 if value | 1 == hash | 1 { 201 if symbol.name(endian, strings) == Ok(name) { 202 return Some(symbol); 203 } 204 } 205 if value & 1 != 0 { 206 break; 207 } 208 } 209 None 210 } 211 } 212