Re: [PATCH] kallsyms data size reduction / lookup speedup
From: Paulo Marques
Date: Thu Aug 26 2004 - 05:35:25 EST
Andrew Morton wrote:
viro@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx wrote:
On Thu, Aug 26, 2004 at 12:40:30AM +0100, Paulo Marques wrote:
> That is why I kept a big *If* in that sentence. I'm quite new to all
> this, and I'm still reading a lot of source code.
>
> If the culprit is in fact seq_file, and seq_file can be improved in a
> way that works for everyone (not only kallsyms), then I also agree
> that is is the way to go. But hunting this down might prove that the
> problem is somewhere else. It is just too soon to draw conclusions.
readprofile(1) ought to narrow it down with that kind of timing difference...
c014696c do_anonymous_page 4 0.0133
c0133550 kallsyms_expand_symbol 17 0.1545
c026b78f __copy_user_intel 31 0.2039
c026a5ec vsnprintf 39 0.0283
c026a318 number 40 0.0552
c011d102 write_profile 79 0.7182
c0131f39 is_exported 3805 17.0628
c0104028 default_idle 4254 86.8163
00000000 total 8325 0.0025
It's all in the O(n) is_exported(). Rusty's fault ;)
The is_exported function is only called for kernel symbols, and not
module symbols AFAICT.
If there is a way to know at compile time the exported symbols, then
scripts/kallsyms might generate a bitmap along with all the other data
it generates so that checking is_exported would become O(1).
For a tipical scenario of less than 16k symbols, the bitmap would take
2kB. If we don't want to spend this 2kB we can do something a little
more ugly:
The format of the compressed stream is basicaly:
[1 byte <name length>][N-bytes name]
repeated for every symbol. Since KSYM_NAME_LEN is defined to be 127, we
still have an extra bit in the length to keep the "is_exported"
information there. The format would then be:
[1 byte <7:is_exported bit>:<6..0:name length>][N-bytes name]
Of course, this limits future changes to KSYM_NAME_LEN :(
If the information is hard to get at compile time, then we could do a
single loop the first time the information is needed, and then use that
for subsequent calls.
But with this solved we could have sub-milisecond "cat /proc/kallsyms" :)
--
Paulo Marques - www.grupopie.com
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/