From patchwork Thu May 31 14:45:05 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Paolo Valente X-Patchwork-Id: 137417 Delivered-To: patch@linaro.org Received: by 2002:a2e:9706:0:0:0:0:0 with SMTP id r6-v6csp6691338lji; Thu, 31 May 2018 07:45:39 -0700 (PDT) X-Google-Smtp-Source: ADUXVKIJFHp958Sd6ktiyw7JmyEOLLFU1qQbAgyceJASSFcnWYGic9x2bx+WmJXXrGlyaeLB6v5z X-Received: by 2002:a17:902:422:: with SMTP id 31-v6mr7466022ple.320.1527777939136; Thu, 31 May 2018 07:45:39 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1527777939; cv=none; d=google.com; s=arc-20160816; b=YrunI7jZz54sY+t6w64IqbZlaI765seCbZlSydGLdh4cSgbRtEiailjVCt93AiikB/ h8uXumnE18u/HzVQS8LiUctAPYvATCkoeuvMA6vvdmD5bl7mK5E+9Jt6sfZWnCbWbnfN 6l+kfUFNlGu54DaBE5d7ab9n/KHYSmsjr+0eih5Gwvtzt4rD5EFgno6lMOve7kvaTx04 kKo4G7euEW5wkW6H4omWUIpiIrfZor+lv+vEFQ1yE4n25+PjF9CTFEBGyh5dPs6C6JHL EIi0S5fyW3RmO0CA5fUzeCYF3fEAae7Rg8Lgq1JsLyYbPWjmCqOFbH1dpGRjfimJekO+ y/2g== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=list-id:precedence:sender:references:in-reply-to:message-id:date :subject:cc:to:from:dkim-signature:arc-authentication-results; bh=IFrDgLL2djABtcZVT/83HhEbvNP72Hw1DrJc+3k+XAk=; b=Ascdo7rxqOyzzFgttNxLybOgEp6zigd2Pr49BMWdKhvxrBjKAUG3Vmta22vqgSlaXQ avKyzSoNK0Dg5UqpMS9HRJJZRxV85STAVMmKDr4OCJBPN7hcBmFJf5bE0xjo/ZShW1tH DKFhjjuiUU3JgFmTMpwUak0UF5iPdIYtxAei6Nyx9MXB4zZU3QU5UAXUtu58aYRZ+zl8 5+ADyRi3sW5rlLWXVUK7OAWp84uPPNEWzV815gJRp49wjGi+J8iW/gB0edJ5aO/SJJk8 SKNJv+zI7j9zE8m/cIFoLywfWAf4QvJVZrwueBIpFbkAAAVhqnG0brwWeOS5f0N0FIVk Oe6A== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@linaro.org header.s=google header.b=YQdbOh2P; spf=pass (google.com: best guess record for domain of linux-kernel-owner@vger.kernel.org designates 209.132.180.67 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org; dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=linaro.org Return-Path: Received: from vger.kernel.org (vger.kernel.org. [209.132.180.67]) by mx.google.com with ESMTP id v8-v6si37009656plo.306.2018.05.31.07.45.38; Thu, 31 May 2018 07:45:39 -0700 (PDT) Received-SPF: pass (google.com: best guess record for domain of linux-kernel-owner@vger.kernel.org designates 209.132.180.67 as permitted sender) client-ip=209.132.180.67; Authentication-Results: mx.google.com; dkim=pass header.i=@linaro.org header.s=google header.b=YQdbOh2P; spf=pass (google.com: best guess record for domain of linux-kernel-owner@vger.kernel.org designates 209.132.180.67 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org; dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=linaro.org Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1755463AbeEaOpg (ORCPT + 30 others); Thu, 31 May 2018 10:45:36 -0400 Received: from mail-wr0-f195.google.com ([209.85.128.195]:40474 "EHLO mail-wr0-f195.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1755117AbeEaOpa (ORCPT ); Thu, 31 May 2018 10:45:30 -0400 Received: by mail-wr0-f195.google.com with SMTP id l41-v6so33329136wre.7 for ; Thu, 31 May 2018 07:45:29 -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; bh=IFrDgLL2djABtcZVT/83HhEbvNP72Hw1DrJc+3k+XAk=; b=YQdbOh2PNAjed89u+zit1vsprYVGY8gVgSWIjoxLRX2b5ZMBEUMzELtelBDbrRZC56 qBer9F3YY30gyD6r+xy81P+4qax+s1M9AVoHZ4q9l515xbsdcfoq7Tc13utK56OtLIQ0 Z4WmszDBdEna4fpHUUsT35Rm2+z6IZhZbuIIU= 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; bh=IFrDgLL2djABtcZVT/83HhEbvNP72Hw1DrJc+3k+XAk=; b=NC8NuP3ElXXti0gcK+DVFd8Kl3SjgjbtOYrI0DxgDBn8Ca1UuJpYgUZrdldAs3b6hy +TrW7ltN5jaCe0sBPIXwhLFl2prpWOIcokHOYf49ZhAxQI3r/eoGYUIWgMIIlzh7IfgS s0L4kzRYHM/Keyvg3IEcGyZTFX3dkO08G4SKaG6b/2PCrHw91yhzMKVVkSSDSn9tHtcM zasGCOA0iUeZDq+pgGHX2Y5J0koxv5SGWARDn9KBf5Sfd02ov4YxXpjtJGb+QjnvqA7Q AR4KynfbIHadvYh2m0RGRb59JDlme02kVk3IsDXBmhTX9Wk7xp/1w5ciZzgrRED9g/pR HtAQ== X-Gm-Message-State: ALKqPwel1oCc1QbeJqPL6KYBTV0UmB8c1hPIRlJQf8gPPq8UNu+CE9i1 UrobKc7S7NmLjTwDO8OIpEsaMQ== X-Received: by 2002:adf:a54a:: with SMTP id j10-v6mr6243312wrb.155.1527777928757; Thu, 31 May 2018 07:45:28 -0700 (PDT) Received: from localhost.localdomain (146-241-12-84.dyn.eolo.it. [146.241.12.84]) by smtp.gmail.com with ESMTPSA id y45-v6sm36106869wrd.97.2018.05.31.07.45.27 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Thu, 31 May 2018 07:45:27 -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, linus.walleij@linaro.org, bfq-iosched@googlegroups.com, oleksandr@natalenko.name, sapienza.dav@gmail.com, 177992@studenti.unimore.it, Paolo Valente Subject: [PATCH BUGFIX/IMPROVEMENTS 1/4] block, bfq: add description of weight-raising heuristics Date: Thu, 31 May 2018 16:45:05 +0200 Message-Id: <20180531144508.3927-2-paolo.valente@linaro.org> X-Mailer: git-send-email 2.16.1 In-Reply-To: <20180531144508.3927-1-paolo.valente@linaro.org> References: <20180531144508.3927-1-paolo.valente@linaro.org> Sender: linux-kernel-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org A description of how weight raising works is missing in BFQ sources. In addition, the code for handling weight raising is scattered across a few functions. This makes it rather hard to understand the mechanism and its rationale. This commits adds such a description at the beginning of the main source file. Signed-off-by: Paolo Valente --- block/bfq-iosched.c | 80 +++++++++++++++++++++++++++++++++++++---------------- 1 file changed, 56 insertions(+), 24 deletions(-) -- 2.16.1 diff --git a/block/bfq-iosched.c b/block/bfq-iosched.c index f71a5846b629..f3703e7431aa 100644 --- a/block/bfq-iosched.c +++ b/block/bfq-iosched.c @@ -49,9 +49,39 @@ * * In particular, to provide these low-latency guarantees, BFQ * explicitly privileges the I/O of two classes of time-sensitive - * applications: interactive and soft real-time. This feature enables - * BFQ to provide applications in these classes with a very low - * latency. Finally, BFQ also features additional heuristics for + * applications: interactive and soft real-time. In more detail, BFQ + * behaves this way if the low_latency parameter is set (default + * configuration). This feature enables BFQ to provide applications in + * these classes with a very low latency. + * + * To implement this feature, BFQ constantly tries to detect whether + * the I/O requests in a bfq_queue come from an interactive or a soft + * real-time application. For brevity, in these cases, the queue is + * said to be interactive or soft real-time. In both cases, BFQ + * privileges the service of the queue, over that of non-interactive + * and non-soft-real-time queues. This privileging is performed, + * mainly, by raising the weight of the queue. So, for brevity, we + * call just weight-raising periods the time periods during which a + * queue is privileged, because deemed interactive or soft real-time. + * + * The detection of soft real-time queues/applications is described in + * detail in the comments on the function + * bfq_bfqq_softrt_next_start. On the other hand, the detection of an + * interactive queue works as follows: a queue is deemed interactive + * if it is constantly non empty only for a limited time interval, + * after which it does become empty. The queue may be deemed + * interactive again (for a limited time), if it restarts being + * constantly non empty, provided that this happens only after the + * queue has remained empty for a given minimum idle time. + * + * By default, BFQ computes automatically the above maximum time + * interval, i.e., the time interval after which a constantly + * non-empty queue stops being deemed interactive. Since a queue is + * weight-raised while it is deemed interactive, this maximum time + * interval happens to coincide with the (maximum) duration of the + * weight-raising for interactive queues. + * + * Finally, BFQ also features additional heuristics for * preserving both a low latency and a high throughput on NCQ-capable, * rotational or flash-based devices, and to get the job done quickly * for applications consisting in many I/O-bound processes. @@ -61,14 +91,14 @@ * all low-latency heuristics for that device, by setting low_latency * to 0. * - * BFQ is described in [1], where also a reference to the initial, more - * theoretical paper on BFQ can be found. The interested reader can find - * in the latter paper full details on the main algorithm, as well as - * formulas of the guarantees and formal proofs of all the properties. - * With respect to the version of BFQ presented in these papers, this - * implementation adds a few more heuristics, such as the one that - * guarantees a low latency to soft real-time applications, and a - * hierarchical extension based on H-WF2Q+. + * BFQ is described in [1], where also a reference to the initial, + * more theoretical paper on BFQ can be found. The interested reader + * can find in the latter paper full details on the main algorithm, as + * well as formulas of the guarantees and formal proofs of all the + * properties. With respect to the version of BFQ presented in these + * papers, this implementation adds a few more heuristics, such as the + * ones that guarantee a low latency to interactive and soft real-time + * applications, and a hierarchical extension based on H-WF2Q+. * * B-WF2Q+ is based on WF2Q+, which is described in [2], together with * H-WF2Q+, while the augmented tree used here to implement B-WF2Q+ @@ -218,21 +248,23 @@ static struct kmem_cache *bfq_pool; #define BFQ_RATE_SHIFT 16 /* - * By default, BFQ computes the duration of the weight raising for - * interactive applications automatically, using the following formula: - * duration = (R / r) * T, where r is the peak rate of the device, and - * R and T are two reference parameters. - * In particular, R is the peak rate of the reference device (see - * below), and T is a reference time: given the systems that are - * likely to be installed on the reference device according to its - * speed class, T is about the maximum time needed, under BFQ and + * When configured for computing the duration of the weight-raising + * for interactive queues automatically (see the comments at the + * beginning of this file), BFQ does it using the following formula: + * duration = (R / r) * T, + * where r is the peak rate of the device, and R + * and T are two reference parameters. In particular, + * R is the peak rate of the reference device (see below), and + * T is a reference time: given the systems that are likely + * to be installed on the reference device according to its speed + * class, T is about the maximum time needed, under BFQ and * while reading two files in parallel, to load typical large * applications on these systems (see the comments on - * max_service_from_wr below, for more details on how T is obtained). - * In practice, the slower/faster the device at hand is, the more/less - * it takes to load applications with respect to the reference device. - * Accordingly, the longer/shorter BFQ grants weight raising to - * interactive applications. + * max_service_from_wr below, for more details on how T is + * obtained). In practice, the slower/faster the device at hand is, + * the more/less it takes to load applications with respect to the + * reference device. Accordingly, the longer/shorter BFQ grants + * weight raising to interactive applications. * * BFQ uses four different reference pairs (R, T), depending on: * . whether the device is rotational or non-rotational;