From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from SHSQR01.spreadtrum.com (mx1.unisoc.com [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 0E33C390998 for ; Mon, 22 Jun 2026 13:09:30 +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=1782133772; cv=none; b=GVnum7AQ2/RizgEeyydVtbTpqifkNuXeHNCa8T62sjitrqQIvIfTfyBmID1IphpnTxqI2+lISH1A7ytJK6T4Og8coErWVJprD13QMgFnlmNYBfLDXGek5jZYwYJYXNuzsqEOdQU0Rju4f8syGX/N85C7OMApCsYg178UiyC9yRk= ARC-Message-Signature:i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1782133772; c=relaxed/simple; bh=wkRpvhi6AEBGV7/1Cie64Nkw/mXjQcqsDcy3lkXwoY0=; h=From:To:CC:Subject:Date:Message-ID:In-Reply-To:References: MIME-Version:Content-Type; b=E1qEV3xFbbQa7/CfkPoNQcYabVvCsJFIW4f51cE/DepK1WIeDT9GSWjKpEqFyzU4PtIMyC3P5m4Ck6PeKAbK+g+//vS1KQUmC/GaLLbbTEAe2cH+LgEKtffNgONoAyXTDh+HlEPThF+1OOZTDx9wsNDUIMXwNPA+Y+AGSotOmpQ= 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=pSUHnK0F; 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="pSUHnK0F" Received: from dlp.unisoc.com ([10.29.3.86]) by SHSQR01.spreadtrum.com with ESMTPS id 65MD99aG084974 (version=TLSv1.3 cipher=TLS_AES_256_GCM_SHA384 bits=256 verify=NO); Mon, 22 Jun 2026 21:09:09 +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 4gkT1L73Qvz2Mx99x; Mon, 22 Jun 2026 21:04:22 +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; Mon, 22 Jun 2026 21:09:06 +0800 From: Yi Sun To: CC: , <279644543@qq.com>, , , , , , , , , , , , Subject: [PATCH v8 2/2] lib: bitmap: optimize bitmap_find_next_zero_area_off() Date: Mon, 22 Jun 2026 21:08:59 +0800 Message-ID: <20260622130859.1973637-3-yi.sun@unisoc.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20260622130859.1973637-1-yi.sun@unisoc.com> References: <20260622130859.1973637-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: 8bit Content-Type: text/plain X-ClientProxiedBy: SHCAS03.spreadtrum.com (10.0.1.207) To BJMBX02.spreadtrum.com (10.0.64.8) X-MAIL:SHSQR01.spreadtrum.com 65MD99aG084974 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=unisoc.com; s=default; t=1782133766; bh=CFGp8ueJ2DnRFn0u3mQt/xOfzLB/xtp5FFPYVJqAX34=; h=From:To:CC:Subject:Date:In-Reply-To:References; b=pSUHnK0F5BxwS/DGxbK+WEasuHg1dStXRlfSnVkwoUFFrgzzTou9Lu/JAa4ZSv35I r5pO6M0mpMHo/yqznJJnlO/Zr3oDY4bMytM9jpYQOr0Q6RdpmF3nPodNU9TbcMQvuU W/Z/1sOHITJcVaIqhf43+s47LI7NQ4y/vbrTo1YwA4VRuwoqfRWPR0LXVD3EBmxdpV RssHFPHhroVObfoW/eOPJ4DUvIVvQTM0yOt+KCPUlloLuGeN9PahyURNSbgjwOC6/l RfWnHY9OV+Un+xyqM+FAIQinsci3X4bKz3OffdXRTBMiPNP+4MOMeY4Alk6Nx0KWn7 G6zlm+sfV3kqQ== 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 = 0, find bit 0) -> find_next_bit(find bit 4) -> next loop -> find_next_zero_bit(start = 5, find bit 6) -> find_next_bit(find bit 9) -> next loop -> find_next_zero_bit(start = 10, find bit 11) -> success The new code logic is as follows: find_next_zero_bit(start = 0, find bit 0) -> find_last_bit(find bit 9) -> next loop -> find_next_zero_bit(start = 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 ++++++++++++++++--------------- lib/test_bitmap.c | 4 ++-- 2 files changed, 18 insertions(+), 17 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 = find_next_zero_bit(map, size, start); - - /* Align allocation */ - index = __ALIGN_MASK(index + align_offset, align_mask) - align_offset; - - end = index + nr; - if (end > size) - return end; - i = find_next_bit(map, end, index); - if (i < end) { - start = i + 1; - goto again; + unsigned long end, i, off; + + for_each_clear_bit_from(start, map, size) { + start = __ALIGN_MASK(start + align_offset, align_mask) - align_offset; + end = start + nr; + if (end > size) + break; + + off = round_down(start, BITS_PER_LONG); + i = find_last_bit(map + start / BITS_PER_LONG, end - off) + off; + if (i >= end || i < start) + return start; + + start = i; } - return index; + + return size; } EXPORT_SYMBOL(bitmap_find_next_zero_area_off); diff --git a/lib/test_bitmap.c b/lib/test_bitmap.c index 5acb4dc5223c..40df8d8575c0 100644 --- a/lib/test_bitmap.c +++ b/lib/test_bitmap.c @@ -267,8 +267,8 @@ test_bitmap_find_next_zero_area_off(void) 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) > 192); + expect_eq_uint(192, + bitmap_find_next_zero_area_off(bmap, 192, 0, 33, 0, 0)); } static void __init test_fill_set(void) -- 2.34.1