cfq-iosched.c 55.1 KB
Newer Older
Linus Torvalds's avatar
Linus Torvalds committed
1 2 3 4 5 6
/*
 *  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.
 *
7
 *  Copyright (C) 2003 Jens Axboe <axboe@kernel.dk>
Linus Torvalds's avatar
Linus Torvalds committed
8 9
 */
#include <linux/module.h>
Al Viro's avatar
Al Viro committed
10 11
#include <linux/blkdev.h>
#include <linux/elevator.h>
Linus Torvalds's avatar
Linus Torvalds committed
12 13
#include <linux/hash.h>
#include <linux/rbtree.h>
14
#include <linux/ioprio.h>
Linus Torvalds's avatar
Linus Torvalds committed
15 16 17 18

/*
 * tunables
 */
19 20 21 22
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 */
Linus Torvalds's avatar
Linus Torvalds committed
23

24
static const int cfq_slice_sync = HZ / 10;
Jens Axboe's avatar
Jens Axboe committed
25
static int cfq_slice_async = HZ / 25;
26
static const int cfq_slice_async_rq = 2;
27
static int cfq_slice_idle = HZ / 125;
28 29 30 31 32 33

#define CFQ_IDLE_GRACE		(HZ / 10)
#define CFQ_SLICE_SCALE		(5)

#define CFQ_KEY_ASYNC		(0)

Linus Torvalds's avatar
Linus Torvalds committed
34 35 36 37 38 39 40 41 42
/*
 * 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)

Jens Axboe's avatar
Jens Axboe committed
43 44
#define RQ_CIC(rq)		((struct cfq_io_context*)(rq)->elevator_private)
#define RQ_CFQQ(rq)		((rq)->elevator_private2)
Linus Torvalds's avatar
Linus Torvalds committed
45

46 47
static struct kmem_cache *cfq_pool;
static struct kmem_cache *cfq_ioc_pool;
Linus Torvalds's avatar
Linus Torvalds committed
48

49
static DEFINE_PER_CPU(unsigned long, ioc_count);
50 51
static struct completion *ioc_gone;

52 53 54 55
#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)

Jens Axboe's avatar
Jens Axboe committed
56 57 58
#define ASYNC			(0)
#define SYNC			(1)

Jens Axboe's avatar
Jens Axboe committed
59
#define cfq_cfqq_sync(cfqq)	((cfqq)->key != CFQ_KEY_ASYNC)
60

61 62
#define sample_valid(samples)	((samples) > 80)

63 64 65
/*
 * Per block device queue structure
 */
Linus Torvalds's avatar
Linus Torvalds committed
66
struct cfq_data {
67 68 69 70 71 72 73 74
	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;
Jens Axboe's avatar
Jens Axboe committed
75
	unsigned long cur_rr_tick;
76 77 78 79 80
	unsigned int busy_queues;

	/*
	 * cfqq lookup hash
	 */
Linus Torvalds's avatar
Linus Torvalds committed
81 82
	struct hlist_head *cfq_hash;

83
	int rq_in_driver;
84
	int hw_tag;
Linus Torvalds's avatar
Linus Torvalds committed
85

86 87 88 89 90
	/*
	 * idle window management
	 */
	struct timer_list idle_slice_timer;
	struct work_struct unplug_work;
Linus Torvalds's avatar
Linus Torvalds committed
91

92 93 94
	struct cfq_queue *active_queue;
	struct cfq_io_context *active_cic;
	int cur_prio, cur_end_prio;
Jens Axboe's avatar
Jens Axboe committed
95
	unsigned long prio_time;
96 97 98
	unsigned int dispatch_slice;

	struct timer_list idle_class_timer;
Linus Torvalds's avatar
Linus Torvalds committed
99

Jens Axboe's avatar
Jens Axboe committed
100
	sector_t last_position;
101
	unsigned long last_end_request;
Linus Torvalds's avatar
Linus Torvalds committed
102 103 104 105 106

	/*
	 * tunables, see top of file
	 */
	unsigned int cfq_quantum;
107
	unsigned int cfq_fifo_expire[2];
Linus Torvalds's avatar
Linus Torvalds committed
108 109
	unsigned int cfq_back_penalty;
	unsigned int cfq_back_max;
110 111 112
	unsigned int cfq_slice[2];
	unsigned int cfq_slice_async_rq;
	unsigned int cfq_slice_idle;
113 114

	struct list_head cic_list;
Jens Axboe's avatar
Jens Axboe committed
115 116 117

	sector_t new_seek_mean;
	u64 new_seek_total;
Linus Torvalds's avatar
Linus Torvalds committed
118 119
};

120 121 122
/*
 * Per process-grouping structure
 */
Linus Torvalds's avatar
Linus Torvalds committed
123 124 125 126 127
struct cfq_queue {
	/* reference count */
	atomic_t ref;
	/* parent cfq_data */
	struct cfq_data *cfqd;
128
	/* cfqq lookup hash */
Linus Torvalds's avatar
Linus Torvalds committed
129 130
	struct hlist_node cfq_hash;
	/* hash key */
131
	unsigned int key;
132
	/* member of the rr/busy/cur/idle cfqd list */
Linus Torvalds's avatar
Linus Torvalds committed
133
	struct list_head cfq_list;
Jens Axboe's avatar
Jens Axboe committed
134 135
	/* in what tick we were last serviced */
	unsigned long rr_tick;
Linus Torvalds's avatar
Linus Torvalds committed
136 137 138
	/* sorted list of pending requests */
	struct rb_root sort_list;
	/* if fifo isn't expired, next request to serve */
Jens Axboe's avatar
Jens Axboe committed
139
	struct request *next_rq;
Linus Torvalds's avatar
Linus Torvalds committed
140 141 142 143
	/* requests queued in sort_list */
	int queued[2];
	/* currently allocated requests */
	int allocated[2];
144 145
	/* pending metadata requests */
	int meta_pending;
Linus Torvalds's avatar
Linus Torvalds committed
146
	/* fifo list of requests in sort_list */
147
	struct list_head fifo;
Linus Torvalds's avatar
Linus Torvalds committed
148

149
	unsigned long slice_end;
150
	unsigned long service_last;
Jens Axboe's avatar
Jens Axboe committed
151
	unsigned long slice_start;
152
	long slice_resid;
Linus Torvalds's avatar
Linus Torvalds committed
153

Jens Axboe's avatar
Jens Axboe committed
154 155
	/* number of requests that are on the dispatch list or inside driver */
	int dispatched;
156 157 158 159 160

	/* io prio of this group */
	unsigned short ioprio, org_ioprio;
	unsigned short ioprio_class, org_ioprio_class;

Jens Axboe's avatar
Jens Axboe committed
161 162
	/* various state flags, see below */
	unsigned int flags;
Jens Axboe's avatar
Jens Axboe committed
163 164

	sector_t last_request_pos;
Linus Torvalds's avatar
Linus Torvalds committed
165 166
};

Jens Axboe's avatar
Jens Axboe committed
167
enum cfqq_state_flags {
168 169 170 171 172 173 174 175 176
	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 */
177
	CFQ_CFQQ_FLAG_slice_new,	/* no requests dispatched in slice */
Jens Axboe's avatar
Jens Axboe committed
178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201
};

#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);
202
CFQ_CFQQ_FNS(queue_new);
203
CFQ_CFQQ_FNS(slice_new);
Jens Axboe's avatar
Jens Axboe committed
204 205 206
#undef CFQ_CFQQ_FNS

static struct cfq_queue *cfq_find_cfq_hash(struct cfq_data *, unsigned int, unsigned short);
Jens Axboe's avatar
Jens Axboe committed
207
static void cfq_dispatch_insert(request_queue_t *, struct request *);
208
static struct cfq_queue *cfq_get_queue(struct cfq_data *cfqd, unsigned int key, struct task_struct *tsk, gfp_t gfp_mask);
Linus Torvalds's avatar
Linus Torvalds committed
209

Andrew Morton's avatar
Andrew Morton committed
210 211 212 213 214 215
/*
 * 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)
{
216
	if (cfqd->busy_queues)
Andrew Morton's avatar
Andrew Morton committed
217 218 219 220 221 222 223
		kblockd_schedule_work(&cfqd->unplug_work);
}

static int cfq_queue_empty(request_queue_t *q)
{
	struct cfq_data *cfqd = q->elevator->elevator_data;

224
	return !cfqd->busy_queues;
Andrew Morton's avatar
Andrew Morton committed
225 226
}

227
static inline pid_t cfq_queue_pid(struct task_struct *task, int rw, int is_sync)
228
{
229 230 231 232
	/*
	 * Use the per-process queue, for read requests and syncronous writes
	 */
	if (!(rw & REQ_RW) || is_sync)
233 234 235 236 237
		return task->pid;

	return CFQ_KEY_ASYNC;
}

238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256
/*
 * 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;
257 258 259 260 261 262 263 264
	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;
Jens Axboe's avatar
Jens Axboe committed
265 266

	cfqq->slice_start = jiffies;
267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283
}

/*
 * 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;
}

Linus Torvalds's avatar
Linus Torvalds committed
284
/*
Jens Axboe's avatar
Jens Axboe committed
285
 * Lifted from AS - choose which of rq1 and rq2 that is best served now.
Linus Torvalds's avatar
Linus Torvalds committed
286
 * We choose the request that is closest to the head right now. Distance
287
 * behind the head is penalized and only allowed to a certain extent.
Linus Torvalds's avatar
Linus Torvalds committed
288
 */
Jens Axboe's avatar
Jens Axboe committed
289 290
static struct request *
cfq_choose_req(struct cfq_data *cfqd, struct request *rq1, struct request *rq2)
Linus Torvalds's avatar
Linus Torvalds committed
291 292 293
{
	sector_t last, s1, s2, d1 = 0, d2 = 0;
	unsigned long back_max;
294 295 296
#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? */
Linus Torvalds's avatar
Linus Torvalds committed
297

Jens Axboe's avatar
Jens Axboe committed
298 299 300 301
	if (rq1 == NULL || rq1 == rq2)
		return rq2;
	if (rq2 == NULL)
		return rq1;
302

Jens Axboe's avatar
Jens Axboe committed
303 304 305 306
	if (rq_is_sync(rq1) && !rq_is_sync(rq2))
		return rq1;
	else if (rq_is_sync(rq2) && !rq_is_sync(rq1))
		return rq2;
307 308 309 310
	if (rq_is_meta(rq1) && !rq_is_meta(rq2))
		return rq1;
	else if (rq_is_meta(rq2) && !rq_is_meta(rq1))
		return rq2;
Linus Torvalds's avatar
Linus Torvalds committed
311

Jens Axboe's avatar
Jens Axboe committed
312 313
	s1 = rq1->sector;
	s2 = rq2->sector;
Linus Torvalds's avatar
Linus Torvalds committed
314

Jens Axboe's avatar
Jens Axboe committed
315
	last = cfqd->last_position;
Linus Torvalds's avatar
Linus Torvalds committed
316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331

	/*
	 * 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
332
		wrap |= CFQ_RQ1_WRAP;
Linus Torvalds's avatar
Linus Torvalds committed
333 334 335 336 337 338

	if (s2 >= last)
		d2 = s2 - last;
	else if (s2 + back_max >= last)
		d2 = (last - s2) * cfqd->cfq_back_penalty;
	else
339
		wrap |= CFQ_RQ2_WRAP;
Linus Torvalds's avatar
Linus Torvalds committed
340 341

	/* Found required data */
342 343 344 345 346 347

	/*
	 * By doing switch() on the bit mask "wrap" we avoid having to
	 * check two variables for all permutations: --> faster!
	 */
	switch (wrap) {
Jens Axboe's avatar
Jens Axboe committed
348
	case 0: /* common case for CFQ: rq1 and rq2 not wrapped */
349
		if (d1 < d2)
Jens Axboe's avatar
Jens Axboe committed
350
			return rq1;
351
		else if (d2 < d1)
Jens Axboe's avatar
Jens Axboe committed
352
			return rq2;
353 354
		else {
			if (s1 >= s2)
Jens Axboe's avatar
Jens Axboe committed
355
				return rq1;
356
			else
Jens Axboe's avatar
Jens Axboe committed
357
				return rq2;
358
		}
Linus Torvalds's avatar
Linus Torvalds committed
359

360
	case CFQ_RQ2_WRAP:
Jens Axboe's avatar
Jens Axboe committed
361
		return rq1;
362
	case CFQ_RQ1_WRAP:
Jens Axboe's avatar
Jens Axboe committed
363 364
		return rq2;
	case (CFQ_RQ1_WRAP|CFQ_RQ2_WRAP): /* both rqs wrapped */
365 366 367 368 369 370 371 372
	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)
Jens Axboe's avatar
Jens Axboe committed
373
			return rq1;
Linus Torvalds's avatar
Linus Torvalds committed
374
		else
Jens Axboe's avatar
Jens Axboe committed
375
			return rq2;
Linus Torvalds's avatar
Linus Torvalds committed
376 377 378 379 380 381
	}
}

/*
 * would be nice to take fifo expire time into account as well
 */
Jens Axboe's avatar
Jens Axboe committed
382 383 384
static struct request *
cfq_find_next_rq(struct cfq_data *cfqd, struct cfq_queue *cfqq,
		  struct request *last)
Linus Torvalds's avatar
Linus Torvalds committed
385
{
386 387
	struct rb_node *rbnext = rb_next(&last->rb_node);
	struct rb_node *rbprev = rb_prev(&last->rb_node);
Jens Axboe's avatar
Jens Axboe committed
388
	struct request *next = NULL, *prev = NULL;
Linus Torvalds's avatar
Linus Torvalds committed
389

390
	BUG_ON(RB_EMPTY_NODE(&last->rb_node));
Linus Torvalds's avatar
Linus Torvalds committed
391 392

	if (rbprev)
Jens Axboe's avatar
Jens Axboe committed
393
		prev = rb_entry_rq(rbprev);
Linus Torvalds's avatar
Linus Torvalds committed
394

395
	if (rbnext)
Jens Axboe's avatar
Jens Axboe committed
396
		next = rb_entry_rq(rbnext);
397 398 399
	else {
		rbnext = rb_first(&cfqq->sort_list);
		if (rbnext && rbnext != &last->rb_node)
Jens Axboe's avatar
Jens Axboe committed
400
			next = rb_entry_rq(rbnext);
401
	}
Linus Torvalds's avatar
Linus Torvalds committed
402

403
	return cfq_choose_req(cfqd, next, prev);
Linus Torvalds's avatar
Linus Torvalds committed
404 405
}

Jens Axboe's avatar
Jens Axboe committed
406 407 408 409 410
/*
 * 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)
Linus Torvalds's avatar
Linus Torvalds committed
411
{
Jens Axboe's avatar
Jens Axboe committed
412 413 414 415
	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];
Linus Torvalds's avatar
Linus Torvalds committed
416

417 418
		/*
		 * sort by last service, but don't cross a new or async
Jens Axboe's avatar
Jens Axboe committed
419 420 421
		 * 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.
422
		 */
Jens Axboe's avatar
Jens Axboe committed
423
		while ((n = n->prev) != &cfqd->rr_list[cfqq->ioprio]) {
Jens Axboe's avatar
Jens Axboe committed
424
			struct cfq_queue *__c = list_entry_cfqq(n);
Linus Torvalds's avatar
Linus Torvalds committed
425

Jens Axboe's avatar
Jens Axboe committed
426
			if (!cfq_cfqq_sync(__c) || !__c->service_last)
427
				break;
Jens Axboe's avatar
Jens Axboe committed
428
			if (time_before(__c->service_last, cfqq->service_last))
429 430 431
				break;
		}
		list_add(&cfqq->cfq_list, n);
Linus Torvalds's avatar
Linus Torvalds committed
432 433 434
	}
}

Jens Axboe's avatar
Jens Axboe committed
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);
	}
}

Linus Torvalds's avatar
Linus Torvalds committed
472 473
/*
 * add to busy list of queues for service, trying to be fair in ordering
474
 * the pending list according to last request service
Linus Torvalds's avatar
Linus Torvalds committed
475 476
 */
static inline void
477
cfq_add_cfqq_rr(struct cfq_data *cfqd, struct cfq_queue *cfqq)
Linus Torvalds's avatar
Linus Torvalds committed
478
{
Jens Axboe's avatar
Jens Axboe committed
479 480
	BUG_ON(cfq_cfqq_on_rr(cfqq));
	cfq_mark_cfqq_on_rr(cfqq);
Linus Torvalds's avatar
Linus Torvalds committed
481 482
	cfqd->busy_queues++;

483
	cfq_resort_rr_list(cfqq, 0);
Linus Torvalds's avatar
Linus Torvalds committed
484 485 486 487 488
}

static inline void
cfq_del_cfqq_rr(struct cfq_data *cfqd, struct cfq_queue *cfqq)
{
Jens Axboe's avatar
Jens Axboe committed
489 490
	BUG_ON(!cfq_cfqq_on_rr(cfqq));
	cfq_clear_cfqq_on_rr(cfqq);
491
	list_del_init(&cfqq->cfq_list);
Linus Torvalds's avatar
Linus Torvalds committed
492 493 494 495 496 497 498 499

	BUG_ON(!cfqd->busy_queues);
	cfqd->busy_queues--;
}

/*
 * rb tree support functions
 */
Jens Axboe's avatar
Jens Axboe committed
500
static inline void cfq_del_rq_rb(struct request *rq)
Linus Torvalds's avatar
Linus Torvalds committed
501
{
Jens Axboe's avatar
Jens Axboe committed
502
	struct cfq_queue *cfqq = RQ_CFQQ(rq);
503
	struct cfq_data *cfqd = cfqq->cfqd;
Jens Axboe's avatar
Jens Axboe committed
504
	const int sync = rq_is_sync(rq);
Linus Torvalds's avatar
Linus Torvalds committed
505

506 507
	BUG_ON(!cfqq->queued[sync]);
	cfqq->queued[sync]--;
Linus Torvalds's avatar
Linus Torvalds committed
508

Jens Axboe's avatar
Jens Axboe committed
509
	elv_rb_del(&cfqq->sort_list, rq);
Linus Torvalds's avatar
Linus Torvalds committed
510

511
	if (cfq_cfqq_on_rr(cfqq) && RB_EMPTY_ROOT(&cfqq->sort_list))
512
		cfq_del_cfqq_rr(cfqd, cfqq);
Linus Torvalds's avatar
Linus Torvalds committed
513 514
}

Jens Axboe's avatar
Jens Axboe committed
515
static void cfq_add_rq_rb(struct request *rq)
Linus Torvalds's avatar
Linus Torvalds committed
516
{
Jens Axboe's avatar
Jens Axboe committed
517
	struct cfq_queue *cfqq = RQ_CFQQ(rq);
Linus Torvalds's avatar
Linus Torvalds committed
518
	struct cfq_data *cfqd = cfqq->cfqd;
519
	struct request *__alias;
Linus Torvalds's avatar
Linus Torvalds committed
520

521
	cfqq->queued[rq_is_sync(rq)]++;
Linus Torvalds's avatar
Linus Torvalds committed
522 523 524 525 526

	/*
	 * looks a little odd, but the first insert might return an alias.
	 * if that happens, put the alias on the dispatch list
	 */
527
	while ((__alias = elv_rb_add(&cfqq->sort_list, rq)) != NULL)
Jens Axboe's avatar
Jens Axboe committed
528
		cfq_dispatch_insert(cfqd->queue, __alias);
529 530 531

	if (!cfq_cfqq_on_rr(cfqq))
		cfq_add_cfqq_rr(cfqd, cfqq);
532 533 534 535 536 537

	/*
	 * 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);
Linus Torvalds's avatar
Linus Torvalds committed
538 539 540
}

static inline void
Jens Axboe's avatar
Jens Axboe committed
541
cfq_reposition_rq_rb(struct cfq_queue *cfqq, struct request *rq)
Linus Torvalds's avatar
Linus Torvalds committed
542
{
543 544
	elv_rb_del(&cfqq->sort_list, rq);
	cfqq->queued[rq_is_sync(rq)]--;
Jens Axboe's avatar
Jens Axboe committed
545
	cfq_add_rq_rb(rq);
Linus Torvalds's avatar
Linus Torvalds committed
546 547
}

548 549
static struct request *
cfq_find_rq_fmerge(struct cfq_data *cfqd, struct bio *bio)
Linus Torvalds's avatar
Linus Torvalds committed
550
{
551
	struct task_struct *tsk = current;
552
	pid_t key = cfq_queue_pid(tsk, bio_data_dir(bio), bio_sync(bio));
553
	struct cfq_queue *cfqq;
Linus Torvalds's avatar
Linus Torvalds committed
554

555
	cfqq = cfq_find_cfq_hash(cfqd, key, tsk->ioprio);
556 557 558
	if (cfqq) {
		sector_t sector = bio->bi_sector + bio_sectors(bio);

559
		return elv_rb_find(&cfqq->sort_list, sector);
560
	}
Linus Torvalds's avatar
Linus Torvalds committed
561 562 563 564

	return NULL;
}

565
static void cfq_activate_request(request_queue_t *q, struct request *rq)
Linus Torvalds's avatar
Linus Torvalds committed
566
{
567
	struct cfq_data *cfqd = q->elevator->elevator_data;
Jens Axboe's avatar
Jens Axboe committed
568

569
	cfqd->rq_in_driver++;
570 571 572 573 574 575 576 577 578

	/*
	 * 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;
Jens Axboe's avatar
Jens Axboe committed
579 580

	cfqd->last_position = rq->hard_sector + rq->hard_nr_sectors;
Linus Torvalds's avatar
Linus Torvalds committed
581 582
}

583
static void cfq_deactivate_request(request_queue_t *q, struct request *rq)
Linus Torvalds's avatar
Linus Torvalds committed
584
{
585 586 587 588
	struct cfq_data *cfqd = q->elevator->elevator_data;

	WARN_ON(!cfqd->rq_in_driver);
	cfqd->rq_in_driver--;
Linus Torvalds's avatar
Linus Torvalds committed
589 590
}

591
static void cfq_remove_request(struct request *rq)
Linus Torvalds's avatar
Linus Torvalds committed
592
{
Jens Axboe's avatar
Jens Axboe committed
593
	struct cfq_queue *cfqq = RQ_CFQQ(rq);
594

Jens Axboe's avatar
Jens Axboe committed
595 596
	if (cfqq->next_rq == rq)
		cfqq->next_rq = cfq_find_next_rq(cfqq->cfqd, cfqq, rq);
Linus Torvalds's avatar
Linus Torvalds committed
597

598
	list_del_init(&rq->queuelist);
Jens Axboe's avatar
Jens Axboe committed
599
	cfq_del_rq_rb(rq);
600 601 602 603 604

	if (rq_is_meta(rq)) {
		WARN_ON(!cfqq->meta_pending);
		cfqq->meta_pending--;
	}
Linus Torvalds's avatar
Linus Torvalds committed
605 606 607 608 609 610 611 612
}

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;

613
	__rq = cfq_find_rq_fmerge(cfqd, bio);
614
	if (__rq && elv_rq_merge_ok(__rq, bio)) {
615 616
		*req = __rq;
		return ELEVATOR_FRONT_MERGE;
Linus Torvalds's avatar
Linus Torvalds committed
617 618 619 620 621
	}

	return ELEVATOR_NO_MERGE;
}

622 623
static void cfq_merged_request(request_queue_t *q, struct request *req,
			       int type)
Linus Torvalds's avatar
Linus Torvalds committed
624
{
625
	if (type == ELEVATOR_FRONT_MERGE) {
Jens Axboe's avatar
Jens Axboe committed
626
		struct cfq_queue *cfqq = RQ_CFQQ(req);
Linus Torvalds's avatar
Linus Torvalds committed
627

Jens Axboe's avatar
Jens Axboe committed
628
		cfq_reposition_rq_rb(cfqq, req);
Linus Torvalds's avatar
Linus Torvalds committed
629 630 631 632 633 634 635
	}
}

static void
cfq_merged_requests(request_queue_t *q, struct request *rq,
		    struct request *next)
{
636 637 638 639 640 641 642
	/*
	 * 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);

643
	cfq_remove_request(next);
644 645
}

646 647 648 649 650 651 652 653 654
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;

	/*
655
	 * Disallow merge of a sync bio into an async request.
656
	 */
657
	if ((bio_data_dir(bio) == READ || bio_sync(bio)) && !rq_is_sync(rq))
658 659 660
		return 0;

	/*
661 662
	 * Lookup the cfqq that this bio will be queued with. Allow
	 * merge only if rq is queued there.
663
	 */
664
	key = cfq_queue_pid(current, rw, bio_sync(bio));
665
	cfqq = cfq_find_cfq_hash(cfqd, key, current->ioprio);
666 667 668

	if (cfqq == RQ_CFQQ(rq))
		return 1;
669

670
	return 0;
671 672
}

673 674 675 676 677 678 679 680 681 682
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;
Jens Axboe's avatar
Jens Axboe committed
683 684
		cfq_clear_cfqq_must_alloc_slice(cfqq);
		cfq_clear_cfqq_fifo_expire(cfqq);
685
		cfq_mark_cfqq_slice_new(cfqq);
Jens Axboe's avatar
Jens Axboe committed
686
		cfq_clear_cfqq_queue_new(cfqq);
Jens Axboe's avatar
Jens Axboe committed
687
		cfqq->rr_tick = cfqd->cur_rr_tick;
688 689 690 691 692
	}

	cfqd->active_queue = cfqq;
}

693 694 695 696 697
/*
 * 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,
698
		    int preempted, int timed_out)
699 700 701 702 703 704 705 706 707 708 709
{
	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
	 */
710
	if (timed_out && !cfq_cfqq_slice_new(cfqq))
711
		cfqq->slice_resid = cfqq->slice_end - jiffies;
712

713
	cfq_resort_rr_list(cfqq, preempted);
714 715 716 717 718 719 720 721 722 723 724 725

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

726 727
static inline void cfq_slice_expired(struct cfq_data *cfqd, int preempted,
				     int timed_out)
728 729 730 731
{
	struct cfq_queue *cfqq = cfqd->active_queue;

	if (cfqq)
732
		__cfq_slice_expired(cfqd, cfqq, preempted, timed_out);
733 734
}

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;
Linus Torvalds's avatar
Linus Torvalds committed
769
		}
770 771 772 773 774 775 776 777 778 779 780 781 782 783 784 785 786
	} 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;
Linus Torvalds's avatar
Linus Torvalds committed
787 788
	}

Jens Axboe's avatar
Jens Axboe committed
789 790
	cfqd->cur_rr_tick++;
	cfqd->prio_time = jiffies;
791 792 793
	return prio;
}

Jens Axboe's avatar
Jens Axboe committed
794 795 796 797 798 799 800 801 802 803 804 805
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;
Jens Axboe's avatar
Jens Axboe committed
806
	sector_t best = -1, first = -1, dist;
Jens Axboe's avatar
Jens Axboe committed
807 808 809 810 811 812

	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);
Jens Axboe's avatar
Jens Axboe committed
813 814
		if (first == -1)
			first = dist;
Jens Axboe's avatar
Jens Axboe committed
815 816 817 818 819 820 821
		if (dist < best) {
			best = dist;
			cfqq = __cfqq;
		}
	}

	/*
Jens Axboe's avatar
Jens Axboe committed
822 823 824
	 * 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.
Jens Axboe's avatar
Jens Axboe committed
825
	 */
Jens Axboe's avatar
Jens Axboe committed
826
	if (!cfqq || (best && first != best && ((first / best) < 4)))
Jens Axboe's avatar
Jens Axboe committed
827 828 829 830 831 832
		cfqq = list_entry_cfqq(cfqd->cur_rr.next);

	return cfqq;
}

static struct cfq_queue *cfq_get_next_queue(struct cfq_data *cfqd)
833
{
834
	struct cfq_queue *cfqq = NULL;
835

836 837 838 839 840 841
	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
		 */
Jens Axboe's avatar
Jens Axboe committed
842
		cfqq = cfq_get_best_queue(cfqd);
843 844 845 846 847 848
	} 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
		 */
849 850 851 852 853 854 855 856
		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);
	}

Jens Axboe's avatar
Jens Axboe committed
857 858 859 860 861 862 863 864 865 866 867 868 869 870 871 872 873 874 875 876 877 878 879 880
	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);

881
	__cfq_set_active_queue(cfqd, cfqq);
Jens Axboe's avatar
Jens Axboe committed
882
	return cfqq;
883 884
}

Jens Axboe's avatar
Jens Axboe committed
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))
937

Jens Axboe's avatar
Jens Axboe committed
938
static void cfq_arm_slice_timer(struct cfq_data *cfqd)
939
{
940
	struct cfq_queue *cfqq = cfqd->active_queue;
941
	struct cfq_io_context *cic;
942 943
	unsigned long sl;

944
	WARN_ON(!RB_EMPTY_ROOT(&cfqq->sort_list));
Jens Axboe's avatar
Jens Axboe committed
945
	WARN_ON(cfq_cfqq_slice_new(cfqq));
946 947 948 949

	/*
	 * idle is disabled, either manually or by past process history
	 */
Jens Axboe's avatar
Jens Axboe committed
950 951 952
	if (!cfqd->cfq_slice_idle || !cfq_cfqq_idle_window(cfqq))
		return;

953 954 955
	/*
	 * task has exited, don't wait
	 */
956 957
	cic = cfqd->active_cic;
	if (!cic || !cic->ioc->task)
Jens Axboe's avatar
Jens Axboe committed
958 959 960 961 962
		return;

	/*
	 * See if this prio level has a good candidate
	 */
Jens Axboe's avatar
Jens Axboe committed
963 964
	if (cfq_close_cooperator(cfqd, cfqq) &&
	    (sample_valid(cic->ttime_samples) && cic->ttime_mean > 2))
Jens Axboe's avatar
Jens Axboe committed
965
		return;
966

Jens Axboe's avatar
Jens Axboe committed
967 968
	cfq_mark_cfqq_must_dispatch(cfqq);
	cfq_mark_cfqq_wait_request(cfqq);
969

970 971 972 973 974
	/*
	 * 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
	 */
Jens Axboe's avatar
Jens Axboe committed
975
	sl = cfqd->cfq_slice_idle;
976
	if (sample_valid(cic->seek_samples) && CIC_SEEKY(cic))
977
		sl = min(sl, msecs_to_jiffies(2));
978

979
	mod_timer(&cfqd->idle_slice_timer, jiffies + sl);
Linus Torvalds's avatar
Linus Torvalds committed
980 981
}

Jens Axboe's avatar
Jens Axboe committed
982
static void cfq_dispatch_insert(request_queue_t *q, struct request *rq)
Linus Torvalds's avatar
Linus Torvalds committed
983
{
Jens Axboe's avatar
Jens Axboe committed
984
	struct cfq_queue *cfqq = RQ_CFQQ(rq);
985

986
	cfq_remove_request(rq);
Jens Axboe's avatar
Jens Axboe committed
987
	cfqq->dispatched++;
988
	elv_dispatch_sort(q, rq);
Linus Torvalds's avatar
Linus Torvalds committed
989 990 991 992 993
}

/*
 * return expired entry, or NULL to just start from scratch in rbtree
 */
Jens Axboe's avatar
Jens Axboe committed
994
static inline struct request *cfq_check_fifo(struct cfq_queue *cfqq)
Linus Torvalds's avatar
Linus Torvalds committed
995 996
{
	struct cfq_data *cfqd = cfqq->cfqd;
997
	struct request *rq;
998
	int fifo;
Linus Torvalds's avatar
Linus Torvalds committed
999

Jens Axboe's avatar
Jens Axboe committed
1000
	if (cfq_cfqq_fifo_expire(cfqq))
Linus Torvalds's avatar
Linus Torvalds committed
1001
		return NULL;
1002 1003 1004

	cfq_mark_cfqq_fifo_expire(cfqq);

1005 1006
	if (list_empty(&cfqq->fifo))
		return NULL;
Linus Torvalds's avatar
Linus Torvalds committed
1007

Jens Axboe's avatar
Jens Axboe committed
1008
	fifo = cfq_cfqq_sync(cfqq);
1009
	rq = rq_entry_fifo(cfqq->fifo.next);
Linus Torvalds's avatar
Linus Torvalds committed
1010

Jens Axboe's avatar
Jens Axboe committed
1011 1012
	if (time_before(jiffies, rq->start_time + cfqd->cfq_fifo_expire[fifo]))
		return NULL;
Linus Torvalds's avatar
Linus Torvalds committed
1013

Jens Axboe's avatar
Jens Axboe committed
1014
	return rq;
Linus Torvalds's avatar
Linus Torvalds committed
1015 1016
}

1017 1018 1019 1020
static inline int
cfq_prio_to_maxrq(struct cfq_data *cfqd, struct cfq_queue *cfqq)
{
	const int base_rq = cfqd->cfq_slice_async_rq;
Linus Torvalds's avatar
Linus Torvalds committed
1021

1022
	WARN_ON(cfqq->ioprio >= IOPRIO_BE_NR);
Linus Torvalds's avatar
Linus Torvalds committed
1023

1024
	return 2 * (base_rq + base_rq * (CFQ_PRIO_LISTS - 1 - cfqq->ioprio));
Linus Torvalds's avatar
Linus Torvalds committed
1025 1026
}

1027 1028 1029
/*
 * get next queue for service
 */
1030
static struct cfq_queue *cfq_select_queue(struct cfq_data *cfqd)
Linus Torvalds's avatar
Linus Torvalds committed
1031 1032 1033
{
	struct cfq_queue *cfqq;

1034 1035 1036
	cfqq = cfqd->active_queue;
	if (!cfqq)
		goto new_queue;
Linus Torvalds's avatar
Linus Torvalds committed
1037

1038
	/*
Jens Axboe's avatar
Jens Axboe committed
1039
	 * The active queue has run out of time, expire it and select new.
1040
	 */
Jens Axboe's avatar
Jens Axboe committed
1041
	if (cfq_slice_used(cfqq))
Jens Axboe's avatar
Jens Axboe committed
1042
		goto expire;
Linus Torvalds's avatar
Linus Torvalds committed
1043

1044
	/*
Jens Axboe's avatar
Jens Axboe committed
1045 1046
	 * The active queue has requests and isn't expired, allow it to
	 * dispatch.
1047
	 */
1048
	if (!RB_EMPTY_ROOT(&cfqq->sort_list))
1049
		goto keep_queue;
Jens Axboe's avatar
Jens Axboe committed
1050 1051 1052 1053 1054 1055 1056

	/*
	 * 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 (cfqq->dispatched || timer_pending(&cfqd->idle_slice_timer)) {
1057 1058
		cfqq = NULL;
		goto keep_queue;
1059 1060
	}

Jens Axboe's avatar
Jens Axboe committed
1061
expire:
1062
	cfq_slice_expired(cfqd, 0, 0);
Jens Axboe's avatar
Jens Axboe committed
1063 1064
new_queue:
	cfqq = cfq_set_active_queue(cfqd);
1065
keep_queue:
Jens Axboe's avatar
Jens Axboe committed
1066
	return cfqq;
1067 1068 1069 1070 1071 1072 1073 1074
}

static int
__cfq_dispatch_requests(struct cfq_data *cfqd, struct cfq_queue *cfqq,
			int max_dispatch)
{
	int dispatched = 0;

1075
	BUG_ON(RB_EMPTY_ROOT(&cfqq->sort_list));
1076 1077

	do {
Jens Axboe's avatar
Jens Axboe committed
1078
		struct request *rq;
Linus Torvalds's avatar
Linus Torvalds committed
1079 1080

		/*
1081
		 * follow expired path, else get first next available
Linus Torvalds's avatar
Linus Torvalds committed
1082
		 */
Jens Axboe's avatar
Jens Axboe committed
1083 1084
		if ((rq = cfq_check_fifo(cfqq)) == NULL)
			rq = cfqq->next_rq;
1085 1086 1087 1088

		/*
		 * finally, insert request into driver dispatch list
		 */
Jens Axboe's avatar
Jens Axboe committed
1089
		cfq_dispatch_insert(cfqd->queue, rq);
Linus Torvalds's avatar
Linus Torvalds committed
1090

1091 1092
		cfqd->dispatch_slice++;
		dispatched++;
Linus Torvalds's avatar
Linus Torvalds committed
1093

1094
		if (!cfqd->active_cic) {
Jens Axboe's avatar
Jens Axboe committed
1095 1096
			atomic_inc(&RQ_CIC(rq)->ioc->refcount);
			cfqd->active_cic = RQ_CIC(rq);
1097
		}
Linus Torvalds's avatar
Linus Torvalds committed
1098

1099
		if (RB_EMPTY_ROOT(&cfqq->sort_list))
1100 1101 1102 1103 1104 1105 1106 1107
			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.
	 */
1108
	if (cfqd->busy_queues > 1 && ((!cfq_cfqq_sync(cfqq) &&
1109
	    cfqd->dispatch_slice >= cfq_prio_to_maxrq(cfqd, cfqq)) ||
1110
	    cfq_class_idle(cfqq))) {
1111
		cfqq->slice_end = jiffies + 1;