From patchwork Fri Sep 14 14:23:07 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Paolo Valente X-Patchwork-Id: 146700 Delivered-To: patch@linaro.org Received: by 2002:a2e:1648:0:0:0:0:0 with SMTP id 8-v6csp772819ljw; Fri, 14 Sep 2018 07:23:24 -0700 (PDT) X-Google-Smtp-Source: ANB0VdaW8Qkx8JBPqWeash1v/ShKfKMyoUqWGYmWMPJt+xrolZ+ySdProGN+5C8Nye6yLTEm0qU5 X-Received: by 2002:a63:5261:: with SMTP id s33-v6mr12123081pgl.313.1536935003967; Fri, 14 Sep 2018 07:23:23 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1536935003; cv=none; d=google.com; s=arc-20160816; b=GBcQVDr2d5ojiKOQc/7LWzB3lnf5ZzMH5VGdGzHDv24gqAMm85majXS9vYXZUWjIzL dn45GzQG3M5zNxDiBb5RZVw3eiNt9Fm9pm/DRUAc+FsZrpSyp2QDgyF5RENf6iMSNoq2 Pa1S2je0g/M74GhuL0+0pXuXxeTP6RTEkBQfdIEuKcQvdbmexkfdJhNsh2yMFkv5uMUt lJQWuL5iKKM0jahVe1hx82+NwjXKpkiHVRGMJESio2OVowwE4304ArW27WyKOuce64nA y9OksaIgkJ90HZ5738Lx9Jybk9GcqgwXQ1ppQTL1vNuhBFvAvrkkjs9z1BKAI8tnpo7I ltHg== 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; bh=rd8R49tSHe6GNNdxrka86f7ThsGMCBdbsdSM4u5ch9U=; b=AOSM4QM4OlFZUjV9CJWFX74B+Xs+Qh09Gysi3fApWAZY5fe+3RRMnhdo0LEfVPzbGN fDz44kjtkg1MiDS/2g1uld5WYyK8oVrSUrlFXCFEywDemTlTsAUttlE9qNFFOR+DI0Iy k2v7U0PsZmnKXgvbh38z1VGs72B2NZZMKo65qG7RhtLESnUKWF+7E6EJMN3FqGoAQ540 xLYpDzU38+PYfsnCda7Q57I0DPJqrRxzuRVxxEABZ0hj5uYQw+v6cCwRdC1IeindOqlU sEJr9IEisp7aUU5NnibtPUNvjx1qbVrTq4RLiNmtFDROfOSg7ZWgKFQaFsWbWZ8iDORA 4a5w== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@linaro.org header.s=google header.b=BTmY+DOv; 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 b66-v6si7452161pga.60.2018.09.14.07.23.23; Fri, 14 Sep 2018 07:23:23 -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=BTmY+DOv; 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 S1728230AbeINTiE (ORCPT + 32 others); Fri, 14 Sep 2018 15:38:04 -0400 Received: from mail-wr1-f67.google.com ([209.85.221.67]:44538 "EHLO mail-wr1-f67.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1728199AbeINTiE (ORCPT ); Fri, 14 Sep 2018 15:38:04 -0400 Received: by mail-wr1-f67.google.com with SMTP id v16-v6so10804355wro.11 for ; Fri, 14 Sep 2018 07:23:20 -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=rd8R49tSHe6GNNdxrka86f7ThsGMCBdbsdSM4u5ch9U=; b=BTmY+DOv8DiEIzGEBJX4RYWfTk/ZOXAwxG1eXFr6KPaJviJ3QBqi3DStYle0FMgmrL r7Ng47lpJf0ENMgzgGhvvVGCn3wy5zudPNNvoFs9PCymWb340uzsaMV6UN1y2JIakczL T7mbwvShfpS27whef0OAcbAhlzy+NF4PCSlJ0= 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=rd8R49tSHe6GNNdxrka86f7ThsGMCBdbsdSM4u5ch9U=; b=ZrmKh1E6Np9Y2EdXtUXc3Tnt6g3P5v3BtUbme/rANsoUtT205b0VCYtoiE5RWVugUt MTucwTShw/fslFfY8MXdDerOqOglS6Q2TlPJkOpcblAIEtdMmJqCWnCS+y5s4AM/ZOOn KcIUCD9JUvRelt+qVWZXB17SWgU29rRjfvoWwOSMVpwvF3vFFt1IEx+qX8FDPJzh4gib 23Qu+N7EDtrrSwv7nTXwFwgYRAR5yjCVBYqycoAzniTWre08uEGMXCqnAWX9TQ8KrP0T c15l0qWkCTYuLbpS+T2emV8q1E5cUbQKnKLJde2Sy4OkjyczmaObUL6DU0QJXKW0zoPb NGvg== X-Gm-Message-State: APzg51BaDb7Uu5rrvr3WFywUhsK+qrkDRVQSoWsAcgY6UvHO4ITvtJom 2G3mjYLoY9GP7usKP6M8jjeZow== X-Received: by 2002:a5d:448d:: with SMTP id j13-v6mr10052504wrq.236.1536934999666; Fri, 14 Sep 2018 07:23:19 -0700 (PDT) Received: from wifi-122_dhcprange-84.wifi.unimo.it (wifi-122_dhcprange-84.wifi.unimo.it. [155.185.122.84]) by smtp.gmail.com with ESMTPSA id k35-v6sm17084888wrc.14.2018.09.14.07.23.18 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Fri, 14 Sep 2018 07:23:18 -0700 (PDT) From: Paolo Valente To: Jens Axboe Cc: linux-block@vger.kernel.org, linux-kernel@vger.kernel.org, ulf.hansson@linaro.org, linus.walleij@linaro.org, broonie@kernel.org, bfq-iosched@googlegroups.com, oleksandr@natalenko.name, Paolo Valente Subject: [PATCH BUGFIX/IMPROVEMENT 1/3] block, bfq: correctly charge and reset entity service in all cases Date: Fri, 14 Sep 2018 16:23:07 +0200 Message-Id: <20180914142309.6789-2-paolo.valente@linaro.org> X-Mailer: git-send-email 2.16.1 In-Reply-To: <20180914142309.6789-1-paolo.valente@linaro.org> References: <20180914142309.6789-1-paolo.valente@linaro.org> Sender: linux-kernel-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org BFQ schedules entities (which represent either per-process queues or groups of queues) as a function of their timestamps. In particular, as a function of their (virtual) finish times. The finish time of an entity is computed as a function of the budget assigned to the entity, assuming, tentatively, that the entity, once in service, will receive an amount of service equal to its budget. Then, when the entity is expired because it finishes to be served, this finish time is updated as a function of the actual service received by the entity. This allows the entity to be correctly charged with only the service received, and then to be correctly re-scheduled. Yet an entity may receive service also while not being the entity in service (in the scheduling environment of its parent entity), for several reasons. If the entity remains with no backlog while receiving this 'unofficial' service, then it is expired. Also on such an expiration, the finish time of the entity should be updated to account for only the service actually received by the entity. Unfortunately, such an update is not performed for an entity expiring without being the entity in service. In a similar vein, the service counter of the entity in service is reset when the entity is expired, to be ready to be used for next service cycle. This reset too should be performed also in case an entity is expired because it remains empty after receiving service while not being the entity in service. But in this case the reset is not performed. This commit performs the above update of the finish time and reset of the service received, also for an entity expiring while not being the entity in service. Signed-off-by: Paolo Valente --- block/bfq-wf2q.c | 13 ++++++++++--- 1 file changed, 10 insertions(+), 3 deletions(-) -- 2.16.1 diff --git a/block/bfq-wf2q.c b/block/bfq-wf2q.c index ae52bff43ce4..ff7c2d470bb8 100644 --- a/block/bfq-wf2q.c +++ b/block/bfq-wf2q.c @@ -1181,10 +1181,17 @@ bool __bfq_deactivate_entity(struct bfq_entity *entity, bool ins_into_idle_tree) st = bfq_entity_service_tree(entity); is_in_service = entity == sd->in_service_entity; - if (is_in_service) { - bfq_calc_finish(entity, entity->service); + bfq_calc_finish(entity, entity->service); + + if (is_in_service) sd->in_service_entity = NULL; - } + else + /* + * Non in-service entity: nobody will take care of + * resetting its service counter on expiration. Do it + * now. + */ + entity->service = 0; if (entity->tree == &st->active) bfq_active_extract(st, entity); From patchwork Fri Sep 14 14:23:08 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Paolo Valente X-Patchwork-Id: 146701 Delivered-To: patch@linaro.org Received: by 2002:a2e:1648:0:0:0:0:0 with SMTP id 8-v6csp772868ljw; Fri, 14 Sep 2018 07:23:27 -0700 (PDT) X-Google-Smtp-Source: ANB0VdaWNogqP6RP98zSGcIlgLgIOfLxXkPVbMC4Kf6bPDrb8BTnSUtjHlnME9NMTNmXWcKm8pLj X-Received: by 2002:a63:141c:: with SMTP id u28-v6mr12273041pgl.247.1536935007053; Fri, 14 Sep 2018 07:23:27 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1536935007; cv=none; d=google.com; s=arc-20160816; b=jvqpzOZFuOKwfblknvHeJRPosElZDJC725KIYnzZUVlKzo5yYxCl8sNikAwHKmmWq1 UuzUdkq9NcdPLtc5S26aL3U6r98jEja08I5hGPl2TTuMiLbumHx+36LrdSMnEidk76IZ WllhzjO7sz9W+6OarcWPSHnnvpUQuaLUEeV7ARaOf95TwyHKK6OIedStHdV9ZT8e3Gez gO8o1N6iVVJRKDtPqmNmHpaMgzuB5SqDCxNp9ujZAkClY9jToJKnri/58Bgj+sqoW54x F8htzTd8tS8z6y1fsVZSP+RzXkzvnh+EYQdKy0eS4ZuSJTmisq6PVF9GcF+cHWhoiKQk idYg== 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; bh=M+kKZwDAbPtAP7Qkjv5tvIc/0u48iTxGHE2Zfoo1e6E=; b=YPkU6ler8CeWykh3RzrvBeeBmJZRX9RfRqLEyPGsc7qH0lAdBHevwkh9zDBOAoiZwM PTQQnR0u9SXGC5H3+tVt/kSHXVePTuUkeg7WZMhZmgT3dNOTaFwVdajh5YKmlO6H8eR9 RTXiVcL/WHSgWUeejgsZrpl0c51i1I4p2cX3UAm9GH8VZnzG3EDC8McOp5HH5s/T1J/I I0lgguz92kZDDDlPGAWDfb0rD168jFuyrBSVucEwcmxdOoLRpSFAu/UREn/wjbKVeGgy ToGrpYE/JZfiLLPnVezc0Z8HX6KBQDw2WMlBZHUuCTcs9ufvoF57lakBYGa9Qk/NO6l1 SM9g== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@linaro.org header.s=google header.b=T9VQZi1X; 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 b66-v6si7452161pga.60.2018.09.14.07.23.26; Fri, 14 Sep 2018 07:23:27 -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=T9VQZi1X; 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 S1728273AbeINTiJ (ORCPT + 32 others); Fri, 14 Sep 2018 15:38:09 -0400 Received: from mail-wm1-f66.google.com ([209.85.128.66]:35364 "EHLO mail-wm1-f66.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1728199AbeINTiH (ORCPT ); Fri, 14 Sep 2018 15:38:07 -0400 Received: by mail-wm1-f66.google.com with SMTP id o18-v6so2142570wmc.0 for ; Fri, 14 Sep 2018 07:23:22 -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=M+kKZwDAbPtAP7Qkjv5tvIc/0u48iTxGHE2Zfoo1e6E=; b=T9VQZi1XlVk9k/P+MMtiy3GtXFT9jG4xtC0/Js2nTqEmmRdIAwUlx2gMBwVJqGFANH +XtZdbYYhV6NAR1EPEgPlTzI7dDsolyJOZPDoGAa9nBBbM0djwr3VGeSJudEVBQ2iH2I pAc0HGNEiZ/yst5qeay6jskTiZxS7qMh3O1K0= 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=M+kKZwDAbPtAP7Qkjv5tvIc/0u48iTxGHE2Zfoo1e6E=; b=Bz5CzfQy4b1GuAMeom/nmym16n06ePlW0CMuFVJtUSC2DassSkz9FMd/4Dz6gAyXF2 798TqGMtbxOHigc3+ZFJv1fC45I9YKX6YlTSFwM3wZM/GlevXwbHdJEu7+FBSEzEWQCu ILWICglboMllZ9+43+w+V6s7bhVN/RWTc9DE7V8sArUyqTk3+WyIcm6XcsVTpV7JKsZA p/BYzyntgkRbgdhx+HzQHnGw5bBYR5LcZATxL+9Hc0nvv3n9bc9iK+rcCEziLEtaEySs k/VYj4+Ld72dWE6u+BHHX499NbwE0KN3IZGvmSp12HBXxoVsPFf4uOx1jTMswYv5Pbn0 XkIg== X-Gm-Message-State: APzg51Cs7kDxznt1yiVkhYlUiqVrDWgPS7ptw+sk1iSQlYvoV2IodK2A QQ3FdXl43b18d0J6vR9pjcnJAg== X-Received: by 2002:a1c:3712:: with SMTP id e18-v6mr2608332wma.84.1536935001094; Fri, 14 Sep 2018 07:23:21 -0700 (PDT) Received: from wifi-122_dhcprange-84.wifi.unimo.it (wifi-122_dhcprange-84.wifi.unimo.it. [155.185.122.84]) by smtp.gmail.com with ESMTPSA id k35-v6sm17084888wrc.14.2018.09.14.07.23.19 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Fri, 14 Sep 2018 07:23:20 -0700 (PDT) From: Paolo Valente To: Jens Axboe Cc: linux-block@vger.kernel.org, linux-kernel@vger.kernel.org, ulf.hansson@linaro.org, linus.walleij@linaro.org, broonie@kernel.org, bfq-iosched@googlegroups.com, oleksandr@natalenko.name, Paolo Valente Subject: [PATCH BUGFIX/IMPROVEMENT 2/3] block, bfq: inject other-queue I/O into seeky idle queues on NCQ flash Date: Fri, 14 Sep 2018 16:23:08 +0200 Message-Id: <20180914142309.6789-3-paolo.valente@linaro.org> X-Mailer: git-send-email 2.16.1 In-Reply-To: <20180914142309.6789-1-paolo.valente@linaro.org> References: <20180914142309.6789-1-paolo.valente@linaro.org> Sender: linux-kernel-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org The Achilles' heel of BFQ is its failing to reach a high throughput with sync random I/O on flash storage with internal queueing, in case the processes doing I/O have differentiated weights. The cause of this failure is as follows. If at least two processes do sync I/O, and have a different weight from each other, then BFQ plugs I/O dispatching every time one of these processes, while it is being served, remains temporarily without pending I/O requests. This plugging is necessary to guarantee that every process enjoys a bandwidth proportional to its weight; but it empties the internal queue(s) of the drive. And this kills throughput with random I/O. So, if some processes have differentiated weights and do both sync and random I/O, the end result is a throughput collapse. This commit tries to counter this problem by injecting the service of other processes, in a controlled way, while the process in service happens to have no I/O. This injection is performed only if the medium is non rotational and performs internal queueing, and the process in service does random I/O (service injection might be beneficial for sequential I/O too, we'll work on that). As an example of the benefits of this commit, on a PLEXTOR PX-256M5S SSD, and with five processes having differentiated weights and doing sync random 4KB I/O, this commit makes the throughput with bfq grow by 400%, from 25 to 100MB/s. This higher throughput is 10MB/s lower than that reached with none. As some less random I/O is added to the mix, the throughput becomes equal to or higher than that with none. This commit is a very first attempt to recover throughput without losing control, and certainly has many limitations. One is, e.g., that the processes whose service is injected are not chosen so as to distribute the extra bandwidth they receive in accordance to their weights. Thus there might be loss of weighted fairness in some cases. Anyway, this loss concerns extra service, which would not have been received at all without this commit. Other limitations and issues will probably show up with usage. Signed-off-by: Paolo Valente --- block/bfq-iosched.c | 68 ++++++++++++++++++++++++++++++++++++++++++++++++----- block/bfq-iosched.h | 26 ++++++++++++++++++++ 2 files changed, 88 insertions(+), 6 deletions(-) -- 2.16.1 diff --git a/block/bfq-iosched.c b/block/bfq-iosched.c index 653100fb719e..d94838bcc135 100644 --- a/block/bfq-iosched.c +++ b/block/bfq-iosched.c @@ -3182,6 +3182,13 @@ static unsigned long bfq_bfqq_softrt_next_start(struct bfq_data *bfqd, jiffies + nsecs_to_jiffies(bfqq->bfqd->bfq_slice_idle) + 4); } +static bool bfq_bfqq_injectable(struct bfq_queue *bfqq) +{ + return BFQQ_SEEKY(bfqq) && bfqq->wr_coeff == 1 && + blk_queue_nonrot(bfqq->bfqd->queue) && + bfqq->bfqd->hw_tag; +} + /** * bfq_bfqq_expire - expire a queue. * @bfqd: device owning the queue. @@ -3291,6 +3298,8 @@ void bfq_bfqq_expire(struct bfq_data *bfqd, if (ref == 1) /* bfqq is gone, no more actions on it */ return; + bfqq->injected_service = 0; + /* mark bfqq as waiting a request only if a bic still points to it */ if (!bfq_bfqq_busy(bfqq) && reason != BFQQE_BUDGET_TIMEOUT && @@ -3629,6 +3638,30 @@ static bool bfq_bfqq_must_idle(struct bfq_queue *bfqq) return RB_EMPTY_ROOT(&bfqq->sort_list) && bfq_better_to_idle(bfqq); } +static struct bfq_queue *bfq_choose_bfqq_for_injection(struct bfq_data *bfqd) +{ + struct bfq_queue *bfqq; + + /* + * A linear search; but, with a high probability, very few + * steps are needed to find a candidate queue, i.e., a queue + * with enough budget left for its next request. In fact: + * - BFQ dynamically updates the budget of every queue so as + * to accommodate the expected backlog of the queue; + * - if a queue gets all its requests dispatched as injected + * service, then the queue is removed from the active list + * (and re-added only if it gets new requests, but with + * enough budget for its new backlog). + */ + list_for_each_entry(bfqq, &bfqd->active_list, bfqq_list) + if (!RB_EMPTY_ROOT(&bfqq->sort_list) && + bfq_serv_to_charge(bfqq->next_rq, bfqq) <= + bfq_bfqq_budget_left(bfqq)) + return bfqq; + + return NULL; +} + /* * Select a queue for service. If we have a current queue in service, * check whether to continue servicing it, or retrieve and set a new one. @@ -3710,10 +3743,19 @@ static struct bfq_queue *bfq_select_queue(struct bfq_data *bfqd) * No requests pending. However, if the in-service queue is idling * for a new request, or has requests waiting for a completion and * may idle after their completion, then keep it anyway. + * + * Yet, to boost throughput, inject service from other queues if + * possible. */ if (bfq_bfqq_wait_request(bfqq) || (bfqq->dispatched != 0 && bfq_better_to_idle(bfqq))) { - bfqq = NULL; + if (bfq_bfqq_injectable(bfqq) && + bfqq->injected_service * bfqq->inject_coeff < + bfqq->entity.service * 10) + bfqq = bfq_choose_bfqq_for_injection(bfqd); + else + bfqq = NULL; + goto keep_queue; } @@ -3803,6 +3845,14 @@ static struct request *bfq_dispatch_rq_from_bfqq(struct bfq_data *bfqd, bfq_dispatch_remove(bfqd->queue, rq); + if (bfqq != bfqd->in_service_queue) { + if (likely(bfqd->in_service_queue)) + bfqd->in_service_queue->injected_service += + bfq_serv_to_charge(rq, bfqq); + + goto return_rq; + } + /* * If weight raising has to terminate for bfqq, then next * function causes an immediate update of bfqq's weight, @@ -3821,13 +3871,12 @@ static struct request *bfq_dispatch_rq_from_bfqq(struct bfq_data *bfqd, * belongs to CLASS_IDLE and other queues are waiting for * service. */ - if (bfqd->busy_queues > 1 && bfq_class_idle(bfqq)) - goto expire; - - return rq; + if (!(bfqd->busy_queues > 1 && bfq_class_idle(bfqq))) + goto return_rq; -expire: bfq_bfqq_expire(bfqd, bfqq, false, BFQQE_BUDGET_EXHAUSTED); + +return_rq: return rq; } @@ -4232,6 +4281,13 @@ static void bfq_init_bfqq(struct bfq_data *bfqd, struct bfq_queue *bfqq, bfq_mark_bfqq_has_short_ttime(bfqq); bfq_mark_bfqq_sync(bfqq); bfq_mark_bfqq_just_created(bfqq); + /* + * Aggressively inject a lot of service: up to 90%. + * This coefficient remains constant during bfqq life, + * but this behavior might be changed, after enough + * testing and tuning. + */ + bfqq->inject_coeff = 1; } else bfq_clear_bfqq_sync(bfqq); diff --git a/block/bfq-iosched.h b/block/bfq-iosched.h index a8a2e5aca4d4..37d627afdc2e 100644 --- a/block/bfq-iosched.h +++ b/block/bfq-iosched.h @@ -351,6 +351,32 @@ struct bfq_queue { unsigned long split_time; /* time of last split */ unsigned long first_IO_time; /* time of first I/O for this queue */ + + /* max service rate measured so far */ + u32 max_service_rate; + /* + * Ratio between the service received by bfqq while it is in + * service, and the cumulative service (of requests of other + * queues) that may be injected while bfqq is empty but still + * in service. To increase precision, the coefficient is + * measured in tenths of unit. Here are some example of (1) + * ratios, (2) resulting percentages of service injected + * w.r.t. to the total service dispatched while bfqq is in + * service, and (3) corresponding values of the coefficient: + * 1 (50%) -> 10 + * 2 (33%) -> 20 + * 10 (9%) -> 100 + * 9.9 (9%) -> 99 + * 1.5 (40%) -> 15 + * 0.5 (66%) -> 5 + * 0.1 (90%) -> 1 + * + * So, if the coefficient is lower than 10, then + * injected service is more than bfqq service. + */ + unsigned int inject_coeff; + /* amount of service injected in current service slot */ + unsigned int injected_service; }; /** From patchwork Fri Sep 14 14:23:09 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Paolo Valente X-Patchwork-Id: 146702 Delivered-To: patch@linaro.org Received: by 2002:a2e:1648:0:0:0:0:0 with SMTP id 8-v6csp772973ljw; Fri, 14 Sep 2018 07:23:33 -0700 (PDT) X-Google-Smtp-Source: ANB0VdY1raM4RG+Nn1l5Oota5xBk3r2vvIAszbM4ixaLQsngzwxe11yxh9ZD60Oeqf5MGq2PdO6v X-Received: by 2002:a65:4d42:: with SMTP id j2-v6mr11922270pgt.232.1536935013066; Fri, 14 Sep 2018 07:23:33 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1536935013; cv=none; d=google.com; s=arc-20160816; b=PIi3SKDq379rzB5aakr9m4+Wt3a+GHaEnUbMC/ZLseNMaYcgbDF0rmYsEECaValmro 8t9dI2pKDqWeNOvHkGRcORBmR62faU9UVBkFf3PTV39VSovsKztBVHi6T5TAZBJafoTI /cXmTVMy+WDl5hRgLAqQZzrl/qjn9Oy/d5EuxZnp5lVobsMVXS14nwSX/2b9F7Yh/Iaf j22TA02f7lvQ9B/mYygOdxtZDuulo+6acXIXShyQtlNzaMjAkx9eqUSieHqvzDpT9o0b 911oGx1ad2E9tBskVTRe1ISCn4lbg1jKQClT0zHdyQ9kQxs3L55czfIOY4DKPF6Vbq6V 38qQ== 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; bh=NDz4sLfCSE+TqlBABM2X5T0yTWgA3O/WCAY/iJ5XldA=; b=on055ZWV9YJCQcswQnk8KNIXtf6gbVkhEQ+U01QS2O/PbWO309rzys7Wl5OgrCMcbm vcOMgYSgLfLxtvkFiXtQclqDW2Y5483fAyu0tJ8qmSA6X+cZNrhml5VLKzt/W4GglNRV F0qhUBsewHwV2NyXBL88TJNbbchk1/wVFIlX6E0oUMmy9EczXxuYGrhLyyg9IP+NnDTR rp2eGQTDDQ3UfW+6JO3gv4avnO2BMRupbp+tCa/rPAZboD111JJhbIDou76G8xRBwpeS u/WnlI19YmbL6p3W41a42f3aCDYh68YIZyk4N+mq1qQuhCl4YJKCzHK8SPYD0gbJf4kz iAhg== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@linaro.org header.s=google header.b=YNVrodgC; 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 w10-v6si7126762ply.267.2018.09.14.07.23.32; Fri, 14 Sep 2018 07:23:33 -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=YNVrodgC; 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 S1728257AbeINTiI (ORCPT + 32 others); Fri, 14 Sep 2018 15:38:08 -0400 Received: from mail-wm1-f68.google.com ([209.85.128.68]:40689 "EHLO mail-wm1-f68.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1728236AbeINTiI (ORCPT ); Fri, 14 Sep 2018 15:38:08 -0400 Received: by mail-wm1-f68.google.com with SMTP id 207-v6so2122901wme.5 for ; Fri, 14 Sep 2018 07:23:23 -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=NDz4sLfCSE+TqlBABM2X5T0yTWgA3O/WCAY/iJ5XldA=; b=YNVrodgCbk9Qq5HogJG1AhAKMGOgsPkDX58PZ3nUiWAS19J+GLmr3eM3hbVzJEl1Nn iM2s6VmpVn4WiFQuLfYRHP2pMDq8+L3ybI0QLjIYffvVskXBxpPjNaBX3+q4bXdcnVLY Du/pd6y5PG7r0qZeYTHjwoZW0jagutAO8C3+E= 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=NDz4sLfCSE+TqlBABM2X5T0yTWgA3O/WCAY/iJ5XldA=; b=s5pmOJ1dkf0Zgp05Eqjj5svVmDlVA25Kf3aao00IlTgC59DLxDFVWOttz+L6bskU2e wWlRM/f9fAvknpWflXJoDpBHI4OlWFSd6SaXlUTafJlaA1cSzPpyekioDWh/AZyD+c3p r/p4J5bkXuMQdDFrAWgRue5cIoyywCApRzwCpY8It7z6yxnFoCZHIUaRJRy8OKszIsrF HlKxUS7V1h3MLTEUJI3CYxjcxZu1oS77ZIpvMzR5Mu85VwN/bGtSHGt+F8L9SLVBsV5z 4U+WZdyd4Y9o6FaWgwX6BUMLg+JFZ45XmWzyjVtpPFzBDkCdWAfQSgfeZpS1iBf9df0v YiyQ== X-Gm-Message-State: APzg51Di5Jd9oNsmn2k5al3bLqSnEXf1U9RYok9Cyn+1jmyfBHjIO6NQ 2L0jsW06ua/t5t8Aye/61NXXkaQ2T1w= X-Received: by 2002:a1c:c14:: with SMTP id 20-v6mr2618562wmm.117.1536935002644; Fri, 14 Sep 2018 07:23:22 -0700 (PDT) Received: from wifi-122_dhcprange-84.wifi.unimo.it (wifi-122_dhcprange-84.wifi.unimo.it. [155.185.122.84]) by smtp.gmail.com with ESMTPSA id k35-v6sm17084888wrc.14.2018.09.14.07.23.21 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Fri, 14 Sep 2018 07:23:21 -0700 (PDT) From: Paolo Valente To: Jens Axboe Cc: linux-block@vger.kernel.org, linux-kernel@vger.kernel.org, ulf.hansson@linaro.org, linus.walleij@linaro.org, broonie@kernel.org, bfq-iosched@googlegroups.com, oleksandr@natalenko.name, Paolo Valente Subject: [PATCH BUGFIX/IMPROVEMENT 3/3] blok, bfq: do not plug I/O if all queues are weight-raised Date: Fri, 14 Sep 2018 16:23:09 +0200 Message-Id: <20180914142309.6789-4-paolo.valente@linaro.org> X-Mailer: git-send-email 2.16.1 In-Reply-To: <20180914142309.6789-1-paolo.valente@linaro.org> References: <20180914142309.6789-1-paolo.valente@linaro.org> Sender: linux-kernel-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org To reduce latency for interactive and soft real-time applications, bfq privileges the bfq_queues containing the I/O of these applications. These privileged queues, referred-to as weight-raised queues, get a much higher share of the device throughput w.r.t. non-privileged queues. To preserve this higher share, the I/O of any non-weight-raised queue must be plugged whenever a sync weight-raised queue, while being served, remains temporarily empty. To attain this goal, bfq simply plugs any I/O (from any queue), if a sync weight-raised queue remains empty while in service. Unfortunately, this plugging typically lowers throughput with random I/O, on devices with internal queueing (because it reduces the filling level of the internal queues of the device). This commit addresses this issue by restricting the cases where plugging is performed: if a sync weight-raised queue remains empty while in service, then I/O plugging is performed only if some of the active bfq_queues are *not* weight-raised (which is actually the only circumstance where plugging is needed to preserve the higher share of the throughput of weight-raised queues). This restriction proved able to boost throughput in really many use cases needing only maximum throughput. Signed-off-by: Paolo Valente --- block/bfq-iosched.c | 10 ++++++++-- 1 file changed, 8 insertions(+), 2 deletions(-) -- 2.16.1 diff --git a/block/bfq-iosched.c b/block/bfq-iosched.c index d94838bcc135..c0b1db3afb81 100644 --- a/block/bfq-iosched.c +++ b/block/bfq-iosched.c @@ -3580,7 +3580,12 @@ static bool bfq_better_to_idle(struct bfq_queue *bfqq) * whether bfqq is being weight-raised, because * bfq_symmetric_scenario() does not take into account also * weight-raised queues (see comments on - * bfq_weights_tree_add()). + * bfq_weights_tree_add()). In particular, if bfqq is being + * weight-raised, it is important to idle only if there are + * other, non-weight-raised queues that may steal throughput + * to bfqq. Actually, we should be even more precise, and + * differentiate between interactive weight raising and + * soft real-time weight raising. * * As a side note, it is worth considering that the above * device-idling countermeasures may however fail in the @@ -3592,7 +3597,8 @@ static bool bfq_better_to_idle(struct bfq_queue *bfqq) * to let requests be served in the desired order until all * the requests already queued in the device have been served. */ - asymmetric_scenario = bfqq->wr_coeff > 1 || + asymmetric_scenario = (bfqq->wr_coeff > 1 && + bfqd->wr_busy_queues < bfqd->busy_queues) || !bfq_symmetric_scenario(bfqd); /*