From patchwork Thu Aug 31 06:46:29 2017 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Paolo Valente X-Patchwork-Id: 111361 Delivered-To: patch@linaro.org Received: by 10.140.95.112 with SMTP id h103csp2106903qge; Wed, 30 Aug 2017 23:46:53 -0700 (PDT) X-Received: by 10.98.51.2 with SMTP id z2mr1207774pfz.309.1504162013464; Wed, 30 Aug 2017 23:46:53 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1504162013; cv=none; d=google.com; s=arc-20160816; b=F/jVCJxx/O0Dv86ZdlSsawNNUAitfod+hlsCmrfOkqp0lv8+pbYQRpigZ3UvYHuJ2z ddU9UvhcE8HDYP4P8qmmTa9DCNaFv8QOVHGrtlUgNJ01b+q1mldFPzRtLfBg4FsTHPED +UE6gCEXvJCD+5CRC8gxuyImVe8Z9yOGr3e9ynAslyj6xBS/pgdOXT6SZwMh+GYmfarR /vcLSFpDyu4myGh794qtZLbjfQ5s+wQ7lM5hS66inbV1ohg1SE7C1WxCX7ZTZBRYC2sT v+DqAo5KiJtGJ4bGAeF/D6Ubv4we3zqxXb3CQIU03aOmlSDd8GAD7a1Z59paYUbj+ef2 meEw== 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=MNdZp05kyhRYhH+C3BeJaWoZK2kI4/TdBYWEo2K1v/g=; b=utK3QW4BEzpc6ICcW+ZKa2mkIAzH9Z3QQaWI8RXEQ8lhycS5ewnZkZBMbVV1j1P1fR RJTVIzCv02WdAYFTL3jnBkgN+y00VadswB0sDbSWTUqCe1teSHC96jss8WJgr/PCiOBN +2nacKcXo8ZkHHF5C7RTm91ItUsIp//0q1EB+heA8kc6mE3yWqNPvbj6ZUwkrxL68/Yc ii0jTM9aTm77dzN3b31h8B9VnuHxfVLeAfF7j66xSBQZSgGn6dq7yPii0oFWG6H4s8Xf 920xlxJNAEGbFPAotVKPmqMbjMo0QloZo57UwobTfAMByCifiZYm++aj5U8Jmd/qfJsM qkMg== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@linaro.org header.s=google header.b=BPycIFoA; 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 b96si6137509pli.420.2017.08.30.23.46.53; Wed, 30 Aug 2017 23:46:53 -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=BPycIFoA; 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 S1751325AbdHaGqv (ORCPT + 26 others); Thu, 31 Aug 2017 02:46:51 -0400 Received: from mail-wr0-f172.google.com ([209.85.128.172]:38507 "EHLO mail-wr0-f172.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1750998AbdHaGqr (ORCPT ); Thu, 31 Aug 2017 02:46:47 -0400 Received: by mail-wr0-f172.google.com with SMTP id 40so23125553wrv.5 for ; Wed, 30 Aug 2017 23:46:46 -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=MNdZp05kyhRYhH+C3BeJaWoZK2kI4/TdBYWEo2K1v/g=; b=BPycIFoAyeXDAm88wtKhAASTqzsx9DCXx4kXQlZ2govyHYQxkm+E4XDoBkfrbFwMtv OyB60+C8idF28bDcQk5iMU1inVFXptr6Mhhle4jkmAIHYNjJoUrlP4H5D03TT++m9U+e 3mX9Y30CY1kk7l2Z8OUeyLuDjsQfA7vrtCCiI= 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=MNdZp05kyhRYhH+C3BeJaWoZK2kI4/TdBYWEo2K1v/g=; b=q79FZPbrA03P7FdgcJRyz4zKgaQQRAa5mN6vRblcWjrl10S6dY71Z6gg7gvz+1taQQ V+STXHZiqC6/OhlG0VpOuuLKWvqV/Y2NpMcuu8cRzQ2hE0egMF5ALVHl5s7i1VHb7Pi0 hX8QRKtUXiJQ5iEhb3k1EET8lrL94BxeJmSJBz3kTJr1wrGQECfu4aUIfUCNxiIIIUnT GfNPPwDds95sm4Fgz13nEY+WWl116MogB3Gzu+Fxek6/a3x3hZuinT0odB6iwmUk6u9J 9hS6TYxYX5kmZx1k0NukY1AC53PDsGuYalaCr3vtASdQEOGnY44w0nqoInlAhys4Q37G np4w== X-Gm-Message-State: AHYfb5iOW2gCRKDa9NNQ2n88BEI4NL2JKHCxHA0Ec7UxOetTgUH+d+wL xkjHMujHhTxdZ3+J X-Received: by 10.223.133.241 with SMTP id 46mr2178725wru.159.1504162005583; Wed, 30 Aug 2017 23:46:45 -0700 (PDT) Received: from localhost.localdomain ([185.14.8.94]) by smtp.gmail.com with ESMTPSA id s15sm6497667wrg.84.2017.08.30.23.46.43 (version=TLS1 cipher=AES128-SHA bits=128/128); Wed, 30 Aug 2017 23:46:44 -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 1/3] block, bfq: make lookup_next_entity push up vtime on expirations Date: Thu, 31 Aug 2017 08:46:29 +0200 Message-Id: <20170831064631.2223-2-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 To provide a very smooth service, bfq starts to serve a bfq_queue only if the queue is 'eligible', i.e., if the same queue would have started to be served in the ideal, perfectly fair system that bfq simulates internally. This is obtained by associating each queue with a virtual start time, and by computing a special system virtual time quantity: a queue is eligible only if the system virtual time has reached the virtual start time of the queue. Finally, bfq guarantees that, when a new queue must be set in service, there is always at least one eligible entity for each active parent entity in the scheduler. To provide this guarantee, the function __bfq_lookup_next_entity pushes up, for each parent entity on which it is invoked, the system virtual time to the minimum among the virtual start times of the entities in the active tree for the parent entity (more precisely, the push up occurs if the system virtual time happens to be lower than all such virtual start times). There is however a circumstance in which __bfq_lookup_next_entity cannot push up the system virtual time for a parent entity, even if the system virtual time is lower than the virtual start times of all the child entities in the active tree. It happens if one of the child entities is in service. In fact, in such a case, there is already an eligible entity, the in-service one, even if it may not be not present in the active tree (because in-service entities may be removed from the active tree). Unfortunately, in the last re-design of the hierarchical-scheduling engine, the reset of the pointer to the in-service entity for a given parent entity--reset to be done as a consequence of the expiration of the in-service entity--always happens after the function __bfq_lookup_next_entity has been invoked. This causes the function to think that there is still an entity in service for the parent entity, and then that the system virtual time cannot be pushed up, even if actually such a no-more-in-service entity has already been properly reinserted into the active tree (or in some other tree if no more active). Yet, the system virtual time *had* to be pushed up, to be ready to correctly choose the next queue to serve. Because of the lack of this push up, bfq may wrongly set in service a queue that had been speculatively pre-computed as the possible next-in-service queue, but that would no more be the one to serve after the expiration and the reinsertion into the active trees of the previously in-service entities. This commit addresses this issue by making __bfq_lookup_next_entity properly push up the system virtual time if an expiration is occurring. Signed-off-by: Paolo Valente Tested-by: Lee Tibbert Tested-by: Oleksandr Natalenko --- block/bfq-iosched.c | 4 ++-- block/bfq-iosched.h | 4 ++-- block/bfq-wf2q.c | 58 +++++++++++++++++++++++++++++++++++++++-------------- 3 files changed, 47 insertions(+), 19 deletions(-) -- 2.10.0 diff --git a/block/bfq-iosched.c b/block/bfq-iosched.c index 436b6ca..a10f147 100644 --- a/block/bfq-iosched.c +++ b/block/bfq-iosched.c @@ -720,7 +720,7 @@ static void bfq_updated_next_req(struct bfq_data *bfqd, entity->budget = new_budget; bfq_log_bfqq(bfqd, bfqq, "updated next rq: new budget %lu", new_budget); - bfq_requeue_bfqq(bfqd, bfqq); + bfq_requeue_bfqq(bfqd, bfqq, false); } } @@ -2563,7 +2563,7 @@ static void __bfq_bfqq_expire(struct bfq_data *bfqd, struct bfq_queue *bfqq) bfq_del_bfqq_busy(bfqd, bfqq, true); } else { - bfq_requeue_bfqq(bfqd, bfqq); + bfq_requeue_bfqq(bfqd, bfqq, true); /* * Resort priority tree of potential close cooperators. */ diff --git a/block/bfq-iosched.h b/block/bfq-iosched.h index 859f0a8..3e2659c 100644 --- a/block/bfq-iosched.h +++ b/block/bfq-iosched.h @@ -817,7 +817,6 @@ extern const int bfq_timeout; struct bfq_queue *bic_to_bfqq(struct bfq_io_cq *bic, bool is_sync); void bic_set_bfqq(struct bfq_io_cq *bic, struct bfq_queue *bfqq, bool is_sync); struct bfq_data *bic_to_bfqd(struct bfq_io_cq *bic); -void bfq_requeue_bfqq(struct bfq_data *bfqd, struct bfq_queue *bfqq); void bfq_pos_tree_add_move(struct bfq_data *bfqd, struct bfq_queue *bfqq); void bfq_weights_tree_add(struct bfq_data *bfqd, struct bfq_entity *entity, struct rb_root *root); @@ -917,7 +916,8 @@ void __bfq_bfqd_reset_in_service(struct bfq_data *bfqd); void bfq_deactivate_bfqq(struct bfq_data *bfqd, struct bfq_queue *bfqq, bool ins_into_idle_tree, bool expiration); void bfq_activate_bfqq(struct bfq_data *bfqd, struct bfq_queue *bfqq); -void bfq_requeue_bfqq(struct bfq_data *bfqd, struct bfq_queue *bfqq); +void bfq_requeue_bfqq(struct bfq_data *bfqd, struct bfq_queue *bfqq, + bool expiration); void bfq_del_bfqq_busy(struct bfq_data *bfqd, struct bfq_queue *bfqq, bool expiration); void bfq_add_bfqq_busy(struct bfq_data *bfqd, struct bfq_queue *bfqq); diff --git a/block/bfq-wf2q.c b/block/bfq-wf2q.c index 3183b39..138732e 100644 --- a/block/bfq-wf2q.c +++ b/block/bfq-wf2q.c @@ -44,7 +44,8 @@ static unsigned int bfq_class_idx(struct bfq_entity *entity) BFQ_DEFAULT_GRP_CLASS - 1; } -static struct bfq_entity *bfq_lookup_next_entity(struct bfq_sched_data *sd); +static struct bfq_entity *bfq_lookup_next_entity(struct bfq_sched_data *sd, + bool expiration); static bool bfq_update_parent_budget(struct bfq_entity *next_in_service); @@ -54,6 +55,8 @@ static bool bfq_update_parent_budget(struct bfq_entity *next_in_service); * @new_entity: if not NULL, pointer to the entity whose activation, * requeueing or repositionig triggered the invocation of * this function. + * @expiration: id true, this function is being invoked after the + * expiration of the in-service entity * * This function is called to update sd->next_in_service, which, in * its turn, may change as a consequence of the insertion or @@ -72,7 +75,8 @@ static bool bfq_update_parent_budget(struct bfq_entity *next_in_service); * entity. */ static bool bfq_update_next_in_service(struct bfq_sched_data *sd, - struct bfq_entity *new_entity) + struct bfq_entity *new_entity, + bool expiration) { struct bfq_entity *next_in_service = sd->next_in_service; bool parent_sched_may_change = false; @@ -130,7 +134,7 @@ static bool bfq_update_next_in_service(struct bfq_sched_data *sd, if (replace_next) next_in_service = new_entity; } else /* invoked because of a deactivation: lookup needed */ - next_in_service = bfq_lookup_next_entity(sd); + next_in_service = bfq_lookup_next_entity(sd, expiration); if (next_in_service) { parent_sched_may_change = !sd->next_in_service || @@ -1134,10 +1138,12 @@ static void __bfq_activate_requeue_entity(struct bfq_entity *entity, * @requeue: true if this is a requeue, which implies that bfqq is * being expired; thus ALL its ancestors stop being served and must * therefore be requeued + * @expiration: true if this function is being invoked in the expiration path + * of the in-service queue */ static void bfq_activate_requeue_entity(struct bfq_entity *entity, bool non_blocking_wait_rq, - bool requeue) + bool requeue, bool expiration) { struct bfq_sched_data *sd; @@ -1145,7 +1151,8 @@ static void bfq_activate_requeue_entity(struct bfq_entity *entity, sd = entity->sched_data; __bfq_activate_requeue_entity(entity, sd, non_blocking_wait_rq); - if (!bfq_update_next_in_service(sd, entity) && !requeue) + if (!bfq_update_next_in_service(sd, entity, expiration) && + !requeue) break; } } @@ -1201,6 +1208,8 @@ bool __bfq_deactivate_entity(struct bfq_entity *entity, bool ins_into_idle_tree) * bfq_deactivate_entity - deactivate an entity representing a bfq_queue. * @entity: the entity to deactivate. * @ins_into_idle_tree: true if the entity can be put into the idle tree + * @expiration: true if this function is being invoked in the expiration path + * of the in-service queue */ static void bfq_deactivate_entity(struct bfq_entity *entity, bool ins_into_idle_tree, @@ -1229,7 +1238,7 @@ static void bfq_deactivate_entity(struct bfq_entity *entity, * then, since entity has just been * deactivated, a new one must be found. */ - bfq_update_next_in_service(sd, NULL); + bfq_update_next_in_service(sd, NULL, expiration); if (sd->next_in_service || sd->in_service_entity) { /* @@ -1288,7 +1297,7 @@ static void bfq_deactivate_entity(struct bfq_entity *entity, __bfq_requeue_entity(entity); sd = entity->sched_data; - if (!bfq_update_next_in_service(sd, entity) && + if (!bfq_update_next_in_service(sd, entity, expiration) && !expiration) /* * next_in_service unchanged or not causing @@ -1423,12 +1432,14 @@ __bfq_lookup_next_entity(struct bfq_service_tree *st, bool in_service) /** * bfq_lookup_next_entity - return the first eligible entity in @sd. * @sd: the sched_data. + * @expiration: true if we are on the expiration path of the in-service queue * * This function is invoked when there has been a change in the trees - * for sd, and we need know what is the new next entity after this - * change. + * for sd, and we need to know what is the new next entity to serve + * after this change. */ -static struct bfq_entity *bfq_lookup_next_entity(struct bfq_sched_data *sd) +static struct bfq_entity *bfq_lookup_next_entity(struct bfq_sched_data *sd, + bool expiration) { struct bfq_service_tree *st = sd->service_tree; struct bfq_service_tree *idle_class_st = st + (BFQ_IOPRIO_CLASSES - 1); @@ -1455,8 +1466,24 @@ static struct bfq_entity *bfq_lookup_next_entity(struct bfq_sched_data *sd) * class, unless the idle class needs to be served. */ for (; class_idx < BFQ_IOPRIO_CLASSES; class_idx++) { + /* + * If expiration is true, then bfq_lookup_next_entity + * is being invoked as a part of the expiration path + * of the in-service queue. In this case, even if + * sd->in_service_entity is not NULL, + * sd->in_service_entiy at this point is actually not + * in service any more, and, if needed, has already + * been properly queued or requeued into the right + * tree. The reason why sd->in_service_entity is still + * not NULL here, even if expiration is true, is that + * sd->in_service_entiy is reset as a last step in the + * expiration path. So, if expiration is true, tell + * __bfq_lookup_next_entity that there is no + * sd->in_service_entity. + */ entity = __bfq_lookup_next_entity(st + class_idx, - sd->in_service_entity); + sd->in_service_entity && + !expiration); if (entity) break; @@ -1569,7 +1596,7 @@ struct bfq_queue *bfq_get_next_queue(struct bfq_data *bfqd) for_each_entity(entity) { struct bfq_sched_data *sd = entity->sched_data; - if (!bfq_update_next_in_service(sd, NULL)) + if (!bfq_update_next_in_service(sd, NULL, false)) break; } @@ -1617,16 +1644,17 @@ void bfq_activate_bfqq(struct bfq_data *bfqd, struct bfq_queue *bfqq) struct bfq_entity *entity = &bfqq->entity; bfq_activate_requeue_entity(entity, bfq_bfqq_non_blocking_wait_rq(bfqq), - false); + false, false); bfq_clear_bfqq_non_blocking_wait_rq(bfqq); } -void bfq_requeue_bfqq(struct bfq_data *bfqd, struct bfq_queue *bfqq) +void bfq_requeue_bfqq(struct bfq_data *bfqd, struct bfq_queue *bfqq, + bool expiration) { struct bfq_entity *entity = &bfqq->entity; bfq_activate_requeue_entity(entity, false, - bfqq == bfqd->in_service_queue); + bfqq == bfqd->in_service_queue, expiration); } /* From patchwork Thu Aug 31 06:46:30 2017 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Paolo Valente X-Patchwork-Id: 111363 Delivered-To: patch@linaro.org Received: by 10.140.95.112 with SMTP id h103csp2107424qge; Wed, 30 Aug 2017 23:47:29 -0700 (PDT) X-Received: by 10.98.200.218 with SMTP id i87mr1263516pfk.85.1504162049091; Wed, 30 Aug 2017 23:47:29 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1504162049; cv=none; d=google.com; s=arc-20160816; b=Q657wi3nGgHAhIPgmNUUiCGWLpGJBUPCN4JoZdatYeTBcBgaof6j+AMyF4cGgT1HVf n33TraRY0x8XzSNJdU717cErM/TH4qf7p+4nDioFuBPwZllPBQf6zJ0jGecOdt3SeBzx pZTSYQt7Xnj+PcEjmMxNjhjLd4TOBsYX+UhMpuSOqmmfKcrGjHXoYC3Ju8Qctf1uLYYc XY1rp1L94GR05po3WY0GhHXeKvlUs7x3+HyDNVsgdYl6XsGpPaZL9owpTUL7AEB5enjR k2J5G0Yj9Vg2MyrL1G88hhnusroL//qXvI2wn8bKKno6sjrF3pnNoRD6syVOjwIVbcZ4 SRow== 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=YjEtdvjfb9xLDIrEUJbj7IcmuE/lWWeOhnohyU29UQs=; b=S26OWKLYsDThtU/s7jS6gNTRFNs2AP60HMnbSsUUGX0EDcpJH0OKfxlIoOluHcAXH0 1qh1J8wgUqDY6hl2fLk2F4qunGxedSzRKm/xh66hhNnTDVOcCMChOief9KqezhbhLHrc R+GZKY7xQ9oFOk8CQGzS143VvAVs6FTlSEE1wolvYSg2HHLSFQJQC7v4J1yHwRWrmnsh s6NImukP9Mgyo8KI0zllQm70MdG0qqJCq9aTaVZ5OaqXoPfzUcCC7h/32CmNJL8mcMgP 26zahGJ2EznyqAk/aaHNGns95Loq6hOGJdXBL+8mdscnf235mTGifceTnC2nHeHnGMWn yKEg== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@linaro.org header.s=google header.b=YrMmmocJ; 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 d21si3588136pgn.394.2017.08.30.23.47.28; Wed, 30 Aug 2017 23:47:29 -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=YrMmmocJ; 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 S1751431AbdHaGrY (ORCPT + 26 others); Thu, 31 Aug 2017 02:47:24 -0400 Received: from mail-wr0-f170.google.com ([209.85.128.170]:33733 "EHLO mail-wr0-f170.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1751205AbdHaGqs (ORCPT ); Thu, 31 Aug 2017 02:46:48 -0400 Received: by mail-wr0-f170.google.com with SMTP id k94so23705598wrc.0 for ; Wed, 30 Aug 2017 23:46:48 -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=YjEtdvjfb9xLDIrEUJbj7IcmuE/lWWeOhnohyU29UQs=; b=YrMmmocJZ+6DIre4qYxdCrrbIK1M5cUEECkjgcW6lAbmIjEw2yMQnc7Pu6tMUm1H9M UN7aolGANHACoS796jnkAsyduS0e8vYTsrPBcgo1nVTKMhea1PJEfJNxDpZ1PZjHvC2+ 7iUtj4dlWf6GAB4FhhJqNb7MJ+ZRuNiKfk6Qc= 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=YjEtdvjfb9xLDIrEUJbj7IcmuE/lWWeOhnohyU29UQs=; b=D8sAHHDZNKQ1SkxD3faV7e+oQ+R9kCOkdxlAR+Rzm8OwyvndlKGlpHFIFjVeZEZNRS LfPHPDgeTb65ASntN+ZbYbA0/uOpFEv0xZKDQr6Euw30X7OWbGLX9ePX8B7hg5NJIb3+ ipXP9eYpboGqWeZf90f7BuXV9tSy2o6c1itfF2w3Kz415X+CptMY38MdOWS3pS/wfwLx lmzzHMJUXx6pXZgaf+0IKhZ0VSUCooxKG7s0oJwTKyKIYvaM5MpGC9lVhnKXIHy2zlZu DHvyIS7VLQYOFmm5+sMBrNEOtEjr+525qeQkACJCJs4NahwzOtNaQ4dCBcrQ3wvkfDKO q4YQ== X-Gm-Message-State: AHYfb5hXppngXNxNgfVbUjcaCglWlMPN6P0VTDTpHx0PnbUo31mpDuXp b2MQIoXDMzenHX94 X-Received: by 10.223.148.101 with SMTP id 92mr2259847wrq.182.1504162007481; Wed, 30 Aug 2017 23:46:47 -0700 (PDT) Received: from localhost.localdomain ([185.14.8.94]) by smtp.gmail.com with ESMTPSA id s15sm6497667wrg.84.2017.08.30.23.46.45 (version=TLS1 cipher=AES128-SHA bits=128/128); Wed, 30 Aug 2017 23:46:46 -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 2/3] block, bfq: remove direct switch to an entity in higher class Date: Thu, 31 Aug 2017 08:46:30 +0200 Message-Id: <20170831064631.2223-3-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, and finds out that E belongs to a higher-priority class than that of the current next-in-service entity, then it sets next_in_service directly to E. But this may lead to anomalous schedules, because E may happen not be eligible for service, because its virtual start time is higher than the system virtual time for its service tree. This commit addresses this issue by simply removing this direct switch. Signed-off-by: Paolo Valente Tested-by: Lee Tibbert Tested-by: Oleksandr Natalenko --- block/bfq-wf2q.c | 19 +++++-------------- 1 file changed, 5 insertions(+), 14 deletions(-) -- 2.10.0 diff --git a/block/bfq-wf2q.c b/block/bfq-wf2q.c index 138732e..eeaf326 100644 --- a/block/bfq-wf2q.c +++ b/block/bfq-wf2q.c @@ -86,9 +86,8 @@ static bool bfq_update_next_in_service(struct bfq_sched_data *sd, * or repositiong of an entity that does not coincide with * sd->next_in_service, then a full lookup in the active tree * can be avoided. In fact, it is enough to check whether the - * just-modified entity has a higher priority than - * sd->next_in_service, or, even if it has the same priority - * as sd->next_in_service, is eligible and has a lower virtual + * just-modified entity has the same priority as + * sd->next_in_service, is eligible and has a lower virtual * finish time than sd->next_in_service. If this compound * condition holds, then the new entity becomes the new * next_in_service. Otherwise no change is needed. @@ -104,9 +103,8 @@ static bool bfq_update_next_in_service(struct bfq_sched_data *sd, /* * If there is already a next_in_service candidate - * entity, then compare class priorities or timestamps - * to decide whether to replace sd->service_tree with - * new_entity. + * entity, then compare timestamps to decide whether + * to replace sd->service_tree with new_entity. */ if (next_in_service) { unsigned int new_entity_class_idx = @@ -114,10 +112,6 @@ static bool bfq_update_next_in_service(struct bfq_sched_data *sd, struct bfq_service_tree *st = sd->service_tree + new_entity_class_idx; - /* - * For efficiency, evaluate the most likely - * sub-condition first. - */ replace_next = (new_entity_class_idx == bfq_class_idx(next_in_service) @@ -125,10 +119,7 @@ static bool bfq_update_next_in_service(struct bfq_sched_data *sd, !bfq_gt(new_entity->start, st->vtime) && bfq_gt(next_in_service->finish, - new_entity->finish)) - || - new_entity_class_idx < - bfq_class_idx(next_in_service); + new_entity->finish)); } if (replace_next) 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;