From patchwork Wed Dec 20 11:38:31 2017 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Paolo Valente X-Patchwork-Id: 122460 Delivered-To: patch@linaro.org Received: by 10.140.22.227 with SMTP id 90csp5452116qgn; Wed, 20 Dec 2017 03:39:34 -0800 (PST) X-Google-Smtp-Source: ACJfBos+35I9NZwuocqczkBr6Tpj9KIxlGANzxJ50MBuekkMUER/0hTfIAUmjCnfIGqCCU+71i/0 X-Received: by 10.101.64.130 with SMTP id t2mr5868333pgp.299.1513769973932; Wed, 20 Dec 2017 03:39:33 -0800 (PST) ARC-Seal: i=1; a=rsa-sha256; t=1513769973; cv=none; d=google.com; s=arc-20160816; b=lNB5Jrs6osywuX0Ktqd6jINQmrVHoT0VlpP8ydxFgCWhQn97lLoqXkhNAMPkTVo58d ZmmUhOjjhMQvkp8vOtkAsmDUALj8F5QU0g5wQa0zD+Qi8CzFX18Zw1QvE4MqVzZx78LB 8jfYSbHD89DfhosT93dyJsjW3HB48Z2ox4er1EfX2IJWTCNxkMvncUmUo76B7XMogUtI TKK/K929cbXUC8s706QUMHrKSQT7PYP8LNZRg0NAxiU4x9ym6JMTbv5vl39CDzWBUJ0K OJK/la9qx8VyT04UX4kUnpaDaq21bHSBV7c3hiAANAbMFvpErWousivcT7AFyXCNp1cg 856g== 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=ErN9MVCc7+5ZbfMB2t6kzsPh1Xw65tj7g1Knz3fHQ7s=; b=uGBmuOkN0Gn461igYUpzZbyM5Lev/4i1+fBhUu5hP1LJNgPiof9BNoLFFmR4YEfz+6 y5pt3ibhCbis6JaTExvREVfsRvCqP3aRTpPd6lu+FVN+5c/zd9OXijY4g2x9lzJvq55A V/RM8XGKwH9oGdyWzq6cuhHcw1b/e2wugufCXjUXfV614jsqBTKNkS8K2yPFYpft2EiK 2VrPLt+HyFqSOzF2tfHjEm7g0WG62bSYyGWYUhkYEo/IL5x2622aKY0gu8/RrrlhCRwT NWMxPx2knTo1ckKkJORlcrFNxFPrTRxeFcFGEub7Z84PDNc53TiSeL+OPO71XadqG4s5 IsHg== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@linaro.org header.s=google header.b=EgqmUUCq; 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 bd12si12744551plb.694.2017.12.20.03.39.33; Wed, 20 Dec 2017 03:39:33 -0800 (PST) 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=EgqmUUCq; 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 S1755278AbdLTLja (ORCPT + 28 others); Wed, 20 Dec 2017 06:39:30 -0500 Received: from mail-wm0-f67.google.com ([74.125.82.67]:39355 "EHLO mail-wm0-f67.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1755169AbdLTLjV (ORCPT ); Wed, 20 Dec 2017 06:39:21 -0500 Received: by mail-wm0-f67.google.com with SMTP id i11so9120844wmf.4 for ; Wed, 20 Dec 2017 03:39:21 -0800 (PST) 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=ErN9MVCc7+5ZbfMB2t6kzsPh1Xw65tj7g1Knz3fHQ7s=; b=EgqmUUCqXYWHM4xaOd4rYDmYlQoxQKzjPIEeDQ03ARrLi2BycMa2vI9XD69bIxyBQh gURIyfc2bL/uhDx+DBeV8bScduFpPki0tVkjkppH6uEGARiepYPKg8zzEt7gzquY5efG +eWPgrEAoWcA5GQRJu81fn2IQo2BwZ9GWSLLA= 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=ErN9MVCc7+5ZbfMB2t6kzsPh1Xw65tj7g1Knz3fHQ7s=; b=rhKz/gj//Wsty1LDqkwLN+3jb+3Vk+ZnIOEXzsoII0ogrgcT1lgMNiIZ4fLXQzUAUq HujA+zQoGbV5mDvNuva6/u3Ae83kCzWsdP8PCm03oSYwFXdwP5dfnwjV7YRwGxvEI2l4 mLCBZb3fFF9PppLeZ/HT3cUBI+ZOUZwZM0Ryugr/Hoo0DM7TMK5u4/hnRtmusQTqnE3M KkPRMlsR465EmxrsL/pvuNg8X+LLJw6OMhrMVUGFxm5ZeMKM2FKDHeVviz04/J9wnWo3 qLN51NWhGYuetCIqhXZM8Ylea8DFonM/fykdgYxukNiVfTbFJLzsL3C3Z7qkW7p+RZ4C OepQ== X-Gm-Message-State: AKGB3mLTfysmDcwRBt+O1Me4abIW+34I4B5JBWfE8X3p+Ed10HaLoFij oGNlayah0TsRHD38sUObPz9KDw== X-Received: by 10.28.47.66 with SMTP id v63mr6170335wmv.144.1513769960224; Wed, 20 Dec 2017 03:39:20 -0800 (PST) Received: from wifi-122_dhcprange-89.wifi.unimo.it (wifi-122_dhcprange-89.wifi.unimo.it. [155.185.122.89]) by smtp.gmail.com with ESMTPSA id o27sm9704436wro.9.2017.12.20.03.39.17 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Wed, 20 Dec 2017 03:39:18 -0800 (PST) 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, angeloruocco90@gmail.com, bfq-iosched@googlegroups.com, Paolo Valente Subject: [PATCH IMPROVEMENT/BUGFIX 1/4] block, bfq: add missing rq_pos_tree update on rq removal Date: Wed, 20 Dec 2017 12:38:31 +0100 Message-Id: <20171220113834.2578-2-paolo.valente@linaro.org> X-Mailer: git-send-email 2.15.1 In-Reply-To: <20171220113834.2578-1-paolo.valente@linaro.org> References: <20171220113834.2578-1-paolo.valente@linaro.org> Sender: linux-kernel-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org If two processes do I/O close to each other, then BFQ merges the bfq_queues associated with these processes, to get a more sequential I/O, and thus a higher throughput. In this respect, to detect whether two processes are doing I/O close to each other, BFQ keeps a list of the head-of-line I/O requests of all active bfq_queues. The list is ordered by initial sectors, and implemented through a red-black tree (rq_pos_tree). Unfortunately, the update of the rq_pos_tree was incomplete, because the tree was not updated on the removal of the head-of-line I/O request of a bfq_queue, in case the queue did not remain empty. This commit adds the missing update. Signed-off-by: Paolo Valente Signed-off-by: Angelo Ruocco --- block/bfq-iosched.c | 2 ++ 1 file changed, 2 insertions(+) -- 2.15.1 diff --git a/block/bfq-iosched.c b/block/bfq-iosched.c index a9e06217e64d..c6f0b93a769c 100644 --- a/block/bfq-iosched.c +++ b/block/bfq-iosched.c @@ -1627,6 +1627,8 @@ static void bfq_remove_request(struct request_queue *q, rb_erase(&bfqq->pos_node, bfqq->pos_root); bfqq->pos_root = NULL; } + } else { + bfq_pos_tree_add_move(bfqd, bfqq); } if (rq->cmd_flags & REQ_META) From patchwork Wed Dec 20 11:38:32 2017 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Paolo Valente X-Patchwork-Id: 122461 Delivered-To: patch@linaro.org Received: by 10.140.22.227 with SMTP id 90csp5452201qgn; Wed, 20 Dec 2017 03:39:40 -0800 (PST) X-Google-Smtp-Source: ACJfBovZdsFj2I2SDcsuGG5oaAs8/vZB1L5X2C6oz2EtclZkwwi9RxL2J3oI90Jr+sRlzZHBRpAS X-Received: by 10.84.218.72 with SMTP id f8mr6843133plm.143.1513769980867; Wed, 20 Dec 2017 03:39:40 -0800 (PST) ARC-Seal: i=1; a=rsa-sha256; t=1513769980; cv=none; d=google.com; s=arc-20160816; b=hp3KeG1xByQdrz4FrZEugQKdYkh8hYGLye950imrH6JKtdbOpXY21a+A8gp5ROAmNi oABqjATVa2AYCMCHU2BF/GJy3biOrLe/OfGiKG2xkd3AlK2EWIwrvij0hbhq4vXyQM6g qH88ebzJR/SG6/sQFjSAc/JDULZMwy+XgMKsVeeTTux5ayUtdgU0u1BTfJ9g7P0VMe5v V9IMCLw80GXpF6JpCVtuzknjgz3JbXn67fWZVUSxMHW92s1n2kOsToT8ifyAjiLahMm1 48buBMKIUfMLZ7FzzUHK2rWCbuFHvtQ4gB5RbTBGVkmwXGUxXxj/Riu8XAcjshq6awyk Bkbg== 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=pcqAnNIwcvmEufgTac7uUsP5d7eBX/9awX2+Cg/30dc=; b=FdJ5YnZtOMDNEFEkR0W3COxWb3xj50WPruuQCQjd7SXttpLnGgUInc4dgl3vz7ZIJS WqmQG7PxucYFpjpw9kBbQFnk7HhgKnUuJDzjqsm5ldxEvdDxjHEEGe7e3dnzU/wEhp/U 55idKGcN+0HSucWHumHJDV7RHMifyvs9IphuXOQV7JgGCX0eu6rrKkZryK5yzn9m3Fih W6QQ/LfUXmtSTvvknKT4K4Q2IZuo8O7P4eH46oKOWEo7JojCvfsRMDy0alXS5a4Schrr H6EDvHO8dnAeEUKLNM87eupRWZdWWkLjIquqolbN8kecCphyE6a7p0z2ssOVTBVawQRu dk6Q== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@linaro.org header.s=google header.b=Dkd43blY; 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 u63si11752493pgc.269.2017.12.20.03.39.40; Wed, 20 Dec 2017 03:39:40 -0800 (PST) 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=Dkd43blY; 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 S1755293AbdLTLjf (ORCPT + 28 others); Wed, 20 Dec 2017 06:39:35 -0500 Received: from mail-wm0-f65.google.com ([74.125.82.65]:36405 "EHLO mail-wm0-f65.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1755240AbdLTLjX (ORCPT ); Wed, 20 Dec 2017 06:39:23 -0500 Received: by mail-wm0-f65.google.com with SMTP id b76so9211668wmg.1 for ; Wed, 20 Dec 2017 03:39:22 -0800 (PST) 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=pcqAnNIwcvmEufgTac7uUsP5d7eBX/9awX2+Cg/30dc=; b=Dkd43blY6j4jG/3OA4wZInwyIxkl0Xix5SGw7h+f5IuoDoCqhW9gxU02woQAQ0GiTZ O+DPTUbe3yVAwwPHh9YipqQ3Rco4wZtIOT4rfwnQTgOSXn6xdSYeemfxelgINZ/pls/E xaW5zes5jboG9TPqzGYd+cBWBBTGFNRGWpQUw= 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=pcqAnNIwcvmEufgTac7uUsP5d7eBX/9awX2+Cg/30dc=; b=n+2il2Jwg/s/33t/iBi+DbRQJlmK4lQ6DBg21JsHzLVCFrcuahkcT8vwfxID3q+YRV v6ytS/L5+ZSx6TsiQIcikNImdPVnDzENfq3sYxuI2jmvTx+Nmm/w+rHH34+RJPXRgIdi 0zT7TwT1jvRV/SK/rXgWYHAhc82plR5qCGFd2EqfDSvYSiO43AAAEXyJaxN4sBhkwsS2 gCqwerfEMlY8QET64ja6dgstk2jRojiooqWcRA7H3u6KyTq5aLRwqQ8Fw5MSxoNSUgyB Hdt7QK8m1gjg8fmF07txKYNWBIi7cguW2TOr4ngs00LUGnEXt54D3D4zpHSw1/IX/wZd ejyA== X-Gm-Message-State: AKGB3mJVA83szezoP/SRXdOQkU1NrQTaCIpb4GqBseZ08lAAZIRP8Z32 jw9rLSEmh41XgPwiXkOQ68VBpQ== X-Received: by 10.28.116.19 with SMTP id p19mr5890253wmc.152.1513769962081; Wed, 20 Dec 2017 03:39:22 -0800 (PST) Received: from wifi-122_dhcprange-89.wifi.unimo.it (wifi-122_dhcprange-89.wifi.unimo.it. [155.185.122.89]) by smtp.gmail.com with ESMTPSA id o27sm9704436wro.9.2017.12.20.03.39.20 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Wed, 20 Dec 2017 03:39:21 -0800 (PST) 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, angeloruocco90@gmail.com, bfq-iosched@googlegroups.com, Paolo Valente Subject: [PATCH IMPROVEMENT/BUGFIX 2/4] block, bfq: check low_latency flag in bfq_bfqq_save_state() Date: Wed, 20 Dec 2017 12:38:32 +0100 Message-Id: <20171220113834.2578-3-paolo.valente@linaro.org> X-Mailer: git-send-email 2.15.1 In-Reply-To: <20171220113834.2578-1-paolo.valente@linaro.org> References: <20171220113834.2578-1-paolo.valente@linaro.org> Sender: linux-kernel-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org From: Angelo Ruocco A just-created bfq_queue will certainly be deemed as interactive on the arrival of its first I/O request, if the low_latency flag is set. Yet, if the queue is merged with another queue on the arrival of its first I/O request, it will not have the chance to be flagged as interactive. Nevertheless, if the queue is then split soon enough, it has to be flagged as interactive after the split. To handle this early-merge scenario correctly, BFQ saves the state of the queue, on the merge, as if the latter had already been deemed interactive. So, if the queue is split soon, it will get weight-raised, because the previous state of the queue is resumed on the split. Unfortunately, in the act of saving the state of the newly-created queue, BFQ doesn't check whether the low_latency flag is set, and this causes early-merged queues to be then weight-raised, on queue splits, even if low_latency is off. This commit addresses this problem by adding the missing check. Signed-off-by: Angelo Ruocco Signed-off-by: Paolo Valente --- block/bfq-iosched.c | 3 ++- 1 file changed, 2 insertions(+), 1 deletion(-) -- 2.15.1 diff --git a/block/bfq-iosched.c b/block/bfq-iosched.c index c6f0b93a769c..f58367ef98c1 100644 --- a/block/bfq-iosched.c +++ b/block/bfq-iosched.c @@ -2064,7 +2064,8 @@ static void bfq_bfqq_save_state(struct bfq_queue *bfqq) bic->saved_in_large_burst = bfq_bfqq_in_large_burst(bfqq); bic->was_in_burst_list = !hlist_unhashed(&bfqq->burst_list_node); if (unlikely(bfq_bfqq_just_created(bfqq) && - !bfq_bfqq_in_large_burst(bfqq))) { + !bfq_bfqq_in_large_burst(bfqq) && + bfqq->bfqd->low_latency)) { /* * bfqq being merged right after being created: bfqq * would have deserved interactive weight raising, but From patchwork Wed Dec 20 11:38:33 2017 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Paolo Valente X-Patchwork-Id: 122462 Delivered-To: patch@linaro.org Received: by 10.140.22.227 with SMTP id 90csp5452231qgn; Wed, 20 Dec 2017 03:39:42 -0800 (PST) X-Google-Smtp-Source: ACJfBouvYmbNTvhfIaZuOwRXOOCgs2byOrbN7vyrWpwrOYFE/tFjPf2AOmCVW61AwF7Oe98fMara X-Received: by 10.101.97.75 with SMTP id o11mr5918163pgv.363.1513769982009; Wed, 20 Dec 2017 03:39:42 -0800 (PST) ARC-Seal: i=1; a=rsa-sha256; t=1513769982; cv=none; d=google.com; s=arc-20160816; b=NItxAJrcFH31gY4XOoaxpNOGjNMv2Zzz9msSSDjcurf4plwWRog0uEG0gACTj7xXyL Ji9b5bocMTDiDbC0acZCKT9JqTQXhM7aP67EMipwl8C2uGbUBM3JnItMBE4zp0MbLt5y JZjwXZulcCmCoECHCKEMFY2rtQo23ULGf3JGs6odlfhCp0A07H3Ns+OrZvBLml3be526 sOQ1MOuUoswPD3EOpOFWCnnOj+Vd7S6lIBXff0TwnlbWjS2KimlBOhQXTSQIJpreurgP rc2R008nH7K35vWacOx3RbbNyeqNux61evRjnqp1nDn4yTcMqa4xjKr4ahpK0WqKRxI6 gLlw== 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=NbQMGpqCravqWvdwQ0/erZYhDw1gWLCsefWSq5SO9QY=; b=TkUkJ90F6Ow/te4PhZiLBGoHIdhDzpWya+jzqqwOGJ94OZNXRo7jPGNO7JSi597MBJ Oad+5AHkMmYq/mF8dLdA+bX5uF4YGJk4cPd+CS1LgwqHjFDP1ZpSrv1VnTpBQz1ScCsf 5ml1GKnO/S/B1yCtzf2jndXKnGTh/4MUfRWCMAYzF/0zVPqG8nlswKobcymAi3ylIwVs JYJp2f1UV9NhfZ7q/VokTYY0nn+dkDQemIGJuqorI3IX31vAp03rJyg2XnXP1um4Zi5I G0m6+RUa1JPROM4cRkqQMUnIqSS2xNNooMjk0tPACuyRS33/cqoeB8bMbGteHl8maFVZ uvxA== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@linaro.org header.s=google header.b=X+QOL7FB; 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 u63si11752493pgc.269.2017.12.20.03.39.41; Wed, 20 Dec 2017 03:39:41 -0800 (PST) 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=X+QOL7FB; 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 S1755307AbdLTLji (ORCPT + 28 others); Wed, 20 Dec 2017 06:39:38 -0500 Received: from mail-wm0-f66.google.com ([74.125.82.66]:36414 "EHLO mail-wm0-f66.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1755243AbdLTLjZ (ORCPT ); Wed, 20 Dec 2017 06:39:25 -0500 Received: by mail-wm0-f66.google.com with SMTP id b76so9211847wmg.1 for ; Wed, 20 Dec 2017 03:39:25 -0800 (PST) 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=NbQMGpqCravqWvdwQ0/erZYhDw1gWLCsefWSq5SO9QY=; b=X+QOL7FBgT0FS0WSBJS0ofGV0bw+lLrlQmZjLTuuvZR/4DV3iWJIYqwTgrjpcRD626 PAmDt51LsToTvTBczqx96R8s3A6YG7VirZNzYOuE61QjeYl3l4QrGBZ8Y2uuJARiOhy7 RLIPgOSC/kdmy/6bYiUI/tJXkx2cW1fnoix4E= 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=NbQMGpqCravqWvdwQ0/erZYhDw1gWLCsefWSq5SO9QY=; b=fc6N1KzUVaQJeWfLj5V2VoDk6YjSLjw1t1S2vxLB/uBP6daUl09I501B5SW9fLcU8R wuCkvvUtcTvxlF68mP1M3NYf0YnhqhTPo9Z75W2JhYpXffd6YuMzQkuC2JHrJIV0qlhp LOHRs+rn2WkNhMsMJvcL4nR3gZKIl1tzp83GRgvvwagaeeGQecS0+5EeqgqZ6/u/yZlm xdDAqsIcgKdhsdaivpLLr/TxqXTeQiNC9+l6M/ZYMZHpDrIBTDBmS7C0vMT2JwnNnqmO +anVHib8Bg6YdLkYLUlF/iidbJEdr5uyw2rnz4CRniLyWmReF6shoy05xtHzBuMqXI7x K/dg== X-Gm-Message-State: AKGB3mIvihTFEa52JCHwDaLfUzHDDUA/FVMixT1ohhKXPzfj4e2iAm9Z nneMrRYOiDrUcFdlIF+3F30Txg== X-Received: by 10.28.191.3 with SMTP id p3mr6093463wmf.81.1513769964049; Wed, 20 Dec 2017 03:39:24 -0800 (PST) Received: from wifi-122_dhcprange-89.wifi.unimo.it (wifi-122_dhcprange-89.wifi.unimo.it. [155.185.122.89]) by smtp.gmail.com with ESMTPSA id o27sm9704436wro.9.2017.12.20.03.39.22 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Wed, 20 Dec 2017 03:39:23 -0800 (PST) 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, angeloruocco90@gmail.com, bfq-iosched@googlegroups.com, Paolo Valente Subject: [PATCH IMPROVEMENT/BUGFIX 3/4] block, bfq: let a queue be merged only shortly after starting I/O Date: Wed, 20 Dec 2017 12:38:33 +0100 Message-Id: <20171220113834.2578-4-paolo.valente@linaro.org> X-Mailer: git-send-email 2.15.1 In-Reply-To: <20171220113834.2578-1-paolo.valente@linaro.org> References: <20171220113834.2578-1-paolo.valente@linaro.org> Sender: linux-kernel-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org In BFQ and CFQ, two processes are said to be cooperating if they do I/O in such a way that the union of their I/O requests yields a sequential I/O pattern. To get such a sequential I/O pattern out of the non-sequential pattern of each cooperating process, BFQ and CFQ merge the queues associated with these processes. In more detail, cooperating processes, and thus their associated queues, usually start, or restart, to do I/O shortly after each other. This is the case, e.g., for the I/O threads of KVM/QEMU and of the dump utility. Basing on this assumption, this commit allows a bfq_queue to be merged only during a short time interval (100ms) after it starts, or re-starts, to do I/O. This filtering provides two important benefits. First, it greatly reduces the probability that two non-cooperating processes have their queues merged by mistake, if they just happen to do I/O close to each other for a short time interval. These spurious merges cause loss of service guarantees. A low-weight bfq_queue may unjustly get more than its expected share of the throughput: if such a low-weight queue is merged with a high-weight queue, then the I/O for the low-weight queue is served as if the queue had a high weight. This may damage other high-weight queues unexpectedly. For instance, because of this issue, lxterminal occasionally took 7.5 seconds to start, instead of 6.5 seconds, when some sequential readers and writers did I/O in the background on a FUJITSU MHX2300BT HDD. The reason is that the bfq_queues associated with some of the readers or the writers were merged with the high-weight queues of some processes that had to do some urgent but little I/O. The readers then exploited the inherited high weight for all or most of their I/O, during the start-up of terminal. The filtering introduced by this commit eliminated any outlier caused by spurious queue merges in our start-up time tests. This filtering also provides a little boost of the throughput sustainable by BFQ: 3-4%, depending on the CPU. The reason is that, once a bfq_queue cannot be merged any longer, this commit makes BFQ stop updating the data needed to handle merging for the queue. Signed-off-by: Paolo Valente Signed-off-by: Angelo Ruocco --- block/bfq-iosched.c | 57 ++++++++++++++++++++++++++++++++++++++++++----------- block/bfq-iosched.h | 2 ++ block/bfq-wf2q.c | 4 ++++ 3 files changed, 52 insertions(+), 11 deletions(-) -- 2.15.1 diff --git a/block/bfq-iosched.c b/block/bfq-iosched.c index f58367ef98c1..320022135dc8 100644 --- a/block/bfq-iosched.c +++ b/block/bfq-iosched.c @@ -166,6 +166,20 @@ static const int bfq_async_charge_factor = 10; /* Default timeout values, in jiffies, approximating CFQ defaults. */ const int bfq_timeout = HZ / 8; +/* + * Time limit for merging (see comments in bfq_setup_cooperator). Set + * to the slowest value that, in our tests, proved to be effective in + * removing false positives, while not causing true positives to miss + * queue merging. + * + * As can be deduced from the low time limit below, queue merging, if + * successful, happens at the very beggining of the I/O of the involved + * cooperating processes, as a consequence of the arrival of the very + * first requests from each cooperator. After that, there is very + * little chance to find cooperators. + */ +static const unsigned long bfq_merge_time_limit = HZ/10; + static struct kmem_cache *bfq_pool; /* Below this threshold (in ns), we consider thinktime immediate. */ @@ -444,6 +458,13 @@ bfq_rq_pos_tree_lookup(struct bfq_data *bfqd, struct rb_root *root, return bfqq; } +static bool bfq_too_late_for_merging(struct bfq_queue *bfqq) +{ + return bfqq->service_from_backlogged > 0 && + time_is_before_jiffies(bfqq->first_IO_time + + bfq_merge_time_limit); +} + void bfq_pos_tree_add_move(struct bfq_data *bfqd, struct bfq_queue *bfqq) { struct rb_node **p, *parent; @@ -454,6 +475,14 @@ void bfq_pos_tree_add_move(struct bfq_data *bfqd, struct bfq_queue *bfqq) bfqq->pos_root = NULL; } + /* + * bfqq cannot be merged any longer (see comments in + * bfq_setup_cooperator): no point in adding bfqq into the + * position tree. + */ + if (bfq_too_late_for_merging(bfqq)) + return; + if (bfq_class_idle(bfqq)) return; if (!bfqq->next_rq) @@ -1935,6 +1964,9 @@ bfq_setup_merge(struct bfq_queue *bfqq, struct bfq_queue *new_bfqq) static bool bfq_may_be_close_cooperator(struct bfq_queue *bfqq, struct bfq_queue *new_bfqq) { + if (bfq_too_late_for_merging(new_bfqq)) + return false; + if (bfq_class_idle(bfqq) || bfq_class_idle(new_bfqq) || (bfqq->ioprio_class != new_bfqq->ioprio_class)) return false; @@ -2003,6 +2035,20 @@ bfq_setup_cooperator(struct bfq_data *bfqd, struct bfq_queue *bfqq, { struct bfq_queue *in_service_bfqq, *new_bfqq; + /* + * Prevent bfqq from being merged if it has been created too + * long ago. The idea is that true cooperating processes, and + * thus their associated bfq_queues, are supposed to be + * created shortly after each other. This is the case, e.g., + * for KVM/QEMU and dump I/O threads. Basing on this + * assumption, the following filtering greatly reduces the + * probability that two non-cooperating processes, which just + * happen to do close I/O for some short time interval, have + * their queues merged by mistake. + */ + if (bfq_too_late_for_merging(bfqq)) + return NULL; + if (bfqq->new_bfqq) return bfqq->new_bfqq; @@ -3044,17 +3090,6 @@ void bfq_bfqq_expire(struct bfq_data *bfqd, */ slow = bfq_bfqq_is_slow(bfqd, bfqq, compensate, reason, &delta); - /* - * Increase service_from_backlogged before next statement, - * because the possible next invocation of - * bfq_bfqq_charge_time would likely inflate - * entity->service. In contrast, service_from_backlogged must - * contain real service, to enable the soft real-time - * heuristic to correctly compute the bandwidth consumed by - * bfqq. - */ - bfqq->service_from_backlogged += entity->service; - /* * As above explained, charge slow (typically seeky) and * timed-out queues with the time and not the service diff --git a/block/bfq-iosched.h b/block/bfq-iosched.h index 91c4390903a1..5d47b58d5fc8 100644 --- a/block/bfq-iosched.h +++ b/block/bfq-iosched.h @@ -344,6 +344,8 @@ struct bfq_queue { unsigned long wr_start_at_switch_to_srt; unsigned long split_time; /* time of last split */ + + unsigned long first_IO_time; /* time of first I/O for this queue */ }; /** diff --git a/block/bfq-wf2q.c b/block/bfq-wf2q.c index e495d3f9b4b0..4456eda34e48 100644 --- a/block/bfq-wf2q.c +++ b/block/bfq-wf2q.c @@ -835,6 +835,10 @@ void bfq_bfqq_served(struct bfq_queue *bfqq, int served) struct bfq_entity *entity = &bfqq->entity; struct bfq_service_tree *st; + if (!bfqq->service_from_backlogged) + bfqq->first_IO_time = jiffies; + + bfqq->service_from_backlogged += served; for_each_entity(entity) { st = bfq_entity_service_tree(entity); From patchwork Wed Dec 20 11:38:34 2017 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Paolo Valente X-Patchwork-Id: 122463 Delivered-To: patch@linaro.org Received: by 10.140.22.227 with SMTP id 90csp5452761qgn; Wed, 20 Dec 2017 03:40:13 -0800 (PST) X-Google-Smtp-Source: ACJfBotq6KYtivqxj+lGrBmTAZwRiUctPSA5gm6zUM4hvyJyifD17sE4UXnqhxD+1ujMoSnkUOqK X-Received: by 10.124.22.132 with SMTP id v4mr6647175ply.158.1513770013648; Wed, 20 Dec 2017 03:40:13 -0800 (PST) ARC-Seal: i=1; a=rsa-sha256; t=1513770013; cv=none; d=google.com; s=arc-20160816; b=wOxJuucfPj/FEBWvJ+g4mxnyKo2QWAO7SwvA+Hj911Ss5uaQiazyfTGt+Nst7bmPZG Bhi7/C5DLfIanhE+t1WQYHYUIgCcl0X1t0ObIabGG2HCNS4iqvMoO2XYsGQitnX6YGka pXtwT1wzgOEck9ewUbpcUEtJmBpffxmsdpSenliFGcsVieAD4huYN69k98kyOHNJwcZJ Xk5mxGZqflsiCCvLZRKx4oHvvtbnyWgKJtQ+6Na0omEPT84eX9zkcWXZxglerf7CtXfu dSHx9xBshZz4BgGq38U/e3PCdOL8rKXD+UxsS6bLQNk/evmHh3Vai1AA8vorhXY64CGh BUFw== 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=73hnCDqCmB0yErZn73n7WIhPPJ+L4UI2WUpvPNLSBng=; b=i4yKbanNH3c/VqYh/Mkmh+/pq5GPJsJ+9KdOio4oukRTPJnVHt5jjvk7GaU1PqlSjX fQBcSWOtiZ34J/HEzo2vBsqfSkyC8bjLNelduspcU2EAi1cLyaXyhlb/dW+Yr4xYU3yN imKjqBrcpI9y659pyEnTaFmd/EcWQO9lG5KKds3WE/RRvSUcUuZW5GpnrK9H0WTODP06 Rx/j64GVa90KL7wUdUXPTWdHWON6tq4VnvH9KLbifiANKe1u1Ugy0U9ugw7whGc/YxY3 aVOFw45Dypf/pE/Oa9Q+4m3owiCFzZ/QkX4BvvWRsDaOSKisQO03ymVCBo2pOmihU/5P l5kg== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@linaro.org header.s=google header.b=NzxWsIG8; 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 o1si743175pgp.166.2017.12.20.03.40.13; Wed, 20 Dec 2017 03:40:13 -0800 (PST) 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=NzxWsIG8; 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 S1755187AbdLTLkJ (ORCPT + 28 others); Wed, 20 Dec 2017 06:40:09 -0500 Received: from mail-wm0-f66.google.com ([74.125.82.66]:44128 "EHLO mail-wm0-f66.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1754985AbdLTLj0 (ORCPT ); Wed, 20 Dec 2017 06:39:26 -0500 Received: by mail-wm0-f66.google.com with SMTP id t8so9229035wmc.3 for ; Wed, 20 Dec 2017 03:39:26 -0800 (PST) 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=73hnCDqCmB0yErZn73n7WIhPPJ+L4UI2WUpvPNLSBng=; b=NzxWsIG8CxjlsK54zzooTn+pUaJ4rBiOr9trjOLKx8WWEvPsQnlGWbTm4iLMWyR+cy +hN408BaqR7nmt1Ilk30GcsrvHrSY38ERNq4HYx3m+TkW8cbE50MQoS4hxoYoxORHR8p VO3bSMpPdl6uqotk2BI1H9K1/ScnLHibIv7Fs= 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=73hnCDqCmB0yErZn73n7WIhPPJ+L4UI2WUpvPNLSBng=; b=XHcGLypk8sq0bkp8eeNGRAzDa9Mo38damhgbXlX56rZHMulBwEWbGzYMmCHY6ppapu cW648QbXgaXDcUMb//ir6vTdMoOy+FOrJp7WzI1OuJICHuEXfHBA9s/AyETdH00u4ln7 3qlD3uIUdEIDIlV8MtXadC5aOabyXlMLwhK6wJTtTQUIX/V2N3CBnWvJLmf9rCTxDSLG 6EJRTPaq+cTfxNheLEC88+REuYchO4NkKRK/yg2WtindajM7+m8kTIPlaOcT04R9B6Me PI1eBmiH9fb3oT0GD6xLfpMHf2NL2bzUsoxGdTX7MQ7ib7p8zqbzMmK1Cg400flz2kWu rowg== X-Gm-Message-State: AKGB3mLeBDLXMyn3Juy9PHRAr2Wv9agzO45CNSAUMpvP3pKrSTK1Cl47 x07ZOSx9h7eDxP+ZRBYSVtVmdQ== X-Received: by 10.28.222.132 with SMTP id v126mr6196602wmg.127.1513769965375; Wed, 20 Dec 2017 03:39:25 -0800 (PST) Received: from wifi-122_dhcprange-89.wifi.unimo.it (wifi-122_dhcprange-89.wifi.unimo.it. [155.185.122.89]) by smtp.gmail.com with ESMTPSA id o27sm9704436wro.9.2017.12.20.03.39.24 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Wed, 20 Dec 2017 03:39:24 -0800 (PST) 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, angeloruocco90@gmail.com, bfq-iosched@googlegroups.com, Paolo Valente Subject: [PATCH IMPROVEMENT/BUGFIX 4/4] block, bfq: remove superfluous check in queue-merging setup Date: Wed, 20 Dec 2017 12:38:34 +0100 Message-Id: <20171220113834.2578-5-paolo.valente@linaro.org> X-Mailer: git-send-email 2.15.1 In-Reply-To: <20171220113834.2578-1-paolo.valente@linaro.org> References: <20171220113834.2578-1-paolo.valente@linaro.org> Sender: linux-kernel-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org From: Angelo Ruocco When two or more processes do I/O in a way that the their requests are sequential in respect to one another, BFQ merges the bfq_queues associated with the processes. This way the overall I/O pattern becomes sequential, and thus there is a boost in througput. These cooperating processes usually start or restart to do I/O shortly after each other. So, in order to avoid merging non-cooperating processes, BFQ ensures that none of these queues has been in weight raising for too long. In this respect, from commit "block, bfq-sq, bfq-mq: let a queue be merged only shortly after being created", BFQ checks whether any queue (and not only weight-raised ones) is doing I/O continuously from too long to be merged. This new additional check makes the first one useless: a queue doing I/O from long enough, if being weight-raised, is also a queue in weight raising for too long to be merged. Accordingly, this commit removes the first check. Signed-off-by: Angelo Ruocco Signed-off-by: Paolo Valente --- block/bfq-iosched.c | 36 +++++------------------------------- 1 file changed, 5 insertions(+), 31 deletions(-) -- 2.15.1 diff --git a/block/bfq-iosched.c b/block/bfq-iosched.c index 320022135dc8..c66578592c9e 100644 --- a/block/bfq-iosched.c +++ b/block/bfq-iosched.c @@ -1990,20 +1990,6 @@ static bool bfq_may_be_close_cooperator(struct bfq_queue *bfqq, return true; } -/* - * If this function returns true, then bfqq cannot be merged. The idea - * is that true cooperation happens very early after processes start - * to do I/O. Usually, late cooperations are just accidental false - * positives. In case bfqq is weight-raised, such false positives - * would evidently degrade latency guarantees for bfqq. - */ -static bool wr_from_too_long(struct bfq_queue *bfqq) -{ - return bfqq->wr_coeff > 1 && - time_is_before_jiffies(bfqq->last_wr_start_finish + - msecs_to_jiffies(100)); -} - /* * Attempt to schedule a merge of bfqq with the currently in-service * queue or with a close queue among the scheduled queues. Return @@ -2017,11 +2003,6 @@ static bool wr_from_too_long(struct bfq_queue *bfqq) * to maintain. Besides, in such a critical condition as an out of memory, * the benefits of queue merging may be little relevant, or even negligible. * - * Weight-raised queues can be merged only if their weight-raising - * period has just started. In fact cooperating processes are usually - * started together. Thus, with this filter we avoid false positives - * that would jeopardize low-latency guarantees. - * * WARNING: queue merging may impair fairness among non-weight raised * queues, for at least two reasons: 1) the original weight of a * merged queue may change during the merged state, 2) even being the @@ -2052,9 +2033,7 @@ bfq_setup_cooperator(struct bfq_data *bfqd, struct bfq_queue *bfqq, if (bfqq->new_bfqq) return bfqq->new_bfqq; - if (!io_struct || - wr_from_too_long(bfqq) || - unlikely(bfqq == &bfqd->oom_bfqq)) + if (!io_struct || unlikely(bfqq == &bfqd->oom_bfqq)) return NULL; /* If there is only one backlogged queue, don't search. */ @@ -2063,12 +2042,9 @@ bfq_setup_cooperator(struct bfq_data *bfqd, struct bfq_queue *bfqq, in_service_bfqq = bfqd->in_service_queue; - if (!in_service_bfqq || in_service_bfqq == bfqq - || wr_from_too_long(in_service_bfqq) || - unlikely(in_service_bfqq == &bfqd->oom_bfqq)) - goto check_scheduled; - - if (bfq_rq_close_to_sector(io_struct, request, bfqd->last_position) && + if (in_service_bfqq && in_service_bfqq != bfqq && + likely(in_service_bfqq != &bfqd->oom_bfqq) && + bfq_rq_close_to_sector(io_struct, request, bfqd->last_position) && bfqq->entity.parent == in_service_bfqq->entity.parent && bfq_may_be_close_cooperator(bfqq, in_service_bfqq)) { new_bfqq = bfq_setup_merge(bfqq, in_service_bfqq); @@ -2080,12 +2056,10 @@ bfq_setup_cooperator(struct bfq_data *bfqd, struct bfq_queue *bfqq, * queues. The only thing we need is that the bio/request is not * NULL, as we need it to establish whether a cooperator exists. */ -check_scheduled: new_bfqq = bfq_find_close_cooperator(bfqd, bfqq, bfq_io_struct_pos(io_struct, request)); - if (new_bfqq && !wr_from_too_long(new_bfqq) && - likely(new_bfqq != &bfqd->oom_bfqq) && + if (new_bfqq && likely(new_bfqq != &bfqd->oom_bfqq) && bfq_may_be_close_cooperator(bfqq, new_bfqq)) return bfq_setup_merge(bfqq, new_bfqq);