/*

 * kmod-depmod - calculate modules.dep  using libkmod.

 *

 * Copyright (C) 2011-2013  ProFUSION embedded systems

 *

 * 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 2 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/>.

 */

#include <assert.h>

#include <ctype.h>

#include <dirent.h>

#include <errno.h>

#include <getopt.h>

#include <limits.h>

#include <regex.h>

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#include <unistd.h>

#include <sys/stat.h>

#include <sys/utsname.h>

#include <shared/array.h>

#include <shared/hash.h>

#include <shared/macro.h>

#include <shared/util.h>

#include <shared/scratchbuf.h>

#include <libkmod/libkmod-internal.h>

#undef ERR

#undef DBG

#include "kmod.h"

#define DEFAULT_VERBOSE LOG_WARNING

static int verbose = DEFAULT_VERBOSE;

static const char CFG_BUILTIN_KEY[] = "built-in";

static const char CFG_EXTERNAL_KEY[] = "external";

static const char *default_cfg_paths[] = {

	"/run/depmod.d",

	SYSCONFDIR "/depmod.d",

	"/lib/depmod.d",

	NULL

};

static const char cmdopts_s[] = "aAb:C:E:F:euqrvnP:wmVh";

static const struct option cmdopts[] = {

	{ "all", no_argument, 0, 'a' },

	{ "quick", no_argument, 0, 'A' },

	{ "basedir", required_argument, 0, 'b' },

	{ "config", required_argument, 0, 'C' },

	{ "symvers", required_argument, 0, 'E' },

	{ "filesyms", required_argument, 0, 'F' },

	{ "errsyms", no_argument, 0, 'e' },

	{ "unresolved-error", no_argument, 0, 'u' }, /* deprecated */

	{ "quiet", no_argument, 0, 'q' }, /* deprecated */

	{ "root", no_argument, 0, 'r' }, /* deprecated */

	{ "verbose", no_argument, 0, 'v' },

	{ "show", no_argument, 0, 'n' },

	{ "dry-run", no_argument, 0, 'n' },

	{ "symbol-prefix", required_argument, 0, 'P' },

	{ "warn", no_argument, 0, 'w' },

	{ "map", no_argument, 0, 'm' }, /* deprecated */

	{ "version", no_argument, 0, 'V' },

	{ "help", no_argument, 0, 'h' },

	{ }

};

static void help(void)

{

	printf("Usage:\n"

		"\t%s -[aA] [options] [forced_version]\n"

		"\n"

		"If no arguments (except options) are given, \"depmod -a\" is assumed\n"

		"\n"

		"depmod will output a dependency list suitable for the modprobe utility.\n"

		"\n"

		"Options:\n"

		"\t-a, --all            Probe all modules\n"

		"\t-A, --quick          Only does the work if there's a new module\n"

		"\t-e, --errsyms        Report not supplied symbols\n"

		"\t-n, --show           Write the dependency file on stdout only\n"

		"\t-P, --symbol-prefix  Architecture symbol prefix\n"

		"\t-C, --config=PATH    Read configuration from PATH\n"

		"\t-v, --verbose        Enable verbose mode\n"

		"\t-w, --warn           Warn on duplicates\n"

		"\t-V, --version        show version\n"

		"\t-h, --help           show this help\n"

		"\n"

		"The following options are useful for people managing distributions:\n"

		"\t-b, --basedir=DIR    Use an image of a module tree.\n"

		"\t-F, --filesyms=FILE  Use the file instead of the\n"

		"\t                     current kernel symbols.\n"

		"\t-E, --symvers=FILE   Use Module.symvers file to check\n"

		"\t                     symbol versions.\n",

		program_invocation_short_name);

}

_printf_format_(1, 2)

static inline void _show(const char *fmt, ...)

{

	va_list args;

	if (verbose <= DEFAULT_VERBOSE)

		return;

	va_start(args, fmt);

	vfprintf(stdout, fmt, args);

	fflush(stdout);

	va_end(args);

}

#define SHOW(...) _show(__VA_ARGS__)

/* binary index write *************************************************/

#include <arpa/inet.h>

/* BEGIN: code from module-init-tools/index.c just modified to compile here.

 *

 * Original copyright:

 *   index.c: module index file shared functions for modprobe and depmod

 *   Copyright (C) 2008  Alan Jenkins <alan-jenkins@tuffmail.co.uk>.

 *

 *   These programs are 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 2 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 these programs.  If not, see <http://www.gnu.org/licenses/>.

 */

/* see documentation in libkmod/libkmod-index.c */

#define INDEX_MAGIC 0xB007F457

#define INDEX_VERSION_MAJOR 0x0002

#define INDEX_VERSION_MINOR 0x0001

#define INDEX_VERSION ((INDEX_VERSION_MAJOR<<16)|INDEX_VERSION_MINOR)

#define INDEX_CHILDMAX 128

struct index_value {

	struct index_value *next;

	unsigned int priority;

	char value[0];

};

/* In-memory index (depmod only) */

struct index_node {

	char *prefix;		/* path compression */

	struct index_value *values;

	unsigned char first;	/* range of child nodes */

	unsigned char last;

	struct index_node *children[INDEX_CHILDMAX]; /* indexed by character */

};

/* Format of node offsets within index file */

enum node_offset {

	INDEX_NODE_FLAGS    = 0xF0000000, /* Flags in high nibble */

	INDEX_NODE_PREFIX   = 0x80000000,

	INDEX_NODE_VALUES = 0x40000000,

	INDEX_NODE_CHILDS   = 0x20000000,

	INDEX_NODE_MASK     = 0x0FFFFFFF, /* Offset value */

};

static struct index_node *index_create(void)

{

	struct index_node *node;

	node = NOFAIL(calloc(sizeof(struct index_node), 1));

	node->prefix = NOFAIL(strdup(""));

	node->first = INDEX_CHILDMAX;

	return node;

}

static void index_values_free(struct index_value *values)

{

	while (values) {

		struct index_value *value = values;

		values = value->next;

		free(value);

	}

}

static void index_destroy(struct index_node *node)

{

	int c;

	for (c = node->first; c <= node->last; c++) {

		struct index_node *child = node->children[c];

		if (child)

			index_destroy(child);

	}

	index_values_free(node->values);

	free(node->prefix);

	free(node);

}

static void index__checkstring(const char *str)

{

	int i;

	for (i = 0; str[i]; i++) {

		int ch = str[i];

		if (ch >= INDEX_CHILDMAX)

			CRIT("Module index: bad character '%c'=0x%x - only 7-bit ASCII is supported:"

			      "\n%s\n", (char) ch, (int) ch, str);

	}

}

static int index_add_value(struct index_value **values,

				const char *value, unsigned int priority)

{

	struct index_value *v;

	int duplicate = 0;

	int len;

	/* report the presence of duplicate values */

	for (v = *values; v; v = v->next) {

		if (streq(v->value, value))

			duplicate = 1;

	}

	/* find position to insert value */

	while (*values && (*values)->priority < priority)

		values = &(*values)->next;

	len = strlen(value);

	v = NOFAIL(calloc(sizeof(struct index_value) + len + 1, 1));

	v->next = *values;

	v->priority = priority;

	memcpy(v->value, value, len + 1);

	*values = v;

	return duplicate;

}

static int index_insert(struct index_node *node, const char *key,

			const char *value, unsigned int priority)

{

	int i = 0; /* index within str */

	int ch;

	index__checkstring(key);

	index__checkstring(value);

	while(1) {

		int j; /* index within node->prefix */

		/* Ensure node->prefix is a prefix of &str[i].

		   If it is not already, then we must split node. */

		for (j = 0; node->prefix[j]; j++) {

			ch = node->prefix[j];

			if (ch != key[i+j]) {

				char *prefix = node->prefix;

				struct index_node *n;

				/* New child is copy of node with prefix[j+1..N] */

				n = NOFAIL(calloc(sizeof(struct index_node), 1));

				memcpy(n, node, sizeof(struct index_node));

				n->prefix = NOFAIL(strdup(&prefix[j+1]));

				/* Parent has prefix[0..j], child at prefix[j] */

				memset(node, 0, sizeof(struct index_node));

				prefix[j] = '\0';

				node->prefix = prefix;

				node->first = ch;

				node->last = ch;

				node->children[ch] = n;

				break;

			}

		}

		/* j is now length of node->prefix */

		i += j;

		ch = key[i];

		if(ch == '\0')

			return index_add_value(&node->values, value, priority);

		if (!node->children[ch]) {

			struct index_node *child;

			if (ch < node->first)

				node->first = ch;

			if (ch > node->last)

				node->last = ch;

			node->children[ch] = NOFAIL(calloc(sizeof(struct index_node), 1));

			child = node->children[ch];

			child->prefix = NOFAIL(strdup(&key[i+1]));

			child->first = INDEX_CHILDMAX;

			index_add_value(&child->values, value, priority);

			return 0;

		}

		/* Descend into child node and continue */

		node = node->children[ch];

		i++;

	}

}

static int index__haschildren(const struct index_node *node)

{

	return node->first < INDEX_CHILDMAX;

}

/* Recursive post-order traversal

   Pre-order would make for better read-side buffering / readahead / caching.

   (post-order means you go backwards in the file as you descend the tree).

   However, index reading is already fast enough.

   Pre-order is simpler for writing, and depmod is already slow.

 */

static uint32_t index_write__node(const struct index_node *node, FILE *out)

{

	uint32_t *child_offs = NULL;

	int child_count = 0;

	long offset;

	if (!node)

		return 0;

	/* Write children and save their offsets */

	if (index__haschildren(node)) {

		const struct index_node *child;

		int i;

		child_count = node->last - node->first + 1;

		child_offs = NOFAIL(malloc(child_count * sizeof(uint32_t)));

		for (i = 0; i < child_count; i++) {

			child = node->children[node->first + i];

			child_offs[i] = htonl(index_write__node(child, out));

		}

	}

	/* Now write this node */

	offset = ftell(out);

	if (node->prefix[0]) {

		fputs(node->prefix, out);

		fputc('\0', out);

		offset |= INDEX_NODE_PREFIX;

	}

	if (child_count) {

		fputc(node->first, out);

		fputc(node->last, out);

		fwrite(child_offs, sizeof(uint32_t), child_count, out);

		offset |= INDEX_NODE_CHILDS;

	}

	free(child_offs);

	if (node->values) {

		const struct index_value *v;

		unsigned int value_count;

		uint32_t u;

		value_count = 0;

		for (v = node->values; v != NULL; v = v->next)

			value_count++;

		u = htonl(value_count);

		fwrite(&u, sizeof(u), 1, out);

		for (v = node->values; v != NULL; v = v->next) {

			u = htonl(v->priority);

			fwrite(&u, sizeof(u), 1, out);

			fputs(v->value, out);

			fputc('\0', out);

		}

		offset |= INDEX_NODE_VALUES;

	}

	return offset;

}

static void index_write(const struct index_node *node, FILE *out)

{

	long initial_offset, final_offset;

	uint32_t u;

	u = htonl(INDEX_MAGIC);

	fwrite(&u, sizeof(u), 1, out);

	u = htonl(INDEX_VERSION);

	fwrite(&u, sizeof(u), 1, out);

	/* Second word is reserved for the offset of the root node */

	initial_offset = ftell(out);

	assert(initial_offset >= 0);

	u = 0;

	fwrite(&u, sizeof(uint32_t), 1, out);

	/* Dump trie */

	u = htonl(index_write__node(node, out));

	/* Update first word */

	final_offset = ftell(out);

	assert(final_offset >= 0);

	(void)fseek(out, initial_offset, SEEK_SET);

	fwrite(&u, sizeof(uint32_t), 1, out);

	(void)fseek(out, final_offset, SEEK_SET);

}

/* END: code from module-init-tools/index.c just modified to compile here.

 */

/* configuration parsing **********************************************/

struct cfg_override {

	struct cfg_override *next;

	size_t len;

	char path[];

};

enum search_type {

	SEARCH_PATH,

	SEARCH_BUILTIN,

	SEARCH_EXTERNAL

};

struct cfg_search {

	struct cfg_search *next;

	enum search_type type;

	size_t len;

	char path[];

};

struct cfg_external {

	struct cfg_external *next;

	size_t len;

	char path[];

};

struct cfg {

	const char *kversion;

	char dirname[PATH_MAX];

	size_t dirnamelen;

	char sym_prefix;

	uint8_t check_symvers;

	uint8_t print_unknown;

	uint8_t warn_dups;

	struct cfg_override *overrides;

	struct cfg_search *searches;

	struct cfg_external *externals;

};

static enum search_type cfg_define_search_type(const char *path)

{

	if (streq(path, CFG_BUILTIN_KEY))

		return SEARCH_BUILTIN;

	if (streq(path, CFG_EXTERNAL_KEY))

		return SEARCH_EXTERNAL;

	return SEARCH_PATH;

}

static int cfg_search_add(struct cfg *cfg, const char *path)

{

	struct cfg_search *s;

	size_t len;

	enum search_type type;

	type = cfg_define_search_type(path);

	if (type != SEARCH_PATH)

		len = 0;

	else

		len = strlen(path) + 1;

	s = malloc(sizeof(struct cfg_search) + len);

	if (s == NULL) {

		ERR("search add: out of memory\n");

		return -ENOMEM;

	}

	s->type = type;

	if (type != SEARCH_PATH)

		s->len = 0;

	else {

		s->len = len - 1;

		memcpy(s->path, path, len);

	}

	DBG("search add: %s, search type=%hhu\n", path, type);

	s->next = cfg->searches;

	cfg->searches = s;

	return 0;

}

static void cfg_search_free(struct cfg_search *s)

{

	free(s);

}

static int cfg_override_add(struct cfg *cfg, const char *modname, const char *subdir)

{

	struct cfg_override *o;

	size_t modnamelen = strlen(modname);

	size_t subdirlen = strlen(subdir);

	size_t i;

	o = malloc(sizeof(struct cfg_override) + subdirlen + 1

		   + modnamelen + 1);

	if (o == NULL) {

		ERR("override add: out of memory\n");

		return -ENOMEM;

	}

	memcpy(o->path, subdir, subdirlen);

	i = subdirlen;

	o->path[i] = '/';

	i++;

	memcpy(o->path + i, modname, modnamelen);

	i += modnamelen;

	o->path[i] = '\0'; /* no extension, so we can match .ko/.ko.gz */

	o->len = i;

	DBG("override add: %s\n", o->path);

	o->next = cfg->overrides;

	cfg->overrides = o;

	return 0;

}

static void cfg_override_free(struct cfg_override *o)

{

	free(o);

}

static int cfg_external_add(struct cfg *cfg, const char *path)

{

	struct cfg_external *ext;

	size_t len = strlen(path);

	ext = malloc(sizeof(struct cfg_external) + len + 1);

	if (ext == NULL) {

		ERR("external add: out of memory\n");

		return -ENOMEM;

	}

	strcpy(ext->path, path);

	ext->len = len;

	DBG("external add: %s\n", ext->path);

	ext->next = cfg->externals;

	cfg->externals = ext;

	return 0;

}

static void cfg_external_free(struct cfg_external *ext)

{

	free(ext);

}

static int cfg_kernel_matches(const struct cfg *cfg, const char *pattern)

{

	regex_t re;

	int status;

	/* old style */

	if (streq(pattern, "*"))

		return 1;

	if (regcomp(&re, pattern, REG_EXTENDED|REG_NOSUB) != 0)

		return 0;

	status = regexec(&re, cfg->kversion, 0, NULL, 0);

	regfree(&re);

	return status == 0;

}

static int cfg_file_parse(struct cfg *cfg, const char *filename)

{

	char *line;

	FILE *fp;

	unsigned int linenum = 0;

	int err;

	fp = fopen(filename, "r");

	if (fp == NULL) {

		err = -errno;

		ERR("file parse %s: %m\n", filename);

		return err;

	}

	while ((line = freadline_wrapped(fp, &linenum)) != NULL) {

		char *cmd, *saveptr;

		if (line[0] == '\0' || line[0] == '#')

			goto done_next;

		cmd = strtok_r(line, "\t ", &saveptr);

		if (cmd == NULL)

			goto done_next;

		if (streq(cmd, "search")) {

			const char *sp;

			while ((sp = strtok_r(NULL, "\t ", &saveptr)) != NULL) {

				cfg_search_add(cfg, sp);

			}

		} else if (streq(cmd, "override")) {

			const char *modname = strtok_r(NULL, "\t ", &saveptr);

			const char *version = strtok_r(NULL, "\t ", &saveptr);

			const char *subdir = strtok_r(NULL, "\t ", &saveptr);

			if (modname == NULL || version == NULL ||

					subdir == NULL)

				goto syntax_error;

			if (!cfg_kernel_matches(cfg, version)) {

				INF("%s:%u: override kernel did not match %s\n",

				    filename, linenum, version);

				goto done_next;

			}

			cfg_override_add(cfg, modname, subdir);

		} else if (streq(cmd, "external")) {

			const char *version = strtok_r(NULL, "\t ", &saveptr);

			const char *dir = strtok_r(NULL, "\t ", &saveptr);

			if (version == NULL || dir == NULL)

				goto syntax_error;

			if (!cfg_kernel_matches(cfg, version)) {

				INF("%s:%u: external directory did not match %s\n",

				    filename, linenum, version);

				goto done_next;

			}

			cfg_external_add(cfg, dir);

		} else if (streq(cmd, "include")

				|| streq(cmd, "make_map_files")) {

			INF("%s:%u: command %s not implemented yet\n",

			    filename, linenum, cmd);

		} else {

syntax_error:

			ERR("%s:%u: ignoring bad line starting with '%s'\n",

			    filename, linenum, cmd);

		}

done_next:

		free(line);

	}

	fclose(fp);

	return 0;

}

static int cfg_files_filter_out(DIR *d, const char *dir, const char *name)

{

	size_t len = strlen(name);

	struct stat st;

	if (name[0] == '.')

		return 1;

	if (len < 6 || !streq(name + len - 5, ".conf")) {

		INF("All cfg files need .conf: %s/%s\n", dir, name);

		return 1;

	}

	fstatat(dirfd(d), name, &st, 0);

	if (S_ISDIR(st.st_mode)) {

		ERR("Directories inside directories are not supported: %s/%s\n",

		    dir, name);

		return 1;

	}

	return 0;

}

struct cfg_file {

	size_t dirlen;

	size_t namelen;

	const char *name;

	char path[];

};

static void cfg_file_free(struct cfg_file *f)

{

	free(f);

}

static int cfg_files_insert_sorted(struct cfg_file ***p_files, size_t *p_n_files,

					const char *dir, const char *name)

{

	struct cfg_file **files, *f;

	size_t i, n_files, namelen, dirlen;

	void *tmp;

	dirlen = strlen(dir);

	if (name != NULL)

		namelen = strlen(name);

	else {

		name = basename(dir);

		namelen = strlen(name);

		dirlen -= namelen + 1;

	}

	n_files = *p_n_files;

	files = *p_files;

	for (i = 0; i < n_files; i++) {

		int cmp = strcmp(name, files[i]->name);

		if (cmp == 0) {

			DBG("Ignoring duplicate config file: %.*s/%s\n",

			    (int)dirlen, dir, name);

			return -EEXIST;

		} else if (cmp < 0)

			break;

	}

	f = malloc(sizeof(struct cfg_file) + dirlen + namelen + 2);

	if (f == NULL) {

		ERR("files insert sorted: out of memory\n");

		return -ENOMEM;

	}

	tmp = realloc(files, sizeof(struct cfg_file *) * (n_files + 1));

	if (tmp == NULL) {

		ERR("files insert sorted: out of memory\n");

		free(f);

		return -ENOMEM;

	}

	*p_files = files = tmp;

	if (i < n_files) {

		memmove(files + i + 1, files + i,

			sizeof(struct cfg_file *) * (n_files - i));

	}

	files[i] = f;

	f->dirlen = dirlen;

	f->namelen = namelen;

	f->name = f->path + dirlen + 1;

	memcpy(f->path, dir, dirlen);

	f->path[dirlen] = '/';

	memcpy(f->path + dirlen + 1, name, namelen);

	f->path[dirlen + 1 + namelen] = '\0';

	*p_n_files = n_files + 1;

	return 0;

}

/*

 * Insert configuration files ignoring duplicates

 */

static int cfg_files_list(struct cfg_file ***p_files, size_t *p_n_files,

				const char *path)

{

	struct dirent *dent;

	DIR *d;

	int err = 0;

	struct stat st;

	if (stat(path, &st) != 0) {

		err = -errno;

		DBG("could not stat '%s': %m\n", path);

		return err;

	}

	if (!S_ISDIR(st.st_mode)) {

		cfg_files_insert_sorted(p_files, p_n_files, path, NULL);

		return 0;

	}

	d = opendir(path);

	if (d == NULL) {

		ERR("files list %s: %m\n", path);

		return -EINVAL;

	}

	for (dent = readdir(d); dent != NULL; dent = readdir(d)) {

		if (cfg_files_filter_out(d, path, dent->d_name))

			continue;

		cfg_files_insert_sorted(p_files, p_n_files, path, dent->d_name);

	}

	closedir(d);

	DBG("parsed configuration files from %s\n", path);

	return err;

}

static int cfg_load(struct cfg *cfg, const char * const *cfg_paths)

{

	size_t i, n_files = 0;

	struct cfg_file **files = NULL;

	if (cfg_paths == NULL)

		cfg_paths = default_cfg_paths;

	for (i = 0; cfg_paths[i] != NULL; i++)

		cfg_files_list(&files, &n_files, cfg_paths[i]);

	for (i = 0; i < n_files; i++) {

		struct cfg_file *f = files[i];

		cfg_file_parse(cfg, f->path);

		cfg_file_free(f);

	}

	free(files);

	/* For backward compatibility add "updates" to the head of the search

	 * list here. But only if there was no "search" option specified.

	 */

	if (cfg->searches == NULL)

		cfg_search_add(cfg, "updates");

	return 0;

}

static void cfg_free(struct cfg *cfg)

{

	while (cfg->overrides) {

		struct cfg_override *tmp = cfg->overrides;

		cfg->overrides = cfg->overrides->next;

		cfg_override_free(tmp);

	}

	while (cfg->searches) {

		struct cfg_search *tmp = cfg->searches;

		cfg->searches = cfg->searches->next;

		cfg_search_free(tmp);

	}

	while (cfg->externals) {

		struct cfg_external *tmp = cfg->externals;

		cfg->externals = cfg->externals->next;

		cfg_external_free(tmp);

	}

}

/* depmod calculations ***********************************************/

struct vertex;

struct mod {

	struct kmod_module *kmod;

	char *path;

	const char *relpath; /* path relative to '$ROOT/lib/modules/$VER/' */

	char *uncrelpath; /* same as relpath but ending in .ko */

	struct kmod_list *info_list;

	struct kmod_list *dep_sym_list;

	struct array deps; /* struct symbol */

	size_t baselen; /* points to start of basename/filename */

	size_t modnamesz;

	int sort_idx; /* sort index using modules.order */

	int dep_sort_idx; /* topological sort index */

	uint16_t idx; /* index in depmod->modules.array */

	uint16_t users; /* how many modules depend on this one */

	bool visited; /* helper field to report cycles */

	struct vertex *vertex; /* helper field to report cycles */

	char modname[];

};