projects/linux·blob master · refs

589 lines · 12.7 KiB

1// SPDX-License-Identifier: GPL-2.0
2/*
3 * Copyright (C) 2024 Google LLC
4 */
5
6#define _GNU_SOURCE
7#include <inttypes.h>
8#include <stdio.h>
9#include <stdlib.h>
10#include <string.h>
11#include <zlib.h>
12
13#include "gendwarfksyms.h"
14
15static struct cache expansion_cache;
16
17/*
18 * A simple linked list of shared or owned strings to avoid copying strings
19 * around when not necessary.
20 */
21struct type_list_entry {
22 const char *str;
23 void *owned;
24 struct list_head list;
25};
26
27static void type_list_free(struct list_head *list)
28{
29 struct type_list_entry *entry;
30 struct type_list_entry *tmp;
31
32 list_for_each_entry_safe(entry, tmp, list, list) {
33 if (entry->owned)
34 free(entry->owned);
35 free(entry);
36 }
37
38 INIT_LIST_HEAD(list);
39}
40
41static int type_list_append(struct list_head *list, const char *s, void *owned)
42{
43 struct type_list_entry *entry;
44
45 if (!s)
46 return 0;
47
48 entry = xmalloc(sizeof(*entry));
49 entry->str = s;
50 entry->owned = owned;
51 list_add_tail(&entry->list, list);
52
53 return strlen(entry->str);
54}
55
56static void type_list_write(struct list_head *list, FILE *file)
57{
58 struct type_list_entry *entry;
59
60 list_for_each_entry(entry, list, list) {
61 if (entry->str)
62 checkp(fputs(entry->str, file));
63 }
64}
65
66/*
67 * An expanded type string in symtypes format.
68 */
69struct type_expansion {
70 char *name;
71 size_t len;
72 struct list_head expanded;
73 struct hlist_node hash;
74};
75
76static void type_expansion_init(struct type_expansion *type)
77{
78 type->name = NULL;
79 type->len = 0;
80 INIT_LIST_HEAD(&type->expanded);
81}
82
83static inline void type_expansion_free(struct type_expansion *type)
84{
85 free(type->name);
86 type->name = NULL;
87 type->len = 0;
88 type_list_free(&type->expanded);
89}
90
91static void type_expansion_append(struct type_expansion *type, const char *s,
92 void *owned)
93{
94 type->len += type_list_append(&type->expanded, s, owned);
95}
96
97/*
98 * type_map -- the longest expansions for each type.
99 *
100 * const char *name -> struct type_expansion *
101 */
102#define TYPE_HASH_BITS 12
103static HASHTABLE_DEFINE(type_map, 1 << TYPE_HASH_BITS);
104
105static int __type_map_get(const char *name, struct type_expansion **res)
106{
107 struct type_expansion *e;
108
109 hash_for_each_possible(type_map, e, hash, hash_str(name)) {
110 if (!strcmp(name, e->name)) {
111 *res = e;
112 return 0;
113 }
114 }
115
116 return -1;
117}
118
119static struct type_expansion *type_map_add(const char *name,
120 struct type_expansion *type)
121{
122 struct type_expansion *e;
123
124 if (__type_map_get(name, &e)) {
125 e = xmalloc(sizeof(*e));
126 type_expansion_init(e);
127 e->name = xstrdup(name);
128
129 hash_add(type_map, &e->hash, hash_str(e->name));
130
131 if (dump_types)
132 debug("adding %s", e->name);
133 } else {
134 /* Use the longest available expansion */
135 if (type->len <= e->len)
136 return e;
137
138 type_list_free(&e->expanded);
139
140 if (dump_types)
141 debug("replacing %s", e->name);
142 }
143
144 /* Take ownership of type->expanded */
145 list_replace_init(&type->expanded, &e->expanded);
146 e->len = type->len;
147
148 if (dump_types) {
149 checkp(fputs(e->name, stderr));
150 checkp(fputs(" ", stderr));
151 type_list_write(&e->expanded, stderr);
152 checkp(fputs("\n", stderr));
153 }
154
155 return e;
156}
157
158static void type_parse(const char *name, const char *str,
159 struct type_expansion *type);
160
161static int type_map_get(const char *name, struct type_expansion **res)
162{
163 struct type_expansion type;
164 const char *override;
165
166 if (!__type_map_get(name, res))
167 return 0;
168
169 /*
170 * If die_map didn't contain a type, we might still have
171 * a type_string kABI rule that defines it.
172 */
173 if (stable && kabi_get_type_string(name, &override)) {
174 type_expansion_init(&type);
175 type_parse(name, override, &type);
176 *res = type_map_add(name, &type);
177 type_expansion_free(&type);
178 return 0;
179 }
180
181 return -1;
182}
183
184static int cmp_expansion_name(const void *p1, const void *p2)
185{
186 struct type_expansion *const *e1 = p1;
187 struct type_expansion *const *e2 = p2;
188
189 return strcmp((*e1)->name, (*e2)->name);
190}
191
192static void type_map_write(FILE *file)
193{
194 struct type_expansion *e;
195 struct hlist_node *tmp;
196 struct type_expansion **es;
197 size_t count = 0;
198 size_t i = 0;
199
200 if (!file)
201 return;
202
203 hash_for_each_safe(type_map, e, tmp, hash)
204 ++count;
205 es = xmalloc(count * sizeof(*es));
206 hash_for_each_safe(type_map, e, tmp, hash)
207 es[i++] = e;
208
209 qsort(es, count, sizeof(*es), cmp_expansion_name);
210
211 for (i = 0; i < count; ++i) {
212 checkp(fputs(es[i]->name, file));
213 checkp(fputs(" ", file));
214 type_list_write(&es[i]->expanded, file);
215 checkp(fputs("\n", file));
216 }
217
218 free(es);
219}
220
221static void type_map_free(void)
222{
223 struct type_expansion *e;
224 struct hlist_node *tmp;
225
226 hash_for_each_safe(type_map, e, tmp, hash) {
227 type_expansion_free(e);
228 free(e);
229 }
230
231 hash_init(type_map);
232}
233
234/*
235 * CRC for a type, with an optional fully expanded type string for
236 * debugging.
237 */
238struct version {
239 struct type_expansion type;
240 unsigned long crc;
241};
242
243static void version_init(struct version *version)
244{
245 version->crc = crc32(0, NULL, 0);
246 type_expansion_init(&version->type);
247}
248
249static void version_free(struct version *version)
250{
251 type_expansion_free(&version->type);
252}
253
254static void version_add(struct version *version, const char *s)
255{
256 version->crc = crc32(version->crc, (void *)s, strlen(s));
257 if (dump_versions)
258 type_expansion_append(&version->type, s, NULL);
259}
260
261/*
262 * Type reference format: <prefix>#<name>, where prefix:
263 * s -> structure
264 * u -> union
265 * e -> enum
266 * t -> typedef
267 *
268 * Names with spaces are additionally wrapped in single quotes.
269 */
270static inline bool is_type_prefix(const char *s)
271{
272 return (s[0] == 's' || s[0] == 'u' || s[0] == 'e' || s[0] == 't') &&
273 s[1] == '#';
274}
275
276static char get_type_prefix(int tag)
277{
278 switch (tag) {
279 case DW_TAG_class_type:
280 case DW_TAG_structure_type:
281 return 's';
282 case DW_TAG_union_type:
283 return 'u';
284 case DW_TAG_enumeration_type:
285 return 'e';
286 case DW_TAG_typedef_type:
287 return 't';
288 default:
289 return 0;
290 }
291}
292
293static char *get_type_name(struct die *cache)
294{
295 const char *quote;
296 char prefix;
297 char *name;
298
299 if (cache->state == DIE_INCOMPLETE) {
300 warn("found incomplete cache entry: %p", cache);
301 return NULL;
302 }
303 if (cache->state == DIE_SYMBOL || cache->state == DIE_FQN)
304 return NULL;
305 if (!cache->fqn || !*cache->fqn)
306 return NULL;
307
308 prefix = get_type_prefix(cache->tag);
309 if (!prefix)
310 return NULL;
311
312 /* Wrap names with spaces in single quotes */
313 quote = strstr(cache->fqn, " ") ? "'" : "";
314
315 /* <prefix>#<type_name>\0 */
316 if (asprintf(&name, "%c#%s%s%s", prefix, quote, cache->fqn, quote) < 0)
317 error("asprintf failed for '%s'", cache->fqn);
318
319 return name;
320}
321
322static void __calculate_version(struct version *version,
323 struct type_expansion *type)
324{
325 struct type_list_entry *entry;
326 struct type_expansion *e;
327
328 /* Calculate a CRC over an expanded type string */
329 list_for_each_entry(entry, &type->expanded, list) {
330 if (is_type_prefix(entry->str)) {
331 if (type_map_get(entry->str, &e))
332 error("unknown type reference to '%s' when expanding '%s'",
333 entry->str, type->name);
334
335 /*
336 * It's sufficient to expand each type reference just
337 * once to detect changes.
338 */
339 if (cache_was_expanded(&expansion_cache, e)) {
340 version_add(version, entry->str);
341 } else {
342 cache_mark_expanded(&expansion_cache, e);
343 __calculate_version(version, e);
344 }
345 } else {
346 version_add(version, entry->str);
347 }
348 }
349}
350
351static void calculate_version(struct version *version,
352 struct type_expansion *type)
353{
354 version_init(version);
355 __calculate_version(version, type);
356 cache_free(&expansion_cache);
357}
358
359static void __type_expand(struct die *cache, struct type_expansion *type)
360{
361 struct die_fragment *df;
362 struct die *child;
363 char *name;
364
365 list_for_each_entry(df, &cache->fragments, list) {
366 switch (df->type) {
367 case FRAGMENT_STRING:
368 type_expansion_append(type, df->data.str, NULL);
369 break;
370 case FRAGMENT_DIE:
371 /* Use a complete die_map expansion if available */
372 if (__die_map_get(df->data.addr, DIE_COMPLETE,
373 &child) &&
374 __die_map_get(df->data.addr, DIE_UNEXPANDED,
375 &child))
376 error("unknown child: %" PRIxPTR,
377 df->data.addr);
378
379 name = get_type_name(child);
380 if (name)
381 type_expansion_append(type, name, name);
382 else
383 __type_expand(child, type);
384
385 break;
386 case FRAGMENT_LINEBREAK:
387 /*
388 * Keep whitespace in the symtypes format, but avoid
389 * repeated spaces.
390 */
391 if (list_is_last(&df->list, &cache->fragments) ||
392 list_next_entry(df, list)->type !=
393 FRAGMENT_LINEBREAK)
394 type_expansion_append(type, " ", NULL);
395 break;
396 default:
397 error("empty die_fragment in %p", cache);
398 }
399 }
400}
401
402static void type_expand(const char *name, struct die *cache,
403 struct type_expansion *type)
404{
405 const char *override;
406
407 type_expansion_init(type);
408
409 if (stable && kabi_get_type_string(name, &override))
410 type_parse(name, override, type);
411 else
412 __type_expand(cache, type);
413}
414
415static void type_parse(const char *name, const char *str,
416 struct type_expansion *type)
417{
418 char *fragment;
419 size_t start = 0;
420 size_t end;
421 size_t pos;
422
423 if (!*str)
424 error("empty type string override for '%s'", name);
425
426 for (pos = 0; str[pos]; ++pos) {
427 bool empty;
428 char marker = ' ';
429
430 if (!is_type_prefix(&str[pos]))
431 continue;
432
433 end = pos + 2;
434
435 /*
436 * Find the end of the type reference. If the type name contains
437 * spaces, it must be in single quotes.
438 */
439 if (str[end] == '\'') {
440 marker = '\'';
441 ++end;
442 }
443 while (str[end] && str[end] != marker)
444 ++end;
445
446 /* Check that we have a non-empty type name */
447 if (marker == '\'') {
448 if (str[end] != marker)
449 error("incomplete %c# type reference for '%s' (string : '%s')",
450 str[pos], name, str);
451 empty = end == pos + 3;
452 ++end;
453 } else {
454 empty = end == pos + 2;
455 }
456 if (empty)
457 error("empty %c# type name for '%s' (string: '%s')",
458 str[pos], name, str);
459
460 /* Append the part of the string before the type reference */
461 if (pos > start) {
462 fragment = xstrndup(&str[start], pos - start);
463 type_expansion_append(type, fragment, fragment);
464 }
465
466 /*
467 * Append the type reference -- note that if the reference
468 * is invalid, i.e. points to a non-existent type, we will
469 * print out an error when calculating versions.
470 */
471 fragment = xstrndup(&str[pos], end - pos);
472 type_expansion_append(type, fragment, fragment);
473
474 start = end;
475 pos = end - 1;
476 }
477
478 /* Append the rest of the type string, if there's any left */
479 if (str[start])
480 type_expansion_append(type, &str[start], NULL);
481}
482
483static void expand_type(struct die *cache, void *arg)
484{
485 struct type_expansion type;
486 char *name;
487
488 if (cache->mapped)
489 return;
490
491 cache->mapped = true;
492
493 /*
494 * Skip unexpanded die_map entries if there's a complete
495 * expansion available for this DIE.
496 */
497 if (cache->state == DIE_UNEXPANDED &&
498 !__die_map_get(cache->addr, DIE_COMPLETE, &cache)) {
499 if (cache->mapped)
500 return;
501
502 cache->mapped = true;
503 }
504
505 name = get_type_name(cache);
506 if (!name)
507 return;
508
509 debug("%s", name);
510
511 type_expand(name, cache, &type);
512 type_map_add(name, &type);
513 type_expansion_free(&type);
514 free(name);
515}
516
517static void expand_symbol(struct symbol *sym, void *arg)
518{
519 struct type_expansion type;
520 struct version version;
521 struct die *cache;
522
523 /*
524 * No need to expand again unless we want a symtypes file entry
525 * for the symbol. Note that this means `sym` has the same address
526 * as another symbol that was already processed.
527 */
528 if (!symtypes && sym->state == SYMBOL_PROCESSED)
529 return;
530
531 if (__die_map_get(sym->die_addr, DIE_SYMBOL, &cache))
532 return; /* We'll warn about missing CRCs later. */
533
534 type_expand(sym->name, cache, &type);
535
536 /* If the symbol already has a version, don't calculate it again. */
537 if (sym->state != SYMBOL_PROCESSED) {
538 calculate_version(&version, &type);
539 symbol_set_crc(sym, version.crc);
540 debug("%s = %lx", sym->name, version.crc);
541
542 if (dump_versions) {
543 checkp(fputs(sym->name, stderr));
544 checkp(fputs(" ", stderr));
545 type_list_write(&version.type.expanded, stderr);
546 checkp(fputs("\n", stderr));
547 }
548
549 version_free(&version);
550 }
551
552 /* These aren't needed in type_map unless we want a symtypes file. */
553 if (symtypes)
554 type_map_add(sym->name, &type);
555
556 type_expansion_free(&type);
557}
558
559void generate_symtypes_and_versions(FILE *file)
560{
561 cache_init(&expansion_cache);
562
563 /*
564 * die_map processing:
565 *
566 * 1. die_map contains all types referenced in exported symbol
567 * signatures, but can contain duplicates just like the original
568 * DWARF, and some references may not be fully expanded depending
569 * on how far we processed the DIE tree for that specific symbol.
570 *
571 * For each die_map entry, find the longest available expansion,
572 * and add it to type_map.
573 */
574 die_map_for_each(expand_type, NULL);
575
576 /*
577 * 2. For each exported symbol, expand the die_map type, and use
578 * type_map expansions to calculate a symbol version from the
579 * fully expanded type string.
580 */
581 symbol_for_each(expand_symbol, NULL);
582
583 /*
584 * 3. If a symtypes file is requested, write type_map contents to
585 * the file.
586 */
587 type_map_write(file);
588 type_map_free();
589}