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
}
}
}
};
}
|
