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

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-ID: <x49vd8iatee.fsf@segfault.boston.devel.redhat.com>
Date:	Wed, 14 Jul 2010 13:02:33 -0400
From:	Jeff Moyer <jmoyer@...hat.com>
To:	axboe@...nel.dk
Cc:	linux-kernel@...r.kernel.org
Subject: Re: [PATCH] deadline-iosched: don't allow aliased requests to starve others

Jeff Moyer <jmoyer@...hat.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
  */
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/