summaryrefslogtreecommitdiffstats
path: root/block/bfq-wf2q.c
diff options
context:
space:
mode:
Diffstat (limited to 'block/bfq-wf2q.c')
-rw-r--r--block/bfq-wf2q.c91
1 files changed, 56 insertions, 35 deletions
diff --git a/block/bfq-wf2q.c b/block/bfq-wf2q.c
index 911aa7431dbe..414ba686a847 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,19 +75,20 @@ 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;
+ bool change_without_lookup = false;
/*
* If this update is triggered by the activation, requeueing
* 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.
@@ -96,13 +100,12 @@ 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
- * 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 =
@@ -110,32 +113,26 @@ 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 =
+ change_without_lookup =
(new_entity_class_idx ==
bfq_class_idx(next_in_service)
&&
!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)
+ if (change_without_lookup)
next_in_service = new_entity;
- } else /* invoked because of a deactivation: lookup needed */
- next_in_service = bfq_lookup_next_entity(sd);
+ }
+
+ 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;
@@ -1127,10 +1124,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;
@@ -1138,7 +1137,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;
}
}
@@ -1194,6 +1194,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,
@@ -1222,7 +1224,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) {
/*
@@ -1281,7 +1283,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
@@ -1416,12 +1418,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);
@@ -1448,8 +1452,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;
@@ -1562,7 +1582,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;
}
@@ -1610,16 +1630,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);
}
/*