@@ -85,6 +85,17 @@ static unsigned int strhash(const char *s)
return hash;
}
+static unsigned int memhash(char *s, size_t len)
+{
+ /* fnv32 hash */
+ unsigned int hash = 2166136261U;
+ size_t i;
+
+ for (i = 0; i < len; i++)
+ hash = (hash ^ *(s + i)) * 0x01000193;
+ return hash;
+}
+
#define OBJ2MOD_BITS 10
#define OBJ2MOD_N (1 << OBJ2MOD_BITS)
#define OBJ2MOD_MASK (OBJ2MOD_N - 1)
@@ -94,14 +105,24 @@ struct obj2mod_elem {
size_t nmods; /* number of modules in "mods" */
size_t mods_size; /* size of all mods together */
int mod_offset; /* offset in .kallsyms_module_names */
+ /*
+ * If set at emission time, this points at another obj2mod entry that
+ * contains the module name we need (possibly at a slightly later
+ * offset, if the entry is for an objfile that appears in many modules).
+ */
+ struct obj2mod_elem *xref;
struct obj2mod_elem *obj2mod_next;
+ struct obj2mod_elem *mod2obj_next;
};
/*
- * Map from object files to obj2mod entries (a unique mapping).
+ * Map from object files to obj2mod entries (a unique mapping), and vice versa
+ * (not unique, but entries for objfiles in more than one module in this hash
+ * are ignored).
*/
static struct obj2mod_elem *obj2mod[OBJ2MOD_N];
+static struct obj2mod_elem *mod2obj[OBJ2MOD_N];
static size_t num_objfiles;
/*
@@ -143,6 +164,8 @@ static void obj2mod_add(char *obj, char *mod)
elem = obj2mod_get(obj);
if (!elem) {
+ int j = strhash(mod) & OBJ2MOD_MASK;
+
elem = malloc(sizeof(struct obj2mod_elem));
if (!elem)
goto oom;
@@ -156,8 +179,15 @@ static void obj2mod_add(char *obj, char *mod)
elem->obj2mod_next = obj2mod[i];
obj2mod[i] = elem;
+ elem->mod2obj_next = mod2obj[j];
+ mod2obj[j] = elem;
num_objfiles++;
} else {
+ /*
+ * TU appears in multiple modules. mod2obj for this entry will
+ * be ignored from now on, except insofar as it is needed to
+ * maintain the hash chain.
+ */
elem->mods = realloc(elem->mods, elem->mods_size +
strlen(mod) + 1);
if (!elem->mods)
@@ -177,6 +207,164 @@ static void obj2mod_add(char *obj, char *mod)
fprintf(stderr, "kallsyms: out of memory\n");
exit(1);
}
+
+/*
+ * Used inside optimize_obj2mod to identify duplicate module entries.
+ */
+struct obj2mod_modhash_elem {
+ struct obj2mod_elem *elem;
+ unsigned int modhash; /* hash value of this entry */
+};
+
+static int qstrcmp(const void *a, const void *b)
+{
+ return strcmp((const char *) a, (const char *) b);
+}
+
+static int qmodhash(const void *a, const void *b)
+{
+ const struct obj2mod_modhash_elem *el_a = a;
+ const struct obj2mod_modhash_elem *el_b = b;
+ if (el_a->modhash < el_b->modhash)
+ return -1;
+ else if (el_a->modhash > el_b->modhash)
+ return 1;
+ return 0;
+}
+
+/*
+ * Associate all TUs in obj2mod which refer to the same module with a single
+ * obj2mod entry for emission, preferring to point into the module list in a
+ * multi-module objfile.
+ */
+static void optimize_obj2mod(void)
+{
+ size_t i;
+ size_t n = 0;
+ struct obj2mod_elem *elem;
+ struct obj2mod_elem *dedup;
+ /* An array of all obj2mod_elems, later sorted by hashval. */
+ struct obj2mod_modhash_elem *uniq;
+ struct obj2mod_modhash_elem *last;
+
+ /*
+ * Canonicalize all module lists by sorting them, then compute their
+ * hash values.
+ */
+ uniq = malloc(sizeof(struct obj2mod_modhash_elem) * num_objfiles);
+ if (uniq == NULL)
+ goto oom;
+
+ for (i = 0; i < OBJ2MOD_N; i++) {
+ for (elem = obj2mod[i]; elem; elem = elem->obj2mod_next) {
+ if (elem->nmods >= 2) {
+ char **sorter;
+ char *walk;
+ char *tmp_mods;
+ size_t j;
+
+ tmp_mods = malloc(elem->mods_size);
+ sorter = malloc(sizeof(char *) * elem->nmods);
+ if (sorter == NULL || tmp_mods == NULL)
+ goto oom;
+ memcpy(tmp_mods, elem->mods, elem->mods_size);
+
+ for (j = 0, walk = tmp_mods; j < elem->nmods;
+ j++) {
+ sorter[j] = walk;
+ walk += strlen(walk) + 1;
+ }
+ qsort(sorter, elem->nmods, sizeof (char *),
+ qstrcmp);
+ for (j = 0, walk = elem->mods; j < elem->nmods;
+ j++) {
+ strcpy(walk, sorter[j]);
+ walk += strlen(walk) + 1;
+ }
+ free(tmp_mods);
+ free(sorter);
+ }
+
+ uniq[n].elem = elem;
+ uniq[n].modhash = memhash(elem->mods, elem->mods_size);
+ n++;
+ }
+ }
+
+ qsort (uniq, num_objfiles, sizeof (struct obj2mod_modhash_elem),
+ qmodhash);
+
+ /*
+ * Work over multimodule entries. These must be emitted into
+ * .kallsyms_module_names as a unit, but we can still optimize by
+ * reusing some other identical entry. Single-file modules are amenable
+ * to the same optimization, but we avoid doing it for now so that we
+ * can prefer to point them directly inside a multimodule entry.
+ */
+ for (i = 0, last = NULL; i < num_objfiles; i++) {
+ const char *onemod;
+ size_t j;
+
+ if (uniq[i].elem->nmods < 2)
+ continue;
+
+ /* Duplicate multimodule. Reuse the first we saw. */
+ if (last != NULL && last->modhash == uniq[i].modhash) {
+ uniq[i].elem->xref = last->elem;
+ continue;
+ }
+
+ /*
+ * Single-module entries relating to modules also emitted as
+ * part of this multimodule entry can refer to it: later, we
+ * will hunt down the right specific module name within this
+ * multimodule entry and point directly to it.
+ */
+ onemod = uniq[i].elem->mods;
+ for (j = uniq[i].elem->nmods; j > 0; j--) {
+ int h = strhash(onemod) & OBJ2MOD_MASK;
+
+ for (dedup = mod2obj[h]; dedup;
+ dedup = dedup->mod2obj_next) {
+ if (dedup->nmods > 1)
+ continue;
+
+ if (strcmp(dedup->mods, onemod) != 0)
+ continue;
+ dedup->xref = uniq[i].elem;
+ assert (uniq[i].elem->xref == NULL);
+ }
+ onemod += strlen(onemod) + 1;
+ }
+
+ last = &uniq[i];
+ }
+
+ /*
+ * Now traverse all single-module entries, xreffing every one that
+ * relates to a given module to the first one we saw that refers to that
+ * module.
+ */
+ for (i = 0, last = NULL; i < num_objfiles; i++) {
+ if (uniq[i].elem->nmods > 1)
+ continue;
+
+ if (uniq[i].elem->xref != NULL)
+ continue;
+
+ /* Duplicate module name. Reuse the first we saw. */
+ if (last != NULL && last->modhash == uniq[i].modhash) {
+ uniq[i].elem->xref = last->elem;
+ assert (last->elem->xref == NULL);
+ continue;
+ }
+ last = &uniq[i];
+ }
+ return;
+oom:
+ fprintf(stderr, "kallsyms: out of memory optimizing module list\n");
+ exit(EXIT_FAILURE);
+}
#endif /* CONFIG_KALLMODSYMS */
static void usage(void)
@@ -479,7 +667,7 @@ static void output_kallmodsyms_modules(void)
size_t i;
/*
- * Traverse and emit, updating mod_offset accordingly.
+ * Traverse and emit, chasing xref and updating mod_offset accordingly.
* Emit a single \0 at the start, to encode non-modular objfiles.
*/
output_label("kallsyms_module_names");
@@ -489,9 +677,15 @@ static void output_kallmodsyms_modules(void)
elem = elem->obj2mod_next) {
const char *onemod;
size_t i;
+ struct obj2mod_elem *out_elem = elem;
- elem->mod_offset = offset;
- onemod = elem->mods;
+ if (elem->xref)
+ out_elem = elem->xref;
+ if (out_elem->mod_offset != 0)
+ continue; /* Already emitted. */
+
+ out_elem->mod_offset = offset;
+ onemod = out_elem->mods;
/*
* Technically this is a waste of space: we could just
@@ -500,13 +694,13 @@ static void output_kallmodsyms_modules(void)
* entry, but doing it this way makes it more obvious
* when an entry is a multimodule entry.
*/
- if (elem->nmods != 1) {
+ if (out_elem->nmods != 1) {
printf("\t.byte\t0\n");
- printf("\t.byte\t%zi\n", elem->nmods);
+ printf("\t.byte\t%zi\n", out_elem->nmods);
offset += 2;
}
- for (i = elem->nmods; i > 0; i--) {
+ for (i = out_elem->nmods; i > 0; i--) {
printf("\t.asciz\t\"%s\"\n", onemod);
offset += strlen(onemod) + 1;
onemod += strlen(onemod) + 1;
@@ -533,6 +727,13 @@ static void output_kallmodsyms_objfiles(void)
long long offset;
int overflow;
+ /*
+ * Fuse consecutive address ranges citing the same object file
+ * into one.
+ */
+ if (i > 0 && addrmap[i-1].objfile == addrmap[i].objfile)
+ continue;
+
if (base_relative) {
if (!absolute_percpu) {
offset = addrmap[i].addr - relative_base;
@@ -558,6 +759,13 @@ static void output_kallmodsyms_objfiles(void)
for (i = 0; i < addrmap_num; i++) {
struct obj2mod_elem *elem = addrmap[i].objfile;
+ int orig_nmods;
+ const char *orig_modname;
+ int mod_offset;
+
+ if (i > 0 && addrmap[i-1].objfile == addrmap[i].objfile)
+ continue;
+
/*
* Address range cites no object file: point at 0, the built-in
* module.
@@ -568,13 +776,53 @@ static void output_kallmodsyms_objfiles(void)
continue;
}
+ orig_nmods = elem->nmods;
+ orig_modname = elem->mods;
+
+ /*
+ * Chase down xrefs, if need be. There can only be one layer of
+ * these: from single-module entry to other single-module entry,
+ * or from single- or multi-module entry to another multi-module
+ * entry. Single -> single and multi -> multi always points at
+ * the start of the xref target, so its offset can be used as is.
+ */
+ if (elem->xref)
+ elem = elem->xref;
+
+ if (elem->nmods == 1 || orig_nmods > 1)
+ mod_offset = elem->mod_offset;
+ else {
+ /*
+ * If this is a reference from a single-module entry to
+ * a multi-module entry, hunt down the offset to this
+ * specific module's name (which is guaranteed to be
+ * present: see optimize_obj2mod).
+ */
+
+ size_t j = elem->nmods;
+ const char *onemod = elem->mods;
+ mod_offset = elem->mod_offset;
+
+ for (; j > 0; j--) {
+ if (strcmp(orig_modname, onemod) == 0)
+ break;
+ onemod += strlen(onemod) + 1;
+ }
+ assert (j > 0);
+ /*
+ * +2 to skip the null byte and count at the start of
+ * the multimodule entry.
+ */
+ mod_offset += onemod - elem->mods + 2;
+ }
+
/*
* Zero offset is the initial \0, there to catch uninitialized
* obj2mod entries, and is forbidden.
*/
- assert (elem->mod_offset != 0);
+ assert (mod_offset != 0);
- printf("\t.long\t0x%x\n", elem->mod_offset);
+ printf("\t.long\t0x%x\n", mod_offset);
emitted_objfiles++;
}
@@ -1093,6 +1341,7 @@ static void read_modules(const char *modules_builtin)
free(module_name);
modules_thick_iter_free(i);
+ optimize_obj2mod();
/*
* Read linker map.