Re: [RFC] [PATCH] cfq-iosched: add cfq group hierarchical schedulingsupport

[Gui Jianfeng]

Add Kamezawa

Vivek Goyal wrote:
> On Tue, Aug 31, 2010 at 08:29:20AM +0800, Gui Jianfeng wrote:
>> Vivek Goyal wrote:
>>> On Mon, Aug 30, 2010 at 02:50:40PM +0800, Gui Jianfeng wrote:
>>>> Hi All,
>>>>
>>>> This patch enables cfq group hierarchical scheduling.
>>>>
>>>> With this patch, you can create a cgroup directory deeper than level 1.
>>>> Now, I/O Bandwidth is distributed in a hierarchy way. For example:
>>>> We create cgroup directories as following(the number represents weight):
>>>>
>>>>             Root grp
>>>>            /       \
>>>>        grp_1(100) grp_2(400)
>>>>        /    \ 
>>>>   grp_3(200) grp_4(300)
>>>>
>>>> If grp_2 grp_3 and grp_4 are contending for I/O Bandwidth,
>>>> grp_2 will share 80% of total bandwidth.
>>>> For sub_groups, grp_3 shares 8%(20% * 40%), grp_4 shares 12%(20% * 60%)
>>>>
>>>> Design:
>>>>   o Each cfq group has its own group service tree. 
>>>>   o Each cfq group contains a "group schedule entity" (gse) that 
>>>>     schedules on parent cfq group's service tree.
>>>>   o Each cfq group contains a "queue schedule entity"(qse), it
>>>>     represents all cfqqs located on this cfq group. It schedules
>>>>     on this group's service tree. For the time being, root group
>>>>     qse's weight is 1000, and subgroup qse's weight is 500.
>>>>   o All gses and qse which belones to a same cfq group schedules
>>>>     on the same group service tree.
>>> Hi Gui,
>>>
>>> Thanks for the patch. I have few questions.
>>>
>>> - So how does the hierarchy look like, w.r.t root group. Something as
>>>   follows?
>>>
>>>
>>> 			root
>>> 		       / | \
>>> 		     q1  q2 G1
>>>
>>> Assume there are two processes doin IO in root group and q1 and q2 are
>>> cfqq queues for those processes and G1 is the cgroup created by user.
>>>
>>> If yes, then what algorithm do you use to do scheduling between q1, q2
>>> and G1? IOW, currently we have two algorithms operating in CFQ. One for
>>> cfqq and other for groups. Group algorithm does not use the logic of
>>> cfq_slice_offset().
>> Hi Vivek,
>>
>> This patch doesn't break the original sheduling logic. That is cfqg => st => cfqq.
>> If q1 and q2 in root group, I treat q1 and q2 bundle as a queue sched entity, and
>> it will schedule on root group service with G1, as following:
>>
>>                          root group
>>                         /         \
>>                     qse(q1,q2)    gse(G1)
>>
> 
> Ok. That's interesting. That raises another question that how hierarchy
> should look like. IOW, how queue and groups should be treated in
> hierarchy.
> 
> CFS cpu scheduler treats queues and group at the same level. That is as
> follows.
> 
> 			root
> 			/ | \
> 		       q1 q2 G1
> 
> In the past I had raised this question and Jens and corrado liked treating
> queues and group at same level.
> 
> Logically, q1, q2 and G1 are all children of root, so it makes sense to
> treat them at same level and not group q1 and q2 in to a single entity and
> group.

Hi Vivek,

IMO, this new approach keeps the original scheduling logic, and keep things
simple. And to me, this approach works for me. So i choose it.

> 
> One of the possible way forward could be this.
> 
> - Treat queue and group at same level (like CFS)
> 
> - Get rid of cfq_slice_offset() logic. That means without idling on, there
>   will be no ioprio difference between cfq queues. I think anyway as of 
>   today that logic helps in so little situations that I would not mind
>   getting rid of it. Just that Jens should agree to it.
> 
> - With this new scheme, it will break the existing semantics of root group
>   being at same level as child groups. To avoid that, we can probably
>   implement two modes (flat and hierarchical), something similar to what
>   memory cgroup controller has done. May be one tunable in root cgroup of
>   blkio "use_hierarchy".  By default everything will be in flat mode and
>   if user wants hiearchical control, he needs to set user_hierarchy in
>   root group.
> 
>   I think memory controller provides "use_hierarchy" tunable in each
>   cgroup. I am not sure why do we need it in each cgroup and not just
>   in root cgroup.

I think Kamezawa-san should be able to answer this question. :)

Thanks
Gui

> 
> Thanks
> Vivek 
> 
>> Thanks,
>> Gui
>>
>>> The reason being they are different because CFQ wanted to provide ioprio
>>> service differentiation on SSD where slice idle is effectively zero. But
>>> that slice_offset() logic is approximate at best and is not suitable
>>> for group scheduling.
>>>
>>> I have yet to go through the patches in detail, so thought will ask you
>>> that how have you handeled above.
>>>
>>> Vivek
>>>
>>>>   o cfq group allocates in a recursive manner, that means when a cfq 
>>>>     group needs to be allocated, the upper level cfq groups are also
>>>>     allocated.
>>>>   o When a cfq group served, not only charge this cfq group but also
>>>>     charge its ancestors.
>>>>  block/cfq-iosched.c |  477 +++++++++++++++++++++++++++++++++++++-------------
>>>>  2 files changed, 353 insertions(+), 128 deletions(-)
>>>>
>>>> diff --git a/block/blk-cgroup.c b/block/blk-cgroup.c
>>>> index 2fef1ef..aa06cb3 100644
>>>> --- a/block/blk-cgroup.c
>>>> +++ b/block/blk-cgroup.c
>>>> @@ -964,10 +964,6 @@ blkiocg_create(struct cgroup_subsys *subsys, struct cgroup *cgroup)
>>>>  		goto done;
>>>>  	}
>>>>  
>>>> -	/* Currently we do not support hierarchy deeper than two level (0,1) */
>>>> -	if (parent != cgroup->top_cgroup)
>>>> -		return ERR_PTR(-EPERM);
>>>> -
>>>>  	blkcg = kzalloc(sizeof(*blkcg), GFP_KERNEL);
>>>>  	if (!blkcg)
>>>>  		return ERR_PTR(-ENOMEM);
>>>> diff --git a/block/cfq-iosched.c b/block/cfq-iosched.c
>>>> index f65c6f0..4660d89 100644
>>>> --- a/block/cfq-iosched.c
>>>> +++ b/block/cfq-iosched.c
>>>> @@ -73,7 +73,8 @@ static DEFINE_IDA(cic_index_ida);
>>>>  #define cfq_class_rt(cfqq)	((cfqq)->ioprio_class == IOPRIO_CLASS_RT)
>>>>  
>>>>  #define sample_valid(samples)	((samples) > 80)
>>>> -#define rb_entry_cfqg(node)	rb_entry((node), struct cfq_group, rb_node)
>>>> +#define rb_entry_se(node)	\
>>>> +	rb_entry((node), struct io_sched_entity, rb_node)
>>>>  
>>>>  /*
>>>>   * Most of our rbtree usage is for sorting with min extraction, so
>>>> @@ -171,19 +172,40 @@ enum wl_type_t {
>>>>  	SYNC_WORKLOAD = 2
>>>>  };
>>>>  
>>>> -/* This is per cgroup per device grouping structure */
>>>> -struct cfq_group {
>>>> +/* 
>>>> + * This's the schedule entity which is scheduled on group service tree.
>>>> + * It represents shedule structure of a cfq group, or a bundle of cfq
>>>> + * queues that locate in a cfq group.
>>>> + */
>>>> +struct io_sched_entity {
>>>> +	struct cfq_rb_root *st;
>>>> +
>>>>  	/* group service_tree member */
>>>>  	struct rb_node rb_node;
>>>> -
>>>> -	/* group service_tree key */
>>>>  	u64 vdisktime;
>>>>  	unsigned int weight;
>>>>  	bool on_st;
>>>> +	bool is_group_se;
>>>> +	struct io_sched_entity *parent;
>>>> +};
>>>> +
>>>> +/* This is per cgroup per device grouping structure */
>>>> +struct cfq_group {
>>>> +	/* cfq group sched entity */
>>>> +	struct io_sched_entity group_se;
>>>> +
>>>> +	/* sched entity for cfqqs */
>>>> +	struct io_sched_entity queue_se;
>>>> +
>>>> +	/* Service tree for cfq_groups and cfqqs set*/
>>>> +	struct cfq_rb_root grp_service_tree;
>>>>  
>>>>  	/* number of cfqq currently on this group */
>>>>  	int nr_cfqq;
>>>>  
>>>> +	/* number of sub cfq groups */
>>>> +	int nr_subgp;
>>>> +
>>>>  	/* Per group busy queus average. Useful for workload slice calc. */
>>>>  	unsigned int busy_queues_avg[2];
>>>>  	/*
>>>> @@ -210,8 +232,6 @@ struct cfq_group {
>>>>   */
>>>>  struct cfq_data {
>>>>  	struct request_queue *queue;
>>>> -	/* Root service tree for cfq_groups */
>>>> -	struct cfq_rb_root grp_service_tree;
>>>>  	struct cfq_group root_group;
>>>>  
>>>>  	/*
>>>> @@ -399,6 +419,22 @@ static inline bool iops_mode(struct cfq_data *cfqd)
>>>>  		return false;
>>>>  }
>>>>  
>>>> +static inline struct cfq_group *cfqg_of_gse(struct io_sched_entity *se)
>>>> +{
>>>> +	if (se->is_group_se)
>>>> +		return container_of(se, struct cfq_group, group_se);
>>>> +	else
>>>> +		return NULL;
>>>> +}
>>>> +
>>>> +static inline struct cfq_group *cfqg_of_qse(struct io_sched_entity *se)
>>>> +{
>>>> +	if (!se->is_group_se)
>>>> +		return container_of(se, struct cfq_group, queue_se);
>>>> +	else
>>>> +		return NULL;
>>>> +}
>>>> +
>>>>  static inline enum wl_prio_t cfqq_prio(struct cfq_queue *cfqq)
>>>>  {
>>>>  	if (cfq_class_idle(cfqq))
>>>> @@ -522,12 +558,13 @@ cfq_prio_to_slice(struct cfq_data *cfqd, struct cfq_queue *cfqq)
>>>>  	return cfq_prio_slice(cfqd, cfq_cfqq_sync(cfqq), cfqq->ioprio);
>>>>  }
>>>>  
>>>> -static inline u64 cfq_scale_slice(unsigned long delta, struct cfq_group *cfqg)
>>>> +static inline u64 cfq_scale_slice(unsigned long delta,
>>>> +				  struct io_sched_entity *se)
>>>>  {
>>>>  	u64 d = delta << CFQ_SERVICE_SHIFT;
>>>>  
>>>>  	d = d * BLKIO_WEIGHT_DEFAULT;
>>>> -	do_div(d, cfqg->weight);
>>>> +	do_div(d, se->weight);
>>>>  	return d;
>>>>  }
>>>>  
>>>> @@ -552,16 +589,16 @@ static inline u64 min_vdisktime(u64 min_vdisktime, u64 vdisktime)
>>>>  static void update_min_vdisktime(struct cfq_rb_root *st)
>>>>  {
>>>>  	u64 vdisktime = st->min_vdisktime;
>>>> -	struct cfq_group *cfqg;
>>>> +	struct io_sched_entity *se;
>>>>  
>>>>  	if (st->active) {
>>>> -		cfqg = rb_entry_cfqg(st->active);
>>>> -		vdisktime = cfqg->vdisktime;
>>>> +		se = rb_entry_se(st->active);
>>>> +		vdisktime = se->vdisktime;
>>>>  	}
>>>>  
>>>>  	if (st->left) {
>>>> -		cfqg = rb_entry_cfqg(st->left);
>>>> -		vdisktime = min_vdisktime(vdisktime, cfqg->vdisktime);
>>>> +		se = rb_entry_se(st->left);
>>>> +		vdisktime = min_vdisktime(vdisktime, se->vdisktime);
>>>>  	}
>>>>  
>>>>  	st->min_vdisktime = max_vdisktime(st->min_vdisktime, vdisktime);
>>>> @@ -591,9 +628,10 @@ static inline unsigned cfq_group_get_avg_queues(struct cfq_data *cfqd,
>>>>  static inline unsigned
>>>>  cfq_group_slice(struct cfq_data *cfqd, struct cfq_group *cfqg)
>>>>  {
>>>> -	struct cfq_rb_root *st = &cfqd->grp_service_tree;
>>>> +	struct io_sched_entity *gse = &cfqg->queue_se;
>>>> +	struct cfq_rb_root *st = gse->st;
>>>>  
>>>> -	return cfq_target_latency * cfqg->weight / st->total_weight;
>>>> +	return cfq_target_latency * gse->weight / st->total_weight;
>>>>  }
>>>>  
>>>>  static inline void
>>>> @@ -756,13 +794,13 @@ static struct cfq_queue *cfq_rb_first(struct cfq_rb_root *root)
>>>>  	return NULL;
>>>>  }
>>>>  
>>>> -static struct cfq_group *cfq_rb_first_group(struct cfq_rb_root *root)
>>>> +static struct io_sched_entity *cfq_rb_first_se(struct cfq_rb_root *root)
>>>>  {
>>>>  	if (!root->left)
>>>>  		root->left = rb_first(&root->rb);
>>>>  
>>>>  	if (root->left)
>>>> -		return rb_entry_cfqg(root->left);
>>>> +		return rb_entry_se(root->left);
>>>>  
>>>>  	return NULL;
>>>>  }
>>>> @@ -819,25 +857,25 @@ static unsigned long cfq_slice_offset(struct cfq_data *cfqd,
>>>>  }
>>>>  
>>>>  static inline s64
>>>> -cfqg_key(struct cfq_rb_root *st, struct cfq_group *cfqg)
>>>> +se_key(struct cfq_rb_root *st, struct io_sched_entity *se)
>>>>  {
>>>> -	return cfqg->vdisktime - st->min_vdisktime;
>>>> +	return se->vdisktime - st->min_vdisktime;
>>>>  }
>>>>  
>>>>  static void
>>>> -__cfq_group_service_tree_add(struct cfq_rb_root *st, struct cfq_group *cfqg)
>>>> +__io_sched_entity_add(struct cfq_rb_root *st, struct io_sched_entity *se)
>>>>  {
>>>>  	struct rb_node **node = &st->rb.rb_node;
>>>>  	struct rb_node *parent = NULL;
>>>> -	struct cfq_group *__cfqg;
>>>> -	s64 key = cfqg_key(st, cfqg);
>>>> +	struct io_sched_entity *__se;
>>>> +	s64 key = se_key(st, se);
>>>>  	int left = 1;
>>>>  
>>>>  	while (*node != NULL) {
>>>>  		parent = *node;
>>>> -		__cfqg = rb_entry_cfqg(parent);
>>>> +		__se = rb_entry_se(parent);
>>>>  
>>>> -		if (key < cfqg_key(st, __cfqg))
>>>> +		if (key < se_key(st, __se))
>>>>  			node = &parent->rb_left;
>>>>  		else {
>>>>  			node = &parent->rb_right;
>>>> @@ -846,47 +884,80 @@ __cfq_group_service_tree_add(struct cfq_rb_root *st, struct cfq_group *cfqg)
>>>>  	}
>>>>  
>>>>  	if (left)
>>>> -		st->left = &cfqg->rb_node;
>>>> +		st->left = &se->rb_node;
>>>>  
>>>> -	rb_link_node(&cfqg->rb_node, parent, node);
>>>> -	rb_insert_color(&cfqg->rb_node, &st->rb);
>>>> +	rb_link_node(&se->rb_node, parent, node);
>>>> +	rb_insert_color(&se->rb_node, &st->rb);
>>>>  }
>>>>  
>>>> -static void
>>>> -cfq_group_service_tree_add(struct cfq_data *cfqd, struct cfq_group *cfqg)
>>>> +static void io_sched_entity_add(struct cfq_rb_root *st,
>>>> +				struct io_sched_entity *se)
>>>>  {
>>>> -	struct cfq_rb_root *st = &cfqd->grp_service_tree;
>>>> -	struct cfq_group *__cfqg;
>>>>  	struct rb_node *n;
>>>> +	struct io_sched_entity *__se;
>>>>  
>>>> -	cfqg->nr_cfqq++;
>>>> -	if (cfqg->on_st)
>>>> -		return;
>>>>  
>>>> +	if (se->on_st)
>>>> +		return;
>>>>  	/*
>>>>  	 * Currently put the group at the end. Later implement something
>>>>  	 * so that groups get lesser vtime based on their weights, so that
>>>>  	 * if group does not loose all if it was not continously backlogged.
>>>>  	 */
>>>> -	n = rb_last(&st->rb);
>>>> +	n = rb_last(&se->st->rb);
>>>>  	if (n) {
>>>> -		__cfqg = rb_entry_cfqg(n);
>>>> -		cfqg->vdisktime = __cfqg->vdisktime + CFQ_IDLE_DELAY;
>>>> +		__se = rb_entry_se(n);
>>>> +		se->vdisktime = __se->vdisktime + CFQ_IDLE_DELAY;
>>>>  	} else
>>>> -		cfqg->vdisktime = st->min_vdisktime;
>>>> +		se->vdisktime = st->min_vdisktime;
>>>>  
>>>> -	__cfq_group_service_tree_add(st, cfqg);
>>>> -	cfqg->on_st = true;
>>>> -	st->total_weight += cfqg->weight;
>>>> +	__io_sched_entity_add(se->st, se);
>>>> +	se->on_st = true;
>>>> +	st->total_weight += se->weight;
>>>> +}
>>>> +
>>>> +static void
>>>> +cfq_group_service_tree_add(struct cfq_data *cfqd, struct cfq_group *cfqg)
>>>> +{
>>>> +	struct io_sched_entity *gse = &cfqg->group_se;
>>>> +	struct io_sched_entity *qse = &cfqg->queue_se;
>>>> +	struct cfq_group *__cfqg;
>>>> +
>>>> +	cfqg->nr_cfqq++;
>>>> +
>>>> +	io_sched_entity_add(qse->st, qse);
>>>> +
>>>> +	while (gse && gse->parent) {
>>>> +		if (gse->on_st)
>>>> +			return;
>>>> +		io_sched_entity_add(gse->st, gse);
>>>> +		gse = gse->parent;
>>>> +		__cfqg = cfqg_of_gse(gse);
>>>> +		__cfqg->nr_subgp++;
>>>> +	}
>>>> +}
>>>> +
>>>> +static void io_sched_entity_del(struct io_sched_entity *se)
>>>> +{
>>>> +	if (!RB_EMPTY_NODE(&se->rb_node))
>>>> +		cfq_rb_erase(&se->rb_node, se->st);
>>>> +
>>>> +	se->on_st = false;
>>>> +	se->st->total_weight -= se->weight;
>>>>  }
>>>>  
>>>>  static void
>>>>  cfq_group_service_tree_del(struct cfq_data *cfqd, struct cfq_group *cfqg)
>>>>  {
>>>> -	struct cfq_rb_root *st = &cfqd->grp_service_tree;
>>>> +	struct io_sched_entity *gse = &cfqg->group_se;
>>>> +	struct io_sched_entity *qse = &cfqg->queue_se;
>>>> +	struct cfq_group *__cfqg, *p_cfqg;
>>>> +
>>>> +	if (gse->st && gse->st->active == &gse->rb_node)
>>>> +		gse->st->active = NULL;
>>>>  
>>>> -	if (st->active == &cfqg->rb_node)
>>>> -		st->active = NULL;
>>>> +	if (qse->st && qse->st->active == &qse->rb_node)
>>>> +		qse->st->active = NULL;
>>>>  
>>>>  	BUG_ON(cfqg->nr_cfqq < 1);
>>>>  	cfqg->nr_cfqq--;
>>>> @@ -895,13 +966,25 @@ cfq_group_service_tree_del(struct cfq_data *cfqd, struct cfq_group *cfqg)
>>>>  	if (cfqg->nr_cfqq)
>>>>  		return;
>>>>  
>>>> -	cfq_log_cfqg(cfqd, cfqg, "del_from_rr group");
>>>> -	cfqg->on_st = false;
>>>> -	st->total_weight -= cfqg->weight;
>>>> -	if (!RB_EMPTY_NODE(&cfqg->rb_node))
>>>> -		cfq_rb_erase(&cfqg->rb_node, st);
>>>> -	cfqg->saved_workload_slice = 0;
>>>> -	cfq_blkiocg_update_dequeue_stats(&cfqg->blkg, 1);
>>>> +	/* dequeue queue se from group */
>>>> +	io_sched_entity_del(qse);
>>>> +
>>>> +	if (cfqg->nr_subgp)
>>>> +		return;
>>>> +
>>>> +	/* prevent from dequeuing root group */
>>>> +	while (gse && gse->parent) {
>>>> +		__cfqg = cfqg_of_gse(gse);
>>>> +		p_cfqg = cfqg_of_gse(gse->parent);
>>>> +		io_sched_entity_del(gse);
>>>> +		cfq_blkiocg_update_dequeue_stats(&__cfqg->blkg, 1);
>>>> +		cfq_log_cfqg(cfqd, __cfqg, "del_from_rr group");
>>>> +		__cfqg->saved_workload_slice = 0;
>>>> +		gse = gse->parent;
>>>> +		p_cfqg->nr_subgp--;
>>>> +		if (p_cfqg->nr_cfqq || p_cfqg->nr_subgp)
>>>> +			return;
>>>> +	}
>>>>  }
>>>>  
>>>>  static inline unsigned int cfq_cfqq_slice_usage(struct cfq_queue *cfqq)
>>>> @@ -933,7 +1016,8 @@ static inline unsigned int cfq_cfqq_slice_usage(struct cfq_queue *cfqq)
>>>>  static void cfq_group_served(struct cfq_data *cfqd, struct cfq_group *cfqg,
>>>>  				struct cfq_queue *cfqq)
>>>>  {
>>>> -	struct cfq_rb_root *st = &cfqd->grp_service_tree;
>>>> +	struct io_sched_entity *gse = &cfqg->group_se;
>>>> +	struct io_sched_entity *qse = &cfqg->queue_se;
>>>>  	unsigned int used_sl, charge;
>>>>  	int nr_sync = cfqg->nr_cfqq - cfqg_busy_async_queues(cfqd, cfqg)
>>>>  			- cfqg->service_tree_idle.count;
>>>> @@ -946,10 +1030,25 @@ static void cfq_group_served(struct cfq_data *cfqd, struct cfq_group *cfqg,
>>>>  	else if (!cfq_cfqq_sync(cfqq) && !nr_sync)
>>>>  		charge = cfqq->allocated_slice;
>>>>  
>>>> -	/* Can't update vdisktime while group is on service tree */
>>>> -	cfq_rb_erase(&cfqg->rb_node, st);
>>>> -	cfqg->vdisktime += cfq_scale_slice(charge, cfqg);
>>>> -	__cfq_group_service_tree_add(st, cfqg);
>>>> +	/*
>>>> +	 *  update queue se's vdisktime.
>>>> +	 *  Can't update vdisktime while group is on service tree.
>>>> +	 */
>>>> +
>>>> +	cfq_rb_erase(&qse->rb_node, qse->st);
>>>> +	qse->vdisktime += cfq_scale_slice(charge, qse);
>>>> +	__io_sched_entity_add(qse->st, qse);
>>>> +	if (&qse->rb_node == qse->st->active)
>>>> +		qse->st->active = NULL;
>>>> +
>>>> +	while (gse && gse->parent) {
>>>> +		cfq_rb_erase(&gse->rb_node, gse->st);
>>>> +		gse->vdisktime += cfq_scale_slice(charge, gse);
>>>> +		__io_sched_entity_add(gse->st, gse);
>>>> +		if (&gse->rb_node == gse->st->active)
>>>> +			gse->st->active = NULL;
>>>> +		gse = gse->parent;
>>>> +	}
>>>>  
>>>>  	/* This group is being expired. Save the context */
>>>>  	if (time_after(cfqd->workload_expires, jiffies)) {
>>>> @@ -960,8 +1059,9 @@ static void cfq_group_served(struct cfq_data *cfqd, struct cfq_group *cfqg,
>>>>  	} else
>>>>  		cfqg->saved_workload_slice = 0;
>>>>  
>>>> -	cfq_log_cfqg(cfqd, cfqg, "served: vt=%llu min_vt=%llu", cfqg->vdisktime,
>>>> -					st->min_vdisktime);
>>>> +	cfq_log_cfqg(cfqd, cfqg, "served: vt=%llu min_vt=%llu", gse->vdisktime,
>>>> +		     gse->st->min_vdisktime);
>>>> +
>>>>  	cfq_log_cfqq(cfqq->cfqd, cfqq, "sl_used=%u disp=%u charge=%u iops=%u"
>>>>  			" sect=%u", used_sl, cfqq->slice_dispatch, charge,
>>>>  			iops_mode(cfqd), cfqq->nr_sectors);
>>>> @@ -977,39 +1077,84 @@ static inline struct cfq_group *cfqg_of_blkg(struct blkio_group *blkg)
>>>>  	return NULL;
>>>>  }
>>>>  
>>>> +static void cfq_put_cfqg(struct cfq_group *cfqg)
>>>> +{
>>>> +	struct cfq_rb_root *st;
>>>> +	int i, j;
>>>> +	struct io_sched_entity *gse;
>>>> +	struct cfq_group *p_cfqg;
>>>> +
>>>> +	BUG_ON(atomic_read(&cfqg->ref) <= 0);
>>>> +	if (!atomic_dec_and_test(&cfqg->ref))
>>>> +		return;
>>>> +	for_each_cfqg_st(cfqg, i, j, st)
>>>> +		BUG_ON(!RB_EMPTY_ROOT(&st->rb) || st->active != NULL);
>>>> +
>>>> +	gse = &cfqg->group_se;
>>>> +	if (gse->parent) {
>>>> +		p_cfqg = cfqg_of_gse(gse->parent);
>>>> +		/* Drop the reference taken by children */
>>>> +		atomic_dec(&p_cfqg->ref);
>>>> +	}
>>>> +
>>>> +	kfree(cfqg);
>>>> +}
>>>> +
>>>> +static void cfq_destroy_cfqg(struct cfq_data *cfqd, struct cfq_group *cfqg)
>>>> +{
>>>> +	/* Something wrong if we are trying to remove same group twice */
>>>> +	BUG_ON(hlist_unhashed(&cfqg->cfqd_node));
>>>> +
>>>> +	hlist_del_init(&cfqg->cfqd_node);
>>>> +
>>>> +	/*
>>>> +	 * Put the reference taken at the time of creation so that when all
>>>> +	 * queues are gone, group can be destroyed.
>>>> +	 */
>>>> +	cfq_put_cfqg(cfqg);
>>>> +}
>>>> +
>>>>  void
>>>>  cfq_update_blkio_group_weight(struct blkio_group *blkg, unsigned int weight)
>>>>  {
>>>> -	cfqg_of_blkg(blkg)->weight = weight;
>>>> +	struct cfq_group *cfqg;
>>>> +	struct io_sched_entity *gse;
>>>> +
>>>> +	cfqg = cfqg_of_blkg(blkg);
>>>> +	gse = &cfqg->group_se;
>>>> +	gse->weight = weight;
>>>>  }
>>>>  
>>>> -static struct cfq_group *
>>>> -cfq_find_alloc_cfqg(struct cfq_data *cfqd, struct cgroup *cgroup, int create)
>>>> +static void init_group_queue_entity(struct blkio_cgroup *blkcg,
>>>> +				   struct cfq_group *cfqg)
>>>> +{
>>>> +	struct io_sched_entity *gse = &cfqg->group_se;
>>>> +	struct io_sched_entity *qse = &cfqg->queue_se;
>>>> +
>>>> +	gse->weight = blkcg_get_weight(blkcg, cfqg->blkg.dev);
>>>> +	RB_CLEAR_NODE(&gse->rb_node);
>>>> +	gse->is_group_se = true;
>>>> +	gse->on_st = false;
>>>> +
>>>> +	/* Set to 500 for the time being */
>>>> +	qse->weight = 500;
>>>> +	RB_CLEAR_NODE(&qse->rb_node);
>>>> +	qse->is_group_se = false;
>>>> +	qse->on_st = false;
>>>> +}
>>>> +
>>>> +static void init_cfqg(struct cfq_data *cfqd, struct blkio_cgroup *blkcg,
>>>> +		      struct cfq_group *cfqg)
>>>>  {
>>>> -	struct blkio_cgroup *blkcg = cgroup_to_blkio_cgroup(cgroup);
>>>> -	struct cfq_group *cfqg = NULL;
>>>> -	void *key = cfqd;
>>>>  	int i, j;
>>>>  	struct cfq_rb_root *st;
>>>> -	struct backing_dev_info *bdi = &cfqd->queue->backing_dev_info;
>>>>  	unsigned int major, minor;
>>>> +	struct backing_dev_info *bdi = &cfqd->queue->backing_dev_info;
>>>>  
>>>> -	cfqg = cfqg_of_blkg(blkiocg_lookup_group(blkcg, key));
>>>> -	if (cfqg && !cfqg->blkg.dev && bdi->dev && dev_name(bdi->dev)) {
>>>> -		sscanf(dev_name(bdi->dev), "%u:%u", &major, &minor);
>>>> -		cfqg->blkg.dev = MKDEV(major, minor);
>>>> -		goto done;
>>>> -	}
>>>> -	if (cfqg || !create)
>>>> -		goto done;
>>>> -
>>>> -	cfqg = kzalloc_node(sizeof(*cfqg), GFP_ATOMIC, cfqd->queue->node);
>>>> -	if (!cfqg)
>>>> -		goto done;
>>>> +	cfqg->grp_service_tree = CFQ_RB_ROOT;
>>>>  
>>>>  	for_each_cfqg_st(cfqg, i, j, st)
>>>>  		*st = CFQ_RB_ROOT;
>>>> -	RB_CLEAR_NODE(&cfqg->rb_node);
>>>>  
>>>>  	/*
>>>>  	 * Take the initial reference that will be released on destroy
>>>> @@ -1023,11 +1168,102 @@ cfq_find_alloc_cfqg(struct cfq_data *cfqd, struct cgroup *cgroup, int create)
>>>>  	sscanf(dev_name(bdi->dev), "%u:%u", &major, &minor);
>>>>  	cfq_blkiocg_add_blkio_group(blkcg, &cfqg->blkg, (void *)cfqd,
>>>>  					MKDEV(major, minor));
>>>> -	cfqg->weight = blkcg_get_weight(blkcg, cfqg->blkg.dev);
>>>> -
>>>> +	init_group_queue_entity(blkcg, cfqg);
>>>>  	/* Add group on cfqd list */
>>>>  	hlist_add_head(&cfqg->cfqd_node, &cfqd->cfqg_list);
>>>> +}
>>>> +
>>>> +static void uninit_cfqg(struct cfq_data *cfqd, struct cfq_group *cfqg)
>>>> +{
>>>> +	if (!cfq_blkiocg_del_blkio_group(&cfqg->blkg))
>>>> +		cfq_destroy_cfqg(cfqd, cfqg);
>>>> +}
>>>> +
>>>> +static void cfqg_set_parent(struct cfq_group *cfqg, struct cfq_group *p_cfqg)
>>>> +{
>>>> +	struct io_sched_entity *gse = &cfqg->group_se;
>>>> +	struct io_sched_entity *qse = &cfqg->queue_se;
>>>> +	struct io_sched_entity *p_gse = &p_cfqg->group_se;
>>>> +
>>>> +	gse->parent = p_gse;
>>>> +	gse->st = &p_cfqg->grp_service_tree;
>>>> +
>>>> +	qse->parent = gse;
>>>> +	qse->st = &cfqg->grp_service_tree;
>>>> +
>>>> +	/* child reference */
>>>> +	atomic_inc(&p_cfqg->ref);
>>>> +}
>>>> +
>>>> +int cfqg_chain_alloc(struct cfq_data *cfqd, struct cgroup *cgroup)
>>>> +{
>>>> +	struct blkio_cgroup *blkcg = cgroup_to_blkio_cgroup(cgroup);
>>>> +	struct blkio_cgroup *p_blkcg;
>>>> +	struct backing_dev_info *bdi = &cfqd->queue->backing_dev_info;
>>>> +	unsigned int major, minor;
>>>> +	struct cfq_group *cfqg, *p_cfqg;
>>>> +	void *key = cfqd;
>>>> +	int ret;
>>>> +
>>>> +	cfqg = cfqg_of_blkg(blkiocg_lookup_group(blkcg, key));
>>>> +	if (cfqg) {
>>>> +		if (!cfqg->blkg.dev && bdi->dev && dev_name(bdi->dev)) {
>>>> +			sscanf(dev_name(bdi->dev), "%u:%u", &major, &minor);
>>>> +			cfqg->blkg.dev = MKDEV(major, minor);
>>>> +		}
>>>> +		/* chain has already been built */
>>>> +		return 0;
>>>> +	}
>>>> +
>>>> +	cfqg = kzalloc_node(sizeof(*cfqg), GFP_ATOMIC, cfqd->queue->node);
>>>> +	if (!cfqg)
>>>> +		return -1;
>>>> +
>>>> +	init_cfqg(cfqd, blkcg, cfqg);
>>>> +
>>>> +	/* Already to the top group */
>>>> +	if (!cgroup->parent)
>>>> +		return 0;
>>>> +
>>>> +	ret = cfqg_chain_alloc(cfqd, cgroup->parent);
>>>> +	if (ret == -1) {
>>>> +		uninit_cfqg(cfqd, cfqg);
>>>> +		return -1;
>>>> +	}
>>>> +
>>>> +	p_blkcg = cgroup_to_blkio_cgroup(cgroup->parent);
>>>> +	p_cfqg = cfqg_of_blkg(blkiocg_lookup_group(p_blkcg, key));
>>>> +	BUG_ON(p_cfqg == NULL);
>>>> +
>>>> +	cfqg_set_parent(cfqg, p_cfqg);
>>>> +	return 0;
>>>> +}
>>>> +
>>>> +static struct cfq_group *
>>>> +cfq_find_alloc_cfqg(struct cfq_data *cfqd, struct cgroup *cgroup, int create)
>>>> +{
>>>> +	struct blkio_cgroup *blkcg = cgroup_to_blkio_cgroup(cgroup);
>>>> +	struct cfq_group *cfqg = NULL;
>>>> +	void *key = cfqd;
>>>> +	struct backing_dev_info *bdi = &cfqd->queue->backing_dev_info;
>>>> +	unsigned int major, minor;
>>>> +	int ret;
>>>>  
>>>> +	cfqg = cfqg_of_blkg(blkiocg_lookup_group(blkcg, key));
>>>> +	if (cfqg && !cfqg->blkg.dev && bdi->dev && dev_name(bdi->dev)) {
>>>> +		sscanf(dev_name(bdi->dev), "%u:%u", &major, &minor);
>>>> +		cfqg->blkg.dev = MKDEV(major, minor);
>>>> +		goto done;
>>>> +	}
>>>> +	if (cfqg || !create)
>>>> +		goto done;
>>>> +
>>>> +	ret = cfqg_chain_alloc(cfqd, cgroup);
>>>> +	if (!ret) {
>>>> +		cfqg = cfqg_of_blkg(blkiocg_lookup_group(blkcg, key));
>>>> +		BUG_ON(cfqg == NULL);
>>>> +		goto done;
>>>> +	}
>>>>  done:
>>>>  	return cfqg;
>>>>  }
>>>> @@ -1067,33 +1303,6 @@ static void cfq_link_cfqq_cfqg(struct cfq_queue *cfqq, struct cfq_group *cfqg)
>>>>  	atomic_inc(&cfqq->cfqg->ref);
>>>>  }
>>>>  
>>>> -static void cfq_put_cfqg(struct cfq_group *cfqg)
>>>> -{
>>>> -	struct cfq_rb_root *st;
>>>> -	int i, j;
>>>> -
>>>> -	BUG_ON(atomic_read(&cfqg->ref) <= 0);
>>>> -	if (!atomic_dec_and_test(&cfqg->ref))
>>>> -		return;
>>>> -	for_each_cfqg_st(cfqg, i, j, st)
>>>> -		BUG_ON(!RB_EMPTY_ROOT(&st->rb) || st->active != NULL);
>>>> -	kfree(cfqg);
>>>> -}
>>>> -
>>>> -static void cfq_destroy_cfqg(struct cfq_data *cfqd, struct cfq_group *cfqg)
>>>> -{
>>>> -	/* Something wrong if we are trying to remove same group twice */
>>>> -	BUG_ON(hlist_unhashed(&cfqg->cfqd_node));
>>>> -
>>>> -	hlist_del_init(&cfqg->cfqd_node);
>>>> -
>>>> -	/*
>>>> -	 * Put the reference taken at the time of creation so that when all
>>>> -	 * queues are gone, group can be destroyed.
>>>> -	 */
>>>> -	cfq_put_cfqg(cfqg);
>>>> -}
>>>> -
>>>>  static void cfq_release_cfq_groups(struct cfq_data *cfqd)
>>>>  {
>>>>  	struct hlist_node *pos, *n;
>>>> @@ -1668,9 +1877,6 @@ __cfq_slice_expired(struct cfq_data *cfqd, struct cfq_queue *cfqq,
>>>>  	if (cfqq == cfqd->active_queue)
>>>>  		cfqd->active_queue = NULL;
>>>>  
>>>> -	if (&cfqq->cfqg->rb_node == cfqd->grp_service_tree.active)
>>>> -		cfqd->grp_service_tree.active = NULL;
>>>> -
>>>>  	if (cfqd->active_cic) {
>>>>  		put_io_context(cfqd->active_cic->ioc);
>>>>  		cfqd->active_cic = NULL;
>>>> @@ -2173,17 +2379,26 @@ static void choose_service_tree(struct cfq_data *cfqd, struct cfq_group *cfqg)
>>>>  	cfqd->noidle_tree_requires_idle = false;
>>>>  }
>>>>  
>>>> +
>>>>  static struct cfq_group *cfq_get_next_cfqg(struct cfq_data *cfqd)
>>>>  {
>>>> -	struct cfq_rb_root *st = &cfqd->grp_service_tree;
>>>> +	struct cfq_group *root_group = &cfqd->root_group;
>>>> +	struct cfq_rb_root *st = &root_group->grp_service_tree;
>>>>  	struct cfq_group *cfqg;
>>>> +	struct io_sched_entity *se;
>>>>  
>>>> -	if (RB_EMPTY_ROOT(&st->rb))
>>>> -		return NULL;
>>>> -	cfqg = cfq_rb_first_group(st);
>>>> -	st->active = &cfqg->rb_node;
>>>> -	update_min_vdisktime(st);
>>>> -	return cfqg;
>>>> +	do {
>>>> +		se = cfq_rb_first_se(st);
>>>> +		if (!se)
>>>> +			return NULL;
>>>> +		st->active = &se->rb_node;
>>>> +		update_min_vdisktime(st);
>>>> +		cfqg = cfqg_of_qse(se);
>>>> +		if (cfqg)
>>>> +			return cfqg;
>>>> +		cfqg = cfqg_of_gse(se);
>>>> +		st = &cfqg->grp_service_tree;
>>>> +	} while (1);
>>>>  }
>>>>  
>>>>  static void cfq_choose_cfqg(struct cfq_data *cfqd)
>>>> @@ -2215,15 +2430,18 @@ static struct cfq_queue *cfq_select_queue(struct cfq_data *cfqd)
>>>>  	if (!cfqq)
>>>>  		goto new_queue;
>>>>  
>>>> +
>>>>  	if (!cfqd->rq_queued)
>>>>  		return NULL;
>>>>  
>>>> +
>>>>  	/*
>>>>  	 * We were waiting for group to get backlogged. Expire the queue
>>>>  	 */
>>>>  	if (cfq_cfqq_wait_busy(cfqq) && !RB_EMPTY_ROOT(&cfqq->sort_list))
>>>>  		goto expire;
>>>>  
>>>> +
>>>>  	/*
>>>>  	 * The active queue has run out of time, expire it and select new.
>>>>  	 */
>>>> @@ -2245,6 +2463,7 @@ static struct cfq_queue *cfq_select_queue(struct cfq_data *cfqd)
>>>>  			goto check_group_idle;
>>>>  	}
>>>>  
>>>> +
>>>>  	/*
>>>>  	 * The active queue has requests and isn't expired, allow it to
>>>>  	 * dispatch.
>>>> @@ -2252,6 +2471,7 @@ static struct cfq_queue *cfq_select_queue(struct cfq_data *cfqd)
>>>>  	if (!RB_EMPTY_ROOT(&cfqq->sort_list))
>>>>  		goto keep_queue;
>>>>  
>>>> +
>>>>  	/*
>>>>  	 * If another queue has a request waiting within our mean seek
>>>>  	 * distance, let it run.  The expire code will check for close
>>>> @@ -2505,6 +2725,7 @@ static int cfq_dispatch_requests(struct request_queue *q, int force)
>>>>  	}
>>>>  
>>>>  	cfq_log_cfqq(cfqd, cfqq, "dispatched a request");
>>>> +
>>>>  	return 1;
>>>>  }
>>>>  
>>>> @@ -3854,17 +4075,25 @@ static void *cfq_init_queue(struct request_queue *q)
>>>>  
>>>>  	cfqd->cic_index = i;
>>>>  
>>>> -	/* Init root service tree */
>>>> -	cfqd->grp_service_tree = CFQ_RB_ROOT;
>>>> -
>>>>  	/* Init root group */
>>>>  	cfqg = &cfqd->root_group;
>>>> +	cfqg->grp_service_tree = CFQ_RB_ROOT;
>>>>  	for_each_cfqg_st(cfqg, i, j, st)
>>>>  		*st = CFQ_RB_ROOT;
>>>> -	RB_CLEAR_NODE(&cfqg->rb_node);
>>>> -
>>>> +	cfqg->group_se.is_group_se = true;
>>>> +	RB_CLEAR_NODE(&cfqg->group_se.rb_node);
>>>> +	cfqg->group_se.on_st = false;
>>>>  	/* Give preference to root group over other groups */
>>>> -	cfqg->weight = 2*BLKIO_WEIGHT_DEFAULT;
>>>> +	cfqg->group_se.weight = 2*BLKIO_WEIGHT_DEFAULT;
>>>> +	cfqg->group_se.parent = NULL;
>>>> +	cfqg->group_se.st = NULL;
>>>> +
>>>> +	cfqg->queue_se.is_group_se = false;
>>>> +	RB_CLEAR_NODE(&cfqg->queue_se.rb_node);
>>>> +	cfqg->queue_se.on_st = false;
>>>> +	cfqg->queue_se.weight = 2*BLKIO_WEIGHT_DEFAULT;
>>>> +	cfqg->queue_se.parent = &cfqg->group_se;
>>>> +	cfqg->queue_se.st = &cfqg->grp_service_tree;
>>>>  
>>>>  #ifdef CONFIG_CFQ_GROUP_IOSCHED
>>>>  	/*
>>>> -- 
>>>> 1.6.5.2
>>>>
>>>>
> 
> 
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/