module: Add comments describing how the "strmap" logic works

PATCH In review Kevin Cernekee 3 participants 10 messages Nov 13, 2011 – Nov 22, 2011 Kbuild

lore

Share & tools

lore

Kevin Cernekee

author

2011-11-13 03:14 UTC #0 lore raw

PATCH v2 1/2 module: Add comments describing how the "strmap" logic works

Signed-off-by Kevin Cernekee <[email protected]>

---
 kernel/module.c |    9 +++++++++
 1 files changed, 9 insertions(+), 0 deletions(-)

kernel/module.c +9 -0

index 178333c..cf9f1b6 100644
@@ -2193,6 +2193,13 @@ static void layout_symtab(struct module *mod, struct load_info *info)
 
 	src = (void *)info->hdr + symsect->sh_offset;
 	nsrc = symsect->sh_size / sizeof(*src);
+
+	/*
+	 * info->strmap has a '1' bit for each byte of .strtab we want to
+	 * keep resident in mod->core_strtab.  Everything else in .strtab
+	 * is unreferenced by the symbols in mod->core_symtab, and will be
+	 * discarded when add_kallsyms() compacts the string table.
+	 */
 	for (ndst = i = 1; i < nsrc; ++i, ++src)
 		if (is_core_symbol(src, info->sechdrs, info->hdr->e_shnum)) {
 			unsigned int j = src->st_name;

@@ -2215,6 +2222,8 @@ static void layout_symtab(struct module *mod, struct load_info *info)
 
 	/* Append room for core symbols' strings at end of core part. */
 	info->stroffs = mod->core_size;
+
+	/* First strtab byte (and first symtab entry) are zeroes. */
 	__set_bit(0, info->strmap);
 	mod->core_size += bitmap_weight(info->strmap, strsect->sh_size);
 }

Signature · 1 line

1.7.6.3

Kevin Cernekee

author

2011-11-13 03:14 UTC #1 lore raw

PATCH v2 2/2 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

Signed-off-by Rusty Russell <[email protected]>

Signed-off-by Kevin Cernekee <[email protected]>

---

V2:

Properly handle cases where different symtab entries point to strtab substrings (suffix merging). Mostly Rusty's work. Also, add comments.

My test case for suffix merging was:

$ nm --no-sort alphabet.ko
00000000 t hello
00000014 t init
00000000 d retcode
00000000 r __mod_retcodetype8
00000000 r __param_retcode
00000000 r __param_str_retcode
00000000 r $LC0
00000018 r __module_depends
00000000 r ____versions
00000021 r __mod_vermagic5
00000050 T uvwxyz
00000000 D __this_module
00000048 T yz
00000000 T qrstuvwxyz
00000060 T rstuvwxyz
00000014 T init_module
00000040 T wxyz
00000068 T tuvwxyz
         U printk
00000058 T vwxyz
         U param_ops_int

"qrstuvwxyz" is in .init.text (non-core symbol); all others were core symbols. The symtab entries for all substrings were hexedited to point to the respective portion of the "qrstuvwxyz" strtab entry.

I verified that "rstuvwxyz" (without the 'q') was copied to core_strtab when the loop hit "uvwxyz", and that the substrings all used that entry.

 kernel/module.c |   40 +++++++++++++++++++++++++++++++++-------
 1 files changed, 33 insertions(+), 7 deletions(-)

kernel/module.c +33 -7

index cf9f1b6..6c87305 100644
@@ -2246,22 +2246,48 @@ 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) {
+		const char *name;
 		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);
+
+		name = &mod->strtab[src->st_name];
+		if (unlikely(!test_bit(src->st_name, info->strmap))) {
+			/* Symbol name has already been copied; find it. */
+			char *dup;
+
+			for (dup = mod->core_strtab; strcmp(dup, name); dup++)
+				BUG_ON(dup > s);
+
+			dst[ndst].st_name = dup - mod->core_strtab;
+		} else {
+			/*
+			 * Copy the symbol name to mod->core_strtab.
+			 * "name" might point to the middle of a longer strtab
+			 * entry, so backtrack to the first "required" byte
+			 * of the string.
+			 */
+			unsigned start = src->st_name, len = 0;
+
+			for (; test_bit(start - 1, info->strmap) &&
+			       mod->strtab[start - 1]; start--)
+				len++;
+
+			dst[ndst].st_name = len + s - mod->core_strtab;
+			len += strlen(name) + 1;
+
+			memcpy(s, &mod->strtab[start], len);
+			s += len;
+			bitmap_clear(info->strmap, start, len);
+		}
 		++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)

Signature · 1 line

1.7.6.3

Rusty Russell

2011-11-14 00:49 UTC #2 lore raw

Re: [PATCH V2 2/2] module: Fix performance regression on modules with large symbol tables

kernel/module.c static void add_kallsyms(struct module *mod, const struct load_info *info) · line 2274

Quoted 6 lines · Kevin Cernekee

kernel/module.c +6 -0

+			/*
+			 * Copy the symbol name to mod->core_strtab.
+			 * "name" might point to the middle of a longer strtab
+			 * entry, so backtrack to the first "required" byte
+			 * of the string.
+			 */

Icky, but it works.

Both applied, thanks!
Rusty.

Jan Beulich

2011-11-14 08:48 UTC #3 lore raw

Re: [PATCH V2 2/2] module: Fix performance regression on modules with large symbol tables

In reply to Kevin Cernekee

Quoted 86 lines

Quoted 1 line
Quoted 1 line · Kevin Cernekee
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
Signed-off-by Rusty Russell <[email protected]>
Signed-off-by Kevin Cernekee <[email protected]>
---
V2:
Properly handle cases where different symtab entries point to strtab substrings (suffix merging). Mostly Rusty's work. Also, add comments.
My test case for suffix merging was:
$ nm --no-sort alphabet.ko
00000000 t hello
00000014 t init
00000000 d retcode
00000000 r __mod_retcodetype8
00000000 r __param_retcode
00000000 r __param_str_retcode
00000000 r $LC0
00000018 r __module_depends
00000000 r ____versions
00000021 r __mod_vermagic5
00000050 T uvwxyz
00000000 D __this_module
00000048 T yz
00000000 T qrstuvwxyz
00000060 T rstuvwxyz
00000014 T init_module
00000040 T wxyz
00000068 T tuvwxyz
         U printk
00000058 T vwxyz
         U param_ops_int
"qrstuvwxyz" is in .init.text (non-core symbol); all others were core symbols. The symtab entries for all substrings were hexedited to point to the respective portion of the "qrstuvwxyz" strtab entry.
I verified that "rstuvwxyz" (without the 'q') was copied to core_strtab when the loop hit "uvwxyz", and that the substrings all used that entry.
 kernel/module.c |   40 +++++++++++++++++++++++++++++++++-------
 1 files changed, 33 insertions(+), 7 deletions(-)
kernel/module.c +3 -0
index cf9f1b6..6c87305 100644
@@ -2246,22 +2246,48 @@ 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) {
+		const char *name;
 		if (!is_core_symbol(src, info->sechdrs, info->hdr->e_shnum))
 			continue;
 		dst[ndst] = *src;

kernel/module.c static void add_kallsyms(struct module *mod, const · line 2266

Quoted 10 lines

kernel/module.c +8 -2

-		dst[ndst].st_name = bitmap_weight(info->strmap,
-						  dst[ndst].st_name);
+
+		name = &mod->strtab[src->st_name];
+		if (unlikely(!test_bit(src->st_name, info->strmap))) {
+			/* Symbol name has already been copied; find it. */
+			char *dup;
+
+			for (dup = mod->core_strtab; strcmp(dup, name); dup++)
+				BUG_ON(dup > s);

Aren't you concerned that this again will be rather slow? It would be pretty easy to accelerate by comparing only with the tail of each string (as nothing else can possibly match), moving from string to string instead of from character to character.

Jan

Quoted 34 lines

kernel/module.c +22 -5

+
+			dst[ndst].st_name = dup - mod->core_strtab;
+		} else {
+			/*
+			 * Copy the symbol name to mod->core_strtab.
+			 * "name" might point to the middle of a longer strtab
+			 * entry, so backtrack to the first "required" byte
+			 * of the string.
+			 */
+			unsigned start = src->st_name, len = 0;
+
+			for (; test_bit(start - 1, info->strmap) &&
+			       mod->strtab[start - 1]; start--)
+				len++;
+
+			dst[ndst].st_name = len + s - mod->core_strtab;
+			len += strlen(name) + 1;
+
+			memcpy(s, &mod->strtab[start], len);
+			s += len;
+			bitmap_clear(info->strmap, start, len);
+		}
 		++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)

Rusty Russell

2011-11-16 02:33 UTC #4 lore raw

Re: [PATCH V2 2/2] module: Fix performance regression on modules with large symbol tables

Quoted 4 lines · Jan Beulich

Quoted 4 lines

kernel/module.c +4 -0

+		name = &mod->strtab[src->st_name];
+		if (unlikely(!test_bit(src->st_name, info->strmap))) {
+			/* Symbol name has already been copied; find it. */
+			char *dup;

Quoted 8 lines

kernel/module.c static void add_kallsyms(struct module *mod, const struct load_info *info) · line 2265
Quoted 3 lines
kernel/module.c +3 -0
+
+			for (dup = mod->core_strtab; strcmp(dup, name); dup++)
+				BUG_ON(dup > s);
Aren't you concerned that this again will be rather slow? It would be pretty easy to accelerate by comparing only with the tail of each string (as nothing else can possibly match), moving from string to string instead of from character to character.

Kevin's central thesis is that this is actually really unusual.

I'm not sure how much faster a tail search would be in practice. We're still scanning the string. Perhaps a "dup[0] == name[0] &&" would optimize it almost as well, if gcc doesn't already?

Kevin, you're probably in an optimal position to get numbers on this?

Thanks,
Rusty.

Kevin Cernekee

author

2011-11-18 03:20 UTC #5 lore raw

Re: [PATCH V2 2/2] module: Fix performance regression on modules with large symbol tables

In reply to Jan Beulich

Quoted 7 lines · Jan Beulich

Review
Quoted 2 lines
(quoted diff) +2 -0
+                   for (dup = mod->core_strtab; strcmp(dup, name); dup++)
+                           BUG_ON(dup > s);
Aren't you concerned that this again will be rather slow? It would be pretty easy to accelerate by comparing only with the tail of each string (as nothing else can possibly match), moving from string to string instead of from character to character.

I reinstalled an old laptop today and then ran a few numbers for fun.

System: Linux 3.0.4, Ubuntu 11.10, x86 32-bit, Intel Core 2 P8700, nvidia 280.13 driver

Looking at /proc/kallsyms, one starts to ponder whether all of the extra strtab-related complexity in module.c is worth the memory savings:

nvidia.ko: 33,785 entries (3,037 are duplicates) Other *.ko files: 5,972 entries (3 are duplicates) Kernel image: 62,737 entries

Sum of lengths of all *.ko core symbol names + terminating bytes:
542,824 bytes; 408,585 of that is from nvidia.ko

Potential memory savings from suffix merging (shorter strings refer to a longer strtab entry, exact matches excluded): 13,156 bytes total; 487 from nvidia.ko. These mostly came from entries starting with __kcrctab* or __param* .

Potential memory savings from reusing EXACT strtab matches: 36,475 bytes total; 35,432 from nvidia.ko. For comparison, discarding non-core strtab entries saved about 91KB on my system.

Instead of making the add_kallsyms() loop even more complex, I tried the other route of deleting the strmap logic and naively copying each string into core_strtab with no consideration for consolidating duplicates. According to the above figures, this would unnecessarily cost me about 49KB (10%) if binutils did suffix merging.

Performance on an "already exists" insmod of nvidia.ko (runs add_kallsyms() but does not actually initialize the module):

Original scheme: 1.230s
With patch V2: 0.280s
With naive copying: 0.058s

I am posting the "naive copying" patch in case anybody else wants to follow up on this. I am satisfied enough with the way the "V2" code works and do not know if any additional tweaking is warranted. But if you can make good use of my patch, feel free:

Signed-off-by Kevin Cernekee <[email protected]>

---

kernel/module.c +12 ~~-68~~

index 6c87305..b07f71c 100644
@@ -138,7 +138,6 @@ struct load_info {
 	unsigned long len;
 	Elf_Shdr *sechdrs;
 	char *secstrings, *strtab;
-	unsigned long *strmap;
 	unsigned long symoffs, stroffs;
 	struct _ddebug *debug;
 	unsigned int num_debug;

@@ -2183,7 +2182,7 @@ static void layout_symtab(struct module *mod, struct load_info *info)
 	Elf_Shdr *symsect = info->sechdrs + info->index.sym;
 	Elf_Shdr *strsect = info->sechdrs + info->index.str;
 	const Elf_Sym *src;
-	unsigned int i, nsrc, ndst;
+	unsigned int i, nsrc, ndst, strtab_size;
 
 	/* Put symbol section at end of init part of module. */
 	symsect->sh_flags |= SHF_ALLOC;

@@ -2194,38 +2193,23 @@ static void layout_symtab(struct module *mod, struct load_info *info)
 	src = (void *)info->hdr + symsect->sh_offset;
 	nsrc = symsect->sh_size / sizeof(*src);
 
-	/*
-	 * info->strmap has a '1' bit for each byte of .strtab we want to
-	 * keep resident in mod->core_strtab.  Everything else in .strtab
-	 * is unreferenced by the symbols in mod->core_symtab, and will be
-	 * discarded when add_kallsyms() compacts the string table.
-	 */
-	for (ndst = i = 1; i < nsrc; ++i, ++src)
+	/* Compute total space required for the core symbols' strtab. */
+	for (ndst = i = strtab_size = 1; i < nsrc; ++i, ++src)
 		if (is_core_symbol(src, info->sechdrs, info->hdr->e_shnum)) {
-			unsigned int j = src->st_name;
-
-			while (!__test_and_set_bit(j, info->strmap)
-			       && info->strtab[j])
-				++j;
-			++ndst;
+			strtab_size += strlen(&info->strtab[src->st_name]) + 1;
+			ndst++;
 		}
 
 	/* Append room for core symbols at end of core part. */
 	info->symoffs = ALIGN(mod->core_size, symsect->sh_addralign ?: 1);
-	mod->core_size = info->symoffs + ndst * sizeof(Elf_Sym);
+	info->stroffs = mod->core_size = info->symoffs + ndst * sizeof(Elf_Sym);
+	mod->core_size += strtab_size;
 
 	/* Put string table section at end of init part of module. */
 	strsect->sh_flags |= SHF_ALLOC;
 	strsect->sh_entsize = get_offset(mod, &mod->init_size, strsect,
 					 info->index.str) | INIT_OFFSET_MASK;
 	DEBUGP("\t%s\n", info->secstrings + strsect->sh_name);
-
-	/* Append room for core symbols' strings at end of core part. */
-	info->stroffs = mod->core_size;
-
-	/* First strtab byte (and first symtab entry) are zeroes. */
-	__set_bit(0, info->strmap);
-	mod->core_size += bitmap_weight(info->strmap, strsect->sh_size);
 }
 
 static void add_kallsyms(struct module *mod, const struct load_info *info)

@@ -2251,41 +2235,12 @@ static void add_kallsyms(struct module *mod, const struct load_info *info)
 	*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))) {
-			/* Symbol name has already been copied; find it. */
-			char *dup;
-
-			for (dup = mod->core_strtab; strcmp(dup, name); dup++)
-				BUG_ON(dup > s);
-
-			dst[ndst].st_name = dup - mod->core_strtab;
-		} else {
-			/*
-			 * Copy the symbol name to mod->core_strtab.
-			 * "name" might point to the middle of a longer strtab
-			 * entry, so backtrack to the first "required" byte
-			 * of the string.
-			 */
-			unsigned start = src->st_name, len = 0;
-
-			for (; test_bit(start - 1, info->strmap) &&
-			       mod->strtab[start - 1]; start--)
-				len++;
-
-			dst[ndst].st_name = len + s - mod->core_strtab;
-			len += strlen(name) + 1;
-
-			memcpy(s, &mod->strtab[start], len);
-			s += len;
-			bitmap_clear(info->strmap, start, len);
-		}
-		++ndst;
+		dst[ndst] = *src;
+		dst[ndst++].st_name = s - mod->core_strtab;
+		s += strlcpy(s, &mod->strtab[src->st_name], KSYM_NAME_LEN) + 1;
 	}
 	mod->core_num_syms = ndst;
 }

@@ -2777,27 +2732,18 @@ static struct module *layout_and_allocate(struct load_info *info)
 	   this is done generically; there doesn't appear to be any
 	   special cases for the architectures. */
 	layout_sections(mod, info);
-
-	info->strmap = kzalloc(BITS_TO_LONGS(info->sechdrs[info->index.str].sh_size)
-			 * sizeof(long), GFP_KERNEL);
-	if (!info->strmap) {
-		err = -ENOMEM;
-		goto free_percpu;
-	}
 	layout_symtab(mod, info);
 
 	/* Allocate and move to the final place */
 	err = move_module(mod, info);
 	if (err)
-		goto free_strmap;
+		goto free_percpu;
 
 	/* Module has been copied to its final place now: return it. */
 	mod = (void *)info->sechdrs[info->index.mod].sh_addr;
 	kmemleak_load_module(mod, info);
 	return mod;
 
-free_strmap:
-	kfree(info->strmap);
 free_percpu:
 	percpu_modfree(mod);
 out:

@@ -2807,7 +2753,6 @@ out:
 /* mod is no longer valid after this! */
 static void module_deallocate(struct module *mod, struct load_info *info)
 {
-	kfree(info->strmap);
 	percpu_modfree(mod);
 	module_free(mod, mod->module_init);
 	module_free(mod, mod->module_core);

@@ -2937,8 +2882,7 @@ static struct module *load_module(void __user *umod,
 	if (err < 0)
 		goto unlink;
 
-	/* Get rid of temporary copy and strmap. */
-	kfree(info.strmap);
+	/* Get rid of temporary copy. */
 	free_copy(&info);
 
 	/* Done! */

Rusty Russell

2011-11-21 05:21 UTC #6 lore raw

Re: [PATCH V2 2/2] module: Fix performance regression on modules with large symbol tables

Quoted 3 lines · Kevin Cernekee

Potential memory savings from reusing EXACT strtab matches: 36,475 bytes total; 35,432 from nvidia.ko. For comparison, discarding non-core strtab entries saved about 91KB on my system.

...

Quoted 3 lines

Original scheme: 1.230s
With patch V2: 0.280s
With naive copying: 0.058s

I'm deeply tempted. It's very simple, 46 lines shorter, preserves exact matches, and doesn't have any strange slowdowns on corner cases.

But like Kevin, I could be convinced either way. Jan?

Thanks,
Rusty.

Kevin Cernekee

author

2011-11-21 06:29 UTC #7 lore raw

Re: [PATCH V2 2/2] module: Fix performance regression on modules with large symbol tables

Quoted 3 lines · Rusty Russell

On Thu, 17 Nov 2011 19:15:02 -0800, Kevin Cernekee <[email protected]> wrote:
I'm deeply tempted. It's very simple, 46 lines shorter, preserves exact matches, and doesn't have any strange slowdowns on corner cases.

Unfortunately, the last patch I posted still makes duplicate copies of the exact matches. And the copy of nvidia.ko I'm looking at right now does reuse strtab entries for the duplicated symbols.

FWIW, preserving exact matches would save about 35KB on a kernel module whose .text + .data + .rodata sections add up to ~9.5MB.

I'm sure there are more clever ways to do it, but a fast brute force approach could involve storing the core_strtab offsets in a temporary array indexed by the original strtab st_name values.

Rusty Russell

2011-11-22 00:59 UTC #8 lore raw

Re: [PATCH V2 2/2] module: Fix performance regression on modules with large symbol tables

Quoted 8 lines · Kevin Cernekee

Quoted 3 lines · Rusty Russell
On Thu, 17 Nov 2011 19:15:02 -0800, Kevin Cernekee <[email protected]> wrote:
I'm deeply tempted. It's very simple, 46 lines shorter, preserves exact matches, and doesn't have any strange slowdowns on corner cases.
Unfortunately, the last patch I posted still makes duplicate copies of the exact matches. And the copy of nvidia.ko I'm looking at right now does reuse strtab entries for the duplicated symbols.

Ah, I read it too fast.

Still, simplicity wins. I like Jan's point, I'll put in a comment and reference to this thread for future adventurers. Result below.

Thanks!
Rusty.

From: Kevin Cernekee <[email protected]>
Subject: module: Fix performance regression on modules with large symbol tables

Looking at /proc/kallsyms, one starts to ponder whether all of the extra strtab-related complexity in module.c is worth the memory savings.

Performance on an "already exists" insmod of nvidia.ko (runs add_kallsyms() but does not actually initialize the module):

	Original scheme: 1.230s
	With naive copying: 0.058s

Extra space used: 35k (of a 408k module).

Signed-off-by Kevin Cernekee <[email protected]>

Signed-off-by Rusty Russell <[email protected]>

LKML-Reference: <73defb5e4bca04a6431392cc341112b1@localhost>

---
 kernel/module.c |   65 ++++++++++++++++++--------------------------------------
 1 file changed, 21 insertions(+), 44 deletions(-)

kernel/module.c +21 ~~-44~~

@@ -138,7 +138,6 @@ struct load_info {
 	unsigned long len;
 	Elf_Shdr *sechdrs;
 	char *secstrings, *strtab;
-	unsigned long *strmap;
 	unsigned long symoffs, stroffs;
 	struct _ddebug *debug;
 	unsigned int num_debug;

@@ -2178,12 +2177,19 @@ static bool is_core_symbol(const Elf_Sym
 	return true;
 }
 
+/*
+ * We only allocate and copy the strings needed by the parts of symtab
+ * we keep.  This is simple, but has the effect of making multiple
+ * copies of duplicates.  We could be more sophisticated, see
+ * linux-kernel thread starting with
+ * <73defb5e4bca04a6431392cc341112b1@localhost>.
+ */
 static void layout_symtab(struct module *mod, struct load_info *info)
 {
 	Elf_Shdr *symsect = info->sechdrs + info->index.sym;
 	Elf_Shdr *strsect = info->sechdrs + info->index.str;
 	const Elf_Sym *src;
-	unsigned int i, nsrc, ndst;
+	unsigned int i, nsrc, ndst, strtab_size;
 
 	/* Put symbol section at end of init part of module. */
 	symsect->sh_flags |= SHF_ALLOC;

@@ -2194,38 +2200,23 @@ static void layout_symtab(struct module 
 	src = (void *)info->hdr + symsect->sh_offset;
 	nsrc = symsect->sh_size / sizeof(*src);
 
-	/*
-	 * info->strmap has a '1' bit for each byte of .strtab we want to
-	 * keep resident in mod->core_strtab.  Everything else in .strtab
-	 * is unreferenced by the symbols in mod->core_symtab, and will be
-	 * discarded when add_kallsyms() compacts the string table.
-	 */
-	for (ndst = i = 1; i < nsrc; ++i, ++src)
+	/* Compute total space required for the core symbols' strtab. */
+	for (ndst = i = strtab_size = 1; i < nsrc; ++i, ++src)
 		if (is_core_symbol(src, info->sechdrs, info->hdr->e_shnum)) {
-			unsigned int j = src->st_name;
-
-			while (!__test_and_set_bit(j, info->strmap)
-			       && info->strtab[j])
-				++j;
-			++ndst;
+			strtab_size += strlen(&info->strtab[src->st_name]) + 1;
+			ndst++;
 		}
 
 	/* Append room for core symbols at end of core part. */
 	info->symoffs = ALIGN(mod->core_size, symsect->sh_addralign ?: 1);
-	mod->core_size = info->symoffs + ndst * sizeof(Elf_Sym);
+	info->stroffs = mod->core_size = info->symoffs + ndst * sizeof(Elf_Sym);
+	mod->core_size += strtab_size;
 
 	/* Put string table section at end of init part of module. */
 	strsect->sh_flags |= SHF_ALLOC;
 	strsect->sh_entsize = get_offset(mod, &mod->init_size, strsect,
 					 info->index.str) | INIT_OFFSET_MASK;
 	DEBUGP("\t%s\n", info->secstrings + strsect->sh_name);
-
-	/* Append room for core symbols' strings at end of core part. */
-	info->stroffs = mod->core_size;
-
-	/* First strtab byte (and first symtab entry) are zeroes. */
-	__set_bit(0, info->strmap);
-	mod->core_size += bitmap_weight(info->strmap, strsect->sh_size);
 }
 
 static void add_kallsyms(struct module *mod, const struct load_info *info)

@@ -2246,22 +2237,19 @@ static void add_kallsyms(struct module *
 		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);
-		++ndst;
+		dst[ndst++].st_name = s - mod->core_strtab;
+		s += strlcpy(s, &mod->strtab[src->st_name], KSYM_NAME_LEN) + 1;
 	}
 	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)

@@ -2751,27 +2739,18 @@ static struct module *layout_and_allocat
 	   this is done generically; there doesn't appear to be any
 	   special cases for the architectures. */
 	layout_sections(mod, info);
-
-	info->strmap = kzalloc(BITS_TO_LONGS(info->sechdrs[info->index.str].sh_size)
-			 * sizeof(long), GFP_KERNEL);
-	if (!info->strmap) {
-		err = -ENOMEM;
-		goto free_percpu;
-	}
 	layout_symtab(mod, info);
 
 	/* Allocate and move to the final place */
 	err = move_module(mod, info);
 	if (err)
-		goto free_strmap;
+		goto free_percpu;
 
 	/* Module has been copied to its final place now: return it. */
 	mod = (void *)info->sechdrs[info->index.mod].sh_addr;
 	kmemleak_load_module(mod, info);
 	return mod;
 
-free_strmap:
-	kfree(info->strmap);
 free_percpu:
 	percpu_modfree(mod);
 out:

@@ -2781,7 +2760,6 @@ out:
 /* mod is no longer valid after this! */
 static void module_deallocate(struct module *mod, struct load_info *info)
 {
-	kfree(info->strmap);
 	percpu_modfree(mod);
 	module_free(mod, mod->module_init);
 	module_free(mod, mod->module_core);

@@ -2911,8 +2889,7 @@ static struct module *load_module(void _
 	if (err < 0)
 		goto unlink;
 
-	/* Get rid of temporary copy and strmap. */
-	kfree(info.strmap);
+	/* Get rid of temporary copy. */
 	free_copy(&info);
 
 	/* Done! */

Jan Beulich

2011-11-21 08:08 UTC #9 lore raw

Re: [PATCH V2 2/2] module: Fix performance regression on modules with large symbol tables

In reply to Rusty Russell

Quoted 6 lines

Quoted 1 line
Quoted 1 line · Rusty Russell
Quoted 3 lines · Kevin Cernekee
Potential memory savings from reusing EXACT strtab matches: 36,475 bytes total; 35,432 from nvidia.ko. For comparison, discarding non-core strtab entries saved about 91KB on my system.
...

Quoted 8 lines

Quoted 3 lines
Original scheme: 1.230s
With patch V2: 0.280s
With naive copying: 0.058s
I'm deeply tempted. It's very simple, 46 lines shorter, preserves exact matches, and doesn't have any strange slowdowns on corner cases.
But like Kevin, I could be convinced either way. Jan?

I'd be fine with the simpler solution, as long it is clearly understood (and marked as intended to be that was for the time being) that it has room for improvement, should it ever turn out to yield more significant savings in other contexts.

Jan