Sort kallsyms in name order: kernel shrinks by 30k

Admittedly, anyone who sets CONFIG_KALLSYMS doesn't care about space, it's a fairly trivial change.

Name: Sort Kallsyms for Stem Compression
Status: Booted on 2.6.6
Depends: Misc/kallsyms-include-aliases.patch.gz

Leaving the symbols sorted by name rather than address, so stem compression works more effectively. Saves a little over 30k here.

diff -urpN --exclude TAGS -X /home/rusty/devel/kernel/kernel-patches/current-dontdiff --minimal .5923-linux-2.6.6/Makefile .5923-linux-2.6.6.updated/Makefile
@@ -567,7 +567,7 @@ ifdef CONFIG_KALLSYMS
 kallsyms.o := .tmp_kallsyms2.o
 
 quiet_cmd_kallsyms = KSYM    $@
-cmd_kallsyms = $(NM) -n $< | $(KALLSYMS) > $@
+cmd_kallsyms = $(NM) $< | $(KALLSYMS) > $@
 
 .tmp_kallsyms1.o .tmp_kallsyms2.o: %.o: %.S scripts FORCE
 	$(call if_changed_dep,as_o_S)

diff -urpN --exclude TAGS -X /home/rusty/devel/kernel/kernel-patches/current-dontdiff --minimal .5923-linux-2.6.6/kernel/kallsyms.c .5923-linux-2.6.6.updated/kernel/kallsyms.c
@@ -62,7 +62,7 @@ const char *kallsyms_lookup(unsigned lon
 			    unsigned long *offset,
 			    char **modname, char *namebuf)
 {
-	unsigned long i, best = 0;
+	unsigned long i, best = -1UL;
 
 	/* This kernel should never had been booted. */
 	BUG_ON(!kallsyms_addresses);

@@ -74,10 +74,12 @@ const char *kallsyms_lookup(unsigned lon
 		unsigned long symbol_end;
 		char *name = kallsyms_names;
 
-		/* They're sorted, we could be clever here, but who cares? */
+		/* Look for closest symbol <= address. */
 		for (i = 0; i < kallsyms_num_syms; i++) {
-			if (kallsyms_addresses[i] > kallsyms_addresses[best] &&
-			    kallsyms_addresses[i] <= addr)
+			if (kallsyms_addresses[i] > addr)
+				continue;
+			if (best == -1UL
+			    ||kallsyms_addresses[i] > kallsyms_addresses[best])
 				best = i;
 		}
 

@@ -94,12 +96,11 @@ const char *kallsyms_lookup(unsigned lon
 		else
 			symbol_end = (unsigned long)_etext;
 
-		/* Search for next non-aliased symbol */
-		for (i = best+1; i < kallsyms_num_syms; i++) {
-			if (kallsyms_addresses[i] > kallsyms_addresses[best]) {
+		/* Search for next symbol */
+		for (i = 0; i < kallsyms_num_syms; i++) {
+			if (kallsyms_addresses[i] > kallsyms_addresses[best]
+			    && kallsyms_addresses[i] < symbol_end)
 				symbol_end = kallsyms_addresses[i];
-				break;
-			}
 		}
 
 		*symbolsize = symbol_end - kallsyms_addresses[best];

Anyone who quotes me in their signature is an idiot -- Rusty Russell

Not sure this is a good idea. proc_pid_wchan() calls kallsyms_lookup() and has been identified as a bottleneck on systems with a large number of processes. top can consume a complete cpu out of 128 cpus, all because of this bottleneck. I was toying with the idea of doing a binary chop on the address lookup, but this patch prevents that fix.

As long as nobody does binary search it's good. Wonder why I did not have this idea already with the original stem compression change ;-)

-Andi

On 11 May 2004 10:08:43 +0200 Andi Kleen wrote:

| On Tue, May 11, 2004 at 03:08:55PM +1000, Rusty Russell wrote:
| > Admittedly, anyone who sets CONFIG_KALLSYMS doesn't care about space,
| > it's a fairly trivial change.
| 
| As long as nobody does binary search it's good. Wonder why I did not
| have this idea already with the original stem compression change ;-)

My (limited) experience is that things reading /proc/kallsyms want to see it in sorted address order, not in sorted name order.

--
~Randy
(Again. Sometimes I think ln -s /usr/src/linux/.config .signature) -- akpm

ISTR that someone (I thought you) mentioned doing this before.

In general this code was considered non-speed-critical, but Keith points out its use in wchan. A simple cache might make more sense there, however.

A binary search as stands doesn't help much because we still need to iterate through the names. We could do "address, nameindex" pairs, but with stem compression we need to at least wade back some way to decode the name.

I have a 30-line static huffman decoder (from the IDE mini-oopser) which we could use instead of stem compression, which we could combine with "address, bitoffset" pairs which would be about 20k smaller and faster than the current approach, but is it worth the trouble?

Thoughts welcome,
Rusty.

Anyone who quotes me in their signature is an idiot -- Rusty Russell

I'd like to delta compress the addresses as well. I think the way to do this is to change the address table to be sparsed by a factor of 16 or 32 or so, with pointers into the stem table. The pointers are chosen to land us on stems of length 0 so we don't have to do any backtracking. Then in addition to stem length, we keep a 16-bit address delta.

So we do a binary (or linear) search on the reduced address table, hop into the stem table, and iterate along as before until we find our symbol. Even if we stick with linear search on the address table, we've sped up the search by 32x. So now we have nearly random access into the stem table and for 15000 symbols, we'll save on the order of 30k (and 90k on 64-bit!).

We can also drop the nulls from the end of the ascii strings and look for termination by finding the next stem code (hopefully always in the control character range). This should be worth another 15k.

Matt Mackall : http://www.selenic.com : Linux development and consulting

Yes, but that iteration is bounded.

Probably not.

-Andi