Version:  2.6.24 2.6.25 2.6.26 2.6.27 2.6.28

Architecture:  x86 m68k m68knommu mips powerpc sh blackfin

   /*
    *  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/blkdev.h>
  #include <linux/elevator.h>
  #include <linux/rbtree.h>
  #include <linux/ioprio.h>
  #include <linux/blktrace_api.h>
  
  /*
   * tunables
   */
  /* max queue in one round of service */
  static const int cfq_quantum = 4;
  static const int cfq_fifo_expire[2] = { HZ / 4, HZ / 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 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;
  
  /*
   * offset from end of service tree
   */
  #define CFQ_IDLE_DELAY          (HZ / 5)
  
  /*
   * below this threshold, we consider thinktime immediate
   */
  #define CFQ_MIN_TT              (2)
  
  #define CFQ_SLICE_SCALE         (5)
  #define CFQ_HW_QUEUE_MIN        (5)
  
  #define RQ_CIC(rq)              \
          ((struct cfq_io_context *) (rq)->elevator_private)
  #define RQ_CFQQ(rq)             (struct cfq_queue *) ((rq)->elevator_private2)
  
  static struct kmem_cache *cfq_pool;
  static struct kmem_cache *cfq_ioc_pool;
  
  static DEFINE_PER_CPU(unsigned long, ioc_count);
  static struct completion *ioc_gone;
  static DEFINE_SPINLOCK(ioc_gone_lock);
  
  #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 ASYNC                   (0)
  #define SYNC                    (1)
  
  #define sample_valid(samples)   ((samples) > 80)
  
  /*
   * 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;
  };
  #define CFQ_RB_ROOT     (struct cfq_rb_root) { RB_ROOT, NULL, }
  
  /*
   * Per block device queue structure
   */
  struct cfq_data {
          struct request_queue *queue;
  
          /*
           * rr list of queues with requests and the count of them
           */
          struct cfq_rb_root service_tree;
          unsigned int busy_queues;
  
          int rq_in_driver;
          int sync_flight;
  
          /*
           * queue-depth detection
           */
          int rq_queued;
          int hw_tag;
          int hw_tag_samples;
          int rq_in_driver_peak;
  
          /*
          * idle window management
          */
         struct timer_list idle_slice_timer;
         struct work_struct unplug_work;
 
         struct cfq_queue *active_queue;
         struct cfq_io_context *active_cic;
 
         /*
          * async queue for each priority case
          */
         struct cfq_queue *async_cfqq[2][IOPRIO_BE_NR];
         struct cfq_queue *async_idle_cfqq;
 
         sector_t last_position;
         unsigned long last_end_request;
 
         /*
          * tunables, see top of file
          */
         unsigned int cfq_quantum;
         unsigned int cfq_fifo_expire[2];
         unsigned int cfq_back_penalty;
         unsigned int cfq_back_max;
         unsigned int cfq_slice[2];
         unsigned int cfq_slice_async_rq;
         unsigned int cfq_slice_idle;
 
         struct list_head cic_list;
 };
 
 /*
  * Per process-grouping structure
  */
 struct cfq_queue {
         /* reference count */
         atomic_t 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 */
         unsigned long rb_key;
         /* 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;
 
         unsigned long slice_end;
         long slice_resid;
 
         /* pending metadata requests */
         int meta_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;
 };
 
 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_alloc,       /* must be allowed rq alloc */
         CFQ_CFQQ_FLAG_must_alloc_slice, /* per-slice must_alloc flag */
         CFQ_CFQQ_FLAG_must_dispatch,    /* must dispatch, even if expired */
         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_queue_new,        /* queue never been serviced */
         CFQ_CFQQ_FLAG_slice_new,        /* no requests dispatched in slice */
         CFQ_CFQQ_FLAG_sync,             /* synchronous queue */
 };
 
 #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_alloc);
 CFQ_CFQQ_FNS(must_alloc_slice);
 CFQ_CFQQ_FNS(must_dispatch);
 CFQ_CFQQ_FNS(fifo_expire);
 CFQ_CFQQ_FNS(idle_window);
 CFQ_CFQQ_FNS(prio_changed);
 CFQ_CFQQ_FNS(queue_new);
 CFQ_CFQQ_FNS(slice_new);
 CFQ_CFQQ_FNS(sync);
 #undef CFQ_CFQQ_FNS
 
 #define cfq_log_cfqq(cfqd, cfqq, fmt, args...)  \
         blk_add_trace_msg((cfqd)->queue, "cfq%d " fmt, (cfqq)->pid, ##args)
 #define cfq_log(cfqd, fmt, args...)     \
         blk_add_trace_msg((cfqd)->queue, "cfq " fmt, ##args)
 
 static void cfq_dispatch_insert(struct request_queue *, struct request *);
 static struct cfq_queue *cfq_get_queue(struct cfq_data *, int,
                                        struct io_context *, gfp_t);
 static struct cfq_io_context *cfq_cic_lookup(struct cfq_data *,
                                                 struct io_context *);
 
 static inline struct cfq_queue *cic_to_cfqq(struct cfq_io_context *cic,
                                             int is_sync)
 {
         return cic->cfqq[!!is_sync];
 }
 
 static inline void cic_set_cfqq(struct cfq_io_context *cic,
                                 struct cfq_queue *cfqq, int is_sync)
 {
         cic->cfqq[!!is_sync] = cfqq;
 }
 
 /*
  * 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 int cfq_bio_sync(struct bio *bio)
 {
         if (bio_data_dir(bio) == READ || bio_sync(bio))
                 return 1;
 
         return 0;
 }
 
 /*
  * 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->queue, &cfqd->unplug_work);
         }
 }
 
 static int cfq_queue_empty(struct request_queue *q)
 {
         struct cfq_data *cfqd = q->elevator->elevator_data;
 
         return !cfqd->busy_queues;
 }
 
 /*
  * 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 int cfq_prio_slice(struct cfq_data *cfqd, int sync,
                                  unsigned short prio)
 {
         const int base_slice = cfqd->cfq_slice[sync];
 
         WARN_ON(prio >= IOPRIO_BE_NR);
 
         return base_slice + (base_slice/CFQ_SLICE_SCALE * (4 - prio));
 }
 
 static inline int
 cfq_prio_to_slice(struct cfq_data *cfqd, struct cfq_queue *cfqq)
 {
         return cfq_prio_slice(cfqd, cfq_cfqq_sync(cfqq), cfqq->ioprio);
 }
 
 static inline void
 cfq_set_prio_slice(struct cfq_data *cfqd, struct cfq_queue *cfqq)
 {
         cfqq->slice_end = cfq_prio_to_slice(cfqd, cfqq) + jiffies;
         cfq_log_cfqq(cfqd, cfqq, "set_slice=%lu", cfqq->slice_end - jiffies);
 }
 
 /*
  * 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 int cfq_slice_used(struct cfq_queue *cfqq)
 {
         if (cfq_cfqq_slice_new(cfqq))
                 return 0;
         if (time_before(jiffies, cfqq->slice_end))
                 return 0;
 
         return 1;
 }
 
 /*
  * 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, 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 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;
 
         s1 = rq1->sector;
         s2 = rq2->sector;
 
         last = cfqd->last_position;
 
         /*
          * 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)
 {
         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 void cfq_rb_erase(struct rb_node *n, struct cfq_rb_root *root)
 {
         if (root->left == n)
                 root->left = NULL;
 
         rb_erase(n, &root->rb);
         RB_CLEAR_NODE(n);
 }
 
 /*
  * 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);
 }
 
 static unsigned long cfq_slice_offset(struct cfq_data *cfqd,
                                       struct cfq_queue *cfqq)
 {
         /*
          * just an approximation, should be ok.
          */
         return (cfqd->busy_queues - 1) * (cfq_prio_slice(cfqd, 1, 0) -
                        cfq_prio_slice(cfqd, cfq_cfqq_sync(cfqq), cfqq->ioprio));
 }
 
 /*
  * The cfqd->service_tree holds all pending cfq_queue's that have
  * requests waiting to be processed. It is sorted in the order that
  * we will service the queues.
  */
 static void cfq_service_tree_add(struct cfq_data *cfqd,
                                     struct cfq_queue *cfqq, int add_front)
 {
         struct rb_node **p, *parent;
         struct cfq_queue *__cfqq;
         unsigned long rb_key;
         int left;
 
         if (cfq_class_idle(cfqq)) {
                 rb_key = CFQ_IDLE_DELAY;
                 parent = rb_last(&cfqd->service_tree.rb);
                 if (parent && parent != &cfqq->rb_node) {
                         __cfqq = rb_entry(parent, struct cfq_queue, rb_node);
                         rb_key += __cfqq->rb_key;
                 } else
                         rb_key += jiffies;
         } else if (!add_front) {
                 rb_key = cfq_slice_offset(cfqd, cfqq) + jiffies;
                 rb_key += cfqq->slice_resid;
                 cfqq->slice_resid = 0;
         } else
                 rb_key = 0;
 
         if (!RB_EMPTY_NODE(&cfqq->rb_node)) {
                 /*
                  * same position, nothing more to do
                  */
                 if (rb_key == cfqq->rb_key)
                         return;
 
                 cfq_rb_erase(&cfqq->rb_node, &cfqd->service_tree);
         }
 
         left = 1;
         parent = NULL;
         p = &cfqd->service_tree.rb.rb_node;
         while (*p) {
                 struct rb_node **n;
 
                 parent = *p;
                 __cfqq = rb_entry(parent, struct cfq_queue, rb_node);
 
                 /*
                  * sort RT queues first, we always want to give
                  * preference to them. IDLE queues goes to the back.
                  * after that, sort on the next service time.
                  */
                 if (cfq_class_rt(cfqq) > cfq_class_rt(__cfqq))
                         n = &(*p)->rb_left;
                 else if (cfq_class_rt(cfqq) < cfq_class_rt(__cfqq))
                         n = &(*p)->rb_right;
                 else if (cfq_class_idle(cfqq) < cfq_class_idle(__cfqq))
                         n = &(*p)->rb_left;
                 else if (cfq_class_idle(cfqq) > cfq_class_idle(__cfqq))
                         n = &(*p)->rb_right;
                 else if (rb_key < __cfqq->rb_key)
                         n = &(*p)->rb_left;
                 else
                         n = &(*p)->rb_right;
 
                 if (n == &(*p)->rb_right)
                         left = 0;
 
                 p = n;
         }
 
         if (left)
                 cfqd->service_tree.left = &cfqq->rb_node;
 
         cfqq->rb_key = rb_key;
         rb_link_node(&cfqq->rb_node, parent, p);
         rb_insert_color(&cfqq->rb_node, &cfqd->service_tree.rb);
 }
 
 /*
  * Update cfqq's position in the service tree.
  */
 static void cfq_resort_rr_list(struct cfq_data *cfqd, struct cfq_queue *cfqq)
 {
         /*
          * Resorting requires the cfqq to be on the RR list already.
          */
         if (cfq_cfqq_on_rr(cfqq))
                 cfq_service_tree_add(cfqd, cfqq, 0);
 }
 
 /*
  * add to busy list of queues for service, trying to be fair in ordering
  * the pending list according to last request service
  */
 static void cfq_add_cfqq_rr(struct cfq_data *cfqd, struct cfq_queue *cfqq)
 {
         cfq_log_cfqq(cfqd, cfqq, "add_to_rr");
         BUG_ON(cfq_cfqq_on_rr(cfqq));
         cfq_mark_cfqq_on_rr(cfqq);
         cfqd->busy_queues++;
 
         cfq_resort_rr_list(cfqd, cfqq);
 }
 
 /*
  * Called when the cfqq no longer has requests pending, remove it from
  * the service tree.
  */
 static void cfq_del_cfqq_rr(struct cfq_data *cfqd, struct cfq_queue *cfqq)
 {
         cfq_log_cfqq(cfqd, cfqq, "del_from_rr");
         BUG_ON(!cfq_cfqq_on_rr(cfqq));
         cfq_clear_cfqq_on_rr(cfqq);
 
         if (!RB_EMPTY_NODE(&cfqq->rb_node))
                 cfq_rb_erase(&cfqq->rb_node, &cfqd->service_tree);
 
         BUG_ON(!cfqd->busy_queues);
         cfqd->busy_queues--;
 }
 
 /*
  * rb tree support functions
  */
 static void cfq_del_rq_rb(struct request *rq)
 {
         struct cfq_queue *cfqq = RQ_CFQQ(rq);
         struct cfq_data *cfqd = cfqq->cfqd;
         const int sync = rq_is_sync(rq);
 
         BUG_ON(!cfqq->queued[sync]);
         cfqq->queued[sync]--;
 
         elv_rb_del(&cfqq->sort_list, rq);
 
         if (cfq_cfqq_on_rr(cfqq) && RB_EMPTY_ROOT(&cfqq->sort_list))
                 cfq_del_cfqq_rr(cfqd, cfqq);
 }
 
 static void cfq_add_rq_rb(struct request *rq)
 {
         struct cfq_queue *cfqq = RQ_CFQQ(rq);
         struct cfq_data *cfqd = cfqq->cfqd;
         struct request *__alias;
 
         cfqq->queued[rq_is_sync(rq)]++;
 
         /*
          * looks a little odd, but the first insert might return an alias.
          * if that happens, put the alias on the dispatch list
          */
         while ((__alias = elv_rb_add(&cfqq->sort_list, rq)) != NULL)
                 cfq_dispatch_insert(cfqd->queue, __alias);
 
         if (!cfq_cfqq_on_rr(cfqq))
                 cfq_add_cfqq_rr(cfqd, cfqq);
 
         /*
          * check if this request is a better next-serve candidate
          */
         cfqq->next_rq = cfq_choose_req(cfqd, cfqq->next_rq, rq);
         BUG_ON(!cfqq->next_rq);
 }
 
 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_add_rq_rb(rq);
 }
 
 static struct request *
 cfq_find_rq_fmerge(struct cfq_data *cfqd, struct bio *bio)
 {
         struct task_struct *tsk = current;
         struct cfq_io_context *cic;
         struct cfq_queue *cfqq;
 
         cic = cfq_cic_lookup(cfqd, tsk->io_context);
         if (!cic)
                 return NULL;
 
         cfqq = cic_to_cfqq(cic, cfq_bio_sync(bio));
         if (cfqq) {
                 sector_t sector = bio->bi_sector + bio_sectors(bio);
 
                 return elv_rb_find(&cfqq->sort_list, sector);
         }
 
         return NULL;
 }
 
 static void cfq_activate_request(struct request_queue *q, struct request *rq)
 {
         struct cfq_data *cfqd = q->elevator->elevator_data;
 
         cfqd->rq_in_driver++;
         cfq_log_cfqq(cfqd, RQ_CFQQ(rq), "activate rq, drv=%d",
                                                 cfqd->rq_in_driver);
 
         cfqd->last_position = rq->hard_sector + rq->hard_nr_sectors;
 }
 
 static void cfq_deactivate_request(struct request_queue *q, struct request *rq)
 {
         struct cfq_data *cfqd = q->elevator->elevator_data;
 
         WARN_ON(!cfqd->rq_in_driver);
         cfqd->rq_in_driver--;
         cfq_log_cfqq(cfqd, RQ_CFQQ(rq), "deactivate rq, drv=%d",
                                                 cfqd->rq_in_driver);
 }
 
 static void cfq_remove_request(struct request *rq)
 {
         struct cfq_queue *cfqq = RQ_CFQQ(rq);
 
         if (cfqq->next_rq == rq)
                 cfqq->next_rq = cfq_find_next_rq(cfqq->cfqd, cfqq, rq);
 
         list_del_init(&rq->queuelist);
         cfq_del_rq_rb(rq);
 
         cfqq->cfqd->rq_queued--;
         if (rq_is_meta(rq)) {
                 WARN_ON(!cfqq->meta_pending);
                 cfqq->meta_pending--;
         }
 }
 
 static int cfq_merge(struct request_queue *q, struct request **req,
                      struct bio *bio)
 {
         struct cfq_data *cfqd = q->elevator->elevator_data;
         struct request *__rq;
 
         __rq = cfq_find_rq_fmerge(cfqd, bio);
         if (__rq && elv_rq_merge_ok(__rq, bio)) {
                 *req = __rq;
                 return ELEVATOR_FRONT_MERGE;
         }
 
         return ELEVATOR_NO_MERGE;
 }
 
 static void cfq_merged_request(struct request_queue *q, struct request *req,
                                int type)
 {
         if (type == ELEVATOR_FRONT_MERGE) {
                 struct cfq_queue *cfqq = RQ_CFQQ(req);
 
                 cfq_reposition_rq_rb(cfqq, req);
         }
 }
 
 static void
 cfq_merged_requests(struct request_queue *q, struct request *rq,
                     struct request *next)
 {
         /*
          * reposition in fifo if next is older than rq
          */
         if (!list_empty(&rq->queuelist) && !list_empty(&next->queuelist) &&
             time_before(next->start_time, rq->start_time))
                 list_move(&rq->queuelist, &next->queuelist);
 
         cfq_remove_request(next);
 }
 
 static int cfq_allow_merge(struct request_queue *q, struct request *rq,
                            struct bio *bio)
 {
         struct cfq_data *cfqd = q->elevator->elevator_data;
         struct cfq_io_context *cic;
         struct cfq_queue *cfqq;
 
         /*
          * Disallow merge of a sync bio into an async request.
          */
         if (cfq_bio_sync(bio) && !rq_is_sync(rq))
                 return 0;
 
         /*
          * Lookup the cfqq that this bio will be queued with. Allow
          * merge only if rq is queued there.
          */
         cic = cfq_cic_lookup(cfqd, current->io_context);
         if (!cic)
                 return 0;
 
         cfqq = cic_to_cfqq(cic, cfq_bio_sync(bio));
         if (cfqq == RQ_CFQQ(rq))
                 return 1;
 
         return 0;
 }
 
 static void __cfq_set_active_queue(struct cfq_data *cfqd,
                                    struct cfq_queue *cfqq)
 {
         if (cfqq) {
                 cfq_log_cfqq(cfqd, cfqq, "set_active");
                 cfqq->slice_end = 0;
                 cfq_clear_cfqq_must_alloc_slice(cfqq);
                 cfq_clear_cfqq_fifo_expire(cfqq);
                 cfq_mark_cfqq_slice_new(cfqq);
                 cfq_clear_cfqq_queue_new(cfqq);
         }
 
         cfqd->active_queue = cfqq;
 }
 
 /*
  * current cfqq expired its slice (or was too idle), select new one
  */
 static void
 __cfq_slice_expired(struct cfq_data *cfqd, struct cfq_queue *cfqq,
                     int timed_out)
 {
         cfq_log_cfqq(cfqd, cfqq, "slice expired t=%d", timed_out);
 
         if (cfq_cfqq_wait_request(cfqq))
                 del_timer(&cfqd->idle_slice_timer);
 
         cfq_clear_cfqq_must_dispatch(cfqq);
         cfq_clear_cfqq_wait_request(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;
                 cfq_log_cfqq(cfqd, cfqq, "resid=%ld", cfqq->slice_resid);
         }
 
         cfq_resort_rr_list(cfqd, cfqq);
 
         if (cfqq == cfqd->active_queue)
                 cfqd->active_queue = NULL;
 
         if (cfqd->active_cic) {
                 put_io_context(cfqd->active_cic->ioc);
                 cfqd->active_cic = NULL;
         }
 }
 
 static inline void cfq_slice_expired(struct cfq_data *cfqd, int timed_out)
 {
         struct cfq_queue *cfqq = cfqd->active_queue;
 
         if (cfqq)
                 __cfq_slice_expired(cfqd, cfqq, timed_out);
 }
 
 /*
  * Get next queue for service. Unless we have a queue preemption,
  * we'll simply select the first cfqq in the service tree.
  */
 static struct cfq_queue *cfq_get_next_queue(struct cfq_data *cfqd)
 {
         if (RB_EMPTY_ROOT(&cfqd->service_tree.rb))
                 return NULL;
 
         return cfq_rb_first(&cfqd->service_tree);
 }
 
 /*
  * Get and set a new active queue for service.
  */
 static struct cfq_queue *cfq_set_active_queue(struct cfq_data *cfqd)
 {
         struct cfq_queue *cfqq;
 
         cfqq = cfq_get_next_queue(cfqd);
         __cfq_set_active_queue(cfqd, cfqq);
         return cfqq;
 }
 
 static inline sector_t cfq_dist_from_last(struct cfq_data *cfqd,
                                           struct request *rq)
 {
         if (rq->sector >= cfqd->last_position)
                 return rq->sector - cfqd->last_position;
         else
                 return cfqd->last_position - rq->sector;
 }
 
 static inline int cfq_rq_close(struct cfq_data *cfqd, struct request *rq)
 {
         struct cfq_io_context *cic = cfqd->active_cic;
 
         if (!sample_valid(cic->seek_samples))
                 return 0;
 
         return cfq_dist_from_last(cfqd, rq) <= cic->seek_mean;
 }
 
 static int cfq_close_cooperator(struct cfq_data *cfq_data,
                                 struct cfq_queue *cfqq)
 {
         /*
          * We should notice if some of the queues are cooperating, eg
          * working closely on the same area of the disk. In that case,
          * we can group them together and don't waste time idling.
          */
         return 0;
 }
 
 #define CIC_SEEKY(cic) ((cic)->seek_mean > (8 * 1024))
 
 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;
 
         /*
          * SSD device without seek penalty, disable idling. But only do so
          * for devices that support queuing, otherwise we still have a problem
          * with sync vs async workloads.
          */
         if (blk_queue_nonrot(cfqd->queue) && cfqd->hw_tag)
                 return;
 
         WARN_ON(!RB_EMPTY_ROOT(&cfqq->sort_list));
         WARN_ON(cfq_cfqq_slice_new(cfqq));
 
         /*
          * idle is disabled, either manually or by past process history
          */
         if (!cfqd->cfq_slice_idle || !cfq_cfqq_idle_window(cfqq))
                 return;
 
         /*
          * still requests with the driver, don't idle
          */
         if (cfqd->rq_in_driver)
                 return;
 
         /*
          * task has exited, don't wait
          */
         cic = cfqd->active_cic;
         if (!cic || !atomic_read(&cic->ioc->nr_tasks))
                 return;
 
         /*
          * See if this prio level has a good candidate
          */
         if (cfq_close_cooperator(cfqd, cfqq) &&
             (sample_valid(cic->ttime_samples) && cic->ttime_mean > 2))
                 return;
 
         cfq_mark_cfqq_must_dispatch(cfqq);
         cfq_mark_cfqq_wait_request(cfqq);
 
         /*
          * we don't want to idle for seeks, but we do want to allow
          * fair distribution of slice time for a process doing back-to-back
          * seeks. so allow a little bit of time for him to submit a new rq
          */
         sl = cfqd->cfq_slice_idle;
         if (sample_valid(cic->seek_samples) && CIC_SEEKY(cic))
                 sl = min(sl, msecs_to_jiffies(CFQ_MIN_TT));
 
         mod_timer(&cfqd->idle_slice_timer, jiffies + sl);
         cfq_log(cfqd, "arm_idle: %lu", sl);
 }
 
 /*
  * Move request from internal lists to the request queue dispatch list.
  */
 static void cfq_dispatch_insert(struct request_queue *q, struct request *rq)
 {
         struct cfq_data *cfqd = q->elevator->elevator_data;
         struct cfq_queue *cfqq = RQ_CFQQ(rq);
 
         cfq_log_cfqq(cfqd, cfqq, "dispatch_insert");
 
         cfq_remove_request(rq);
         cfqq->dispatched++;
         elv_dispatch_sort(q, rq);
 
         if (cfq_cfqq_sync(cfqq))
                 cfqd->sync_flight++;
 }
 
 /*
  * return expired entry, or NULL to just start from scratch in rbtree
  */
 static struct request *cfq_check_fifo(struct cfq_queue *cfqq)
 {
         struct cfq_data *cfqd = cfqq->cfqd;
         struct request *rq;
         int fifo;
 
         if (cfq_cfqq_fifo_expire(cfqq))
                 return NULL;
 
         cfq_mark_cfqq_fifo_expire(cfqq);
 
         if (list_empty(&cfqq->fifo))
                 return NULL;
 
         fifo = cfq_cfqq_sync(cfqq);
         rq = rq_entry_fifo(cfqq->fifo.next);
 
         if (time_before(jiffies, rq->start_time + cfqd->cfq_fifo_expire[fifo]))
                 rq = NULL;
 
         cfq_log_cfqq(cfqd, cfqq, "fifo=%p", rq);
         return rq;
 }
 
 static inline int
 cfq_prio_to_maxrq(struct cfq_data *cfqd, struct cfq_queue *cfqq)
 {
         const int base_rq = cfqd->cfq_slice_async_rq;
 
         WARN_ON(cfqq->ioprio >= IOPRIO_BE_NR);
 
         return 2 * (base_rq + base_rq * (CFQ_PRIO_LISTS - 1 - cfqq->ioprio));
 }
 
 /*
  * Select a queue for service. If we have a current active queue,
  * check whether to continue servicing it, or retrieve and set a new one.
  */
 static struct cfq_queue *cfq_select_queue(struct cfq_data *cfqd)
 {
         struct cfq_queue *cfqq;
 
         cfqq = cfqd->active_queue;
         if (!cfqq)
                 goto new_queue;
 
         /*
          * The active queue has run out of time, expire it and select new.
          */
         if (cfq_slice_used(cfqq))
                 goto expire;
 
         /*
          * The active queue has requests and isn't expired, allow it to
          * dispatch.
          */
         if (!RB_EMPTY_ROOT(&cfqq->sort_list))
                 goto keep_queue;
 
         /*
          * No requests pending. If the active queue still has requests in
          * 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_cfqq_idle_window(cfqq))) {
                 cfqq = NULL;
                 goto keep_queue;
         }
 
 expire:
         cfq_slice_expired(cfqd, 0);
 new_queue:
         cfqq = cfq_set_active_queue(cfqd);
 keep_queue:
         return cfqq;
 }
 
 /*
  * Dispatch some requests from cfqq, moving them to the request queue
  * dispatch list.
  */
 static int
 __cfq_dispatch_requests(struct cfq_data *cfqd, struct cfq_queue *cfqq,
                         int max_dispatch)
 {
         int dispatched = 0;
 
         BUG_ON(RB_EMPTY_ROOT(&cfqq->sort_list));
 
         do {
                 struct request *rq;
 
                 /*
                  * follow expired path, else get first next available
                  */
                 rq = cfq_check_fifo(cfqq);
                 if (rq == NULL)
                         rq = cfqq->next_rq;
 
                 /*
                  * finally, insert request into driver dispatch list
                  */
                 cfq_dispatch_insert(cfqd->queue, rq);
 
                 dispatched++;
 
                 if (!cfqd->active_cic) {
                         atomic_inc(&RQ_CIC(rq)->ioc->refcount);
                         cfqd->active_cic = RQ_CIC(rq);
                 }
 
                 if (RB_EMPTY_ROOT(&cfqq->sort_list))
                         break;
 
         } while (dispatched < max_dispatch);
 
         /*
          * expire an async queue immediately if it has used up its slice. idle
          * queue always expire after 1 dispatch round.
          */
         if (cfqd->busy_queues > 1 && ((!cfq_cfqq_sync(cfqq) &&
             dispatched >= cfq_prio_to_maxrq(cfqd, cfqq)) ||
             cfq_class_idle(cfqq))) {
                 cfqq->slice_end = jiffies + 1;
                 cfq_slice_expired(cfqd, 0);
         }
 
         return dispatched;
 }
 
 static int __cfq_forced_dispatch_cfqq(struct cfq_queue *cfqq)
 {
         int dispatched = 0;
 
         while (cfqq->next_rq) {
                 cfq_dispatch_insert(cfqq->cfqd->queue, cfqq->next_rq);