We use different service trees for different priority classes.
This allows a simplification in the service tree insertion code, that no
longer has to consider priority while walking the tree.
Signed-off-by: Corrado Zoccolo <[email protected]>
---
block/cfq-iosched.c | 94 ++++++++++++++++++++++++++++++++++-----------------
1 files changed, 63 insertions(+), 31 deletions(-)
diff --git a/block/cfq-iosched.c b/block/cfq-iosched.c
index f866b17..a5a1786 100644
--- a/block/cfq-iosched.c
+++ b/block/cfq-iosched.c
@@ -121,6 +121,12 @@ struct cfq_queue {
struct cfq_io_context *cic;
};
+enum wl_prio_t {
+ IDLE_WL = -1,
+ BE_WL = 0,
+ RT_WL = 1
+};
+
/*
* Per block device queue structure
*/
@@ -130,7 +136,10 @@ struct cfq_data {
/*
* rr list of queues with requests and the count of them
*/
- struct cfq_rb_root service_tree;
+ struct cfq_rb_root service_trees[2];
+ struct cfq_rb_root service_tree_idle;
+
+ enum wl_prio_t serving_prio;
/*
* Each priority tree is sorted by next_request position. These
@@ -140,7 +149,6 @@ struct cfq_data {
struct rb_root prio_trees[CFQ_PRIO_LISTS];
unsigned int busy_queues;
- unsigned int busy_rt_queues;
unsigned int busy_queues_avg[2];
int rq_in_driver[2];
@@ -193,6 +201,13 @@ struct cfq_data {
unsigned long last_end_sync_rq;
};
+static struct cfq_rb_root *service_tree_for(enum wl_prio_t prio,
+ struct cfq_data *cfqd)
+{
+ return prio == IDLE_WL ? &cfqd->service_tree_idle :
+ &cfqd->service_trees[prio];
+}
+
enum cfqq_state_flags {
CFQ_CFQQ_FLAG_on_rr = 0, /* on round-robin busy list */
CFQ_CFQQ_FLAG_wait_request, /* waiting for a request */
@@ -237,6 +252,12 @@ CFQ_CFQQ_FNS(coop);
#define cfq_log(cfqd, fmt, args...) \
blk_add_trace_msg((cfqd)->queue, "cfq " fmt, ##args)
+static inline int cfq_busy_queues_wl(enum wl_prio_t wl, struct cfq_data *cfqd)
+{
+ return wl == IDLE_WL ? cfqd->service_tree_idle.count :
+ cfqd->service_trees[wl].count;
+}
+
static void cfq_dispatch_insert(struct request_queue *, struct request *);
static struct cfq_queue *cfq_get_queue(struct cfq_data *, bool,
struct io_context *, gfp_t);
@@ -315,8 +336,7 @@ cfq_get_avg_queues(struct cfq_data *cfqd, bool rt) {
unsigned min_q, max_q;
unsigned mult = cfq_hist_divisor - 1;
unsigned round = cfq_hist_divisor / 2;
- unsigned busy = rt ? cfqd->busy_rt_queues :
- (cfqd->busy_queues - cfqd->busy_rt_queues);
+ unsigned busy = cfq_busy_queues_wl(rt, cfqd);
min_q = min(cfqd->busy_queues_avg[rt], busy);
max_q = max(cfqd->busy_queues_avg[rt], busy);
cfqd->busy_queues_avg[rt] = (mult * max_q + min_q + round) /
@@ -520,7 +540,7 @@ static unsigned long cfq_slice_offset(struct cfq_data *cfqd,
}
/*
- * The cfqd->service_tree holds all pending cfq_queue's that have
+ * The cfqd->service_trees holds all pending cfq_queue's that have
* requests waiting to be processed. It is sorted in the order that
* we will service the queues.
*/
@@ -530,11 +550,12 @@ static void cfq_service_tree_add(struct cfq_data *cfqd, struct cfq_queue *cfqq,
struct rb_node **p, *parent;
struct cfq_queue *__cfqq;
unsigned long rb_key;
- struct cfq_rb_root *service_tree = &cfqd->service_tree;
+ struct cfq_rb_root *service_tree;
int left;
if (cfq_class_idle(cfqq)) {
rb_key = CFQ_IDLE_DELAY;
+ service_tree = &cfqd->service_tree_idle;
parent = rb_last(&service_tree->rb);
if (parent && parent != &cfqq->rb_node) {
__cfqq = rb_entry(parent, struct cfq_queue, rb_node);
@@ -542,6 +563,8 @@ static void cfq_service_tree_add(struct cfq_data *cfqd, struct cfq_queue *cfqq,
} else
rb_key += jiffies;
} else if (!add_front) {
+ enum wl_prio_t prio = cfq_class_rt(cfqq) ? RT_WL : BE_WL;
+ service_tree = service_tree_for(prio, cfqd);
/*
* Get our rb key offset. Subtract any residual slice
* value carried from last service. A negative resid
@@ -552,6 +575,8 @@ static void cfq_service_tree_add(struct cfq_data *cfqd, struct cfq_queue *cfqq,
rb_key -= cfqq->slice_resid;
cfqq->slice_resid = 0;
} else {
+ enum wl_prio_t prio = cfq_class_rt(cfqq) ? RT_WL : BE_WL;
+ service_tree = service_tree_for(prio, cfqd);
rb_key = -HZ;
__cfqq = cfq_rb_first(service_tree);
rb_key += __cfqq ? __cfqq->rb_key : jiffies;
@@ -561,7 +586,8 @@ static void cfq_service_tree_add(struct cfq_data *cfqd, struct cfq_queue *cfqq,
/*
* same position, nothing more to do
*/
- if (rb_key == cfqq->rb_key)
+ if (rb_key == cfqq->rb_key &&
+ cfqq->service_tree == service_tree)
return;
cfq_rb_erase(&cfqq->rb_node, cfqq->service_tree);
@@ -579,25 +605,14 @@ static void cfq_service_tree_add(struct cfq_data *cfqd, struct cfq_queue *cfqq,
__cfqq = rb_entry(parent, struct cfq_queue, rb_node);
/*
- * sort RT queues first, we always want to give
- * preference to them. IDLE queues goes to the back.
- * after that, sort on the next service time.
+ * sort by key, that represents service time.
*/
- if (cfq_class_rt(cfqq) > cfq_class_rt(__cfqq))
- n = &(*p)->rb_left;
- else if (cfq_class_rt(cfqq) < cfq_class_rt(__cfqq))
- n = &(*p)->rb_right;
- else if (cfq_class_idle(cfqq) < cfq_class_idle(__cfqq))
- n = &(*p)->rb_left;
- else if (cfq_class_idle(cfqq) > cfq_class_idle(__cfqq))
- n = &(*p)->rb_right;
- else if (time_before(rb_key, __cfqq->rb_key))
+ if (time_before(rb_key, __cfqq->rb_key))
n = &(*p)->rb_left;
- else
+ else {
n = &(*p)->rb_right;
-
- if (n == &(*p)->rb_right)
left = 0;
+ }
p = n;
}
@@ -696,8 +711,7 @@ static void cfq_add_cfqq_rr(struct cfq_data *cfqd, struct cfq_queue *cfqq)
BUG_ON(cfq_cfqq_on_rr(cfqq));
cfq_mark_cfqq_on_rr(cfqq);
cfqd->busy_queues++;
- if (cfq_class_rt(cfqq))
- cfqd->busy_rt_queues++;
+
cfq_resort_rr_list(cfqd, cfqq);
}
@@ -722,8 +736,6 @@ static void cfq_del_cfqq_rr(struct cfq_data *cfqd, struct cfq_queue *cfqq)
BUG_ON(!cfqd->busy_queues);
cfqd->busy_queues--;
- if (cfq_class_rt(cfqq))
- cfqd->busy_rt_queues--;
}
/*
@@ -977,10 +989,12 @@ static inline void cfq_slice_expired(struct cfq_data *cfqd, bool timed_out)
*/
static struct cfq_queue *cfq_get_next_queue(struct cfq_data *cfqd)
{
- if (RB_EMPTY_ROOT(&cfqd->service_tree.rb))
- return NULL;
+ struct cfq_rb_root *service_tree =
+ service_tree_for(cfqd->serving_prio, cfqd);
- return cfq_rb_first(&cfqd->service_tree);
+ if (RB_EMPTY_ROOT(&service_tree->rb))
+ return NULL;
+ return cfq_rb_first(service_tree);
}
/*
@@ -1098,6 +1112,10 @@ static struct cfq_queue *cfq_close_cooperator(struct cfq_data *cfqd,
if (cfq_cfqq_coop(cfqq))
return NULL;
+ /* we don't want to mix processes with different characteristics */
+ if (cfqq->service_tree != cur_cfqq->service_tree)
+ return NULL;
+
if (!probe)
cfq_mark_cfqq_coop(cfqq);
return cfqq;
@@ -1264,6 +1282,14 @@ static struct cfq_queue *cfq_select_queue(struct cfq_data *cfqd)
expire:
cfq_slice_expired(cfqd, 0);
new_queue:
+ if (!new_cfqq) {
+ if (cfq_busy_queues_wl(RT_WL, cfqd))
+ cfqd->serving_prio = RT_WL;
+ else if (cfq_busy_queues_wl(BE_WL, cfqd))
+ cfqd->serving_prio = BE_WL;
+ else
+ cfqd->serving_prio = IDLE_WL;
+ }
cfqq = cfq_set_active_queue(cfqd, new_cfqq);
keep_queue:
return cfqq;
@@ -1290,8 +1316,12 @@ static int cfq_forced_dispatch(struct cfq_data *cfqd)
{
struct cfq_queue *cfqq;
int dispatched = 0;
+ int i;
+ for (i = 0; i < 2; ++i)
+ while ((cfqq = cfq_rb_first(&cfqd->service_trees[i])) != NULL)
+ dispatched += __cfq_forced_dispatch_cfqq(cfqq);
- while ((cfqq = cfq_rb_first(&cfqd->service_tree)) != NULL)
+ while ((cfqq = cfq_rb_first(&cfqd->service_tree_idle)) != NULL)
dispatched += __cfq_forced_dispatch_cfqq(cfqq);
cfq_slice_expired(cfqd, 0);
@@ -2538,7 +2568,9 @@ static void *cfq_init_queue(struct request_queue *q)
if (!cfqd)
return NULL;
- cfqd->service_tree = CFQ_RB_ROOT;
+ for (i = 0; i < 2; ++i)
+ cfqd->service_trees[i] = CFQ_RB_ROOT;
+ cfqd->service_tree_idle = CFQ_RB_ROOT;
/*
* Not strictly needed (since RB_ROOT just clears the node and we
--
1.6.2.5
On Mon, Oct 19 2009, Corrado Zoccolo wrote:
> We use different service trees for different priority classes.
> This allows a simplification in the service tree insertion code, that no
> longer has to consider priority while walking the tree.
> +enum wl_prio_t {
> + IDLE_WL = -1,
> + BE_WL = 0,
> + RT_WL = 1
> +};
WL?
> +static struct cfq_rb_root *service_tree_for(enum wl_prio_t prio,
> + struct cfq_data *cfqd)
> +{
> + return prio == IDLE_WL ? &cfqd->service_tree_idle :
> + &cfqd->service_trees[prio];
> +}
Don't do it...
static struct cfq_rb_root *service_tree_for(enum wl_prio_t prio,
struct cfq_data *cfqd)
{
if (prio == IDLE_WL)
return &cfqd->service_tree_idle;
return &cfqd->service_trees[prio];
}
much cleaner. There are more of these in this patch.
Otherwise it looks sane, and I agree that making the insert cleaner here
is a good bonus.
--
Jens Axboe
On Tue, Oct 20, 2009 at 2:58 AM, Jens Axboe <[email protected]> wrote:
> On Mon, Oct 19 2009, Corrado Zoccolo wrote:
>> We use different service trees for different priority classes.
>> This allows a simplification in the service tree insertion code, that no
>> longer has to consider priority while walking the tree.
>
>> +enum wl_prio_t {
>> + IDLE_WL = -1,
>> + BE_WL = 0,
>> + RT_WL = 1
>> +};
>
> WL?
It stands for "workload". When defining all-caps constants, one has to
avoid possible clashes adding pre/suf-fixes.
Any suggestion for better naming?
>
>> +static struct cfq_rb_root *service_tree_for(enum wl_prio_t prio,
>> + struct cfq_data *cfqd)
>> +{
>> + return prio == IDLE_WL ? &cfqd->service_tree_idle :
>> + &cfqd->service_trees[prio];
>> +}
>
> Don't do it...
>
> static struct cfq_rb_root *service_tree_for(enum wl_prio_t prio,
> struct cfq_data *cfqd)
> {
> if (prio == IDLE_WL)
> return &cfqd->service_tree_idle;
>
> return &cfqd->service_trees[prio];
> }
>
> much cleaner. There are more of these in this patch.
I don't see much difference: my brain just translates the former in
the latter, and the former takes up less screen space.
But you are the maintainer, so I'll write it as you want.
> Otherwise it looks sane, and I agree that making the insert cleaner here
> is a good bonus.
Thanks
Corrado
>
> --
> Jens Axboe
>
>
On Tue, Oct 20 2009, Corrado Zoccolo wrote:
> On Tue, Oct 20, 2009 at 2:58 AM, Jens Axboe <[email protected]> wrote:
> > On Mon, Oct 19 2009, Corrado Zoccolo wrote:
> >> We use different service trees for different priority classes.
> >> This allows a simplification in the service tree insertion code, that no
> >> longer has to consider priority while walking the tree.
> >
> >> +enum wl_prio_t {
> >> + ? ? IDLE_WL = -1,
> >> + ? ? BE_WL = 0,
> >> + ? ? RT_WL = 1
> >> +};
> >
> > WL?
> It stands for "workload". When defining all-caps constants, one has to
> avoid possible clashes adding pre/suf-fixes.
> Any suggestion for better naming?
Nobody will guess that. Make variable/enum names as short as possible,
but not so short that their meaning are incomprehensible. Suggestion
would be to use IDLE_WORKLOAD etc.
--
Jens Axboe