From nobody Tue Dec 2 01:50:42 2025 Received: from mailout3.samsung.com (mailout3.samsung.com [203.254.224.33]) (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 D228923D7EC for ; Fri, 21 Nov 2025 03:19:30 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=203.254.224.33 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1763695174; cv=none; b=b4XL+HTUjD/bxImAoM6pGJNQH8sFk85A4Uh4/lOuY0GARaKD1yJCty09o54TFJ3fs8CZ/yfGOOViiOGUk0duVMViv6RXtPptyB0nloHI/XOB0wnghA2i/SKxsPB228s8Oca7r8pbBQFB7/4FdafkON4JkH7XVoEgcylfz2pbGJ0= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1763695174; c=relaxed/simple; bh=DgsBtqxGQa4wjm9WzZ1LoBOPv18n3Digt4dA6FTpxqM=; h=From:To:Cc:Subject:Date:Message-Id:MIME-Version:Content-Type: References; b=E2biHWaNYSDp9in6yhJUG822k4t79gXNEz5QiscTRa5zxmtyxb4JUvEIWh+XHpsSzO8nBujxk1FfFnc+vdmjf85nR8Y8Iqp6hRyIjhgU3Qok6zlDzfOcIab6zxu+DxMN0acmoiTcuDwuTUJwA5BlfsEliPSEftp4y6yp28eX58g= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=samsung.com; spf=pass smtp.mailfrom=samsung.com; dkim=pass (1024-bit key) header.d=samsung.com header.i=@samsung.com header.b=AtUTB8pP; arc=none smtp.client-ip=203.254.224.33 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=samsung.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=samsung.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (1024-bit key) header.d=samsung.com header.i=@samsung.com header.b="AtUTB8pP" Received: from epcas5p2.samsung.com (unknown [182.195.41.40]) by mailout3.samsung.com (KnoxPortal) with ESMTP id 20251121031922epoutp037c00141c6c7d43608f521e8fadc1799c~552fpRejJ0174101741epoutp03F for ; Fri, 21 Nov 2025 03:19:22 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 mailout3.samsung.com 20251121031922epoutp037c00141c6c7d43608f521e8fadc1799c~552fpRejJ0174101741epoutp03F DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=samsung.com; s=mail20170921; t=1763695162; bh=H/BBH4ycWODNggkUgW6kGRbq38eHJVYcrzyoZ7ky4hM=; h=From:To:Cc:Subject:Date:References:From; b=AtUTB8pPsn2YfO4mbdivR9lgtAhMGaZsta362+tByai9kcQVHxcxMG25sYcJNU4HA /4WLce76gAAr8TNIljrh5+y3cABsbVqYyCONd/NWltZLf1zv16d4EBGVUUSFIojEJG +CDh4RL60jVb0YCYy6Pr44N2obHPC5/gdNBGYjFo= Received: from epsnrtp04.localdomain (unknown [182.195.42.156]) by epcas5p1.samsung.com (KnoxPortal) with ESMTPS id 20251121031922epcas5p1fa9610b094a8eb6afe5de29f1186344d~552fVe7kV2774027740epcas5p1J; Fri, 21 Nov 2025 03:19:22 +0000 (GMT) Received: from epcas5p4.samsung.com (unknown [182.195.38.94]) by epsnrtp04.localdomain (Postfix) with ESMTP id 4dCL6d3mnRz6B9m5; Fri, 21 Nov 2025 03:19:21 +0000 (GMT) Received: from epsmtip2.samsung.com (unknown [182.195.34.31]) by epcas5p4.samsung.com (KnoxPortal) with ESMTPA id 20251121031810epcas5p4f6c4b4cd26ea2fa01dea5c7dd3a9572b~551cUbwhq1792617926epcas5p4M; Fri, 21 Nov 2025 03:18:10 +0000 (GMT) Received: from node122.. (unknown [109.105.118.122]) by epsmtip2.samsung.com (KnoxPortal) with ESMTPA id 20251121031809epsmtip217944f4e6633ed22e4fec34fdbb309dc~551boYdUX1355313553epsmtip2A; Fri, 21 Nov 2025 03:18:09 +0000 (GMT) From: Xue He To: akpm@linux-foundation.org, axboe@kernel.dk Cc: linux-kernel@vger.kernel.org, linux-block@vger.kernel.org, hexue Subject: [PATCH RESEND] lib/sbitmap: add an helper of sbitmap_find_bits_in_word Date: Fri, 21 Nov 2025 03:13:29 +0000 Message-Id: <20251121031329.705663-1-xue01.he@samsung.com> X-Mailer: git-send-email 2.34.1 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-CMS-MailID: 20251121031810epcas5p4f6c4b4cd26ea2fa01dea5c7dd3a9572b X-Msg-Generator: CA Content-Type: text/plain; charset="utf-8" X-Sendblock-Type: REQ_APPROVE CMS-TYPE: 105P cpgsPolicy: CPGSC10-505,Y X-CFilter-Loop: Reflected X-CMS-RootMailID: 20251121031810epcas5p4f6c4b4cd26ea2fa01dea5c7dd3a9572b References: From: hexue The original sbitmap performed a cleanup operation before acquiring a bit, but this was sometimes unnecessary overhead. This patch reduced the frequency of cleanup operations, executing them only when necessary, and abstracted a helper function that can acquire multiple free bits in a single operation. ---------------------------------------------------------------------- HW: 16 CPUs/16 poll queues Disk: Samsung PM9A3 Gen4 3.84T CMD: [global] ioengine=3Dio_uring group_reporting=3D1 time_based=3D1 runtime=3D1m refill_buffers=3D1 norandommap=3D1 randrepeat=3D0 fixedbufs=3D1 registerfiles=3D1 rw=3Drandread iodepth=3D128 iodepth_batch_submit=3D32 iodepth_batch_complete_min=3D32 iodepth_batch_complete_max=3D128 iodepth_low=3D32 bs=3D4k numjobs=3D1 direct=3D1 hipri=3D1 [job1] filename=3D/dev/nvme0n1 name=3Dbatch_test ------------------------------------------------------------------- Perf: base code: __blk_mq_alloc_requests() 0.75% patch: __blk_mq_alloc_requests() 0.70% ------------------------------------------------------------------- Signed-off-by: hexue --- lib/sbitmap.c | 71 ++++++++++++++++++++++++++++++++++----------------- 1 file changed, 47 insertions(+), 24 deletions(-) diff --git a/lib/sbitmap.c b/lib/sbitmap.c index 4d188d05db15..98fd27a896f1 100644 --- a/lib/sbitmap.c +++ b/lib/sbitmap.c @@ -208,6 +208,43 @@ static int sbitmap_find_bit_in_word(struct sbitmap_wor= d *map, return nr; } =20 +static unsigned long sbitmap_find_bits_in_word(struct sbitmap_word *map, + unsigned int map_depth, int nr_tags, unsigned long *nr) +{ + unsigned long val, bit_nr, get_mask; + + while (1) { + val =3D READ_ONCE(map->word); + if (val =3D=3D (1UL << (map_depth - 1)) - 1) { + if (!sbitmap_deferred_clear(map, 0, 0, 0)) + return 0; + continue; + } + + bit_nr =3D find_first_zero_bit(&val, map_depth); + + /* Ensure that the lengths of get_mask and val are consistent + * to avoid NULL pointer dereference + */ + if (bit_nr + nr_tags <=3D map_depth) + break; + + if (!sbitmap_deferred_clear(map, 0, 0, 0)) + return 0; + }; + + atomic_long_t *ptr =3D (atomic_long_t *) &map->word; + + get_mask =3D ((1UL << nr_tags) - 1) << bit_nr; + while (!atomic_long_try_cmpxchg(ptr, &val, + get_mask | val)) + ; + get_mask =3D (get_mask & ~val) >> bit_nr; + + *nr =3D bit_nr; + return get_mask; +} + static unsigned int __map_depth_with_shallow(const struct sbitmap *sb, int index, unsigned int shallow_depth) @@ -517,7 +554,7 @@ unsigned long __sbitmap_queue_get_batch(struct sbitmap_= queue *sbq, int nr_tags, { struct sbitmap *sb =3D &sbq->sb; unsigned int hint, depth; - unsigned long index, nr; + unsigned long index; int i; =20 if (unlikely(sb->round_robin)) @@ -530,32 +567,18 @@ unsigned long __sbitmap_queue_get_batch(struct sbitma= p_queue *sbq, int nr_tags, =20 for (i =3D 0; i < sb->map_nr; i++) { struct sbitmap_word *map =3D &sb->map[index]; - unsigned long get_mask; + unsigned long get_mask, nr; unsigned int map_depth =3D __map_depth(sb, index); - unsigned long val; =20 - sbitmap_deferred_clear(map, 0, 0, 0); - val =3D READ_ONCE(map->word); - if (val =3D=3D (1UL << (map_depth - 1)) - 1) - goto next; - - nr =3D find_first_zero_bit(&val, map_depth); - if (nr + nr_tags <=3D map_depth) { - atomic_long_t *ptr =3D (atomic_long_t *) &map->word; - - get_mask =3D ((1UL << nr_tags) - 1) << nr; - while (!atomic_long_try_cmpxchg(ptr, &val, - get_mask | val)) - ; - get_mask =3D (get_mask & ~val) >> nr; - if (get_mask) { - *offset =3D nr + (index << sb->shift); - update_alloc_hint_after_get(sb, depth, hint, - *offset + nr_tags - 1); - return get_mask; - } + get_mask =3D sbitmap_find_bits_in_word(map, map_depth, nr_tags, &nr); + + if (get_mask) { + *offset =3D nr + (index << sb->shift); + update_alloc_hint_after_get(sb, depth, hint, + *offset + nr_tags - 1); + return get_mask; } -next: + /* Jump to next index. */ if (++index >=3D sb->map_nr) index =3D 0; --=20 2.34.1