/*

	Copyright(C) 2016, Red Hat, Inc., Stanislav Kozina

	This program is free software: you can redistribute it and/or modify

	it under the terms of the GNU General Public License as published by

	the Free Software Foundation, either version 3 of the License, or

	(at your option) any later version.

	This program is distributed in the hope that it will be useful,

	but WITHOUT ANY WARRANTY; without even the implied warranty of

	MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the

	GNU General Public License for more details.

	You should have received a copy of the GNU General Public License

	along with this program.  If not, see <http://www.gnu.org/licenses/>.

*/

/*

 * This file contains the code which generates the kabi information for the

 * given build of the Linux kernel.

 */

#include <dwarf.h>

#include <inttypes.h>

#include <ctype.h>

#include <libelf.h>

#include <fcntl.h>

#include <stdio.h>

#include <string.h>

#include <sys/types.h>

#include <sys/stat.h>

#include <unistd.h>

#include <stdlib.h>

#include <errno.h>

#include <assert.h>

#include <getopt.h>

#include <limits.h>

#include <elfutils/libdw.h>

#include <elfutils/libdwfl.h>

#include <elfutils/known-dwarf.h>

#include "main.h"

#include "utils.h"

#include "generate.h"

#include "ksymtab.h"

#include "stack.h"

#include "hash.h"

#include "objects.h"

#include "list.h"

#define	EMPTY_NAME	"(NULL)"

#define PROCESSED_SIZE 1024

/*

  DB size is number of hash buckets, do not have to be exact,

  but since now we have ~20K records, make it this

*/

#define DB_SIZE (20 * 1024)

#define INITIAL_RECORD_SIZE 512

/*

 * Dwarf5 spec, 7.5.4 Attribute Encodings

 * libdw doesn't support it yet

 */

#ifndef DW_AT_alignment

#define DW_AT_alignment 0x88

#endif

struct set;

struct record_db;

typedef struct {

	char *kernel_dir; /* Path to  the kernel modules to process */

	char *kabi_dir; /* Where to put the output */

	struct ksymtab *symbols; /* List of symbols to generate */

	size_t symbol_cnt;

	struct record_db *db;

	bool rhel_tree;

	bool verbose;

	bool gen_extra;

} generate_config_t;

struct cu_ctx {

	generate_config_t *conf;

	Dwarf_Die *cu_die;

	stack_t *stack; /* Current stack of symbol we're parsing */

	struct set *processed; /* Set of processed types for this CU */

};

struct file_ctx {

	generate_config_t *conf;

	struct ksymtab *ksymtab; /* ksymtab of the current kernel module */

};

struct dwarf_type {

	unsigned int dwarf_tag;

	char *prefix;

} known_dwarf_types[] = {

	{ DW_TAG_subprogram, FUNC_FILE },

	{ DW_TAG_typedef, TYPEDEF_FILE },

	{ DW_TAG_variable, VAR_FILE },

	{ DW_TAG_enumeration_type, ENUM_FILE },

	{ DW_TAG_structure_type, STRUCT_FILE },

	{ DW_TAG_union_type, UNION_FILE },

	{ 0, NULL }

};

/*

 * Structure of the database record:

 *

 * key: record key, usually includes path the file, where the type is

 *      defined (may include pseudo path, like <declaration>);

 *

 * version: type's version, used when we need to add another type of the same

 *	    name. It may happend, for example, when because of defines the same

 *          structure has changed for different compilation units.

 *

 *          It is not for the case, when the same structure defined in

 *	    different files -- it will have different keys, since it includes

 *	    the path;

 *

 * ref_count: reference counter, needed since the ownership is shared with the

 *            internal database;

 *

 * base_file: base part of the key (without version), used to generate the

 *            unique key for the new version;

 *

 * cu: compilation unit, where the type for the record defined;

 *

 * origin: "File <file>:<line>" string, describing the source, where the type

 *         for the record defined;

 *

 * stack: stack of types to reach this one.

 *         Ex.: on the toplevel

 *              struct A {

 *                        struct B fieldA;

 *              }

 *         in another file:

 *              struct B {

 *                        basetype fieldB;

 *              }

 *         the "struct B" description will contain key of the "struct A"

 *         description record in the stack;

 *

 * obj: pointer to the abstract type object, representing the toplevel type of

 *      the record.

 *

 * link: name of weak link alisas for the weak aliases.

 *

 * free: type specific function to free the record

 *       (there are normal, weak and assembly records).

 *

 * dump: type specific function for record output.

 *

 * dependents: objects that reference this record.

 */

struct record {

	char *key;

	int version;

	int ref_count;

	char *base_file;

	char *cu;

	char *origin;

	stack_t *stack;

	obj_t *obj;

	char *link;

	void (*free)(struct record *);

	void (*dump)(struct record *, FILE *);

	struct list dependents;

};

void record_update_dependents(struct record *record)

{

	struct list_node *iter;

	LIST_FOR_EACH(&record->dependents, iter) {

		obj_t *obj = list_node_data(iter);

		free(obj->base_type);

		obj->base_type = safe_strdup(record->key);

	}

}

static const bool is_builtin(Dwarf_Die *die)

{

	char *fname;

	const char *path = dwarf_decl_file(die);

	if (path == NULL)

		return true;

	fname = basename(path);

	assert (fname != NULL);

	if (strcmp(fname, "<built-in>") == 0)

		return true;

	return false;

}

static const char *get_die_name(Dwarf_Die *die)

{

	if (dwarf_hasattr(die, DW_AT_name))

		return dwarf_diename(die);

	else

		return EMPTY_NAME;

}

/*

 * Check if given DIE has DW_AT_declaration attribute.

 * That indicates that the symbol is just a declaration, not full definition.

 */

static bool is_declaration(Dwarf_Die *die)

{

	Dwarf_Attribute attr;

	if (!dwarf_hasattr(die, DW_AT_declaration))

		return false;

	(void) dwarf_attr(die, DW_AT_declaration, &attr);

	if (!dwarf_hasform(&attr, DW_FORM_flag_present))

		return false;

	return true;

}

static char *get_file_replace_path;

static char *_get_file(Dwarf_Die *cu_die, Dwarf_Die *die)

{

	const char *filename;

	char *ret;

	filename = dwarf_decl_file(die);

	if (get_file_replace_path) {

		int len = strlen(get_file_replace_path);

		if (strncmp(filename, get_file_replace_path, len) == 0) {

			filename = filename + len;

			while (*filename == '/')

				filename++;

		}

	}

	ret = safe_strdup(filename);

	path_normalize(ret);

	return ret;

}

static char *get_file(Dwarf_Die *cu_die, Dwarf_Die *die)

{

	Dwarf_Attribute attr;

	Dwarf_Die spec_die;

	/*

	 * Handle types built-in in C compiler. These are for example the

	 * variable argument list which is defined as * struct __va_list_tag.

	 */

	if (is_builtin(die))

		return safe_strdup(BUILTIN_PATH);

	if (dwarf_hasattr(die, DW_AT_decl_file))

		return _get_file(cu_die, die);

	if ((dwarf_attr(die, DW_AT_specification, &attr) == NULL) ||

	    (dwarf_formref_die(&attr, &spec_die) == NULL)) {

		fail("DIE missing file information: %s\n",

		     dwarf_diename(die));

	}

	return _get_file(cu_die, &spec_die);

}

static long get_line(Dwarf_Die *cu_die, Dwarf_Die *die)

{

	Dwarf_Attribute attr;

	Dwarf_Word line;

	Dwarf_Die spec_die;

	if (is_builtin(die))

		return 0;

	if (dwarf_attr(die, DW_AT_decl_line, &attr) != NULL) {

		dwarf_formudata(&attr, &line);

		return line;

	}

	if ((dwarf_attr(die, DW_AT_specification, &attr) == NULL) ||

	    (dwarf_formref_die(&attr, &spec_die) == NULL)) {

		fail("DIE missing line information: %s\n",

		     dwarf_diename(die));

	}

	return get_line(cu_die, &spec_die);

}

static obj_t *print_die(struct cu_ctx *, struct record *, Dwarf_Die *);

static const char *dwarf_tag_string(unsigned int tag)

{

	switch (tag) {

#define	DWARF_ONE_KNOWN_DW_TAG(NAME, CODE) case CODE: return #NAME;

		DWARF_ALL_KNOWN_DW_TAG

#undef DWARF_ONE_KNOWN_DW_TAG

	default:

		return NULL;

	}

}

static char *get_file_prefix(unsigned int dwarf_tag)

{

	struct dwarf_type *current;

	for (current = known_dwarf_types; current->prefix != NULL; current++) {

		if (dwarf_tag == current->dwarf_tag)

			break;

	}

	return current->prefix;

}

static char *get_symbol_file(Dwarf_Die *die, Dwarf_Die *cu_die)

{

	const char *name = dwarf_diename(die);

	unsigned int tag = dwarf_tag(die);

	char *file_prefix;

	char *file_name = NULL;

	file_prefix = get_file_prefix(tag);

	if (file_prefix == NULL) {

		/* No need to redirect output for this type */

		return NULL;

	}

	/*

	 * DW_AT_declaration don't have DW_AT_decl_file.

	 * Pretend like it's in other, non existent file.

	 */

	if (is_declaration(die)) {

		safe_asprintf(&file_name, DECLARATION_PATH "/%s%s.txt",

		    file_prefix, name);

		return file_name;

	}

	/*

	 * Following types can be anonymous, eg. used directly as variable type

	 * in the declaration. We don't create new file for them if that's

	 * the case, embed them directly in the current file.

	 * Note that anonymous unions can also be embedded directly in the

	 * structure!

	 */

	switch (tag) {

	case DW_TAG_enumeration_type:

	case DW_TAG_structure_type:

	case DW_TAG_union_type:

		if (name == NULL)

			return NULL;

		break;

	}

	/* We don't expect our name to be empty now */

	assert(name != NULL);

	safe_asprintf(&file_name, "%s%s.txt", file_prefix, name);

	return file_name;

}

/*

 * Check if given DIE is external.

 * It can has DW_AT_external attribute itself,

 * or in case of reference to the specification,

 * the specification DIE can be exported.

 */

static int is_external(Dwarf_Die *die)

{

	Dwarf_Attribute attr;

	Dwarf_Die spec_die;

	if (dwarf_hasattr(die, DW_AT_external)) {

		dwarf_attr(die, DW_AT_external, &attr);

		if (!dwarf_hasform(&attr, DW_FORM_flag_present))

			return false;

		return true;

	}

	if (dwarf_attr(die, DW_AT_specification, &attr) == NULL)

		return false;

	if (dwarf_formref_die(&attr, &spec_die) == NULL)

		fail("dwarf_formref_die() failed for %s\n",

		     dwarf_diename(die));

	return is_external(&spec_die);

}

static obj_t *die_read_alignment(Dwarf_Die *die, obj_t *obj)

{

	Dwarf_Attribute attr;

	Dwarf_Word value;

	if (dwarf_attr(die, DW_AT_alignment, &attr) == NULL)

		goto out;

	dwarf_formudata(&attr, &value);

	obj->alignment = value;

out:

	return obj;

}

struct set *set_init(size_t size)

{

	struct hash *h;

	h = hash_new(size, free);

	if (h == NULL)

		fail("Cannot create hash");

	return (struct set *)h;

}

static void set_add(struct set *set, const char *key)

{

	char *storage;

	struct hash *h = (struct hash *)set;

	storage = safe_strdup(key);

	hash_add(h, storage, storage);

}

static bool set_contains(struct set *set, const char *key)

{

	void *v;

	struct hash *h = (struct hash *)set;

	v = hash_find(h, key);

	return v != NULL;

}

static void set_free(struct set *set)

{

	struct hash *h = (struct hash *)set;

	hash_free(h);

}

static struct record *record_alloc(void)

{

	struct record *rec;

	rec = safe_zmalloc(sizeof(*rec));

	return rec;

}

static void record_free_regular(struct record *rec)

{

	void *data;

	struct list_node *iter;

	free(rec->base_file);

	free(rec->origin);

	if (rec->cu)

		free(rec->cu);

	while ((data = stack_pop(rec->stack)) != NULL)

		free(data);

	stack_destroy(rec->stack);

	LIST_FOR_EACH(&rec->dependents, iter) {

		obj_t *o = list_node_data(iter);

		o->depend_rec_node = NULL;

	}

	list_clear(&rec->dependents);

	obj_free(rec->obj);

}

static void record_free_weak(struct record *rec)

{

	free(rec->link);

}

static void record_free(struct record *rec)

{

	free(rec->key);

	if (rec->free)

		rec->free(rec);

	free(rec);

}

static void record_put(struct record *rec)

{

	assert(rec->ref_count > 0);

	if (--rec->ref_count == 0)

		record_free(rec);

}

static void record_get(struct record *rec)

{

	rec->ref_count++;

}

static void record_dump_regular(struct record *rec, FILE *f);

static struct record *record_new_regular(const char *key)

{

	struct record *rec;

	rec = record_alloc();

	rec->key = safe_strdup(key);

	rec->stack = stack_init();

	rec->free = record_free_regular;

	rec->dump = record_dump_regular;

	list_init(&rec->dependents, NULL);

	record_get(rec);

	return rec;

}

static void record_dump_assembly(struct record *rec, FILE *f);

static struct record *record_new_assembly(const char *key)

{

	struct record *rec;

	rec = record_alloc();

	rec->key = safe_strdup(key);

	/*

	 * The symbol not necessary belongs to an assembly function,

	 * it is actually "no definition found in the debug information",

	 * but the main goal is to find the assembly ones.

	 */

	rec->free = NULL;

	rec->dump = record_dump_assembly;

	record_get(rec);

	return rec;

}

static void record_dump_weak(struct record *rec, FILE *f);

static struct record *record_new_weak(const char *key, const char *link)

{

	struct record *rec;

	rec = record_alloc();

	rec->key = safe_strdup(key);

	rec->link = safe_strdup(link);

	rec->free = record_free_weak;

	rec->dump = record_dump_weak;

	record_get(rec);

	return rec;

}

static obj_t *record_obj(struct record *rec)

{

	return rec->obj;

}

static obj_t *record_obj_exchange(struct record *rec, obj_t *o)

{

	obj_t *old;

	old = rec->obj;

	rec->obj = o;

	return old;

}

static const char *record_origin(struct record *rec)

{

	return rec->origin;

}

static void copy_stack_cb(void *data, void *arg)

{

	char *symbol = (char *)data;

	struct record *fp = (struct record *)arg;

	char *copy;

	copy = safe_strdup(symbol);

	stack_push(fp->stack, copy);

}

static void record_add_stack(struct record *rec, stack_t *stack)

{

	walk_stack_backward(stack, copy_stack_cb, rec);

}

static void record_add_cu(struct record *rec, Dwarf_Die *cu_die)

{

	const char *name;

	if (cu_die == NULL)

		return;

	name = dwarf_diename(cu_die);

	safe_asprintf(&rec->cu, "CU: \"%s\"\n", name);

}

static void record_add_origin(struct record *rec,

			      Dwarf_Die *cu_die,

			      Dwarf_Die *die)

{

	char *dec_file;

	long dec_line;

	dec_file = get_file(cu_die, die);

	dec_line = get_line(cu_die, die);

	safe_asprintf(&rec->origin, "File: %s:%lu\n", dec_file, dec_line);

	free(dec_file);

}

static struct record *record_start(struct cu_ctx *ctx,

				   Dwarf_Die *die,

				   char *key)

{

	struct record *rec = NULL;

	generate_config_t *conf = ctx->conf;

	Dwarf_Die *cu_die = ctx->cu_die;

	/*

	 * Don't try to reenter a file that we have seen already for

	 * this CU.

	 * Note that this is just a pure optimization, the same file

	 * (type) in the same CU must be identical.

	 * But this is major optimization, without it a single

	 * re-generation of a top file would require a full regeneration

	 * of its full tree, thus the difference in speed is many orders

	 * of magnitude!

	 */

	if (set_contains(ctx->processed, key))

		goto done;

	set_add(ctx->processed, key);

	if (is_declaration(die)) {

		if (conf->verbose)

			printf("WARNING: Skipping following file as we "

			       "have only declaration: %s\n", key);

		goto done;

	}

	if (conf->verbose)

		printf("Generating %s\n", key);

	rec = record_new_regular(key);

	if (conf->gen_extra)

		record_add_cu(rec, cu_die);

	record_add_origin(rec, cu_die, die);

	record_add_stack(rec, ctx->stack);

done:

	return rec;

}

static void record_set_version(struct record *rec, int version)

{

	char *base_file = rec->base_file;

	char *key = NULL;

	if (version == 0)

		return;

	if (rec->version == 0) {

		base_file = safe_strdup(rec->key);

		/* Remove .txt ending */

		base_file[strlen(base_file) - 4] = '\0';

		rec->base_file = base_file;

	}

	rec->version = version;

	safe_asprintf(&key, "%s-%i.txt", base_file, rec->version);

	free(rec->key);

	rec->key = key;

}

static void record_close(struct record *rec, obj_t *obj)

{

	obj_fill_parent(obj);

	rec->obj = obj;

}

static void record_stack_dump_and_clear(struct record *rec, FILE *f)

{

	char *data = stack_pop(rec->stack);

	if (data == NULL)

		return;

	fprintf(f, "Stack:\n");

	do {

		fprintf(f, "-> \"%s\"\n", data);

		free(data);

	} while ((data = stack_pop(rec->stack)) != NULL);

}

static void record_dump_regular(struct record *rec, FILE *f)

{

	int rc;

	fprintf(f, FILEFMT_VERSION_STRING);

	if (rec->cu != NULL) {

		rc = fputs(rec->cu, f);

		if (rc == EOF)

			fail("Could not put CU name");

	}

	rc = fputs(rec->origin, f);

	if (rc == EOF)

		fail("Could not put origin");

	record_stack_dump_and_clear(rec, f);

	fprintf(f, "Symbol:\n");

	if (rec->obj->alignment != 0)

		fprintf(f, "Alignment %u\n", rec->obj->alignment);

	obj_dump(rec->obj, f);

}

static void record_dump_assembly(struct record *rec, FILE *f)

{

	char *name = filenametosymbol(rec->key);

	int rc;

	rc = fprintf(f, FILEFMT_VERSION_STRING "Symbol:\nassembly %s\n", name);

	free(name);

	if (rc < 0)

		fail("Could not put assembly\n");

}

static void record_dump_weak(struct record *rec, FILE *f)

{

	char *name = filenametosymbol(rec->key);

	int rc;

	rc = fprintf(f, FILEFMT_VERSION_STRING "Symbol:\nweak %s -> %s\n",

		     name, rec->link);

	free(name);

	if (rc < 0)

		fail("Could not put weak link\n");

}

static void record_dump(struct record *rec, const char *dir)

{

	char path[PATH_MAX];

	FILE *f;

	char *slash;

	snprintf(path, sizeof(path), "%s/%s", dir, rec->key);

	slash = strrchr(path, '/');

	assert(slash != NULL);

	*slash = '\0';

	rec_mkdir(path);

	*slash = '/';

	f = fopen(path, "w");

	if (f == NULL)

		fail("Cannot create record file '%s': %m", path);

	rec->dump(rec, f);

	fclose(f);

}

static void list_record_free(void *value)

{

	struct record *rec = value;

	record_put(rec);

}

/*

 * merge rec_src to the record rec_dst

 */

static bool record_merge(struct record *rec_dst,

			 struct record *rec_src,

			 bool merge_decl)

{

	const char *s1;

	const char *s2;

	obj_t *o1;

	obj_t *o2;

	obj_t *o;

	s1 = record_origin(rec_dst);

	s2 = record_origin(rec_src);

	if (!safe_streq(s1, s2))

		return false;

	o1 = record_obj(rec_dst);

	o2 = record_obj(rec_src);

	o = obj_merge(o1, o2, merge_decl);

	if (o == NULL)

		return false;

	obj_fill_parent(o);

	o = record_obj_exchange(rec_dst, o);

	obj_free(o);

	return true;

}

static char *record_db_add(struct record_db *db, struct record *rec)

{

	/*

	 * Now we need to put the new type record we've just generated

	 * to the db.

	 *

	 * The problem stopping us from merging every record possible is that

	 * multiple records can't be merged if it is not possible to create

	 * groups in which they should be merged. This is not a problem if all

	 * the records are able to be merged together, but when there is one or

	 * more incompatible merging then merging them aggressively could group

	 * them in the wrong way. And because the right way to group them can't

	 * be decided, it is better not to group and subsequently merge them at

	 * all.

	 *

	 * Meaning that at this stage, when we don't know all the records, we

	 * can't decide if all records can be merged into one, and so the only

	 * records we can merge are those that are completely same.

	 *

	 * In case they aren't same we store them as another node of the list.

	 * We also change the name of the new record, so that two reffile obj_t

	 * referencing records that we couldn't merge wouldn't get merged.

	 */

	struct hash *hash = (struct hash *)db;

	struct record *tmp_rec;

	struct list *list;

	struct list_node *iter;

	list = hash_find(hash, rec->key);

	if (list == NULL) {

		list = list_new(list_record_free);

		hash_add(hash, rec->key, list);

	}

	LIST_FOR_EACH(list, iter) {

		tmp_rec = list_node_data(iter);

		if (record_merge(tmp_rec, rec, NO_MERGE_DECL)) {

			list_concat(&tmp_rec->dependents, &rec->dependents);

			return safe_strdup(tmp_rec->key);

		}

	}

	record_get(rec);

	record_set_version(rec, list->len);

	list_add(list, rec);

	return safe_strdup(rec->key);

}

static void hash_list_free(void *value)

{

	struct list *list = value;

	list_free(list);

}

static struct record_db *record_db_init(void)

{

	struct hash *db;

	db = hash_new(DB_SIZE, hash_list_free);

	if (db == NULL)