1 /*
2 * Copyright (C) 2019 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 "src/kallsyms/kernel_symbol_map.h"
18
19 #include "perfetto/base/build_config.h"
20 #include "perfetto/base/logging.h"
21 #include "perfetto/ext/base/file_utils.h"
22 #include "perfetto/ext/base/metatrace.h"
23 #include "perfetto/ext/base/paged_memory.h"
24 #include "perfetto/ext/base/scoped_file.h"
25 #include "perfetto/ext/base/string_view.h"
26 #include "perfetto/ext/base/utils.h"
27 #include "perfetto/protozero/proto_utils.h"
28
29 #include <inttypes.h>
30 #include <stdio.h>
31
32 #include <algorithm>
33 #include <functional>
34 #include <map>
35 #include <utility>
36
37 namespace perfetto {
38
39 // On a Pixel 3 this gives an avg. lookup time of 600 ns and a memory usage
40 // of 1.1 MB for 65k symbols. See go/kallsyms-parser-bench.
41 size_t KernelSymbolMap::kSymIndexSampling = 16;
42 size_t KernelSymbolMap::kTokenIndexSampling = 4;
43
44 namespace {
45
46 using TokenId = KernelSymbolMap::TokenTable::TokenId;
47 constexpr size_t kSymNameMaxLen = 128;
48 constexpr size_t kSymMaxSizeBytes = 1024 * 1024;
49
50 // Reads a kallsyms file in blocks of 4 pages each and decode its lines using
51 // a simple FSM. Calls the passed lambda for each valid symbol.
52 // It skips undefined symbols and other useless stuff.
53 template <typename Lambda /* void(uint64_t, const char*) */>
ForEachSym(const std::string & kallsyms_path,Lambda fn)54 void ForEachSym(const std::string& kallsyms_path, Lambda fn) {
55 base::ScopedFile fd = base::OpenFile(kallsyms_path.c_str(), O_RDONLY);
56 if (!fd) {
57 PERFETTO_PLOG("Cannot open %s", kallsyms_path.c_str());
58 return;
59 }
60
61 // /proc/kallsyms looks as follows:
62 // 0000000000026a80 A bpf_trace_sds
63 //
64 // ffffffffc03a6000 T cpufreq_gov_powersave_init<TAB> [cpufreq_powersave]
65 // ffffffffc035d000 T cpufreq_gov_userspace_init<TAB> [cpufreq_userspace]
66 //
67 // We parse it with a state machine that has four states, one for each column.
68 // We don't care about the part in the square brackets and ignore everything
69 // after the symbol name.
70
71 static constexpr size_t kBufSize = 16 * 1024;
72 base::PagedMemory buffer = base::PagedMemory::Allocate(kBufSize);
73 enum { kSymAddr, kSymType, kSymName, kEatRestOfLine } state = kSymAddr;
74 uint64_t sym_addr = 0;
75 char sym_type = '\0';
76 char sym_name[kSymNameMaxLen + 1];
77 size_t sym_name_len = 0;
78 for (;;) {
79 char* buf = static_cast<char*>(buffer.Get());
80 auto rsize = base::Read(*fd, buf, kBufSize);
81 if (rsize < 0) {
82 PERFETTO_PLOG("read(%s) failed", kallsyms_path.c_str());
83 return;
84 }
85 if (rsize == 0)
86 return; // EOF
87 for (size_t i = 0; i < static_cast<size_t>(rsize); i++) {
88 char c = buf[i];
89 const bool is_space = c == ' ' || c == '\t';
90 switch (state) {
91 case kSymAddr:
92 if (c >= '0' && c <= '9') {
93 sym_addr = (sym_addr << 4) | static_cast<uint8_t>(c - '0');
94 } else if (c >= 'a' && c <= 'f') {
95 sym_addr = (sym_addr << 4) | static_cast<uint8_t>(c - 'a' + 10);
96 } else if (is_space) {
97 state = kSymType;
98 } else if (c == '\0') {
99 return;
100 } else {
101 PERFETTO_ELOG("kallsyms parser error: chr 0x%x @ off=%zu", c, i);
102 return;
103 }
104 break;
105
106 case kSymType:
107 if (is_space)
108 break; // Eat leading spaces.
109 sym_type = c;
110 state = kSymName;
111 sym_name_len = 0;
112 break;
113
114 case kSymName:
115 if (is_space && sym_name_len == 0)
116 break; // Eat leading spaces.
117 if (c && c != '\n' && !is_space && sym_name_len < kSymNameMaxLen) {
118 sym_name[sym_name_len++] = c;
119 break;
120 }
121 sym_name[sym_name_len] = '\0';
122 fn(sym_addr, sym_type, sym_name);
123 sym_addr = 0;
124 sym_type = '\0';
125 state = c == '\n' ? kSymAddr : kEatRestOfLine;
126 break;
127
128 case kEatRestOfLine:
129 if (c == '\n')
130 state = kSymAddr;
131 break;
132 } // switch(state)
133 } // for (char in buf)
134 } // for (read chunk)
135 }
136
137 // Splits a symbol name into tokens using '_' as a separator, calling the passed
138 // lambda for each token. It splits tokens in a way that allows the original
139 // string to be rebuilt as-is by re-joining using a '_' between each token.
140 // For instance:
141 // _fo_a_b -> ["", fo, a, b]
142 // __fo_a_b -> [_, fo, a, b]
143 // __fo_a_b_ -> [_, fo, a, b, ""]
144 // __fo_a_b____ -> [_, fo, a, b, ___]
145 template <typename Lambda /* void(base::StringView) */>
Tokenize(const char * name,Lambda fn)146 void Tokenize(const char* name, Lambda fn) {
147 const char* tok_start = name;
148 bool is_start_of_token = true;
149 bool tok_is_sep = false;
150 for (const char* ptr = name;; ptr++) {
151 const char c = *ptr;
152 if (is_start_of_token) {
153 tok_is_sep = *tok_start == '_'; // Deals with tokens made of '_'s.
154 is_start_of_token = false;
155 }
156 // Scan until either the end of string or the next character (which is a '_'
157 // in nominal cases, or anything != '_' for tokens made by 1+ '_').
158 if (c == '\0' || (!tok_is_sep && c == '_') || (tok_is_sep && c != '_')) {
159 size_t tok_len = static_cast<size_t>(ptr - tok_start);
160 if (tok_is_sep && c != '\0')
161 --tok_len;
162 fn(base::StringView(tok_start, tok_len));
163 if (c == '\0')
164 return;
165 tok_start = tok_is_sep ? ptr : ptr + 1;
166 is_start_of_token = true;
167 }
168 }
169 }
170
171 } // namespace
172
TokenTable()173 KernelSymbolMap::TokenTable::TokenTable() {
174 // Insert a null token as id 0. We can't just add "" because the empty string
175 // is special-cased and doesn't insert an actual token. So we push a string of
176 // size one that contains only the null character instead.
177 char null_tok = 0;
178 Add(std::string(&null_tok, 1));
179 }
180
181 KernelSymbolMap::TokenTable::~TokenTable() = default;
182
183 // Adds a new token to the db. Does not dedupe identical token (with the
184 // exception of the empty string). The caller has to deal with that.
185 // Supports only ASCII characters in the range [1, 127].
186 // The last character of the token will have the MSB set.
Add(const std::string & token)187 TokenId KernelSymbolMap::TokenTable::Add(const std::string& token) {
188 const size_t token_size = token.size();
189 if (token_size == 0)
190 return 0;
191 TokenId id = num_tokens_++;
192
193 const size_t buf_size_before_insertion = buf_.size();
194 if (id % kTokenIndexSampling == 0)
195 index_.emplace_back(buf_size_before_insertion);
196
197 const size_t prev_size = buf_.size();
198 buf_.resize(prev_size + token_size);
199 char* tok_wptr = &buf_[prev_size];
200 for (size_t i = 0; i < token_size - 1; i++) {
201 PERFETTO_DCHECK((token.at(i) & 0x80) == 0); // |token| must be ASCII only.
202 *(tok_wptr++) = token.at(i) & 0x7f;
203 }
204 *(tok_wptr++) = static_cast<char>(token.at(token_size - 1) | 0x80);
205 PERFETTO_DCHECK(tok_wptr == &buf_[buf_.size()]);
206 return id;
207 }
208
209 // NOTE: the caller need to mask the returned chars with 0x7f. The last char of
210 // the StringView will have its MSB set (it's used as a EOF char internally).
Lookup(TokenId id)211 base::StringView KernelSymbolMap::TokenTable::Lookup(TokenId id) {
212 if (id == 0)
213 return base::StringView();
214 if (id > num_tokens_)
215 return base::StringView("<error>");
216 // We don't know precisely where the id-th token starts in the buffer. We
217 // store only one position every kTokenIndexSampling. From there, the token
218 // can be found with a linear scan of at most kTokenIndexSampling steps.
219 size_t index_off = id / kTokenIndexSampling;
220 PERFETTO_DCHECK(index_off < index_.size());
221 TokenId cur_id = static_cast<TokenId>(index_off * kTokenIndexSampling);
222 uint32_t begin = index_[index_off];
223 PERFETTO_DCHECK(begin == 0 || buf_[begin - 1] & 0x80);
224 const size_t buf_size = buf_.size();
225 for (uint32_t off = begin; off < buf_size; ++off) {
226 // Advance |off| until the end of the token (which has the MSB set).
227 if ((buf_[off] & 0x80) == 0)
228 continue;
229 if (cur_id == id)
230 return base::StringView(&buf_[begin], off - begin + 1);
231 ++cur_id;
232 begin = off + 1;
233 }
234 return base::StringView();
235 }
236
Parse(const std::string & kallsyms_path)237 size_t KernelSymbolMap::Parse(const std::string& kallsyms_path) {
238 PERFETTO_METATRACE_SCOPED(TAG_PRODUCER, KALLSYMS_PARSE);
239 using SymAddr = uint64_t;
240
241 struct TokenInfo {
242 uint32_t count = 0;
243 TokenId id = 0;
244 };
245
246 // Note if changing the container: the code below relies on stable iterators.
247 using TokenMap = std::map<std::string, TokenInfo>;
248 using TokenMapPtr = TokenMap::value_type*;
249 TokenMap tokens;
250
251 // Keep the (ordered) list of tokens for each symbol.
252 struct SymAddrAndTokenPtr {
253 SymAddr addr;
254 TokenMapPtr token_map_entry;
255
256 bool operator<(const SymAddrAndTokenPtr& other) const {
257 return addr < other.addr;
258 }
259 };
260 std::vector<SymAddrAndTokenPtr> symbol_tokens;
261
262 // Based on `cat /proc/kallsyms | egrep "\b[tT]\b" | wc -l`.
263 symbol_tokens.reserve(128 * 1024);
264
265 ForEachSym(kallsyms_path, [&](SymAddr addr, char type, const char* name) {
266 if (addr == 0 || (type != 't' && type != 'T') || name[0] == '$') {
267 return;
268 }
269
270 // Split each symbol name in tokens, using '_' as a separator (so that
271 // "foo_bar" -> ["foo", "bar"]). For each token hash:
272 // 1. Keep track of the frequency of each token.
273 // 2. Keep track of the list of token hashes for each symbol.
274 Tokenize(name, [&tokens, &symbol_tokens, addr](base::StringView token) {
275 // Strip the .cfi part if present.
276 if (token.substr(token.size() - 4) == ".cfi")
277 token = token.substr(0, token.size() - 4);
278 auto it_and_ins = tokens.emplace(token.ToStdString(), TokenInfo{});
279 it_and_ins.first->second.count++;
280 symbol_tokens.emplace_back(SymAddrAndTokenPtr{addr, &*it_and_ins.first});
281 });
282 });
283
284 symbol_tokens.shrink_to_fit();
285
286 // For each symbol address, T entries are inserted into |symbol_tokens|, one
287 // for each token. These symbols are added in arbitrary address (as seen in
288 // /proc/kallsyms). Here we want to sort symbols by addresses, but at the same
289 // time preserve the order of tokens within each address.
290 // For instance, if kallsyms has: {0x41: connect_socket, 0x42: write_file}:
291 // Before sort: [(0x42, write), (0x42, file), (0x41, connect), (0x41, socket)]
292 // After sort: [(0x41, connect), (0x41, socket), (0x42, write), (0x42, file)]
293 std::stable_sort(symbol_tokens.begin(), symbol_tokens.end());
294
295 // At this point we have broken down each symbol into a set of token hashes.
296 // Now generate the token ids, putting high freq tokens first, so they use
297 // only one byte to varint encode.
298
299 // This block limits the lifetime of |tokens_by_freq|.
300 {
301 std::vector<TokenMapPtr> tokens_by_freq;
302 tokens_by_freq.resize(tokens.size());
303 size_t tok_idx = 0;
304 for (auto& kv : tokens)
305 tokens_by_freq[tok_idx++] = &kv;
306
307 auto comparer = [](TokenMapPtr a, TokenMapPtr b) {
308 PERFETTO_DCHECK(a && b);
309 return b->second.count < a->second.count;
310 };
311 std::sort(tokens_by_freq.begin(), tokens_by_freq.end(), comparer);
312 for (TokenMapPtr tinfo : tokens_by_freq) {
313 tinfo->second.id = tokens_.Add(tinfo->first);
314 }
315 }
316 tokens_.shrink_to_fit();
317
318 buf_.resize(2 * 1024 * 1024); // Based on real-word observations.
319 base_addr_ = symbol_tokens.empty() ? 0 : symbol_tokens.begin()->addr;
320 SymAddr prev_sym_addr = base_addr_;
321 uint8_t* wptr = buf_.data();
322
323 for (auto it = symbol_tokens.begin(); it != symbol_tokens.end();) {
324 const SymAddr sym_addr = it->addr;
325
326 // Find the iterator to the first token of the next symbol (or the end).
327 auto sym_start = it;
328 auto sym_end = it;
329 while (sym_end != symbol_tokens.end() && sym_end->addr == sym_addr)
330 ++sym_end;
331
332 // The range [sym_start, sym_end) has all the tokens for the current symbol.
333 uint32_t size_before = static_cast<uint32_t>(wptr - buf_.data());
334
335 // Make sure there is enough headroom to write the symbol.
336 if (buf_.size() - size_before < 1024) {
337 buf_.resize(buf_.size() + 32768);
338 wptr = buf_.data() + size_before;
339 }
340
341 uint32_t sym_rel_addr = static_cast<uint32_t>(sym_addr - base_addr_);
342 const size_t sym_num = num_syms_++;
343 if (sym_num % kSymIndexSampling == 0)
344 index_.emplace_back(std::make_pair(sym_rel_addr, size_before));
345 PERFETTO_DCHECK(sym_addr >= prev_sym_addr);
346 uint32_t delta = static_cast<uint32_t>(sym_addr - prev_sym_addr);
347 wptr = protozero::proto_utils::WriteVarInt(delta, wptr);
348 // Append all the token ids.
349 for (it = sym_start; it != sym_end;) {
350 PERFETTO_DCHECK(it->addr == sym_addr);
351 TokenMapPtr const token_map_entry = it->token_map_entry;
352 const TokenInfo& token_info = token_map_entry->second;
353 TokenId token_id = token_info.id << 1;
354 ++it;
355 token_id |= (it == sym_end) ? 1 : 0; // Last one has LSB set to 1.
356 wptr = protozero::proto_utils::WriteVarInt(token_id, wptr);
357 }
358 prev_sym_addr = sym_addr;
359 } // for (symbols)
360
361 buf_.resize(static_cast<size_t>(wptr - buf_.data()));
362 buf_.shrink_to_fit();
363 base::MaybeReleaseAllocatorMemToOS(); // For Scudo, b/170217718.
364
365 if (num_syms_ == 0) {
366 PERFETTO_ELOG(
367 "Failed to parse kallsyms. Kernel functions will not be symbolized. On "
368 "Linux this requires either running traced_probes as root or manually "
369 "lowering /proc/sys/kernel/kptr_restrict");
370 } else {
371 PERFETTO_DLOG(
372 "Loaded %zu kalllsyms entries. Mem usage: %zu B (addresses) + %zu B "
373 "(tokens), total: %zu B",
374 num_syms_, addr_bytes(), tokens_.size_bytes(), size_bytes());
375 }
376
377 return num_syms_;
378 }
379
Lookup(uint64_t sym_addr)380 std::string KernelSymbolMap::Lookup(uint64_t sym_addr) {
381 if (index_.empty() || sym_addr < base_addr_)
382 return "";
383
384 // First find the highest symbol address <= sym_addr.
385 // Start with a binary search using the sparse index.
386
387 const uint32_t sym_rel_addr = static_cast<uint32_t>(sym_addr - base_addr_);
388 auto it = std::upper_bound(index_.cbegin(), index_.cend(),
389 std::make_pair(sym_rel_addr, 0u));
390 if (it != index_.cbegin())
391 --it;
392
393 // Then continue with a linear scan (of at most kSymIndexSampling steps).
394 uint32_t addr = it->first;
395 uint32_t off = it->second;
396 const uint8_t* rdptr = &buf_[off];
397 const uint8_t* const buf_end = &buf_[buf_.size()];
398 bool parsing_addr = true;
399 const uint8_t* next_rdptr = nullptr;
400 uint64_t sym_start_addr = 0;
401 for (bool is_first_addr = true;; is_first_addr = false) {
402 uint64_t v = 0;
403 const auto* prev_rdptr = rdptr;
404 rdptr = protozero::proto_utils::ParseVarInt(rdptr, buf_end, &v);
405 if (rdptr == prev_rdptr)
406 break;
407 if (parsing_addr) {
408 addr += is_first_addr ? 0 : static_cast<uint32_t>(v);
409 parsing_addr = false;
410 if (addr > sym_rel_addr)
411 break;
412 next_rdptr = rdptr;
413 sym_start_addr = addr;
414 } else {
415 // This is a token. Wait for the EOF maker.
416 parsing_addr = (v & 1) == 1;
417 }
418 }
419
420 if (!next_rdptr)
421 return "";
422
423 PERFETTO_DCHECK(sym_rel_addr >= sym_start_addr);
424
425 // If this address is too far from the start of the symbol, this is likely
426 // a pointer to something else (e.g. some vmalloc struct) and we just picked
427 // the very last symbol for a loader region.
428 if (sym_rel_addr - sym_start_addr > kSymMaxSizeBytes)
429 return "";
430
431 // The address has been found. Now rejoin the tokens to form the symbol name.
432
433 rdptr = next_rdptr;
434 std::string sym_name;
435 sym_name.reserve(kSymNameMaxLen);
436 for (bool eof = false, is_first_token = true; !eof; is_first_token = false) {
437 uint64_t v = 0;
438 const auto* old = rdptr;
439 rdptr = protozero::proto_utils::ParseVarInt(rdptr, buf_end, &v);
440 if (rdptr == old)
441 break;
442 eof = v & 1;
443 base::StringView token = tokens_.Lookup(static_cast<TokenId>(v >> 1));
444 if (!is_first_token)
445 sym_name.push_back('_');
446 for (size_t i = 0; i < token.size(); i++)
447 sym_name.push_back(token.at(i) & 0x7f);
448 }
449 return sym_name;
450 }
451
452 } // namespace perfetto
453