Re: [PATCH] kallsyms data size reduction / lookup speedup

[Paulo Marques <pmarques@grupopie.com>]

Andrew Morton wrote:
> viro@parcelfarce.linux.theplanet.co.uk 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