types.c

  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}