| Message ID | 20230212092715.1422619-4-davemarchevsky@fb.com (mailing list archive) |
|---|---|
| State | Superseded |
| Delegated to: | BPF |
| Headers | show |
| Series | BPF rbtree next-gen datastructure | expand |
Hi Dave,
Thank you for the patch! Perhaps something to improve:
[auto build test WARNING on bpf-next/master]
url: https://github.com/intel-lab-lkp/linux/commits/Dave-Marchevsky/bpf-Migrate-release_on_unlock-logic-to-non-owning-ref-semantics/20230212-172813
base: https://git.kernel.org/pub/scm/linux/kernel/git/bpf/bpf-next.git master
patch link: https://lore.kernel.org/r/20230212092715.1422619-4-davemarchevsky%40fb.com
patch subject: [PATCH v5 bpf-next 3/9] bpf: Add bpf_rbtree_{add,remove,first} kfuncs
config: hexagon-randconfig-r045-20230212 (https://download.01.org/0day-ci/archive/20230212/202302121936.t36vlAFG-lkp@intel.com/config)
compiler: clang version 17.0.0 (https://github.com/llvm/llvm-project db0e6591612b53910a1b366863348bdb9d7d2fb1)
reproduce (this is a W=1 build):
wget https://raw.githubusercontent.com/intel/lkp-tests/master/sbin/make.cross -O ~/bin/make.cross
chmod +x ~/bin/make.cross
# https://github.com/intel-lab-lkp/linux/commit/39ccb1ecaa4f95d55dfd9ba495ecefe3fe1f6982
git remote add linux-review https://github.com/intel-lab-lkp/linux
git fetch --no-tags linux-review Dave-Marchevsky/bpf-Migrate-release_on_unlock-logic-to-non-owning-ref-semantics/20230212-172813
git checkout 39ccb1ecaa4f95d55dfd9ba495ecefe3fe1f6982
# save the config file
mkdir build_dir && cp config build_dir/.config
COMPILER_INSTALL_PATH=$HOME/0day COMPILER=clang make.cross W=1 O=build_dir ARCH=hexagon olddefconfig
COMPILER_INSTALL_PATH=$HOME/0day COMPILER=clang make.cross W=1 O=build_dir ARCH=hexagon SHELL=/bin/bash kernel/bpf/
If you fix the issue, kindly add following tag where applicable
| Reported-by: kernel test robot <lkp@intel.com>
| Link: https://lore.kernel.org/oe-kbuild-all/202302121936.t36vlAFG-lkp@intel.com/
All warnings (new ones prefixed by >>):
In file included from kernel/bpf/helpers.c:4:
In file included from include/linux/bpf.h:31:
In file included from include/linux/memcontrol.h:13:
In file included from include/linux/cgroup.h:26:
In file included from include/linux/kernel_stat.h:9:
In file included from include/linux/interrupt.h:11:
In file included from include/linux/hardirq.h:11:
In file included from ./arch/hexagon/include/generated/asm/hardirq.h:1:
In file included from include/asm-generic/hardirq.h:17:
In file included from include/linux/irq.h:20:
In file included from include/linux/io.h:13:
In file included from arch/hexagon/include/asm/io.h:334:
include/asm-generic/io.h:547:31: warning: performing pointer arithmetic on a null pointer has undefined behavior [-Wnull-pointer-arithmetic]
val = __raw_readb(PCI_IOBASE + addr);
~~~~~~~~~~ ^
include/asm-generic/io.h:560:61: warning: performing pointer arithmetic on a null pointer has undefined behavior [-Wnull-pointer-arithmetic]
val = __le16_to_cpu((__le16 __force)__raw_readw(PCI_IOBASE + addr));
~~~~~~~~~~ ^
include/uapi/linux/byteorder/little_endian.h:37:51: note: expanded from macro '__le16_to_cpu'
#define __le16_to_cpu(x) ((__force __u16)(__le16)(x))
^
In file included from kernel/bpf/helpers.c:4:
In file included from include/linux/bpf.h:31:
In file included from include/linux/memcontrol.h:13:
In file included from include/linux/cgroup.h:26:
In file included from include/linux/kernel_stat.h:9:
In file included from include/linux/interrupt.h:11:
In file included from include/linux/hardirq.h:11:
In file included from ./arch/hexagon/include/generated/asm/hardirq.h:1:
In file included from include/asm-generic/hardirq.h:17:
In file included from include/linux/irq.h:20:
In file included from include/linux/io.h:13:
In file included from arch/hexagon/include/asm/io.h:334:
include/asm-generic/io.h:573:61: warning: performing pointer arithmetic on a null pointer has undefined behavior [-Wnull-pointer-arithmetic]
val = __le32_to_cpu((__le32 __force)__raw_readl(PCI_IOBASE + addr));
~~~~~~~~~~ ^
include/uapi/linux/byteorder/little_endian.h:35:51: note: expanded from macro '__le32_to_cpu'
#define __le32_to_cpu(x) ((__force __u32)(__le32)(x))
^
In file included from kernel/bpf/helpers.c:4:
In file included from include/linux/bpf.h:31:
In file included from include/linux/memcontrol.h:13:
In file included from include/linux/cgroup.h:26:
In file included from include/linux/kernel_stat.h:9:
In file included from include/linux/interrupt.h:11:
In file included from include/linux/hardirq.h:11:
In file included from ./arch/hexagon/include/generated/asm/hardirq.h:1:
In file included from include/asm-generic/hardirq.h:17:
In file included from include/linux/irq.h:20:
In file included from include/linux/io.h:13:
In file included from arch/hexagon/include/asm/io.h:334:
include/asm-generic/io.h:584:33: warning: performing pointer arithmetic on a null pointer has undefined behavior [-Wnull-pointer-arithmetic]
__raw_writeb(value, PCI_IOBASE + addr);
~~~~~~~~~~ ^
include/asm-generic/io.h:594:59: warning: performing pointer arithmetic on a null pointer has undefined behavior [-Wnull-pointer-arithmetic]
__raw_writew((u16 __force)cpu_to_le16(value), PCI_IOBASE + addr);
~~~~~~~~~~ ^
include/asm-generic/io.h:604:59: warning: performing pointer arithmetic on a null pointer has undefined behavior [-Wnull-pointer-arithmetic]
__raw_writel((u32 __force)cpu_to_le32(value), PCI_IOBASE + addr);
~~~~~~~~~~ ^
>> kernel/bpf/helpers.c:1901:9: warning: cast from 'bool (*)(struct bpf_rb_node *, const struct bpf_rb_node *)' (aka '_Bool (*)(struct bpf_rb_node *, const struct bpf_rb_node *)') to 'bool (*)(struct rb_node *, const struct rb_node *)' (aka '_Bool (*)(struct rb_node *, const struct rb_node *)') converts to incompatible function type [-Wcast-function-type-strict]
(bool (*)(struct rb_node *, const struct rb_node *))less);
^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
7 warnings generated.
vim +1901 kernel/bpf/helpers.c
1896
1897 void bpf_rbtree_add(struct bpf_rb_root *root, struct bpf_rb_node *node,
1898 bool (less)(struct bpf_rb_node *a, const struct bpf_rb_node *b))
1899 {
1900 rb_add_cached((struct rb_node *)node, (struct rb_root_cached *)root,
> 1901 (bool (*)(struct rb_node *, const struct rb_node *))less);
1902 }
1903
On 2/12/23 6:21 AM, kernel test robot wrote: > Hi Dave, > > Thank you for the patch! Perhaps something to improve: > > [auto build test WARNING on bpf-next/master] > > url: https://github.com/intel-lab-lkp/linux/commits/Dave-Marchevsky/bpf-Migrate-release_on_unlock-logic-to-non-owning-ref-semantics/20230212-172813 > base: https://git.kernel.org/pub/scm/linux/kernel/git/bpf/bpf-next.git master > patch link: https://lore.kernel.org/r/20230212092715.1422619-4-davemarchevsky%40fb.com > patch subject: [PATCH v5 bpf-next 3/9] bpf: Add bpf_rbtree_{add,remove,first} kfuncs > config: hexagon-randconfig-r045-20230212 (https://download.01.org/0day-ci/archive/20230212/202302121936.t36vlAFG-lkp@intel.com/config ) > compiler: clang version 17.0.0 (https://github.com/llvm/llvm-project db0e6591612b53910a1b366863348bdb9d7d2fb1) > reproduce (this is a W=1 build): > wget https://raw.githubusercontent.com/intel/lkp-tests/master/sbin/make.cross -O ~/bin/make.cross > chmod +x ~/bin/make.cross > # https://github.com/intel-lab-lkp/linux/commit/39ccb1ecaa4f95d55dfd9ba495ecefe3fe1f6982 > git remote add linux-review https://github.com/intel-lab-lkp/linux > git fetch --no-tags linux-review Dave-Marchevsky/bpf-Migrate-release_on_unlock-logic-to-non-owning-ref-semantics/20230212-172813 > git checkout 39ccb1ecaa4f95d55dfd9ba495ecefe3fe1f6982 > # save the config file > mkdir build_dir && cp config build_dir/.config > COMPILER_INSTALL_PATH=$HOME/0day COMPILER=clang make.cross W=1 O=build_dir ARCH=hexagon olddefconfig > COMPILER_INSTALL_PATH=$HOME/0day COMPILER=clang make.cross W=1 O=build_dir ARCH=hexagon SHELL=/bin/bash kernel/bpf/ > > If you fix the issue, kindly add following tag where applicable > | Reported-by: kernel test robot <lkp@intel.com> > | Link: https://lore.kernel.org/oe-kbuild-all/202302121936.t36vlAFG-lkp@intel.com/ > > All warnings (new ones prefixed by >>): > > In file included from kernel/bpf/helpers.c:4: > In file included from include/linux/bpf.h:31: > In file included from include/linux/memcontrol.h:13: > In file included from include/linux/cgroup.h:26: > In file included from include/linux/kernel_stat.h:9: > In file included from include/linux/interrupt.h:11: > In file included from include/linux/hardirq.h:11: > In file included from ./arch/hexagon/include/generated/asm/hardirq.h:1: > In file included from include/asm-generic/hardirq.h:17: > In file included from include/linux/irq.h:20: > In file included from include/linux/io.h:13: > In file included from arch/hexagon/include/asm/io.h:334: > include/asm-generic/io.h:547:31: warning: performing pointer arithmetic on a null pointer has undefined behavior [-Wnull-pointer-arithmetic] > val = __raw_readb(PCI_IOBASE + addr); > ~~~~~~~~~~ ^ > include/asm-generic/io.h:560:61: warning: performing pointer arithmetic on a null pointer has undefined behavior [-Wnull-pointer-arithmetic] > val = __le16_to_cpu((__le16 __force)__raw_readw(PCI_IOBASE + addr)); > ~~~~~~~~~~ ^ > include/uapi/linux/byteorder/little_endian.h:37:51: note: expanded from macro '__le16_to_cpu' > #define __le16_to_cpu(x) ((__force __u16)(__le16)(x)) > ^ > In file included from kernel/bpf/helpers.c:4: > In file included from include/linux/bpf.h:31: > In file included from include/linux/memcontrol.h:13: > In file included from include/linux/cgroup.h:26: > In file included from include/linux/kernel_stat.h:9: > In file included from include/linux/interrupt.h:11: > In file included from include/linux/hardirq.h:11: > In file included from ./arch/hexagon/include/generated/asm/hardirq.h:1: > In file included from include/asm-generic/hardirq.h:17: > In file included from include/linux/irq.h:20: > In file included from include/linux/io.h:13: > In file included from arch/hexagon/include/asm/io.h:334: > include/asm-generic/io.h:573:61: warning: performing pointer arithmetic on a null pointer has undefined behavior [-Wnull-pointer-arithmetic] > val = __le32_to_cpu((__le32 __force)__raw_readl(PCI_IOBASE + addr)); > ~~~~~~~~~~ ^ > include/uapi/linux/byteorder/little_endian.h:35:51: note: expanded from macro '__le32_to_cpu' > #define __le32_to_cpu(x) ((__force __u32)(__le32)(x)) > ^ > In file included from kernel/bpf/helpers.c:4: > In file included from include/linux/bpf.h:31: > In file included from include/linux/memcontrol.h:13: > In file included from include/linux/cgroup.h:26: > In file included from include/linux/kernel_stat.h:9: > In file included from include/linux/interrupt.h:11: > In file included from include/linux/hardirq.h:11: > In file included from ./arch/hexagon/include/generated/asm/hardirq.h:1: > In file included from include/asm-generic/hardirq.h:17: > In file included from include/linux/irq.h:20: > In file included from include/linux/io.h:13: > In file included from arch/hexagon/include/asm/io.h:334: > include/asm-generic/io.h:584:33: warning: performing pointer arithmetic on a null pointer has undefined behavior [-Wnull-pointer-arithmetic] > __raw_writeb(value, PCI_IOBASE + addr); > ~~~~~~~~~~ ^ > include/asm-generic/io.h:594:59: warning: performing pointer arithmetic on a null pointer has undefined behavior [-Wnull-pointer-arithmetic] > __raw_writew((u16 __force)cpu_to_le16(value), PCI_IOBASE + addr); > ~~~~~~~~~~ ^ > include/asm-generic/io.h:604:59: warning: performing pointer arithmetic on a null pointer has undefined behavior [-Wnull-pointer-arithmetic] > __raw_writel((u32 __force)cpu_to_le32(value), PCI_IOBASE + addr); > ~~~~~~~~~~ ^ >>> kernel/bpf/helpers.c:1901:9: warning: cast from 'bool (*)(struct bpf_rb_node *, const struct bpf_rb_node *)' (aka '_Bool (*)(struct bpf_rb_node *, const struct bpf_rb_node *)') to 'bool (*)(struct rb_node *, const struct rb_node *)' (aka '_Bool (*)(struct rb_node *, const struct rb_node *)') converts to incompatible function type [-Wcast-function-type-strict] > (bool (*)(struct rb_node *, const struct rb_node *))less); > ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ This is the only new warning introduced by this series. A previous version had the same complaint by kernel test robot. struct bpf_rb_node is an opaque struct with the same size as struct rb_node. It's not intended to be manipulated directly by any BPF program or bpf-rbtree kernel code, but rather to be used as a struct rb_node by rbtree library helpers. Here, the compiler complains that the less() callback taken by bpf_rbtree_add is typed bool (*)(struct bpf_rb_node *, const struct bpf_rb_node *) while the actual rbtree lib helper rb_add's less() is typed bool (*)(struct rb_node *, const struct rb_node *) I'm not a C standard expert, but based on my googling, for C99 it's not valid to cast a function pointer to anything aside from void* and its original type. Furthermore, since struct bpf_rb_node an opaque bitfield and struct rb_node has actual members, C99 standard 6.2.7 paragraph 1 states that they're not compatible: Moreover, two structure, union, or enumerated types declared in separate translation units are compatible if their tags and members satisfy the following requirements: If one is declared with a tag, the other shall be declared with the same tag. If both are complete types, then the following additional requirements apply: there shall be a one-to-one correspondence between their members such that each pair of corresponding members are declared with compatible types, and such that if one member of a corresponding pair is declared with a name, the other member is declared with the same name. For two structures, corresponding members shall be declared in the same order I'm not sure how to proceed here. We could change bpf_rbtree_add's less() cb to take two rb_node *'s, but then each such cb implementation would have to cast its parameters before doing anything useful with them. Furthermore this would require introducing non-opaque rb_node type into BPF programs. Other ideas seem similarly hacky. Note that this flag was only recently introduced [0] and discussion in that linked thread notes that ~1500 other places in the kernel raise same warning. [0]: https://reviews.llvm.org/D134831 > 7 warnings generated. > > > vim +1901 kernel/bpf/helpers.c > > 1896 > 1897 void bpf_rbtree_add(struct bpf_rb_root *root, struct bpf_rb_node *node, > 1898 bool (less)(struct bpf_rb_node *a, const struct bpf_rb_node *b)) > 1899 { > 1900 rb_add_cached((struct rb_node *)node, (struct rb_root_cached *)root, >> 1901 (bool (*)(struct rb_node *, const struct rb_node *))less); > 1902 } > 1903 >
On Mon, Feb 13, 2023 at 12:45 PM Dave Marchevsky <davemarchevsky@meta.com> wrote: > > On 2/12/23 6:21 AM, kernel test robot wrote: > > Hi Dave, > > > >>> kernel/bpf/helpers.c:1901:9: warning: cast from 'bool (*)(struct bpf_rb_node *, const struct bpf_rb_node *)' (aka '_Bool (*)(struct bpf_rb_node *, const struct bpf_rb_node *)') to 'bool (*)(struct rb_node *, const struct rb_node *)' (aka '_Bool (*)(struct rb_node *, const struct rb_node *)') converts to incompatible function type [-Wcast-function-type-strict] > > (bool (*)(struct rb_node *, const struct rb_node *))less); > > ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ > > This is the only new warning introduced by this series. A previous version had > the same complaint by kernel test robot. > > struct bpf_rb_node is an opaque struct with the same size as struct rb_node. > It's not intended to be manipulated directly by any BPF program or bpf-rbtree > kernel code, but rather to be used as a struct rb_node by rbtree library > helpers. > > Here, the compiler complains that the less() callback taken by bpf_rbtree_add > is typed > > bool (*)(struct bpf_rb_node *, const struct bpf_rb_node *) > > while the actual rbtree lib helper rb_add's less() is typed > > bool (*)(struct rb_node *, const struct rb_node *) > > I'm not a C standard expert, but based on my googling, for C99 it's not valid > to cast a function pointer to anything aside from void* and its original type. > Furthermore, since struct bpf_rb_node an opaque bitfield and struct rb_node > has actual members, C99 standard 6.2.7 paragraph 1 states that they're not > compatible: > > Moreover, two structure, > union, or enumerated types declared in separate translation units are compatible if their > tags and members satisfy the following requirements: If one is declared with a tag, the > other shall be declared with the same tag. If both are complete types, then the following > additional requirements apply: there shall be a one-to-one correspondence between their > members such that each pair of corresponding members are declared with compatible > types, and such that if one member of a corresponding pair is declared with a name, the > other member is declared with the same name. For two structures, corresponding > members shall be declared in the same order > > I'm not sure how to proceed here. We could change bpf_rbtree_add's less() cb to I haven't looked at the series in question, but note that this compile time warning is meant to help us catch Control Flow Integrity runtime violations, which may result in a panic. > take two rb_node *'s, but then each such cb implementation would have to cast > its parameters before doing anything useful with them. Furthermore this would > require introducing non-opaque rb_node type into BPF programs. Other ideas seem > similarly hacky. > > Note that this flag was only recently introduced [0] and discussion in that > linked thread notes that ~1500 other places in the kernel raise same warning. > > > [0]: https://reviews.llvm.org/D134831 > > > > > 7 warnings generated. > > > > > > vim +1901 kernel/bpf/helpers.c > > > > 1896 > > 1897 void bpf_rbtree_add(struct bpf_rb_root *root, struct bpf_rb_node *node, > > 1898 bool (less)(struct bpf_rb_node *a, const struct bpf_rb_node *b)) > > 1899 { > > 1900 rb_add_cached((struct rb_node *)node, (struct rb_root_cached *)root, > >> 1901 (bool (*)(struct rb_node *, const struct rb_node *))less); > > 1902 } > > 1903 > > >
On Mon, Feb 13, 2023 at 12:49 PM Nick Desaulniers <ndesaulniers@google.com> wrote: > > On Mon, Feb 13, 2023 at 12:45 PM Dave Marchevsky > <davemarchevsky@meta.com> wrote: > > > > On 2/12/23 6:21 AM, kernel test robot wrote: > > > Hi Dave, > > > > > >>> kernel/bpf/helpers.c:1901:9: warning: cast from 'bool (*)(struct bpf_rb_node *, const struct bpf_rb_node *)' (aka '_Bool (*)(struct bpf_rb_node *, const struct bpf_rb_node *)') to 'bool (*)(struct rb_node *, const struct rb_node *)' (aka '_Bool (*)(struct rb_node *, const struct rb_node *)') converts to incompatible function type [-Wcast-function-type-strict] > > > (bool (*)(struct rb_node *, const struct rb_node *))less); > > > ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ > > > > This is the only new warning introduced by this series. A previous version had > > the same complaint by kernel test robot. > > > > struct bpf_rb_node is an opaque struct with the same size as struct rb_node. > > It's not intended to be manipulated directly by any BPF program or bpf-rbtree > > kernel code, but rather to be used as a struct rb_node by rbtree library > > helpers. > > > > Here, the compiler complains that the less() callback taken by bpf_rbtree_add > > is typed > > > > bool (*)(struct bpf_rb_node *, const struct bpf_rb_node *) > > > > while the actual rbtree lib helper rb_add's less() is typed > > > > bool (*)(struct rb_node *, const struct rb_node *) > > > > I'm not a C standard expert, but based on my googling, for C99 it's not valid > > to cast a function pointer to anything aside from void* and its original type. > > Furthermore, since struct bpf_rb_node an opaque bitfield and struct rb_node > > has actual members, C99 standard 6.2.7 paragraph 1 states that they're not > > compatible: > > > > Moreover, two structure, > > union, or enumerated types declared in separate translation units are compatible if their > > tags and members satisfy the following requirements: If one is declared with a tag, the > > other shall be declared with the same tag. If both are complete types, then the following > > additional requirements apply: there shall be a one-to-one correspondence between their > > members such that each pair of corresponding members are declared with compatible > > types, and such that if one member of a corresponding pair is declared with a name, the > > other member is declared with the same name. For two structures, corresponding > > members shall be declared in the same order > > > > I'm not sure how to proceed here. We could change bpf_rbtree_add's less() cb to > > I haven't looked at the series in question, but note that this compile > time warning is meant to help us catch Control Flow Integrity runtime > violations, which may result in a panic. It's a transition from kernel to bpf prog. If CFI trips on it it will trip on all transitions. All calls from kernel into bpf are more or less the same. Not sure what it means for other archs, but on x86 JIT emits 'endbr' insn to make IBT/CFI happy.
On Mon, Feb 13, 2023 at 2:17 PM Alexei Starovoitov <alexei.starovoitov@gmail.com> wrote: > > On Mon, Feb 13, 2023 at 12:49 PM Nick Desaulniers > <ndesaulniers@google.com> wrote: > > > > On Mon, Feb 13, 2023 at 12:45 PM Dave Marchevsky > > <davemarchevsky@meta.com> wrote: > > > > > > On 2/12/23 6:21 AM, kernel test robot wrote: > > > > Hi Dave, > > > > > > > >>> kernel/bpf/helpers.c:1901:9: warning: cast from 'bool (*)(struct bpf_rb_node *, const struct bpf_rb_node *)' (aka '_Bool (*)(struct bpf_rb_node *, const struct bpf_rb_node *)') to 'bool (*)(struct rb_node *, const struct rb_node *)' (aka '_Bool (*)(struct rb_node *, const struct rb_node *)') converts to incompatible function type [-Wcast-function-type-strict] > > > > (bool (*)(struct rb_node *, const struct rb_node *))less); > > > > ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ > > > > > > This is the only new warning introduced by this series. A previous version had > > > the same complaint by kernel test robot. > > > > > > struct bpf_rb_node is an opaque struct with the same size as struct rb_node. > > > It's not intended to be manipulated directly by any BPF program or bpf-rbtree > > > kernel code, but rather to be used as a struct rb_node by rbtree library > > > helpers. > > > > > > Here, the compiler complains that the less() callback taken by bpf_rbtree_add > > > is typed > > > > > > bool (*)(struct bpf_rb_node *, const struct bpf_rb_node *) > > > > > > while the actual rbtree lib helper rb_add's less() is typed > > > > > > bool (*)(struct rb_node *, const struct rb_node *) > > > > > > I'm not a C standard expert, but based on my googling, for C99 it's not valid > > > to cast a function pointer to anything aside from void* and its original type. > > > Furthermore, since struct bpf_rb_node an opaque bitfield and struct rb_node > > > has actual members, C99 standard 6.2.7 paragraph 1 states that they're not > > > compatible: > > > > > > Moreover, two structure, > > > union, or enumerated types declared in separate translation units are compatible if their > > > tags and members satisfy the following requirements: If one is declared with a tag, the > > > other shall be declared with the same tag. If both are complete types, then the following > > > additional requirements apply: there shall be a one-to-one correspondence between their > > > members such that each pair of corresponding members are declared with compatible > > > types, and such that if one member of a corresponding pair is declared with a name, the > > > other member is declared with the same name. For two structures, corresponding > > > members shall be declared in the same order > > > > > > I'm not sure how to proceed here. We could change bpf_rbtree_add's less() cb to > > > > I haven't looked at the series in question, but note that this compile > > time warning is meant to help us catch Control Flow Integrity runtime > > violations, which may result in a panic. > > It's a transition from kernel to bpf prog. > If CFI trips on it it will trip on all transitions. > All calls from kernel into bpf are more or less the same. > Not sure what it means for other archs, but on x86 JIT emits 'endbr' > insn to make IBT/CFI happy. Having said the above it's good that the warning was there. Just type casting the func is not correct. We should call bpf progs like this: -void bpf_rbtree_add(struct bpf_rb_root *root, struct bpf_rb_node *node, - bool (less)(struct bpf_rb_node *a, const struct bpf_rb_node *b)) -{ - rb_add_cached((struct rb_node *)node, (struct rb_root_cached *)root, - (bool (*)(struct rb_node *, const struct rb_node *))less); +void bpf_rbtree_add(struct bpf_rb_root *root, struct bpf_rb_node *node, bpf_callback_t less) +{ + struct rb_node **link = &((struct rb_root_cached *)root)->rb_root.rb_node; + struct rb_node *parent = NULL; + bool leftmost = true; + + while (*link) { + parent = *link; + if (less((uintptr_t)node, (uintptr_t)parent, 0, 0, 0)) { + link = &parent->rb_left; + } else { + link = &parent->rb_right; + leftmost = false; + } + } + + rb_link_node((struct rb_node *)node, parent, link); + rb_insert_color_cached((struct rb_node *)node, (struct rb_root_cached *)root, leftmost); Dave, please incorporate in the next respin. I only compile tested the above.
On Mon, Feb 13, 2023 at 2:17 PM Alexei Starovoitov <alexei.starovoitov@gmail.com> wrote: > > On Mon, Feb 13, 2023 at 12:49 PM Nick Desaulniers > <ndesaulniers@google.com> wrote: > > > > I haven't looked at the series in question, but note that this compile > > time warning is meant to help us catch Control Flow Integrity runtime > > violations, which may result in a panic. Here's the tracking issue for the other warnings of this type in the kernel, nearly all the warnings are in one driver: https://github.com/ClangBuiltLinux/linux/issues/1724 > It's a transition from kernel to bpf prog. > If CFI trips on it it will trip on all transitions. > All calls from kernel into bpf are more or less the same. > Not sure what it means for other archs, but on x86 JIT emits 'endbr' > insn to make IBT/CFI happy. While IBT allows indirect calls to any function that starts with endbr, CFI is more fine-grained and requires the function pointer type to match the function type, which further limits possible call targets. To actually enforce this, the compiler emits a type hash prefix for each function, and a check before each indirect call to ensure the call target has the expected prefix. The commit message here has an example of the code the compiler generates: https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/commit/?id=3c516f89e17e56b4738f05588e51267e295b5e63 As calling a JIT compiled function would obviously trip CFI, indirect call checking is currently disabled in BPF dispatcher functions (using the __nocfi attribute). However, BPF trampolines still have the same problem, I believe. I wouldn't mind coming up with a solution for CFI+BPF JIT compatibility, but I haven't had much time to look into this. Basically, in places where we currently emit an endbr instruction, we should also emit a type hash prefix. Generating type prefixes for functions called through a dispatcher shouldn't be that hard because the function type is always the same, but figuring out the correct type for indirect calls that don't go through a dispatcher might not be entirely trivial, although I'm sure the BPF verifier/compiler must have this information. FineIBT also complicates matters a bit here as the actual prefix format differs from the basic KCFI prefix. I'm not sure if Peter or Joao have had time to look at this, but I would be happy to hear any suggestions you might have. Sami
On Mon, Feb 13, 2023 at 03:31:21PM -0800, Sami Tolvanen wrote: > On Mon, Feb 13, 2023 at 2:17 PM Alexei Starovoitov > <alexei.starovoitov@gmail.com> wrote: > > > > On Mon, Feb 13, 2023 at 12:49 PM Nick Desaulniers > > <ndesaulniers@google.com> wrote: > > > > > > I haven't looked at the series in question, but note that this compile > > > time warning is meant to help us catch Control Flow Integrity runtime > > > violations, which may result in a panic. > > Here's the tracking issue for the other warnings of this type in the > kernel, nearly all the warnings are in one driver: > > https://github.com/ClangBuiltLinux/linux/issues/1724 > > > It's a transition from kernel to bpf prog. > > If CFI trips on it it will trip on all transitions. > > All calls from kernel into bpf are more or less the same. > > Not sure what it means for other archs, but on x86 JIT emits 'endbr' > > insn to make IBT/CFI happy. > > While IBT allows indirect calls to any function that starts with > endbr, CFI is more fine-grained and requires the function pointer type > to match the function type, which further limits possible call > targets. To actually enforce this, the compiler emits a type hash > prefix for each function, and a check before each indirect call to > ensure the call target has the expected prefix. The commit message > here has an example of the code the compiler generates: > > https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/commit/?id=3c516f89e17e56b4738f05588e51267e295b5e63 Another good commit to look at is: https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/commit/?id=931ab63664f02b17d2213ef36b83e1e50190a0aa That includes the FineIBT variant too. > As calling a JIT compiled function would obviously trip CFI, indirect > call checking is currently disabled in BPF dispatcher functions (using > the __nocfi attribute). However, BPF trampolines still have the same > problem, I believe. I wouldn't mind coming up with a solution for > CFI+BPF JIT compatibility, but I haven't had much time to look into > this. Basically, in places where we currently emit an endbr > instruction, we should also emit a type hash prefix. > > Generating type prefixes for functions called through a dispatcher > shouldn't be that hard because the function type is always the same, > but figuring out the correct type for indirect calls that don't go > through a dispatcher might not be entirely trivial, although I'm sure > the BPF verifier/compiler must have this information. FineIBT also > complicates matters a bit here as the actual prefix format differs > from the basic KCFI prefix. > > I'm not sure if Peter or Joao have had time to look at this, but I > would be happy to hear any suggestions you might have. I've not had time to look at this -- but afair BPF will only emit an indirect jump (tail-call even, irrc), it doesn't do indirect calls otherwise (this is also the only place we have RETPOLINE magic in the JIT). (ooh, also dispatcher thing) This generates an unadorned indirect jump, that is, it doesn't have any kCFI magic included, eg. traditional calling convention. The other case, which you allude to I think, is control transfer to the JIT'ed code which is currently __nocfi annotated. I've only briefly thought about how to change this, but basically it would entail the JIT emitting the correct prefix bytes and setting the entry point at +16. Given the JIT will only run after we've selected kCFI/FineIBT it knows which form to pick from and can emit the right prefix. Then if we remove the __nocfi annotation from the call into JIT'ed code, everything should work. None of this should be exceptionally hard, but I've not had time to actually do much about it yet.
On Tue, Feb 14, 2023 at 7:36 AM Peter Zijlstra <peterz@infradead.org> wrote: > > The other case, which you allude to I think, is control transfer to the > JIT'ed code which is currently __nocfi annotated. I've only briefly > thought about how to change this, but basically it would entail the JIT > emitting the correct prefix bytes and setting the entry point at +16. > > Given the JIT will only run after we've selected kCFI/FineIBT it knows > which form to pick from and can emit the right prefix. Then if we remove > the __nocfi annotation from the call into JIT'ed code, everything should > work. > > None of this should be exceptionally hard, but I've not had time to > actually do much about it yet. The dispatcher path shouldn't be terribly hard to fix, but when I looked into this briefly half a year ago and ran BPF self-tests with CFI enabled, I found a few more places that indirectly call jitted code (or trampolines) using a different function pointer type: https://github.com/ClangBuiltLinux/linux/issues/1727 For some of these, determining the correct type didn't look all that simple, but then again, I'm not super familiar with BPF internals. Sami
On Tue, Feb 14, 2023 at 2:00 PM Sami Tolvanen <samitolvanen@google.com> wrote: > > On Tue, Feb 14, 2023 at 7:36 AM Peter Zijlstra <peterz@infradead.org> wrote: > > > > The other case, which you allude to I think, is control transfer to the > > JIT'ed code which is currently __nocfi annotated. I've only briefly > > thought about how to change this, but basically it would entail the JIT > > emitting the correct prefix bytes and setting the entry point at +16. > > > > Given the JIT will only run after we've selected kCFI/FineIBT it knows > > which form to pick from and can emit the right prefix. Then if we remove > > the __nocfi annotation from the call into JIT'ed code, everything should > > work. > > > > None of this should be exceptionally hard, but I've not had time to > > actually do much about it yet. > > The dispatcher path shouldn't be terribly hard to fix, but when I > looked into this briefly half a year ago and ran BPF self-tests with > CFI enabled, I found a few more places that indirectly call jitted > code (or trampolines) using a different function pointer type: > > https://github.com/ClangBuiltLinux/linux/issues/1727 > > For some of these, determining the correct type didn't look all that > simple, but then again, I'm not super familiar with BPF internals. How is 'kcfi' 32-bit hash computed? Some kind of hash of type id-s? Here we'll be dealing with bpf side callbacks with its own types that are called from the kernel side with its own types. I don't quite see how clang can come up with the same hashing algorithm for both. Also what to do with the situation when kernel is compiled with GCC while bpf progs are with clang? and the other way around ? gcc-bpf can compile all of selftests/bpf, but not yet run them. kcfi is addressing the case when endbr/ibt is not supported by cpu or some other reason? btw even for bpf_tail_call we're using direct call most of the time. Even when bpf progs look like a callback through an indirect call we are using direct call whenever possible.
On Tue, Feb 14, 2023 at 03:59:57PM -0800, Alexei Starovoitov wrote: > How is 'kcfi' 32-bit hash computed? > Some kind of hash of type id-s? Yes. Specifically I think a hash of the C++ name mangled function signature. (which is giving pain with eg. Rust because then the C++ mangling isn't specific enough or somesuch, I'm sure Sami can easily find it if you want to know more) > Here we'll be dealing with bpf side callbacks with its own types > that are called from the kernel side with its own types. As long as there's a kernel side function declaration (definition not required) the compiler will generate you a usable __kcfi_typeid_##name symbol that contains the hash. If it is a pure BPF internal (C never sees either the declaration of definition) then it doesn't matter and you can make up your own scheme as long as caller and callee agree on the magic number. > Also what to do with the situation when kernel is compiled with GCC > while bpf progs are with clang? and the other way around ? > gcc-bpf can compile all of selftests/bpf, but not yet run them. As of yet GCC doesn't support kCFI, so mixing is not possible at present. kCFI fundamentally changes the C ABI in incompatible ways. Ideally the GCC implementation of kCFI (when it happens) will use the same hashing scheme as LLVM so that mutual compatibility is possible. > kcfi is addressing the case when endbr/ibt is not supported by cpu > or some other reason? kCFI/FineIBT are supplementary to regular IBT. kCFI works regardless of hardware support, but the same infrastructure is employed with FineIBT to provide more fine-gained target control. Specifically, with bare IBT all that is required is the indirect target be an ENDBR instruction, *any* ENDBR instruction. The kCFI/FineIBT improvement over that is that caller and callee need to agree on the hash, thereby further limiting which functions can be called.
On Wed, Feb 15, 2023 at 1:44 AM Peter Zijlstra <peterz@infradead.org> wrote: > > On Tue, Feb 14, 2023 at 03:59:57PM -0800, Alexei Starovoitov wrote: > > How is 'kcfi' 32-bit hash computed? > > Some kind of hash of type id-s? > > Yes. Specifically I think a hash of the C++ name mangled function > signature. (which is giving pain with eg. Rust because then the C++ > mangling isn't specific enough or somesuch, I'm sure Sami can easily > find it if you want to know more) The Rust pain is mostly about type system differences when it comes to integer types, but we're working on fixing that. > > Also what to do with the situation when kernel is compiled with GCC > > while bpf progs are with clang? and the other way around ? > > gcc-bpf can compile all of selftests/bpf, but not yet run them. > > As of yet GCC doesn't support kCFI, so mixing is not possible at > present. kCFI fundamentally changes the C ABI in incompatible ways. When it comes to the BPF programs themselves, it shouldn't matter which compiler you use to compile them as the BPF back-end doesn't emit CFI instrumentation. I'm also fairly sure that the function type in the BPF C program doesn't necessarily have to exactly match the function pointer type used to call the JIT compiled version of that function in the kernel, and the latter one is what actually matters. Sami
diff --git a/kernel/bpf/helpers.c b/kernel/bpf/helpers.c index 192184b5156e..cea42b31e9b8 100644 --- a/kernel/bpf/helpers.c +++ b/kernel/bpf/helpers.c @@ -1884,6 +1884,30 @@ __bpf_kfunc struct bpf_list_node *bpf_list_pop_back(struct bpf_list_head *head) return __bpf_list_del(head, true); } +struct bpf_rb_node *bpf_rbtree_remove(struct bpf_rb_root *root, struct bpf_rb_node *node) +{ + struct rb_root_cached *r = (struct rb_root_cached *)root; + struct rb_node *n = (struct rb_node *)node; + + rb_erase_cached(n, r); + RB_CLEAR_NODE(n); + return (struct bpf_rb_node *)n; +} + +void bpf_rbtree_add(struct bpf_rb_root *root, struct bpf_rb_node *node, + bool (less)(struct bpf_rb_node *a, const struct bpf_rb_node *b)) +{ + rb_add_cached((struct rb_node *)node, (struct rb_root_cached *)root, + (bool (*)(struct rb_node *, const struct rb_node *))less); +} + +struct bpf_rb_node *bpf_rbtree_first(struct bpf_rb_root *root) +{ + struct rb_root_cached *r = (struct rb_root_cached *)root; + + return (struct bpf_rb_node *)rb_first_cached(r); +} + /** * bpf_task_acquire - Acquire a reference to a task. A task acquired by this * kfunc which is not stored in a map as a kptr, must be released by calling @@ -2108,6 +2132,10 @@ BTF_ID_FLAGS(func, bpf_task_acquire, KF_ACQUIRE | KF_TRUSTED_ARGS) BTF_ID_FLAGS(func, bpf_task_acquire_not_zero, KF_ACQUIRE | KF_RCU | KF_RET_NULL) BTF_ID_FLAGS(func, bpf_task_kptr_get, KF_ACQUIRE | KF_KPTR_GET | KF_RET_NULL) BTF_ID_FLAGS(func, bpf_task_release, KF_RELEASE) +BTF_ID_FLAGS(func, bpf_rbtree_remove, KF_ACQUIRE) +BTF_ID_FLAGS(func, bpf_rbtree_add) +BTF_ID_FLAGS(func, bpf_rbtree_first, KF_RET_NULL) + #ifdef CONFIG_CGROUPS BTF_ID_FLAGS(func, bpf_cgroup_acquire, KF_ACQUIRE | KF_TRUSTED_ARGS) BTF_ID_FLAGS(func, bpf_cgroup_kptr_get, KF_ACQUIRE | KF_KPTR_GET | KF_RET_NULL) diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c index 4fd098851f43..e6d2a599c7d1 100644 --- a/kernel/bpf/verifier.c +++ b/kernel/bpf/verifier.c @@ -8638,6 +8638,8 @@ BTF_ID_LIST(kf_arg_btf_ids) BTF_ID(struct, bpf_dynptr_kern) BTF_ID(struct, bpf_list_head) BTF_ID(struct, bpf_list_node) +BTF_ID(struct, bpf_rb_root) +BTF_ID(struct, bpf_rb_node) static bool __is_kfunc_ptr_arg_type(const struct btf *btf, const struct btf_param *arg, int type) @@ -8743,6 +8745,9 @@ enum special_kfunc_type { KF_bpf_rdonly_cast, KF_bpf_rcu_read_lock, KF_bpf_rcu_read_unlock, + KF_bpf_rbtree_remove, + KF_bpf_rbtree_add, + KF_bpf_rbtree_first, }; BTF_SET_START(special_kfunc_set) @@ -8754,6 +8759,9 @@ BTF_ID(func, bpf_list_pop_front) BTF_ID(func, bpf_list_pop_back) BTF_ID(func, bpf_cast_to_kern_ctx) BTF_ID(func, bpf_rdonly_cast) +BTF_ID(func, bpf_rbtree_remove) +BTF_ID(func, bpf_rbtree_add) +BTF_ID(func, bpf_rbtree_first) BTF_SET_END(special_kfunc_set) BTF_ID_LIST(special_kfunc_list) @@ -8767,6 +8775,9 @@ BTF_ID(func, bpf_cast_to_kern_ctx) BTF_ID(func, bpf_rdonly_cast) BTF_ID(func, bpf_rcu_read_lock) BTF_ID(func, bpf_rcu_read_unlock) +BTF_ID(func, bpf_rbtree_remove) +BTF_ID(func, bpf_rbtree_add) +BTF_ID(func, bpf_rbtree_first) static bool is_kfunc_bpf_rcu_read_lock(struct bpf_kfunc_call_arg_meta *meta) { @@ -9556,7 +9567,8 @@ static int check_kfunc_call(struct bpf_verifier_env *env, struct bpf_insn *insn, } if (meta.func_id == special_kfunc_list[KF_bpf_list_push_front] || - meta.func_id == special_kfunc_list[KF_bpf_list_push_back]) { + meta.func_id == special_kfunc_list[KF_bpf_list_push_back] || + meta.func_id == special_kfunc_list[KF_bpf_rbtree_add]) { release_ref_obj_id = regs[BPF_REG_2].ref_obj_id; err = ref_convert_owning_non_owning(env, release_ref_obj_id); if (err) {
This patch adds implementations of bpf_rbtree_{add,remove,first} and teaches verifier about their BTF_IDs as well as those of bpf_rb_{root,node}. All three kfuncs have some nonstandard component to their verification that needs to be addressed in future patches before programs can properly use them: * bpf_rbtree_add: Takes 'less' callback, need to verify it * bpf_rbtree_first: Returns ptr_to_node_type(off=rb_node_off) instead of ptr_to_rb_node(off=0). Return value ref is non-owning. * bpf_rbtree_remove: Returns ptr_to_node_type(off=rb_node_off) instead of ptr_to_rb_node(off=0). 2nd arg (node) is a non-owning reference. Signed-off-by: Dave Marchevsky <davemarchevsky@fb.com> --- kernel/bpf/helpers.c | 28 ++++++++++++++++++++++++++++ kernel/bpf/verifier.c | 14 +++++++++++++- 2 files changed, 41 insertions(+), 1 deletion(-)