Message ID | 20160422152145.GA15003@char.us.oracle.com (mailing list archive) |
---|---|
State | New, archived |
Headers | show |
>>> On 22.04.16 at 17:21, <konrad.wilk@oracle.com> wrote: > Here is what I came up using your idea. Do you want me to add 'Suggested-by' > Jan on it? I'll leave that up to you; it was really just a vague idea that I gave... > --- a/xen/arch/x86/Makefile > +++ b/xen/arch/x86/Makefile > @@ -74,6 +74,9 @@ efi-y := $(shell if [ ! -r $(BASEDIR)/include/xen/compile.h -o \ > > ifdef CONFIG_XSPLICE > all_symbols = --all-symbols > +ifdef CONFIG_FAST_SYMBOL_LOOKUP > +all_symbols = --all-symbols --add-extra-sorted > +endif > else > all_symbols = > endif This now even more calls for using the common list model, at least as later cleanup. > --- a/xen/common/symbols-dummy.c > +++ b/xen/common/symbols-dummy.c > @@ -5,6 +5,7 @@ > > #include <xen/config.h> > #include <xen/types.h> > +#include <xen/symbols.h> > > #ifdef SYMBOLS_ORIGIN > const unsigned int symbols_offsets[1]; > @@ -14,6 +15,10 @@ const unsigned long symbols_addresses[1]; > const unsigned int symbols_num_syms; > const u8 symbols_names[1]; > > +#ifdef CONFIG_FAST_SYMBOL_LOOKUP > +const struct symbol_offset symbols_sorted_offsets[1]; > +#endif Oh, nice - you even do the sorting at build time! > --- a/xen/common/symbols.c > +++ b/xen/common/symbols.c > @@ -31,6 +31,10 @@ extern const unsigned long symbols_addresses[]; > extern const unsigned int symbols_num_syms; > extern const u8 symbols_names[]; > > +#ifdef CONFIG_FAST_SYMBOL_LOOKUP > +extern const struct symbol_offset symbols_sorted_offsets[]; > +#endif No need for an #ifdef around just a declaration. > @@ -208,8 +212,45 @@ int xensyms_read(uint32_t *symnum, char *type, > return 0; > } > > +#ifdef CONFIG_FAST_SYMBOL_LOOKUP > void *symbols_lookup_by_name(const char *symname) > { > + char namebuf[KSYM_NAME_LEN + 1]; > + unsigned long low, high; > + static const char *filename_token = "#"; It's being used just once, so I don't see the value of this. But if you want to retain it, please at least make it an array instead of a pointer. > + if ( *symname == '\0' ) > + return NULL; > + > + /* Unsupported search for filename in symbol right now. */ > + if ( strpbrk(symname, filename_token) ) > + return NULL; That's unfortunate - why are you filtering these out? (Related to the earlier comment - this could even be strchr(), with no need at all for a string literal.) > + low = 0; > + high = symbols_num_syms; > + while ( low < high ) > + { > + unsigned long mid = low + ((high - low) / 2); > + const struct symbol_offset *s; > + int rc; > + > + s = &symbols_sorted_offsets[mid]; > + (void)symbols_expand_symbol(s->stream, namebuf); > + /* Format is: [filename]#<symbol>. symbols_expand_symbol eats type.*/ [<filename>#]<symbol> And what relevance does the type part of the comment have here? > + rc = strcmp(symname, namebuf); So looking at this I really don't see why you filter filename prefixed input names above. > + if ( rc < 0 ) > + high = mid; > + else if ( rc > 0 ) > + low = mid + 1; > + else > + return (void *)symbols_address(s->addr); > + } > + return NULL; > +} > + > +#else > +void *symbols_lookup_by_name(const char *symname) > + { Please put the #ifdef/#else/#endif inside the function body, to avoid duplicating code as much as possible. Putting them outside would be needed primarily if the function type varied between the two instances. > +/* Sort by original (non mangled) symbol name, then type. */ > +static int compare_name_orig(const void *p1, const void *p2) > +{ > + const struct sym_entry *sym1 = p1; > + const struct sym_entry *sym2 = p2; > + int rc; > + > + rc = strcmp(sym1->orig_symbol, sym2->orig_symbol); > + > + if (!rc) { > + if (sym1->type < sym2->type) > + rc = -1; > + else if (sym1->type > sym2->type) > + rc = 1; > + else > + rc = 0; How about just "rc = sym1->type - sym2->type"? > @@ -350,6 +381,27 @@ static void write_src(void) > for (i = 0; i < 256; i++) > printf("\t.short\t%d\n", best_idx[i]); > printf("\n"); > + > + if (!extra_sorted) { > + free(markers); > + return; > + } > + > + /* Sorted by original symbol names, filename, and lastly type. */ > + qsort(table, table_cnt, sizeof(*table), compare_name_orig); > + > + output_label("symbols_sorted_offsets"); > + /* An fixed sized array with two entries: offset in the "A fixed size ..." > + * compressed stream (for symbol name), and offset in > + * symbols_addresses (or symbols_offset). */ > + for (i = 0; i < table_cnt; i++) { > + printf("\t.long %d", table[i].stream_offset); > + printf(", %d", table[i].addr_idx); > + printf("\n"); How about making this just a single printf()? Also both are unsigned, so please at least %u, but even better %#x. > @@ -561,6 +614,8 @@ int main(int argc, char **argv) > input_format = fmt_sysv; > else if (strcmp(argv[i], "--sort") == 0) > unsorted = true; > + else if (strcmp(argv[i], "--add-extra-sorted") == 0) > + extra_sorted = 1; s/extra/name/ ? Or --sort-by-name? Jan
On Mon, Apr 25, 2016 at 02:38:57AM -0600, Jan Beulich wrote: > >>> On 22.04.16 at 17:21, <konrad.wilk@oracle.com> wrote: > > Here is what I came up using your idea. Do you want me to add 'Suggested-by' > > Jan on it? > > I'll leave that up to you; it was really just a vague idea that I gave... > > > --- a/xen/arch/x86/Makefile > > +++ b/xen/arch/x86/Makefile > > @@ -74,6 +74,9 @@ efi-y := $(shell if [ ! -r $(BASEDIR)/include/xen/compile.h -o \ > > > > ifdef CONFIG_XSPLICE > > all_symbols = --all-symbols > > +ifdef CONFIG_FAST_SYMBOL_LOOKUP > > +all_symbols = --all-symbols --add-extra-sorted > > +endif > > else > > all_symbols = > > endif > > This now even more calls for using the common list model, at least as > later cleanup. OK, put it on the Wiki. > > > --- a/xen/common/symbols-dummy.c > > +++ b/xen/common/symbols-dummy.c > > @@ -5,6 +5,7 @@ > > > > #include <xen/config.h> > > #include <xen/types.h> > > +#include <xen/symbols.h> > > > > #ifdef SYMBOLS_ORIGIN > > const unsigned int symbols_offsets[1]; > > @@ -14,6 +15,10 @@ const unsigned long symbols_addresses[1]; > > const unsigned int symbols_num_syms; > > const u8 symbols_names[1]; > > > > +#ifdef CONFIG_FAST_SYMBOL_LOOKUP > > +const struct symbol_offset symbols_sorted_offsets[1]; > > +#endif > > Oh, nice - you even do the sorting at build time! :-) ..snip.. > > +#ifdef CONFIG_FAST_SYMBOL_LOOKUP > > void *symbols_lookup_by_name(const char *symname) > > { ..snip.. > > + /* Unsupported search for filename in symbol right now. */ > > + if ( strpbrk(symname, filename_token) ) > > + return NULL; > > That's unfortunate - why are you filtering these out? (Related to > the earlier comment - this could even be strchr(), with no need at > all for a string literal.) This was an artificat of the earlier version. Removed it all now. > > > + low = 0; > > + high = symbols_num_syms; > > + while ( low < high ) > > + { > > + unsigned long mid = low + ((high - low) / 2); > > + const struct symbol_offset *s; > > + int rc; > > + > > + s = &symbols_sorted_offsets[mid]; > > + (void)symbols_expand_symbol(s->stream, namebuf); > > + /* Format is: [filename]#<symbol>. symbols_expand_symbol eats type.*/ > > [<filename>#]<symbol> > > And what relevance does the type part of the comment have here? Artifact of the older version - Where I was searching for #. .. snip.p I removed the comment. > > + for (i = 0; i < table_cnt; i++) { > > + printf("\t.long %d", table[i].stream_offset); > > + printf(", %d", table[i].addr_idx); > > + printf("\n"); > > How about making this just a single printf()? Also both are unsigned, > so please at least %u, but even better %#x. I would rather have it as %u. As when debugging this I found it quite useful for these values to be decimal as I could edit the .xen-sym.0.S file and see in the editor where it would match up with the symbols_addresses or the symbol_names in a quite easy way. Doing it in hex means doing extra calculations. > > > @@ -561,6 +614,8 @@ int main(int argc, char **argv) > > input_format = fmt_sysv; > > else if (strcmp(argv[i], "--sort") == 0) > > unsorted = true; > > + else if (strcmp(argv[i], "--add-extra-sorted") == 0) > > + extra_sorted = 1; > > s/extra/name/ ? > > Or --sort-by-name? > > Jan
diff --git a/xen/arch/x86/Makefile b/xen/arch/x86/Makefile index fdf4202..f8b1b23 100644 --- a/xen/arch/x86/Makefile +++ b/xen/arch/x86/Makefile @@ -74,6 +74,9 @@ efi-y := $(shell if [ ! -r $(BASEDIR)/include/xen/compile.h -o \ ifdef CONFIG_XSPLICE all_symbols = --all-symbols +ifdef CONFIG_FAST_SYMBOL_LOOKUP +all_symbols = --all-symbols --add-extra-sorted +endif else all_symbols = endif diff --git a/xen/common/Kconfig b/xen/common/Kconfig index 692ef51..e4f86c2 100644 --- a/xen/common/Kconfig +++ b/xen/common/Kconfig @@ -200,4 +200,16 @@ config XSPLICE If unsure, say Y. +config FAST_SYMBOL_LOOKUP + bool "Fast symbol lookup (bigger binary)" + default y + depends on XSPLICE + ---help--- + When searching for symbol addresses we can use the built-in system + that is optimized for searching symbols using addresses as the key. + However using it for the inverse (find address using the symbol name) + it is slow. This extra data and code (~55kB) speeds up the search. + The only user of this is xSplice. + + If unsure, say Y. endmenu diff --git a/xen/common/symbols-dummy.c b/xen/common/symbols-dummy.c index 5090c3b..044dfd3 100644 --- a/xen/common/symbols-dummy.c +++ b/xen/common/symbols-dummy.c @@ -5,6 +5,7 @@ #include <xen/config.h> #include <xen/types.h> +#include <xen/symbols.h> #ifdef SYMBOLS_ORIGIN const unsigned int symbols_offsets[1]; @@ -14,6 +15,10 @@ const unsigned long symbols_addresses[1]; const unsigned int symbols_num_syms; const u8 symbols_names[1]; +#ifdef CONFIG_FAST_SYMBOL_LOOKUP +const struct symbol_offset symbols_sorted_offsets[1]; +#endif + const u8 symbols_token_table[1]; const u16 symbols_token_index[1]; diff --git a/xen/common/symbols.c b/xen/common/symbols.c index 18bbfef..789d90e 100644 --- a/xen/common/symbols.c +++ b/xen/common/symbols.c @@ -31,6 +31,10 @@ extern const unsigned long symbols_addresses[]; extern const unsigned int symbols_num_syms; extern const u8 symbols_names[]; +#ifdef CONFIG_FAST_SYMBOL_LOOKUP +extern const struct symbol_offset symbols_sorted_offsets[]; +#endif + extern const u8 symbols_token_table[]; extern const u16 symbols_token_index[]; @@ -208,8 +212,45 @@ int xensyms_read(uint32_t *symnum, char *type, return 0; } +#ifdef CONFIG_FAST_SYMBOL_LOOKUP void *symbols_lookup_by_name(const char *symname) { + char namebuf[KSYM_NAME_LEN + 1]; + unsigned long low, high; + static const char *filename_token = "#"; + + if ( *symname == '\0' ) + return NULL; + + /* Unsupported search for filename in symbol right now. */ + if ( strpbrk(symname, filename_token) ) + return NULL; + + low = 0; + high = symbols_num_syms; + while ( low < high ) + { + unsigned long mid = low + ((high - low) / 2); + const struct symbol_offset *s; + int rc; + + s = &symbols_sorted_offsets[mid]; + (void)symbols_expand_symbol(s->stream, namebuf); + /* Format is: [filename]#<symbol>. symbols_expand_symbol eats type.*/ + rc = strcmp(symname, namebuf); + if ( rc < 0 ) + high = mid; + else if ( rc > 0 ) + low = mid + 1; + else + return (void *)symbols_address(s->addr); + } + return NULL; +} + +#else +void *symbols_lookup_by_name(const char *symname) + { char name[KSYM_NAME_LEN + 1]; uint32_t symnum = 0; char type; @@ -232,6 +273,7 @@ void *symbols_lookup_by_name(const char *symname) return NULL; } +#endif /* * Local variables: * mode: C diff --git a/xen/include/xen/symbols.h b/xen/include/xen/symbols.h index 2122a5d..d4c4e1c 100644 --- a/xen/include/xen/symbols.h +++ b/xen/include/xen/symbols.h @@ -25,4 +25,14 @@ int xensyms_read(uint32_t *symnum, char *type, void *symbols_lookup_by_name(const char *symname); +#ifdef CONFIG_FAST_SYMBOL_LOOKUP +/* + * A sorted (by symbols) lookup table table to symbols_names (stream) + * and symbols_address (or offset). + */ +struct symbol_offset { + uint32_t stream; /* .. in the compressed stream.*/ + uint32_t addr; /* .. and in the fixed size address array. */ +}; +#endif #endif /*_XEN_SYMBOLS_H*/ diff --git a/xen/tools/symbols.c b/xen/tools/symbols.c index 196db74..78d9ef8 100644 --- a/xen/tools/symbols.c +++ b/xen/tools/symbols.c @@ -40,6 +40,10 @@ struct sym_entry { unsigned long long addr; unsigned int len; unsigned char *sym; + char *orig_symbol; + unsigned int addr_idx; + unsigned int stream_offset; + unsigned char type; }; #define SYMBOL_NAME(s) ((char *)(s)->sym + 1) @@ -47,8 +51,10 @@ static struct sym_entry *table; static unsigned int table_size, table_cnt; static unsigned long long _stext, _etext, _sinittext, _einittext, _sextratext, _eextratext; static int all_symbols = 0; +static int extra_sorted = 0; static char symbol_prefix_char = '\0'; static enum { fmt_bsd, fmt_sysv } input_format; +static int compare_name(const void *p1, const void *p2); int token_profit[0x10000]; @@ -174,9 +180,13 @@ static int read_symbol(FILE *in, struct sym_entry *s) sym = stpcpy(sym, filename); *sym++ = '#'; } + strcpy(sym, str); + if (extra_sorted) { + s->orig_symbol = strdup(SYMBOL_NAME(s)); + s->type = stype; /* As s->sym[0] ends mangled. */ + } s->sym[0] = stype; rc = 0; skip_tail: @@ -276,6 +286,27 @@ static int expand_symbol(unsigned char *data, int len, char *result) return total; } +/* Sort by original (non mangled) symbol name, then type. */ +static int compare_name_orig(const void *p1, const void *p2) +{ + const struct sym_entry *sym1 = p1; + const struct sym_entry *sym2 = p2; + int rc; + + rc = strcmp(sym1->orig_symbol, sym2->orig_symbol); + + if (!rc) { + if (sym1->type < sym2->type) + rc = -1; + else if (sym1->type > sym2->type) + rc = 1; + else + rc = 0; + } + + return rc; +} + static void write_src(void) { unsigned int i, k, off; @@ -325,6 +356,7 @@ static void write_src(void) printf(", 0x%02x", table[i].sym[k]); printf("\n"); + table[i].stream_offset = off; off += table[i].len + 1; } printf("\n"); @@ -334,7 +366,6 @@ static void write_src(void) printf("\t.long\t%d\n", markers[i]); printf("\n"); - free(markers); output_label("symbols_token_table"); off = 0; @@ -350,6 +381,27 @@ static void write_src(void) for (i = 0; i < 256; i++) printf("\t.short\t%d\n", best_idx[i]); printf("\n"); + + if (!extra_sorted) { + free(markers); + return; + } + + /* Sorted by original symbol names, filename, and lastly type. */ + qsort(table, table_cnt, sizeof(*table), compare_name_orig); + + output_label("symbols_sorted_offsets"); + /* An fixed sized array with two entries: offset in the + * compressed stream (for symbol name), and offset in + * symbols_addresses (or symbols_offset). */ + for (i = 0; i < table_cnt; i++) { + printf("\t.long %d", table[i].stream_offset); + printf(", %d", table[i].addr_idx); + printf("\n"); + } + printf("\n"); + + free(markers); } @@ -410,6 +462,7 @@ static void compress_symbols(unsigned char *str, int idx) len = table[i].len; p1 = table[i].sym; + table[i].addr_idx = i; /* find the token on the symbol */ p2 = memmem_pvt(p1, len, str, 2); if (!p2) continue; @@ -561,6 +614,8 @@ int main(int argc, char **argv) input_format = fmt_sysv; else if (strcmp(argv[i], "--sort") == 0) unsorted = true; + else if (strcmp(argv[i], "--add-extra-sorted") == 0) + extra_sorted = 1; else if (strcmp(argv[i], "--warn-dup") == 0) warn_dup = true; else