From nobody Fri Apr 3 02:23:13 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 A04B9ECAAD3 for ; Sun, 18 Sep 2022 03:07:37 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S229586AbiIRDHe (ORCPT ); Sat, 17 Sep 2022 23:07:34 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:51496 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S229447AbiIRDHW (ORCPT ); Sat, 17 Sep 2022 23:07:22 -0400 Received: from mail-qk1-x72a.google.com (mail-qk1-x72a.google.com [IPv6:2607:f8b0:4864:20::72a]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id E06BA29827 for ; Sat, 17 Sep 2022 20:07:20 -0700 (PDT) Received: by mail-qk1-x72a.google.com with SMTP id d15so18430446qka.9 for ; Sat, 17 Sep 2022 20:07:20 -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=hIH+cYLLu5nISquJxX2Y2BfHZrCs6NlFVQp9n+J7Pgc=; b=fPKERsemDqrcstzHiRkssOFxyuyOWKPWXycQixi0LQTkrcLpHXWh0n/+WGRK/CLiA3 /s0MWj48h6ZTtNSH7dU4Kb9hn2xHyM66/KhzqOgMQw9XM4GSYm3Xqv2wovwFdTJZmCj9 Rkba5PLj+irLjvP+bUWO+787NSKs9jxHmYdmEbePdg+zR7yfkO8vSxIEHyb1bTg6xc0A TVRhV9ERIBm4Aeadfuhcpaji5OYWOe1R7eynSDg1bQ93hrQm74JZ0hvMgKzg0IawR+dC AjnfjzE8Y3/WdUJ2tIRSFIH+wGt1uwwliOCg1E2ihwBhJ99aYaBFcvaQSWvhVuh9bxmw eF3w== 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=hIH+cYLLu5nISquJxX2Y2BfHZrCs6NlFVQp9n+J7Pgc=; b=vmM086yK6XpEGJqzEC7v41wHBLHMUqJ6APLTujf6ZoXKn0hpRHGy4TrnnoliMfoO31 TCW6pwCjQNhESgi7KVhV04DzywPY8xiDLX8HTs8GaZeeoDik8qMAFp0b+4xbbqiBc0fy BWhULwF1xL9IyMc4Q1epqsLOQy/j/IR37cdcIZJhBUmQVbpH75Y52zZas5JBJYGOYvwV wMdtvlN1CpiEDyaOjasoFwGA1u8dP+7UBKF6/pBjz51/9Y6+B7oS4Lv5ydRuiNZhSR05 SZ4NQi0mXIRC/zbLugBEpGfSihN5gw1KplvIn8bwuhbucjDE8CsvvQXwwm3iK4ISxWR/ QzKA== X-Gm-Message-State: ACrzQf2k/P59dujBnlLt7jKQZm07Pe49GLWlw1YrvmiDfwRqvpFFV+jq 88fwP1SLgLIK4E/opqKSkk/SZEurIeg= X-Google-Smtp-Source: AMsMyM7EYcJ7TQqwfb69HXS3kYjkopMU3K7dFgaYkrMBgx2XfKEulJbaiBzu3vSxAZopiPdewuwJaw== X-Received: by 2002:a37:c09:0:b0:6cb:d61d:22b8 with SMTP id 9-20020a370c09000000b006cbd61d22b8mr9115535qkm.130.1663470439786; Sat, 17 Sep 2022 20:07:19 -0700 (PDT) Received: from localhost ([2601:4c1:c100:2270:a495:2224:867e:566a]) by smtp.gmail.com with ESMTPSA id a12-20020a05620a16cc00b006a5d2eb58b2sm8844806qkn.33.2022.09.17.20.07.19 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Sat, 17 Sep 2022 20:07:19 -0700 (PDT) From: Yury Norov To: linux-kernel@vger.kernel.org, Alexander Lobakin , Andy Shevchenko , Arnd Bergmann , David Gow , Eric Dumazet , Isabella Basso , Kees Cook , Keith Busch , Kumar Kartikeya Dwivedi , Marco Elver , Mark Rutland , Rasmus Villemoes , Steven Rostedt , =?UTF-8?q?Toke=20H=C3=B8iland-J=C3=B8rgensen?= , Valentin Schneider Cc: Yury Norov Subject: [PATCH v3 1/6] lib/bitmap: don't call __bitmap_weight() in kernel code Date: Sat, 17 Sep 2022 20:07:11 -0700 Message-Id: <20220918030716.1252285-2-yury.norov@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20220918030716.1252285-1-yury.norov@gmail.com> References: <20220918030716.1252285-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" __bitmap_weight() is not to be used directly in the kernel code because it's a helper for bitmap_weight(). Switch everything to bitmap_weight(). Signed-off-by: Yury Norov --- fs/ntfs3/bitmap.c | 4 ++-- lib/bitmap.c | 2 +- 2 files changed, 3 insertions(+), 3 deletions(-) diff --git a/fs/ntfs3/bitmap.c b/fs/ntfs3/bitmap.c index 5d44ceac855b..e92bbd754365 100644 --- a/fs/ntfs3/bitmap.c +++ b/fs/ntfs3/bitmap.c @@ -560,7 +560,7 @@ static int wnd_rescan(struct wnd_bitmap *wnd) =20 buf =3D (ulong *)bh->b_data; =20 - used =3D __bitmap_weight(buf, wbits); + used =3D bitmap_weight(buf, wbits); if (used < wbits) { frb =3D wbits - used; wnd->free_bits[iw] =3D frb; @@ -1364,7 +1364,7 @@ int wnd_extend(struct wnd_bitmap *wnd, size_t new_bit= s) buf =3D (ulong *)bh->b_data; =20 __bitmap_clear(buf, b0, blocksize * 8 - b0); - frb =3D wbits - __bitmap_weight(buf, wbits); + frb =3D wbits - bitmap_weight(buf, wbits); wnd->total_zeroes +=3D frb - wnd->free_bits[iw]; wnd->free_bits[iw] =3D frb; =20 diff --git a/lib/bitmap.c b/lib/bitmap.c index 488e6c3e5acc..d56e275db73e 100644 --- a/lib/bitmap.c +++ b/lib/bitmap.c @@ -953,7 +953,7 @@ static int bitmap_pos_to_ord(const unsigned long *buf, = unsigned int pos, unsigne if (pos >=3D nbits || !test_bit(pos, buf)) return -1; =20 - return __bitmap_weight(buf, pos); + return bitmap_weight(buf, pos); } =20 /** --=20 2.34.1 From nobody Fri Apr 3 02:23:13 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 4F017ECAAA1 for ; Sun, 18 Sep 2022 03:07:42 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S229613AbiIRDHi (ORCPT ); Sat, 17 Sep 2022 23:07:38 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:51502 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S229541AbiIRDHX (ORCPT ); Sat, 17 Sep 2022 23:07:23 -0400 Received: from mail-qk1-x736.google.com (mail-qk1-x736.google.com [IPv6:2607:f8b0:4864:20::736]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 103352982D for ; Sat, 17 Sep 2022 20:07:21 -0700 (PDT) Received: by mail-qk1-x736.google.com with SMTP id h28so18469807qka.0 for ; Sat, 17 Sep 2022 20:07:21 -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=28qxGuS3wBP5HWmbq1UhK0+iKUABPY0/24xMCB/mxU0=; b=jkN6o2n7ceG76VrpNvl/UfZg0xFsLNNx8bitngnNrLejsyCFIAfL54F5Li4umMFyQl jKe2CyNbf8y0iyAui0VPsF0gJuuzvuPVdG+YhE71ETGda8TagPQRWKqWuPAhX+Al4XTT yfCmqmZSOdQVShOG5meIXXhVGlpbix8+yWwJQdB4gxYPSkIYg6Fsyu6ThnE+h94Ys7H8 Ww/UKngs81LGPtNPtbUdU49JDxRnDuktxCNiLvBW7GMorwGQu46QTEhyCSFAO9Jo2rt1 3AXWUC6UgPpPpkySQivL7/sdgWK97eoFMmfjBoSFKOb+rAFJYiT/JS0tHe31UCat+Jio +lIQ== 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=28qxGuS3wBP5HWmbq1UhK0+iKUABPY0/24xMCB/mxU0=; b=WYYXJCoIv17dg/QAhGr3c/eL7HjVnWTW78hzt+1C7tKgiKgBFAKJRUtsTP8LYS0Hw6 oNolPoVVmuRhotRWwol6KrKZ/6u9ZyGwMVIa4uUHvhzyhJCc7AKA+aLTT5UwbITWsFp8 UU/1uFXs63Du2SVtTbjsl1S8zd7e5C9YNaijiXSMsX6XYhgWh45iX1C+ZsYCDeiiIRqL mZvhFeVMXSaVtmeFFIjpr1EPsTmJ/OD49IVujJhV1TQjaeFfH81OS0VZbts+1PSMibWD jWZpEeKHEdfKm60f75n1t/HYm9VtvXI+fXwuWyKBt5QeBvyG7/E4S5Nl6IAMCbuBxuph Ts/Q== X-Gm-Message-State: ACrzQf2+vWBZggIb0cpx9D9rNGMMffi/jQfMEwv5P2j309QhsPn1mEr+ +ZrGRBRySo016v1aSjwxW5vK9W5yIj0= X-Google-Smtp-Source: AMsMyM4K7Fr1jwBbPPlQnUvqP0q7cqiBR73NcNsSpB9SV8rGTB2SR7kwbVIBn4ZjXP8dQ/p5sFkkJQ== X-Received: by 2002:a05:620a:1410:b0:6ce:9946:8469 with SMTP id d16-20020a05620a141000b006ce99468469mr9137829qkj.654.1663470440751; Sat, 17 Sep 2022 20:07:20 -0700 (PDT) Received: from localhost ([2601:4c1:c100:2270:a495:2224:867e:566a]) by smtp.gmail.com with ESMTPSA id l20-20020a05620a28d400b006ce1bfbd603sm9941918qkp.124.2022.09.17.20.07.20 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Sat, 17 Sep 2022 20:07:20 -0700 (PDT) From: Yury Norov To: linux-kernel@vger.kernel.org, Alexander Lobakin , Andy Shevchenko , Arnd Bergmann , David Gow , Eric Dumazet , Isabella Basso , Kees Cook , Keith Busch , Kumar Kartikeya Dwivedi , Marco Elver , Mark Rutland , Rasmus Villemoes , Steven Rostedt , =?UTF-8?q?Toke=20H=C3=B8iland-J=C3=B8rgensen?= , Valentin Schneider Cc: Yury Norov Subject: [PATCH v3 2/6] lib/bitmap: add bitmap_weight_and() Date: Sat, 17 Sep 2022 20:07:12 -0700 Message-Id: <20220918030716.1252285-3-yury.norov@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20220918030716.1252285-1-yury.norov@gmail.com> References: <20220918030716.1252285-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" The function calculates Hamming weight of (bitmap1 & bitmap2). Now we have to do like this: tmp =3D bitmap_alloc(nbits); bitmap_and(tmp, map1, map2, nbits); weight =3D bitmap_weight(tmp, nbits); bitmap_free(tmp); This requires additional memory, adds pressure on alloc subsystem, and way less cache-friendly than just: weight =3D bitmap_weight_and(map1, map2, nbits); The following patches apply it for cpumask functions. Signed-off-by: Yury Norov --- include/linux/bitmap.h | 12 ++++++++++++ include/linux/cpumask.h | 11 +++++++++++ lib/bitmap.c | 30 +++++++++++++++++++++--------- 3 files changed, 44 insertions(+), 9 deletions(-) diff --git a/include/linux/bitmap.h b/include/linux/bitmap.h index f65410a49fda..b2aef45af0db 100644 --- a/include/linux/bitmap.h +++ b/include/linux/bitmap.h @@ -51,6 +51,7 @@ struct device; * bitmap_empty(src, nbits) Are all bits zero in *src? * bitmap_full(src, nbits) Are all bits set in *src? * bitmap_weight(src, nbits) Hamming Weight: number set= bits + * bitmap_weight_and(src1, src2, nbits) Hamming Weight of and'ed b= itmap * bitmap_set(dst, pos, nbits) Set specified bit area * bitmap_clear(dst, pos, nbits) Clear specified bit area * bitmap_find_next_zero_area(buf, len, pos, n, mask) Find bit free area @@ -164,6 +165,8 @@ bool __bitmap_intersects(const unsigned long *bitmap1, bool __bitmap_subset(const unsigned long *bitmap1, const unsigned long *bitmap2, unsigned int nbits); unsigned int __bitmap_weight(const unsigned long *bitmap, unsigned int nbi= ts); +unsigned int __bitmap_weight_and(const unsigned long *bitmap1, + const unsigned long *bitmap2, unsigned int nbits); void __bitmap_set(unsigned long *map, unsigned int start, int len); void __bitmap_clear(unsigned long *map, unsigned int start, int len); =20 @@ -439,6 +442,15 @@ unsigned int bitmap_weight(const unsigned long *src, u= nsigned int nbits) return __bitmap_weight(src, nbits); } =20 +static __always_inline +unsigned long bitmap_weight_and(const unsigned long *src1, + const unsigned long *src2, unsigned int nbits) +{ + if (small_const_nbits(nbits)) + return hweight_long(*src1 & *src2 & BITMAP_LAST_WORD_MASK(nbits)); + return __bitmap_weight_and(src1, src2, nbits); +} + static __always_inline void bitmap_set(unsigned long *map, unsigned int st= art, unsigned int nbits) { diff --git a/include/linux/cpumask.h b/include/linux/cpumask.h index e8ad12b5b9d2..31bf08c786e3 100644 --- a/include/linux/cpumask.h +++ b/include/linux/cpumask.h @@ -586,6 +586,17 @@ static inline unsigned int cpumask_weight(const struct= cpumask *srcp) return bitmap_weight(cpumask_bits(srcp), nr_cpumask_bits); } =20 +/** + * cpumask_weight_and - Count of bits in (*srcp1 & *srcp2) + * @srcp1: the cpumask to count bits (< nr_cpu_ids) in. + * @srcp2: the cpumask to count bits (< nr_cpu_ids) in. + */ +static inline unsigned int cpumask_weight_and(const struct cpumask *srcp1, + const struct cpumask *srcp2) +{ + return bitmap_weight_and(cpumask_bits(srcp1), cpumask_bits(srcp2), nr_cpu= mask_bits); +} + /** * cpumask_shift_right - *dstp =3D *srcp >> n * @dstp: the cpumask result diff --git a/lib/bitmap.c b/lib/bitmap.c index d56e275db73e..3fc2e338ec30 100644 --- a/lib/bitmap.c +++ b/lib/bitmap.c @@ -333,20 +333,32 @@ bool __bitmap_subset(const unsigned long *bitmap1, } EXPORT_SYMBOL(__bitmap_subset); =20 +#define BITMAP_WEIGHT(FETCH, bits) \ +({ \ + unsigned int __bits =3D (bits), idx, w =3D 0; \ + \ + for (idx =3D 0; idx < __bits / BITS_PER_LONG; idx++) \ + w +=3D hweight_long(FETCH); \ + \ + if (__bits % BITS_PER_LONG) \ + w +=3D hweight_long((FETCH) & BITMAP_LAST_WORD_MASK(__bits)); \ + \ + w; \ +}) + unsigned int __bitmap_weight(const unsigned long *bitmap, unsigned int bit= s) { - unsigned int k, lim =3D bits/BITS_PER_LONG, w =3D 0; - - for (k =3D 0; k < lim; k++) - w +=3D hweight_long(bitmap[k]); - - if (bits % BITS_PER_LONG) - w +=3D hweight_long(bitmap[k] & BITMAP_LAST_WORD_MASK(bits)); - - return w; + return BITMAP_WEIGHT(bitmap[idx], bits); } EXPORT_SYMBOL(__bitmap_weight); =20 +unsigned int __bitmap_weight_and(const unsigned long *bitmap1, + const unsigned long *bitmap2, unsigned int bits) +{ + return BITMAP_WEIGHT(bitmap1[idx] & bitmap2[idx], bits); +} +EXPORT_SYMBOL(__bitmap_weight_and); + void __bitmap_set(unsigned long *map, unsigned int start, int len) { unsigned long *p =3D map + BIT_WORD(start); --=20 2.34.1 From nobody Fri Apr 3 02:23:13 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 F3AC7ECAAD3 for ; Sun, 18 Sep 2022 03:07:56 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S229483AbiIRDHy (ORCPT ); Sat, 17 Sep 2022 23:07:54 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:51508 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S229548AbiIRDHY (ORCPT ); Sat, 17 Sep 2022 23:07:24 -0400 Received: from mail-qv1-xf31.google.com (mail-qv1-xf31.google.com [IPv6:2607:f8b0:4864:20::f31]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id C6EF327159 for ; Sat, 17 Sep 2022 20:07:22 -0700 (PDT) Received: by mail-qv1-xf31.google.com with SMTP id s13so19545248qvq.10 for ; Sat, 17 Sep 2022 20:07:22 -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=LgocecjigwU3Agdjb8TY62Q6ibOCi0iPSWcnW4GUNJI=; b=BJeCZHOcdO6zOBUNdIxK5z8bIM1M8Gyv2hCjpc/o95fdn8kVtR4ype/fy3q/91YWDo //M6Z2kV6swHFlHTa8GX+sAVHlI5Nu3HHvMfSP+qvXUCPhjAHo6v1DPa2Ogw+FYQxMy8 CQTuEj3VFXsSAUxYOfRElmOxbKIdctzLuGAKo/4fp6gIpmbCed8b3L5WEafJPUFwWldz 4xphSCxGiWE5FcalqxvWJCDT/hVJDD6tlLfNHhxhjkoIWD/u1vtObyTS5LaFLx8R11bJ NxePgECU7eqqNDE3TYScGblkGBDP1QKM97RKaejDj20J1agJrnQbiGGx91HWW5dOX7Xy lWhw== 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=LgocecjigwU3Agdjb8TY62Q6ibOCi0iPSWcnW4GUNJI=; b=cPJ/hgKXi9wPD0dFnFgFeoDSrvtYuV0w/+zz8gWh4v4udSWZW4cbtCCsTqr9AX9NeU JQ5Wppz7r1CUgSUH3XpvfqwrrJ1qtK3ztGsh/d3VWzzNMWfyAl/XabejAVBQ7RirkaOM UrSqDovl/2s1OqfIcqlPIVNXGsWmpgrruJC0gTh7FlY9UfrTEV+QVq2KnciUnGpSfLzg OUB9m/63B0sn6fdgpKdcqDAI6LOBi3+fKTR8z2jLa9nyYOyFTJ5YRwUseuCmLP4u1ksc 8zJyHjyQATkNchn82jEiDou0AnNMNsnBPBfMEH8mSR0E4AFzgUeftUH7h13ynAQEVi5z lXIQ== X-Gm-Message-State: ACrzQf3v6lgIm+z5vfz4E1908/P5SiN+uMiuInR2iQL4MDz5CSRCvM/o amVoM4oIpKd8/dtztIkH+vBi451jhto= X-Google-Smtp-Source: AMsMyM6ZvR5uibZiHzw8/3Ayi1vOpODJ2r5OJE4qvSBCQn+Q7uunbB95pLT3hZyN5gmttiseOshRuQ== X-Received: by 2002:ad4:5961:0:b0:4ad:2406:e014 with SMTP id eq1-20020ad45961000000b004ad2406e014mr4097608qvb.119.1663470441720; Sat, 17 Sep 2022 20:07:21 -0700 (PDT) Received: from localhost ([2601:4c1:c100:2270:a495:2224:867e:566a]) by smtp.gmail.com with ESMTPSA id v15-20020a05620a0f0f00b0069fe1dfbeffsm9739734qkl.92.2022.09.17.20.07.21 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Sat, 17 Sep 2022 20:07:21 -0700 (PDT) From: Yury Norov To: linux-kernel@vger.kernel.org, Alexander Lobakin , Andy Shevchenko , Arnd Bergmann , David Gow , Eric Dumazet , Isabella Basso , Kees Cook , Keith Busch , Kumar Kartikeya Dwivedi , Marco Elver , Mark Rutland , Rasmus Villemoes , Steven Rostedt , =?UTF-8?q?Toke=20H=C3=B8iland-J=C3=B8rgensen?= , Valentin Schneider Cc: Yury Norov Subject: [PATCH v3 3/6] lib: add find_nth{,_and,_andnot}_bit() Date: Sat, 17 Sep 2022 20:07:13 -0700 Message-Id: <20220918030716.1252285-4-yury.norov@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20220918030716.1252285-1-yury.norov@gmail.com> References: <20220918030716.1252285-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" Kernel lacks for a function that searches for Nth bit in a bitmap. Usually people do it like this: for_each_set_bit(bit, mask, size) if (n-- =3D=3D 0) return bit; We can do it more efficiently, if we: 1. find a word containing Nth bit, using hweight(); and 2. find the bit, using a helper fns(), that works similarly to __ffs() and ffz(). fns() is implemented as a simple loop. For x86_64, there's PDEP instruction to do that: ret =3D clz(pdep(1 << idx, num)). However, for large bitmaps the most of improvement comes from using hweight(), so I kept fns() simple. New find_nth_bit() is ~70 times faster on x86_64/kvm in find_bit benchmark: find_nth_bit: 7154190 ns, 16411 iterations for_each_bit: 505493126 ns, 16315 iterations With all that, a family of 3 new functions is added, and used where appropriate in the following patches. Signed-off-by: Yury Norov --- Comparing to v2, it adds a path that allows quit earlier if the condition can't be met: for (idx =3D 0; (idx + 1) * BITS_PER_LONG <=3D sz; idx++) {=09 + if (idx * BITS_PER_LONG + nr >=3D sz) + goto out; ... include/linux/bitops.h | 19 ++++++++++ include/linux/find.h | 86 ++++++++++++++++++++++++++++++++++++++++++ lib/find_bit.c | 44 +++++++++++++++++++++ 3 files changed, 149 insertions(+) diff --git a/include/linux/bitops.h b/include/linux/bitops.h index 3b89c64bcfd8..d7dd83fafeba 100644 --- a/include/linux/bitops.h +++ b/include/linux/bitops.h @@ -247,6 +247,25 @@ static inline unsigned long __ffs64(u64 word) return __ffs((unsigned long)word); } =20 +/** + * fns - find N'th set bit in a word + * @word: The word to search + * @n: Bit to find + */ +static inline unsigned long fns(unsigned long word, unsigned int n) +{ + unsigned int bit; + + while (word) { + bit =3D __ffs(word); + if (n-- =3D=3D 0) + return bit; + __clear_bit(bit, &word); + } + + return BITS_PER_LONG; +} + /** * assign_bit - Assign value to a bit in memory * @nr: the bit to set diff --git a/include/linux/find.h b/include/linux/find.h index dead6f53a97b..b100944daba0 100644 --- a/include/linux/find.h +++ b/include/linux/find.h @@ -15,6 +15,11 @@ unsigned long _find_next_and_bit(const unsigned long *ad= dr1, const unsigned long 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); +unsigned long __find_nth_bit(const unsigned long *addr, unsigned long size= , unsigned long n); +unsigned long __find_nth_and_bit(const unsigned long *addr1, const unsigne= d long *addr2, + unsigned long size, unsigned long n); +unsigned long __find_nth_andnot_bit(const unsigned long *addr1, const unsi= gned long *addr2, + unsigned long size, unsigned long n); 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); @@ -136,6 +141,87 @@ unsigned long find_first_bit(const unsigned long *addr= , unsigned long size) } #endif =20 +/** + * find_nth_bit - find N'th set bit in a memory region + * @addr: The address to start the search at + * @size: The maximum number of bits to search + * @n: The number of set bit, which position is needed, counting from 0 + * + * The following is semantically equivalent: + * idx =3D find_nth_bit(addr, size, 0); + * idx =3D find_first_bit(addr, size); + * + * Returns the bit number of the N'th set bit. + * If no such, returns @size. + */ +static inline +unsigned long find_nth_bit(const unsigned long *addr, unsigned long size, = unsigned long n) +{ + if (n >=3D size) + return size; + + if (small_const_nbits(size)) { + unsigned long val =3D *addr & GENMASK(size - 1, 0); + + return val ? fns(val, n) : size; + } + + return __find_nth_bit(addr, size, n); +} + +/** + * find_nth_and_bit - find N'th set bit in 2 memory regions + * @addr1: The 1st address to start the search at + * @addr2: The 2nd address to start the search at + * @size: The maximum number of bits to search + * @n: The number of set bit, which position is needed, counting from 0 + * + * Returns the bit number of the N'th set bit. + * If no such, returns @size. + */ +static inline +unsigned long find_nth_and_bit(const unsigned long *addr1, const unsigned = long *addr2, + unsigned long size, unsigned long n) +{ + if (n >=3D size) + return size; + + if (small_const_nbits(size)) { + unsigned long val =3D *addr1 & *addr2 & GENMASK(size - 1, 0); + + return val ? fns(val, n) : size; + } + + return __find_nth_and_bit(addr1, addr2, size, n); +} + +/** + * find_nth_andnot_bit - find N'th set bit in 2 memory regions, + * flipping bits in 2nd region + * @addr1: The 1st address to start the search at + * @addr2: The 2nd address to start the search at + * @size: The maximum number of bits to search + * @n: The number of set bit, which position is needed, counting from 0 + * + * Returns the bit number of the N'th set bit. + * If no such, returns @size. + */ +static inline +unsigned long find_nth_andnot_bit(const unsigned long *addr1, const unsign= ed long *addr2, + unsigned long size, unsigned long n) +{ + if (n >=3D size) + return size; + + if (small_const_nbits(size)) { + unsigned long val =3D *addr1 & (~*addr2) & GENMASK(size - 1, 0); + + return val ? fns(val, n) : size; + } + + return __find_nth_andnot_bit(addr1, addr2, size, n); +} + #ifndef find_first_and_bit /** * find_first_and_bit - find the first set bit in both memory regions diff --git a/lib/find_bit.c b/lib/find_bit.c index 8707b4ef3e5e..ae2a59b59bfe 100644 --- a/lib/find_bit.c +++ b/lib/find_bit.c @@ -68,6 +68,30 @@ out: \ sz; \ }) =20 +#define FIND_NTH_BIT(FETCH, size, num) \ +({ \ + unsigned long sz =3D (size), nr =3D (num), idx, w, tmp; \ + \ + for (idx =3D 0; (idx + 1) * BITS_PER_LONG <=3D sz; idx++) { \ + if (idx * BITS_PER_LONG + nr >=3D sz) \ + goto out; \ + \ + tmp =3D (FETCH); \ + w =3D hweight_long(tmp); \ + if (w > nr) \ + goto found; \ + \ + nr -=3D w; \ + } \ + \ + if (sz % BITS_PER_LONG) \ + tmp =3D (FETCH) & BITMAP_LAST_WORD_MASK(sz); \ +found: \ + sz =3D min(idx * BITS_PER_LONG + fns(tmp, nr), sz); \ +out: \ + sz; \ +}) + #ifndef find_first_bit /* * Find the first set bit in a memory region. @@ -111,6 +135,26 @@ unsigned long _find_next_bit(const unsigned long *addr= , unsigned long nbits, uns EXPORT_SYMBOL(_find_next_bit); #endif =20 +unsigned long __find_nth_bit(const unsigned long *addr, unsigned long size= , unsigned long n) +{ + return FIND_NTH_BIT(addr[idx], size, n); +} +EXPORT_SYMBOL(__find_nth_bit); + +unsigned long __find_nth_and_bit(const unsigned long *addr1, const unsigne= d long *addr2, + unsigned long size, unsigned long n) +{ + return FIND_NTH_BIT(addr1[idx] & addr2[idx], size, n); +} +EXPORT_SYMBOL(__find_nth_and_bit); + +unsigned long __find_nth_andnot_bit(const unsigned long *addr1, const unsi= gned long *addr2, + unsigned long size, unsigned long n) +{ + return FIND_NTH_BIT(addr1[idx] & ~addr2[idx], size, n); +} +EXPORT_SYMBOL(__find_nth_andnot_bit); + #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) --=20 2.34.1 From nobody Fri Apr 3 02:23:13 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 C5B8FECAAD3 for ; Sun, 18 Sep 2022 03:07:48 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S229596AbiIRDHo (ORCPT ); Sat, 17 Sep 2022 23:07:44 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:51510 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S229552AbiIRDHY (ORCPT ); Sat, 17 Sep 2022 23:07:24 -0400 Received: from mail-qv1-xf2d.google.com (mail-qv1-xf2d.google.com [IPv6:2607:f8b0:4864:20::f2d]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id BFD5029826 for ; Sat, 17 Sep 2022 20:07:23 -0700 (PDT) Received: by mail-qv1-xf2d.google.com with SMTP id m9so19568822qvv.7 for ; Sat, 17 Sep 2022 20:07:23 -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=gCTBhSJCs9AiuXZ3/z9oldmsugRUUzLPVuV6iPHNgs8=; b=XhDaXNRo59ti0TtQTlfbrxgmn5EDvUx7/ssBEaoqZlIAA5rJDS6OODpSgxS5wjc5Ge jj20aIk3+lD2ohD/oaYsEYmKvPYeO2L2PXq41SOvawjTeydWfIiYgFkr2/oTXJ+7/k47 GzxsMkRdSOWDPVgUnKMbyxsQltwMB1oIJ9nCMqiRCmbXxGxhrtVJsTKNvvk4U8mjI4G/ uDOiAAF/TlCZIVFFwtV2OdHFZS444JWj1HPMZQGLk8nC26pCEaJ7EG1/DfnrePjJnkTJ c3ZBRytrIUzAw2BmNjOl4DmCNLtFKH5+9RX1cyX4K7RBXj/eAUizAb3rssdNRyldYHME +YHA== 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=gCTBhSJCs9AiuXZ3/z9oldmsugRUUzLPVuV6iPHNgs8=; b=LLyg7Ds6oHYgSQbM/JyZD4XHY2iGHGdY0hj39ngTkskwYJl46m1TuFbQJ/kgGBd3Oa rxFkZDdhGGQ0ud1ZFN9TIetZt8PJrQFcq6+8egWso/hqqa3zMClxnIeByWOs0wsXNPfx y4jqFnJ5k1TBTRwbK2V7cRDfMTyYGznQt4xcdj8BvX+5K/mHBv9gb2xlmrhLdOudsFNP BlGkDNL5U+0yXjUrBMN4lp+4XNIZ5xvLqgVBFSQkjV+U9NeVVpptB43q60yB2vEhU8aM u1aPbVMKGGNGiQB5cNnXfoUT/lnLPtDNhDlTxz8YdDqttqryZ6NhMUCfpu8l07l4CZpc XAng== X-Gm-Message-State: ACrzQf2tg76NnaFO7iUfvOi5knM2u9nsocv3jRmpxzm/0bCcwNKpCY7o p/J0S1R88r5qsfJuROzfvBr/drF7xtA= X-Google-Smtp-Source: AMsMyM50AOyZ+GPk3Qx9/K6T4BSXcIR/p2CP++G9GaLBUwI+y3oftEIbytQf02XXtQPgSvP3FLCZCw== X-Received: by 2002:a05:6214:2022:b0:4ac:b001:2c75 with SMTP id 2-20020a056214202200b004acb0012c75mr9653900qvf.83.1663470442731; Sat, 17 Sep 2022 20:07:22 -0700 (PDT) Received: from localhost ([2601:4c1:c100:2270:a495:2224:867e:566a]) by smtp.gmail.com with ESMTPSA id p13-20020ac8740d000000b0034454067d24sm7737188qtq.64.2022.09.17.20.07.22 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Sat, 17 Sep 2022 20:07:22 -0700 (PDT) From: Yury Norov To: linux-kernel@vger.kernel.org, Alexander Lobakin , Andy Shevchenko , Arnd Bergmann , David Gow , Eric Dumazet , Isabella Basso , Kees Cook , Keith Busch , Kumar Kartikeya Dwivedi , Marco Elver , Mark Rutland , Rasmus Villemoes , Steven Rostedt , =?UTF-8?q?Toke=20H=C3=B8iland-J=C3=B8rgensen?= , Valentin Schneider Cc: Yury Norov Subject: [PATCH v3 4/6] lib/bitmap: add tests for find_nth_bit() Date: Sat, 17 Sep 2022 20:07:14 -0700 Message-Id: <20220918030716.1252285-5-yury.norov@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20220918030716.1252285-1-yury.norov@gmail.com> References: <20220918030716.1252285-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" Add functional and performance tests for find_nth_bit(). Signed-off-by: Yury Norov --- lib/find_bit_benchmark.c | 18 +++++++++++++++ lib/test_bitmap.c | 47 ++++++++++++++++++++++++++++++++++++++-- 2 files changed, 63 insertions(+), 2 deletions(-) diff --git a/lib/find_bit_benchmark.c b/lib/find_bit_benchmark.c index db904b57d4b8..10754586403b 100644 --- a/lib/find_bit_benchmark.c +++ b/lib/find_bit_benchmark.c @@ -115,6 +115,22 @@ static int __init test_find_last_bit(const void *bitma= p, unsigned long len) return 0; } =20 +static int __init test_find_nth_bit(const unsigned long *bitmap, unsigned = long len) +{ + unsigned long l, n, w =3D bitmap_weight(bitmap, len); + ktime_t time; + + time =3D ktime_get(); + for (n =3D 0; n < w; n++) { + l =3D find_nth_bit(bitmap, len, n); + WARN_ON(l >=3D len); + } + time =3D ktime_get() - time; + pr_err("find_nth_bit: %18llu ns, %6ld iterations\n", time, w); + + return 0; +} + static int __init test_find_next_and_bit(const void *bitmap, const void *bitmap2, unsigned long len) { @@ -142,6 +158,7 @@ static int __init find_bit_test(void) test_find_next_bit(bitmap, BITMAP_LEN); test_find_next_zero_bit(bitmap, BITMAP_LEN); test_find_last_bit(bitmap, BITMAP_LEN); + test_find_nth_bit(bitmap, BITMAP_LEN / 10); =20 /* * test_find_first_bit() may take some time, so @@ -164,6 +181,7 @@ static int __init find_bit_test(void) test_find_next_bit(bitmap, BITMAP_LEN); test_find_next_zero_bit(bitmap, BITMAP_LEN); test_find_last_bit(bitmap, BITMAP_LEN); + test_find_nth_bit(bitmap, BITMAP_LEN); test_find_first_bit(bitmap, BITMAP_LEN); test_find_first_and_bit(bitmap, bitmap2, BITMAP_LEN); test_find_next_and_bit(bitmap, bitmap2, BITMAP_LEN); diff --git a/lib/test_bitmap.c b/lib/test_bitmap.c index 98754ff9fe68..da52dc759c95 100644 --- a/lib/test_bitmap.c +++ b/lib/test_bitmap.c @@ -16,6 +16,8 @@ =20 #include "../tools/testing/selftests/kselftest_module.h" =20 +#define EXP1_IN_BITS (sizeof(exp1) * 8) + KSTM_MODULE_GLOBALS(); =20 static char pbl_buffer[PAGE_SIZE] __initdata; @@ -219,6 +221,47 @@ static void __init test_zero_clear(void) expect_eq_pbl("", bmap, 1024); } =20 +static void __init test_find_nth_bit(void) +{ + unsigned long b, bit, cnt =3D 0; + DECLARE_BITMAP(bmap, 64 * 3); + + bitmap_zero(bmap, 64 * 3); + __set_bit(10, bmap); + __set_bit(20, bmap); + __set_bit(30, bmap); + __set_bit(40, bmap); + __set_bit(50, bmap); + __set_bit(60, bmap); + __set_bit(80, bmap); + __set_bit(123, bmap); + + expect_eq_uint(10, find_nth_bit(bmap, 64 * 3, 0)); + expect_eq_uint(20, find_nth_bit(bmap, 64 * 3, 1)); + expect_eq_uint(30, find_nth_bit(bmap, 64 * 3, 2)); + expect_eq_uint(40, find_nth_bit(bmap, 64 * 3, 3)); + expect_eq_uint(50, find_nth_bit(bmap, 64 * 3, 4)); + expect_eq_uint(60, find_nth_bit(bmap, 64 * 3, 5)); + expect_eq_uint(80, find_nth_bit(bmap, 64 * 3, 6)); + expect_eq_uint(123, find_nth_bit(bmap, 64 * 3, 7)); + expect_eq_uint(64 * 3, find_nth_bit(bmap, 64 * 3, 8)); + + expect_eq_uint(10, find_nth_bit(bmap, 64 * 3 - 1, 0)); + expect_eq_uint(20, find_nth_bit(bmap, 64 * 3 - 1, 1)); + expect_eq_uint(30, find_nth_bit(bmap, 64 * 3 - 1, 2)); + expect_eq_uint(40, find_nth_bit(bmap, 64 * 3 - 1, 3)); + expect_eq_uint(50, find_nth_bit(bmap, 64 * 3 - 1, 4)); + expect_eq_uint(60, find_nth_bit(bmap, 64 * 3 - 1, 5)); + expect_eq_uint(80, find_nth_bit(bmap, 64 * 3 - 1, 6)); + expect_eq_uint(123, find_nth_bit(bmap, 64 * 3 - 1, 7)); + expect_eq_uint(64 * 3 - 1, find_nth_bit(bmap, 64 * 3 - 1, 8)); + + for_each_set_bit(bit, exp1, EXP1_IN_BITS) { + b =3D find_nth_bit(exp1, EXP1_IN_BITS, cnt++); + expect_eq_uint(b, bit); + } +} + static void __init test_fill_set(void) { DECLARE_BITMAP(bmap, 1024); @@ -557,8 +600,6 @@ static void __init test_bitmap_parse(void) } } =20 -#define EXP1_IN_BITS (sizeof(exp1) * 8) - static void __init test_bitmap_arr32(void) { unsigned int nbits, next_bit; @@ -952,6 +993,8 @@ static void __init selftest(void) test_bitmap_cut(); test_bitmap_print_buf(); test_bitmap_const_eval(); + + test_find_nth_bit(); } =20 KSTM_MODULE_LOADERS(test_bitmap); --=20 2.34.1 From nobody Fri Apr 3 02:23:13 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 5E3CFECAAD3 for ; Sun, 18 Sep 2022 03:08:03 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S229650AbiIRDH7 (ORCPT ); Sat, 17 Sep 2022 23:07:59 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:51530 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S229556AbiIRDHZ (ORCPT ); Sat, 17 Sep 2022 23:07:25 -0400 Received: from mail-qt1-x829.google.com (mail-qt1-x829.google.com [IPv6:2607:f8b0:4864:20::829]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id ABECC29827 for ; Sat, 17 Sep 2022 20:07:24 -0700 (PDT) Received: by mail-qt1-x829.google.com with SMTP id w2so14964665qtv.9 for ; Sat, 17 Sep 2022 20:07:24 -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=VgTcXwGZrpzBbQzsthzQYcLd10lXthgvNsdCg7qOn24=; b=noMRXT/IG3xK+9Trj/o5NbybSsqx1IUB3gQoufMRjY7nf9bo/prXXJ7e60VGmSa+ON HNPufmT1VVr2TRVp0tqUgoxaUATNOrkBp5FK3T/9Tv74S563UNPUokqABra+Jv9+UJTs F6OfQV0PY25UA8ATuMPOnskwCdlpukHovIiHGSqIxAAmyNy0lLbU9TJnRJMu5Cv9wAbp xbM9+G749ztOL2FUnSmVIRcjFcn1tm3XoOZ3pN6KcC1vNOHsk5TeDICesw/QkELrRSSF YXvD9z6gwkERexp/GyhF7j6tNGwbeHCH8NirjSGgErLKWSSH1TLVt7k7ngb+VImgokiA AHnA== 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=VgTcXwGZrpzBbQzsthzQYcLd10lXthgvNsdCg7qOn24=; b=bhxhLq52aKC4+2Bqc0d0zn8uNt3udH0WIqIiUb+h7KgHhaBv7aivQvuBTCkGjZ5nFj efXSkGLE6Sc5WOi/YnhFCi6iTSE7ZQVv46wxIxSBth/M6WWMt/5JTN8l/C+fpHQc2uYE rEMfYJitkNbK+/YA/q4CjqNCzj4hhoqdlSIImDQwj4DfOw/OcnYyt6BIWDtoFHPxpwby vrxTJr8nOGm01bZZ5VKH8RbhUwKbR3zg1YXhS8AL6mT56ewE4fhbzvb9Jus9VxIX9Jep qRNSK3jtJplPrJLk0NWQMMIO0pXpOkHTr43Gfrg8Aee+/AzsRKnYWi21KQa1qxqm3lxf M2kw== X-Gm-Message-State: ACrzQf3Ac/U7cij3iGcWxIf2fsBi/Km1dL4vgZOgs20DA5FnkXydlzeg QY1Hgb9djdc0cvToQx38GjbL+YcxBs4= X-Google-Smtp-Source: AMsMyM71a5PlRJYT6IDljqkK2nI5OCN0aQ3SXq0eRC6hcPn4eo14erIjg7ktHEsE/mIfEdy8/11SoA== X-Received: by 2002:ac8:7dc6:0:b0:35c:c9b1:9f98 with SMTP id c6-20020ac87dc6000000b0035cc9b19f98mr10466823qte.170.1663470443652; Sat, 17 Sep 2022 20:07:23 -0700 (PDT) Received: from localhost ([2601:4c1:c100:2270:a495:2224:867e:566a]) by smtp.gmail.com with ESMTPSA id s3-20020a05620a29c300b006bb8b5b79efsm4993612qkp.129.2022.09.17.20.07.23 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Sat, 17 Sep 2022 20:07:23 -0700 (PDT) From: Yury Norov To: linux-kernel@vger.kernel.org, Alexander Lobakin , Andy Shevchenko , Arnd Bergmann , David Gow , Eric Dumazet , Isabella Basso , Kees Cook , Keith Busch , Kumar Kartikeya Dwivedi , Marco Elver , Mark Rutland , Rasmus Villemoes , Steven Rostedt , =?UTF-8?q?Toke=20H=C3=B8iland-J=C3=B8rgensen?= , Valentin Schneider Cc: Yury Norov Subject: [PATCH v3 5/6] lib/bitmap: remove bitmap_ord_to_pos Date: Sat, 17 Sep 2022 20:07:15 -0700 Message-Id: <20220918030716.1252285-6-yury.norov@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20220918030716.1252285-1-yury.norov@gmail.com> References: <20220918030716.1252285-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 find_nth_bit(), we can drop bitmap_ord_to_pos(). Signed-off-by: Yury Norov --- include/linux/bitmap.h | 1 - include/linux/nodemask.h | 3 +-- lib/bitmap.c | 36 +++--------------------------------- 3 files changed, 4 insertions(+), 36 deletions(-) diff --git a/include/linux/bitmap.h b/include/linux/bitmap.h index b2aef45af0db..7d6d73b78147 100644 --- a/include/linux/bitmap.h +++ b/include/linux/bitmap.h @@ -225,7 +225,6 @@ void bitmap_copy_le(unsigned long *dst, const unsigned = long *src, unsigned int n #else #define bitmap_copy_le bitmap_copy #endif -unsigned int bitmap_ord_to_pos(const unsigned long *bitmap, unsigned int o= rd, unsigned int nbits); int bitmap_print_to_pagebuf(bool list, char *buf, const unsigned long *maskp, int nmaskbits); =20 diff --git a/include/linux/nodemask.h b/include/linux/nodemask.h index 4b71a96190a8..0c45fb066caa 100644 --- a/include/linux/nodemask.h +++ b/include/linux/nodemask.h @@ -508,8 +508,7 @@ static inline int node_random(const nodemask_t *maskp) =20 w =3D nodes_weight(*maskp); if (w) - bit =3D bitmap_ord_to_pos(maskp->bits, - get_random_int() % w, MAX_NUMNODES); + bit =3D find_nth_bit(maskp->bits, MAX_NUMNODES, get_random_int() % w); return bit; #else return 0; diff --git a/lib/bitmap.c b/lib/bitmap.c index 3fc2e338ec30..1c81413c51f8 100644 --- a/lib/bitmap.c +++ b/lib/bitmap.c @@ -968,36 +968,6 @@ static int bitmap_pos_to_ord(const unsigned long *buf,= unsigned int pos, unsigne return bitmap_weight(buf, pos); } =20 -/** - * bitmap_ord_to_pos - find position of n-th set bit in bitmap - * @buf: pointer to bitmap - * @ord: ordinal bit position (n-th set bit, n >=3D 0) - * @nbits: number of valid bit positions in @buf - * - * Map the ordinal offset of bit @ord in @buf to its position in @buf. - * Value of @ord should be in range 0 <=3D @ord < weight(buf). If @ord - * >=3D weight(buf), returns @nbits. - * - * If for example, just bits 4 through 7 are set in @buf, then @ord - * values 0 through 3 will get mapped to 4 through 7, respectively, - * and all other @ord values returns @nbits. When @ord value 3 - * gets mapped to (returns) @pos value 7 in this example, that means - * that the 3rd set bit (starting with 0th) is at position 7 in @buf. - * - * The bit positions 0 through @nbits-1 are valid positions in @buf. - */ -unsigned int bitmap_ord_to_pos(const unsigned long *buf, unsigned int ord,= unsigned int nbits) -{ - unsigned int pos; - - for (pos =3D find_first_bit(buf, nbits); - pos < nbits && ord; - pos =3D find_next_bit(buf, nbits, pos + 1)) - ord--; - - return pos; -} - /** * bitmap_remap - Apply map defined by a pair of bitmaps to another bitmap * @dst: remapped result @@ -1047,7 +1017,7 @@ void bitmap_remap(unsigned long *dst, const unsigned = long *src, if (n < 0 || w =3D=3D 0) set_bit(oldbit, dst); /* identity map */ else - set_bit(bitmap_ord_to_pos(new, n % w, nbits), dst); + set_bit(find_nth_bit(new, nbits, n % w), dst); } } EXPORT_SYMBOL(bitmap_remap); @@ -1086,7 +1056,7 @@ int bitmap_bitremap(int oldbit, const unsigned long *= old, if (n < 0 || w =3D=3D 0) return oldbit; else - return bitmap_ord_to_pos(new, n % w, bits); + return find_nth_bit(new, bits, n % w); } EXPORT_SYMBOL(bitmap_bitremap); =20 @@ -1210,7 +1180,7 @@ void bitmap_onto(unsigned long *dst, const unsigned l= ong *orig, * The following code is a more efficient, but less * obvious, equivalent to the loop: * for (m =3D 0; m < bitmap_weight(relmap, bits); m++) { - * n =3D bitmap_ord_to_pos(orig, m, bits); + * n =3D find_nth_bit(orig, bits, m); * if (test_bit(m, orig)) * set_bit(n, dst); * } --=20 2.34.1 From nobody Fri Apr 3 02:23:13 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 BF09EECAAD3 for ; Sun, 18 Sep 2022 03:08:09 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S229615AbiIRDIG (ORCPT ); Sat, 17 Sep 2022 23:08:06 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:51544 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S229558AbiIRDH0 (ORCPT ); Sat, 17 Sep 2022 23:07:26 -0400 Received: from mail-qk1-x735.google.com (mail-qk1-x735.google.com [IPv6:2607:f8b0:4864:20::735]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id A383F27159 for ; Sat, 17 Sep 2022 20:07:25 -0700 (PDT) Received: by mail-qk1-x735.google.com with SMTP id q11so15400302qkc.12 for ; Sat, 17 Sep 2022 20:07:25 -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=SBOziEHkuH3w7/25l1oW2hkJ2TfdUUpVoIxYlWXHHvA=; b=Eips4MEH0hXW7hGRgRT+q3D1fUYpQ4rU/J2zk97cwSqUd4+CX8dXiYWZZjqiUwE7RP omcBLor5ov3jJk63zBPOzt7rJFsC6A3uux6r9H2ub+40Ia3YUvoHomcgKI21Oz4CxWHZ gJy3zVrH1+CMKYYwwUWYZbcosKS1hNVSEF2JIz6FkqEoWqCj20uNb9EAJhEuVayKAkmb Zao49cv2ZJUVWWLlnJbeXTQk4s7m8TXrcecbM4m5T5mM6WYL0aZGaNbzT0gUrfCAff0v AJWmACo4uIgAz0mhr1kCzWIOSRHSf4xudMBR43hA2/iphGUqL4zwqlRIAERYeM6WO48/ ErBQ== 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=SBOziEHkuH3w7/25l1oW2hkJ2TfdUUpVoIxYlWXHHvA=; b=1LXOcyf0C/haRP5xhEoaRtHQJwVrXbYiJnuPysVyJ92D1UpIdDPz0h0BAX3LyvejFB jvNqrOHN0La/DxhE7OavOEeyVdTgULBxMrWPQ3bFffWSbczRqFduru1bUBcO8eGeML8P quIG/vztCwnihUmPv0Y8Md3+Hk/NKT0wwv5h4c9A/MYWsP98yQ2UoNq0LzbtUd237UhR +zH97cZD94XwZcBIX+KvY7aInOQnb4DU/qBV/BUMieeCkOJI3bSKFdrzD+Hh2ppAoGBz m4PgT072m1gWnPfTe4e61RzjfFOX8wN4sJBWIEfy+HXN7JVLTqwOLiRk645o1dfmSQe0 qjvA== X-Gm-Message-State: ACrzQf2KAxU8l9vI6LKnKgbjq/kESIyNrFBZ4JvsD3E6r7tru5zJ3yDI 9jQy4sj6d/uBx3XHuRP/C5TGyw4Hw0A= X-Google-Smtp-Source: AMsMyM6hCNQmI2r9Ld2t4MZN5RE5pkAfvZvt4nHfjynB+SEZVXifdBE9DznHwiaavnj6QBb52cyepA== X-Received: by 2002:a05:620a:f8e:b0:6cc:1c3a:4f5d with SMTP id b14-20020a05620a0f8e00b006cc1c3a4f5dmr8833133qkn.425.1663470444652; Sat, 17 Sep 2022 20:07:24 -0700 (PDT) Received: from localhost ([2601:4c1:c100:2270:a495:2224:867e:566a]) by smtp.gmail.com with ESMTPSA id de20-20020a05620a371400b006bb49cfe147sm9319549qkb.84.2022.09.17.20.07.24 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Sat, 17 Sep 2022 20:07:24 -0700 (PDT) From: Yury Norov To: linux-kernel@vger.kernel.org, Alexander Lobakin , Andy Shevchenko , Arnd Bergmann , David Gow , Eric Dumazet , Isabella Basso , Kees Cook , Keith Busch , Kumar Kartikeya Dwivedi , Marco Elver , Mark Rutland , Rasmus Villemoes , Steven Rostedt , =?UTF-8?q?Toke=20H=C3=B8iland-J=C3=B8rgensen?= , Valentin Schneider Cc: Yury Norov Subject: [PATCH v3 6/6] cpumask: add cpumask_nth_{,and,andnot} Date: Sat, 17 Sep 2022 20:07:16 -0700 Message-Id: <20220918030716.1252285-7-yury.norov@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20220918030716.1252285-1-yury.norov@gmail.com> References: <20220918030716.1252285-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" Add cpumask_nth_{,and,andnot} as wrappers around corresponding find functions, and use it in cpumask_local_spread(). Signed-off-by: Yury Norov --- include/linux/cpumask.h | 44 +++++++++++++++++++++++++++++++++++++++++ lib/cpumask.c | 28 ++++++++++++-------------- 2 files changed, 57 insertions(+), 15 deletions(-) diff --git a/include/linux/cpumask.h b/include/linux/cpumask.h index 31bf08c786e3..621b59820561 100644 --- a/include/linux/cpumask.h +++ b/include/linux/cpumask.h @@ -337,6 +337,50 @@ unsigned int cpumask_any_but(const struct cpumask *mas= k, unsigned int cpu) return i; } =20 +/** + * cpumask_nth - get the first cpu in a cpumask + * @srcp: the cpumask pointer + * @cpu: the N'th cpu to find, starting from 0 + * + * Returns >=3D nr_cpu_ids if such cpu doesn't exist. + */ +static inline unsigned int cpumask_nth(unsigned int cpu, const struct cpum= ask *srcp) +{ + return find_nth_bit(cpumask_bits(srcp), nr_cpumask_bits, cpumask_check(cp= u)); +} + +/** + * cpumask_nth_and - get the first cpu in 2 cpumasks + * @srcp1: the cpumask pointer + * @srcp2: the cpumask pointer + * @cpu: the N'th cpu to find, starting from 0 + * + * Returns >=3D nr_cpu_ids if such cpu doesn't exist. + */ +static inline +unsigned int cpumask_nth_and(unsigned int cpu, const struct cpumask *srcp1, + const struct cpumask *srcp2) +{ + return find_nth_and_bit(cpumask_bits(srcp1), cpumask_bits(srcp2), + nr_cpumask_bits, cpumask_check(cpu)); +} + +/** + * cpumask_nth_andnot - get the first cpu set in 1st cpumask, and clear in= 2nd. + * @srcp1: the cpumask pointer + * @srcp2: the cpumask pointer + * @cpu: the N'th cpu to find, starting from 0 + * + * Returns >=3D nr_cpu_ids if such cpu doesn't exist. + */ +static inline +unsigned int cpumask_nth_andnot(unsigned int cpu, const struct cpumask *sr= cp1, + const struct cpumask *srcp2) +{ + return find_nth_andnot_bit(cpumask_bits(srcp1), cpumask_bits(srcp2), + nr_cpumask_bits, cpumask_check(cpu)); +} + #define CPU_BITS_NONE \ { \ [0 ... BITS_TO_LONGS(NR_CPUS)-1] =3D 0UL \ diff --git a/lib/cpumask.c b/lib/cpumask.c index f0ae119be8c4..2c4a63b6f03f 100644 --- a/lib/cpumask.c +++ b/lib/cpumask.c @@ -128,23 +128,21 @@ unsigned int cpumask_local_spread(unsigned int i, int= node) i %=3D num_online_cpus(); =20 if (node =3D=3D NUMA_NO_NODE) { - for_each_cpu(cpu, cpu_online_mask) - if (i-- =3D=3D 0) - return cpu; + cpu =3D cpumask_nth(i, cpu_online_mask); + if (cpu < nr_cpu_ids) + return cpu; } else { /* NUMA first. */ - for_each_cpu_and(cpu, cpumask_of_node(node), cpu_online_mask) - if (i-- =3D=3D 0) - return cpu; - - for_each_cpu(cpu, cpu_online_mask) { - /* Skip NUMA nodes, done above. */ - if (cpumask_test_cpu(cpu, cpumask_of_node(node))) - continue; - - if (i-- =3D=3D 0) - return cpu; - } + cpu =3D cpumask_nth_and(i, cpu_online_mask, cpumask_of_node(node)); + if (cpu < nr_cpu_ids) + return cpu; + + i -=3D cpumask_weight_and(cpu_online_mask, cpumask_of_node(node)); + + /* Skip NUMA nodes, done above. */ + cpu =3D cpumask_nth_andnot(i, cpu_online_mask, cpumask_of_node(node)); + if (cpu < nr_cpu_ids) + return cpu; } BUG(); } --=20 2.34.1