| Message ID | 20220909130016.727-2-thunder.leizhen@huawei.com (mailing list archive) |
|---|---|
| State | New, archived |
| Headers | show |
| Series | kallsyms: Optimizes the performance of lookup symbols | expand |
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. > 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@huawei.com> > --- > 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 */ [...] 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. 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? What about 3rd party modules? I would personally suggest to store the symbol type into a separate sym->type entry in struct sym_entry and never compress it. 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. Best Regards, Petr
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@huawei.com> >> --- >> 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 > . >
On 2022/9/21 10:42, Leizhen (ThunderTown) wrote: > > > 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@huawei.com> >>> --- >>> 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. The main thing is, I don't know if there will be any other impact after this change. If this doesn't work, I don't have to do it all over again. I can refactor it after it have been fully reviewed. > > 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 >> . >> >
On Wed 2022-09-21 10:42:56, Leizhen (ThunderTown) wrote: > > > 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. Ah, there is even v4. I have missed that. The commit message looks much better there. > 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@huawei.com> > >> --- > >> 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 > >> + */ > >> + 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. I guess that we are talking about different things. Anyway, please ignore my concern about that it is fragile. The change in scripts/kallsyms.c does not longer depend on --all-symbols parameter in the last v4 patchset. > > 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 This is another optimization. I agree that we could do it later after this patchset is accepted. Best Regards, Petr
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) ]++; } @@ -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. + */ + if (all_symbols) + sym_start_idx = 1; + read_map(stdin); shrink_table(); if (absolute_percpu)
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 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@huawei.com> --- scripts/kallsyms.c | 15 ++++++++++++--- 1 file changed, 12 insertions(+), 3 deletions(-)