Re: [PATCH v2 1/8] scripts/kallsyms: don't compress symbol type when CONFIG_KALLSYMS_ALL=y

[Leizhen (ThunderTown)]

On 2022/9/21 1:26, Petr Mladek wrote:
> On Fri 2022-09-09 21:00:09, Zhen Lei wrote:
>> Currently, to search for a symbol, we need to expand the symbols in
>> 'kallsyms_names' one by one, and then use the expanded string for
>> comparison. This is very slow.
>>
>> In fact, we can first compress the name being looked up and then use
>> it for comparison when traversing 'kallsyms_names'.
> 
> This does not explain how this patch modifies the compressed data
> and why it is needed.

Yes, I have updated the description from the v3 version.

So if we don't compress the symbol type, we can first compress the
searched symbol and then make a quick comparison based on the compressed
length and content. In this way, for entries with mismatched lengths,
there is no need to expand and compare strings. And for those matching
lengths, there's no need to expand the symbol. This saves a lot of time.

> 
> 
>> This increases the size of 'kallsyms_names'. About 48KiB, 2.67%, on x86
>> with defconfig.
>> Before: kallsyms_num_syms=131392, sizeof(kallsyms_names)=1823659
>> After : kallsyms_num_syms=131392, sizeof(kallsyms_names)=1872418
>>
>> However, if CONFIG_KALLSYMS_ALL is not set, the size of 'kallsyms_names'
>> does not change.
>>
>> Signed-off-by: Zhen Lei <thunder.leizhen@xxxxxxxxxx>
>> ---
>>  scripts/kallsyms.c | 15 ++++++++++++---
>>  1 file changed, 12 insertions(+), 3 deletions(-)
>>
>> diff --git a/scripts/kallsyms.c b/scripts/kallsyms.c
>> index f18e6dfc68c5839..ab6fe7cd014efd1 100644
>> --- a/scripts/kallsyms.c
>> +++ b/scripts/kallsyms.c
>> @@ -60,6 +60,7 @@ static unsigned int table_size, table_cnt;
>>  static int all_symbols;
>>  static int absolute_percpu;
>>  static int base_relative;
>> +static int sym_start_idx;
>>  
>>  static int token_profit[0x10000];
>>  
>> @@ -511,7 +512,7 @@ static void learn_symbol(const unsigned char *symbol, int len)
>>  {
>>  	int i;
>>  
>> -	for (i = 0; i < len - 1; i++)
>> +	for (i = sym_start_idx; i < len - 1; i++)
>>  		token_profit[ symbol[i] + (symbol[i + 1] << 8) ]++;
> 
> This skips the first character in the @symbol string. I do not see how
> this is used in the new code, for example, in
> kallsyms_on_each_match_symbol(), in the 5th patch. It seems to iterate
> the compressed data from the 0th index:
> 
> 	for (i = 0, off = 0; i < kallsyms_num_syms; i++)
> 
>>  }
>>  
>> @@ -520,7 +521,7 @@ static void forget_symbol(const unsigned char *symbol, int len)
>>  {
>>  	int i;
>>  
>> -	for (i = 0; i < len - 1; i++)
>> +	for (i = sym_start_idx; i < len - 1; i++)
>>  		token_profit[ symbol[i] + (symbol[i + 1] << 8) ]--;
>>  }
>>  
>> @@ -538,7 +539,7 @@ static unsigned char *find_token(unsigned char *str, int len,
>>  {
>>  	int i;
>>  
>> -	for (i = 0; i < len - 1; i++) {
>> +	for (i = sym_start_idx; i < len - 1; i++) {
>>  		if (str[i] == token[0] && str[i+1] == token[1])
>>  			return &str[i];
>>  	}
>> @@ -780,6 +781,14 @@ int main(int argc, char **argv)
>>  	} else if (argc != 1)
>>  		usage();
>>  
>> +	/*
>> +	 * Skip the symbol type, do not compress it to optimize the performance
>> +	 * of finding or traversing symbols in kernel, this is good for modules
>> +	 * such as livepatch.
> 
> I see. The type is added as the first character here.
> 
> in static struct sym_entry *read_symbol(FILE *in)
> {
> [...]
> 	/* include the type field in the symbol name, so that it gets
> 	 * compressed together */

Good catch. I should remove "so that it gets compressed together"

> [...]
> 	sym->sym[0] = type;
> 	strcpy(sym_name(sym), name);
> 
> It sounds a bit crazy. read_symbol() makes a trick so that the type
> can be compressed. This patch does another trick to avoid it.
> 
> 
>> +	 */
>> +	if (all_symbols)
>> +		sym_start_idx = 1;
> 
> This looks a bit fragile. My understanding is that the new code in
> kernel/kallsyms.c and kernel/module/kallsyms.c depends on this change.

They do not depend on this change, because the index in
insert_real_symbols_in_table() is still starting from 0. kallsyms_expand_symbol()
shows that it uses every byte of the compressed data to look up the token table.
The index in insert_real_symbols_in_table() starting from 0 make sure that the
raw character of 'type' occupies a separate position in kallsyms_token_table[].
So that kallsyms_expand_symbol() can still work well.

> 
> The faster search is used when CONFIG_KALLSYMS_ALL is defined.
> But the data are compressed this way when this script is called
> with --all-symbols.
> 
> Is it guaranteed that this script will generate the needed data
> when CONFIG_KALLSYMS_ALL is defined?

Yes, see kallsyms() in scripts/link-vmlinux.sh
	if is_enabled CONFIG_KALLSYMS_ALL; then
                kallsymopt="${kallsymopt} --all-symbols"
        fi

> 
> What about 3rd party modules?

Should they call the API directly?

> 
> I would personally suggest to store the symbol type into a separate
> sym->type entry in struct sym_entry and never compress it.

Yes，I've also considered this, for the purpose of increasing the
compression ratio. See below, if the sorting is performed based on
the address and then based on the type. We can record all the symbol
type information in less than 100 bytes. Of course, this makes the
functions that look up symbols based on the address loop serveral
times more. However, I would like to wait until the current patch
series is accepted. Otherwise, I'll have to rework a lot of patches
and it's too much work. To be honest, I've been coding for it these days.

cat /proc/kallsyms | awk '{print $2}' | sort | uniq -c | sort -r
  44678 r
  38299 t
  28315 T
  11644 d
   3768 D
   2778 b
    778 R
    641 B
    282 A
    178 W
     37 V

> 
> IMHO, the size win is not worth the code complexity.
> 
> Well, people compiling the kernel for small devices might think
> different. But they probably disable kallsyms completely.

Yes, to make the code look better, I've stopped binding CONFIG_KALLSYMS_ALL since v3.

3. The symbol type is not compressed regardless of whether
   CONFIG_KALLSYMS_ALL is set or not. The memory overhead is increased
   by less than 20KiB if CONFIG_KALLSYMS_ALL=n.

> 
> Best Regards,
> Petr
> .
> 

-- 
Regards,
  Zhen Lei