From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from mail-pf1-f180.google.com (mail-pf1-f180.google.com [209.85.210.180]) (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 6D7D221FF35 for ; Sat, 22 Nov 2025 08:50:12 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.210.180 ARC-Seal:i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1763801414; cv=none; b=QabYaHSGzOPn0894vQDl5tDvZYgPl3ssE57luv01z+YayRGdAvOTQ8n2l5jS5Hq08JF2wJVUAUeVSix370vfHywi8OoWFljrb45OH78HbcPmu2rr2N0lrs3Qi6ug8k5AExXo7Yf7gkgAFHMXWH0+/kT03472K4SxsKKj2YLnkno= ARC-Message-Signature:i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1763801414; c=relaxed/simple; bh=JYpUk2d5LVEVvLeynM6oao2GwY6qr8tahYHhHE+OC0s=; h=Message-ID:Subject:From:To:Cc:Date:In-Reply-To:References: Content-Type:MIME-Version; b=R0dFpWVm3BdRPTa1qoXR5GtEd7tnbxDR2m8IrqlVciu/J/LVbPFKnrr+gSYfJQrRmjNQ5/+svmXNbgxee+YjViHnV4H9zDrzUCnLltLqFHcwjH4dxoL/LuoreJe5bdd9tM7V8dVMfMz4J87zPkgZ1l9apjRbb4XWOhUaNbCgTnE= 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=dZ23pzJv; arc=none smtp.client-ip=209.85.210.180 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="dZ23pzJv" Received: by mail-pf1-f180.google.com with SMTP id d2e1a72fcca58-7b8eff36e3bso4243947b3a.2 for ; Sat, 22 Nov 2025 00:50:12 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1763801412; x=1764406212; 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=JYpUk2d5LVEVvLeynM6oao2GwY6qr8tahYHhHE+OC0s=; b=dZ23pzJvVqq8IJJzg9AWrcWVD8ve7KvE1A6CkBkpyhTyuBrBnLD5lXu0CXUPQv/UYk piynnFusOC//f+k9p9jz3TQs1P+Fl4wqedBTEnhdsqUj5i6nd5MSIXzda970dWTZjeol /y3D3wh+Vt5/4hEKvaAhJtSsBrl8yhSGB6KLVoFTWpK1H6E6NUU9oQBsKQIM0aGsQrPI T7/2xAPmsZlQilS8SfxvncGG8Ap3CeQaw6z/wSbyUcFXdNZCQLUZjmJueFCGN9x03MVv PCHb24PpQmsha6PmAB0SblM4M/Z67aJb14XU5ZbEKMV0tgkrT/IM04GC7+ul1kj5Fju6 ra8w== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1763801412; x=1764406212; 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=JYpUk2d5LVEVvLeynM6oao2GwY6qr8tahYHhHE+OC0s=; b=p6rlYhmi3yhueFhW7HKBAe/1k+EqLGCTsym9p7RjAl74aQDW9onYuf1B+fLI6JvT0+ sp4+tCWW6FzVa9jsY5QUtCKq+tdPAN+3IX5j/kRSWxC3XfllbPRVkuRx5wuDNViymu83 Uzwyy950BFcRYEVaTG0NIRCdGiRRx94HrAGbNkkmXtfEoNMH11FzVyHpFVk/8ujjayW3 0UwJvURba+Hvfp1vuM/s6dMiiBP8yB7qg60XAU5pOfRTAkBjMy0eUzLOUCkbw7MgkRfn Z7LRxk3JhK4oDEuD3UFhV/VYPn2XniBYzcqQcehp1f9/PiL6OUD8IwsI9sqnGnk7t6Hd UPvg== X-Forwarded-Encrypted: i=1; AJvYcCVF/yVT88eWwwtVw0UuGhg1YMkYDQL2ZsdCNyuq89gh90ZSnhfekLOsUaEc2mm4AvIi5n73iG5fs1CkUAQ=@vger.kernel.org X-Gm-Message-State: AOJu0YxGfupp3yn8rr3ZoP6KJAh5PCRqo3C351G/87CCKN67NRa9TDC+ QlCYcxbIABYNZmBl+WwJILU/mGy/R1B76JwRsBgP1zkDiUK9W8L4vAo2w/Vj8w== X-Gm-Gg: ASbGncv7IIc9YNBzPUAyOQFrD2mNlmiuU54261to7enX3bDgJ1+cm6n+s0mEy5MRDkD qQ/Pex+7QzyVYjL6gL/cR3JfI5eaMjt40k3U3TQA2SGhTm8uf3lCdztm8g7cCkxvOMOPYSlAGgS DcenGaoKsmCB2rC4Y3/slcz2rRf9KolJ3yPX0VIMnl+s0cVAV9Xl1gnJ9OBRW73fdcN8IbIC/fk A0XpJLnUkmPDoWvDgmS+azTKE+VkLXg1GwKRgVl2WZBlQEfrtjRfO18+iAsUEhTRuhg6qL3f9I3 V3MRR5B3ZZlycTyFD0gNjQDoPwjnqgxv7kUElO8T+tDymrmYlNJrSfUG+YMJWY8gQJhxCoT3Frv 7S51LMGvaj1TB/ZV4GWSlzbGCGPM+FxtoTRX5eu1ULdhDArlTvbZhlRj3O4Oj0jNz8RgESByQgO idl3RcWAk= X-Google-Smtp-Source: AGHT+IHOtvBb/gc+kJaGK3biLyQeaMFA39gCQxyG+kDUtS7sNw6EMd06A4LyWaC8dVZwQA4xyMu7SQ== X-Received: by 2002:a05:6a20:5491:b0:35f:30ff:89f1 with SMTP id adf61e73a8af0-3614ee85318mr7246761637.56.1763801411603; Sat, 22 Nov 2025 00:50:11 -0800 (PST) Received: from [192.168.0.56] ([38.34.87.7]) by smtp.gmail.com with ESMTPSA id 41be03b00d2f7-bd760ac633dsm7722798a12.27.2025.11.22.00.50.10 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Sat, 22 Nov 2025 00:50:11 -0800 (PST) Message-ID: Subject: Re: [RFC PATCH v7 5/7] libbpf: Implement BTF type sorting validation for binary search optimization From: Eduard Zingerman To: Donglin Peng Cc: Andrii Nakryiko , ast@kernel.org, zhangxiaoqin@xiaomi.com, linux-kernel@vger.kernel.org, bpf@vger.kernel.org, Donglin Peng , Alan Maguire , Song Liu Date: Sat, 22 Nov 2025 00:50:08 -0800 In-Reply-To: References: <20251119031531.1817099-1-dolinux.peng@gmail.com> <20251119031531.1817099-6-dolinux.peng@gmail.com> Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable User-Agent: Evolution 3.58.1 (3.58.1-1.fc43) Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 On Sat, 2025-11-22 at 15:19 +0800, Donglin Peng wrote: [...] > > - find_bpffs_btf_enums() - this function does a linear scan over all > > =C2=A0 types in module BTFs. >=20 > I think putting names ahead is helpful here, because there is a check > (info->cmd_t && info->map_t && info->prog_t && info->attach_t) to > return early. but I think it can be converted to use btf_find_by_name_kin= d. Oh, sorry, I somehow missed the early exit here. But as you say, it is a combination of 4 by-name lookups, essentially. Thus can be converted to btf_find_by_name_kind() trivially. > > - find_btf_percpu_datasec() - this function looks for a DATASEC with > > =C2=A0 name ".data..percpu" and returns as soon as the match is found. > >=20 > > Of the 4 functions above only find_btf_percpu_datasec() will return > > early if BTF type with specified name is found. And it can be > > converted to use btf_find_by_name_kind(). >=20 > Thanks. I=E2=80=99ve looked into find_btf_percpu_datasec and we can=E2=80= =99t use > btf_find_by_name_kind here because the search scope differs. For > a module BTF, find_btf_percpu_datasec only searches within the > module=E2=80=99s own BTF, whereas btf_find_by_name_kind prioritizes > searching the base BTF first. Thus, placing named types ahead is > more effective here. Besides, I found that the '.data..percpu' named > type will be placed at [1] for vmlinux BTF because the prefix '.' is > smaller than any letter, so the linear search only requires one loop to > locate it. However, if we put named types at the end, it will need more > than 60,000 loops.. But this can be easily fixed if a variant of btf_find_by_name_kind() is provided that looks for a match only in a specific BTF. Or accepts a start id parameter.