From nobody Mon Nov 25 07:25:54 2024 Received: from mail-pg1-f178.google.com (mail-pg1-f178.google.com [209.85.215.178]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id EEFEF79F5; Tue, 29 Oct 2024 00:22:24 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.215.178 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1730161348; cv=none; b=IxiTURwKGW9ZfHB7VxPX3LL9qQK3Us7RhFvI9exdv2tfVWRAezKSG/++y/vsKjotqS8MswQYS09/81z2J5PHmnVT+Ez5EoriWur9L+hwXU7tOgwA1CSerfkaosL9YWx/egkZT2+NBDBN4rzrp96V00chekVLxNxRMjzCbRiIg4Q= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1730161348; c=relaxed/simple; bh=AnN603qwCjTnmNjWuIvbxyyFo50ShPsvcy9hrZpo6xg=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=U+d2tg7A45b5TMZX298SVWCrazjo8x9qaIYe7Yv5NKmuAfKYpAAZ94UVd9M32wkeW9qiBkVc78zo/4roEg6qmY/QmWmWwbRAnBLhbaugcNf+LFyBzpUAgLylFR38iq3YemSA5QxC2Na5706QIeQoEvmoBDMOA2Ol44KrBWshhYo= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com; spf=pass smtp.mailfrom=gmail.com; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b=DGkVoqLh; arc=none smtp.client-ip=209.85.215.178 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=gmail.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="DGkVoqLh" Received: by mail-pg1-f178.google.com with SMTP id 41be03b00d2f7-7d4fa972cbeso4127083a12.2; Mon, 28 Oct 2024 17:22:24 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1730161344; x=1730766144; darn=vger.kernel.org; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=zCwI8AAhOqVEsLEN4vixtT4a70Lj0Ci3f9ieyC7vrBo=; b=DGkVoqLhI7QFyWhrX/c2G14ePr+5sVbzNr3Jluv+2Pn22OFNR8xxafQrdcCE95I0xw LuQNN3Rh2yWwnLudDoGPHpN7zIl0BXdxS5PD8neZeP6FHbrkS630PO5slMiduLpflXtN y5C047uaSn6sjbO1E0MWlByPxSkiDNloSrsUiddkT+QPIGY417j52NOgXZ0N5hFV7kHX p0AsEUpYP2c/oWJgA7+Z4YXzli5s0h2Gdgusx/fmWuAwY3qB2BDUYCpAabwM7vjD5V3V sVkN3pThoMm/4czKN6deTMuePd8b80yJO9ApZFCzebBn/67ZT4le8otJMKi08K89K1UP TrJg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1730161344; x=1730766144; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=zCwI8AAhOqVEsLEN4vixtT4a70Lj0Ci3f9ieyC7vrBo=; b=JlrceXSMZS5A99S9ndgsDW9E4bHXCfXyG0TXTx3rrPVEchY1iYuMkfSRP5M1jNrFCf /QSwNjQ7SOV+KAI1p17yM4tuNTzthzn6r6jbwabrakEsRF+bxHvZgT/95eZ7q0eSyAVr RHoEXZwiQY40y+ugI4qVn92R7JRknNdGreChm2PJ+9dBwGi2nxy7BtW2VtG9VXAKHo+f Z5Wvi53Vxlybma67hWoqHuD8QjcSXqVzR1ezXWnaGGSLfSWbonkqqBVkF0cbqqHgCaSy z/mNzsfeDq/i1Dh/su6KLjXwuEIchPDNmS1i/ZnSFC77h4EFLeZ2HBJvpL4nxHhQiYvN qyJA== X-Forwarded-Encrypted: i=1; AJvYcCUSCWnsxtbZpU6PCAY+WO7rZUu/mwcoCb18uQfnDNQD0OukGjNQDF76RNqHkgvnGB6XrJd5Sd5Wg21/6kCLaToqpWmQ@vger.kernel.org, AJvYcCUkOYnvznjriR2Gc6zc1TGLJCLX0R3cBJRUbA2TUKhvqWtGS0w4Ar1NqcmODQIIfvFQi9O4g4TIRwSkPcQU@vger.kernel.org, AJvYcCVRMy4aPbWpOCaHhJpcQSEmsIo/jBPfaAk3pBhs3BMsY7vF7W5lsusnHwlvQs1BXYaQ5mb0Lqr7+IgKXvzlEgHT@vger.kernel.org, AJvYcCX9nGpIBu6eN58A6bcOWHnTunvweqBuBOXnbm2Yr965/Jn38X+D53tYzMaBH+I3JNvEc2Y=@vger.kernel.org X-Gm-Message-State: AOJu0YxEv12LfPktJ1CuVNXmjAWEIIqXXhRKdz8x07HCdjDwPvpHlnMM muLb/FQfOz1lg1rHt3TZWZBjWY0CU0CHVE6ewsMnrmR3zdEYQBlB5FfCb1/L X-Google-Smtp-Source: AGHT+IG7Meak8bLIY6YQCzhkJ9XHo97omfuOU8GMl7S1qgl7P7GBtQxOGWDEay8y0y5kFIDFrGVuNA== X-Received: by 2002:a17:90a:e10a:b0:2e5:8392:afe7 with SMTP id 98e67ed59e1d1-2e8f0d65883mr11910717a91.0.1730161343916; Mon, 28 Oct 2024 17:22:23 -0700 (PDT) Received: from pengdl-ub.localdomain ([106.37.77.202]) by smtp.gmail.com with ESMTPSA id 98e67ed59e1d1-2e77e48e4a2sm10175507a91.2.2024.10.28.17.22.19 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 28 Oct 2024 17:22:22 -0700 (PDT) From: Donglin Peng To: andrii@kernel.org, eddyz87@gmail.com Cc: ast@kernel.org, rostedt@goodmis.org, mhiramat@kernel.org, bpf@vger.kernel.org, linux-trace-kernel@vger.kernel.org, linux-kselftest@vger.kernel.org, linux-kernel@vger.kernel.org, Donglin Peng Subject: [PATCH v4 1/3] libbpf: Sort btf_types in ascending order by name Date: Tue, 29 Oct 2024 08:22:06 +0800 Message-Id: <20241029002208.1947947-2-dolinux.peng@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20241029002208.1947947-1-dolinux.peng@gmail.com> References: <20241029002208.1947947-1-dolinux.peng@gmail.com> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset="utf-8" To enhance the searching performance of btf_find_by_name_kind, we can sort the btf_types in ascending order based on their names. This allows us to implement a binary search method. Co-developed-by: Eduard Zingerman Signed-off-by: Eduard Zingerman Signed-off-by: Donglin Peng --- v4: - Divide the patch into two parts: kernel and libbpf - Use Eduard's code to sort btf_types in the btf__dedup function - Correct some btf testcases due to modifications of the order of btf_type= s. --- tools/lib/bpf/btf.c | 115 +++++-- tools/testing/selftests/bpf/prog_tests/btf.c | 296 +++++++++--------- .../bpf/prog_tests/btf_dedup_split.c | 64 ++-- 3 files changed, 268 insertions(+), 207 deletions(-) diff --git a/tools/lib/bpf/btf.c b/tools/lib/bpf/btf.c index 3c131039c523..5290e9d59997 100644 --- a/tools/lib/bpf/btf.c +++ b/tools/lib/bpf/btf.c @@ -1,6 +1,9 @@ // SPDX-License-Identifier: (LGPL-2.1 OR BSD-2-Clause) /* Copyright (c) 2018 Facebook */ =20 +#ifndef _GNU_SOURCE +#define _GNU_SOURCE +#endif #include #include #include @@ -4902,6 +4905,49 @@ static int btf_dedup_resolve_fwds(struct btf_dedup *= d) return err; } =20 +/* compare btf types by name, consider named < anonymous */ +static int btf_compare_type_names(const void *a, const void *b, void *priv) +{ + struct btf *btf =3D (struct btf *)priv; + struct btf_type *ta =3D btf_type_by_id(btf, *(__u32 *)a); + struct btf_type *tb =3D btf_type_by_id(btf, *(__u32 *)b); + const char *na, *nb; + + /* ta w/o name is greater than tb */ + if (!ta->name_off && tb->name_off) + return 1; + /* tb w/o name is smaller than ta */ + if (ta->name_off && !tb->name_off) + return -1; + + na =3D btf__str_by_offset(btf, ta->name_off); + nb =3D btf__str_by_offset(btf, tb->name_off); + return strcmp(na, nb); +} + +static __u32 *get_sorted_canon_types(struct btf_dedup *d, __u32 *cnt) +{ + int i, j, id, types_cnt =3D 0; + __u32 *sorted_ids; + + for (i =3D 0, id =3D d->btf->start_id; i < d->btf->nr_types; i++, id++) + if (d->map[id] =3D=3D id) + ++types_cnt; + + sorted_ids =3D calloc(types_cnt, sizeof(*sorted_ids)); + if (!sorted_ids) + return NULL; + + for (j =3D 0, i =3D 0, id =3D d->btf->start_id; i < d->btf->nr_types; i++= , id++) + if (d->map[id] =3D=3D id) + sorted_ids[j++] =3D id; + qsort_r(sorted_ids, types_cnt, sizeof(*sorted_ids), + btf_compare_type_names, d->btf); + *cnt =3D types_cnt; + + return sorted_ids; +} + /* * Compact types. * @@ -4915,11 +4961,11 @@ static int btf_dedup_resolve_fwds(struct btf_dedup = *d) */ static int btf_dedup_compact_types(struct btf_dedup *d) { - __u32 *new_offs; - __u32 next_type_id =3D d->btf->start_id; + __u32 canon_types_cnt =3D 0, canon_types_len =3D 0; + __u32 *new_offs =3D NULL, *canon_types =3D NULL; const struct btf_type *t; - void *p; - int i, id, len; + void *p, *new_types =3D NULL; + int i, id, len, err; =20 /* we are going to reuse hypot_map to store compaction remapping */ d->hypot_map[0] =3D 0; @@ -4929,36 +4975,61 @@ static int btf_dedup_compact_types(struct btf_dedup= *d) for (i =3D 0, id =3D d->btf->start_id; i < d->btf->nr_types; i++, id++) d->hypot_map[id] =3D BTF_UNPROCESSED_ID; =20 - p =3D d->btf->types_data; - - for (i =3D 0, id =3D d->btf->start_id; i < d->btf->nr_types; i++, id++) { - if (d->map[id] !=3D id) - continue; + canon_types =3D get_sorted_canon_types(d, &canon_types_cnt); + if (!canon_types) { + err =3D -ENOMEM; + goto out_err; + } =20 + for (i =3D 0; i < canon_types_cnt; i++) { + id =3D canon_types[i]; t =3D btf__type_by_id(d->btf, id); len =3D btf_type_size(t); - if (len < 0) - return len; + if (len < 0) { + err =3D len; + goto out_err; + } + canon_types_len +=3D len; + } + + new_offs =3D calloc(canon_types_cnt, sizeof(*new_offs)); + new_types =3D calloc(canon_types_len, 1); + if (!new_types || !new_offs) { + err =3D -ENOMEM; + goto out_err; + } =20 - memmove(p, t, len); - d->hypot_map[id] =3D next_type_id; - d->btf->type_offs[next_type_id - d->btf->start_id] =3D p - d->btf->types= _data; + p =3D new_types; + + for (i =3D 0; i < canon_types_cnt; i++) { + id =3D canon_types[i]; + t =3D btf__type_by_id(d->btf, id); + len =3D btf_type_size(t); + memcpy(p, t, len); + d->hypot_map[id] =3D d->btf->start_id + i; + new_offs[i] =3D p - new_types; p +=3D len; - next_type_id++; } =20 /* shrink struct btf's internal types index and update btf_header */ - d->btf->nr_types =3D next_type_id - d->btf->start_id; - d->btf->type_offs_cap =3D d->btf->nr_types; - d->btf->hdr->type_len =3D p - d->btf->types_data; - new_offs =3D libbpf_reallocarray(d->btf->type_offs, d->btf->type_offs_cap, - sizeof(*new_offs)); - if (d->btf->type_offs_cap && !new_offs) - return -ENOMEM; + free(d->btf->types_data); + free(d->btf->type_offs); + d->btf->types_data =3D new_types; d->btf->type_offs =3D new_offs; + d->btf->types_data_cap =3D canon_types_len; + d->btf->type_offs_cap =3D canon_types_cnt; + d->btf->nr_types =3D canon_types_cnt; + d->btf->hdr->type_len =3D canon_types_len; d->btf->hdr->str_off =3D d->btf->hdr->type_len; d->btf->raw_size =3D d->btf->hdr->hdr_len + d->btf->hdr->type_len + d->bt= f->hdr->str_len; + free(canon_types); return 0; + +out_err: + free(canon_types); + free(new_types); + free(new_offs); + return err; } =20 /* diff --git a/tools/testing/selftests/bpf/prog_tests/btf.c b/tools/testing/s= elftests/bpf/prog_tests/btf.c index e63d74ce046f..4dc1e2bfacbb 100644 --- a/tools/testing/selftests/bpf/prog_tests/btf.c +++ b/tools/testing/selftests/bpf/prog_tests/btf.c @@ -7025,26 +7025,26 @@ static struct btf_dedup_test dedup_tests[] =3D { }, .expect =3D { .raw_types =3D { + BTF_TYPE_FLOAT_ENC(NAME_NTH(7), 4), /* [1] */ /* int */ - BTF_TYPE_INT_ENC(NAME_NTH(5), BTF_INT_SIGNED, 0, 32, 4), /* [1] */ - /* int[16] */ - BTF_TYPE_ARRAY_ENC(1, 1, 16), /* [2] */ + BTF_TYPE_INT_ENC(NAME_NTH(5), BTF_INT_SIGNED, 0, 32, 4), /* [2] */ /* struct s { */ BTF_STRUCT_ENC(NAME_NTH(8), 5, 88), /* [3] */ - BTF_MEMBER_ENC(NAME_NTH(7), 4, 0), /* struct s *next; */ - BTF_MEMBER_ENC(NAME_NTH(1), 5, 64), /* const int *a; */ - BTF_MEMBER_ENC(NAME_NTH(2), 2, 128), /* int b[16]; */ - BTF_MEMBER_ENC(NAME_NTH(3), 1, 640), /* int c; */ - BTF_MEMBER_ENC(NAME_NTH(4), 9, 672), /* float d; */ + BTF_MEMBER_ENC(NAME_NTH(7), 7, 0), /* struct s *next; */ + BTF_MEMBER_ENC(NAME_NTH(1), 8, 64), /* const int *a; */ + BTF_MEMBER_ENC(NAME_NTH(2), 6, 128), /* int b[16]; */ + BTF_MEMBER_ENC(NAME_NTH(3), 2, 640), /* int c; */ + BTF_MEMBER_ENC(NAME_NTH(4), 1, 672), /* float d; */ + BTF_DECL_TAG_ENC(NAME_NTH(2), 3, -1), /* [4] */ + BTF_DECL_TAG_ENC(NAME_NTH(2), 3, 1), /* [5] */ + /* int[16] */ + BTF_TYPE_ARRAY_ENC(1, 2, 16), /* [6] */ /* ptr -> [3] struct s */ - BTF_PTR_ENC(3), /* [4] */ + BTF_PTR_ENC(3), /* [7] */ /* ptr -> [6] const int */ - BTF_PTR_ENC(6), /* [5] */ + BTF_PTR_ENC(9), /* [8] */ /* const -> [1] int */ - BTF_CONST_ENC(1), /* [6] */ - BTF_DECL_TAG_ENC(NAME_NTH(2), 3, -1), /* [7] */ - BTF_DECL_TAG_ENC(NAME_NTH(2), 3, 1), /* [8] */ - BTF_TYPE_FLOAT_ENC(NAME_NTH(7), 4), /* [9] */ + BTF_CONST_ENC(2), /* [9] */ BTF_END_RAW, }, BTF_STR_SEC("\0a\0b\0c\0d\0int\0float\0next\0s"), @@ -7082,10 +7082,10 @@ static struct btf_dedup_test dedup_tests[] =3D { }, .expect =3D { .raw_types =3D { - 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_STRUCT_ENC(NAME_TBD, 1, 8), /* [1] struct s */ + BTF_MEMBER_ENC(NAME_TBD, 3, 0), + BTF_STRUCT_ENC(NAME_NTH(2), 0, 0), /* [2] struct x */ + BTF_PTR_ENC(2), /* [3] ptr -> [3] */ BTF_END_RAW, }, BTF_STR_SEC("\0s\0x"), @@ -7123,15 +7123,13 @@ static struct btf_dedup_test dedup_tests[] =3D { }, .expect =3D { .raw_types =3D { - /* CU 1 */ - BTF_STRUCT_ENC(0, 0, 1), /* [1] struct {} */ - BTF_PTR_ENC(1), /* [2] ptr -> [1] */ - BTF_STRUCT_ENC(NAME_NTH(1), 1, 8), /* [3] struct s */ - BTF_MEMBER_ENC(NAME_NTH(2), 2, 0), - /* CU 2 */ - BTF_PTR_ENC(0), /* [4] ptr -> void */ - BTF_STRUCT_ENC(NAME_NTH(1), 1, 8), /* [5] struct s */ + BTF_STRUCT_ENC(NAME_NTH(1), 1, 8), /* [1] struct s */ BTF_MEMBER_ENC(NAME_NTH(2), 4, 0), + BTF_STRUCT_ENC(NAME_NTH(1), 1, 8), /* [2] struct s */ + BTF_MEMBER_ENC(NAME_NTH(2), 5, 0), + BTF_STRUCT_ENC(0, 0, 1), /* [3] struct {} */ + BTF_PTR_ENC(3), /* [5] ptr -> [1] */ + BTF_PTR_ENC(0), /* [4] ptr -> void */ BTF_END_RAW, }, BTF_STR_SEC("\0s\0x"), @@ -7182,28 +7180,28 @@ static struct btf_dedup_test dedup_tests[] =3D { BTF_ENUM_ENC(NAME_TBD, 0), BTF_ENUM_ENC(NAME_TBD, 1), BTF_FWD_ENC(NAME_TBD, 1 /* union kind_flag */), /* [3] fwd */ - BTF_TYPE_ARRAY_ENC(2, 1, 7), /* [4] array */ - BTF_STRUCT_ENC(NAME_TBD, 1, 4), /* [5] struct */ + BTF_STRUCT_ENC(NAME_TBD, 1, 4), /* [4] struct */ BTF_MEMBER_ENC(NAME_TBD, 1, 0), - BTF_UNION_ENC(NAME_TBD, 1, 4), /* [6] union */ + BTF_UNION_ENC(NAME_TBD, 1, 4), /* [5] union */ BTF_MEMBER_ENC(NAME_TBD, 1, 0), - BTF_TYPEDEF_ENC(NAME_TBD, 1), /* [7] typedef */ - BTF_PTR_ENC(0), /* [8] ptr */ - BTF_CONST_ENC(8), /* [9] const */ - BTF_VOLATILE_ENC(8), /* [10] volatile */ - BTF_RESTRICT_ENC(8), /* [11] restrict */ - BTF_FUNC_PROTO_ENC(1, 2), /* [12] func_proto */ - BTF_FUNC_PROTO_ARG_ENC(NAME_TBD, 1), - BTF_FUNC_PROTO_ARG_ENC(NAME_TBD, 18), - BTF_FUNC_ENC(NAME_TBD, 12), /* [13] func */ - BTF_TYPE_FLOAT_ENC(NAME_TBD, 2), /* [14] float */ - BTF_DECL_TAG_ENC(NAME_TBD, 13, -1), /* [15] decl_tag */ - BTF_DECL_TAG_ENC(NAME_TBD, 13, 1), /* [16] decl_tag */ - BTF_DECL_TAG_ENC(NAME_TBD, 7, -1), /* [17] decl_tag */ - BTF_TYPE_TAG_ENC(NAME_TBD, 8), /* [18] type_tag */ - BTF_TYPE_ENC(NAME_TBD, BTF_INFO_ENC(BTF_KIND_ENUM64, 0, 2), 8), /* [19]= enum64 */ + BTF_TYPEDEF_ENC(NAME_TBD, 1), /* [6] typedef */ + BTF_FUNC_ENC(NAME_TBD, 19), /* [7] func */ + BTF_TYPE_FLOAT_ENC(NAME_TBD, 2), /* [8] float */ + BTF_DECL_TAG_ENC(NAME_TBD, 7, -1), /* [9] decl_tag */ + BTF_DECL_TAG_ENC(NAME_TBD, 7, 1), /* [10] decl_tag */ + BTF_DECL_TAG_ENC(NAME_TBD, 6, -1), /* [11] decl_tag */ + BTF_TYPE_TAG_ENC(NAME_TBD, 15), /* [12] type_tag */ + BTF_TYPE_ENC(NAME_TBD, BTF_INFO_ENC(BTF_KIND_ENUM64, 0, 2), 8), /* [13]= enum64 */ BTF_ENUM64_ENC(NAME_TBD, 0, 0), BTF_ENUM64_ENC(NAME_TBD, 1, 1), + BTF_TYPE_ARRAY_ENC(2, 2, 7), /* [14] array */ + BTF_PTR_ENC(0), /* [15] ptr */ + BTF_CONST_ENC(15), /* [16] const */ + BTF_VOLATILE_ENC(15), /* [17] volatile */ + BTF_RESTRICT_ENC(15), /* [18] restrict */ + BTF_FUNC_PROTO_ENC(1, 2), /* [19] func_proto */ + BTF_FUNC_PROTO_ARG_ENC(NAME_TBD, 1), + BTF_FUNC_PROTO_ARG_ENC(NAME_TBD, 12), BTF_END_RAW, }, BTF_STR_SEC("\0A\0B\0C\0D\0E\0F\0G\0H\0I\0J\0K\0L\0M\0N\0O\0P\0Q\0R\0S\0= T\0U"), @@ -7237,9 +7235,14 @@ static struct btf_dedup_test dedup_tests[] =3D { }, .expect =3D { .raw_types =3D { + /* all allowed sizes */ + BTF_TYPE_FLOAT_ENC(NAME_NTH(3), 2), + BTF_TYPE_FLOAT_ENC(NAME_NTH(3), 4), + BTF_TYPE_FLOAT_ENC(NAME_NTH(3), 8), + BTF_TYPE_FLOAT_ENC(NAME_NTH(3), 12), + BTF_TYPE_FLOAT_ENC(NAME_NTH(3), 16), + BTF_TYPE_INT_ENC(NAME_NTH(1), BTF_INT_SIGNED, 0, 32, 8), - /* different name */ - BTF_TYPE_INT_ENC(NAME_NTH(2), BTF_INT_SIGNED, 0, 32, 8), /* different encoding */ BTF_TYPE_INT_ENC(NAME_NTH(1), BTF_INT_CHAR, 0, 32, 8), BTF_TYPE_INT_ENC(NAME_NTH(1), BTF_INT_BOOL, 0, 32, 8), @@ -7249,12 +7252,8 @@ static struct btf_dedup_test dedup_tests[] =3D { BTF_TYPE_INT_ENC(NAME_NTH(1), BTF_INT_SIGNED, 0, 27, 8), /* different byte size */ BTF_TYPE_INT_ENC(NAME_NTH(1), BTF_INT_SIGNED, 0, 32, 4), - /* all allowed sizes */ - BTF_TYPE_FLOAT_ENC(NAME_NTH(3), 2), - BTF_TYPE_FLOAT_ENC(NAME_NTH(3), 4), - BTF_TYPE_FLOAT_ENC(NAME_NTH(3), 8), - BTF_TYPE_FLOAT_ENC(NAME_NTH(3), 12), - BTF_TYPE_FLOAT_ENC(NAME_NTH(3), 16), + /* different name */ + BTF_TYPE_INT_ENC(NAME_NTH(2), BTF_INT_SIGNED, 0, 32, 8), BTF_END_RAW, }, BTF_STR_SEC("\0int\0some other int\0float"), @@ -7323,18 +7322,18 @@ static struct btf_dedup_test dedup_tests[] =3D { }, .expect =3D { .raw_types =3D { - /* int */ - BTF_TYPE_INT_ENC(0, BTF_INT_SIGNED, 0, 32, 4), /* [1] */ - /* static int t */ - BTF_VAR_ENC(NAME_NTH(2), 1, 0), /* [2] */ - /* .bss section */ /* [3] */ + /* .bss section */ /* [1] */ BTF_TYPE_ENC(NAME_NTH(1), BTF_INFO_ENC(BTF_KIND_DATASEC, 0, 1), 4), - BTF_VAR_SECINFO_ENC(2, 0, 4), - /* another static int t */ - BTF_VAR_ENC(NAME_NTH(2), 1, 0), /* [4] */ - /* another .bss section */ /* [5] */ + BTF_VAR_SECINFO_ENC(3, 0, 4), + /* another .bss section */ /* [2] */ BTF_TYPE_ENC(NAME_NTH(1), BTF_INFO_ENC(BTF_KIND_DATASEC, 0, 1), 4), BTF_VAR_SECINFO_ENC(4, 0, 4), + /* static int t */ + BTF_VAR_ENC(NAME_NTH(2), 5, 0), /* [3] */ + /* another static int t */ + BTF_VAR_ENC(NAME_NTH(2), 5, 0), /* [4] */ + /* int */ + BTF_TYPE_INT_ENC(0, BTF_INT_SIGNED, 0, 32, 4), /* [5] */ BTF_END_RAW, }, BTF_STR_SEC("\0.bss\0t"), @@ -7371,15 +7370,15 @@ static struct btf_dedup_test dedup_tests[] =3D { }, .expect =3D { .raw_types =3D { - BTF_TYPE_INT_ENC(0, BTF_INT_SIGNED, 0, 32, 4), /* [1] */ - BTF_VAR_ENC(NAME_NTH(1), 1, 0), /* [2] */ - BTF_FUNC_PROTO_ENC(0, 2), /* [3] */ - BTF_FUNC_PROTO_ARG_ENC(NAME_NTH(2), 1), - BTF_FUNC_PROTO_ARG_ENC(NAME_NTH(3), 1), - BTF_FUNC_ENC(NAME_NTH(4), 3), /* [4] */ - BTF_DECL_TAG_ENC(NAME_NTH(5), 2, -1), /* [5] */ - BTF_DECL_TAG_ENC(NAME_NTH(5), 4, -1), /* [6] */ - BTF_DECL_TAG_ENC(NAME_NTH(5), 4, 1), /* [7] */ + BTF_FUNC_ENC(NAME_NTH(4), 7), /* [1] */ + BTF_VAR_ENC(NAME_NTH(1), 6, 0), /* [2] */ + BTF_DECL_TAG_ENC(NAME_NTH(5), 2, -1), /* [3] */ + BTF_DECL_TAG_ENC(NAME_NTH(5), 1, -1), /* [4] */ + BTF_DECL_TAG_ENC(NAME_NTH(5), 1, 1), /* [5] */ + BTF_TYPE_INT_ENC(0, BTF_INT_SIGNED, 0, 32, 4), /* [6] */ + BTF_FUNC_PROTO_ENC(0, 2), /* [7] */ + BTF_FUNC_PROTO_ARG_ENC(NAME_NTH(2), 6), + BTF_FUNC_PROTO_ARG_ENC(NAME_NTH(3), 6), BTF_END_RAW, }, BTF_STR_SEC("\0t\0a1\0a2\0f\0tag"), @@ -7419,17 +7418,17 @@ static struct btf_dedup_test dedup_tests[] =3D { }, .expect =3D { .raw_types =3D { - BTF_TYPE_INT_ENC(0, BTF_INT_SIGNED, 0, 32, 4), /* [1] */ - BTF_FUNC_PROTO_ENC(0, 2), /* [2] */ - BTF_FUNC_PROTO_ARG_ENC(NAME_NTH(1), 1), - BTF_FUNC_PROTO_ARG_ENC(NAME_NTH(2), 1), - BTF_FUNC_ENC(NAME_NTH(3), 2), /* [3] */ - BTF_DECL_TAG_ENC(NAME_NTH(4), 3, -1), /* [4] */ - BTF_DECL_TAG_ENC(NAME_NTH(5), 3, -1), /* [5] */ - BTF_DECL_TAG_ENC(NAME_NTH(6), 3, -1), /* [6] */ - BTF_DECL_TAG_ENC(NAME_NTH(4), 3, 1), /* [7] */ - BTF_DECL_TAG_ENC(NAME_NTH(5), 3, 1), /* [8] */ - BTF_DECL_TAG_ENC(NAME_NTH(6), 3, 1), /* [9] */ + BTF_FUNC_ENC(NAME_NTH(3), 9), /* [1] */ + BTF_DECL_TAG_ENC(NAME_NTH(4), 1, -1), /* [2] */ + BTF_DECL_TAG_ENC(NAME_NTH(4), 1, 1), /* [3] */ + BTF_DECL_TAG_ENC(NAME_NTH(5), 1, -1), /* [4] */ + BTF_DECL_TAG_ENC(NAME_NTH(5), 1, 1), /* [5] */ + BTF_DECL_TAG_ENC(NAME_NTH(6), 1, -1), /* [6] */ + BTF_DECL_TAG_ENC(NAME_NTH(6), 1, 1), /* [7] */ + BTF_TYPE_INT_ENC(0, BTF_INT_SIGNED, 0, 32, 4), /* [8] */ + BTF_FUNC_PROTO_ENC(0, 2), /* [9] */ + BTF_FUNC_PROTO_ARG_ENC(NAME_NTH(1), 8), + BTF_FUNC_PROTO_ARG_ENC(NAME_NTH(2), 8), BTF_END_RAW, }, BTF_STR_SEC("\0a1\0a2\0f\0tag1\0tag2\0tag3"), @@ -7465,16 +7464,16 @@ static struct btf_dedup_test dedup_tests[] =3D { }, .expect =3D { .raw_types =3D { - BTF_TYPE_INT_ENC(0, BTF_INT_SIGNED, 0, 32, 4), /* [1] */ - BTF_STRUCT_ENC(NAME_NTH(1), 2, 8), /* [2] */ - BTF_MEMBER_ENC(NAME_NTH(2), 1, 0), - BTF_MEMBER_ENC(NAME_NTH(3), 1, 32), - BTF_DECL_TAG_ENC(NAME_NTH(4), 2, -1), /* [3] */ - BTF_DECL_TAG_ENC(NAME_NTH(5), 2, -1), /* [4] */ - BTF_DECL_TAG_ENC(NAME_NTH(6), 2, -1), /* [5] */ - BTF_DECL_TAG_ENC(NAME_NTH(4), 2, 1), /* [6] */ - BTF_DECL_TAG_ENC(NAME_NTH(5), 2, 1), /* [7] */ - BTF_DECL_TAG_ENC(NAME_NTH(6), 2, 1), /* [8] */ + BTF_STRUCT_ENC(NAME_NTH(1), 2, 8), /* [1] */ + BTF_MEMBER_ENC(NAME_NTH(2), 8, 0), + BTF_MEMBER_ENC(NAME_NTH(3), 8, 32), + BTF_DECL_TAG_ENC(NAME_NTH(4), 1, -1), /* [2] */ + BTF_DECL_TAG_ENC(NAME_NTH(4), 1, 1), /* [3] */ + BTF_DECL_TAG_ENC(NAME_NTH(5), 1, -1), /* [4] */ + BTF_DECL_TAG_ENC(NAME_NTH(5), 1, 1), /* [5] */ + BTF_DECL_TAG_ENC(NAME_NTH(6), 1, -1), /* [6] */ + BTF_DECL_TAG_ENC(NAME_NTH(6), 1, 1), /* [7] */ + BTF_TYPE_INT_ENC(0, BTF_INT_SIGNED, 0, 32, 4), /* [8] */ BTF_END_RAW, }, BTF_STR_SEC("\0t\0m1\0m2\0tag1\0tag2\0tag3"), @@ -7500,11 +7499,11 @@ static struct btf_dedup_test dedup_tests[] =3D { }, .expect =3D { .raw_types =3D { - BTF_TYPE_INT_ENC(0, BTF_INT_SIGNED, 0, 32, 4), /* [1] */ - BTF_TYPEDEF_ENC(NAME_NTH(1), 1), /* [2] */ - BTF_DECL_TAG_ENC(NAME_NTH(2), 2, -1), /* [3] */ - BTF_DECL_TAG_ENC(NAME_NTH(3), 2, -1), /* [4] */ - BTF_DECL_TAG_ENC(NAME_NTH(4), 2, -1), /* [5] */ + BTF_TYPEDEF_ENC(NAME_NTH(1), 5), /* [1] */ + BTF_DECL_TAG_ENC(NAME_NTH(2), 1, -1), /* [2] */ + BTF_DECL_TAG_ENC(NAME_NTH(3), 1, -1), /* [3] */ + BTF_DECL_TAG_ENC(NAME_NTH(4), 1, -1), /* [4] */ + BTF_TYPE_INT_ENC(0, BTF_INT_SIGNED, 0, 32, 4), /* [5] */ BTF_END_RAW, }, BTF_STR_SEC("\0t\0tag1\0tag2\0tag3"), @@ -7533,12 +7532,12 @@ static struct btf_dedup_test dedup_tests[] =3D { .expect =3D { .raw_types =3D { /* ptr -> tag2 -> tag1 -> int */ - BTF_TYPE_INT_ENC(0, BTF_INT_SIGNED, 0, 32, 4), /* [1] */ - BTF_TYPE_TAG_ENC(NAME_NTH(1), 1), /* [2] */ - BTF_TYPE_TAG_ENC(NAME_NTH(2), 2), /* [3] */ - BTF_PTR_ENC(3), /* [4] */ + BTF_TYPE_TAG_ENC(NAME_NTH(1), 3), /* [1] */ + BTF_TYPE_TAG_ENC(NAME_NTH(2), 1), /* [2] */ + BTF_TYPE_INT_ENC(0, BTF_INT_SIGNED, 0, 32, 4), /* [3] */ + BTF_PTR_ENC(2), /* [4] */ /* ptr -> tag1 -> int */ - BTF_PTR_ENC(2), /* [5] */ + BTF_PTR_ENC(1), /* [5] */ BTF_END_RAW, }, BTF_STR_SEC("\0tag1\0tag2"), @@ -7563,13 +7562,13 @@ static struct btf_dedup_test dedup_tests[] =3D { .expect =3D { .raw_types =3D { /* ptr -> tag2 -> tag1 -> int */ - BTF_TYPE_INT_ENC(0, BTF_INT_SIGNED, 0, 32, 4), /* [1] */ - BTF_TYPE_TAG_ENC(NAME_NTH(1), 1), /* [2] */ - BTF_TYPE_TAG_ENC(NAME_NTH(2), 2), /* [3] */ - BTF_PTR_ENC(3), /* [4] */ + BTF_TYPE_TAG_ENC(NAME_NTH(1), 4), /* [1] */ + BTF_TYPE_TAG_ENC(NAME_NTH(2), 1), /* [2] */ /* ptr -> tag2 -> int */ - BTF_TYPE_TAG_ENC(NAME_NTH(2), 1), /* [5] */ - BTF_PTR_ENC(5), /* [6] */ + BTF_TYPE_TAG_ENC(NAME_NTH(2), 4), /* [3] */ + BTF_TYPE_INT_ENC(0, BTF_INT_SIGNED, 0, 32, 4), /* [4] */ + BTF_PTR_ENC(2), /* [5] */ + BTF_PTR_ENC(3), /* [6] */ BTF_END_RAW, }, BTF_STR_SEC("\0tag1\0tag2"), @@ -7594,15 +7593,13 @@ static struct btf_dedup_test dedup_tests[] =3D { }, .expect =3D { .raw_types =3D { - /* ptr -> tag2 -> tag1 -> int */ - BTF_TYPE_INT_ENC(0, BTF_INT_SIGNED, 0, 32, 4), /* [1] */ - BTF_TYPE_TAG_ENC(NAME_NTH(1), 1), /* [2] */ - BTF_TYPE_TAG_ENC(NAME_NTH(2), 2), /* [3] */ - BTF_PTR_ENC(3), /* [4] */ - /* ptr -> tag1 -> tag2 -> int */ - BTF_TYPE_TAG_ENC(NAME_NTH(2), 1), /* [5] */ - BTF_TYPE_TAG_ENC(NAME_NTH(1), 5), /* [6] */ - BTF_PTR_ENC(6), /* [7] */ + BTF_TYPE_TAG_ENC(NAME_NTH(1), 5), /* [1] */ + BTF_TYPE_TAG_ENC(NAME_NTH(1), 4), /* [2] */ + BTF_TYPE_TAG_ENC(NAME_NTH(2), 1), /* [3] */ + BTF_TYPE_TAG_ENC(NAME_NTH(2), 5), /* [4] */ + BTF_TYPE_INT_ENC(0, BTF_INT_SIGNED, 0, 32, 4), /* [5] */ + BTF_PTR_ENC(3), /* [6] */ + BTF_PTR_ENC(2), /* [7] */ BTF_END_RAW, }, BTF_STR_SEC("\0tag1\0tag2"), @@ -7626,14 +7623,12 @@ static struct btf_dedup_test dedup_tests[] =3D { }, .expect =3D { .raw_types =3D { - /* ptr -> tag1 -> int */ - BTF_TYPE_INT_ENC(0, BTF_INT_SIGNED, 0, 32, 4), /* [1] */ - BTF_TYPE_TAG_ENC(NAME_NTH(1), 1), /* [2] */ - BTF_PTR_ENC(2), /* [3] */ - /* ptr -> tag1 -> long */ - BTF_TYPE_INT_ENC(0, BTF_INT_SIGNED, 0, 64, 8), /* [4] */ - BTF_TYPE_TAG_ENC(NAME_NTH(1), 4), /* [5] */ - BTF_PTR_ENC(5), /* [6] */ + BTF_TYPE_TAG_ENC(NAME_NTH(1), 3), /* [1] */ + BTF_TYPE_TAG_ENC(NAME_NTH(1), 5), /* [2] */ + BTF_TYPE_INT_ENC(0, BTF_INT_SIGNED, 0, 32, 4), /* [3] */ + BTF_PTR_ENC(1), /* [4] */ + BTF_TYPE_INT_ENC(0, BTF_INT_SIGNED, 0, 64, 8), /* [5] */ + BTF_PTR_ENC(2), /* [6] */ BTF_END_RAW, }, BTF_STR_SEC("\0tag1"), @@ -7656,10 +7651,10 @@ static struct btf_dedup_test dedup_tests[] =3D { }, .expect =3D { .raw_types =3D { - BTF_TYPE_INT_ENC(0, BTF_INT_SIGNED, 0, 32, 4), /* [1] */ - BTF_TYPE_TAG_ENC(NAME_NTH(1), 1), /* [2] */ - BTF_TYPE_ENC(NAME_NTH(2), BTF_INFO_ENC(BTF_KIND_STRUCT, 1, 1), 4), /* [= 3] */ + BTF_TYPE_ENC(NAME_NTH(2), BTF_INFO_ENC(BTF_KIND_STRUCT, 1, 1), 4), /* [= 1] */ BTF_MEMBER_ENC(NAME_NTH(3), 2, BTF_MEMBER_OFFSET(0, 0)), + BTF_TYPE_TAG_ENC(NAME_NTH(1), 3), /* [2] */ + BTF_TYPE_INT_ENC(0, BTF_INT_SIGNED, 0, 32, 4), /* [3] */ BTF_END_RAW, }, BTF_STR_SEC("\0tag1\0t\0m"), @@ -7861,10 +7856,10 @@ static struct btf_dedup_test dedup_tests[] =3D { .expect =3D { .raw_types =3D { BTF_STRUCT_ENC(NAME_NTH(1), 1, 4), /* [1] */ - BTF_MEMBER_ENC(NAME_NTH(2), 2, 0), - BTF_TYPE_INT_ENC(0, BTF_INT_SIGNED, 0, 32, 4), /* [2] */ - BTF_PTR_ENC(1), /* [3] */ - BTF_TYPEDEF_ENC(NAME_NTH(3), 3), /* [4] */ + BTF_MEMBER_ENC(NAME_NTH(2), 3, 0), + BTF_TYPEDEF_ENC(NAME_NTH(3), 4), /* [2] */ + BTF_TYPE_INT_ENC(0, BTF_INT_SIGNED, 0, 32, 4), /* [3] */ + BTF_PTR_ENC(1), /* [4] */ BTF_END_RAW, }, BTF_STR_SEC("\0foo\0x\0foo_ptr"), @@ -7901,10 +7896,10 @@ static struct btf_dedup_test dedup_tests[] =3D { .expect =3D { .raw_types =3D { BTF_UNION_ENC(NAME_NTH(1), 1, 4), /* [1] */ - BTF_MEMBER_ENC(NAME_NTH(2), 2, 0), - BTF_TYPE_INT_ENC(0, BTF_INT_SIGNED, 0, 32, 4), /* [2] */ - BTF_PTR_ENC(1), /* [3] */ - BTF_TYPEDEF_ENC(NAME_NTH(3), 3), /* [4] */ + BTF_MEMBER_ENC(NAME_NTH(2), 3, 0), + BTF_TYPEDEF_ENC(NAME_NTH(3), 4), /* [2] */ + BTF_TYPE_INT_ENC(0, BTF_INT_SIGNED, 0, 32, 4), /* [3] */ + BTF_PTR_ENC(1), /* [4] */ BTF_END_RAW, }, BTF_STR_SEC("\0foo\0x\0foo_ptr"), @@ -7940,14 +7935,12 @@ static struct btf_dedup_test dedup_tests[] =3D { }, .expect =3D { .raw_types =3D { - /* CU 1 */ BTF_STRUCT_ENC(NAME_NTH(1), 1, 4), /* [1] */ - BTF_MEMBER_ENC(NAME_NTH(2), 2, 0), - BTF_TYPE_INT_ENC(0, BTF_INT_SIGNED, 0, 32, 4), /* [2] */ - /* CU 2 */ - BTF_FWD_ENC(NAME_NTH(3), 1), /* [3] */ - BTF_PTR_ENC(3), /* [4] */ - BTF_TYPEDEF_ENC(NAME_NTH(3), 4), /* [5] */ + BTF_MEMBER_ENC(NAME_NTH(2), 4, 0), + BTF_FWD_ENC(NAME_NTH(3), 1), /* [2] */ + BTF_TYPEDEF_ENC(NAME_NTH(3), 5), /* [3] */ + BTF_TYPE_INT_ENC(0, BTF_INT_SIGNED, 0, 32, 4), /* [4] */ + BTF_PTR_ENC(2), /* [5] */ BTF_END_RAW, }, BTF_STR_SEC("\0foo\0x\0foo_ptr"), @@ -7990,18 +7983,15 @@ static struct btf_dedup_test dedup_tests[] =3D { }, .expect =3D { .raw_types =3D { - /* CU 1 */ BTF_STRUCT_ENC(NAME_NTH(1), 1, 4), /* [1] */ - BTF_MEMBER_ENC(NAME_NTH(2), 2, 0), - BTF_TYPE_INT_ENC(0, BTF_INT_SIGNED, 0, 32, 4), /* [2] */ - /* CU 2 */ - BTF_FWD_ENC(NAME_NTH(1), 0), /* [3] */ - BTF_PTR_ENC(3), /* [4] */ - BTF_TYPEDEF_ENC(NAME_NTH(4), 4), /* [5] */ - /* CU 3 */ - BTF_STRUCT_ENC(NAME_NTH(1), 2, 8), /* [6] */ - BTF_MEMBER_ENC(NAME_NTH(2), 2, 0), - BTF_MEMBER_ENC(NAME_NTH(3), 2, 0), + BTF_MEMBER_ENC(NAME_NTH(2), 5, 0), + BTF_FWD_ENC(NAME_NTH(1), 0), /* [2] */ + BTF_STRUCT_ENC(NAME_NTH(1), 2, 8), /* [3] */ + BTF_MEMBER_ENC(NAME_NTH(2), 5, 0), + BTF_MEMBER_ENC(NAME_NTH(3), 5, 0), + BTF_TYPEDEF_ENC(NAME_NTH(4), 6), /* [4] */ + BTF_TYPE_INT_ENC(0, BTF_INT_SIGNED, 0, 32, 4), /* [5] */ + BTF_PTR_ENC(2), /* [6] */ BTF_END_RAW, }, BTF_STR_SEC("\0foo\0x\0y\0foo_ptr"), diff --git a/tools/testing/selftests/bpf/prog_tests/btf_dedup_split.c b/too= ls/testing/selftests/bpf/prog_tests/btf_dedup_split.c index d9024c7a892a..e50c290b2d8c 100644 --- a/tools/testing/selftests/bpf/prog_tests/btf_dedup_split.c +++ b/tools/testing/selftests/bpf/prog_tests/btf_dedup_split.c @@ -311,18 +311,18 @@ static void test_split_struct_duped() { "[5] STRUCT 's1' size=3D16 vlen=3D2\n" "\t'f1' type_id=3D2 bits_offset=3D0\n" "\t'f2' type_id=3D4 bits_offset=3D64", - "[6] PTR '(anon)' type_id=3D8", - "[7] PTR '(anon)' type_id=3D9", - "[8] STRUCT 's1' size=3D16 vlen=3D2\n" - "\t'f1' type_id=3D6 bits_offset=3D0\n" - "\t'f2' type_id=3D7 bits_offset=3D64", - "[9] STRUCT 's2' size=3D40 vlen=3D4\n" - "\t'f1' type_id=3D6 bits_offset=3D0\n" - "\t'f2' type_id=3D7 bits_offset=3D64\n" + "[6] STRUCT 's1' size=3D16 vlen=3D2\n" + "\t'f1' type_id=3D9 bits_offset=3D0\n" + "\t'f2' type_id=3D10 bits_offset=3D64", + "[7] STRUCT 's2' size=3D40 vlen=3D4\n" + "\t'f1' type_id=3D9 bits_offset=3D0\n" + "\t'f2' type_id=3D10 bits_offset=3D64\n" "\t'f3' type_id=3D1 bits_offset=3D128\n" - "\t'f4' type_id=3D8 bits_offset=3D192", - "[10] STRUCT 's3' size=3D8 vlen=3D1\n" - "\t'f1' type_id=3D7 bits_offset=3D0"); + "\t'f4' type_id=3D6 bits_offset=3D192", + "[8] STRUCT 's3' size=3D8 vlen=3D1\n" + "\t'f1' type_id=3D10 bits_offset=3D0", + "[9] PTR '(anon)' type_id=3D6", + "[10] PTR '(anon)' type_id=3D7"); =20 cleanup: btf__free(btf2); @@ -385,13 +385,13 @@ static void test_split_dup_struct_in_cu() =20 VALIDATE_RAW_BTF( btf1, - "[1] INT 'int' size=3D4 bits_offset=3D0 nr_bits=3D32 encoding=3DSIGNED", - "[2] STRUCT 's' size=3D8 vlen=3D2\n" - "\t'a' type_id=3D3 bits_offset=3D0\n" - "\t'b' type_id=3D3 bits_offset=3D0", - "[3] STRUCT '(anon)' size=3D8 vlen=3D2\n" - "\t'f1' type_id=3D1 bits_offset=3D0\n" - "\t'f2' type_id=3D1 bits_offset=3D32"); + "[1] STRUCT '(anon)' size=3D8 vlen=3D2\n" + "\t'f1' type_id=3D2 bits_offset=3D0\n" + "\t'f2' type_id=3D2 bits_offset=3D32", + "[2] INT 'int' size=3D4 bits_offset=3D0 nr_bits=3D32 encoding=3DSIGNED", + "[3] STRUCT 's' size=3D8 vlen=3D2\n" + "\t'a' type_id=3D1 bits_offset=3D0\n" + "\t'b' type_id=3D1 bits_offset=3D0"); =20 /* and add the same data on top of it */ btf2 =3D btf__new_empty_split(btf1); @@ -402,13 +402,13 @@ static void test_split_dup_struct_in_cu() =20 VALIDATE_RAW_BTF( btf2, - "[1] INT 'int' size=3D4 bits_offset=3D0 nr_bits=3D32 encoding=3DSIGNED", - "[2] STRUCT 's' size=3D8 vlen=3D2\n" - "\t'a' type_id=3D3 bits_offset=3D0\n" - "\t'b' type_id=3D3 bits_offset=3D0", - "[3] STRUCT '(anon)' size=3D8 vlen=3D2\n" - "\t'f1' type_id=3D1 bits_offset=3D0\n" - "\t'f2' type_id=3D1 bits_offset=3D32", + "[1] STRUCT '(anon)' size=3D8 vlen=3D2\n" + "\t'f1' type_id=3D2 bits_offset=3D0\n" + "\t'f2' type_id=3D2 bits_offset=3D32", + "[2] INT 'int' size=3D4 bits_offset=3D0 nr_bits=3D32 encoding=3DSIGNED", + "[3] STRUCT 's' size=3D8 vlen=3D2\n" + "\t'a' type_id=3D1 bits_offset=3D0\n" + "\t'b' type_id=3D1 bits_offset=3D0", "[4] INT 'int' size=3D4 bits_offset=3D0 nr_bits=3D32 encoding=3DSIGNED", "[5] STRUCT 's' size=3D8 vlen=3D2\n" "\t'a' type_id=3D6 bits_offset=3D0\n" @@ -427,13 +427,13 @@ static void test_split_dup_struct_in_cu() /* after dedup it should match the original data */ VALIDATE_RAW_BTF( btf2, - "[1] INT 'int' size=3D4 bits_offset=3D0 nr_bits=3D32 encoding=3DSIGNED", - "[2] STRUCT 's' size=3D8 vlen=3D2\n" - "\t'a' type_id=3D3 bits_offset=3D0\n" - "\t'b' type_id=3D3 bits_offset=3D0", - "[3] STRUCT '(anon)' size=3D8 vlen=3D2\n" - "\t'f1' type_id=3D1 bits_offset=3D0\n" - "\t'f2' type_id=3D1 bits_offset=3D32"); + "[1] STRUCT '(anon)' size=3D8 vlen=3D2\n" + "\t'f1' type_id=3D2 bits_offset=3D0\n" + "\t'f2' type_id=3D2 bits_offset=3D32", + "[2] INT 'int' size=3D4 bits_offset=3D0 nr_bits=3D32 encoding=3DSIGNED", + "[3] STRUCT 's' size=3D8 vlen=3D2\n" + "\t'a' type_id=3D1 bits_offset=3D0\n" + "\t'b' type_id=3D1 bits_offset=3D0"); =20 cleanup: btf__free(btf2); --=20 2.34.1 From nobody Mon Nov 25 07:25:54 2024 Received: from mail-pl1-f179.google.com (mail-pl1-f179.google.com [209.85.214.179]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 755838F5E; Tue, 29 Oct 2024 00:22:29 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.214.179 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1730161351; cv=none; b=kuTTdpyUOTkI5sk7Tb27+jbiMuNZca6I7AIqST/BMp8oV+wqSAm2OcK7rqbDJMnrE/HmndwQdbhaAykHAkfYXkVIRCv+wR02Ccojg/OCf1Bzpe9P10T4opkJGqBpYklWnIVlqPdk645trL55CCdFVK0kRJqwQxpqNTrKHHB1CRw= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1730161351; c=relaxed/simple; bh=fcC1iFJKxdZfE7f4KdQ33h051tuX1f6s3QXqbwjKvaA=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=Hkw0/iD28N789ZUQRKua7+5YdS4JyHDrxVD1msSmEUkHcFwymaRb/I7/yCP9DBXi4lqmPPki4mk3scJ4t3D3clrOlh5AoQ6tHb5nl7ekib+/0pNT34jqtjI9ZCgN1cCOq6/QLVj7xigzgfCWqbFKUb7P3lyE58Toq6B8IfYwyOU= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com; spf=pass smtp.mailfrom=gmail.com; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b=G7hgt42/; arc=none smtp.client-ip=209.85.214.179 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=gmail.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="G7hgt42/" Received: by mail-pl1-f179.google.com with SMTP id d9443c01a7336-20c70abba48so38414265ad.0; Mon, 28 Oct 2024 17:22:29 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1730161349; x=1730766149; darn=vger.kernel.org; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=7Jdi+t099FdxC155FhQSAwxqJnHWS1BYqwkZvlhr0Dw=; b=G7hgt42/vs4m7ivnOJ6blQjKdJF6AZuA6QJNF8jAFSHplS0SdLxwH2PJb8gtjAjh3j Gt19M96z68d2V7c8XFhPs2mA/Bmx48AWl6Cm6ihwXQKDLkBxFslBbfIN60Do7vXTJ3aV cYAplVSq24h92z79sezxwXxgPBsrgOnrRpgV6JKjNHljagdxneTo9FCio0fJQ0ZXXqc8 qca6JhdgMeHj3T6LKtwRnC7PaO0YbkTEmp92fUzH6ECdI4GKUOLvfQlWVjqU9FPDNVx/ tAphfFq57iDcHxpiju6rYNHzk4gjh0vbA5CDvvG2Mxy1aCzQbUKaNO6DFMFPQgXMES3i tLDw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1730161349; x=1730766149; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=7Jdi+t099FdxC155FhQSAwxqJnHWS1BYqwkZvlhr0Dw=; b=bOwWEU+m/vD2k1zO050jrP7ntDMuH/6TznidfSRdtUWWnYaFIIHbp1UYKKWHPzTwo2 sHKCSX3SB4Uvd1RSpYQF2KqVBNZvXJxiQAOqo8I24mVZwWyZCHHGxCvm5uzKsYEfyrLX JX7WWnxhT1Rypf7n/ah59Vx2SnMo2z2UpFEY4wwtnSHHVhQHzJoUrj9Tu0tGWCkvw/Cm 9/8a3Jl2SdV2aoV6DcGioGobtYDP/3b6R8YI0soHPd0QlbvKlhnSG/4rWBDfYNtkxkOE zLn31ogThkI3jIRCPXDAcBwB1R1m93HWMks8wA5u2Gqy+PyJMdkQJnICa8F8i6kPlrhx Vi5Q== X-Forwarded-Encrypted: i=1; AJvYcCUef3EsLwN4eF/g4gJ4I+Ben6iDw+Zb8N9wKgawKUxhN2l/ebxF+KWBIHry6YXL7f5uGN5gx5RTU1t01mAZku+w@vger.kernel.org, AJvYcCVO+7CrLjDK1fUrBJoXwUFBkoqgCQzqsbTmX5lYbBkjKA3KtJsJKK02G0nUs/cQTGRcbBc=@vger.kernel.org, AJvYcCWCLoPp/EyspuuJqtbRjZAcCfEliHZ6PbWnups1WvNmKvWcYZrVWRVGHRyXvVkASm8uvObpiYZsX2ofju3NdChaWYNV@vger.kernel.org, AJvYcCXvm3NOdNC/awCJS5DnEwnCXjwpakk4OBz9bSTUzMYPvWtlwt9kwQ6Q0uds2HPCUYNrlcxG7ywGC+dDcRKl@vger.kernel.org X-Gm-Message-State: AOJu0YxA5f2L7ristGF6Z/UEqi0eFqWW1WNRTf40f6wNSYG11RXo7Mm1 udgsFH3JmGp4LG/LqOELmWtQnAEorZJdnO+WaVt86bsPl6J8hy6GRcqqiG9U X-Google-Smtp-Source: AGHT+IGB30CXe1oQBemeYR93KMMMhpUXeFg9EpzOhIsD5obt8Oeze7ecpx1bRZmToLJjfi0Nl3d8gA== X-Received: by 2002:a17:90a:6fe3:b0:2e2:e6c8:36a7 with SMTP id 98e67ed59e1d1-2e8f10a75bdmr12849246a91.31.1730161348713; Mon, 28 Oct 2024 17:22:28 -0700 (PDT) Received: from pengdl-ub.localdomain ([106.37.77.202]) by smtp.gmail.com with ESMTPSA id 98e67ed59e1d1-2e77e48e4a2sm10175507a91.2.2024.10.28.17.22.24 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 28 Oct 2024 17:22:27 -0700 (PDT) From: Donglin Peng To: andrii@kernel.org, eddyz87@gmail.com Cc: ast@kernel.org, rostedt@goodmis.org, mhiramat@kernel.org, bpf@vger.kernel.org, linux-trace-kernel@vger.kernel.org, linux-kselftest@vger.kernel.org, linux-kernel@vger.kernel.org, Donglin Peng Subject: [PATCH v4 2/3] bpf: Using binary search to improve the performance of btf_find_by_name_kind Date: Tue, 29 Oct 2024 08:22:07 +0800 Message-Id: <20241029002208.1947947-3-dolinux.peng@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20241029002208.1947947-1-dolinux.peng@gmail.com> References: <20241029002208.1947947-1-dolinux.peng@gmail.com> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset="utf-8" Currently, we are only using the linear search method to find the type id by the name, which has a time complexity of O(n). This change involves sorting the names of btf types in ascending order and using binary search, which has a time complexity of O(log(n)). This idea was inspired by the following patch: 60443c88f3a8 ("kallsyms: Improve the performance of kallsyms_lookup_name()"= ). At present, this improvement is only for searching in vmlinux's and module's BTFs. Another change is the search direction, where we search the BTF first and then its base, the type id of the first matched btf_type will be returned. Here is a time-consuming result that finding 87590 type ids by their names = in vmlinux's BTF. Before: 158426 ms After: 114 ms The average lookup performance has improved more than 1000x in the above sc= enario. Tested-by: Masami Hiramatsu (Google) Signed-off-by: Donglin Peng --- v4: - move the modification of libbpf to another patch v3: - Link: https://lore.kernel.org/all/20240608140835.965949-1-dolinux.peng@g= mail.com/ - Sort btf_types during build process other than during boot, to reduce the overhead of memory and boot time. v2: - Link: https://lore.kernel.org/all/20230909091646.420163-1-pengdonglin@sa= ngfor.com.cn --- include/linux/btf.h | 1 + kernel/bpf/btf.c | 157 ++++++++++++++++++++++++++++++++++++++++---- 2 files changed, 147 insertions(+), 11 deletions(-) diff --git a/include/linux/btf.h b/include/linux/btf.h index b8a583194c4a..64c35aaa22fa 100644 --- a/include/linux/btf.h +++ b/include/linux/btf.h @@ -216,6 +216,7 @@ bool btf_is_module(const struct btf *btf); bool btf_is_vmlinux(const struct btf *btf); struct module *btf_try_get_module(const struct btf *btf); u32 btf_nr_types(const struct btf *btf); +u32 btf_type_cnt(const struct btf *btf); struct btf *btf_base_btf(const struct btf *btf); bool btf_member_is_reg_int(const struct btf *btf, const struct btf_type *s, const struct btf_member *m, diff --git a/kernel/bpf/btf.c b/kernel/bpf/btf.c index 5cd1c7a23848..6d0d58989640 100644 --- a/kernel/bpf/btf.c +++ b/kernel/bpf/btf.c @@ -262,6 +262,7 @@ struct btf { u32 data_size; refcount_t refcnt; u32 id; + u32 nr_types_sorted; struct rcu_head rcu; struct btf_kfunc_set_tab *kfunc_set_tab; struct btf_id_dtor_kfunc_tab *dtor_kfunc_tab; @@ -548,23 +549,102 @@ u32 btf_nr_types(const struct btf *btf) return total; } =20 -s32 btf_find_by_name_kind(const struct btf *btf, const char *name, u8 kind) +u32 btf_type_cnt(const struct btf *btf) +{ + return btf->start_id + btf->nr_types; +} + +static s32 btf_find_by_name_bsearch(const struct btf *btf, const char *nam= e, + int *start, int *end) { const struct btf_type *t; - const char *tname; - u32 i, total; + const char *name_buf; + int low, low_start, mid, high, high_end; + int ret, start_id; + + start_id =3D btf->base_btf ? btf->start_id : 1; + low_start =3D low =3D start_id; + high_end =3D high =3D start_id + btf->nr_types_sorted - 1; + + while (low <=3D high) { + mid =3D low + (high - low) / 2; + t =3D btf_type_by_id(btf, mid); + name_buf =3D btf_name_by_offset(btf, t->name_off); + ret =3D strcmp(name, name_buf); + if (ret > 0) + low =3D mid + 1; + else if (ret < 0) + high =3D mid - 1; + else + break; + } =20 - total =3D btf_nr_types(btf); - for (i =3D 1; i < total; i++) { - t =3D btf_type_by_id(btf, i); - if (BTF_INFO_KIND(t->info) !=3D kind) - continue; + if (low > high) + return -ESRCH; =20 - tname =3D btf_name_by_offset(btf, t->name_off); - if (!strcmp(tname, name)) - return i; + if (start) { + low =3D mid; + while (low > low_start) { + t =3D btf_type_by_id(btf, low-1); + name_buf =3D btf_name_by_offset(btf, t->name_off); + if (strcmp(name, name_buf)) + break; + low--; + } + *start =3D low; + } + + if (end) { + high =3D mid; + while (high < high_end) { + t =3D btf_type_by_id(btf, high+1); + name_buf =3D btf_name_by_offset(btf, t->name_off); + if (strcmp(name, name_buf)) + break; + high++; + } + *end =3D high; } =20 + return mid; +} + +s32 btf_find_by_name_kind(const struct btf *btf, const char *name, u8 kind) +{ + const struct btf_type *t; + const char *tname; + int start, end; + s32 id, total; + + do { + if (btf->nr_types_sorted) { + /* binary search */ + id =3D btf_find_by_name_bsearch(btf, name, &start, &end); + if (id > 0) { + while (start <=3D end) { + t =3D btf_type_by_id(btf, start); + if (BTF_INFO_KIND(t->info) =3D=3D kind) + return start; + start++; + } + } + } else { + /* linear search */ + total =3D btf_type_cnt(btf); + for (id =3D btf->base_btf ? btf->start_id : 1; + id < total; id++) { + t =3D btf_type_by_id(btf, id); + if (BTF_INFO_KIND(t->info) !=3D kind) + continue; + + tname =3D btf_name_by_offset(btf, t->name_off); + if (!strcmp(tname, name)) + return id; + } + } + btf =3D btf->base_btf; + } while (btf); + return -ENOENT; } =20 @@ -6141,6 +6221,53 @@ int get_kern_ctx_btf_id(struct bpf_verifier_log *log= , enum bpf_prog_type prog_ty return kctx_type_id; } =20 +static int btf_check_sort(struct btf *btf, int start_id) +{ + int i, n, nr_names =3D 0; + + n =3D btf_nr_types(btf); + for (i =3D start_id; i < n; i++) { + const struct btf_type *t; + const char *name; + + t =3D btf_type_by_id(btf, i); + if (!t) + return -EINVAL; + + name =3D btf_str_by_offset(btf, t->name_off); + if (!str_is_empty(name)) + nr_names++; + } + + for (i =3D 0; i < nr_names - 1; i++) { + const struct btf_type *t1, *t2; + const char *s1, *s2; + + t1 =3D btf_type_by_id(btf, start_id + i); + if (!t1) + return -EINVAL; + + s1 =3D btf_str_by_offset(btf, t1->name_off); + if (str_is_empty(s1)) + goto out; + + t2 =3D btf_type_by_id(btf, start_id + i + 1); + if (!t2) + return -EINVAL; + + s2 =3D btf_str_by_offset(btf, t2->name_off); + if (str_is_empty(s2)) + goto out; + + if (strcmp(s1, s2) > 0) + goto out; + } + + btf->nr_types_sorted =3D nr_names; +out: + return 0; +} + BTF_ID_LIST(bpf_ctx_convert_btf_id) BTF_ID(struct, bpf_ctx_convert) =20 @@ -6212,6 +6339,10 @@ struct btf *btf_parse_vmlinux(void) if (IS_ERR(btf)) goto err_out; =20 + err =3D btf_check_sort(btf, 1); + if (err) + goto err_out; + /* btf_parse_vmlinux() runs under bpf_verifier_lock */ bpf_ctx_convert.t =3D btf_type_by_id(btf, bpf_ctx_convert_btf_id[0]); err =3D btf_alloc_id(btf); @@ -6315,6 +6446,10 @@ static struct btf *btf_parse_module(const char *modu= le_name, const void *data, base_btf =3D vmlinux_btf; } =20 + err =3D btf_check_sort(btf, btf_nr_types(base_btf)); + if (err) + goto errout; + btf_verifier_env_free(env); refcount_set(&btf->refcnt, 1); return btf; --=20 2.34.1 From nobody Mon Nov 25 07:25:54 2024 Received: from mail-pl1-f175.google.com (mail-pl1-f175.google.com [209.85.214.175]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 5325DD529; Tue, 29 Oct 2024 00:22:34 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.214.175 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1730161356; cv=none; b=cRXF3qwZ2a7GbOGcj+U1Vtlh4FxsDhB9oRD5qRIoyxA9w+JqUS1Ii6JKdBqjPriAtcmO4b+sx6jK/GKqd5YuGVa9r90GCitCSpIVI7qU1fn7lhk3zXyPob3vR7aS7V0WGoaElFhLlM0jClB4+hQMKjSd3pdlgw67t/XXTRSgnLI= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1730161356; c=relaxed/simple; bh=7snpNK2X7OssbINrb13dvlgAk1CmGzOUvCtAWtWASZ8=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=R6KLXkouF3lAFZd6b2CEdNEkgkoh9N5Sqrpw7Oh3YPWMYZDsxyBidMKmjsgdwK+vuex5KtOmQm52hNatMIHyFHXuSNEjDgthgIVfpNNISFWme6LmOIFq8f5SB9hlmOGccZXhfydyYgozN1uxnQkA8/4A8NizfR6Nt3Hnwwo/09o= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com; spf=pass smtp.mailfrom=gmail.com; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b=h656d6Ue; arc=none smtp.client-ip=209.85.214.175 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=gmail.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="h656d6Ue" Received: by mail-pl1-f175.google.com with SMTP id d9443c01a7336-20ce5e3b116so33234105ad.1; Mon, 28 Oct 2024 17:22:34 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1730161354; x=1730766154; darn=vger.kernel.org; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=i9yLdCYlpqPTX58B/EOpzxj/uwBLH6nW8WmtXaMecqk=; b=h656d6Ue6I+ZP7lZS0hRF8v+r7+stYfQFG6pJJhKcbtbxDnJ0FGyUnSC0su0B/z+q4 tOqkecUwiIOgxJZ/sIsZw+UZDnTEBkAg1+vOMpR/Df9cMcXv2xl60yOmo5rBfN5k1Iuq Vwgqn6W6jK0iK9lV+z3Z2uYX8nXk9tTtgaulXgfTXU/b589kUZcouqK7KOc8tiU2SDC1 G6VYPsW0gqQ41zHwAHIdjhzEWFFBT+MRg8wxhFU9AgvQy0MeXwFJO7QqZTbuPA9JQmxj 0Yd1HU9WKCsBmN7xZQKQYKlO4Q1HUmfw6oycJe8oUqkVuuDMauKALPsVdKYoQxDi6uwk iv/Q== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1730161354; x=1730766154; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=i9yLdCYlpqPTX58B/EOpzxj/uwBLH6nW8WmtXaMecqk=; b=r2qs1y3/vbibfspFkQ7zRQFLQSc0sTVRmpXpxPZA1ADNsuagyQ1mFCEQE1FQSAjW5o /KB4WBrsD4VRNXLNhodzKOPTF0wDZ+yFxC5hHlrxiiOcTznIfui4PqFIH7ZcHSOrKnOt nZ5WxvxpMChQ72x1lOFNlVynX8kGSbB4Pfj7SSYDTwheOzFeRMvHrEegyymBRh7S818q I0Lx5lsAiW8heGg5ovzPxBZ37S0iZ3AtyUIxUFDKL2oLyP+/DPKoEGQidAlBTgWypBEw tcJr80X6JS2TfNcOLp+vCX+uPa/rHaBQTSkCJdV2mpeDwhrYKXtYRc3NHdb9clZkfFBk 172Q== X-Forwarded-Encrypted: i=1; AJvYcCWIGGWXh49cAD4x5nY1uKDGBooWt2l0VxWWYAAUjUvVUKZvzDYoI9gGPwX+uRjqjTgWbLmNi/copb/XnFIf7/XaPiU9@vger.kernel.org, AJvYcCWY/hZ/IdWzYJhDd8YZaoO92Ds7HOE924VGL02B9fotF/KXkljHd3V+XfTrG54sIqUBdOcaDDtwp7EAxQyd@vger.kernel.org, AJvYcCWxq1cMKmmO2JwAmCZIuOoJL1Lh8D3KeqzmBDr7RVJ/0CwdrI38iG8pTmekIFniMnkQdsY=@vger.kernel.org, AJvYcCXkEEkdOfzqtWMUm0R+7PWPgsKpGqCwv3+cIPiSqH5h5wrZ8RwusFlV39rSQO9Nk7tqTJpsFid5gOi2JzQ9aowr@vger.kernel.org X-Gm-Message-State: AOJu0YznwjJfiKdX0rmZRcBPjOJpNIeF94LGVbQLd/e7/B7iHAAMU8S7 RW9itQ/zEWjZF3e35Tx81PqQRiHA8BqABhakBQ5jf0uvbTTODGRm X-Google-Smtp-Source: AGHT+IGzmc7vrVmYh/WKbUFbUoX2HPcYORnMsySleT7RDYFhCjZkMJNnf2EpiDFCC7NKHLJWgV6tuA== X-Received: by 2002:a17:90a:1347:b0:2e2:e91b:f0d3 with SMTP id 98e67ed59e1d1-2e8f11ac8d0mr10794538a91.29.1730161353523; Mon, 28 Oct 2024 17:22:33 -0700 (PDT) Received: from pengdl-ub.localdomain ([106.37.77.202]) by smtp.gmail.com with ESMTPSA id 98e67ed59e1d1-2e77e48e4a2sm10175507a91.2.2024.10.28.17.22.29 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 28 Oct 2024 17:22:32 -0700 (PDT) From: Donglin Peng To: andrii@kernel.org, eddyz87@gmail.com Cc: ast@kernel.org, rostedt@goodmis.org, mhiramat@kernel.org, bpf@vger.kernel.org, linux-trace-kernel@vger.kernel.org, linux-kselftest@vger.kernel.org, linux-kernel@vger.kernel.org, Donglin Peng Subject: [PATCH v4 3/3] libbpf: Using binary search to improve the performance of btf__find_by_name_kind Date: Tue, 29 Oct 2024 08:22:08 +0800 Message-Id: <20241029002208.1947947-4-dolinux.peng@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20241029002208.1947947-1-dolinux.peng@gmail.com> References: <20241029002208.1947947-1-dolinux.peng@gmail.com> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset="utf-8" Currently, we are only using the linear search method to find the type id by the name, which has a time complexity of O(n). This change involves sorting the names of btf types in ascending order and using binary search, which has a time complexity of O(log(n)). Another change is the search direction, where we search the BTF first and then its base. Signed-off-by: Donglin Peng --- tools/lib/bpf/btf.c | 159 ++++++++++++++++++++++++++++++++++++++------ 1 file changed, 140 insertions(+), 19 deletions(-) diff --git a/tools/lib/bpf/btf.c b/tools/lib/bpf/btf.c index 5290e9d59997..cbf88a6b92e5 100644 --- a/tools/lib/bpf/btf.c +++ b/tools/lib/bpf/btf.c @@ -94,6 +94,10 @@ struct btf { * - for split BTF counts number of types added on top of base BTF. */ __u32 nr_types; + /* number of types in this BTF instance which are sorted by name: + * - doesn't include special [0] void type; + */ + __u32 nr_types_sorted; /* if not NULL, points to the base BTF on top of which the current * split BTF is based */ @@ -896,46 +900,111 @@ int btf__resolve_type(const struct btf *btf, __u32 t= ype_id) return type_id; } =20 -__s32 btf__find_by_name(const struct btf *btf, const char *type_name) +static __s32 btf__find_by_name_bsearch(const struct btf *btf, const char *= name, + int *start, int *end) { - __u32 i, nr_types =3D btf__type_cnt(btf); + const struct btf_type *t; + const char *name_buf; + int low, low_start, mid, high, high_end; + int ret; + + low_start =3D low =3D btf->start_id; + high_end =3D high =3D btf->start_id + btf->nr_types_sorted - 1; + + while (low <=3D high) { + mid =3D low + (high - low) / 2; + t =3D btf__type_by_id(btf, mid); + name_buf =3D btf__name_by_offset(btf, t->name_off); + ret =3D strcmp(name, name_buf); + if (ret > 0) + low =3D mid + 1; + else if (ret < 0) + high =3D mid - 1; + else + break; + } =20 - if (!strcmp(type_name, "void")) - return 0; + if (low > high) + return -ESRCH; =20 - for (i =3D 1; i < nr_types; i++) { - const struct btf_type *t =3D btf__type_by_id(btf, i); - const char *name =3D btf__name_by_offset(btf, t->name_off); + if (start) { + low =3D mid; + while (low > low_start) { + t =3D btf__type_by_id(btf, low-1); + name_buf =3D btf__name_by_offset(btf, t->name_off); + if (strcmp(name, name_buf)) + break; + low--; + } + *start =3D low; + } =20 - if (name && !strcmp(type_name, name)) - return i; + if (end) { + high =3D mid; + while (high < high_end) { + t =3D btf__type_by_id(btf, high+1); + name_buf =3D btf__name_by_offset(btf, t->name_off); + if (strcmp(name, name_buf)) + break; + high++; + } + *end =3D high; } =20 - return libbpf_err(-ENOENT); + return mid; } =20 static __s32 btf_find_by_name_kind(const struct btf *btf, int start_id, const char *type_name, __u32 kind) { - __u32 i, nr_types =3D btf__type_cnt(btf); + const struct btf_type *t; + const char *tname; + int start, end, id; + __u32 nr_types; =20 if (kind =3D=3D BTF_KIND_UNKN || !strcmp(type_name, "void")) return 0; =20 - for (i =3D start_id; i < nr_types; i++) { - const struct btf_type *t =3D btf__type_by_id(btf, i); - const char *name; - - if (btf_kind(t) !=3D kind) + while (btf) { + if (btf->start_id < start_id) { + btf =3D btf->base_btf; continue; - name =3D btf__name_by_offset(btf, t->name_off); - if (name && !strcmp(type_name, name)) - return i; + } + + if (btf->nr_types_sorted) { + id =3D btf__find_by_name_bsearch(btf, type_name, &start, &end); + if (id > 0) { + while (start <=3D end) { + t =3D btf__type_by_id(btf, start); + if (kind =3D=3D BTF_KIND_MAX || + btf_kind(t) =3D=3D kind) + return start; + start++; + } + } + } else { + nr_types =3D btf__type_cnt(btf); + for (id =3D btf->start_id; id < nr_types; id++) { + t =3D btf__type_by_id(btf, id); + if (kind !=3D BTF_KIND_MAX && btf_kind(t) !=3D kind) + continue; + + tname =3D btf__name_by_offset(btf, t->name_off); + if (tname && !strcmp(tname, type_name)) + return id; + } + } + btf =3D btf__base_btf(btf); } =20 return libbpf_err(-ENOENT); } =20 +__s32 btf__find_by_name(const struct btf *btf, const char *type_name) +{ + return btf_find_by_name_kind(btf, 1, type_name, BTF_KIND_MAX); +} + __s32 btf__find_by_name_kind_own(const struct btf *btf, const char *type_n= ame, __u32 kind) { @@ -989,6 +1058,7 @@ static struct btf *btf_new_empty(struct btf *base_btf) return ERR_PTR(-ENOMEM); =20 btf->nr_types =3D 0; + btf->nr_types_sorted =3D 0; btf->start_id =3D 1; btf->start_str_off =3D 0; btf->fd =3D -1; @@ -1032,6 +1102,53 @@ struct btf *btf__new_empty_split(struct btf *base_bt= f) return libbpf_ptr(btf_new_empty(base_btf)); } =20 +static int btf_check_sort(struct btf *btf, __u32 start_id) +{ + __u32 i, n, nr_names =3D 0; + + n =3D btf__type_cnt(btf); + for (i =3D start_id; i < n; i++) { + const struct btf_type *t; + const char *name; + + t =3D btf__type_by_id(btf, i); + if (!t) + return libbpf_err(-EINVAL); + + name =3D btf__str_by_offset(btf, t->name_off); + if (!str_is_empty(name)) + nr_names++; + } + + for (i =3D 0; i < nr_names - 1; i++) { + const struct btf_type *t1, *t2; + const char *s1, *s2; + + t1 =3D btf__type_by_id(btf, start_id + i); + if (!t1) + return libbpf_err(-EINVAL); + + s1 =3D btf__str_by_offset(btf, t1->name_off); + if (str_is_empty(s1)) + goto out; + + t2 =3D btf__type_by_id(btf, start_id + i + 1); + if (!t2) + return libbpf_err(-EINVAL); + + s2 =3D btf__str_by_offset(btf, t2->name_off); + if (str_is_empty(s2)) + goto out; + + if (strcmp(s1, s2) > 0) + goto out; + } + + btf->nr_types_sorted =3D nr_names; +out: + return 0; +} + static struct btf *btf_new(const void *data, __u32 size, struct btf *base_= btf) { struct btf *btf; @@ -1042,6 +1159,7 @@ static struct btf *btf_new(const void *data, __u32 si= ze, struct btf *base_btf) return ERR_PTR(-ENOMEM); =20 btf->nr_types =3D 0; + btf->nr_types_sorted =3D 0; btf->start_id =3D 1; btf->start_str_off =3D 0; btf->fd =3D -1; @@ -1071,6 +1189,7 @@ static struct btf *btf_new(const void *data, __u32 si= ze, struct btf *base_btf) err =3D btf_parse_str_sec(btf); err =3D err ?: btf_parse_type_sec(btf); err =3D err ?: btf_sanity_check(btf); + err =3D err ?: btf_check_sort(btf, btf->start_id); if (err) goto done; =20 @@ -1690,6 +1809,8 @@ static int btf_ensure_modifiable(struct btf *btf) btf->types_data_cap =3D btf->hdr->type_len; btf->strs_data =3D NULL; btf->strs_set =3D set; + /* clear when splitting */ + btf->nr_types_sorted =3D 0; /* if BTF was created from scratch, all strings are guaranteed to be * unique and deduplicated */ --=20 2.34.1