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; From patchwork Tue Nov 15 22:45:52 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: 20624 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a5d:6687:0:0:0:0:0 with SMTP id l7csp2978141wru; Tue, 15 Nov 2022 14:49:24 -0800 (PST) X-Google-Smtp-Source: AA0mqf4wuCLMj4xUWCwZlvn5vGg8f7DIUTLRU39XIAjnGixNYR+FH9sp/6IMB4Sbewbb7/+rUklU X-Received: by 2002:a05:6402:653:b0:458:7758:7ed1 with SMTP id u19-20020a056402065300b0045877587ed1mr16339494edx.315.1668552564425; Tue, 15 Nov 2022 14:49:24 -0800 (PST) ARC-Seal: i=1; a=rsa-sha256; t=1668552564; cv=none; d=google.com; s=arc-20160816; b=kmHvNtHV+nu5FkjSUEEhRjdVsIsWe3m52zvCfR5xDK2QWD5O63FLg7g7h7QpmPSxZi zNxgCLJ575/eS/8APx6WCuvE5KvVMinU31aYDt7xeQYRHQhBCK6hGZ8au6ZtDjIxQmUm TpclFlWjtVWK4qEms1eSud4VeIunqhwYh+iaBpv2QjWYVMIPSJ1XhkljVNblvCsjt2fz dGKZs8wBZhvZ8V9+iJ78uBBsyXKEPwXfqfPFobLwR4inpkjSJbgDIPIEqWqDKDR9igQM CjzuPN23KtEDlAr96zmJcVZsorfHKC0+MX8RlSeAHK2ALVGqykdUjy6s4QBPk09hBpki 9xcQ== 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=i4p+Bf1ZB3EMXcVQfO03WbaDQ0+xCKIhIBXxIum+x8w=; b=Yb5HdJVSTrNRLm+WRoVgL5lFIN6hIgm4CeOSc9qluZiW8VKrrIUjfwug8XcgQMKa+6 FuxBGGDD4pE46cjiOoRgSNdP7pjtXXn/YutuhmoqbcST8Uc/9eS7MH7hH4JhxvUb4Y/k 2F/mFOIFtHA//qbgXgDJQE1qhXDpyN8ZBw1SeYQj2+1nrRIGVOlmQpFJ4u8JLstPDs2M ++R8Ohv+KRgEWwR+aKsHFeILt8PwUAIlar+yxEBuiVOBQ4H8plFNhVDd1M76niPJTytW N9mcsBt+emS+gJPWjqtMdwvUgvUddALVN/hqxW19CqKGxTLdpHxAp5Gx7YmZaqDYsdX4 P02g== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@suse.de header.s=susede2_rsa header.b=h58UqQnz; dkim=neutral (no key) header.i=@suse.de header.s=susede2_ed25519; 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 e3-20020a50a683000000b00461d5afea01si13494129edc.165.2022.11.15.14.49.00; Tue, 15 Nov 2022 14:49:24 -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=h58UqQnz; dkim=neutral (no key) header.i=@suse.de header.s=susede2_ed25519; 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 S232040AbiKOWqV (ORCPT + 99 others); Tue, 15 Nov 2022 17:46:21 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:43128 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S231913AbiKOWqO (ORCPT ); Tue, 15 Nov 2022 17:46:14 -0500 Received: from smtp-out2.suse.de (smtp-out2.suse.de [195.135.220.29]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id EDA201F9DA; Tue, 15 Nov 2022 14:46:11 -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-out2.suse.de (Postfix) with ESMTPS id AD50920A5E; Tue, 15 Nov 2022 22:46:10 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=suse.de; s=susede2_rsa; t=1668552370; 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=i4p+Bf1ZB3EMXcVQfO03WbaDQ0+xCKIhIBXxIum+x8w=; b=h58UqQnzUH6hYBmuAOffZG1ph12ApvePMQMxwfMqxYG7pzxE1cOc6bgOc1Vp7KB+y87Irq HOQfNpEd1tw5qxs71+IxhwW/J5CPYYRNykz/b2oBrLKO0u7ltJUDFb//i1hB0arjGmiBS2 QKE9ZAvIMFqzrJb8R00e5r1zPpXKGuc= DKIM-Signature: v=1; a=ed25519-sha256; c=relaxed/relaxed; d=suse.de; s=susede2_ed25519; t=1668552370; 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=i4p+Bf1ZB3EMXcVQfO03WbaDQ0+xCKIhIBXxIum+x8w=; b=2uWtfTyuS96Crx4LlR88t0aGB3ngLNKGMOijm+WmBufIMPo0nlI9pjuH+IxnmJA0fb7gwI Vqrym3FAKWk5jABg== 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 0F1B313273; Tue, 15 Nov 2022 22:46:09 +0000 (UTC) Received: from dovecot-director2.suse.de ([192.168.254.65]) by imap2.suse-dmz.suse.de with ESMTPSA id yGbdK7EWdGPsSwAAMHmgww (envelope-from ); Tue, 15 Nov 2022 22:46:09 +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 2/3] wait: Return number of exclusive waiters awaken Date: Tue, 15 Nov 2022 17:45:52 -0500 Message-Id: <20221115224553.23594-3-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?1749604174087062120?= X-GMAIL-MSGID: =?utf-8?q?1749604174087062120?= Sbitmap code will need to know how many waiters were actually woken for its batched wakeups implementation. Return the number of woken exclusive waiters from __wake_up() to facilitate that. Suggested-by: Jan Kara Signed-off-by: Gabriel Krisman Bertazi Reviewed-by: Jan Kara Acked-by: Peter Zijlstra (Intel) --- include/linux/wait.h | 2 +- kernel/sched/wait.c | 18 +++++++++++------- 2 files changed, 12 insertions(+), 8 deletions(-) diff --git a/include/linux/wait.h b/include/linux/wait.h index 7f5a51aae0a7..a0307b516b09 100644 --- a/include/linux/wait.h +++ b/include/linux/wait.h @@ -209,7 +209,7 @@ __remove_wait_queue(struct wait_queue_head *wq_head, struct wait_queue_entry *wq list_del(&wq_entry->entry); } -void __wake_up(struct wait_queue_head *wq_head, unsigned int mode, int nr, void *key); +int __wake_up(struct wait_queue_head *wq_head, unsigned int mode, int nr, void *key); void __wake_up_locked_key(struct wait_queue_head *wq_head, unsigned int mode, void *key); void __wake_up_locked_key_bookmark(struct wait_queue_head *wq_head, unsigned int mode, void *key, wait_queue_entry_t *bookmark); diff --git a/kernel/sched/wait.c b/kernel/sched/wait.c index 9860bb9a847c..133b74730738 100644 --- a/kernel/sched/wait.c +++ b/kernel/sched/wait.c @@ -121,11 +121,12 @@ static int __wake_up_common(struct wait_queue_head *wq_head, unsigned int mode, return nr_exclusive; } -static void __wake_up_common_lock(struct wait_queue_head *wq_head, unsigned int mode, +static int __wake_up_common_lock(struct wait_queue_head *wq_head, unsigned int mode, int nr_exclusive, int wake_flags, void *key) { unsigned long flags; wait_queue_entry_t bookmark; + int remaining = nr_exclusive; bookmark.flags = 0; bookmark.private = NULL; @@ -134,10 +135,12 @@ static void __wake_up_common_lock(struct wait_queue_head *wq_head, unsigned int do { spin_lock_irqsave(&wq_head->lock, flags); - nr_exclusive = __wake_up_common(wq_head, mode, nr_exclusive, + remaining = __wake_up_common(wq_head, mode, remaining, wake_flags, key, &bookmark); spin_unlock_irqrestore(&wq_head->lock, flags); } while (bookmark.flags & WQ_FLAG_BOOKMARK); + + return nr_exclusive - remaining; } /** @@ -147,13 +150,14 @@ static void __wake_up_common_lock(struct wait_queue_head *wq_head, unsigned int * @nr_exclusive: how many wake-one or wake-many threads to wake up * @key: is directly passed to the wakeup function * - * If this function wakes up a task, it executes a full memory barrier before - * accessing the task state. + * If this function wakes up a task, it executes a full memory barrier + * before accessing the task state. Returns the number of exclusive + * tasks that were awaken. */ -void __wake_up(struct wait_queue_head *wq_head, unsigned int mode, - int nr_exclusive, void *key) +int __wake_up(struct wait_queue_head *wq_head, unsigned int mode, + int nr_exclusive, void *key) { - __wake_up_common_lock(wq_head, mode, nr_exclusive, 0, key); + return __wake_up_common_lock(wq_head, mode, nr_exclusive, 0, key); } EXPORT_SYMBOL(__wake_up); From patchwork Tue Nov 15 22:45:53 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: 20625 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a5d:6687:0:0:0:0:0 with SMTP id l7csp2978267wru; Tue, 15 Nov 2022 14:49:53 -0800 (PST) X-Google-Smtp-Source: AA0mqf6RmGyO0GCq9wklAe8Nx9F+y3CHofN0lXNLN8vAns/ryCosMlW0zG69rHGNm1eGDiKsrcTz X-Received: by 2002:a17:907:6748:b0:7ae:bfeb:f484 with SMTP id qm8-20020a170907674800b007aebfebf484mr16262444ejc.174.1668552593459; Tue, 15 Nov 2022 14:49:53 -0800 (PST) ARC-Seal: i=1; a=rsa-sha256; t=1668552593; cv=none; d=google.com; s=arc-20160816; b=wtGbmOv+E9ydQLILrLyen5HJeWD1BTjtcdsl0nJqGBx73DoB4lkzFR8tWoT3ambSeC MwNnLShvIr9N5lvLexJzumj1d4hNCaR1JiO78yux3mD6j9L/d/F147ZxC4RL2ue3wWiY TJZjRdrIClbm0kvisDKlYDkbN1OnGMCTUS38yeQIZuZyqkXepTCmwvA3V9SvWSS9xo1A pYk+2TUAQ4yEBTYl4GxDfFg2gs5693NdglZfE2wY3DWE+EIhIeBmMTEWph+bfnUjhQDn p1AQpAa2pswxnv8uu9qH5TvUmk3oSaTC+DLhX+Wgwr8Krl59XtZTGhW3mKwZpqcoH8CH Mbug== 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=d3jRfb3u2UMhELX3RFNE2yKyqYVqcOMcurpZIDpUfqQ=; b=WHtfR4RHm3SwvCqfr2mDyksVbY+LhL/b9fpiaWvg3dTUAhX9TMIFVhuJYmVr+Fd4JY kJ6c1bo4c3XuTkk+1cc96j3DnRSXihwEFT2VgzsSAW3chL5cI5fC4A/RgKEVB4yAnnR1 AF/vU7Azv9RBAL0UA+r9/8kAYlobRQqhmrrgaxDwsUoWfc17aNOzl+4O1qtwxkCqJPHM V6imc9ZN2oZKFzbY14w0PEiQVakjeQQMFYSOBs1ehIwcDgwQKhknrjz0sr+YDK+6vO+1 T5C57654wFiVr636k/IR/nIbZ01LmE5GtKDwsedZbDNps8sK/zSah9pAO+e8yiJeZKAg 3ofg== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@suse.de header.s=susede2_rsa header.b=ICr7+Pbd; 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 hs24-20020a1709073e9800b007ab1b8b719csi15007811ejc.0.2022.11.15.14.49.29; Tue, 15 Nov 2022 14:49:53 -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=ICr7+Pbd; 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 S232296AbiKOWq1 (ORCPT + 99 others); Tue, 15 Nov 2022 17:46:27 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:43276 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S231754AbiKOWqT (ORCPT ); Tue, 15 Nov 2022 17:46:19 -0500 Received: from smtp-out2.suse.de (smtp-out2.suse.de [IPv6:2001:67c:2178:6::1d]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 147B61FCFE; Tue, 15 Nov 2022 14:46:15 -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-out2.suse.de (Postfix) with ESMTPS id 7A5CF20A90; Tue, 15 Nov 2022 22:46:14 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=suse.de; s=susede2_rsa; t=1668552374; 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=d3jRfb3u2UMhELX3RFNE2yKyqYVqcOMcurpZIDpUfqQ=; b=ICr7+PbdeP+cvI4LbyR8wehVSKXI9D+8UYj/5EI5AZlluzxdnsPEZEd1qGvXKzSRNwdWEr 3+iX//2sCDWNtPdX61Ol2e1nAgZu7aUFQtYsYgMWy5NTcfMyT56IdlHqUfIoPx/JnyVmvA SbBZmECalYSPPyWnXXAK1mCm2KXGpBs= DKIM-Signature: v=1; a=ed25519-sha256; c=relaxed/relaxed; d=suse.de; s=susede2_ed25519; t=1668552374; 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=d3jRfb3u2UMhELX3RFNE2yKyqYVqcOMcurpZIDpUfqQ=; b=a5XL0CFX5ESUe67zQsjAkZjjyX5RwRLma+q2/quZ8SEzsSCciMKWsyEY+8PctohwjOaoRd XgjXOpMSoqafK9DQ== 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 D122213273; Tue, 15 Nov 2022 22:46:13 +0000 (UTC) Received: from dovecot-director2.suse.de ([192.168.254.65]) by imap2.suse-dmz.suse.de with ESMTPSA id nvQtI7UWdGPzSwAAMHmgww (envelope-from ); Tue, 15 Nov 2022 22:46:13 +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 3/3] sbitmap: Try each queue to wake up at least one waiter Date: Tue, 15 Nov 2022 17:45:53 -0500 Message-Id: <20221115224553.23594-4-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?1749604204406055340?= X-GMAIL-MSGID: =?utf-8?q?1749604204406055340?= Jan reported the new algorithm as merged might be problematic if the queue being awaken becomes empty between the waitqueue_active inside sbq_wake_ptr check and the wake up. If that happens, wake_up_nr will not wake up any waiter and we loose too many wake ups. In order to guarantee progress, we need to wake up at least one waiter here, if there are any. This now requires trying to wake up from every queue. Instead of walking through all the queues with sbq_wake_ptr, this call moves the wake up inside that function. In a previous version of the patch, I found that updating wake_index several times when walking through queues had a measurable overhead. This ensures we only update it once, at the end. Fixes: 4f8126bb2308 ("sbitmap: Use single per-bitmap counting to wake up queued tags") Reported-by: Jan Kara Signed-off-by: Gabriel Krisman Bertazi Reviewed-by: Jan Kara --- lib/sbitmap.c | 28 ++++++++++++---------------- 1 file changed, 12 insertions(+), 16 deletions(-) diff --git a/lib/sbitmap.c b/lib/sbitmap.c index bea7984f7987..586deb333237 100644 --- a/lib/sbitmap.c +++ b/lib/sbitmap.c @@ -560,12 +560,12 @@ void sbitmap_queue_min_shallow_depth(struct sbitmap_queue *sbq, } EXPORT_SYMBOL_GPL(sbitmap_queue_min_shallow_depth); -static struct sbq_wait_state *sbq_wake_ptr(struct sbitmap_queue *sbq) +static void __sbitmap_queue_wake_up(struct sbitmap_queue *sbq, int nr) { int i, wake_index; if (!atomic_read(&sbq->ws_active)) - return NULL; + return; wake_index = atomic_read(&sbq->wake_index); for (i = 0; i < SBQ_WAIT_QUEUES; i++) { @@ -579,20 +579,22 @@ static struct sbq_wait_state *sbq_wake_ptr(struct sbitmap_queue *sbq) */ 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; - } + /* + * It is sufficient to wake up at least one waiter to + * guarantee forward progress. + */ + if (waitqueue_active(&ws->wait) && + wake_up_nr(&ws->wait, nr)) + break; } - return NULL; + if (wake_index != atomic_read(&sbq->wake_index)) + atomic_set(&sbq->wake_index, wake_index); } void sbitmap_queue_wake_up(struct sbitmap_queue *sbq, int nr) { unsigned int wake_batch = READ_ONCE(sbq->wake_batch); - struct sbq_wait_state *ws = NULL; unsigned int wakeups; if (!atomic_read(&sbq->ws_active)) @@ -604,16 +606,10 @@ void sbitmap_queue_wake_up(struct sbitmap_queue *sbq, int nr) do { if (atomic_read(&sbq->completion_cnt) - wakeups < wake_batch) return; - - if (!ws) { - ws = sbq_wake_ptr(sbq); - if (!ws) - return; - } } while (!atomic_try_cmpxchg(&sbq->wakeup_cnt, &wakeups, wakeups + wake_batch)); - wake_up_nr(&ws->wait, wake_batch); + __sbitmap_queue_wake_up(sbq, wake_batch); } EXPORT_SYMBOL_GPL(sbitmap_queue_wake_up);