From patchwork Thu Feb 28 23:31:21 2019 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Andrii Nakryiko X-Patchwork-Id: 1049874 X-Patchwork-Delegate: bpf@iogearbox.net Return-Path: X-Original-To: patchwork-incoming-netdev@ozlabs.org Delivered-To: patchwork-incoming-netdev@ozlabs.org Authentication-Results: ozlabs.org; spf=none (mailfrom) smtp.mailfrom=vger.kernel.org (client-ip=209.132.180.67; helo=vger.kernel.org; envelope-from=netdev-owner@vger.kernel.org; receiver=) Authentication-Results: ozlabs.org; dmarc=pass (p=none dis=none) header.from=fb.com Authentication-Results: ozlabs.org; dkim=pass (1024-bit key; unprotected) header.d=fb.com header.i=@fb.com header.b="VIhuLsgb"; dkim-atps=neutral Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by ozlabs.org (Postfix) with ESMTP id 449TN96Zfmz9s4V for ; Fri, 1 Mar 2019 10:31:53 +1100 (AEDT) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1732637AbfB1Xbo (ORCPT ); Thu, 28 Feb 2019 18:31:44 -0500 Received: from mx0a-00082601.pphosted.com ([67.231.145.42]:50324 "EHLO mx0a-00082601.pphosted.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1732272AbfB1Xbo (ORCPT ); Thu, 28 Feb 2019 18:31:44 -0500 Received: from pps.filterd (m0044010.ppops.net [127.0.0.1]) by mx0a-00082601.pphosted.com (8.16.0.27/8.16.0.27) with SMTP id x1SNUl7R010662 for ; Thu, 28 Feb 2019 15:31:43 -0800 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=fb.com; h=from : to : cc : subject : date : message-id : in-reply-to : references : mime-version : content-type; s=facebook; bh=Hjm+nav2XKcsjHNzDeGspPZAHnnk3L/rZd88etbaJtA=; b=VIhuLsgbxd3iRn1kGK2nu5aSe9MeR4iy0fypUfwP0Widvk1S8QQNRnboJDWygHjFA6Vn ugNXeiShVlyskE8OLCbERY2tLCxsnzgwSWnKoWNw6tTpxL/Ma2CFu8Z/U6cft4l+uzV9 R8cNIpbNapZPasuGcdja1zpOFUe/oGhgi4E= Received: from maileast.thefacebook.com ([199.201.65.23]) by mx0a-00082601.pphosted.com with ESMTP id 2qxqu30b1a-18 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-SHA384 bits=256 verify=NOT) for ; Thu, 28 Feb 2019 15:31:43 -0800 Received: from mx-out.facebook.com (2620:10d:c0a1:3::13) by mail.thefacebook.com (2620:10d:c021:18::176) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_CBC_SHA) id 15.1.1531.3; Thu, 28 Feb 2019 15:31:27 -0800 Received: by devvm7221.prn2.facebook.com (Postfix, from userid 137359) id C6C30C155DDA; Thu, 28 Feb 2019 15:31:26 -0800 (PST) Smtp-Origin-Hostprefix: devvm From: Andrii Nakryiko Smtp-Origin-Hostname: devvm7221.prn2.facebook.com To: , , , , , , , CC: Andrii Nakryiko Smtp-Origin-Cluster: prn2c23 Subject: [PATCH v2 bpf-next 1/5] selftests/bpf: fix btf_dedup testing code Date: Thu, 28 Feb 2019 15:31:21 -0800 Message-ID: <20190228233125.1013080-2-andriin@fb.com> X-Mailer: git-send-email 2.17.1 In-Reply-To: <20190228233125.1013080-1-andriin@fb.com> References: <20190228233125.1013080-1-andriin@fb.com> X-FB-Internal: Safe MIME-Version: 1.0 X-Proofpoint-Virus-Version: vendor=fsecure engine=2.50.10434:, , definitions=2019-02-28_15:, , signatures=0 X-Proofpoint-Spam-Reason: safe X-FB-Internal: Safe Sender: netdev-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: netdev@vger.kernel.org btf_dedup testing code doesn't account for length of struct btf_header when calculating the start of a string section. This patch fixes this problem. Fixes: 49b57e0d01db ("tools/bpf: remove btf__get_strings() superseded by raw data API") Signed-off-by: Andrii Nakryiko Acked-by: Song Liu Acked-by: Yonghong Song --- tools/testing/selftests/bpf/.gitignore | 1 + tools/testing/selftests/bpf/test_btf.c | 4 ++-- 2 files changed, 3 insertions(+), 2 deletions(-) diff --git a/tools/testing/selftests/bpf/.gitignore b/tools/testing/selftests/bpf/.gitignore index e47168d1257d..3b74d23fffab 100644 --- a/tools/testing/selftests/bpf/.gitignore +++ b/tools/testing/selftests/bpf/.gitignore @@ -14,6 +14,7 @@ feature test_libbpf_open test_sock test_sock_addr +test_sock_fields urandom_read test_btf test_sockmap diff --git a/tools/testing/selftests/bpf/test_btf.c b/tools/testing/selftests/bpf/test_btf.c index 02d314383a9c..1426c0a905c8 100644 --- a/tools/testing/selftests/bpf/test_btf.c +++ b/tools/testing/selftests/bpf/test_btf.c @@ -5936,9 +5936,9 @@ static int do_test_dedup(unsigned int test_num) } test_hdr = test_btf_data; - test_strs = test_btf_data + test_hdr->str_off; + test_strs = test_btf_data + sizeof(*test_hdr) + test_hdr->str_off; expect_hdr = expect_btf_data; - expect_strs = expect_btf_data + expect_hdr->str_off; + expect_strs = expect_btf_data + sizeof(*test_hdr) + expect_hdr->str_off; if (CHECK(test_hdr->str_len != expect_hdr->str_len, "test_hdr->str_len:%u != expect_hdr->str_len:%u", test_hdr->str_len, expect_hdr->str_len)) { From patchwork Thu Feb 28 23:31:22 2019 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Andrii Nakryiko X-Patchwork-Id: 1049871 X-Patchwork-Delegate: bpf@iogearbox.net Return-Path: X-Original-To: patchwork-incoming-netdev@ozlabs.org Delivered-To: patchwork-incoming-netdev@ozlabs.org Authentication-Results: ozlabs.org; spf=none (mailfrom) smtp.mailfrom=vger.kernel.org (client-ip=209.132.180.67; helo=vger.kernel.org; envelope-from=netdev-owner@vger.kernel.org; receiver=) Authentication-Results: ozlabs.org; dmarc=pass (p=none dis=none) header.from=fb.com Authentication-Results: ozlabs.org; dkim=pass (1024-bit key; unprotected) header.d=fb.com header.i=@fb.com header.b="c3jY1F3c"; dkim-atps=neutral Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by ozlabs.org (Postfix) with ESMTP id 449TMs3z7fz9s70 for ; Fri, 1 Mar 2019 10:31:37 +1100 (AEDT) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1732069AbfB1Xbg (ORCPT ); Thu, 28 Feb 2019 18:31:36 -0500 Received: from mx0b-00082601.pphosted.com ([67.231.153.30]:37366 "EHLO mx0a-00082601.pphosted.com" rhost-flags-OK-OK-OK-FAIL) by vger.kernel.org with ESMTP id S1731528AbfB1Xbd (ORCPT ); Thu, 28 Feb 2019 18:31:33 -0500 Received: from pps.filterd (m0089730.ppops.net [127.0.0.1]) by m0089730.ppops.net (8.16.0.27/8.16.0.27) with SMTP id x1SNSZwj002203 for ; Thu, 28 Feb 2019 15:31:32 -0800 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=fb.com; h=from : to : cc : subject : date : message-id : in-reply-to : references : mime-version : content-type; s=facebook; bh=dpZLcbOpJtqNjue0D0FFGgsQK5vt4wX6LcRJXPB4jsU=; b=c3jY1F3c1D/7l+kIFzup8OWo5jjxYBXMmHrLgygLTgda1lffwWlOPlaayq/gPCTjZao4 YQ3bnpODn4IYu9hAh/TA8WZyPDFvHfT4X36crSb7DB91TsazWwZsGuNYcqnwWCBzlPcn aJ3fAtThGM8l4oOcv+avikNYG/LeonmdJqc= Received: from maileast.thefacebook.com ([199.201.65.23]) by m0089730.ppops.net with ESMTP id 2qxrh085ca-13 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-SHA384 bits=256 verify=NOT) for ; Thu, 28 Feb 2019 15:31:32 -0800 Received: from mx-out.facebook.com (2620:10d:c0a1:3::13) by mail.thefacebook.com (2620:10d:c021:18::171) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_CBC_SHA) id 15.1.1713.5; Thu, 28 Feb 2019 15:31:28 -0800 Received: by devvm7221.prn2.facebook.com (Postfix, from userid 137359) id CB9C2C155DDC; Thu, 28 Feb 2019 15:31:26 -0800 (PST) Smtp-Origin-Hostprefix: devvm From: Andrii Nakryiko Smtp-Origin-Hostname: devvm7221.prn2.facebook.com To: , , , , , , , CC: Andrii Nakryiko Smtp-Origin-Cluster: prn2c23 Subject: [PATCH v2 bpf-next 2/5] libbpf: fix formatting for btf_ext__get_raw_data Date: Thu, 28 Feb 2019 15:31:22 -0800 Message-ID: <20190228233125.1013080-3-andriin@fb.com> X-Mailer: git-send-email 2.17.1 In-Reply-To: <20190228233125.1013080-1-andriin@fb.com> References: <20190228233125.1013080-1-andriin@fb.com> X-FB-Internal: Safe MIME-Version: 1.0 X-Proofpoint-Virus-Version: vendor=fsecure engine=2.50.10434:, , definitions=2019-02-28_15:, , signatures=0 X-Proofpoint-Spam-Reason: safe X-FB-Internal: Safe Sender: netdev-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: netdev@vger.kernel.org Fix invalid formatting of pointer arg. Signed-off-by: Andrii Nakryiko Acked-by: Song Liu --- tools/lib/bpf/btf.h | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/tools/lib/bpf/btf.h b/tools/lib/bpf/btf.h index 94bbc249b0f1..b60bb7cf5fff 100644 --- a/tools/lib/bpf/btf.h +++ b/tools/lib/bpf/btf.h @@ -76,7 +76,7 @@ LIBBPF_API int btf__get_map_kv_tids(const struct btf *btf, const char *map_name, LIBBPF_API struct btf_ext *btf_ext__new(__u8 *data, __u32 size); LIBBPF_API void btf_ext__free(struct btf_ext *btf_ext); -LIBBPF_API const void *btf_ext__get_raw_data(const struct btf_ext* btf_ext, +LIBBPF_API const void *btf_ext__get_raw_data(const struct btf_ext *btf_ext, __u32 *size); LIBBPF_API int btf_ext__reloc_func_info(const struct btf *btf, const struct btf_ext *btf_ext, From patchwork Thu Feb 28 23:31:23 2019 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Andrii Nakryiko X-Patchwork-Id: 1049870 X-Patchwork-Delegate: bpf@iogearbox.net Return-Path: X-Original-To: patchwork-incoming-netdev@ozlabs.org Delivered-To: patchwork-incoming-netdev@ozlabs.org Authentication-Results: ozlabs.org; spf=none (mailfrom) smtp.mailfrom=vger.kernel.org (client-ip=209.132.180.67; helo=vger.kernel.org; envelope-from=netdev-owner@vger.kernel.org; receiver=) Authentication-Results: ozlabs.org; dmarc=pass (p=none dis=none) header.from=fb.com Authentication-Results: ozlabs.org; dkim=pass (1024-bit key; unprotected) header.d=fb.com header.i=@fb.com header.b="hQIL/UhC"; dkim-atps=neutral Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by ozlabs.org (Postfix) with ESMTP id 449TMr2K3Jz9s4V for ; Fri, 1 Mar 2019 10:31:36 +1100 (AEDT) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1731853AbfB1Xbe (ORCPT ); Thu, 28 Feb 2019 18:31:34 -0500 Received: from mx0b-00082601.pphosted.com ([67.231.153.30]:37354 "EHLO mx0a-00082601.pphosted.com" rhost-flags-OK-OK-OK-FAIL) by vger.kernel.org with ESMTP id S1731324AbfB1Xbd (ORCPT ); Thu, 28 Feb 2019 18:31:33 -0500 Received: from pps.filterd (m0089730.ppops.net [127.0.0.1]) by m0089730.ppops.net (8.16.0.27/8.16.0.27) with SMTP id x1SNSZwh002203 for ; Thu, 28 Feb 2019 15:31:32 -0800 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=fb.com; h=from : to : cc : subject : date : message-id : in-reply-to : references : mime-version : content-type; s=facebook; bh=9i1lDDyiX6EYz4yom4CayHQJIy/EVoB//AM7hzboX+Y=; b=hQIL/UhCpTx/g3J+cH+P8vjP7cEY93pto7noJQkUEQlRfxEJPLQfQ4s55GKfcfjTfem/ MXiZMP2WquPNKWhnhCyso4/o1IE4+uQAhFZDvg53V8UuaOfRQdcgXweQgvqpDZTlmV6e bDWReDEgN3KkFLqb51uiVpq/+JXt02OVys8= Received: from maileast.thefacebook.com ([199.201.65.23]) by m0089730.ppops.net with ESMTP id 2qxrh085ca-11 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-SHA384 bits=256 verify=NOT) for ; Thu, 28 Feb 2019 15:31:31 -0800 Received: from mx-out.facebook.com (2620:10d:c0a1:3::13) by mail.thefacebook.com (2620:10d:c021:18::171) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_CBC_SHA) id 15.1.1713.5; Thu, 28 Feb 2019 15:31:28 -0800 Received: by devvm7221.prn2.facebook.com (Postfix, from userid 137359) id D1921C155DDE; Thu, 28 Feb 2019 15:31:26 -0800 (PST) Smtp-Origin-Hostprefix: devvm From: Andrii Nakryiko Smtp-Origin-Hostname: devvm7221.prn2.facebook.com To: , , , , , , , CC: Andrii Nakryiko Smtp-Origin-Cluster: prn2c23 Subject: [PATCH v2 bpf-next 3/5] btf: allow to customize dedup hash table size Date: Thu, 28 Feb 2019 15:31:23 -0800 Message-ID: <20190228233125.1013080-4-andriin@fb.com> X-Mailer: git-send-email 2.17.1 In-Reply-To: <20190228233125.1013080-1-andriin@fb.com> References: <20190228233125.1013080-1-andriin@fb.com> X-FB-Internal: Safe MIME-Version: 1.0 X-Proofpoint-Virus-Version: vendor=fsecure engine=2.50.10434:, , definitions=2019-02-28_15:, , signatures=0 X-Proofpoint-Spam-Reason: safe X-FB-Internal: Safe Sender: netdev-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: netdev@vger.kernel.org Default size of dedup table (16k) is good enough for most binaries, even typical vmlinux images. But there are cases of binaries with huge amount of BTF types (e.g., allyesconfig variants of kernel), which benefit from having bigger dedup table size to lower amount of unnecessary hash collisions. Tools like pahole, thus, can tune this parameter to reach optimal performance. This change also serves double purpose of allowing tests to force hash collisions to test some corner cases, used in follow up patch. Signed-off-by: Andrii Nakryiko Acked-by: Yonghong Song --- tools/lib/bpf/btf.c | 53 ++++++++++++++++++++++++++++++--------------- tools/lib/bpf/btf.h | 1 + 2 files changed, 37 insertions(+), 17 deletions(-) diff --git a/tools/lib/bpf/btf.c b/tools/lib/bpf/btf.c index 68b50e9bbde1..0f83f99211c6 100644 --- a/tools/lib/bpf/btf.c +++ b/tools/lib/bpf/btf.c @@ -1070,8 +1070,8 @@ int btf__dedup(struct btf *btf, struct btf_ext *btf_ext, return err; } -#define BTF_DEDUP_TABLE_SIZE_LOG 14 -#define BTF_DEDUP_TABLE_MOD ((1 << BTF_DEDUP_TABLE_SIZE_LOG) - 1) +#define BTF_DEDUP_TABLE_DEFAULT_SIZE (1 << 14) +#define BTF_DEDUP_TABLE_MAX_SIZE_LOG 31 #define BTF_UNPROCESSED_ID ((__u32)-1) #define BTF_IN_PROGRESS_ID ((__u32)-2) @@ -1128,18 +1128,21 @@ static inline __u32 hash_combine(__u32 h, __u32 value) #undef GOLDEN_RATIO_PRIME } -#define for_each_hash_node(table, hash, node) \ - for (node = table[hash & BTF_DEDUP_TABLE_MOD]; node; node = node->next) +#define for_each_dedup_cand(d, hash, node) \ + for (node = d->dedup_table[hash & (d->opts.dedup_table_size - 1)]; \ + node; \ + node = node->next) static int btf_dedup_table_add(struct btf_dedup *d, __u32 hash, __u32 type_id) { struct btf_dedup_node *node = malloc(sizeof(struct btf_dedup_node)); + int bucket = hash & (d->opts.dedup_table_size - 1); if (!node) return -ENOMEM; node->type_id = type_id; - node->next = d->dedup_table[hash & BTF_DEDUP_TABLE_MOD]; - d->dedup_table[hash & BTF_DEDUP_TABLE_MOD] = node; + node->next = d->dedup_table[bucket]; + d->dedup_table[bucket] = node; return 0; } @@ -1177,7 +1180,7 @@ static void btf_dedup_table_free(struct btf_dedup *d) if (!d->dedup_table) return; - for (i = 0; i < (1 << BTF_DEDUP_TABLE_SIZE_LOG); i++) { + for (i = 0; i < d->opts.dedup_table_size; i++) { while (d->dedup_table[i]) { tmp = d->dedup_table[i]; d->dedup_table[i] = tmp->next; @@ -1212,19 +1215,37 @@ static void btf_dedup_free(struct btf_dedup *d) free(d); } +/* Find closest power of two >= to size, capped at 2^max_size_log */ +static __u32 roundup_pow2_max(__u32 size, int max_size_log) +{ + int i; + + for (i = 0; i < max_size_log && (1U << i) < size; i++) + ; + return 1U << i; +} + + static struct btf_dedup *btf_dedup_new(struct btf *btf, struct btf_ext *btf_ext, const struct btf_dedup_opts *opts) { struct btf_dedup *d = calloc(1, sizeof(struct btf_dedup)); int i, err = 0; + __u32 sz; if (!d) return ERR_PTR(-ENOMEM); + d->opts.dont_resolve_fwds = opts && opts->dont_resolve_fwds; + sz = opts && opts->dedup_table_size ? opts->dedup_table_size + : BTF_DEDUP_TABLE_DEFAULT_SIZE; + sz = roundup_pow2_max(sz, BTF_DEDUP_TABLE_MAX_SIZE_LOG); + d->opts.dedup_table_size = sz; + d->btf = btf; d->btf_ext = btf_ext; - d->dedup_table = calloc(1 << BTF_DEDUP_TABLE_SIZE_LOG, + d->dedup_table = calloc(d->opts.dedup_table_size, sizeof(struct btf_dedup_node *)); if (!d->dedup_table) { err = -ENOMEM; @@ -1249,8 +1270,6 @@ static struct btf_dedup *btf_dedup_new(struct btf *btf, struct btf_ext *btf_ext, for (i = 0; i <= btf->nr_types; i++) d->hypot_map[i] = BTF_UNPROCESSED_ID; - d->opts.dont_resolve_fwds = opts && opts->dont_resolve_fwds; - done: if (err) { btf_dedup_free(d); @@ -1824,7 +1843,7 @@ static int btf_dedup_prim_type(struct btf_dedup *d, __u32 type_id) case BTF_KIND_INT: h = btf_hash_int(t); - for_each_hash_node(d->dedup_table, h, cand_node) { + for_each_dedup_cand(d, h, cand_node) { cand = d->btf->types[cand_node->type_id]; if (btf_equal_int(t, cand)) { new_id = cand_node->type_id; @@ -1835,7 +1854,7 @@ static int btf_dedup_prim_type(struct btf_dedup *d, __u32 type_id) case BTF_KIND_ENUM: h = btf_hash_enum(t); - for_each_hash_node(d->dedup_table, h, cand_node) { + for_each_dedup_cand(d, h, cand_node) { cand = d->btf->types[cand_node->type_id]; if (btf_equal_enum(t, cand)) { new_id = cand_node->type_id; @@ -1846,7 +1865,7 @@ static int btf_dedup_prim_type(struct btf_dedup *d, __u32 type_id) case BTF_KIND_FWD: h = btf_hash_common(t); - for_each_hash_node(d->dedup_table, h, cand_node) { + for_each_dedup_cand(d, h, cand_node) { cand = d->btf->types[cand_node->type_id]; if (btf_equal_common(t, cand)) { new_id = cand_node->type_id; @@ -2263,7 +2282,7 @@ static int btf_dedup_struct_type(struct btf_dedup *d, __u32 type_id) return 0; h = btf_hash_struct(t); - for_each_hash_node(d->dedup_table, h, cand_node) { + for_each_dedup_cand(d, h, cand_node) { int eq; btf_dedup_clear_hypot_map(d); @@ -2349,7 +2368,7 @@ static int btf_dedup_ref_type(struct btf_dedup *d, __u32 type_id) t->type = ref_type_id; h = btf_hash_common(t); - for_each_hash_node(d->dedup_table, h, cand_node) { + for_each_dedup_cand(d, h, cand_node) { cand = d->btf->types[cand_node->type_id]; if (btf_equal_common(t, cand)) { new_id = cand_node->type_id; @@ -2372,7 +2391,7 @@ static int btf_dedup_ref_type(struct btf_dedup *d, __u32 type_id) info->index_type = ref_type_id; h = btf_hash_array(t); - for_each_hash_node(d->dedup_table, h, cand_node) { + for_each_dedup_cand(d, h, cand_node) { cand = d->btf->types[cand_node->type_id]; if (btf_equal_array(t, cand)) { new_id = cand_node->type_id; @@ -2403,7 +2422,7 @@ static int btf_dedup_ref_type(struct btf_dedup *d, __u32 type_id) } h = btf_hash_fnproto(t); - for_each_hash_node(d->dedup_table, h, cand_node) { + for_each_dedup_cand(d, h, cand_node) { cand = d->btf->types[cand_node->type_id]; if (btf_equal_fnproto(t, cand)) { new_id = cand_node->type_id; diff --git a/tools/lib/bpf/btf.h b/tools/lib/bpf/btf.h index b60bb7cf5fff..28a1e1e59861 100644 --- a/tools/lib/bpf/btf.h +++ b/tools/lib/bpf/btf.h @@ -90,6 +90,7 @@ LIBBPF_API __u32 btf_ext__func_info_rec_size(const struct btf_ext *btf_ext); LIBBPF_API __u32 btf_ext__line_info_rec_size(const struct btf_ext *btf_ext); struct btf_dedup_opts { + unsigned int dedup_table_size; bool dont_resolve_fwds; }; From patchwork Thu Feb 28 23:31:24 2019 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Andrii Nakryiko X-Patchwork-Id: 1049872 X-Patchwork-Delegate: bpf@iogearbox.net Return-Path: X-Original-To: patchwork-incoming-netdev@ozlabs.org Delivered-To: patchwork-incoming-netdev@ozlabs.org Authentication-Results: ozlabs.org; spf=none (mailfrom) smtp.mailfrom=vger.kernel.org (client-ip=209.132.180.67; helo=vger.kernel.org; envelope-from=netdev-owner@vger.kernel.org; receiver=) Authentication-Results: ozlabs.org; dmarc=pass (p=none dis=none) header.from=fb.com Authentication-Results: ozlabs.org; dkim=pass (1024-bit key; unprotected) header.d=fb.com header.i=@fb.com header.b="FCt4484A"; dkim-atps=neutral Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by ozlabs.org (Postfix) with ESMTP id 449TMw0lYwz9s4V for ; Fri, 1 Mar 2019 10:31:40 +1100 (AEDT) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1732267AbfB1Xbj (ORCPT ); Thu, 28 Feb 2019 18:31:39 -0500 Received: from mx0b-00082601.pphosted.com ([67.231.153.30]:37382 "EHLO mx0a-00082601.pphosted.com" rhost-flags-OK-OK-OK-FAIL) by vger.kernel.org with ESMTP id S1731684AbfB1Xbf (ORCPT ); Thu, 28 Feb 2019 18:31:35 -0500 Received: from pps.filterd (m0089730.ppops.net [127.0.0.1]) by m0089730.ppops.net (8.16.0.27/8.16.0.27) with SMTP id x1SNSZwn002203 for ; Thu, 28 Feb 2019 15:31:33 -0800 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=fb.com; h=from : to : cc : subject : date : message-id : in-reply-to : references : mime-version : content-type; s=facebook; bh=yv2te+/7ZWov+RFZsLfl7wFKUr1FUlswI0auD1wsbbU=; b=FCt4484ATkFxja13Pn/4MLDVkQ5CF0SIMvm6PrHBLi1rXPrUOU1twLqS73b4WwTkd86m y5/wS0e8GNmwtXsAcJll9xx/M7R2HdmM8T5DqjKaAPP5OnCGD7QkzbPa11sJLoioVTxW NtB/0zT7mAZEj+WXX/6RtpkY/1XFa2686Lw= Received: from maileast.thefacebook.com ([199.201.65.23]) by m0089730.ppops.net with ESMTP id 2qxrh085ca-17 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-SHA384 bits=256 verify=NOT) for ; Thu, 28 Feb 2019 15:31:33 -0800 Received: from mx-out.facebook.com (2620:10d:c0a1:3::13) by mail.thefacebook.com (2620:10d:c021:18::171) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_CBC_SHA) id 15.1.1713.5; Thu, 28 Feb 2019 15:31:28 -0800 Received: by devvm7221.prn2.facebook.com (Postfix, from userid 137359) id D45B5C155DE0; Thu, 28 Feb 2019 15:31:26 -0800 (PST) Smtp-Origin-Hostprefix: devvm From: Andrii Nakryiko Smtp-Origin-Hostname: devvm7221.prn2.facebook.com To: , , , , , , , CC: Andrii Nakryiko Smtp-Origin-Cluster: prn2c23 Subject: [PATCH v2 bpf-next 4/5] btf: fix bug with resolving STRUCT/UNION into corresponding FWD Date: Thu, 28 Feb 2019 15:31:24 -0800 Message-ID: <20190228233125.1013080-5-andriin@fb.com> X-Mailer: git-send-email 2.17.1 In-Reply-To: <20190228233125.1013080-1-andriin@fb.com> References: <20190228233125.1013080-1-andriin@fb.com> X-FB-Internal: Safe MIME-Version: 1.0 X-Proofpoint-Virus-Version: vendor=fsecure engine=2.50.10434:, , definitions=2019-02-28_15:, , signatures=0 X-Proofpoint-Spam-Reason: safe X-FB-Internal: Safe Sender: netdev-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: netdev@vger.kernel.org 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). Fixes: d5caef5b5655 ("btf: add BTF types deduplication algorithm") Reported-by: Arnaldo Carvalho de Melo Signed-off-by: Andrii Nakryiko Acked-by: Song Liu Acked-by: Yonghong Song --- tools/lib/bpf/btf.c | 20 +++++++++++++++++--- 1 file changed, 17 insertions(+), 3 deletions(-) diff --git a/tools/lib/bpf/btf.c b/tools/lib/bpf/btf.c index 0f83f99211c6..c0b575c6ebb0 100644 --- a/tools/lib/bpf/btf.c +++ b/tools/lib/bpf/btf.c @@ -1663,7 +1663,7 @@ static __u32 btf_hash_struct(struct btf_type *t) * 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) +static bool btf_shallow_equal_struct(struct btf_type *t1, struct btf_type *t2) { struct btf_member *m1, *m2; __u16 vlen; @@ -2124,7 +2124,7 @@ static int btf_dedup_is_equiv(struct btf_dedup *d, __u32 cand_id, struct btf_member *cand_m, *canon_m; __u16 vlen; - if (!btf_equal_struct(cand_type, canon_type)) + if (!btf_shallow_equal_struct(cand_type, canon_type)) return 0; vlen = BTF_INFO_VLEN(cand_type->info); cand_m = (struct btf_member *)(cand_type + 1); @@ -2265,7 +2265,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; @@ -2285,6 +2285,20 @@ static int btf_dedup_struct_type(struct btf_dedup *d, __u32 type_id) for_each_dedup_cand(d, h, cand_node) { int eq; + /* + * Even though btf_dedup_is_equiv() checks for + * btf_shallow_equal_struct() internally when checking two + * structs (unions) for equivalence, we need to guard here + * from picking matching FWD type as a dedup candidate. + * This can happen due to hash collision. In such case just + * relying on btf_dedup_is_equiv() would lead to potentially + * creating a loop (FWD -> STRUCT and STRUCT -> FWD), because + * FWD and compatible STRUCT/UNION are considered equivalent. + */ + cand_type = d->btf->types[cand_node->type_id]; + if (!btf_shallow_equal_struct(t, cand_type)) + continue; + btf_dedup_clear_hypot_map(d); eq = btf_dedup_is_equiv(d, type_id, cand_node->type_id); if (eq < 0) From patchwork Thu Feb 28 23:31:25 2019 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Andrii Nakryiko X-Patchwork-Id: 1049873 X-Patchwork-Delegate: bpf@iogearbox.net Return-Path: X-Original-To: patchwork-incoming-netdev@ozlabs.org Delivered-To: patchwork-incoming-netdev@ozlabs.org Authentication-Results: ozlabs.org; spf=none (mailfrom) smtp.mailfrom=vger.kernel.org (client-ip=209.132.180.67; helo=vger.kernel.org; envelope-from=netdev-owner@vger.kernel.org; receiver=) Authentication-Results: ozlabs.org; dmarc=pass (p=none dis=none) header.from=fb.com Authentication-Results: ozlabs.org; dkim=pass (1024-bit key; unprotected) header.d=fb.com header.i=@fb.com header.b="aIaIDgan"; dkim-atps=neutral Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by ozlabs.org (Postfix) with ESMTP id 449TN82tYkz9s4V for ; Fri, 1 Mar 2019 10:31:52 +1100 (AEDT) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1732956AbfB1Xbu (ORCPT ); Thu, 28 Feb 2019 18:31:50 -0500 Received: from mx0b-00082601.pphosted.com ([67.231.153.30]:57134 "EHLO mx0b-00082601.pphosted.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1732934AbfB1Xbu (ORCPT ); Thu, 28 Feb 2019 18:31:50 -0500 Received: from pps.filterd (m0109331.ppops.net [127.0.0.1]) by mx0a-00082601.pphosted.com (8.16.0.27/8.16.0.27) with SMTP id x1SNS8wS002228 for ; Thu, 28 Feb 2019 15:31:49 -0800 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=fb.com; h=from : to : cc : subject : date : message-id : in-reply-to : references : mime-version : content-type; s=facebook; bh=msSYZg3Ko7s53DGsMv/nGqEd7BGNU9xLNbbXuzjEKt4=; b=aIaIDganIQ9YE/KMwYjsqdg5tNUDez5ZeJw+ryblEGY3T1i8rjKvslgGGdyEt6lEM0bN 8MUIuK3mPHKbwMy7Za/3aUuhmW9AMJMHrZWLqoYuLDNQSacVTOHB/mLPrAm5R8+ItKNf HuODY5dYp6ud6WoyqaDVZgJUNIv0vZVJuQw= Received: from maileast.thefacebook.com ([199.201.65.23]) by mx0a-00082601.pphosted.com with ESMTP id 2qxr1509k7-6 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-SHA384 bits=256 verify=NOT) for ; Thu, 28 Feb 2019 15:31:48 -0800 Received: from mx-out.facebook.com (2620:10d:c0a1:3::13) by mail.thefacebook.com (2620:10d:c021:18::176) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_CBC_SHA) id 15.1.1531.3; Thu, 28 Feb 2019 15:31:28 -0800 Received: by devvm7221.prn2.facebook.com (Postfix, from userid 137359) id D907DC155DE2; Thu, 28 Feb 2019 15:31:26 -0800 (PST) Smtp-Origin-Hostprefix: devvm From: Andrii Nakryiko Smtp-Origin-Hostname: devvm7221.prn2.facebook.com To: , , , , , , , CC: Andrii Nakryiko Smtp-Origin-Cluster: prn2c23 Subject: [PATCH v2 bpf-next 5/5] selftests/bpf: add btf_dedup test of FWD/STRUCT resolution Date: Thu, 28 Feb 2019 15:31:25 -0800 Message-ID: <20190228233125.1013080-6-andriin@fb.com> X-Mailer: git-send-email 2.17.1 In-Reply-To: <20190228233125.1013080-1-andriin@fb.com> References: <20190228233125.1013080-1-andriin@fb.com> X-FB-Internal: Safe MIME-Version: 1.0 X-Proofpoint-Virus-Version: vendor=fsecure engine=2.50.10434:, , definitions=2019-02-28_15:, , signatures=0 X-Proofpoint-Spam-Reason: safe X-FB-Internal: Safe Sender: netdev-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: netdev@vger.kernel.org This patch adds a btf_dedup test exercising logic of STRUCT<->FWD resolution and validating that STRUCT is not resolved to a FWD. It also forces hash collisions, forcing both FWD and STRUCT to be candidates for each other. Previously this condition caused infinite loop due to FWD pointing to STRUCT and STRUCT pointing to its FWD. Reported-by: Arnaldo Carvalho de Melo Signed-off-by: Andrii Nakryiko Acked-by: Song Liu --- tools/testing/selftests/bpf/test_btf.c | 45 ++++++++++++++++++++++++++ 1 file changed, 45 insertions(+) diff --git a/tools/testing/selftests/bpf/test_btf.c b/tools/testing/selftests/bpf/test_btf.c index 1426c0a905c8..38797aa627a7 100644 --- a/tools/testing/selftests/bpf/test_btf.c +++ b/tools/testing/selftests/bpf/test_btf.c @@ -5731,6 +5731,51 @@ const struct btf_dedup_test dedup_tests[] = { .dont_resolve_fwds = false, }, }, +{ + .descr = "dedup: struct <-> fwd resolution w/ hash collision", + /* + * // CU 1: + * struct x; + * struct s { + * struct x *x; + * }; + * // CU 2: + * struct x {}; + * struct s { + * struct x *x; + * }; + */ + .input = { + .raw_types = { + /* CU 1 */ + BTF_FWD_ENC(NAME_TBD, 0 /* struct fwd */), /* [1] fwd x */ + BTF_PTR_ENC(1), /* [2] ptr -> [1] */ + BTF_STRUCT_ENC(NAME_TBD, 1, 8), /* [3] struct s */ + BTF_MEMBER_ENC(NAME_TBD, 2, 0), + /* CU 2 */ + BTF_STRUCT_ENC(NAME_TBD, 0, 0), /* [4] struct x */ + BTF_PTR_ENC(4), /* [5] ptr -> [4] */ + BTF_STRUCT_ENC(NAME_TBD, 1, 8), /* [6] struct s */ + BTF_MEMBER_ENC(NAME_TBD, 5, 0), + BTF_END_RAW, + }, + BTF_STR_SEC("\0x\0s\0x\0x\0s\0x\0"), + }, + .expect = { + .raw_types = { + BTF_PTR_ENC(3), /* [1] ptr -> [3] */ + BTF_STRUCT_ENC(NAME_TBD, 1, 8), /* [2] struct s */ + BTF_MEMBER_ENC(NAME_TBD, 1, 0), + BTF_STRUCT_ENC(NAME_NTH(2), 0, 0), /* [3] struct x */ + BTF_END_RAW, + }, + BTF_STR_SEC("\0s\0x"), + }, + .opts = { + .dont_resolve_fwds = false, + .dedup_table_size = 1, /* force hash collisions */ + }, +}, { .descr = "dedup: all possible kinds (no duplicates)", .input = {