path: root/block/cfq-iosched.c (plain)
blob: 650d69e0f6f7eb987e1f1e5dddb54964f5351c55

1	/*
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	*
7	* Copyright (C) 2003 Jens Axboe <axboe@kernel.dk>
8	*/
9	#include <linux/module.h>
10	#include <linux/slab.h>
11	#include <linux/blkdev.h>
12	#include <linux/elevator.h>
13	#include <linux/ktime.h>
14	#include <linux/rbtree.h>
15	#include <linux/ioprio.h>
16	#include <linux/blktrace_api.h>
17	#include <linux/blk-cgroup.h>
18	#include "blk.h"
19
20	/*
21	* tunables
22	*/
23	/* max queue in one round of service */
24	static const int cfq_quantum = 8;
25	static const u64 cfq_fifo_expire[2] = { NSEC_PER_SEC / 4, NSEC_PER_SEC / 8 };
26	/* maximum backwards seek, in KiB */
27	static const int cfq_back_max = 16 * 1024;
28	/* penalty of a backwards seek */
29	static const int cfq_back_penalty = 2;
30	static const u64 cfq_slice_sync = NSEC_PER_SEC / 10;
31	static u64 cfq_slice_async = NSEC_PER_SEC / 25;
32	static const int cfq_slice_async_rq = 2;
33	static u64 cfq_slice_idle = NSEC_PER_SEC / 125;
34	static u64 cfq_group_idle = NSEC_PER_SEC / 125;
35	static const u64 cfq_target_latency = (u64)NSEC_PER_SEC * 3/10; /* 300 ms */
36	static const int cfq_hist_divisor = 4;
37
38	/*
39	* offset from end of queue service tree for idle class
40	*/
41	#define CFQ_IDLE_DELAY (NSEC_PER_SEC / 5)
42	/* offset from end of group service tree under time slice mode */
43	#define CFQ_SLICE_MODE_GROUP_DELAY (NSEC_PER_SEC / 5)
44	/* offset from end of group service under IOPS mode */
45	#define CFQ_IOPS_MODE_GROUP_DELAY (HZ / 5)
46
47	/*
48	* below this threshold, we consider thinktime immediate
49	*/
50	#define CFQ_MIN_TT (2 * NSEC_PER_SEC / HZ)
51
52	#define CFQ_SLICE_SCALE (5)
53	#define CFQ_HW_QUEUE_MIN (5)
54	#define CFQ_SERVICE_SHIFT 12
55
56	#define CFQQ_SEEK_THR (sector_t)(8 * 100)
57	#define CFQQ_CLOSE_THR (sector_t)(8 * 1024)
58	#define CFQQ_SECT_THR_NONROT (sector_t)(2 * 32)
59	#define CFQQ_SEEKY(cfqq) (hweight32(cfqq->seek_history) > 32/8)
60
61	#define RQ_CIC(rq) icq_to_cic((rq)->elv.icq)
62	#define RQ_CFQQ(rq) (struct cfq_queue *) ((rq)->elv.priv[0])
63	#define RQ_CFQG(rq) (struct cfq_group *) ((rq)->elv.priv[1])
64
65	static struct kmem_cache *cfq_pool;
66
67	#define CFQ_PRIO_LISTS IOPRIO_BE_NR
68	#define cfq_class_idle(cfqq) ((cfqq)->ioprio_class == IOPRIO_CLASS_IDLE)
69	#define cfq_class_rt(cfqq) ((cfqq)->ioprio_class == IOPRIO_CLASS_RT)
70
71	#define sample_valid(samples) ((samples) > 80)
72	#define rb_entry_cfqg(node) rb_entry((node), struct cfq_group, rb_node)
73
74	/* blkio-related constants */
75	#define CFQ_WEIGHT_LEGACY_MIN 10
76	#define CFQ_WEIGHT_LEGACY_DFL 500
77	#define CFQ_WEIGHT_LEGACY_MAX 1000
78
79	struct cfq_ttime {
80	u64 last_end_request;
81
82	u64 ttime_total;
83	u64 ttime_mean;
84	unsigned long ttime_samples;
85	};
86
87	/*
88	* Most of our rbtree usage is for sorting with min extraction, so
89	* if we cache the leftmost node we don't have to walk down the tree
90	* to find it. Idea borrowed from Ingo Molnars CFS scheduler. We should
91	* move this into the elevator for the rq sorting as well.
92	*/
93	struct cfq_rb_root {
94	struct rb_root rb;
95	struct rb_node *left;
96	unsigned count;
97	u64 min_vdisktime;
98	struct cfq_ttime ttime;
99	};
100	#define CFQ_RB_ROOT (struct cfq_rb_root) { .rb = RB_ROOT, \
101	.ttime = {.last_end_request = ktime_get_ns(),},}
102
103	/*
104	* Per process-grouping structure
105	*/
106	struct cfq_queue {
107	/* reference count */
108	int ref;
109	/* various state flags, see below */
110	unsigned int flags;
111	/* parent cfq_data */
112	struct cfq_data *cfqd;
113	/* service_tree member */
114	struct rb_node rb_node;
115	/* service_tree key */
116	u64 rb_key;
117	/* prio tree member */
118	struct rb_node p_node;
119	/* prio tree root we belong to, if any */
120	struct rb_root *p_root;
121	/* sorted list of pending requests */
122	struct rb_root sort_list;
123	/* if fifo isn't expired, next request to serve */
124	struct request *next_rq;
125	/* requests queued in sort_list */
126	int queued[2];
127	/* currently allocated requests */
128	int allocated[2];
129	/* fifo list of requests in sort_list */
130	struct list_head fifo;
131
132	/* time when queue got scheduled in to dispatch first request. */
133	u64 dispatch_start;
134	u64 allocated_slice;
135	u64 slice_dispatch;
136	/* time when first request from queue completed and slice started. */
137	u64 slice_start;
138	u64 slice_end;
139	s64 slice_resid;
140
141	/* pending priority requests */
142	int prio_pending;
143	/* number of requests that are on the dispatch list or inside driver */
144	int dispatched;
145
146	/* io prio of this group */
147	unsigned short ioprio, org_ioprio;
148	unsigned short ioprio_class, org_ioprio_class;
149
150	pid_t pid;
151
152	u32 seek_history;
153	sector_t last_request_pos;
154
155	struct cfq_rb_root *service_tree;
156	struct cfq_queue *new_cfqq;
157	struct cfq_group *cfqg;
158	/* Number of sectors dispatched from queue in single dispatch round */
159	unsigned long nr_sectors;
160	};
161
162	/*
163	* First index in the service_trees.
164	* IDLE is handled separately, so it has negative index
165	*/
166	enum wl_class_t {
167	BE_WORKLOAD = 0,
168	RT_WORKLOAD = 1,
169	IDLE_WORKLOAD = 2,
170	CFQ_PRIO_NR,
171	};
172
173	/*
174	* Second index in the service_trees.
175	*/
176	enum wl_type_t {
177	ASYNC_WORKLOAD = 0,
178	SYNC_NOIDLE_WORKLOAD = 1,
179	SYNC_WORKLOAD = 2
180	};
181
182	struct cfqg_stats {
183	#ifdef CONFIG_CFQ_GROUP_IOSCHED
184	/* number of ios merged */
185	struct blkg_rwstat merged;
186	/* total time spent on device in ns, may not be accurate w/ queueing */
187	struct blkg_rwstat service_time;
188	/* total time spent waiting in scheduler queue in ns */
189	struct blkg_rwstat wait_time;
190	/* number of IOs queued up */
191	struct blkg_rwstat queued;
192	/* total disk time and nr sectors dispatched by this group */
193	struct blkg_stat time;
194	#ifdef CONFIG_DEBUG_BLK_CGROUP
195	/* time not charged to this cgroup */
196	struct blkg_stat unaccounted_time;
197	/* sum of number of ios queued across all samples */
198	struct blkg_stat avg_queue_size_sum;
199	/* count of samples taken for average */
200	struct blkg_stat avg_queue_size_samples;
201	/* how many times this group has been removed from service tree */
202	struct blkg_stat dequeue;
203	/* total time spent waiting for it to be assigned a timeslice. */
204	struct blkg_stat group_wait_time;
205	/* time spent idling for this blkcg_gq */
206	struct blkg_stat idle_time;
207	/* total time with empty current active q with other requests queued */
208	struct blkg_stat empty_time;
209	/* fields after this shouldn't be cleared on stat reset */
210	uint64_t start_group_wait_time;
211	uint64_t start_idle_time;
212	uint64_t start_empty_time;
213	uint16_t flags;
214	#endif /* CONFIG_DEBUG_BLK_CGROUP */
215	#endif /* CONFIG_CFQ_GROUP_IOSCHED */
216	};
217
218	/* Per-cgroup data */
219	struct cfq_group_data {
220	/* must be the first member */
221	struct blkcg_policy_data cpd;
222
223	unsigned int weight;
224	unsigned int leaf_weight;
225	u64 group_idle;
226	};
227
228	/* This is per cgroup per device grouping structure */
229	struct cfq_group {
230	/* must be the first member */
231	struct blkg_policy_data pd;
232
233	/* group service_tree member */
234	struct rb_node rb_node;
235
236	/* group service_tree key */
237	u64 vdisktime;
238
239	/*
240	* The number of active cfqgs and sum of their weights under this
241	* cfqg. This covers this cfqg's leaf_weight and all children's
242	* weights, but does not cover weights of further descendants.
243	*
244	* If a cfqg is on the service tree, it's active. An active cfqg
245	* also activates its parent and contributes to the children_weight
246	* of the parent.
247	*/
248	int nr_active;
249	unsigned int children_weight;
250
251	/*
252	* vfraction is the fraction of vdisktime that the tasks in this
253	* cfqg are entitled to. This is determined by compounding the
254	* ratios walking up from this cfqg to the root.
255	*
256	* It is in fixed point w/ CFQ_SERVICE_SHIFT and the sum of all
257	* vfractions on a service tree is approximately 1. The sum may
258	* deviate a bit due to rounding errors and fluctuations caused by
259	* cfqgs entering and leaving the service tree.
260	*/
261	unsigned int vfraction;
262
263	/*
264	* There are two weights - (internal) weight is the weight of this
265	* cfqg against the sibling cfqgs. leaf_weight is the wight of
266	* this cfqg against the child cfqgs. For the root cfqg, both
267	* weights are kept in sync for backward compatibility.
268	*/
269	unsigned int weight;
270	unsigned int new_weight;
271	unsigned int dev_weight;
272
273	unsigned int leaf_weight;
274	unsigned int new_leaf_weight;
275	unsigned int dev_leaf_weight;
276
277	/* number of cfqq currently on this group */
278	int nr_cfqq;
279
280	/*
281	* Per group busy queues average. Useful for workload slice calc. We
282	* create the array for each prio class but at run time it is used
283	* only for RT and BE class and slot for IDLE class remains unused.
284	* This is primarily done to avoid confusion and a gcc warning.
285	*/
286	unsigned int busy_queues_avg[CFQ_PRIO_NR];
287	/*
288	* rr lists of queues with requests. We maintain service trees for
289	* RT and BE classes. These trees are subdivided in subclasses
290	* of SYNC, SYNC_NOIDLE and ASYNC based on workload type. For IDLE
291	* class there is no subclassification and all the cfq queues go on
292	* a single tree service_tree_idle.
293	* Counts are embedded in the cfq_rb_root
294	*/
295	struct cfq_rb_root service_trees[2][3];
296	struct cfq_rb_root service_tree_idle;
297
298	u64 saved_wl_slice;
299	enum wl_type_t saved_wl_type;
300	enum wl_class_t saved_wl_class;
301
302	/* number of requests that are on the dispatch list or inside driver */
303	int dispatched;
304	struct cfq_ttime ttime;
305	struct cfqg_stats stats; /* stats for this cfqg */
306
307	/* async queue for each priority case */
308	struct cfq_queue *async_cfqq[2][IOPRIO_BE_NR];
309	struct cfq_queue *async_idle_cfqq;
310
311	u64 group_idle;
312	};
313
314	struct cfq_io_cq {
315	struct io_cq icq; /* must be the first member */
316	struct cfq_queue *cfqq[2];
317	struct cfq_ttime ttime;
318	int ioprio; /* the current ioprio */
319	#ifdef CONFIG_CFQ_GROUP_IOSCHED
320	uint64_t blkcg_serial_nr; /* the current blkcg serial */
321	#endif
322	};
323
324	/*
325	* Per block device queue structure
326	*/
327	struct cfq_data {
328	struct request_queue *queue;
329	/* Root service tree for cfq_groups */
330	struct cfq_rb_root grp_service_tree;
331	struct cfq_group *root_group;
332
333	/*
334	* The priority currently being served
335	*/
336	enum wl_class_t serving_wl_class;
337	enum wl_type_t serving_wl_type;
338	u64 workload_expires;
339	struct cfq_group *serving_group;
340
341	/*
342	* Each priority tree is sorted by next_request position. These
343	* trees are used when determining if two or more queues are
344	* interleaving requests (see cfq_close_cooperator).
345	*/
346	struct rb_root prio_trees[CFQ_PRIO_LISTS];
347
348	unsigned int busy_queues;
349	unsigned int busy_sync_queues;
350
351	int rq_in_driver;
352	int rq_in_flight[2];
353
354	/*
355	* queue-depth detection
356	*/
357	int rq_queued;
358	int hw_tag;
359	/*
360	* hw_tag can be
361	* -1 => indeterminate, (cfq will behave as if NCQ is present, to allow better detection)
362	* 1 => NCQ is present (hw_tag_est_depth is the estimated max depth)
363	* 0 => no NCQ
364	*/
365	int hw_tag_est_depth;
366	unsigned int hw_tag_samples;
367
368	/*
369	* idle window management
370	*/
371	struct hrtimer idle_slice_timer;
372	struct work_struct unplug_work;
373
374	struct cfq_queue *active_queue;
375	struct cfq_io_cq *active_cic;
376
377	sector_t last_position;
378
379	/*
380	* tunables, see top of file
381	*/
382	unsigned int cfq_quantum;
383	unsigned int cfq_back_penalty;
384	unsigned int cfq_back_max;
385	unsigned int cfq_slice_async_rq;
386	unsigned int cfq_latency;
387	u64 cfq_fifo_expire[2];
388	u64 cfq_slice[2];
389	u64 cfq_slice_idle;
390	u64 cfq_group_idle;
391	u64 cfq_target_latency;
392
393	/*
394	* Fallback dummy cfqq for extreme OOM conditions
395	*/
396	struct cfq_queue oom_cfqq;
397
398	u64 last_delayed_sync;
399	};
400
401	static struct cfq_group *cfq_get_next_cfqg(struct cfq_data *cfqd);
402	static void cfq_put_queue(struct cfq_queue *cfqq);
403
404	static struct cfq_rb_root *st_for(struct cfq_group *cfqg,
405	enum wl_class_t class,
406	enum wl_type_t type)
407	{
408	if (!cfqg)
409	return NULL;
410
411	if (class == IDLE_WORKLOAD)
412	return &cfqg->service_tree_idle;
413
414	return &cfqg->service_trees[class][type];
415	}
416
417	enum cfqq_state_flags {
418	CFQ_CFQQ_FLAG_on_rr = 0, /* on round-robin busy list */
419	CFQ_CFQQ_FLAG_wait_request, /* waiting for a request */
420	CFQ_CFQQ_FLAG_must_dispatch, /* must be allowed a dispatch */
421	CFQ_CFQQ_FLAG_must_alloc_slice, /* per-slice must_alloc flag */
422	CFQ_CFQQ_FLAG_fifo_expire, /* FIFO checked in this slice */
423	CFQ_CFQQ_FLAG_idle_window, /* slice idling enabled */
424	CFQ_CFQQ_FLAG_prio_changed, /* task priority has changed */
425	CFQ_CFQQ_FLAG_slice_new, /* no requests dispatched in slice */
426	CFQ_CFQQ_FLAG_sync, /* synchronous queue */
427	CFQ_CFQQ_FLAG_coop, /* cfqq is shared */
428	CFQ_CFQQ_FLAG_split_coop, /* shared cfqq will be splitted */
429	CFQ_CFQQ_FLAG_deep, /* sync cfqq experienced large depth */
430	CFQ_CFQQ_FLAG_wait_busy, /* Waiting for next request */
431	};
432
433	#define CFQ_CFQQ_FNS(name) \
434	static inline void cfq_mark_cfqq_##name(struct cfq_queue *cfqq) \
435	{ \
436	(cfqq)->flags |= (1 << CFQ_CFQQ_FLAG_##name); \
437	} \
438	static inline void cfq_clear_cfqq_##name(struct cfq_queue *cfqq) \
439	{ \
440	(cfqq)->flags &= ~(1 << CFQ_CFQQ_FLAG_##name); \
441	} \
442	static inline int cfq_cfqq_##name(const struct cfq_queue *cfqq) \
443	{ \
444	return ((cfqq)->flags & (1 << CFQ_CFQQ_FLAG_##name)) != 0; \
445	}
446
447	CFQ_CFQQ_FNS(on_rr);
448	CFQ_CFQQ_FNS(wait_request);
449	CFQ_CFQQ_FNS(must_dispatch);
450	CFQ_CFQQ_FNS(must_alloc_slice);
451	CFQ_CFQQ_FNS(fifo_expire);
452	CFQ_CFQQ_FNS(idle_window);
453	CFQ_CFQQ_FNS(prio_changed);
454	CFQ_CFQQ_FNS(slice_new);
455	CFQ_CFQQ_FNS(sync);
456	CFQ_CFQQ_FNS(coop);
457	CFQ_CFQQ_FNS(split_coop);
458	CFQ_CFQQ_FNS(deep);
459	CFQ_CFQQ_FNS(wait_busy);
460	#undef CFQ_CFQQ_FNS
461
462	#if defined(CONFIG_CFQ_GROUP_IOSCHED) && defined(CONFIG_DEBUG_BLK_CGROUP)
463
464	/* cfqg stats flags */
465	enum cfqg_stats_flags {
466	CFQG_stats_waiting = 0,
467	CFQG_stats_idling,
468	CFQG_stats_empty,
469	};
470
471	#define CFQG_FLAG_FNS(name) \
472	static inline void cfqg_stats_mark_##name(struct cfqg_stats *stats) \
473	{ \
474	stats->flags |= (1 << CFQG_stats_##name); \
475	} \
476	static inline void cfqg_stats_clear_##name(struct cfqg_stats *stats) \
477	{ \
478	stats->flags &= ~(1 << CFQG_stats_##name); \
479	} \
480	static inline int cfqg_stats_##name(struct cfqg_stats *stats) \
481	{ \
482	return (stats->flags & (1 << CFQG_stats_##name)) != 0; \
483	} \
484
485	CFQG_FLAG_FNS(waiting)
486	CFQG_FLAG_FNS(idling)
487	CFQG_FLAG_FNS(empty)
488	#undef CFQG_FLAG_FNS
489
490	/* This should be called with the queue_lock held. */
491	static void cfqg_stats_update_group_wait_time(struct cfqg_stats *stats)
492	{
493	unsigned long long now;
494
495	if (!cfqg_stats_waiting(stats))
496	return;
497
498	now = sched_clock();
499	if (time_after64(now, stats->start_group_wait_time))
500	blkg_stat_add(&stats->group_wait_time,
501	now - stats->start_group_wait_time);
502	cfqg_stats_clear_waiting(stats);
503	}
504
505	/* This should be called with the queue_lock held. */
506	static void cfqg_stats_set_start_group_wait_time(struct cfq_group *cfqg,
507	struct cfq_group *curr_cfqg)
508	{
509	struct cfqg_stats *stats = &cfqg->stats;
510
511	if (cfqg_stats_waiting(stats))
512	return;
513	if (cfqg == curr_cfqg)
514	return;
515	stats->start_group_wait_time = sched_clock();
516	cfqg_stats_mark_waiting(stats);
517	}
518
519	/* This should be called with the queue_lock held. */
520	static void cfqg_stats_end_empty_time(struct cfqg_stats *stats)
521	{
522	unsigned long long now;
523
524	if (!cfqg_stats_empty(stats))
525	return;
526
527	now = sched_clock();
528	if (time_after64(now, stats->start_empty_time))
529	blkg_stat_add(&stats->empty_time,
530	now - stats->start_empty_time);
531	cfqg_stats_clear_empty(stats);
532	}
533
534	static void cfqg_stats_update_dequeue(struct cfq_group *cfqg)
535	{
536	blkg_stat_add(&cfqg->stats.dequeue, 1);
537	}
538
539	static void cfqg_stats_set_start_empty_time(struct cfq_group *cfqg)
540	{
541	struct cfqg_stats *stats = &cfqg->stats;
542
543	if (blkg_rwstat_total(&stats->queued))
544	return;
545
546	/*
547	* group is already marked empty. This can happen if cfqq got new
548	* request in parent group and moved to this group while being added
549	* to service tree. Just ignore the event and move on.
550	*/
551	if (cfqg_stats_empty(stats))
552	return;
553
554	stats->start_empty_time = sched_clock();
555	cfqg_stats_mark_empty(stats);
556	}
557
558	static void cfqg_stats_update_idle_time(struct cfq_group *cfqg)
559	{
560	struct cfqg_stats *stats = &cfqg->stats;
561
562	if (cfqg_stats_idling(stats)) {
563	unsigned long long now = sched_clock();
564
565	if (time_after64(now, stats->start_idle_time))
566	blkg_stat_add(&stats->idle_time,
567	now - stats->start_idle_time);
568	cfqg_stats_clear_idling(stats);
569	}
570	}
571
572	static void cfqg_stats_set_start_idle_time(struct cfq_group *cfqg)
573	{
574	struct cfqg_stats *stats = &cfqg->stats;
575
576	BUG_ON(cfqg_stats_idling(stats));
577
578	stats->start_idle_time = sched_clock();
579	cfqg_stats_mark_idling(stats);
580	}
581
582	static void cfqg_stats_update_avg_queue_size(struct cfq_group *cfqg)
583	{
584	struct cfqg_stats *stats = &cfqg->stats;
585
586	blkg_stat_add(&stats->avg_queue_size_sum,
587	blkg_rwstat_total(&stats->queued));
588	blkg_stat_add(&stats->avg_queue_size_samples, 1);
589	cfqg_stats_update_group_wait_time(stats);
590	}
591
592	#else /* CONFIG_CFQ_GROUP_IOSCHED && CONFIG_DEBUG_BLK_CGROUP */
593
594	static inline void cfqg_stats_set_start_group_wait_time(struct cfq_group *cfqg, struct cfq_group *curr_cfqg) { }
595	static inline void cfqg_stats_end_empty_time(struct cfqg_stats *stats) { }
596	static inline void cfqg_stats_update_dequeue(struct cfq_group *cfqg) { }
597	static inline void cfqg_stats_set_start_empty_time(struct cfq_group *cfqg) { }
598	static inline void cfqg_stats_update_idle_time(struct cfq_group *cfqg) { }
599	static inline void cfqg_stats_set_start_idle_time(struct cfq_group *cfqg) { }
600	static inline void cfqg_stats_update_avg_queue_size(struct cfq_group *cfqg) { }
601
602	#endif /* CONFIG_CFQ_GROUP_IOSCHED && CONFIG_DEBUG_BLK_CGROUP */
603
604	#ifdef CONFIG_CFQ_GROUP_IOSCHED
605
606	static inline struct cfq_group *pd_to_cfqg(struct blkg_policy_data *pd)
607	{
608	return pd ? container_of(pd, struct cfq_group, pd) : NULL;
609	}
610
611	static struct cfq_group_data
612	*cpd_to_cfqgd(struct blkcg_policy_data *cpd)
613	{
614	return cpd ? container_of(cpd, struct cfq_group_data, cpd) : NULL;
615	}
616
617	static inline struct blkcg_gq *cfqg_to_blkg(struct cfq_group *cfqg)
618	{
619	return pd_to_blkg(&cfqg->pd);
620	}
621
622	static struct blkcg_policy blkcg_policy_cfq;
623
624	static inline struct cfq_group *blkg_to_cfqg(struct blkcg_gq *blkg)
625	{
626	return pd_to_cfqg(blkg_to_pd(blkg, &blkcg_policy_cfq));
627	}
628
629	static struct cfq_group_data *blkcg_to_cfqgd(struct blkcg *blkcg)
630	{
631	return cpd_to_cfqgd(blkcg_to_cpd(blkcg, &blkcg_policy_cfq));
632	}
633
634	static inline struct cfq_group *cfqg_parent(struct cfq_group *cfqg)
635	{
636	struct blkcg_gq *pblkg = cfqg_to_blkg(cfqg)->parent;
637
638	return pblkg ? blkg_to_cfqg(pblkg) : NULL;
639	}
640
641	static inline bool cfqg_is_descendant(struct cfq_group *cfqg,
642	struct cfq_group *ancestor)
643	{
644	return cgroup_is_descendant(cfqg_to_blkg(cfqg)->blkcg->css.cgroup,
645	cfqg_to_blkg(ancestor)->blkcg->css.cgroup);
646	}
647
648	static inline void cfqg_get(struct cfq_group *cfqg)
649	{
650	return blkg_get(cfqg_to_blkg(cfqg));
651	}
652
653	static inline void cfqg_put(struct cfq_group *cfqg)
654	{
655	return blkg_put(cfqg_to_blkg(cfqg));
656	}
657
658	#define cfq_log_cfqq(cfqd, cfqq, fmt, args...) do { \
659	char __pbuf[128]; \
660	\
661	blkg_path(cfqg_to_blkg((cfqq)->cfqg), __pbuf, sizeof(__pbuf)); \
662	blk_add_trace_msg((cfqd)->queue, "cfq%d%c%c %s " fmt, (cfqq)->pid, \
663	cfq_cfqq_sync((cfqq)) ? 'S' : 'A', \
664	cfqq_type((cfqq)) == SYNC_NOIDLE_WORKLOAD ? 'N' : ' ',\
665	__pbuf, ##args); \
666	} while (0)
667
668	#define cfq_log_cfqg(cfqd, cfqg, fmt, args...) do { \
669	char __pbuf[128]; \
670	\
671	blkg_path(cfqg_to_blkg(cfqg), __pbuf, sizeof(__pbuf)); \
672	blk_add_trace_msg((cfqd)->queue, "%s " fmt, __pbuf, ##args); \
673	} while (0)
674
675	static inline void cfqg_stats_update_io_add(struct cfq_group *cfqg,
676	struct cfq_group *curr_cfqg, int op,
677	int op_flags)
678	{
679	blkg_rwstat_add(&cfqg->stats.queued, op, op_flags, 1);
680	cfqg_stats_end_empty_time(&cfqg->stats);
681	cfqg_stats_set_start_group_wait_time(cfqg, curr_cfqg);
682	}
683
684	static inline void cfqg_stats_update_timeslice_used(struct cfq_group *cfqg,
685	uint64_t time, unsigned long unaccounted_time)
686	{
687	blkg_stat_add(&cfqg->stats.time, time);
688	#ifdef CONFIG_DEBUG_BLK_CGROUP
689	blkg_stat_add(&cfqg->stats.unaccounted_time, unaccounted_time);
690	#endif
691	}
692
693	static inline void cfqg_stats_update_io_remove(struct cfq_group *cfqg, int op,
694	int op_flags)
695	{
696	blkg_rwstat_add(&cfqg->stats.queued, op, op_flags, -1);
697	}
698
699	static inline void cfqg_stats_update_io_merged(struct cfq_group *cfqg, int op,
700	int op_flags)
701	{
702	blkg_rwstat_add(&cfqg->stats.merged, op, op_flags, 1);
703	}
704
705	static inline void cfqg_stats_update_completion(struct cfq_group *cfqg,
706	uint64_t start_time, uint64_t io_start_time, int op,
707	int op_flags)
708	{
709	struct cfqg_stats *stats = &cfqg->stats;
710	unsigned long long now = sched_clock();
711
712	if (time_after64(now, io_start_time))
713	blkg_rwstat_add(&stats->service_time, op, op_flags,
714	now - io_start_time);
715	if (time_after64(io_start_time, start_time))
716	blkg_rwstat_add(&stats->wait_time, op, op_flags,
717	io_start_time - start_time);
718	}
719
720	/* @stats = 0 */
721	static void cfqg_stats_reset(struct cfqg_stats *stats)
722	{
723	/* queued stats shouldn't be cleared */
724	blkg_rwstat_reset(&stats->merged);
725	blkg_rwstat_reset(&stats->service_time);
726	blkg_rwstat_reset(&stats->wait_time);
727	blkg_stat_reset(&stats->time);
728	#ifdef CONFIG_DEBUG_BLK_CGROUP
729	blkg_stat_reset(&stats->unaccounted_time);
730	blkg_stat_reset(&stats->avg_queue_size_sum);
731	blkg_stat_reset(&stats->avg_queue_size_samples);
732	blkg_stat_reset(&stats->dequeue);
733	blkg_stat_reset(&stats->group_wait_time);
734	blkg_stat_reset(&stats->idle_time);
735	blkg_stat_reset(&stats->empty_time);
736	#endif
737	}
738
739	/* @to += @from */
740	static void cfqg_stats_add_aux(struct cfqg_stats *to, struct cfqg_stats *from)
741	{
742	/* queued stats shouldn't be cleared */
743	blkg_rwstat_add_aux(&to->merged, &from->merged);
744	blkg_rwstat_add_aux(&to->service_time, &from->service_time);
745	blkg_rwstat_add_aux(&to->wait_time, &from->wait_time);
746	blkg_stat_add_aux(&from->time, &from->time);
747	#ifdef CONFIG_DEBUG_BLK_CGROUP
748	blkg_stat_add_aux(&to->unaccounted_time, &from->unaccounted_time);
749	blkg_stat_add_aux(&to->avg_queue_size_sum, &from->avg_queue_size_sum);
750	blkg_stat_add_aux(&to->avg_queue_size_samples, &from->avg_queue_size_samples);
751	blkg_stat_add_aux(&to->dequeue, &from->dequeue);
752	blkg_stat_add_aux(&to->group_wait_time, &from->group_wait_time);
753	blkg_stat_add_aux(&to->idle_time, &from->idle_time);
754	blkg_stat_add_aux(&to->empty_time, &from->empty_time);
755	#endif
756	}
757
758	/*
759	* Transfer @cfqg's stats to its parent's aux counts so that the ancestors'
760	* recursive stats can still account for the amount used by this cfqg after
761	* it's gone.
762	*/
763	static void cfqg_stats_xfer_dead(struct cfq_group *cfqg)
764	{
765	struct cfq_group *parent = cfqg_parent(cfqg);
766
767	lockdep_assert_held(cfqg_to_blkg(cfqg)->q->queue_lock);
768
769	if (unlikely(!parent))
770	return;
771
772	cfqg_stats_add_aux(&parent->stats, &cfqg->stats);
773	cfqg_stats_reset(&cfqg->stats);
774	}
775
776	#else /* CONFIG_CFQ_GROUP_IOSCHED */
777
778	static inline struct cfq_group *cfqg_parent(struct cfq_group *cfqg) { return NULL; }
779	static inline bool cfqg_is_descendant(struct cfq_group *cfqg,
780	struct cfq_group *ancestor)
781	{
782	return true;
783	}
784	static inline void cfqg_get(struct cfq_group *cfqg) { }
785	static inline void cfqg_put(struct cfq_group *cfqg) { }
786
787	#define cfq_log_cfqq(cfqd, cfqq, fmt, args...) \
788	blk_add_trace_msg((cfqd)->queue, "cfq%d%c%c " fmt, (cfqq)->pid, \
789	cfq_cfqq_sync((cfqq)) ? 'S' : 'A', \
790	cfqq_type((cfqq)) == SYNC_NOIDLE_WORKLOAD ? 'N' : ' ',\
791	##args)
792	#define cfq_log_cfqg(cfqd, cfqg, fmt, args...) do {} while (0)
793
794	static inline void cfqg_stats_update_io_add(struct cfq_group *cfqg,
795	struct cfq_group *curr_cfqg, int op, int op_flags) { }
796	static inline void cfqg_stats_update_timeslice_used(struct cfq_group *cfqg,
797	uint64_t time, unsigned long unaccounted_time) { }
798	static inline void cfqg_stats_update_io_remove(struct cfq_group *cfqg, int op,
799	int op_flags) { }
800	static inline void cfqg_stats_update_io_merged(struct cfq_group *cfqg, int op,
801	int op_flags) { }
802	static inline void cfqg_stats_update_completion(struct cfq_group *cfqg,
803	uint64_t start_time, uint64_t io_start_time, int op,
804	int op_flags) { }
805
806	#endif /* CONFIG_CFQ_GROUP_IOSCHED */
807
808	static inline u64 get_group_idle(struct cfq_data *cfqd)
809	{
810	#ifdef CONFIG_CFQ_GROUP_IOSCHED
811	struct cfq_queue *cfqq = cfqd->active_queue;
812
813	if (cfqq && cfqq->cfqg)
814	return cfqq->cfqg->group_idle;
815	#endif
816	return cfqd->cfq_group_idle;
817	}
818
819	#define cfq_log(cfqd, fmt, args...) \
820	blk_add_trace_msg((cfqd)->queue, "cfq " fmt, ##args)
821
822	/* Traverses through cfq group service trees */
823	#define for_each_cfqg_st(cfqg, i, j, st) \
824	for (i = 0; i <= IDLE_WORKLOAD; i++) \
825	for (j = 0, st = i < IDLE_WORKLOAD ? &cfqg->service_trees[i][j]\
826	: &cfqg->service_tree_idle; \
827	(i < IDLE_WORKLOAD && j <= SYNC_WORKLOAD) || \
828	(i == IDLE_WORKLOAD && j == 0); \
829	j++, st = i < IDLE_WORKLOAD ? \
830	&cfqg->service_trees[i][j]: NULL) \
831
832	static inline bool cfq_io_thinktime_big(struct cfq_data *cfqd,
833	struct cfq_ttime *ttime, bool group_idle)
834	{
835	u64 slice;
836	if (!sample_valid(ttime->ttime_samples))
837	return false;
838	if (group_idle)
839	slice = get_group_idle(cfqd);
840	else
841	slice = cfqd->cfq_slice_idle;
842	return ttime->ttime_mean > slice;
843	}
844
845	static inline bool iops_mode(struct cfq_data *cfqd)
846	{
847	/*
848	* If we are not idling on queues and it is a NCQ drive, parallel
849	* execution of requests is on and measuring time is not possible
850	* in most of the cases until and unless we drive shallower queue
851	* depths and that becomes a performance bottleneck. In such cases
852	* switch to start providing fairness in terms of number of IOs.
853	*/
854	if (!cfqd->cfq_slice_idle && cfqd->hw_tag)
855	return true;
856	else
857	return false;
858	}
859
860	static inline enum wl_class_t cfqq_class(struct cfq_queue *cfqq)
861	{
862	if (cfq_class_idle(cfqq))
863	return IDLE_WORKLOAD;
864	if (cfq_class_rt(cfqq))
865	return RT_WORKLOAD;
866	return BE_WORKLOAD;
867	}
868
869
870	static enum wl_type_t cfqq_type(struct cfq_queue *cfqq)
871	{
872	if (!cfq_cfqq_sync(cfqq))
873	return ASYNC_WORKLOAD;
874	if (!cfq_cfqq_idle_window(cfqq))
875	return SYNC_NOIDLE_WORKLOAD;
876	return SYNC_WORKLOAD;
877	}
878
879	static inline int cfq_group_busy_queues_wl(enum wl_class_t wl_class,
880	struct cfq_data *cfqd,
881	struct cfq_group *cfqg)
882	{
883	if (wl_class == IDLE_WORKLOAD)
884	return cfqg->service_tree_idle.count;
885
886	return cfqg->service_trees[wl_class][ASYNC_WORKLOAD].count +
887	cfqg->service_trees[wl_class][SYNC_NOIDLE_WORKLOAD].count +
888	cfqg->service_trees[wl_class][SYNC_WORKLOAD].count;
889	}
890
891	static inline int cfqg_busy_async_queues(struct cfq_data *cfqd,
892	struct cfq_group *cfqg)
893	{
894	return cfqg->service_trees[RT_WORKLOAD][ASYNC_WORKLOAD].count +
895	cfqg->service_trees[BE_WORKLOAD][ASYNC_WORKLOAD].count;
896	}
897
898	static void cfq_dispatch_insert(struct request_queue *, struct request *);
899	static struct cfq_queue *cfq_get_queue(struct cfq_data *cfqd, bool is_sync,
900	struct cfq_io_cq *cic, struct bio *bio);
901
902	static inline struct cfq_io_cq *icq_to_cic(struct io_cq *icq)
903	{
904	/* cic->icq is the first member, %NULL will convert to %NULL */
905	return container_of(icq, struct cfq_io_cq, icq);
906	}
907
908	static inline struct cfq_io_cq *cfq_cic_lookup(struct cfq_data *cfqd,
909	struct io_context *ioc)
910	{
911	if (ioc)
912	return icq_to_cic(ioc_lookup_icq(ioc, cfqd->queue));
913	return NULL;
914	}
915
916	static inline struct cfq_queue *cic_to_cfqq(struct cfq_io_cq *cic, bool is_sync)
917	{
918	return cic->cfqq[is_sync];
919	}
920
921	static inline void cic_set_cfqq(struct cfq_io_cq *cic, struct cfq_queue *cfqq,
922	bool is_sync)
923	{
924	cic->cfqq[is_sync] = cfqq;
925	}
926
927	static inline struct cfq_data *cic_to_cfqd(struct cfq_io_cq *cic)
928	{
929	return cic->icq.q->elevator->elevator_data;
930	}
931
932	/*
933	* We regard a request as SYNC, if it's either a read or has the SYNC bit
934	* set (in which case it could also be direct WRITE).
935	*/
936	static inline bool cfq_bio_sync(struct bio *bio)
937	{
938	return bio_data_dir(bio) == READ || (bio->bi_opf & REQ_SYNC);
939	}
940
941	/*
942	* scheduler run of queue, if there are requests pending and no one in the
943	* driver that will restart queueing
944	*/
945	static inline void cfq_schedule_dispatch(struct cfq_data *cfqd)
946	{
947	if (cfqd->busy_queues) {
948	cfq_log(cfqd, "schedule dispatch");
949	kblockd_schedule_work(&cfqd->unplug_work);
950	}
951	}
952
953	/*
954	* Scale schedule slice based on io priority. Use the sync time slice only
955	* if a queue is marked sync and has sync io queued. A sync queue with async
956	* io only, should not get full sync slice length.
957	*/
958	static inline u64 cfq_prio_slice(struct cfq_data *cfqd, bool sync,
959	unsigned short prio)
960	{
961	u64 base_slice = cfqd->cfq_slice[sync];
962	u64 slice = div_u64(base_slice, CFQ_SLICE_SCALE);
963
964	WARN_ON(prio >= IOPRIO_BE_NR);
965
966	return base_slice + (slice * (4 - prio));
967	}
968
969	static inline u64
970	cfq_prio_to_slice(struct cfq_data *cfqd, struct cfq_queue *cfqq)
971	{
972	return cfq_prio_slice(cfqd, cfq_cfqq_sync(cfqq), cfqq->ioprio);
973	}
974
975	/**
976	* cfqg_scale_charge - scale disk time charge according to cfqg weight
977	* @charge: disk time being charged
978	* @vfraction: vfraction of the cfqg, fixed point w/ CFQ_SERVICE_SHIFT
979	*
980	* Scale @charge according to @vfraction, which is in range (0, 1]. The
981	* scaling is inversely proportional.
982	*
983	* scaled = charge / vfraction
984	*
985	* The result is also in fixed point w/ CFQ_SERVICE_SHIFT.
986	*/
987	static inline u64 cfqg_scale_charge(u64 charge,
988	unsigned int vfraction)
989	{
990	u64 c = charge << CFQ_SERVICE_SHIFT; /* make it fixed point */
991
992	/* charge / vfraction */
993	c <<= CFQ_SERVICE_SHIFT;
994	return div_u64(c, vfraction);
995	}
996
997	static inline u64 max_vdisktime(u64 min_vdisktime, u64 vdisktime)
998	{
999	s64 delta = (s64)(vdisktime - min_vdisktime);
1000	if (delta > 0)
1001	min_vdisktime = vdisktime;
1002
1003	return min_vdisktime;
1004	}
1005
1006	static inline u64 min_vdisktime(u64 min_vdisktime, u64 vdisktime)
1007	{
1008	s64 delta = (s64)(vdisktime - min_vdisktime);
1009	if (delta < 0)
1010	min_vdisktime = vdisktime;
1011
1012	return min_vdisktime;
1013	}
1014
1015	static void update_min_vdisktime(struct cfq_rb_root *st)
1016	{
1017	struct cfq_group *cfqg;
1018
1019	if (st->left) {
1020	cfqg = rb_entry_cfqg(st->left);
1021	st->min_vdisktime = max_vdisktime(st->min_vdisktime,
1022	cfqg->vdisktime);
1023	}
1024	}
1025
1026	/*
1027	* get averaged number of queues of RT/BE priority.
1028	* average is updated, with a formula that gives more weight to higher numbers,
1029	* to quickly follows sudden increases and decrease slowly
1030	*/
1031
1032	static inline unsigned cfq_group_get_avg_queues(struct cfq_data *cfqd,
1033	struct cfq_group *cfqg, bool rt)
1034	{
1035	unsigned min_q, max_q;
1036	unsigned mult = cfq_hist_divisor - 1;
1037	unsigned round = cfq_hist_divisor / 2;
1038	unsigned busy = cfq_group_busy_queues_wl(rt, cfqd, cfqg);
1039
1040	min_q = min(cfqg->busy_queues_avg[rt], busy);
1041	max_q = max(cfqg->busy_queues_avg[rt], busy);
1042	cfqg->busy_queues_avg[rt] = (mult * max_q + min_q + round) /
1043	cfq_hist_divisor;
1044	return cfqg->busy_queues_avg[rt];
1045	}
1046
1047	static inline u64
1048	cfq_group_slice(struct cfq_data *cfqd, struct cfq_group *cfqg)
1049	{
1050	return cfqd->cfq_target_latency * cfqg->vfraction >> CFQ_SERVICE_SHIFT;
1051	}
1052
1053	static inline u64
1054	cfq_scaled_cfqq_slice(struct cfq_data *cfqd, struct cfq_queue *cfqq)
1055	{
1056	u64 slice = cfq_prio_to_slice(cfqd, cfqq);
1057	if (cfqd->cfq_latency) {
1058	/*
1059	* interested queues (we consider only the ones with the same
1060	* priority class in the cfq group)
1061	*/
1062	unsigned iq = cfq_group_get_avg_queues(cfqd, cfqq->cfqg,
1063	cfq_class_rt(cfqq));
1064	u64 sync_slice = cfqd->cfq_slice[1];
1065	u64 expect_latency = sync_slice * iq;
1066	u64 group_slice = cfq_group_slice(cfqd, cfqq->cfqg);
1067
1068	if (expect_latency > group_slice) {
1069	u64 base_low_slice = 2 * cfqd->cfq_slice_idle;
1070	u64 low_slice;
1071
1072	/* scale low_slice according to IO priority
1073	* and sync vs async */
1074	low_slice = div64_u64(base_low_slice*slice, sync_slice);
1075	low_slice = min(slice, low_slice);
1076	/* the adapted slice value is scaled to fit all iqs
1077	* into the target latency */
1078	slice = div64_u64(slice*group_slice, expect_latency);
1079	slice = max(slice, low_slice);
1080	}
1081	}
1082	return slice;
1083	}
1084
1085	static inline void
1086	cfq_set_prio_slice(struct cfq_data *cfqd, struct cfq_queue *cfqq)
1087	{
1088	u64 slice = cfq_scaled_cfqq_slice(cfqd, cfqq);
1089	u64 now = ktime_get_ns();
1090
1091	cfqq->slice_start = now;
1092	cfqq->slice_end = now + slice;
1093	cfqq->allocated_slice = slice;
1094	cfq_log_cfqq(cfqd, cfqq, "set_slice=%llu", cfqq->slice_end - now);
1095	}
1096
1097	/*
1098	* We need to wrap this check in cfq_cfqq_slice_new(), since ->slice_end
1099	* isn't valid until the first request from the dispatch is activated
1100	* and the slice time set.
1101	*/
1102	static inline bool cfq_slice_used(struct cfq_queue *cfqq)
1103	{
1104	if (cfq_cfqq_slice_new(cfqq))
1105	return false;
1106	if (ktime_get_ns() < cfqq->slice_end)
1107	return false;
1108
1109	return true;
1110	}
1111
1112	/*
1113	* Lifted from AS - choose which of rq1 and rq2 that is best served now.
1114	* We choose the request that is closest to the head right now. Distance
1115	* behind the head is penalized and only allowed to a certain extent.
1116	*/
1117	static struct request *
1118	cfq_choose_req(struct cfq_data *cfqd, struct request *rq1, struct request *rq2, sector_t last)
1119	{
1120	sector_t s1, s2, d1 = 0, d2 = 0;
1121	unsigned long back_max;
1122	#define CFQ_RQ1_WRAP 0x01 /* request 1 wraps */
1123	#define CFQ_RQ2_WRAP 0x02 /* request 2 wraps */
1124	unsigned wrap = 0; /* bit mask: requests behind the disk head? */
1125
1126	if (rq1 == NULL || rq1 == rq2)
1127	return rq2;
1128	if (rq2 == NULL)
1129	return rq1;
1130
1131	if (rq_is_sync(rq1) != rq_is_sync(rq2))
1132	return rq_is_sync(rq1) ? rq1 : rq2;
1133
1134	if ((rq1->cmd_flags ^ rq2->cmd_flags) & REQ_PRIO)
1135	return rq1->cmd_flags & REQ_PRIO ? rq1 : rq2;
1136
1137	s1 = blk_rq_pos(rq1);
1138	s2 = blk_rq_pos(rq2);
1139
1140	/*
1141	* by definition, 1KiB is 2 sectors
1142	*/
1143	back_max = cfqd->cfq_back_max * 2;
1144
1145	/*
1146	* Strict one way elevator _except_ in the case where we allow
1147	* short backward seeks which are biased as twice the cost of a
1148	* similar forward seek.
1149	*/
1150	if (s1 >= last)
1151	d1 = s1 - last;
1152	else if (s1 + back_max >= last)
1153	d1 = (last - s1) * cfqd->cfq_back_penalty;
1154	else
1155	wrap |= CFQ_RQ1_WRAP;
1156
1157	if (s2 >= last)
1158	d2 = s2 - last;
1159	else if (s2 + back_max >= last)
1160	d2 = (last - s2) * cfqd->cfq_back_penalty;
1161	else
1162	wrap |= CFQ_RQ2_WRAP;
1163
1164	/* Found required data */
1165
1166	/*
1167	* By doing switch() on the bit mask "wrap" we avoid having to
1168	* check two variables for all permutations: --> faster!
1169	*/
1170	switch (wrap) {
1171	case 0: /* common case for CFQ: rq1 and rq2 not wrapped */
1172	if (d1 < d2)
1173	return rq1;
1174	else if (d2 < d1)
1175	return rq2;
1176	else {
1177	if (s1 >= s2)
1178	return rq1;
1179	else
1180	return rq2;
1181	}
1182
1183	case CFQ_RQ2_WRAP:
1184	return rq1;
1185	case CFQ_RQ1_WRAP:
1186	return rq2;
1187	case (CFQ_RQ1_WRAP|CFQ_RQ2_WRAP): /* both rqs wrapped */
1188	default:
1189	/*
1190	* Since both rqs are wrapped,
1191	* start with the one that's further behind head
1192	* (--> only *one* back seek required),
1193	* since back seek takes more time than forward.
1194	*/
1195	if (s1 <= s2)
1196	return rq1;
1197	else
1198	return rq2;
1199	}
1200	}
1201
1202	/*
1203	* The below is leftmost cache rbtree addon
1204	*/
1205	static struct cfq_queue *cfq_rb_first(struct cfq_rb_root *root)
1206	{
1207	/* Service tree is empty */
1208	if (!root->count)
1209	return NULL;
1210
1211	if (!root->left)
1212	root->left = rb_first(&root->rb);
1213
1214	if (root->left)
1215	return rb_entry(root->left, struct cfq_queue, rb_node);
1216
1217	return NULL;
1218	}
1219
1220	static struct cfq_group *cfq_rb_first_group(struct cfq_rb_root *root)
1221	{
1222	if (!root->left)
1223	root->left = rb_first(&root->rb);
1224
1225	if (root->left)
1226	return rb_entry_cfqg(root->left);
1227
1228	return NULL;
1229	}
1230
1231	static void rb_erase_init(struct rb_node *n, struct rb_root *root)
1232	{
1233	rb_erase(n, root);
1234	RB_CLEAR_NODE(n);
1235	}
1236
1237	static void cfq_rb_erase(struct rb_node *n, struct cfq_rb_root *root)
1238	{
1239	if (root->left == n)
1240	root->left = NULL;
1241	rb_erase_init(n, &root->rb);
1242	--root->count;
1243	}
1244
1245	/*
1246	* would be nice to take fifo expire time into account as well
1247	*/
1248	static struct request *
1249	cfq_find_next_rq(struct cfq_data *cfqd, struct cfq_queue *cfqq,
1250	struct request *last)
1251	{
1252	struct rb_node *rbnext = rb_next(&last->rb_node);
1253	struct rb_node *rbprev = rb_prev(&last->rb_node);
1254	struct request *next = NULL, *prev = NULL;
1255
1256	BUG_ON(RB_EMPTY_NODE(&last->rb_node));
1257
1258	if (rbprev)
1259	prev = rb_entry_rq(rbprev);
1260
1261	if (rbnext)
1262	next = rb_entry_rq(rbnext);
1263	else {
1264	rbnext = rb_first(&cfqq->sort_list);
1265	if (rbnext && rbnext != &last->rb_node)
1266	next = rb_entry_rq(rbnext);
1267	}
1268
1269	return cfq_choose_req(cfqd, next, prev, blk_rq_pos(last));
1270	}
1271
1272	static u64 cfq_slice_offset(struct cfq_data *cfqd,
1273	struct cfq_queue *cfqq)
1274	{
1275	/*
1276	* just an approximation, should be ok.
1277	*/
1278	return (cfqq->cfqg->nr_cfqq - 1) * (cfq_prio_slice(cfqd, 1, 0) -
1279	cfq_prio_slice(cfqd, cfq_cfqq_sync(cfqq), cfqq->ioprio));
1280	}
1281
1282	static inline s64
1283	cfqg_key(struct cfq_rb_root *st, struct cfq_group *cfqg)
1284	{
1285	return cfqg->vdisktime - st->min_vdisktime;
1286	}
1287
1288	static void
1289	__cfq_group_service_tree_add(struct cfq_rb_root *st, struct cfq_group *cfqg)
1290	{
1291	struct rb_node **node = &st->rb.rb_node;
1292	struct rb_node *parent = NULL;
1293	struct cfq_group *__cfqg;
1294	s64 key = cfqg_key(st, cfqg);
1295	int left = 1;
1296
1297	while (*node != NULL) {
1298	parent = *node;
1299	__cfqg = rb_entry_cfqg(parent);
1300
1301	if (key < cfqg_key(st, __cfqg))
1302	node = &parent->rb_left;
1303	else {
1304	node = &parent->rb_right;
1305	left = 0;
1306	}
1307	}
1308
1309	if (left)
1310	st->left = &cfqg->rb_node;
1311
1312	rb_link_node(&cfqg->rb_node, parent, node);
1313	rb_insert_color(&cfqg->rb_node, &st->rb);
1314	}
1315
1316	/*
1317	* This has to be called only on activation of cfqg
1318	*/
1319	static void
1320	cfq_update_group_weight(struct cfq_group *cfqg)
1321	{
1322	if (cfqg->new_weight) {
1323	cfqg->weight = cfqg->new_weight;
1324	cfqg->new_weight = 0;
1325	}
1326	}
1327
1328	static void
1329	cfq_update_group_leaf_weight(struct cfq_group *cfqg)
1330	{
1331	BUG_ON(!RB_EMPTY_NODE(&cfqg->rb_node));
1332
1333	if (cfqg->new_leaf_weight) {
1334	cfqg->leaf_weight = cfqg->new_leaf_weight;
1335	cfqg->new_leaf_weight = 0;
1336	}
1337	}
1338
1339	static void
1340	cfq_group_service_tree_add(struct cfq_rb_root *st, struct cfq_group *cfqg)
1341	{
1342	unsigned int vfr = 1 << CFQ_SERVICE_SHIFT; /* start with 1 */
1343	struct cfq_group *pos = cfqg;
1344	struct cfq_group *parent;
1345	bool propagate;
1346
1347	/* add to the service tree */
1348	BUG_ON(!RB_EMPTY_NODE(&cfqg->rb_node));
1349
1350	/*
1351	* Update leaf_weight. We cannot update weight at this point
1352	* because cfqg might already have been activated and is
1353	* contributing its current weight to the parent's child_weight.
1354	*/
1355	cfq_update_group_leaf_weight(cfqg);
1356	__cfq_group_service_tree_add(st, cfqg);
1357
1358	/*
1359	* Activate @cfqg and calculate the portion of vfraction @cfqg is
1360	* entitled to. vfraction is calculated by walking the tree
1361	* towards the root calculating the fraction it has at each level.
1362	* The compounded ratio is how much vfraction @cfqg owns.
1363	*
1364	* Start with the proportion tasks in this cfqg has against active
1365	* children cfqgs - its leaf_weight against children_weight.
1366	*/
1367	propagate = !pos->nr_active++;
1368	pos->children_weight += pos->leaf_weight;
1369	vfr = vfr * pos->leaf_weight / pos->children_weight;
1370
1371	/*
1372	* Compound ->weight walking up the tree. Both activation and
1373	* vfraction calculation are done in the same loop. Propagation
1374	* stops once an already activated node is met. vfraction
1375	* calculation should always continue to the root.
1376	*/
1377	while ((parent = cfqg_parent(pos))) {
1378	if (propagate) {
1379	cfq_update_group_weight(pos);
1380	propagate = !parent->nr_active++;
1381	parent->children_weight += pos->weight;
1382	}
1383	vfr = vfr * pos->weight / parent->children_weight;
1384	pos = parent;
1385	}
1386
1387	cfqg->vfraction = max_t(unsigned, vfr, 1);
1388	}
1389
1390	static inline u64 cfq_get_cfqg_vdisktime_delay(struct cfq_data *cfqd)
1391	{
1392	if (!iops_mode(cfqd))
1393	return CFQ_SLICE_MODE_GROUP_DELAY;
1394	else
1395	return CFQ_IOPS_MODE_GROUP_DELAY;
1396	}
1397
1398	static void
1399	cfq_group_notify_queue_add(struct cfq_data *cfqd, struct cfq_group *cfqg)
1400	{
1401	struct cfq_rb_root *st = &cfqd->grp_service_tree;
1402	struct cfq_group *__cfqg;
1403	struct rb_node *n;
1404
1405	cfqg->nr_cfqq++;
1406	if (!RB_EMPTY_NODE(&cfqg->rb_node))
1407	return;
1408
1409	/*
1410	* Currently put the group at the end. Later implement something
1411	* so that groups get lesser vtime based on their weights, so that
1412	* if group does not loose all if it was not continuously backlogged.
1413	*/
1414	n = rb_last(&st->rb);
1415	if (n) {
1416	__cfqg = rb_entry_cfqg(n);
1417	cfqg->vdisktime = __cfqg->vdisktime +
1418	cfq_get_cfqg_vdisktime_delay(cfqd);
1419	} else
1420	cfqg->vdisktime = st->min_vdisktime;
1421	cfq_group_service_tree_add(st, cfqg);
1422	}
1423
1424	static void
1425	cfq_group_service_tree_del(struct cfq_rb_root *st, struct cfq_group *cfqg)
1426	{
1427	struct cfq_group *pos = cfqg;
1428	bool propagate;
1429
1430	/*
1431	* Undo activation from cfq_group_service_tree_add(). Deactivate
1432	* @cfqg and propagate deactivation upwards.
1433	*/
1434	propagate = !--pos->nr_active;
1435	pos->children_weight -= pos->leaf_weight;
1436
1437	while (propagate) {
1438	struct cfq_group *parent = cfqg_parent(pos);
1439
1440	/* @pos has 0 nr_active at this point */
1441	WARN_ON_ONCE(pos->children_weight);
1442	pos->vfraction = 0;
1443
1444	if (!parent)
1445	break;
1446
1447	propagate = !--parent->nr_active;
1448	parent->children_weight -= pos->weight;
1449	pos = parent;
1450	}
1451
1452	/* remove from the service tree */
1453	if (!RB_EMPTY_NODE(&cfqg->rb_node))
1454	cfq_rb_erase(&cfqg->rb_node, st);
1455	}
1456
1457	static void
1458	cfq_group_notify_queue_del(struct cfq_data *cfqd, struct cfq_group *cfqg)
1459	{
1460	struct cfq_rb_root *st = &cfqd->grp_service_tree;
1461
1462	BUG_ON(cfqg->nr_cfqq < 1);
1463	cfqg->nr_cfqq--;
1464
1465	/* If there are other cfq queues under this group, don't delete it */
1466	if (cfqg->nr_cfqq)
1467	return;
1468
1469	cfq_log_cfqg(cfqd, cfqg, "del_from_rr group");
1470	cfq_group_service_tree_del(st, cfqg);
1471	cfqg->saved_wl_slice = 0;
1472	cfqg_stats_update_dequeue(cfqg);
1473	}
1474
1475	static inline u64 cfq_cfqq_slice_usage(struct cfq_queue *cfqq,
1476	u64 *unaccounted_time)
1477	{
1478	u64 slice_used;
1479	u64 now = ktime_get_ns();
1480
1481	/*
1482	* Queue got expired before even a single request completed or
1483	* got expired immediately after first request completion.
1484	*/
1485	if (!cfqq->slice_start || cfqq->slice_start == now) {
1486	/*
1487	* Also charge the seek time incurred to the group, otherwise
1488	* if there are mutiple queues in the group, each can dispatch
1489	* a single request on seeky media and cause lots of seek time
1490	* and group will never know it.
1491	*/
1492	slice_used = max_t(u64, (now - cfqq->dispatch_start),
1493	jiffies_to_nsecs(1));
1494	} else {
1495	slice_used = now - cfqq->slice_start;
1496	if (slice_used > cfqq->allocated_slice) {
1497	*unaccounted_time = slice_used - cfqq->allocated_slice;
1498	slice_used = cfqq->allocated_slice;
1499	}
1500	if (cfqq->slice_start > cfqq->dispatch_start)
1501	*unaccounted_time += cfqq->slice_start -
1502	cfqq->dispatch_start;
1503	}
1504
1505	return slice_used;
1506	}
1507
1508	static void cfq_group_served(struct cfq_data *cfqd, struct cfq_group *cfqg,
1509	struct cfq_queue *cfqq)
1510	{
1511	struct cfq_rb_root *st = &cfqd->grp_service_tree;
1512	u64 used_sl, charge, unaccounted_sl = 0;
1513	int nr_sync = cfqg->nr_cfqq - cfqg_busy_async_queues(cfqd, cfqg)
1514	- cfqg->service_tree_idle.count;
1515	unsigned int vfr;
1516	u64 now = ktime_get_ns();
1517
1518	BUG_ON(nr_sync < 0);
1519	used_sl = charge = cfq_cfqq_slice_usage(cfqq, &unaccounted_sl);
1520
1521	if (iops_mode(cfqd))
1522	charge = cfqq->slice_dispatch;
1523	else if (!cfq_cfqq_sync(cfqq) && !nr_sync)
1524	charge = cfqq->allocated_slice;
1525
1526	/*
1527	* Can't update vdisktime while on service tree and cfqg->vfraction
1528	* is valid only while on it. Cache vfr, leave the service tree,
1529	* update vdisktime and go back on. The re-addition to the tree
1530	* will also update the weights as necessary.
1531	*/
1532	vfr = cfqg->vfraction;
1533	cfq_group_service_tree_del(st, cfqg);
1534	cfqg->vdisktime += cfqg_scale_charge(charge, vfr);
1535	cfq_group_service_tree_add(st, cfqg);
1536
1537	/* This group is being expired. Save the context */
1538	if (cfqd->workload_expires > now) {
1539	cfqg->saved_wl_slice = cfqd->workload_expires - now;
1540	cfqg->saved_wl_type = cfqd->serving_wl_type;
1541	cfqg->saved_wl_class = cfqd->serving_wl_class;
1542	} else
1543	cfqg->saved_wl_slice = 0;
1544
1545	cfq_log_cfqg(cfqd, cfqg, "served: vt=%llu min_vt=%llu", cfqg->vdisktime,
1546	st->min_vdisktime);
1547	cfq_log_cfqq(cfqq->cfqd, cfqq,
1548	"sl_used=%llu disp=%llu charge=%llu iops=%u sect=%lu",
1549	used_sl, cfqq->slice_dispatch, charge,
1550	iops_mode(cfqd), cfqq->nr_sectors);
1551	cfqg_stats_update_timeslice_used(cfqg, used_sl, unaccounted_sl);
1552	cfqg_stats_set_start_empty_time(cfqg);
1553	}
1554
1555	/**
1556	* cfq_init_cfqg_base - initialize base part of a cfq_group
1557	* @cfqg: cfq_group to initialize
1558	*
1559	* Initialize the base part which is used whether %CONFIG_CFQ_GROUP_IOSCHED
1560	* is enabled or not.
1561	*/
1562	static void cfq_init_cfqg_base(struct cfq_group *cfqg)
1563	{
1564	struct cfq_rb_root *st;
1565	int i, j;
1566
1567	for_each_cfqg_st(cfqg, i, j, st)
1568	*st = CFQ_RB_ROOT;
1569	RB_CLEAR_NODE(&cfqg->rb_node);
1570
1571	cfqg->ttime.last_end_request = ktime_get_ns();
1572	}
1573
1574	#ifdef CONFIG_CFQ_GROUP_IOSCHED
1575	static int __cfq_set_weight(struct cgroup_subsys_state *css, u64 val,
1576	bool on_dfl, bool reset_dev, bool is_leaf_weight);
1577
1578	static void cfqg_stats_exit(struct cfqg_stats *stats)
1579	{
1580	blkg_rwstat_exit(&stats->merged);
1581	blkg_rwstat_exit(&stats->service_time);
1582	blkg_rwstat_exit(&stats->wait_time);
1583	blkg_rwstat_exit(&stats->queued);
1584	blkg_stat_exit(&stats->time);
1585	#ifdef CONFIG_DEBUG_BLK_CGROUP
1586	blkg_stat_exit(&stats->unaccounted_time);
1587	blkg_stat_exit(&stats->avg_queue_size_sum);
1588	blkg_stat_exit(&stats->avg_queue_size_samples);
1589	blkg_stat_exit(&stats->dequeue);
1590	blkg_stat_exit(&stats->group_wait_time);
1591	blkg_stat_exit(&stats->idle_time);
1592	blkg_stat_exit(&stats->empty_time);
1593	#endif
1594	}
1595
1596	static int cfqg_stats_init(struct cfqg_stats *stats, gfp_t gfp)
1597	{
1598	if (blkg_rwstat_init(&stats->merged, gfp) ||
1599	blkg_rwstat_init(&stats->service_time, gfp) ||
1600	blkg_rwstat_init(&stats->wait_time, gfp) ||
1601	blkg_rwstat_init(&stats->queued, gfp) ||
1602	blkg_stat_init(&stats->time, gfp))
1603	goto err;
1604
1605	#ifdef CONFIG_DEBUG_BLK_CGROUP
1606	if (blkg_stat_init(&stats->unaccounted_time, gfp) ||
1607	blkg_stat_init(&stats->avg_queue_size_sum, gfp) ||
1608	blkg_stat_init(&stats->avg_queue_size_samples, gfp) ||
1609	blkg_stat_init(&stats->dequeue, gfp) ||
1610	blkg_stat_init(&stats->group_wait_time, gfp) ||
1611	blkg_stat_init(&stats->idle_time, gfp) ||
1612	blkg_stat_init(&stats->empty_time, gfp))
1613	goto err;
1614	#endif
1615	return 0;
1616	err:
1617	cfqg_stats_exit(stats);
1618	return -ENOMEM;
1619	}
1620
1621	static struct blkcg_policy_data *cfq_cpd_alloc(gfp_t gfp)
1622	{
1623	struct cfq_group_data *cgd;
1624
1625	cgd = kzalloc(sizeof(*cgd), gfp);
1626	if (!cgd)
1627	return NULL;
1628	return &cgd->cpd;
1629	}
1630
1631	static void cfq_cpd_init(struct blkcg_policy_data *cpd)
1632	{
1633	struct cfq_group_data *cgd = cpd_to_cfqgd(cpd);
1634	unsigned int weight = cgroup_subsys_on_dfl(io_cgrp_subsys) ?
1635	CGROUP_WEIGHT_DFL : CFQ_WEIGHT_LEGACY_DFL;
1636
1637	if (cpd_to_blkcg(cpd) == &blkcg_root)
1638	weight *= 2;
1639
1640	cgd->weight = weight;
1641	cgd->leaf_weight = weight;
1642	cgd->group_idle = cfq_group_idle;
1643	}
1644
1645	static void cfq_cpd_free(struct blkcg_policy_data *cpd)
1646	{
1647	kfree(cpd_to_cfqgd(cpd));
1648	}
1649
1650	static void cfq_cpd_bind(struct blkcg_policy_data *cpd)
1651	{
1652	struct blkcg *blkcg = cpd_to_blkcg(cpd);
1653	bool on_dfl = cgroup_subsys_on_dfl(io_cgrp_subsys);
1654	unsigned int weight = on_dfl ? CGROUP_WEIGHT_DFL : CFQ_WEIGHT_LEGACY_DFL;
1655
1656	if (blkcg == &blkcg_root)
1657	weight *= 2;
1658
1659	WARN_ON_ONCE(__cfq_set_weight(&blkcg->css, weight, on_dfl, true, false));
1660	WARN_ON_ONCE(__cfq_set_weight(&blkcg->css, weight, on_dfl, true, true));
1661	}
1662
1663	static struct blkg_policy_data *cfq_pd_alloc(gfp_t gfp, int node)
1664	{
1665	struct cfq_group *cfqg;
1666
1667	cfqg = kzalloc_node(sizeof(*cfqg), gfp, node);
1668	if (!cfqg)
1669	return NULL;
1670
1671	cfq_init_cfqg_base(cfqg);
1672	if (cfqg_stats_init(&cfqg->stats, gfp)) {
1673	kfree(cfqg);
1674	return NULL;
1675	}
1676
1677	return &cfqg->pd;
1678	}
1679
1680	static void cfq_pd_init(struct blkg_policy_data *pd)
1681	{
1682	struct cfq_group *cfqg = pd_to_cfqg(pd);
1683	struct cfq_group_data *cgd = blkcg_to_cfqgd(pd->blkg->blkcg);
1684
1685	cfqg->weight = cgd->weight;
1686	cfqg->leaf_weight = cgd->leaf_weight;
1687	cfqg->group_idle = cgd->group_idle;
1688	}
1689
1690	static void cfq_pd_offline(struct blkg_policy_data *pd)
1691	{
1692	struct cfq_group *cfqg = pd_to_cfqg(pd);
1693	int i;
1694
1695	for (i = 0; i < IOPRIO_BE_NR; i++) {
1696	if (cfqg->async_cfqq[0][i])
1697	cfq_put_queue(cfqg->async_cfqq[0][i]);
1698	if (cfqg->async_cfqq[1][i])
1699	cfq_put_queue(cfqg->async_cfqq[1][i]);
1700	}
1701
1702	if (cfqg->async_idle_cfqq)
1703	cfq_put_queue(cfqg->async_idle_cfqq);
1704
1705	/*
1706	* @blkg is going offline and will be ignored by
1707	* blkg_[rw]stat_recursive_sum(). Transfer stats to the parent so
1708	* that they don't get lost. If IOs complete after this point, the
1709	* stats for them will be lost. Oh well...
1710	*/
1711	cfqg_stats_xfer_dead(cfqg);
1712	}
1713
1714	static void cfq_pd_free(struct blkg_policy_data *pd)
1715	{
1716	struct cfq_group *cfqg = pd_to_cfqg(pd);
1717
1718	cfqg_stats_exit(&cfqg->stats);
1719	return kfree(cfqg);
1720	}
1721
1722	static void cfq_pd_reset_stats(struct blkg_policy_data *pd)
1723	{
1724	struct cfq_group *cfqg = pd_to_cfqg(pd);
1725
1726	cfqg_stats_reset(&cfqg->stats);
1727	}
1728
1729	static struct cfq_group *cfq_lookup_cfqg(struct cfq_data *cfqd,
1730	struct blkcg *blkcg)
1731	{
1732	struct blkcg_gq *blkg;
1733
1734	blkg = blkg_lookup(blkcg, cfqd->queue);
1735	if (likely(blkg))
1736	return blkg_to_cfqg(blkg);
1737	return NULL;
1738	}
1739
1740	static void cfq_link_cfqq_cfqg(struct cfq_queue *cfqq, struct cfq_group *cfqg)
1741	{
1742	cfqq->cfqg = cfqg;
1743	/* cfqq reference on cfqg */
1744	cfqg_get(cfqg);
1745	}
1746
1747	static u64 cfqg_prfill_weight_device(struct seq_file *sf,
1748	struct blkg_policy_data *pd, int off)
1749	{
1750	struct cfq_group *cfqg = pd_to_cfqg(pd);
1751
1752	if (!cfqg->dev_weight)
1753	return 0;
1754	return __blkg_prfill_u64(sf, pd, cfqg->dev_weight);
1755	}
1756
1757	static int cfqg_print_weight_device(struct seq_file *sf, void *v)
1758	{
1759	blkcg_print_blkgs(sf, css_to_blkcg(seq_css(sf)),
1760	cfqg_prfill_weight_device, &blkcg_policy_cfq,
1761	0, false);
1762	return 0;
1763	}
1764
1765	static u64 cfqg_prfill_leaf_weight_device(struct seq_file *sf,
1766	struct blkg_policy_data *pd, int off)
1767	{
1768	struct cfq_group *cfqg = pd_to_cfqg(pd);
1769
1770	if (!cfqg->dev_leaf_weight)
1771	return 0;
1772	return __blkg_prfill_u64(sf, pd, cfqg->dev_leaf_weight);
1773	}
1774
1775	static int cfqg_print_leaf_weight_device(struct seq_file *sf, void *v)
1776	{
1777	blkcg_print_blkgs(sf, css_to_blkcg(seq_css(sf)),
1778	cfqg_prfill_leaf_weight_device, &blkcg_policy_cfq,
1779	0, false);
1780	return 0;
1781	}
1782
1783	static int cfq_print_weight(struct seq_file *sf, void *v)
1784	{
1785	struct blkcg *blkcg = css_to_blkcg(seq_css(sf));
1786	struct cfq_group_data *cgd = blkcg_to_cfqgd(blkcg);
1787	unsigned int val = 0;
1788
1789	if (cgd)
1790	val = cgd->weight;
1791
1792	seq_printf(sf, "%u\n", val);
1793	return 0;
1794	}
1795
1796	static int cfq_print_leaf_weight(struct seq_file *sf, void *v)
1797	{
1798	struct blkcg *blkcg = css_to_blkcg(seq_css(sf));
1799	struct cfq_group_data *cgd = blkcg_to_cfqgd(blkcg);
1800	unsigned int val = 0;
1801
1802	if (cgd)
1803	val = cgd->leaf_weight;
1804
1805	seq_printf(sf, "%u\n", val);
1806	return 0;
1807	}
1808
1809	static int cfq_print_group_idle(struct seq_file *sf, void *v)
1810	{
1811	struct blkcg *blkcg = css_to_blkcg(seq_css(sf));
1812	struct cfq_group_data *cgd = blkcg_to_cfqgd(blkcg);
1813	u64 val = 0;
1814
1815	if (cgd)
1816	val = cgd->group_idle;
1817
1818	seq_printf(sf, "%llu\n", div_u64(val, NSEC_PER_USEC));
1819	return 0;
1820	}
1821
1822	static ssize_t __cfqg_set_weight_device(struct kernfs_open_file *of,
1823	char *buf, size_t nbytes, loff_t off,
1824	bool on_dfl, bool is_leaf_weight)
1825	{
1826	unsigned int min = on_dfl ? CGROUP_WEIGHT_MIN : CFQ_WEIGHT_LEGACY_MIN;
1827	unsigned int max = on_dfl ? CGROUP_WEIGHT_MAX : CFQ_WEIGHT_LEGACY_MAX;
1828	struct blkcg *blkcg = css_to_blkcg(of_css(of));
1829	struct blkg_conf_ctx ctx;
1830	struct cfq_group *cfqg;
1831	struct cfq_group_data *cfqgd;
1832	int ret;
1833	u64 v;
1834
1835	ret = blkg_conf_prep(blkcg, &blkcg_policy_cfq, buf, &ctx);
1836	if (ret)
1837	return ret;
1838
1839	if (sscanf(ctx.body, "%llu", &v) == 1) {
1840	/* require "default" on dfl */
1841	ret = -ERANGE;
1842	if (!v && on_dfl)
1843	goto out_finish;
1844	} else if (!strcmp(strim(ctx.body), "default")) {
1845	v = 0;
1846	} else {
1847	ret = -EINVAL;
1848	goto out_finish;
1849	}
1850
1851	cfqg = blkg_to_cfqg(ctx.blkg);
1852	cfqgd = blkcg_to_cfqgd(blkcg);
1853
1854	ret = -ERANGE;
1855	if (!v || (v >= min && v <= max)) {
1856	if (!is_leaf_weight) {
1857	cfqg->dev_weight = v;
1858	cfqg->new_weight = v ?: cfqgd->weight;
1859	} else {
1860	cfqg->dev_leaf_weight = v;
1861	cfqg->new_leaf_weight = v ?: cfqgd->leaf_weight;
1862	}
1863	ret = 0;
1864	}
1865	out_finish:
1866	blkg_conf_finish(&ctx);
1867	return ret ?: nbytes;
1868	}
1869
1870	static ssize_t cfqg_set_weight_device(struct kernfs_open_file *of,
1871	char *buf, size_t nbytes, loff_t off)
1872	{
1873	return __cfqg_set_weight_device(of, buf, nbytes, off, false, false);
1874	}
1875
1876	static ssize_t cfqg_set_leaf_weight_device(struct kernfs_open_file *of,
1877	char *buf, size_t nbytes, loff_t off)
1878	{
1879	return __cfqg_set_weight_device(of, buf, nbytes, off, false, true);
1880	}
1881
1882	static int __cfq_set_weight(struct cgroup_subsys_state *css, u64 val,
1883	bool on_dfl, bool reset_dev, bool is_leaf_weight)
1884	{
1885	unsigned int min = on_dfl ? CGROUP_WEIGHT_MIN : CFQ_WEIGHT_LEGACY_MIN;
1886	unsigned int max = on_dfl ? CGROUP_WEIGHT_MAX : CFQ_WEIGHT_LEGACY_MAX;
1887	struct blkcg *blkcg = css_to_blkcg(css);
1888	struct blkcg_gq *blkg;
1889	struct cfq_group_data *cfqgd;
1890	int ret = 0;
1891
1892	if (val < min || val > max)
1893	return -ERANGE;
1894
1895	spin_lock_irq(&blkcg->lock);
1896	cfqgd = blkcg_to_cfqgd(blkcg);
1897	if (!cfqgd) {
1898	ret = -EINVAL;
1899	goto out;
1900	}
1901
1902	if (!is_leaf_weight)
1903	cfqgd->weight = val;
1904	else
1905	cfqgd->leaf_weight = val;
1906
1907	hlist_for_each_entry(blkg, &blkcg->blkg_list, blkcg_node) {
1908	struct cfq_group *cfqg = blkg_to_cfqg(blkg);
1909
1910	if (!cfqg)
1911	continue;
1912
1913	if (!is_leaf_weight) {
1914	if (reset_dev)
1915	cfqg->dev_weight = 0;
1916	if (!cfqg->dev_weight)
1917	cfqg->new_weight = cfqgd->weight;
1918	} else {
1919	if (reset_dev)
1920	cfqg->dev_leaf_weight = 0;
1921	if (!cfqg->dev_leaf_weight)
1922	cfqg->new_leaf_weight = cfqgd->leaf_weight;
1923	}
1924	}
1925
1926	out:
1927	spin_unlock_irq(&blkcg->lock);
1928	return ret;
1929	}
1930
1931	static int cfq_set_weight(struct cgroup_subsys_state *css, struct cftype *cft,
1932	u64 val)
1933	{
1934	return __cfq_set_weight(css, val, false, false, false);
1935	}
1936
1937	static int cfq_set_leaf_weight(struct cgroup_subsys_state *css,
1938	struct cftype *cft, u64 val)
1939	{
1940	return __cfq_set_weight(css, val, false, false, true);
1941	}
1942
1943	static int cfq_set_group_idle(struct cgroup_subsys_state *css,
1944	struct cftype *cft, u64 val)
1945	{
1946	struct blkcg *blkcg = css_to_blkcg(css);
1947	struct cfq_group_data *cfqgd;
1948	struct blkcg_gq *blkg;
1949	int ret = 0;
1950
1951	spin_lock_irq(&blkcg->lock);
1952	cfqgd = blkcg_to_cfqgd(blkcg);
1953	if (!cfqgd) {
1954	ret = -EINVAL;
1955	goto out;
1956	}
1957
1958	cfqgd->group_idle = val * NSEC_PER_USEC;
1959
1960	hlist_for_each_entry(blkg, &blkcg->blkg_list, blkcg_node) {
1961	struct cfq_group *cfqg = blkg_to_cfqg(blkg);
1962
1963	if (!cfqg)
1964	continue;
1965
1966	cfqg->group_idle = cfqgd->group_idle;
1967	}
1968
1969	out:
1970	spin_unlock_irq(&blkcg->lock);
1971	return ret;
1972	}
1973
1974	static int cfqg_print_stat(struct seq_file *sf, void *v)
1975	{
1976	blkcg_print_blkgs(sf, css_to_blkcg(seq_css(sf)), blkg_prfill_stat,
1977	&blkcg_policy_cfq, seq_cft(sf)->private, false);
1978	return 0;
1979	}
1980
1981	static int cfqg_print_rwstat(struct seq_file *sf, void *v)
1982	{
1983	blkcg_print_blkgs(sf, css_to_blkcg(seq_css(sf)), blkg_prfill_rwstat,
1984	&blkcg_policy_cfq, seq_cft(sf)->private, true);
1985	return 0;
1986	}
1987
1988	static u64 cfqg_prfill_stat_recursive(struct seq_file *sf,
1989	struct blkg_policy_data *pd, int off)
1990	{
1991	u64 sum = blkg_stat_recursive_sum(pd_to_blkg(pd),
1992	&blkcg_policy_cfq, off);
1993	return __blkg_prfill_u64(sf, pd, sum);
1994	}
1995
1996	static u64 cfqg_prfill_rwstat_recursive(struct seq_file *sf,
1997	struct blkg_policy_data *pd, int off)
1998	{
1999	struct blkg_rwstat sum = blkg_rwstat_recursive_sum(pd_to_blkg(pd),
2000	&blkcg_policy_cfq, off);
2001	return __blkg_prfill_rwstat(sf, pd, &sum);
2002	}
2003
2004	static int cfqg_print_stat_recursive(struct seq_file *sf, void *v)
2005	{
2006	blkcg_print_blkgs(sf, css_to_blkcg(seq_css(sf)),
2007	cfqg_prfill_stat_recursive, &blkcg_policy_cfq,
2008	seq_cft(sf)->private, false);
2009	return 0;
2010	}
2011
2012	static int cfqg_print_rwstat_recursive(struct seq_file *sf, void *v)
2013	{
2014	blkcg_print_blkgs(sf, css_to_blkcg(seq_css(sf)),
2015	cfqg_prfill_rwstat_recursive, &blkcg_policy_cfq,
2016	seq_cft(sf)->private, true);
2017	return 0;
2018	}
2019
2020	static u64 cfqg_prfill_sectors(struct seq_file *sf, struct blkg_policy_data *pd,
2021	int off)
2022	{
2023	u64 sum = blkg_rwstat_total(&pd->blkg->stat_bytes);
2024
2025	return __blkg_prfill_u64(sf, pd, sum >> 9);
2026	}
2027
2028	static int cfqg_print_stat_sectors(struct seq_file *sf, void *v)
2029	{
2030	blkcg_print_blkgs(sf, css_to_blkcg(seq_css(sf)),
2031	cfqg_prfill_sectors, &blkcg_policy_cfq, 0, false);
2032	return 0;
2033	}
2034
2035	static u64 cfqg_prfill_sectors_recursive(struct seq_file *sf,
2036	struct blkg_policy_data *pd, int off)
2037	{
2038	struct blkg_rwstat tmp = blkg_rwstat_recursive_sum(pd->blkg, NULL,
2039	offsetof(struct blkcg_gq, stat_bytes));
2040	u64 sum = atomic64_read(&tmp.aux_cnt[BLKG_RWSTAT_READ]) +
2041	atomic64_read(&tmp.aux_cnt[BLKG_RWSTAT_WRITE]);
2042
2043	return __blkg_prfill_u64(sf, pd, sum >> 9);
2044	}
2045
2046	static int cfqg_print_stat_sectors_recursive(struct seq_file *sf, void *v)
2047	{
2048	blkcg_print_blkgs(sf, css_to_blkcg(seq_css(sf)),
2049	cfqg_prfill_sectors_recursive, &blkcg_policy_cfq, 0,
2050	false);
2051	return 0;
2052	}
2053
2054	#ifdef CONFIG_DEBUG_BLK_CGROUP
2055	static u64 cfqg_prfill_avg_queue_size(struct seq_file *sf,
2056	struct blkg_policy_data *pd, int off)
2057	{
2058	struct cfq_group *cfqg = pd_to_cfqg(pd);
2059	u64 samples = blkg_stat_read(&cfqg->stats.avg_queue_size_samples);
2060	u64 v = 0;
2061
2062	if (samples) {
2063	v = blkg_stat_read(&cfqg->stats.avg_queue_size_sum);
2064	v = div64_u64(v, samples);
2065	}
2066	__blkg_prfill_u64(sf, pd, v);
2067	return 0;
2068	}
2069
2070	/* print avg_queue_size */
2071	static int cfqg_print_avg_queue_size(struct seq_file *sf, void *v)
2072	{
2073	blkcg_print_blkgs(sf, css_to_blkcg(seq_css(sf)),
2074	cfqg_prfill_avg_queue_size, &blkcg_policy_cfq,
2075	0, false);
2076	return 0;
2077	}
2078	#endif /* CONFIG_DEBUG_BLK_CGROUP */
2079
2080	static struct cftype cfq_blkcg_legacy_files[] = {
2081	/* on root, weight is mapped to leaf_weight */
2082	{
2083	.name = "weight_device",
2084	.flags = CFTYPE_ONLY_ON_ROOT,
2085	.seq_show = cfqg_print_leaf_weight_device,
2086	.write = cfqg_set_leaf_weight_device,
2087	},
2088	{
2089	.name = "weight",
2090	.flags = CFTYPE_ONLY_ON_ROOT,
2091	.seq_show = cfq_print_leaf_weight,
2092	.write_u64 = cfq_set_leaf_weight,
2093	},
2094
2095	/* no such mapping necessary for !roots */
2096	{
2097	.name = "weight_device",
2098	.flags = CFTYPE_NOT_ON_ROOT,
2099	.seq_show = cfqg_print_weight_device,
2100	.write = cfqg_set_weight_device,
2101	},
2102	{
2103	.name = "weight",
2104	.flags = CFTYPE_NOT_ON_ROOT,
2105	.seq_show = cfq_print_weight,
2106	.write_u64 = cfq_set_weight,
2107	},
2108
2109	{
2110	.name = "leaf_weight_device",
2111	.seq_show = cfqg_print_leaf_weight_device,
2112	.write = cfqg_set_leaf_weight_device,
2113	},
2114	{
2115	.name = "leaf_weight",
2116	.seq_show = cfq_print_leaf_weight,
2117	.write_u64 = cfq_set_leaf_weight,
2118	},
2119	{
2120	.name = "group_idle",
2121	.seq_show = cfq_print_group_idle,
2122	.write_u64 = cfq_set_group_idle,
2123	},
2124
2125	/* statistics, covers only the tasks in the cfqg */
2126	{
2127	.name = "time",
2128	.private = offsetof(struct cfq_group, stats.time),
2129	.seq_show = cfqg_print_stat,
2130	},
2131	{
2132	.name = "sectors",
2133	.seq_show = cfqg_print_stat_sectors,
2134	},
2135	{
2136	.name = "io_service_bytes",
2137	.private = (unsigned long)&blkcg_policy_cfq,
2138	.seq_show = blkg_print_stat_bytes,
2139	},
2140	{
2141	.name = "io_serviced",
2142	.private = (unsigned long)&blkcg_policy_cfq,
2143	.seq_show = blkg_print_stat_ios,
2144	},
2145	{
2146	.name = "io_service_time",
2147	.private = offsetof(struct cfq_group, stats.service_time),
2148	.seq_show = cfqg_print_rwstat,
2149	},
2150	{
2151	.name = "io_wait_time",
2152	.private = offsetof(struct cfq_group, stats.wait_time),
2153	.seq_show = cfqg_print_rwstat,
2154	},
2155	{
2156	.name = "io_merged",
2157	.private = offsetof(struct cfq_group, stats.merged),
2158	.seq_show = cfqg_print_rwstat,
2159	},
2160	{
2161	.name = "io_queued",
2162	.private = offsetof(struct cfq_group, stats.queued),
2163	.seq_show = cfqg_print_rwstat,
2164	},
2165
2166	/* the same statictics which cover the cfqg and its descendants */
2167	{
2168	.name = "time_recursive",
2169	.private = offsetof(struct cfq_group, stats.time),
2170	.seq_show = cfqg_print_stat_recursive,
2171	},
2172	{
2173	.name = "sectors_recursive",
2174	.seq_show = cfqg_print_stat_sectors_recursive,
2175	},
2176	{
2177	.name = "io_service_bytes_recursive",
2178	.private = (unsigned long)&blkcg_policy_cfq,
2179	.seq_show = blkg_print_stat_bytes_recursive,
2180	},
2181	{
2182	.name = "io_serviced_recursive",
2183	.private = (unsigned long)&blkcg_policy_cfq,
2184	.seq_show = blkg_print_stat_ios_recursive,
2185	},
2186	{
2187	.name = "io_service_time_recursive",
2188	.private = offsetof(struct cfq_group, stats.service_time),
2189	.seq_show = cfqg_print_rwstat_recursive,
2190	},
2191	{
2192	.name = "io_wait_time_recursive",
2193	.private = offsetof(struct cfq_group, stats.wait_time),
2194	.seq_show = cfqg_print_rwstat_recursive,
2195	},
2196	{
2197	.name = "io_merged_recursive",
2198	.private = offsetof(struct cfq_group, stats.merged),
2199	.seq_show = cfqg_print_rwstat_recursive,
2200	},
2201	{
2202	.name = "io_queued_recursive",
2203	.private = offsetof(struct cfq_group, stats.queued),
2204	.seq_show = cfqg_print_rwstat_recursive,
2205	},
2206	#ifdef CONFIG_DEBUG_BLK_CGROUP
2207	{
2208	.name = "avg_queue_size",
2209	.seq_show = cfqg_print_avg_queue_size,
2210	},
2211	{
2212	.name = "group_wait_time",
2213	.private = offsetof(struct cfq_group, stats.group_wait_time),
2214	.seq_show = cfqg_print_stat,
2215	},
2216	{
2217	.name = "idle_time",
2218	.private = offsetof(struct cfq_group, stats.idle_time),
2219	.seq_show = cfqg_print_stat,
2220	},
2221	{
2222	.name = "empty_time",
2223	.private = offsetof(struct cfq_group, stats.empty_time),
2224	.seq_show = cfqg_print_stat,
2225	},
2226	{
2227	.name = "dequeue",
2228	.private = offsetof(struct cfq_group, stats.dequeue),
2229	.seq_show = cfqg_print_stat,
2230	},
2231	{
2232	.name = "unaccounted_time",
2233	.private = offsetof(struct cfq_group, stats.unaccounted_time),
2234	.seq_show = cfqg_print_stat,
2235	},
2236	#endif /* CONFIG_DEBUG_BLK_CGROUP */
2237	{ } /* terminate */
2238	};
2239
2240	static int cfq_print_weight_on_dfl(struct seq_file *sf, void *v)
2241	{
2242	struct blkcg *blkcg = css_to_blkcg(seq_css(sf));
2243	struct cfq_group_data *cgd = blkcg_to_cfqgd(blkcg);
2244
2245	seq_printf(sf, "default %u\n", cgd->weight);
2246	blkcg_print_blkgs(sf, blkcg, cfqg_prfill_weight_device,
2247	&blkcg_policy_cfq, 0, false);
2248	return 0;
2249	}
2250
2251	static ssize_t cfq_set_weight_on_dfl(struct kernfs_open_file *of,
2252	char *buf, size_t nbytes, loff_t off)
2253	{
2254	char *endp;
2255	int ret;
2256	u64 v;
2257
2258	buf = strim(buf);
2259
2260	/* "WEIGHT" or "default WEIGHT" sets the default weight */
2261	v = simple_strtoull(buf, &endp, 0);
2262	if (*endp == '\0' || sscanf(buf, "default %llu", &v) == 1) {
2263	ret = __cfq_set_weight(of_css(of), v, true, false, false);
2264	return ret ?: nbytes;
2265	}
2266
2267	/* "MAJ:MIN WEIGHT" */
2268	return __cfqg_set_weight_device(of, buf, nbytes, off, true, false);
2269	}
2270
2271	static struct cftype cfq_blkcg_files[] = {
2272	{
2273	.name = "weight",
2274	.flags = CFTYPE_NOT_ON_ROOT,
2275	.seq_show = cfq_print_weight_on_dfl,
2276	.write = cfq_set_weight_on_dfl,
2277	},
2278	{ } /* terminate */
2279	};
2280
2281	#else /* GROUP_IOSCHED */
2282	static struct cfq_group *cfq_lookup_cfqg(struct cfq_data *cfqd,
2283	struct blkcg *blkcg)
2284	{
2285	return cfqd->root_group;
2286	}
2287
2288	static inline void
2289	cfq_link_cfqq_cfqg(struct cfq_queue *cfqq, struct cfq_group *cfqg) {
2290	cfqq->cfqg = cfqg;
2291	}
2292
2293	#endif /* GROUP_IOSCHED */
2294
2295	/*
2296	* The cfqd->service_trees holds all pending cfq_queue's that have
2297	* requests waiting to be processed. It is sorted in the order that
2298	* we will service the queues.
2299	*/
2300	static void cfq_service_tree_add(struct cfq_data *cfqd, struct cfq_queue *cfqq,
2301	bool add_front)
2302	{
2303	struct rb_node **p, *parent;
2304	struct cfq_queue *__cfqq;
2305	u64 rb_key;
2306	struct cfq_rb_root *st;
2307	int left;
2308	int new_cfqq = 1;
2309	u64 now = ktime_get_ns();
2310
2311	st = st_for(cfqq->cfqg, cfqq_class(cfqq), cfqq_type(cfqq));
2312	if (cfq_class_idle(cfqq)) {
2313	rb_key = CFQ_IDLE_DELAY;
2314	parent = rb_last(&st->rb);
2315	if (parent && parent != &cfqq->rb_node) {
2316	__cfqq = rb_entry(parent, struct cfq_queue, rb_node);
2317	rb_key += __cfqq->rb_key;
2318	} else
2319	rb_key += now;
2320	} else if (!add_front) {
2321	/*
2322	* Get our rb key offset. Subtract any residual slice
2323	* value carried from last service. A negative resid
2324	* count indicates slice overrun, and this should position
2325	* the next service time further away in the tree.
2326	*/
2327	rb_key = cfq_slice_offset(cfqd, cfqq) + now;
2328	rb_key -= cfqq->slice_resid;
2329	cfqq->slice_resid = 0;
2330	} else {
2331	rb_key = -NSEC_PER_SEC;
2332	__cfqq = cfq_rb_first(st);
2333	rb_key += __cfqq ? __cfqq->rb_key : now;
2334	}
2335
2336	if (!RB_EMPTY_NODE(&cfqq->rb_node)) {
2337	new_cfqq = 0;
2338	/*
2339	* same position, nothing more to do
2340	*/
2341	if (rb_key == cfqq->rb_key && cfqq->service_tree == st)
2342	return;
2343
2344	cfq_rb_erase(&cfqq->rb_node, cfqq->service_tree);
2345	cfqq->service_tree = NULL;
2346	}
2347
2348	left = 1;
2349	parent = NULL;
2350	cfqq->service_tree = st;
2351	p = &st->rb.rb_node;
2352	while (*p) {
2353	parent = *p;
2354	__cfqq = rb_entry(parent, struct cfq_queue, rb_node);
2355
2356	/*
2357	* sort by key, that represents service time.
2358	*/
2359	if (rb_key < __cfqq->rb_key)
2360	p = &parent->rb_left;
2361	else {
2362	p = &parent->rb_right;
2363	left = 0;
2364	}
2365	}
2366
2367	if (left)
2368	st->left = &cfqq->rb_node;
2369
2370	cfqq->rb_key = rb_key;
2371	rb_link_node(&cfqq->rb_node, parent, p);
2372	rb_insert_color(&cfqq->rb_node, &st->rb);
2373	st->count++;
2374	if (add_front || !new_cfqq)
2375	return;
2376	cfq_group_notify_queue_add(cfqd, cfqq->cfqg);
2377	}
2378
2379	static struct cfq_queue *
2380	cfq_prio_tree_lookup(struct cfq_data *cfqd, struct rb_root *root,
2381	sector_t sector, struct rb_node **ret_parent,
2382	struct rb_node ***rb_link)
2383	{
2384	struct rb_node **p, *parent;
2385	struct cfq_queue *cfqq = NULL;
2386
2387	parent = NULL;
2388	p = &root->rb_node;
2389	while (*p) {
2390	struct rb_node **n;
2391
2392	parent = *p;
2393	cfqq = rb_entry(parent, struct cfq_queue, p_node);
2394
2395	/*
2396	* Sort strictly based on sector. Smallest to the left,
2397	* largest to the right.
2398	*/
2399	if (sector > blk_rq_pos(cfqq->next_rq))
2400	n = &(*p)->rb_right;
2401	else if (sector < blk_rq_pos(cfqq->next_rq))
2402	n = &(*p)->rb_left;
2403	else
2404	break;
2405	p = n;
2406	cfqq = NULL;
2407	}
2408
2409	*ret_parent = parent;
2410	if (rb_link)
2411	*rb_link = p;
2412	return cfqq;
2413	}
2414
2415	static void cfq_prio_tree_add(struct cfq_data *cfqd, struct cfq_queue *cfqq)
2416	{
2417	struct rb_node **p, *parent;
2418	struct cfq_queue *__cfqq;
2419
2420	if (cfqq->p_root) {
2421	rb_erase(&cfqq->p_node, cfqq->p_root);
2422	cfqq->p_root = NULL;
2423	}
2424
2425	if (cfq_class_idle(cfqq))
2426	return;
2427	if (!cfqq->next_rq)
2428	return;
2429
2430	cfqq->p_root = &cfqd->prio_trees[cfqq->org_ioprio];
2431	__cfqq = cfq_prio_tree_lookup(cfqd, cfqq->p_root,
2432	blk_rq_pos(cfqq->next_rq), &parent, &p);
2433	if (!__cfqq) {
2434	rb_link_node(&cfqq->p_node, parent, p);
2435	rb_insert_color(&cfqq->p_node, cfqq->p_root);
2436	} else
2437	cfqq->p_root = NULL;
2438	}
2439
2440	/*
2441	* Update cfqq's position in the service tree.
2442	*/
2443	static void cfq_resort_rr_list(struct cfq_data *cfqd, struct cfq_queue *cfqq)
2444	{
2445	/*
2446	* Resorting requires the cfqq to be on the RR list already.
2447	*/
2448	if (cfq_cfqq_on_rr(cfqq)) {
2449	cfq_service_tree_add(cfqd, cfqq, 0);
2450	cfq_prio_tree_add(cfqd, cfqq);
2451	}
2452	}
2453
2454	/*
2455	* add to busy list of queues for service, trying to be fair in ordering
2456	* the pending list according to last request service
2457	*/
2458	static void cfq_add_cfqq_rr(struct cfq_data *cfqd, struct cfq_queue *cfqq)
2459	{
2460	cfq_log_cfqq(cfqd, cfqq, "add_to_rr");
2461	BUG_ON(cfq_cfqq_on_rr(cfqq));
2462	cfq_mark_cfqq_on_rr(cfqq);
2463	cfqd->busy_queues++;
2464	if (cfq_cfqq_sync(cfqq))
2465	cfqd->busy_sync_queues++;
2466
2467	cfq_resort_rr_list(cfqd, cfqq);
2468	}
2469
2470	/*
2471	* Called when the cfqq no longer has requests pending, remove it from
2472	* the service tree.
2473	*/
2474	static void cfq_del_cfqq_rr(struct cfq_data *cfqd, struct cfq_queue *cfqq)
2475	{
2476	cfq_log_cfqq(cfqd, cfqq, "del_from_rr");
2477	BUG_ON(!cfq_cfqq_on_rr(cfqq));
2478	cfq_clear_cfqq_on_rr(cfqq);
2479
2480	if (!RB_EMPTY_NODE(&cfqq->rb_node)) {
2481	cfq_rb_erase(&cfqq->rb_node, cfqq->service_tree);
2482	cfqq->service_tree = NULL;
2483	}
2484	if (cfqq->p_root) {
2485	rb_erase(&cfqq->p_node, cfqq->p_root);
2486	cfqq->p_root = NULL;
2487	}
2488
2489	cfq_group_notify_queue_del(cfqd, cfqq->cfqg);
2490	BUG_ON(!cfqd->busy_queues);
2491	cfqd->busy_queues--;
2492	if (cfq_cfqq_sync(cfqq))
2493	cfqd->busy_sync_queues--;
2494	}
2495
2496	/*
2497	* rb tree support functions
2498	*/
2499	static void cfq_del_rq_rb(struct request *rq)
2500	{
2501	struct cfq_queue *cfqq = RQ_CFQQ(rq);
2502	const int sync = rq_is_sync(rq);
2503
2504	BUG_ON(!cfqq->queued[sync]);
2505	cfqq->queued[sync]--;
2506
2507	elv_rb_del(&cfqq->sort_list, rq);
2508
2509	if (cfq_cfqq_on_rr(cfqq) && RB_EMPTY_ROOT(&cfqq->sort_list)) {
2510	/*
2511	* Queue will be deleted from service tree when we actually
2512	* expire it later. Right now just remove it from prio tree
2513	* as it is empty.
2514	*/
2515	if (cfqq->p_root) {
2516	rb_erase(&cfqq->p_node, cfqq->p_root);
2517	cfqq->p_root = NULL;
2518	}
2519	}
2520	}
2521
2522	static void cfq_add_rq_rb(struct request *rq)
2523	{
2524	struct cfq_queue *cfqq = RQ_CFQQ(rq);
2525	struct cfq_data *cfqd = cfqq->cfqd;
2526	struct request *prev;
2527
2528	cfqq->queued[rq_is_sync(rq)]++;
2529
2530	elv_rb_add(&cfqq->sort_list, rq);
2531
2532	if (!cfq_cfqq_on_rr(cfqq))
2533	cfq_add_cfqq_rr(cfqd, cfqq);
2534
2535	/*
2536	* check if this request is a better next-serve candidate
2537	*/
2538	prev = cfqq->next_rq;
2539	cfqq->next_rq = cfq_choose_req(cfqd, cfqq->next_rq, rq, cfqd->last_position);
2540
2541	/*
2542	* adjust priority tree position, if ->next_rq changes
2543	*/
2544	if (prev != cfqq->next_rq)
2545	cfq_prio_tree_add(cfqd, cfqq);
2546
2547	BUG_ON(!cfqq->next_rq);
2548	}
2549
2550	static void cfq_reposition_rq_rb(struct cfq_queue *cfqq, struct request *rq)
2551	{
2552	elv_rb_del(&cfqq->sort_list, rq);
2553	cfqq->queued[rq_is_sync(rq)]--;
2554	cfqg_stats_update_io_remove(RQ_CFQG(rq), req_op(rq), rq->cmd_flags);
2555	cfq_add_rq_rb(rq);
2556	cfqg_stats_update_io_add(RQ_CFQG(rq), cfqq->cfqd->serving_group,
2557	req_op(rq), rq->cmd_flags);
2558	}
2559
2560	static struct request *
2561	cfq_find_rq_fmerge(struct cfq_data *cfqd, struct bio *bio)
2562	{
2563	struct task_struct *tsk = current;
2564	struct cfq_io_cq *cic;
2565	struct cfq_queue *cfqq;
2566
2567	cic = cfq_cic_lookup(cfqd, tsk->io_context);
2568	if (!cic)
2569	return NULL;
2570
2571	cfqq = cic_to_cfqq(cic, cfq_bio_sync(bio));
2572	if (cfqq)
2573	return elv_rb_find(&cfqq->sort_list, bio_end_sector(bio));
2574
2575	return NULL;
2576	}
2577
2578	static void cfq_activate_request(struct request_queue *q, struct request *rq)
2579	{
2580	struct cfq_data *cfqd = q->elevator->elevator_data;
2581
2582	cfqd->rq_in_driver++;
2583	cfq_log_cfqq(cfqd, RQ_CFQQ(rq), "activate rq, drv=%d",
2584	cfqd->rq_in_driver);
2585
2586	cfqd->last_position = blk_rq_pos(rq) + blk_rq_sectors(rq);
2587	}
2588
2589	static void cfq_deactivate_request(struct request_queue *q, struct request *rq)
2590	{
2591	struct cfq_data *cfqd = q->elevator->elevator_data;
2592
2593	WARN_ON(!cfqd->rq_in_driver);
2594	cfqd->rq_in_driver--;
2595	cfq_log_cfqq(cfqd, RQ_CFQQ(rq), "deactivate rq, drv=%d",
2596	cfqd->rq_in_driver);
2597	}
2598
2599	static void cfq_remove_request(struct request *rq)
2600	{
2601	struct cfq_queue *cfqq = RQ_CFQQ(rq);
2602
2603	if (cfqq->next_rq == rq)
2604	cfqq->next_rq = cfq_find_next_rq(cfqq->cfqd, cfqq, rq);
2605
2606	list_del_init(&rq->queuelist);
2607	cfq_del_rq_rb(rq);
2608
2609	cfqq->cfqd->rq_queued--;
2610	cfqg_stats_update_io_remove(RQ_CFQG(rq), req_op(rq), rq->cmd_flags);
2611	if (rq->cmd_flags & REQ_PRIO) {
2612	WARN_ON(!cfqq->prio_pending);
2613	cfqq->prio_pending--;
2614	}
2615	}
2616
2617	static int cfq_merge(struct request_queue *q, struct request **req,
2618	struct bio *bio)
2619	{
2620	struct cfq_data *cfqd = q->elevator->elevator_data;
2621	struct request *__rq;
2622
2623	__rq = cfq_find_rq_fmerge(cfqd, bio);
2624	if (__rq && elv_bio_merge_ok(__rq, bio)) {
2625	*req = __rq;
2626	return ELEVATOR_FRONT_MERGE;
2627	}
2628
2629	return ELEVATOR_NO_MERGE;
2630	}
2631
2632	static void cfq_merged_request(struct request_queue *q, struct request *req,
2633	int type)
2634	{
2635	if (type == ELEVATOR_FRONT_MERGE) {
2636	struct cfq_queue *cfqq = RQ_CFQQ(req);
2637
2638	cfq_reposition_rq_rb(cfqq, req);
2639	}
2640	}
2641
2642	static void cfq_bio_merged(struct request_queue *q, struct request *req,
2643	struct bio *bio)
2644	{
2645	cfqg_stats_update_io_merged(RQ_CFQG(req), bio_op(bio), bio->bi_opf);
2646	}
2647
2648	static void
2649	cfq_merged_requests(struct request_queue *q, struct request *rq,
2650	struct request *next)
2651	{
2652	struct cfq_queue *cfqq = RQ_CFQQ(rq);
2653	struct cfq_data *cfqd = q->elevator->elevator_data;
2654
2655	/*
2656	* reposition in fifo if next is older than rq
2657	*/
2658	if (!list_empty(&rq->queuelist) && !list_empty(&next->queuelist) &&
2659	next->fifo_time < rq->fifo_time &&
2660	cfqq == RQ_CFQQ(next)) {
2661	list_move(&rq->queuelist, &next->queuelist);
2662	rq->fifo_time = next->fifo_time;
2663	}
2664
2665	if (cfqq->next_rq == next)
2666	cfqq->next_rq = rq;
2667	cfq_remove_request(next);
2668	cfqg_stats_update_io_merged(RQ_CFQG(rq), req_op(next), next->cmd_flags);
2669
2670	cfqq = RQ_CFQQ(next);
2671	/*
2672	* all requests of this queue are merged to other queues, delete it
2673	* from the service tree. If it's the active_queue,
2674	* cfq_dispatch_requests() will choose to expire it or do idle
2675	*/
2676	if (cfq_cfqq_on_rr(cfqq) && RB_EMPTY_ROOT(&cfqq->sort_list) &&
2677	cfqq != cfqd->active_queue)
2678	cfq_del_cfqq_rr(cfqd, cfqq);
2679	}
2680
2681	static int cfq_allow_bio_merge(struct request_queue *q, struct request *rq,
2682	struct bio *bio)
2683	{
2684	struct cfq_data *cfqd = q->elevator->elevator_data;
2685	struct cfq_io_cq *cic;
2686	struct cfq_queue *cfqq;
2687
2688	/*
2689	* Disallow merge of a sync bio into an async request.
2690	*/
2691	if (cfq_bio_sync(bio) && !rq_is_sync(rq))
2692	return false;
2693
2694	/*
2695	* Lookup the cfqq that this bio will be queued with and allow
2696	* merge only if rq is queued there.
2697	*/
2698	cic = cfq_cic_lookup(cfqd, current->io_context);
2699	if (!cic)
2700	return false;
2701
2702	cfqq = cic_to_cfqq(cic, cfq_bio_sync(bio));
2703	return cfqq == RQ_CFQQ(rq);
2704	}
2705
2706	static int cfq_allow_rq_merge(struct request_queue *q, struct request *rq,
2707	struct request *next)
2708	{
2709	return RQ_CFQQ(rq) == RQ_CFQQ(next);
2710	}
2711
2712	static inline void cfq_del_timer(struct cfq_data *cfqd, struct cfq_queue *cfqq)
2713	{
2714	hrtimer_try_to_cancel(&cfqd->idle_slice_timer);
2715	cfqg_stats_update_idle_time(cfqq->cfqg);
2716	}
2717
2718	static void __cfq_set_active_queue(struct cfq_data *cfqd,
2719	struct cfq_queue *cfqq)
2720	{
2721	if (cfqq) {
2722	cfq_log_cfqq(cfqd, cfqq, "set_active wl_class:%d wl_type:%d",
2723	cfqd->serving_wl_class, cfqd->serving_wl_type);
2724	cfqg_stats_update_avg_queue_size(cfqq->cfqg);
2725	cfqq->slice_start = 0;
2726	cfqq->dispatch_start = ktime_get_ns();
2727	cfqq->allocated_slice = 0;
2728	cfqq->slice_end = 0;
2729	cfqq->slice_dispatch = 0;
2730	cfqq->nr_sectors = 0;
2731
2732	cfq_clear_cfqq_wait_request(cfqq);
2733	cfq_clear_cfqq_must_dispatch(cfqq);
2734	cfq_clear_cfqq_must_alloc_slice(cfqq);
2735	cfq_clear_cfqq_fifo_expire(cfqq);
2736	cfq_mark_cfqq_slice_new(cfqq);
2737
2738	cfq_del_timer(cfqd, cfqq);
2739	}
2740
2741	cfqd->active_queue = cfqq;
2742	}
2743
2744	/*
2745	* current cfqq expired its slice (or was too idle), select new one
2746	*/
2747	static void
2748	__cfq_slice_expired(struct cfq_data *cfqd, struct cfq_queue *cfqq,
2749	bool timed_out)
2750	{
2751	cfq_log_cfqq(cfqd, cfqq, "slice expired t=%d", timed_out);
2752
2753	if (cfq_cfqq_wait_request(cfqq))
2754	cfq_del_timer(cfqd, cfqq);
2755
2756	cfq_clear_cfqq_wait_request(cfqq);
2757	cfq_clear_cfqq_wait_busy(cfqq);
2758
2759	/*
2760	* If this cfqq is shared between multiple processes, check to
2761	* make sure that those processes are still issuing I/Os within
2762	* the mean seek distance. If not, it may be time to break the
2763	* queues apart again.
2764	*/
2765	if (cfq_cfqq_coop(cfqq) && CFQQ_SEEKY(cfqq))
2766	cfq_mark_cfqq_split_coop(cfqq);
2767
2768	/*
2769	* store what was left of this slice, if the queue idled/timed out
2770	*/
2771	if (timed_out) {
2772	if (cfq_cfqq_slice_new(cfqq))
2773	cfqq->slice_resid = cfq_scaled_cfqq_slice(cfqd, cfqq);
2774	else
2775	cfqq->slice_resid = cfqq->slice_end - ktime_get_ns();
2776	cfq_log_cfqq(cfqd, cfqq, "resid=%lld", cfqq->slice_resid);
2777	}
2778
2779	cfq_group_served(cfqd, cfqq->cfqg, cfqq);
2780
2781	if (cfq_cfqq_on_rr(cfqq) && RB_EMPTY_ROOT(&cfqq->sort_list))
2782	cfq_del_cfqq_rr(cfqd, cfqq);
2783
2784	cfq_resort_rr_list(cfqd, cfqq);
2785
2786	if (cfqq == cfqd->active_queue)
2787	cfqd->active_queue = NULL;
2788
2789	if (cfqd->active_cic) {
2790	put_io_context(cfqd->active_cic->icq.ioc);
2791	cfqd->active_cic = NULL;
2792	}
2793	}
2794
2795	static inline void cfq_slice_expired(struct cfq_data *cfqd, bool timed_out)
2796	{
2797	struct cfq_queue *cfqq = cfqd->active_queue;
2798
2799	if (cfqq)
2800	__cfq_slice_expired(cfqd, cfqq, timed_out);
2801	}
2802
2803	/*
2804	* Get next queue for service. Unless we have a queue preemption,
2805	* we'll simply select the first cfqq in the service tree.
2806	*/
2807	static struct cfq_queue *cfq_get_next_queue(struct cfq_data *cfqd)
2808	{
2809	struct cfq_rb_root *st = st_for(cfqd->serving_group,
2810	cfqd->serving_wl_class, cfqd->serving_wl_type);
2811
2812	if (!cfqd->rq_queued)
2813	return NULL;
2814
2815	/* There is nothing to dispatch */
2816	if (!st)
2817	return NULL;
2818	if (RB_EMPTY_ROOT(&st->rb))
2819	return NULL;
2820	return cfq_rb_first(st);
2821	}
2822
2823	static struct cfq_queue *cfq_get_next_queue_forced(struct cfq_data *cfqd)
2824	{
2825	struct cfq_group *cfqg;
2826	struct cfq_queue *cfqq;
2827	int i, j;
2828	struct cfq_rb_root *st;
2829
2830	if (!cfqd->rq_queued)
2831	return NULL;
2832
2833	cfqg = cfq_get_next_cfqg(cfqd);
2834	if (!cfqg)
2835	return NULL;
2836
2837	for_each_cfqg_st(cfqg, i, j, st)
2838	if ((cfqq = cfq_rb_first(st)) != NULL)
2839	return cfqq;
2840	return NULL;
2841	}
2842
2843	/*
2844	* Get and set a new active queue for service.
2845	*/
2846	static struct cfq_queue *cfq_set_active_queue(struct cfq_data *cfqd,
2847	struct cfq_queue *cfqq)
2848	{
2849	if (!cfqq)
2850	cfqq = cfq_get_next_queue(cfqd);
2851
2852	__cfq_set_active_queue(cfqd, cfqq);
2853	return cfqq;
2854	}
2855
2856	static inline sector_t cfq_dist_from_last(struct cfq_data *cfqd,
2857	struct request *rq)
2858	{
2859	if (blk_rq_pos(rq) >= cfqd->last_position)
2860	return blk_rq_pos(rq) - cfqd->last_position;
2861	else
2862	return cfqd->last_position - blk_rq_pos(rq);
2863	}
2864
2865	static inline int cfq_rq_close(struct cfq_data *cfqd, struct cfq_queue *cfqq,
2866	struct request *rq)
2867	{
2868	return cfq_dist_from_last(cfqd, rq) <= CFQQ_CLOSE_THR;
2869	}
2870
2871	static struct cfq_queue *cfqq_close(struct cfq_data *cfqd,
2872	struct cfq_queue *cur_cfqq)
2873	{
2874	struct rb_root *root = &cfqd->prio_trees[cur_cfqq->org_ioprio];
2875	struct rb_node *parent, *node;
2876	struct cfq_queue *__cfqq;
2877	sector_t sector = cfqd->last_position;
2878
2879	if (RB_EMPTY_ROOT(root))
2880	return NULL;
2881
2882	/*
2883	* First, if we find a request starting at the end of the last
2884	* request, choose it.
2885	*/
2886	__cfqq = cfq_prio_tree_lookup(cfqd, root, sector, &parent, NULL);
2887	if (__cfqq)
2888	return __cfqq;
2889
2890	/*
2891	* If the exact sector wasn't found, the parent of the NULL leaf
2892	* will contain the closest sector.
2893	*/
2894	__cfqq = rb_entry(parent, struct cfq_queue, p_node);
2895	if (cfq_rq_close(cfqd, cur_cfqq, __cfqq->next_rq))
2896	return __cfqq;
2897
2898	if (blk_rq_pos(__cfqq->next_rq) < sector)
2899	node = rb_next(&__cfqq->p_node);
2900	else
2901	node = rb_prev(&__cfqq->p_node);
2902	if (!node)
2903	return NULL;
2904
2905	__cfqq = rb_entry(node, struct cfq_queue, p_node);
2906	if (cfq_rq_close(cfqd, cur_cfqq, __cfqq->next_rq))
2907	return __cfqq;
2908
2909	return NULL;
2910	}
2911
2912	/*
2913	* cfqd - obvious
2914	* cur_cfqq - passed in so that we don't decide that the current queue is
2915	* closely cooperating with itself.
2916	*
2917	* So, basically we're assuming that that cur_cfqq has dispatched at least
2918	* one request, and that cfqd->last_position reflects a position on the disk
2919	* associated with the I/O issued by cur_cfqq. I'm not sure this is a valid
2920	* assumption.
2921	*/
2922	static struct cfq_queue *cfq_close_cooperator(struct cfq_data *cfqd,
2923	struct cfq_queue *cur_cfqq)
2924	{
2925	struct cfq_queue *cfqq;
2926
2927	if (cfq_class_idle(cur_cfqq))
2928	return NULL;
2929	if (!cfq_cfqq_sync(cur_cfqq))
2930	return NULL;
2931	if (CFQQ_SEEKY(cur_cfqq))
2932	return NULL;
2933
2934	/*
2935	* Don't search priority tree if it's the only queue in the group.
2936	*/
2937	if (cur_cfqq->cfqg->nr_cfqq == 1)
2938	return NULL;
2939
2940	/*
2941	* We should notice if some of the queues are cooperating, eg
2942	* working closely on the same area of the disk. In that case,
2943	* we can group them together and don't waste time idling.
2944	*/
2945	cfqq = cfqq_close(cfqd, cur_cfqq);
2946	if (!cfqq)
2947	return NULL;
2948
2949	/* If new queue belongs to different cfq_group, don't choose it */
2950	if (cur_cfqq->cfqg != cfqq->cfqg)
2951	return NULL;
2952
2953	/*
2954	* It only makes sense to merge sync queues.
2955	*/
2956	if (!cfq_cfqq_sync(cfqq))
2957	return NULL;
2958	if (CFQQ_SEEKY(cfqq))
2959	return NULL;
2960
2961	/*
2962	* Do not merge queues of different priority classes
2963	*/
2964	if (cfq_class_rt(cfqq) != cfq_class_rt(cur_cfqq))
2965	return NULL;
2966
2967	return cfqq;
2968	}
2969
2970	/*
2971	* Determine whether we should enforce idle window for this queue.
2972	*/
2973
2974	static bool cfq_should_idle(struct cfq_data *cfqd, struct cfq_queue *cfqq)
2975	{
2976	enum wl_class_t wl_class = cfqq_class(cfqq);
2977	struct cfq_rb_root *st = cfqq->service_tree;
2978
2979	BUG_ON(!st);
2980	BUG_ON(!st->count);
2981
2982	if (!cfqd->cfq_slice_idle)
2983	return false;
2984
2985	/* We never do for idle class queues. */
2986	if (wl_class == IDLE_WORKLOAD)
2987	return false;
2988
2989	/* We do for queues that were marked with idle window flag. */
2990	if (cfq_cfqq_idle_window(cfqq) &&
2991	!(blk_queue_nonrot(cfqd->queue) && cfqd->hw_tag))
2992	return true;
2993
2994	/*
2995	* Otherwise, we do only if they are the last ones
2996	* in their service tree.
2997	*/
2998	if (st->count == 1 && cfq_cfqq_sync(cfqq) &&
2999	!cfq_io_thinktime_big(cfqd, &st->ttime, false))
3000	return true;
3001	cfq_log_cfqq(cfqd, cfqq, "Not idling. st->count:%d", st->count);
3002	return false;
3003	}
3004
3005	static void cfq_arm_slice_timer(struct cfq_data *cfqd)
3006	{
3007	struct cfq_queue *cfqq = cfqd->active_queue;
3008	struct cfq_rb_root *st = cfqq->service_tree;
3009	struct cfq_io_cq *cic;
3010	u64 sl, group_idle = 0;
3011	u64 now = ktime_get_ns();
3012
3013	/*
3014	* SSD device without seek penalty, disable idling. But only do so
3015	* for devices that support queuing, otherwise we still have a problem
3016	* with sync vs async workloads.
3017	*/
3018	if (blk_queue_nonrot(cfqd->queue) && cfqd->hw_tag &&
3019	!get_group_idle(cfqd))
3020	return;
3021
3022	WARN_ON(!RB_EMPTY_ROOT(&cfqq->sort_list));
3023	WARN_ON(cfq_cfqq_slice_new(cfqq));
3024
3025	/*
3026	* idle is disabled, either manually or by past process history
3027	*/
3028	if (!cfq_should_idle(cfqd, cfqq)) {
3029	/* no queue idling. Check for group idling */
3030	group_idle = get_group_idle(cfqd);
3031	if (!group_idle)
3032	return;
3033	}
3034
3035	/*
3036	* still active requests from this queue, don't idle
3037	*/
3038	if (cfqq->dispatched)
3039	return;
3040
3041	/*
3042	* task has exited, don't wait
3043	*/
3044	cic = cfqd->active_cic;
3045	if (!cic || !atomic_read(&cic->icq.ioc->active_ref))
3046	return;
3047
3048	/*
3049	* If our average think time is larger than the remaining time
3050	* slice, then don't idle. This avoids overrunning the allotted
3051	* time slice.
3052	*/
3053	if (sample_valid(cic->ttime.ttime_samples) &&
3054	(cfqq->slice_end - now < cic->ttime.ttime_mean)) {
3055	cfq_log_cfqq(cfqd, cfqq, "Not idling. think_time:%llu",
3056	cic->ttime.ttime_mean);
3057	return;
3058	}
3059
3060	/*
3061	* There are other queues in the group or this is the only group and
3062	* it has too big thinktime, don't do group idle.
3063	*/
3064	if (group_idle &&
3065	(cfqq->cfqg->nr_cfqq > 1 ||
3066	cfq_io_thinktime_big(cfqd, &st->ttime, true)))
3067	return;
3068
3069	cfq_mark_cfqq_wait_request(cfqq);
3070
3071	if (group_idle)
3072	sl = group_idle;
3073	else
3074	sl = cfqd->cfq_slice_idle;
3075
3076	hrtimer_start(&cfqd->idle_slice_timer, ns_to_ktime(sl),
3077	HRTIMER_MODE_REL);
3078	cfqg_stats_set_start_idle_time(cfqq->cfqg);
3079	cfq_log_cfqq(cfqd, cfqq, "arm_idle: %llu group_idle: %d", sl,
3080	group_idle ? 1 : 0);
3081	}
3082
3083	/*
3084	* Move request from internal lists to the request queue dispatch list.
3085	*/
3086	static void cfq_dispatch_insert(struct request_queue *q, struct request *rq)
3087	{
3088	struct cfq_data *cfqd = q->elevator->elevator_data;
3089	struct cfq_queue *cfqq = RQ_CFQQ(rq);
3090
3091	cfq_log_cfqq(cfqd, cfqq, "dispatch_insert");
3092
3093	cfqq->next_rq = cfq_find_next_rq(cfqd, cfqq, rq);
3094	cfq_remove_request(rq);
3095	cfqq->dispatched++;
3096	(RQ_CFQG(rq))->dispatched++;
3097	elv_dispatch_sort(q, rq);
3098
3099	cfqd->rq_in_flight[cfq_cfqq_sync(cfqq)]++;
3100	cfqq->nr_sectors += blk_rq_sectors(rq);
3101	}
3102
3103	/*
3104	* return expired entry, or NULL to just start from scratch in rbtree
3105	*/
3106	static struct request *cfq_check_fifo(struct cfq_queue *cfqq)
3107	{
3108	struct request *rq = NULL;
3109
3110	if (cfq_cfqq_fifo_expire(cfqq))
3111	return NULL;
3112
3113	cfq_mark_cfqq_fifo_expire(cfqq);
3114
3115	if (list_empty(&cfqq->fifo))
3116	return NULL;
3117
3118	rq = rq_entry_fifo(cfqq->fifo.next);
3119	if (ktime_get_ns() < rq->fifo_time)
3120	rq = NULL;
3121
3122	return rq;
3123	}
3124
3125	static inline int
3126	cfq_prio_to_maxrq(struct cfq_data *cfqd, struct cfq_queue *cfqq)
3127	{
3128	const int base_rq = cfqd->cfq_slice_async_rq;
3129
3130	WARN_ON(cfqq->ioprio >= IOPRIO_BE_NR);
3131
3132	return 2 * base_rq * (IOPRIO_BE_NR - cfqq->ioprio);
3133	}
3134
3135	/*
3136	* Must be called with the queue_lock held.
3137	*/
3138	static int cfqq_process_refs(struct cfq_queue *cfqq)
3139	{
3140	int process_refs, io_refs;
3141
3142	io_refs = cfqq->allocated[READ] + cfqq->allocated[WRITE];
3143	process_refs = cfqq->ref - io_refs;
3144	BUG_ON(process_refs < 0);
3145	return process_refs;
3146	}
3147
3148	static void cfq_setup_merge(struct cfq_queue *cfqq, struct cfq_queue *new_cfqq)
3149	{
3150	int process_refs, new_process_refs;
3151	struct cfq_queue *__cfqq;
3152
3153	/*
3154	* If there are no process references on the new_cfqq, then it is
3155	* unsafe to follow the ->new_cfqq chain as other cfqq's in the
3156	* chain may have dropped their last reference (not just their
3157	* last process reference).
3158	*/
3159	if (!cfqq_process_refs(new_cfqq))
3160	return;
3161
3162	/* Avoid a circular list and skip interim queue merges */
3163	while ((__cfqq = new_cfqq->new_cfqq)) {
3164	if (__cfqq == cfqq)
3165	return;
3166	new_cfqq = __cfqq;
3167	}
3168
3169	process_refs = cfqq_process_refs(cfqq);
3170	new_process_refs = cfqq_process_refs(new_cfqq);
3171	/*
3172	* If the process for the cfqq has gone away, there is no
3173	* sense in merging the queues.
3174	*/
3175	if (process_refs == 0 || new_process_refs == 0)
3176	return;
3177
3178	/*
3179	* Merge in the direction of the lesser amount of work.
3180	*/
3181	if (new_process_refs >= process_refs) {
3182	cfqq->new_cfqq = new_cfqq;
3183	new_cfqq->ref += process_refs;
3184	} else {
3185	new_cfqq->new_cfqq = cfqq;
3186	cfqq->ref += new_process_refs;
3187	}
3188	}
3189
3190	static enum wl_type_t cfq_choose_wl_type(struct cfq_data *cfqd,
3191	struct cfq_group *cfqg, enum wl_class_t wl_class)
3192	{
3193	struct cfq_queue *queue;
3194	int i;
3195	bool key_valid = false;
3196	u64 lowest_key = 0;
3197	enum wl_type_t cur_best = SYNC_NOIDLE_WORKLOAD;
3198
3199	for (i = 0; i <= SYNC_WORKLOAD; ++i) {
3200	/* select the one with lowest rb_key */
3201	queue = cfq_rb_first(st_for(cfqg, wl_class, i));
3202	if (queue &&
3203	(!key_valid || queue->rb_key < lowest_key)) {
3204	lowest_key = queue->rb_key;
3205	cur_best = i;
3206	key_valid = true;
3207	}
3208	}
3209
3210	return cur_best;
3211	}
3212
3213	static void
3214	choose_wl_class_and_type(struct cfq_data *cfqd, struct cfq_group *cfqg)
3215	{
3216	u64 slice;
3217	unsigned count;
3218	struct cfq_rb_root *st;
3219	u64 group_slice;
3220	enum wl_class_t original_class = cfqd->serving_wl_class;
3221	u64 now = ktime_get_ns();
3222
3223	/* Choose next priority. RT > BE > IDLE */
3224	if (cfq_group_busy_queues_wl(RT_WORKLOAD, cfqd, cfqg))
3225	cfqd->serving_wl_class = RT_WORKLOAD;
3226	else if (cfq_group_busy_queues_wl(BE_WORKLOAD, cfqd, cfqg))
3227	cfqd->serving_wl_class = BE_WORKLOAD;
3228	else {
3229	cfqd->serving_wl_class = IDLE_WORKLOAD;
3230	cfqd->workload_expires = now + jiffies_to_nsecs(1);
3231	return;
3232	}
3233
3234	if (original_class != cfqd->serving_wl_class)
3235	goto new_workload;
3236
3237	/*
3238	* For RT and BE, we have to choose also the type
3239	* (SYNC, SYNC_NOIDLE, ASYNC), and to compute a workload
3240	* expiration time
3241	*/
3242	st = st_for(cfqg, cfqd->serving_wl_class, cfqd->serving_wl_type);
3243	count = st->count;
3244
3245	/*
3246	* check workload expiration, and that we still have other queues ready
3247	*/
3248	if (count && !(now > cfqd->workload_expires))
3249	return;
3250
3251	new_workload:
3252	/* otherwise select new workload type */
3253	cfqd->serving_wl_type = cfq_choose_wl_type(cfqd, cfqg,
3254	cfqd->serving_wl_class);
3255	st = st_for(cfqg, cfqd->serving_wl_class, cfqd->serving_wl_type);
3256	count = st->count;
3257
3258	/*
3259	* the workload slice is computed as a fraction of target latency
3260	* proportional to the number of queues in that workload, over
3261	* all the queues in the same priority class
3262	*/
3263	group_slice = cfq_group_slice(cfqd, cfqg);
3264
3265	slice = div_u64(group_slice * count,
3266	max_t(unsigned, cfqg->busy_queues_avg[cfqd->serving_wl_class],
3267	cfq_group_busy_queues_wl(cfqd->serving_wl_class, cfqd,
3268	cfqg)));
3269
3270	if (cfqd->serving_wl_type == ASYNC_WORKLOAD) {
3271	u64 tmp;
3272
3273	/*
3274	* Async queues are currently system wide. Just taking
3275	* proportion of queues with-in same group will lead to higher
3276	* async ratio system wide as generally root group is going
3277	* to have higher weight. A more accurate thing would be to
3278	* calculate system wide asnc/sync ratio.
3279	*/
3280	tmp = cfqd->cfq_target_latency *
3281	cfqg_busy_async_queues(cfqd, cfqg);
3282	tmp = div_u64(tmp, cfqd->busy_queues);
3283	slice = min_t(u64, slice, tmp);
3284
3285	/* async workload slice is scaled down according to
3286	* the sync/async slice ratio. */
3287	slice = div64_u64(slice*cfqd->cfq_slice[0], cfqd->cfq_slice[1]);
3288	} else
3289	/* sync workload slice is at least 2 * cfq_slice_idle */
3290	slice = max(slice, 2 * cfqd->cfq_slice_idle);
3291
3292	slice = max_t(u64, slice, CFQ_MIN_TT);
3293	cfq_log(cfqd, "workload slice:%llu", slice);
3294	cfqd->workload_expires = now + slice;
3295	}
3296
3297	static struct cfq_group *cfq_get_next_cfqg(struct cfq_data *cfqd)
3298	{
3299	struct cfq_rb_root *st = &cfqd->grp_service_tree;
3300	struct cfq_group *cfqg;
3301
3302	if (RB_EMPTY_ROOT(&st->rb))
3303	return NULL;
3304	cfqg = cfq_rb_first_group(st);
3305	update_min_vdisktime(st);
3306	return cfqg;
3307	}
3308
3309	static void cfq_choose_cfqg(struct cfq_data *cfqd)
3310	{
3311	struct cfq_group *cfqg = cfq_get_next_cfqg(cfqd);
3312	u64 now = ktime_get_ns();
3313
3314	cfqd->serving_group = cfqg;
3315
3316	/* Restore the workload type data */
3317	if (cfqg->saved_wl_slice) {
3318	cfqd->workload_expires = now + cfqg->saved_wl_slice;
3319	cfqd->serving_wl_type = cfqg->saved_wl_type;
3320	cfqd->serving_wl_class = cfqg->saved_wl_class;
3321	} else
3322	cfqd->workload_expires = now - 1;
3323
3324	choose_wl_class_and_type(cfqd, cfqg);
3325	}
3326
3327	/*
3328	* Select a queue for service. If we have a current active queue,
3329	* check whether to continue servicing it, or retrieve and set a new one.
3330	*/
3331	static struct cfq_queue *cfq_select_queue(struct cfq_data *cfqd)
3332	{
3333	struct cfq_queue *cfqq, *new_cfqq = NULL;
3334	u64 now = ktime_get_ns();
3335
3336	cfqq = cfqd->active_queue;
3337	if (!cfqq)
3338	goto new_queue;
3339
3340	if (!cfqd->rq_queued)
3341	return NULL;
3342
3343	/*
3344	* We were waiting for group to get backlogged. Expire the queue
3345	*/
3346	if (cfq_cfqq_wait_busy(cfqq) && !RB_EMPTY_ROOT(&cfqq->sort_list))
3347	goto expire;
3348
3349	/*
3350	* The active queue has run out of time, expire it and select new.
3351	*/
3352	if (cfq_slice_used(cfqq) && !cfq_cfqq_must_dispatch(cfqq)) {
3353	/*
3354	* If slice had not expired at the completion of last request
3355	* we might not have turned on wait_busy flag. Don't expire
3356	* the queue yet. Allow the group to get backlogged.
3357	*
3358	* The very fact that we have used the slice, that means we
3359	* have been idling all along on this queue and it should be
3360	* ok to wait for this request to complete.
3361	*/
3362	if (cfqq->cfqg->nr_cfqq == 1 && RB_EMPTY_ROOT(&cfqq->sort_list)
3363	&& cfqq->dispatched && cfq_should_idle(cfqd, cfqq)) {
3364	cfqq = NULL;
3365	goto keep_queue;
3366	} else
3367	goto check_group_idle;
3368	}
3369
3370	/*
3371	* The active queue has requests and isn't expired, allow it to
3372	* dispatch.
3373	*/
3374	if (!RB_EMPTY_ROOT(&cfqq->sort_list))
3375	goto keep_queue;
3376
3377	/*
3378	* If another queue has a request waiting within our mean seek
3379	* distance, let it run. The expire code will check for close
3380	* cooperators and put the close queue at the front of the service
3381	* tree. If possible, merge the expiring queue with the new cfqq.
3382	*/
3383	new_cfqq = cfq_close_cooperator(cfqd, cfqq);
3384	if (new_cfqq) {
3385	if (!cfqq->new_cfqq)
3386	cfq_setup_merge(cfqq, new_cfqq);
3387	goto expire;
3388	}
3389
3390	/*
3391	* No requests pending. If the active queue still has requests in
3392	* flight or is idling for a new request, allow either of these
3393	* conditions to happen (or time out) before selecting a new queue.
3394	*/
3395	if (hrtimer_active(&cfqd->idle_slice_timer)) {
3396	cfqq = NULL;
3397	goto keep_queue;
3398	}
3399
3400	/*
3401	* This is a deep seek queue, but the device is much faster than
3402	* the queue can deliver, don't idle
3403	**/
3404	if (CFQQ_SEEKY(cfqq) && cfq_cfqq_idle_window(cfqq) &&
3405	(cfq_cfqq_slice_new(cfqq) ||
3406	(cfqq->slice_end - now > now - cfqq->slice_start))) {
3407	cfq_clear_cfqq_deep(cfqq);
3408	cfq_clear_cfqq_idle_window(cfqq);
3409	}
3410
3411	if (cfqq->dispatched && cfq_should_idle(cfqd, cfqq)) {
3412	cfqq = NULL;
3413	goto keep_queue;
3414	}
3415
3416	/*
3417	* If group idle is enabled and there are requests dispatched from
3418	* this group, wait for requests to complete.
3419	*/
3420	check_group_idle:
3421	if (get_group_idle(cfqd) && cfqq->cfqg->nr_cfqq == 1 &&
3422	cfqq->cfqg->dispatched &&
3423	!cfq_io_thinktime_big(cfqd, &cfqq->cfqg->ttime, true)) {
3424	cfqq = NULL;
3425	goto keep_queue;
3426	}
3427
3428	expire:
3429	cfq_slice_expired(cfqd, 0);
3430	new_queue:
3431	/*
3432	* Current queue expired. Check if we have to switch to a new
3433	* service tree
3434	*/
3435	if (!new_cfqq)
3436	cfq_choose_cfqg(cfqd);
3437
3438	cfqq = cfq_set_active_queue(cfqd, new_cfqq);
3439	keep_queue:
3440	return cfqq;
3441	}
3442
3443	static int __cfq_forced_dispatch_cfqq(struct cfq_queue *cfqq)
3444	{
3445	int dispatched = 0;
3446
3447	while (cfqq->next_rq) {
3448	cfq_dispatch_insert(cfqq->cfqd->queue, cfqq->next_rq);
3449	dispatched++;
3450	}
3451
3452	BUG_ON(!list_empty(&cfqq->fifo));
3453
3454	/* By default cfqq is not expired if it is empty. Do it explicitly */
3455	__cfq_slice_expired(cfqq->cfqd, cfqq, 0);
3456	return dispatched;
3457	}
3458
3459	/*
3460	* Drain our current requests. Used for barriers and when switching
3461	* io schedulers on-the-fly.
3462	*/
3463	static int cfq_forced_dispatch(struct cfq_data *cfqd)
3464	{
3465	struct cfq_queue *cfqq;
3466	int dispatched = 0;
3467
3468	/* Expire the timeslice of the current active queue first */
3469	cfq_slice_expired(cfqd, 0);
3470	while ((cfqq = cfq_get_next_queue_forced(cfqd)) != NULL) {
3471	__cfq_set_active_queue(cfqd, cfqq);
3472	dispatched += __cfq_forced_dispatch_cfqq(cfqq);
3473	}
3474
3475	BUG_ON(cfqd->busy_queues);
3476
3477	cfq_log(cfqd, "forced_dispatch=%d", dispatched);
3478	return dispatched;
3479	}
3480
3481	static inline bool cfq_slice_used_soon(struct cfq_data *cfqd,
3482	struct cfq_queue *cfqq)
3483	{
3484	u64 now = ktime_get_ns();
3485
3486	/* the queue hasn't finished any request, can't estimate */
3487	if (cfq_cfqq_slice_new(cfqq))
3488	return true;
3489	if (now + cfqd->cfq_slice_idle * cfqq->dispatched > cfqq->slice_end)
3490	return true;
3491
3492	return false;
3493	}
3494
3495	static bool cfq_may_dispatch(struct cfq_data *cfqd, struct cfq_queue *cfqq)
3496	{
3497	unsigned int max_dispatch;
3498
3499	if (cfq_cfqq_must_dispatch(cfqq))
3500	return true;
3501
3502	/*
3503	* Drain async requests before we start sync IO
3504	*/
3505	if (cfq_should_idle(cfqd, cfqq) && cfqd->rq_in_flight[BLK_RW_ASYNC])
3506	return false;
3507
3508	/*
3509	* If this is an async queue and we have sync IO in flight, let it wait
3510	*/
3511	if (cfqd->rq_in_flight[BLK_RW_SYNC] && !cfq_cfqq_sync(cfqq))
3512	return false;
3513
3514	max_dispatch = max_t(unsigned int, cfqd->cfq_quantum / 2, 1);
3515	if (cfq_class_idle(cfqq))
3516	max_dispatch = 1;
3517
3518	/*
3519	* Does this cfqq already have too much IO in flight?
3520	*/
3521	if (cfqq->dispatched >= max_dispatch) {
3522	bool promote_sync = false;
3523	/*
3524	* idle queue must always only have a single IO in flight
3525	*/
3526	if (cfq_class_idle(cfqq))
3527	return false;
3528
3529	/*
3530	* If there is only one sync queue
3531	* we can ignore async queue here and give the sync
3532	* queue no dispatch limit. The reason is a sync queue can
3533	* preempt async queue, limiting the sync queue doesn't make
3534	* sense. This is useful for aiostress test.
3535	*/
3536	if (cfq_cfqq_sync(cfqq) && cfqd->busy_sync_queues == 1)
3537	promote_sync = true;
3538
3539	/*
3540	* We have other queues, don't allow more IO from this one
3541	*/
3542	if (cfqd->busy_queues > 1 && cfq_slice_used_soon(cfqd, cfqq) &&
3543	!promote_sync)
3544	return false;
3545
3546	/*
3547	* Sole queue user, no limit
3548	*/
3549	if (cfqd->busy_queues == 1 || promote_sync)
3550	max_dispatch = -1;
3551	else
3552	/*
3553	* Normally we start throttling cfqq when cfq_quantum/2
3554	* requests have been dispatched. But we can drive
3555	* deeper queue depths at the beginning of slice
3556	* subjected to upper limit of cfq_quantum.
3557	* */
3558	max_dispatch = cfqd->cfq_quantum;
3559	}
3560
3561	/*
3562	* Async queues must wait a bit before being allowed dispatch.
3563	* We also ramp up the dispatch depth gradually for async IO,
3564	* based on the last sync IO we serviced
3565	*/
3566	if (!cfq_cfqq_sync(cfqq) && cfqd->cfq_latency) {
3567	u64 last_sync = ktime_get_ns() - cfqd->last_delayed_sync;
3568	unsigned int depth;
3569
3570	depth = div64_u64(last_sync, cfqd->cfq_slice[1]);
3571	if (!depth && !cfqq->dispatched)
3572	depth = 1;
3573	if (depth < max_dispatch)
3574	max_dispatch = depth;
3575	}
3576
3577	/*
3578	* If we're below the current max, allow a dispatch
3579	*/
3580	return cfqq->dispatched < max_dispatch;
3581	}
3582
3583	/*
3584	* Dispatch a request from cfqq, moving them to the request queue
3585	* dispatch list.
3586	*/
3587	static bool cfq_dispatch_request(struct cfq_data *cfqd, struct cfq_queue *cfqq)
3588	{
3589	struct request *rq;
3590
3591	BUG_ON(RB_EMPTY_ROOT(&cfqq->sort_list));
3592
3593	rq = cfq_check_fifo(cfqq);
3594	if (rq)
3595	cfq_mark_cfqq_must_dispatch(cfqq);
3596
3597	if (!cfq_may_dispatch(cfqd, cfqq))
3598	return false;
3599
3600	/*
3601	* follow expired path, else get first next available
3602	*/
3603	if (!rq)
3604	rq = cfqq->next_rq;
3605	else
3606	cfq_log_cfqq(cfqq->cfqd, cfqq, "fifo=%p", rq);
3607
3608	/*
3609	* insert request into driver dispatch list
3610	*/
3611	cfq_dispatch_insert(cfqd->queue, rq);
3612
3613	if (!cfqd->active_cic) {
3614	struct cfq_io_cq *cic = RQ_CIC(rq);
3615
3616	atomic_long_inc(&cic->icq.ioc->refcount);
3617	cfqd->active_cic = cic;
3618	}
3619
3620	return true;
3621	}
3622
3623	/*
3624	* Find the cfqq that we need to service and move a request from that to the
3625	* dispatch list
3626	*/
3627	static int cfq_dispatch_requests(struct request_queue *q, int force)
3628	{
3629	struct cfq_data *cfqd = q->elevator->elevator_data;
3630	struct cfq_queue *cfqq;
3631
3632	if (!cfqd->busy_queues)
3633	return 0;
3634
3635	if (unlikely(force))
3636	return cfq_forced_dispatch(cfqd);
3637
3638	cfqq = cfq_select_queue(cfqd);
3639	if (!cfqq)
3640	return 0;
3641
3642	/*
3643	* Dispatch a request from this cfqq, if it is allowed
3644	*/
3645	if (!cfq_dispatch_request(cfqd, cfqq))
3646	return 0;
3647
3648	cfqq->slice_dispatch++;
3649	cfq_clear_cfqq_must_dispatch(cfqq);
3650
3651	/*
3652	* expire an async queue immediately if it has used up its slice. idle
3653	* queue always expire after 1 dispatch round.
3654	*/
3655	if (cfqd->busy_queues > 1 && ((!cfq_cfqq_sync(cfqq) &&
3656	cfqq->slice_dispatch >= cfq_prio_to_maxrq(cfqd, cfqq)) ||
3657	cfq_class_idle(cfqq))) {
3658	cfqq->slice_end = ktime_get_ns() + 1;
3659	cfq_slice_expired(cfqd, 0);
3660	}
3661
3662	cfq_log_cfqq(cfqd, cfqq, "dispatched a request");
3663	return 1;
3664	}
3665
3666	/*
3667	* task holds one reference to the queue, dropped when task exits. each rq
3668	* in-flight on this queue also holds a reference, dropped when rq is freed.
3669	*
3670	* Each cfq queue took a reference on the parent group. Drop it now.
3671	* queue lock must be held here.
3672	*/
3673	static void cfq_put_queue(struct cfq_queue *cfqq)
3674	{
3675	struct cfq_data *cfqd = cfqq->cfqd;
3676	struct cfq_group *cfqg;
3677
3678	BUG_ON(cfqq->ref <= 0);
3679
3680	cfqq->ref--;
3681	if (cfqq->ref)
3682	return;
3683
3684	cfq_log_cfqq(cfqd, cfqq, "put_queue");
3685	BUG_ON(rb_first(&cfqq->sort_list));
3686	BUG_ON(cfqq->allocated[READ] + cfqq->allocated[WRITE]);
3687	cfqg = cfqq->cfqg;
3688
3689	if (unlikely(cfqd->active_queue == cfqq)) {
3690	__cfq_slice_expired(cfqd, cfqq, 0);
3691	cfq_schedule_dispatch(cfqd);
3692	}
3693
3694	BUG_ON(cfq_cfqq_on_rr(cfqq));
3695	kmem_cache_free(cfq_pool, cfqq);
3696	cfqg_put(cfqg);
3697	}
3698
3699	static void cfq_put_cooperator(struct cfq_queue *cfqq)
3700	{
3701	struct cfq_queue *__cfqq, *next;
3702
3703	/*
3704	* If this queue was scheduled to merge with another queue, be
3705	* sure to drop the reference taken on that queue (and others in
3706	* the merge chain). See cfq_setup_merge and cfq_merge_cfqqs.
3707	*/
3708	__cfqq = cfqq->new_cfqq;
3709	while (__cfqq) {
3710	if (__cfqq == cfqq) {
3711	WARN(1, "cfqq->new_cfqq loop detected\n");
3712	break;
3713	}
3714	next = __cfqq->new_cfqq;
3715	cfq_put_queue(__cfqq);
3716	__cfqq = next;
3717	}
3718	}
3719
3720	static void cfq_exit_cfqq(struct cfq_data *cfqd, struct cfq_queue *cfqq)
3721	{
3722	if (unlikely(cfqq == cfqd->active_queue)) {
3723	__cfq_slice_expired(cfqd, cfqq, 0);
3724	cfq_schedule_dispatch(cfqd);
3725	}
3726
3727	cfq_put_cooperator(cfqq);
3728
3729	cfq_put_queue(cfqq);
3730	}
3731
3732	static void cfq_init_icq(struct io_cq *icq)
3733	{
3734	struct cfq_io_cq *cic = icq_to_cic(icq);
3735
3736	cic->ttime.last_end_request = ktime_get_ns();
3737	}
3738
3739	static void cfq_exit_icq(struct io_cq *icq)
3740	{
3741	struct cfq_io_cq *cic = icq_to_cic(icq);
3742	struct cfq_data *cfqd = cic_to_cfqd(cic);
3743
3744	if (cic_to_cfqq(cic, false)) {
3745	cfq_exit_cfqq(cfqd, cic_to_cfqq(cic, false));
3746	cic_set_cfqq(cic, NULL, false);
3747	}
3748
3749	if (cic_to_cfqq(cic, true)) {
3750	cfq_exit_cfqq(cfqd, cic_to_cfqq(cic, true));
3751	cic_set_cfqq(cic, NULL, true);
3752	}
3753	}
3754
3755	static void cfq_init_prio_data(struct cfq_queue *cfqq, struct cfq_io_cq *cic)
3756	{
3757	struct task_struct *tsk = current;
3758	int ioprio_class;
3759
3760	if (!cfq_cfqq_prio_changed(cfqq))
3761	return;
3762
3763	ioprio_class = IOPRIO_PRIO_CLASS(cic->ioprio);
3764	switch (ioprio_class) {
3765	default:
3766	printk(KERN_ERR "cfq: bad prio %x\n", ioprio_class);
3767	case IOPRIO_CLASS_NONE:
3768	/*
3769	* no prio set, inherit CPU scheduling settings
3770	*/
3771	cfqq->ioprio = task_nice_ioprio(tsk);
3772	cfqq->ioprio_class = task_nice_ioclass(tsk);
3773	break;
3774	case IOPRIO_CLASS_RT:
3775	cfqq->ioprio = IOPRIO_PRIO_DATA(cic->ioprio);
3776	cfqq->ioprio_class = IOPRIO_CLASS_RT;
3777	break;
3778	case IOPRIO_CLASS_BE:
3779	cfqq->ioprio = IOPRIO_PRIO_DATA(cic->ioprio);
3780	cfqq->ioprio_class = IOPRIO_CLASS_BE;
3781	break;
3782	case IOPRIO_CLASS_IDLE:
3783	cfqq->ioprio_class = IOPRIO_CLASS_IDLE;
3784	cfqq->ioprio = 7;
3785	cfq_clear_cfqq_idle_window(cfqq);
3786	break;
3787	}
3788
3789	/*
3790	* keep track of original prio settings in case we have to temporarily
3791	* elevate the priority of this queue
3792	*/
3793	cfqq->org_ioprio = cfqq->ioprio;
3794	cfqq->org_ioprio_class = cfqq->ioprio_class;
3795	cfq_clear_cfqq_prio_changed(cfqq);
3796	}
3797
3798	static void check_ioprio_changed(struct cfq_io_cq *cic, struct bio *bio)
3799	{
3800	int ioprio = cic->icq.ioc->ioprio;
3801	struct cfq_data *cfqd = cic_to_cfqd(cic);
3802	struct cfq_queue *cfqq;
3803
3804	/*
3805	* Check whether ioprio has changed. The condition may trigger
3806	* spuriously on a newly created cic but there's no harm.
3807	*/
3808	if (unlikely(!cfqd) || likely(cic->ioprio == ioprio))
3809	return;
3810
3811	cfqq = cic_to_cfqq(cic, false);
3812	if (cfqq) {
3813	cfq_put_queue(cfqq);
3814	cfqq = cfq_get_queue(cfqd, BLK_RW_ASYNC, cic, bio);
3815	cic_set_cfqq(cic, cfqq, false);
3816	}
3817
3818	cfqq = cic_to_cfqq(cic, true);
3819	if (cfqq)
3820	cfq_mark_cfqq_prio_changed(cfqq);
3821
3822	cic->ioprio = ioprio;
3823	}
3824
3825	static void cfq_init_cfqq(struct cfq_data *cfqd, struct cfq_queue *cfqq,
3826	pid_t pid, bool is_sync)
3827	{
3828	RB_CLEAR_NODE(&cfqq->rb_node);
3829	RB_CLEAR_NODE(&cfqq->p_node);
3830	INIT_LIST_HEAD(&cfqq->fifo);
3831
3832	cfqq->ref = 0;
3833	cfqq->cfqd = cfqd;
3834
3835	cfq_mark_cfqq_prio_changed(cfqq);
3836
3837	if (is_sync) {
3838	if (!cfq_class_idle(cfqq))
3839	cfq_mark_cfqq_idle_window(cfqq);
3840	cfq_mark_cfqq_sync(cfqq);
3841	}
3842	cfqq->pid = pid;
3843	}
3844
3845	#ifdef CONFIG_CFQ_GROUP_IOSCHED
3846	static void check_blkcg_changed(struct cfq_io_cq *cic, struct bio *bio)
3847	{
3848	struct cfq_data *cfqd = cic_to_cfqd(cic);
3849	struct cfq_queue *cfqq;
3850	uint64_t serial_nr;
3851
3852	rcu_read_lock();
3853	serial_nr = bio_blkcg(bio)->css.serial_nr;
3854	rcu_read_unlock();
3855
3856	/*
3857	* Check whether blkcg has changed. The condition may trigger
3858	* spuriously on a newly created cic but there's no harm.
3859	*/
3860	if (unlikely(!cfqd) || likely(cic->blkcg_serial_nr == serial_nr))
3861	return;
3862
3863	/*
3864	* Drop reference to queues. New queues will be assigned in new
3865	* group upon arrival of fresh requests.
3866	*/
3867	cfqq = cic_to_cfqq(cic, false);
3868	if (cfqq) {
3869	cfq_log_cfqq(cfqd, cfqq, "changed cgroup");
3870	cic_set_cfqq(cic, NULL, false);
3871	cfq_put_queue(cfqq);
3872	}
3873
3874	cfqq = cic_to_cfqq(cic, true);
3875	if (cfqq) {
3876	cfq_log_cfqq(cfqd, cfqq, "changed cgroup");
3877	cic_set_cfqq(cic, NULL, true);
3878	cfq_put_queue(cfqq);
3879	}
3880
3881	cic->blkcg_serial_nr = serial_nr;
3882	}
3883	#else
3884	static inline void check_blkcg_changed(struct cfq_io_cq *cic, struct bio *bio) { }
3885	#endif /* CONFIG_CFQ_GROUP_IOSCHED */
3886
3887	static struct cfq_queue **
3888	cfq_async_queue_prio(struct cfq_group *cfqg, int ioprio_class, int ioprio)
3889	{
3890	switch (ioprio_class) {
3891	case IOPRIO_CLASS_RT:
3892	return &cfqg->async_cfqq[0][ioprio];
3893	case IOPRIO_CLASS_NONE:
3894	ioprio = IOPRIO_NORM;
3895	/* fall through */
3896	case IOPRIO_CLASS_BE:
3897	return &cfqg->async_cfqq[1][ioprio];
3898	case IOPRIO_CLASS_IDLE:
3899	return &cfqg->async_idle_cfqq;
3900	default:
3901	BUG();
3902	}
3903	}
3904
3905	static struct cfq_queue *
3906	cfq_get_queue(struct cfq_data *cfqd, bool is_sync, struct cfq_io_cq *cic,
3907	struct bio *bio)
3908	{
3909	int ioprio_class = IOPRIO_PRIO_CLASS(cic->ioprio);
3910	int ioprio = IOPRIO_PRIO_DATA(cic->ioprio);
3911	struct cfq_queue **async_cfqq = NULL;
3912	struct cfq_queue *cfqq;
3913	struct cfq_group *cfqg;
3914
3915	rcu_read_lock();
3916	cfqg = cfq_lookup_cfqg(cfqd, bio_blkcg(bio));
3917	if (!cfqg) {
3918	cfqq = &cfqd->oom_cfqq;
3919	goto out;
3920	}
3921
3922	if (!is_sync) {
3923	if (!ioprio_valid(cic->ioprio)) {
3924	struct task_struct *tsk = current;
3925	ioprio = task_nice_ioprio(tsk);
3926	ioprio_class = task_nice_ioclass(tsk);
3927	}
3928	async_cfqq = cfq_async_queue_prio(cfqg, ioprio_class, ioprio);
3929	cfqq = *async_cfqq;
3930	if (cfqq)
3931	goto out;
3932	}
3933
3934	cfqq = kmem_cache_alloc_node(cfq_pool,
3935	GFP_NOWAIT | __GFP_ZERO | __GFP_NOWARN,
3936	cfqd->queue->node);
3937	if (!cfqq) {
3938	cfqq = &cfqd->oom_cfqq;
3939	goto out;
3940	}
3941
3942	cfq_init_cfqq(cfqd, cfqq, current->pid, is_sync);
3943	cfq_init_prio_data(cfqq, cic);
3944	cfq_link_cfqq_cfqg(cfqq, cfqg);
3945	cfq_log_cfqq(cfqd, cfqq, "alloced");
3946
3947	if (async_cfqq) {
3948	/* a new async queue is created, pin and remember */
3949	cfqq->ref++;
3950	*async_cfqq = cfqq;
3951	}
3952	out:
3953	cfqq->ref++;
3954	rcu_read_unlock();
3955	return cfqq;
3956	}
3957
3958	static void
3959	__cfq_update_io_thinktime(struct cfq_ttime *ttime, u64 slice_idle)
3960	{
3961	u64 elapsed = ktime_get_ns() - ttime->last_end_request;
3962	elapsed = min(elapsed, 2UL * slice_idle);
3963
3964	ttime->ttime_samples = (7*ttime->ttime_samples + 256) / 8;
3965	ttime->ttime_total = div_u64(7*ttime->ttime_total + 256*elapsed, 8);
3966	ttime->ttime_mean = div64_ul(ttime->ttime_total + 128,
3967	ttime->ttime_samples);
3968	}
3969
3970	static void
3971	cfq_update_io_thinktime(struct cfq_data *cfqd, struct cfq_queue *cfqq,
3972	struct cfq_io_cq *cic)
3973	{
3974	if (cfq_cfqq_sync(cfqq)) {
3975	__cfq_update_io_thinktime(&cic->ttime, cfqd->cfq_slice_idle);
3976	__cfq_update_io_thinktime(&cfqq->service_tree->ttime,
3977	cfqd->cfq_slice_idle);
3978	}
3979	#ifdef CONFIG_CFQ_GROUP_IOSCHED
3980	__cfq_update_io_thinktime(&cfqq->cfqg->ttime, get_group_idle(cfqd));
3981	#endif
3982	}
3983
3984	static void
3985	cfq_update_io_seektime(struct cfq_data *cfqd, struct cfq_queue *cfqq,
3986	struct request *rq)
3987	{
3988	sector_t sdist = 0;
3989	sector_t n_sec = blk_rq_sectors(rq);
3990	if (cfqq->last_request_pos) {
3991	if (cfqq->last_request_pos < blk_rq_pos(rq))
3992	sdist = blk_rq_pos(rq) - cfqq->last_request_pos;
3993	else
3994	sdist = cfqq->last_request_pos - blk_rq_pos(rq);
3995	}
3996
3997	cfqq->seek_history <<= 1;
3998	if (blk_queue_nonrot(cfqd->queue))
3999	cfqq->seek_history |= (n_sec < CFQQ_SECT_THR_NONROT);
4000	else
4001	cfqq->seek_history |= (sdist > CFQQ_SEEK_THR);
4002	}
4003
4004	/*
4005	* Disable idle window if the process thinks too long or seeks so much that
4006	* it doesn't matter
4007	*/
4008	static void
4009	cfq_update_idle_window(struct cfq_data *cfqd, struct cfq_queue *cfqq,
4010	struct cfq_io_cq *cic)
4011	{
4012	int old_idle, enable_idle;
4013
4014	/*
4015	* Don't idle for async or idle io prio class
4016	*/
4017	if (!cfq_cfqq_sync(cfqq) || cfq_class_idle(cfqq))
4018	return;
4019
4020	enable_idle = old_idle = cfq_cfqq_idle_window(cfqq);
4021
4022	if (cfqq->queued[0] + cfqq->queued[1] >= 4)
4023	cfq_mark_cfqq_deep(cfqq);
4024
4025	if (cfqq->next_rq && (cfqq->next_rq->cmd_flags & REQ_NOIDLE))
4026	enable_idle = 0;
4027	else if (!atomic_read(&cic->icq.ioc->active_ref) ||
4028	!cfqd->cfq_slice_idle ||
4029	(!cfq_cfqq_deep(cfqq) && CFQQ_SEEKY(cfqq)))
4030	enable_idle = 0;
4031	else if (sample_valid(cic->ttime.ttime_samples)) {
4032	if (cic->ttime.ttime_mean > cfqd->cfq_slice_idle)
4033	enable_idle = 0;
4034	else
4035	enable_idle = 1;
4036	}
4037
4038	if (old_idle != enable_idle) {
4039	cfq_log_cfqq(cfqd, cfqq, "idle=%d", enable_idle);
4040	if (enable_idle)
4041	cfq_mark_cfqq_idle_window(cfqq);
4042	else
4043	cfq_clear_cfqq_idle_window(cfqq);
4044	}
4045	}
4046
4047	/*
4048	* Check if new_cfqq should preempt the currently active queue. Return 0 for
4049	* no or if we aren't sure, a 1 will cause a preempt.
4050	*/
4051	static bool
4052	cfq_should_preempt(struct cfq_data *cfqd, struct cfq_queue *new_cfqq,
4053	struct request *rq)
4054	{
4055	struct cfq_queue *cfqq;
4056
4057	cfqq = cfqd->active_queue;
4058	if (!cfqq)
4059	return false;
4060
4061	if (cfq_class_idle(new_cfqq))
4062	return false;
4063
4064	if (cfq_class_idle(cfqq))
4065	return true;
4066
4067	/*
4068	* Don't allow a non-RT request to preempt an ongoing RT cfqq timeslice.
4069	*/
4070	if (cfq_class_rt(cfqq) && !cfq_class_rt(new_cfqq))
4071	return false;
4072
4073	/*
4074	* if the new request is sync, but the currently running queue is
4075	* not, let the sync request have priority.
4076	*/
4077	if (rq_is_sync(rq) && !cfq_cfqq_sync(cfqq) && !cfq_cfqq_must_dispatch(cfqq))
4078	return true;
4079
4080	/*
4081	* Treat ancestors of current cgroup the same way as current cgroup.
4082	* For anybody else we disallow preemption to guarantee service
4083	* fairness among cgroups.
4084	*/
4085	if (!cfqg_is_descendant(cfqq->cfqg, new_cfqq->cfqg))
4086	return false;
4087
4088	if (cfq_slice_used(cfqq))
4089	return true;
4090
4091	/*
4092	* Allow an RT request to pre-empt an ongoing non-RT cfqq timeslice.
4093	*/
4094	if (cfq_class_rt(new_cfqq) && !cfq_class_rt(cfqq))
4095	return true;
4096
4097	WARN_ON_ONCE(cfqq->ioprio_class != new_cfqq->ioprio_class);
4098	/* Allow preemption only if we are idling on sync-noidle tree */
4099	if (cfqd->serving_wl_type == SYNC_NOIDLE_WORKLOAD &&
4100	cfqq_type(new_cfqq) == SYNC_NOIDLE_WORKLOAD &&
4101	RB_EMPTY_ROOT(&cfqq->sort_list))
4102	return true;
4103
4104	/*
4105	* So both queues are sync. Let the new request get disk time if
4106	* it's a metadata request and the current queue is doing regular IO.
4107	*/
4108	if ((rq->cmd_flags & REQ_PRIO) && !cfqq->prio_pending)
4109	return true;
4110
4111	/* An idle queue should not be idle now for some reason */
4112	if (RB_EMPTY_ROOT(&cfqq->sort_list) && !cfq_should_idle(cfqd, cfqq))
4113	return true;
4114
4115	if (!cfqd->active_cic || !cfq_cfqq_wait_request(cfqq))
4116	return false;
4117
4118	/*
4119	* if this request is as-good as one we would expect from the
4120	* current cfqq, let it preempt
4121	*/
4122	if (cfq_rq_close(cfqd, cfqq, rq))
4123	return true;
4124
4125	return false;
4126	}
4127
4128	/*
4129	* cfqq preempts the active queue. if we allowed preempt with no slice left,
4130	* let it have half of its nominal slice.
4131	*/
4132	static void cfq_preempt_queue(struct cfq_data *cfqd, struct cfq_queue *cfqq)
4133	{
4134	enum wl_type_t old_type = cfqq_type(cfqd->active_queue);
4135
4136	cfq_log_cfqq(cfqd, cfqq, "preempt");
4137	cfq_slice_expired(cfqd, 1);
4138
4139	/*
4140	* workload type is changed, don't save slice, otherwise preempt
4141	* doesn't happen
4142	*/
4143	if (old_type != cfqq_type(cfqq))
4144	cfqq->cfqg->saved_wl_slice = 0;
4145
4146	/*
4147	* Put the new queue at the front of the of the current list,
4148	* so we know that it will be selected next.
4149	*/
4150	BUG_ON(!cfq_cfqq_on_rr(cfqq));
4151
4152	cfq_service_tree_add(cfqd, cfqq, 1);
4153
4154	cfqq->slice_end = 0;
4155	cfq_mark_cfqq_slice_new(cfqq);
4156	}
4157
4158	/*
4159	* Called when a new fs request (rq) is added (to cfqq). Check if there's
4160	* something we should do about it
4161	*/
4162	static void
4163	cfq_rq_enqueued(struct cfq_data *cfqd, struct cfq_queue *cfqq,
4164	struct request *rq)
4165	{
4166	struct cfq_io_cq *cic = RQ_CIC(rq);
4167
4168	cfqd->rq_queued++;
4169	if (rq->cmd_flags & REQ_PRIO)
4170	cfqq->prio_pending++;
4171
4172	cfq_update_io_thinktime(cfqd, cfqq, cic);
4173	cfq_update_io_seektime(cfqd, cfqq, rq);
4174	cfq_update_idle_window(cfqd, cfqq, cic);
4175
4176	cfqq->last_request_pos = blk_rq_pos(rq) + blk_rq_sectors(rq);
4177
4178	if (cfqq == cfqd->active_queue) {
4179	/*
4180	* Remember that we saw a request from this process, but
4181	* don't start queuing just yet. Otherwise we risk seeing lots
4182	* of tiny requests, because we disrupt the normal plugging
4183	* and merging. If the request is already larger than a single
4184	* page, let it rip immediately. For that case we assume that
4185	* merging is already done. Ditto for a busy system that
4186	* has other work pending, don't risk delaying until the
4187	* idle timer unplug to continue working.
4188	*/
4189	if (cfq_cfqq_wait_request(cfqq)) {
4190	if (blk_rq_bytes(rq) > PAGE_SIZE ||
4191	cfqd->busy_queues > 1) {
4192	cfq_del_timer(cfqd, cfqq);
4193	cfq_clear_cfqq_wait_request(cfqq);
4194	__blk_run_queue(cfqd->queue);
4195	} else {
4196	cfqg_stats_update_idle_time(cfqq->cfqg);
4197	cfq_mark_cfqq_must_dispatch(cfqq);
4198	}
4199	}
4200	} else if (cfq_should_preempt(cfqd, cfqq, rq)) {
4201	/*
4202	* not the active queue - expire current slice if it is
4203	* idle and has expired it's mean thinktime or this new queue
4204	* has some old slice time left and is of higher priority or
4205	* this new queue is RT and the current one is BE
4206	*/
4207	cfq_preempt_queue(cfqd, cfqq);
4208	__blk_run_queue(cfqd->queue);
4209	}
4210	}
4211
4212	static void cfq_insert_request(struct request_queue *q, struct request *rq)
4213	{
4214	struct cfq_data *cfqd = q->elevator->elevator_data;
4215	struct cfq_queue *cfqq = RQ_CFQQ(rq);
4216
4217	cfq_log_cfqq(cfqd, cfqq, "insert_request");
4218	cfq_init_prio_data(cfqq, RQ_CIC(rq));
4219
4220	rq->fifo_time = ktime_get_ns() + cfqd->cfq_fifo_expire[rq_is_sync(rq)];
4221	list_add_tail(&rq->queuelist, &cfqq->fifo);
4222	cfq_add_rq_rb(rq);
4223	cfqg_stats_update_io_add(RQ_CFQG(rq), cfqd->serving_group, req_op(rq),
4224	rq->cmd_flags);
4225	cfq_rq_enqueued(cfqd, cfqq, rq);
4226	}
4227
4228	/*
4229	* Update hw_tag based on peak queue depth over 50 samples under
4230	* sufficient load.
4231	*/
4232	static void cfq_update_hw_tag(struct cfq_data *cfqd)
4233	{
4234	struct cfq_queue *cfqq = cfqd->active_queue;
4235
4236	if (cfqd->rq_in_driver > cfqd->hw_tag_est_depth)
4237	cfqd->hw_tag_est_depth = cfqd->rq_in_driver;
4238
4239	if (cfqd->hw_tag == 1)
4240	return;
4241
4242	if (cfqd->rq_queued <= CFQ_HW_QUEUE_MIN &&
4243	cfqd->rq_in_driver <= CFQ_HW_QUEUE_MIN)
4244	return;
4245
4246	/*
4247	* If active queue hasn't enough requests and can idle, cfq might not
4248	* dispatch sufficient requests to hardware. Don't zero hw_tag in this
4249	* case
4250	*/
4251	if (cfqq && cfq_cfqq_idle_window(cfqq) &&
4252	cfqq->dispatched + cfqq->queued[0] + cfqq->queued[1] <
4253	CFQ_HW_QUEUE_MIN && cfqd->rq_in_driver < CFQ_HW_QUEUE_MIN)
4254	return;
4255
4256	if (cfqd->hw_tag_samples++ < 50)
4257	return;
4258
4259	if (cfqd->hw_tag_est_depth >= CFQ_HW_QUEUE_MIN)
4260	cfqd->hw_tag = 1;
4261	else
4262	cfqd->hw_tag = 0;
4263	}
4264
4265	static bool cfq_should_wait_busy(struct cfq_data *cfqd, struct cfq_queue *cfqq)
4266	{
4267	struct cfq_io_cq *cic = cfqd->active_cic;
4268	u64 now = ktime_get_ns();
4269
4270	/* If the queue already has requests, don't wait */
4271	if (!RB_EMPTY_ROOT(&cfqq->sort_list))
4272	return false;
4273
4274	/* If there are other queues in the group, don't wait */
4275	if (cfqq->cfqg->nr_cfqq > 1)
4276	return false;
4277
4278	/* the only queue in the group, but think time is big */
4279	if (cfq_io_thinktime_big(cfqd, &cfqq->cfqg->ttime, true))
4280	return false;
4281
4282	if (cfq_slice_used(cfqq))
4283	return true;
4284
4285	/* if slice left is less than think time, wait busy */
4286	if (cic && sample_valid(cic->ttime.ttime_samples)
4287	&& (cfqq->slice_end - now < cic->ttime.ttime_mean))
4288	return true;
4289
4290	/*
4291	* If think times is less than a jiffy than ttime_mean=0 and above
4292	* will not be true. It might happen that slice has not expired yet
4293	* but will expire soon (4-5 ns) during select_queue(). To cover the
4294	* case where think time is less than a jiffy, mark the queue wait
4295	* busy if only 1 jiffy is left in the slice.
4296	*/
4297	if (cfqq->slice_end - now <= jiffies_to_nsecs(1))
4298	return true;
4299
4300	return false;
4301	}
4302
4303	static void cfq_completed_request(struct request_queue *q, struct request *rq)
4304	{
4305	struct cfq_queue *cfqq = RQ_CFQQ(rq);
4306	struct cfq_data *cfqd = cfqq->cfqd;
4307	const int sync = rq_is_sync(rq);
4308	u64 now = ktime_get_ns();
4309
4310	cfq_log_cfqq(cfqd, cfqq, "complete rqnoidle %d",
4311	!!(rq->cmd_flags & REQ_NOIDLE));
4312
4313	cfq_update_hw_tag(cfqd);
4314
4315	WARN_ON(!cfqd->rq_in_driver);
4316	WARN_ON(!cfqq->dispatched);
4317	cfqd->rq_in_driver--;
4318	cfqq->dispatched--;
4319	(RQ_CFQG(rq))->dispatched--;
4320	cfqg_stats_update_completion(cfqq->cfqg, rq_start_time_ns(rq),
4321	rq_io_start_time_ns(rq), req_op(rq),
4322	rq->cmd_flags);
4323
4324	cfqd->rq_in_flight[cfq_cfqq_sync(cfqq)]--;
4325
4326	if (sync) {
4327	struct cfq_rb_root *st;
4328
4329	RQ_CIC(rq)->ttime.last_end_request = now;
4330
4331	if (cfq_cfqq_on_rr(cfqq))
4332	st = cfqq->service_tree;
4333	else
4334	st = st_for(cfqq->cfqg, cfqq_class(cfqq),
4335	cfqq_type(cfqq));
4336
4337	st->ttime.last_end_request = now;
4338	/*
4339	* We have to do this check in jiffies since start_time is in
4340	* jiffies and it is not trivial to convert to ns. If
4341	* cfq_fifo_expire[1] ever comes close to 1 jiffie, this test
4342	* will become problematic but so far we are fine (the default
4343	* is 128 ms).
4344	*/
4345	if (!time_after(rq->start_time +
4346	nsecs_to_jiffies(cfqd->cfq_fifo_expire[1]),
4347	jiffies))
4348	cfqd->last_delayed_sync = now;
4349	}
4350
4351	#ifdef CONFIG_CFQ_GROUP_IOSCHED
4352	cfqq->cfqg->ttime.last_end_request = now;
4353	#endif
4354
4355	/*
4356	* If this is the active queue, check if it needs to be expired,
4357	* or if we want to idle in case it has no pending requests.
4358	*/
4359	if (cfqd->active_queue == cfqq) {
4360	const bool cfqq_empty = RB_EMPTY_ROOT(&cfqq->sort_list);
4361
4362	if (cfq_cfqq_slice_new(cfqq)) {
4363	cfq_set_prio_slice(cfqd, cfqq);
4364	cfq_clear_cfqq_slice_new(cfqq);
4365	}
4366
4367	/*
4368	* Should we wait for next request to come in before we expire
4369	* the queue.
4370	*/
4371	if (cfq_should_wait_busy(cfqd, cfqq)) {
4372	u64 extend_sl = cfqd->cfq_slice_idle;
4373	if (!cfqd->cfq_slice_idle)
4374	extend_sl = get_group_idle(cfqd);
4375	cfqq->slice_end = now + extend_sl;
4376	cfq_mark_cfqq_wait_busy(cfqq);
4377	cfq_log_cfqq(cfqd, cfqq, "will busy wait");
4378	}
4379
4380	/*
4381	* Idling is not enabled on:
4382	* - expired queues
4383	* - idle-priority queues
4384	* - async queues
4385	* - queues with still some requests queued
4386	* - when there is a close cooperator
4387	*/
4388	if (cfq_slice_used(cfqq) || cfq_class_idle(cfqq))
4389	cfq_slice_expired(cfqd, 1);
4390	else if (sync && cfqq_empty &&
4391	!cfq_close_cooperator(cfqd, cfqq)) {
4392	cfq_arm_slice_timer(cfqd);
4393	}
4394	}
4395
4396	if (!cfqd->rq_in_driver)
4397	cfq_schedule_dispatch(cfqd);
4398	}
4399
4400	static void cfqq_boost_on_prio(struct cfq_queue *cfqq, int op_flags)
4401	{
4402	/*
4403	* If REQ_PRIO is set, boost class and prio level, if it's below
4404	* BE/NORM. If prio is not set, restore the potentially boosted
4405	* class/prio level.
4406	*/
4407	if (!(op_flags & REQ_PRIO)) {
4408	cfqq->ioprio_class = cfqq->org_ioprio_class;
4409	cfqq->ioprio = cfqq->org_ioprio;
4410	} else {
4411	if (cfq_class_idle(cfqq))
4412	cfqq->ioprio_class = IOPRIO_CLASS_BE;
4413	if (cfqq->ioprio > IOPRIO_NORM)
4414	cfqq->ioprio = IOPRIO_NORM;
4415	}
4416	}
4417
4418	static inline int __cfq_may_queue(struct cfq_queue *cfqq)
4419	{
4420	if (cfq_cfqq_wait_request(cfqq) && !cfq_cfqq_must_alloc_slice(cfqq)) {
4421	cfq_mark_cfqq_must_alloc_slice(cfqq);
4422	return ELV_MQUEUE_MUST;
4423	}
4424
4425	return ELV_MQUEUE_MAY;
4426	}
4427
4428	static int cfq_may_queue(struct request_queue *q, int op, int op_flags)
4429	{
4430	struct cfq_data *cfqd = q->elevator->elevator_data;
4431	struct task_struct *tsk = current;
4432	struct cfq_io_cq *cic;
4433	struct cfq_queue *cfqq;
4434
4435	/*
4436	* don't force setup of a queue from here, as a call to may_queue
4437	* does not necessarily imply that a request actually will be queued.
4438	* so just lookup a possibly existing queue, or return 'may queue'
4439	* if that fails
4440	*/
4441	cic = cfq_cic_lookup(cfqd, tsk->io_context);
4442	if (!cic)
4443	return ELV_MQUEUE_MAY;
4444
4445	cfqq = cic_to_cfqq(cic, rw_is_sync(op, op_flags));
4446	if (cfqq) {
4447	cfq_init_prio_data(cfqq, cic);
4448	cfqq_boost_on_prio(cfqq, op_flags);
4449
4450	return __cfq_may_queue(cfqq);
4451	}
4452
4453	return ELV_MQUEUE_MAY;
4454	}
4455
4456	/*
4457	* queue lock held here
4458	*/
4459	static void cfq_put_request(struct request *rq)
4460	{
4461	struct cfq_queue *cfqq = RQ_CFQQ(rq);
4462
4463	if (cfqq) {
4464	const int rw = rq_data_dir(rq);
4465
4466	BUG_ON(!cfqq->allocated[rw]);
4467	cfqq->allocated[rw]--;
4468
4469	/* Put down rq reference on cfqg */
4470	cfqg_put(RQ_CFQG(rq));
4471	rq->elv.priv[0] = NULL;
4472	rq->elv.priv[1] = NULL;
4473
4474	cfq_put_queue(cfqq);
4475	}
4476	}
4477
4478	static struct cfq_queue *
4479	cfq_merge_cfqqs(struct cfq_data *cfqd, struct cfq_io_cq *cic,
4480	struct cfq_queue *cfqq)
4481	{
4482	cfq_log_cfqq(cfqd, cfqq, "merging with queue %p", cfqq->new_cfqq);
4483	cic_set_cfqq(cic, cfqq->new_cfqq, 1);
4484	cfq_mark_cfqq_coop(cfqq->new_cfqq);
4485	cfq_put_queue(cfqq);
4486	return cic_to_cfqq(cic, 1);
4487	}
4488
4489	/*
4490	* Returns NULL if a new cfqq should be allocated, or the old cfqq if this
4491	* was the last process referring to said cfqq.
4492	*/
4493	static struct cfq_queue *
4494	split_cfqq(struct cfq_io_cq *cic, struct cfq_queue *cfqq)
4495	{
4496	if (cfqq_process_refs(cfqq) == 1) {
4497	cfqq->pid = current->pid;
4498	cfq_clear_cfqq_coop(cfqq);
4499	cfq_clear_cfqq_split_coop(cfqq);
4500	return cfqq;
4501	}
4502
4503	cic_set_cfqq(cic, NULL, 1);
4504
4505	cfq_put_cooperator(cfqq);
4506
4507	cfq_put_queue(cfqq);
4508	return NULL;
4509	}
4510	/*
4511	* Allocate cfq data structures associated with this request.
4512	*/
4513	static int
4514	cfq_set_request(struct request_queue *q, struct request *rq, struct bio *bio,
4515	gfp_t gfp_mask)
4516	{
4517	struct cfq_data *cfqd = q->elevator->elevator_data;
4518	struct cfq_io_cq *cic = icq_to_cic(rq->elv.icq);
4519	const int rw = rq_data_dir(rq);
4520	const bool is_sync = rq_is_sync(rq);
4521	struct cfq_queue *cfqq;
4522
4523	spin_lock_irq(q->queue_lock);
4524
4525	check_ioprio_changed(cic, bio);
4526	check_blkcg_changed(cic, bio);
4527	new_queue:
4528	cfqq = cic_to_cfqq(cic, is_sync);
4529	if (!cfqq || cfqq == &cfqd->oom_cfqq) {
4530	if (cfqq)
4531	cfq_put_queue(cfqq);
4532	cfqq = cfq_get_queue(cfqd, is_sync, cic, bio);
4533	cic_set_cfqq(cic, cfqq, is_sync);
4534	} else {
4535	/*
4536	* If the queue was seeky for too long, break it apart.
4537	*/
4538	if (cfq_cfqq_coop(cfqq) && cfq_cfqq_split_coop(cfqq)) {
4539	cfq_log_cfqq(cfqd, cfqq, "breaking apart cfqq");
4540	cfqq = split_cfqq(cic, cfqq);
4541	if (!cfqq)
4542	goto new_queue;
4543	}
4544
4545	/*
4546	* Check to see if this queue is scheduled to merge with
4547	* another, closely cooperating queue. The merging of
4548	* queues happens here as it must be done in process context.
4549	* The reference on new_cfqq was taken in merge_cfqqs.
4550	*/
4551	if (cfqq->new_cfqq)
4552	cfqq = cfq_merge_cfqqs(cfqd, cic, cfqq);
4553	}
4554
4555	cfqq->allocated[rw]++;
4556
4557	cfqq->ref++;
4558	cfqg_get(cfqq->cfqg);
4559	rq->elv.priv[0] = cfqq;
4560	rq->elv.priv[1] = cfqq->cfqg;
4561	spin_unlock_irq(q->queue_lock);
4562	return 0;
4563	}
4564
4565	static void cfq_kick_queue(struct work_struct *work)
4566	{
4567	struct cfq_data *cfqd =
4568	container_of(work, struct cfq_data, unplug_work);
4569	struct request_queue *q = cfqd->queue;
4570
4571	spin_lock_irq(q->queue_lock);
4572	__blk_run_queue(cfqd->queue);
4573	spin_unlock_irq(q->queue_lock);
4574	}
4575
4576	/*
4577	* Timer running if the active_queue is currently idling inside its time slice
4578	*/
4579	static enum hrtimer_restart cfq_idle_slice_timer(struct hrtimer *timer)
4580	{
4581	struct cfq_data *cfqd = container_of(timer, struct cfq_data,
4582	idle_slice_timer);
4583	struct cfq_queue *cfqq;
4584	unsigned long flags;
4585	int timed_out = 1;
4586
4587	cfq_log(cfqd, "idle timer fired");
4588
4589	spin_lock_irqsave(cfqd->queue->queue_lock, flags);
4590
4591	cfqq = cfqd->active_queue;
4592	if (cfqq) {
4593	timed_out = 0;
4594
4595	/*
4596	* We saw a request before the queue expired, let it through
4597	*/
4598	if (cfq_cfqq_must_dispatch(cfqq))
4599	goto out_kick;
4600
4601	/*
4602	* expired
4603	*/
4604	if (cfq_slice_used(cfqq))
4605	goto expire;
4606
4607	/*
4608	* only expire and reinvoke request handler, if there are
4609	* other queues with pending requests
4610	*/
4611	if (!cfqd->busy_queues)
4612	goto out_cont;
4613
4614	/*
4615	* not expired and it has a request pending, let it dispatch
4616	*/
4617	if (!RB_EMPTY_ROOT(&cfqq->sort_list))
4618	goto out_kick;
4619
4620	/*
4621	* Queue depth flag is reset only when the idle didn't succeed
4622	*/
4623	cfq_clear_cfqq_deep(cfqq);
4624	}
4625	expire:
4626	cfq_slice_expired(cfqd, timed_out);
4627	out_kick:
4628	cfq_schedule_dispatch(cfqd);
4629	out_cont:
4630	spin_unlock_irqrestore(cfqd->queue->queue_lock, flags);
4631	return HRTIMER_NORESTART;
4632	}
4633
4634	static void cfq_shutdown_timer_wq(struct cfq_data *cfqd)
4635	{
4636	hrtimer_cancel(&cfqd->idle_slice_timer);
4637	cancel_work_sync(&cfqd->unplug_work);
4638	}
4639
4640	static void cfq_exit_queue(struct elevator_queue *e)
4641	{
4642	struct cfq_data *cfqd = e->elevator_data;
4643	struct request_queue *q = cfqd->queue;
4644
4645	cfq_shutdown_timer_wq(cfqd);
4646
4647	spin_lock_irq(q->queue_lock);
4648
4649	if (cfqd->active_queue)
4650	__cfq_slice_expired(cfqd, cfqd->active_queue, 0);
4651
4652	spin_unlock_irq(q->queue_lock);
4653
4654	cfq_shutdown_timer_wq(cfqd);
4655
4656	#ifdef CONFIG_CFQ_GROUP_IOSCHED
4657	blkcg_deactivate_policy(q, &blkcg_policy_cfq);
4658	#else
4659	kfree(cfqd->root_group);
4660	#endif
4661	kfree(cfqd);
4662	}
4663
4664	static int cfq_init_queue(struct request_queue *q, struct elevator_type *e)
4665	{
4666	struct cfq_data *cfqd;
4667	struct blkcg_gq *blkg __maybe_unused;
4668	int i, ret;
4669	struct elevator_queue *eq;
4670
4671	eq = elevator_alloc(q, e);
4672	if (!eq)
4673	return -ENOMEM;
4674
4675	cfqd = kzalloc_node(sizeof(*cfqd), GFP_KERNEL, q->node);
4676	if (!cfqd) {
4677	kobject_put(&eq->kobj);
4678	return -ENOMEM;
4679	}
4680	eq->elevator_data = cfqd;
4681
4682	cfqd->queue = q;
4683	spin_lock_irq(q->queue_lock);
4684	q->elevator = eq;
4685	spin_unlock_irq(q->queue_lock);
4686
4687	/* Init root service tree */
4688	cfqd->grp_service_tree = CFQ_RB_ROOT;
4689
4690	/* Init root group and prefer root group over other groups by default */
4691	#ifdef CONFIG_CFQ_GROUP_IOSCHED
4692	ret = blkcg_activate_policy(q, &blkcg_policy_cfq);
4693	if (ret)
4694	goto out_free;
4695
4696	cfqd->root_group = blkg_to_cfqg(q->root_blkg);
4697	#else
4698	ret = -ENOMEM;
4699	cfqd->root_group = kzalloc_node(sizeof(*cfqd->root_group),
4700	GFP_KERNEL, cfqd->queue->node);
4701	if (!cfqd->root_group)
4702	goto out_free;
4703
4704	cfq_init_cfqg_base(cfqd->root_group);
4705	cfqd->root_group->weight = 2 * CFQ_WEIGHT_LEGACY_DFL;
4706	cfqd->root_group->leaf_weight = 2 * CFQ_WEIGHT_LEGACY_DFL;
4707	#endif
4708
4709	/*
4710	* Not strictly needed (since RB_ROOT just clears the node and we
4711	* zeroed cfqd on alloc), but better be safe in case someone decides
4712	* to add magic to the rb code
4713	*/
4714	for (i = 0; i < CFQ_PRIO_LISTS; i++)
4715	cfqd->prio_trees[i] = RB_ROOT;
4716
4717	/*
4718	* Our fallback cfqq if cfq_get_queue() runs into OOM issues.
4719	* Grab a permanent reference to it, so that the normal code flow
4720	* will not attempt to free it. oom_cfqq is linked to root_group
4721	* but shouldn't hold a reference as it'll never be unlinked. Lose
4722	* the reference from linking right away.
4723	*/
4724	cfq_init_cfqq(cfqd, &cfqd->oom_cfqq, 1, 0);
4725	cfqd->oom_cfqq.ref++;
4726
4727	spin_lock_irq(q->queue_lock);
4728	cfq_link_cfqq_cfqg(&cfqd->oom_cfqq, cfqd->root_group);
4729	cfqg_put(cfqd->root_group);
4730	spin_unlock_irq(q->queue_lock);
4731
4732	hrtimer_init(&cfqd->idle_slice_timer, CLOCK_MONOTONIC,
4733	HRTIMER_MODE_REL);
4734	cfqd->idle_slice_timer.function = cfq_idle_slice_timer;
4735
4736	INIT_WORK(&cfqd->unplug_work, cfq_kick_queue);
4737
4738	cfqd->cfq_quantum = cfq_quantum;
4739	cfqd->cfq_fifo_expire[0] = cfq_fifo_expire[0];
4740	cfqd->cfq_fifo_expire[1] = cfq_fifo_expire[1];
4741	cfqd->cfq_back_max = cfq_back_max;
4742	cfqd->cfq_back_penalty = cfq_back_penalty;
4743	cfqd->cfq_slice[0] = cfq_slice_async;
4744	cfqd->cfq_slice[1] = cfq_slice_sync;
4745	cfqd->cfq_target_latency = cfq_target_latency;
4746	cfqd->cfq_slice_async_rq = cfq_slice_async_rq;
4747	cfqd->cfq_slice_idle = cfq_slice_idle;
4748	cfqd->cfq_group_idle = cfq_group_idle;
4749	cfqd->cfq_latency = 1;
4750	cfqd->hw_tag = -1;
4751	/*
4752	* we optimistically start assuming sync ops weren't delayed in last
4753	* second, in order to have larger depth for async operations.
4754	*/
4755	cfqd->last_delayed_sync = ktime_get_ns() - NSEC_PER_SEC;
4756	return 0;
4757
4758	out_free:
4759	kfree(cfqd);
4760	kobject_put(&eq->kobj);
4761	return ret;
4762	}
4763
4764	static void cfq_registered_queue(struct request_queue *q)
4765	{
4766	struct elevator_queue *e = q->elevator;
4767	struct cfq_data *cfqd = e->elevator_data;
4768
4769	/*
4770	* Default to IOPS mode with no idling for SSDs
4771	*/
4772	if (blk_queue_nonrot(q))
4773	cfqd->cfq_slice_idle = 0;
4774	}
4775
4776	/*
4777	* sysfs parts below -->
4778	*/
4779	static ssize_t
4780	cfq_var_show(unsigned int var, char *page)
4781	{
4782	return sprintf(page, "%u\n", var);
4783	}
4784
4785	static ssize_t
4786	cfq_var_store(unsigned int *var, const char *page, size_t count)
4787	{
4788	char *p = (char *) page;
4789
4790	*var = simple_strtoul(p, &p, 10);
4791	return count;
4792	}
4793
4794	#define SHOW_FUNCTION(__FUNC, __VAR, __CONV) \
4795	static ssize_t __FUNC(struct elevator_queue *e, char *page) \
4796	{ \
4797	struct cfq_data *cfqd = e->elevator_data; \
4798	u64 __data = __VAR; \
4799	if (__CONV) \
4800	__data = div_u64(__data, NSEC_PER_MSEC); \
4801	return cfq_var_show(__data, (page)); \
4802	}
4803	SHOW_FUNCTION(cfq_quantum_show, cfqd->cfq_quantum, 0);
4804	SHOW_FUNCTION(cfq_fifo_expire_sync_show, cfqd->cfq_fifo_expire[1], 1);
4805	SHOW_FUNCTION(cfq_fifo_expire_async_show, cfqd->cfq_fifo_expire[0], 1);
4806	SHOW_FUNCTION(cfq_back_seek_max_show, cfqd->cfq_back_max, 0);
4807	SHOW_FUNCTION(cfq_back_seek_penalty_show, cfqd->cfq_back_penalty, 0);
4808	SHOW_FUNCTION(cfq_slice_idle_show, cfqd->cfq_slice_idle, 1);
4809	SHOW_FUNCTION(cfq_group_idle_show, cfqd->cfq_group_idle, 1);
4810	SHOW_FUNCTION(cfq_slice_sync_show, cfqd->cfq_slice[1], 1);
4811	SHOW_FUNCTION(cfq_slice_async_show, cfqd->cfq_slice[0], 1);
4812	SHOW_FUNCTION(cfq_slice_async_rq_show, cfqd->cfq_slice_async_rq, 0);
4813	SHOW_FUNCTION(cfq_low_latency_show, cfqd->cfq_latency, 0);
4814	SHOW_FUNCTION(cfq_target_latency_show, cfqd->cfq_target_latency, 1);
4815	#undef SHOW_FUNCTION
4816
4817	#define USEC_SHOW_FUNCTION(__FUNC, __VAR) \
4818	static ssize_t __FUNC(struct elevator_queue *e, char *page) \
4819	{ \
4820	struct cfq_data *cfqd = e->elevator_data; \
4821	u64 __data = __VAR; \
4822	__data = div_u64(__data, NSEC_PER_USEC); \
4823	return cfq_var_show(__data, (page)); \
4824	}
4825	USEC_SHOW_FUNCTION(cfq_slice_idle_us_show, cfqd->cfq_slice_idle);
4826	USEC_SHOW_FUNCTION(cfq_group_idle_us_show, cfqd->cfq_group_idle);
4827	USEC_SHOW_FUNCTION(cfq_slice_sync_us_show, cfqd->cfq_slice[1]);
4828	USEC_SHOW_FUNCTION(cfq_slice_async_us_show, cfqd->cfq_slice[0]);
4829	USEC_SHOW_FUNCTION(cfq_target_latency_us_show, cfqd->cfq_target_latency);
4830	#undef USEC_SHOW_FUNCTION
4831
4832	#define STORE_FUNCTION(__FUNC, __PTR, MIN, MAX, __CONV) \
4833	static ssize_t __FUNC(struct elevator_queue *e, const char *page, size_t count) \
4834	{ \
4835	struct cfq_data *cfqd = e->elevator_data; \
4836	unsigned int __data; \
4837	int ret = cfq_var_store(&__data, (page), count); \
4838	if (__data < (MIN)) \
4839	__data = (MIN); \
4840	else if (__data > (MAX)) \
4841	__data = (MAX); \
4842	if (__CONV) \
4843	*(__PTR) = (u64)__data * NSEC_PER_MSEC; \
4844	else \
4845	*(__PTR) = __data; \
4846	return ret; \
4847	}
4848	STORE_FUNCTION(cfq_quantum_store, &cfqd->cfq_quantum, 1, UINT_MAX, 0);
4849	STORE_FUNCTION(cfq_fifo_expire_sync_store, &cfqd->cfq_fifo_expire[1], 1,
4850	UINT_MAX, 1);
4851	STORE_FUNCTION(cfq_fifo_expire_async_store, &cfqd->cfq_fifo_expire[0], 1,
4852	UINT_MAX, 1);
4853	STORE_FUNCTION(cfq_back_seek_max_store, &cfqd->cfq_back_max, 0, UINT_MAX, 0);
4854	STORE_FUNCTION(cfq_back_seek_penalty_store, &cfqd->cfq_back_penalty, 1,
4855	UINT_MAX, 0);
4856	STORE_FUNCTION(cfq_slice_idle_store, &cfqd->cfq_slice_idle, 0, UINT_MAX, 1);
4857	STORE_FUNCTION(cfq_group_idle_store, &cfqd->cfq_group_idle, 0, UINT_MAX, 1);
4858	STORE_FUNCTION(cfq_slice_sync_store, &cfqd->cfq_slice[1], 1, UINT_MAX, 1);
4859	STORE_FUNCTION(cfq_slice_async_store, &cfqd->cfq_slice[0], 1, UINT_MAX, 1);
4860	STORE_FUNCTION(cfq_slice_async_rq_store, &cfqd->cfq_slice_async_rq, 1,
4861	UINT_MAX, 0);
4862	STORE_FUNCTION(cfq_low_latency_store, &cfqd->cfq_latency, 0, 1, 0);
4863	STORE_FUNCTION(cfq_target_latency_store, &cfqd->cfq_target_latency, 1, UINT_MAX, 1);
4864	#undef STORE_FUNCTION
4865
4866	#define USEC_STORE_FUNCTION(__FUNC, __PTR, MIN, MAX) \
4867	static ssize_t __FUNC(struct elevator_queue *e, const char *page, size_t count) \
4868	{ \
4869	struct cfq_data *cfqd = e->elevator_data; \
4870	unsigned int __data; \
4871	int ret = cfq_var_store(&__data, (page), count); \
4872	if (__data < (MIN)) \
4873	__data = (MIN); \
4874	else if (__data > (MAX)) \
4875	__data = (MAX); \
4876	*(__PTR) = (u64)__data * NSEC_PER_USEC; \
4877	return ret; \
4878	}
4879	USEC_STORE_FUNCTION(cfq_slice_idle_us_store, &cfqd->cfq_slice_idle, 0, UINT_MAX);
4880	USEC_STORE_FUNCTION(cfq_group_idle_us_store, &cfqd->cfq_group_idle, 0, UINT_MAX);
4881	USEC_STORE_FUNCTION(cfq_slice_sync_us_store, &cfqd->cfq_slice[1], 1, UINT_MAX);
4882	USEC_STORE_FUNCTION(cfq_slice_async_us_store, &cfqd->cfq_slice[0], 1, UINT_MAX);
4883	USEC_STORE_FUNCTION(cfq_target_latency_us_store, &cfqd->cfq_target_latency, 1, UINT_MAX);
4884	#undef USEC_STORE_FUNCTION
4885
4886	#define CFQ_ATTR(name) \
4887	__ATTR(name, S_IRUGO|S_IWUSR, cfq_##name##_show, cfq_##name##_store)
4888
4889	static struct elv_fs_entry cfq_attrs[] = {
4890	CFQ_ATTR(quantum),
4891	CFQ_ATTR(fifo_expire_sync),
4892	CFQ_ATTR(fifo_expire_async),
4893	CFQ_ATTR(back_seek_max),
4894	CFQ_ATTR(back_seek_penalty),
4895	CFQ_ATTR(slice_sync),
4896	CFQ_ATTR(slice_sync_us),
4897	CFQ_ATTR(slice_async),
4898	CFQ_ATTR(slice_async_us),
4899	CFQ_ATTR(slice_async_rq),
4900	CFQ_ATTR(slice_idle),
4901	CFQ_ATTR(slice_idle_us),
4902	CFQ_ATTR(group_idle),
4903	CFQ_ATTR(group_idle_us),
4904	CFQ_ATTR(low_latency),
4905	CFQ_ATTR(target_latency),
4906	CFQ_ATTR(target_latency_us),
4907	__ATTR_NULL
4908	};
4909
4910	static struct elevator_type iosched_cfq = {
4911	.ops = {
4912	.elevator_merge_fn = cfq_merge,
4913	.elevator_merged_fn = cfq_merged_request,
4914	.elevator_merge_req_fn = cfq_merged_requests,
4915	.elevator_allow_bio_merge_fn = cfq_allow_bio_merge,
4916	.elevator_allow_rq_merge_fn = cfq_allow_rq_merge,
4917	.elevator_bio_merged_fn = cfq_bio_merged,
4918	.elevator_dispatch_fn = cfq_dispatch_requests,
4919	.elevator_add_req_fn = cfq_insert_request,
4920	.elevator_activate_req_fn = cfq_activate_request,
4921	.elevator_deactivate_req_fn = cfq_deactivate_request,
4922	.elevator_completed_req_fn = cfq_completed_request,
4923	.elevator_former_req_fn = elv_rb_former_request,
4924	.elevator_latter_req_fn = elv_rb_latter_request,
4925	.elevator_init_icq_fn = cfq_init_icq,
4926	.elevator_exit_icq_fn = cfq_exit_icq,
4927	.elevator_set_req_fn = cfq_set_request,
4928	.elevator_put_req_fn = cfq_put_request,
4929	.elevator_may_queue_fn = cfq_may_queue,
4930	.elevator_init_fn = cfq_init_queue,
4931	.elevator_exit_fn = cfq_exit_queue,
4932	.elevator_registered_fn = cfq_registered_queue,
4933	},
4934	.icq_size = sizeof(struct cfq_io_cq),
4935	.icq_align = __alignof__(struct cfq_io_cq),
4936	.elevator_attrs = cfq_attrs,
4937	.elevator_name = "cfq",
4938	.elevator_owner = THIS_MODULE,
4939	};
4940
4941	#ifdef CONFIG_CFQ_GROUP_IOSCHED
4942	static struct blkcg_policy blkcg_policy_cfq = {
4943	.dfl_cftypes = cfq_blkcg_files,
4944	.legacy_cftypes = cfq_blkcg_legacy_files,
4945
4946	.cpd_alloc_fn = cfq_cpd_alloc,
4947	.cpd_init_fn = cfq_cpd_init,
4948	.cpd_free_fn = cfq_cpd_free,
4949	.cpd_bind_fn = cfq_cpd_bind,
4950
4951	.pd_alloc_fn = cfq_pd_alloc,
4952	.pd_init_fn = cfq_pd_init,
4953	.pd_offline_fn = cfq_pd_offline,
4954	.pd_free_fn = cfq_pd_free,
4955	.pd_reset_stats_fn = cfq_pd_reset_stats,
4956	};
4957	#endif
4958
4959	static int __init cfq_init(void)
4960	{
4961	int ret;
4962
4963	#ifdef CONFIG_CFQ_GROUP_IOSCHED
4964	ret = blkcg_policy_register(&blkcg_policy_cfq);
4965	if (ret)
4966	return ret;
4967	#else
4968	cfq_group_idle = 0;
4969	#endif
4970
4971	ret = -ENOMEM;
4972	cfq_pool = KMEM_CACHE(cfq_queue, 0);
4973	if (!cfq_pool)
4974	goto err_pol_unreg;
4975
4976	ret = elv_register(&iosched_cfq);
4977	if (ret)
4978	goto err_free_pool;
4979
4980	return 0;
4981
4982	err_free_pool:
4983	kmem_cache_destroy(cfq_pool);
4984	err_pol_unreg:
4985	#ifdef CONFIG_CFQ_GROUP_IOSCHED
4986	blkcg_policy_unregister(&blkcg_policy_cfq);
4987	#endif
4988	return ret;
4989	}
4990
4991	static void __exit cfq_exit(void)
4992	{
4993	#ifdef CONFIG_CFQ_GROUP_IOSCHED
4994	blkcg_policy_unregister(&blkcg_policy_cfq);
4995	#endif
4996	elv_unregister(&iosched_cfq);
4997	kmem_cache_destroy(cfq_pool);
4998	}
4999
5000	module_init(cfq_init);
5001	module_exit(cfq_exit);
5002
5003	MODULE_AUTHOR("Jens Axboe");
5004	MODULE_LICENSE("GPL");
5005	MODULE_DESCRIPTION("Completely Fair Queueing IO scheduler");
5006