Re: [PATCH v5 bpf-next 3/9] bpf: Add bpf_rbtree_{add,remove,first} kfuncs

Re: [PATCH v5 bpf-next 3/9] bpf: Add bpf_rbtree_{add,remove,first} kfuncs

[kernel test robot]

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	

-- 
0-DAY CI Kernel Test Service
https://github.com/intel/lkp-tests

Re: [PATCH v5 bpf-next 3/9] bpf: Add bpf_rbtree_{add,remove,first} kfuncs

[Dave Marchevsky]

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	
> 

Re: [PATCH v5 bpf-next 3/9] bpf: Add bpf_rbtree_{add,remove,first} kfuncs

[Nick Desaulniers]

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
> >
>


-- 
Thanks,
~Nick Desaulniers

Re: [PATCH v5 bpf-next 3/9] bpf: Add bpf_rbtree_{add,remove,first} kfuncs

[Alexei Starovoitov]

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.

Re: [PATCH v5 bpf-next 3/9] bpf: Add bpf_rbtree_{add,remove,first} kfuncs

[Alexei Starovoitov]

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.

Re: [PATCH v5 bpf-next 3/9] bpf: Add bpf_rbtree_{add,remove,first} kfuncs

[Sami Tolvanen]

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

Re: [PATCH v5 bpf-next 3/9] bpf: Add bpf_rbtree_{add,remove,first} kfuncs

[Peter Zijlstra]

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.

Re: [PATCH v5 bpf-next 3/9] bpf: Add bpf_rbtree_{add,remove,first} kfuncs

[Sami Tolvanen]

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

Re: [PATCH v5 bpf-next 3/9] bpf: Add bpf_rbtree_{add,remove,first} kfuncs

[Alexei Starovoitov]

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.

Re: [PATCH v5 bpf-next 3/9] bpf: Add bpf_rbtree_{add,remove,first} kfuncs

[Peter Zijlstra]

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.

Re: [PATCH v5 bpf-next 3/9] bpf: Add bpf_rbtree_{add,remove,first} kfuncs

[Sami Tolvanen]

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