blob: 838834be115b3f341f3bc6e0eba54a5c3fcc424c [file] [log] [blame]
Linus Torvalds1da177e2005-04-16 15:20:36 -07001/*
Linus Torvalds1da177e2005-04-16 15:20:36 -07002 * 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 *
Jens Axboe0fe23472006-09-04 15:41:16 +02007 * Copyright (C) 2003 Jens Axboe <axboe@kernel.dk>
Linus Torvalds1da177e2005-04-16 15:20:36 -07008 */
Linus Torvalds1da177e2005-04-16 15:20:36 -07009#include <linux/module.h>
Tejun Heo5a0e3ad2010-03-24 17:04:11 +090010#include <linux/slab.h>
Al Viro1cc9be62006-03-18 12:29:52 -050011#include <linux/blkdev.h>
12#include <linux/elevator.h>
Randy Dunlapad5ebd22009-11-11 13:47:45 +010013#include <linux/jiffies.h>
Linus Torvalds1da177e2005-04-16 15:20:36 -070014#include <linux/rbtree.h>
Jens Axboe22e2c502005-06-27 10:55:12 +020015#include <linux/ioprio.h>
Jens Axboe7b679132008-05-30 12:23:07 +020016#include <linux/blktrace_api.h>
Vivek Goyal25bc6b02009-12-03 12:59:43 -050017#include "blk-cgroup.h"
Linus Torvalds1da177e2005-04-16 15:20:36 -070018
19/*
20 * tunables
21 */
Jens Axboefe094d92008-01-31 13:08:54 +010022/* max queue in one round of service */
Shaohua Liabc3c742010-03-01 09:20:54 +010023static const int cfq_quantum = 8;
Arjan van de Ven64100092006-01-06 09:46:02 +010024static const int cfq_fifo_expire[2] = { HZ / 4, HZ / 8 };
Jens Axboefe094d92008-01-31 13:08:54 +010025/* maximum backwards seek, in KiB */
26static const int cfq_back_max = 16 * 1024;
27/* penalty of a backwards seek */
28static const int cfq_back_penalty = 2;
Arjan van de Ven64100092006-01-06 09:46:02 +010029static const int cfq_slice_sync = HZ / 10;
Jens Axboe3b181522005-06-27 10:56:24 +020030static int cfq_slice_async = HZ / 25;
Arjan van de Ven64100092006-01-06 09:46:02 +010031static const int cfq_slice_async_rq = 2;
Jens Axboecaaa5f92006-06-16 11:23:00 +020032static int cfq_slice_idle = HZ / 125;
Corrado Zoccolo5db5d642009-10-26 22:44:04 +010033static const int cfq_target_latency = HZ * 3/10; /* 300 ms */
34static const int cfq_hist_divisor = 4;
Jens Axboe22e2c502005-06-27 10:55:12 +020035
Jens Axboed9e76202007-04-20 14:27:50 +020036/*
Jens Axboe08717142008-01-28 11:38:15 +010037 * offset from end of service tree
Jens Axboed9e76202007-04-20 14:27:50 +020038 */
Jens Axboe08717142008-01-28 11:38:15 +010039#define CFQ_IDLE_DELAY (HZ / 5)
Jens Axboed9e76202007-04-20 14:27:50 +020040
41/*
42 * below this threshold, we consider thinktime immediate
43 */
44#define CFQ_MIN_TT (2)
45
Jens Axboe22e2c502005-06-27 10:55:12 +020046#define CFQ_SLICE_SCALE (5)
Aaron Carroll45333d52008-08-26 15:52:36 +020047#define CFQ_HW_QUEUE_MIN (5)
Vivek Goyal25bc6b02009-12-03 12:59:43 -050048#define CFQ_SERVICE_SHIFT 12
Jens Axboe22e2c502005-06-27 10:55:12 +020049
Corrado Zoccolo3dde36d2010-02-27 19:45:39 +010050#define CFQQ_SEEK_THR (sector_t)(8 * 100)
Shaohua Lie9ce3352010-03-19 08:03:04 +010051#define CFQQ_CLOSE_THR (sector_t)(8 * 1024)
Corrado Zoccolo41647e72010-02-27 19:45:40 +010052#define CFQQ_SECT_THR_NONROT (sector_t)(2 * 32)
Corrado Zoccolo3dde36d2010-02-27 19:45:39 +010053#define CFQQ_SEEKY(cfqq) (hweight32(cfqq->seek_history) > 32/8)
Shaohua Liae54abe2010-02-05 13:11:45 +010054
Jens Axboefe094d92008-01-31 13:08:54 +010055#define RQ_CIC(rq) \
56 ((struct cfq_io_context *) (rq)->elevator_private)
Jens Axboe7b679132008-05-30 12:23:07 +020057#define RQ_CFQQ(rq) (struct cfq_queue *) ((rq)->elevator_private2)
Linus Torvalds1da177e2005-04-16 15:20:36 -070058
Christoph Lametere18b8902006-12-06 20:33:20 -080059static struct kmem_cache *cfq_pool;
60static struct kmem_cache *cfq_ioc_pool;
Linus Torvalds1da177e2005-04-16 15:20:36 -070061
Tejun Heo245b2e72009-06-24 15:13:48 +090062static DEFINE_PER_CPU(unsigned long, cfq_ioc_count);
Al Viro334e94d2006-03-18 15:05:53 -050063static struct completion *ioc_gone;
Jens Axboe9a11b4e2008-05-29 09:32:08 +020064static DEFINE_SPINLOCK(ioc_gone_lock);
Al Viro334e94d2006-03-18 15:05:53 -050065
Jens Axboe22e2c502005-06-27 10:55:12 +020066#define CFQ_PRIO_LISTS IOPRIO_BE_NR
67#define cfq_class_idle(cfqq) ((cfqq)->ioprio_class == IOPRIO_CLASS_IDLE)
Jens Axboe22e2c502005-06-27 10:55:12 +020068#define cfq_class_rt(cfqq) ((cfqq)->ioprio_class == IOPRIO_CLASS_RT)
69
Jens Axboe206dc692006-03-28 13:03:44 +020070#define sample_valid(samples) ((samples) > 80)
Vivek Goyal1fa8f6d2009-12-03 12:59:41 -050071#define rb_entry_cfqg(node) rb_entry((node), struct cfq_group, rb_node)
Jens Axboe206dc692006-03-28 13:03:44 +020072
Jens Axboe22e2c502005-06-27 10:55:12 +020073/*
Jens Axboecc09e292007-04-26 12:53:50 +020074 * Most of our rbtree usage is for sorting with min extraction, so
75 * if we cache the leftmost node we don't have to walk down the tree
76 * to find it. Idea borrowed from Ingo Molnars CFS scheduler. We should
77 * move this into the elevator for the rq sorting as well.
78 */
79struct cfq_rb_root {
80 struct rb_root rb;
81 struct rb_node *left;
Corrado Zoccoloaa6f6a32009-10-26 22:44:33 +010082 unsigned count;
Richard Kennedy73e9ffd2010-03-01 10:50:20 +010083 unsigned total_weight;
Vivek Goyal1fa8f6d2009-12-03 12:59:41 -050084 u64 min_vdisktime;
Vivek Goyal25bc6b02009-12-03 12:59:43 -050085 struct rb_node *active;
Jens Axboecc09e292007-04-26 12:53:50 +020086};
Richard Kennedy73e9ffd2010-03-01 10:50:20 +010087#define CFQ_RB_ROOT (struct cfq_rb_root) { .rb = RB_ROOT, .left = NULL, \
88 .count = 0, .min_vdisktime = 0, }
Jens Axboecc09e292007-04-26 12:53:50 +020089
90/*
Jens Axboe6118b702009-06-30 09:34:12 +020091 * Per process-grouping structure
92 */
93struct cfq_queue {
94 /* reference count */
95 atomic_t ref;
96 /* various state flags, see below */
97 unsigned int flags;
98 /* parent cfq_data */
99 struct cfq_data *cfqd;
100 /* service_tree member */
101 struct rb_node rb_node;
102 /* service_tree key */
103 unsigned long rb_key;
104 /* prio tree member */
105 struct rb_node p_node;
106 /* prio tree root we belong to, if any */
107 struct rb_root *p_root;
108 /* sorted list of pending requests */
109 struct rb_root sort_list;
110 /* if fifo isn't expired, next request to serve */
111 struct request *next_rq;
112 /* requests queued in sort_list */
113 int queued[2];
114 /* currently allocated requests */
115 int allocated[2];
116 /* fifo list of requests in sort_list */
117 struct list_head fifo;
118
Vivek Goyaldae739e2009-12-03 12:59:45 -0500119 /* time when queue got scheduled in to dispatch first request. */
120 unsigned long dispatch_start;
Vivek Goyalf75edf22009-12-03 12:59:53 -0500121 unsigned int allocated_slice;
Richard Kennedyc4081ba2010-02-22 13:49:24 +0100122 unsigned int slice_dispatch;
Vivek Goyaldae739e2009-12-03 12:59:45 -0500123 /* time when first request from queue completed and slice started. */
124 unsigned long slice_start;
Jens Axboe6118b702009-06-30 09:34:12 +0200125 unsigned long slice_end;
126 long slice_resid;
Jens Axboe6118b702009-06-30 09:34:12 +0200127
128 /* pending metadata requests */
129 int meta_pending;
130 /* number of requests that are on the dispatch list or inside driver */
131 int dispatched;
132
133 /* io prio of this group */
134 unsigned short ioprio, org_ioprio;
135 unsigned short ioprio_class, org_ioprio_class;
136
Richard Kennedyc4081ba2010-02-22 13:49:24 +0100137 pid_t pid;
138
Corrado Zoccolo3dde36d2010-02-27 19:45:39 +0100139 u32 seek_history;
Jeff Moyerb2c18e12009-10-23 17:14:49 -0400140 sector_t last_request_pos;
141
Corrado Zoccoloaa6f6a32009-10-26 22:44:33 +0100142 struct cfq_rb_root *service_tree;
Jeff Moyerdf5fe3e2009-10-23 17:14:50 -0400143 struct cfq_queue *new_cfqq;
Vivek Goyalcdb16e82009-12-03 12:59:38 -0500144 struct cfq_group *cfqg;
Vivek Goyalae30c282009-12-03 12:59:55 -0500145 struct cfq_group *orig_cfqg;
Vivek Goyal22084192009-12-03 12:59:49 -0500146 /* Sectors dispatched in current dispatch round */
147 unsigned long nr_sectors;
Jens Axboe6118b702009-06-30 09:34:12 +0200148};
149
150/*
Corrado Zoccolo718eee02009-10-26 22:45:29 +0100151 * First index in the service_trees.
Corrado Zoccoloc0324a02009-10-27 19:16:03 +0100152 * IDLE is handled separately, so it has negative index
153 */
154enum wl_prio_t {
Corrado Zoccoloc0324a02009-10-27 19:16:03 +0100155 BE_WORKLOAD = 0,
Vivek Goyal615f0252009-12-03 12:59:39 -0500156 RT_WORKLOAD = 1,
157 IDLE_WORKLOAD = 2,
Corrado Zoccoloc0324a02009-10-27 19:16:03 +0100158};
159
160/*
Corrado Zoccolo718eee02009-10-26 22:45:29 +0100161 * Second index in the service_trees.
162 */
163enum wl_type_t {
164 ASYNC_WORKLOAD = 0,
165 SYNC_NOIDLE_WORKLOAD = 1,
166 SYNC_WORKLOAD = 2
167};
168
Vivek Goyalcdb16e82009-12-03 12:59:38 -0500169/* This is per cgroup per device grouping structure */
170struct cfq_group {
Vivek Goyal1fa8f6d2009-12-03 12:59:41 -0500171 /* group service_tree member */
172 struct rb_node rb_node;
173
174 /* group service_tree key */
175 u64 vdisktime;
Vivek Goyal25bc6b02009-12-03 12:59:43 -0500176 unsigned int weight;
Vivek Goyal1fa8f6d2009-12-03 12:59:41 -0500177 bool on_st;
178
179 /* number of cfqq currently on this group */
180 int nr_cfqq;
181
Vivek Goyal58ff82f2009-12-03 12:59:44 -0500182 /* Per group busy queus average. Useful for workload slice calc. */
183 unsigned int busy_queues_avg[2];
Jens Axboe22e2c502005-06-27 10:55:12 +0200184 /*
Corrado Zoccoloc0324a02009-10-27 19:16:03 +0100185 * rr lists of queues with requests, onle rr for each priority class.
186 * Counts are embedded in the cfq_rb_root
Jens Axboe22e2c502005-06-27 10:55:12 +0200187 */
Corrado Zoccolo718eee02009-10-26 22:45:29 +0100188 struct cfq_rb_root service_trees[2][3];
Corrado Zoccoloc0324a02009-10-27 19:16:03 +0100189 struct cfq_rb_root service_tree_idle;
Vivek Goyaldae739e2009-12-03 12:59:45 -0500190
191 unsigned long saved_workload_slice;
192 enum wl_type_t saved_workload;
193 enum wl_prio_t saved_serving_prio;
Vivek Goyal25fb5162009-12-03 12:59:46 -0500194 struct blkio_group blkg;
195#ifdef CONFIG_CFQ_GROUP_IOSCHED
196 struct hlist_node cfqd_node;
Vivek Goyalb1c35762009-12-03 12:59:47 -0500197 atomic_t ref;
Vivek Goyal25fb5162009-12-03 12:59:46 -0500198#endif
Vivek Goyalcdb16e82009-12-03 12:59:38 -0500199};
200
201/*
202 * Per block device queue structure
203 */
204struct cfq_data {
205 struct request_queue *queue;
Vivek Goyal1fa8f6d2009-12-03 12:59:41 -0500206 /* Root service tree for cfq_groups */
207 struct cfq_rb_root grp_service_tree;
Vivek Goyalcdb16e82009-12-03 12:59:38 -0500208 struct cfq_group root_group;
209
Corrado Zoccoloc0324a02009-10-27 19:16:03 +0100210 /*
211 * The priority currently being served
212 */
213 enum wl_prio_t serving_prio;
Corrado Zoccolo718eee02009-10-26 22:45:29 +0100214 enum wl_type_t serving_type;
215 unsigned long workload_expires;
Vivek Goyalcdb16e82009-12-03 12:59:38 -0500216 struct cfq_group *serving_group;
Corrado Zoccolo8e550632009-11-26 10:02:58 +0100217 bool noidle_tree_requires_idle;
Jens Axboea36e71f2009-04-15 12:15:11 +0200218
219 /*
220 * Each priority tree is sorted by next_request position. These
221 * trees are used when determining if two or more queues are
222 * interleaving requests (see cfq_close_cooperator).
223 */
224 struct rb_root prio_trees[CFQ_PRIO_LISTS];
225
Jens Axboe22e2c502005-06-27 10:55:12 +0200226 unsigned int busy_queues;
227
Corrado Zoccolo53c583d2010-02-28 19:45:05 +0100228 int rq_in_driver;
229 int rq_in_flight[2];
Aaron Carroll45333d52008-08-26 15:52:36 +0200230
231 /*
232 * queue-depth detection
233 */
234 int rq_queued;
Jens Axboe25776e32006-06-01 10:12:26 +0200235 int hw_tag;
Corrado Zoccoloe459dd02009-11-26 10:02:57 +0100236 /*
237 * hw_tag can be
238 * -1 => indeterminate, (cfq will behave as if NCQ is present, to allow better detection)
239 * 1 => NCQ is present (hw_tag_est_depth is the estimated max depth)
240 * 0 => no NCQ
241 */
242 int hw_tag_est_depth;
243 unsigned int hw_tag_samples;
Jens Axboe22e2c502005-06-27 10:55:12 +0200244
245 /*
Jens Axboe22e2c502005-06-27 10:55:12 +0200246 * idle window management
247 */
248 struct timer_list idle_slice_timer;
Jens Axboe23e018a2009-10-05 08:52:35 +0200249 struct work_struct unplug_work;
Jens Axboe22e2c502005-06-27 10:55:12 +0200250
251 struct cfq_queue *active_queue;
252 struct cfq_io_context *active_cic;
Jens Axboe22e2c502005-06-27 10:55:12 +0200253
Vasily Tarasovc2dea2d2007-07-20 10:06:38 +0200254 /*
255 * async queue for each priority case
256 */
257 struct cfq_queue *async_cfqq[2][IOPRIO_BE_NR];
258 struct cfq_queue *async_idle_cfqq;
Jens Axboe15c31be2007-07-10 13:43:25 +0200259
Jens Axboe6d048f52007-04-25 12:44:27 +0200260 sector_t last_position;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700261
Linus Torvalds1da177e2005-04-16 15:20:36 -0700262 /*
263 * tunables, see top of file
264 */
265 unsigned int cfq_quantum;
Jens Axboe22e2c502005-06-27 10:55:12 +0200266 unsigned int cfq_fifo_expire[2];
Linus Torvalds1da177e2005-04-16 15:20:36 -0700267 unsigned int cfq_back_penalty;
268 unsigned int cfq_back_max;
Jens Axboe22e2c502005-06-27 10:55:12 +0200269 unsigned int cfq_slice[2];
270 unsigned int cfq_slice_async_rq;
271 unsigned int cfq_slice_idle;
Jens Axboe963b72f2009-10-03 19:42:18 +0200272 unsigned int cfq_latency;
Vivek Goyalae30c282009-12-03 12:59:55 -0500273 unsigned int cfq_group_isolation;
Al Virod9ff4182006-03-18 13:51:22 -0500274
275 struct list_head cic_list;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700276
Jens Axboe6118b702009-06-30 09:34:12 +0200277 /*
278 * Fallback dummy cfqq for extreme OOM conditions
279 */
280 struct cfq_queue oom_cfqq;
Vivek Goyal365722b2009-10-03 15:21:27 +0200281
Corrado Zoccolo573412b2009-12-06 11:48:52 +0100282 unsigned long last_delayed_sync;
Vivek Goyal25fb5162009-12-03 12:59:46 -0500283
284 /* List of cfq groups being managed on this device*/
285 struct hlist_head cfqg_list;
Jens Axboebb729bc2009-12-06 09:54:19 +0100286 struct rcu_head rcu;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700287};
288
Vivek Goyal25fb5162009-12-03 12:59:46 -0500289static struct cfq_group *cfq_get_next_cfqg(struct cfq_data *cfqd);
290
Vivek Goyalcdb16e82009-12-03 12:59:38 -0500291static struct cfq_rb_root *service_tree_for(struct cfq_group *cfqg,
292 enum wl_prio_t prio,
Vivek Goyal65b32a52009-12-16 17:52:59 -0500293 enum wl_type_t type)
Corrado Zoccoloc0324a02009-10-27 19:16:03 +0100294{
Vivek Goyal1fa8f6d2009-12-03 12:59:41 -0500295 if (!cfqg)
296 return NULL;
297
Corrado Zoccoloc0324a02009-10-27 19:16:03 +0100298 if (prio == IDLE_WORKLOAD)
Vivek Goyalcdb16e82009-12-03 12:59:38 -0500299 return &cfqg->service_tree_idle;
Corrado Zoccoloc0324a02009-10-27 19:16:03 +0100300
Vivek Goyalcdb16e82009-12-03 12:59:38 -0500301 return &cfqg->service_trees[prio][type];
Corrado Zoccoloc0324a02009-10-27 19:16:03 +0100302}
303
Jens Axboe3b181522005-06-27 10:56:24 +0200304enum cfqq_state_flags {
Jens Axboeb0b8d742007-01-19 11:35:30 +1100305 CFQ_CFQQ_FLAG_on_rr = 0, /* on round-robin busy list */
306 CFQ_CFQQ_FLAG_wait_request, /* waiting for a request */
Jens Axboeb0291952009-04-07 11:38:31 +0200307 CFQ_CFQQ_FLAG_must_dispatch, /* must be allowed a dispatch */
Jens Axboeb0b8d742007-01-19 11:35:30 +1100308 CFQ_CFQQ_FLAG_must_alloc_slice, /* per-slice must_alloc flag */
Jens Axboeb0b8d742007-01-19 11:35:30 +1100309 CFQ_CFQQ_FLAG_fifo_expire, /* FIFO checked in this slice */
310 CFQ_CFQQ_FLAG_idle_window, /* slice idling enabled */
311 CFQ_CFQQ_FLAG_prio_changed, /* task priority has changed */
Jens Axboe44f7c162007-01-19 11:51:58 +1100312 CFQ_CFQQ_FLAG_slice_new, /* no requests dispatched in slice */
Vasily Tarasov91fac312007-04-25 12:29:51 +0200313 CFQ_CFQQ_FLAG_sync, /* synchronous queue */
Jeff Moyerb3b6d042009-10-23 17:14:51 -0400314 CFQ_CFQQ_FLAG_coop, /* cfqq is shared */
Shaohua Liae54abe2010-02-05 13:11:45 +0100315 CFQ_CFQQ_FLAG_split_coop, /* shared cfqq will be splitted */
Corrado Zoccolo76280af2009-11-26 10:02:58 +0100316 CFQ_CFQQ_FLAG_deep, /* sync cfqq experienced large depth */
Vivek Goyalf75edf22009-12-03 12:59:53 -0500317 CFQ_CFQQ_FLAG_wait_busy, /* Waiting for next request */
Jens Axboe3b181522005-06-27 10:56:24 +0200318};
319
320#define CFQ_CFQQ_FNS(name) \
321static inline void cfq_mark_cfqq_##name(struct cfq_queue *cfqq) \
322{ \
Jens Axboefe094d92008-01-31 13:08:54 +0100323 (cfqq)->flags |= (1 << CFQ_CFQQ_FLAG_##name); \
Jens Axboe3b181522005-06-27 10:56:24 +0200324} \
325static inline void cfq_clear_cfqq_##name(struct cfq_queue *cfqq) \
326{ \
Jens Axboefe094d92008-01-31 13:08:54 +0100327 (cfqq)->flags &= ~(1 << CFQ_CFQQ_FLAG_##name); \
Jens Axboe3b181522005-06-27 10:56:24 +0200328} \
329static inline int cfq_cfqq_##name(const struct cfq_queue *cfqq) \
330{ \
Jens Axboefe094d92008-01-31 13:08:54 +0100331 return ((cfqq)->flags & (1 << CFQ_CFQQ_FLAG_##name)) != 0; \
Jens Axboe3b181522005-06-27 10:56:24 +0200332}
333
334CFQ_CFQQ_FNS(on_rr);
335CFQ_CFQQ_FNS(wait_request);
Jens Axboeb0291952009-04-07 11:38:31 +0200336CFQ_CFQQ_FNS(must_dispatch);
Jens Axboe3b181522005-06-27 10:56:24 +0200337CFQ_CFQQ_FNS(must_alloc_slice);
Jens Axboe3b181522005-06-27 10:56:24 +0200338CFQ_CFQQ_FNS(fifo_expire);
339CFQ_CFQQ_FNS(idle_window);
340CFQ_CFQQ_FNS(prio_changed);
Jens Axboe44f7c162007-01-19 11:51:58 +1100341CFQ_CFQQ_FNS(slice_new);
Vasily Tarasov91fac312007-04-25 12:29:51 +0200342CFQ_CFQQ_FNS(sync);
Jens Axboea36e71f2009-04-15 12:15:11 +0200343CFQ_CFQQ_FNS(coop);
Shaohua Liae54abe2010-02-05 13:11:45 +0100344CFQ_CFQQ_FNS(split_coop);
Corrado Zoccolo76280af2009-11-26 10:02:58 +0100345CFQ_CFQQ_FNS(deep);
Vivek Goyalf75edf22009-12-03 12:59:53 -0500346CFQ_CFQQ_FNS(wait_busy);
Jens Axboe3b181522005-06-27 10:56:24 +0200347#undef CFQ_CFQQ_FNS
348
Vivek Goyal2868ef72009-12-03 12:59:48 -0500349#ifdef CONFIG_DEBUG_CFQ_IOSCHED
350#define cfq_log_cfqq(cfqd, cfqq, fmt, args...) \
351 blk_add_trace_msg((cfqd)->queue, "cfq%d%c %s " fmt, (cfqq)->pid, \
352 cfq_cfqq_sync((cfqq)) ? 'S' : 'A', \
353 blkg_path(&(cfqq)->cfqg->blkg), ##args);
354
355#define cfq_log_cfqg(cfqd, cfqg, fmt, args...) \
356 blk_add_trace_msg((cfqd)->queue, "%s " fmt, \
357 blkg_path(&(cfqg)->blkg), ##args); \
358
359#else
Jens Axboe7b679132008-05-30 12:23:07 +0200360#define cfq_log_cfqq(cfqd, cfqq, fmt, args...) \
361 blk_add_trace_msg((cfqd)->queue, "cfq%d " fmt, (cfqq)->pid, ##args)
Vivek Goyal2868ef72009-12-03 12:59:48 -0500362#define cfq_log_cfqg(cfqd, cfqg, fmt, args...) do {} while (0);
363#endif
Jens Axboe7b679132008-05-30 12:23:07 +0200364#define cfq_log(cfqd, fmt, args...) \
365 blk_add_trace_msg((cfqd)->queue, "cfq " fmt, ##args)
366
Vivek Goyal615f0252009-12-03 12:59:39 -0500367/* Traverses through cfq group service trees */
368#define for_each_cfqg_st(cfqg, i, j, st) \
369 for (i = 0; i <= IDLE_WORKLOAD; i++) \
370 for (j = 0, st = i < IDLE_WORKLOAD ? &cfqg->service_trees[i][j]\
371 : &cfqg->service_tree_idle; \
372 (i < IDLE_WORKLOAD && j <= SYNC_WORKLOAD) || \
373 (i == IDLE_WORKLOAD && j == 0); \
374 j++, st = i < IDLE_WORKLOAD ? \
375 &cfqg->service_trees[i][j]: NULL) \
376
377
Corrado Zoccoloc0324a02009-10-27 19:16:03 +0100378static inline enum wl_prio_t cfqq_prio(struct cfq_queue *cfqq)
379{
380 if (cfq_class_idle(cfqq))
381 return IDLE_WORKLOAD;
382 if (cfq_class_rt(cfqq))
383 return RT_WORKLOAD;
384 return BE_WORKLOAD;
385}
386
Corrado Zoccolo718eee02009-10-26 22:45:29 +0100387
388static enum wl_type_t cfqq_type(struct cfq_queue *cfqq)
389{
390 if (!cfq_cfqq_sync(cfqq))
391 return ASYNC_WORKLOAD;
392 if (!cfq_cfqq_idle_window(cfqq))
393 return SYNC_NOIDLE_WORKLOAD;
394 return SYNC_WORKLOAD;
395}
396
Vivek Goyal58ff82f2009-12-03 12:59:44 -0500397static inline int cfq_group_busy_queues_wl(enum wl_prio_t wl,
398 struct cfq_data *cfqd,
399 struct cfq_group *cfqg)
Corrado Zoccoloc0324a02009-10-27 19:16:03 +0100400{
Vivek Goyalcdb16e82009-12-03 12:59:38 -0500401 if (wl == IDLE_WORKLOAD)
402 return cfqg->service_tree_idle.count;
403
404 return cfqg->service_trees[wl][ASYNC_WORKLOAD].count
405 + cfqg->service_trees[wl][SYNC_NOIDLE_WORKLOAD].count
406 + cfqg->service_trees[wl][SYNC_WORKLOAD].count;
Corrado Zoccoloc0324a02009-10-27 19:16:03 +0100407}
408
Vivek Goyalf26bd1f2009-12-03 12:59:54 -0500409static inline int cfqg_busy_async_queues(struct cfq_data *cfqd,
410 struct cfq_group *cfqg)
411{
412 return cfqg->service_trees[RT_WORKLOAD][ASYNC_WORKLOAD].count
413 + cfqg->service_trees[BE_WORKLOAD][ASYNC_WORKLOAD].count;
414}
415
Jens Axboe165125e2007-07-24 09:28:11 +0200416static void cfq_dispatch_insert(struct request_queue *, struct request *);
Jens Axboea6151c32009-10-07 20:02:57 +0200417static struct cfq_queue *cfq_get_queue(struct cfq_data *, bool,
Jens Axboefd0928d2008-01-24 08:52:45 +0100418 struct io_context *, gfp_t);
Jens Axboe4ac845a2008-01-24 08:44:49 +0100419static struct cfq_io_context *cfq_cic_lookup(struct cfq_data *,
Vasily Tarasov91fac312007-04-25 12:29:51 +0200420 struct io_context *);
421
422static inline struct cfq_queue *cic_to_cfqq(struct cfq_io_context *cic,
Jens Axboea6151c32009-10-07 20:02:57 +0200423 bool is_sync)
Vasily Tarasov91fac312007-04-25 12:29:51 +0200424{
Jens Axboea6151c32009-10-07 20:02:57 +0200425 return cic->cfqq[is_sync];
Vasily Tarasov91fac312007-04-25 12:29:51 +0200426}
427
428static inline void cic_set_cfqq(struct cfq_io_context *cic,
Jens Axboea6151c32009-10-07 20:02:57 +0200429 struct cfq_queue *cfqq, bool is_sync)
Vasily Tarasov91fac312007-04-25 12:29:51 +0200430{
Jens Axboea6151c32009-10-07 20:02:57 +0200431 cic->cfqq[is_sync] = cfqq;
Vasily Tarasov91fac312007-04-25 12:29:51 +0200432}
433
434/*
435 * We regard a request as SYNC, if it's either a read or has the SYNC bit
436 * set (in which case it could also be direct WRITE).
437 */
Jens Axboea6151c32009-10-07 20:02:57 +0200438static inline bool cfq_bio_sync(struct bio *bio)
Vasily Tarasov91fac312007-04-25 12:29:51 +0200439{
Jens Axboea6151c32009-10-07 20:02:57 +0200440 return bio_data_dir(bio) == READ || bio_rw_flagged(bio, BIO_RW_SYNCIO);
Vasily Tarasov91fac312007-04-25 12:29:51 +0200441}
Linus Torvalds1da177e2005-04-16 15:20:36 -0700442
Linus Torvalds1da177e2005-04-16 15:20:36 -0700443/*
Andrew Morton99f95e52005-06-27 20:14:05 -0700444 * scheduler run of queue, if there are requests pending and no one in the
445 * driver that will restart queueing
446 */
Jens Axboe23e018a2009-10-05 08:52:35 +0200447static inline void cfq_schedule_dispatch(struct cfq_data *cfqd)
Andrew Morton99f95e52005-06-27 20:14:05 -0700448{
Jens Axboe7b679132008-05-30 12:23:07 +0200449 if (cfqd->busy_queues) {
450 cfq_log(cfqd, "schedule dispatch");
Jens Axboe23e018a2009-10-05 08:52:35 +0200451 kblockd_schedule_work(cfqd->queue, &cfqd->unplug_work);
Jens Axboe7b679132008-05-30 12:23:07 +0200452 }
Andrew Morton99f95e52005-06-27 20:14:05 -0700453}
454
Jens Axboe165125e2007-07-24 09:28:11 +0200455static int cfq_queue_empty(struct request_queue *q)
Andrew Morton99f95e52005-06-27 20:14:05 -0700456{
457 struct cfq_data *cfqd = q->elevator->elevator_data;
458
Vivek Goyalf04a6422009-12-03 12:59:40 -0500459 return !cfqd->rq_queued;
Andrew Morton99f95e52005-06-27 20:14:05 -0700460}
461
Linus Torvalds1da177e2005-04-16 15:20:36 -0700462/*
Jens Axboe44f7c162007-01-19 11:51:58 +1100463 * Scale schedule slice based on io priority. Use the sync time slice only
464 * if a queue is marked sync and has sync io queued. A sync queue with async
465 * io only, should not get full sync slice length.
466 */
Jens Axboea6151c32009-10-07 20:02:57 +0200467static inline int cfq_prio_slice(struct cfq_data *cfqd, bool sync,
Jens Axboed9e76202007-04-20 14:27:50 +0200468 unsigned short prio)
469{
470 const int base_slice = cfqd->cfq_slice[sync];
471
472 WARN_ON(prio >= IOPRIO_BE_NR);
473
474 return base_slice + (base_slice/CFQ_SLICE_SCALE * (4 - prio));
475}
476
Jens Axboe44f7c162007-01-19 11:51:58 +1100477static inline int
478cfq_prio_to_slice(struct cfq_data *cfqd, struct cfq_queue *cfqq)
479{
Jens Axboed9e76202007-04-20 14:27:50 +0200480 return cfq_prio_slice(cfqd, cfq_cfqq_sync(cfqq), cfqq->ioprio);
Jens Axboe44f7c162007-01-19 11:51:58 +1100481}
482
Vivek Goyal25bc6b02009-12-03 12:59:43 -0500483static inline u64 cfq_scale_slice(unsigned long delta, struct cfq_group *cfqg)
484{
485 u64 d = delta << CFQ_SERVICE_SHIFT;
486
487 d = d * BLKIO_WEIGHT_DEFAULT;
488 do_div(d, cfqg->weight);
489 return d;
490}
491
492static inline u64 max_vdisktime(u64 min_vdisktime, u64 vdisktime)
493{
494 s64 delta = (s64)(vdisktime - min_vdisktime);
495 if (delta > 0)
496 min_vdisktime = vdisktime;
497
498 return min_vdisktime;
499}
500
501static inline u64 min_vdisktime(u64 min_vdisktime, u64 vdisktime)
502{
503 s64 delta = (s64)(vdisktime - min_vdisktime);
504 if (delta < 0)
505 min_vdisktime = vdisktime;
506
507 return min_vdisktime;
508}
509
510static void update_min_vdisktime(struct cfq_rb_root *st)
511{
512 u64 vdisktime = st->min_vdisktime;
513 struct cfq_group *cfqg;
514
515 if (st->active) {
516 cfqg = rb_entry_cfqg(st->active);
517 vdisktime = cfqg->vdisktime;
518 }
519
520 if (st->left) {
521 cfqg = rb_entry_cfqg(st->left);
522 vdisktime = min_vdisktime(vdisktime, cfqg->vdisktime);
523 }
524
525 st->min_vdisktime = max_vdisktime(st->min_vdisktime, vdisktime);
526}
527
Corrado Zoccolo5db5d642009-10-26 22:44:04 +0100528/*
529 * get averaged number of queues of RT/BE priority.
530 * average is updated, with a formula that gives more weight to higher numbers,
531 * to quickly follows sudden increases and decrease slowly
532 */
533
Vivek Goyal58ff82f2009-12-03 12:59:44 -0500534static inline unsigned cfq_group_get_avg_queues(struct cfq_data *cfqd,
535 struct cfq_group *cfqg, bool rt)
Jens Axboe58696192009-10-28 09:27:07 +0100536{
Corrado Zoccolo5db5d642009-10-26 22:44:04 +0100537 unsigned min_q, max_q;
538 unsigned mult = cfq_hist_divisor - 1;
539 unsigned round = cfq_hist_divisor / 2;
Vivek Goyal58ff82f2009-12-03 12:59:44 -0500540 unsigned busy = cfq_group_busy_queues_wl(rt, cfqd, cfqg);
Corrado Zoccolo5db5d642009-10-26 22:44:04 +0100541
Vivek Goyal58ff82f2009-12-03 12:59:44 -0500542 min_q = min(cfqg->busy_queues_avg[rt], busy);
543 max_q = max(cfqg->busy_queues_avg[rt], busy);
544 cfqg->busy_queues_avg[rt] = (mult * max_q + min_q + round) /
Corrado Zoccolo5db5d642009-10-26 22:44:04 +0100545 cfq_hist_divisor;
Vivek Goyal58ff82f2009-12-03 12:59:44 -0500546 return cfqg->busy_queues_avg[rt];
547}
548
549static inline unsigned
550cfq_group_slice(struct cfq_data *cfqd, struct cfq_group *cfqg)
551{
552 struct cfq_rb_root *st = &cfqd->grp_service_tree;
553
554 return cfq_target_latency * cfqg->weight / st->total_weight;
Corrado Zoccolo5db5d642009-10-26 22:44:04 +0100555}
556
Jens Axboe44f7c162007-01-19 11:51:58 +1100557static inline void
558cfq_set_prio_slice(struct cfq_data *cfqd, struct cfq_queue *cfqq)
559{
Corrado Zoccolo5db5d642009-10-26 22:44:04 +0100560 unsigned slice = cfq_prio_to_slice(cfqd, cfqq);
561 if (cfqd->cfq_latency) {
Vivek Goyal58ff82f2009-12-03 12:59:44 -0500562 /*
563 * interested queues (we consider only the ones with the same
564 * priority class in the cfq group)
565 */
566 unsigned iq = cfq_group_get_avg_queues(cfqd, cfqq->cfqg,
567 cfq_class_rt(cfqq));
Corrado Zoccolo5db5d642009-10-26 22:44:04 +0100568 unsigned sync_slice = cfqd->cfq_slice[1];
569 unsigned expect_latency = sync_slice * iq;
Vivek Goyal58ff82f2009-12-03 12:59:44 -0500570 unsigned group_slice = cfq_group_slice(cfqd, cfqq->cfqg);
571
572 if (expect_latency > group_slice) {
Corrado Zoccolo5db5d642009-10-26 22:44:04 +0100573 unsigned base_low_slice = 2 * cfqd->cfq_slice_idle;
574 /* scale low_slice according to IO priority
575 * and sync vs async */
576 unsigned low_slice =
577 min(slice, base_low_slice * slice / sync_slice);
578 /* the adapted slice value is scaled to fit all iqs
579 * into the target latency */
Vivek Goyal58ff82f2009-12-03 12:59:44 -0500580 slice = max(slice * group_slice / expect_latency,
Corrado Zoccolo5db5d642009-10-26 22:44:04 +0100581 low_slice);
582 }
583 }
Vivek Goyaldae739e2009-12-03 12:59:45 -0500584 cfqq->slice_start = jiffies;
Corrado Zoccolo5db5d642009-10-26 22:44:04 +0100585 cfqq->slice_end = jiffies + slice;
Vivek Goyalf75edf22009-12-03 12:59:53 -0500586 cfqq->allocated_slice = slice;
Jens Axboe7b679132008-05-30 12:23:07 +0200587 cfq_log_cfqq(cfqd, cfqq, "set_slice=%lu", cfqq->slice_end - jiffies);
Jens Axboe44f7c162007-01-19 11:51:58 +1100588}
589
590/*
591 * We need to wrap this check in cfq_cfqq_slice_new(), since ->slice_end
592 * isn't valid until the first request from the dispatch is activated
593 * and the slice time set.
594 */
Jens Axboea6151c32009-10-07 20:02:57 +0200595static inline bool cfq_slice_used(struct cfq_queue *cfqq)
Jens Axboe44f7c162007-01-19 11:51:58 +1100596{
597 if (cfq_cfqq_slice_new(cfqq))
598 return 0;
599 if (time_before(jiffies, cfqq->slice_end))
600 return 0;
601
602 return 1;
603}
604
605/*
Jens Axboe5e705372006-07-13 12:39:25 +0200606 * Lifted from AS - choose which of rq1 and rq2 that is best served now.
Linus Torvalds1da177e2005-04-16 15:20:36 -0700607 * We choose the request that is closest to the head right now. Distance
Andreas Mohre8a99052006-03-28 08:59:49 +0200608 * behind the head is penalized and only allowed to a certain extent.
Linus Torvalds1da177e2005-04-16 15:20:36 -0700609 */
Jens Axboe5e705372006-07-13 12:39:25 +0200610static struct request *
Corrado Zoccolocf7c25c2009-11-08 17:16:46 +0100611cfq_choose_req(struct cfq_data *cfqd, struct request *rq1, struct request *rq2, sector_t last)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700612{
Corrado Zoccolocf7c25c2009-11-08 17:16:46 +0100613 sector_t s1, s2, d1 = 0, d2 = 0;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700614 unsigned long back_max;
Andreas Mohre8a99052006-03-28 08:59:49 +0200615#define CFQ_RQ1_WRAP 0x01 /* request 1 wraps */
616#define CFQ_RQ2_WRAP 0x02 /* request 2 wraps */
617 unsigned wrap = 0; /* bit mask: requests behind the disk head? */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700618
Jens Axboe5e705372006-07-13 12:39:25 +0200619 if (rq1 == NULL || rq1 == rq2)
620 return rq2;
621 if (rq2 == NULL)
622 return rq1;
Jens Axboe9c2c38a2005-08-24 14:57:54 +0200623
Jens Axboe5e705372006-07-13 12:39:25 +0200624 if (rq_is_sync(rq1) && !rq_is_sync(rq2))
625 return rq1;
626 else if (rq_is_sync(rq2) && !rq_is_sync(rq1))
627 return rq2;
Jens Axboe374f84a2006-07-23 01:42:19 +0200628 if (rq_is_meta(rq1) && !rq_is_meta(rq2))
629 return rq1;
630 else if (rq_is_meta(rq2) && !rq_is_meta(rq1))
631 return rq2;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700632
Tejun Heo83096eb2009-05-07 22:24:39 +0900633 s1 = blk_rq_pos(rq1);
634 s2 = blk_rq_pos(rq2);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700635
Linus Torvalds1da177e2005-04-16 15:20:36 -0700636 /*
637 * by definition, 1KiB is 2 sectors
638 */
639 back_max = cfqd->cfq_back_max * 2;
640
641 /*
642 * Strict one way elevator _except_ in the case where we allow
643 * short backward seeks which are biased as twice the cost of a
644 * similar forward seek.
645 */
646 if (s1 >= last)
647 d1 = s1 - last;
648 else if (s1 + back_max >= last)
649 d1 = (last - s1) * cfqd->cfq_back_penalty;
650 else
Andreas Mohre8a99052006-03-28 08:59:49 +0200651 wrap |= CFQ_RQ1_WRAP;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700652
653 if (s2 >= last)
654 d2 = s2 - last;
655 else if (s2 + back_max >= last)
656 d2 = (last - s2) * cfqd->cfq_back_penalty;
657 else
Andreas Mohre8a99052006-03-28 08:59:49 +0200658 wrap |= CFQ_RQ2_WRAP;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700659
660 /* Found required data */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700661
Andreas Mohre8a99052006-03-28 08:59:49 +0200662 /*
663 * By doing switch() on the bit mask "wrap" we avoid having to
664 * check two variables for all permutations: --> faster!
665 */
666 switch (wrap) {
Jens Axboe5e705372006-07-13 12:39:25 +0200667 case 0: /* common case for CFQ: rq1 and rq2 not wrapped */
Andreas Mohre8a99052006-03-28 08:59:49 +0200668 if (d1 < d2)
Jens Axboe5e705372006-07-13 12:39:25 +0200669 return rq1;
Andreas Mohre8a99052006-03-28 08:59:49 +0200670 else if (d2 < d1)
Jens Axboe5e705372006-07-13 12:39:25 +0200671 return rq2;
Andreas Mohre8a99052006-03-28 08:59:49 +0200672 else {
673 if (s1 >= s2)
Jens Axboe5e705372006-07-13 12:39:25 +0200674 return rq1;
Andreas Mohre8a99052006-03-28 08:59:49 +0200675 else
Jens Axboe5e705372006-07-13 12:39:25 +0200676 return rq2;
Andreas Mohre8a99052006-03-28 08:59:49 +0200677 }
678
679 case CFQ_RQ2_WRAP:
Jens Axboe5e705372006-07-13 12:39:25 +0200680 return rq1;
Andreas Mohre8a99052006-03-28 08:59:49 +0200681 case CFQ_RQ1_WRAP:
Jens Axboe5e705372006-07-13 12:39:25 +0200682 return rq2;
683 case (CFQ_RQ1_WRAP|CFQ_RQ2_WRAP): /* both rqs wrapped */
Andreas Mohre8a99052006-03-28 08:59:49 +0200684 default:
685 /*
686 * Since both rqs are wrapped,
687 * start with the one that's further behind head
688 * (--> only *one* back seek required),
689 * since back seek takes more time than forward.
690 */
691 if (s1 <= s2)
Jens Axboe5e705372006-07-13 12:39:25 +0200692 return rq1;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700693 else
Jens Axboe5e705372006-07-13 12:39:25 +0200694 return rq2;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700695 }
696}
697
Jens Axboe498d3aa2007-04-26 12:54:48 +0200698/*
699 * The below is leftmost cache rbtree addon
700 */
Jens Axboe08717142008-01-28 11:38:15 +0100701static struct cfq_queue *cfq_rb_first(struct cfq_rb_root *root)
Jens Axboecc09e292007-04-26 12:53:50 +0200702{
Vivek Goyal615f0252009-12-03 12:59:39 -0500703 /* Service tree is empty */
704 if (!root->count)
705 return NULL;
706
Jens Axboecc09e292007-04-26 12:53:50 +0200707 if (!root->left)
708 root->left = rb_first(&root->rb);
709
Jens Axboe08717142008-01-28 11:38:15 +0100710 if (root->left)
711 return rb_entry(root->left, struct cfq_queue, rb_node);
712
713 return NULL;
Jens Axboecc09e292007-04-26 12:53:50 +0200714}
715
Vivek Goyal1fa8f6d2009-12-03 12:59:41 -0500716static struct cfq_group *cfq_rb_first_group(struct cfq_rb_root *root)
717{
718 if (!root->left)
719 root->left = rb_first(&root->rb);
720
721 if (root->left)
722 return rb_entry_cfqg(root->left);
723
724 return NULL;
725}
726
Jens Axboea36e71f2009-04-15 12:15:11 +0200727static void rb_erase_init(struct rb_node *n, struct rb_root *root)
728{
729 rb_erase(n, root);
730 RB_CLEAR_NODE(n);
731}
732
Jens Axboecc09e292007-04-26 12:53:50 +0200733static void cfq_rb_erase(struct rb_node *n, struct cfq_rb_root *root)
734{
735 if (root->left == n)
736 root->left = NULL;
Jens Axboea36e71f2009-04-15 12:15:11 +0200737 rb_erase_init(n, &root->rb);
Corrado Zoccoloaa6f6a32009-10-26 22:44:33 +0100738 --root->count;
Jens Axboecc09e292007-04-26 12:53:50 +0200739}
740
Linus Torvalds1da177e2005-04-16 15:20:36 -0700741/*
742 * would be nice to take fifo expire time into account as well
743 */
Jens Axboe5e705372006-07-13 12:39:25 +0200744static struct request *
745cfq_find_next_rq(struct cfq_data *cfqd, struct cfq_queue *cfqq,
746 struct request *last)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700747{
Jens Axboe21183b02006-07-13 12:33:14 +0200748 struct rb_node *rbnext = rb_next(&last->rb_node);
749 struct rb_node *rbprev = rb_prev(&last->rb_node);
Jens Axboe5e705372006-07-13 12:39:25 +0200750 struct request *next = NULL, *prev = NULL;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700751
Jens Axboe21183b02006-07-13 12:33:14 +0200752 BUG_ON(RB_EMPTY_NODE(&last->rb_node));
Linus Torvalds1da177e2005-04-16 15:20:36 -0700753
754 if (rbprev)
Jens Axboe5e705372006-07-13 12:39:25 +0200755 prev = rb_entry_rq(rbprev);
Jens Axboe21183b02006-07-13 12:33:14 +0200756
Linus Torvalds1da177e2005-04-16 15:20:36 -0700757 if (rbnext)
Jens Axboe5e705372006-07-13 12:39:25 +0200758 next = rb_entry_rq(rbnext);
Jens Axboe21183b02006-07-13 12:33:14 +0200759 else {
760 rbnext = rb_first(&cfqq->sort_list);
761 if (rbnext && rbnext != &last->rb_node)
Jens Axboe5e705372006-07-13 12:39:25 +0200762 next = rb_entry_rq(rbnext);
Jens Axboe21183b02006-07-13 12:33:14 +0200763 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700764
Corrado Zoccolocf7c25c2009-11-08 17:16:46 +0100765 return cfq_choose_req(cfqd, next, prev, blk_rq_pos(last));
Linus Torvalds1da177e2005-04-16 15:20:36 -0700766}
767
Jens Axboed9e76202007-04-20 14:27:50 +0200768static unsigned long cfq_slice_offset(struct cfq_data *cfqd,
769 struct cfq_queue *cfqq)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700770{
Jens Axboed9e76202007-04-20 14:27:50 +0200771 /*
772 * just an approximation, should be ok.
773 */
Vivek Goyalcdb16e82009-12-03 12:59:38 -0500774 return (cfqq->cfqg->nr_cfqq - 1) * (cfq_prio_slice(cfqd, 1, 0) -
Jens Axboe464191c2009-11-30 09:38:13 +0100775 cfq_prio_slice(cfqd, cfq_cfqq_sync(cfqq), cfqq->ioprio));
Jens Axboed9e76202007-04-20 14:27:50 +0200776}
Linus Torvalds1da177e2005-04-16 15:20:36 -0700777
Vivek Goyal1fa8f6d2009-12-03 12:59:41 -0500778static inline s64
779cfqg_key(struct cfq_rb_root *st, struct cfq_group *cfqg)
780{
781 return cfqg->vdisktime - st->min_vdisktime;
782}
783
784static void
785__cfq_group_service_tree_add(struct cfq_rb_root *st, struct cfq_group *cfqg)
786{
787 struct rb_node **node = &st->rb.rb_node;
788 struct rb_node *parent = NULL;
789 struct cfq_group *__cfqg;
790 s64 key = cfqg_key(st, cfqg);
791 int left = 1;
792
793 while (*node != NULL) {
794 parent = *node;
795 __cfqg = rb_entry_cfqg(parent);
796
797 if (key < cfqg_key(st, __cfqg))
798 node = &parent->rb_left;
799 else {
800 node = &parent->rb_right;
801 left = 0;
802 }
803 }
804
805 if (left)
806 st->left = &cfqg->rb_node;
807
808 rb_link_node(&cfqg->rb_node, parent, node);
809 rb_insert_color(&cfqg->rb_node, &st->rb);
810}
811
812static void
813cfq_group_service_tree_add(struct cfq_data *cfqd, struct cfq_group *cfqg)
814{
815 struct cfq_rb_root *st = &cfqd->grp_service_tree;
816 struct cfq_group *__cfqg;
817 struct rb_node *n;
818
819 cfqg->nr_cfqq++;
820 if (cfqg->on_st)
821 return;
822
823 /*
824 * Currently put the group at the end. Later implement something
825 * so that groups get lesser vtime based on their weights, so that
826 * if group does not loose all if it was not continously backlogged.
827 */
828 n = rb_last(&st->rb);
829 if (n) {
830 __cfqg = rb_entry_cfqg(n);
831 cfqg->vdisktime = __cfqg->vdisktime + CFQ_IDLE_DELAY;
832 } else
833 cfqg->vdisktime = st->min_vdisktime;
834
835 __cfq_group_service_tree_add(st, cfqg);
836 cfqg->on_st = true;
Vivek Goyal58ff82f2009-12-03 12:59:44 -0500837 st->total_weight += cfqg->weight;
Vivek Goyal1fa8f6d2009-12-03 12:59:41 -0500838}
839
840static void
841cfq_group_service_tree_del(struct cfq_data *cfqd, struct cfq_group *cfqg)
842{
843 struct cfq_rb_root *st = &cfqd->grp_service_tree;
844
Vivek Goyal25bc6b02009-12-03 12:59:43 -0500845 if (st->active == &cfqg->rb_node)
846 st->active = NULL;
847
Vivek Goyal1fa8f6d2009-12-03 12:59:41 -0500848 BUG_ON(cfqg->nr_cfqq < 1);
849 cfqg->nr_cfqq--;
Vivek Goyal25bc6b02009-12-03 12:59:43 -0500850
Vivek Goyal1fa8f6d2009-12-03 12:59:41 -0500851 /* If there are other cfq queues under this group, don't delete it */
852 if (cfqg->nr_cfqq)
853 return;
854
Vivek Goyal2868ef72009-12-03 12:59:48 -0500855 cfq_log_cfqg(cfqd, cfqg, "del_from_rr group");
Vivek Goyal1fa8f6d2009-12-03 12:59:41 -0500856 cfqg->on_st = false;
Vivek Goyal58ff82f2009-12-03 12:59:44 -0500857 st->total_weight -= cfqg->weight;
Vivek Goyal1fa8f6d2009-12-03 12:59:41 -0500858 if (!RB_EMPTY_NODE(&cfqg->rb_node))
859 cfq_rb_erase(&cfqg->rb_node, st);
Vivek Goyaldae739e2009-12-03 12:59:45 -0500860 cfqg->saved_workload_slice = 0;
Vivek Goyal22084192009-12-03 12:59:49 -0500861 blkiocg_update_blkio_group_dequeue_stats(&cfqg->blkg, 1);
Vivek Goyaldae739e2009-12-03 12:59:45 -0500862}
863
864static inline unsigned int cfq_cfqq_slice_usage(struct cfq_queue *cfqq)
865{
Vivek Goyalf75edf22009-12-03 12:59:53 -0500866 unsigned int slice_used;
Vivek Goyaldae739e2009-12-03 12:59:45 -0500867
868 /*
869 * Queue got expired before even a single request completed or
870 * got expired immediately after first request completion.
871 */
872 if (!cfqq->slice_start || cfqq->slice_start == jiffies) {
873 /*
874 * Also charge the seek time incurred to the group, otherwise
875 * if there are mutiple queues in the group, each can dispatch
876 * a single request on seeky media and cause lots of seek time
877 * and group will never know it.
878 */
879 slice_used = max_t(unsigned, (jiffies - cfqq->dispatch_start),
880 1);
881 } else {
882 slice_used = jiffies - cfqq->slice_start;
Vivek Goyalf75edf22009-12-03 12:59:53 -0500883 if (slice_used > cfqq->allocated_slice)
884 slice_used = cfqq->allocated_slice;
Vivek Goyaldae739e2009-12-03 12:59:45 -0500885 }
886
Vivek Goyal22084192009-12-03 12:59:49 -0500887 cfq_log_cfqq(cfqq->cfqd, cfqq, "sl_used=%u sect=%lu", slice_used,
888 cfqq->nr_sectors);
Vivek Goyaldae739e2009-12-03 12:59:45 -0500889 return slice_used;
890}
891
892static void cfq_group_served(struct cfq_data *cfqd, struct cfq_group *cfqg,
893 struct cfq_queue *cfqq)
894{
895 struct cfq_rb_root *st = &cfqd->grp_service_tree;
Vivek Goyalf26bd1f2009-12-03 12:59:54 -0500896 unsigned int used_sl, charge_sl;
897 int nr_sync = cfqg->nr_cfqq - cfqg_busy_async_queues(cfqd, cfqg)
898 - cfqg->service_tree_idle.count;
Vivek Goyaldae739e2009-12-03 12:59:45 -0500899
Vivek Goyalf26bd1f2009-12-03 12:59:54 -0500900 BUG_ON(nr_sync < 0);
901 used_sl = charge_sl = cfq_cfqq_slice_usage(cfqq);
902
903 if (!cfq_cfqq_sync(cfqq) && !nr_sync)
904 charge_sl = cfqq->allocated_slice;
Vivek Goyaldae739e2009-12-03 12:59:45 -0500905
906 /* Can't update vdisktime while group is on service tree */
907 cfq_rb_erase(&cfqg->rb_node, st);
Vivek Goyalf26bd1f2009-12-03 12:59:54 -0500908 cfqg->vdisktime += cfq_scale_slice(charge_sl, cfqg);
Vivek Goyaldae739e2009-12-03 12:59:45 -0500909 __cfq_group_service_tree_add(st, cfqg);
910
911 /* This group is being expired. Save the context */
912 if (time_after(cfqd->workload_expires, jiffies)) {
913 cfqg->saved_workload_slice = cfqd->workload_expires
914 - jiffies;
915 cfqg->saved_workload = cfqd->serving_type;
916 cfqg->saved_serving_prio = cfqd->serving_prio;
917 } else
918 cfqg->saved_workload_slice = 0;
Vivek Goyal2868ef72009-12-03 12:59:48 -0500919
920 cfq_log_cfqg(cfqd, cfqg, "served: vt=%llu min_vt=%llu", cfqg->vdisktime,
921 st->min_vdisktime);
Vivek Goyal22084192009-12-03 12:59:49 -0500922 blkiocg_update_blkio_group_stats(&cfqg->blkg, used_sl,
923 cfqq->nr_sectors);
Vivek Goyal1fa8f6d2009-12-03 12:59:41 -0500924}
925
Vivek Goyal25fb5162009-12-03 12:59:46 -0500926#ifdef CONFIG_CFQ_GROUP_IOSCHED
927static inline struct cfq_group *cfqg_of_blkg(struct blkio_group *blkg)
928{
929 if (blkg)
930 return container_of(blkg, struct cfq_group, blkg);
931 return NULL;
932}
933
Vivek Goyalf8d461d2009-12-03 12:59:52 -0500934void
935cfq_update_blkio_group_weight(struct blkio_group *blkg, unsigned int weight)
936{
937 cfqg_of_blkg(blkg)->weight = weight;
938}
939
Vivek Goyal25fb5162009-12-03 12:59:46 -0500940static struct cfq_group *
941cfq_find_alloc_cfqg(struct cfq_data *cfqd, struct cgroup *cgroup, int create)
942{
943 struct blkio_cgroup *blkcg = cgroup_to_blkio_cgroup(cgroup);
944 struct cfq_group *cfqg = NULL;
945 void *key = cfqd;
946 int i, j;
947 struct cfq_rb_root *st;
Vivek Goyal22084192009-12-03 12:59:49 -0500948 struct backing_dev_info *bdi = &cfqd->queue->backing_dev_info;
949 unsigned int major, minor;
Vivek Goyal25fb5162009-12-03 12:59:46 -0500950
Vivek Goyal25fb5162009-12-03 12:59:46 -0500951 cfqg = cfqg_of_blkg(blkiocg_lookup_group(blkcg, key));
Ricky Beniteza74b2ad2010-04-05 18:22:17 +0200952 if (cfqg && !cfqg->blkg.dev && bdi->dev && dev_name(bdi->dev)) {
953 sscanf(dev_name(bdi->dev), "%u:%u", &major, &minor);
954 cfqg->blkg.dev = MKDEV(major, minor);
955 goto done;
956 }
Vivek Goyal25fb5162009-12-03 12:59:46 -0500957 if (cfqg || !create)
958 goto done;
959
960 cfqg = kzalloc_node(sizeof(*cfqg), GFP_ATOMIC, cfqd->queue->node);
961 if (!cfqg)
962 goto done;
963
964 cfqg->weight = blkcg->weight;
965 for_each_cfqg_st(cfqg, i, j, st)
966 *st = CFQ_RB_ROOT;
967 RB_CLEAR_NODE(&cfqg->rb_node);
968
Vivek Goyalb1c35762009-12-03 12:59:47 -0500969 /*
970 * Take the initial reference that will be released on destroy
971 * This can be thought of a joint reference by cgroup and
972 * elevator which will be dropped by either elevator exit
973 * or cgroup deletion path depending on who is exiting first.
974 */
975 atomic_set(&cfqg->ref, 1);
976
Vivek Goyal25fb5162009-12-03 12:59:46 -0500977 /* Add group onto cgroup list */
Vivek Goyal22084192009-12-03 12:59:49 -0500978 sscanf(dev_name(bdi->dev), "%u:%u", &major, &minor);
979 blkiocg_add_blkio_group(blkcg, &cfqg->blkg, (void *)cfqd,
980 MKDEV(major, minor));
Vivek Goyal25fb5162009-12-03 12:59:46 -0500981
982 /* Add group on cfqd list */
983 hlist_add_head(&cfqg->cfqd_node, &cfqd->cfqg_list);
984
985done:
Vivek Goyal25fb5162009-12-03 12:59:46 -0500986 return cfqg;
987}
988
989/*
990 * Search for the cfq group current task belongs to. If create = 1, then also
991 * create the cfq group if it does not exist. request_queue lock must be held.
992 */
993static struct cfq_group *cfq_get_cfqg(struct cfq_data *cfqd, int create)
994{
995 struct cgroup *cgroup;
996 struct cfq_group *cfqg = NULL;
997
998 rcu_read_lock();
999 cgroup = task_cgroup(current, blkio_subsys_id);
1000 cfqg = cfq_find_alloc_cfqg(cfqd, cgroup, create);
1001 if (!cfqg && create)
1002 cfqg = &cfqd->root_group;
1003 rcu_read_unlock();
1004 return cfqg;
1005}
1006
1007static void cfq_link_cfqq_cfqg(struct cfq_queue *cfqq, struct cfq_group *cfqg)
1008{
1009 /* Currently, all async queues are mapped to root group */
1010 if (!cfq_cfqq_sync(cfqq))
1011 cfqg = &cfqq->cfqd->root_group;
1012
1013 cfqq->cfqg = cfqg;
Vivek Goyalb1c35762009-12-03 12:59:47 -05001014 /* cfqq reference on cfqg */
1015 atomic_inc(&cfqq->cfqg->ref);
Vivek Goyal25fb5162009-12-03 12:59:46 -05001016}
Vivek Goyalb1c35762009-12-03 12:59:47 -05001017
1018static void cfq_put_cfqg(struct cfq_group *cfqg)
1019{
1020 struct cfq_rb_root *st;
1021 int i, j;
1022
1023 BUG_ON(atomic_read(&cfqg->ref) <= 0);
1024 if (!atomic_dec_and_test(&cfqg->ref))
1025 return;
1026 for_each_cfqg_st(cfqg, i, j, st)
1027 BUG_ON(!RB_EMPTY_ROOT(&st->rb) || st->active != NULL);
1028 kfree(cfqg);
1029}
1030
1031static void cfq_destroy_cfqg(struct cfq_data *cfqd, struct cfq_group *cfqg)
1032{
1033 /* Something wrong if we are trying to remove same group twice */
1034 BUG_ON(hlist_unhashed(&cfqg->cfqd_node));
1035
1036 hlist_del_init(&cfqg->cfqd_node);
1037
1038 /*
1039 * Put the reference taken at the time of creation so that when all
1040 * queues are gone, group can be destroyed.
1041 */
1042 cfq_put_cfqg(cfqg);
1043}
1044
1045static void cfq_release_cfq_groups(struct cfq_data *cfqd)
1046{
1047 struct hlist_node *pos, *n;
1048 struct cfq_group *cfqg;
1049
1050 hlist_for_each_entry_safe(cfqg, pos, n, &cfqd->cfqg_list, cfqd_node) {
1051 /*
1052 * If cgroup removal path got to blk_group first and removed
1053 * it from cgroup list, then it will take care of destroying
1054 * cfqg also.
1055 */
1056 if (!blkiocg_del_blkio_group(&cfqg->blkg))
1057 cfq_destroy_cfqg(cfqd, cfqg);
1058 }
1059}
1060
1061/*
1062 * Blk cgroup controller notification saying that blkio_group object is being
1063 * delinked as associated cgroup object is going away. That also means that
1064 * no new IO will come in this group. So get rid of this group as soon as
1065 * any pending IO in the group is finished.
1066 *
1067 * This function is called under rcu_read_lock(). key is the rcu protected
1068 * pointer. That means "key" is a valid cfq_data pointer as long as we are rcu
1069 * read lock.
1070 *
1071 * "key" was fetched from blkio_group under blkio_cgroup->lock. That means
1072 * it should not be NULL as even if elevator was exiting, cgroup deltion
1073 * path got to it first.
1074 */
1075void cfq_unlink_blkio_group(void *key, struct blkio_group *blkg)
1076{
1077 unsigned long flags;
1078 struct cfq_data *cfqd = key;
1079
1080 spin_lock_irqsave(cfqd->queue->queue_lock, flags);
1081 cfq_destroy_cfqg(cfqd, cfqg_of_blkg(blkg));
1082 spin_unlock_irqrestore(cfqd->queue->queue_lock, flags);
1083}
1084
Vivek Goyal25fb5162009-12-03 12:59:46 -05001085#else /* GROUP_IOSCHED */
1086static struct cfq_group *cfq_get_cfqg(struct cfq_data *cfqd, int create)
1087{
1088 return &cfqd->root_group;
1089}
1090static inline void
1091cfq_link_cfqq_cfqg(struct cfq_queue *cfqq, struct cfq_group *cfqg) {
1092 cfqq->cfqg = cfqg;
1093}
1094
Vivek Goyalb1c35762009-12-03 12:59:47 -05001095static void cfq_release_cfq_groups(struct cfq_data *cfqd) {}
1096static inline void cfq_put_cfqg(struct cfq_group *cfqg) {}
1097
Vivek Goyal25fb5162009-12-03 12:59:46 -05001098#endif /* GROUP_IOSCHED */
1099
Jens Axboe498d3aa2007-04-26 12:54:48 +02001100/*
Corrado Zoccoloc0324a02009-10-27 19:16:03 +01001101 * The cfqd->service_trees holds all pending cfq_queue's that have
Jens Axboe498d3aa2007-04-26 12:54:48 +02001102 * requests waiting to be processed. It is sorted in the order that
1103 * we will service the queues.
1104 */
Jens Axboea36e71f2009-04-15 12:15:11 +02001105static void cfq_service_tree_add(struct cfq_data *cfqd, struct cfq_queue *cfqq,
Jens Axboea6151c32009-10-07 20:02:57 +02001106 bool add_front)
Jens Axboed9e76202007-04-20 14:27:50 +02001107{
Jens Axboe08717142008-01-28 11:38:15 +01001108 struct rb_node **p, *parent;
1109 struct cfq_queue *__cfqq;
Jens Axboed9e76202007-04-20 14:27:50 +02001110 unsigned long rb_key;
Corrado Zoccoloc0324a02009-10-27 19:16:03 +01001111 struct cfq_rb_root *service_tree;
Jens Axboe498d3aa2007-04-26 12:54:48 +02001112 int left;
Vivek Goyaldae739e2009-12-03 12:59:45 -05001113 int new_cfqq = 1;
Vivek Goyalae30c282009-12-03 12:59:55 -05001114 int group_changed = 0;
1115
1116#ifdef CONFIG_CFQ_GROUP_IOSCHED
1117 if (!cfqd->cfq_group_isolation
1118 && cfqq_type(cfqq) == SYNC_NOIDLE_WORKLOAD
1119 && cfqq->cfqg && cfqq->cfqg != &cfqd->root_group) {
1120 /* Move this cfq to root group */
1121 cfq_log_cfqq(cfqd, cfqq, "moving to root group");
1122 if (!RB_EMPTY_NODE(&cfqq->rb_node))
1123 cfq_group_service_tree_del(cfqd, cfqq->cfqg);
1124 cfqq->orig_cfqg = cfqq->cfqg;
1125 cfqq->cfqg = &cfqd->root_group;
1126 atomic_inc(&cfqd->root_group.ref);
1127 group_changed = 1;
1128 } else if (!cfqd->cfq_group_isolation
1129 && cfqq_type(cfqq) == SYNC_WORKLOAD && cfqq->orig_cfqg) {
1130 /* cfqq is sequential now needs to go to its original group */
1131 BUG_ON(cfqq->cfqg != &cfqd->root_group);
1132 if (!RB_EMPTY_NODE(&cfqq->rb_node))
1133 cfq_group_service_tree_del(cfqd, cfqq->cfqg);
1134 cfq_put_cfqg(cfqq->cfqg);
1135 cfqq->cfqg = cfqq->orig_cfqg;
1136 cfqq->orig_cfqg = NULL;
1137 group_changed = 1;
1138 cfq_log_cfqq(cfqd, cfqq, "moved to origin group");
1139 }
1140#endif
Jens Axboed9e76202007-04-20 14:27:50 +02001141
Vivek Goyalcdb16e82009-12-03 12:59:38 -05001142 service_tree = service_tree_for(cfqq->cfqg, cfqq_prio(cfqq),
Vivek Goyal65b32a52009-12-16 17:52:59 -05001143 cfqq_type(cfqq));
Jens Axboe08717142008-01-28 11:38:15 +01001144 if (cfq_class_idle(cfqq)) {
1145 rb_key = CFQ_IDLE_DELAY;
Corrado Zoccoloaa6f6a32009-10-26 22:44:33 +01001146 parent = rb_last(&service_tree->rb);
Jens Axboe08717142008-01-28 11:38:15 +01001147 if (parent && parent != &cfqq->rb_node) {
1148 __cfqq = rb_entry(parent, struct cfq_queue, rb_node);
1149 rb_key += __cfqq->rb_key;
1150 } else
1151 rb_key += jiffies;
1152 } else if (!add_front) {
Jens Axboeb9c89462009-10-06 20:53:44 +02001153 /*
1154 * Get our rb key offset. Subtract any residual slice
1155 * value carried from last service. A negative resid
1156 * count indicates slice overrun, and this should position
1157 * the next service time further away in the tree.
1158 */
Jens Axboeedd75ff2007-04-19 12:03:34 +02001159 rb_key = cfq_slice_offset(cfqd, cfqq) + jiffies;
Jens Axboeb9c89462009-10-06 20:53:44 +02001160 rb_key -= cfqq->slice_resid;
Jens Axboeedd75ff2007-04-19 12:03:34 +02001161 cfqq->slice_resid = 0;
Corrado Zoccolo48e025e2009-10-05 08:49:23 +02001162 } else {
1163 rb_key = -HZ;
Corrado Zoccoloaa6f6a32009-10-26 22:44:33 +01001164 __cfqq = cfq_rb_first(service_tree);
Corrado Zoccolo48e025e2009-10-05 08:49:23 +02001165 rb_key += __cfqq ? __cfqq->rb_key : jiffies;
1166 }
Jens Axboed9e76202007-04-20 14:27:50 +02001167
1168 if (!RB_EMPTY_NODE(&cfqq->rb_node)) {
Vivek Goyaldae739e2009-12-03 12:59:45 -05001169 new_cfqq = 0;
Jens Axboe99f96282007-02-05 11:56:25 +01001170 /*
Jens Axboed9e76202007-04-20 14:27:50 +02001171 * same position, nothing more to do
Jens Axboe99f96282007-02-05 11:56:25 +01001172 */
Corrado Zoccoloc0324a02009-10-27 19:16:03 +01001173 if (rb_key == cfqq->rb_key &&
1174 cfqq->service_tree == service_tree)
Jens Axboed9e76202007-04-20 14:27:50 +02001175 return;
Jens Axboe53b03742006-07-28 09:48:51 +02001176
Corrado Zoccoloaa6f6a32009-10-26 22:44:33 +01001177 cfq_rb_erase(&cfqq->rb_node, cfqq->service_tree);
1178 cfqq->service_tree = NULL;
Jens Axboe22e2c502005-06-27 10:55:12 +02001179 }
Jens Axboed9e76202007-04-20 14:27:50 +02001180
Jens Axboe498d3aa2007-04-26 12:54:48 +02001181 left = 1;
Jens Axboe08717142008-01-28 11:38:15 +01001182 parent = NULL;
Corrado Zoccoloaa6f6a32009-10-26 22:44:33 +01001183 cfqq->service_tree = service_tree;
1184 p = &service_tree->rb.rb_node;
Jens Axboed9e76202007-04-20 14:27:50 +02001185 while (*p) {
Jens Axboe67060e32007-04-18 20:13:32 +02001186 struct rb_node **n;
Jens Axboecc09e292007-04-26 12:53:50 +02001187
Jens Axboed9e76202007-04-20 14:27:50 +02001188 parent = *p;
1189 __cfqq = rb_entry(parent, struct cfq_queue, rb_node);
1190
Jens Axboe0c534e02007-04-18 20:01:57 +02001191 /*
Corrado Zoccoloc0324a02009-10-27 19:16:03 +01001192 * sort by key, that represents service time.
Jens Axboe0c534e02007-04-18 20:01:57 +02001193 */
Corrado Zoccoloc0324a02009-10-27 19:16:03 +01001194 if (time_before(rb_key, __cfqq->rb_key))
Jens Axboe67060e32007-04-18 20:13:32 +02001195 n = &(*p)->rb_left;
Corrado Zoccoloc0324a02009-10-27 19:16:03 +01001196 else {
Jens Axboe67060e32007-04-18 20:13:32 +02001197 n = &(*p)->rb_right;
Jens Axboecc09e292007-04-26 12:53:50 +02001198 left = 0;
Corrado Zoccoloc0324a02009-10-27 19:16:03 +01001199 }
Jens Axboe67060e32007-04-18 20:13:32 +02001200
1201 p = n;
Jens Axboed9e76202007-04-20 14:27:50 +02001202 }
1203
Jens Axboecc09e292007-04-26 12:53:50 +02001204 if (left)
Corrado Zoccoloaa6f6a32009-10-26 22:44:33 +01001205 service_tree->left = &cfqq->rb_node;
Jens Axboecc09e292007-04-26 12:53:50 +02001206
Jens Axboed9e76202007-04-20 14:27:50 +02001207 cfqq->rb_key = rb_key;
1208 rb_link_node(&cfqq->rb_node, parent, p);
Corrado Zoccoloaa6f6a32009-10-26 22:44:33 +01001209 rb_insert_color(&cfqq->rb_node, &service_tree->rb);
1210 service_tree->count++;
Vivek Goyalae30c282009-12-03 12:59:55 -05001211 if ((add_front || !new_cfqq) && !group_changed)
Vivek Goyaldae739e2009-12-03 12:59:45 -05001212 return;
Vivek Goyal1fa8f6d2009-12-03 12:59:41 -05001213 cfq_group_service_tree_add(cfqd, cfqq->cfqg);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001214}
1215
Jens Axboea36e71f2009-04-15 12:15:11 +02001216static struct cfq_queue *
Jens Axboef2d1f0a2009-04-23 12:19:38 +02001217cfq_prio_tree_lookup(struct cfq_data *cfqd, struct rb_root *root,
1218 sector_t sector, struct rb_node **ret_parent,
1219 struct rb_node ***rb_link)
Jens Axboea36e71f2009-04-15 12:15:11 +02001220{
Jens Axboea36e71f2009-04-15 12:15:11 +02001221 struct rb_node **p, *parent;
1222 struct cfq_queue *cfqq = NULL;
1223
1224 parent = NULL;
1225 p = &root->rb_node;
1226 while (*p) {
1227 struct rb_node **n;
1228
1229 parent = *p;
1230 cfqq = rb_entry(parent, struct cfq_queue, p_node);
1231
1232 /*
1233 * Sort strictly based on sector. Smallest to the left,
1234 * largest to the right.
1235 */
Tejun Heo2e46e8b2009-05-07 22:24:41 +09001236 if (sector > blk_rq_pos(cfqq->next_rq))
Jens Axboea36e71f2009-04-15 12:15:11 +02001237 n = &(*p)->rb_right;
Tejun Heo2e46e8b2009-05-07 22:24:41 +09001238 else if (sector < blk_rq_pos(cfqq->next_rq))
Jens Axboea36e71f2009-04-15 12:15:11 +02001239 n = &(*p)->rb_left;
1240 else
1241 break;
1242 p = n;
Jens Axboe3ac6c9f2009-04-23 12:14:56 +02001243 cfqq = NULL;
Jens Axboea36e71f2009-04-15 12:15:11 +02001244 }
1245
1246 *ret_parent = parent;
1247 if (rb_link)
1248 *rb_link = p;
Jens Axboe3ac6c9f2009-04-23 12:14:56 +02001249 return cfqq;
Jens Axboea36e71f2009-04-15 12:15:11 +02001250}
1251
1252static void cfq_prio_tree_add(struct cfq_data *cfqd, struct cfq_queue *cfqq)
1253{
Jens Axboea36e71f2009-04-15 12:15:11 +02001254 struct rb_node **p, *parent;
1255 struct cfq_queue *__cfqq;
1256
Jens Axboef2d1f0a2009-04-23 12:19:38 +02001257 if (cfqq->p_root) {
1258 rb_erase(&cfqq->p_node, cfqq->p_root);
1259 cfqq->p_root = NULL;
1260 }
Jens Axboea36e71f2009-04-15 12:15:11 +02001261
1262 if (cfq_class_idle(cfqq))
1263 return;
1264 if (!cfqq->next_rq)
1265 return;
1266
Jens Axboef2d1f0a2009-04-23 12:19:38 +02001267 cfqq->p_root = &cfqd->prio_trees[cfqq->org_ioprio];
Tejun Heo2e46e8b2009-05-07 22:24:41 +09001268 __cfqq = cfq_prio_tree_lookup(cfqd, cfqq->p_root,
1269 blk_rq_pos(cfqq->next_rq), &parent, &p);
Jens Axboe3ac6c9f2009-04-23 12:14:56 +02001270 if (!__cfqq) {
1271 rb_link_node(&cfqq->p_node, parent, p);
Jens Axboef2d1f0a2009-04-23 12:19:38 +02001272 rb_insert_color(&cfqq->p_node, cfqq->p_root);
1273 } else
1274 cfqq->p_root = NULL;
Jens Axboea36e71f2009-04-15 12:15:11 +02001275}
1276
Jens Axboe498d3aa2007-04-26 12:54:48 +02001277/*
1278 * Update cfqq's position in the service tree.
1279 */
Jens Axboeedd75ff2007-04-19 12:03:34 +02001280static void cfq_resort_rr_list(struct cfq_data *cfqd, struct cfq_queue *cfqq)
Jens Axboe6d048f52007-04-25 12:44:27 +02001281{
Jens Axboe6d048f52007-04-25 12:44:27 +02001282 /*
1283 * Resorting requires the cfqq to be on the RR list already.
1284 */
Jens Axboea36e71f2009-04-15 12:15:11 +02001285 if (cfq_cfqq_on_rr(cfqq)) {
Jens Axboeedd75ff2007-04-19 12:03:34 +02001286 cfq_service_tree_add(cfqd, cfqq, 0);
Jens Axboea36e71f2009-04-15 12:15:11 +02001287 cfq_prio_tree_add(cfqd, cfqq);
1288 }
Jens Axboe6d048f52007-04-25 12:44:27 +02001289}
1290
Linus Torvalds1da177e2005-04-16 15:20:36 -07001291/*
1292 * add to busy list of queues for service, trying to be fair in ordering
Jens Axboe22e2c502005-06-27 10:55:12 +02001293 * the pending list according to last request service
Linus Torvalds1da177e2005-04-16 15:20:36 -07001294 */
Jens Axboefebffd62008-01-28 13:19:43 +01001295static void cfq_add_cfqq_rr(struct cfq_data *cfqd, struct cfq_queue *cfqq)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001296{
Jens Axboe7b679132008-05-30 12:23:07 +02001297 cfq_log_cfqq(cfqd, cfqq, "add_to_rr");
Jens Axboe3b181522005-06-27 10:56:24 +02001298 BUG_ON(cfq_cfqq_on_rr(cfqq));
1299 cfq_mark_cfqq_on_rr(cfqq);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001300 cfqd->busy_queues++;
1301
Jens Axboeedd75ff2007-04-19 12:03:34 +02001302 cfq_resort_rr_list(cfqd, cfqq);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001303}
1304
Jens Axboe498d3aa2007-04-26 12:54:48 +02001305/*
1306 * Called when the cfqq no longer has requests pending, remove it from
1307 * the service tree.
1308 */
Jens Axboefebffd62008-01-28 13:19:43 +01001309static void cfq_del_cfqq_rr(struct cfq_data *cfqd, struct cfq_queue *cfqq)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001310{
Jens Axboe7b679132008-05-30 12:23:07 +02001311 cfq_log_cfqq(cfqd, cfqq, "del_from_rr");
Jens Axboe3b181522005-06-27 10:56:24 +02001312 BUG_ON(!cfq_cfqq_on_rr(cfqq));
1313 cfq_clear_cfqq_on_rr(cfqq);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001314
Corrado Zoccoloaa6f6a32009-10-26 22:44:33 +01001315 if (!RB_EMPTY_NODE(&cfqq->rb_node)) {
1316 cfq_rb_erase(&cfqq->rb_node, cfqq->service_tree);
1317 cfqq->service_tree = NULL;
1318 }
Jens Axboef2d1f0a2009-04-23 12:19:38 +02001319 if (cfqq->p_root) {
1320 rb_erase(&cfqq->p_node, cfqq->p_root);
1321 cfqq->p_root = NULL;
1322 }
Jens Axboed9e76202007-04-20 14:27:50 +02001323
Vivek Goyal1fa8f6d2009-12-03 12:59:41 -05001324 cfq_group_service_tree_del(cfqd, cfqq->cfqg);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001325 BUG_ON(!cfqd->busy_queues);
1326 cfqd->busy_queues--;
1327}
1328
1329/*
1330 * rb tree support functions
1331 */
Jens Axboefebffd62008-01-28 13:19:43 +01001332static void cfq_del_rq_rb(struct request *rq)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001333{
Jens Axboe5e705372006-07-13 12:39:25 +02001334 struct cfq_queue *cfqq = RQ_CFQQ(rq);
Jens Axboe5e705372006-07-13 12:39:25 +02001335 const int sync = rq_is_sync(rq);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001336
Jens Axboeb4878f22005-10-20 16:42:29 +02001337 BUG_ON(!cfqq->queued[sync]);
1338 cfqq->queued[sync]--;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001339
Jens Axboe5e705372006-07-13 12:39:25 +02001340 elv_rb_del(&cfqq->sort_list, rq);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001341
Vivek Goyalf04a6422009-12-03 12:59:40 -05001342 if (cfq_cfqq_on_rr(cfqq) && RB_EMPTY_ROOT(&cfqq->sort_list)) {
1343 /*
1344 * Queue will be deleted from service tree when we actually
1345 * expire it later. Right now just remove it from prio tree
1346 * as it is empty.
1347 */
1348 if (cfqq->p_root) {
1349 rb_erase(&cfqq->p_node, cfqq->p_root);
1350 cfqq->p_root = NULL;
1351 }
1352 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07001353}
1354
Jens Axboe5e705372006-07-13 12:39:25 +02001355static void cfq_add_rq_rb(struct request *rq)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001356{
Jens Axboe5e705372006-07-13 12:39:25 +02001357 struct cfq_queue *cfqq = RQ_CFQQ(rq);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001358 struct cfq_data *cfqd = cfqq->cfqd;
Jens Axboea36e71f2009-04-15 12:15:11 +02001359 struct request *__alias, *prev;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001360
Jens Axboe5380a102006-07-13 12:37:56 +02001361 cfqq->queued[rq_is_sync(rq)]++;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001362
1363 /*
1364 * looks a little odd, but the first insert might return an alias.
1365 * if that happens, put the alias on the dispatch list
1366 */
Jens Axboe21183b02006-07-13 12:33:14 +02001367 while ((__alias = elv_rb_add(&cfqq->sort_list, rq)) != NULL)
Jens Axboe5e705372006-07-13 12:39:25 +02001368 cfq_dispatch_insert(cfqd->queue, __alias);
Jens Axboe5fccbf62006-10-31 14:21:55 +01001369
1370 if (!cfq_cfqq_on_rr(cfqq))
1371 cfq_add_cfqq_rr(cfqd, cfqq);
Jens Axboe5044eed2007-04-25 11:53:48 +02001372
1373 /*
1374 * check if this request is a better next-serve candidate
1375 */
Jens Axboea36e71f2009-04-15 12:15:11 +02001376 prev = cfqq->next_rq;
Corrado Zoccolocf7c25c2009-11-08 17:16:46 +01001377 cfqq->next_rq = cfq_choose_req(cfqd, cfqq->next_rq, rq, cfqd->last_position);
Jens Axboea36e71f2009-04-15 12:15:11 +02001378
1379 /*
1380 * adjust priority tree position, if ->next_rq changes
1381 */
1382 if (prev != cfqq->next_rq)
1383 cfq_prio_tree_add(cfqd, cfqq);
1384
Jens Axboe5044eed2007-04-25 11:53:48 +02001385 BUG_ON(!cfqq->next_rq);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001386}
1387
Jens Axboefebffd62008-01-28 13:19:43 +01001388static void cfq_reposition_rq_rb(struct cfq_queue *cfqq, struct request *rq)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001389{
Jens Axboe5380a102006-07-13 12:37:56 +02001390 elv_rb_del(&cfqq->sort_list, rq);
1391 cfqq->queued[rq_is_sync(rq)]--;
Jens Axboe5e705372006-07-13 12:39:25 +02001392 cfq_add_rq_rb(rq);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001393}
1394
Jens Axboe206dc692006-03-28 13:03:44 +02001395static struct request *
1396cfq_find_rq_fmerge(struct cfq_data *cfqd, struct bio *bio)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001397{
Jens Axboe206dc692006-03-28 13:03:44 +02001398 struct task_struct *tsk = current;
Vasily Tarasov91fac312007-04-25 12:29:51 +02001399 struct cfq_io_context *cic;
Jens Axboe206dc692006-03-28 13:03:44 +02001400 struct cfq_queue *cfqq;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001401
Jens Axboe4ac845a2008-01-24 08:44:49 +01001402 cic = cfq_cic_lookup(cfqd, tsk->io_context);
Vasily Tarasov91fac312007-04-25 12:29:51 +02001403 if (!cic)
1404 return NULL;
1405
1406 cfqq = cic_to_cfqq(cic, cfq_bio_sync(bio));
Jens Axboe89850f72006-07-22 16:48:31 +02001407 if (cfqq) {
1408 sector_t sector = bio->bi_sector + bio_sectors(bio);
1409
Jens Axboe21183b02006-07-13 12:33:14 +02001410 return elv_rb_find(&cfqq->sort_list, sector);
Jens Axboe89850f72006-07-22 16:48:31 +02001411 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07001412
Linus Torvalds1da177e2005-04-16 15:20:36 -07001413 return NULL;
1414}
1415
Jens Axboe165125e2007-07-24 09:28:11 +02001416static void cfq_activate_request(struct request_queue *q, struct request *rq)
Jens Axboeb4878f22005-10-20 16:42:29 +02001417{
1418 struct cfq_data *cfqd = q->elevator->elevator_data;
1419
Corrado Zoccolo53c583d2010-02-28 19:45:05 +01001420 cfqd->rq_in_driver++;
Jens Axboe7b679132008-05-30 12:23:07 +02001421 cfq_log_cfqq(cfqd, RQ_CFQQ(rq), "activate rq, drv=%d",
Corrado Zoccolo53c583d2010-02-28 19:45:05 +01001422 cfqd->rq_in_driver);
Jens Axboe25776e32006-06-01 10:12:26 +02001423
Tejun Heo5b936292009-05-07 22:24:38 +09001424 cfqd->last_position = blk_rq_pos(rq) + blk_rq_sectors(rq);
Jens Axboeb4878f22005-10-20 16:42:29 +02001425}
1426
Jens Axboe165125e2007-07-24 09:28:11 +02001427static void cfq_deactivate_request(struct request_queue *q, struct request *rq)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001428{
Jens Axboe22e2c502005-06-27 10:55:12 +02001429 struct cfq_data *cfqd = q->elevator->elevator_data;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001430
Corrado Zoccolo53c583d2010-02-28 19:45:05 +01001431 WARN_ON(!cfqd->rq_in_driver);
1432 cfqd->rq_in_driver--;
Jens Axboe7b679132008-05-30 12:23:07 +02001433 cfq_log_cfqq(cfqd, RQ_CFQQ(rq), "deactivate rq, drv=%d",
Corrado Zoccolo53c583d2010-02-28 19:45:05 +01001434 cfqd->rq_in_driver);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001435}
1436
Jens Axboeb4878f22005-10-20 16:42:29 +02001437static void cfq_remove_request(struct request *rq)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001438{
Jens Axboe5e705372006-07-13 12:39:25 +02001439 struct cfq_queue *cfqq = RQ_CFQQ(rq);
Jens Axboe21183b02006-07-13 12:33:14 +02001440
Jens Axboe5e705372006-07-13 12:39:25 +02001441 if (cfqq->next_rq == rq)
1442 cfqq->next_rq = cfq_find_next_rq(cfqq->cfqd, cfqq, rq);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001443
Jens Axboeb4878f22005-10-20 16:42:29 +02001444 list_del_init(&rq->queuelist);
Jens Axboe5e705372006-07-13 12:39:25 +02001445 cfq_del_rq_rb(rq);
Jens Axboe374f84a2006-07-23 01:42:19 +02001446
Aaron Carroll45333d52008-08-26 15:52:36 +02001447 cfqq->cfqd->rq_queued--;
Jens Axboe374f84a2006-07-23 01:42:19 +02001448 if (rq_is_meta(rq)) {
1449 WARN_ON(!cfqq->meta_pending);
1450 cfqq->meta_pending--;
1451 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07001452}
1453
Jens Axboe165125e2007-07-24 09:28:11 +02001454static int cfq_merge(struct request_queue *q, struct request **req,
1455 struct bio *bio)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001456{
1457 struct cfq_data *cfqd = q->elevator->elevator_data;
1458 struct request *__rq;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001459
Jens Axboe206dc692006-03-28 13:03:44 +02001460 __rq = cfq_find_rq_fmerge(cfqd, bio);
Jens Axboe22e2c502005-06-27 10:55:12 +02001461 if (__rq && elv_rq_merge_ok(__rq, bio)) {
Jens Axboe98170642006-07-28 09:23:08 +02001462 *req = __rq;
1463 return ELEVATOR_FRONT_MERGE;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001464 }
1465
1466 return ELEVATOR_NO_MERGE;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001467}
1468
Jens Axboe165125e2007-07-24 09:28:11 +02001469static void cfq_merged_request(struct request_queue *q, struct request *req,
Jens Axboe21183b02006-07-13 12:33:14 +02001470 int type)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001471{
Jens Axboe21183b02006-07-13 12:33:14 +02001472 if (type == ELEVATOR_FRONT_MERGE) {
Jens Axboe5e705372006-07-13 12:39:25 +02001473 struct cfq_queue *cfqq = RQ_CFQQ(req);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001474
Jens Axboe5e705372006-07-13 12:39:25 +02001475 cfq_reposition_rq_rb(cfqq, req);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001476 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07001477}
1478
1479static void
Jens Axboe165125e2007-07-24 09:28:11 +02001480cfq_merged_requests(struct request_queue *q, struct request *rq,
Linus Torvalds1da177e2005-04-16 15:20:36 -07001481 struct request *next)
1482{
Corrado Zoccolocf7c25c2009-11-08 17:16:46 +01001483 struct cfq_queue *cfqq = RQ_CFQQ(rq);
Jens Axboe22e2c502005-06-27 10:55:12 +02001484 /*
1485 * reposition in fifo if next is older than rq
1486 */
1487 if (!list_empty(&rq->queuelist) && !list_empty(&next->queuelist) &&
Jens Axboe30996f42009-10-05 11:03:39 +02001488 time_before(rq_fifo_time(next), rq_fifo_time(rq))) {
Jens Axboe22e2c502005-06-27 10:55:12 +02001489 list_move(&rq->queuelist, &next->queuelist);
Jens Axboe30996f42009-10-05 11:03:39 +02001490 rq_set_fifo_time(rq, rq_fifo_time(next));
1491 }
Jens Axboe22e2c502005-06-27 10:55:12 +02001492
Corrado Zoccolocf7c25c2009-11-08 17:16:46 +01001493 if (cfqq->next_rq == next)
1494 cfqq->next_rq = rq;
Jens Axboeb4878f22005-10-20 16:42:29 +02001495 cfq_remove_request(next);
Jens Axboe22e2c502005-06-27 10:55:12 +02001496}
1497
Jens Axboe165125e2007-07-24 09:28:11 +02001498static int cfq_allow_merge(struct request_queue *q, struct request *rq,
Jens Axboeda775262006-12-20 11:04:12 +01001499 struct bio *bio)
1500{
1501 struct cfq_data *cfqd = q->elevator->elevator_data;
Vasily Tarasov91fac312007-04-25 12:29:51 +02001502 struct cfq_io_context *cic;
Jens Axboeda775262006-12-20 11:04:12 +01001503 struct cfq_queue *cfqq;
Jens Axboeda775262006-12-20 11:04:12 +01001504
1505 /*
Jens Axboeec8acb62007-01-02 18:32:11 +01001506 * Disallow merge of a sync bio into an async request.
Jens Axboeda775262006-12-20 11:04:12 +01001507 */
Vasily Tarasov91fac312007-04-25 12:29:51 +02001508 if (cfq_bio_sync(bio) && !rq_is_sync(rq))
Jens Axboea6151c32009-10-07 20:02:57 +02001509 return false;
Jens Axboeda775262006-12-20 11:04:12 +01001510
1511 /*
Jens Axboe719d3402006-12-22 09:38:53 +01001512 * Lookup the cfqq that this bio will be queued with. Allow
1513 * merge only if rq is queued there.
Jens Axboeda775262006-12-20 11:04:12 +01001514 */
Jens Axboe4ac845a2008-01-24 08:44:49 +01001515 cic = cfq_cic_lookup(cfqd, current->io_context);
Vasily Tarasov91fac312007-04-25 12:29:51 +02001516 if (!cic)
Jens Axboea6151c32009-10-07 20:02:57 +02001517 return false;
Jens Axboe719d3402006-12-22 09:38:53 +01001518
Vasily Tarasov91fac312007-04-25 12:29:51 +02001519 cfqq = cic_to_cfqq(cic, cfq_bio_sync(bio));
Jens Axboea6151c32009-10-07 20:02:57 +02001520 return cfqq == RQ_CFQQ(rq);
Jens Axboeda775262006-12-20 11:04:12 +01001521}
1522
Jens Axboefebffd62008-01-28 13:19:43 +01001523static void __cfq_set_active_queue(struct cfq_data *cfqd,
1524 struct cfq_queue *cfqq)
Jens Axboe22e2c502005-06-27 10:55:12 +02001525{
1526 if (cfqq) {
Divyesh Shahb1ffe732010-03-25 15:45:03 +01001527 cfq_log_cfqq(cfqd, cfqq, "set_active wl_prio:%d wl_type:%d",
1528 cfqd->serving_prio, cfqd->serving_type);
Vivek Goyaldae739e2009-12-03 12:59:45 -05001529 cfqq->slice_start = 0;
1530 cfqq->dispatch_start = jiffies;
Vivek Goyalf75edf22009-12-03 12:59:53 -05001531 cfqq->allocated_slice = 0;
Jens Axboe22e2c502005-06-27 10:55:12 +02001532 cfqq->slice_end = 0;
Jens Axboe2f5cb732009-04-07 08:51:19 +02001533 cfqq->slice_dispatch = 0;
Vivek Goyal22084192009-12-03 12:59:49 -05001534 cfqq->nr_sectors = 0;
Jens Axboe2f5cb732009-04-07 08:51:19 +02001535
Jens Axboe2f5cb732009-04-07 08:51:19 +02001536 cfq_clear_cfqq_wait_request(cfqq);
Jens Axboeb0291952009-04-07 11:38:31 +02001537 cfq_clear_cfqq_must_dispatch(cfqq);
Jens Axboe3b181522005-06-27 10:56:24 +02001538 cfq_clear_cfqq_must_alloc_slice(cfqq);
1539 cfq_clear_cfqq_fifo_expire(cfqq);
Jens Axboe44f7c162007-01-19 11:51:58 +11001540 cfq_mark_cfqq_slice_new(cfqq);
Jens Axboe2f5cb732009-04-07 08:51:19 +02001541
1542 del_timer(&cfqd->idle_slice_timer);
Jens Axboe22e2c502005-06-27 10:55:12 +02001543 }
1544
1545 cfqd->active_queue = cfqq;
1546}
1547
1548/*
Jens Axboe7b14e3b2006-02-28 09:35:11 +01001549 * current cfqq expired its slice (or was too idle), select new one
1550 */
1551static void
1552__cfq_slice_expired(struct cfq_data *cfqd, struct cfq_queue *cfqq,
Jens Axboea6151c32009-10-07 20:02:57 +02001553 bool timed_out)
Jens Axboe7b14e3b2006-02-28 09:35:11 +01001554{
Jens Axboe7b679132008-05-30 12:23:07 +02001555 cfq_log_cfqq(cfqd, cfqq, "slice expired t=%d", timed_out);
1556
Jens Axboe7b14e3b2006-02-28 09:35:11 +01001557 if (cfq_cfqq_wait_request(cfqq))
1558 del_timer(&cfqd->idle_slice_timer);
1559
Jens Axboe7b14e3b2006-02-28 09:35:11 +01001560 cfq_clear_cfqq_wait_request(cfqq);
Vivek Goyalf75edf22009-12-03 12:59:53 -05001561 cfq_clear_cfqq_wait_busy(cfqq);
Jens Axboe7b14e3b2006-02-28 09:35:11 +01001562
1563 /*
Shaohua Liae54abe2010-02-05 13:11:45 +01001564 * If this cfqq is shared between multiple processes, check to
1565 * make sure that those processes are still issuing I/Os within
1566 * the mean seek distance. If not, it may be time to break the
1567 * queues apart again.
1568 */
1569 if (cfq_cfqq_coop(cfqq) && CFQQ_SEEKY(cfqq))
1570 cfq_mark_cfqq_split_coop(cfqq);
1571
1572 /*
Jens Axboe6084cdd2007-04-23 08:25:00 +02001573 * store what was left of this slice, if the queue idled/timed out
Jens Axboe7b14e3b2006-02-28 09:35:11 +01001574 */
Jens Axboe7b679132008-05-30 12:23:07 +02001575 if (timed_out && !cfq_cfqq_slice_new(cfqq)) {
Jens Axboec5b680f2007-01-19 11:56:49 +11001576 cfqq->slice_resid = cfqq->slice_end - jiffies;
Jens Axboe7b679132008-05-30 12:23:07 +02001577 cfq_log_cfqq(cfqd, cfqq, "resid=%ld", cfqq->slice_resid);
1578 }
Jens Axboe7b14e3b2006-02-28 09:35:11 +01001579
Vivek Goyaldae739e2009-12-03 12:59:45 -05001580 cfq_group_served(cfqd, cfqq->cfqg, cfqq);
1581
Vivek Goyalf04a6422009-12-03 12:59:40 -05001582 if (cfq_cfqq_on_rr(cfqq) && RB_EMPTY_ROOT(&cfqq->sort_list))
1583 cfq_del_cfqq_rr(cfqd, cfqq);
1584
Jens Axboeedd75ff2007-04-19 12:03:34 +02001585 cfq_resort_rr_list(cfqd, cfqq);
Jens Axboe7b14e3b2006-02-28 09:35:11 +01001586
1587 if (cfqq == cfqd->active_queue)
1588 cfqd->active_queue = NULL;
1589
Vivek Goyaldae739e2009-12-03 12:59:45 -05001590 if (&cfqq->cfqg->rb_node == cfqd->grp_service_tree.active)
1591 cfqd->grp_service_tree.active = NULL;
1592
Jens Axboe7b14e3b2006-02-28 09:35:11 +01001593 if (cfqd->active_cic) {
1594 put_io_context(cfqd->active_cic->ioc);
1595 cfqd->active_cic = NULL;
1596 }
Jens Axboe7b14e3b2006-02-28 09:35:11 +01001597}
1598
Jens Axboea6151c32009-10-07 20:02:57 +02001599static inline void cfq_slice_expired(struct cfq_data *cfqd, bool timed_out)
Jens Axboe7b14e3b2006-02-28 09:35:11 +01001600{
1601 struct cfq_queue *cfqq = cfqd->active_queue;
1602
1603 if (cfqq)
Jens Axboe6084cdd2007-04-23 08:25:00 +02001604 __cfq_slice_expired(cfqd, cfqq, timed_out);
Jens Axboe7b14e3b2006-02-28 09:35:11 +01001605}
1606
Jens Axboe498d3aa2007-04-26 12:54:48 +02001607/*
1608 * Get next queue for service. Unless we have a queue preemption,
1609 * we'll simply select the first cfqq in the service tree.
1610 */
Jens Axboe6d048f52007-04-25 12:44:27 +02001611static struct cfq_queue *cfq_get_next_queue(struct cfq_data *cfqd)
Jens Axboe22e2c502005-06-27 10:55:12 +02001612{
Corrado Zoccoloc0324a02009-10-27 19:16:03 +01001613 struct cfq_rb_root *service_tree =
Vivek Goyalcdb16e82009-12-03 12:59:38 -05001614 service_tree_for(cfqd->serving_group, cfqd->serving_prio,
Vivek Goyal65b32a52009-12-16 17:52:59 -05001615 cfqd->serving_type);
Jens Axboeedd75ff2007-04-19 12:03:34 +02001616
Vivek Goyalf04a6422009-12-03 12:59:40 -05001617 if (!cfqd->rq_queued)
1618 return NULL;
1619
Vivek Goyal1fa8f6d2009-12-03 12:59:41 -05001620 /* There is nothing to dispatch */
1621 if (!service_tree)
1622 return NULL;
Corrado Zoccoloc0324a02009-10-27 19:16:03 +01001623 if (RB_EMPTY_ROOT(&service_tree->rb))
1624 return NULL;
1625 return cfq_rb_first(service_tree);
Jens Axboe6d048f52007-04-25 12:44:27 +02001626}
1627
Vivek Goyalf04a6422009-12-03 12:59:40 -05001628static struct cfq_queue *cfq_get_next_queue_forced(struct cfq_data *cfqd)
1629{
Vivek Goyal25fb5162009-12-03 12:59:46 -05001630 struct cfq_group *cfqg;
Vivek Goyalf04a6422009-12-03 12:59:40 -05001631 struct cfq_queue *cfqq;
1632 int i, j;
1633 struct cfq_rb_root *st;
1634
1635 if (!cfqd->rq_queued)
1636 return NULL;
1637
Vivek Goyal25fb5162009-12-03 12:59:46 -05001638 cfqg = cfq_get_next_cfqg(cfqd);
1639 if (!cfqg)
1640 return NULL;
1641
Vivek Goyalf04a6422009-12-03 12:59:40 -05001642 for_each_cfqg_st(cfqg, i, j, st)
1643 if ((cfqq = cfq_rb_first(st)) != NULL)
1644 return cfqq;
1645 return NULL;
1646}
1647
Jens Axboe498d3aa2007-04-26 12:54:48 +02001648/*
1649 * Get and set a new active queue for service.
1650 */
Jens Axboea36e71f2009-04-15 12:15:11 +02001651static struct cfq_queue *cfq_set_active_queue(struct cfq_data *cfqd,
1652 struct cfq_queue *cfqq)
Jens Axboe6d048f52007-04-25 12:44:27 +02001653{
Jens Axboee00ef792009-11-04 08:54:55 +01001654 if (!cfqq)
Jens Axboea36e71f2009-04-15 12:15:11 +02001655 cfqq = cfq_get_next_queue(cfqd);
Jens Axboe6d048f52007-04-25 12:44:27 +02001656
Jens Axboe22e2c502005-06-27 10:55:12 +02001657 __cfq_set_active_queue(cfqd, cfqq);
Jens Axboe3b181522005-06-27 10:56:24 +02001658 return cfqq;
Jens Axboe22e2c502005-06-27 10:55:12 +02001659}
1660
Jens Axboed9e76202007-04-20 14:27:50 +02001661static inline sector_t cfq_dist_from_last(struct cfq_data *cfqd,
1662 struct request *rq)
1663{
Tejun Heo83096eb2009-05-07 22:24:39 +09001664 if (blk_rq_pos(rq) >= cfqd->last_position)
1665 return blk_rq_pos(rq) - cfqd->last_position;
Jens Axboed9e76202007-04-20 14:27:50 +02001666 else
Tejun Heo83096eb2009-05-07 22:24:39 +09001667 return cfqd->last_position - blk_rq_pos(rq);
Jens Axboed9e76202007-04-20 14:27:50 +02001668}
1669
Jeff Moyerb2c18e12009-10-23 17:14:49 -04001670static inline int cfq_rq_close(struct cfq_data *cfqd, struct cfq_queue *cfqq,
Shaohua Lie9ce3352010-03-19 08:03:04 +01001671 struct request *rq)
Jens Axboe6d048f52007-04-25 12:44:27 +02001672{
Shaohua Lie9ce3352010-03-19 08:03:04 +01001673 return cfq_dist_from_last(cfqd, rq) <= CFQQ_CLOSE_THR;
Jens Axboe6d048f52007-04-25 12:44:27 +02001674}
1675
Jens Axboea36e71f2009-04-15 12:15:11 +02001676static struct cfq_queue *cfqq_close(struct cfq_data *cfqd,
1677 struct cfq_queue *cur_cfqq)
Jens Axboe6d048f52007-04-25 12:44:27 +02001678{
Jens Axboef2d1f0a2009-04-23 12:19:38 +02001679 struct rb_root *root = &cfqd->prio_trees[cur_cfqq->org_ioprio];
Jens Axboea36e71f2009-04-15 12:15:11 +02001680 struct rb_node *parent, *node;
1681 struct cfq_queue *__cfqq;
1682 sector_t sector = cfqd->last_position;
1683
1684 if (RB_EMPTY_ROOT(root))
1685 return NULL;
1686
1687 /*
1688 * First, if we find a request starting at the end of the last
1689 * request, choose it.
1690 */
Jens Axboef2d1f0a2009-04-23 12:19:38 +02001691 __cfqq = cfq_prio_tree_lookup(cfqd, root, sector, &parent, NULL);
Jens Axboea36e71f2009-04-15 12:15:11 +02001692 if (__cfqq)
1693 return __cfqq;
1694
1695 /*
1696 * If the exact sector wasn't found, the parent of the NULL leaf
1697 * will contain the closest sector.
1698 */
1699 __cfqq = rb_entry(parent, struct cfq_queue, p_node);
Shaohua Lie9ce3352010-03-19 08:03:04 +01001700 if (cfq_rq_close(cfqd, cur_cfqq, __cfqq->next_rq))
Jens Axboea36e71f2009-04-15 12:15:11 +02001701 return __cfqq;
1702
Tejun Heo2e46e8b2009-05-07 22:24:41 +09001703 if (blk_rq_pos(__cfqq->next_rq) < sector)
Jens Axboea36e71f2009-04-15 12:15:11 +02001704 node = rb_next(&__cfqq->p_node);
1705 else
1706 node = rb_prev(&__cfqq->p_node);
1707 if (!node)
1708 return NULL;
1709
1710 __cfqq = rb_entry(node, struct cfq_queue, p_node);
Shaohua Lie9ce3352010-03-19 08:03:04 +01001711 if (cfq_rq_close(cfqd, cur_cfqq, __cfqq->next_rq))
Jens Axboea36e71f2009-04-15 12:15:11 +02001712 return __cfqq;
1713
1714 return NULL;
1715}
1716
1717/*
1718 * cfqd - obvious
1719 * cur_cfqq - passed in so that we don't decide that the current queue is
1720 * closely cooperating with itself.
1721 *
1722 * So, basically we're assuming that that cur_cfqq has dispatched at least
1723 * one request, and that cfqd->last_position reflects a position on the disk
1724 * associated with the I/O issued by cur_cfqq. I'm not sure this is a valid
1725 * assumption.
1726 */
1727static struct cfq_queue *cfq_close_cooperator(struct cfq_data *cfqd,
Jeff Moyerb3b6d042009-10-23 17:14:51 -04001728 struct cfq_queue *cur_cfqq)
Jens Axboea36e71f2009-04-15 12:15:11 +02001729{
1730 struct cfq_queue *cfqq;
1731
Divyesh Shah39c01b22010-03-25 15:45:57 +01001732 if (cfq_class_idle(cur_cfqq))
1733 return NULL;
Jeff Moyere6c5bc72009-10-23 17:14:52 -04001734 if (!cfq_cfqq_sync(cur_cfqq))
1735 return NULL;
1736 if (CFQQ_SEEKY(cur_cfqq))
1737 return NULL;
1738
Jens Axboea36e71f2009-04-15 12:15:11 +02001739 /*
Gui Jianfengb9d8f4c2009-12-08 08:54:17 +01001740 * Don't search priority tree if it's the only queue in the group.
1741 */
1742 if (cur_cfqq->cfqg->nr_cfqq == 1)
1743 return NULL;
1744
1745 /*
Jens Axboed9e76202007-04-20 14:27:50 +02001746 * We should notice if some of the queues are cooperating, eg
1747 * working closely on the same area of the disk. In that case,
1748 * we can group them together and don't waste time idling.
Jens Axboe6d048f52007-04-25 12:44:27 +02001749 */
Jens Axboea36e71f2009-04-15 12:15:11 +02001750 cfqq = cfqq_close(cfqd, cur_cfqq);
1751 if (!cfqq)
1752 return NULL;
1753
Vivek Goyal8682e1f2009-12-03 12:59:50 -05001754 /* If new queue belongs to different cfq_group, don't choose it */
1755 if (cur_cfqq->cfqg != cfqq->cfqg)
1756 return NULL;
1757
Jeff Moyerdf5fe3e2009-10-23 17:14:50 -04001758 /*
1759 * It only makes sense to merge sync queues.
1760 */
1761 if (!cfq_cfqq_sync(cfqq))
1762 return NULL;
Jeff Moyere6c5bc72009-10-23 17:14:52 -04001763 if (CFQQ_SEEKY(cfqq))
1764 return NULL;
Jeff Moyerdf5fe3e2009-10-23 17:14:50 -04001765
Corrado Zoccoloc0324a02009-10-27 19:16:03 +01001766 /*
1767 * Do not merge queues of different priority classes
1768 */
1769 if (cfq_class_rt(cfqq) != cfq_class_rt(cur_cfqq))
1770 return NULL;
1771
Jens Axboea36e71f2009-04-15 12:15:11 +02001772 return cfqq;
Jens Axboe6d048f52007-04-25 12:44:27 +02001773}
1774
Corrado Zoccoloa6d44e92009-10-26 22:45:11 +01001775/*
1776 * Determine whether we should enforce idle window for this queue.
1777 */
1778
1779static bool cfq_should_idle(struct cfq_data *cfqd, struct cfq_queue *cfqq)
1780{
1781 enum wl_prio_t prio = cfqq_prio(cfqq);
Corrado Zoccolo718eee02009-10-26 22:45:29 +01001782 struct cfq_rb_root *service_tree = cfqq->service_tree;
Corrado Zoccoloa6d44e92009-10-26 22:45:11 +01001783
Vivek Goyalf04a6422009-12-03 12:59:40 -05001784 BUG_ON(!service_tree);
1785 BUG_ON(!service_tree->count);
1786
Corrado Zoccoloa6d44e92009-10-26 22:45:11 +01001787 /* We never do for idle class queues. */
1788 if (prio == IDLE_WORKLOAD)
1789 return false;
1790
1791 /* We do for queues that were marked with idle window flag. */
Shaohua Li3c764b72009-12-04 13:12:06 +01001792 if (cfq_cfqq_idle_window(cfqq) &&
1793 !(blk_queue_nonrot(cfqd->queue) && cfqd->hw_tag))
Corrado Zoccoloa6d44e92009-10-26 22:45:11 +01001794 return true;
1795
1796 /*
1797 * Otherwise, we do only if they are the last ones
1798 * in their service tree.
1799 */
Divyesh Shahb1ffe732010-03-25 15:45:03 +01001800 if (service_tree->count == 1 && cfq_cfqq_sync(cfqq))
1801 return 1;
1802 cfq_log_cfqq(cfqd, cfqq, "Not idling. st->count:%d",
1803 service_tree->count);
1804 return 0;
Corrado Zoccoloa6d44e92009-10-26 22:45:11 +01001805}
1806
Jens Axboe6d048f52007-04-25 12:44:27 +02001807static void cfq_arm_slice_timer(struct cfq_data *cfqd)
Jens Axboe22e2c502005-06-27 10:55:12 +02001808{
Jens Axboe17926692007-01-19 11:59:30 +11001809 struct cfq_queue *cfqq = cfqd->active_queue;
Jens Axboe206dc692006-03-28 13:03:44 +02001810 struct cfq_io_context *cic;
Jens Axboe7b14e3b2006-02-28 09:35:11 +01001811 unsigned long sl;
1812
Jens Axboea68bbdd2008-09-24 13:03:33 +02001813 /*
Jens Axboef7d7b7a2008-09-25 11:37:50 +02001814 * SSD device without seek penalty, disable idling. But only do so
1815 * for devices that support queuing, otherwise we still have a problem
1816 * with sync vs async workloads.
Jens Axboea68bbdd2008-09-24 13:03:33 +02001817 */
Jens Axboef7d7b7a2008-09-25 11:37:50 +02001818 if (blk_queue_nonrot(cfqd->queue) && cfqd->hw_tag)
Jens Axboea68bbdd2008-09-24 13:03:33 +02001819 return;
1820
Jens Axboedd67d052006-06-21 09:36:18 +02001821 WARN_ON(!RB_EMPTY_ROOT(&cfqq->sort_list));
Jens Axboe6d048f52007-04-25 12:44:27 +02001822 WARN_ON(cfq_cfqq_slice_new(cfqq));
Jens Axboe22e2c502005-06-27 10:55:12 +02001823
1824 /*
1825 * idle is disabled, either manually or by past process history
1826 */
Corrado Zoccoloa6d44e92009-10-26 22:45:11 +01001827 if (!cfqd->cfq_slice_idle || !cfq_should_idle(cfqd, cfqq))
Jens Axboe6d048f52007-04-25 12:44:27 +02001828 return;
1829
Jens Axboe22e2c502005-06-27 10:55:12 +02001830 /*
Corrado Zoccolo8e550632009-11-26 10:02:58 +01001831 * still active requests from this queue, don't idle
Jens Axboe7b679132008-05-30 12:23:07 +02001832 */
Corrado Zoccolo8e550632009-11-26 10:02:58 +01001833 if (cfqq->dispatched)
Jens Axboe7b679132008-05-30 12:23:07 +02001834 return;
1835
1836 /*
Jens Axboe22e2c502005-06-27 10:55:12 +02001837 * task has exited, don't wait
1838 */
Jens Axboe206dc692006-03-28 13:03:44 +02001839 cic = cfqd->active_cic;
Nikanth Karthikesan66dac982007-11-27 12:47:04 +01001840 if (!cic || !atomic_read(&cic->ioc->nr_tasks))
Jens Axboe6d048f52007-04-25 12:44:27 +02001841 return;
1842
Corrado Zoccolo355b6592009-10-08 08:43:32 +02001843 /*
1844 * If our average think time is larger than the remaining time
1845 * slice, then don't idle. This avoids overrunning the allotted
1846 * time slice.
1847 */
1848 if (sample_valid(cic->ttime_samples) &&
Divyesh Shahb1ffe732010-03-25 15:45:03 +01001849 (cfqq->slice_end - jiffies < cic->ttime_mean)) {
1850 cfq_log_cfqq(cfqd, cfqq, "Not idling. think_time:%d",
1851 cic->ttime_mean);
Corrado Zoccolo355b6592009-10-08 08:43:32 +02001852 return;
Divyesh Shahb1ffe732010-03-25 15:45:03 +01001853 }
Corrado Zoccolo355b6592009-10-08 08:43:32 +02001854
Jens Axboe3b181522005-06-27 10:56:24 +02001855 cfq_mark_cfqq_wait_request(cfqq);
Jens Axboe22e2c502005-06-27 10:55:12 +02001856
Jens Axboe6d048f52007-04-25 12:44:27 +02001857 sl = cfqd->cfq_slice_idle;
Jens Axboe206dc692006-03-28 13:03:44 +02001858
Jens Axboe7b14e3b2006-02-28 09:35:11 +01001859 mod_timer(&cfqd->idle_slice_timer, jiffies + sl);
Jens Axboe9481ffd2009-04-15 12:14:13 +02001860 cfq_log_cfqq(cfqd, cfqq, "arm_idle: %lu", sl);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001861}
1862
Jens Axboe498d3aa2007-04-26 12:54:48 +02001863/*
1864 * Move request from internal lists to the request queue dispatch list.
1865 */
Jens Axboe165125e2007-07-24 09:28:11 +02001866static void cfq_dispatch_insert(struct request_queue *q, struct request *rq)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001867{
Jens Axboe3ed9a292007-04-23 08:33:33 +02001868 struct cfq_data *cfqd = q->elevator->elevator_data;
Jens Axboe5e705372006-07-13 12:39:25 +02001869 struct cfq_queue *cfqq = RQ_CFQQ(rq);
Jens Axboe22e2c502005-06-27 10:55:12 +02001870
Jens Axboe7b679132008-05-30 12:23:07 +02001871 cfq_log_cfqq(cfqd, cfqq, "dispatch_insert");
1872
Jeff Moyer06d21882009-09-11 17:08:59 +02001873 cfqq->next_rq = cfq_find_next_rq(cfqd, cfqq, rq);
Jens Axboe5380a102006-07-13 12:37:56 +02001874 cfq_remove_request(rq);
Jens Axboe6d048f52007-04-25 12:44:27 +02001875 cfqq->dispatched++;
Jens Axboe5380a102006-07-13 12:37:56 +02001876 elv_dispatch_sort(q, rq);
Jens Axboe3ed9a292007-04-23 08:33:33 +02001877
Corrado Zoccolo53c583d2010-02-28 19:45:05 +01001878 cfqd->rq_in_flight[cfq_cfqq_sync(cfqq)]++;
Vivek Goyal22084192009-12-03 12:59:49 -05001879 cfqq->nr_sectors += blk_rq_sectors(rq);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001880}
1881
1882/*
1883 * return expired entry, or NULL to just start from scratch in rbtree
1884 */
Jens Axboefebffd62008-01-28 13:19:43 +01001885static struct request *cfq_check_fifo(struct cfq_queue *cfqq)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001886{
Jens Axboe30996f42009-10-05 11:03:39 +02001887 struct request *rq = NULL;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001888
Jens Axboe3b181522005-06-27 10:56:24 +02001889 if (cfq_cfqq_fifo_expire(cfqq))
Linus Torvalds1da177e2005-04-16 15:20:36 -07001890 return NULL;
Jens Axboecb887412007-01-19 12:01:16 +11001891
1892 cfq_mark_cfqq_fifo_expire(cfqq);
1893
Jens Axboe89850f72006-07-22 16:48:31 +02001894 if (list_empty(&cfqq->fifo))
1895 return NULL;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001896
Jens Axboe89850f72006-07-22 16:48:31 +02001897 rq = rq_entry_fifo(cfqq->fifo.next);
Jens Axboe30996f42009-10-05 11:03:39 +02001898 if (time_before(jiffies, rq_fifo_time(rq)))
Jens Axboe7b679132008-05-30 12:23:07 +02001899 rq = NULL;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001900
Jens Axboe30996f42009-10-05 11:03:39 +02001901 cfq_log_cfqq(cfqq->cfqd, cfqq, "fifo=%p", rq);
Jens Axboe6d048f52007-04-25 12:44:27 +02001902 return rq;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001903}
1904
Jens Axboe22e2c502005-06-27 10:55:12 +02001905static inline int
1906cfq_prio_to_maxrq(struct cfq_data *cfqd, struct cfq_queue *cfqq)
1907{
1908 const int base_rq = cfqd->cfq_slice_async_rq;
1909
1910 WARN_ON(cfqq->ioprio >= IOPRIO_BE_NR);
1911
1912 return 2 * (base_rq + base_rq * (CFQ_PRIO_LISTS - 1 - cfqq->ioprio));
1913}
1914
1915/*
Jeff Moyerdf5fe3e2009-10-23 17:14:50 -04001916 * Must be called with the queue_lock held.
1917 */
1918static int cfqq_process_refs(struct cfq_queue *cfqq)
1919{
1920 int process_refs, io_refs;
1921
1922 io_refs = cfqq->allocated[READ] + cfqq->allocated[WRITE];
1923 process_refs = atomic_read(&cfqq->ref) - io_refs;
1924 BUG_ON(process_refs < 0);
1925 return process_refs;
1926}
1927
1928static void cfq_setup_merge(struct cfq_queue *cfqq, struct cfq_queue *new_cfqq)
1929{
Jeff Moyere6c5bc72009-10-23 17:14:52 -04001930 int process_refs, new_process_refs;
Jeff Moyerdf5fe3e2009-10-23 17:14:50 -04001931 struct cfq_queue *__cfqq;
1932
1933 /* Avoid a circular list and skip interim queue merges */
1934 while ((__cfqq = new_cfqq->new_cfqq)) {
1935 if (__cfqq == cfqq)
1936 return;
1937 new_cfqq = __cfqq;
1938 }
1939
1940 process_refs = cfqq_process_refs(cfqq);
1941 /*
1942 * If the process for the cfqq has gone away, there is no
1943 * sense in merging the queues.
1944 */
1945 if (process_refs == 0)
1946 return;
1947
Jeff Moyere6c5bc72009-10-23 17:14:52 -04001948 /*
1949 * Merge in the direction of the lesser amount of work.
1950 */
1951 new_process_refs = cfqq_process_refs(new_cfqq);
1952 if (new_process_refs >= process_refs) {
1953 cfqq->new_cfqq = new_cfqq;
1954 atomic_add(process_refs, &new_cfqq->ref);
1955 } else {
1956 new_cfqq->new_cfqq = cfqq;
1957 atomic_add(new_process_refs, &cfqq->ref);
1958 }
Jeff Moyerdf5fe3e2009-10-23 17:14:50 -04001959}
1960
Vivek Goyalcdb16e82009-12-03 12:59:38 -05001961static enum wl_type_t cfq_choose_wl(struct cfq_data *cfqd,
Vivek Goyal65b32a52009-12-16 17:52:59 -05001962 struct cfq_group *cfqg, enum wl_prio_t prio)
Corrado Zoccolo718eee02009-10-26 22:45:29 +01001963{
1964 struct cfq_queue *queue;
1965 int i;
1966 bool key_valid = false;
1967 unsigned long lowest_key = 0;
1968 enum wl_type_t cur_best = SYNC_NOIDLE_WORKLOAD;
1969
Vivek Goyal65b32a52009-12-16 17:52:59 -05001970 for (i = 0; i <= SYNC_WORKLOAD; ++i) {
1971 /* select the one with lowest rb_key */
1972 queue = cfq_rb_first(service_tree_for(cfqg, prio, i));
Corrado Zoccolo718eee02009-10-26 22:45:29 +01001973 if (queue &&
1974 (!key_valid || time_before(queue->rb_key, lowest_key))) {
1975 lowest_key = queue->rb_key;
1976 cur_best = i;
1977 key_valid = true;
1978 }
1979 }
1980
1981 return cur_best;
1982}
1983
Vivek Goyalcdb16e82009-12-03 12:59:38 -05001984static void choose_service_tree(struct cfq_data *cfqd, struct cfq_group *cfqg)
Corrado Zoccolo718eee02009-10-26 22:45:29 +01001985{
Corrado Zoccolo718eee02009-10-26 22:45:29 +01001986 unsigned slice;
1987 unsigned count;
Vivek Goyalcdb16e82009-12-03 12:59:38 -05001988 struct cfq_rb_root *st;
Vivek Goyal58ff82f2009-12-03 12:59:44 -05001989 unsigned group_slice;
Corrado Zoccolo718eee02009-10-26 22:45:29 +01001990
Vivek Goyal1fa8f6d2009-12-03 12:59:41 -05001991 if (!cfqg) {
1992 cfqd->serving_prio = IDLE_WORKLOAD;
1993 cfqd->workload_expires = jiffies + 1;
1994 return;
1995 }
1996
Corrado Zoccolo718eee02009-10-26 22:45:29 +01001997 /* Choose next priority. RT > BE > IDLE */
Vivek Goyal58ff82f2009-12-03 12:59:44 -05001998 if (cfq_group_busy_queues_wl(RT_WORKLOAD, cfqd, cfqg))
Corrado Zoccolo718eee02009-10-26 22:45:29 +01001999 cfqd->serving_prio = RT_WORKLOAD;
Vivek Goyal58ff82f2009-12-03 12:59:44 -05002000 else if (cfq_group_busy_queues_wl(BE_WORKLOAD, cfqd, cfqg))
Corrado Zoccolo718eee02009-10-26 22:45:29 +01002001 cfqd->serving_prio = BE_WORKLOAD;
2002 else {
2003 cfqd->serving_prio = IDLE_WORKLOAD;
2004 cfqd->workload_expires = jiffies + 1;
2005 return;
2006 }
2007
2008 /*
2009 * For RT and BE, we have to choose also the type
2010 * (SYNC, SYNC_NOIDLE, ASYNC), and to compute a workload
2011 * expiration time
2012 */
Vivek Goyal65b32a52009-12-16 17:52:59 -05002013 st = service_tree_for(cfqg, cfqd->serving_prio, cfqd->serving_type);
Vivek Goyalcdb16e82009-12-03 12:59:38 -05002014 count = st->count;
Corrado Zoccolo718eee02009-10-26 22:45:29 +01002015
2016 /*
Vivek Goyal65b32a52009-12-16 17:52:59 -05002017 * check workload expiration, and that we still have other queues ready
Corrado Zoccolo718eee02009-10-26 22:45:29 +01002018 */
Vivek Goyal65b32a52009-12-16 17:52:59 -05002019 if (count && !time_after(jiffies, cfqd->workload_expires))
Corrado Zoccolo718eee02009-10-26 22:45:29 +01002020 return;
2021
2022 /* otherwise select new workload type */
2023 cfqd->serving_type =
Vivek Goyal65b32a52009-12-16 17:52:59 -05002024 cfq_choose_wl(cfqd, cfqg, cfqd->serving_prio);
2025 st = service_tree_for(cfqg, cfqd->serving_prio, cfqd->serving_type);
Vivek Goyalcdb16e82009-12-03 12:59:38 -05002026 count = st->count;
Corrado Zoccolo718eee02009-10-26 22:45:29 +01002027
2028 /*
2029 * the workload slice is computed as a fraction of target latency
2030 * proportional to the number of queues in that workload, over
2031 * all the queues in the same priority class
2032 */
Vivek Goyal58ff82f2009-12-03 12:59:44 -05002033 group_slice = cfq_group_slice(cfqd, cfqg);
2034
2035 slice = group_slice * count /
2036 max_t(unsigned, cfqg->busy_queues_avg[cfqd->serving_prio],
2037 cfq_group_busy_queues_wl(cfqd->serving_prio, cfqd, cfqg));
Corrado Zoccolo718eee02009-10-26 22:45:29 +01002038
Vivek Goyalf26bd1f2009-12-03 12:59:54 -05002039 if (cfqd->serving_type == ASYNC_WORKLOAD) {
2040 unsigned int tmp;
2041
2042 /*
2043 * Async queues are currently system wide. Just taking
2044 * proportion of queues with-in same group will lead to higher
2045 * async ratio system wide as generally root group is going
2046 * to have higher weight. A more accurate thing would be to
2047 * calculate system wide asnc/sync ratio.
2048 */
2049 tmp = cfq_target_latency * cfqg_busy_async_queues(cfqd, cfqg);
2050 tmp = tmp/cfqd->busy_queues;
2051 slice = min_t(unsigned, slice, tmp);
2052
Corrado Zoccolo718eee02009-10-26 22:45:29 +01002053 /* async workload slice is scaled down according to
2054 * the sync/async slice ratio. */
2055 slice = slice * cfqd->cfq_slice[0] / cfqd->cfq_slice[1];
Vivek Goyalf26bd1f2009-12-03 12:59:54 -05002056 } else
Corrado Zoccolo718eee02009-10-26 22:45:29 +01002057 /* sync workload slice is at least 2 * cfq_slice_idle */
2058 slice = max(slice, 2 * cfqd->cfq_slice_idle);
2059
2060 slice = max_t(unsigned, slice, CFQ_MIN_TT);
Divyesh Shahb1ffe732010-03-25 15:45:03 +01002061 cfq_log(cfqd, "workload slice:%d", slice);
Corrado Zoccolo718eee02009-10-26 22:45:29 +01002062 cfqd->workload_expires = jiffies + slice;
Corrado Zoccolo8e550632009-11-26 10:02:58 +01002063 cfqd->noidle_tree_requires_idle = false;
Corrado Zoccolo718eee02009-10-26 22:45:29 +01002064}
2065
Vivek Goyal1fa8f6d2009-12-03 12:59:41 -05002066static struct cfq_group *cfq_get_next_cfqg(struct cfq_data *cfqd)
2067{
2068 struct cfq_rb_root *st = &cfqd->grp_service_tree;
Vivek Goyal25bc6b02009-12-03 12:59:43 -05002069 struct cfq_group *cfqg;
Vivek Goyal1fa8f6d2009-12-03 12:59:41 -05002070
2071 if (RB_EMPTY_ROOT(&st->rb))
2072 return NULL;
Vivek Goyal25bc6b02009-12-03 12:59:43 -05002073 cfqg = cfq_rb_first_group(st);
2074 st->active = &cfqg->rb_node;
2075 update_min_vdisktime(st);
2076 return cfqg;
Vivek Goyal1fa8f6d2009-12-03 12:59:41 -05002077}
2078
Vivek Goyalcdb16e82009-12-03 12:59:38 -05002079static void cfq_choose_cfqg(struct cfq_data *cfqd)
2080{
Vivek Goyal1fa8f6d2009-12-03 12:59:41 -05002081 struct cfq_group *cfqg = cfq_get_next_cfqg(cfqd);
2082
2083 cfqd->serving_group = cfqg;
Vivek Goyaldae739e2009-12-03 12:59:45 -05002084
2085 /* Restore the workload type data */
2086 if (cfqg->saved_workload_slice) {
2087 cfqd->workload_expires = jiffies + cfqg->saved_workload_slice;
2088 cfqd->serving_type = cfqg->saved_workload;
2089 cfqd->serving_prio = cfqg->saved_serving_prio;
Gui Jianfeng66ae2912009-12-15 10:08:45 +01002090 } else
2091 cfqd->workload_expires = jiffies - 1;
2092
Vivek Goyal1fa8f6d2009-12-03 12:59:41 -05002093 choose_service_tree(cfqd, cfqg);
Vivek Goyalcdb16e82009-12-03 12:59:38 -05002094}
2095
Jeff Moyerdf5fe3e2009-10-23 17:14:50 -04002096/*
Jens Axboe498d3aa2007-04-26 12:54:48 +02002097 * Select a queue for service. If we have a current active queue,
2098 * check whether to continue servicing it, or retrieve and set a new one.
Jens Axboe22e2c502005-06-27 10:55:12 +02002099 */
Tejun Heo1b5ed5e12005-11-10 08:49:19 +01002100static struct cfq_queue *cfq_select_queue(struct cfq_data *cfqd)
Jens Axboe22e2c502005-06-27 10:55:12 +02002101{
Jens Axboea36e71f2009-04-15 12:15:11 +02002102 struct cfq_queue *cfqq, *new_cfqq = NULL;
Jens Axboe22e2c502005-06-27 10:55:12 +02002103
2104 cfqq = cfqd->active_queue;
2105 if (!cfqq)
2106 goto new_queue;
2107
Vivek Goyalf04a6422009-12-03 12:59:40 -05002108 if (!cfqd->rq_queued)
2109 return NULL;
Vivek Goyalc244bb52009-12-08 17:52:57 -05002110
2111 /*
2112 * We were waiting for group to get backlogged. Expire the queue
2113 */
2114 if (cfq_cfqq_wait_busy(cfqq) && !RB_EMPTY_ROOT(&cfqq->sort_list))
2115 goto expire;
2116
Jens Axboe22e2c502005-06-27 10:55:12 +02002117 /*
Jens Axboe6d048f52007-04-25 12:44:27 +02002118 * The active queue has run out of time, expire it and select new.
Jens Axboe22e2c502005-06-27 10:55:12 +02002119 */
Vivek Goyal7667aa02009-12-08 17:52:58 -05002120 if (cfq_slice_used(cfqq) && !cfq_cfqq_must_dispatch(cfqq)) {
2121 /*
2122 * If slice had not expired at the completion of last request
2123 * we might not have turned on wait_busy flag. Don't expire
2124 * the queue yet. Allow the group to get backlogged.
2125 *
2126 * The very fact that we have used the slice, that means we
2127 * have been idling all along on this queue and it should be
2128 * ok to wait for this request to complete.
2129 */
Vivek Goyal82bbbf22009-12-10 19:25:41 +01002130 if (cfqq->cfqg->nr_cfqq == 1 && RB_EMPTY_ROOT(&cfqq->sort_list)
2131 && cfqq->dispatched && cfq_should_idle(cfqd, cfqq)) {
2132 cfqq = NULL;
Vivek Goyal7667aa02009-12-08 17:52:58 -05002133 goto keep_queue;
Vivek Goyal82bbbf22009-12-10 19:25:41 +01002134 } else
Vivek Goyal7667aa02009-12-08 17:52:58 -05002135 goto expire;
2136 }
Jens Axboe22e2c502005-06-27 10:55:12 +02002137
2138 /*
Jens Axboe6d048f52007-04-25 12:44:27 +02002139 * The active queue has requests and isn't expired, allow it to
2140 * dispatch.
Jens Axboe22e2c502005-06-27 10:55:12 +02002141 */
Jens Axboedd67d052006-06-21 09:36:18 +02002142 if (!RB_EMPTY_ROOT(&cfqq->sort_list))
Jens Axboe22e2c502005-06-27 10:55:12 +02002143 goto keep_queue;
Jens Axboe6d048f52007-04-25 12:44:27 +02002144
2145 /*
Jens Axboea36e71f2009-04-15 12:15:11 +02002146 * If another queue has a request waiting within our mean seek
2147 * distance, let it run. The expire code will check for close
2148 * cooperators and put the close queue at the front of the service
Jeff Moyerdf5fe3e2009-10-23 17:14:50 -04002149 * tree. If possible, merge the expiring queue with the new cfqq.
Jens Axboea36e71f2009-04-15 12:15:11 +02002150 */
Jeff Moyerb3b6d042009-10-23 17:14:51 -04002151 new_cfqq = cfq_close_cooperator(cfqd, cfqq);
Jeff Moyerdf5fe3e2009-10-23 17:14:50 -04002152 if (new_cfqq) {
2153 if (!cfqq->new_cfqq)
2154 cfq_setup_merge(cfqq, new_cfqq);
Jens Axboea36e71f2009-04-15 12:15:11 +02002155 goto expire;
Jeff Moyerdf5fe3e2009-10-23 17:14:50 -04002156 }
Jens Axboea36e71f2009-04-15 12:15:11 +02002157
2158 /*
Jens Axboe6d048f52007-04-25 12:44:27 +02002159 * No requests pending. If the active queue still has requests in
2160 * flight or is idling for a new request, allow either of these
2161 * conditions to happen (or time out) before selecting a new queue.
2162 */
Jens Axboecc197472007-04-20 20:45:39 +02002163 if (timer_pending(&cfqd->idle_slice_timer) ||
Corrado Zoccoloa6d44e92009-10-26 22:45:11 +01002164 (cfqq->dispatched && cfq_should_idle(cfqd, cfqq))) {
Jens Axboecaaa5f92006-06-16 11:23:00 +02002165 cfqq = NULL;
2166 goto keep_queue;
Jens Axboe22e2c502005-06-27 10:55:12 +02002167 }
2168
Jens Axboe3b181522005-06-27 10:56:24 +02002169expire:
Jens Axboe6084cdd2007-04-23 08:25:00 +02002170 cfq_slice_expired(cfqd, 0);
Jens Axboe3b181522005-06-27 10:56:24 +02002171new_queue:
Corrado Zoccolo718eee02009-10-26 22:45:29 +01002172 /*
2173 * Current queue expired. Check if we have to switch to a new
2174 * service tree
2175 */
2176 if (!new_cfqq)
Vivek Goyalcdb16e82009-12-03 12:59:38 -05002177 cfq_choose_cfqg(cfqd);
Corrado Zoccolo718eee02009-10-26 22:45:29 +01002178
Jens Axboea36e71f2009-04-15 12:15:11 +02002179 cfqq = cfq_set_active_queue(cfqd, new_cfqq);
Jens Axboe22e2c502005-06-27 10:55:12 +02002180keep_queue:
Jens Axboe3b181522005-06-27 10:56:24 +02002181 return cfqq;
Jens Axboe22e2c502005-06-27 10:55:12 +02002182}
2183
Jens Axboefebffd62008-01-28 13:19:43 +01002184static int __cfq_forced_dispatch_cfqq(struct cfq_queue *cfqq)
Jens Axboed9e76202007-04-20 14:27:50 +02002185{
2186 int dispatched = 0;
2187
2188 while (cfqq->next_rq) {
2189 cfq_dispatch_insert(cfqq->cfqd->queue, cfqq->next_rq);
2190 dispatched++;
2191 }
2192
2193 BUG_ON(!list_empty(&cfqq->fifo));
Vivek Goyalf04a6422009-12-03 12:59:40 -05002194
2195 /* By default cfqq is not expired if it is empty. Do it explicitly */
2196 __cfq_slice_expired(cfqq->cfqd, cfqq, 0);
Jens Axboed9e76202007-04-20 14:27:50 +02002197 return dispatched;
2198}
2199
Jens Axboe498d3aa2007-04-26 12:54:48 +02002200/*
2201 * Drain our current requests. Used for barriers and when switching
2202 * io schedulers on-the-fly.
2203 */
Jens Axboed9e76202007-04-20 14:27:50 +02002204static int cfq_forced_dispatch(struct cfq_data *cfqd)
Tejun Heo1b5ed5e12005-11-10 08:49:19 +01002205{
Jens Axboe08717142008-01-28 11:38:15 +01002206 struct cfq_queue *cfqq;
Jens Axboed9e76202007-04-20 14:27:50 +02002207 int dispatched = 0;
Vivek Goyalcdb16e82009-12-03 12:59:38 -05002208
Divyesh Shah3440c492010-04-09 09:29:57 +02002209 /* Expire the timeslice of the current active queue first */
Jens Axboe6084cdd2007-04-23 08:25:00 +02002210 cfq_slice_expired(cfqd, 0);
Divyesh Shah3440c492010-04-09 09:29:57 +02002211 while ((cfqq = cfq_get_next_queue_forced(cfqd)) != NULL) {
2212 __cfq_set_active_queue(cfqd, cfqq);
2213 dispatched += __cfq_forced_dispatch_cfqq(cfqq);
2214 }
2215
Tejun Heo1b5ed5e12005-11-10 08:49:19 +01002216 BUG_ON(cfqd->busy_queues);
2217
Jeff Moyer69237152009-06-12 15:29:30 +02002218 cfq_log(cfqd, "forced_dispatch=%d", dispatched);
Tejun Heo1b5ed5e12005-11-10 08:49:19 +01002219 return dispatched;
2220}
2221
Shaohua Liabc3c742010-03-01 09:20:54 +01002222static inline bool cfq_slice_used_soon(struct cfq_data *cfqd,
2223 struct cfq_queue *cfqq)
2224{
2225 /* the queue hasn't finished any request, can't estimate */
2226 if (cfq_cfqq_slice_new(cfqq))
2227 return 1;
2228 if (time_after(jiffies + cfqd->cfq_slice_idle * cfqq->dispatched,
2229 cfqq->slice_end))
2230 return 1;
2231
2232 return 0;
2233}
2234
Jens Axboe0b182d62009-10-06 20:49:37 +02002235static bool cfq_may_dispatch(struct cfq_data *cfqd, struct cfq_queue *cfqq)
Jens Axboe2f5cb732009-04-07 08:51:19 +02002236{
Jens Axboe2f5cb732009-04-07 08:51:19 +02002237 unsigned int max_dispatch;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002238
Jens Axboe2f5cb732009-04-07 08:51:19 +02002239 /*
Jens Axboe5ad531d2009-07-03 12:57:48 +02002240 * Drain async requests before we start sync IO
2241 */
Corrado Zoccolo53c583d2010-02-28 19:45:05 +01002242 if (cfq_should_idle(cfqd, cfqq) && cfqd->rq_in_flight[BLK_RW_ASYNC])
Jens Axboe0b182d62009-10-06 20:49:37 +02002243 return false;
Jens Axboe5ad531d2009-07-03 12:57:48 +02002244
2245 /*
Jens Axboe2f5cb732009-04-07 08:51:19 +02002246 * If this is an async queue and we have sync IO in flight, let it wait
2247 */
Corrado Zoccolo53c583d2010-02-28 19:45:05 +01002248 if (cfqd->rq_in_flight[BLK_RW_SYNC] && !cfq_cfqq_sync(cfqq))
Jens Axboe0b182d62009-10-06 20:49:37 +02002249 return false;
Jens Axboe2f5cb732009-04-07 08:51:19 +02002250
Shaohua Liabc3c742010-03-01 09:20:54 +01002251 max_dispatch = max_t(unsigned int, cfqd->cfq_quantum / 2, 1);
Jens Axboe2f5cb732009-04-07 08:51:19 +02002252 if (cfq_class_idle(cfqq))
2253 max_dispatch = 1;
2254
2255 /*
2256 * Does this cfqq already have too much IO in flight?
2257 */
2258 if (cfqq->dispatched >= max_dispatch) {
2259 /*
2260 * idle queue must always only have a single IO in flight
2261 */
Jens Axboe3ed9a292007-04-23 08:33:33 +02002262 if (cfq_class_idle(cfqq))
Jens Axboe0b182d62009-10-06 20:49:37 +02002263 return false;
Jens Axboe3ed9a292007-04-23 08:33:33 +02002264
Jens Axboe2f5cb732009-04-07 08:51:19 +02002265 /*
2266 * We have other queues, don't allow more IO from this one
2267 */
Shaohua Liabc3c742010-03-01 09:20:54 +01002268 if (cfqd->busy_queues > 1 && cfq_slice_used_soon(cfqd, cfqq))
Jens Axboe0b182d62009-10-06 20:49:37 +02002269 return false;
Jens Axboe9ede2092007-01-19 12:11:44 +11002270
Jens Axboe2f5cb732009-04-07 08:51:19 +02002271 /*
Shaohua Li474b18c2009-12-03 12:58:05 +01002272 * Sole queue user, no limit
Vivek Goyal365722b2009-10-03 15:21:27 +02002273 */
Shaohua Liabc3c742010-03-01 09:20:54 +01002274 if (cfqd->busy_queues == 1)
2275 max_dispatch = -1;
2276 else
2277 /*
2278 * Normally we start throttling cfqq when cfq_quantum/2
2279 * requests have been dispatched. But we can drive
2280 * deeper queue depths at the beginning of slice
2281 * subjected to upper limit of cfq_quantum.
2282 * */
2283 max_dispatch = cfqd->cfq_quantum;
Jens Axboe8e296752009-10-03 16:26:03 +02002284 }
2285
2286 /*
2287 * Async queues must wait a bit before being allowed dispatch.
2288 * We also ramp up the dispatch depth gradually for async IO,
2289 * based on the last sync IO we serviced
2290 */
Jens Axboe963b72f2009-10-03 19:42:18 +02002291 if (!cfq_cfqq_sync(cfqq) && cfqd->cfq_latency) {
Corrado Zoccolo573412b2009-12-06 11:48:52 +01002292 unsigned long last_sync = jiffies - cfqd->last_delayed_sync;
Jens Axboe8e296752009-10-03 16:26:03 +02002293 unsigned int depth;
Vivek Goyal365722b2009-10-03 15:21:27 +02002294
Jens Axboe61f0c1d2009-10-03 19:46:03 +02002295 depth = last_sync / cfqd->cfq_slice[1];
Jens Axboee00c54c2009-10-04 20:36:19 +02002296 if (!depth && !cfqq->dispatched)
2297 depth = 1;
Jens Axboe8e296752009-10-03 16:26:03 +02002298 if (depth < max_dispatch)
2299 max_dispatch = depth;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002300 }
2301
Jens Axboe0b182d62009-10-06 20:49:37 +02002302 /*
2303 * If we're below the current max, allow a dispatch
2304 */
2305 return cfqq->dispatched < max_dispatch;
2306}
2307
2308/*
2309 * Dispatch a request from cfqq, moving them to the request queue
2310 * dispatch list.
2311 */
2312static bool cfq_dispatch_request(struct cfq_data *cfqd, struct cfq_queue *cfqq)
2313{
2314 struct request *rq;
2315
2316 BUG_ON(RB_EMPTY_ROOT(&cfqq->sort_list));
2317
2318 if (!cfq_may_dispatch(cfqd, cfqq))
2319 return false;
2320
2321 /*
2322 * follow expired path, else get first next available
2323 */
2324 rq = cfq_check_fifo(cfqq);
2325 if (!rq)
2326 rq = cfqq->next_rq;
2327
2328 /*
2329 * insert request into driver dispatch list
2330 */
2331 cfq_dispatch_insert(cfqd->queue, rq);
2332
2333 if (!cfqd->active_cic) {
2334 struct cfq_io_context *cic = RQ_CIC(rq);
2335
2336 atomic_long_inc(&cic->ioc->refcount);
2337 cfqd->active_cic = cic;
2338 }
2339
2340 return true;
2341}
2342
2343/*
2344 * Find the cfqq that we need to service and move a request from that to the
2345 * dispatch list
2346 */
2347static int cfq_dispatch_requests(struct request_queue *q, int force)
2348{
2349 struct cfq_data *cfqd = q->elevator->elevator_data;
2350 struct cfq_queue *cfqq;
2351
2352 if (!cfqd->busy_queues)
2353 return 0;
2354
2355 if (unlikely(force))
2356 return cfq_forced_dispatch(cfqd);
2357
2358 cfqq = cfq_select_queue(cfqd);
2359 if (!cfqq)
Jens Axboe8e296752009-10-03 16:26:03 +02002360 return 0;
2361
Jens Axboe2f5cb732009-04-07 08:51:19 +02002362 /*
Jens Axboe0b182d62009-10-06 20:49:37 +02002363 * Dispatch a request from this cfqq, if it is allowed
Jens Axboe2f5cb732009-04-07 08:51:19 +02002364 */
Jens Axboe0b182d62009-10-06 20:49:37 +02002365 if (!cfq_dispatch_request(cfqd, cfqq))
2366 return 0;
2367
Jens Axboe2f5cb732009-04-07 08:51:19 +02002368 cfqq->slice_dispatch++;
Jens Axboeb0291952009-04-07 11:38:31 +02002369 cfq_clear_cfqq_must_dispatch(cfqq);
Jens Axboe2f5cb732009-04-07 08:51:19 +02002370
2371 /*
2372 * expire an async queue immediately if it has used up its slice. idle
2373 * queue always expire after 1 dispatch round.
2374 */
2375 if (cfqd->busy_queues > 1 && ((!cfq_cfqq_sync(cfqq) &&
2376 cfqq->slice_dispatch >= cfq_prio_to_maxrq(cfqd, cfqq)) ||
2377 cfq_class_idle(cfqq))) {
2378 cfqq->slice_end = jiffies + 1;
2379 cfq_slice_expired(cfqd, 0);
2380 }
2381
Shan Weib217a902009-09-01 10:06:42 +02002382 cfq_log_cfqq(cfqd, cfqq, "dispatched a request");
Jens Axboe2f5cb732009-04-07 08:51:19 +02002383 return 1;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002384}
2385
Linus Torvalds1da177e2005-04-16 15:20:36 -07002386/*
Jens Axboe5e705372006-07-13 12:39:25 +02002387 * task holds one reference to the queue, dropped when task exits. each rq
2388 * in-flight on this queue also holds a reference, dropped when rq is freed.
Linus Torvalds1da177e2005-04-16 15:20:36 -07002389 *
Vivek Goyalb1c35762009-12-03 12:59:47 -05002390 * Each cfq queue took a reference on the parent group. Drop it now.
Linus Torvalds1da177e2005-04-16 15:20:36 -07002391 * queue lock must be held here.
2392 */
2393static void cfq_put_queue(struct cfq_queue *cfqq)
2394{
Jens Axboe22e2c502005-06-27 10:55:12 +02002395 struct cfq_data *cfqd = cfqq->cfqd;
Vivek Goyal878eadd2009-12-07 19:37:15 +01002396 struct cfq_group *cfqg, *orig_cfqg;
Jens Axboe22e2c502005-06-27 10:55:12 +02002397
2398 BUG_ON(atomic_read(&cfqq->ref) <= 0);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002399
2400 if (!atomic_dec_and_test(&cfqq->ref))
2401 return;
2402
Jens Axboe7b679132008-05-30 12:23:07 +02002403 cfq_log_cfqq(cfqd, cfqq, "put_queue");
Linus Torvalds1da177e2005-04-16 15:20:36 -07002404 BUG_ON(rb_first(&cfqq->sort_list));
Jens Axboe22e2c502005-06-27 10:55:12 +02002405 BUG_ON(cfqq->allocated[READ] + cfqq->allocated[WRITE]);
Vivek Goyalb1c35762009-12-03 12:59:47 -05002406 cfqg = cfqq->cfqg;
Vivek Goyal878eadd2009-12-07 19:37:15 +01002407 orig_cfqg = cfqq->orig_cfqg;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002408
Jens Axboe28f95cbc2007-01-19 12:09:53 +11002409 if (unlikely(cfqd->active_queue == cfqq)) {
Jens Axboe6084cdd2007-04-23 08:25:00 +02002410 __cfq_slice_expired(cfqd, cfqq, 0);
Jens Axboe23e018a2009-10-05 08:52:35 +02002411 cfq_schedule_dispatch(cfqd);
Jens Axboe28f95cbc2007-01-19 12:09:53 +11002412 }
Jens Axboe22e2c502005-06-27 10:55:12 +02002413
Vivek Goyalf04a6422009-12-03 12:59:40 -05002414 BUG_ON(cfq_cfqq_on_rr(cfqq));
Linus Torvalds1da177e2005-04-16 15:20:36 -07002415 kmem_cache_free(cfq_pool, cfqq);
Vivek Goyalb1c35762009-12-03 12:59:47 -05002416 cfq_put_cfqg(cfqg);
Vivek Goyal878eadd2009-12-07 19:37:15 +01002417 if (orig_cfqg)
2418 cfq_put_cfqg(orig_cfqg);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002419}
2420
Jens Axboed6de8be2008-05-28 14:46:59 +02002421/*
2422 * Must always be called with the rcu_read_lock() held
2423 */
Jens Axboe07416d22008-05-07 09:17:12 +02002424static void
2425__call_for_each_cic(struct io_context *ioc,
2426 void (*func)(struct io_context *, struct cfq_io_context *))
2427{
2428 struct cfq_io_context *cic;
2429 struct hlist_node *n;
2430
2431 hlist_for_each_entry_rcu(cic, n, &ioc->cic_list, cic_list)
2432 func(ioc, cic);
2433}
2434
Jens Axboe4ac845a2008-01-24 08:44:49 +01002435/*
Fabio Checconi34e6bbf2008-04-02 14:31:02 +02002436 * Call func for each cic attached to this ioc.
Jens Axboe4ac845a2008-01-24 08:44:49 +01002437 */
Fabio Checconi34e6bbf2008-04-02 14:31:02 +02002438static void
Jens Axboe4ac845a2008-01-24 08:44:49 +01002439call_for_each_cic(struct io_context *ioc,
2440 void (*func)(struct io_context *, struct cfq_io_context *))
2441{
Jens Axboe4ac845a2008-01-24 08:44:49 +01002442 rcu_read_lock();
Jens Axboe07416d22008-05-07 09:17:12 +02002443 __call_for_each_cic(ioc, func);
Jens Axboe4ac845a2008-01-24 08:44:49 +01002444 rcu_read_unlock();
Fabio Checconi34e6bbf2008-04-02 14:31:02 +02002445}
Jens Axboe4ac845a2008-01-24 08:44:49 +01002446
Fabio Checconi34e6bbf2008-04-02 14:31:02 +02002447static void cfq_cic_free_rcu(struct rcu_head *head)
2448{
2449 struct cfq_io_context *cic;
2450
2451 cic = container_of(head, struct cfq_io_context, rcu_head);
2452
2453 kmem_cache_free(cfq_ioc_pool, cic);
Tejun Heo245b2e72009-06-24 15:13:48 +09002454 elv_ioc_count_dec(cfq_ioc_count);
Fabio Checconi34e6bbf2008-04-02 14:31:02 +02002455
Jens Axboe9a11b4e2008-05-29 09:32:08 +02002456 if (ioc_gone) {
2457 /*
2458 * CFQ scheduler is exiting, grab exit lock and check
2459 * the pending io context count. If it hits zero,
2460 * complete ioc_gone and set it back to NULL
2461 */
2462 spin_lock(&ioc_gone_lock);
Tejun Heo245b2e72009-06-24 15:13:48 +09002463 if (ioc_gone && !elv_ioc_count_read(cfq_ioc_count)) {
Jens Axboe9a11b4e2008-05-29 09:32:08 +02002464 complete(ioc_gone);
2465 ioc_gone = NULL;
2466 }
2467 spin_unlock(&ioc_gone_lock);
2468 }
Fabio Checconi34e6bbf2008-04-02 14:31:02 +02002469}
2470
2471static void cfq_cic_free(struct cfq_io_context *cic)
2472{
2473 call_rcu(&cic->rcu_head, cfq_cic_free_rcu);
Jens Axboe4ac845a2008-01-24 08:44:49 +01002474}
2475
2476static void cic_free_func(struct io_context *ioc, struct cfq_io_context *cic)
2477{
2478 unsigned long flags;
2479
2480 BUG_ON(!cic->dead_key);
2481
2482 spin_lock_irqsave(&ioc->lock, flags);
2483 radix_tree_delete(&ioc->radix_root, cic->dead_key);
Jens Axboeffc4e752008-02-19 10:02:29 +01002484 hlist_del_rcu(&cic->cic_list);
Jens Axboe4ac845a2008-01-24 08:44:49 +01002485 spin_unlock_irqrestore(&ioc->lock, flags);
2486
Fabio Checconi34e6bbf2008-04-02 14:31:02 +02002487 cfq_cic_free(cic);
Jens Axboe4ac845a2008-01-24 08:44:49 +01002488}
2489
Jens Axboed6de8be2008-05-28 14:46:59 +02002490/*
2491 * Must be called with rcu_read_lock() held or preemption otherwise disabled.
2492 * Only two callers of this - ->dtor() which is called with the rcu_read_lock(),
2493 * and ->trim() which is called with the task lock held
2494 */
Jens Axboee2d74ac2006-03-28 08:59:01 +02002495static void cfq_free_io_context(struct io_context *ioc)
Linus Torvalds1da177e2005-04-16 15:20:36 -07002496{
Jens Axboe4ac845a2008-01-24 08:44:49 +01002497 /*
Fabio Checconi34e6bbf2008-04-02 14:31:02 +02002498 * ioc->refcount is zero here, or we are called from elv_unregister(),
2499 * so no more cic's are allowed to be linked into this ioc. So it
2500 * should be ok to iterate over the known list, we will see all cic's
2501 * since no new ones are added.
Jens Axboe4ac845a2008-01-24 08:44:49 +01002502 */
Jens Axboe07416d22008-05-07 09:17:12 +02002503 __call_for_each_cic(ioc, cic_free_func);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002504}
2505
Jens Axboe89850f72006-07-22 16:48:31 +02002506static void cfq_exit_cfqq(struct cfq_data *cfqd, struct cfq_queue *cfqq)
2507{
Jeff Moyerdf5fe3e2009-10-23 17:14:50 -04002508 struct cfq_queue *__cfqq, *next;
2509
Jens Axboe28f95cbc2007-01-19 12:09:53 +11002510 if (unlikely(cfqq == cfqd->active_queue)) {
Jens Axboe6084cdd2007-04-23 08:25:00 +02002511 __cfq_slice_expired(cfqd, cfqq, 0);
Jens Axboe23e018a2009-10-05 08:52:35 +02002512 cfq_schedule_dispatch(cfqd);
Jens Axboe28f95cbc2007-01-19 12:09:53 +11002513 }
Jens Axboe89850f72006-07-22 16:48:31 +02002514
Jeff Moyerdf5fe3e2009-10-23 17:14:50 -04002515 /*
2516 * If this queue was scheduled to merge with another queue, be
2517 * sure to drop the reference taken on that queue (and others in
2518 * the merge chain). See cfq_setup_merge and cfq_merge_cfqqs.
2519 */
2520 __cfqq = cfqq->new_cfqq;
2521 while (__cfqq) {
2522 if (__cfqq == cfqq) {
2523 WARN(1, "cfqq->new_cfqq loop detected\n");
2524 break;
2525 }
2526 next = __cfqq->new_cfqq;
2527 cfq_put_queue(__cfqq);
2528 __cfqq = next;
2529 }
2530
Jens Axboe89850f72006-07-22 16:48:31 +02002531 cfq_put_queue(cfqq);
2532}
2533
2534static void __cfq_exit_single_io_context(struct cfq_data *cfqd,
2535 struct cfq_io_context *cic)
2536{
Fabio Checconi4faa3c82008-04-10 08:28:01 +02002537 struct io_context *ioc = cic->ioc;
2538
Jens Axboefc463792006-08-29 09:05:44 +02002539 list_del_init(&cic->queue_list);
Jens Axboe4ac845a2008-01-24 08:44:49 +01002540
2541 /*
2542 * Make sure key == NULL is seen for dead queues
2543 */
Jens Axboefc463792006-08-29 09:05:44 +02002544 smp_wmb();
Jens Axboe4ac845a2008-01-24 08:44:49 +01002545 cic->dead_key = (unsigned long) cic->key;
Jens Axboefc463792006-08-29 09:05:44 +02002546 cic->key = NULL;
2547
Fabio Checconi4faa3c82008-04-10 08:28:01 +02002548 if (ioc->ioc_data == cic)
2549 rcu_assign_pointer(ioc->ioc_data, NULL);
2550
Jens Axboeff6657c2009-04-08 10:58:57 +02002551 if (cic->cfqq[BLK_RW_ASYNC]) {
2552 cfq_exit_cfqq(cfqd, cic->cfqq[BLK_RW_ASYNC]);
2553 cic->cfqq[BLK_RW_ASYNC] = NULL;
Jens Axboe89850f72006-07-22 16:48:31 +02002554 }
2555
Jens Axboeff6657c2009-04-08 10:58:57 +02002556 if (cic->cfqq[BLK_RW_SYNC]) {
2557 cfq_exit_cfqq(cfqd, cic->cfqq[BLK_RW_SYNC]);
2558 cic->cfqq[BLK_RW_SYNC] = NULL;
Jens Axboe89850f72006-07-22 16:48:31 +02002559 }
Jens Axboe89850f72006-07-22 16:48:31 +02002560}
2561
Jens Axboe4ac845a2008-01-24 08:44:49 +01002562static void cfq_exit_single_io_context(struct io_context *ioc,
2563 struct cfq_io_context *cic)
Jens Axboe22e2c502005-06-27 10:55:12 +02002564{
Al Viro478a82b2006-03-18 13:25:24 -05002565 struct cfq_data *cfqd = cic->key;
Jens Axboe22e2c502005-06-27 10:55:12 +02002566
Jens Axboe89850f72006-07-22 16:48:31 +02002567 if (cfqd) {
Jens Axboe165125e2007-07-24 09:28:11 +02002568 struct request_queue *q = cfqd->queue;
Jens Axboe4ac845a2008-01-24 08:44:49 +01002569 unsigned long flags;
Jens Axboe22e2c502005-06-27 10:55:12 +02002570
Jens Axboe4ac845a2008-01-24 08:44:49 +01002571 spin_lock_irqsave(q->queue_lock, flags);
Jens Axboe62c1fe92008-12-15 21:19:25 +01002572
2573 /*
2574 * Ensure we get a fresh copy of the ->key to prevent
2575 * race between exiting task and queue
2576 */
2577 smp_read_barrier_depends();
2578 if (cic->key)
2579 __cfq_exit_single_io_context(cfqd, cic);
2580
Jens Axboe4ac845a2008-01-24 08:44:49 +01002581 spin_unlock_irqrestore(q->queue_lock, flags);
Al Viro12a05732006-03-18 13:38:01 -05002582 }
Jens Axboe22e2c502005-06-27 10:55:12 +02002583}
2584
Jens Axboe498d3aa2007-04-26 12:54:48 +02002585/*
2586 * The process that ioc belongs to has exited, we need to clean up
2587 * and put the internal structures we have that belongs to that process.
2588 */
Jens Axboee2d74ac2006-03-28 08:59:01 +02002589static void cfq_exit_io_context(struct io_context *ioc)
Linus Torvalds1da177e2005-04-16 15:20:36 -07002590{
Jens Axboe4ac845a2008-01-24 08:44:49 +01002591 call_for_each_cic(ioc, cfq_exit_single_io_context);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002592}
2593
Jens Axboe22e2c502005-06-27 10:55:12 +02002594static struct cfq_io_context *
Al Viro8267e262005-10-21 03:20:53 -04002595cfq_alloc_io_context(struct cfq_data *cfqd, gfp_t gfp_mask)
Linus Torvalds1da177e2005-04-16 15:20:36 -07002596{
Jens Axboeb5deef92006-07-19 23:39:40 +02002597 struct cfq_io_context *cic;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002598
Christoph Lameter94f60302007-07-17 04:03:29 -07002599 cic = kmem_cache_alloc_node(cfq_ioc_pool, gfp_mask | __GFP_ZERO,
2600 cfqd->queue->node);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002601 if (cic) {
Jens Axboe22e2c502005-06-27 10:55:12 +02002602 cic->last_end_request = jiffies;
Jens Axboe553698f2006-06-14 19:11:57 +02002603 INIT_LIST_HEAD(&cic->queue_list);
Jens Axboeffc4e752008-02-19 10:02:29 +01002604 INIT_HLIST_NODE(&cic->cic_list);
Jens Axboe22e2c502005-06-27 10:55:12 +02002605 cic->dtor = cfq_free_io_context;
2606 cic->exit = cfq_exit_io_context;
Tejun Heo245b2e72009-06-24 15:13:48 +09002607 elv_ioc_count_inc(cfq_ioc_count);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002608 }
2609
2610 return cic;
2611}
2612
Jens Axboefd0928d2008-01-24 08:52:45 +01002613static void cfq_init_prio_data(struct cfq_queue *cfqq, struct io_context *ioc)
Jens Axboe22e2c502005-06-27 10:55:12 +02002614{
2615 struct task_struct *tsk = current;
2616 int ioprio_class;
2617
Jens Axboe3b181522005-06-27 10:56:24 +02002618 if (!cfq_cfqq_prio_changed(cfqq))
Jens Axboe22e2c502005-06-27 10:55:12 +02002619 return;
2620
Jens Axboefd0928d2008-01-24 08:52:45 +01002621 ioprio_class = IOPRIO_PRIO_CLASS(ioc->ioprio);
Jens Axboe22e2c502005-06-27 10:55:12 +02002622 switch (ioprio_class) {
Jens Axboefe094d92008-01-31 13:08:54 +01002623 default:
2624 printk(KERN_ERR "cfq: bad prio %x\n", ioprio_class);
2625 case IOPRIO_CLASS_NONE:
2626 /*
Jens Axboe6d63c272008-05-07 09:51:23 +02002627 * no prio set, inherit CPU scheduling settings
Jens Axboefe094d92008-01-31 13:08:54 +01002628 */
2629 cfqq->ioprio = task_nice_ioprio(tsk);
Jens Axboe6d63c272008-05-07 09:51:23 +02002630 cfqq->ioprio_class = task_nice_ioclass(tsk);
Jens Axboefe094d92008-01-31 13:08:54 +01002631 break;
2632 case IOPRIO_CLASS_RT:
2633 cfqq->ioprio = task_ioprio(ioc);
2634 cfqq->ioprio_class = IOPRIO_CLASS_RT;
2635 break;
2636 case IOPRIO_CLASS_BE:
2637 cfqq->ioprio = task_ioprio(ioc);
2638 cfqq->ioprio_class = IOPRIO_CLASS_BE;
2639 break;
2640 case IOPRIO_CLASS_IDLE:
2641 cfqq->ioprio_class = IOPRIO_CLASS_IDLE;
2642 cfqq->ioprio = 7;
2643 cfq_clear_cfqq_idle_window(cfqq);
2644 break;
Jens Axboe22e2c502005-06-27 10:55:12 +02002645 }
2646
2647 /*
2648 * keep track of original prio settings in case we have to temporarily
2649 * elevate the priority of this queue
2650 */
2651 cfqq->org_ioprio = cfqq->ioprio;
2652 cfqq->org_ioprio_class = cfqq->ioprio_class;
Jens Axboe3b181522005-06-27 10:56:24 +02002653 cfq_clear_cfqq_prio_changed(cfqq);
Jens Axboe22e2c502005-06-27 10:55:12 +02002654}
2655
Jens Axboefebffd62008-01-28 13:19:43 +01002656static void changed_ioprio(struct io_context *ioc, struct cfq_io_context *cic)
Jens Axboe22e2c502005-06-27 10:55:12 +02002657{
Al Viro478a82b2006-03-18 13:25:24 -05002658 struct cfq_data *cfqd = cic->key;
2659 struct cfq_queue *cfqq;
Jens Axboec1b707d2006-10-30 19:54:23 +01002660 unsigned long flags;
Jens Axboe35e60772006-06-14 09:10:45 +02002661
Jens Axboecaaa5f92006-06-16 11:23:00 +02002662 if (unlikely(!cfqd))
2663 return;
2664
Jens Axboec1b707d2006-10-30 19:54:23 +01002665 spin_lock_irqsave(cfqd->queue->queue_lock, flags);
Jens Axboecaaa5f92006-06-16 11:23:00 +02002666
Jens Axboeff6657c2009-04-08 10:58:57 +02002667 cfqq = cic->cfqq[BLK_RW_ASYNC];
Jens Axboecaaa5f92006-06-16 11:23:00 +02002668 if (cfqq) {
2669 struct cfq_queue *new_cfqq;
Jens Axboeff6657c2009-04-08 10:58:57 +02002670 new_cfqq = cfq_get_queue(cfqd, BLK_RW_ASYNC, cic->ioc,
2671 GFP_ATOMIC);
Jens Axboecaaa5f92006-06-16 11:23:00 +02002672 if (new_cfqq) {
Jens Axboeff6657c2009-04-08 10:58:57 +02002673 cic->cfqq[BLK_RW_ASYNC] = new_cfqq;
Jens Axboecaaa5f92006-06-16 11:23:00 +02002674 cfq_put_queue(cfqq);
2675 }
Jens Axboe22e2c502005-06-27 10:55:12 +02002676 }
Jens Axboecaaa5f92006-06-16 11:23:00 +02002677
Jens Axboeff6657c2009-04-08 10:58:57 +02002678 cfqq = cic->cfqq[BLK_RW_SYNC];
Jens Axboecaaa5f92006-06-16 11:23:00 +02002679 if (cfqq)
2680 cfq_mark_cfqq_prio_changed(cfqq);
2681
Jens Axboec1b707d2006-10-30 19:54:23 +01002682 spin_unlock_irqrestore(cfqd->queue->queue_lock, flags);
Jens Axboe22e2c502005-06-27 10:55:12 +02002683}
2684
Jens Axboefc463792006-08-29 09:05:44 +02002685static void cfq_ioc_set_ioprio(struct io_context *ioc)
Linus Torvalds1da177e2005-04-16 15:20:36 -07002686{
Jens Axboe4ac845a2008-01-24 08:44:49 +01002687 call_for_each_cic(ioc, changed_ioprio);
Jens Axboefc463792006-08-29 09:05:44 +02002688 ioc->ioprio_changed = 0;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002689}
2690
Jens Axboed5036d72009-06-26 10:44:34 +02002691static void cfq_init_cfqq(struct cfq_data *cfqd, struct cfq_queue *cfqq,
Jens Axboea6151c32009-10-07 20:02:57 +02002692 pid_t pid, bool is_sync)
Jens Axboed5036d72009-06-26 10:44:34 +02002693{
2694 RB_CLEAR_NODE(&cfqq->rb_node);
2695 RB_CLEAR_NODE(&cfqq->p_node);
2696 INIT_LIST_HEAD(&cfqq->fifo);
2697
2698 atomic_set(&cfqq->ref, 0);
2699 cfqq->cfqd = cfqd;
2700
2701 cfq_mark_cfqq_prio_changed(cfqq);
2702
2703 if (is_sync) {
2704 if (!cfq_class_idle(cfqq))
2705 cfq_mark_cfqq_idle_window(cfqq);
2706 cfq_mark_cfqq_sync(cfqq);
2707 }
2708 cfqq->pid = pid;
2709}
2710
Vivek Goyal24610332009-12-03 12:59:51 -05002711#ifdef CONFIG_CFQ_GROUP_IOSCHED
2712static void changed_cgroup(struct io_context *ioc, struct cfq_io_context *cic)
2713{
2714 struct cfq_queue *sync_cfqq = cic_to_cfqq(cic, 1);
2715 struct cfq_data *cfqd = cic->key;
2716 unsigned long flags;
2717 struct request_queue *q;
2718
2719 if (unlikely(!cfqd))
2720 return;
2721
2722 q = cfqd->queue;
2723
2724 spin_lock_irqsave(q->queue_lock, flags);
2725
2726 if (sync_cfqq) {
2727 /*
2728 * Drop reference to sync queue. A new sync queue will be
2729 * assigned in new group upon arrival of a fresh request.
2730 */
2731 cfq_log_cfqq(cfqd, sync_cfqq, "changed cgroup");
2732 cic_set_cfqq(cic, NULL, 1);
2733 cfq_put_queue(sync_cfqq);
2734 }
2735
2736 spin_unlock_irqrestore(q->queue_lock, flags);
2737}
2738
2739static void cfq_ioc_set_cgroup(struct io_context *ioc)
2740{
2741 call_for_each_cic(ioc, changed_cgroup);
2742 ioc->cgroup_changed = 0;
2743}
2744#endif /* CONFIG_CFQ_GROUP_IOSCHED */
2745
Linus Torvalds1da177e2005-04-16 15:20:36 -07002746static struct cfq_queue *
Jens Axboea6151c32009-10-07 20:02:57 +02002747cfq_find_alloc_queue(struct cfq_data *cfqd, bool is_sync,
Jens Axboefd0928d2008-01-24 08:52:45 +01002748 struct io_context *ioc, gfp_t gfp_mask)
Linus Torvalds1da177e2005-04-16 15:20:36 -07002749{
Linus Torvalds1da177e2005-04-16 15:20:36 -07002750 struct cfq_queue *cfqq, *new_cfqq = NULL;
Vasily Tarasov91fac312007-04-25 12:29:51 +02002751 struct cfq_io_context *cic;
Vivek Goyalcdb16e82009-12-03 12:59:38 -05002752 struct cfq_group *cfqg;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002753
2754retry:
Vivek Goyalcdb16e82009-12-03 12:59:38 -05002755 cfqg = cfq_get_cfqg(cfqd, 1);
Jens Axboe4ac845a2008-01-24 08:44:49 +01002756 cic = cfq_cic_lookup(cfqd, ioc);
Vasily Tarasov91fac312007-04-25 12:29:51 +02002757 /* cic always exists here */
2758 cfqq = cic_to_cfqq(cic, is_sync);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002759
Jens Axboe6118b702009-06-30 09:34:12 +02002760 /*
2761 * Always try a new alloc if we fell back to the OOM cfqq
2762 * originally, since it should just be a temporary situation.
2763 */
2764 if (!cfqq || cfqq == &cfqd->oom_cfqq) {
2765 cfqq = NULL;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002766 if (new_cfqq) {
2767 cfqq = new_cfqq;
2768 new_cfqq = NULL;
Jens Axboe22e2c502005-06-27 10:55:12 +02002769 } else if (gfp_mask & __GFP_WAIT) {
Linus Torvalds1da177e2005-04-16 15:20:36 -07002770 spin_unlock_irq(cfqd->queue->queue_lock);
Christoph Lameter94f60302007-07-17 04:03:29 -07002771 new_cfqq = kmem_cache_alloc_node(cfq_pool,
Jens Axboe6118b702009-06-30 09:34:12 +02002772 gfp_mask | __GFP_ZERO,
Christoph Lameter94f60302007-07-17 04:03:29 -07002773 cfqd->queue->node);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002774 spin_lock_irq(cfqd->queue->queue_lock);
Jens Axboe6118b702009-06-30 09:34:12 +02002775 if (new_cfqq)
2776 goto retry;
Jens Axboe22e2c502005-06-27 10:55:12 +02002777 } else {
Christoph Lameter94f60302007-07-17 04:03:29 -07002778 cfqq = kmem_cache_alloc_node(cfq_pool,
2779 gfp_mask | __GFP_ZERO,
2780 cfqd->queue->node);
Kiyoshi Ueda db3b5842005-06-17 16:15:10 +02002781 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07002782
Jens Axboe6118b702009-06-30 09:34:12 +02002783 if (cfqq) {
2784 cfq_init_cfqq(cfqd, cfqq, current->pid, is_sync);
2785 cfq_init_prio_data(cfqq, ioc);
Vivek Goyalcdb16e82009-12-03 12:59:38 -05002786 cfq_link_cfqq_cfqg(cfqq, cfqg);
Jens Axboe6118b702009-06-30 09:34:12 +02002787 cfq_log_cfqq(cfqd, cfqq, "alloced");
2788 } else
2789 cfqq = &cfqd->oom_cfqq;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002790 }
2791
2792 if (new_cfqq)
2793 kmem_cache_free(cfq_pool, new_cfqq);
2794
Linus Torvalds1da177e2005-04-16 15:20:36 -07002795 return cfqq;
2796}
2797
Vasily Tarasovc2dea2d2007-07-20 10:06:38 +02002798static struct cfq_queue **
2799cfq_async_queue_prio(struct cfq_data *cfqd, int ioprio_class, int ioprio)
2800{
Jens Axboefe094d92008-01-31 13:08:54 +01002801 switch (ioprio_class) {
Vasily Tarasovc2dea2d2007-07-20 10:06:38 +02002802 case IOPRIO_CLASS_RT:
2803 return &cfqd->async_cfqq[0][ioprio];
2804 case IOPRIO_CLASS_BE:
2805 return &cfqd->async_cfqq[1][ioprio];
2806 case IOPRIO_CLASS_IDLE:
2807 return &cfqd->async_idle_cfqq;
2808 default:
2809 BUG();
2810 }
2811}
2812
Jens Axboe15c31be2007-07-10 13:43:25 +02002813static struct cfq_queue *
Jens Axboea6151c32009-10-07 20:02:57 +02002814cfq_get_queue(struct cfq_data *cfqd, bool is_sync, struct io_context *ioc,
Jens Axboe15c31be2007-07-10 13:43:25 +02002815 gfp_t gfp_mask)
2816{
Jens Axboefd0928d2008-01-24 08:52:45 +01002817 const int ioprio = task_ioprio(ioc);
2818 const int ioprio_class = task_ioprio_class(ioc);
Vasily Tarasovc2dea2d2007-07-20 10:06:38 +02002819 struct cfq_queue **async_cfqq = NULL;
Jens Axboe15c31be2007-07-10 13:43:25 +02002820 struct cfq_queue *cfqq = NULL;
2821
Vasily Tarasovc2dea2d2007-07-20 10:06:38 +02002822 if (!is_sync) {
2823 async_cfqq = cfq_async_queue_prio(cfqd, ioprio_class, ioprio);
2824 cfqq = *async_cfqq;
2825 }
2826
Jens Axboe6118b702009-06-30 09:34:12 +02002827 if (!cfqq)
Jens Axboefd0928d2008-01-24 08:52:45 +01002828 cfqq = cfq_find_alloc_queue(cfqd, is_sync, ioc, gfp_mask);
Jens Axboe15c31be2007-07-10 13:43:25 +02002829
2830 /*
2831 * pin the queue now that it's allocated, scheduler exit will prune it
2832 */
Vasily Tarasovc2dea2d2007-07-20 10:06:38 +02002833 if (!is_sync && !(*async_cfqq)) {
Jens Axboe15c31be2007-07-10 13:43:25 +02002834 atomic_inc(&cfqq->ref);
Vasily Tarasovc2dea2d2007-07-20 10:06:38 +02002835 *async_cfqq = cfqq;
Jens Axboe15c31be2007-07-10 13:43:25 +02002836 }
2837
2838 atomic_inc(&cfqq->ref);
2839 return cfqq;
2840}
2841
Jens Axboe498d3aa2007-04-26 12:54:48 +02002842/*
2843 * We drop cfq io contexts lazily, so we may find a dead one.
2844 */
OGAWA Hirofumidbecf3a2006-04-18 09:45:18 +02002845static void
Jens Axboe4ac845a2008-01-24 08:44:49 +01002846cfq_drop_dead_cic(struct cfq_data *cfqd, struct io_context *ioc,
2847 struct cfq_io_context *cic)
OGAWA Hirofumidbecf3a2006-04-18 09:45:18 +02002848{
Jens Axboe4ac845a2008-01-24 08:44:49 +01002849 unsigned long flags;
2850
Jens Axboefc463792006-08-29 09:05:44 +02002851 WARN_ON(!list_empty(&cic->queue_list));
Jens Axboe597bc482007-04-24 21:23:53 +02002852
Jens Axboe4ac845a2008-01-24 08:44:49 +01002853 spin_lock_irqsave(&ioc->lock, flags);
Jens Axboe597bc482007-04-24 21:23:53 +02002854
Fabio Checconi4faa3c82008-04-10 08:28:01 +02002855 BUG_ON(ioc->ioc_data == cic);
Jens Axboe4ac845a2008-01-24 08:44:49 +01002856
2857 radix_tree_delete(&ioc->radix_root, (unsigned long) cfqd);
Jens Axboeffc4e752008-02-19 10:02:29 +01002858 hlist_del_rcu(&cic->cic_list);
Jens Axboe4ac845a2008-01-24 08:44:49 +01002859 spin_unlock_irqrestore(&ioc->lock, flags);
2860
2861 cfq_cic_free(cic);
OGAWA Hirofumidbecf3a2006-04-18 09:45:18 +02002862}
2863
Jens Axboee2d74ac2006-03-28 08:59:01 +02002864static struct cfq_io_context *
Jens Axboe4ac845a2008-01-24 08:44:49 +01002865cfq_cic_lookup(struct cfq_data *cfqd, struct io_context *ioc)
Jens Axboee2d74ac2006-03-28 08:59:01 +02002866{
Jens Axboee2d74ac2006-03-28 08:59:01 +02002867 struct cfq_io_context *cic;
Jens Axboed6de8be2008-05-28 14:46:59 +02002868 unsigned long flags;
Jens Axboe4ac845a2008-01-24 08:44:49 +01002869 void *k;
Jens Axboee2d74ac2006-03-28 08:59:01 +02002870
Vasily Tarasov91fac312007-04-25 12:29:51 +02002871 if (unlikely(!ioc))
2872 return NULL;
2873
Jens Axboed6de8be2008-05-28 14:46:59 +02002874 rcu_read_lock();
2875
Jens Axboe597bc482007-04-24 21:23:53 +02002876 /*
2877 * we maintain a last-hit cache, to avoid browsing over the tree
2878 */
Jens Axboe4ac845a2008-01-24 08:44:49 +01002879 cic = rcu_dereference(ioc->ioc_data);
Jens Axboed6de8be2008-05-28 14:46:59 +02002880 if (cic && cic->key == cfqd) {
2881 rcu_read_unlock();
Jens Axboe597bc482007-04-24 21:23:53 +02002882 return cic;
Jens Axboed6de8be2008-05-28 14:46:59 +02002883 }
Jens Axboe597bc482007-04-24 21:23:53 +02002884
Jens Axboe4ac845a2008-01-24 08:44:49 +01002885 do {
Jens Axboe4ac845a2008-01-24 08:44:49 +01002886 cic = radix_tree_lookup(&ioc->radix_root, (unsigned long) cfqd);
2887 rcu_read_unlock();
2888 if (!cic)
2889 break;
OGAWA Hirofumibe3b0752006-04-18 19:18:31 +02002890 /* ->key must be copied to avoid race with cfq_exit_queue() */
2891 k = cic->key;
2892 if (unlikely(!k)) {
Jens Axboe4ac845a2008-01-24 08:44:49 +01002893 cfq_drop_dead_cic(cfqd, ioc, cic);
Jens Axboed6de8be2008-05-28 14:46:59 +02002894 rcu_read_lock();
Jens Axboe4ac845a2008-01-24 08:44:49 +01002895 continue;
OGAWA Hirofumidbecf3a2006-04-18 09:45:18 +02002896 }
Jens Axboee2d74ac2006-03-28 08:59:01 +02002897
Jens Axboed6de8be2008-05-28 14:46:59 +02002898 spin_lock_irqsave(&ioc->lock, flags);
Jens Axboe4ac845a2008-01-24 08:44:49 +01002899 rcu_assign_pointer(ioc->ioc_data, cic);
Jens Axboed6de8be2008-05-28 14:46:59 +02002900 spin_unlock_irqrestore(&ioc->lock, flags);
Jens Axboe4ac845a2008-01-24 08:44:49 +01002901 break;
2902 } while (1);
Jens Axboee2d74ac2006-03-28 08:59:01 +02002903
Jens Axboe4ac845a2008-01-24 08:44:49 +01002904 return cic;
Jens Axboee2d74ac2006-03-28 08:59:01 +02002905}
2906
Jens Axboe4ac845a2008-01-24 08:44:49 +01002907/*
2908 * Add cic into ioc, using cfqd as the search key. This enables us to lookup
2909 * the process specific cfq io context when entered from the block layer.
2910 * Also adds the cic to a per-cfqd list, used when this queue is removed.
2911 */
Jens Axboefebffd62008-01-28 13:19:43 +01002912static int cfq_cic_link(struct cfq_data *cfqd, struct io_context *ioc,
2913 struct cfq_io_context *cic, gfp_t gfp_mask)
Jens Axboee2d74ac2006-03-28 08:59:01 +02002914{
Jens Axboe0261d682006-10-30 19:07:48 +01002915 unsigned long flags;
Jens Axboe4ac845a2008-01-24 08:44:49 +01002916 int ret;
Jens Axboee2d74ac2006-03-28 08:59:01 +02002917
Jens Axboe4ac845a2008-01-24 08:44:49 +01002918 ret = radix_tree_preload(gfp_mask);
2919 if (!ret) {
2920 cic->ioc = ioc;
2921 cic->key = cfqd;
Jens Axboee2d74ac2006-03-28 08:59:01 +02002922
Jens Axboe4ac845a2008-01-24 08:44:49 +01002923 spin_lock_irqsave(&ioc->lock, flags);
2924 ret = radix_tree_insert(&ioc->radix_root,
2925 (unsigned long) cfqd, cic);
Jens Axboeffc4e752008-02-19 10:02:29 +01002926 if (!ret)
2927 hlist_add_head_rcu(&cic->cic_list, &ioc->cic_list);
Jens Axboe4ac845a2008-01-24 08:44:49 +01002928 spin_unlock_irqrestore(&ioc->lock, flags);
2929
2930 radix_tree_preload_end();
2931
2932 if (!ret) {
2933 spin_lock_irqsave(cfqd->queue->queue_lock, flags);
2934 list_add(&cic->queue_list, &cfqd->cic_list);
2935 spin_unlock_irqrestore(cfqd->queue->queue_lock, flags);
OGAWA Hirofumidbecf3a2006-04-18 09:45:18 +02002936 }
Jens Axboee2d74ac2006-03-28 08:59:01 +02002937 }
2938
Jens Axboe4ac845a2008-01-24 08:44:49 +01002939 if (ret)
2940 printk(KERN_ERR "cfq: cic link failed!\n");
Jens Axboefc463792006-08-29 09:05:44 +02002941
Jens Axboe4ac845a2008-01-24 08:44:49 +01002942 return ret;
Jens Axboee2d74ac2006-03-28 08:59:01 +02002943}
2944
Jens Axboe22e2c502005-06-27 10:55:12 +02002945/*
2946 * Setup general io context and cfq io context. There can be several cfq
2947 * io contexts per general io context, if this process is doing io to more
Jens Axboee2d74ac2006-03-28 08:59:01 +02002948 * than one device managed by cfq.
Jens Axboe22e2c502005-06-27 10:55:12 +02002949 */
2950static struct cfq_io_context *
Jens Axboee2d74ac2006-03-28 08:59:01 +02002951cfq_get_io_context(struct cfq_data *cfqd, gfp_t gfp_mask)
Linus Torvalds1da177e2005-04-16 15:20:36 -07002952{
Jens Axboe22e2c502005-06-27 10:55:12 +02002953 struct io_context *ioc = NULL;
2954 struct cfq_io_context *cic;
2955
2956 might_sleep_if(gfp_mask & __GFP_WAIT);
2957
Jens Axboeb5deef92006-07-19 23:39:40 +02002958 ioc = get_io_context(gfp_mask, cfqd->queue->node);
Jens Axboe22e2c502005-06-27 10:55:12 +02002959 if (!ioc)
2960 return NULL;
2961
Jens Axboe4ac845a2008-01-24 08:44:49 +01002962 cic = cfq_cic_lookup(cfqd, ioc);
Jens Axboee2d74ac2006-03-28 08:59:01 +02002963 if (cic)
2964 goto out;
Jens Axboe22e2c502005-06-27 10:55:12 +02002965
Jens Axboee2d74ac2006-03-28 08:59:01 +02002966 cic = cfq_alloc_io_context(cfqd, gfp_mask);
2967 if (cic == NULL)
2968 goto err;
Jens Axboe22e2c502005-06-27 10:55:12 +02002969
Jens Axboe4ac845a2008-01-24 08:44:49 +01002970 if (cfq_cic_link(cfqd, ioc, cic, gfp_mask))
2971 goto err_free;
2972
Jens Axboe22e2c502005-06-27 10:55:12 +02002973out:
Jens Axboefc463792006-08-29 09:05:44 +02002974 smp_read_barrier_depends();
2975 if (unlikely(ioc->ioprio_changed))
2976 cfq_ioc_set_ioprio(ioc);
2977
Vivek Goyal24610332009-12-03 12:59:51 -05002978#ifdef CONFIG_CFQ_GROUP_IOSCHED
2979 if (unlikely(ioc->cgroup_changed))
2980 cfq_ioc_set_cgroup(ioc);
2981#endif
Jens Axboe22e2c502005-06-27 10:55:12 +02002982 return cic;
Jens Axboe4ac845a2008-01-24 08:44:49 +01002983err_free:
2984 cfq_cic_free(cic);
Jens Axboe22e2c502005-06-27 10:55:12 +02002985err:
2986 put_io_context(ioc);
2987 return NULL;
2988}
2989
2990static void
2991cfq_update_io_thinktime(struct cfq_data *cfqd, struct cfq_io_context *cic)
2992{
Jens Axboeaaf12282007-01-19 11:30:16 +11002993 unsigned long elapsed = jiffies - cic->last_end_request;
2994 unsigned long ttime = min(elapsed, 2UL * cfqd->cfq_slice_idle);
Jens Axboe22e2c502005-06-27 10:55:12 +02002995
2996 cic->ttime_samples = (7*cic->ttime_samples + 256) / 8;
2997 cic->ttime_total = (7*cic->ttime_total + 256*ttime) / 8;
2998 cic->ttime_mean = (cic->ttime_total + 128) / cic->ttime_samples;
2999}
3000
Jens Axboe206dc692006-03-28 13:03:44 +02003001static void
Jeff Moyerb2c18e12009-10-23 17:14:49 -04003002cfq_update_io_seektime(struct cfq_data *cfqd, struct cfq_queue *cfqq,
Jens Axboe6d048f52007-04-25 12:44:27 +02003003 struct request *rq)
Jens Axboe206dc692006-03-28 13:03:44 +02003004{
Corrado Zoccolo3dde36d2010-02-27 19:45:39 +01003005 sector_t sdist = 0;
Corrado Zoccolo41647e72010-02-27 19:45:40 +01003006 sector_t n_sec = blk_rq_sectors(rq);
Corrado Zoccolo3dde36d2010-02-27 19:45:39 +01003007 if (cfqq->last_request_pos) {
3008 if (cfqq->last_request_pos < blk_rq_pos(rq))
3009 sdist = blk_rq_pos(rq) - cfqq->last_request_pos;
3010 else
3011 sdist = cfqq->last_request_pos - blk_rq_pos(rq);
3012 }
Jens Axboe206dc692006-03-28 13:03:44 +02003013
Corrado Zoccolo3dde36d2010-02-27 19:45:39 +01003014 cfqq->seek_history <<= 1;
Corrado Zoccolo41647e72010-02-27 19:45:40 +01003015 if (blk_queue_nonrot(cfqd->queue))
3016 cfqq->seek_history |= (n_sec < CFQQ_SECT_THR_NONROT);
3017 else
3018 cfqq->seek_history |= (sdist > CFQQ_SEEK_THR);
Jens Axboe206dc692006-03-28 13:03:44 +02003019}
Jens Axboe22e2c502005-06-27 10:55:12 +02003020
3021/*
3022 * Disable idle window if the process thinks too long or seeks so much that
3023 * it doesn't matter
3024 */
3025static void
3026cfq_update_idle_window(struct cfq_data *cfqd, struct cfq_queue *cfqq,
3027 struct cfq_io_context *cic)
3028{
Jens Axboe7b679132008-05-30 12:23:07 +02003029 int old_idle, enable_idle;
Jens Axboe1be92f22007-04-19 14:32:26 +02003030
Jens Axboe08717142008-01-28 11:38:15 +01003031 /*
3032 * Don't idle for async or idle io prio class
3033 */
3034 if (!cfq_cfqq_sync(cfqq) || cfq_class_idle(cfqq))
Jens Axboe1be92f22007-04-19 14:32:26 +02003035 return;
3036
Jens Axboec265a7f2008-06-26 13:49:33 +02003037 enable_idle = old_idle = cfq_cfqq_idle_window(cfqq);
Jens Axboe22e2c502005-06-27 10:55:12 +02003038
Corrado Zoccolo76280af2009-11-26 10:02:58 +01003039 if (cfqq->queued[0] + cfqq->queued[1] >= 4)
3040 cfq_mark_cfqq_deep(cfqq);
3041
Nikanth Karthikesan66dac982007-11-27 12:47:04 +01003042 if (!atomic_read(&cic->ioc->nr_tasks) || !cfqd->cfq_slice_idle ||
Corrado Zoccolo3dde36d2010-02-27 19:45:39 +01003043 (!cfq_cfqq_deep(cfqq) && CFQQ_SEEKY(cfqq)))
Jens Axboe22e2c502005-06-27 10:55:12 +02003044 enable_idle = 0;
3045 else if (sample_valid(cic->ttime_samples)) {
Corrado Zoccolo718eee02009-10-26 22:45:29 +01003046 if (cic->ttime_mean > cfqd->cfq_slice_idle)
Jens Axboe22e2c502005-06-27 10:55:12 +02003047 enable_idle = 0;
3048 else
3049 enable_idle = 1;
3050 }
3051
Jens Axboe7b679132008-05-30 12:23:07 +02003052 if (old_idle != enable_idle) {
3053 cfq_log_cfqq(cfqd, cfqq, "idle=%d", enable_idle);
3054 if (enable_idle)
3055 cfq_mark_cfqq_idle_window(cfqq);
3056 else
3057 cfq_clear_cfqq_idle_window(cfqq);
3058 }
Jens Axboe22e2c502005-06-27 10:55:12 +02003059}
3060
Jens Axboe22e2c502005-06-27 10:55:12 +02003061/*
3062 * Check if new_cfqq should preempt the currently active queue. Return 0 for
3063 * no or if we aren't sure, a 1 will cause a preempt.
3064 */
Jens Axboea6151c32009-10-07 20:02:57 +02003065static bool
Jens Axboe22e2c502005-06-27 10:55:12 +02003066cfq_should_preempt(struct cfq_data *cfqd, struct cfq_queue *new_cfqq,
Jens Axboe5e705372006-07-13 12:39:25 +02003067 struct request *rq)
Jens Axboe22e2c502005-06-27 10:55:12 +02003068{
Jens Axboe6d048f52007-04-25 12:44:27 +02003069 struct cfq_queue *cfqq;
Jens Axboe22e2c502005-06-27 10:55:12 +02003070
Jens Axboe6d048f52007-04-25 12:44:27 +02003071 cfqq = cfqd->active_queue;
3072 if (!cfqq)
Jens Axboea6151c32009-10-07 20:02:57 +02003073 return false;
Jens Axboe22e2c502005-06-27 10:55:12 +02003074
Jens Axboe6d048f52007-04-25 12:44:27 +02003075 if (cfq_class_idle(new_cfqq))
Jens Axboea6151c32009-10-07 20:02:57 +02003076 return false;
Jens Axboe22e2c502005-06-27 10:55:12 +02003077
3078 if (cfq_class_idle(cfqq))
Jens Axboea6151c32009-10-07 20:02:57 +02003079 return true;
Jens Axboe1e3335d2007-02-14 19:59:49 +01003080
Jens Axboe22e2c502005-06-27 10:55:12 +02003081 /*
Divyesh Shah875feb62010-01-06 18:58:20 -08003082 * Don't allow a non-RT request to preempt an ongoing RT cfqq timeslice.
3083 */
3084 if (cfq_class_rt(cfqq) && !cfq_class_rt(new_cfqq))
3085 return false;
3086
3087 /*
Jens Axboe374f84a2006-07-23 01:42:19 +02003088 * if the new request is sync, but the currently running queue is
3089 * not, let the sync request have priority.
3090 */
Jens Axboe5e705372006-07-13 12:39:25 +02003091 if (rq_is_sync(rq) && !cfq_cfqq_sync(cfqq))
Jens Axboea6151c32009-10-07 20:02:57 +02003092 return true;
Jens Axboe1e3335d2007-02-14 19:59:49 +01003093
Vivek Goyal8682e1f2009-12-03 12:59:50 -05003094 if (new_cfqq->cfqg != cfqq->cfqg)
3095 return false;
3096
3097 if (cfq_slice_used(cfqq))
3098 return true;
3099
3100 /* Allow preemption only if we are idling on sync-noidle tree */
3101 if (cfqd->serving_type == SYNC_NOIDLE_WORKLOAD &&
3102 cfqq_type(new_cfqq) == SYNC_NOIDLE_WORKLOAD &&
3103 new_cfqq->service_tree->count == 2 &&
3104 RB_EMPTY_ROOT(&cfqq->sort_list))
3105 return true;
3106
Jens Axboe374f84a2006-07-23 01:42:19 +02003107 /*
3108 * So both queues are sync. Let the new request get disk time if
3109 * it's a metadata request and the current queue is doing regular IO.
3110 */
3111 if (rq_is_meta(rq) && !cfqq->meta_pending)
Jens Axboee6ec4fe2009-11-03 20:21:35 +01003112 return true;
Jens Axboe22e2c502005-06-27 10:55:12 +02003113
Divyesh Shah3a9a3f62009-01-30 12:46:41 +01003114 /*
3115 * Allow an RT request to pre-empt an ongoing non-RT cfqq timeslice.
3116 */
3117 if (cfq_class_rt(new_cfqq) && !cfq_class_rt(cfqq))
Jens Axboea6151c32009-10-07 20:02:57 +02003118 return true;
Divyesh Shah3a9a3f62009-01-30 12:46:41 +01003119
Jens Axboe1e3335d2007-02-14 19:59:49 +01003120 if (!cfqd->active_cic || !cfq_cfqq_wait_request(cfqq))
Jens Axboea6151c32009-10-07 20:02:57 +02003121 return false;
Jens Axboe1e3335d2007-02-14 19:59:49 +01003122
3123 /*
3124 * if this request is as-good as one we would expect from the
3125 * current cfqq, let it preempt
3126 */
Shaohua Lie9ce3352010-03-19 08:03:04 +01003127 if (cfq_rq_close(cfqd, cfqq, rq))
Jens Axboea6151c32009-10-07 20:02:57 +02003128 return true;
Jens Axboe1e3335d2007-02-14 19:59:49 +01003129
Jens Axboea6151c32009-10-07 20:02:57 +02003130 return false;
Jens Axboe22e2c502005-06-27 10:55:12 +02003131}
3132
3133/*
3134 * cfqq preempts the active queue. if we allowed preempt with no slice left,
3135 * let it have half of its nominal slice.
3136 */
3137static void cfq_preempt_queue(struct cfq_data *cfqd, struct cfq_queue *cfqq)
3138{
Jens Axboe7b679132008-05-30 12:23:07 +02003139 cfq_log_cfqq(cfqd, cfqq, "preempt");
Jens Axboe6084cdd2007-04-23 08:25:00 +02003140 cfq_slice_expired(cfqd, 1);
Jens Axboe22e2c502005-06-27 10:55:12 +02003141
Jens Axboebf572252006-07-19 20:29:12 +02003142 /*
3143 * Put the new queue at the front of the of the current list,
3144 * so we know that it will be selected next.
3145 */
3146 BUG_ON(!cfq_cfqq_on_rr(cfqq));
Jens Axboeedd75ff2007-04-19 12:03:34 +02003147
3148 cfq_service_tree_add(cfqd, cfqq, 1);
Jens Axboebf572252006-07-19 20:29:12 +02003149
Jens Axboe44f7c162007-01-19 11:51:58 +11003150 cfqq->slice_end = 0;
3151 cfq_mark_cfqq_slice_new(cfqq);
Jens Axboe22e2c502005-06-27 10:55:12 +02003152}
3153
3154/*
Jens Axboe5e705372006-07-13 12:39:25 +02003155 * Called when a new fs request (rq) is added (to cfqq). Check if there's
Jens Axboe22e2c502005-06-27 10:55:12 +02003156 * something we should do about it
3157 */
3158static void
Jens Axboe5e705372006-07-13 12:39:25 +02003159cfq_rq_enqueued(struct cfq_data *cfqd, struct cfq_queue *cfqq,
3160 struct request *rq)
Jens Axboe22e2c502005-06-27 10:55:12 +02003161{
Jens Axboe5e705372006-07-13 12:39:25 +02003162 struct cfq_io_context *cic = RQ_CIC(rq);
Jens Axboe12e9fdd2006-06-01 10:09:56 +02003163
Aaron Carroll45333d52008-08-26 15:52:36 +02003164 cfqd->rq_queued++;
Jens Axboe374f84a2006-07-23 01:42:19 +02003165 if (rq_is_meta(rq))
3166 cfqq->meta_pending++;
3167
Jens Axboe9c2c38a2005-08-24 14:57:54 +02003168 cfq_update_io_thinktime(cfqd, cic);
Jeff Moyerb2c18e12009-10-23 17:14:49 -04003169 cfq_update_io_seektime(cfqd, cfqq, rq);
Jens Axboe9c2c38a2005-08-24 14:57:54 +02003170 cfq_update_idle_window(cfqd, cfqq, cic);
3171
Jeff Moyerb2c18e12009-10-23 17:14:49 -04003172 cfqq->last_request_pos = blk_rq_pos(rq) + blk_rq_sectors(rq);
Jens Axboe22e2c502005-06-27 10:55:12 +02003173
3174 if (cfqq == cfqd->active_queue) {
3175 /*
Jens Axboeb0291952009-04-07 11:38:31 +02003176 * Remember that we saw a request from this process, but
3177 * don't start queuing just yet. Otherwise we risk seeing lots
3178 * of tiny requests, because we disrupt the normal plugging
Jens Axboed6ceb252009-04-14 14:18:16 +02003179 * and merging. If the request is already larger than a single
3180 * page, let it rip immediately. For that case we assume that
Jens Axboe2d870722009-04-15 12:12:46 +02003181 * merging is already done. Ditto for a busy system that
3182 * has other work pending, don't risk delaying until the
3183 * idle timer unplug to continue working.
Jens Axboe22e2c502005-06-27 10:55:12 +02003184 */
Jens Axboed6ceb252009-04-14 14:18:16 +02003185 if (cfq_cfqq_wait_request(cfqq)) {
Jens Axboe2d870722009-04-15 12:12:46 +02003186 if (blk_rq_bytes(rq) > PAGE_CACHE_SIZE ||
3187 cfqd->busy_queues > 1) {
Jens Axboed6ceb252009-04-14 14:18:16 +02003188 del_timer(&cfqd->idle_slice_timer);
Gui Jianfeng554554f2009-12-10 09:38:39 +01003189 cfq_clear_cfqq_wait_request(cfqq);
Vivek Goyalbf791932009-12-03 12:59:37 -05003190 __blk_run_queue(cfqd->queue);
3191 } else
3192 cfq_mark_cfqq_must_dispatch(cfqq);
Jens Axboed6ceb252009-04-14 14:18:16 +02003193 }
Jens Axboe5e705372006-07-13 12:39:25 +02003194 } else if (cfq_should_preempt(cfqd, cfqq, rq)) {
Jens Axboe22e2c502005-06-27 10:55:12 +02003195 /*
3196 * not the active queue - expire current slice if it is
3197 * idle and has expired it's mean thinktime or this new queue
Divyesh Shah3a9a3f62009-01-30 12:46:41 +01003198 * has some old slice time left and is of higher priority or
3199 * this new queue is RT and the current one is BE
Jens Axboe22e2c502005-06-27 10:55:12 +02003200 */
3201 cfq_preempt_queue(cfqd, cfqq);
Tejun Heoa7f55792009-04-23 11:05:17 +09003202 __blk_run_queue(cfqd->queue);
Jens Axboe22e2c502005-06-27 10:55:12 +02003203 }
3204}
3205
Jens Axboe165125e2007-07-24 09:28:11 +02003206static void cfq_insert_request(struct request_queue *q, struct request *rq)
Jens Axboe22e2c502005-06-27 10:55:12 +02003207{
Jens Axboeb4878f22005-10-20 16:42:29 +02003208 struct cfq_data *cfqd = q->elevator->elevator_data;
Jens Axboe5e705372006-07-13 12:39:25 +02003209 struct cfq_queue *cfqq = RQ_CFQQ(rq);
Jens Axboe22e2c502005-06-27 10:55:12 +02003210
Jens Axboe7b679132008-05-30 12:23:07 +02003211 cfq_log_cfqq(cfqd, cfqq, "insert_request");
Jens Axboefd0928d2008-01-24 08:52:45 +01003212 cfq_init_prio_data(cfqq, RQ_CIC(rq)->ioc);
Linus Torvalds1da177e2005-04-16 15:20:36 -07003213
Jens Axboe30996f42009-10-05 11:03:39 +02003214 rq_set_fifo_time(rq, jiffies + cfqd->cfq_fifo_expire[rq_is_sync(rq)]);
Jens Axboe22e2c502005-06-27 10:55:12 +02003215 list_add_tail(&rq->queuelist, &cfqq->fifo);
Corrado Zoccoloaa6f6a32009-10-26 22:44:33 +01003216 cfq_add_rq_rb(rq);
Jens Axboe22e2c502005-06-27 10:55:12 +02003217
Jens Axboe5e705372006-07-13 12:39:25 +02003218 cfq_rq_enqueued(cfqd, cfqq, rq);
Linus Torvalds1da177e2005-04-16 15:20:36 -07003219}
3220
Aaron Carroll45333d52008-08-26 15:52:36 +02003221/*
3222 * Update hw_tag based on peak queue depth over 50 samples under
3223 * sufficient load.
3224 */
3225static void cfq_update_hw_tag(struct cfq_data *cfqd)
3226{
Shaohua Li1a1238a2009-10-27 08:46:23 +01003227 struct cfq_queue *cfqq = cfqd->active_queue;
3228
Corrado Zoccolo53c583d2010-02-28 19:45:05 +01003229 if (cfqd->rq_in_driver > cfqd->hw_tag_est_depth)
3230 cfqd->hw_tag_est_depth = cfqd->rq_in_driver;
Corrado Zoccoloe459dd02009-11-26 10:02:57 +01003231
3232 if (cfqd->hw_tag == 1)
3233 return;
Aaron Carroll45333d52008-08-26 15:52:36 +02003234
3235 if (cfqd->rq_queued <= CFQ_HW_QUEUE_MIN &&
Corrado Zoccolo53c583d2010-02-28 19:45:05 +01003236 cfqd->rq_in_driver <= CFQ_HW_QUEUE_MIN)
Aaron Carroll45333d52008-08-26 15:52:36 +02003237 return;
3238
Shaohua Li1a1238a2009-10-27 08:46:23 +01003239 /*
3240 * If active queue hasn't enough requests and can idle, cfq might not
3241 * dispatch sufficient requests to hardware. Don't zero hw_tag in this
3242 * case
3243 */
3244 if (cfqq && cfq_cfqq_idle_window(cfqq) &&
3245 cfqq->dispatched + cfqq->queued[0] + cfqq->queued[1] <
Corrado Zoccolo53c583d2010-02-28 19:45:05 +01003246 CFQ_HW_QUEUE_MIN && cfqd->rq_in_driver < CFQ_HW_QUEUE_MIN)
Shaohua Li1a1238a2009-10-27 08:46:23 +01003247 return;
3248
Aaron Carroll45333d52008-08-26 15:52:36 +02003249 if (cfqd->hw_tag_samples++ < 50)
3250 return;
3251
Corrado Zoccoloe459dd02009-11-26 10:02:57 +01003252 if (cfqd->hw_tag_est_depth >= CFQ_HW_QUEUE_MIN)
Aaron Carroll45333d52008-08-26 15:52:36 +02003253 cfqd->hw_tag = 1;
3254 else
3255 cfqd->hw_tag = 0;
Aaron Carroll45333d52008-08-26 15:52:36 +02003256}
3257
Vivek Goyal7667aa02009-12-08 17:52:58 -05003258static bool cfq_should_wait_busy(struct cfq_data *cfqd, struct cfq_queue *cfqq)
3259{
3260 struct cfq_io_context *cic = cfqd->active_cic;
3261
3262 /* If there are other queues in the group, don't wait */
3263 if (cfqq->cfqg->nr_cfqq > 1)
3264 return false;
3265
3266 if (cfq_slice_used(cfqq))
3267 return true;
3268
3269 /* if slice left is less than think time, wait busy */
3270 if (cic && sample_valid(cic->ttime_samples)
3271 && (cfqq->slice_end - jiffies < cic->ttime_mean))
3272 return true;
3273
3274 /*
3275 * If think times is less than a jiffy than ttime_mean=0 and above
3276 * will not be true. It might happen that slice has not expired yet
3277 * but will expire soon (4-5 ns) during select_queue(). To cover the
3278 * case where think time is less than a jiffy, mark the queue wait
3279 * busy if only 1 jiffy is left in the slice.
3280 */
3281 if (cfqq->slice_end - jiffies == 1)
3282 return true;
3283
3284 return false;
3285}
3286
Jens Axboe165125e2007-07-24 09:28:11 +02003287static void cfq_completed_request(struct request_queue *q, struct request *rq)
Linus Torvalds1da177e2005-04-16 15:20:36 -07003288{
Jens Axboe5e705372006-07-13 12:39:25 +02003289 struct cfq_queue *cfqq = RQ_CFQQ(rq);
Jens Axboeb4878f22005-10-20 16:42:29 +02003290 struct cfq_data *cfqd = cfqq->cfqd;
Jens Axboe5380a102006-07-13 12:37:56 +02003291 const int sync = rq_is_sync(rq);
Jens Axboeb4878f22005-10-20 16:42:29 +02003292 unsigned long now;
Linus Torvalds1da177e2005-04-16 15:20:36 -07003293
Jens Axboeb4878f22005-10-20 16:42:29 +02003294 now = jiffies;
Vivek Goyal2868ef72009-12-03 12:59:48 -05003295 cfq_log_cfqq(cfqd, cfqq, "complete rqnoidle %d", !!rq_noidle(rq));
Linus Torvalds1da177e2005-04-16 15:20:36 -07003296
Aaron Carroll45333d52008-08-26 15:52:36 +02003297 cfq_update_hw_tag(cfqd);
3298
Corrado Zoccolo53c583d2010-02-28 19:45:05 +01003299 WARN_ON(!cfqd->rq_in_driver);
Jens Axboe6d048f52007-04-25 12:44:27 +02003300 WARN_ON(!cfqq->dispatched);
Corrado Zoccolo53c583d2010-02-28 19:45:05 +01003301 cfqd->rq_in_driver--;
Jens Axboe6d048f52007-04-25 12:44:27 +02003302 cfqq->dispatched--;
Linus Torvalds1da177e2005-04-16 15:20:36 -07003303
Corrado Zoccolo53c583d2010-02-28 19:45:05 +01003304 cfqd->rq_in_flight[cfq_cfqq_sync(cfqq)]--;
Jens Axboe3ed9a292007-04-23 08:33:33 +02003305
Vivek Goyal365722b2009-10-03 15:21:27 +02003306 if (sync) {
Jens Axboe5e705372006-07-13 12:39:25 +02003307 RQ_CIC(rq)->last_end_request = now;
Corrado Zoccolo573412b2009-12-06 11:48:52 +01003308 if (!time_after(rq->start_time + cfqd->cfq_fifo_expire[1], now))
3309 cfqd->last_delayed_sync = now;
Vivek Goyal365722b2009-10-03 15:21:27 +02003310 }
Jens Axboecaaa5f92006-06-16 11:23:00 +02003311
3312 /*
3313 * If this is the active queue, check if it needs to be expired,
3314 * or if we want to idle in case it has no pending requests.
3315 */
3316 if (cfqd->active_queue == cfqq) {
Jens Axboea36e71f2009-04-15 12:15:11 +02003317 const bool cfqq_empty = RB_EMPTY_ROOT(&cfqq->sort_list);
3318
Jens Axboe44f7c162007-01-19 11:51:58 +11003319 if (cfq_cfqq_slice_new(cfqq)) {
3320 cfq_set_prio_slice(cfqd, cfqq);
3321 cfq_clear_cfqq_slice_new(cfqq);
3322 }
Vivek Goyalf75edf22009-12-03 12:59:53 -05003323
3324 /*
Vivek Goyal7667aa02009-12-08 17:52:58 -05003325 * Should we wait for next request to come in before we expire
3326 * the queue.
Vivek Goyalf75edf22009-12-03 12:59:53 -05003327 */
Vivek Goyal7667aa02009-12-08 17:52:58 -05003328 if (cfq_should_wait_busy(cfqd, cfqq)) {
Vivek Goyalf75edf22009-12-03 12:59:53 -05003329 cfqq->slice_end = jiffies + cfqd->cfq_slice_idle;
3330 cfq_mark_cfqq_wait_busy(cfqq);
Divyesh Shahb1ffe732010-03-25 15:45:03 +01003331 cfq_log_cfqq(cfqd, cfqq, "will busy wait");
Vivek Goyalf75edf22009-12-03 12:59:53 -05003332 }
3333
Jens Axboea36e71f2009-04-15 12:15:11 +02003334 /*
Corrado Zoccolo8e550632009-11-26 10:02:58 +01003335 * Idling is not enabled on:
3336 * - expired queues
3337 * - idle-priority queues
3338 * - async queues
3339 * - queues with still some requests queued
3340 * - when there is a close cooperator
Jens Axboea36e71f2009-04-15 12:15:11 +02003341 */
Jens Axboe08717142008-01-28 11:38:15 +01003342 if (cfq_slice_used(cfqq) || cfq_class_idle(cfqq))
Jens Axboe6084cdd2007-04-23 08:25:00 +02003343 cfq_slice_expired(cfqd, 1);
Corrado Zoccolo8e550632009-11-26 10:02:58 +01003344 else if (sync && cfqq_empty &&
3345 !cfq_close_cooperator(cfqd, cfqq)) {
3346 cfqd->noidle_tree_requires_idle |= !rq_noidle(rq);
3347 /*
3348 * Idling is enabled for SYNC_WORKLOAD.
3349 * SYNC_NOIDLE_WORKLOAD idles at the end of the tree
3350 * only if we processed at least one !rq_noidle request
3351 */
3352 if (cfqd->serving_type == SYNC_WORKLOAD
Vivek Goyalc04645e2009-12-03 12:59:56 -05003353 || cfqd->noidle_tree_requires_idle
3354 || cfqq->cfqg->nr_cfqq == 1)
Corrado Zoccolo8e550632009-11-26 10:02:58 +01003355 cfq_arm_slice_timer(cfqd);
3356 }
Jens Axboecaaa5f92006-06-16 11:23:00 +02003357 }
Jens Axboe6d048f52007-04-25 12:44:27 +02003358
Corrado Zoccolo53c583d2010-02-28 19:45:05 +01003359 if (!cfqd->rq_in_driver)
Jens Axboe23e018a2009-10-05 08:52:35 +02003360 cfq_schedule_dispatch(cfqd);
Linus Torvalds1da177e2005-04-16 15:20:36 -07003361}
3362
Jens Axboe22e2c502005-06-27 10:55:12 +02003363/*
3364 * we temporarily boost lower priority queues if they are holding fs exclusive
3365 * resources. they are boosted to normal prio (CLASS_BE/4)
3366 */
3367static void cfq_prio_boost(struct cfq_queue *cfqq)
Linus Torvalds1da177e2005-04-16 15:20:36 -07003368{
Jens Axboe22e2c502005-06-27 10:55:12 +02003369 if (has_fs_excl()) {
3370 /*
3371 * boost idle prio on transactions that would lock out other
3372 * users of the filesystem
3373 */
3374 if (cfq_class_idle(cfqq))
3375 cfqq->ioprio_class = IOPRIO_CLASS_BE;
3376 if (cfqq->ioprio > IOPRIO_NORM)
3377 cfqq->ioprio = IOPRIO_NORM;
3378 } else {
3379 /*
Corrado Zoccolodddb7452009-11-02 10:40:37 +01003380 * unboost the queue (if needed)
Jens Axboe22e2c502005-06-27 10:55:12 +02003381 */
Corrado Zoccolodddb7452009-11-02 10:40:37 +01003382 cfqq->ioprio_class = cfqq->org_ioprio_class;
3383 cfqq->ioprio = cfqq->org_ioprio;
Linus Torvalds1da177e2005-04-16 15:20:36 -07003384 }
Jens Axboe22e2c502005-06-27 10:55:12 +02003385}
3386
Jens Axboe89850f72006-07-22 16:48:31 +02003387static inline int __cfq_may_queue(struct cfq_queue *cfqq)
Jens Axboe22e2c502005-06-27 10:55:12 +02003388{
Jens Axboe1b379d82009-08-11 08:26:11 +02003389 if (cfq_cfqq_wait_request(cfqq) && !cfq_cfqq_must_alloc_slice(cfqq)) {
Jens Axboe3b181522005-06-27 10:56:24 +02003390 cfq_mark_cfqq_must_alloc_slice(cfqq);
Jens Axboe22e2c502005-06-27 10:55:12 +02003391 return ELV_MQUEUE_MUST;
Jens Axboe3b181522005-06-27 10:56:24 +02003392 }
Jens Axboe22e2c502005-06-27 10:55:12 +02003393
3394 return ELV_MQUEUE_MAY;
Jens Axboe22e2c502005-06-27 10:55:12 +02003395}
3396
Jens Axboe165125e2007-07-24 09:28:11 +02003397static int cfq_may_queue(struct request_queue *q, int rw)
Jens Axboe22e2c502005-06-27 10:55:12 +02003398{
3399 struct cfq_data *cfqd = q->elevator->elevator_data;
3400 struct task_struct *tsk = current;
Vasily Tarasov91fac312007-04-25 12:29:51 +02003401 struct cfq_io_context *cic;
Jens Axboe22e2c502005-06-27 10:55:12 +02003402 struct cfq_queue *cfqq;
3403
3404 /*
3405 * don't force setup of a queue from here, as a call to may_queue
3406 * does not necessarily imply that a request actually will be queued.
3407 * so just lookup a possibly existing queue, or return 'may queue'
3408 * if that fails
3409 */
Jens Axboe4ac845a2008-01-24 08:44:49 +01003410 cic = cfq_cic_lookup(cfqd, tsk->io_context);
Vasily Tarasov91fac312007-04-25 12:29:51 +02003411 if (!cic)
3412 return ELV_MQUEUE_MAY;
3413
Jens Axboeb0b78f82009-04-08 10:56:08 +02003414 cfqq = cic_to_cfqq(cic, rw_is_sync(rw));
Jens Axboe22e2c502005-06-27 10:55:12 +02003415 if (cfqq) {
Jens Axboefd0928d2008-01-24 08:52:45 +01003416 cfq_init_prio_data(cfqq, cic->ioc);
Jens Axboe22e2c502005-06-27 10:55:12 +02003417 cfq_prio_boost(cfqq);
3418
Jens Axboe89850f72006-07-22 16:48:31 +02003419 return __cfq_may_queue(cfqq);
Jens Axboe22e2c502005-06-27 10:55:12 +02003420 }
3421
3422 return ELV_MQUEUE_MAY;
Linus Torvalds1da177e2005-04-16 15:20:36 -07003423}
3424
Linus Torvalds1da177e2005-04-16 15:20:36 -07003425/*
3426 * queue lock held here
3427 */
Jens Axboebb37b942006-12-01 10:42:33 +01003428static void cfq_put_request(struct request *rq)
Linus Torvalds1da177e2005-04-16 15:20:36 -07003429{
Jens Axboe5e705372006-07-13 12:39:25 +02003430 struct cfq_queue *cfqq = RQ_CFQQ(rq);
Linus Torvalds1da177e2005-04-16 15:20:36 -07003431
Jens Axboe5e705372006-07-13 12:39:25 +02003432 if (cfqq) {
Jens Axboe22e2c502005-06-27 10:55:12 +02003433 const int rw = rq_data_dir(rq);
Linus Torvalds1da177e2005-04-16 15:20:36 -07003434
Jens Axboe22e2c502005-06-27 10:55:12 +02003435 BUG_ON(!cfqq->allocated[rw]);
3436 cfqq->allocated[rw]--;
Linus Torvalds1da177e2005-04-16 15:20:36 -07003437
Jens Axboe5e705372006-07-13 12:39:25 +02003438 put_io_context(RQ_CIC(rq)->ioc);
Linus Torvalds1da177e2005-04-16 15:20:36 -07003439
Linus Torvalds1da177e2005-04-16 15:20:36 -07003440 rq->elevator_private = NULL;
Jens Axboe5e705372006-07-13 12:39:25 +02003441 rq->elevator_private2 = NULL;
Linus Torvalds1da177e2005-04-16 15:20:36 -07003442
Linus Torvalds1da177e2005-04-16 15:20:36 -07003443 cfq_put_queue(cfqq);
3444 }
3445}
3446
Jeff Moyerdf5fe3e2009-10-23 17:14:50 -04003447static struct cfq_queue *
3448cfq_merge_cfqqs(struct cfq_data *cfqd, struct cfq_io_context *cic,
3449 struct cfq_queue *cfqq)
3450{
3451 cfq_log_cfqq(cfqd, cfqq, "merging with queue %p", cfqq->new_cfqq);
3452 cic_set_cfqq(cic, cfqq->new_cfqq, 1);
Jeff Moyerb3b6d042009-10-23 17:14:51 -04003453 cfq_mark_cfqq_coop(cfqq->new_cfqq);
Jeff Moyerdf5fe3e2009-10-23 17:14:50 -04003454 cfq_put_queue(cfqq);
3455 return cic_to_cfqq(cic, 1);
3456}
3457
Jeff Moyere6c5bc72009-10-23 17:14:52 -04003458/*
3459 * Returns NULL if a new cfqq should be allocated, or the old cfqq if this
3460 * was the last process referring to said cfqq.
3461 */
3462static struct cfq_queue *
3463split_cfqq(struct cfq_io_context *cic, struct cfq_queue *cfqq)
3464{
3465 if (cfqq_process_refs(cfqq) == 1) {
Jeff Moyere6c5bc72009-10-23 17:14:52 -04003466 cfqq->pid = current->pid;
3467 cfq_clear_cfqq_coop(cfqq);
Shaohua Liae54abe2010-02-05 13:11:45 +01003468 cfq_clear_cfqq_split_coop(cfqq);
Jeff Moyere6c5bc72009-10-23 17:14:52 -04003469 return cfqq;
3470 }
3471
3472 cic_set_cfqq(cic, NULL, 1);
3473 cfq_put_queue(cfqq);
3474 return NULL;
3475}
Linus Torvalds1da177e2005-04-16 15:20:36 -07003476/*
Jens Axboe22e2c502005-06-27 10:55:12 +02003477 * Allocate cfq data structures associated with this request.
Linus Torvalds1da177e2005-04-16 15:20:36 -07003478 */
Jens Axboe22e2c502005-06-27 10:55:12 +02003479static int
Jens Axboe165125e2007-07-24 09:28:11 +02003480cfq_set_request(struct request_queue *q, struct request *rq, gfp_t gfp_mask)
Linus Torvalds1da177e2005-04-16 15:20:36 -07003481{
3482 struct cfq_data *cfqd = q->elevator->elevator_data;
3483 struct cfq_io_context *cic;
3484 const int rw = rq_data_dir(rq);
Jens Axboea6151c32009-10-07 20:02:57 +02003485 const bool is_sync = rq_is_sync(rq);
Jens Axboe22e2c502005-06-27 10:55:12 +02003486 struct cfq_queue *cfqq;
Linus Torvalds1da177e2005-04-16 15:20:36 -07003487 unsigned long flags;
3488
3489 might_sleep_if(gfp_mask & __GFP_WAIT);
3490
Jens Axboee2d74ac2006-03-28 08:59:01 +02003491 cic = cfq_get_io_context(cfqd, gfp_mask);
Jens Axboe22e2c502005-06-27 10:55:12 +02003492
Linus Torvalds1da177e2005-04-16 15:20:36 -07003493 spin_lock_irqsave(q->queue_lock, flags);
3494
Jens Axboe22e2c502005-06-27 10:55:12 +02003495 if (!cic)
3496 goto queue_fail;
Linus Torvalds1da177e2005-04-16 15:20:36 -07003497
Jeff Moyere6c5bc72009-10-23 17:14:52 -04003498new_queue:
Vasily Tarasov91fac312007-04-25 12:29:51 +02003499 cfqq = cic_to_cfqq(cic, is_sync);
Vivek Goyal32f2e802009-07-09 22:13:16 +02003500 if (!cfqq || cfqq == &cfqd->oom_cfqq) {
Jens Axboefd0928d2008-01-24 08:52:45 +01003501 cfqq = cfq_get_queue(cfqd, is_sync, cic->ioc, gfp_mask);
Vasily Tarasov91fac312007-04-25 12:29:51 +02003502 cic_set_cfqq(cic, cfqq, is_sync);
Jeff Moyerdf5fe3e2009-10-23 17:14:50 -04003503 } else {
3504 /*
Jeff Moyere6c5bc72009-10-23 17:14:52 -04003505 * If the queue was seeky for too long, break it apart.
3506 */
Shaohua Liae54abe2010-02-05 13:11:45 +01003507 if (cfq_cfqq_coop(cfqq) && cfq_cfqq_split_coop(cfqq)) {
Jeff Moyere6c5bc72009-10-23 17:14:52 -04003508 cfq_log_cfqq(cfqd, cfqq, "breaking apart cfqq");
3509 cfqq = split_cfqq(cic, cfqq);
3510 if (!cfqq)
3511 goto new_queue;
3512 }
3513
3514 /*
Jeff Moyerdf5fe3e2009-10-23 17:14:50 -04003515 * Check to see if this queue is scheduled to merge with
3516 * another, closely cooperating queue. The merging of
3517 * queues happens here as it must be done in process context.
3518 * The reference on new_cfqq was taken in merge_cfqqs.
3519 */
3520 if (cfqq->new_cfqq)
3521 cfqq = cfq_merge_cfqqs(cfqd, cic, cfqq);
Vasily Tarasov91fac312007-04-25 12:29:51 +02003522 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07003523
3524 cfqq->allocated[rw]++;
Jens Axboe22e2c502005-06-27 10:55:12 +02003525 atomic_inc(&cfqq->ref);
Jens Axboe5e705372006-07-13 12:39:25 +02003526
Linus Torvalds1da177e2005-04-16 15:20:36 -07003527 spin_unlock_irqrestore(q->queue_lock, flags);
3528
Jens Axboe5e705372006-07-13 12:39:25 +02003529 rq->elevator_private = cic;
3530 rq->elevator_private2 = cfqq;
3531 return 0;
Jens Axboe3b181522005-06-27 10:56:24 +02003532
Jens Axboe22e2c502005-06-27 10:55:12 +02003533queue_fail:
3534 if (cic)
3535 put_io_context(cic->ioc);
Jens Axboe89850f72006-07-22 16:48:31 +02003536
Jens Axboe23e018a2009-10-05 08:52:35 +02003537 cfq_schedule_dispatch(cfqd);
Linus Torvalds1da177e2005-04-16 15:20:36 -07003538 spin_unlock_irqrestore(q->queue_lock, flags);
Jens Axboe7b679132008-05-30 12:23:07 +02003539 cfq_log(cfqd, "set_request fail");
Linus Torvalds1da177e2005-04-16 15:20:36 -07003540 return 1;
3541}
3542
David Howells65f27f32006-11-22 14:55:48 +00003543static void cfq_kick_queue(struct work_struct *work)
Jens Axboe22e2c502005-06-27 10:55:12 +02003544{
David Howells65f27f32006-11-22 14:55:48 +00003545 struct cfq_data *cfqd =
Jens Axboe23e018a2009-10-05 08:52:35 +02003546 container_of(work, struct cfq_data, unplug_work);
Jens Axboe165125e2007-07-24 09:28:11 +02003547 struct request_queue *q = cfqd->queue;
Jens Axboe22e2c502005-06-27 10:55:12 +02003548
Jens Axboe40bb54d2009-04-15 12:11:10 +02003549 spin_lock_irq(q->queue_lock);
Tejun Heoa7f55792009-04-23 11:05:17 +09003550 __blk_run_queue(cfqd->queue);
Jens Axboe40bb54d2009-04-15 12:11:10 +02003551 spin_unlock_irq(q->queue_lock);
Jens Axboe22e2c502005-06-27 10:55:12 +02003552}
3553
3554/*
3555 * Timer running if the active_queue is currently idling inside its time slice
3556 */
3557static void cfq_idle_slice_timer(unsigned long data)
3558{
3559 struct cfq_data *cfqd = (struct cfq_data *) data;
3560 struct cfq_queue *cfqq;
3561 unsigned long flags;
Jens Axboe3c6bd2f2007-01-19 12:06:33 +11003562 int timed_out = 1;
Jens Axboe22e2c502005-06-27 10:55:12 +02003563
Jens Axboe7b679132008-05-30 12:23:07 +02003564 cfq_log(cfqd, "idle timer fired");
3565
Jens Axboe22e2c502005-06-27 10:55:12 +02003566 spin_lock_irqsave(cfqd->queue->queue_lock, flags);
3567
Jens Axboefe094d92008-01-31 13:08:54 +01003568 cfqq = cfqd->active_queue;
3569 if (cfqq) {
Jens Axboe3c6bd2f2007-01-19 12:06:33 +11003570 timed_out = 0;
3571
Jens Axboe22e2c502005-06-27 10:55:12 +02003572 /*
Jens Axboeb0291952009-04-07 11:38:31 +02003573 * We saw a request before the queue expired, let it through
3574 */
3575 if (cfq_cfqq_must_dispatch(cfqq))
3576 goto out_kick;
3577
3578 /*
Jens Axboe22e2c502005-06-27 10:55:12 +02003579 * expired
3580 */
Jens Axboe44f7c162007-01-19 11:51:58 +11003581 if (cfq_slice_used(cfqq))
Jens Axboe22e2c502005-06-27 10:55:12 +02003582 goto expire;
3583
3584 /*
3585 * only expire and reinvoke request handler, if there are
3586 * other queues with pending requests
3587 */
Jens Axboecaaa5f92006-06-16 11:23:00 +02003588 if (!cfqd->busy_queues)
Jens Axboe22e2c502005-06-27 10:55:12 +02003589 goto out_cont;
Jens Axboe22e2c502005-06-27 10:55:12 +02003590
3591 /*
3592 * not expired and it has a request pending, let it dispatch
3593 */
Jens Axboe75e50982009-04-07 08:56:14 +02003594 if (!RB_EMPTY_ROOT(&cfqq->sort_list))
Jens Axboe22e2c502005-06-27 10:55:12 +02003595 goto out_kick;
Corrado Zoccolo76280af2009-11-26 10:02:58 +01003596
3597 /*
3598 * Queue depth flag is reset only when the idle didn't succeed
3599 */
3600 cfq_clear_cfqq_deep(cfqq);
Jens Axboe22e2c502005-06-27 10:55:12 +02003601 }
3602expire:
Jens Axboe6084cdd2007-04-23 08:25:00 +02003603 cfq_slice_expired(cfqd, timed_out);
Jens Axboe22e2c502005-06-27 10:55:12 +02003604out_kick:
Jens Axboe23e018a2009-10-05 08:52:35 +02003605 cfq_schedule_dispatch(cfqd);
Jens Axboe22e2c502005-06-27 10:55:12 +02003606out_cont:
3607 spin_unlock_irqrestore(cfqd->queue->queue_lock, flags);
3608}
3609
Jens Axboe3b181522005-06-27 10:56:24 +02003610static void cfq_shutdown_timer_wq(struct cfq_data *cfqd)
3611{
3612 del_timer_sync(&cfqd->idle_slice_timer);
Jens Axboe23e018a2009-10-05 08:52:35 +02003613 cancel_work_sync(&cfqd->unplug_work);
Jens Axboe3b181522005-06-27 10:56:24 +02003614}
Jens Axboe22e2c502005-06-27 10:55:12 +02003615
Vasily Tarasovc2dea2d2007-07-20 10:06:38 +02003616static void cfq_put_async_queues(struct cfq_data *cfqd)
3617{
3618 int i;
3619
3620 for (i = 0; i < IOPRIO_BE_NR; i++) {
3621 if (cfqd->async_cfqq[0][i])
3622 cfq_put_queue(cfqd->async_cfqq[0][i]);
3623 if (cfqd->async_cfqq[1][i])
3624 cfq_put_queue(cfqd->async_cfqq[1][i]);
Vasily Tarasovc2dea2d2007-07-20 10:06:38 +02003625 }
Oleg Nesterov2389d1e2007-11-05 08:58:05 +01003626
3627 if (cfqd->async_idle_cfqq)
3628 cfq_put_queue(cfqd->async_idle_cfqq);
Vasily Tarasovc2dea2d2007-07-20 10:06:38 +02003629}
3630
Jens Axboebb729bc2009-12-06 09:54:19 +01003631static void cfq_cfqd_free(struct rcu_head *head)
3632{
3633 kfree(container_of(head, struct cfq_data, rcu));
3634}
3635
Jens Axboeb374d182008-10-31 10:05:07 +01003636static void cfq_exit_queue(struct elevator_queue *e)
Linus Torvalds1da177e2005-04-16 15:20:36 -07003637{
Jens Axboe22e2c502005-06-27 10:55:12 +02003638 struct cfq_data *cfqd = e->elevator_data;
Jens Axboe165125e2007-07-24 09:28:11 +02003639 struct request_queue *q = cfqd->queue;
Jens Axboe22e2c502005-06-27 10:55:12 +02003640
Jens Axboe3b181522005-06-27 10:56:24 +02003641 cfq_shutdown_timer_wq(cfqd);
Jens Axboee2d74ac2006-03-28 08:59:01 +02003642
Al Virod9ff4182006-03-18 13:51:22 -05003643 spin_lock_irq(q->queue_lock);
Jens Axboee2d74ac2006-03-28 08:59:01 +02003644
Al Virod9ff4182006-03-18 13:51:22 -05003645 if (cfqd->active_queue)
Jens Axboe6084cdd2007-04-23 08:25:00 +02003646 __cfq_slice_expired(cfqd, cfqd->active_queue, 0);
Jens Axboee2d74ac2006-03-28 08:59:01 +02003647
3648 while (!list_empty(&cfqd->cic_list)) {
Al Virod9ff4182006-03-18 13:51:22 -05003649 struct cfq_io_context *cic = list_entry(cfqd->cic_list.next,
3650 struct cfq_io_context,
3651 queue_list);
Jens Axboe89850f72006-07-22 16:48:31 +02003652
3653 __cfq_exit_single_io_context(cfqd, cic);
Al Virod9ff4182006-03-18 13:51:22 -05003654 }
Jens Axboee2d74ac2006-03-28 08:59:01 +02003655
Vasily Tarasovc2dea2d2007-07-20 10:06:38 +02003656 cfq_put_async_queues(cfqd);
Vivek Goyalb1c35762009-12-03 12:59:47 -05003657 cfq_release_cfq_groups(cfqd);
3658 blkiocg_del_blkio_group(&cfqd->root_group.blkg);
Jens Axboe15c31be2007-07-10 13:43:25 +02003659
Al Virod9ff4182006-03-18 13:51:22 -05003660 spin_unlock_irq(q->queue_lock);
Al Viroa90d7422006-03-18 12:05:37 -05003661
3662 cfq_shutdown_timer_wq(cfqd);
3663
Vivek Goyalb1c35762009-12-03 12:59:47 -05003664 /* Wait for cfqg->blkg->key accessors to exit their grace periods. */
Jens Axboebb729bc2009-12-06 09:54:19 +01003665 call_rcu(&cfqd->rcu, cfq_cfqd_free);
Linus Torvalds1da177e2005-04-16 15:20:36 -07003666}
3667
Jens Axboe165125e2007-07-24 09:28:11 +02003668static void *cfq_init_queue(struct request_queue *q)
Linus Torvalds1da177e2005-04-16 15:20:36 -07003669{
3670 struct cfq_data *cfqd;
Corrado Zoccolo718eee02009-10-26 22:45:29 +01003671 int i, j;
Vivek Goyalcdb16e82009-12-03 12:59:38 -05003672 struct cfq_group *cfqg;
Vivek Goyal615f0252009-12-03 12:59:39 -05003673 struct cfq_rb_root *st;
Linus Torvalds1da177e2005-04-16 15:20:36 -07003674
Christoph Lameter94f60302007-07-17 04:03:29 -07003675 cfqd = kmalloc_node(sizeof(*cfqd), GFP_KERNEL | __GFP_ZERO, q->node);
Linus Torvalds1da177e2005-04-16 15:20:36 -07003676 if (!cfqd)
Jens Axboebc1c1162006-06-08 08:49:06 +02003677 return NULL;
Linus Torvalds1da177e2005-04-16 15:20:36 -07003678
Vivek Goyal1fa8f6d2009-12-03 12:59:41 -05003679 /* Init root service tree */
3680 cfqd->grp_service_tree = CFQ_RB_ROOT;
3681
Vivek Goyalcdb16e82009-12-03 12:59:38 -05003682 /* Init root group */
3683 cfqg = &cfqd->root_group;
Vivek Goyal615f0252009-12-03 12:59:39 -05003684 for_each_cfqg_st(cfqg, i, j, st)
3685 *st = CFQ_RB_ROOT;
Vivek Goyal1fa8f6d2009-12-03 12:59:41 -05003686 RB_CLEAR_NODE(&cfqg->rb_node);
Jens Axboe26a2ac02009-04-23 12:13:27 +02003687
Vivek Goyal25bc6b02009-12-03 12:59:43 -05003688 /* Give preference to root group over other groups */
3689 cfqg->weight = 2*BLKIO_WEIGHT_DEFAULT;
3690
Vivek Goyal25fb5162009-12-03 12:59:46 -05003691#ifdef CONFIG_CFQ_GROUP_IOSCHED
Vivek Goyalb1c35762009-12-03 12:59:47 -05003692 /*
3693 * Take a reference to root group which we never drop. This is just
3694 * to make sure that cfq_put_cfqg() does not try to kfree root group
3695 */
3696 atomic_set(&cfqg->ref, 1);
Vivek Goyal22084192009-12-03 12:59:49 -05003697 blkiocg_add_blkio_group(&blkio_root_cgroup, &cfqg->blkg, (void *)cfqd,
3698 0);
Vivek Goyal25fb5162009-12-03 12:59:46 -05003699#endif
Jens Axboe26a2ac02009-04-23 12:13:27 +02003700 /*
3701 * Not strictly needed (since RB_ROOT just clears the node and we
3702 * zeroed cfqd on alloc), but better be safe in case someone decides
3703 * to add magic to the rb code
3704 */
3705 for (i = 0; i < CFQ_PRIO_LISTS; i++)
3706 cfqd->prio_trees[i] = RB_ROOT;
3707
Jens Axboe6118b702009-06-30 09:34:12 +02003708 /*
3709 * Our fallback cfqq if cfq_find_alloc_queue() runs into OOM issues.
3710 * Grab a permanent reference to it, so that the normal code flow
3711 * will not attempt to free it.
3712 */
3713 cfq_init_cfqq(cfqd, &cfqd->oom_cfqq, 1, 0);
3714 atomic_inc(&cfqd->oom_cfqq.ref);
Vivek Goyalcdb16e82009-12-03 12:59:38 -05003715 cfq_link_cfqq_cfqg(&cfqd->oom_cfqq, &cfqd->root_group);
Jens Axboe6118b702009-06-30 09:34:12 +02003716
Al Virod9ff4182006-03-18 13:51:22 -05003717 INIT_LIST_HEAD(&cfqd->cic_list);
Linus Torvalds1da177e2005-04-16 15:20:36 -07003718
Linus Torvalds1da177e2005-04-16 15:20:36 -07003719 cfqd->queue = q;
Linus Torvalds1da177e2005-04-16 15:20:36 -07003720
Jens Axboe22e2c502005-06-27 10:55:12 +02003721 init_timer(&cfqd->idle_slice_timer);
3722 cfqd->idle_slice_timer.function = cfq_idle_slice_timer;
3723 cfqd->idle_slice_timer.data = (unsigned long) cfqd;
3724
Jens Axboe23e018a2009-10-05 08:52:35 +02003725 INIT_WORK(&cfqd->unplug_work, cfq_kick_queue);
Jens Axboe22e2c502005-06-27 10:55:12 +02003726
Linus Torvalds1da177e2005-04-16 15:20:36 -07003727 cfqd->cfq_quantum = cfq_quantum;
Jens Axboe22e2c502005-06-27 10:55:12 +02003728 cfqd->cfq_fifo_expire[0] = cfq_fifo_expire[0];
3729 cfqd->cfq_fifo_expire[1] = cfq_fifo_expire[1];
Linus Torvalds1da177e2005-04-16 15:20:36 -07003730 cfqd->cfq_back_max = cfq_back_max;
3731 cfqd->cfq_back_penalty = cfq_back_penalty;
Jens Axboe22e2c502005-06-27 10:55:12 +02003732 cfqd->cfq_slice[0] = cfq_slice_async;
3733 cfqd->cfq_slice[1] = cfq_slice_sync;
3734 cfqd->cfq_slice_async_rq = cfq_slice_async_rq;
3735 cfqd->cfq_slice_idle = cfq_slice_idle;
Jens Axboe963b72f2009-10-03 19:42:18 +02003736 cfqd->cfq_latency = 1;
Vivek Goyalae30c282009-12-03 12:59:55 -05003737 cfqd->cfq_group_isolation = 0;
Corrado Zoccoloe459dd02009-11-26 10:02:57 +01003738 cfqd->hw_tag = -1;
Corrado Zoccoloedc71132009-12-09 20:56:04 +01003739 /*
3740 * we optimistically start assuming sync ops weren't delayed in last
3741 * second, in order to have larger depth for async operations.
3742 */
Corrado Zoccolo573412b2009-12-06 11:48:52 +01003743 cfqd->last_delayed_sync = jiffies - HZ;
Jens Axboebb729bc2009-12-06 09:54:19 +01003744 INIT_RCU_HEAD(&cfqd->rcu);
Jens Axboebc1c1162006-06-08 08:49:06 +02003745 return cfqd;
Linus Torvalds1da177e2005-04-16 15:20:36 -07003746}
3747
3748static void cfq_slab_kill(void)
3749{
Jens Axboed6de8be2008-05-28 14:46:59 +02003750 /*
3751 * Caller already ensured that pending RCU callbacks are completed,
3752 * so we should have no busy allocations at this point.
3753 */
Linus Torvalds1da177e2005-04-16 15:20:36 -07003754 if (cfq_pool)
3755 kmem_cache_destroy(cfq_pool);
3756 if (cfq_ioc_pool)
3757 kmem_cache_destroy(cfq_ioc_pool);
3758}
3759
3760static int __init cfq_slab_setup(void)
3761{
Christoph Lameter0a31bd52007-05-06 14:49:57 -07003762 cfq_pool = KMEM_CACHE(cfq_queue, 0);
Linus Torvalds1da177e2005-04-16 15:20:36 -07003763 if (!cfq_pool)
3764 goto fail;
3765
Fabio Checconi34e6bbf2008-04-02 14:31:02 +02003766 cfq_ioc_pool = KMEM_CACHE(cfq_io_context, 0);
Linus Torvalds1da177e2005-04-16 15:20:36 -07003767 if (!cfq_ioc_pool)
3768 goto fail;
3769
3770 return 0;
3771fail:
3772 cfq_slab_kill();
3773 return -ENOMEM;
3774}
3775
Linus Torvalds1da177e2005-04-16 15:20:36 -07003776/*
3777 * sysfs parts below -->
3778 */
Linus Torvalds1da177e2005-04-16 15:20:36 -07003779static ssize_t
3780cfq_var_show(unsigned int var, char *page)
3781{
3782 return sprintf(page, "%d\n", var);
3783}
3784
3785static ssize_t
3786cfq_var_store(unsigned int *var, const char *page, size_t count)
3787{
3788 char *p = (char *) page;
3789
3790 *var = simple_strtoul(p, &p, 10);
3791 return count;
3792}
3793
Linus Torvalds1da177e2005-04-16 15:20:36 -07003794#define SHOW_FUNCTION(__FUNC, __VAR, __CONV) \
Jens Axboeb374d182008-10-31 10:05:07 +01003795static ssize_t __FUNC(struct elevator_queue *e, char *page) \
Linus Torvalds1da177e2005-04-16 15:20:36 -07003796{ \
Al Viro3d1ab402006-03-18 18:35:43 -05003797 struct cfq_data *cfqd = e->elevator_data; \
Linus Torvalds1da177e2005-04-16 15:20:36 -07003798 unsigned int __data = __VAR; \
3799 if (__CONV) \
3800 __data = jiffies_to_msecs(__data); \
3801 return cfq_var_show(__data, (page)); \
3802}
3803SHOW_FUNCTION(cfq_quantum_show, cfqd->cfq_quantum, 0);
Jens Axboe22e2c502005-06-27 10:55:12 +02003804SHOW_FUNCTION(cfq_fifo_expire_sync_show, cfqd->cfq_fifo_expire[1], 1);
3805SHOW_FUNCTION(cfq_fifo_expire_async_show, cfqd->cfq_fifo_expire[0], 1);
Al Viroe572ec72006-03-18 22:27:18 -05003806SHOW_FUNCTION(cfq_back_seek_max_show, cfqd->cfq_back_max, 0);
3807SHOW_FUNCTION(cfq_back_seek_penalty_show, cfqd->cfq_back_penalty, 0);
Jens Axboe22e2c502005-06-27 10:55:12 +02003808SHOW_FUNCTION(cfq_slice_idle_show, cfqd->cfq_slice_idle, 1);
3809SHOW_FUNCTION(cfq_slice_sync_show, cfqd->cfq_slice[1], 1);
3810SHOW_FUNCTION(cfq_slice_async_show, cfqd->cfq_slice[0], 1);
3811SHOW_FUNCTION(cfq_slice_async_rq_show, cfqd->cfq_slice_async_rq, 0);
Jens Axboe963b72f2009-10-03 19:42:18 +02003812SHOW_FUNCTION(cfq_low_latency_show, cfqd->cfq_latency, 0);
Vivek Goyalae30c282009-12-03 12:59:55 -05003813SHOW_FUNCTION(cfq_group_isolation_show, cfqd->cfq_group_isolation, 0);
Linus Torvalds1da177e2005-04-16 15:20:36 -07003814#undef SHOW_FUNCTION
3815
3816#define STORE_FUNCTION(__FUNC, __PTR, MIN, MAX, __CONV) \
Jens Axboeb374d182008-10-31 10:05:07 +01003817static ssize_t __FUNC(struct elevator_queue *e, const char *page, size_t count) \
Linus Torvalds1da177e2005-04-16 15:20:36 -07003818{ \
Al Viro3d1ab402006-03-18 18:35:43 -05003819 struct cfq_data *cfqd = e->elevator_data; \
Linus Torvalds1da177e2005-04-16 15:20:36 -07003820 unsigned int __data; \
3821 int ret = cfq_var_store(&__data, (page), count); \
3822 if (__data < (MIN)) \
3823 __data = (MIN); \
3824 else if (__data > (MAX)) \
3825 __data = (MAX); \
3826 if (__CONV) \
3827 *(__PTR) = msecs_to_jiffies(__data); \
3828 else \
3829 *(__PTR) = __data; \
3830 return ret; \
3831}
3832STORE_FUNCTION(cfq_quantum_store, &cfqd->cfq_quantum, 1, UINT_MAX, 0);
Jens Axboefe094d92008-01-31 13:08:54 +01003833STORE_FUNCTION(cfq_fifo_expire_sync_store, &cfqd->cfq_fifo_expire[1], 1,
3834 UINT_MAX, 1);
3835STORE_FUNCTION(cfq_fifo_expire_async_store, &cfqd->cfq_fifo_expire[0], 1,
3836 UINT_MAX, 1);
Al Viroe572ec72006-03-18 22:27:18 -05003837STORE_FUNCTION(cfq_back_seek_max_store, &cfqd->cfq_back_max, 0, UINT_MAX, 0);
Jens Axboefe094d92008-01-31 13:08:54 +01003838STORE_FUNCTION(cfq_back_seek_penalty_store, &cfqd->cfq_back_penalty, 1,
3839 UINT_MAX, 0);
Jens Axboe22e2c502005-06-27 10:55:12 +02003840STORE_FUNCTION(cfq_slice_idle_store, &cfqd->cfq_slice_idle, 0, UINT_MAX, 1);
3841STORE_FUNCTION(cfq_slice_sync_store, &cfqd->cfq_slice[1], 1, UINT_MAX, 1);
3842STORE_FUNCTION(cfq_slice_async_store, &cfqd->cfq_slice[0], 1, UINT_MAX, 1);
Jens Axboefe094d92008-01-31 13:08:54 +01003843STORE_FUNCTION(cfq_slice_async_rq_store, &cfqd->cfq_slice_async_rq, 1,
3844 UINT_MAX, 0);
Jens Axboe963b72f2009-10-03 19:42:18 +02003845STORE_FUNCTION(cfq_low_latency_store, &cfqd->cfq_latency, 0, 1, 0);
Vivek Goyalae30c282009-12-03 12:59:55 -05003846STORE_FUNCTION(cfq_group_isolation_store, &cfqd->cfq_group_isolation, 0, 1, 0);
Linus Torvalds1da177e2005-04-16 15:20:36 -07003847#undef STORE_FUNCTION
3848
Al Viroe572ec72006-03-18 22:27:18 -05003849#define CFQ_ATTR(name) \
3850 __ATTR(name, S_IRUGO|S_IWUSR, cfq_##name##_show, cfq_##name##_store)
Jens Axboe3b181522005-06-27 10:56:24 +02003851
Al Viroe572ec72006-03-18 22:27:18 -05003852static struct elv_fs_entry cfq_attrs[] = {
3853 CFQ_ATTR(quantum),
Al Viroe572ec72006-03-18 22:27:18 -05003854 CFQ_ATTR(fifo_expire_sync),
3855 CFQ_ATTR(fifo_expire_async),
3856 CFQ_ATTR(back_seek_max),
3857 CFQ_ATTR(back_seek_penalty),
3858 CFQ_ATTR(slice_sync),
3859 CFQ_ATTR(slice_async),
3860 CFQ_ATTR(slice_async_rq),
3861 CFQ_ATTR(slice_idle),
Jens Axboe963b72f2009-10-03 19:42:18 +02003862 CFQ_ATTR(low_latency),
Vivek Goyalae30c282009-12-03 12:59:55 -05003863 CFQ_ATTR(group_isolation),
Al Viroe572ec72006-03-18 22:27:18 -05003864 __ATTR_NULL
Linus Torvalds1da177e2005-04-16 15:20:36 -07003865};
3866
Linus Torvalds1da177e2005-04-16 15:20:36 -07003867static struct elevator_type iosched_cfq = {
3868 .ops = {
3869 .elevator_merge_fn = cfq_merge,
3870 .elevator_merged_fn = cfq_merged_request,
3871 .elevator_merge_req_fn = cfq_merged_requests,
Jens Axboeda775262006-12-20 11:04:12 +01003872 .elevator_allow_merge_fn = cfq_allow_merge,
Jens Axboeb4878f22005-10-20 16:42:29 +02003873 .elevator_dispatch_fn = cfq_dispatch_requests,
Linus Torvalds1da177e2005-04-16 15:20:36 -07003874 .elevator_add_req_fn = cfq_insert_request,
Jens Axboeb4878f22005-10-20 16:42:29 +02003875 .elevator_activate_req_fn = cfq_activate_request,
Linus Torvalds1da177e2005-04-16 15:20:36 -07003876 .elevator_deactivate_req_fn = cfq_deactivate_request,
3877 .elevator_queue_empty_fn = cfq_queue_empty,
3878 .elevator_completed_req_fn = cfq_completed_request,
Jens Axboe21183b02006-07-13 12:33:14 +02003879 .elevator_former_req_fn = elv_rb_former_request,
3880 .elevator_latter_req_fn = elv_rb_latter_request,
Linus Torvalds1da177e2005-04-16 15:20:36 -07003881 .elevator_set_req_fn = cfq_set_request,
3882 .elevator_put_req_fn = cfq_put_request,
3883 .elevator_may_queue_fn = cfq_may_queue,
3884 .elevator_init_fn = cfq_init_queue,
3885 .elevator_exit_fn = cfq_exit_queue,
Jens Axboefc463792006-08-29 09:05:44 +02003886 .trim = cfq_free_io_context,
Linus Torvalds1da177e2005-04-16 15:20:36 -07003887 },
Al Viro3d1ab402006-03-18 18:35:43 -05003888 .elevator_attrs = cfq_attrs,
Linus Torvalds1da177e2005-04-16 15:20:36 -07003889 .elevator_name = "cfq",
3890 .elevator_owner = THIS_MODULE,
3891};
3892
Vivek Goyal3e252062009-12-04 10:36:42 -05003893#ifdef CONFIG_CFQ_GROUP_IOSCHED
3894static struct blkio_policy_type blkio_policy_cfq = {
3895 .ops = {
3896 .blkio_unlink_group_fn = cfq_unlink_blkio_group,
3897 .blkio_update_group_weight_fn = cfq_update_blkio_group_weight,
3898 },
3899};
3900#else
3901static struct blkio_policy_type blkio_policy_cfq;
3902#endif
3903
Linus Torvalds1da177e2005-04-16 15:20:36 -07003904static int __init cfq_init(void)
3905{
Jens Axboe22e2c502005-06-27 10:55:12 +02003906 /*
3907 * could be 0 on HZ < 1000 setups
3908 */
3909 if (!cfq_slice_async)
3910 cfq_slice_async = 1;
3911 if (!cfq_slice_idle)
3912 cfq_slice_idle = 1;
3913
Linus Torvalds1da177e2005-04-16 15:20:36 -07003914 if (cfq_slab_setup())
3915 return -ENOMEM;
3916
Adrian Bunk2fdd82b2007-12-12 18:51:56 +01003917 elv_register(&iosched_cfq);
Vivek Goyal3e252062009-12-04 10:36:42 -05003918 blkio_policy_register(&blkio_policy_cfq);
Linus Torvalds1da177e2005-04-16 15:20:36 -07003919
Adrian Bunk2fdd82b2007-12-12 18:51:56 +01003920 return 0;
Linus Torvalds1da177e2005-04-16 15:20:36 -07003921}
3922
3923static void __exit cfq_exit(void)
3924{
Peter Zijlstra6e9a4732006-09-30 23:28:10 -07003925 DECLARE_COMPLETION_ONSTACK(all_gone);
Vivek Goyal3e252062009-12-04 10:36:42 -05003926 blkio_policy_unregister(&blkio_policy_cfq);
Linus Torvalds1da177e2005-04-16 15:20:36 -07003927 elv_unregister(&iosched_cfq);
Al Viro334e94d2006-03-18 15:05:53 -05003928 ioc_gone = &all_gone;
OGAWA Hirofumifba82272006-04-18 09:44:06 +02003929 /* ioc_gone's update must be visible before reading ioc_count */
3930 smp_wmb();
Jens Axboed6de8be2008-05-28 14:46:59 +02003931
3932 /*
3933 * this also protects us from entering cfq_slab_kill() with
3934 * pending RCU callbacks
3935 */
Tejun Heo245b2e72009-06-24 15:13:48 +09003936 if (elv_ioc_count_read(cfq_ioc_count))
Jens Axboe9a11b4e2008-05-29 09:32:08 +02003937 wait_for_completion(&all_gone);
Christoph Hellwig83521d32005-10-30 15:01:39 -08003938 cfq_slab_kill();
Linus Torvalds1da177e2005-04-16 15:20:36 -07003939}
3940
3941module_init(cfq_init);
3942module_exit(cfq_exit);
3943
3944MODULE_AUTHOR("Jens Axboe");
3945MODULE_LICENSE("GPL");
3946MODULE_DESCRIPTION("Completely Fair Queueing IO scheduler");