cfq-iosched.c 120.3 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>
10
#include <linux/slab.h>
A
Al Viro 已提交
11 12
#include <linux/blkdev.h>
#include <linux/elevator.h>
R
Randy Dunlap 已提交
13
#include <linux/jiffies.h>
L
Linus Torvalds 已提交
14
#include <linux/rbtree.h>
15
#include <linux/ioprio.h>
16
#include <linux/blktrace_api.h>
17
#include <linux/blk-cgroup.h>
18
#include "blk.h"
L
Linus Torvalds 已提交
19 20 21 22

/*
 * tunables
 */
23
/* max queue in one round of service */
S
Shaohua Li 已提交
24
static const int cfq_quantum = 8;
25
static const int cfq_fifo_expire[2] = { HZ / 4, HZ / 8 };
26 27 28 29
/* 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;
30
static const int cfq_slice_sync = HZ / 10;
J
Jens Axboe 已提交
31
static int cfq_slice_async = HZ / 25;
32
static const int cfq_slice_async_rq = 2;
33
static int cfq_slice_idle = HZ / 125;
34
static int cfq_group_idle = HZ / 125;
35 36
static const int cfq_target_latency = HZ * 3/10; /* 300 ms */
static const int cfq_hist_divisor = 4;
37

38
/*
39
 * offset from end of service tree
40
 */
41
#define CFQ_IDLE_DELAY		(HZ / 5)
42 43 44 45 46 47

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

48
#define CFQ_SLICE_SCALE		(5)
49
#define CFQ_HW_QUEUE_MIN	(5)
50
#define CFQ_SERVICE_SHIFT       12
51

52
#define CFQQ_SEEK_THR		(sector_t)(8 * 100)
53
#define CFQQ_CLOSE_THR		(sector_t)(8 * 1024)
54
#define CFQQ_SECT_THR_NONROT	(sector_t)(2 * 32)
55
#define CFQQ_SEEKY(cfqq)	(hweight32(cfqq->seek_history) > 32/8)
56

57 58 59
#define RQ_CIC(rq)		icq_to_cic((rq)->elv.icq)
#define RQ_CFQQ(rq)		(struct cfq_queue *) ((rq)->elv.priv[0])
#define RQ_CFQG(rq)		(struct cfq_group *) ((rq)->elv.priv[1])
L
Linus Torvalds 已提交
60

61
static struct kmem_cache *cfq_pool;
L
Linus Torvalds 已提交
62

63 64 65 66
#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)

67
#define sample_valid(samples)	((samples) > 80)
68
#define rb_entry_cfqg(node)	rb_entry((node), struct cfq_group, rb_node)
69

70 71 72 73 74 75 76 77
struct cfq_ttime {
	unsigned long last_end_request;

	unsigned long ttime_total;
	unsigned long ttime_samples;
	unsigned long ttime_mean;
};

78 79 80 81 82 83 84 85 86
/*
 * 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;
87
	unsigned count;
88
	u64 min_vdisktime;
89
	struct cfq_ttime ttime;
90
};
91 92
#define CFQ_RB_ROOT	(struct cfq_rb_root) { .rb = RB_ROOT, \
			.ttime = {.last_end_request = jiffies,},}
93

94 95 96 97 98
/*
 * Per process-grouping structure
 */
struct cfq_queue {
	/* reference count */
99
	int ref;
100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122
	/* various state flags, see below */
	unsigned int flags;
	/* parent cfq_data */
	struct cfq_data *cfqd;
	/* service_tree member */
	struct rb_node rb_node;
	/* service_tree key */
	unsigned long rb_key;
	/* prio tree member */
	struct rb_node p_node;
	/* prio tree root we belong to, if any */
	struct rb_root *p_root;
	/* sorted list of pending requests */
	struct rb_root sort_list;
	/* if fifo isn't expired, next request to serve */
	struct request *next_rq;
	/* requests queued in sort_list */
	int queued[2];
	/* currently allocated requests */
	int allocated[2];
	/* fifo list of requests in sort_list */
	struct list_head fifo;

123 124
	/* time when queue got scheduled in to dispatch first request. */
	unsigned long dispatch_start;
125
	unsigned int allocated_slice;
126
	unsigned int slice_dispatch;
127 128
	/* time when first request from queue completed and slice started. */
	unsigned long slice_start;
129 130 131
	unsigned long slice_end;
	long slice_resid;

132 133
	/* pending priority requests */
	int prio_pending;
134 135 136 137 138
	/* number of requests that are on the dispatch list or inside driver */
	int dispatched;

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

141 142
	pid_t pid;

143
	u32 seek_history;
144 145
	sector_t last_request_pos;

146
	struct cfq_rb_root *service_tree;
J
Jeff Moyer 已提交
147
	struct cfq_queue *new_cfqq;
148
	struct cfq_group *cfqg;
149 150
	/* Number of sectors dispatched from queue in single dispatch round */
	unsigned long nr_sectors;
151 152
};

153
/*
154
 * First index in the service_trees.
155 156
 * IDLE is handled separately, so it has negative index
 */
157
enum wl_class_t {
158
	BE_WORKLOAD = 0,
159 160
	RT_WORKLOAD = 1,
	IDLE_WORKLOAD = 2,
161
	CFQ_PRIO_NR,
162 163
};

164 165 166 167 168 169 170 171 172
/*
 * Second index in the service_trees.
 */
enum wl_type_t {
	ASYNC_WORKLOAD = 0,
	SYNC_NOIDLE_WORKLOAD = 1,
	SYNC_WORKLOAD = 2
};

173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201
struct cfqg_stats {
#ifdef CONFIG_CFQ_GROUP_IOSCHED
	/* total bytes transferred */
	struct blkg_rwstat		service_bytes;
	/* total IOs serviced, post merge */
	struct blkg_rwstat		serviced;
	/* number of ios merged */
	struct blkg_rwstat		merged;
	/* total time spent on device in ns, may not be accurate w/ queueing */
	struct blkg_rwstat		service_time;
	/* total time spent waiting in scheduler queue in ns */
	struct blkg_rwstat		wait_time;
	/* number of IOs queued up */
	struct blkg_rwstat		queued;
	/* total sectors transferred */
	struct blkg_stat		sectors;
	/* total disk time and nr sectors dispatched by this group */
	struct blkg_stat		time;
#ifdef CONFIG_DEBUG_BLK_CGROUP
	/* time not charged to this cgroup */
	struct blkg_stat		unaccounted_time;
	/* sum of number of ios queued across all samples */
	struct blkg_stat		avg_queue_size_sum;
	/* count of samples taken for average */
	struct blkg_stat		avg_queue_size_samples;
	/* how many times this group has been removed from service tree */
	struct blkg_stat		dequeue;
	/* total time spent waiting for it to be assigned a timeslice. */
	struct blkg_stat		group_wait_time;
T
Tejun Heo 已提交
202
	/* time spent idling for this blkcg_gq */
203 204 205 206 207 208 209 210 211 212 213 214
	struct blkg_stat		idle_time;
	/* total time with empty current active q with other requests queued */
	struct blkg_stat		empty_time;
	/* fields after this shouldn't be cleared on stat reset */
	uint64_t			start_group_wait_time;
	uint64_t			start_idle_time;
	uint64_t			start_empty_time;
	uint16_t			flags;
#endif	/* CONFIG_DEBUG_BLK_CGROUP */
#endif	/* CONFIG_CFQ_GROUP_IOSCHED */
};

215 216
/* This is per cgroup per device grouping structure */
struct cfq_group {
217 218 219
	/* must be the first member */
	struct blkg_policy_data pd;

220 221 222 223 224
	/* group service_tree member */
	struct rb_node rb_node;

	/* group service_tree key */
	u64 vdisktime;
T
Tejun Heo 已提交
225

226 227 228 229 230 231 232 233 234 235 236 237
	/*
	 * The number of active cfqgs and sum of their weights under this
	 * cfqg.  This covers this cfqg's leaf_weight and all children's
	 * weights, but does not cover weights of further descendants.
	 *
	 * If a cfqg is on the service tree, it's active.  An active cfqg
	 * also activates its parent and contributes to the children_weight
	 * of the parent.
	 */
	int nr_active;
	unsigned int children_weight;

238 239 240 241 242 243 244 245 246 247 248 249
	/*
	 * vfraction is the fraction of vdisktime that the tasks in this
	 * cfqg are entitled to.  This is determined by compounding the
	 * ratios walking up from this cfqg to the root.
	 *
	 * It is in fixed point w/ CFQ_SERVICE_SHIFT and the sum of all
	 * vfractions on a service tree is approximately 1.  The sum may
	 * deviate a bit due to rounding errors and fluctuations caused by
	 * cfqgs entering and leaving the service tree.
	 */
	unsigned int vfraction;

T
Tejun Heo 已提交
250 251 252 253 254 255
	/*
	 * There are two weights - (internal) weight is the weight of this
	 * cfqg against the sibling cfqgs.  leaf_weight is the wight of
	 * this cfqg against the child cfqgs.  For the root cfqg, both
	 * weights are kept in sync for backward compatibility.
	 */
256
	unsigned int weight;
257
	unsigned int new_weight;
258
	unsigned int dev_weight;
259

T
Tejun Heo 已提交
260 261 262 263
	unsigned int leaf_weight;
	unsigned int new_leaf_weight;
	unsigned int dev_leaf_weight;

264 265 266
	/* number of cfqq currently on this group */
	int nr_cfqq;

267
	/*
268
	 * Per group busy queues average. Useful for workload slice calc. We
269 270 271 272 273 274 275 276 277 278 279
	 * create the array for each prio class but at run time it is used
	 * only for RT and BE class and slot for IDLE class remains unused.
	 * This is primarily done to avoid confusion and a gcc warning.
	 */
	unsigned int busy_queues_avg[CFQ_PRIO_NR];
	/*
	 * rr lists of queues with requests. We maintain service trees for
	 * RT and BE classes. These trees are subdivided in subclasses
	 * of SYNC, SYNC_NOIDLE and ASYNC based on workload type. For IDLE
	 * class there is no subclassification and all the cfq queues go on
	 * a single tree service_tree_idle.
280 281 282 283
	 * Counts are embedded in the cfq_rb_root
	 */
	struct cfq_rb_root service_trees[2][3];
	struct cfq_rb_root service_tree_idle;
284

285 286 287
	unsigned long saved_wl_slice;
	enum wl_type_t saved_wl_type;
	enum wl_class_t saved_wl_class;
288

289 290
	/* number of requests that are on the dispatch list or inside driver */
	int dispatched;
S
Shaohua Li 已提交
291
	struct cfq_ttime ttime;
292 293
	struct cfqg_stats stats;	/* stats for this cfqg */
	struct cfqg_stats dead_stats;	/* stats pushed from dead children */
294
};
295

296 297 298 299
struct cfq_io_cq {
	struct io_cq		icq;		/* must be the first member */
	struct cfq_queue	*cfqq[2];
	struct cfq_ttime	ttime;
T
Tejun Heo 已提交
300 301
	int			ioprio;		/* the current ioprio */
#ifdef CONFIG_CFQ_GROUP_IOSCHED
T
Tejun Heo 已提交
302
	uint64_t		blkcg_serial_nr; /* the current blkcg serial */
T
Tejun Heo 已提交
303
#endif
304 305
};

306 307 308
/*
 * Per block device queue structure
 */
L
Linus Torvalds 已提交
309
struct cfq_data {
310
	struct request_queue *queue;
311 312
	/* Root service tree for cfq_groups */
	struct cfq_rb_root grp_service_tree;
313
	struct cfq_group *root_group;
314

315 316
	/*
	 * The priority currently being served
317
	 */
318 319
	enum wl_class_t serving_wl_class;
	enum wl_type_t serving_wl_type;
320
	unsigned long workload_expires;
321
	struct cfq_group *serving_group;
322 323 324 325 326 327 328 329

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

330
	unsigned int busy_queues;
331
	unsigned int busy_sync_queues;
332

333 334
	int rq_in_driver;
	int rq_in_flight[2];
335 336 337 338 339

	/*
	 * queue-depth detection
	 */
	int rq_queued;
340
	int hw_tag;
341 342 343 344 345 346 347 348
	/*
	 * hw_tag can be
	 * -1 => indeterminate, (cfq will behave as if NCQ is present, to allow better detection)
	 *  1 => NCQ is present (hw_tag_est_depth is the estimated max depth)
	 *  0 => no NCQ
	 */
	int hw_tag_est_depth;
	unsigned int hw_tag_samples;
L
Linus Torvalds 已提交
349

350 351 352 353
	/*
	 * idle window management
	 */
	struct timer_list idle_slice_timer;
354
	struct work_struct unplug_work;
L
Linus Torvalds 已提交
355

356
	struct cfq_queue *active_queue;
357
	struct cfq_io_cq *active_cic;
358

359 360 361 362 363
	/*
	 * async queue for each priority case
	 */
	struct cfq_queue *async_cfqq[2][IOPRIO_BE_NR];
	struct cfq_queue *async_idle_cfqq;
364

J
Jens Axboe 已提交
365
	sector_t last_position;
L
Linus Torvalds 已提交
366 367 368 369 370

	/*
	 * tunables, see top of file
	 */
	unsigned int cfq_quantum;
371
	unsigned int cfq_fifo_expire[2];
L
Linus Torvalds 已提交
372 373
	unsigned int cfq_back_penalty;
	unsigned int cfq_back_max;
374 375 376
	unsigned int cfq_slice[2];
	unsigned int cfq_slice_async_rq;
	unsigned int cfq_slice_idle;
377
	unsigned int cfq_group_idle;
378
	unsigned int cfq_latency;
379
	unsigned int cfq_target_latency;
380

381 382 383 384
	/*
	 * Fallback dummy cfqq for extreme OOM conditions
	 */
	struct cfq_queue oom_cfqq;
385

386
	unsigned long last_delayed_sync;
L
Linus Torvalds 已提交
387 388
};

389 390
static struct cfq_group *cfq_get_next_cfqg(struct cfq_data *cfqd);

391
static struct cfq_rb_root *st_for(struct cfq_group *cfqg,
392
					    enum wl_class_t class,
393
					    enum wl_type_t type)
394
{
395 396 397
	if (!cfqg)
		return NULL;

398
	if (class == IDLE_WORKLOAD)
399
		return &cfqg->service_tree_idle;
400

401
	return &cfqg->service_trees[class][type];
402 403
}

J
Jens Axboe 已提交
404
enum cfqq_state_flags {
405 406
	CFQ_CFQQ_FLAG_on_rr = 0,	/* on round-robin busy list */
	CFQ_CFQQ_FLAG_wait_request,	/* waiting for a request */
407
	CFQ_CFQQ_FLAG_must_dispatch,	/* must be allowed a dispatch */
408 409 410 411
	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 */
412
	CFQ_CFQQ_FLAG_slice_new,	/* no requests dispatched in slice */
413
	CFQ_CFQQ_FLAG_sync,		/* synchronous queue */
414
	CFQ_CFQQ_FLAG_coop,		/* cfqq is shared */
415
	CFQ_CFQQ_FLAG_split_coop,	/* shared cfqq will be splitted */
416
	CFQ_CFQQ_FLAG_deep,		/* sync cfqq experienced large depth */
417
	CFQ_CFQQ_FLAG_wait_busy,	/* Waiting for next request */
J
Jens Axboe 已提交
418 419 420 421 422
};

#define CFQ_CFQQ_FNS(name)						\
static inline void cfq_mark_cfqq_##name(struct cfq_queue *cfqq)		\
{									\
423
	(cfqq)->flags |= (1 << CFQ_CFQQ_FLAG_##name);			\
J
Jens Axboe 已提交
424 425 426
}									\
static inline void cfq_clear_cfqq_##name(struct cfq_queue *cfqq)	\
{									\
427
	(cfqq)->flags &= ~(1 << CFQ_CFQQ_FLAG_##name);			\
J
Jens Axboe 已提交
428 429 430
}									\
static inline int cfq_cfqq_##name(const struct cfq_queue *cfqq)		\
{									\
431
	return ((cfqq)->flags & (1 << CFQ_CFQQ_FLAG_##name)) != 0;	\
J
Jens Axboe 已提交
432 433 434 435
}

CFQ_CFQQ_FNS(on_rr);
CFQ_CFQQ_FNS(wait_request);
436
CFQ_CFQQ_FNS(must_dispatch);
J
Jens Axboe 已提交
437 438 439 440
CFQ_CFQQ_FNS(must_alloc_slice);
CFQ_CFQQ_FNS(fifo_expire);
CFQ_CFQQ_FNS(idle_window);
CFQ_CFQQ_FNS(prio_changed);
441
CFQ_CFQQ_FNS(slice_new);
442
CFQ_CFQQ_FNS(sync);
443
CFQ_CFQQ_FNS(coop);
444
CFQ_CFQQ_FNS(split_coop);
445
CFQ_CFQQ_FNS(deep);
446
CFQ_CFQQ_FNS(wait_busy);
J
Jens Axboe 已提交
447 448
#undef CFQ_CFQQ_FNS

449 450 451 452 453 454 455 456 457 458
static inline struct cfq_group *pd_to_cfqg(struct blkg_policy_data *pd)
{
	return pd ? container_of(pd, struct cfq_group, pd) : NULL;
}

static inline struct blkcg_gq *cfqg_to_blkg(struct cfq_group *cfqg)
{
	return pd_to_blkg(&cfqg->pd);
}

459
#if defined(CONFIG_CFQ_GROUP_IOSCHED) && defined(CONFIG_DEBUG_BLK_CGROUP)
460

461 462 463 464 465
/* cfqg stats flags */
enum cfqg_stats_flags {
	CFQG_stats_waiting = 0,
	CFQG_stats_idling,
	CFQG_stats_empty,
466 467
};

468 469
#define CFQG_FLAG_FNS(name)						\
static inline void cfqg_stats_mark_##name(struct cfqg_stats *stats)	\
470
{									\
471
	stats->flags |= (1 << CFQG_stats_##name);			\
472
}									\
473
static inline void cfqg_stats_clear_##name(struct cfqg_stats *stats)	\
474
{									\
475
	stats->flags &= ~(1 << CFQG_stats_##name);			\
476
}									\
477
static inline int cfqg_stats_##name(struct cfqg_stats *stats)		\
478
{									\
479
	return (stats->flags & (1 << CFQG_stats_##name)) != 0;		\
480 481
}									\

482 483 484 485
CFQG_FLAG_FNS(waiting)
CFQG_FLAG_FNS(idling)
CFQG_FLAG_FNS(empty)
#undef CFQG_FLAG_FNS
486 487

/* This should be called with the queue_lock held. */
488
static void cfqg_stats_update_group_wait_time(struct cfqg_stats *stats)
489 490 491
{
	unsigned long long now;

492
	if (!cfqg_stats_waiting(stats))
493 494 495 496 497 498
		return;

	now = sched_clock();
	if (time_after64(now, stats->start_group_wait_time))
		blkg_stat_add(&stats->group_wait_time,
			      now - stats->start_group_wait_time);
499
	cfqg_stats_clear_waiting(stats);
500 501 502
}

/* This should be called with the queue_lock held. */
503 504
static void cfqg_stats_set_start_group_wait_time(struct cfq_group *cfqg,
						 struct cfq_group *curr_cfqg)
505
{
506
	struct cfqg_stats *stats = &cfqg->stats;
507

508
	if (cfqg_stats_waiting(stats))
509
		return;
510
	if (cfqg == curr_cfqg)
511
		return;
512 513
	stats->start_group_wait_time = sched_clock();
	cfqg_stats_mark_waiting(stats);
514 515 516
}

/* This should be called with the queue_lock held. */
517
static void cfqg_stats_end_empty_time(struct cfqg_stats *stats)
518 519 520
{
	unsigned long long now;

521
	if (!cfqg_stats_empty(stats))
522 523 524 525 526 527
		return;

	now = sched_clock();
	if (time_after64(now, stats->start_empty_time))
		blkg_stat_add(&stats->empty_time,
			      now - stats->start_empty_time);
528
	cfqg_stats_clear_empty(stats);
529 530
}

531
static void cfqg_stats_update_dequeue(struct cfq_group *cfqg)
532
{
533
	blkg_stat_add(&cfqg->stats.dequeue, 1);
534 535
}

536
static void cfqg_stats_set_start_empty_time(struct cfq_group *cfqg)
537
{
538
	struct cfqg_stats *stats = &cfqg->stats;
539

540
	if (blkg_rwstat_total(&stats->queued))
541 542 543 544 545 546 547
		return;

	/*
	 * group is already marked empty. This can happen if cfqq got new
	 * request in parent group and moved to this group while being added
	 * to service tree. Just ignore the event and move on.
	 */
548
	if (cfqg_stats_empty(stats))
549 550 551
		return;

	stats->start_empty_time = sched_clock();
552
	cfqg_stats_mark_empty(stats);
553 554
}

555
static void cfqg_stats_update_idle_time(struct cfq_group *cfqg)
556
{
557
	struct cfqg_stats *stats = &cfqg->stats;
558

559
	if (cfqg_stats_idling(stats)) {
560 561 562 563 564
		unsigned long long now = sched_clock();

		if (time_after64(now, stats->start_idle_time))
			blkg_stat_add(&stats->idle_time,
				      now - stats->start_idle_time);
565
		cfqg_stats_clear_idling(stats);
566 567 568
	}
}

569
static void cfqg_stats_set_start_idle_time(struct cfq_group *cfqg)
570
{
571
	struct cfqg_stats *stats = &cfqg->stats;
572

573
	BUG_ON(cfqg_stats_idling(stats));
574 575

	stats->start_idle_time = sched_clock();
576
	cfqg_stats_mark_idling(stats);
577 578
}

579
static void cfqg_stats_update_avg_queue_size(struct cfq_group *cfqg)
580
{
581
	struct cfqg_stats *stats = &cfqg->stats;
582 583

	blkg_stat_add(&stats->avg_queue_size_sum,
584
		      blkg_rwstat_total(&stats->queued));
585
	blkg_stat_add(&stats->avg_queue_size_samples, 1);
586
	cfqg_stats_update_group_wait_time(stats);
587 588 589 590
}

#else	/* CONFIG_CFQ_GROUP_IOSCHED && CONFIG_DEBUG_BLK_CGROUP */

T
Tejun Heo 已提交
591 592 593 594 595 596 597
static inline void cfqg_stats_set_start_group_wait_time(struct cfq_group *cfqg, struct cfq_group *curr_cfqg) { }
static inline void cfqg_stats_end_empty_time(struct cfqg_stats *stats) { }
static inline void cfqg_stats_update_dequeue(struct cfq_group *cfqg) { }
static inline void cfqg_stats_set_start_empty_time(struct cfq_group *cfqg) { }
static inline void cfqg_stats_update_idle_time(struct cfq_group *cfqg) { }
static inline void cfqg_stats_set_start_idle_time(struct cfq_group *cfqg) { }
static inline void cfqg_stats_update_avg_queue_size(struct cfq_group *cfqg) { }
598 599 600 601

#endif	/* CONFIG_CFQ_GROUP_IOSCHED && CONFIG_DEBUG_BLK_CGROUP */

#ifdef CONFIG_CFQ_GROUP_IOSCHED
602

603 604 605 606 607 608 609
static struct blkcg_policy blkcg_policy_cfq;

static inline struct cfq_group *blkg_to_cfqg(struct blkcg_gq *blkg)
{
	return pd_to_cfqg(blkg_to_pd(blkg, &blkcg_policy_cfq));
}

610
static inline struct cfq_group *cfqg_parent(struct cfq_group *cfqg)
611
{
612
	struct blkcg_gq *pblkg = cfqg_to_blkg(cfqg)->parent;
613

614
	return pblkg ? blkg_to_cfqg(pblkg) : NULL;
615 616
}

617 618 619 620 621 622 623 624 625 626
static inline void cfqg_get(struct cfq_group *cfqg)
{
	return blkg_get(cfqg_to_blkg(cfqg));
}

static inline void cfqg_put(struct cfq_group *cfqg)
{
	return blkg_put(cfqg_to_blkg(cfqg));
}

T
Tejun Heo 已提交
627 628 629 630
#define cfq_log_cfqq(cfqd, cfqq, fmt, args...)	do {			\
	char __pbuf[128];						\
									\
	blkg_path(cfqg_to_blkg((cfqq)->cfqg), __pbuf, sizeof(__pbuf));	\
631 632 633
	blk_add_trace_msg((cfqd)->queue, "cfq%d%c%c %s " fmt, (cfqq)->pid, \
			cfq_cfqq_sync((cfqq)) ? 'S' : 'A',		\
			cfqq_type((cfqq)) == SYNC_NOIDLE_WORKLOAD ? 'N' : ' ',\
T
Tejun Heo 已提交
634 635 636 637 638 639 640 641 642
			  __pbuf, ##args);				\
} while (0)

#define cfq_log_cfqg(cfqd, cfqg, fmt, args...)	do {			\
	char __pbuf[128];						\
									\
	blkg_path(cfqg_to_blkg(cfqg), __pbuf, sizeof(__pbuf));		\
	blk_add_trace_msg((cfqd)->queue, "%s " fmt, __pbuf, ##args);	\
} while (0)
V
Vivek Goyal 已提交
643

644 645
static inline void cfqg_stats_update_io_add(struct cfq_group *cfqg,
					    struct cfq_group *curr_cfqg, int rw)
646
{
647 648 649
	blkg_rwstat_add(&cfqg->stats.queued, rw, 1);
	cfqg_stats_end_empty_time(&cfqg->stats);
	cfqg_stats_set_start_group_wait_time(cfqg, curr_cfqg);
650 651
}

652 653
static inline void cfqg_stats_update_timeslice_used(struct cfq_group *cfqg,
			unsigned long time, unsigned long unaccounted_time)
654
{
655
	blkg_stat_add(&cfqg->stats.time, time);
656
#ifdef CONFIG_DEBUG_BLK_CGROUP
657
	blkg_stat_add(&cfqg->stats.unaccounted_time, unaccounted_time);
658
#endif
659 660
}

661
static inline void cfqg_stats_update_io_remove(struct cfq_group *cfqg, int rw)
662
{
663
	blkg_rwstat_add(&cfqg->stats.queued, rw, -1);
664 665
}

666
static inline void cfqg_stats_update_io_merged(struct cfq_group *cfqg, int rw)
667
{
668
	blkg_rwstat_add(&cfqg->stats.merged, rw, 1);
669 670
}

671 672
static inline void cfqg_stats_update_dispatch(struct cfq_group *cfqg,
					      uint64_t bytes, int rw)
673
{
674 675 676
	blkg_stat_add(&cfqg->stats.sectors, bytes >> 9);
	blkg_rwstat_add(&cfqg->stats.serviced, rw, 1);
	blkg_rwstat_add(&cfqg->stats.service_bytes, rw, bytes);
677 678
}

679 680
static inline void cfqg_stats_update_completion(struct cfq_group *cfqg,
			uint64_t start_time, uint64_t io_start_time, int rw)
681
{
682
	struct cfqg_stats *stats = &cfqg->stats;
683 684 685 686 687 688 689
	unsigned long long now = sched_clock();

	if (time_after64(now, io_start_time))
		blkg_rwstat_add(&stats->service_time, rw, now - io_start_time);
	if (time_after64(io_start_time, start_time))
		blkg_rwstat_add(&stats->wait_time, rw,
				io_start_time - start_time);
690 691
}

692 693
/* @stats = 0 */
static void cfqg_stats_reset(struct cfqg_stats *stats)
694 695 696 697 698 699 700 701 702 703 704 705 706 707 708 709 710 711 712
{
	/* queued stats shouldn't be cleared */
	blkg_rwstat_reset(&stats->service_bytes);
	blkg_rwstat_reset(&stats->serviced);
	blkg_rwstat_reset(&stats->merged);
	blkg_rwstat_reset(&stats->service_time);
	blkg_rwstat_reset(&stats->wait_time);
	blkg_stat_reset(&stats->time);
#ifdef CONFIG_DEBUG_BLK_CGROUP
	blkg_stat_reset(&stats->unaccounted_time);
	blkg_stat_reset(&stats->avg_queue_size_sum);
	blkg_stat_reset(&stats->avg_queue_size_samples);
	blkg_stat_reset(&stats->dequeue);
	blkg_stat_reset(&stats->group_wait_time);
	blkg_stat_reset(&stats->idle_time);
	blkg_stat_reset(&stats->empty_time);
#endif
}

713 714 715 716 717 718 719 720 721 722 723 724 725 726 727 728 729 730 731 732 733 734 735 736 737 738 739 740 741 742 743 744 745 746 747 748 749 750 751 752 753
/* @to += @from */
static void cfqg_stats_merge(struct cfqg_stats *to, struct cfqg_stats *from)
{
	/* queued stats shouldn't be cleared */
	blkg_rwstat_merge(&to->service_bytes, &from->service_bytes);
	blkg_rwstat_merge(&to->serviced, &from->serviced);
	blkg_rwstat_merge(&to->merged, &from->merged);
	blkg_rwstat_merge(&to->service_time, &from->service_time);
	blkg_rwstat_merge(&to->wait_time, &from->wait_time);
	blkg_stat_merge(&from->time, &from->time);
#ifdef CONFIG_DEBUG_BLK_CGROUP
	blkg_stat_merge(&to->unaccounted_time, &from->unaccounted_time);
	blkg_stat_merge(&to->avg_queue_size_sum, &from->avg_queue_size_sum);
	blkg_stat_merge(&to->avg_queue_size_samples, &from->avg_queue_size_samples);
	blkg_stat_merge(&to->dequeue, &from->dequeue);
	blkg_stat_merge(&to->group_wait_time, &from->group_wait_time);
	blkg_stat_merge(&to->idle_time, &from->idle_time);
	blkg_stat_merge(&to->empty_time, &from->empty_time);
#endif
}

/*
 * Transfer @cfqg's stats to its parent's dead_stats so that the ancestors'
 * recursive stats can still account for the amount used by this cfqg after
 * it's gone.
 */
static void cfqg_stats_xfer_dead(struct cfq_group *cfqg)
{
	struct cfq_group *parent = cfqg_parent(cfqg);

	lockdep_assert_held(cfqg_to_blkg(cfqg)->q->queue_lock);

	if (unlikely(!parent))
		return;

	cfqg_stats_merge(&parent->dead_stats, &cfqg->stats);
	cfqg_stats_merge(&parent->dead_stats, &cfqg->dead_stats);
	cfqg_stats_reset(&cfqg->stats);
	cfqg_stats_reset(&cfqg->dead_stats);
}

754 755
#else	/* CONFIG_CFQ_GROUP_IOSCHED */

756
static inline struct cfq_group *cfqg_parent(struct cfq_group *cfqg) { return NULL; }
757 758 759
static inline void cfqg_get(struct cfq_group *cfqg) { }
static inline void cfqg_put(struct cfq_group *cfqg) { }

760
#define cfq_log_cfqq(cfqd, cfqq, fmt, args...)	\
761 762 763 764
	blk_add_trace_msg((cfqd)->queue, "cfq%d%c%c " fmt, (cfqq)->pid,	\
			cfq_cfqq_sync((cfqq)) ? 'S' : 'A',		\
			cfqq_type((cfqq)) == SYNC_NOIDLE_WORKLOAD ? 'N' : ' ',\
				##args)
765
#define cfq_log_cfqg(cfqd, cfqg, fmt, args...)		do {} while (0)
766

767 768 769 770 771 772 773 774 775 776
static inline void cfqg_stats_update_io_add(struct cfq_group *cfqg,
			struct cfq_group *curr_cfqg, int rw) { }
static inline void cfqg_stats_update_timeslice_used(struct cfq_group *cfqg,
			unsigned long time, unsigned long unaccounted_time) { }
static inline void cfqg_stats_update_io_remove(struct cfq_group *cfqg, int rw) { }
static inline void cfqg_stats_update_io_merged(struct cfq_group *cfqg, int rw) { }
static inline void cfqg_stats_update_dispatch(struct cfq_group *cfqg,
					      uint64_t bytes, int rw) { }
static inline void cfqg_stats_update_completion(struct cfq_group *cfqg,
			uint64_t start_time, uint64_t io_start_time, int rw) { }
777

778 779
#endif	/* CONFIG_CFQ_GROUP_IOSCHED */

780 781 782
#define cfq_log(cfqd, fmt, args...)	\
	blk_add_trace_msg((cfqd)->queue, "cfq " fmt, ##args)

783 784 785 786 787 788 789 790 791 792
/* Traverses through cfq group service trees */
#define for_each_cfqg_st(cfqg, i, j, st) \
	for (i = 0; i <= IDLE_WORKLOAD; i++) \
		for (j = 0, st = i < IDLE_WORKLOAD ? &cfqg->service_trees[i][j]\
			: &cfqg->service_tree_idle; \
			(i < IDLE_WORKLOAD && j <= SYNC_WORKLOAD) || \
			(i == IDLE_WORKLOAD && j == 0); \
			j++, st = i < IDLE_WORKLOAD ? \
			&cfqg->service_trees[i][j]: NULL) \

793 794 795 796 797 798 799 800 801 802 803 804
static inline bool cfq_io_thinktime_big(struct cfq_data *cfqd,
	struct cfq_ttime *ttime, bool group_idle)
{
	unsigned long slice;
	if (!sample_valid(ttime->ttime_samples))
		return false;
	if (group_idle)
		slice = cfqd->cfq_group_idle;
	else
		slice = cfqd->cfq_slice_idle;
	return ttime->ttime_mean > slice;
}
805

806 807 808 809 810 811 812 813 814 815 816 817 818 819 820
static inline bool iops_mode(struct cfq_data *cfqd)
{
	/*
	 * If we are not idling on queues and it is a NCQ drive, parallel
	 * execution of requests is on and measuring time is not possible
	 * in most of the cases until and unless we drive shallower queue
	 * depths and that becomes a performance bottleneck. In such cases
	 * switch to start providing fairness in terms of number of IOs.
	 */
	if (!cfqd->cfq_slice_idle && cfqd->hw_tag)
		return true;
	else
		return false;
}

821
static inline enum wl_class_t cfqq_class(struct cfq_queue *cfqq)
822 823 824 825 826 827 828 829
{
	if (cfq_class_idle(cfqq))
		return IDLE_WORKLOAD;
	if (cfq_class_rt(cfqq))
		return RT_WORKLOAD;
	return BE_WORKLOAD;
}

830 831 832 833 834 835 836 837 838 839

static enum wl_type_t cfqq_type(struct cfq_queue *cfqq)
{
	if (!cfq_cfqq_sync(cfqq))
		return ASYNC_WORKLOAD;
	if (!cfq_cfqq_idle_window(cfqq))
		return SYNC_NOIDLE_WORKLOAD;
	return SYNC_WORKLOAD;
}

840
static inline int cfq_group_busy_queues_wl(enum wl_class_t wl_class,
841 842
					struct cfq_data *cfqd,
					struct cfq_group *cfqg)
843
{
844
	if (wl_class == IDLE_WORKLOAD)
845
		return cfqg->service_tree_idle.count;
846

847 848 849
	return cfqg->service_trees[wl_class][ASYNC_WORKLOAD].count +
		cfqg->service_trees[wl_class][SYNC_NOIDLE_WORKLOAD].count +
		cfqg->service_trees[wl_class][SYNC_WORKLOAD].count;
850 851
}

852 853 854
static inline int cfqg_busy_async_queues(struct cfq_data *cfqd,
					struct cfq_group *cfqg)
{
855 856
	return cfqg->service_trees[RT_WORKLOAD][ASYNC_WORKLOAD].count +
		cfqg->service_trees[BE_WORKLOAD][ASYNC_WORKLOAD].count;
857 858
}

859
static void cfq_dispatch_insert(struct request_queue *, struct request *);
860
static struct cfq_queue *cfq_get_queue(struct cfq_data *cfqd, bool is_sync,
861
				       struct cfq_io_cq *cic, struct bio *bio,
862
				       gfp_t gfp_mask);
863

864 865 866 867 868 869
static inline struct cfq_io_cq *icq_to_cic(struct io_cq *icq)
{
	/* cic->icq is the first member, %NULL will convert to %NULL */
	return container_of(icq, struct cfq_io_cq, icq);
}

870 871 872 873 874 875 876 877
static inline struct cfq_io_cq *cfq_cic_lookup(struct cfq_data *cfqd,
					       struct io_context *ioc)
{
	if (ioc)
		return icq_to_cic(ioc_lookup_icq(ioc, cfqd->queue));
	return NULL;
}

878
static inline struct cfq_queue *cic_to_cfqq(struct cfq_io_cq *cic, bool is_sync)
879
{
880
	return cic->cfqq[is_sync];
881 882
}

883 884
static inline void cic_set_cfqq(struct cfq_io_cq *cic, struct cfq_queue *cfqq,
				bool is_sync)
885
{
886
	cic->cfqq[is_sync] = cfqq;
887 888
}

889
static inline struct cfq_data *cic_to_cfqd(struct cfq_io_cq *cic)
890
{
891
	return cic->icq.q->elevator->elevator_data;
892 893
}

894 895 896 897
/*
 * 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).
 */
898
static inline bool cfq_bio_sync(struct bio *bio)
899
{
900
	return bio_data_dir(bio) == READ || (bio->bi_rw & REQ_SYNC);
901
}
L
Linus Torvalds 已提交
902

A
Andrew Morton 已提交
903 904 905 906
/*
 * scheduler run of queue, if there are requests pending and no one in the
 * driver that will restart queueing
 */
907
static inline void cfq_schedule_dispatch(struct cfq_data *cfqd)
A
Andrew Morton 已提交
908
{
909 910
	if (cfqd->busy_queues) {
		cfq_log(cfqd, "schedule dispatch");
911
		kblockd_schedule_work(&cfqd->unplug_work);
912
	}
A
Andrew Morton 已提交
913 914
}

915 916 917 918 919
/*
 * 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.
 */
920
static inline int cfq_prio_slice(struct cfq_data *cfqd, bool sync,
921
				 unsigned short prio)
922
{
923
	const int base_slice = cfqd->cfq_slice[sync];
924

925 926 927 928
	WARN_ON(prio >= IOPRIO_BE_NR);

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

930 931 932 933
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);
934 935
}

936 937 938 939 940 941 942 943 944 945 946 947 948 949
/**
 * cfqg_scale_charge - scale disk time charge according to cfqg weight
 * @charge: disk time being charged
 * @vfraction: vfraction of the cfqg, fixed point w/ CFQ_SERVICE_SHIFT
 *
 * Scale @charge according to @vfraction, which is in range (0, 1].  The
 * scaling is inversely proportional.
 *
 * scaled = charge / vfraction
 *
 * The result is also in fixed point w/ CFQ_SERVICE_SHIFT.
 */
static inline u64 cfqg_scale_charge(unsigned long charge,
				    unsigned int vfraction)
950
{
951
	u64 c = charge << CFQ_SERVICE_SHIFT;	/* make it fixed point */
952

953 954 955 956
	/* charge / vfraction */
	c <<= CFQ_SERVICE_SHIFT;
	do_div(c, vfraction);
	return c;
957 958 959 960 961 962 963 964 965 966 967 968 969 970 971 972 973 974 975 976 977 978 979 980 981 982
}

static inline u64 max_vdisktime(u64 min_vdisktime, u64 vdisktime)
{
	s64 delta = (s64)(vdisktime - min_vdisktime);
	if (delta > 0)
		min_vdisktime = vdisktime;

	return min_vdisktime;
}

static inline u64 min_vdisktime(u64 min_vdisktime, u64 vdisktime)
{
	s64 delta = (s64)(vdisktime - min_vdisktime);
	if (delta < 0)
		min_vdisktime = vdisktime;

	return min_vdisktime;
}

static void update_min_vdisktime(struct cfq_rb_root *st)
{
	struct cfq_group *cfqg;

	if (st->left) {
		cfqg = rb_entry_cfqg(st->left);
983 984
		st->min_vdisktime = max_vdisktime(st->min_vdisktime,
						  cfqg->vdisktime);
985 986 987
	}
}

988 989 990 991 992 993
/*
 * get averaged number of queues of RT/BE priority.
 * average is updated, with a formula that gives more weight to higher numbers,
 * to quickly follows sudden increases and decrease slowly
 */

994 995
static inline unsigned cfq_group_get_avg_queues(struct cfq_data *cfqd,
					struct cfq_group *cfqg, bool rt)
996
{
997 998 999
	unsigned min_q, max_q;
	unsigned mult  = cfq_hist_divisor - 1;
	unsigned round = cfq_hist_divisor / 2;
1000
	unsigned busy = cfq_group_busy_queues_wl(rt, cfqd, cfqg);
1001

1002 1003 1004
	min_q = min(cfqg->busy_queues_avg[rt], busy);
	max_q = max(cfqg->busy_queues_avg[rt], busy);
	cfqg->busy_queues_avg[rt] = (mult * max_q + min_q + round) /
1005
		cfq_hist_divisor;
1006 1007 1008 1009 1010 1011
	return cfqg->busy_queues_avg[rt];
}

static inline unsigned
cfq_group_slice(struct cfq_data *cfqd, struct cfq_group *cfqg)
{
1012
	return cfqd->cfq_target_latency * cfqg->vfraction >> CFQ_SERVICE_SHIFT;
1013 1014
}

1015
static inline unsigned
1016
cfq_scaled_cfqq_slice(struct cfq_data *cfqd, struct cfq_queue *cfqq)
1017
{
1018 1019
	unsigned slice = cfq_prio_to_slice(cfqd, cfqq);
	if (cfqd->cfq_latency) {
1020 1021 1022 1023 1024 1025
		/*
		 * interested queues (we consider only the ones with the same
		 * priority class in the cfq group)
		 */
		unsigned iq = cfq_group_get_avg_queues(cfqd, cfqq->cfqg,
						cfq_class_rt(cfqq));
1026 1027
		unsigned sync_slice = cfqd->cfq_slice[1];
		unsigned expect_latency = sync_slice * iq;
1028 1029 1030
		unsigned group_slice = cfq_group_slice(cfqd, cfqq->cfqg);

		if (expect_latency > group_slice) {
1031 1032 1033 1034 1035 1036 1037
			unsigned base_low_slice = 2 * cfqd->cfq_slice_idle;
			/* scale low_slice according to IO priority
			 * and sync vs async */
			unsigned low_slice =
				min(slice, base_low_slice * slice / sync_slice);
			/* the adapted slice value is scaled to fit all iqs
			 * into the target latency */
1038
			slice = max(slice * group_slice / expect_latency,
1039 1040 1041
				    low_slice);
		}
	}
1042 1043 1044 1045 1046 1047
	return slice;
}

static inline void
cfq_set_prio_slice(struct cfq_data *cfqd, struct cfq_queue *cfqq)
{
1048
	unsigned slice = cfq_scaled_cfqq_slice(cfqd, cfqq);
1049

1050
	cfqq->slice_start = jiffies;
1051
	cfqq->slice_end = jiffies + slice;
1052
	cfqq->allocated_slice = slice;
1053
	cfq_log_cfqq(cfqd, cfqq, "set_slice=%lu", cfqq->slice_end - jiffies);
1054 1055 1056 1057 1058 1059 1060
}

/*
 * 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.
 */
1061
static inline bool cfq_slice_used(struct cfq_queue *cfqq)
1062 1063
{
	if (cfq_cfqq_slice_new(cfqq))
S
Shaohua Li 已提交
1064
		return false;
1065
	if (time_before(jiffies, cfqq->slice_end))
S
Shaohua Li 已提交
1066
		return false;
1067

S
Shaohua Li 已提交
1068
	return true;
1069 1070
}

L
Linus Torvalds 已提交
1071
/*
J
Jens Axboe 已提交
1072
 * Lifted from AS - choose which of rq1 and rq2 that is best served now.
L
Linus Torvalds 已提交
1073
 * We choose the request that is closest to the head right now. Distance
1074
 * behind the head is penalized and only allowed to a certain extent.
L
Linus Torvalds 已提交
1075
 */
J
Jens Axboe 已提交
1076
static struct request *
1077
cfq_choose_req(struct cfq_data *cfqd, struct request *rq1, struct request *rq2, sector_t last)
L
Linus Torvalds 已提交
1078
{
1079
	sector_t s1, s2, d1 = 0, d2 = 0;
L
Linus Torvalds 已提交
1080
	unsigned long back_max;
1081 1082 1083
#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 已提交
1084

J
Jens Axboe 已提交
1085 1086 1087 1088
	if (rq1 == NULL || rq1 == rq2)
		return rq2;
	if (rq2 == NULL)
		return rq1;
J
Jens Axboe 已提交
1089

1090 1091 1092
	if (rq_is_sync(rq1) != rq_is_sync(rq2))
		return rq_is_sync(rq1) ? rq1 : rq2;

1093 1094
	if ((rq1->cmd_flags ^ rq2->cmd_flags) & REQ_PRIO)
		return rq1->cmd_flags & REQ_PRIO ? rq1 : rq2;
1095

1096 1097
	s1 = blk_rq_pos(rq1);
	s2 = blk_rq_pos(rq2);
L
Linus Torvalds 已提交
1098 1099 1100 1101 1102 1103 1104 1105 1106 1107 1108 1109 1110 1111 1112 1113

	/*
	 * 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
1114
		wrap |= CFQ_RQ1_WRAP;
L
Linus Torvalds 已提交
1115 1116 1117 1118 1119 1120

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

	/* Found required data */
1124 1125 1126 1127 1128 1129

	/*
	 * By doing switch() on the bit mask "wrap" we avoid having to
	 * check two variables for all permutations: --> faster!
	 */
	switch (wrap) {
J
Jens Axboe 已提交
1130
	case 0: /* common case for CFQ: rq1 and rq2 not wrapped */
1131
		if (d1 < d2)
J
Jens Axboe 已提交
1132
			return rq1;
1133
		else if (d2 < d1)
J
Jens Axboe 已提交
1134
			return rq2;
1135 1136
		else {
			if (s1 >= s2)
J
Jens Axboe 已提交
1137
				return rq1;
1138
			else
J
Jens Axboe 已提交
1139
				return rq2;
1140
		}
L
Linus Torvalds 已提交
1141

1142
	case CFQ_RQ2_WRAP:
J
Jens Axboe 已提交
1143
		return rq1;
1144
	case CFQ_RQ1_WRAP:
J
Jens Axboe 已提交
1145 1146
		return rq2;
	case (CFQ_RQ1_WRAP|CFQ_RQ2_WRAP): /* both rqs wrapped */
1147 1148 1149 1150 1151 1152 1153 1154
	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 已提交
1155
			return rq1;
L
Linus Torvalds 已提交
1156
		else
J
Jens Axboe 已提交
1157
			return rq2;
L
Linus Torvalds 已提交
1158 1159 1160
	}
}

1161 1162 1163
/*
 * The below is leftmost cache rbtree addon
 */
1164
static struct cfq_queue *cfq_rb_first(struct cfq_rb_root *root)
1165
{
1166 1167 1168 1169
	/* Service tree is empty */
	if (!root->count)
		return NULL;

1170 1171 1172
	if (!root->left)
		root->left = rb_first(&root->rb);

1173 1174 1175 1176
	if (root->left)
		return rb_entry(root->left, struct cfq_queue, rb_node);

	return NULL;
1177 1178
}

1179 1180 1181 1182 1183 1184 1185 1186 1187 1188 1189
static struct cfq_group *cfq_rb_first_group(struct cfq_rb_root *root)
{
	if (!root->left)
		root->left = rb_first(&root->rb);

	if (root->left)
		return rb_entry_cfqg(root->left);

	return NULL;
}

1190 1191 1192 1193 1194 1195
static void rb_erase_init(struct rb_node *n, struct rb_root *root)
{
	rb_erase(n, root);
	RB_CLEAR_NODE(n);
}

1196 1197 1198 1199
static void cfq_rb_erase(struct rb_node *n, struct cfq_rb_root *root)
{
	if (root->left == n)
		root->left = NULL;
1200
	rb_erase_init(n, &root->rb);
1201
	--root->count;
1202 1203
}

L
Linus Torvalds 已提交
1204 1205 1206
/*
 * would be nice to take fifo expire time into account as well
 */
J
Jens Axboe 已提交
1207 1208 1209
static struct request *
cfq_find_next_rq(struct cfq_data *cfqd, struct cfq_queue *cfqq,
		  struct request *last)
L
Linus Torvalds 已提交
1210
{
1211 1212
	struct rb_node *rbnext = rb_next(&last->rb_node);
	struct rb_node *rbprev = rb_prev(&last->rb_node);
J
Jens Axboe 已提交
1213
	struct request *next = NULL, *prev = NULL;
L
Linus Torvalds 已提交
1214

1215
	BUG_ON(RB_EMPTY_NODE(&last->rb_node));
L
Linus Torvalds 已提交
1216 1217

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

1220
	if (rbnext)
J
Jens Axboe 已提交
1221
		next = rb_entry_rq(rbnext);
1222 1223 1224
	else {
		rbnext = rb_first(&cfqq->sort_list);
		if (rbnext && rbnext != &last->rb_node)
J
Jens Axboe 已提交
1225
			next = rb_entry_rq(rbnext);
1226
	}
L
Linus Torvalds 已提交
1227

1228
	return cfq_choose_req(cfqd, next, prev, blk_rq_pos(last));
L
Linus Torvalds 已提交
1229 1230
}

1231 1232
static unsigned long cfq_slice_offset(struct cfq_data *cfqd,
				      struct cfq_queue *cfqq)
L
Linus Torvalds 已提交
1233
{
1234 1235 1236
	/*
	 * just an approximation, should be ok.
	 */
1237
	return (cfqq->cfqg->nr_cfqq - 1) * (cfq_prio_slice(cfqd, 1, 0) -
1238
		       cfq_prio_slice(cfqd, cfq_cfqq_sync(cfqq), cfqq->ioprio));
1239 1240
}

1241 1242 1243 1244 1245 1246 1247 1248 1249 1250 1251 1252 1253 1254 1255 1256 1257 1258 1259 1260 1261 1262 1263 1264 1265 1266 1267 1268 1269 1270 1271 1272 1273 1274
static inline s64
cfqg_key(struct cfq_rb_root *st, struct cfq_group *cfqg)
{
	return cfqg->vdisktime - st->min_vdisktime;
}

static void
__cfq_group_service_tree_add(struct cfq_rb_root *st, struct cfq_group *cfqg)
{
	struct rb_node **node = &st->rb.rb_node;
	struct rb_node *parent = NULL;
	struct cfq_group *__cfqg;
	s64 key = cfqg_key(st, cfqg);
	int left = 1;

	while (*node != NULL) {
		parent = *node;
		__cfqg = rb_entry_cfqg(parent);

		if (key < cfqg_key(st, __cfqg))
			node = &parent->rb_left;
		else {
			node = &parent->rb_right;
			left = 0;
		}
	}

	if (left)
		st->left = &cfqg->rb_node;

	rb_link_node(&cfqg->rb_node, parent, node);
	rb_insert_color(&cfqg->rb_node, &st->rb);
}

1275 1276 1277
/*
 * This has to be called only on activation of cfqg
 */
1278
static void
1279 1280
cfq_update_group_weight(struct cfq_group *cfqg)
{
1281
	if (cfqg->new_weight) {
1282
		cfqg->weight = cfqg->new_weight;
1283
		cfqg->new_weight = 0;
1284
	}
1285 1286 1287 1288 1289 1290
}

static void
cfq_update_group_leaf_weight(struct cfq_group *cfqg)
{
	BUG_ON(!RB_EMPTY_NODE(&cfqg->rb_node));
T
Tejun Heo 已提交
1291 1292 1293 1294 1295

	if (cfqg->new_leaf_weight) {
		cfqg->leaf_weight = cfqg->new_leaf_weight;
		cfqg->new_leaf_weight = 0;
	}
1296 1297 1298 1299 1300
}

static void
cfq_group_service_tree_add(struct cfq_rb_root *st, struct cfq_group *cfqg)
{
1301
	unsigned int vfr = 1 << CFQ_SERVICE_SHIFT;	/* start with 1 */
1302
	struct cfq_group *pos = cfqg;
1303
	struct cfq_group *parent;
1304 1305 1306
	bool propagate;

	/* add to the service tree */
1307 1308
	BUG_ON(!RB_EMPTY_NODE(&cfqg->rb_node));

1309 1310 1311 1312 1313
	/*
	 * Update leaf_weight.  We cannot update weight at this point
	 * because cfqg might already have been activated and is
	 * contributing its current weight to the parent's child_weight.
	 */
1314
	cfq_update_group_leaf_weight(cfqg);
1315
	__cfq_group_service_tree_add(st, cfqg);
1316 1317

	/*
1318 1319 1320 1321 1322 1323 1324
	 * Activate @cfqg and calculate the portion of vfraction @cfqg is
	 * entitled to.  vfraction is calculated by walking the tree
	 * towards the root calculating the fraction it has at each level.
	 * The compounded ratio is how much vfraction @cfqg owns.
	 *
	 * Start with the proportion tasks in this cfqg has against active
	 * children cfqgs - its leaf_weight against children_weight.
1325 1326 1327
	 */
	propagate = !pos->nr_active++;
	pos->children_weight += pos->leaf_weight;
1328
	vfr = vfr * pos->leaf_weight / pos->children_weight;
1329

1330 1331 1332 1333 1334 1335
	/*
	 * Compound ->weight walking up the tree.  Both activation and
	 * vfraction calculation are done in the same loop.  Propagation
	 * stops once an already activated node is met.  vfraction
	 * calculation should always continue to the root.
	 */
1336
	while ((parent = cfqg_parent(pos))) {
1337
		if (propagate) {
1338
			cfq_update_group_weight(pos);
1339 1340 1341 1342
			propagate = !parent->nr_active++;
			parent->children_weight += pos->weight;
		}
		vfr = vfr * pos->weight / parent->children_weight;
1343 1344
		pos = parent;
	}
1345 1346

	cfqg->vfraction = max_t(unsigned, vfr, 1);
1347 1348 1349 1350
}

static void
cfq_group_notify_queue_add(struct cfq_data *cfqd, struct cfq_group *cfqg)
1351 1352 1353 1354 1355 1356
{
	struct cfq_rb_root *st = &cfqd->grp_service_tree;
	struct cfq_group *__cfqg;
	struct rb_node *n;

	cfqg->nr_cfqq++;
G
Gui Jianfeng 已提交
1357
	if (!RB_EMPTY_NODE(&cfqg->rb_node))
1358 1359 1360 1361 1362
		return;

	/*
	 * Currently put the group at the end. Later implement something
	 * so that groups get lesser vtime based on their weights, so that
L
Lucas De Marchi 已提交
1363
	 * if group does not loose all if it was not continuously backlogged.
1364 1365 1366 1367 1368 1369 1370
	 */
	n = rb_last(&st->rb);
	if (n) {
		__cfqg = rb_entry_cfqg(n);
		cfqg->vdisktime = __cfqg->vdisktime + CFQ_IDLE_DELAY;
	} else
		cfqg->vdisktime = st->min_vdisktime;
1371 1372
	cfq_group_service_tree_add(st, cfqg);
}
1373

1374 1375 1376
static void
cfq_group_service_tree_del(struct cfq_rb_root *st, struct cfq_group *cfqg)
{
1377 1378 1379 1380 1381 1382 1383 1384 1385 1386 1387
	struct cfq_group *pos = cfqg;
	bool propagate;

	/*
	 * Undo activation from cfq_group_service_tree_add().  Deactivate
	 * @cfqg and propagate deactivation upwards.
	 */
	propagate = !--pos->nr_active;
	pos->children_weight -= pos->leaf_weight;

	while (propagate) {
1388
		struct cfq_group *parent = cfqg_parent(pos);
1389 1390 1391

		/* @pos has 0 nr_active at this point */
		WARN_ON_ONCE(pos->children_weight);
1392
		pos->vfraction = 0;
1393 1394 1395 1396 1397 1398 1399 1400 1401 1402

		if (!parent)
			break;

		propagate = !--parent->nr_active;
		parent->children_weight -= pos->weight;
		pos = parent;
	}

	/* remove from the service tree */
1403 1404
	if (!RB_EMPTY_NODE(&cfqg->rb_node))
		cfq_rb_erase(&cfqg->rb_node, st);
1405 1406 1407
}

static void
1408
cfq_group_notify_queue_del(struct cfq_data *cfqd, struct cfq_group *cfqg)
1409 1410 1411 1412 1413
{
	struct cfq_rb_root *st = &cfqd->grp_service_tree;

	BUG_ON(cfqg->nr_cfqq < 1);
	cfqg->nr_cfqq--;
1414

1415 1416 1417 1418
	/* If there are other cfq queues under this group, don't delete it */
	if (cfqg->nr_cfqq)
		return;

V
Vivek Goyal 已提交
1419
	cfq_log_cfqg(cfqd, cfqg, "del_from_rr group");
1420
	cfq_group_service_tree_del(st, cfqg);
1421
	cfqg->saved_wl_slice = 0;
1422
	cfqg_stats_update_dequeue(cfqg);
1423 1424
}

1425 1426
static inline unsigned int cfq_cfqq_slice_usage(struct cfq_queue *cfqq,
						unsigned int *unaccounted_time)
1427
{
1428
	unsigned int slice_used;
1429 1430 1431 1432 1433 1434 1435 1436 1437 1438 1439 1440 1441 1442 1443 1444

	/*
	 * Queue got expired before even a single request completed or
	 * got expired immediately after first request completion.
	 */
	if (!cfqq->slice_start || cfqq->slice_start == jiffies) {
		/*
		 * Also charge the seek time incurred to the group, otherwise
		 * if there are mutiple queues in the group, each can dispatch
		 * a single request on seeky media and cause lots of seek time
		 * and group will never know it.
		 */
		slice_used = max_t(unsigned, (jiffies - cfqq->dispatch_start),
					1);
	} else {
		slice_used = jiffies - cfqq->slice_start;
1445 1446
		if (slice_used > cfqq->allocated_slice) {
			*unaccounted_time = slice_used - cfqq->allocated_slice;
1447
			slice_used = cfqq->allocated_slice;
1448 1449 1450 1451
		}
		if (time_after(cfqq->slice_start, cfqq->dispatch_start))
			*unaccounted_time += cfqq->slice_start -
					cfqq->dispatch_start;
1452 1453 1454 1455 1456 1457
	}

	return slice_used;
}

static void cfq_group_served(struct cfq_data *cfqd, struct cfq_group *cfqg,
1458
				struct cfq_queue *cfqq)
1459 1460
{
	struct cfq_rb_root *st = &cfqd->grp_service_tree;
1461
	unsigned int used_sl, charge, unaccounted_sl = 0;
1462 1463
	int nr_sync = cfqg->nr_cfqq - cfqg_busy_async_queues(cfqd, cfqg)
			- cfqg->service_tree_idle.count;
1464
	unsigned int vfr;
1465 1466

	BUG_ON(nr_sync < 0);
1467
	used_sl = charge = cfq_cfqq_slice_usage(cfqq, &unaccounted_sl);
1468

1469 1470 1471 1472
	if (iops_mode(cfqd))
		charge = cfqq->slice_dispatch;
	else if (!cfq_cfqq_sync(cfqq) && !nr_sync)
		charge = cfqq->allocated_slice;
1473

1474 1475 1476 1477 1478 1479 1480
	/*
	 * Can't update vdisktime while on service tree and cfqg->vfraction
	 * is valid only while on it.  Cache vfr, leave the service tree,
	 * update vdisktime and go back on.  The re-addition to the tree
	 * will also update the weights as necessary.
	 */
	vfr = cfqg->vfraction;
1481
	cfq_group_service_tree_del(st, cfqg);
1482
	cfqg->vdisktime += cfqg_scale_charge(charge, vfr);
1483
	cfq_group_service_tree_add(st, cfqg);
1484 1485 1486

	/* This group is being expired. Save the context */
	if (time_after(cfqd->workload_expires, jiffies)) {
1487
		cfqg->saved_wl_slice = cfqd->workload_expires
1488
						- jiffies;
1489 1490
		cfqg->saved_wl_type = cfqd->serving_wl_type;
		cfqg->saved_wl_class = cfqd->serving_wl_class;
1491
	} else
1492
		cfqg->saved_wl_slice = 0;
V
Vivek Goyal 已提交
1493 1494 1495

	cfq_log_cfqg(cfqd, cfqg, "served: vt=%llu min_vt=%llu", cfqg->vdisktime,
					st->min_vdisktime);
1496 1497 1498 1499
	cfq_log_cfqq(cfqq->cfqd, cfqq,
		     "sl_used=%u disp=%u charge=%u iops=%u sect=%lu",
		     used_sl, cfqq->slice_dispatch, charge,
		     iops_mode(cfqd), cfqq->nr_sectors);
1500 1501
	cfqg_stats_update_timeslice_used(cfqg, used_sl, unaccounted_sl);
	cfqg_stats_set_start_empty_time(cfqg);
1502 1503
}

1504 1505 1506 1507 1508 1509 1510 1511 1512 1513 1514 1515 1516 1517 1518 1519 1520 1521 1522
/**
 * cfq_init_cfqg_base - initialize base part of a cfq_group
 * @cfqg: cfq_group to initialize
 *
 * Initialize the base part which is used whether %CONFIG_CFQ_GROUP_IOSCHED
 * is enabled or not.
 */
static void cfq_init_cfqg_base(struct cfq_group *cfqg)
{
	struct cfq_rb_root *st;
	int i, j;

	for_each_cfqg_st(cfqg, i, j, st)
		*st = CFQ_RB_ROOT;
	RB_CLEAR_NODE(&cfqg->rb_node);

	cfqg->ttime.last_end_request = jiffies;
}

1523
#ifdef CONFIG_CFQ_GROUP_IOSCHED
1524 1525 1526 1527 1528 1529 1530 1531 1532 1533 1534 1535 1536 1537 1538 1539 1540 1541 1542 1543 1544 1545 1546
static void cfqg_stats_init(struct cfqg_stats *stats)
{
	blkg_rwstat_init(&stats->service_bytes);
	blkg_rwstat_init(&stats->serviced);
	blkg_rwstat_init(&stats->merged);
	blkg_rwstat_init(&stats->service_time);
	blkg_rwstat_init(&stats->wait_time);
	blkg_rwstat_init(&stats->queued);

	blkg_stat_init(&stats->sectors);
	blkg_stat_init(&stats->time);

#ifdef CONFIG_DEBUG_BLK_CGROUP
	blkg_stat_init(&stats->unaccounted_time);
	blkg_stat_init(&stats->avg_queue_size_sum);
	blkg_stat_init(&stats->avg_queue_size_samples);
	blkg_stat_init(&stats->dequeue);
	blkg_stat_init(&stats->group_wait_time);
	blkg_stat_init(&stats->idle_time);
	blkg_stat_init(&stats->empty_time);
#endif
}

T
Tejun Heo 已提交
1547
static void cfq_pd_init(struct blkcg_gq *blkg)
1548
{
1549
	struct cfq_group *cfqg = blkg_to_cfqg(blkg);
1550

1551
	cfq_init_cfqg_base(cfqg);
1552
	cfqg->weight = blkg->blkcg->cfq_weight;
T
Tejun Heo 已提交
1553
	cfqg->leaf_weight = blkg->blkcg->cfq_leaf_weight;
1554 1555
	cfqg_stats_init(&cfqg->stats);
	cfqg_stats_init(&cfqg->dead_stats);
1556 1557
}

1558 1559 1560 1561 1562 1563 1564 1565 1566 1567 1568
static void cfq_pd_offline(struct blkcg_gq *blkg)
{
	/*
	 * @blkg is going offline and will be ignored by
	 * blkg_[rw]stat_recursive_sum().  Transfer stats to the parent so
	 * that they don't get lost.  If IOs complete after this point, the
	 * stats for them will be lost.  Oh well...
	 */
	cfqg_stats_xfer_dead(blkg_to_cfqg(blkg));
}

1569 1570 1571 1572 1573 1574 1575 1576 1577 1578 1579 1580 1581 1582 1583 1584 1585 1586 1587 1588 1589 1590 1591 1592 1593 1594
/* offset delta from cfqg->stats to cfqg->dead_stats */
static const int dead_stats_off_delta = offsetof(struct cfq_group, dead_stats) -
					offsetof(struct cfq_group, stats);

/* to be used by recursive prfill, sums live and dead stats recursively */
static u64 cfqg_stat_pd_recursive_sum(struct blkg_policy_data *pd, int off)
{
	u64 sum = 0;

	sum += blkg_stat_recursive_sum(pd, off);
	sum += blkg_stat_recursive_sum(pd, off + dead_stats_off_delta);
	return sum;
}

/* to be used by recursive prfill, sums live and dead rwstats recursively */
static struct blkg_rwstat cfqg_rwstat_pd_recursive_sum(struct blkg_policy_data *pd,
						       int off)
{
	struct blkg_rwstat a, b;

	a = blkg_rwstat_recursive_sum(pd, off);
	b = blkg_rwstat_recursive_sum(pd, off + dead_stats_off_delta);
	blkg_rwstat_merge(&a, &b);
	return a;
}

1595 1596 1597 1598 1599
static void cfq_pd_reset_stats(struct blkcg_gq *blkg)
{
	struct cfq_group *cfqg = blkg_to_cfqg(blkg);

	cfqg_stats_reset(&cfqg->stats);
1600
	cfqg_stats_reset(&cfqg->dead_stats);
1601 1602 1603
}

/*
1604 1605
 * Search for the cfq group current task belongs to. request_queue lock must
 * be held.
1606
 */
1607
static struct cfq_group *cfq_lookup_create_cfqg(struct cfq_data *cfqd,
T
Tejun Heo 已提交
1608
						struct blkcg *blkcg)
1609
{
1610
	struct request_queue *q = cfqd->queue;
1611
	struct cfq_group *cfqg = NULL;
1612

T
Tejun Heo 已提交
1613 1614
	/* avoid lookup for the common case where there's no blkcg */
	if (blkcg == &blkcg_root) {
1615 1616
		cfqg = cfqd->root_group;
	} else {
T
Tejun Heo 已提交
1617
		struct blkcg_gq *blkg;
1618

1619
		blkg = blkg_lookup_create(blkcg, q);
1620
		if (!IS_ERR(blkg))
1621
			cfqg = blkg_to_cfqg(blkg);
1622
	}
1623

1624 1625 1626 1627 1628 1629 1630
	return cfqg;
}

static void cfq_link_cfqq_cfqg(struct cfq_queue *cfqq, struct cfq_group *cfqg)
{
	/* Currently, all async queues are mapped to root group */
	if (!cfq_cfqq_sync(cfqq))
1631
		cfqg = cfqq->cfqd->root_group;
1632 1633

	cfqq->cfqg = cfqg;
1634
	/* cfqq reference on cfqg */
1635
	cfqg_get(cfqg);
1636 1637
}

1638 1639
static u64 cfqg_prfill_weight_device(struct seq_file *sf,
				     struct blkg_policy_data *pd, int off)
1640
{
1641
	struct cfq_group *cfqg = pd_to_cfqg(pd);
1642 1643

	if (!cfqg->dev_weight)
1644
		return 0;
1645
	return __blkg_prfill_u64(sf, pd, cfqg->dev_weight);
1646 1647
}

1648
static int cfqg_print_weight_device(struct seq_file *sf, void *v)
1649
{
1650 1651 1652
	blkcg_print_blkgs(sf, css_to_blkcg(seq_css(sf)),
			  cfqg_prfill_weight_device, &blkcg_policy_cfq,
			  0, false);
1653 1654 1655
	return 0;
}

T
Tejun Heo 已提交
1656 1657 1658 1659 1660 1661 1662 1663 1664 1665
static u64 cfqg_prfill_leaf_weight_device(struct seq_file *sf,
					  struct blkg_policy_data *pd, int off)
{
	struct cfq_group *cfqg = pd_to_cfqg(pd);

	if (!cfqg->dev_leaf_weight)
		return 0;
	return __blkg_prfill_u64(sf, pd, cfqg->dev_leaf_weight);
}

1666
static int cfqg_print_leaf_weight_device(struct seq_file *sf, void *v)
T
Tejun Heo 已提交
1667
{
1668 1669 1670
	blkcg_print_blkgs(sf, css_to_blkcg(seq_css(sf)),
			  cfqg_prfill_leaf_weight_device, &blkcg_policy_cfq,
			  0, false);
T
Tejun Heo 已提交
1671 1672 1673
	return 0;
}

1674
static int cfq_print_weight(struct seq_file *sf, void *v)
1675
{
1676
	seq_printf(sf, "%u\n", css_to_blkcg(seq_css(sf))->cfq_weight);
1677 1678 1679
	return 0;
}

1680
static int cfq_print_leaf_weight(struct seq_file *sf, void *v)
T
Tejun Heo 已提交
1681
{
1682
	seq_printf(sf, "%u\n", css_to_blkcg(seq_css(sf))->cfq_leaf_weight);
T
Tejun Heo 已提交
1683 1684 1685
	return 0;
}

1686 1687 1688
static ssize_t __cfqg_set_weight_device(struct kernfs_open_file *of,
					char *buf, size_t nbytes, loff_t off,
					bool is_leaf_weight)
1689
{
1690
	struct blkcg *blkcg = css_to_blkcg(of_css(of));
1691
	struct blkg_conf_ctx ctx;
1692
	struct cfq_group *cfqg;
1693 1694
	int ret;

T
Tejun Heo 已提交
1695
	ret = blkg_conf_prep(blkcg, &blkcg_policy_cfq, buf, &ctx);
1696 1697 1698 1699
	if (ret)
		return ret;

	ret = -EINVAL;
1700
	cfqg = blkg_to_cfqg(ctx.blkg);
1701
	if (!ctx.v || (ctx.v >= CFQ_WEIGHT_MIN && ctx.v <= CFQ_WEIGHT_MAX)) {
T
Tejun Heo 已提交
1702 1703 1704 1705 1706 1707 1708
		if (!is_leaf_weight) {
			cfqg->dev_weight = ctx.v;
			cfqg->new_weight = ctx.v ?: blkcg->cfq_weight;
		} else {
			cfqg->dev_leaf_weight = ctx.v;
			cfqg->new_leaf_weight = ctx.v ?: blkcg->cfq_leaf_weight;
		}
1709 1710 1711 1712
		ret = 0;
	}

	blkg_conf_finish(&ctx);
1713
	return ret ?: nbytes;
1714 1715
}

1716 1717
static ssize_t cfqg_set_weight_device(struct kernfs_open_file *of,
				      char *buf, size_t nbytes, loff_t off)
T
Tejun Heo 已提交
1718
{
1719
	return __cfqg_set_weight_device(of, buf, nbytes, off, false);
T
Tejun Heo 已提交
1720 1721
}

1722 1723
static ssize_t cfqg_set_leaf_weight_device(struct kernfs_open_file *of,
					   char *buf, size_t nbytes, loff_t off)
T
Tejun Heo 已提交
1724
{
1725
	return __cfqg_set_weight_device(of, buf, nbytes, off, true);
T
Tejun Heo 已提交
1726 1727
}

1728 1729
static int __cfq_set_weight(struct cgroup_subsys_state *css, struct cftype *cft,
			    u64 val, bool is_leaf_weight)
1730
{
1731
	struct blkcg *blkcg = css_to_blkcg(css);
T
Tejun Heo 已提交
1732
	struct blkcg_gq *blkg;
1733

1734
	if (val < CFQ_WEIGHT_MIN || val > CFQ_WEIGHT_MAX)
1735 1736 1737
		return -EINVAL;

	spin_lock_irq(&blkcg->lock);
T
Tejun Heo 已提交
1738 1739 1740 1741 1742

	if (!is_leaf_weight)
		blkcg->cfq_weight = val;
	else
		blkcg->cfq_leaf_weight = val;
1743

1744
	hlist_for_each_entry(blkg, &blkcg->blkg_list, blkcg_node) {
1745
		struct cfq_group *cfqg = blkg_to_cfqg(blkg);
1746

T
Tejun Heo 已提交
1747 1748 1749 1750 1751 1752 1753 1754 1755 1756
		if (!cfqg)
			continue;

		if (!is_leaf_weight) {
			if (!cfqg->dev_weight)
				cfqg->new_weight = blkcg->cfq_weight;
		} else {
			if (!cfqg->dev_leaf_weight)
				cfqg->new_leaf_weight = blkcg->cfq_leaf_weight;
		}
1757 1758 1759 1760 1761 1762
	}

	spin_unlock_irq(&blkcg->lock);
	return 0;
}

1763 1764
static int cfq_set_weight(struct cgroup_subsys_state *css, struct cftype *cft,
			  u64 val)
T
Tejun Heo 已提交
1765
{
1766
	return __cfq_set_weight(css, cft, val, false);
T
Tejun Heo 已提交
1767 1768
}

1769 1770
static int cfq_set_leaf_weight(struct cgroup_subsys_state *css,
			       struct cftype *cft, u64 val)
T
Tejun Heo 已提交
1771
{
1772
	return __cfq_set_weight(css, cft, val, true);
T
Tejun Heo 已提交
1773 1774
}

1775
static int cfqg_print_stat(struct seq_file *sf, void *v)
1776
{
1777 1778
	blkcg_print_blkgs(sf, css_to_blkcg(seq_css(sf)), blkg_prfill_stat,
			  &blkcg_policy_cfq, seq_cft(sf)->private, false);
1779 1780 1781
	return 0;
}

1782
static int cfqg_print_rwstat(struct seq_file *sf, void *v)
1783
{
1784 1785
	blkcg_print_blkgs(sf, css_to_blkcg(seq_css(sf)), blkg_prfill_rwstat,
			  &blkcg_policy_cfq, seq_cft(sf)->private, true);
1786 1787 1788
	return 0;
}

1789 1790 1791 1792 1793 1794 1795 1796 1797 1798 1799 1800 1801 1802 1803 1804
static u64 cfqg_prfill_stat_recursive(struct seq_file *sf,
				      struct blkg_policy_data *pd, int off)
{
	u64 sum = cfqg_stat_pd_recursive_sum(pd, off);

	return __blkg_prfill_u64(sf, pd, sum);
}

static u64 cfqg_prfill_rwstat_recursive(struct seq_file *sf,
					struct blkg_policy_data *pd, int off)
{
	struct blkg_rwstat sum = cfqg_rwstat_pd_recursive_sum(pd, off);

	return __blkg_prfill_rwstat(sf, pd, &sum);
}

1805
static int cfqg_print_stat_recursive(struct seq_file *sf, void *v)
1806
{
1807 1808 1809
	blkcg_print_blkgs(sf, css_to_blkcg(seq_css(sf)),
			  cfqg_prfill_stat_recursive, &blkcg_policy_cfq,
			  seq_cft(sf)->private, false);
1810 1811 1812
	return 0;
}

1813
static int cfqg_print_rwstat_recursive(struct seq_file *sf, void *v)
1814
{
1815 1816 1817
	blkcg_print_blkgs(sf, css_to_blkcg(seq_css(sf)),
			  cfqg_prfill_rwstat_recursive, &blkcg_policy_cfq,
			  seq_cft(sf)->private, true);
1818 1819 1820
	return 0;
}

1821
#ifdef CONFIG_DEBUG_BLK_CGROUP
1822 1823
static u64 cfqg_prfill_avg_queue_size(struct seq_file *sf,
				      struct blkg_policy_data *pd, int off)
1824
{
1825
	struct cfq_group *cfqg = pd_to_cfqg(pd);
1826
	u64 samples = blkg_stat_read(&cfqg->stats.avg_queue_size_samples);
1827 1828 1829
	u64 v = 0;

	if (samples) {
1830
		v = blkg_stat_read(&cfqg->stats.avg_queue_size_sum);
1831
		v = div64_u64(v, samples);
1832
	}
1833
	__blkg_prfill_u64(sf, pd, v);
1834 1835 1836 1837
	return 0;
}

/* print avg_queue_size */
1838
static int cfqg_print_avg_queue_size(struct seq_file *sf, void *v)
1839
{
1840 1841 1842
	blkcg_print_blkgs(sf, css_to_blkcg(seq_css(sf)),
			  cfqg_prfill_avg_queue_size, &blkcg_policy_cfq,
			  0, false);
1843 1844 1845 1846 1847
	return 0;
}
#endif	/* CONFIG_DEBUG_BLK_CGROUP */

static struct cftype cfq_blkcg_files[] = {
1848
	/* on root, weight is mapped to leaf_weight */
1849 1850
	{
		.name = "weight_device",
1851
		.flags = CFTYPE_ONLY_ON_ROOT,
1852
		.seq_show = cfqg_print_leaf_weight_device,
1853
		.write = cfqg_set_leaf_weight_device,
1854 1855 1856
	},
	{
		.name = "weight",
1857
		.flags = CFTYPE_ONLY_ON_ROOT,
1858
		.seq_show = cfq_print_leaf_weight,
1859
		.write_u64 = cfq_set_leaf_weight,
1860
	},
T
Tejun Heo 已提交
1861

1862
	/* no such mapping necessary for !roots */
1863 1864
	{
		.name = "weight_device",
1865
		.flags = CFTYPE_NOT_ON_ROOT,
1866
		.seq_show = cfqg_print_weight_device,
1867
		.write = cfqg_set_weight_device,
1868 1869 1870
	},
	{
		.name = "weight",
1871
		.flags = CFTYPE_NOT_ON_ROOT,
1872
		.seq_show = cfq_print_weight,
1873
		.write_u64 = cfq_set_weight,
1874
	},
T
Tejun Heo 已提交
1875 1876 1877

	{
		.name = "leaf_weight_device",
1878
		.seq_show = cfqg_print_leaf_weight_device,
1879
		.write = cfqg_set_leaf_weight_device,
T
Tejun Heo 已提交
1880 1881 1882
	},
	{
		.name = "leaf_weight",
1883
		.seq_show = cfq_print_leaf_weight,
T
Tejun Heo 已提交
1884 1885 1886
		.write_u64 = cfq_set_leaf_weight,
	},

1887
	/* statistics, covers only the tasks in the cfqg */
1888 1889
	{
		.name = "time",
1890
		.private = offsetof(struct cfq_group, stats.time),
1891
		.seq_show = cfqg_print_stat,
1892 1893 1894
	},
	{
		.name = "sectors",
1895
		.private = offsetof(struct cfq_group, stats.sectors),
1896
		.seq_show = cfqg_print_stat,
1897 1898 1899
	},
	{
		.name = "io_service_bytes",
1900
		.private = offsetof(struct cfq_group, stats.service_bytes),
1901
		.seq_show = cfqg_print_rwstat,
1902 1903 1904
	},
	{
		.name = "io_serviced",
1905
		.private = offsetof(struct cfq_group, stats.serviced),
1906
		.seq_show = cfqg_print_rwstat,
1907 1908 1909
	},
	{
		.name = "io_service_time",
1910
		.private = offsetof(struct cfq_group, stats.service_time),
1911
		.seq_show = cfqg_print_rwstat,
1912 1913 1914
	},
	{
		.name = "io_wait_time",
1915
		.private = offsetof(struct cfq_group, stats.wait_time),
1916
		.seq_show = cfqg_print_rwstat,
1917 1918 1919
	},
	{
		.name = "io_merged",
1920
		.private = offsetof(struct cfq_group, stats.merged),
1921
		.seq_show = cfqg_print_rwstat,
1922 1923 1924
	},
	{
		.name = "io_queued",
1925
		.private = offsetof(struct cfq_group, stats.queued),
1926
		.seq_show = cfqg_print_rwstat,
1927
	},
1928 1929 1930 1931 1932

	/* the same statictics which cover the cfqg and its descendants */
	{
		.name = "time_recursive",
		.private = offsetof(struct cfq_group, stats.time),
1933
		.seq_show = cfqg_print_stat_recursive,
1934 1935 1936 1937
	},
	{
		.name = "sectors_recursive",
		.private = offsetof(struct cfq_group, stats.sectors),
1938
		.seq_show = cfqg_print_stat_recursive,
1939 1940 1941 1942
	},
	{
		.name = "io_service_bytes_recursive",
		.private = offsetof(struct cfq_group, stats.service_bytes),
1943
		.seq_show = cfqg_print_rwstat_recursive,
1944 1945 1946 1947
	},
	{
		.name = "io_serviced_recursive",
		.private = offsetof(struct cfq_group, stats.serviced),
1948
		.seq_show = cfqg_print_rwstat_recursive,
1949 1950 1951 1952
	},
	{
		.name = "io_service_time_recursive",
		.private = offsetof(struct cfq_group, stats.service_time),
1953
		.seq_show = cfqg_print_rwstat_recursive,
1954 1955 1956 1957
	},
	{
		.name = "io_wait_time_recursive",
		.private = offsetof(struct cfq_group, stats.wait_time),
1958
		.seq_show = cfqg_print_rwstat_recursive,
1959 1960 1961 1962
	},
	{
		.name = "io_merged_recursive",
		.private = offsetof(struct cfq_group, stats.merged),
1963
		.seq_show = cfqg_print_rwstat_recursive,
1964 1965 1966 1967
	},
	{
		.name = "io_queued_recursive",
		.private = offsetof(struct cfq_group, stats.queued),
1968
		.seq_show = cfqg_print_rwstat_recursive,
1969
	},
1970 1971 1972
#ifdef CONFIG_DEBUG_BLK_CGROUP
	{
		.name = "avg_queue_size",
1973
		.seq_show = cfqg_print_avg_queue_size,
1974 1975 1976
	},
	{
		.name = "group_wait_time",
1977
		.private = offsetof(struct cfq_group, stats.group_wait_time),
1978
		.seq_show = cfqg_print_stat,
1979 1980 1981
	},
	{
		.name = "idle_time",
1982
		.private = offsetof(struct cfq_group, stats.idle_time),
1983
		.seq_show = cfqg_print_stat,
1984 1985 1986
	},
	{
		.name = "empty_time",
1987
		.private = offsetof(struct cfq_group, stats.empty_time),
1988
		.seq_show = cfqg_print_stat,
1989 1990 1991
	},
	{
		.name = "dequeue",
1992
		.private = offsetof(struct cfq_group, stats.dequeue),
1993
		.seq_show = cfqg_print_stat,
1994 1995 1996
	},
	{
		.name = "unaccounted_time",
1997
		.private = offsetof(struct cfq_group, stats.unaccounted_time),
1998
		.seq_show = cfqg_print_stat,
1999 2000 2001 2002
	},
#endif	/* CONFIG_DEBUG_BLK_CGROUP */
	{ }	/* terminate */
};
2003
#else /* GROUP_IOSCHED */
2004
static struct cfq_group *cfq_lookup_create_cfqg(struct cfq_data *cfqd,
T
Tejun Heo 已提交
2005
						struct blkcg *blkcg)
2006
{
2007
	return cfqd->root_group;
2008
}
2009

2010 2011 2012 2013 2014 2015 2016
static inline void
cfq_link_cfqq_cfqg(struct cfq_queue *cfqq, struct cfq_group *cfqg) {
	cfqq->cfqg = cfqg;
}

#endif /* GROUP_IOSCHED */

2017
/*
2018
 * The cfqd->service_trees holds all pending cfq_queue's that have
2019 2020 2021
 * requests waiting to be processed. It is sorted in the order that
 * we will service the queues.
 */
2022
static void cfq_service_tree_add(struct cfq_data *cfqd, struct cfq_queue *cfqq,
2023
				 bool add_front)
2024
{
2025 2026
	struct rb_node **p, *parent;
	struct cfq_queue *__cfqq;
2027
	unsigned long rb_key;
2028
	struct cfq_rb_root *st;
2029
	int left;
2030
	int new_cfqq = 1;
2031

2032
	st = st_for(cfqq->cfqg, cfqq_class(cfqq), cfqq_type(cfqq));
2033 2034
	if (cfq_class_idle(cfqq)) {
		rb_key = CFQ_IDLE_DELAY;
2035
		parent = rb_last(&st->rb);
2036 2037 2038 2039 2040 2041
		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) {
2042 2043 2044 2045 2046 2047
		/*
		 * Get our rb key offset. Subtract any residual slice
		 * value carried from last service. A negative resid
		 * count indicates slice overrun, and this should position
		 * the next service time further away in the tree.
		 */
2048
		rb_key = cfq_slice_offset(cfqd, cfqq) + jiffies;
2049
		rb_key -= cfqq->slice_resid;
2050
		cfqq->slice_resid = 0;
2051 2052
	} else {
		rb_key = -HZ;
2053
		__cfqq = cfq_rb_first(st);
2054 2055
		rb_key += __cfqq ? __cfqq->rb_key : jiffies;
	}
L
Linus Torvalds 已提交
2056

2057
	if (!RB_EMPTY_NODE(&cfqq->rb_node)) {
2058
		new_cfqq = 0;
2059
		/*
2060
		 * same position, nothing more to do
2061
		 */
2062
		if (rb_key == cfqq->rb_key && cfqq->service_tree == st)
2063
			return;
L
Linus Torvalds 已提交
2064

2065 2066
		cfq_rb_erase(&cfqq->rb_node, cfqq->service_tree);
		cfqq->service_tree = NULL;
L
Linus Torvalds 已提交
2067
	}
2068

2069
	left = 1;
2070
	parent = NULL;
2071 2072
	cfqq->service_tree = st;
	p = &st->rb.rb_node;
2073 2074 2075 2076
	while (*p) {
		parent = *p;
		__cfqq = rb_entry(parent, struct cfq_queue, rb_node);

2077
		/*
2078
		 * sort by key, that represents service time.
2079
		 */
2080
		if (time_before(rb_key, __cfqq->rb_key))
2081
			p = &parent->rb_left;
2082
		else {
2083
			p = &parent->rb_right;
2084
			left = 0;
2085
		}
2086 2087
	}

2088
	if (left)
2089
		st->left = &cfqq->rb_node;
2090

2091 2092
	cfqq->rb_key = rb_key;
	rb_link_node(&cfqq->rb_node, parent, p);
2093 2094
	rb_insert_color(&cfqq->rb_node, &st->rb);
	st->count++;
2095
	if (add_front || !new_cfqq)
2096
		return;
2097
	cfq_group_notify_queue_add(cfqd, cfqq->cfqg);
L
Linus Torvalds 已提交
2098 2099
}

2100
static struct cfq_queue *
2101 2102 2103
cfq_prio_tree_lookup(struct cfq_data *cfqd, struct rb_root *root,
		     sector_t sector, struct rb_node **ret_parent,
		     struct rb_node ***rb_link)
2104 2105 2106 2107 2108 2109 2110 2111 2112 2113 2114 2115 2116 2117 2118 2119
{
	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.
		 */
2120
		if (sector > blk_rq_pos(cfqq->next_rq))
2121
			n = &(*p)->rb_right;
2122
		else if (sector < blk_rq_pos(cfqq->next_rq))
2123 2124 2125 2126
			n = &(*p)->rb_left;
		else
			break;
		p = n;
2127
		cfqq = NULL;
2128 2129 2130 2131 2132
	}

	*ret_parent = parent;
	if (rb_link)
		*rb_link = p;
2133
	return cfqq;
2134 2135 2136 2137 2138 2139 2140
}

static void cfq_prio_tree_add(struct cfq_data *cfqd, struct cfq_queue *cfqq)
{
	struct rb_node **p, *parent;
	struct cfq_queue *__cfqq;

2141 2142 2143 2144
	if (cfqq->p_root) {
		rb_erase(&cfqq->p_node, cfqq->p_root);
		cfqq->p_root = NULL;
	}
2145 2146 2147 2148 2149 2150

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

2151
	cfqq->p_root = &cfqd->prio_trees[cfqq->org_ioprio];
2152 2153
	__cfqq = cfq_prio_tree_lookup(cfqd, cfqq->p_root,
				      blk_rq_pos(cfqq->next_rq), &parent, &p);
2154 2155
	if (!__cfqq) {
		rb_link_node(&cfqq->p_node, parent, p);
2156 2157 2158
		rb_insert_color(&cfqq->p_node, cfqq->p_root);
	} else
		cfqq->p_root = NULL;
2159 2160
}

2161 2162 2163
/*
 * Update cfqq's position in the service tree.
 */
2164
static void cfq_resort_rr_list(struct cfq_data *cfqd, struct cfq_queue *cfqq)
J
Jens Axboe 已提交
2165 2166 2167 2168
{
	/*
	 * Resorting requires the cfqq to be on the RR list already.
	 */
2169
	if (cfq_cfqq_on_rr(cfqq)) {
2170
		cfq_service_tree_add(cfqd, cfqq, 0);
2171 2172
		cfq_prio_tree_add(cfqd, cfqq);
	}
J
Jens Axboe 已提交
2173 2174
}

L
Linus Torvalds 已提交
2175 2176
/*
 * add to busy list of queues for service, trying to be fair in ordering
2177
 * the pending list according to last request service
L
Linus Torvalds 已提交
2178
 */
J
Jens Axboe 已提交
2179
static void cfq_add_cfqq_rr(struct cfq_data *cfqd, struct cfq_queue *cfqq)
L
Linus Torvalds 已提交
2180
{
2181
	cfq_log_cfqq(cfqd, cfqq, "add_to_rr");
J
Jens Axboe 已提交
2182 2183
	BUG_ON(cfq_cfqq_on_rr(cfqq));
	cfq_mark_cfqq_on_rr(cfqq);
L
Linus Torvalds 已提交
2184
	cfqd->busy_queues++;
2185 2186
	if (cfq_cfqq_sync(cfqq))
		cfqd->busy_sync_queues++;
L
Linus Torvalds 已提交
2187

2188
	cfq_resort_rr_list(cfqd, cfqq);
L
Linus Torvalds 已提交
2189 2190
}

2191 2192 2193 2194
/*
 * Called when the cfqq no longer has requests pending, remove it from
 * the service tree.
 */
J
Jens Axboe 已提交
2195
static void cfq_del_cfqq_rr(struct cfq_data *cfqd, struct cfq_queue *cfqq)
L
Linus Torvalds 已提交
2196
{
2197
	cfq_log_cfqq(cfqd, cfqq, "del_from_rr");
J
Jens Axboe 已提交
2198 2199
	BUG_ON(!cfq_cfqq_on_rr(cfqq));
	cfq_clear_cfqq_on_rr(cfqq);
L
Linus Torvalds 已提交
2200

2201 2202 2203 2204
	if (!RB_EMPTY_NODE(&cfqq->rb_node)) {
		cfq_rb_erase(&cfqq->rb_node, cfqq->service_tree);
		cfqq->service_tree = NULL;
	}
2205 2206 2207 2208
	if (cfqq->p_root) {
		rb_erase(&cfqq->p_node, cfqq->p_root);
		cfqq->p_root = NULL;
	}
2209

2210
	cfq_group_notify_queue_del(cfqd, cfqq->cfqg);
L
Linus Torvalds 已提交
2211 2212
	BUG_ON(!cfqd->busy_queues);
	cfqd->busy_queues--;
2213 2214
	if (cfq_cfqq_sync(cfqq))
		cfqd->busy_sync_queues--;
L
Linus Torvalds 已提交
2215 2216 2217 2218 2219
}

/*
 * rb tree support functions
 */
J
Jens Axboe 已提交
2220
static void cfq_del_rq_rb(struct request *rq)
L
Linus Torvalds 已提交
2221
{
J
Jens Axboe 已提交
2222 2223
	struct cfq_queue *cfqq = RQ_CFQQ(rq);
	const int sync = rq_is_sync(rq);
L
Linus Torvalds 已提交
2224

2225 2226
	BUG_ON(!cfqq->queued[sync]);
	cfqq->queued[sync]--;
L
Linus Torvalds 已提交
2227

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

2230 2231 2232 2233 2234 2235 2236 2237 2238 2239 2240
	if (cfq_cfqq_on_rr(cfqq) && RB_EMPTY_ROOT(&cfqq->sort_list)) {
		/*
		 * Queue will be deleted from service tree when we actually
		 * expire it later. Right now just remove it from prio tree
		 * as it is empty.
		 */
		if (cfqq->p_root) {
			rb_erase(&cfqq->p_node, cfqq->p_root);
			cfqq->p_root = NULL;
		}
	}
L
Linus Torvalds 已提交
2241 2242
}

J
Jens Axboe 已提交
2243
static void cfq_add_rq_rb(struct request *rq)
L
Linus Torvalds 已提交
2244
{
J
Jens Axboe 已提交
2245
	struct cfq_queue *cfqq = RQ_CFQQ(rq);
L
Linus Torvalds 已提交
2246
	struct cfq_data *cfqd = cfqq->cfqd;
2247
	struct request *prev;
L
Linus Torvalds 已提交
2248

2249
	cfqq->queued[rq_is_sync(rq)]++;
L
Linus Torvalds 已提交
2250

2251
	elv_rb_add(&cfqq->sort_list, rq);
2252 2253 2254

	if (!cfq_cfqq_on_rr(cfqq))
		cfq_add_cfqq_rr(cfqd, cfqq);
2255 2256 2257 2258

	/*
	 * check if this request is a better next-serve candidate
	 */
2259
	prev = cfqq->next_rq;
2260
	cfqq->next_rq = cfq_choose_req(cfqd, cfqq->next_rq, rq, cfqd->last_position);
2261 2262 2263 2264 2265 2266 2267

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

2268
	BUG_ON(!cfqq->next_rq);
L
Linus Torvalds 已提交
2269 2270
}

J
Jens Axboe 已提交
2271
static void cfq_reposition_rq_rb(struct cfq_queue *cfqq, struct request *rq)
L
Linus Torvalds 已提交
2272
{
2273 2274
	elv_rb_del(&cfqq->sort_list, rq);
	cfqq->queued[rq_is_sync(rq)]--;
2275
	cfqg_stats_update_io_remove(RQ_CFQG(rq), rq->cmd_flags);
J
Jens Axboe 已提交
2276
	cfq_add_rq_rb(rq);
2277 2278
	cfqg_stats_update_io_add(RQ_CFQG(rq), cfqq->cfqd->serving_group,
				 rq->cmd_flags);
L
Linus Torvalds 已提交
2279 2280
}

2281 2282
static struct request *
cfq_find_rq_fmerge(struct cfq_data *cfqd, struct bio *bio)
L
Linus Torvalds 已提交
2283
{
2284
	struct task_struct *tsk = current;
2285
	struct cfq_io_cq *cic;
2286
	struct cfq_queue *cfqq;
L
Linus Torvalds 已提交
2287

2288
	cic = cfq_cic_lookup(cfqd, tsk->io_context);
2289 2290 2291 2292
	if (!cic)
		return NULL;

	cfqq = cic_to_cfqq(cic, cfq_bio_sync(bio));
K
Kent Overstreet 已提交
2293 2294
	if (cfqq)
		return elv_rb_find(&cfqq->sort_list, bio_end_sector(bio));
L
Linus Torvalds 已提交
2295 2296 2297 2298

	return NULL;
}

2299
static void cfq_activate_request(struct request_queue *q, struct request *rq)
L
Linus Torvalds 已提交
2300
{
2301
	struct cfq_data *cfqd = q->elevator->elevator_data;
J
Jens Axboe 已提交
2302

2303
	cfqd->rq_in_driver++;
2304
	cfq_log_cfqq(cfqd, RQ_CFQQ(rq), "activate rq, drv=%d",
2305
						cfqd->rq_in_driver);
2306

2307
	cfqd->last_position = blk_rq_pos(rq) + blk_rq_sectors(rq);
L
Linus Torvalds 已提交
2308 2309
}

2310
static void cfq_deactivate_request(struct request_queue *q, struct request *rq)
L
Linus Torvalds 已提交
2311
{
2312 2313
	struct cfq_data *cfqd = q->elevator->elevator_data;

2314 2315
	WARN_ON(!cfqd->rq_in_driver);
	cfqd->rq_in_driver--;
2316
	cfq_log_cfqq(cfqd, RQ_CFQQ(rq), "deactivate rq, drv=%d",
2317
						cfqd->rq_in_driver);
L
Linus Torvalds 已提交
2318 2319
}

2320
static void cfq_remove_request(struct request *rq)
L
Linus Torvalds 已提交
2321
{
J
Jens Axboe 已提交
2322
	struct cfq_queue *cfqq = RQ_CFQQ(rq);
2323

J
Jens Axboe 已提交
2324 2325
	if (cfqq->next_rq == rq)
		cfqq->next_rq = cfq_find_next_rq(cfqq->cfqd, cfqq, rq);
L
Linus Torvalds 已提交
2326

2327
	list_del_init(&rq->queuelist);
J
Jens Axboe 已提交
2328
	cfq_del_rq_rb(rq);
2329

2330
	cfqq->cfqd->rq_queued--;
2331
	cfqg_stats_update_io_remove(RQ_CFQG(rq), rq->cmd_flags);
2332 2333 2334
	if (rq->cmd_flags & REQ_PRIO) {
		WARN_ON(!cfqq->prio_pending);
		cfqq->prio_pending--;
2335
	}
L
Linus Torvalds 已提交
2336 2337
}

2338 2339
static int cfq_merge(struct request_queue *q, struct request **req,
		     struct bio *bio)
L
Linus Torvalds 已提交
2340 2341 2342 2343
{
	struct cfq_data *cfqd = q->elevator->elevator_data;
	struct request *__rq;

2344
	__rq = cfq_find_rq_fmerge(cfqd, bio);
2345
	if (__rq && elv_rq_merge_ok(__rq, bio)) {
2346 2347
		*req = __rq;
		return ELEVATOR_FRONT_MERGE;
L
Linus Torvalds 已提交
2348 2349 2350 2351 2352
	}

	return ELEVATOR_NO_MERGE;
}

2353
static void cfq_merged_request(struct request_queue *q, struct request *req,
2354
			       int type)
L
Linus Torvalds 已提交
2355
{
2356
	if (type == ELEVATOR_FRONT_MERGE) {
J
Jens Axboe 已提交
2357
		struct cfq_queue *cfqq = RQ_CFQQ(req);
L
Linus Torvalds 已提交
2358

J
Jens Axboe 已提交
2359
		cfq_reposition_rq_rb(cfqq, req);
L
Linus Torvalds 已提交
2360 2361 2362
	}
}

D
Divyesh Shah 已提交
2363 2364 2365
static void cfq_bio_merged(struct request_queue *q, struct request *req,
				struct bio *bio)
{
2366
	cfqg_stats_update_io_merged(RQ_CFQG(req), bio->bi_rw);
D
Divyesh Shah 已提交
2367 2368
}

L
Linus Torvalds 已提交
2369
static void
2370
cfq_merged_requests(struct request_queue *q, struct request *rq,
L
Linus Torvalds 已提交
2371 2372
		    struct request *next)
{
2373
	struct cfq_queue *cfqq = RQ_CFQQ(rq);
2374 2375
	struct cfq_data *cfqd = q->elevator->elevator_data;

2376 2377 2378 2379
	/*
	 * reposition in fifo if next is older than rq
	 */
	if (!list_empty(&rq->queuelist) && !list_empty(&next->queuelist) &&
2380
	    time_before(next->fifo_time, rq->fifo_time) &&
2381
	    cfqq == RQ_CFQQ(next)) {
2382
		list_move(&rq->queuelist, &next->queuelist);
2383
		rq->fifo_time = next->fifo_time;
2384
	}
2385

2386 2387
	if (cfqq->next_rq == next)
		cfqq->next_rq = rq;
2388
	cfq_remove_request(next);
2389
	cfqg_stats_update_io_merged(RQ_CFQG(rq), next->cmd_flags);
2390 2391 2392 2393 2394 2395 2396 2397 2398 2399

	cfqq = RQ_CFQQ(next);
	/*
	 * all requests of this queue are merged to other queues, delete it
	 * from the service tree. If it's the active_queue,
	 * cfq_dispatch_requests() will choose to expire it or do idle
	 */
	if (cfq_cfqq_on_rr(cfqq) && RB_EMPTY_ROOT(&cfqq->sort_list) &&
	    cfqq != cfqd->active_queue)
		cfq_del_cfqq_rr(cfqd, cfqq);
2400 2401
}

2402
static int cfq_allow_merge(struct request_queue *q, struct request *rq,
2403 2404 2405
			   struct bio *bio)
{
	struct cfq_data *cfqd = q->elevator->elevator_data;
2406
	struct cfq_io_cq *cic;
2407 2408 2409
	struct cfq_queue *cfqq;

	/*
2410
	 * Disallow merge of a sync bio into an async request.
2411
	 */
2412
	if (cfq_bio_sync(bio) && !rq_is_sync(rq))
2413
		return false;
2414 2415

	/*
T
Tejun Heo 已提交
2416
	 * Lookup the cfqq that this bio will be queued with and allow
2417
	 * merge only if rq is queued there.
T
Tejun Heo 已提交
2418
	 */
2419 2420 2421
	cic = cfq_cic_lookup(cfqd, current->io_context);
	if (!cic)
		return false;
2422

2423
	cfqq = cic_to_cfqq(cic, cfq_bio_sync(bio));
2424
	return cfqq == RQ_CFQQ(rq);
2425 2426
}

2427 2428 2429
static inline void cfq_del_timer(struct cfq_data *cfqd, struct cfq_queue *cfqq)
{
	del_timer(&cfqd->idle_slice_timer);
2430
	cfqg_stats_update_idle_time(cfqq->cfqg);
2431 2432
}

J
Jens Axboe 已提交
2433 2434
static void __cfq_set_active_queue(struct cfq_data *cfqd,
				   struct cfq_queue *cfqq)
2435 2436
{
	if (cfqq) {
2437
		cfq_log_cfqq(cfqd, cfqq, "set_active wl_class:%d wl_type:%d",
2438
				cfqd->serving_wl_class, cfqd->serving_wl_type);
2439
		cfqg_stats_update_avg_queue_size(cfqq->cfqg);
2440 2441 2442 2443 2444 2445 2446 2447 2448 2449 2450 2451 2452 2453
		cfqq->slice_start = 0;
		cfqq->dispatch_start = jiffies;
		cfqq->allocated_slice = 0;
		cfqq->slice_end = 0;
		cfqq->slice_dispatch = 0;
		cfqq->nr_sectors = 0;

		cfq_clear_cfqq_wait_request(cfqq);
		cfq_clear_cfqq_must_dispatch(cfqq);
		cfq_clear_cfqq_must_alloc_slice(cfqq);
		cfq_clear_cfqq_fifo_expire(cfqq);
		cfq_mark_cfqq_slice_new(cfqq);

		cfq_del_timer(cfqd, cfqq);
2454 2455 2456 2457 2458
	}

	cfqd->active_queue = cfqq;
}

2459 2460 2461 2462 2463
/*
 * 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,
2464
		    bool timed_out)
2465
{
2466 2467
	cfq_log_cfqq(cfqd, cfqq, "slice expired t=%d", timed_out);

2468
	if (cfq_cfqq_wait_request(cfqq))
2469
		cfq_del_timer(cfqd, cfqq);
2470 2471

	cfq_clear_cfqq_wait_request(cfqq);
2472
	cfq_clear_cfqq_wait_busy(cfqq);
2473

2474 2475 2476 2477 2478 2479 2480 2481 2482
	/*
	 * If this cfqq is shared between multiple processes, check to
	 * make sure that those processes are still issuing I/Os within
	 * the mean seek distance.  If not, it may be time to break the
	 * queues apart again.
	 */
	if (cfq_cfqq_coop(cfqq) && CFQQ_SEEKY(cfqq))
		cfq_mark_cfqq_split_coop(cfqq);

2483
	/*
2484
	 * store what was left of this slice, if the queue idled/timed out
2485
	 */
2486 2487
	if (timed_out) {
		if (cfq_cfqq_slice_new(cfqq))
2488
			cfqq->slice_resid = cfq_scaled_cfqq_slice(cfqd, cfqq);
2489 2490
		else
			cfqq->slice_resid = cfqq->slice_end - jiffies;
2491 2492
		cfq_log_cfqq(cfqd, cfqq, "resid=%ld", cfqq->slice_resid);
	}
2493

2494
	cfq_group_served(cfqd, cfqq->cfqg, cfqq);
2495

2496 2497 2498
	if (cfq_cfqq_on_rr(cfqq) && RB_EMPTY_ROOT(&cfqq->sort_list))
		cfq_del_cfqq_rr(cfqd, cfqq);

2499
	cfq_resort_rr_list(cfqd, cfqq);
2500 2501 2502 2503 2504

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

	if (cfqd->active_cic) {
2505
		put_io_context(cfqd->active_cic->icq.ioc);
2506 2507 2508 2509
		cfqd->active_cic = NULL;
	}
}

2510
static inline void cfq_slice_expired(struct cfq_data *cfqd, bool timed_out)
2511 2512 2513 2514
{
	struct cfq_queue *cfqq = cfqd->active_queue;

	if (cfqq)
2515
		__cfq_slice_expired(cfqd, cfqq, timed_out);
2516 2517
}

2518 2519 2520 2521
/*
 * 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 已提交
2522
static struct cfq_queue *cfq_get_next_queue(struct cfq_data *cfqd)
2523
{
2524 2525
	struct cfq_rb_root *st = st_for(cfqd->serving_group,
			cfqd->serving_wl_class, cfqd->serving_wl_type);
2526

2527 2528 2529
	if (!cfqd->rq_queued)
		return NULL;

2530
	/* There is nothing to dispatch */
2531
	if (!st)
2532
		return NULL;
2533
	if (RB_EMPTY_ROOT(&st->rb))
2534
		return NULL;
2535
	return cfq_rb_first(st);
J
Jens Axboe 已提交
2536 2537
}

2538 2539
static struct cfq_queue *cfq_get_next_queue_forced(struct cfq_data *cfqd)
{
2540
	struct cfq_group *cfqg;
2541 2542 2543 2544 2545 2546 2547
	struct cfq_queue *cfqq;
	int i, j;
	struct cfq_rb_root *st;

	if (!cfqd->rq_queued)
		return NULL;

2548 2549 2550 2551
	cfqg = cfq_get_next_cfqg(cfqd);
	if (!cfqg)
		return NULL;

2552 2553 2554 2555 2556 2557
	for_each_cfqg_st(cfqg, i, j, st)
		if ((cfqq = cfq_rb_first(st)) != NULL)
			return cfqq;
	return NULL;
}

2558 2559 2560
/*
 * Get and set a new active queue for service.
 */
2561 2562
static struct cfq_queue *cfq_set_active_queue(struct cfq_data *cfqd,
					      struct cfq_queue *cfqq)
J
Jens Axboe 已提交
2563
{
2564
	if (!cfqq)
2565
		cfqq = cfq_get_next_queue(cfqd);
J
Jens Axboe 已提交
2566

2567
	__cfq_set_active_queue(cfqd, cfqq);
J
Jens Axboe 已提交
2568
	return cfqq;
2569 2570
}

2571 2572 2573
static inline sector_t cfq_dist_from_last(struct cfq_data *cfqd,
					  struct request *rq)
{
2574 2575
	if (blk_rq_pos(rq) >= cfqd->last_position)
		return blk_rq_pos(rq) - cfqd->last_position;
2576
	else
2577
		return cfqd->last_position - blk_rq_pos(rq);
2578 2579
}

2580
static inline int cfq_rq_close(struct cfq_data *cfqd, struct cfq_queue *cfqq,
2581
			       struct request *rq)
J
Jens Axboe 已提交
2582
{
2583
	return cfq_dist_from_last(cfqd, rq) <= CFQQ_CLOSE_THR;
J
Jens Axboe 已提交
2584 2585
}

2586 2587 2588
static struct cfq_queue *cfqq_close(struct cfq_data *cfqd,
				    struct cfq_queue *cur_cfqq)
{
2589
	struct rb_root *root = &cfqd->prio_trees[cur_cfqq->org_ioprio];
2590 2591 2592 2593 2594 2595 2596 2597 2598 2599 2600
	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.
	 */
2601
	__cfqq = cfq_prio_tree_lookup(cfqd, root, sector, &parent, NULL);
2602 2603 2604 2605 2606 2607 2608 2609
	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);
2610
	if (cfq_rq_close(cfqd, cur_cfqq, __cfqq->next_rq))
2611 2612
		return __cfqq;

2613
	if (blk_rq_pos(__cfqq->next_rq) < sector)
2614 2615 2616 2617 2618 2619 2620
		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);
2621
	if (cfq_rq_close(cfqd, cur_cfqq, __cfqq->next_rq))
2622 2623 2624 2625 2626 2627 2628 2629 2630 2631 2632 2633 2634 2635 2636 2637
		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,
2638
					      struct cfq_queue *cur_cfqq)
J
Jens Axboe 已提交
2639
{
2640 2641
	struct cfq_queue *cfqq;

2642 2643
	if (cfq_class_idle(cur_cfqq))
		return NULL;
2644 2645 2646 2647 2648
	if (!cfq_cfqq_sync(cur_cfqq))
		return NULL;
	if (CFQQ_SEEKY(cur_cfqq))
		return NULL;

2649 2650 2651 2652 2653 2654
	/*
	 * Don't search priority tree if it's the only queue in the group.
	 */
	if (cur_cfqq->cfqg->nr_cfqq == 1)
		return NULL;

J
Jens Axboe 已提交
2655
	/*
2656 2657 2658
	 * 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 已提交
2659
	 */
2660 2661 2662 2663
	cfqq = cfqq_close(cfqd, cur_cfqq);
	if (!cfqq)
		return NULL;

2664 2665 2666 2667
	/* If new queue belongs to different cfq_group, don't choose it */
	if (cur_cfqq->cfqg != cfqq->cfqg)
		return NULL;

J
Jeff Moyer 已提交
2668 2669 2670 2671 2672
	/*
	 * It only makes sense to merge sync queues.
	 */
	if (!cfq_cfqq_sync(cfqq))
		return NULL;
2673 2674
	if (CFQQ_SEEKY(cfqq))
		return NULL;
J
Jeff Moyer 已提交
2675

2676 2677 2678 2679 2680 2681
	/*
	 * Do not merge queues of different priority classes
	 */
	if (cfq_class_rt(cfqq) != cfq_class_rt(cur_cfqq))
		return NULL;

2682
	return cfqq;
J
Jens Axboe 已提交
2683 2684
}

2685 2686 2687 2688 2689 2690
/*
 * Determine whether we should enforce idle window for this queue.
 */

static bool cfq_should_idle(struct cfq_data *cfqd, struct cfq_queue *cfqq)
{
2691
	enum wl_class_t wl_class = cfqq_class(cfqq);
2692
	struct cfq_rb_root *st = cfqq->service_tree;
2693

2694 2695
	BUG_ON(!st);
	BUG_ON(!st->count);
2696

2697 2698 2699
	if (!cfqd->cfq_slice_idle)
		return false;

2700
	/* We never do for idle class queues. */
2701
	if (wl_class == IDLE_WORKLOAD)
2702 2703 2704
		return false;

	/* We do for queues that were marked with idle window flag. */
2705 2706
	if (cfq_cfqq_idle_window(cfqq) &&
	   !(blk_queue_nonrot(cfqd->queue) && cfqd->hw_tag))
2707 2708 2709 2710 2711 2712
		return true;

	/*
	 * Otherwise, we do only if they are the last ones
	 * in their service tree.
	 */
2713 2714
	if (st->count == 1 && cfq_cfqq_sync(cfqq) &&
	   !cfq_io_thinktime_big(cfqd, &st->ttime, false))
S
Shaohua Li 已提交
2715
		return true;
2716
	cfq_log_cfqq(cfqd, cfqq, "Not idling. st->count:%d", st->count);
S
Shaohua Li 已提交
2717
	return false;
2718 2719
}

J
Jens Axboe 已提交
2720
static void cfq_arm_slice_timer(struct cfq_data *cfqd)
2721
{
2722
	struct cfq_queue *cfqq = cfqd->active_queue;
2723
	struct cfq_io_cq *cic;
2724
	unsigned long sl, group_idle = 0;
2725

2726
	/*
J
Jens Axboe 已提交
2727 2728 2729
	 * 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.
2730
	 */
J
Jens Axboe 已提交
2731
	if (blk_queue_nonrot(cfqd->queue) && cfqd->hw_tag)
2732 2733
		return;

2734
	WARN_ON(!RB_EMPTY_ROOT(&cfqq->sort_list));
J
Jens Axboe 已提交
2735
	WARN_ON(cfq_cfqq_slice_new(cfqq));
2736 2737 2738 2739

	/*
	 * idle is disabled, either manually or by past process history
	 */
2740 2741 2742 2743 2744 2745 2746
	if (!cfq_should_idle(cfqd, cfqq)) {
		/* no queue idling. Check for group idling */
		if (cfqd->cfq_group_idle)
			group_idle = cfqd->cfq_group_idle;
		else
			return;
	}
J
Jens Axboe 已提交
2747

2748
	/*
2749
	 * still active requests from this queue, don't idle
2750
	 */
2751
	if (cfqq->dispatched)
2752 2753
		return;

2754 2755 2756
	/*
	 * task has exited, don't wait
	 */
2757
	cic = cfqd->active_cic;
T
Tejun Heo 已提交
2758
	if (!cic || !atomic_read(&cic->icq.ioc->active_ref))
J
Jens Axboe 已提交
2759 2760
		return;

2761 2762 2763 2764 2765
	/*
	 * If our average think time is larger than the remaining time
	 * slice, then don't idle. This avoids overrunning the allotted
	 * time slice.
	 */
2766 2767
	if (sample_valid(cic->ttime.ttime_samples) &&
	    (cfqq->slice_end - jiffies < cic->ttime.ttime_mean)) {
2768
		cfq_log_cfqq(cfqd, cfqq, "Not idling. think_time:%lu",
2769
			     cic->ttime.ttime_mean);
2770
		return;
2771
	}
2772

2773 2774 2775 2776
	/* There are other queues in the group, don't do group idle */
	if (group_idle && cfqq->cfqg->nr_cfqq > 1)
		return;

J
Jens Axboe 已提交
2777
	cfq_mark_cfqq_wait_request(cfqq);
2778

2779 2780 2781 2782
	if (group_idle)
		sl = cfqd->cfq_group_idle;
	else
		sl = cfqd->cfq_slice_idle;
2783

2784
	mod_timer(&cfqd->idle_slice_timer, jiffies + sl);
2785
	cfqg_stats_set_start_idle_time(cfqq->cfqg);
2786 2787
	cfq_log_cfqq(cfqd, cfqq, "arm_idle: %lu group_idle: %d", sl,
			group_idle ? 1 : 0);
L
Linus Torvalds 已提交
2788 2789
}

2790 2791 2792
/*
 * Move request from internal lists to the request queue dispatch list.
 */
2793
static void cfq_dispatch_insert(struct request_queue *q, struct request *rq)
L
Linus Torvalds 已提交
2794
{
2795
	struct cfq_data *cfqd = q->elevator->elevator_data;
J
Jens Axboe 已提交
2796
	struct cfq_queue *cfqq = RQ_CFQQ(rq);
2797

2798 2799
	cfq_log_cfqq(cfqd, cfqq, "dispatch_insert");

2800
	cfqq->next_rq = cfq_find_next_rq(cfqd, cfqq, rq);
2801
	cfq_remove_request(rq);
J
Jens Axboe 已提交
2802
	cfqq->dispatched++;
2803
	(RQ_CFQG(rq))->dispatched++;
2804
	elv_dispatch_sort(q, rq);
2805

2806
	cfqd->rq_in_flight[cfq_cfqq_sync(cfqq)]++;
2807
	cfqq->nr_sectors += blk_rq_sectors(rq);
2808
	cfqg_stats_update_dispatch(cfqq->cfqg, blk_rq_bytes(rq), rq->cmd_flags);
L
Linus Torvalds 已提交
2809 2810 2811 2812 2813
}

/*
 * return expired entry, or NULL to just start from scratch in rbtree
 */
J
Jens Axboe 已提交
2814
static struct request *cfq_check_fifo(struct cfq_queue *cfqq)
L
Linus Torvalds 已提交
2815
{
2816
	struct request *rq = NULL;
L
Linus Torvalds 已提交
2817

J
Jens Axboe 已提交
2818
	if (cfq_cfqq_fifo_expire(cfqq))
L
Linus Torvalds 已提交
2819
		return NULL;
2820 2821 2822

	cfq_mark_cfqq_fifo_expire(cfqq);

2823 2824
	if (list_empty(&cfqq->fifo))
		return NULL;
L
Linus Torvalds 已提交
2825

2826
	rq = rq_entry_fifo(cfqq->fifo.next);
2827
	if (time_before(jiffies, rq->fifo_time))
2828
		rq = NULL;
L
Linus Torvalds 已提交
2829

2830
	cfq_log_cfqq(cfqq->cfqd, cfqq, "fifo=%p", rq);
J
Jens Axboe 已提交
2831
	return rq;
L
Linus Torvalds 已提交
2832 2833
}

2834 2835 2836 2837
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 已提交
2838

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

2841
	return 2 * base_rq * (IOPRIO_BE_NR - cfqq->ioprio);
L
Linus Torvalds 已提交
2842 2843
}

J
Jeff Moyer 已提交
2844 2845 2846 2847 2848 2849 2850 2851
/*
 * Must be called with the queue_lock held.
 */
static int cfqq_process_refs(struct cfq_queue *cfqq)
{
	int process_refs, io_refs;

	io_refs = cfqq->allocated[READ] + cfqq->allocated[WRITE];
2852
	process_refs = cfqq->ref - io_refs;
J
Jeff Moyer 已提交
2853 2854 2855 2856 2857 2858
	BUG_ON(process_refs < 0);
	return process_refs;
}

static void cfq_setup_merge(struct cfq_queue *cfqq, struct cfq_queue *new_cfqq)
{
2859
	int process_refs, new_process_refs;
J
Jeff Moyer 已提交
2860 2861
	struct cfq_queue *__cfqq;

2862 2863 2864 2865 2866 2867 2868 2869 2870
	/*
	 * If there are no process references on the new_cfqq, then it is
	 * unsafe to follow the ->new_cfqq chain as other cfqq's in the
	 * chain may have dropped their last reference (not just their
	 * last process reference).
	 */
	if (!cfqq_process_refs(new_cfqq))
		return;

J
Jeff Moyer 已提交
2871 2872 2873 2874 2875 2876 2877 2878
	/* Avoid a circular list and skip interim queue merges */
	while ((__cfqq = new_cfqq->new_cfqq)) {
		if (__cfqq == cfqq)
			return;
		new_cfqq = __cfqq;
	}

	process_refs = cfqq_process_refs(cfqq);
2879
	new_process_refs = cfqq_process_refs(new_cfqq);
J
Jeff Moyer 已提交
2880 2881 2882 2883
	/*
	 * If the process for the cfqq has gone away, there is no
	 * sense in merging the queues.
	 */
2884
	if (process_refs == 0 || new_process_refs == 0)
J
Jeff Moyer 已提交
2885 2886
		return;

2887 2888 2889 2890 2891
	/*
	 * Merge in the direction of the lesser amount of work.
	 */
	if (new_process_refs >= process_refs) {
		cfqq->new_cfqq = new_cfqq;
2892
		new_cfqq->ref += process_refs;
2893 2894
	} else {
		new_cfqq->new_cfqq = cfqq;
2895
		cfqq->ref += new_process_refs;
2896
	}
J
Jeff Moyer 已提交
2897 2898
}

2899
static enum wl_type_t cfq_choose_wl_type(struct cfq_data *cfqd,
2900
			struct cfq_group *cfqg, enum wl_class_t wl_class)
2901 2902 2903 2904 2905 2906 2907
{
	struct cfq_queue *queue;
	int i;
	bool key_valid = false;
	unsigned long lowest_key = 0;
	enum wl_type_t cur_best = SYNC_NOIDLE_WORKLOAD;

2908 2909
	for (i = 0; i <= SYNC_WORKLOAD; ++i) {
		/* select the one with lowest rb_key */
2910
		queue = cfq_rb_first(st_for(cfqg, wl_class, i));
2911 2912 2913 2914 2915 2916 2917 2918 2919 2920 2921
		if (queue &&
		    (!key_valid || time_before(queue->rb_key, lowest_key))) {
			lowest_key = queue->rb_key;
			cur_best = i;
			key_valid = true;
		}
	}

	return cur_best;
}

2922 2923
static void
choose_wl_class_and_type(struct cfq_data *cfqd, struct cfq_group *cfqg)
2924 2925 2926
{
	unsigned slice;
	unsigned count;
2927
	struct cfq_rb_root *st;
2928
	unsigned group_slice;
2929
	enum wl_class_t original_class = cfqd->serving_wl_class;
2930

2931
	/* Choose next priority. RT > BE > IDLE */
2932
	if (cfq_group_busy_queues_wl(RT_WORKLOAD, cfqd, cfqg))
2933
		cfqd->serving_wl_class = RT_WORKLOAD;
2934
	else if (cfq_group_busy_queues_wl(BE_WORKLOAD, cfqd, cfqg))
2935
		cfqd->serving_wl_class = BE_WORKLOAD;
2936
	else {
2937
		cfqd->serving_wl_class = IDLE_WORKLOAD;
2938 2939 2940 2941
		cfqd->workload_expires = jiffies + 1;
		return;
	}

2942
	if (original_class != cfqd->serving_wl_class)
2943 2944
		goto new_workload;

2945 2946 2947 2948 2949
	/*
	 * For RT and BE, we have to choose also the type
	 * (SYNC, SYNC_NOIDLE, ASYNC), and to compute a workload
	 * expiration time
	 */
2950
	st = st_for(cfqg, cfqd->serving_wl_class, cfqd->serving_wl_type);
2951
	count = st->count;
2952 2953

	/*
2954
	 * check workload expiration, and that we still have other queues ready
2955
	 */
2956
	if (count && !time_after(jiffies, cfqd->workload_expires))
2957 2958
		return;

2959
new_workload:
2960
	/* otherwise select new workload type */
2961
	cfqd->serving_wl_type = cfq_choose_wl_type(cfqd, cfqg,
2962
					cfqd->serving_wl_class);
2963
	st = st_for(cfqg, cfqd->serving_wl_class, cfqd->serving_wl_type);
2964
	count = st->count;
2965 2966 2967 2968 2969 2970

	/*
	 * the workload slice is computed as a fraction of target latency
	 * proportional to the number of queues in that workload, over
	 * all the queues in the same priority class
	 */
2971 2972 2973
	group_slice = cfq_group_slice(cfqd, cfqg);

	slice = group_slice * count /
2974 2975
		max_t(unsigned, cfqg->busy_queues_avg[cfqd->serving_wl_class],
		      cfq_group_busy_queues_wl(cfqd->serving_wl_class, cfqd,
2976
					cfqg));
2977

2978
	if (cfqd->serving_wl_type == ASYNC_WORKLOAD) {
2979 2980 2981 2982 2983 2984 2985 2986 2987
		unsigned int tmp;

		/*
		 * Async queues are currently system wide. Just taking
		 * proportion of queues with-in same group will lead to higher
		 * async ratio system wide as generally root group is going
		 * to have higher weight. A more accurate thing would be to
		 * calculate system wide asnc/sync ratio.
		 */
2988 2989
		tmp = cfqd->cfq_target_latency *
			cfqg_busy_async_queues(cfqd, cfqg);
2990 2991 2992
		tmp = tmp/cfqd->busy_queues;
		slice = min_t(unsigned, slice, tmp);

2993 2994 2995
		/* async workload slice is scaled down according to
		 * the sync/async slice ratio. */
		slice = slice * cfqd->cfq_slice[0] / cfqd->cfq_slice[1];
2996
	} else
2997 2998 2999 3000
		/* sync workload slice is at least 2 * cfq_slice_idle */
		slice = max(slice, 2 * cfqd->cfq_slice_idle);

	slice = max_t(unsigned, slice, CFQ_MIN_TT);
3001
	cfq_log(cfqd, "workload slice:%d", slice);
3002 3003 3004
	cfqd->workload_expires = jiffies + slice;
}

3005 3006 3007
static struct cfq_group *cfq_get_next_cfqg(struct cfq_data *cfqd)
{
	struct cfq_rb_root *st = &cfqd->grp_service_tree;
3008
	struct cfq_group *cfqg;
3009 3010 3011

	if (RB_EMPTY_ROOT(&st->rb))
		return NULL;
3012 3013 3014
	cfqg = cfq_rb_first_group(st);
	update_min_vdisktime(st);
	return cfqg;
3015 3016
}

3017 3018
static void cfq_choose_cfqg(struct cfq_data *cfqd)
{
3019 3020 3021
	struct cfq_group *cfqg = cfq_get_next_cfqg(cfqd);

	cfqd->serving_group = cfqg;
3022 3023

	/* Restore the workload type data */
3024 3025 3026 3027
	if (cfqg->saved_wl_slice) {
		cfqd->workload_expires = jiffies + cfqg->saved_wl_slice;
		cfqd->serving_wl_type = cfqg->saved_wl_type;
		cfqd->serving_wl_class = cfqg->saved_wl_class;
3028 3029 3030
	} else
		cfqd->workload_expires = jiffies - 1;

3031
	choose_wl_class_and_type(cfqd, cfqg);
3032 3033
}

3034
/*
3035 3036
 * 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.
3037
 */
3038
static struct cfq_queue *cfq_select_queue(struct cfq_data *cfqd)
L
Linus Torvalds 已提交
3039
{
3040
	struct cfq_queue *cfqq, *new_cfqq = NULL;
L
Linus Torvalds 已提交
3041

3042 3043 3044
	cfqq = cfqd->active_queue;
	if (!cfqq)
		goto new_queue;
L
Linus Torvalds 已提交
3045

3046 3047
	if (!cfqd->rq_queued)
		return NULL;
3048 3049 3050 3051 3052 3053 3054

	/*
	 * We were waiting for group to get backlogged. Expire the queue
	 */
	if (cfq_cfqq_wait_busy(cfqq) && !RB_EMPTY_ROOT(&cfqq->sort_list))
		goto expire;

3055
	/*
J
Jens Axboe 已提交
3056
	 * The active queue has run out of time, expire it and select new.
3057
	 */
3058 3059 3060 3061 3062 3063 3064 3065 3066 3067
	if (cfq_slice_used(cfqq) && !cfq_cfqq_must_dispatch(cfqq)) {
		/*
		 * If slice had not expired at the completion of last request
		 * we might not have turned on wait_busy flag. Don't expire
		 * the queue yet. Allow the group to get backlogged.
		 *
		 * The very fact that we have used the slice, that means we
		 * have been idling all along on this queue and it should be
		 * ok to wait for this request to complete.
		 */
3068 3069 3070
		if (cfqq->cfqg->nr_cfqq == 1 && RB_EMPTY_ROOT(&cfqq->sort_list)
		    && cfqq->dispatched && cfq_should_idle(cfqd, cfqq)) {
			cfqq = NULL;
3071
			goto keep_queue;
3072
		} else
3073
			goto check_group_idle;
3074
	}
L
Linus Torvalds 已提交
3075

3076
	/*
J
Jens Axboe 已提交
3077 3078
	 * The active queue has requests and isn't expired, allow it to
	 * dispatch.
3079
	 */
3080
	if (!RB_EMPTY_ROOT(&cfqq->sort_list))
3081
		goto keep_queue;
J
Jens Axboe 已提交
3082

3083 3084 3085 3086
	/*
	 * 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
J
Jeff Moyer 已提交
3087
	 * tree.  If possible, merge the expiring queue with the new cfqq.
3088
	 */
3089
	new_cfqq = cfq_close_cooperator(cfqd, cfqq);
J
Jeff Moyer 已提交
3090 3091 3092
	if (new_cfqq) {
		if (!cfqq->new_cfqq)
			cfq_setup_merge(cfqq, new_cfqq);
3093
		goto expire;
J
Jeff Moyer 已提交
3094
	}
3095

J
Jens Axboe 已提交
3096 3097 3098 3099 3100
	/*
	 * 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.
	 */
3101 3102 3103 3104 3105
	if (timer_pending(&cfqd->idle_slice_timer)) {
		cfqq = NULL;
		goto keep_queue;
	}

3106 3107 3108 3109 3110 3111 3112 3113 3114 3115 3116
	/*
	 * This is a deep seek queue, but the device is much faster than
	 * the queue can deliver, don't idle
	 **/
	if (CFQQ_SEEKY(cfqq) && cfq_cfqq_idle_window(cfqq) &&
	    (cfq_cfqq_slice_new(cfqq) ||
	    (cfqq->slice_end - jiffies > jiffies - cfqq->slice_start))) {
		cfq_clear_cfqq_deep(cfqq);
		cfq_clear_cfqq_idle_window(cfqq);
	}

3117 3118 3119 3120 3121 3122 3123 3124 3125 3126
	if (cfqq->dispatched && cfq_should_idle(cfqd, cfqq)) {
		cfqq = NULL;
		goto keep_queue;
	}

	/*
	 * If group idle is enabled and there are requests dispatched from
	 * this group, wait for requests to complete.
	 */
check_group_idle:
S
Shaohua Li 已提交
3127 3128 3129
	if (cfqd->cfq_group_idle && cfqq->cfqg->nr_cfqq == 1 &&
	    cfqq->cfqg->dispatched &&
	    !cfq_io_thinktime_big(cfqd, &cfqq->cfqg->ttime, true)) {
3130 3131
		cfqq = NULL;
		goto keep_queue;
3132 3133
	}

J
Jens Axboe 已提交
3134
expire:
3135
	cfq_slice_expired(cfqd, 0);
J
Jens Axboe 已提交
3136
new_queue:
3137 3138 3139 3140 3141
	/*
	 * Current queue expired. Check if we have to switch to a new
	 * service tree
	 */
	if (!new_cfqq)
3142
		cfq_choose_cfqg(cfqd);
3143

3144
	cfqq = cfq_set_active_queue(cfqd, new_cfqq);
3145
keep_queue:
J
Jens Axboe 已提交
3146
	return cfqq;
3147 3148
}

J
Jens Axboe 已提交
3149
static int __cfq_forced_dispatch_cfqq(struct cfq_queue *cfqq)
3150 3151 3152 3153 3154 3155 3156 3157 3158
{
	int dispatched = 0;

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

	BUG_ON(!list_empty(&cfqq->fifo));
3159 3160

	/* By default cfqq is not expired if it is empty. Do it explicitly */
3161
	__cfq_slice_expired(cfqq->cfqd, cfqq, 0);
3162 3163 3164
	return dispatched;
}

3165 3166 3167 3168
/*
 * Drain our current requests. Used for barriers and when switching
 * io schedulers on-the-fly.
 */
3169
static int cfq_forced_dispatch(struct cfq_data *cfqd)
3170
{
3171
	struct cfq_queue *cfqq;
3172
	int dispatched = 0;
3173

3174
	/* Expire the timeslice of the current active queue first */
3175
	cfq_slice_expired(cfqd, 0);
3176 3177
	while ((cfqq = cfq_get_next_queue_forced(cfqd)) != NULL) {
		__cfq_set_active_queue(cfqd, cfqq);
3178
		dispatched += __cfq_forced_dispatch_cfqq(cfqq);
3179
	}
3180 3181 3182

	BUG_ON(cfqd->busy_queues);

3183
	cfq_log(cfqd, "forced_dispatch=%d", dispatched);
3184 3185 3186
	return dispatched;
}

S
Shaohua Li 已提交
3187 3188 3189 3190 3191
static inline bool cfq_slice_used_soon(struct cfq_data *cfqd,
	struct cfq_queue *cfqq)
{
	/* the queue hasn't finished any request, can't estimate */
	if (cfq_cfqq_slice_new(cfqq))
S
Shaohua Li 已提交
3192
		return true;
S
Shaohua Li 已提交
3193 3194
	if (time_after(jiffies + cfqd->cfq_slice_idle * cfqq->dispatched,
		cfqq->slice_end))
S
Shaohua Li 已提交
3195
		return true;
S
Shaohua Li 已提交
3196

S
Shaohua Li 已提交
3197
	return false;
S
Shaohua Li 已提交
3198 3199
}

3200
static bool cfq_may_dispatch(struct cfq_data *cfqd, struct cfq_queue *cfqq)
3201 3202
{
	unsigned int max_dispatch;
3203

3204 3205 3206
	/*
	 * Drain async requests before we start sync IO
	 */
3207
	if (cfq_should_idle(cfqd, cfqq) && cfqd->rq_in_flight[BLK_RW_ASYNC])
3208
		return false;
3209

3210 3211 3212
	/*
	 * If this is an async queue and we have sync IO in flight, let it wait
	 */
3213
	if (cfqd->rq_in_flight[BLK_RW_SYNC] && !cfq_cfqq_sync(cfqq))
3214
		return false;
3215

S
Shaohua Li 已提交
3216
	max_dispatch = max_t(unsigned int, cfqd->cfq_quantum / 2, 1);
3217 3218
	if (cfq_class_idle(cfqq))
		max_dispatch = 1;
3219

3220 3221 3222 3223
	/*
	 * Does this cfqq already have too much IO in flight?
	 */
	if (cfqq->dispatched >= max_dispatch) {
3224
		bool promote_sync = false;
3225 3226 3227
		/*
		 * idle queue must always only have a single IO in flight
		 */
3228
		if (cfq_class_idle(cfqq))
3229
			return false;
3230

3231
		/*
3232 3233
		 * If there is only one sync queue
		 * we can ignore async queue here and give the sync
3234 3235 3236 3237
		 * queue no dispatch limit. The reason is a sync queue can
		 * preempt async queue, limiting the sync queue doesn't make
		 * sense. This is useful for aiostress test.
		 */
3238 3239
		if (cfq_cfqq_sync(cfqq) && cfqd->busy_sync_queues == 1)
			promote_sync = true;
3240

3241 3242 3243
		/*
		 * We have other queues, don't allow more IO from this one
		 */
3244 3245
		if (cfqd->busy_queues > 1 && cfq_slice_used_soon(cfqd, cfqq) &&
				!promote_sync)
3246
			return false;
3247

3248
		/*
3249
		 * Sole queue user, no limit
3250
		 */
3251
		if (cfqd->busy_queues == 1 || promote_sync)
S
Shaohua Li 已提交
3252 3253 3254 3255 3256 3257 3258 3259 3260
			max_dispatch = -1;
		else
			/*
			 * Normally we start throttling cfqq when cfq_quantum/2
			 * requests have been dispatched. But we can drive
			 * deeper queue depths at the beginning of slice
			 * subjected to upper limit of cfq_quantum.
			 * */
			max_dispatch = cfqd->cfq_quantum;
3261 3262 3263 3264 3265 3266 3267
	}

	/*
	 * Async queues must wait a bit before being allowed dispatch.
	 * We also ramp up the dispatch depth gradually for async IO,
	 * based on the last sync IO we serviced
	 */
3268
	if (!cfq_cfqq_sync(cfqq) && cfqd->cfq_latency) {
3269
		unsigned long last_sync = jiffies - cfqd->last_delayed_sync;
3270
		unsigned int depth;
3271

3272
		depth = last_sync / cfqd->cfq_slice[1];
3273 3274
		if (!depth && !cfqq->dispatched)
			depth = 1;
3275 3276
		if (depth < max_dispatch)
			max_dispatch = depth;
3277
	}
3278

3279 3280 3281 3282 3283 3284 3285 3286 3287 3288 3289 3290 3291 3292 3293 3294 3295 3296 3297 3298 3299 3300 3301 3302 3303 3304 3305 3306 3307 3308 3309 3310
	/*
	 * If we're below the current max, allow a dispatch
	 */
	return cfqq->dispatched < max_dispatch;
}

/*
 * Dispatch a request from cfqq, moving them to the request queue
 * dispatch list.
 */
static bool cfq_dispatch_request(struct cfq_data *cfqd, struct cfq_queue *cfqq)
{
	struct request *rq;

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

	if (!cfq_may_dispatch(cfqd, cfqq))
		return false;

	/*
	 * 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) {
3311
		struct cfq_io_cq *cic = RQ_CIC(rq);
3312

3313
		atomic_long_inc(&cic->icq.ioc->refcount);
3314 3315 3316 3317 3318 3319 3320 3321 3322 3323 3324 3325 3326 3327 3328 3329 3330 3331 3332 3333 3334 3335 3336
		cfqd->active_cic = cic;
	}

	return true;
}

/*
 * Find the cfqq that we need to service and move a request from that to the
 * dispatch list
 */
static int cfq_dispatch_requests(struct request_queue *q, int force)
{
	struct cfq_data *cfqd = q->elevator->elevator_data;
	struct cfq_queue *cfqq;

	if (!cfqd->busy_queues)
		return 0;

	if (unlikely(force))
		return cfq_forced_dispatch(cfqd);

	cfqq = cfq_select_queue(cfqd);
	if (!cfqq)
3337 3338
		return 0;

3339
	/*
3340
	 * Dispatch a request from this cfqq, if it is allowed
3341
	 */
3342 3343 3344
	if (!cfq_dispatch_request(cfqd, cfqq))
		return 0;

3345
	cfqq->slice_dispatch++;
3346
	cfq_clear_cfqq_must_dispatch(cfqq);
3347

3348 3349 3350 3351 3352 3353 3354 3355
	/*
	 * 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;
3356
		cfq_slice_expired(cfqd, 0);
L
Linus Torvalds 已提交
3357 3358
	}

3359
	cfq_log_cfqq(cfqd, cfqq, "dispatched a request");
3360
	return 1;
L
Linus Torvalds 已提交
3361 3362 3363
}

/*
J
Jens Axboe 已提交
3364 3365
 * 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 已提交
3366
 *
3367
 * Each cfq queue took a reference on the parent group. Drop it now.
L
Linus Torvalds 已提交
3368 3369 3370 3371
 * queue lock must be held here.
 */
static void cfq_put_queue(struct cfq_queue *cfqq)
{
3372
	struct cfq_data *cfqd = cfqq->cfqd;
3373
	struct cfq_group *cfqg;
3374

3375
	BUG_ON(cfqq->ref <= 0);
L
Linus Torvalds 已提交
3376

3377 3378
	cfqq->ref--;
	if (cfqq->ref)
L
Linus Torvalds 已提交
3379 3380
		return;

3381
	cfq_log_cfqq(cfqd, cfqq, "put_queue");
L
Linus Torvalds 已提交
3382
	BUG_ON(rb_first(&cfqq->sort_list));
3383
	BUG_ON(cfqq->allocated[READ] + cfqq->allocated[WRITE]);
3384
	cfqg = cfqq->cfqg;
L
Linus Torvalds 已提交
3385

3386
	if (unlikely(cfqd->active_queue == cfqq)) {
3387
		__cfq_slice_expired(cfqd, cfqq, 0);
3388
		cfq_schedule_dispatch(cfqd);
3389
	}
3390

3391
	BUG_ON(cfq_cfqq_on_rr(cfqq));
L
Linus Torvalds 已提交
3392
	kmem_cache_free(cfq_pool, cfqq);
3393
	cfqg_put(cfqg);
L
Linus Torvalds 已提交
3394 3395
}

3396
static void cfq_put_cooperator(struct cfq_queue *cfqq)
L
Linus Torvalds 已提交
3397
{
J
Jeff Moyer 已提交
3398 3399 3400 3401 3402 3403 3404 3405 3406 3407 3408 3409 3410 3411 3412 3413 3414
	struct cfq_queue *__cfqq, *next;

	/*
	 * If this queue was scheduled to merge with another queue, be
	 * sure to drop the reference taken on that queue (and others in
	 * the merge chain).  See cfq_setup_merge and cfq_merge_cfqqs.
	 */
	__cfqq = cfqq->new_cfqq;
	while (__cfqq) {
		if (__cfqq == cfqq) {
			WARN(1, "cfqq->new_cfqq loop detected\n");
			break;
		}
		next = __cfqq->new_cfqq;
		cfq_put_queue(__cfqq);
		__cfqq = next;
	}
3415 3416 3417 3418 3419 3420 3421 3422 3423 3424
}

static void cfq_exit_cfqq(struct cfq_data *cfqd, struct cfq_queue *cfqq)
{
	if (unlikely(cfqq == cfqd->active_queue)) {
		__cfq_slice_expired(cfqd, cfqq, 0);
		cfq_schedule_dispatch(cfqd);
	}

	cfq_put_cooperator(cfqq);
J
Jeff Moyer 已提交
3425

3426 3427
	cfq_put_queue(cfqq);
}
3428

3429 3430 3431 3432 3433 3434 3435
static void cfq_init_icq(struct io_cq *icq)
{
	struct cfq_io_cq *cic = icq_to_cic(icq);

	cic->ttime.last_end_request = jiffies;
}

3436
static void cfq_exit_icq(struct io_cq *icq)
3437
{
3438
	struct cfq_io_cq *cic = icq_to_cic(icq);
3439
	struct cfq_data *cfqd = cic_to_cfqd(cic);
3440

3441 3442 3443
	if (cic->cfqq[BLK_RW_ASYNC]) {
		cfq_exit_cfqq(cfqd, cic->cfqq[BLK_RW_ASYNC]);
		cic->cfqq[BLK_RW_ASYNC] = NULL;
3444 3445
	}

3446 3447 3448
	if (cic->cfqq[BLK_RW_SYNC]) {
		cfq_exit_cfqq(cfqd, cic->cfqq[BLK_RW_SYNC]);
		cic->cfqq[BLK_RW_SYNC] = NULL;
3449
	}
3450 3451
}

3452
static void cfq_init_prio_data(struct cfq_queue *cfqq, struct cfq_io_cq *cic)
3453 3454 3455 3456
{
	struct task_struct *tsk = current;
	int ioprio_class;

J
Jens Axboe 已提交
3457
	if (!cfq_cfqq_prio_changed(cfqq))
3458 3459
		return;

T
Tejun Heo 已提交
3460
	ioprio_class = IOPRIO_PRIO_CLASS(cic->ioprio);
3461
	switch (ioprio_class) {
3462 3463 3464 3465
	default:
		printk(KERN_ERR "cfq: bad prio %x\n", ioprio_class);
	case IOPRIO_CLASS_NONE:
		/*
3466
		 * no prio set, inherit CPU scheduling settings
3467 3468
		 */
		cfqq->ioprio = task_nice_ioprio(tsk);
3469
		cfqq->ioprio_class = task_nice_ioclass(tsk);
3470 3471
		break;
	case IOPRIO_CLASS_RT:
T
Tejun Heo 已提交
3472
		cfqq->ioprio = IOPRIO_PRIO_DATA(cic->ioprio);
3473 3474 3475
		cfqq->ioprio_class = IOPRIO_CLASS_RT;
		break;
	case IOPRIO_CLASS_BE:
T
Tejun Heo 已提交
3476
		cfqq->ioprio = IOPRIO_PRIO_DATA(cic->ioprio);
3477 3478 3479 3480 3481 3482 3483
		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;
3484 3485 3486 3487 3488 3489 3490
	}

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

T
Tejun Heo 已提交
3494
static void check_ioprio_changed(struct cfq_io_cq *cic, struct bio *bio)
3495
{
T
Tejun Heo 已提交
3496
	int ioprio = cic->icq.ioc->ioprio;
3497
	struct cfq_data *cfqd = cic_to_cfqd(cic);
3498
	struct cfq_queue *cfqq;
3499

T
Tejun Heo 已提交
3500 3501 3502 3503 3504
	/*
	 * Check whether ioprio has changed.  The condition may trigger
	 * spuriously on a newly created cic but there's no harm.
	 */
	if (unlikely(!cfqd) || likely(cic->ioprio == ioprio))
3505 3506
		return;

3507
	cfqq = cic->cfqq[BLK_RW_ASYNC];
3508 3509
	if (cfqq) {
		struct cfq_queue *new_cfqq;
3510 3511
		new_cfqq = cfq_get_queue(cfqd, BLK_RW_ASYNC, cic, bio,
					 GFP_ATOMIC);
3512
		if (new_cfqq) {
3513
			cic->cfqq[BLK_RW_ASYNC] = new_cfqq;
3514 3515
			cfq_put_queue(cfqq);
		}
3516
	}
3517

3518
	cfqq = cic->cfqq[BLK_RW_SYNC];
3519 3520
	if (cfqq)
		cfq_mark_cfqq_prio_changed(cfqq);
T
Tejun Heo 已提交
3521 3522

	cic->ioprio = ioprio;
3523 3524
}

3525
static void cfq_init_cfqq(struct cfq_data *cfqd, struct cfq_queue *cfqq,
3526
			  pid_t pid, bool is_sync)
3527 3528 3529 3530 3531
{
	RB_CLEAR_NODE(&cfqq->rb_node);
	RB_CLEAR_NODE(&cfqq->p_node);
	INIT_LIST_HEAD(&cfqq->fifo);

3532
	cfqq->ref = 0;
3533 3534 3535 3536 3537 3538 3539 3540 3541 3542 3543 3544
	cfqq->cfqd = cfqd;

	cfq_mark_cfqq_prio_changed(cfqq);

	if (is_sync) {
		if (!cfq_class_idle(cfqq))
			cfq_mark_cfqq_idle_window(cfqq);
		cfq_mark_cfqq_sync(cfqq);
	}
	cfqq->pid = pid;
}

3545
#ifdef CONFIG_CFQ_GROUP_IOSCHED
T
Tejun Heo 已提交
3546
static void check_blkcg_changed(struct cfq_io_cq *cic, struct bio *bio)
3547
{
3548
	struct cfq_data *cfqd = cic_to_cfqd(cic);
T
Tejun Heo 已提交
3549
	struct cfq_queue *sync_cfqq;
T
Tejun Heo 已提交
3550
	uint64_t serial_nr;
3551

T
Tejun Heo 已提交
3552
	rcu_read_lock();
T
Tejun Heo 已提交
3553
	serial_nr = bio_blkcg(bio)->css.serial_nr;
T
Tejun Heo 已提交
3554
	rcu_read_unlock();
3555

T
Tejun Heo 已提交
3556 3557 3558 3559
	/*
	 * Check whether blkcg has changed.  The condition may trigger
	 * spuriously on a newly created cic but there's no harm.
	 */
T
Tejun Heo 已提交
3560
	if (unlikely(!cfqd) || likely(cic->blkcg_serial_nr == serial_nr))
T
Tejun Heo 已提交
3561
		return;
3562

T
Tejun Heo 已提交
3563
	sync_cfqq = cic_to_cfqq(cic, 1);
3564 3565 3566 3567 3568 3569 3570 3571 3572
	if (sync_cfqq) {
		/*
		 * Drop reference to sync queue. A new sync queue will be
		 * assigned in new group upon arrival of a fresh request.
		 */
		cfq_log_cfqq(cfqd, sync_cfqq, "changed cgroup");
		cic_set_cfqq(cic, NULL, 1);
		cfq_put_queue(sync_cfqq);
	}
T
Tejun Heo 已提交
3573

T
Tejun Heo 已提交
3574
	cic->blkcg_serial_nr = serial_nr;
3575
}
T
Tejun Heo 已提交
3576 3577
#else
static inline void check_blkcg_changed(struct cfq_io_cq *cic, struct bio *bio) { }
3578 3579
#endif  /* CONFIG_CFQ_GROUP_IOSCHED */

3580
static struct cfq_queue *
3581 3582
cfq_find_alloc_queue(struct cfq_data *cfqd, bool is_sync, struct cfq_io_cq *cic,
		     struct bio *bio, gfp_t gfp_mask)
3583
{
T
Tejun Heo 已提交
3584
	struct blkcg *blkcg;
3585
	struct cfq_queue *cfqq, *new_cfqq = NULL;
3586
	struct cfq_group *cfqg;
3587 3588

retry:
3589 3590
	rcu_read_lock();

T
Tejun Heo 已提交
3591
	blkcg = bio_blkcg(bio);
3592
	cfqg = cfq_lookup_create_cfqg(cfqd, blkcg);
3593 3594 3595 3596 3597
	if (!cfqg) {
		cfqq = &cfqd->oom_cfqq;
		goto out;
	}

3598
	cfqq = cic_to_cfqq(cic, is_sync);
3599

3600 3601 3602 3603 3604 3605
	/*
	 * Always try a new alloc if we fell back to the OOM cfqq
	 * originally, since it should just be a temporary situation.
	 */
	if (!cfqq || cfqq == &cfqd->oom_cfqq) {
		cfqq = NULL;
3606 3607 3608 3609
		if (new_cfqq) {
			cfqq = new_cfqq;
			new_cfqq = NULL;
		} else if (gfp_mask & __GFP_WAIT) {
3610
			rcu_read_unlock();
3611
			spin_unlock_irq(cfqd->queue->queue_lock);
3612
			new_cfqq = kmem_cache_alloc_node(cfq_pool,
3613
					gfp_mask | __GFP_ZERO,
3614
					cfqd->queue->node);
3615
			spin_lock_irq(cfqd->queue->queue_lock);
3616 3617
			if (new_cfqq)
				goto retry;
3618 3619
			else
				return &cfqd->oom_cfqq;
3620
		} else {
3621 3622 3623
			cfqq = kmem_cache_alloc_node(cfq_pool,
					gfp_mask | __GFP_ZERO,
					cfqd->queue->node);
3624 3625
		}

3626 3627
		if (cfqq) {
			cfq_init_cfqq(cfqd, cfqq, current->pid, is_sync);
3628
			cfq_init_prio_data(cfqq, cic);
3629
			cfq_link_cfqq_cfqg(cfqq, cfqg);
3630 3631 3632
			cfq_log_cfqq(cfqd, cfqq, "alloced");
		} else
			cfqq = &cfqd->oom_cfqq;
3633
	}
3634
out:
3635 3636 3637
	if (new_cfqq)
		kmem_cache_free(cfq_pool, new_cfqq);

3638
	rcu_read_unlock();
3639 3640 3641
	return cfqq;
}

3642 3643 3644
static struct cfq_queue **
cfq_async_queue_prio(struct cfq_data *cfqd, int ioprio_class, int ioprio)
{
3645
	switch (ioprio_class) {
3646 3647
	case IOPRIO_CLASS_RT:
		return &cfqd->async_cfqq[0][ioprio];
T
Tejun Heo 已提交
3648 3649 3650
	case IOPRIO_CLASS_NONE:
		ioprio = IOPRIO_NORM;
		/* fall through */
3651 3652 3653 3654 3655 3656 3657 3658 3659
	case IOPRIO_CLASS_BE:
		return &cfqd->async_cfqq[1][ioprio];
	case IOPRIO_CLASS_IDLE:
		return &cfqd->async_idle_cfqq;
	default:
		BUG();
	}
}

3660
static struct cfq_queue *
3661
cfq_get_queue(struct cfq_data *cfqd, bool is_sync, struct cfq_io_cq *cic,
3662
	      struct bio *bio, gfp_t gfp_mask)
3663
{
3664 3665
	int ioprio_class = IOPRIO_PRIO_CLASS(cic->ioprio);
	int ioprio = IOPRIO_PRIO_DATA(cic->ioprio);
3666
	struct cfq_queue **async_cfqq = NULL;
3667 3668
	struct cfq_queue *cfqq = NULL;

3669
	if (!is_sync) {
3670 3671 3672 3673 3674
		if (!ioprio_valid(cic->ioprio)) {
			struct task_struct *tsk = current;
			ioprio = task_nice_ioprio(tsk);
			ioprio_class = task_nice_ioclass(tsk);
		}
3675 3676 3677 3678
		async_cfqq = cfq_async_queue_prio(cfqd, ioprio_class, ioprio);
		cfqq = *async_cfqq;
	}

3679
	if (!cfqq)
3680
		cfqq = cfq_find_alloc_queue(cfqd, is_sync, cic, bio, gfp_mask);
3681 3682 3683 3684

	/*
	 * pin the queue now that it's allocated, scheduler exit will prune it
	 */
3685
	if (!is_sync && !(*async_cfqq)) {
3686
		cfqq->ref++;
3687
		*async_cfqq = cfqq;
3688 3689
	}

3690
	cfqq->ref++;
3691 3692 3693
	return cfqq;
}

3694
static void
3695
__cfq_update_io_thinktime(struct cfq_ttime *ttime, unsigned long slice_idle)
L
Linus Torvalds 已提交
3696
{
3697 3698
	unsigned long elapsed = jiffies - ttime->last_end_request;
	elapsed = min(elapsed, 2UL * slice_idle);
3699

3700 3701 3702 3703 3704 3705 3706
	ttime->ttime_samples = (7*ttime->ttime_samples + 256) / 8;
	ttime->ttime_total = (7*ttime->ttime_total + 256*elapsed) / 8;
	ttime->ttime_mean = (ttime->ttime_total + 128) / ttime->ttime_samples;
}

static void
cfq_update_io_thinktime(struct cfq_data *cfqd, struct cfq_queue *cfqq,
3707
			struct cfq_io_cq *cic)
3708
{
3709
	if (cfq_cfqq_sync(cfqq)) {
3710
		__cfq_update_io_thinktime(&cic->ttime, cfqd->cfq_slice_idle);
3711 3712 3713
		__cfq_update_io_thinktime(&cfqq->service_tree->ttime,
			cfqd->cfq_slice_idle);
	}
S
Shaohua Li 已提交
3714 3715 3716
#ifdef CONFIG_CFQ_GROUP_IOSCHED
	__cfq_update_io_thinktime(&cfqq->cfqg->ttime, cfqd->cfq_group_idle);
#endif
3717
}
L
Linus Torvalds 已提交
3718

3719
static void
3720
cfq_update_io_seektime(struct cfq_data *cfqd, struct cfq_queue *cfqq,
J
Jens Axboe 已提交
3721
		       struct request *rq)
3722
{
3723
	sector_t sdist = 0;
3724
	sector_t n_sec = blk_rq_sectors(rq);
3725 3726 3727 3728 3729 3730
	if (cfqq->last_request_pos) {
		if (cfqq->last_request_pos < blk_rq_pos(rq))
			sdist = blk_rq_pos(rq) - cfqq->last_request_pos;
		else
			sdist = cfqq->last_request_pos - blk_rq_pos(rq);
	}
3731

3732
	cfqq->seek_history <<= 1;
3733 3734 3735 3736
	if (blk_queue_nonrot(cfqd->queue))
		cfqq->seek_history |= (n_sec < CFQQ_SECT_THR_NONROT);
	else
		cfqq->seek_history |= (sdist > CFQQ_SEEK_THR);
3737
}
L
Linus Torvalds 已提交
3738

3739 3740 3741 3742 3743 3744
/*
 * 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,
3745
		       struct cfq_io_cq *cic)
3746
{
3747
	int old_idle, enable_idle;
3748

3749 3750 3751 3752
	/*
	 * Don't idle for async or idle io prio class
	 */
	if (!cfq_cfqq_sync(cfqq) || cfq_class_idle(cfqq))
3753 3754
		return;

3755
	enable_idle = old_idle = cfq_cfqq_idle_window(cfqq);
L
Linus Torvalds 已提交
3756

3757 3758 3759
	if (cfqq->queued[0] + cfqq->queued[1] >= 4)
		cfq_mark_cfqq_deep(cfqq);

3760 3761
	if (cfqq->next_rq && (cfqq->next_rq->cmd_flags & REQ_NOIDLE))
		enable_idle = 0;
T
Tejun Heo 已提交
3762
	else if (!atomic_read(&cic->icq.ioc->active_ref) ||
3763 3764
		 !cfqd->cfq_slice_idle ||
		 (!cfq_cfqq_deep(cfqq) && CFQQ_SEEKY(cfqq)))
3765
		enable_idle = 0;
3766 3767
	else if (sample_valid(cic->ttime.ttime_samples)) {
		if (cic->ttime.ttime_mean > cfqd->cfq_slice_idle)
3768 3769 3770
			enable_idle = 0;
		else
			enable_idle = 1;
L
Linus Torvalds 已提交
3771 3772
	}

3773 3774 3775 3776 3777 3778 3779
	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);
	}
3780
}
L
Linus Torvalds 已提交
3781

3782 3783 3784 3785
/*
 * 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.
 */
3786
static bool
3787
cfq_should_preempt(struct cfq_data *cfqd, struct cfq_queue *new_cfqq,
J
Jens Axboe 已提交
3788
		   struct request *rq)
3789
{
J
Jens Axboe 已提交
3790
	struct cfq_queue *cfqq;
3791

J
Jens Axboe 已提交
3792 3793
	cfqq = cfqd->active_queue;
	if (!cfqq)
3794
		return false;
3795

J
Jens Axboe 已提交
3796
	if (cfq_class_idle(new_cfqq))
3797
		return false;
3798 3799

	if (cfq_class_idle(cfqq))
3800
		return true;
3801

3802 3803 3804 3805 3806 3807
	/*
	 * Don't allow a non-RT request to preempt an ongoing RT cfqq timeslice.
	 */
	if (cfq_class_rt(cfqq) && !cfq_class_rt(new_cfqq))
		return false;

3808 3809 3810 3811
	/*
	 * if the new request is sync, but the currently running queue is
	 * not, let the sync request have priority.
	 */
J
Jens Axboe 已提交
3812
	if (rq_is_sync(rq) && !cfq_cfqq_sync(cfqq))
3813
		return true;
3814

3815 3816 3817 3818 3819 3820 3821
	if (new_cfqq->cfqg != cfqq->cfqg)
		return false;

	if (cfq_slice_used(cfqq))
		return true;

	/* Allow preemption only if we are idling on sync-noidle tree */
3822
	if (cfqd->serving_wl_type == SYNC_NOIDLE_WORKLOAD &&
3823 3824 3825 3826 3827
	    cfqq_type(new_cfqq) == SYNC_NOIDLE_WORKLOAD &&
	    new_cfqq->service_tree->count == 2 &&
	    RB_EMPTY_ROOT(&cfqq->sort_list))
		return true;

3828 3829 3830 3831
	/*
	 * 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.
	 */
3832
	if ((rq->cmd_flags & REQ_PRIO) && !cfqq->prio_pending)
3833 3834
		return true;

3835 3836 3837 3838
	/*
	 * Allow an RT request to pre-empt an ongoing non-RT cfqq timeslice.
	 */
	if (cfq_class_rt(new_cfqq) && !cfq_class_rt(cfqq))
3839
		return true;
3840

3841 3842 3843 3844
	/* An idle queue should not be idle now for some reason */
	if (RB_EMPTY_ROOT(&cfqq->sort_list) && !cfq_should_idle(cfqd, cfqq))
		return true;

3845
	if (!cfqd->active_cic || !cfq_cfqq_wait_request(cfqq))
3846
		return false;
3847 3848 3849 3850 3851

	/*
	 * if this request is as-good as one we would expect from the
	 * current cfqq, let it preempt
	 */
3852
	if (cfq_rq_close(cfqd, cfqq, rq))
3853
		return true;
3854

3855
	return false;
3856 3857 3858 3859 3860 3861 3862 3863
}

/*
 * 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)
{
S
Shaohua Li 已提交
3864 3865
	enum wl_type_t old_type = cfqq_type(cfqd->active_queue);

3866
	cfq_log_cfqq(cfqd, cfqq, "preempt");
S
Shaohua Li 已提交
3867
	cfq_slice_expired(cfqd, 1);
3868

3869 3870 3871 3872
	/*
	 * workload type is changed, don't save slice, otherwise preempt
	 * doesn't happen
	 */
S
Shaohua Li 已提交
3873
	if (old_type != cfqq_type(cfqq))
3874
		cfqq->cfqg->saved_wl_slice = 0;
3875

3876 3877 3878 3879 3880
	/*
	 * 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));
3881 3882

	cfq_service_tree_add(cfqd, cfqq, 1);
3883

3884 3885
	cfqq->slice_end = 0;
	cfq_mark_cfqq_slice_new(cfqq);
3886 3887 3888
}

/*
J
Jens Axboe 已提交
3889
 * Called when a new fs request (rq) is added (to cfqq). Check if there's
3890 3891 3892
 * something we should do about it
 */
static void
J
Jens Axboe 已提交
3893 3894
cfq_rq_enqueued(struct cfq_data *cfqd, struct cfq_queue *cfqq,
		struct request *rq)
3895
{
3896
	struct cfq_io_cq *cic = RQ_CIC(rq);
3897

3898
	cfqd->rq_queued++;
3899 3900
	if (rq->cmd_flags & REQ_PRIO)
		cfqq->prio_pending++;
3901

3902
	cfq_update_io_thinktime(cfqd, cfqq, cic);
3903
	cfq_update_io_seektime(cfqd, cfqq, rq);
J
Jens Axboe 已提交
3904 3905
	cfq_update_idle_window(cfqd, cfqq, cic);

3906
	cfqq->last_request_pos = blk_rq_pos(rq) + blk_rq_sectors(rq);
3907 3908 3909

	if (cfqq == cfqd->active_queue) {
		/*
3910 3911 3912
		 * 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
3913 3914
		 * and merging. If the request is already larger than a single
		 * page, let it rip immediately. For that case we assume that
3915 3916 3917
		 * 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.
3918
		 */
3919
		if (cfq_cfqq_wait_request(cfqq)) {
3920 3921
			if (blk_rq_bytes(rq) > PAGE_CACHE_SIZE ||
			    cfqd->busy_queues > 1) {
3922
				cfq_del_timer(cfqd, cfqq);
3923
				cfq_clear_cfqq_wait_request(cfqq);
3924
				__blk_run_queue(cfqd->queue);
3925
			} else {
3926
				cfqg_stats_update_idle_time(cfqq->cfqg);
3927
				cfq_mark_cfqq_must_dispatch(cfqq);
3928
			}
3929
		}
J
Jens Axboe 已提交
3930
	} else if (cfq_should_preempt(cfqd, cfqq, rq)) {
3931 3932 3933
		/*
		 * not the active queue - expire current slice if it is
		 * idle and has expired it's mean thinktime or this new queue
3934 3935
		 * has some old slice time left and is of higher priority or
		 * this new queue is RT and the current one is BE
3936 3937
		 */
		cfq_preempt_queue(cfqd, cfqq);
3938
		__blk_run_queue(cfqd->queue);
3939
	}
L
Linus Torvalds 已提交
3940 3941
}

3942
static void cfq_insert_request(struct request_queue *q, struct request *rq)
L
Linus Torvalds 已提交
3943
{
3944
	struct cfq_data *cfqd = q->elevator->elevator_data;
J
Jens Axboe 已提交
3945
	struct cfq_queue *cfqq = RQ_CFQQ(rq);
3946

3947
	cfq_log_cfqq(cfqd, cfqq, "insert_request");
3948
	cfq_init_prio_data(cfqq, RQ_CIC(rq));
L
Linus Torvalds 已提交
3949

3950
	rq->fifo_time = jiffies + cfqd->cfq_fifo_expire[rq_is_sync(rq)];
3951
	list_add_tail(&rq->queuelist, &cfqq->fifo);
3952
	cfq_add_rq_rb(rq);
3953 3954
	cfqg_stats_update_io_add(RQ_CFQG(rq), cfqd->serving_group,
				 rq->cmd_flags);
J
Jens Axboe 已提交
3955
	cfq_rq_enqueued(cfqd, cfqq, rq);
L
Linus Torvalds 已提交
3956 3957
}

3958 3959 3960 3961 3962 3963
/*
 * Update hw_tag based on peak queue depth over 50 samples under
 * sufficient load.
 */
static void cfq_update_hw_tag(struct cfq_data *cfqd)
{
S
Shaohua Li 已提交
3964 3965
	struct cfq_queue *cfqq = cfqd->active_queue;

3966 3967
	if (cfqd->rq_in_driver > cfqd->hw_tag_est_depth)
		cfqd->hw_tag_est_depth = cfqd->rq_in_driver;
3968 3969 3970

	if (cfqd->hw_tag == 1)
		return;
3971 3972

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

S
Shaohua Li 已提交
3976 3977 3978 3979 3980 3981 3982
	/*
	 * If active queue hasn't enough requests and can idle, cfq might not
	 * dispatch sufficient requests to hardware. Don't zero hw_tag in this
	 * case
	 */
	if (cfqq && cfq_cfqq_idle_window(cfqq) &&
	    cfqq->dispatched + cfqq->queued[0] + cfqq->queued[1] <
3983
	    CFQ_HW_QUEUE_MIN && cfqd->rq_in_driver < CFQ_HW_QUEUE_MIN)
S
Shaohua Li 已提交
3984 3985
		return;

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

3989
	if (cfqd->hw_tag_est_depth >= CFQ_HW_QUEUE_MIN)
3990 3991 3992 3993 3994
		cfqd->hw_tag = 1;
	else
		cfqd->hw_tag = 0;
}

3995 3996
static bool cfq_should_wait_busy(struct cfq_data *cfqd, struct cfq_queue *cfqq)
{
3997
	struct cfq_io_cq *cic = cfqd->active_cic;
3998

3999 4000 4001 4002
	/* If the queue already has requests, don't wait */
	if (!RB_EMPTY_ROOT(&cfqq->sort_list))
		return false;

4003 4004 4005 4006
	/* If there are other queues in the group, don't wait */
	if (cfqq->cfqg->nr_cfqq > 1)
		return false;

S
Shaohua Li 已提交
4007 4008 4009 4010
	/* the only queue in the group, but think time is big */
	if (cfq_io_thinktime_big(cfqd, &cfqq->cfqg->ttime, true))
		return false;

4011 4012 4013 4014
	if (cfq_slice_used(cfqq))
		return true;

	/* if slice left is less than think time, wait busy */
4015 4016
	if (cic && sample_valid(cic->ttime.ttime_samples)
	    && (cfqq->slice_end - jiffies < cic->ttime.ttime_mean))
4017 4018 4019 4020 4021 4022 4023 4024 4025 4026 4027 4028 4029 4030 4031
		return true;

	/*
	 * If think times is less than a jiffy than ttime_mean=0 and above
	 * will not be true. It might happen that slice has not expired yet
	 * but will expire soon (4-5 ns) during select_queue(). To cover the
	 * case where think time is less than a jiffy, mark the queue wait
	 * busy if only 1 jiffy is left in the slice.
	 */
	if (cfqq->slice_end - jiffies == 1)
		return true;

	return false;
}

4032
static void cfq_completed_request(struct request_queue *q, struct request *rq)
L
Linus Torvalds 已提交
4033
{
J
Jens Axboe 已提交
4034
	struct cfq_queue *cfqq = RQ_CFQQ(rq);
4035
	struct cfq_data *cfqd = cfqq->cfqd;
4036
	const int sync = rq_is_sync(rq);
4037
	unsigned long now;
L
Linus Torvalds 已提交
4038

4039
	now = jiffies;
4040 4041
	cfq_log_cfqq(cfqd, cfqq, "complete rqnoidle %d",
		     !!(rq->cmd_flags & REQ_NOIDLE));
L
Linus Torvalds 已提交
4042

4043 4044
	cfq_update_hw_tag(cfqd);

4045
	WARN_ON(!cfqd->rq_in_driver);
J
Jens Axboe 已提交
4046
	WARN_ON(!cfqq->dispatched);
4047
	cfqd->rq_in_driver--;
J
Jens Axboe 已提交
4048
	cfqq->dispatched--;
4049
	(RQ_CFQG(rq))->dispatched--;
4050 4051
	cfqg_stats_update_completion(cfqq->cfqg, rq_start_time_ns(rq),
				     rq_io_start_time_ns(rq), rq->cmd_flags);
L
Linus Torvalds 已提交
4052

4053
	cfqd->rq_in_flight[cfq_cfqq_sync(cfqq)]--;
4054

4055
	if (sync) {
4056
		struct cfq_rb_root *st;
4057

4058
		RQ_CIC(rq)->ttime.last_end_request = now;
4059 4060

		if (cfq_cfqq_on_rr(cfqq))
4061
			st = cfqq->service_tree;
4062
		else
4063 4064 4065 4066
			st = st_for(cfqq->cfqg, cfqq_class(cfqq),
					cfqq_type(cfqq));

		st->ttime.last_end_request = now;
4067 4068
		if (!time_after(rq->start_time + cfqd->cfq_fifo_expire[1], now))
			cfqd->last_delayed_sync = now;
4069
	}
4070

S
Shaohua Li 已提交
4071 4072 4073 4074
#ifdef CONFIG_CFQ_GROUP_IOSCHED
	cfqq->cfqg->ttime.last_end_request = now;
#endif

4075 4076 4077 4078 4079
	/*
	 * 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) {
4080 4081
		const bool cfqq_empty = RB_EMPTY_ROOT(&cfqq->sort_list);

4082 4083 4084 4085
		if (cfq_cfqq_slice_new(cfqq)) {
			cfq_set_prio_slice(cfqd, cfqq);
			cfq_clear_cfqq_slice_new(cfqq);
		}
4086 4087

		/*
4088 4089
		 * Should we wait for next request to come in before we expire
		 * the queue.
4090
		 */
4091
		if (cfq_should_wait_busy(cfqd, cfqq)) {
4092 4093 4094 4095
			unsigned long extend_sl = cfqd->cfq_slice_idle;
			if (!cfqd->cfq_slice_idle)
				extend_sl = cfqd->cfq_group_idle;
			cfqq->slice_end = jiffies + extend_sl;
4096
			cfq_mark_cfqq_wait_busy(cfqq);
4097
			cfq_log_cfqq(cfqd, cfqq, "will busy wait");
4098 4099
		}

4100
		/*
4101 4102 4103 4104 4105 4106
		 * Idling is not enabled on:
		 * - expired queues
		 * - idle-priority queues
		 * - async queues
		 * - queues with still some requests queued
		 * - when there is a close cooperator
4107
		 */
4108
		if (cfq_slice_used(cfqq) || cfq_class_idle(cfqq))
4109
			cfq_slice_expired(cfqd, 1);
4110 4111
		else if (sync && cfqq_empty &&
			 !cfq_close_cooperator(cfqd, cfqq)) {
4112
			cfq_arm_slice_timer(cfqd);
4113
		}
4114
	}
J
Jens Axboe 已提交
4115

4116
	if (!cfqd->rq_in_driver)
4117
		cfq_schedule_dispatch(cfqd);
L
Linus Torvalds 已提交
4118 4119
}

4120
static inline int __cfq_may_queue(struct cfq_queue *cfqq)
4121
{
4122
	if (cfq_cfqq_wait_request(cfqq) && !cfq_cfqq_must_alloc_slice(cfqq)) {
J
Jens Axboe 已提交
4123
		cfq_mark_cfqq_must_alloc_slice(cfqq);
4124
		return ELV_MQUEUE_MUST;
J
Jens Axboe 已提交
4125
	}
L
Linus Torvalds 已提交
4126

4127 4128 4129
	return ELV_MQUEUE_MAY;
}

4130
static int cfq_may_queue(struct request_queue *q, int rw)
4131 4132 4133
{
	struct cfq_data *cfqd = q->elevator->elevator_data;
	struct task_struct *tsk = current;
4134
	struct cfq_io_cq *cic;
4135 4136 4137 4138 4139 4140 4141 4142
	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
	 */
4143
	cic = cfq_cic_lookup(cfqd, tsk->io_context);
4144 4145 4146
	if (!cic)
		return ELV_MQUEUE_MAY;

4147
	cfqq = cic_to_cfqq(cic, rw_is_sync(rw));
4148
	if (cfqq) {
4149
		cfq_init_prio_data(cfqq, cic);
4150

4151
		return __cfq_may_queue(cfqq);
4152 4153 4154
	}

	return ELV_MQUEUE_MAY;
L
Linus Torvalds 已提交
4155 4156 4157 4158 4159
}

/*
 * queue lock held here
 */
4160
static void cfq_put_request(struct request *rq)
L
Linus Torvalds 已提交
4161
{
J
Jens Axboe 已提交
4162
	struct cfq_queue *cfqq = RQ_CFQQ(rq);
L
Linus Torvalds 已提交
4163

J
Jens Axboe 已提交
4164
	if (cfqq) {
4165
		const int rw = rq_data_dir(rq);
L
Linus Torvalds 已提交
4166

4167 4168
		BUG_ON(!cfqq->allocated[rw]);
		cfqq->allocated[rw]--;
L
Linus Torvalds 已提交
4169

4170
		/* Put down rq reference on cfqg */
4171
		cfqg_put(RQ_CFQG(rq));
4172 4173
		rq->elv.priv[0] = NULL;
		rq->elv.priv[1] = NULL;
4174

L
Linus Torvalds 已提交
4175 4176 4177 4178
		cfq_put_queue(cfqq);
	}
}

J
Jeff Moyer 已提交
4179
static struct cfq_queue *
4180
cfq_merge_cfqqs(struct cfq_data *cfqd, struct cfq_io_cq *cic,
J
Jeff Moyer 已提交
4181 4182 4183 4184
		struct cfq_queue *cfqq)
{
	cfq_log_cfqq(cfqd, cfqq, "merging with queue %p", cfqq->new_cfqq);
	cic_set_cfqq(cic, cfqq->new_cfqq, 1);
4185
	cfq_mark_cfqq_coop(cfqq->new_cfqq);
J
Jeff Moyer 已提交
4186 4187 4188 4189
	cfq_put_queue(cfqq);
	return cic_to_cfqq(cic, 1);
}

4190 4191 4192 4193 4194
/*
 * Returns NULL if a new cfqq should be allocated, or the old cfqq if this
 * was the last process referring to said cfqq.
 */
static struct cfq_queue *
4195
split_cfqq(struct cfq_io_cq *cic, struct cfq_queue *cfqq)
4196 4197 4198 4199
{
	if (cfqq_process_refs(cfqq) == 1) {
		cfqq->pid = current->pid;
		cfq_clear_cfqq_coop(cfqq);
4200
		cfq_clear_cfqq_split_coop(cfqq);
4201 4202 4203 4204
		return cfqq;
	}

	cic_set_cfqq(cic, NULL, 1);
4205 4206 4207

	cfq_put_cooperator(cfqq);

4208 4209 4210
	cfq_put_queue(cfqq);
	return NULL;
}
L
Linus Torvalds 已提交
4211
/*
4212
 * Allocate cfq data structures associated with this request.
L
Linus Torvalds 已提交
4213
 */
4214
static int
4215 4216
cfq_set_request(struct request_queue *q, struct request *rq, struct bio *bio,
		gfp_t gfp_mask)
L
Linus Torvalds 已提交
4217 4218
{
	struct cfq_data *cfqd = q->elevator->elevator_data;
4219
	struct cfq_io_cq *cic = icq_to_cic(rq->elv.icq);
L
Linus Torvalds 已提交
4220
	const int rw = rq_data_dir(rq);
4221
	const bool is_sync = rq_is_sync(rq);
4222
	struct cfq_queue *cfqq;
L
Linus Torvalds 已提交
4223 4224 4225

	might_sleep_if(gfp_mask & __GFP_WAIT);

4226
	spin_lock_irq(q->queue_lock);
4227

T
Tejun Heo 已提交
4228 4229
	check_ioprio_changed(cic, bio);
	check_blkcg_changed(cic, bio);
4230
new_queue:
4231
	cfqq = cic_to_cfqq(cic, is_sync);
4232
	if (!cfqq || cfqq == &cfqd->oom_cfqq) {
4233
		cfqq = cfq_get_queue(cfqd, is_sync, cic, bio, gfp_mask);
4234
		cic_set_cfqq(cic, cfqq, is_sync);
J
Jeff Moyer 已提交
4235
	} else {
4236 4237 4238
		/*
		 * If the queue was seeky for too long, break it apart.
		 */
4239
		if (cfq_cfqq_coop(cfqq) && cfq_cfqq_split_coop(cfqq)) {
4240 4241 4242 4243 4244 4245
			cfq_log_cfqq(cfqd, cfqq, "breaking apart cfqq");
			cfqq = split_cfqq(cic, cfqq);
			if (!cfqq)
				goto new_queue;
		}

J
Jeff Moyer 已提交
4246 4247 4248 4249 4250 4251 4252 4253
		/*
		 * Check to see if this queue is scheduled to merge with
		 * another, closely cooperating queue.  The merging of
		 * queues happens here as it must be done in process context.
		 * The reference on new_cfqq was taken in merge_cfqqs.
		 */
		if (cfqq->new_cfqq)
			cfqq = cfq_merge_cfqqs(cfqd, cic, cfqq);
4254
	}
L
Linus Torvalds 已提交
4255 4256 4257

	cfqq->allocated[rw]++;

4258
	cfqq->ref++;
4259
	cfqg_get(cfqq->cfqg);
4260
	rq->elv.priv[0] = cfqq;
T
Tejun Heo 已提交
4261
	rq->elv.priv[1] = cfqq->cfqg;
4262
	spin_unlock_irq(q->queue_lock);
J
Jens Axboe 已提交
4263
	return 0;
L
Linus Torvalds 已提交
4264 4265
}

4266
static void cfq_kick_queue(struct work_struct *work)
4267
{
4268
	struct cfq_data *cfqd =
4269
		container_of(work, struct cfq_data, unplug_work);
4270
	struct request_queue *q = cfqd->queue;
4271

4272
	spin_lock_irq(q->queue_lock);
4273
	__blk_run_queue(cfqd->queue);
4274
	spin_unlock_irq(q->queue_lock);
4275 4276 4277 4278 4279 4280 4281 4282 4283 4284
}

/*
 * 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;
4285
	int timed_out = 1;
4286

4287 4288
	cfq_log(cfqd, "idle timer fired");

4289 4290
	spin_lock_irqsave(cfqd->queue->queue_lock, flags);

4291 4292
	cfqq = cfqd->active_queue;
	if (cfqq) {
4293 4294
		timed_out = 0;

4295 4296 4297 4298 4299 4300
		/*
		 * We saw a request before the queue expired, let it through
		 */
		if (cfq_cfqq_must_dispatch(cfqq))
			goto out_kick;

4301 4302 4303
		/*
		 * expired
		 */
4304
		if (cfq_slice_used(cfqq))
4305 4306 4307 4308 4309 4310
			goto expire;

		/*
		 * only expire and reinvoke request handler, if there are
		 * other queues with pending requests
		 */
4311
		if (!cfqd->busy_queues)
4312 4313 4314 4315 4316
			goto out_cont;

		/*
		 * not expired and it has a request pending, let it dispatch
		 */
4317
		if (!RB_EMPTY_ROOT(&cfqq->sort_list))
4318
			goto out_kick;
4319 4320 4321 4322 4323

		/*
		 * Queue depth flag is reset only when the idle didn't succeed
		 */
		cfq_clear_cfqq_deep(cfqq);
4324 4325
	}
expire:
4326
	cfq_slice_expired(cfqd, timed_out);
4327
out_kick:
4328
	cfq_schedule_dispatch(cfqd);
4329 4330 4331 4332
out_cont:
	spin_unlock_irqrestore(cfqd->queue->queue_lock, flags);
}

J
Jens Axboe 已提交
4333 4334 4335
static void cfq_shutdown_timer_wq(struct cfq_data *cfqd)
{
	del_timer_sync(&cfqd->idle_slice_timer);
4336
	cancel_work_sync(&cfqd->unplug_work);
J
Jens Axboe 已提交
4337
}
4338

4339 4340 4341 4342 4343 4344 4345 4346 4347 4348
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]);
	}
4349 4350 4351

	if (cfqd->async_idle_cfqq)
		cfq_put_queue(cfqd->async_idle_cfqq);
4352 4353
}

J
Jens Axboe 已提交
4354
static void cfq_exit_queue(struct elevator_queue *e)
L
Linus Torvalds 已提交
4355
{
4356
	struct cfq_data *cfqd = e->elevator_data;
4357
	struct request_queue *q = cfqd->queue;
4358

J
Jens Axboe 已提交
4359
	cfq_shutdown_timer_wq(cfqd);
4360

4361
	spin_lock_irq(q->queue_lock);
4362

4363
	if (cfqd->active_queue)
4364
		__cfq_slice_expired(cfqd, cfqd->active_queue, 0);
4365

4366
	cfq_put_async_queues(cfqd);
4367 4368 4369

	spin_unlock_irq(q->queue_lock);

4370 4371
	cfq_shutdown_timer_wq(cfqd);

4372 4373 4374
#ifdef CONFIG_CFQ_GROUP_IOSCHED
	blkcg_deactivate_policy(q, &blkcg_policy_cfq);
#else
4375
	kfree(cfqd->root_group);
4376
#endif
4377
	kfree(cfqd);
L
Linus Torvalds 已提交
4378 4379
}

4380
static int cfq_init_queue(struct request_queue *q, struct elevator_type *e)
L
Linus Torvalds 已提交
4381 4382
{
	struct cfq_data *cfqd;
T
Tejun Heo 已提交
4383
	struct blkcg_gq *blkg __maybe_unused;
4384
	int i, ret;
4385 4386 4387 4388 4389
	struct elevator_queue *eq;

	eq = elevator_alloc(q, e);
	if (!eq)
		return -ENOMEM;
L
Linus Torvalds 已提交
4390

4391
	cfqd = kzalloc_node(sizeof(*cfqd), GFP_KERNEL, q->node);
4392 4393
	if (!cfqd) {
		kobject_put(&eq->kobj);
4394
		return -ENOMEM;
4395 4396
	}
	eq->elevator_data = cfqd;
4397

4398
	cfqd->queue = q;
4399 4400 4401
	spin_lock_irq(q->queue_lock);
	q->elevator = eq;
	spin_unlock_irq(q->queue_lock);
4402

4403 4404 4405
	/* Init root service tree */
	cfqd->grp_service_tree = CFQ_RB_ROOT;

4406
	/* Init root group and prefer root group over other groups by default */
4407
#ifdef CONFIG_CFQ_GROUP_IOSCHED
T
Tejun Heo 已提交
4408
	ret = blkcg_activate_policy(q, &blkcg_policy_cfq);
4409 4410
	if (ret)
		goto out_free;
4411

4412
	cfqd->root_group = blkg_to_cfqg(q->root_blkg);
4413
#else
4414
	ret = -ENOMEM;
4415 4416
	cfqd->root_group = kzalloc_node(sizeof(*cfqd->root_group),
					GFP_KERNEL, cfqd->queue->node);
4417 4418
	if (!cfqd->root_group)
		goto out_free;
4419

4420 4421
	cfq_init_cfqg_base(cfqd->root_group);
#endif
4422
	cfqd->root_group->weight = 2 * CFQ_WEIGHT_DEFAULT;
T
Tejun Heo 已提交
4423
	cfqd->root_group->leaf_weight = 2 * CFQ_WEIGHT_DEFAULT;
4424

4425 4426 4427 4428 4429 4430 4431 4432
	/*
	 * Not strictly needed (since RB_ROOT just clears the node and we
	 * zeroed cfqd on alloc), but better be safe in case someone decides
	 * to add magic to the rb code
	 */
	for (i = 0; i < CFQ_PRIO_LISTS; i++)
		cfqd->prio_trees[i] = RB_ROOT;

4433 4434 4435
	/*
	 * Our fallback cfqq if cfq_find_alloc_queue() runs into OOM issues.
	 * Grab a permanent reference to it, so that the normal code flow
4436 4437 4438
	 * will not attempt to free it.  oom_cfqq is linked to root_group
	 * but shouldn't hold a reference as it'll never be unlinked.  Lose
	 * the reference from linking right away.
4439 4440
	 */
	cfq_init_cfqq(cfqd, &cfqd->oom_cfqq, 1, 0);
4441
	cfqd->oom_cfqq.ref++;
T
Tejun Heo 已提交
4442 4443

	spin_lock_irq(q->queue_lock);
4444
	cfq_link_cfqq_cfqg(&cfqd->oom_cfqq, cfqd->root_group);
4445
	cfqg_put(cfqd->root_group);
T
Tejun Heo 已提交
4446
	spin_unlock_irq(q->queue_lock);
L
Linus Torvalds 已提交
4447

4448 4449 4450 4451
	init_timer(&cfqd->idle_slice_timer);
	cfqd->idle_slice_timer.function = cfq_idle_slice_timer;
	cfqd->idle_slice_timer.data = (unsigned long) cfqd;

4452
	INIT_WORK(&cfqd->unplug_work, cfq_kick_queue);
4453

L
Linus Torvalds 已提交
4454
	cfqd->cfq_quantum = cfq_quantum;
4455 4456
	cfqd->cfq_fifo_expire[0] = cfq_fifo_expire[0];
	cfqd->cfq_fifo_expire[1] = cfq_fifo_expire[1];
L
Linus Torvalds 已提交
4457 4458
	cfqd->cfq_back_max = cfq_back_max;
	cfqd->cfq_back_penalty = cfq_back_penalty;
4459 4460
	cfqd->cfq_slice[0] = cfq_slice_async;
	cfqd->cfq_slice[1] = cfq_slice_sync;
4461
	cfqd->cfq_target_latency = cfq_target_latency;
4462 4463
	cfqd->cfq_slice_async_rq = cfq_slice_async_rq;
	cfqd->cfq_slice_idle = cfq_slice_idle;
4464
	cfqd->cfq_group_idle = cfq_group_idle;
4465
	cfqd->cfq_latency = 1;
4466
	cfqd->hw_tag = -1;
4467 4468 4469 4470
	/*
	 * we optimistically start assuming sync ops weren't delayed in last
	 * second, in order to have larger depth for async operations.
	 */
4471
	cfqd->last_delayed_sync = jiffies - HZ;
4472
	return 0;
4473 4474 4475

out_free:
	kfree(cfqd);
4476
	kobject_put(&eq->kobj);
4477
	return ret;
L
Linus Torvalds 已提交
4478 4479 4480 4481 4482 4483 4484 4485
}

/*
 * sysfs parts below -->
 */
static ssize_t
cfq_var_show(unsigned int var, char *page)
{
4486
	return sprintf(page, "%u\n", var);
L
Linus Torvalds 已提交
4487 4488 4489 4490 4491 4492 4493 4494 4495 4496 4497 4498
}

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 已提交
4499
static ssize_t __FUNC(struct elevator_queue *e, char *page)		\
L
Linus Torvalds 已提交
4500
{									\
4501
	struct cfq_data *cfqd = e->elevator_data;			\
L
Linus Torvalds 已提交
4502 4503 4504 4505 4506 4507
	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);
4508 4509
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);
4510 4511
SHOW_FUNCTION(cfq_back_seek_max_show, cfqd->cfq_back_max, 0);
SHOW_FUNCTION(cfq_back_seek_penalty_show, cfqd->cfq_back_penalty, 0);
4512
SHOW_FUNCTION(cfq_slice_idle_show, cfqd->cfq_slice_idle, 1);
4513
SHOW_FUNCTION(cfq_group_idle_show, cfqd->cfq_group_idle, 1);
4514 4515 4516
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);
4517
SHOW_FUNCTION(cfq_low_latency_show, cfqd->cfq_latency, 0);
4518
SHOW_FUNCTION(cfq_target_latency_show, cfqd->cfq_target_latency, 1);
L
Linus Torvalds 已提交
4519 4520 4521
#undef SHOW_FUNCTION

#define STORE_FUNCTION(__FUNC, __PTR, MIN, MAX, __CONV)			\
J
Jens Axboe 已提交
4522
static ssize_t __FUNC(struct elevator_queue *e, const char *page, size_t count)	\
L
Linus Torvalds 已提交
4523
{									\
4524
	struct cfq_data *cfqd = e->elevator_data;			\
L
Linus Torvalds 已提交
4525 4526 4527 4528 4529 4530 4531 4532 4533 4534 4535 4536 4537
	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);
4538 4539 4540 4541
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);
4542
STORE_FUNCTION(cfq_back_seek_max_store, &cfqd->cfq_back_max, 0, UINT_MAX, 0);
4543 4544
STORE_FUNCTION(cfq_back_seek_penalty_store, &cfqd->cfq_back_penalty, 1,
		UINT_MAX, 0);
4545
STORE_FUNCTION(cfq_slice_idle_store, &cfqd->cfq_slice_idle, 0, UINT_MAX, 1);
4546
STORE_FUNCTION(cfq_group_idle_store, &cfqd->cfq_group_idle, 0, UINT_MAX, 1);
4547 4548
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);
4549 4550
STORE_FUNCTION(cfq_slice_async_rq_store, &cfqd->cfq_slice_async_rq, 1,
		UINT_MAX, 0);
4551
STORE_FUNCTION(cfq_low_latency_store, &cfqd->cfq_latency, 0, 1, 0);
4552
STORE_FUNCTION(cfq_target_latency_store, &cfqd->cfq_target_latency, 1, UINT_MAX, 1);
L
Linus Torvalds 已提交
4553 4554
#undef STORE_FUNCTION

4555 4556 4557 4558 4559 4560 4561 4562 4563 4564 4565 4566 4567
#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),
4568
	CFQ_ATTR(group_idle),
4569
	CFQ_ATTR(low_latency),
4570
	CFQ_ATTR(target_latency),
4571
	__ATTR_NULL
L
Linus Torvalds 已提交
4572 4573 4574 4575 4576 4577 4578
};

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,
4579
		.elevator_allow_merge_fn =	cfq_allow_merge,
D
Divyesh Shah 已提交
4580
		.elevator_bio_merged_fn =	cfq_bio_merged,
4581
		.elevator_dispatch_fn =		cfq_dispatch_requests,
L
Linus Torvalds 已提交
4582
		.elevator_add_req_fn =		cfq_insert_request,
4583
		.elevator_activate_req_fn =	cfq_activate_request,
L
Linus Torvalds 已提交
4584 4585
		.elevator_deactivate_req_fn =	cfq_deactivate_request,
		.elevator_completed_req_fn =	cfq_completed_request,
4586 4587
		.elevator_former_req_fn =	elv_rb_former_request,
		.elevator_latter_req_fn =	elv_rb_latter_request,
4588
		.elevator_init_icq_fn =		cfq_init_icq,
4589
		.elevator_exit_icq_fn =		cfq_exit_icq,
L
Linus Torvalds 已提交
4590 4591 4592 4593 4594 4595
		.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,
	},
4596 4597
	.icq_size	=	sizeof(struct cfq_io_cq),
	.icq_align	=	__alignof__(struct cfq_io_cq),
4598
	.elevator_attrs =	cfq_attrs,
4599
	.elevator_name	=	"cfq",
L
Linus Torvalds 已提交
4600 4601 4602
	.elevator_owner =	THIS_MODULE,
};

4603
#ifdef CONFIG_CFQ_GROUP_IOSCHED
T
Tejun Heo 已提交
4604
static struct blkcg_policy blkcg_policy_cfq = {
4605 4606 4607 4608
	.pd_size		= sizeof(struct cfq_group),
	.cftypes		= cfq_blkcg_files,

	.pd_init_fn		= cfq_pd_init,
4609
	.pd_offline_fn		= cfq_pd_offline,
4610
	.pd_reset_stats_fn	= cfq_pd_reset_stats,
4611 4612 4613
};
#endif

L
Linus Torvalds 已提交
4614 4615
static int __init cfq_init(void)
{
4616 4617
	int ret;

4618 4619 4620 4621 4622 4623 4624 4625
	/*
	 * could be 0 on HZ < 1000 setups
	 */
	if (!cfq_slice_async)
		cfq_slice_async = 1;
	if (!cfq_slice_idle)
		cfq_slice_idle = 1;

4626 4627 4628
#ifdef CONFIG_CFQ_GROUP_IOSCHED
	if (!cfq_group_idle)
		cfq_group_idle = 1;
T
Tejun Heo 已提交
4629

T
Tejun Heo 已提交
4630
	ret = blkcg_policy_register(&blkcg_policy_cfq);
T
Tejun Heo 已提交
4631 4632
	if (ret)
		return ret;
4633 4634 4635
#else
	cfq_group_idle = 0;
#endif
T
Tejun Heo 已提交
4636

4637
	ret = -ENOMEM;
4638 4639
	cfq_pool = KMEM_CACHE(cfq_queue, 0);
	if (!cfq_pool)
T
Tejun Heo 已提交
4640
		goto err_pol_unreg;
L
Linus Torvalds 已提交
4641

4642
	ret = elv_register(&iosched_cfq);
T
Tejun Heo 已提交
4643 4644
	if (ret)
		goto err_free_pool;
4645

4646
	return 0;
T
Tejun Heo 已提交
4647 4648 4649 4650

err_free_pool:
	kmem_cache_destroy(cfq_pool);
err_pol_unreg:
4651
#ifdef CONFIG_CFQ_GROUP_IOSCHED
T
Tejun Heo 已提交
4652
	blkcg_policy_unregister(&blkcg_policy_cfq);
4653
#endif
T
Tejun Heo 已提交
4654
	return ret;
L
Linus Torvalds 已提交
4655 4656 4657 4658
}

static void __exit cfq_exit(void)
{
4659
#ifdef CONFIG_CFQ_GROUP_IOSCHED
T
Tejun Heo 已提交
4660
	blkcg_policy_unregister(&blkcg_policy_cfq);
4661
#endif
L
Linus Torvalds 已提交
4662
	elv_unregister(&iosched_cfq);
4663
	kmem_cache_destroy(cfq_pool);
L
Linus Torvalds 已提交
4664 4665 4666 4667 4668 4669 4670 4671
}

module_init(cfq_init);
module_exit(cfq_exit);

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