Skip to contentSkip to conversation

cfq-iosched: fix corner cases in idling logic

PATCH In review Corrado Zoccolo 3 participants 8 messages Nov 24, 2009 – Dec 2, 2009 Block layer

lore
Share & tools
lore
#0 lore raw

PATCH 4/4 cfq-iosched: fix corner cases in idling logic

Idling logic was disabled in some corner cases, leading to unfair share for noidle queues.
* the idle timer was not armed if there were other requests in the driver. unfortunately, those requests could come from other workloads, or queues for which we don't enable idling. So we will check only pending requests from the active queue
* rq_noidle check on no-idle queue could disable the end of tree idle if the last completed request was rq_noidle. Now, we will disable that idle only if all the queues served in the no-idle tree had rq_noidle requests.

---
 block/cfq-iosched.c |   32 ++++++++++++++++++++++----------
 1 files changed, 22 insertions(+), 10 deletions(-)
block/cfq-iosched.c +22 -10
index 373e80f..d44f8a4 100644
@@ -172,6 +172,7 @@ struct cfq_data {
 	enum wl_prio_t serving_prio;
 	enum wl_type_t serving_type;
 	unsigned long workload_expires;
+	bool noidle_tree_requires_idle;
 
 	/*
 	 * Each priority tree is sorted by next_request position.  These
@@ -1249,9 +1250,9 @@ static void cfq_arm_slice_timer(struct cfq_data *cfqd)
 		return;
 
 	/*
-	 * still requests with the driver, don't idle
+	 * still active requests from this queue, don't idle
 	 */
-	if (rq_in_driver(cfqd))
+	if (cfqq->dispatched)
 		return;
 
 	/*
@@ -1487,6 +1488,7 @@ static void choose_service_tree(struct cfq_data *cfqd)
 
 	slice = max_t(unsigned, slice, CFQ_MIN_TT);
 	cfqd->workload_expires = jiffies + slice;
+	cfqd->noidle_tree_requires_idle = false;
 }
 
 /*
@@ -2606,17 +2608,27 @@ static void cfq_completed_request(struct request_queue *q, struct request *rq)
 			cfq_clear_cfqq_slice_new(cfqq);
 		}
 		/*
-		 * If there are no requests waiting in this queue, and
-		 * there are other queues ready to issue requests, AND
-		 * those other queues are issuing requests within our
-		 * mean seek distance, give them a chance to run instead
-		 * of idling.
+		 * Idling is not enabled on:
+		 * - expired queues
+		 * - idle-priority queues
+		 * - async queues
+		 * - queues with still some requests queued
+		 * - when there is a close cooperator
 		 */
 		if (cfq_slice_used(cfqq) || cfq_class_idle(cfqq))
 			cfq_slice_expired(cfqd, 1);
-		else if (cfqq_empty && !cfq_close_cooperator(cfqd, cfqq) &&
-			 sync && !rq_noidle(rq))
-			cfq_arm_slice_timer(cfqd);
+		else if (sync && cfqq_empty &&
+			 !cfq_close_cooperator(cfqd, cfqq)) {
+			cfqd->noidle_tree_requires_idle |= !rq_noidle(rq);
+			/*
+			 * Idling is enabled for SYNC_WORKLOAD.
+			 * SYNC_NOIDLE_WORKLOAD idles at the end of the tree
+			 * only if we processed at least one !rq_noidle request
+			 */
+			if (cfqd->serving_type == SYNC_WORKLOAD
+			    || cfqd->noidle_tree_requires_idle)
+				cfq_arm_slice_timer(cfqd);
+		}
 	}
 
 	if (!rq_in_driver(cfqd))
Signature · 1 line
1.6.2.5
Acked-by on v1 4/4
#1 lore raw
Quoted 11 lines · Corrado Zoccolo

Idling logic was disabled in some corner cases, leading to unfair share for noidle queues.
* the idle timer was not armed if there were other requests in the driver. unfortunately, those requests could come from other workloads, or queues for which we don't enable idling. So we will check only pending requests from the active queue
* rq_noidle check on no-idle queue could disable the end of tree idle if the last completed request was rq_noidle. Now, we will disable that idle only if all the queues served in the no-idle tree had rq_noidle requests.

Quoted 2 lines

Looks good to me.

A minor nit, "noidle_tree_requires_idle" is too long a string. A little smaller string can be "idle_on_noidle_wl".

Thanks
Vivek

Quoted 75 lines
---
 block/cfq-iosched.c |   32 ++++++++++++++++++++++----------
 1 files changed, 22 insertions(+), 10 deletions(-)
block/cfq-iosched.c +22 -10
index 373e80f..d44f8a4 100644
@@ -172,6 +172,7 @@ struct cfq_data {
 	enum wl_prio_t serving_prio;
 	enum wl_type_t serving_type;
 	unsigned long workload_expires;
+	bool noidle_tree_requires_idle;
 
 	/*
 	 * Each priority tree is sorted by next_request position.  These
@@ -1249,9 +1250,9 @@ static void cfq_arm_slice_timer(struct cfq_data *cfqd)
 		return;
 
 	/*
-	 * still requests with the driver, don't idle
+	 * still active requests from this queue, don't idle
 	 */
-	if (rq_in_driver(cfqd))
+	if (cfqq->dispatched)
 		return;
 
 	/*
@@ -1487,6 +1488,7 @@ static void choose_service_tree(struct cfq_data *cfqd)
 
 	slice = max_t(unsigned, slice, CFQ_MIN_TT);
 	cfqd->workload_expires = jiffies + slice;
+	cfqd->noidle_tree_requires_idle = false;
 }
 
 /*
@@ -2606,17 +2608,27 @@ static void cfq_completed_request(struct request_queue *q, struct request *rq)
 			cfq_clear_cfqq_slice_new(cfqq);
 		}
 		/*
-		 * If there are no requests waiting in this queue, and
-		 * there are other queues ready to issue requests, AND
-		 * those other queues are issuing requests within our
-		 * mean seek distance, give them a chance to run instead
-		 * of idling.
+		 * Idling is not enabled on:
+		 * - expired queues
+		 * - idle-priority queues
+		 * - async queues
+		 * - queues with still some requests queued
+		 * - when there is a close cooperator
 		 */
 		if (cfq_slice_used(cfqq) || cfq_class_idle(cfqq))
 			cfq_slice_expired(cfqd, 1);
-		else if (cfqq_empty && !cfq_close_cooperator(cfqd, cfqq) &&
-			 sync && !rq_noidle(rq))
-			cfq_arm_slice_timer(cfqd);
+		else if (sync && cfqq_empty &&
+			 !cfq_close_cooperator(cfqd, cfqq)) {
+			cfqd->noidle_tree_requires_idle |= !rq_noidle(rq);
+			/*
+			 * Idling is enabled for SYNC_WORKLOAD.
+			 * SYNC_NOIDLE_WORKLOAD idles at the end of the tree
+			 * only if we processed at least one !rq_noidle request
+			 */
+			if (cfqd->serving_type == SYNC_WORKLOAD
+			    || cfqd->noidle_tree_requires_idle)
+				cfq_arm_slice_timer(cfqd);
+		}
 	}
 
 	if (!rq_in_driver(cfqd))
Signature · 1 line
1.6.2.5
#2 lore raw
In reply to Corrado Zoccolo
Quoted 20 lines · Corrado Zoccolo

Idling logic was disabled in some corner cases, leading to unfair share for noidle queues.
* the idle timer was not armed if there were other requests in the driver. unfortunately, those requests could come from other workloads, or queues for which we don't enable idling. So we will check only pending requests from the active queue
* rq_noidle check on no-idle queue could disable the end of tree idle if the last completed request was rq_noidle. Now, we will disable that idle only if all the queues served in the no-idle tree had rq_noidle requests.

block/cfq-iosched.c +0 -2
@@ -2606,17 +2608,27 @@ static void cfq_completed_request(struct request_queue *q, struct request *rq)
 			cfq_clear_cfqq_slice_new(cfqq);
 		}
 		/*
-		 * If there are no requests waiting in this queue, and
-		 * there are other queues ready to issue requests, AND

block/cfq-iosched.c static void cfq_completed_request(struct request_queue *q, struct request *rq) · line 2617

Quoted 10 lines
block/cfq-iosched.c +6 -3
-		 * those other queues are issuing requests within our
-		 * mean seek distance, give them a chance to run instead
-		 * of idling.
+		 * Idling is not enabled on:
+		 * - expired queues
+		 * - idle-priority queues
+		 * - async queues
+		 * - queues with still some requests queued
+		 * - when there is a close cooperator
 		 */

I'm not sure this logic is correct. Is this for the 2.6.33 branch? If so, the coop flag now means that multiple processes share the same cfqq. Are you sure this is the right thing to do for close cooperators?

Cheers,
Jeff

Quoted 20 lines
block/cfq-iosched.c +12 -3
 		if (cfq_slice_used(cfqq) || cfq_class_idle(cfqq))
 			cfq_slice_expired(cfqd, 1);
-		else if (cfqq_empty && !cfq_close_cooperator(cfqd, cfqq) &&
-			 sync && !rq_noidle(rq))
-			cfq_arm_slice_timer(cfqd);
+		else if (sync && cfqq_empty &&
+			 !cfq_close_cooperator(cfqd, cfqq)) {
+			cfqd->noidle_tree_requires_idle |= !rq_noidle(rq);
+			/*
+			 * Idling is enabled for SYNC_WORKLOAD.
+			 * SYNC_NOIDLE_WORKLOAD idles at the end of the tree
+			 * only if we processed at least one !rq_noidle request
+			 */
+			if (cfqd->serving_type == SYNC_WORKLOAD
+			    || cfqd->noidle_tree_requires_idle)
+				cfq_arm_slice_timer(cfqd);
+		}
 	}
 
 	if (!rq_in_driver(cfqd))
#3 lore raw

Hi Jeff,

Quoted 26 lines · Jeff Moyer
Quoted 24 lines · Corrado Zoccolo

Idling logic was disabled in some corner cases, leading to unfair share for noidle queues.
* the idle timer was not armed if there were other requests in the driver. unfortunately, those requests could come from other workloads, or queues for which we don't enable idling. So we will check only pending requests from the active queue
* rq_noidle check on no-idle queue could disable the end of tree idle if the last completed request was rq_noidle. Now, we will disable that idle only if all the queues served in the no-idle tree had rq_noidle requests.

block/cfq-iosched.c +1 -5
@@ -2606,17 +2608,27 @@ static void cfq_completed_request(struct request_queue *q, struct request *rq)
                       cfq_clear_cfqq_slice_new(cfqq);
               }
               /*
-              * If there are no requests waiting in this queue, and
-              * there are other queues ready to issue requests, AND
-              * those other queues are issuing requests within our
-              * mean seek distance, give them a chance to run instead
-              * of idling.
+              * Idling is not enabled on:
Quoted 8 lines

block/cfq-iosched.c static void cfq_completed_request(struct request_queue *q, struct request *rq) · line 2617

Quoted 6 lines
block/cfq-iosched.c +5 -0
+              * - expired queues
+              * - idle-priority queues
+              * - async queues
+              * - queues with still some requests queued
+              * - when there is a close cooperator
                */

I'm not sure this logic is correct.  Is this for the 2.6.33 branch?

Yes.

Quoted 2 lines

 If so, the coop flag now means that multiple processes share the same cfqq.  Are you sure this is the right thing to do for close cooperators?

I'm not sure. I didn't change the logic for close cooperators:
- else if (cfqq_empty && !cfq_close_cooperator(cfqd, cfqq) &&
- sync && !rq_noidle(rq))
- cfq_arm_slice_timer(cfqd);
+ else if (sync && cfqq_empty &&
+ !cfq_close_cooperator(cfqd, cfqq)) {
+ cfqd->noidle_tree_requires_idle |= !rq_noidle(rq);

I changed the rq_noidle part, and rewrote the comment to be aligned with the code.
So I don't mind if you improve (or just remove) the close cooperator part. Probably, you should do a test where close cooperating processes are competing with a sequential reader, to see the effect of idling or not on them.

Thanks
Corrado

Quoted 3 lines

Cheers,
Jeff

Signature · 10 lines
__________________________________________________________________________

dott. Corrado Zoccolo                          mailto:[email protected]
PhD - Department of Computer Science - University of Pisa, Italy
--------------------------------------------------------------------------
The self-confidence of a warrior is not the self-confidence of the average
man. The average man seeks certainty in the eyes of the onlooker and calls
that self-confidence. The warrior seeks impeccability in his own eyes and
calls that humbleness.
                               Tales of Power - C. Castaneda
#4 lore raw
Quoted 47 lines · Corrado Zoccolo

Hi Jeff,

Quoted 26 lines · Jeff Moyer
Quoted 24 lines · Corrado Zoccolo

Idling logic was disabled in some corner cases, leading to unfair share for noidle queues.
* the idle timer was not armed if there were other requests in the driver. unfortunately, those requests could come from other workloads, or queues for which we don't enable idling. So we will check only pending requests from the active queue
* rq_noidle check on no-idle queue could disable the end of tree idle if the last completed request was rq_noidle. Now, we will disable that idle only if all the queues served in the no-idle tree had rq_noidle requests.

block/cfq-iosched.c +1 -5
@@ -2606,17 +2608,27 @@ static void cfq_completed_request(struct request_queue *q, struct request *rq)
                       cfq_clear_cfqq_slice_new(cfqq);
               }
               /*
-              * If there are no requests waiting in this queue, and
-              * there are other queues ready to issue requests, AND
-              * those other queues are issuing requests within our
-              * mean seek distance, give them a chance to run instead
-              * of idling.
+              * Idling is not enabled on:
Quoted 8 lines

block/cfq-iosched.c static void cfq_completed_request(struct request_queue *q, struct request *rq) · line 2617

Quoted 6 lines
block/cfq-iosched.c +5 -0
+              * - expired queues
+              * - idle-priority queues
+              * - async queues
+              * - queues with still some requests queued
+              * - when there is a close cooperator
                */

I'm not sure this logic is correct.  Is this for the 2.6.33 branch?

Yes.

Quoted 2 lines

 If so, the coop flag now means that multiple processes share the same cfqq.  Are you sure this is the right thing to do for close cooperators?

I'm not sure. I didn't change the logic for close cooperators:

block/cfq-iosched.c +3 -3
-               else if (cfqq_empty && !cfq_close_cooperator(cfqd, cfqq) &&
-                        sync && !rq_noidle(rq))
-                       cfq_arm_slice_timer(cfqd);
+               else if (sync && cfqq_empty &&
+                        !cfq_close_cooperator(cfqd, cfqq)) {
+                       cfqd->noidle_tree_requires_idle |= !rq_noidle(rq);
Quoted 6 lines

I changed the rq_noidle part, and rewrote the comment to be aligned with the code.
So I don't mind if you improve (or just remove) the close cooperator part. Probably, you should do a test where close cooperating processes are competing with a sequential reader, to see the effect of idling or not on them.

I also can't find what's wrong with this. Previously we were not merging close cooperators in a single queue. So if we found a close cooperator we chose to not idle and move to that close cooperator. Now we try to merge all the close cooperators in a single queue. But that merging has not taken place yet and will happen when next request comes.

A normal sequential reader will not find the close cooperator. Only the queues which should be merged will find the close cooperator. If anyway these queues are going to be merged soon, there is proably no point in continuing to idle on this queue in case we found a close cooperator.

So, to me even in new code by jeff, it probably is fine to continue with policy of not idling if we found a close cooperator.

Thanks
Vivek

Quoted 18 lines

Thanks
Corrado

Quoted 3 lines

Cheers,
Jeff

Signature · 10 lines
__________________________________________________________________________

dott. Corrado Zoccolo                          mailto:[email protected]
PhD - Department of Computer Science - University of Pisa, Italy
--------------------------------------------------------------------------
The self-confidence of a warrior is not the self-confidence of the average
man. The average man seeks certainty in the eyes of the onlooker and calls
that self-confidence. The warrior seeks impeccability in his own eyes and
calls that humbleness.
                               Tales of Power - C. Castaneda
#5 lore raw
Quoted 37 lines · Vivek Goyal
Quoted 36 lines · Corrado Zoccolo

Hi Jeff,

Quoted 34 lines · Jeff Moyer
Quoted 20 lines · Corrado Zoccolo

Idling logic was disabled in some corner cases, leading to unfair share for noidle queues.
* the idle timer was not armed if there were other requests in the driver. unfortunately, those requests could come from other workloads, or queues for which we don't enable idling. So we will check only pending requests from the active queue
* rq_noidle check on no-idle queue could disable the end of tree idle if the last completed request was rq_noidle. Now, we will disable that idle only if all the queues served in the no-idle tree had rq_noidle requests.

block/cfq-iosched.c +0 -2
@@ -2606,17 +2608,27 @@ static void cfq_completed_request(struct request_queue *q, struct request *rq)
                       cfq_clear_cfqq_slice_new(cfqq);
               }
               /*
-              * If there are no requests waiting in this queue, and
-              * there are other queues ready to issue requests, AND

block/cfq-iosched.c static void cfq_completed_request(struct request_queue *q, struct request *rq) · line 2617

Quoted 10 lines
block/cfq-iosched.c +6 -3
-              * those other queues are issuing requests within our
-              * mean seek distance, give them a chance to run instead
-              * of idling.
+              * Idling is not enabled on:
+              * - expired queues
+              * - idle-priority queues
+              * - async queues
+              * - queues with still some requests queued
+              * - when there is a close cooperator
                */

I'm not sure this logic is correct.  Is this for the 2.6.33 branch?

Quoted 4 lines
Quoted 4 lines

Yes.

Quoted 2 lines

 If so, the coop flag now means that multiple processes share the same cfqq.  Are you sure this is the right thing to do for close cooperators?

I'm not sure. I didn't change the logic for close cooperators:

Heh, right you are.

Quoted 14 lines
Quoted 7 lines
block/cfq-iosched.c +3 -3
-               else if (cfqq_empty && !cfq_close_cooperator(cfqd, cfqq) &&
-                        sync && !rq_noidle(rq))
-                       cfq_arm_slice_timer(cfqd);
+               else if (sync && cfqq_empty &&
+                        !cfq_close_cooperator(cfqd, cfqq)) {
+                       cfqd->noidle_tree_requires_idle |= !rq_noidle(rq);
Quoted 6 lines

I changed the rq_noidle part, and rewrote the comment to be aligned with the code.
So I don't mind if you improve (or just remove) the close cooperator part. Probably, you should do a test where close cooperating processes are competing with a sequential reader, to see the effect of idling or not on them.

Quoted 5 lines

I also can't find what's wrong with this. Previously we were not merging close cooperators in a single queue. So if we found a close cooperator we chose to not idle and move to that close cooperator. Now we try to merge all the close cooperators in a single queue. But that merging has not taken place yet and will happen when next request comes.

The coop flag is not set until the merge has taken place.

Quoted 7 lines

A normal sequential reader will not find the close cooperator. Only the queues which should be merged will find the close cooperator. If anyway these queues are going to be merged soon, there is proably no point in continuing to idle on this queue in case we found a close cooperator.

So, to me even in new code by jeff, it probably is fine to continue with policy of not idling if we found a close cooperator.

That would mean changing the check from cfqq_coop to cfqq->new_queue != NULL.

Cheers,
Jeff

#6 lore raw
Quoted 73 lines · Jeff Moyer
Quoted 37 lines · Vivek Goyal
Quoted 36 lines · Corrado Zoccolo

Hi Jeff,

Quoted 34 lines · Jeff Moyer
Quoted 20 lines · Corrado Zoccolo

Idling logic was disabled in some corner cases, leading to unfair share for noidle queues.
* the idle timer was not armed if there were other requests in the driver. unfortunately, those requests could come from other workloads, or queues for which we don't enable idling. So we will check only pending requests from the active queue
* rq_noidle check on no-idle queue could disable the end of tree idle if the last completed request was rq_noidle. Now, we will disable that idle only if all the queues served in the no-idle tree had rq_noidle requests.

block/cfq-iosched.c +0 -2
@@ -2606,17 +2608,27 @@ static void cfq_completed_request(struct request_queue *q, struct request *rq)
                       cfq_clear_cfqq_slice_new(cfqq);
               }
               /*
-              * If there are no requests waiting in this queue, and
-              * there are other queues ready to issue requests, AND

block/cfq-iosched.c static void cfq_completed_request(struct request_queue *q, struct request *rq) · line 2617

Quoted 10 lines
block/cfq-iosched.c +6 -3
-              * those other queues are issuing requests within our
-              * mean seek distance, give them a chance to run instead
-              * of idling.
+              * Idling is not enabled on:
+              * - expired queues
+              * - idle-priority queues
+              * - async queues
+              * - queues with still some requests queued
+              * - when there is a close cooperator
                */

I'm not sure this logic is correct.  Is this for the 2.6.33 branch?

Quoted 4 lines
Quoted 4 lines

Yes.

Quoted 2 lines

 If so, the coop flag now means that multiple processes share the same cfqq.  Are you sure this is the right thing to do for close cooperators?

I'm not sure. I didn't change the logic for close cooperators:

Heh, right you are.

Quoted 14 lines
Quoted 7 lines
block/cfq-iosched.c +3 -3
-               else if (cfqq_empty && !cfq_close_cooperator(cfqd, cfqq) &&
-                        sync && !rq_noidle(rq))
-                       cfq_arm_slice_timer(cfqd);
+               else if (sync && cfqq_empty &&
+                        !cfq_close_cooperator(cfqd, cfqq)) {
+                       cfqd->noidle_tree_requires_idle |= !rq_noidle(rq);
Quoted 6 lines

I changed the rq_noidle part, and rewrote the comment to be aligned with the code.
So I don't mind if you improve (or just remove) the close cooperator part. Probably, you should do a test where close cooperating processes are competing with a sequential reader, to see the effect of idling or not on them.

Quoted 5 lines

I also can't find what's wrong with this. Previously we were not merging close cooperators in a single queue. So if we found a close cooperator we chose to not idle and move to that close cooperator. Now we try to merge all the close cooperators in a single queue. But that merging has not taken place yet and will happen when next request comes.

The coop flag is not set until the merge has taken place.

Quoted 5 lines

A normal sequential reader will not find the close cooperator. Only the queues which should be merged will find the close cooperator. If anyway these queues are going to be merged soon, there is proably no point in continuing to idle on this queue in case we found a close cooperator.

Quoted 5 lines
Quoted 2 lines

So, to me even in new code by jeff, it probably is fine to continue with policy of not idling if we found a close cooperator.

That would mean changing the check from cfqq_coop to cfqq->new_queue != NULL.

Does it make a big difference. cfq_close_cooperator() does not seem to be relying on coop flag. It will return us a queue if it thinks there is a close cooperator. (Irrespective of the fact whether cfqq->new_cfqq has bee setup yet or not). IIUC, cfqq->new_cfqq will be set in select_queue(). So in case select_queue() has not run yet, then cfqq->new_cfqq = NULL but we have a close cooperator.

But I guess this condition will not hit many a times as select_queue() happens very frequently on NCQ hardware and the moment select queue finds close cooperator it will expire the current queue and above check will not even get a chance to turn.

So IIUC, if we are here cfqq->new_cfqq is always NULL otherwise select_queue() by now must have expired us and we will not be here. So either we can completely remove the check or we can just continue with above check.

Thanks
Vivek

#7 lore raw
Quoted 7 lines · Vivek Goyal

Does it make a big difference. cfq_close_cooperator() does not seem to be relying on coop flag. It will return us a queue if it thinks there is a close cooperator. (Irrespective of the fact whether cfqq->new_cfqq has bee setup yet or not). IIUC, cfqq->new_cfqq will be set in select_queue(). So in case select_queue() has not run yet, then cfqq->new_cfqq = NULL but we have a close cooperator.

Quoted 8 lines

But I guess this condition will not hit many a times as select_queue() happens very frequently on NCQ hardware and the moment select queue finds close cooperator it will expire the current queue and above check will not even get a chance to turn.

So IIUC, if we are here cfqq->new_cfqq is always NULL otherwise select_queue() by now must have expired us and we will not be here. So either we can completely remove the check or we can just continue with above check.

Wow, I need another cup of coffee for sure. You can just ignore me as I completely misread the code being changed.

Sorry for the noise. I'll go make some coffee.

Cheers,
Jeff