From patchwork Thu Jul 27 15:20:18 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Chengming Zhou X-Patchwork-Id: 127048 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a59:a985:0:b0:3e4:2afc:c1 with SMTP id t5csp1212665vqo; Thu, 27 Jul 2023 09:19:00 -0700 (PDT) X-Google-Smtp-Source: APBJJlFtc+WYQxnYyh0BtT5BN2eZkoWvcCB5Jk1QVE9tIdCQjRzOC/C2D7T11/aychiSWNsskAh3 X-Received: by 2002:a17:907:7712:b0:99b:d178:f051 with SMTP id kw18-20020a170907771200b0099bd178f051mr2706022ejc.64.1690474739868; Thu, 27 Jul 2023 09:18:59 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1690474739; cv=none; d=google.com; s=arc-20160816; b=0cb2GbFrXc7WgfMw6kSvKtlCw67yogVtwJcfxZbVrrcAJieeg6l+knW2gggkM5f2Yj 6tueeU4ZdsxspGdFe9OlrXgLa8LXOik8EYzoyBnVSt85hei4n7JNtd2xGdJfiNzxu/Zi uvNnQrxnf7MejsqSEHsOW8Z9AVIzNp6M6Iqr/VX8WoFgl/01nLikX/9/vbJ26qu4kQlH OwJbFjiFZgbhlMOYIoEjhng9KfKILwneJWeBQ7u4w28FSXKW6YeeOir8qODFn8Q2yXT8 9uS2xIiBSpZSjCvRi4v3qdqn0PJUpY+6aF02fjuRDvo/PDqw9qiKi0P8u5GkUzGpZhh6 Oi8Q== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=list-id:precedence:content-transfer-encoding:mime-version :message-id:date:subject:cc:to:from:dkim-signature; bh=IlwsvGNRJnMmWnx4X81rM4zHsMyVpGxID3lfp4Wm+1A=; fh=CVBJz1nv1DiM00KSAFXpoDdrembP9EJZsKRDNKymLtw=; b=vvNzqlXdxb6KlIGTb49Hdk05lxOnE5eD7/vTWl/JnizjKUG64GMnfjCN9Hv4DtlpIZ MZ4SmE6zG/uwMIjWbCTvFeI6RPuGQ2UZJeOaRJbgWPgzQY33KUAA0GPqJHYjY1D/aasc KjC2CG0hAnHUg+eIExVMXabH969BfqXaDjXWJP4uEaE2CwHjS6d8THESipkuAKlGuWrA 5/wus2HDJ+kfYfaRtCTGEq4RlUNOJu0WLmB8pSQ3BCN8pOwYffo0MDqWDHgViOLVaqmJ aS4PYdgI+fvHaaGDcfbOoQSJf441axi9Mt20dKwDta0tz8Cq2C6Q6/yQCriZ29gFYSvL /eNw== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@linux.dev header.s=key1 header.b="UnKls/jj"; spf=pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org; dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=linux.dev Received: from out1.vger.email (out1.vger.email. [2620:137:e000::1:20]) by mx.google.com with ESMTP id gq14-20020a170906e24e00b00993949aad30si912598ejb.37.2023.07.27.09.18.33; Thu, 27 Jul 2023 09:18:59 -0700 (PDT) Received-SPF: pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) client-ip=2620:137:e000::1:20; Authentication-Results: mx.google.com; dkim=pass header.i=@linux.dev header.s=key1 header.b="UnKls/jj"; spf=pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org; dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=linux.dev Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S234528AbjG0PVp (ORCPT + 99 others); Thu, 27 Jul 2023 11:21:45 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:35376 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S234561AbjG0PVm (ORCPT ); Thu, 27 Jul 2023 11:21:42 -0400 Received: from out-116.mta0.migadu.com (out-116.mta0.migadu.com [91.218.175.116]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 6B11130C5 for ; Thu, 27 Jul 2023 08:21:37 -0700 (PDT) X-Report-Abuse: Please report any abuse attempt to abuse@migadu.com and include these headers. DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=linux.dev; s=key1; t=1690471295; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:cc:mime-version:mime-version: content-transfer-encoding:content-transfer-encoding; bh=IlwsvGNRJnMmWnx4X81rM4zHsMyVpGxID3lfp4Wm+1A=; b=UnKls/jjqZcZzftvuk3ljzIPLwoprqIWOu7LoFbkkVSAIBhLiG4rj7MDXbC/wSvtMI359l N6V7bn3EnXoWjtBGCXe0jAO/FTTa0piMOgDtLsfDpCDWkAJsdhdkz/EHKYdP3PVjE+UdzQ hRtC43R6653je6/DHV9wtgV6FW0mNXk= From: chengming.zhou@linux.dev To: axboe@kernel.dk, osandov@fb.com, ming.lei@redhat.com, kbusch@kernel.org, krisman@suse.de Cc: linux-block@vger.kernel.org, linux-kernel@vger.kernel.org, zhouchengming@bytedance.com Subject: [PATCH v2 1/3] sbitmap: fix hint wrap in the failure case Date: Thu, 27 Jul 2023 23:20:18 +0800 Message-ID: <20230727152020.3633009-1-chengming.zhou@linux.dev> MIME-Version: 1.0 X-Migadu-Flow: FLOW_OUT X-Spam-Status: No, score=-2.1 required=5.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,DKIM_VALID_EF,SPF_HELO_NONE,SPF_PASS, T_SCC_BODY_TEXT_LINE autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on lindbergh.monkeyblade.net Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org X-getmail-retrieved-from-mailbox: INBOX X-GMAIL-THRID: 1772591240811883189 X-GMAIL-MSGID: 1772591240811883189 From: Chengming Zhou ``` hint = nr + 1; if (hint >= depth - 1) hint = 0; ``` Now we wrap the hint to 0 in the failure case, but has two problems: 1. hint == depth - 1, is actually an available offset hint, in which case we shouldn't wrap hint to 0. 2. In the strict round_robin non-wrap case, we shouldn't wrap at all. ``` wrap = wrap && hint; ``` We only need to check wrap based on the original hint ( > 0), don't need to recheck the new hint which maybe updated in the failure case, which may cause second wrap. We set wrap to false after we wrap once to avoid repeated wrap, which is clearer than rechecking the hint. Signed-off-by: Chengming Zhou --- lib/sbitmap.c | 13 ++++++++++--- 1 file changed, 10 insertions(+), 3 deletions(-) diff --git a/lib/sbitmap.c b/lib/sbitmap.c index d0a5081dfd12..ac4027884765 100644 --- a/lib/sbitmap.c +++ b/lib/sbitmap.c @@ -149,7 +149,8 @@ static int __sbitmap_get_word(unsigned long *word, unsigned long depth, * offset to 0 in a failure case, so start from 0 to * exhaust the map. */ - if (hint && wrap) { + if (wrap) { + wrap = false; hint = 0; continue; } @@ -160,8 +161,14 @@ static int __sbitmap_get_word(unsigned long *word, unsigned long depth, break; hint = nr + 1; - if (hint >= depth - 1) - hint = 0; + if (unlikely(hint >= depth)) { + if (wrap) { + wrap = false; + hint = 0; + continue; + } + return -1; + } } return nr; From patchwork Thu Jul 27 15:20:19 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Chengming Zhou X-Patchwork-Id: 127042 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a59:a985:0:b0:3e4:2afc:c1 with SMTP id t5csp1206066vqo; Thu, 27 Jul 2023 09:09:11 -0700 (PDT) X-Google-Smtp-Source: APBJJlFIGreBfWNjNSxLV7Gu2V8VVF3UaBUc9W2rQeaWZ7ww7Q9WOS1+nvWgJclWxP9E8rklXRB9 X-Received: by 2002:a17:90b:378d:b0:267:6fd0:bd31 with SMTP id mz13-20020a17090b378d00b002676fd0bd31mr3881457pjb.7.1690474150866; Thu, 27 Jul 2023 09:09:10 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1690474150; cv=none; d=google.com; s=arc-20160816; b=P+lTKvOF9uaAiXYwECOBdbjK8C7fwndffeP4gvAWG2utEwFjqF829M0qwmptV0zdP1 dlHTH9D9vkC3lg5dGcy9u785Sag0oeGOoAyVF+BUOmgS93tOud4GGyKquENNAhXYe2Ef 59mzc7mqoJ3t+3TomLG9UAetb/R9gF9uogU1uefc7xduCqBlJvNKG+t6o83YaDmRNvJW L6AHzt6gt3U1FbmgeyirhlKHq+YdaSOtDHrKDd47nimres0e4LLs9beo58pk6V/wTtup QwX9GadABkBgfnWxT134eh9BO/vPBlKiopyQHENZ9kZ9kKyPh35ulPdhnsIZ3qbBuVUe BIVQ== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=list-id:precedence:content-transfer-encoding:mime-version :references:in-reply-to:message-id:date:subject:cc:to:from :dkim-signature; bh=/sKpoCtxUkYnH2WqkRrOBZ45YFGekx6TcrM1LcTi34Y=; fh=CVBJz1nv1DiM00KSAFXpoDdrembP9EJZsKRDNKymLtw=; b=XNi7zbDxqOu+SkgUGMMc2cp1FTq5kQ9nLx5BuH4JGaupcgIXEsifKF8gOjNVHiSas/ g+2Av5dxhISS8lmRmNAA6pyu0G/U8W68S6S06fuueP47uleFoV9r0qrC836avDBmU9mO 7yqb+Bjl6yqN7uxREhqClumcwlbxH+2lGv24TSenJ3OIun2O1wkqNPdg0Q/xd1ivBNMG PiPOKILNlW4ygDkmc1UpCTMEran4EEy28KSQEHlwRP9lo5yaeTn+VsmlNqQhQiROWeLa o3cF5+8kEvxmmyP05UzkMu3xgQA1/Vq8E9c8AoAjadbNxpi9WMPhWP4EtwWgwzmDiSUR Qq8A== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@linux.dev header.s=key1 header.b=GoAulQGy; spf=pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org; dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=linux.dev Received: from out1.vger.email (out1.vger.email. [2620:137:e000::1:20]) by mx.google.com with ESMTP id my18-20020a17090b4c9200b0026815fe629esi3214984pjb.70.2023.07.27.09.08.56; Thu, 27 Jul 2023 09:09:10 -0700 (PDT) Received-SPF: pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) client-ip=2620:137:e000::1:20; Authentication-Results: mx.google.com; dkim=pass header.i=@linux.dev header.s=key1 header.b=GoAulQGy; spf=pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org; dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=linux.dev Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S234570AbjG0PVt (ORCPT + 99 others); Thu, 27 Jul 2023 11:21:49 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:35534 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S233672AbjG0PVr (ORCPT ); Thu, 27 Jul 2023 11:21:47 -0400 Received: from out-94.mta0.migadu.com (out-94.mta0.migadu.com [91.218.175.94]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id D83F62D57 for ; Thu, 27 Jul 2023 08:21:41 -0700 (PDT) X-Report-Abuse: Please report any abuse attempt to abuse@migadu.com and include these headers. DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=linux.dev; s=key1; t=1690471299; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:cc:mime-version:mime-version: content-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references; bh=/sKpoCtxUkYnH2WqkRrOBZ45YFGekx6TcrM1LcTi34Y=; b=GoAulQGyGJtzXSa5IKoRcjIs0s8QPP3zFwnYNiNs+kPVJnExsYqEOYEtlR8fhSpj47xKUw YJMSo28qz6Ff2+WhW4F2MDPA7X0bZeGdSFiNNk7xJAPXm25ysAo4/ta6xcQFVsJP/ROKoX B4SM3TA0HMPPk371Wjn8U3jkybITGKc= From: chengming.zhou@linux.dev To: axboe@kernel.dk, osandov@fb.com, ming.lei@redhat.com, kbusch@kernel.org, krisman@suse.de Cc: linux-block@vger.kernel.org, linux-kernel@vger.kernel.org, zhouchengming@bytedance.com Subject: [PATCH v2 2/3] sbitmap: fix strict round-robin non-wrap with hint > 0 Date: Thu, 27 Jul 2023 23:20:19 +0800 Message-ID: <20230727152020.3633009-2-chengming.zhou@linux.dev> In-Reply-To: <20230727152020.3633009-1-chengming.zhou@linux.dev> References: <20230727152020.3633009-1-chengming.zhou@linux.dev> MIME-Version: 1.0 X-Migadu-Flow: FLOW_OUT X-Spam-Status: No, score=-2.1 required=5.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,DKIM_VALID_EF,RCVD_IN_DNSWL_BLOCKED, SPF_HELO_NONE,SPF_PASS,T_SCC_BODY_TEXT_LINE autolearn=unavailable autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on lindbergh.monkeyblade.net Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org X-getmail-retrieved-from-mailbox: INBOX X-GMAIL-THRID: 1772590623183005075 X-GMAIL-MSGID: 1772590623183005075 From: Chengming Zhou If we have alloc_hint > 0 and don't wrap, we need to recheck sb->map[index] with hint == 0 to exhaust the map. For example: we have 8 words to search, index == 4, hint > 0 In sb->map[4] word, we only search [hint, 63] bits in the first word search. Then we search left 7 words, the sb->map[4] [0, hint-1] bits aren't searched. This patch fix it by searching 9 words in this case, so we will search sb->map[4] the second time at last with hint == 0. Signed-off-by: Chengming Zhou --- lib/sbitmap.c | 10 +++++++++- 1 file changed, 9 insertions(+), 1 deletion(-) diff --git a/lib/sbitmap.c b/lib/sbitmap.c index ac4027884765..6e098a46be26 100644 --- a/lib/sbitmap.c +++ b/lib/sbitmap.c @@ -199,10 +199,18 @@ static int sbitmap_find_bit(struct sbitmap *sb, unsigned int alloc_hint, bool wrap) { + unsigned int map_nr = sb->map_nr; unsigned int i; int nr = -1; - for (i = 0; i < sb->map_nr; i++) { + /* + * If we have alloc_hint > 0 and don't wrap, we need to + * recheck sb->map[index] with hint == 0 to exhaust the map. + */ + if (alloc_hint && !wrap) + map_nr += 1; + + for (i = 0; i < map_nr; i++) { nr = sbitmap_find_bit_in_word(&sb->map[index], min_t(unsigned int, __map_depth(sb, index), From patchwork Thu Jul 27 15:20:20 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Chengming Zhou X-Patchwork-Id: 127043 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a59:a985:0:b0:3e4:2afc:c1 with SMTP id t5csp1207643vqo; Thu, 27 Jul 2023 09:11:24 -0700 (PDT) X-Google-Smtp-Source: APBJJlGBvXHZezPGNIlkyG2OJMJ4mwXQeuy58+zo/ldL2tJlZDnzOyaek7sxAlMoZPfeG+Fx04Wd X-Received: by 2002:a05:6a00:248a:b0:682:57f0:7c00 with SMTP id c10-20020a056a00248a00b0068257f07c00mr6228227pfv.3.1690474284011; Thu, 27 Jul 2023 09:11:24 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1690474283; cv=none; d=google.com; s=arc-20160816; b=V9EE+s+xvE/acN3poSBSANgBpsfAHdzaxoQKUDP1C9DjIjnNwMjq3MRT/NniVFrdoC /s2dlQD6lVRwSmr2da3VktM44Tni9cyE8A6rFiEE/sSFvZZD+Xb8Nyz/Pe4RfUn5NJag UEm9/FN6mQo2PSetGp2QDSTk5lD4+EUnA7HJ6zq+IRpXF+coiQ18KFucHIMyHLQc7xxk XMMiheTuAHPWFmXawu3sU3/X3WiLCAmrBtx5aOtTIccp6Tw1JCRdVbZYD9GBswwneRes 4UoU2oZQAaZWw1GXRy995Y/cS5j/oDAMSjCSeheD/3P6+O6KaxbSFPommjhoDBCiYgAX vQ3g== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=list-id:precedence:content-transfer-encoding:mime-version :references:in-reply-to:message-id:date:subject:cc:to:from :dkim-signature; bh=MHEGgdVdHj4vY18bdOXyRtJoqYQZlvIgYxDQJPuL59w=; fh=CVBJz1nv1DiM00KSAFXpoDdrembP9EJZsKRDNKymLtw=; b=wB6rsxGVhW9/XiLL5nEGIkVR8iI0wPdpxtccRuFXeoto8TX+FN3iUSj8omIMt8BwWk GDWV5LpB0swOTdYSvF/UodJ8nWHCUDLqQ16cVEyQl7o6M6DLnP8J8M2qrKvnJSbXI4jK cG7kNjto15FCEx0g2mlCDXorDYQR+lKiYVFFWyM2jTdbVi/k5ZFQM21iTIsri+RS5PyJ T/pEC68dZGgH9CSxSMgAdTVOfHCHOtd+J8HeDV8+nS8r7RRxE+/emG+4YOxlXC0qGelz Y0+sQmL+gqUidZYvMmV74/Z2uVKZp8s9TFws32C1yqjZ4oDZi6ObG1WMLqPzpFgJzF/t Gu4g== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@linux.dev header.s=key1 header.b="Vv/FGX69"; spf=pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org; dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=linux.dev Received: from out1.vger.email (out1.vger.email. [2620:137:e000::1:20]) by mx.google.com with ESMTP id y12-20020a056a00190c00b00668718e54c6si1610869pfi.202.2023.07.27.09.10.58; Thu, 27 Jul 2023 09:11:23 -0700 (PDT) Received-SPF: pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) client-ip=2620:137:e000::1:20; Authentication-Results: mx.google.com; dkim=pass header.i=@linux.dev header.s=key1 header.b="Vv/FGX69"; spf=pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org; dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=linux.dev Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S234572AbjG0PV6 (ORCPT + 99 others); Thu, 27 Jul 2023 11:21:58 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:35598 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S234539AbjG0PVw (ORCPT ); Thu, 27 Jul 2023 11:21:52 -0400 Received: from out-96.mta0.migadu.com (out-96.mta0.migadu.com [91.218.175.96]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 35A0B1FCF for ; Thu, 27 Jul 2023 08:21:45 -0700 (PDT) X-Report-Abuse: Please report any abuse attempt to abuse@migadu.com and include these headers. DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=linux.dev; s=key1; t=1690471303; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:cc:mime-version:mime-version: content-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references; bh=MHEGgdVdHj4vY18bdOXyRtJoqYQZlvIgYxDQJPuL59w=; b=Vv/FGX69XOHCDVN28FE8R9XfgBkvYOjRJ9IrvFT4uw+lvzw0cVFHnWmhOhZGe5DGQq4Vm6 xenzswl7kJ31dEbx9wuTzt3TmK2vDnonf0xi2V8MGao8+9SF3mSueeizHrtPzSG04Vm5+Z hNGBLEjRgjptwa72wdpo33hUSoujnnA= From: chengming.zhou@linux.dev To: axboe@kernel.dk, osandov@fb.com, ming.lei@redhat.com, kbusch@kernel.org, krisman@suse.de Cc: linux-block@vger.kernel.org, linux-kernel@vger.kernel.org, zhouchengming@bytedance.com Subject: [PATCH v2 3/3] sbitmap: drop wrap logic in __sbitmap_get_word() Date: Thu, 27 Jul 2023 23:20:20 +0800 Message-ID: <20230727152020.3633009-3-chengming.zhou@linux.dev> In-Reply-To: <20230727152020.3633009-1-chengming.zhou@linux.dev> References: <20230727152020.3633009-1-chengming.zhou@linux.dev> MIME-Version: 1.0 X-Migadu-Flow: FLOW_OUT X-Spam-Status: No, score=-2.1 required=5.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,DKIM_VALID_EF,SPF_HELO_NONE,SPF_PASS, T_SCC_BODY_TEXT_LINE autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on lindbergh.monkeyblade.net Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org X-getmail-retrieved-from-mailbox: INBOX X-GMAIL-THRID: 1772590762558049168 X-GMAIL-MSGID: 1772590762558049168 From: Chengming Zhou The complex wrap logic in __sbitmap_get_word() seems unnecessary: 1. Strict round-robin mode: wrap == false 1.1 hint == 0: we search sb->map_nr words, won't wrap 1.2 hint > 0: we search (sb->map_nr + 1) words, won't wrap 2. Non round-robin mode: wrap == true 2.1 hint == 0: we search sb->map_nr words, don't need wrap 2.2 hint > 0: we search sb->map_nr words, need wrap So 2.2 is the only reason we need wrap logic in __sbitmap_get_word(), the only user like 2.2 is __sbitmap_get_shallow(). __sbitmap_get_shallow() always set wrap == true no matter the sbitmap is round-robin or not, seems that it doesn't want strict round-robin tag in this limited case. We can remove 2.2 case by setting hint == 0 in __sbitmap_get_shallow(), since there is no point in looping twice in find_next_zero_bit() if we don't want strict round-robin tag for this case. Signed-off-by: Chengming Zhou --- lib/sbitmap.c | 47 +++++++++++++---------------------------------- 1 file changed, 13 insertions(+), 34 deletions(-) diff --git a/lib/sbitmap.c b/lib/sbitmap.c index 6e098a46be26..d042dc5d53c3 100644 --- a/lib/sbitmap.c +++ b/lib/sbitmap.c @@ -134,41 +134,21 @@ void sbitmap_resize(struct sbitmap *sb, unsigned int depth) EXPORT_SYMBOL_GPL(sbitmap_resize); static int __sbitmap_get_word(unsigned long *word, unsigned long depth, - unsigned int hint, bool wrap) + unsigned int hint) { int nr; - /* don't wrap if starting from 0 */ - wrap = wrap && hint; - while (1) { nr = find_next_zero_bit(word, depth, hint); - if (unlikely(nr >= depth)) { - /* - * We started with an offset, and we didn't reset the - * offset to 0 in a failure case, so start from 0 to - * exhaust the map. - */ - if (wrap) { - wrap = false; - hint = 0; - continue; - } + if (unlikely(nr >= depth)) return -1; - } if (!test_and_set_bit_lock(nr, word)) break; hint = nr + 1; - if (unlikely(hint >= depth)) { - if (wrap) { - wrap = false; - hint = 0; - continue; - } + if (unlikely(hint >= depth)) return -1; - } } return nr; @@ -176,14 +156,13 @@ static int __sbitmap_get_word(unsigned long *word, unsigned long depth, static int sbitmap_find_bit_in_word(struct sbitmap_word *map, unsigned int depth, - unsigned int alloc_hint, - bool wrap) + unsigned int alloc_hint) { int nr; do { nr = __sbitmap_get_word(&map->word, depth, - alloc_hint, wrap); + alloc_hint); if (nr != -1) break; if (!sbitmap_deferred_clear(map)) @@ -196,8 +175,7 @@ static int sbitmap_find_bit_in_word(struct sbitmap_word *map, static int sbitmap_find_bit(struct sbitmap *sb, unsigned int depth, unsigned int index, - unsigned int alloc_hint, - bool wrap) + unsigned int alloc_hint) { unsigned int map_nr = sb->map_nr; unsigned int i; @@ -207,7 +185,7 @@ static int sbitmap_find_bit(struct sbitmap *sb, * If we have alloc_hint > 0 and don't wrap, we need to * recheck sb->map[index] with hint == 0 to exhaust the map. */ - if (alloc_hint && !wrap) + if (alloc_hint) map_nr += 1; for (i = 0; i < map_nr; i++) { @@ -215,7 +193,7 @@ static int sbitmap_find_bit(struct sbitmap *sb, min_t(unsigned int, __map_depth(sb, index), depth), - alloc_hint, wrap); + alloc_hint); if (nr != -1) { nr += index << sb->shift; @@ -247,8 +225,7 @@ static int __sbitmap_get(struct sbitmap *sb, unsigned int alloc_hint) else alloc_hint = 0; - return sbitmap_find_bit(sb, UINT_MAX, index, alloc_hint, - !sb->round_robin); + return sbitmap_find_bit(sb, UINT_MAX, index, alloc_hint); } int sbitmap_get(struct sbitmap *sb) @@ -275,9 +252,11 @@ static int __sbitmap_get_shallow(struct sbitmap *sb, unsigned int index; index = SB_NR_TO_INDEX(sb, alloc_hint); - alloc_hint = SB_NR_TO_BIT(sb, alloc_hint); - return sbitmap_find_bit(sb, shallow_depth, index, alloc_hint, true); + /* No point in looping twice in find_next_zero_bit() for this case. */ + alloc_hint = 0; + + return sbitmap_find_bit(sb, shallow_depth, index, alloc_hint); } int sbitmap_get_shallow(struct sbitmap *sb, unsigned long shallow_depth)