projects / linux-2.6-block.git / blame
? search:
summary | shortlog | log | commit | commitdiff | tree
blob | blame (incremental) | history | HEAD
cfq: collapse cfq.h into cfq-iosched.c
[linux-2.6-block.git] / block / cfq-iosched.c
CommitLineData
1da177e4 1/*
1da177e4
LT		 2 * CFQ, or complete fairness queueing, disk scheduler.
3 *
4 * Based on ideas from a previously unfinished io
5 * scheduler (round robin per-process disk scheduling) and Andrea Arcangeli.
6 *
0fe23479 7 * Copyright (C) 2003 Jens Axboe <axboe@kernel.dk>
1da177e4 8 */
1da177e4 9#include <linux/module.h>
5a0e3ad6 10#include <linux/slab.h>
1cc9be68
AV		 11#include <linux/blkdev.h>
12#include <linux/elevator.h>
ad5ebd2f 13#include <linux/jiffies.h>
1da177e4 14#include <linux/rbtree.h>
22e2c507 15#include <linux/ioprio.h>
7b679138 16#include <linux/blktrace_api.h>
6e736be7 17#include "blk.h"
1da177e4 18
0381411e
TH		 19static struct blkio_policy_type blkio_policy_cfq;
20
1da177e4
LT		 21/*
22 * tunables
23 */
fe094d98 24/* max queue in one round of service */
abc3c744 25static const int cfq_quantum = 8;
64100099 26static const int cfq_fifo_expire[2] = { HZ / 4, HZ / 8 };
fe094d98
JA		 27/* maximum backwards seek, in KiB */
28static const int cfq_back_max = 16 * 1024;
29/* penalty of a backwards seek */
30static const int cfq_back_penalty = 2;
64100099 31static const int cfq_slice_sync = HZ / 10;
3b18152c 32static int cfq_slice_async = HZ / 25;
64100099 33static const int cfq_slice_async_rq = 2;
caaa5f9f 34static int cfq_slice_idle = HZ / 125;
80bdf0c7 35static int cfq_group_idle = HZ / 125;
5db5d642
CZ		 36static const int cfq_target_latency = HZ * 3/10; /* 300 ms */
37static const int cfq_hist_divisor = 4;
22e2c507 38
d9e7620e 39/*
0871714e 40 * offset from end of service tree
d9e7620e 41 */
0871714e 42#define CFQ_IDLE_DELAY (HZ / 5)
d9e7620e
JA		 43
44/*
45 * below this threshold, we consider thinktime immediate
46 */
47#define CFQ_MIN_TT (2)
48
22e2c507 49#define CFQ_SLICE_SCALE (5)
45333d5a 50#define CFQ_HW_QUEUE_MIN (5)
25bc6b07 51#define CFQ_SERVICE_SHIFT 12
22e2c507 52
3dde36dd 53#define CFQQ_SEEK_THR (sector_t)(8 * 100)
e9ce335d 54#define CFQQ_CLOSE_THR (sector_t)(8 * 1024)
41647e7a 55#define CFQQ_SECT_THR_NONROT (sector_t)(2 * 32)
3dde36dd 56#define CFQQ_SEEKY(cfqq) (hweight32(cfqq->seek_history) > 32/8)
ae54abed 57
a612fddf
TH		 58#define RQ_CIC(rq) icq_to_cic((rq)->elv.icq)
59#define RQ_CFQQ(rq) (struct cfq_queue *) ((rq)->elv.priv[0])
60#define RQ_CFQG(rq) (struct cfq_group *) ((rq)->elv.priv[1])
1da177e4 61
e18b890b 62static struct kmem_cache *cfq_pool;
1da177e4 63
22e2c507
JA		 64#define CFQ_PRIO_LISTS IOPRIO_BE_NR
65#define cfq_class_idle(cfqq) ((cfqq)->ioprio_class == IOPRIO_CLASS_IDLE)
22e2c507
JA		 66#define cfq_class_rt(cfqq) ((cfqq)->ioprio_class == IOPRIO_CLASS_RT)
67
206dc69b 68#define sample_valid(samples) ((samples) > 80)
1fa8f6d6 69#define rb_entry_cfqg(node) rb_entry((node), struct cfq_group, rb_node)
206dc69b 70
c5869807
TH		 71struct cfq_ttime {
72 unsigned long last_end_request;
73
74 unsigned long ttime_total;
75 unsigned long ttime_samples;
76 unsigned long ttime_mean;
77};
78
cc09e299
JA		 79/*
80 * Most of our rbtree usage is for sorting with min extraction, so
81 * if we cache the leftmost node we don't have to walk down the tree
82 * to find it. Idea borrowed from Ingo Molnars CFS scheduler. We should
83 * move this into the elevator for the rq sorting as well.
84 */
85struct cfq_rb_root {
86 struct rb_root rb;
87 struct rb_node *left;
aa6f6a3d 88 unsigned count;
73e9ffdd 89 unsigned total_weight;
1fa8f6d6 90 u64 min_vdisktime;
f5f2b6ce 91 struct cfq_ttime ttime;
cc09e299 92};
f5f2b6ce
SL		 93#define CFQ_RB_ROOT (struct cfq_rb_root) { .rb = RB_ROOT, \
94 .ttime = {.last_end_request = jiffies,},}
cc09e299 95
6118b70b
JA		 96/*
97 * Per process-grouping structure
98 */
99struct cfq_queue {
100 /* reference count */
30d7b944 101 int ref;
6118b70b
JA		 102 /* various state flags, see below */
103 unsigned int flags;
104 /* parent cfq_data */
105 struct cfq_data *cfqd;
106 /* service_tree member */
107 struct rb_node rb_node;
108 /* service_tree key */
109 unsigned long rb_key;
110 /* prio tree member */
111 struct rb_node p_node;
112 /* prio tree root we belong to, if any */
113 struct rb_root *p_root;
114 /* sorted list of pending requests */
115 struct rb_root sort_list;
116 /* if fifo isn't expired, next request to serve */
117 struct request *next_rq;
118 /* requests queued in sort_list */
119 int queued[2];
120 /* currently allocated requests */
121 int allocated[2];
122 /* fifo list of requests in sort_list */
123 struct list_head fifo;
124
dae739eb
VG		 125 /* time when queue got scheduled in to dispatch first request. */
126 unsigned long dispatch_start;
f75edf2d 127 unsigned int allocated_slice;
c4081ba5 128 unsigned int slice_dispatch;
dae739eb
VG		 129 /* time when first request from queue completed and slice started. */
130 unsigned long slice_start;
6118b70b
JA		 131 unsigned long slice_end;
132 long slice_resid;
6118b70b 133
65299a3b
CH		 134 /* pending priority requests */
135 int prio_pending;
6118b70b
JA		 136 /* number of requests that are on the dispatch list or inside driver */
137 int dispatched;
138
139 /* io prio of this group */
140 unsigned short ioprio, org_ioprio;
4aede84b 141 unsigned short ioprio_class;
6118b70b 142
c4081ba5
RK		 143 pid_t pid;
144
3dde36dd 145 u32 seek_history;
b2c18e1e
JM		 146 sector_t last_request_pos;
147
aa6f6a3d 148 struct cfq_rb_root *service_tree;
df5fe3e8 149 struct cfq_queue *new_cfqq;
cdb16e8f 150 struct cfq_group *cfqg;
c4e7893e
VG		 151 /* Number of sectors dispatched from queue in single dispatch round */
152 unsigned long nr_sectors;
6118b70b
JA		 153};
154
c0324a02 155/*
718eee05 156 * First index in the service_trees.
c0324a02
CZ		 157 * IDLE is handled separately, so it has negative index
158 */
159enum wl_prio_t {
c0324a02 160 BE_WORKLOAD = 0,
615f0259
VG		 161 RT_WORKLOAD = 1,
162 IDLE_WORKLOAD = 2,
b4627321 163 CFQ_PRIO_NR,
c0324a02
CZ		 164};
165
718eee05
CZ		 166/*
167 * Second index in the service_trees.
168 */
169enum wl_type_t {
170 ASYNC_WORKLOAD = 0,
171 SYNC_NOIDLE_WORKLOAD = 1,
172 SYNC_WORKLOAD = 2
173};
174
cdb16e8f
VG		 175/* This is per cgroup per device grouping structure */
176struct cfq_group {
1fa8f6d6
VG		 177 /* group service_tree member */
178 struct rb_node rb_node;
179
180 /* group service_tree key */
181 u64 vdisktime;
25bc6b07 182 unsigned int weight;
8184f93e
JT		 183 unsigned int new_weight;
184 bool needs_update;
1fa8f6d6
VG		 185
186 /* number of cfqq currently on this group */
187 int nr_cfqq;
188
cdb16e8f 189 /*
4495a7d4 190 * Per group busy queues average. Useful for workload slice calc. We
b4627321
VG		 191 * create the array for each prio class but at run time it is used
192 * only for RT and BE class and slot for IDLE class remains unused.
193 * This is primarily done to avoid confusion and a gcc warning.
194 */
195 unsigned int busy_queues_avg[CFQ_PRIO_NR];
196 /*
197 * rr lists of queues with requests. We maintain service trees for
198 * RT and BE classes. These trees are subdivided in subclasses
199 * of SYNC, SYNC_NOIDLE and ASYNC based on workload type. For IDLE
200 * class there is no subclassification and all the cfq queues go on
201 * a single tree service_tree_idle.
cdb16e8f
VG		 202 * Counts are embedded in the cfq_rb_root
203 */
204 struct cfq_rb_root service_trees[2][3];
205 struct cfq_rb_root service_tree_idle;
dae739eb
VG		 206
207 unsigned long saved_workload_slice;
208 enum wl_type_t saved_workload;
209 enum wl_prio_t saved_serving_prio;
4eef3049 210
80bdf0c7
VG		 211 /* number of requests that are on the dispatch list or inside driver */
212 int dispatched;
7700fc4f 213 struct cfq_ttime ttime;
cdb16e8f 214};
718eee05 215
c5869807
TH		 216struct cfq_io_cq {
217 struct io_cq icq; /* must be the first member */
218 struct cfq_queue *cfqq[2];
219 struct cfq_ttime ttime;
598971bf
TH		 220 int ioprio; /* the current ioprio */
221#ifdef CONFIG_CFQ_GROUP_IOSCHED
222 uint64_t blkcg_id; /* the current blkcg ID */
223#endif
c5869807
TH		 224};
225
22e2c507
JA		 226/*
227 * Per block device queue structure
228 */
1da177e4 229struct cfq_data {
165125e1 230 struct request_queue *queue;
1fa8f6d6
VG		 231 /* Root service tree for cfq_groups */
232 struct cfq_rb_root grp_service_tree;
f51b802c 233 struct cfq_group *root_group;
22e2c507 234
c0324a02
CZ		 235 /*
236 * The priority currently being served
22e2c507 237 */
c0324a02 238 enum wl_prio_t serving_prio;
718eee05
CZ		 239 enum wl_type_t serving_type;
240 unsigned long workload_expires;
cdb16e8f 241 struct cfq_group *serving_group;
a36e71f9
JA		 242
243 /*
244 * Each priority tree is sorted by next_request position. These
245 * trees are used when determining if two or more queues are
246 * interleaving requests (see cfq_close_cooperator).
247 */
248 struct rb_root prio_trees[CFQ_PRIO_LISTS];
249
22e2c507 250 unsigned int busy_queues;
ef8a41df 251 unsigned int busy_sync_queues;
22e2c507 252
53c583d2
CZ		 253 int rq_in_driver;
254 int rq_in_flight[2];
45333d5a
AC		 255
256 /*
257 * queue-depth detection
258 */
259 int rq_queued;
25776e35 260 int hw_tag;
e459dd08
CZ		 261 /*
262 * hw_tag can be
263 * -1 => indeterminate, (cfq will behave as if NCQ is present, to allow better detection)
264 * 1 => NCQ is present (hw_tag_est_depth is the estimated max depth)
265 * 0 => no NCQ
266 */
267 int hw_tag_est_depth;
268 unsigned int hw_tag_samples;
1da177e4 269
22e2c507
JA		 270 /*
271 * idle window management
272 */
273 struct timer_list idle_slice_timer;
23e018a1 274 struct work_struct unplug_work;
1da177e4 275
22e2c507 276 struct cfq_queue *active_queue;
c5869807 277 struct cfq_io_cq *active_cic;
22e2c507 278
c2dea2d1
VT		 279 /*
280 * async queue for each priority case
281 */
282 struct cfq_queue *async_cfqq[2][IOPRIO_BE_NR];
283 struct cfq_queue *async_idle_cfqq;
15c31be4 284
6d048f53 285 sector_t last_position;
1da177e4 286
1da177e4
LT		 287 /*
288 * tunables, see top of file
289 */
290 unsigned int cfq_quantum;
22e2c507 291 unsigned int cfq_fifo_expire[2];
1da177e4
LT		 292 unsigned int cfq_back_penalty;
293 unsigned int cfq_back_max;
22e2c507
JA		 294 unsigned int cfq_slice[2];
295 unsigned int cfq_slice_async_rq;
296 unsigned int cfq_slice_idle;
80bdf0c7 297 unsigned int cfq_group_idle;
963b72fc 298 unsigned int cfq_latency;
d9ff4187 299
6118b70b
JA		 300 /*
301 * Fallback dummy cfqq for extreme OOM conditions
302 */
303 struct cfq_queue oom_cfqq;
365722bb 304
573412b2 305 unsigned long last_delayed_sync;
1da177e4
LT		 306};
307
25fb5169
VG		 308static struct cfq_group *cfq_get_next_cfqg(struct cfq_data *cfqd);
309
cdb16e8f
VG		 310static struct cfq_rb_root *service_tree_for(struct cfq_group *cfqg,
311 enum wl_prio_t prio,
65b32a57 312 enum wl_type_t type)
c0324a02 313{
1fa8f6d6
VG		 314 if (!cfqg)
315 return NULL;
316
c0324a02 317 if (prio == IDLE_WORKLOAD)
cdb16e8f 318 return &cfqg->service_tree_idle;
c0324a02 319
cdb16e8f 320 return &cfqg->service_trees[prio][type];
c0324a02
CZ		 321}
322
3b18152c 323enum cfqq_state_flags {
b0b8d749
JA		 324 CFQ_CFQQ_FLAG_on_rr = 0, /* on round-robin busy list */
325 CFQ_CFQQ_FLAG_wait_request, /* waiting for a request */
b029195d 326 CFQ_CFQQ_FLAG_must_dispatch, /* must be allowed a dispatch */
b0b8d749 327 CFQ_CFQQ_FLAG_must_alloc_slice, /* per-slice must_alloc flag */
b0b8d749
JA		 328 CFQ_CFQQ_FLAG_fifo_expire, /* FIFO checked in this slice */
329 CFQ_CFQQ_FLAG_idle_window, /* slice idling enabled */
330 CFQ_CFQQ_FLAG_prio_changed, /* task priority has changed */
44f7c160 331 CFQ_CFQQ_FLAG_slice_new, /* no requests dispatched in slice */
91fac317 332 CFQ_CFQQ_FLAG_sync, /* synchronous queue */
b3b6d040 333 CFQ_CFQQ_FLAG_coop, /* cfqq is shared */
ae54abed 334 CFQ_CFQQ_FLAG_split_coop, /* shared cfqq will be splitted */
76280aff 335 CFQ_CFQQ_FLAG_deep, /* sync cfqq experienced large depth */
f75edf2d 336 CFQ_CFQQ_FLAG_wait_busy, /* Waiting for next request */
3b18152c
JA		 337};
338
339#define CFQ_CFQQ_FNS(name) \
340static inline void cfq_mark_cfqq_##name(struct cfq_queue *cfqq) \
341{ \
fe094d98 342 (cfqq)->flags |= (1 << CFQ_CFQQ_FLAG_##name); \
3b18152c
JA		 343} \
344static inline void cfq_clear_cfqq_##name(struct cfq_queue *cfqq) \
345{ \
fe094d98 346 (cfqq)->flags &= ~(1 << CFQ_CFQQ_FLAG_##name); \
3b18152c
JA		 347} \
348static inline int cfq_cfqq_##name(const struct cfq_queue *cfqq) \
349{ \
fe094d98 350 return ((cfqq)->flags & (1 << CFQ_CFQQ_FLAG_##name)) != 0; \
3b18152c
JA		 351}
352
353CFQ_CFQQ_FNS(on_rr);
354CFQ_CFQQ_FNS(wait_request);
b029195d 355CFQ_CFQQ_FNS(must_dispatch);
3b18152c 356CFQ_CFQQ_FNS(must_alloc_slice);
3b18152c
JA		 357CFQ_CFQQ_FNS(fifo_expire);
358CFQ_CFQQ_FNS(idle_window);
359CFQ_CFQQ_FNS(prio_changed);
44f7c160 360CFQ_CFQQ_FNS(slice_new);
91fac317 361CFQ_CFQQ_FNS(sync);
a36e71f9 362CFQ_CFQQ_FNS(coop);
ae54abed 363CFQ_CFQQ_FNS(split_coop);
76280aff 364CFQ_CFQQ_FNS(deep);
f75edf2d 365CFQ_CFQQ_FNS(wait_busy);
3b18152c
JA		 366#undef CFQ_CFQQ_FNS
367
afc24d49 368#ifdef CONFIG_CFQ_GROUP_IOSCHED
2ce4d50f
TH		 369
370#include "blk-cgroup.h"
371
eb7d8c07
TH		 372static inline struct cfq_group *blkg_to_cfqg(struct blkio_group *blkg)
373{
374 return blkg_to_pdata(blkg, &blkio_policy_cfq);
375}
376
377static inline struct blkio_group *cfqg_to_blkg(struct cfq_group *cfqg)
378{
aaec55a0 379 return pdata_to_blkg(cfqg);
eb7d8c07
TH		 380}
381
382static inline void cfqg_get(struct cfq_group *cfqg)
383{
384 return blkg_get(cfqg_to_blkg(cfqg));
385}
386
387static inline void cfqg_put(struct cfq_group *cfqg)
388{
389 return blkg_put(cfqg_to_blkg(cfqg));
390}
391
2868ef7b
VG		 392#define cfq_log_cfqq(cfqd, cfqq, fmt, args...) \
393 blk_add_trace_msg((cfqd)->queue, "cfq%d%c %s " fmt, (cfqq)->pid, \
394 cfq_cfqq_sync((cfqq)) ? 'S' : 'A', \
0381411e 395 blkg_path(cfqg_to_blkg((cfqq)->cfqg)), ##args)
2868ef7b
VG		 396
397#define cfq_log_cfqg(cfqd, cfqg, fmt, args...) \
398 blk_add_trace_msg((cfqd)->queue, "%s " fmt, \
0381411e 399 blkg_path(cfqg_to_blkg((cfqg))), ##args) \
2868ef7b 400
2ce4d50f
TH		 401static inline void cfq_blkiocg_update_io_add_stats(struct blkio_group *blkg,
402 struct blkio_policy_type *pol,
403 struct blkio_group *curr_blkg,
404 bool direction, bool sync)
405{
406 blkiocg_update_io_add_stats(blkg, pol, curr_blkg, direction, sync);
407}
408
409static inline void cfq_blkiocg_update_dequeue_stats(struct blkio_group *blkg,
410 struct blkio_policy_type *pol, unsigned long dequeue)
411{
412 blkiocg_update_dequeue_stats(blkg, pol, dequeue);
413}
414
415static inline void cfq_blkiocg_update_timeslice_used(struct blkio_group *blkg,
416 struct blkio_policy_type *pol, unsigned long time,
417 unsigned long unaccounted_time)
418{
419 blkiocg_update_timeslice_used(blkg, pol, time, unaccounted_time);
420}
421
422static inline void cfq_blkiocg_set_start_empty_time(struct blkio_group *blkg,
423 struct blkio_policy_type *pol)
424{
425 blkiocg_set_start_empty_time(blkg, pol);
426}
427
428static inline void cfq_blkiocg_update_io_remove_stats(struct blkio_group *blkg,
429 struct blkio_policy_type *pol, bool direction,
430 bool sync)
431{
432 blkiocg_update_io_remove_stats(blkg, pol, direction, sync);
433}
434
435static inline void cfq_blkiocg_update_io_merged_stats(struct blkio_group *blkg,
436 struct blkio_policy_type *pol, bool direction,
437 bool sync)
438{
439 blkiocg_update_io_merged_stats(blkg, pol, direction, sync);
440}
441
442static inline void cfq_blkiocg_update_idle_time_stats(struct blkio_group *blkg,
443 struct blkio_policy_type *pol)
444{
445 blkiocg_update_idle_time_stats(blkg, pol);
446}
447
448static inline void
449cfq_blkiocg_update_avg_queue_size_stats(struct blkio_group *blkg,
450 struct blkio_policy_type *pol)
451{
452 blkiocg_update_avg_queue_size_stats(blkg, pol);
453}
454
455static inline void
456cfq_blkiocg_update_set_idle_time_stats(struct blkio_group *blkg,
457 struct blkio_policy_type *pol)
458{
459 blkiocg_update_set_idle_time_stats(blkg, pol);
460}
461
462static inline void cfq_blkiocg_update_dispatch_stats(struct blkio_group *blkg,
463 struct blkio_policy_type *pol, uint64_t bytes,
464 bool direction, bool sync)
465{
466 blkiocg_update_dispatch_stats(blkg, pol, bytes, direction, sync);
467}
468
469static inline void cfq_blkiocg_update_completion_stats(struct blkio_group *blkg,
470 struct blkio_policy_type *pol, uint64_t start_time,
471 uint64_t io_start_time, bool direction, bool sync)
472{
473 blkiocg_update_completion_stats(blkg, pol, start_time, io_start_time,
474 direction, sync);
475}
476
eb7d8c07
TH		 477#else /* CONFIG_CFQ_GROUP_IOSCHED */
478
479static inline struct cfq_group *blkg_to_cfqg(struct blkio_group *blkg) { return NULL; }
480static inline struct blkio_group *cfqg_to_blkg(struct cfq_group *cfqg) { return NULL; }
481static inline void cfqg_get(struct cfq_group *cfqg) { }
482static inline void cfqg_put(struct cfq_group *cfqg) { }
483
7b679138
JA		 484#define cfq_log_cfqq(cfqd, cfqq, fmt, args...) \
485 blk_add_trace_msg((cfqd)->queue, "cfq%d " fmt, (cfqq)->pid, ##args)
4495a7d4 486#define cfq_log_cfqg(cfqd, cfqg, fmt, args...) do {} while (0)
eb7d8c07 487
2ce4d50f
TH		 488static inline void cfq_blkiocg_update_io_add_stats(struct blkio_group *blkg,
489 struct blkio_policy_type *pol,
490 struct blkio_group *curr_blkg, bool direction,
491 bool sync) { }
492static inline void cfq_blkiocg_update_dequeue_stats(struct blkio_group *blkg,
493 struct blkio_policy_type *pol, unsigned long dequeue) { }
494static inline void cfq_blkiocg_update_timeslice_used(struct blkio_group *blkg,
495 struct blkio_policy_type *pol, unsigned long time,
496 unsigned long unaccounted_time) { }
497static inline void cfq_blkiocg_set_start_empty_time(struct blkio_group *blkg,
498 struct blkio_policy_type *pol) { }
499static inline void cfq_blkiocg_update_io_remove_stats(struct blkio_group *blkg,
500 struct blkio_policy_type *pol, bool direction,
501 bool sync) { }
502static inline void cfq_blkiocg_update_io_merged_stats(struct blkio_group *blkg,
503 struct blkio_policy_type *pol, bool direction,
504 bool sync) { }
505static inline void cfq_blkiocg_update_idle_time_stats(struct blkio_group *blkg,
506 struct blkio_policy_type *pol) { }
507static inline void
508cfq_blkiocg_update_avg_queue_size_stats(struct blkio_group *blkg,
509 struct blkio_policy_type *pol) { }
510
511static inline void
512cfq_blkiocg_update_set_idle_time_stats(struct blkio_group *blkg,
513 struct blkio_policy_type *pol) { }
514
515static inline void cfq_blkiocg_update_dispatch_stats(struct blkio_group *blkg,
516 struct blkio_policy_type *pol, uint64_t bytes,
517 bool direction, bool sync) { }
518static inline void cfq_blkiocg_update_completion_stats(struct blkio_group *blkg,
519 struct blkio_policy_type *pol, uint64_t start_time,
520 uint64_t io_start_time, bool direction, bool sync) { }
521
eb7d8c07
TH		 522#endif /* CONFIG_CFQ_GROUP_IOSCHED */
523
7b679138
JA		 524#define cfq_log(cfqd, fmt, args...) \
525 blk_add_trace_msg((cfqd)->queue, "cfq " fmt, ##args)
526
615f0259
VG		 527/* Traverses through cfq group service trees */
528#define for_each_cfqg_st(cfqg, i, j, st) \
529 for (i = 0; i <= IDLE_WORKLOAD; i++) \
530 for (j = 0, st = i < IDLE_WORKLOAD ? &cfqg->service_trees[i][j]\
531 : &cfqg->service_tree_idle; \
532 (i < IDLE_WORKLOAD && j <= SYNC_WORKLOAD) || \
533 (i == IDLE_WORKLOAD && j == 0); \
534 j++, st = i < IDLE_WORKLOAD ? \
535 &cfqg->service_trees[i][j]: NULL) \
536
f5f2b6ce
SL		 537static inline bool cfq_io_thinktime_big(struct cfq_data *cfqd,
538 struct cfq_ttime *ttime, bool group_idle)
539{
540 unsigned long slice;
541 if (!sample_valid(ttime->ttime_samples))
542 return false;
543 if (group_idle)
544 slice = cfqd->cfq_group_idle;
545 else
546 slice = cfqd->cfq_slice_idle;
547 return ttime->ttime_mean > slice;
548}
615f0259 549
02b35081
VG		 550static inline bool iops_mode(struct cfq_data *cfqd)
551{
552 /*
553 * If we are not idling on queues and it is a NCQ drive, parallel
554 * execution of requests is on and measuring time is not possible
555 * in most of the cases until and unless we drive shallower queue
556 * depths and that becomes a performance bottleneck. In such cases
557 * switch to start providing fairness in terms of number of IOs.
558 */
559 if (!cfqd->cfq_slice_idle && cfqd->hw_tag)
560 return true;
561 else
562 return false;
563}
564
c0324a02
CZ		 565static inline enum wl_prio_t cfqq_prio(struct cfq_queue *cfqq)
566{
567 if (cfq_class_idle(cfqq))
568 return IDLE_WORKLOAD;
569 if (cfq_class_rt(cfqq))
570 return RT_WORKLOAD;
571 return BE_WORKLOAD;
572}
573
718eee05
CZ		 574
575static enum wl_type_t cfqq_type(struct cfq_queue *cfqq)
576{
577 if (!cfq_cfqq_sync(cfqq))
578 return ASYNC_WORKLOAD;
579 if (!cfq_cfqq_idle_window(cfqq))
580 return SYNC_NOIDLE_WORKLOAD;
581 return SYNC_WORKLOAD;
582}
583
58ff82f3
VG		 584static inline int cfq_group_busy_queues_wl(enum wl_prio_t wl,
585 struct cfq_data *cfqd,
586 struct cfq_group *cfqg)
c0324a02
CZ		 587{
588 if (wl == IDLE_WORKLOAD)
cdb16e8f 589 return cfqg->service_tree_idle.count;
c0324a02 590
cdb16e8f
VG		 591 return cfqg->service_trees[wl][ASYNC_WORKLOAD].count
592 + cfqg->service_trees[wl][SYNC_NOIDLE_WORKLOAD].count
593 + cfqg->service_trees[wl][SYNC_WORKLOAD].count;
c0324a02
CZ		 594}
595
f26bd1f0
VG		 596static inline int cfqg_busy_async_queues(struct cfq_data *cfqd,
597 struct cfq_group *cfqg)
598{
599 return cfqg->service_trees[RT_WORKLOAD][ASYNC_WORKLOAD].count
600 + cfqg->service_trees[BE_WORKLOAD][ASYNC_WORKLOAD].count;
601}
602
165125e1 603static void cfq_dispatch_insert(struct request_queue *, struct request *);
4f85cb96 604static struct cfq_queue *cfq_get_queue(struct cfq_data *cfqd, bool is_sync,
abede6da 605 struct cfq_io_cq *cic, struct bio *bio,
4f85cb96 606 gfp_t gfp_mask);
91fac317 607
c5869807
TH		 608static inline struct cfq_io_cq *icq_to_cic(struct io_cq *icq)
609{
610 /* cic->icq is the first member, %NULL will convert to %NULL */
611 return container_of(icq, struct cfq_io_cq, icq);
612}
613
47fdd4ca
TH		 614static inline struct cfq_io_cq *cfq_cic_lookup(struct cfq_data *cfqd,
615 struct io_context *ioc)
616{
617 if (ioc)
618 return icq_to_cic(ioc_lookup_icq(ioc, cfqd->queue));
619 return NULL;
620}
621
c5869807 622static inline struct cfq_queue *cic_to_cfqq(struct cfq_io_cq *cic, bool is_sync)
91fac317 623{
a6151c3a 624 return cic->cfqq[is_sync];
91fac317
VT		 625}
626
c5869807
TH		 627static inline void cic_set_cfqq(struct cfq_io_cq *cic, struct cfq_queue *cfqq,
628 bool is_sync)
91fac317 629{
a6151c3a 630 cic->cfqq[is_sync] = cfqq;
91fac317
VT		 631}
632
c5869807 633static inline struct cfq_data *cic_to_cfqd(struct cfq_io_cq *cic)
bca4b914 634{
c5869807 635 return cic->icq.q->elevator->elevator_data;
bca4b914
KK		 636}
637
91fac317
VT		 638/*
639 * We regard a request as SYNC, if it's either a read or has the SYNC bit
640 * set (in which case it could also be direct WRITE).
641 */
a6151c3a 642static inline bool cfq_bio_sync(struct bio *bio)
91fac317 643{
7b6d91da 644 return bio_data_dir(bio) == READ || (bio->bi_rw & REQ_SYNC);
91fac317 645}
1da177e4 646
99f95e52
AM		 647/*
648 * scheduler run of queue, if there are requests pending and no one in the
649 * driver that will restart queueing
650 */
23e018a1 651static inline void cfq_schedule_dispatch(struct cfq_data *cfqd)
99f95e52 652{
7b679138
JA		 653 if (cfqd->busy_queues) {
654 cfq_log(cfqd, "schedule dispatch");
23e018a1 655 kblockd_schedule_work(cfqd->queue, &cfqd->unplug_work);
7b679138 656 }
99f95e52
AM		 657}
658
44f7c160
JA		 659/*
660 * Scale schedule slice based on io priority. Use the sync time slice only
661 * if a queue is marked sync and has sync io queued. A sync queue with async
662 * io only, should not get full sync slice length.
663 */
a6151c3a 664static inline int cfq_prio_slice(struct cfq_data *cfqd, bool sync,
d9e7620e 665 unsigned short prio)
44f7c160 666{
d9e7620e 667 const int base_slice = cfqd->cfq_slice[sync];
44f7c160 668
d9e7620e
JA		 669 WARN_ON(prio >= IOPRIO_BE_NR);
670
671 return base_slice + (base_slice/CFQ_SLICE_SCALE * (4 - prio));
672}
44f7c160 673
d9e7620e
JA		 674static inline int
675cfq_prio_to_slice(struct cfq_data *cfqd, struct cfq_queue *cfqq)
676{
677 return cfq_prio_slice(cfqd, cfq_cfqq_sync(cfqq), cfqq->ioprio);
44f7c160
JA		 678}
679
25bc6b07
VG		 680static inline u64 cfq_scale_slice(unsigned long delta, struct cfq_group *cfqg)
681{
682 u64 d = delta << CFQ_SERVICE_SHIFT;
683
684 d = d * BLKIO_WEIGHT_DEFAULT;
685 do_div(d, cfqg->weight);
686 return d;
687}
688
689static inline u64 max_vdisktime(u64 min_vdisktime, u64 vdisktime)
690{
691 s64 delta = (s64)(vdisktime - min_vdisktime);
692 if (delta > 0)
693 min_vdisktime = vdisktime;
694
695 return min_vdisktime;
696}
697
698static inline u64 min_vdisktime(u64 min_vdisktime, u64 vdisktime)
699{
700 s64 delta = (s64)(vdisktime - min_vdisktime);
701 if (delta < 0)
702 min_vdisktime = vdisktime;
703
704 return min_vdisktime;
705}
706
707static void update_min_vdisktime(struct cfq_rb_root *st)
708{
25bc6b07
VG		 709 struct cfq_group *cfqg;
710
25bc6b07
VG		 711 if (st->left) {
712 cfqg = rb_entry_cfqg(st->left);
a6032710
GJ		 713 st->min_vdisktime = max_vdisktime(st->min_vdisktime,
714 cfqg->vdisktime);
25bc6b07 715 }
25bc6b07
VG		 716}
717
5db5d642
CZ		 718/*
719 * get averaged number of queues of RT/BE priority.
720 * average is updated, with a formula that gives more weight to higher numbers,
721 * to quickly follows sudden increases and decrease slowly
722 */
723
58ff82f3
VG		 724static inline unsigned cfq_group_get_avg_queues(struct cfq_data *cfqd,
725 struct cfq_group *cfqg, bool rt)
5869619c 726{
5db5d642
CZ		 727 unsigned min_q, max_q;
728 unsigned mult = cfq_hist_divisor - 1;
729 unsigned round = cfq_hist_divisor / 2;
58ff82f3 730 unsigned busy = cfq_group_busy_queues_wl(rt, cfqd, cfqg);
5db5d642 731
58ff82f3
VG		 732 min_q = min(cfqg->busy_queues_avg[rt], busy);
733 max_q = max(cfqg->busy_queues_avg[rt], busy);
734 cfqg->busy_queues_avg[rt] = (mult * max_q + min_q + round) /
5db5d642 735 cfq_hist_divisor;
58ff82f3
VG		 736 return cfqg->busy_queues_avg[rt];
737}
738
739static inline unsigned
740cfq_group_slice(struct cfq_data *cfqd, struct cfq_group *cfqg)
741{
742 struct cfq_rb_root *st = &cfqd->grp_service_tree;
743
744 return cfq_target_latency * cfqg->weight / st->total_weight;
5db5d642
CZ		 745}
746
c553f8e3 747static inline unsigned
ba5bd520 748cfq_scaled_cfqq_slice(struct cfq_data *cfqd, struct cfq_queue *cfqq)
44f7c160 749{
5db5d642
CZ		 750 unsigned slice = cfq_prio_to_slice(cfqd, cfqq);
751 if (cfqd->cfq_latency) {
58ff82f3
VG		 752 /*
753 * interested queues (we consider only the ones with the same
754 * priority class in the cfq group)
755 */
756 unsigned iq = cfq_group_get_avg_queues(cfqd, cfqq->cfqg,
757 cfq_class_rt(cfqq));
5db5d642
CZ		 758 unsigned sync_slice = cfqd->cfq_slice[1];
759 unsigned expect_latency = sync_slice * iq;
58ff82f3
VG		 760 unsigned group_slice = cfq_group_slice(cfqd, cfqq->cfqg);
761
762 if (expect_latency > group_slice) {
5db5d642
CZ		 763 unsigned base_low_slice = 2 * cfqd->cfq_slice_idle;
764 /* scale low_slice according to IO priority
765 * and sync vs async */
766 unsigned low_slice =
767 min(slice, base_low_slice * slice / sync_slice);
768 /* the adapted slice value is scaled to fit all iqs
769 * into the target latency */
58ff82f3 770 slice = max(slice * group_slice / expect_latency,
5db5d642
CZ		 771 low_slice);
772 }
773 }
c553f8e3
SL		 774 return slice;
775}
776
777static inline void
778cfq_set_prio_slice(struct cfq_data *cfqd, struct cfq_queue *cfqq)
779{
ba5bd520 780 unsigned slice = cfq_scaled_cfqq_slice(cfqd, cfqq);
c553f8e3 781
dae739eb 782 cfqq->slice_start = jiffies;
5db5d642 783 cfqq->slice_end = jiffies + slice;
f75edf2d 784 cfqq->allocated_slice = slice;
7b679138 785 cfq_log_cfqq(cfqd, cfqq, "set_slice=%lu", cfqq->slice_end - jiffies);
44f7c160
JA		 786}
787
788/*
789 * We need to wrap this check in cfq_cfqq_slice_new(), since ->slice_end
790 * isn't valid until the first request from the dispatch is activated
791 * and the slice time set.
792 */
a6151c3a 793static inline bool cfq_slice_used(struct cfq_queue *cfqq)
44f7c160
JA		 794{
795 if (cfq_cfqq_slice_new(cfqq))
c1e44756 796 return false;
44f7c160 797 if (time_before(jiffies, cfqq->slice_end))
c1e44756 798 return false;
44f7c160 799
c1e44756 800 return true;
44f7c160
JA		 801}
802
1da177e4 803/*
5e705374 804 * Lifted from AS - choose which of rq1 and rq2 that is best served now.
1da177e4 805 * We choose the request that is closest to the head right now. Distance
e8a99053 806 * behind the head is penalized and only allowed to a certain extent.
1da177e4 807 */
5e705374 808static struct request *
cf7c25cf 809cfq_choose_req(struct cfq_data *cfqd, struct request *rq1, struct request *rq2, sector_t last)
1da177e4 810{
cf7c25cf 811 sector_t s1, s2, d1 = 0, d2 = 0;
1da177e4 812 unsigned long back_max;
e8a99053
AM		 813#define CFQ_RQ1_WRAP 0x01 /* request 1 wraps */
814#define CFQ_RQ2_WRAP 0x02 /* request 2 wraps */
815 unsigned wrap = 0; /* bit mask: requests behind the disk head? */
1da177e4 816
5e705374
JA		 817 if (rq1 == NULL || rq1 == rq2)
818 return rq2;
819 if (rq2 == NULL)
820 return rq1;
9c2c38a1 821
229836bd
NK		 822 if (rq_is_sync(rq1) != rq_is_sync(rq2))
823 return rq_is_sync(rq1) ? rq1 : rq2;
824
65299a3b
CH		 825 if ((rq1->cmd_flags ^ rq2->cmd_flags) & REQ_PRIO)
826 return rq1->cmd_flags & REQ_PRIO ? rq1 : rq2;
b53d1ed7 827
83096ebf
TH		 828 s1 = blk_rq_pos(rq1);
829 s2 = blk_rq_pos(rq2);
1da177e4 830
1da177e4
LT		 831 /*
832 * by definition, 1KiB is 2 sectors
833 */
834 back_max = cfqd->cfq_back_max * 2;
835
836 /*
837 * Strict one way elevator _except_ in the case where we allow
838 * short backward seeks which are biased as twice the cost of a
839 * similar forward seek.
840 */
841 if (s1 >= last)
842 d1 = s1 - last;
843 else if (s1 + back_max >= last)
844 d1 = (last - s1) * cfqd->cfq_back_penalty;
845 else
e8a99053 846 wrap |= CFQ_RQ1_WRAP;
1da177e4
LT		 847
848 if (s2 >= last)
849 d2 = s2 - last;
850 else if (s2 + back_max >= last)
851 d2 = (last - s2) * cfqd->cfq_back_penalty;
852 else
e8a99053 853 wrap |= CFQ_RQ2_WRAP;
1da177e4
LT		 854
855 /* Found required data */
e8a99053
AM		 856
857 /*
858 * By doing switch() on the bit mask "wrap" we avoid having to
859 * check two variables for all permutations: --> faster!
860 */
861 switch (wrap) {
5e705374 862 case 0: /* common case for CFQ: rq1 and rq2 not wrapped */
e8a99053 863 if (d1 < d2)
5e705374 864 return rq1;
e8a99053 865 else if (d2 < d1)
5e705374 866 return rq2;
e8a99053
AM		 867 else {
868 if (s1 >= s2)
5e705374 869 return rq1;
e8a99053 870 else
5e705374 871 return rq2;
e8a99053 872 }
1da177e4 873
e8a99053 874 case CFQ_RQ2_WRAP:
5e705374 875 return rq1;
e8a99053 876 case CFQ_RQ1_WRAP:
5e705374
JA		 877 return rq2;
878 case (CFQ_RQ1_WRAP|CFQ_RQ2_WRAP): /* both rqs wrapped */
e8a99053
AM		 879 default:
880 /*
881 * Since both rqs are wrapped,
882 * start with the one that's further behind head
883 * (--> only *one* back seek required),
884 * since back seek takes more time than forward.
885 */
886 if (s1 <= s2)
5e705374 887 return rq1;
1da177e4 888 else
5e705374 889 return rq2;
1da177e4
LT		 890 }
891}
892
498d3aa2
JA		 893/*
894 * The below is leftmost cache rbtree addon
895 */
0871714e 896static struct cfq_queue *cfq_rb_first(struct cfq_rb_root *root)
cc09e299 897{
615f0259
VG		 898 /* Service tree is empty */
899 if (!root->count)
900 return NULL;
901
cc09e299
JA		 902 if (!root->left)
903 root->left = rb_first(&root->rb);
904
0871714e
JA		 905 if (root->left)
906 return rb_entry(root->left, struct cfq_queue, rb_node);
907
908 return NULL;
cc09e299
JA		 909}
910
1fa8f6d6
VG		 911static struct cfq_group *cfq_rb_first_group(struct cfq_rb_root *root)
912{
913 if (!root->left)
914 root->left = rb_first(&root->rb);
915
916 if (root->left)
917 return rb_entry_cfqg(root->left);
918
919 return NULL;
920}
921
a36e71f9
JA		 922static void rb_erase_init(struct rb_node *n, struct rb_root *root)
923{
924 rb_erase(n, root);
925 RB_CLEAR_NODE(n);
926}
927
cc09e299
JA		 928static void cfq_rb_erase(struct rb_node *n, struct cfq_rb_root *root)
929{
930 if (root->left == n)
931 root->left = NULL;
a36e71f9 932 rb_erase_init(n, &root->rb);
aa6f6a3d 933 --root->count;
cc09e299
JA		 934}
935
1da177e4
LT		 936/*
937 * would be nice to take fifo expire time into account as well
938 */
5e705374
JA		 939static struct request *
940cfq_find_next_rq(struct cfq_data *cfqd, struct cfq_queue *cfqq,
941 struct request *last)
1da177e4 942{
21183b07
JA		 943 struct rb_node *rbnext = rb_next(&last->rb_node);
944 struct rb_node *rbprev = rb_prev(&last->rb_node);
5e705374 945 struct request *next = NULL, *prev = NULL;
1da177e4 946
21183b07 947 BUG_ON(RB_EMPTY_NODE(&last->rb_node));
1da177e4
LT		 948
949 if (rbprev)
5e705374 950 prev = rb_entry_rq(rbprev);
1da177e4 951
21183b07 952 if (rbnext)
5e705374 953 next = rb_entry_rq(rbnext);
21183b07
JA		 954 else {
955 rbnext = rb_first(&cfqq->sort_list);
956 if (rbnext && rbnext != &last->rb_node)
5e705374 957 next = rb_entry_rq(rbnext);
21183b07 958 }
1da177e4 959
cf7c25cf 960 return cfq_choose_req(cfqd, next, prev, blk_rq_pos(last));
1da177e4
LT		 961}
962
d9e7620e
JA		 963static unsigned long cfq_slice_offset(struct cfq_data *cfqd,
964 struct cfq_queue *cfqq)
1da177e4 965{
d9e7620e
JA		 966 /*
967 * just an approximation, should be ok.
968 */
cdb16e8f 969 return (cfqq->cfqg->nr_cfqq - 1) * (cfq_prio_slice(cfqd, 1, 0) -
464191c6 970 cfq_prio_slice(cfqd, cfq_cfqq_sync(cfqq), cfqq->ioprio));
d9e7620e
JA		 971}
972
1fa8f6d6
VG		 973static inline s64
974cfqg_key(struct cfq_rb_root *st, struct cfq_group *cfqg)
975{
976 return cfqg->vdisktime - st->min_vdisktime;
977}
978
979static void
980__cfq_group_service_tree_add(struct cfq_rb_root *st, struct cfq_group *cfqg)
981{
982 struct rb_node **node = &st->rb.rb_node;
983 struct rb_node *parent = NULL;
984 struct cfq_group *__cfqg;
985 s64 key = cfqg_key(st, cfqg);
986 int left = 1;
987
988 while (*node != NULL) {
989 parent = *node;
990 __cfqg = rb_entry_cfqg(parent);
991
992 if (key < cfqg_key(st, __cfqg))
993 node = &parent->rb_left;
994 else {
995 node = &parent->rb_right;
996 left = 0;
997 }
998 }
999
1000 if (left)
1001 st->left = &cfqg->rb_node;
1002
1003 rb_link_node(&cfqg->rb_node, parent, node);
1004 rb_insert_color(&cfqg->rb_node, &st->rb);
1005}
1006
1007static void
8184f93e
JT		 1008cfq_update_group_weight(struct cfq_group *cfqg)
1009{
1010 BUG_ON(!RB_EMPTY_NODE(&cfqg->rb_node));
1011 if (cfqg->needs_update) {
1012 cfqg->weight = cfqg->new_weight;
1013 cfqg->needs_update = false;
1014 }
1015}
1016
1017static void
1018cfq_group_service_tree_add(struct cfq_rb_root *st, struct cfq_group *cfqg)
1019{
1020 BUG_ON(!RB_EMPTY_NODE(&cfqg->rb_node));
1021
1022 cfq_update_group_weight(cfqg);
1023 __cfq_group_service_tree_add(st, cfqg);
1024 st->total_weight += cfqg->weight;
1025}
1026
1027static void
1028cfq_group_notify_queue_add(struct cfq_data *cfqd, struct cfq_group *cfqg)
1fa8f6d6
VG		 1029{
1030 struct cfq_rb_root *st = &cfqd->grp_service_tree;
1031 struct cfq_group *__cfqg;
1032 struct rb_node *n;
1033
1034 cfqg->nr_cfqq++;
760701bf 1035 if (!RB_EMPTY_NODE(&cfqg->rb_node))
1fa8f6d6
VG		 1036 return;
1037
1038 /*
1039 * Currently put the group at the end. Later implement something
1040 * so that groups get lesser vtime based on their weights, so that
25985edc 1041 * if group does not loose all if it was not continuously backlogged.
1fa8f6d6
VG		 1042 */
1043 n = rb_last(&st->rb);
1044 if (n) {
1045 __cfqg = rb_entry_cfqg(n);
1046 cfqg->vdisktime = __cfqg->vdisktime + CFQ_IDLE_DELAY;
1047 } else
1048 cfqg->vdisktime = st->min_vdisktime;
8184f93e
JT		 1049 cfq_group_service_tree_add(st, cfqg);
1050}
1fa8f6d6 1051
8184f93e
JT		 1052static void
1053cfq_group_service_tree_del(struct cfq_rb_root *st, struct cfq_group *cfqg)
1054{
1055 st->total_weight -= cfqg->weight;
1056 if (!RB_EMPTY_NODE(&cfqg->rb_node))
1057 cfq_rb_erase(&cfqg->rb_node, st);
1fa8f6d6
VG		 1058}
1059
1060static void
8184f93e 1061cfq_group_notify_queue_del(struct cfq_data *cfqd, struct cfq_group *cfqg)
1fa8f6d6
VG		 1062{
1063 struct cfq_rb_root *st = &cfqd->grp_service_tree;
1064
1065 BUG_ON(cfqg->nr_cfqq < 1);
1066 cfqg->nr_cfqq--;
25bc6b07 1067
1fa8f6d6
VG		 1068 /* If there are other cfq queues under this group, don't delete it */
1069 if (cfqg->nr_cfqq)
1070 return;
1071
2868ef7b 1072 cfq_log_cfqg(cfqd, cfqg, "del_from_rr group");
8184f93e 1073 cfq_group_service_tree_del(st, cfqg);
dae739eb 1074 cfqg->saved_workload_slice = 0;
c1768268
TH		 1075 cfq_blkiocg_update_dequeue_stats(cfqg_to_blkg(cfqg),
1076 &blkio_policy_cfq, 1);
dae739eb
VG		 1077}
1078
167400d3
JT		 1079static inline unsigned int cfq_cfqq_slice_usage(struct cfq_queue *cfqq,
1080 unsigned int *unaccounted_time)
dae739eb 1081{
f75edf2d 1082 unsigned int slice_used;
dae739eb
VG		 1083
1084 /*
1085 * Queue got expired before even a single request completed or
1086 * got expired immediately after first request completion.
1087 */
1088 if (!cfqq->slice_start || cfqq->slice_start == jiffies) {
1089 /*
1090 * Also charge the seek time incurred to the group, otherwise
1091 * if there are mutiple queues in the group, each can dispatch
1092 * a single request on seeky media and cause lots of seek time
1093 * and group will never know it.
1094 */
1095 slice_used = max_t(unsigned, (jiffies - cfqq->dispatch_start),
1096 1);
1097 } else {
1098 slice_used = jiffies - cfqq->slice_start;
167400d3
JT		 1099 if (slice_used > cfqq->allocated_slice) {
1100 *unaccounted_time = slice_used - cfqq->allocated_slice;
f75edf2d 1101 slice_used = cfqq->allocated_slice;
167400d3
JT		 1102 }
1103 if (time_after(cfqq->slice_start, cfqq->dispatch_start))
1104 *unaccounted_time += cfqq->slice_start -
1105 cfqq->dispatch_start;
dae739eb
VG		 1106 }
1107
dae739eb
VG		 1108 return slice_used;
1109}
1110
1111static void cfq_group_served(struct cfq_data *cfqd, struct cfq_group *cfqg,
e5ff082e 1112 struct cfq_queue *cfqq)
dae739eb
VG		 1113{
1114 struct cfq_rb_root *st = &cfqd->grp_service_tree;
167400d3 1115 unsigned int used_sl, charge, unaccounted_sl = 0;
f26bd1f0
VG		 1116 int nr_sync = cfqg->nr_cfqq - cfqg_busy_async_queues(cfqd, cfqg)
1117 - cfqg->service_tree_idle.count;
1118
1119 BUG_ON(nr_sync < 0);
167400d3 1120 used_sl = charge = cfq_cfqq_slice_usage(cfqq, &unaccounted_sl);
dae739eb 1121
02b35081
VG		 1122 if (iops_mode(cfqd))
1123 charge = cfqq->slice_dispatch;
1124 else if (!cfq_cfqq_sync(cfqq) && !nr_sync)
1125 charge = cfqq->allocated_slice;
dae739eb
VG		 1126
1127 /* Can't update vdisktime while group is on service tree */
8184f93e 1128 cfq_group_service_tree_del(st, cfqg);
02b35081 1129 cfqg->vdisktime += cfq_scale_slice(charge, cfqg);
8184f93e
JT		 1130 /* If a new weight was requested, update now, off tree */
1131 cfq_group_service_tree_add(st, cfqg);
dae739eb
VG		 1132
1133 /* This group is being expired. Save the context */
1134 if (time_after(cfqd->workload_expires, jiffies)) {
1135 cfqg->saved_workload_slice = cfqd->workload_expires
1136 - jiffies;
1137 cfqg->saved_workload = cfqd->serving_type;
1138 cfqg->saved_serving_prio = cfqd->serving_prio;
1139 } else
1140 cfqg->saved_workload_slice = 0;
2868ef7b
VG		 1141
1142 cfq_log_cfqg(cfqd, cfqg, "served: vt=%llu min_vt=%llu", cfqg->vdisktime,
1143 st->min_vdisktime);
fd16d263
JP		 1144 cfq_log_cfqq(cfqq->cfqd, cfqq,
1145 "sl_used=%u disp=%u charge=%u iops=%u sect=%lu",
1146 used_sl, cfqq->slice_dispatch, charge,
1147 iops_mode(cfqd), cfqq->nr_sectors);
c1768268
TH		 1148 cfq_blkiocg_update_timeslice_used(cfqg_to_blkg(cfqg), &blkio_policy_cfq,
1149 used_sl, unaccounted_sl);
1150 cfq_blkiocg_set_start_empty_time(cfqg_to_blkg(cfqg), &blkio_policy_cfq);
1fa8f6d6
VG		 1151}
1152
f51b802c
TH		 1153/**
1154 * cfq_init_cfqg_base - initialize base part of a cfq_group
1155 * @cfqg: cfq_group to initialize
1156 *
1157 * Initialize the base part which is used whether %CONFIG_CFQ_GROUP_IOSCHED
1158 * is enabled or not.
1159 */
1160static void cfq_init_cfqg_base(struct cfq_group *cfqg)
1161{
1162 struct cfq_rb_root *st;
1163 int i, j;
1164
1165 for_each_cfqg_st(cfqg, i, j, st)
1166 *st = CFQ_RB_ROOT;
1167 RB_CLEAR_NODE(&cfqg->rb_node);
1168
1169 cfqg->ttime.last_end_request = jiffies;
1170}
1171
25fb5169 1172#ifdef CONFIG_CFQ_GROUP_IOSCHED
60c2bc2d 1173static void cfq_update_blkio_group_weight(struct blkio_group *blkg,
8aea4545 1174 unsigned int weight)
f8d461d6 1175{
0381411e
TH		 1176 struct cfq_group *cfqg = blkg_to_cfqg(blkg);
1177
8184f93e
JT		 1178 cfqg->new_weight = weight;
1179 cfqg->needs_update = true;
f8d461d6
VG		 1180}
1181
0381411e 1182static void cfq_init_blkio_group(struct blkio_group *blkg)
f469a7b4 1183{
0381411e 1184 struct cfq_group *cfqg = blkg_to_cfqg(blkg);
25fb5169 1185
f51b802c 1186 cfq_init_cfqg_base(cfqg);
0381411e 1187 cfqg->weight = blkg->blkcg->weight;
25fb5169
VG		 1188}
1189
1190/*
3e59cf9d
VG		 1191 * Search for the cfq group current task belongs to. request_queue lock must
1192 * be held.
25fb5169 1193 */
cd1604fa
TH		 1194static struct cfq_group *cfq_lookup_create_cfqg(struct cfq_data *cfqd,
1195 struct blkio_cgroup *blkcg)
25fb5169 1196{
f469a7b4 1197 struct request_queue *q = cfqd->queue;
cd1604fa 1198 struct cfq_group *cfqg = NULL;
25fb5169 1199
cd1604fa
TH		 1200 /* avoid lookup for the common case where there's no blkio cgroup */
1201 if (blkcg == &blkio_root_cgroup) {
1202 cfqg = cfqd->root_group;
1203 } else {
1204 struct blkio_group *blkg;
f469a7b4 1205
aaec55a0 1206 blkg = blkg_lookup_create(blkcg, q, false);
cd1604fa 1207 if (!IS_ERR(blkg))
0381411e 1208 cfqg = blkg_to_cfqg(blkg);
cd1604fa 1209 }
f469a7b4 1210
25fb5169
VG		 1211 return cfqg;
1212}
1213
1214static void cfq_link_cfqq_cfqg(struct cfq_queue *cfqq, struct cfq_group *cfqg)
1215{
1216 /* Currently, all async queues are mapped to root group */
1217 if (!cfq_cfqq_sync(cfqq))
f51b802c 1218 cfqg = cfqq->cfqd->root_group;
25fb5169
VG		 1219
1220 cfqq->cfqg = cfqg;
b1c35769 1221 /* cfqq reference on cfqg */
eb7d8c07 1222 cfqg_get(cfqg);
b1c35769
VG		 1223}
1224
60c2bc2d
TH		 1225static u64 blkg_prfill_weight_device(struct seq_file *sf,
1226 struct blkg_policy_data *pd, int off)
1227{
1228 if (!pd->conf.weight)
1229 return 0;
1230 return __blkg_prfill_u64(sf, pd, pd->conf.weight);
1231}
1232
1233static int blkcg_print_weight_device(struct cgroup *cgrp, struct cftype *cft,
1234 struct seq_file *sf)
1235{
1236 blkcg_print_blkgs(sf, cgroup_to_blkio_cgroup(cgrp),
1237 blkg_prfill_weight_device, BLKIO_POLICY_PROP, 0,
1238 false);
1239 return 0;
1240}
1241
1242static int blkcg_print_weight(struct cgroup *cgrp, struct cftype *cft,
1243 struct seq_file *sf)
1244{
1245 seq_printf(sf, "%u\n", cgroup_to_blkio_cgroup(cgrp)->weight);
1246 return 0;
1247}
1248
1249static int blkcg_set_weight_device(struct cgroup *cgrp, struct cftype *cft,
1250 const char *buf)
1251{
1252 struct blkio_cgroup *blkcg = cgroup_to_blkio_cgroup(cgrp);
1253 struct blkg_policy_data *pd;
1254 struct blkg_conf_ctx ctx;
1255 int ret;
1256
1257 ret = blkg_conf_prep(blkcg, buf, &ctx);
1258 if (ret)
1259 return ret;
1260
1261 ret = -EINVAL;
1262 pd = ctx.blkg->pd[BLKIO_POLICY_PROP];
1263 if (pd && (!ctx.v || (ctx.v >= BLKIO_WEIGHT_MIN &&
1264 ctx.v <= BLKIO_WEIGHT_MAX))) {
1265 pd->conf.weight = ctx.v;
1266 cfq_update_blkio_group_weight(ctx.blkg, ctx.v ?: blkcg->weight);
1267 ret = 0;
1268 }
1269
1270 blkg_conf_finish(&ctx);
1271 return ret;
1272}
1273
1274static int blkcg_set_weight(struct cgroup *cgrp, struct cftype *cft, u64 val)
1275{
1276 struct blkio_cgroup *blkcg = cgroup_to_blkio_cgroup(cgrp);
1277 struct blkio_group *blkg;
1278 struct hlist_node *n;
1279
1280 if (val < BLKIO_WEIGHT_MIN || val > BLKIO_WEIGHT_MAX)
1281 return -EINVAL;
1282
1283 spin_lock_irq(&blkcg->lock);
1284 blkcg->weight = (unsigned int)val;
1285
1286 hlist_for_each_entry(blkg, n, &blkcg->blkg_list, blkcg_node) {
1287 struct blkg_policy_data *pd = blkg->pd[BLKIO_POLICY_PROP];
1288
1289 if (pd && !pd->conf.weight)
1290 cfq_update_blkio_group_weight(blkg, blkcg->weight);
1291 }
1292
1293 spin_unlock_irq(&blkcg->lock);
1294 return 0;
1295}
1296
1297#ifdef CONFIG_DEBUG_BLK_CGROUP
1298static u64 blkg_prfill_avg_queue_size(struct seq_file *sf,
1299 struct blkg_policy_data *pd, int off)
1300{
1301 u64 samples = blkg_stat_read(&pd->stats.avg_queue_size_samples);
1302 u64 v = 0;
1303
1304 if (samples) {
1305 v = blkg_stat_read(&pd->stats.avg_queue_size_sum);
1306 do_div(v, samples);
1307 }
1308 __blkg_prfill_u64(sf, pd, v);
1309 return 0;
1310}
1311
1312/* print avg_queue_size */
1313static int blkcg_print_avg_queue_size(struct cgroup *cgrp, struct cftype *cft,
1314 struct seq_file *sf)
1315{
1316 struct blkio_cgroup *blkcg = cgroup_to_blkio_cgroup(cgrp);
1317
1318 blkcg_print_blkgs(sf, blkcg, blkg_prfill_avg_queue_size,
1319 BLKIO_POLICY_PROP, 0, false);
1320 return 0;
1321}
1322#endif /* CONFIG_DEBUG_BLK_CGROUP */
1323
1324static struct cftype cfq_blkcg_files[] = {
1325 {
1326 .name = "weight_device",
1327 .read_seq_string = blkcg_print_weight_device,
1328 .write_string = blkcg_set_weight_device,
1329 .max_write_len = 256,
1330 },
1331 {
1332 .name = "weight",
1333 .read_seq_string = blkcg_print_weight,
1334 .write_u64 = blkcg_set_weight,
1335 },
1336 {
1337 .name = "time",
1338 .private = BLKCG_STAT_PRIV(BLKIO_POLICY_PROP,
1339 offsetof(struct blkio_group_stats, time)),
1340 .read_seq_string = blkcg_print_stat,
1341 },
1342 {
1343 .name = "sectors",
1344 .private = BLKCG_STAT_PRIV(BLKIO_POLICY_PROP,
1345 offsetof(struct blkio_group_stats_cpu, sectors)),
1346 .read_seq_string = blkcg_print_cpu_stat,
1347 },
1348 {
1349 .name = "io_service_bytes",
1350 .private = BLKCG_STAT_PRIV(BLKIO_POLICY_PROP,
1351 offsetof(struct blkio_group_stats_cpu, service_bytes)),
1352 .read_seq_string = blkcg_print_cpu_rwstat,
1353 },
1354 {
1355 .name = "io_serviced",
1356 .private = BLKCG_STAT_PRIV(BLKIO_POLICY_PROP,
1357 offsetof(struct blkio_group_stats_cpu, serviced)),
1358 .read_seq_string = blkcg_print_cpu_rwstat,
1359 },
1360 {
1361 .name = "io_service_time",
1362 .private = BLKCG_STAT_PRIV(BLKIO_POLICY_PROP,
1363 offsetof(struct blkio_group_stats, service_time)),
1364 .read_seq_string = blkcg_print_rwstat,
1365 },
1366 {
1367 .name = "io_wait_time",
1368 .private = BLKCG_STAT_PRIV(BLKIO_POLICY_PROP,
1369 offsetof(struct blkio_group_stats, wait_time)),
1370 .read_seq_string = blkcg_print_rwstat,
1371 },
1372 {
1373 .name = "io_merged",
1374 .private = BLKCG_STAT_PRIV(BLKIO_POLICY_PROP,
1375 offsetof(struct blkio_group_stats, merged)),
1376 .read_seq_string = blkcg_print_rwstat,
1377 },
1378 {
1379 .name = "io_queued",
1380 .private = BLKCG_STAT_PRIV(BLKIO_POLICY_PROP,
1381 offsetof(struct blkio_group_stats, queued)),
1382 .read_seq_string = blkcg_print_rwstat,
1383 },
1384#ifdef CONFIG_DEBUG_BLK_CGROUP
1385 {
1386 .name = "avg_queue_size",
1387 .read_seq_string = blkcg_print_avg_queue_size,
1388 },
1389 {
1390 .name = "group_wait_time",
1391 .private = BLKCG_STAT_PRIV(BLKIO_POLICY_PROP,
1392 offsetof(struct blkio_group_stats, group_wait_time)),
1393 .read_seq_string = blkcg_print_stat,
1394 },
1395 {
1396 .name = "idle_time",
1397 .private = BLKCG_STAT_PRIV(BLKIO_POLICY_PROP,
1398 offsetof(struct blkio_group_stats, idle_time)),
1399 .read_seq_string = blkcg_print_stat,
1400 },
1401 {
1402 .name = "empty_time",
1403 .private = BLKCG_STAT_PRIV(BLKIO_POLICY_PROP,
1404 offsetof(struct blkio_group_stats, empty_time)),
1405 .read_seq_string = blkcg_print_stat,
1406 },
1407 {
1408 .name = "dequeue",
1409 .private = BLKCG_STAT_PRIV(BLKIO_POLICY_PROP,
1410 offsetof(struct blkio_group_stats, dequeue)),
1411 .read_seq_string = blkcg_print_stat,
1412 },
1413 {
1414 .name = "unaccounted_time",
1415 .private = BLKCG_STAT_PRIV(BLKIO_POLICY_PROP,
1416 offsetof(struct blkio_group_stats, unaccounted_time)),
1417 .read_seq_string = blkcg_print_stat,
1418 },
1419#endif /* CONFIG_DEBUG_BLK_CGROUP */
1420 { } /* terminate */
1421};
25fb5169 1422#else /* GROUP_IOSCHED */
cd1604fa
TH		 1423static struct cfq_group *cfq_lookup_create_cfqg(struct cfq_data *cfqd,
1424 struct blkio_cgroup *blkcg)
25fb5169 1425{
f51b802c 1426 return cfqd->root_group;
25fb5169 1427}
7f1dc8a2 1428
25fb5169
VG		 1429static inline void
1430cfq_link_cfqq_cfqg(struct cfq_queue *cfqq, struct cfq_group *cfqg) {
1431 cfqq->cfqg = cfqg;
1432}
1433
1434#endif /* GROUP_IOSCHED */
1435
498d3aa2 1436/*
c0324a02 1437 * The cfqd->service_trees holds all pending cfq_queue's that have
498d3aa2
JA		 1438 * requests waiting to be processed. It is sorted in the order that
1439 * we will service the queues.
1440 */
a36e71f9 1441static void cfq_service_tree_add(struct cfq_data *cfqd, struct cfq_queue *cfqq,
a6151c3a 1442 bool add_front)
d9e7620e 1443{
0871714e
JA		 1444 struct rb_node **p, *parent;
1445 struct cfq_queue *__cfqq;
d9e7620e 1446 unsigned long rb_key;
c0324a02 1447 struct cfq_rb_root *service_tree;
498d3aa2 1448 int left;
dae739eb 1449 int new_cfqq = 1;
ae30c286 1450
cdb16e8f 1451 service_tree = service_tree_for(cfqq->cfqg, cfqq_prio(cfqq),
65b32a57 1452 cfqq_type(cfqq));
0871714e
JA		 1453 if (cfq_class_idle(cfqq)) {
1454 rb_key = CFQ_IDLE_DELAY;
aa6f6a3d 1455 parent = rb_last(&service_tree->rb);
0871714e
JA		 1456 if (parent && parent != &cfqq->rb_node) {
1457 __cfqq = rb_entry(parent, struct cfq_queue, rb_node);
1458 rb_key += __cfqq->rb_key;
1459 } else
1460 rb_key += jiffies;
1461 } else if (!add_front) {
b9c8946b
JA		 1462 /*
1463 * Get our rb key offset. Subtract any residual slice
1464 * value carried from last service. A negative resid
1465 * count indicates slice overrun, and this should position
1466 * the next service time further away in the tree.
1467 */
edd75ffd 1468 rb_key = cfq_slice_offset(cfqd, cfqq) + jiffies;
b9c8946b 1469 rb_key -= cfqq->slice_resid;
edd75ffd 1470 cfqq->slice_resid = 0;
48e025e6
CZ		 1471 } else {
1472 rb_key = -HZ;
aa6f6a3d 1473 __cfqq = cfq_rb_first(service_tree);
48e025e6
CZ		 1474 rb_key += __cfqq ? __cfqq->rb_key : jiffies;
1475 }
1da177e4 1476
d9e7620e 1477 if (!RB_EMPTY_NODE(&cfqq->rb_node)) {
dae739eb 1478 new_cfqq = 0;
99f9628a 1479 /*
d9e7620e 1480 * same position, nothing more to do
99f9628a 1481 */
c0324a02
CZ		 1482 if (rb_key == cfqq->rb_key &&
1483 cfqq->service_tree == service_tree)
d9e7620e 1484 return;
1da177e4 1485
aa6f6a3d
CZ		 1486 cfq_rb_erase(&cfqq->rb_node, cfqq->service_tree);
1487 cfqq->service_tree = NULL;
1da177e4 1488 }
d9e7620e 1489
498d3aa2 1490 left = 1;
0871714e 1491 parent = NULL;
aa6f6a3d
CZ		 1492 cfqq->service_tree = service_tree;
1493 p = &service_tree->rb.rb_node;
d9e7620e 1494 while (*p) {
67060e37 1495 struct rb_node **n;
cc09e299 1496
d9e7620e
JA		 1497 parent = *p;
1498 __cfqq = rb_entry(parent, struct cfq_queue, rb_node);
1499
0c534e0a 1500 /*
c0324a02 1501 * sort by key, that represents service time.
0c534e0a 1502 */
c0324a02 1503 if (time_before(rb_key, __cfqq->rb_key))
67060e37 1504 n = &(*p)->rb_left;
c0324a02 1505 else {
67060e37 1506 n = &(*p)->rb_right;
cc09e299 1507 left = 0;
c0324a02 1508 }
67060e37
JA		 1509
1510 p = n;
d9e7620e
JA		 1511 }
1512
cc09e299 1513 if (left)
aa6f6a3d 1514 service_tree->left = &cfqq->rb_node;
cc09e299 1515
d9e7620e
JA		 1516 cfqq->rb_key = rb_key;
1517 rb_link_node(&cfqq->rb_node, parent, p);
aa6f6a3d
CZ		 1518 rb_insert_color(&cfqq->rb_node, &service_tree->rb);
1519 service_tree->count++;
20359f27 1520 if (add_front || !new_cfqq)
dae739eb 1521 return;
8184f93e 1522 cfq_group_notify_queue_add(cfqd, cfqq->cfqg);
1da177e4
LT		 1523}
1524
a36e71f9 1525static struct cfq_queue *
f2d1f0ae
JA		 1526cfq_prio_tree_lookup(struct cfq_data *cfqd, struct rb_root *root,
1527 sector_t sector, struct rb_node **ret_parent,
1528 struct rb_node ***rb_link)
a36e71f9 1529{
a36e71f9
JA		 1530 struct rb_node **p, *parent;
1531 struct cfq_queue *cfqq = NULL;
1532
1533 parent = NULL;
1534 p = &root->rb_node;
1535 while (*p) {
1536 struct rb_node **n;
1537
1538 parent = *p;
1539 cfqq = rb_entry(parent, struct cfq_queue, p_node);
1540
1541 /*
1542 * Sort strictly based on sector. Smallest to the left,
1543 * largest to the right.
1544 */
2e46e8b2 1545 if (sector > blk_rq_pos(cfqq->next_rq))
a36e71f9 1546 n = &(*p)->rb_right;
2e46e8b2 1547 else if (sector < blk_rq_pos(cfqq->next_rq))
a36e71f9
JA		 1548 n = &(*p)->rb_left;
1549 else
1550 break;
1551 p = n;
3ac6c9f8 1552 cfqq = NULL;
a36e71f9
JA		 1553 }
1554
1555 *ret_parent = parent;
1556 if (rb_link)
1557 *rb_link = p;
3ac6c9f8 1558 return cfqq;
a36e71f9
JA		 1559}
1560
1561static void cfq_prio_tree_add(struct cfq_data *cfqd, struct cfq_queue *cfqq)
1562{
a36e71f9
JA		 1563 struct rb_node **p, *parent;
1564 struct cfq_queue *__cfqq;
1565
f2d1f0ae
JA		 1566 if (cfqq->p_root) {
1567 rb_erase(&cfqq->p_node, cfqq->p_root);
1568 cfqq->p_root = NULL;
1569 }
a36e71f9
JA		 1570
1571 if (cfq_class_idle(cfqq))
1572 return;
1573 if (!cfqq->next_rq)
1574 return;
1575
f2d1f0ae 1576 cfqq->p_root = &cfqd->prio_trees[cfqq->org_ioprio];
2e46e8b2
TH		 1577 __cfqq = cfq_prio_tree_lookup(cfqd, cfqq->p_root,
1578 blk_rq_pos(cfqq->next_rq), &parent, &p);
3ac6c9f8
JA		 1579 if (!__cfqq) {
1580 rb_link_node(&cfqq->p_node, parent, p);
f2d1f0ae
JA		 1581 rb_insert_color(&cfqq->p_node, cfqq->p_root);
1582 } else
1583 cfqq->p_root = NULL;
a36e71f9
JA		 1584}
1585
498d3aa2
JA		 1586/*
1587 * Update cfqq's position in the service tree.
1588 */
edd75ffd 1589static void cfq_resort_rr_list(struct cfq_data *cfqd, struct cfq_queue *cfqq)
6d048f53 1590{
6d048f53
JA		 1591 /*
1592 * Resorting requires the cfqq to be on the RR list already.
1593 */
a36e71f9 1594 if (cfq_cfqq_on_rr(cfqq)) {
edd75ffd 1595 cfq_service_tree_add(cfqd, cfqq, 0);
a36e71f9
JA		 1596 cfq_prio_tree_add(cfqd, cfqq);
1597 }
6d048f53
JA		 1598}
1599
1da177e4
LT		 1600/*
1601 * add to busy list of queues for service, trying to be fair in ordering
22e2c507 1602 * the pending list according to last request service
1da177e4 1603 */
febffd61 1604static void cfq_add_cfqq_rr(struct cfq_data *cfqd, struct cfq_queue *cfqq)
1da177e4 1605{
7b679138 1606 cfq_log_cfqq(cfqd, cfqq, "add_to_rr");
3b18152c
JA		 1607 BUG_ON(cfq_cfqq_on_rr(cfqq));
1608 cfq_mark_cfqq_on_rr(cfqq);
1da177e4 1609 cfqd->busy_queues++;
ef8a41df
SL		 1610 if (cfq_cfqq_sync(cfqq))
1611 cfqd->busy_sync_queues++;
1da177e4 1612
edd75ffd 1613 cfq_resort_rr_list(cfqd, cfqq);
1da177e4
LT		 1614}
1615
498d3aa2
JA		 1616/*
1617 * Called when the cfqq no longer has requests pending, remove it from
1618 * the service tree.
1619 */
febffd61 1620static void cfq_del_cfqq_rr(struct cfq_data *cfqd, struct cfq_queue *cfqq)
1da177e4 1621{
7b679138 1622 cfq_log_cfqq(cfqd, cfqq, "del_from_rr");
3b18152c
JA		 1623 BUG_ON(!cfq_cfqq_on_rr(cfqq));
1624 cfq_clear_cfqq_on_rr(cfqq);
1da177e4 1625
aa6f6a3d
CZ		 1626 if (!RB_EMPTY_NODE(&cfqq->rb_node)) {
1627 cfq_rb_erase(&cfqq->rb_node, cfqq->service_tree);
1628 cfqq->service_tree = NULL;
1629 }
f2d1f0ae
JA		 1630 if (cfqq->p_root) {
1631 rb_erase(&cfqq->p_node, cfqq->p_root);
1632 cfqq->p_root = NULL;
1633 }
d9e7620e 1634
8184f93e 1635 cfq_group_notify_queue_del(cfqd, cfqq->cfqg);
1da177e4
LT		 1636 BUG_ON(!cfqd->busy_queues);
1637 cfqd->busy_queues--;
ef8a41df
SL		 1638 if (cfq_cfqq_sync(cfqq))
1639 cfqd->busy_sync_queues--;
1da177e4
LT		 1640}
1641
1642/*
1643 * rb tree support functions
1644 */
febffd61 1645static void cfq_del_rq_rb(struct request *rq)
1da177e4 1646{
5e705374 1647 struct cfq_queue *cfqq = RQ_CFQQ(rq);
5e705374 1648 const int sync = rq_is_sync(rq);
1da177e4 1649
b4878f24
JA		 1650 BUG_ON(!cfqq->queued[sync]);
1651 cfqq->queued[sync]--;
1da177e4 1652
5e705374 1653 elv_rb_del(&cfqq->sort_list, rq);
1da177e4 1654
f04a6424
VG		 1655 if (cfq_cfqq_on_rr(cfqq) && RB_EMPTY_ROOT(&cfqq->sort_list)) {
1656 /*
1657 * Queue will be deleted from service tree when we actually
1658 * expire it later. Right now just remove it from prio tree
1659 * as it is empty.
1660 */
1661 if (cfqq->p_root) {
1662 rb_erase(&cfqq->p_node, cfqq->p_root);
1663 cfqq->p_root = NULL;
1664 }
1665 }
1da177e4
LT		 1666}
1667
5e705374 1668static void cfq_add_rq_rb(struct request *rq)
1da177e4 1669{
5e705374 1670 struct cfq_queue *cfqq = RQ_CFQQ(rq);
1da177e4 1671 struct cfq_data *cfqd = cfqq->cfqd;
796d5116 1672 struct request *prev;
1da177e4 1673
5380a101 1674 cfqq->queued[rq_is_sync(rq)]++;
1da177e4 1675
796d5116 1676 elv_rb_add(&cfqq->sort_list, rq);
5fccbf61
JA		 1677
1678 if (!cfq_cfqq_on_rr(cfqq))
1679 cfq_add_cfqq_rr(cfqd, cfqq);
5044eed4
JA		 1680
1681 /*
1682 * check if this request is a better next-serve candidate
1683 */
a36e71f9 1684 prev = cfqq->next_rq;
cf7c25cf 1685 cfqq->next_rq = cfq_choose_req(cfqd, cfqq->next_rq, rq, cfqd->last_position);
a36e71f9
JA		 1686
1687 /*
1688 * adjust priority tree position, if ->next_rq changes
1689 */
1690 if (prev != cfqq->next_rq)
1691 cfq_prio_tree_add(cfqd, cfqq);
1692
5044eed4 1693 BUG_ON(!cfqq->next_rq);
1da177e4
LT		 1694}
1695
febffd61 1696static void cfq_reposition_rq_rb(struct cfq_queue *cfqq, struct request *rq)
1da177e4 1697{
5380a101
JA		 1698 elv_rb_del(&cfqq->sort_list, rq);
1699 cfqq->queued[rq_is_sync(rq)]--;
0381411e 1700 cfq_blkiocg_update_io_remove_stats(cfqg_to_blkg(RQ_CFQG(rq)),
c1768268
TH		 1701 &blkio_policy_cfq, rq_data_dir(rq),
1702 rq_is_sync(rq));
5e705374 1703 cfq_add_rq_rb(rq);
0381411e 1704 cfq_blkiocg_update_io_add_stats(cfqg_to_blkg(RQ_CFQG(rq)),
c1768268 1705 &blkio_policy_cfq,
0381411e
TH		 1706 cfqg_to_blkg(cfqq->cfqd->serving_group),
1707 rq_data_dir(rq), rq_is_sync(rq));
1da177e4
LT		 1708}
1709
206dc69b
JA		 1710static struct request *
1711cfq_find_rq_fmerge(struct cfq_data *cfqd, struct bio *bio)
1da177e4 1712{
206dc69b 1713 struct task_struct *tsk = current;
c5869807 1714 struct cfq_io_cq *cic;
206dc69b 1715 struct cfq_queue *cfqq;
1da177e4 1716
4ac845a2 1717 cic = cfq_cic_lookup(cfqd, tsk->io_context);
91fac317
VT		 1718 if (!cic)
1719 return NULL;
1720
1721 cfqq = cic_to_cfqq(cic, cfq_bio_sync(bio));
89850f7e
JA		 1722 if (cfqq) {
1723 sector_t sector = bio->bi_sector + bio_sectors(bio);
1724
21183b07 1725 return elv_rb_find(&cfqq->sort_list, sector);
89850f7e 1726 }
1da177e4 1727
1da177e4
LT		 1728 return NULL;
1729}
1730
165125e1 1731static void cfq_activate_request(struct request_queue *q, struct request *rq)
1da177e4 1732{
22e2c507 1733 struct cfq_data *cfqd = q->elevator->elevator_data;
3b18152c 1734
53c583d2 1735 cfqd->rq_in_driver++;
7b679138 1736 cfq_log_cfqq(cfqd, RQ_CFQQ(rq), "activate rq, drv=%d",
53c583d2 1737 cfqd->rq_in_driver);
25776e35 1738
5b93629b 1739 cfqd->last_position = blk_rq_pos(rq) + blk_rq_sectors(rq);
1da177e4
LT		 1740}
1741
165125e1 1742static void cfq_deactivate_request(struct request_queue *q, struct request *rq)
1da177e4 1743{
b4878f24
JA		 1744 struct cfq_data *cfqd = q->elevator->elevator_data;
1745
53c583d2
CZ		 1746 WARN_ON(!cfqd->rq_in_driver);
1747 cfqd->rq_in_driver--;
7b679138 1748 cfq_log_cfqq(cfqd, RQ_CFQQ(rq), "deactivate rq, drv=%d",
53c583d2 1749 cfqd->rq_in_driver);
1da177e4
LT		 1750}
1751
b4878f24 1752static void cfq_remove_request(struct request *rq)
1da177e4 1753{
5e705374 1754 struct cfq_queue *cfqq = RQ_CFQQ(rq);
21183b07 1755
5e705374
JA		 1756 if (cfqq->next_rq == rq)
1757 cfqq->next_rq = cfq_find_next_rq(cfqq->cfqd, cfqq, rq);
1da177e4 1758
b4878f24 1759 list_del_init(&rq->queuelist);
5e705374 1760 cfq_del_rq_rb(rq);
374f84ac 1761
45333d5a 1762 cfqq->cfqd->rq_queued--;
0381411e 1763 cfq_blkiocg_update_io_remove_stats(cfqg_to_blkg(RQ_CFQG(rq)),
c1768268
TH		 1764 &blkio_policy_cfq, rq_data_dir(rq),
1765 rq_is_sync(rq));
65299a3b
CH		 1766 if (rq->cmd_flags & REQ_PRIO) {
1767 WARN_ON(!cfqq->prio_pending);
1768 cfqq->prio_pending--;
b53d1ed7 1769 }
1da177e4
LT		 1770}
1771
165125e1
JA		 1772static int cfq_merge(struct request_queue *q, struct request **req,
1773 struct bio *bio)
1da177e4
LT		 1774{
1775 struct cfq_data *cfqd = q->elevator->elevator_data;
1776 struct request *__rq;
1da177e4 1777
206dc69b 1778 __rq = cfq_find_rq_fmerge(cfqd, bio);
22e2c507 1779 if (__rq && elv_rq_merge_ok(__rq, bio)) {
9817064b
JA		 1780 *req = __rq;
1781 return ELEVATOR_FRONT_MERGE;
1da177e4
LT		 1782 }
1783
1784 return ELEVATOR_NO_MERGE;
1da177e4
LT		 1785}
1786
165125e1 1787static void cfq_merged_request(struct request_queue *q, struct request *req,
21183b07 1788 int type)
1da177e4 1789{
21183b07 1790 if (type == ELEVATOR_FRONT_MERGE) {
5e705374 1791 struct cfq_queue *cfqq = RQ_CFQQ(req);
1da177e4 1792
5e705374 1793 cfq_reposition_rq_rb(cfqq, req);
1da177e4 1794 }
1da177e4
LT		 1795}
1796
812d4026
DS		 1797static void cfq_bio_merged(struct request_queue *q, struct request *req,
1798 struct bio *bio)
1799{
0381411e 1800 cfq_blkiocg_update_io_merged_stats(cfqg_to_blkg(RQ_CFQG(req)),
c1768268
TH		 1801 &blkio_policy_cfq, bio_data_dir(bio),
1802 cfq_bio_sync(bio));
812d4026
DS		 1803}
1804
1da177e4 1805static void
165125e1 1806cfq_merged_requests(struct request_queue *q, struct request *rq,
1da177e4
LT		 1807 struct request *next)
1808{
cf7c25cf 1809 struct cfq_queue *cfqq = RQ_CFQQ(rq);
4a0b75c7
SL		 1810 struct cfq_data *cfqd = q->elevator->elevator_data;
1811
22e2c507
JA		 1812 /*
1813 * reposition in fifo if next is older than rq
1814 */
1815 if (!list_empty(&rq->queuelist) && !list_empty(&next->queuelist) &&
30996f40 1816 time_before(rq_fifo_time(next), rq_fifo_time(rq))) {
22e2c507 1817 list_move(&rq->queuelist, &next->queuelist);
30996f40
JA		 1818 rq_set_fifo_time(rq, rq_fifo_time(next));
1819 }
22e2c507 1820
cf7c25cf
CZ		 1821 if (cfqq->next_rq == next)
1822 cfqq->next_rq = rq;
b4878f24 1823 cfq_remove_request(next);
0381411e 1824 cfq_blkiocg_update_io_merged_stats(cfqg_to_blkg(RQ_CFQG(rq)),
c1768268
TH		 1825 &blkio_policy_cfq, rq_data_dir(next),
1826 rq_is_sync(next));
4a0b75c7
SL		 1827
1828 cfqq = RQ_CFQQ(next);
1829 /*
1830 * all requests of this queue are merged to other queues, delete it
1831 * from the service tree. If it's the active_queue,
1832 * cfq_dispatch_requests() will choose to expire it or do idle
1833 */
1834 if (cfq_cfqq_on_rr(cfqq) && RB_EMPTY_ROOT(&cfqq->sort_list) &&
1835 cfqq != cfqd->active_queue)
1836 cfq_del_cfqq_rr(cfqd, cfqq);
22e2c507
JA		 1837}
1838
165125e1 1839static int cfq_allow_merge(struct request_queue *q, struct request *rq,
da775265
JA		 1840 struct bio *bio)
1841{
1842 struct cfq_data *cfqd = q->elevator->elevator_data;
c5869807 1843 struct cfq_io_cq *cic;
da775265 1844 struct cfq_queue *cfqq;
da775265
JA		 1845
1846 /*
ec8acb69 1847 * Disallow merge of a sync bio into an async request.
da775265 1848 */
91fac317 1849 if (cfq_bio_sync(bio) && !rq_is_sync(rq))
a6151c3a 1850 return false;
da775265
JA		 1851
1852 /*
f1a4f4d3 1853 * Lookup the cfqq that this bio will be queued with and allow
07c2bd37 1854 * merge only if rq is queued there.
f1a4f4d3 1855 */
07c2bd37
TH		 1856 cic = cfq_cic_lookup(cfqd, current->io_context);
1857 if (!cic)
1858 return false;
719d3402 1859
91fac317 1860 cfqq = cic_to_cfqq(cic, cfq_bio_sync(bio));
a6151c3a 1861 return cfqq == RQ_CFQQ(rq);
da775265
JA		 1862}
1863
812df48d
DS		 1864static inline void cfq_del_timer(struct cfq_data *cfqd, struct cfq_queue *cfqq)
1865{
1866 del_timer(&cfqd->idle_slice_timer);
c1768268
TH		 1867 cfq_blkiocg_update_idle_time_stats(cfqg_to_blkg(cfqq->cfqg),
1868 &blkio_policy_cfq);
812df48d
DS		 1869}
1870
febffd61
JA		 1871static void __cfq_set_active_queue(struct cfq_data *cfqd,
1872 struct cfq_queue *cfqq)
22e2c507
JA		 1873{
1874 if (cfqq) {
b1ffe737
DS		 1875 cfq_log_cfqq(cfqd, cfqq, "set_active wl_prio:%d wl_type:%d",
1876 cfqd->serving_prio, cfqd->serving_type);
c1768268
TH		 1877 cfq_blkiocg_update_avg_queue_size_stats(cfqg_to_blkg(cfqq->cfqg),
1878 &blkio_policy_cfq);
62a37f6b
JT		 1879 cfqq->slice_start = 0;
1880 cfqq->dispatch_start = jiffies;
1881 cfqq->allocated_slice = 0;
1882 cfqq->slice_end = 0;
1883 cfqq->slice_dispatch = 0;
1884 cfqq->nr_sectors = 0;
1885
1886 cfq_clear_cfqq_wait_request(cfqq);
1887 cfq_clear_cfqq_must_dispatch(cfqq);
1888 cfq_clear_cfqq_must_alloc_slice(cfqq);
1889 cfq_clear_cfqq_fifo_expire(cfqq);
1890 cfq_mark_cfqq_slice_new(cfqq);
1891
1892 cfq_del_timer(cfqd, cfqq);
22e2c507
JA		 1893 }
1894
1895 cfqd->active_queue = cfqq;
1896}
1897
7b14e3b5
JA		 1898/*
1899 * current cfqq expired its slice (or was too idle), select new one
1900 */
1901static void
1902__cfq_slice_expired(struct cfq_data *cfqd, struct cfq_queue *cfqq,
e5ff082e 1903 bool timed_out)
7b14e3b5 1904{
7b679138
JA		 1905 cfq_log_cfqq(cfqd, cfqq, "slice expired t=%d", timed_out);
1906
7b14e3b5 1907 if (cfq_cfqq_wait_request(cfqq))
812df48d 1908 cfq_del_timer(cfqd, cfqq);
7b14e3b5 1909
7b14e3b5 1910 cfq_clear_cfqq_wait_request(cfqq);
f75edf2d 1911 cfq_clear_cfqq_wait_busy(cfqq);
7b14e3b5 1912
ae54abed
SL		 1913 /*
1914 * If this cfqq is shared between multiple processes, check to
1915 * make sure that those processes are still issuing I/Os within
1916 * the mean seek distance. If not, it may be time to break the
1917 * queues apart again.
1918 */
1919 if (cfq_cfqq_coop(cfqq) && CFQQ_SEEKY(cfqq))
1920 cfq_mark_cfqq_split_coop(cfqq);
1921
7b14e3b5 1922 /*
6084cdda 1923 * store what was left of this slice, if the queue idled/timed out
7b14e3b5 1924 */
c553f8e3
SL		 1925 if (timed_out) {
1926 if (cfq_cfqq_slice_new(cfqq))
ba5bd520 1927 cfqq->slice_resid = cfq_scaled_cfqq_slice(cfqd, cfqq);
c553f8e3
SL		 1928 else
1929 cfqq->slice_resid = cfqq->slice_end - jiffies;
7b679138
JA		 1930 cfq_log_cfqq(cfqd, cfqq, "resid=%ld", cfqq->slice_resid);
1931 }
7b14e3b5 1932
e5ff082e 1933 cfq_group_served(cfqd, cfqq->cfqg, cfqq);
dae739eb 1934
f04a6424
VG		 1935 if (cfq_cfqq_on_rr(cfqq) && RB_EMPTY_ROOT(&cfqq->sort_list))
1936 cfq_del_cfqq_rr(cfqd, cfqq);
1937
edd75ffd 1938 cfq_resort_rr_list(cfqd, cfqq);
7b14e3b5
JA		 1939
1940 if (cfqq == cfqd->active_queue)
1941 cfqd->active_queue = NULL;
1942
1943 if (cfqd->active_cic) {
11a3122f 1944 put_io_context(cfqd->active_cic->icq.ioc);
7b14e3b5
JA		 1945 cfqd->active_cic = NULL;
1946 }
7b14e3b5
JA		 1947}
1948
e5ff082e 1949static inline void cfq_slice_expired(struct cfq_data *cfqd, bool timed_out)
7b14e3b5
JA		 1950{
1951 struct cfq_queue *cfqq = cfqd->active_queue;
1952
1953 if (cfqq)
e5ff082e 1954 __cfq_slice_expired(cfqd, cfqq, timed_out);
7b14e3b5
JA		 1955}
1956
498d3aa2
JA		 1957/*
1958 * Get next queue for service. Unless we have a queue preemption,
1959 * we'll simply select the first cfqq in the service tree.
1960 */
6d048f53 1961static struct cfq_queue *cfq_get_next_queue(struct cfq_data *cfqd)
22e2c507 1962{
c0324a02 1963 struct cfq_rb_root *service_tree =
cdb16e8f 1964 service_tree_for(cfqd->serving_group, cfqd->serving_prio,
65b32a57 1965 cfqd->serving_type);
d9e7620e 1966
f04a6424
VG		 1967 if (!cfqd->rq_queued)
1968 return NULL;
1969
1fa8f6d6
VG		 1970 /* There is nothing to dispatch */
1971 if (!service_tree)
1972 return NULL;
c0324a02
CZ		 1973 if (RB_EMPTY_ROOT(&service_tree->rb))
1974 return NULL;
1975 return cfq_rb_first(service_tree);
6d048f53
JA		 1976}
1977
f04a6424
VG		 1978static struct cfq_queue *cfq_get_next_queue_forced(struct cfq_data *cfqd)
1979{
25fb5169 1980 struct cfq_group *cfqg;
f04a6424
VG		 1981 struct cfq_queue *cfqq;
1982 int i, j;
1983 struct cfq_rb_root *st;
1984
1985 if (!cfqd->rq_queued)
1986 return NULL;
1987
25fb5169
VG		 1988 cfqg = cfq_get_next_cfqg(cfqd);
1989 if (!cfqg)
1990 return NULL;
1991
f04a6424
VG		 1992 for_each_cfqg_st(cfqg, i, j, st)
1993 if ((cfqq = cfq_rb_first(st)) != NULL)
1994 return cfqq;
1995 return NULL;
1996}
1997
498d3aa2
JA		 1998/*
1999 * Get and set a new active queue for service.
2000 */
a36e71f9
JA		 2001static struct cfq_queue *cfq_set_active_queue(struct cfq_data *cfqd,
2002 struct cfq_queue *cfqq)
6d048f53 2003{
e00ef799 2004 if (!cfqq)
a36e71f9 2005 cfqq = cfq_get_next_queue(cfqd);
6d048f53 2006
22e2c507 2007 __cfq_set_active_queue(cfqd, cfqq);
3b18152c 2008 return cfqq;
22e2c507
JA		 2009}
2010
d9e7620e
JA		 2011static inline sector_t cfq_dist_from_last(struct cfq_data *cfqd,
2012 struct request *rq)
2013{
83096ebf
TH		 2014 if (blk_rq_pos(rq) >= cfqd->last_position)
2015 return blk_rq_pos(rq) - cfqd->last_position;
d9e7620e 2016 else
83096ebf 2017 return cfqd->last_position - blk_rq_pos(rq);
d9e7620e
JA		 2018}
2019
b2c18e1e 2020static inline int cfq_rq_close(struct cfq_data *cfqd, struct cfq_queue *cfqq,
e9ce335d 2021 struct request *rq)
6d048f53 2022{
e9ce335d 2023 return cfq_dist_from_last(cfqd, rq) <= CFQQ_CLOSE_THR;
6d048f53
JA		 2024}
2025
a36e71f9
JA		 2026static struct cfq_queue *cfqq_close(struct cfq_data *cfqd,
2027 struct cfq_queue *cur_cfqq)
2028{
f2d1f0ae 2029 struct rb_root *root = &cfqd->prio_trees[cur_cfqq->org_ioprio];
a36e71f9
JA		 2030 struct rb_node *parent, *node;
2031 struct cfq_queue *__cfqq;
2032 sector_t sector = cfqd->last_position;
2033
2034 if (RB_EMPTY_ROOT(root))
2035 return NULL;
2036
2037 /*
2038 * First, if we find a request starting at the end of the last
2039 * request, choose it.
2040 */
f2d1f0ae 2041 __cfqq = cfq_prio_tree_lookup(cfqd, root, sector, &parent, NULL);
a36e71f9
JA		 2042 if (__cfqq)
2043 return __cfqq;
2044
2045 /*
2046 * If the exact sector wasn't found, the parent of the NULL leaf
2047 * will contain the closest sector.
2048 */
2049 __cfqq = rb_entry(parent, struct cfq_queue, p_node);
e9ce335d 2050 if (cfq_rq_close(cfqd, cur_cfqq, __cfqq->next_rq))
a36e71f9
JA		 2051 return __cfqq;
2052
2e46e8b2 2053 if (blk_rq_pos(__cfqq->next_rq) < sector)
a36e71f9
JA		 2054 node = rb_next(&__cfqq->p_node);
2055 else
2056 node = rb_prev(&__cfqq->p_node);
2057 if (!node)
2058 return NULL;
2059
2060 __cfqq = rb_entry(node, struct cfq_queue, p_node);
e9ce335d 2061 if (cfq_rq_close(cfqd, cur_cfqq, __cfqq->next_rq))
a36e71f9
JA		 2062 return __cfqq;
2063
2064 return NULL;
2065}
2066
2067/*
2068 * cfqd - obvious
2069 * cur_cfqq - passed in so that we don't decide that the current queue is
2070 * closely cooperating with itself.
2071 *
2072 * So, basically we're assuming that that cur_cfqq has dispatched at least
2073 * one request, and that cfqd->last_position reflects a position on the disk
2074 * associated with the I/O issued by cur_cfqq. I'm not sure this is a valid
2075 * assumption.
2076 */
2077static struct cfq_queue *cfq_close_cooperator(struct cfq_data *cfqd,
b3b6d040 2078 struct cfq_queue *cur_cfqq)
6d048f53 2079{
a36e71f9
JA		 2080 struct cfq_queue *cfqq;
2081
39c01b21
DS		 2082 if (cfq_class_idle(cur_cfqq))
2083 return NULL;
e6c5bc73
JM		 2084 if (!cfq_cfqq_sync(cur_cfqq))
2085 return NULL;
2086 if (CFQQ_SEEKY(cur_cfqq))
2087 return NULL;
2088
b9d8f4c7
GJ		 2089 /*
2090 * Don't search priority tree if it's the only queue in the group.
2091 */
2092 if (cur_cfqq->cfqg->nr_cfqq == 1)
2093 return NULL;
2094
6d048f53 2095 /*
d9e7620e
JA		 2096 * We should notice if some of the queues are cooperating, eg
2097 * working closely on the same area of the disk. In that case,
2098 * we can group them together and don't waste time idling.
6d048f53 2099 */
a36e71f9
JA		 2100 cfqq = cfqq_close(cfqd, cur_cfqq);
2101 if (!cfqq)
2102 return NULL;
2103
8682e1f1
VG		 2104 /* If new queue belongs to different cfq_group, don't choose it */
2105 if (cur_cfqq->cfqg != cfqq->cfqg)
2106 return NULL;
2107
df5fe3e8
JM		 2108 /*
2109 * It only makes sense to merge sync queues.
2110 */
2111 if (!cfq_cfqq_sync(cfqq))
2112 return NULL;
e6c5bc73
JM		 2113 if (CFQQ_SEEKY(cfqq))
2114 return NULL;
df5fe3e8 2115
c0324a02
CZ		 2116 /*
2117 * Do not merge queues of different priority classes
2118 */
2119 if (cfq_class_rt(cfqq) != cfq_class_rt(cur_cfqq))
2120 return NULL;
2121
a36e71f9 2122 return cfqq;
6d048f53
JA		 2123}
2124
a6d44e98
CZ		 2125/*
2126 * Determine whether we should enforce idle window for this queue.
2127 */
2128
2129static bool cfq_should_idle(struct cfq_data *cfqd, struct cfq_queue *cfqq)
2130{
2131 enum wl_prio_t prio = cfqq_prio(cfqq);
718eee05 2132 struct cfq_rb_root *service_tree = cfqq->service_tree;
a6d44e98 2133
f04a6424
VG		 2134 BUG_ON(!service_tree);
2135 BUG_ON(!service_tree->count);
2136
b6508c16
VG		 2137 if (!cfqd->cfq_slice_idle)
2138 return false;
2139
a6d44e98
CZ		 2140 /* We never do for idle class queues. */
2141 if (prio == IDLE_WORKLOAD)
2142 return false;
2143
2144 /* We do for queues that were marked with idle window flag. */
3c764b7a
SL		 2145 if (cfq_cfqq_idle_window(cfqq) &&
2146 !(blk_queue_nonrot(cfqd->queue) && cfqd->hw_tag))
a6d44e98
CZ		 2147 return true;
2148
2149 /*
2150 * Otherwise, we do only if they are the last ones
2151 * in their service tree.
2152 */
f5f2b6ce
SL		 2153 if (service_tree->count == 1 && cfq_cfqq_sync(cfqq) &&
2154 !cfq_io_thinktime_big(cfqd, &service_tree->ttime, false))
c1e44756 2155 return true;
b1ffe737
DS		 2156 cfq_log_cfqq(cfqd, cfqq, "Not idling. st->count:%d",
2157 service_tree->count);
c1e44756 2158 return false;
a6d44e98
CZ		 2159}
2160
6d048f53 2161static void cfq_arm_slice_timer(struct cfq_data *cfqd)
22e2c507 2162{
1792669c 2163 struct cfq_queue *cfqq = cfqd->active_queue;
c5869807 2164 struct cfq_io_cq *cic;
80bdf0c7 2165 unsigned long sl, group_idle = 0;
7b14e3b5 2166
a68bbddb 2167 /*
f7d7b7a7
JA		 2168 * SSD device without seek penalty, disable idling. But only do so
2169 * for devices that support queuing, otherwise we still have a problem
2170 * with sync vs async workloads.
a68bbddb 2171 */
f7d7b7a7 2172 if (blk_queue_nonrot(cfqd->queue) && cfqd->hw_tag)
a68bbddb
JA		 2173 return;
2174
dd67d051 2175 WARN_ON(!RB_EMPTY_ROOT(&cfqq->sort_list));
6d048f53 2176 WARN_ON(cfq_cfqq_slice_new(cfqq));
22e2c507
JA		 2177
2178 /*
2179 * idle is disabled, either manually or by past process history
2180 */
80bdf0c7
VG		 2181 if (!cfq_should_idle(cfqd, cfqq)) {
2182 /* no queue idling. Check for group idling */
2183 if (cfqd->cfq_group_idle)
2184 group_idle = cfqd->cfq_group_idle;
2185 else
2186 return;
2187 }
6d048f53 2188
7b679138 2189 /*
8e550632 2190 * still active requests from this queue, don't idle
7b679138 2191 */
8e550632 2192 if (cfqq->dispatched)
7b679138
JA		 2193 return;
2194
22e2c507
JA		 2195 /*
2196 * task has exited, don't wait
2197 */
206dc69b 2198 cic = cfqd->active_cic;
f6e8d01b 2199 if (!cic || !atomic_read(&cic->icq.ioc->active_ref))
6d048f53
JA		 2200 return;
2201
355b659c
CZ		 2202 /*
2203 * If our average think time is larger than the remaining time
2204 * slice, then don't idle. This avoids overrunning the allotted
2205 * time slice.
2206 */
383cd721
SL		 2207 if (sample_valid(cic->ttime.ttime_samples) &&
2208 (cfqq->slice_end - jiffies < cic->ttime.ttime_mean)) {
fd16d263 2209 cfq_log_cfqq(cfqd, cfqq, "Not idling. think_time:%lu",
383cd721 2210 cic->ttime.ttime_mean);
355b659c 2211 return;
b1ffe737 2212 }
355b659c 2213
80bdf0c7
VG		 2214 /* There are other queues in the group, don't do group idle */
2215 if (group_idle && cfqq->cfqg->nr_cfqq > 1)
2216 return;
2217
3b18152c 2218 cfq_mark_cfqq_wait_request(cfqq);
22e2c507 2219
80bdf0c7
VG		 2220 if (group_idle)
2221 sl = cfqd->cfq_group_idle;
2222 else
2223 sl = cfqd->cfq_slice_idle;
206dc69b 2224
7b14e3b5 2225 mod_timer(&cfqd->idle_slice_timer, jiffies + sl);
c1768268
TH		 2226 cfq_blkiocg_update_set_idle_time_stats(cfqg_to_blkg(cfqq->cfqg),
2227 &blkio_policy_cfq);
80bdf0c7
VG		 2228 cfq_log_cfqq(cfqd, cfqq, "arm_idle: %lu group_idle: %d", sl,
2229 group_idle ? 1 : 0);
1da177e4
LT		 2230}
2231
498d3aa2
JA		 2232/*
2233 * Move request from internal lists to the request queue dispatch list.
2234 */
165125e1 2235static void cfq_dispatch_insert(struct request_queue *q, struct request *rq)
1da177e4 2236{
3ed9a296 2237 struct cfq_data *cfqd = q->elevator->elevator_data;
5e705374 2238 struct cfq_queue *cfqq = RQ_CFQQ(rq);
22e2c507 2239
7b679138
JA		 2240 cfq_log_cfqq(cfqd, cfqq, "dispatch_insert");
2241
06d21886 2242 cfqq->next_rq = cfq_find_next_rq(cfqd, cfqq, rq);
5380a101 2243 cfq_remove_request(rq);
6d048f53 2244 cfqq->dispatched++;
80bdf0c7 2245 (RQ_CFQG(rq))->dispatched++;
5380a101 2246 elv_dispatch_sort(q, rq);
3ed9a296 2247
53c583d2 2248 cfqd->rq_in_flight[cfq_cfqq_sync(cfqq)]++;
c4e7893e 2249 cfqq->nr_sectors += blk_rq_sectors(rq);
0381411e 2250 cfq_blkiocg_update_dispatch_stats(cfqg_to_blkg(cfqq->cfqg),
c1768268
TH		 2251 &blkio_policy_cfq, blk_rq_bytes(rq),
2252 rq_data_dir(rq), rq_is_sync(rq));
1da177e4
LT		 2253}
2254
2255/*
2256 * return expired entry, or NULL to just start from scratch in rbtree
2257 */
febffd61 2258static struct request *cfq_check_fifo(struct cfq_queue *cfqq)
1da177e4 2259{
30996f40 2260 struct request *rq = NULL;
1da177e4 2261
3b18152c 2262 if (cfq_cfqq_fifo_expire(cfqq))
1da177e4 2263 return NULL;
cb887411
JA		 2264
2265 cfq_mark_cfqq_fifo_expire(cfqq);
2266
89850f7e
JA		 2267 if (list_empty(&cfqq->fifo))
2268 return NULL;
1da177e4 2269
89850f7e 2270 rq = rq_entry_fifo(cfqq->fifo.next);
30996f40 2271 if (time_before(jiffies, rq_fifo_time(rq)))
7b679138 2272 rq = NULL;
1da177e4 2273
30996f40 2274 cfq_log_cfqq(cfqq->cfqd, cfqq, "fifo=%p", rq);
6d048f53 2275 return rq;
1da177e4
LT		 2276}
2277
22e2c507
JA		 2278static inline int
2279cfq_prio_to_maxrq(struct cfq_data *cfqd, struct cfq_queue *cfqq)
2280{
2281 const int base_rq = cfqd->cfq_slice_async_rq;
1da177e4 2282
22e2c507 2283 WARN_ON(cfqq->ioprio >= IOPRIO_BE_NR);
1da177e4 2284
b9f8ce05 2285 return 2 * base_rq * (IOPRIO_BE_NR - cfqq->ioprio);
1da177e4
LT		 2286}
2287
df5fe3e8
JM		 2288/*
2289 * Must be called with the queue_lock held.
2290 */
2291static int cfqq_process_refs(struct cfq_queue *cfqq)
2292{
2293 int process_refs, io_refs;
2294
2295 io_refs = cfqq->allocated[READ] + cfqq->allocated[WRITE];
30d7b944 2296 process_refs = cfqq->ref - io_refs;
df5fe3e8
JM		 2297 BUG_ON(process_refs < 0);
2298 return process_refs;
2299}
2300
2301static void cfq_setup_merge(struct cfq_queue *cfqq, struct cfq_queue *new_cfqq)
2302{
e6c5bc73 2303 int process_refs, new_process_refs;
df5fe3e8
JM		 2304 struct cfq_queue *__cfqq;
2305
c10b61f0
JM		 2306 /*
2307 * If there are no process references on the new_cfqq, then it is
2308 * unsafe to follow the ->new_cfqq chain as other cfqq's in the
2309 * chain may have dropped their last reference (not just their
2310 * last process reference).
2311 */
2312 if (!cfqq_process_refs(new_cfqq))
2313 return;
2314
df5fe3e8
JM		 2315 /* Avoid a circular list and skip interim queue merges */
2316 while ((__cfqq = new_cfqq->new_cfqq)) {
2317 if (__cfqq == cfqq)
2318 return;
2319 new_cfqq = __cfqq;
2320 }
2321
2322 process_refs = cfqq_process_refs(cfqq);
c10b61f0 2323 new_process_refs = cfqq_process_refs(new_cfqq);
df5fe3e8
JM		 2324 /*
2325 * If the process for the cfqq has gone away, there is no
2326 * sense in merging the queues.
2327 */
c10b61f0 2328 if (process_refs == 0 || new_process_refs == 0)
df5fe3e8
JM		 2329 return;
2330
e6c5bc73
JM		 2331 /*
2332 * Merge in the direction of the lesser amount of work.
2333 */
e6c5bc73
JM		 2334 if (new_process_refs >= process_refs) {
2335 cfqq->new_cfqq = new_cfqq;
30d7b944 2336 new_cfqq->ref += process_refs;
e6c5bc73
JM		 2337 } else {
2338 new_cfqq->new_cfqq = cfqq;
30d7b944 2339 cfqq->ref += new_process_refs;
e6c5bc73 2340 }
df5fe3e8
JM		 2341}
2342
cdb16e8f 2343static enum wl_type_t cfq_choose_wl(struct cfq_data *cfqd,
65b32a57 2344 struct cfq_group *cfqg, enum wl_prio_t prio)
718eee05
CZ		 2345{
2346 struct cfq_queue *queue;
2347 int i;
2348 bool key_valid = false;
2349 unsigned long lowest_key = 0;
2350 enum wl_type_t cur_best = SYNC_NOIDLE_WORKLOAD;
2351
65b32a57
VG		 2352 for (i = 0; i <= SYNC_WORKLOAD; ++i) {
2353 /* select the one with lowest rb_key */
2354 queue = cfq_rb_first(service_tree_for(cfqg, prio, i));
718eee05
CZ		 2355 if (queue &&
2356 (!key_valid || time_before(queue->rb_key, lowest_key))) {
2357 lowest_key = queue->rb_key;
2358 cur_best = i;
2359 key_valid = true;
2360 }
2361 }
2362
2363 return cur_best;
2364}
2365
cdb16e8f 2366static void choose_service_tree(struct cfq_data *cfqd, struct cfq_group *cfqg)
718eee05 2367{
718eee05
CZ		 2368 unsigned slice;
2369 unsigned count;
cdb16e8f 2370 struct cfq_rb_root *st;
58ff82f3 2371 unsigned group_slice;
e4ea0c16 2372 enum wl_prio_t original_prio = cfqd->serving_prio;
1fa8f6d6 2373
718eee05 2374 /* Choose next priority. RT > BE > IDLE */
58ff82f3 2375 if (cfq_group_busy_queues_wl(RT_WORKLOAD, cfqd, cfqg))
718eee05 2376 cfqd->serving_prio = RT_WORKLOAD;
58ff82f3 2377 else if (cfq_group_busy_queues_wl(BE_WORKLOAD, cfqd, cfqg))
718eee05
CZ		 2378 cfqd->serving_prio = BE_WORKLOAD;
2379 else {
2380 cfqd->serving_prio = IDLE_WORKLOAD;
2381 cfqd->workload_expires = jiffies + 1;
2382 return;
2383 }
2384
e4ea0c16
SL		 2385 if (original_prio != cfqd->serving_prio)
2386 goto new_workload;
2387
718eee05
CZ		 2388 /*
2389 * For RT and BE, we have to choose also the type
2390 * (SYNC, SYNC_NOIDLE, ASYNC), and to compute a workload
2391 * expiration time
2392 */
65b32a57 2393 st = service_tree_for(cfqg, cfqd->serving_prio, cfqd->serving_type);
cdb16e8f 2394 count = st->count;
718eee05
CZ		 2395
2396 /*
65b32a57 2397 * check workload expiration, and that we still have other queues ready
718eee05 2398 */
65b32a57 2399 if (count && !time_after(jiffies, cfqd->workload_expires))
718eee05
CZ		 2400 return;
2401
e4ea0c16 2402new_workload:
718eee05
CZ		 2403 /* otherwise select new workload type */
2404 cfqd->serving_type =
65b32a57
VG		 2405 cfq_choose_wl(cfqd, cfqg, cfqd->serving_prio);
2406 st = service_tree_for(cfqg, cfqd->serving_prio, cfqd->serving_type);
cdb16e8f 2407 count = st->count;
718eee05
CZ		 2408
2409 /*
2410 * the workload slice is computed as a fraction of target latency
2411 * proportional to the number of queues in that workload, over
2412 * all the queues in the same priority class
2413 */
58ff82f3
VG		 2414 group_slice = cfq_group_slice(cfqd, cfqg);
2415
2416 slice = group_slice * count /
2417 max_t(unsigned, cfqg->busy_queues_avg[cfqd->serving_prio],
2418 cfq_group_busy_queues_wl(cfqd->serving_prio, cfqd, cfqg));
718eee05 2419
f26bd1f0
VG		 2420 if (cfqd->serving_type == ASYNC_WORKLOAD) {
2421 unsigned int tmp;
2422
2423 /*
2424 * Async queues are currently system wide. Just taking
2425 * proportion of queues with-in same group will lead to higher
2426 * async ratio system wide as generally root group is going
2427 * to have higher weight. A more accurate thing would be to
2428 * calculate system wide asnc/sync ratio.
2429 */
2430 tmp = cfq_target_latency * cfqg_busy_async_queues(cfqd, cfqg);
2431 tmp = tmp/cfqd->busy_queues;
2432 slice = min_t(unsigned, slice, tmp);
2433
718eee05
CZ		 2434 /* async workload slice is scaled down according to
2435 * the sync/async slice ratio. */
2436 slice = slice * cfqd->cfq_slice[0] / cfqd->cfq_slice[1];
f26bd1f0 2437 } else
718eee05
CZ		 2438 /* sync workload slice is at least 2 * cfq_slice_idle */
2439 slice = max(slice, 2 * cfqd->cfq_slice_idle);
2440
2441 slice = max_t(unsigned, slice, CFQ_MIN_TT);
b1ffe737 2442 cfq_log(cfqd, "workload slice:%d", slice);
718eee05
CZ		 2443 cfqd->workload_expires = jiffies + slice;
2444}
2445
1fa8f6d6
VG		 2446static struct cfq_group *cfq_get_next_cfqg(struct cfq_data *cfqd)
2447{
2448 struct cfq_rb_root *st = &cfqd->grp_service_tree;
25bc6b07 2449 struct cfq_group *cfqg;
1fa8f6d6
VG		 2450
2451 if (RB_EMPTY_ROOT(&st->rb))
2452 return NULL;
25bc6b07 2453 cfqg = cfq_rb_first_group(st);
25bc6b07
VG		 2454 update_min_vdisktime(st);
2455 return cfqg;
1fa8f6d6
VG		 2456}
2457
cdb16e8f
VG		 2458static void cfq_choose_cfqg(struct cfq_data *cfqd)
2459{
1fa8f6d6
VG		 2460 struct cfq_group *cfqg = cfq_get_next_cfqg(cfqd);
2461
2462 cfqd->serving_group = cfqg;
dae739eb
VG		 2463
2464 /* Restore the workload type data */
2465 if (cfqg->saved_workload_slice) {
2466 cfqd->workload_expires = jiffies + cfqg->saved_workload_slice;
2467 cfqd->serving_type = cfqg->saved_workload;
2468 cfqd->serving_prio = cfqg->saved_serving_prio;
66ae2919
GJ		 2469 } else
2470 cfqd->workload_expires = jiffies - 1;
2471
1fa8f6d6 2472 choose_service_tree(cfqd, cfqg);
cdb16e8f
VG		 2473}
2474
22e2c507 2475/*
498d3aa2
JA		 2476 * Select a queue for service. If we have a current active queue,
2477 * check whether to continue servicing it, or retrieve and set a new one.
22e2c507 2478 */
1b5ed5e1 2479static struct cfq_queue *cfq_select_queue(struct cfq_data *cfqd)
1da177e4 2480{
a36e71f9 2481 struct cfq_queue *cfqq, *new_cfqq = NULL;
1da177e4 2482
22e2c507
JA		 2483 cfqq = cfqd->active_queue;
2484 if (!cfqq)
2485 goto new_queue;
1da177e4 2486
f04a6424
VG		 2487 if (!cfqd->rq_queued)
2488 return NULL;
c244bb50
VG		 2489
2490 /*
2491 * We were waiting for group to get backlogged. Expire the queue
2492 */
2493 if (cfq_cfqq_wait_busy(cfqq) && !RB_EMPTY_ROOT(&cfqq->sort_list))
2494 goto expire;
2495
22e2c507 2496 /*
6d048f53 2497 * The active queue has run out of time, expire it and select new.
22e2c507 2498 */
7667aa06
VG		 2499 if (cfq_slice_used(cfqq) && !cfq_cfqq_must_dispatch(cfqq)) {
2500 /*
2501 * If slice had not expired at the completion of last request
2502 * we might not have turned on wait_busy flag. Don't expire
2503 * the queue yet. Allow the group to get backlogged.
2504 *
2505 * The very fact that we have used the slice, that means we
2506 * have been idling all along on this queue and it should be
2507 * ok to wait for this request to complete.
2508 */
82bbbf28
VG		 2509 if (cfqq->cfqg->nr_cfqq == 1 && RB_EMPTY_ROOT(&cfqq->sort_list)
2510 && cfqq->dispatched && cfq_should_idle(cfqd, cfqq)) {
2511 cfqq = NULL;
7667aa06 2512 goto keep_queue;
82bbbf28 2513 } else
80bdf0c7 2514 goto check_group_idle;
7667aa06 2515 }
1da177e4 2516
22e2c507 2517 /*
6d048f53
JA		 2518 * The active queue has requests and isn't expired, allow it to
2519 * dispatch.
22e2c507 2520 */
dd67d051 2521 if (!RB_EMPTY_ROOT(&cfqq->sort_list))
22e2c507 2522 goto keep_queue;
6d048f53 2523
a36e71f9
JA		 2524 /*
2525 * If another queue has a request waiting within our mean seek
2526 * distance, let it run. The expire code will check for close
2527 * cooperators and put the close queue at the front of the service
df5fe3e8 2528 * tree. If possible, merge the expiring queue with the new cfqq.
a36e71f9 2529 */
b3b6d040 2530 new_cfqq = cfq_close_cooperator(cfqd, cfqq);
df5fe3e8
JM		 2531 if (new_cfqq) {
2532 if (!cfqq->new_cfqq)
2533 cfq_setup_merge(cfqq, new_cfqq);
a36e71f9 2534 goto expire;
df5fe3e8 2535 }
a36e71f9 2536
6d048f53
JA		 2537 /*
2538 * No requests pending. If the active queue still has requests in
2539 * flight or is idling for a new request, allow either of these
2540 * conditions to happen (or time out) before selecting a new queue.
2541 */
80bdf0c7
VG		 2542 if (timer_pending(&cfqd->idle_slice_timer)) {
2543 cfqq = NULL;
2544 goto keep_queue;
2545 }
2546
8e1ac665
SL		 2547 /*
2548 * This is a deep seek queue, but the device is much faster than
2549 * the queue can deliver, don't idle
2550 **/
2551 if (CFQQ_SEEKY(cfqq) && cfq_cfqq_idle_window(cfqq) &&
2552 (cfq_cfqq_slice_new(cfqq) ||
2553 (cfqq->slice_end - jiffies > jiffies - cfqq->slice_start))) {
2554 cfq_clear_cfqq_deep(cfqq);
2555 cfq_clear_cfqq_idle_window(cfqq);
2556 }
2557
80bdf0c7
VG		 2558 if (cfqq->dispatched && cfq_should_idle(cfqd, cfqq)) {
2559 cfqq = NULL;
2560 goto keep_queue;
2561 }
2562
2563 /*
2564 * If group idle is enabled and there are requests dispatched from
2565 * this group, wait for requests to complete.
2566 */
2567check_group_idle:
7700fc4f
SL		 2568 if (cfqd->cfq_group_idle && cfqq->cfqg->nr_cfqq == 1 &&
2569 cfqq->cfqg->dispatched &&
2570 !cfq_io_thinktime_big(cfqd, &cfqq->cfqg->ttime, true)) {
caaa5f9f
JA		 2571 cfqq = NULL;
2572 goto keep_queue;
22e2c507
JA		 2573 }
2574
3b18152c 2575expire:
e5ff082e 2576 cfq_slice_expired(cfqd, 0);
3b18152c 2577new_queue:
718eee05
CZ		 2578 /*
2579 * Current queue expired. Check if we have to switch to a new
2580 * service tree
2581 */
2582 if (!new_cfqq)
cdb16e8f 2583 cfq_choose_cfqg(cfqd);
718eee05 2584
a36e71f9 2585 cfqq = cfq_set_active_queue(cfqd, new_cfqq);
22e2c507 2586keep_queue:
3b18152c 2587 return cfqq;
22e2c507
JA		 2588}
2589
febffd61 2590static int __cfq_forced_dispatch_cfqq(struct cfq_queue *cfqq)
d9e7620e
JA		 2591{
2592 int dispatched = 0;
2593
2594 while (cfqq->next_rq) {
2595 cfq_dispatch_insert(cfqq->cfqd->queue, cfqq->next_rq);
2596 dispatched++;
2597 }
2598
2599 BUG_ON(!list_empty(&cfqq->fifo));
f04a6424
VG		 2600
2601 /* By default cfqq is not expired if it is empty. Do it explicitly */
e5ff082e 2602 __cfq_slice_expired(cfqq->cfqd, cfqq, 0);
d9e7620e
JA		 2603 return dispatched;
2604}
2605
498d3aa2
JA		 2606/*
2607 * Drain our current requests. Used for barriers and when switching
2608 * io schedulers on-the-fly.
2609 */
d9e7620e 2610static int cfq_forced_dispatch(struct cfq_data *cfqd)
1b5ed5e1 2611{
0871714e 2612 struct cfq_queue *cfqq;
d9e7620e 2613 int dispatched = 0;
cdb16e8f 2614
3440c49f 2615 /* Expire the timeslice of the current active queue first */
e5ff082e 2616 cfq_slice_expired(cfqd, 0);
3440c49f
DS		 2617 while ((cfqq = cfq_get_next_queue_forced(cfqd)) != NULL) {
2618 __cfq_set_active_queue(cfqd, cfqq);
f04a6424 2619 dispatched += __cfq_forced_dispatch_cfqq(cfqq);
3440c49f 2620 }
1b5ed5e1 2621
1b5ed5e1
TH		 2622 BUG_ON(cfqd->busy_queues);
2623
6923715a 2624 cfq_log(cfqd, "forced_dispatch=%d", dispatched);
1b5ed5e1
TH		 2625 return dispatched;
2626}
2627
abc3c744
SL		 2628static inline bool cfq_slice_used_soon(struct cfq_data *cfqd,
2629 struct cfq_queue *cfqq)
2630{
2631 /* the queue hasn't finished any request, can't estimate */
2632 if (cfq_cfqq_slice_new(cfqq))
c1e44756 2633 return true;
abc3c744
SL		 2634 if (time_after(jiffies + cfqd->cfq_slice_idle * cfqq->dispatched,
2635 cfqq->slice_end))
c1e44756 2636 return true;
abc3c744 2637
c1e44756 2638 return false;
abc3c744
SL		 2639}
2640
0b182d61 2641static bool cfq_may_dispatch(struct cfq_data *cfqd, struct cfq_queue *cfqq)
2f5cb738 2642{
2f5cb738 2643 unsigned int max_dispatch;
22e2c507 2644
5ad531db
JA		 2645 /*
2646 * Drain async requests before we start sync IO
2647 */
53c583d2 2648 if (cfq_should_idle(cfqd, cfqq) && cfqd->rq_in_flight[BLK_RW_ASYNC])
0b182d61 2649 return false;
5ad531db 2650
2f5cb738
JA		 2651 /*
2652 * If this is an async queue and we have sync IO in flight, let it wait
2653 */
53c583d2 2654 if (cfqd->rq_in_flight[BLK_RW_SYNC] && !cfq_cfqq_sync(cfqq))
0b182d61 2655 return false;
2f5cb738 2656
abc3c744 2657 max_dispatch = max_t(unsigned int, cfqd->cfq_quantum / 2, 1);
2f5cb738
JA		 2658 if (cfq_class_idle(cfqq))
2659 max_dispatch = 1;
b4878f24 2660
2f5cb738
JA		 2661 /*
2662 * Does this cfqq already have too much IO in flight?
2663 */
2664 if (cfqq->dispatched >= max_dispatch) {
ef8a41df 2665 bool promote_sync = false;
2f5cb738
JA		 2666 /*
2667 * idle queue must always only have a single IO in flight
2668 */
3ed9a296 2669 if (cfq_class_idle(cfqq))
0b182d61 2670 return false;
3ed9a296 2671
ef8a41df 2672 /*
c4ade94f
LS		 2673 * If there is only one sync queue
2674 * we can ignore async queue here and give the sync
ef8a41df
SL		 2675 * queue no dispatch limit. The reason is a sync queue can
2676 * preempt async queue, limiting the sync queue doesn't make
2677 * sense. This is useful for aiostress test.
2678 */
c4ade94f
LS		 2679 if (cfq_cfqq_sync(cfqq) && cfqd->busy_sync_queues == 1)
2680 promote_sync = true;
ef8a41df 2681
2f5cb738
JA		 2682 /*
2683 * We have other queues, don't allow more IO from this one
2684 */
ef8a41df
SL		 2685 if (cfqd->busy_queues > 1 && cfq_slice_used_soon(cfqd, cfqq) &&
2686 !promote_sync)
0b182d61 2687 return false;
9ede209e 2688
365722bb 2689 /*
474b18cc 2690 * Sole queue user, no limit
365722bb 2691 */
ef8a41df 2692 if (cfqd->busy_queues == 1 || promote_sync)
abc3c744
SL		 2693 max_dispatch = -1;
2694 else
2695 /*
2696 * Normally we start throttling cfqq when cfq_quantum/2
2697 * requests have been dispatched. But we can drive
2698 * deeper queue depths at the beginning of slice
2699 * subjected to upper limit of cfq_quantum.
2700 * */
2701 max_dispatch = cfqd->cfq_quantum;
8e296755
JA		 2702 }
2703
2704 /*
2705 * Async queues must wait a bit before being allowed dispatch.
2706 * We also ramp up the dispatch depth gradually for async IO,
2707 * based on the last sync IO we serviced
2708 */
963b72fc 2709 if (!cfq_cfqq_sync(cfqq) && cfqd->cfq_latency) {
573412b2 2710 unsigned long last_sync = jiffies - cfqd->last_delayed_sync;
8e296755 2711 unsigned int depth;
365722bb 2712
61f0c1dc 2713 depth = last_sync / cfqd->cfq_slice[1];
e00c54c3
JA		 2714 if (!depth && !cfqq->dispatched)
2715 depth = 1;
8e296755
JA		 2716 if (depth < max_dispatch)
2717 max_dispatch = depth;
2f5cb738 2718 }
3ed9a296 2719
0b182d61
JA		 2720 /*
2721 * If we're below the current max, allow a dispatch
2722 */
2723 return cfqq->dispatched < max_dispatch;
2724}
2725
2726/*
2727 * Dispatch a request from cfqq, moving them to the request queue
2728 * dispatch list.
2729 */
2730static bool cfq_dispatch_request(struct cfq_data *cfqd, struct cfq_queue *cfqq)
2731{
2732 struct request *rq;
2733
2734 BUG_ON(RB_EMPTY_ROOT(&cfqq->sort_list));
2735
2736 if (!cfq_may_dispatch(cfqd, cfqq))
2737 return false;
2738
2739 /*
2740 * follow expired path, else get first next available
2741 */
2742 rq = cfq_check_fifo(cfqq);
2743 if (!rq)
2744 rq = cfqq->next_rq;
2745
2746 /*
2747 * insert request into driver dispatch list
2748 */
2749 cfq_dispatch_insert(cfqd->queue, rq);
2750
2751 if (!cfqd->active_cic) {
c5869807 2752 struct cfq_io_cq *cic = RQ_CIC(rq);
0b182d61 2753
c5869807 2754 atomic_long_inc(&cic->icq.ioc->refcount);
0b182d61
JA		 2755 cfqd->active_cic = cic;
2756 }
2757
2758 return true;
2759}
2760
2761/*
2762 * Find the cfqq that we need to service and move a request from that to the
2763 * dispatch list
2764 */
2765static int cfq_dispatch_requests(struct request_queue *q, int force)
2766{
2767 struct cfq_data *cfqd = q->elevator->elevator_data;
2768 struct cfq_queue *cfqq;
2769
2770 if (!cfqd->busy_queues)
2771 return 0;
2772
2773 if (unlikely(force))
2774 return cfq_forced_dispatch(cfqd);
2775
2776 cfqq = cfq_select_queue(cfqd);
2777 if (!cfqq)
8e296755
JA		 2778 return 0;
2779
2f5cb738 2780 /*
0b182d61 2781 * Dispatch a request from this cfqq, if it is allowed
2f5cb738 2782 */
0b182d61
JA		 2783 if (!cfq_dispatch_request(cfqd, cfqq))
2784 return 0;
2785
2f5cb738 2786 cfqq->slice_dispatch++;
b029195d 2787 cfq_clear_cfqq_must_dispatch(cfqq);
22e2c507 2788
2f5cb738
JA		 2789 /*
2790 * expire an async queue immediately if it has used up its slice. idle
2791 * queue always expire after 1 dispatch round.
2792 */
2793 if (cfqd->busy_queues > 1 && ((!cfq_cfqq_sync(cfqq) &&
2794 cfqq->slice_dispatch >= cfq_prio_to_maxrq(cfqd, cfqq)) ||
2795 cfq_class_idle(cfqq))) {
2796 cfqq->slice_end = jiffies + 1;
e5ff082e 2797 cfq_slice_expired(cfqd, 0);
1da177e4
LT		 2798 }
2799
b217a903 2800 cfq_log_cfqq(cfqd, cfqq, "dispatched a request");
2f5cb738 2801 return 1;
1da177e4
LT		 2802}
2803
1da177e4 2804/*
5e705374
JA		 2805 * task holds one reference to the queue, dropped when task exits. each rq
2806 * in-flight on this queue also holds a reference, dropped when rq is freed.
1da177e4 2807 *
b1c35769 2808 * Each cfq queue took a reference on the parent group. Drop it now.
1da177e4
LT		 2809 * queue lock must be held here.
2810 */
2811static void cfq_put_queue(struct cfq_queue *cfqq)
2812{
22e2c507 2813 struct cfq_data *cfqd = cfqq->cfqd;
0bbfeb83 2814 struct cfq_group *cfqg;
22e2c507 2815
30d7b944 2816 BUG_ON(cfqq->ref <= 0);
1da177e4 2817
30d7b944
SL		 2818 cfqq->ref--;
2819 if (cfqq->ref)
1da177e4
LT		 2820 return;
2821
7b679138 2822 cfq_log_cfqq(cfqd, cfqq, "put_queue");
1da177e4 2823 BUG_ON(rb_first(&cfqq->sort_list));
22e2c507 2824 BUG_ON(cfqq->allocated[READ] + cfqq->allocated[WRITE]);
b1c35769 2825 cfqg = cfqq->cfqg;
1da177e4 2826
28f95cbc 2827 if (unlikely(cfqd->active_queue == cfqq)) {
e5ff082e 2828 __cfq_slice_expired(cfqd, cfqq, 0);
23e018a1 2829 cfq_schedule_dispatch(cfqd);
28f95cbc 2830 }
22e2c507 2831
f04a6424 2832 BUG_ON(cfq_cfqq_on_rr(cfqq));
1da177e4 2833 kmem_cache_free(cfq_pool, cfqq);
eb7d8c07 2834 cfqg_put(cfqg);
1da177e4
LT		 2835}
2836
d02a2c07 2837static void cfq_put_cooperator(struct cfq_queue *cfqq)
1da177e4 2838{
df5fe3e8
JM		 2839 struct cfq_queue *__cfqq, *next;
2840
df5fe3e8
JM		 2841 /*
2842 * If this queue was scheduled to merge with another queue, be
2843 * sure to drop the reference taken on that queue (and others in
2844 * the merge chain). See cfq_setup_merge and cfq_merge_cfqqs.
2845 */
2846 __cfqq = cfqq->new_cfqq;
2847 while (__cfqq) {
2848 if (__cfqq == cfqq) {
2849 WARN(1, "cfqq->new_cfqq loop detected\n");
2850 break;
2851 }
2852 next = __cfqq->new_cfqq;
2853 cfq_put_queue(__cfqq);
2854 __cfqq = next;
2855 }
d02a2c07
SL		 2856}
2857
2858static void cfq_exit_cfqq(struct cfq_data *cfqd, struct cfq_queue *cfqq)
2859{
2860 if (unlikely(cfqq == cfqd->active_queue)) {
2861 __cfq_slice_expired(cfqd, cfqq, 0);
2862 cfq_schedule_dispatch(cfqd);
2863 }
2864
2865 cfq_put_cooperator(cfqq);
df5fe3e8 2866
89850f7e
JA		 2867 cfq_put_queue(cfqq);
2868}
22e2c507 2869
9b84cacd
TH		 2870static void cfq_init_icq(struct io_cq *icq)
2871{
2872 struct cfq_io_cq *cic = icq_to_cic(icq);
2873
2874 cic->ttime.last_end_request = jiffies;
2875}
2876
c5869807 2877static void cfq_exit_icq(struct io_cq *icq)
89850f7e 2878{
c5869807 2879 struct cfq_io_cq *cic = icq_to_cic(icq);
283287a5 2880 struct cfq_data *cfqd = cic_to_cfqd(cic);
4faa3c81 2881
ff6657c6
JA		 2882 if (cic->cfqq[BLK_RW_ASYNC]) {
2883 cfq_exit_cfqq(cfqd, cic->cfqq[BLK_RW_ASYNC]);
2884 cic->cfqq[BLK_RW_ASYNC] = NULL;
12a05732
AV		 2885 }
2886
ff6657c6
JA		 2887 if (cic->cfqq[BLK_RW_SYNC]) {
2888 cfq_exit_cfqq(cfqd, cic->cfqq[BLK_RW_SYNC]);
2889 cic->cfqq[BLK_RW_SYNC] = NULL;
12a05732 2890 }
89850f7e
JA		 2891}
2892
abede6da 2893static void cfq_init_prio_data(struct cfq_queue *cfqq, struct cfq_io_cq *cic)
22e2c507
JA		 2894{
2895 struct task_struct *tsk = current;
2896 int ioprio_class;
2897
3b18152c 2898 if (!cfq_cfqq_prio_changed(cfqq))
22e2c507
JA		 2899 return;
2900
598971bf 2901 ioprio_class = IOPRIO_PRIO_CLASS(cic->ioprio);
22e2c507 2902 switch (ioprio_class) {
fe094d98
JA		 2903 default:
2904 printk(KERN_ERR "cfq: bad prio %x\n", ioprio_class);
2905 case IOPRIO_CLASS_NONE:
2906 /*
6d63c275 2907 * no prio set, inherit CPU scheduling settings
fe094d98
JA		 2908 */
2909 cfqq->ioprio = task_nice_ioprio(tsk);
6d63c275 2910 cfqq->ioprio_class = task_nice_ioclass(tsk);
fe094d98
JA		 2911 break;
2912 case IOPRIO_CLASS_RT:
598971bf 2913 cfqq->ioprio = IOPRIO_PRIO_DATA(cic->ioprio);
fe094d98
JA		 2914 cfqq->ioprio_class = IOPRIO_CLASS_RT;
2915 break;
2916 case IOPRIO_CLASS_BE:
598971bf 2917 cfqq->ioprio = IOPRIO_PRIO_DATA(cic->ioprio);
fe094d98
JA		 2918 cfqq->ioprio_class = IOPRIO_CLASS_BE;
2919 break;
2920 case IOPRIO_CLASS_IDLE:
2921 cfqq->ioprio_class = IOPRIO_CLASS_IDLE;
2922 cfqq->ioprio = 7;
2923 cfq_clear_cfqq_idle_window(cfqq);
2924 break;
22e2c507
JA		 2925 }
2926
2927 /*
2928 * keep track of original prio settings in case we have to temporarily
2929 * elevate the priority of this queue
2930 */
2931 cfqq->org_ioprio = cfqq->ioprio;
3b18152c 2932 cfq_clear_cfqq_prio_changed(cfqq);
22e2c507
JA		 2933}
2934
598971bf 2935static void check_ioprio_changed(struct cfq_io_cq *cic, struct bio *bio)
22e2c507 2936{
598971bf 2937 int ioprio = cic->icq.ioc->ioprio;
bca4b914 2938 struct cfq_data *cfqd = cic_to_cfqd(cic);
478a82b0 2939 struct cfq_queue *cfqq;
35e6077c 2940
598971bf
TH		 2941 /*
2942 * Check whether ioprio has changed. The condition may trigger
2943 * spuriously on a newly created cic but there's no harm.
2944 */
2945 if (unlikely(!cfqd) || likely(cic->ioprio == ioprio))
caaa5f9f
JA		 2946 return;
2947
ff6657c6 2948 cfqq = cic->cfqq[BLK_RW_ASYNC];
caaa5f9f
JA		 2949 if (cfqq) {
2950 struct cfq_queue *new_cfqq;
abede6da
TH		 2951 new_cfqq = cfq_get_queue(cfqd, BLK_RW_ASYNC, cic, bio,
2952 GFP_ATOMIC);
caaa5f9f 2953 if (new_cfqq) {
ff6657c6 2954 cic->cfqq[BLK_RW_ASYNC] = new_cfqq;
caaa5f9f
JA		 2955 cfq_put_queue(cfqq);
2956 }
22e2c507 2957 }
caaa5f9f 2958
ff6657c6 2959 cfqq = cic->cfqq[BLK_RW_SYNC];
caaa5f9f
JA		 2960 if (cfqq)
2961 cfq_mark_cfqq_prio_changed(cfqq);
598971bf
TH		 2962
2963 cic->ioprio = ioprio;
22e2c507
JA		 2964}
2965
d5036d77 2966static void cfq_init_cfqq(struct cfq_data *cfqd, struct cfq_queue *cfqq,
a6151c3a 2967 pid_t pid, bool is_sync)
d5036d77
JA		 2968{
2969 RB_CLEAR_NODE(&cfqq->rb_node);
2970 RB_CLEAR_NODE(&cfqq->p_node);
2971 INIT_LIST_HEAD(&cfqq->fifo);
2972
30d7b944 2973 cfqq->ref = 0;
d5036d77
JA		 2974 cfqq->cfqd = cfqd;
2975
2976 cfq_mark_cfqq_prio_changed(cfqq);
2977
2978 if (is_sync) {
2979 if (!cfq_class_idle(cfqq))
2980 cfq_mark_cfqq_idle_window(cfqq);
2981 cfq_mark_cfqq_sync(cfqq);
2982 }
2983 cfqq->pid = pid;
2984}
2985
24610333 2986#ifdef CONFIG_CFQ_GROUP_IOSCHED
598971bf 2987static void check_blkcg_changed(struct cfq_io_cq *cic, struct bio *bio)
24610333 2988{
bca4b914 2989 struct cfq_data *cfqd = cic_to_cfqd(cic);
598971bf
TH		 2990 struct cfq_queue *sync_cfqq;
2991 uint64_t id;
24610333 2992
598971bf
TH		 2993 rcu_read_lock();
2994 id = bio_blkio_cgroup(bio)->id;
2995 rcu_read_unlock();
24610333 2996
598971bf
TH		 2997 /*
2998 * Check whether blkcg has changed. The condition may trigger
2999 * spuriously on a newly created cic but there's no harm.
3000 */
3001 if (unlikely(!cfqd) || likely(cic->blkcg_id == id))
3002 return;
24610333 3003
598971bf 3004 sync_cfqq = cic_to_cfqq(cic, 1);
24610333
VG		 3005 if (sync_cfqq) {
3006 /*
3007 * Drop reference to sync queue. A new sync queue will be
3008 * assigned in new group upon arrival of a fresh request.
3009 */
3010 cfq_log_cfqq(cfqd, sync_cfqq, "changed cgroup");
3011 cic_set_cfqq(cic, NULL, 1);
3012 cfq_put_queue(sync_cfqq);
3013 }
598971bf
TH		 3014
3015 cic->blkcg_id = id;
24610333 3016}
598971bf
TH		 3017#else
3018static inline void check_blkcg_changed(struct cfq_io_cq *cic, struct bio *bio) { }
24610333
VG		 3019#endif /* CONFIG_CFQ_GROUP_IOSCHED */
3020
22e2c507 3021static struct cfq_queue *
abede6da
TH		 3022cfq_find_alloc_queue(struct cfq_data *cfqd, bool is_sync, struct cfq_io_cq *cic,
3023 struct bio *bio, gfp_t gfp_mask)
22e2c507 3024{
0a5a7d0e 3025 struct blkio_cgroup *blkcg;
22e2c507 3026 struct cfq_queue *cfqq, *new_cfqq = NULL;
cdb16e8f 3027 struct cfq_group *cfqg;
22e2c507
JA		 3028
3029retry:
2a7f1244
TH		 3030 rcu_read_lock();
3031
4f85cb96 3032 blkcg = bio_blkio_cgroup(bio);
cd1604fa 3033 cfqg = cfq_lookup_create_cfqg(cfqd, blkcg);
91fac317 3034 cfqq = cic_to_cfqq(cic, is_sync);
22e2c507 3035
6118b70b
JA		 3036 /*
3037 * Always try a new alloc if we fell back to the OOM cfqq
3038 * originally, since it should just be a temporary situation.
3039 */
3040 if (!cfqq || cfqq == &cfqd->oom_cfqq) {
3041 cfqq = NULL;
22e2c507
JA		 3042 if (new_cfqq) {
3043 cfqq = new_cfqq;
3044 new_cfqq = NULL;
3045 } else if (gfp_mask & __GFP_WAIT) {
2a7f1244 3046 rcu_read_unlock();
22e2c507 3047 spin_unlock_irq(cfqd->queue->queue_lock);
94f6030c 3048 new_cfqq = kmem_cache_alloc_node(cfq_pool,
6118b70b 3049 gfp_mask | __GFP_ZERO,
94f6030c 3050 cfqd->queue->node);
22e2c507 3051 spin_lock_irq(cfqd->queue->queue_lock);
6118b70b
JA		 3052 if (new_cfqq)
3053 goto retry;
22e2c507 3054 } else {
94f6030c
CL		 3055 cfqq = kmem_cache_alloc_node(cfq_pool,
3056 gfp_mask | __GFP_ZERO,
3057 cfqd->queue->node);
22e2c507
JA		 3058 }
3059
6118b70b
JA		 3060 if (cfqq) {
3061 cfq_init_cfqq(cfqd, cfqq, current->pid, is_sync);
abede6da 3062 cfq_init_prio_data(cfqq, cic);
cdb16e8f 3063 cfq_link_cfqq_cfqg(cfqq, cfqg);
6118b70b
JA		 3064 cfq_log_cfqq(cfqd, cfqq, "alloced");
3065 } else
3066 cfqq = &cfqd->oom_cfqq;
22e2c507
JA		 3067 }
3068
3069 if (new_cfqq)
3070 kmem_cache_free(cfq_pool, new_cfqq);
3071
2a7f1244 3072 rcu_read_unlock();
22e2c507
JA		 3073 return cfqq;
3074}
3075
c2dea2d1
VT		 3076static struct cfq_queue **
3077cfq_async_queue_prio(struct cfq_data *cfqd, int ioprio_class, int ioprio)
3078{
fe094d98 3079 switch (ioprio_class) {
c2dea2d1
VT		 3080 case IOPRIO_CLASS_RT:
3081 return &cfqd->async_cfqq[0][ioprio];
598971bf
TH		 3082 case IOPRIO_CLASS_NONE:
3083 ioprio = IOPRIO_NORM;
3084 /* fall through */
c2dea2d1
VT		 3085 case IOPRIO_CLASS_BE:
3086 return &cfqd->async_cfqq[1][ioprio];
3087 case IOPRIO_CLASS_IDLE:
3088 return &cfqd->async_idle_cfqq;
3089 default:
3090 BUG();
3091 }
3092}
3093
15c31be4 3094static struct cfq_queue *
abede6da 3095cfq_get_queue(struct cfq_data *cfqd, bool is_sync, struct cfq_io_cq *cic,
4f85cb96 3096 struct bio *bio, gfp_t gfp_mask)
15c31be4 3097{
598971bf
TH		 3098 const int ioprio_class = IOPRIO_PRIO_CLASS(cic->ioprio);
3099 const int ioprio = IOPRIO_PRIO_DATA(cic->ioprio);
c2dea2d1 3100 struct cfq_queue **async_cfqq = NULL;
15c31be4
JA		 3101 struct cfq_queue *cfqq = NULL;
3102
c2dea2d1
VT		 3103 if (!is_sync) {
3104 async_cfqq = cfq_async_queue_prio(cfqd, ioprio_class, ioprio);
3105 cfqq = *async_cfqq;
3106 }
3107
6118b70b 3108 if (!cfqq)
abede6da 3109 cfqq = cfq_find_alloc_queue(cfqd, is_sync, cic, bio, gfp_mask);
15c31be4
JA		 3110
3111 /*
3112 * pin the queue now that it's allocated, scheduler exit will prune it
3113 */
c2dea2d1 3114 if (!is_sync && !(*async_cfqq)) {
30d7b944 3115 cfqq->ref++;
c2dea2d1 3116 *async_cfqq = cfqq;
15c31be4
JA		 3117 }
3118
30d7b944 3119 cfqq->ref++;
15c31be4
JA		 3120 return cfqq;
3121}
3122
22e2c507 3123static void
383cd721 3124__cfq_update_io_thinktime(struct cfq_ttime *ttime, unsigned long slice_idle)
1da177e4 3125{
383cd721
SL		 3126 unsigned long elapsed = jiffies - ttime->last_end_request;
3127 elapsed = min(elapsed, 2UL * slice_idle);
db3b5848 3128
383cd721
SL		 3129 ttime->ttime_samples = (7*ttime->ttime_samples + 256) / 8;
3130 ttime->ttime_total = (7*ttime->ttime_total + 256*elapsed) / 8;
3131 ttime->ttime_mean = (ttime->ttime_total + 128) / ttime->ttime_samples;
3132}
3133
3134static void
3135cfq_update_io_thinktime(struct cfq_data *cfqd, struct cfq_queue *cfqq,
c5869807 3136 struct cfq_io_cq *cic)
383cd721 3137{
f5f2b6ce 3138 if (cfq_cfqq_sync(cfqq)) {
383cd721 3139 __cfq_update_io_thinktime(&cic->ttime, cfqd->cfq_slice_idle);
f5f2b6ce
SL		 3140 __cfq_update_io_thinktime(&cfqq->service_tree->ttime,
3141 cfqd->cfq_slice_idle);
3142 }
7700fc4f
SL		 3143#ifdef CONFIG_CFQ_GROUP_IOSCHED
3144 __cfq_update_io_thinktime(&cfqq->cfqg->ttime, cfqd->cfq_group_idle);
3145#endif
22e2c507 3146}
1da177e4 3147
206dc69b 3148static void
b2c18e1e 3149cfq_update_io_seektime(struct cfq_data *cfqd, struct cfq_queue *cfqq,
6d048f53 3150 struct request *rq)
206dc69b 3151{
3dde36dd 3152 sector_t sdist = 0;
41647e7a 3153 sector_t n_sec = blk_rq_sectors(rq);
3dde36dd
CZ		 3154 if (cfqq->last_request_pos) {
3155 if (cfqq->last_request_pos < blk_rq_pos(rq))
3156 sdist = blk_rq_pos(rq) - cfqq->last_request_pos;
3157 else
3158 sdist = cfqq->last_request_pos - blk_rq_pos(rq);
3159 }
206dc69b 3160
3dde36dd 3161 cfqq->seek_history <<= 1;
41647e7a
CZ		 3162 if (blk_queue_nonrot(cfqd->queue))
3163 cfqq->seek_history |= (n_sec < CFQQ_SECT_THR_NONROT);
3164 else
3165 cfqq->seek_history |= (sdist > CFQQ_SEEK_THR);
206dc69b 3166}
1da177e4 3167
22e2c507
JA		 3168/*
3169 * Disable idle window if the process thinks too long or seeks so much that
3170 * it doesn't matter
3171 */
3172static void
3173cfq_update_idle_window(struct cfq_data *cfqd, struct cfq_queue *cfqq,
c5869807 3174 struct cfq_io_cq *cic)
22e2c507 3175{
7b679138 3176 int old_idle, enable_idle;
1be92f2f 3177
0871714e
JA		 3178 /*
3179 * Don't idle for async or idle io prio class
3180 */
3181 if (!cfq_cfqq_sync(cfqq) || cfq_class_idle(cfqq))
1be92f2f
JA		 3182 return;
3183
c265a7f4 3184 enable_idle = old_idle = cfq_cfqq_idle_window(cfqq);
1da177e4 3185
76280aff
CZ		 3186 if (cfqq->queued[0] + cfqq->queued[1] >= 4)
3187 cfq_mark_cfqq_deep(cfqq);
3188
749ef9f8
CZ		 3189 if (cfqq->next_rq && (cfqq->next_rq->cmd_flags & REQ_NOIDLE))
3190 enable_idle = 0;
f6e8d01b 3191 else if (!atomic_read(&cic->icq.ioc->active_ref) ||
c5869807
TH		 3192 !cfqd->cfq_slice_idle ||
3193 (!cfq_cfqq_deep(cfqq) && CFQQ_SEEKY(cfqq)))
22e2c507 3194 enable_idle = 0;
383cd721
SL		 3195 else if (sample_valid(cic->ttime.ttime_samples)) {
3196 if (cic->ttime.ttime_mean > cfqd->cfq_slice_idle)
22e2c507
JA		 3197 enable_idle = 0;
3198 else
3199 enable_idle = 1;
1da177e4
LT		 3200 }
3201
7b679138
JA		 3202 if (old_idle != enable_idle) {
3203 cfq_log_cfqq(cfqd, cfqq, "idle=%d", enable_idle);
3204 if (enable_idle)
3205 cfq_mark_cfqq_idle_window(cfqq);
3206 else
3207 cfq_clear_cfqq_idle_window(cfqq);
3208 }
22e2c507 3209}
1da177e4 3210
22e2c507
JA		 3211/*
3212 * Check if new_cfqq should preempt the currently active queue. Return 0 for
3213 * no or if we aren't sure, a 1 will cause a preempt.
3214 */
a6151c3a 3215static bool
22e2c507 3216cfq_should_preempt(struct cfq_data *cfqd, struct cfq_queue *new_cfqq,
5e705374 3217 struct request *rq)
22e2c507 3218{
6d048f53 3219 struct cfq_queue *cfqq;
22e2c507 3220
6d048f53
JA		 3221 cfqq = cfqd->active_queue;
3222 if (!cfqq)
a6151c3a 3223 return false;
22e2c507 3224
6d048f53 3225 if (cfq_class_idle(new_cfqq))
a6151c3a 3226 return false;
22e2c507
JA		 3227
3228 if (cfq_class_idle(cfqq))
a6151c3a 3229 return true;
1e3335de 3230
875feb63
DS		 3231 /*
3232 * Don't allow a non-RT request to preempt an ongoing RT cfqq timeslice.
3233 */
3234 if (cfq_class_rt(cfqq) && !cfq_class_rt(new_cfqq))
3235 return false;
3236
374f84ac
JA		 3237 /*
3238 * if the new request is sync, but the currently running queue is
3239 * not, let the sync request have priority.
3240 */
5e705374 3241 if (rq_is_sync(rq) && !cfq_cfqq_sync(cfqq))
a6151c3a 3242 return true;
1e3335de 3243
8682e1f1
VG		 3244 if (new_cfqq->cfqg != cfqq->cfqg)
3245 return false;
3246
3247 if (cfq_slice_used(cfqq))
3248 return true;
3249
3250 /* Allow preemption only if we are idling on sync-noidle tree */
3251 if (cfqd->serving_type == SYNC_NOIDLE_WORKLOAD &&
3252 cfqq_type(new_cfqq) == SYNC_NOIDLE_WORKLOAD &&
3253 new_cfqq->service_tree->count == 2 &&
3254 RB_EMPTY_ROOT(&cfqq->sort_list))
3255 return true;
3256
b53d1ed7
JA		 3257 /*
3258 * So both queues are sync. Let the new request get disk time if
3259 * it's a metadata request and the current queue is doing regular IO.
3260 */
65299a3b 3261 if ((rq->cmd_flags & REQ_PRIO) && !cfqq->prio_pending)
b53d1ed7
JA		 3262 return true;
3263
3a9a3f6c
DS		 3264 /*
3265 * Allow an RT request to pre-empt an ongoing non-RT cfqq timeslice.
3266 */
3267 if (cfq_class_rt(new_cfqq) && !cfq_class_rt(cfqq))
a6151c3a 3268 return true;
3a9a3f6c 3269
d2d59e18
SL		 3270 /* An idle queue should not be idle now for some reason */
3271 if (RB_EMPTY_ROOT(&cfqq->sort_list) && !cfq_should_idle(cfqd, cfqq))
3272 return true;
3273
1e3335de 3274 if (!cfqd->active_cic || !cfq_cfqq_wait_request(cfqq))
a6151c3a 3275 return false;
1e3335de
JA		 3276
3277 /*
3278 * if this request is as-good as one we would expect from the
3279 * current cfqq, let it preempt
3280 */
e9ce335d 3281 if (cfq_rq_close(cfqd, cfqq, rq))
a6151c3a 3282 return true;
1e3335de 3283
a6151c3a 3284 return false;
22e2c507
JA		 3285}
3286
3287/*
3288 * cfqq preempts the active queue. if we allowed preempt with no slice left,
3289 * let it have half of its nominal slice.
3290 */
3291static void cfq_preempt_queue(struct cfq_data *cfqd, struct cfq_queue *cfqq)
3292{
df0793ab
SL		 3293 enum wl_type_t old_type = cfqq_type(cfqd->active_queue);
3294
7b679138 3295 cfq_log_cfqq(cfqd, cfqq, "preempt");
df0793ab 3296 cfq_slice_expired(cfqd, 1);
22e2c507 3297
f8ae6e3e
SL		 3298 /*
3299 * workload type is changed, don't save slice, otherwise preempt
3300 * doesn't happen
3301 */
df0793ab 3302 if (old_type != cfqq_type(cfqq))
f8ae6e3e
SL		 3303 cfqq->cfqg->saved_workload_slice = 0;
3304
bf572256
JA		 3305 /*
3306 * Put the new queue at the front of the of the current list,
3307 * so we know that it will be selected next.
3308 */
3309 BUG_ON(!cfq_cfqq_on_rr(cfqq));
edd75ffd
JA		 3310
3311 cfq_service_tree_add(cfqd, cfqq, 1);
eda5e0c9 3312
62a37f6b
JT		 3313 cfqq->slice_end = 0;
3314 cfq_mark_cfqq_slice_new(cfqq);
22e2c507
JA		 3315}
3316
22e2c507 3317/*
5e705374 3318 * Called when a new fs request (rq) is added (to cfqq). Check if there's
22e2c507
JA		 3319 * something we should do about it
3320 */
3321static void
5e705374
JA		 3322cfq_rq_enqueued(struct cfq_data *cfqd, struct cfq_queue *cfqq,
3323 struct request *rq)
22e2c507 3324{
c5869807 3325 struct cfq_io_cq *cic = RQ_CIC(rq);
12e9fddd 3326
45333d5a 3327 cfqd->rq_queued++;
65299a3b
CH		 3328 if (rq->cmd_flags & REQ_PRIO)
3329 cfqq->prio_pending++;
374f84ac 3330
383cd721 3331 cfq_update_io_thinktime(cfqd, cfqq, cic);
b2c18e1e 3332 cfq_update_io_seektime(cfqd, cfqq, rq);
9c2c38a1
JA		 3333 cfq_update_idle_window(cfqd, cfqq, cic);
3334
b2c18e1e 3335 cfqq->last_request_pos = blk_rq_pos(rq) + blk_rq_sectors(rq);
22e2c507
JA		 3336
3337 if (cfqq == cfqd->active_queue) {
3338 /*
b029195d
JA		 3339 * Remember that we saw a request from this process, but
3340 * don't start queuing just yet. Otherwise we risk seeing lots
3341 * of tiny requests, because we disrupt the normal plugging
d6ceb25e
JA		 3342 * and merging. If the request is already larger than a single
3343 * page, let it rip immediately. For that case we assume that
2d870722
JA		 3344 * merging is already done. Ditto for a busy system that
3345 * has other work pending, don't risk delaying until the
3346 * idle timer unplug to continue working.
22e2c507 3347 */
d6ceb25e 3348 if (cfq_cfqq_wait_request(cfqq)) {
2d870722
JA		 3349 if (blk_rq_bytes(rq) > PAGE_CACHE_SIZE ||
3350 cfqd->busy_queues > 1) {
812df48d 3351 cfq_del_timer(cfqd, cfqq);
554554f6 3352 cfq_clear_cfqq_wait_request(cfqq);
24ecfbe2 3353 __blk_run_queue(cfqd->queue);
a11cdaa7 3354 } else {
e98ef89b 3355 cfq_blkiocg_update_idle_time_stats(
c1768268
TH		 3356 cfqg_to_blkg(cfqq->cfqg),
3357 &blkio_policy_cfq);
bf791937 3358 cfq_mark_cfqq_must_dispatch(cfqq);
a11cdaa7 3359 }
d6ceb25e 3360 }
5e705374 3361 } else if (cfq_should_preempt(cfqd, cfqq, rq)) {
22e2c507
JA		 3362 /*
3363 * not the active queue - expire current slice if it is
3364 * idle and has expired it's mean thinktime or this new queue
3a9a3f6c
DS		 3365 * has some old slice time left and is of higher priority or
3366 * this new queue is RT and the current one is BE
22e2c507
JA		 3367 */
3368 cfq_preempt_queue(cfqd, cfqq);
24ecfbe2 3369 __blk_run_queue(cfqd->queue);
22e2c507 3370 }
1da177e4
LT		 3371}
3372
165125e1 3373static void cfq_insert_request(struct request_queue *q, struct request *rq)
1da177e4 3374{
b4878f24 3375 struct cfq_data *cfqd = q->elevator->elevator_data;
5e705374 3376 struct cfq_queue *cfqq = RQ_CFQQ(rq);
22e2c507 3377
7b679138 3378 cfq_log_cfqq(cfqd, cfqq, "insert_request");
abede6da 3379 cfq_init_prio_data(cfqq, RQ_CIC(rq));
1da177e4 3380
30996f40 3381 rq_set_fifo_time(rq, jiffies + cfqd->cfq_fifo_expire[rq_is_sync(rq)]);
22e2c507 3382 list_add_tail(&rq->queuelist, &cfqq->fifo);
aa6f6a3d 3383 cfq_add_rq_rb(rq);
0381411e 3384 cfq_blkiocg_update_io_add_stats(cfqg_to_blkg(RQ_CFQG(rq)),
c1768268 3385 &blkio_policy_cfq,
0381411e
TH		 3386 cfqg_to_blkg(cfqd->serving_group),
3387 rq_data_dir(rq), rq_is_sync(rq));
5e705374 3388 cfq_rq_enqueued(cfqd, cfqq, rq);
1da177e4
LT		 3389}
3390
45333d5a
AC		 3391/*
3392 * Update hw_tag based on peak queue depth over 50 samples under
3393 * sufficient load.
3394 */
3395static void cfq_update_hw_tag(struct cfq_data *cfqd)
3396{
1a1238a7
SL		 3397 struct cfq_queue *cfqq = cfqd->active_queue;
3398
53c583d2
CZ		 3399 if (cfqd->rq_in_driver > cfqd->hw_tag_est_depth)
3400 cfqd->hw_tag_est_depth = cfqd->rq_in_driver;
e459dd08
CZ		 3401
3402 if (cfqd->hw_tag == 1)
3403 return;
45333d5a
AC		 3404
3405 if (cfqd->rq_queued <= CFQ_HW_QUEUE_MIN &&
53c583d2 3406 cfqd->rq_in_driver <= CFQ_HW_QUEUE_MIN)
45333d5a
AC		 3407 return;
3408
1a1238a7
SL		 3409 /*
3410 * If active queue hasn't enough requests and can idle, cfq might not
3411 * dispatch sufficient requests to hardware. Don't zero hw_tag in this
3412 * case
3413 */
3414 if (cfqq && cfq_cfqq_idle_window(cfqq) &&
3415 cfqq->dispatched + cfqq->queued[0] + cfqq->queued[1] <
53c583d2 3416 CFQ_HW_QUEUE_MIN && cfqd->rq_in_driver < CFQ_HW_QUEUE_MIN)
1a1238a7
SL		 3417 return;
3418
45333d5a
AC		 3419 if (cfqd->hw_tag_samples++ < 50)
3420 return;
3421
e459dd08 3422 if (cfqd->hw_tag_est_depth >= CFQ_HW_QUEUE_MIN)
45333d5a
AC		 3423 cfqd->hw_tag = 1;
3424 else
3425 cfqd->hw_tag = 0;
45333d5a
AC		 3426}
3427
7667aa06
VG		 3428static bool cfq_should_wait_busy(struct cfq_data *cfqd, struct cfq_queue *cfqq)
3429{
c5869807 3430 struct cfq_io_cq *cic = cfqd->active_cic;
7667aa06 3431
02a8f01b
JT		 3432 /* If the queue already has requests, don't wait */
3433 if (!RB_EMPTY_ROOT(&cfqq->sort_list))
3434 return false;
3435
7667aa06
VG		 3436 /* If there are other queues in the group, don't wait */
3437 if (cfqq->cfqg->nr_cfqq > 1)
3438 return false;
3439
7700fc4f
SL		 3440 /* the only queue in the group, but think time is big */
3441 if (cfq_io_thinktime_big(cfqd, &cfqq->cfqg->ttime, true))
3442 return false;
3443
7667aa06
VG		 3444 if (cfq_slice_used(cfqq))
3445 return true;
3446
3447 /* if slice left is less than think time, wait busy */
383cd721
SL		 3448 if (cic && sample_valid(cic->ttime.ttime_samples)
3449 && (cfqq->slice_end - jiffies < cic->ttime.ttime_mean))
7667aa06
VG		 3450 return true;
3451
3452 /*
3453 * If think times is less than a jiffy than ttime_mean=0 and above
3454 * will not be true. It might happen that slice has not expired yet
3455 * but will expire soon (4-5 ns) during select_queue(). To cover the
3456 * case where think time is less than a jiffy, mark the queue wait
3457 * busy if only 1 jiffy is left in the slice.
3458 */
3459 if (cfqq->slice_end - jiffies == 1)
3460 return true;
3461
3462 return false;
3463}
3464
165125e1 3465static void cfq_completed_request(struct request_queue *q, struct request *rq)
1da177e4 3466{
5e705374 3467 struct cfq_queue *cfqq = RQ_CFQQ(rq);
b4878f24 3468 struct cfq_data *cfqd = cfqq->cfqd;
5380a101 3469 const int sync = rq_is_sync(rq);
b4878f24 3470 unsigned long now;
1da177e4 3471
b4878f24 3472 now = jiffies;
33659ebb
CH		 3473 cfq_log_cfqq(cfqd, cfqq, "complete rqnoidle %d",
3474 !!(rq->cmd_flags & REQ_NOIDLE));
1da177e4 3475
45333d5a
AC		 3476 cfq_update_hw_tag(cfqd);
3477
53c583d2 3478 WARN_ON(!cfqd->rq_in_driver);
6d048f53 3479 WARN_ON(!cfqq->dispatched);
53c583d2 3480 cfqd->rq_in_driver--;
6d048f53 3481 cfqq->dispatched--;
80bdf0c7 3482 (RQ_CFQG(rq))->dispatched--;
0381411e 3483 cfq_blkiocg_update_completion_stats(cfqg_to_blkg(cfqq->cfqg),
c1768268
TH		 3484 &blkio_policy_cfq, rq_start_time_ns(rq),
3485 rq_io_start_time_ns(rq), rq_data_dir(rq),
3486 rq_is_sync(rq));
1da177e4 3487
53c583d2 3488 cfqd->rq_in_flight[cfq_cfqq_sync(cfqq)]--;
3ed9a296 3489
365722bb 3490 if (sync) {
f5f2b6ce
SL		 3491 struct cfq_rb_root *service_tree;
3492
383cd721 3493 RQ_CIC(rq)->ttime.last_end_request = now;
f5f2b6ce
SL		 3494
3495 if (cfq_cfqq_on_rr(cfqq))
3496 service_tree = cfqq->service_tree;
3497 else
3498 service_tree = service_tree_for(cfqq->cfqg,
3499 cfqq_prio(cfqq), cfqq_type(cfqq));
3500 service_tree->ttime.last_end_request = now;
573412b2
CZ		 3501 if (!time_after(rq->start_time + cfqd->cfq_fifo_expire[1], now))
3502 cfqd->last_delayed_sync = now;
365722bb 3503 }
caaa5f9f 3504
7700fc4f
SL		 3505#ifdef CONFIG_CFQ_GROUP_IOSCHED
3506 cfqq->cfqg->ttime.last_end_request = now;
3507#endif
3508
caaa5f9f
JA		 3509 /*
3510 * If this is the active queue, check if it needs to be expired,
3511 * or if we want to idle in case it has no pending requests.
3512 */
3513 if (cfqd->active_queue == cfqq) {
a36e71f9
JA		 3514 const bool cfqq_empty = RB_EMPTY_ROOT(&cfqq->sort_list);
3515
44f7c160
JA		 3516 if (cfq_cfqq_slice_new(cfqq)) {
3517 cfq_set_prio_slice(cfqd, cfqq);
3518 cfq_clear_cfqq_slice_new(cfqq);
3519 }
f75edf2d
VG		 3520
3521 /*
7667aa06
VG		 3522 * Should we wait for next request to come in before we expire
3523 * the queue.
f75edf2d 3524 */
7667aa06 3525 if (cfq_should_wait_busy(cfqd, cfqq)) {
80bdf0c7
VG		 3526 unsigned long extend_sl = cfqd->cfq_slice_idle;
3527 if (!cfqd->cfq_slice_idle)
3528 extend_sl = cfqd->cfq_group_idle;
3529 cfqq->slice_end = jiffies + extend_sl;
f75edf2d 3530 cfq_mark_cfqq_wait_busy(cfqq);
b1ffe737 3531 cfq_log_cfqq(cfqd, cfqq, "will busy wait");
f75edf2d
VG		 3532 }
3533
a36e71f9 3534 /*
8e550632
CZ		 3535 * Idling is not enabled on:
3536 * - expired queues
3537 * - idle-priority queues
3538 * - async queues
3539 * - queues with still some requests queued
3540 * - when there is a close cooperator
a36e71f9 3541 */
0871714e 3542 if (cfq_slice_used(cfqq) || cfq_class_idle(cfqq))
e5ff082e 3543 cfq_slice_expired(cfqd, 1);
8e550632
CZ		 3544 else if (sync && cfqq_empty &&
3545 !cfq_close_cooperator(cfqd, cfqq)) {
749ef9f8 3546 cfq_arm_slice_timer(cfqd);
8e550632 3547 }
caaa5f9f 3548 }
6d048f53 3549
53c583d2 3550 if (!cfqd->rq_in_driver)
23e018a1 3551 cfq_schedule_dispatch(cfqd);
1da177e4
LT		 3552}
3553
89850f7e 3554static inline int __cfq_may_queue(struct cfq_queue *cfqq)
22e2c507 3555{
1b379d8d 3556 if (cfq_cfqq_wait_request(cfqq) && !cfq_cfqq_must_alloc_slice(cfqq)) {
3b18152c 3557 cfq_mark_cfqq_must_alloc_slice(cfqq);
22e2c507 3558 return ELV_MQUEUE_MUST;
3b18152c 3559 }
1da177e4 3560
22e2c507 3561 return ELV_MQUEUE_MAY;
22e2c507
JA		 3562}
3563
165125e1 3564static int cfq_may_queue(struct request_queue *q, int rw)
22e2c507
JA		 3565{
3566 struct cfq_data *cfqd = q->elevator->elevator_data;
3567 struct task_struct *tsk = current;
c5869807 3568 struct cfq_io_cq *cic;
22e2c507
JA		 3569 struct cfq_queue *cfqq;
3570
3571 /*
3572 * don't force setup of a queue from here, as a call to may_queue
3573 * does not necessarily imply that a request actually will be queued.
3574 * so just lookup a possibly existing queue, or return 'may queue'
3575 * if that fails
3576 */
4ac845a2 3577 cic = cfq_cic_lookup(cfqd, tsk->io_context);
91fac317
VT		 3578 if (!cic)
3579 return ELV_MQUEUE_MAY;
3580
b0b78f81 3581 cfqq = cic_to_cfqq(cic, rw_is_sync(rw));
22e2c507 3582 if (cfqq) {
abede6da 3583 cfq_init_prio_data(cfqq, cic);
22e2c507 3584
89850f7e 3585 return __cfq_may_queue(cfqq);
22e2c507
JA		 3586 }
3587
3588 return ELV_MQUEUE_MAY;
1da177e4
LT		 3589}
3590
1da177e4
LT		 3591/*
3592 * queue lock held here
3593 */
bb37b94c 3594static void cfq_put_request(struct request *rq)
1da177e4 3595{
5e705374 3596 struct cfq_queue *cfqq = RQ_CFQQ(rq);
1da177e4 3597
5e705374 3598 if (cfqq) {
22e2c507 3599 const int rw = rq_data_dir(rq);
1da177e4 3600
22e2c507
JA		 3601 BUG_ON(!cfqq->allocated[rw]);
3602 cfqq->allocated[rw]--;
1da177e4 3603
7f1dc8a2 3604 /* Put down rq reference on cfqg */
eb7d8c07 3605 cfqg_put(RQ_CFQG(rq));
a612fddf
TH		 3606 rq->elv.priv[0] = NULL;
3607 rq->elv.priv[1] = NULL;
7f1dc8a2 3608
1da177e4
LT		 3609 cfq_put_queue(cfqq);
3610 }
3611}
3612
df5fe3e8 3613static struct cfq_queue *
c5869807 3614cfq_merge_cfqqs(struct cfq_data *cfqd, struct cfq_io_cq *cic,
df5fe3e8
JM		 3615 struct cfq_queue *cfqq)
3616{
3617 cfq_log_cfqq(cfqd, cfqq, "merging with queue %p", cfqq->new_cfqq);
3618 cic_set_cfqq(cic, cfqq->new_cfqq, 1);
b3b6d040 3619 cfq_mark_cfqq_coop(cfqq->new_cfqq);
df5fe3e8
JM		 3620 cfq_put_queue(cfqq);
3621 return cic_to_cfqq(cic, 1);
3622}
3623
e6c5bc73
JM		 3624/*
3625 * Returns NULL if a new cfqq should be allocated, or the old cfqq if this
3626 * was the last process referring to said cfqq.
3627 */
3628static struct cfq_queue *
c5869807 3629split_cfqq(struct cfq_io_cq *cic, struct cfq_queue *cfqq)
e6c5bc73
JM		 3630{
3631 if (cfqq_process_refs(cfqq) == 1) {
e6c5bc73
JM		 3632 cfqq->pid = current->pid;
3633 cfq_clear_cfqq_coop(cfqq);
ae54abed 3634 cfq_clear_cfqq_split_coop(cfqq);
e6c5bc73
JM		 3635 return cfqq;
3636 }
3637
3638 cic_set_cfqq(cic, NULL, 1);
d02a2c07
SL		 3639
3640 cfq_put_cooperator(cfqq);
3641
e6c5bc73
JM		 3642 cfq_put_queue(cfqq);
3643 return NULL;
3644}
1da177e4 3645/*
22e2c507 3646 * Allocate cfq data structures associated with this request.
1da177e4 3647 */
22e2c507 3648static int
852c788f
TH		 3649cfq_set_request(struct request_queue *q, struct request *rq, struct bio *bio,
3650 gfp_t gfp_mask)
1da177e4
LT		 3651{
3652 struct cfq_data *cfqd = q->elevator->elevator_data;
f1f8cc94 3653 struct cfq_io_cq *cic = icq_to_cic(rq->elv.icq);
1da177e4 3654 const int rw = rq_data_dir(rq);
a6151c3a 3655 const bool is_sync = rq_is_sync(rq);
22e2c507 3656 struct cfq_queue *cfqq;
1da177e4
LT		 3657
3658 might_sleep_if(gfp_mask & __GFP_WAIT);
3659
216284c3 3660 spin_lock_irq(q->queue_lock);
f1f8cc94 3661
598971bf
TH		 3662 check_ioprio_changed(cic, bio);
3663 check_blkcg_changed(cic, bio);
e6c5bc73 3664new_queue:
91fac317 3665 cfqq = cic_to_cfqq(cic, is_sync);
32f2e807 3666 if (!cfqq || cfqq == &cfqd->oom_cfqq) {
abede6da 3667 cfqq = cfq_get_queue(cfqd, is_sync, cic, bio, gfp_mask);
91fac317 3668 cic_set_cfqq(cic, cfqq, is_sync);
df5fe3e8 3669 } else {
e6c5bc73
JM		 3670 /*
3671 * If the queue was seeky for too long, break it apart.
3672 */
ae54abed 3673 if (cfq_cfqq_coop(cfqq) && cfq_cfqq_split_coop(cfqq)) {
e6c5bc73
JM		 3674 cfq_log_cfqq(cfqd, cfqq, "breaking apart cfqq");
3675 cfqq = split_cfqq(cic, cfqq);
3676 if (!cfqq)
3677 goto new_queue;
3678 }
3679
df5fe3e8
JM		 3680 /*
3681 * Check to see if this queue is scheduled to merge with
3682 * another, closely cooperating queue. The merging of
3683 * queues happens here as it must be done in process context.
3684 * The reference on new_cfqq was taken in merge_cfqqs.
3685 */
3686 if (cfqq->new_cfqq)
3687 cfqq = cfq_merge_cfqqs(cfqd, cic, cfqq);
91fac317 3688 }
1da177e4
LT		 3689
3690 cfqq->allocated[rw]++;
1da177e4 3691
6fae9c25 3692 cfqq->ref++;
eb7d8c07 3693 cfqg_get(cfqq->cfqg);
a612fddf 3694 rq->elv.priv[0] = cfqq;
1adaf3dd 3695 rq->elv.priv[1] = cfqq->cfqg;
216284c3 3696 spin_unlock_irq(q->queue_lock);
5e705374 3697 return 0;
1da177e4
LT		 3698}
3699
65f27f38 3700static void cfq_kick_queue(struct work_struct *work)
22e2c507 3701{
65f27f38 3702 struct cfq_data *cfqd =
23e018a1 3703 container_of(work, struct cfq_data, unplug_work);
165125e1 3704 struct request_queue *q = cfqd->queue;
22e2c507 3705
40bb54d1 3706 spin_lock_irq(q->queue_lock);
24ecfbe2 3707 __blk_run_queue(cfqd->queue);
40bb54d1 3708 spin_unlock_irq(q->queue_lock);
22e2c507
JA		 3709}
3710
3711/*
3712 * Timer running if the active_queue is currently idling inside its time slice
3713 */
3714static void cfq_idle_slice_timer(unsigned long data)
3715{
3716 struct cfq_data *cfqd = (struct cfq_data *) data;
3717 struct cfq_queue *cfqq;
3718 unsigned long flags;
3c6bd2f8 3719 int timed_out = 1;
22e2c507 3720
7b679138
JA		 3721 cfq_log(cfqd, "idle timer fired");
3722
22e2c507
JA		 3723 spin_lock_irqsave(cfqd->queue->queue_lock, flags);
3724
fe094d98
JA		 3725 cfqq = cfqd->active_queue;
3726 if (cfqq) {
3c6bd2f8
JA		 3727 timed_out = 0;
3728
b029195d
JA		 3729 /*
3730 * We saw a request before the queue expired, let it through
3731 */
3732 if (cfq_cfqq_must_dispatch(cfqq))
3733 goto out_kick;
3734
22e2c507
JA		 3735 /*
3736 * expired
3737 */
44f7c160 3738 if (cfq_slice_used(cfqq))
22e2c507
JA		 3739 goto expire;
3740
3741 /*
3742 * only expire and reinvoke request handler, if there are
3743 * other queues with pending requests
3744 */
caaa5f9f 3745 if (!cfqd->busy_queues)
22e2c507 3746 goto out_cont;
22e2c507
JA		 3747
3748 /*
3749 * not expired and it has a request pending, let it dispatch
3750 */
75e50984 3751 if (!RB_EMPTY_ROOT(&cfqq->sort_list))
22e2c507 3752 goto out_kick;
76280aff
CZ		 3753
3754 /*
3755 * Queue depth flag is reset only when the idle didn't succeed
3756 */
3757 cfq_clear_cfqq_deep(cfqq);
22e2c507
JA		 3758 }
3759expire:
e5ff082e 3760 cfq_slice_expired(cfqd, timed_out);
22e2c507 3761out_kick:
23e018a1 3762 cfq_schedule_dispatch(cfqd);
22e2c507
JA		 3763out_cont:
3764 spin_unlock_irqrestore(cfqd->queue->queue_lock, flags);
3765}
3766
3b18152c
JA		 3767static void cfq_shutdown_timer_wq(struct cfq_data *cfqd)
3768{
3769 del_timer_sync(&cfqd->idle_slice_timer);
23e018a1 3770 cancel_work_sync(&cfqd->unplug_work);
3b18152c 3771}
22e2c507 3772
c2dea2d1
VT		 3773static void cfq_put_async_queues(struct cfq_data *cfqd)
3774{
3775 int i;
3776
3777 for (i = 0; i < IOPRIO_BE_NR; i++) {
3778 if (cfqd->async_cfqq[0][i])
3779 cfq_put_queue(cfqd->async_cfqq[0][i]);
3780 if (cfqd->async_cfqq[1][i])
3781 cfq_put_queue(cfqd->async_cfqq[1][i]);
c2dea2d1 3782 }
2389d1ef
ON		 3783
3784 if (cfqd->async_idle_cfqq)
3785 cfq_put_queue(cfqd->async_idle_cfqq);
c2dea2d1
VT		 3786}
3787
b374d18a 3788static void cfq_exit_queue(struct elevator_queue *e)
1da177e4 3789{
22e2c507 3790 struct cfq_data *cfqd = e->elevator_data;
165125e1 3791 struct request_queue *q = cfqd->queue;
22e2c507 3792
3b18152c 3793 cfq_shutdown_timer_wq(cfqd);
e2d74ac0 3794
d9ff4187 3795 spin_lock_irq(q->queue_lock);
e2d74ac0 3796
d9ff4187 3797 if (cfqd->active_queue)
e5ff082e 3798 __cfq_slice_expired(cfqd, cfqd->active_queue, 0);
e2d74ac0 3799
c2dea2d1 3800 cfq_put_async_queues(cfqd);
03aa264a
TH		 3801
3802 spin_unlock_irq(q->queue_lock);
3803
a90d742e
AV		 3804 cfq_shutdown_timer_wq(cfqd);
3805
f51b802c
TH		 3806#ifndef CONFIG_CFQ_GROUP_IOSCHED
3807 kfree(cfqd->root_group);
2abae55f 3808#endif
e8989fae 3809 update_root_blkg_pd(q, BLKIO_POLICY_PROP);
56edf7d7 3810 kfree(cfqd);
1da177e4
LT		 3811}
3812
b2fab5ac 3813static int cfq_init_queue(struct request_queue *q)
1da177e4
LT		 3814{
3815 struct cfq_data *cfqd;
cd1604fa 3816 struct blkio_group *blkg __maybe_unused;
f51b802c 3817 int i;
1da177e4 3818
94f6030c 3819 cfqd = kmalloc_node(sizeof(*cfqd), GFP_KERNEL | __GFP_ZERO, q->node);
a73f730d 3820 if (!cfqd)
b2fab5ac 3821 return -ENOMEM;
80b15c73 3822
f51b802c
TH		 3823 cfqd->queue = q;
3824 q->elevator->elevator_data = cfqd;
3825
1fa8f6d6
VG		 3826 /* Init root service tree */
3827 cfqd->grp_service_tree = CFQ_RB_ROOT;
3828
f51b802c 3829 /* Init root group and prefer root group over other groups by default */
25fb5169 3830#ifdef CONFIG_CFQ_GROUP_IOSCHED
f51b802c
TH		 3831 rcu_read_lock();
3832 spin_lock_irq(q->queue_lock);
5624a4e4 3833
aaec55a0 3834 blkg = blkg_lookup_create(&blkio_root_cgroup, q, true);
cd1604fa 3835 if (!IS_ERR(blkg))
0381411e 3836 cfqd->root_group = blkg_to_cfqg(blkg);
f51b802c
TH		 3837
3838 spin_unlock_irq(q->queue_lock);
3839 rcu_read_unlock();
3840#else
3841 cfqd->root_group = kzalloc_node(sizeof(*cfqd->root_group),
3842 GFP_KERNEL, cfqd->queue->node);
3843 if (cfqd->root_group)
3844 cfq_init_cfqg_base(cfqd->root_group);
3845#endif
3846 if (!cfqd->root_group) {
5624a4e4 3847 kfree(cfqd);
b2fab5ac 3848 return -ENOMEM;
5624a4e4
VG		 3849 }
3850
f51b802c 3851 cfqd->root_group->weight = 2*BLKIO_WEIGHT_DEFAULT;
5624a4e4 3852
26a2ac00
JA		 3853 /*
3854 * Not strictly needed (since RB_ROOT just clears the node and we
3855 * zeroed cfqd on alloc), but better be safe in case someone decides
3856 * to add magic to the rb code
3857 */
3858 for (i = 0; i < CFQ_PRIO_LISTS; i++)
3859 cfqd->prio_trees[i] = RB_ROOT;
3860
6118b70b
JA		 3861 /*
3862 * Our fallback cfqq if cfq_find_alloc_queue() runs into OOM issues.
3863 * Grab a permanent reference to it, so that the normal code flow
f51b802c
TH		 3864 * will not attempt to free it. oom_cfqq is linked to root_group
3865 * but shouldn't hold a reference as it'll never be unlinked. Lose
3866 * the reference from linking right away.
6118b70b
JA		 3867 */
3868 cfq_init_cfqq(cfqd, &cfqd->oom_cfqq, 1, 0);
30d7b944 3869 cfqd->oom_cfqq.ref++;
1adaf3dd
TH		 3870
3871 spin_lock_irq(q->queue_lock);
f51b802c 3872 cfq_link_cfqq_cfqg(&cfqd->oom_cfqq, cfqd->root_group);
eb7d8c07 3873 cfqg_put(cfqd->root_group);
1adaf3dd 3874 spin_unlock_irq(q->queue_lock);
1da177e4 3875
22e2c507
JA		 3876 init_timer(&cfqd->idle_slice_timer);
3877 cfqd->idle_slice_timer.function = cfq_idle_slice_timer;
3878 cfqd->idle_slice_timer.data = (unsigned long) cfqd;
3879
23e018a1 3880 INIT_WORK(&cfqd->unplug_work, cfq_kick_queue);
22e2c507 3881
1da177e4 3882 cfqd->cfq_quantum = cfq_quantum;
22e2c507
JA		 3883 cfqd->cfq_fifo_expire[0] = cfq_fifo_expire[0];
3884 cfqd->cfq_fifo_expire[1] = cfq_fifo_expire[1];
1da177e4
LT		 3885 cfqd->cfq_back_max = cfq_back_max;
3886 cfqd->cfq_back_penalty = cfq_back_penalty;
22e2c507
JA		 3887 cfqd->cfq_slice[0] = cfq_slice_async;
3888 cfqd->cfq_slice[1] = cfq_slice_sync;
3889 cfqd->cfq_slice_async_rq = cfq_slice_async_rq;
3890 cfqd->cfq_slice_idle = cfq_slice_idle;
80bdf0c7 3891 cfqd->cfq_group_idle = cfq_group_idle;
963b72fc 3892 cfqd->cfq_latency = 1;
e459dd08 3893 cfqd->hw_tag = -1;
edc71131
CZ		 3894 /*
3895 * we optimistically start assuming sync ops weren't delayed in last
3896 * second, in order to have larger depth for async operations.
3897 */
573412b2 3898 cfqd->last_delayed_sync = jiffies - HZ;
b2fab5ac 3899 return 0;
1da177e4
LT		 3900}
3901
1da177e4
LT		 3902/*
3903 * sysfs parts below -->
3904 */
1da177e4
LT		 3905static ssize_t
3906cfq_var_show(unsigned int var, char *page)
3907{
3908 return sprintf(page, "%d\n", var);
3909}
3910
3911static ssize_t
3912cfq_var_store(unsigned int *var, const char *page, size_t count)
3913{
3914 char *p = (char *) page;
3915
3916 *var = simple_strtoul(p, &p, 10);
3917 return count;
3918}
3919
1da177e4 3920#define SHOW_FUNCTION(__FUNC, __VAR, __CONV) \
b374d18a 3921static ssize_t __FUNC(struct elevator_queue *e, char *page) \
1da177e4 3922{ \
3d1ab40f 3923 struct cfq_data *cfqd = e->elevator_data; \
1da177e4
LT		 3924 unsigned int __data = __VAR; \
3925 if (__CONV) \
3926 __data = jiffies_to_msecs(__data); \
3927 return cfq_var_show(__data, (page)); \
3928}
3929SHOW_FUNCTION(cfq_quantum_show, cfqd->cfq_quantum, 0);
22e2c507
JA		 3930SHOW_FUNCTION(cfq_fifo_expire_sync_show, cfqd->cfq_fifo_expire[1], 1);
3931SHOW_FUNCTION(cfq_fifo_expire_async_show, cfqd->cfq_fifo_expire[0], 1);
e572ec7e
AV		 3932SHOW_FUNCTION(cfq_back_seek_max_show, cfqd->cfq_back_max, 0);
3933SHOW_FUNCTION(cfq_back_seek_penalty_show, cfqd->cfq_back_penalty, 0);
22e2c507 3934SHOW_FUNCTION(cfq_slice_idle_show, cfqd->cfq_slice_idle, 1);
80bdf0c7 3935SHOW_FUNCTION(cfq_group_idle_show, cfqd->cfq_group_idle, 1);
22e2c507
JA		 3936SHOW_FUNCTION(cfq_slice_sync_show, cfqd->cfq_slice[1], 1);
3937SHOW_FUNCTION(cfq_slice_async_show, cfqd->cfq_slice[0], 1);
3938SHOW_FUNCTION(cfq_slice_async_rq_show, cfqd->cfq_slice_async_rq, 0);
963b72fc 3939SHOW_FUNCTION(cfq_low_latency_show, cfqd->cfq_latency, 0);
1da177e4
LT		 3940#undef SHOW_FUNCTION
3941
3942#define STORE_FUNCTION(__FUNC, __PTR, MIN, MAX, __CONV) \
b374d18a 3943static ssize_t __FUNC(struct elevator_queue *e, const char *page, size_t count) \
1da177e4 3944{ \
3d1ab40f 3945 struct cfq_data *cfqd = e->elevator_data; \
1da177e4
LT		 3946 unsigned int __data; \
3947 int ret = cfq_var_store(&__data, (page), count); \
3948 if (__data < (MIN)) \
3949 __data = (MIN); \
3950 else if (__data > (MAX)) \
3951 __data = (MAX); \
3952 if (__CONV) \
3953 *(__PTR) = msecs_to_jiffies(__data); \
3954 else \
3955 *(__PTR) = __data; \
3956 return ret; \
3957}
3958STORE_FUNCTION(cfq_quantum_store, &cfqd->cfq_quantum, 1, UINT_MAX, 0);
fe094d98
JA		 3959STORE_FUNCTION(cfq_fifo_expire_sync_store, &cfqd->cfq_fifo_expire[1], 1,
3960 UINT_MAX, 1);
3961STORE_FUNCTION(cfq_fifo_expire_async_store, &cfqd->cfq_fifo_expire[0], 1,
3962 UINT_MAX, 1);
e572ec7e 3963STORE_FUNCTION(cfq_back_seek_max_store, &cfqd->cfq_back_max, 0, UINT_MAX, 0);
fe094d98
JA		 3964STORE_FUNCTION(cfq_back_seek_penalty_store, &cfqd->cfq_back_penalty, 1,
3965 UINT_MAX, 0);
22e2c507 3966STORE_FUNCTION(cfq_slice_idle_store, &cfqd->cfq_slice_idle, 0, UINT_MAX, 1);
80bdf0c7 3967STORE_FUNCTION(cfq_group_idle_store, &cfqd->cfq_group_idle, 0, UINT_MAX, 1);
22e2c507
JA		 3968STORE_FUNCTION(cfq_slice_sync_store, &cfqd->cfq_slice[1], 1, UINT_MAX, 1);
3969STORE_FUNCTION(cfq_slice_async_store, &cfqd->cfq_slice[0], 1, UINT_MAX, 1);
fe094d98
JA		 3970STORE_FUNCTION(cfq_slice_async_rq_store, &cfqd->cfq_slice_async_rq, 1,
3971 UINT_MAX, 0);
963b72fc 3972STORE_FUNCTION(cfq_low_latency_store, &cfqd->cfq_latency, 0, 1, 0);
1da177e4
LT		 3973#undef STORE_FUNCTION
3974
e572ec7e
AV		 3975#define CFQ_ATTR(name) \
3976 __ATTR(name, S_IRUGO|S_IWUSR, cfq_##name##_show, cfq_##name##_store)
3977
3978static struct elv_fs_entry cfq_attrs[] = {
3979 CFQ_ATTR(quantum),
e572ec7e
AV		 3980 CFQ_ATTR(fifo_expire_sync),
3981 CFQ_ATTR(fifo_expire_async),
3982 CFQ_ATTR(back_seek_max),
3983 CFQ_ATTR(back_seek_penalty),
3984 CFQ_ATTR(slice_sync),
3985 CFQ_ATTR(slice_async),
3986 CFQ_ATTR(slice_async_rq),
3987 CFQ_ATTR(slice_idle),
80bdf0c7 3988 CFQ_ATTR(group_idle),
963b72fc 3989 CFQ_ATTR(low_latency),
e572ec7e 3990 __ATTR_NULL
1da177e4
LT		 3991};
3992
1da177e4
LT		 3993static struct elevator_type iosched_cfq = {
3994 .ops = {
3995 .elevator_merge_fn = cfq_merge,
3996 .elevator_merged_fn = cfq_merged_request,
3997 .elevator_merge_req_fn = cfq_merged_requests,
da775265 3998 .elevator_allow_merge_fn = cfq_allow_merge,
812d4026 3999 .elevator_bio_merged_fn = cfq_bio_merged,
b4878f24 4000 .elevator_dispatch_fn = cfq_dispatch_requests,
1da177e4 4001 .elevator_add_req_fn = cfq_insert_request,
b4878f24 4002 .elevator_activate_req_fn = cfq_activate_request,
1da177e4 4003 .elevator_deactivate_req_fn = cfq_deactivate_request,
1da177e4 4004 .elevator_completed_req_fn = cfq_completed_request,
21183b07
JA		 4005 .elevator_former_req_fn = elv_rb_former_request,
4006 .elevator_latter_req_fn = elv_rb_latter_request,
9b84cacd 4007 .elevator_init_icq_fn = cfq_init_icq,
7e5a8794 4008 .elevator_exit_icq_fn = cfq_exit_icq,
1da177e4
LT		 4009 .elevator_set_req_fn = cfq_set_request,
4010 .elevator_put_req_fn = cfq_put_request,
4011 .elevator_may_queue_fn = cfq_may_queue,
4012 .elevator_init_fn = cfq_init_queue,
4013 .elevator_exit_fn = cfq_exit_queue,
4014 },
3d3c2379
TH		 4015 .icq_size = sizeof(struct cfq_io_cq),
4016 .icq_align = __alignof__(struct cfq_io_cq),
3d1ab40f 4017 .elevator_attrs = cfq_attrs,
3d3c2379 4018 .elevator_name = "cfq",
1da177e4
LT		 4019 .elevator_owner = THIS_MODULE,
4020};
4021
3e252066
VG		 4022#ifdef CONFIG_CFQ_GROUP_IOSCHED
4023static struct blkio_policy_type blkio_policy_cfq = {
4024 .ops = {
0381411e 4025 .blkio_init_group_fn = cfq_init_blkio_group,
3e252066 4026 },
062a644d 4027 .plid = BLKIO_POLICY_PROP,
0381411e 4028 .pdata_size = sizeof(struct cfq_group),
60c2bc2d 4029 .cftypes = cfq_blkcg_files,
3e252066 4030};
3e252066
VG		 4031#endif
4032
1da177e4
LT		 4033static int __init cfq_init(void)
4034{
3d3c2379
TH		 4035 int ret;
4036
22e2c507
JA		 4037 /*
4038 * could be 0 on HZ < 1000 setups
4039 */
4040 if (!cfq_slice_async)
4041 cfq_slice_async = 1;
4042 if (!cfq_slice_idle)
4043 cfq_slice_idle = 1;
4044
80bdf0c7
VG		 4045#ifdef CONFIG_CFQ_GROUP_IOSCHED
4046 if (!cfq_group_idle)
4047 cfq_group_idle = 1;
4048#else
4049 cfq_group_idle = 0;
4050#endif
3d3c2379
TH		 4051 cfq_pool = KMEM_CACHE(cfq_queue, 0);
4052 if (!cfq_pool)
1da177e4
LT		 4053 return -ENOMEM;
4054
3d3c2379
TH		 4055 ret = elv_register(&iosched_cfq);
4056 if (ret) {
4057 kmem_cache_destroy(cfq_pool);
4058 return ret;
4059 }
3d3c2379 4060
b95ada55 4061#ifdef CONFIG_CFQ_GROUP_IOSCHED
3e252066 4062 blkio_policy_register(&blkio_policy_cfq);
b95ada55 4063#endif
2fdd82bd 4064 return 0;
1da177e4
LT		 4065}
4066
4067static void __exit cfq_exit(void)
4068{
b95ada55 4069#ifdef CONFIG_CFQ_GROUP_IOSCHED
3e252066 4070 blkio_policy_unregister(&blkio_policy_cfq);
b95ada55 4071#endif
1da177e4 4072 elv_unregister(&iosched_cfq);
3d3c2379 4073 kmem_cache_destroy(cfq_pool);
1da177e4
LT		 4074}
4075
4076module_init(cfq_init);
4077module_exit(cfq_exit);
4078
4079MODULE_AUTHOR("Jens Axboe");
4080MODULE_LICENSE("GPL");
4081MODULE_DESCRIPTION("Completely Fair Queueing IO scheduler");
Linux 6.x block layer and io_uring tree(s)