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
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("") , 0x00001505);
assert_eq!(hash("printf") , 0x156b2bb8);
assert_eq!(hash("exit") , 0x7c967e3f);
assert_eq!(hash("syscall") , 0xbac212a0);
assert_eq!(hash("flapenguin.me"), 0x8ae9f18e);
}
}
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],
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;
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;
if idx == 0 {
return None;
}
let mut hash_idx = idx - self.symindex;
let hash = hash & !1;
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];
if hash == (h2 & !1) && name == symbol {
return Some(symbol_);
}
if h2 & 1 == 1 {
break;
}
}
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));
let filter = self.bloomwords[bloom_idx as usize] as usize;
filter & (bitmask as usize) != (bitmask as usize)
}
pub fn find(&self,
name: &str,
hash: u32,
strtab: &Strtab)
-> Option<&sym::Sym> {
if self.filter(hash) {
None
} else {
self.lookup(name, hash, strtab)
}
}
}
}
}