[PATCH] RDMA/rtrs-clt: use find_next_zero_bit() for permit allocation

[PATCH] RDMA/rtrs-clt: use find_next_zero_bit() for permit allocation

[Liu Zhenlong]

__rtrs_get_permit() allocates a free permit from a bitmap under lockless
contention: it scans with find_first_zero_bit() and claims the bit with
test_and_set_bit_lock(), restarting the whole scan when it loses the
race.  Each retry rewinds to bit 0 and re-walks every already-set low
bit before reaching the free region again.

Under high queue depth - the RTRS/RNBD data path - the low part of
permits_map is densely set, so a lost race wastes a scan proportional
to the number of in-use permits on every retry.

Use find_next_zero_bit(), resuming from the last position, so a lost
race continues scanning from where it left off instead of from the
beginning.  When the scan reaches the end, wrap to the beginning to
exhaust the map, so a permit freed below the cursor is still found
and NULL is returned only when the map is actually full, matching the
original behavior.  The scan remains non-atomic, so the
test_and_set_bit_lock() retry is still required and the race
handling is unchanged.

A userspace model of the bitmap-allocation algorithm (not the kernel
find_*_bit primitives) quantifies the mechanism: with qdepth=512 and 14
threads holding ~98% of the bits set, a lost race in the baseline
re-scans the densely-set low region, traversing ~1.3k bit-positions per
allocation, while the patched version resumes and traverses ~260.  The
benefit is contention- and density-dependent: under low contention
(sparse map) the two are equivalent, and the wrap adds a small amount
of code over the single-scan baseline.

End-to-end RNBD/fio throughput was not measured (no RDMA hardware
available); the model isolates the allocation mechanism, not the full
IO path.

Compile-tested: arm64 defconfig + INFINIBAND_RTRS_CLIENT=m, rtrs-clt.o
Assisted-by: Claude:claude-opus-5
Signed-off-by: Liu Zhenlong <dragonliu2018@gmail.com>
---
 drivers/infiniband/ulp/rtrs/rtrs-clt.c | 23 ++++++++++++++---------
 1 file changed, 14 insertions(+), 9 deletions(-)

diff --git a/drivers/infiniband/ulp/rtrs/rtrs-clt.c b/drivers/infiniband/ulp/rtrs/rtrs-clt.c
index d34d7e5f34d6..a1df90243c41 100644
--- a/drivers/infiniband/ulp/rtrs/rtrs-clt.c
+++ b/drivers/infiniband/ulp/rtrs/rtrs-clt.c
@@ -70,19 +70,24 @@ __rtrs_get_permit(struct rtrs_clt_sess *clt, enum rtrs_clt_con_type con_type)
 {
 	size_t max_depth = clt->queue_depth;
 	struct rtrs_permit *permit;
-	int bit;
+	unsigned long bit = 0;
 
 	/*
-	 * Adapted from null_blk get_tag(). Callers from different cpus may
-	 * grab the same bit, since find_first_zero_bit is not atomic.
-	 * But then the test_and_set_bit_lock will fail for all the
-	 * callers but one, so that they will loop again.
-	 * This way an explicit spinlock is not required.
+	 * Callers from different CPUs may grab the same bit, since the bitmap
+	 * scan is not atomic. But then the test_and_set_bit_lock() will fail
+	 * for all the callers but one, so that they loop again. This way an
+	 * explicit spinlock is not required. find_next_zero_bit() resumes
+	 * from the last position so that a lost race does not rescan the
+	 * already-set low bits; if it reaches the end, wrap to the beginning
+	 * to exhaust the map and still find a permit freed below the cursor.
 	 */
 	do {
-		bit = find_first_zero_bit(clt->permits_map, max_depth);
-		if (bit >= max_depth)
-			return NULL;
+		bit = find_next_zero_bit(clt->permits_map, max_depth, bit);
+		if (bit >= max_depth) {
+			bit = find_first_zero_bit(clt->permits_map, max_depth);
+			if (bit >= max_depth)
+				return NULL;
+		}
 	} while (test_and_set_bit_lock(bit, clt->permits_map));
 
 	permit = get_permit(clt, bit);
-- 
2.55.0

Re: [PATCH] RDMA/rtrs-clt: use find_next_zero_bit() for permit allocation

[Jinpu Wang]

On Sun, Aug 16, 2026 at 7:00 PM Liu Zhenlong <dragonliu2018@gmail.com> wrote:
>
> __rtrs_get_permit() allocates a free permit from a bitmap under lockless
> contention: it scans with find_first_zero_bit() and claims the bit with
> test_and_set_bit_lock(), restarting the whole scan when it loses the
> race.  Each retry rewinds to bit 0 and re-walks every already-set low
> bit before reaching the free region again.
>
> Under high queue depth - the RTRS/RNBD data path - the low part of
> permits_map is densely set, so a lost race wastes a scan proportional
> to the number of in-use permits on every retry.
>
> Use find_next_zero_bit(), resuming from the last position, so a lost
> race continues scanning from where it left off instead of from the
> beginning.  When the scan reaches the end, wrap to the beginning to
> exhaust the map, so a permit freed below the cursor is still found
> and NULL is returned only when the map is actually full, matching the
> original behavior.  The scan remains non-atomic, so the
> test_and_set_bit_lock() retry is still required and the race
> handling is unchanged.
>
> A userspace model of the bitmap-allocation algorithm (not the kernel
> find_*_bit primitives) quantifies the mechanism: with qdepth=512 and 14
> threads holding ~98% of the bits set, a lost race in the baseline
> re-scans the densely-set low region, traversing ~1.3k bit-positions per
> allocation, while the patched version resumes and traverses ~260.  The
> benefit is contention- and density-dependent: under low contention
> (sparse map) the two are equivalent, and the wrap adds a small amount
> of code over the single-scan baseline.
>
> End-to-end RNBD/fio throughput was not measured (no RDMA hardware
> available); the model isolates the allocation mechanism, not the full
> IO path.
>
> Compile-tested: arm64 defconfig + INFINIBAND_RTRS_CLIENT=m, rtrs-clt.o
> Assisted-by: Claude:claude-opus-5
> Signed-off-by: Liu Zhenlong <dragonliu2018@gmail.com>
Hi Zhenlong,

Thx for your patch, it looks good, nice optimization.

We may simplify the commit message a bit:
"Callers from different CPUs may grab the same bit, since the bitmap
scan is not atomic. But then the test_and_set_bit_lock() will fail for
all the callers but one, so that they loop again. This way an explicit
spinlock is not required. find_next_zero_bit() resumes from the last
position so that a lost race does not rescan the already-set low bits;
if it reaches the end, wrap to the beginning to exhaust the map and
still find a permit freed below the cursor."

Reviewed-by: Jack Wang <jinpu.wang@cloud.ionos.com>

> ---
>  drivers/infiniband/ulp/rtrs/rtrs-clt.c | 23 ++++++++++++++---------
>  1 file changed, 14 insertions(+), 9 deletions(-)
>
> diff --git a/drivers/infiniband/ulp/rtrs/rtrs-clt.c b/drivers/infiniband/ulp/rtrs/rtrs-clt.c
> index d34d7e5f34d6..a1df90243c41 100644
> --- a/drivers/infiniband/ulp/rtrs/rtrs-clt.c
> +++ b/drivers/infiniband/ulp/rtrs/rtrs-clt.c
> @@ -70,19 +70,24 @@ __rtrs_get_permit(struct rtrs_clt_sess *clt, enum rtrs_clt_con_type con_type)
>  {
>         size_t max_depth = clt->queue_depth;
>         struct rtrs_permit *permit;
> -       int bit;
> +       unsigned long bit = 0;
>
>         /*
> -        * Adapted from null_blk get_tag(). Callers from different cpus may
> -        * grab the same bit, since find_first_zero_bit is not atomic.
> -        * But then the test_and_set_bit_lock will fail for all the
> -        * callers but one, so that they will loop again.
> -        * This way an explicit spinlock is not required.
> +        * Callers from different CPUs may grab the same bit, since the bitmap
> +        * scan is not atomic. But then the test_and_set_bit_lock() will fail
> +        * for all the callers but one, so that they loop again. This way an
> +        * explicit spinlock is not required. find_next_zero_bit() resumes
> +        * from the last position so that a lost race does not rescan the
> +        * already-set low bits; if it reaches the end, wrap to the beginning
> +        * to exhaust the map and still find a permit freed below the cursor.
>          */
>         do {
> -               bit = find_first_zero_bit(clt->permits_map, max_depth);
> -               if (bit >= max_depth)
> -                       return NULL;
> +               bit = find_next_zero_bit(clt->permits_map, max_depth, bit);
> +               if (bit >= max_depth) {
> +                       bit = find_first_zero_bit(clt->permits_map, max_depth);
> +                       if (bit >= max_depth)
> +                               return NULL;
> +               }
>         } while (test_and_set_bit_lock(bit, clt->permits_map));
>
>         permit = get_permit(clt, bit);
> --
> 2.55.0
>