From: "Jan Beulich" <JBeulich@suse.com>
To: Konrad Rzeszutek Wilk <konrad.wilk@oracle.com>
Cc: Keir Fraser <keir@xen.org>,
ross.lagerwall@citrix.com, andrew.cooper3@citrix.com,
mpohlack@amazon.de, sasha.levin@oracle.com,
xen-devel@lists.xenproject.org
Subject: Re: [PATCH v9 15/27] xsplice, symbols: Implement fast symbol names -> virtual addresses lookup
Date: Tue, 26 Apr 2016 09:53:24 -0600 [thread overview]
Message-ID: <571FAB1402000078000E603D@prv-mh.provo.novell.com> (raw)
In-Reply-To: <1461598514-5440-16-git-send-email-konrad.wilk@oracle.com>
>>> On 25.04.16 at 17:35, <konrad.wilk@oracle.com> wrote:
> 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 during build-time
> (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@oracle.com>
Reviewed-by: Jan Beulich <jbeulich@suse.com>
_______________________________________________
Xen-devel mailing list
Xen-devel@lists.xen.org
http://lists.xen.org/xen-devel
next prev parent reply other threads:[~2016-04-26 15:53 UTC|newest]
Thread overview: 90+ messages / expand[flat|nested] mbox.gz Atom feed top
2016-04-25 15:34 [PATCH 9] xSplice v1 design and implementation Konrad Rzeszutek Wilk
2016-04-25 15:34 ` [PATCH v9 01/27] Revert "libxc/libxl/python/xenstat/ocaml: Use new XEN_VERSION hypercall" Konrad Rzeszutek Wilk
2016-04-25 15:48 ` Jan Beulich
2016-04-25 15:53 ` Wei Liu
2016-04-25 15:34 ` [PATCH v9 02/27] Revert "HYPERCALL_version_op. New hypercall mirroring XENVER_ but sane." Konrad Rzeszutek Wilk
2016-04-25 15:34 ` [PATCH v9 03/27] xsplice: Design document Konrad Rzeszutek Wilk
2016-04-25 15:34 ` [PATCH v9 04/27] xen/xsplice: Hypervisor implementation of XEN_XSPLICE_op Konrad Rzeszutek Wilk
2016-04-26 7:48 ` Ross Lagerwall
2016-04-26 7:52 ` Ross Lagerwall
2016-04-26 10:21 ` Jan Beulich
2016-04-26 17:50 ` Konrad Rzeszutek Wilk
2016-04-27 6:51 ` Jan Beulich
2016-04-27 13:47 ` Konrad Rzeszutek Wilk
2016-04-27 14:11 ` Jan Beulich
2016-04-25 15:34 ` [PATCH v9 05/27] libxc: Implementation of XEN_XSPLICE_op in libxc Konrad Rzeszutek Wilk
2016-04-26 7:51 ` Ross Lagerwall
2016-04-25 15:34 ` [PATCH v9 06/27] xen-xsplice: Tool to manipulate xsplice payloads Konrad Rzeszutek Wilk
2016-04-26 7:49 ` Ross Lagerwall
2016-04-25 15:34 ` [PATCH v9 07/27] arm/x86: Use struct virtual_region to do bug, symbol, and (x86) exception tables lookup Konrad Rzeszutek Wilk
2016-04-26 10:31 ` Jan Beulich
2016-04-25 15:34 ` [PATCH v9 08/27] arm/x86/vmap: Add v[z|m]alloc_xen and vm_init_type Konrad Rzeszutek Wilk
2016-04-26 10:47 ` Jan Beulich
2016-04-27 2:38 ` Konrad Rzeszutek Wilk
2016-04-27 7:12 ` Jan Beulich
2016-04-27 13:46 ` Konrad Rzeszutek Wilk
2016-04-27 14:15 ` Jan Beulich
2016-04-25 15:34 ` [PATCH v9 09/27] x86/mm: Introduce modify_xen_mappings() Konrad Rzeszutek Wilk
2016-04-25 15:34 ` [PATCH v9 10/27] xsplice: Add helper elf routines Konrad Rzeszutek Wilk
2016-04-26 10:05 ` Ross Lagerwall
2016-04-26 11:52 ` Jan Beulich
2016-04-26 12:37 ` Jan Beulich
2016-04-27 1:59 ` Konrad Rzeszutek Wilk
2016-04-27 7:27 ` Jan Beulich
2016-04-27 14:00 ` Konrad Rzeszutek Wilk
2016-04-27 4:06 ` Konrad Rzeszutek Wilk
2016-04-27 7:52 ` Jan Beulich
2016-04-27 18:45 ` Konrad Rzeszutek Wilk
2016-04-25 15:34 ` [PATCH v9 11/27] xsplice: Implement payload loading Konrad Rzeszutek Wilk
2016-04-26 10:48 ` Ross Lagerwall
2016-04-26 13:39 ` Jan Beulich
2016-04-27 1:47 ` Konrad Rzeszutek Wilk
2016-04-27 7:57 ` Jan Beulich
2016-04-27 3:28 ` Konrad Rzeszutek Wilk
2016-04-27 8:28 ` Jan Beulich
2016-04-27 15:48 ` Konrad Rzeszutek Wilk
2016-04-27 16:06 ` Jan Beulich
2016-04-27 16:14 ` Jan Beulich
2016-04-27 18:40 ` Konrad Rzeszutek Wilk
2016-04-25 15:34 ` [PATCH v9 12/27] xsplice: Implement support for applying/reverting/replacing patches Konrad Rzeszutek Wilk
2016-04-26 15:21 ` Jan Beulich
2016-04-27 3:39 ` Konrad Rzeszutek Wilk
2016-04-27 8:36 ` Jan Beulich
2016-05-11 9:51 ` Martin Pohlack
2016-05-11 13:56 ` Konrad Rzeszutek Wilk
2016-04-25 15:35 ` [PATCH v9 13/27] x86/xen_hello_world.xsplice: Test payload for patching 'xen_extra_version' Konrad Rzeszutek Wilk
2016-04-26 15:31 ` Jan Beulich
2016-04-25 15:35 ` [PATCH v9 14/27] xsplice, symbols: Implement symbol name resolution on address Konrad Rzeszutek Wilk
2016-04-26 15:48 ` Jan Beulich
2016-04-25 15:35 ` [PATCH v9 15/27] xsplice, symbols: Implement fast symbol names -> virtual addresses lookup Konrad Rzeszutek Wilk
2016-04-26 15:53 ` Jan Beulich [this message]
2016-04-25 15:35 ` [PATCH v9 16/27] x86, xsplice: Print payload's symbol name and payload name in backtraces Konrad Rzeszutek Wilk
2016-04-26 11:06 ` Ross Lagerwall
2016-04-26 12:41 ` Jan Beulich
2016-04-26 12:48 ` Ross Lagerwall
2016-04-26 13:41 ` Jan Beulich
2016-04-27 3:31 ` Konrad Rzeszutek Wilk
2016-04-27 8:37 ` Jan Beulich
2016-04-25 15:35 ` [PATCH v9 17/27] xsplice: Add support for bug frames Konrad Rzeszutek Wilk
2016-04-26 11:05 ` Ross Lagerwall
2016-04-26 13:08 ` Ross Lagerwall
2016-04-26 15:58 ` Jan Beulich
2016-04-25 15:35 ` [PATCH v9 18/27] xsplice: Add support for exception tables Konrad Rzeszutek Wilk
2016-04-26 16:01 ` Jan Beulich
2016-04-25 15:35 ` [PATCH v9 19/27] xsplice: Add support for alternatives Konrad Rzeszutek Wilk
2016-04-27 8:58 ` Jan Beulich
2016-04-25 15:35 ` [PATCH v9 20/27] build_id: Provide ld-embedded build-ids Konrad Rzeszutek Wilk
2016-04-25 15:35 ` [PATCH v9 21/27] xsplice: Print build_id in keyhandler and on bootup Konrad Rzeszutek Wilk
2016-04-25 15:35 ` [PATCH v9 22/27] XENVER_build_id/libxc: Provide ld-embedded build-id Konrad Rzeszutek Wilk
2016-04-25 15:35 ` [PATCH v9 23/27] libxl: info: Display build_id of the hypervisor Konrad Rzeszutek Wilk
2016-04-25 15:35 ` [PATCH v9 24/27] xsplice: Stacking build-id dependency checking Konrad Rzeszutek Wilk
2016-04-27 9:27 ` Jan Beulich
2016-04-27 16:36 ` Konrad Rzeszutek Wilk
2016-04-28 9:47 ` Jan Beulich
2016-04-25 15:35 ` [PATCH v9 25/27] xsplice/xen_replace_world: Test-case for XSPLICE_ACTION_REPLACE Konrad Rzeszutek Wilk
2016-04-25 15:35 ` [PATCH v9 26/27] xsplice: Prevent duplicate payloads from being loaded Konrad Rzeszutek Wilk
2016-04-27 9:31 ` Jan Beulich
2016-04-25 15:35 ` [PATCH v9 27/27] MAINTAINERS/xsplice: Add myself and Ross as the maintainers Konrad Rzeszutek Wilk
2016-04-25 15:41 ` [PATCH 9] xSplice v1 design and implementation Jan Beulich
2016-04-25 15:47 ` Konrad Rzeszutek Wilk
2016-04-25 15:54 ` Jan Beulich
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=571FAB1402000078000E603D@prv-mh.provo.novell.com \
--to=jbeulich@suse.com \
--cc=andrew.cooper3@citrix.com \
--cc=keir@xen.org \
--cc=konrad.wilk@oracle.com \
--cc=mpohlack@amazon.de \
--cc=ross.lagerwall@citrix.com \
--cc=sasha.levin@oracle.com \
--cc=xen-devel@lists.xenproject.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).