Fix array overflow in CFQ
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
@@ -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
Jens Axboe
maintainerQuoted 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 boundsand 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_avgcan be indexed by this enumenum
wl_prio_t{
BE_WORKLOAD= 0,
RT_WORKLOAD= 1,
IDLE_WORKLOAD= 2,
};
Quoted 5 lines
in
cfqd->serving_prio, but is only declared asunsigned 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
@@ -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
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 boundsand 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_avgcan be indexed by this enumenum
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 asunsigned 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@@ -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
Jens Axboe
maintainerQuoted 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 boundsand 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_avgcan be indexed by this enumenum
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 asunsigned 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_WORKLOADorSYNC_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
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 boundsand 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_avgcan be indexed by this enumenum
wl_prio_t{
BE_WORKLOAD= 0,
RT_WORKLOAD= 1,
IDLE_WORKLOAD= 2,
};in
cfqd->serving_prio, but is only declared asunsigned 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
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
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
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
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
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