From patchwork Wed Feb 27 22:46:37 2019 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Andrii Nakryiko X-Patchwork-Id: 1049183 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="lkzSSXki"; dkim-atps=neutral Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by ozlabs.org (Postfix) with ESMTP id 448rQt0QhLz9sBL for ; Thu, 28 Feb 2019 09:47:02 +1100 (AEDT) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1730384AbfB0Wqy (ORCPT ); Wed, 27 Feb 2019 17:46:54 -0500 Received: from mx0b-00082601.pphosted.com ([67.231.153.30]:33205 "EHLO mx0b-00082601.pphosted.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1729412AbfB0Wqx (ORCPT ); Wed, 27 Feb 2019 17:46:53 -0500 Received: from pps.filterd (m0109332.ppops.net [127.0.0.1]) by mx0a-00082601.pphosted.com (8.16.0.27/8.16.0.27) with SMTP id x1RMcuZY005773 for ; Wed, 27 Feb 2019 14:46:51 -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=T8sJ2xWNHTxJWZsJPQCIdh0hu6T8/lu6TSUaaKl+pbY=; b=lkzSSXki/lr2N0IpQugW8dgFHrbhy+lZeNPTYdWLmGq+TxcjCeRJXpzUHeP4dntxlxyv KTlMyrWET+uF82RPKges9oCy35PcrZc471E9URn3xnd/TNlSGReaa9vx0WbHUQ+yZ+Sp ++kxNOgV8Fi1VhMpFJt6c6+qJQvB98LqoM8= Received: from maileast.thefacebook.com ([199.201.65.23]) by mx0a-00082601.pphosted.com with ESMTP id 2qx2ywg4kw-17 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-SHA384 bits=256 verify=NOT) for ; Wed, 27 Feb 2019 14:46:51 -0800 Received: from mx-out.facebook.com (2620:10d:c0a1:3::13) by mail.thefacebook.com (2620:10d:c021:18::175) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_CBC_SHA) id 15.1.1531.3; Wed, 27 Feb 2019 14:46:49 -0800 Received: by devvm7221.prn2.facebook.com (Postfix, from userid 137359) id 90EA2C07CCCE; Wed, 27 Feb 2019 14:46:47 -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 bpf-next 1/5] selftests/bpf: fix btf_dedup testing code Date: Wed, 27 Feb 2019 14:46:37 -0800 Message-ID: <20190227224642.1069138-2-andriin@fb.com> X-Mailer: git-send-email 2.17.1 In-Reply-To: <20190227224642.1069138-1-andriin@fb.com> References: <20190227224642.1069138-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-27_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 Wed Feb 27 22:46:38 2019 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Andrii Nakryiko X-Patchwork-Id: 1049180 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="dlT77PTD"; dkim-atps=neutral Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by ozlabs.org (Postfix) with ESMTP id 448rQm043Cz9sBL for ; Thu, 28 Feb 2019 09:46:55 +1100 (AEDT) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1730409AbfB0Wqy (ORCPT ); Wed, 27 Feb 2019 17:46:54 -0500 Received: from mx0b-00082601.pphosted.com ([67.231.153.30]:40160 "EHLO mx0a-00082601.pphosted.com" rhost-flags-OK-OK-OK-FAIL) by vger.kernel.org with ESMTP id S1730139AbfB0Wqx (ORCPT ); Wed, 27 Feb 2019 17:46:53 -0500 Received: from pps.filterd (m0001303.ppops.net [127.0.0.1]) by m0001303.ppops.net (8.16.0.27/8.16.0.27) with SMTP id x1RMbOKN005766 for ; Wed, 27 Feb 2019 14:46:50 -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=sFH4MoFp3GxAhDbV2cYE2ivPv+x1a5PpUyPPmIJ1L4g=; b=dlT77PTDxKxd0CHfL/iU7N5pWWgNUx/Xe7WeGksJtjTo+rDnuJzFFwvJgPVo5aM9gEiO vI2zSHA3FEeP5CX4fMA/pvOxgKXm4sUO6+1KkftqSuo4Xggqg69+OAfHlvP40BObkoYH C/MmYL5tYcVgAgYHij7pbprcrO0HkcoqVZc= Received: from maileast.thefacebook.com ([199.201.65.23]) by m0001303.ppops.net with ESMTP id 2qx25v89r6-3 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-SHA384 bits=256 verify=NOT) for ; Wed, 27 Feb 2019 14:46:50 -0800 Received: from mx-out.facebook.com (2620:10d:c0a1:3::13) by mail.thefacebook.com (2620:10d:c021:18::172) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_CBC_SHA) id 15.1.1531.3; Wed, 27 Feb 2019 14:46:48 -0800 Received: by devvm7221.prn2.facebook.com (Postfix, from userid 137359) id 94AD9C07CCD0; Wed, 27 Feb 2019 14:46:47 -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 bpf-next 2/5] libbpf: fix formatting for btf_ext__get_raw_data Date: Wed, 27 Feb 2019 14:46:38 -0800 Message-ID: <20190227224642.1069138-3-andriin@fb.com> X-Mailer: git-send-email 2.17.1 In-Reply-To: <20190227224642.1069138-1-andriin@fb.com> References: <20190227224642.1069138-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-27_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. Fixes: ae4ab4b4117d ("btf: expose API to work with raw btf_ext data") 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 Wed Feb 27 22:46:39 2019 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Andrii Nakryiko X-Patchwork-Id: 1049181 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="BK8Alomk"; dkim-atps=neutral Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by ozlabs.org (Postfix) with ESMTP id 448rQm6sLqz9sDb for ; Thu, 28 Feb 2019 09:46:56 +1100 (AEDT) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1730453AbfB0Wqz (ORCPT ); Wed, 27 Feb 2019 17:46:55 -0500 Received: from mx0b-00082601.pphosted.com ([67.231.153.30]:40158 "EHLO mx0a-00082601.pphosted.com" rhost-flags-OK-OK-OK-FAIL) by vger.kernel.org with ESMTP id S1730240AbfB0Wqy (ORCPT ); Wed, 27 Feb 2019 17:46:54 -0500 Received: from pps.filterd (m0001303.ppops.net [127.0.0.1]) by m0001303.ppops.net (8.16.0.27/8.16.0.27) with SMTP id x1RMbOtd005758 for ; Wed, 27 Feb 2019 14:46:50 -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=hSIwi9nxKoxtoVYzn/ZKlLIJ1IWoCePZKtrycLWhdOY=; b=BK8Alomkzw/ju+xCK/+n4yFSRhA/rBKYjTI18i+3lKOVdi6Ld+rqPAUtRCq3YT4Pi5W1 kDbcsaD1HI6fDxzYKMWF8FoQfeGTOVHgk2hCuQLddQlbN9hVEvIKbz2PV8MVZ1JVUHNh Gj1gbbXPgdYs6hhzVii6ZDnnmA2GHd4q4P0= Received: from maileast.thefacebook.com ([199.201.65.23]) by m0001303.ppops.net with ESMTP id 2qx25v89r7-5 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-SHA384 bits=256 verify=NOT) for ; Wed, 27 Feb 2019 14:46:50 -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.1531.3; Wed, 27 Feb 2019 14:46:49 -0800 Received: by devvm7221.prn2.facebook.com (Postfix, from userid 137359) id 99228C07CCD2; Wed, 27 Feb 2019 14:46:47 -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 bpf-next 3/5] btf: allow to customize dedup hash table size Date: Wed, 27 Feb 2019 14:46:39 -0800 Message-ID: <20190227224642.1069138-4-andriin@fb.com> X-Mailer: git-send-email 2.17.1 In-Reply-To: <20190227224642.1069138-1-andriin@fb.com> References: <20190227224642.1069138-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-27_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 --- tools/lib/bpf/btf.c | 43 ++++++++++++++++++++++++++----------------- tools/lib/bpf/btf.h | 1 + 2 files changed, 27 insertions(+), 17 deletions(-) diff --git a/tools/lib/bpf/btf.c b/tools/lib/bpf/btf.c index 68b50e9bbde1..6bbb710216e6 100644 --- a/tools/lib/bpf/btf.c +++ b/tools/lib/bpf/btf.c @@ -1070,8 +1070,7 @@ 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_UNPROCESSED_ID ((__u32)-1) #define BTF_IN_PROGRESS_ID ((__u32)-2) @@ -1128,18 +1127,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 +1179,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; @@ -1221,10 +1223,19 @@ static struct btf_dedup *btf_dedup_new(struct btf *btf, struct btf_ext *btf_ext, if (!d) return ERR_PTR(-ENOMEM); + d->opts.dont_resolve_fwds = opts && opts->dont_resolve_fwds; + /* ensure table size is power of two and limit to 2G */ + d->opts.dedup_table_size = opts && opts->dedup_table_size + ? opts->dedup_table_size + : BTF_DEDUP_TABLE_DEFAULT_SIZE; + for (i = 0; i < 31 && (1 << i) < d->opts.dedup_table_size; i++) + ; + d->opts.dedup_table_size = 1 << i; + 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 +1260,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 +1833,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 +1844,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 +1855,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 +2272,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 +2358,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 +2381,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 +2412,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 Wed Feb 27 22:46:40 2019 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Andrii Nakryiko X-Patchwork-Id: 1049184 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="a7N2hmmC"; dkim-atps=neutral Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by ozlabs.org (Postfix) with ESMTP id 448rRT2S86z9sDL for ; Thu, 28 Feb 2019 09:47:33 +1100 (AEDT) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1730463AbfB0Wrb (ORCPT ); Wed, 27 Feb 2019 17:47:31 -0500 Received: from mx0b-00082601.pphosted.com ([67.231.153.30]:45982 "EHLO mx0a-00082601.pphosted.com" rhost-flags-OK-OK-OK-FAIL) by vger.kernel.org with ESMTP id S1730149AbfB0Wrb (ORCPT ); Wed, 27 Feb 2019 17:47:31 -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 x1RMj4n7000895 for ; Wed, 27 Feb 2019 14:47:30 -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=9aNLpjBqFRqS9gdhzLnZZThY6ccSFCfONWG1DMgXnLk=; b=a7N2hmmCZ7d/itFTCoKHC0IdXGn/LpvEjERVS2RSGhMdbmMrSDjt6MMEnnIN5Mvv0Lvo QdJHdjJ48g+BLygjZlHapsc6ETv+0l0lQpacMKHMP4YDlTOAo3l9PpzN6AgHYgG7WhZF LmL+J6NR1PVIeK+nrfoB0xEVc072PU06VD8= Received: from maileast.thefacebook.com ([199.201.65.23]) by m0089730.ppops.net with ESMTP id 2qx2snr5w7-16 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-SHA384 bits=256 verify=NOT) for ; Wed, 27 Feb 2019 14:47:30 -0800 Received: from mx-out.facebook.com (2620:10d:c0a1:3::13) by mail.thefacebook.com (2620:10d:c021:18::173) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_CBC_SHA) id 15.1.1531.3; Wed, 27 Feb 2019 14:46:49 -0800 Received: by devvm7221.prn2.facebook.com (Postfix, from userid 137359) id 9DDFCC07CCD4; Wed, 27 Feb 2019 14:46:47 -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 bpf-next 4/5] btf: fix bug with resolving STRUCT/UNION into corresponding FWD Date: Wed, 27 Feb 2019 14:46:40 -0800 Message-ID: <20190227224642.1069138-5-andriin@fb.com> X-Mailer: git-send-email 2.17.1 In-Reply-To: <20190227224642.1069138-1-andriin@fb.com> References: <20190227224642.1069138-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-27_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 --- 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)) + continue; + btf_dedup_clear_hypot_map(d); eq = btf_dedup_is_equiv(d, type_id, cand_node->type_id); if (eq < 0) From patchwork Wed Feb 27 22:46:41 2019 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Andrii Nakryiko X-Patchwork-Id: 1049185 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="YTYB6Kfg"; dkim-atps=neutral Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by ozlabs.org (Postfix) with ESMTP id 448rRW28lLz9sDL for ; Thu, 28 Feb 2019 09:47:35 +1100 (AEDT) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1730485AbfB0Wre (ORCPT ); Wed, 27 Feb 2019 17:47:34 -0500 Received: from mx0b-00082601.pphosted.com ([67.231.153.30]:45986 "EHLO mx0a-00082601.pphosted.com" rhost-flags-OK-OK-OK-FAIL) by vger.kernel.org with ESMTP id S1729412AbfB0Wrc (ORCPT ); Wed, 27 Feb 2019 17:47:32 -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 x1RMj4n8000895 for ; Wed, 27 Feb 2019 14:47:31 -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=y3lAPtTPfGuTKfWufaJ+6qdfeI4yRivOrYZvuORDGyA=; b=YTYB6KfgPD54I+QCIbTYgBINUqcr/Br4huWZN3eWAa4ItCihA89iOMk8R4SUrdciJNM1 27IcS7sO9zqZ4YkKbM27n7ITB1mcdhpRc+PAth1MAm46aq65+hlzwQ9KyemJjXExTMln bw20qjYCiNRjmhbvXqpZ4iLJ+5lMxtGqjvg= Received: from maileast.thefacebook.com ([199.201.65.23]) by m0089730.ppops.net with ESMTP id 2qx2snr5w7-17 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-SHA384 bits=256 verify=NOT) for ; Wed, 27 Feb 2019 14:47:31 -0800 Received: from mx-out.facebook.com (2620:10d:c0a1:3::13) by mail.thefacebook.com (2620:10d:c021:18::173) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_CBC_SHA) id 15.1.1531.3; Wed, 27 Feb 2019 14:46:49 -0800 Received: by devvm7221.prn2.facebook.com (Postfix, from userid 137359) id A205BC07CCD6; Wed, 27 Feb 2019 14:46:47 -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 bpf-next 5/5] selftests/bpf: add btf_dedup test of FWD/STRUCT resolution Date: Wed, 27 Feb 2019 14:46:41 -0800 Message-ID: <20190227224642.1069138-6-andriin@fb.com> X-Mailer: git-send-email 2.17.1 In-Reply-To: <20190227224642.1069138-1-andriin@fb.com> References: <20190227224642.1069138-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-27_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 = {