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