/*

   *  CFQ, or complete fairness queueing, disk scheduler.
   *
   *  Based on ideas from a previously unfinished io
   *  scheduler (round robin per-process disk scheduling) and Andrea Arcangeli.
   *

   *  Copyright (C) 2003 Jens Axboe <axboe@kernel.dk>

   */

  #include <linux/module.h>

  #include <linux/slab.h>

  #include <linux/blkdev.h>
  #include <linux/elevator.h>

  #include <linux/ktime.h>

  #include <linux/rbtree.h>

  #include <linux/ioprio.h>

  #include <linux/blktrace_api.h>

  #include <linux/blk-cgroup.h>

  #include "blk.h"

  
  /*
   * tunables
   */

  /* max queue in one round of service */

  static const int cfq_quantum = 8;

  static const u64 cfq_fifo_expire[2] = { NSEC_PER_SEC / 4, NSEC_PER_SEC / 8 };

  /* maximum backwards seek, in KiB */
  static const int cfq_back_max = 16 * 1024;
  /* penalty of a backwards seek */
  static const int cfq_back_penalty = 2;

  static const u64 cfq_slice_sync = NSEC_PER_SEC / 10;
  static u64 cfq_slice_async = NSEC_PER_SEC / 25;

  static const int cfq_slice_async_rq = 2;

  static u64 cfq_slice_idle = NSEC_PER_SEC / 125;
  static u64 cfq_group_idle = NSEC_PER_SEC / 125;
  static const u64 cfq_target_latency = (u64)NSEC_PER_SEC * 3/10; /* 300 ms */

  static const int cfq_hist_divisor = 4;

  /*

   * offset from end of service tree

   */

  #define CFQ_IDLE_DELAY		(NSEC_PER_SEC / 5)

  
  /*
   * below this threshold, we consider thinktime immediate
   */

  #define CFQ_MIN_TT		(2 * NSEC_PER_SEC / HZ)

  #define CFQ_SLICE_SCALE		(5)

  #define CFQ_HW_QUEUE_MIN	(5)

  #define CFQ_SERVICE_SHIFT       12

  #define CFQQ_SEEK_THR		(sector_t)(8 * 100)

  #define CFQQ_CLOSE_THR		(sector_t)(8 * 1024)

  #define CFQQ_SECT_THR_NONROT	(sector_t)(2 * 32)

  #define CFQQ_SEEKY(cfqq)	(hweight32(cfqq->seek_history) > 32/8)

  #define RQ_CIC(rq)		icq_to_cic((rq)->elv.icq)
  #define RQ_CFQQ(rq)		(struct cfq_queue *) ((rq)->elv.priv[0])
  #define RQ_CFQG(rq)		(struct cfq_group *) ((rq)->elv.priv[1])

  static struct kmem_cache *cfq_pool;

  #define CFQ_PRIO_LISTS		IOPRIO_BE_NR
  #define cfq_class_idle(cfqq)	((cfqq)->ioprio_class == IOPRIO_CLASS_IDLE)

  #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)

  /* blkio-related constants */

  #define CFQ_WEIGHT_LEGACY_MIN	10
  #define CFQ_WEIGHT_LEGACY_DFL	500
  #define CFQ_WEIGHT_LEGACY_MAX	1000

  struct cfq_ttime {

  	u64 last_end_request;

  	u64 ttime_total;
  	u64 ttime_mean;

  	unsigned long ttime_samples;

  };

  /*

   * Most of our rbtree usage is for sorting with min extraction, so
   * if we cache the leftmost node we don't have to walk down the tree
   * to find it. Idea borrowed from Ingo Molnars CFS scheduler. We should
   * move this into the elevator for the rq sorting as well.
   */
  struct cfq_rb_root {
  	struct rb_root rb;
  	struct rb_node *left;

  	unsigned count;

  	u64 min_vdisktime;

  	struct cfq_ttime ttime;

  };

  #define CFQ_RB_ROOT	(struct cfq_rb_root) { .rb = RB_ROOT, \

  			.ttime = {.last_end_request = ktime_get_ns(),},}

  
  /*

   * Per process-grouping structure
   */
  struct cfq_queue {
  	/* reference count */

  	int ref;

  	/* various state flags, see below */
  	unsigned int flags;
  	/* parent cfq_data */
  	struct cfq_data *cfqd;
  	/* service_tree member */
  	struct rb_node rb_node;
  	/* service_tree key */

  	u64 rb_key;

  	/* prio tree member */
  	struct rb_node p_node;
  	/* prio tree root we belong to, if any */
  	struct rb_root *p_root;
  	/* sorted list of pending requests */
  	struct rb_root sort_list;
  	/* if fifo isn't expired, next request to serve */
  	struct request *next_rq;
  	/* requests queued in sort_list */
  	int queued[2];
  	/* currently allocated requests */
  	int allocated[2];
  	/* fifo list of requests in sort_list */
  	struct list_head fifo;

  	/* time when queue got scheduled in to dispatch first request. */

  	u64 dispatch_start;
  	u64 allocated_slice;
  	u64 slice_dispatch;

  	/* time when first request from queue completed and slice started. */

  	u64 slice_start;
  	u64 slice_end;

  	s64 slice_resid;

  	/* pending priority requests */
  	int prio_pending;

  	/* number of requests that are on the dispatch list or inside driver */
  	int dispatched;
  
  	/* io prio of this group */
  	unsigned short ioprio, org_ioprio;

  	unsigned short ioprio_class, org_ioprio_class;

  	pid_t pid;

  	u32 seek_history;

  	sector_t last_request_pos;

  	struct cfq_rb_root *service_tree;

  	struct cfq_queue *new_cfqq;

  	struct cfq_group *cfqg;

  	/* Number of sectors dispatched from queue in single dispatch round */
  	unsigned long nr_sectors;

  };
  
  /*

   * First index in the service_trees.

   * IDLE is handled separately, so it has negative index
   */

  enum wl_class_t {

  	BE_WORKLOAD = 0,

  	RT_WORKLOAD = 1,
  	IDLE_WORKLOAD = 2,

  	CFQ_PRIO_NR,

  };
  
  /*

   * Second index in the service_trees.
   */
  enum wl_type_t {
  	ASYNC_WORKLOAD = 0,
  	SYNC_NOIDLE_WORKLOAD = 1,
  	SYNC_WORKLOAD = 2
  };

  struct cfqg_stats {
  #ifdef CONFIG_CFQ_GROUP_IOSCHED

  	/* number of ios merged */
  	struct blkg_rwstat		merged;
  	/* total time spent on device in ns, may not be accurate w/ queueing */
  	struct blkg_rwstat		service_time;
  	/* total time spent waiting in scheduler queue in ns */
  	struct blkg_rwstat		wait_time;
  	/* number of IOs queued up */
  	struct blkg_rwstat		queued;

  	/* total disk time and nr sectors dispatched by this group */
  	struct blkg_stat		time;
  #ifdef CONFIG_DEBUG_BLK_CGROUP
  	/* time not charged to this cgroup */
  	struct blkg_stat		unaccounted_time;
  	/* sum of number of ios queued across all samples */
  	struct blkg_stat		avg_queue_size_sum;
  	/* count of samples taken for average */
  	struct blkg_stat		avg_queue_size_samples;
  	/* how many times this group has been removed from service tree */
  	struct blkg_stat		dequeue;
  	/* total time spent waiting for it to be assigned a timeslice. */
  	struct blkg_stat		group_wait_time;

  	/* time spent idling for this blkcg_gq */

  	struct blkg_stat		idle_time;
  	/* total time with empty current active q with other requests queued */
  	struct blkg_stat		empty_time;
  	/* fields after this shouldn't be cleared on stat reset */
  	uint64_t			start_group_wait_time;
  	uint64_t			start_idle_time;
  	uint64_t			start_empty_time;
  	uint16_t			flags;
  #endif	/* CONFIG_DEBUG_BLK_CGROUP */
  #endif	/* CONFIG_CFQ_GROUP_IOSCHED */
  };

  /* Per-cgroup data */
  struct cfq_group_data {
  	/* must be the first member */

  	struct blkcg_policy_data cpd;

  
  	unsigned int weight;
  	unsigned int leaf_weight;
  };

  /* This is per cgroup per device grouping structure */
  struct cfq_group {

  	/* must be the first member */
  	struct blkg_policy_data pd;

  	/* group service_tree member */
  	struct rb_node rb_node;
  
  	/* group service_tree key */
  	u64 vdisktime;

  
  	/*

  	 * The number of active cfqgs and sum of their weights under this
  	 * cfqg.  This covers this cfqg's leaf_weight and all children's
  	 * weights, but does not cover weights of further descendants.
  	 *
  	 * If a cfqg is on the service tree, it's active.  An active cfqg
  	 * also activates its parent and contributes to the children_weight
  	 * of the parent.
  	 */
  	int nr_active;
  	unsigned int children_weight;
  
  	/*

  	 * vfraction is the fraction of vdisktime that the tasks in this
  	 * cfqg are entitled to.  This is determined by compounding the
  	 * ratios walking up from this cfqg to the root.
  	 *
  	 * It is in fixed point w/ CFQ_SERVICE_SHIFT and the sum of all
  	 * vfractions on a service tree is approximately 1.  The sum may
  	 * deviate a bit due to rounding errors and fluctuations caused by
  	 * cfqgs entering and leaving the service tree.
  	 */
  	unsigned int vfraction;
  
  	/*

  	 * There are two weights - (internal) weight is the weight of this
  	 * cfqg against the sibling cfqgs.  leaf_weight is the wight of
  	 * this cfqg against the child cfqgs.  For the root cfqg, both
  	 * weights are kept in sync for backward compatibility.
  	 */

  	unsigned int weight;

  	unsigned int new_weight;

  	unsigned int dev_weight;

  	unsigned int leaf_weight;
  	unsigned int new_leaf_weight;
  	unsigned int dev_leaf_weight;

  	/* number of cfqq currently on this group */
  	int nr_cfqq;

  	/*

  	 * Per group busy queues average. Useful for workload slice calc. We

  	 * create the array for each prio class but at run time it is used
  	 * only for RT and BE class and slot for IDLE class remains unused.
  	 * This is primarily done to avoid confusion and a gcc warning.
  	 */
  	unsigned int busy_queues_avg[CFQ_PRIO_NR];
  	/*
  	 * rr lists of queues with requests. We maintain service trees for
  	 * RT and BE classes. These trees are subdivided in subclasses
  	 * of SYNC, SYNC_NOIDLE and ASYNC based on workload type. For IDLE
  	 * class there is no subclassification and all the cfq queues go on
  	 * a single tree service_tree_idle.

  	 * Counts are embedded in the cfq_rb_root
  	 */
  	struct cfq_rb_root service_trees[2][3];
  	struct cfq_rb_root service_tree_idle;

  	u64 saved_wl_slice;

  	enum wl_type_t saved_wl_type;
  	enum wl_class_t saved_wl_class;

  	/* number of requests that are on the dispatch list or inside driver */
  	int dispatched;

  	struct cfq_ttime ttime;

  	struct cfqg_stats stats;	/* stats for this cfqg */

  
  	/* async queue for each priority case */
  	struct cfq_queue *async_cfqq[2][IOPRIO_BE_NR];
  	struct cfq_queue *async_idle_cfqq;

  };

  struct cfq_io_cq {
  	struct io_cq		icq;		/* must be the first member */
  	struct cfq_queue	*cfqq[2];
  	struct cfq_ttime	ttime;

  	int			ioprio;		/* the current ioprio */
  #ifdef CONFIG_CFQ_GROUP_IOSCHED

  	uint64_t		blkcg_serial_nr; /* the current blkcg serial */

  #endif

  };

  /*

   * Per block device queue structure
   */

  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;

  
  	/*

  	 * The priority currently being served

  	 */

  	enum wl_class_t serving_wl_class;
  	enum wl_type_t serving_wl_type;

  	u64 workload_expires;

  	struct cfq_group *serving_group;

  
  	/*
  	 * Each priority tree is sorted by next_request position.  These
  	 * trees are used when determining if two or more queues are
  	 * interleaving requests (see cfq_close_cooperator).
  	 */
  	struct rb_root prio_trees[CFQ_PRIO_LISTS];

  	unsigned int busy_queues;

  	unsigned int busy_sync_queues;

  	int rq_in_driver;
  	int rq_in_flight[2];

  
  	/*
  	 * queue-depth detection
  	 */
  	int rq_queued;

  	int hw_tag;

  	/*
  	 * hw_tag can be
  	 * -1 => indeterminate, (cfq will behave as if NCQ is present, to allow better detection)
  	 *  1 => NCQ is present (hw_tag_est_depth is the estimated max depth)
  	 *  0 => no NCQ
  	 */
  	int hw_tag_est_depth;
  	unsigned int hw_tag_samples;

  	/*

  	 * idle window management
  	 */

  	struct hrtimer idle_slice_timer;

  	struct work_struct unplug_work;

  	struct cfq_queue *active_queue;

  	struct cfq_io_cq *active_cic;

  	sector_t last_position;

  	/*
  	 * tunables, see top of file
  	 */
  	unsigned int cfq_quantum;

  	unsigned int cfq_back_penalty;
  	unsigned int cfq_back_max;

  	unsigned int cfq_slice_async_rq;

  	unsigned int cfq_latency;

  	u64 cfq_fifo_expire[2];
  	u64 cfq_slice[2];
  	u64 cfq_slice_idle;
  	u64 cfq_group_idle;
  	u64 cfq_target_latency;

  	/*
  	 * Fallback dummy cfqq for extreme OOM conditions
  	 */
  	struct cfq_queue oom_cfqq;

  	u64 last_delayed_sync;

  };

  static struct cfq_group *cfq_get_next_cfqg(struct cfq_data *cfqd);

  static void cfq_put_queue(struct cfq_queue *cfqq);

  static struct cfq_rb_root *st_for(struct cfq_group *cfqg,

  					    enum wl_class_t class,

  					    enum wl_type_t type)

  {

  	if (!cfqg)
  		return NULL;

  	if (class == IDLE_WORKLOAD)

  		return &cfqg->service_tree_idle;

  	return &cfqg->service_trees[class][type];

  }

  enum cfqq_state_flags {

  	CFQ_CFQQ_FLAG_on_rr = 0,	/* on round-robin busy list */
  	CFQ_CFQQ_FLAG_wait_request,	/* waiting for a request */

  	CFQ_CFQQ_FLAG_must_dispatch,	/* must be allowed a dispatch */

  	CFQ_CFQQ_FLAG_must_alloc_slice,	/* per-slice must_alloc flag */

  	CFQ_CFQQ_FLAG_fifo_expire,	/* FIFO checked in this slice */
  	CFQ_CFQQ_FLAG_idle_window,	/* slice idling enabled */
  	CFQ_CFQQ_FLAG_prio_changed,	/* task priority has changed */

  	CFQ_CFQQ_FLAG_slice_new,	/* no requests dispatched in slice */

  	CFQ_CFQQ_FLAG_sync,		/* synchronous queue */

  	CFQ_CFQQ_FLAG_coop,		/* cfqq is shared */

  	CFQ_CFQQ_FLAG_split_coop,	/* shared cfqq will be splitted */

  	CFQ_CFQQ_FLAG_deep,		/* sync cfqq experienced large depth */

  	CFQ_CFQQ_FLAG_wait_busy,	/* Waiting for next request */

  };
  
  #define CFQ_CFQQ_FNS(name)						\
  static inline void cfq_mark_cfqq_##name(struct cfq_queue *cfqq)		\
  {									\

  	(cfqq)->flags |= (1 << CFQ_CFQQ_FLAG_##name);			\

  }									\
  static inline void cfq_clear_cfqq_##name(struct cfq_queue *cfqq)	\
  {									\

  	(cfqq)->flags &= ~(1 << CFQ_CFQQ_FLAG_##name);			\

  }									\
  static inline int cfq_cfqq_##name(const struct cfq_queue *cfqq)		\
  {									\

  	return ((cfqq)->flags & (1 << CFQ_CFQQ_FLAG_##name)) != 0;	\

  }
  
  CFQ_CFQQ_FNS(on_rr);
  CFQ_CFQQ_FNS(wait_request);

  CFQ_CFQQ_FNS(must_dispatch);

  CFQ_CFQQ_FNS(must_alloc_slice);

  CFQ_CFQQ_FNS(fifo_expire);
  CFQ_CFQQ_FNS(idle_window);
  CFQ_CFQQ_FNS(prio_changed);

  CFQ_CFQQ_FNS(slice_new);

  CFQ_CFQQ_FNS(sync);

  CFQ_CFQQ_FNS(coop);

  CFQ_CFQQ_FNS(split_coop);

  CFQ_CFQQ_FNS(deep);

  CFQ_CFQQ_FNS(wait_busy);

  #undef CFQ_CFQQ_FNS

  #if defined(CONFIG_CFQ_GROUP_IOSCHED) && defined(CONFIG_DEBUG_BLK_CGROUP)

  /* cfqg stats flags */
  enum cfqg_stats_flags {
  	CFQG_stats_waiting = 0,
  	CFQG_stats_idling,
  	CFQG_stats_empty,

  };

  #define CFQG_FLAG_FNS(name)						\
  static inline void cfqg_stats_mark_##name(struct cfqg_stats *stats)	\

  {									\

  	stats->flags |= (1 << CFQG_stats_##name);			\

  }									\

  static inline void cfqg_stats_clear_##name(struct cfqg_stats *stats)	\

  {									\

  	stats->flags &= ~(1 << CFQG_stats_##name);			\

  }									\

  static inline int cfqg_stats_##name(struct cfqg_stats *stats)		\

  {									\

  	return (stats->flags & (1 << CFQG_stats_##name)) != 0;		\

  }									\

  CFQG_FLAG_FNS(waiting)
  CFQG_FLAG_FNS(idling)
  CFQG_FLAG_FNS(empty)
  #undef CFQG_FLAG_FNS

  
  /* This should be called with the queue_lock held. */

  static void cfqg_stats_update_group_wait_time(struct cfqg_stats *stats)

  {
  	unsigned long long now;

  	if (!cfqg_stats_waiting(stats))

  		return;
  
  	now = sched_clock();
  	if (time_after64(now, stats->start_group_wait_time))
  		blkg_stat_add(&stats->group_wait_time,
  			      now - stats->start_group_wait_time);

  	cfqg_stats_clear_waiting(stats);

  }
  
  /* This should be called with the queue_lock held. */

  static void cfqg_stats_set_start_group_wait_time(struct cfq_group *cfqg,
  						 struct cfq_group *curr_cfqg)

  {

  	struct cfqg_stats *stats = &cfqg->stats;

  	if (cfqg_stats_waiting(stats))

  		return;

  	if (cfqg == curr_cfqg)

  		return;

  	stats->start_group_wait_time = sched_clock();
  	cfqg_stats_mark_waiting(stats);

  }
  
  /* This should be called with the queue_lock held. */

  static void cfqg_stats_end_empty_time(struct cfqg_stats *stats)

  {
  	unsigned long long now;

  	if (!cfqg_stats_empty(stats))

  		return;
  
  	now = sched_clock();
  	if (time_after64(now, stats->start_empty_time))
  		blkg_stat_add(&stats->empty_time,
  			      now - stats->start_empty_time);

  	cfqg_stats_clear_empty(stats);

  }

  static void cfqg_stats_update_dequeue(struct cfq_group *cfqg)

  {

  	blkg_stat_add(&cfqg->stats.dequeue, 1);

  }

  static void cfqg_stats_set_start_empty_time(struct cfq_group *cfqg)

  {

  	struct cfqg_stats *stats = &cfqg->stats;

  	if (blkg_rwstat_total(&stats->queued))

  		return;
  
  	/*
  	 * group is already marked empty. This can happen if cfqq got new
  	 * request in parent group and moved to this group while being added
  	 * to service tree. Just ignore the event and move on.
  	 */

  	if (cfqg_stats_empty(stats))

  		return;
  
  	stats->start_empty_time = sched_clock();

  	cfqg_stats_mark_empty(stats);

  }

  static void cfqg_stats_update_idle_time(struct cfq_group *cfqg)

  {

  	struct cfqg_stats *stats = &cfqg->stats;

  	if (cfqg_stats_idling(stats)) {

  		unsigned long long now = sched_clock();
  
  		if (time_after64(now, stats->start_idle_time))
  			blkg_stat_add(&stats->idle_time,
  				      now - stats->start_idle_time);

  		cfqg_stats_clear_idling(stats);

  	}
  }

  static void cfqg_stats_set_start_idle_time(struct cfq_group *cfqg)

  {

  	struct cfqg_stats *stats = &cfqg->stats;

  	BUG_ON(cfqg_stats_idling(stats));

  
  	stats->start_idle_time = sched_clock();

  	cfqg_stats_mark_idling(stats);

  }

  static void cfqg_stats_update_avg_queue_size(struct cfq_group *cfqg)

  {

  	struct cfqg_stats *stats = &cfqg->stats;

  
  	blkg_stat_add(&stats->avg_queue_size_sum,

  		      blkg_rwstat_total(&stats->queued));

  	blkg_stat_add(&stats->avg_queue_size_samples, 1);

  	cfqg_stats_update_group_wait_time(stats);

  }
  
  #else	/* CONFIG_CFQ_GROUP_IOSCHED && CONFIG_DEBUG_BLK_CGROUP */

  static inline void cfqg_stats_set_start_group_wait_time(struct cfq_group *cfqg, struct cfq_group *curr_cfqg) { }
  static inline void cfqg_stats_end_empty_time(struct cfqg_stats *stats) { }
  static inline void cfqg_stats_update_dequeue(struct cfq_group *cfqg) { }
  static inline void cfqg_stats_set_start_empty_time(struct cfq_group *cfqg) { }
  static inline void cfqg_stats_update_idle_time(struct cfq_group *cfqg) { }
  static inline void cfqg_stats_set_start_idle_time(struct cfq_group *cfqg) { }
  static inline void cfqg_stats_update_avg_queue_size(struct cfq_group *cfqg) { }

  
  #endif	/* CONFIG_CFQ_GROUP_IOSCHED && CONFIG_DEBUG_BLK_CGROUP */
  
  #ifdef CONFIG_CFQ_GROUP_IOSCHED

  static inline struct cfq_group *pd_to_cfqg(struct blkg_policy_data *pd)
  {
  	return pd ? container_of(pd, struct cfq_group, pd) : NULL;
  }
  
  static struct cfq_group_data
  *cpd_to_cfqgd(struct blkcg_policy_data *cpd)
  {

  	return cpd ? container_of(cpd, struct cfq_group_data, cpd) : NULL;

  }
  
  static inline struct blkcg_gq *cfqg_to_blkg(struct cfq_group *cfqg)
  {
  	return pd_to_blkg(&cfqg->pd);
  }

  static struct blkcg_policy blkcg_policy_cfq;
  
  static inline struct cfq_group *blkg_to_cfqg(struct blkcg_gq *blkg)
  {
  	return pd_to_cfqg(blkg_to_pd(blkg, &blkcg_policy_cfq));
  }

  static struct cfq_group_data *blkcg_to_cfqgd(struct blkcg *blkcg)
  {
  	return cpd_to_cfqgd(blkcg_to_cpd(blkcg, &blkcg_policy_cfq));
  }

  static inline struct cfq_group *cfqg_parent(struct cfq_group *cfqg)

  {

  	struct blkcg_gq *pblkg = cfqg_to_blkg(cfqg)->parent;

  	return pblkg ? blkg_to_cfqg(pblkg) : NULL;

  }

  static inline bool cfqg_is_descendant(struct cfq_group *cfqg,
  				      struct cfq_group *ancestor)
  {
  	return cgroup_is_descendant(cfqg_to_blkg(cfqg)->blkcg->css.cgroup,
  				    cfqg_to_blkg(ancestor)->blkcg->css.cgroup);
  }

  static inline void cfqg_get(struct cfq_group *cfqg)
  {
  	return blkg_get(cfqg_to_blkg(cfqg));
  }
  
  static inline void cfqg_put(struct cfq_group *cfqg)
  {
  	return blkg_put(cfqg_to_blkg(cfqg));
  }

  #define cfq_log_cfqq(cfqd, cfqq, fmt, args...)	do {			\
  	char __pbuf[128];						\
  									\
  	blkg_path(cfqg_to_blkg((cfqq)->cfqg), __pbuf, sizeof(__pbuf));	\

  	blk_add_trace_msg((cfqd)->queue, "cfq%d%c%c %s " fmt, (cfqq)->pid, \
  			cfq_cfqq_sync((cfqq)) ? 'S' : 'A',		\
  			cfqq_type((cfqq)) == SYNC_NOIDLE_WORKLOAD ? 'N' : ' ',\

  			  __pbuf, ##args);				\
  } while (0)
  
  #define cfq_log_cfqg(cfqd, cfqg, fmt, args...)	do {			\
  	char __pbuf[128];						\
  									\
  	blkg_path(cfqg_to_blkg(cfqg), __pbuf, sizeof(__pbuf));		\
  	blk_add_trace_msg((cfqd)->queue, "%s " fmt, __pbuf, ##args);	\
  } while (0)

  static inline void cfqg_stats_update_io_add(struct cfq_group *cfqg,

  					    struct cfq_group *curr_cfqg, int op,
  					    int op_flags)

  {

  	blkg_rwstat_add(&cfqg->stats.queued, op, op_flags, 1);

  	cfqg_stats_end_empty_time(&cfqg->stats);
  	cfqg_stats_set_start_group_wait_time(cfqg, curr_cfqg);

  }

  static inline void cfqg_stats_update_timeslice_used(struct cfq_group *cfqg,

  			uint64_t time, unsigned long unaccounted_time)

  {

  	blkg_stat_add(&cfqg->stats.time, time);

  #ifdef CONFIG_DEBUG_BLK_CGROUP

  	blkg_stat_add(&cfqg->stats.unaccounted_time, unaccounted_time);

  #endif

  }

  static inline void cfqg_stats_update_io_remove(struct cfq_group *cfqg, int op,
  					       int op_flags)

  {

  	blkg_rwstat_add(&cfqg->stats.queued, op, op_flags, -1);

  }

  static inline void cfqg_stats_update_io_merged(struct cfq_group *cfqg, int op,
  					       int op_flags)

  {

  	blkg_rwstat_add(&cfqg->stats.merged, op, op_flags, 1);

  }

  static inline void cfqg_stats_update_completion(struct cfq_group *cfqg,

  			uint64_t start_time, uint64_t io_start_time, int op,
  			int op_flags)

  {

  	struct cfqg_stats *stats = &cfqg->stats;

  	unsigned long long now = sched_clock();

  
  	if (time_after64(now, io_start_time))

  		blkg_rwstat_add(&stats->service_time, op, op_flags,
  				now - io_start_time);

  	if (time_after64(io_start_time, start_time))

  		blkg_rwstat_add(&stats->wait_time, op, op_flags,

  				io_start_time - start_time);

  }

  /* @stats = 0 */
  static void cfqg_stats_reset(struct cfqg_stats *stats)

  {

  	/* queued stats shouldn't be cleared */

  	blkg_rwstat_reset(&stats->merged);
  	blkg_rwstat_reset(&stats->service_time);
  	blkg_rwstat_reset(&stats->wait_time);
  	blkg_stat_reset(&stats->time);
  #ifdef CONFIG_DEBUG_BLK_CGROUP
  	blkg_stat_reset(&stats->unaccounted_time);
  	blkg_stat_reset(&stats->avg_queue_size_sum);
  	blkg_stat_reset(&stats->avg_queue_size_samples);
  	blkg_stat_reset(&stats->dequeue);
  	blkg_stat_reset(&stats->group_wait_time);
  	blkg_stat_reset(&stats->idle_time);
  	blkg_stat_reset(&stats->empty_time);
  #endif
  }

  /* @to += @from */

  static void cfqg_stats_add_aux(struct cfqg_stats *to, struct cfqg_stats *from)

  {
  	/* queued stats shouldn't be cleared */

  	blkg_rwstat_add_aux(&to->merged, &from->merged);
  	blkg_rwstat_add_aux(&to->service_time, &from->service_time);
  	blkg_rwstat_add_aux(&to->wait_time, &from->wait_time);
  	blkg_stat_add_aux(&from->time, &from->time);

  #ifdef CONFIG_DEBUG_BLK_CGROUP

  	blkg_stat_add_aux(&to->unaccounted_time, &from->unaccounted_time);
  	blkg_stat_add_aux(&to->avg_queue_size_sum, &from->avg_queue_size_sum);
  	blkg_stat_add_aux(&to->avg_queue_size_samples, &from->avg_queue_size_samples);
  	blkg_stat_add_aux(&to->dequeue, &from->dequeue);
  	blkg_stat_add_aux(&to->group_wait_time, &from->group_wait_time);
  	blkg_stat_add_aux(&to->idle_time, &from->idle_time);
  	blkg_stat_add_aux(&to->empty_time, &from->empty_time);

  #endif
  }
  
  /*

   * Transfer @cfqg's stats to its parent's aux counts so that the ancestors'

   * recursive stats can still account for the amount used by this cfqg after
   * it's gone.
   */
  static void cfqg_stats_xfer_dead(struct cfq_group *cfqg)
  {
  	struct cfq_group *parent = cfqg_parent(cfqg);
  
  	lockdep_assert_held(cfqg_to_blkg(cfqg)->q->queue_lock);
  
  	if (unlikely(!parent))
  		return;

  	cfqg_stats_add_aux(&parent->stats, &cfqg->stats);

  	cfqg_stats_reset(&cfqg->stats);

  }

  #else	/* CONFIG_CFQ_GROUP_IOSCHED */

  static inline struct cfq_group *cfqg_parent(struct cfq_group *cfqg) { return NULL; }

  static inline bool cfqg_is_descendant(struct cfq_group *cfqg,
  				      struct cfq_group *ancestor)
  {
  	return true;
  }

  static inline void cfqg_get(struct cfq_group *cfqg) { }
  static inline void cfqg_put(struct cfq_group *cfqg) { }

  #define cfq_log_cfqq(cfqd, cfqq, fmt, args...)	\

  	blk_add_trace_msg((cfqd)->queue, "cfq%d%c%c " fmt, (cfqq)->pid,	\
  			cfq_cfqq_sync((cfqq)) ? 'S' : 'A',		\
  			cfqq_type((cfqq)) == SYNC_NOIDLE_WORKLOAD ? 'N' : ' ',\
  				##args)

  #define cfq_log_cfqg(cfqd, cfqg, fmt, args...)		do {} while (0)

  static inline void cfqg_stats_update_io_add(struct cfq_group *cfqg,

  			struct cfq_group *curr_cfqg, int op, int op_flags) { }

  static inline void cfqg_stats_update_timeslice_used(struct cfq_group *cfqg,

  			uint64_t time, unsigned long unaccounted_time) { }

  static inline void cfqg_stats_update_io_remove(struct cfq_group *cfqg, int op,
  			int op_flags) { }
  static inline void cfqg_stats_update_io_merged(struct cfq_group *cfqg, int op,
  			int op_flags) { }

  static inline void cfqg_stats_update_completion(struct cfq_group *cfqg,

  			uint64_t start_time, uint64_t io_start_time, int op,
  			int op_flags) { }

  #endif	/* CONFIG_CFQ_GROUP_IOSCHED */

  #define cfq_log(cfqd, fmt, args...)	\
  	blk_add_trace_msg((cfqd)->queue, "cfq " fmt, ##args)

  /* Traverses through cfq group service trees */
  #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) \

  static inline bool cfq_io_thinktime_big(struct cfq_data *cfqd,
  	struct cfq_ttime *ttime, bool group_idle)
  {

  	u64 slice;

  	if (!sample_valid(ttime->ttime_samples))
  		return false;
  	if (group_idle)
  		slice = cfqd->cfq_group_idle;
  	else
  		slice = cfqd->cfq_slice_idle;
  	return ttime->ttime_mean > slice;
  }

  static inline bool iops_mode(struct cfq_data *cfqd)
  {
  	/*
  	 * If we are not idling on queues and it is a NCQ drive, parallel
  	 * execution of requests is on and measuring time is not possible
  	 * in most of the cases until and unless we drive shallower queue
  	 * depths and that becomes a performance bottleneck. In such cases
  	 * switch to start providing fairness in terms of number of IOs.
  	 */
  	if (!cfqd->cfq_slice_idle && cfqd->hw_tag)
  		return true;
  	else
  		return false;
  }

  static inline enum wl_class_t cfqq_class(struct cfq_queue *cfqq)

  {
  	if (cfq_class_idle(cfqq))
  		return IDLE_WORKLOAD;
  	if (cfq_class_rt(cfqq))
  		return RT_WORKLOAD;
  	return BE_WORKLOAD;
  }

  
  static enum wl_type_t cfqq_type(struct cfq_queue *cfqq)
  {
  	if (!cfq_cfqq_sync(cfqq))
  		return ASYNC_WORKLOAD;
  	if (!cfq_cfqq_idle_window(cfqq))
  		return SYNC_NOIDLE_WORKLOAD;
  	return SYNC_WORKLOAD;
  }

  static inline int cfq_group_busy_queues_wl(enum wl_class_t wl_class,

  					struct cfq_data *cfqd,
  					struct cfq_group *cfqg)

  {

  	if (wl_class == IDLE_WORKLOAD)

  		return cfqg->service_tree_idle.count;

  	return cfqg->service_trees[wl_class][ASYNC_WORKLOAD].count +
  		cfqg->service_trees[wl_class][SYNC_NOIDLE_WORKLOAD].count +
  		cfqg->service_trees[wl_class][SYNC_WORKLOAD].count;

  }

  static inline int cfqg_busy_async_queues(struct cfq_data *cfqd,
  					struct cfq_group *cfqg)
  {

  	return cfqg->service_trees[RT_WORKLOAD][ASYNC_WORKLOAD].count +
  		cfqg->service_trees[BE_WORKLOAD][ASYNC_WORKLOAD].count;

  }

  static void cfq_dispatch_insert(struct request_queue *, struct request *);

  static struct cfq_queue *cfq_get_queue(struct cfq_data *cfqd, bool is_sync,

  				       struct cfq_io_cq *cic, struct bio *bio);

  static inline struct cfq_io_cq *icq_to_cic(struct io_cq *icq)
  {
  	/* cic->icq is the first member, %NULL will convert to %NULL */
  	return container_of(icq, struct cfq_io_cq, icq);
  }

  static inline struct cfq_io_cq *cfq_cic_lookup(struct cfq_data *cfqd,
  					       struct io_context *ioc)
  {
  	if (ioc)
  		return icq_to_cic(ioc_lookup_icq(ioc, cfqd->queue));
  	return NULL;
  }

  static inline struct cfq_queue *cic_to_cfqq(struct cfq_io_cq *cic, bool is_sync)

  {

  	return cic->cfqq[is_sync];

  }

  static inline void cic_set_cfqq(struct cfq_io_cq *cic, struct cfq_queue *cfqq,
  				bool is_sync)

  {

  	cic->cfqq[is_sync] = cfqq;

  }

  static inline struct cfq_data *cic_to_cfqd(struct cfq_io_cq *cic)

  {

  	return cic->icq.q->elevator->elevator_data;

  }

  /*
   * We regard a request as SYNC, if it's either a read or has the SYNC bit
   * set (in which case it could also be direct WRITE).
   */

  static inline bool cfq_bio_sync(struct bio *bio)

  {

  	return bio_data_dir(bio) == READ || (bio->bi_opf & REQ_SYNC);

  }

  /*

   * scheduler run of queue, if there are requests pending and no one in the
   * driver that will restart queueing
   */

  static inline void cfq_schedule_dispatch(struct cfq_data *cfqd)

  {

  	if (cfqd->busy_queues) {
  		cfq_log(cfqd, "schedule dispatch");

  		kblockd_schedule_work(&cfqd->unplug_work);

  	}

  }

  /*

   * Scale schedule slice based on io priority. Use the sync time slice only
   * if a queue is marked sync and has sync io queued. A sync queue with async
   * io only, should not get full sync slice length.
   */

  static inline u64 cfq_prio_slice(struct cfq_data *cfqd, bool sync,

  				 unsigned short prio)

  {

  	u64 base_slice = cfqd->cfq_slice[sync];
  	u64 slice = div_u64(base_slice, CFQ_SLICE_SCALE);

  	WARN_ON(prio >= IOPRIO_BE_NR);

  	return base_slice + (slice * (4 - prio));

  }

  static inline u64

  cfq_prio_to_slice(struct cfq_data *cfqd, struct cfq_queue *cfqq)
  {
  	return cfq_prio_slice(cfqd, cfq_cfqq_sync(cfqq), cfqq->ioprio);

  }

  /**
   * cfqg_scale_charge - scale disk time charge according to cfqg weight
   * @charge: disk time being charged
   * @vfraction: vfraction of the cfqg, fixed point w/ CFQ_SERVICE_SHIFT
   *
   * Scale @charge according to @vfraction, which is in range (0, 1].  The
   * scaling is inversely proportional.
   *
   * scaled = charge / vfraction
   *
   * The result is also in fixed point w/ CFQ_SERVICE_SHIFT.
   */

  static inline u64 cfqg_scale_charge(u64 charge,

  				    unsigned int vfraction)

  {

  	u64 c = charge << CFQ_SERVICE_SHIFT;	/* make it fixed point */

  	/* charge / vfraction */
  	c <<= CFQ_SERVICE_SHIFT;

  	return div_u64(c, vfraction);

  }
  
  static inline u64 max_vdisktime(u64 min_vdisktime, u64 vdisktime)
  {
  	s64 delta = (s64)(vdisktime - min_vdisktime);
  	if (delta > 0)
  		min_vdisktime = vdisktime;
  
  	return min_vdisktime;
  }
  
  static inline u64 min_vdisktime(u64 min_vdisktime, u64 vdisktime)
  {
  	s64 delta = (s64)(vdisktime - min_vdisktime);
  	if (delta < 0)
  		min_vdisktime = vdisktime;
  
  	return min_vdisktime;
  }
  
  static void update_min_vdisktime(struct cfq_rb_root *st)
  {

  	struct cfq_group *cfqg;

  	if (st->left) {
  		cfqg = rb_entry_cfqg(st->left);

  		st->min_vdisktime = max_vdisktime(st->min_vdisktime,
  						  cfqg->vdisktime);

  	}

  }

  /*
   * get averaged number of queues of RT/BE priority.
   * average is updated, with a formula that gives more weight to higher numbers,
   * to quickly follows sudden increases and decrease slowly
   */

  static inline unsigned cfq_group_get_avg_queues(struct cfq_data *cfqd,
  					struct cfq_group *cfqg, bool rt)

  {

  	unsigned min_q, max_q;
  	unsigned mult  = cfq_hist_divisor - 1;
  	unsigned round = cfq_hist_divisor / 2;

  	unsigned busy = cfq_group_busy_queues_wl(rt, cfqd, cfqg);

  	min_q = min(cfqg->busy_queues_avg[rt], busy);
  	max_q = max(cfqg->busy_queues_avg[rt], busy);
  	cfqg->busy_queues_avg[rt] = (mult * max_q + min_q + round) /

  		cfq_hist_divisor;

  	return cfqg->busy_queues_avg[rt];
  }

  static inline u64

  cfq_group_slice(struct cfq_data *cfqd, struct cfq_group *cfqg)
  {

  	return cfqd->cfq_target_latency * cfqg->vfraction >> CFQ_SERVICE_SHIFT;

  }

  static inline u64

  cfq_scaled_cfqq_slice(struct cfq_data *cfqd, struct cfq_queue *cfqq)

  {

  	u64 slice = cfq_prio_to_slice(cfqd, cfqq);

  	if (cfqd->cfq_latency) {

  		/*
  		 * interested queues (we consider only the ones with the same
  		 * priority class in the cfq group)
  		 */
  		unsigned iq = cfq_group_get_avg_queues(cfqd, cfqq->cfqg,
  						cfq_class_rt(cfqq));

  		u64 sync_slice = cfqd->cfq_slice[1];
  		u64 expect_latency = sync_slice * iq;
  		u64 group_slice = cfq_group_slice(cfqd, cfqq->cfqg);

  
  		if (expect_latency > group_slice) {

  			u64 base_low_slice = 2 * cfqd->cfq_slice_idle;
  			u64 low_slice;

  			/* scale low_slice according to IO priority
  			 * and sync vs async */

  			low_slice = div64_u64(base_low_slice*slice, sync_slice);
  			low_slice = min(slice, low_slice);

  			/* the adapted slice value is scaled to fit all iqs
  			 * into the target latency */

  			slice = div64_u64(slice*group_slice, expect_latency);
  			slice = max(slice, low_slice);

  		}
  	}

  	return slice;
  }
  
  static inline void
  cfq_set_prio_slice(struct cfq_data *cfqd, struct cfq_queue *cfqq)
  {

  	u64 slice = cfq_scaled_cfqq_slice(cfqd, cfqq);
  	u64 now = ktime_get_ns();

  	cfqq->slice_start = now;
  	cfqq->slice_end = now + slice;

  	cfqq->allocated_slice = slice;

  	cfq_log_cfqq(cfqd, cfqq, "set_slice=%llu", cfqq->slice_end - now);

  }
  
  /*
   * We need to wrap this check in cfq_cfqq_slice_new(), since ->slice_end
   * isn't valid until the first request from the dispatch is activated
   * and the slice time set.
   */

  static inline bool cfq_slice_used(struct cfq_queue *cfqq)

  {
  	if (cfq_cfqq_slice_new(cfqq))

  		return false;

  	if (ktime_get_ns() < cfqq->slice_end)

  		return false;

  	return true;

  }
  
  /*

   * Lifted from AS - choose which of rq1 and rq2 that is best served now.

   * We choose the request that is closest to the head right now. Distance

   * behind the head is penalized and only allowed to a certain extent.

   */

  static struct request *

  cfq_choose_req(struct cfq_data *cfqd, struct request *rq1, struct request *rq2, sector_t last)

  {

  	sector_t s1, s2, d1 = 0, d2 = 0;

  	unsigned long back_max;

  #define CFQ_RQ1_WRAP	0x01 /* request 1 wraps */
  #define CFQ_RQ2_WRAP	0x02 /* request 2 wraps */
  	unsigned wrap = 0; /* bit mask: requests behind the disk head? */

  	if (rq1 == NULL || rq1 == rq2)
  		return rq2;
  	if (rq2 == NULL)
  		return rq1;

  	if (rq_is_sync(rq1) != rq_is_sync(rq2))
  		return rq_is_sync(rq1) ? rq1 : rq2;

  	if ((rq1->cmd_flags ^ rq2->cmd_flags) & REQ_PRIO)
  		return rq1->cmd_flags & REQ_PRIO ? rq1 : rq2;

  	s1 = blk_rq_pos(rq1);
  	s2 = blk_rq_pos(rq2);

  	/*
  	 * by definition, 1KiB is 2 sectors
  	 */
  	back_max = cfqd->cfq_back_max * 2;
  
  	/*
  	 * Strict one way elevator _except_ in the case where we allow
  	 * short backward seeks which are biased as twice the cost of a
  	 * similar forward seek.
  	 */
  	if (s1 >= last)
  		d1 = s1 - last;
  	else if (s1 + back_max >= last)
  		d1 = (last - s1) * cfqd->cfq_back_penalty;
  	else

  		wrap |= CFQ_RQ1_WRAP;

  
  	if (s2 >= last)
  		d2 = s2 - last;
  	else if (s2 + back_max >= last)
  		d2 = (last - s2) * cfqd->cfq_back_penalty;
  	else

  		wrap |= CFQ_RQ2_WRAP;

  
  	/* Found required data */

  
  	/*
  	 * By doing switch() on the bit mask "wrap" we avoid having to
  	 * check two variables for all permutations: --> faster!
  	 */
  	switch (wrap) {

  	case 0: /* common case for CFQ: rq1 and rq2 not wrapped */

  		if (d1 < d2)

  			return rq1;

  		else if (d2 < d1)

  			return rq2;

  		else {
  			if (s1 >= s2)

  				return rq1;

  			else

  				return rq2;

  		}

  	case CFQ_RQ2_WRAP:

  		return rq1;

  	case CFQ_RQ1_WRAP:

  		return rq2;
  	case (CFQ_RQ1_WRAP|CFQ_RQ2_WRAP): /* both rqs wrapped */

  	default:
  		/*
  		 * Since both rqs are wrapped,
  		 * start with the one that's further behind head
  		 * (--> only *one* back seek required),
  		 * since back seek takes more time than forward.
  		 */
  		if (s1 <= s2)

  			return rq1;

  		else

  			return rq2;

  	}
  }

  /*
   * The below is leftmost cache rbtree addon
   */

  static struct cfq_queue *cfq_rb_first(struct cfq_rb_root *root)

  {

  	/* Service tree is empty */
  	if (!root->count)
  		return NULL;

  	if (!root->left)
  		root->left = rb_first(&root->rb);

  	if (root->left)
  		return rb_entry(root->left, struct cfq_queue, rb_node);
  
  	return NULL;

  }

  static struct cfq_group *cfq_rb_first_group(struct cfq_rb_root *root)
  {
  	if (!root->left)
  		root->left = rb_first(&root->rb);
  
  	if (root->left)
  		return rb_entry_cfqg(root->left);
  
  	return NULL;
  }

  static void rb_erase_init(struct rb_node *n, struct rb_root *root)
  {
  	rb_erase(n, root);
  	RB_CLEAR_NODE(n);
  }

  static void cfq_rb_erase(struct rb_node *n, struct cfq_rb_root *root)
  {
  	if (root->left == n)
  		root->left = NULL;

  	rb_erase_init(n, &root->rb);

  	--root->count;

  }

  /*
   * would be nice to take fifo expire time into account as well
   */

  static struct request *
  cfq_find_next_rq(struct cfq_data *cfqd, struct cfq_queue *cfqq,
  		  struct request *last)

  {

  	struct rb_node *rbnext = rb_next(&last->rb_node);
  	struct rb_node *rbprev = rb_prev(&last->rb_node);

  	struct request *next = NULL, *prev = NULL;

  	BUG_ON(RB_EMPTY_NODE(&last->rb_node));

  
  	if (rbprev)

  		prev = rb_entry_rq(rbprev);

  	if (rbnext)

  		next = rb_entry_rq(rbnext);

  	else {
  		rbnext = rb_first(&cfqq->sort_list);
  		if (rbnext && rbnext != &last->rb_node)

  			next = rb_entry_rq(rbnext);

  	}

  	return cfq_choose_req(cfqd, next, prev, blk_rq_pos(last));

  }

  static u64 cfq_slice_offset(struct cfq_data *cfqd,
  			    struct cfq_queue *cfqq)

  {

  	/*
  	 * just an approximation, should be ok.
  	 */

  	return (cfqq->cfqg->nr_cfqq - 1) * (cfq_prio_slice(cfqd, 1, 0) -

  		       cfq_prio_slice(cfqd, cfq_cfqq_sync(cfqq), cfqq->ioprio));

  }

  static inline s64
  cfqg_key(struct cfq_rb_root *st, struct cfq_group *cfqg)
  {
  	return cfqg->vdisktime - st->min_vdisktime;
  }
  
  static void
  __cfq_group_service_tree_add(struct cfq_rb_root *st, struct cfq_group *cfqg)
  {
  	struct rb_node **node = &st->rb.rb_node;
  	struct rb_node *parent = NULL;
  	struct cfq_group *__cfqg;
  	s64 key = cfqg_key(st, cfqg);
  	int left = 1;
  
  	while (*node != NULL) {
  		parent = *node;
  		__cfqg = rb_entry_cfqg(parent);
  
  		if (key < cfqg_key(st, __cfqg))
  			node = &parent->rb_left;
  		else {
  			node = &parent->rb_right;
  			left = 0;
  		}
  	}
  
  	if (left)
  		st->left = &cfqg->rb_node;
  
  	rb_link_node(&cfqg->rb_node, parent, node);
  	rb_insert_color(&cfqg->rb_node, &st->rb);
  }

  /*
   * This has to be called only on activation of cfqg
   */

  static void

  cfq_update_group_weight(struct cfq_group *cfqg)
  {

  	if (cfqg->new_weight) {

  		cfqg->weight = cfqg->new_weight;

  		cfqg->new_weight = 0;

  	}

  }
  
  static void
  cfq_update_group_leaf_weight(struct cfq_group *cfqg)
  {
  	BUG_ON(!RB_EMPTY_NODE(&cfqg->rb_node));

  
  	if (cfqg->new_leaf_weight) {
  		cfqg->leaf_weight = cfqg->new_leaf_weight;
  		cfqg->new_leaf_weight = 0;
  	}

  }
  
  static void
  cfq_group_service_tree_add(struct cfq_rb_root *st, struct cfq_group *cfqg)
  {

  	unsigned int vfr = 1 << CFQ_SERVICE_SHIFT;	/* start with 1 */

  	struct cfq_group *pos = cfqg;

  	struct cfq_group *parent;

  	bool propagate;
  
  	/* add to the service tree */

  	BUG_ON(!RB_EMPTY_NODE(&cfqg->rb_node));

  	/*
  	 * Update leaf_weight.  We cannot update weight at this point
  	 * because cfqg might already have been activated and is
  	 * contributing its current weight to the parent's child_weight.
  	 */

  	cfq_update_group_leaf_weight(cfqg);

  	__cfq_group_service_tree_add(st, cfqg);

  
  	/*

  	 * Activate @cfqg and calculate the portion of vfraction @cfqg is
  	 * entitled to.  vfraction is calculated by walking the tree
  	 * towards the root calculating the fraction it has at each level.
  	 * The compounded ratio is how much vfraction @cfqg owns.
  	 *
  	 * Start with the proportion tasks in this cfqg has against active
  	 * children cfqgs - its leaf_weight against children_weight.

  	 */
  	propagate = !pos->nr_active++;
  	pos->children_weight += pos->leaf_weight;

  	vfr = vfr * pos->leaf_weight / pos->children_weight;

  	/*
  	 * Compound ->weight walking up the tree.  Both activation and
  	 * vfraction calculation are done in the same loop.  Propagation
  	 * stops once an already activated node is met.  vfraction
  	 * calculation should always continue to the root.
  	 */

  	while ((parent = cfqg_parent(pos))) {

  		if (propagate) {

  			cfq_update_group_weight(pos);

  			propagate = !parent->nr_active++;
  			parent->children_weight += pos->weight;
  		}
  		vfr = vfr * pos->weight / parent->children_weight;

  		pos = parent;
  	}

  
  	cfqg->vfraction = max_t(unsigned, vfr, 1);

  }
  
  static void
  cfq_group_notify_queue_add(struct cfq_data *cfqd, struct cfq_group *cfqg)

  {
  	struct cfq_rb_root *st = &cfqd->grp_service_tree;
  	struct cfq_group *__cfqg;
  	struct rb_node *n;
  
  	cfqg->nr_cfqq++;

  	if (!RB_EMPTY_NODE(&cfqg->rb_node))

  		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 continuously backlogged.

  	 */
  	n = rb_last(&st->rb);
  	if (n) {
  		__cfqg = rb_entry_cfqg(n);
  		cfqg->vdisktime = __cfqg->vdisktime + CFQ_IDLE_DELAY;
  	} else
  		cfqg->vdisktime = st->min_vdisktime;

  	cfq_group_service_tree_add(st, cfqg);
  }

  static void
  cfq_group_service_tree_del(struct cfq_rb_root *st, struct cfq_group *cfqg)
  {

  	struct cfq_group *pos = cfqg;
  	bool propagate;
  
  	/*
  	 * Undo activation from cfq_group_service_tree_add().  Deactivate
  	 * @cfqg and propagate deactivation upwards.
  	 */
  	propagate = !--pos->nr_active;
  	pos->children_weight -= pos->leaf_weight;
  
  	while (propagate) {

  		struct cfq_group *parent = cfqg_parent(pos);

  
  		/* @pos has 0 nr_active at this point */
  		WARN_ON_ONCE(pos->children_weight);

  		pos->vfraction = 0;

  
  		if (!parent)
  			break;
  
  		propagate = !--parent->nr_active;
  		parent->children_weight -= pos->weight;
  		pos = parent;
  	}
  
  	/* remove from the service tree */

  	if (!RB_EMPTY_NODE(&cfqg->rb_node))
  		cfq_rb_erase(&cfqg->rb_node, st);

  }
  
  static void

  cfq_group_notify_queue_del(struct cfq_data *cfqd, struct cfq_group *cfqg)

  {
  	struct cfq_rb_root *st = &cfqd->grp_service_tree;
  
  	BUG_ON(cfqg->nr_cfqq < 1);
  	cfqg->nr_cfqq--;

  	/* If there are other cfq queues under this group, don't delete it */
  	if (cfqg->nr_cfqq)
  		return;

  	cfq_log_cfqg(cfqd, cfqg, "del_from_rr group");

  	cfq_group_service_tree_del(st, cfqg);

  	cfqg->saved_wl_slice = 0;

  	cfqg_stats_update_dequeue(cfqg);

  }

  static inline u64 cfq_cfqq_slice_usage(struct cfq_queue *cfqq,
  				       u64 *unaccounted_time)

  {

  	u64 slice_used;
  	u64 now = ktime_get_ns();

  
  	/*
  	 * Queue got expired before even a single request completed or
  	 * got expired immediately after first request completion.
  	 */

  	if (!cfqq->slice_start || cfqq->slice_start == now) {

  		/*
  		 * Also charge the seek time incurred to the group, otherwise
  		 * if there are mutiple queues in the group, each can dispatch
  		 * a single request on seeky media and cause lots of seek time
  		 * and group will never know it.
  		 */

  		slice_used = max_t(u64, (now - cfqq->dispatch_start),
  					jiffies_to_nsecs(1));

  	} else {

  		slice_used = now - cfqq->slice_start;

  		if (slice_used > cfqq->allocated_slice) {
  			*unaccounted_time = slice_used - cfqq->allocated_slice;

  			slice_used = cfqq->allocated_slice;

  		}

  		if (cfqq->slice_start > cfqq->dispatch_start)

  			*unaccounted_time += cfqq->slice_start -
  					cfqq->dispatch_start;

  	}

  	return slice_used;
  }
  
  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;

  	u64 used_sl, charge, unaccounted_sl = 0;

  	int nr_sync = cfqg->nr_cfqq - cfqg_busy_async_queues(cfqd, cfqg)
  			- cfqg->service_tree_idle.count;