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

[PATCH] cfq-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/cfq-iosched.c b/block/cfq-iosched.c
index 7982b83..0d8d2cd 100644
--- a/block/cfq-iosched.c
+++ b/block/cfq-iosched.c
@@ -417,6 +417,7 @@ static inline int cfqg_busy_async_queues(struct cfq_data *cfqd,
 }
 
 static void cfq_dispatch_insert(struct request_queue *, struct request *);
+static struct request *cfq_check_fifo(struct cfq_queue *cfqq);
 static struct cfq_queue *cfq_get_queue(struct cfq_data *, bool,
 				       struct io_context *, gfp_t);
 static struct cfq_io_context *cfq_cic_lookup(struct cfq_data *,
@@ -1394,10 +1395,22 @@ static void cfq_add_rq_rb(struct request *rq)
 
 	/*
 	 * looks a little odd, but the first insert might return an alias.
-	 * if that happens, put the alias on the dispatch list
+	 * If that happens, put the alias on the dispatch list, but don't
+	 * allow issuing of aliased requests to starve out the queue.
 	 */
-	while ((__alias = elv_rb_add(&cfqq->sort_list, rq)) != NULL)
+	while ((__alias = elv_rb_add(&cfqq->sort_list, rq)) != NULL) {
+		int fifo_checked = cfq_cfqq_fifo_expire(cfqq);
+		struct request *__rq;
+
 		cfq_dispatch_insert(cfqd->queue, __alias);
+		cfq_clear_cfqq_fifo_expire(cfqq);
+		while ((__rq = cfq_check_fifo(cfqq))) {
+			cfq_dispatch_insert(cfqd->queue, __rq);
+			cfq_clear_cfqq_fifo_expire(cfqq);
+		}
+		if (fifo_checked)
+			cfq_mark_cfqq_fifo_expire(cfqq);
+	}
 
 	if (!cfq_cfqq_on_rr(cfqq))
 		cfq_add_cfqq_rr(cfqd, cfqq);

Re: [PATCH] cfq-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.
>
> Comments, as always, are welcome.
>
> Cheers,
> Jeff

Forgot:

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

>
> diff --git a/block/cfq-iosched.c b/block/cfq-iosched.c
> index 7982b83..0d8d2cd 100644
> --- a/block/cfq-iosched.c
> +++ b/block/cfq-iosched.c
> @@ -417,6 +417,7 @@ static inline int cfqg_busy_async_queues(struct cfq_data *cfqd,
>  }
>  
>  static void cfq_dispatch_insert(struct request_queue *, struct request *);
> +static struct request *cfq_check_fifo(struct cfq_queue *cfqq);
>  static struct cfq_queue *cfq_get_queue(struct cfq_data *, bool,
>  				       struct io_context *, gfp_t);
>  static struct cfq_io_context *cfq_cic_lookup(struct cfq_data *,
> @@ -1394,10 +1395,22 @@ static void cfq_add_rq_rb(struct request *rq)
>  
>  	/*
>  	 * looks a little odd, but the first insert might return an alias.
> -	 * if that happens, put the alias on the dispatch list
> +	 * If that happens, put the alias on the dispatch list, but don't
> +	 * allow issuing of aliased requests to starve out the queue.
>  	 */
> -	while ((__alias = elv_rb_add(&cfqq->sort_list, rq)) != NULL)
> +	while ((__alias = elv_rb_add(&cfqq->sort_list, rq)) != NULL) {
> +		int fifo_checked = cfq_cfqq_fifo_expire(cfqq);
> +		struct request *__rq;
> +
>  		cfq_dispatch_insert(cfqd->queue, __alias);
> +		cfq_clear_cfqq_fifo_expire(cfqq);
> +		while ((__rq = cfq_check_fifo(cfqq))) {
> +			cfq_dispatch_insert(cfqd->queue, __rq);
> +			cfq_clear_cfqq_fifo_expire(cfqq);
> +		}
> +		if (fifo_checked)
> +			cfq_mark_cfqq_fifo_expire(cfqq);
> +	}
>  
>  	if (!cfq_cfqq_on_rr(cfqq))
>  		cfq_add_cfqq_rr(cfqd, cfqq);
> --
> To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
> the body of a message to majordomo@vger.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html
> Please read the FAQ at  http://www.tux.org/lkml/

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

[Vivek Goyal]

On Wed, Jul 14, 2010 at 11:09:48AM -0400, Jeff Moyer wrote:
> 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/cfq-iosched.c b/block/cfq-iosched.c
> index 7982b83..0d8d2cd 100644
> --- a/block/cfq-iosched.c
> +++ b/block/cfq-iosched.c
> @@ -417,6 +417,7 @@ static inline int cfqg_busy_async_queues(struct cfq_data *cfqd,
>  }
>  
>  static void cfq_dispatch_insert(struct request_queue *, struct request *);
> +static struct request *cfq_check_fifo(struct cfq_queue *cfqq);
>  static struct cfq_queue *cfq_get_queue(struct cfq_data *, bool,
>  				       struct io_context *, gfp_t);
>  static struct cfq_io_context *cfq_cic_lookup(struct cfq_data *,
> @@ -1394,10 +1395,22 @@ static void cfq_add_rq_rb(struct request *rq)
>  
>  	/*
>  	 * looks a little odd, but the first insert might return an alias.
> -	 * if that happens, put the alias on the dispatch list
> +	 * If that happens, put the alias on the dispatch list, but don't
> +	 * allow issuing of aliased requests to starve out the queue.
>  	 */
> -	while ((__alias = elv_rb_add(&cfqq->sort_list, rq)) != NULL)
> +	while ((__alias = elv_rb_add(&cfqq->sort_list, rq)) != NULL) {
> +		int fifo_checked = cfq_cfqq_fifo_expire(cfqq);
> +		struct request *__rq;
> +
>  		cfq_dispatch_insert(cfqd->queue, __alias);
> +		cfq_clear_cfqq_fifo_expire(cfqq);
> +		while ((__rq = cfq_check_fifo(cfqq))) {
> +			cfq_dispatch_insert(cfqd->queue, __rq);
> +			cfq_clear_cfqq_fifo_expire(cfqq);
> +		}
> +		if (fifo_checked)
> +			cfq_mark_cfqq_fifo_expire(cfqq);
> +	}

Jeff,

IIUC correctly upon receiving an alias, you are checking fifo of same
cfqq and not the fifo of other cfqqs which are blocked. So dispatching
more expired requests from the cfqq which is generating lots of aliases
can at best only worsen the problem. I am wondering how does this patch
help in dispatching requests from other cfqqs. 

Also for my education purposes I was curious to know that why can't
we keep aliased requests in the service tree. 

Thanks
Vivek

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

[Jeff Moyer]

Vivek Goyal <vgoyal@redhat.com> writes:

> On Wed, Jul 14, 2010 at 11:09:48AM -0400, Jeff Moyer wrote:
>> 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/cfq-iosched.c b/block/cfq-iosched.c
>> index 7982b83..0d8d2cd 100644
>> --- a/block/cfq-iosched.c
>> +++ b/block/cfq-iosched.c
>> @@ -417,6 +417,7 @@ static inline int cfqg_busy_async_queues(struct cfq_data *cfqd,
>>  }
>>  
>>  static void cfq_dispatch_insert(struct request_queue *, struct request *);
>> +static struct request *cfq_check_fifo(struct cfq_queue *cfqq);
>>  static struct cfq_queue *cfq_get_queue(struct cfq_data *, bool,
>>  				       struct io_context *, gfp_t);
>>  static struct cfq_io_context *cfq_cic_lookup(struct cfq_data *,
>> @@ -1394,10 +1395,22 @@ static void cfq_add_rq_rb(struct request *rq)
>>  
>>  	/*
>>  	 * looks a little odd, but the first insert might return an alias.
>> -	 * if that happens, put the alias on the dispatch list
>> +	 * If that happens, put the alias on the dispatch list, but don't
>> +	 * allow issuing of aliased requests to starve out the queue.
>>  	 */
>> -	while ((__alias = elv_rb_add(&cfqq->sort_list, rq)) != NULL)
>> +	while ((__alias = elv_rb_add(&cfqq->sort_list, rq)) != NULL) {
>> +		int fifo_checked = cfq_cfqq_fifo_expire(cfqq);
>> +		struct request *__rq;
>> +
>>  		cfq_dispatch_insert(cfqd->queue, __alias);
>> +		cfq_clear_cfqq_fifo_expire(cfqq);
>> +		while ((__rq = cfq_check_fifo(cfqq))) {
>> +			cfq_dispatch_insert(cfqd->queue, __rq);
>> +			cfq_clear_cfqq_fifo_expire(cfqq);
>> +		}
>> +		if (fifo_checked)
>> +			cfq_mark_cfqq_fifo_expire(cfqq);
>> +	}
>
> Jeff,
>
> IIUC correctly upon receiving an alias, you are checking fifo of same
> cfqq and not the fifo of other cfqqs which are blocked. So dispatching
> more expired requests from the cfqq which is generating lots of aliases
> can at best only worsen the problem. I am wondering how does this patch
> help in dispatching requests from other cfqqs. 

I think you're missing a key element, here.  Let's assume some harmless
process has the I/O scheduler.  Then, your pathological alias generator
process comes in and inserts a request into the queue.  If that request
is an alias, then it gets moved to the dispatch list immediately, even
though the cfqq for that process is not currently being served.

Now, I'm not sure why we ever get back into select_queue if the request
queue is always full of these aliases.  I didn't dig down that far, but
I did verify that progress was made in my simple reproducer.

> Also for my education purposes I was curious to know that why can't
> we keep aliased requests in the service tree. 

You know, I dug back through the logs, and I didn't find any mention of
that.  The anticipatory scheduler used to allow such aliases, but then
that support was removed in favor of a simpler approach.  So, the reason
may just be out of convenience.

Cheers,
Jeff

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

[Vivek Goyal]

On Fri, Jul 23, 2010 at 11:07:11AM -0400, Jeff Moyer wrote:

[..]
> >> diff --git a/block/cfq-iosched.c b/block/cfq-iosched.c
> >> index 7982b83..0d8d2cd 100644
> >> --- a/block/cfq-iosched.c
> >> +++ b/block/cfq-iosched.c
> >> @@ -417,6 +417,7 @@ static inline int cfqg_busy_async_queues(struct cfq_data *cfqd,
> >>  }
> >>  
> >>  static void cfq_dispatch_insert(struct request_queue *, struct request *);
> >> +static struct request *cfq_check_fifo(struct cfq_queue *cfqq);
> >>  static struct cfq_queue *cfq_get_queue(struct cfq_data *, bool,
> >>  				       struct io_context *, gfp_t);
> >>  static struct cfq_io_context *cfq_cic_lookup(struct cfq_data *,
> >> @@ -1394,10 +1395,22 @@ static void cfq_add_rq_rb(struct request *rq)
> >>  
> >>  	/*
> >>  	 * looks a little odd, but the first insert might return an alias.
> >> -	 * if that happens, put the alias on the dispatch list
> >> +	 * If that happens, put the alias on the dispatch list, but don't
> >> +	 * allow issuing of aliased requests to starve out the queue.
> >>  	 */
> >> -	while ((__alias = elv_rb_add(&cfqq->sort_list, rq)) != NULL)
> >> +	while ((__alias = elv_rb_add(&cfqq->sort_list, rq)) != NULL) {
> >> +		int fifo_checked = cfq_cfqq_fifo_expire(cfqq);
> >> +		struct request *__rq;
> >> +
> >>  		cfq_dispatch_insert(cfqd->queue, __alias);
> >> +		cfq_clear_cfqq_fifo_expire(cfqq);
> >> +		while ((__rq = cfq_check_fifo(cfqq))) {
> >> +			cfq_dispatch_insert(cfqd->queue, __rq);
> >> +			cfq_clear_cfqq_fifo_expire(cfqq);
> >> +		}
> >> +		if (fifo_checked)
> >> +			cfq_mark_cfqq_fifo_expire(cfqq);
> >> +	}
> >
> > Jeff,
> >
> > IIUC correctly upon receiving an alias, you are checking fifo of same
> > cfqq and not the fifo of other cfqqs which are blocked. So dispatching
> > more expired requests from the cfqq which is generating lots of aliases
> > can at best only worsen the problem. I am wondering how does this patch
> > help in dispatching requests from other cfqqs. 
> 
> I think you're missing a key element, here.  Let's assume some harmless
> process has the I/O scheduler.  Then, your pathological alias generator
> process comes in and inserts a request into the queue.  If that request
> is an alias, then it gets moved to the dispatch list immediately, even
> though the cfqq for that process is not currently being served.
> 
> Now, I'm not sure why we ever get back into select_queue if the request
> queue is always full of these aliases.  I didn't dig down that far, but
> I did verify that progress was made in my simple reproducer.

Jeff, I do understand the problem here. Just that I don't understand
how this patch is going to fix it for CFQ. How this patch will make
sure that requests from other starved queue are put onto dispatch queue.

Also I have been trying to reproduce the issue with 2.6.36-rc6 kernel
and have not been successful so far.

Thanks
Vivek

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

[Jens Axboe]

On 07/23/2010 05:07 PM, Jeff Moyer wrote:
> Vivek Goyal <vgoyal@redhat.com> writes:
>> Also for my education purposes I was curious to know that why can't
>> we keep aliased requests in the service tree. 
> 
> You know, I dug back through the logs, and I didn't find any mention of
> that.  The anticipatory scheduler used to allow such aliases, but then
> that support was removed in favor of a simpler approach.  So, the reason
> may just be out of convenience.

There's no technical reason why we can't do that, at least it'll work in
the rbtree.

-- 
Jens Axboe

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

[Heinz Diehl]

On 14.07.2010, Jeff Moyer wrote: 

> Comments, as always, are welcome.

This patch, applied to 2.6.35-rc6, increases desktop interactivity
_NOTICEABLY_ on my quadcore machine, and the machine stays rock-stable.
I have now tested this patch with the latest 2.6.35-rc kernels over 
1 week.

Unfortunately, I can't provide some testing results which makes this
statement more objective, but I'll do some synthetic testing in the next
days.

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

[Jens Axboe]

On 07/24/2010 10:04 AM, Heinz Diehl wrote:
> On 14.07.2010, Jeff Moyer wrote: 
> 
>> Comments, as always, are welcome.
> 
> This patch, applied to 2.6.35-rc6, increases desktop interactivity
> _NOTICEABLY_ on my quadcore machine, and the machine stays rock-stable.
> I have now tested this patch with the latest 2.6.35-rc kernels over 
> 1 week.
> 
> Unfortunately, I can't provide some testing results which makes this
> statement more objective, but I'll do some synthetic testing in the next
> days.

It is extremely unlikely that this patch will have any impact on
"normal" workloads. To even hit a code path where it would make a
difference, you would need to use O_DIRECT IO, otherwise you cannot have
aliases in the IO scheduler.

-- 
Jens Axboe

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

[Jeff Moyer]

Jens Axboe <axboe@kernel.dk> writes:

> On 07/24/2010 10:04 AM, Heinz Diehl wrote:
>> On 14.07.2010, Jeff Moyer wrote: 
>> 
>>> Comments, as always, are welcome.
>> 
>> This patch, applied to 2.6.35-rc6, increases desktop interactivity
>> _NOTICEABLY_ on my quadcore machine, and the machine stays rock-stable.
>> I have now tested this patch with the latest 2.6.35-rc kernels over 
>> 1 week.
>> 
>> Unfortunately, I can't provide some testing results which makes this
>> statement more objective, but I'll do some synthetic testing in the next
>> days.
>
> It is extremely unlikely that this patch will have any impact on
> "normal" workloads. To even hit a code path where it would make a
> difference, you would need to use O_DIRECT IO, otherwise you cannot have
> aliases in the IO scheduler.

I agree that it shouldn't help normal workloads at all.  I do think
there is one other case where you can get aliases: doing I/O both
through the file system and the underlying device.  However, that's
obviously a bad idea (and maybe open_bdev_exclusive will keep that from
happening?).

Cheers,
Jeff

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

[Jens Axboe]

On 2010-07-26 15:17, Jeff Moyer wrote:
> Jens Axboe <axboe@kernel.dk> writes:
> 
>> On 07/24/2010 10:04 AM, Heinz Diehl wrote:
>>> On 14.07.2010, Jeff Moyer wrote: 
>>>
>>>> Comments, as always, are welcome.
>>>
>>> This patch, applied to 2.6.35-rc6, increases desktop interactivity
>>> _NOTICEABLY_ on my quadcore machine, and the machine stays rock-stable.
>>> I have now tested this patch with the latest 2.6.35-rc kernels over 
>>> 1 week.
>>>
>>> Unfortunately, I can't provide some testing results which makes this
>>> statement more objective, but I'll do some synthetic testing in the next
>>> days.
>>
>> It is extremely unlikely that this patch will have any impact on
>> "normal" workloads. To even hit a code path where it would make a
>> difference, you would need to use O_DIRECT IO, otherwise you cannot have
>> aliases in the IO scheduler.
> 
> I agree that it shouldn't help normal workloads at all.  I do think
> there is one other case where you can get aliases: doing I/O both
> through the file system and the underlying device.  However, that's
> obviously a bad idea (and maybe open_bdev_exclusive will keep that from
> happening?).

That's correct, you could construct such a test case since you would
get page cache synchronization from different mappings. But again,
not something that the casual user would run into :-)

Exclusive opens only guard against each other, not against "normal"
opens.

-- 
Jens Axboe