From nobody Fri Dec 19 13:24:03 2025 Received: from mail-pj1-f46.google.com (mail-pj1-f46.google.com [209.85.216.46]) (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 CE79C31AAAD for ; Thu, 18 Dec 2025 11:31:32 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.216.46 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1766057495; cv=none; b=mCuVkeyV+9KUJmzqF+xlxNhyiw7yUpOU6eBNeuCnnMVSIsbGvHXbDz95GaghhlTr7PSGSNxMNVbNG3hwyHEi5kudHTIqx6gdZI4tM3pKrDPYe09Qvu0eNHTJMG56S5VkqUYFGjAh0S8NDguf1AJLzBkBQXVF7gqLBgedCKyrt54= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1766057495; c=relaxed/simple; bh=+zqsDHnuHDnyqQtOgMwqka0OTnj+dnOtXNTtEUn01ew=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=bn2NgiNmlZScAclOci04k2SteFY+ATS0RgcxhvN4dcIbtOC5KoBMspf1Qb/VYN4aTUz/u0tKSeuQzgMGTSq/rS3XeBd6qbHVn9K8ib+K0VtyhxKlt2yoJgaQtHxErG5qCwet6/AfAS3OLrWiEO96j7Vz9cmx/SqyhonwOo1iJUo= 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=HgPeQGOV; arc=none smtp.client-ip=209.85.216.46 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="HgPeQGOV" Received: by mail-pj1-f46.google.com with SMTP id 98e67ed59e1d1-34abc7da414so492075a91.0 for ; Thu, 18 Dec 2025 03:31:32 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1766057492; x=1766662292; 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=uewsaipU9OXUmad7hbnTZa38j0aK0kfvkQvJ5cwCJxk=; b=HgPeQGOVK9jteed7DN8wI2baXQb0GnzZ43CsSJLpjQPQYLHSOyspZOgFg4DfbmPoHF II1VixcOS+9GBK0d1F3lCaZ6vcMZ1EDijLYcLvE9g0ssor4xApOzzpKWkLWbATSe5BsW 1aLh6paWQat6cZaD2ZbYa27Bf1EhL++J/YzQMNbGXJSMjMILfwDYqK3INdZktl/5KAJw iZbxxc3Muxv4mWp/3iEao5tOfGO7VPPJPflO+bBpbZvNnqHYaQGncWhFk+60Nhnn3Ncb YI1Xl712GcqmzA04e1DlvPc4v+dXz8LHgog1veXCuwIjl4oxpU9KZ6h2aVYAwbrq5KZf E3mw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1766057492; x=1766662292; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-gg:x-gm-message-state:from :to:cc:subject:date:message-id:reply-to; bh=uewsaipU9OXUmad7hbnTZa38j0aK0kfvkQvJ5cwCJxk=; b=WQXaSjwqCcDtPys1AGZZvB/33mdyCa8HDzU/w2aVwNU28j0KKax6B5kMowzvoJ0Qu6 cc8joKeHtEYgvGYqaEA4xQOJ8Y/wQRYGksfhnbQPpQVI2dRVXmsqdSxfqfG6L+l2CGbr n5jMIvRScaTcFcazsN9XFeHfwJmkWY+uqGGKCtwH9dLvMg2kzCgCOqO2oDdhSFqC4+Mz FWdxnCCMLQaytAn/OyuxUXqMGESymLCxrDnzt8IhSvIdDZUk3ag+3eMQuUFNeXeTDwka b3pwQBHFSpmBs/x5U9wChyN0+ihQALS14p/GZhkdX+XMmnvxiVBbIu5TvdMOoXcEfnsa mI1w== X-Forwarded-Encrypted: i=1; AJvYcCU6WinEsxy+6ZaitzWWbfhWLG5tBDHAT2847qqnSwkaE2VlhIsMnWLmD4bVXJk7pfT0z+eAjxPOj0aKBxw=@vger.kernel.org X-Gm-Message-State: AOJu0YxAp3761HEE1yEvaooYfJBMDG8g4mqJgsiU2l36FVPtamXDcizI SuSwt8HCzHARWT2P/MDq2t6Z6g20IO8s68K3nc8+3LJTBZsWFpPaUNt/ X-Gm-Gg: AY/fxX6V3AKeT6oYVN0OmnsWnDIPXUxg/LmqopaNPDAuvbElgXYK4f93X/9Errhrcy9 AW+J/FK6ugDkSlzS2qqtjAq9J9AQBeEFDlXfYTM1NVeBq7ci/OEEf5VgJFpc/AHJcwQ3uNEAivw h+9bB9XbBWOjs2LLjFAORYtSWRAXN07TjJk/+K55YmmoK2kO8Ll+0HbnSm/n7+1Ajrr0h7N80Pk afqG2V7k09vYObrxiLUMLV37ABjzOxBOaTGurmFUerwYGGbu7mR+Sfikeg+YHEO79SNBOPS7j/5 Rurzz9WAN1ygJXq+LGdIDD57Js8Tbtl3HBqkeFL9k99ATbpWsgtdBUc3gDp4WdjYhDfB2+m2If8 dmCzn+Dbuz89yLHKCMWT/ejlhbTC+dxG6he3sw7wc6AEPHLThncecVUp76+TjOZ5RwMEVa7uhws x72gbRmVd8mSqm80foK7Cx8gJUeMQ= X-Google-Smtp-Source: AGHT+IELClayAaqS0OadqjKtH4cOtXpKc/dZ0z9qgGpxsVMemuOw5iYbdyYOvOxgDADYhzL2w3p6cA== X-Received: by 2002:a17:90b:5111:b0:34a:adf1:677d with SMTP id 98e67ed59e1d1-34abd6d88abmr17202318a91.9.1766057492127; Thu, 18 Dec 2025 03:31:32 -0800 (PST) Received: from pengdl-pc.mioffice.cn ([43.224.245.249]) by smtp.gmail.com with ESMTPSA id 98e67ed59e1d1-34e70d4f887sm2328237a91.3.2025.12.18.03.31.28 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 18 Dec 2025 03:31:31 -0800 (PST) From: Donglin Peng To: ast@kernel.org, andrii.nakryiko@gmail.com, eddyz87@gmail.com Cc: zhangxiaoqin@xiaomi.com, ihor.solodrai@linux.dev, linux-kernel@vger.kernel.org, bpf@vger.kernel.org, pengdonglin , Alan Maguire Subject: [PATCH bpf-next v10 06/13] btf: Optimize type lookup with binary search Date: Thu, 18 Dec 2025 19:30:44 +0800 Message-Id: <20251218113051.455293-7-dolinux.peng@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20251218113051.455293-1-dolinux.peng@gmail.com> References: <20251218113051.455293-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" From: pengdonglin Improve btf_find_by_name_kind() performance by adding binary search support for sorted types. Falls back to linear search for compatibility. Cc: Eduard Zingerman Cc: Alexei Starovoitov Cc: Andrii Nakryiko Cc: Alan Maguire Cc: Ihor Solodrai Cc: Xiaoqin Zhang Signed-off-by: pengdonglin Acked-by: Eduard Zingerman --- kernel/bpf/btf.c | 85 +++++++++++++++++++++++++++++++++++++++++++----- 1 file changed, 76 insertions(+), 9 deletions(-) diff --git a/kernel/bpf/btf.c b/kernel/bpf/btf.c index 0de8fc8a0e0b..0394f0c8ef74 100644 --- a/kernel/bpf/btf.c +++ b/kernel/bpf/btf.c @@ -259,6 +259,7 @@ struct btf { void *nohdr_data; struct btf_header hdr; u32 nr_types; /* includes VOID for base BTF */ + u32 sorted_start_id; u32 types_size; u32 data_size; refcount_t refcnt; @@ -494,6 +495,11 @@ static bool btf_type_is_modifier(const struct btf_type= *t) return false; } =20 +static int btf_start_id(const struct btf *btf) +{ + return btf->start_id + (btf->base_btf ? 0 : 1); +} + bool btf_type_is_void(const struct btf_type *t) { return t =3D=3D &btf_void; @@ -544,21 +550,79 @@ u32 btf_nr_types(const struct btf *btf) return total; } =20 +static s32 btf_find_by_name_bsearch(const struct btf *btf, const char *nam= e, + s32 start_id, s32 end_id) +{ + const struct btf_type *t; + const char *tname; + s32 l, r, m, lmost =3D -ENOENT; + int ret; + + l =3D start_id; + r =3D end_id; + while (l <=3D r) { + m =3D l + (r - l) / 2; + t =3D btf_type_by_id(btf, m); + tname =3D btf_name_by_offset(btf, t->name_off); + ret =3D strcmp(tname, name); + if (ret < 0) { + l =3D m + 1; + } else { + if (ret =3D=3D 0) + lmost =3D m; + r =3D m - 1; + } + } + + return lmost; +} + s32 btf_find_by_name_kind(const struct btf *btf, const char *name, u8 kind) { + const struct btf *base_btf =3D btf_base_btf(btf); const struct btf_type *t; const char *tname; - u32 i, total; + s32 idx; =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 (base_btf) { + idx =3D btf_find_by_name_kind(base_btf, name, kind); + if (idx > 0) + return idx; + } =20 - tname =3D btf_name_by_offset(btf, t->name_off); - if (!strcmp(tname, name)) - return i; + if (btf->sorted_start_id > 0 && name[0]) { + /* skip anonymous types */ + s32 start_id =3D btf->sorted_start_id; + s32 end_id =3D btf_nr_types(btf) - 1; + + idx =3D btf_find_by_name_bsearch(btf, name, start_id, end_id); + if (idx < 0) + return -ENOENT; + + t =3D btf_type_by_id(btf, idx); + if (BTF_INFO_KIND(t->info) =3D=3D kind) + return idx; + + for (idx++; idx <=3D end_id; idx++) { + t =3D btf_type_by_id(btf, idx); + tname =3D btf_name_by_offset(btf, t->name_off); + if (strcmp(tname, name) !=3D 0) + return -ENOENT; + if (BTF_INFO_KIND(t->info) =3D=3D kind) + return idx; + } + } else { + u32 i, total; + + total =3D btf_nr_types(btf); + for (i =3D btf_start_id(btf); i < total; i++) { + t =3D btf_type_by_id(btf, i); + if (BTF_INFO_KIND(t->info) !=3D kind) + continue; + tname =3D btf_name_by_offset(btf, t->name_off); + if (strcmp(tname, name) =3D=3D 0) + return i; + } } =20 return -ENOENT; @@ -5791,6 +5855,7 @@ static struct btf *btf_parse(const union bpf_attr *at= tr, bpfptr_t uattr, u32 uat goto errout; } env->btf =3D btf; + btf->sorted_start_id =3D 0; =20 data =3D kvmalloc(attr->btf_size, GFP_KERNEL | __GFP_NOWARN); if (!data) { @@ -6210,6 +6275,7 @@ static struct btf *btf_parse_base(struct btf_verifier= _env *env, const char *name btf->data =3D data; btf->data_size =3D data_size; btf->kernel_btf =3D true; + btf->sorted_start_id =3D 0; snprintf(btf->name, sizeof(btf->name), "%s", name); =20 err =3D btf_parse_hdr(env); @@ -6327,6 +6393,7 @@ static struct btf *btf_parse_module(const char *modul= e_name, const void *data, btf->start_id =3D base_btf->nr_types; btf->start_str_off =3D base_btf->hdr.str_len; btf->kernel_btf =3D true; + btf->sorted_start_id =3D 0; snprintf(btf->name, sizeof(btf->name), "%s", module_name); =20 btf->data =3D kvmemdup(data, data_size, GFP_KERNEL | __GFP_NOWARN); --=20 2.34.1