Skip to contentSkip to conversation

Fix array overflow in CFQ

PATCH In review Andi Kleen 5 participants 10 messages Oct 19, 2010 – Oct 21, 2010 Block layer

lore
Share & tools
lore

Andi Kleen

author
#0 lore raw

PATCH 1/1 Fix array overflow in CFQ

From: Andi Kleen <[email protected]>

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.

---
 block/cfq-iosched.c |    2 +-
 1 files changed, 1 insertions(+), 1 deletions(-)
block/cfq-iosched.c +1 -1
index 9eba291..76741da 100644
@@ -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
Signature · 1 line
1.7.1
maintainer
#1 lore raw
Quoted 21 lines · Andi Kleen

From: Andi Kleen <[email protected]>

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,
};

Quoted 5 lines

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

block/cfq-iosched.c +5 -3
index 9eba291..8ce9f52 100644
@@ -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;
Signature · 1 line
Jens Axboe
#2 lore raw
Quoted 22 lines · Jens Axboe
Quoted 21 lines · Andi Kleen

From: Andi Kleen <[email protected]>

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,
};

Quoted 8 lines
Quoted 5 lines

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

Quoted 41 lines
block/cfq-iosched.c +5 -3
index 9eba291..8ce9f52 100644
@@ -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;
Signature · 2 lines
-- 
Jens Axboe
maintainer
#3 lore raw
Quoted 34 lines · Vivek Goyal
Quoted 22 lines · Jens Axboe
Quoted 21 lines · Andi Kleen

From: Andi Kleen <[email protected]>

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,
};

Quoted 8 lines
Quoted 5 lines

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,

Quoted 8 lines

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) \
Signature · 1 line
Jens Axboe
#4 lore raw
In reply to Vivek Goyal
Quoted 29 lines · Vivek Goyal
Quoted 28 lines · Jens Axboe
Quoted 26 lines · Andi Kleen

From: Andi Kleen <[email protected]>

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.

Quoted 8 lines
Quoted 2 lines

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

#5 lore raw
Quoted 8 lines
         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?

Quoted 3 lines

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

#6 lore raw
Quoted 6 lines · Andi Kleen
Quoted 6 lines
        slice = group_slice * count /
                max_t(unsigned, cfqg->busy_queues_avg[cfqd->serving_prio],
                      cfq_group_busy_queues_wl(cfqd->serving_prio, cfqd,

cfqg));

Quoted 6 lines
Quoted 2 lines

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.

Quoted 4 lines
Quoted 3 lines

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

#7 lore raw
Quoted 20 lines · Vivek Goyal
Quoted 6 lines · Andi Kleen
Quoted 6 lines
        slice = group_slice * count /
                max_t(unsigned, cfqg->busy_queues_avg[cfqd->serving_prio],
                      cfq_group_busy_queues_wl(cfqd->serving_prio, cfqd,

cfqg));

Quoted 6 lines
Quoted 2 lines

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.

Quoted 3 lines
Quoted 3 lines

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

Quoted 6 lines
Quoted 1 line

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

#8 lore raw
Quoted 7 lines
Quoted 4 lines

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

#9 lore raw
Quoted 10 lines · Andi Kleen
Quoted 7 lines
Quoted 4 lines

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