[bpf-next,v3,00/10] Introduce type match support

Message

Daniel Müller June 28, 2022, 4:01 p.m. UTC

This patch set proposes the addition of a new way for performing type queries to
BPF. It introduces the "type matches" relation, similar to what is already
present with "type exists" (in the form of bpf_core_type_exists).

"type exists" performs fairly superficial checking, mostly concerned with
whether a type exists in the kernel and is of the same kind (enum/struct/...).
Notably, compatibility checks for members of composite types is lacking.

The newly introduced "type matches" (bpf_core_type_matches) fills this gap in
that it performs stricter checks: compatibility of members and existence of
similarly named enum variants is checked as well. E.g., given these definitions:

	struct task_struct___og { int pid; int tgid; };

	struct task_struct___foo { int foo; }

'task_struct___og' would "match" the kernel type 'task_struct', because the
members match up, while 'task_struct___foo' would not match, because the
kernel's 'task_struct' has no member named 'foo'.

More precisely, the "type match" relation is defined as follows (copied from
source):
- modifiers and typedefs are stripped (and, hence, effectively ignored)
- generally speaking types need to be of same kind (struct vs. struct, union
  vs. union, etc.)
  - exceptions are struct/union behind a pointer which could also match a
    forward declaration of a struct or union, respectively, and enum vs.
    enum64 (see below)
Then, depending on type:
- integers:
  - match if size and signedness match
- arrays & pointers:
  - target types are recursively matched
- structs & unions:
  - local members need to exist in target with the same name
  - for each member we recursively check match unless it is already behind a
    pointer, in which case we only check matching names and compatible kind
- enums:
  - local variants have to have a match in target by symbolic name (but not
    numeric value)
  - size has to match (but enum may match enum64 and vice versa)
- function pointers:
  - number and position of arguments in local type has to match target
  - for each argument and the return value we recursively check match

Enabling this feature requires a new relocation to be made known to the
compiler. This is being taken care of for LLVM as part of
https://reviews.llvm.org/D126838.

If applied, among other things, usage of this functionality could have helped
flag issues such as the one discussed here
https://lore.kernel.org/all/[e-mail]/
earlier.

Suggested-by: Andrii Nakryiko <[e-mail]>
---
Changelog:
v2 -> v3:
- renamed btfgen_mark_types_match
- covered BTF_KIND_RESTRICT in type match marking logic
- used bpf_core_names_match in more places
- reworked "behind pointer" logic
- added test using live task_struct

v1 -> v2:
- deduplicated and moved core algorithm into relo_core.c
- adjusted bpf_core_names_match to get btf_type passed in
- removed some length equality checks before strncmp usage
- correctly use kflag from targ_t instead of local_t
- added comment for meaning of kflag w/ FWD kind
- __u32 -> u32
- handle BTF_KIND_FWD properly in bpftool marking logic
- rebased

Daniel Müller (10):
  bpf: Introduce TYPE_MATCH related constants/macros
  bpftool: Honor BPF_CORE_TYPE_MATCHES relocation
  bpf: Introduce btf_int_bits() function
  libbpf: Add type match support
  bpf: Add type match support
  libbpf: Honor TYPE_MATCH relocation
  selftests/bpf: Add type-match checks to type-based tests
  selftests/bpf: Add test checking more characteristics
  selftests/bpf: Add nested type to type based tests
  selftests/bpf: Add type match test against kernel's task_struct

 include/linux/btf.h                           |   5 +
 include/uapi/linux/bpf.h                      |   1 +
 kernel/bpf/btf.c                              |   9 +
 tools/bpf/bpftool/gen.c                       | 108 +++++++
 tools/include/uapi/linux/bpf.h                |   1 +
 tools/lib/bpf/bpf_core_read.h                 |  11 +
 tools/lib/bpf/libbpf.c                        |   6 +
 tools/lib/bpf/relo_core.c                     | 284 +++++++++++++++++-
 tools/lib/bpf/relo_core.h                     |   4 +
 .../selftests/bpf/prog_tests/core_reloc.c     |  73 ++++-
 .../progs/btf__core_reloc_type_based___diff.c |   3 +
 .../selftests/bpf/progs/core_reloc_types.h    | 108 ++++++-
 .../bpf/progs/test_core_reloc_kernel.c        |  11 +
 .../bpf/progs/test_core_reloc_type_based.c    |  44 ++-
 14 files changed, 650 insertions(+), 18 deletions(-)
 create mode 100644 tools/testing/selftests/bpf/progs/btf__core_reloc_type_based___diff.c

Comments

Daniel Müller July 5, 2022, 9:07 p.m. UTC | #1

On Tue, Jun 28, 2022 at 04:01:17PM +0000, Daniel Müller wrote:
> This patch set proposes the addition of a new way for performing type queries to
> BPF. It introduces the "type matches" relation, similar to what is already
> present with "type exists" (in the form of bpf_core_type_exists).
> 
> "type exists" performs fairly superficial checking, mostly concerned with
> whether a type exists in the kernel and is of the same kind (enum/struct/...).
> Notably, compatibility checks for members of composite types is lacking.
> 
> The newly introduced "type matches" (bpf_core_type_matches) fills this gap in
> that it performs stricter checks: compatibility of members and existence of
> similarly named enum variants is checked as well. E.g., given these definitions:
> 
> 	struct task_struct___og { int pid; int tgid; };
> 
> 	struct task_struct___foo { int foo; }
> 
> 'task_struct___og' would "match" the kernel type 'task_struct', because the
> members match up, while 'task_struct___foo' would not match, because the
> kernel's 'task_struct' has no member named 'foo'.
> 
> More precisely, the "type match" relation is defined as follows (copied from
> source):
> - modifiers and typedefs are stripped (and, hence, effectively ignored)
> - generally speaking types need to be of same kind (struct vs. struct, union
>   vs. union, etc.)
>   - exceptions are struct/union behind a pointer which could also match a
>     forward declaration of a struct or union, respectively, and enum vs.
>     enum64 (see below)
> Then, depending on type:
> - integers:
>   - match if size and signedness match
> - arrays & pointers:
>   - target types are recursively matched
> - structs & unions:
>   - local members need to exist in target with the same name
>   - for each member we recursively check match unless it is already behind a
>     pointer, in which case we only check matching names and compatible kind
> - enums:
>   - local variants have to have a match in target by symbolic name (but not
>     numeric value)
>   - size has to match (but enum may match enum64 and vice versa)
> - function pointers:
>   - number and position of arguments in local type has to match target
>   - for each argument and the return value we recursively check match
> 
> Enabling this feature requires a new relocation to be made known to the
> compiler. This is being taken care of for LLVM as part of
> https://reviews.llvm.org/D126838.

To give an update here, LLVM changes have been merged and, to the best of my
knowledge, are being used by BPF CI (tests that failed earlier are now passing).

Thanks,
Daniel

[...]

Andrii Nakryiko July 6, 2022, 4:16 a.m. UTC | #2

On Tue, Jul 5, 2022 at 2:07 PM Daniel Müller <[e-mail]> wrote:
>
> On Tue, Jun 28, 2022 at 04:01:17PM +0000, Daniel Müller wrote:
> > This patch set proposes the addition of a new way for performing type queries to
> > BPF. It introduces the "type matches" relation, similar to what is already
> > present with "type exists" (in the form of bpf_core_type_exists).
> >
> > "type exists" performs fairly superficial checking, mostly concerned with
> > whether a type exists in the kernel and is of the same kind (enum/struct/...).
> > Notably, compatibility checks for members of composite types is lacking.
> >
> > The newly introduced "type matches" (bpf_core_type_matches) fills this gap in
> > that it performs stricter checks: compatibility of members and existence of
> > similarly named enum variants is checked as well. E.g., given these definitions:
> >
> >       struct task_struct___og { int pid; int tgid; };
> >
> >       struct task_struct___foo { int foo; }
> >
> > 'task_struct___og' would "match" the kernel type 'task_struct', because the
> > members match up, while 'task_struct___foo' would not match, because the
> > kernel's 'task_struct' has no member named 'foo'.
> >
> > More precisely, the "type match" relation is defined as follows (copied from
> > source):
> > - modifiers and typedefs are stripped (and, hence, effectively ignored)
> > - generally speaking types need to be of same kind (struct vs. struct, union
> >   vs. union, etc.)
> >   - exceptions are struct/union behind a pointer which could also match a
> >     forward declaration of a struct or union, respectively, and enum vs.
> >     enum64 (see below)
> > Then, depending on type:
> > - integers:
> >   - match if size and signedness match
> > - arrays & pointers:
> >   - target types are recursively matched
> > - structs & unions:
> >   - local members need to exist in target with the same name
> >   - for each member we recursively check match unless it is already behind a
> >     pointer, in which case we only check matching names and compatible kind
> > - enums:
> >   - local variants have to have a match in target by symbolic name (but not
> >     numeric value)
> >   - size has to match (but enum may match enum64 and vice versa)
> > - function pointers:
> >   - number and position of arguments in local type has to match target
> >   - for each argument and the return value we recursively check match
> >
> > Enabling this feature requires a new relocation to be made known to the
> > compiler. This is being taken care of for LLVM as part of
> > https://reviews.llvm.org/D126838.
>
> To give an update here, LLVM changes have been merged and, to the best of my
> knowledge, are being used by BPF CI (tests that failed earlier are now passing).
>

I did a few small changes and combined patches 4-6 together (because
they add the same functionality to both libbpf and kernel
simultaneously, there were compilation warnings about non-static
functions not having a proper prototype defined). But I've split out
the bpf_core_type_matches() macro in bpf_core_read.h into a separate
patch. I also dropped patch #3 as it wasn't needed anymore.

Please see comments I left for two further follow ups.

> Thanks,
> Daniel
>
> [...]

[e-mail] July 6, 2022, 4:20 a.m. UTC | #3

Hello:

This series was applied to bpf/bpf-next.git (master)
by Andrii Nakryiko <[e-mail]>:

On Tue, 28 Jun 2022 16:01:17 +0000 you wrote:
> This patch set proposes the addition of a new way for performing type queries to
> BPF. It introduces the "type matches" relation, similar to what is already
> present with "type exists" (in the form of bpf_core_type_exists).
> 
> "type exists" performs fairly superficial checking, mostly concerned with
> whether a type exists in the kernel and is of the same kind (enum/struct/...).
> Notably, compatibility checks for members of composite types is lacking.
> 
> [...]

Here is the summary with links:
  - [bpf-next,v3,01/10] bpf: Introduce TYPE_MATCH related constants/macros
    https://git.kernel.org/bpf/bpf-next/c/3c660a5d86f4
  - [bpf-next,v3,02/10] bpftool: Honor BPF_CORE_TYPE_MATCHES relocation
    https://git.kernel.org/bpf/bpf-next/c/633e7ceb2cbb
  - [bpf-next,v3,03/10] bpf: Introduce btf_int_bits() function
    (no matching commit)
  - [bpf-next,v3,04/10] libbpf: Add type match support
    https://git.kernel.org/bpf/bpf-next/c/ec6209c8d42f
  - [bpf-next,v3,05/10] bpf: Add type match support
    (no matching commit)
  - [bpf-next,v3,06/10] libbpf: Honor TYPE_MATCH relocation
    (no matching commit)
  - [bpf-next,v3,07/10] selftests/bpf: Add type-match checks to type-based tests
    https://git.kernel.org/bpf/bpf-next/c/67d8ed429525
  - [bpf-next,v3,08/10] selftests/bpf: Add test checking more characteristics
    https://git.kernel.org/bpf/bpf-next/c/bed56a6dd4cb
  - [bpf-next,v3,09/10] selftests/bpf: Add nested type to type based tests
    https://git.kernel.org/bpf/bpf-next/c/537905c4b68f
  - [bpf-next,v3,10/10] selftests/bpf: Add type match test against kernel's task_struct
    https://git.kernel.org/bpf/bpf-next/c/950b34778722

You are awesome, thank you!

Daniel Müller July 6, 2022, 4:06 p.m. UTC | #4

On Tue, Jul 05, 2022 at 09:16:27PM -0700, Andrii Nakryiko wrote:
> On Tue, Jul 5, 2022 at 2:07 PM Daniel Müller <[e-mail]> wrote:
> >
> > On Tue, Jun 28, 2022 at 04:01:17PM +0000, Daniel Müller wrote:
> > > This patch set proposes the addition of a new way for performing type queries to
> > > BPF. It introduces the "type matches" relation, similar to what is already
> > > present with "type exists" (in the form of bpf_core_type_exists).
> > >
> > > "type exists" performs fairly superficial checking, mostly concerned with
> > > whether a type exists in the kernel and is of the same kind (enum/struct/...).
> > > Notably, compatibility checks for members of composite types is lacking.
> > >
> > > The newly introduced "type matches" (bpf_core_type_matches) fills this gap in
> > > that it performs stricter checks: compatibility of members and existence of
> > > similarly named enum variants is checked as well. E.g., given these definitions:
> > >
> > >       struct task_struct___og { int pid; int tgid; };
> > >
> > >       struct task_struct___foo { int foo; }
> > >
> > > 'task_struct___og' would "match" the kernel type 'task_struct', because the
> > > members match up, while 'task_struct___foo' would not match, because the
> > > kernel's 'task_struct' has no member named 'foo'.
> > >
> > > More precisely, the "type match" relation is defined as follows (copied from
> > > source):
> > > - modifiers and typedefs are stripped (and, hence, effectively ignored)
> > > - generally speaking types need to be of same kind (struct vs. struct, union
> > >   vs. union, etc.)
> > >   - exceptions are struct/union behind a pointer which could also match a
> > >     forward declaration of a struct or union, respectively, and enum vs.
> > >     enum64 (see below)
> > > Then, depending on type:
> > > - integers:
> > >   - match if size and signedness match
> > > - arrays & pointers:
> > >   - target types are recursively matched
> > > - structs & unions:
> > >   - local members need to exist in target with the same name
> > >   - for each member we recursively check match unless it is already behind a
> > >     pointer, in which case we only check matching names and compatible kind
> > > - enums:
> > >   - local variants have to have a match in target by symbolic name (but not
> > >     numeric value)
> > >   - size has to match (but enum may match enum64 and vice versa)
> > > - function pointers:
> > >   - number and position of arguments in local type has to match target
> > >   - for each argument and the return value we recursively check match
> > >
> > > Enabling this feature requires a new relocation to be made known to the
> > > compiler. This is being taken care of for LLVM as part of
> > > https://reviews.llvm.org/D126838.
> >
> > To give an update here, LLVM changes have been merged and, to the best of my
> > knowledge, are being used by BPF CI (tests that failed earlier are now passing).
> >
> 
> I did a few small changes and combined patches 4-6 together (because
> they add the same functionality to both libbpf and kernel
> simultaneously, there were compilation warnings about non-static
> functions not having a proper prototype defined). But I've split out
> the bpf_core_type_matches() macro in bpf_core_read.h into a separate
> patch. I also dropped patch #3 as it wasn't needed anymore.
> 
> Please see comments I left for two further follow ups.

Sounds good. Will address your comments soon. Thanks for merging!

Daniel