From patchwork Mon Oct 9 11:11:23 2017 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Paolo Valente X-Patchwork-Id: 9992631 Return-Path: Received: from mail.wl.linuxfoundation.org (pdx-wl-mail.web.codeaurora.org [172.30.200.125]) by pdx-korg-patchwork.web.codeaurora.org (Postfix) with ESMTP id BE11360223 for ; Mon, 9 Oct 2017 11:11:55 +0000 (UTC) Received: from mail.wl.linuxfoundation.org (localhost [127.0.0.1]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id AF26B28791 for ; Mon, 9 Oct 2017 11:11:55 +0000 (UTC) Received: by mail.wl.linuxfoundation.org (Postfix, from userid 486) id A2A4C287A0; Mon, 9 Oct 2017 11:11:55 +0000 (UTC) X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on pdx-wl-mail.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-6.5 required=2.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,RCVD_IN_DNSWL_HI,RCVD_IN_SORBS_SPAM autolearn=unavailable version=3.3.1 Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id CC1CD28791 for ; Mon, 9 Oct 2017 11:11:54 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1751621AbdJILLl (ORCPT ); Mon, 9 Oct 2017 07:11:41 -0400 Received: from mail-wm0-f44.google.com ([74.125.82.44]:56709 "EHLO mail-wm0-f44.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1754084AbdJILLi (ORCPT ); Mon, 9 Oct 2017 07:11:38 -0400 Received: by mail-wm0-f44.google.com with SMTP id l68so22337775wmd.5 for ; Mon, 09 Oct 2017 04:11:38 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=linaro.org; s=google; h=from:to:cc:subject:date:message-id:in-reply-to:references :mime-version:content-transfer-encoding; bh=PQHw+EhzpxTLsXahNCcF7SXxTt/sXTMVQNapbLaWIJg=; b=Xyta2d9oQ6mvTFXyVw45pu0VN2aITOxFx05yCLXkNqX0wsG17NTiqmhczsu9XE21ui +G14ZdeiAzuAJJgxOjQmxtIC5nhe5Oa1CcHdw13BDDkbWfNTrGo/WA6AzRAgoLCFICCh WsB+dAZZ9axXNR4XZ5oIFgUAPEt8jqDN3DoX0= X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:from:to:cc:subject:date:message-id:in-reply-to :references:mime-version:content-transfer-encoding; bh=PQHw+EhzpxTLsXahNCcF7SXxTt/sXTMVQNapbLaWIJg=; b=BMWjFkVYVSWbfcBwAZTJp2RtJDVYxo0ZvRQ5HJcMc1pAENysO6NS5DHJAZ/AegLZvs MclmpnHEOkuwUenKJthzxw2VprRGNs9JFDQ2QpCdF3S1GQlotf87ocmWkB6XzNpIcfTW fkVAJ6xdEnMFJTF/yxwv3Al42UK4RUfeEcMCaBubitLyHerRIZqXErjq4P01ysM4xnol rkcAlQt1kmt8vLhg3yrtQsUEPxZ98bCYMPIGMdfXlzxT3TcD51mITy/dVO8ZOXyU+ex5 TBH6mVJJ+X1R+ezsqch2BqmDRAu9Efo0sXpVg/lviPy+XVm2DL1mv1yCILh2md48yF3D W31g== X-Gm-Message-State: AMCzsaVIi4sldf56iP/8twH+mI8zLzHt2YvmBW1mXvQLZ7z+5MIE2J93 vpzlLXr+P2hth8Yy5+YcGwX3GQ== X-Google-Smtp-Source: AOwi7QACv95bUMjjY0l+fUFYe2yZCrNIRh0SuiZiKrkOKHZAcKHateBdQpd66Zi2ugcx1+sWW93s1Q== X-Received: by 10.28.230.77 with SMTP id d74mr7320799wmh.75.1507547497491; Mon, 09 Oct 2017 04:11:37 -0700 (PDT) Received: from localhost.localdomain ([185.14.9.224]) by smtp.gmail.com with ESMTPSA id g136sm9119206wmd.40.2017.10.09.04.11.35 (version=TLS1 cipher=AES128-SHA bits=128/128); Mon, 09 Oct 2017 04:11:36 -0700 (PDT) From: Paolo Valente To: Jens Axboe Cc: linux-block@vger.kernel.org, linux-kernel@vger.kernel.org, ulf.hansson@linaro.org, broonie@kernel.org, lee.tibbert@gmail.com, oleksandr@natalenko.name, angeloruocco90@gmail.com, philm@manjaro.org, Paolo Valente Subject: [PATCH BUGFIX] block, bfq: fix unbalanced decrements of burst size Date: Mon, 9 Oct 2017 13:11:23 +0200 Message-Id: <20171009111123.2961-2-paolo.valente@linaro.org> X-Mailer: git-send-email 2.10.0 In-Reply-To: <20171009111123.2961-1-paolo.valente@linaro.org> References: <20171009111123.2961-1-paolo.valente@linaro.org> MIME-Version: 1.0 Sender: linux-block-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: linux-block@vger.kernel.org X-Virus-Scanned: ClamAV using ClamSMTP The commit "block, bfq: decrease burst size when queues in burst exit" introduced the decrement of burst_size on the removal of a bfq_queue from the burst list. Unfortunately, this decrement can happen to be performed even when burst size is already equal to 0, because of unbalanced decrements. A description follows of the cause of these unbalanced decrements, namely a wrong assumption, and of the way how this wrong assumption leads to unbalanced decrements. The wrong assumption is that a bfq_queue can exit only if the process associated with the bfq_queue has exited. This is false, because a bfq_queue, say Q, may exit also as a consequence of a merge with another bfq_queue. In this case, Q exits because the I/O of its associated process has been redirected to another bfq_queue. The decrement unbalance occurs because Q may then be re-created after a split, and added back to the current burst list, *without* incrementing burst_size. burst_size is not incremented because Q is not a new bfq_queue added to the burst list, but a bfq_queue only temporarily removed from the list, and, before the commit "bfq-sq, bfq-mq: decrease burst size when queues in burst exit", burst_size was not decremented when Q was removed. This commit addresses this issue by just checking whether the exiting bfq_queue is a merged bfq_queue, and, in that case, not decrementing burst_size. Unfortunately, this still leaves room for unbalanced decrements, in the following rarer case: on a split, the bfq_queue happens to be inserted into a different burst list than that it was removed from when merged. If this happens, the number of elements in the new burst list becomes higher than burst_size (by one). When the bfq_queue then exits, it is of course not in a merged state any longer, thus burst_size is decremented, which results in an unbalanced decrement. To handle this sporadic, unlucky case in a simple way, this commit also checks that burst_size is larger than 0 before decrementing it. Finally, this commit removes an useless, extra check: the check that the bfq_queue is sync, performed before checking whether the bfq_queue is in the burst list. This extra check is redundant, because only sync bfq_queues can be inserted into the burst list. Reported-by: Philip Müller Signed-off-by: Paolo Valente Signed-off-by: Angelo Ruocco Tested-by: Philip Müller Tested-by: Oleksandr Natalenko Tested-by: Lee Tibbert --- block/bfq-iosched.c | 59 +++++++++++++++++++++++++++++++++++++++++++++++++++-- 1 file changed, 57 insertions(+), 2 deletions(-) diff --git a/block/bfq-iosched.c b/block/bfq-iosched.c index 0d7272a..8689b24 100644 --- a/block/bfq-iosched.c +++ b/block/bfq-iosched.c @@ -3685,9 +3685,36 @@ void bfq_put_queue(struct bfq_queue *bfqq) if (bfqq->ref) return; - if (bfq_bfqq_sync(bfqq) && !hlist_unhashed(&bfqq->burst_list_node)) { + if (!hlist_unhashed(&bfqq->burst_list_node)) { hlist_del_init(&bfqq->burst_list_node); - bfqq->bfqd->burst_size--; + /* + * Decrement also burst size after the removal, if the + * process associated with bfqq is exiting, and thus + * does not contribute to the burst any longer. This + * decrement helps filter out false positives of large + * bursts, when some short-lived process (often due to + * the execution of commands by some service) happens + * to start and exit while a complex application is + * starting, and thus spawning several processes that + * do I/O (and that *must not* be treated as a large + * burst, see comments on bfq_handle_burst). + * + * In particular, the decrement is performed only if: + * 1) bfqq is not a merged queue, because, if it is, + * then this free of bfqq is not triggered by the exit + * of the process bfqq is associated with, but exactly + * by the fact that bfqq has just been merged. + * 2) burst_size is greater than 0, to handle + * unbalanced decrements. Unbalanced decrements may + * happen in te following case: bfqq is inserted into + * the current burst list--without incrementing + * bust_size--because of a split, but the current + * burst list is not the burst list bfqq belonged to + * (see comments on the case of a split in + * bfq_set_request). + */ + if (bfqq->bic && bfqq->bfqd->burst_size > 0) + bfqq->bfqd->burst_size--; } kmem_cache_free(bfq_pool, bfqq); @@ -4418,6 +4445,34 @@ static struct bfq_queue *bfq_get_bfqq_handle_split(struct bfq_data *bfqd, else { bfq_clear_bfqq_in_large_burst(bfqq); if (bic->was_in_burst_list) + /* + * If bfqq was in the current + * burst list before being + * merged, then we have to add + * it back. And we do not need + * to increase burst_size, as + * we did not decrement + * burst_size when we removed + * bfqq from the burst list as + * a consequence of a merge + * (see comments in + * bfq_put_queue). In this + * respect, it would be rather + * costly to know whether the + * current burst list is still + * the same burst list from + * which bfqq was removed on + * the merge. To avoid this + * cost, if bfqq was in a + * burst list, then we add + * bfqq to the current burst + * list without any further + * check. This can cause + * inappropriate insertions, + * but rarely enough to not + * harm the detection of large + * bursts significantly. + */ hlist_add_head(&bfqq->burst_list_node, &bfqd->burst_list); }