Debian Codegraph @

libdrgn/symbol.c

raw
1 // Copyright (c) Meta Platforms, Inc. and affiliates.
2 // SPDX-License-Identifier: LGPL-2.1-or-later
3
4 #include <elf.h>
5 #include <inttypes.h>
6 #include <stdlib.h>
7 #include <string.h>
8
9 #include "binary_search.h"
10 #include "drgn_internal.h"
11 #include "string_builder.h"
12 #include "symbol.h"
13 #include "util.h"
14
15 DEFINE_VECTOR_FUNCTIONS(symbol_vector);
16
17 LIBDRGN_PUBLIC void drgn_symbol_destroy(struct drgn_symbol *sym)
18 {
19 if (sym && sym->lifetime == DRGN_LIFETIME_STATIC)
20 return;
21 if (sym && sym->name_lifetime == DRGN_LIFETIME_OWNED)
22 /* Cast here is necessary - we want symbol users to
23 * never modify sym->name, but when we own the name,
24 * we must modify it by freeing it. */
25 free((char *)sym->name);
26 free(sym);
27 }
28
29 LIBDRGN_PUBLIC void drgn_symbols_destroy(struct drgn_symbol **syms,
30 size_t count)
31 {
32 for (size_t i = 0; i < count; i++)
33 drgn_symbol_destroy(syms[i]);
34 free(syms);
35 }
36
37 struct drgn_error *
38 drgn_symbol_copy(struct drgn_symbol *dst, struct drgn_symbol *src)
39 {
40 if (src->name_lifetime == DRGN_LIFETIME_STATIC) {
41 dst->name = src->name;
42 dst->name_lifetime = DRGN_LIFETIME_STATIC;
43 } else {
44 dst->name = strdup(src->name);
45 if (!dst->name)
46 return &drgn_enomem;
47 dst->name_lifetime = DRGN_LIFETIME_OWNED;
48 }
49 dst->address = src->address;
50 dst->size = src->size;
51 dst->kind = src->kind;
52 dst->binding = src->binding;
53 return NULL;
54 }
55
56 LIBDRGN_PUBLIC struct drgn_error *
57 drgn_symbol_create(const char *name, uint64_t address, uint64_t size,
58 enum drgn_symbol_binding binding, enum drgn_symbol_kind kind,
59 enum drgn_lifetime name_lifetime, struct drgn_symbol **ret)
60 {
61 struct drgn_symbol *sym = malloc(sizeof(*sym));
62 if (!sym)
63 return &drgn_enomem;
64 sym->name = name;
65 sym->address = address;
66 sym->size = size;
67 sym->binding = binding;
68 sym->kind = kind;
69 sym->name_lifetime = name_lifetime;
70 sym->lifetime = DRGN_LIFETIME_OWNED;
71 *ret = sym;
72 return NULL;
73 }
74
75 LIBDRGN_PUBLIC const char *drgn_symbol_name(struct drgn_symbol *sym)
76 {
77 return sym->name;
78 }
79
80 LIBDRGN_PUBLIC uint64_t drgn_symbol_address(struct drgn_symbol *sym)
81 {
82 return sym->address;
83 }
84
85 LIBDRGN_PUBLIC uint64_t drgn_symbol_size(struct drgn_symbol *sym)
86 {
87 return sym->size;
88 }
89
90
91 LIBDRGN_PUBLIC enum drgn_symbol_binding
92 drgn_symbol_binding(struct drgn_symbol *sym)
93 {
94 return sym->binding;
95 }
96
97 LIBDRGN_PUBLIC enum drgn_symbol_kind drgn_symbol_kind(struct drgn_symbol *sym)
98 {
99 return sym->kind;
100 }
101
102 LIBDRGN_PUBLIC bool drgn_symbol_eq(struct drgn_symbol *a, struct drgn_symbol *b)
103 {
104 return (strcmp(a->name, b->name) == 0 && a->address == b->address &&
105 a->size == b->size && a->binding == b->binding &&
106 a->kind == b->kind);
107 }
108
109 DEFINE_VECTOR_FUNCTIONS(symbolp_vector);
110
111 LIBDRGN_PUBLIC bool
112 drgn_symbol_result_builder_add(struct drgn_symbol_result_builder *builder,
113 struct drgn_symbol *symbol)
114 {
115 if (builder->one) {
116 if (builder->single)
117 drgn_symbol_destroy(builder->single);
118 builder->single = symbol;
119 } else if (!symbolp_vector_append(&builder->vector, &symbol)) {
120 return false;
121 }
122 return true;
123 }
124
125 static void drgn_symbol_from_elf(const char *name, uint64_t address,
126 const GElf_Sym *elf_sym,
127 struct drgn_symbol *ret)
128 {
129 ret->name = name;
130 ret->name_lifetime = DRGN_LIFETIME_STATIC;
131 ret->lifetime = DRGN_LIFETIME_OWNED;
132 ret->address = address;
133 ret->size = elf_sym->st_size;
134 int binding = GELF_ST_BIND(elf_sym->st_info);
135 if (binding <= STB_WEAK || binding == STB_GNU_UNIQUE)
136 ret->binding = binding + 1;
137 else
138 ret->binding = DRGN_SYMBOL_BINDING_UNKNOWN;
139 int type = GELF_ST_TYPE(elf_sym->st_info);
140 if (type <= STT_TLS || type == STT_GNU_IFUNC)
141 ret->kind = type;
142 else
143 ret->kind = DRGN_SYMBOL_KIND_UNKNOWN;
144 }
145
146 bool
147 drgn_symbol_result_builder_add_from_elf(struct drgn_symbol_result_builder *builder,
148 const char *name, uint64_t address,
149 const GElf_Sym *elf_sym)
150 {
151 if (builder->one) {
152 // As an optimization, reuse the existing symbol allocation if
153 // we can.
154 if (!builder->single
155 || builder->single->lifetime == DRGN_LIFETIME_STATIC) {
156 builder->single = malloc(sizeof(*builder->single));
157 if (!builder->single)
158 return false;
159 } else if (builder->single->name_lifetime == DRGN_LIFETIME_OWNED) {
160 free((char *)builder->single->name);
161 }
162 drgn_symbol_from_elf(name, address, elf_sym, builder->single);
163 } else {
164 struct drgn_symbol *sym = malloc(sizeof(*sym));
165 if (!sym)
166 return false;
167 drgn_symbol_from_elf(name, address, elf_sym, sym);
168 if (!symbolp_vector_append(&builder->vector, &sym)) {
169 free(sym);
170 return false;
171 }
172 }
173 return true;
174 }
175
176 LIBDRGN_PUBLIC size_t
177 drgn_symbol_result_builder_count(const struct drgn_symbol_result_builder *builder)
178 {
179 if (builder->one)
180 return builder->single ? 1 : 0;
181 else
182 return symbolp_vector_size(&builder->vector);
183 }
184
185 void drgn_symbol_result_builder_init(struct drgn_symbol_result_builder *builder,
186 bool one)
187 {
188 memset(builder, 0, sizeof(*builder));
189 builder->one = one;
190 if (!one)
191 symbolp_vector_init(&builder->vector);
192 }
193
194 void drgn_symbol_result_builder_abort(struct drgn_symbol_result_builder *builder)
195 {
196 if (builder->one) {
197 drgn_symbol_destroy(builder->single);
198 } else {
199 vector_for_each(symbolp_vector, symbolp, &builder->vector)
200 drgn_symbol_destroy(*symbolp);
201 symbolp_vector_deinit(&builder->vector);
202 }
203 }
204
205 struct drgn_symbol *
206 drgn_symbol_result_builder_single(struct drgn_symbol_result_builder *builder)
207 {
208 return builder->single;
209 }
210
211 void drgn_symbol_result_builder_array(struct drgn_symbol_result_builder *builder,
212 struct drgn_symbol ***syms_ret, size_t *count_ret)
213 {
214 symbolp_vector_shrink_to_fit(&builder->vector);
215 symbolp_vector_steal(&builder->vector, syms_ret, count_ret);
216 }
217
218 static int name_compar(const void *lhs, const void *rhs, void *arg)
219 {
220 struct drgn_symbol_index *ix = arg;
221 uint32_t left_ix = *(const uint32_t *)lhs;
222 uint32_t right_ix = *(const uint32_t *)rhs;
223 return strcmp(ix->symbols[left_ix].name, ix->symbols[right_ix].name);
224 }
225
226 static int addr_compar(const void *lhs, const void *rhs)
227 {
228 const struct drgn_symbol *left = lhs;
229 const struct drgn_symbol *right = rhs;
230 // returning a simple subtraction would not work well since these are
231 // unsigned
232 if (left->address < right->address)
233 return -1;
234 else if (left->address > right->address)
235 return 1;
236 else
237 return 0;
238 }
239
240 struct drgn_error *
241 drgn_symbol_index_init(struct drgn_symbol *symbols, uint32_t count,
242 char *buffer, struct drgn_symbol_index *ret)
243 {
244 ret->symbols = symbols;
245 ret->num_syms = count;
246 ret->strings = buffer;
247 ret->name_sort = NULL;
248 ret->max_addrs = NULL;
249 drgn_symbol_name_table_init(&ret->htab);
250 ret->name_sort = malloc_array(count, sizeof(ret->name_sort[0]));
251 if (!ret->name_sort)
252 goto enomem;
253 ret->max_addrs = malloc_array(count, sizeof(ret->max_addrs[0]));
254 if (!ret->max_addrs)
255 goto enomem;
256
257 // In many cases (e.g kallsyms), symbols are already sorted by address,
258 // but not always. Check whether sorted, and if not, sort.
259 for (uint32_t i = 1; i < ret->num_syms; i++) {
260 if (ret->symbols[i - 1].address > ret->symbols[i].address) {
261 qsort(ret->symbols, count, sizeof(ret->symbols[0]), addr_compar);
262 break;
263 }
264 }
265
266 // Kallsyms doesn't include symbol lengths, so symbols are
267 // non-overlapping. But this is not true in general! Symbols may
268 // overlap, which makes address lookup complicated. Rather than using a
269 // complex range data structure, we can use two binary searches, one to
270 // find the first symbol which could overlap with an address, and one to
271 // find the last symbol, and then linearly search that array. This
272 // performs poorly if there are symbols which span many others, but
273 // that's a rare case. In order to do this strategy, we need an array
274 // that contains the maximum address spanned by any symbol at or before
275 // that index.
276 if (ret->num_syms > 0) // in case num_syms == 0
277 ret->max_addrs[0] = ret->symbols[0].address + ret->symbols[0].size;
278 for (uint32_t i = 1; i < ret->num_syms; i++) {
279 uint64_t max_addr = ret->symbols[i].address + ret->symbols[i].size;
280 ret->max_addrs[i] = max(ret->max_addrs[i - 1], max_addr);
281 }
282
283 // Sort the "name_sort" array by name so we get runs of symbols with the
284 // same name
285 for (uint32_t i = 0; i < ret->num_syms; i++)
286 ret->name_sort[i] = i;
287 qsort_arg(ret->name_sort, ret->num_syms, sizeof(ret->name_sort[0]),
288 name_compar, ret);
289
290 // For each unique symbol name, insert the range of symbol indexes
291 // into the hash table for fast name lookup
292 struct drgn_symbol_name_table_entry entry;
293 uint32_t current = 0;
294 while (current < ret->num_syms) {
295 const char *current_str = ret->symbols[ret->name_sort[current]].name;
296 uint32_t next = current + 1;
297 while (next < ret->num_syms) {
298 const char *next_str = ret->symbols[ret->name_sort[next]].name;
299 if (strcmp(current_str, next_str) != 0)
300 break;
301 next++;
302 }
303
304 entry.key = current_str;
305 entry.value.start = current;
306 entry.value.end = next;
307 if (drgn_symbol_name_table_insert(&ret->htab, &entry, NULL) < 0)
308 goto enomem;
309
310 current = next;
311 }
312 return NULL;
313
314 enomem:
315 drgn_symbol_index_deinit(ret);
316 return &drgn_enomem;
317 }
318
319 void
320 drgn_symbol_index_deinit(struct drgn_symbol_index *index)
321 {
322 // The symbol array is contiguous and all names come from strings
323 free(index->symbols);
324 free(index->max_addrs);
325 drgn_symbol_name_table_deinit(&index->htab);
326 free(index->strings);
327 free(index->name_sort);
328 // Simplify error handling by ensuring deinit is safe to call twice
329 memset(index, 0, sizeof(*index));
330 }
331
332 static void address_search_range(struct drgn_symbol_index *index, uint64_t address,
333 uint32_t *start_ret, uint32_t *end_ret)
334 {
335 // First, identify the maximum symbol index which could possibly contain
336 // this address. Think of this as:
337 // end_ret = bisect_right([s.address for s in symbols], address)
338 #define less_than_start(a, b) (*(a) < (b)->address)
339 *end_ret = binary_search_gt(index->symbols, index->num_syms, &address,
340 less_than_start);
341 #undef less_than_start
342
343 // Second, identify first symbol index which could possibly contain this
344 // address. We need to use "max_addrs" for this task:
345 // bisect_right(max_addrs, address)
346 #define less_than_end(a, b) (*(a) < *(b))
347 *start_ret = binary_search_gt(index->max_addrs, index->num_syms, &address,
348 less_than_end);
349 #undef less_than_end
350 }
351
352 struct drgn_error *
353 drgn_symbol_index_find(const char *name, uint64_t address,
354 enum drgn_find_symbol_flags flags, void *arg,
355 struct drgn_symbol_result_builder *builder)
356 {
357 struct drgn_symbol_index *index = arg;
358
359 // Unlike the ELF symbol finder, we don't have any particular rules
360 // about which symbols get priority when looking up a single symbol.
361 // If we decide this logic is critical, it would probably make sense to
362 // move it into the symbol finder's API via the result builder, rather
363 // than reimplementing it here.
364
365 if (flags & DRGN_FIND_SYMBOL_ADDR) {
366 uint32_t start, end;
367 address_search_range(index, address, &start, &end);
368 for (uint32_t i = start; i < end; i++) {
369 struct drgn_symbol *s = &index->symbols[i];
370 if (s->address > address || address >= s->address + s->size)
371 continue;
372 if ((flags & DRGN_FIND_SYMBOL_NAME) &&
373 strcmp(s->name, name) != 0)
374 continue;
375 if (!drgn_symbol_result_builder_add(builder, s))
376 return &drgn_enomem;
377 if (flags & DRGN_FIND_SYMBOL_ONE)
378 break;
379 }
380 } else if (flags & DRGN_FIND_SYMBOL_NAME) {
381 struct drgn_symbol_name_table_iterator it =
382 drgn_symbol_name_table_search(&index->htab, &name);
383 if (!it.entry)
384 return NULL;
385 for (uint32_t i = it.entry->value.start; i < it.entry->value.end; i++) {
386 struct drgn_symbol *s = &index->symbols[index->name_sort[i]];
387 if (!drgn_symbol_result_builder_add(builder, s))
388 return &drgn_enomem;
389 if (flags & DRGN_FIND_SYMBOL_ONE)
390 break;
391 }
392 } else {
393 for (int i = 0; i < index->num_syms; i++) {
394 struct drgn_symbol *s = &index->symbols[i];
395 if (!drgn_symbol_result_builder_add(builder, s))
396 return &drgn_enomem;
397 if (flags & DRGN_FIND_SYMBOL_ONE)
398 break;
399 }
400 }
401 return NULL;
402 }
403
404 void
405 drgn_symbol_index_builder_init(struct drgn_symbol_index_builder *builder)
406 {
407 builder->names = (struct string_builder)STRING_BUILDER_INIT;
408 symbol_vector_init(&builder->symbols);
409 }
410
411 void
412 drgn_symbol_index_builder_deinit(struct drgn_symbol_index_builder *builder)
413 {
414 string_builder_deinit(&builder->names);
415 symbol_vector_deinit(&builder->symbols);
416 }
417
418 bool
419 drgn_symbol_index_builder_add(struct drgn_symbol_index_builder *builder,
420 const struct drgn_symbol *ptr)
421 {
422 struct drgn_symbol copy = *ptr;
423
424 // Temporarily store the index into the name
425 copy.name = (char *)builder->names.len;
426 return string_builder_append(&builder->names, ptr->name)
427 && string_builder_appendc(&builder->names, '\0')
428 && symbol_vector_append(&builder->symbols, &copy);
429 }
430
431 struct drgn_error *
432 drgn_symbol_index_init_from_builder(struct drgn_symbol_index *index,
433 struct drgn_symbol_index_builder *builder)
434 {
435 size_t names_len = builder->names.len;
436 char *names = string_builder_steal(&builder->names);
437 char *tmp_names = realloc(names, names_len);
438 if (tmp_names)
439 names = tmp_names;
440
441 symbol_vector_shrink_to_fit(&builder->symbols);
442 struct drgn_symbol *symbols;
443 size_t num_syms;
444 symbol_vector_steal(&builder->symbols, &symbols, &num_syms);
445
446 // Now that the name array is finalized, resolve the names to real
447 // pointers. Update the name lifetime to static, reflecting that the
448 // symbol name is owned by the finder whose lifetime is bound to the
449 // program's once it is attached. The same goes for the symbol. Using
450 // static lifetimes helps avoid unnecessary copying.
451 for (size_t i = 0; i < num_syms; i++) {
452 size_t string_index = (size_t)symbols[i].name;
453 symbols[i].name = &names[string_index];
454 symbols[i].name_lifetime = DRGN_LIFETIME_STATIC;
455 symbols[i].lifetime = DRGN_LIFETIME_STATIC;
456 }
457
458 if (num_syms > UINT32_MAX) {
459 free(names);
460 free(symbols);
461 return drgn_error_format(DRGN_ERROR_OUT_OF_BOUNDS,
462 "too many symbols provided: %zu > %" PRIu32,
463 num_syms, UINT32_MAX);
464 }
465
466 return drgn_symbol_index_init(symbols, num_syms, names, index);
467 }