[PATCH] deadline-iosched: don't allow aliased requests to starve others

[PATCH] deadline-iosched: don't allow aliased requests to starve others

[Jeff Moyer]

Hi,

In running a test case that tries to trip up the kernel's AIO
implementation, we ran into a situation where no other I/O to the device
under test would be completed.  The test program spawned (in this case)
100 threads, each of which performed the following in a loop:

open file O_DIRECT
queue 1MB of read I/O from file using 16 iocbs
close file
repeat

The program does NOT wait for the I/O to complete.  The file length is
only 4MB, meaning that you have 25 threads performing I/O on each of the
4 1MB regions.

Both deadline and cfq check for aliased requests in the sorted list of
I/Os, and when an alias is found, the request in the rb tree is moved to
the dispatch list.  So, what happens is that, with this workload, only
requests from this program are moved to the dispatch list, starving out
all other I/O.

The attached patch fixes this problem by issuing all expired requests in
the aliased request handling code.  The reason I opted to issue all
expired requsts is because if we only service a single one, I still see
really awful interactivity;  an ls would take over 5 minutes to
complete.  With the attached patch, the ls took about 7 seconds to
complete.

Comments, as always, are welcome.

Cheers,
Jeff

diff --git a/block/deadline-iosched.c b/block/deadline-iosched.c
index b547cbc..3f3649a 100644
--- a/block/deadline-iosched.c
+++ b/block/deadline-iosched.c
@@ -73,14 +73,41 @@ deadline_latter_request(struct request *rq)
 	return NULL;
 }
 
+/*
+ * deadline_check_fifo returns 0 if there are no expired requests on the fifo,
+ * 1 otherwise. Requires !list_empty(&dd->fifo_list[data_dir])
+ */
+static inline int deadline_check_fifo(struct deadline_data *dd, int ddir)
+{
+	struct request *rq = rq_entry_fifo(dd->fifo_list[ddir].next);
+
+	/*
+	 * rq is expired!
+	 */
+	if (time_after(jiffies, rq_fifo_time(rq)))
+		return 1;
+
+	return 0;
+}
+
 static void
 deadline_add_rq_rb(struct deadline_data *dd, struct request *rq)
 {
 	struct rb_root *root = deadline_rb_root(dd, rq);
 	struct request *__alias;
 
-	while (unlikely(__alias = elv_rb_add(root, rq)))
+	while (unlikely(__alias = elv_rb_add(root, rq))) {
+		int data_dir = rq_data_dir(rq);
+
 		deadline_move_request(dd, __alias);
+
+		while (!list_empty(&dd->fifo_list[data_dir]) &&
+		       deadline_check_fifo(dd, data_dir)) {
+			struct request *__rq;
+			__rq = rq_entry_fifo(dd->fifo_list[data_dir].next);
+			deadline_move_request(dd, __rq);
+		}
+	}
 }
 
 static inline void
@@ -222,23 +249,6 @@ deadline_move_request(struct deadline_data *dd, struct request *rq)
 }
 
 /*
- * deadline_check_fifo returns 0 if there are no expired requests on the fifo,
- * 1 otherwise. Requires !list_empty(&dd->fifo_list[data_dir])
- */
-static inline int deadline_check_fifo(struct deadline_data *dd, int ddir)
-{
-	struct request *rq = rq_entry_fifo(dd->fifo_list[ddir].next);
-
-	/*
-	 * rq is expired!
-	 */
-	if (time_after(jiffies, rq_fifo_time(rq)))
-		return 1;
-
-	return 0;
-}
-
-/*
  * deadline_dispatch_requests selects the best request according to
  * read/write expire, fifo_batch, etc
  */

Re: [PATCH] deadline-iosched: don't allow aliased requests to starve others

[Jeff Moyer]

Jeff Moyer <jmoyer@redhat.com> writes:

> Hi,
>
> In running a test case that tries to trip up the kernel's AIO
> implementation, we ran into a situation where no other I/O to the device
> under test would be completed.  The test program spawned (in this case)
> 100 threads, each of which performed the following in a loop:
>
> open file O_DIRECT
> queue 1MB of read I/O from file using 16 iocbs
> close file
> repeat
>
> The program does NOT wait for the I/O to complete.  The file length is
> only 4MB, meaning that you have 25 threads performing I/O on each of the
> 4 1MB regions.
>
> Both deadline and cfq check for aliased requests in the sorted list of
> I/Os, and when an alias is found, the request in the rb tree is moved to
> the dispatch list.  So, what happens is that, with this workload, only
> requests from this program are moved to the dispatch list, starving out
> all other I/O.
>
> The attached patch fixes this problem by issuing all expired requests in
> the aliased request handling code.  The reason I opted to issue all
> expired requsts is because if we only service a single one, I still see
> really awful interactivity;  an ls would take over 5 minutes to
> complete.  With the attached patch, the ls took about 7 seconds to
> complete.

It occured to me that this doesn't solve the problem of starving WRITE
I/O.  So, this patch fixes that as well, tested with a dd if=/dev/zero
of=outfile bs=1M count=1 oflag=sync while.

Cheers,
Jeff

diff --git a/block/deadline-iosched.c b/block/deadline-iosched.c
index b547cbc..62abb42 100644
--- a/block/deadline-iosched.c
+++ b/block/deadline-iosched.c
@@ -73,14 +73,48 @@ deadline_latter_request(struct request *rq)
 	return NULL;
 }
 
+/*
+ * deadline_check_fifo returns 0 if there are no expired requests on the fifo,
+ * 1 otherwise. Requires !list_empty(&dd->fifo_list[data_dir])
+ */
+static inline int deadline_check_fifo(struct deadline_data *dd, int ddir)
+{
+	struct request *rq = rq_entry_fifo(dd->fifo_list[ddir].next);
+
+	/*
+	 * rq is expired!
+	 */
+	if (time_after(jiffies, rq_fifo_time(rq)))
+		return 1;
+
+	return 0;
+}
+
+static void
+deadline_dispatch_expired(struct deadline_data *dd)
+{
+	int data_dir;
+
+	for (data_dir = 0 /* READ */; data_dir <= 1 /* WRITE */; data_dir++) {
+		while (!list_empty(&dd->fifo_list[data_dir]) &&
+		       deadline_check_fifo(dd, data_dir)) {
+			struct request *rq;
+			rq = rq_entry_fifo(dd->fifo_list[data_dir].next);
+			deadline_move_request(dd, rq);
+		}
+	}
+}
+
 static void
 deadline_add_rq_rb(struct deadline_data *dd, struct request *rq)
 {
 	struct rb_root *root = deadline_rb_root(dd, rq);
 	struct request *__alias;
 
-	while (unlikely(__alias = elv_rb_add(root, rq)))
+	while (unlikely(__alias = elv_rb_add(root, rq))) {
 		deadline_move_request(dd, __alias);
+		deadline_dispatch_expired(dd);
+	}
 }
 
 static inline void
@@ -222,23 +256,6 @@ deadline_move_request(struct deadline_data *dd, struct request *rq)
 }
 
 /*
- * deadline_check_fifo returns 0 if there are no expired requests on the fifo,
- * 1 otherwise. Requires !list_empty(&dd->fifo_list[data_dir])
- */
-static inline int deadline_check_fifo(struct deadline_data *dd, int ddir)
-{
-	struct request *rq = rq_entry_fifo(dd->fifo_list[ddir].next);
-
-	/*
-	 * rq is expired!
-	 */
-	if (time_after(jiffies, rq_fifo_time(rq)))
-		return 1;
-
-	return 0;
-}
-
-/*
  * deadline_dispatch_requests selects the best request according to
  * read/write expire, fifo_batch, etc
  */

Re: [PATCH] deadline-iosched: don't allow aliased requests to starve others

[Jeff Moyer]

Jeff Moyer <jmoyer@redhat.com> writes:

> Jeff Moyer <jmoyer@redhat.com> writes:
>
>> Hi,
>>
>> In running a test case that tries to trip up the kernel's AIO
>> implementation, we ran into a situation where no other I/O to the device
>> under test would be completed.  The test program spawned (in this case)
>> 100 threads, each of which performed the following in a loop:
>>
>> open file O_DIRECT
>> queue 1MB of read I/O from file using 16 iocbs
>> close file
>> repeat
>>
>> The program does NOT wait for the I/O to complete.  The file length is
>> only 4MB, meaning that you have 25 threads performing I/O on each of the
>> 4 1MB regions.
>>
>> Both deadline and cfq check for aliased requests in the sorted list of
>> I/Os, and when an alias is found, the request in the rb tree is moved to
>> the dispatch list.  So, what happens is that, with this workload, only
>> requests from this program are moved to the dispatch list, starving out
>> all other I/O.
>>
>> The attached patch fixes this problem by issuing all expired requests in
>> the aliased request handling code.  The reason I opted to issue all
>> expired requsts is because if we only service a single one, I still see
>> really awful interactivity;  an ls would take over 5 minutes to
>> complete.  With the attached patch, the ls took about 7 seconds to
>> complete.
>
> It occured to me that this doesn't solve the problem of starving WRITE
> I/O.  So, this patch fixes that as well, tested with a dd if=/dev/zero
> of=outfile bs=1M count=1 oflag=sync while.

Gah.  Forgot:

Signed-off-by: Jeff Moyer <jmoyer@redhat.com>