Re: [PATCH bpf-next 4/5] btf: fix bug with resolving STRUCT/UNION into corresponding FWD
From: Yonghong Song <hidden>
Date: 2019-02-28 18:19:18
Also in:
bpf
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?
quoted hunk ↗ jump to hunk
Fixes: d5caef5b5655 ("btf: add BTF types deduplication algorithm") Reported-by: Arnaldo Carvalho de Melo <redacted> Signed-off-by: Andrii Nakryiko <redacted> --- 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)