Re: [PATCH 25/23] io-controller: fix queue vs group fairness

[Vivek Goyal <vgoyal@redhat.com>]

On Wed, Sep 09, 2009 at 01:13:34AM +0200, Fabio Checconi wrote:
> Hi,
> 
> > From: Vivek Goyal <vgoyal@redhat.com>
> > Date: Tue, Sep 08, 2009 06:28:27PM -0400
> >
> > 
> > o I found an issue during test and that is if there is a mix of queue and group
> ...
> >  So we need to keep track of process io queue's vdisktime, even it after got
> >  deleted from io scheduler's service tree and use that same vdisktime if that
> >  queue gets backlogged again. But trusting a ioq's vdisktime is bad because
> >  it can lead to issues if a service tree min_vtime wrap around takes place 
> >  between two requests of the queue. (Agreed that it can be not that easy to
> >  hit but it is possible).
> > 
> >  Hence, keep a cache of io queues serviced recently and when a queue gets
> >  backlogged, if it is found in cache, use that vdisktime otherwise assign
> >  a new vdisktime. This cache of io queues (idle tree), is basically the idea
> >  implemented by BFQ guys. I had gotten rid of idle trees in V9 and now I am
> >  bringing it back. (Now I understand it better. :-)).
> > 
> >  There is one good side affect of keeping the cache of recently service io
> >  queues. Now CFQ can differentiate between streaming readers and new processes
> >  doing IO. Now for a new queue (which is not in the cache), we can assign a
> >  lower vdisktime and for a streaming reader, we assign vdisktime based on disk
> >  time used. This way small file readers or the processes doing small amount
> >  of IO will have reduced latencies at the cost of little reduced throughput of
> >  streaming readers.
> > 
> 
>   just a little note: this patch seems to introduce a special case for
> vdisktime = 0, assigning it the meaning of "bad timestamp," but the virtual
> time space wraps, so 0 is a perfectly legal value, which can be reached by
> service.  I have no idea if it can produce visible effects, but it doesn't
> seem to be correct.
> 
> 

Hi Fabio,

You are right that technically during wrap arounds one can hit value 0 as
legal value. But I think it is hard to hit at the same time, the only side
affect of it will be that a queue will be either placed favorably (in case of
sync queues) or at the end of tree (if it is async queue).

Async queues anyway go at the end after every dispatch round. So only side
affect is that once during wrap around cycle a sync queue will be placed
favorably and can gain share once in a dispatch round.

I think it is not a big issue at this point of time. But if it becomes
significant, I can introduce a new variable or start passing function
parameter to denote whether we found the queue in cache or not.

But if you think that it is absolutely no no, let me know....

Thanks
Vivek


> > Signed-off-by: Vivek Goyal <vgoyal@redhat.com>
> > ---
> >  block/cfq-iosched.c |    2 
> >  block/elevator-fq.c |  252 ++++++++++++++++++++++++++++++++++++++++++++++++----
> >  block/elevator-fq.h |    9 +
> >  3 files changed, 246 insertions(+), 17 deletions(-)
> > 
> > Index: linux16/block/elevator-fq.c
> > ===================================================================
> > --- linux16.orig/block/elevator-fq.c	2009-09-08 15:44:21.000000000 -0400
> > +++ linux16/block/elevator-fq.c	2009-09-08 15:47:45.000000000 -0400
> > @@ -52,6 +52,8 @@ static struct kmem_cache *elv_ioq_pool;
> >  #define elv_log_entity(entity, fmt, args...)
> >  #endif
> >  
> > +static void check_idle_tree_release(struct io_service_tree *st);
> > +
> >  static inline struct io_queue *ioq_of(struct io_entity *entity)
> >  {
> >  	if (entity->my_sd == NULL)
> > @@ -109,6 +111,11 @@ elv_prio_to_slice(struct elv_fq_data *ef
> >  	return elv_weight_slice(efqd, elv_ioq_sync(ioq), ioq->entity.weight);
> >  }
> >  
> > +static inline int vdisktime_gt(u64 a, u64 b)
> > +{
> > +	return (s64)(a - b) > 0;
> > +}
> > +
> >  static inline u64 max_vdisktime(u64 min_vdisktime, u64 vdisktime)
> >  {
> >  	s64 delta = (s64)(vdisktime - min_vdisktime);
> > @@ -145,6 +152,7 @@ static void update_min_vdisktime(struct 
> >  	}
> >  
> >  	st->min_vdisktime = max_vdisktime(st->min_vdisktime, vdisktime);
> > +	check_idle_tree_release(st);
> >  }
> >  
> >  static inline struct io_entity *parent_entity(struct io_entity *entity)
> > @@ -411,27 +419,46 @@ static void place_entity(struct io_servi
> >  	struct rb_node *parent;
> >  	struct io_entity *entry;
> >  	int nr_active = st->nr_active - 1;
> > +	struct io_queue *ioq = ioq_of(entity);
> > +	int sync = 1;
> > +
> > +	if (ioq)
> > +		sync = elv_ioq_sync(ioq);
> > +
> > +	if (add_front || !nr_active) {
> > +		vdisktime = st->min_vdisktime;
> > +		goto done;
> > +	}
> > +
> > +	if (sync && entity->vdisktime
> > +	    && vdisktime_gt(entity->vdisktime, st->min_vdisktime)) {
> > +		/* vdisktime still in future. Use old vdisktime */
> > +		vdisktime = entity->vdisktime;
> > +		goto done;
> > +	}
> >  
> >  	/*
> > -	 * Currently put entity at the end of last entity. This probably will
> > -	 * require adjustments as we move along
> > +	 * Effectively a new queue. Assign sync queue a lower vdisktime so
> > +	 * we can achieve better latencies for small file readers. For async
> > +	 * queues, put them at the end of the existing queue.
> > +	 * Group entities are always considered sync.
> >  	 */
> > -	if (io_entity_class_idle(entity)) {
> > -		vdisktime = elv_delta_fair(ELV_IDLE_DELAY, entity);
> > -		parent = rb_last(&st->active);
> > -		if (parent) {
> > -			entry = rb_entry(parent, struct io_entity, rb_node);
> > -			vdisktime += entry->vdisktime;
> > -		}
> > -	} else if (!add_front && nr_active) {
> > -		parent = rb_last(&st->active);
> > -		if (parent) {
> > -			entry = rb_entry(parent, struct io_entity, rb_node);
> > -			vdisktime = entry->vdisktime;
> > -		}
> > -	} else
> > +	if (sync) {
> >  		vdisktime = st->min_vdisktime;
> > +		goto done;
> > +	}
> >  
> > +	/*
> > +	 * Put entity at the end of the tree. Effectively async queues use
> > +	 * this path.
> > +	 */
> > +	parent = rb_last(&st->active);
> > +	if (parent) {
> > +		entry = rb_entry(parent, struct io_entity, rb_node);
> > +		vdisktime = entry->vdisktime;
> > +	} else
> > +		vdisktime = st->min_vdisktime;
> > +done:
> >  	entity->vdisktime = max_vdisktime(st->min_vdisktime, vdisktime);
> >  	elv_log_entity(entity, "place_entity: vdisktime=%llu"
> >  			" min_vdisktime=%llu", entity->vdisktime,
> > @@ -447,6 +474,122 @@ static inline void io_entity_update_prio
> >  		 */
> >  		init_io_entity_service_tree(entity, parent_entity(entity));
> >  		entity->ioprio_changed = 0;
> > +
> > +		/*
> > +		 * Assign this entity a fresh vdisktime instead of using
> > +		 * previous one as prio class will lead to service tree
> > +		 * change and this vdisktime will not be valid on new
> > +		 * service tree.
> > +		 *
> > +		 * TODO: Handle the case of only prio change.
> > +		 */
> > +		entity->vdisktime = 0;
> > +	}
> > +}
> > +
> > +static void
> > +__dequeue_io_entity_idle(struct io_service_tree *st, struct io_entity *entity)
> > +{
> > +	if (st->rb_leftmost_idle == &entity->rb_node) {
> > +		struct rb_node *next_node;
> > +
> > +		next_node = rb_next(&entity->rb_node);
> > +		st->rb_leftmost_idle = next_node;
> > +	}
> > +
> > +	rb_erase(&entity->rb_node, &st->idle);
> > +	RB_CLEAR_NODE(&entity->rb_node);
> > +}
> > +
> > +static void dequeue_io_entity_idle(struct io_entity *entity)
> > +{
> > +	struct io_queue *ioq = ioq_of(entity);
> > +
> > +	__dequeue_io_entity_idle(entity->st, entity);
> > +	entity->on_idle_st = 0;
> > +	if (ioq)
> > +		elv_put_ioq(ioq);
> > +}
> > +
> > +static void
> > +__enqueue_io_entity_idle(struct io_service_tree *st, struct io_entity *entity)
> > +{
> > +	struct rb_node **node = &st->idle.rb_node;
> > +	struct rb_node *parent = NULL;
> > +	struct io_entity *entry;
> > +	int leftmost = 1;
> > +
> > +	while (*node != NULL) {
> > +		parent = *node;
> > +		entry = rb_entry(parent, struct io_entity, rb_node);
> > +
> > +		if (vdisktime_gt(entry->vdisktime, entity->vdisktime))
> > +			node = &parent->rb_left;
> > +		else {
> > +			node = &parent->rb_right;
> > +			leftmost = 0;
> > +		}
> > +	}
> > +
> > +	/*
> > +	 * Maintain a cache of leftmost tree entries (it is frequently
> > +	 * used)
> > +	 */
> > +	if (leftmost)
> > +		st->rb_leftmost_idle = &entity->rb_node;
> > +
> > +	rb_link_node(&entity->rb_node, parent, node);
> > +	rb_insert_color(&entity->rb_node, &st->idle);
> > +}
> > +
> > +static void enqueue_io_entity_idle(struct io_entity *entity)
> > +{
> > +	struct io_queue *ioq = ioq_of(entity);
> > +	struct io_group *parent_iog;
> > +
> > +	/*
> > +	 * Don't put an entity on idle tree if it has been marked for deletion.
> > +	 * We are not expecting more io from this entity. No need to cache it
> > +	 */
> > +
> > +	if (entity->exiting)
> > +		return;
> > +
> > +	/*
> > +	 * If parent group is exiting, don't put on idle tree. May be task got
> > +	 * moved to a different cgroup and original cgroup got deleted
> > +	 */
> > +	parent_iog = iog_of(parent_entity(entity));
> > +	if (parent_iog->entity.exiting)
> > +		return;
> > +
> > +	if (ioq)
> > +		elv_get_ioq(ioq);
> > +	__enqueue_io_entity_idle(entity->st, entity);
> > +	entity->on_idle_st = 1;
> > +}
> > +
> > +static void check_idle_tree_release(struct io_service_tree *st)
> > +{
> > +	struct io_entity *leftmost;
> > +
> > +	if (!st->rb_leftmost_idle)
> > +		return;
> > +
> > +	leftmost = rb_entry(st->rb_leftmost_idle, struct io_entity, rb_node);
> > +
> > +	if (vdisktime_gt(st->min_vdisktime, leftmost->vdisktime))
> > +		dequeue_io_entity_idle(leftmost);
> > +}
> > +
> > +static void flush_idle_tree(struct io_service_tree *st)
> > +{
> > +	struct io_entity *entity;
> > +
> > +	while(st->rb_leftmost_idle) {
> > +		entity = rb_entry(st->rb_leftmost_idle, struct io_entity,
> > +					rb_node);
> > +		dequeue_io_entity_idle(entity);
> >  	}
> >  }
> >  
> > @@ -483,6 +626,9 @@ static void dequeue_io_entity(struct io_
> >  	st->nr_active--;
> >  	sd->nr_active--;
> >  	debug_update_stats_dequeue(entity);
> > +
> > +	if (vdisktime_gt(entity->vdisktime, st->min_vdisktime))
> > +		enqueue_io_entity_idle(entity);
> >  }
> >  
> >  static void
> > @@ -524,6 +670,16 @@ static void enqueue_io_entity(struct io_
> >  	struct io_service_tree *st;
> >  	struct io_sched_data *sd = io_entity_sched_data(entity);
> >  
> > +	if (entity->on_idle_st)
> > +		dequeue_io_entity_idle(entity);
> > +	else
> > +		/*
> > +		 * This entity was not in idle tree cache. Zero out vdisktime
> > +		 * so that we don't rely on old vdisktime instead assign a
> > +		 * fresh one.
> > +		 */
> > +		entity->vdisktime = 0;
> > +
> >  	io_entity_update_prio(entity);
> >  	st = entity->st;
> >  	st->nr_active++;
> > @@ -574,6 +730,8 @@ static void requeue_io_entity(struct io_
> >  	struct io_service_tree *st = entity->st;
> >  	struct io_entity *next_entity;
> >  
> > +	entity->vdisktime = 0;
> > +
> >  	if (add_front) {
> >  		next_entity = __lookup_next_io_entity(st);
> >  
> > @@ -1937,11 +2095,18 @@ static void io_free_root_group(struct el
> >  {
> >  	struct io_group *iog = e->efqd->root_group;
> >  	struct io_cgroup *iocg = &io_root_cgroup;
> > +	struct io_service_tree *st;
> > +	int i;
> >  
> >  	spin_lock_irq(&iocg->lock);
> >  	hlist_del_rcu(&iog->group_node);
> >  	spin_unlock_irq(&iocg->lock);
> >  
> > +	for (i = 0; i < IO_IOPRIO_CLASSES; i++) {
> > +		st = iog->sched_data.service_tree + i;
> > +		flush_idle_tree(st);
> > +	}
> > +
> >  	put_io_group_queues(e, iog);
> >  	elv_put_iog(iog);
> >  }
> > @@ -2039,9 +2204,29 @@ EXPORT_SYMBOL(elv_put_iog);
> >   */
> >  static void __io_destroy_group(struct elv_fq_data *efqd, struct io_group *iog)
> >  {
> > +	struct io_service_tree *st;
> > +	int i;
> > +	struct io_entity *entity = &iog->entity;
> > +
> > +	/*
> > +	 * Mark io group for deletion so that no new entry goes in
> > +	 * idle tree. Any active queue which is removed from active
> > +	 * tree will not be put in to idle tree.
> > +	 */
> > +	entity->exiting = 1;
> > +
> > +	/* We flush idle tree now, and don't put things in there any more. */
> > +	for (i = 0; i < IO_IOPRIO_CLASSES; i++) {
> > +		st = iog->sched_data.service_tree + i;
> > +		flush_idle_tree(st);
> > +	}
> > +
> >  	hlist_del(&iog->elv_data_node);
> >  	put_io_group_queues(efqd->eq, iog);
> >  
> > +	if (entity->on_idle_st)
> > +		dequeue_io_entity_idle(entity);
> > +
> >  	/*
> >  	 * Put the reference taken at the time of creation so that when all
> >  	 * queues are gone, group can be destroyed.
> > @@ -2374,7 +2559,13 @@ static struct io_group *io_alloc_root_gr
> >  static void io_free_root_group(struct elevator_queue *e)
> >  {
> >  	struct io_group *iog = e->efqd->root_group;
> > +	struct io_service_tree *st;
> > +	int i;
> >  
> > +	for (i = 0; i < IO_IOPRIO_CLASSES; i++) {
> > +		st = iog->sched_data.service_tree + i;
> > +		flush_idle_tree(st);
> > +	}
> >  	put_io_group_queues(e, iog);
> >  	kfree(iog);
> >  }
> > @@ -3257,6 +3448,35 @@ done:
> >  		elv_schedule_dispatch(q);
> >  }
> >  
> > +/*
> > + * The process associted with ioq (in case of cfq), is going away. Mark it
> > + * for deletion.
> > + */
> > +void elv_exit_ioq(struct io_queue *ioq)
> > +{
> > +	struct io_entity *entity = &ioq->entity;
> > +
> > +	/*
> > +	 * Async ioq's belong to io group and are cleaned up once group is
> > +	 * being deleted. Not need to do any cleanup here even if cfq has
> > +	 * dropped the reference to the queue
> > +	 */
> > +	if (!elv_ioq_sync(ioq))
> > +		return;
> > +
> > +	/*
> > + 	 * This queue is still under service. Just mark it so that once all
> > +	 * the IO from queue is done, it is not put back in idle tree.
> > +	 */
> > +	if (entity->on_st) {
> > +		entity->exiting = 1;
> > +		return;
> > +	} else if(entity->on_idle_st) {
> > +		/* Remove ioq from idle tree */
> > +		dequeue_io_entity_idle(entity);
> > +	}
> > +}
> > +EXPORT_SYMBOL(elv_exit_ioq);
> >  static void elv_slab_kill(void)
> >  {
> >  	/*
> > Index: linux16/block/cfq-iosched.c
> > ===================================================================
> > --- linux16.orig/block/cfq-iosched.c	2009-09-08 15:43:36.000000000 -0400
> > +++ linux16/block/cfq-iosched.c	2009-09-08 15:47:45.000000000 -0400
> > @@ -1138,6 +1138,7 @@ static void cfq_exit_cfqq(struct cfq_dat
> >  		elv_schedule_dispatch(cfqd->queue);
> >  	}
> >  
> > +	elv_exit_ioq(cfqq->ioq);
> >  	cfq_put_queue(cfqq);
> >  }
> >  
> > @@ -1373,6 +1374,7 @@ static void changed_cgroup(struct io_con
> >  		 */
> >  		if (iog != __iog) {
> >  			cic_set_cfqq(cic, NULL, 1);
> > +			elv_exit_ioq(sync_cfqq->ioq);
> >  			cfq_put_queue(sync_cfqq);
> >  		}
> >  	}
> > Index: linux16/block/elevator-fq.h
> > ===================================================================
> > --- linux16.orig/block/elevator-fq.h	2009-09-08 15:43:36.000000000 -0400
> > +++ linux16/block/elevator-fq.h	2009-09-08 15:47:45.000000000 -0400
> > @@ -33,6 +33,10 @@ struct io_service_tree {
> >  	u64 min_vdisktime;
> >  	struct rb_node *rb_leftmost;
> >  	unsigned int nr_active;
> > +
> > +        /* A cache of io entities which were served and expired */
> > +        struct rb_root idle;
> > +        struct rb_node *rb_leftmost_idle;
> >  };
> >  
> >  struct io_sched_data {
> > @@ -44,9 +48,12 @@ struct io_sched_data {
> >  struct io_entity {
> >  	struct rb_node rb_node;
> >  	int on_st;
> > +	int on_idle_st;
> >  	u64 vdisktime;
> >  	unsigned int weight;
> >  	struct io_entity *parent;
> > +	/* This io entity (queue or group) has been marked for deletion */
> > +	unsigned int exiting;
> >  
> >  	struct io_sched_data *my_sd;
> >  	struct io_service_tree *st;
> > @@ -572,7 +579,7 @@ extern struct io_queue *elv_alloc_ioq(st
> >  extern void elv_free_ioq(struct io_queue *ioq);
> >  extern struct io_group *ioq_to_io_group(struct io_queue *ioq);
> >  extern int elv_iog_should_idle(struct io_queue *ioq);
> > -
> > +extern void elv_exit_ioq(struct io_queue *ioq);
> >  #else /* CONFIG_ELV_FAIR_QUEUING */
> >  static inline struct elv_fq_data *
> >  elv_alloc_fq_data(struct request_queue *q, struct elevator_queue *e)