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

source code of linux/scripts/gendwarfksyms/types.c