From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from mail-yw1-f172.google.com (mail-yw1-f172.google.com [209.85.128.172]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 17C9A1A304A for ; Thu, 18 Jun 2026 06:15:00 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.128.172 ARC-Seal:i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1781763302; cv=none; b=NHYqNr2ke/K4ymDnJemgSDkCX+mFDMpm4t/I6r8cDVCpMENMo9ndrhGztHNEFyYUxZANXH0lSfD5ZfS6VZ2YupYK0T6lpFuMPWgatQquYov7hew9RfPl1fgIlw05I0rU1RxLYrzvjBZO2yO3QOzjm2uLRs4DvTtXB1CcsluS0lY= ARC-Message-Signature:i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1781763302; c=relaxed/simple; bh=mm6NcCgX+8pT6zCZQARwPgoDKqcLGT8APA+71NtyOwU=; h=From:Date:To:Cc:Subject:Message-ID:References:MIME-Version: Content-Type:Content-Disposition:In-Reply-To; b=Y8328IiYSUIBKOb7RiL/2zVL5jdwT4Vwn1OgMjnHsIwMNQnCFI2zEOg3cmzQEbP81DZyU4HXz2drajZbA3x2eFey9zc5YGUcoHp6Gv/yIIajiRfFYIeNUQd6Nm5vmil4gRn976uWQNRu9JGPFVVGxtRHmASDnl8yzvNLqVO3eAI= ARC-Authentication-Results:i=1; smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com; spf=pass smtp.mailfrom=gmail.com; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b=lfyeK59W; arc=none smtp.client-ip=209.85.128.172 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=gmail.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="lfyeK59W" Received: by mail-yw1-f172.google.com with SMTP id 00721157ae682-7fdb04d774aso6941277b3.2 for ; Wed, 17 Jun 2026 23:15:00 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20251104; t=1781763300; x=1782368100; darn=vger.kernel.org; h=in-reply-to:content-disposition:mime-version:references:message-id :subject:cc:to:date:from:from:to:cc:subject:date:message-id:reply-to; bh=x9Ha1kKjhrIrsW2VKjrv5YsQdzPun2BLliM9GvbRf40=; b=lfyeK59WSM2PRvl4MtIRsVGgFXfMXGXM1AuealJntma6+OwSc4XwrtxE7Bb3hwc0iS bHEiWhfKTpX70b/TfoHGRGKqqysvcVOrhqjrMc6b0P8XPVc0vbZiBpD3uXSc2Dcd34il H07RcmgQlTgE+5OTuAr8bCFSBM0BIZ598ClGy16KX7CV4vRz7xFFSVfKwfSixsAcZVYl 0/f7TeLSwUG2iFUjc6y1cGuLo+Tx+qUQDhzSURVTr4WdWX7enr5r8V0yG+lavlBvkfYG MUwDOFF8FYtTEm/Dq/e284pxrOZQDAZnYs6ibxxoB0p1YyhljxiT7GFdlAS6t4jV8YwP cQKg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20251104; t=1781763300; x=1782368100; h=in-reply-to:content-disposition:mime-version:references:message-id :subject:cc:to:date:from:x-gm-gg:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=x9Ha1kKjhrIrsW2VKjrv5YsQdzPun2BLliM9GvbRf40=; b=GpTLt/LVDbOVq1kmj//dzrRrHEzxEFAZM4IeO9tJvB9j0qPtmltjQ+IZ6LXBIW2a84 He6yDYb1EY3leasLDBbMRCslCUt9Ui0J0tpxtMojS1OhCD/9p77B9Eh3zGpPdcfWirj3 2Kfd9/2M6HR3ZKT/ElXEnNSP0Ahv9pgydJum0HQ8efhNtl7sWPb4bID3z+jp9JfYbE3A EsjxoPP17z0RBn14+D9Dc2kA/Ke77AOjaWpx2ngx5GtH+q5ib5pQ8NqK3yV2CK3U7D+E slCn0XMUKbnvmjugMntUwm3iAb6pNVAuyPNquWgAtNduvnpyt5Jywhv1LunsiA2hZn3h FDxw== X-Forwarded-Encrypted: i=1; AFNElJ/GVVKLTokCCCXCCx63vgzZK0YeHNXuAxjikPZHCKUL92X7hED7kDNAk60maN/f3V/oz58GSuyUgInNXUE=@vger.kernel.org X-Gm-Message-State: AOJu0YwWRm/YaPbI5i0rywhzlsuRLT7xwEx3V7wHbuoXahfcK4G1y83D mR8tgP2AIxZGFHNW7xfCGLtN/aPb3UmV3XlPWjOGvwdNtesR5lHyFtly X-Gm-Gg: AfdE7ckARN4TXF+Xi1MU/4COyVEx9+bsJ4fRxjOvnz2KB46cSO2a3JL9i7nWj8g3E/Q ll1CsqX2SYu1r995s5Dp/A/ktVPB3CLHmS0dNB+2bbSqJYqjTKjdIzC7+cE3r6Qw6xJcCQk694J jrQht2vZbGmLjuS9ZB56RN2o4W1CrkPKL5BmiXUzbYB824BPhIhfdh8jSbxv0l0YsdMfE0thf/i 52i6/A7feoypcqFBlGclGQdPtF8WMlwNRO9Gtpg3NowPknwu2Euq2baiObnpjYWuMjoOhkfrxiK vsMnL3L9+/UHQRNbHLN8bSytUJ5wfVmQmjddO8Amwvq5FvaoG33qASjTtwWYOqa23Wna6YmEjEz 43rytM9faMU02QdsDeeUItHnzvuIqt2Mnt2dn1/xztNM5IfdBZDxcD7JW+Nfkw9LNpSLI+2XPzO AxlrtE+kq7Fi11siENyQSwDMOpzx3GBVFgVaPkpskk2l1S4A== X-Received: by 2002:a05:690c:3706:b0:7f5:4d6e:6d20 with SMTP id 00721157ae682-80027155c2amr9393277b3.33.1781763299997; Wed, 17 Jun 2026 23:14:59 -0700 (PDT) Received: from localhost (syn-035-130-123-074.biz.spectrum.com. [35.130.123.74]) by smtp.gmail.com with ESMTPSA id 00721157ae682-7fcd345a5fesm63432327b3.36.2026.06.17.23.14.59 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Wed, 17 Jun 2026 23:14:59 -0700 (PDT) From: Yury Norov X-Google-Original-From: Yury Norov Date: Thu, 18 Jun 2026 02:14:58 -0400 To: Yi Sun Cc: yury.norov@gmail.com, mina86@mina86.com, 279644543@qq.com, mnazarewicz@gmail.com, akpm@linux-foundation.org, akinobu.mita@gmail.com, linux-kernel@vger.kernel.org, john.stultz@linaro.org, tjmercier@google.com, qiang.zhao@freescale.com, scottwood@freescale.com, benjamin.gaignard@linaro.org, fvdl@google.com, tglx@kernel.org, andreas.herrmann@calxeda.com, song@kernel.org, hch@lst.de, sasha.levin@oracle.com, minchan@kernel.org Subject: Re: [PATCH v5 2/2] lib: bitmap: optimize bitmap_find_next_zero_area_off() Message-ID: References: <20260618015252.3601554-1-yi.sun@unisoc.com> <20260618015252.3601554-3-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-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <20260618015252.3601554-3-yi.sun@unisoc.com> On Thu, Jun 18, 2026 at 09:52:52AM +0800, Yi Sun wrote: > 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) -> > goto again -> > find_next_zero_bit(start = 5, find bit 6) -> find_next_bit(find bit 9) -> > goto again -> > 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) -> > goto again -> > find_next_zero_bit(start = 10, find bit 11) -> success In new logic there's no goto, right? > 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 > > Signed-off-by: Yi Sun > --- > lib/bitmap.c | 35 +++++++++++++++++++++-------------- > 1 file changed, 21 insertions(+), 14 deletions(-) > > diff --git a/lib/bitmap.c b/lib/bitmap.c > index b9bfa157e095..a2c4bd22d875 100644 > --- a/lib/bitmap.c > +++ b/lib/bitmap.c > @@ -432,22 +432,29 @@ 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) { > + unsigned long find_idx, end, i, find_word_idx, find_word_off; > + > + for (;;) { "Infinite" loop is nothing better than the backward goto. Can you try this: 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 size; If it works for you, let's move with the for_each() version. Can you test and add my Co-developed-by please? Thanks, Yury > + find_idx = find_next_zero_bit(map, size, start); > + > + /* Align allocation */ > + find_idx = __ALIGN_MASK(find_idx + align_offset, > + align_mask) - align_offset; > + > + end = find_idx + nr; > + if (end > size) > + return end; > + > + find_word_idx = find_idx / BITS_PER_LONG; > + find_word_off = find_word_idx * BITS_PER_LONG; > + > + i = find_last_bit(map + find_word_idx, > + end - find_word_off) + find_word_off; > + if (i >= end || i < find_idx) > + return find_idx; > + > start = i + 1; > - goto again; > } > - return index; > } > EXPORT_SYMBOL(bitmap_find_next_zero_area_off); > > -- > 2.34.1