From patchwork Tue Nov 15 22:45:51 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Gabriel Krisman Bertazi X-Patchwork-Id: 20623 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a5d:6687:0:0:0:0:0 with SMTP id l7csp2978020wru; Tue, 15 Nov 2022 14:48:54 -0800 (PST) X-Google-Smtp-Source: AA0mqf4d98MC6ty59lEfRR5xe+Y06gvVZpj6EUwuZv19yE7wLWmtVDymp6rhZlori9j34vGcLhFj X-Received: by 2002:a17:906:f1c3:b0:7b2:86d6:292d with SMTP id gx3-20020a170906f1c300b007b286d6292dmr270924ejb.714.1668552534743; Tue, 15 Nov 2022 14:48:54 -0800 (PST) ARC-Seal: i=1; a=rsa-sha256; t=1668552534; cv=none; d=google.com; s=arc-20160816; b=PqTpGK9Ito2KwJASRR6nKOslzxFckHZah5aq+G3bh1YBmEi00V03TQ2yh9gzMWbsEr KUCPVq9bLvwSRubhae8+IcDGthdOCjvU8lbhQOwe4CynSHOvtjdKU6Fwdt/S/tey+Yqe T+VLkZM7iFxjV0rnV6uhMumlFTdk8U2/naIgUaZyfkM2fhLxgK3ALskoeSM0BuzVlYgc lVqVMo4g/YDeYAlaW/5NOaMB5lBPEZJ7f8WgvrEuecg3isbn5DrM/+rGQ3GmZ6g3ac/U NKoNsC7CQ9n0I57q+s/xSQr2z24axh4L4fopRI9aDmcZT1WAsxE3z0inOaTjLmbMXEpl iIOA== 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:dkim-signature; bh=IYrVaqsmS8b3jCtQozwiIPWEpoyeeH8SinlJYdcy0ko=; b=pqe9buOP5T9KS0jl+hMeF8eQ6jJPuNXhaEtBf/HBCaegU8nuZjv0dHKM/PVjQIGx/5 qjcZCXL9PAUKXVaa9dbJbuufGqA1pCtIpOOQGdejLt6Z7GYwJD0TooVANEO50ukl5BxS /JbkFXBH+lzfowFGlZlQjZYPgipCr/yIWUzTm6SxLz7qYMVxQjFGPpcHhFkIO1QYiCC6 JKVjaH30cW2JJGna6raReQh7oADVE7rY4vVmXHTGCk8XewRdPqj184ZcIfbpetN2j8QG Q9A+94ngJb87hdJWh5YpX127LnZVolF5KqxyCtQfqQwoSaEjyrEv2lKrthMvfBNFTpAU mvxw== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@suse.de header.s=susede2_rsa header.b=lylnNgvk; dkim=neutral (no key) header.i=@suse.de; 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=suse.de Received: from out1.vger.email (out1.vger.email. [2620:137:e000::1:20]) by mx.google.com with ESMTP id sd41-20020a1709076e2900b007a8beb3aa4csi14758341ejc.872.2022.11.15.14.48.30; Tue, 15 Nov 2022 14:48:54 -0800 (PST) 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=@suse.de header.s=susede2_rsa header.b=lylnNgvk; dkim=neutral (no key) header.i=@suse.de; 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=suse.de Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S231629AbiKOWqO (ORCPT + 99 others); Tue, 15 Nov 2022 17:46:14 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:43092 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S231521AbiKOWqK (ORCPT ); Tue, 15 Nov 2022 17:46:10 -0500 Received: from smtp-out1.suse.de (smtp-out1.suse.de [195.135.220.28]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 10CC51F623; Tue, 15 Nov 2022 14:46:08 -0800 (PST) Received: from imap2.suse-dmz.suse.de (imap2.suse-dmz.suse.de [192.168.254.74]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature ECDSA (P-521) server-digest SHA512) (No client certificate requested) by smtp-out1.suse.de (Postfix) with ESMTPS id C6F5A34318; Tue, 15 Nov 2022 22:46:06 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=suse.de; s=susede2_rsa; t=1668552366; h=from:from:reply-to: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=IYrVaqsmS8b3jCtQozwiIPWEpoyeeH8SinlJYdcy0ko=; b=lylnNgvkIbjdtaQ9et/CbJnSyquYdtzCSKuOBWIWt0UcfL2pkHMfFzlKPazE7jYTNfMiMJ v/ZMjL6hM3beSzbsHVHl8q+TGRtDgJRoPKuFg5wx+aJ3ABNgEcYO+dAOb4ViozPeNdUGPY 1jK+Ok3OuTLAx/eGRwsSHkwmilZXju0= DKIM-Signature: v=1; a=ed25519-sha256; c=relaxed/relaxed; d=suse.de; s=susede2_ed25519; t=1668552366; h=from:from:reply-to: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=IYrVaqsmS8b3jCtQozwiIPWEpoyeeH8SinlJYdcy0ko=; b=gbePz9b6hhi2tyEhmmJ7CShlR+h8KxYE4FaERpycstPN4ddmV9K9gwiCna5M1PHlByfzSa t9prs6macy3B8tDQ== Received: from imap2.suse-dmz.suse.de (imap2.suse-dmz.suse.de [192.168.254.74]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature ECDSA (P-521) server-digest SHA512) (No client certificate requested) by imap2.suse-dmz.suse.de (Postfix) with ESMTPS id 2A2B913273; Tue, 15 Nov 2022 22:46:05 +0000 (UTC) Received: from dovecot-director2.suse.de ([192.168.254.65]) by imap2.suse-dmz.suse.de with ESMTPSA id mvHfNa0WdGPcSwAAMHmgww (envelope-from ); Tue, 15 Nov 2022 22:46:05 +0000 From: Gabriel Krisman Bertazi To: axboe@kernel.dk Cc: mingo@redhat.com, peterz@infradead.org, jack@suse.cz, linux-kernel@vger.kernel.org, linux-block@vger.kernel.org, liusong@linux.alibaba.com, chaitanyak@nvidia.com, Gabriel Krisman Bertazi Subject: [PATCH 1/3] sbitmap: Advance the queue index before waking up a queue Date: Tue, 15 Nov 2022 17:45:51 -0500 Message-Id: <20221115224553.23594-2-krisman@suse.de> X-Mailer: git-send-email 2.35.3 In-Reply-To: <20221115224553.23594-1-krisman@suse.de> References: <20221115224553.23594-1-krisman@suse.de> MIME-Version: 1.0 X-Spam-Status: No, score=-4.4 required=5.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,DKIM_VALID_EF,RCVD_IN_DNSWL_MED,SPF_HELO_NONE, SPF_PASS 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: =?utf-8?q?INBOX?= X-GMAIL-THRID: =?utf-8?q?1749604142850372922?= X-GMAIL-MSGID: =?utf-8?q?1749604142850372922?= When a queue is awaken, the wake_index written by sbq_wake_ptr currently keeps pointing to the same queue. On the next wake up, it will thus retry the same queue, which is unfair to other queues, and can lead to starvation. This patch, moves the index update to happen before the queue is returned, such that it will now try a different queue first on the next wake up, improving fairness. Fixes: 4f8126bb2308 ("sbitmap: Use single per-bitmap counting to wake up queued tags") Reported-by: Jan Kara Reviewed-by: Jan Kara Signed-off-by: Gabriel Krisman Bertazi --- lib/sbitmap.c | 10 ++++++++-- 1 file changed, 8 insertions(+), 2 deletions(-) diff --git a/lib/sbitmap.c b/lib/sbitmap.c index eca462cba398..bea7984f7987 100644 --- a/lib/sbitmap.c +++ b/lib/sbitmap.c @@ -571,13 +571,19 @@ static struct sbq_wait_state *sbq_wake_ptr(struct sbitmap_queue *sbq) for (i = 0; i < SBQ_WAIT_QUEUES; i++) { struct sbq_wait_state *ws = &sbq->ws[wake_index]; + /* + * Advance the index before checking the current queue. + * It improves fairness, by ensuring the queue doesn't + * need to be fully emptied before trying to wake up + * from the next one. + */ + wake_index = sbq_index_inc(wake_index); + if (waitqueue_active(&ws->wait)) { if (wake_index != atomic_read(&sbq->wake_index)) atomic_set(&sbq->wake_index, wake_index); return ws; } - - wake_index = sbq_index_inc(wake_index); } return NULL;