1use core::mem;
2
3use crate::elf;
4use crate::read::{ReadError, ReadRef, Result};
5use crate::{U32, U64};
6
7use 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)]
13pub struct HashTable<'data, Elf: FileHeader> {
14 buckets: &'data [U32<Elf::Endian>],
15 chains: &'data [U32<Elf::Endian>],
16}
17
18impl<'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)]
78pub 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
86impl<'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