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

--

[ message continues ]

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

--

[ message continues ]

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
--

[ message continues ]

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

--

[ message continues ]

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
--

[ message continues ]

Hmm that's true. But why do you put this into a global variable anyways, 
can't it
It's better to increase the field still I think.

-Andi

--

[ message continues ]

We keep track of average number of queues per group per prio class. So it

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
--

[ message continues ]

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
--

[ message continues ]

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

-Andi
--

[ message continues ]

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
--

[ message continues ]