From nobody Fri Apr 3 06:44:50 2026 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by smtp.lore.kernel.org (Postfix) with ESMTP id C382AECAAD8 for ; Thu, 15 Sep 2022 02:07:46 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S230163AbiIOCHn (ORCPT ); Wed, 14 Sep 2022 22:07:43 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:33970 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S229498AbiIOCHh (ORCPT ); Wed, 14 Sep 2022 22:07:37 -0400 Received: from mail-qk1-x72e.google.com (mail-qk1-x72e.google.com [IPv6:2607:f8b0:4864:20::72e]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 4800E8E9A8 for ; Wed, 14 Sep 2022 19:07:36 -0700 (PDT) Received: by mail-qk1-x72e.google.com with SMTP id q11so9232144qkc.12 for ; Wed, 14 Sep 2022 19:07:36 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20210112; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date; bh=K2R1iy21HsJbeE0Fr+rvJINP8Hx2Z3d/5iM9+cUl0Mc=; b=MtE4YlPz6GSinYPA7O6U58FScSNenLLpnFARHYmejMCEbQ8SjfT+VPr9HvfYfRDVKG 0VcJ+QE5TBow44fI7GypVig5xj0eVFs8z4rM3/iECjw+Q9B/CVMj5abLnYi20syh1vtQ VaNsoi9siBz/hjvR38gja49xd72rBEsyp6N4/wQZSzNoo27NFe1JjCdf4btz0jvQpOOQ upSxM3fZmfTLwNAurS1Bf4rtIIx7RrSnyF4rB/Verp73+2c2YJ/tKgKWOSqBaZYYIM2B hgivupoOy/xsI+cwqEk9XCzLY0Cl/mi1LaoPnRyklIMSCKApeFZ3TN3z+ef0Ba8/lUx/ Utow== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; 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; bh=K2R1iy21HsJbeE0Fr+rvJINP8Hx2Z3d/5iM9+cUl0Mc=; b=1tFLJG9zzp+cUKWtQcVjGGgVStTpqlNMdZXgEALS/8zfLePvLFaBpbk0qpf2fbP56E GIDXMqIEJKLabXKz7zsb8HcoXwgS7z+uIk5HAffkNFNhDfWZravspxsLX79nkGPUxDGS mt/rU5iRdyIK0IXNzcG59vUax8qnIPpcTmwmbkwPmikNukM2a/LHTzivz1UnL15/zwsO 5St/k5gvTM1TChUIEpd6QT6mbilA9v0lvGL7ZrVRDDH1Ybd1gL7VeMfbc5CW54/Gdt7M RAfJy3VnpSFZa+IAvI1C7fhLIasdMiA4ld2BhhS8oeHkEYXDv1iVbTcWxt8bl3nDO/nk jp1w== X-Gm-Message-State: ACgBeo1AfAWALvNasFx+UHUlWMPCjRB6IdzFGdVUGvENwV8wLJvFzBP9 0U45zz96exrKM/wET4NVU4BM3wk+yIk= X-Google-Smtp-Source: AA6agR5+wjLr8XCFamIspuz6ol/NsYiy/v95crsMi2gk010QtKIGdh/6yUYNia/tNfjAUWDLhKPNNA== X-Received: by 2002:a05:620a:bc6:b0:6bc:644b:8e94 with SMTP id s6-20020a05620a0bc600b006bc644b8e94mr28710551qki.321.1663207655353; Wed, 14 Sep 2022 19:07:35 -0700 (PDT) Received: from localhost (96-87-29-153-static.hfc.comcastbusiness.net. [96.87.29.153]) by smtp.gmail.com with ESMTPSA id v26-20020ac8729a000000b0031f36cd1958sm2485833qto.81.2022.09.14.19.07.34 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Wed, 14 Sep 2022 19:07:35 -0700 (PDT) From: Yury Norov To: Linus Torvalds , linux-kernel@vger.kernel.org Cc: Yury Norov , Alexey Klimov , Andy Shevchenko , Andy Whitcroft , Catalin Marinas , David Laight , Dennis Zhou , Guenter Roeck , Kees Cook , Rasmus Villemoes , Valentin Schneider , Sven Schnelle , Russell King Subject: [PATCH v4 1/4] lib/find_bit: introduce FIND_FIRST_BIT() macro Date: Wed, 14 Sep 2022 19:07:27 -0700 Message-Id: <20220915020730.852234-2-yury.norov@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20220915020730.852234-1-yury.norov@gmail.com> References: <20220915020730.852234-1-yury.norov@gmail.com> MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org Content-Type: text/plain; charset="utf-8" Now that we have many flavors of find_first_bit(), and expect even more, it's better to have one macro that generates optimal code for all and makes maintaining of slightly different functions simpler. The logic common to all versions is moved to the new macro, and all the flavors are generated by providing an FETCH macro-parameter, like in this example: #define FIND_FIRST_BIT(FETCH, MUNGE, size) ... find_first_ornot_and_bit(addr1, addr2, addr3, size) { return FIND_FIRST_BIT(addr1[idx] | ~addr2[idx] & addr3[idx], /* nop= */, size); } The FETCH may be of any complexity, as soon as it only refers the bitmap(s) and an iterator idx. MUNGE is here to support _le code generation for BE builds. May be empty. Suggested-by: Linus Torvalds Reviewed-by: Valentin Schneider Signed-off-by: Yury Norov --- lib/find_bit.c | 49 ++++++++++++++++++++++++------------------------- 1 file changed, 24 insertions(+), 25 deletions(-) diff --git a/lib/find_bit.c b/lib/find_bit.c index 1b8e4b2a9cba..894b656f6836 100644 --- a/lib/find_bit.c +++ b/lib/find_bit.c @@ -19,6 +19,27 @@ #include #include =20 +/* + * Common helper for find_bit() function family + * @FETCH: The expression that fetches and pre-processes each word of bitm= ap(s) + * @MUNGE: The expression that post-processes a word containing found bit = (may be empty) + * @size: The bitmap size in bits + */ +#define FIND_FIRST_BIT(FETCH, MUNGE, size) \ +({ \ + unsigned long idx, val, sz =3D (size); \ + \ + for (idx =3D 0; idx * BITS_PER_LONG < sz; idx++) { \ + val =3D (FETCH); \ + if (val) { \ + sz =3D min(idx * BITS_PER_LONG + __ffs(MUNGE(val)), sz); \ + break; \ + } \ + } \ + \ + sz; \ +}) + #if !defined(find_next_bit) || !defined(find_next_zero_bit) || \ !defined(find_next_bit_le) || !defined(find_next_zero_bit_le) || \ !defined(find_next_and_bit) @@ -77,14 +98,7 @@ EXPORT_SYMBOL(_find_next_bit); */ unsigned long _find_first_bit(const unsigned long *addr, unsigned long siz= e) { - unsigned long idx; - - for (idx =3D 0; idx * BITS_PER_LONG < size; idx++) { - if (addr[idx]) - return min(idx * BITS_PER_LONG + __ffs(addr[idx]), size); - } - - return size; + return FIND_FIRST_BIT(addr[idx], /* nop */, size); } EXPORT_SYMBOL(_find_first_bit); #endif @@ -97,15 +111,7 @@ unsigned long _find_first_and_bit(const unsigned long *= addr1, const unsigned long *addr2, unsigned long size) { - unsigned long idx, val; - - for (idx =3D 0; idx * BITS_PER_LONG < size; idx++) { - val =3D addr1[idx] & addr2[idx]; - if (val) - return min(idx * BITS_PER_LONG + __ffs(val), size); - } - - return size; + return FIND_FIRST_BIT(addr1[idx] & addr2[idx], /* nop */, size); } EXPORT_SYMBOL(_find_first_and_bit); #endif @@ -116,14 +122,7 @@ EXPORT_SYMBOL(_find_first_and_bit); */ unsigned long _find_first_zero_bit(const unsigned long *addr, unsigned lon= g size) { - unsigned long idx; - - for (idx =3D 0; idx * BITS_PER_LONG < size; idx++) { - if (addr[idx] !=3D ~0UL) - return min(idx * BITS_PER_LONG + ffz(addr[idx]), size); - } - - return size; + return FIND_FIRST_BIT(~addr[idx], /* nop */, size); } EXPORT_SYMBOL(_find_first_zero_bit); #endif --=20 2.34.1 From nobody Fri Apr 3 06:44:50 2026 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by smtp.lore.kernel.org (Postfix) with ESMTP id 80A22C6FA82 for ; Thu, 15 Sep 2022 02:07:48 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S229665AbiIOCHq (ORCPT ); Wed, 14 Sep 2022 22:07:46 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:33976 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S230134AbiIOCHh (ORCPT ); Wed, 14 Sep 2022 22:07:37 -0400 Received: from mail-qt1-x82c.google.com (mail-qt1-x82c.google.com [IPv6:2607:f8b0:4864:20::82c]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 2900C8E9A3 for ; Wed, 14 Sep 2022 19:07:37 -0700 (PDT) Received: by mail-qt1-x82c.google.com with SMTP id cj27so434912qtb.7 for ; Wed, 14 Sep 2022 19:07:37 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20210112; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date; bh=3+iTs7Qci+cQAiUkXQV8UIioBFj35PInyrTjTdgkjzM=; b=Tc0X3VRnLhT04xI+XfW7wjfijgeKow0ZUOe5T6e/nT+yvW8ECrkf/+IVs09upXULh1 Jl+EON47HmzO70hb51m2HWXztDLyL6iwcXrusFujfAG7RqmKthBKggvNZbVdmRX4leKW oSXBnzX3TBN4xhx7qrXNezuKGVehmr9JTPXM3ejhWFY8h92ThJZ9gFwaljxD1iuWzzH6 SiZvlHSldccCxuF+j1c1ReLXJgNnM40cRuy9Rlp+pnAdzXRyh5vLzIH9MwVaohVEg682 bRhPJ3CHJaO8ghf9D/ZzE4xaZjr2WUJ0R4U839XZZPkYnvq/o5inFZcLrzD+zt5ZkQ48 2+WQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; 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; bh=3+iTs7Qci+cQAiUkXQV8UIioBFj35PInyrTjTdgkjzM=; b=c2Nmg0Uq0S2UkJmoHvPWbswlw/IN9MXgEH5pntF+4gzSezI5YefAabFIH4ABsWfmKI RJrs1KY3eAPNeT92dmn8zqJdAYzETKfu+wz6FwbBRFiQobaaInhM3DBhphyzk93QqMac TBlnz71Yn48W1mWj/5YntQ81RShakLyOi90qlidU+f+Oy6+2xw3e8Q/HMMKcqDugEAQR zi0AiVn1Abv71BC6QOM2ECmLGPFTP8Dh0B/torH5j+zbZqE2Ka6TIsnMQIZ5nQtlc0A0 6SeE5lg8F8E6TAmB1Aff9ouZBasL0SVWmrlDaXdUyqSOwoZaWhILzBl3+VCxXryCkK1c ZaoA== X-Gm-Message-State: ACgBeo3mpqLCqTrQxvhgoi/tpa6wKDkMf8WnzZDwom6TWU9mtMcsK3JY sgafHJ7H/y3ZEa6IikLSzlg= X-Google-Smtp-Source: AA6agR7m/mLwKEBVZiieSHstxBu6MKX6UIaW9upYvHvQ8i0DfggUcpjyXKeucYsiDeIlV95y7ehw6A== X-Received: by 2002:ac8:5c51:0:b0:344:5510:be77 with SMTP id j17-20020ac85c51000000b003445510be77mr36449031qtj.84.1663207656216; Wed, 14 Sep 2022 19:07:36 -0700 (PDT) Received: from localhost (96-87-29-153-static.hfc.comcastbusiness.net. [96.87.29.153]) by smtp.gmail.com with ESMTPSA id bp44-20020a05622a1bac00b0034456277e3asm2549454qtb.89.2022.09.14.19.07.35 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Wed, 14 Sep 2022 19:07:36 -0700 (PDT) From: Yury Norov To: Linus Torvalds , linux-kernel@vger.kernel.org Cc: Yury Norov , Alexey Klimov , Andy Shevchenko , Andy Whitcroft , Catalin Marinas , David Laight , Dennis Zhou , Guenter Roeck , Kees Cook , Rasmus Villemoes , Valentin Schneider , Sven Schnelle , Russell King Subject: [PATCH v4 2/4] lib/find_bit: create find_first_zero_bit_le() Date: Wed, 14 Sep 2022 19:07:28 -0700 Message-Id: <20220915020730.852234-3-yury.norov@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20220915020730.852234-1-yury.norov@gmail.com> References: <20220915020730.852234-1-yury.norov@gmail.com> MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org Content-Type: text/plain; charset="utf-8" find_first_zero_bit_le() is an alias to find_next_zero_bit_le(), despite that 'next' is known to be slower than 'first' version. Now that we have common FIND_FIRST_BIT() macro helper, it's trivial to implement find_first_zero_bit_le() as a real function. Reviewed-by: Valentin Schneider Signed-off-by: Yury Norov --- include/linux/find.h | 23 ++++++++++++++++++----- lib/find_bit.c | 14 ++++++++++++++ 2 files changed, 32 insertions(+), 5 deletions(-) diff --git a/include/linux/find.h b/include/linux/find.h index 424ef67d4a42..2464bff5de04 100644 --- a/include/linux/find.h +++ b/include/linux/find.h @@ -17,6 +17,10 @@ extern unsigned long _find_first_and_bit(const unsigned = long *addr1, extern unsigned long _find_first_zero_bit(const unsigned long *addr, unsig= ned long size); extern unsigned long _find_last_bit(const unsigned long *addr, unsigned lo= ng size); =20 +#ifdef __BIG_ENDIAN +unsigned long _find_first_zero_bit_le(const unsigned long *addr, unsigned = long size); +#endif + #ifndef find_next_bit /** * find_next_bit - find the next set bit in a memory region @@ -251,6 +255,20 @@ unsigned long find_next_zero_bit_le(const void *addr, = unsigned } #endif =20 +#ifndef find_first_zero_bit_le +static inline +unsigned long find_first_zero_bit_le(const void *addr, unsigned long size) +{ + if (small_const_nbits(size)) { + unsigned long val =3D swab(*(const unsigned long *)addr) | ~GENMASK(size= - 1, 0); + + return val =3D=3D ~0UL ? size : ffz(val); + } + + return _find_first_zero_bit_le(addr, size); +} +#endif + #ifndef find_next_bit_le static inline unsigned long find_next_bit_le(const void *addr, unsigned @@ -270,11 +288,6 @@ unsigned long find_next_bit_le(const void *addr, unsig= ned } #endif =20 -#ifndef find_first_zero_bit_le -#define find_first_zero_bit_le(addr, size) \ - find_next_zero_bit_le((addr), (size), 0) -#endif - #else #error "Please fix " #endif diff --git a/lib/find_bit.c b/lib/find_bit.c index 894b656f6836..f4d9b9684811 100644 --- a/lib/find_bit.c +++ b/lib/find_bit.c @@ -160,3 +160,17 @@ unsigned long find_next_clump8(unsigned long *clump, c= onst unsigned long *addr, return offset; } EXPORT_SYMBOL(find_next_clump8); + +#ifdef __BIG_ENDIAN +#ifndef find_first_zero_bit_le +/* + * Find the first cleared bit in an LE memory region. + */ +unsigned long _find_first_zero_bit_le(const unsigned long *addr, unsigned = long size) +{ + return FIND_FIRST_BIT(~addr[idx], swab, size); +} +EXPORT_SYMBOL(_find_first_zero_bit_le); +#endif + +#endif /* __BIG_ENDIAN */ --=20 2.34.1 From nobody Fri Apr 3 06:44:50 2026 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by smtp.lore.kernel.org (Postfix) with ESMTP id A5922ECAAD8 for ; Thu, 15 Sep 2022 02:07:53 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S230181AbiIOCHv (ORCPT ); Wed, 14 Sep 2022 22:07:51 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:34010 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S230143AbiIOCHj (ORCPT ); Wed, 14 Sep 2022 22:07:39 -0400 Received: from mail-qt1-x82d.google.com (mail-qt1-x82d.google.com [IPv6:2607:f8b0:4864:20::82d]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 1FA1D8E9AE for ; Wed, 14 Sep 2022 19:07:38 -0700 (PDT) Received: by mail-qt1-x82d.google.com with SMTP id cj27so434936qtb.7 for ; Wed, 14 Sep 2022 19:07:38 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20210112; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date; bh=D2+7cCsVxWQuJxreBgAxCUqwVsvEMV0WKolCrPdQo9s=; b=LkVN93nD5+CfQcifA7mk/QAmkSOEA1E7M7PSWCs0RY897s7vx9bMIrk9q1R81AfafG JJ8sJz4yyo7Lo8GQjC3IGcT0+fKgUDNSGwl+m23KZeJxRaGGu17VdVpCCJLUx7ngyEB2 M4GkkVT1CargLzseq5Gi3GaE76d1k0UnH5yBg0Bhuee4ya5/JEgtCqkMInsJo7a2lzv0 ph/Ju2Iq/uW3PXdjGLttzGDCJ/B/Z8fN54GAE8fpRqDdDsRKNbB4qPnALU8JRTHn+Qoz 1Idv5y34jx1st/wdlVOpms2IR9et/d2G65bldlKeq9KffKcgJF/qokLVMXrEFJIlj7iq ZrnA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; 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; bh=D2+7cCsVxWQuJxreBgAxCUqwVsvEMV0WKolCrPdQo9s=; b=Gb18rllu4otx5RWYCC0OgN4iSRsnQumUlYA4KJ8MEiOutBe7q+kgDbFADlkkz3DJFF CD7tVB5JNQOOlyi5rRwPEqocdOJSHDYazy/7aa13VCEYlzuHy0ihzlhXYkJh62GTuob3 ZZcSppp0tbxPbHjdQt2MbhVRoXzcYZoGC3vvuxxS9UqK0uzLCtifIQJwm5JleKgGS1jV eWc3PMIdzPmJ08JBspmwcnO8tHQ43uyfAjLorgInWrAwvj10FOn8e4ynHq/mA85226c3 6l+uLTvHML167S9fJj/XwdMwHDlkOo9wUNBH3YSCqCGd4vWvCDEn1967bkyxqL4DGpH9 UWcw== X-Gm-Message-State: ACgBeo2kmSAS9lxc9oEvWCRxwgz9r/pwfPfM5f4gIvK/CVTLaiUqkrO0 4vdQAHEexPQ4m1ZF/rTOSHA= X-Google-Smtp-Source: AA6agR44yYVr1Jlzy50qD7g6yi2RLqNn6EssYR5fc4KMn/CUOcdOKmka5QKyW1mKcMQIH9jiDqVgcA== X-Received: by 2002:ac8:5b53:0:b0:35b:a628:873c with SMTP id n19-20020ac85b53000000b0035ba628873cmr23051922qtw.398.1663207657161; Wed, 14 Sep 2022 19:07:37 -0700 (PDT) Received: from localhost (96-87-29-153-static.hfc.comcastbusiness.net. [96.87.29.153]) by smtp.gmail.com with ESMTPSA id br36-20020a05620a462400b006cbbc3daaacsm2919544qkb.113.2022.09.14.19.07.36 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Wed, 14 Sep 2022 19:07:36 -0700 (PDT) From: Yury Norov To: Linus Torvalds , linux-kernel@vger.kernel.org Cc: Yury Norov , Alexey Klimov , Andy Shevchenko , Andy Whitcroft , Catalin Marinas , David Laight , Dennis Zhou , Guenter Roeck , Kees Cook , Rasmus Villemoes , Valentin Schneider , Sven Schnelle , Russell King Subject: [PATCH v4 3/4] lib/find_bit: optimize find_next_bit() functions Date: Wed, 14 Sep 2022 19:07:29 -0700 Message-Id: <20220915020730.852234-4-yury.norov@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20220915020730.852234-1-yury.norov@gmail.com> References: <20220915020730.852234-1-yury.norov@gmail.com> MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org Content-Type: text/plain; charset="utf-8" Over the past couple years, the function _find_next_bit() was extended with parameters that modify its behavior to implement and- zero- and le- flavors. The parameters are passed at compile time, but current design prevents a compiler from optimizing out the conditionals. As find_next_bit() API grows, I expect that more parameters will be added. Current design would require more conditional code in _find_next_bit(), which would bloat the helper even more and make it barely readable. This patch replaces _find_next_bit() with a macro FIND_NEXT_BIT, and adds a set of wrappers, so that the compile-time optimizations become possible. The common logic is moved to the new macro, and all flavors may be generated by providing a FETCH macro parameter, like in this example: #define FIND_NEXT_BIT(FETCH, MUNGE, size, start) ... find_next_xornot_and_bit(addr1, addr2, addr3, size, start) { return FIND_NEXT_BIT(addr1[idx] ^ ~addr2[idx] & addr3[idx], /* nop */, size, start); } The FETCH may be of any complexity, as soon as it only refers the bitmap(s) and an iterator idx. MUNGE is here to support _le code generation for BE builds. May be empty. I ran find_bit_benchmark 16 times on top of 6.0-rc2 and 16 times on top of 6.0-rc2 + this series. The results for kvm/x86_64 are: v6.0-rc2 Optimized Difference Z-score Random dense bitmap ns ns ns % find_next_bit: 787735 670546 117189 14.9 3.97 find_next_zero_bit: 777492 664208 113284 14.6 10.51 find_last_bit: 830925 687573 143352 17.3 2.35 find_first_bit: 3874366 3306635 567731 14.7 1.84 find_first_and_bit: 40677125 37739887 2937238 7.2 1.36 find_next_and_bit: 347865 304456 43409 12.5 1.35 Random sparse bitmap find_next_bit: 19816 14021 5795 29.2 6.10 find_next_zero_bit: 1318901 1223794 95107 7.2 1.41 find_last_bit: 14573 13514 1059 7.3 6.92 find_first_bit: 1313321 1249024 64297 4.9 1.53 find_first_and_bit: 8921 8098 823 9.2 4.56 find_next_and_bit: 9796 7176 2620 26.7 5.39 Where the statistics is significant (z-score > 3), the improvement is ~15%. According to the bloat-o-meter, the Image size is 10-11K less: x86_64/defconfig: add/remove: 32/14 grow/shrink: 61/782 up/down: 6344/-16521 (-10177) arm64/defconfig: add/remove: 3/2 grow/shrink: 50/714 up/down: 608/-11556 (-10948) Suggested-by: Linus Torvalds Signed-off-by: Yury Norov Reviewed-by: Valentin Schneider --- include/linux/find.h | 23 ++++++--- lib/find_bit.c | 119 +++++++++++++++++++++++++------------------ 2 files changed, 85 insertions(+), 57 deletions(-) diff --git a/include/linux/find.h b/include/linux/find.h index 2464bff5de04..dead6f53a97b 100644 --- a/include/linux/find.h +++ b/include/linux/find.h @@ -8,9 +8,12 @@ =20 #include =20 -extern unsigned long _find_next_bit(const unsigned long *addr1, - const unsigned long *addr2, unsigned long nbits, - unsigned long start, unsigned long invert, unsigned long le); +unsigned long _find_next_bit(const unsigned long *addr1, unsigned long nbi= ts, + unsigned long start); +unsigned long _find_next_and_bit(const unsigned long *addr1, const unsigne= d long *addr2, + unsigned long nbits, unsigned long start); +unsigned long _find_next_zero_bit(const unsigned long *addr, unsigned long= nbits, + unsigned long start); extern unsigned long _find_first_bit(const unsigned long *addr, unsigned l= ong size); extern unsigned long _find_first_and_bit(const unsigned long *addr1, const unsigned long *addr2, unsigned long size); @@ -19,6 +22,10 @@ extern unsigned long _find_last_bit(const unsigned long = *addr, unsigned long siz =20 #ifdef __BIG_ENDIAN unsigned long _find_first_zero_bit_le(const unsigned long *addr, unsigned = long size); +unsigned long _find_next_zero_bit_le(const unsigned long *addr, unsigned + long size, unsigned long offset); +unsigned long _find_next_bit_le(const unsigned long *addr, unsigned + long size, unsigned long offset); #endif =20 #ifndef find_next_bit @@ -45,7 +52,7 @@ unsigned long find_next_bit(const unsigned long *addr, un= signed long size, return val ? __ffs(val) : size; } =20 - return _find_next_bit(addr, NULL, size, offset, 0UL, 0); + return _find_next_bit(addr, size, offset); } #endif =20 @@ -75,7 +82,7 @@ unsigned long find_next_and_bit(const unsigned long *addr= 1, return val ? __ffs(val) : size; } =20 - return _find_next_bit(addr1, addr2, size, offset, 0UL, 0); + return _find_next_and_bit(addr1, addr2, size, offset); } #endif =20 @@ -103,7 +110,7 @@ unsigned long find_next_zero_bit(const unsigned long *a= ddr, unsigned long size, return val =3D=3D ~0UL ? size : ffz(val); } =20 - return _find_next_bit(addr, NULL, size, offset, ~0UL, 0); + return _find_next_zero_bit(addr, size, offset); } #endif =20 @@ -251,7 +258,7 @@ unsigned long find_next_zero_bit_le(const void *addr, u= nsigned return val =3D=3D ~0UL ? size : ffz(val); } =20 - return _find_next_bit(addr, NULL, size, offset, ~0UL, 1); + return _find_next_zero_bit_le(addr, size, offset); } #endif =20 @@ -284,7 +291,7 @@ unsigned long find_next_bit_le(const void *addr, unsign= ed return val ? __ffs(val) : size; } =20 - return _find_next_bit(addr, NULL, size, offset, 0UL, 1); + return _find_next_bit_le(addr, size, offset); } #endif =20 diff --git a/lib/find_bit.c b/lib/find_bit.c index f4d9b9684811..8707b4ef3e5e 100644 --- a/lib/find_bit.c +++ b/lib/find_bit.c @@ -40,57 +40,33 @@ sz; \ }) =20 -#if !defined(find_next_bit) || !defined(find_next_zero_bit) || \ - !defined(find_next_bit_le) || !defined(find_next_zero_bit_le) || \ - !defined(find_next_and_bit) /* - * This is a common helper function for find_next_bit, find_next_zero_bit,= and - * find_next_and_bit. The differences are: - * - The "invert" argument, which is XORed with each fetched word before - * searching it for one bits. - * - The optional "addr2", which is anded with "addr1" if present. + * Common helper for find_next_bit() function family + * @FETCH: The expression that fetches and pre-processes each word of bitm= ap(s) + * @MUNGE: The expression that post-processes a word containing found bit = (may be empty) + * @size: The bitmap size in bits + * @start: The bitnumber to start searching at */ -unsigned long _find_next_bit(const unsigned long *addr1, - const unsigned long *addr2, unsigned long nbits, - unsigned long start, unsigned long invert, unsigned long le) -{ - unsigned long tmp, mask; - - if (unlikely(start >=3D nbits)) - return nbits; - - tmp =3D addr1[start / BITS_PER_LONG]; - if (addr2) - tmp &=3D addr2[start / BITS_PER_LONG]; - tmp ^=3D invert; - - /* Handle 1st word. */ - mask =3D BITMAP_FIRST_WORD_MASK(start); - if (le) - mask =3D swab(mask); - - tmp &=3D mask; - - start =3D round_down(start, BITS_PER_LONG); - - while (!tmp) { - start +=3D BITS_PER_LONG; - if (start >=3D nbits) - return nbits; - - tmp =3D addr1[start / BITS_PER_LONG]; - if (addr2) - tmp &=3D addr2[start / BITS_PER_LONG]; - tmp ^=3D invert; - } - - if (le) - tmp =3D swab(tmp); - - return min(start + __ffs(tmp), nbits); -} -EXPORT_SYMBOL(_find_next_bit); -#endif +#define FIND_NEXT_BIT(FETCH, MUNGE, size, start) \ +({ \ + unsigned long mask, idx, tmp, sz =3D (size), __start =3D (start); \ + \ + if (unlikely(__start >=3D sz)) \ + goto out; \ + \ + mask =3D MUNGE(BITMAP_FIRST_WORD_MASK(__start)); \ + idx =3D __start / BITS_PER_LONG; \ + \ + for (tmp =3D (FETCH) & mask; !tmp; tmp =3D (FETCH)) { \ + if ((idx + 1) * BITS_PER_LONG >=3D sz) \ + goto out; \ + idx++; \ + } \ + \ + sz =3D min(idx * BITS_PER_LONG + __ffs(MUNGE(tmp)), sz); \ +out: \ + sz; \ +}) =20 #ifndef find_first_bit /* @@ -127,6 +103,32 @@ unsigned long _find_first_zero_bit(const unsigned long= *addr, unsigned long size EXPORT_SYMBOL(_find_first_zero_bit); #endif =20 +#ifndef find_next_bit +unsigned long _find_next_bit(const unsigned long *addr, unsigned long nbit= s, unsigned long start) +{ + return FIND_NEXT_BIT(addr[idx], /* nop */, nbits, start); +} +EXPORT_SYMBOL(_find_next_bit); +#endif + +#ifndef find_next_and_bit +unsigned long _find_next_and_bit(const unsigned long *addr1, const unsigne= d long *addr2, + unsigned long nbits, unsigned long start) +{ + return FIND_NEXT_BIT(addr1[idx] & addr2[idx], /* nop */, nbits, start); +} +EXPORT_SYMBOL(_find_next_and_bit); +#endif + +#ifndef find_next_zero_bit +unsigned long _find_next_zero_bit(const unsigned long *addr, unsigned long= nbits, + unsigned long start) +{ + return FIND_NEXT_BIT(~addr[idx], /* nop */, nbits, start); +} +EXPORT_SYMBOL(_find_next_zero_bit); +#endif + #ifndef find_last_bit unsigned long _find_last_bit(const unsigned long *addr, unsigned long size) { @@ -173,4 +175,23 @@ unsigned long _find_first_zero_bit_le(const unsigned l= ong *addr, unsigned long s EXPORT_SYMBOL(_find_first_zero_bit_le); #endif =20 +#ifndef find_next_zero_bit_le +unsigned long _find_next_zero_bit_le(const unsigned long *addr, unsigned + long size, unsigned long offset) +{ + return FIND_NEXT_BIT(~addr[idx], swab, size, offset); +} +EXPORT_SYMBOL(_find_next_zero_bit_le); +#endif + +#ifndef find_next_bit_le +unsigned long _find_next_bit_le(const unsigned long *addr, unsigned + long size, unsigned long offset) +{ + return FIND_NEXT_BIT(addr[idx], swab, size, offset); +} +EXPORT_SYMBOL(_find_next_bit_le); + +#endif + #endif /* __BIG_ENDIAN */ --=20 2.34.1 From nobody Fri Apr 3 06:44:50 2026 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by smtp.lore.kernel.org (Postfix) with ESMTP id C061DECAAD8 for ; Thu, 15 Sep 2022 02:07:57 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S230212AbiIOCHx (ORCPT ); Wed, 14 Sep 2022 22:07:53 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:34024 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S230160AbiIOCHk (ORCPT ); Wed, 14 Sep 2022 22:07:40 -0400 Received: from mail-qk1-x734.google.com (mail-qk1-x734.google.com [IPv6:2607:f8b0:4864:20::734]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 123CE8E9B5 for ; Wed, 14 Sep 2022 19:07:39 -0700 (PDT) Received: by mail-qk1-x734.google.com with SMTP id c19so10368760qkm.7 for ; Wed, 14 Sep 2022 19:07:39 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20210112; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date; bh=HoazOBg3gnF+fFlmxx/8Q7AvXXy8sKGesbRgGW+mA+4=; b=j2Bfpw0lJCB8yILkHqGGbPyD/zAeBmkpPOn0E9qnpf5IE5b0CoYc+iau/E7TLE4WZO kY1iLV0gmqAowZmT/Hz6+u9zq7tJF6+IEWD8l6/1mO+671Aa3NqwTOlvUt2ltgO3Afxk gtYtPH81be96bEEEhA4qENkE+G0T+4F/8rUxRR/+1cA8vmvUIFMpAFVg05JPDliTIlb8 HLqNpRbkXKJghl5zoamPS9Kfd4SBUjga52YXd6wZXS0OikU81RYm3KZ8/1+eGWdxz/6V DmczdV2W0fVxLa/gjLHMfqxusN770G+xHQYIIfII/H9Re0AF6ryTqW0aY+W+AA4CoPOq yEmg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; 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; bh=HoazOBg3gnF+fFlmxx/8Q7AvXXy8sKGesbRgGW+mA+4=; b=SQsXT+yPyIcJ/mPyF7aTkwVXrxz84lgoEipGyj8O9hyodS0+EfsLQ+C5VZ6IdGVEfl GN0Cu3AiK9uo60rPMCHHjSCPw9NhaVSpy81wttAtOReElGWK1IINF+sbgD9fx+B7WpST LSFNdhXn1B+6EatMtKVNoLe4g7xzSMpQEJQUGVQY4Oks8HZd0BuCmf1sDCaGafPNIlHt pDUg+xsb2Jj8M3ap2cRzpzgT1vX4Qv4X2ockfUo5dWclSSY/LNspu10f0EL2vsdHepNp kXEoScbXL3lY0tmMS1TjouX6UjYgJK1x3ejsvYfmOfHsT04AaWzpqHY9GiP30c64Nm4G HMRQ== X-Gm-Message-State: ACgBeo12e+rOtZeREdccY1MxgD9isvlG46HODW1XFRthWg+NaT6DP4G/ XNng/0E7J+Ws5xDGYiJvJCU= X-Google-Smtp-Source: AA6agR71SisC4a4Uy1pOY8EzMgvzbcl1A4BdEEdaxU+BhYI3d1RF29G07PJHeXYbCEoMZ3HAB23R7w== X-Received: by 2002:a05:620a:4403:b0:6ce:9be8:fe98 with SMTP id v3-20020a05620a440300b006ce9be8fe98mr2772898qkp.761.1663207658027; Wed, 14 Sep 2022 19:07:38 -0700 (PDT) Received: from localhost (96-87-29-153-static.hfc.comcastbusiness.net. [96.87.29.153]) by smtp.gmail.com with ESMTPSA id q8-20020a05620a0d8800b006ce407b996asm3141376qkl.69.2022.09.14.19.07.37 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Wed, 14 Sep 2022 19:07:37 -0700 (PDT) From: Yury Norov To: Linus Torvalds , linux-kernel@vger.kernel.org Cc: Yury Norov , Alexey Klimov , Andy Shevchenko , Andy Whitcroft , Catalin Marinas , David Laight , Dennis Zhou , Guenter Roeck , Kees Cook , Rasmus Villemoes , Valentin Schneider , Sven Schnelle , Russell King Subject: [PATCH v4 4/4] tools: sync find_bit() implementation Date: Wed, 14 Sep 2022 19:07:30 -0700 Message-Id: <20220915020730.852234-5-yury.norov@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20220915020730.852234-1-yury.norov@gmail.com> References: <20220915020730.852234-1-yury.norov@gmail.com> MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org Content-Type: text/plain; charset="utf-8" Sync find_first_bit() and find_next_bit() implementation with the mother kernel. Also, drop unused find_last_bit() and find_next_clump8(). Signed-off-by: Yury Norov --- tools/include/linux/find.h | 61 +++------------ tools/lib/find_bit.c | 149 +++++++++++++++++-------------------- 2 files changed, 81 insertions(+), 129 deletions(-) diff --git a/tools/include/linux/find.h b/tools/include/linux/find.h index 47e2bd6c5174..38c0a542b0e2 100644 --- a/tools/include/linux/find.h +++ b/tools/include/linux/find.h @@ -8,21 +8,23 @@ =20 #include =20 -extern unsigned long _find_next_bit(const unsigned long *addr1, - const unsigned long *addr2, unsigned long nbits, - unsigned long start, unsigned long invert, unsigned long le); +unsigned long _find_next_bit(const unsigned long *addr1, unsigned long nbi= ts, + unsigned long start); +unsigned long _find_next_and_bit(const unsigned long *addr1, const unsigne= d long *addr2, + unsigned long nbits, unsigned long start); +unsigned long _find_next_zero_bit(const unsigned long *addr, unsigned long= nbits, + unsigned long start); extern unsigned long _find_first_bit(const unsigned long *addr, unsigned l= ong size); extern unsigned long _find_first_and_bit(const unsigned long *addr1, const unsigned long *addr2, unsigned long size); extern unsigned long _find_first_zero_bit(const unsigned long *addr, unsig= ned long size); -extern unsigned long _find_last_bit(const unsigned long *addr, unsigned lo= ng size); =20 #ifndef find_next_bit /** * find_next_bit - find the next set bit in a memory region * @addr: The address to base the search on - * @offset: The bitnumber to start searching at * @size: The bitmap size in bits + * @offset: The bitnumber to start searching at * * Returns the bit number for the next set bit * If no bits are set, returns @size. @@ -41,7 +43,7 @@ unsigned long find_next_bit(const unsigned long *addr, un= signed long size, return val ? __ffs(val) : size; } =20 - return _find_next_bit(addr, NULL, size, offset, 0UL, 0); + return _find_next_bit(addr, size, offset); } #endif =20 @@ -50,8 +52,8 @@ unsigned long find_next_bit(const unsigned long *addr, un= signed long size, * find_next_and_bit - find the next set bit in both memory regions * @addr1: The first address to base the search on * @addr2: The second address to base the search on - * @offset: The bitnumber to start searching at * @size: The bitmap size in bits + * @offset: The bitnumber to start searching at * * Returns the bit number for the next set bit * If no bits are set, returns @size. @@ -71,7 +73,7 @@ unsigned long find_next_and_bit(const unsigned long *addr= 1, return val ? __ffs(val) : size; } =20 - return _find_next_bit(addr1, addr2, size, offset, 0UL, 0); + return _find_next_and_bit(addr1, addr2, size, offset); } #endif =20 @@ -79,8 +81,8 @@ unsigned long find_next_and_bit(const unsigned long *addr= 1, /** * find_next_zero_bit - find the next cleared bit in a memory region * @addr: The address to base the search on - * @offset: The bitnumber to start searching at * @size: The bitmap size in bits + * @offset: The bitnumber to start searching at * * Returns the bit number of the next zero bit * If no bits are zero, returns @size. @@ -99,7 +101,7 @@ unsigned long find_next_zero_bit(const unsigned long *ad= dr, unsigned long size, return val =3D=3D ~0UL ? size : ffz(val); } =20 - return _find_next_bit(addr, NULL, size, offset, ~0UL, 0); + return _find_next_zero_bit(addr, size, offset); } #endif =20 @@ -172,43 +174,4 @@ unsigned long find_first_zero_bit(const unsigned long = *addr, unsigned long size) } #endif =20 -#ifndef find_last_bit -/** - * find_last_bit - find the last set bit in a memory region - * @addr: The address to start the search at - * @size: The number of bits to search - * - * Returns the bit number of the last set bit, or size. - */ -static inline -unsigned long find_last_bit(const unsigned long *addr, unsigned long size) -{ - if (small_const_nbits(size)) { - unsigned long val =3D *addr & GENMASK(size - 1, 0); - - return val ? __fls(val) : size; - } - - return _find_last_bit(addr, size); -} -#endif - -/** - * find_next_clump8 - find next 8-bit clump with set bits in a memory regi= on - * @clump: location to store copy of found clump - * @addr: address to base the search on - * @size: bitmap size in number of bits - * @offset: bit offset at which to start searching - * - * Returns the bit offset for the next set clump; the found clump value is - * copied to the location pointed by @clump. If no bits are set, returns @= size. - */ -extern unsigned long find_next_clump8(unsigned long *clump, - const unsigned long *addr, - unsigned long size, unsigned long offset); - -#define find_first_clump8(clump, bits, size) \ - find_next_clump8((clump), (bits), (size), 0) - - #endif /*__LINUX_FIND_H_ */ diff --git a/tools/lib/find_bit.c b/tools/lib/find_bit.c index ba4b8d94e004..6a3dc167d30e 100644 --- a/tools/lib/find_bit.c +++ b/tools/lib/find_bit.c @@ -18,66 +18,54 @@ #include #include =20 -#if !defined(find_next_bit) || !defined(find_next_zero_bit) || \ - !defined(find_next_and_bit) - /* - * This is a common helper function for find_next_bit, find_next_zero_bit,= and - * find_next_and_bit. The differences are: - * - The "invert" argument, which is XORed with each fetched word before - * searching it for one bits. - * - The optional "addr2", which is anded with "addr1" if present. + * Common helper for find_bit() function family + * @FETCH: The expression that fetches and pre-processes each word of bitm= ap(s) + * @MUNGE: The expression that post-processes a word containing found bit = (may be empty) + * @size: The bitmap size in bits */ -unsigned long _find_next_bit(const unsigned long *addr1, - const unsigned long *addr2, unsigned long nbits, - unsigned long start, unsigned long invert, unsigned long le) -{ - unsigned long tmp, mask; - (void) le; - - if (unlikely(start >=3D nbits)) - return nbits; - - tmp =3D addr1[start / BITS_PER_LONG]; - if (addr2) - tmp &=3D addr2[start / BITS_PER_LONG]; - tmp ^=3D invert; - - /* Handle 1st word. */ - mask =3D BITMAP_FIRST_WORD_MASK(start); - - /* - * Due to the lack of swab() in tools, and the fact that it doesn't - * need little-endian support, just comment it out - */ -#if (0) - if (le) - mask =3D swab(mask); -#endif - - tmp &=3D mask; +#define FIND_FIRST_BIT(FETCH, MUNGE, size) \ +({ \ + unsigned long idx, val, sz =3D (size); \ + \ + for (idx =3D 0; idx * BITS_PER_LONG < sz; idx++) { \ + val =3D (FETCH); \ + if (val) { \ + sz =3D min(idx * BITS_PER_LONG + __ffs(MUNGE(val)), sz); \ + break; \ + } \ + } \ + \ + sz; \ +}) =20 - start =3D round_down(start, BITS_PER_LONG); - - while (!tmp) { - start +=3D BITS_PER_LONG; - if (start >=3D nbits) - return nbits; - - tmp =3D addr1[start / BITS_PER_LONG]; - if (addr2) - tmp &=3D addr2[start / BITS_PER_LONG]; - tmp ^=3D invert; - } - -#if (0) - if (le) - tmp =3D swab(tmp); -#endif - - return min(start + __ffs(tmp), nbits); -} -#endif +/* + * Common helper for find_next_bit() function family + * @FETCH: The expression that fetches and pre-processes each word of bitm= ap(s) + * @MUNGE: The expression that post-processes a word containing found bit = (may be empty) + * @size: The bitmap size in bits + * @start: The bitnumber to start searching at + */ +#define FIND_NEXT_BIT(FETCH, MUNGE, size, start) \ +({ \ + unsigned long mask, idx, tmp, sz =3D (size), __start =3D (start); \ + \ + if (unlikely(__start >=3D sz)) \ + goto out; \ + \ + mask =3D MUNGE(BITMAP_FIRST_WORD_MASK(__start)); \ + idx =3D __start / BITS_PER_LONG; \ + \ + for (tmp =3D (FETCH) & mask; !tmp; tmp =3D (FETCH)) { \ + if ((idx + 1) * BITS_PER_LONG >=3D sz) \ + goto out; \ + idx++; \ + } \ + \ + sz =3D min(idx * BITS_PER_LONG + __ffs(MUNGE(tmp)), sz); \ +out: \ + sz; \ +}) =20 #ifndef find_first_bit /* @@ -85,14 +73,7 @@ unsigned long _find_next_bit(const unsigned long *addr1, */ unsigned long _find_first_bit(const unsigned long *addr, unsigned long siz= e) { - unsigned long idx; - - for (idx =3D 0; idx * BITS_PER_LONG < size; idx++) { - if (addr[idx]) - return min(idx * BITS_PER_LONG + __ffs(addr[idx]), size); - } - - return size; + return FIND_FIRST_BIT(addr[idx], /* nop */, size); } #endif =20 @@ -104,15 +85,7 @@ unsigned long _find_first_and_bit(const unsigned long *= addr1, const unsigned long *addr2, unsigned long size) { - unsigned long idx, val; - - for (idx =3D 0; idx * BITS_PER_LONG < size; idx++) { - val =3D addr1[idx] & addr2[idx]; - if (val) - return min(idx * BITS_PER_LONG + __ffs(val), size); - } - - return size; + return FIND_FIRST_BIT(addr1[idx] & addr2[idx], /* nop */, size); } #endif =20 @@ -122,13 +95,29 @@ unsigned long _find_first_and_bit(const unsigned long = *addr1, */ unsigned long _find_first_zero_bit(const unsigned long *addr, unsigned lon= g size) { - unsigned long idx; + return FIND_FIRST_BIT(~addr[idx], /* nop */, size); +} +#endif =20 - for (idx =3D 0; idx * BITS_PER_LONG < size; idx++) { - if (addr[idx] !=3D ~0UL) - return min(idx * BITS_PER_LONG + ffz(addr[idx]), size); - } +#ifndef find_next_bit +unsigned long _find_next_bit(const unsigned long *addr, unsigned long nbit= s, unsigned long start) +{ + return FIND_NEXT_BIT(addr[idx], /* nop */, nbits, start); +} +#endif =20 - return size; +#ifndef find_next_and_bit +unsigned long _find_next_and_bit(const unsigned long *addr1, const unsigne= d long *addr2, + unsigned long nbits, unsigned long start) +{ + return FIND_NEXT_BIT(addr1[idx] & addr2[idx], /* nop */, nbits, start); +} +#endif + +#ifndef find_next_zero_bit +unsigned long _find_next_zero_bit(const unsigned long *addr, unsigned long= nbits, + unsigned long start) +{ + return FIND_NEXT_BIT(~addr[idx], /* nop */, nbits, start); } #endif --=20 2.34.1