cfq-iosched: reduce bit operations in cfq_choose_req()
[linux-2.6.git] / block / cfq-iosched.c
index 8df4fe5..7ffcedd 100644 (file)
@@ -7,19 +7,20 @@
  *  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/jiffies.h>
 #include <linux/rbtree.h>
 #include <linux/ioprio.h>
 #include <linux/blktrace_api.h>
-#include "blk-cgroup.h"
+#include "cfq.h"
 
 /*
  * tunables
  */
 /* max queue in one round of service */
-static const int cfq_quantum = 4;
+static const int cfq_quantum = 8;
 static const int cfq_fifo_expire[2] = { HZ / 4, HZ / 8 };
 /* maximum backwards seek, in KiB */
 static const int cfq_back_max = 16 * 1024;
@@ -29,6 +30,7 @@ static const int cfq_slice_sync = HZ / 10;
 static int cfq_slice_async = HZ / 25;
 static const int cfq_slice_async_rq = 2;
 static int cfq_slice_idle = HZ / 125;
+static int cfq_group_idle = HZ / 125;
 static const int cfq_target_latency = HZ * 3/10; /* 300 ms */
 static const int cfq_hist_divisor = 4;
 
@@ -42,19 +44,19 @@ static const int cfq_hist_divisor = 4;
  */
 #define CFQ_MIN_TT             (2)
 
-/*
- * Allow merged cfqqs to perform this amount of seeky I/O before
- * deciding to break the queues up again.
- */
-#define CFQQ_COOP_TOUT         (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)             \
-       ((struct cfq_io_context *) (rq)->elevator_private)
-#define RQ_CFQQ(rq)            (struct cfq_queue *) ((rq)->elevator_private2)
+       ((struct cfq_io_context *) (rq)->elevator_private[0])
+#define RQ_CFQQ(rq)            (struct cfq_queue *) ((rq)->elevator_private[1])
+#define RQ_CFQG(rq)            (struct cfq_group *) ((rq)->elevator_private[2])
 
 static struct kmem_cache *cfq_pool;
 static struct kmem_cache *cfq_ioc_pool;
@@ -63,6 +65,9 @@ static DEFINE_PER_CPU(unsigned long, cfq_ioc_count);
 static struct completion *ioc_gone;
 static DEFINE_SPINLOCK(ioc_gone_lock);
 
+static DEFINE_SPINLOCK(cic_index_lock);
+static DEFINE_IDA(cic_index_ida);
+
 #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)
@@ -80,18 +85,18 @@ struct cfq_rb_root {
        struct rb_root rb;
        struct rb_node *left;
        unsigned count;
-       u64 min_vdisktime;
-       struct rb_node *active;
        unsigned total_weight;
+       u64 min_vdisktime;
 };
-#define CFQ_RB_ROOT    (struct cfq_rb_root) { RB_ROOT, NULL, 0, 0, }
+#define CFQ_RB_ROOT    (struct cfq_rb_root) { .rb = RB_ROOT, .left = NULL, \
+                       .count = 0, .min_vdisktime = 0, }
 
 /*
  * Per process-grouping structure
  */
 struct cfq_queue {
        /* reference count */
-       atomic_t ref;
+       int ref;
        /* various state flags, see below */
        unsigned int flags;
        /* parent cfq_data */
@@ -118,11 +123,11 @@ struct cfq_queue {
        /* time when queue got scheduled in to dispatch first request. */
        unsigned long dispatch_start;
        unsigned int allocated_slice;
+       unsigned int slice_dispatch;
        /* time when first request from queue completed and slice started. */
        unsigned long slice_start;
        unsigned long slice_end;
        long slice_resid;
-       unsigned int slice_dispatch;
 
        /* pending metadata requests */
        int meta_pending;
@@ -133,19 +138,15 @@ struct cfq_queue {
        unsigned short ioprio, org_ioprio;
        unsigned short ioprio_class, org_ioprio_class;
 
-       unsigned int seek_samples;
-       u64 seek_total;
-       sector_t seek_mean;
-       sector_t last_request_pos;
-       unsigned long seeky_start;
-
        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;
-       struct cfq_group *orig_cfqg;
-       /* Sectors dispatched in current dispatch round */
+       /* Number of sectors dispatched from queue in single dispatch round */
        unsigned long nr_sectors;
 };
 
@@ -157,6 +158,7 @@ enum wl_prio_t {
        BE_WORKLOAD = 0,
        RT_WORKLOAD = 1,
        IDLE_WORKLOAD = 2,
+       CFQ_PRIO_NR,
 };
 
 /*
@@ -176,15 +178,25 @@ struct cfq_group {
        /* group service_tree key */
        u64 vdisktime;
        unsigned int weight;
-       bool on_st;
+       unsigned int new_weight;
+       bool needs_update;
 
        /* number of cfqq currently on this group */
        int nr_cfqq;
 
-       /* Per group busy queus average. Useful for workload slice calc. */
-       unsigned int busy_queues_avg[2];
        /*
-        * rr lists of queues with requests, onle rr for each priority class.
+        * Per group busy queus 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];
@@ -196,8 +208,10 @@ struct cfq_group {
        struct blkio_group blkg;
 #ifdef CONFIG_CFQ_GROUP_IOSCHED
        struct hlist_node cfqd_node;
-       atomic_t ref;
+       int ref;
 #endif
+       /* number of requests that are on the dispatch list or inside driver */
+       int dispatched;
 };
 
 /*
@@ -216,7 +230,6 @@ struct cfq_data {
        enum wl_type_t serving_type;
        unsigned long workload_expires;
        struct cfq_group *serving_group;
-       bool noidle_tree_requires_idle;
 
        /*
         * Each priority tree is sorted by next_request position.  These
@@ -226,9 +239,10 @@ struct cfq_data {
        struct rb_root prio_trees[CFQ_PRIO_LISTS];
 
        unsigned int busy_queues;
+       unsigned int busy_sync_queues;
 
-       int rq_in_driver[2];
-       int sync_flight;
+       int rq_in_driver;
+       int rq_in_flight[2];
 
        /*
         * queue-depth detection
@@ -271,9 +285,10 @@ struct cfq_data {
        unsigned int cfq_slice[2];
        unsigned int cfq_slice_async_rq;
        unsigned int cfq_slice_idle;
+       unsigned int cfq_group_idle;
        unsigned int cfq_latency;
-       unsigned int cfq_group_isolation;
 
+       unsigned int cic_index;
        struct list_head cic_list;
 
        /*
@@ -285,7 +300,9 @@ struct cfq_data {
 
        /* List of cfq groups being managed on this device*/
        struct hlist_head cfqg_list;
-       struct rcu_head rcu;
+
+       /* Number of groups which are on blkcg->blkg_list */
+       unsigned int nr_blkcg_linked_grps;
 };
 
 static struct cfq_group *cfq_get_next_cfqg(struct cfq_data *cfqd);
@@ -314,6 +331,7 @@ enum cfqq_state_flags {
        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 */
 };
@@ -342,11 +360,12 @@ 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
 
-#ifdef CONFIG_DEBUG_CFQ_IOSCHED
+#ifdef CONFIG_CFQ_GROUP_IOSCHED
 #define cfq_log_cfqq(cfqd, cfqq, fmt, args...) \
        blk_add_trace_msg((cfqd)->queue, "cfq%d%c %s " fmt, (cfqq)->pid, \
                        cfq_cfqq_sync((cfqq)) ? 'S' : 'A', \
@@ -375,6 +394,21 @@ CFQ_CFQQ_FNS(wait_busy);
                        &cfqg->service_trees[i][j]: NULL) \
 
 
+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_prio_t cfqq_prio(struct cfq_queue *cfqq)
 {
        if (cfq_class_idle(cfqq))
@@ -419,11 +453,6 @@ static struct cfq_queue *cfq_get_queue(struct cfq_data *, bool,
 static struct cfq_io_context *cfq_cic_lookup(struct cfq_data *,
                                                struct io_context *);
 
-static inline int rq_in_driver(struct cfq_data *cfqd)
-{
-       return cfqd->rq_in_driver[0] + cfqd->rq_in_driver[1];
-}
-
 static inline struct cfq_queue *cic_to_cfqq(struct cfq_io_context *cic,
                                            bool is_sync)
 {
@@ -436,13 +465,31 @@ static inline void cic_set_cfqq(struct cfq_io_context *cic,
        cic->cfqq[is_sync] = cfqq;
 }
 
+#define CIC_DEAD_KEY   1ul
+#define CIC_DEAD_INDEX_SHIFT   1
+
+static inline void *cfqd_dead_key(struct cfq_data *cfqd)
+{
+       return (void *)(cfqd->cic_index << CIC_DEAD_INDEX_SHIFT | CIC_DEAD_KEY);
+}
+
+static inline struct cfq_data *cic_to_cfqd(struct cfq_io_context *cic)
+{
+       struct cfq_data *cfqd = cic->key;
+
+       if (unlikely((unsigned long) cfqd & CIC_DEAD_KEY))
+               return NULL;
+
+       return cfqd;
+}
+
 /*
  * 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_rw_flagged(bio, BIO_RW_SYNCIO);
+       return bio_data_dir(bio) == READ || (bio->bi_rw & REQ_SYNC);
 }
 
 /*
@@ -457,13 +504,6 @@ static inline void cfq_schedule_dispatch(struct cfq_data *cfqd)
        }
 }
 
-static int cfq_queue_empty(struct request_queue *q)
-{
-       struct cfq_data *cfqd = q->elevator->elevator_data;
-
-       return !cfqd->rq_queued;
-}
-
 /*
  * 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
@@ -514,20 +554,13 @@ 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;
 
-       if (st->active) {
-               cfqg = rb_entry_cfqg(st->active);
-               vdisktime = cfqg->vdisktime;
-       }
-
        if (st->left) {
                cfqg = rb_entry_cfqg(st->left);
-               vdisktime = min_vdisktime(vdisktime, cfqg->vdisktime);
+               st->min_vdisktime = max_vdisktime(st->min_vdisktime,
+                                                 cfqg->vdisktime);
        }
-
-       st->min_vdisktime = max_vdisktime(st->min_vdisktime, vdisktime);
 }
 
 /*
@@ -559,8 +592,8 @@ cfq_group_slice(struct cfq_data *cfqd, struct cfq_group *cfqg)
        return cfq_target_latency * cfqg->weight / st->total_weight;
 }
 
-static inline void
-cfq_set_prio_slice(struct cfq_data *cfqd, struct cfq_queue *cfqq)
+static inline unsigned
+cfq_scaled_cfqq_slice(struct cfq_data *cfqd, struct cfq_queue *cfqq)
 {
        unsigned slice = cfq_prio_to_slice(cfqd, cfqq);
        if (cfqd->cfq_latency) {
@@ -586,6 +619,14 @@ cfq_set_prio_slice(struct cfq_data *cfqd, struct cfq_queue *cfqq)
                                    low_slice);
                }
        }
+       return slice;
+}
+
+static inline void
+cfq_set_prio_slice(struct cfq_data *cfqd, struct cfq_queue *cfqq)
+{
+       unsigned slice = cfq_scaled_cfqq_slice(cfqd, cfqq);
+
        cfqq->slice_start = jiffies;
        cfqq->slice_end = jiffies + slice;
        cfqq->allocated_slice = slice;
@@ -600,11 +641,11 @@ cfq_set_prio_slice(struct cfq_data *cfqd, struct cfq_queue *cfqq)
 static inline bool cfq_slice_used(struct cfq_queue *cfqq)
 {
        if (cfq_cfqq_slice_new(cfqq))
-               return 0;
+               return false;
        if (time_before(jiffies, cfqq->slice_end))
-               return 0;
+               return false;
 
-       return 1;
+       return true;
 }
 
 /*
@@ -626,14 +667,11 @@ cfq_choose_req(struct cfq_data *cfqd, struct request *rq1, struct request *rq2,
        if (rq2 == NULL)
                return rq1;
 
-       if (rq_is_sync(rq1) && !rq_is_sync(rq2))
-               return rq1;
-       else if (rq_is_sync(rq2) && !rq_is_sync(rq1))
-               return rq2;
-       if (rq_is_meta(rq1) && !rq_is_meta(rq2))
-               return rq1;
-       else if (rq_is_meta(rq2) && !rq_is_meta(rq1))
-               return rq2;
+       if (rq_is_sync(rq1) != rq_is_sync(rq2))
+               return rq_is_sync(rq1) ? rq1 : rq2;
+
+       if ((rq1->cmd_flags ^ rq2->cmd_flags) & REQ_META)
+               return rq1->cmd_flags & REQ_META ? rq1 : rq2;
 
        s1 = blk_rq_pos(rq1);
        s2 = blk_rq_pos(rq2);
@@ -815,20 +853,40 @@ __cfq_group_service_tree_add(struct cfq_rb_root *st, struct cfq_group *cfqg)
 }
 
 static void
-cfq_group_service_tree_add(struct cfq_data *cfqd, struct cfq_group *cfqg)
+cfq_update_group_weight(struct cfq_group *cfqg)
+{
+       BUG_ON(!RB_EMPTY_NODE(&cfqg->rb_node));
+       if (cfqg->needs_update) {
+               cfqg->weight = cfqg->new_weight;
+               cfqg->needs_update = false;
+       }
+}
+
+static void
+cfq_group_service_tree_add(struct cfq_rb_root *st, struct cfq_group *cfqg)
+{
+       BUG_ON(!RB_EMPTY_NODE(&cfqg->rb_node));
+
+       cfq_update_group_weight(cfqg);
+       __cfq_group_service_tree_add(st, cfqg);
+       st->total_weight += cfqg->weight;
+}
+
+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 (cfqg->on_st)
+       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 continously backlogged.
+        * if group does not loose all if it was not continuously backlogged.
         */
        n = rb_last(&st->rb);
        if (n) {
@@ -836,20 +894,22 @@ cfq_group_service_tree_add(struct cfq_data *cfqd, struct cfq_group *cfqg)
                cfqg->vdisktime = __cfqg->vdisktime + CFQ_IDLE_DELAY;
        } else
                cfqg->vdisktime = st->min_vdisktime;
+       cfq_group_service_tree_add(st, cfqg);
+}
 
-       __cfq_group_service_tree_add(st, cfqg);
-       cfqg->on_st = true;
-       st->total_weight += cfqg->weight;
+static void
+cfq_group_service_tree_del(struct cfq_rb_root *st, struct cfq_group *cfqg)
+{
+       st->total_weight -= cfqg->weight;
+       if (!RB_EMPTY_NODE(&cfqg->rb_node))
+               cfq_rb_erase(&cfqg->rb_node, st);
 }
 
 static void
-cfq_group_service_tree_del(struct cfq_data *cfqd, struct cfq_group *cfqg)
+cfq_group_notify_queue_del(struct cfq_data *cfqd, struct cfq_group *cfqg)
 {
        struct cfq_rb_root *st = &cfqd->grp_service_tree;
 
-       if (st->active == &cfqg->rb_node)
-               st->active = NULL;
-
        BUG_ON(cfqg->nr_cfqq < 1);
        cfqg->nr_cfqq--;
 
@@ -858,15 +918,13 @@ cfq_group_service_tree_del(struct cfq_data *cfqd, struct cfq_group *cfqg)
                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);
+       cfq_group_service_tree_del(st, cfqg);
        cfqg->saved_workload_slice = 0;
-       blkiocg_update_blkio_group_dequeue_stats(&cfqg->blkg, 1);
+       cfq_blkiocg_update_dequeue_stats(&cfqg->blkg, 1);
 }
 
-static inline unsigned int cfq_cfqq_slice_usage(struct cfq_queue *cfqq)
+static inline unsigned int cfq_cfqq_slice_usage(struct cfq_queue *cfqq,
+                                               unsigned int *unaccounted_time)
 {
        unsigned int slice_used;
 
@@ -885,12 +943,15 @@ static inline unsigned int cfq_cfqq_slice_usage(struct cfq_queue *cfqq)
                                        1);
        } else {
                slice_used = jiffies - cfqq->slice_start;
-               if (slice_used > cfqq->allocated_slice)
+               if (slice_used > cfqq->allocated_slice) {
+                       *unaccounted_time = slice_used - cfqq->allocated_slice;
                        slice_used = cfqq->allocated_slice;
+               }
+               if (time_after(cfqq->slice_start, cfqq->dispatch_start))
+                       *unaccounted_time += cfqq->slice_start -
+                                       cfqq->dispatch_start;
        }
 
-       cfq_log_cfqq(cfqq->cfqd, cfqq, "sl_used=%u sect=%lu", slice_used,
-                               cfqq->nr_sectors);
        return slice_used;
 }
 
@@ -898,20 +959,23 @@ 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;
-       unsigned int used_sl, charge_sl;
+       unsigned int used_sl, charge, unaccounted_sl = 0;
        int nr_sync = cfqg->nr_cfqq - cfqg_busy_async_queues(cfqd, cfqg)
                        - cfqg->service_tree_idle.count;
 
        BUG_ON(nr_sync < 0);
-       used_sl = charge_sl = cfq_cfqq_slice_usage(cfqq);
+       used_sl = charge = cfq_cfqq_slice_usage(cfqq, &unaccounted_sl);
 
-       if (!cfq_cfqq_sync(cfqq) && !nr_sync)
-               charge_sl = cfqq->allocated_slice;
+       if (iops_mode(cfqd))
+               charge = cfqq->slice_dispatch;
+       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_sl, cfqg);
-       __cfq_group_service_tree_add(st, cfqg);
+       cfq_group_service_tree_del(st, cfqg);
+       cfqg->vdisktime += cfq_scale_slice(charge, cfqg);
+       /* If a new weight was requested, update now, off tree */
+       cfq_group_service_tree_add(st, cfqg);
 
        /* This group is being expired. Save the context */
        if (time_after(cfqd->workload_expires, jiffies)) {
@@ -924,8 +988,12 @@ static void cfq_group_served(struct cfq_data *cfqd, struct cfq_group *cfqg,
 
        cfq_log_cfqg(cfqd, cfqg, "served: vt=%llu min_vt=%llu", cfqg->vdisktime,
                                        st->min_vdisktime);
-       blkiocg_update_blkio_group_stats(&cfqg->blkg, used_sl,
-                                               cfqq->nr_sectors);
+       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);
+       cfq_blkiocg_update_timeslice_used(&cfqg->blkg, used_sl,
+                                         unaccounted_sl);
+       cfq_blkiocg_set_start_empty_time(&cfqg->blkg);
 }
 
 #ifdef CONFIG_CFQ_GROUP_IOSCHED
@@ -936,36 +1004,56 @@ static inline struct cfq_group *cfqg_of_blkg(struct blkio_group *blkg)
        return NULL;
 }
 
-void
-cfq_update_blkio_group_weight(struct blkio_group *blkg, unsigned int weight)
+void cfq_update_blkio_group_weight(void *key, struct blkio_group *blkg,
+                                       unsigned int weight)
 {
-       cfqg_of_blkg(blkg)->weight = weight;
+       struct cfq_group *cfqg = cfqg_of_blkg(blkg);
+       cfqg->new_weight = weight;
+       cfqg->needs_update = true;
 }
 
-static struct cfq_group *
-cfq_find_alloc_cfqg(struct cfq_data *cfqd, struct cgroup *cgroup, int create)
+static void cfq_init_add_cfqg_lists(struct cfq_data *cfqd,
+                       struct cfq_group *cfqg, struct blkio_cgroup *blkcg)
 {
-       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;
 
-       /* Do we need to take this reference */
-       if (!blkiocg_css_tryget(blkcg))
-               return NULL;;
+       /*
+        * Add group onto cgroup list. It might happen that bdi->dev is
+        * not initialized yet. Initialize this new group without major
+        * and minor info and this info will be filled in once a new thread
+        * comes for IO.
+        */
+       if (bdi->dev) {
+               sscanf(dev_name(bdi->dev), "%u:%u", &major, &minor);
+               cfq_blkiocg_add_blkio_group(blkcg, &cfqg->blkg,
+                                       (void *)cfqd, MKDEV(major, minor));
+       } else
+               cfq_blkiocg_add_blkio_group(blkcg, &cfqg->blkg,
+                                       (void *)cfqd, 0);
+
+       cfqd->nr_blkcg_linked_grps++;
+       cfqg->weight = blkcg_get_weight(blkcg, cfqg->blkg.dev);
 
-       cfqg = cfqg_of_blkg(blkiocg_lookup_group(blkcg, key));
-       if (cfqg || !create)
-               goto done;
+       /* Add group on cfqd list */
+       hlist_add_head(&cfqg->cfqd_node, &cfqd->cfqg_list);
+}
+
+/*
+ * Should be called from sleepable context. No request queue lock as per
+ * cpu stats are allocated dynamically and alloc_percpu needs to be called
+ * from sleepable context.
+ */
+static struct cfq_group * cfq_alloc_cfqg(struct cfq_data *cfqd)
+{
+       struct cfq_group *cfqg = NULL;
+       int i, j, ret;
+       struct cfq_rb_root *st;
 
        cfqg = kzalloc_node(sizeof(*cfqg), GFP_ATOMIC, cfqd->queue->node);
        if (!cfqg)
-               goto done;
+               return NULL;
 
-       cfqg->weight = blkcg->weight;
        for_each_cfqg_st(cfqg, i, j, st)
                *st = CFQ_RB_ROOT;
        RB_CLEAR_NODE(&cfqg->rb_node);
@@ -976,39 +1064,106 @@ cfq_find_alloc_cfqg(struct cfq_data *cfqd, struct cgroup *cgroup, int create)
         * elevator which will be dropped by either elevator exit
         * or cgroup deletion path depending on who is exiting first.
         */
-       atomic_set(&cfqg->ref, 1);
+       cfqg->ref = 1;
 
-       /* Add group onto cgroup list */
-       sscanf(dev_name(bdi->dev), "%u:%u", &major, &minor);
-       blkiocg_add_blkio_group(blkcg, &cfqg->blkg, (void *)cfqd,
-                                       MKDEV(major, minor));
+       ret = blkio_alloc_blkg_stats(&cfqg->blkg);
+       if (ret) {
+               kfree(cfqg);
+               return NULL;
+       }
 
-       /* Add group on cfqd list */
-       hlist_add_head(&cfqg->cfqd_node, &cfqd->cfqg_list);
+       return cfqg;
+}
+
+static struct cfq_group *
+cfq_find_cfqg(struct cfq_data *cfqd, struct blkio_cgroup *blkcg)
+{
+       struct cfq_group *cfqg = NULL;
+       void *key = cfqd;
+       struct backing_dev_info *bdi = &cfqd->queue->backing_dev_info;
+       unsigned int major, minor;
+
+       /*
+        * This is the common case when there are no blkio cgroups.
+        * Avoid lookup in this case
+        */
+       if (blkcg == &blkio_root_cgroup)
+               cfqg = &cfqd->root_group;
+       else
+               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);
+       }
 
-done:
-       blkiocg_css_put(blkcg);
        return cfqg;
 }
 
 /*
- * Search for the cfq group current task belongs to. If create = 1, then also
- * create the cfq group if it does not exist. request_queue lock must be held.
+ * Search for the cfq group current task belongs to. request_queue lock must
+ * be held.
  */
-static struct cfq_group *cfq_get_cfqg(struct cfq_data *cfqd, int create)
+static struct cfq_group *cfq_get_cfqg(struct cfq_data *cfqd)
 {
-       struct cgroup *cgroup;
-       struct cfq_group *cfqg = NULL;
+       struct blkio_cgroup *blkcg;
+       struct cfq_group *cfqg = NULL, *__cfqg = NULL;
+       struct request_queue *q = cfqd->queue;
 
        rcu_read_lock();
-       cgroup = task_cgroup(current, blkio_subsys_id);
-       cfqg = cfq_find_alloc_cfqg(cfqd, cgroup, create);
-       if (!cfqg && create)
+       blkcg = task_blkio_cgroup(current);
+       cfqg = cfq_find_cfqg(cfqd, blkcg);
+       if (cfqg) {
+               rcu_read_unlock();
+               return cfqg;
+       }
+
+       /*
+        * Need to allocate a group. Allocation of group also needs allocation
+        * of per cpu stats which in-turn takes a mutex() and can block. Hence
+        * we need to drop rcu lock and queue_lock before we call alloc.
+        *
+        * Not taking any queue reference here and assuming that queue is
+        * around by the time we return. CFQ queue allocation code does
+        * the same. It might be racy though.
+        */
+
+       rcu_read_unlock();
+       spin_unlock_irq(q->queue_lock);
+
+       cfqg = cfq_alloc_cfqg(cfqd);
+
+       spin_lock_irq(q->queue_lock);
+
+       rcu_read_lock();
+       blkcg = task_blkio_cgroup(current);
+
+       /*
+        * If some other thread already allocated the group while we were
+        * not holding queue lock, free up the group
+        */
+       __cfqg = cfq_find_cfqg(cfqd, blkcg);
+
+       if (__cfqg) {
+               kfree(cfqg);
+               rcu_read_unlock();
+               return __cfqg;
+       }
+
+       if (!cfqg)
                cfqg = &cfqd->root_group;
+
+       cfq_init_add_cfqg_lists(cfqd, cfqg, blkcg);
        rcu_read_unlock();
        return cfqg;
 }
 
+static inline struct cfq_group *cfq_ref_get_cfqg(struct cfq_group *cfqg)
+{
+       cfqg->ref++;
+       return cfqg;
+}
+
 static void cfq_link_cfqq_cfqg(struct cfq_queue *cfqq, struct cfq_group *cfqg)
 {
        /* Currently, all async queues are mapped to root group */
@@ -1017,7 +1172,7 @@ static void cfq_link_cfqq_cfqg(struct cfq_queue *cfqq, struct cfq_group *cfqg)
 
        cfqq->cfqg = cfqg;
        /* cfqq reference on cfqg */
-       atomic_inc(&cfqq->cfqg->ref);
+       cfqq->cfqg->ref++;
 }
 
 static void cfq_put_cfqg(struct cfq_group *cfqg)
@@ -1025,11 +1180,13 @@ 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))
+       BUG_ON(cfqg->ref <= 0);
+       cfqg->ref--;
+       if (cfqg->ref)
                return;
        for_each_cfqg_st(cfqg, i, j, st)
-               BUG_ON(!RB_EMPTY_ROOT(&st->rb) || st->active != NULL);
+               BUG_ON(!RB_EMPTY_ROOT(&st->rb));
+       free_percpu(cfqg->blkg.stats_cpu);
        kfree(cfqg);
 }
 
@@ -1058,7 +1215,7 @@ static void cfq_release_cfq_groups(struct cfq_data *cfqd)
                 * it from cgroup list, then it will take care of destroying
                 * cfqg also.
                 */
-               if (!blkiocg_del_blkio_group(&cfqg->blkg))
+               if (!cfq_blkiocg_del_blkio_group(&cfqg->blkg))
                        cfq_destroy_cfqg(cfqd, cfqg);
        }
 }
@@ -1088,10 +1245,16 @@ void cfq_unlink_blkio_group(void *key, struct blkio_group *blkg)
 }
 
 #else /* GROUP_IOSCHED */
-static struct cfq_group *cfq_get_cfqg(struct cfq_data *cfqd, int create)
+static struct cfq_group *cfq_get_cfqg(struct cfq_data *cfqd)
 {
        return &cfqd->root_group;
 }
+
+static inline struct cfq_group *cfq_ref_get_cfqg(struct cfq_group *cfqg)
+{
+       return cfqg;
+}
+
 static inline void
 cfq_link_cfqq_cfqg(struct cfq_queue *cfqq, struct cfq_group *cfqg) {
        cfqq->cfqg = cfqg;
@@ -1118,32 +1281,6 @@ static void cfq_service_tree_add(struct cfq_data *cfqd, struct cfq_queue *cfqq,
        int new_cfqq = 1;
        int group_changed = 0;
 
-#ifdef CONFIG_CFQ_GROUP_IOSCHED
-       if (!cfqd->cfq_group_isolation
-           && cfqq_type(cfqq) == SYNC_NOIDLE_WORKLOAD
-           && cfqq->cfqg && cfqq->cfqg != &cfqd->root_group) {
-               /* Move this cfq to root group */
-               cfq_log_cfqq(cfqd, cfqq, "moving to root group");
-               if (!RB_EMPTY_NODE(&cfqq->rb_node))
-                       cfq_group_service_tree_del(cfqd, cfqq->cfqg);
-               cfqq->orig_cfqg = cfqq->cfqg;
-               cfqq->cfqg = &cfqd->root_group;
-               atomic_inc(&cfqd->root_group.ref);
-               group_changed = 1;
-       } else if (!cfqd->cfq_group_isolation
-                  && cfqq_type(cfqq) == SYNC_WORKLOAD && cfqq->orig_cfqg) {
-               /* cfqq is sequential now needs to go to its original group */
-               BUG_ON(cfqq->cfqg != &cfqd->root_group);
-               if (!RB_EMPTY_NODE(&cfqq->rb_node))
-                       cfq_group_service_tree_del(cfqd, cfqq->cfqg);
-               cfq_put_cfqg(cfqq->cfqg);
-               cfqq->cfqg = cfqq->orig_cfqg;
-               cfqq->orig_cfqg = NULL;
-               group_changed = 1;
-               cfq_log_cfqq(cfqd, cfqq, "moved to origin group");
-       }
-#endif
-
        service_tree = service_tree_for(cfqq->cfqg, cfqq_prio(cfqq),
                                                cfqq_type(cfqq));
        if (cfq_class_idle(cfqq)) {
@@ -1215,7 +1352,7 @@ static void cfq_service_tree_add(struct cfq_data *cfqd, struct cfq_queue *cfqq,
        service_tree->count++;
        if ((add_front || !new_cfqq) && !group_changed)
                return;
-       cfq_group_service_tree_add(cfqd, cfqq->cfqg);
+       cfq_group_notify_queue_add(cfqd, cfqq->cfqg);
 }
 
 static struct cfq_queue *
@@ -1303,6 +1440,8 @@ 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_cfqq_sync(cfqq))
+               cfqd->busy_sync_queues++;
 
        cfq_resort_rr_list(cfqd, cfqq);
 }
@@ -1326,9 +1465,11 @@ static void cfq_del_cfqq_rr(struct cfq_data *cfqd, struct cfq_queue *cfqq)
                cfqq->p_root = NULL;
        }
 
-       cfq_group_service_tree_del(cfqd, cfqq->cfqg);
+       cfq_group_notify_queue_del(cfqd, cfqq->cfqg);
        BUG_ON(!cfqd->busy_queues);
        cfqd->busy_queues--;
+       if (cfq_cfqq_sync(cfqq))
+               cfqd->busy_sync_queues--;
 }
 
 /*
@@ -1394,7 +1535,12 @@ static void cfq_reposition_rq_rb(struct cfq_queue *cfqq, struct request *rq)
 {
        elv_rb_del(&cfqq->sort_list, rq);
        cfqq->queued[rq_is_sync(rq)]--;
+       cfq_blkiocg_update_io_remove_stats(&(RQ_CFQG(rq))->blkg,
+                                       rq_data_dir(rq), rq_is_sync(rq));
        cfq_add_rq_rb(rq);
+       cfq_blkiocg_update_io_add_stats(&(RQ_CFQG(rq))->blkg,
+                       &cfqq->cfqd->serving_group->blkg, rq_data_dir(rq),
+                       rq_is_sync(rq));
 }
 
 static struct request *
@@ -1422,9 +1568,9 @@ static void cfq_activate_request(struct request_queue *q, struct request *rq)
 {
        struct cfq_data *cfqd = q->elevator->elevator_data;
 
-       cfqd->rq_in_driver[rq_is_sync(rq)]++;
+       cfqd->rq_in_driver++;
        cfq_log_cfqq(cfqd, RQ_CFQQ(rq), "activate rq, drv=%d",
-                                               rq_in_driver(cfqd));
+                                               cfqd->rq_in_driver);
 
        cfqd->last_position = blk_rq_pos(rq) + blk_rq_sectors(rq);
 }
@@ -1432,12 +1578,11 @@ static void cfq_activate_request(struct request_queue *q, struct request *rq)
 static void cfq_deactivate_request(struct request_queue *q, struct request *rq)
 {
        struct cfq_data *cfqd = q->elevator->elevator_data;
-       const int sync = rq_is_sync(rq);
 
-       WARN_ON(!cfqd->rq_in_driver[sync]);
-       cfqd->rq_in_driver[sync]--;
+       WARN_ON(!cfqd->rq_in_driver);
+       cfqd->rq_in_driver--;
        cfq_log_cfqq(cfqd, RQ_CFQQ(rq), "deactivate rq, drv=%d",
-                                               rq_in_driver(cfqd));
+                                               cfqd->rq_in_driver);
 }
 
 static void cfq_remove_request(struct request *rq)
@@ -1451,7 +1596,9 @@ static void cfq_remove_request(struct request *rq)
        cfq_del_rq_rb(rq);
 
        cfqq->cfqd->rq_queued--;
-       if (rq_is_meta(rq)) {
+       cfq_blkiocg_update_io_remove_stats(&(RQ_CFQG(rq))->blkg,
+                                       rq_data_dir(rq), rq_is_sync(rq));
+       if (rq->cmd_flags & REQ_META) {
                WARN_ON(!cfqq->meta_pending);
                cfqq->meta_pending--;
        }
@@ -1482,6 +1629,13 @@ static void cfq_merged_request(struct request_queue *q, struct request *req,
        }
 }
 
+static void cfq_bio_merged(struct request_queue *q, struct request *req,
+                               struct bio *bio)
+{
+       cfq_blkiocg_update_io_merged_stats(&(RQ_CFQG(req))->blkg,
+                                       bio_data_dir(bio), cfq_bio_sync(bio));
+}
+
 static void
 cfq_merged_requests(struct request_queue *q, struct request *rq,
                    struct request *next)
@@ -1499,6 +1653,8 @@ cfq_merged_requests(struct request_queue *q, struct request *rq,
        if (cfqq->next_rq == next)
                cfqq->next_rq = rq;
        cfq_remove_request(next);
+       cfq_blkiocg_update_io_merged_stats(&(RQ_CFQG(rq))->blkg,
+                                       rq_data_dir(next), rq_is_sync(next));
 }
 
 static int cfq_allow_merge(struct request_queue *q, struct request *rq,
@@ -1526,11 +1682,19 @@ static int cfq_allow_merge(struct request_queue *q, struct request *rq,
        return cfqq == RQ_CFQQ(rq);
 }
 
+static inline void cfq_del_timer(struct cfq_data *cfqd, struct cfq_queue *cfqq)
+{
+       del_timer(&cfqd->idle_slice_timer);
+       cfq_blkiocg_update_idle_time_stats(&cfqq->cfqg->blkg);
+}
+
 static void __cfq_set_active_queue(struct cfq_data *cfqd,
                                   struct cfq_queue *cfqq)
 {
        if (cfqq) {
-               cfq_log_cfqq(cfqd, cfqq, "set_active");
+               cfq_log_cfqq(cfqd, cfqq, "set_active wl_prio:%d wl_type:%d",
+                               cfqd->serving_prio, cfqd->serving_type);
+               cfq_blkiocg_update_avg_queue_size_stats(&cfqq->cfqg->blkg);
                cfqq->slice_start = 0;
                cfqq->dispatch_start = jiffies;
                cfqq->allocated_slice = 0;
@@ -1544,7 +1708,7 @@ static void __cfq_set_active_queue(struct cfq_data *cfqd,
                cfq_clear_cfqq_fifo_expire(cfqq);
                cfq_mark_cfqq_slice_new(cfqq);
 
-               del_timer(&cfqd->idle_slice_timer);
+               cfq_del_timer(cfqd, cfqq);
        }
 
        cfqd->active_queue = cfqq;
@@ -1560,16 +1724,28 @@ __cfq_slice_expired(struct cfq_data *cfqd, struct cfq_queue *cfqq,
        cfq_log_cfqq(cfqd, cfqq, "slice expired t=%d", timed_out);
 
        if (cfq_cfqq_wait_request(cfqq))
-               del_timer(&cfqd->idle_slice_timer);
+               cfq_del_timer(cfqd, cfqq);
 
        cfq_clear_cfqq_wait_request(cfqq);
        cfq_clear_cfqq_wait_busy(cfqq);
 
        /*
+        * If this cfqq is shared between multiple processes, check to
+        * make sure that those processes are still issuing I/Os within
+        * the mean seek distance.  If not, it may be time to break the
+        * queues apart again.
+        */
+       if (cfq_cfqq_coop(cfqq) && CFQQ_SEEKY(cfqq))
+               cfq_mark_cfqq_split_coop(cfqq);
+
+       /*
         * store what was left of this slice, if the queue idled/timed out
         */
-       if (timed_out && !cfq_cfqq_slice_new(cfqq)) {
-               cfqq->slice_resid = cfqq->slice_end - jiffies;
+       if (timed_out) {
+               if (cfq_cfqq_slice_new(cfqq))
+                       cfqq->slice_resid = cfq_scaled_cfqq_slice(cfqd, cfqq);
+               else
+                       cfqq->slice_resid = cfqq->slice_end - jiffies;
                cfq_log_cfqq(cfqd, cfqq, "resid=%ld", cfqq->slice_resid);
        }
 
@@ -1583,9 +1759,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;
@@ -1663,18 +1836,10 @@ static inline sector_t cfq_dist_from_last(struct cfq_data *cfqd,
                return cfqd->last_position - blk_rq_pos(rq);
 }
 
-#define CFQQ_SEEK_THR          8 * 1024
-#define CFQQ_SEEKY(cfqq)       ((cfqq)->seek_mean > CFQQ_SEEK_THR)
-
 static inline int cfq_rq_close(struct cfq_data *cfqd, struct cfq_queue *cfqq,
                               struct request *rq)
 {
-       sector_t sdist = cfqq->seek_mean;
-
-       if (!sample_valid(cfqq->seek_samples))
-               sdist = CFQQ_SEEK_THR;
-
-       return cfq_dist_from_last(cfqd, rq) <= sdist;
+       return cfq_dist_from_last(cfqd, rq) <= CFQQ_CLOSE_THR;
 }
 
 static struct cfq_queue *cfqq_close(struct cfq_data *cfqd,
@@ -1733,6 +1898,8 @@ static struct cfq_queue *cfq_close_cooperator(struct cfq_data *cfqd,
 {
        struct cfq_queue *cfqq;
 
+       if (cfq_class_idle(cur_cfqq))
+               return NULL;
        if (!cfq_cfqq_sync(cur_cfqq))
                return NULL;
        if (CFQQ_SEEKY(cur_cfqq))
@@ -1786,6 +1953,9 @@ static bool cfq_should_idle(struct cfq_data *cfqd, struct cfq_queue *cfqq)
        BUG_ON(!service_tree);
        BUG_ON(!service_tree->count);
 
+       if (!cfqd->cfq_slice_idle)
+               return false;
+
        /* We never do for idle class queues. */
        if (prio == IDLE_WORKLOAD)
                return false;
@@ -1799,14 +1969,18 @@ static bool cfq_should_idle(struct cfq_data *cfqd, struct cfq_queue *cfqq)
         * Otherwise, we do only if they are the last ones
         * in their service tree.
         */
-       return service_tree->count == 1;
+       if (service_tree->count == 1 && cfq_cfqq_sync(cfqq))
+               return true;
+       cfq_log_cfqq(cfqd, cfqq, "Not idling. st->count:%d",
+                       service_tree->count);
+       return false;
 }
 
 static void cfq_arm_slice_timer(struct cfq_data *cfqd)
 {
        struct cfq_queue *cfqq = cfqd->active_queue;
        struct cfq_io_context *cic;
-       unsigned long sl;
+       unsigned long sl, group_idle = 0;
 
        /*
         * SSD device without seek penalty, disable idling. But only do so
@@ -1822,8 +1996,13 @@ static void cfq_arm_slice_timer(struct cfq_data *cfqd)
        /*
         * idle is disabled, either manually or by past process history
         */
-       if (!cfqd->cfq_slice_idle || !cfq_should_idle(cfqd, cfqq))
-               return;
+       if (!cfq_should_idle(cfqd, cfqq)) {
+               /* no queue idling. Check for group idling */
+               if (cfqd->cfq_group_idle)
+                       group_idle = cfqd->cfq_group_idle;
+               else
+                       return;
+       }
 
        /*
         * still active requests from this queue, don't idle
@@ -1844,15 +2023,27 @@ static void cfq_arm_slice_timer(struct cfq_data *cfqd)
         * time slice.
         */
        if (sample_valid(cic->ttime_samples) &&
-           (cfqq->slice_end - jiffies < cic->ttime_mean))
+           (cfqq->slice_end - jiffies < cic->ttime_mean)) {
+               cfq_log_cfqq(cfqd, cfqq, "Not idling. think_time:%d",
+                               cic->ttime_mean);
+               return;
+       }
+
+       /* There are other queues in the group, don't do group idle */
+       if (group_idle && cfqq->cfqg->nr_cfqq > 1)
                return;
 
        cfq_mark_cfqq_wait_request(cfqq);
 
-       sl = cfqd->cfq_slice_idle;
+       if (group_idle)
+               sl = cfqd->cfq_group_idle;
+       else
+               sl = cfqd->cfq_slice_idle;
 
        mod_timer(&cfqd->idle_slice_timer, jiffies + sl);
-       cfq_log_cfqq(cfqd, cfqq, "arm_idle: %lu", sl);
+       cfq_blkiocg_update_set_idle_time_stats(&cfqq->cfqg->blkg);
+       cfq_log_cfqq(cfqd, cfqq, "arm_idle: %lu group_idle: %d", sl,
+                       group_idle ? 1 : 0);
 }
 
 /*
@@ -1868,11 +2059,13 @@ static void cfq_dispatch_insert(struct request_queue *q, struct request *rq)
        cfqq->next_rq = cfq_find_next_rq(cfqd, cfqq, rq);
        cfq_remove_request(rq);
        cfqq->dispatched++;
+       (RQ_CFQG(rq))->dispatched++;
        elv_dispatch_sort(q, rq);
 
-       if (cfq_cfqq_sync(cfqq))
-               cfqd->sync_flight++;
+       cfqd->rq_in_flight[cfq_cfqq_sync(cfqq)]++;
        cfqq->nr_sectors += blk_rq_sectors(rq);
+       cfq_blkiocg_update_dispatch_stats(&cfqq->cfqg->blkg, blk_rq_bytes(rq),
+                                       rq_data_dir(rq), rq_is_sync(rq));
 }
 
 /*
@@ -1905,7 +2098,7 @@ cfq_prio_to_maxrq(struct cfq_data *cfqd, struct cfq_queue *cfqq)
 
        WARN_ON(cfqq->ioprio >= IOPRIO_BE_NR);
 
-       return 2 * (base_rq + base_rq * (CFQ_PRIO_LISTS - 1 - cfqq->ioprio));
+       return 2 * base_rq * (IOPRIO_BE_NR - cfqq->ioprio);
 }
 
 /*
@@ -1916,7 +2109,7 @@ static int cfqq_process_refs(struct cfq_queue *cfqq)
        int process_refs, io_refs;
 
        io_refs = cfqq->allocated[READ] + cfqq->allocated[WRITE];
-       process_refs = atomic_read(&cfqq->ref) - io_refs;
+       process_refs = cfqq->ref - io_refs;
        BUG_ON(process_refs < 0);
        return process_refs;
 }
@@ -1926,6 +2119,15 @@ static void cfq_setup_merge(struct cfq_queue *cfqq, struct cfq_queue *new_cfqq)
        int process_refs, new_process_refs;
        struct cfq_queue *__cfqq;
 
+       /*
+        * If there are no process references on the new_cfqq, then it is
+        * unsafe to follow the ->new_cfqq chain as other cfqq's in the
+        * chain may have dropped their last reference (not just their
+        * last process reference).
+        */
+       if (!cfqq_process_refs(new_cfqq))
+               return;
+
        /* Avoid a circular list and skip interim queue merges */
        while ((__cfqq = new_cfqq->new_cfqq)) {
                if (__cfqq == cfqq)
@@ -1934,23 +2136,23 @@ static void cfq_setup_merge(struct cfq_queue *cfqq, struct cfq_queue *new_cfqq)
        }
 
        process_refs = cfqq_process_refs(cfqq);
+       new_process_refs = cfqq_process_refs(new_cfqq);
        /*
         * If the process for the cfqq has gone away, there is no
         * sense in merging the queues.
         */
-       if (process_refs == 0)
+       if (process_refs == 0 || new_process_refs == 0)
                return;
 
        /*
         * Merge in the direction of the lesser amount of work.
         */
-       new_process_refs = cfqq_process_refs(new_cfqq);
        if (new_process_refs >= process_refs) {
                cfqq->new_cfqq = new_cfqq;
-               atomic_add(process_refs, &new_cfqq->ref);
+               new_cfqq->ref += process_refs;
        } else {
                new_cfqq->new_cfqq = cfqq;
-               atomic_add(new_process_refs, &cfqq->ref);
+               cfqq->ref += new_process_refs;
        }
 }
 
@@ -1983,12 +2185,7 @@ static void choose_service_tree(struct cfq_data *cfqd, struct cfq_group *cfqg)
        unsigned count;
        struct cfq_rb_root *st;
        unsigned group_slice;
-
-       if (!cfqg) {
-               cfqd->serving_prio = IDLE_WORKLOAD;
-               cfqd->workload_expires = jiffies + 1;
-               return;
-       }
+       enum wl_prio_t original_prio = cfqd->serving_prio;
 
        /* Choose next priority. RT > BE > IDLE */
        if (cfq_group_busy_queues_wl(RT_WORKLOAD, cfqd, cfqg))
@@ -2001,6 +2198,9 @@ static void choose_service_tree(struct cfq_data *cfqd, struct cfq_group *cfqg)
                return;
        }
 
+       if (original_prio != cfqd->serving_prio)
+               goto new_workload;
+
        /*
         * For RT and BE, we have to choose also the type
         * (SYNC, SYNC_NOIDLE, ASYNC), and to compute a workload
@@ -2015,6 +2215,7 @@ static void choose_service_tree(struct cfq_data *cfqd, struct cfq_group *cfqg)
        if (count && !time_after(jiffies, cfqd->workload_expires))
                return;
 
+new_workload:
        /* otherwise select new workload type */
        cfqd->serving_type =
                cfq_choose_wl(cfqd, cfqg, cfqd->serving_prio);
@@ -2054,8 +2255,8 @@ static void choose_service_tree(struct cfq_data *cfqd, struct cfq_group *cfqg)
                slice = max(slice, 2 * cfqd->cfq_slice_idle);
 
        slice = max_t(unsigned, slice, CFQ_MIN_TT);
+       cfq_log(cfqd, "workload slice:%d", slice);
        cfqd->workload_expires = jiffies + slice;
-       cfqd->noidle_tree_requires_idle = false;
 }
 
 static struct cfq_group *cfq_get_next_cfqg(struct cfq_data *cfqd)
@@ -2066,7 +2267,6 @@ static struct cfq_group *cfq_get_next_cfqg(struct cfq_data *cfqd)
        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;
 }
@@ -2127,7 +2327,7 @@ static struct cfq_queue *cfq_select_queue(struct cfq_data *cfqd)
                        cfqq = NULL;
                        goto keep_queue;
                } else
-                       goto expire;
+                       goto check_group_idle;
        }
 
        /*
@@ -2155,8 +2355,34 @@ static struct cfq_queue *cfq_select_queue(struct cfq_data *cfqd)
         * flight or is idling for a new request, allow either of these
         * conditions to happen (or time out) before selecting a new queue.
         */
-       if (timer_pending(&cfqd->idle_slice_timer) ||
-           (cfqq->dispatched && cfq_should_idle(cfqd, cfqq))) {
+       if (timer_pending(&cfqd->idle_slice_timer)) {
+               cfqq = NULL;
+               goto keep_queue;
+       }
+
+       /*
+        * This is a deep seek queue, but the device is much faster than
+        * the queue can deliver, don't idle
+        **/
+       if (CFQQ_SEEKY(cfqq) && cfq_cfqq_idle_window(cfqq) &&
+           (cfq_cfqq_slice_new(cfqq) ||
+           (cfqq->slice_end - jiffies > jiffies - cfqq->slice_start))) {
+               cfq_clear_cfqq_deep(cfqq);
+               cfq_clear_cfqq_idle_window(cfqq);
+       }
+
+       if (cfqq->dispatched && cfq_should_idle(cfqd, cfqq)) {
+               cfqq = NULL;
+               goto keep_queue;
+       }
+
+       /*
+        * If group idle is enabled and there are requests dispatched from
+        * this group, wait for requests to complete.
+        */
+check_group_idle:
+       if (cfqd->cfq_group_idle && cfqq->cfqg->nr_cfqq == 1
+           && cfqq->cfqg->dispatched) {
                cfqq = NULL;
                goto keep_queue;
        }
@@ -2201,16 +2427,32 @@ static int cfq_forced_dispatch(struct cfq_data *cfqd)
        struct cfq_queue *cfqq;
        int dispatched = 0;
 
-       while ((cfqq = cfq_get_next_queue_forced(cfqd)) != NULL)
+       /* Expire the timeslice of the current active queue first */
+       cfq_slice_expired(cfqd, 0);
+       while ((cfqq = cfq_get_next_queue_forced(cfqd)) != NULL) {
+               __cfq_set_active_queue(cfqd, cfqq);
                dispatched += __cfq_forced_dispatch_cfqq(cfqq);
+       }
 
-       cfq_slice_expired(cfqd, 0);
        BUG_ON(cfqd->busy_queues);
 
        cfq_log(cfqd, "forced_dispatch=%d", dispatched);
        return dispatched;
 }
 
+static inline bool cfq_slice_used_soon(struct cfq_data *cfqd,
+       struct cfq_queue *cfqq)
+{
+       /* the queue hasn't finished any request, can't estimate */
+       if (cfq_cfqq_slice_new(cfqq))
+               return true;
+       if (time_after(jiffies + cfqd->cfq_slice_idle * cfqq->dispatched,
+               cfqq->slice_end))
+               return true;
+
+       return false;
+}
+
 static bool cfq_may_dispatch(struct cfq_data *cfqd, struct cfq_queue *cfqq)
 {
        unsigned int max_dispatch;
@@ -2218,16 +2460,16 @@ static bool cfq_may_dispatch(struct cfq_data *cfqd, struct cfq_queue *cfqq)
        /*
         * Drain async requests before we start sync IO
         */
-       if (cfq_should_idle(cfqd, cfqq) && cfqd->rq_in_driver[BLK_RW_ASYNC])
+       if (cfq_should_idle(cfqd, cfqq) && cfqd->rq_in_flight[BLK_RW_ASYNC])
                return false;
 
        /*
         * If this is an async queue and we have sync IO in flight, let it wait
         */
-       if (cfqd->sync_flight && !cfq_cfqq_sync(cfqq))
+       if (cfqd->rq_in_flight[BLK_RW_SYNC] && !cfq_cfqq_sync(cfqq))
                return false;
 
-       max_dispatch = cfqd->cfq_quantum;
+       max_dispatch = max_t(unsigned int, cfqd->cfq_quantum / 2, 1);
        if (cfq_class_idle(cfqq))
                max_dispatch = 1;
 
@@ -2235,6 +2477,7 @@ static bool cfq_may_dispatch(struct cfq_data *cfqd, struct cfq_queue *cfqq)
         * Does this cfqq already have too much IO in flight?
         */
        if (cfqq->dispatched >= max_dispatch) {
+               bool promote_sync = false;
                /*
                 * idle queue must always only have a single IO in flight
                 */
@@ -2242,15 +2485,35 @@ static bool cfq_may_dispatch(struct cfq_data *cfqd, struct cfq_queue *cfqq)
                        return false;
 
                /*
+                * If there is only one sync queue
+                * we can ignore async queue here and give the sync
+                * queue no dispatch limit. The reason is a sync queue can
+                * preempt async queue, limiting the sync queue doesn't make
+                * sense. This is useful for aiostress test.
+                */
+               if (cfq_cfqq_sync(cfqq) && cfqd->busy_sync_queues == 1)
+                       promote_sync = true;
+
+               /*
                 * We have other queues, don't allow more IO from this one
                 */
-               if (cfqd->busy_queues > 1)
+               if (cfqd->busy_queues > 1 && cfq_slice_used_soon(cfqd, cfqq) &&
+                               !promote_sync)
                        return false;
 
                /*
                 * Sole queue user, no limit
                 */
-               max_dispatch = -1;
+               if (cfqd->busy_queues == 1 || promote_sync)
+                       max_dispatch = -1;
+               else
+                       /*
+                        * Normally we start throttling cfqq when cfq_quantum/2
+                        * requests have been dispatched. But we can drive
+                        * deeper queue depths at the beginning of slice
+                        * subjected to upper limit of cfq_quantum.
+                        * */
+                       max_dispatch = cfqd->cfq_quantum;
        }
 
        /*
@@ -2363,18 +2626,18 @@ static int cfq_dispatch_requests(struct request_queue *q, int force)
 static void cfq_put_queue(struct cfq_queue *cfqq)
 {
        struct cfq_data *cfqd = cfqq->cfqd;
-       struct cfq_group *cfqg, *orig_cfqg;
+       struct cfq_group *cfqg;
 
-       BUG_ON(atomic_read(&cfqq->ref) <= 0);
+       BUG_ON(cfqq->ref <= 0);
 
-       if (!atomic_dec_and_test(&cfqq->ref))
+       cfqq->ref--;
+       if (cfqq->ref)
                return;
 
        cfq_log_cfqq(cfqd, cfqq, "put_queue");
        BUG_ON(rb_first(&cfqq->sort_list));
        BUG_ON(cfqq->allocated[READ] + cfqq->allocated[WRITE]);
        cfqg = cfqq->cfqg;
-       orig_cfqg = cfqq->orig_cfqg;
 
        if (unlikely(cfqd->active_queue == cfqq)) {
                __cfq_slice_expired(cfqd, cfqq, 0);
@@ -2384,33 +2647,23 @@ static void cfq_put_queue(struct cfq_queue *cfqq)
        BUG_ON(cfq_cfqq_on_rr(cfqq));
        kmem_cache_free(cfq_pool, cfqq);
        cfq_put_cfqg(cfqg);
-       if (orig_cfqg)
-               cfq_put_cfqg(orig_cfqg);
 }
 
 /*
- * Must always be called with the rcu_read_lock() held
+ * Call func for each cic attached to this ioc.
  */
 static void
-__call_for_each_cic(struct io_context *ioc,
-                   void (*func)(struct io_context *, struct cfq_io_context *))
+call_for_each_cic(struct io_context *ioc,
+                 void (*func)(struct io_context *, struct cfq_io_context *))
 {
        struct cfq_io_context *cic;
        struct hlist_node *n;
 
+       rcu_read_lock();
+
        hlist_for_each_entry_rcu(cic, n, &ioc->cic_list, cic_list)
                func(ioc, cic);
-}
 
-/*
- * Call func for each cic attached to this ioc.
- */
-static void
-call_for_each_cic(struct io_context *ioc,
-                 void (*func)(struct io_context *, struct cfq_io_context *))
-{
-       rcu_read_lock();
-       __call_for_each_cic(ioc, func);
        rcu_read_unlock();
 }
 
@@ -2446,11 +2699,12 @@ static void cfq_cic_free(struct cfq_io_context *cic)
 static void cic_free_func(struct io_context *ioc, struct cfq_io_context *cic)
 {
        unsigned long flags;
+       unsigned long dead_key = (unsigned long) cic->key;
 
-       BUG_ON(!cic->dead_key);
+       BUG_ON(!(dead_key & CIC_DEAD_KEY));
 
        spin_lock_irqsave(&ioc->lock, flags);
-       radix_tree_delete(&ioc->radix_root, cic->dead_key);
+       radix_tree_delete(&ioc->radix_root, dead_key >> CIC_DEAD_INDEX_SHIFT);
        hlist_del_rcu(&cic->cic_list);
        spin_unlock_irqrestore(&ioc->lock, flags);
 
@@ -2470,18 +2724,13 @@ static void cfq_free_io_context(struct io_context *ioc)
         * should be ok to iterate over the known list, we will see all cic's
         * since no new ones are added.
         */
-       __call_for_each_cic(ioc, cic_free_func);
+       call_for_each_cic(ioc, cic_free_func);
 }
 
-static void cfq_exit_cfqq(struct cfq_data *cfqd, struct cfq_queue *cfqq)
+static void cfq_put_cooperator(struct cfq_queue *cfqq)
 {
        struct cfq_queue *__cfqq, *next;
 
-       if (unlikely(cfqq == cfqd->active_queue)) {
-               __cfq_slice_expired(cfqd, cfqq, 0);
-               cfq_schedule_dispatch(cfqd);
-       }
-
        /*
         * If this queue was scheduled to merge with another queue, be
         * sure to drop the reference taken on that queue (and others in
@@ -2497,6 +2746,16 @@ static void cfq_exit_cfqq(struct cfq_data *cfqd, struct cfq_queue *cfqq)
                cfq_put_queue(__cfqq);
                __cfqq = next;
        }
+}
+
+static void cfq_exit_cfqq(struct cfq_data *cfqd, struct cfq_queue *cfqq)
+{
+       if (unlikely(cfqq == cfqd->active_queue)) {
+               __cfq_slice_expired(cfqd, cfqq, 0);
+               cfq_schedule_dispatch(cfqd);
+       }
+
+       cfq_put_cooperator(cfqq);
 
        cfq_put_queue(cfqq);
 }
@@ -2509,11 +2768,10 @@ static void __cfq_exit_single_io_context(struct cfq_data *cfqd,
        list_del_init(&cic->queue_list);
 
        /*
-        * Make sure key == NULL is seen for dead queues
+        * Make sure dead mark is seen for dead queues
         */
        smp_wmb();
-       cic->dead_key = (unsigned long) cic->key;
-       cic->key = NULL;
+       cic->key = cfqd_dead_key(cfqd);
 
        if (ioc->ioc_data == cic)
                rcu_assign_pointer(ioc->ioc_data, NULL);
@@ -2532,7 +2790,7 @@ static void __cfq_exit_single_io_context(struct cfq_data *cfqd,
 static void cfq_exit_single_io_context(struct io_context *ioc,
                                       struct cfq_io_context *cic)
 {
-       struct cfq_data *cfqd = cic->key;
+       struct cfq_data *cfqd = cic_to_cfqd(cic);
 
        if (cfqd) {
                struct request_queue *q = cfqd->queue;
@@ -2545,7 +2803,7 @@ static void cfq_exit_single_io_context(struct io_context *ioc,
                 * race between exiting task and queue
                 */
                smp_read_barrier_depends();
-               if (cic->key)
+               if (cic->key == cfqd)
                        __cfq_exit_single_io_context(cfqd, cic);
 
                spin_unlock_irqrestore(q->queue_lock, flags);
@@ -2625,7 +2883,7 @@ static void cfq_init_prio_data(struct cfq_queue *cfqq, struct io_context *ioc)
 
 static void changed_ioprio(struct io_context *ioc, struct cfq_io_context *cic)
 {
-       struct cfq_data *cfqd = cic->key;
+       struct cfq_data *cfqd = cic_to_cfqd(cic);
        struct cfq_queue *cfqq;
        unsigned long flags;
 
@@ -2665,7 +2923,7 @@ static void cfq_init_cfqq(struct cfq_data *cfqd, struct cfq_queue *cfqq,
        RB_CLEAR_NODE(&cfqq->p_node);
        INIT_LIST_HEAD(&cfqq->fifo);
 
-       atomic_set(&cfqq->ref, 0);
+       cfqq->ref = 0;
        cfqq->cfqd = cfqd;
 
        cfq_mark_cfqq_prio_changed(cfqq);
@@ -2682,7 +2940,7 @@ static void cfq_init_cfqq(struct cfq_data *cfqd, struct cfq_queue *cfqq,
 static void changed_cgroup(struct io_context *ioc, struct cfq_io_context *cic)
 {
        struct cfq_queue *sync_cfqq = cic_to_cfqq(cic, 1);
-       struct cfq_data *cfqd = cic->key;
+       struct cfq_data *cfqd = cic_to_cfqd(cic);
        unsigned long flags;
        struct request_queue *q;
 
@@ -2722,7 +2980,7 @@ cfq_find_alloc_queue(struct cfq_data *cfqd, bool is_sync,
        struct cfq_group *cfqg;
 
 retry:
-       cfqg = cfq_get_cfqg(cfqd, 1);
+       cfqg = cfq_get_cfqg(cfqd);
        cic = cfq_cic_lookup(cfqd, ioc);
        /* cic always exists here */
        cfqq = cic_to_cfqq(cic, is_sync);
@@ -2801,11 +3059,11 @@ cfq_get_queue(struct cfq_data *cfqd, bool is_sync, struct io_context *ioc,
         * pin the queue now that it's allocated, scheduler exit will prune it
         */
        if (!is_sync && !(*async_cfqq)) {
-               atomic_inc(&cfqq->ref);
+               cfqq->ref++;
                *async_cfqq = cfqq;
        }
 
-       atomic_inc(&cfqq->ref);
+       cfqq->ref++;
        return cfqq;
 }
 
@@ -2819,12 +3077,13 @@ cfq_drop_dead_cic(struct cfq_data *cfqd, struct io_context *ioc,
        unsigned long flags;
 
        WARN_ON(!list_empty(&cic->queue_list));
+       BUG_ON(cic->key != cfqd_dead_key(cfqd));
 
        spin_lock_irqsave(&ioc->lock, flags);
 
        BUG_ON(ioc->ioc_data == cic);
 
-       radix_tree_delete(&ioc->radix_root, (unsigned long) cfqd);
+       radix_tree_delete(&ioc->radix_root, cfqd->cic_index);
        hlist_del_rcu(&cic->cic_list);
        spin_unlock_irqrestore(&ioc->lock, flags);
 
@@ -2836,7 +3095,6 @@ cfq_cic_lookup(struct cfq_data *cfqd, struct io_context *ioc)
 {
        struct cfq_io_context *cic;
        unsigned long flags;
-       void *k;
 
        if (unlikely(!ioc))
                return NULL;
@@ -2853,13 +3111,11 @@ cfq_cic_lookup(struct cfq_data *cfqd, struct io_context *ioc)
        }
 
        do {
-               cic = radix_tree_lookup(&ioc->radix_root, (unsigned long) cfqd);
+               cic = radix_tree_lookup(&ioc->radix_root, cfqd->cic_index);
                rcu_read_unlock();
                if (!cic)
                        break;
-               /* ->key must be copied to avoid race with cfq_exit_queue() */
-               k = cic->key;
-               if (unlikely(!k)) {
+               if (unlikely(cic->key != cfqd)) {
                        cfq_drop_dead_cic(cfqd, ioc, cic);
                        rcu_read_lock();
                        continue;
@@ -2892,7 +3148,7 @@ static int cfq_cic_link(struct cfq_data *cfqd, struct io_context *ioc,
 
                spin_lock_irqsave(&ioc->lock, flags);
                ret = radix_tree_insert(&ioc->radix_root,
-                                               (unsigned long) cfqd, cic);
+                                               cfqd->cic_index, cic);
                if (!ret)
                        hlist_add_head_rcu(&cic->cic_list, &ioc->cic_list);
                spin_unlock_irqrestore(&ioc->lock, flags);
@@ -2972,43 +3228,20 @@ static void
 cfq_update_io_seektime(struct cfq_data *cfqd, struct cfq_queue *cfqq,
                       struct request *rq)
 {
-       sector_t sdist;
-       u64 total;
+       sector_t sdist = 0;
+       sector_t n_sec = blk_rq_sectors(rq);
+       if (cfqq->last_request_pos) {
+               if (cfqq->last_request_pos < blk_rq_pos(rq))
+                       sdist = blk_rq_pos(rq) - cfqq->last_request_pos;
+               else
+                       sdist = cfqq->last_request_pos - blk_rq_pos(rq);
+       }
 
-       if (!cfqq->last_request_pos)
-               sdist = 0;
-       else if (cfqq->last_request_pos < blk_rq_pos(rq))
-               sdist = blk_rq_pos(rq) - cfqq->last_request_pos;
+       cfqq->seek_history <<= 1;
+       if (blk_queue_nonrot(cfqd->queue))
+               cfqq->seek_history |= (n_sec < CFQQ_SECT_THR_NONROT);
        else
-               sdist = cfqq->last_request_pos - blk_rq_pos(rq);
-
-       /*
-        * Don't allow the seek distance to get too large from the
-        * odd fragment, pagein, etc
-        */
-       if (cfqq->seek_samples <= 60) /* second&third seek */
-               sdist = min(sdist, (cfqq->seek_mean * 4) + 2*1024*1024);
-       else
-               sdist = min(sdist, (cfqq->seek_mean * 4) + 2*1024*64);
-
-       cfqq->seek_samples = (7*cfqq->seek_samples + 256) / 8;
-       cfqq->seek_total = (7*cfqq->seek_total + (u64)256*sdist) / 8;
-       total = cfqq->seek_total + (cfqq->seek_samples/2);
-       do_div(total, cfqq->seek_samples);
-       cfqq->seek_mean = (sector_t)total;
-
-       /*
-        * If this cfqq is shared between multiple processes, check to
-        * make sure that those processes are still issuing I/Os within
-        * the mean seek distance.  If not, it may be time to break the
-        * queues apart again.
-        */
-       if (cfq_cfqq_coop(cfqq)) {
-               if (CFQQ_SEEKY(cfqq) && !cfqq->seeky_start)
-                       cfqq->seeky_start = jiffies;
-               else if (!CFQQ_SEEKY(cfqq))
-                       cfqq->seeky_start = 0;
-       }
+               cfqq->seek_history |= (sdist > CFQQ_SEEK_THR);
 }
 
 /*
@@ -3032,9 +3265,10 @@ cfq_update_idle_window(struct cfq_data *cfqd, struct cfq_queue *cfqq,
        if (cfqq->queued[0] + cfqq->queued[1] >= 4)
                cfq_mark_cfqq_deep(cfqq);
 
-       if (!atomic_read(&cic->ioc->nr_tasks) || !cfqd->cfq_slice_idle ||
-           (!cfq_cfqq_deep(cfqq) && sample_valid(cfqq->seek_samples)
-            && CFQQ_SEEKY(cfqq)))
+       if (cfqq->next_rq && (cfqq->next_rq->cmd_flags & REQ_NOIDLE))
+               enable_idle = 0;
+       else if (!atomic_read(&cic->ioc->nr_tasks) || !cfqd->cfq_slice_idle ||
+           (!cfq_cfqq_deep(cfqq) && CFQQ_SEEKY(cfqq)))
                enable_idle = 0;
        else if (sample_valid(cic->ttime_samples)) {
                if (cic->ttime_mean > cfqd->cfq_slice_idle)
@@ -3073,6 +3307,12 @@ cfq_should_preempt(struct cfq_data *cfqd, struct cfq_queue *new_cfqq,
                return true;
 
        /*
+        * Don't allow a non-RT request to preempt an ongoing RT cfqq timeslice.
+        */
+       if (cfq_class_rt(cfqq) && !cfq_class_rt(new_cfqq))
+               return false;
+
+       /*
         * if the new request is sync, but the currently running queue is
         * not, let the sync request have priority.
         */
@@ -3096,7 +3336,7 @@ cfq_should_preempt(struct cfq_data *cfqd, struct cfq_queue *new_cfqq,
         * So both queues are sync. Let the new request get disk time if
         * it's a metadata request and the current queue is doing regular IO.
         */
-       if (rq_is_meta(rq) && !cfqq->meta_pending)
+       if ((rq->cmd_flags & REQ_META) && !cfqq->meta_pending)
                return true;
 
        /*
@@ -3105,6 +3345,10 @@ cfq_should_preempt(struct cfq_data *cfqd, struct cfq_queue *new_cfqq,
        if (cfq_class_rt(new_cfqq) && !cfq_class_rt(cfqq))
                return true;
 
+       /* An idle queue should not be idle now for some reason */
+       if (RB_EMPTY_ROOT(&cfqq->sort_list) && !cfq_should_idle(cfqd, cfqq))
+               return true;
+
        if (!cfqd->active_cic || !cfq_cfqq_wait_request(cfqq))
                return false;
 
@@ -3124,10 +3368,19 @@ cfq_should_preempt(struct cfq_data *cfqd, struct cfq_queue *new_cfqq,
  */
 static void cfq_preempt_queue(struct cfq_data *cfqd, struct cfq_queue *cfqq)
 {
+       struct cfq_queue *old_cfqq = cfqd->active_queue;
+
        cfq_log_cfqq(cfqd, cfqq, "preempt");
        cfq_slice_expired(cfqd, 1);
 
        /*
+        * workload type is changed, don't save slice, otherwise preempt
+        * doesn't happen
+        */
+       if (cfqq_type(old_cfqq) != cfqq_type(cfqq))
+               cfqq->cfqg->saved_workload_slice = 0;
+
+       /*
         * Put the new queue at the front of the of the current list,
         * so we know that it will be selected next.
         */
@@ -3150,7 +3403,7 @@ cfq_rq_enqueued(struct cfq_data *cfqd, struct cfq_queue *cfqq,
        struct cfq_io_context *cic = RQ_CIC(rq);
 
        cfqd->rq_queued++;
-       if (rq_is_meta(rq))
+       if (rq->cmd_flags & REQ_META)
                cfqq->meta_pending++;
 
        cfq_update_io_thinktime(cfqd, cic);
@@ -3173,11 +3426,14 @@ cfq_rq_enqueued(struct cfq_data *cfqd, struct cfq_queue *cfqq,
                if (cfq_cfqq_wait_request(cfqq)) {
                        if (blk_rq_bytes(rq) > PAGE_CACHE_SIZE ||
                            cfqd->busy_queues > 1) {
-                               del_timer(&cfqd->idle_slice_timer);
+                               cfq_del_timer(cfqd, cfqq);
                                cfq_clear_cfqq_wait_request(cfqq);
                                __blk_run_queue(cfqd->queue);
-                       } else
+                       } else {
+                               cfq_blkiocg_update_idle_time_stats(
+                                               &cfqq->cfqg->blkg);
                                cfq_mark_cfqq_must_dispatch(cfqq);
+                       }
                }
        } else if (cfq_should_preempt(cfqd, cfqq, rq)) {
                /*
@@ -3202,7 +3458,9 @@ static void cfq_insert_request(struct request_queue *q, struct request *rq)
        rq_set_fifo_time(rq, jiffies + cfqd->cfq_fifo_expire[rq_is_sync(rq)]);
        list_add_tail(&rq->queuelist, &cfqq->fifo);
        cfq_add_rq_rb(rq);
-
+       cfq_blkiocg_update_io_add_stats(&(RQ_CFQG(rq))->blkg,
+                       &cfqd->serving_group->blkg, rq_data_dir(rq),
+                       rq_is_sync(rq));
        cfq_rq_enqueued(cfqd, cfqq, rq);
 }
 
@@ -3214,14 +3472,14 @@ static void cfq_update_hw_tag(struct cfq_data *cfqd)
 {
        struct cfq_queue *cfqq = cfqd->active_queue;
 
-       if (rq_in_driver(cfqd) > cfqd->hw_tag_est_depth)
-               cfqd->hw_tag_est_depth = rq_in_driver(cfqd);
+       if (cfqd->rq_in_driver > cfqd->hw_tag_est_depth)
+               cfqd->hw_tag_est_depth = cfqd->rq_in_driver;
 
        if (cfqd->hw_tag == 1)
                return;
 
        if (cfqd->rq_queued <= CFQ_HW_QUEUE_MIN &&
-           rq_in_driver(cfqd) <= CFQ_HW_QUEUE_MIN)
+           cfqd->rq_in_driver <= CFQ_HW_QUEUE_MIN)
                return;
 
        /*
@@ -3231,7 +3489,7 @@ static void cfq_update_hw_tag(struct cfq_data *cfqd)
         */
        if (cfqq && cfq_cfqq_idle_window(cfqq) &&
            cfqq->dispatched + cfqq->queued[0] + cfqq->queued[1] <
-           CFQ_HW_QUEUE_MIN && rq_in_driver(cfqd) < CFQ_HW_QUEUE_MIN)
+           CFQ_HW_QUEUE_MIN && cfqd->rq_in_driver < CFQ_HW_QUEUE_MIN)
                return;
 
        if (cfqd->hw_tag_samples++ < 50)
@@ -3247,6 +3505,10 @@ static bool cfq_should_wait_busy(struct cfq_data *cfqd, struct cfq_queue *cfqq)
 {
        struct cfq_io_context *cic = cfqd->active_cic;
 
+       /* If the queue already has requests, don't wait */
+       if (!RB_EMPTY_ROOT(&cfqq->sort_list))
+               return false;
+
        /* If there are other queues in the group, don't wait */
        if (cfqq->cfqg->nr_cfqq > 1)
                return false;
@@ -3280,17 +3542,21 @@ static void cfq_completed_request(struct request_queue *q, struct request *rq)
        unsigned long now;
 
        now = jiffies;
-       cfq_log_cfqq(cfqd, cfqq, "complete rqnoidle %d", !!rq_noidle(rq));
+       cfq_log_cfqq(cfqd, cfqq, "complete rqnoidle %d",
+                    !!(rq->cmd_flags & REQ_NOIDLE));
 
        cfq_update_hw_tag(cfqd);
 
-       WARN_ON(!cfqd->rq_in_driver[sync]);
+       WARN_ON(!cfqd->rq_in_driver);
        WARN_ON(!cfqq->dispatched);
-       cfqd->rq_in_driver[sync]--;
+       cfqd->rq_in_driver--;
        cfqq->dispatched--;
+       (RQ_CFQG(rq))->dispatched--;
+       cfq_blkiocg_update_completion_stats(&cfqq->cfqg->blkg,
+                       rq_start_time_ns(rq), rq_io_start_time_ns(rq),
+                       rq_data_dir(rq), rq_is_sync(rq));
 
-       if (cfq_cfqq_sync(cfqq))
-               cfqd->sync_flight--;
+       cfqd->rq_in_flight[cfq_cfqq_sync(cfqq)]--;
 
        if (sync) {
                RQ_CIC(rq)->last_end_request = now;
@@ -3315,8 +3581,12 @@ static void cfq_completed_request(struct request_queue *q, struct request *rq)
                 * the queue.
                 */
                if (cfq_should_wait_busy(cfqd, cfqq)) {
-                       cfqq->slice_end = jiffies + cfqd->cfq_slice_idle;
+                       unsigned long extend_sl = cfqd->cfq_slice_idle;
+                       if (!cfqd->cfq_slice_idle)
+                               extend_sl = cfqd->cfq_group_idle;
+                       cfqq->slice_end = jiffies + extend_sl;
                        cfq_mark_cfqq_wait_busy(cfqq);
+                       cfq_log_cfqq(cfqd, cfqq, "will busy wait");
                }
 
                /*
@@ -3331,20 +3601,11 @@ static void cfq_completed_request(struct request_queue *q, struct request *rq)
                        cfq_slice_expired(cfqd, 1);
                else if (sync && cfqq_empty &&
                         !cfq_close_cooperator(cfqd, cfqq)) {
-                       cfqd->noidle_tree_requires_idle |= !rq_noidle(rq);
-                       /*
-                        * Idling is enabled for SYNC_WORKLOAD.
-                        * SYNC_NOIDLE_WORKLOAD idles at the end of the tree
-                        * only if we processed at least one !rq_noidle request
-                        */
-                       if (cfqd->serving_type == SYNC_WORKLOAD
-                           || cfqd->noidle_tree_requires_idle
-                           || cfqq->cfqg->nr_cfqq == 1)
-                               cfq_arm_slice_timer(cfqd);
+                       cfq_arm_slice_timer(cfqd);
                }
        }
 
-       if (!rq_in_driver(cfqd))
+       if (!cfqd->rq_in_driver)
                cfq_schedule_dispatch(cfqd);
 }
 
@@ -3425,8 +3686,12 @@ static void cfq_put_request(struct request *rq)
 
                put_io_context(RQ_CIC(rq)->ioc);
 
-               rq->elevator_private = NULL;
-               rq->elevator_private2 = NULL;
+               rq->elevator_private[0] = NULL;
+               rq->elevator_private[1] = NULL;
+
+               /* Put down rq reference on cfqg */
+               cfq_put_cfqg(RQ_CFQG(rq));
+               rq->elevator_private[2] = NULL;
 
                cfq_put_queue(cfqq);
        }
@@ -3443,14 +3708,6 @@ cfq_merge_cfqqs(struct cfq_data *cfqd, struct cfq_io_context *cic,
        return cic_to_cfqq(cic, 1);
 }
 
-static int should_split_cfqq(struct cfq_queue *cfqq)
-{
-       if (cfqq->seeky_start &&
-           time_after(jiffies, cfqq->seeky_start + CFQQ_COOP_TOUT))
-               return 1;
-       return 0;
-}
-
 /*
  * Returns NULL if a new cfqq should be allocated, or the old cfqq if this
  * was the last process referring to said cfqq.
@@ -3459,13 +3716,16 @@ static struct cfq_queue *
 split_cfqq(struct cfq_io_context *cic, struct cfq_queue *cfqq)
 {
        if (cfqq_process_refs(cfqq) == 1) {
-               cfqq->seeky_start = 0;
                cfqq->pid = current->pid;
                cfq_clear_cfqq_coop(cfqq);
+               cfq_clear_cfqq_split_coop(cfqq);
                return cfqq;
        }
 
        cic_set_cfqq(cic, NULL, 1);
+
+       cfq_put_cooperator(cfqq);
+
        cfq_put_queue(cfqq);
        return NULL;
 }
@@ -3500,7 +3760,7 @@ new_queue:
                /*
                 * If the queue was seeky for too long, break it apart.
                 */
-               if (cfq_cfqq_coop(cfqq) && should_split_cfqq(cfqq)) {
+               if (cfq_cfqq_coop(cfqq) && cfq_cfqq_split_coop(cfqq)) {
                        cfq_log_cfqq(cfqd, cfqq, "breaking apart cfqq");
                        cfqq = split_cfqq(cic, cfqq);
                        if (!cfqq)
@@ -3518,12 +3778,12 @@ new_queue:
        }
 
        cfqq->allocated[rw]++;
-       atomic_inc(&cfqq->ref);
 
+       cfqq->ref++;
+       rq->elevator_private[0] = cic;
+       rq->elevator_private[1] = cfqq;
+       rq->elevator_private[2] = cfq_ref_get_cfqg(cfqq->cfqg);
        spin_unlock_irqrestore(q->queue_lock, flags);
-
-       rq->elevator_private = cic;
-       rq->elevator_private2 = cfqq;
        return 0;
 
 queue_fail:
@@ -3624,15 +3884,11 @@ static void cfq_put_async_queues(struct cfq_data *cfqd)
                cfq_put_queue(cfqd->async_idle_cfqq);
 }
 
-static void cfq_cfqd_free(struct rcu_head *head)
-{
-       kfree(container_of(head, struct cfq_data, rcu));
-}
-
 static void cfq_exit_queue(struct elevator_queue *e)
 {
        struct cfq_data *cfqd = e->elevator_data;
        struct request_queue *q = cfqd->queue;
+       bool wait = false;
 
        cfq_shutdown_timer_wq(cfqd);
 
@@ -3651,14 +3907,59 @@ static void cfq_exit_queue(struct elevator_queue *e)
 
        cfq_put_async_queues(cfqd);
        cfq_release_cfq_groups(cfqd);
-       blkiocg_del_blkio_group(&cfqd->root_group.blkg);
+
+       /*
+        * If there are groups which we could not unlink from blkcg list,
+        * wait for a rcu period for them to be freed.
+        */
+       if (cfqd->nr_blkcg_linked_grps)
+               wait = true;
 
        spin_unlock_irq(q->queue_lock);
 
        cfq_shutdown_timer_wq(cfqd);
 
-       /* Wait for cfqg->blkg->key accessors to exit their grace periods. */
-       call_rcu(&cfqd->rcu, cfq_cfqd_free);
+       spin_lock(&cic_index_lock);
+       ida_remove(&cic_index_ida, cfqd->cic_index);
+       spin_unlock(&cic_index_lock);
+
+       /*
+        * Wait for cfqg->blkg->key accessors to exit their grace periods.
+        * Do this wait only if there are other unlinked groups out
+        * there. This can happen if cgroup deletion path claimed the
+        * responsibility of cleaning up a group before queue cleanup code
+        * get to the group.
+        *
+        * Do not call synchronize_rcu() unconditionally as there are drivers
+        * which create/delete request queue hundreds of times during scan/boot
+        * and synchronize_rcu() can take significant time and slow down boot.
+        */
+       if (wait)
+               synchronize_rcu();
+
+#ifdef CONFIG_CFQ_GROUP_IOSCHED
+       /* Free up per cpu stats for root group */
+       free_percpu(cfqd->root_group.blkg.stats_cpu);
+#endif
+       kfree(cfqd);
+}
+
+static int cfq_alloc_cic_index(void)
+{
+       int index, error;
+
+       do {
+               if (!ida_pre_get(&cic_index_ida, GFP_KERNEL))
+                       return -ENOMEM;
+
+               spin_lock(&cic_index_lock);
+               error = ida_get_new(&cic_index_ida, &index);
+               spin_unlock(&cic_index_lock);
+               if (error && error != -EAGAIN)
+                       return error;
+       } while (error);
+
+       return index;
 }
 
 static void *cfq_init_queue(struct request_queue *q)
@@ -3668,10 +3969,20 @@ static void *cfq_init_queue(struct request_queue *q)
        struct cfq_group *cfqg;
        struct cfq_rb_root *st;
 
+       i = cfq_alloc_cic_index();
+       if (i < 0)
+               return NULL;
+
        cfqd = kmalloc_node(sizeof(*cfqd), GFP_KERNEL | __GFP_ZERO, q->node);
        if (!cfqd)
                return NULL;
 
+       /*
+        * Don't need take queue_lock in the routine, since we are
+        * initializing the ioscheduler, and nobody is using cfqd
+        */
+       cfqd->cic_index = i;
+
        /* Init root service tree */
        cfqd->grp_service_tree = CFQ_RB_ROOT;
 
@@ -3686,12 +3997,29 @@ static void *cfq_init_queue(struct request_queue *q)
 
 #ifdef CONFIG_CFQ_GROUP_IOSCHED
        /*
-        * Take a reference to root group which we never drop. This is just
-        * to make sure that cfq_put_cfqg() does not try to kfree root group
+        * Set root group reference to 2. One reference will be dropped when
+        * all groups on cfqd->cfqg_list are being deleted during queue exit.
+        * Other reference will remain there as we don't want to delete this
+        * group as it is statically allocated and gets destroyed when
+        * throtl_data goes away.
         */
-       atomic_set(&cfqg->ref, 1);
-       blkiocg_add_blkio_group(&blkio_root_cgroup, &cfqg->blkg, (void *)cfqd,
-                                       0);
+       cfqg->ref = 2;
+
+       if (blkio_alloc_blkg_stats(&cfqg->blkg)) {
+               kfree(cfqg);
+               kfree(cfqd);
+               return NULL;
+       }
+
+       rcu_read_lock();
+
+       cfq_blkiocg_add_blkio_group(&blkio_root_cgroup, &cfqg->blkg,
+                                       (void *)cfqd, 0);
+       rcu_read_unlock();
+       cfqd->nr_blkcg_linked_grps++;
+
+       /* Add group on cfqd->cfqg_list */
+       hlist_add_head(&cfqg->cfqd_node, &cfqd->cfqg_list);
 #endif
        /*
         * Not strictly needed (since RB_ROOT just clears the node and we
@@ -3707,7 +4035,7 @@ static void *cfq_init_queue(struct request_queue *q)
         * will not attempt to free it.
         */
        cfq_init_cfqq(cfqd, &cfqd->oom_cfqq, 1, 0);
-       atomic_inc(&cfqd->oom_cfqq.ref);
+       cfqd->oom_cfqq.ref++;
        cfq_link_cfqq_cfqg(&cfqd->oom_cfqq, &cfqd->root_group);
 
        INIT_LIST_HEAD(&cfqd->cic_list);
@@ -3729,15 +4057,14 @@ static void *cfq_init_queue(struct request_queue *q)
        cfqd->cfq_slice[1] = cfq_slice_sync;
        cfqd->cfq_slice_async_rq = cfq_slice_async_rq;
        cfqd->cfq_slice_idle = cfq_slice_idle;
+       cfqd->cfq_group_idle = cfq_group_idle;
        cfqd->cfq_latency = 1;
-       cfqd->cfq_group_isolation = 0;
        cfqd->hw_tag = -1;
        /*
         * we optimistically start assuming sync ops weren't delayed in last
         * second, in order to have larger depth for async operations.
         */
        cfqd->last_delayed_sync = jiffies - HZ;
-       INIT_RCU_HEAD(&cfqd->rcu);
        return cfqd;
 }
 
@@ -3802,11 +4129,11 @@ SHOW_FUNCTION(cfq_fifo_expire_async_show, cfqd->cfq_fifo_expire[0], 1);
 SHOW_FUNCTION(cfq_back_seek_max_show, cfqd->cfq_back_max, 0);
 SHOW_FUNCTION(cfq_back_seek_penalty_show, cfqd->cfq_back_penalty, 0);
 SHOW_FUNCTION(cfq_slice_idle_show, cfqd->cfq_slice_idle, 1);
+SHOW_FUNCTION(cfq_group_idle_show, cfqd->cfq_group_idle, 1);
 SHOW_FUNCTION(cfq_slice_sync_show, cfqd->cfq_slice[1], 1);
 SHOW_FUNCTION(cfq_slice_async_show, cfqd->cfq_slice[0], 1);
 SHOW_FUNCTION(cfq_slice_async_rq_show, cfqd->cfq_slice_async_rq, 0);
 SHOW_FUNCTION(cfq_low_latency_show, cfqd->cfq_latency, 0);
-SHOW_FUNCTION(cfq_group_isolation_show, cfqd->cfq_group_isolation, 0);
 #undef SHOW_FUNCTION
 
 #define STORE_FUNCTION(__FUNC, __PTR, MIN, MAX, __CONV)                        \
@@ -3834,12 +4161,12 @@ STORE_FUNCTION(cfq_back_seek_max_store, &cfqd->cfq_back_max, 0, UINT_MAX, 0);
 STORE_FUNCTION(cfq_back_seek_penalty_store, &cfqd->cfq_back_penalty, 1,
                UINT_MAX, 0);
 STORE_FUNCTION(cfq_slice_idle_store, &cfqd->cfq_slice_idle, 0, UINT_MAX, 1);
+STORE_FUNCTION(cfq_group_idle_store, &cfqd->cfq_group_idle, 0, UINT_MAX, 1);
 STORE_FUNCTION(cfq_slice_sync_store, &cfqd->cfq_slice[1], 1, UINT_MAX, 1);
 STORE_FUNCTION(cfq_slice_async_store, &cfqd->cfq_slice[0], 1, UINT_MAX, 1);
 STORE_FUNCTION(cfq_slice_async_rq_store, &cfqd->cfq_slice_async_rq, 1,
                UINT_MAX, 0);
 STORE_FUNCTION(cfq_low_latency_store, &cfqd->cfq_latency, 0, 1, 0);
-STORE_FUNCTION(cfq_group_isolation_store, &cfqd->cfq_group_isolation, 0, 1, 0);
 #undef STORE_FUNCTION
 
 #define CFQ_ATTR(name) \
@@ -3855,8 +4182,8 @@ static struct elv_fs_entry cfq_attrs[] = {
        CFQ_ATTR(slice_async),
        CFQ_ATTR(slice_async_rq),
        CFQ_ATTR(slice_idle),
+       CFQ_ATTR(group_idle),
        CFQ_ATTR(low_latency),
-       CFQ_ATTR(group_isolation),
        __ATTR_NULL
 };
 
@@ -3866,11 +4193,11 @@ static struct elevator_type iosched_cfq = {
                .elevator_merged_fn =           cfq_merged_request,
                .elevator_merge_req_fn =        cfq_merged_requests,
                .elevator_allow_merge_fn =      cfq_allow_merge,
+               .elevator_bio_merged_fn =       cfq_bio_merged,
                .elevator_dispatch_fn =         cfq_dispatch_requests,
                .elevator_add_req_fn =          cfq_insert_request,
                .elevator_activate_req_fn =     cfq_activate_request,
                .elevator_deactivate_req_fn =   cfq_deactivate_request,
-               .elevator_queue_empty_fn =      cfq_queue_empty,
                .elevator_completed_req_fn =    cfq_completed_request,
                .elevator_former_req_fn =       elv_rb_former_request,
                .elevator_latter_req_fn =       elv_rb_latter_request,
@@ -3892,6 +4219,7 @@ static struct blkio_policy_type blkio_policy_cfq = {
                .blkio_unlink_group_fn =        cfq_unlink_blkio_group,
                .blkio_update_group_weight_fn = cfq_update_blkio_group_weight,
        },
+       .plid = BLKIO_POLICY_PROP,
 };
 #else
 static struct blkio_policy_type blkio_policy_cfq;
@@ -3907,6 +4235,12 @@ static int __init cfq_init(void)
        if (!cfq_slice_idle)
                cfq_slice_idle = 1;
 
+#ifdef CONFIG_CFQ_GROUP_IOSCHED
+       if (!cfq_group_idle)
+               cfq_group_idle = 1;
+#else
+               cfq_group_idle = 0;
+#endif
        if (cfq_slab_setup())
                return -ENOMEM;
 
@@ -3931,6 +4265,7 @@ static void __exit cfq_exit(void)
         */
        if (elv_ioc_count_read(cfq_ioc_count))
                wait_for_completion(&all_gone);
+       ida_destroy(&cic_index_ida);
        cfq_slab_kill();
 }