[PATCH bpf-next 0/6] bpf: Introduce global functions

[PATCH bpf-next 0/6] bpf: Introduce global functions

[Alexei Starovoitov]

Introduce static vs global functions and function by function verification.
This is another step toward dynamic re-linking (or replacement) of global
functions. See patch 3 for details. The rest are supporting patches.

Alexei Starovoitov (6):
  libbpf: Sanitize BTF_KIND_FUNC linkage
  libbpf: Collect static vs global info about functions
  bpf: Introduce function-by-function verification
  selftests/bpf: Add fexit-to-skb test for global funcs
  selftests/bpf: Add a test for a large global function
  selftests/bpf: Modify a test to check global functions

 include/linux/bpf.h                           |   7 +-
 include/linux/bpf_verifier.h                  |   7 +-
 include/uapi/linux/btf.h                      |   6 +
 kernel/bpf/btf.c                              | 147 ++++++++---
 kernel/bpf/verifier.c                         | 228 ++++++++++++++----
 tools/include/uapi/linux/btf.h                |   6 +
 tools/lib/bpf/libbpf.c                        | 150 +++++++++++-
 .../bpf/prog_tests/bpf_verif_scale.c          |   2 +
 .../selftests/bpf/prog_tests/fexit_bpf2bpf.c  |   1 +
 .../selftests/bpf/progs/fexit_bpf2bpf.c       |  15 ++
 tools/testing/selftests/bpf/progs/pyperf.h    |   9 +-
 .../selftests/bpf/progs/pyperf_global.c       |   5 +
 .../selftests/bpf/progs/test_pkt_access.c     |  28 +++
 .../selftests/bpf/progs/test_xdp_noinline.c   |   4 +-
 14 files changed, 528 insertions(+), 87 deletions(-)
 create mode 100644 tools/testing/selftests/bpf/progs/pyperf_global.c

-- 
2.23.0

[PATCH bpf-next 1/6] libbpf: Sanitize BTF_KIND_FUNC linkage

[Alexei Starovoitov]

In case kernel doesn't support static/global/extern liknage of BTF_KIND_FUNC
sanitize BTF produced by llvm.

Signed-off-by: Alexei Starovoitov <ast@kernel.org>
---
 tools/include/uapi/linux/btf.h |  6 ++++++
 tools/lib/bpf/libbpf.c         | 35 +++++++++++++++++++++++++++++++++-
 2 files changed, 40 insertions(+), 1 deletion(-)

diff --git a/tools/include/uapi/linux/btf.h b/tools/include/uapi/linux/btf.h
index 1a2898c482ee..5a667107ad2c 100644
--- a/tools/include/uapi/linux/btf.h
+++ b/tools/include/uapi/linux/btf.h
@@ -146,6 +146,12 @@ enum {
 	BTF_VAR_GLOBAL_EXTERN = 2,
 };
 
+enum btf_func_linkage {
+	BTF_FUNC_STATIC = 0,
+	BTF_FUNC_GLOBAL = 1,
+	BTF_FUNC_EXTERN = 2,
+};
+
 /* BTF_KIND_VAR is followed by a single "struct btf_var" to describe
  * additional information related to the variable such as its linkage.
  */
diff --git a/tools/lib/bpf/libbpf.c b/tools/lib/bpf/libbpf.c
index 7513165b104f..f72b3ed6c34b 100644
--- a/tools/lib/bpf/libbpf.c
+++ b/tools/lib/bpf/libbpf.c
@@ -166,6 +166,8 @@ struct bpf_capabilities {
 	__u32 btf_datasec:1;
 	/* BPF_F_MMAPABLE is supported for arrays */
 	__u32 array_mmap:1;
+	/* static/global/extern is supported for BTF_KIND_FUNC */
+	__u32 btf_func_linkage:1;
 };
 
 enum reloc_type {
@@ -1817,13 +1819,14 @@ static bool section_have_execinstr(struct bpf_object *obj, int idx)
 
 static void bpf_object__sanitize_btf(struct bpf_object *obj)
 {
+	bool has_func_linkage = obj->caps.btf_func_linkage;
 	bool has_datasec = obj->caps.btf_datasec;
 	bool has_func = obj->caps.btf_func;
 	struct btf *btf = obj->btf;
 	struct btf_type *t;
 	int i, j, vlen;
 
-	if (!obj->btf || (has_func && has_datasec))
+	if (!obj->btf || (has_func && has_datasec && has_func_linkage))
 		return;
 
 	for (i = 1; i <= btf__get_nr_types(btf); i++) {
@@ -1871,6 +1874,9 @@ static void bpf_object__sanitize_btf(struct bpf_object *obj)
 		} else if (!has_func && btf_is_func(t)) {
 			/* replace FUNC with TYPEDEF */
 			t->info = BTF_INFO_ENC(BTF_KIND_TYPEDEF, 0, 0);
+		} else if (!has_func_linkage && btf_is_func(t)) {
+			/* replace BTF_FUNC_GLOBAL with BTF_FUNC_STATIC */
+			t->info = BTF_INFO_ENC(BTF_KIND_FUNC, 0, 0);
 		}
 	}
 }
@@ -2804,6 +2810,32 @@ static int bpf_object__probe_btf_func(struct bpf_object *obj)
 	return 0;
 }
 
+static int bpf_object__probe_btf_func_linkage(struct bpf_object *obj)
+{
+	static const char strs[] = "\0int\0x\0a";
+	/* static void x(int a) {} */
+	__u32 types[] = {
+		/* int */
+		BTF_TYPE_INT_ENC(1, BTF_INT_SIGNED, 0, 32, 4),  /* [1] */
+		/* FUNC_PROTO */                                /* [2] */
+		BTF_TYPE_ENC(0, BTF_INFO_ENC(BTF_KIND_FUNC_PROTO, 0, 1), 0),
+		BTF_PARAM_ENC(7, 1),
+		/* FUNC x BTF_FUNC_GLOBAL */                    /* [3] */
+		BTF_TYPE_ENC(5, BTF_INFO_ENC(BTF_KIND_FUNC, 0, 1), 2),
+	};
+	int btf_fd;
+
+	btf_fd = libbpf__load_raw_btf((char *)types, sizeof(types),
+				      strs, sizeof(strs));
+	if (btf_fd >= 0) {
+		obj->caps.btf_func_linkage = 1;
+		close(btf_fd);
+		return 1;
+	}
+
+	return 0;
+}
+
 static int bpf_object__probe_btf_datasec(struct bpf_object *obj)
 {
 	static const char strs[] = "\0x\0.data";
@@ -2859,6 +2891,7 @@ bpf_object__probe_caps(struct bpf_object *obj)
 		bpf_object__probe_name,
 		bpf_object__probe_global_data,
 		bpf_object__probe_btf_func,
+		bpf_object__probe_btf_func_linkage,
 		bpf_object__probe_btf_datasec,
 		bpf_object__probe_array_mmap,
 	};
-- 
2.23.0

Re: [PATCH bpf-next 1/6] libbpf: Sanitize BTF_KIND_FUNC linkage

[Song Liu]

> On Jan 7, 2020, at 11:25 PM, Alexei Starovoitov <ast@kernel.org> wrote:
> 
> In case kernel doesn't support static/global/extern liknage of BTF_KIND_FUNC
                                                     ^^^ linkage
> sanitize BTF produced by llvm.
> 
> Signed-off-by: Alexei Starovoitov <ast@kernel.org>

Acked-by: Song Liu <songliubraving@fb.com>

Re: [PATCH bpf-next 1/6] libbpf: Sanitize BTF_KIND_FUNC linkage

[Yonghong Song]

On 1/7/20 11:25 PM, Alexei Starovoitov wrote:
> In case kernel doesn't support static/global/extern liknage of BTF_KIND_FUNC
> sanitize BTF produced by llvm.
> 
> Signed-off-by: Alexei Starovoitov <ast@kernel.org>
> ---
>   tools/include/uapi/linux/btf.h |  6 ++++++
>   tools/lib/bpf/libbpf.c         | 35 +++++++++++++++++++++++++++++++++-
>   2 files changed, 40 insertions(+), 1 deletion(-)
> 
> diff --git a/tools/include/uapi/linux/btf.h b/tools/include/uapi/linux/btf.h
> index 1a2898c482ee..5a667107ad2c 100644
> --- a/tools/include/uapi/linux/btf.h
> +++ b/tools/include/uapi/linux/btf.h
> @@ -146,6 +146,12 @@ enum {
>   	BTF_VAR_GLOBAL_EXTERN = 2,
>   };
>   
> +enum btf_func_linkage {
> +	BTF_FUNC_STATIC = 0,
> +	BTF_FUNC_GLOBAL = 1,
> +	BTF_FUNC_EXTERN = 2,
> +};
> +
>   /* BTF_KIND_VAR is followed by a single "struct btf_var" to describe
>    * additional information related to the variable such as its linkage.
>    */
> diff --git a/tools/lib/bpf/libbpf.c b/tools/lib/bpf/libbpf.c
> index 7513165b104f..f72b3ed6c34b 100644
> --- a/tools/lib/bpf/libbpf.c
> +++ b/tools/lib/bpf/libbpf.c
> @@ -166,6 +166,8 @@ struct bpf_capabilities {
>   	__u32 btf_datasec:1;
>   	/* BPF_F_MMAPABLE is supported for arrays */
>   	__u32 array_mmap:1;
> +	/* static/global/extern is supported for BTF_KIND_FUNC */
> +	__u32 btf_func_linkage:1;
>   };
>   
>   enum reloc_type {
> @@ -1817,13 +1819,14 @@ static bool section_have_execinstr(struct bpf_object *obj, int idx)
>   
>   static void bpf_object__sanitize_btf(struct bpf_object *obj)
>   {
> +	bool has_func_linkage = obj->caps.btf_func_linkage;
>   	bool has_datasec = obj->caps.btf_datasec;
>   	bool has_func = obj->caps.btf_func;
>   	struct btf *btf = obj->btf;
>   	struct btf_type *t;
>   	int i, j, vlen;
>   
> -	if (!obj->btf || (has_func && has_datasec))
> +	if (!obj->btf || (has_func && has_datasec && has_func_linkage))
>   		return;
>   
>   	for (i = 1; i <= btf__get_nr_types(btf); i++) {
> @@ -1871,6 +1874,9 @@ static void bpf_object__sanitize_btf(struct bpf_object *obj)
>   		} else if (!has_func && btf_is_func(t)) {
>   			/* replace FUNC with TYPEDEF */
>   			t->info = BTF_INFO_ENC(BTF_KIND_TYPEDEF, 0, 0);
> +		} else if (!has_func_linkage && btf_is_func(t)) {
> +			/* replace BTF_FUNC_GLOBAL with BTF_FUNC_STATIC */
> +			t->info = BTF_INFO_ENC(BTF_KIND_FUNC, 0, 0);

The comment says we only sanitize BTF_FUNC_GLOBAL here.
Actually, it also sanitize BTF_FUNC_EXTERN.

Currently, in kernel/bpf/btf.c, we have
static int btf_check_all_types(struct btf_verifier_env *env)
{
		...
                 if (btf_type_is_func(t)) {
                         err = btf_func_check(env, t);
                         if (err)
                                 return err;
                 }
		...
}

btf_func_check() will ensure func btf_type->type is a func_proto
and all arguments of func_proto has a name except void which is
considered as varg.

For extern function, the argument name is lost in llvm/clang.

-bash-4.4$ cat test.c 

extern int foo(int a);
int test() { return foo(5); }
-bash-4.4$
-bash-4.4$ clang -target bpf -O2 -g -S -emit-llvm test.c

!2 = !{}
!4 = !DISubprogram(name: "foo", scope: !1, file: !1, line: 1, type: !5, 
flags: DIFlagPrototyped, spFlags: DISPFlagOptimized, retainedNodes: !2)
!5 = !DISubroutineType(types: !6)
!6 = !{!7, !7}
!7 = !DIBasicType(name: "int", size: 32, encoding: DW_ATE_signed)

To avoid kernel complaints, we need to sanitize in a different way.
For example extern BTF_KIND_FUNC could be rewritten to a
BTF_KIND_PTR to void.

>   		}
>   	}
>   }
> @@ -2804,6 +2810,32 @@ static int bpf_object__probe_btf_func(struct bpf_object *obj)
>   	return 0;
>   }
>   
> +static int bpf_object__probe_btf_func_linkage(struct bpf_object *obj)
> +{
> +	static const char strs[] = "\0int\0x\0a";
> +	/* static void x(int a) {} */
> +	__u32 types[] = {
> +		/* int */
> +		BTF_TYPE_INT_ENC(1, BTF_INT_SIGNED, 0, 32, 4),  /* [1] */
> +		/* FUNC_PROTO */                                /* [2] */
> +		BTF_TYPE_ENC(0, BTF_INFO_ENC(BTF_KIND_FUNC_PROTO, 0, 1), 0),
> +		BTF_PARAM_ENC(7, 1),
> +		/* FUNC x BTF_FUNC_GLOBAL */                    /* [3] */
> +		BTF_TYPE_ENC(5, BTF_INFO_ENC(BTF_KIND_FUNC, 0, 1), 2),
> +	};
> +	int btf_fd;
> +
> +	btf_fd = libbpf__load_raw_btf((char *)types, sizeof(types),
> +				      strs, sizeof(strs));
> +	if (btf_fd >= 0) {
> +		obj->caps.btf_func_linkage = 1;
> +		close(btf_fd);
> +		return 1;
> +	}
> +
> +	return 0;
> +}
> +
>   static int bpf_object__probe_btf_datasec(struct bpf_object *obj)
>   {
>   	static const char strs[] = "\0x\0.data";
> @@ -2859,6 +2891,7 @@ bpf_object__probe_caps(struct bpf_object *obj)
>   		bpf_object__probe_name,
>   		bpf_object__probe_global_data,
>   		bpf_object__probe_btf_func,
> +		bpf_object__probe_btf_func_linkage,
>   		bpf_object__probe_btf_datasec,
>   		bpf_object__probe_array_mmap,
>   	};
> 

Re: [PATCH bpf-next 1/6] libbpf: Sanitize BTF_KIND_FUNC linkage

[Alexei Starovoitov]

On Wed, Jan 08, 2020 at 06:57:18PM +0000, Yonghong Song wrote:
> 
> 
> On 1/7/20 11:25 PM, Alexei Starovoitov wrote:
> > In case kernel doesn't support static/global/extern liknage of BTF_KIND_FUNC
> > sanitize BTF produced by llvm.
> > 
> > Signed-off-by: Alexei Starovoitov <ast@kernel.org>
> > ---
> >   tools/include/uapi/linux/btf.h |  6 ++++++
> >   tools/lib/bpf/libbpf.c         | 35 +++++++++++++++++++++++++++++++++-
> >   2 files changed, 40 insertions(+), 1 deletion(-)
> > 
> > diff --git a/tools/include/uapi/linux/btf.h b/tools/include/uapi/linux/btf.h
> > index 1a2898c482ee..5a667107ad2c 100644
> > --- a/tools/include/uapi/linux/btf.h
> > +++ b/tools/include/uapi/linux/btf.h
> > @@ -146,6 +146,12 @@ enum {
> >   	BTF_VAR_GLOBAL_EXTERN = 2,
> >   };
> >   
> > +enum btf_func_linkage {
> > +	BTF_FUNC_STATIC = 0,
> > +	BTF_FUNC_GLOBAL = 1,
> > +	BTF_FUNC_EXTERN = 2,
> > +};
> > +
> >   /* BTF_KIND_VAR is followed by a single "struct btf_var" to describe
> >    * additional information related to the variable such as its linkage.
> >    */
> > diff --git a/tools/lib/bpf/libbpf.c b/tools/lib/bpf/libbpf.c
> > index 7513165b104f..f72b3ed6c34b 100644
> > --- a/tools/lib/bpf/libbpf.c
> > +++ b/tools/lib/bpf/libbpf.c
> > @@ -166,6 +166,8 @@ struct bpf_capabilities {
> >   	__u32 btf_datasec:1;
> >   	/* BPF_F_MMAPABLE is supported for arrays */
> >   	__u32 array_mmap:1;
> > +	/* static/global/extern is supported for BTF_KIND_FUNC */
> > +	__u32 btf_func_linkage:1;
> >   };
> >   
> >   enum reloc_type {
> > @@ -1817,13 +1819,14 @@ static bool section_have_execinstr(struct bpf_object *obj, int idx)
> >   
> >   static void bpf_object__sanitize_btf(struct bpf_object *obj)
> >   {
> > +	bool has_func_linkage = obj->caps.btf_func_linkage;
> >   	bool has_datasec = obj->caps.btf_datasec;
> >   	bool has_func = obj->caps.btf_func;
> >   	struct btf *btf = obj->btf;
> >   	struct btf_type *t;
> >   	int i, j, vlen;
> >   
> > -	if (!obj->btf || (has_func && has_datasec))
> > +	if (!obj->btf || (has_func && has_datasec && has_func_linkage))
> >   		return;
> >   
> >   	for (i = 1; i <= btf__get_nr_types(btf); i++) {
> > @@ -1871,6 +1874,9 @@ static void bpf_object__sanitize_btf(struct bpf_object *obj)
> >   		} else if (!has_func && btf_is_func(t)) {
> >   			/* replace FUNC with TYPEDEF */
> >   			t->info = BTF_INFO_ENC(BTF_KIND_TYPEDEF, 0, 0);
> > +		} else if (!has_func_linkage && btf_is_func(t)) {
> > +			/* replace BTF_FUNC_GLOBAL with BTF_FUNC_STATIC */
> > +			t->info = BTF_INFO_ENC(BTF_KIND_FUNC, 0, 0);
> 
> The comment says we only sanitize BTF_FUNC_GLOBAL here.
> Actually, it also sanitize BTF_FUNC_EXTERN.
> 
> Currently, in kernel/bpf/btf.c, we have
> static int btf_check_all_types(struct btf_verifier_env *env)
> {
> 		...
>                  if (btf_type_is_func(t)) {
>                          err = btf_func_check(env, t);
>                          if (err)
>                                  return err;
>                  }
> 		...
> }
> 
> btf_func_check() will ensure func btf_type->type is a func_proto
> and all arguments of func_proto has a name except void which is
> considered as varg.
> 
> For extern function, the argument name is lost in llvm/clang.
> 
> -bash-4.4$ cat test.c 
> 
> extern int foo(int a);
> int test() { return foo(5); }
> -bash-4.4$
> -bash-4.4$ clang -target bpf -O2 -g -S -emit-llvm test.c
> 
> !2 = !{}
> !4 = !DISubprogram(name: "foo", scope: !1, file: !1, line: 1, type: !5, 
> flags: DIFlagPrototyped, spFlags: DISPFlagOptimized, retainedNodes: !2)
> !5 = !DISubroutineType(types: !6)
> !6 = !{!7, !7}
> !7 = !DIBasicType(name: "int", size: 32, encoding: DW_ATE_signed)
> 
> To avoid kernel complaints, we need to sanitize in a different way.
> For example extern BTF_KIND_FUNC could be rewritten to a
> BTF_KIND_PTR to void.

Good point. I'll reword the comment and rename the test to btf_func_global,
so it probes kernel for KIND_GLOBAL only and santizes only that bit.
KIND_EXTERN sanitization is to be done later. Separate libbpf and kernel patches.

[PATCH bpf-next 2/6] libbpf: Collect static vs global info about functions

[Alexei Starovoitov]

Collect static vs global information about BPF functions from ELF file and
improve BTF with this additional info if llvm is too old and doesn't emit it on
its own.

Signed-off-by: Alexei Starovoitov <ast@kernel.org>
---
 tools/lib/bpf/libbpf.c | 115 +++++++++++++++++++++++++++++++++++++++--
 1 file changed, 111 insertions(+), 4 deletions(-)

diff --git a/tools/lib/bpf/libbpf.c b/tools/lib/bpf/libbpf.c
index f72b3ed6c34b..2a4417d03ee2 100644
--- a/tools/lib/bpf/libbpf.c
+++ b/tools/lib/bpf/libbpf.c
@@ -294,6 +294,12 @@ struct extern_desc {
 
 static LIST_HEAD(bpf_objects_list);
 
+struct func_desc {
+	int insn_idx;
+	int sec_idx;
+	enum btf_func_linkage linkage;
+};
+
 struct bpf_object {
 	char name[BPF_OBJ_NAME_LEN];
 	char license[64];
@@ -304,6 +310,8 @@ struct bpf_object {
 	struct bpf_map *maps;
 	size_t nr_maps;
 	size_t maps_cap;
+	struct func_desc *funcs;
+	int nr_funcs;
 
 	char *kconfig;
 	struct extern_desc *externs;
@@ -313,6 +321,7 @@ struct bpf_object {
 	bool loaded;
 	bool has_pseudo_calls;
 	bool relaxed_core_relocs;
+	bool llvm_emits_func_linkage;
 
 	/*
 	 * Information when doing elf related work. Only valid if fd
@@ -526,10 +535,10 @@ bpf_object__init_prog_names(struct bpf_object *obj)
 				continue;
 			if (GELF_ST_BIND(sym.st_info) != STB_GLOBAL)
 				continue;
-
 			name = elf_strptr(obj->efile.elf,
 					  obj->efile.strtabidx,
 					  sym.st_name);
+
 			if (!name) {
 				pr_warn("failed to get sym name string for prog %s\n",
 					prog->section_name);
@@ -2232,6 +2241,34 @@ static int cmp_externs(const void *_a, const void *_b)
 	return strcmp(a->name, b->name);
 }
 
+static int bpf_object__record_func_info(struct bpf_object *obj, GElf_Sym *sym)
+{
+	int bind = GELF_ST_BIND(sym->st_info);
+	bool static_func = bind == STB_LOCAL;
+	struct func_desc *f;
+
+	/*
+	 * Cannot check obj->caps.btf_func_linkage during elf open phase.
+	 * Otherwise could have skipped collection of this info.
+	 */
+
+	f = obj->funcs;
+	f = reallocarray(f, obj->nr_funcs + 1, sizeof(*f));
+	if (!f)
+		return -ENOMEM;
+	obj->funcs = f;
+	f = &f[obj->nr_funcs];
+	memset(f, 0, sizeof(*f));
+	obj->nr_funcs++;
+
+	f->insn_idx = sym->st_value / 8;
+	f->linkage = static_func ? BTF_FUNC_STATIC : BTF_FUNC_GLOBAL;
+	f->sec_idx = sym->st_shndx;
+	pr_debug("Func at insn %d sec %d linkage %d\n",
+		 f->insn_idx, f->sec_idx, f->linkage);
+	return 0;
+}
+
 static int bpf_object__collect_externs(struct bpf_object *obj)
 {
 	const struct btf_type *t;
@@ -2258,6 +2295,12 @@ static int bpf_object__collect_externs(struct bpf_object *obj)
 
 		if (!gelf_getsym(obj->efile.symbols, i, &sym))
 			return -LIBBPF_ERRNO__FORMAT;
+		if (GELF_ST_TYPE(sym.st_info) == STT_FUNC) {
+			int err = bpf_object__record_func_info(obj, &sym);
+
+			if (err)
+				return err;
+		}
 		if (!sym_is_extern(&sym))
 			continue;
 		ext_name = elf_strptr(obj->efile.elf, obj->efile.strtabidx,
@@ -3145,9 +3188,62 @@ check_btf_ext_reloc_err(struct bpf_program *prog, int err,
 	return 0;
 }
 
+static int btf_ext_improve_func_info(struct bpf_object *obj,
+				     struct bpf_program *prog,
+				     __u32 sec_idx)
+{
+	struct bpf_func_info_min *info;
+	struct btf_type *t;
+	struct func_desc *f;
+	const char *name;
+	int i, j;
+
+	if (!obj->caps.btf_func_linkage || obj->llvm_emits_func_linkage)
+		/*
+		 * If kernel doesn't understand func linkage or llvm emits
+		 * it already into BTF then don't try to improve BTF based on
+		 * ELF info.
+		 */
+		return 0;
+
+	info = prog->func_info;
+	for (i = 0; i < prog->func_info_cnt; i++) {
+		for (j = 0; j < obj->nr_funcs; j++) {
+			f = &obj->funcs[j];
+			if (f->insn_idx != info->insn_off ||
+			    f->sec_idx != sec_idx)
+				continue;
+			t = (void *)btf__type_by_id(obj->btf, info->type_id);
+			if (!t)
+				return -EINVAL;
+			name = btf__name_by_offset(obj->btf, t->name_off);
+			if (!name)
+				return -EINVAL;
+			pr_debug("Func '%s' at insn %d btf_id %d linkage in BTF %d in ELF %d\n",
+				 name, info->insn_off, info->type_id,
+				 BTF_INFO_VLEN(t->info), f->linkage);
+			if (BTF_INFO_VLEN(t->info) == f->linkage) {
+				if (BTF_INFO_VLEN(t->info)) {
+					/* llvm emits func linkage. Don't touch BTF */
+					obj->llvm_emits_func_linkage = true;
+					return 0;
+				}
+			} else {
+				/* improve BTF with static vs global */
+				t->info = BTF_INFO_ENC(BTF_KIND_FUNC, 0,
+						       f->linkage);
+			}
+			break;
+		}
+		info = ((void *)info) + prog->func_info_rec_size;
+	}
+	return 0;
+}
+
 static int
 bpf_program_reloc_btf_ext(struct bpf_program *prog, struct bpf_object *obj,
-			  const char *section_name,  __u32 insn_offset)
+			  const char *section_name,  __u32 insn_offset,
+			  __u32 sec_idx)
 {
 	int err;
 
@@ -3168,6 +3264,15 @@ bpf_program_reloc_btf_ext(struct bpf_program *prog, struct bpf_object *obj,
 						       "bpf_func_info");
 
 		prog->func_info_rec_size = btf_ext__func_info_rec_size(obj->btf_ext);
+		if (!insn_offset) {
+			/*
+			 * improve BTF_KIND_FUNC when func_info is allocated
+			 * first time. Don't touch it during relocation.
+			 */
+			err = btf_ext_improve_func_info(obj, prog, sec_idx);
+			if (err)
+				return err;
+		}
 	}
 
 	if (!insn_offset || prog->line_info) {
@@ -4308,7 +4413,8 @@ bpf_program__reloc_text(struct bpf_program *prog, struct bpf_object *obj,
 		if (obj->btf_ext) {
 			err = bpf_program_reloc_btf_ext(prog, obj,
 							text->section_name,
-							prog->insns_cnt);
+							prog->insns_cnt,
+							text->idx);
 			if (err)
 				return err;
 		}
@@ -4336,7 +4442,8 @@ bpf_program__relocate(struct bpf_program *prog, struct bpf_object *obj)
 
 	if (obj->btf_ext) {
 		err = bpf_program_reloc_btf_ext(prog, obj,
-						prog->section_name, 0);
+						prog->section_name, 0,
+						prog->idx);
 		if (err)
 			return err;
 	}
-- 
2.23.0

Re: [PATCH bpf-next 2/6] libbpf: Collect static vs global info about functions

[Toke Høiland-Jørgensen]

Alexei Starovoitov <ast@kernel.org> writes:

> Collect static vs global information about BPF functions from ELF file and
> improve BTF with this additional info if llvm is too old and doesn't emit it on
> its own.

Has the support for this actually landed in LLVM yet? I tried grep'ing
in the commit log and couldn't find anything...

[...]
> @@ -313,6 +321,7 @@ struct bpf_object {
>  	bool loaded;
>  	bool has_pseudo_calls;
>  	bool relaxed_core_relocs;
> +	bool llvm_emits_func_linkage;

Nit: s/llvm/compiler/? Presumably GCC will also support this at some
point?

-Toke

Re: [PATCH bpf-next 2/6] libbpf: Collect static vs global info about functions

[Yonghong Song]

On 1/8/20 2:25 AM, Toke Høiland-Jørgensen wrote:
> Alexei Starovoitov <ast@kernel.org> writes:
> 
>> Collect static vs global information about BPF functions from ELF file and
>> improve BTF with this additional info if llvm is too old and doesn't emit it on
>> its own.
> 
> Has the support for this actually landed in LLVM yet? I tried grep'ing
> in the commit log and couldn't find anything...

It has not landed yet. The commit link is:
    https://reviews.llvm.org/D71638

I will try to land the patch in the next couple of days once this series
of patch is merged or the principle of the patch is accepted.

> 
> [...]
>> @@ -313,6 +321,7 @@ struct bpf_object {
>>   	bool loaded;
>>   	bool has_pseudo_calls;
>>   	bool relaxed_core_relocs;
>> +	bool llvm_emits_func_linkage;
> 
> Nit: s/llvm/compiler/? Presumably GCC will also support this at some
> point?
> 
> -Toke
> 

Re: [PATCH bpf-next 2/6] libbpf: Collect static vs global info about functions

[Toke Høiland-Jørgensen]

Yonghong Song <yhs@fb.com> writes:

> On 1/8/20 2:25 AM, Toke Høiland-Jørgensen wrote:
>> Alexei Starovoitov <ast@kernel.org> writes:
>> 
>>> Collect static vs global information about BPF functions from ELF file and
>>> improve BTF with this additional info if llvm is too old and doesn't emit it on
>>> its own.
>> 
>> Has the support for this actually landed in LLVM yet? I tried grep'ing
>> in the commit log and couldn't find anything...
>
> It has not landed yet. The commit link is:
>     https://reviews.llvm.org/D71638
>
> I will try to land the patch in the next couple of days once this series
> of patch is merged or the principle of the patch is accepted.

OK. My next question was going to be whether you're planning to get this
into LLVM master before the cutoff date for LLVM10, but I see Alexei
already answered that in the other reply, so great!

-Toke

Re: [PATCH bpf-next 2/6] libbpf: Collect static vs global info about functions

[Song Liu]

> On Jan 8, 2020, at 2:25 AM, Toke Høiland-Jørgensen <toke@redhat.com> wrote:
> 
> Alexei Starovoitov <ast@kernel.org> writes:
> 
>> Collect static vs global information about BPF functions from ELF file and
>> improve BTF with this additional info if llvm is too old and doesn't emit it on
>> its own.
> 
> Has the support for this actually landed in LLVM yet? I tried grep'ing
> in the commit log and couldn't find anything...
> 
> [...]
>> @@ -313,6 +321,7 @@ struct bpf_object {
>> 	bool loaded;
>> 	bool has_pseudo_calls;
>> 	bool relaxed_core_relocs;
>> +	bool llvm_emits_func_linkage;
> 
> Nit: s/llvm/compiler/? Presumably GCC will also support this at some
> point?

Echoing this nit (and other references to llvm). Otherwise,

Acked-by: Song Liu <songliubraving@fb.com>

Re: [PATCH bpf-next 2/6] libbpf: Collect static vs global info about functions

[Alexei Starovoitov]

On Wed, Jan 08, 2020 at 05:57:55PM +0000, Song Liu wrote:
> 
> 
> > On Jan 8, 2020, at 2:25 AM, Toke Høiland-Jørgensen <toke@redhat.com> wrote:
> > 
> > Alexei Starovoitov <ast@kernel.org> writes:
> > 
> >> Collect static vs global information about BPF functions from ELF file and
> >> improve BTF with this additional info if llvm is too old and doesn't emit it on
> >> its own.
> > 
> > Has the support for this actually landed in LLVM yet? I tried grep'ing
> > in the commit log and couldn't find anything...
> > 
> > [...]
> >> @@ -313,6 +321,7 @@ struct bpf_object {
> >> 	bool loaded;
> >> 	bool has_pseudo_calls;
> >> 	bool relaxed_core_relocs;
> >> +	bool llvm_emits_func_linkage;
> > 
> > Nit: s/llvm/compiler/? Presumably GCC will also support this at some
> > point?
> 
> Echoing this nit (and other references to llvm). Otherwise,

sure. will rename to compiler, but I think you folks are overly optimistic
about gcc. Even basic stuff doesn't work yet. I doubt we will see BTF
emitted by gcc this year.

[PATCH bpf-next 3/6] bpf: Introduce function-by-function verification

[Alexei Starovoitov]

New llvm and old llvm with libbpf help produce BTF that distinguish global and
static functions. Unlike arguments of static function the arguments of global
functions cannot be removed or optimized away by llvm. The compiler has to use
exactly the arguments specified in a function prototype. The argument type
information allows the verifier validate each global function independently.
For now only supported argument types are pointer to context and scalars. In
the future pointers to structures, sizes, pointer to packet data can be
supported as well. Consider the following example:

static int f1(int ...)
{
  ...
}

int f3(int b);

int f2(int a)
{
  f1(a) + f3(a);
}

int f3(int b)
{
  ...
}

int main(...)
{
  f1(...) + f2(...) + f3(...);
}

The verifier will start its safety checks from the first global function f2().
It will recursively descend into f1() because it's static. Then it will check
that arguments match for the f3() invocation inside f2(). It will not descend
into f3(). It will finish f2() that has to be successfully verified for all
possible values of 'a'. Then it will proceed with f3(). That function also has
to be safe for all possible values of 'b'. Then it will start subprog 0 (which
is main() function). It will recursively descend into f1() and will skip full
check of f2() and f3(), since they are global. The order of processing global
functions doesn't affect safety, since all global functions must be proven safe
based on their arguments only.

Such function by function verification can drastically improve speed of the
verification and reduce complexity.

Note that the stack limit of 512 still applies to the call chain regardless whether
functions were static or global. The nested level of 8 also still applies. The
same recursion prevention checks are in place as well.

The type information and static/global kind is preserved after the verification
hence in the above example global function f2() and f3() can be replaced later
by equivalent functions with the same types that are loaded and verified later
without affecting safety of this main() program. Such replacement (re-linking)
of global functions is a subject of future patches.

Signed-off-by: Alexei Starovoitov <ast@kernel.org>
---
 include/linux/bpf.h          |   7 +-
 include/linux/bpf_verifier.h |   7 +-
 include/uapi/linux/btf.h     |   6 +
 kernel/bpf/btf.c             | 147 +++++++++++++++++-----
 kernel/bpf/verifier.c        | 228 +++++++++++++++++++++++++++--------
 5 files changed, 317 insertions(+), 78 deletions(-)

diff --git a/include/linux/bpf.h b/include/linux/bpf.h
index b14e51d56a82..ceb5b6c13abc 100644
--- a/include/linux/bpf.h
+++ b/include/linux/bpf.h
@@ -558,6 +558,7 @@ static inline void bpf_dispatcher_change_prog(struct bpf_dispatcher *d,
 #endif
 
 struct bpf_func_info_aux {
+	u32 linkage;
 	bool unreliable;
 };
 
@@ -1006,7 +1007,11 @@ int btf_distill_func_proto(struct bpf_verifier_log *log,
 			   const char *func_name,
 			   struct btf_func_model *m);
 
-int btf_check_func_arg_match(struct bpf_verifier_env *env, int subprog);
+struct bpf_reg_state;
+int btf_check_func_arg_match(struct bpf_verifier_env *env, int subprog,
+			     struct bpf_reg_state *regs);
+int btf_prepare_func_args(struct bpf_verifier_env *env, int subprog,
+			  struct bpf_reg_state *reg);
 
 struct bpf_prog *bpf_prog_by_id(u32 id);
 
diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h
index 26e40de9ef55..b668d3ba2f11 100644
--- a/include/linux/bpf_verifier.h
+++ b/include/linux/bpf_verifier.h
@@ -304,11 +304,13 @@ struct bpf_insn_aux_data {
 	u64 map_key_state; /* constant (32 bit) key tracking for maps */
 	int ctx_field_size; /* the ctx field size for load insn, maybe 0 */
 	int sanitize_stack_off; /* stack slot to be cleared */
-	bool seen; /* this insn was processed by the verifier */
+	u32 seen; /* this insn was processed by the verifier at env->pass_cnt */
 	bool zext_dst; /* this insn zero extends dst reg */
 	u8 alu_state; /* used in combination with alu_limit */
-	bool prune_point;
+
+	/* below fields are initialized once */
 	unsigned int orig_idx; /* original instruction index */
+	bool prune_point;
 };
 
 #define MAX_USED_MAPS 64 /* max number of maps accessed by one eBPF program */
@@ -379,6 +381,7 @@ struct bpf_verifier_env {
 		int *insn_stack;
 		int cur_stack;
 	} cfg;
+	u32 pass_cnt; /* number of times do_check() was called */
 	u32 subprog_cnt;
 	/* number of instructions analyzed by the verifier */
 	u32 prev_insn_processed, insn_processed;
diff --git a/include/uapi/linux/btf.h b/include/uapi/linux/btf.h
index 1a2898c482ee..5a667107ad2c 100644
--- a/include/uapi/linux/btf.h
+++ b/include/uapi/linux/btf.h
@@ -146,6 +146,12 @@ enum {
 	BTF_VAR_GLOBAL_EXTERN = 2,
 };
 
+enum btf_func_linkage {
+	BTF_FUNC_STATIC = 0,
+	BTF_FUNC_GLOBAL = 1,
+	BTF_FUNC_EXTERN = 2,
+};
+
 /* BTF_KIND_VAR is followed by a single "struct btf_var" to describe
  * additional information related to the variable such as its linkage.
  */
diff --git a/kernel/bpf/btf.c b/kernel/bpf/btf.c
index ed2075884724..e28ec89971ce 100644
--- a/kernel/bpf/btf.c
+++ b/kernel/bpf/btf.c
@@ -2621,8 +2621,8 @@ static s32 btf_func_check_meta(struct btf_verifier_env *env,
 		return -EINVAL;
 	}
 
-	if (btf_type_vlen(t)) {
-		btf_verifier_log_type(env, t, "vlen != 0");
+	if (btf_type_vlen(t) > BTF_FUNC_EXTERN) {
+		btf_verifier_log_type(env, t, "invalid func linkage");
 		return -EINVAL;
 	}
 
@@ -3476,7 +3476,8 @@ static u8 bpf_ctx_convert_map[] = {
 
 static const struct btf_member *
 btf_get_prog_ctx_type(struct bpf_verifier_log *log, struct btf *btf,
-		      const struct btf_type *t, enum bpf_prog_type prog_type)
+		      const struct btf_type *t, enum bpf_prog_type prog_type,
+		      int arg)
 {
 	const struct btf_type *conv_struct;
 	const struct btf_type *ctx_struct;
@@ -3497,12 +3498,13 @@ btf_get_prog_ctx_type(struct bpf_verifier_log *log, struct btf *btf,
 		 * is not supported yet.
 		 * BPF_PROG_TYPE_RAW_TRACEPOINT is fine.
 		 */
-		bpf_log(log, "BPF program ctx type is not a struct\n");
+		if (log->level & BPF_LOG_LEVEL)
+			bpf_log(log, "arg#%d type is not a struct\n", arg);
 		return NULL;
 	}
 	tname = btf_name_by_offset(btf, t->name_off);
 	if (!tname) {
-		bpf_log(log, "BPF program ctx struct doesn't have a name\n");
+		bpf_log(log, "arg#%d struct doesn't have a name\n", arg);
 		return NULL;
 	}
 	/* prog_type is valid bpf program type. No need for bounds check. */
@@ -3535,11 +3537,12 @@ btf_get_prog_ctx_type(struct bpf_verifier_log *log, struct btf *btf,
 static int btf_translate_to_vmlinux(struct bpf_verifier_log *log,
 				     struct btf *btf,
 				     const struct btf_type *t,
-				     enum bpf_prog_type prog_type)
+				     enum bpf_prog_type prog_type,
+				     int arg)
 {
 	const struct btf_member *prog_ctx_type, *kern_ctx_type;
 
-	prog_ctx_type = btf_get_prog_ctx_type(log, btf, t, prog_type);
+	prog_ctx_type = btf_get_prog_ctx_type(log, btf, t, prog_type, arg);
 	if (!prog_ctx_type)
 		return -ENOENT;
 	kern_ctx_type = prog_ctx_type + 1;
@@ -3700,7 +3703,7 @@ bool btf_ctx_access(int off, int size, enum bpf_access_type type,
 	info->btf_id = t->type;
 
 	if (tgt_prog) {
-		ret = btf_translate_to_vmlinux(log, btf, t, tgt_prog->type);
+		ret = btf_translate_to_vmlinux(log, btf, t, tgt_prog->type, arg);
 		if (ret > 0) {
 			info->btf_id = ret;
 			return true;
@@ -4043,11 +4046,10 @@ int btf_distill_func_proto(struct bpf_verifier_log *log,
 	return 0;
 }
 
-int btf_check_func_arg_match(struct bpf_verifier_env *env, int subprog)
+/* Compare BTF of a function with given bpf_reg_state */
+int btf_check_func_arg_match(struct bpf_verifier_env *env, int subprog,
+			     struct bpf_reg_state *reg)
 {
-	struct bpf_verifier_state *st = env->cur_state;
-	struct bpf_func_state *func = st->frame[st->curframe];
-	struct bpf_reg_state *reg = func->regs;
 	struct bpf_verifier_log *log = &env->log;
 	struct bpf_prog *prog = env->prog;
 	struct btf *btf = prog->aux->btf;
@@ -4057,27 +4059,27 @@ int btf_check_func_arg_match(struct bpf_verifier_env *env, int subprog)
 	const char *tname;
 
 	if (!prog->aux->func_info)
-		return 0;
+		return -EINVAL;
 
 	btf_id = prog->aux->func_info[subprog].type_id;
 	if (!btf_id)
-		return 0;
+		return -EINVAL;
 
 	if (prog->aux->func_info_aux[subprog].unreliable)
-		return 0;
+		return -EINVAL;
 
 	t = btf_type_by_id(btf, btf_id);
 	if (!t || !btf_type_is_func(t)) {
-		bpf_log(log, "BTF of subprog %d doesn't point to KIND_FUNC\n",
+		bpf_log(log, "BTF of func#%d doesn't point to KIND_FUNC\n",
 			subprog);
-		return -EINVAL;
+		return -EFAULT;
 	}
 	tname = btf_name_by_offset(btf, t->name_off);
 
 	t = btf_type_by_id(btf, t->type);
 	if (!t || !btf_type_is_func_proto(t)) {
 		bpf_log(log, "Invalid type of func %s\n", tname);
-		return -EINVAL;
+		return -EFAULT;
 	}
 	args = (const struct btf_param *)(t + 1);
 	nargs = btf_type_vlen(t);
@@ -4103,25 +4105,116 @@ int btf_check_func_arg_match(struct bpf_verifier_env *env, int subprog)
 				bpf_log(log, "R%d is not a pointer\n", i + 1);
 				goto out;
 			}
-			/* If program is passing PTR_TO_CTX into subprogram
-			 * check that BTF type matches.
+			/* If function expects ctx type in BTF check that callee
+			 * is passing PTR_TO_CTX.
 			 */
-			if (reg[i + 1].type == PTR_TO_CTX &&
-			    !btf_get_prog_ctx_type(log, btf, t, prog->type))
+			if (btf_get_prog_ctx_type(log, btf, t, prog->type, i) &&
+			    reg[i + 1].type != PTR_TO_CTX) {
+				bpf_log(log,
+					"arg#%d expected pointer to ctx, but got %s\n",
+					i, btf_kind_str[BTF_INFO_KIND(t->info)]);
 				goto out;
+			}
 			/* All other pointers are ok */
 			continue;
 		}
-		bpf_log(log, "Unrecognized argument type %s\n",
-			btf_kind_str[BTF_INFO_KIND(t->info)]);
+		bpf_log(log, "Unrecognized arg#%d type %s\n",
+			i, btf_kind_str[BTF_INFO_KIND(t->info)]);
 		goto out;
 	}
 	return 0;
 out:
-	/* LLVM optimizations can remove arguments from static functions. */
-	bpf_log(log,
-		"Type info disagrees with actual arguments due to compiler optimizations\n");
+	/* LLVM optimizations can remove arguments from static functions
+	 * or mismatched type can be passed into a global function.
+	 * In such cases mark the function as unreliable from BTF point of view.
+	 */
 	prog->aux->func_info_aux[subprog].unreliable = true;
+	return -EINVAL;
+}
+
+/* Convert BTF of a function into bpf_reg_state if possible */
+int btf_prepare_func_args(struct bpf_verifier_env *env, int subprog,
+			  struct bpf_reg_state *reg)
+{
+	struct bpf_verifier_log *log = &env->log;
+	struct bpf_prog *prog = env->prog;
+	struct btf *btf = prog->aux->btf;
+	const struct btf_param *args;
+	const struct btf_type *t;
+	u32 i, nargs, btf_id;
+	const char *tname;
+
+	if (!prog->aux->func_info ||
+	    prog->aux->func_info_aux[subprog].linkage != BTF_FUNC_GLOBAL) {
+		bpf_log(log, "Verifier bug\n");
+		return -EFAULT;
+	}
+
+	btf_id = prog->aux->func_info[subprog].type_id;
+	if (!btf_id) {
+		bpf_log(log, "Global functions need valid BTF\n");
+		return -EINVAL;
+	}
+
+	t = btf_type_by_id(btf, btf_id);
+	if (!t || !btf_type_is_func(t)) {
+		bpf_log(log, "BTF of func#%d doesn't point to KIND_FUNC\n",
+			subprog);
+		return -EINVAL;
+	}
+	tname = btf_name_by_offset(btf, t->name_off);
+
+	if (log->level & BPF_LOG_LEVEL)
+		bpf_log(log, "Validating %s() func#%d...\n",
+			tname, subprog);
+
+	if (prog->aux->func_info_aux[subprog].unreliable) {
+		bpf_log(log, "Verifier bug in function %s()\n", tname);
+		return -EFAULT;
+	}
+
+	t = btf_type_by_id(btf, t->type);
+	if (!t || !btf_type_is_func_proto(t)) {
+		bpf_log(log, "Invalid type of function %s()\n", tname);
+		return -EINVAL;
+	}
+	args = (const struct btf_param *)(t + 1);
+	nargs = btf_type_vlen(t);
+	if (nargs > 5) {
+		bpf_log(log, "Global function %s() with %d > 5 args. Buggy llvm.\n",
+			tname, nargs);
+		return -EINVAL;
+	}
+	/* check that function returns int */
+	t = btf_type_by_id(btf, t->type);
+	while (btf_type_is_modifier(t))
+		t = btf_type_by_id(btf, t->type);
+	if (!btf_type_is_int(t) && !btf_type_is_enum(t)) {
+		bpf_log(log,
+			"Global function %s() doesn't return scalar. Only those are supported.\n",
+			tname);
+		return -EINVAL;
+	}
+	/* Convert BTF function arguments into verifier types.
+	 * Only PTR_TO_CTX and SCALAR are supported atm.
+	 */
+	for (i = 0; i < nargs; i++) {
+		t = btf_type_by_id(btf, args[i].type);
+		while (btf_type_is_modifier(t))
+			t = btf_type_by_id(btf, t->type);
+		if (btf_type_is_int(t) || btf_type_is_enum(t)) {
+			reg[i + 1].type = SCALAR_VALUE;
+			continue;
+		}
+		if (btf_type_is_ptr(t) &&
+		    btf_get_prog_ctx_type(log, btf, t, prog->type, i)) {
+			reg[i + 1].type = PTR_TO_CTX;
+			continue;
+		}
+		bpf_log(log, "Arg#%d type %s in %s() is not supported yet.\n",
+			i, btf_kind_str[BTF_INFO_KIND(t->info)], tname);
+		return -EINVAL;
+	}
 	return 0;
 }
 
diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 6f63ae7a370c..3abb5bcc5cd9 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -1122,10 +1122,6 @@ static void init_reg_state(struct bpf_verifier_env *env,
 	regs[BPF_REG_FP].type = PTR_TO_STACK;
 	mark_reg_known_zero(env, regs, BPF_REG_FP);
 	regs[BPF_REG_FP].frameno = state->frameno;
-
-	/* 1st arg to a function */
-	regs[BPF_REG_1].type = PTR_TO_CTX;
-	mark_reg_known_zero(env, regs, BPF_REG_1);
 }
 
 #define BPF_MAIN_FUNC (-1)
@@ -3945,12 +3941,26 @@ static int release_reference(struct bpf_verifier_env *env,
 	return 0;
 }
 
+static void clear_caller_saved_regs(struct bpf_verifier_env *env,
+				    struct bpf_reg_state *regs)
+{
+	int i;
+
+	/* after the call registers r0 - r5 were scratched */
+	for (i = 0; i < CALLER_SAVED_REGS; i++) {
+		mark_reg_not_init(env, regs, caller_saved[i]);
+		check_reg_arg(env, caller_saved[i], DST_OP_NO_MARK);
+	}
+}
+
 static int check_func_call(struct bpf_verifier_env *env, struct bpf_insn *insn,
 			   int *insn_idx)
 {
 	struct bpf_verifier_state *state = env->cur_state;
+	struct bpf_func_info_aux *func_info_aux;
 	struct bpf_func_state *caller, *callee;
 	int i, err, subprog, target_insn;
+	bool is_global = false;
 
 	if (state->curframe + 1 >= MAX_CALL_FRAMES) {
 		verbose(env, "the call stack of %d frames is too deep\n",
@@ -3973,6 +3983,32 @@ static int check_func_call(struct bpf_verifier_env *env, struct bpf_insn *insn,
 		return -EFAULT;
 	}
 
+	func_info_aux = env->prog->aux->func_info_aux;
+	if (func_info_aux)
+		is_global = func_info_aux[subprog].linkage == BTF_FUNC_GLOBAL;
+	err = btf_check_func_arg_match(env, subprog, caller->regs);
+	if (err == -EFAULT)
+		return err;
+	if (is_global) {
+		if (err) {
+			verbose(env, "Caller passes invalid args into func#%d\n",
+				subprog);
+			return err;
+		} else {
+			if (env->log.level & BPF_LOG_LEVEL)
+				verbose(env,
+					"Func#%d is global and valid. Skipping.\n",
+					subprog);
+			clear_caller_saved_regs(env, caller->regs);
+
+			/* All global functions return SCALAR_VALUE */
+			mark_reg_unknown(env, caller->regs, BPF_REG_0);
+
+			/* continue with next insn after call */
+			return 0;
+		}
+	}
+
 	callee = kzalloc(sizeof(*callee), GFP_KERNEL);
 	if (!callee)
 		return -ENOMEM;
@@ -3999,18 +4035,11 @@ static int check_func_call(struct bpf_verifier_env *env, struct bpf_insn *insn,
 	for (i = BPF_REG_1; i <= BPF_REG_5; i++)
 		callee->regs[i] = caller->regs[i];
 
-	/* after the call registers r0 - r5 were scratched */
-	for (i = 0; i < CALLER_SAVED_REGS; i++) {
-		mark_reg_not_init(env, caller->regs, caller_saved[i]);
-		check_reg_arg(env, caller_saved[i], DST_OP_NO_MARK);
-	}
+	clear_caller_saved_regs(env, caller->regs);
 
 	/* only increment it after check_reg_arg() finished */
 	state->curframe++;
 
-	if (btf_check_func_arg_match(env, subprog))
-		return -EINVAL;
-
 	/* and go analyze first insn of the callee */
 	*insn_idx = target_insn;
 
@@ -6738,12 +6767,13 @@ static int check_btf_func(struct bpf_verifier_env *env,
 
 		/* check type_id */
 		type = btf_type_by_id(btf, krecord[i].type_id);
-		if (!type || BTF_INFO_KIND(type->info) != BTF_KIND_FUNC) {
+		if (!type || !btf_type_is_func(type)) {
 			verbose(env, "invalid type id %d in func info",
 				krecord[i].type_id);
 			ret = -EINVAL;
 			goto err_free;
 		}
+		info_aux[i].linkage = BTF_INFO_VLEN(type->info);
 		prev_offset = krecord[i].insn_off;
 		urecord += urec_size;
 	}
@@ -7723,35 +7753,13 @@ static bool reg_type_mismatch(enum bpf_reg_type src, enum bpf_reg_type prev)
 
 static int do_check(struct bpf_verifier_env *env)
 {
-	struct bpf_verifier_state *state;
+	struct bpf_verifier_state *state = env->cur_state;
 	struct bpf_insn *insns = env->prog->insnsi;
 	struct bpf_reg_state *regs;
 	int insn_cnt = env->prog->len;
 	bool do_print_state = false;
 	int prev_insn_idx = -1;
 
-	env->prev_linfo = NULL;
-
-	state = kzalloc(sizeof(struct bpf_verifier_state), GFP_KERNEL);
-	if (!state)
-		return -ENOMEM;
-	state->curframe = 0;
-	state->speculative = false;
-	state->branches = 1;
-	state->frame[0] = kzalloc(sizeof(struct bpf_func_state), GFP_KERNEL);
-	if (!state->frame[0]) {
-		kfree(state);
-		return -ENOMEM;
-	}
-	env->cur_state = state;
-	init_func_state(env, state->frame[0],
-			BPF_MAIN_FUNC /* callsite */,
-			0 /* frameno */,
-			0 /* subprogno, zero == main subprog */);
-
-	if (btf_check_func_arg_match(env, 0))
-		return -EINVAL;
-
 	for (;;) {
 		struct bpf_insn *insn;
 		u8 class;
@@ -7829,7 +7837,7 @@ static int do_check(struct bpf_verifier_env *env)
 		}
 
 		regs = cur_regs(env);
-		env->insn_aux_data[env->insn_idx].seen = true;
+		env->insn_aux_data[env->insn_idx].seen = env->pass_cnt;
 		prev_insn_idx = env->insn_idx;
 
 		if (class == BPF_ALU || class == BPF_ALU64) {
@@ -8064,7 +8072,7 @@ static int do_check(struct bpf_verifier_env *env)
 					return err;
 
 				env->insn_idx++;
-				env->insn_aux_data[env->insn_idx].seen = true;
+				env->insn_aux_data[env->insn_idx].seen = env->pass_cnt;
 			} else {
 				verbose(env, "invalid BPF_LD mode\n");
 				return -EINVAL;
@@ -8077,7 +8085,6 @@ static int do_check(struct bpf_verifier_env *env)
 		env->insn_idx++;
 	}
 
-	env->prog->aux->stack_depth = env->subprog_info[0].stack_depth;
 	return 0;
 }
 
@@ -8349,7 +8356,7 @@ static int adjust_insn_aux_data(struct bpf_verifier_env *env,
 	memcpy(new_data + off + cnt - 1, old_data + off,
 	       sizeof(struct bpf_insn_aux_data) * (prog_len - off - cnt + 1));
 	for (i = off; i < off + cnt - 1; i++) {
-		new_data[i].seen = true;
+		new_data[i].seen = env->pass_cnt;
 		new_data[i].zext_dst = insn_has_def32(env, insn + i);
 	}
 	env->insn_aux_data = new_data;
@@ -9459,6 +9466,7 @@ static void free_states(struct bpf_verifier_env *env)
 		kfree(sl);
 		sl = sln;
 	}
+	env->free_list = NULL;
 
 	if (!env->explored_states)
 		return;
@@ -9472,11 +9480,139 @@ static void free_states(struct bpf_verifier_env *env)
 			kfree(sl);
 			sl = sln;
 		}
+		env->explored_states[i] = NULL;
 	}
+}
 
-	kvfree(env->explored_states);
+static void sanitize_insn_aux_data(struct bpf_verifier_env *env)
+{
+	struct bpf_insn *insn = env->prog->insnsi;
+	struct bpf_insn_aux_data *aux;
+	int i, class;
+
+	for (i = 0; i < env->prog->len; i++) {
+		class = BPF_CLASS(insn[i].code);
+		if (class != BPF_LDX && class != BPF_STX)
+			continue;
+		aux = &env->insn_aux_data[i];
+		if (aux->seen != env->pass_cnt)
+			continue;
+		memset(aux, 0, offsetof(typeof(*aux), orig_idx));
+	}
 }
 
+static int do_check_common(struct bpf_verifier_env *env, int subprog)
+{
+	struct bpf_verifier_state *state;
+	struct bpf_reg_state *regs;
+	int ret, i;
+
+	env->prev_linfo = NULL;
+	env->pass_cnt++;
+
+	state = kzalloc(sizeof(struct bpf_verifier_state), GFP_KERNEL);
+	if (!state)
+		return -ENOMEM;
+	state->curframe = 0;
+	state->speculative = false;
+	state->branches = 1;
+	state->frame[0] = kzalloc(sizeof(struct bpf_func_state), GFP_KERNEL);
+	if (!state->frame[0]) {
+		kfree(state);
+		return -ENOMEM;
+	}
+	env->cur_state = state;
+	init_func_state(env, state->frame[0],
+			BPF_MAIN_FUNC /* callsite */,
+			0 /* frameno */,
+			subprog);
+
+	regs = state->frame[state->curframe]->regs;
+	if (subprog) {
+		ret = btf_prepare_func_args(env, subprog, regs);
+		if (ret)
+			return ret;
+		for (i = BPF_REG_1; i <= BPF_REG_5; i++) {
+			if (regs[i].type == PTR_TO_CTX)
+				mark_reg_known_zero(env, regs, i);
+			else if (regs[i].type == SCALAR_VALUE)
+				mark_reg_unknown(env, regs, i);
+		}
+	} else {
+		/* 1st arg to a function */
+		regs[BPF_REG_1].type = PTR_TO_CTX;
+		mark_reg_known_zero(env, regs, BPF_REG_1);
+		if (btf_check_func_arg_match(env, subprog, regs) == -EFAULT)
+			return -EFAULT;
+	}
+
+	ret = do_check(env);
+	if (env->cur_state) {
+		free_verifier_state(env->cur_state, true);
+		env->cur_state = NULL;
+	}
+	while (!pop_stack(env, NULL, NULL));
+	free_states(env);
+	if (ret)
+		/* clean aux data in case subprog was rejected */
+		sanitize_insn_aux_data(env);
+	return ret;
+}
+
+/* Verify all global functions in a BPF program one by one based on their BTF.
+ * All global functions must pass verification. Otherwise the whole program is rejected.
+ * Consider:
+ * int bar(int);
+ * int foo(int f)
+ * {
+ *    return bar(f);
+ * }
+ * int bar(int b)
+ * {
+ *    ...
+ * }
+ * foo() will be verified first for R1=any_scalar_value. During verification it
+ * will be assumed that bar() already verified successfully and call to bar()
+ * from foo() will be checked for type match only. Later bar() will be verified
+ * independently to check that it's safe for R1=any_scalar_value.
+ */
+static int do_check_subprogs(struct bpf_verifier_env *env)
+{
+	struct bpf_prog_aux *aux = env->prog->aux;
+	int i, ret;
+
+	if (!aux->func_info)
+		return 0;
+
+	for (i = 1; i < env->subprog_cnt; i++) {
+		if (aux->func_info_aux[i].linkage != BTF_FUNC_GLOBAL)
+			continue;
+		env->insn_idx = env->subprog_info[i].start;
+		WARN_ON_ONCE(env->insn_idx == 0);
+		ret = do_check_common(env, i);
+		if (ret) {
+			return ret;
+		} else if (env->log.level & BPF_LOG_LEVEL) {
+			verbose(env,
+				"Func#%d is safe for any args that match its prototype\n",
+				i);
+		}
+	}
+	return 0;
+}
+
+static int do_check_main(struct bpf_verifier_env *env)
+{
+	int ret;
+
+	env->insn_idx = 0;
+	ret = do_check_common(env, 0);
+	if (!ret)
+		env->prog->aux->stack_depth = env->subprog_info[0].stack_depth;
+	return ret;
+}
+
+
 static void print_verification_stats(struct bpf_verifier_env *env)
 {
 	int i;
@@ -9769,18 +9905,14 @@ int bpf_check(struct bpf_prog **prog, union bpf_attr *attr,
 	if (ret < 0)
 		goto skip_full_check;
 
-	ret = do_check(env);
-	if (env->cur_state) {
-		free_verifier_state(env->cur_state, true);
-		env->cur_state = NULL;
-	}
+	ret = do_check_subprogs(env);
+	ret = ret ?: do_check_main(env);
 
 	if (ret == 0 && bpf_prog_is_dev_bound(env->prog->aux))
 		ret = bpf_prog_offload_finalize(env);
 
 skip_full_check:
-	while (!pop_stack(env, NULL, NULL));
-	free_states(env);
+	kvfree(env->explored_states);
 
 	if (ret == 0)
 		ret = check_max_stack_depth(env);
-- 
2.23.0

Re: [PATCH bpf-next 3/6] bpf: Introduce function-by-function verification

[Toke Høiland-Jørgensen]

Alexei Starovoitov <ast@kernel.org> writes:

> New llvm and old llvm with libbpf help produce BTF that distinguish global and
> static functions. Unlike arguments of static function the arguments of global
> functions cannot be removed or optimized away by llvm. The compiler has to use
> exactly the arguments specified in a function prototype. The argument type
> information allows the verifier validate each global function independently.
> For now only supported argument types are pointer to context and scalars. In
> the future pointers to structures, sizes, pointer to packet data can be
> supported as well. Consider the following example:
>
> static int f1(int ...)
> {
>   ...
> }
>
> int f3(int b);
>
> int f2(int a)
> {
>   f1(a) + f3(a);
> }
>
> int f3(int b)
> {
>   ...
> }
>
> int main(...)
> {
>   f1(...) + f2(...) + f3(...);
> }
>
> The verifier will start its safety checks from the first global function f2().
> It will recursively descend into f1() because it's static. Then it will check
> that arguments match for the f3() invocation inside f2(). It will not descend
> into f3(). It will finish f2() that has to be successfully verified for all
> possible values of 'a'. Then it will proceed with f3(). That function also has
> to be safe for all possible values of 'b'. Then it will start subprog 0 (which
> is main() function). It will recursively descend into f1() and will skip full
> check of f2() and f3(), since they are global. The order of processing global
> functions doesn't affect safety, since all global functions must be proven safe
> based on their arguments only.
>
> Such function by function verification can drastically improve speed of the
> verification and reduce complexity.
>
> Note that the stack limit of 512 still applies to the call chain regardless whether
> functions were static or global. The nested level of 8 also still applies. The
> same recursion prevention checks are in place as well.
>
> The type information and static/global kind is preserved after the verification
> hence in the above example global function f2() and f3() can be replaced later
> by equivalent functions with the same types that are loaded and verified later
> without affecting safety of this main() program. Such replacement (re-linking)
> of global functions is a subject of future patches.
>
> Signed-off-by: Alexei Starovoitov <ast@kernel.org>

Great to see this progressing; and thanks for breaking things up, makes
it much easier to follow along!

One question:

> +enum btf_func_linkage {
> +	BTF_FUNC_STATIC = 0,
> +	BTF_FUNC_GLOBAL = 1,
> +	BTF_FUNC_EXTERN = 2,
> +};

What's supposed to happen with FUNC_EXTERN? That is specifically for the
re-linking follow-up?

>  /* BTF_KIND_VAR is followed by a single "struct btf_var" to describe
>   * additional information related to the variable such as its linkage.
>   */
> diff --git a/kernel/bpf/btf.c b/kernel/bpf/btf.c
> index ed2075884724..e28ec89971ce 100644
> --- a/kernel/bpf/btf.c
> +++ b/kernel/bpf/btf.c
> @@ -2621,8 +2621,8 @@ static s32 btf_func_check_meta(struct btf_verifier_env *env,
>  		return -EINVAL;
>  	}
>  
> -	if (btf_type_vlen(t)) {
> -		btf_verifier_log_type(env, t, "vlen != 0");
> +	if (btf_type_vlen(t) > BTF_FUNC_EXTERN) {
> +		btf_verifier_log_type(env, t, "invalid func linkage");

This doesn't reject linkage==BTF_FUNC_EXTERN; so for this patch
FUNC_EXTERN will be treated the same as FUNC_STATIC (it'll fail the
is_global check below)? Or did I miss somewhere else where
BTF_FUNC_EXTERN is rejected?

-Toke

Re: [PATCH bpf-next 3/6] bpf: Introduce function-by-function verification

[Alexei Starovoitov]

On Wed, Jan 08, 2020 at 11:28:21AM +0100, Toke Høiland-Jørgensen wrote:
> Alexei Starovoitov <ast@kernel.org> writes:
> 
> > New llvm and old llvm with libbpf help produce BTF that distinguish global and
> > static functions. Unlike arguments of static function the arguments of global
> > functions cannot be removed or optimized away by llvm. The compiler has to use
> > exactly the arguments specified in a function prototype. The argument type
> > information allows the verifier validate each global function independently.
> > For now only supported argument types are pointer to context and scalars. In
> > the future pointers to structures, sizes, pointer to packet data can be
> > supported as well. Consider the following example:
> >
> > static int f1(int ...)
> > {
> >   ...
> > }
> >
> > int f3(int b);
> >
> > int f2(int a)
> > {
> >   f1(a) + f3(a);
> > }
> >
> > int f3(int b)
> > {
> >   ...
> > }
> >
> > int main(...)
> > {
> >   f1(...) + f2(...) + f3(...);
> > }
> >
> > The verifier will start its safety checks from the first global function f2().
> > It will recursively descend into f1() because it's static. Then it will check
> > that arguments match for the f3() invocation inside f2(). It will not descend
> > into f3(). It will finish f2() that has to be successfully verified for all
> > possible values of 'a'. Then it will proceed with f3(). That function also has
> > to be safe for all possible values of 'b'. Then it will start subprog 0 (which
> > is main() function). It will recursively descend into f1() and will skip full
> > check of f2() and f3(), since they are global. The order of processing global
> > functions doesn't affect safety, since all global functions must be proven safe
> > based on their arguments only.
> >
> > Such function by function verification can drastically improve speed of the
> > verification and reduce complexity.
> >
> > Note that the stack limit of 512 still applies to the call chain regardless whether
> > functions were static or global. The nested level of 8 also still applies. The
> > same recursion prevention checks are in place as well.
> >
> > The type information and static/global kind is preserved after the verification
> > hence in the above example global function f2() and f3() can be replaced later
> > by equivalent functions with the same types that are loaded and verified later
> > without affecting safety of this main() program. Such replacement (re-linking)
> > of global functions is a subject of future patches.
> >
> > Signed-off-by: Alexei Starovoitov <ast@kernel.org>
> 
> Great to see this progressing; and thanks for breaking things up, makes
> it much easier to follow along!
> 
> One question:
> 
> > +enum btf_func_linkage {
> > +	BTF_FUNC_STATIC = 0,
> > +	BTF_FUNC_GLOBAL = 1,
> > +	BTF_FUNC_EXTERN = 2,
> > +};
> 
> What's supposed to happen with FUNC_EXTERN? That is specifically for the
> re-linking follow-up?

I was thinking to complete the whole thing with re-linking and then send it,
but llvm 10 feature cut off date is end of this week, so we have to land llvm
bits asap. I'd like to land patch 1 with libbpf sanitization first before
landing llvm. llvm release cadence is ~4 month and it would be sad to miss it.
Note we will be able to tweak encoding if really necessary after next week.
(BTF encoding gets fixed in ABI only after full kernel release).
It's unlikely though. I think the encoding is good. I've played with few
different variants and this one fits the best. FUNC_EXTERN encoding as 2 is
kinda obvious when encoding for global vs static is selected. The kernel and
libbpf will not be using FUNC_EXTERN yet, but llvm is tested to do the right
thing already, so I think it's fine to add it to btf.h now.

As far as future plans when libbpf sees FUNC_EXTERN it will do the linking the
way we discussed in the other thread. The kernel will support FUNC_EXTERN when
we introduce dynamic libraries. A collection of bpf functions will be loaded
into the kernel first (like libc.so) and later programs will have FUNC_EXTERN
as part of their BTF to be resolved while loading. The func name to btf_id
resolution will be done by libbpf. The kernel verifier will do the type
checking on BTFs. So the kernel side of FUNC_EXTERN support will be minimal,
but to your point below...

> This doesn't reject linkage==BTF_FUNC_EXTERN; so for this patch
> FUNC_EXTERN will be treated the same as FUNC_STATIC (it'll fail the
> is_global check below)? Or did I miss somewhere else where
> BTF_FUNC_EXTERN is rejected?

... is absolutely correct. My bad. Added this bit too soon.
Will remove. The kernel should accept FUNC_GLOBAL only in this patch set.

Re: [PATCH bpf-next 3/6] bpf: Introduce function-by-function verification

[Toke Høiland-Jørgensen]

Alexei Starovoitov <alexei.starovoitov@gmail.com> writes:

> On Wed, Jan 08, 2020 at 11:28:21AM +0100, Toke Høiland-Jørgensen wrote:
>> Alexei Starovoitov <ast@kernel.org> writes:
>> 
>> > New llvm and old llvm with libbpf help produce BTF that distinguish global and
>> > static functions. Unlike arguments of static function the arguments of global
>> > functions cannot be removed or optimized away by llvm. The compiler has to use
>> > exactly the arguments specified in a function prototype. The argument type
>> > information allows the verifier validate each global function independently.
>> > For now only supported argument types are pointer to context and scalars. In
>> > the future pointers to structures, sizes, pointer to packet data can be
>> > supported as well. Consider the following example:
>> >
>> > static int f1(int ...)
>> > {
>> >   ...
>> > }
>> >
>> > int f3(int b);
>> >
>> > int f2(int a)
>> > {
>> >   f1(a) + f3(a);
>> > }
>> >
>> > int f3(int b)
>> > {
>> >   ...
>> > }
>> >
>> > int main(...)
>> > {
>> >   f1(...) + f2(...) + f3(...);
>> > }
>> >
>> > The verifier will start its safety checks from the first global function f2().
>> > It will recursively descend into f1() because it's static. Then it will check
>> > that arguments match for the f3() invocation inside f2(). It will not descend
>> > into f3(). It will finish f2() that has to be successfully verified for all
>> > possible values of 'a'. Then it will proceed with f3(). That function also has
>> > to be safe for all possible values of 'b'. Then it will start subprog 0 (which
>> > is main() function). It will recursively descend into f1() and will skip full
>> > check of f2() and f3(), since they are global. The order of processing global
>> > functions doesn't affect safety, since all global functions must be proven safe
>> > based on their arguments only.
>> >
>> > Such function by function verification can drastically improve speed of the
>> > verification and reduce complexity.
>> >
>> > Note that the stack limit of 512 still applies to the call chain regardless whether
>> > functions were static or global. The nested level of 8 also still applies. The
>> > same recursion prevention checks are in place as well.
>> >
>> > The type information and static/global kind is preserved after the verification
>> > hence in the above example global function f2() and f3() can be replaced later
>> > by equivalent functions with the same types that are loaded and verified later
>> > without affecting safety of this main() program. Such replacement (re-linking)
>> > of global functions is a subject of future patches.
>> >
>> > Signed-off-by: Alexei Starovoitov <ast@kernel.org>
>> 
>> Great to see this progressing; and thanks for breaking things up, makes
>> it much easier to follow along!
>> 
>> One question:
>> 
>> > +enum btf_func_linkage {
>> > +	BTF_FUNC_STATIC = 0,
>> > +	BTF_FUNC_GLOBAL = 1,
>> > +	BTF_FUNC_EXTERN = 2,
>> > +};
>> 
>> What's supposed to happen with FUNC_EXTERN? That is specifically for the
>> re-linking follow-up?
>
> I was thinking to complete the whole thing with re-linking and then send it,
> but llvm 10 feature cut off date is end of this week, so we have to land llvm
> bits asap. I'd like to land patch 1 with libbpf sanitization first before
> landing llvm. llvm release cadence is ~4 month and it would be sad to
> miss it.

Agreed, it would be sad to miss the cutoff!

> Note we will be able to tweak encoding if really necessary after next week.
> (BTF encoding gets fixed in ABI only after full kernel release).
> It's unlikely though. I think the encoding is good. I've played with few
> different variants and this one fits the best. FUNC_EXTERN encoding as 2 is
> kinda obvious when encoding for global vs static is selected. The kernel and
> libbpf will not be using FUNC_EXTERN yet, but llvm is tested to do the right
> thing already, so I think it's fine to add it to btf.h now.

Sure, OK. Don't have any objections (or opinions on the encoding,
really), just want to understand how this all fits together.

> As far as future plans when libbpf sees FUNC_EXTERN it will do the linking the
> way we discussed in the other thread. The kernel will support FUNC_EXTERN when
> we introduce dynamic libraries. A collection of bpf functions will be loaded
> into the kernel first (like libc.so) and later programs will have FUNC_EXTERN
> as part of their BTF to be resolved while loading. The func name to btf_id
> resolution will be done by libbpf. The kernel verifier will do the type
> checking on BTFs.

Right, FUNC_EXTERN will be rejected by the kernel unless it's patched up
with "target" btf_ids by libbpf before load? So it'll be
FUNC_GLOBAL-linked functions that will be replaceable after the fact
with the "dynamic re-linking" feature?

> So the kernel side of FUNC_EXTERN support will be minimal,
> but to your point below...
>
>> This doesn't reject linkage==BTF_FUNC_EXTERN; so for this patch
>> FUNC_EXTERN will be treated the same as FUNC_STATIC (it'll fail the
>> is_global check below)? Or did I miss somewhere else where
>> BTF_FUNC_EXTERN is rejected?
>
> ... is absolutely correct. My bad. Added this bit too soon.
> Will remove. The kernel should accept FUNC_GLOBAL only in this patch set.

Great, thanks!

-Toke

Re: [PATCH bpf-next 3/6] bpf: Introduce function-by-function verification

[Alexei Starovoitov]

On Thu, Jan 09, 2020 at 09:57:50AM +0100, Toke Høiland-Jørgensen wrote:
> 
> > As far as future plans when libbpf sees FUNC_EXTERN it will do the linking the
> > way we discussed in the other thread. The kernel will support FUNC_EXTERN when
> > we introduce dynamic libraries. A collection of bpf functions will be loaded
> > into the kernel first (like libc.so) and later programs will have FUNC_EXTERN
> > as part of their BTF to be resolved while loading. The func name to btf_id
> > resolution will be done by libbpf. The kernel verifier will do the type
> > checking on BTFs.
> 
> Right, FUNC_EXTERN will be rejected by the kernel unless it's patched up
> with "target" btf_ids by libbpf before load? So it'll be
> FUNC_GLOBAL-linked functions that will be replaceable after the fact
> with the "dynamic re-linking" feature?

Right. When libbpf statically links two .o it will need to produce a combined
BTF out of these two .o. That new BTF will not have FUNC_EXTERN anymore if they
are resolved. When the kernel sees FUNC_EXTERN it's a directive for the kernel
to resolve it. BPF program with FUNC_EXTERN references would be loadable, but
not executable. Anyhow the extern work is not immediate. I don't think any of
that is necessary for dynamic re-linking.

Re: [PATCH bpf-next 3/6] bpf: Introduce function-by-function verification

[Toke Høiland-Jørgensen]

Alexei Starovoitov <alexei.starovoitov@gmail.com> writes:

> On Thu, Jan 09, 2020 at 09:57:50AM +0100, Toke Høiland-Jørgensen wrote:
>> 
>> > As far as future plans when libbpf sees FUNC_EXTERN it will do the linking the
>> > way we discussed in the other thread. The kernel will support FUNC_EXTERN when
>> > we introduce dynamic libraries. A collection of bpf functions will be loaded
>> > into the kernel first (like libc.so) and later programs will have FUNC_EXTERN
>> > as part of their BTF to be resolved while loading. The func name to btf_id
>> > resolution will be done by libbpf. The kernel verifier will do the type
>> > checking on BTFs.
>> 
>> Right, FUNC_EXTERN will be rejected by the kernel unless it's patched up
>> with "target" btf_ids by libbpf before load? So it'll be
>> FUNC_GLOBAL-linked functions that will be replaceable after the fact
>> with the "dynamic re-linking" feature?
>
> Right. When libbpf statically links two .o it will need to produce a combined
> BTF out of these two .o. That new BTF will not have FUNC_EXTERN anymore if they
> are resolved. When the kernel sees FUNC_EXTERN it's a directive for the kernel
> to resolve it. BPF program with FUNC_EXTERN references would be loadable, but
> not executable. Anyhow the extern work is not immediate. I don't think any of
> that is necessary for dynamic re-linking.

Right, makes sense. I'll just wait for your follow-up series for the
dynamic re-linking, then. Thanks for the explanation :)

-Toke

Re: [PATCH bpf-next 3/6] bpf: Introduce function-by-function verification

[Song Liu]

> On Jan 7, 2020, at 11:25 PM, Alexei Starovoitov <ast@kernel.org> wrote:
> 
> New llvm and old llvm with libbpf help produce BTF that distinguish global and
> static functions. Unlike arguments of static function the arguments of global
> functions cannot be removed or optimized away by llvm. The compiler has to use
> exactly the arguments specified in a function prototype. The argument type
> information allows the verifier validate each global function independently.
> For now only supported argument types are pointer to context and scalars. In
> the future pointers to structures, sizes, pointer to packet data can be
> supported as well. Consider the following example:

[...]

> The type information and static/global kind is preserved after the verification
> hence in the above example global function f2() and f3() can be replaced later
> by equivalent functions with the same types that are loaded and verified later
> without affecting safety of this main() program. Such replacement (re-linking)
> of global functions is a subject of future patches.
> 
> Signed-off-by: Alexei Starovoitov <ast@kernel.org>
> ---
> include/linux/bpf.h          |   7 +-
> include/linux/bpf_verifier.h |   7 +-
> include/uapi/linux/btf.h     |   6 +
> kernel/bpf/btf.c             | 147 +++++++++++++++++-----
> kernel/bpf/verifier.c        | 228 +++++++++++++++++++++++++++--------
> 5 files changed, 317 insertions(+), 78 deletions(-)
> 
> diff --git a/include/linux/bpf.h b/include/linux/bpf.h
> index b14e51d56a82..ceb5b6c13abc 100644
> --- a/include/linux/bpf.h
> +++ b/include/linux/bpf.h
> @@ -558,6 +558,7 @@ static inline void bpf_dispatcher_change_prog(struct bpf_dispatcher *d,
> #endif
> 
> struct bpf_func_info_aux {
> +	u32 linkage;

How about we use u16 or even u8 for linkage? We are using BTF_INFO_VLEN() which 
is 16-bit long. Maybe we should save some bits for future extensions?

> 	bool unreliable;
> };
> 
> @@ -1006,7 +1007,11 @@ int btf_distill_func_proto(struct bpf_verifier_log *log,
> 			   const char *func_name,
> 			   struct btf_func_model *m);
> 
> -int btf_check_func_arg_match(struct bpf_verifier_env *env, int subprog);
> +struct bpf_reg_state;
> +int btf_check_func_arg_match(struct bpf_verifier_env *env, int subprog,
> +			     struct bpf_reg_state *regs);
> +int btf_prepare_func_args(struct bpf_verifier_env *env, int subprog,
> +			  struct bpf_reg_state *reg);
> 
> struct bpf_prog *bpf_prog_by_id(u32 id);
> 
[...]

> @@ -3535,11 +3537,12 @@ btf_get_prog_ctx_type(struct bpf_verifier_log *log, struct btf *btf,
> static int btf_translate_to_vmlinux(struct bpf_verifier_log *log,
> 				     struct btf *btf,
> 				     const struct btf_type *t,
> -				     enum bpf_prog_type prog_type)
> +				     enum bpf_prog_type prog_type,
> +				     int arg)
> {
> 	const struct btf_member *prog_ctx_type, *kern_ctx_type;
> 
> -	prog_ctx_type = btf_get_prog_ctx_type(log, btf, t, prog_type);
> +	prog_ctx_type = btf_get_prog_ctx_type(log, btf, t, prog_type, arg);
> 	if (!prog_ctx_type)
> 		return -ENOENT;
> 	kern_ctx_type = prog_ctx_type + 1;
> @@ -3700,7 +3703,7 @@ bool btf_ctx_access(int off, int size, enum bpf_access_type type,
> 	info->btf_id = t->type;
> 
> 	if (tgt_prog) {
> -		ret = btf_translate_to_vmlinux(log, btf, t, tgt_prog->type);
> +		ret = btf_translate_to_vmlinux(log, btf, t, tgt_prog->type, arg);
> 		if (ret > 0) {
> 			info->btf_id = ret;
> 			return true;
> @@ -4043,11 +4046,10 @@ int btf_distill_func_proto(struct bpf_verifier_log *log,
> 	return 0;
> }
> 
> -int btf_check_func_arg_match(struct bpf_verifier_env *env, int subprog)
> +/* Compare BTF of a function with given bpf_reg_state */
> +int btf_check_func_arg_match(struct bpf_verifier_env *env, int subprog,
> +			     struct bpf_reg_state *reg)

I think we need more comments for the retval of btf_check_func_arg_match().

> {
> -	struct bpf_verifier_state *st = env->cur_state;
> -	struct bpf_func_state *func = st->frame[st->curframe];
> -	struct bpf_reg_state *reg = func->regs;
> 	struct bpf_verifier_log *log = &env->log;
> 	struct bpf_prog *prog = env->prog;
> 	struct btf *btf = prog->aux->btf;
[...]
> +
> +/* Convert BTF of a function into bpf_reg_state if possible */
> +int btf_prepare_func_args(struct bpf_verifier_env *env, int subprog,
> +			  struct bpf_reg_state *reg)
> +{
> +	struct bpf_verifier_log *log = &env->log;
> +	struct bpf_prog *prog = env->prog;
> +	struct btf *btf = prog->aux->btf;
> +	const struct btf_param *args;
> +	const struct btf_type *t;
> +	u32 i, nargs, btf_id;
> +	const char *tname;
> +
> +	if (!prog->aux->func_info ||
> +	    prog->aux->func_info_aux[subprog].linkage != BTF_FUNC_GLOBAL) {
> +		bpf_log(log, "Verifier bug\n");

IIUC, this should never happen? Maybe we need more details in the log, and 
maybe also WARN_ONCE()?

> +		return -EFAULT;
> +	}
> +
> +	btf_id = prog->aux->func_info[subprog].type_id;
> +	if (!btf_id) {
> +		bpf_log(log, "Global functions need valid BTF\n");
> +		return -EINVAL;
> +	}
> +
> +	t = btf_type_by_id(btf, btf_id);
> +	if (!t || !btf_type_is_func(t)) {
> +		bpf_log(log, "BTF of func#%d doesn't point to KIND_FUNC\n",
> +			subprog);
> +		return -EINVAL;
> +	}
> +	tname = btf_name_by_offset(btf, t->name_off);
> +
> +	if (log->level & BPF_LOG_LEVEL)
> +		bpf_log(log, "Validating %s() func#%d...\n",
> +			tname, subprog);
> +
> +	if (prog->aux->func_info_aux[subprog].unreliable) {
> +		bpf_log(log, "Verifier bug in function %s()\n", tname);
> +		return -EFAULT;

Why -EFAULT instead of -EINVAL? I think we treat them the same? 
I guess this to highlight verifier bug vs. libbpf/llvm bug? How about 
we use WARN_ONCE() for all verifier bug?

> +	}
> +
> +	t = btf_type_by_id(btf, t->type);
> +	if (!t || !btf_type_is_func_proto(t)) {
> +		bpf_log(log, "Invalid type of function %s()\n", tname);
> +		return -EINVAL;
> +	}
> +	args = (const struct btf_param *)(t + 1);
> +	nargs = btf_type_vlen(t);
> +	if (nargs > 5) {
> +		bpf_log(log, "Global function %s() with %d > 5 args. Buggy llvm.\n",
> +			tname, nargs);
> +		return -EINVAL;
> +	}
> +	/* check that function returns int */
> +	t = btf_type_by_id(btf, t->type);
> +	while (btf_type_is_modifier(t))
> +		t = btf_type_by_id(btf, t->type);
> +	if (!btf_type_is_int(t) && !btf_type_is_enum(t)) {
> +		bpf_log(log,
> +			"Global function %s() doesn't return scalar. Only those are supported.\n",
> +			tname);
> +		return -EINVAL;
> +	}
> +	/* Convert BTF function arguments into verifier types.
> +	 * Only PTR_TO_CTX and SCALAR are supported atm.
> +	 */
> +	for (i = 0; i < nargs; i++) {
> +		t = btf_type_by_id(btf, args[i].type);
> +		while (btf_type_is_modifier(t))
> +			t = btf_type_by_id(btf, t->type);
> +		if (btf_type_is_int(t) || btf_type_is_enum(t)) {
> +			reg[i + 1].type = SCALAR_VALUE;
> +			continue;
> +		}
> +		if (btf_type_is_ptr(t) &&
> +		    btf_get_prog_ctx_type(log, btf, t, prog->type, i)) {
> +			reg[i + 1].type = PTR_TO_CTX;
> +			continue;
> +		}
> +		bpf_log(log, "Arg#%d type %s in %s() is not supported yet.\n",
> +			i, btf_kind_str[BTF_INFO_KIND(t->info)], tname);
> +		return -EINVAL;
> +	}
> 	return 0;
> }
[...]

Re: [PATCH bpf-next 3/6] bpf: Introduce function-by-function verification

[Alexei Starovoitov]

On Wed, Jan 08, 2020 at 07:10:59PM +0000, Song Liu wrote:
> 
> 
> > On Jan 7, 2020, at 11:25 PM, Alexei Starovoitov <ast@kernel.org> wrote:
> > 
> > New llvm and old llvm with libbpf help produce BTF that distinguish global and
> > static functions. Unlike arguments of static function the arguments of global
> > functions cannot be removed or optimized away by llvm. The compiler has to use
> > exactly the arguments specified in a function prototype. The argument type
> > information allows the verifier validate each global function independently.
> > For now only supported argument types are pointer to context and scalars. In
> > the future pointers to structures, sizes, pointer to packet data can be
> > supported as well. Consider the following example:
> 
> [...]
> 
> > The type information and static/global kind is preserved after the verification
> > hence in the above example global function f2() and f3() can be replaced later
> > by equivalent functions with the same types that are loaded and verified later
> > without affecting safety of this main() program. Such replacement (re-linking)
> > of global functions is a subject of future patches.
> > 
> > Signed-off-by: Alexei Starovoitov <ast@kernel.org>
> > ---
> > include/linux/bpf.h          |   7 +-
> > include/linux/bpf_verifier.h |   7 +-
> > include/uapi/linux/btf.h     |   6 +
> > kernel/bpf/btf.c             | 147 +++++++++++++++++-----
> > kernel/bpf/verifier.c        | 228 +++++++++++++++++++++++++++--------
> > 5 files changed, 317 insertions(+), 78 deletions(-)
> > 
> > diff --git a/include/linux/bpf.h b/include/linux/bpf.h
> > index b14e51d56a82..ceb5b6c13abc 100644
> > --- a/include/linux/bpf.h
> > +++ b/include/linux/bpf.h
> > @@ -558,6 +558,7 @@ static inline void bpf_dispatcher_change_prog(struct bpf_dispatcher *d,
> > #endif
> > 
> > struct bpf_func_info_aux {
> > +	u32 linkage;
> 
> How about we use u16 or even u8 for linkage? We are using BTF_INFO_VLEN() which 
> is 16-bit long. Maybe we should save some bits for future extensions?

sure. u16 is fine.
Will also introduce btf_func_kind() helper to avoid misleading BTF_INFO_VLEN macro.

> > -int btf_check_func_arg_match(struct bpf_verifier_env *env, int subprog)
> > +/* Compare BTF of a function with given bpf_reg_state */
> > +int btf_check_func_arg_match(struct bpf_verifier_env *env, int subprog,
> > +			     struct bpf_reg_state *reg)
> 
> I think we need more comments for the retval of btf_check_func_arg_match().

sure.

> > {
> > -	struct bpf_verifier_state *st = env->cur_state;
> > -	struct bpf_func_state *func = st->frame[st->curframe];
> > -	struct bpf_reg_state *reg = func->regs;
> > 	struct bpf_verifier_log *log = &env->log;
> > 	struct bpf_prog *prog = env->prog;
> > 	struct btf *btf = prog->aux->btf;
> [...]
> > +
> > +/* Convert BTF of a function into bpf_reg_state if possible */
> > +int btf_prepare_func_args(struct bpf_verifier_env *env, int subprog,
> > +			  struct bpf_reg_state *reg)
> > +{
> > +	struct bpf_verifier_log *log = &env->log;
> > +	struct bpf_prog *prog = env->prog;
> > +	struct btf *btf = prog->aux->btf;
> > +	const struct btf_param *args;
> > +	const struct btf_type *t;
> > +	u32 i, nargs, btf_id;
> > +	const char *tname;
> > +
> > +	if (!prog->aux->func_info ||
> > +	    prog->aux->func_info_aux[subprog].linkage != BTF_FUNC_GLOBAL) {
> > +		bpf_log(log, "Verifier bug\n");
> 
> IIUC, this should never happen? Maybe we need more details in the log, and 
> maybe also WARN_ONCE()?

Should never happen and I think it's pretty clear from the diff, since
this function is called after == FUNC_GLOBAL check in the caller.
I didn't add WARN to avoid wasting .text even more here.
Single 'if' above already feels a bit overly defensive.
It's not like other cases in the verifier where we have WARN_ONCE.
Those are for complex things. Here it's one callsite and trivial control flow.

> > +	if (prog->aux->func_info_aux[subprog].unreliable) {
> > +		bpf_log(log, "Verifier bug in function %s()\n", tname);
> > +		return -EFAULT;
> 
> Why -EFAULT instead of -EINVAL? I think we treat them the same? 

EFAULT is a verifier bug like in all other places in the verifier
where EFAULT is returned. EINVAL is normal error.

Re: [PATCH bpf-next 3/6] bpf: Introduce function-by-function verification

[Song Liu]

> On Jan 8, 2020, at 12:20 PM, Alexei Starovoitov <alexei.starovoitov@gmail.com> wrote:
> 
> On Wed, Jan 08, 2020 at 07:10:59PM +0000, Song Liu wrote:
>> 
>> 
>>> On Jan 7, 2020, at 11:25 PM, Alexei Starovoitov <ast@kernel.org> wrote:
>>> 
>>> New llvm and old llvm with libbpf help produce BTF that distinguish global and
>>> static functions. Unlike arguments of static function the arguments of global
>>> functions cannot be removed or optimized away by llvm. The compiler has to use
>>> exactly the arguments specified in a function prototype. The argument type
>>> information allows the verifier validate each global function independently.
>>> For now only supported argument types are pointer to context and scalars. In
>>> the future pointers to structures, sizes, pointer to packet data can be
>>> supported as well. Consider the following example:
>> 
>> [...]
>> 
>>> The type information and static/global kind is preserved after the verification
>>> hence in the above example global function f2() and f3() can be replaced later
>>> by equivalent functions with the same types that are loaded and verified later
>>> without affecting safety of this main() program. Such replacement (re-linking)
>>> of global functions is a subject of future patches.
>>> 
>>> Signed-off-by: Alexei Starovoitov <ast@kernel.org>
>>> ---
>>> include/linux/bpf.h          |   7 +-
>>> include/linux/bpf_verifier.h |   7 +-
>>> include/uapi/linux/btf.h     |   6 +
>>> kernel/bpf/btf.c             | 147 +++++++++++++++++-----
>>> kernel/bpf/verifier.c        | 228 +++++++++++++++++++++++++++--------
>>> 5 files changed, 317 insertions(+), 78 deletions(-)
>>> 
>>> diff --git a/include/linux/bpf.h b/include/linux/bpf.h
>>> index b14e51d56a82..ceb5b6c13abc 100644
>>> --- a/include/linux/bpf.h
>>> +++ b/include/linux/bpf.h
>>> @@ -558,6 +558,7 @@ static inline void bpf_dispatcher_change_prog(struct bpf_dispatcher *d,
>>> #endif
>>> 
>>> struct bpf_func_info_aux {
>>> +	u32 linkage;
>> 
>> How about we use u16 or even u8 for linkage? We are using BTF_INFO_VLEN() which 
>> is 16-bit long. Maybe we should save some bits for future extensions?
> 
> sure. u16 is fine.
> Will also introduce btf_func_kind() helper to avoid misleading BTF_INFO_VLEN macro.
> 
>>> -int btf_check_func_arg_match(struct bpf_verifier_env *env, int subprog)
>>> +/* Compare BTF of a function with given bpf_reg_state */
>>> +int btf_check_func_arg_match(struct bpf_verifier_env *env, int subprog,
>>> +			     struct bpf_reg_state *reg)
>> 
>> I think we need more comments for the retval of btf_check_func_arg_match().
> 
> sure.
> 
>>> {
>>> -	struct bpf_verifier_state *st = env->cur_state;
>>> -	struct bpf_func_state *func = st->frame[st->curframe];
>>> -	struct bpf_reg_state *reg = func->regs;
>>> 	struct bpf_verifier_log *log = &env->log;
>>> 	struct bpf_prog *prog = env->prog;
>>> 	struct btf *btf = prog->aux->btf;
>> [...]
>>> +
>>> +/* Convert BTF of a function into bpf_reg_state if possible */
>>> +int btf_prepare_func_args(struct bpf_verifier_env *env, int subprog,
>>> +			  struct bpf_reg_state *reg)
>>> +{
>>> +	struct bpf_verifier_log *log = &env->log;
>>> +	struct bpf_prog *prog = env->prog;
>>> +	struct btf *btf = prog->aux->btf;
>>> +	const struct btf_param *args;
>>> +	const struct btf_type *t;
>>> +	u32 i, nargs, btf_id;
>>> +	const char *tname;
>>> +
>>> +	if (!prog->aux->func_info ||
>>> +	    prog->aux->func_info_aux[subprog].linkage != BTF_FUNC_GLOBAL) {
>>> +		bpf_log(log, "Verifier bug\n");
>> 
>> IIUC, this should never happen? Maybe we need more details in the log, and 
>> maybe also WARN_ONCE()?
> 
> Should never happen and I think it's pretty clear from the diff, since
> this function is called after == FUNC_GLOBAL check in the caller.
> I didn't add WARN to avoid wasting .text even more here.
> Single 'if' above already feels a bit overly defensive.
> It's not like other cases in the verifier where we have WARN_ONCE.
> Those are for complex things. Here it's one callsite and trivial control flow.

Agreed. Current check is good enough. 

> 
>>> +	if (prog->aux->func_info_aux[subprog].unreliable) {
>>> +		bpf_log(log, "Verifier bug in function %s()\n", tname);
>>> +		return -EFAULT;
>> 
>> Why -EFAULT instead of -EINVAL? I think we treat them the same? 
> 
> EFAULT is a verifier bug like in all other places in the verifier
> where EFAULT is returned. EINVAL is normal error.

Thanks for the explanation. 

Song

Re: [PATCH bpf-next 3/6] bpf: Introduce function-by-function verification

[Alexei Starovoitov]

On Tue, Jan 7, 2020 at 11:27 PM Alexei Starovoitov <ast@kernel.org> wrote:
> +       if (subprog) {
> +               ret = btf_prepare_func_args(env, subprog, regs);
> +               if (ret)
> +                       return ret;

noticed a memory leak here.
Will respin with all comments addressed soon.

Re: [PATCH bpf-next 3/6] bpf: Introduce function-by-function verification

[Stanislav Fomichev]

On 01/07, Alexei Starovoitov wrote:
> New llvm and old llvm with libbpf help produce BTF that distinguish global and
> static functions. Unlike arguments of static function the arguments of global
> functions cannot be removed or optimized away by llvm. The compiler has to use
> exactly the arguments specified in a function prototype. The argument type
> information allows the verifier validate each global function independently.
> For now only supported argument types are pointer to context and scalars. In
> the future pointers to structures, sizes, pointer to packet data can be
> supported as well. Consider the following example:
> --- a/kernel/bpf/btf.c
> +++ b/kernel/bpf/btf.c
> @@ -2621,8 +2621,8 @@ static s32 btf_func_check_meta(struct btf_verifier_env *env,
>  		return -EINVAL;
>  	}
>  
> -	if (btf_type_vlen(t)) {
> -		btf_verifier_log_type(env, t, "vlen != 0");
> +	if (btf_type_vlen(t) > BTF_FUNC_EXTERN) {
> +		btf_verifier_log_type(env, t, "invalid func linkage");
>  		return -EINVAL;
Sorry for bringing it up after the review:

This effectively teaches kernel about BTF_KIND_FUNC scope argument,
right? Which means, if I take clang from the tip
(https://github.com/llvm/llvm-project/commit/fbb64aa69835c8e3e9efe0afc8a73058b5a0fb3c#diff-f191c05d1eb0a6ca0e89d7e7938d73d4)
and take 5.4 kernel, it will reject BTF because it now has a
BTF_KIND_FUNC with global scope (any 'main' function is global and has
non-zero vlen).

What's the general guidance on the situation where clang starts
spitting out some BTF and released kernels reject it? Is there some list of
flags I can pass to clang to not emit some of the BTF features?
Or am I missing something?

Re: [PATCH bpf-next 3/6] bpf: Introduce function-by-function verification

[Andrii Nakryiko]

On Tue, Jan 14, 2020 at 3:39 PM Stanislav Fomichev <sdf@fomichev.me> wrote:
>
> On 01/07, Alexei Starovoitov wrote:
> > New llvm and old llvm with libbpf help produce BTF that distinguish global and
> > static functions. Unlike arguments of static function the arguments of global
> > functions cannot be removed or optimized away by llvm. The compiler has to use
> > exactly the arguments specified in a function prototype. The argument type
> > information allows the verifier validate each global function independently.
> > For now only supported argument types are pointer to context and scalars. In
> > the future pointers to structures, sizes, pointer to packet data can be
> > supported as well. Consider the following example:
> > --- a/kernel/bpf/btf.c
> > +++ b/kernel/bpf/btf.c
> > @@ -2621,8 +2621,8 @@ static s32 btf_func_check_meta(struct btf_verifier_env *env,
> >               return -EINVAL;
> >       }
> >
> > -     if (btf_type_vlen(t)) {
> > -             btf_verifier_log_type(env, t, "vlen != 0");
> > +     if (btf_type_vlen(t) > BTF_FUNC_EXTERN) {
> > +             btf_verifier_log_type(env, t, "invalid func linkage");
> >               return -EINVAL;
> Sorry for bringing it up after the review:
>
> This effectively teaches kernel about BTF_KIND_FUNC scope argument,
> right? Which means, if I take clang from the tip
> (https://github.com/llvm/llvm-project/commit/fbb64aa69835c8e3e9efe0afc8a73058b5a0fb3c#diff-f191c05d1eb0a6ca0e89d7e7938d73d4)
> and take 5.4 kernel, it will reject BTF because it now has a
> BTF_KIND_FUNC with global scope (any 'main' function is global and has
> non-zero vlen).
>
> What's the general guidance on the situation where clang starts
> spitting out some BTF and released kernels reject it? Is there some list of
> flags I can pass to clang to not emit some of the BTF features?
> Or am I missing something?

Isn't that the issue that 2d3eb67f64ec ("libbpf: Sanitize global
functions") addresses by sanitizing those BTF_KIND_FUNC as static
functions (with vlen=0)?

The general guidance is to have libbpf sanitize such BTF to make it
compatible with old kernels.

Re: [PATCH bpf-next 3/6] bpf: Introduce function-by-function verification

[Stanislav Fomichev]

On 01/14, Andrii Nakryiko wrote:
> On Tue, Jan 14, 2020 at 3:39 PM Stanislav Fomichev <sdf@fomichev.me> wrote:
> >
> > On 01/07, Alexei Starovoitov wrote:
> > > New llvm and old llvm with libbpf help produce BTF that distinguish global and
> > > static functions. Unlike arguments of static function the arguments of global
> > > functions cannot be removed or optimized away by llvm. The compiler has to use
> > > exactly the arguments specified in a function prototype. The argument type
> > > information allows the verifier validate each global function independently.
> > > For now only supported argument types are pointer to context and scalars. In
> > > the future pointers to structures, sizes, pointer to packet data can be
> > > supported as well. Consider the following example:
> > > --- a/kernel/bpf/btf.c
> > > +++ b/kernel/bpf/btf.c
> > > @@ -2621,8 +2621,8 @@ static s32 btf_func_check_meta(struct btf_verifier_env *env,
> > >               return -EINVAL;
> > >       }
> > >
> > > -     if (btf_type_vlen(t)) {
> > > -             btf_verifier_log_type(env, t, "vlen != 0");
> > > +     if (btf_type_vlen(t) > BTF_FUNC_EXTERN) {
> > > +             btf_verifier_log_type(env, t, "invalid func linkage");
> > >               return -EINVAL;
> > Sorry for bringing it up after the review:
> >
> > This effectively teaches kernel about BTF_KIND_FUNC scope argument,
> > right? Which means, if I take clang from the tip
> > (https://github.com/llvm/llvm-project/commit/fbb64aa69835c8e3e9efe0afc8a73058b5a0fb3c#diff-f191c05d1eb0a6ca0e89d7e7938d73d4)
> > and take 5.4 kernel, it will reject BTF because it now has a
> > BTF_KIND_FUNC with global scope (any 'main' function is global and has
> > non-zero vlen).
> >
> > What's the general guidance on the situation where clang starts
> > spitting out some BTF and released kernels reject it? Is there some list of
> > flags I can pass to clang to not emit some of the BTF features?
> > Or am I missing something?
> 
> Isn't that the issue that 2d3eb67f64ec ("libbpf: Sanitize global
> functions") addresses by sanitizing those BTF_KIND_FUNC as static
> functions (with vlen=0)?
> 
> The general guidance is to have libbpf sanitize such BTF to make it
> compatible with old kernels.
Ah, that was the missing piece, thank you!

[PATCH bpf-next 4/6] selftests/bpf: Add fexit-to-skb test for global funcs

[Alexei Starovoitov]

Add simple fexit prog type to skb prog type test when subprogram is a global
function.

Signed-off-by: Alexei Starovoitov <ast@kernel.org>
---
 .../selftests/bpf/prog_tests/fexit_bpf2bpf.c  |  1 +
 .../selftests/bpf/progs/fexit_bpf2bpf.c       | 15 ++++++++++
 .../selftests/bpf/progs/test_pkt_access.c     | 28 +++++++++++++++++++
 3 files changed, 44 insertions(+)

diff --git a/tools/testing/selftests/bpf/prog_tests/fexit_bpf2bpf.c b/tools/testing/selftests/bpf/prog_tests/fexit_bpf2bpf.c
index b426bf2f97e4..7d3740d38965 100644
--- a/tools/testing/selftests/bpf/prog_tests/fexit_bpf2bpf.c
+++ b/tools/testing/selftests/bpf/prog_tests/fexit_bpf2bpf.c
@@ -98,6 +98,7 @@ static void test_target_yes_callees(void)
 		"fexit/test_pkt_access",
 		"fexit/test_pkt_access_subprog1",
 		"fexit/test_pkt_access_subprog2",
+		"fexit/test_pkt_access_subprog3",
 	};
 	test_fexit_bpf2bpf_common("./fexit_bpf2bpf.o",
 				  "./test_pkt_access.o",
diff --git a/tools/testing/selftests/bpf/progs/fexit_bpf2bpf.c b/tools/testing/selftests/bpf/progs/fexit_bpf2bpf.c
index 2d211ee98a1c..81d7b4aaf79e 100644
--- a/tools/testing/selftests/bpf/progs/fexit_bpf2bpf.c
+++ b/tools/testing/selftests/bpf/progs/fexit_bpf2bpf.c
@@ -79,4 +79,19 @@ int test_subprog2(struct args_subprog2 *ctx)
 	test_result_subprog2 = 1;
 	return 0;
 }
+
+__u64 test_result_subprog3 = 0;
+BPF_TRACE_3("fexit/test_pkt_access_subprog3", test_subprog3,
+	    int, val, struct sk_buff *, skb, int, ret)
+{
+	int len;
+
+	__builtin_preserve_access_index(({
+		len = skb->len;
+	}));
+	if (len != 74 || ret != 74 * val || val != 3)
+		return 0;
+	test_result_subprog3 = 1;
+	return 0;
+}
 char _license[] SEC("license") = "GPL";
diff --git a/tools/testing/selftests/bpf/progs/test_pkt_access.c b/tools/testing/selftests/bpf/progs/test_pkt_access.c
index 3a7b4b607ed3..b77cebf71e66 100644
--- a/tools/testing/selftests/bpf/progs/test_pkt_access.c
+++ b/tools/testing/selftests/bpf/progs/test_pkt_access.c
@@ -47,6 +47,32 @@ int test_pkt_access_subprog2(int val, volatile struct __sk_buff *skb)
 	return skb->len * val;
 }
 
+#define MAX_STACK (512 - 2 * 32)
+
+__attribute__ ((noinline))
+int get_skb_len(struct __sk_buff *skb)
+{
+	volatile char buf[MAX_STACK] = {};
+
+	return skb->len;
+}
+
+int get_skb_ifindex(int, struct __sk_buff *skb, int);
+
+__attribute__ ((noinline))
+int test_pkt_access_subprog3(int val, struct __sk_buff *skb)
+{
+	return get_skb_len(skb) * get_skb_ifindex(val, skb, 1);
+}
+
+__attribute__ ((noinline))
+int get_skb_ifindex(int val, struct __sk_buff *skb, int var)
+{
+	volatile char buf[MAX_STACK] = {};
+
+	return skb->ifindex * val * var;
+}
+
 SEC("classifier/test_pkt_access")
 int test_pkt_access(struct __sk_buff *skb)
 {
@@ -82,6 +108,8 @@ int test_pkt_access(struct __sk_buff *skb)
 		return TC_ACT_SHOT;
 	if (test_pkt_access_subprog2(2, skb) != skb->len * 2)
 		return TC_ACT_SHOT;
+	if (test_pkt_access_subprog3(3, skb) != skb->len * 3 * skb->ifindex)
+		return TC_ACT_SHOT;
 	if (tcp) {
 		if (((void *)(tcp) + 20) > data_end || proto != 6)
 			return TC_ACT_SHOT;
-- 
2.23.0

Re: [PATCH bpf-next 4/6] selftests/bpf: Add fexit-to-skb test for global funcs

[Song Liu]

> On Jan 7, 2020, at 11:25 PM, Alexei Starovoitov <ast@kernel.org> wrote:
> 
> Add simple fexit prog type to skb prog type test when subprogram is a global
> function.
> 
> Signed-off-by: Alexei Starovoitov <ast@kernel.org>

Acked-by: Song Liu <songliubraving@fb.com>

[PATCH bpf-next 5/6] selftests/bpf: Add a test for a large global function

[Alexei Starovoitov]

test results:
pyperf50 with always_inlined the same function five times: processed 46378 insns
pyperf50 with global function: processed 6102 insns

Signed-off-by: Alexei Starovoitov <ast@kernel.org>
---
 tools/testing/selftests/bpf/prog_tests/bpf_verif_scale.c | 2 ++
 tools/testing/selftests/bpf/progs/pyperf.h               | 9 +++++++--
 tools/testing/selftests/bpf/progs/pyperf_global.c        | 5 +++++
 3 files changed, 14 insertions(+), 2 deletions(-)
 create mode 100644 tools/testing/selftests/bpf/progs/pyperf_global.c

diff --git a/tools/testing/selftests/bpf/prog_tests/bpf_verif_scale.c b/tools/testing/selftests/bpf/prog_tests/bpf_verif_scale.c
index 9486c13af6b2..e9f2f12ba06b 100644
--- a/tools/testing/selftests/bpf/prog_tests/bpf_verif_scale.c
+++ b/tools/testing/selftests/bpf/prog_tests/bpf_verif_scale.c
@@ -48,6 +48,8 @@ void test_bpf_verif_scale(void)
 		{ "test_verif_scale2.o", BPF_PROG_TYPE_SCHED_CLS },
 		{ "test_verif_scale3.o", BPF_PROG_TYPE_SCHED_CLS },
 
+		{ "pyperf_global.o", BPF_PROG_TYPE_RAW_TRACEPOINT },
+
 		/* full unroll by llvm */
 		{ "pyperf50.o", BPF_PROG_TYPE_RAW_TRACEPOINT },
 		{ "pyperf100.o", BPF_PROG_TYPE_RAW_TRACEPOINT },
diff --git a/tools/testing/selftests/bpf/progs/pyperf.h b/tools/testing/selftests/bpf/progs/pyperf.h
index 71d383cc9b85..e186899954e9 100644
--- a/tools/testing/selftests/bpf/progs/pyperf.h
+++ b/tools/testing/selftests/bpf/progs/pyperf.h
@@ -154,7 +154,12 @@ struct {
 	__uint(value_size, sizeof(long long) * 127);
 } stackmap SEC(".maps");
 
-static __always_inline int __on_event(struct pt_regs *ctx)
+#ifdef GLOBAL_FUNC
+__attribute__((noinline))
+#else
+static __always_inline
+#endif
+int __on_event(struct bpf_raw_tracepoint_args *ctx)
 {
 	uint64_t pid_tgid = bpf_get_current_pid_tgid();
 	pid_t pid = (pid_t)(pid_tgid >> 32);
@@ -254,7 +259,7 @@ static __always_inline int __on_event(struct pt_regs *ctx)
 }
 
 SEC("raw_tracepoint/kfree_skb")
-int on_event(struct pt_regs* ctx)
+int on_event(struct bpf_raw_tracepoint_args* ctx)
 {
 	int i, ret = 0;
 	ret |= __on_event(ctx);
diff --git a/tools/testing/selftests/bpf/progs/pyperf_global.c b/tools/testing/selftests/bpf/progs/pyperf_global.c
new file mode 100644
index 000000000000..079e78a7562b
--- /dev/null
+++ b/tools/testing/selftests/bpf/progs/pyperf_global.c
@@ -0,0 +1,5 @@
+// SPDX-License-Identifier: GPL-2.0
+/* Copyright (c) 2020 Facebook */
+#define STACK_MAX_LEN 50
+#define GLOBAL_FUNC
+#include "pyperf.h"
-- 
2.23.0

Re: [PATCH bpf-next 5/6] selftests/bpf: Add a test for a large global function

[Song Liu]

> On Jan 7, 2020, at 11:25 PM, Alexei Starovoitov <ast@kernel.org> wrote:
> 
> test results:
> pyperf50 with always_inlined the same function five times: processed 46378 insns
> pyperf50 with global function: processed 6102 insns
> 
> Signed-off-by: Alexei Starovoitov <ast@kernel.org>

Acked-by: Song Liu <songliubraving@fb.com>

Re: [PATCH bpf-next 5/6] selftests/bpf: Add a test for a large global function

[Song Liu]

> On Jan 8, 2020, at 11:16 AM, Song Liu <songliubraving@fb.com> wrote:
> 
> 
> 
>> On Jan 7, 2020, at 11:25 PM, Alexei Starovoitov <ast@kernel.org> wrote:
>> 
>> test results:
>> pyperf50 with always_inlined the same function five times: processed 46378 insns
>> pyperf50 with global function: processed 6102 insns

This is awesome!

>> 
>> Signed-off-by: Alexei Starovoitov <ast@kernel.org>
> 
> Acked-by: Song Liu <songliubraving@fb.com>

[PATCH bpf-next 6/6] selftests/bpf: Modify a test to check global functions

[Alexei Starovoitov]

Make two static functions in test_xdp_noinline.c global:
before: processed 2790 insns
after: processed 2598 insns

Signed-off-by: Alexei Starovoitov <ast@kernel.org>
---
 tools/testing/selftests/bpf/progs/test_xdp_noinline.c | 4 ++--
 1 file changed, 2 insertions(+), 2 deletions(-)

diff --git a/tools/testing/selftests/bpf/progs/test_xdp_noinline.c b/tools/testing/selftests/bpf/progs/test_xdp_noinline.c
index e88d7b9d65ab..f95bc1a17667 100644
--- a/tools/testing/selftests/bpf/progs/test_xdp_noinline.c
+++ b/tools/testing/selftests/bpf/progs/test_xdp_noinline.c
@@ -86,7 +86,7 @@ u32 jhash(const void *key, u32 length, u32 initval)
 	return c;
 }
 
-static __attribute__ ((noinline))
+__attribute__ ((noinline))
 u32 __jhash_nwords(u32 a, u32 b, u32 c, u32 initval)
 {
 	a += initval;
@@ -96,7 +96,7 @@ u32 __jhash_nwords(u32 a, u32 b, u32 c, u32 initval)
 	return c;
 }
 
-static __attribute__ ((noinline))
+__attribute__ ((noinline))
 u32 jhash_2words(u32 a, u32 b, u32 initval)
 {
 	return __jhash_nwords(a, b, 0, initval + JHASH_INITVAL + (2 << 2));
-- 
2.23.0

Re: [PATCH bpf-next 6/6] selftests/bpf: Modify a test to check global functions

[Song Liu]

> On Jan 7, 2020, at 11:25 PM, Alexei Starovoitov <ast@kernel.org> wrote:
> 
> Make two static functions in test_xdp_noinline.c global:
> before: processed 2790 insns
> after: processed 2598 insns
> 
> Signed-off-by: Alexei Starovoitov <ast@kernel.org>

Acked-by: Song Liu <songliubraving@fb.com>