From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from mail-lf1-f45.google.com (mail-lf1-f45.google.com [209.85.167.45]) (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 0DCE63672B8 for ; Tue, 12 May 2026 11:31:46 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.167.45 ARC-Seal:i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1778585509; cv=none; b=FK33QO0tG8leDnM0K9ePX+9f++L661kX4sIhEjOjAeOakpTmEnJrmtFsrMn5/Hh8m1PgvQ7r8ZHuIvElEawuhNPytX8KIpPbxkXknXyIYL/xZwxLgrwmCI/6kzfuZOwK1rbKXlXfyekhjuUJMuje/kV+OwRfYkd9/dXqNr+nVDc= ARC-Message-Signature:i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1778585509; c=relaxed/simple; bh=B+leOCEctgJ3aL1kR6N+EwfhxPiqybiB9ANH1dLPEU0=; h=From:To:Cc:Subject:In-Reply-To:References:Date:Message-ID: MIME-Version:Content-Type; b=oRw5ac2ohRs7QrhcN+HjgjbEBn5qbOICi/z0ON0J+GCk1RDekHC2YDp1ikZpsxuPGGnTTJCR9IkV4jekaw3T5aVe/g4t3bUWkv8OdXRHbdRPpNNG52Q8n7kWtSCAkQ1Jrl7s4JdBMDBaU0aH6U9zyG+5J98YzaIxWSYpHgTekiI= ARC-Authentication-Results:i=1; smtp.subspace.kernel.org; dmarc=fail (p=none dis=none) header.from=mina86.com; spf=pass smtp.mailfrom=gmail.com; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b=lG9EGKIL; arc=none smtp.client-ip=209.85.167.45 Authentication-Results: smtp.subspace.kernel.org; dmarc=fail (p=none dis=none) header.from=mina86.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="lG9EGKIL" Received: by mail-lf1-f45.google.com with SMTP id 2adb3069b0e04-5a8738c178dso3719445e87.1 for ; Tue, 12 May 2026 04:31:46 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20251104; t=1778585505; x=1779190305; darn=vger.kernel.org; h=content-transfer-encoding:mime-version:message-id:date:references :in-reply-to:subject:cc:to:from:sender:from:to:cc:subject:date :message-id:reply-to; bh=tL+U9c97joh2/XEWcphvjCD2QPSQwQ8RK6OhlOZiN+A=; b=lG9EGKILGGDrXVATBgQNgYrrt9z0Mk4NJwFmOUvSSTstuDNTHcYyvzz7vBOdpXR2Rg wEqkYel+9/ilDnBVqQkTvxr5h5do2/exNiuH4A5VJl0TIpvHAjqlPEwPKsH2HZPScSvp LlY4odcs+9UTj5KoRiNsVhmbBfI0jfs9vXYxlj+fLlRN1dhMceqsxDAzIRxtc9vg97// R3TFZQzQ4SeF/9JcnAQgBs6ssEeRvx2k1iUGUioOaQaW2a+b28DMjS4kZoIp2ITRxAmx mTg9gH3xequld7peHUEP8mqAi4XDOwOdSvnCZaw/8MgIZrG3jfHPRP356Gt6sJERYOyD Lu4A== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20251104; t=1778585505; x=1779190305; h=content-transfer-encoding:mime-version:message-id:date:references :in-reply-to:subject:cc:to:from:sender:x-gm-gg:x-gm-message-state :from:to:cc:subject:date:message-id:reply-to; bh=tL+U9c97joh2/XEWcphvjCD2QPSQwQ8RK6OhlOZiN+A=; b=KBcgFNBQEt3rstcgSk9N5xLMdW0LQhM8LzbkReItk2hSJWannsF91bKpUPjhIeDtW9 Nb9DaE4NXc3iq1lhp2K/xFrwqa87p6gBvRA5xN1aDsIDNIlOMAU5WRZbd33065zUY9WK KVZD8mdEju7B8B+Haz98ws5FOy13lQCFJzL3k3q6DB9uvX8PSB5bCxEhfFranibNTFR6 aUz8ccsCioSC0vVOFD3Ivznye9/aAz9V9ze4eTCqzJdHhqZP1xTNZYbrBJysd/aLI8aG sUHzKlRuHPmRq68E+ILgDPzeKvhcPbzvjBPdUR9bdEb3EL6ABI1JgGBiSiO13BJUDbu+ MLWA== X-Forwarded-Encrypted: i=1; AFNElJ/8lK4CCQ7PM8GEF8f2IK2F4iIA4UVAiez7fLXrOgO5I7RAIvRmA378zCl+lTcpZpEL1OnSPy5Ir5DYR7c=@vger.kernel.org X-Gm-Message-State: AOJu0Yzm/iXiyg2Mot8v+ZAjWtyUvrcGGEbdw8LJkM8TPA1Y7l8ILgl+ spIrJbaKdyvyAEVpZY3xg0cI9lxogVouI2XfvrXGs5BAy56TGihFD2WwCnxiKQ== X-Gm-Gg: Acq92OGXJHcAHbx6n/bjk6Q2mrTcaKfakckhnVtKNU+7jXbBuQcc8f9pnrXHtnUTRUA v/faiRQwF6I/P/HOqKGsFK4qYO+b5xFeFmDnx5O9pQT3Al2/zXjI9t7SqbG0fB7UEf1IcokpJ9i 4jyALnjrRxAh2wf9zn0iYd9ZP/mtQLJoTBL6RKoV7jLjZIE9mJK3i+ahIPD1CefpI4VSHml95OR WdS5plM/hh7fZta1K6YUxMdrU8NpMFkORE9+MaTHSOSbiwu5f/tb91hlbjs002yYGvry2NjJhj9 Cjj7GO1Q4SHqDs21pPoc9cYOVoim63JSAnMOwwaAwM2fvAe2co0hxQzyKoReNeJ56TlwutKjkxU K73W9bgxb/P0oCcZeq03F2DoSY7BkBPPoJl0uge1q9UAgpGd78+6h+XMwc5i+6wl2rVthkvpvWO EqFP+GlIDS+MH38H29CoOflb/zE7+xQoLk0tiiocqoqkrvcwxfyA== X-Received: by 2002:a05:6512:ad1:b0:5a8:84a5:bffa with SMTP id 2adb3069b0e04-5a8e30ca1e8mr719675e87.5.1778585504976; Tue, 12 May 2026 04:31:44 -0700 (PDT) Received: from erwin (109241130011.warszawa.vectranet.pl. [109.241.130.11]) by smtp.gmail.com with ESMTPSA id 2adb3069b0e04-5a8cf1b671esm1380285e87.76.2026.05.12.04.31.43 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 12 May 2026 04:31:43 -0700 (PDT) Sender: =?UTF-8?Q?Micha=C5=82_Nazarewicz?= From: =?utf-8?Q?Micha=C5=82?= Nazarewicz To: Yi Sun , yi.sun@unisoc.com, yury.norov@gmail.com, akpm@linux-foundation.org Cc: akinobu.mita@gmail.com, linux-kernel@vger.kernel.org Subject: Re: [PATCH 1/2] lib: bitmap: add find_last_bit_range() and _find_last_bit_range() In-Reply-To: <20260512040659.2992142-2-yi.sun@unisoc.com> References: <20260512040659.2992142-1-yi.sun@unisoc.com> <20260512040659.2992142-2-yi.sun@unisoc.com> Date: Tue, 12 May 2026 13:31:42 +0200 Message-ID: Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: quoted-printable On Tue, May 12 2026, Yi Sun wrote: > In some scenarios, it's not desirable to keep searching through the > beginning of the bitmap, but rather to search within a specific part. > The newly added function can accomplish this quickly. > > Signed-off-by: Yi Sun Acked-by: Micha=C5=82 Nazarewicz > --- > include/linux/find.h | 35 +++++++++++++++++++++++++++++++++++ > lib/find_bit.c | 30 ++++++++++++++++++++++++++++++ > 2 files changed, 65 insertions(+) > > diff --git a/include/linux/find.h b/include/linux/find.h > index 6c2be8ca615d..7126b0fffe0f 100644 > --- a/include/linux/find.h > +++ b/include/linux/find.h > @@ -33,6 +33,8 @@ unsigned long _find_first_and_and_bit(const unsigned lo= ng *addr1, const unsigned > const unsigned long *addr3, unsigned long size); > extern unsigned long _find_first_zero_bit(const unsigned long *addr, uns= igned long size); > extern unsigned long _find_last_bit(const unsigned long *addr, unsigned = long size); > +extern unsigned long _find_last_bit_range(const unsigned long *addr, uns= igned long size, > + unsigned long offset); >=20=20 > #ifdef __BIG_ENDIAN > unsigned long _find_first_zero_bit_le(const unsigned long *addr, unsigne= d long size); > @@ -413,6 +415,39 @@ unsigned long find_last_bit(const unsigned long *add= r, unsigned long size) > } > #endif >=20=20 > +#ifndef find_last_bit_range > +/** > + * find_last_bit_range - find the last set bit in a memory region > + * @addr: The address to base the search on > + * @size: The bitmap size in bits > + * @offset: The bit number to start searching at > + * > + * Compared to the find_last_bit(), > + * find_last_bit_range() has an additional parameter @offset, > + * so it can search within a specific range of the bitmap, > + * just like the find_next_bit(). > + * > + * Returns the bit number of the last set bit, or size. > + */ > +static __always_inline > +unsigned long find_last_bit_range(const unsigned long *addr, unsigned lo= ng size, > + unsigned long offset) This should be called find_last_bit_off instead. `_range` suffix, to me at least, implies that the order of arguments is (addr, offset, size). `_off` is also the suffix used by `bitmap_find_next_zero_area_off` name. > +{ > + if (small_const_nbits(size)) { > + unsigned long val; > + > + if (unlikely(offset >=3D size)) > + return size; > + > + val =3D *addr & GENMASK(size - 1, offset); > + > + return val ? __fls(val) : size; > + } > + > + return _find_last_bit_range(addr, size, offset); > +} > +#endif > + > /** > * find_next_and_bit_wrap - find the next set bit in both memory regions > * @addr1: The first address to base the search on > diff --git a/lib/find_bit.c b/lib/find_bit.c > index 5ac52dfce730..bedc85053cea 100644 > --- a/lib/find_bit.c > +++ b/lib/find_bit.c > @@ -237,6 +237,36 @@ unsigned long _find_last_bit(const unsigned long *ad= dr, unsigned long size) > EXPORT_SYMBOL(_find_last_bit); > #endif >=20=20 > +#ifndef find_last_bit_range > +unsigned long _find_last_bit_range(const unsigned long *addr, unsigned l= ong size, > + unsigned long offset) > +{ > + unsigned long val, idx, start_idx; > + > + if (unlikely(offset >=3D size)) > + return size; > + > + val =3D BITMAP_LAST_WORD_MASK(size); > + idx =3D (size - 1) / BITS_PER_LONG; > + start_idx =3D offset / BITS_PER_LONG; > + > + do { > + val &=3D addr[idx]; > + > + if (idx =3D=3D start_idx) > + val &=3D BITMAP_FIRST_WORD_MASK(offset); > + > + if (val) > + return idx * BITS_PER_LONG + __fls(val); > + > + val =3D ~0UL; > + } while (idx-- > start_idx); Perhaps: ``` val =3D BITMAP_LAST_WORD_MASK(size) & addr[idx]; while (!val && idx > start_idx) val =3D addr[--idx]; if (idx =3D=3D start_idx) val &=3D BITMAP_FIRST_WORD_MASK(offset); return val ? idx * BITS_PER_LONG + __fls(val) : size; ``` This moves the `idx =3D=3D start_idx` condition outside of the loop so that it=E2=80=99s not checked on each iteration. It also removes the need for `= val =3D ~0UL` from the loop again simplifying its body. > + > + return size; > +} > +EXPORT_SYMBOL(_find_last_bit_range); > +#endif > + > unsigned long find_next_clump8(unsigned long *clump, const unsigned long= *addr, > unsigned long size, unsigned long offset) > { --=20 Best regards =E3=83=9F=E3=83=8F=E3=82=A6 =E2=80=9C=F0=9D=93=B6=F0=9D=93=B2=F0=9D=93=B7= =F0=9D=93=AA86=E2=80=9D =E3=83=8A=E3=82=B6=E3=83=AC=E3=83=B4=E3=82=A3=E3=83= =84 =C2=ABIf at first you don=E2=80=99t succeed, give up skydiving=C2=BB