diff options
author | sirlucjan | 2017-08-01 15:04:07 +0200 |
---|---|---|
committer | sirlucjan | 2017-08-01 15:04:07 +0200 |
commit | ece576f82876545fc2904e4e606d40abe42dd6e4 (patch) | |
tree | 34aec1b04dc06da48f77d04a2becdddb412d0aba | |
parent | 469aa61b1d0b306d1ddbcacfa76c4bb0f292d200 (diff) | |
download | aur-ece576f82876545fc2904e4e606d40abe42dd6e4.tar.gz |
Add 0006-BFQ-bugfix-for-v8r12.patch
-rw-r--r-- | .SRCINFO | 4 | ||||
-rw-r--r-- | 0006-BFQ-bugfix-for-v8r12.patch | 443 | ||||
-rw-r--r-- | PKGBUILD | 10 |
3 files changed, 452 insertions, 5 deletions
@@ -1,6 +1,6 @@ pkgbase = linux-bfq pkgver = 4.11.12 - pkgrel = 1 + pkgrel = 2 url = http://algo.ing.unimo.it arch = i686 arch = x86_64 @@ -23,6 +23,7 @@ pkgbase = linux-bfq source = 90-linux.hook source = linux.preset source = 0005-BFQ-update-to-v8r12.patch + source = 0006-BFQ-bugfix-for-v8r12.patch validpgpkeys = ABAF11C65A2970B130ABE3C479BE3E4300411886 validpgpkeys = 647F28654894E3BD457199BE38DBBDC86092693E sha512sums = 6610eed97ffb7207c71771198c36179b8244ace7222bebb109507720e26c5f17d918079a56d5febdd8605844d67fb2df0ebe910fa2f2f53690daf6e2a8ad09c3 @@ -39,6 +40,7 @@ pkgbase = linux-bfq sha512sums = d6faa67f3ef40052152254ae43fee031365d0b1524aa0718b659eb75afc21a3f79ea8d62d66ea311a800109bed545bc8f79e8752319cd378eef2cbd3a09aba22 sha512sums = 2dc6b0ba8f7dbf19d2446c5c5f1823587de89f4e28e9595937dd51a87755099656f2acec50e3e2546ea633ad1bfd1c722e0c2b91eef1d609103d8abdc0a7cbaf sha512sums = b1f6306a27d7e25eb4ff3eb51cb1fe38b0ca035cff229537d1b9f68bdc25861f2fecdeeeb1582e34cd166ee4275e49e4c679247a4c36109b2dcd6d4fa9456d60 + sha512sums = c03c5a8dd81c40e01639d04bbb4d5347e844c76248965c020a76addc83b1e897f4b9a26c6b6125739175577c8d8829054ce7ce8400f8d71d6cd2c2f89fc6ac3b pkgname = linux-bfq pkgdesc = Linux Kernel and modules with the BFQ scheduler. diff --git a/0006-BFQ-bugfix-for-v8r12.patch b/0006-BFQ-bugfix-for-v8r12.patch new file mode 100644 index 000000000000..68e7c41bddf6 --- /dev/null +++ b/0006-BFQ-bugfix-for-v8r12.patch @@ -0,0 +1,443 @@ +From 518e5275d6057ee8b3b4eeebaaa779c5aca7a15c Mon Sep 17 00:00:00 2001 +From: Paolo Valente <paolo.valente@linaro.org> +Date: Thu, 20 Jul 2017 10:46:39 +0200 +Subject: [PATCH 1/3] Add extra checks related to entity scheduling + +- extra checks related to ioprioi-class changes +- specific check on st->idle in __bfq_requeue_entity + +Signed-off-by: Paolo Valente <paolo.valente@linaro.org> +--- + block/bfq-sched.c | 9 ++++++++- + 1 file changed, 8 insertions(+), 1 deletion(-) + +diff --git a/block/bfq-sched.c b/block/bfq-sched.c +index 90d2856358a1..b6eb25887262 100644 +--- a/block/bfq-sched.c ++++ b/block/bfq-sched.c +@@ -812,6 +812,7 @@ __bfq_entity_update_weight_prio(struct bfq_service_tree *old_st, + } + #endif + ++ BUG_ON(entity->tree && update_class_too); + BUG_ON(old_st->wsum < entity->weight); + old_st->wsum -= entity->weight; + +@@ -883,8 +884,10 @@ __bfq_entity_update_weight_prio(struct bfq_service_tree *old_st, + + new_st->wsum += entity->weight; + +- if (new_st != old_st) ++ if (new_st != old_st) { ++ BUG_ON(!update_class_too); + entity->start = new_st->vtime; ++ } + } + + return new_st; +@@ -993,6 +996,7 @@ static void bfq_update_fin_time_enqueue(struct bfq_entity *entity, + * tree, then it is safe to invoke next function with the last + * parameter set (see the comments on the function). + */ ++ BUG_ON(entity->tree); + st = __bfq_entity_update_weight_prio(st, entity, true); + bfq_calc_finish(entity, entity->budget); + +@@ -1113,9 +1117,11 @@ static void __bfq_activate_entity(struct bfq_entity *entity, + * check for that. + */ + bfq_idle_extract(st, entity); ++ BUG_ON(entity->tree); + entity->start = bfq_gt(min_vstart, entity->finish) ? + min_vstart : entity->finish; + } else { ++ BUG_ON(entity->tree); + /* + * The finish time of the entity may be invalid, and + * it is in the past for sure, otherwise the queue +@@ -1203,6 +1209,7 @@ static void __bfq_requeue_entity(struct bfq_entity *entity) + */ + bfq_calc_finish(entity, entity->service); + entity->start = entity->finish; ++ BUG_ON(entity->tree && entity->tree == &st->idle); + BUG_ON(entity->tree && entity->tree != &st->active); + /* + * In addition, if the entity had more than one child + +From 6af8852b69527087d11c81a4dcb49d24f297dbce Mon Sep 17 00:00:00 2001 +From: Paolo Valente <paolo.valente@linaro.org> +Date: Fri, 21 Jul 2017 12:08:57 +0200 +Subject: [PATCH 2/3] block, bfq: reset in_service_entity if it becomes idle + +BFQ implements hierarchical scheduling by representing each group of +queues with a generic parent entity. For each parent entity, BFQ +maintains an in_service_entity pointer: if one of the child entities +happens to be in service, in_service_entity points to it. The +resetting of these pointers happens only on queue expirations: when +the in-service queue is expired, i.e., stops to be the queue in +service, BFQ resets all in_service_entity pointers along the +parent-entity path from this queue to the root entity. + +Functions handling the scheduling of entities assume, naturally, that +in-service entities are active, i.e., have pending I/O requests (or, +as a special case, even if they have no pending requests, they are +expected to receive a new request very soon, with the scheduler idling +the storage device while waiting for such an event). Unfortunately, +the above resetting scheme of the in_service_entity pointers may cause +this assumption to be violated. For example, the in-service queue may +happen to remain without requests because of a request merge. In this +case the queue does become idle, and all related data structures are +updated accordingly. But in_service_entity still points to the queue +in the parent entity. This inconsistency may even propagate to +higher-level parent entities, if they happen to become idle as well, +as a consequence of the leaf queue becoming idle. For this queue and +parent entities, scheduling functions have an undefined behaviour, +and, as reported, may easily lead to kernel crashes or hangs. + +This commit addresses this issue by simply resetting the +in_service_entity field also when it is detected to point to an entity +becoming idle (regardless of why the entity becomes idle). + +Reported-by: Laurentiu Nicola <lnicola@dend.ro> +Signed-off-by: Paolo Valente <paolo.valente@linaro.org> +Tested-by: Laurentiu Nicola <lnicola@dend.ro> +--- + block/bfq-sched.c | 4 +++- + 1 file changed, 3 insertions(+), 1 deletion(-) + +diff --git a/block/bfq-sched.c b/block/bfq-sched.c +index b6eb25887262..fdf1c713d050 100644 +--- a/block/bfq-sched.c ++++ b/block/bfq-sched.c +@@ -1336,8 +1336,10 @@ static bool __bfq_deactivate_entity(struct bfq_entity *entity, + + BUG_ON(is_in_service && entity->tree && entity->tree != &st->active); + +- if (is_in_service) ++ if (is_in_service) { + bfq_calc_finish(entity, entity->service); ++ sd->in_service_entity = NULL; ++ } + + if (entity->tree == &st->active) + bfq_active_extract(st, entity); + +From 52ce0ffe68b5e3fefaed21cfb32f104202eddc25 Mon Sep 17 00:00:00 2001 +From: Paolo Valente <paolo.valente@linaro.org> +Date: Fri, 28 Jul 2017 21:09:51 +0200 +Subject: [PATCH 3/3] block, bfq: consider also in_service_entity to state + whether an entity is active + +Groups of BFQ queues are represented by generic entities in BFQ. When +a queue belonging to a parent entity is deactivated, the parent entity +may need to be deactivated too, in case the deactivated queue was the +only active queue for the parent entity. This deactivation may need to +be propagated upwards if the entity belongs, in its turn, to a further +higher-level entity, and so on. In particular, the upward propagation +of deactivation stops at the first parent entity that remains active +even if one of its child entities has been deactivated. + +To decide whether the last non-deactivation condition holds for a +parent entity, BFQ checks whether the field next_in_service is still +not NULL for the parent entity, after the deactivation of one of its +child entity. If it is not NULL, then there are certainly other active +entities in the parent entity, and deactivations can stop. + +Unfortunately, this check misses a corner case: if in_service_entity +is not NULL, then next_in_service may happen to be NULL, although the +parent entity is evidently active. This happens if: 1) the entity +pointed by in_service_entity is the only active entity in the parent +entity, and 2) according to the definition of next_in_service, the +in_service_entity cannot be considered as next_in_service. See the +comments on the definition of next_in_service for details on this +second point. + +Hitting the above corner case causes crashes. + +To address this issue, this commit: +1) Extends the above check on only next_in_service to controlling both +next_in_service and in_service_entity (if any of them is not NULL, +then no further deactivation is performed) +2) Improves the (important) comments on how next_in_service is defined +and updated; in particular it fixes a few rather obscure paragraphs + +Reported-by: Eric Wheeler <bfq-sched@lists.ewheeler.net> +Reported-by: Rick Yiu <rick_yiu@htc.com> +Reported-by: Tom X Nguyen <tom81094@gmail.com> +Signed-off-by: Paolo Valente <paolo.valente@linaro.org> +Tested-by: Eric Wheeler <bfq-sched@lists.ewheeler.net> +Tested-by: Rick Yiu <rick_yiu@htc.com> +Tested-by: Laurentiu Nicola <lnicola@dend.ro> +Tested-by: Tom X Nguyen <tom81094@gmail.com> +--- + block/bfq-sched.c | 140 ++++++++++++++++++++++++++++++------------------------ + block/bfq.h | 23 +++++++-- + 2 files changed, 95 insertions(+), 68 deletions(-) + +diff --git a/block/bfq-sched.c b/block/bfq-sched.c +index fdf1c713d050..be985d9d5f17 100644 +--- a/block/bfq-sched.c ++++ b/block/bfq-sched.c +@@ -196,21 +196,23 @@ static bool bfq_update_parent_budget(struct bfq_entity *next_in_service) + + /* + * This function tells whether entity stops being a candidate for next +- * service, according to the following logic. ++ * service, according to the restrictive definition of the field ++ * next_in_service. In particular, this function is invoked for an ++ * entity that is about to be set in service. + * +- * This function is invoked for an entity that is about to be set in +- * service. If such an entity is a queue, then the entity is no longer +- * a candidate for next service (i.e, a candidate entity to serve +- * after the in-service entity is expired). The function then returns +- * true. ++ * If entity is a queue, then the entity is no longer a candidate for ++ * next service according to the that definition, because entity is ++ * about to become the in-service queue. This function then returns ++ * true if entity is a queue. + * +- * In contrast, the entity could stil be a candidate for next service +- * if it is not a queue, and has more than one child. In fact, even if +- * one of its children is about to be set in service, other children +- * may still be the next to serve. As a consequence, a non-queue +- * entity is not a candidate for next-service only if it has only one +- * child. And only if this condition holds, then the function returns +- * true for a non-queue entity. ++ * In contrast, entity could still be a candidate for next service if ++ * it is not a queue, and has more than one active child. In fact, ++ * even if one of its children is about to be set in service, other ++ * active children may still be the next to serve, for the parent ++ * entity, even according to the above definition. As a consequence, a ++ * non-queue entity is not a candidate for next-service only if it has ++ * only one active child. And only if this condition holds, then this ++ * function returns true for a non-queue entity. + */ + static bool bfq_no_longer_next_in_service(struct bfq_entity *entity) + { +@@ -223,6 +225,18 @@ static bool bfq_no_longer_next_in_service(struct bfq_entity *entity) + + BUG_ON(bfqg == ((struct bfq_data *)(bfqg->bfqd))->root_group); + BUG_ON(bfqg->active_entities == 0); ++ /* ++ * The field active_entities does not always contain the ++ * actual number of active children entities: it happens to ++ * not account for the in-service entity in case the latter is ++ * removed from its active tree (which may get done after ++ * invoking the function bfq_no_longer_next_in_service in ++ * bfq_get_next_queue). Fortunately, here, i.e., while ++ * bfq_no_longer_next_in_service is not yet completed in ++ * bfq_get_next_queue, bfq_active_extract has not yet been ++ * invoked, and thus active_entities still coincides with the ++ * actual number of active entities. ++ */ + if (bfqg->active_entities == 1) + return true; + +@@ -1089,7 +1103,7 @@ static void bfq_update_fin_time_enqueue(struct bfq_entity *entity, + * one of its children receives a new request. + * + * Basically, this function updates the timestamps of entity and +- * inserts entity into its active tree, ater possible extracting it ++ * inserts entity into its active tree, ater possibly extracting it + * from its idle tree. + */ + static void __bfq_activate_entity(struct bfq_entity *entity, +@@ -1213,7 +1227,7 @@ static void __bfq_requeue_entity(struct bfq_entity *entity) + BUG_ON(entity->tree && entity->tree != &st->active); + /* + * In addition, if the entity had more than one child +- * when set in service, then was not extracted from ++ * when set in service, then it was not extracted from + * the active tree. This implies that the position of + * the entity in the active tree may need to be + * changed now, because we have just updated the start +@@ -1221,9 +1235,8 @@ static void __bfq_requeue_entity(struct bfq_entity *entity) + * time in a moment (the requeueing is then, more + * precisely, a repositioning in this case). To + * implement this repositioning, we: 1) dequeue the +- * entity here, 2) update the finish time and +- * requeue the entity according to the new +- * timestamps below. ++ * entity here, 2) update the finish time and requeue ++ * the entity according to the new timestamps below. + */ + if (entity->tree) + bfq_active_extract(st, entity); +@@ -1270,9 +1283,9 @@ static void __bfq_activate_requeue_entity(struct bfq_entity *entity, + + + /** +- * bfq_activate_entity - activate or requeue an entity representing a bfq_queue, +- * and activate, requeue or reposition all ancestors +- * for which such an update becomes necessary. ++ * bfq_activate_requeue_entity - activate or requeue an entity representing a bfq_queue, ++ * and activate, requeue or reposition all ancestors ++ * for which such an update becomes necessary. + * @entity: the entity to activate. + * @non_blocking_wait_rq: true if this entity was waiting for a request + * @requeue: true if this is a requeue, which implies that bfqq is +@@ -1308,9 +1321,9 @@ static void bfq_activate_requeue_entity(struct bfq_entity *entity, + * @ins_into_idle_tree: if false, the entity will not be put into the + * idle tree. + * +- * Deactivates an entity, independently from its previous state. Must ++ * Deactivates an entity, independently of its previous state. Must + * be invoked only if entity is on a service tree. Extracts the entity +- * from that tree, and if necessary and allowed, puts it on the idle ++ * from that tree, and if necessary and allowed, puts it into the idle + * tree. + */ + static bool __bfq_deactivate_entity(struct bfq_entity *entity, +@@ -1359,7 +1372,7 @@ static bool __bfq_deactivate_entity(struct bfq_entity *entity, + /** + * 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 on the idle tree ++ * @ins_into_idle_tree: true if the entity can be put into the idle tree + */ + static void bfq_deactivate_entity(struct bfq_entity *entity, + bool ins_into_idle_tree, +@@ -1406,16 +1419,29 @@ static void bfq_deactivate_entity(struct bfq_entity *entity, + */ + bfq_update_next_in_service(sd, NULL); + +- if (sd->next_in_service) { ++ if (sd->next_in_service || sd->in_service_entity) { + /* +- * The parent entity is still backlogged, +- * because next_in_service is not NULL. So, no +- * further upwards deactivation must be +- * performed. Yet, next_in_service has +- * changed. Then the schedule does need to be +- * updated upwards. ++ * The parent entity is still active, because ++ * either next_in_service or in_service_entity ++ * is not NULL. So, no further upwards ++ * deactivation must be performed. Yet, ++ * next_in_service has changed. Then the ++ * schedule does need to be updated upwards. ++ * ++ * NOTE If in_service_entity is not NULL, then ++ * next_in_service may happen to be NULL, ++ * although the parent entity is evidently ++ * active. This happens if 1) the entity ++ * pointed by in_service_entity is the only ++ * active entity in the parent entity, and 2) ++ * according to the definition of ++ * next_in_service, the in_service_entity ++ * cannot be considered as ++ * next_in_service. See the comments on the ++ * definition of next_in_service for details. + */ + BUG_ON(sd->next_in_service == entity); ++ BUG_ON(sd->in_service_entity == entity); + break; + } + +@@ -1806,45 +1832,33 @@ static struct bfq_queue *bfq_get_next_queue(struct bfq_data *bfqd) + + /* + * If entity is no longer a candidate for next +- * service, then we extract it from its active tree, +- * for the following reason. To further boost the +- * throughput in some special case, BFQ needs to know +- * which is the next candidate entity to serve, while +- * there is already an entity in service. In this +- * respect, to make it easy to compute/update the next +- * candidate entity to serve after the current +- * candidate has been set in service, there is a case +- * where it is necessary to extract the current +- * candidate from its service tree. Such a case is +- * when the entity just set in service cannot be also +- * a candidate for next service. Details about when +- * this conditions holds are reported in the comments +- * on the function bfq_no_longer_next_in_service() +- * invoked below. ++ * service, then it must be extracted from its active ++ * tree, so as to make sure that it won't be ++ * considered when computing next_in_service. See the ++ * comments on the function ++ * bfq_no_longer_next_in_service() for details. + */ + if (bfq_no_longer_next_in_service(entity)) + bfq_active_extract(bfq_entity_service_tree(entity), + entity); + + /* +- * For the same reason why we may have just extracted +- * entity from its active tree, we may need to update +- * next_in_service for the sched_data of entity too, +- * regardless of whether entity has been extracted. +- * In fact, even if entity has not been extracted, a +- * descendant entity may get extracted. Such an event +- * would cause a change in next_in_service for the +- * level of the descendant entity, and thus possibly +- * back to upper levels. ++ * Even if entity is not to be extracted according to ++ * the above check, a descendant entity may get ++ * extracted in one of the next iterations of this ++ * loop. Such an event could cause a change in ++ * next_in_service for the level of the descendant ++ * entity, and thus possibly back to this level. + * +- * We cannot perform the resulting needed update +- * before the end of this loop, because, to know which +- * is the correct next-to-serve candidate entity for +- * each level, we need first to find the leaf entity +- * to set in service. In fact, only after we know +- * which is the next-to-serve leaf entity, we can +- * discover whether the parent entity of the leaf +- * entity becomes the next-to-serve, and so on. ++ * However, we cannot perform the resulting needed ++ * update of next_in_service for this level before the ++ * end of the whole loop, because, to know which is ++ * the correct next-to-serve candidate entity for each ++ * level, we need first to find the leaf entity to set ++ * in service. In fact, only after we know which is ++ * the next-to-serve leaf entity, we can discover ++ * whether the parent entity of the leaf entity ++ * becomes the next-to-serve, and so on. + */ + + /* Log some information */ +diff --git a/block/bfq.h b/block/bfq.h +index 77dc72c35fbf..ffa833863d88 100644 +--- a/block/bfq.h ++++ b/block/bfq.h +@@ -68,17 +68,30 @@ struct bfq_service_tree { + * + * bfq_sched_data is the basic scheduler queue. It supports three + * ioprio_classes, and can be used either as a toplevel queue or as an +- * intermediate queue on a hierarchical setup. @next_in_service +- * points to the active entity of the sched_data service trees that +- * will be scheduled next. It is used to reduce the number of steps +- * needed for each hierarchical-schedule update. ++ * intermediate queue in a hierarchical setup. + * + * The supported ioprio_classes are the same as in CFQ, in descending + * priority order, IOPRIO_CLASS_RT, IOPRIO_CLASS_BE, IOPRIO_CLASS_IDLE. + * Requests from higher priority queues are served before all the + * requests from lower priority queues; among requests of the same + * queue requests are served according to B-WF2Q+. +- * All the fields are protected by the queue lock of the containing bfqd. ++ * ++ * The schedule is implemented by the service trees, plus the field ++ * @next_in_service, which points to the entity on the active trees ++ * that will be served next, if 1) no changes in the schedule occurs ++ * before the current in-service entity is expired, 2) the in-service ++ * queue becomes idle when it expires, and 3) if the entity pointed by ++ * in_service_entity is not a queue, then the in-service child entity ++ * of the entity pointed by in_service_entity becomes idle on ++ * expiration. This peculiar definition allows for the following ++ * optimization, not yet exploited: while a given entity is still in ++ * service, we already know which is the best candidate for next ++ * service among the other active entitities in the same parent ++ * entity. We can then quickly compare the timestamps of the ++ * in-service entity with those of such best candidate. ++ * ++ * All the fields are protected by the queue lock of the containing ++ * bfqd. + */ + struct bfq_sched_data { + struct bfq_entity *in_service_entity; /* entity in service */ @@ -52,7 +52,7 @@ pkgbase=linux-bfq # pkgname=('linux-bfq' 'linux-bfq-headers' 'linux-bfq-docs') _srcname=linux-4.11 pkgver=4.11.12 -pkgrel=1 +pkgrel=2 arch=('i686' 'x86_64') url="http://algo.ing.unimo.it" license=('GPL2') @@ -80,7 +80,8 @@ source=("http://www.kernel.org/pub/linux/kernel/v4.x/${_srcname}.tar.xz" # standard config files for mkinitcpio ramdisk 'linux.preset' # patches from https://github.com/linusw/linux-bfq/commits/bfq-v8 - '0005-BFQ-update-to-v8r12.patch') + '0005-BFQ-update-to-v8r12.patch' + '0006-BFQ-bugfix-for-v8r12.patch') _kernelname=${pkgbase#linux} @@ -93,7 +94,7 @@ prepare() { ### Patch source with BFQ msg "Patching source with BFQ patches" - for p in "${srcdir}"/000{1,2,3,4,5}-*BFQ*.patch; do + for p in "${srcdir}"/000{1,2,3,4,5,6}-*BFQ*.patch; do msg " $p" patch -Np1 -i "$p" done @@ -436,7 +437,8 @@ sha512sums=('6610eed97ffb7207c71771198c36179b8244ace7222bebb109507720e26c5f17d91 '57addf780fc68d8e2914514e47d2edd27600cc0d1bf0c7d3786bc3e16ec9c6527eb8e9d95f156da8b77c11a53ac2a8f0d23360547a26350ebc3dca93721ebc42' 'd6faa67f3ef40052152254ae43fee031365d0b1524aa0718b659eb75afc21a3f79ea8d62d66ea311a800109bed545bc8f79e8752319cd378eef2cbd3a09aba22' '2dc6b0ba8f7dbf19d2446c5c5f1823587de89f4e28e9595937dd51a87755099656f2acec50e3e2546ea633ad1bfd1c722e0c2b91eef1d609103d8abdc0a7cbaf' - 'b1f6306a27d7e25eb4ff3eb51cb1fe38b0ca035cff229537d1b9f68bdc25861f2fecdeeeb1582e34cd166ee4275e49e4c679247a4c36109b2dcd6d4fa9456d60') + 'b1f6306a27d7e25eb4ff3eb51cb1fe38b0ca035cff229537d1b9f68bdc25861f2fecdeeeb1582e34cd166ee4275e49e4c679247a4c36109b2dcd6d4fa9456d60' + 'c03c5a8dd81c40e01639d04bbb4d5347e844c76248965c020a76addc83b1e897f4b9a26c6b6125739175577c8d8829054ce7ce8400f8d71d6cd2c2f89fc6ac3b') validpgpkeys=( 'ABAF11C65A2970B130ABE3C479BE3E4300411886' # Linus Torvalds |