path: root/tools/lib/bpf/btf_dump.c

// SPDX-License-Identifier: (LGPL-2.1 OR BSD-2-Clause)

/*
 * BTF-to-C type converter.
 *
 * Copyright (c) 2019 Facebook
 */

#include <stdbool.h>
#include <stddef.h>
#include <stdlib.h>
#include <string.h>
#include <errno.h>
#include <linux/err.h>
#include <linux/btf.h>
#include <linux/kernel.h>
#include "btf.h"
#include "hashmap.h"
#include "libbpf.h"
#include "libbpf_internal.h"

static const char PREFIXES[] = "\t\t\t\t\t\t\t\t\t\t\t\t\t";
static const size_t PREFIX_CNT = sizeof(PREFIXES) - 1;

static const char *pfx(int lvl)
{
	return lvl >= PREFIX_CNT ? PREFIXES : &PREFIXES[PREFIX_CNT - lvl];
}

enum btf_dump_type_order_state {
	NOT_ORDERED,
	ORDERING,
	ORDERED,
};

enum btf_dump_type_emit_state {
	NOT_EMITTED,
	EMITTING,
	EMITTED,
};

/* per-type auxiliary state */
struct btf_dump_type_aux_state {
	/* topological sorting state */
	enum btf_dump_type_order_state order_state: 2;
	/* emitting state used to determine the need for forward declaration */
	enum btf_dump_type_emit_state emit_state: 2;
	/* whether forward declaration was already emitted */
	__u8 fwd_emitted: 1;
	/* whether unique non-duplicate name was already assigned */
	__u8 name_resolved: 1;
	/* whether type is referenced from any other type */
	__u8 referenced: 1;
};

struct btf_dump {
	const struct btf *btf;
	const struct btf_ext *btf_ext;
	btf_dump_printf_fn_t printf_fn;
	struct btf_dump_opts opts;
	int ptr_sz;
	bool strip_mods;
	int last_id;

	/* per-type auxiliary state */
	struct btf_dump_type_aux_state *type_states;
	size_t type_states_cap;
	/* per-type optional cached unique name, must be freed, if present */
	const char **cached_names;
	size_t cached_names_cap;

	/* topo-sorted list of dependent type definitions */
	__u32 *emit_queue;
	int emit_queue_cap;
	int emit_queue_cnt;

	/*
	 * stack of type declarations (e.g., chain of modifiers, arrays,
	 * funcs, etc)
	 */
	__u32 *decl_stack;
	int decl_stack_cap;
	int decl_stack_cnt;

	/* maps struct/union/enum name to a number of name occurrences */
	struct hashmap *type_names;
	/*
	 * maps typedef identifiers and enum value names to a number of such
	 * name occurrences
	 */
	struct hashmap *ident_names;
};

static size_t str_hash_fn(const void *key, void *ctx)
{
	return str_hash(key);
}

static bool str_equal_fn(const void *a, const void *b, void *ctx)
{
	return strcmp(a, b) == 0;
}

static const char *btf_name_of(const struct btf_dump *d, __u32 name_off)
{
	return btf__name_by_offset(d->btf, name_off);
}

static void btf_dump_printf(const struct btf_dump *d, const char *fmt, ...)
{
	va_list args;

	va_start(args, fmt);
	d->printf_fn(d->opts.ctx, fmt, args);
	va_end(args);
}

static int btf_dump_mark_referenced(struct btf_dump *d);
static int btf_dump_resize(struct btf_dump *d);

struct btf_dump *btf_dump__new(const struct btf *btf,
			       const struct btf_ext *btf_ext,
			       const struct btf_dump_opts *opts,
			       btf_dump_printf_fn_t printf_fn)
{
	struct btf_dump *d;
	int err;

	d = calloc(1, sizeof(struct btf_dump));
	if (!d)
		return ERR_PTR(-ENOMEM);

	d->btf = btf;
	d->btf_ext = btf_ext;
	d->printf_fn = printf_fn;
	d->opts.ctx = opts ? opts->ctx : NULL;
	d->ptr_sz = btf__pointer_size(btf) ? : sizeof(void *);

	d->type_names = hashmap__new(str_hash_fn, str_equal_fn, NULL);
	if (IS_ERR(d->type_names)) {
		err = PTR_ERR(d->type_names);
		d->type_names = NULL;
		goto err;
	}
	d->ident_names = hashmap__new(str_hash_fn, str_equal_fn, NULL);
	if (IS_ERR(d->ident_names)) {
		err = PTR_ERR(d->ident_names);
		d->ident_names = NULL;
		goto err;
	}

	err = btf_dump_resize(d);
	if (err)
		goto err;

	return d;
err:
	btf_dump__free(d);
	return ERR_PTR(err);
}

static int btf_dump_resize(struct btf_dump *d)
{
	int err, last_id = btf__get_nr_types(d->btf);

	if (last_id <= d->last_id)
		return 0;

	if (btf_ensure_mem((void **)&d->type_states, &d->type_states_cap,
			   sizeof(*d->type_states), last_id + 1))
		return -ENOMEM;
	if (btf_ensure_mem((void **)&d->cached_names, &d->cached_names_cap,
			   sizeof(*d->cached_names), last_id + 1))
		return -ENOMEM;

	if (d->last_id == 0) {
		/* VOID is special */
		d->type_states[0].order_state = ORDERED;
		d->type_states[0].emit_state = EMITTED;
	}

	/* eagerly determine referenced types for anon enums */
	err = btf_dump_mark_referenced(d);
	if (err)
		return err;

	d->last_id = last_id;
	return 0;
}

static void btf_dump_free_names(struct hashmap *map)
{
	size_t bkt;
	struct hashmap_entry *cur;

	if (!map)
		return;

	hashmap__for_each_entry(map, cur, bkt)
		free((void *)cur->key);

	hashmap__free(map);
}

void btf_dump__free(struct btf_dump *d)
{
	int i;

	if (IS_ERR_OR_NULL(d))
		return;

	free(d->type_states);
	if (d->cached_names) {
		/* any set cached name is owned by us and should be freed */
		for (i = 0; i <= d->last_id; i++) {
			if (d->cached_names[i])
				free((void *)d->cached_names[i]);
		}
	}
	free(d->cached_names);
	free(d->emit_queue);
	free(d->decl_stack);
	btf_dump_free_names(d->type_names);
	btf_dump_free_names(d->ident_names);

	free(d);
}

static int btf_dump_order_type(struct btf_dump *d, __u32 id, bool through_ptr);
static void btf_dump_emit_type(struct btf_dump *d, __u32 id, __u32 cont_id);

/*
 * Dump BTF type in a compilable C syntax, including all the necessary
 * dependent types, necessary for compilation. If some of the dependent types
 * were already emitted as part of previous btf_dump__dump_type() invocation
 * for another type, they won't be emitted again. This API allows callers to
 * filter out BTF types according to user-defined criterias and emitted only
 * minimal subset of types, necessary to compile everything. Full struct/union
 * definitions will still be emitted, even if the only usage is through
 * pointer and could be satisfied with just a forward declaration.
 *
 * Dumping is done in two high-level passes:
 *   1. Topologically sort type definitions to satisfy C rules of compilation.
 *   2. Emit type definitions in C syntax.
 *
 * Returns 0 on success; <0, otherwise.
 */
int btf_dump__dump_type(struct btf_dump *d, __u32 id)
{
	int err, i;

	if (id > btf__get_nr_types(d->btf))
		return -EINVAL;

	err = btf_dump_resize(d);
	if (err)
		return err;

	d->emit_queue_cnt = 0;
	err = btf_dump_order_type(d, id, false);
	if (err < 0)
		return err;

	for (i = 0; i < d->emit_queue_cnt; i++)
		btf_dump_emit_type(d, d->emit_queue[i], 0 /*top-level*/);

	return 0;
}

/*
 * Mark all types that are referenced from any other type. This is used to
 * determine top-level anonymous enums that need to be emitted as an
 * independent type declarations.
 * Anonymous enums come in two flavors: either embedded in a struct's field
 * definition, in which case they have to be declared inline as part of field
 * type declaration; or as a top-level anonymous enum, typically used for
 * declaring global constants. It's impossible to distinguish between two
 * without knowning whether given enum type was referenced from other type:
 * top-level anonymous enum won't be referenced by anything, while embedded
 * one will.
 */
static int btf_dump_mark_referenced(struct btf_dump *d)
{
	int i, j, n = btf__get_nr_types(d->btf);
	const struct btf_type *t;
	__u16 vlen;

	for (i = d->last_id + 1; i <= n; i++) {
		t = btf__type_by_id(d->btf, i);
		vlen = btf_vlen(t);

		switch (btf_kind(t)) {
		case BTF_KIND_INT:
		case BTF_KIND_ENUM:
		case BTF_KIND_FWD:
			break;

		case BTF_KIND_VOLATILE:
		case BTF_KIND_CONST:
		case BTF_KIND_RESTRICT:
		case BTF_KIND_PTR:
		case BTF_KIND_TYPEDEF:
		case BTF_KIND_FUNC:
		case BTF_KIN