netdev - Re: [PATCH bpf-next 4/5] btf: fix bug with resolving STRUCT/UNION into corresponding FWD

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-ID: <797b56c0-2178-a0b1-3070-721c2fd4d38c@fb.com>
Date:   Thu, 28 Feb 2019 18:18:32 +0000
From:   Yonghong Song <yhs@...com>
To:     Andrii Nakryiko <andriin@...com>,
        "andrii.nakryiko@...il.com" <andrii.nakryiko@...il.com>,
        Kernel Team <Kernel-team@...com>,
        "Alexei Starovoitov" <ast@...com>,
        "acme@...nel.org" <acme@...nel.org>,
        "netdev@...r.kernel.org" <netdev@...r.kernel.org>,
        "bpf@...r.kernel.org" <bpf@...r.kernel.org>,
        "daniel@...earbox.net" <daniel@...earbox.net>
Subject: Re: [PATCH bpf-next 4/5] btf: fix bug with resolving STRUCT/UNION
 into corresponding FWD



On 2/27/19 2:46 PM, Andrii Nakryiko wrote:
> When checking available canonical candidates for struct/union algorithm
> utilizes btf_dedup_is_equiv to determine if candidate is suitable. This
> check is not enough when candidate is corresponding FWD for that
> struct/union, because according to equivalence logic they are
> equivalent. When it so happens that FWD and STRUCT/UNION end in hashing
> to the same bucket, it's possible to create remapping loop from FWD to
> STRUCT and STRUCT to same FWD, which will cause btf_dedup() to loop
> forever.
> 
> This patch fixes the issue by additionally checking that type and
> canonical candidate are strictly equal (utilizing btf_equal_struct).

It looks like btf_equal_struct() checking equality except
member type id's. Maybe calling it btf_almost_equal_struct() or 
something like that?

> 
> Fixes: d5caef5b5655 ("btf: add BTF types deduplication algorithm")
> Reported-by: Arnaldo Carvalho de Melo <acme@...hat.com>
> Signed-off-by: Andrii Nakryiko <andriin@...com>
> ---
>   tools/lib/bpf/btf.c | 6 +++++-
>   1 file changed, 5 insertions(+), 1 deletion(-)
> 
> diff --git a/tools/lib/bpf/btf.c b/tools/lib/bpf/btf.c
> index 6bbb710216e6..53db26d158c9 100644
> --- a/tools/lib/bpf/btf.c
> +++ b/tools/lib/bpf/btf.c
> @@ -2255,7 +2255,7 @@ static void btf_dedup_merge_hypot_map(struct btf_dedup *d)
>   static int btf_dedup_struct_type(struct btf_dedup *d, __u32 type_id)
>   {
>   	struct btf_dedup_node *cand_node;
> -	struct btf_type *t;
> +	struct btf_type *cand_type, *t;
>   	/* if we don't find equivalent type, then we are canonical */
>   	__u32 new_id = type_id;
>   	__u16 kind;
> @@ -2275,6 +2275,10 @@ static int btf_dedup_struct_type(struct btf_dedup *d, __u32 type_id)
>   	for_each_dedup_cand(d, h, cand_node) {
>   		int eq;
>   
> +		cand_type = d->btf->types[cand_node->type_id];
> +		if (!btf_equal_struct(t, cand_type))

The comment for this btf_equal_struct is not quite right.
/*
  * Check structural compatibility of two FUNC_PROTOs, ignoring 
referenced type
  * IDs. This check is performed during type graph equivalence check and
  * referenced types equivalence is checked separately.
  */
static bool btf_equal_struct(struct btf_type *t1, struct btf_type *t2)

It should be two "struct/union types".

> +			continue;
> +

I did not trace the algorithm how infinite loop happens. But the above
change is certainly a correct one, you want to do deduplication only 
after everything else (except member types) are euqal?

If the bug is due to circle in struct->fwd and fwd->struct mappings,
maybe a simple check whether such circle exists or not before update
the mapping will also work? I am not proposing this fix, but want
to understand better the issue.




>   		btf_dedup_clear_hypot_map(d);
>   		eq = btf_dedup_is_equiv(d, type_id, cand_node->type_id);
>   		if (eq < 0)
>