From patchwork Thu Aug 31 06:46: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: 111362 Delivered-To: patch@linaro.org Received: by 10.140.95.112 with SMTP id h103csp2107015qge; Wed, 30 Aug 2017 23:47:02 -0700 (PDT) X-Received: by 10.84.238.134 with SMTP id v6mr1475219plk.187.1504162021971; Wed, 30 Aug 2017 23:47:01 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1504162021; cv=none; d=google.com; s=arc-20160816; b=dqxB8lnRnh7rRC102chApgIUidteGzSgThZM1v5SUbDU2cSW9ISZjqFYLybVd0wKa/ 2eEz5J/aja6UZtXeT/py76M9CWoes9kcPKJxKLUWcdHrykWdx7hFWg2s5uE+gMkECTS4 Ekmdw4pY+WwuNpr4G+GRcktFi41HD3QH/ZdmHtzHtVqcv4VaBiTit8RhZBhkauf8r4iq XTQ7kdXbER3/htxYZzwIJsUkXfw3Ecn1ey//fBpSQiRqeAc/wSoquL7rSJcC9M2eWNhK MRHuOl5nH3xMGArr/VqUz6aYBtcHqqyH/qdo+yFElbX+Zq419WNsOQmz3EnEgUSSTd5o B5Sg== 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=UegtACuFkVMVkjT5M5KWgjSma1pHi5BamVOlGevAwlo=; b=ARpHp0DQDprMB43jxobzvJuqYbSboVbPBmmUCDx6OmSbuBdC5HWfS35deYtlmr9ZRQ KeyBD6rT9aJU9mc3o72Fm41QYIXGr9LV9el5vRlpQIr3fUmhW6v0RnRrDEvQUBjUAD0f dbQVc934wmrSkxu3hLYAohbpbt0NRHNzxNj7YcKkVrFD7aozOMjRPuvbFoH08aYUDkay 6oxF611h5Dtu+RnksUIjrsq+uJ1q5cXpaL6ZVneXh1uI/n57xh2yZsQlVXx746zgTvSM NW6+TFAxnd7DZNmnnGTOhsZUa38ifqHRbPlJO/uSZFaO0lhFbQHbiZAZNuj4PSUyBd2u eRrQ== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@linaro.org header.s=google header.b=dYodH8jd; 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 q132si5929992pgq.540.2017.08.30.23.47.01; Wed, 30 Aug 2017 23:47:01 -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=dYodH8jd; 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 S1751367AbdHaGq7 (ORCPT + 26 others); Thu, 31 Aug 2017 02:46:59 -0400 Received: from mail-wr0-f172.google.com ([209.85.128.172]:34306 "EHLO mail-wr0-f172.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1751250AbdHaGqu (ORCPT ); Thu, 31 Aug 2017 02:46:50 -0400 Received: by mail-wr0-f172.google.com with SMTP id z91so23669413wrc.1 for ; Wed, 30 Aug 2017 23:46:50 -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=UegtACuFkVMVkjT5M5KWgjSma1pHi5BamVOlGevAwlo=; b=dYodH8jdEKBzWs9hmi1o0mR/PEbyF50U6YXwOTumpZrZ/6N2Y2pP+rL7DV+mE21PbW pOMK1LfjGArs8PU0UTccD6DDf4p8PZuCeqesWgq+7QQZwu+E8dIosJHay5zmD2Co0z+S 6g+BRZLc4ijgitebNn3ICyPmD4l3uGl9sOyuc= 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=UegtACuFkVMVkjT5M5KWgjSma1pHi5BamVOlGevAwlo=; b=Ap+AHTZsMp04JrUFMvYfERA2PVuXHSkxoVoaXvbxRXE9AuG8xdj9MJliSMt7sv2veP F76h0xpoFwmhgea9q7Yh+1iA+A2v8eFA16QMQgLda5SqGQIAZz5zrx8FQGGypctkmhwU YNg3KjmwdI/OPIcn3xEPdU+Telm/W65Y8gATH5FqmzH200R7E+IBjWzSL0HI/t0D6rhV jpySnaM7lzjH6tGMTzfBE/6kBXa2vSC1EFx/N8DJwsAoJNoxhHxKnY0dRXAlvOQYdTju Y08pA1L8i0O1AobOF0hh/4Tifl2GQucbop2y7Y0tS1gUAXtM+ZOJwOnUvvtR7+vOcuz/ qpYQ== X-Gm-Message-State: AHYfb5hLp0AsM6/PBT1+uFGWYEkHTvXNcuhwbfXdD6xb3ZEMrwJcQNkl DoDoJyHbumDOHR2q X-Received: by 10.223.187.75 with SMTP id x11mr2398632wrg.103.1504162009428; Wed, 30 Aug 2017 23:46:49 -0700 (PDT) Received: from localhost.localdomain ([185.14.8.94]) by smtp.gmail.com with ESMTPSA id s15sm6497667wrg.84.2017.08.30.23.46.47 (version=TLS1 cipher=AES128-SHA bits=128/128); Wed, 30 Aug 2017 23:46:48 -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, mgorman@techsingularity.net, lee.tibbert@gmail.com, oleksandr@natalenko.name, Paolo Valente Subject: [PATCH BUGFIX/IMPROVEMENT V2 3/3] block, bfq: guarantee update_next_in_service always returns an eligible entity Date: Thu, 31 Aug 2017 08:46:31 +0200 Message-Id: <20170831064631.2223-4-paolo.valente@linaro.org> X-Mailer: git-send-email 2.10.0 In-Reply-To: <20170831064631.2223-1-paolo.valente@linaro.org> References: <20170831064631.2223-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 the function bfq_update_next_in_service is invoked as a consequence of the activation or requeueing of an entity, say E, then it doesn't invoke bfq_lookup_next_entity to get the next-in-service entity. In contrast, it follows a shorter path: if E happens to be eligible (see commit "bfq-sq-mq: make lookup_next_entity push up vtime on expirations" for details on eligibility) and to have a lower virtual finish time than the current candidate as next-in-service entity, then E directly becomes the next-in-service entity. Unfortunately, there is a corner case for which this shorter path makes bfq_update_next_in_service choose a non eligible entity: it occurs if both E and the current next-in-service entity happen to be non eligible when bfq_update_next_in_service is invoked. In this case, E is not set as next-in-service, and, since bfq_lookup_next_entity is not invoked, the state of the parent entity is not updated so as to end up with an eligible entity as the proper next-in-service entity. In this respect, next-in-service is actually allowed to be non eligible while some queue is in service: since no system-virtual-time push-up can be performed in that case (see again commit "bfq-sq-mq: make lookup_next_entity push up vtime on expirations" for details), next-in-service is chosen, speculatively, as a function of the possible value that the system virtual time may get after a push up. But the correctness of the schedule breaks if next-in-service is still a non eligible entity when it is time to set in service the next entity. Unfortunately, this may happen in the above corner case. This commit fixes this problem by making bfq_update_next_in_service invoke bfq_lookup_next_entity not only if the above shorter path cannot be taken, but also if the shorter path is taken but fails to yield an eligible next-in-service entity. Signed-off-by: Paolo Valente Tested-by: Lee Tibbert Tested-by: Oleksandr Natalenko --- block/bfq-wf2q.c | 14 ++++++++------ 1 file changed, 8 insertions(+), 6 deletions(-) -- 2.10.0 diff --git a/block/bfq-wf2q.c b/block/bfq-wf2q.c index eeaf326..add54f2 100644 --- a/block/bfq-wf2q.c +++ b/block/bfq-wf2q.c @@ -80,6 +80,7 @@ static bool bfq_update_next_in_service(struct bfq_sched_data *sd, { struct bfq_entity *next_in_service = sd->next_in_service; bool parent_sched_may_change = false; + bool change_without_lookup = false; /* * If this update is triggered by the activation, requeueing @@ -99,7 +100,7 @@ static bool bfq_update_next_in_service(struct bfq_sched_data *sd, * set to true, and left as true if * sd->next_in_service is NULL. */ - bool replace_next = true; + change_without_lookup = true; /* * If there is already a next_in_service candidate @@ -112,7 +113,7 @@ static bool bfq_update_next_in_service(struct bfq_sched_data *sd, struct bfq_service_tree *st = sd->service_tree + new_entity_class_idx; - replace_next = + change_without_lookup = (new_entity_class_idx == bfq_class_idx(next_in_service) && @@ -122,15 +123,16 @@ static bool bfq_update_next_in_service(struct bfq_sched_data *sd, new_entity->finish)); } - if (replace_next) + if (change_without_lookup) next_in_service = new_entity; - } else /* invoked because of a deactivation: lookup needed */ + } + + if (!change_without_lookup) /* lookup needed */ next_in_service = bfq_lookup_next_entity(sd, expiration); - if (next_in_service) { + if (next_in_service) parent_sched_may_change = !sd->next_in_service || bfq_update_parent_budget(next_in_service); - } sd->next_in_service = next_in_service;