Bump to BFQ v8r6

5 files changed, 969 insertions, 89 deletions

diff --git a/.SRCINFO b/.SRCINFO
index 5f0ed1830f9c..d346d7b123b5 100644
--- a/.SRCINFO
+++ b/.SRCINFO
@@ -1,6 +1,6 @@
 pkgbase = linux-bfq
 	pkgver = 4.8.15
-	pkgrel = 2
+	pkgrel = 3
 	url = http://algo.ing.unimo.it
 	arch = i686
 	arch = x86_64
@@ -36,15 +36,15 @@ pkgbase = linux-bfq
 	sha512sums = dc0649dfe2a5ce8e8879a62df29a4a1959eb1a84e5d896a9cb119d6a85a9bad1b17135371799e0be96532e17c66043d298e4a14b18fad3078a1f425108f888c9
 	sha512sums = 135afcffee2439e2260a71202658dce9ec5f555de3291b2d49a5cffdd953c6d7851b8a90e961576895555142a618e52220a7e4a46521ca4ba19d37df71887581
 	sha512sums = 87ae76889ab84ced46c237374c124786551982f8ff7325102af9153aed1ab7be72bec4db1f7516426c5ee34c5ce17221679eb2f129c5cbdeec05c0d3cb7f785d
-	sha512sums = 6046432243b8f0497b43ea2c5fe3fde5135e058f2be25c02773ead93e2ab3b525b6f7c1c4898b9e67ac2bec0959b972829e997e79fabf6ac87e006700dfaf987
+	sha512sums = ba9af1f177159ae1e6eba7375850a20e5d260e19c340f9bc540e6c91dc64e6a2841d261532b21e29a60bdb74123baa01a823837a699a5e74930b5062d590d5eb
 	sha512sums = d9d28e02e964704ea96645a5107f8b65cae5f4fb4f537e224e5e3d087fd296cb770c29ac76e0ce95d173bc420ea87fb8f187d616672a60a0cae618b0ef15b8c8
-	sha512sums = dc9ad074791a9edb3414a71480525a1c4a75b257137c754749c251e45ef376e313d3310766fedcabcd392837a8022bbcd97bfcd17c42feae63f71b4c4064b73d
-	sha512sums = bcc657cd2366b55ba303d4d091ab9958e4f97121e7fdd64013a90be7fb6b19ac28ca2e8973496935475b9a8f8386bcbed8924981a20bb51cf3fc5c6f4f14b22a
+	sha512sums = 6dc35242059c8ce3cc9878ce661511b46266a63182afc37deb53bc2ba6b8e7fe5be3d7da08d1a2abcb9a1cd16e896a49ef9e360e8e2bee53c8d7b7004bc8f655
+	sha512sums = aebf2940074ec3b9f4b6177489ec37400b962f714b4732ff3386e3532934520d507aff3effb1d38ec4b113508ce7c7ba4214b8b448854ddf857435a35cff3db7
 	sha512sums = d6faa67f3ef40052152254ae43fee031365d0b1524aa0718b659eb75afc21a3f79ea8d62d66ea311a800109bed545bc8f79e8752319cd378eef2cbd3a09aba22
 	sha512sums = 2dc6b0ba8f7dbf19d2446c5c5f1823587de89f4e28e9595937dd51a87755099656f2acec50e3e2546ea633ad1bfd1c722e0c2b91eef1d609103d8abdc0a7cbaf
 	sha512sums = c53bd47527adbd2599a583e05a7d24f930dc4e86b1de017486588205ad6f262a51a4551593bc7a1218c96541ea073ea03b770278d947b1cd0d2801311fcc80e5
 	sha512sums = 002d5e0ccfa5824c1750912a6400ff722672d6587b74ba66b1127cf1228048f604bba107617cf4f4477884039af4d4d196cf1b74cefe43b0bddc82270f11940d
-	sha512sums = 98612f37013d1b41c76887bc5ed80f70753f6fc859748038dc83f3b53aa89464321951c6c21b364f56b2d4860e594c2091240c70ff70ce616d6b3fdadb817934
+	sha512sums = 6c9992e1ae39e81577af9399d583c8c04c2d8ff205eb58ed082016e310ed2b2f040689ae8f2a36bf131d3c58d40eaf94ba2bd4b9fc0006eeedb9569f8c0deef5
 
 pkgname = linux-bfq
 	pkgdesc = Linux Kernel and modules with the BFQ scheduler.
diff --git a/0005-BFQ-update-to-v8r6.patch b/0005-BFQ-update-to-v8r6.patch
index 1b42af900abe..69e33cb2fcc2 100644
--- a/0005-BFQ-update-to-v8r6.patch
+++ b/0005-BFQ-update-to-v8r6.patch
@@ -1,7 +1,7 @@
 From 1acff6b391cd626a495e42c9782bf2139b9f330f Mon Sep 17 00:00:00 2001
 From: Paolo Valente <paolo.valente@linaro.org>
 Date: Wed, 19 Oct 2016 20:11:42 +0200
-Subject: [PATCH 01/24] Documentation/block: add bfq-iosched.txt
+Subject: [PATCH 01/28] Documentation/block: add bfq-iosched.txt
 
 Documentation of BFQ benefits, inner workings, interface and tunables.
 
@@ -542,7 +542,7 @@ index 0000000..67e1269
 From 11f0d8caa035ff4fe6fe02ebc0f2f14dc5473479 Mon Sep 17 00:00:00 2001
 From: Paolo Valente <paolo.valente@linaro.org>
 Date: Sat, 22 Oct 2016 15:26:33 +0200
-Subject: [PATCH 02/24] BUGFIX: Replace max wrongly used for modulo numbers
+Subject: [PATCH 02/28] BUGFIX: Replace max wrongly used for modulo numbers
 
 Signed-off-by: Paolo Valente <paolo.valente@linaro.org>
 ---
@@ -574,7 +574,7 @@ index eef6ff4..c161ff0 100644
 From eb59d4ac664f64372c440006b0cd27bf137a2025 Mon Sep 17 00:00:00 2001
 From: Paolo Valente <paolo.valente@linaro.org>
 Date: Mon, 24 Oct 2016 17:08:32 +0200
-Subject: [PATCH 03/24] Improve bfq-iosched.txt
+Subject: [PATCH 03/28] Improve bfq-iosched.txt
 
 Signed-off-by: Paolo Valente <paolo.valente@linaro.org>
 ---
@@ -610,7 +610,7 @@ index 67e1269..8626b14 100644
 From a53d556f54f33de6e71f909748c6994ff90fa243 Mon Sep 17 00:00:00 2001
 From: Paolo Valente <paolo.valente@linaro.org>
 Date: Mon, 24 Oct 2016 20:36:53 +0200
-Subject: [PATCH 04/24] Improve help message in Kconfig.iosched
+Subject: [PATCH 04/28] Improve help message in Kconfig.iosched
 
 Signed-off-by: Paolo Valente <paolo.valente@linaro.org>
 ---
@@ -643,7 +643,7 @@ index 6d92579..277b112 100644
 From 710824a320c015b314abba3bc2982d0f3caa0acc Mon Sep 17 00:00:00 2001
 From: Paolo Valente <paolo.valente@linaro.org>
 Date: Mon, 24 Oct 2016 20:37:59 +0200
-Subject: [PATCH 05/24] Remove stray disk word in first line
+Subject: [PATCH 05/28] Remove stray disk word in first line
 
 SIgned-off-by: Paolo Valente <paolo.valente@linaro.org>
 ---
@@ -665,7 +665,7 @@ index c161ff0..b5fdd45 100644
 From a2f6ff7877e60f533cdf39e941fc45f7b5aafcee Mon Sep 17 00:00:00 2001
 From: Paolo Valente <paolo.valente@linaro.org>
 Date: Mon, 24 Oct 2016 20:41:03 +0200
-Subject: [PATCH 06/24] BUGFIX: Remove wrong conversion in use of
+Subject: [PATCH 06/28] BUGFIX: Remove wrong conversion in use of
  bfq_fifo_expire
 
 Signed-off-by: Paolo Valente <paolo.valente@linaro.org>
@@ -691,7 +691,7 @@ index b5fdd45..a8c6887 100644
 From c91736449d06052469c2c3abaf5d455b85e77417 Mon Sep 17 00:00:00 2001
 From: Paolo Valente <paolo.valente@linaro.org>
 Date: Tue, 25 Oct 2016 09:31:37 +0200
-Subject: [PATCH 07/24] bfq-iosched.txt: add description of preemption
+Subject: [PATCH 07/28] bfq-iosched.txt: add description of preemption
 
 Signed-off-by: Paolo Valente <paolo.valente@linaro.org>
 ---
@@ -719,7 +719,7 @@ index 8626b14..8979408 100644
 From 2dc9393e7ff65d0e5340118402134cff03276b1c Mon Sep 17 00:00:00 2001
 From: Paolo Valente <paolo.valente@linaro.org>
 Date: Sat, 5 Nov 2016 18:09:07 +0100
-Subject: [PATCH 08/24] Add parentheses to complex macros
+Subject: [PATCH 08/28] Add parentheses to complex macros
 
 Signed-off-by: Paolo Valente <paolo.valente@linaro.org>
 ---
@@ -775,7 +775,7 @@ index a8c6887..88be34e 100644
 From 882f0607d82efe44d98634ce1fdcc4b602ccf5ec Mon Sep 17 00:00:00 2001
 From: Paolo Valente <paolo.valente@linaro.org>
 Date: Sat, 5 Nov 2016 18:32:20 +0100
-Subject: [PATCH 09/24] Fix type in bfq-iosched.txt
+Subject: [PATCH 09/28] Fix type in bfq-iosched.txt
 
 Sigend-off-by: Paolo Valente <paolo.valente@linaro.org>
 ---
@@ -799,7 +799,7 @@ index 8979408..5ba67af 100644
 From 99b1da54ca162abdc9e62915050154b35bd9bc27 Mon Sep 17 00:00:00 2001
 From: Paolo Valente <paolo.valente@linaro.org>
 Date: Sat, 5 Nov 2016 18:34:58 +0100
-Subject: [PATCH 10/24] BFQ-v8r5
+Subject: [PATCH 10/28] BFQ-v8r5
 
 Signed-off-by: Paolo Valente <paolo.valente@linaro.org>
 ---
@@ -835,7 +835,7 @@ index ea1e7d8..b80abe0 100644
 From d825ef204aa934e1fd9ebd925276ca0e67783508 Mon Sep 17 00:00:00 2001
 From: Paolo Valente <paolo.valente@linaro.org>
 Date: Wed, 7 Dec 2016 19:31:37 +0100
-Subject: [PATCH 11/24] Improve documentation
+Subject: [PATCH 11/28] Improve documentation
 
 Signed-off-by: Paolo Valente <paolo.valente@linaro.org>
 
@@ -929,7 +929,7 @@ index 277b112..f2cd945 100644
 From 880441682487350cd5b116c2cea830351f9c9478 Mon Sep 17 00:00:00 2001
 From: Paolo Valente <paolo.valente@linaro.org>
 Date: Wed, 7 Dec 2016 19:43:58 +0100
-Subject: [PATCH 12/24] Add and improve pointers in initial comments
+Subject: [PATCH 12/28] Add and improve pointers in initial comments
 
 ---
  block/bfq-iosched.c | 14 ++++++++++----
@@ -971,7 +971,7 @@ index 0f3081d..b07d251 100644
 From 60dad3833c9afa52315508579cbb4bac7e55d3a3 Mon Sep 17 00:00:00 2001
 From: Paolo Valente <paolo.valente@linaro.org>
 Date: Fri, 9 Dec 2016 07:05:29 +0100
-Subject: [PATCH 13/24] Fix typo in comments on bfq_lookup_next_entity
+Subject: [PATCH 13/28] Fix typo in comments on bfq_lookup_next_entity
 
 Signed-off-by: Paolo Valente <paolo.valente@linaro.org>
 ---
@@ -995,7 +995,7 @@ index 45d63d3..9afeaab 100644
 From 15f446f3bc189df88c64366930b5e237c8d9d5d5 Mon Sep 17 00:00:00 2001
 From: Paolo Valente <paolo.valente@linaro.org>
 Date: Fri, 9 Dec 2016 09:46:41 +0100
-Subject: [PATCH 14/24] Fix false-positive warning for uninitialized var
+Subject: [PATCH 14/28] Fix false-positive warning for uninitialized var
 
 Signed-off-by: Paolo Valente <paolo.valente@linaro.org>
 ---
@@ -1019,7 +1019,7 @@ index b07d251..3043e5e 100644
 From 1430feb8c7194f72be0a8066ad6b996d78bf3e09 Mon Sep 17 00:00:00 2001
 From: Paolo Valente <paolo.valente@linaro.org>
 Date: Sun, 11 Dec 2016 11:46:13 +0100
-Subject: [PATCH 15/24] Improve and fix some bugs in hierarchical code
+Subject: [PATCH 15/28] Improve and fix some bugs in hierarchical code
 
 This commit provides the following contributions.
 
@@ -1877,7 +1877,7 @@ index b80abe0..6b28030 100644
 From b5734696e18577dda6ef6571af7cb3718937d2f5 Mon Sep 17 00:00:00 2001
 From: Paolo Valente <paolo.valente@linaro.org>
 Date: Wed, 14 Dec 2016 17:56:25 +0100
-Subject: [PATCH 16/24] BFQ v8r6-rc1
+Subject: [PATCH 16/28] BFQ v8r6-rc1
 
 Signed-off-by: Paolo Valente <paolo.valente@linaro.org>
 ---
@@ -1913,7 +1913,7 @@ index 6b28030..d4d784f 100644
 From a7c98629904dcc103d676c2b8e2ceaff4ca19ca2 Mon Sep 17 00:00:00 2001
 From: Paolo Valente <paolo.valente@linaro.org>
 Date: Wed, 14 Dec 2016 18:07:41 +0100
-Subject: [PATCH 17/24] Port and improve CFQ commit 41647e7a
+Subject: [PATCH 17/28] Port and improve CFQ commit 41647e7a
 
 BFQ currently used the same logic for detecting seeky queues for
 for rotational disks and SSDs. This logic is appropriate for the
@@ -1958,7 +1958,7 @@ index 72443bd..153292f 100644
 From 5cacb798d523b9fa7e394ca3a369a0c196e0b022 Mon Sep 17 00:00:00 2001
 From: Paolo Valente <paolo.valente@linaro.org>
 Date: Thu, 15 Dec 2016 15:57:22 +0100
-Subject: [PATCH 18/24] Provide more details in switching-off-wr message
+Subject: [PATCH 18/28] Provide more details in switching-off-wr message
 
 Signed-off-by: Paolo Valente <paolo.valente@linaro.org>
 ---
@@ -1984,7 +1984,7 @@ index 153292f..a5853c7 100644
 From 6f62391c914a25818f839b932a9e1b16ee28c1f1 Mon Sep 17 00:00:00 2001
 From: Paolo Valente <paolo.valente@linaro.org>
 Date: Thu, 15 Dec 2016 16:10:17 +0100
-Subject: [PATCH 19/24] Remove useless parameter from bfq_del_bfqq_busy
+Subject: [PATCH 19/28] Remove useless parameter from bfq_del_bfqq_busy
 
 Signed-off-by: Paolo Valente <paolo.valente@linaro.org>
 ---
@@ -2050,7 +2050,7 @@ index 2f54ac5..fae28ee 100644
 From 1469db5fec95e3bfad0fe60dc1a843b0c5de4efa Mon Sep 17 00:00:00 2001
 From: Paolo Valente <paolo.valente@linaro.org>
 Date: Thu, 15 Dec 2016 16:40:09 +0100
-Subject: [PATCH 20/24] Further improve code and comments for hierarchical code
+Subject: [PATCH 20/28] Further improve code and comments for hierarchical code
 
 Signed-off-by: Paolo Valente <paolo.valente@linaro.org>
 ---
@@ -2210,7 +2210,7 @@ index fae28ee..52911cc 100644
 From d12d41bee45b988e1ae4f8dcece4bcecb5ad74a9 Mon Sep 17 00:00:00 2001
 From: Paolo Valente <paolo.valente@linaro.org>
 Date: Thu, 15 Dec 2016 22:11:39 +0100
-Subject: [PATCH 21/24] Optimize update of next_in_service entity
+Subject: [PATCH 21/28] Optimize update of next_in_service entity
 
 If the update of the next_in_service candidate entity is triggered by
 the activation of an entity, then it is not necessary to perform full
@@ -2511,7 +2511,7 @@ index d4d784f..9c68d8b 100644
 From 634414378918d47830a12f2c0e0a6c526d227502 Mon Sep 17 00:00:00 2001
 From: Paolo Valente <paolo.valente@linaro.org>
 Date: Thu, 15 Dec 2016 22:15:42 +0100
-Subject: [PATCH 22/24] Fix bug causing occasional loss of weight raising
+Subject: [PATCH 22/28] Fix bug causing occasional loss of weight raising
 
 When a bfq_queue, say bfqq, is split after a merging with another
 bfq_queue, BFQ checks whether it has to restore for bfqq the
@@ -2569,28 +2569,64 @@ index 9c68d8b..1a03521 100644
  
  enum bfq_device_speed {
 
-From cb826b5dbc9fcf524cd672857bcbcb68c6aa7236 Mon Sep 17 00:00:00 2001
+From a63703d1fcce41e4d0b36e366c333b56fdd04fe3 Mon Sep 17 00:00:00 2001
 From: Paolo Valente <paolo.valente@linaro.org>
 Date: Fri, 16 Dec 2016 17:57:00 +0100
-Subject: [PATCH 23/24] Fix wrong reset of in-service entities in commit
- 1430feb8
+Subject: [PATCH 23/28] Fix wrong reset of in-service entities
 
 In-service entities were reset with an indirect logic, which
 happened to be even buggy for some cases. This commit fixes
-this bug by replacing this indirect logic with a direct logic,
-in which all involved entities are immediately reset, with a
-bubble-up loop, when the in-service queue is reset.
+this bug in two important steps. First, by replacing this
+indirect logic with a direct logic, in which all involved
+entities are immediately reset, with a bubble-up loop, when
+the in-service queue is reset. Second, by restructuring the
+code related to this change, so as to become not only correct
+with respect to this change, but also cleaner and hopefully
+clearer.
 
 Signed-off-by: Paolo Valente <paolo.valente@linaro.org>
 ---
- block/bfq-iosched.c |  5 ++---
- block/bfq-sched.c   | 45 +++++++++++++++++++++++++++++----------------
- 2 files changed, 31 insertions(+), 19 deletions(-)
+ block/bfq-cgroup.c  |   2 +-
+ block/bfq-iosched.c |  20 ++-
+ block/bfq-sched.c   | 499 +++++++++++++++++++++++++++++++++-------------------
+ block/bfq.h         |   6 +-
+ 4 files changed, 332 insertions(+), 195 deletions(-)
 
+diff --git a/block/bfq-cgroup.c b/block/bfq-cgroup.c
+index bd31da5..bbaecd0 100644
+--- a/block/bfq-cgroup.c
++++ b/block/bfq-cgroup.c
+@@ -552,7 +552,7 @@ static void bfq_bfqq_move(struct bfq_data *bfqd, struct bfq_queue *bfqq,
+ 	BUG_ON(RB_EMPTY_ROOT(&bfqq->sort_list) && bfq_bfqq_busy(bfqq));
+ 
+ 	if (bfq_bfqq_busy(bfqq))
+-		bfq_deactivate_bfqq(bfqd, bfqq, false);
++		bfq_deactivate_bfqq(bfqd, bfqq, false, false);
+ 	else if (entity->on_st) {
+ 		BUG_ON(&bfq_entity_service_tree(entity)->idle !=
+ 		       entity->tree);
 diff --git a/block/bfq-iosched.c b/block/bfq-iosched.c
-index 7aa3d55..4d70d5e 100644
+index 7aa3d55..23e4c94 100644
 --- a/block/bfq-iosched.c
 +++ b/block/bfq-iosched.c
+@@ -600,7 +600,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_activate_bfqq(bfqd, bfqq);
++		bfq_requeue_bfqq(bfqd, bfqq);
+ 	}
+ }
+ 
+@@ -1526,7 +1526,7 @@ static void bfq_remove_request(struct request *rq)
+ 		BUG_ON(bfqq->entity.budget < 0);
+ 
+ 		if (bfq_bfqq_busy(bfqq) && bfqq != bfqd->in_service_queue) {
+-			bfq_del_bfqq_busy(bfqd, bfqq);
++			bfq_del_bfqq_busy(bfqd, bfqq, false);
+ 
+ 			/* bfqq emptied. In normal operation, when
+ 			 * bfqq is empty, bfqq->entity.service and
 @@ -2643,8 +2643,6 @@ static void __bfq_bfqq_expire(struct bfq_data *bfqd, struct bfq_queue *bfqq)
  {
  	BUG_ON(bfqq != bfqd->in_service_queue);
@@ -2600,16 +2636,31 @@ index 7aa3d55..4d70d5e 100644
  	/*
  	 * If this bfqq is shared between multiple processes, check
  	 * to make sure that those processes are still issuing I/Os
-@@ -2672,6 +2670,8 @@ static void __bfq_bfqq_expire(struct bfq_data *bfqd, struct bfq_queue *bfqq)
+@@ -2664,14 +2662,21 @@ static void __bfq_bfqq_expire(struct bfq_data *bfqd, struct bfq_queue *bfqq)
+ 			 */
+ 			bfqq->budget_timeout = jiffies;
+ 
+-		bfq_del_bfqq_busy(bfqd, bfqq);
++		bfq_del_bfqq_busy(bfqd, bfqq, true);
+ 	} else {
+-		bfq_activate_bfqq(bfqd, bfqq);
++		bfq_requeue_bfqq(bfqd, bfqq);
+ 		/*
+ 		 * Resort priority tree of potential close cooperators.
  		 */
  		bfq_pos_tree_add_move(bfqd, bfqq);
  	}
 +
++	/*
++	 * All in-service entities must have been properly deactivated
++	 * or requeued before executing the next function, which
++	 * resets all in-service entites as no more in service.
++	 */
 +	__bfq_bfqd_reset_in_service(bfqd);
  }
  
  /**
-@@ -3819,7 +3819,6 @@ static void bfq_put_queue(struct bfq_queue *bfqq)
+@@ -3819,7 +3824,6 @@ static void bfq_put_queue(struct bfq_queue *bfqq)
  	BUG_ON(bfqq->allocated[READ] + bfqq->allocated[WRITE] != 0);
  	BUG_ON(bfqq->entity.tree);
  	BUG_ON(bfq_bfqq_busy(bfqq));
@@ -2617,19 +2668,266 @@ index 7aa3d55..4d70d5e 100644
  
  	if (bfq_bfqq_sync(bfqq))
  		/*
+@@ -4740,7 +4744,7 @@ static void bfq_exit_queue(struct elevator_queue *e)
+ 
+ 	BUG_ON(bfqd->in_service_queue);
+ 	list_for_each_entry_safe(bfqq, n, &bfqd->idle_list, bfqq_list)
+-		bfq_deactivate_bfqq(bfqd, bfqq, false);
++		bfq_deactivate_bfqq(bfqd, bfqq, false, false);
+ 
+ 	spin_unlock_irq(q->queue_lock);
+ 
 diff --git a/block/bfq-sched.c b/block/bfq-sched.c
-index 09e494b..d9e63712 100644
+index 09e494b..3b8e05b 100644
 --- a/block/bfq-sched.c
 +++ b/block/bfq-sched.c
-@@ -923,22 +923,28 @@ static void __bfq_activate_entity(struct bfq_entity *entity,
- 	if (entity == sd->in_service_entity) {
- 		/*
- 		 * We are requeueing the current in-service entity,
+@@ -79,9 +79,9 @@ static struct bfq_entity *bfq_root_active_entity(struct rb_root *tree)
+  * 'true' activations, and other activations being requeueings (i.e.,
+  * implementing the second, requeueing phase of the mechanism used to
+  * reposition an entity in its active tree; see comments on
+- * __bfq_activate_entity for details). In both the last two activation
+- * sub-cases, new_entity points to the just activated or requeued
+- * entity.
++ * __bfq_activate_entity and __bfq_requeue_entity for details). In
++ * both the last two activation sub-cases, new_entity points to the
++ * just activated or requeued entity.
+  *
+  * This is a still incomplete version of this function, which always
+  * returns true. It will return also false in its complete version, in
+@@ -658,7 +658,7 @@ static void bfq_forget_entity(struct bfq_service_tree *st,
+ 
+ 	BUG_ON(!entity->on_st);
+ 
+-	entity->on_st = 0;
++	entity->on_st = false;
+ 	st->wsum -= entity->weight;
+ 	if (bfqq) {
+ 		sd = entity->sched_data;
+@@ -896,115 +896,12 @@ static void bfq_bfqq_charge_time(struct bfq_data *bfqd, struct bfq_queue *bfqq,
+ 			max_t(int, 0, tot_serv_to_charge - entity->service));
+ }
+ 
+-/**
+- * __bfq_activate_entity - handle activation or requeueing of an entity.
+- * @entity: the entity being activated or requeued.
+- * @non_blocking_wait_rq: true if entity was waiting for a request
+- *
+- * Called whenever an entity is activated, which happens either if the
+- * entity is not active and one of its children receives a new request
+- * (true activation), or if the entity needs to be repositioned in its
+- * active tree (requeueing, as explained in detail in the comments
+- * inside the function).
+- *
+- * Basically, this function updates the timestamps of entity and
+- * (re)inserts entity into its active tree.
+- */
+-static void __bfq_activate_entity(struct bfq_entity *entity,
+-				  bool non_blocking_wait_rq)
++static void bfq_update_fin_time_enqueue(struct bfq_entity *entity,
++					struct bfq_service_tree *st,
++					bool backshifted)
+ {
+-	struct bfq_sched_data *sd = entity->sched_data;
+-	struct bfq_service_tree *st = bfq_entity_service_tree(entity);
+ 	struct bfq_queue *bfqq = bfq_entity_to_bfqq(entity);
+-	bool backshifted = false;
+-
+-	BUG_ON(!sd);
+-	BUG_ON(!st);
+-	if (entity == sd->in_service_entity) {
+-		/*
+-		 * We are requeueing the current in-service entity,
 -		 * because of the requeueing of a just-expired
 -		 * non-idle leaf entity in the path originating from
 -		 * this entity. In fact, in this case, all entities in
 -		 * this path need to be requeued again for next
 -		 * service.
+-		 *
+-		 * Before requeueing, the start time of the entity
+-		 * must be moved forward to account for the service
+-		 * that the entity has received while in service. The
+-		 * finish time will then be updated according to this
+-		 * new value of the start time, and to the budget of
+-		 * the entity.
+-		 */
+-		bfq_calc_finish(entity, entity->service);
+-		entity->start = entity->finish;
+-		sd->in_service_entity = NULL;
+-		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
+-		 * 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
+-		 * time of the entity, and we will update its finish
+-		 * 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.
+-		 */
+-		if (entity->tree)
+-			bfq_active_extract(st, entity);
+-	} else if (entity->tree == &st->active) {
+-		/*
+-		 * The entity is already active, and not in
+-		 * service. In this case, this function gets called
+-		 * only if the next_in_service entity below this
+-		 * entity has changed, and this change has caused the
+-		 * budget of this entity to change, which, finally
+-		 * implies that the finish time of this entity must be
+-		 * updated. Such an update may cause the scheduling,
+-		 * i.e., the position in the active tree, of this
+-		 * entity to change. We handle this change by: 1)
+-		 * dequeueing the entity here, 2) updating the finish
+-		 * time and requeueing the entity according to the new
+-		 * timestamps below. This is the same approach as the
+-		 * non-extracted-entity sub-case above.
+-		 */
+-		bfq_active_extract(st, entity);
+-	} else { /* This is a 'true' activation, not a requeueing. */
+-		unsigned long long min_vstart;
+-
+-		/* See comments on bfq_fqq_update_budg_for_activation */
+-		if (non_blocking_wait_rq && bfq_gt(st->vtime, entity->finish)) {
+-			backshifted = true;
+-			min_vstart = entity->finish;
+-		} else
+-			min_vstart = st->vtime;
+-
+-		if (entity->tree == &st->idle) {
+-			/*
+-			 * Must be on the idle tree, bfq_idle_extract() will
+-			 * check for that.
+-			 */
+-			bfq_idle_extract(st, entity);
+-			entity->start = bfq_gt(min_vstart, entity->finish) ?
+-				min_vstart : entity->finish;
+-		} else {
+-			/*
+-			 * The finish time of the entity may be invalid, and
+-			 * it is in the past for sure, otherwise the queue
+-			 * would have been on the idle tree.
+-			 */
+-			entity->start = min_vstart;
+-			st->wsum += entity->weight;
+-			bfq_get_entity(entity);
+-
+-			BUG_ON(entity->on_st);
+-			entity->on_st = 1;
+-		}
+-	}
++	struct bfq_sched_data *sd = entity->sched_data;
+ 
+ 	st = __bfq_entity_update_weight_prio(st, entity);
+ 	bfq_calc_finish(entity, entity->budget);
+@@ -1087,37 +984,215 @@ static void __bfq_activate_entity(struct bfq_entity *entity,
+ 	BUG_ON(&st->active != &sd->service_tree->active &&
+ 	       &st->active != &(sd->service_tree+1)->active &&
+ 	       &st->active != &(sd->service_tree+2)->active);
++}
++
++/**
++ * __bfq_activate_entity - handle activation of entity.
++ * @entity: the entity being activated.
++ * @non_blocking_wait_rq: true if entity was waiting for a request
++ *
++ * Called for a 'true' activation, i.e., if entity is not active and
++ * 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
++ * from its idle tree.
++ */
++static void __bfq_activate_entity(struct bfq_entity *entity,
++				  bool non_blocking_wait_rq)
++{
++	struct bfq_sched_data *sd = entity->sched_data;
++	struct bfq_service_tree *st = bfq_entity_service_tree(entity);
++	struct bfq_queue *bfqq = bfq_entity_to_bfqq(entity);
++	bool backshifted = false;
++	unsigned long long min_vstart;
++
++	BUG_ON(!sd);
++	BUG_ON(!st);
++
++	/* See comments on bfq_fqq_update_budg_for_activation */
++	if (non_blocking_wait_rq && bfq_gt(st->vtime, entity->finish)) {
++		backshifted = true;
++		min_vstart = entity->finish;
++	} else
++		min_vstart = st->vtime;
++
++	if (entity->tree == &st->idle) {
++		/*
++		 * Must be on the idle tree, bfq_idle_extract() will
++		 * check for that.
++		 */
++		bfq_idle_extract(st, entity);
++		entity->start = bfq_gt(min_vstart, entity->finish) ?
++			min_vstart : entity->finish;
++	} else {
++		/*
++		 * The finish time of the entity may be invalid, and
++		 * it is in the past for sure, otherwise the queue
++		 * would have been on the idle tree.
++		 */
++		entity->start = min_vstart;
++		st->wsum += entity->weight;
++		bfq_get_entity(entity);
++
++		BUG_ON(entity->on_st && bfqq);
++
++#ifdef CONFIG_BFQ_GROUP_IOSCHED
++		if (entity->on_st && !bfqq) {
++			struct bfq_group *bfqg =
++				container_of(entity, struct bfq_group,
++					     entity);
++
++			bfq_log_bfqg((struct bfq_data *)bfqg->bfqd,
++				     bfqg,
++				     "activate bug, class %d in_service %p",
++				     bfq_class_idx(entity), sd->in_service_entity);
++		}
++#endif
++		BUG_ON(entity->on_st && !bfqq);
++		entity->on_st = true;
++	}
++
++	bfq_update_fin_time_enqueue(entity, st, backshifted);
++}
++
++/**
++ * __bfq_requeue_entity - handle requeueing or repositioning of an entity.
++ * @entity: the entity being requeued or repositioned.
++ *
++ * Requeueing is needed if this entity stops being served, which
++ * happens if a leaf descendant entity has expired. On the other hand,
++ * repositioning is needed if the next_inservice_entity for the child
++ * entity has changed. See the comments inside the function for
++ * details.
++ *
++ * Basically, this function: 1) removes entity from its active tree if
++ * present there, 2) updates the timestamps of entity and 3) inserts
++ * entity back into its active tree (in the new, right position for
++ * the new values of the timestamps).
++ */
++static void __bfq_requeue_entity(struct bfq_entity *entity)
++{
++	struct bfq_sched_data *sd = entity->sched_data;
++	struct bfq_service_tree *st = bfq_entity_service_tree(entity);
++
++	BUG_ON(!sd);
++	BUG_ON(!st);
++
++	BUG_ON(entity != sd->in_service_entity &&
++	       entity->tree != &st->active);
++
++	if (entity == sd->in_service_entity) {
++		/*
++		 * We are requeueing the current in-service entity,
 +		 * which may have to be done for one of the following
 +		 * reasons:
 +		 * - entity represents the in-service queue, and the
@@ -2641,35 +2939,159 @@ index 09e494b..d9e63712 100644
 +		 *   reason; the timestamps of the entity need then to
 +		 *   be updated, and the entity needs to be enqueued
 +		 *   or repositioned accordingly.
- 		 *
--		 * Before requeueing, the start time of the entity
--		 * must be moved forward to account for the service
--		 * that the entity has received while in service. The
++		 *
 +		 * In particular, before requeueing, the start time of
 +		 * the entity must be moved forward to account for the
 +		 * service that the entity has received while in
 +		 * service. This is done by the next instructions. The
- 		 * finish time will then be updated according to this
- 		 * new value of the start time, and to the budget of
- 		 * the entity.
- 		 */
- 		bfq_calc_finish(entity, entity->service);
- 		entity->start = entity->finish;
--		sd->in_service_entity = NULL;
- 		BUG_ON(entity->tree && entity->tree != &st->active);
- 		/*
- 		 * In addition, if the entity had more than one child
-@@ -1001,7 +1007,8 @@ static void __bfq_activate_entity(struct bfq_entity *entity,
- 			st->wsum += entity->weight;
- 			bfq_get_entity(entity);
++		 * finish time will then be updated according to this
++		 * new value of the start time, and to the budget of
++		 * the entity.
++		 */
++		bfq_calc_finish(entity, entity->service);
++		entity->start = entity->finish;
++		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
++		 * 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
++		 * time of the entity, and we will update its finish
++		 * 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.
++		 */
++		if (entity->tree)
++			bfq_active_extract(st, entity);
++	} else { /* The entity is already active, and not in service */
++		/*
++		 * In this case, this function gets called only if the
++		 * next_in_service entity below this entity has
++		 * changed, and this change has caused the budget of
++		 * this entity to change, which, finally implies that
++		 * the finish time of this entity must be
++		 * updated. Such an update may cause the scheduling,
++		 * i.e., the position in the active tree, of this
++		 * entity to change. We handle this change by: 1)
++		 * dequeueing the entity here, 2) updating the finish
++		 * time and requeueing the entity according to the new
++		 * timestamps below. This is the same approach as the
++		 * non-extracted-entity sub-case above.
++		 */
++		bfq_active_extract(st, entity);
++	}
  
--			BUG_ON(entity->on_st);
-+			BUG_ON(entity->on_st && bfqq);
-+			BUG_ON(entity->on_st && !bfqq);
- 			entity->on_st = 1;
++	bfq_update_fin_time_enqueue(entity, st, false);
+ }
+ 
++static void __bfq_activate_requeue_entity(struct bfq_entity *entity,
++					  struct bfq_sched_data *sd,
++					  bool non_blocking_wait_rq)
++{
++	struct bfq_service_tree *st = bfq_entity_service_tree(entity);
++
++	if (sd->in_service_entity == entity || entity->tree == &st->active)
++		 /*
++		  * in service or already queued on the active tree,
++		  * requeue or reposition
++		  */
++		__bfq_requeue_entity(entity);
++	else
++		/*
++		 * Not in service and not queued on its active tree:
++		 * the activity is idle and this is a true activation.
++		 */
++		__bfq_activate_entity(entity, non_blocking_wait_rq);
++}
++
++
+ /**
+- * bfq_activate_entity - activate an entity and its ancestors if necessary.
++ * 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.
+  * @entity: the entity to activate.
+  * @non_blocking_wait_rq: true if this entity was waiting for a request
+- *
+- * Activate @entity and all the entities on the path from it to the root.
++ * @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
+  */
+-static void bfq_activate_entity(struct bfq_entity *entity,
+-				bool non_blocking_wait_rq)
++static void bfq_activate_requeue_entity(struct bfq_entity *entity,
++					bool non_blocking_wait_rq,
++					bool requeue)
+ {
+ 	struct bfq_sched_data *sd;
+ 
+ 	for_each_entity(entity) {
+ 		BUG_ON(!entity);
+-		__bfq_activate_entity(entity, non_blocking_wait_rq);
+-
+ 		sd = entity->sched_data;
++		__bfq_activate_requeue_entity(entity, sd, non_blocking_wait_rq);
++
+ 		BUG_ON(RB_EMPTY_ROOT(&sd->service_tree->active) &&
+ 		       RB_EMPTY_ROOT(&(sd->service_tree+1)->active) &&
+ 		       RB_EMPTY_ROOT(&(sd->service_tree+2)->active));
+ 
+-		if (!bfq_update_next_in_service(sd, entity)) {
++		if (!bfq_update_next_in_service(sd, entity) && !requeue) {
+ 			BUG_ON(!sd->next_in_service);
+-			/*
+-			 * No need to propagate the activation to the
+-			 * upper entities, as they will be updated when
+-			 * the in-service entity is rescheduled.
+-			 */
+ 			break;
  		}
- 	}
-@@ -1153,10 +1160,8 @@ static bool __bfq_deactivate_entity(struct bfq_entity *entity, bool requeue)
+ 		BUG_ON(!sd->next_in_service);
+@@ -1127,36 +1202,30 @@ static void bfq_activate_entity(struct bfq_entity *entity,
+ /**
+  * __bfq_deactivate_entity - deactivate an entity from its service tree.
+  * @entity: the entity to deactivate.
+- * @requeue: if false, the entity will not be put into the idle tree.
+- *
+- * Deactivate an entity, independently from its previous state.  If the
+- * entity was not on a service tree just return, otherwise if it is on
+- * any scheduler tree, extract it from that tree, and if necessary
+- * and if the caller did not specify @requeue, put it on the idle tree.
++ * @ins_into_idle_tree: if false, the entity will not be put into the
++ *			idle tree.
+  *
+- * Return %true if the caller should update the entity hierarchy, i.e.,
+- * if the entity was in service or if it was the next_in_service for
+- * its sched_data; return %false otherwise.
++ * Deactivates an entity, independently from 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
++ * tree.
+  */
+-static bool __bfq_deactivate_entity(struct bfq_entity *entity, bool requeue)
++static bool __bfq_deactivate_entity(struct bfq_entity *entity,
++				    bool ins_into_idle_tree)
+ {
+ 	struct bfq_sched_data *sd = entity->sched_data;
+-	struct bfq_service_tree *st;
+-	int was_in_service;
+-	bool ret = false;
++	struct bfq_service_tree *st = bfq_entity_service_tree(entity);
++	bool was_in_service = entity == sd->in_service_entity;
+ 
+-	if (sd == NULL || !entity->on_st) /* never activated, or inactive */
++	if (!entity->on_st) { /* entity never activated, or already inactive */
++		BUG_ON(entity == entity->sched_data->in_service_entity);
+ 		return false;
+-
+-	st = bfq_entity_service_tree(entity);
+-	was_in_service = entity == sd->in_service_entity;
++	}
  
  	BUG_ON(was_in_service && entity->tree && entity->tree != &st->active);
  
@@ -2681,15 +3103,167 @@ index 09e494b..d9e63712 100644
  
  	if (entity->tree == &st->active)
  		bfq_active_extract(st, entity);
-@@ -1173,7 +1178,6 @@ static bool __bfq_deactivate_entity(struct bfq_entity *entity, bool requeue)
+@@ -1165,26 +1234,22 @@ static bool __bfq_deactivate_entity(struct bfq_entity *entity, bool requeue)
+ 	else if (entity->tree)
+ 		BUG();
+ 
+-	if (sd->next_in_service == entity)
+-		ret = bfq_update_next_in_service(sd, NULL);
+-
+-	if (!requeue || !bfq_gt(entity->finish, st->vtime))
++	if (!ins_into_idle_tree || !bfq_gt(entity->finish, st->vtime))
+ 		bfq_forget_entity(st, entity);
  	else
  		bfq_idle_insert(st, entity);
  
 -	BUG_ON(sd->in_service_entity == entity);
- 	BUG_ON(sd->next_in_service == entity);
+-	BUG_ON(sd->next_in_service == entity);
+-
+-	return ret;
++	return true;
+ }
+ 
+ /**
+- * bfq_deactivate_entity - deactivate an entity.
++ * bfq_deactivate_entity - deactivate an entity representing a bfq_queue.
+  * @entity: the entity to deactivate.
+- * @requeue: true if the entity can be put on the idle tree
++ * @ins_into_idle_tree: true if the entity can be put on the idle tree
+  */
+-static void bfq_deactivate_entity(struct bfq_entity *entity, int requeue)
++static void bfq_deactivate_entity(struct bfq_entity *entity,
++				  bool ins_into_idle_tree,
++				  bool expiration)
+ {
+ 	struct bfq_sched_data *sd;
+ 	struct bfq_entity *parent;
+@@ -1192,54 +1257,91 @@ static void bfq_deactivate_entity(struct bfq_entity *entity, int requeue)
+ 	for_each_entity_safe(entity, parent) {
+ 		sd = entity->sched_data;
+ 
+-		if (!__bfq_deactivate_entity(entity, requeue))
++		BUG_ON(sd == NULL); /*
++				     * It would mean that this is the
++				     * root group.
++				     */
++
++		BUG_ON(expiration && entity != sd->in_service_entity);
++
++		BUG_ON(entity != sd->in_service_entity &&
++		       entity->tree ==
++		       &bfq_entity_service_tree(entity)->active &&
++		       !sd->next_in_service);
++
++		if (!__bfq_deactivate_entity(entity, ins_into_idle_tree)) {
+ 			/*
+-			 * next_in_service has not been changed, so
+-			 * no upwards update is needed
++			 * Entity is not any tree any more, so, this
++			 * deactivation is a no-op, and there is
++			 * nothing to change for upper-level entities
++			 * (in case of expiration, this can never
++			 * happen).
+ 			 */
+-			break;
++			BUG_ON(expiration); /*
++					     * entity cannot be already out of
++					     * any tree
++					     */
++			return;
++		}
+ 
+-		if (sd->next_in_service)
++		if (sd->next_in_service == entity)
++			/*
++			 * entity was the next_in_service entity,
++			 * then, since entity has just been
++			 * deactivated, a new one must be found.
++			 */
++			bfq_update_next_in_service(sd, NULL);
++
++		if (sd->next_in_service) {
+ 			/*
+ 			 * The parent entity is still backlogged,
+ 			 * because next_in_service is not NULL. So, no
+-			 * upwards deactivation is needed.  Yet,
+-			 * next_in_service has been updated (see
+-			 * comment on the body of the above if).  Then
+-			 * the schedule nees to be updated upwards.
++			 * further upwards deactivation must be
++			 * performed.  Yet, next_in_service has
++			 * changed.  Then the schedule does need to be
++			 * updated upwards.
+ 			 */
+-			goto update_schedule;
++			BUG_ON(sd->next_in_service == entity);
++			break;
++		}
+ 
+ 		/*
+ 		 * If we get here, then the parent is no more
+ 		 * backlogged and we need to propagate the
+-		 * deactivation upwards. Then let the loop go on.
++		 * deactivation upwards. Thus let the loop go on.
+ 		 */
+ 
+ 		/*
+ 		 * Also let parent be queued into the idle tree on
+ 		 * deactivation, to preserve service guarantees, and
+ 		 * assuming that who invoked this function does not
+-		 * need parent entities too to be removed by any tree.
++		 * need parent entities too to be removed completely.
+ 		 */
+-		requeue = true;
++		ins_into_idle_tree = true;
+ 	}
+ 
+-	return;
+-
+-update_schedule:
++	/*
++	 * If the deactivation loop is fully executed, then there are
++	 * no more entities to touch and next loop is not executed at
++	 * all. Otherwise, requeue remaining entities if they are
++	 * about to stop receiving service, or reposition them if this
++	 * is not the case.
++	 */
+ 	entity = parent;
+ 	for_each_entity(entity) {
+ 		struct bfq_queue *bfqq = bfq_entity_to_bfqq(entity);
++
+ 		/*
+-		 * Invoke __bfq_activate_entity on entity, even if
+-		 * already active, to update its position in the
++		 * Invoke __bfq_requeue_entity on entity, even if
++		 * already active, to requeue/reposition it in the
+ 		 * active tree (because sd->next_in_service has
+ 		 * changed)
+ 		 */
+-		__bfq_activate_entity(entity, false);
++		__bfq_requeue_entity(entity);
  
- 	return ret;
-@@ -1700,6 +1704,8 @@ static struct bfq_queue *bfq_get_next_queue(struct bfq_data *bfqd)
+ 		sd = entity->sched_data;
++		BUG_ON(expiration && sd->in_service_entity != entity);
++
+ 		if (bfqq)
+ 			bfq_log_bfqq(bfqq->bfqd, bfqq,
+ 				     "invoking udpdate_next for this queue");
+@@ -1253,7 +1355,13 @@ static void bfq_deactivate_entity(struct bfq_entity *entity, int requeue)
+ 				     "invoking udpdate_next for this entity");
+ 		}
+ #endif
+-		if (!bfq_update_next_in_service(sd, entity))
++		if (!bfq_update_next_in_service(sd, entity) &&
++		    !expiration)
++			/*
++			 * next_in_service unchanged, and no
++			 * requeueing needed for expiration: stop
++			 * here.
++			 */
+ 			break;
+ 	}
+ }
+@@ -1700,6 +1808,8 @@ static struct bfq_queue *bfq_get_next_queue(struct bfq_data *bfqd)
  
  static void __bfq_bfqd_reset_in_service(struct bfq_data *bfqd)
  {
@@ -2698,23 +3272,30 @@ index 09e494b..d9e63712 100644
  	if (bfqd->in_service_bic) {
  		put_io_context(bfqd->in_service_bic->icq.ioc);
  		bfqd->in_service_bic = NULL;
-@@ -1708,6 +1714,10 @@ static void __bfq_bfqd_reset_in_service(struct bfq_data *bfqd)
+@@ -1708,36 +1818,59 @@ static void __bfq_bfqd_reset_in_service(struct bfq_data *bfqd)
  	bfq_clear_bfqq_wait_request(bfqd->in_service_queue);
  	hrtimer_try_to_cancel(&bfqd->idle_slice_timer);
  	bfqd->in_service_queue = NULL;
 +
-+	/* Reset in_service_entity along the path from entity to the root */
++	/*
++	 * When this function is called, all in-service entities have
++	 * been properly deactivated or requeued, so we can safely
++	 * execute the final step: reset in_service_entity along the
++	 * path from entity to the root.
++	 */
 +	for_each_entity(entity)
 +		entity->sched_data->in_service_entity = NULL;
  }
  
  static void bfq_deactivate_bfqq(struct bfq_data *bfqd, struct bfq_queue *bfqq,
-@@ -1715,13 +1725,17 @@ static void bfq_deactivate_bfqq(struct bfq_data *bfqd, struct bfq_queue *bfqq,
+-				bool requeue)
++				bool ins_into_idle_tree, bool expiration)
  {
  	struct bfq_entity *entity = &bfqq->entity;
  
 -	BUG_ON(bfqq == bfqd->in_service_queue);
- 	bfq_deactivate_entity(entity, requeue);
+-	bfq_deactivate_entity(entity, requeue);
++	bfq_deactivate_entity(entity, ins_into_idle_tree, expiration);
  }
  
  static void bfq_activate_bfqq(struct bfq_data *bfqd, struct bfq_queue *bfqq)
@@ -2722,13 +3303,35 @@ index 09e494b..d9e63712 100644
  	struct bfq_entity *entity = &bfqq->entity;
 +	struct bfq_service_tree *st = bfq_entity_service_tree(entity);
 +
-+	BUG_ON(bfqq != bfqd->in_service_queue &&
-+	       entity->tree != &st->active && entity->tree != &st->idle &&
++	BUG_ON(bfqq == bfqd->in_service_queue);
++	BUG_ON(entity->tree != &st->active && entity->tree != &st->idle &&
 +	       entity->on_st);
  
- 	bfq_activate_entity(entity, bfq_bfqq_non_blocking_wait_rq(bfqq));
+-	bfq_activate_entity(entity, bfq_bfqq_non_blocking_wait_rq(bfqq));
++	bfq_activate_requeue_entity(entity, bfq_bfqq_non_blocking_wait_rq(bfqq),
++				    false);
  	bfq_clear_bfqq_non_blocking_wait_rq(bfqq);
-@@ -1737,7 +1751,6 @@ static void bfq_del_bfqq_busy(struct bfq_data *bfqd, struct bfq_queue *bfqq)
+ }
+ 
++static void bfq_requeue_bfqq(struct bfq_data *bfqd, struct bfq_queue *bfqq)
++{
++	struct bfq_entity *entity = &bfqq->entity;
++
++	bfq_activate_requeue_entity(entity, false,
++				    bfqq == bfqd->in_service_queue);
++}
++
+ static void bfqg_stats_update_dequeue(struct bfq_group *bfqg);
+ 
+ /*
+  * Called when the bfqq no longer has requests pending, remove it from
+- * the service tree.
++ * the service tree. As a special case, it can be invoked during an
++ * expiration.
+  */
+-static void bfq_del_bfqq_busy(struct bfq_data *bfqd, struct bfq_queue *bfqq)
++static void bfq_del_bfqq_busy(struct bfq_data *bfqd, struct bfq_queue *bfqq,
++			      bool expiration)
  {
  	BUG_ON(!bfq_bfqq_busy(bfqq));
  	BUG_ON(!RB_EMPTY_ROOT(&bfqq->sort_list));
@@ -2736,11 +3339,38 @@ index 09e494b..d9e63712 100644
  
  	bfq_log_bfqq(bfqd, bfqq, "del from busy");
  
+@@ -1757,7 +1890,7 @@ static void bfq_del_bfqq_busy(struct bfq_data *bfqd, struct bfq_queue *bfqq)
+ 
+ 	BUG_ON(bfqq->entity.budget < 0);
+ 
+-	bfq_deactivate_bfqq(bfqd, bfqq, true);
++	bfq_deactivate_bfqq(bfqd, bfqq, true, expiration);
+ 
+ 	BUG_ON(bfqq->entity.budget < 0);
+ }
+diff --git a/block/bfq.h b/block/bfq.h
+index 1a03521..f90d534 100644
+--- a/block/bfq.h
++++ b/block/bfq.h
+@@ -140,10 +140,10 @@ struct bfq_entity {
+ 	struct bfq_weight_counter *weight_counter;
+ 
+ 	/*
+-	 * flag, true if the entity is on a tree (either the active or
+-	 * the idle one of its service_tree).
++	 * Flag, true if the entity is on a tree (either the active or
++	 * the idle one of its service_tree) or is in service.
+ 	 */
+-	int on_st;
++	bool on_st;
+ 
+ 	u64 finish; /* B-WF2Q+ finish timestamp (aka F_i) */
+ 	u64 start;  /* B-WF2Q+ start timestamp (aka S_i) */
 
-From 316c31562f169ccb8752045217aead1688229315 Mon Sep 17 00:00:00 2001
+From 6ef4dcd808aa50f7ba49bc0fde68b72a8a68028c Mon Sep 17 00:00:00 2001
 From: Paolo Valente <paolo.valente@linaro.org>
 Date: Fri, 16 Dec 2016 18:01:52 +0100
-Subject: [PATCH 24/24] Add code to redirect trace log to console
+Subject: [PATCH 24/28] Add code to redirect trace log to console
 
 Signed-off-by: Paolo Valente <paolo.valente@linaro.org>
 ---
@@ -2748,7 +3378,7 @@ Signed-off-by: Paolo Valente <paolo.valente@linaro.org>
  1 file changed, 38 insertions(+)
 
 diff --git a/block/bfq.h b/block/bfq.h
-index 1a03521..a09804e 100644
+index f90d534..d98403e 100644
 --- a/block/bfq.h
 +++ b/block/bfq.h
 @@ -648,6 +648,43 @@ BFQ_BFQQ_FNS(softrt_update);
@@ -2803,4 +3433,252 @@ index 1a03521..a09804e 100644
  
  /* Expiration reasons. */
  enum bfqq_expiration {
+
+From f7e139123c8becd5ac6de6b62d395f5d8e94e498 Mon Sep 17 00:00:00 2001
+From: Paolo Valente <paolo.valente@linaro.org>
+Date: Sun, 18 Dec 2016 22:45:07 +0100
+Subject: [PATCH 25/28] BFQ v8r6-rc2
+
+---
+ block/bfq-iosched.c | 2 +-
+ block/bfq.h         | 2 +-
+ 2 files changed, 2 insertions(+), 2 deletions(-)
+
+diff --git a/block/bfq-iosched.c b/block/bfq-iosched.c
+index 23e4c94..7036f0b 100644
+--- a/block/bfq-iosched.c
++++ b/block/bfq-iosched.c
+@@ -5229,7 +5229,7 @@ static struct blkcg_policy blkcg_policy_bfq = {
+ static int __init bfq_init(void)
+ {
+ 	int ret;
+-	char msg[60] = "BFQ I/O-scheduler: v8r6-rc1";
++	char msg[60] = "BFQ I/O-scheduler: v8r6-rc2";
+ 
+ #ifdef CONFIG_BFQ_GROUP_IOSCHED
+ 	ret = blkcg_policy_register(&blkcg_policy_bfq);
+diff --git a/block/bfq.h b/block/bfq.h
+index d98403e..4dd4931 100644
+--- a/block/bfq.h
++++ b/block/bfq.h
+@@ -1,5 +1,5 @@
+ /*
+- * BFQ v8r6-rc1 for 4.9.0: data structures and common functions prototypes.
++ * BFQ v8r6-rc2 for 4.9.0: data structures and common functions prototypes.
+  *
+  * Based on ideas and code from CFQ:
+  * Copyright (C) 2003 Jens Axboe <axboe@kernel.dk>
+
+From 2d790c793eab404abd5aadce0981b97c498c996b Mon Sep 17 00:00:00 2001
+From: Paolo Valente <paolo.valente@linaro.org>
+Date: Mon, 19 Dec 2016 08:12:26 +0100
+Subject: [PATCH 26/28] Fix bug in optimized update of next_in_service entity
+
+There was a case where bfq_update_next_in_service did not update
+next_in_service, even if it might need to be changed: in case of
+requeueing or repositioning of the entity that happened to be
+pointed exactly by next_in_service. This could result in violation
+of service guarantees, because, after a change of timestamps for
+such an entity, it might be the case that next_in_service had to
+point to a different entity. This commit fixes this bug.
+
+Signed-off-by: Paolo Valente <paolo.valente@linaro.org>
+---
+ block/bfq-sched.c | 19 +++++++++----------
+ 1 file changed, 9 insertions(+), 10 deletions(-)
+
+diff --git a/block/bfq-sched.c b/block/bfq-sched.c
+index 3b8e05b..41fd5c9 100644
+--- a/block/bfq-sched.c
++++ b/block/bfq-sched.c
+@@ -68,8 +68,9 @@ static struct bfq_entity *bfq_root_active_entity(struct rb_root *tree)
+ /**
+  * bfq_update_next_in_service - update sd->next_in_service
+  * @sd: sched_data for which to perform the update.
+- * @new_entity: if not NULL, pointer to the entity whose activation
+- *		triggered the invocation of this function.
++ * @new_entity: if not NULL, pointer to the entity whose activation,
++ *		requeueing or repositionig triggered the invocation of
++ *		this function.
+  *
+  * This function is called to update sd->next_in_service, which, in
+  * its turn, may change as a consequence of the insertion or
+@@ -95,17 +96,18 @@ static bool bfq_update_next_in_service(struct bfq_sched_data *sd,
+ 	struct bfq_queue *bfqq;
+ 
+ 	/*
+-	 * If this update is triggered by the activation of a new
+-	 * entity, then a full lookup in the active tree can be
+-	 * avoided. In fact, it is enough to check whether the
+-	 * just-activated entity has a higher priority of
++	 * 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
+ 	 * 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.
+ 	 */
+-	if (new_entity) {
++	if (new_entity && new_entity != sd->next_in_service) {
+ 		/*
+ 		 * Flag used to decide whether to replace
+ 		 * sd->next_in_service with new_entity. Tentatively
+@@ -114,9 +116,6 @@ static bool bfq_update_next_in_service(struct bfq_sched_data *sd,
+ 		 */
+ 		bool replace_next = true;
+ 
+-		if (new_entity == sd->next_in_service)
+-			return false;
+-
+ 		/*
+ 		 * If there is already a next_in_service candidate
+ 		 * entity, then compare class priorities or timestamps
+
+From 86fed232c6e9c6c54bb4e0035c5641977d734cc6 Mon Sep 17 00:00:00 2001
+From: Paolo Valente <paolo.valente@linaro.org>
+Date: Mon, 19 Dec 2016 09:11:50 +0100
+Subject: [PATCH 27/28] Stop bubble-up of next_in_service update if possible
+
+Signed-off-by: Paolo Valente <paolo.valente@linaro.org>
+---
+ block/bfq-sched.c | 38 +++++++++++++++++++++++++-------------
+ 1 file changed, 25 insertions(+), 13 deletions(-)
+
+diff --git a/block/bfq-sched.c b/block/bfq-sched.c
+index 41fd5c9..4af77f4 100644
+--- a/block/bfq-sched.c
++++ b/block/bfq-sched.c
+@@ -37,11 +37,16 @@ static int bfq_gt(u64 a, u64 b)
+ 
+ static struct bfq_entity *bfq_lookup_next_entity(struct bfq_sched_data *sd);
+ 
+-static void bfq_update_budget(struct bfq_entity *next_in_service)
++/*
++ * Returns true if this budget changes may let next_in_service->parent
++ * become the next_in_service entity for its parent entity.
++ */
++static bool bfq_update_parent_budget(struct bfq_entity *next_in_service)
+ {
+ 	struct bfq_entity *bfqg_entity;
+ 	struct bfq_group *bfqg;
+ 	struct bfq_sched_data *group_sd;
++	bool ret = false;
+ 
+ 	BUG_ON(!next_in_service);
+ 
+@@ -54,8 +59,13 @@ static void bfq_update_budget(struct bfq_entity *next_in_service)
+ 	 * as it must never become an in-service entity.
+ 	 */
+ 	bfqg_entity = bfqg->my_entity;
+-	if (bfqg_entity)
++	if (bfqg_entity) {
++		if (bfqg_entity->budget > next_in_service->budget)
++			ret = true;
+ 		bfqg_entity->budget = next_in_service->budget;
++	}
++
++	return ret;
+ }
+ 
+ static struct bfq_entity *bfq_root_active_entity(struct rb_root *tree)
+@@ -84,16 +94,16 @@ static struct bfq_entity *bfq_root_active_entity(struct rb_root *tree)
+  * both the last two activation sub-cases, new_entity points to the
+  * just activated or requeued entity.
+  *
+- * This is a still incomplete version of this function, which always
+- * returns true. It will return also false in its complete version, in
+- * case either next_in_service has not changed, or next_in_service has
+- * changed but in a way that will not influence upper levels.
++ * Returns true if sd->next_in_service changes in such a way that
++ * entity->parent may become the next_in_service for its parent
++ * entity.
+  */
+ static bool bfq_update_next_in_service(struct bfq_sched_data *sd,
+ 				       struct bfq_entity *new_entity)
+ {
+ 	struct bfq_entity *next_in_service = sd->next_in_service;
+ 	struct bfq_queue *bfqq;
++	bool parent_sched_may_change = false;
+ 
+ 	/*
+ 	 * If this update is triggered by the activation, requeueing
+@@ -150,12 +160,15 @@ static bool bfq_update_next_in_service(struct bfq_sched_data *sd,
+ 	} else /* invoked because of a deactivation: lookup needed */
+ 		next_in_service = bfq_lookup_next_entity(sd);
+ 
++	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;
+ 
+-	if (next_in_service)
+-		bfq_update_budget(next_in_service);
+-	else
+-		goto exit;
++	if (!next_in_service)
++		return parent_sched_may_change;
+ 
+ 	bfqq = bfq_entity_to_bfqq(next_in_service);
+ 	if (bfqq)
+@@ -171,8 +184,7 @@ static bool bfq_update_next_in_service(struct bfq_sched_data *sd,
+ 			     "update_next_in_service: chosen this entity");
+ 	}
+ #endif
+-exit:
+-	return true;
++	return parent_sched_may_change;
+ }
+ 
+ #else
+@@ -187,7 +199,7 @@ static int bfq_update_next_in_service(struct bfq_sched_data *sd)
+ 	return 0;
+ }
+ 
+-static void bfq_update_budget(struct bfq_entity *next_in_service)
++static void bfq_update_parent_budget(struct bfq_entity *next_in_service)
+ {
+ }
+ #endif
+
+From eb70b7cbd454b508d3d81cac89f4c4655f8ff7a1 Mon Sep 17 00:00:00 2001
+From: Paolo Valente <paolo.valente@linaro.org>
+Date: Mon, 19 Dec 2016 11:15:38 +0100
+Subject: [PATCH 28/28] BFQ v8r6-rc3
+
+Signed-off-by: Paolo Valente <paolo.valente@linaro.org>
+---
+ block/bfq-iosched.c | 2 +-
+ block/bfq.h         | 2 +-
+ 2 files changed, 2 insertions(+), 2 deletions(-)
+
+diff --git a/block/bfq-iosched.c b/block/bfq-iosched.c
+index 7036f0b..be8aa7f 100644
+--- a/block/bfq-iosched.c
++++ b/block/bfq-iosched.c
+@@ -5229,7 +5229,7 @@ static struct blkcg_policy blkcg_policy_bfq = {
+ static int __init bfq_init(void)
+ {
+ 	int ret;
+-	char msg[60] = "BFQ I/O-scheduler: v8r6-rc2";
++	char msg[60] = "BFQ I/O-scheduler: v8r6-rc3";
  
+ #ifdef CONFIG_BFQ_GROUP_IOSCHED
+ 	ret = blkcg_policy_register(&blkcg_policy_bfq);
+diff --git a/block/bfq.h b/block/bfq.h
+index 4dd4931..b285bc4 100644
+--- a/block/bfq.h
++++ b/block/bfq.h
+@@ -1,5 +1,5 @@
+ /*
+- * BFQ v8r6-rc2 for 4.9.0: data structures and common functions prototypes.
++ * BFQ v8r6-rc3 for 4.9.0: data structures and common functions prototypes.
+  *
+  * Based on ideas and code from CFQ:
+  * Copyright (C) 2003 Jens Axboe <axboe@kernel.dk>
+0
diff --git a/PKGBUILD b/PKGBUILD
index d625f8cc1140..77f8cb7ffc67 100644
--- a/PKGBUILD
+++ b/PKGBUILD
@@ -52,7 +52,7 @@ pkgbase=linux-bfq
 # pkgname=('linux-bfq' 'linux-bfq-headers' 'linux-bfq-docs')
 _srcname=linux-4.8
 pkgver=4.8.15
-pkgrel=2
+pkgrel=3
 arch=('i686' 'x86_64')
 url="http://algo.ing.unimo.it"
 license=('GPL2')
@@ -462,15 +462,15 @@ sha512sums=('a48a065f21e1c7c4de4cf8ca47b8b8d9a70f86b64e7cfa6e01be490f78895745b9c
             'dc0649dfe2a5ce8e8879a62df29a4a1959eb1a84e5d896a9cb119d6a85a9bad1b17135371799e0be96532e17c66043d298e4a14b18fad3078a1f425108f888c9'
             '135afcffee2439e2260a71202658dce9ec5f555de3291b2d49a5cffdd953c6d7851b8a90e961576895555142a618e52220a7e4a46521ca4ba19d37df71887581'
             '87ae76889ab84ced46c237374c124786551982f8ff7325102af9153aed1ab7be72bec4db1f7516426c5ee34c5ce17221679eb2f129c5cbdeec05c0d3cb7f785d'
-            '6046432243b8f0497b43ea2c5fe3fde5135e058f2be25c02773ead93e2ab3b525b6f7c1c4898b9e67ac2bec0959b972829e997e79fabf6ac87e006700dfaf987'
+            'ba9af1f177159ae1e6eba7375850a20e5d260e19c340f9bc540e6c91dc64e6a2841d261532b21e29a60bdb74123baa01a823837a699a5e74930b5062d590d5eb'
             'd9d28e02e964704ea96645a5107f8b65cae5f4fb4f537e224e5e3d087fd296cb770c29ac76e0ce95d173bc420ea87fb8f187d616672a60a0cae618b0ef15b8c8'
-            'dc9ad074791a9edb3414a71480525a1c4a75b257137c754749c251e45ef376e313d3310766fedcabcd392837a8022bbcd97bfcd17c42feae63f71b4c4064b73d'
-            'bcc657cd2366b55ba303d4d091ab9958e4f97121e7fdd64013a90be7fb6b19ac28ca2e8973496935475b9a8f8386bcbed8924981a20bb51cf3fc5c6f4f14b22a'
+            '6dc35242059c8ce3cc9878ce661511b46266a63182afc37deb53bc2ba6b8e7fe5be3d7da08d1a2abcb9a1cd16e896a49ef9e360e8e2bee53c8d7b7004bc8f655'
+            'aebf2940074ec3b9f4b6177489ec37400b962f714b4732ff3386e3532934520d507aff3effb1d38ec4b113508ce7c7ba4214b8b448854ddf857435a35cff3db7'
             'd6faa67f3ef40052152254ae43fee031365d0b1524aa0718b659eb75afc21a3f79ea8d62d66ea311a800109bed545bc8f79e8752319cd378eef2cbd3a09aba22'
             '2dc6b0ba8f7dbf19d2446c5c5f1823587de89f4e28e9595937dd51a87755099656f2acec50e3e2546ea633ad1bfd1c722e0c2b91eef1d609103d8abdc0a7cbaf'
             'c53bd47527adbd2599a583e05a7d24f930dc4e86b1de017486588205ad6f262a51a4551593bc7a1218c96541ea073ea03b770278d947b1cd0d2801311fcc80e5'
             '002d5e0ccfa5824c1750912a6400ff722672d6587b74ba66b1127cf1228048f604bba107617cf4f4477884039af4d4d196cf1b74cefe43b0bddc82270f11940d'
-            '98612f37013d1b41c76887bc5ed80f70753f6fc859748038dc83f3b53aa89464321951c6c21b364f56b2d4860e594c2091240c70ff70ce616d6b3fdadb817934')
+            '6c9992e1ae39e81577af9399d583c8c04c2d8ff205eb58ed082016e310ed2b2f040689ae8f2a36bf131d3c58d40eaf94ba2bd4b9fc0006eeedb9569f8c0deef5')
             
 validpgpkeys=(
               'ABAF11C65A2970B130ABE3C479BE3E4300411886' # Linus Torvalds
diff --git a/config b/config
index 788f14dd440e..99010b0ae71e 100644
--- a/config
+++ b/config
@@ -1,6 +1,6 @@
 #
 # Automatically generated file; DO NOT EDIT.
-# Linux/x86 4.8.15-1 Kernel Configuration
+# Linux/x86 4.8.15-2 Kernel Configuration
 #
 # CONFIG_64BIT is not set
 CONFIG_X86_32=y
@@ -445,6 +445,7 @@ CONFIG_M686=y
 # CONFIG_MHASWELL is not set
 # CONFIG_MBROADWELL is not set
 # CONFIG_MSKYLAKE is not set
+# CONFIG_MNATIVE is not set
 CONFIG_X86_GENERIC=y
 CONFIG_X86_INTERNODE_CACHE_SHIFT=6
 CONFIG_X86_L1_CACHE_SHIFT=6
diff --git a/config.x86_64 b/config.x86_64
index 246520db8b4f..808ba7262646 100644
--- a/config.x86_64
+++ b/config.x86_64
@@ -1,6 +1,6 @@
 #
 # Automatically generated file; DO NOT EDIT.
-# Linux/x86 4.8.15-1 Kernel Configuration
+# Linux/x86 4.8.15-2 Kernel Configuration
 #
 CONFIG_64BIT=y
 CONFIG_X86_64=y
@@ -448,6 +448,7 @@ CONFIG_NO_BOOTMEM=y
 # CONFIG_MBROADWELL is not set
 # CONFIG_MSKYLAKE is not set
 CONFIG_GENERIC_CPU=y
+# CONFIG_MNATIVE is not set
 CONFIG_X86_INTERNODE_CACHE_SHIFT=6
 CONFIG_X86_L1_CACHE_SHIFT=6
 CONFIG_X86_TSC=y