Message-ID: <CAEf4BzZVda=d=xR4+R4-w+VRiLSnrybtgnCH_xZ6mVCy2hHauA@mail.gmail.com>
Date:   Thu, 28 Feb 2019 12:26:02 -0800
From:   Andrii Nakryiko <andrii.nakryiko@...il.com>
To:     Yonghong Song <yhs@...com>
Cc:     Andrii Nakryiko <andriin@...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 Thu, Feb 28, 2019 at 11:42 AM Yonghong Song <yhs@...com> wrote:
>
>
>
> On 2/28/19 11:07 AM, Andrii Nakryiko wrote:
> > On Thu, Feb 28, 2019 at 10:19 AM Yonghong Song <yhs@...com> wrote:
> >>
> >>
> >>
> >> 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?
> >
> > Yes, for struct/union we can't compare types directly, that's what
> > btf_dedup_is_equiv is doing. I think btf_equal_struct w/ comment
> > explaining this particular behavior is good enough. If you insist,
> > though, I'd rather go to something like btf_shallow_equal_struct or
> > something along those lines.
>
> btf_shallow_equal_struct() will be fine.

Ok.

>
> >
> >>
> >>>
> >>> 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".
> >
> > Yep, good catch, will fix!
> >
> >>
> >>> +                     continue;
> >>> +
> >>
> >> I did not trace the algorithm how infinite loop happens. But the above
> >
> > Check the test in follow up patch. It has a minimal example that
> > triggers this bug. It happens when we have some FWD x, which we
> > discover that it should be resolved to some STRUCT x (as a result of
> > equivalence check/resolution of some other struct s, that references
> > struct x internally). But that struct x might not have been
> > deduplicated yet, we just record this FWD -> STRUCT mapping so that we
> > don't lose this connection. Later, once we get to deduplication of
> > struct x, FWD x will be (in case of hash collision) one possible
> > candidate to consider for deduplication. At that point,
> > btf_dedup_is_equiv will consider them equivalent (but they are not
> > equal (!), that's where the bug is), so we'll try to resolve STRUCT x
> > -> FWD x, which creates a loop.
> >
> > In btf_dedup_merge_hypot_map() that is used to record discovered
> > "equivalences" during struct/union type graph equivalence check, we
> > have explicit check to never resolve STRUCT/UNION into equivalent FWD,
> > so such loop shouldn't happen, except I missed the case of having FWD
> > as a possible dedup candidate due to hash collision.
> >
> >> change is certainly a correct one, you want to do deduplication only
> >> after everything else (except member types) are euqal?
> >
> > Well, if not for special case of FWD == STRUCT/UNION when
> > deduplicating structs, btf_dedup_is_equiv would be enough, because it
> > already checks for btf_equal_struct internally, when both types are
> > struct/union. It's just the special bit at the beginning of is_equiv
> > check that allows FWD and STRUCT/UNION with the same name to be
> > declared equivalent, that throws this off.
> >
> >>
> >> 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.
> >
> > That's essentially what we use btf_equal_struct for here, really. We
> > could equivalently just check BTF_INFO_KIND(t) == BTF_INFO_KIND(cand)
> > explicitly, but I btf_equal_struct feels a bit more generic and
> > obviously correct.
>
> Okay, I see. So the goal is really to prevent processing FWD in the
> struct/union dedup candidate list. It will be good to summarize
> the above detailed explanation in commit message.

Ok, will try to do this more succinctly.

>
> With the above suggested changes,
>    Acked-by: Yonghong Song <yhs@...com>
>
> >
> >>
> >>
> >>
> >>
> >>>                btf_dedup_clear_hypot_map(d);
> >>>                eq = btf_dedup_is_equiv(d, type_id, cand_node->type_id);
> >>>                if (eq < 0)
> >>>

Powered by blists - more mailing lists