From nobody Fri Jun 19 05:10:34 2026 Received: from SHSQR01.spreadtrum.com (unknown [222.66.158.135]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 7D33B8F49 for ; Thu, 18 Jun 2026 13:35:35 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=222.66.158.135 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1781789739; cv=none; b=T6bwFHmFc/tMMssR0ELKPbJHJIp2OJ+O2VNLtE0IDD5JRhTxoAYuOu4VuR48Kh0befMBaTP4m+xjAnNKo9/K3pdmD6T0r4wUXszXVL3/sbq0BYngTkUDZXhJWiMcaTB+c5dnmLi26QqwSvrlZyBTc2eKWqREpJ01EzQVJMsMAWk= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1781789739; c=relaxed/simple; bh=uwB1kGD+mE/N1Y87nO1O2F5DwvAoSiz1FC774KPsdc4=; h=From:To:CC:Subject:Date:Message-ID:In-Reply-To:References: MIME-Version:Content-Type; b=MlMhLn+ZmOrcv7Y4MDWD2cFFQkTjz7uTIiiWdVdktsAusQptHqK8X6YrZpd7UwNbzHlalGikefhuy8Hyec+qI1z6XHo7xcRkz38kDqm5maaDhtjodpXns/yk5F6t9Ql3wKWfAYAsxkkwukN4cvH4wumT7Ax50LCgBp/3Em9G1Hw= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass (p=quarantine dis=none) header.from=unisoc.com; spf=pass smtp.mailfrom=unisoc.com; dkim=pass (2048-bit key) header.d=unisoc.com header.i=@unisoc.com header.b=l0jOvFRZ; arc=none smtp.client-ip=222.66.158.135 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=quarantine dis=none) header.from=unisoc.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=unisoc.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=unisoc.com header.i=@unisoc.com header.b="l0jOvFRZ" Received: from dlp.unisoc.com ([10.29.3.86]) by SHSQR01.spreadtrum.com with ESMTPS id 65IDZNBB045211 (version=TLSv1.3 cipher=TLS_AES_256_GCM_SHA384 bits=256 verify=NO); Thu, 18 Jun 2026 21:35:24 +0800 (+08) (envelope-from Yi.Sun@unisoc.com) Received: from SHDLP.spreadtrum.com (BJMBX02.spreadtrum.com [10.0.64.8]) by dlp.unisoc.com (SkyGuard) with ESMTPS id 4gh1nf1rdlz2Mt8bS; Thu, 18 Jun 2026 21:30:46 +0800 (CST) Received: from tj10379pcu.spreadtrum.com (10.5.32.15) by BJMBX02.spreadtrum.com (10.0.64.8) with Microsoft SMTP Server (TLS) id 15.0.1497.48; Thu, 18 Jun 2026 21:35:21 +0800 From: Yi Sun To: CC: , <279644543@qq.com>, , , , , , , , , , , , , , Subject: [PATCH v6 1/2] lib: bitmap: add tests for bitmap_find_next_zero_area_off() Date: Thu, 18 Jun 2026 21:35:17 +0800 Message-ID: <20260618133518.4079981-2-yi.sun@unisoc.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20260618133518.4079981-1-yi.sun@unisoc.com> References: <20260618133518.4079981-1-yi.sun@unisoc.com> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable X-ClientProxiedBy: SHCAS01.spreadtrum.com (10.0.1.201) To BJMBX02.spreadtrum.com (10.0.64.8) X-MAIL: SHSQR01.spreadtrum.com 65IDZNBB045211 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=unisoc.com; s=default; t=1781789731; bh=TPHKiu0YnoMT+px+0T/JgFeY4+u1EblqnhFAS6Q0Amw=; h=From:To:CC:Subject:Date:In-Reply-To:References; b=l0jOvFRZFCeJrZi/qLg140lcnDrhrfNtDMMKlpF/foBhn1Wcim0kOVxhm/H59EBQg 7eIMlHzT2UascEsX5sthSeTouwa4dQ5Zt8ESkdkZmnHVoblZopwczGcOboX8UDXKQ2 pGNOWJjuzVYFeCwiSBOxcD92xoN+JuLrZXB3HyROsKYd10F2V9RPrxgQ5gnUrIB2x9 pKTyAsl2ffcNy6AT2k4j05fo3YdpJtCa0iam7heG0tH5keaJjKj5GxPHd7s9LwDVMF X4i5hqJw1tUriInAmH2X4CwrAl7QDnPuvKuyvPI/ufzawSaretCriymMYFo7Bwqqxc mR6w7qWWpGX/w== Content-Type: text/plain; charset="utf-8" Add functional and performance tests for bitmap_find_next_zero_area_off(). performance tests partial output: Start testing find_bit() with random-filled bitmap [ 0.310073] bitmap_find_next_zero_area_off: 852731 ns, 1154 it= erations [ 0.311435] find_next_bit: 1356654 ns, 163975 it= erations Start testing find_bit() with sparse bitmap [ 0.316267] bitmap_find_next_zero_area_off: 4426808 ns, 322479 it= erations [ 0.316292] find_next_bit: 15154 ns, 656 it= erations Signed-off-by: Yi Sun --- lib/find_bit_benchmark.c | 31 ++++++++++++++++++++++++------- lib/test_bitmap.c | 38 ++++++++++++++++++++++++++++++++++++++ 2 files changed, 62 insertions(+), 7 deletions(-) diff --git a/lib/find_bit_benchmark.c b/lib/find_bit_benchmark.c index 00d9dc61cd46..cde7c09de05c 100644 --- a/lib/find_bit_benchmark.c +++ b/lib/find_bit_benchmark.c @@ -46,7 +46,7 @@ static int __init test_find_first_bit(const void *bitmap,= unsigned long len) __clear_bit(i, cp); } time =3D ktime_get() - time; - pr_err("find_first_bit: %18llu ns, %6ld iterations\n", time, cnt); + pr_err("find_first_bit: %14llu ns, %6ld iterations\n", ti= me, cnt); =20 return 0; } @@ -66,7 +66,7 @@ static int __init test_find_first_and_bit(const void *bit= map, const void *bitmap __clear_bit(i, cp); } time =3D ktime_get() - time; - pr_err("find_first_and_bit: %18llu ns, %6ld iterations\n", time, cnt); + pr_err("find_first_and_bit: %14llu ns, %6ld iterations\n", ti= me, cnt); =20 return 0; } @@ -80,7 +80,7 @@ static int __init test_find_next_bit(const void *bitmap, = unsigned long len) for (cnt =3D i =3D 0; i < BITMAP_LEN; cnt++) i =3D find_next_bit(bitmap, BITMAP_LEN, i) + 1; time =3D ktime_get() - time; - pr_err("find_next_bit: %18llu ns, %6ld iterations\n", time, cnt); + pr_err("find_next_bit: %14llu ns, %6ld iterations\n", ti= me, cnt); =20 return 0; } @@ -94,7 +94,7 @@ static int __init test_find_next_zero_bit(const void *bit= map, unsigned long len) for (cnt =3D i =3D 0; i < BITMAP_LEN; cnt++) i =3D find_next_zero_bit(bitmap, len, i) + 1; time =3D ktime_get() - time; - pr_err("find_next_zero_bit: %18llu ns, %6ld iterations\n", time, cnt); + pr_err("find_next_zero_bit: %14llu ns, %6ld iterations\n", ti= me, cnt); =20 return 0; } @@ -113,7 +113,7 @@ static int __init test_find_last_bit(const void *bitmap= , unsigned long len) len =3D l; } while (len); time =3D ktime_get() - time; - pr_err("find_last_bit: %18llu ns, %6ld iterations\n", time, cnt); + pr_err("find_last_bit: %14llu ns, %6ld iterations\n", ti= me, cnt); =20 return 0; } @@ -129,7 +129,7 @@ static int __init test_find_nth_bit(const unsigned long= *bitmap, unsigned long l WARN_ON(l >=3D len); } time =3D ktime_get() - time; - pr_err("find_nth_bit: %18llu ns, %6ld iterations\n", time, w); + pr_err("find_nth_bit: %14llu ns, %6ld iterations\n", ti= me, w); =20 return 0; } @@ -144,7 +144,22 @@ static int __init test_find_next_and_bit(const void *b= itmap, for (cnt =3D i =3D 0; i < BITMAP_LEN; cnt++) i =3D find_next_and_bit(bitmap, bitmap2, BITMAP_LEN, i + 1); time =3D ktime_get() - time; - pr_err("find_next_and_bit: %18llu ns, %6ld iterations\n", time, cnt); + pr_err("find_next_and_bit: %14llu ns, %6ld iterations\n", ti= me, cnt); + + return 0; +} + +static int __init +test_bitmap_find_next_zero_area_off(unsigned long *bitmap, unsigned long l= en) +{ + unsigned long i, cnt; + ktime_t time; + + time =3D ktime_get(); + for (cnt =3D i =3D 0; i < BITMAP_LEN; cnt++) + i =3D bitmap_find_next_zero_area_off(bitmap, BITMAP_LEN, i, 8, 0, 0) + 1; + time =3D ktime_get() - time; + pr_err("bitmap_find_next_zero_area_off: %14llu ns, %6ld iterations\n", ti= me, cnt); =20 return 0; } @@ -158,6 +173,7 @@ static int __init find_bit_test(void) get_random_bytes(bitmap, sizeof(bitmap)); get_random_bytes(bitmap2, sizeof(bitmap2)); =20 + test_bitmap_find_next_zero_area_off(bitmap, BITMAP_LEN); test_find_next_bit(bitmap, BITMAP_LEN); test_find_next_zero_bit(bitmap, BITMAP_LEN); test_find_last_bit(bitmap, BITMAP_LEN); @@ -181,6 +197,7 @@ static int __init find_bit_test(void) __set_bit(get_random_u32_below(BITMAP_LEN), bitmap2); } =20 + test_bitmap_find_next_zero_area_off(bitmap, BITMAP_LEN); test_find_next_bit(bitmap, BITMAP_LEN); test_find_next_zero_bit(bitmap, BITMAP_LEN); test_find_last_bit(bitmap, BITMAP_LEN); diff --git a/lib/test_bitmap.c b/lib/test_bitmap.c index 69813c10e6c0..8665df77c960 100644 --- a/lib/test_bitmap.c +++ b/lib/test_bitmap.c @@ -234,6 +234,43 @@ static void __init test_find_nth_bit(void) } } =20 +static void __init +test_bitmap_find_next_zero_area_off(void) +{ + DECLARE_BITMAP(bmap, 192); + + bitmap_set(bmap, 0, 192); + + bitmap_clear(bmap, 0, 8); + __clear_bit(50, bmap); + bitmap_clear(bmap, 60, 18); + __set_bit(69, bmap); + __clear_bit(80, bmap); + bitmap_clear(bmap, 100, 10); + __clear_bit(120, bmap); + bitmap_clear(bmap, 145, 8); + bitmap_clear(bmap, 160, 32); + + expect_eq_uint(0, + bitmap_find_next_zero_area_off(bmap, 192, 0, 8, 0, 0)); + expect_eq_uint(0, + bitmap_find_next_zero_area_off(bmap, 192, 0, 8, 3, 0)); + expect_eq_uint(163, + bitmap_find_next_zero_area_off(bmap, 192, 0, 8, 3, 1)); + expect_eq_uint(60, + bitmap_find_next_zero_area_off(bmap, 192, 1, 8, 0, 0)); + expect_eq_uint(160, + bitmap_find_next_zero_area_off(bmap, 192, 1, 8, 7, 0)); + expect_eq_uint(60, + bitmap_find_next_zero_area_off(bmap, 192, 1, 8, 7, 4)); + expect_eq_uint(100, + bitmap_find_next_zero_area_off(bmap, 192, 0, 10, 0, 0)); + expect_eq_uint(160, + bitmap_find_next_zero_area_off(bmap, 192, 0, 32, 0, 0)); + expect_eq_uint(1, + !!(bitmap_find_next_zero_area_off(bmap, 192, 0, 33, 0, 0) >=3D 192)); +} + static void __init test_fill_set(void) { DECLARE_BITMAP(bmap, 1024); @@ -1559,6 +1596,7 @@ static void __init selftest(void) test_for_each_clear_bitrange_from(); test_for_each_set_clump8(); test_for_each_set_bit_wrap(); + test_bitmap_find_next_zero_area_off(); } =20 KSTM_MODULE_LOADERS(test_bitmap); --=20 2.34.1 From nobody Fri Jun 19 05:10:34 2026 Received: from SHSQR01.spreadtrum.com (unknown [222.66.158.135]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 621192BDC28 for ; Thu, 18 Jun 2026 13:35:39 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=222.66.158.135 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1781789744; cv=none; b=PU9cefINNImSJ8exPHvaNoTNxAAX1Ldts4BFIHlRI0rUahg/7pSsIiP+LbCzDY/clCf89q5fGkFyT6IjLiZSR423j61fNF/L4fsTqRC+4R1PaEv49ZlwusVgjXZb3VT1/O4PDCMFb7Gd0EvSqK4ev+ZaAOqNK/JJXjTEns1X2bA= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1781789744; c=relaxed/simple; bh=25JQpagMtFjmMhL6puykQv1OyYQDp/gF2B4SLONJTQc=; h=From:To:CC:Subject:Date:Message-ID:In-Reply-To:References: MIME-Version:Content-Type; b=rFVukvaNn6M9pg/fUEEdsEh+oZQMvRDN8jGKQDC6q3eGGJoZuE8zEsuNHk+0fQFsZPF013vFDkzX5813Q4a1eSWPlmXT0CgEvR1dCH7w88260b3MbySPxqdgRzYbKkKJ61Nfvhst6h5s2pNtKcVsyrZSUwGQnWlJMwY/gmC1TVw= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass (p=quarantine dis=none) header.from=unisoc.com; spf=pass smtp.mailfrom=unisoc.com; dkim=pass (2048-bit key) header.d=unisoc.com header.i=@unisoc.com header.b=bQKJNZul; arc=none smtp.client-ip=222.66.158.135 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=quarantine dis=none) header.from=unisoc.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=unisoc.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=unisoc.com header.i=@unisoc.com header.b="bQKJNZul" Received: from dlp.unisoc.com ([10.29.3.86]) by SHSQR01.spreadtrum.com with ESMTPS id 65IDZPhx045217 (version=TLSv1.3 cipher=TLS_AES_256_GCM_SHA384 bits=256 verify=NO); Thu, 18 Jun 2026 21:35:25 +0800 (+08) (envelope-from Yi.Sun@unisoc.com) Received: from SHDLP.spreadtrum.com (BJMBX02.spreadtrum.com [10.0.64.8]) by dlp.unisoc.com (SkyGuard) with ESMTPS id 4gh1ng3r8Mz2Mt8bJ; Thu, 18 Jun 2026 21:30:47 +0800 (CST) Received: from tj10379pcu.spreadtrum.com (10.5.32.15) by BJMBX02.spreadtrum.com (10.0.64.8) with Microsoft SMTP Server (TLS) id 15.0.1497.48; Thu, 18 Jun 2026 21:35:23 +0800 From: Yi Sun To: CC: , <279644543@qq.com>, , , , , , , , , , , , , , Subject: [PATCH v6 2/2] lib: bitmap: optimize bitmap_find_next_zero_area_off() Date: Thu, 18 Jun 2026 21:35:18 +0800 Message-ID: <20260618133518.4079981-3-yi.sun@unisoc.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20260618133518.4079981-1-yi.sun@unisoc.com> References: <20260618133518.4079981-1-yi.sun@unisoc.com> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable X-ClientProxiedBy: SHCAS01.spreadtrum.com (10.0.1.201) To BJMBX02.spreadtrum.com (10.0.64.8) X-MAIL: SHSQR01.spreadtrum.com 65IDZPhx045217 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=unisoc.com; s=default; t=1781789736; bh=Cr5tzJsckZnfP4fznZm/POofxhCsLMWwxxI/37UtKV4=; h=From:To:CC:Subject:Date:In-Reply-To:References; b=bQKJNZulyUMIZwDwgDwoSKArIWCZiPMpXWHHIn1F5WQXdwvws1qjMYbd6udVAcBRy KvFmO4esgmAZQoC5gTRthTjvMEDe+935X1JySDGbx//EFWwR6klcH5higqH5LiLVko SZYvLMkOSVzSn8a0EQyNZ4PlIEn8pTdrlyaLg7sG9pwYoZ3uUCiQe3fufcrBxtMvIl R5JtzQbAhyVb1u1sZ+41Zf8Z08zRqcDXmIcl/xGYXDrowjh6nBE13iqa8X2BH8OMuv 6xybXhjQbyAzdwLz6lzFdAHWahPtSfPdsKvLBMZwxigIPgwHmes7T0qlvUkpsqbXY4 molgKE4UiNX0w== Content-Type: text/plain; charset="utf-8" Finding a contiguous free region in a highly fragmented bitmap is not easy and may require many repeated attempts. Therefore, find_next_bit(map, end, index) is not the optimal choice. This is because there may be multiple scattered free regions within the range [index, end) and none of them will meet the length requirement of @nr. Instead, it's sufficient to directly find the last bit within the range [index, end), thus reducing unnecessary repeated calls. An example of a bitmap: Bits 0-3: cleared(4 bits) Bits 4-5: set (2 bits) Bits 6-8: cleared(4 bits) Bits 9-10: set (2 bits) Bits 11-20: cleared(10 bits) The goal is to find a 10-bit free region. The old code logic is as follows: find_next_zero_bit(start =3D 0, find bit 0) -> find_next_bit(find bit 4) -> next loop -> find_next_zero_bit(start =3D 5, find bit 6) -> find_next_bit(find bit 9) -> next loop -> find_next_zero_bit(start =3D 10, find bit 11) -> success The new code logic is as follows: find_next_zero_bit(start =3D 0, find bit 0) -> find_last_bit(find bit 9) -> next loop -> find_next_zero_bit(start =3D 10, find bit 11) -> success Performance test results on my hardware(use lib/find_bit_benchmark.c): before after change p-value dense 1211 688 -43.2% 8.3e-11 sparse 13.3 13.4 0.8% 0.27 Co-developed-by: Yury Norov Signed-off-by: Yury Norov Signed-off-by: Yi Sun --- lib/bitmap.c | 31 ++++++++++++++++--------------- 1 file changed, 16 insertions(+), 15 deletions(-) diff --git a/lib/bitmap.c b/lib/bitmap.c index b9bfa157e095..a00a71f2b7bb 100644 --- a/lib/bitmap.c +++ b/lib/bitmap.c @@ -432,22 +432,23 @@ unsigned long bitmap_find_next_zero_area_off(unsigned= long *map, unsigned long align_mask, unsigned long align_offset) { - unsigned long index, end, i; -again: - index =3D find_next_zero_bit(map, size, start); - - /* Align allocation */ - index =3D __ALIGN_MASK(index + align_offset, align_mask) - align_offset; - - end =3D index + nr; - if (end > size) - return end; - i =3D find_next_bit(map, end, index); - if (i < end) { - start =3D i + 1; - goto again; + unsigned long end, i, off; + + for_each_clear_bit_from(start, map, size) { + start =3D __ALIGN_MASK(start + align_offset, align_mask) - align_offset; + end =3D start + nr; + if (end > size) + break; + + off =3D round_down(start, BITS_PER_LONG); + i =3D find_last_bit(map + start / BITS_PER_LONG, end - off) + off; + if (i >=3D end || i < start) + return start; + + start =3D i; } - return index; + + return size; } EXPORT_SYMBOL(bitmap_find_next_zero_area_off); =20 --=20 2.34.1