module: Fix performance regression on modules with large symbol tables

Commit 554bdfe5acf3715e87c8d5e25a4f9a896ac9f014 (module: reduce string table for loaded modules) introduced an optimization to shrink the size of the resident string table. Part of this involves calling bitmap_weight() on the strmap bitmap once for each core symbol. strmap contains one bit for each byte of the module's strtab.

For kernel modules with a large number of symbols, the addition of the bitmap_weight() operation to each iteration of the add_kallsyms() loop resulted in a significant "insmod" performance regression from 2.6.31 to 2.6.32. bitmap_weight() is expensive when the bitmap is large.

The proposed alternative optimizes the common case in this loop (is_core_symbol() == true, and the symbol name is not a duplicate), while penalizing the exceptional case of a duplicate symbol.

My test was run on a 600 MHz MIPS processor, using a kernel module with 15,000 "core" symbols and 10,000 symbols in .init.text. .strtab takes up 250,227 bytes.

Original code: insmod takes 3.39 seconds
Patched code: insmod takes 0.07 seconds

---

Since the new code performs an exhaustive string compare search when it encounters duplicate symbols inside a module (i.e. multiple symtab entries referring to the same strtab index), I did some extra checking on my Linux PC to see how common this is:

For modules other than nvidia, there were 35 duplicate symbols out of 9,956 total LKM symbols (0.4%). This is with KALLSYMS and KALLSYMS_ALL enabled. Many were ".LCx" literal constants, and others were random duplications of trace_kmalloc(), cache_put(), do_vfs_lock(), etc. Probably caused by combining multiple *.o files into a single *.ko file.

The nvidia module has 29,296 total entries, and 3,045 duplicates (10%). There were 597 instances of each of: _nv009058rm, _nv009059rm, _nv009060rm, and _nv009061rm.

To make sure the degenerate case of nvidia.ko was still covered, I ran additional tests with qemu-system-arm (ARM Versatile) on Linus' head of tree:

Latest kernel (commit 15831714), 25,000 symbol test (as above): 4.5s

Latest kernel with 2,400 (16%) of my module's core symbols turned into duplicates through hex editing: 4.4s

Patched kernel, 25,000 symbol test: 0.1s

Patched kernel, with 2,400 duplicate symbols: 0.8s

So, even a module with large numbers of duplicate symbols loads more quickly with my patch, than without it.

 kernel/module.c |   26 ++++++++++++++++++--------
 1 files changed, 18 insertions(+), 8 deletions(-)

index 93342d9..7f5dcbf 100644
@@ -2221,7 +2221,7 @@ static void layout_symtab(struct module *mod, struct load_info *info)
 
 static void add_kallsyms(struct module *mod, const struct load_info *info)
 {
-	unsigned int i, ndst;
+	unsigned int i, j, stridx = 1, ndst;
 	const Elf_Sym *src;
 	Elf_Sym *dst;
 	char *s;

@@ -2237,22 +2237,32 @@ static void add_kallsyms(struct module *mod, const struct load_info *info)
 		mod->symtab[i].st_info = elf_type(&mod->symtab[i], info);
 
 	mod->core_symtab = dst = mod->module_core + info->symoffs;
+	mod->core_strtab = s = mod->module_core + info->stroffs;
 	src = mod->symtab;
 	*dst = *src;
+	*s++ = 0;
 	for (ndst = i = 1; i < mod->num_symtab; ++i, ++src) {
 		if (!is_core_symbol(src, info->sechdrs, info->hdr->e_shnum))
 			continue;
 		dst[ndst] = *src;
-		dst[ndst].st_name = bitmap_weight(info->strmap,
-						  dst[ndst].st_name);
+		if (unlikely(!test_bit(src->st_name, info->strmap))) {
+			dst[ndst].st_name = 0;
+			for (j = 1; j < ndst; j++)
+				if (!strcmp(&mod->strtab[src->st_name],
+					    &mod->core_strtab[dst[j].st_name]))
+					dst[ndst].st_name = dst[j].st_name;
+		} else {
+			dst[ndst].st_name = stridx;
+			j = src->st_name;
+			clear_bit(j, info->strmap);
+			do {
+				*s = mod->strtab[j++];
+				stridx++;
+			} while (*s++);
+		}
 		++ndst;
 	}
 	mod->core_num_syms = ndst;
-
-	mod->core_strtab = s = mod->module_core + info->stroffs;
-	for (*s = 0, i = 1; i < info->sechdrs[info->index.str].sh_size; ++i)
-		if (test_bit(i, info->strmap))
-			*++s = mod->strtab[i];
 }
 #else
 static inline void layout_symtab(struct module *mod, struct load_info *info)

1.7.6.3

I see you honored Jan's original patch by leaving it mysterious and undocumented. I was totally confused by your patch.

I finally figured out that you pack the compacted strtab in symtab order, and override the strmap bit to detect duplicates. Clever.

But I don't think it quite works in general. gcc is allowed to compact the strtab itself, eg with two names "foobar" and "bar", it can reuse the tail of the first strtab entry. It may not yet, but it could.

This makes your job a bit harder, but not too bad. See below...

I've started a separate patch to add comments to all this.

Cheers,
Rusty.

module: fix overlapping entries in symtab case.

The prior patch didn't handle the (theoretical?) case where strings in the strtab are partially shared by two symtab entries. This detects that correctly, and does an exhaustive search for that case.

@@ -2221,7 +2221,7 @@ static void layout_symtab(struct module 
 
 static void add_kallsyms(struct module *mod, const struct load_info *info)
 {
-	unsigned int i, j, stridx = 1, ndst;
+	unsigned int i, ndst;
 	const Elf_Sym *src;
 	Elf_Sym *dst;
 	char *s;

@@ -2242,23 +2242,26 @@ static void add_kallsyms(struct module *
 	*dst = *src;
 	*s++ = 0;
 	for (ndst = i = 1; i < mod->num_symtab; ++i, ++src) {
+		const char *name;
 		if (!is_core_symbol(src, info->sechdrs, info->hdr->e_shnum))
 			continue;
 		dst[ndst] = *src;
+
+		name = &mod->strtab[src->st_name];
 		if (unlikely(!test_bit(src->st_name, info->strmap))) {
-			dst[ndst].st_name = 0;
-			for (j = 1; j < ndst; j++)
-				if (!strcmp(&mod->strtab[src->st_name],
-					    &mod->core_strtab[dst[j].st_name]))
-					dst[ndst].st_name = dst[j].st_name;
+			char *dup;
+
+			for (dup = mod->core_strtab; strcmp(dup, name); dup++)
+				BUG_ON(dup > s);
+
+			dst[ndst].st_name = dup - mod->core_strtab;
 		} else {
-			dst[ndst].st_name = stridx;
-			j = src->st_name;
-			clear_bit(j, info->strmap);
-			do {
-				*s = mod->strtab[j++];
-				stridx++;
-			} while (*s++);
+			unsigned len = strlen(name) + 1;
+
+			dst[ndst].st_name = s - mod->core_strtab;
+			memcpy(s, name, len);
+			s += len;
+			bitmap_clear(info->strmap, src->st_name, len);
 		}
 		++ndst;
 	}

Sorry - was just trying to mimic the existing level of verbosity.

Well, sure enough, libbfd's elf-strtab.c is advertised as:

/* ELF strtab with GC and suffix merging support. */

The function that performs the suffix merging is _bfd_elf_strtab_finalize(). For some reason this only seems to get called for .shstrtab (or .dynstr), not for the larger .strtab . And I'm not sure why this would be useful for .shstrtab, since the section names usually start with '.'. I guess it might save a few dozen bytes for cases like .init.data or .exit.text .

But as you said, there is nothing keeping the binutils maintainers from extending this to .strtab in the future.

One thing I noticed when making a test case was that the earliest entry in the section table doesn't necessarily pick the longest substring:

  [ 1] .text             PROGBITS         0000000000000000  00000040
       0000000000000006  0000000000000000  AX       0     0     4
  [ 2] .data             PROGBITS         0000000000000000  00000048
       0000000000000000  0000000000000000  WA       0     0     4
  [ 3] .bss              NOBITS           0000000000000000  00000048
       0000000000000000  0000000000000000  WA       0     0     4
  [ 4] a_                PROGBITS         0000000000000000  00000048
       0000000000000006  0000000000000000  AX       0     0     1
  [ 5] fedcba_           PROGBITS         0000000000000000  0000004e
       0000000000000006  0000000000000000  AX       0     0     1
  [ 6] cba_              PROGBITS         0000000000000000  00000054
       0000000000000006  0000000000000000  AX       0     0     1

Hex dump of section '.shstrtab':
0x00000000 002e7379 6d746162 002e7374 72746162 ..symtab..strtab 0x00000010 002e7368 73747274 6162002e 74657874 ..shstrtab..text 0x00000020 002e6461 7461002e 62737300 67666564 ..data..bss.gfed 0x00000030 6362615f 002e636f 6d6d656e 74002e6e cba_..comment..n 0x00000040 6f74652e 474e552d 73746163 6b002e72 ote.GNU-stack..r
0x00000050 656c612e 65685f66 72616d65 00 ela.eh_frame.

So, the first entry referencing "gfedcba_" has sh_name 0x32 ("a_").

The second entry referencing "gfedcba_" has sh_name 0x2d ("fedcba_").

The third entry referencing "gfedcba_" has sh_name 0x30 ("cba_").

If the same holds true for .symtab, this means we probably need to change the logic to "backtrack" to the beginning of the string before copying it into core_strtab, because a subsequent symtab entry could reference a larger chunk of the string.

We will also want to check the strmap bits, since it's possible that "cba_" was a core symbol but "edcba_" is not. In which case we did not allocate room for the "ed" part, back in layout_symtab().

Not sure how you want to handle combining these changes?

I'll just send a V2 that rolls in all of the desired modifications, if there are no objections...

Thanks.

Please do. I'll write a comment patch on top of that, too.

Thanks!
Rusty.

Why would you want to keep the leading part if it's not part of a core symbol's name?

Jan

Indeed, sorry, I didn't read this part.

Cheers,
Rusty.