|
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index] Re: [Xen-devel] [PATCH v8.1 15/27] xsplice, symbols: Implement fast symbol names -> virtual addresses lookup
On Tue, Apr 19, 2016 at 01:52:33PM -0600, Jan Beulich wrote:
> >>> Konrad Rzeszutek Wilk <konrad.wilk@xxxxxxxxxx> 04/14/16 12:02 AM >>>
> >NEW CODE:
> >
> >To make that work we add three tables:
>
> Why three? Two (or a single one with element pairs) ought to be sufficient:
> Afaict you could just have (symbol-address,symbol-offset) pairs which you
> then sort and search by name (using symbols_expand_symbol() on
> symbol-offset, which in turn you store using the result of get_symbol_offset()
> during setup of the table).
>
> >1) symbols_addresses_index_sorted[0..symbols_num_syms]. The values are
> >indicies into symbols_addresses array. This is a 1-1 table:
> >
> >symbols_addresses_index_sorted:
> >.long 6315
> >.long 6097
> >
> >To get the address of a symbol at offset 0 in symbols_name_sorted
> >(see below) we look in symbols_addresses_index_sorted[0] to get
> >6315 and then look in symbols_addresses_index[6315] to find it.
> >
> >2) The symbols_names_sorted stream - same format as symbols_names but
> >constructued by sorting the <type>[filename#]<symbol> by <symbol>,
> >then [filename#] and lastly type. Recall that symbol_names is sorted
> >based on addresses of the symbols.
>
> Why would you treat the <filename># prefix specially? The full thing is the
> symbol you should care about imo.
>
> >3) To make it simpler to search we also add an symbols_markers_sorted
> >array (of size symbols_num_syms/255).
>
> >Searching for symbols is simplified as we can do a binary search
> >on symbol_names_sorted (and using symbols_markers_sorted). Since the
> >symbols are sorted it takes on average 13 calls to symbols_expand_symbol.
> >
> >Doing small tests (search for five different symbols) using the old
> >and new mechanism show 2ms vs 0ms improvement.
>
> What does "2m vs 0ms" improvement mean here? If you mean to say that on
> some symbols there's no gain at all, then I'd question whether millisecond
> granularity is enough to see an improvement.
>
> With the basic data question above I'm not going to look at the actual code
> for now; I'll leave this until either I understand why the suggested variant
> can't work, or until a future version implementing that one.
Here is what I came up using your idea. Do you want me to add 'Suggested-by'
Jan on it?
From 37173f674e4bce0bc0515d28b2536d29c55b7e7f Mon Sep 17 00:00:00 2001
From: Konrad Rzeszutek Wilk <konrad.wilk@xxxxxxxxxx>
Date: Thu, 21 Apr 2016 16:47:43 -0400
Subject: [PATCH] xsplice, symbols: Implement fast symbol names -> virtual
addresses lookup
The current mechanism is geared towards fast virtual address ->
symbol names lookup. This is fine for the normal use cases
(BUG_ON, WARN_ON, etc), but for xSplice - where we need to find
hypervisor symbols - it is slow.
To understand this patch, a description of the existing
method is explained first. For folks familar go to 'NEW CODE:'.
HOW IT WORKS:
The symbol table lookup mechanism uses a simple encoding mechanism
where it extracts the common ascii characters that the symbol's use.
This saves us space. The lookup mechanism is geared towards looking
up symbols based on address. We have one 0..N (where N is
the number of symbols, so 6849 for example) table:
symbols_addresses[0..N]
And an 1-1 (in a loose fashion) of the symbols (encoded) in a
symbols_names stream of size N.
The N is variable (later on that below)
The symbols_names are sorted based on symbols_addresses, which
means that the decoded entries inside symbols_names are not in
ascending or descending order.
There is also the encoding mechanism - the table of 255 entries
called symbols_token_index[]. And the symbols_token_table which
is an stream of ASCIIZ characters, such as (it really
is not a table as the values are variable):
@0 .asciz "credit"
@6 .asciz "mask"
..
@300 .asciz "S"
And the symbols_token_index:
@0 .short 0
@1 .short 7
@2 .short 12
@4 .short 16
...
@84 .short 300
The relationship between them is that the symbols_token_index
gives us the offset to symbols_token_table.
The symbol_names[] array is a stream of encoded values. Each value
follows the same pattern - <len> followed by <encoding values>.
And the another <len> followed by <encoding values>.
Hence to find the right one you need to read <len>, add <len>
(to skip over), read <len>, add <len>, and so on until one
finds the right tuple offset.
The <encoding values> are the indicies into the symbols_token_index.
Meaning if you have:
0x04, 0x54, 0xda, 0xe2, 0x74
[4, 84, 218, 226, 116 in human numbering]
The 0x04 tells us that the symbol is four bytes past this one (so next
symbol offset starts at 5). If we lookup symbols_token_index[84] we get 300.
symbols_token[300] gets us the "S". And so on, the string eventually
end up being decode to be 'S_stext'. The first character is the type,
then optionally follwed by the filename (and # right after filename)
and then lastly the symbol, such as:
tvpmu_intel.c#core2_vpmu_do_interrupt
Keep in mind that there are two fixed sized tables:
symbols_addresses[0..symbols_num_syms], and
symbols_markers[0..symbols_num_syms/255].
The symbols_markers is used to speed searching for the right address.
It gives us the offsets within symbol_names that start at the <len><encoded
value>.
The way to find a symbol based on the address is:
1) Figure out the 'tuple offset' from symbols_address[0..symbols_num_syms].
This table is sorted by virtual addresses so finding the value is simple.
2) Get starting offset of symbol_names by retrieving value of
symbol_markers['tuple offset' / 255].
3). Iterate up to 'tuple_offset & 255' in symbols_markers stream starting
at 'offset'.
4). Decode the <len><encoded value>
This however does not work very well if we want to search the other
way - we have the symbol name and want to find the address.
NEW CODE:
To make that work we add one fixed size table called symbols_sorted_offsets
which
has two elements: offset in symbol stream, offset in the symbol-address.
This whole array is sorted on the original symbol name (in case of collision
we also take into account the type).
The values are for example:
symbols_sorted_offsets:
.long 83363, 6302 # [.bss, len=5]
.long 80459, 6084 # [.data, len=5]
..
[The # added for clarity]
Which makes it incredibly easy to get in the symbols_names and also
symbols_addresses (or symbols_offsets)
Searching for symbols is simplified as we can do a binary search
on symbols_sorted_offsets. Since the symbols are sorted it takes on
average 13 calls to symbols_expand_symbol.
Signed-off-by: Konrad Rzeszutek Wilk <konrad.wilk@xxxxxxxxxx>
---
CC: Keir Fraser <keir@xxxxxxx>
CC: Jan Beulich <jbeulich@xxxxxxxx>
CC: Andrew Cooper <andrew.cooper3@xxxxxxxxxx>
v8: New
- Remove the debug code
- Return the 'mid' index in symbol_addresses, not the 'low'.
v9:
- Make it return void*
- Ditch the old implementation. Use a single fixed-size array
with two uint32_t values - offset in stream and offset in address.
---
xen/arch/x86/Makefile | 3 +++
xen/common/Kconfig | 12 ++++++++++
xen/common/symbols-dummy.c | 5 ++++
xen/common/symbols.c | 42 +++++++++++++++++++++++++++++++++
xen/include/xen/symbols.h | 10 ++++++++
xen/tools/symbols.c | 59 ++++++++++++++++++++++++++++++++++++++++++++--
6 files changed, 129 insertions(+), 2 deletions(-)
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
--
2.5.0
_______________________________________________
Xen-devel mailing list
Xen-devel@xxxxxxxxxxxxx
http://lists.xen.org/xen-devel
|
 |
Lists.xenproject.org is hosted with RackSpace, monitoring our |