|
|
|
On Tue, Jul 19, 2016 at 05:19:20PM -0700, Kyle Laracey wrote: Alexei,
with stringmap the user space process will be able to populate the map
with its own strings, then the bpf prog can do bpf_get_unsafe_string
to put a string pointed to by uprobe parameter into a map.
The helper can return a flag whether string is present in the map.
That will be the equvalent of fast comparison of uprobe parameter
with a set of strings. Will that work for you?
If I'm understanding correctly, then yes that would work for us. I'm a
little confused by the exact semantics of "bpf_get_unsafe_string" (whether
it's putting or getting, as you mentioned "put"), but it sounds like it
would give us an ability to figure out if an arbitrary string were already
in the map.
Do you expect to compare with only one hardcoded string?
I expect the standard use case would be a single string, but it could be
the case that, e.g., the user wants to filter by a few query strings. I
don't expect any more than that. Either way, I think the solution is the
same: put the target string or strings in the map, and filter by indexing
into the map using "bpf_get_unsafe_string." excellent. I guess we need something like err = bpf_lookup_string(&stringmap, unsafe_ptr, len, flags, &handle) where flags are similar to normal maps any/exist/noexist, so program can insert maps if necessary or perform search over all strings already stored in the map. If inserted, the helper should return a handle that can later be used to retrieve the string. Even for single string compare with hard coded string it probably going to be more efficient, since bpf prog can only do byte by byte probe_read and compare with a lot of 'if' which will quickly make verifier go crazy. Best,
Kyle
On Tue, Jul 19, 2016 at 9:59 AM, Alexei Starovoitov <
alexei.starovoitov@...> wrote:
On Mon, Jul 18, 2016 at 01:57:24PM -0700, Kyle Laracey wrote:
Alexei,
What is your use case that needs strings?
We are trying to filter on SQL query strings at USDT probes in our product
(a database). We would like to be able to compare a string probe parameter
to another string which might be statically defined in the BPF script. It
sounds like you have been discussing loading strings in, which is an issue,
but more important to us would be string comparison. with stringmap the user space process will be able to populate the map
with its own strings, then the bpf prog can do bpf_get_unsafe_string
to put a string pointed to by uprobe parameter into a map.
The helper can return a flag whether string is present in the map.
That will be the equvalent of fast comparison of uprobe parameter
with a set of strings. Will that work for you?
Do you expect to compare with only one hardcoded string?
Thanks,
Kyle
On Fri, Jul 15, 2016 at 1:48 PM, Alexei Starovoitov <
alexei.starovoitov@...> wrote:
On Fri, Jul 15, 2016 at 12:56 AM, Sasha Goldshtein <goldshtn@... wrote:
On Fri, Jul 15, 2016 at 3:59 AM Alexei Starovoitov
<alexei.starovoitov@...> wrote:
On Wed, Jul 13, 2016 at 4:17 PM, Kyle Laracey via iovisor-dev
<iovisor-dev@...> wrote:
An additional issue brought up on the call (I apologize for
forgetting
by
whom) was that any comparisons on long strings would bloat the
program,
perhaps beyond the maximum allowed program size. Would the
solution to
this
be to have something like another BPF helper function in the
kernel?
the idea we discussed is to introduce string map similar to stackmap
where different strings are referenced by id. The helper would be
able
to push user or kernel strings into this map.
That should solve https://github.com/iovisor/bcc/issues/607
What is your use case that needs strings?
To come up with good kernel design we need to
categorize all use cases that need strings.
Both the trace and argdist tools collect strings from tracepoints,
uprobes/kprobes, and USDT tracepoints. These strings are displayed
to the
user (trace) [1] or used as keys for histograms and event frequency counters
(argdist) [2]. The length of the string is usually not known in
advance,
so
something like strcpy would be very useful.
The proposed string map solution would work as long as the kernel
helper
would be able to support two modes of operation: read string until
null
terminator, and read N characters. exactly. was thinking about:
u32 id = bpf_get_unsafe_string(map, unsafe_ptr, len_or_zero)
that returns negative error or 32-bit string id.
either it copies 'len' bytes or the whole string.
or a slight variant:
u64 id;
err = bpf_get_unsafe_string(map, unsafe_ptr, len_or_zero, &id)
64-bit ids will occupy more space when we'd need to store
them in other maps and/or pass to user space,
but 64bit space allows to encode short strings into
it as-is (little endian). Keeping real ids with 63rd bit set.
the main problem is that character memory needs to be
pre-allocated, since bpf can be called from contexts where
kmalloc is not allowed, so have to use gen_pool_alloc api.
the hash table to point to strings is probably enough
and we don't need a trie.
Any data structure suggestions?
We will also need a helper that can
actually retrieve the string based on its id. yes. from user space, right?
is there use case to do that from the bpf?
[1] Examples of tracing string values: file names being opened, JVM thread
names starting/finishing.
[2] Examples of frequency counting string values: web server URLs
being
hit
(e.g. in Node.js USDT probes), exec() command lines, JVM method names being
executed. yep. all makes sense.
Hannes,
do you know systemtap's use cases?
Hannes,
any news from systemtap guys? have you discussed stringmap proposal?
I'd like api to cover as many as possible requests before jumping into
implementation.
|
|
Alexei,
with stringmap the user space process will be able to populate the map
with its own strings, then the bpf prog can do bpf_get_unsafe_string
to put a string pointed to by uprobe parameter into a map.
The helper can return a flag whether string is present in the map.
That will be the equvalent of fast comparison of uprobe parameter
with a set of strings. Will that work for you?
If I'm understanding correctly, then yes that would work for us. I'm a little confused by the exact semantics of "bpf_get_unsafe_string" (whether it's putting or getting, as you mentioned "put"), but it sounds like it would give us an ability to figure out if an arbitrary string were already in the map.
Do you expect to compare with only one hardcoded string?
I expect the standard use case would be a single string, but it could be the case that, e.g., the user wants to filter by a few query strings. I don't expect any more than that. Either way, I think the solution is the same: put the target string or strings in the map, and filter by indexing into the map using "bpf_get_unsafe_string."
Best, Kyle
|
|
On Mon, Jul 18, 2016 at 01:57:24PM -0700, Kyle Laracey wrote: Alexei,
What is your use case that needs strings?
We are trying to filter on SQL query strings at USDT probes in our product
(a database). We would like to be able to compare a string probe parameter
to another string which might be statically defined in the BPF script. It
sounds like you have been discussing loading strings in, which is an issue,
but more important to us would be string comparison. with stringmap the user space process will be able to populate the map with its own strings, then the bpf prog can do bpf_get_unsafe_string to put a string pointed to by uprobe parameter into a map. The helper can return a flag whether string is present in the map. That will be the equvalent of fast comparison of uprobe parameter with a set of strings. Will that work for you? Do you expect to compare with only one hardcoded string? Thanks,
Kyle
On Fri, Jul 15, 2016 at 1:48 PM, Alexei Starovoitov <
alexei.starovoitov@...> wrote:
On Fri, Jul 15, 2016 at 12:56 AM, Sasha Goldshtein <goldshtn@...>
wrote:
On Fri, Jul 15, 2016 at 3:59 AM Alexei Starovoitov
<alexei.starovoitov@...> wrote:
On Wed, Jul 13, 2016 at 4:17 PM, Kyle Laracey via iovisor-dev
<iovisor-dev@...> wrote:
An additional issue brought up on the call (I apologize for forgetting
by
whom) was that any comparisons on long strings would bloat the
program,
perhaps beyond the maximum allowed program size. Would the solution to
this
be to have something like another BPF helper function in the kernel? the idea we discussed is to introduce string map similar to stackmap
where different strings are referenced by id. The helper would be able
to push user or kernel strings into this map.
That should solve https://github.com/iovisor/bcc/issues/607
What is your use case that needs strings?
To come up with good kernel design we need to
categorize all use cases that need strings.
Both the trace and argdist tools collect strings from tracepoints,
uprobes/kprobes, and USDT tracepoints. These strings are displayed to the
user (trace) [1] or used as keys for histograms and event frequency
counters
(argdist) [2]. The length of the string is usually not known in advance, so
something like strcpy would be very useful.
The proposed string map solution would work as long as the kernel helper
would be able to support two modes of operation: read string until null
terminator, and read N characters. exactly. was thinking about:
u32 id = bpf_get_unsafe_string(map, unsafe_ptr, len_or_zero)
that returns negative error or 32-bit string id.
either it copies 'len' bytes or the whole string.
or a slight variant:
u64 id;
err = bpf_get_unsafe_string(map, unsafe_ptr, len_or_zero, &id)
64-bit ids will occupy more space when we'd need to store
them in other maps and/or pass to user space,
but 64bit space allows to encode short strings into
it as-is (little endian). Keeping real ids with 63rd bit set.
the main problem is that character memory needs to be
pre-allocated, since bpf can be called from contexts where
kmalloc is not allowed, so have to use gen_pool_alloc api.
the hash table to point to strings is probably enough
and we don't need a trie.
Any data structure suggestions?
We will also need a helper that can
actually retrieve the string based on its id. yes. from user space, right?
is there use case to do that from the bpf?
[1] Examples of tracing string values: file names being opened, JVM thread
names starting/finishing.
[2] Examples of frequency counting string values: web server URLs being hit
(e.g. in Node.js USDT probes), exec() command lines, JVM method names being
executed. yep. all makes sense.
Hannes,
do you know systemtap's use cases? Hannes, any news from systemtap guys? have you discussed stringmap proposal? I'd like api to cover as many as possible requests before jumping into implementation.
|
|
Alexei, What is your use case that needs strings?
We are trying to filter on SQL query strings at USDT probes in our product (a database). We would like to be able to compare a string probe parameter to another string which might be statically defined in the BPF script. It sounds like you have been discussing loading strings in, which is an issue, but more important to us would be string comparison.
Thanks, Kyle
|
|
On Fri, Jul 15, 2016 at 12:56 AM, Sasha Goldshtein <goldshtn@...> wrote: On Fri, Jul 15, 2016 at 3:59 AM Alexei Starovoitov
<alexei.starovoitov@...> wrote:
On Wed, Jul 13, 2016 at 4:17 PM, Kyle Laracey via iovisor-dev
<iovisor-dev@...> wrote:
An additional issue brought up on the call (I apologize for forgetting
by
whom) was that any comparisons on long strings would bloat the program,
perhaps beyond the maximum allowed program size. Would the solution to
this
be to have something like another BPF helper function in the kernel?
the idea we discussed is to introduce string map similar to stackmap
where different strings are referenced by id. The helper would be able
to push user or kernel strings into this map.
That should solve https://github.com/iovisor/bcc/issues/607
What is your use case that needs strings?
To come up with good kernel design we need to
categorize all use cases that need strings.
Both the trace and argdist tools collect strings from tracepoints,
uprobes/kprobes, and USDT tracepoints. These strings are displayed to the
user (trace) [1] or used as keys for histograms and event frequency counters
(argdist) [2]. The length of the string is usually not known in advance, so
something like strcpy would be very useful.
The proposed string map solution would work as long as the kernel helper
would be able to support two modes of operation: read string until null
terminator, and read N characters. exactly. was thinking about: u32 id = bpf_get_unsafe_string(map, unsafe_ptr, len_or_zero) that returns negative error or 32-bit string id. either it copies 'len' bytes or the whole string. or a slight variant: u64 id; err = bpf_get_unsafe_string(map, unsafe_ptr, len_or_zero, &id) 64-bit ids will occupy more space when we'd need to store them in other maps and/or pass to user space, but 64bit space allows to encode short strings into it as-is (little endian). Keeping real ids with 63rd bit set. the main problem is that character memory needs to be pre-allocated, since bpf can be called from contexts where kmalloc is not allowed, so have to use gen_pool_alloc api. the hash table to point to strings is probably enough and we don't need a trie. Any data structure suggestions? We will also need a helper that can
actually retrieve the string based on its id. yes. from user space, right? is there use case to do that from the bpf? [1] Examples of tracing string values: file names being opened, JVM thread
names starting/finishing.
[2] Examples of frequency counting string values: web server URLs being hit
(e.g. in Node.js USDT probes), exec() command lines, JVM method names being
executed. yep. all makes sense. Hannes, do you know systemtap's use cases?
|
|
On Fri, Jul 15, 2016 at 3:59 AM Alexei Starovoitov < alexei.starovoitov@...> wrote: On Wed, Jul 13, 2016 at 4:17 PM, Kyle Laracey via iovisor-dev
<iovisor-dev@...> wrote:
>
> An additional issue brought up on the call (I apologize for forgetting by
> whom) was that any comparisons on long strings would bloat the program,
> perhaps beyond the maximum allowed program size. Would the solution to this
> be to have something like another BPF helper function in the kernel?
the idea we discussed is to introduce string map similar to stackmap
where different strings are referenced by id. The helper would be able
to push user or kernel strings into this map.
That should solve https://github.com/iovisor/bcc/issues/607
What is your use case that needs strings?
To come up with good kernel design we need to
categorize all use cases that need strings.
Both the trace and argdist tools collect strings from tracepoints, uprobes/kprobes, and USDT tracepoints. These strings are displayed to the user (trace) [1] or used as keys for histograms and event frequency counters (argdist) [2]. The length of the string is usually not known in advance, so something like strcpy would be very useful.
The proposed string map solution would work as long as the kernel helper would be able to support two modes of operation: read string until null terminator, and read N characters. We will also need a helper that can actually retrieve the string based on its id. [1] Examples of tracing string values: file names being opened, JVM thread names starting/finishing.
[2] Examples of frequency counting string values: web server URLs being hit (e.g. in Node.js USDT probes), exec() command lines, JVM method names being executed.
|
|
On Wed, Jul 13, 2016 at 4:17 PM, Kyle Laracey via iovisor-dev <iovisor-dev@...> wrote:
An additional issue brought up on the call (I apologize for forgetting by
whom) was that any comparisons on long strings would bloat the program,
perhaps beyond the maximum allowed program size. Would the solution to this
be to have something like another BPF helper function in the kernel?
the idea we discussed is to introduce string map similar to stackmap where different strings are referenced by id. The helper would be able to push user or kernel strings into this map. That should solve https://github.com/iovisor/bcc/issues/607What is your use case that needs strings? To come up with good kernel design we need to categorize all use cases that need strings.
|
|
Hi everyone,
Thanks for todays phone call; it was my first time calling in and was informative and helpful.
I just wanted to follow up on my question about filtering on string arguments of USDT probes. Thanks to Brendan for suggesting looking into LLVM's builtins (e.g. __builtin_memcmp, __builtin_strstr); my initial experimentation with them has been unsuccessful, but I plan to keep trying.
An additional issue brought up on the call (I apologize for forgetting by whom) was that any comparisons on long strings would bloat the program, perhaps beyond the maximum allowed program size. Would the solution to this be to have something like another BPF helper function in the kernel?
Something we may end up doing is passing u64 hash of our query string to our probes and filter on it. If anyone has other recommendations for workarounds, I'm all ears.
Thanks,
Kyle Laracey MemSQL Performance Engineer
|
|
