[PATCH] Sort kallsyms in name order: kernel shrinks by 30k

[PATCH] Sort kallsyms in name order: kernel shrinks by 30k

[Rusty Russell]

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
--- .5923-linux-2.6.6/Makefile	2004-05-10 15:12:44.000000000 +1000
+++ .5923-linux-2.6.6.updated/Makefile	2004-05-11 14:45:37.000000000 +1000
@@ -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
--- .5923-linux-2.6.6/kernel/kallsyms.c	2004-05-11 14:45:36.000000000 +1000
+++ .5923-linux-2.6.6.updated/kernel/kallsyms.c	2004-05-11 14:49:45.000000000 +1000
@@ -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

Re: [PATCH] Sort kallsyms in name order: kernel shrinks by 30k

[Keith Owens]

On Tue, 11 May 2004 15:08:55 +1000, 
Rusty Russell <rusty@rustcorp.com.au> wrote:
>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.

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.

Re: [PATCH] Sort kallsyms in name order: kernel shrinks by 30k

[Andi Kleen]

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 ;-)

-Andi

Re: [PATCH] Sort kallsyms in name order: kernel shrinks by 30k

[Randy.Dunlap]

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

Re: [PATCH] Sort kallsyms in name order: kernel shrinks by 30k

[Rusty Russell]

On Tue, 2004-05-11 at 18:08, 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 ;-)

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

Re: [PATCH] Sort kallsyms in name order: kernel shrinks by 30k

[Matt Mackall]

On Wed, May 12, 2004 at 09:16:56AM +1000, Rusty Russell wrote:
> On Tue, 2004-05-11 at 18:08, 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 ;-)
> 
> 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'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

Re: [PATCH] Sort kallsyms in name order: kernel shrinks by 30k

[Andi Kleen]

On Wed, May 12, 2004 at 09:16:56AM +1000, Rusty Russell wrote:
> 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.

Yes, but that iteration is bounded.

> 
> 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?

Probably not.

-Andi

Re: [PATCH] Sort kallsyms in name order: kernel shrinks by 30k

[Albert Cahalan]

> 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.

That's nothing these days.

How does this change stand up to benchmarking?
Start up 12345 processes or more, then do this:

time ps -eo wchan >> /dev/null
time cat /proc/*/wchan >> /dev/null

As Keith Owens says, "top can consume a complete
cpu out of 128 cpus". (not that I can verify this)