[MODALTS,v0.1,2/4] kmod: add generation of modules.alternatives to depmod

Commit Message

Valerii Chernous May 10, 2024, 11:21 a.m. UTC

algorithm of creating deps alternatives

1. for each module(m) creating hash map(mp) of module providers for required symbols(s)

2. for each required(primary) symbol(s) into module(m) create temp array of providers(p)
from list of symbol(s) alternatives with first elem into array as symbol(s)

3. get array of providers(pc) for owner(o) of symbol(s) from
hash map(mp) of module providers

4. if array of providers(pc) already presented
4.1 check is pc equal or subset of p, if yes leave pc into map(mp) and ignore p,
4.2 no - remove from temp array p all symbols providers that is not presenetd into pc
(create new set of providers p less or equal to pc(providers should cover all
required symbols, not only current symbol) and update hash map(mp) for owner(o)
to new(cutted) p

4.3 if array of providers(pc) is not presented for owner(o), create it

At the end of algorithm, for each primary dependency hash map(mp) contain modules
alternatives that provided all required symbols

Note:
Alternatives than not provide some required symbol(s) didn't trap to final list and
variant where this symbol provided by some other module ignored(not implemented)
Note:
modules.dep index different for standard/basic and modules alternatives algorithms
modules.dep for modules alternatives algorithm contain only direct dependencies
and full dependency list will be calculated into runtime correspond to
preferred alternative.
modules.dep for standard/basic algorithm contain full dependency list for
module and can't be changed during runtime without rebuild database via depmod

Cc: [e-mail]
Cc: Valerii Chernous <[e-mail]>
Signed-off-by: Valerii Chernous <[e-mail]>
---
 tools/depmod.c | 293 ++++++++++++++++++++++++++++++++++++++++++++++++-
 1 file changed, 290 insertions(+), 3 deletions(-)

Patch

diff --git a/tools/depmod.c b/tools/depmod.c
index 24f79c4..7bea8e9 100644
--- a/tools/depmod.c
+++ b/tools/depmod.c
@@ -919,6 +919,7 @@  struct mod {
 	struct kmod_list *info_list;
 	struct kmod_list *dep_sym_list;
 	struct array deps; /* struct symbol */
+	struct hash *deps_alts; /* array struct symbol */
 	size_t baselen; /* points to start of basename/filename */
 	size_t modnamesz;
 	int sort_idx; /* sort index using modules.order */
@@ -950,6 +951,7 @@  struct depmod {
 static void mod_free(struct mod *mod)
 {
 	DBG("free %p kmod=%p, path=%s\n", mod, mod->kmod, mod->path);
+	hash_free(mod->deps_alts);
 	array_free_array(&mod->deps);
 	kmod_module_unref(mod->kmod);
 	kmod_module_info_free_list(mod->info_list);
@@ -980,6 +982,76 @@  static int mod_add_dependency(struct mod *mod, struct symbol *sym)
 	return 0;
 }
 
+static struct symbol *depmod_symbol_find(const struct depmod *depmod,
+							const char *name);
+
+struct array *symbol_get_owners(struct depmod *depmod, struct symbol *sym, int *err)
+{
+	struct array *sym_arr;
+	struct symbol *sym_l, *li;
+	sym_arr = malloc(sizeof(struct array));
+	if (sym_arr == NULL) {
+	    *err = -ENOMEM;
+	    return NULL;
+	}
+	array_init(sym_arr, 4);
+	// first owner into alternatives should be primary owner so add it at 0 position //
+	*err = array_append(sym_arr, sym);
+	if ( *err < 0)
+		goto fail;
+	sym_l = (struct symbol*)depmod_symbol_find(depmod, sym->name);
+	for (li = sym_l; li != NULL; li = li->next)
+		if (li != sym) {
+			*err = array_append(sym_arr, li);
+			if ( *err < 0)
+				goto fail;
+		}
+	*err = 0;
+	return sym_arr;
+fail:
+	array_free_array(sym_arr);
+	free(sym_arr);
+	return NULL;
+}
+
+static int mod_update_dep_alternatives_groups(const struct depmod *depmod, struct mod *mod, struct symbol *sym)
+{
+	struct array *alt_arr;
+	int err;
+
+	DBG("Preparing alternatives for module %s dependency %s %s\n", mod->path, sym->name,
+	    sym->owner != NULL ? sym->owner->path : "(unknown)");
+
+	if (sym->owner == NULL)
+		return 0;
+	err = 0;
+	alt_arr = (struct array*)hash_find(mod->deps_alts, sym->owner->path);
+	if (!alt_arr) {
+		// Create the initial alternative modules array if not presented
+		alt_arr = symbol_get_owners(depmod, sym, &err);
+		if (!alt_arr)
+			goto alt_ex;
+		err = hash_add(mod->deps_alts, sym->owner->path, alt_arr);
+	} else {
+		// Remove alternatives that don't provide the necessary symbol
+		struct symbol *sym_l, *li;
+		size_t si = 0;
+		sym_l = (struct symbol*)depmod_symbol_find(depmod, sym->name);
+		while (si < alt_arr->count) {
+			for (li = sym_l; li != NULL; li = li->next)
+				if (li->owner == ((struct symbol*)alt_arr->array[si])->owner)
+					break;
+			// primary owner can't be removed from alternatives
+			if (!li && si != 0)
+				array_remove_at(alt_arr, si);
+			else
+				si += 1;
+		}
+	}
+alt_ex:
+	return err;
+}
+
 static void symbol_free_sub(struct symbol *sym)
 {
 	DBG("free %p sym=%s, owner=%p %s\n", sym, sym->name, sym->owner,
@@ -1014,6 +1086,13 @@  static struct kmod_module_info *depmod_get_mod_info(struct mod *mod, const char
 	return rval;
 }
 
+static void symbol_alternatives_free(struct array *arr)
+{
+	array_free_array(arr);
+	free(arr);
+}
+
+
 static int depmod_init(struct depmod *depmod, struct cfg *cfg,
 							struct kmod_ctx *ctx)
 {
@@ -1089,6 +1168,11 @@  static int depmod_module_add(struct depmod *depmod, struct kmod_module *kmod)
 	memcpy(mod->modname, modname, modnamesz);
 	mod->modnamesz = modnamesz;
 
+	mod->deps_alts = hash_new(64, (void (*)(void *))symbol_alternatives_free);
+	if (mod->deps_alts == NULL) {
+		free(mod);
+		return -ENOMEM;
+	}
 	array_init(&mod->deps, 4);
 
 	mod->path = strdup(kmod_module_get_path(kmod));
@@ -1127,6 +1211,7 @@  static int depmod_module_add(struct depmod *depmod, struct kmod_module *kmod)
 
 fail:
 	free(mod->uncrelpath);
+	hash_free(mod->deps_alts);
 	free(mod);
 	return err;
 }
@@ -1742,6 +1827,8 @@  static int depmod_load_module_dependencies(struct depmod *depmod, struct mod *mo
 		}
 
 		mod_add_dependency(mod, sym);
+		if (depmod->cfg->use_deps_alternatives == 1)
+			mod_update_dep_alternatives_groups(depmod, mod, sym);
 	}
 
 	return 0;
@@ -2164,11 +2251,24 @@  static int mod_fill_all_unique_dependencies(const struct mod *mod, const struct
 	return err;
 }
 
-static const struct mod **mod_get_all_sorted_dependencies(const struct mod *mod, size_t *n_deps)
+static const struct mod **mod_get_all_sorted_dependencies(const struct mod *mod, size_t *n_deps, int is_direct_deps_only)
 {
 	const struct mod **deps;
 	size_t last = 0;
 
+	if (is_direct_deps_only == 1) {
+	// in case of dirrect deps it's already unique so make an deps array copy//
+		*n_deps = mod->deps.count;
+		if (*n_deps == 0)
+			return NULL;
+		last = mod->deps.count;
+		deps = malloc(sizeof(struct mod *) * last);
+		if (deps == NULL)
+			return NULL;
+		for (size_t i = 0; i < last; i++)
+			deps[i] = mod->deps.array[i];
+		goto sort_dep;
+	}
 	*n_deps = mod_count_all_dependencies(mod);
 	if (*n_deps == 0)
 		return NULL;
@@ -2182,6 +2282,7 @@  static const struct mod **mod_get_all_sorted_dependencies(const struct mod *mod,
 		return NULL;
 	}
 
+sort_dep:
 	qsort(deps, last, sizeof(struct mod *), dep_cmp);
 	*n_deps = last;
 	return deps;
@@ -2208,7 +2309,7 @@  static int output_deps(struct depmod *depmod, FILE *out)
 		if (mod->deps.count == 0)
 			goto end;
 
-		deps = mod_get_all_sorted_dependencies(mod, &n_deps);
+		deps = mod_get_all_sorted_dependencies(mod, &n_deps, depmod->cfg->use_deps_alternatives);
 		if (deps == NULL) {
 			ERR("could not get all sorted dependencies of %s\n", p);
 			goto end;
@@ -2245,7 +2346,7 @@  static int output_deps_bin(struct depmod *depmod, FILE *out)
 		size_t j, n_deps, linepos, linelen, slen;
 		int duplicate;
 
-		deps = mod_get_all_sorted_dependencies(mod, &n_deps);
+		deps = mod_get_all_sorted_dependencies(mod, &n_deps, depmod->cfg->use_deps_alternatives);
 		if (deps == NULL && n_deps > 0) {
 			ERR("could not get all sorted dependencies of %s\n", p);
 			continue;
@@ -2368,6 +2469,171 @@  static int output_aliases_bin(struct depmod *depmod, FILE *out)
 	return 0;
 }
 
+static int sym_mod_cmp(const void *pa, const void *pb)
+{
+	int rsl;
+	const struct symbol *a = *(const struct symbol**)pa;
+	const struct symbol *b = *(const struct symbol**)pb;
+	rsl = strcmp(a->owner->modname, b->owner->modname);
+	if (rsl == 0)
+		rsl = strcmp(a->owner->path, b->owner->path);
+	return rsl;
+}
+
+static int sym_name_cmp(const void *pa, const void *pb)
+{
+	const struct symbol *sa, *sb;
+	const struct array *a = *(const struct array**)pa;
+	const struct array *b = *(const struct array**)pb;
+	sa = (const struct symbol*)a->array[0];
+	sb = (const struct symbol*)b->array[0];
+	return strcmp(sa->name, sb->name);
+}
+
+static void sort_sym_alternatives(struct array *sym_arr)
+{
+	if (sym_arr->count <= 2)
+		return;
+	// first element into array should remain it position //
+	qsort( &sym_arr->array[1], sym_arr->count - 1, sizeof(void*), sym_mod_cmp);
+}
+
+static int sort_mod_alternatives(const struct mod *mod, struct array *sorted)
+{
+	struct hash_iter it;
+	const void *v;
+	int rval;
+
+	array_init(sorted, 4);
+	hash_iter_init(mod->deps_alts, &it);
+	while (hash_iter_next(&it, NULL, &v)) {
+		struct array *sym_arr = (struct array *)v;
+		struct symbol *sym = (struct symbol *)sym_arr->array[0];
+		sort_sym_alternatives(sym_arr);
+		rval = array_append(sorted, sym_arr);
+		if (rval < 0) {
+			array_free_array(sorted);
+			return rval;
+		}
+	}
+	array_sort(sorted, sym_name_cmp);
+	return 0;
+}
+
+static int output_alternatives(struct depmod *depmod, FILE *out)
+{
+	size_t i, i2, i3;
+	fputs("# Modules dependencies alternatives extracted from modules themselves.\n", out);
+	for (i = 0; i < depmod->modules.count; i++) {
+		const struct mod *mod = depmod->modules.array[i];
+		struct array sorted_alts;
+		int rval;
+		rval = sort_mod_alternatives(mod, &sorted_alts);
+		if ( rval < 0) {
+		    ERR("Sorting deps alternatives for %s failed\n", mod->modname);
+		    return rval;
+		}
+		for (i2 = 0; i2 < sorted_alts.count; i2++) {
+			struct array *sym_arr = (struct array *)sorted_alts.array[i2];
+			struct symbol *alternative = (struct symbol *)sym_arr->array[0];
+			// avoid printing deps with single alternative to reduce index size//
+			if (sym_arr->count <= 1)
+				continue;
+			fprintf(out, "%s#_#%s:", mod->modname, alternative->owner->modname);
+			for (i3 = 0; i3 < sym_arr->count; i3++) {
+				alternative = (struct symbol *)sym_arr->array[i3];
+				fprintf(out, " %s", mod_get_compressed_path(alternative->owner));
+			}
+			fprintf(out, "\n");
+		}
+		array_free_array(&sorted_alts);
+	}
+	return 0;
+}
+
+static int output_alternatives_bin(struct depmod *depmod, FILE *out)
+{
+	struct index_node *idx;
+	size_t i, i2, i3;
+	int err = 0;
+
+	if (out == stdout)
+		return 0;
+
+	idx = index_create();
+	if (idx == NULL)
+		return -ENOMEM;
+
+	for (i = 0; i < depmod->modules.count; i++) {
+		const struct mod *mod = depmod->modules.array[i];
+		struct array sorted_alts;
+		int rval;
+		rval = sort_mod_alternatives(mod, &sorted_alts);
+		if ( rval < 0) {
+		    ERR("Sorting deps alternatives for %s failed\n", mod->modname);
+		    return rval;
+		}
+
+		for (i2 = 0; i2 < sorted_alts.count; i2++) {
+			int duplicate;
+			char alt_key[PATH_MAX*2];
+			char *alt_value, *tmp_value;
+			size_t alt_vsize = PATH_MAX*2;
+			size_t alt_vlen = 0;
+			struct array *sym_arr = (struct array *)sorted_alts.array[i2];
+			struct symbol *alternative = (struct symbol *)sym_arr->array[0];
+			// avoid storing deps with single alternative to reduce index size //
+			if (sym_arr->count <= 1)
+				continue;
+			// construct index key //
+			snprintf(alt_key, sizeof(alt_key) - 1, "%s#_#%s", mod->modname, alternative->owner->modname);
+			alt_value = malloc(alt_vsize);
+			if (alt_value == NULL) {
+				err = -ENOMEM;
+				goto fail;
+			}
+			alt_vlen = snprintf(alt_value, alt_vsize, "%s:", alt_key);
+			// construct index value //
+			for ( i3 = 0; i3 < sym_arr->count; i3++) {
+				size_t l;
+				const char *mpath;
+				alternative = (struct symbol *)sym_arr->array[i3];
+				mpath = mod_get_compressed_path(alternative->owner);
+				l = strlen(mpath) + strlen(" ");
+				if (alt_vlen + l >= alt_vsize) {
+					alt_vsize += PATH_MAX > l ? PATH_MAX : l + 1;
+					tmp_value = realloc(alt_value, alt_vsize);
+					if (tmp_value == NULL) {
+						free(alt_value);
+						err = -ENOMEM;
+						goto fail;
+					}
+					alt_value = tmp_value;
+				}
+				strncat(alt_value, " ", alt_vsize);
+				strncat(alt_value, mpath, alt_vsize);
+				alt_vlen += l;
+			}
+			DBG("Adding to index mod: %s, key: %s, value: %s\n", mod->modname, alt_key, alt_value);
+			duplicate = index_insert(idx, alt_key, alt_value, mod->idx);
+			if (duplicate && depmod->cfg->warn_dups)
+				WRN("duplicate module alternative:\n%s %s\n",
+				    alt_key, mod->modname);
+			free(alt_value);
+		}
+		array_free_array(&sorted_alts);
+	}
+
+	index_write(idx, out);
+	index_destroy(idx);
+
+	return 0;
+fail:
+	index_destroy(idx);
+	return err;
+
+}
+
 static int output_softdeps(struct depmod *depmod, FILE *out)
 {
 	size_t i;
@@ -2684,6 +2950,8 @@  static int depmod_output(struct depmod *depmod, FILE *out)
 		{ "modules.dep.bin", output_deps_bin },
 		{ "modules.alias", output_aliases },
 		{ "modules.alias.bin", output_aliases_bin },
+		{ "modules.alternatives", output_alternatives },
+		{ "modules.alternatives.bin", output_alternatives_bin },
 		{ "modules.softdep", output_softdeps },
 		{ "modules.symbols", output_symbols },
 		{ "modules.symbols.bin", output_symbols_bin },
@@ -2719,6 +2987,25 @@  static int depmod_output(struct depmod *depmod, FILE *out)
 		char tmp[NAME_MAX] = "";
 		int r, ferr;
 
+		// modules.alternatives and modules.alternatives.bin should be processed only into dependency alternatives mode(with -D flag) //
+		if (depmod->cfg->use_deps_alternatives == 0 && (itr->cb == output_alternatives || itr->cb == output_alternatives_bin)) {
+			if (fp == NULL) {
+			// if not output to stdout //
+				int fd;
+				fd = openat(dfd, itr->name, O_RDONLY|O_CLOEXEC);
+				if (fd >=0) {
+					// if alternatives index file exists //
+					close(fd);
+					if (unlinkat(dfd, itr->name, 0) != 0) {
+						err = -errno;
+						ERR("unlinkat(%s, %s)\n", dname, itr->name);
+						break;
+					}
+				}
+			}
+			continue;
+		}
+
 		if (fp == NULL) {
 			int flags = O_CREAT | O_EXCL | O_WRONLY;
 			int mode = 0644;