From patchwork Thu Aug 31 06:10:20 2017 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Paolo Valente X-Patchwork-Id: 111358 Delivered-To: patch@linaro.org Received: by 10.140.95.112 with SMTP id h103csp2072796qge; Wed, 30 Aug 2017 23:11:20 -0700 (PDT) X-Received: by 10.84.217.10 with SMTP id o10mr1367379pli.75.1504159880136; Wed, 30 Aug 2017 23:11:20 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1504159880; cv=none; d=google.com; s=arc-20160816; b=Lkoi5irrYSslHhY/kg4LbdL0fh2I8WK+CagupXn9sJ86UIGWQstcaQCIkhTAUvFGRz KNCR+pMpHdKOYtjcQD99QIqdwaO2fcnDrrVX7+AQHgysJByyeurr9se4UpZW4E0zxFat D4OUnxh5lbnD6IhkSfse+yvrZLq1I63njl8uaMjPde/QbfDMneZZvBzhnE3pn6qGUmxC PiSl9o1cSZgh5FGanYaah5DuAFw/3cJCPXHKvlOY88/UmcjDz4fkKyJHzgNx760q/n3u mtUcyRChdjIXxlwFN3zQ6lUtFHT4bR/hLBsB+mykKRFwOTfxzRemrRTiRZ/lURfE6rMU kMWg== 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=tFlb0gTtD3R9ZfOW4b3rsoVbqESDnjC4fYXlTnwXMi8=; b=p2PYJ9/52ZXCZA/DTLHmT+qIzNjhH/CmS6kbD/tDRVf3aVAdNMFOohaJCXSRFu6Erj mT9TaziBgtsxt/rOBVmZ0sLNOuDbhpxYkeE1dYenE9H5DaBRLZsOxPw4uEd33ZmtCpyT EoEmZSyVc+N3n/sg1x3lWl0JxME+TVr7clecIl3S09ClKuakZ5XER8SPrbCvrStoxWeE HBpCPQy/iRnW+SJUjB6gmElrDrIvxGDWsZk3ImdRyIIQ68nXV6N55RVqDQSSBeg8BRfm auBgPYkuTiHjNqoCFv7qNsV3Thu4Ffxv+8DYgzyVwajh6tyMigs4XLEzhyUF4I4QK/Ne CafA== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@linaro.org header.s=google header.b=Fs58h5Vy; 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 h15si6255291plk.820.2017.08.30.23.11.17; Wed, 30 Aug 2017 23:11:20 -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=Fs58h5Vy; 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 S1751457AbdHaGLP (ORCPT + 26 others); Thu, 31 Aug 2017 02:11:15 -0400 Received: from mail-wm0-f50.google.com ([74.125.82.50]:33205 "EHLO mail-wm0-f50.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1751417AbdHaGK4 (ORCPT ); Thu, 31 Aug 2017 02:10:56 -0400 Received: by mail-wm0-f50.google.com with SMTP id r202so6107193wmd.0 for ; Wed, 30 Aug 2017 23:10:55 -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=tFlb0gTtD3R9ZfOW4b3rsoVbqESDnjC4fYXlTnwXMi8=; b=Fs58h5VyAXQfRN2FUukaD6fnNaK72Y0k1FVlf7XAZrPQLUjqdoW1a5+3uDSOKlZhea N3+NgSw9GOOSDptILosil9f1cd3+2bv3+LzCGUK/EqZiG+SRvaQ8Ht17zygA2vE4rQB5 KmaJ7YnqTPF94DhkuJwk94q6LyvBrMsbAsi2E= 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=tFlb0gTtD3R9ZfOW4b3rsoVbqESDnjC4fYXlTnwXMi8=; b=IC4s8/IDBzbMTuKDlGeemtyPrYtrzl+2FtidfBMt/CMTGIUv1obTy4HHhn93lk3DtY 0Vj7aKAR8ikFGVSY/2qYA0fwZpO3h4vThHICzxpXGuf45E4nlHHtbhFKw/dWhJcu3s8I yEP83wsaWKhbQHq1QDzVyYFNez+cvi8hHyW8JK+eJ5+voaShvmDDF8x2+48i7pOOecia /1VWT12QP7cZRiZ0jFIsfsf3yA7zYA/9aCRsS7qvIFZ96SLn3sJDhT0Okxk6a/QUoMEm cpxY76Yvt6hHPXsOM9WRkbmltz6+r8nQLNAGVe+A+YNErgaEYe7P0SG+cWFyb8LCPSTs 7kbA== X-Gm-Message-State: AHYfb5gzUkae0UXGohDFb+Wg3/DkvYlSQ9HE7i6ISLCGdmOUItxQjxzd 5si+86U3FbBnUg8b X-Received: by 10.28.14.73 with SMTP id 70mr2488289wmo.34.1504159854260; Wed, 30 Aug 2017 23:10:54 -0700 (PDT) Received: from localhost.localdomain ([185.14.8.94]) by smtp.gmail.com with ESMTPSA id t8sm6676897wrg.21.2017.08.30.23.10.52 (version=TLS1 cipher=AES128-SHA bits=128/128); Wed, 30 Aug 2017 23:10:53 -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 3/3] block, bfq: guarantee update_next_in_service always returns an eligible entity Date: Thu, 31 Aug 2017 08:10:20 +0200 Message-Id: <20170831061020.4426-4-paolo.valente@linaro.org> X-Mailer: git-send-email 2.10.0 In-Reply-To: <20170831061020.4426-1-paolo.valente@linaro.org> References: <20170831061020.4426-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: Oleksander 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;