Re: [PATCH v2 bpf-next 02/12] libbpf: implement BPF CO-RE offset relocation algorithm

Song Liu
2019-07-31T00:16:30Z

> On Jul 30, 2019, at 4:55 PM, Andrii Nakryiko <andrii.nakryiko@gmail.com> wrote:
>
> On Tue, Jul 30, 2019 at 4:44 PM Song Liu <songliubraving@fb.com> wrote:
>>
>>
>>
>>> On Jul 30, 2019, at 12:53 PM, Andrii Nakryiko <andriin@fb.com> wrote:
>>>
>>> This patch implements the core logic for BPF CO-RE offsets relocations.
>>> Every instruction that needs to be relocated has corresponding
>>> bpf_offset_reloc as part of BTF.ext. Relocations are performed by trying
>>> to match recorded "local" relocation spec against potentially many
>>> compatible "target" types, creating corresponding spec. Details of the
>>> algorithm are noted in corresponding comments in the code.
>>>
>>> Signed-off-by: Andrii Nakryiko <andriin@fb.com>
>>> ---
>>> tools/lib/bpf/libbpf.c | 915 ++++++++++++++++++++++++++++++++++++++++-
>>> tools/lib/bpf/libbpf.h | 1 +
>>> 2 files changed, 909 insertions(+), 7 deletions(-)
>>>
>>> diff --git a/tools/lib/bpf/libbpf.c b/tools/lib/bpf/libbpf.c
>>> index ead915aec349..75da90928257 100644
>>> --- a/tools/lib/bpf/libbpf.c
>>> +++ b/tools/lib/bpf/libbpf.c
>>> @@ -38,6 +38,7 @@
>
> [...]
>
>>>
>>> -static const struct btf_type *skip_mods_and_typedefs(const struct btf *btf,
>>> - __u32 id)
>>> +static const struct btf_type *
>>> +skip_mods_and_typedefs(const struct btf *btf, __u32 id, __u32 *res_id)
>>> {
>>> const struct btf_type *t = btf__type_by_id(btf, id);
>>>
>>> + if (res_id)
>>> + *res_id = id;
>>> +
>>> while (true) {
>>> switch (BTF_INFO_KIND(t->info)) {
>>> case BTF_KIND_VOLATILE:
>>> case BTF_KIND_CONST:
>>> case BTF_KIND_RESTRICT:
>>> case BTF_KIND_TYPEDEF:
>>> + if (res_id)
>>> + *res_id = t->type;
>>> t = btf__type_by_id(btf, t->type);
>>
>> So btf->types[*res_id] == retval, right? Then with retval and btf, we can
>> calculate *res_id without this change?
>
> Unless I'm missing something very clever here, no. btf->types is array
> of pointers (it's an index into a variable-sized types). This function
> returns `struct btf_type *`, which is one of the **values** stored in
> that array. You are claiming that by having value of one of array
> elements you can easily find element's index? If it was possible to do
> in O(1), we wouldn't have so many algorithms and data structures for
> search and indexing. You can do that only with linear search, not some
> clever pointer arithmetic or at least binary search. So I'm not sure
> what you are proposing here...

oops.. Clearly, I made some silly mistake. Sorry for the noise.

Song

>
> The way BTF is defined, struct btf_type doesn't know its own type ID,
> which is often inconvenient and requires to keep track of that ID, if
> it's necessary, but that's how it is.
>
> But then again, what are we trying to achieve here? Eliminate
> returning id and pointer? I could always return id and easily look up
> pointer, but having both is super convenient and makes code simpler
> and shorter, so I'd like to keep it.
>
>>
>>> break;
>>> default:
>>> @@ -1044,7 +1051,7 @@ static const struct btf_type *skip_mods_and_typedefs(const struct btf *btf,
>>> static bool get_map_field_int(const char *map_name, const struct btf *btf,
>>> const struct btf_type *def,
>>> const struct btf_member *m, __u32 *res) {
>
> …