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
//! A Gnu Hash table as 4 sections:
//!
//! 1. Header
//! 2. Bloom Filter
//! 3. Hash Buckets
//! 4. Hash Values
//!
//! The header has is an array of four (4) u32s:
//!
//! 1. nbuckets
//! 2. symndx
//! 3. maskwords
//! 4. shift2
//!
//! See: https://blogs.oracle.com/solaris/gnu-hash-elf-sections-v2
/// GNU hash function: takes a string and returns the u32 hash of that string
pub fn hash(symbol: &str) -> u32 {
const HASH_SEED: u32 = 5381;
let mut hash = HASH_SEED;
for b in symbol.as_bytes() {
hash = hash
.wrapping_mul(33)
.wrapping_add(u32::from(*b));
}
hash
}
#[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 {
($size:ty) => {
use core::slice;
use core::mem;
use crate::strtab::Strtab;
use super::sym;
pub struct GnuHash<'process> {
nbuckets: u32,
symindex: usize,
shift2: u32,
maskbits: u32,
bloomwords: &'process [$size], // either 32 or 64 bit masks, depending on platform
maskwords_bitmask: u32,
buckets: &'process [u32],
hashvalues: &'process [u32],
symtab: &'process [sym::Sym],
}
impl<'process> GnuHash<'process> {
pub unsafe fn new(hashtab: *const u32, total_dynsyms: usize, symtab: &'process [sym::Sym]) -> GnuHash<'process> {
let nbuckets = *hashtab;
let symindex = *hashtab.add(1) as usize;
let maskwords = *hashtab.add(2) as usize; // how many words our bloom filter mask has
let shift2 = *hashtab.add(3);
let bloomwords_ptr = hashtab.add(4) as *const $size;
let buckets_ptr = bloomwords_ptr.add(maskwords) as *const u32;
let buckets = slice::from_raw_parts(buckets_ptr, nbuckets as usize);
let hashvalues_ptr = buckets_ptr.add(nbuckets as usize);
let hashvalues = slice::from_raw_parts(hashvalues_ptr, total_dynsyms - symindex);
let bloomwords = slice::from_raw_parts(bloomwords_ptr, maskwords);
GnuHash {
nbuckets,
symindex,
shift2,
maskbits: mem::size_of::<usize>() as u32,
bloomwords,
hashvalues,
buckets,
maskwords_bitmask: ((maskwords as i32) - 1) as u32,
symtab,
}
}
#[inline(always)]
fn lookup(&self,
symbol: &str,
hash: u32,
strtab: &Strtab)
-> Option<&sym::Sym> {
let mut idx = self.buckets[(hash % self.nbuckets) as usize] as usize;
// println!("lookup idx = buckets[hash % nbuckets] = {}", idx);
if idx == 0 {
return None;
}
let mut hash_idx = idx - self.symindex;
let hash = hash & !1;
// TODO: replace this with an iterator
loop {
let symbol_ = &self.symtab[idx];
let h2 = self.hashvalues[hash_idx];
idx += 1;
hash_idx += 1;
let name = &strtab[symbol_.st_name as usize];
// println!("{}: h2 0x{:x} resolves to: {}", i, h2, name);
if hash == (h2 & !1) && name == symbol {
// println!("lookup match for {} at: 0x{:x}", symbol, symbol_.st_value);
return Some(symbol_);
}
if h2 & 1 == 1 {
break;
} // end of chain
}
None
}
#[inline(always)]
fn filter(&self, hash: u32) -> bool {
let bloom_idx = (hash / self.maskbits) & self.maskwords_bitmask;
let h2 = hash >> self.shift2;
let bitmask = (1u64 << (hash % self.maskbits)) | (1u64 << (h2 % self.maskbits));
// println!("lookup: maskwords: {} bloom_idx: {} bitmask: {} shift2: {}", self.maskwords, bloom_idx, bitmask, self.shift2);
let filter = self.bloomwords[bloom_idx as usize] as usize; // FIXME: verify this is safe ;)
filter & (bitmask as usize) != (bitmask as usize) // if true, def _don't have_
}
/// Given a name, a hash of that name, a strtab to cross-reference names, maybe returns a Sym
pub fn find(&self,
name: &str,
hash: u32,
strtab: &Strtab)
-> Option<&sym::Sym> {
if self.filter(hash) {
None
} else {
self.lookup(name, hash, strtab)
}
}
}
}
}