From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from mail-pf1-f175.google.com (mail-pf1-f175.google.com [209.85.210.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 9B8BA2F8BC3 for ; Thu, 18 Dec 2025 21:38:12 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.210.175 ARC-Seal:i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1766093896; cv=none; b=ZxiChMZjYeJCBEg/m5+LxuZ1gZvnymuXOi/2dgnG5t63wGNLqLYPoxxtjUjEutn8NVuDz7DzjwsbMTbixN6Sx3Gw8yu8UfFVhDPcCgCT7j5Aem76mT7/EVUqf6rhgOL7RjFe9+diKcgIiXVvP9PjHP9Yu08CG9Y7NAelYHauptQ= ARC-Message-Signature:i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1766093896; c=relaxed/simple; bh=x3gs/QkwhXWKJee9flxhMM41mwK7jJYdeEPKYBqsGbk=; h=Message-ID:Subject:From:To:Cc:Date:In-Reply-To:References: Content-Type:MIME-Version; b=WIj5yuccp/pZl+B9gTm84p2c+CXN1l3Fpf3tbbco1fekCnymnplM5JYw+3g2L9K0yIfE56Mzwm6+Xuz/lXW3WW3fYThzAX8ELqmAfpuyisCcgsAIoS+sJBZ2zBQeB7mx+NqjshYXoNpG7JzDTYGjNsGutU9iJzijKEUCY+o29J0= 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=i0JiDnTC; arc=none smtp.client-ip=209.85.210.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="i0JiDnTC" Received: by mail-pf1-f175.google.com with SMTP id d2e1a72fcca58-7b7828bf7bcso1291071b3a.2 for ; Thu, 18 Dec 2025 13:38:12 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1766093891; x=1766698691; darn=vger.kernel.org; h=mime-version:user-agent:content-transfer-encoding:references :in-reply-to:date:cc:to:from:subject:message-id:from:to:cc:subject :date:message-id:reply-to; bh=46e/g8olhTGyx9sgeuPo5RKSKaANbZnSdw71U+AdQtk=; b=i0JiDnTClOSHSHhOWVmFa7ZENwjSTEsrC2HPt/wgOurEzGRmgaXNpVf7NOaKRzZ7i9 M0+4PQas4Fntx8kIWqQM5dcd0rBAhENAW1M1zwzmitOUtGEmaRzMfnOPcPCmp+WtRDMz QdcgyRlA0zlYCmDWg+wlWG/adddTCVbur32v9uOQfITmwn52VESzK5/YI9mhqEBOCeon 0DHN2GyoHn4ltXnOdcelWMDBSBVSWFtEhKzegZlbeziAIH9TZWFwrBjhZvgLSgOv5PJR XsJTZwmdGroNu+ONLOCzaFoBeUDezW/LgPuOFz1Di3WH++uDOmEt1PRhFCtx40gzqIPQ tpAQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1766093891; x=1766698691; h=mime-version:user-agent:content-transfer-encoding:references :in-reply-to:date:cc:to:from:subject:message-id:x-gm-gg :x-gm-message-state:from:to:cc:subject:date:message-id:reply-to; bh=46e/g8olhTGyx9sgeuPo5RKSKaANbZnSdw71U+AdQtk=; b=EJyv6oSabxnKJQbSMbRNwwHyTqq+uTheAAA+HiYrZoWRWWu4BQ5UJPCKCMetmdT4K2 YmzcTquwxd8jNlGSwmoeT8hKAMlfnZkYLtvnBFoprQMlNIFDUDMivZuowk4Df5gypDvz oNXBj/u4k5JPmdbHr6FKvxuG4gOUkk8z/8a5T6MeDxPX6nw9tRL2PHJnuWmFEnhv5h0w wCn1WS2Czaw5vM8yZe2rsM2lJTLVArZ6C/mWHWpCweISRQk2Dm+wYRxOGJb9mL6nD1Et LwqNX4G2wdt/S7oEmCQZGU7ehhoJbRrpqVKyzkHKElJLV3O4J2wQn/YIbEREkdcNxupP FX5w== X-Forwarded-Encrypted: i=1; AJvYcCXmiabAbDMlE7Q66RWMjsmTfFVfD0JV82WCM7i0eiw7F2TMgSxCLwXp+wxf+okPkwEtBSD4yTqJhFpPxRg=@vger.kernel.org X-Gm-Message-State: AOJu0YwVeFMbL/v4bosGtgYBAqYlLtCLkYmlzPbSierb5QFmcYKJtk/a EGfpqGlmXVW2ssEGJw9doSx0IdPvca8DesHdmq2raLuPGwKxsAX7pkHBj4qZ1uCbGEA= X-Gm-Gg: AY/fxX7XPsx2XLQ4mUWGqBh7fBHJhStnShYwt0LshcinlMRaiYd6YR7tFnJz+4LoX9+ 6+Zq0qixGb9/a+ASrEHe50j4YuEYe+PrdElIvdUMaTqg6cBqUtgkEYIZBqT9Gwvrm5Re8G+AQga 5z86s5cof7bSHeIecRSyMP46E62ynF3Kaks4bXUAcBhcGYT1fmgBlfffJRP9xV87SBkLhyrZiPB HH7ZZj/ez9H8mSI+9bzOr50PvoWvd/X/3CpUzBguHRUH9ijpOtdXiT164JPC4SmkfIObf9QG50+ bKJWkWS3xw27CSffZOMxnKNlTQl8lZSQFTDyNNgWHlbaIaBEQN9ZTU9TpAB13o/MW0e7nDyk1ot URpBtjWFr5aMMw/CmemO/VfSWq7Xl/P1ffHg7YpNjUdz3eiX8H//6VnapMkEM09Jj4bFHr8yJ7X 5h30aMR4lo9c16VmBuu/zzGYoI4vbc/r2D0WeJ X-Google-Smtp-Source: AGHT+IE9S8nx1Xj9+e7DuNbibOjjVl4iWT965rzzma8m6a0Lb7aAXpTMmbJDs9+ZKMAmR9hsb9qWsw== X-Received: by 2002:a05:7022:ef0b:b0:11b:8161:5cfc with SMTP id a92af1059eb24-12172306ccfmr931972c88.36.1766093890851; Thu, 18 Dec 2025 13:38:10 -0800 (PST) Received: from ?IPv6:2a03:83e0:115c:1:4779:aa2b:e8ff:52c4? ([2620:10d:c090:500::5:3eff]) by smtp.gmail.com with ESMTPSA id a92af1059eb24-121724cfa2csm1294024c88.3.2025.12.18.13.38.09 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 18 Dec 2025 13:38:10 -0800 (PST) Message-ID: <290a67f65e9f7083895b5177d524e3ce27e9f93c.camel@gmail.com> Subject: Re: [PATCH bpf-next v10 06/13] btf: Optimize type lookup with binary search From: Eduard Zingerman To: Donglin Peng , ast@kernel.org, andrii.nakryiko@gmail.com Cc: zhangxiaoqin@xiaomi.com, ihor.solodrai@linux.dev, linux-kernel@vger.kernel.org, bpf@vger.kernel.org, pengdonglin , Alan Maguire Date: Thu, 18 Dec 2025 13:38:09 -0800 In-Reply-To: <20251218113051.455293-7-dolinux.peng@gmail.com> References: <20251218113051.455293-1-dolinux.peng@gmail.com> <20251218113051.455293-7-dolinux.peng@gmail.com> Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable User-Agent: Evolution 3.56.2 (3.56.2-2.fc42) Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 On Thu, 2025-12-18 at 19:30 +0800, Donglin Peng wrote: > From: pengdonglin >=20 > Improve btf_find_by_name_kind() performance by adding binary search > support for sorted types. Falls back to linear search for compatibility. >=20 > Cc: Eduard Zingerman > Cc: Alexei Starovoitov > Cc: Andrii Nakryiko > Cc: Alan Maguire > Cc: Ihor Solodrai > Cc: Xiaoqin Zhang > Signed-off-by: pengdonglin > --- (One nit below). Acked-by: Eduard Zingerman > kernel/bpf/btf.c | 85 +++++++++++++++++++++++++++++++++++++++++++----- > 1 file changed, 76 insertions(+), 9 deletions(-) >=20 > 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_ty= pe *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 *n= ame, > + 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 ki= nd) > { > + 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]) { ^^^^^^^^^^^^^^^^^^^^^^^^ Nit: Maybe pull the is_sorted helper into this patch-set? > + /* 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 *= attr, 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_verifi= er_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 *mod= ule_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);