[PATCH] Fix array overflow in CFQ

[PATCH] Fix array overflow in CFQ

[Andi Kleen]

From: Andi Kleen <ak@linux.intel.com>

gcc 4.5 complains when compiling a recent rc with

linux/block/cfq-iosched.c: In function ‘cfq_dispatch_requests’:
linux/block/cfq-iosched.c:2156:3: warning: array subscript is above array bounds

and it is right:

 slice = group_slice * count /
                max_t(unsigned, cfqg->busy_queues_avg[cfqd->serving_prio],
                      cfq_group_busy_queues_wl(cfqd->serving_prio, cfqd, cfqg));

busy_queues_avg can be indexed by this enum

enum wl_prio_t {
        BE_WORKLOAD = 0,
        RT_WORKLOAD = 1,
        IDLE_WORKLOAD = 2,
};

in cfqd->serving_prio, but is only declared as

unsigned int busy_queues_avg[2];

which is clearly off by one. Fix this here.

Signed-off-by: Andi Kleen <ak@linux.intel.com>
---
 block/cfq-iosched.c |    2 +-
 1 files changed, 1 insertions(+), 1 deletions(-)

diff --git a/block/cfq-iosched.c b/block/cfq-iosched.c
index 9eba291..76741da 100644
--- a/block/cfq-iosched.c
+++ b/block/cfq-iosched.c
@@ -185,7 +185,7 @@ struct cfq_group {
 	int nr_cfqq;
 
 	/* Per group busy queus average. Useful for workload slice calc. */
-	unsigned int busy_queues_avg[2];
+	unsigned int busy_queues_avg[3];
 	/*
 	 * rr lists of queues with requests, onle rr for each priority class.
 	 * Counts are embedded in the cfq_rb_root
-- 
1.7.1

Re: [PATCH] Fix array overflow in CFQ

[Jens Axboe]

On 2010-10-19 11:10, Andi Kleen wrote:
> From: Andi Kleen <ak@linux.intel.com>
> 
> gcc 4.5 complains when compiling a recent rc with
> 
> linux/block/cfq-iosched.c: In function ‘cfq_dispatch_requests’:
> linux/block/cfq-iosched.c:2156:3: warning: array subscript is above array bounds
> 
> and it is right:
> 
>  slice = group_slice * count /
>                 max_t(unsigned, cfqg->busy_queues_avg[cfqd->serving_prio],
>                       cfq_group_busy_queues_wl(cfqd->serving_prio, cfqd, cfqg));
> 
> busy_queues_avg can be indexed by this enum
> 
> enum wl_prio_t {
>         BE_WORKLOAD = 0,
>         RT_WORKLOAD = 1,
>         IDLE_WORKLOAD = 2,
> };
> 
> in cfqd->serving_prio, but is only declared as
> 
> unsigned int busy_queues_avg[2];
> 
> which is clearly off by one. Fix this here.

Indeed, that is definitely buggy. ->service_trees[][] looks buggy, too.
WTF?!

diff --git a/block/cfq-iosched.c b/block/cfq-iosched.c
index 9eba291..8ce9f52 100644
--- a/block/cfq-iosched.c
+++ b/block/cfq-iosched.c
@@ -160,6 +160,7 @@ enum wl_prio_t {
 	BE_WORKLOAD = 0,
 	RT_WORKLOAD = 1,
 	IDLE_WORKLOAD = 2,
+	CFQ_PRIO_NR,
 };
 
 /*
@@ -168,7 +169,8 @@ enum wl_prio_t {
 enum wl_type_t {
 	ASYNC_WORKLOAD = 0,
 	SYNC_NOIDLE_WORKLOAD = 1,
-	SYNC_WORKLOAD = 2
+	SYNC_WORKLOAD = 2,
+	CFQ_TYPE_NR,
 };
 
 /* This is per cgroup per device grouping structure */
@@ -185,12 +187,12 @@ struct cfq_group {
 	int nr_cfqq;
 
 	/* Per group busy queus average. Useful for workload slice calc. */
-	unsigned int busy_queues_avg[2];
+	unsigned int busy_queues_avg[CFQ_PRIO_NR];
 	/*
 	 * rr lists of queues with requests, onle rr for each priority class.
 	 * Counts are embedded in the cfq_rb_root
 	 */
-	struct cfq_rb_root service_trees[2][3];
+	struct cfq_rb_root service_trees[CFQ_PRIO_NR][CFQ_TYPE_NR];
 	struct cfq_rb_root service_tree_idle;
 
 	unsigned long saved_workload_slice;

-- 
Jens Axboe

Re: [PATCH] Fix array overflow in CFQ

[Vivek Goyal]

On Tue, Oct 19, 2010 at 12:01:40PM +0200, Jens Axboe wrote:
> On 2010-10-19 11:10, Andi Kleen wrote:
> > From: Andi Kleen <ak@linux.intel.com>
> > 
> > gcc 4.5 complains when compiling a recent rc with
> > 
> > linux/block/cfq-iosched.c: In function ‘cfq_dispatch_requests’:
> > linux/block/cfq-iosched.c:2156:3: warning: array subscript is above array bounds
> > 
> > and it is right:
> > 
> >  slice = group_slice * count /
> >                 max_t(unsigned, cfqg->busy_queues_avg[cfqd->serving_prio],
> >                       cfq_group_busy_queues_wl(cfqd->serving_prio, cfqd, cfqg));
> > 
> > busy_queues_avg can be indexed by this enum
> > 
> > enum wl_prio_t {
> >         BE_WORKLOAD = 0,
> >         RT_WORKLOAD = 1,
> >         IDLE_WORKLOAD = 2,
> > };
> > 
> > in cfqd->serving_prio, but is only declared as
> > 
> > unsigned int busy_queues_avg[2];
> > 
> > which is clearly off by one. Fix this here.
> 
> Indeed, that is definitely buggy. ->service_trees[][] looks buggy, too.
> WTF?!

Hi Jens,

busy_queues_avg[] definitely looks buggy. Looks like I introduced this bug
while converting corrado's logic to group logic. I will fix it in a while.
Sorry for the goof up here.

->service_trees[][] is not buggy. We maintain workload subclassification
only for RT and BE class. For IDLE class, there are no ASYNC_WORKLOAD,
SYNC_NOIDLE_WORKLOAD or SYNC_WORKLOAD. All the type of idle queues
go onto a separate service tree, service_tree_idle.

Thanks
Vivek

> 
> diff --git a/block/cfq-iosched.c b/block/cfq-iosched.c
> index 9eba291..8ce9f52 100644
> --- a/block/cfq-iosched.c
> +++ b/block/cfq-iosched.c
> @@ -160,6 +160,7 @@ enum wl_prio_t {
>  	BE_WORKLOAD = 0,
>  	RT_WORKLOAD = 1,
>  	IDLE_WORKLOAD = 2,
> +	CFQ_PRIO_NR,
>  };
>  
>  /*
> @@ -168,7 +169,8 @@ enum wl_prio_t {
>  enum wl_type_t {
>  	ASYNC_WORKLOAD = 0,
>  	SYNC_NOIDLE_WORKLOAD = 1,
> -	SYNC_WORKLOAD = 2
> +	SYNC_WORKLOAD = 2,
> +	CFQ_TYPE_NR,
>  };
>  
>  /* This is per cgroup per device grouping structure */
> @@ -185,12 +187,12 @@ struct cfq_group {
>  	int nr_cfqq;
>  
>  	/* Per group busy queus average. Useful for workload slice calc. */
> -	unsigned int busy_queues_avg[2];
> +	unsigned int busy_queues_avg[CFQ_PRIO_NR];
>  	/*
>  	 * rr lists of queues with requests, onle rr for each priority class.
>  	 * Counts are embedded in the cfq_rb_root
>  	 */
> -	struct cfq_rb_root service_trees[2][3];
> +	struct cfq_rb_root service_trees[CFQ_PRIO_NR][CFQ_TYPE_NR];
>  	struct cfq_rb_root service_tree_idle;
>  
>  	unsigned long saved_workload_slice;
> 
> -- 
> Jens Axboe

Re: [PATCH] Fix array overflow in CFQ

[Jens Axboe]

On 2010-10-19 13:49, Vivek Goyal wrote:
> On Tue, Oct 19, 2010 at 12:01:40PM +0200, Jens Axboe wrote:
>> On 2010-10-19 11:10, Andi Kleen wrote:
>>> From: Andi Kleen <ak@linux.intel.com>
>>>
>>> gcc 4.5 complains when compiling a recent rc with
>>>
>>> linux/block/cfq-iosched.c: In function ‘cfq_dispatch_requests’:
>>> linux/block/cfq-iosched.c:2156:3: warning: array subscript is above array bounds
>>>
>>> and it is right:
>>>
>>>  slice = group_slice * count /
>>>                 max_t(unsigned, cfqg->busy_queues_avg[cfqd->serving_prio],
>>>                       cfq_group_busy_queues_wl(cfqd->serving_prio, cfqd, cfqg));
>>>
>>> busy_queues_avg can be indexed by this enum
>>>
>>> enum wl_prio_t {
>>>         BE_WORKLOAD = 0,
>>>         RT_WORKLOAD = 1,
>>>         IDLE_WORKLOAD = 2,
>>> };
>>>
>>> in cfqd->serving_prio, but is only declared as
>>>
>>> unsigned int busy_queues_avg[2];
>>>
>>> which is clearly off by one. Fix this here.
>>
>> Indeed, that is definitely buggy. ->service_trees[][] looks buggy, too.
>> WTF?!
> 
> Hi Jens,
> 
> busy_queues_avg[] definitely looks buggy. Looks like I introduced this bug
> while converting corrado's logic to group logic. I will fix it in a while.
> Sorry for the goof up here.
> 
> ->service_trees[][] is not buggy. We maintain workload subclassification
> only for RT and BE class. For IDLE class, there are no ASYNC_WORKLOAD,
> SYNC_NOIDLE_WORKLOAD or SYNC_WORKLOAD. All the type of idle queues
> go onto a separate service tree, service_tree_idle.

Right, that one looks convoluted (but correct). Ugh:

#define for_each_cfqg_st(cfqg, i, j, st) \
        for (i = 0; i <= IDLE_WORKLOAD; i++) \
                for (j = 0, st = i < IDLE_WORKLOAD ?  &cfqg->service_trees[i][j]\
                        : &cfqg->service_tree_idle; \
                        (i < IDLE_WORKLOAD && j <= SYNC_WORKLOAD) || \
                        (i == IDLE_WORKLOAD && j == 0); \
                        j++, st = i < IDLE_WORKLOAD ? \
                        &cfqg->service_trees[i][j]: NULL) \

-- 
Jens Axboe

Re: [PATCH] Fix array overflow in CFQ

[Vivek Goyal]

On Tue, Oct 19, 2010 at 07:49:33AM -0400, Vivek Goyal wrote:
> On Tue, Oct 19, 2010 at 12:01:40PM +0200, Jens Axboe wrote:
> > On 2010-10-19 11:10, Andi Kleen wrote:
> > > From: Andi Kleen <ak@linux.intel.com>
> > > 
> > > gcc 4.5 complains when compiling a recent rc with
> > > 
> > > linux/block/cfq-iosched.c: In function ‘cfq_dispatch_requests’:
> > > linux/block/cfq-iosched.c:2156:3: warning: array subscript is above array bounds
> > > 
> > > and it is right:
> > > 
> > >  slice = group_slice * count /
> > >                 max_t(unsigned, cfqg->busy_queues_avg[cfqd->serving_prio],
> > >                       cfq_group_busy_queues_wl(cfqd->serving_prio, cfqd, cfqg));
> > > 
> > > busy_queues_avg can be indexed by this enum
> > > 
> > > enum wl_prio_t {
> > >         BE_WORKLOAD = 0,
> > >         RT_WORKLOAD = 1,
> > >         IDLE_WORKLOAD = 2,
> > > };
> > > 
> > > in cfqd->serving_prio, but is only declared as
> > > 
> > > unsigned int busy_queues_avg[2];
> > > 
> > > which is clearly off by one. Fix this here.
> > 
> > Indeed, that is definitely buggy. ->service_trees[][] looks buggy, too.
> > WTF?!
> 
> Hi Jens,
> 
> busy_queues_avg[] definitely looks buggy. Looks like I introduced this bug
> while converting corrado's logic to group logic. I will fix it in a while.
> Sorry for the goof up here.

Jens,

Staring at the code for some more time, it looks like that busy_queues_avg[]
is also not buggy (at least at run time).

We maintain busy_queues_avg() only for RT and BE class. For IDLE class, we
expire the workload immediately after a jiffy.


        /* Choose next priority. RT > BE > IDLE */
        if (cfq_group_busy_queues_wl(RT_WORKLOAD, cfqd, cfqg))
                cfqd->serving_prio = RT_WORKLOAD;
        else if (cfq_group_busy_queues_wl(BE_WORKLOAD, cfqd, cfqg))
                cfqd->serving_prio = BE_WORKLOAD;
        else {
                cfqd->serving_prio = IDLE_WORKLOAD;
                cfqd->workload_expires = jiffies + 1;
                return;
        }

...
...
...

        slice = group_slice * count /
                max_t(unsigned, cfqg->busy_queues_avg[cfqd->serving_prio],
                      cfq_group_busy_queues_wl(cfqd->serving_prio, cfqd,
cfqg));

So for IDLE class, we return immediately from the function and never
execute cfqg->busy_queues_avg[IDLE].

Now to remove the gcc warning we can increase the size of busy_queues_avg[]
array but third field should always remain unused.

Thanks
Vivek

Re: [PATCH] Fix array overflow in CFQ

[Andi Kleen]

>          slice = group_slice * count /
>                  max_t(unsigned, cfqg->busy_queues_avg[cfqd->serving_prio],
>                        cfq_group_busy_queues_wl(cfqd->serving_prio, cfqd,
> cfqg));
>
> So for IDLE class, we return immediately from the function and never
> execute cfqg->busy_queues_avg[IDLE].

Hmm that's true. But why do you put this into a global variable anyways, 
can't it
just be a local?
> Now to remove the gcc warning we can increase the size of busy_queues_avg[]
> array but third field should always remain unused.
>
It's better to increase the field still I think.

-Andi

Re: [PATCH] Fix array overflow in CFQ

[Vivek Goyal]

On Tue, Oct 19, 2010 at 03:23:22PM +0200, Andi Kleen wrote:
> 
> >         slice = group_slice * count /
> >                 max_t(unsigned, cfqg->busy_queues_avg[cfqd->serving_prio],
> >                       cfq_group_busy_queues_wl(cfqd->serving_prio, cfqd,
> >cfqg));
> >
> >So for IDLE class, we return immediately from the function and never
> >execute cfqg->busy_queues_avg[IDLE].
> 
> Hmm that's true. But why do you put this into a global variable
> anyways, can't it
> just be a local?

We keep track of average number of queues per group per prio class. So it
can't be local as it historical data.

> >Now to remove the gcc warning we can increase the size of busy_queues_avg[]
> >array but third field should always remain unused.
> >
> It's better to increase the field still I think.

Agreed.

Jens, do you want me to regenerate your patch so that we increase the
size of ->busy_queues_avg[CFQ_PRIO_NR] but not ->service_trees[][].

Thanks
Vivek

Re: [PATCH] Fix array overflow in CFQ

[Jeff Moyer]

Vivek Goyal <vgoyal@redhat.com> writes:

> On Tue, Oct 19, 2010 at 03:23:22PM +0200, Andi Kleen wrote:
>> 
>> >         slice = group_slice * count /
>> >                 max_t(unsigned, cfqg->busy_queues_avg[cfqd->serving_prio],
>> >                       cfq_group_busy_queues_wl(cfqd->serving_prio, cfqd,
>> >cfqg));
>> >
>> >So for IDLE class, we return immediately from the function and never
>> >execute cfqg->busy_queues_avg[IDLE].
>> 
>> Hmm that's true. But why do you put this into a global variable
>> anyways, can't it
>> just be a local?
>
> We keep track of average number of queues per group per prio class. So it
> can't be local as it historical data.
>
>> >Now to remove the gcc warning we can increase the size of busy_queues_avg[]
>> >array but third field should always remain unused.
>> >
>> It's better to increase the field still I think.
>
> Agreed.
>
> Jens, do you want me to regenerate your patch so that we increase the
> size of ->busy_queues_avg[CFQ_PRIO_NR] but not ->service_trees[][].

Just be sure to put a huge comment in there so you don't confuse the
poor masses trying to make sense of the code.

Cheers,
Jeff

Re: [PATCH] Fix array overflow in CFQ

[Jeff Moyer]

Andi Kleen <ak@linux.intel.com> writes:

>> > Agreed.
>> >
>> > Jens, do you want me to regenerate your patch so that we increase the
>> > size of ->busy_queues_avg[CFQ_PRIO_NR] but not ->service_trees[][].
>> 
>> Just be sure to put a huge comment in there so you don't confuse the
>> poor masses trying to make sense of the code.
>
> Right now the code is confusing, with a correctly sized array it would
> be completely straight forward.

That's not entirely true.  You want a comment to state that the array
size is adjusted to ensure no accidental overflows, but in reality, that
third bucket is never used.

Cheers,
Jeff

Re: [PATCH] Fix array overflow in CFQ

[Andi Kleen]

> > Agreed.
> >
> > Jens, do you want me to regenerate your patch so that we increase the
> > size of ->busy_queues_avg[CFQ_PRIO_NR] but not ->service_trees[][].
> 
> Just be sure to put a huge comment in there so you don't confuse the
> poor masses trying to make sense of the code.

Right now the code is confusing, with a correctly sized array it would
be completely straight forward.

-Andi