Newer
Older
/*
* 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/blkdev.h>
#include <linux/elevator.h>
#include <linux/ioprio.h>
static const int cfq_quantum = 4; /* max queue in one round of service */
static const int cfq_fifo_expire[2] = { HZ / 4, HZ / 8 };
static const int cfq_back_max = 16 * 1024; /* maximum backwards seek, in KiB */
static const int cfq_back_penalty = 2; /* penalty of a backwards seek */
static const int cfq_slice_sync = HZ / 10;
static const int cfq_slice_async_rq = 2;
static int cfq_slice_idle = HZ / 125;
#define CFQ_IDLE_GRACE (HZ / 10)
#define CFQ_SLICE_SCALE (5)
#define CFQ_KEY_ASYNC (0)
/*
* for the hash of cfqq inside the cfqd
*/
#define CFQ_QHASH_SHIFT 6
#define CFQ_QHASH_ENTRIES (1 << CFQ_QHASH_SHIFT)
#define list_entry_qhash(entry) hlist_entry((entry), struct cfq_queue, cfq_hash)
#define list_entry_cfqq(ptr) list_entry((ptr), struct cfq_queue, cfq_list)
#define RQ_CIC(rq) ((struct cfq_io_context*)(rq)->elevator_private)
#define RQ_CFQQ(rq) ((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;
#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 cfq_cfqq_sync(cfqq) ((cfqq)->key != CFQ_KEY_ASYNC)
#define sample_valid(samples) ((samples) > 80)
/*
* Per block device queue structure
*/
request_queue_t *queue;
/*
* rr list of queues with requests and the count of them
*/
struct list_head rr_list[CFQ_PRIO_LISTS];
struct list_head cur_rr;
struct list_head idle_rr;
unsigned int busy_queues;
/*
* cfqq lookup hash
*/
/*
* 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;
int cur_prio, cur_end_prio;
unsigned int dispatch_slice;
struct timer_list idle_class_timer;
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;
sector_t new_seek_mean;
u64 new_seek_total;
/*
* Per process-grouping structure
*/
struct cfq_queue {
/* reference count */
atomic_t ref;
/* parent cfq_data */
struct cfq_data *cfqd;
/* cfqq lookup hash */
/* member of the rr/busy/cur/idle cfqd list */
/* in what tick we were last serviced */
unsigned long rr_tick;
/* sorted list of pending requests */
struct rb_root sort_list;
/* if fifo isn't expired, next request to serve */
/* requests queued in sort_list */
int queued[2];
/* currently allocated requests */
int allocated[2];
/* pending metadata requests */
int meta_pending;
struct list_head fifo;
unsigned long slice_end;
unsigned long service_last;
/* 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;
/* various state flags, see below */
unsigned int 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 */
};
#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);
#undef CFQ_CFQQ_FNS
static struct cfq_queue *cfq_find_cfq_hash(struct cfq_data *, unsigned int, unsigned short);
static void cfq_dispatch_insert(request_queue_t *, struct request *);
static struct cfq_queue *cfq_get_queue(struct cfq_data *cfqd, unsigned int key, struct task_struct *tsk, gfp_t gfp_mask);
/*
* 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)
{
kblockd_schedule_work(&cfqd->unplug_work);
}
static int cfq_queue_empty(request_queue_t *q)
{
struct cfq_data *cfqd = q->elevator->elevator_data;
return !cfqd->busy_queues;
static inline pid_t cfq_queue_pid(struct task_struct *task, int rw, int is_sync)
/*
* Use the per-process queue, for read requests and syncronous writes
*/
if (!(rw & REQ_RW) || is_sync)
return task->pid;
return CFQ_KEY_ASYNC;
}
/*
* 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;
cfqq->slice_end += cfqq->slice_resid;
/*
* Don't carry over residual for more than one slice, we only want
* to slightly correct the fairness. Carrying over forever would
* easily introduce oscillations.
*/
cfqq->slice_resid = 0;
}
/*
* 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;
/*
* 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;
/*
* 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 */
else if (d2 < d1)
else {
if (s1 >= s2)
case CFQ_RQ2_WRAP:
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)
}
}
/*
* 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);
BUG_ON(RB_EMPTY_NODE(&last->rb_node));
if (rbnext)
else {
rbnext = rb_first(&cfqq->sort_list);
if (rbnext && rbnext != &last->rb_node)
return cfq_choose_req(cfqd, next, prev);
/*
* This function finds out where to insert a BE queue in the service hierarchy
*/
static void cfq_resort_be_queue(struct cfq_data *cfqd, struct cfq_queue *cfqq,
int preempted)
if (!cfq_cfqq_sync(cfqq))
list_add_tail(&cfqq->cfq_list, &cfqd->rr_list[cfqq->ioprio]);
else {
struct list_head *n = &cfqd->rr_list[cfqq->ioprio];
/*
* sort by last service, but don't cross a new or async
* queue. we don't cross a new queue because it hasn't
* been service before, and we don't cross an async
* queue because it gets added to the end on expire.
while ((n = n->prev) != &cfqd->rr_list[cfqq->ioprio]) {
struct cfq_queue *__c = list_entry_cfqq(n);
if (!cfq_cfqq_sync(__c) || !__c->service_last)
break;
if (time_before(__c->service_last, cfqq->service_last))
break;
}
list_add(&cfqq->cfq_list, n);
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
static void cfq_resort_rr_list(struct cfq_queue *cfqq, int preempted)
{
struct cfq_data *cfqd = cfqq->cfqd;
struct list_head *n;
/*
* Resorting requires the cfqq to be on the RR list already.
*/
if (!cfq_cfqq_on_rr(cfqq))
return;
list_del(&cfqq->cfq_list);
if (cfq_class_rt(cfqq)) {
/*
* At to the front of the current list, but behind other
* RT queues.
*/
n = &cfqd->cur_rr;
while (n->next != &cfqd->cur_rr)
if (!cfq_class_rt(cfqq))
break;
list_add(&cfqq->cfq_list, n);
} else if (cfq_class_idle(cfqq)) {
/*
* IDLE goes to the tail of the idle list
*/
list_add_tail(&cfqq->cfq_list, &cfqd->idle_rr);
} else {
/*
* So we get here, ergo the queue is a regular best-effort queue
*/
cfq_resort_be_queue(cfqd, cfqq, preempted);
}
}
/*
* add to busy list of queues for service, trying to be fair in ordering
* the pending list according to last request service
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);
cfq_resort_rr_list(cfqq, 0);
}
static inline void
cfq_del_cfqq_rr(struct cfq_data *cfqd, struct cfq_queue *cfqq)
{
BUG_ON(!cfq_cfqq_on_rr(cfqq));
cfq_clear_cfqq_on_rr(cfqq);
BUG_ON(!cfqd->busy_queues);
cfqd->busy_queues--;
}
/*
* rb tree support functions
*/
static inline void cfq_del_rq_rb(struct request *rq)
struct cfq_data *cfqd = cfqq->cfqd;
BUG_ON(!cfqq->queued[sync]);
cfqq->queued[sync]--;
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 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)
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);
cfq_reposition_rq_rb(struct cfq_queue *cfqq, struct request *rq)
elv_rb_del(&cfqq->sort_list, rq);
cfqq->queued[rq_is_sync(rq)]--;
static struct request *
cfq_find_rq_fmerge(struct cfq_data *cfqd, struct bio *bio)
struct task_struct *tsk = current;
pid_t key = cfq_queue_pid(tsk, bio_data_dir(bio), bio_sync(bio));
struct cfq_queue *cfqq;
cfqq = cfq_find_cfq_hash(cfqd, key, tsk->ioprio);
if (cfqq) {
sector_t sector = bio->bi_sector + bio_sectors(bio);
return elv_rb_find(&cfqq->sort_list, sector);
static void cfq_activate_request(request_queue_t *q, struct request *rq)
struct cfq_data *cfqd = q->elevator->elevator_data;
cfqd->rq_in_driver++;
/*
* If the depth is larger 1, it really could be queueing. But lets
* make the mark a little higher - idling could still be good for
* low queueing, and a low queueing number could also just indicate
* a SCSI mid layer like behaviour where limit+1 is often seen.
*/
if (!cfqd->hw_tag && cfqd->rq_in_driver > 4)
cfqd->hw_tag = 1;
cfqd->last_position = rq->hard_sector + rq->hard_nr_sectors;
static void cfq_deactivate_request(request_queue_t *q, struct request *rq)
struct cfq_data *cfqd = q->elevator->elevator_data;
WARN_ON(!cfqd->rq_in_driver);
cfqd->rq_in_driver--;
static void cfq_remove_request(struct request *rq)
if (cfqq->next_rq == rq)
cfqq->next_rq = cfq_find_next_rq(cfqq->cfqd, cfqq, rq);
list_del_init(&rq->queuelist);
if (rq_is_meta(rq)) {
WARN_ON(!cfqq->meta_pending);
cfqq->meta_pending--;
}
}
static int
cfq_merge(request_queue_t *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;
static void cfq_merged_request(request_queue_t *q, struct request *req,
int type)
if (type == ELEVATOR_FRONT_MERGE) {
}
}
static void
cfq_merged_requests(request_queue_t *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(request_queue_t *q, struct request *rq,
struct bio *bio)
{
struct cfq_data *cfqd = q->elevator->elevator_data;
const int rw = bio_data_dir(bio);
struct cfq_queue *cfqq;
pid_t key;
/*
* Disallow merge of a sync bio into an async request.
if ((bio_data_dir(bio) == READ || 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.
key = cfq_queue_pid(current, rw, bio_sync(bio));
cfqq = cfq_find_cfq_hash(cfqd, key, current->ioprio);
if (cfqq == RQ_CFQQ(rq))
return 1;
static inline void
__cfq_set_active_queue(struct cfq_data *cfqd, struct cfq_queue *cfqq)
{
if (cfqq) {
/*
* stop potential idle class queues waiting service
*/
del_timer(&cfqd->idle_class_timer);
cfqq->slice_end = 0;
cfq_clear_cfqq_must_alloc_slice(cfqq);
cfq_clear_cfqq_fifo_expire(cfqq);
cfq_mark_cfqq_slice_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 preempted, int 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 out
* or was preempted
*/
if (timed_out && !cfq_cfqq_slice_new(cfqq))
cfqq->slice_resid = cfqq->slice_end - jiffies;
cfq_resort_rr_list(cfqq, preempted);
if (cfqq == cfqd->active_queue)
cfqd->active_queue = NULL;
if (cfqd->active_cic) {
put_io_context(cfqd->active_cic->ioc);
cfqd->active_cic = NULL;
}
cfqd->dispatch_slice = 0;
}
static inline void cfq_slice_expired(struct cfq_data *cfqd, int preempted,
int timed_out)
{
struct cfq_queue *cfqq = cfqd->active_queue;
if (cfqq)
__cfq_slice_expired(cfqd, cfqq, preempted, timed_out);
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
/*
* 0
* 0,1
* 0,1,2
* 0,1,2,3
* 0,1,2,3,4
* 0,1,2,3,4,5
* 0,1,2,3,4,5,6
* 0,1,2,3,4,5,6,7
*/
static int cfq_get_next_prio_level(struct cfq_data *cfqd)
{
int prio, wrap;
prio = -1;
wrap = 0;
do {
int p;
for (p = cfqd->cur_prio; p <= cfqd->cur_end_prio; p++) {
if (!list_empty(&cfqd->rr_list[p])) {
prio = p;
break;
}
}
if (prio != -1)
break;
cfqd->cur_prio = 0;
if (++cfqd->cur_end_prio == CFQ_PRIO_LISTS) {
cfqd->cur_end_prio = 0;
if (wrap)
break;
wrap = 1;
} while (1);
if (unlikely(prio == -1))
return -1;
BUG_ON(prio >= CFQ_PRIO_LISTS);
list_splice_init(&cfqd->rr_list[prio], &cfqd->cur_rr);
cfqd->cur_prio = prio + 1;
if (cfqd->cur_prio > cfqd->cur_end_prio) {
cfqd->cur_end_prio = cfqd->cur_prio;
cfqd->cur_prio = 0;
}
if (cfqd->cur_end_prio == CFQ_PRIO_LISTS) {
cfqd->cur_prio = 0;
cfqd->cur_end_prio = 0;
cfqd->cur_rr_tick++;
cfqd->prio_time = jiffies;
return prio;
}
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 struct cfq_queue *cfq_get_best_queue(struct cfq_data *cfqd)
{
struct cfq_queue *cfqq = NULL, *__cfqq;
list_for_each_entry(__cfqq, &cfqd->cur_rr, cfq_list) {
if (!__cfqq->next_rq || !cfq_cfqq_sync(__cfqq))
continue;
dist = cfq_dist_from_last(cfqd, __cfqq->next_rq);
if (dist < best) {
best = dist;
cfqq = __cfqq;
}
}
/*
* Only async queue(s) available, grab first entry. Do the same
* if the difference between the first and best isn't more than
* twice, to obey fairness.
if (!cfqq || (best && first != best && ((first / best) < 4)))
cfqq = list_entry_cfqq(cfqd->cur_rr.next);
return cfqq;
}
static struct cfq_queue *cfq_get_next_queue(struct cfq_data *cfqd)
if (!list_empty(&cfqd->cur_rr) || cfq_get_next_prio_level(cfqd) != -1) {
/*
* if current list is non-empty, grab first entry. if it is
* empty, get next prio level and grab first entry then if any
* are spliced
*/
} else if (!list_empty(&cfqd->idle_rr)) {
/*
* if we have idle queues and no rt or be queues had pending
* requests, either allow immediate service if the grace period
* has passed or arm the idle grace timer
*/
unsigned long end = cfqd->last_end_request + CFQ_IDLE_GRACE;
if (time_after_eq(jiffies, end))
cfqq = list_entry_cfqq(cfqd->idle_rr.next);
else
mod_timer(&cfqd->idle_class_timer, end);
}
return cfqq;
}
static struct cfq_queue *cfq_set_active_queue(struct cfq_data *cfqd)
{
struct cfq_queue *cfqq;
do {
long prio;
cfqq = cfq_get_next_queue(cfqd);
if (!cfqq)
break;
prio = cfq_prio_to_slice(cfqd, cfqq);
if (cfqq->slice_resid > -prio)
break;
cfqq->slice_resid += prio;
list_del_init(&cfqq->cfq_list);
list_add_tail(&cfqq->cfq_list, &cfqd->rr_list[cfqq->ioprio]);
cfqq = NULL;
} while (1);
__cfq_set_active_queue(cfqd, cfqq);
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
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 struct cfq_queue *__cfq_close_cooperator(struct cfq_data *cfqd,
struct cfq_queue *cur_cfqq,
struct list_head *list)
{
struct cfq_queue *cfqq;
list_for_each_entry(cfqq, list, cfq_list) {
if (cfqq == cur_cfqq || !cfq_cfqq_sync(cfqq))
continue;
BUG_ON(!cfqq->next_rq);
if (cfq_rq_close(cfqd, cfqq->next_rq))
return cfqq;
}
return NULL;
}
static int cfq_close_cooperator(struct cfq_data *cfqd,
struct cfq_queue *cur_cfqq)
{
struct cfq_queue *cfqq;
if (!cfqd->busy_queues)
return 0;
/*
* check cur_rr and same-prio rr_list for candidates
*/
cfqq = __cfq_close_cooperator(cfqd, cur_cfqq, &cfqd->cur_rr);
if (cfqq)
return 1;
cfqq = __cfq_close_cooperator(cfqd, cur_cfqq, &cfqd->rr_list[cur_cfqq->ioprio]);
if (cfqq && (cfqq->rr_tick == cfqd->cur_rr_tick))
cfqq = NULL;
return cfqq != NULL;
}
#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;
WARN_ON(!RB_EMPTY_ROOT(&cfqq->sort_list));
/*
* idle is disabled, either manually or by past process history
*/
if (!cfqd->cfq_slice_idle || !cfq_cfqq_idle_window(cfqq))
return;
/*
* task has exited, don't wait
*/
cic = cfqd->active_cic;
if (!cic || !cic->ioc->task)
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))
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
*/
if (sample_valid(cic->seek_samples) && CIC_SEEKY(cic))
sl = min(sl, msecs_to_jiffies(2));
mod_timer(&cfqd->idle_slice_timer, jiffies + sl);
static void cfq_dispatch_insert(request_queue_t *q, struct request *rq)
cfq_remove_request(rq);
elv_dispatch_sort(q, rq);
}
/*
* return expired entry, or NULL to just start from scratch in rbtree
*/
static inline struct request *cfq_check_fifo(struct cfq_queue *cfqq)