blob: ee130f14d1fc9228214fb7d0acbd3d4f4a85acdd [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>
Al Viro1cc9be62006-03-18 12:29:52 -050010#include <linux/blkdev.h>
11#include <linux/elevator.h>
Randy Dunlapad5ebd22009-11-11 13:47:45 +010012#include <linux/jiffies.h>
Linus Torvalds1da177e2005-04-16 15:20:36 -070013#include <linux/rbtree.h>
Jens Axboe22e2c502005-06-27 10:55:12 +020014#include <linux/ioprio.h>
Jens Axboe7b679132008-05-30 12:23:07 +020015#include <linux/blktrace_api.h>
Vivek Goyal25bc6b02009-12-03 12:59:43 -050016#include "blk-cgroup.h"
Linus Torvalds1da177e2005-04-16 15:20:36 -070017
18/*
19 * tunables
20 */
Jens Axboefe094d92008-01-31 13:08:54 +010021/* max queue in one round of service */
22static const int cfq_quantum = 4;
Arjan van de Ven64100092006-01-06 09:46:02 +010023static const int cfq_fifo_expire[2] = { HZ / 4, HZ / 8 };
Jens Axboefe094d92008-01-31 13:08:54 +010024/* maximum backwards seek, in KiB */
25static const int cfq_back_max = 16 * 1024;
26/* penalty of a backwards seek */
27static const int cfq_back_penalty = 2;
Arjan van de Ven64100092006-01-06 09:46:02 +010028static const int cfq_slice_sync = HZ / 10;
Jens Axboe3b181522005-06-27 10:56:24 +020029static int cfq_slice_async = HZ / 25;
Arjan van de Ven64100092006-01-06 09:46:02 +010030static const int cfq_slice_async_rq = 2;
Jens Axboecaaa5f92006-06-16 11:23:00 +020031static int cfq_slice_idle = HZ / 125;
Corrado Zoccolo5db5d642009-10-26 22:44:04 +010032static const int cfq_target_latency = HZ * 3/10; /* 300 ms */
33static const int cfq_hist_divisor = 4;
Jens Axboe22e2c502005-06-27 10:55:12 +020034
Jens Axboed9e76202007-04-20 14:27:50 +020035/*
Jens Axboe08717142008-01-28 11:38:15 +010036 * offset from end of service tree
Jens Axboed9e76202007-04-20 14:27:50 +020037 */
Jens Axboe08717142008-01-28 11:38:15 +010038#define CFQ_IDLE_DELAY (HZ / 5)
Jens Axboed9e76202007-04-20 14:27:50 +020039
40/*
41 * below this threshold, we consider thinktime immediate
42 */
43#define CFQ_MIN_TT (2)
44
Jeff Moyere6c5bc72009-10-23 17:14:52 -040045/*
46 * Allow merged cfqqs to perform this amount of seeky I/O before
47 * deciding to break the queues up again.
48 */
49#define CFQQ_COOP_TOUT (HZ)
50
Jens Axboe22e2c502005-06-27 10:55:12 +020051#define CFQ_SLICE_SCALE (5)
Aaron Carroll45333d52008-08-26 15:52:36 +020052#define CFQ_HW_QUEUE_MIN (5)
Vivek Goyal25bc6b02009-12-03 12:59:43 -050053#define CFQ_SERVICE_SHIFT 12
Jens Axboe22e2c502005-06-27 10:55:12 +020054
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;
Vivek Goyal1fa8f6d2009-12-03 12:59:41 -050083 u64 min_vdisktime;
Vivek Goyal25bc6b02009-12-03 12:59:43 -050084 struct rb_node *active;
Vivek Goyal58ff82f2009-12-03 12:59:44 -050085 unsigned total_weight;
Jens Axboecc09e292007-04-26 12:53:50 +020086};
Vivek Goyal1fa8f6d2009-12-03 12:59:41 -050087#define CFQ_RB_ROOT (struct cfq_rb_root) { RB_ROOT, NULL, 0, 0, }
Jens Axboecc09e292007-04-26 12:53:50 +020088
89/*
Jens Axboe6118b702009-06-30 09:34:12 +020090 * Per process-grouping structure
91 */
92struct cfq_queue {
93 /* reference count */
94 atomic_t ref;
95 /* various state flags, see below */
96 unsigned int flags;
97 /* parent cfq_data */
98 struct cfq_data *cfqd;
99 /* service_tree member */
100 struct rb_node rb_node;
101 /* service_tree key */
102 unsigned long rb_key;
103 /* prio tree member */
104 struct rb_node p_node;
105 /* prio tree root we belong to, if any */
106 struct rb_root *p_root;
107 /* sorted list of pending requests */
108 struct rb_root sort_list;
109 /* if fifo isn't expired, next request to serve */
110 struct request *next_rq;
111 /* requests queued in sort_list */
112 int queued[2];
113 /* currently allocated requests */
114 int allocated[2];
115 /* fifo list of requests in sort_list */
116 struct list_head fifo;
117
Vivek Goyaldae739e2009-12-03 12:59:45 -0500118 /* time when queue got scheduled in to dispatch first request. */
119 unsigned long dispatch_start;
Vivek Goyalf75edf22009-12-03 12:59:53 -0500120 unsigned int allocated_slice;
Vivek Goyaldae739e2009-12-03 12:59:45 -0500121 /* time when first request from queue completed and slice started. */
122 unsigned long slice_start;
Jens Axboe6118b702009-06-30 09:34:12 +0200123 unsigned long slice_end;
124 long slice_resid;
125 unsigned int slice_dispatch;
126
127 /* pending metadata requests */
128 int meta_pending;
129 /* number of requests that are on the dispatch list or inside driver */
130 int dispatched;
131
132 /* io prio of this group */
133 unsigned short ioprio, org_ioprio;
134 unsigned short ioprio_class, org_ioprio_class;
135
Jeff Moyerb2c18e12009-10-23 17:14:49 -0400136 unsigned int seek_samples;
137 u64 seek_total;
138 sector_t seek_mean;
139 sector_t last_request_pos;
Jeff Moyere6c5bc72009-10-23 17:14:52 -0400140 unsigned long seeky_start;
Jeff Moyerb2c18e12009-10-23 17:14:49 -0400141
Jens Axboe6118b702009-06-30 09:34:12 +0200142 pid_t pid;
Jeff Moyerdf5fe3e2009-10-23 17:14:50 -0400143
Corrado Zoccoloaa6f6a32009-10-26 22:44:33 +0100144 struct cfq_rb_root *service_tree;
Jeff Moyerdf5fe3e2009-10-23 17:14:50 -0400145 struct cfq_queue *new_cfqq;
Vivek Goyalcdb16e82009-12-03 12:59:38 -0500146 struct cfq_group *cfqg;
Vivek Goyalae30c282009-12-03 12:59:55 -0500147 struct cfq_group *orig_cfqg;
Vivek Goyal22084192009-12-03 12:59:49 -0500148 /* Sectors dispatched in current dispatch round */
149 unsigned long nr_sectors;
Jens Axboe6118b702009-06-30 09:34:12 +0200150};
151
152/*
Corrado Zoccolo718eee02009-10-26 22:45:29 +0100153 * First index in the service_trees.
Corrado Zoccoloc0324a02009-10-27 19:16:03 +0100154 * IDLE is handled separately, so it has negative index
155 */
156enum wl_prio_t {
Corrado Zoccoloc0324a02009-10-27 19:16:03 +0100157 BE_WORKLOAD = 0,
Vivek Goyal615f0252009-12-03 12:59:39 -0500158 RT_WORKLOAD = 1,
159 IDLE_WORKLOAD = 2,
Corrado Zoccoloc0324a02009-10-27 19:16:03 +0100160};
161
162/*
Corrado Zoccolo718eee02009-10-26 22:45:29 +0100163 * Second index in the service_trees.
164 */
165enum wl_type_t {
166 ASYNC_WORKLOAD = 0,
167 SYNC_NOIDLE_WORKLOAD = 1,
168 SYNC_WORKLOAD = 2
169};
170
Vivek Goyalcdb16e82009-12-03 12:59:38 -0500171/* This is per cgroup per device grouping structure */
172struct cfq_group {
Vivek Goyal1fa8f6d2009-12-03 12:59:41 -0500173 /* group service_tree member */
174 struct rb_node rb_node;
175
176 /* group service_tree key */
177 u64 vdisktime;
Vivek Goyal25bc6b02009-12-03 12:59:43 -0500178 unsigned int weight;
Vivek Goyal1fa8f6d2009-12-03 12:59:41 -0500179 bool on_st;
180
181 /* number of cfqq currently on this group */
182 int nr_cfqq;
183
Vivek Goyal58ff82f2009-12-03 12:59:44 -0500184 /* Per group busy queus average. Useful for workload slice calc. */
185 unsigned int busy_queues_avg[2];
Jens Axboe22e2c502005-06-27 10:55:12 +0200186 /*
Corrado Zoccoloc0324a02009-10-27 19:16:03 +0100187 * rr lists of queues with requests, onle rr for each priority class.
188 * Counts are embedded in the cfq_rb_root
Jens Axboe22e2c502005-06-27 10:55:12 +0200189 */
Corrado Zoccolo718eee02009-10-26 22:45:29 +0100190 struct cfq_rb_root service_trees[2][3];
Corrado Zoccoloc0324a02009-10-27 19:16:03 +0100191 struct cfq_rb_root service_tree_idle;
Vivek Goyaldae739e2009-12-03 12:59:45 -0500192
193 unsigned long saved_workload_slice;
194 enum wl_type_t saved_workload;
195 enum wl_prio_t saved_serving_prio;
Vivek Goyal25fb5162009-12-03 12:59:46 -0500196 struct blkio_group blkg;
197#ifdef CONFIG_CFQ_GROUP_IOSCHED
198 struct hlist_node cfqd_node;
Vivek Goyalb1c35762009-12-03 12:59:47 -0500199 atomic_t ref;
Vivek Goyal25fb5162009-12-03 12:59:46 -0500200#endif
Vivek Goyalcdb16e82009-12-03 12:59:38 -0500201};
202
203/*
204 * Per block device queue structure
205 */
206struct cfq_data {
207 struct request_queue *queue;
Vivek Goyal1fa8f6d2009-12-03 12:59:41 -0500208 /* Root service tree for cfq_groups */
209 struct cfq_rb_root grp_service_tree;
Vivek Goyalcdb16e82009-12-03 12:59:38 -0500210 struct cfq_group root_group;
211
Corrado Zoccoloc0324a02009-10-27 19:16:03 +0100212 /*
213 * The priority currently being served
214 */
215 enum wl_prio_t serving_prio;
Corrado Zoccolo718eee02009-10-26 22:45:29 +0100216 enum wl_type_t serving_type;
217 unsigned long workload_expires;
Vivek Goyalcdb16e82009-12-03 12:59:38 -0500218 struct cfq_group *serving_group;
Corrado Zoccolo8e550632009-11-26 10:02:58 +0100219 bool noidle_tree_requires_idle;
Jens Axboea36e71f2009-04-15 12:15:11 +0200220
221 /*
222 * Each priority tree is sorted by next_request position. These
223 * trees are used when determining if two or more queues are
224 * interleaving requests (see cfq_close_cooperator).
225 */
226 struct rb_root prio_trees[CFQ_PRIO_LISTS];
227
Jens Axboe22e2c502005-06-27 10:55:12 +0200228 unsigned int busy_queues;
229
Jens Axboe5ad531d2009-07-03 12:57:48 +0200230 int rq_in_driver[2];
Jens Axboe3ed9a292007-04-23 08:33:33 +0200231 int sync_flight;
Aaron Carroll45333d52008-08-26 15:52:36 +0200232
233 /*
234 * queue-depth detection
235 */
236 int rq_queued;
Jens Axboe25776e32006-06-01 10:12:26 +0200237 int hw_tag;
Corrado Zoccoloe459dd02009-11-26 10:02:57 +0100238 /*
239 * hw_tag can be
240 * -1 => indeterminate, (cfq will behave as if NCQ is present, to allow better detection)
241 * 1 => NCQ is present (hw_tag_est_depth is the estimated max depth)
242 * 0 => no NCQ
243 */
244 int hw_tag_est_depth;
245 unsigned int hw_tag_samples;
Jens Axboe22e2c502005-06-27 10:55:12 +0200246
247 /*
Jens Axboe22e2c502005-06-27 10:55:12 +0200248 * idle window management
249 */
250 struct timer_list idle_slice_timer;
Jens Axboe23e018a2009-10-05 08:52:35 +0200251 struct work_struct unplug_work;
Jens Axboe22e2c502005-06-27 10:55:12 +0200252
253 struct cfq_queue *active_queue;
254 struct cfq_io_context *active_cic;
Jens Axboe22e2c502005-06-27 10:55:12 +0200255
Vasily Tarasovc2dea2d2007-07-20 10:06:38 +0200256 /*
257 * async queue for each priority case
258 */
259 struct cfq_queue *async_cfqq[2][IOPRIO_BE_NR];
260 struct cfq_queue *async_idle_cfqq;
Jens Axboe15c31be2007-07-10 13:43:25 +0200261
Jens Axboe6d048f52007-04-25 12:44:27 +0200262 sector_t last_position;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700263
Linus Torvalds1da177e2005-04-16 15:20:36 -0700264 /*
265 * tunables, see top of file
266 */
267 unsigned int cfq_quantum;
Jens Axboe22e2c502005-06-27 10:55:12 +0200268 unsigned int cfq_fifo_expire[2];
Linus Torvalds1da177e2005-04-16 15:20:36 -0700269 unsigned int cfq_back_penalty;
270 unsigned int cfq_back_max;
Jens Axboe22e2c502005-06-27 10:55:12 +0200271 unsigned int cfq_slice[2];
272 unsigned int cfq_slice_async_rq;
273 unsigned int cfq_slice_idle;
Jens Axboe963b72f2009-10-03 19:42:18 +0200274 unsigned int cfq_latency;
Vivek Goyalae30c282009-12-03 12:59:55 -0500275 unsigned int cfq_group_isolation;
Al Virod9ff4182006-03-18 13:51:22 -0500276
277 struct list_head cic_list;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700278
Jens Axboe6118b702009-06-30 09:34:12 +0200279 /*
280 * Fallback dummy cfqq for extreme OOM conditions
281 */
282 struct cfq_queue oom_cfqq;
Vivek Goyal365722b2009-10-03 15:21:27 +0200283
Corrado Zoccolo573412b2009-12-06 11:48:52 +0100284 unsigned long last_delayed_sync;
Vivek Goyal25fb5162009-12-03 12:59:46 -0500285
286 /* List of cfq groups being managed on this device*/
287 struct hlist_head cfqg_list;
Jens Axboebb729bc2009-12-06 09:54:19 +0100288 struct rcu_head rcu;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700289};
290
Vivek Goyal25fb5162009-12-03 12:59:46 -0500291static struct cfq_group *cfq_get_next_cfqg(struct cfq_data *cfqd);
292
Vivek Goyalcdb16e82009-12-03 12:59:38 -0500293static struct cfq_rb_root *service_tree_for(struct cfq_group *cfqg,
294 enum wl_prio_t prio,
Vivek Goyal65b32a52009-12-16 17:52:59 -0500295 enum wl_type_t type)
Corrado Zoccoloc0324a02009-10-27 19:16:03 +0100296{
Vivek Goyal1fa8f6d2009-12-03 12:59:41 -0500297 if (!cfqg)
298 return NULL;
299
Corrado Zoccoloc0324a02009-10-27 19:16:03 +0100300 if (prio == IDLE_WORKLOAD)
Vivek Goyalcdb16e82009-12-03 12:59:38 -0500301 return &cfqg->service_tree_idle;
Corrado Zoccoloc0324a02009-10-27 19:16:03 +0100302
Vivek Goyalcdb16e82009-12-03 12:59:38 -0500303 return &cfqg->service_trees[prio][type];
Corrado Zoccoloc0324a02009-10-27 19:16:03 +0100304}
305
Jens Axboe3b181522005-06-27 10:56:24 +0200306enum cfqq_state_flags {
Jens Axboeb0b8d7492007-01-19 11:35:30 +1100307 CFQ_CFQQ_FLAG_on_rr = 0, /* on round-robin busy list */
308 CFQ_CFQQ_FLAG_wait_request, /* waiting for a request */
Jens Axboeb0291952009-04-07 11:38:31 +0200309 CFQ_CFQQ_FLAG_must_dispatch, /* must be allowed a dispatch */
Jens Axboeb0b8d7492007-01-19 11:35:30 +1100310 CFQ_CFQQ_FLAG_must_alloc_slice, /* per-slice must_alloc flag */
Jens Axboeb0b8d7492007-01-19 11:35:30 +1100311 CFQ_CFQQ_FLAG_fifo_expire, /* FIFO checked in this slice */
312 CFQ_CFQQ_FLAG_idle_window, /* slice idling enabled */
313 CFQ_CFQQ_FLAG_prio_changed, /* task priority has changed */
Jens Axboe44f7c162007-01-19 11:51:58 +1100314 CFQ_CFQQ_FLAG_slice_new, /* no requests dispatched in slice */
Vasily Tarasov91fac312007-04-25 12:29:51 +0200315 CFQ_CFQQ_FLAG_sync, /* synchronous queue */
Jeff Moyerb3b6d042009-10-23 17:14:51 -0400316 CFQ_CFQQ_FLAG_coop, /* cfqq is shared */
Corrado Zoccolo76280af2009-11-26 10:02:58 +0100317 CFQ_CFQQ_FLAG_deep, /* sync cfqq experienced large depth */
Vivek Goyalf75edf22009-12-03 12:59:53 -0500318 CFQ_CFQQ_FLAG_wait_busy, /* Waiting for next request */
Jens Axboe3b181522005-06-27 10:56:24 +0200319};
320
321#define CFQ_CFQQ_FNS(name) \
322static inline void cfq_mark_cfqq_##name(struct cfq_queue *cfqq) \
323{ \
Jens Axboefe094d92008-01-31 13:08:54 +0100324 (cfqq)->flags |= (1 << CFQ_CFQQ_FLAG_##name); \
Jens Axboe3b181522005-06-27 10:56:24 +0200325} \
326static inline void cfq_clear_cfqq_##name(struct cfq_queue *cfqq) \
327{ \
Jens Axboefe094d92008-01-31 13:08:54 +0100328 (cfqq)->flags &= ~(1 << CFQ_CFQQ_FLAG_##name); \
Jens Axboe3b181522005-06-27 10:56:24 +0200329} \
330static inline int cfq_cfqq_##name(const struct cfq_queue *cfqq) \
331{ \
Jens Axboefe094d92008-01-31 13:08:54 +0100332 return ((cfqq)->flags & (1 << CFQ_CFQQ_FLAG_##name)) != 0; \
Jens Axboe3b181522005-06-27 10:56:24 +0200333}
334
335CFQ_CFQQ_FNS(on_rr);
336CFQ_CFQQ_FNS(wait_request);
Jens Axboeb0291952009-04-07 11:38:31 +0200337CFQ_CFQQ_FNS(must_dispatch);
Jens Axboe3b181522005-06-27 10:56:24 +0200338CFQ_CFQQ_FNS(must_alloc_slice);
Jens Axboe3b181522005-06-27 10:56:24 +0200339CFQ_CFQQ_FNS(fifo_expire);
340CFQ_CFQQ_FNS(idle_window);
341CFQ_CFQQ_FNS(prio_changed);
Jens Axboe44f7c162007-01-19 11:51:58 +1100342CFQ_CFQQ_FNS(slice_new);
Vasily Tarasov91fac312007-04-25 12:29:51 +0200343CFQ_CFQQ_FNS(sync);
Jens Axboea36e71f2009-04-15 12:15:11 +0200344CFQ_CFQQ_FNS(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
Jens Axboe5ad531d2009-07-03 12:57:48 +0200422static inline int rq_in_driver(struct cfq_data *cfqd)
423{
424 return cfqd->rq_in_driver[0] + cfqd->rq_in_driver[1];
425}
426
Vasily Tarasov91fac312007-04-25 12:29:51 +0200427static inline struct cfq_queue *cic_to_cfqq(struct cfq_io_context *cic,
Jens Axboea6151c32009-10-07 20:02:57 +0200428 bool is_sync)
Vasily Tarasov91fac312007-04-25 12:29:51 +0200429{
Jens Axboea6151c32009-10-07 20:02:57 +0200430 return cic->cfqq[is_sync];
Vasily Tarasov91fac312007-04-25 12:29:51 +0200431}
432
433static inline void cic_set_cfqq(struct cfq_io_context *cic,
Jens Axboea6151c32009-10-07 20:02:57 +0200434 struct cfq_queue *cfqq, bool is_sync)
Vasily Tarasov91fac312007-04-25 12:29:51 +0200435{
Jens Axboea6151c32009-10-07 20:02:57 +0200436 cic->cfqq[is_sync] = cfqq;
Vasily Tarasov91fac312007-04-25 12:29:51 +0200437}
438
439/*
440 * We regard a request as SYNC, if it's either a read or has the SYNC bit
441 * set (in which case it could also be direct WRITE).
442 */
Jens Axboea6151c32009-10-07 20:02:57 +0200443static inline bool cfq_bio_sync(struct bio *bio)
Vasily Tarasov91fac312007-04-25 12:29:51 +0200444{
Jens Axboea6151c32009-10-07 20:02:57 +0200445 return bio_data_dir(bio) == READ || bio_rw_flagged(bio, BIO_RW_SYNCIO);
Vasily Tarasov91fac312007-04-25 12:29:51 +0200446}
Linus Torvalds1da177e2005-04-16 15:20:36 -0700447
Linus Torvalds1da177e2005-04-16 15:20:36 -0700448/*
Andrew Morton99f95e52005-06-27 20:14:05 -0700449 * scheduler run of queue, if there are requests pending and no one in the
450 * driver that will restart queueing
451 */
Jens Axboe23e018a2009-10-05 08:52:35 +0200452static inline void cfq_schedule_dispatch(struct cfq_data *cfqd)
Andrew Morton99f95e52005-06-27 20:14:05 -0700453{
Jens Axboe7b679132008-05-30 12:23:07 +0200454 if (cfqd->busy_queues) {
455 cfq_log(cfqd, "schedule dispatch");
Jens Axboe23e018a2009-10-05 08:52:35 +0200456 kblockd_schedule_work(cfqd->queue, &cfqd->unplug_work);
Jens Axboe7b679132008-05-30 12:23:07 +0200457 }
Andrew Morton99f95e52005-06-27 20:14:05 -0700458}
459
Jens Axboe165125e2007-07-24 09:28:11 +0200460static int cfq_queue_empty(struct request_queue *q)
Andrew Morton99f95e52005-06-27 20:14:05 -0700461{
462 struct cfq_data *cfqd = q->elevator->elevator_data;
463
Vivek Goyalf04a6422009-12-03 12:59:40 -0500464 return !cfqd->rq_queued;
Andrew Morton99f95e52005-06-27 20:14:05 -0700465}
466
Linus Torvalds1da177e2005-04-16 15:20:36 -0700467/*
Jens Axboe44f7c162007-01-19 11:51:58 +1100468 * Scale schedule slice based on io priority. Use the sync time slice only
469 * if a queue is marked sync and has sync io queued. A sync queue with async
470 * io only, should not get full sync slice length.
471 */
Jens Axboea6151c32009-10-07 20:02:57 +0200472static inline int cfq_prio_slice(struct cfq_data *cfqd, bool sync,
Jens Axboed9e76202007-04-20 14:27:50 +0200473 unsigned short prio)
474{
475 const int base_slice = cfqd->cfq_slice[sync];
476
477 WARN_ON(prio >= IOPRIO_BE_NR);
478
479 return base_slice + (base_slice/CFQ_SLICE_SCALE * (4 - prio));
480}
481
Jens Axboe44f7c162007-01-19 11:51:58 +1100482static inline int
483cfq_prio_to_slice(struct cfq_data *cfqd, struct cfq_queue *cfqq)
484{
Jens Axboed9e76202007-04-20 14:27:50 +0200485 return cfq_prio_slice(cfqd, cfq_cfqq_sync(cfqq), cfqq->ioprio);
Jens Axboe44f7c162007-01-19 11:51:58 +1100486}
487
Vivek Goyal25bc6b02009-12-03 12:59:43 -0500488static inline u64 cfq_scale_slice(unsigned long delta, struct cfq_group *cfqg)
489{
490 u64 d = delta << CFQ_SERVICE_SHIFT;
491
492 d = d * BLKIO_WEIGHT_DEFAULT;
493 do_div(d, cfqg->weight);
494 return d;
495}
496
497static inline u64 max_vdisktime(u64 min_vdisktime, u64 vdisktime)
498{
499 s64 delta = (s64)(vdisktime - min_vdisktime);
500 if (delta > 0)
501 min_vdisktime = vdisktime;
502
503 return min_vdisktime;
504}
505
506static inline u64 min_vdisktime(u64 min_vdisktime, u64 vdisktime)
507{
508 s64 delta = (s64)(vdisktime - min_vdisktime);
509 if (delta < 0)
510 min_vdisktime = vdisktime;
511
512 return min_vdisktime;
513}
514
515static void update_min_vdisktime(struct cfq_rb_root *st)
516{
517 u64 vdisktime = st->min_vdisktime;
518 struct cfq_group *cfqg;
519
520 if (st->active) {
521 cfqg = rb_entry_cfqg(st->active);
522 vdisktime = cfqg->vdisktime;
523 }
524
525 if (st->left) {
526 cfqg = rb_entry_cfqg(st->left);
527 vdisktime = min_vdisktime(vdisktime, cfqg->vdisktime);
528 }
529
530 st->min_vdisktime = max_vdisktime(st->min_vdisktime, vdisktime);
531}
532
Corrado Zoccolo5db5d642009-10-26 22:44:04 +0100533/*
534 * get averaged number of queues of RT/BE priority.
535 * average is updated, with a formula that gives more weight to higher numbers,
536 * to quickly follows sudden increases and decrease slowly
537 */
538
Vivek Goyal58ff82f2009-12-03 12:59:44 -0500539static inline unsigned cfq_group_get_avg_queues(struct cfq_data *cfqd,
540 struct cfq_group *cfqg, bool rt)
Jens Axboe5869619c2009-10-28 09:27:07 +0100541{
Corrado Zoccolo5db5d642009-10-26 22:44:04 +0100542 unsigned min_q, max_q;
543 unsigned mult = cfq_hist_divisor - 1;
544 unsigned round = cfq_hist_divisor / 2;
Vivek Goyal58ff82f2009-12-03 12:59:44 -0500545 unsigned busy = cfq_group_busy_queues_wl(rt, cfqd, cfqg);
Corrado Zoccolo5db5d642009-10-26 22:44:04 +0100546
Vivek Goyal58ff82f2009-12-03 12:59:44 -0500547 min_q = min(cfqg->busy_queues_avg[rt], busy);
548 max_q = max(cfqg->busy_queues_avg[rt], busy);
549 cfqg->busy_queues_avg[rt] = (mult * max_q + min_q + round) /
Corrado Zoccolo5db5d642009-10-26 22:44:04 +0100550 cfq_hist_divisor;
Vivek Goyal58ff82f2009-12-03 12:59:44 -0500551 return cfqg->busy_queues_avg[rt];
552}
553
554static inline unsigned
555cfq_group_slice(struct cfq_data *cfqd, struct cfq_group *cfqg)
556{
557 struct cfq_rb_root *st = &cfqd->grp_service_tree;
558
559 return cfq_target_latency * cfqg->weight / st->total_weight;
Corrado Zoccolo5db5d642009-10-26 22:44:04 +0100560}
561
Jens Axboe44f7c162007-01-19 11:51:58 +1100562static inline void
563cfq_set_prio_slice(struct cfq_data *cfqd, struct cfq_queue *cfqq)
564{
Corrado Zoccolo5db5d642009-10-26 22:44:04 +0100565 unsigned slice = cfq_prio_to_slice(cfqd, cfqq);
566 if (cfqd->cfq_latency) {
Vivek Goyal58ff82f2009-12-03 12:59:44 -0500567 /*
568 * interested queues (we consider only the ones with the same
569 * priority class in the cfq group)
570 */
571 unsigned iq = cfq_group_get_avg_queues(cfqd, cfqq->cfqg,
572 cfq_class_rt(cfqq));
Corrado Zoccolo5db5d642009-10-26 22:44:04 +0100573 unsigned sync_slice = cfqd->cfq_slice[1];
574 unsigned expect_latency = sync_slice * iq;
Vivek Goyal58ff82f2009-12-03 12:59:44 -0500575 unsigned group_slice = cfq_group_slice(cfqd, cfqq->cfqg);
576
577 if (expect_latency > group_slice) {
Corrado Zoccolo5db5d642009-10-26 22:44:04 +0100578 unsigned base_low_slice = 2 * cfqd->cfq_slice_idle;
579 /* scale low_slice according to IO priority
580 * and sync vs async */
581 unsigned low_slice =
582 min(slice, base_low_slice * slice / sync_slice);
583 /* the adapted slice value is scaled to fit all iqs
584 * into the target latency */
Vivek Goyal58ff82f2009-12-03 12:59:44 -0500585 slice = max(slice * group_slice / expect_latency,
Corrado Zoccolo5db5d642009-10-26 22:44:04 +0100586 low_slice);
587 }
588 }
Vivek Goyaldae739e2009-12-03 12:59:45 -0500589 cfqq->slice_start = jiffies;
Corrado Zoccolo5db5d642009-10-26 22:44:04 +0100590 cfqq->slice_end = jiffies + slice;
Vivek Goyalf75edf22009-12-03 12:59:53 -0500591 cfqq->allocated_slice = slice;
Jens Axboe7b679132008-05-30 12:23:07 +0200592 cfq_log_cfqq(cfqd, cfqq, "set_slice=%lu", cfqq->slice_end - jiffies);
Jens Axboe44f7c162007-01-19 11:51:58 +1100593}
594
595/*
596 * We need to wrap this check in cfq_cfqq_slice_new(), since ->slice_end
597 * isn't valid until the first request from the dispatch is activated
598 * and the slice time set.
599 */
Jens Axboea6151c32009-10-07 20:02:57 +0200600static inline bool cfq_slice_used(struct cfq_queue *cfqq)
Jens Axboe44f7c162007-01-19 11:51:58 +1100601{
602 if (cfq_cfqq_slice_new(cfqq))
603 return 0;
604 if (time_before(jiffies, cfqq->slice_end))
605 return 0;
606
607 return 1;
608}
609
610/*
Jens Axboe5e705372006-07-13 12:39:25 +0200611 * Lifted from AS - choose which of rq1 and rq2 that is best served now.
Linus Torvalds1da177e2005-04-16 15:20:36 -0700612 * We choose the request that is closest to the head right now. Distance
Andreas Mohre8a99052006-03-28 08:59:49 +0200613 * behind the head is penalized and only allowed to a certain extent.
Linus Torvalds1da177e2005-04-16 15:20:36 -0700614 */
Jens Axboe5e705372006-07-13 12:39:25 +0200615static struct request *
Corrado Zoccolocf7c25c2009-11-08 17:16:46 +0100616cfq_choose_req(struct cfq_data *cfqd, struct request *rq1, struct request *rq2, sector_t last)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700617{
Corrado Zoccolocf7c25c2009-11-08 17:16:46 +0100618 sector_t s1, s2, d1 = 0, d2 = 0;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700619 unsigned long back_max;
Andreas Mohre8a99052006-03-28 08:59:49 +0200620#define CFQ_RQ1_WRAP 0x01 /* request 1 wraps */
621#define CFQ_RQ2_WRAP 0x02 /* request 2 wraps */
622 unsigned wrap = 0; /* bit mask: requests behind the disk head? */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700623
Jens Axboe5e705372006-07-13 12:39:25 +0200624 if (rq1 == NULL || rq1 == rq2)
625 return rq2;
626 if (rq2 == NULL)
627 return rq1;
Jens Axboe9c2c38a2005-08-24 14:57:54 +0200628
Jens Axboe5e705372006-07-13 12:39:25 +0200629 if (rq_is_sync(rq1) && !rq_is_sync(rq2))
630 return rq1;
631 else if (rq_is_sync(rq2) && !rq_is_sync(rq1))
632 return rq2;
Jens Axboe374f84a2006-07-23 01:42:19 +0200633 if (rq_is_meta(rq1) && !rq_is_meta(rq2))
634 return rq1;
635 else if (rq_is_meta(rq2) && !rq_is_meta(rq1))
636 return rq2;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700637
Tejun Heo83096eb2009-05-07 22:24:39 +0900638 s1 = blk_rq_pos(rq1);
639 s2 = blk_rq_pos(rq2);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700640
Linus Torvalds1da177e2005-04-16 15:20:36 -0700641 /*
642 * by definition, 1KiB is 2 sectors
643 */
644 back_max = cfqd->cfq_back_max * 2;
645
646 /*
647 * Strict one way elevator _except_ in the case where we allow
648 * short backward seeks which are biased as twice the cost of a
649 * similar forward seek.
650 */
651 if (s1 >= last)
652 d1 = s1 - last;
653 else if (s1 + back_max >= last)
654 d1 = (last - s1) * cfqd->cfq_back_penalty;
655 else
Andreas Mohre8a99052006-03-28 08:59:49 +0200656 wrap |= CFQ_RQ1_WRAP;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700657
658 if (s2 >= last)
659 d2 = s2 - last;
660 else if (s2 + back_max >= last)
661 d2 = (last - s2) * cfqd->cfq_back_penalty;
662 else
Andreas Mohre8a99052006-03-28 08:59:49 +0200663 wrap |= CFQ_RQ2_WRAP;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700664
665 /* Found required data */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700666
Andreas Mohre8a99052006-03-28 08:59:49 +0200667 /*
668 * By doing switch() on the bit mask "wrap" we avoid having to
669 * check two variables for all permutations: --> faster!
670 */
671 switch (wrap) {
Jens Axboe5e705372006-07-13 12:39:25 +0200672 case 0: /* common case for CFQ: rq1 and rq2 not wrapped */
Andreas Mohre8a99052006-03-28 08:59:49 +0200673 if (d1 < d2)
Jens Axboe5e705372006-07-13 12:39:25 +0200674 return rq1;
Andreas Mohre8a99052006-03-28 08:59:49 +0200675 else if (d2 < d1)
Jens Axboe5e705372006-07-13 12:39:25 +0200676 return rq2;
Andreas Mohre8a99052006-03-28 08:59:49 +0200677 else {
678 if (s1 >= s2)
Jens Axboe5e705372006-07-13 12:39:25 +0200679 return rq1;
Andreas Mohre8a99052006-03-28 08:59:49 +0200680 else
Jens Axboe5e705372006-07-13 12:39:25 +0200681 return rq2;
Andreas Mohre8a99052006-03-28 08:59:49 +0200682 }
683
684 case CFQ_RQ2_WRAP:
Jens Axboe5e705372006-07-13 12:39:25 +0200685 return rq1;
Andreas Mohre8a99052006-03-28 08:59:49 +0200686 case CFQ_RQ1_WRAP:
Jens Axboe5e705372006-07-13 12:39:25 +0200687 return rq2;
688 case (CFQ_RQ1_WRAP|CFQ_RQ2_WRAP): /* both rqs wrapped */
Andreas Mohre8a99052006-03-28 08:59:49 +0200689 default:
690 /*
691 * Since both rqs are wrapped,
692 * start with the one that's further behind head
693 * (--> only *one* back seek required),
694 * since back seek takes more time than forward.
695 */
696 if (s1 <= s2)
Jens Axboe5e705372006-07-13 12:39:25 +0200697 return rq1;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700698 else
Jens Axboe5e705372006-07-13 12:39:25 +0200699 return rq2;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700700 }
701}
702
Jens Axboe498d3aa22007-04-26 12:54:48 +0200703/*
704 * The below is leftmost cache rbtree addon
705 */
Jens Axboe08717142008-01-28 11:38:15 +0100706static struct cfq_queue *cfq_rb_first(struct cfq_rb_root *root)
Jens Axboecc09e292007-04-26 12:53:50 +0200707{
Vivek Goyal615f0252009-12-03 12:59:39 -0500708 /* Service tree is empty */
709 if (!root->count)
710 return NULL;
711
Jens Axboecc09e292007-04-26 12:53:50 +0200712 if (!root->left)
713 root->left = rb_first(&root->rb);
714
Jens Axboe08717142008-01-28 11:38:15 +0100715 if (root->left)
716 return rb_entry(root->left, struct cfq_queue, rb_node);
717
718 return NULL;
Jens Axboecc09e292007-04-26 12:53:50 +0200719}
720
Vivek Goyal1fa8f6d2009-12-03 12:59:41 -0500721static struct cfq_group *cfq_rb_first_group(struct cfq_rb_root *root)
722{
723 if (!root->left)
724 root->left = rb_first(&root->rb);
725
726 if (root->left)
727 return rb_entry_cfqg(root->left);
728
729 return NULL;
730}
731
Jens Axboea36e71f2009-04-15 12:15:11 +0200732static void rb_erase_init(struct rb_node *n, struct rb_root *root)
733{
734 rb_erase(n, root);
735 RB_CLEAR_NODE(n);
736}
737
Jens Axboecc09e292007-04-26 12:53:50 +0200738static void cfq_rb_erase(struct rb_node *n, struct cfq_rb_root *root)
739{
740 if (root->left == n)
741 root->left = NULL;
Jens Axboea36e71f2009-04-15 12:15:11 +0200742 rb_erase_init(n, &root->rb);
Corrado Zoccoloaa6f6a32009-10-26 22:44:33 +0100743 --root->count;
Jens Axboecc09e292007-04-26 12:53:50 +0200744}
745
Linus Torvalds1da177e2005-04-16 15:20:36 -0700746/*
747 * would be nice to take fifo expire time into account as well
748 */
Jens Axboe5e705372006-07-13 12:39:25 +0200749static struct request *
750cfq_find_next_rq(struct cfq_data *cfqd, struct cfq_queue *cfqq,
751 struct request *last)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700752{
Jens Axboe21183b02006-07-13 12:33:14 +0200753 struct rb_node *rbnext = rb_next(&last->rb_node);
754 struct rb_node *rbprev = rb_prev(&last->rb_node);
Jens Axboe5e705372006-07-13 12:39:25 +0200755 struct request *next = NULL, *prev = NULL;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700756
Jens Axboe21183b02006-07-13 12:33:14 +0200757 BUG_ON(RB_EMPTY_NODE(&last->rb_node));
Linus Torvalds1da177e2005-04-16 15:20:36 -0700758
759 if (rbprev)
Jens Axboe5e705372006-07-13 12:39:25 +0200760 prev = rb_entry_rq(rbprev);
Jens Axboe21183b02006-07-13 12:33:14 +0200761
Linus Torvalds1da177e2005-04-16 15:20:36 -0700762 if (rbnext)
Jens Axboe5e705372006-07-13 12:39:25 +0200763 next = rb_entry_rq(rbnext);
Jens Axboe21183b02006-07-13 12:33:14 +0200764 else {
765 rbnext = rb_first(&cfqq->sort_list);
766 if (rbnext && rbnext != &last->rb_node)
Jens Axboe5e705372006-07-13 12:39:25 +0200767 next = rb_entry_rq(rbnext);
Jens Axboe21183b02006-07-13 12:33:14 +0200768 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700769
Corrado Zoccolocf7c25c2009-11-08 17:16:46 +0100770 return cfq_choose_req(cfqd, next, prev, blk_rq_pos(last));
Linus Torvalds1da177e2005-04-16 15:20:36 -0700771}
772
Jens Axboed9e76202007-04-20 14:27:50 +0200773static unsigned long cfq_slice_offset(struct cfq_data *cfqd,
774 struct cfq_queue *cfqq)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700775{
Jens Axboed9e76202007-04-20 14:27:50 +0200776 /*
777 * just an approximation, should be ok.
778 */
Vivek Goyalcdb16e82009-12-03 12:59:38 -0500779 return (cfqq->cfqg->nr_cfqq - 1) * (cfq_prio_slice(cfqd, 1, 0) -
Jens Axboe464191c2009-11-30 09:38:13 +0100780 cfq_prio_slice(cfqd, cfq_cfqq_sync(cfqq), cfqq->ioprio));
Jens Axboed9e76202007-04-20 14:27:50 +0200781}
Linus Torvalds1da177e2005-04-16 15:20:36 -0700782
Vivek Goyal1fa8f6d2009-12-03 12:59:41 -0500783static inline s64
784cfqg_key(struct cfq_rb_root *st, struct cfq_group *cfqg)
785{
786 return cfqg->vdisktime - st->min_vdisktime;
787}
788
789static void
790__cfq_group_service_tree_add(struct cfq_rb_root *st, struct cfq_group *cfqg)
791{
792 struct rb_node **node = &st->rb.rb_node;
793 struct rb_node *parent = NULL;
794 struct cfq_group *__cfqg;
795 s64 key = cfqg_key(st, cfqg);
796 int left = 1;
797
798 while (*node != NULL) {
799 parent = *node;
800 __cfqg = rb_entry_cfqg(parent);
801
802 if (key < cfqg_key(st, __cfqg))
803 node = &parent->rb_left;
804 else {
805 node = &parent->rb_right;
806 left = 0;
807 }
808 }
809
810 if (left)
811 st->left = &cfqg->rb_node;
812
813 rb_link_node(&cfqg->rb_node, parent, node);
814 rb_insert_color(&cfqg->rb_node, &st->rb);
815}
816
817static void
818cfq_group_service_tree_add(struct cfq_data *cfqd, struct cfq_group *cfqg)
819{
820 struct cfq_rb_root *st = &cfqd->grp_service_tree;
821 struct cfq_group *__cfqg;
822 struct rb_node *n;
823
824 cfqg->nr_cfqq++;
825 if (cfqg->on_st)
826 return;
827
828 /*
829 * Currently put the group at the end. Later implement something
830 * so that groups get lesser vtime based on their weights, so that
831 * if group does not loose all if it was not continously backlogged.
832 */
833 n = rb_last(&st->rb);
834 if (n) {
835 __cfqg = rb_entry_cfqg(n);
836 cfqg->vdisktime = __cfqg->vdisktime + CFQ_IDLE_DELAY;
837 } else
838 cfqg->vdisktime = st->min_vdisktime;
839
840 __cfq_group_service_tree_add(st, cfqg);
841 cfqg->on_st = true;
Vivek Goyal58ff82f2009-12-03 12:59:44 -0500842 st->total_weight += cfqg->weight;
Vivek Goyal1fa8f6d2009-12-03 12:59:41 -0500843}
844
845static void
846cfq_group_service_tree_del(struct cfq_data *cfqd, struct cfq_group *cfqg)
847{
848 struct cfq_rb_root *st = &cfqd->grp_service_tree;
849
Vivek Goyal25bc6b02009-12-03 12:59:43 -0500850 if (st->active == &cfqg->rb_node)
851 st->active = NULL;
852
Vivek Goyal1fa8f6d2009-12-03 12:59:41 -0500853 BUG_ON(cfqg->nr_cfqq < 1);
854 cfqg->nr_cfqq--;
Vivek Goyal25bc6b02009-12-03 12:59:43 -0500855
Vivek Goyal1fa8f6d2009-12-03 12:59:41 -0500856 /* If there are other cfq queues under this group, don't delete it */
857 if (cfqg->nr_cfqq)
858 return;
859
Vivek Goyal2868ef72009-12-03 12:59:48 -0500860 cfq_log_cfqg(cfqd, cfqg, "del_from_rr group");
Vivek Goyal1fa8f6d2009-12-03 12:59:41 -0500861 cfqg->on_st = false;
Vivek Goyal58ff82f2009-12-03 12:59:44 -0500862 st->total_weight -= cfqg->weight;
Vivek Goyal1fa8f6d2009-12-03 12:59:41 -0500863 if (!RB_EMPTY_NODE(&cfqg->rb_node))
864 cfq_rb_erase(&cfqg->rb_node, st);
Vivek Goyaldae739e2009-12-03 12:59:45 -0500865 cfqg->saved_workload_slice = 0;
Vivek Goyal22084192009-12-03 12:59:49 -0500866 blkiocg_update_blkio_group_dequeue_stats(&cfqg->blkg, 1);
Vivek Goyaldae739e2009-12-03 12:59:45 -0500867}
868
869static inline unsigned int cfq_cfqq_slice_usage(struct cfq_queue *cfqq)
870{
Vivek Goyalf75edf22009-12-03 12:59:53 -0500871 unsigned int slice_used;
Vivek Goyaldae739e2009-12-03 12:59:45 -0500872
873 /*
874 * Queue got expired before even a single request completed or
875 * got expired immediately after first request completion.
876 */
877 if (!cfqq->slice_start || cfqq->slice_start == jiffies) {
878 /*
879 * Also charge the seek time incurred to the group, otherwise
880 * if there are mutiple queues in the group, each can dispatch
881 * a single request on seeky media and cause lots of seek time
882 * and group will never know it.
883 */
884 slice_used = max_t(unsigned, (jiffies - cfqq->dispatch_start),
885 1);
886 } else {
887 slice_used = jiffies - cfqq->slice_start;
Vivek Goyalf75edf22009-12-03 12:59:53 -0500888 if (slice_used > cfqq->allocated_slice)
889 slice_used = cfqq->allocated_slice;
Vivek Goyaldae739e2009-12-03 12:59:45 -0500890 }
891
Vivek Goyal22084192009-12-03 12:59:49 -0500892 cfq_log_cfqq(cfqq->cfqd, cfqq, "sl_used=%u sect=%lu", slice_used,
893 cfqq->nr_sectors);
Vivek Goyaldae739e2009-12-03 12:59:45 -0500894 return slice_used;
895}
896
897static void cfq_group_served(struct cfq_data *cfqd, struct cfq_group *cfqg,
898 struct cfq_queue *cfqq)
899{
900 struct cfq_rb_root *st = &cfqd->grp_service_tree;
Vivek Goyalf26bd1f2009-12-03 12:59:54 -0500901 unsigned int used_sl, charge_sl;
902 int nr_sync = cfqg->nr_cfqq - cfqg_busy_async_queues(cfqd, cfqg)
903 - cfqg->service_tree_idle.count;
Vivek Goyaldae739e2009-12-03 12:59:45 -0500904
Vivek Goyalf26bd1f2009-12-03 12:59:54 -0500905 BUG_ON(nr_sync < 0);
906 used_sl = charge_sl = cfq_cfqq_slice_usage(cfqq);
907
908 if (!cfq_cfqq_sync(cfqq) && !nr_sync)
909 charge_sl = cfqq->allocated_slice;
Vivek Goyaldae739e2009-12-03 12:59:45 -0500910
911 /* Can't update vdisktime while group is on service tree */
912 cfq_rb_erase(&cfqg->rb_node, st);
Vivek Goyalf26bd1f2009-12-03 12:59:54 -0500913 cfqg->vdisktime += cfq_scale_slice(charge_sl, cfqg);
Vivek Goyaldae739e2009-12-03 12:59:45 -0500914 __cfq_group_service_tree_add(st, cfqg);
915
916 /* This group is being expired. Save the context */
917 if (time_after(cfqd->workload_expires, jiffies)) {
918 cfqg->saved_workload_slice = cfqd->workload_expires
919 - jiffies;
920 cfqg->saved_workload = cfqd->serving_type;
921 cfqg->saved_serving_prio = cfqd->serving_prio;
922 } else
923 cfqg->saved_workload_slice = 0;
Vivek Goyal2868ef72009-12-03 12:59:48 -0500924
925 cfq_log_cfqg(cfqd, cfqg, "served: vt=%llu min_vt=%llu", cfqg->vdisktime,
926 st->min_vdisktime);
Vivek Goyal22084192009-12-03 12:59:49 -0500927 blkiocg_update_blkio_group_stats(&cfqg->blkg, used_sl,
928 cfqq->nr_sectors);
Vivek Goyal1fa8f6d2009-12-03 12:59:41 -0500929}
930
Vivek Goyal25fb5162009-12-03 12:59:46 -0500931#ifdef CONFIG_CFQ_GROUP_IOSCHED
932static inline struct cfq_group *cfqg_of_blkg(struct blkio_group *blkg)
933{
934 if (blkg)
935 return container_of(blkg, struct cfq_group, blkg);
936 return NULL;
937}
938
Vivek Goyalf8d461d2009-12-03 12:59:52 -0500939void
940cfq_update_blkio_group_weight(struct blkio_group *blkg, unsigned int weight)
941{
942 cfqg_of_blkg(blkg)->weight = weight;
943}
944
Vivek Goyal25fb5162009-12-03 12:59:46 -0500945static struct cfq_group *
946cfq_find_alloc_cfqg(struct cfq_data *cfqd, struct cgroup *cgroup, int create)
947{
948 struct blkio_cgroup *blkcg = cgroup_to_blkio_cgroup(cgroup);
949 struct cfq_group *cfqg = NULL;
950 void *key = cfqd;
951 int i, j;
952 struct cfq_rb_root *st;
Vivek Goyal22084192009-12-03 12:59:49 -0500953 struct backing_dev_info *bdi = &cfqd->queue->backing_dev_info;
954 unsigned int major, minor;
Vivek Goyal25fb5162009-12-03 12:59:46 -0500955
956 /* Do we need to take this reference */
Vivek Goyal9d6a9862009-12-04 10:36:41 -0500957 if (!blkiocg_css_tryget(blkcg))
Vivek Goyal25fb5162009-12-03 12:59:46 -0500958 return NULL;;
959
960 cfqg = cfqg_of_blkg(blkiocg_lookup_group(blkcg, key));
961 if (cfqg || !create)
962 goto done;
963
964 cfqg = kzalloc_node(sizeof(*cfqg), GFP_ATOMIC, cfqd->queue->node);
965 if (!cfqg)
966 goto done;
967
968 cfqg->weight = blkcg->weight;
969 for_each_cfqg_st(cfqg, i, j, st)
970 *st = CFQ_RB_ROOT;
971 RB_CLEAR_NODE(&cfqg->rb_node);
972
Vivek Goyalb1c35762009-12-03 12:59:47 -0500973 /*
974 * Take the initial reference that will be released on destroy
975 * This can be thought of a joint reference by cgroup and
976 * elevator which will be dropped by either elevator exit
977 * or cgroup deletion path depending on who is exiting first.
978 */
979 atomic_set(&cfqg->ref, 1);
980
Vivek Goyal25fb5162009-12-03 12:59:46 -0500981 /* Add group onto cgroup list */
Vivek Goyal22084192009-12-03 12:59:49 -0500982 sscanf(dev_name(bdi->dev), "%u:%u", &major, &minor);
983 blkiocg_add_blkio_group(blkcg, &cfqg->blkg, (void *)cfqd,
984 MKDEV(major, minor));
Vivek Goyal25fb5162009-12-03 12:59:46 -0500985
986 /* Add group on cfqd list */
987 hlist_add_head(&cfqg->cfqd_node, &cfqd->cfqg_list);
988
989done:
Vivek Goyal9d6a9862009-12-04 10:36:41 -0500990 blkiocg_css_put(blkcg);
Vivek Goyal25fb5162009-12-03 12:59:46 -0500991 return cfqg;
992}
993
994/*
995 * Search for the cfq group current task belongs to. If create = 1, then also
996 * create the cfq group if it does not exist. request_queue lock must be held.
997 */
998static struct cfq_group *cfq_get_cfqg(struct cfq_data *cfqd, int create)
999{
1000 struct cgroup *cgroup;
1001 struct cfq_group *cfqg = NULL;
1002
1003 rcu_read_lock();
1004 cgroup = task_cgroup(current, blkio_subsys_id);
1005 cfqg = cfq_find_alloc_cfqg(cfqd, cgroup, create);
1006 if (!cfqg && create)
1007 cfqg = &cfqd->root_group;
1008 rcu_read_unlock();
1009 return cfqg;
1010}
1011
1012static void cfq_link_cfqq_cfqg(struct cfq_queue *cfqq, struct cfq_group *cfqg)
1013{
1014 /* Currently, all async queues are mapped to root group */
1015 if (!cfq_cfqq_sync(cfqq))
1016 cfqg = &cfqq->cfqd->root_group;
1017
1018 cfqq->cfqg = cfqg;
Vivek Goyalb1c35762009-12-03 12:59:47 -05001019 /* cfqq reference on cfqg */
1020 atomic_inc(&cfqq->cfqg->ref);
Vivek Goyal25fb5162009-12-03 12:59:46 -05001021}
Vivek Goyalb1c35762009-12-03 12:59:47 -05001022
1023static void cfq_put_cfqg(struct cfq_group *cfqg)
1024{
1025 struct cfq_rb_root *st;
1026 int i, j;
1027
1028 BUG_ON(atomic_read(&cfqg->ref) <= 0);
1029 if (!atomic_dec_and_test(&cfqg->ref))
1030 return;
1031 for_each_cfqg_st(cfqg, i, j, st)
1032 BUG_ON(!RB_EMPTY_ROOT(&st->rb) || st->active != NULL);
1033 kfree(cfqg);
1034}
1035
1036static void cfq_destroy_cfqg(struct cfq_data *cfqd, struct cfq_group *cfqg)
1037{
1038 /* Something wrong if we are trying to remove same group twice */
1039 BUG_ON(hlist_unhashed(&cfqg->cfqd_node));
1040
1041 hlist_del_init(&cfqg->cfqd_node);
1042
1043 /*
1044 * Put the reference taken at the time of creation so that when all
1045 * queues are gone, group can be destroyed.
1046 */
1047 cfq_put_cfqg(cfqg);
1048}
1049
1050static void cfq_release_cfq_groups(struct cfq_data *cfqd)
1051{
1052 struct hlist_node *pos, *n;
1053 struct cfq_group *cfqg;
1054
1055 hlist_for_each_entry_safe(cfqg, pos, n, &cfqd->cfqg_list, cfqd_node) {
1056 /*
1057 * If cgroup removal path got to blk_group first and removed
1058 * it from cgroup list, then it will take care of destroying
1059 * cfqg also.
1060 */
1061 if (!blkiocg_del_blkio_group(&cfqg->blkg))
1062 cfq_destroy_cfqg(cfqd, cfqg);
1063 }
1064}
1065
1066/*
1067 * Blk cgroup controller notification saying that blkio_group object is being
1068 * delinked as associated cgroup object is going away. That also means that
1069 * no new IO will come in this group. So get rid of this group as soon as
1070 * any pending IO in the group is finished.
1071 *
1072 * This function is called under rcu_read_lock(). key is the rcu protected
1073 * pointer. That means "key" is a valid cfq_data pointer as long as we are rcu
1074 * read lock.
1075 *
1076 * "key" was fetched from blkio_group under blkio_cgroup->lock. That means
1077 * it should not be NULL as even if elevator was exiting, cgroup deltion
1078 * path got to it first.
1079 */
1080void cfq_unlink_blkio_group(void *key, struct blkio_group *blkg)
1081{
1082 unsigned long flags;
1083 struct cfq_data *cfqd = key;
1084
1085 spin_lock_irqsave(cfqd->queue->queue_lock, flags);
1086 cfq_destroy_cfqg(cfqd, cfqg_of_blkg(blkg));
1087 spin_unlock_irqrestore(cfqd->queue->queue_lock, flags);
1088}
1089
Vivek Goyal25fb5162009-12-03 12:59:46 -05001090#else /* GROUP_IOSCHED */
1091static struct cfq_group *cfq_get_cfqg(struct cfq_data *cfqd, int create)
1092{
1093 return &cfqd->root_group;
1094}
1095static inline void
1096cfq_link_cfqq_cfqg(struct cfq_queue *cfqq, struct cfq_group *cfqg) {
1097 cfqq->cfqg = cfqg;
1098}
1099
Vivek Goyalb1c35762009-12-03 12:59:47 -05001100static void cfq_release_cfq_groups(struct cfq_data *cfqd) {}
1101static inline void cfq_put_cfqg(struct cfq_group *cfqg) {}
1102
Vivek Goyal25fb5162009-12-03 12:59:46 -05001103#endif /* GROUP_IOSCHED */
1104
Jens Axboe498d3aa22007-04-26 12:54:48 +02001105/*
Corrado Zoccoloc0324a02009-10-27 19:16:03 +01001106 * The cfqd->service_trees holds all pending cfq_queue's that have
Jens Axboe498d3aa22007-04-26 12:54:48 +02001107 * requests waiting to be processed. It is sorted in the order that
1108 * we will service the queues.
1109 */
Jens Axboea36e71f2009-04-15 12:15:11 +02001110static void cfq_service_tree_add(struct cfq_data *cfqd, struct cfq_queue *cfqq,
Jens Axboea6151c32009-10-07 20:02:57 +02001111 bool add_front)
Jens Axboed9e76202007-04-20 14:27:50 +02001112{
Jens Axboe08717142008-01-28 11:38:15 +01001113 struct rb_node **p, *parent;
1114 struct cfq_queue *__cfqq;
Jens Axboed9e76202007-04-20 14:27:50 +02001115 unsigned long rb_key;
Corrado Zoccoloc0324a02009-10-27 19:16:03 +01001116 struct cfq_rb_root *service_tree;
Jens Axboe498d3aa22007-04-26 12:54:48 +02001117 int left;
Vivek Goyaldae739e2009-12-03 12:59:45 -05001118 int new_cfqq = 1;
Vivek Goyalae30c282009-12-03 12:59:55 -05001119 int group_changed = 0;
1120
1121#ifdef CONFIG_CFQ_GROUP_IOSCHED
1122 if (!cfqd->cfq_group_isolation
1123 && cfqq_type(cfqq) == SYNC_NOIDLE_WORKLOAD
1124 && cfqq->cfqg && cfqq->cfqg != &cfqd->root_group) {
1125 /* Move this cfq to root group */
1126 cfq_log_cfqq(cfqd, cfqq, "moving to root group");
1127 if (!RB_EMPTY_NODE(&cfqq->rb_node))
1128 cfq_group_service_tree_del(cfqd, cfqq->cfqg);
1129 cfqq->orig_cfqg = cfqq->cfqg;
1130 cfqq->cfqg = &cfqd->root_group;
1131 atomic_inc(&cfqd->root_group.ref);
1132 group_changed = 1;
1133 } else if (!cfqd->cfq_group_isolation
1134 && cfqq_type(cfqq) == SYNC_WORKLOAD && cfqq->orig_cfqg) {
1135 /* cfqq is sequential now needs to go to its original group */
1136 BUG_ON(cfqq->cfqg != &cfqd->root_group);
1137 if (!RB_EMPTY_NODE(&cfqq->rb_node))
1138 cfq_group_service_tree_del(cfqd, cfqq->cfqg);
1139 cfq_put_cfqg(cfqq->cfqg);
1140 cfqq->cfqg = cfqq->orig_cfqg;
1141 cfqq->orig_cfqg = NULL;
1142 group_changed = 1;
1143 cfq_log_cfqq(cfqd, cfqq, "moved to origin group");
1144 }
1145#endif
Jens Axboed9e76202007-04-20 14:27:50 +02001146
Vivek Goyalcdb16e82009-12-03 12:59:38 -05001147 service_tree = service_tree_for(cfqq->cfqg, cfqq_prio(cfqq),
Vivek Goyal65b32a52009-12-16 17:52:59 -05001148 cfqq_type(cfqq));
Jens Axboe08717142008-01-28 11:38:15 +01001149 if (cfq_class_idle(cfqq)) {
1150 rb_key = CFQ_IDLE_DELAY;
Corrado Zoccoloaa6f6a32009-10-26 22:44:33 +01001151 parent = rb_last(&service_tree->rb);
Jens Axboe08717142008-01-28 11:38:15 +01001152 if (parent && parent != &cfqq->rb_node) {
1153 __cfqq = rb_entry(parent, struct cfq_queue, rb_node);
1154 rb_key += __cfqq->rb_key;
1155 } else
1156 rb_key += jiffies;
1157 } else if (!add_front) {
Jens Axboeb9c89462009-10-06 20:53:44 +02001158 /*
1159 * Get our rb key offset. Subtract any residual slice
1160 * value carried from last service. A negative resid
1161 * count indicates slice overrun, and this should position
1162 * the next service time further away in the tree.
1163 */
Jens Axboeedd75ff2007-04-19 12:03:34 +02001164 rb_key = cfq_slice_offset(cfqd, cfqq) + jiffies;
Jens Axboeb9c89462009-10-06 20:53:44 +02001165 rb_key -= cfqq->slice_resid;
Jens Axboeedd75ff2007-04-19 12:03:34 +02001166 cfqq->slice_resid = 0;
Corrado Zoccolo48e025e2009-10-05 08:49:23 +02001167 } else {
1168 rb_key = -HZ;
Corrado Zoccoloaa6f6a32009-10-26 22:44:33 +01001169 __cfqq = cfq_rb_first(service_tree);
Corrado Zoccolo48e025e2009-10-05 08:49:23 +02001170 rb_key += __cfqq ? __cfqq->rb_key : jiffies;
1171 }
Jens Axboed9e76202007-04-20 14:27:50 +02001172
1173 if (!RB_EMPTY_NODE(&cfqq->rb_node)) {
Vivek Goyaldae739e2009-12-03 12:59:45 -05001174 new_cfqq = 0;
Jens Axboe99f96282007-02-05 11:56:25 +01001175 /*
Jens Axboed9e76202007-04-20 14:27:50 +02001176 * same position, nothing more to do
Jens Axboe99f96282007-02-05 11:56:25 +01001177 */
Corrado Zoccoloc0324a02009-10-27 19:16:03 +01001178 if (rb_key == cfqq->rb_key &&
1179 cfqq->service_tree == service_tree)
Jens Axboed9e76202007-04-20 14:27:50 +02001180 return;
Jens Axboe53b037442006-07-28 09:48:51 +02001181
Corrado Zoccoloaa6f6a32009-10-26 22:44:33 +01001182 cfq_rb_erase(&cfqq->rb_node, cfqq->service_tree);
1183 cfqq->service_tree = NULL;
Jens Axboe22e2c502005-06-27 10:55:12 +02001184 }
Jens Axboed9e76202007-04-20 14:27:50 +02001185
Jens Axboe498d3aa22007-04-26 12:54:48 +02001186 left = 1;
Jens Axboe08717142008-01-28 11:38:15 +01001187 parent = NULL;
Corrado Zoccoloaa6f6a32009-10-26 22:44:33 +01001188 cfqq->service_tree = service_tree;
1189 p = &service_tree->rb.rb_node;
Jens Axboed9e76202007-04-20 14:27:50 +02001190 while (*p) {
Jens Axboe67060e32007-04-18 20:13:32 +02001191 struct rb_node **n;
Jens Axboecc09e292007-04-26 12:53:50 +02001192
Jens Axboed9e76202007-04-20 14:27:50 +02001193 parent = *p;
1194 __cfqq = rb_entry(parent, struct cfq_queue, rb_node);
1195
Jens Axboe0c534e02007-04-18 20:01:57 +02001196 /*
Corrado Zoccoloc0324a02009-10-27 19:16:03 +01001197 * sort by key, that represents service time.
Jens Axboe0c534e02007-04-18 20:01:57 +02001198 */
Corrado Zoccoloc0324a02009-10-27 19:16:03 +01001199 if (time_before(rb_key, __cfqq->rb_key))
Jens Axboe67060e32007-04-18 20:13:32 +02001200 n = &(*p)->rb_left;
Corrado Zoccoloc0324a02009-10-27 19:16:03 +01001201 else {
Jens Axboe67060e32007-04-18 20:13:32 +02001202 n = &(*p)->rb_right;
Jens Axboecc09e292007-04-26 12:53:50 +02001203 left = 0;
Corrado Zoccoloc0324a02009-10-27 19:16:03 +01001204 }
Jens Axboe67060e32007-04-18 20:13:32 +02001205
1206 p = n;
Jens Axboed9e76202007-04-20 14:27:50 +02001207 }
1208
Jens Axboecc09e292007-04-26 12:53:50 +02001209 if (left)
Corrado Zoccoloaa6f6a32009-10-26 22:44:33 +01001210 service_tree->left = &cfqq->rb_node;
Jens Axboecc09e292007-04-26 12:53:50 +02001211
Jens Axboed9e76202007-04-20 14:27:50 +02001212 cfqq->rb_key = rb_key;
1213 rb_link_node(&cfqq->rb_node, parent, p);
Corrado Zoccoloaa6f6a32009-10-26 22:44:33 +01001214 rb_insert_color(&cfqq->rb_node, &service_tree->rb);
1215 service_tree->count++;
Vivek Goyalae30c282009-12-03 12:59:55 -05001216 if ((add_front || !new_cfqq) && !group_changed)
Vivek Goyaldae739e2009-12-03 12:59:45 -05001217 return;
Vivek Goyal1fa8f6d2009-12-03 12:59:41 -05001218 cfq_group_service_tree_add(cfqd, cfqq->cfqg);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001219}
1220
Jens Axboea36e71f2009-04-15 12:15:11 +02001221static struct cfq_queue *
Jens Axboef2d1f0a2009-04-23 12:19:38 +02001222cfq_prio_tree_lookup(struct cfq_data *cfqd, struct rb_root *root,
1223 sector_t sector, struct rb_node **ret_parent,
1224 struct rb_node ***rb_link)
Jens Axboea36e71f2009-04-15 12:15:11 +02001225{
Jens Axboea36e71f2009-04-15 12:15:11 +02001226 struct rb_node **p, *parent;
1227 struct cfq_queue *cfqq = NULL;
1228
1229 parent = NULL;
1230 p = &root->rb_node;
1231 while (*p) {
1232 struct rb_node **n;
1233
1234 parent = *p;
1235 cfqq = rb_entry(parent, struct cfq_queue, p_node);
1236
1237 /*
1238 * Sort strictly based on sector. Smallest to the left,
1239 * largest to the right.
1240 */
Tejun Heo2e46e8b2009-05-07 22:24:41 +09001241 if (sector > blk_rq_pos(cfqq->next_rq))
Jens Axboea36e71f2009-04-15 12:15:11 +02001242 n = &(*p)->rb_right;
Tejun Heo2e46e8b2009-05-07 22:24:41 +09001243 else if (sector < blk_rq_pos(cfqq->next_rq))
Jens Axboea36e71f2009-04-15 12:15:11 +02001244 n = &(*p)->rb_left;
1245 else
1246 break;
1247 p = n;
Jens Axboe3ac6c9f2009-04-23 12:14:56 +02001248 cfqq = NULL;
Jens Axboea36e71f2009-04-15 12:15:11 +02001249 }
1250
1251 *ret_parent = parent;
1252 if (rb_link)
1253 *rb_link = p;
Jens Axboe3ac6c9f2009-04-23 12:14:56 +02001254 return cfqq;
Jens Axboea36e71f2009-04-15 12:15:11 +02001255}
1256
1257static void cfq_prio_tree_add(struct cfq_data *cfqd, struct cfq_queue *cfqq)
1258{
Jens Axboea36e71f2009-04-15 12:15:11 +02001259 struct rb_node **p, *parent;
1260 struct cfq_queue *__cfqq;
1261
Jens Axboef2d1f0a2009-04-23 12:19:38 +02001262 if (cfqq->p_root) {
1263 rb_erase(&cfqq->p_node, cfqq->p_root);
1264 cfqq->p_root = NULL;
1265 }
Jens Axboea36e71f2009-04-15 12:15:11 +02001266
1267 if (cfq_class_idle(cfqq))
1268 return;
1269 if (!cfqq->next_rq)
1270 return;
1271
Jens Axboef2d1f0a2009-04-23 12:19:38 +02001272 cfqq->p_root = &cfqd->prio_trees[cfqq->org_ioprio];
Tejun Heo2e46e8b2009-05-07 22:24:41 +09001273 __cfqq = cfq_prio_tree_lookup(cfqd, cfqq->p_root,
1274 blk_rq_pos(cfqq->next_rq), &parent, &p);
Jens Axboe3ac6c9f2009-04-23 12:14:56 +02001275 if (!__cfqq) {
1276 rb_link_node(&cfqq->p_node, parent, p);
Jens Axboef2d1f0a2009-04-23 12:19:38 +02001277 rb_insert_color(&cfqq->p_node, cfqq->p_root);
1278 } else
1279 cfqq->p_root = NULL;
Jens Axboea36e71f2009-04-15 12:15:11 +02001280}
1281
Jens Axboe498d3aa22007-04-26 12:54:48 +02001282/*
1283 * Update cfqq's position in the service tree.
1284 */
Jens Axboeedd75ff2007-04-19 12:03:34 +02001285static void cfq_resort_rr_list(struct cfq_data *cfqd, struct cfq_queue *cfqq)
Jens Axboe6d048f52007-04-25 12:44:27 +02001286{
Jens Axboe6d048f52007-04-25 12:44:27 +02001287 /*
1288 * Resorting requires the cfqq to be on the RR list already.
1289 */
Jens Axboea36e71f2009-04-15 12:15:11 +02001290 if (cfq_cfqq_on_rr(cfqq)) {
Jens Axboeedd75ff2007-04-19 12:03:34 +02001291 cfq_service_tree_add(cfqd, cfqq, 0);
Jens Axboea36e71f2009-04-15 12:15:11 +02001292 cfq_prio_tree_add(cfqd, cfqq);
1293 }
Jens Axboe6d048f52007-04-25 12:44:27 +02001294}
1295
Linus Torvalds1da177e2005-04-16 15:20:36 -07001296/*
1297 * add to busy list of queues for service, trying to be fair in ordering
Jens Axboe22e2c502005-06-27 10:55:12 +02001298 * the pending list according to last request service
Linus Torvalds1da177e2005-04-16 15:20:36 -07001299 */
Jens Axboefebffd62008-01-28 13:19:43 +01001300static void cfq_add_cfqq_rr(struct cfq_data *cfqd, struct cfq_queue *cfqq)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001301{
Jens Axboe7b679132008-05-30 12:23:07 +02001302 cfq_log_cfqq(cfqd, cfqq, "add_to_rr");
Jens Axboe3b181522005-06-27 10:56:24 +02001303 BUG_ON(cfq_cfqq_on_rr(cfqq));
1304 cfq_mark_cfqq_on_rr(cfqq);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001305 cfqd->busy_queues++;
1306
Jens Axboeedd75ff2007-04-19 12:03:34 +02001307 cfq_resort_rr_list(cfqd, cfqq);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001308}
1309
Jens Axboe498d3aa22007-04-26 12:54:48 +02001310/*
1311 * Called when the cfqq no longer has requests pending, remove it from
1312 * the service tree.
1313 */
Jens Axboefebffd62008-01-28 13:19:43 +01001314static void cfq_del_cfqq_rr(struct cfq_data *cfqd, struct cfq_queue *cfqq)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001315{
Jens Axboe7b679132008-05-30 12:23:07 +02001316 cfq_log_cfqq(cfqd, cfqq, "del_from_rr");
Jens Axboe3b181522005-06-27 10:56:24 +02001317 BUG_ON(!cfq_cfqq_on_rr(cfqq));
1318 cfq_clear_cfqq_on_rr(cfqq);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001319
Corrado Zoccoloaa6f6a32009-10-26 22:44:33 +01001320 if (!RB_EMPTY_NODE(&cfqq->rb_node)) {
1321 cfq_rb_erase(&cfqq->rb_node, cfqq->service_tree);
1322 cfqq->service_tree = NULL;
1323 }
Jens Axboef2d1f0a2009-04-23 12:19:38 +02001324 if (cfqq->p_root) {
1325 rb_erase(&cfqq->p_node, cfqq->p_root);
1326 cfqq->p_root = NULL;
1327 }
Jens Axboed9e76202007-04-20 14:27:50 +02001328
Vivek Goyal1fa8f6d2009-12-03 12:59:41 -05001329 cfq_group_service_tree_del(cfqd, cfqq->cfqg);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001330 BUG_ON(!cfqd->busy_queues);
1331 cfqd->busy_queues--;
1332}
1333
1334/*
1335 * rb tree support functions
1336 */
Jens Axboefebffd62008-01-28 13:19:43 +01001337static void cfq_del_rq_rb(struct request *rq)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001338{
Jens Axboe5e705372006-07-13 12:39:25 +02001339 struct cfq_queue *cfqq = RQ_CFQQ(rq);
Jens Axboe5e705372006-07-13 12:39:25 +02001340 const int sync = rq_is_sync(rq);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001341
Jens Axboeb4878f22005-10-20 16:42:29 +02001342 BUG_ON(!cfqq->queued[sync]);
1343 cfqq->queued[sync]--;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001344
Jens Axboe5e705372006-07-13 12:39:25 +02001345 elv_rb_del(&cfqq->sort_list, rq);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001346
Vivek Goyalf04a6422009-12-03 12:59:40 -05001347 if (cfq_cfqq_on_rr(cfqq) && RB_EMPTY_ROOT(&cfqq->sort_list)) {
1348 /*
1349 * Queue will be deleted from service tree when we actually
1350 * expire it later. Right now just remove it from prio tree
1351 * as it is empty.
1352 */
1353 if (cfqq->p_root) {
1354 rb_erase(&cfqq->p_node, cfqq->p_root);
1355 cfqq->p_root = NULL;
1356 }
1357 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07001358}
1359
Jens Axboe5e705372006-07-13 12:39:25 +02001360static void cfq_add_rq_rb(struct request *rq)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001361{
Jens Axboe5e705372006-07-13 12:39:25 +02001362 struct cfq_queue *cfqq = RQ_CFQQ(rq);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001363 struct cfq_data *cfqd = cfqq->cfqd;
Jens Axboea36e71f2009-04-15 12:15:11 +02001364 struct request *__alias, *prev;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001365
Jens Axboe5380a102006-07-13 12:37:56 +02001366 cfqq->queued[rq_is_sync(rq)]++;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001367
1368 /*
1369 * looks a little odd, but the first insert might return an alias.
1370 * if that happens, put the alias on the dispatch list
1371 */
Jens Axboe21183b02006-07-13 12:33:14 +02001372 while ((__alias = elv_rb_add(&cfqq->sort_list, rq)) != NULL)
Jens Axboe5e705372006-07-13 12:39:25 +02001373 cfq_dispatch_insert(cfqd->queue, __alias);
Jens Axboe5fccbf62006-10-31 14:21:55 +01001374
1375 if (!cfq_cfqq_on_rr(cfqq))
1376 cfq_add_cfqq_rr(cfqd, cfqq);
Jens Axboe5044eed2007-04-25 11:53:48 +02001377
1378 /*
1379 * check if this request is a better next-serve candidate
1380 */
Jens Axboea36e71f2009-04-15 12:15:11 +02001381 prev = cfqq->next_rq;
Corrado Zoccolocf7c25c2009-11-08 17:16:46 +01001382 cfqq->next_rq = cfq_choose_req(cfqd, cfqq->next_rq, rq, cfqd->last_position);
Jens Axboea36e71f2009-04-15 12:15:11 +02001383
1384 /*
1385 * adjust priority tree position, if ->next_rq changes
1386 */
1387 if (prev != cfqq->next_rq)
1388 cfq_prio_tree_add(cfqd, cfqq);
1389
Jens Axboe5044eed2007-04-25 11:53:48 +02001390 BUG_ON(!cfqq->next_rq);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001391}
1392
Jens Axboefebffd62008-01-28 13:19:43 +01001393static void cfq_reposition_rq_rb(struct cfq_queue *cfqq, struct request *rq)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001394{
Jens Axboe5380a102006-07-13 12:37:56 +02001395 elv_rb_del(&cfqq->sort_list, rq);
1396 cfqq->queued[rq_is_sync(rq)]--;
Jens Axboe5e705372006-07-13 12:39:25 +02001397 cfq_add_rq_rb(rq);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001398}
1399
Jens Axboe206dc692006-03-28 13:03:44 +02001400static struct request *
1401cfq_find_rq_fmerge(struct cfq_data *cfqd, struct bio *bio)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001402{
Jens Axboe206dc692006-03-28 13:03:44 +02001403 struct task_struct *tsk = current;
Vasily Tarasov91fac312007-04-25 12:29:51 +02001404 struct cfq_io_context *cic;
Jens Axboe206dc692006-03-28 13:03:44 +02001405 struct cfq_queue *cfqq;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001406
Jens Axboe4ac845a2008-01-24 08:44:49 +01001407 cic = cfq_cic_lookup(cfqd, tsk->io_context);
Vasily Tarasov91fac312007-04-25 12:29:51 +02001408 if (!cic)
1409 return NULL;
1410
1411 cfqq = cic_to_cfqq(cic, cfq_bio_sync(bio));
Jens Axboe89850f72006-07-22 16:48:31 +02001412 if (cfqq) {
1413 sector_t sector = bio->bi_sector + bio_sectors(bio);
1414
Jens Axboe21183b02006-07-13 12:33:14 +02001415 return elv_rb_find(&cfqq->sort_list, sector);
Jens Axboe89850f72006-07-22 16:48:31 +02001416 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07001417
Linus Torvalds1da177e2005-04-16 15:20:36 -07001418 return NULL;
1419}
1420
Jens Axboe165125e2007-07-24 09:28:11 +02001421static void cfq_activate_request(struct request_queue *q, struct request *rq)
Jens Axboeb4878f22005-10-20 16:42:29 +02001422{
1423 struct cfq_data *cfqd = q->elevator->elevator_data;
1424
Jens Axboe5ad531d2009-07-03 12:57:48 +02001425 cfqd->rq_in_driver[rq_is_sync(rq)]++;
Jens Axboe7b679132008-05-30 12:23:07 +02001426 cfq_log_cfqq(cfqd, RQ_CFQQ(rq), "activate rq, drv=%d",
Jens Axboe5ad531d2009-07-03 12:57:48 +02001427 rq_in_driver(cfqd));
Jens Axboe25776e32006-06-01 10:12:26 +02001428
Tejun Heo5b936292009-05-07 22:24:38 +09001429 cfqd->last_position = blk_rq_pos(rq) + blk_rq_sectors(rq);
Jens Axboeb4878f22005-10-20 16:42:29 +02001430}
1431
Jens Axboe165125e2007-07-24 09:28:11 +02001432static void cfq_deactivate_request(struct request_queue *q, struct request *rq)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001433{
Jens Axboe22e2c502005-06-27 10:55:12 +02001434 struct cfq_data *cfqd = q->elevator->elevator_data;
Jens Axboe5ad531d2009-07-03 12:57:48 +02001435 const int sync = rq_is_sync(rq);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001436
Jens Axboe5ad531d2009-07-03 12:57:48 +02001437 WARN_ON(!cfqd->rq_in_driver[sync]);
1438 cfqd->rq_in_driver[sync]--;
Jens Axboe7b679132008-05-30 12:23:07 +02001439 cfq_log_cfqq(cfqd, RQ_CFQQ(rq), "deactivate rq, drv=%d",
Jens Axboe5ad531d2009-07-03 12:57:48 +02001440 rq_in_driver(cfqd));
Linus Torvalds1da177e2005-04-16 15:20:36 -07001441}
1442
Jens Axboeb4878f22005-10-20 16:42:29 +02001443static void cfq_remove_request(struct request *rq)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001444{
Jens Axboe5e705372006-07-13 12:39:25 +02001445 struct cfq_queue *cfqq = RQ_CFQQ(rq);
Jens Axboe21183b02006-07-13 12:33:14 +02001446
Jens Axboe5e705372006-07-13 12:39:25 +02001447 if (cfqq->next_rq == rq)
1448 cfqq->next_rq = cfq_find_next_rq(cfqq->cfqd, cfqq, rq);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001449
Jens Axboeb4878f22005-10-20 16:42:29 +02001450 list_del_init(&rq->queuelist);
Jens Axboe5e705372006-07-13 12:39:25 +02001451 cfq_del_rq_rb(rq);
Jens Axboe374f84a2006-07-23 01:42:19 +02001452
Aaron Carroll45333d52008-08-26 15:52:36 +02001453 cfqq->cfqd->rq_queued--;
Jens Axboe374f84a2006-07-23 01:42:19 +02001454 if (rq_is_meta(rq)) {
1455 WARN_ON(!cfqq->meta_pending);
1456 cfqq->meta_pending--;
1457 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07001458}
1459
Jens Axboe165125e2007-07-24 09:28:11 +02001460static int cfq_merge(struct request_queue *q, struct request **req,
1461 struct bio *bio)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001462{
1463 struct cfq_data *cfqd = q->elevator->elevator_data;
1464 struct request *__rq;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001465
Jens Axboe206dc692006-03-28 13:03:44 +02001466 __rq = cfq_find_rq_fmerge(cfqd, bio);
Jens Axboe22e2c502005-06-27 10:55:12 +02001467 if (__rq && elv_rq_merge_ok(__rq, bio)) {
Jens Axboe98170642006-07-28 09:23:08 +02001468 *req = __rq;
1469 return ELEVATOR_FRONT_MERGE;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001470 }
1471
1472 return ELEVATOR_NO_MERGE;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001473}
1474
Jens Axboe165125e2007-07-24 09:28:11 +02001475static void cfq_merged_request(struct request_queue *q, struct request *req,
Jens Axboe21183b02006-07-13 12:33:14 +02001476 int type)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001477{
Jens Axboe21183b02006-07-13 12:33:14 +02001478 if (type == ELEVATOR_FRONT_MERGE) {
Jens Axboe5e705372006-07-13 12:39:25 +02001479 struct cfq_queue *cfqq = RQ_CFQQ(req);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001480
Jens Axboe5e705372006-07-13 12:39:25 +02001481 cfq_reposition_rq_rb(cfqq, req);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001482 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07001483}
1484
1485static void
Jens Axboe165125e2007-07-24 09:28:11 +02001486cfq_merged_requests(struct request_queue *q, struct request *rq,
Linus Torvalds1da177e2005-04-16 15:20:36 -07001487 struct request *next)
1488{
Corrado Zoccolocf7c25c2009-11-08 17:16:46 +01001489 struct cfq_queue *cfqq = RQ_CFQQ(rq);
Jens Axboe22e2c502005-06-27 10:55:12 +02001490 /*
1491 * reposition in fifo if next is older than rq
1492 */
1493 if (!list_empty(&rq->queuelist) && !list_empty(&next->queuelist) &&
Jens Axboe30996f42009-10-05 11:03:39 +02001494 time_before(rq_fifo_time(next), rq_fifo_time(rq))) {
Jens Axboe22e2c502005-06-27 10:55:12 +02001495 list_move(&rq->queuelist, &next->queuelist);
Jens Axboe30996f42009-10-05 11:03:39 +02001496 rq_set_fifo_time(rq, rq_fifo_time(next));
1497 }
Jens Axboe22e2c502005-06-27 10:55:12 +02001498
Corrado Zoccolocf7c25c2009-11-08 17:16:46 +01001499 if (cfqq->next_rq == next)
1500 cfqq->next_rq = rq;
Jens Axboeb4878f22005-10-20 16:42:29 +02001501 cfq_remove_request(next);
Jens Axboe22e2c502005-06-27 10:55:12 +02001502}
1503
Jens Axboe165125e2007-07-24 09:28:11 +02001504static int cfq_allow_merge(struct request_queue *q, struct request *rq,
Jens Axboeda775262006-12-20 11:04:12 +01001505 struct bio *bio)
1506{
1507 struct cfq_data *cfqd = q->elevator->elevator_data;
Vasily Tarasov91fac312007-04-25 12:29:51 +02001508 struct cfq_io_context *cic;
Jens Axboeda775262006-12-20 11:04:12 +01001509 struct cfq_queue *cfqq;
Jens Axboeda775262006-12-20 11:04:12 +01001510
1511 /*
Jens Axboeec8acb62007-01-02 18:32:11 +01001512 * Disallow merge of a sync bio into an async request.
Jens Axboeda775262006-12-20 11:04:12 +01001513 */
Vasily Tarasov91fac312007-04-25 12:29:51 +02001514 if (cfq_bio_sync(bio) && !rq_is_sync(rq))
Jens Axboea6151c32009-10-07 20:02:57 +02001515 return false;
Jens Axboeda775262006-12-20 11:04:12 +01001516
1517 /*
Jens Axboe719d3402006-12-22 09:38:53 +01001518 * Lookup the cfqq that this bio will be queued with. Allow
1519 * merge only if rq is queued there.
Jens Axboeda775262006-12-20 11:04:12 +01001520 */
Jens Axboe4ac845a2008-01-24 08:44:49 +01001521 cic = cfq_cic_lookup(cfqd, current->io_context);
Vasily Tarasov91fac312007-04-25 12:29:51 +02001522 if (!cic)
Jens Axboea6151c32009-10-07 20:02:57 +02001523 return false;
Jens Axboe719d3402006-12-22 09:38:53 +01001524
Vasily Tarasov91fac312007-04-25 12:29:51 +02001525 cfqq = cic_to_cfqq(cic, cfq_bio_sync(bio));
Jens Axboea6151c32009-10-07 20:02:57 +02001526 return cfqq == RQ_CFQQ(rq);
Jens Axboeda775262006-12-20 11:04:12 +01001527}
1528
Jens Axboefebffd62008-01-28 13:19:43 +01001529static void __cfq_set_active_queue(struct cfq_data *cfqd,
1530 struct cfq_queue *cfqq)
Jens Axboe22e2c502005-06-27 10:55:12 +02001531{
1532 if (cfqq) {
Jens Axboe7b679132008-05-30 12:23:07 +02001533 cfq_log_cfqq(cfqd, cfqq, "set_active");
Vivek Goyaldae739e2009-12-03 12:59:45 -05001534 cfqq->slice_start = 0;
1535 cfqq->dispatch_start = jiffies;
Vivek Goyalf75edf22009-12-03 12:59:53 -05001536 cfqq->allocated_slice = 0;
Jens Axboe22e2c502005-06-27 10:55:12 +02001537 cfqq->slice_end = 0;
Jens Axboe2f5cb732009-04-07 08:51:19 +02001538 cfqq->slice_dispatch = 0;
Vivek Goyal22084192009-12-03 12:59:49 -05001539 cfqq->nr_sectors = 0;
Jens Axboe2f5cb732009-04-07 08:51:19 +02001540
Jens Axboe2f5cb732009-04-07 08:51:19 +02001541 cfq_clear_cfqq_wait_request(cfqq);
Jens Axboeb0291952009-04-07 11:38:31 +02001542 cfq_clear_cfqq_must_dispatch(cfqq);
Jens Axboe3b181522005-06-27 10:56:24 +02001543 cfq_clear_cfqq_must_alloc_slice(cfqq);
1544 cfq_clear_cfqq_fifo_expire(cfqq);
Jens Axboe44f7c162007-01-19 11:51:58 +11001545 cfq_mark_cfqq_slice_new(cfqq);
Jens Axboe2f5cb732009-04-07 08:51:19 +02001546
1547 del_timer(&cfqd->idle_slice_timer);
Jens Axboe22e2c502005-06-27 10:55:12 +02001548 }
1549
1550 cfqd->active_queue = cfqq;
1551}
1552
1553/*
Jens Axboe7b14e3b2006-02-28 09:35:11 +01001554 * current cfqq expired its slice (or was too idle), select new one
1555 */
1556static void
1557__cfq_slice_expired(struct cfq_data *cfqd, struct cfq_queue *cfqq,
Jens Axboea6151c32009-10-07 20:02:57 +02001558 bool timed_out)
Jens Axboe7b14e3b2006-02-28 09:35:11 +01001559{
Jens Axboe7b679132008-05-30 12:23:07 +02001560 cfq_log_cfqq(cfqd, cfqq, "slice expired t=%d", timed_out);
1561
Jens Axboe7b14e3b2006-02-28 09:35:11 +01001562 if (cfq_cfqq_wait_request(cfqq))
1563 del_timer(&cfqd->idle_slice_timer);
1564
Jens Axboe7b14e3b2006-02-28 09:35:11 +01001565 cfq_clear_cfqq_wait_request(cfqq);
Vivek Goyalf75edf22009-12-03 12:59:53 -05001566 cfq_clear_cfqq_wait_busy(cfqq);
Jens Axboe7b14e3b2006-02-28 09:35:11 +01001567
1568 /*
Jens Axboe6084cdd2007-04-23 08:25:00 +02001569 * store what was left of this slice, if the queue idled/timed out
Jens Axboe7b14e3b2006-02-28 09:35:11 +01001570 */
Jens Axboe7b679132008-05-30 12:23:07 +02001571 if (timed_out && !cfq_cfqq_slice_new(cfqq)) {
Jens Axboec5b680f2007-01-19 11:56:49 +11001572 cfqq->slice_resid = cfqq->slice_end - jiffies;
Jens Axboe7b679132008-05-30 12:23:07 +02001573 cfq_log_cfqq(cfqd, cfqq, "resid=%ld", cfqq->slice_resid);
1574 }
Jens Axboe7b14e3b2006-02-28 09:35:11 +01001575
Vivek Goyaldae739e2009-12-03 12:59:45 -05001576 cfq_group_served(cfqd, cfqq->cfqg, cfqq);
1577
Vivek Goyalf04a6422009-12-03 12:59:40 -05001578 if (cfq_cfqq_on_rr(cfqq) && RB_EMPTY_ROOT(&cfqq->sort_list))
1579 cfq_del_cfqq_rr(cfqd, cfqq);
1580
Jens Axboeedd75ff2007-04-19 12:03:34 +02001581 cfq_resort_rr_list(cfqd, cfqq);
Jens Axboe7b14e3b2006-02-28 09:35:11 +01001582
1583 if (cfqq == cfqd->active_queue)
1584 cfqd->active_queue = NULL;
1585
Vivek Goyaldae739e2009-12-03 12:59:45 -05001586 if (&cfqq->cfqg->rb_node == cfqd->grp_service_tree.active)
1587 cfqd->grp_service_tree.active = NULL;
1588
Jens Axboe7b14e3b2006-02-28 09:35:11 +01001589 if (cfqd->active_cic) {
1590 put_io_context(cfqd->active_cic->ioc);
1591 cfqd->active_cic = NULL;
1592 }
Jens Axboe7b14e3b2006-02-28 09:35:11 +01001593}
1594
Jens Axboea6151c32009-10-07 20:02:57 +02001595static inline void cfq_slice_expired(struct cfq_data *cfqd, bool timed_out)
Jens Axboe7b14e3b2006-02-28 09:35:11 +01001596{
1597 struct cfq_queue *cfqq = cfqd->active_queue;
1598
1599 if (cfqq)
Jens Axboe6084cdd2007-04-23 08:25:00 +02001600 __cfq_slice_expired(cfqd, cfqq, timed_out);
Jens Axboe7b14e3b2006-02-28 09:35:11 +01001601}
1602
Jens Axboe498d3aa22007-04-26 12:54:48 +02001603/*
1604 * Get next queue for service. Unless we have a queue preemption,
1605 * we'll simply select the first cfqq in the service tree.
1606 */
Jens Axboe6d048f52007-04-25 12:44:27 +02001607static struct cfq_queue *cfq_get_next_queue(struct cfq_data *cfqd)
Jens Axboe22e2c502005-06-27 10:55:12 +02001608{
Corrado Zoccoloc0324a02009-10-27 19:16:03 +01001609 struct cfq_rb_root *service_tree =
Vivek Goyalcdb16e82009-12-03 12:59:38 -05001610 service_tree_for(cfqd->serving_group, cfqd->serving_prio,
Vivek Goyal65b32a52009-12-16 17:52:59 -05001611 cfqd->serving_type);
Jens Axboeedd75ff2007-04-19 12:03:34 +02001612
Vivek Goyalf04a6422009-12-03 12:59:40 -05001613 if (!cfqd->rq_queued)
1614 return NULL;
1615
Vivek Goyal1fa8f6d2009-12-03 12:59:41 -05001616 /* There is nothing to dispatch */
1617 if (!service_tree)
1618 return NULL;
Corrado Zoccoloc0324a02009-10-27 19:16:03 +01001619 if (RB_EMPTY_ROOT(&service_tree->rb))
1620 return NULL;
1621 return cfq_rb_first(service_tree);
Jens Axboe6d048f52007-04-25 12:44:27 +02001622}
1623
Vivek Goyalf04a6422009-12-03 12:59:40 -05001624static struct cfq_queue *cfq_get_next_queue_forced(struct cfq_data *cfqd)
1625{
Vivek Goyal25fb5162009-12-03 12:59:46 -05001626 struct cfq_group *cfqg;
Vivek Goyalf04a6422009-12-03 12:59:40 -05001627 struct cfq_queue *cfqq;
1628 int i, j;
1629 struct cfq_rb_root *st;
1630
1631 if (!cfqd->rq_queued)
1632 return NULL;
1633
Vivek Goyal25fb5162009-12-03 12:59:46 -05001634 cfqg = cfq_get_next_cfqg(cfqd);
1635 if (!cfqg)
1636 return NULL;
1637
Vivek Goyalf04a6422009-12-03 12:59:40 -05001638 for_each_cfqg_st(cfqg, i, j, st)
1639 if ((cfqq = cfq_rb_first(st)) != NULL)
1640 return cfqq;
1641 return NULL;
1642}
1643
Jens Axboe498d3aa22007-04-26 12:54:48 +02001644/*
1645 * Get and set a new active queue for service.
1646 */
Jens Axboea36e71f2009-04-15 12:15:11 +02001647static struct cfq_queue *cfq_set_active_queue(struct cfq_data *cfqd,
1648 struct cfq_queue *cfqq)
Jens Axboe6d048f52007-04-25 12:44:27 +02001649{
Jens Axboee00ef792009-11-04 08:54:55 +01001650 if (!cfqq)
Jens Axboea36e71f2009-04-15 12:15:11 +02001651 cfqq = cfq_get_next_queue(cfqd);
Jens Axboe6d048f52007-04-25 12:44:27 +02001652
Jens Axboe22e2c502005-06-27 10:55:12 +02001653 __cfq_set_active_queue(cfqd, cfqq);
Jens Axboe3b181522005-06-27 10:56:24 +02001654 return cfqq;
Jens Axboe22e2c502005-06-27 10:55:12 +02001655}
1656
Jens Axboed9e76202007-04-20 14:27:50 +02001657static inline sector_t cfq_dist_from_last(struct cfq_data *cfqd,
1658 struct request *rq)
1659{
Tejun Heo83096eb2009-05-07 22:24:39 +09001660 if (blk_rq_pos(rq) >= cfqd->last_position)
1661 return blk_rq_pos(rq) - cfqd->last_position;
Jens Axboed9e76202007-04-20 14:27:50 +02001662 else
Tejun Heo83096eb2009-05-07 22:24:39 +09001663 return cfqd->last_position - blk_rq_pos(rq);
Jens Axboed9e76202007-04-20 14:27:50 +02001664}
1665
Jeff Moyerb2c18e12009-10-23 17:14:49 -04001666#define CFQQ_SEEK_THR 8 * 1024
1667#define CFQQ_SEEKY(cfqq) ((cfqq)->seek_mean > CFQQ_SEEK_THR)
Jeff Moyer04dc6e72009-04-21 07:31:56 +02001668
Jeff Moyerb2c18e12009-10-23 17:14:49 -04001669static inline int cfq_rq_close(struct cfq_data *cfqd, struct cfq_queue *cfqq,
Shaohua Li2f7a2d82009-12-28 13:18:44 +01001670 struct request *rq, bool for_preempt)
Jens Axboe6d048f52007-04-25 12:44:27 +02001671{
Jeff Moyerb2c18e12009-10-23 17:14:49 -04001672 sector_t sdist = cfqq->seek_mean;
Jens Axboecaaa5f92006-06-16 11:23:00 +02001673
Jeff Moyerb2c18e12009-10-23 17:14:49 -04001674 if (!sample_valid(cfqq->seek_samples))
1675 sdist = CFQQ_SEEK_THR;
Jens Axboe6d048f52007-04-25 12:44:27 +02001676
Shaohua Li2f7a2d82009-12-28 13:18:44 +01001677 /* if seek_mean is big, using it as close criteria is meaningless */
1678 if (sdist > CFQQ_SEEK_THR && !for_preempt)
1679 sdist = CFQQ_SEEK_THR;
1680
Jeff Moyer04dc6e72009-04-21 07:31:56 +02001681 return cfq_dist_from_last(cfqd, rq) <= sdist;
Jens Axboe6d048f52007-04-25 12:44:27 +02001682}
1683
Jens Axboea36e71f2009-04-15 12:15:11 +02001684static struct cfq_queue *cfqq_close(struct cfq_data *cfqd,
1685 struct cfq_queue *cur_cfqq)
Jens Axboe6d048f52007-04-25 12:44:27 +02001686{
Jens Axboef2d1f0a2009-04-23 12:19:38 +02001687 struct rb_root *root = &cfqd->prio_trees[cur_cfqq->org_ioprio];
Jens Axboea36e71f2009-04-15 12:15:11 +02001688 struct rb_node *parent, *node;
1689 struct cfq_queue *__cfqq;
1690 sector_t sector = cfqd->last_position;
1691
1692 if (RB_EMPTY_ROOT(root))
1693 return NULL;
1694
1695 /*
1696 * First, if we find a request starting at the end of the last
1697 * request, choose it.
1698 */
Jens Axboef2d1f0a2009-04-23 12:19:38 +02001699 __cfqq = cfq_prio_tree_lookup(cfqd, root, sector, &parent, NULL);
Jens Axboea36e71f2009-04-15 12:15:11 +02001700 if (__cfqq)
1701 return __cfqq;
1702
1703 /*
1704 * If the exact sector wasn't found, the parent of the NULL leaf
1705 * will contain the closest sector.
1706 */
1707 __cfqq = rb_entry(parent, struct cfq_queue, p_node);
Shaohua Li2f7a2d82009-12-28 13:18:44 +01001708 if (cfq_rq_close(cfqd, cur_cfqq, __cfqq->next_rq, false))
Jens Axboea36e71f2009-04-15 12:15:11 +02001709 return __cfqq;
1710
Tejun Heo2e46e8b2009-05-07 22:24:41 +09001711 if (blk_rq_pos(__cfqq->next_rq) < sector)
Jens Axboea36e71f2009-04-15 12:15:11 +02001712 node = rb_next(&__cfqq->p_node);
1713 else
1714 node = rb_prev(&__cfqq->p_node);
1715 if (!node)
1716 return NULL;
1717
1718 __cfqq = rb_entry(node, struct cfq_queue, p_node);
Shaohua Li2f7a2d82009-12-28 13:18:44 +01001719 if (cfq_rq_close(cfqd, cur_cfqq, __cfqq->next_rq, false))
Jens Axboea36e71f2009-04-15 12:15:11 +02001720 return __cfqq;
1721
1722 return NULL;
1723}
1724
1725/*
1726 * cfqd - obvious
1727 * cur_cfqq - passed in so that we don't decide that the current queue is
1728 * closely cooperating with itself.
1729 *
1730 * So, basically we're assuming that that cur_cfqq has dispatched at least
1731 * one request, and that cfqd->last_position reflects a position on the disk
1732 * associated with the I/O issued by cur_cfqq. I'm not sure this is a valid
1733 * assumption.
1734 */
1735static struct cfq_queue *cfq_close_cooperator(struct cfq_data *cfqd,
Jeff Moyerb3b6d042009-10-23 17:14:51 -04001736 struct cfq_queue *cur_cfqq)
Jens Axboea36e71f2009-04-15 12:15:11 +02001737{
1738 struct cfq_queue *cfqq;
1739
Jeff Moyere6c5bc72009-10-23 17:14:52 -04001740 if (!cfq_cfqq_sync(cur_cfqq))
1741 return NULL;
1742 if (CFQQ_SEEKY(cur_cfqq))
1743 return NULL;
1744
Jens Axboea36e71f2009-04-15 12:15:11 +02001745 /*
Gui Jianfengb9d8f4c2009-12-08 08:54:17 +01001746 * Don't search priority tree if it's the only queue in the group.
1747 */
1748 if (cur_cfqq->cfqg->nr_cfqq == 1)
1749 return NULL;
1750
1751 /*
Jens Axboed9e76202007-04-20 14:27:50 +02001752 * We should notice if some of the queues are cooperating, eg
1753 * working closely on the same area of the disk. In that case,
1754 * we can group them together and don't waste time idling.
Jens Axboe6d048f52007-04-25 12:44:27 +02001755 */
Jens Axboea36e71f2009-04-15 12:15:11 +02001756 cfqq = cfqq_close(cfqd, cur_cfqq);
1757 if (!cfqq)
1758 return NULL;
1759
Vivek Goyal8682e1f2009-12-03 12:59:50 -05001760 /* If new queue belongs to different cfq_group, don't choose it */
1761 if (cur_cfqq->cfqg != cfqq->cfqg)
1762 return NULL;
1763
Jeff Moyerdf5fe3e2009-10-23 17:14:50 -04001764 /*
1765 * It only makes sense to merge sync queues.
1766 */
1767 if (!cfq_cfqq_sync(cfqq))
1768 return NULL;
Jeff Moyere6c5bc72009-10-23 17:14:52 -04001769 if (CFQQ_SEEKY(cfqq))
1770 return NULL;
Jeff Moyerdf5fe3e2009-10-23 17:14:50 -04001771
Corrado Zoccoloc0324a02009-10-27 19:16:03 +01001772 /*
1773 * Do not merge queues of different priority classes
1774 */
1775 if (cfq_class_rt(cfqq) != cfq_class_rt(cur_cfqq))
1776 return NULL;
1777
Jens Axboea36e71f2009-04-15 12:15:11 +02001778 return cfqq;
Jens Axboe6d048f52007-04-25 12:44:27 +02001779}
1780
Corrado Zoccoloa6d44e92009-10-26 22:45:11 +01001781/*
1782 * Determine whether we should enforce idle window for this queue.
1783 */
1784
1785static bool cfq_should_idle(struct cfq_data *cfqd, struct cfq_queue *cfqq)
1786{
1787 enum wl_prio_t prio = cfqq_prio(cfqq);
Corrado Zoccolo718eee02009-10-26 22:45:29 +01001788 struct cfq_rb_root *service_tree = cfqq->service_tree;
Corrado Zoccoloa6d44e92009-10-26 22:45:11 +01001789
Vivek Goyalf04a6422009-12-03 12:59:40 -05001790 BUG_ON(!service_tree);
1791 BUG_ON(!service_tree->count);
1792
Corrado Zoccoloa6d44e92009-10-26 22:45:11 +01001793 /* We never do for idle class queues. */
1794 if (prio == IDLE_WORKLOAD)
1795 return false;
1796
1797 /* We do for queues that were marked with idle window flag. */
Shaohua Li3c764b72009-12-04 13:12:06 +01001798 if (cfq_cfqq_idle_window(cfqq) &&
1799 !(blk_queue_nonrot(cfqd->queue) && cfqd->hw_tag))
Corrado Zoccoloa6d44e92009-10-26 22:45:11 +01001800 return true;
1801
1802 /*
1803 * Otherwise, we do only if they are the last ones
1804 * in their service tree.
1805 */
Vivek Goyalf04a6422009-12-03 12:59:40 -05001806 return service_tree->count == 1;
Corrado Zoccoloa6d44e92009-10-26 22:45:11 +01001807}
1808
Jens Axboe6d048f52007-04-25 12:44:27 +02001809static void cfq_arm_slice_timer(struct cfq_data *cfqd)
Jens Axboe22e2c502005-06-27 10:55:12 +02001810{
Jens Axboe17926692007-01-19 11:59:30 +11001811 struct cfq_queue *cfqq = cfqd->active_queue;
Jens Axboe206dc692006-03-28 13:03:44 +02001812 struct cfq_io_context *cic;
Jens Axboe7b14e3b2006-02-28 09:35:11 +01001813 unsigned long sl;
1814
Jens Axboea68bbdd2008-09-24 13:03:33 +02001815 /*
Jens Axboef7d7b7a2008-09-25 11:37:50 +02001816 * SSD device without seek penalty, disable idling. But only do so
1817 * for devices that support queuing, otherwise we still have a problem
1818 * with sync vs async workloads.
Jens Axboea68bbdd2008-09-24 13:03:33 +02001819 */
Jens Axboef7d7b7a2008-09-25 11:37:50 +02001820 if (blk_queue_nonrot(cfqd->queue) && cfqd->hw_tag)
Jens Axboea68bbdd2008-09-24 13:03:33 +02001821 return;
1822
Jens Axboedd67d052006-06-21 09:36:18 +02001823 WARN_ON(!RB_EMPTY_ROOT(&cfqq->sort_list));
Jens Axboe6d048f52007-04-25 12:44:27 +02001824 WARN_ON(cfq_cfqq_slice_new(cfqq));
Jens Axboe22e2c502005-06-27 10:55:12 +02001825
1826 /*
1827 * idle is disabled, either manually or by past process history
1828 */
Corrado Zoccoloa6d44e92009-10-26 22:45:11 +01001829 if (!cfqd->cfq_slice_idle || !cfq_should_idle(cfqd, cfqq))
Jens Axboe6d048f52007-04-25 12:44:27 +02001830 return;
1831
Jens Axboe22e2c502005-06-27 10:55:12 +02001832 /*
Corrado Zoccolo8e550632009-11-26 10:02:58 +01001833 * still active requests from this queue, don't idle
Jens Axboe7b679132008-05-30 12:23:07 +02001834 */
Corrado Zoccolo8e550632009-11-26 10:02:58 +01001835 if (cfqq->dispatched)
Jens Axboe7b679132008-05-30 12:23:07 +02001836 return;
1837
1838 /*
Jens Axboe22e2c502005-06-27 10:55:12 +02001839 * task has exited, don't wait
1840 */
Jens Axboe206dc692006-03-28 13:03:44 +02001841 cic = cfqd->active_cic;
Nikanth Karthikesan66dac982007-11-27 12:47:04 +01001842 if (!cic || !atomic_read(&cic->ioc->nr_tasks))
Jens Axboe6d048f52007-04-25 12:44:27 +02001843 return;
1844
Corrado Zoccolo355b6592009-10-08 08:43:32 +02001845 /*
1846 * If our average think time is larger than the remaining time
1847 * slice, then don't idle. This avoids overrunning the allotted
1848 * time slice.
1849 */
1850 if (sample_valid(cic->ttime_samples) &&
1851 (cfqq->slice_end - jiffies < cic->ttime_mean))
1852 return;
1853
Jens Axboe3b181522005-06-27 10:56:24 +02001854 cfq_mark_cfqq_wait_request(cfqq);
Jens Axboe22e2c502005-06-27 10:55:12 +02001855
Jens Axboe6d048f52007-04-25 12:44:27 +02001856 sl = cfqd->cfq_slice_idle;
Jens Axboe206dc692006-03-28 13:03:44 +02001857
Jens Axboe7b14e3b2006-02-28 09:35:11 +01001858 mod_timer(&cfqd->idle_slice_timer, jiffies + sl);
Jens Axboe9481ffd2009-04-15 12:14:13 +02001859 cfq_log_cfqq(cfqd, cfqq, "arm_idle: %lu", sl);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001860}
1861
Jens Axboe498d3aa22007-04-26 12:54:48 +02001862/*
1863 * Move request from internal lists to the request queue dispatch list.
1864 */
Jens Axboe165125e2007-07-24 09:28:11 +02001865static void cfq_dispatch_insert(struct request_queue *q, struct request *rq)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001866{
Jens Axboe3ed9a292007-04-23 08:33:33 +02001867 struct cfq_data *cfqd = q->elevator->elevator_data;
Jens Axboe5e705372006-07-13 12:39:25 +02001868 struct cfq_queue *cfqq = RQ_CFQQ(rq);
Jens Axboe22e2c502005-06-27 10:55:12 +02001869
Jens Axboe7b679132008-05-30 12:23:07 +02001870 cfq_log_cfqq(cfqd, cfqq, "dispatch_insert");
1871
Jeff Moyer06d21882009-09-11 17:08:59 +02001872 cfqq->next_rq = cfq_find_next_rq(cfqd, cfqq, rq);
Jens Axboe5380a102006-07-13 12:37:56 +02001873 cfq_remove_request(rq);
Jens Axboe6d048f52007-04-25 12:44:27 +02001874 cfqq->dispatched++;
Jens Axboe5380a102006-07-13 12:37:56 +02001875 elv_dispatch_sort(q, rq);
Jens Axboe3ed9a292007-04-23 08:33:33 +02001876
1877 if (cfq_cfqq_sync(cfqq))
1878 cfqd->sync_flight++;
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);
2061 cfqd->workload_expires = jiffies + slice;
Corrado Zoccolo8e550632009-11-26 10:02:58 +01002062 cfqd->noidle_tree_requires_idle = false;
Corrado Zoccolo718eee02009-10-26 22:45:29 +01002063}
2064
Vivek Goyal1fa8f6d2009-12-03 12:59:41 -05002065static struct cfq_group *cfq_get_next_cfqg(struct cfq_data *cfqd)
2066{
2067 struct cfq_rb_root *st = &cfqd->grp_service_tree;
Vivek Goyal25bc6b02009-12-03 12:59:43 -05002068 struct cfq_group *cfqg;
Vivek Goyal1fa8f6d2009-12-03 12:59:41 -05002069
2070 if (RB_EMPTY_ROOT(&st->rb))
2071 return NULL;
Vivek Goyal25bc6b02009-12-03 12:59:43 -05002072 cfqg = cfq_rb_first_group(st);
2073 st->active = &cfqg->rb_node;
2074 update_min_vdisktime(st);
2075 return cfqg;
Vivek Goyal1fa8f6d2009-12-03 12:59:41 -05002076}
2077
Vivek Goyalcdb16e82009-12-03 12:59:38 -05002078static void cfq_choose_cfqg(struct cfq_data *cfqd)
2079{
Vivek Goyal1fa8f6d2009-12-03 12:59:41 -05002080 struct cfq_group *cfqg = cfq_get_next_cfqg(cfqd);
2081
2082 cfqd->serving_group = cfqg;
Vivek Goyaldae739e2009-12-03 12:59:45 -05002083
2084 /* Restore the workload type data */
2085 if (cfqg->saved_workload_slice) {
2086 cfqd->workload_expires = jiffies + cfqg->saved_workload_slice;
2087 cfqd->serving_type = cfqg->saved_workload;
2088 cfqd->serving_prio = cfqg->saved_serving_prio;
Gui Jianfeng66ae2912009-12-15 10:08:45 +01002089 } else
2090 cfqd->workload_expires = jiffies - 1;
2091
Vivek Goyal1fa8f6d2009-12-03 12:59:41 -05002092 choose_service_tree(cfqd, cfqg);
Vivek Goyalcdb16e82009-12-03 12:59:38 -05002093}
2094
Jeff Moyerdf5fe3e2009-10-23 17:14:50 -04002095/*
Jens Axboe498d3aa22007-04-26 12:54:48 +02002096 * Select a queue for service. If we have a current active queue,
2097 * check whether to continue servicing it, or retrieve and set a new one.
Jens Axboe22e2c502005-06-27 10:55:12 +02002098 */
Tejun Heo1b5ed5e12005-11-10 08:49:19 +01002099static struct cfq_queue *cfq_select_queue(struct cfq_data *cfqd)
Jens Axboe22e2c502005-06-27 10:55:12 +02002100{
Jens Axboea36e71f2009-04-15 12:15:11 +02002101 struct cfq_queue *cfqq, *new_cfqq = NULL;
Jens Axboe22e2c502005-06-27 10:55:12 +02002102
2103 cfqq = cfqd->active_queue;
2104 if (!cfqq)
2105 goto new_queue;
2106
Vivek Goyalf04a6422009-12-03 12:59:40 -05002107 if (!cfqd->rq_queued)
2108 return NULL;
Vivek Goyalc244bb52009-12-08 17:52:57 -05002109
2110 /*
2111 * We were waiting for group to get backlogged. Expire the queue
2112 */
2113 if (cfq_cfqq_wait_busy(cfqq) && !RB_EMPTY_ROOT(&cfqq->sort_list))
2114 goto expire;
2115
Jens Axboe22e2c502005-06-27 10:55:12 +02002116 /*
Jens Axboe6d048f52007-04-25 12:44:27 +02002117 * The active queue has run out of time, expire it and select new.
Jens Axboe22e2c502005-06-27 10:55:12 +02002118 */
Vivek Goyal7667aa02009-12-08 17:52:58 -05002119 if (cfq_slice_used(cfqq) && !cfq_cfqq_must_dispatch(cfqq)) {
2120 /*
2121 * If slice had not expired at the completion of last request
2122 * we might not have turned on wait_busy flag. Don't expire
2123 * the queue yet. Allow the group to get backlogged.
2124 *
2125 * The very fact that we have used the slice, that means we
2126 * have been idling all along on this queue and it should be
2127 * ok to wait for this request to complete.
2128 */
Vivek Goyal82bbbf22009-12-10 19:25:41 +01002129 if (cfqq->cfqg->nr_cfqq == 1 && RB_EMPTY_ROOT(&cfqq->sort_list)
2130 && cfqq->dispatched && cfq_should_idle(cfqd, cfqq)) {
2131 cfqq = NULL;
Vivek Goyal7667aa02009-12-08 17:52:58 -05002132 goto keep_queue;
Vivek Goyal82bbbf22009-12-10 19:25:41 +01002133 } else
Vivek Goyal7667aa02009-12-08 17:52:58 -05002134 goto expire;
2135 }
Jens Axboe22e2c502005-06-27 10:55:12 +02002136
2137 /*
Jens Axboe6d048f52007-04-25 12:44:27 +02002138 * The active queue has requests and isn't expired, allow it to
2139 * dispatch.
Jens Axboe22e2c502005-06-27 10:55:12 +02002140 */
Jens Axboedd67d052006-06-21 09:36:18 +02002141 if (!RB_EMPTY_ROOT(&cfqq->sort_list))
Jens Axboe22e2c502005-06-27 10:55:12 +02002142 goto keep_queue;
Jens Axboe6d048f52007-04-25 12:44:27 +02002143
2144 /*
Jens Axboea36e71f2009-04-15 12:15:11 +02002145 * If another queue has a request waiting within our mean seek
2146 * distance, let it run. The expire code will check for close
2147 * cooperators and put the close queue at the front of the service
Jeff Moyerdf5fe3e2009-10-23 17:14:50 -04002148 * tree. If possible, merge the expiring queue with the new cfqq.
Jens Axboea36e71f2009-04-15 12:15:11 +02002149 */
Jeff Moyerb3b6d042009-10-23 17:14:51 -04002150 new_cfqq = cfq_close_cooperator(cfqd, cfqq);
Jeff Moyerdf5fe3e2009-10-23 17:14:50 -04002151 if (new_cfqq) {
2152 if (!cfqq->new_cfqq)
2153 cfq_setup_merge(cfqq, new_cfqq);
Jens Axboea36e71f2009-04-15 12:15:11 +02002154 goto expire;
Jeff Moyerdf5fe3e2009-10-23 17:14:50 -04002155 }
Jens Axboea36e71f2009-04-15 12:15:11 +02002156
2157 /*
Jens Axboe6d048f52007-04-25 12:44:27 +02002158 * No requests pending. If the active queue still has requests in
2159 * flight or is idling for a new request, allow either of these
2160 * conditions to happen (or time out) before selecting a new queue.
2161 */
Jens Axboecc197472007-04-20 20:45:39 +02002162 if (timer_pending(&cfqd->idle_slice_timer) ||
Corrado Zoccoloa6d44e92009-10-26 22:45:11 +01002163 (cfqq->dispatched && cfq_should_idle(cfqd, cfqq))) {
Jens Axboecaaa5f92006-06-16 11:23:00 +02002164 cfqq = NULL;
2165 goto keep_queue;
Jens Axboe22e2c502005-06-27 10:55:12 +02002166 }
2167
Jens Axboe3b181522005-06-27 10:56:24 +02002168expire:
Jens Axboe6084cdd2007-04-23 08:25:00 +02002169 cfq_slice_expired(cfqd, 0);
Jens Axboe3b181522005-06-27 10:56:24 +02002170new_queue:
Corrado Zoccolo718eee02009-10-26 22:45:29 +01002171 /*
2172 * Current queue expired. Check if we have to switch to a new
2173 * service tree
2174 */
2175 if (!new_cfqq)
Vivek Goyalcdb16e82009-12-03 12:59:38 -05002176 cfq_choose_cfqg(cfqd);
Corrado Zoccolo718eee02009-10-26 22:45:29 +01002177
Jens Axboea36e71f2009-04-15 12:15:11 +02002178 cfqq = cfq_set_active_queue(cfqd, new_cfqq);
Jens Axboe22e2c502005-06-27 10:55:12 +02002179keep_queue:
Jens Axboe3b181522005-06-27 10:56:24 +02002180 return cfqq;
Jens Axboe22e2c502005-06-27 10:55:12 +02002181}
2182
Jens Axboefebffd62008-01-28 13:19:43 +01002183static int __cfq_forced_dispatch_cfqq(struct cfq_queue *cfqq)
Jens Axboed9e76202007-04-20 14:27:50 +02002184{
2185 int dispatched = 0;
2186
2187 while (cfqq->next_rq) {
2188 cfq_dispatch_insert(cfqq->cfqd->queue, cfqq->next_rq);
2189 dispatched++;
2190 }
2191
2192 BUG_ON(!list_empty(&cfqq->fifo));
Vivek Goyalf04a6422009-12-03 12:59:40 -05002193
2194 /* By default cfqq is not expired if it is empty. Do it explicitly */
2195 __cfq_slice_expired(cfqq->cfqd, cfqq, 0);
Jens Axboed9e76202007-04-20 14:27:50 +02002196 return dispatched;
2197}
2198
Jens Axboe498d3aa22007-04-26 12:54:48 +02002199/*
2200 * Drain our current requests. Used for barriers and when switching
2201 * io schedulers on-the-fly.
2202 */
Jens Axboed9e76202007-04-20 14:27:50 +02002203static int cfq_forced_dispatch(struct cfq_data *cfqd)
Tejun Heo1b5ed5e12005-11-10 08:49:19 +01002204{
Jens Axboe08717142008-01-28 11:38:15 +01002205 struct cfq_queue *cfqq;
Jens Axboed9e76202007-04-20 14:27:50 +02002206 int dispatched = 0;
Vivek Goyalcdb16e82009-12-03 12:59:38 -05002207
Vivek Goyalf04a6422009-12-03 12:59:40 -05002208 while ((cfqq = cfq_get_next_queue_forced(cfqd)) != NULL)
2209 dispatched += __cfq_forced_dispatch_cfqq(cfqq);
Tejun Heo1b5ed5e12005-11-10 08:49:19 +01002210
Jens Axboe6084cdd2007-04-23 08:25:00 +02002211 cfq_slice_expired(cfqd, 0);
Tejun Heo1b5ed5e12005-11-10 08:49:19 +01002212 BUG_ON(cfqd->busy_queues);
2213
Jeff Moyer69237152009-06-12 15:29:30 +02002214 cfq_log(cfqd, "forced_dispatch=%d", dispatched);
Tejun Heo1b5ed5e12005-11-10 08:49:19 +01002215 return dispatched;
2216}
2217
Jens Axboe0b182d62009-10-06 20:49:37 +02002218static bool cfq_may_dispatch(struct cfq_data *cfqd, struct cfq_queue *cfqq)
Jens Axboe2f5cb732009-04-07 08:51:19 +02002219{
Jens Axboe2f5cb732009-04-07 08:51:19 +02002220 unsigned int max_dispatch;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002221
Jens Axboe2f5cb732009-04-07 08:51:19 +02002222 /*
Jens Axboe5ad531d2009-07-03 12:57:48 +02002223 * Drain async requests before we start sync IO
2224 */
Corrado Zoccoloa6d44e92009-10-26 22:45:11 +01002225 if (cfq_should_idle(cfqd, cfqq) && cfqd->rq_in_driver[BLK_RW_ASYNC])
Jens Axboe0b182d62009-10-06 20:49:37 +02002226 return false;
Jens Axboe5ad531d2009-07-03 12:57:48 +02002227
2228 /*
Jens Axboe2f5cb732009-04-07 08:51:19 +02002229 * If this is an async queue and we have sync IO in flight, let it wait
2230 */
2231 if (cfqd->sync_flight && !cfq_cfqq_sync(cfqq))
Jens Axboe0b182d62009-10-06 20:49:37 +02002232 return false;
Jens Axboe2f5cb732009-04-07 08:51:19 +02002233
2234 max_dispatch = cfqd->cfq_quantum;
2235 if (cfq_class_idle(cfqq))
2236 max_dispatch = 1;
2237
2238 /*
2239 * Does this cfqq already have too much IO in flight?
2240 */
2241 if (cfqq->dispatched >= max_dispatch) {
2242 /*
2243 * idle queue must always only have a single IO in flight
2244 */
Jens Axboe3ed9a292007-04-23 08:33:33 +02002245 if (cfq_class_idle(cfqq))
Jens Axboe0b182d62009-10-06 20:49:37 +02002246 return false;
Jens Axboe3ed9a292007-04-23 08:33:33 +02002247
Jens Axboe2f5cb732009-04-07 08:51:19 +02002248 /*
2249 * We have other queues, don't allow more IO from this one
2250 */
2251 if (cfqd->busy_queues > 1)
Jens Axboe0b182d62009-10-06 20:49:37 +02002252 return false;
Jens Axboe9ede2092007-01-19 12:11:44 +11002253
Jens Axboe2f5cb732009-04-07 08:51:19 +02002254 /*
Shaohua Li474b18c2009-12-03 12:58:05 +01002255 * Sole queue user, no limit
Vivek Goyal365722b2009-10-03 15:21:27 +02002256 */
Shaohua Li474b18c2009-12-03 12:58:05 +01002257 max_dispatch = -1;
Jens Axboe8e296752009-10-03 16:26:03 +02002258 }
2259
2260 /*
2261 * Async queues must wait a bit before being allowed dispatch.
2262 * We also ramp up the dispatch depth gradually for async IO,
2263 * based on the last sync IO we serviced
2264 */
Jens Axboe963b72f2009-10-03 19:42:18 +02002265 if (!cfq_cfqq_sync(cfqq) && cfqd->cfq_latency) {
Corrado Zoccolo573412b2009-12-06 11:48:52 +01002266 unsigned long last_sync = jiffies - cfqd->last_delayed_sync;
Jens Axboe8e296752009-10-03 16:26:03 +02002267 unsigned int depth;
Vivek Goyal365722b2009-10-03 15:21:27 +02002268
Jens Axboe61f0c1d2009-10-03 19:46:03 +02002269 depth = last_sync / cfqd->cfq_slice[1];
Jens Axboee00c54c2009-10-04 20:36:19 +02002270 if (!depth && !cfqq->dispatched)
2271 depth = 1;
Jens Axboe8e296752009-10-03 16:26:03 +02002272 if (depth < max_dispatch)
2273 max_dispatch = depth;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002274 }
2275
Jens Axboe0b182d62009-10-06 20:49:37 +02002276 /*
2277 * If we're below the current max, allow a dispatch
2278 */
2279 return cfqq->dispatched < max_dispatch;
2280}
2281
2282/*
2283 * Dispatch a request from cfqq, moving them to the request queue
2284 * dispatch list.
2285 */
2286static bool cfq_dispatch_request(struct cfq_data *cfqd, struct cfq_queue *cfqq)
2287{
2288 struct request *rq;
2289
2290 BUG_ON(RB_EMPTY_ROOT(&cfqq->sort_list));
2291
2292 if (!cfq_may_dispatch(cfqd, cfqq))
2293 return false;
2294
2295 /*
2296 * follow expired path, else get first next available
2297 */
2298 rq = cfq_check_fifo(cfqq);
2299 if (!rq)
2300 rq = cfqq->next_rq;
2301
2302 /*
2303 * insert request into driver dispatch list
2304 */
2305 cfq_dispatch_insert(cfqd->queue, rq);
2306
2307 if (!cfqd->active_cic) {
2308 struct cfq_io_context *cic = RQ_CIC(rq);
2309
2310 atomic_long_inc(&cic->ioc->refcount);
2311 cfqd->active_cic = cic;
2312 }
2313
2314 return true;
2315}
2316
2317/*
2318 * Find the cfqq that we need to service and move a request from that to the
2319 * dispatch list
2320 */
2321static int cfq_dispatch_requests(struct request_queue *q, int force)
2322{
2323 struct cfq_data *cfqd = q->elevator->elevator_data;
2324 struct cfq_queue *cfqq;
2325
2326 if (!cfqd->busy_queues)
2327 return 0;
2328
2329 if (unlikely(force))
2330 return cfq_forced_dispatch(cfqd);
2331
2332 cfqq = cfq_select_queue(cfqd);
2333 if (!cfqq)
Jens Axboe8e296752009-10-03 16:26:03 +02002334 return 0;
2335
Jens Axboe2f5cb732009-04-07 08:51:19 +02002336 /*
Jens Axboe0b182d62009-10-06 20:49:37 +02002337 * Dispatch a request from this cfqq, if it is allowed
Jens Axboe2f5cb732009-04-07 08:51:19 +02002338 */
Jens Axboe0b182d62009-10-06 20:49:37 +02002339 if (!cfq_dispatch_request(cfqd, cfqq))
2340 return 0;
2341
Jens Axboe2f5cb732009-04-07 08:51:19 +02002342 cfqq->slice_dispatch++;
Jens Axboeb0291952009-04-07 11:38:31 +02002343 cfq_clear_cfqq_must_dispatch(cfqq);
Jens Axboe2f5cb732009-04-07 08:51:19 +02002344
2345 /*
2346 * expire an async queue immediately if it has used up its slice. idle
2347 * queue always expire after 1 dispatch round.
2348 */
2349 if (cfqd->busy_queues > 1 && ((!cfq_cfqq_sync(cfqq) &&
2350 cfqq->slice_dispatch >= cfq_prio_to_maxrq(cfqd, cfqq)) ||
2351 cfq_class_idle(cfqq))) {
2352 cfqq->slice_end = jiffies + 1;
2353 cfq_slice_expired(cfqd, 0);
2354 }
2355
Shan Weib217a902009-09-01 10:06:42 +02002356 cfq_log_cfqq(cfqd, cfqq, "dispatched a request");
Jens Axboe2f5cb732009-04-07 08:51:19 +02002357 return 1;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002358}
2359
Linus Torvalds1da177e2005-04-16 15:20:36 -07002360/*
Jens Axboe5e705372006-07-13 12:39:25 +02002361 * task holds one reference to the queue, dropped when task exits. each rq
2362 * in-flight on this queue also holds a reference, dropped when rq is freed.
Linus Torvalds1da177e2005-04-16 15:20:36 -07002363 *
Vivek Goyalb1c35762009-12-03 12:59:47 -05002364 * Each cfq queue took a reference on the parent group. Drop it now.
Linus Torvalds1da177e2005-04-16 15:20:36 -07002365 * queue lock must be held here.
2366 */
2367static void cfq_put_queue(struct cfq_queue *cfqq)
2368{
Jens Axboe22e2c502005-06-27 10:55:12 +02002369 struct cfq_data *cfqd = cfqq->cfqd;
Vivek Goyal878eadd2009-12-07 19:37:15 +01002370 struct cfq_group *cfqg, *orig_cfqg;
Jens Axboe22e2c502005-06-27 10:55:12 +02002371
2372 BUG_ON(atomic_read(&cfqq->ref) <= 0);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002373
2374 if (!atomic_dec_and_test(&cfqq->ref))
2375 return;
2376
Jens Axboe7b679132008-05-30 12:23:07 +02002377 cfq_log_cfqq(cfqd, cfqq, "put_queue");
Linus Torvalds1da177e2005-04-16 15:20:36 -07002378 BUG_ON(rb_first(&cfqq->sort_list));
Jens Axboe22e2c502005-06-27 10:55:12 +02002379 BUG_ON(cfqq->allocated[READ] + cfqq->allocated[WRITE]);
Vivek Goyalb1c35762009-12-03 12:59:47 -05002380 cfqg = cfqq->cfqg;
Vivek Goyal878eadd2009-12-07 19:37:15 +01002381 orig_cfqg = cfqq->orig_cfqg;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002382
Jens Axboe28f95cbc2007-01-19 12:09:53 +11002383 if (unlikely(cfqd->active_queue == cfqq)) {
Jens Axboe6084cdd2007-04-23 08:25:00 +02002384 __cfq_slice_expired(cfqd, cfqq, 0);
Jens Axboe23e018a2009-10-05 08:52:35 +02002385 cfq_schedule_dispatch(cfqd);
Jens Axboe28f95cbc2007-01-19 12:09:53 +11002386 }
Jens Axboe22e2c502005-06-27 10:55:12 +02002387
Vivek Goyalf04a6422009-12-03 12:59:40 -05002388 BUG_ON(cfq_cfqq_on_rr(cfqq));
Linus Torvalds1da177e2005-04-16 15:20:36 -07002389 kmem_cache_free(cfq_pool, cfqq);
Vivek Goyalb1c35762009-12-03 12:59:47 -05002390 cfq_put_cfqg(cfqg);
Vivek Goyal878eadd2009-12-07 19:37:15 +01002391 if (orig_cfqg)
2392 cfq_put_cfqg(orig_cfqg);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002393}
2394
Jens Axboed6de8be2008-05-28 14:46:59 +02002395/*
2396 * Must always be called with the rcu_read_lock() held
2397 */
Jens Axboe07416d22008-05-07 09:17:12 +02002398static void
2399__call_for_each_cic(struct io_context *ioc,
2400 void (*func)(struct io_context *, struct cfq_io_context *))
2401{
2402 struct cfq_io_context *cic;
2403 struct hlist_node *n;
2404
2405 hlist_for_each_entry_rcu(cic, n, &ioc->cic_list, cic_list)
2406 func(ioc, cic);
2407}
2408
Jens Axboe4ac845a2008-01-24 08:44:49 +01002409/*
Fabio Checconi34e6bbf2008-04-02 14:31:02 +02002410 * Call func for each cic attached to this ioc.
Jens Axboe4ac845a2008-01-24 08:44:49 +01002411 */
Fabio Checconi34e6bbf2008-04-02 14:31:02 +02002412static void
Jens Axboe4ac845a2008-01-24 08:44:49 +01002413call_for_each_cic(struct io_context *ioc,
2414 void (*func)(struct io_context *, struct cfq_io_context *))
2415{
Jens Axboe4ac845a2008-01-24 08:44:49 +01002416 rcu_read_lock();
Jens Axboe07416d22008-05-07 09:17:12 +02002417 __call_for_each_cic(ioc, func);
Jens Axboe4ac845a2008-01-24 08:44:49 +01002418 rcu_read_unlock();
Fabio Checconi34e6bbf2008-04-02 14:31:02 +02002419}
Jens Axboe4ac845a2008-01-24 08:44:49 +01002420
Fabio Checconi34e6bbf2008-04-02 14:31:02 +02002421static void cfq_cic_free_rcu(struct rcu_head *head)
2422{
2423 struct cfq_io_context *cic;
2424
2425 cic = container_of(head, struct cfq_io_context, rcu_head);
2426
2427 kmem_cache_free(cfq_ioc_pool, cic);
Tejun Heo245b2e72009-06-24 15:13:48 +09002428 elv_ioc_count_dec(cfq_ioc_count);
Fabio Checconi34e6bbf2008-04-02 14:31:02 +02002429
Jens Axboe9a11b4e2008-05-29 09:32:08 +02002430 if (ioc_gone) {
2431 /*
2432 * CFQ scheduler is exiting, grab exit lock and check
2433 * the pending io context count. If it hits zero,
2434 * complete ioc_gone and set it back to NULL
2435 */
2436 spin_lock(&ioc_gone_lock);
Tejun Heo245b2e72009-06-24 15:13:48 +09002437 if (ioc_gone && !elv_ioc_count_read(cfq_ioc_count)) {
Jens Axboe9a11b4e2008-05-29 09:32:08 +02002438 complete(ioc_gone);
2439 ioc_gone = NULL;
2440 }
2441 spin_unlock(&ioc_gone_lock);
2442 }
Fabio Checconi34e6bbf2008-04-02 14:31:02 +02002443}
2444
2445static void cfq_cic_free(struct cfq_io_context *cic)
2446{
2447 call_rcu(&cic->rcu_head, cfq_cic_free_rcu);
Jens Axboe4ac845a2008-01-24 08:44:49 +01002448}
2449
2450static void cic_free_func(struct io_context *ioc, struct cfq_io_context *cic)
2451{
2452 unsigned long flags;
2453
2454 BUG_ON(!cic->dead_key);
2455
2456 spin_lock_irqsave(&ioc->lock, flags);
2457 radix_tree_delete(&ioc->radix_root, cic->dead_key);
Jens Axboeffc4e752008-02-19 10:02:29 +01002458 hlist_del_rcu(&cic->cic_list);
Jens Axboe4ac845a2008-01-24 08:44:49 +01002459 spin_unlock_irqrestore(&ioc->lock, flags);
2460
Fabio Checconi34e6bbf2008-04-02 14:31:02 +02002461 cfq_cic_free(cic);
Jens Axboe4ac845a2008-01-24 08:44:49 +01002462}
2463
Jens Axboed6de8be2008-05-28 14:46:59 +02002464/*
2465 * Must be called with rcu_read_lock() held or preemption otherwise disabled.
2466 * Only two callers of this - ->dtor() which is called with the rcu_read_lock(),
2467 * and ->trim() which is called with the task lock held
2468 */
Jens Axboee2d74ac2006-03-28 08:59:01 +02002469static void cfq_free_io_context(struct io_context *ioc)
Linus Torvalds1da177e2005-04-16 15:20:36 -07002470{
Jens Axboe4ac845a2008-01-24 08:44:49 +01002471 /*
Fabio Checconi34e6bbf2008-04-02 14:31:02 +02002472 * ioc->refcount is zero here, or we are called from elv_unregister(),
2473 * so no more cic's are allowed to be linked into this ioc. So it
2474 * should be ok to iterate over the known list, we will see all cic's
2475 * since no new ones are added.
Jens Axboe4ac845a2008-01-24 08:44:49 +01002476 */
Jens Axboe07416d22008-05-07 09:17:12 +02002477 __call_for_each_cic(ioc, cic_free_func);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002478}
2479
Jens Axboe89850f72006-07-22 16:48:31 +02002480static void cfq_exit_cfqq(struct cfq_data *cfqd, struct cfq_queue *cfqq)
2481{
Jeff Moyerdf5fe3e2009-10-23 17:14:50 -04002482 struct cfq_queue *__cfqq, *next;
2483
Jens Axboe28f95cbc2007-01-19 12:09:53 +11002484 if (unlikely(cfqq == cfqd->active_queue)) {
Jens Axboe6084cdd2007-04-23 08:25:00 +02002485 __cfq_slice_expired(cfqd, cfqq, 0);
Jens Axboe23e018a2009-10-05 08:52:35 +02002486 cfq_schedule_dispatch(cfqd);
Jens Axboe28f95cbc2007-01-19 12:09:53 +11002487 }
Jens Axboe89850f72006-07-22 16:48:31 +02002488
Jeff Moyerdf5fe3e2009-10-23 17:14:50 -04002489 /*
2490 * If this queue was scheduled to merge with another queue, be
2491 * sure to drop the reference taken on that queue (and others in
2492 * the merge chain). See cfq_setup_merge and cfq_merge_cfqqs.
2493 */
2494 __cfqq = cfqq->new_cfqq;
2495 while (__cfqq) {
2496 if (__cfqq == cfqq) {
2497 WARN(1, "cfqq->new_cfqq loop detected\n");
2498 break;
2499 }
2500 next = __cfqq->new_cfqq;
2501 cfq_put_queue(__cfqq);
2502 __cfqq = next;
2503 }
2504
Jens Axboe89850f72006-07-22 16:48:31 +02002505 cfq_put_queue(cfqq);
2506}
2507
2508static void __cfq_exit_single_io_context(struct cfq_data *cfqd,
2509 struct cfq_io_context *cic)
2510{
Fabio Checconi4faa3c82008-04-10 08:28:01 +02002511 struct io_context *ioc = cic->ioc;
2512
Jens Axboefc463792006-08-29 09:05:44 +02002513 list_del_init(&cic->queue_list);
Jens Axboe4ac845a2008-01-24 08:44:49 +01002514
2515 /*
2516 * Make sure key == NULL is seen for dead queues
2517 */
Jens Axboefc463792006-08-29 09:05:44 +02002518 smp_wmb();
Jens Axboe4ac845a2008-01-24 08:44:49 +01002519 cic->dead_key = (unsigned long) cic->key;
Jens Axboefc463792006-08-29 09:05:44 +02002520 cic->key = NULL;
2521
Fabio Checconi4faa3c82008-04-10 08:28:01 +02002522 if (ioc->ioc_data == cic)
2523 rcu_assign_pointer(ioc->ioc_data, NULL);
2524
Jens Axboeff6657c2009-04-08 10:58:57 +02002525 if (cic->cfqq[BLK_RW_ASYNC]) {
2526 cfq_exit_cfqq(cfqd, cic->cfqq[BLK_RW_ASYNC]);
2527 cic->cfqq[BLK_RW_ASYNC] = NULL;
Jens Axboe89850f72006-07-22 16:48:31 +02002528 }
2529
Jens Axboeff6657c2009-04-08 10:58:57 +02002530 if (cic->cfqq[BLK_RW_SYNC]) {
2531 cfq_exit_cfqq(cfqd, cic->cfqq[BLK_RW_SYNC]);
2532 cic->cfqq[BLK_RW_SYNC] = NULL;
Jens Axboe89850f72006-07-22 16:48:31 +02002533 }
Jens Axboe89850f72006-07-22 16:48:31 +02002534}
2535
Jens Axboe4ac845a2008-01-24 08:44:49 +01002536static void cfq_exit_single_io_context(struct io_context *ioc,
2537 struct cfq_io_context *cic)
Jens Axboe22e2c502005-06-27 10:55:12 +02002538{
Al Viro478a82b2006-03-18 13:25:24 -05002539 struct cfq_data *cfqd = cic->key;
Jens Axboe22e2c502005-06-27 10:55:12 +02002540
Jens Axboe89850f72006-07-22 16:48:31 +02002541 if (cfqd) {
Jens Axboe165125e2007-07-24 09:28:11 +02002542 struct request_queue *q = cfqd->queue;
Jens Axboe4ac845a2008-01-24 08:44:49 +01002543 unsigned long flags;
Jens Axboe22e2c502005-06-27 10:55:12 +02002544
Jens Axboe4ac845a2008-01-24 08:44:49 +01002545 spin_lock_irqsave(q->queue_lock, flags);
Jens Axboe62c1fe92008-12-15 21:19:25 +01002546
2547 /*
2548 * Ensure we get a fresh copy of the ->key to prevent
2549 * race between exiting task and queue
2550 */
2551 smp_read_barrier_depends();
2552 if (cic->key)
2553 __cfq_exit_single_io_context(cfqd, cic);
2554
Jens Axboe4ac845a2008-01-24 08:44:49 +01002555 spin_unlock_irqrestore(q->queue_lock, flags);
Al Viro12a05732006-03-18 13:38:01 -05002556 }
Jens Axboe22e2c502005-06-27 10:55:12 +02002557}
2558
Jens Axboe498d3aa22007-04-26 12:54:48 +02002559/*
2560 * The process that ioc belongs to has exited, we need to clean up
2561 * and put the internal structures we have that belongs to that process.
2562 */
Jens Axboee2d74ac2006-03-28 08:59:01 +02002563static void cfq_exit_io_context(struct io_context *ioc)
Linus Torvalds1da177e2005-04-16 15:20:36 -07002564{
Jens Axboe4ac845a2008-01-24 08:44:49 +01002565 call_for_each_cic(ioc, cfq_exit_single_io_context);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002566}
2567
Jens Axboe22e2c502005-06-27 10:55:12 +02002568static struct cfq_io_context *
Al Viro8267e262005-10-21 03:20:53 -04002569cfq_alloc_io_context(struct cfq_data *cfqd, gfp_t gfp_mask)
Linus Torvalds1da177e2005-04-16 15:20:36 -07002570{
Jens Axboeb5deef92006-07-19 23:39:40 +02002571 struct cfq_io_context *cic;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002572
Christoph Lameter94f60302007-07-17 04:03:29 -07002573 cic = kmem_cache_alloc_node(cfq_ioc_pool, gfp_mask | __GFP_ZERO,
2574 cfqd->queue->node);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002575 if (cic) {
Jens Axboe22e2c502005-06-27 10:55:12 +02002576 cic->last_end_request = jiffies;
Jens Axboe553698f2006-06-14 19:11:57 +02002577 INIT_LIST_HEAD(&cic->queue_list);
Jens Axboeffc4e752008-02-19 10:02:29 +01002578 INIT_HLIST_NODE(&cic->cic_list);
Jens Axboe22e2c502005-06-27 10:55:12 +02002579 cic->dtor = cfq_free_io_context;
2580 cic->exit = cfq_exit_io_context;
Tejun Heo245b2e72009-06-24 15:13:48 +09002581 elv_ioc_count_inc(cfq_ioc_count);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002582 }
2583
2584 return cic;
2585}
2586
Jens Axboefd0928d2008-01-24 08:52:45 +01002587static void cfq_init_prio_data(struct cfq_queue *cfqq, struct io_context *ioc)
Jens Axboe22e2c502005-06-27 10:55:12 +02002588{
2589 struct task_struct *tsk = current;
2590 int ioprio_class;
2591
Jens Axboe3b181522005-06-27 10:56:24 +02002592 if (!cfq_cfqq_prio_changed(cfqq))
Jens Axboe22e2c502005-06-27 10:55:12 +02002593 return;
2594
Jens Axboefd0928d2008-01-24 08:52:45 +01002595 ioprio_class = IOPRIO_PRIO_CLASS(ioc->ioprio);
Jens Axboe22e2c502005-06-27 10:55:12 +02002596 switch (ioprio_class) {
Jens Axboefe094d92008-01-31 13:08:54 +01002597 default:
2598 printk(KERN_ERR "cfq: bad prio %x\n", ioprio_class);
2599 case IOPRIO_CLASS_NONE:
2600 /*
Jens Axboe6d63c272008-05-07 09:51:23 +02002601 * no prio set, inherit CPU scheduling settings
Jens Axboefe094d92008-01-31 13:08:54 +01002602 */
2603 cfqq->ioprio = task_nice_ioprio(tsk);
Jens Axboe6d63c272008-05-07 09:51:23 +02002604 cfqq->ioprio_class = task_nice_ioclass(tsk);
Jens Axboefe094d92008-01-31 13:08:54 +01002605 break;
2606 case IOPRIO_CLASS_RT:
2607 cfqq->ioprio = task_ioprio(ioc);
2608 cfqq->ioprio_class = IOPRIO_CLASS_RT;
2609 break;
2610 case IOPRIO_CLASS_BE:
2611 cfqq->ioprio = task_ioprio(ioc);
2612 cfqq->ioprio_class = IOPRIO_CLASS_BE;
2613 break;
2614 case IOPRIO_CLASS_IDLE:
2615 cfqq->ioprio_class = IOPRIO_CLASS_IDLE;
2616 cfqq->ioprio = 7;
2617 cfq_clear_cfqq_idle_window(cfqq);
2618 break;
Jens Axboe22e2c502005-06-27 10:55:12 +02002619 }
2620
2621 /*
2622 * keep track of original prio settings in case we have to temporarily
2623 * elevate the priority of this queue
2624 */
2625 cfqq->org_ioprio = cfqq->ioprio;
2626 cfqq->org_ioprio_class = cfqq->ioprio_class;
Jens Axboe3b181522005-06-27 10:56:24 +02002627 cfq_clear_cfqq_prio_changed(cfqq);
Jens Axboe22e2c502005-06-27 10:55:12 +02002628}
2629
Jens Axboefebffd62008-01-28 13:19:43 +01002630static void changed_ioprio(struct io_context *ioc, struct cfq_io_context *cic)
Jens Axboe22e2c502005-06-27 10:55:12 +02002631{
Al Viro478a82b2006-03-18 13:25:24 -05002632 struct cfq_data *cfqd = cic->key;
2633 struct cfq_queue *cfqq;
Jens Axboec1b707d2006-10-30 19:54:23 +01002634 unsigned long flags;
Jens Axboe35e60772006-06-14 09:10:45 +02002635
Jens Axboecaaa5f92006-06-16 11:23:00 +02002636 if (unlikely(!cfqd))
2637 return;
2638
Jens Axboec1b707d2006-10-30 19:54:23 +01002639 spin_lock_irqsave(cfqd->queue->queue_lock, flags);
Jens Axboecaaa5f92006-06-16 11:23:00 +02002640
Jens Axboeff6657c2009-04-08 10:58:57 +02002641 cfqq = cic->cfqq[BLK_RW_ASYNC];
Jens Axboecaaa5f92006-06-16 11:23:00 +02002642 if (cfqq) {
2643 struct cfq_queue *new_cfqq;
Jens Axboeff6657c2009-04-08 10:58:57 +02002644 new_cfqq = cfq_get_queue(cfqd, BLK_RW_ASYNC, cic->ioc,
2645 GFP_ATOMIC);
Jens Axboecaaa5f92006-06-16 11:23:00 +02002646 if (new_cfqq) {
Jens Axboeff6657c2009-04-08 10:58:57 +02002647 cic->cfqq[BLK_RW_ASYNC] = new_cfqq;
Jens Axboecaaa5f92006-06-16 11:23:00 +02002648 cfq_put_queue(cfqq);
2649 }
Jens Axboe22e2c502005-06-27 10:55:12 +02002650 }
Jens Axboecaaa5f92006-06-16 11:23:00 +02002651
Jens Axboeff6657c2009-04-08 10:58:57 +02002652 cfqq = cic->cfqq[BLK_RW_SYNC];
Jens Axboecaaa5f92006-06-16 11:23:00 +02002653 if (cfqq)
2654 cfq_mark_cfqq_prio_changed(cfqq);
2655
Jens Axboec1b707d2006-10-30 19:54:23 +01002656 spin_unlock_irqrestore(cfqd->queue->queue_lock, flags);
Jens Axboe22e2c502005-06-27 10:55:12 +02002657}
2658
Jens Axboefc463792006-08-29 09:05:44 +02002659static void cfq_ioc_set_ioprio(struct io_context *ioc)
Linus Torvalds1da177e2005-04-16 15:20:36 -07002660{
Jens Axboe4ac845a2008-01-24 08:44:49 +01002661 call_for_each_cic(ioc, changed_ioprio);
Jens Axboefc463792006-08-29 09:05:44 +02002662 ioc->ioprio_changed = 0;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002663}
2664
Jens Axboed5036d72009-06-26 10:44:34 +02002665static void cfq_init_cfqq(struct cfq_data *cfqd, struct cfq_queue *cfqq,
Jens Axboea6151c32009-10-07 20:02:57 +02002666 pid_t pid, bool is_sync)
Jens Axboed5036d72009-06-26 10:44:34 +02002667{
2668 RB_CLEAR_NODE(&cfqq->rb_node);
2669 RB_CLEAR_NODE(&cfqq->p_node);
2670 INIT_LIST_HEAD(&cfqq->fifo);
2671
2672 atomic_set(&cfqq->ref, 0);
2673 cfqq->cfqd = cfqd;
2674
2675 cfq_mark_cfqq_prio_changed(cfqq);
2676
2677 if (is_sync) {
2678 if (!cfq_class_idle(cfqq))
2679 cfq_mark_cfqq_idle_window(cfqq);
2680 cfq_mark_cfqq_sync(cfqq);
2681 }
2682 cfqq->pid = pid;
2683}
2684
Vivek Goyal246103332009-12-03 12:59:51 -05002685#ifdef CONFIG_CFQ_GROUP_IOSCHED
2686static void changed_cgroup(struct io_context *ioc, struct cfq_io_context *cic)
2687{
2688 struct cfq_queue *sync_cfqq = cic_to_cfqq(cic, 1);
2689 struct cfq_data *cfqd = cic->key;
2690 unsigned long flags;
2691 struct request_queue *q;
2692
2693 if (unlikely(!cfqd))
2694 return;
2695
2696 q = cfqd->queue;
2697
2698 spin_lock_irqsave(q->queue_lock, flags);
2699
2700 if (sync_cfqq) {
2701 /*
2702 * Drop reference to sync queue. A new sync queue will be
2703 * assigned in new group upon arrival of a fresh request.
2704 */
2705 cfq_log_cfqq(cfqd, sync_cfqq, "changed cgroup");
2706 cic_set_cfqq(cic, NULL, 1);
2707 cfq_put_queue(sync_cfqq);
2708 }
2709
2710 spin_unlock_irqrestore(q->queue_lock, flags);
2711}
2712
2713static void cfq_ioc_set_cgroup(struct io_context *ioc)
2714{
2715 call_for_each_cic(ioc, changed_cgroup);
2716 ioc->cgroup_changed = 0;
2717}
2718#endif /* CONFIG_CFQ_GROUP_IOSCHED */
2719
Linus Torvalds1da177e2005-04-16 15:20:36 -07002720static struct cfq_queue *
Jens Axboea6151c32009-10-07 20:02:57 +02002721cfq_find_alloc_queue(struct cfq_data *cfqd, bool is_sync,
Jens Axboefd0928d2008-01-24 08:52:45 +01002722 struct io_context *ioc, gfp_t gfp_mask)
Linus Torvalds1da177e2005-04-16 15:20:36 -07002723{
Linus Torvalds1da177e2005-04-16 15:20:36 -07002724 struct cfq_queue *cfqq, *new_cfqq = NULL;
Vasily Tarasov91fac312007-04-25 12:29:51 +02002725 struct cfq_io_context *cic;
Vivek Goyalcdb16e82009-12-03 12:59:38 -05002726 struct cfq_group *cfqg;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002727
2728retry:
Vivek Goyalcdb16e82009-12-03 12:59:38 -05002729 cfqg = cfq_get_cfqg(cfqd, 1);
Jens Axboe4ac845a2008-01-24 08:44:49 +01002730 cic = cfq_cic_lookup(cfqd, ioc);
Vasily Tarasov91fac312007-04-25 12:29:51 +02002731 /* cic always exists here */
2732 cfqq = cic_to_cfqq(cic, is_sync);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002733
Jens Axboe6118b702009-06-30 09:34:12 +02002734 /*
2735 * Always try a new alloc if we fell back to the OOM cfqq
2736 * originally, since it should just be a temporary situation.
2737 */
2738 if (!cfqq || cfqq == &cfqd->oom_cfqq) {
2739 cfqq = NULL;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002740 if (new_cfqq) {
2741 cfqq = new_cfqq;
2742 new_cfqq = NULL;
Jens Axboe22e2c502005-06-27 10:55:12 +02002743 } else if (gfp_mask & __GFP_WAIT) {
Linus Torvalds1da177e2005-04-16 15:20:36 -07002744 spin_unlock_irq(cfqd->queue->queue_lock);
Christoph Lameter94f60302007-07-17 04:03:29 -07002745 new_cfqq = kmem_cache_alloc_node(cfq_pool,
Jens Axboe6118b702009-06-30 09:34:12 +02002746 gfp_mask | __GFP_ZERO,
Christoph Lameter94f60302007-07-17 04:03:29 -07002747 cfqd->queue->node);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002748 spin_lock_irq(cfqd->queue->queue_lock);
Jens Axboe6118b702009-06-30 09:34:12 +02002749 if (new_cfqq)
2750 goto retry;
Jens Axboe22e2c502005-06-27 10:55:12 +02002751 } else {
Christoph Lameter94f60302007-07-17 04:03:29 -07002752 cfqq = kmem_cache_alloc_node(cfq_pool,
2753 gfp_mask | __GFP_ZERO,
2754 cfqd->queue->node);
Kiyoshi Ueda db3b5842005-06-17 16:15:10 +02002755 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07002756
Jens Axboe6118b702009-06-30 09:34:12 +02002757 if (cfqq) {
2758 cfq_init_cfqq(cfqd, cfqq, current->pid, is_sync);
2759 cfq_init_prio_data(cfqq, ioc);
Vivek Goyalcdb16e82009-12-03 12:59:38 -05002760 cfq_link_cfqq_cfqg(cfqq, cfqg);
Jens Axboe6118b702009-06-30 09:34:12 +02002761 cfq_log_cfqq(cfqd, cfqq, "alloced");
2762 } else
2763 cfqq = &cfqd->oom_cfqq;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002764 }
2765
2766 if (new_cfqq)
2767 kmem_cache_free(cfq_pool, new_cfqq);
2768
Linus Torvalds1da177e2005-04-16 15:20:36 -07002769 return cfqq;
2770}
2771
Vasily Tarasovc2dea2d2007-07-20 10:06:38 +02002772static struct cfq_queue **
2773cfq_async_queue_prio(struct cfq_data *cfqd, int ioprio_class, int ioprio)
2774{
Jens Axboefe094d92008-01-31 13:08:54 +01002775 switch (ioprio_class) {
Vasily Tarasovc2dea2d2007-07-20 10:06:38 +02002776 case IOPRIO_CLASS_RT:
2777 return &cfqd->async_cfqq[0][ioprio];
2778 case IOPRIO_CLASS_BE:
2779 return &cfqd->async_cfqq[1][ioprio];
2780 case IOPRIO_CLASS_IDLE:
2781 return &cfqd->async_idle_cfqq;
2782 default:
2783 BUG();
2784 }
2785}
2786
Jens Axboe15c31be2007-07-10 13:43:25 +02002787static struct cfq_queue *
Jens Axboea6151c32009-10-07 20:02:57 +02002788cfq_get_queue(struct cfq_data *cfqd, bool is_sync, struct io_context *ioc,
Jens Axboe15c31be2007-07-10 13:43:25 +02002789 gfp_t gfp_mask)
2790{
Jens Axboefd0928d2008-01-24 08:52:45 +01002791 const int ioprio = task_ioprio(ioc);
2792 const int ioprio_class = task_ioprio_class(ioc);
Vasily Tarasovc2dea2d2007-07-20 10:06:38 +02002793 struct cfq_queue **async_cfqq = NULL;
Jens Axboe15c31be2007-07-10 13:43:25 +02002794 struct cfq_queue *cfqq = NULL;
2795
Vasily Tarasovc2dea2d2007-07-20 10:06:38 +02002796 if (!is_sync) {
2797 async_cfqq = cfq_async_queue_prio(cfqd, ioprio_class, ioprio);
2798 cfqq = *async_cfqq;
2799 }
2800
Jens Axboe6118b702009-06-30 09:34:12 +02002801 if (!cfqq)
Jens Axboefd0928d2008-01-24 08:52:45 +01002802 cfqq = cfq_find_alloc_queue(cfqd, is_sync, ioc, gfp_mask);
Jens Axboe15c31be2007-07-10 13:43:25 +02002803
2804 /*
2805 * pin the queue now that it's allocated, scheduler exit will prune it
2806 */
Vasily Tarasovc2dea2d2007-07-20 10:06:38 +02002807 if (!is_sync && !(*async_cfqq)) {
Jens Axboe15c31be2007-07-10 13:43:25 +02002808 atomic_inc(&cfqq->ref);
Vasily Tarasovc2dea2d2007-07-20 10:06:38 +02002809 *async_cfqq = cfqq;
Jens Axboe15c31be2007-07-10 13:43:25 +02002810 }
2811
2812 atomic_inc(&cfqq->ref);
2813 return cfqq;
2814}
2815
Jens Axboe498d3aa22007-04-26 12:54:48 +02002816/*
2817 * We drop cfq io contexts lazily, so we may find a dead one.
2818 */
OGAWA Hirofumidbecf3a2006-04-18 09:45:18 +02002819static void
Jens Axboe4ac845a2008-01-24 08:44:49 +01002820cfq_drop_dead_cic(struct cfq_data *cfqd, struct io_context *ioc,
2821 struct cfq_io_context *cic)
OGAWA Hirofumidbecf3a2006-04-18 09:45:18 +02002822{
Jens Axboe4ac845a2008-01-24 08:44:49 +01002823 unsigned long flags;
2824
Jens Axboefc463792006-08-29 09:05:44 +02002825 WARN_ON(!list_empty(&cic->queue_list));
Jens Axboe597bc482007-04-24 21:23:53 +02002826
Jens Axboe4ac845a2008-01-24 08:44:49 +01002827 spin_lock_irqsave(&ioc->lock, flags);
Jens Axboe597bc482007-04-24 21:23:53 +02002828
Fabio Checconi4faa3c82008-04-10 08:28:01 +02002829 BUG_ON(ioc->ioc_data == cic);
Jens Axboe4ac845a2008-01-24 08:44:49 +01002830
2831 radix_tree_delete(&ioc->radix_root, (unsigned long) cfqd);
Jens Axboeffc4e752008-02-19 10:02:29 +01002832 hlist_del_rcu(&cic->cic_list);
Jens Axboe4ac845a2008-01-24 08:44:49 +01002833 spin_unlock_irqrestore(&ioc->lock, flags);
2834
2835 cfq_cic_free(cic);
OGAWA Hirofumidbecf3a2006-04-18 09:45:18 +02002836}
2837
Jens Axboee2d74ac2006-03-28 08:59:01 +02002838static struct cfq_io_context *
Jens Axboe4ac845a2008-01-24 08:44:49 +01002839cfq_cic_lookup(struct cfq_data *cfqd, struct io_context *ioc)
Jens Axboee2d74ac2006-03-28 08:59:01 +02002840{
Jens Axboee2d74ac2006-03-28 08:59:01 +02002841 struct cfq_io_context *cic;
Jens Axboed6de8be2008-05-28 14:46:59 +02002842 unsigned long flags;
Jens Axboe4ac845a2008-01-24 08:44:49 +01002843 void *k;
Jens Axboee2d74ac2006-03-28 08:59:01 +02002844
Vasily Tarasov91fac312007-04-25 12:29:51 +02002845 if (unlikely(!ioc))
2846 return NULL;
2847
Jens Axboed6de8be2008-05-28 14:46:59 +02002848 rcu_read_lock();
2849
Jens Axboe597bc482007-04-24 21:23:53 +02002850 /*
2851 * we maintain a last-hit cache, to avoid browsing over the tree
2852 */
Jens Axboe4ac845a2008-01-24 08:44:49 +01002853 cic = rcu_dereference(ioc->ioc_data);
Jens Axboed6de8be2008-05-28 14:46:59 +02002854 if (cic && cic->key == cfqd) {
2855 rcu_read_unlock();
Jens Axboe597bc482007-04-24 21:23:53 +02002856 return cic;
Jens Axboed6de8be2008-05-28 14:46:59 +02002857 }
Jens Axboe597bc482007-04-24 21:23:53 +02002858
Jens Axboe4ac845a2008-01-24 08:44:49 +01002859 do {
Jens Axboe4ac845a2008-01-24 08:44:49 +01002860 cic = radix_tree_lookup(&ioc->radix_root, (unsigned long) cfqd);
2861 rcu_read_unlock();
2862 if (!cic)
2863 break;
OGAWA Hirofumibe3b0752006-04-18 19:18:31 +02002864 /* ->key must be copied to avoid race with cfq_exit_queue() */
2865 k = cic->key;
2866 if (unlikely(!k)) {
Jens Axboe4ac845a2008-01-24 08:44:49 +01002867 cfq_drop_dead_cic(cfqd, ioc, cic);
Jens Axboed6de8be2008-05-28 14:46:59 +02002868 rcu_read_lock();
Jens Axboe4ac845a2008-01-24 08:44:49 +01002869 continue;
OGAWA Hirofumidbecf3a2006-04-18 09:45:18 +02002870 }
Jens Axboee2d74ac2006-03-28 08:59:01 +02002871
Jens Axboed6de8be2008-05-28 14:46:59 +02002872 spin_lock_irqsave(&ioc->lock, flags);
Jens Axboe4ac845a2008-01-24 08:44:49 +01002873 rcu_assign_pointer(ioc->ioc_data, cic);
Jens Axboed6de8be2008-05-28 14:46:59 +02002874 spin_unlock_irqrestore(&ioc->lock, flags);
Jens Axboe4ac845a2008-01-24 08:44:49 +01002875 break;
2876 } while (1);
Jens Axboee2d74ac2006-03-28 08:59:01 +02002877
Jens Axboe4ac845a2008-01-24 08:44:49 +01002878 return cic;
Jens Axboee2d74ac2006-03-28 08:59:01 +02002879}
2880
Jens Axboe4ac845a2008-01-24 08:44:49 +01002881/*
2882 * Add cic into ioc, using cfqd as the search key. This enables us to lookup
2883 * the process specific cfq io context when entered from the block layer.
2884 * Also adds the cic to a per-cfqd list, used when this queue is removed.
2885 */
Jens Axboefebffd62008-01-28 13:19:43 +01002886static int cfq_cic_link(struct cfq_data *cfqd, struct io_context *ioc,
2887 struct cfq_io_context *cic, gfp_t gfp_mask)
Jens Axboee2d74ac2006-03-28 08:59:01 +02002888{
Jens Axboe0261d682006-10-30 19:07:48 +01002889 unsigned long flags;
Jens Axboe4ac845a2008-01-24 08:44:49 +01002890 int ret;
Jens Axboee2d74ac2006-03-28 08:59:01 +02002891
Jens Axboe4ac845a2008-01-24 08:44:49 +01002892 ret = radix_tree_preload(gfp_mask);
2893 if (!ret) {
2894 cic->ioc = ioc;
2895 cic->key = cfqd;
Jens Axboee2d74ac2006-03-28 08:59:01 +02002896
Jens Axboe4ac845a2008-01-24 08:44:49 +01002897 spin_lock_irqsave(&ioc->lock, flags);
2898 ret = radix_tree_insert(&ioc->radix_root,
2899 (unsigned long) cfqd, cic);
Jens Axboeffc4e752008-02-19 10:02:29 +01002900 if (!ret)
2901 hlist_add_head_rcu(&cic->cic_list, &ioc->cic_list);
Jens Axboe4ac845a2008-01-24 08:44:49 +01002902 spin_unlock_irqrestore(&ioc->lock, flags);
2903
2904 radix_tree_preload_end();
2905
2906 if (!ret) {
2907 spin_lock_irqsave(cfqd->queue->queue_lock, flags);
2908 list_add(&cic->queue_list, &cfqd->cic_list);
2909 spin_unlock_irqrestore(cfqd->queue->queue_lock, flags);
OGAWA Hirofumidbecf3a2006-04-18 09:45:18 +02002910 }
Jens Axboee2d74ac2006-03-28 08:59:01 +02002911 }
2912
Jens Axboe4ac845a2008-01-24 08:44:49 +01002913 if (ret)
2914 printk(KERN_ERR "cfq: cic link failed!\n");
Jens Axboefc463792006-08-29 09:05:44 +02002915
Jens Axboe4ac845a2008-01-24 08:44:49 +01002916 return ret;
Jens Axboee2d74ac2006-03-28 08:59:01 +02002917}
2918
Jens Axboe22e2c502005-06-27 10:55:12 +02002919/*
2920 * Setup general io context and cfq io context. There can be several cfq
2921 * io contexts per general io context, if this process is doing io to more
Jens Axboee2d74ac2006-03-28 08:59:01 +02002922 * than one device managed by cfq.
Jens Axboe22e2c502005-06-27 10:55:12 +02002923 */
2924static struct cfq_io_context *
Jens Axboee2d74ac2006-03-28 08:59:01 +02002925cfq_get_io_context(struct cfq_data *cfqd, gfp_t gfp_mask)
Linus Torvalds1da177e2005-04-16 15:20:36 -07002926{
Jens Axboe22e2c502005-06-27 10:55:12 +02002927 struct io_context *ioc = NULL;
2928 struct cfq_io_context *cic;
2929
2930 might_sleep_if(gfp_mask & __GFP_WAIT);
2931
Jens Axboeb5deef92006-07-19 23:39:40 +02002932 ioc = get_io_context(gfp_mask, cfqd->queue->node);
Jens Axboe22e2c502005-06-27 10:55:12 +02002933 if (!ioc)
2934 return NULL;
2935
Jens Axboe4ac845a2008-01-24 08:44:49 +01002936 cic = cfq_cic_lookup(cfqd, ioc);
Jens Axboee2d74ac2006-03-28 08:59:01 +02002937 if (cic)
2938 goto out;
Jens Axboe22e2c502005-06-27 10:55:12 +02002939
Jens Axboee2d74ac2006-03-28 08:59:01 +02002940 cic = cfq_alloc_io_context(cfqd, gfp_mask);
2941 if (cic == NULL)
2942 goto err;
Jens Axboe22e2c502005-06-27 10:55:12 +02002943
Jens Axboe4ac845a2008-01-24 08:44:49 +01002944 if (cfq_cic_link(cfqd, ioc, cic, gfp_mask))
2945 goto err_free;
2946
Jens Axboe22e2c502005-06-27 10:55:12 +02002947out:
Jens Axboefc463792006-08-29 09:05:44 +02002948 smp_read_barrier_depends();
2949 if (unlikely(ioc->ioprio_changed))
2950 cfq_ioc_set_ioprio(ioc);
2951
Vivek Goyal246103332009-12-03 12:59:51 -05002952#ifdef CONFIG_CFQ_GROUP_IOSCHED
2953 if (unlikely(ioc->cgroup_changed))
2954 cfq_ioc_set_cgroup(ioc);
2955#endif
Jens Axboe22e2c502005-06-27 10:55:12 +02002956 return cic;
Jens Axboe4ac845a2008-01-24 08:44:49 +01002957err_free:
2958 cfq_cic_free(cic);
Jens Axboe22e2c502005-06-27 10:55:12 +02002959err:
2960 put_io_context(ioc);
2961 return NULL;
2962}
2963
2964static void
2965cfq_update_io_thinktime(struct cfq_data *cfqd, struct cfq_io_context *cic)
2966{
Jens Axboeaaf12282007-01-19 11:30:16 +11002967 unsigned long elapsed = jiffies - cic->last_end_request;
2968 unsigned long ttime = min(elapsed, 2UL * cfqd->cfq_slice_idle);
Jens Axboe22e2c502005-06-27 10:55:12 +02002969
2970 cic->ttime_samples = (7*cic->ttime_samples + 256) / 8;
2971 cic->ttime_total = (7*cic->ttime_total + 256*ttime) / 8;
2972 cic->ttime_mean = (cic->ttime_total + 128) / cic->ttime_samples;
2973}
2974
Jens Axboe206dc692006-03-28 13:03:44 +02002975static void
Jeff Moyerb2c18e12009-10-23 17:14:49 -04002976cfq_update_io_seektime(struct cfq_data *cfqd, struct cfq_queue *cfqq,
Jens Axboe6d048f52007-04-25 12:44:27 +02002977 struct request *rq)
Jens Axboe206dc692006-03-28 13:03:44 +02002978{
2979 sector_t sdist;
2980 u64 total;
2981
Jeff Moyerb2c18e12009-10-23 17:14:49 -04002982 if (!cfqq->last_request_pos)
Jeff Moyer4d00aa42009-04-21 07:25:04 +02002983 sdist = 0;
Jeff Moyerb2c18e12009-10-23 17:14:49 -04002984 else if (cfqq->last_request_pos < blk_rq_pos(rq))
2985 sdist = blk_rq_pos(rq) - cfqq->last_request_pos;
Jens Axboe206dc692006-03-28 13:03:44 +02002986 else
Jeff Moyerb2c18e12009-10-23 17:14:49 -04002987 sdist = cfqq->last_request_pos - blk_rq_pos(rq);
Jens Axboe206dc692006-03-28 13:03:44 +02002988
2989 /*
2990 * Don't allow the seek distance to get too large from the
2991 * odd fragment, pagein, etc
2992 */
Jeff Moyerb2c18e12009-10-23 17:14:49 -04002993 if (cfqq->seek_samples <= 60) /* second&third seek */
2994 sdist = min(sdist, (cfqq->seek_mean * 4) + 2*1024*1024);
Jens Axboe206dc692006-03-28 13:03:44 +02002995 else
Jeff Moyerb2c18e12009-10-23 17:14:49 -04002996 sdist = min(sdist, (cfqq->seek_mean * 4) + 2*1024*64);
Jens Axboe206dc692006-03-28 13:03:44 +02002997
Jeff Moyerb2c18e12009-10-23 17:14:49 -04002998 cfqq->seek_samples = (7*cfqq->seek_samples + 256) / 8;
2999 cfqq->seek_total = (7*cfqq->seek_total + (u64)256*sdist) / 8;
3000 total = cfqq->seek_total + (cfqq->seek_samples/2);
3001 do_div(total, cfqq->seek_samples);
3002 cfqq->seek_mean = (sector_t)total;
Jeff Moyere6c5bc72009-10-23 17:14:52 -04003003
3004 /*
3005 * If this cfqq is shared between multiple processes, check to
3006 * make sure that those processes are still issuing I/Os within
3007 * the mean seek distance. If not, it may be time to break the
3008 * queues apart again.
3009 */
3010 if (cfq_cfqq_coop(cfqq)) {
3011 if (CFQQ_SEEKY(cfqq) && !cfqq->seeky_start)
3012 cfqq->seeky_start = jiffies;
3013 else if (!CFQQ_SEEKY(cfqq))
3014 cfqq->seeky_start = 0;
3015 }
Jens Axboe206dc692006-03-28 13:03:44 +02003016}
Jens Axboe22e2c502005-06-27 10:55:12 +02003017
3018/*
3019 * Disable idle window if the process thinks too long or seeks so much that
3020 * it doesn't matter
3021 */
3022static void
3023cfq_update_idle_window(struct cfq_data *cfqd, struct cfq_queue *cfqq,
3024 struct cfq_io_context *cic)
3025{
Jens Axboe7b679132008-05-30 12:23:07 +02003026 int old_idle, enable_idle;
Jens Axboe1be92f22007-04-19 14:32:26 +02003027
Jens Axboe08717142008-01-28 11:38:15 +01003028 /*
3029 * Don't idle for async or idle io prio class
3030 */
3031 if (!cfq_cfqq_sync(cfqq) || cfq_class_idle(cfqq))
Jens Axboe1be92f22007-04-19 14:32:26 +02003032 return;
3033
Jens Axboec265a7f2008-06-26 13:49:33 +02003034 enable_idle = old_idle = cfq_cfqq_idle_window(cfqq);
Jens Axboe22e2c502005-06-27 10:55:12 +02003035
Corrado Zoccolo76280af2009-11-26 10:02:58 +01003036 if (cfqq->queued[0] + cfqq->queued[1] >= 4)
3037 cfq_mark_cfqq_deep(cfqq);
3038
Nikanth Karthikesan66dac982007-11-27 12:47:04 +01003039 if (!atomic_read(&cic->ioc->nr_tasks) || !cfqd->cfq_slice_idle ||
Corrado Zoccolo76280af2009-11-26 10:02:58 +01003040 (!cfq_cfqq_deep(cfqq) && sample_valid(cfqq->seek_samples)
3041 && CFQQ_SEEKY(cfqq)))
Jens Axboe22e2c502005-06-27 10:55:12 +02003042 enable_idle = 0;
3043 else if (sample_valid(cic->ttime_samples)) {
Corrado Zoccolo718eee02009-10-26 22:45:29 +01003044 if (cic->ttime_mean > cfqd->cfq_slice_idle)
Jens Axboe22e2c502005-06-27 10:55:12 +02003045 enable_idle = 0;
3046 else
3047 enable_idle = 1;
3048 }
3049
Jens Axboe7b679132008-05-30 12:23:07 +02003050 if (old_idle != enable_idle) {
3051 cfq_log_cfqq(cfqd, cfqq, "idle=%d", enable_idle);
3052 if (enable_idle)
3053 cfq_mark_cfqq_idle_window(cfqq);
3054 else
3055 cfq_clear_cfqq_idle_window(cfqq);
3056 }
Jens Axboe22e2c502005-06-27 10:55:12 +02003057}
3058
Jens Axboe22e2c502005-06-27 10:55:12 +02003059/*
3060 * Check if new_cfqq should preempt the currently active queue. Return 0 for
3061 * no or if we aren't sure, a 1 will cause a preempt.
3062 */
Jens Axboea6151c32009-10-07 20:02:57 +02003063static bool
Jens Axboe22e2c502005-06-27 10:55:12 +02003064cfq_should_preempt(struct cfq_data *cfqd, struct cfq_queue *new_cfqq,
Jens Axboe5e705372006-07-13 12:39:25 +02003065 struct request *rq)
Jens Axboe22e2c502005-06-27 10:55:12 +02003066{
Jens Axboe6d048f52007-04-25 12:44:27 +02003067 struct cfq_queue *cfqq;
Jens Axboe22e2c502005-06-27 10:55:12 +02003068
Jens Axboe6d048f52007-04-25 12:44:27 +02003069 cfqq = cfqd->active_queue;
3070 if (!cfqq)
Jens Axboea6151c32009-10-07 20:02:57 +02003071 return false;
Jens Axboe22e2c502005-06-27 10:55:12 +02003072
Jens Axboe6d048f52007-04-25 12:44:27 +02003073 if (cfq_class_idle(new_cfqq))
Jens Axboea6151c32009-10-07 20:02:57 +02003074 return false;
Jens Axboe22e2c502005-06-27 10:55:12 +02003075
3076 if (cfq_class_idle(cfqq))
Jens Axboea6151c32009-10-07 20:02:57 +02003077 return true;
Jens Axboe1e3335d2007-02-14 19:59:49 +01003078
Jens Axboe22e2c502005-06-27 10:55:12 +02003079 /*
Divyesh Shah875feb62010-01-06 18:58:20 -08003080 * Don't allow a non-RT request to preempt an ongoing RT cfqq timeslice.
3081 */
3082 if (cfq_class_rt(cfqq) && !cfq_class_rt(new_cfqq))
3083 return false;
3084
3085 /*
Jens Axboe374f84a2006-07-23 01:42:19 +02003086 * if the new request is sync, but the currently running queue is
3087 * not, let the sync request have priority.
3088 */
Jens Axboe5e705372006-07-13 12:39:25 +02003089 if (rq_is_sync(rq) && !cfq_cfqq_sync(cfqq))
Jens Axboea6151c32009-10-07 20:02:57 +02003090 return true;
Jens Axboe1e3335d2007-02-14 19:59:49 +01003091
Vivek Goyal8682e1f2009-12-03 12:59:50 -05003092 if (new_cfqq->cfqg != cfqq->cfqg)
3093 return false;
3094
3095 if (cfq_slice_used(cfqq))
3096 return true;
3097
3098 /* Allow preemption only if we are idling on sync-noidle tree */
3099 if (cfqd->serving_type == SYNC_NOIDLE_WORKLOAD &&
3100 cfqq_type(new_cfqq) == SYNC_NOIDLE_WORKLOAD &&
3101 new_cfqq->service_tree->count == 2 &&
3102 RB_EMPTY_ROOT(&cfqq->sort_list))
3103 return true;
3104
Jens Axboe374f84a2006-07-23 01:42:19 +02003105 /*
3106 * So both queues are sync. Let the new request get disk time if
3107 * it's a metadata request and the current queue is doing regular IO.
3108 */
3109 if (rq_is_meta(rq) && !cfqq->meta_pending)
Jens Axboee6ec4fe2009-11-03 20:21:35 +01003110 return true;
Jens Axboe22e2c502005-06-27 10:55:12 +02003111
Divyesh Shah3a9a3f62009-01-30 12:46:41 +01003112 /*
3113 * Allow an RT request to pre-empt an ongoing non-RT cfqq timeslice.
3114 */
3115 if (cfq_class_rt(new_cfqq) && !cfq_class_rt(cfqq))
Jens Axboea6151c32009-10-07 20:02:57 +02003116 return true;
Divyesh Shah3a9a3f62009-01-30 12:46:41 +01003117
Jens Axboe1e3335d2007-02-14 19:59:49 +01003118 if (!cfqd->active_cic || !cfq_cfqq_wait_request(cfqq))
Jens Axboea6151c32009-10-07 20:02:57 +02003119 return false;
Jens Axboe1e3335d2007-02-14 19:59:49 +01003120
3121 /*
3122 * if this request is as-good as one we would expect from the
3123 * current cfqq, let it preempt
3124 */
Shaohua Li2f7a2d82009-12-28 13:18:44 +01003125 if (cfq_rq_close(cfqd, cfqq, rq, true))
Jens Axboea6151c32009-10-07 20:02:57 +02003126 return true;
Jens Axboe1e3335d2007-02-14 19:59:49 +01003127
Jens Axboea6151c32009-10-07 20:02:57 +02003128 return false;
Jens Axboe22e2c502005-06-27 10:55:12 +02003129}
3130
3131/*
3132 * cfqq preempts the active queue. if we allowed preempt with no slice left,
3133 * let it have half of its nominal slice.
3134 */
3135static void cfq_preempt_queue(struct cfq_data *cfqd, struct cfq_queue *cfqq)
3136{
Jens Axboe7b679132008-05-30 12:23:07 +02003137 cfq_log_cfqq(cfqd, cfqq, "preempt");
Jens Axboe6084cdd2007-04-23 08:25:00 +02003138 cfq_slice_expired(cfqd, 1);
Jens Axboe22e2c502005-06-27 10:55:12 +02003139
Jens Axboebf572252006-07-19 20:29:12 +02003140 /*
3141 * Put the new queue at the front of the of the current list,
3142 * so we know that it will be selected next.
3143 */
3144 BUG_ON(!cfq_cfqq_on_rr(cfqq));
Jens Axboeedd75ff2007-04-19 12:03:34 +02003145
3146 cfq_service_tree_add(cfqd, cfqq, 1);
Jens Axboebf572252006-07-19 20:29:12 +02003147
Jens Axboe44f7c162007-01-19 11:51:58 +11003148 cfqq->slice_end = 0;
3149 cfq_mark_cfqq_slice_new(cfqq);
Jens Axboe22e2c502005-06-27 10:55:12 +02003150}
3151
3152/*
Jens Axboe5e705372006-07-13 12:39:25 +02003153 * Called when a new fs request (rq) is added (to cfqq). Check if there's
Jens Axboe22e2c502005-06-27 10:55:12 +02003154 * something we should do about it
3155 */
3156static void
Jens Axboe5e705372006-07-13 12:39:25 +02003157cfq_rq_enqueued(struct cfq_data *cfqd, struct cfq_queue *cfqq,
3158 struct request *rq)
Jens Axboe22e2c502005-06-27 10:55:12 +02003159{
Jens Axboe5e705372006-07-13 12:39:25 +02003160 struct cfq_io_context *cic = RQ_CIC(rq);
Jens Axboe12e9fdd2006-06-01 10:09:56 +02003161
Aaron Carroll45333d52008-08-26 15:52:36 +02003162 cfqd->rq_queued++;
Jens Axboe374f84a2006-07-23 01:42:19 +02003163 if (rq_is_meta(rq))
3164 cfqq->meta_pending++;
3165
Jens Axboe9c2c38a2005-08-24 14:57:54 +02003166 cfq_update_io_thinktime(cfqd, cic);
Jeff Moyerb2c18e12009-10-23 17:14:49 -04003167 cfq_update_io_seektime(cfqd, cfqq, rq);
Jens Axboe9c2c38a2005-08-24 14:57:54 +02003168 cfq_update_idle_window(cfqd, cfqq, cic);
3169
Jeff Moyerb2c18e12009-10-23 17:14:49 -04003170 cfqq->last_request_pos = blk_rq_pos(rq) + blk_rq_sectors(rq);
Jens Axboe22e2c502005-06-27 10:55:12 +02003171
3172 if (cfqq == cfqd->active_queue) {
3173 /*
Jens Axboeb0291952009-04-07 11:38:31 +02003174 * Remember that we saw a request from this process, but
3175 * don't start queuing just yet. Otherwise we risk seeing lots
3176 * of tiny requests, because we disrupt the normal plugging
Jens Axboed6ceb252009-04-14 14:18:16 +02003177 * and merging. If the request is already larger than a single
3178 * page, let it rip immediately. For that case we assume that
Jens Axboe2d870722009-04-15 12:12:46 +02003179 * merging is already done. Ditto for a busy system that
3180 * has other work pending, don't risk delaying until the
3181 * idle timer unplug to continue working.
Jens Axboe22e2c502005-06-27 10:55:12 +02003182 */
Jens Axboed6ceb252009-04-14 14:18:16 +02003183 if (cfq_cfqq_wait_request(cfqq)) {
Jens Axboe2d870722009-04-15 12:12:46 +02003184 if (blk_rq_bytes(rq) > PAGE_CACHE_SIZE ||
3185 cfqd->busy_queues > 1) {
Jens Axboed6ceb252009-04-14 14:18:16 +02003186 del_timer(&cfqd->idle_slice_timer);
Gui Jianfeng554554f2009-12-10 09:38:39 +01003187 cfq_clear_cfqq_wait_request(cfqq);
Vivek Goyalbf7919372009-12-03 12:59:37 -05003188 __blk_run_queue(cfqd->queue);
3189 } else
3190 cfq_mark_cfqq_must_dispatch(cfqq);
Jens Axboed6ceb252009-04-14 14:18:16 +02003191 }
Jens Axboe5e705372006-07-13 12:39:25 +02003192 } else if (cfq_should_preempt(cfqd, cfqq, rq)) {
Jens Axboe22e2c502005-06-27 10:55:12 +02003193 /*
3194 * not the active queue - expire current slice if it is
3195 * idle and has expired it's mean thinktime or this new queue
Divyesh Shah3a9a3f62009-01-30 12:46:41 +01003196 * has some old slice time left and is of higher priority or
3197 * this new queue is RT and the current one is BE
Jens Axboe22e2c502005-06-27 10:55:12 +02003198 */
3199 cfq_preempt_queue(cfqd, cfqq);
Tejun Heoa7f55792009-04-23 11:05:17 +09003200 __blk_run_queue(cfqd->queue);
Jens Axboe22e2c502005-06-27 10:55:12 +02003201 }
3202}
3203
Jens Axboe165125e2007-07-24 09:28:11 +02003204static void cfq_insert_request(struct request_queue *q, struct request *rq)
Jens Axboe22e2c502005-06-27 10:55:12 +02003205{
Jens Axboeb4878f22005-10-20 16:42:29 +02003206 struct cfq_data *cfqd = q->elevator->elevator_data;
Jens Axboe5e705372006-07-13 12:39:25 +02003207 struct cfq_queue *cfqq = RQ_CFQQ(rq);
Jens Axboe22e2c502005-06-27 10:55:12 +02003208
Jens Axboe7b679132008-05-30 12:23:07 +02003209 cfq_log_cfqq(cfqd, cfqq, "insert_request");
Jens Axboefd0928d2008-01-24 08:52:45 +01003210 cfq_init_prio_data(cfqq, RQ_CIC(rq)->ioc);
Linus Torvalds1da177e2005-04-16 15:20:36 -07003211
Jens Axboe30996f42009-10-05 11:03:39 +02003212 rq_set_fifo_time(rq, jiffies + cfqd->cfq_fifo_expire[rq_is_sync(rq)]);
Jens Axboe22e2c502005-06-27 10:55:12 +02003213 list_add_tail(&rq->queuelist, &cfqq->fifo);
Corrado Zoccoloaa6f6a32009-10-26 22:44:33 +01003214 cfq_add_rq_rb(rq);
Jens Axboe22e2c502005-06-27 10:55:12 +02003215
Jens Axboe5e705372006-07-13 12:39:25 +02003216 cfq_rq_enqueued(cfqd, cfqq, rq);
Linus Torvalds1da177e2005-04-16 15:20:36 -07003217}
3218
Aaron Carroll45333d52008-08-26 15:52:36 +02003219/*
3220 * Update hw_tag based on peak queue depth over 50 samples under
3221 * sufficient load.
3222 */
3223static void cfq_update_hw_tag(struct cfq_data *cfqd)
3224{
Shaohua Li1a1238a2009-10-27 08:46:23 +01003225 struct cfq_queue *cfqq = cfqd->active_queue;
3226
Corrado Zoccoloe459dd02009-11-26 10:02:57 +01003227 if (rq_in_driver(cfqd) > cfqd->hw_tag_est_depth)
3228 cfqd->hw_tag_est_depth = rq_in_driver(cfqd);
3229
3230 if (cfqd->hw_tag == 1)
3231 return;
Aaron Carroll45333d52008-08-26 15:52:36 +02003232
3233 if (cfqd->rq_queued <= CFQ_HW_QUEUE_MIN &&
Jens Axboe5ad531d2009-07-03 12:57:48 +02003234 rq_in_driver(cfqd) <= CFQ_HW_QUEUE_MIN)
Aaron Carroll45333d52008-08-26 15:52:36 +02003235 return;
3236
Shaohua Li1a1238a2009-10-27 08:46:23 +01003237 /*
3238 * If active queue hasn't enough requests and can idle, cfq might not
3239 * dispatch sufficient requests to hardware. Don't zero hw_tag in this
3240 * case
3241 */
3242 if (cfqq && cfq_cfqq_idle_window(cfqq) &&
3243 cfqq->dispatched + cfqq->queued[0] + cfqq->queued[1] <
3244 CFQ_HW_QUEUE_MIN && rq_in_driver(cfqd) < CFQ_HW_QUEUE_MIN)
3245 return;
3246
Aaron Carroll45333d52008-08-26 15:52:36 +02003247 if (cfqd->hw_tag_samples++ < 50)
3248 return;
3249
Corrado Zoccoloe459dd02009-11-26 10:02:57 +01003250 if (cfqd->hw_tag_est_depth >= CFQ_HW_QUEUE_MIN)
Aaron Carroll45333d52008-08-26 15:52:36 +02003251 cfqd->hw_tag = 1;
3252 else
3253 cfqd->hw_tag = 0;
Aaron Carroll45333d52008-08-26 15:52:36 +02003254}
3255
Vivek Goyal7667aa02009-12-08 17:52:58 -05003256static bool cfq_should_wait_busy(struct cfq_data *cfqd, struct cfq_queue *cfqq)
3257{
3258 struct cfq_io_context *cic = cfqd->active_cic;
3259
3260 /* If there are other queues in the group, don't wait */
3261 if (cfqq->cfqg->nr_cfqq > 1)
3262 return false;
3263
3264 if (cfq_slice_used(cfqq))
3265 return true;
3266
3267 /* if slice left is less than think time, wait busy */
3268 if (cic && sample_valid(cic->ttime_samples)
3269 && (cfqq->slice_end - jiffies < cic->ttime_mean))
3270 return true;
3271
3272 /*
3273 * If think times is less than a jiffy than ttime_mean=0 and above
3274 * will not be true. It might happen that slice has not expired yet
3275 * but will expire soon (4-5 ns) during select_queue(). To cover the
3276 * case where think time is less than a jiffy, mark the queue wait
3277 * busy if only 1 jiffy is left in the slice.
3278 */
3279 if (cfqq->slice_end - jiffies == 1)
3280 return true;
3281
3282 return false;
3283}
3284
Jens Axboe165125e2007-07-24 09:28:11 +02003285static void cfq_completed_request(struct request_queue *q, struct request *rq)
Linus Torvalds1da177e2005-04-16 15:20:36 -07003286{
Jens Axboe5e705372006-07-13 12:39:25 +02003287 struct cfq_queue *cfqq = RQ_CFQQ(rq);
Jens Axboeb4878f22005-10-20 16:42:29 +02003288 struct cfq_data *cfqd = cfqq->cfqd;
Jens Axboe5380a102006-07-13 12:37:56 +02003289 const int sync = rq_is_sync(rq);
Jens Axboeb4878f22005-10-20 16:42:29 +02003290 unsigned long now;
Linus Torvalds1da177e2005-04-16 15:20:36 -07003291
Jens Axboeb4878f22005-10-20 16:42:29 +02003292 now = jiffies;
Vivek Goyal2868ef72009-12-03 12:59:48 -05003293 cfq_log_cfqq(cfqd, cfqq, "complete rqnoidle %d", !!rq_noidle(rq));
Linus Torvalds1da177e2005-04-16 15:20:36 -07003294
Aaron Carroll45333d52008-08-26 15:52:36 +02003295 cfq_update_hw_tag(cfqd);
3296
Jens Axboe5ad531d2009-07-03 12:57:48 +02003297 WARN_ON(!cfqd->rq_in_driver[sync]);
Jens Axboe6d048f52007-04-25 12:44:27 +02003298 WARN_ON(!cfqq->dispatched);
Jens Axboe5ad531d2009-07-03 12:57:48 +02003299 cfqd->rq_in_driver[sync]--;
Jens Axboe6d048f52007-04-25 12:44:27 +02003300 cfqq->dispatched--;
Linus Torvalds1da177e2005-04-16 15:20:36 -07003301
Jens Axboe3ed9a292007-04-23 08:33:33 +02003302 if (cfq_cfqq_sync(cfqq))
3303 cfqd->sync_flight--;
3304
Vivek Goyal365722b2009-10-03 15:21:27 +02003305 if (sync) {
Jens Axboe5e705372006-07-13 12:39:25 +02003306 RQ_CIC(rq)->last_end_request = now;
Corrado Zoccolo573412b2009-12-06 11:48:52 +01003307 if (!time_after(rq->start_time + cfqd->cfq_fifo_expire[1], now))
3308 cfqd->last_delayed_sync = now;
Vivek Goyal365722b2009-10-03 15:21:27 +02003309 }
Jens Axboecaaa5f92006-06-16 11:23:00 +02003310
3311 /*
3312 * If this is the active queue, check if it needs to be expired,
3313 * or if we want to idle in case it has no pending requests.
3314 */
3315 if (cfqd->active_queue == cfqq) {
Jens Axboea36e71f2009-04-15 12:15:11 +02003316 const bool cfqq_empty = RB_EMPTY_ROOT(&cfqq->sort_list);
3317
Jens Axboe44f7c162007-01-19 11:51:58 +11003318 if (cfq_cfqq_slice_new(cfqq)) {
3319 cfq_set_prio_slice(cfqd, cfqq);
3320 cfq_clear_cfqq_slice_new(cfqq);
3321 }
Vivek Goyalf75edf22009-12-03 12:59:53 -05003322
3323 /*
Vivek Goyal7667aa02009-12-08 17:52:58 -05003324 * Should we wait for next request to come in before we expire
3325 * the queue.
Vivek Goyalf75edf22009-12-03 12:59:53 -05003326 */
Vivek Goyal7667aa02009-12-08 17:52:58 -05003327 if (cfq_should_wait_busy(cfqd, cfqq)) {
Vivek Goyalf75edf22009-12-03 12:59:53 -05003328 cfqq->slice_end = jiffies + cfqd->cfq_slice_idle;
3329 cfq_mark_cfqq_wait_busy(cfqq);
3330 }
3331
Jens Axboea36e71f2009-04-15 12:15:11 +02003332 /*
Corrado Zoccolo8e550632009-11-26 10:02:58 +01003333 * Idling is not enabled on:
3334 * - expired queues
3335 * - idle-priority queues
3336 * - async queues
3337 * - queues with still some requests queued
3338 * - when there is a close cooperator
Jens Axboea36e71f2009-04-15 12:15:11 +02003339 */
Jens Axboe08717142008-01-28 11:38:15 +01003340 if (cfq_slice_used(cfqq) || cfq_class_idle(cfqq))
Jens Axboe6084cdd2007-04-23 08:25:00 +02003341 cfq_slice_expired(cfqd, 1);
Corrado Zoccolo8e550632009-11-26 10:02:58 +01003342 else if (sync && cfqq_empty &&
3343 !cfq_close_cooperator(cfqd, cfqq)) {
3344 cfqd->noidle_tree_requires_idle |= !rq_noidle(rq);
3345 /*
3346 * Idling is enabled for SYNC_WORKLOAD.
3347 * SYNC_NOIDLE_WORKLOAD idles at the end of the tree
3348 * only if we processed at least one !rq_noidle request
3349 */
3350 if (cfqd->serving_type == SYNC_WORKLOAD
Vivek Goyalc04645e2009-12-03 12:59:56 -05003351 || cfqd->noidle_tree_requires_idle
3352 || cfqq->cfqg->nr_cfqq == 1)
Corrado Zoccolo8e550632009-11-26 10:02:58 +01003353 cfq_arm_slice_timer(cfqd);
3354 }
Jens Axboecaaa5f92006-06-16 11:23:00 +02003355 }
Jens Axboe6d048f52007-04-25 12:44:27 +02003356
Jens Axboe5ad531d2009-07-03 12:57:48 +02003357 if (!rq_in_driver(cfqd))
Jens Axboe23e018a2009-10-05 08:52:35 +02003358 cfq_schedule_dispatch(cfqd);
Linus Torvalds1da177e2005-04-16 15:20:36 -07003359}
3360
Jens Axboe22e2c502005-06-27 10:55:12 +02003361/*
3362 * we temporarily boost lower priority queues if they are holding fs exclusive
3363 * resources. they are boosted to normal prio (CLASS_BE/4)
3364 */
3365static void cfq_prio_boost(struct cfq_queue *cfqq)
Linus Torvalds1da177e2005-04-16 15:20:36 -07003366{
Jens Axboe22e2c502005-06-27 10:55:12 +02003367 if (has_fs_excl()) {
3368 /*
3369 * boost idle prio on transactions that would lock out other
3370 * users of the filesystem
3371 */
3372 if (cfq_class_idle(cfqq))
3373 cfqq->ioprio_class = IOPRIO_CLASS_BE;
3374 if (cfqq->ioprio > IOPRIO_NORM)
3375 cfqq->ioprio = IOPRIO_NORM;
3376 } else {
3377 /*
Corrado Zoccolodddb7452009-11-02 10:40:37 +01003378 * unboost the queue (if needed)
Jens Axboe22e2c502005-06-27 10:55:12 +02003379 */
Corrado Zoccolodddb7452009-11-02 10:40:37 +01003380 cfqq->ioprio_class = cfqq->org_ioprio_class;
3381 cfqq->ioprio = cfqq->org_ioprio;
Linus Torvalds1da177e2005-04-16 15:20:36 -07003382 }
Jens Axboe22e2c502005-06-27 10:55:12 +02003383}
3384
Jens Axboe89850f72006-07-22 16:48:31 +02003385static inline int __cfq_may_queue(struct cfq_queue *cfqq)
Jens Axboe22e2c502005-06-27 10:55:12 +02003386{
Jens Axboe1b379d82009-08-11 08:26:11 +02003387 if (cfq_cfqq_wait_request(cfqq) && !cfq_cfqq_must_alloc_slice(cfqq)) {
Jens Axboe3b181522005-06-27 10:56:24 +02003388 cfq_mark_cfqq_must_alloc_slice(cfqq);
Jens Axboe22e2c502005-06-27 10:55:12 +02003389 return ELV_MQUEUE_MUST;
Jens Axboe3b181522005-06-27 10:56:24 +02003390 }
Jens Axboe22e2c502005-06-27 10:55:12 +02003391
3392 return ELV_MQUEUE_MAY;
Jens Axboe22e2c502005-06-27 10:55:12 +02003393}
3394
Jens Axboe165125e2007-07-24 09:28:11 +02003395static int cfq_may_queue(struct request_queue *q, int rw)
Jens Axboe22e2c502005-06-27 10:55:12 +02003396{
3397 struct cfq_data *cfqd = q->elevator->elevator_data;
3398 struct task_struct *tsk = current;
Vasily Tarasov91fac312007-04-25 12:29:51 +02003399 struct cfq_io_context *cic;
Jens Axboe22e2c502005-06-27 10:55:12 +02003400 struct cfq_queue *cfqq;
3401
3402 /*
3403 * don't force setup of a queue from here, as a call to may_queue
3404 * does not necessarily imply that a request actually will be queued.
3405 * so just lookup a possibly existing queue, or return 'may queue'
3406 * if that fails
3407 */
Jens Axboe4ac845a2008-01-24 08:44:49 +01003408 cic = cfq_cic_lookup(cfqd, tsk->io_context);
Vasily Tarasov91fac312007-04-25 12:29:51 +02003409 if (!cic)
3410 return ELV_MQUEUE_MAY;
3411
Jens Axboeb0b78f82009-04-08 10:56:08 +02003412 cfqq = cic_to_cfqq(cic, rw_is_sync(rw));
Jens Axboe22e2c502005-06-27 10:55:12 +02003413 if (cfqq) {
Jens Axboefd0928d2008-01-24 08:52:45 +01003414 cfq_init_prio_data(cfqq, cic->ioc);
Jens Axboe22e2c502005-06-27 10:55:12 +02003415 cfq_prio_boost(cfqq);
3416
Jens Axboe89850f72006-07-22 16:48:31 +02003417 return __cfq_may_queue(cfqq);
Jens Axboe22e2c502005-06-27 10:55:12 +02003418 }
3419
3420 return ELV_MQUEUE_MAY;
Linus Torvalds1da177e2005-04-16 15:20:36 -07003421}
3422
Linus Torvalds1da177e2005-04-16 15:20:36 -07003423/*
3424 * queue lock held here
3425 */
Jens Axboebb37b942006-12-01 10:42:33 +01003426static void cfq_put_request(struct request *rq)
Linus Torvalds1da177e2005-04-16 15:20:36 -07003427{
Jens Axboe5e705372006-07-13 12:39:25 +02003428 struct cfq_queue *cfqq = RQ_CFQQ(rq);
Linus Torvalds1da177e2005-04-16 15:20:36 -07003429
Jens Axboe5e705372006-07-13 12:39:25 +02003430 if (cfqq) {
Jens Axboe22e2c502005-06-27 10:55:12 +02003431 const int rw = rq_data_dir(rq);
Linus Torvalds1da177e2005-04-16 15:20:36 -07003432
Jens Axboe22e2c502005-06-27 10:55:12 +02003433 BUG_ON(!cfqq->allocated[rw]);
3434 cfqq->allocated[rw]--;
Linus Torvalds1da177e2005-04-16 15:20:36 -07003435
Jens Axboe5e705372006-07-13 12:39:25 +02003436 put_io_context(RQ_CIC(rq)->ioc);
Linus Torvalds1da177e2005-04-16 15:20:36 -07003437
Linus Torvalds1da177e2005-04-16 15:20:36 -07003438 rq->elevator_private = NULL;
Jens Axboe5e705372006-07-13 12:39:25 +02003439 rq->elevator_private2 = NULL;
Linus Torvalds1da177e2005-04-16 15:20:36 -07003440
Linus Torvalds1da177e2005-04-16 15:20:36 -07003441 cfq_put_queue(cfqq);
3442 }
3443}
3444
Jeff Moyerdf5fe3e2009-10-23 17:14:50 -04003445static struct cfq_queue *
3446cfq_merge_cfqqs(struct cfq_data *cfqd, struct cfq_io_context *cic,
3447 struct cfq_queue *cfqq)
3448{
3449 cfq_log_cfqq(cfqd, cfqq, "merging with queue %p", cfqq->new_cfqq);
3450 cic_set_cfqq(cic, cfqq->new_cfqq, 1);
Jeff Moyerb3b6d042009-10-23 17:14:51 -04003451 cfq_mark_cfqq_coop(cfqq->new_cfqq);
Jeff Moyerdf5fe3e2009-10-23 17:14:50 -04003452 cfq_put_queue(cfqq);
3453 return cic_to_cfqq(cic, 1);
3454}
3455
Jeff Moyere6c5bc72009-10-23 17:14:52 -04003456static int should_split_cfqq(struct cfq_queue *cfqq)
3457{
3458 if (cfqq->seeky_start &&
3459 time_after(jiffies, cfqq->seeky_start + CFQQ_COOP_TOUT))
3460 return 1;
3461 return 0;
3462}
3463
3464/*
3465 * Returns NULL if a new cfqq should be allocated, or the old cfqq if this
3466 * was the last process referring to said cfqq.
3467 */
3468static struct cfq_queue *
3469split_cfqq(struct cfq_io_context *cic, struct cfq_queue *cfqq)
3470{
3471 if (cfqq_process_refs(cfqq) == 1) {
3472 cfqq->seeky_start = 0;
3473 cfqq->pid = current->pid;
3474 cfq_clear_cfqq_coop(cfqq);
3475 return cfqq;
3476 }
3477
3478 cic_set_cfqq(cic, NULL, 1);
3479 cfq_put_queue(cfqq);
3480 return NULL;
3481}
Linus Torvalds1da177e2005-04-16 15:20:36 -07003482/*
Jens Axboe22e2c502005-06-27 10:55:12 +02003483 * Allocate cfq data structures associated with this request.
Linus Torvalds1da177e2005-04-16 15:20:36 -07003484 */
Jens Axboe22e2c502005-06-27 10:55:12 +02003485static int
Jens Axboe165125e2007-07-24 09:28:11 +02003486cfq_set_request(struct request_queue *q, struct request *rq, gfp_t gfp_mask)
Linus Torvalds1da177e2005-04-16 15:20:36 -07003487{
3488 struct cfq_data *cfqd = q->elevator->elevator_data;
3489 struct cfq_io_context *cic;
3490 const int rw = rq_data_dir(rq);
Jens Axboea6151c32009-10-07 20:02:57 +02003491 const bool is_sync = rq_is_sync(rq);
Jens Axboe22e2c502005-06-27 10:55:12 +02003492 struct cfq_queue *cfqq;
Linus Torvalds1da177e2005-04-16 15:20:36 -07003493 unsigned long flags;
3494
3495 might_sleep_if(gfp_mask & __GFP_WAIT);
3496
Jens Axboee2d74ac2006-03-28 08:59:01 +02003497 cic = cfq_get_io_context(cfqd, gfp_mask);
Jens Axboe22e2c502005-06-27 10:55:12 +02003498
Linus Torvalds1da177e2005-04-16 15:20:36 -07003499 spin_lock_irqsave(q->queue_lock, flags);
3500
Jens Axboe22e2c502005-06-27 10:55:12 +02003501 if (!cic)
3502 goto queue_fail;
Linus Torvalds1da177e2005-04-16 15:20:36 -07003503
Jeff Moyere6c5bc72009-10-23 17:14:52 -04003504new_queue:
Vasily Tarasov91fac312007-04-25 12:29:51 +02003505 cfqq = cic_to_cfqq(cic, is_sync);
Vivek Goyal32f2e802009-07-09 22:13:16 +02003506 if (!cfqq || cfqq == &cfqd->oom_cfqq) {
Jens Axboefd0928d2008-01-24 08:52:45 +01003507 cfqq = cfq_get_queue(cfqd, is_sync, cic->ioc, gfp_mask);
Vasily Tarasov91fac312007-04-25 12:29:51 +02003508 cic_set_cfqq(cic, cfqq, is_sync);
Jeff Moyerdf5fe3e2009-10-23 17:14:50 -04003509 } else {
3510 /*
Jeff Moyere6c5bc72009-10-23 17:14:52 -04003511 * If the queue was seeky for too long, break it apart.
3512 */
3513 if (cfq_cfqq_coop(cfqq) && should_split_cfqq(cfqq)) {
3514 cfq_log_cfqq(cfqd, cfqq, "breaking apart cfqq");
3515 cfqq = split_cfqq(cic, cfqq);
3516 if (!cfqq)
3517 goto new_queue;
3518 }
3519
3520 /*
Jeff Moyerdf5fe3e2009-10-23 17:14:50 -04003521 * Check to see if this queue is scheduled to merge with
3522 * another, closely cooperating queue. The merging of
3523 * queues happens here as it must be done in process context.
3524 * The reference on new_cfqq was taken in merge_cfqqs.
3525 */
3526 if (cfqq->new_cfqq)
3527 cfqq = cfq_merge_cfqqs(cfqd, cic, cfqq);
Vasily Tarasov91fac312007-04-25 12:29:51 +02003528 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07003529
3530 cfqq->allocated[rw]++;
Jens Axboe22e2c502005-06-27 10:55:12 +02003531 atomic_inc(&cfqq->ref);
Jens Axboe5e705372006-07-13 12:39:25 +02003532
Linus Torvalds1da177e2005-04-16 15:20:36 -07003533 spin_unlock_irqrestore(q->queue_lock, flags);
3534
Jens Axboe5e705372006-07-13 12:39:25 +02003535 rq->elevator_private = cic;
3536 rq->elevator_private2 = cfqq;
3537 return 0;
Jens Axboe3b181522005-06-27 10:56:24 +02003538
Jens Axboe22e2c502005-06-27 10:55:12 +02003539queue_fail:
3540 if (cic)
3541 put_io_context(cic->ioc);
Jens Axboe89850f72006-07-22 16:48:31 +02003542
Jens Axboe23e018a2009-10-05 08:52:35 +02003543 cfq_schedule_dispatch(cfqd);
Linus Torvalds1da177e2005-04-16 15:20:36 -07003544 spin_unlock_irqrestore(q->queue_lock, flags);
Jens Axboe7b679132008-05-30 12:23:07 +02003545 cfq_log(cfqd, "set_request fail");
Linus Torvalds1da177e2005-04-16 15:20:36 -07003546 return 1;
3547}
3548
David Howells65f27f32006-11-22 14:55:48 +00003549static void cfq_kick_queue(struct work_struct *work)
Jens Axboe22e2c502005-06-27 10:55:12 +02003550{
David Howells65f27f32006-11-22 14:55:48 +00003551 struct cfq_data *cfqd =
Jens Axboe23e018a2009-10-05 08:52:35 +02003552 container_of(work, struct cfq_data, unplug_work);
Jens Axboe165125e2007-07-24 09:28:11 +02003553 struct request_queue *q = cfqd->queue;
Jens Axboe22e2c502005-06-27 10:55:12 +02003554
Jens Axboe40bb54d2009-04-15 12:11:10 +02003555 spin_lock_irq(q->queue_lock);
Tejun Heoa7f55792009-04-23 11:05:17 +09003556 __blk_run_queue(cfqd->queue);
Jens Axboe40bb54d2009-04-15 12:11:10 +02003557 spin_unlock_irq(q->queue_lock);
Jens Axboe22e2c502005-06-27 10:55:12 +02003558}
3559
3560/*
3561 * Timer running if the active_queue is currently idling inside its time slice
3562 */
3563static void cfq_idle_slice_timer(unsigned long data)
3564{
3565 struct cfq_data *cfqd = (struct cfq_data *) data;
3566 struct cfq_queue *cfqq;
3567 unsigned long flags;
Jens Axboe3c6bd2f2007-01-19 12:06:33 +11003568 int timed_out = 1;
Jens Axboe22e2c502005-06-27 10:55:12 +02003569
Jens Axboe7b679132008-05-30 12:23:07 +02003570 cfq_log(cfqd, "idle timer fired");
3571
Jens Axboe22e2c502005-06-27 10:55:12 +02003572 spin_lock_irqsave(cfqd->queue->queue_lock, flags);
3573
Jens Axboefe094d92008-01-31 13:08:54 +01003574 cfqq = cfqd->active_queue;
3575 if (cfqq) {
Jens Axboe3c6bd2f2007-01-19 12:06:33 +11003576 timed_out = 0;
3577
Jens Axboe22e2c502005-06-27 10:55:12 +02003578 /*
Jens Axboeb0291952009-04-07 11:38:31 +02003579 * We saw a request before the queue expired, let it through
3580 */
3581 if (cfq_cfqq_must_dispatch(cfqq))
3582 goto out_kick;
3583
3584 /*
Jens Axboe22e2c502005-06-27 10:55:12 +02003585 * expired
3586 */
Jens Axboe44f7c162007-01-19 11:51:58 +11003587 if (cfq_slice_used(cfqq))
Jens Axboe22e2c502005-06-27 10:55:12 +02003588 goto expire;
3589
3590 /*
3591 * only expire and reinvoke request handler, if there are
3592 * other queues with pending requests
3593 */
Jens Axboecaaa5f92006-06-16 11:23:00 +02003594 if (!cfqd->busy_queues)
Jens Axboe22e2c502005-06-27 10:55:12 +02003595 goto out_cont;
Jens Axboe22e2c502005-06-27 10:55:12 +02003596
3597 /*
3598 * not expired and it has a request pending, let it dispatch
3599 */
Jens Axboe75e50982009-04-07 08:56:14 +02003600 if (!RB_EMPTY_ROOT(&cfqq->sort_list))
Jens Axboe22e2c502005-06-27 10:55:12 +02003601 goto out_kick;
Corrado Zoccolo76280af2009-11-26 10:02:58 +01003602
3603 /*
3604 * Queue depth flag is reset only when the idle didn't succeed
3605 */
3606 cfq_clear_cfqq_deep(cfqq);
Jens Axboe22e2c502005-06-27 10:55:12 +02003607 }
3608expire:
Jens Axboe6084cdd2007-04-23 08:25:00 +02003609 cfq_slice_expired(cfqd, timed_out);
Jens Axboe22e2c502005-06-27 10:55:12 +02003610out_kick:
Jens Axboe23e018a2009-10-05 08:52:35 +02003611 cfq_schedule_dispatch(cfqd);
Jens Axboe22e2c502005-06-27 10:55:12 +02003612out_cont:
3613 spin_unlock_irqrestore(cfqd->queue->queue_lock, flags);
3614}
3615
Jens Axboe3b181522005-06-27 10:56:24 +02003616static void cfq_shutdown_timer_wq(struct cfq_data *cfqd)
3617{
3618 del_timer_sync(&cfqd->idle_slice_timer);
Jens Axboe23e018a2009-10-05 08:52:35 +02003619 cancel_work_sync(&cfqd->unplug_work);
Jens Axboe3b181522005-06-27 10:56:24 +02003620}
Jens Axboe22e2c502005-06-27 10:55:12 +02003621
Vasily Tarasovc2dea2d2007-07-20 10:06:38 +02003622static void cfq_put_async_queues(struct cfq_data *cfqd)
3623{
3624 int i;
3625
3626 for (i = 0; i < IOPRIO_BE_NR; i++) {
3627 if (cfqd->async_cfqq[0][i])
3628 cfq_put_queue(cfqd->async_cfqq[0][i]);
3629 if (cfqd->async_cfqq[1][i])
3630 cfq_put_queue(cfqd->async_cfqq[1][i]);
Vasily Tarasovc2dea2d2007-07-20 10:06:38 +02003631 }
Oleg Nesterov2389d1e2007-11-05 08:58:05 +01003632
3633 if (cfqd->async_idle_cfqq)
3634 cfq_put_queue(cfqd->async_idle_cfqq);
Vasily Tarasovc2dea2d2007-07-20 10:06:38 +02003635}
3636
Jens Axboebb729bc2009-12-06 09:54:19 +01003637static void cfq_cfqd_free(struct rcu_head *head)
3638{
3639 kfree(container_of(head, struct cfq_data, rcu));
3640}
3641
Jens Axboeb374d182008-10-31 10:05:07 +01003642static void cfq_exit_queue(struct elevator_queue *e)
Linus Torvalds1da177e2005-04-16 15:20:36 -07003643{
Jens Axboe22e2c502005-06-27 10:55:12 +02003644 struct cfq_data *cfqd = e->elevator_data;
Jens Axboe165125e2007-07-24 09:28:11 +02003645 struct request_queue *q = cfqd->queue;
Jens Axboe22e2c502005-06-27 10:55:12 +02003646
Jens Axboe3b181522005-06-27 10:56:24 +02003647 cfq_shutdown_timer_wq(cfqd);
Jens Axboee2d74ac2006-03-28 08:59:01 +02003648
Al Virod9ff4182006-03-18 13:51:22 -05003649 spin_lock_irq(q->queue_lock);
Jens Axboee2d74ac2006-03-28 08:59:01 +02003650
Al Virod9ff4182006-03-18 13:51:22 -05003651 if (cfqd->active_queue)
Jens Axboe6084cdd2007-04-23 08:25:00 +02003652 __cfq_slice_expired(cfqd, cfqd->active_queue, 0);
Jens Axboee2d74ac2006-03-28 08:59:01 +02003653
3654 while (!list_empty(&cfqd->cic_list)) {
Al Virod9ff4182006-03-18 13:51:22 -05003655 struct cfq_io_context *cic = list_entry(cfqd->cic_list.next,
3656 struct cfq_io_context,
3657 queue_list);
Jens Axboe89850f72006-07-22 16:48:31 +02003658
3659 __cfq_exit_single_io_context(cfqd, cic);
Al Virod9ff4182006-03-18 13:51:22 -05003660 }
Jens Axboee2d74ac2006-03-28 08:59:01 +02003661
Vasily Tarasovc2dea2d2007-07-20 10:06:38 +02003662 cfq_put_async_queues(cfqd);
Vivek Goyalb1c35762009-12-03 12:59:47 -05003663 cfq_release_cfq_groups(cfqd);
3664 blkiocg_del_blkio_group(&cfqd->root_group.blkg);
Jens Axboe15c31be2007-07-10 13:43:25 +02003665
Al Virod9ff4182006-03-18 13:51:22 -05003666 spin_unlock_irq(q->queue_lock);
Al Viroa90d7422006-03-18 12:05:37 -05003667
3668 cfq_shutdown_timer_wq(cfqd);
3669
Vivek Goyalb1c35762009-12-03 12:59:47 -05003670 /* Wait for cfqg->blkg->key accessors to exit their grace periods. */
Jens Axboebb729bc2009-12-06 09:54:19 +01003671 call_rcu(&cfqd->rcu, cfq_cfqd_free);
Linus Torvalds1da177e2005-04-16 15:20:36 -07003672}
3673
Jens Axboe165125e2007-07-24 09:28:11 +02003674static void *cfq_init_queue(struct request_queue *q)
Linus Torvalds1da177e2005-04-16 15:20:36 -07003675{
3676 struct cfq_data *cfqd;
Corrado Zoccolo718eee02009-10-26 22:45:29 +01003677 int i, j;
Vivek Goyalcdb16e82009-12-03 12:59:38 -05003678 struct cfq_group *cfqg;
Vivek Goyal615f0252009-12-03 12:59:39 -05003679 struct cfq_rb_root *st;
Linus Torvalds1da177e2005-04-16 15:20:36 -07003680
Christoph Lameter94f60302007-07-17 04:03:29 -07003681 cfqd = kmalloc_node(sizeof(*cfqd), GFP_KERNEL | __GFP_ZERO, q->node);
Linus Torvalds1da177e2005-04-16 15:20:36 -07003682 if (!cfqd)
Jens Axboebc1c1162006-06-08 08:49:06 +02003683 return NULL;
Linus Torvalds1da177e2005-04-16 15:20:36 -07003684
Vivek Goyal1fa8f6d2009-12-03 12:59:41 -05003685 /* Init root service tree */
3686 cfqd->grp_service_tree = CFQ_RB_ROOT;
3687
Vivek Goyalcdb16e82009-12-03 12:59:38 -05003688 /* Init root group */
3689 cfqg = &cfqd->root_group;
Vivek Goyal615f0252009-12-03 12:59:39 -05003690 for_each_cfqg_st(cfqg, i, j, st)
3691 *st = CFQ_RB_ROOT;
Vivek Goyal1fa8f6d2009-12-03 12:59:41 -05003692 RB_CLEAR_NODE(&cfqg->rb_node);
Jens Axboe26a2ac02009-04-23 12:13:27 +02003693
Vivek Goyal25bc6b02009-12-03 12:59:43 -05003694 /* Give preference to root group over other groups */
3695 cfqg->weight = 2*BLKIO_WEIGHT_DEFAULT;
3696
Vivek Goyal25fb5162009-12-03 12:59:46 -05003697#ifdef CONFIG_CFQ_GROUP_IOSCHED
Vivek Goyalb1c35762009-12-03 12:59:47 -05003698 /*
3699 * Take a reference to root group which we never drop. This is just
3700 * to make sure that cfq_put_cfqg() does not try to kfree root group
3701 */
3702 atomic_set(&cfqg->ref, 1);
Vivek Goyal22084192009-12-03 12:59:49 -05003703 blkiocg_add_blkio_group(&blkio_root_cgroup, &cfqg->blkg, (void *)cfqd,
3704 0);
Vivek Goyal25fb5162009-12-03 12:59:46 -05003705#endif
Jens Axboe26a2ac02009-04-23 12:13:27 +02003706 /*
3707 * Not strictly needed (since RB_ROOT just clears the node and we
3708 * zeroed cfqd on alloc), but better be safe in case someone decides
3709 * to add magic to the rb code
3710 */
3711 for (i = 0; i < CFQ_PRIO_LISTS; i++)
3712 cfqd->prio_trees[i] = RB_ROOT;
3713
Jens Axboe6118b702009-06-30 09:34:12 +02003714 /*
3715 * Our fallback cfqq if cfq_find_alloc_queue() runs into OOM issues.
3716 * Grab a permanent reference to it, so that the normal code flow
3717 * will not attempt to free it.
3718 */
3719 cfq_init_cfqq(cfqd, &cfqd->oom_cfqq, 1, 0);
3720 atomic_inc(&cfqd->oom_cfqq.ref);
Vivek Goyalcdb16e82009-12-03 12:59:38 -05003721 cfq_link_cfqq_cfqg(&cfqd->oom_cfqq, &cfqd->root_group);
Jens Axboe6118b702009-06-30 09:34:12 +02003722
Al Virod9ff4182006-03-18 13:51:22 -05003723 INIT_LIST_HEAD(&cfqd->cic_list);
Linus Torvalds1da177e2005-04-16 15:20:36 -07003724
Linus Torvalds1da177e2005-04-16 15:20:36 -07003725 cfqd->queue = q;
Linus Torvalds1da177e2005-04-16 15:20:36 -07003726
Jens Axboe22e2c502005-06-27 10:55:12 +02003727 init_timer(&cfqd->idle_slice_timer);
3728 cfqd->idle_slice_timer.function = cfq_idle_slice_timer;
3729 cfqd->idle_slice_timer.data = (unsigned long) cfqd;
3730
Jens Axboe23e018a2009-10-05 08:52:35 +02003731 INIT_WORK(&cfqd->unplug_work, cfq_kick_queue);
Jens Axboe22e2c502005-06-27 10:55:12 +02003732
Linus Torvalds1da177e2005-04-16 15:20:36 -07003733 cfqd->cfq_quantum = cfq_quantum;
Jens Axboe22e2c502005-06-27 10:55:12 +02003734 cfqd->cfq_fifo_expire[0] = cfq_fifo_expire[0];
3735 cfqd->cfq_fifo_expire[1] = cfq_fifo_expire[1];
Linus Torvalds1da177e2005-04-16 15:20:36 -07003736 cfqd->cfq_back_max = cfq_back_max;
3737 cfqd->cfq_back_penalty = cfq_back_penalty;
Jens Axboe22e2c502005-06-27 10:55:12 +02003738 cfqd->cfq_slice[0] = cfq_slice_async;
3739 cfqd->cfq_slice[1] = cfq_slice_sync;
3740 cfqd->cfq_slice_async_rq = cfq_slice_async_rq;
3741 cfqd->cfq_slice_idle = cfq_slice_idle;
Jens Axboe963b72f2009-10-03 19:42:18 +02003742 cfqd->cfq_latency = 1;
Vivek Goyalae30c282009-12-03 12:59:55 -05003743 cfqd->cfq_group_isolation = 0;
Corrado Zoccoloe459dd02009-11-26 10:02:57 +01003744 cfqd->hw_tag = -1;
Corrado Zoccoloedc71132009-12-09 20:56:04 +01003745 /*
3746 * we optimistically start assuming sync ops weren't delayed in last
3747 * second, in order to have larger depth for async operations.
3748 */
Corrado Zoccolo573412b2009-12-06 11:48:52 +01003749 cfqd->last_delayed_sync = jiffies - HZ;
Jens Axboebb729bc2009-12-06 09:54:19 +01003750 INIT_RCU_HEAD(&cfqd->rcu);
Jens Axboebc1c1162006-06-08 08:49:06 +02003751 return cfqd;
Linus Torvalds1da177e2005-04-16 15:20:36 -07003752}
3753
3754static void cfq_slab_kill(void)
3755{
Jens Axboed6de8be2008-05-28 14:46:59 +02003756 /*
3757 * Caller already ensured that pending RCU callbacks are completed,
3758 * so we should have no busy allocations at this point.
3759 */
Linus Torvalds1da177e2005-04-16 15:20:36 -07003760 if (cfq_pool)
3761 kmem_cache_destroy(cfq_pool);
3762 if (cfq_ioc_pool)
3763 kmem_cache_destroy(cfq_ioc_pool);
3764}
3765
3766static int __init cfq_slab_setup(void)
3767{
Christoph Lameter0a31bd52007-05-06 14:49:57 -07003768 cfq_pool = KMEM_CACHE(cfq_queue, 0);
Linus Torvalds1da177e2005-04-16 15:20:36 -07003769 if (!cfq_pool)
3770 goto fail;
3771
Fabio Checconi34e6bbf2008-04-02 14:31:02 +02003772 cfq_ioc_pool = KMEM_CACHE(cfq_io_context, 0);
Linus Torvalds1da177e2005-04-16 15:20:36 -07003773 if (!cfq_ioc_pool)
3774 goto fail;
3775
3776 return 0;
3777fail:
3778 cfq_slab_kill();
3779 return -ENOMEM;
3780}
3781
Linus Torvalds1da177e2005-04-16 15:20:36 -07003782/*
3783 * sysfs parts below -->
3784 */
Linus Torvalds1da177e2005-04-16 15:20:36 -07003785static ssize_t
3786cfq_var_show(unsigned int var, char *page)
3787{
3788 return sprintf(page, "%d\n", var);
3789}
3790
3791static ssize_t
3792cfq_var_store(unsigned int *var, const char *page, size_t count)
3793{
3794 char *p = (char *) page;
3795
3796 *var = simple_strtoul(p, &p, 10);
3797 return count;
3798}
3799
Linus Torvalds1da177e2005-04-16 15:20:36 -07003800#define SHOW_FUNCTION(__FUNC, __VAR, __CONV) \
Jens Axboeb374d182008-10-31 10:05:07 +01003801static ssize_t __FUNC(struct elevator_queue *e, char *page) \
Linus Torvalds1da177e2005-04-16 15:20:36 -07003802{ \
Al Viro3d1ab402006-03-18 18:35:43 -05003803 struct cfq_data *cfqd = e->elevator_data; \
Linus Torvalds1da177e2005-04-16 15:20:36 -07003804 unsigned int __data = __VAR; \
3805 if (__CONV) \
3806 __data = jiffies_to_msecs(__data); \
3807 return cfq_var_show(__data, (page)); \
3808}
3809SHOW_FUNCTION(cfq_quantum_show, cfqd->cfq_quantum, 0);
Jens Axboe22e2c502005-06-27 10:55:12 +02003810SHOW_FUNCTION(cfq_fifo_expire_sync_show, cfqd->cfq_fifo_expire[1], 1);
3811SHOW_FUNCTION(cfq_fifo_expire_async_show, cfqd->cfq_fifo_expire[0], 1);
Al Viroe572ec72006-03-18 22:27:18 -05003812SHOW_FUNCTION(cfq_back_seek_max_show, cfqd->cfq_back_max, 0);
3813SHOW_FUNCTION(cfq_back_seek_penalty_show, cfqd->cfq_back_penalty, 0);
Jens Axboe22e2c502005-06-27 10:55:12 +02003814SHOW_FUNCTION(cfq_slice_idle_show, cfqd->cfq_slice_idle, 1);
3815SHOW_FUNCTION(cfq_slice_sync_show, cfqd->cfq_slice[1], 1);
3816SHOW_FUNCTION(cfq_slice_async_show, cfqd->cfq_slice[0], 1);
3817SHOW_FUNCTION(cfq_slice_async_rq_show, cfqd->cfq_slice_async_rq, 0);
Jens Axboe963b72f2009-10-03 19:42:18 +02003818SHOW_FUNCTION(cfq_low_latency_show, cfqd->cfq_latency, 0);
Vivek Goyalae30c282009-12-03 12:59:55 -05003819SHOW_FUNCTION(cfq_group_isolation_show, cfqd->cfq_group_isolation, 0);
Linus Torvalds1da177e2005-04-16 15:20:36 -07003820#undef SHOW_FUNCTION
3821
3822#define STORE_FUNCTION(__FUNC, __PTR, MIN, MAX, __CONV) \
Jens Axboeb374d182008-10-31 10:05:07 +01003823static ssize_t __FUNC(struct elevator_queue *e, const char *page, size_t count) \
Linus Torvalds1da177e2005-04-16 15:20:36 -07003824{ \
Al Viro3d1ab402006-03-18 18:35:43 -05003825 struct cfq_data *cfqd = e->elevator_data; \
Linus Torvalds1da177e2005-04-16 15:20:36 -07003826 unsigned int __data; \
3827 int ret = cfq_var_store(&__data, (page), count); \
3828 if (__data < (MIN)) \
3829 __data = (MIN); \
3830 else if (__data > (MAX)) \
3831 __data = (MAX); \
3832 if (__CONV) \
3833 *(__PTR) = msecs_to_jiffies(__data); \
3834 else \
3835 *(__PTR) = __data; \
3836 return ret; \
3837}
3838STORE_FUNCTION(cfq_quantum_store, &cfqd->cfq_quantum, 1, UINT_MAX, 0);
Jens Axboefe094d92008-01-31 13:08:54 +01003839STORE_FUNCTION(cfq_fifo_expire_sync_store, &cfqd->cfq_fifo_expire[1], 1,
3840 UINT_MAX, 1);
3841STORE_FUNCTION(cfq_fifo_expire_async_store, &cfqd->cfq_fifo_expire[0], 1,
3842 UINT_MAX, 1);
Al Viroe572ec72006-03-18 22:27:18 -05003843STORE_FUNCTION(cfq_back_seek_max_store, &cfqd->cfq_back_max, 0, UINT_MAX, 0);
Jens Axboefe094d92008-01-31 13:08:54 +01003844STORE_FUNCTION(cfq_back_seek_penalty_store, &cfqd->cfq_back_penalty, 1,
3845 UINT_MAX, 0);
Jens Axboe22e2c502005-06-27 10:55:12 +02003846STORE_FUNCTION(cfq_slice_idle_store, &cfqd->cfq_slice_idle, 0, UINT_MAX, 1);
3847STORE_FUNCTION(cfq_slice_sync_store, &cfqd->cfq_slice[1], 1, UINT_MAX, 1);
3848STORE_FUNCTION(cfq_slice_async_store, &cfqd->cfq_slice[0], 1, UINT_MAX, 1);
Jens Axboefe094d92008-01-31 13:08:54 +01003849STORE_FUNCTION(cfq_slice_async_rq_store, &cfqd->cfq_slice_async_rq, 1,
3850 UINT_MAX, 0);
Jens Axboe963b72f2009-10-03 19:42:18 +02003851STORE_FUNCTION(cfq_low_latency_store, &cfqd->cfq_latency, 0, 1, 0);
Vivek Goyalae30c282009-12-03 12:59:55 -05003852STORE_FUNCTION(cfq_group_isolation_store, &cfqd->cfq_group_isolation, 0, 1, 0);
Linus Torvalds1da177e2005-04-16 15:20:36 -07003853#undef STORE_FUNCTION
3854
Al Viroe572ec72006-03-18 22:27:18 -05003855#define CFQ_ATTR(name) \
3856 __ATTR(name, S_IRUGO|S_IWUSR, cfq_##name##_show, cfq_##name##_store)
Jens Axboe3b181522005-06-27 10:56:24 +02003857
Al Viroe572ec72006-03-18 22:27:18 -05003858static struct elv_fs_entry cfq_attrs[] = {
3859 CFQ_ATTR(quantum),
Al Viroe572ec72006-03-18 22:27:18 -05003860 CFQ_ATTR(fifo_expire_sync),
3861 CFQ_ATTR(fifo_expire_async),
3862 CFQ_ATTR(back_seek_max),
3863 CFQ_ATTR(back_seek_penalty),
3864 CFQ_ATTR(slice_sync),
3865 CFQ_ATTR(slice_async),
3866 CFQ_ATTR(slice_async_rq),
3867 CFQ_ATTR(slice_idle),
Jens Axboe963b72f2009-10-03 19:42:18 +02003868 CFQ_ATTR(low_latency),
Vivek Goyalae30c282009-12-03 12:59:55 -05003869 CFQ_ATTR(group_isolation),
Al Viroe572ec72006-03-18 22:27:18 -05003870 __ATTR_NULL
Linus Torvalds1da177e2005-04-16 15:20:36 -07003871};
3872
Linus Torvalds1da177e2005-04-16 15:20:36 -07003873static struct elevator_type iosched_cfq = {
3874 .ops = {
3875 .elevator_merge_fn = cfq_merge,
3876 .elevator_merged_fn = cfq_merged_request,
3877 .elevator_merge_req_fn = cfq_merged_requests,
Jens Axboeda775262006-12-20 11:04:12 +01003878 .elevator_allow_merge_fn = cfq_allow_merge,
Jens Axboeb4878f22005-10-20 16:42:29 +02003879 .elevator_dispatch_fn = cfq_dispatch_requests,
Linus Torvalds1da177e2005-04-16 15:20:36 -07003880 .elevator_add_req_fn = cfq_insert_request,
Jens Axboeb4878f22005-10-20 16:42:29 +02003881 .elevator_activate_req_fn = cfq_activate_request,
Linus Torvalds1da177e2005-04-16 15:20:36 -07003882 .elevator_deactivate_req_fn = cfq_deactivate_request,
3883 .elevator_queue_empty_fn = cfq_queue_empty,
3884 .elevator_completed_req_fn = cfq_completed_request,
Jens Axboe21183b02006-07-13 12:33:14 +02003885 .elevator_former_req_fn = elv_rb_former_request,
3886 .elevator_latter_req_fn = elv_rb_latter_request,
Linus Torvalds1da177e2005-04-16 15:20:36 -07003887 .elevator_set_req_fn = cfq_set_request,
3888 .elevator_put_req_fn = cfq_put_request,
3889 .elevator_may_queue_fn = cfq_may_queue,
3890 .elevator_init_fn = cfq_init_queue,
3891 .elevator_exit_fn = cfq_exit_queue,
Jens Axboefc463792006-08-29 09:05:44 +02003892 .trim = cfq_free_io_context,
Linus Torvalds1da177e2005-04-16 15:20:36 -07003893 },
Al Viro3d1ab402006-03-18 18:35:43 -05003894 .elevator_attrs = cfq_attrs,
Linus Torvalds1da177e2005-04-16 15:20:36 -07003895 .elevator_name = "cfq",
3896 .elevator_owner = THIS_MODULE,
3897};
3898
Vivek Goyal3e252062009-12-04 10:36:42 -05003899#ifdef CONFIG_CFQ_GROUP_IOSCHED
3900static struct blkio_policy_type blkio_policy_cfq = {
3901 .ops = {
3902 .blkio_unlink_group_fn = cfq_unlink_blkio_group,
3903 .blkio_update_group_weight_fn = cfq_update_blkio_group_weight,
3904 },
3905};
3906#else
3907static struct blkio_policy_type blkio_policy_cfq;
3908#endif
3909
Linus Torvalds1da177e2005-04-16 15:20:36 -07003910static int __init cfq_init(void)
3911{
Jens Axboe22e2c502005-06-27 10:55:12 +02003912 /*
3913 * could be 0 on HZ < 1000 setups
3914 */
3915 if (!cfq_slice_async)
3916 cfq_slice_async = 1;
3917 if (!cfq_slice_idle)
3918 cfq_slice_idle = 1;
3919
Linus Torvalds1da177e2005-04-16 15:20:36 -07003920 if (cfq_slab_setup())
3921 return -ENOMEM;
3922
Adrian Bunk2fdd82b2007-12-12 18:51:56 +01003923 elv_register(&iosched_cfq);
Vivek Goyal3e252062009-12-04 10:36:42 -05003924 blkio_policy_register(&blkio_policy_cfq);
Linus Torvalds1da177e2005-04-16 15:20:36 -07003925
Adrian Bunk2fdd82b2007-12-12 18:51:56 +01003926 return 0;
Linus Torvalds1da177e2005-04-16 15:20:36 -07003927}
3928
3929static void __exit cfq_exit(void)
3930{
Peter Zijlstra6e9a4732006-09-30 23:28:10 -07003931 DECLARE_COMPLETION_ONSTACK(all_gone);
Vivek Goyal3e252062009-12-04 10:36:42 -05003932 blkio_policy_unregister(&blkio_policy_cfq);
Linus Torvalds1da177e2005-04-16 15:20:36 -07003933 elv_unregister(&iosched_cfq);
Al Viro334e94d2006-03-18 15:05:53 -05003934 ioc_gone = &all_gone;
OGAWA Hirofumifba82272006-04-18 09:44:06 +02003935 /* ioc_gone's update must be visible before reading ioc_count */
3936 smp_wmb();
Jens Axboed6de8be2008-05-28 14:46:59 +02003937
3938 /*
3939 * this also protects us from entering cfq_slab_kill() with
3940 * pending RCU callbacks
3941 */
Tejun Heo245b2e72009-06-24 15:13:48 +09003942 if (elv_ioc_count_read(cfq_ioc_count))
Jens Axboe9a11b4e2008-05-29 09:32:08 +02003943 wait_for_completion(&all_gone);
Christoph Hellwig83521d32005-10-30 15:01:39 -08003944 cfq_slab_kill();
Linus Torvalds1da177e2005-04-16 15:20:36 -07003945}
3946
3947module_init(cfq_init);
3948module_exit(cfq_exit);
3949
3950MODULE_AUTHOR("Jens Axboe");
3951MODULE_LICENSE("GPL");
3952MODULE_DESCRIPTION("Completely Fair Queueing IO scheduler");