cfq-iosched.c 63.2 KB
Newer Older
L
Linus Torvalds 已提交
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>
L
Linus Torvalds 已提交
8 9
 */
#include <linux/module.h>
A
Al Viro 已提交
10 11
#include <linux/blkdev.h>
#include <linux/elevator.h>
L
Linus Torvalds 已提交
12
#include <linux/rbtree.h>
13
#include <linux/ioprio.h>
14
#include <linux/blktrace_api.h>
L
Linus Torvalds 已提交
15 16 17 18

/*
 * tunables
 */
19 20
/* max queue in one round of service */
static const int cfq_quantum = 4;
21
static const int cfq_fifo_expire[2] = { HZ / 4, HZ / 8 };
22 23 24 25
/* 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;
26
static const int cfq_slice_sync = HZ / 10;
J
Jens Axboe 已提交
27
static int cfq_slice_async = HZ / 25;
28
static const int cfq_slice_async_rq = 2;
29
static int cfq_slice_idle = HZ / 125;
30

31
/*
32
 * offset from end of service tree
33
 */
34
#define CFQ_IDLE_DELAY		(HZ / 5)
35 36 37 38 39 40

/*
 * below this threshold, we consider thinktime immediate
 */
#define CFQ_MIN_TT		(2)

41
#define CFQ_SLICE_SCALE		(5)
42
#define CFQ_HW_QUEUE_MIN	(5)
43

44 45
#define RQ_CIC(rq)		\
	((struct cfq_io_context *) (rq)->elevator_private)
46
#define RQ_CFQQ(rq)		(struct cfq_queue *) ((rq)->elevator_private2)
L
Linus Torvalds 已提交
47

48 49
static struct kmem_cache *cfq_pool;
static struct kmem_cache *cfq_ioc_pool;
L
Linus Torvalds 已提交
50

51
static DEFINE_PER_CPU(unsigned long, ioc_count);
52
static struct completion *ioc_gone;
53
static DEFINE_SPINLOCK(ioc_gone_lock);
54

55 56 57 58
#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)

59 60
#define sample_valid(samples)	((samples) > 80)

61 62 63 64 65 66 67 68 69 70 71 72
/*
 * 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, }

73 74 75
/*
 * Per block device queue structure
 */
L
Linus Torvalds 已提交
76
struct cfq_data {
77
	struct request_queue *queue;
78 79 80 81

	/*
	 * rr list of queues with requests and the count of them
	 */
82
	struct cfq_rb_root service_tree;
83 84 85 86 87 88 89 90

	/*
	 * Each priority tree is sorted by next_request position.  These
	 * trees are used when determining if two or more queues are
	 * interleaving requests (see cfq_close_cooperator).
	 */
	struct rb_root prio_trees[CFQ_PRIO_LISTS];

91
	unsigned int busy_queues;
92 93 94 95 96
	/*
	 * Used to track any pending rt requests so we can pre-empt current
	 * non-RT cfqq in service when this value is non-zero.
	 */
	unsigned int busy_rt_queues;
97 98

	int rq_in_driver;
99
	int sync_flight;
100 101 102 103 104

	/*
	 * queue-depth detection
	 */
	int rq_queued;
105
	int hw_tag;
106 107
	int hw_tag_samples;
	int rq_in_driver_peak;
L
Linus Torvalds 已提交
108

109 110 111 112 113
	/*
	 * idle window management
	 */
	struct timer_list idle_slice_timer;
	struct work_struct unplug_work;
L
Linus Torvalds 已提交
114

115 116 117
	struct cfq_queue *active_queue;
	struct cfq_io_context *active_cic;

118 119 120 121 122
	/*
	 * async queue for each priority case
	 */
	struct cfq_queue *async_cfqq[2][IOPRIO_BE_NR];
	struct cfq_queue *async_idle_cfqq;
123

J
Jens Axboe 已提交
124
	sector_t last_position;
125
	unsigned long last_end_request;
L
Linus Torvalds 已提交
126 127 128 129 130

	/*
	 * tunables, see top of file
	 */
	unsigned int cfq_quantum;
131
	unsigned int cfq_fifo_expire[2];
L
Linus Torvalds 已提交
132 133
	unsigned int cfq_back_penalty;
	unsigned int cfq_back_max;
134 135 136
	unsigned int cfq_slice[2];
	unsigned int cfq_slice_async_rq;
	unsigned int cfq_slice_idle;
137 138

	struct list_head cic_list;
L
Linus Torvalds 已提交
139 140
};

141 142 143
/*
 * Per process-grouping structure
 */
L
Linus Torvalds 已提交
144 145 146
struct cfq_queue {
	/* reference count */
	atomic_t ref;
147 148
	/* various state flags, see below */
	unsigned int flags;
L
Linus Torvalds 已提交
149 150
	/* parent cfq_data */
	struct cfq_data *cfqd;
151 152 153 154
	/* service_tree member */
	struct rb_node rb_node;
	/* service_tree key */
	unsigned long rb_key;
155 156
	/* prio tree member */
	struct rb_node p_node;
L
Linus Torvalds 已提交
157 158 159
	/* sorted list of pending requests */
	struct rb_root sort_list;
	/* if fifo isn't expired, next request to serve */
J
Jens Axboe 已提交
160
	struct request *next_rq;
L
Linus Torvalds 已提交
161 162 163 164 165
	/* requests queued in sort_list */
	int queued[2];
	/* currently allocated requests */
	int allocated[2];
	/* fifo list of requests in sort_list */
166
	struct list_head fifo;
L
Linus Torvalds 已提交
167

168
	unsigned long slice_end;
169
	long slice_resid;
170
	unsigned int slice_dispatch;
L
Linus Torvalds 已提交
171

172 173
	/* pending metadata requests */
	int meta_pending;
J
Jens Axboe 已提交
174 175
	/* number of requests that are on the dispatch list or inside driver */
	int dispatched;
176 177 178 179 180

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

181
	pid_t pid;
L
Linus Torvalds 已提交
182 183
};

J
Jens Axboe 已提交
184
enum cfqq_state_flags {
185 186
	CFQ_CFQQ_FLAG_on_rr = 0,	/* on round-robin busy list */
	CFQ_CFQQ_FLAG_wait_request,	/* waiting for a request */
187
	CFQ_CFQQ_FLAG_must_dispatch,	/* must be allowed a dispatch */
188 189 190 191 192
	CFQ_CFQQ_FLAG_must_alloc,	/* must be allowed rq alloc */
	CFQ_CFQQ_FLAG_must_alloc_slice,	/* per-slice must_alloc flag */
	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 */
193
	CFQ_CFQQ_FLAG_slice_new,	/* no requests dispatched in slice */
194
	CFQ_CFQQ_FLAG_sync,		/* synchronous queue */
195
	CFQ_CFQQ_FLAG_coop,		/* has done a coop jump of the queue */
J
Jens Axboe 已提交
196 197 198 199 200
};

#define CFQ_CFQQ_FNS(name)						\
static inline void cfq_mark_cfqq_##name(struct cfq_queue *cfqq)		\
{									\
201
	(cfqq)->flags |= (1 << CFQ_CFQQ_FLAG_##name);			\
J
Jens Axboe 已提交
202 203 204
}									\
static inline void cfq_clear_cfqq_##name(struct cfq_queue *cfqq)	\
{									\
205
	(cfqq)->flags &= ~(1 << CFQ_CFQQ_FLAG_##name);			\
J
Jens Axboe 已提交
206 207 208
}									\
static inline int cfq_cfqq_##name(const struct cfq_queue *cfqq)		\
{									\
209
	return ((cfqq)->flags & (1 << CFQ_CFQQ_FLAG_##name)) != 0;	\
J
Jens Axboe 已提交
210 211 212 213
}

CFQ_CFQQ_FNS(on_rr);
CFQ_CFQQ_FNS(wait_request);
214
CFQ_CFQQ_FNS(must_dispatch);
J
Jens Axboe 已提交
215 216 217 218 219
CFQ_CFQQ_FNS(must_alloc);
CFQ_CFQQ_FNS(must_alloc_slice);
CFQ_CFQQ_FNS(fifo_expire);
CFQ_CFQQ_FNS(idle_window);
CFQ_CFQQ_FNS(prio_changed);
220
CFQ_CFQQ_FNS(slice_new);
221
CFQ_CFQQ_FNS(sync);
222
CFQ_CFQQ_FNS(coop);
J
Jens Axboe 已提交
223 224
#undef CFQ_CFQQ_FNS

225 226 227 228 229
#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)

230
static void cfq_dispatch_insert(struct request_queue *, struct request *);
231
static struct cfq_queue *cfq_get_queue(struct cfq_data *, int,
232
				       struct io_context *, gfp_t);
233
static struct cfq_io_context *cfq_cic_lookup(struct cfq_data *,
234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258
						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;
}
L
Linus Torvalds 已提交
259

A
Andrew Morton 已提交
260 261 262 263 264 265
/*
 * 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)
{
266 267
	if (cfqd->busy_queues) {
		cfq_log(cfqd, "schedule dispatch");
268
		kblockd_schedule_work(cfqd->queue, &cfqd->unplug_work);
269
	}
A
Andrew Morton 已提交
270 271
}

272
static int cfq_queue_empty(struct request_queue *q)
A
Andrew Morton 已提交
273 274 275
{
	struct cfq_data *cfqd = q->elevator->elevator_data;

276
	return !cfqd->busy_queues;
A
Andrew Morton 已提交
277 278
}

279 280 281 282 283
/*
 * 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.
 */
284 285
static inline int cfq_prio_slice(struct cfq_data *cfqd, int sync,
				 unsigned short prio)
286
{
287
	const int base_slice = cfqd->cfq_slice[sync];
288

289 290 291 292
	WARN_ON(prio >= IOPRIO_BE_NR);

	return base_slice + (base_slice/CFQ_SLICE_SCALE * (4 - prio));
}
293

294 295 296 297
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);
298 299 300 301 302 303
}

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;
304
	cfq_log_cfqq(cfqd, cfqq, "set_slice=%lu", cfqq->slice_end - jiffies);
305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321
}

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

L
Linus Torvalds 已提交
322
/*
J
Jens Axboe 已提交
323
 * Lifted from AS - choose which of rq1 and rq2 that is best served now.
L
Linus Torvalds 已提交
324
 * We choose the request that is closest to the head right now. Distance
325
 * behind the head is penalized and only allowed to a certain extent.
L
Linus Torvalds 已提交
326
 */
J
Jens Axboe 已提交
327 328
static struct request *
cfq_choose_req(struct cfq_data *cfqd, struct request *rq1, struct request *rq2)
L
Linus Torvalds 已提交
329 330 331
{
	sector_t last, s1, s2, d1 = 0, d2 = 0;
	unsigned long back_max;
332 333 334
#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? */
L
Linus Torvalds 已提交
335

J
Jens Axboe 已提交
336 337 338 339
	if (rq1 == NULL || rq1 == rq2)
		return rq2;
	if (rq2 == NULL)
		return rq1;
J
Jens Axboe 已提交
340

J
Jens Axboe 已提交
341 342 343 344
	if (rq_is_sync(rq1) && !rq_is_sync(rq2))
		return rq1;
	else if (rq_is_sync(rq2) && !rq_is_sync(rq1))
		return rq2;
345 346 347 348
	if (rq_is_meta(rq1) && !rq_is_meta(rq2))
		return rq1;
	else if (rq_is_meta(rq2) && !rq_is_meta(rq1))
		return rq2;
L
Linus Torvalds 已提交
349

J
Jens Axboe 已提交
350 351
	s1 = rq1->sector;
	s2 = rq2->sector;
L
Linus Torvalds 已提交
352

J
Jens Axboe 已提交
353
	last = cfqd->last_position;
L
Linus Torvalds 已提交
354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369

	/*
	 * 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
370
		wrap |= CFQ_RQ1_WRAP;
L
Linus Torvalds 已提交
371 372 373 374 375 376

	if (s2 >= last)
		d2 = s2 - last;
	else if (s2 + back_max >= last)
		d2 = (last - s2) * cfqd->cfq_back_penalty;
	else
377
		wrap |= CFQ_RQ2_WRAP;
L
Linus Torvalds 已提交
378 379

	/* Found required data */
380 381 382 383 384 385

	/*
	 * By doing switch() on the bit mask "wrap" we avoid having to
	 * check two variables for all permutations: --> faster!
	 */
	switch (wrap) {
J
Jens Axboe 已提交
386
	case 0: /* common case for CFQ: rq1 and rq2 not wrapped */
387
		if (d1 < d2)
J
Jens Axboe 已提交
388
			return rq1;
389
		else if (d2 < d1)
J
Jens Axboe 已提交
390
			return rq2;
391 392
		else {
			if (s1 >= s2)
J
Jens Axboe 已提交
393
				return rq1;
394
			else
J
Jens Axboe 已提交
395
				return rq2;
396
		}
L
Linus Torvalds 已提交
397

398
	case CFQ_RQ2_WRAP:
J
Jens Axboe 已提交
399
		return rq1;
400
	case CFQ_RQ1_WRAP:
J
Jens Axboe 已提交
401 402
		return rq2;
	case (CFQ_RQ1_WRAP|CFQ_RQ2_WRAP): /* both rqs wrapped */
403 404 405 406 407 408 409 410
	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)
J
Jens Axboe 已提交
411
			return rq1;
L
Linus Torvalds 已提交
412
		else
J
Jens Axboe 已提交
413
			return rq2;
L
Linus Torvalds 已提交
414 415 416
	}
}

417 418 419
/*
 * The below is leftmost cache rbtree addon
 */
420
static struct cfq_queue *cfq_rb_first(struct cfq_rb_root *root)
421 422 423 424
{
	if (!root->left)
		root->left = rb_first(&root->rb);

425 426 427 428
	if (root->left)
		return rb_entry(root->left, struct cfq_queue, rb_node);

	return NULL;
429 430
}

431 432 433 434 435 436
static void rb_erase_init(struct rb_node *n, struct rb_root *root)
{
	rb_erase(n, root);
	RB_CLEAR_NODE(n);
}

437 438 439 440
static void cfq_rb_erase(struct rb_node *n, struct cfq_rb_root *root)
{
	if (root->left == n)
		root->left = NULL;
441
	rb_erase_init(n, &root->rb);
442 443
}

L
Linus Torvalds 已提交
444 445 446
/*
 * would be nice to take fifo expire time into account as well
 */
J
Jens Axboe 已提交
447 448 449
static struct request *
cfq_find_next_rq(struct cfq_data *cfqd, struct cfq_queue *cfqq,
		  struct request *last)
L
Linus Torvalds 已提交
450
{
451 452
	struct rb_node *rbnext = rb_next(&last->rb_node);
	struct rb_node *rbprev = rb_prev(&last->rb_node);
J
Jens Axboe 已提交
453
	struct request *next = NULL, *prev = NULL;
L
Linus Torvalds 已提交
454

455
	BUG_ON(RB_EMPTY_NODE(&last->rb_node));
L
Linus Torvalds 已提交
456 457

	if (rbprev)
J
Jens Axboe 已提交
458
		prev = rb_entry_rq(rbprev);
L
Linus Torvalds 已提交
459

460
	if (rbnext)
J
Jens Axboe 已提交
461
		next = rb_entry_rq(rbnext);
462 463 464
	else {
		rbnext = rb_first(&cfqq->sort_list);
		if (rbnext && rbnext != &last->rb_node)
J
Jens Axboe 已提交
465
			next = rb_entry_rq(rbnext);
466
	}
L
Linus Torvalds 已提交
467

468
	return cfq_choose_req(cfqd, next, prev);
L
Linus Torvalds 已提交
469 470
}

471 472
static unsigned long cfq_slice_offset(struct cfq_data *cfqd,
				      struct cfq_queue *cfqq)
L
Linus Torvalds 已提交
473
{
474 475 476
	/*
	 * just an approximation, should be ok.
	 */
477 478
	return (cfqd->busy_queues - 1) * (cfq_prio_slice(cfqd, 1, 0) -
		       cfq_prio_slice(cfqd, cfq_cfqq_sync(cfqq), cfqq->ioprio));
479 480
}

481 482 483 484 485
/*
 * 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.
 */
486 487
static void cfq_service_tree_add(struct cfq_data *cfqd, struct cfq_queue *cfqq,
				 int add_front)
488
{
489 490
	struct rb_node **p, *parent;
	struct cfq_queue *__cfqq;
491
	unsigned long rb_key;
492
	int left;
493

494 495 496 497 498 499 500 501 502
	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) {
503 504 505 506 507
		rb_key = cfq_slice_offset(cfqd, cfqq) + jiffies;
		rb_key += cfqq->slice_resid;
		cfqq->slice_resid = 0;
	} else
		rb_key = 0;
L
Linus Torvalds 已提交
508

509
	if (!RB_EMPTY_NODE(&cfqq->rb_node)) {
510
		/*
511
		 * same position, nothing more to do
512
		 */
513 514
		if (rb_key == cfqq->rb_key)
			return;
L
Linus Torvalds 已提交
515

516
		cfq_rb_erase(&cfqq->rb_node, &cfqd->service_tree);
L
Linus Torvalds 已提交
517
	}
518

519
	left = 1;
520 521
	parent = NULL;
	p = &cfqd->service_tree.rb.rb_node;
522
	while (*p) {
523
		struct rb_node **n;
524

525 526 527
		parent = *p;
		__cfqq = rb_entry(parent, struct cfq_queue, rb_node);

528 529
		/*
		 * sort RT queues first, we always want to give
530 531
		 * preference to them. IDLE queues goes to the back.
		 * after that, sort on the next service time.
532 533
		 */
		if (cfq_class_rt(cfqq) > cfq_class_rt(__cfqq))
534
			n = &(*p)->rb_left;
535
		else if (cfq_class_rt(cfqq) < cfq_class_rt(__cfqq))
536 537 538 539 540
			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;
541
		else if (rb_key < __cfqq->rb_key)
542 543 544 545 546
			n = &(*p)->rb_left;
		else
			n = &(*p)->rb_right;

		if (n == &(*p)->rb_right)
547
			left = 0;
548 549

		p = n;
550 551
	}

552 553 554
	if (left)
		cfqd->service_tree.left = &cfqq->rb_node;

555 556
	cfqq->rb_key = rb_key;
	rb_link_node(&cfqq->rb_node, parent, p);
557
	rb_insert_color(&cfqq->rb_node, &cfqd->service_tree.rb);
L
Linus Torvalds 已提交
558 559
}

560 561 562 563 564 565 566 567 568 569 570 571 572 573 574 575 576 577 578 579 580 581 582 583 584 585 586 587 588 589 590 591 592 593 594 595 596 597 598 599 600 601 602 603 604 605 606 607 608 609 610 611 612 613 614 615 616
static struct cfq_queue *
cfq_prio_tree_lookup(struct cfq_data *cfqd, int ioprio, sector_t sector,
		     struct rb_node **ret_parent, struct rb_node ***rb_link)
{
	struct rb_root *root = &cfqd->prio_trees[ioprio];
	struct rb_node **p, *parent;
	struct cfq_queue *cfqq = NULL;

	parent = NULL;
	p = &root->rb_node;
	while (*p) {
		struct rb_node **n;

		parent = *p;
		cfqq = rb_entry(parent, struct cfq_queue, p_node);

		/*
		 * Sort strictly based on sector.  Smallest to the left,
		 * largest to the right.
		 */
		if (sector > cfqq->next_rq->sector)
			n = &(*p)->rb_right;
		else if (sector < cfqq->next_rq->sector)
			n = &(*p)->rb_left;
		else
			break;
		p = n;
	}

	*ret_parent = parent;
	if (rb_link)
		*rb_link = p;
	return NULL;
}

static void cfq_prio_tree_add(struct cfq_data *cfqd, struct cfq_queue *cfqq)
{
	struct rb_root *root = &cfqd->prio_trees[cfqq->ioprio];
	struct rb_node **p, *parent;
	struct cfq_queue *__cfqq;

	if (!RB_EMPTY_NODE(&cfqq->p_node))
		rb_erase_init(&cfqq->p_node, root);

	if (cfq_class_idle(cfqq))
		return;
	if (!cfqq->next_rq)
		return;

	__cfqq = cfq_prio_tree_lookup(cfqd, cfqq->ioprio, cfqq->next_rq->sector,
					 &parent, &p);
	BUG_ON(__cfqq);

	rb_link_node(&cfqq->p_node, parent, p);
	rb_insert_color(&cfqq->p_node, root);
}

617 618 619
/*
 * Update cfqq's position in the service tree.
 */
620
static void cfq_resort_rr_list(struct cfq_data *cfqd, struct cfq_queue *cfqq)
J
Jens Axboe 已提交
621 622 623 624
{
	/*
	 * Resorting requires the cfqq to be on the RR list already.
	 */
625
	if (cfq_cfqq_on_rr(cfqq)) {
626
		cfq_service_tree_add(cfqd, cfqq, 0);
627 628
		cfq_prio_tree_add(cfqd, cfqq);
	}
J
Jens Axboe 已提交
629 630
}

L
Linus Torvalds 已提交
631 632
/*
 * add to busy list of queues for service, trying to be fair in ordering
633
 * the pending list according to last request service
L
Linus Torvalds 已提交
634
 */
J
Jens Axboe 已提交
635
static void cfq_add_cfqq_rr(struct cfq_data *cfqd, struct cfq_queue *cfqq)
L
Linus Torvalds 已提交
636
{
637
	cfq_log_cfqq(cfqd, cfqq, "add_to_rr");
J
Jens Axboe 已提交
638 639
	BUG_ON(cfq_cfqq_on_rr(cfqq));
	cfq_mark_cfqq_on_rr(cfqq);
L
Linus Torvalds 已提交
640
	cfqd->busy_queues++;
641 642
	if (cfq_class_rt(cfqq))
		cfqd->busy_rt_queues++;
L
Linus Torvalds 已提交
643

644
	cfq_resort_rr_list(cfqd, cfqq);
L
Linus Torvalds 已提交
645 646
}

647 648 649 650
/*
 * Called when the cfqq no longer has requests pending, remove it from
 * the service tree.
 */
J
Jens Axboe 已提交
651
static void cfq_del_cfqq_rr(struct cfq_data *cfqd, struct cfq_queue *cfqq)
L
Linus Torvalds 已提交
652
{
653
	cfq_log_cfqq(cfqd, cfqq, "del_from_rr");
J
Jens Axboe 已提交
654 655
	BUG_ON(!cfq_cfqq_on_rr(cfqq));
	cfq_clear_cfqq_on_rr(cfqq);
L
Linus Torvalds 已提交
656

657 658
	if (!RB_EMPTY_NODE(&cfqq->rb_node))
		cfq_rb_erase(&cfqq->rb_node, &cfqd->service_tree);
659 660
	if (!RB_EMPTY_NODE(&cfqq->p_node))
		rb_erase_init(&cfqq->p_node, &cfqd->prio_trees[cfqq->ioprio]);
661

L
Linus Torvalds 已提交
662 663
	BUG_ON(!cfqd->busy_queues);
	cfqd->busy_queues--;
664 665
	if (cfq_class_rt(cfqq))
		cfqd->busy_rt_queues--;
L
Linus Torvalds 已提交
666 667 668 669 670
}

/*
 * rb tree support functions
 */
J
Jens Axboe 已提交
671
static void cfq_del_rq_rb(struct request *rq)
L
Linus Torvalds 已提交
672
{
J
Jens Axboe 已提交
673
	struct cfq_queue *cfqq = RQ_CFQQ(rq);
674
	struct cfq_data *cfqd = cfqq->cfqd;
J
Jens Axboe 已提交
675
	const int sync = rq_is_sync(rq);
L
Linus Torvalds 已提交
676

677 678
	BUG_ON(!cfqq->queued[sync]);
	cfqq->queued[sync]--;
L
Linus Torvalds 已提交
679

J
Jens Axboe 已提交
680
	elv_rb_del(&cfqq->sort_list, rq);
L
Linus Torvalds 已提交
681

682
	if (cfq_cfqq_on_rr(cfqq) && RB_EMPTY_ROOT(&cfqq->sort_list))
683
		cfq_del_cfqq_rr(cfqd, cfqq);
L
Linus Torvalds 已提交
684 685
}

J
Jens Axboe 已提交
686
static void cfq_add_rq_rb(struct request *rq)
L
Linus Torvalds 已提交
687
{
J
Jens Axboe 已提交
688
	struct cfq_queue *cfqq = RQ_CFQQ(rq);
L
Linus Torvalds 已提交
689
	struct cfq_data *cfqd = cfqq->cfqd;
690
	struct request *__alias, *prev;
L
Linus Torvalds 已提交
691

692
	cfqq->queued[rq_is_sync(rq)]++;
L
Linus Torvalds 已提交
693 694 695 696 697

	/*
	 * looks a little odd, but the first insert might return an alias.
	 * if that happens, put the alias on the dispatch list
	 */
698
	while ((__alias = elv_rb_add(&cfqq->sort_list, rq)) != NULL)
J
Jens Axboe 已提交
699
		cfq_dispatch_insert(cfqd->queue, __alias);
700 701 702

	if (!cfq_cfqq_on_rr(cfqq))
		cfq_add_cfqq_rr(cfqd, cfqq);
703 704 705 706

	/*
	 * check if this request is a better next-serve candidate
	 */
707
	prev = cfqq->next_rq;
708
	cfqq->next_rq = cfq_choose_req(cfqd, cfqq->next_rq, rq);
709 710 711 712 713 714 715

	/*
	 * adjust priority tree position, if ->next_rq changes
	 */
	if (prev != cfqq->next_rq)
		cfq_prio_tree_add(cfqd, cfqq);

716
	BUG_ON(!cfqq->next_rq);
L
Linus Torvalds 已提交
717 718
}

J
Jens Axboe 已提交
719
static void cfq_reposition_rq_rb(struct cfq_queue *cfqq, struct request *rq)
L
Linus Torvalds 已提交
720
{
721 722
	elv_rb_del(&cfqq->sort_list, rq);
	cfqq->queued[rq_is_sync(rq)]--;
J
Jens Axboe 已提交
723
	cfq_add_rq_rb(rq);
L
Linus Torvalds 已提交
724 725
}

726 727
static struct request *
cfq_find_rq_fmerge(struct cfq_data *cfqd, struct bio *bio)
L
Linus Torvalds 已提交
728
{
729
	struct task_struct *tsk = current;
730
	struct cfq_io_context *cic;
731
	struct cfq_queue *cfqq;
L
Linus Torvalds 已提交
732

733
	cic = cfq_cic_lookup(cfqd, tsk->io_context);
734 735 736 737
	if (!cic)
		return NULL;

	cfqq = cic_to_cfqq(cic, cfq_bio_sync(bio));
738 739 740
	if (cfqq) {
		sector_t sector = bio->bi_sector + bio_sectors(bio);

741
		return elv_rb_find(&cfqq->sort_list, sector);
742
	}
L
Linus Torvalds 已提交
743 744 745 746

	return NULL;
}

747
static void cfq_activate_request(struct request_queue *q, struct request *rq)
L
Linus Torvalds 已提交
748
{
749
	struct cfq_data *cfqd = q->elevator->elevator_data;
J
Jens Axboe 已提交
750

751
	cfqd->rq_in_driver++;
752 753
	cfq_log_cfqq(cfqd, RQ_CFQQ(rq), "activate rq, drv=%d",
						cfqd->rq_in_driver);
754

J
Jens Axboe 已提交
755
	cfqd->last_position = rq->hard_sector + rq->hard_nr_sectors;
L
Linus Torvalds 已提交
756 757
}

758
static void cfq_deactivate_request(struct request_queue *q, struct request *rq)
L
Linus Torvalds 已提交
759
{
760 761 762 763
	struct cfq_data *cfqd = q->elevator->elevator_data;

	WARN_ON(!cfqd->rq_in_driver);
	cfqd->rq_in_driver--;
764 765
	cfq_log_cfqq(cfqd, RQ_CFQQ(rq), "deactivate rq, drv=%d",
						cfqd->rq_in_driver);
L
Linus Torvalds 已提交
766 767
}

768
static void cfq_remove_request(struct request *rq)
L
Linus Torvalds 已提交
769
{
J
Jens Axboe 已提交
770
	struct cfq_queue *cfqq = RQ_CFQQ(rq);
771

J
Jens Axboe 已提交
772 773
	if (cfqq->next_rq == rq)
		cfqq->next_rq = cfq_find_next_rq(cfqq->cfqd, cfqq, rq);
L
Linus Torvalds 已提交
774

775
	list_del_init(&rq->queuelist);
J
Jens Axboe 已提交
776
	cfq_del_rq_rb(rq);
777

778
	cfqq->cfqd->rq_queued--;
779 780 781 782
	if (rq_is_meta(rq)) {
		WARN_ON(!cfqq->meta_pending);
		cfqq->meta_pending--;
	}
L
Linus Torvalds 已提交
783 784
}

785 786
static int cfq_merge(struct request_queue *q, struct request **req,
		     struct bio *bio)
L
Linus Torvalds 已提交
787 788 789 790
{
	struct cfq_data *cfqd = q->elevator->elevator_data;
	struct request *__rq;

791
	__rq = cfq_find_rq_fmerge(cfqd, bio);
792
	if (__rq && elv_rq_merge_ok(__rq, bio)) {
793 794
		*req = __rq;
		return ELEVATOR_FRONT_MERGE;
L
Linus Torvalds 已提交
795 796 797 798 799
	}

	return ELEVATOR_NO_MERGE;
}

800
static void cfq_merged_request(struct request_queue *q, struct request *req,
801
			       int type)
L
Linus Torvalds 已提交
802
{
803
	if (type == ELEVATOR_FRONT_MERGE) {
J
Jens Axboe 已提交
804
		struct cfq_queue *cfqq = RQ_CFQQ(req);
L
Linus Torvalds 已提交
805

J
Jens Axboe 已提交
806
		cfq_reposition_rq_rb(cfqq, req);
L
Linus Torvalds 已提交
807 808 809 810
	}
}

static void
811
cfq_merged_requests(struct request_queue *q, struct request *rq,
L
Linus Torvalds 已提交
812 813
		    struct request *next)
{
814 815 816 817 818 819 820
	/*
	 * 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);

821
	cfq_remove_request(next);
822 823
}

824
static int cfq_allow_merge(struct request_queue *q, struct request *rq,
825 826 827
			   struct bio *bio)
{
	struct cfq_data *cfqd = q->elevator->elevator_data;
828
	struct cfq_io_context *cic;
829 830 831
	struct cfq_queue *cfqq;

	/*
832
	 * Disallow merge of a sync bio into an async request.
833
	 */
834
	if (cfq_bio_sync(bio) && !rq_is_sync(rq))
835 836 837
		return 0;

	/*
838 839
	 * Lookup the cfqq that this bio will be queued with. Allow
	 * merge only if rq is queued there.
840
	 */
841
	cic = cfq_cic_lookup(cfqd, current->io_context);
842 843
	if (!cic)
		return 0;
844

845
	cfqq = cic_to_cfqq(cic, cfq_bio_sync(bio));
846 847
	if (cfqq == RQ_CFQQ(rq))
		return 1;
848

849
	return 0;
850 851
}

J
Jens Axboe 已提交
852 853
static void __cfq_set_active_queue(struct cfq_data *cfqd,
				   struct cfq_queue *cfqq)
854 855
{
	if (cfqq) {
856
		cfq_log_cfqq(cfqd, cfqq, "set_active");
857
		cfqq->slice_end = 0;
858 859 860
		cfqq->slice_dispatch = 0;

		cfq_clear_cfqq_wait_request(cfqq);
861
		cfq_clear_cfqq_must_dispatch(cfqq);
J
Jens Axboe 已提交
862 863
		cfq_clear_cfqq_must_alloc_slice(cfqq);
		cfq_clear_cfqq_fifo_expire(cfqq);
864
		cfq_mark_cfqq_slice_new(cfqq);
865 866

		del_timer(&cfqd->idle_slice_timer);
867 868 869 870 871
	}

	cfqd->active_queue = cfqq;
}

872 873 874 875 876
/*
 * 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,
877
		    int timed_out)
878
{
879 880
	cfq_log_cfqq(cfqd, cfqq, "slice expired t=%d", timed_out);

881 882 883 884 885 886
	if (cfq_cfqq_wait_request(cfqq))
		del_timer(&cfqd->idle_slice_timer);

	cfq_clear_cfqq_wait_request(cfqq);

	/*
887
	 * store what was left of this slice, if the queue idled/timed out
888
	 */
889
	if (timed_out && !cfq_cfqq_slice_new(cfqq)) {
890
		cfqq->slice_resid = cfqq->slice_end - jiffies;
891 892
		cfq_log_cfqq(cfqd, cfqq, "resid=%ld", cfqq->slice_resid);
	}
893

894
	cfq_resort_rr_list(cfqd, cfqq);
895 896 897 898 899 900 901 902 903 904

	if (cfqq == cfqd->active_queue)
		cfqd->active_queue = NULL;

	if (cfqd->active_cic) {
		put_io_context(cfqd->active_cic->ioc);
		cfqd->active_cic = NULL;
	}
}

905
static inline void cfq_slice_expired(struct cfq_data *cfqd, int timed_out)
906 907 908 909
{
	struct cfq_queue *cfqq = cfqd->active_queue;

	if (cfqq)
910
		__cfq_slice_expired(cfqd, cfqq, timed_out);
911 912
}

913 914 915 916
/*
 * Get next queue for service. Unless we have a queue preemption,
 * we'll simply select the first cfqq in the service tree.
 */
J
Jens Axboe 已提交
917
static struct cfq_queue *cfq_get_next_queue(struct cfq_data *cfqd)
918
{
919 920
	if (RB_EMPTY_ROOT(&cfqd->service_tree.rb))
		return NULL;
921

922
	return cfq_rb_first(&cfqd->service_tree);
J
Jens Axboe 已提交
923 924
}

925 926 927
/*
 * Get and set a new active queue for service.
 */
928 929
static struct cfq_queue *cfq_set_active_queue(struct cfq_data *cfqd,
					      struct cfq_queue *cfqq)
J
Jens Axboe 已提交
930
{
931 932 933 934 935
	if (!cfqq) {
		cfqq = cfq_get_next_queue(cfqd);
		if (cfqq)
			cfq_clear_cfqq_coop(cfqq);
	}
J
Jens Axboe 已提交
936

937
	__cfq_set_active_queue(cfqd, cfqq);
J
Jens Axboe 已提交
938
	return cfqq;
939 940
}

941 942 943 944 945 946 947 948 949
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;
}

J
Jens Axboe 已提交
950 951 952 953 954 955 956 957 958 959
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;
}

960 961 962 963 964 965 966 967 968 969 970 971 972 973 974 975 976 977 978 979 980 981 982 983 984 985 986 987 988 989 990 991 992 993 994 995 996 997 998 999 1000 1001 1002 1003 1004 1005 1006 1007 1008 1009 1010 1011 1012 1013 1014
static struct cfq_queue *cfqq_close(struct cfq_data *cfqd,
				    struct cfq_queue *cur_cfqq)
{
	struct rb_root *root = &cfqd->prio_trees[cur_cfqq->ioprio];
	struct rb_node *parent, *node;
	struct cfq_queue *__cfqq;
	sector_t sector = cfqd->last_position;

	if (RB_EMPTY_ROOT(root))
		return NULL;

	/*
	 * First, if we find a request starting at the end of the last
	 * request, choose it.
	 */
	__cfqq = cfq_prio_tree_lookup(cfqd, cur_cfqq->ioprio,
				      sector, &parent, NULL);
	if (__cfqq)
		return __cfqq;

	/*
	 * If the exact sector wasn't found, the parent of the NULL leaf
	 * will contain the closest sector.
	 */
	__cfqq = rb_entry(parent, struct cfq_queue, p_node);
	if (cfq_rq_close(cfqd, __cfqq->next_rq))
		return __cfqq;

	if (__cfqq->next_rq->sector < sector)
		node = rb_next(&__cfqq->p_node);
	else
		node = rb_prev(&__cfqq->p_node);
	if (!node)
		return NULL;

	__cfqq = rb_entry(node, struct cfq_queue, p_node);
	if (cfq_rq_close(cfqd, __cfqq->next_rq))
		return __cfqq;

	return NULL;
}

/*
 * cfqd - obvious
 * cur_cfqq - passed in so that we don't decide that the current queue is
 * 	      closely cooperating with itself.
 *
 * So, basically we're assuming that that cur_cfqq has dispatched at least
 * one request, and that cfqd->last_position reflects a position on the disk
 * associated with the I/O issued by cur_cfqq.  I'm not sure this is a valid
 * assumption.
 */
static struct cfq_queue *cfq_close_cooperator(struct cfq_data *cfqd,
					      struct cfq_queue *cur_cfqq,
					      int probe)
J
Jens Axboe 已提交
1015
{
1016 1017 1018 1019 1020 1021 1022 1023 1024
	struct cfq_queue *cfqq;

	/*
	 * A valid cfq_io_context is necessary to compare requests against
	 * the seek_mean of the current cfqq.
	 */
	if (!cfqd->active_cic)
		return NULL;

J
Jens Axboe 已提交
1025
	/*
1026 1027 1028
	 * 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.
J
Jens Axboe 已提交
1029
	 */
1030 1031 1032 1033 1034 1035 1036 1037 1038 1039
	cfqq = cfqq_close(cfqd, cur_cfqq);
	if (!cfqq)
		return NULL;

	if (cfq_cfqq_coop(cfqq))
		return NULL;

	if (!probe)
		cfq_mark_cfqq_coop(cfqq);
	return cfqq;
J
Jens Axboe 已提交
1040 1041
}

1042

J
Jens Axboe 已提交
1043
#define CIC_SEEKY(cic) ((cic)->seek_mean > (8 * 1024))
1044

J
Jens Axboe 已提交
1045
static void cfq_arm_slice_timer(struct cfq_data *cfqd)
1046
{
1047
	struct cfq_queue *cfqq = cfqd->active_queue;
1048
	struct cfq_io_context *cic;
1049 1050
	unsigned long sl;

1051
	/*
J
Jens Axboe 已提交
1052 1053 1054
	 * 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.
1055
	 */
J
Jens Axboe 已提交
1056
	if (blk_queue_nonrot(cfqd->queue) && cfqd->hw_tag)
1057 1058
		return;

1059
	WARN_ON(!RB_EMPTY_ROOT(&cfqq->sort_list));
J
Jens Axboe 已提交
1060
	WARN_ON(cfq_cfqq_slice_new(cfqq));
1061 1062 1063 1064

	/*
	 * idle is disabled, either manually or by past process history
	 */
J
Jens Axboe 已提交
1065 1066 1067
	if (!cfqd->cfq_slice_idle || !cfq_cfqq_idle_window(cfqq))
		return;

1068 1069 1070 1071 1072 1073
	/*
	 * still requests with the driver, don't idle
	 */
	if (cfqd->rq_in_driver)
		return;

1074 1075 1076
	/*
	 * task has exited, don't wait
	 */
1077
	cic = cfqd->active_cic;
1078
	if (!cic || !atomic_read(&cic->ioc->nr_tasks))
J
Jens Axboe 已提交
1079 1080
		return;

J
Jens Axboe 已提交
1081
	cfq_mark_cfqq_wait_request(cfqq);
1082

1083 1084 1085 1086 1087
	/*
	 * 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
	 */
J
Jens Axboe 已提交
1088
	sl = cfqd->cfq_slice_idle;
1089
	if (sample_valid(cic->seek_samples) && CIC_SEEKY(cic))
1090
		sl = min(sl, msecs_to_jiffies(CFQ_MIN_TT));
1091

1092
	mod_timer(&cfqd->idle_slice_timer, jiffies + sl);
1093
	cfq_log_cfqq(cfqd, cfqq, "arm_idle: %lu", sl);
L
Linus Torvalds 已提交
1094 1095
}

1096 1097 1098
/*
 * Move request from internal lists to the request queue dispatch list.
 */
1099
static void cfq_dispatch_insert(struct request_queue *q, struct request *rq)
L
Linus Torvalds 已提交
1100
{
1101
	struct cfq_data *cfqd = q->elevator->elevator_data;
J
Jens Axboe 已提交
1102
	struct cfq_queue *cfqq = RQ_CFQQ(rq);
1103

1104 1105
	cfq_log_cfqq(cfqd, cfqq, "dispatch_insert");

1106
	cfq_remove_request(rq);
J
Jens Axboe 已提交
1107
	cfqq->dispatched++;
1108
	elv_dispatch_sort(q, rq);
1109 1110 1111

	if (cfq_cfqq_sync(cfqq))
		cfqd->sync_flight++;
L
Linus Torvalds 已提交
1112 1113 1114 1115 1116
}

/*
 * return expired entry, or NULL to just start from scratch in rbtree
 */
J
Jens Axboe 已提交
1117
static struct request *cfq_check_fifo(struct cfq_queue *cfqq)
L
Linus Torvalds 已提交
1118 1119
{
	struct cfq_data *cfqd = cfqq->cfqd;
1120
	struct request *rq;
1121
	int fifo;
L
Linus Torvalds 已提交
1122

J
Jens Axboe 已提交
1123
	if (cfq_cfqq_fifo_expire(cfqq))
L
Linus Torvalds 已提交
1124
		return NULL;
1125 1126 1127

	cfq_mark_cfqq_fifo_expire(cfqq);

1128 1129
	if (list_empty(&cfqq->fifo))
		return NULL;
L
Linus Torvalds 已提交
1130

J
Jens Axboe 已提交
1131
	fifo = cfq_cfqq_sync(cfqq);
1132
	rq = rq_entry_fifo(cfqq->fifo.next);
L
Linus Torvalds 已提交
1133

J
Jens Axboe 已提交
1134
	if (time_before(jiffies, rq->start_time + cfqd->cfq_fifo_expire[fifo]))
1135
		rq = NULL;
L
Linus Torvalds 已提交
1136

1137
	cfq_log_cfqq(cfqd, cfqq, "fifo=%p", rq);
J
Jens Axboe 已提交
1138
	return rq;
L
Linus Torvalds 已提交
1139 1140
}

1141 1142 1143 1144
static inline int
cfq_prio_to_maxrq(struct cfq_data *cfqd, struct cfq_queue *cfqq)
{
	const int base_rq = cfqd->cfq_slice_async_rq;
L
Linus Torvalds 已提交
1145

1146
	WARN_ON(cfqq->ioprio >= IOPRIO_BE_NR);
L
Linus Torvalds 已提交
1147

1148
	return 2 * (base_rq + base_rq * (CFQ_PRIO_LISTS - 1 - cfqq->ioprio));
L
Linus Torvalds 已提交
1149 1150
}

1151
/*
1152 1153
 * 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.
1154
 */
1155
static struct cfq_queue *cfq_select_queue(struct cfq_data *cfqd)
L
Linus Torvalds 已提交
1156
{
1157
	struct cfq_queue *cfqq, *new_cfqq = NULL;
L
Linus Torvalds 已提交
1158

1159 1160 1161
	cfqq = cfqd->active_queue;
	if (!cfqq)
		goto new_queue;
L
Linus Torvalds 已提交
1162

1163
	/*
J
Jens Axboe 已提交
1164
	 * The active queue has run out of time, expire it and select new.
1165
	 */
1166
	if (cfq_slice_used(cfqq) && !cfq_cfqq_must_dispatch(cfqq))
J
Jens Axboe 已提交
1167
		goto expire;
L
Linus Torvalds 已提交
1168

1169 1170 1171 1172 1173 1174 1175 1176 1177 1178 1179 1180 1181 1182
	/*
	 * If we have a RT cfqq waiting, then we pre-empt the current non-rt
	 * cfqq.
	 */
	if (!cfq_class_rt(cfqq) && cfqd->busy_rt_queues) {
		/*
		 * We simulate this as cfqq timed out so that it gets to bank
		 * the remaining of its time slice.
		 */
		cfq_log_cfqq(cfqd, cfqq, "preempt");
		cfq_slice_expired(cfqd, 1);
		goto new_queue;
	}

1183
	/*
J
Jens Axboe 已提交
1184 1185
	 * The active queue has requests and isn't expired, allow it to
	 * dispatch.
1186
	 */
1187
	if (!RB_EMPTY_ROOT(&cfqq->sort_list))
1188
		goto keep_queue;
J
Jens Axboe 已提交
1189

1190 1191 1192 1193 1194 1195 1196 1197 1198 1199
	/*
	 * If another queue has a request waiting within our mean seek
	 * distance, let it run.  The expire code will check for close
	 * cooperators and put the close queue at the front of the service
	 * tree.
	 */
	new_cfqq = cfq_close_cooperator(cfqd, cfqq, 0);
	if (new_cfqq)
		goto expire;

J
Jens Axboe 已提交
1200 1201 1202 1203 1204
	/*
	 * 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.
	 */
1205 1206
	if (timer_pending(&cfqd->idle_slice_timer) ||
	    (cfqq->dispatched && cfq_cfqq_idle_window(cfqq))) {
1207 1208
		cfqq = NULL;
		goto keep_queue;
1209 1210
	}

J
Jens Axboe 已提交
1211
expire:
1212
	cfq_slice_expired(cfqd, 0);
J
Jens Axboe 已提交
1213
new_queue:
1214
	cfqq = cfq_set_active_queue(cfqd, new_cfqq);
1215
keep_queue:
J
Jens Axboe 已提交
1216
	return cfqq;
1217 1218
}

J
Jens Axboe 已提交
1219
static int __cfq_forced_dispatch_cfqq(struct cfq_queue *cfqq)
1220 1221 1222 1223 1224 1225 1226 1227 1228 1229 1230 1231
{
	int dispatched = 0;

	while (cfqq->next_rq) {
		cfq_dispatch_insert(cfqq->cfqd->queue, cfqq->next_rq);
		dispatched++;
	}

	BUG_ON(!list_empty(&cfqq->fifo));
	return dispatched;
}

1232 1233 1234 1235
/*
 * Drain our current requests. Used for barriers and when switching
 * io schedulers on-the-fly.
 */
1236
static int cfq_forced_dispatch(struct cfq_data *cfqd)
1237
{
1238
	struct cfq_queue *cfqq;
1239
	int dispatched = 0;
1240

1241
	while ((cfqq = cfq_rb_first(&cfqd->service_tree)) != NULL)
1242
		dispatched += __cfq_forced_dispatch_cfqq(cfqq);
1243

1244
	cfq_slice_expired(cfqd, 0);
1245 1246 1247

	BUG_ON(cfqd->busy_queues);

1248
	cfq_log(cfqd, "forced_dispatch=%d\n", dispatched);
1249 1250 1251
	return dispatched;
}

1252 1253 1254 1255 1256 1257 1258 1259 1260 1261 1262 1263 1264 1265 1266 1267 1268 1269 1270 1271 1272 1273 1274 1275 1276 1277 1278 1279 1280 1281 1282 1283 1284 1285
/*
 * Dispatch a request from cfqq, moving them to the request queue
 * dispatch list.
 */
static void cfq_dispatch_request(struct cfq_data *cfqd, struct cfq_queue *cfqq)
{
	struct request *rq;

	BUG_ON(RB_EMPTY_ROOT(&cfqq->sort_list));

	/*
	 * follow expired path, else get first next available
	 */
	rq = cfq_check_fifo(cfqq);
	if (!rq)
		rq = cfqq->next_rq;

	/*
	 * insert request into driver dispatch list
	 */
	cfq_dispatch_insert(cfqd->queue, rq);

	if (!cfqd->active_cic) {
		struct cfq_io_context *cic = RQ_CIC(rq);

		atomic_inc(&cic->ioc->refcount);
		cfqd->active_cic = cic;
	}
}

/*
 * Find the cfqq that we need to service and move a request from that to the
 * dispatch list
 */
1286
static int cfq_dispatch_requests(struct request_queue *q, int force)
1287 1288
{
	struct cfq_data *cfqd = q->elevator->elevator_data;
J
Jens Axboe 已提交
1289
	struct cfq_queue *cfqq;
1290
	unsigned int max_dispatch;
1291 1292 1293 1294

	if (!cfqd->busy_queues)
		return 0;

1295 1296 1297
	if (unlikely(force))
		return cfq_forced_dispatch(cfqd);

1298 1299 1300 1301 1302 1303 1304 1305 1306 1307 1308 1309 1310
	cfqq = cfq_select_queue(cfqd);
	if (!cfqq)
		return 0;

	/*
	 * If this is an async queue and we have sync IO in flight, let it wait
	 */
	if (cfqd->sync_flight && !cfq_cfqq_sync(cfqq))
		return 0;

	max_dispatch = cfqd->cfq_quantum;
	if (cfq_class_idle(cfqq))
		max_dispatch = 1;
1311

1312 1313 1314 1315 1316 1317 1318
	/*
	 * Does this cfqq already have too much IO in flight?
	 */
	if (cfqq->dispatched >= max_dispatch) {
		/*
		 * idle queue must always only have a single IO in flight
		 */
1319
		if (cfq_class_idle(cfqq))
1320
			return 0;
1321

1322 1323 1324 1325 1326
		/*
		 * We have other queues, don't allow more IO from this one
		 */
		if (cfqd->busy_queues > 1)
			return 0;
1327

1328 1329 1330 1331 1332 1333
		/*
		 * we are the only queue, allow up to 4 times of 'quantum'
		 */
		if (cfqq->dispatched >= 4 * max_dispatch)
			return 0;
	}
1334

1335 1336 1337 1338 1339
	/*
	 * Dispatch a request from this cfqq
	 */
	cfq_dispatch_request(cfqd, cfqq);
	cfqq->slice_dispatch++;
1340
	cfq_clear_cfqq_must_dispatch(cfqq);
1341

1342 1343 1344 1345 1346 1347 1348 1349 1350
	/*
	 * 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) &&
	    cfqq->slice_dispatch >= cfq_prio_to_maxrq(cfqd, cfqq)) ||
	    cfq_class_idle(cfqq))) {
		cfqq->slice_end = jiffies + 1;
		cfq_slice_expired(cfqd, 0);
L
Linus Torvalds 已提交
1351 1352
	}

1353 1354
	cfq_log(cfqd, "dispatched a request");
	return 1;
L
Linus Torvalds 已提交
1355 1356 1357
}

/*
J
Jens Axboe 已提交
1358 1359
 * task holds one reference to the queue, dropped when task exits. each rq
 * in-flight on this queue also holds a reference, dropped when rq is freed.
L
Linus Torvalds 已提交
1360 1361 1362 1363 1364
 *
 * queue lock must be held here.
 */
static void cfq_put_queue(struct cfq_queue *cfqq)
{
1365 1366 1367
	struct cfq_data *cfqd = cfqq->cfqd;

	BUG_ON(atomic_read(&cfqq->ref) <= 0);
L
Linus Torvalds 已提交
1368 1369 1370 1371

	if (!atomic_dec_and_test(&cfqq->ref))
		return;

1372
	cfq_log_cfqq(cfqd, cfqq, "put_queue");
L
Linus Torvalds 已提交
1373
	BUG_ON(rb_first(&cfqq->sort_list));
1374
	BUG_ON(cfqq->allocated[READ] + cfqq->allocated[WRITE]);
J
Jens Axboe 已提交
1375
	BUG_ON(cfq_cfqq_on_rr(cfqq));
L
Linus Torvalds 已提交
1376

1377
	if (unlikely(cfqd->active_queue == cfqq)) {
1378
		__cfq_slice_expired(cfqd, cfqq, 0);
1379 1380
		cfq_schedule_dispatch(cfqd);
	}
1381

L
Linus Torvalds 已提交
1382 1383 1384
	kmem_cache_free(cfq_pool, cfqq);
}

1385 1386 1387
/*
 * Must always be called with the rcu_read_lock() held
 */
1388 1389 1390 1391 1392 1393 1394 1395 1396 1397 1398
static void
__call_for_each_cic(struct io_context *ioc,
		    void (*func)(struct io_context *, struct cfq_io_context *))
{
	struct cfq_io_context *cic;
	struct hlist_node *n;

	hlist_for_each_entry_rcu(cic, n, &ioc->cic_list, cic_list)
		func(ioc, cic);
}

1399
/*
1400
 * Call func for each cic attached to this ioc.
1401
 */
1402
static void
1403 1404
call_for_each_cic(struct io_context *ioc,
		  void (*func)(struct io_context *, struct cfq_io_context *))
L
Linus Torvalds 已提交
1405
{
1406
	rcu_read_lock();
1407
	__call_for_each_cic(ioc, func);
1408
	rcu_read_unlock();
1409 1410 1411 1412 1413 1414 1415 1416 1417 1418 1419
}

static void cfq_cic_free_rcu(struct rcu_head *head)
{
	struct cfq_io_context *cic;

	cic = container_of(head, struct cfq_io_context, rcu_head);

	kmem_cache_free(cfq_ioc_pool, cic);
	elv_ioc_count_dec(ioc_count);

1420 1421 1422 1423 1424 1425 1426 1427 1428 1429 1430 1431 1432
	if (ioc_gone) {
		/*
		 * CFQ scheduler is exiting, grab exit lock and check
		 * the pending io context count. If it hits zero,
		 * complete ioc_gone and set it back to NULL
		 */
		spin_lock(&ioc_gone_lock);
		if (ioc_gone && !elv_ioc_count_read(ioc_count)) {
			complete(ioc_gone);
			ioc_gone = NULL;
		}
		spin_unlock(&ioc_gone_lock);
	}
1433
}
1434

1435 1436 1437
static void cfq_cic_free(struct cfq_io_context *cic)
{
	call_rcu(&cic->rcu_head, cfq_cic_free_rcu);
1438 1439 1440 1441 1442 1443 1444 1445 1446 1447
}

static void cic_free_func(struct io_context *ioc, struct cfq_io_context *cic)
{
	unsigned long flags;

	BUG_ON(!cic->dead_key);

	spin_lock_irqsave(&ioc->lock, flags);
	radix_tree_delete(&ioc->radix_root, cic->dead_key);
1448
	hlist_del_rcu(&cic->cic_list);
1449 1450
	spin_unlock_irqrestore(&ioc->lock, flags);

1451
	cfq_cic_free(cic);
1452 1453
}

1454 1455 1456 1457 1458
/*
 * Must be called with rcu_read_lock() held or preemption otherwise disabled.
 * Only two callers of this - ->dtor() which is called with the rcu_read_lock(),
 * and ->trim() which is called with the task lock held
 */
1459 1460 1461
static void cfq_free_io_context(struct io_context *ioc)
{
	/*
1462 1463 1464 1465
	 * ioc->refcount is zero here, or we are called from elv_unregister(),
	 * so no more cic's are allowed to be linked into this ioc.  So it
	 * should be ok to iterate over the known list, we will see all cic's
	 * since no new ones are added.
1466
	 */
1467
	__call_for_each_cic(ioc, cic_free_func);
L
Linus Torvalds 已提交
1468 1469
}

1470
static void cfq_exit_cfqq(struct cfq_data *cfqd, struct cfq_queue *cfqq)
L
Linus Torvalds 已提交
1471
{
1472
	if (unlikely(cfqq == cfqd->active_queue)) {
1473
		__cfq_slice_expired(cfqd, cfqq, 0);
1474 1475
		cfq_schedule_dispatch(cfqd);
	}
1476

1477 1478
	cfq_put_queue(cfqq);
}
1479

1480 1481 1482
static void __cfq_exit_single_io_context(struct cfq_data *cfqd,
					 struct cfq_io_context *cic)
{
1483 1484
	struct io_context *ioc = cic->ioc;

1485
	list_del_init(&cic->queue_list);
1486 1487 1488 1489

	/*
	 * Make sure key == NULL is seen for dead queues
	 */
1490
	smp_wmb();
1491
	cic->dead_key = (unsigned long) cic->key;
1492 1493
	cic->key = NULL;

1494 1495 1496
	if (ioc->ioc_data == cic)
		rcu_assign_pointer(ioc->ioc_data, NULL);

1497 1498 1499
	if (cic->cfqq[BLK_RW_ASYNC]) {
		cfq_exit_cfqq(cfqd, cic->cfqq[BLK_RW_ASYNC]);
		cic->cfqq[BLK_RW_ASYNC] = NULL;
1500 1501
	}

1502 1503 1504
	if (cic->cfqq[BLK_RW_SYNC]) {
		cfq_exit_cfqq(cfqd, cic->cfqq[BLK_RW_SYNC]);
		cic->cfqq[BLK_RW_SYNC] = NULL;
1505
	}
1506 1507
}

1508 1509
static void cfq_exit_single_io_context(struct io_context *ioc,
				       struct cfq_io_context *cic)
1510 1511 1512 1513
{
	struct cfq_data *cfqd = cic->key;

	if (cfqd) {
1514
		struct request_queue *q = cfqd->queue;
1515
		unsigned long flags;
1516

1517
		spin_lock_irqsave(q->queue_lock, flags);
1518 1519 1520 1521 1522 1523 1524 1525 1526

		/*
		 * Ensure we get a fresh copy of the ->key to prevent
		 * race between exiting task and queue
		 */
		smp_read_barrier_depends();
		if (cic->key)
			__cfq_exit_single_io_context(cfqd, cic);

1527
		spin_unlock_irqrestore(q->queue_lock, flags);
1528
	}
L
Linus Torvalds 已提交
1529 1530
}

1531 1532 1533 1534
/*
 * The process that ioc belongs to has exited, we need to clean up
 * and put the internal structures we have that belongs to that process.
 */
1535
static void cfq_exit_io_context(struct io_context *ioc)
L
Linus Torvalds 已提交
1536
{
1537
	call_for_each_cic(ioc, cfq_exit_single_io_context);
L
Linus Torvalds 已提交
1538 1539
}

1540
static struct cfq_io_context *
A
Al Viro 已提交
1541
cfq_alloc_io_context(struct cfq_data *cfqd, gfp_t gfp_mask)
L
Linus Torvalds 已提交
1542
{
1543
	struct cfq_io_context *cic;
L
Linus Torvalds 已提交
1544

1545 1546
	cic = kmem_cache_alloc_node(cfq_ioc_pool, gfp_mask | __GFP_ZERO,
							cfqd->queue->node);
L
Linus Torvalds 已提交
1547
	if (cic) {
1548
		cic->last_end_request = jiffies;
1549
		INIT_LIST_HEAD(&cic->queue_list);
1550
		INIT_HLIST_NODE(&cic->cic_list);
1551 1552
		cic->dtor = cfq_free_io_context;
		cic->exit = cfq_exit_io_context;
1553
		elv_ioc_count_inc(ioc_count);
L
Linus Torvalds 已提交
1554 1555 1556 1557 1558
	}

	return cic;
}

1559
static void cfq_init_prio_data(struct cfq_queue *cfqq, struct io_context *ioc)
1560 1561 1562 1563
{
	struct task_struct *tsk = current;
	int ioprio_class;

J
Jens Axboe 已提交
1564
	if (!cfq_cfqq_prio_changed(cfqq))
1565 1566
		return;

1567
	ioprio_class = IOPRIO_PRIO_CLASS(ioc->ioprio);
1568
	switch (ioprio_class) {
1569 1570 1571 1572
	default:
		printk(KERN_ERR "cfq: bad prio %x\n", ioprio_class);
	case IOPRIO_CLASS_NONE:
		/*
1573
		 * no prio set, inherit CPU scheduling settings
1574 1575
		 */
		cfqq->ioprio = task_nice_ioprio(tsk);
1576
		cfqq->ioprio_class = task_nice_ioclass(tsk);
1577 1578 1579 1580 1581 1582 1583 1584 1585 1586 1587 1588 1589 1590
		break;
	case IOPRIO_CLASS_RT:
		cfqq->ioprio = task_ioprio(ioc);
		cfqq->ioprio_class = IOPRIO_CLASS_RT;
		break;
	case IOPRIO_CLASS_BE:
		cfqq->ioprio = task_ioprio(ioc);
		cfqq->ioprio_class = IOPRIO_CLASS_BE;
		break;
	case IOPRIO_CLASS_IDLE:
		cfqq->ioprio_class = IOPRIO_CLASS_IDLE;
		cfqq->ioprio = 7;
		cfq_clear_cfqq_idle_window(cfqq);
		break;
1591 1592 1593 1594 1595 1596 1597 1598
	}

	/*
	 * keep track of original prio settings in case we have to temporarily
	 * elevate the priority of this queue
	 */
	cfqq->org_ioprio = cfqq->ioprio;
	cfqq->org_ioprio_class = cfqq->ioprio_class;
J
Jens Axboe 已提交
1599
	cfq_clear_cfqq_prio_changed(cfqq);
1600 1601
}

J
Jens Axboe 已提交
1602
static void changed_ioprio(struct io_context *ioc, struct cfq_io_context *cic)
1603
{
1604 1605
	struct cfq_data *cfqd = cic->key;
	struct cfq_queue *cfqq;
1606
	unsigned long flags;
1607

1608 1609 1610
	if (unlikely(!cfqd))
		return;

1611
	spin_lock_irqsave(cfqd->queue->queue_lock, flags);
1612

1613
	cfqq = cic->cfqq[BLK_RW_ASYNC];
1614 1615
	if (cfqq) {
		struct cfq_queue *new_cfqq;
1616 1617
		new_cfqq = cfq_get_queue(cfqd, BLK_RW_ASYNC, cic->ioc,
						GFP_ATOMIC);
1618
		if (new_cfqq) {
1619
			cic->cfqq[BLK_RW_ASYNC] = new_cfqq;
1620 1621
			cfq_put_queue(cfqq);
		}
1622
	}
1623

1624
	cfqq = cic->cfqq[BLK_RW_SYNC];
1625 1626 1627
	if (cfqq)
		cfq_mark_cfqq_prio_changed(cfqq);

1628
	spin_unlock_irqrestore(cfqd->queue->queue_lock, flags);
1629 1630
}

1631
static void cfq_ioc_set_ioprio(struct io_context *ioc)
1632
{
1633
	call_for_each_cic(ioc, changed_ioprio);
1634
	ioc->ioprio_changed = 0;
1635 1636 1637
}

static struct cfq_queue *
1638
cfq_find_alloc_queue(struct cfq_data *cfqd, int is_sync,
1639
		     struct io_context *ioc, gfp_t gfp_mask)
1640 1641
{
	struct cfq_queue *cfqq, *new_cfqq = NULL;
1642
	struct cfq_io_context *cic;
1643 1644

retry:
1645
	cic = cfq_cic_lookup(cfqd, ioc);
1646 1647
	/* cic always exists here */
	cfqq = cic_to_cfqq(cic, is_sync);
1648 1649 1650 1651 1652 1653

	if (!cfqq) {
		if (new_cfqq) {
			cfqq = new_cfqq;
			new_cfqq = NULL;
		} else if (gfp_mask & __GFP_WAIT) {
1654 1655 1656 1657 1658 1659
			/*
			 * Inform the allocator of the fact that we will
			 * just repeat this allocation if it fails, to allow
			 * the allocator to do whatever it needs to attempt to
			 * free memory.
			 */
1660
			spin_unlock_irq(cfqd->queue->queue_lock);
1661 1662 1663
			new_cfqq = kmem_cache_alloc_node(cfq_pool,
					gfp_mask | __GFP_NOFAIL | __GFP_ZERO,
					cfqd->queue->node);
1664 1665 1666
			spin_lock_irq(cfqd->queue->queue_lock);
			goto retry;
		} else {
1667 1668 1669
			cfqq = kmem_cache_alloc_node(cfq_pool,
					gfp_mask | __GFP_ZERO,
					cfqd->queue->node);
1670 1671 1672 1673
			if (!cfqq)
				goto out;
		}

1674
		RB_CLEAR_NODE(&cfqq->rb_node);
1675
		RB_CLEAR_NODE(&cfqq->p_node);
1676 1677 1678 1679
		INIT_LIST_HEAD(&cfqq->fifo);

		atomic_set(&cfqq->ref, 0);
		cfqq->cfqd = cfqd;
1680

J
Jens Axboe 已提交
1681
		cfq_mark_cfqq_prio_changed(cfqq);
1682

1683
		cfq_init_prio_data(cfqq, ioc);
1684 1685 1686 1687 1688 1689

		if (is_sync) {
			if (!cfq_class_idle(cfqq))
				cfq_mark_cfqq_idle_window(cfqq);
			cfq_mark_cfqq_sync(cfqq);
		}
1690 1691
		cfqq->pid = current->pid;
		cfq_log_cfqq(cfqd, cfqq, "alloced");
1692 1693 1694 1695 1696 1697 1698 1699 1700 1701
	}

	if (new_cfqq)
		kmem_cache_free(cfq_pool, new_cfqq);

out:
	WARN_ON((gfp_mask & __GFP_WAIT) && !cfqq);
	return cfqq;
}

1702 1703 1704
static struct cfq_queue **
cfq_async_queue_prio(struct cfq_data *cfqd, int ioprio_class, int ioprio)
{
1705
	switch (ioprio_class) {
1706 1707 1708 1709 1710 1711 1712 1713 1714 1715 1716
	case IOPRIO_CLASS_RT:
		return &cfqd->async_cfqq[0][ioprio];
	case IOPRIO_CLASS_BE:
		return &cfqd->async_cfqq[1][ioprio];
	case IOPRIO_CLASS_IDLE:
		return &cfqd->async_idle_cfqq;
	default:
		BUG();
	}
}

1717
static struct cfq_queue *
1718
cfq_get_queue(struct cfq_data *cfqd, int is_sync, struct io_context *ioc,
1719 1720
	      gfp_t gfp_mask)
{
1721 1722
	const int ioprio = task_ioprio(ioc);
	const int ioprio_class = task_ioprio_class(ioc);
1723
	struct cfq_queue **async_cfqq = NULL;
1724 1725
	struct cfq_queue *cfqq = NULL;

1726 1727 1728 1729 1730
	if (!is_sync) {
		async_cfqq = cfq_async_queue_prio(cfqd, ioprio_class, ioprio);
		cfqq = *async_cfqq;
	}

1731
	if (!cfqq) {
1732
		cfqq = cfq_find_alloc_queue(cfqd, is_sync, ioc, gfp_mask);
1733 1734 1735
		if (!cfqq)
			return NULL;
	}
1736 1737 1738 1739

	/*
	 * pin the queue now that it's allocated, scheduler exit will prune it
	 */
1740
	if (!is_sync && !(*async_cfqq)) {
1741
		atomic_inc(&cfqq->ref);
1742
		*async_cfqq = cfqq;
1743 1744 1745 1746 1747 1748
	}

	atomic_inc(&cfqq->ref);
	return cfqq;
}

1749 1750 1751
/*
 * We drop cfq io contexts lazily, so we may find a dead one.
 */
1752
static void
1753 1754
cfq_drop_dead_cic(struct cfq_data *cfqd, struct io_context *ioc,
		  struct cfq_io_context *cic)
1755
{
1756 1757
	unsigned long flags;

1758
	WARN_ON(!list_empty(&cic->queue_list));
J
Jens Axboe 已提交
1759

1760 1761
	spin_lock_irqsave(&ioc->lock, flags);

1762
	BUG_ON(ioc->ioc_data == cic);
J
Jens Axboe 已提交
1763

1764
	radix_tree_delete(&ioc->radix_root, (unsigned long) cfqd);
1765
	hlist_del_rcu(&cic->cic_list);
1766 1767 1768
	spin_unlock_irqrestore(&ioc->lock, flags);

	cfq_cic_free(cic);
1769 1770
}

1771
static struct cfq_io_context *
1772
cfq_cic_lookup(struct cfq_data *cfqd, struct io_context *ioc)
1773 1774
{
	struct cfq_io_context *cic;
1775
	unsigned long flags;
1776
	void *k;
1777

1778 1779 1780
	if (unlikely(!ioc))
		return NULL;

1781 1782
	rcu_read_lock();

J
Jens Axboe 已提交
1783 1784 1785
	/*
	 * we maintain a last-hit cache, to avoid browsing over the tree
	 */
1786
	cic = rcu_dereference(ioc->ioc_data);
1787 1788
	if (cic && cic->key == cfqd) {
		rcu_read_unlock();
J
Jens Axboe 已提交
1789
		return cic;
1790
	}
J
Jens Axboe 已提交
1791

1792 1793 1794 1795 1796
	do {
		cic = radix_tree_lookup(&ioc->radix_root, (unsigned long) cfqd);
		rcu_read_unlock();
		if (!cic)
			break;
1797 1798 1799
		/* ->key must be copied to avoid race with cfq_exit_queue() */
		k = cic->key;
		if (unlikely(!k)) {
1800
			cfq_drop_dead_cic(cfqd, ioc, cic);
1801
			rcu_read_lock();
1802
			continue;
1803
		}
1804

1805
		spin_lock_irqsave(&ioc->lock, flags);
1806
		rcu_assign_pointer(ioc->ioc_data, cic);
1807
		spin_unlock_irqrestore(&ioc->lock, flags);
1808 1809
		break;
	} while (1);
1810

1811
	return cic;
1812 1813
}

1814 1815 1816 1817 1818
/*
 * Add cic into ioc, using cfqd as the search key. This enables us to lookup
 * the process specific cfq io context when entered from the block layer.
 * Also adds the cic to a per-cfqd list, used when this queue is removed.
 */
J
Jens Axboe 已提交
1819 1820
static int cfq_cic_link(struct cfq_data *cfqd, struct io_context *ioc,
			struct cfq_io_context *cic, gfp_t gfp_mask)
1821
{
1822
	unsigned long flags;
1823
	int ret;
1824

1825 1826 1827 1828
	ret = radix_tree_preload(gfp_mask);
	if (!ret) {
		cic->ioc = ioc;
		cic->key = cfqd;
1829

1830 1831 1832
		spin_lock_irqsave(&ioc->lock, flags);
		ret = radix_tree_insert(&ioc->radix_root,
						(unsigned long) cfqd, cic);
1833 1834
		if (!ret)
			hlist_add_head_rcu(&cic->cic_list, &ioc->cic_list);
1835
		spin_unlock_irqrestore(&ioc->lock, flags);
1836

1837 1838 1839 1840 1841 1842 1843
		radix_tree_preload_end();

		if (!ret) {
			spin_lock_irqsave(cfqd->queue->queue_lock, flags);
			list_add(&cic->queue_list, &cfqd->cic_list);
			spin_unlock_irqrestore(cfqd->queue->queue_lock, flags);
		}
1844 1845
	}

1846 1847
	if (ret)
		printk(KERN_ERR "cfq: cic link failed!\n");
1848

1849
	return ret;
1850 1851
}

L
Linus Torvalds 已提交
1852 1853 1854
/*
 * Setup general io context and cfq io context. There can be several cfq
 * io contexts per general io context, if this process is doing io to more
1855
 * than one device managed by cfq.
L
Linus Torvalds 已提交
1856 1857
 */
static struct cfq_io_context *
1858
cfq_get_io_context(struct cfq_data *cfqd, gfp_t gfp_mask)
L
Linus Torvalds 已提交
1859
{
1860
	struct io_context *ioc = NULL;
L
Linus Torvalds 已提交
1861 1862
	struct cfq_io_context *cic;

1863
	might_sleep_if(gfp_mask & __GFP_WAIT);
L
Linus Torvalds 已提交
1864

1865
	ioc = get_io_context(gfp_mask, cfqd->queue->node);
L
Linus Torvalds 已提交
1866 1867 1868
	if (!ioc)
		return NULL;

1869
	cic = cfq_cic_lookup(cfqd, ioc);
1870 1871
	if (cic)
		goto out;
L
Linus Torvalds 已提交
1872

1873 1874 1875
	cic = cfq_alloc_io_context(cfqd, gfp_mask);
	if (cic == NULL)
		goto err;
L
Linus Torvalds 已提交
1876

1877 1878 1879
	if (cfq_cic_link(cfqd, ioc, cic, gfp_mask))
		goto err_free;

L
Linus Torvalds 已提交
1880
out:
1881 1882 1883 1884
	smp_read_barrier_depends();
	if (unlikely(ioc->ioprio_changed))
		cfq_ioc_set_ioprio(ioc);

L
Linus Torvalds 已提交
1885
	return cic;
1886 1887
err_free:
	cfq_cic_free(cic);
L
Linus Torvalds 已提交
1888 1889 1890 1891 1892
err:
	put_io_context(ioc);
	return NULL;
}

1893 1894
static void
cfq_update_io_thinktime(struct cfq_data *cfqd, struct cfq_io_context *cic)
L
Linus Torvalds 已提交
1895
{
1896 1897
	unsigned long elapsed = jiffies - cic->last_end_request;
	unsigned long ttime = min(elapsed, 2UL * cfqd->cfq_slice_idle);
1898

1899 1900 1901 1902
	cic->ttime_samples = (7*cic->ttime_samples + 256) / 8;
	cic->ttime_total = (7*cic->ttime_total + 256*ttime) / 8;
	cic->ttime_mean = (cic->ttime_total + 128) / cic->ttime_samples;
}
L
Linus Torvalds 已提交
1903

1904
static void
J
Jens Axboe 已提交
1905 1906
cfq_update_io_seektime(struct cfq_data *cfqd, struct cfq_io_context *cic,
		       struct request *rq)
1907 1908 1909 1910
{
	sector_t sdist;
	u64 total;

J
Jens Axboe 已提交
1911 1912
	if (cic->last_request_pos < rq->sector)
		sdist = rq->sector - cic->last_request_pos;
1913
	else
J
Jens Axboe 已提交
1914
		sdist = cic->last_request_pos - rq->sector;
1915 1916 1917 1918 1919 1920 1921 1922 1923 1924 1925 1926 1927 1928 1929 1930

	/*
	 * Don't allow the seek distance to get too large from the
	 * odd fragment, pagein, etc
	 */
	if (cic->seek_samples <= 60) /* second&third seek */
		sdist = min(sdist, (cic->seek_mean * 4) + 2*1024*1024);
	else
		sdist = min(sdist, (cic->seek_mean * 4)	+ 2*1024*64);

	cic->seek_samples = (7*cic->seek_samples + 256) / 8;
	cic->seek_total = (7*cic->seek_total + (u64)256*sdist) / 8;
	total = cic->seek_total + (cic->seek_samples/2);
	do_div(total, cic->seek_samples);
	cic->seek_mean = (sector_t)total;
}
L
Linus Torvalds 已提交
1931

1932 1933 1934 1935 1936 1937 1938 1939
/*
 * Disable idle window if the process thinks too long or seeks so much that
 * it doesn't matter
 */
static void
cfq_update_idle_window(struct cfq_data *cfqd, struct cfq_queue *cfqq,
		       struct cfq_io_context *cic)
{
1940
	int old_idle, enable_idle;
1941

1942 1943 1944 1945
	/*
	 * Don't idle for async or idle io prio class
	 */
	if (!cfq_cfqq_sync(cfqq) || cfq_class_idle(cfqq))
1946 1947
		return;

1948
	enable_idle = old_idle = cfq_cfqq_idle_window(cfqq);
L
Linus Torvalds 已提交
1949

1950
	if (!atomic_read(&cic->ioc->nr_tasks) || !cfqd->cfq_slice_idle ||
1951
	    (cfqd->hw_tag && CIC_SEEKY(cic)))
1952 1953 1954 1955 1956 1957
		enable_idle = 0;
	else if (sample_valid(cic->ttime_samples)) {
		if (cic->ttime_mean > cfqd->cfq_slice_idle)
			enable_idle = 0;
		else
			enable_idle = 1;
L
Linus Torvalds 已提交
1958 1959
	}

1960 1961 1962 1963 1964 1965 1966
	if (old_idle != enable_idle) {
		cfq_log_cfqq(cfqd, cfqq, "idle=%d", enable_idle);
		if (enable_idle)
			cfq_mark_cfqq_idle_window(cfqq);
		else
			cfq_clear_cfqq_idle_window(cfqq);
	}
1967
}
L
Linus Torvalds 已提交
1968

1969 1970 1971 1972 1973 1974
/*
 * Check if new_cfqq should preempt the currently active queue. Return 0 for
 * no or if we aren't sure, a 1 will cause a preempt.
 */
static int
cfq_should_preempt(struct cfq_data *cfqd, struct cfq_queue *new_cfqq,
J
Jens Axboe 已提交
1975
		   struct request *rq)
1976
{
J
Jens Axboe 已提交
1977
	struct cfq_queue *cfqq;
1978

J
Jens Axboe 已提交
1979 1980
	cfqq = cfqd->active_queue;
	if (!cfqq)
1981 1982
		return 0;

J
Jens Axboe 已提交
1983 1984 1985 1986
	if (cfq_slice_used(cfqq))
		return 1;

	if (cfq_class_idle(new_cfqq))
1987
		return 0;
1988 1989 1990

	if (cfq_class_idle(cfqq))
		return 1;
1991

1992 1993 1994 1995
	/*
	 * if the new request is sync, but the currently running queue is
	 * not, let the sync request have priority.
	 */
J
Jens Axboe 已提交
1996
	if (rq_is_sync(rq) && !cfq_cfqq_sync(cfqq))
1997
		return 1;
1998

1999 2000 2001 2002 2003 2004
	/*
	 * So both queues are sync. Let the new request get disk time if
	 * it's a metadata request and the current queue is doing regular IO.
	 */
	if (rq_is_meta(rq) && !cfqq->meta_pending)
		return 1;
2005

2006 2007 2008 2009 2010 2011
	/*
	 * Allow an RT request to pre-empt an ongoing non-RT cfqq timeslice.
	 */
	if (cfq_class_rt(new_cfqq) && !cfq_class_rt(cfqq))
		return 1;

2012 2013 2014 2015 2016 2017 2018
	if (!cfqd->active_cic || !cfq_cfqq_wait_request(cfqq))
		return 0;

	/*
	 * if this request is as-good as one we would expect from the
	 * current cfqq, let it preempt
	 */
J
Jens Axboe 已提交
2019
	if (cfq_rq_close(cfqd, rq))
2020 2021
		return 1;

2022 2023 2024 2025 2026 2027 2028 2029 2030
	return 0;
}

/*
 * cfqq preempts the active queue. if we allowed preempt with no slice left,
 * let it have half of its nominal slice.
 */
static void cfq_preempt_queue(struct cfq_data *cfqd, struct cfq_queue *cfqq)
{
2031
	cfq_log_cfqq(cfqd, cfqq, "preempt");
2032
	cfq_slice_expired(cfqd, 1);
2033

2034 2035 2036 2037 2038
	/*
	 * Put the new queue at the front of the of the current list,
	 * so we know that it will be selected next.
	 */
	BUG_ON(!cfq_cfqq_on_rr(cfqq));
2039 2040

	cfq_service_tree_add(cfqd, cfqq, 1);
2041

2042 2043
	cfqq->slice_end = 0;
	cfq_mark_cfqq_slice_new(cfqq);
2044 2045 2046
}

/*
J
Jens Axboe 已提交
2047
 * Called when a new fs request (rq) is added (to cfqq). Check if there's
2048 2049 2050
 * something we should do about it
 */
static void
J
Jens Axboe 已提交
2051 2052
cfq_rq_enqueued(struct cfq_data *cfqd, struct cfq_queue *cfqq,
		struct request *rq)
2053
{
J
Jens Axboe 已提交
2054
	struct cfq_io_context *cic = RQ_CIC(rq);
2055

2056
	cfqd->rq_queued++;
2057 2058 2059
	if (rq_is_meta(rq))
		cfqq->meta_pending++;

J
Jens Axboe 已提交
2060
	cfq_update_io_thinktime(cfqd, cic);
J
Jens Axboe 已提交
2061
	cfq_update_io_seektime(cfqd, cic, rq);
J
Jens Axboe 已提交
2062 2063
	cfq_update_idle_window(cfqd, cfqq, cic);

J
Jens Axboe 已提交
2064
	cic->last_request_pos = rq->sector + rq->nr_sectors;
2065 2066 2067

	if (cfqq == cfqd->active_queue) {
		/*
2068 2069 2070
		 * Remember that we saw a request from this process, but
		 * don't start queuing just yet. Otherwise we risk seeing lots
		 * of tiny requests, because we disrupt the normal plugging
2071 2072
		 * and merging. If the request is already larger than a single
		 * page, let it rip immediately. For that case we assume that
2073 2074 2075
		 * merging is already done. Ditto for a busy system that
		 * has other work pending, don't risk delaying until the
		 * idle timer unplug to continue working.
2076
		 */
2077
		if (cfq_cfqq_wait_request(cfqq)) {
2078 2079
			if (blk_rq_bytes(rq) > PAGE_CACHE_SIZE ||
			    cfqd->busy_queues > 1) {
2080 2081 2082
				del_timer(&cfqd->idle_slice_timer);
				blk_start_queueing(cfqd->queue);
			}
2083
			cfq_mark_cfqq_must_dispatch(cfqq);
2084
		}
J
Jens Axboe 已提交
2085
	} else if (cfq_should_preempt(cfqd, cfqq, rq)) {
2086 2087 2088
		/*
		 * not the active queue - expire current slice if it is
		 * idle and has expired it's mean thinktime or this new queue
2089 2090
		 * has some old slice time left and is of higher priority or
		 * this new queue is RT and the current one is BE
2091 2092
		 */
		cfq_preempt_queue(cfqd, cfqq);
2093
		blk_start_queueing(cfqd->queue);
2094
	}
L
Linus Torvalds 已提交
2095 2096
}

2097
static void cfq_insert_request(struct request_queue *q, struct request *rq)
L
Linus Torvalds 已提交
2098
{
2099
	struct cfq_data *cfqd = q->elevator->elevator_data;
J
Jens Axboe 已提交
2100
	struct cfq_queue *cfqq = RQ_CFQQ(rq);
2101

2102
	cfq_log_cfqq(cfqd, cfqq, "insert_request");
2103
	cfq_init_prio_data(cfqq, RQ_CIC(rq)->ioc);
L
Linus Torvalds 已提交
2104

J
Jens Axboe 已提交
2105
	cfq_add_rq_rb(rq);
L
Linus Torvalds 已提交
2106

2107 2108
	list_add_tail(&rq->queuelist, &cfqq->fifo);

J
Jens Axboe 已提交
2109
	cfq_rq_enqueued(cfqd, cfqq, rq);
L
Linus Torvalds 已提交
2110 2111
}

2112 2113 2114 2115 2116 2117 2118 2119 2120 2121 2122 2123 2124 2125 2126 2127 2128 2129 2130 2131 2132 2133 2134 2135 2136
/*
 * Update hw_tag based on peak queue depth over 50 samples under
 * sufficient load.
 */
static void cfq_update_hw_tag(struct cfq_data *cfqd)
{
	if (cfqd->rq_in_driver > cfqd->rq_in_driver_peak)
		cfqd->rq_in_driver_peak = cfqd->rq_in_driver;

	if (cfqd->rq_queued <= CFQ_HW_QUEUE_MIN &&
	    cfqd->rq_in_driver <= CFQ_HW_QUEUE_MIN)
		return;

	if (cfqd->hw_tag_samples++ < 50)
		return;

	if (cfqd->rq_in_driver_peak >= CFQ_HW_QUEUE_MIN)
		cfqd->hw_tag = 1;
	else
		cfqd->hw_tag = 0;

	cfqd->hw_tag_samples = 0;
	cfqd->rq_in_driver_peak = 0;
}

2137
static void cfq_completed_request(struct request_queue *q, struct request *rq)
L
Linus Torvalds 已提交
2138
{
J
Jens Axboe 已提交
2139
	struct cfq_queue *cfqq = RQ_CFQQ(rq);
2140
	struct cfq_data *cfqd = cfqq->cfqd;
2141
	const int sync = rq_is_sync(rq);
2142
	unsigned long now;
L
Linus Torvalds 已提交
2143

2144
	now = jiffies;
2145
	cfq_log_cfqq(cfqd, cfqq, "complete");
L
Linus Torvalds 已提交
2146

2147 2148
	cfq_update_hw_tag(cfqd);

2149
	WARN_ON(!cfqd->rq_in_driver);
J
Jens Axboe 已提交
2150
	WARN_ON(!cfqq->dispatched);
2151
	cfqd->rq_in_driver--;
J
Jens Axboe 已提交
2152
	cfqq->dispatched--;
L
Linus Torvalds 已提交
2153

2154 2155 2156
	if (cfq_cfqq_sync(cfqq))
		cfqd->sync_flight--;

2157 2158
	if (!cfq_class_idle(cfqq))
		cfqd->last_end_request = now;
J
Jens Axboe 已提交
2159

2160
	if (sync)
J
Jens Axboe 已提交
2161
		RQ_CIC(rq)->last_end_request = now;
2162 2163 2164 2165 2166 2167

	/*
	 * If this is the active queue, check if it needs to be expired,
	 * or if we want to idle in case it has no pending requests.
	 */
	if (cfqd->active_queue == cfqq) {
2168 2169
		const bool cfqq_empty = RB_EMPTY_ROOT(&cfqq->sort_list);

2170 2171 2172 2173
		if (cfq_cfqq_slice_new(cfqq)) {
			cfq_set_prio_slice(cfqd, cfqq);
			cfq_clear_cfqq_slice_new(cfqq);
		}
2174 2175 2176 2177 2178 2179 2180
		/*
		 * If there are no requests waiting in this queue, and
		 * there are other queues ready to issue requests, AND
		 * those other queues are issuing requests within our
		 * mean seek distance, give them a chance to run instead
		 * of idling.
		 */
2181
		if (cfq_slice_used(cfqq) || cfq_class_idle(cfqq))
2182
			cfq_slice_expired(cfqd, 1);
2183 2184
		else if (cfqq_empty && !cfq_close_cooperator(cfqd, cfqq, 1) &&
			 sync && !rq_noidle(rq))
J
Jens Axboe 已提交
2185
			cfq_arm_slice_timer(cfqd);
2186
	}
J
Jens Axboe 已提交
2187 2188 2189

	if (!cfqd->rq_in_driver)
		cfq_schedule_dispatch(cfqd);
L
Linus Torvalds 已提交
2190 2191
}

2192 2193 2194 2195 2196
/*
 * we temporarily boost lower priority queues if they are holding fs exclusive
 * resources. they are boosted to normal prio (CLASS_BE/4)
 */
static void cfq_prio_boost(struct cfq_queue *cfqq)
L
Linus Torvalds 已提交
2197
{
2198 2199 2200 2201 2202 2203 2204 2205 2206 2207 2208 2209 2210 2211 2212 2213 2214 2215 2216
	if (has_fs_excl()) {
		/*
		 * boost idle prio on transactions that would lock out other
		 * users of the filesystem
		 */
		if (cfq_class_idle(cfqq))
			cfqq->ioprio_class = IOPRIO_CLASS_BE;
		if (cfqq->ioprio > IOPRIO_NORM)
			cfqq->ioprio = IOPRIO_NORM;
	} else {
		/*
		 * check if we need to unboost the queue
		 */
		if (cfqq->ioprio_class != cfqq->org_ioprio_class)
			cfqq->ioprio_class = cfqq->org_ioprio_class;
		if (cfqq->ioprio != cfqq->org_ioprio)
			cfqq->ioprio = cfqq->org_ioprio;
	}
}
L
Linus Torvalds 已提交
2217

2218
static inline int __cfq_may_queue(struct cfq_queue *cfqq)
2219
{
J
Jens Axboe 已提交
2220
	if ((cfq_cfqq_wait_request(cfqq) || cfq_cfqq_must_alloc(cfqq)) &&
A
Andrew Morton 已提交
2221
	    !cfq_cfqq_must_alloc_slice(cfqq)) {
J
Jens Axboe 已提交
2222
		cfq_mark_cfqq_must_alloc_slice(cfqq);
2223
		return ELV_MQUEUE_MUST;
J
Jens Axboe 已提交
2224
	}
L
Linus Torvalds 已提交
2225

2226 2227 2228
	return ELV_MQUEUE_MAY;
}

2229
static int cfq_may_queue(struct request_queue *q, int rw)
2230 2231 2232
{
	struct cfq_data *cfqd = q->elevator->elevator_data;
	struct task_struct *tsk = current;
2233
	struct cfq_io_context *cic;
2234 2235 2236 2237 2238 2239 2240 2241
	struct cfq_queue *cfqq;

	/*
	 * don't force setup of a queue from here, as a call to may_queue
	 * does not necessarily imply that a request actually will be queued.
	 * so just lookup a possibly existing queue, or return 'may queue'
	 * if that fails
	 */
2242
	cic = cfq_cic_lookup(cfqd, tsk->io_context);
2243 2244 2245
	if (!cic)
		return ELV_MQUEUE_MAY;

2246
	cfqq = cic_to_cfqq(cic, rw_is_sync(rw));
2247
	if (cfqq) {
2248
		cfq_init_prio_data(cfqq, cic->ioc);
2249 2250
		cfq_prio_boost(cfqq);

2251
		return __cfq_may_queue(cfqq);
2252 2253 2254
	}

	return ELV_MQUEUE_MAY;
L
Linus Torvalds 已提交
2255 2256 2257 2258 2259
}

/*
 * queue lock held here
 */
2260
static void cfq_put_request(struct request *rq)
L
Linus Torvalds 已提交
2261
{
J
Jens Axboe 已提交
2262
	struct cfq_queue *cfqq = RQ_CFQQ(rq);
L
Linus Torvalds 已提交
2263

J
Jens Axboe 已提交
2264
	if (cfqq) {
2265
		const int rw = rq_data_dir(rq);
L
Linus Torvalds 已提交
2266

2267 2268
		BUG_ON(!cfqq->allocated[rw]);
		cfqq->allocated[rw]--;
L
Linus Torvalds 已提交
2269

J
Jens Axboe 已提交
2270
		put_io_context(RQ_CIC(rq)->ioc);
L
Linus Torvalds 已提交
2271 2272

		rq->elevator_private = NULL;
J
Jens Axboe 已提交
2273
		rq->elevator_private2 = NULL;
L
Linus Torvalds 已提交
2274 2275 2276 2277 2278 2279

		cfq_put_queue(cfqq);
	}
}

/*
2280
 * Allocate cfq data structures associated with this request.
L
Linus Torvalds 已提交
2281
 */
2282
static int
2283
cfq_set_request(struct request_queue *q, struct request *rq, gfp_t gfp_mask)
L
Linus Torvalds 已提交
2284 2285 2286 2287
{
	struct cfq_data *cfqd = q->elevator->elevator_data;
	struct cfq_io_context *cic;
	const int rw = rq_data_dir(rq);
2288
	const int is_sync = rq_is_sync(rq);
2289
	struct cfq_queue *cfqq;
L
Linus Torvalds 已提交
2290 2291 2292 2293
	unsigned long flags;

	might_sleep_if(gfp_mask & __GFP_WAIT);

2294
	cic = cfq_get_io_context(cfqd, gfp_mask);
2295

L
Linus Torvalds 已提交
2296 2297
	spin_lock_irqsave(q->queue_lock, flags);

2298 2299 2300
	if (!cic)
		goto queue_fail;

2301 2302
	cfqq = cic_to_cfqq(cic, is_sync);
	if (!cfqq) {
2303
		cfqq = cfq_get_queue(cfqd, is_sync, cic->ioc, gfp_mask);
2304

2305 2306
		if (!cfqq)
			goto queue_fail;
L
Linus Torvalds 已提交
2307

2308 2309
		cic_set_cfqq(cic, cfqq, is_sync);
	}
L
Linus Torvalds 已提交
2310 2311

	cfqq->allocated[rw]++;
J
Jens Axboe 已提交
2312
	cfq_clear_cfqq_must_alloc(cfqq);
2313
	atomic_inc(&cfqq->ref);
L
Linus Torvalds 已提交
2314

J
Jens Axboe 已提交
2315
	spin_unlock_irqrestore(q->queue_lock, flags);
J
Jens Axboe 已提交
2316

J
Jens Axboe 已提交
2317 2318 2319
	rq->elevator_private = cic;
	rq->elevator_private2 = cfqq;
	return 0;
L
Linus Torvalds 已提交
2320

2321 2322 2323
queue_fail:
	if (cic)
		put_io_context(cic->ioc);
2324

J
Jens Axboe 已提交
2325
	cfq_schedule_dispatch(cfqd);
L
Linus Torvalds 已提交
2326
	spin_unlock_irqrestore(q->queue_lock, flags);
2327
	cfq_log(cfqd, "set_request fail");
L
Linus Torvalds 已提交
2328 2329 2330
	return 1;
}

2331
static void cfq_kick_queue(struct work_struct *work)
2332
{
2333 2334
	struct cfq_data *cfqd =
		container_of(work, struct cfq_data, unplug_work);
2335
	struct request_queue *q = cfqd->queue;
2336

2337
	spin_lock_irq(q->queue_lock);
2338
	blk_start_queueing(q);
2339
	spin_unlock_irq(q->queue_lock);
2340 2341 2342 2343 2344 2345 2346 2347 2348 2349
}

/*
 * Timer running if the active_queue is currently idling inside its time slice
 */
static void cfq_idle_slice_timer(unsigned long data)
{
	struct cfq_data *cfqd = (struct cfq_data *) data;
	struct cfq_queue *cfqq;
	unsigned long flags;
2350
	int timed_out = 1;
2351

2352 2353
	cfq_log(cfqd, "idle timer fired");

2354 2355
	spin_lock_irqsave(cfqd->queue->queue_lock, flags);

2356 2357
	cfqq = cfqd->active_queue;
	if (cfqq) {
2358 2359
		timed_out = 0;

2360 2361 2362 2363 2364 2365
		/*
		 * We saw a request before the queue expired, let it through
		 */
		if (cfq_cfqq_must_dispatch(cfqq))
			goto out_kick;

2366 2367 2368
		/*
		 * expired
		 */
2369
		if (cfq_slice_used(cfqq))
2370 2371 2372 2373 2374 2375
			goto expire;

		/*
		 * only expire and reinvoke request handler, if there are
		 * other queues with pending requests
		 */
2376
		if (!cfqd->busy_queues)
2377 2378 2379 2380 2381
			goto out_cont;

		/*
		 * not expired and it has a request pending, let it dispatch
		 */
2382
		if (!RB_EMPTY_ROOT(&cfqq->sort_list))
2383 2384 2385
			goto out_kick;
	}
expire:
2386
	cfq_slice_expired(cfqd, timed_out);
2387
out_kick:
J
Jens Axboe 已提交
2388
	cfq_schedule_dispatch(cfqd);
2389 2390 2391 2392
out_cont:
	spin_unlock_irqrestore(cfqd->queue->queue_lock, flags);
}

J
Jens Axboe 已提交
2393 2394 2395
static void cfq_shutdown_timer_wq(struct cfq_data *cfqd)
{
	del_timer_sync(&cfqd->idle_slice_timer);
2396
	cancel_work_sync(&cfqd->unplug_work);
J
Jens Axboe 已提交
2397
}
2398

2399 2400 2401 2402 2403 2404 2405 2406 2407 2408
static void cfq_put_async_queues(struct cfq_data *cfqd)
{
	int i;

	for (i = 0; i < IOPRIO_BE_NR; i++) {
		if (cfqd->async_cfqq[0][i])
			cfq_put_queue(cfqd->async_cfqq[0][i]);
		if (cfqd->async_cfqq[1][i])
			cfq_put_queue(cfqd->async_cfqq[1][i]);
	}
2409 2410 2411

	if (cfqd->async_idle_cfqq)
		cfq_put_queue(cfqd->async_idle_cfqq);
2412 2413
}

J
Jens Axboe 已提交
2414
static void cfq_exit_queue(struct elevator_queue *e)
L
Linus Torvalds 已提交
2415
{
2416
	struct cfq_data *cfqd = e->elevator_data;
2417
	struct request_queue *q = cfqd->queue;
2418

J
Jens Axboe 已提交
2419
	cfq_shutdown_timer_wq(cfqd);
2420

2421
	spin_lock_irq(q->queue_lock);
2422

2423
	if (cfqd->active_queue)
2424
		__cfq_slice_expired(cfqd, cfqd->active_queue, 0);
2425 2426

	while (!list_empty(&cfqd->cic_list)) {
2427 2428 2429
		struct cfq_io_context *cic = list_entry(cfqd->cic_list.next,
							struct cfq_io_context,
							queue_list);
2430 2431

		__cfq_exit_single_io_context(cfqd, cic);
2432
	}
2433

2434
	cfq_put_async_queues(cfqd);
2435

2436
	spin_unlock_irq(q->queue_lock);
2437 2438 2439 2440

	cfq_shutdown_timer_wq(cfqd);

	kfree(cfqd);
L
Linus Torvalds 已提交
2441 2442
}

2443
static void *cfq_init_queue(struct request_queue *q)
L
Linus Torvalds 已提交
2444 2445 2446
{
	struct cfq_data *cfqd;

2447
	cfqd = kmalloc_node(sizeof(*cfqd), GFP_KERNEL | __GFP_ZERO, q->node);
L
Linus Torvalds 已提交
2448
	if (!cfqd)
J
Jens Axboe 已提交
2449
		return NULL;
L
Linus Torvalds 已提交
2450

2451
	cfqd->service_tree = CFQ_RB_ROOT;
2452
	INIT_LIST_HEAD(&cfqd->cic_list);
L
Linus Torvalds 已提交
2453 2454 2455

	cfqd->queue = q;

2456 2457 2458 2459
	init_timer(&cfqd->idle_slice_timer);
	cfqd->idle_slice_timer.function = cfq_idle_slice_timer;
	cfqd->idle_slice_timer.data = (unsigned long) cfqd;

2460
	INIT_WORK(&cfqd->unplug_work, cfq_kick_queue);
2461

O
Oleg Nesterov 已提交
2462
	cfqd->last_end_request = jiffies;
L
Linus Torvalds 已提交
2463
	cfqd->cfq_quantum = cfq_quantum;
2464 2465
	cfqd->cfq_fifo_expire[0] = cfq_fifo_expire[0];
	cfqd->cfq_fifo_expire[1] = cfq_fifo_expire[1];
L
Linus Torvalds 已提交
2466 2467
	cfqd->cfq_back_max = cfq_back_max;
	cfqd->cfq_back_penalty = cfq_back_penalty;
2468 2469 2470 2471
	cfqd->cfq_slice[0] = cfq_slice_async;
	cfqd->cfq_slice[1] = cfq_slice_sync;
	cfqd->cfq_slice_async_rq = cfq_slice_async_rq;
	cfqd->cfq_slice_idle = cfq_slice_idle;
2472
	cfqd->hw_tag = 1;
J
Jens Axboe 已提交
2473

J
Jens Axboe 已提交
2474
	return cfqd;
L
Linus Torvalds 已提交
2475 2476 2477 2478
}

static void cfq_slab_kill(void)
{
2479 2480 2481 2482
	/*
	 * Caller already ensured that pending RCU callbacks are completed,
	 * so we should have no busy allocations at this point.
	 */
L
Linus Torvalds 已提交
2483 2484 2485 2486 2487 2488 2489 2490
	if (cfq_pool)
		kmem_cache_destroy(cfq_pool);
	if (cfq_ioc_pool)
		kmem_cache_destroy(cfq_ioc_pool);
}

static int __init cfq_slab_setup(void)
{
2491
	cfq_pool = KMEM_CACHE(cfq_queue, 0);
L
Linus Torvalds 已提交
2492 2493 2494
	if (!cfq_pool)
		goto fail;

2495
	cfq_ioc_pool = KMEM_CACHE(cfq_io_context, 0);
L
Linus Torvalds 已提交
2496 2497 2498 2499 2500 2501 2502 2503 2504 2505 2506 2507 2508 2509 2510 2511 2512 2513 2514 2515 2516 2517 2518 2519 2520 2521 2522 2523
	if (!cfq_ioc_pool)
		goto fail;

	return 0;
fail:
	cfq_slab_kill();
	return -ENOMEM;
}

/*
 * sysfs parts below -->
 */
static ssize_t
cfq_var_show(unsigned int var, char *page)
{
	return sprintf(page, "%d\n", var);
}

static ssize_t
cfq_var_store(unsigned int *var, const char *page, size_t count)
{
	char *p = (char *) page;

	*var = simple_strtoul(p, &p, 10);
	return count;
}

#define SHOW_FUNCTION(__FUNC, __VAR, __CONV)				\
J
Jens Axboe 已提交
2524
static ssize_t __FUNC(struct elevator_queue *e, char *page)		\
L
Linus Torvalds 已提交
2525
{									\
2526
	struct cfq_data *cfqd = e->elevator_data;			\
L
Linus Torvalds 已提交
2527 2528 2529 2530 2531 2532
	unsigned int __data = __VAR;					\
	if (__CONV)							\
		__data = jiffies_to_msecs(__data);			\
	return cfq_var_show(__data, (page));				\
}
SHOW_FUNCTION(cfq_quantum_show, cfqd->cfq_quantum, 0);
2533 2534
SHOW_FUNCTION(cfq_fifo_expire_sync_show, cfqd->cfq_fifo_expire[1], 1);
SHOW_FUNCTION(cfq_fifo_expire_async_show, cfqd->cfq_fifo_expire[0], 1);
2535 2536
SHOW_FUNCTION(cfq_back_seek_max_show, cfqd->cfq_back_max, 0);
SHOW_FUNCTION(cfq_back_seek_penalty_show, cfqd->cfq_back_penalty, 0);
2537 2538 2539 2540
SHOW_FUNCTION(cfq_slice_idle_show, cfqd->cfq_slice_idle, 1);
SHOW_FUNCTION(cfq_slice_sync_show, cfqd->cfq_slice[1], 1);
SHOW_FUNCTION(cfq_slice_async_show, cfqd->cfq_slice[0], 1);
SHOW_FUNCTION(cfq_slice_async_rq_show, cfqd->cfq_slice_async_rq, 0);
L
Linus Torvalds 已提交
2541 2542 2543
#undef SHOW_FUNCTION

#define STORE_FUNCTION(__FUNC, __PTR, MIN, MAX, __CONV)			\
J
Jens Axboe 已提交
2544
static ssize_t __FUNC(struct elevator_queue *e, const char *page, size_t count)	\
L
Linus Torvalds 已提交
2545
{									\
2546
	struct cfq_data *cfqd = e->elevator_data;			\
L
Linus Torvalds 已提交
2547 2548 2549 2550 2551 2552 2553 2554 2555 2556 2557 2558 2559
	unsigned int __data;						\
	int ret = cfq_var_store(&__data, (page), count);		\
	if (__data < (MIN))						\
		__data = (MIN);						\
	else if (__data > (MAX))					\
		__data = (MAX);						\
	if (__CONV)							\
		*(__PTR) = msecs_to_jiffies(__data);			\
	else								\
		*(__PTR) = __data;					\
	return ret;							\
}
STORE_FUNCTION(cfq_quantum_store, &cfqd->cfq_quantum, 1, UINT_MAX, 0);
2560 2561 2562 2563
STORE_FUNCTION(cfq_fifo_expire_sync_store, &cfqd->cfq_fifo_expire[1], 1,
		UINT_MAX, 1);
STORE_FUNCTION(cfq_fifo_expire_async_store, &cfqd->cfq_fifo_expire[0], 1,
		UINT_MAX, 1);
2564
STORE_FUNCTION(cfq_back_seek_max_store, &cfqd->cfq_back_max, 0, UINT_MAX, 0);
2565 2566
STORE_FUNCTION(cfq_back_seek_penalty_store, &cfqd->cfq_back_penalty, 1,
		UINT_MAX, 0);
2567 2568 2569
STORE_FUNCTION(cfq_slice_idle_store, &cfqd->cfq_slice_idle, 0, UINT_MAX, 1);
STORE_FUNCTION(cfq_slice_sync_store, &cfqd->cfq_slice[1], 1, UINT_MAX, 1);
STORE_FUNCTION(cfq_slice_async_store, &cfqd->cfq_slice[0], 1, UINT_MAX, 1);
2570 2571
STORE_FUNCTION(cfq_slice_async_rq_store, &cfqd->cfq_slice_async_rq, 1,
		UINT_MAX, 0);
L
Linus Torvalds 已提交
2572 2573
#undef STORE_FUNCTION

2574 2575 2576 2577 2578 2579 2580 2581 2582 2583 2584 2585 2586 2587
#define CFQ_ATTR(name) \
	__ATTR(name, S_IRUGO|S_IWUSR, cfq_##name##_show, cfq_##name##_store)

static struct elv_fs_entry cfq_attrs[] = {
	CFQ_ATTR(quantum),
	CFQ_ATTR(fifo_expire_sync),
	CFQ_ATTR(fifo_expire_async),
	CFQ_ATTR(back_seek_max),
	CFQ_ATTR(back_seek_penalty),
	CFQ_ATTR(slice_sync),
	CFQ_ATTR(slice_async),
	CFQ_ATTR(slice_async_rq),
	CFQ_ATTR(slice_idle),
	__ATTR_NULL
L
Linus Torvalds 已提交
2588 2589 2590 2591 2592 2593 2594
};

static struct elevator_type iosched_cfq = {
	.ops = {
		.elevator_merge_fn = 		cfq_merge,
		.elevator_merged_fn =		cfq_merged_request,
		.elevator_merge_req_fn =	cfq_merged_requests,
2595
		.elevator_allow_merge_fn =	cfq_allow_merge,
2596
		.elevator_dispatch_fn =		cfq_dispatch_requests,
L
Linus Torvalds 已提交
2597
		.elevator_add_req_fn =		cfq_insert_request,
2598
		.elevator_activate_req_fn =	cfq_activate_request,
L
Linus Torvalds 已提交
2599 2600 2601
		.elevator_deactivate_req_fn =	cfq_deactivate_request,
		.elevator_queue_empty_fn =	cfq_queue_empty,
		.elevator_completed_req_fn =	cfq_completed_request,
2602 2603
		.elevator_former_req_fn =	elv_rb_former_request,
		.elevator_latter_req_fn =	elv_rb_latter_request,
L
Linus Torvalds 已提交
2604 2605 2606 2607 2608
		.elevator_set_req_fn =		cfq_set_request,
		.elevator_put_req_fn =		cfq_put_request,
		.elevator_may_queue_fn =	cfq_may_queue,
		.elevator_init_fn =		cfq_init_queue,
		.elevator_exit_fn =		cfq_exit_queue,
2609
		.trim =				cfq_free_io_context,
L
Linus Torvalds 已提交
2610
	},
2611
	.elevator_attrs =	cfq_attrs,
L
Linus Torvalds 已提交
2612 2613 2614 2615 2616 2617
	.elevator_name =	"cfq",
	.elevator_owner =	THIS_MODULE,
};

static int __init cfq_init(void)
{
2618 2619 2620 2621 2622 2623 2624 2625
	/*
	 * could be 0 on HZ < 1000 setups
	 */
	if (!cfq_slice_async)
		cfq_slice_async = 1;
	if (!cfq_slice_idle)
		cfq_slice_idle = 1;

L
Linus Torvalds 已提交
2626 2627 2628
	if (cfq_slab_setup())
		return -ENOMEM;

2629
	elv_register(&iosched_cfq);
L
Linus Torvalds 已提交
2630

2631
	return 0;
L
Linus Torvalds 已提交
2632 2633 2634 2635
}

static void __exit cfq_exit(void)
{
2636
	DECLARE_COMPLETION_ONSTACK(all_gone);
L
Linus Torvalds 已提交
2637
	elv_unregister(&iosched_cfq);
2638
	ioc_gone = &all_gone;
2639 2640
	/* ioc_gone's update must be visible before reading ioc_count */
	smp_wmb();
2641 2642 2643 2644 2645

	/*
	 * this also protects us from entering cfq_slab_kill() with
	 * pending RCU callbacks
	 */
2646
	if (elv_ioc_count_read(ioc_count))
2647
		wait_for_completion(&all_gone);
2648
	cfq_slab_kill();
L
Linus Torvalds 已提交
2649 2650 2651 2652 2653 2654 2655 2656
}

module_init(cfq_init);
module_exit(cfq_exit);

MODULE_AUTHOR("Jens Axboe");
MODULE_LICENSE("GPL");
MODULE_DESCRIPTION("Completely Fair Queueing IO scheduler");