From nobody Tue Dec 16 11:04:45 2025 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 DEA9DC83F19 for ; Mon, 28 Aug 2023 18:44:48 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S233103AbjH1SoU (ORCPT ); Mon, 28 Aug 2023 14:44:20 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:33100 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S233112AbjH1SoD (ORCPT ); Mon, 28 Aug 2023 14:44:03 -0400 Received: from mail-oo1-xc33.google.com (mail-oo1-xc33.google.com [IPv6:2607:f8b0:4864:20::c33]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 8DB2EBF for ; Mon, 28 Aug 2023 11:43:59 -0700 (PDT) Received: by mail-oo1-xc33.google.com with SMTP id 006d021491bc7-5736caaf151so1284664eaf.3 for ; Mon, 28 Aug 2023 11:43:59 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20221208; t=1693248238; x=1693853038; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=VTMG7+AqXiKDuJXJ9Y6Nzjcn2Rotqo5yC7DsVnC84Pw=; b=K7TRNBXugj8bd+nVVa05uAP6lyYbcOCbOCDwwpOo6trQAi9m9VmGJwVJg3PCDEKjMP GxWkWDpS+gYVApv5whYR/pDhKNFS/xXX9MWccmOx47WGdtL58R/jElG0sjmlU15DbHk6 cvAEkyGXndhdo8EVXhI1oWCmbZL4QDVVAlFJI951wcWKnGNBuM8oVQjFS+T5DVBQafKG cD+onDTRJbQ3TS+wptAGMFhf/S0XAKKjA0+fI6cthyGdNRi8yITYjwoWt2PhfWBmmP2m kFAkDWv5aCp6jI/XD7PBC9r6tRsTKT4Xd0eXzzVIw2eKhLJetuQDBoE2Aq4lET/ZDIuV QrfA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1693248238; x=1693853038; 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:message-id:reply-to; bh=VTMG7+AqXiKDuJXJ9Y6Nzjcn2Rotqo5yC7DsVnC84Pw=; b=alAZLSMdSbZ+w4LtNRj4VBMyhlZ8kuwaRFpA+85wo6FMFAik7q/0hyfVhx89lnAw9I RGZ5YyA0A6MxREECoA6ki5kUNyyIeyi0ofiwmb9kft8l7bL+ngUX/GVVbhc31QOxxMjd tYCyaFrYGuZ9pHeWvYjaSNnmeH3jRF9hq70CDHXLiw+AXLcLvvVV4NC6wzL6osHTVS6O QSyLUXFAF2+qr8RJ2S0kLMbyFhc9souAQefDo8pnxRvEAaA0fUIK535zbBWj1U38pDD5 emop+NYkbRfeWkisSpmBaK4i5iRr08y6tk5Hx14fBDWrFNAKHsrlXxeuKsLNeLoC4LaA UQlw== X-Gm-Message-State: AOJu0YwVnzKtK1K8edGqdItRMvVgnhCKpGVDwyoLiEwbVN1qB2EXBGE/ owFwOfV9h3IoiFGGcpCtgviU8pSC9pg= X-Google-Smtp-Source: AGHT+IGg+iwbv+Z/nIsQrPx/VWfe901Sv85pYwfmveXlI3XHkb8e2dObNIisqfgSNzQwoRNOpMXUHg== X-Received: by 2002:a4a:275d:0:b0:571:aceb:26c8 with SMTP id w29-20020a4a275d000000b00571aceb26c8mr11702441oow.3.1693248238157; Mon, 28 Aug 2023 11:43:58 -0700 (PDT) Received: from localhost ([2600:6c5e:2a00:5805:e348:56d4:5da8:636d]) by smtp.gmail.com with ESMTPSA id l11-20020a4ad9cb000000b00565fbd0d4c0sm3928739oou.28.2023.08.28.11.43.57 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 28 Aug 2023 11:43:57 -0700 (PDT) From: Yury Norov To: linux-kernel@vger.kernel.org Cc: Yury Norov , Andy Shevchenko , Rasmus Villemoes Subject: [PATCH 01/12] bitmap: add find_nth_bit_from() Date: Mon, 28 Aug 2023 11:43:41 -0700 Message-Id: <20230828184353.5145-2-yury.norov@gmail.com> X-Mailer: git-send-email 2.39.2 In-Reply-To: <20230828184353.5145-1-yury.norov@gmail.com> References: <20230828184353.5145-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" Similarly to find_next_bit(), add a _from flavor for find_nth_bit(). It's useful when traversing bitmaps in a loop because it allows to not count bits from the beginning every time. The test is added as well. Signed-off-by: Yury Norov --- include/linux/find.h | 37 +++++++++++++++++++++++++++++++++++++ lib/find_bit.c | 29 +++++++++++++++++++++++++++++ lib/test_bitmap.c | 10 +++++++++- 3 files changed, 75 insertions(+), 1 deletion(-) diff --git a/include/linux/find.h b/include/linux/find.h index 5e4f39ef2e72..f7fb88405201 100644 --- a/include/linux/find.h +++ b/include/linux/find.h @@ -27,6 +27,8 @@ unsigned long __find_nth_andnot_bit(const unsigned long *= addr1, const unsigned l unsigned long __find_nth_and_andnot_bit(const unsigned long *addr1, const = unsigned long *addr2, const unsigned long *addr3, unsigned long size, unsigned long n); +unsigned long __find_nth_bit_from(const unsigned long *addr, unsigned long= size, + unsigned long start, unsigned long nth); 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); @@ -237,6 +239,41 @@ unsigned long find_nth_bit(const unsigned long *addr, = unsigned long size, unsign return __find_nth_bit(addr, size, n); } =20 +/** + * find_nth_bit_from - find N'th set bit in a memory region starting at @o= ff + * @addr: The address to start the search at + * @size: The maximum number of bits to search + * @off: The offset to start search + * @n: The number of set bit, which position is needed, counting from 0 + * + * The following is semantically equivalent: + * idx =3D find_nth_bit_from(addr, size, off, 0); + * idx =3D find_next_bit(addr, size, off); + * + * Return: the bit number of the N'th set bit. + * If no such, returns @size. + */ +static __always_inline +unsigned long find_nth_bit_from(const unsigned long *addr, unsigned long s= ize, + unsigned long start, unsigned long n) +{ + if (n >=3D size - start) + return size; + + if (small_const_nbits(size - start) && size / BITS_PER_LONG =3D=3D start = / BITS_PER_LONG) { + unsigned long val, idx =3D start / BITS_PER_LONG; + + val =3D addr[idx] & GENMASK(size - 1, start); + if (val =3D=3D 0) + return size; + + val =3D idx * BITS_PER_LONG + fns(val, n); + return val < size ? val : size; + } + + return __find_nth_bit_from(addr, size, start, n); +} + /** * find_nth_and_bit - find N'th set bit in 2 memory regions * @addr1: The 1st address to start the search at diff --git a/lib/find_bit.c b/lib/find_bit.c index 32f99e9a670e..49959b51df8c 100644 --- a/lib/find_bit.c +++ b/lib/find_bit.c @@ -164,6 +164,35 @@ unsigned long __find_nth_and_andnot_bit(const unsigned= long *addr1, } EXPORT_SYMBOL(__find_nth_and_andnot_bit); =20 +#define FIND_NTH_BIT_FROM(FETCH, size, start, nth) \ +({ \ + unsigned long mask, idx, tmp, w, sz =3D (size), __start =3D (start), n = =3D (nth);\ + \ + if (unlikely(__start >=3D sz || n > sz - __start)) \ + goto out; \ + \ + mask =3D BITMAP_FIRST_WORD_MASK(__start); \ + idx =3D __start / BITS_PER_LONG; \ + \ + for (tmp =3D (FETCH) & mask; (w =3D hweight_long(tmp)) <=3D n; tmp =3D (F= ETCH)) {\ + if ((idx + 1) * BITS_PER_LONG >=3D sz) \ + goto out; \ + idx++; \ + n -=3D w; \ + } \ + \ + sz =3D min(idx * BITS_PER_LONG + fns(tmp, n), sz); \ +out: \ + sz; \ +}) + +unsigned long __find_nth_bit_from(const unsigned long *addr, unsigned long= size, + unsigned long start, unsigned long nth) +{ + return FIND_NTH_BIT_FROM(addr[idx], size, start, nth); +} +EXPORT_SYMBOL(__find_nth_bit_from); + #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) diff --git a/lib/test_bitmap.c b/lib/test_bitmap.c index def7d2f9bd14..3248ed58a817 100644 --- a/lib/test_bitmap.c +++ b/lib/test_bitmap.c @@ -223,7 +223,7 @@ static void __init test_zero_clear(void) =20 static void __init test_find_nth_bit(void) { - unsigned long b, bit, cnt =3D 0; + unsigned long i, b, bit, cnt =3D 0; DECLARE_BITMAP(bmap, 64 * 3); =20 bitmap_zero(bmap, 64 * 3); @@ -260,6 +260,14 @@ static void __init test_find_nth_bit(void) b =3D find_nth_bit(exp1, EXP1_IN_BITS, cnt++); expect_eq_uint(b, bit); } + + for (i =3D 0; i < EXP1_IN_BITS; i++) { + bit =3D i; cnt =3D 0; + for_each_set_bit_from(bit, exp1, EXP1_IN_BITS) { + b =3D find_nth_bit_from(exp1, EXP1_IN_BITS, i, cnt++); + expect_eq_uint(b, bit); + } + } } =20 static void __init test_fill_set(void) --=20 2.39.2 From nobody Tue Dec 16 11:04:45 2025 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 C43D6C83F11 for ; Mon, 28 Aug 2023 18:44:49 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S233110AbjH1SoX (ORCPT ); Mon, 28 Aug 2023 14:44:23 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:33128 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S233117AbjH1SoE (ORCPT ); Mon, 28 Aug 2023 14:44:04 -0400 Received: from mail-oa1-x36.google.com (mail-oa1-x36.google.com [IPv6:2001:4860:4864:20::36]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 046A8C0 for ; Mon, 28 Aug 2023 11:44:01 -0700 (PDT) Received: by mail-oa1-x36.google.com with SMTP id 586e51a60fabf-1c0fa9dd74fso2491033fac.3 for ; Mon, 28 Aug 2023 11:44:00 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20221208; t=1693248240; x=1693853040; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=eh6X7eL440kyl35oBdovKJ2YgsKz4G6HIjTbBBVGh+8=; b=TxC9JZBqMYLXPg7C8k6HTi08Al+zDSkxUVeAklo/tyDDRLBnotVGA6HM4f5Mu3a6f9 BkwEFv97u2PSqW4GQgrJibzrGNvPJWHR98g7hktIFVUyqkISlLkFUGj7IIectzaBcU+d 5OpAu09Cpw8bJ/BT1FI8ku7y9ZHlusIZbDRDVy1bjg0LA6fnMEIBcdNDFXd+08+iSHUR zt4s6+T+5QBCp+hfpf6RD6VDgQdpzoJfTAv7nkhJXVOnUZTEXWGyqtKIrZ52t+zZO3Fx 5DGRE5xNcimzejV7d3ExuXRbFSiFwt0ZDd4t44wUIkiPWKq8zd6Ky0CWYnUJGzzzLIHO eZ2g== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1693248240; x=1693853040; 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:message-id:reply-to; bh=eh6X7eL440kyl35oBdovKJ2YgsKz4G6HIjTbBBVGh+8=; b=YuzWmMw0B9WKZ++bZeCSOTZDvbKu+nie1AA1+/uD1yC5mdqaaV3f1wyhYinBRh2SvQ UjqJo8xfEutx0wZxienN5Gy/q+Ldb9LZ5oNflp65lr8q8BULpwVCzjupUAIuDQisX3hj JVQt0OZtbIV5Ywk3i+2ED3tXgHbVVeG9ApHGp/eg8GftZjqrTy0J4dxnS9cyrB3Lp4vx qX9v2lJXIK9t3Ar9s1y1YumiNxm2jSWwCi0WmzChlTGfc6kQeUHAqDN+xgWLPpZCZewx cNWfT/lvP83tZSYqBV4b1dla32SDCYaj0Xt2YDkeWtKKi8RISv4ij2ifgGmV6aqXkT/N E7hQ== X-Gm-Message-State: AOJu0Yygk1oopUgP5tAxUX3LUOH9tDzjmJ+BDQNcpIFvskMaroUwWxya pgSLjpbuGn/1AutuHwJZJt2OmvJ3ulo= X-Google-Smtp-Source: AGHT+IF+mFPrmiRsSVKId9NVK72PFCqju3DAUAeS439vj9gBkpT2bSVR6obRG5qnomKUPzWBxMA7Gw== X-Received: by 2002:a05:6870:8a0e:b0:1bb:4bad:ebce with SMTP id p14-20020a0568708a0e00b001bb4badebcemr14484773oaq.27.1693248239897; Mon, 28 Aug 2023 11:43:59 -0700 (PDT) Received: from localhost ([2600:6c5e:2a00:5805:e348:56d4:5da8:636d]) by smtp.gmail.com with ESMTPSA id u38-20020a4a9729000000b0056360466d3esm4308173ooi.48.2023.08.28.11.43.59 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 28 Aug 2023 11:43:59 -0700 (PDT) From: Yury Norov To: linux-kernel@vger.kernel.org Cc: Yury Norov , Andy Shevchenko , Rasmus Villemoes Subject: [PATCH 02/12] bitmap: add bitmap_weight_from() Date: Mon, 28 Aug 2023 11:43:42 -0700 Message-Id: <20230828184353.5145-3-yury.norov@gmail.com> X-Mailer: git-send-email 2.39.2 In-Reply-To: <20230828184353.5145-1-yury.norov@gmail.com> References: <20230828184353.5145-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 a _from flavor for bitmap_weight(). It's useful when traversing bitmaps in a loop to not count bits from the beginning every time. The test for bitmap_weight{,_from}() is added as well. Signed-off-by: Yury Norov --- include/linux/bitmap.h | 14 ++++++++++++++ lib/bitmap.c | 25 +++++++++++++++++++++++++ lib/test_bitmap.c | 18 ++++++++++++++++++ 3 files changed, 57 insertions(+) diff --git a/include/linux/bitmap.h b/include/linux/bitmap.h index 692d0a1dbe92..6acbdd2abd0c 100644 --- a/include/linux/bitmap.h +++ b/include/linux/bitmap.h @@ -168,6 +168,8 @@ bool __bitmap_subset(const unsigned long *bitmap1, 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); +unsigned int __bitmap_weight_from(const unsigned long *bitmap, + unsigned int bits, unsigned int start); void __bitmap_set(unsigned long *map, unsigned int start, int len); void __bitmap_clear(unsigned long *map, unsigned int start, int len); =20 @@ -446,6 +448,18 @@ unsigned long bitmap_weight_and(const unsigned long *s= rc1, return __bitmap_weight_and(src1, src2, nbits); } =20 +static __always_inline +unsigned int bitmap_weight_from(const unsigned long *src, unsigned int nbi= ts, unsigned int start) +{ + if (unlikely(start >=3D nbits)) + return 0; + + if (small_const_nbits(nbits - start) && nbits / BITS_PER_LONG =3D=3D star= t / BITS_PER_LONG) + return hweight_long(*src & GENMASK(nbits-1, start)); + + return __bitmap_weight_from(src, nbits, start); +} + static __always_inline void bitmap_set(unsigned long *map, unsigned int st= art, unsigned int nbits) { diff --git a/lib/bitmap.c b/lib/bitmap.c index cf77d56cf223..65c64911c92f 100644 --- a/lib/bitmap.c +++ b/lib/bitmap.c @@ -345,6 +345,24 @@ EXPORT_SYMBOL(__bitmap_subset); w; \ }) =20 +#define BITMAP_WEIGHT_FROM(FETCH, bits, start) \ +({ \ + unsigned long __bits =3D (bits), val, idx, w =3D 0, __start =3D (start), = mask;\ + \ + mask =3D BITMAP_FIRST_WORD_MASK(__start); \ + idx =3D __start / BITS_PER_LONG; \ + \ + for (val =3D (FETCH) & mask; idx < __bits / BITS_PER_LONG; val =3D (FETCH= )) {\ + w +=3D hweight_long(val); \ + idx++; \ + } \ + \ + if (__bits % BITS_PER_LONG) \ + w +=3D hweight_long((val) & BITMAP_LAST_WORD_MASK(__bits)); \ + \ + w; \ +}) + unsigned int __bitmap_weight(const unsigned long *bitmap, unsigned int bit= s) { return BITMAP_WEIGHT(bitmap[idx], bits); @@ -358,6 +376,13 @@ unsigned int __bitmap_weight_and(const unsigned long *= bitmap1, } EXPORT_SYMBOL(__bitmap_weight_and); =20 +unsigned int __bitmap_weight_from(const unsigned long *bitmap, + unsigned int bits, unsigned int start) +{ + return BITMAP_WEIGHT_FROM(bitmap[idx], bits, start); +} +EXPORT_SYMBOL(__bitmap_weight_from); + void __bitmap_set(unsigned long *map, unsigned int start, int len) { unsigned long *p =3D map + BIT_WORD(start); diff --git a/lib/test_bitmap.c b/lib/test_bitmap.c index 3248ed58a817..a5d823f7589d 100644 --- a/lib/test_bitmap.c +++ b/lib/test_bitmap.c @@ -361,6 +361,23 @@ static void __init test_bitmap_region(void) expect_eq_uint(bitmap_weight(bmap, 1000), 0); } =20 +static void __init test_weight(void) +{ + DECLARE_BITMAP(bmap, 1024); + unsigned int idx, w; + + for (idx =3D 0; idx < 1024; idx++) + __assign_bit(idx, bmap, idx); + + w =3D bitmap_weight(bmap, 1024); + for (idx =3D 0; idx < 1024; idx++) { + unsigned int w1 =3D bitmap_weight(bmap, idx); + unsigned int w2 =3D bitmap_weight_from(bmap, 1024, idx); + + expect_eq_uint(w1 + w2, w); + } +} + #define EXP2_IN_BITS (sizeof(exp2) * 8) =20 static void __init test_replace(void) @@ -1260,6 +1277,7 @@ static void __init selftest(void) test_copy(); test_bitmap_region(); test_replace(); + test_weight(); test_bitmap_arr32(); test_bitmap_arr64(); test_bitmap_parse(); --=20 2.39.2 From nobody Tue Dec 16 11:04:45 2025 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 DC142C83F1A for ; Mon, 28 Aug 2023 18:44:49 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S233117AbjH1SoZ (ORCPT ); Mon, 28 Aug 2023 14:44:25 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:33154 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S233118AbjH1SoE (ORCPT ); Mon, 28 Aug 2023 14:44:04 -0400 Received: from mail-ot1-x32b.google.com (mail-ot1-x32b.google.com [IPv6:2607:f8b0:4864:20::32b]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 612E4BF for ; Mon, 28 Aug 2023 11:44:02 -0700 (PDT) Received: by mail-ot1-x32b.google.com with SMTP id 46e09a7af769-6bcae8c4072so2410184a34.1 for ; Mon, 28 Aug 2023 11:44:02 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20221208; t=1693248241; x=1693853041; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=5rqkvZA+m4Co7mK4wIInGc1Yx/+x+E1K3USzQUDzsT0=; b=Livc0PaChEpmZbX7QTsKnliy45x50RNaWbynGVLdkowAwOQXuqHGksuZE8h2JEuXoz VBQCh89e95HwaCY1PGwLd5C9brm982As1qibqaQ9iBjkmP0wlBABfgLyAr8fcpE+Ka1t P4nA5PfaZITh2Hk2st+NSCryf3Jq6S3Xz/5v6+sCggPMWV6nZ9+40++J9HSXJ7B+rHQ9 UL8tt0RtOltoSM5k4wPJ651DNHL3bBwP8ul5J8Po1vVSBdWSAIoz7Jh7A7hR6k+EQ8bZ T5g0jZUgSKJW5rrt1e89dByliwTF0TsknbGaguWfO0baC2WuJRzSIdXPqjumj5lKRgX7 s6RA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1693248241; x=1693853041; 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:message-id:reply-to; bh=5rqkvZA+m4Co7mK4wIInGc1Yx/+x+E1K3USzQUDzsT0=; b=mDb6Qwhhg9bytY31DiBZgb15ux0LAaJnKqcTfSj3/2Zm8WGghl7T8TsHQOZwxjFizQ oqO5ay6wlhYjo55+jM75kdqt649TJLiqxRLC3JWJQel6S9mluNWLvhTbJe557PYtiyx9 MQ+MU/nFXvyhoMA8fpZDzFbm6FORhQMMelJ+78ipy+9tS3qYC9ntYSrgDaqltreYgREK yqboCPlFYcdFdYqGC9yaKOdZUxjEmNfHEx2Vl+JNra1FZpuBT8j+Dk8PXM5KC/gjVY7T PaQ9PPLVB4LWOjvoD8YmKhXvM2XeV5kwrpIjP0VhHm9nbvqnjKNEuOhJdpHGjIL8y1JG f8Sg== X-Gm-Message-State: AOJu0YwaYqt+O0f3BqTk10/011UA+eU9l7kv21iPWxKzM3aiK0qsMWPv kn7Q3DXPfP+OImEm+xGkcIxqT88A3Lw= X-Google-Smtp-Source: AGHT+IEnxhLP+YPYgRbroOpWL+D5N3R7se11xwTu4MXZi2EgoCg3hUnwljJbUCKkbgine9QclHEofg== X-Received: by 2002:a05:6871:69e:b0:1bf:12ff:db2c with SMTP id l30-20020a056871069e00b001bf12ffdb2cmr10761239oao.22.1693248241229; Mon, 28 Aug 2023 11:44:01 -0700 (PDT) Received: from localhost ([2600:6c5e:2a00:5805:e348:56d4:5da8:636d]) by smtp.gmail.com with ESMTPSA id g6-20020a056870340600b001cd316935c6sm2627296oah.54.2023.08.28.11.44.00 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 28 Aug 2023 11:44:00 -0700 (PDT) From: Yury Norov To: linux-kernel@vger.kernel.org Cc: Yury Norov , Andy Shevchenko , Rasmus Villemoes Subject: [PATCH 03/12] bitmap: add test for bitmap_remap() Date: Mon, 28 Aug 2023 11:43:43 -0700 Message-Id: <20230828184353.5145-4-yury.norov@gmail.com> X-Mailer: git-send-email 2.39.2 In-Reply-To: <20230828184353.5145-1-yury.norov@gmail.com> References: <20230828184353.5145-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" Basic functional and performance tests for bitmap_remap(). 1000 bits length is chosen for performance test because it's of the same order as default value for MAX_NUMNODES in major distros like Ubuntu (1024). Signed-off-by: Yury Norov --- lib/test_bitmap.c | 80 +++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 80 insertions(+) diff --git a/lib/test_bitmap.c b/lib/test_bitmap.c index a5d823f7589d..e1c22d399f24 100644 --- a/lib/test_bitmap.c +++ b/lib/test_bitmap.c @@ -378,6 +378,85 @@ static void __init test_weight(void) } } =20 +static void __init test_remap(void) +{ + DECLARE_BITMAP(dst, 8); + + DECLARE_BITMAP(empty, 8) =3D { 0 }; + DECLARE_BITMAP(src, 8) =3D { 0b00101010 }; + DECLARE_BITMAP(old, 8) =3D { 0b00011100 }; + DECLARE_BITMAP(new, 8) =3D { 0b00111000 }; + DECLARE_BITMAP(exp0, 8) =3D { 0b00110010 }; + DECLARE_BITMAP(exp1, 8) =3D { 0b00011010 }; + DECLARE_BITMAP(exp2, 8) =3D { 0b10000010 }; + + DECLARE_BITMAP(perf_exp, 1000); + DECLARE_BITMAP(perf_dst, 1000); + DECLARE_BITMAP(perf_src, 1000); + DECLARE_BITMAP(perf_old, 1000); + DECLARE_BITMAP(perf_new, 1000); + + unsigned int i; + ktime_t time; + + bitmap_remap(dst, src, old, new, 8); + expect_eq_bitmap(exp0, dst, 8); + + /* + * When old mapping is the same as new, source bits are copied to dst. + * Real code must use bitmap_copy() if it's known in advance. + */ + bitmap_remap(dst, src, old, old, 8); + expect_eq_bitmap(src, dst, 8); + + bitmap_remap(dst, src, new, new, 8); + expect_eq_bitmap(src, dst, 8); + + /* + * When either old or new mappings are empty, source bits are copied to + * dst. Real code must use bitmap_copy() if it's known in advance. + */ + bitmap_remap(dst, src, empty, new, 8); + expect_eq_bitmap(src, dst, 8); + + bitmap_remap(dst, src, old, empty, 8); + expect_eq_bitmap(src, dst, 8); + + bitmap_remap(dst, src, empty, empty, 8); + expect_eq_bitmap(src, dst, 8); + + /* Set extra bit in old map to test carry logic */ + set_bit(5, old); + bitmap_remap(dst, src, old, new, 8); + expect_eq_bitmap(exp1, dst, 8); + + /* Map old bits to #7 */ + bitmap_zero(new, 8); + set_bit(7, new); + bitmap_remap(dst, src, old, new, 8); + expect_eq_bitmap(exp2, dst, 8); + + bitmap_fill(perf_src, 1000); + bitmap_set(perf_old, 0, 500); + bitmap_clear(perf_old, 500, 500); + + for (i =3D 0; i < 1000; i +=3D 20) { + bitmap_set(perf_new, i, 10); + bitmap_clear(perf_new, i + 10, 10); + } + + bitmap_copy(perf_exp, perf_new, 500); + bitmap_set(perf_exp, 500, 500); + + time =3D ktime_get(); + bitmap_remap(perf_dst, perf_src, perf_old, perf_new, 1000); + time =3D ktime_get() - time; + + expect_eq_bitmap(perf_exp, perf_dst, 1000); + pr_err("bitmap_remap: %llu ns\n", time); + +} + #define EXP2_IN_BITS (sizeof(exp2) * 8) =20 static void __init test_replace(void) @@ -1278,6 +1357,7 @@ static void __init selftest(void) test_bitmap_region(); test_replace(); test_weight(); + test_remap(); test_bitmap_arr32(); test_bitmap_arr64(); test_bitmap_parse(); --=20 2.39.2 From nobody Tue Dec 16 11:04:45 2025 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 EDEE2C83F1C for ; Mon, 28 Aug 2023 18:44:49 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S233133AbjH1So0 (ORCPT ); Mon, 28 Aug 2023 14:44:26 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:33164 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S233120AbjH1SoG (ORCPT ); Mon, 28 Aug 2023 14:44:06 -0400 Received: from mail-oi1-x234.google.com (mail-oi1-x234.google.com [IPv6:2607:f8b0:4864:20::234]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id CB2C3B0 for ; Mon, 28 Aug 2023 11:44:03 -0700 (PDT) Received: by mail-oi1-x234.google.com with SMTP id 5614622812f47-3a7d7de894bso2664204b6e.3 for ; Mon, 28 Aug 2023 11:44:03 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20221208; t=1693248242; x=1693853042; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=6TB/j/ZWZca45fLEWddb9WmisfBlH+TD3Akz3eSDVAc=; b=c5KDgZwo4D/k/8kWu/dUfuohPTeeEn+GWExeUTP+FhFsEmj/sXDfarBzv/z5PYfo+9 G57V3LO8rsOSe10NHJTi96c4vXM8zVdkVYyaE8eLHT19yZ2huNHIenEfM5TiPlQetfCG ucYwxWWMyTGDtJFkw5H1QOUF1E/161b0h8OADTklEUIEJcuwfTGPmVWZB3SKrfG9K35o IqPYlXhvohGNs2FOHZ3uPoZPFyS/rov1EtBAbBnUUXGdBGREYJvs9t45AQCK4IR1tb5n 7ZOX+w9Xhm1qNwiw58vPPpuWa1NbbSE/kfbr4qfZ/DD2B1epmUmAPlVsNwE5oARHV/4S HMvg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1693248242; x=1693853042; 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:message-id:reply-to; bh=6TB/j/ZWZca45fLEWddb9WmisfBlH+TD3Akz3eSDVAc=; b=POMKEIANM1mpzBwh+3q72k0Kj3OzHqElHJbCEJ4jTFROB12aw/oUEvdDqJuUrJz24S vrfOhGq3ZHCQ3HVkA5p+FT1CaDMZG32U16yhBM7kWkojlA9XLYy1K2PDMvbSuTD0mHZ/ r6CGxT7nfewqS5XYXlF55TSO2aZX0cATlDlwACZE3vwO/sjQZvBvQpE1w1aPjCeg22nZ Z5ic7Voa/qFaYQHlysNkT2DfPLVxuX1Lwu2Wxk8aK4VnPhsbsiXoW8fK1rEhzxvNXR4g cWdb9L70bDPKrEbNxAH/3DsUg/r9UA2xDSSTpzp/BXIiidSupt2kAoADmO4z8M0V2VB1 WnUQ== X-Gm-Message-State: AOJu0Yxh5qNfMEOnv5HrtxqnJYxGTuUetAOXWpzfLvaUhHQa7OUyFgAh Pz0mlDPjhKyv6JzdmqHdII3NN3X0Nhk= X-Google-Smtp-Source: AGHT+IFWjZUZX9Q+MuK4PQbP3XZTwypZYKopJUOgpLV3UJyGCOYwnwVovIenTHTJWKfWQ4BnACz3oQ== X-Received: by 2002:a05:6808:2a7a:b0:3a1:eccc:26da with SMTP id fu26-20020a0568082a7a00b003a1eccc26damr10737881oib.25.1693248242660; Mon, 28 Aug 2023 11:44:02 -0700 (PDT) Received: from localhost ([2600:6c5e:2a00:5805:e348:56d4:5da8:636d]) by smtp.gmail.com with ESMTPSA id k24-20020a544698000000b003a9a2362f66sm2178194oic.16.2023.08.28.11.44.02 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 28 Aug 2023 11:44:02 -0700 (PDT) From: Yury Norov To: linux-kernel@vger.kernel.org Cc: Yury Norov , Andy Shevchenko , Rasmus Villemoes Subject: [PATCH 04/12] bitmap: add test for bitmap_bitremap() Date: Mon, 28 Aug 2023 11:43:44 -0700 Message-Id: <20230828184353.5145-5-yury.norov@gmail.com> X-Mailer: git-send-email 2.39.2 In-Reply-To: <20230828184353.5145-1-yury.norov@gmail.com> References: <20230828184353.5145-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" Similarly to bitmap_remap, test bitmap_bitremap(). Signed-off-by: Yury Norov --- lib/test_bitmap.c | 34 ++++++++++++++++++++++++++++++++++ 1 file changed, 34 insertions(+) diff --git a/lib/test_bitmap.c b/lib/test_bitmap.c index e1c22d399f24..e9211f9a0e67 100644 --- a/lib/test_bitmap.c +++ b/lib/test_bitmap.c @@ -378,6 +378,19 @@ static void __init test_weight(void) } } =20 +static __always_inline void __init __test_bitremap(unsigned long *dst, uns= igned long *src, + unsigned long *old, unsigned long *new, unsigned long nbits) +{ + unsigned long oldbit, newbit; + + bitmap_zero(dst, nbits); + + for_each_set_bit(oldbit, src, nbits) { + newbit =3D bitmap_bitremap(oldbit, old, new, nbits); + __set_bit(newbit, dst); + } +} + static void __init test_remap(void) { DECLARE_BITMAP(dst, 8); @@ -402,6 +415,9 @@ static void __init test_remap(void) bitmap_remap(dst, src, old, new, 8); expect_eq_bitmap(exp0, dst, 8); =20 + __test_bitremap(dst, src, old, new, 8); + expect_eq_bitmap(exp0, dst, 8); + /* * When old mapping is the same as new, source bits are copied to dst. * Real code must use bitmap_copy() if it's known in advance. @@ -409,6 +425,9 @@ static void __init test_remap(void) bitmap_remap(dst, src, old, old, 8); expect_eq_bitmap(src, dst, 8); =20 + __test_bitremap(dst, src, old, old, 8); + expect_eq_bitmap(src, dst, 8); + bitmap_remap(dst, src, new, new, 8); expect_eq_bitmap(src, dst, 8); =20 @@ -419,23 +438,38 @@ static void __init test_remap(void) bitmap_remap(dst, src, empty, new, 8); expect_eq_bitmap(src, dst, 8); =20 + __test_bitremap(dst, src, empty, new, 8); + expect_eq_bitmap(src, dst, 8); + bitmap_remap(dst, src, old, empty, 8); expect_eq_bitmap(src, dst, 8); =20 + __test_bitremap(dst, src, old, empty, 8); + expect_eq_bitmap(src, dst, 8); + bitmap_remap(dst, src, empty, empty, 8); expect_eq_bitmap(src, dst, 8); =20 + __test_bitremap(dst, src, empty, empty, 8); + expect_eq_bitmap(src, dst, 8); + /* Set extra bit in old map to test carry logic */ set_bit(5, old); bitmap_remap(dst, src, old, new, 8); expect_eq_bitmap(exp1, dst, 8); =20 + __test_bitremap(dst, src, old, new, 8); + expect_eq_bitmap(exp1, dst, 8); + /* Map old bits to #7 */ bitmap_zero(new, 8); set_bit(7, new); bitmap_remap(dst, src, old, new, 8); expect_eq_bitmap(exp2, dst, 8); =20 + __test_bitremap(dst, src, old, new, 8); + expect_eq_bitmap(exp2, dst, 8); + bitmap_fill(perf_src, 1000); bitmap_set(perf_old, 0, 500); bitmap_clear(perf_old, 500, 500); --=20 2.39.2 From nobody Tue Dec 16 11:04:45 2025 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 0ECA8C83F1B for ; Mon, 28 Aug 2023 18:44:50 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S233139AbjH1So2 (ORCPT ); Mon, 28 Aug 2023 14:44:28 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:33190 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S233125AbjH1SoH (ORCPT ); Mon, 28 Aug 2023 14:44:07 -0400 Received: from mail-ot1-x330.google.com (mail-ot1-x330.google.com [IPv6:2607:f8b0:4864:20::330]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 64612B3 for ; Mon, 28 Aug 2023 11:44:05 -0700 (PDT) Received: by mail-ot1-x330.google.com with SMTP id 46e09a7af769-6bd0c953fd9so2395783a34.3 for ; Mon, 28 Aug 2023 11:44:05 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20221208; t=1693248244; x=1693853044; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=H/Y8i6gIDTHVwj3Z5niTajyyTF4DBIPiiGSuA7TZ+wQ=; b=K8G2e9KfnaqVbMn1Jelcp12cieSMO7xTNCXcGKOzt8PCmMbD4md099MNbUdW8DbRVU rmqAW16qU126oFQ9fXVv0EWDAmvyu2bvChMWuZsfPfFZ3z+QXgTw9fNOfnY9JwJYu95E cjQKG3/jF9UASdS1h0dgzVxx4vvkf0AUEanV73ArdyjIs+8e0Le1isANXDtQMWOfuB4i fcWIh7u6FNWRckMZ28sknrPgaJKh1mK9pSdV8HdsRSrcFdWB8NZBCb1YX/5RQKAiNlQv EwpjLW0yCPSdNZutQOBvDLRMpIL1OC8YIRkAyzjLboD7pyqM7qFT+N8GP0uQ71t8KIHO TwQw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1693248244; x=1693853044; 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:message-id:reply-to; bh=H/Y8i6gIDTHVwj3Z5niTajyyTF4DBIPiiGSuA7TZ+wQ=; b=fxdeyZfM014lh2BadbIzM+GO9hIOloj7Im1DIUgLYeVJH7XU98DqreZo31Q7GlxyRT Sx5odsTKpYn/xQmd+4ALfP28Y3OFwlpS/PUoioc7+psimrr9UMyoqyRopb9vUG1mhm25 01uoKMLbTOeeGtnxKthhzyrUkliSdsDYnIU8FVal6Ga5WX6MSlzTAhB1FclSGZxig0RM 4Ankok1NJBzLOhQ10QZ8w/HmHjaDxidpwl8smSxYhlocH+oLbdZXYO4miS0iyVE1nqEp Flz2ASkWZDf1Zbow9/NWCfeDuOQYPpwpWvejxjRSjXjrcgc5zxGAGcvvk4ISYaczF7/x rQpQ== X-Gm-Message-State: AOJu0Yx5UGUwUROZmvxUiHMf4MAxP1FW79YKY4Hceuv2vHeoq1RelTi6 Way70POfmLyDIM1deJdDXl4pjhBDzGw= X-Google-Smtp-Source: AGHT+IHz3qRzaYR2hOVsuV3+n7ed6OCxVXp9nXdCDYDHjFXkPaxQkg5VfbWLNbMHRjB/aX4C6fF9sw== X-Received: by 2002:a9d:5e8b:0:b0:6b9:4516:7d1e with SMTP id f11-20020a9d5e8b000000b006b945167d1emr13536044otl.30.1693248244227; Mon, 28 Aug 2023 11:44:04 -0700 (PDT) Received: from localhost ([2600:6c5e:2a00:5805:e348:56d4:5da8:636d]) by smtp.gmail.com with ESMTPSA id n15-20020a9d4d0f000000b006b94a14b52asm3729568otf.9.2023.08.28.11.44.03 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 28 Aug 2023 11:44:03 -0700 (PDT) From: Yury Norov To: linux-kernel@vger.kernel.org Cc: Yury Norov , Andy Shevchenko , Rasmus Villemoes Subject: [PATCH 05/12] bitmap: update comment for bitmap_{bit,}remap() Date: Mon, 28 Aug 2023 11:43:45 -0700 Message-Id: <20230828184353.5145-6-yury.norov@gmail.com> X-Mailer: git-send-email 2.39.2 In-Reply-To: <20230828184353.5145-1-yury.norov@gmail.com> References: <20230828184353.5145-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 an illustrated example for bitmap_remap(), and drop duplicated wording in bitmap_bitremap(). This exact example is tested in lib/test_bitmap. Signed-off-by: Yury Norov --- lib/bitmap.c | 54 +++++++++++++++++++++++++--------------------------- 1 file changed, 26 insertions(+), 28 deletions(-) diff --git a/lib/bitmap.c b/lib/bitmap.c index 65c64911c92f..30c375bffe8b 100644 --- a/lib/bitmap.c +++ b/lib/bitmap.c @@ -1002,10 +1002,30 @@ static int bitmap_pos_to_ord(const unsigned long *b= uf, unsigned int pos, unsigne * * Let @old and @new define a mapping of bit positions, such that * whatever position is held by the n-th set bit in @old is mapped - * to the n-th set bit in @new. In the more general case, allowing - * for the possibility that the weight 'w' of @new is less than the - * weight of @old, map the position of the n-th set bit in @old to - * the position of the m-th set bit in @new, where m =3D=3D n % w. + * to the n-th set bit in @new. For example lets say that @old has + * bits 2 through 4 set, and @new has bits 3 through 5 set: + * + * old: 00011100 + * |||///|| + * new: 00111000 + * + * This defines the mapping of bit position 2 to 3, 3 to 4 and 4 to 5, + * and of all other bit positions unchanged. So if say @src comes into + * this routine with bits 1, 3 and 5 set, then @dst should leave with + * bits 1, 4 and 5 set: + * + * src: 00101010 + * v v v + * old: 00011100 + * |||///|| + * new: 00111000 + * vv v + * dst: 00110010 + * + * In the more general case, allowing for the possibility that the weight + * 'w' of @new is less than the weight of @old, map the position of the + * n-th set bit in @old to the position of the m-th set bit in @new, where + * m =3D=3D n % w. * * If either of the @old and @new bitmaps are empty, or if @src and * @dst point to the same location, then this routine copies @src @@ -1016,13 +1036,6 @@ static int bitmap_pos_to_ord(const unsigned long *bu= f, unsigned int pos, unsigne * * Apply the above specified mapping to @src, placing the result in * @dst, clearing any bits previously set in @dst. - * - * For example, lets say that @old has bits 4 through 7 set, and - * @new has bits 12 through 15 set. This defines the mapping of bit - * position 4 to 12, 5 to 13, 6 to 14 and 7 to 15, and of all other - * bit positions unchanged. So if say @src comes into this routine - * with bits 1, 5 and 7 set, then @dst should leave with bits 1, - * 13 and 15 set. */ void bitmap_remap(unsigned long *dst, const unsigned long *src, const unsigned long *old, const unsigned long *new, @@ -1053,24 +1066,9 @@ EXPORT_SYMBOL(bitmap_remap); * @new: defines range of map * @bits: number of bits in each of these bitmaps * - * Let @old and @new define a mapping of bit positions, such that - * whatever position is held by the n-th set bit in @old is mapped - * to the n-th set bit in @new. In the more general case, allowing - * for the possibility that the weight 'w' of @new is less than the - * weight of @old, map the position of the n-th set bit in @old to - * the position of the m-th set bit in @new, where m =3D=3D n % w. - * - * The positions of unset bits in @old are mapped to themselves - * (the identity map). - * - * Apply the above specified mapping to bit position @oldbit, returning - * the new bit position. + * A special case of bitmap_remap(), when a single bit remapping is needed. * - * For example, lets say that @old has bits 4 through 7 set, and - * @new has bits 12 through 15 set. This defines the mapping of bit - * position 4 to 12, 5 to 13, 6 to 14 and 7 to 15, and of all other - * bit positions unchanged. So if say @oldbit is 5, then this routine - * returns 13. + * Returns: position of remapped bit */ int bitmap_bitremap(int oldbit, const unsigned long *old, const unsigned long *new, int bits) --=20 2.39.2 From nobody Tue Dec 16 11:04:45 2025 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 21360C83F1E for ; Mon, 28 Aug 2023 18:44:50 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S233145AbjH1So3 (ORCPT ); Mon, 28 Aug 2023 14:44:29 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:33202 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S233126AbjH1SoJ (ORCPT ); Mon, 28 Aug 2023 14:44:09 -0400 Received: from mail-oi1-x232.google.com (mail-oi1-x232.google.com [IPv6:2607:f8b0:4864:20::232]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id E3417B0 for ; Mon, 28 Aug 2023 11:44:06 -0700 (PDT) Received: by mail-oi1-x232.google.com with SMTP id 5614622812f47-3a36b52b4a4so1932224b6e.1 for ; Mon, 28 Aug 2023 11:44:06 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20221208; t=1693248245; x=1693853045; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=ILiXnngfnpSXcy8/UYRmE0PAU6XZ+LgZEWRToIxyalw=; b=sevmt5hHeWtnfIgvXbsYIXsPTHGIFOGCYwBF3DlxQ7XwZ4rBsmGuAAiW6DGpJd9Qco LdmhRA5IMU0sEHBm8BY9G+AXw1J/FCXUwqzdBLSabbri+iJ5V0caSNkG7ThuTQ99+msS a5KzQntqxOnVH+vd4Rxqr+Pg6oNeoEbdyrAqelAHd/OInbsXD9bcyTc4137aqOhb3s86 Wyr9zks/yVTIUkiblCf7OnFmNS6lpkxLEE0AHVlncXMr7aSz1DBbHR/XsOM0UkKuDgqz 2YLKnjT0LDx55rR/qOk2KZYP5HYlOf9JBhj0MVHpoE/ET695FbhpOS1Ghr9xZkr1euZE wyXQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1693248245; x=1693853045; 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:message-id:reply-to; bh=ILiXnngfnpSXcy8/UYRmE0PAU6XZ+LgZEWRToIxyalw=; b=cvOg8Nj40saZxWAca41RRznu1XFDE0CSWkrvUrIAskqayHfnBybt9Hfo88GUFUHDCL i4I8fM8C1WcavPyUZ46OF/lpJVZgpdnXce3dOg2jJ5MxaZyha6NmAaw5YUrRRllGwtP8 xNI9/2i30GqAb80pvb+8ylaWwu8RIenlh87qmGH7mCCt7y3L/1luAx7OMhlrJjiPjiDS Y76vxyicbY6t189W1bteceQCIuJ9Pt53vKIxSkO86sJBot7ZobAxMl3i3+A1yRHsIwel 7yugAiKgDEuBRCqiKuKx0SiUCAQm5/rk7r/QlKhkWFfjyU/PKA1SPW6HFwzk6CEaIhfe mx2Q== X-Gm-Message-State: AOJu0YwKd+CdKCvy/kr138P2Tsmuj/jOvhr1bKutxK+AOt/YnVKNS/jy nJwWh9xdMp3tdcdbVGr+iQL1f1BKct4= X-Google-Smtp-Source: AGHT+IH00igx/EL9+HVJ5wdZmo53lXN84sIekHslWeQ90jsoEQGMJaHGB2BdYwntULBa5VPUm/2Y6Q== X-Received: by 2002:a05:6808:13c1:b0:3a7:551c:a863 with SMTP id d1-20020a05680813c100b003a7551ca863mr342141oiw.10.1693248245633; Mon, 28 Aug 2023 11:44:05 -0700 (PDT) Received: from localhost ([2600:6c5e:2a00:5805:e348:56d4:5da8:636d]) by smtp.gmail.com with ESMTPSA id bl3-20020a056808308300b003a7a422cb6asm3684705oib.37.2023.08.28.11.44.04 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 28 Aug 2023 11:44:05 -0700 (PDT) From: Yury Norov To: linux-kernel@vger.kernel.org Cc: Yury Norov , Andy Shevchenko , Rasmus Villemoes Subject: [PATCH 06/12] bitmap: add small_cont_nbits() optimization for bitmap_remap() Date: Mon, 28 Aug 2023 11:43:46 -0700 Message-Id: <20230828184353.5145-7-yury.norov@gmail.com> X-Mailer: git-send-email 2.39.2 In-Reply-To: <20230828184353.5145-1-yury.norov@gmail.com> References: <20230828184353.5145-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" When nbits is less than BITS_PER_LONG, we can handle trivial cases inline. Signed-off-by: Yury Norov --- include/linux/bitmap.h | 66 ++++++++++++++++++++++++++++++++++++++++-- lib/bitmap.c | 49 ++----------------------------- 2 files changed, 66 insertions(+), 49 deletions(-) diff --git a/include/linux/bitmap.h b/include/linux/bitmap.h index 6acbdd2abd0c..486451b80339 100644 --- a/include/linux/bitmap.h +++ b/include/linux/bitmap.h @@ -161,6 +161,8 @@ bool __bitmap_andnot(unsigned long *dst, const unsigned= long *bitmap1, void __bitmap_replace(unsigned long *dst, const unsigned long *old, const unsigned long *new, const unsigned long *mask, unsigned int nbits); +void __bitmap_remap(unsigned long *dst, const unsigned long *src, + const unsigned long *old, const unsigned long *new, unsigned int nbits); bool __bitmap_intersects(const unsigned long *bitmap1, const unsigned long *bitmap2, unsigned int nbits); bool __bitmap_subset(const unsigned long *bitmap1, @@ -211,8 +213,7 @@ int bitmap_parselist(const char *buf, unsigned long *ma= skp, int nmaskbits); int bitmap_parselist_user(const char __user *ubuf, unsigned int ulen, unsigned long *dst, int nbits); -void bitmap_remap(unsigned long *dst, const unsigned long *src, - const unsigned long *old, const unsigned long *new, unsigned int nbits); + int bitmap_bitremap(int oldbit, const unsigned long *old, const unsigned long *new, int bits); void bitmap_onto(unsigned long *dst, const unsigned long *orig, @@ -671,6 +672,67 @@ static inline int bitmap_find_free_region(unsigned lon= g *bitmap, unsigned int bi return -ENOMEM; } =20 +/** + * bitmap_remap - Apply map defined by a pair of bitmaps to another bitmap + * @dst: remapped result + * @src: subset to be remapped + * @old: defines domain of map + * @new: defines range of map + * @nbits: number of bits in each of these bitmaps + * + * Let @old and @new define a mapping of bit positions, such that + * whatever position is held by the n-th set bit in @old is mapped + * to the n-th set bit in @new. For example lets say that @old has + * bits 2 through 4 set, and @new has bits 3 through 5 set: + * + * old: 00011100 + * |||///|| + * new: 00111000 + * + * This defines the mapping of bit position 2 to 3, 3 to 4 and 4 to 5, + * and of all other bit positions unchanged. So if say @src comes into + * this routine with bits 1, 3 and 5 set, then @dst should leave with + * bits 1, 4 and 5 set: + * + * src: 00101010 + * v v v + * old: 00011100 + * |||///|| + * new: 00111000 + * vv v + * dst: 00110010 + * + * In the more general case, allowing for the possibility that the weight + * 'w' of @new is less than the weight of @old, map the position of the + * n-th set bit in @old to the position of the m-th set bit in @new, where + * m =3D=3D n % w. + * + * If either of the @old and @new bitmaps are empty, or if @src and + * @dst point to the same location, then this routine copies @src + * to @dst. + * + * The positions of unset bits in @old are mapped to themselves + * (the identity map). + * + * Apply the above specified mapping to @src, placing the result in + * @dst, clearing any bits previously set in @dst. + */ +static inline void bitmap_remap(unsigned long *dst, const unsigned long *s= rc, + const unsigned long *old, const unsigned long *new, unsigned int nbits) +{ + if (small_const_nbits(nbits)) { + if ((*src & BITMAP_LAST_WORD_MASK(nbits)) =3D=3D 0 || + (*old & BITMAP_LAST_WORD_MASK(nbits)) =3D=3D 0 || + (*new & BITMAP_LAST_WORD_MASK(nbits)) =3D=3D 0 || + ((*new ^ *old) & BITMAP_LAST_WORD_MASK(nbits)) =3D=3D 0) { + *dst =3D *src & BITMAP_LAST_WORD_MASK(nbits); + return; + } + } + + __bitmap_remap(dst, src, old, new, nbits); +} + #endif /* __ASSEMBLY__ */ =20 #endif /* __LINUX_BITMAP_H */ diff --git a/lib/bitmap.c b/lib/bitmap.c index 30c375bffe8b..2ac48d9bcbc0 100644 --- a/lib/bitmap.c +++ b/lib/bitmap.c @@ -992,52 +992,7 @@ static int bitmap_pos_to_ord(const unsigned long *buf,= unsigned int pos, unsigne return bitmap_weight(buf, pos); } =20 -/** - * bitmap_remap - Apply map defined by a pair of bitmaps to another bitmap - * @dst: remapped result - * @src: subset to be remapped - * @old: defines domain of map - * @new: defines range of map - * @nbits: number of bits in each of these bitmaps - * - * Let @old and @new define a mapping of bit positions, such that - * whatever position is held by the n-th set bit in @old is mapped - * to the n-th set bit in @new. For example lets say that @old has - * bits 2 through 4 set, and @new has bits 3 through 5 set: - * - * old: 00011100 - * |||///|| - * new: 00111000 - * - * This defines the mapping of bit position 2 to 3, 3 to 4 and 4 to 5, - * and of all other bit positions unchanged. So if say @src comes into - * this routine with bits 1, 3 and 5 set, then @dst should leave with - * bits 1, 4 and 5 set: - * - * src: 00101010 - * v v v - * old: 00011100 - * |||///|| - * new: 00111000 - * vv v - * dst: 00110010 - * - * In the more general case, allowing for the possibility that the weight - * 'w' of @new is less than the weight of @old, map the position of the - * n-th set bit in @old to the position of the m-th set bit in @new, where - * m =3D=3D n % w. - * - * If either of the @old and @new bitmaps are empty, or if @src and - * @dst point to the same location, then this routine copies @src - * to @dst. - * - * The positions of unset bits in @old are mapped to themselves - * (the identity map). - * - * Apply the above specified mapping to @src, placing the result in - * @dst, clearing any bits previously set in @dst. - */ -void bitmap_remap(unsigned long *dst, const unsigned long *src, +void __bitmap_remap(unsigned long *dst, const unsigned long *src, const unsigned long *old, const unsigned long *new, unsigned int nbits) { @@ -1057,7 +1012,7 @@ void bitmap_remap(unsigned long *dst, const unsigned = long *src, set_bit(find_nth_bit(new, nbits, n % w), dst); } } -EXPORT_SYMBOL(bitmap_remap); +EXPORT_SYMBOL(__bitmap_remap); =20 /** * bitmap_bitremap - Apply map defined by a pair of bitmaps to a single bit --=20 2.39.2 From nobody Tue Dec 16 11:04:45 2025 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 33D0FC83F1D for ; Mon, 28 Aug 2023 18:44:50 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S233153AbjH1Soa (ORCPT ); Mon, 28 Aug 2023 14:44:30 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:33206 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S233127AbjH1SoL (ORCPT ); Mon, 28 Aug 2023 14:44:11 -0400 Received: from mail-oa1-x2d.google.com (mail-oa1-x2d.google.com [IPv6:2001:4860:4864:20::2d]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 23524B3 for ; Mon, 28 Aug 2023 11:44:08 -0700 (PDT) Received: by mail-oa1-x2d.google.com with SMTP id 586e51a60fabf-1c4de3b9072so2547124fac.3 for ; Mon, 28 Aug 2023 11:44:08 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20221208; t=1693248247; x=1693853047; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=BO9WTCDSdetqwfC+adFwBkJ/NQLbVLN7w9OB2nLu2Hc=; b=DLek+L8gCTU0hMcedn9UA3/i0XY1QAITS45X6Ot7ZMKcvuRbZBrW7ljoLCAHxQe9CD +ZwSVm1AL50qjt59vQUPGZYruGPhk5OCcTLPUtC9bW7p+JzPRGzWT7xM7TZoY0OXysVx XTVPO16r+Az/KqypLw76ul0WyY025xuBzI14JhiAzFWCrYhs5v8ffIJhtHBLPhwG4wGO SUJY1lRdvfno2LLT3R+qjiOnrdNiNdd5o8oNvp/8Nu5j4unEQqdVGtDABfWr47ICQOAw jAn2ePCpVYCnPpYYpqBdSlv6PXD2acut/gzda4+7O2ziB0CiDhQX4mUJ+az3GuEbtjC8 pEcg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1693248247; x=1693853047; 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:message-id:reply-to; bh=BO9WTCDSdetqwfC+adFwBkJ/NQLbVLN7w9OB2nLu2Hc=; b=j5HUrEZ53FjaX7YZ16MscGVWHwG/dfHWmbLYo27O/zX0eYqW1KCM7kRQHBmatuO2Kc Up1O1PVdyy/trpK9z8BS0lgIBauwkEHZ6C8bWkZ5A2b1V++fJIu4gxeQCEtSq4Eh9hgx 5agmxgszZYyJQMBV0RsiwOSdXr0yqL+0K3uAErVIhXyzSu/IJedsnMBZ8Yf6LZnvinx3 /H4qEYIR1KdxYuGLtgfDB07sFidIrwFqEp9I8rST2Bur71xxBib3PArBwB5Avu7RLB2D U9m5+zOhLsXMz5W+YkxhWFZYgpbcJh8VVkGyDDWdd9V8Rt2XNdUHdQrQtYq3+r3PiWSk 3C1Q== X-Gm-Message-State: AOJu0YzUZFDpgfPZ7ciNU5vtsudvZIQx7M70xL9d2Gj40h6rOCVvx1dA uw09yyJIyWiK4Ei8QRoMqgB+FyExQjM= X-Google-Smtp-Source: AGHT+IE/G/wNcyY5+i7oSoidqwFqCa9RNOmaz8F0+1Vn3Ze2ATe1jqHhSeiQH5EYSLzeDuC0fcxjjw== X-Received: by 2002:a05:6870:414d:b0:1bf:32bf:1913 with SMTP id r13-20020a056870414d00b001bf32bf1913mr11968205oad.43.1693248247059; Mon, 28 Aug 2023 11:44:07 -0700 (PDT) Received: from localhost ([2600:6c5e:2a00:5805:e348:56d4:5da8:636d]) by smtp.gmail.com with ESMTPSA id 67-20020a4a1446000000b005660ff9e037sm4321624ood.25.2023.08.28.11.44.06 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 28 Aug 2023 11:44:06 -0700 (PDT) From: Yury Norov To: linux-kernel@vger.kernel.org Cc: Yury Norov , Andy Shevchenko , Rasmus Villemoes Subject: [PATCH 07/12] bitmap: add small_const_nbits() optimization for bitmap_bitremap() Date: Mon, 28 Aug 2023 11:43:47 -0700 Message-Id: <20230828184353.5145-8-yury.norov@gmail.com> X-Mailer: git-send-email 2.39.2 In-Reply-To: <20230828184353.5145-1-yury.norov@gmail.com> References: <20230828184353.5145-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" When 'bits' is less than BITS_PER_LONG, we can remap a bit inline. Signed-off-by: Yury Norov --- include/linux/bitmap.h | 36 ++++++++++++++++++++++++++++++++++-- lib/bitmap.c | 15 ++------------- 2 files changed, 36 insertions(+), 15 deletions(-) diff --git a/include/linux/bitmap.h b/include/linux/bitmap.h index 486451b80339..da5030a99af5 100644 --- a/include/linux/bitmap.h +++ b/include/linux/bitmap.h @@ -163,6 +163,8 @@ void __bitmap_replace(unsigned long *dst, const unsigned long *mask, unsigned int nbits); void __bitmap_remap(unsigned long *dst, const unsigned long *src, const unsigned long *old, const unsigned long *new, unsigned int nbits); +int __bitmap_bitremap(int oldbit, + const unsigned long *old, const unsigned long *new, int nbits); bool __bitmap_intersects(const unsigned long *bitmap1, const unsigned long *bitmap2, unsigned int nbits); bool __bitmap_subset(const unsigned long *bitmap1, @@ -214,8 +216,6 @@ int bitmap_parselist(const char *buf, unsigned long *ma= skp, int bitmap_parselist_user(const char __user *ubuf, unsigned int ulen, unsigned long *dst, int nbits); =20 -int bitmap_bitremap(int oldbit, - const unsigned long *old, const unsigned long *new, int bits); void bitmap_onto(unsigned long *dst, const unsigned long *orig, const unsigned long *relmap, unsigned int bits); void bitmap_fold(unsigned long *dst, const unsigned long *orig, @@ -733,6 +733,38 @@ static inline void bitmap_remap(unsigned long *dst, co= nst unsigned long *src, __bitmap_remap(dst, src, old, new, nbits); } =20 +/** + * bitmap_bitremap - Apply map defined by a pair of bitmaps to a single bit + * @oldbit: bit position to be mapped + * @old: defines domain of map + * @new: defines range of map + * @nbits: number of bits in each of these bitmaps + * + * A special case of bitmap_remap(), when a single bit remapping is needed. + * + * Returns: position of remapped bit + */ +static inline int bitmap_bitremap(int oldbit, + const unsigned long *old, const unsigned long *new, int nbits) +{ + if (small_const_nbits(nbits)) { + unsigned int w, n; + + if ((*old & BIT(oldbit)) =3D=3D 0 || + (*old & BITMAP_LAST_WORD_MASK(nbits)) =3D=3D 0 || + (*new & BITMAP_LAST_WORD_MASK(nbits)) =3D=3D 0 || + ((*new ^ *old) & BITMAP_LAST_WORD_MASK(nbits)) =3D=3D 0) { + return oldbit; + } + + w =3D bitmap_weight(new, nbits); + n =3D bitmap_weight(old, oldbit); + return find_nth_bit(new, nbits, n % w); + } + + return __bitmap_bitremap(oldbit, old, new, nbits); +} + #endif /* __ASSEMBLY__ */ =20 #endif /* __LINUX_BITMAP_H */ diff --git a/lib/bitmap.c b/lib/bitmap.c index 2ac48d9bcbc0..9ecdc74cb6b4 100644 --- a/lib/bitmap.c +++ b/lib/bitmap.c @@ -1014,18 +1014,7 @@ void __bitmap_remap(unsigned long *dst, const unsign= ed long *src, } EXPORT_SYMBOL(__bitmap_remap); =20 -/** - * bitmap_bitremap - Apply map defined by a pair of bitmaps to a single bit - * @oldbit: bit position to be mapped - * @old: defines domain of map - * @new: defines range of map - * @bits: number of bits in each of these bitmaps - * - * A special case of bitmap_remap(), when a single bit remapping is needed. - * - * Returns: position of remapped bit - */ -int bitmap_bitremap(int oldbit, const unsigned long *old, +int __bitmap_bitremap(int oldbit, const unsigned long *old, const unsigned long *new, int bits) { int w =3D bitmap_weight(new, bits); @@ -1035,7 +1024,7 @@ int bitmap_bitremap(int oldbit, const unsigned long *= old, else return find_nth_bit(new, bits, n % w); } -EXPORT_SYMBOL(bitmap_bitremap); +EXPORT_SYMBOL(__bitmap_bitremap); =20 #ifdef CONFIG_NUMA /** --=20 2.39.2 From nobody Tue Dec 16 11:04:45 2025 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 445A7C83F20 for ; Mon, 28 Aug 2023 18:44:50 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S233159AbjH1Sob (ORCPT ); Mon, 28 Aug 2023 14:44:31 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:42028 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S233128AbjH1SoL (ORCPT ); Mon, 28 Aug 2023 14:44:11 -0400 Received: from mail-oi1-x236.google.com (mail-oi1-x236.google.com [IPv6:2607:f8b0:4864:20::236]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id AC453B0 for ; Mon, 28 Aug 2023 11:44:09 -0700 (PDT) Received: by mail-oi1-x236.google.com with SMTP id 5614622812f47-3a85c5854deso2729443b6e.0 for ; Mon, 28 Aug 2023 11:44:09 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20221208; t=1693248248; x=1693853048; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=FplpJ0L1Cq8kvgNUXqiEcC7mn8MGISXoZpv2LNEhVNE=; b=h6EDvUKvuWejmDg99fRjBjUEH/qunGXcHME78wbCR1Gd+mkDGTdoSY+d2N+sR6qjF+ wYO5rDkOPGj7TgB/Q4slKLQeEiqhfzq8qVjXvy5RIHd/Rq4POP1Xr3fZvf7ZznTtN8ev wxy3hfsZesm9Fxf05AuBSdqobFG1q1bN7AF4eGkb5oVf2U6h1hkRhLh48EBEse+Vs5Yu BneIpKJCGjXfDBXEDUafhBuid5ZoD7BF+hV70g+OM/EjeP/HVhOtV6vr75PvHCYquZE4 NckgRs01jycoNN+j7Umz6lxHqxSBeuxTTs8d4OgzdBNP7a2Bq//PzU00pxs8ffqcKvBY zFQQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1693248248; x=1693853048; 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:message-id:reply-to; bh=FplpJ0L1Cq8kvgNUXqiEcC7mn8MGISXoZpv2LNEhVNE=; b=eDsadepfSU1+SoT+d+YZFw1XCzhLOBgyh5gZCb8VrV6BtTtPOUn1ot2pQUQZk9WCb/ kSix3JOhD9dwD4OgH08Aqnc4eVzKrm+E8ICRfYRQA6w+GaIvuzknqztly8hMApu8WlAX IeE1WXWVwiqGztlV7eC26luyAO8Df4JOoJ13bp7NkA4H6i2ApIsKh112gzdH/1kg3Kkh hqbW2n9etGf/kOqUpoy3R93lvfINorenTY+NMdI3oVs/TnFvtm8SoAaPLuNpaYmOOvZ1 X/AbFhPImchJcQ/B+U+Wd0JoJxDJov3TgsytBVIwJ3S5j1tva0AX8IH9td5QpqBMSbyY bkgQ== X-Gm-Message-State: AOJu0YzcEvEz5agQAtxnS8kpO2rnbDRtsL6fW8f1RzW3/sZ2NMrPgf7P Pm+WCGhFirbzt6AiKIwKB2RL+sWqPQY= X-Google-Smtp-Source: AGHT+IEc12Sb51t2ikk7rn8SmMMeW5zZ1FvoL1/UoKx8dCxm2HMcoYk3C3K/NxcfEZFA913lskPYsw== X-Received: by 2002:a05:6808:d46:b0:3a8:8ea9:62de with SMTP id w6-20020a0568080d4600b003a88ea962demr12349285oik.39.1693248248606; Mon, 28 Aug 2023 11:44:08 -0700 (PDT) Received: from localhost ([2600:6c5e:2a00:5805:e348:56d4:5da8:636d]) by smtp.gmail.com with ESMTPSA id n29-20020a0568080a1d00b003a782e88fd9sm3648806oij.58.2023.08.28.11.44.07 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 28 Aug 2023 11:44:08 -0700 (PDT) From: Yury Norov To: linux-kernel@vger.kernel.org Cc: Yury Norov , Andy Shevchenko , Rasmus Villemoes Subject: [PATCH 08/12] bitmap: optiimze bitmap_bitremap() Date: Mon, 28 Aug 2023 11:43:48 -0700 Message-Id: <20230828184353.5145-9-yury.norov@gmail.com> X-Mailer: git-send-email 2.39.2 In-Reply-To: <20230828184353.5145-1-yury.norov@gmail.com> References: <20230828184353.5145-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" When 'new' map is empty, we can skip remapping entirely and return the old bit. Signed-off-by: Yury Norov --- lib/bitmap.c | 15 ++++++++++----- 1 file changed, 10 insertions(+), 5 deletions(-) diff --git a/lib/bitmap.c b/lib/bitmap.c index 9ecdc74cb6b4..2e8deeb8bf99 100644 --- a/lib/bitmap.c +++ b/lib/bitmap.c @@ -1017,12 +1017,17 @@ EXPORT_SYMBOL(__bitmap_remap); int __bitmap_bitremap(int oldbit, const unsigned long *old, const unsigned long *new, int bits) { - int w =3D bitmap_weight(new, bits); - int n =3D bitmap_pos_to_ord(old, oldbit, bits); - if (n < 0 || w =3D=3D 0) + int w, n; + + w =3D bitmap_weight(new, bits); + if (w =3D=3D 0) + return oldbit; + + n =3D bitmap_pos_to_ord(old, oldbit, bits); + if (n < 0) return oldbit; - else - return find_nth_bit(new, bits, n % w); + + return find_nth_bit(new, bits, n % w); } EXPORT_SYMBOL(__bitmap_bitremap); =20 --=20 2.39.2 From nobody Tue Dec 16 11:04:45 2025 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 7D428C83F22 for ; Mon, 28 Aug 2023 18:44:50 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S233172AbjH1Sod (ORCPT ); Mon, 28 Aug 2023 14:44:33 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:42034 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S233129AbjH1SoN (ORCPT ); Mon, 28 Aug 2023 14:44:13 -0400 Received: from mail-oi1-x231.google.com (mail-oi1-x231.google.com [IPv6:2607:f8b0:4864:20::231]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id F3906B0 for ; Mon, 28 Aug 2023 11:44:10 -0700 (PDT) Received: by mail-oi1-x231.google.com with SMTP id 5614622812f47-3a9b41ffe11so2266637b6e.2 for ; Mon, 28 Aug 2023 11:44:10 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20221208; t=1693248250; x=1693853050; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=CnoQbut+iRr5Ecn/zMIRssht6/ZOy4Q1oQlXOYB7XO0=; b=dQ+F8L5Rowmceo7LsbHVTb1oJP/Tcjc7KTaEEoFCaFgoc8fNS1O9exo3p9506uaM3h 8iqqaQT2hQRk6B9OaAXV/0KnTzEGO34BcW88F8DjKIPLtI82SH2IhJzDn7gcgnHdh8GF Xe29FEO5Sf+n6ZVRUn05y8Ts26LvoTcsM3XK6hmpSwHuwrO4KREhL2gskb7UYY4A30Fo KKqX06GNYHXKV60eAHzq0C8X/9oWV5ReBQmMfF9OBZrWnLI3tmftoLlNIxn29Yk88/pz FYbKcHBp65RCR/GYhG9ThVNvfwZEb9iIs0l3c34SnxYSrOR+BIGCz86w7oyTv9yLLlDn a97A== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1693248250; x=1693853050; 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:message-id:reply-to; bh=CnoQbut+iRr5Ecn/zMIRssht6/ZOy4Q1oQlXOYB7XO0=; b=BhA8AURh7qa36mrNYrtQXg24kr30RJB86cNbJw2FNQURrgQrGdaltG6PF/zsIlS5Ec RkEJx8YtWhkaceYTC07JPqtWKchkuy8522PWPe6abNpa7Tk5AuqzE4VdXBTB2YWjA4Ms Yf5L8KdlgplrFWKlZcvO6cPVbIJkUXUhF65MZ7MOSuvpNgxVb0AD6Av7j/Y8EOaeqPdZ 8BCmzvYGn1UaC95i6N0OD3xLds/LRh0UytMvxK/E8rFGVc/8qZxX5NXgxnIsqL0rNHuG S/sHqnqag39NWIVmwbGvcesImdYeUOYDbz0v1Q/StjUr7NZww8lEg/CghRlyww3Z4RNJ CQnA== X-Gm-Message-State: AOJu0YwekmhoSgiUJ6EGuJ00TQjP7zpkqpKK05YjuXBWWsel4SrV6oXJ 2sMDOLbo1YNkGRLhZr79AbW0aSrRzE8= X-Google-Smtp-Source: AGHT+IEF1lqE8sJJyME9qTNmswVJZye5gOfZFtFNcdfaHcv2c1AqnINQLRPIwWcNvJogG8wmZTHd6A== X-Received: by 2002:a54:4e8e:0:b0:3a8:80ea:f0c6 with SMTP id c14-20020a544e8e000000b003a880eaf0c6mr11563399oiy.29.1693248249960; Mon, 28 Aug 2023 11:44:09 -0700 (PDT) Received: from localhost ([2600:6c5e:2a00:5805:e348:56d4:5da8:636d]) by smtp.gmail.com with ESMTPSA id k24-20020a544698000000b003a9a2362f66sm2178336oic.16.2023.08.28.11.44.09 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 28 Aug 2023 11:44:09 -0700 (PDT) From: Yury Norov To: linux-kernel@vger.kernel.org Cc: Yury Norov , Andy Shevchenko , Rasmus Villemoes Subject: [PATCH 09/12] bitmap: optimize bitmap_remap() when 'new' is empty map Date: Mon, 28 Aug 2023 11:43:49 -0700 Message-Id: <20230828184353.5145-10-yury.norov@gmail.com> X-Mailer: git-send-email 2.39.2 In-Reply-To: <20230828184353.5145-1-yury.norov@gmail.com> References: <20230828184353.5145-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" When 'new' map is empty, we can skip remapping entirely and replace it with bitmap_copy(). Signed-off-by: Yury Norov --- lib/bitmap.c | 5 +++++ 1 file changed, 5 insertions(+) diff --git a/lib/bitmap.c b/lib/bitmap.c index 2e8deeb8bf99..50385d61e6ea 100644 --- a/lib/bitmap.c +++ b/lib/bitmap.c @@ -1003,6 +1003,11 @@ void __bitmap_remap(unsigned long *dst, const unsign= ed long *src, bitmap_zero(dst, nbits); =20 w =3D bitmap_weight(new, nbits); + if (w =3D=3D 0) { + bitmap_copy(dst, src, nbits); + return; + } + for_each_set_bit(oldbit, src, nbits) { int n =3D bitmap_pos_to_ord(old, oldbit, nbits); =20 --=20 2.39.2 From nobody Tue Dec 16 11:04:45 2025 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 303F8C83F14 for ; Mon, 28 Aug 2023 18:45:18 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S231588AbjH1Sot (ORCPT ); Mon, 28 Aug 2023 14:44:49 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:42048 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S233131AbjH1SoO (ORCPT ); Mon, 28 Aug 2023 14:44:14 -0400 Received: from mail-oa1-x30.google.com (mail-oa1-x30.google.com [IPv6:2001:4860:4864:20::30]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 8478CB0 for ; Mon, 28 Aug 2023 11:44:12 -0700 (PDT) Received: by mail-oa1-x30.google.com with SMTP id 586e51a60fabf-1c4d8eaa8ebso2581443fac.0 for ; Mon, 28 Aug 2023 11:44:12 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20221208; t=1693248251; x=1693853051; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=FgFnNChBwcTiKeUa47qLSJ3+y5tq48ar+mqpea6xw3o=; b=m+JJ9p9W5ZEw25kxIfUumOUfiBD2gSE1elhHLoYbAZtF4WzvKYMTDpvrp5lMeDq542 20XvSvtYU/sx+yl1YzFNOXJdby2OxCz133IS+H1XNQMpCb4+vV06B0K1sRNtpkMHHEVn Kolt4h8rauFNyZlCFtgUqSlIYU2KVCM+4fkLM6uENxcAgTIVLoZSOLq0sEUJDh1C7T+n x/+WstWv7EnHOiBP0Gum6f/Tc6qNUIAofXG+LChq06mFwcQp+M2H5oQIb0hIvb315GQd bTLTR6U/WGGh/DxxRMLuqogUv/f1h8xgmjNhh+U1iYVoevKjvYqrLjUKyhViMDu+Lq+G CEmA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1693248251; x=1693853051; 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:message-id:reply-to; bh=FgFnNChBwcTiKeUa47qLSJ3+y5tq48ar+mqpea6xw3o=; b=eETuoC4oaidjUrcYda+F77VW9mjxocHO5ukpuoug6zpI8+/2Ve0AsWFmcg54DOXvJ0 QNVGKRPfb0Fxg718xTg+mFCOvnHmVFen55l4zUpYMXhXIX5Eul3hAbhUcfdTUTKC71ok fquFFH/5crsWA4ebnhRIY43dN8gRcDFuXOlKup2qSWVvGAo4lZnR/uxQcqkR74rclgzw qblyqATYs/V5dwu/x58SNwqFf6No4vtQH6DKVbyMP1QIra4UAeWv5vLvgUO4zF2AapFQ JgaZ+oyclE64gzWEiWJbVBdwtld2plEfn8XtKSqoFDD8kowApCV0KlV36fbxO8MQhR6m 0eWA== X-Gm-Message-State: AOJu0Yyb8gw4dUJjNR/aeTY5anL15B934KmjY+ap+TZZCrAho07/6kQ5 uEjE3HwfttUfA2ok/C6dNUHPEgeUMS4= X-Google-Smtp-Source: AGHT+IFM0sXQ5G5lxLZ02JJZWjy/muQx+1MPzsLF8b0XlOH3jMR7cmqDtQIfae5SbOppmQUvH7M3JQ== X-Received: by 2002:a05:6870:1695:b0:1bb:c50d:7451 with SMTP id j21-20020a056870169500b001bbc50d7451mr13902536oae.46.1693248251417; Mon, 28 Aug 2023 11:44:11 -0700 (PDT) Received: from localhost ([2600:6c5e:2a00:5805:e348:56d4:5da8:636d]) by smtp.gmail.com with ESMTPSA id dt37-20020a0568705aa500b001c4fe8e78e1sm4595312oab.43.2023.08.28.11.44.10 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 28 Aug 2023 11:44:11 -0700 (PDT) From: Yury Norov To: linux-kernel@vger.kernel.org Cc: Yury Norov , Andy Shevchenko , Rasmus Villemoes Subject: [PATCH 10/12] bitmap: separate handling of identity and remapping parts in bitmap_remap() Date: Mon, 28 Aug 2023 11:43:50 -0700 Message-Id: <20230828184353.5145-11-yury.norov@gmail.com> X-Mailer: git-send-email 2.39.2 In-Reply-To: <20230828184353.5145-1-yury.norov@gmail.com> References: <20230828184353.5145-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" For unset bits in 'old' map (identity mapping), 'src' bits must be copied to 'dst'. Doing that separately from remapping in a for-loop has some advantages: - implicitly initialize 'dst' without calling bitmap_zero(); - optimize performance of handling identity parts, because per-word bitmap_andnot() is faster than per-bit set_bit() in a for-loop; - make inner part of the loop unconditional; - when 'old' map is empty, new logic simiply skips the for-loop part. While here, replace set_bit() with a non-atomic version, because the whole function is non-atomic anyways. If atomicity required, it should be handled by user. Signed-off-by: Yury Norov --- lib/bitmap.c | 15 +++++++-------- 1 file changed, 7 insertions(+), 8 deletions(-) diff --git a/lib/bitmap.c b/lib/bitmap.c index 50385d61e6ea..f62ea97e942c 100644 --- a/lib/bitmap.c +++ b/lib/bitmap.c @@ -996,11 +996,10 @@ void __bitmap_remap(unsigned long *dst, const unsigne= d long *src, const unsigned long *old, const unsigned long *new, unsigned int nbits) { - unsigned int oldbit, w; + unsigned int oldbit, w, n; =20 if (dst =3D=3D src) /* following doesn't handle inplace remaps */ return; - bitmap_zero(dst, nbits); =20 w =3D bitmap_weight(new, nbits); if (w =3D=3D 0) { @@ -1008,13 +1007,13 @@ void __bitmap_remap(unsigned long *dst, const unsig= ned long *src, return; } =20 - for_each_set_bit(oldbit, src, nbits) { - int n =3D bitmap_pos_to_ord(old, oldbit, nbits); + /* Identity part */ + bitmap_andnot(dst, src, old, nbits); =20 - if (n < 0 || w =3D=3D 0) - set_bit(oldbit, dst); /* identity map */ - else - set_bit(find_nth_bit(new, nbits, n % w), dst); + /* Remapping part */ + for_each_and_bit(oldbit, src, old, nbits) { + n =3D bitmap_weight(old, oldbit); + __set_bit(find_nth_bit(new, nbits, n % w), dst); } } EXPORT_SYMBOL(__bitmap_remap); --=20 2.39.2 From nobody Tue Dec 16 11:04:45 2025 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 6E0E2C71153 for ; Mon, 28 Aug 2023 18:45:18 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S233088AbjH1Sou (ORCPT ); Mon, 28 Aug 2023 14:44:50 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:42054 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S233074AbjH1SoQ (ORCPT ); Mon, 28 Aug 2023 14:44:16 -0400 Received: from mail-ot1-x32c.google.com (mail-ot1-x32c.google.com [IPv6:2607:f8b0:4864:20::32c]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id F092BB0 for ; Mon, 28 Aug 2023 11:44:13 -0700 (PDT) Received: by mail-ot1-x32c.google.com with SMTP id 46e09a7af769-6bca3588edbso2412600a34.0 for ; Mon, 28 Aug 2023 11:44:13 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20221208; t=1693248253; x=1693853053; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=6Xsr5nuLzGFxbxx1dxP1OouE4C2MjCJK6X4fU7S8Qbg=; b=MTBh2p4dZ2lSWT3AayKmfZTXiMSYGb+4LftonLa4Z5Yozn/ZasQ7MFI4sPMAV021hv 140IJmcvo23zt/UEn1G4fwZHFWhGMuFeV8rUjyfbHs3bee4rg3fZDE4KO2ALI6cy9t9a 9G9yc3/i+46l9srmjmQaIQoGZaKqWHJeQ5d0gTkkYXUCnDm/3NPxNr9YKULLEi2/pkZG m2JdL4TQ7OhQ/sW/aXae+ea+S/gNb8a1S/ryCQ4oGqoItilLoY237xMWEw0NyFdbYfmK SWLDIuaJ+X9r7yb9WEbk2CUGxOQ+3nZnNHdVzrtrQQW/AiOT4vuVQIV8A/w8jAIp0vaU 9fWA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1693248253; x=1693853053; 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:message-id:reply-to; bh=6Xsr5nuLzGFxbxx1dxP1OouE4C2MjCJK6X4fU7S8Qbg=; b=Om7pxYwjfe2Skjnf0w9GBKZI4+QE5b6oR0TD4BkkHvyH/CMYqFwCIPH4YTXdyAamUR /p9Ak7Y3T8s6gFcno7UfSiR0+teWAd6rguEbwecntWVLJzVBfOy5n+NOUDA6dtdYIzBd M5WqJf7GMOsHWb6JbybYE9zQqaHiOC58/YvV49NhdrsxV7mZzv76ASRFpMTchn7mnG4r L771QIChWw0QJYMw9vzIYNHqgl1wyFBmwRj9iTG2jsvJ7g58E1km7fglSpjrqRIL39Pw 1YwSQMgNHMHsl54oygfrfMNIvtBamNw8Spi1eXY9CmGhaWV+RDMDZ4Iy+McrUI0vvboD rgLw== X-Gm-Message-State: AOJu0YwXAN9tEjjtDaOYfkkdRP1OQ7lJrRXYnzpHzKqB/sA2L0rB0HIX cCQ8iA+SIrnT1xfMrDjHd6Ae87NGc9g= X-Google-Smtp-Source: AGHT+IGbHDCCFDLGLe2HLemq4m/efj7fH9wBMxKTtFu9ecDGYAAh2SYDEbmI/pyJsFAa05gVz9ZLmg== X-Received: by 2002:a05:6830:32aa:b0:6be:fb88:8352 with SMTP id m42-20020a05683032aa00b006befb888352mr5766080ott.8.1693248252838; Mon, 28 Aug 2023 11:44:12 -0700 (PDT) Received: from localhost ([2600:6c5e:2a00:5805:e348:56d4:5da8:636d]) by smtp.gmail.com with ESMTPSA id i6-20020a056830010600b006b4281cf424sm3719852otp.4.2023.08.28.11.44.12 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 28 Aug 2023 11:44:12 -0700 (PDT) From: Yury Norov To: linux-kernel@vger.kernel.org Cc: Yury Norov , Andy Shevchenko , Rasmus Villemoes Subject: [PATCH 11/12] bitmap: defer calculating weight of 'new' in bitmap_remap() Date: Mon, 28 Aug 2023 11:43:51 -0700 Message-Id: <20230828184353.5145-12-yury.norov@gmail.com> X-Mailer: git-send-email 2.39.2 In-Reply-To: <20230828184353.5145-1-yury.norov@gmail.com> References: <20230828184353.5145-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" When 'old' map is empty, we don't need to calculate weight of 'new' map, because all 'src' bits are simply copied to dst. Signed-off-by: Yury Norov --- lib/bitmap.c | 15 ++++++++------- 1 file changed, 8 insertions(+), 7 deletions(-) diff --git a/lib/bitmap.c b/lib/bitmap.c index f62ea97e942c..1fca60d54cb4 100644 --- a/lib/bitmap.c +++ b/lib/bitmap.c @@ -996,23 +996,24 @@ void __bitmap_remap(unsigned long *dst, const unsigne= d long *src, const unsigned long *old, const unsigned long *new, unsigned int nbits) { - unsigned int oldbit, w, n; + unsigned int oldbit, w =3D 0, n; =20 if (dst =3D=3D src) /* following doesn't handle inplace remaps */ return; =20 - w =3D bitmap_weight(new, nbits); - if (w =3D=3D 0) { - bitmap_copy(dst, src, nbits); - return; - } - /* Identity part */ bitmap_andnot(dst, src, old, nbits); =20 /* Remapping part */ for_each_and_bit(oldbit, src, old, nbits) { n =3D bitmap_weight(old, oldbit); + if (w =3D=3D 0) { /* if not initialized */ + w =3D bitmap_weight(new, nbits); + if (w =3D=3D 0) { /* if empty */ + bitmap_copy(dst, src, nbits); + return; + } + } __set_bit(find_nth_bit(new, nbits, n % w), dst); } } --=20 2.39.2 From nobody Tue Dec 16 11:04:45 2025 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 7ED11C83F18 for ; Mon, 28 Aug 2023 18:45:18 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S233167AbjH1Sow (ORCPT ); Mon, 28 Aug 2023 14:44:52 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:42080 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S233086AbjH1SoR (ORCPT ); Mon, 28 Aug 2023 14:44:17 -0400 Received: from mail-oa1-x31.google.com (mail-oa1-x31.google.com [IPv6:2001:4860:4864:20::31]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 6F2D9BF for ; Mon, 28 Aug 2023 11:44:15 -0700 (PDT) Received: by mail-oa1-x31.google.com with SMTP id 586e51a60fabf-1c4de3b9072so2547211fac.3 for ; Mon, 28 Aug 2023 11:44:15 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20221208; t=1693248254; x=1693853054; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=AKUxuuJmutnBiUjopAvOBtd5ZQokj0PqF2sT+wHUEVQ=; b=n8BPBVv5GFsq8sQpMbo/Bj2u/NuSLdg3NFz28E9l/HalTwX5Txv6n51n9G2Ilxht22 5jmopUurPiC8hxynJCovibqENympoNVbWmAvYH26FlUCIxImuACw8tMm9xEnbxfXx8UB 5bWP+/Iyr5Z39cjfJZV3ibvqPD998zHpw4lz1ALgUax2EHl2tL24tCh+sE7s+Ja34Q9q lMYNw68BkinRRYlPi3k7TaIqrfeZTC6EuTmG78NG2mirRe7q/yJsrGhbct1T39cQXsBg xwz7ByYR84jGW72ZGGaW4h66df/wWEfa0XJcosBqOXI34JM6f9DltpSj68uMa4uBjrNf H7wA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1693248254; x=1693853054; 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:message-id:reply-to; bh=AKUxuuJmutnBiUjopAvOBtd5ZQokj0PqF2sT+wHUEVQ=; b=gUxukYd6W7WjOTTSsuhVpqwMp7eKQh0I8GkINLCq+9hjZ+XNbpnOM+WYTP3CAIKmJw Zxryq6QXSy41jATRlHHTRAGGnWdYkm0MaWxxPYcLkc0Gm51gUvv+XV9KqfdAFlYXThLG WBrZrhZefiE3xZjul8y/2gvQuxZjYVrhJNloOsa6MRLT2LbGbxyIEEaNt8+VWoeLuC// 15fvCosCdaO6DBZr5aDvYF5yQpgdq3P7/teKY3Ak+dIP3tyZ+j1HdmBRA3DN3tgBle7I tkSODGQGpvgWGpKlr8xFA9/LflDlBc4tU2Nols2vcga/ie3yZzx1vXVg6RFBZ+N8l9fZ nUAw== X-Gm-Message-State: AOJu0YxT/L2oMWyaBjxXOcEpAEj/hvrwAFNIBdNVK2oxO0ODuObLS/Bz ijIRuc1PdT1UksNDKtNJyvRbM1Hd+Nk= X-Google-Smtp-Source: AGHT+IGe8SWO3Za8IRW6WMbijnpg3KbeBjZbb9ElTGnH8ThWF8oneko5wyqajSAeePfhNlSDRIs3yQ== X-Received: by 2002:a05:6870:7026:b0:1bf:74cc:c815 with SMTP id u38-20020a056870702600b001bf74ccc815mr12874668oae.19.1693248254332; Mon, 28 Aug 2023 11:44:14 -0700 (PDT) Received: from localhost ([2600:6c5e:2a00:5805:e348:56d4:5da8:636d]) by smtp.gmail.com with ESMTPSA id gy18-20020a056870289200b001c4b473581fsm4562420oab.12.2023.08.28.11.44.13 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 28 Aug 2023 11:44:14 -0700 (PDT) From: Yury Norov To: linux-kernel@vger.kernel.org Cc: Yury Norov , Andy Shevchenko , Rasmus Villemoes Subject: [PATCH 12/12] bitmap: don't count bits from the beginning in bitmap_remap() Date: Mon, 28 Aug 2023 11:43:52 -0700 Message-Id: <20230828184353.5145-13-yury.norov@gmail.com> X-Mailer: git-send-email 2.39.2 In-Reply-To: <20230828184353.5145-1-yury.norov@gmail.com> References: <20230828184353.5145-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" In the remapping part, we count bits in 'old' and 'new' masks from the beginning for every bit. Complexity of this approach is O(N^2). We can do it better in O(N), if switch bitmap_remap() to using _from versions of bitmap_weight() and find_nth_bit(). On kvm/x86_64 it works 9x faster than the current version for the 1000-bit bitmap in lib/test_bitmap. Because popular distros like Ubuntu has 1024-bit nodemasks, ~10x performance improvement is expected where bitmap_remap() is used. Signed-off-by: Yury Norov --- lib/bitmap.c | 22 +++++++++++++++++++--- 1 file changed, 19 insertions(+), 3 deletions(-) diff --git a/lib/bitmap.c b/lib/bitmap.c index 1fca60d54cb4..8bca6bcf2bc5 100644 --- a/lib/bitmap.c +++ b/lib/bitmap.c @@ -996,7 +996,8 @@ void __bitmap_remap(unsigned long *dst, const unsigned = long *src, const unsigned long *old, const unsigned long *new, unsigned int nbits) { - unsigned int oldbit, w =3D 0, n; + unsigned int newbit, oldbit, w =3D 0, n; + unsigned int _oldbit, _newbit; =20 if (dst =3D=3D src) /* following doesn't handle inplace remaps */ return; @@ -1005,8 +1006,17 @@ void __bitmap_remap(unsigned long *dst, const unsign= ed long *src, bitmap_andnot(dst, src, old, nbits); =20 /* Remapping part */ + _oldbit =3D _newbit =3D 0; for_each_and_bit(oldbit, src, old, nbits) { - n =3D bitmap_weight(old, oldbit); + n =3D bitmap_weight_from(old, oldbit, _oldbit); + newbit =3D find_nth_bit_from(new, nbits, _newbit, n); + if (newbit < nbits) + goto set_bit; + + /* + * If we're out of bits in 'new' map, wrap + * around and start from the beginning. + */ if (w =3D=3D 0) { /* if not initialized */ w =3D bitmap_weight(new, nbits); if (w =3D=3D 0) { /* if empty */ @@ -1014,7 +1024,13 @@ void __bitmap_remap(unsigned long *dst, const unsign= ed long *src, return; } } - __set_bit(find_nth_bit(new, nbits, n % w), dst); + + n -=3D bitmap_weight_from(new, nbits, _newbit); + newbit =3D find_nth_bit(new, nbits, n % w); +set_bit: + __set_bit(newbit, dst); + _oldbit =3D oldbit; + _newbit =3D newbit; } } EXPORT_SYMBOL(__bitmap_remap); --=20 2.39.2