+ if (cfq_cfqq_fifo_expire(cfqq))
+ return NULL;
+
+ if (!list_empty(&cfqq->fifo)) {
+ int fifo = cfq_cfqq_class_sync(cfqq);
+
+ crq = RQ_DATA(list_entry_fifo(cfqq->fifo.next));
+ rq = crq->request;
+ if (time_after(jiffies, rq->start_time + cfqd->cfq_fifo_expire[fifo])) {
+ cfq_mark_cfqq_fifo_expire(cfqq);
+ return crq;
+ }
+ }
+
+ return NULL;
+}
+
+/*
+ * 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_to_slice(struct cfq_data *cfqd, struct cfq_queue *cfqq)
+{
+ const int base_slice = cfqd->cfq_slice[cfq_cfqq_sync(cfqq)];
+
+ WARN_ON(cfqq->ioprio >= IOPRIO_BE_NR);
+
+ return base_slice + (base_slice/CFQ_SLICE_SCALE * (4 - 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;
+}
+
+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));
+}
+
+/*
+ * get next queue for service
+ */
+static struct cfq_queue *cfq_select_queue(struct cfq_data *cfqd, int force)
+{
+ unsigned long now = jiffies;
+ struct cfq_queue *cfqq;
+
+ cfqq = cfqd->active_queue;
+ if (!cfqq)
+ goto new_queue;
+
+ if (cfq_cfqq_expired(cfqq))
+ goto new_queue;
+
+ /*
+ * slice has expired
+ */
+ if (!cfq_cfqq_must_dispatch(cfqq) && time_after(now, cfqq->slice_end))
+ goto expire;
+
+ /*
+ * if queue has requests, dispatch one. if not, check if
+ * enough slice is left to wait for one
+ */
+ if (!RB_EMPTY(&cfqq->sort_list))
+ goto keep_queue;
+ else if (!force && cfq_cfqq_class_sync(cfqq) &&
+ time_before(now, cfqq->slice_end)) {
+ if (cfq_arm_slice_timer(cfqd, cfqq))
+ return NULL;
+ }
+
+expire:
+ cfq_slice_expired(cfqd, 0);
+new_queue:
+ cfqq = cfq_set_active_queue(cfqd);
+keep_queue:
+ return cfqq;
+}
+
+static int
+__cfq_dispatch_requests(struct cfq_data *cfqd, struct cfq_queue *cfqq,
+ int max_dispatch)
+{
+ int dispatched = 0;
+
+ BUG_ON(RB_EMPTY(&cfqq->sort_list));
+
+ do {
+ struct cfq_rq *crq;
+
+ /*
+ * follow expired path, else get first next available
+ */
+ if ((crq = cfq_check_fifo(cfqq)) == NULL)
+ crq = cfqq->next_crq;
+
+ /*
+ * finally, insert request into driver dispatch list
+ */
+ cfq_dispatch_sort(cfqd->queue, crq);
+
+ cfqd->dispatch_slice++;
+ dispatched++;
+
+ if (!cfqd->active_cic) {
+ atomic_inc(&crq->io_context->ioc->refcount);
+ cfqd->active_cic = crq->io_context;
+ }
+
+ if (RB_EMPTY(&cfqq->sort_list))
+ break;
+
+ } while (dispatched < max_dispatch);
+
+ /*
+ * if slice end isn't set yet, set it. if at least one request was
+ * sync, use the sync time slice value
+ */
+ if (!cfqq->slice_end)
+ cfq_set_prio_slice(cfqd, cfqq);
+
+ /*
+ * expire an async queue immediately if it has used up its slice. idle
+ * queue always expire after 1 dispatch round.
+ */
+ if ((!cfq_cfqq_sync(cfqq) &&
+ cfqd->dispatch_slice >= cfq_prio_to_maxrq(cfqd, cfqq)) ||
+ cfq_class_idle(cfqq))
+ cfq_slice_expired(cfqd, 0);
+
+ return dispatched;
+}
+
+static int
+cfq_dispatch_requests(request_queue_t *q, int max_dispatch, int force)
+{
+ struct cfq_data *cfqd = q->elevator->elevator_data;
+ struct cfq_queue *cfqq;
+
+ if (!cfqd->busy_queues)
+ return 0;
+
+ cfqq = cfq_select_queue(cfqd, force);
+ if (cfqq) {
+ cfq_clear_cfqq_must_dispatch(cfqq);
+ cfq_clear_cfqq_wait_request(cfqq);
+ del_timer(&cfqd->idle_slice_timer);
+
+ if (cfq_class_idle(cfqq))
+ max_dispatch = 1;
+
+ return __cfq_dispatch_requests(cfqd, cfqq, max_dispatch);
+ }
+
+ return 0;
+}
+
+static inline void cfq_account_dispatch(struct cfq_rq *crq)
+{
+ struct cfq_queue *cfqq = crq->cfq_queue;
+ struct cfq_data *cfqd = cfqq->cfqd;
+
+ if (unlikely(!blk_fs_request(crq->request)))
+ return;
+
+ /*
+ * accounted bit is necessary since some drivers will call
+ * elv_next_request() many times for the same request (eg ide)
+ */
+ if (cfq_crq_in_driver(crq))
+ return;
+
+ cfq_mark_crq_in_driver(crq);
+ cfqd->rq_in_driver++;
+}
+
+static inline void
+cfq_account_completion(struct cfq_queue *cfqq, struct cfq_rq *crq)
+{
+ struct cfq_data *cfqd = cfqq->cfqd;
+ unsigned long now;
+
+ if (!cfq_crq_in_driver(crq))