1 /*
2 * Copyright (C) 2018 The Android Open Source Project
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17 #include "berberis/tiny_loader/tiny_symbol_table.h"
18
19 #include <elf.h>
20 #include <inttypes.h>
21
22 #include "berberis/base/checks.h"
23
TinySymbolTable()24 TinySymbolTable::TinySymbolTable()
25 : load_bias_(0),
26 symtab_(nullptr),
27 strtab_(nullptr),
28 strtab_size_(0),
29 is_gnu_hash_(false),
30 gnu_nbucket_(0),
31 gnu_bucket_(nullptr),
32 gnu_chain_(nullptr),
33 gnu_maskwords_(0),
34 gnu_shift2_(0),
35 gnu_bloom_filter_(nullptr),
36 sysv_nbucket_(0),
37 sysv_nchain_(0),
38 sysv_bucket_(nullptr),
39 sysv_chain_(nullptr) {}
40
TinySymbolTable(ElfAddr load_bias,ElfSym * symtab,const char * strtab,size_t strtab_size,size_t gnu_nbucket,uint32_t * gnu_bucket,uint32_t * gnu_chain,uint32_t gnu_maskwords,uint32_t gnu_shift2,ElfAddr * gnu_bloom_filter)41 TinySymbolTable::TinySymbolTable(ElfAddr load_bias, ElfSym* symtab, const char* strtab,
42 size_t strtab_size, size_t gnu_nbucket, uint32_t* gnu_bucket,
43 uint32_t* gnu_chain, uint32_t gnu_maskwords, uint32_t gnu_shift2,
44 ElfAddr* gnu_bloom_filter)
45 : load_bias_(load_bias),
46 symtab_(symtab),
47 strtab_(strtab),
48 strtab_size_(strtab_size),
49 is_gnu_hash_(true),
50 gnu_nbucket_(gnu_nbucket),
51 gnu_bucket_(gnu_bucket),
52 gnu_chain_(gnu_chain),
53 gnu_maskwords_(gnu_maskwords),
54 gnu_shift2_(gnu_shift2),
55 gnu_bloom_filter_(gnu_bloom_filter),
56 sysv_nbucket_(0),
57 sysv_nchain_(0),
58 sysv_bucket_(nullptr),
59 sysv_chain_(nullptr) {}
60
TinySymbolTable(ElfAddr load_bias,ElfSym * symtab,const char * strtab,size_t strtab_size,size_t sysv_nbucket,size_t sysv_nchain,uint32_t * sysv_bucket,uint32_t * sysv_chain)61 TinySymbolTable::TinySymbolTable(ElfAddr load_bias, ElfSym* symtab, const char* strtab,
62 size_t strtab_size, size_t sysv_nbucket, size_t sysv_nchain,
63 uint32_t* sysv_bucket, uint32_t* sysv_chain)
64 : load_bias_(load_bias),
65 symtab_(symtab),
66 strtab_(strtab),
67 strtab_size_(strtab_size),
68 is_gnu_hash_(false),
69 gnu_nbucket_(0),
70 gnu_bucket_(nullptr),
71 gnu_chain_(nullptr),
72 gnu_maskwords_(0),
73 gnu_shift2_(0),
74 gnu_bloom_filter_(nullptr),
75 sysv_nbucket_(sysv_nbucket),
76 sysv_nchain_(sysv_nchain),
77 sysv_bucket_(sysv_bucket),
78 sysv_chain_(sysv_chain) {}
79
GnuHash(const char * symbol_name) const80 uint32_t TinySymbolTable::GnuHash(const char* symbol_name) const {
81 uint32_t h = 5381;
82 const uint8_t* name = reinterpret_cast<const uint8_t*>(symbol_name);
83 while (*name != 0) {
84 h += (h << 5) + *name++; // h*33 + c = h + h * 32 + c = h + h << 5 + c
85 }
86
87 return h;
88 }
89
SysvHash(const char * symbol_name) const90 uint32_t TinySymbolTable::SysvHash(const char* symbol_name) const {
91 const uint8_t* name = reinterpret_cast<const uint8_t*>(symbol_name);
92 uint32_t h = 0;
93 while (*name != 0) {
94 h = (h << 4) + *name++;
95 uint32_t g = h & 0xf0000000;
96 h ^= g;
97 h ^= g >> 24;
98 }
99
100 return h;
101 }
102
GetString(ElfWord index) const103 const char* TinySymbolTable::GetString(ElfWord index) const {
104 CHECK(index < strtab_size_);
105 return strtab_ + index;
106 }
107
is_symbol_global_and_defined(ElfSym * s)108 static bool is_symbol_global_and_defined(ElfSym* s) {
109 return (ELF32_ST_BIND(s->st_info) == STB_GLOBAL || ELF32_ST_BIND(s->st_info) == STB_WEAK) &&
110 s->st_shndx != SHN_UNDEF;
111 }
112
FindGnuSymbol(const char * name) const113 void* TinySymbolTable::FindGnuSymbol(const char* name) const {
114 CHECK(is_gnu_hash_);
115 CHECK(gnu_bloom_filter_ != nullptr);
116 CHECK(gnu_bucket_ != nullptr);
117 CHECK(gnu_chain_ != nullptr);
118
119 uint32_t hash = GnuHash(name);
120 uint32_t h2 = hash >> gnu_shift2_;
121
122 uint32_t bloom_mask_bits = sizeof(ElfAddr) * 8;
123 uint32_t word_num = (hash / bloom_mask_bits) & gnu_maskwords_;
124 ElfAddr bloom_word = gnu_bloom_filter_[word_num];
125
126 // test against bloom filter
127 if ((1 & (bloom_word >> (hash % bloom_mask_bits)) & (bloom_word >> (h2 % bloom_mask_bits))) ==
128 0) {
129 return nullptr;
130 }
131
132 // probably yes. Run precise test..
133 uint32_t n = gnu_bucket_[hash % gnu_nbucket_];
134
135 if (n == 0) {
136 return nullptr;
137 }
138
139 do {
140 ElfSym* s = symtab_ + n;
141 if (((gnu_chain_[n] ^ hash) >> 1) == 0 && strcmp(GetString(s->st_name), name) == 0 &&
142 is_symbol_global_and_defined(s)) {
143 return reinterpret_cast<void*>(load_bias_ + s->st_value);
144 }
145 } while ((gnu_chain_[n++] & 1) == 0);
146
147 return nullptr;
148 }
149
FindSysvSymbol(const char * name) const150 void* TinySymbolTable::FindSysvSymbol(const char* name) const {
151 CHECK(!is_gnu_hash_);
152 CHECK(sysv_bucket_ != nullptr);
153 CHECK(sysv_chain_ != nullptr);
154
155 uint32_t hash = SysvHash(name);
156
157 for (uint32_t n = sysv_bucket_[hash % sysv_nbucket_]; n != 0; n = sysv_chain_[n]) {
158 ElfSym* s = symtab_ + n;
159 if (strcmp(GetString(s->st_name), name) == 0 && is_symbol_global_and_defined(s)) {
160 return reinterpret_cast<void*>(load_bias_ + s->st_value);
161 }
162 }
163
164 return nullptr;
165 }
166
ForEachGnuSymbol(std::function<void (const ElfSym *)> symbol_handler) const167 void TinySymbolTable::ForEachGnuSymbol(std::function<void(const ElfSym*)> symbol_handler) const {
168 CHECK(is_gnu_hash_);
169 CHECK(gnu_bucket_ != nullptr);
170 CHECK(gnu_chain_ != nullptr);
171
172 for (size_t i = 0; i < gnu_nbucket_; ++i) {
173 uint32_t n = gnu_bucket_[i];
174
175 if (n == 0) {
176 continue;
177 }
178
179 do {
180 symbol_handler(symtab_ + n);
181 } while ((gnu_chain_[n++] & 1) == 0);
182 }
183 }
184
ForEachSysvSymbol(std::function<void (const ElfSym *)> symbol_handler) const185 void TinySymbolTable::ForEachSysvSymbol(std::function<void(const ElfSym*)> symbol_handler) const {
186 CHECK(!is_gnu_hash_);
187
188 for (size_t i = 0; i < sysv_nchain_; ++i) {
189 symbol_handler(symtab_ + i);
190 }
191 }
192
ForEachSymbol(std::function<void (const char *,void *,const ElfSym *)> symbol_handler) const193 void TinySymbolTable::ForEachSymbol(
194 std::function<void(const char*, void*, const ElfSym*)> symbol_handler) const {
195 std::function<void(const ElfSym*)> handler = [&](const ElfSym* s) {
196 symbol_handler(GetString(s->st_name), reinterpret_cast<void*>(load_bias_ + s->st_value), s);
197 };
198
199 if (is_gnu_hash_) {
200 ForEachGnuSymbol(handler);
201 } else {
202 ForEachSysvSymbol(handler);
203 }
204 }
205
FindSymbol(const char * name) const206 void* TinySymbolTable::FindSymbol(const char* name) const {
207 return is_gnu_hash_ ? FindGnuSymbol(name) : FindSysvSymbol(name);
208 }
209