blob: 023f4e69a3378cab44faefbf6c69823e6ec16b48 [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
Jens Axboe22e2c502005-06-27 10:55:12 +020045#define CFQ_SLICE_SCALE (5)
Aaron Carroll45333d52008-08-26 15:52:36 +020046#define CFQ_HW_QUEUE_MIN (5)
Vivek Goyal25bc6b02009-12-03 12:59:43 -050047#define CFQ_SERVICE_SHIFT 12
Jens Axboe22e2c502005-06-27 10:55:12 +020048
Shaohua Liae54abe2010-02-05 13:11:45 +010049#define CFQQ_SEEK_THR 8 * 1024
50#define CFQQ_SEEKY(cfqq) ((cfqq)->seek_mean > CFQQ_SEEK_THR)
51
Jens Axboefe094d92008-01-31 13:08:54 +010052#define RQ_CIC(rq) \
53 ((struct cfq_io_context *) (rq)->elevator_private)
Jens Axboe7b679132008-05-30 12:23:07 +020054#define RQ_CFQQ(rq) (struct cfq_queue *) ((rq)->elevator_private2)
Linus Torvalds1da177e2005-04-16 15:20:36 -070055
Christoph Lametere18b8902006-12-06 20:33:20 -080056static struct kmem_cache *cfq_pool;
57static struct kmem_cache *cfq_ioc_pool;
Linus Torvalds1da177e2005-04-16 15:20:36 -070058
Tejun Heo245b2e72009-06-24 15:13:48 +090059static DEFINE_PER_CPU(unsigned long, cfq_ioc_count);
Al Viro334e94d2006-03-18 15:05:53 -050060static struct completion *ioc_gone;
Jens Axboe9a11b4e2008-05-29 09:32:08 +020061static DEFINE_SPINLOCK(ioc_gone_lock);
Al Viro334e94d2006-03-18 15:05:53 -050062
Jens Axboe22e2c502005-06-27 10:55:12 +020063#define CFQ_PRIO_LISTS IOPRIO_BE_NR
64#define cfq_class_idle(cfqq) ((cfqq)->ioprio_class == IOPRIO_CLASS_IDLE)
Jens Axboe22e2c502005-06-27 10:55:12 +020065#define cfq_class_rt(cfqq) ((cfqq)->ioprio_class == IOPRIO_CLASS_RT)
66
Jens Axboe206dc692006-03-28 13:03:44 +020067#define sample_valid(samples) ((samples) > 80)
Vivek Goyal1fa8f6d2009-12-03 12:59:41 -050068#define rb_entry_cfqg(node) rb_entry((node), struct cfq_group, rb_node)
Jens Axboe206dc692006-03-28 13:03:44 +020069
Jens Axboe22e2c502005-06-27 10:55:12 +020070/*
Jens Axboecc09e292007-04-26 12:53:50 +020071 * Most of our rbtree usage is for sorting with min extraction, so
72 * if we cache the leftmost node we don't have to walk down the tree
73 * to find it. Idea borrowed from Ingo Molnars CFS scheduler. We should
74 * move this into the elevator for the rq sorting as well.
75 */
76struct cfq_rb_root {
77 struct rb_root rb;
78 struct rb_node *left;
Corrado Zoccoloaa6f6a32009-10-26 22:44:33 +010079 unsigned count;
Vivek Goyal1fa8f6d2009-12-03 12:59:41 -050080 u64 min_vdisktime;
Vivek Goyal25bc6b02009-12-03 12:59:43 -050081 struct rb_node *active;
Vivek Goyal58ff82f2009-12-03 12:59:44 -050082 unsigned total_weight;
Jens Axboecc09e292007-04-26 12:53:50 +020083};
Vivek Goyal1fa8f6d2009-12-03 12:59:41 -050084#define CFQ_RB_ROOT (struct cfq_rb_root) { RB_ROOT, NULL, 0, 0, }
Jens Axboecc09e292007-04-26 12:53:50 +020085
86/*
Jens Axboe6118b702009-06-30 09:34:12 +020087 * Per process-grouping structure
88 */
89struct cfq_queue {
90 /* reference count */
91 atomic_t ref;
92 /* various state flags, see below */
93 unsigned int flags;
94 /* parent cfq_data */
95 struct cfq_data *cfqd;
96 /* service_tree member */
97 struct rb_node rb_node;
98 /* service_tree key */
99 unsigned long rb_key;
100 /* prio tree member */
101 struct rb_node p_node;
102 /* prio tree root we belong to, if any */
103 struct rb_root *p_root;
104 /* sorted list of pending requests */
105 struct rb_root sort_list;
106 /* if fifo isn't expired, next request to serve */
107 struct request *next_rq;
108 /* requests queued in sort_list */
109 int queued[2];
110 /* currently allocated requests */
111 int allocated[2];
112 /* fifo list of requests in sort_list */
113 struct list_head fifo;
114
Vivek Goyaldae739e2009-12-03 12:59:45 -0500115 /* time when queue got scheduled in to dispatch first request. */
116 unsigned long dispatch_start;
Vivek Goyalf75edf22009-12-03 12:59:53 -0500117 unsigned int allocated_slice;
Vivek Goyaldae739e2009-12-03 12:59:45 -0500118 /* time when first request from queue completed and slice started. */
119 unsigned long slice_start;
Jens Axboe6118b702009-06-30 09:34:12 +0200120 unsigned long slice_end;
121 long slice_resid;
122 unsigned int slice_dispatch;
123
124 /* pending metadata requests */
125 int meta_pending;
126 /* number of requests that are on the dispatch list or inside driver */
127 int dispatched;
128
129 /* io prio of this group */
130 unsigned short ioprio, org_ioprio;
131 unsigned short ioprio_class, org_ioprio_class;
132
Jeff Moyerb2c18e12009-10-23 17:14:49 -0400133 unsigned int seek_samples;
134 u64 seek_total;
135 sector_t seek_mean;
136 sector_t last_request_pos;
137
Jens Axboe6118b702009-06-30 09:34:12 +0200138 pid_t pid;
Jeff Moyerdf5fe3e2009-10-23 17:14:50 -0400139
Corrado Zoccoloaa6f6a32009-10-26 22:44:33 +0100140 struct cfq_rb_root *service_tree;
Jeff Moyerdf5fe3e2009-10-23 17:14:50 -0400141 struct cfq_queue *new_cfqq;
Vivek Goyalcdb16e82009-12-03 12:59:38 -0500142 struct cfq_group *cfqg;
Vivek Goyalae30c282009-12-03 12:59:55 -0500143 struct cfq_group *orig_cfqg;
Vivek Goyal22084192009-12-03 12:59:49 -0500144 /* Sectors dispatched in current dispatch round */
145 unsigned long nr_sectors;
Jens Axboe6118b702009-06-30 09:34:12 +0200146};
147
148/*
Corrado Zoccolo718eee02009-10-26 22:45:29 +0100149 * First index in the service_trees.
Corrado Zoccoloc0324a02009-10-27 19:16:03 +0100150 * IDLE is handled separately, so it has negative index
151 */
152enum wl_prio_t {
Corrado Zoccoloc0324a02009-10-27 19:16:03 +0100153 BE_WORKLOAD = 0,
Vivek Goyal615f0252009-12-03 12:59:39 -0500154 RT_WORKLOAD = 1,
155 IDLE_WORKLOAD = 2,
Corrado Zoccoloc0324a02009-10-27 19:16:03 +0100156};
157
158/*
Corrado Zoccolo718eee02009-10-26 22:45:29 +0100159 * Second index in the service_trees.
160 */
161enum wl_type_t {
162 ASYNC_WORKLOAD = 0,
163 SYNC_NOIDLE_WORKLOAD = 1,
164 SYNC_WORKLOAD = 2
165};
166
Vivek Goyalcdb16e82009-12-03 12:59:38 -0500167/* This is per cgroup per device grouping structure */
168struct cfq_group {
Vivek Goyal1fa8f6d2009-12-03 12:59:41 -0500169 /* group service_tree member */
170 struct rb_node rb_node;
171
172 /* group service_tree key */
173 u64 vdisktime;
Vivek Goyal25bc6b02009-12-03 12:59:43 -0500174 unsigned int weight;
Vivek Goyal1fa8f6d2009-12-03 12:59:41 -0500175 bool on_st;
176
177 /* number of cfqq currently on this group */
178 int nr_cfqq;
179
Vivek Goyal58ff82f2009-12-03 12:59:44 -0500180 /* Per group busy queus average. Useful for workload slice calc. */
181 unsigned int busy_queues_avg[2];
Jens Axboe22e2c502005-06-27 10:55:12 +0200182 /*
Corrado Zoccoloc0324a02009-10-27 19:16:03 +0100183 * rr lists of queues with requests, onle rr for each priority class.
184 * Counts are embedded in the cfq_rb_root
Jens Axboe22e2c502005-06-27 10:55:12 +0200185 */
Corrado Zoccolo718eee02009-10-26 22:45:29 +0100186 struct cfq_rb_root service_trees[2][3];
Corrado Zoccoloc0324a02009-10-27 19:16:03 +0100187 struct cfq_rb_root service_tree_idle;
Vivek Goyaldae739e2009-12-03 12:59:45 -0500188
189 unsigned long saved_workload_slice;
190 enum wl_type_t saved_workload;
191 enum wl_prio_t saved_serving_prio;
Vivek Goyal25fb5162009-12-03 12:59:46 -0500192 struct blkio_group blkg;
193#ifdef CONFIG_CFQ_GROUP_IOSCHED
194 struct hlist_node cfqd_node;
Vivek Goyalb1c35762009-12-03 12:59:47 -0500195 atomic_t ref;
Vivek Goyal25fb5162009-12-03 12:59:46 -0500196#endif
Vivek Goyalcdb16e82009-12-03 12:59:38 -0500197};
198
199/*
200 * Per block device queue structure
201 */
202struct cfq_data {
203 struct request_queue *queue;
Vivek Goyal1fa8f6d2009-12-03 12:59:41 -0500204 /* Root service tree for cfq_groups */
205 struct cfq_rb_root grp_service_tree;
Vivek Goyalcdb16e82009-12-03 12:59:38 -0500206 struct cfq_group root_group;
207
Corrado Zoccoloc0324a02009-10-27 19:16:03 +0100208 /*
209 * The priority currently being served
210 */
211 enum wl_prio_t serving_prio;
Corrado Zoccolo718eee02009-10-26 22:45:29 +0100212 enum wl_type_t serving_type;
213 unsigned long workload_expires;
Vivek Goyalcdb16e82009-12-03 12:59:38 -0500214 struct cfq_group *serving_group;
Corrado Zoccolo8e550632009-11-26 10:02:58 +0100215 bool noidle_tree_requires_idle;
Jens Axboea36e71f2009-04-15 12:15:11 +0200216
217 /*
218 * Each priority tree is sorted by next_request position. These
219 * trees are used when determining if two or more queues are
220 * interleaving requests (see cfq_close_cooperator).
221 */
222 struct rb_root prio_trees[CFQ_PRIO_LISTS];
223
Jens Axboe22e2c502005-06-27 10:55:12 +0200224 unsigned int busy_queues;
225
Jens Axboe5ad531d2009-07-03 12:57:48 +0200226 int rq_in_driver[2];
Jens Axboe3ed9a292007-04-23 08:33:33 +0200227 int sync_flight;
Aaron Carroll45333d52008-08-26 15:52:36 +0200228
229 /*
230 * queue-depth detection
231 */
232 int rq_queued;
Jens Axboe25776e32006-06-01 10:12:26 +0200233 int hw_tag;
Corrado Zoccoloe459dd02009-11-26 10:02:57 +0100234 /*
235 * hw_tag can be
236 * -1 => indeterminate, (cfq will behave as if NCQ is present, to allow better detection)
237 * 1 => NCQ is present (hw_tag_est_depth is the estimated max depth)
238 * 0 => no NCQ
239 */
240 int hw_tag_est_depth;
241 unsigned int hw_tag_samples;
Jens Axboe22e2c502005-06-27 10:55:12 +0200242
243 /*
Jens Axboe22e2c502005-06-27 10:55:12 +0200244 * idle window management
245 */
246 struct timer_list idle_slice_timer;
Jens Axboe23e018a2009-10-05 08:52:35 +0200247 struct work_struct unplug_work;
Jens Axboe22e2c502005-06-27 10:55:12 +0200248
249 struct cfq_queue *active_queue;
250 struct cfq_io_context *active_cic;
Jens Axboe22e2c502005-06-27 10:55:12 +0200251
Vasily Tarasovc2dea2d2007-07-20 10:06:38 +0200252 /*
253 * async queue for each priority case
254 */
255 struct cfq_queue *async_cfqq[2][IOPRIO_BE_NR];
256 struct cfq_queue *async_idle_cfqq;
Jens Axboe15c31be2007-07-10 13:43:25 +0200257
Jens Axboe6d048f52007-04-25 12:44:27 +0200258 sector_t last_position;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700259
Linus Torvalds1da177e2005-04-16 15:20:36 -0700260 /*
261 * tunables, see top of file
262 */
263 unsigned int cfq_quantum;
Jens Axboe22e2c502005-06-27 10:55:12 +0200264 unsigned int cfq_fifo_expire[2];
Linus Torvalds1da177e2005-04-16 15:20:36 -0700265 unsigned int cfq_back_penalty;
266 unsigned int cfq_back_max;
Jens Axboe22e2c502005-06-27 10:55:12 +0200267 unsigned int cfq_slice[2];
268 unsigned int cfq_slice_async_rq;
269 unsigned int cfq_slice_idle;
Jens Axboe963b72f2009-10-03 19:42:18 +0200270 unsigned int cfq_latency;
Vivek Goyalae30c282009-12-03 12:59:55 -0500271 unsigned int cfq_group_isolation;
Al Virod9ff4182006-03-18 13:51:22 -0500272
273 struct list_head cic_list;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700274
Jens Axboe6118b702009-06-30 09:34:12 +0200275 /*
276 * Fallback dummy cfqq for extreme OOM conditions
277 */
278 struct cfq_queue oom_cfqq;
Vivek Goyal365722b2009-10-03 15:21:27 +0200279
Corrado Zoccolo573412b2009-12-06 11:48:52 +0100280 unsigned long last_delayed_sync;
Vivek Goyal25fb5162009-12-03 12:59:46 -0500281
282 /* List of cfq groups being managed on this device*/
283 struct hlist_head cfqg_list;
Jens Axboebb729bc2009-12-06 09:54:19 +0100284 struct rcu_head rcu;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700285};
286
Vivek Goyal25fb5162009-12-03 12:59:46 -0500287static struct cfq_group *cfq_get_next_cfqg(struct cfq_data *cfqd);
288
Vivek Goyalcdb16e82009-12-03 12:59:38 -0500289static struct cfq_rb_root *service_tree_for(struct cfq_group *cfqg,
290 enum wl_prio_t prio,
Vivek Goyal65b32a52009-12-16 17:52:59 -0500291 enum wl_type_t type)
Corrado Zoccoloc0324a02009-10-27 19:16:03 +0100292{
Vivek Goyal1fa8f6d2009-12-03 12:59:41 -0500293 if (!cfqg)
294 return NULL;
295
Corrado Zoccoloc0324a02009-10-27 19:16:03 +0100296 if (prio == IDLE_WORKLOAD)
Vivek Goyalcdb16e82009-12-03 12:59:38 -0500297 return &cfqg->service_tree_idle;
Corrado Zoccoloc0324a02009-10-27 19:16:03 +0100298
Vivek Goyalcdb16e82009-12-03 12:59:38 -0500299 return &cfqg->service_trees[prio][type];
Corrado Zoccoloc0324a02009-10-27 19:16:03 +0100300}
301
Jens Axboe3b181522005-06-27 10:56:24 +0200302enum cfqq_state_flags {
Jens Axboeb0b8d7492007-01-19 11:35:30 +1100303 CFQ_CFQQ_FLAG_on_rr = 0, /* on round-robin busy list */
304 CFQ_CFQQ_FLAG_wait_request, /* waiting for a request */
Jens Axboeb0291952009-04-07 11:38:31 +0200305 CFQ_CFQQ_FLAG_must_dispatch, /* must be allowed a dispatch */
Jens Axboeb0b8d7492007-01-19 11:35:30 +1100306 CFQ_CFQQ_FLAG_must_alloc_slice, /* per-slice must_alloc flag */
Jens Axboeb0b8d7492007-01-19 11:35:30 +1100307 CFQ_CFQQ_FLAG_fifo_expire, /* FIFO checked in this slice */
308 CFQ_CFQQ_FLAG_idle_window, /* slice idling enabled */
309 CFQ_CFQQ_FLAG_prio_changed, /* task priority has changed */
Jens Axboe44f7c162007-01-19 11:51:58 +1100310 CFQ_CFQQ_FLAG_slice_new, /* no requests dispatched in slice */
Vasily Tarasov91fac312007-04-25 12:29:51 +0200311 CFQ_CFQQ_FLAG_sync, /* synchronous queue */
Jeff Moyerb3b6d042009-10-23 17:14:51 -0400312 CFQ_CFQQ_FLAG_coop, /* cfqq is shared */
Shaohua Liae54abe2010-02-05 13:11:45 +0100313 CFQ_CFQQ_FLAG_split_coop, /* shared cfqq will be splitted */
Corrado Zoccolo76280af2009-11-26 10:02:58 +0100314 CFQ_CFQQ_FLAG_deep, /* sync cfqq experienced large depth */
Vivek Goyalf75edf22009-12-03 12:59:53 -0500315 CFQ_CFQQ_FLAG_wait_busy, /* Waiting for next request */
Jens Axboe3b181522005-06-27 10:56:24 +0200316};
317
318#define CFQ_CFQQ_FNS(name) \
319static inline void cfq_mark_cfqq_##name(struct cfq_queue *cfqq) \
320{ \
Jens Axboefe094d92008-01-31 13:08:54 +0100321 (cfqq)->flags |= (1 << CFQ_CFQQ_FLAG_##name); \
Jens Axboe3b181522005-06-27 10:56:24 +0200322} \
323static inline void cfq_clear_cfqq_##name(struct cfq_queue *cfqq) \
324{ \
Jens Axboefe094d92008-01-31 13:08:54 +0100325 (cfqq)->flags &= ~(1 << CFQ_CFQQ_FLAG_##name); \
Jens Axboe3b181522005-06-27 10:56:24 +0200326} \
327static inline int cfq_cfqq_##name(const struct cfq_queue *cfqq) \
328{ \
Jens Axboefe094d92008-01-31 13:08:54 +0100329 return ((cfqq)->flags & (1 << CFQ_CFQQ_FLAG_##name)) != 0; \
Jens Axboe3b181522005-06-27 10:56:24 +0200330}
331
332CFQ_CFQQ_FNS(on_rr);
333CFQ_CFQQ_FNS(wait_request);
Jens Axboeb0291952009-04-07 11:38:31 +0200334CFQ_CFQQ_FNS(must_dispatch);
Jens Axboe3b181522005-06-27 10:56:24 +0200335CFQ_CFQQ_FNS(must_alloc_slice);
Jens Axboe3b181522005-06-27 10:56:24 +0200336CFQ_CFQQ_FNS(fifo_expire);
337CFQ_CFQQ_FNS(idle_window);
338CFQ_CFQQ_FNS(prio_changed);
Jens Axboe44f7c162007-01-19 11:51:58 +1100339CFQ_CFQQ_FNS(slice_new);
Vasily Tarasov91fac312007-04-25 12:29:51 +0200340CFQ_CFQQ_FNS(sync);
Jens Axboea36e71f2009-04-15 12:15:11 +0200341CFQ_CFQQ_FNS(coop);
Shaohua Liae54abe2010-02-05 13:11:45 +0100342CFQ_CFQQ_FNS(split_coop);
Corrado Zoccolo76280af2009-11-26 10:02:58 +0100343CFQ_CFQQ_FNS(deep);
Vivek Goyalf75edf22009-12-03 12:59:53 -0500344CFQ_CFQQ_FNS(wait_busy);
Jens Axboe3b181522005-06-27 10:56:24 +0200345#undef CFQ_CFQQ_FNS
346
Vivek Goyal2868ef72009-12-03 12:59:48 -0500347#ifdef CONFIG_DEBUG_CFQ_IOSCHED
348#define cfq_log_cfqq(cfqd, cfqq, fmt, args...) \
349 blk_add_trace_msg((cfqd)->queue, "cfq%d%c %s " fmt, (cfqq)->pid, \
350 cfq_cfqq_sync((cfqq)) ? 'S' : 'A', \
351 blkg_path(&(cfqq)->cfqg->blkg), ##args);
352
353#define cfq_log_cfqg(cfqd, cfqg, fmt, args...) \
354 blk_add_trace_msg((cfqd)->queue, "%s " fmt, \
355 blkg_path(&(cfqg)->blkg), ##args); \
356
357#else
Jens Axboe7b679132008-05-30 12:23:07 +0200358#define cfq_log_cfqq(cfqd, cfqq, fmt, args...) \
359 blk_add_trace_msg((cfqd)->queue, "cfq%d " fmt, (cfqq)->pid, ##args)
Vivek Goyal2868ef72009-12-03 12:59:48 -0500360#define cfq_log_cfqg(cfqd, cfqg, fmt, args...) do {} while (0);
361#endif
Jens Axboe7b679132008-05-30 12:23:07 +0200362#define cfq_log(cfqd, fmt, args...) \
363 blk_add_trace_msg((cfqd)->queue, "cfq " fmt, ##args)
364
Vivek Goyal615f0252009-12-03 12:59:39 -0500365/* Traverses through cfq group service trees */
366#define for_each_cfqg_st(cfqg, i, j, st) \
367 for (i = 0; i <= IDLE_WORKLOAD; i++) \
368 for (j = 0, st = i < IDLE_WORKLOAD ? &cfqg->service_trees[i][j]\
369 : &cfqg->service_tree_idle; \
370 (i < IDLE_WORKLOAD && j <= SYNC_WORKLOAD) || \
371 (i == IDLE_WORKLOAD && j == 0); \
372 j++, st = i < IDLE_WORKLOAD ? \
373 &cfqg->service_trees[i][j]: NULL) \
374
375
Corrado Zoccoloc0324a02009-10-27 19:16:03 +0100376static inline enum wl_prio_t cfqq_prio(struct cfq_queue *cfqq)
377{
378 if (cfq_class_idle(cfqq))
379 return IDLE_WORKLOAD;
380 if (cfq_class_rt(cfqq))
381 return RT_WORKLOAD;
382 return BE_WORKLOAD;
383}
384
Corrado Zoccolo718eee02009-10-26 22:45:29 +0100385
386static enum wl_type_t cfqq_type(struct cfq_queue *cfqq)
387{
388 if (!cfq_cfqq_sync(cfqq))
389 return ASYNC_WORKLOAD;
390 if (!cfq_cfqq_idle_window(cfqq))
391 return SYNC_NOIDLE_WORKLOAD;
392 return SYNC_WORKLOAD;
393}
394
Vivek Goyal58ff82f2009-12-03 12:59:44 -0500395static inline int cfq_group_busy_queues_wl(enum wl_prio_t wl,
396 struct cfq_data *cfqd,
397 struct cfq_group *cfqg)
Corrado Zoccoloc0324a02009-10-27 19:16:03 +0100398{
Vivek Goyalcdb16e82009-12-03 12:59:38 -0500399 if (wl == IDLE_WORKLOAD)
400 return cfqg->service_tree_idle.count;
401
402 return cfqg->service_trees[wl][ASYNC_WORKLOAD].count
403 + cfqg->service_trees[wl][SYNC_NOIDLE_WORKLOAD].count
404 + cfqg->service_trees[wl][SYNC_WORKLOAD].count;
Corrado Zoccoloc0324a02009-10-27 19:16:03 +0100405}
406
Vivek Goyalf26bd1f2009-12-03 12:59:54 -0500407static inline int cfqg_busy_async_queues(struct cfq_data *cfqd,
408 struct cfq_group *cfqg)
409{
410 return cfqg->service_trees[RT_WORKLOAD][ASYNC_WORKLOAD].count
411 + cfqg->service_trees[BE_WORKLOAD][ASYNC_WORKLOAD].count;
412}
413
Jens Axboe165125e2007-07-24 09:28:11 +0200414static void cfq_dispatch_insert(struct request_queue *, struct request *);
Jens Axboea6151c32009-10-07 20:02:57 +0200415static struct cfq_queue *cfq_get_queue(struct cfq_data *, bool,
Jens Axboefd0928d2008-01-24 08:52:45 +0100416 struct io_context *, gfp_t);
Jens Axboe4ac845a2008-01-24 08:44:49 +0100417static struct cfq_io_context *cfq_cic_lookup(struct cfq_data *,
Vasily Tarasov91fac312007-04-25 12:29:51 +0200418 struct io_context *);
419
Jens Axboe5ad531d2009-07-03 12:57:48 +0200420static inline int rq_in_driver(struct cfq_data *cfqd)
421{
422 return cfqd->rq_in_driver[0] + cfqd->rq_in_driver[1];
423}
424
Vasily Tarasov91fac312007-04-25 12:29:51 +0200425static inline struct cfq_queue *cic_to_cfqq(struct cfq_io_context *cic,
Jens Axboea6151c32009-10-07 20:02:57 +0200426 bool is_sync)
Vasily Tarasov91fac312007-04-25 12:29:51 +0200427{
Jens Axboea6151c32009-10-07 20:02:57 +0200428 return cic->cfqq[is_sync];
Vasily Tarasov91fac312007-04-25 12:29:51 +0200429}
430
431static inline void cic_set_cfqq(struct cfq_io_context *cic,
Jens Axboea6151c32009-10-07 20:02:57 +0200432 struct cfq_queue *cfqq, bool is_sync)
Vasily Tarasov91fac312007-04-25 12:29:51 +0200433{
Jens Axboea6151c32009-10-07 20:02:57 +0200434 cic->cfqq[is_sync] = cfqq;
Vasily Tarasov91fac312007-04-25 12:29:51 +0200435}
436
437/*
438 * We regard a request as SYNC, if it's either a read or has the SYNC bit
439 * set (in which case it could also be direct WRITE).
440 */
Jens Axboea6151c32009-10-07 20:02:57 +0200441static inline bool cfq_bio_sync(struct bio *bio)
Vasily Tarasov91fac312007-04-25 12:29:51 +0200442{
Jens Axboea6151c32009-10-07 20:02:57 +0200443 return bio_data_dir(bio) == READ || bio_rw_flagged(bio, BIO_RW_SYNCIO);
Vasily Tarasov91fac312007-04-25 12:29:51 +0200444}
Linus Torvalds1da177e2005-04-16 15:20:36 -0700445
Linus Torvalds1da177e2005-04-16 15:20:36 -0700446/*
Andrew Morton99f95e52005-06-27 20:14:05 -0700447 * scheduler run of queue, if there are requests pending and no one in the
448 * driver that will restart queueing
449 */
Jens Axboe23e018a2009-10-05 08:52:35 +0200450static inline void cfq_schedule_dispatch(struct cfq_data *cfqd)
Andrew Morton99f95e52005-06-27 20:14:05 -0700451{
Jens Axboe7b679132008-05-30 12:23:07 +0200452 if (cfqd->busy_queues) {
453 cfq_log(cfqd, "schedule dispatch");
Jens Axboe23e018a2009-10-05 08:52:35 +0200454 kblockd_schedule_work(cfqd->queue, &cfqd->unplug_work);
Jens Axboe7b679132008-05-30 12:23:07 +0200455 }
Andrew Morton99f95e52005-06-27 20:14:05 -0700456}
457
Jens Axboe165125e2007-07-24 09:28:11 +0200458static int cfq_queue_empty(struct request_queue *q)
Andrew Morton99f95e52005-06-27 20:14:05 -0700459{
460 struct cfq_data *cfqd = q->elevator->elevator_data;
461
Vivek Goyalf04a6422009-12-03 12:59:40 -0500462 return !cfqd->rq_queued;
Andrew Morton99f95e52005-06-27 20:14:05 -0700463}
464
Linus Torvalds1da177e2005-04-16 15:20:36 -0700465/*
Jens Axboe44f7c162007-01-19 11:51:58 +1100466 * Scale schedule slice based on io priority. Use the sync time slice only
467 * if a queue is marked sync and has sync io queued. A sync queue with async
468 * io only, should not get full sync slice length.
469 */
Jens Axboea6151c32009-10-07 20:02:57 +0200470static inline int cfq_prio_slice(struct cfq_data *cfqd, bool sync,
Jens Axboed9e76202007-04-20 14:27:50 +0200471 unsigned short prio)
472{
473 const int base_slice = cfqd->cfq_slice[sync];
474
475 WARN_ON(prio >= IOPRIO_BE_NR);
476
477 return base_slice + (base_slice/CFQ_SLICE_SCALE * (4 - prio));
478}
479
Jens Axboe44f7c162007-01-19 11:51:58 +1100480static inline int
481cfq_prio_to_slice(struct cfq_data *cfqd, struct cfq_queue *cfqq)
482{
Jens Axboed9e76202007-04-20 14:27:50 +0200483 return cfq_prio_slice(cfqd, cfq_cfqq_sync(cfqq), cfqq->ioprio);
Jens Axboe44f7c162007-01-19 11:51:58 +1100484}
485
Vivek Goyal25bc6b02009-12-03 12:59:43 -0500486static inline u64 cfq_scale_slice(unsigned long delta, struct cfq_group *cfqg)
487{
488 u64 d = delta << CFQ_SERVICE_SHIFT;
489
490 d = d * BLKIO_WEIGHT_DEFAULT;
491 do_div(d, cfqg->weight);
492 return d;
493}
494
495static inline u64 max_vdisktime(u64 min_vdisktime, u64 vdisktime)
496{
497 s64 delta = (s64)(vdisktime - min_vdisktime);
498 if (delta > 0)
499 min_vdisktime = vdisktime;
500
501 return min_vdisktime;
502}
503
504static inline u64 min_vdisktime(u64 min_vdisktime, u64 vdisktime)
505{
506 s64 delta = (s64)(vdisktime - min_vdisktime);
507 if (delta < 0)
508 min_vdisktime = vdisktime;
509
510 return min_vdisktime;
511}
512
513static void update_min_vdisktime(struct cfq_rb_root *st)
514{
515 u64 vdisktime = st->min_vdisktime;
516 struct cfq_group *cfqg;
517
518 if (st->active) {
519 cfqg = rb_entry_cfqg(st->active);
520 vdisktime = cfqg->vdisktime;
521 }
522
523 if (st->left) {
524 cfqg = rb_entry_cfqg(st->left);
525 vdisktime = min_vdisktime(vdisktime, cfqg->vdisktime);
526 }
527
528 st->min_vdisktime = max_vdisktime(st->min_vdisktime, vdisktime);
529}
530
Corrado Zoccolo5db5d642009-10-26 22:44:04 +0100531/*
532 * get averaged number of queues of RT/BE priority.
533 * average is updated, with a formula that gives more weight to higher numbers,
534 * to quickly follows sudden increases and decrease slowly
535 */
536
Vivek Goyal58ff82f2009-12-03 12:59:44 -0500537static inline unsigned cfq_group_get_avg_queues(struct cfq_data *cfqd,
538 struct cfq_group *cfqg, bool rt)
Jens Axboe5869619c2009-10-28 09:27:07 +0100539{
Corrado Zoccolo5db5d642009-10-26 22:44:04 +0100540 unsigned min_q, max_q;
541 unsigned mult = cfq_hist_divisor - 1;
542 unsigned round = cfq_hist_divisor / 2;
Vivek Goyal58ff82f2009-12-03 12:59:44 -0500543 unsigned busy = cfq_group_busy_queues_wl(rt, cfqd, cfqg);
Corrado Zoccolo5db5d642009-10-26 22:44:04 +0100544
Vivek Goyal58ff82f2009-12-03 12:59:44 -0500545 min_q = min(cfqg->busy_queues_avg[rt], busy);
546 max_q = max(cfqg->busy_queues_avg[rt], busy);
547 cfqg->busy_queues_avg[rt] = (mult * max_q + min_q + round) /
Corrado Zoccolo5db5d642009-10-26 22:44:04 +0100548 cfq_hist_divisor;
Vivek Goyal58ff82f2009-12-03 12:59:44 -0500549 return cfqg->busy_queues_avg[rt];
550}
551
552static inline unsigned
553cfq_group_slice(struct cfq_data *cfqd, struct cfq_group *cfqg)
554{
555 struct cfq_rb_root *st = &cfqd->grp_service_tree;
556
557 return cfq_target_latency * cfqg->weight / st->total_weight;
Corrado Zoccolo5db5d642009-10-26 22:44:04 +0100558}
559
Jens Axboe44f7c162007-01-19 11:51:58 +1100560static inline void
561cfq_set_prio_slice(struct cfq_data *cfqd, struct cfq_queue *cfqq)
562{
Corrado Zoccolo5db5d642009-10-26 22:44:04 +0100563 unsigned slice = cfq_prio_to_slice(cfqd, cfqq);
564 if (cfqd->cfq_latency) {
Vivek Goyal58ff82f2009-12-03 12:59:44 -0500565 /*
566 * interested queues (we consider only the ones with the same
567 * priority class in the cfq group)
568 */
569 unsigned iq = cfq_group_get_avg_queues(cfqd, cfqq->cfqg,
570 cfq_class_rt(cfqq));
Corrado Zoccolo5db5d642009-10-26 22:44:04 +0100571 unsigned sync_slice = cfqd->cfq_slice[1];
572 unsigned expect_latency = sync_slice * iq;
Vivek Goyal58ff82f2009-12-03 12:59:44 -0500573 unsigned group_slice = cfq_group_slice(cfqd, cfqq->cfqg);
574
575 if (expect_latency > group_slice) {
Corrado Zoccolo5db5d642009-10-26 22:44:04 +0100576 unsigned base_low_slice = 2 * cfqd->cfq_slice_idle;
577 /* scale low_slice according to IO priority
578 * and sync vs async */
579 unsigned low_slice =
580 min(slice, base_low_slice * slice / sync_slice);
581 /* the adapted slice value is scaled to fit all iqs
582 * into the target latency */
Vivek Goyal58ff82f2009-12-03 12:59:44 -0500583 slice = max(slice * group_slice / expect_latency,
Corrado Zoccolo5db5d642009-10-26 22:44:04 +0100584 low_slice);
585 }
586 }
Vivek Goyaldae739e2009-12-03 12:59:45 -0500587 cfqq->slice_start = jiffies;
Corrado Zoccolo5db5d642009-10-26 22:44:04 +0100588 cfqq->slice_end = jiffies + slice;
Vivek Goyalf75edf22009-12-03 12:59:53 -0500589 cfqq->allocated_slice = slice;
Jens Axboe7b679132008-05-30 12:23:07 +0200590 cfq_log_cfqq(cfqd, cfqq, "set_slice=%lu", cfqq->slice_end - jiffies);
Jens Axboe44f7c162007-01-19 11:51:58 +1100591}
592
593/*
594 * We need to wrap this check in cfq_cfqq_slice_new(), since ->slice_end
595 * isn't valid until the first request from the dispatch is activated
596 * and the slice time set.
597 */
Jens Axboea6151c32009-10-07 20:02:57 +0200598static inline bool cfq_slice_used(struct cfq_queue *cfqq)
Jens Axboe44f7c162007-01-19 11:51:58 +1100599{
600 if (cfq_cfqq_slice_new(cfqq))
601 return 0;
602 if (time_before(jiffies, cfqq->slice_end))
603 return 0;
604
605 return 1;
606}
607
608/*
Jens Axboe5e705372006-07-13 12:39:25 +0200609 * Lifted from AS - choose which of rq1 and rq2 that is best served now.
Linus Torvalds1da177e2005-04-16 15:20:36 -0700610 * We choose the request that is closest to the head right now. Distance
Andreas Mohre8a99052006-03-28 08:59:49 +0200611 * behind the head is penalized and only allowed to a certain extent.
Linus Torvalds1da177e2005-04-16 15:20:36 -0700612 */
Jens Axboe5e705372006-07-13 12:39:25 +0200613static struct request *
Corrado Zoccolocf7c25c2009-11-08 17:16:46 +0100614cfq_choose_req(struct cfq_data *cfqd, struct request *rq1, struct request *rq2, sector_t last)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700615{
Corrado Zoccolocf7c25c2009-11-08 17:16:46 +0100616 sector_t s1, s2, d1 = 0, d2 = 0;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700617 unsigned long back_max;
Andreas Mohre8a99052006-03-28 08:59:49 +0200618#define CFQ_RQ1_WRAP 0x01 /* request 1 wraps */
619#define CFQ_RQ2_WRAP 0x02 /* request 2 wraps */
620 unsigned wrap = 0; /* bit mask: requests behind the disk head? */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700621
Jens Axboe5e705372006-07-13 12:39:25 +0200622 if (rq1 == NULL || rq1 == rq2)
623 return rq2;
624 if (rq2 == NULL)
625 return rq1;
Jens Axboe9c2c38a2005-08-24 14:57:54 +0200626
Jens Axboe5e705372006-07-13 12:39:25 +0200627 if (rq_is_sync(rq1) && !rq_is_sync(rq2))
628 return rq1;
629 else if (rq_is_sync(rq2) && !rq_is_sync(rq1))
630 return rq2;
Jens Axboe374f84a2006-07-23 01:42:19 +0200631 if (rq_is_meta(rq1) && !rq_is_meta(rq2))
632 return rq1;
633 else if (rq_is_meta(rq2) && !rq_is_meta(rq1))
634 return rq2;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700635
Tejun Heo83096eb2009-05-07 22:24:39 +0900636 s1 = blk_rq_pos(rq1);
637 s2 = blk_rq_pos(rq2);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700638
Linus Torvalds1da177e2005-04-16 15:20:36 -0700639 /*
640 * by definition, 1KiB is 2 sectors
641 */
642 back_max = cfqd->cfq_back_max * 2;
643
644 /*
645 * Strict one way elevator _except_ in the case where we allow
646 * short backward seeks which are biased as twice the cost of a
647 * similar forward seek.
648 */
649 if (s1 >= last)
650 d1 = s1 - last;
651 else if (s1 + back_max >= last)
652 d1 = (last - s1) * cfqd->cfq_back_penalty;
653 else
Andreas Mohre8a99052006-03-28 08:59:49 +0200654 wrap |= CFQ_RQ1_WRAP;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700655
656 if (s2 >= last)
657 d2 = s2 - last;
658 else if (s2 + back_max >= last)
659 d2 = (last - s2) * cfqd->cfq_back_penalty;
660 else
Andreas Mohre8a99052006-03-28 08:59:49 +0200661 wrap |= CFQ_RQ2_WRAP;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700662
663 /* Found required data */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700664
Andreas Mohre8a99052006-03-28 08:59:49 +0200665 /*
666 * By doing switch() on the bit mask "wrap" we avoid having to
667 * check two variables for all permutations: --> faster!
668 */
669 switch (wrap) {
Jens Axboe5e705372006-07-13 12:39:25 +0200670 case 0: /* common case for CFQ: rq1 and rq2 not wrapped */
Andreas Mohre8a99052006-03-28 08:59:49 +0200671 if (d1 < d2)
Jens Axboe5e705372006-07-13 12:39:25 +0200672 return rq1;
Andreas Mohre8a99052006-03-28 08:59:49 +0200673 else if (d2 < d1)
Jens Axboe5e705372006-07-13 12:39:25 +0200674 return rq2;
Andreas Mohre8a99052006-03-28 08:59:49 +0200675 else {
676 if (s1 >= s2)
Jens Axboe5e705372006-07-13 12:39:25 +0200677 return rq1;
Andreas Mohre8a99052006-03-28 08:59:49 +0200678 else
Jens Axboe5e705372006-07-13 12:39:25 +0200679 return rq2;
Andreas Mohre8a99052006-03-28 08:59:49 +0200680 }
681
682 case CFQ_RQ2_WRAP:
Jens Axboe5e705372006-07-13 12:39:25 +0200683 return rq1;
Andreas Mohre8a99052006-03-28 08:59:49 +0200684 case CFQ_RQ1_WRAP:
Jens Axboe5e705372006-07-13 12:39:25 +0200685 return rq2;
686 case (CFQ_RQ1_WRAP|CFQ_RQ2_WRAP): /* both rqs wrapped */
Andreas Mohre8a99052006-03-28 08:59:49 +0200687 default:
688 /*
689 * Since both rqs are wrapped,
690 * start with the one that's further behind head
691 * (--> only *one* back seek required),
692 * since back seek takes more time than forward.
693 */
694 if (s1 <= s2)
Jens Axboe5e705372006-07-13 12:39:25 +0200695 return rq1;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700696 else
Jens Axboe5e705372006-07-13 12:39:25 +0200697 return rq2;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700698 }
699}
700
Jens Axboe498d3aa22007-04-26 12:54:48 +0200701/*
702 * The below is leftmost cache rbtree addon
703 */
Jens Axboe08717142008-01-28 11:38:15 +0100704static struct cfq_queue *cfq_rb_first(struct cfq_rb_root *root)
Jens Axboecc09e292007-04-26 12:53:50 +0200705{
Vivek Goyal615f0252009-12-03 12:59:39 -0500706 /* Service tree is empty */
707 if (!root->count)
708 return NULL;
709
Jens Axboecc09e292007-04-26 12:53:50 +0200710 if (!root->left)
711 root->left = rb_first(&root->rb);
712
Jens Axboe08717142008-01-28 11:38:15 +0100713 if (root->left)
714 return rb_entry(root->left, struct cfq_queue, rb_node);
715
716 return NULL;
Jens Axboecc09e292007-04-26 12:53:50 +0200717}
718
Vivek Goyal1fa8f6d2009-12-03 12:59:41 -0500719static struct cfq_group *cfq_rb_first_group(struct cfq_rb_root *root)
720{
721 if (!root->left)
722 root->left = rb_first(&root->rb);
723
724 if (root->left)
725 return rb_entry_cfqg(root->left);
726
727 return NULL;
728}
729
Jens Axboea36e71f2009-04-15 12:15:11 +0200730static void rb_erase_init(struct rb_node *n, struct rb_root *root)
731{
732 rb_erase(n, root);
733 RB_CLEAR_NODE(n);
734}
735
Jens Axboecc09e292007-04-26 12:53:50 +0200736static void cfq_rb_erase(struct rb_node *n, struct cfq_rb_root *root)
737{
738 if (root->left == n)
739 root->left = NULL;
Jens Axboea36e71f2009-04-15 12:15:11 +0200740 rb_erase_init(n, &root->rb);
Corrado Zoccoloaa6f6a32009-10-26 22:44:33 +0100741 --root->count;
Jens Axboecc09e292007-04-26 12:53:50 +0200742}
743
Linus Torvalds1da177e2005-04-16 15:20:36 -0700744/*
745 * would be nice to take fifo expire time into account as well
746 */
Jens Axboe5e705372006-07-13 12:39:25 +0200747static struct request *
748cfq_find_next_rq(struct cfq_data *cfqd, struct cfq_queue *cfqq,
749 struct request *last)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700750{
Jens Axboe21183b02006-07-13 12:33:14 +0200751 struct rb_node *rbnext = rb_next(&last->rb_node);
752 struct rb_node *rbprev = rb_prev(&last->rb_node);
Jens Axboe5e705372006-07-13 12:39:25 +0200753 struct request *next = NULL, *prev = NULL;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700754
Jens Axboe21183b02006-07-13 12:33:14 +0200755 BUG_ON(RB_EMPTY_NODE(&last->rb_node));
Linus Torvalds1da177e2005-04-16 15:20:36 -0700756
757 if (rbprev)
Jens Axboe5e705372006-07-13 12:39:25 +0200758 prev = rb_entry_rq(rbprev);
Jens Axboe21183b02006-07-13 12:33:14 +0200759
Linus Torvalds1da177e2005-04-16 15:20:36 -0700760 if (rbnext)
Jens Axboe5e705372006-07-13 12:39:25 +0200761 next = rb_entry_rq(rbnext);
Jens Axboe21183b02006-07-13 12:33:14 +0200762 else {
763 rbnext = rb_first(&cfqq->sort_list);
764 if (rbnext && rbnext != &last->rb_node)
Jens Axboe5e705372006-07-13 12:39:25 +0200765 next = rb_entry_rq(rbnext);
Jens Axboe21183b02006-07-13 12:33:14 +0200766 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700767
Corrado Zoccolocf7c25c2009-11-08 17:16:46 +0100768 return cfq_choose_req(cfqd, next, prev, blk_rq_pos(last));
Linus Torvalds1da177e2005-04-16 15:20:36 -0700769}
770
Jens Axboed9e76202007-04-20 14:27:50 +0200771static unsigned long cfq_slice_offset(struct cfq_data *cfqd,
772 struct cfq_queue *cfqq)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700773{
Jens Axboed9e76202007-04-20 14:27:50 +0200774 /*
775 * just an approximation, should be ok.
776 */
Vivek Goyalcdb16e82009-12-03 12:59:38 -0500777 return (cfqq->cfqg->nr_cfqq - 1) * (cfq_prio_slice(cfqd, 1, 0) -
Jens Axboe464191c2009-11-30 09:38:13 +0100778 cfq_prio_slice(cfqd, cfq_cfqq_sync(cfqq), cfqq->ioprio));
Jens Axboed9e76202007-04-20 14:27:50 +0200779}
Linus Torvalds1da177e2005-04-16 15:20:36 -0700780
Vivek Goyal1fa8f6d2009-12-03 12:59:41 -0500781static inline s64
782cfqg_key(struct cfq_rb_root *st, struct cfq_group *cfqg)
783{
784 return cfqg->vdisktime - st->min_vdisktime;
785}
786
787static void
788__cfq_group_service_tree_add(struct cfq_rb_root *st, struct cfq_group *cfqg)
789{
790 struct rb_node **node = &st->rb.rb_node;
791 struct rb_node *parent = NULL;
792 struct cfq_group *__cfqg;
793 s64 key = cfqg_key(st, cfqg);
794 int left = 1;
795
796 while (*node != NULL) {
797 parent = *node;
798 __cfqg = rb_entry_cfqg(parent);
799
800 if (key < cfqg_key(st, __cfqg))
801 node = &parent->rb_left;
802 else {
803 node = &parent->rb_right;
804 left = 0;
805 }
806 }
807
808 if (left)
809 st->left = &cfqg->rb_node;
810
811 rb_link_node(&cfqg->rb_node, parent, node);
812 rb_insert_color(&cfqg->rb_node, &st->rb);
813}
814
815static void
816cfq_group_service_tree_add(struct cfq_data *cfqd, struct cfq_group *cfqg)
817{
818 struct cfq_rb_root *st = &cfqd->grp_service_tree;
819 struct cfq_group *__cfqg;
820 struct rb_node *n;
821
822 cfqg->nr_cfqq++;
823 if (cfqg->on_st)
824 return;
825
826 /*
827 * Currently put the group at the end. Later implement something
828 * so that groups get lesser vtime based on their weights, so that
829 * if group does not loose all if it was not continously backlogged.
830 */
831 n = rb_last(&st->rb);
832 if (n) {
833 __cfqg = rb_entry_cfqg(n);
834 cfqg->vdisktime = __cfqg->vdisktime + CFQ_IDLE_DELAY;
835 } else
836 cfqg->vdisktime = st->min_vdisktime;
837
838 __cfq_group_service_tree_add(st, cfqg);
839 cfqg->on_st = true;
Vivek Goyal58ff82f2009-12-03 12:59:44 -0500840 st->total_weight += cfqg->weight;
Vivek Goyal1fa8f6d2009-12-03 12:59:41 -0500841}
842
843static void
844cfq_group_service_tree_del(struct cfq_data *cfqd, struct cfq_group *cfqg)
845{
846 struct cfq_rb_root *st = &cfqd->grp_service_tree;
847
Vivek Goyal25bc6b02009-12-03 12:59:43 -0500848 if (st->active == &cfqg->rb_node)
849 st->active = NULL;
850
Vivek Goyal1fa8f6d2009-12-03 12:59:41 -0500851 BUG_ON(cfqg->nr_cfqq < 1);
852 cfqg->nr_cfqq--;
Vivek Goyal25bc6b02009-12-03 12:59:43 -0500853
Vivek Goyal1fa8f6d2009-12-03 12:59:41 -0500854 /* If there are other cfq queues under this group, don't delete it */
855 if (cfqg->nr_cfqq)
856 return;
857
Vivek Goyal2868ef72009-12-03 12:59:48 -0500858 cfq_log_cfqg(cfqd, cfqg, "del_from_rr group");
Vivek Goyal1fa8f6d2009-12-03 12:59:41 -0500859 cfqg->on_st = false;
Vivek Goyal58ff82f2009-12-03 12:59:44 -0500860 st->total_weight -= cfqg->weight;
Vivek Goyal1fa8f6d2009-12-03 12:59:41 -0500861 if (!RB_EMPTY_NODE(&cfqg->rb_node))
862 cfq_rb_erase(&cfqg->rb_node, st);
Vivek Goyaldae739e2009-12-03 12:59:45 -0500863 cfqg->saved_workload_slice = 0;
Vivek Goyal22084192009-12-03 12:59:49 -0500864 blkiocg_update_blkio_group_dequeue_stats(&cfqg->blkg, 1);
Vivek Goyaldae739e2009-12-03 12:59:45 -0500865}
866
867static inline unsigned int cfq_cfqq_slice_usage(struct cfq_queue *cfqq)
868{
Vivek Goyalf75edf22009-12-03 12:59:53 -0500869 unsigned int slice_used;
Vivek Goyaldae739e2009-12-03 12:59:45 -0500870
871 /*
872 * Queue got expired before even a single request completed or
873 * got expired immediately after first request completion.
874 */
875 if (!cfqq->slice_start || cfqq->slice_start == jiffies) {
876 /*
877 * Also charge the seek time incurred to the group, otherwise
878 * if there are mutiple queues in the group, each can dispatch
879 * a single request on seeky media and cause lots of seek time
880 * and group will never know it.
881 */
882 slice_used = max_t(unsigned, (jiffies - cfqq->dispatch_start),
883 1);
884 } else {
885 slice_used = jiffies - cfqq->slice_start;
Vivek Goyalf75edf22009-12-03 12:59:53 -0500886 if (slice_used > cfqq->allocated_slice)
887 slice_used = cfqq->allocated_slice;
Vivek Goyaldae739e2009-12-03 12:59:45 -0500888 }
889
Vivek Goyal22084192009-12-03 12:59:49 -0500890 cfq_log_cfqq(cfqq->cfqd, cfqq, "sl_used=%u sect=%lu", slice_used,
891 cfqq->nr_sectors);
Vivek Goyaldae739e2009-12-03 12:59:45 -0500892 return slice_used;
893}
894
895static void cfq_group_served(struct cfq_data *cfqd, struct cfq_group *cfqg,
896 struct cfq_queue *cfqq)
897{
898 struct cfq_rb_root *st = &cfqd->grp_service_tree;
Vivek Goyalf26bd1f2009-12-03 12:59:54 -0500899 unsigned int used_sl, charge_sl;
900 int nr_sync = cfqg->nr_cfqq - cfqg_busy_async_queues(cfqd, cfqg)
901 - cfqg->service_tree_idle.count;
Vivek Goyaldae739e2009-12-03 12:59:45 -0500902
Vivek Goyalf26bd1f2009-12-03 12:59:54 -0500903 BUG_ON(nr_sync < 0);
904 used_sl = charge_sl = cfq_cfqq_slice_usage(cfqq);
905
906 if (!cfq_cfqq_sync(cfqq) && !nr_sync)
907 charge_sl = cfqq->allocated_slice;
Vivek Goyaldae739e2009-12-03 12:59:45 -0500908
909 /* Can't update vdisktime while group is on service tree */
910 cfq_rb_erase(&cfqg->rb_node, st);
Vivek Goyalf26bd1f2009-12-03 12:59:54 -0500911 cfqg->vdisktime += cfq_scale_slice(charge_sl, cfqg);
Vivek Goyaldae739e2009-12-03 12:59:45 -0500912 __cfq_group_service_tree_add(st, cfqg);
913
914 /* This group is being expired. Save the context */
915 if (time_after(cfqd->workload_expires, jiffies)) {
916 cfqg->saved_workload_slice = cfqd->workload_expires
917 - jiffies;
918 cfqg->saved_workload = cfqd->serving_type;
919 cfqg->saved_serving_prio = cfqd->serving_prio;
920 } else
921 cfqg->saved_workload_slice = 0;
Vivek Goyal2868ef72009-12-03 12:59:48 -0500922
923 cfq_log_cfqg(cfqd, cfqg, "served: vt=%llu min_vt=%llu", cfqg->vdisktime,
924 st->min_vdisktime);
Vivek Goyal22084192009-12-03 12:59:49 -0500925 blkiocg_update_blkio_group_stats(&cfqg->blkg, used_sl,
926 cfqq->nr_sectors);
Vivek Goyal1fa8f6d2009-12-03 12:59:41 -0500927}
928
Vivek Goyal25fb5162009-12-03 12:59:46 -0500929#ifdef CONFIG_CFQ_GROUP_IOSCHED
930static inline struct cfq_group *cfqg_of_blkg(struct blkio_group *blkg)
931{
932 if (blkg)
933 return container_of(blkg, struct cfq_group, blkg);
934 return NULL;
935}
936
Vivek Goyalf8d461d2009-12-03 12:59:52 -0500937void
938cfq_update_blkio_group_weight(struct blkio_group *blkg, unsigned int weight)
939{
940 cfqg_of_blkg(blkg)->weight = weight;
941}
942
Vivek Goyal25fb5162009-12-03 12:59:46 -0500943static struct cfq_group *
944cfq_find_alloc_cfqg(struct cfq_data *cfqd, struct cgroup *cgroup, int create)
945{
946 struct blkio_cgroup *blkcg = cgroup_to_blkio_cgroup(cgroup);
947 struct cfq_group *cfqg = NULL;
948 void *key = cfqd;
949 int i, j;
950 struct cfq_rb_root *st;
Vivek Goyal22084192009-12-03 12:59:49 -0500951 struct backing_dev_info *bdi = &cfqd->queue->backing_dev_info;
952 unsigned int major, minor;
Vivek Goyal25fb5162009-12-03 12:59:46 -0500953
954 /* Do we need to take this reference */
Vivek Goyal9d6a9862009-12-04 10:36:41 -0500955 if (!blkiocg_css_tryget(blkcg))
Vivek Goyal25fb5162009-12-03 12:59:46 -0500956 return NULL;;
957
958 cfqg = cfqg_of_blkg(blkiocg_lookup_group(blkcg, key));
959 if (cfqg || !create)
960 goto done;
961
962 cfqg = kzalloc_node(sizeof(*cfqg), GFP_ATOMIC, cfqd->queue->node);
963 if (!cfqg)
964 goto done;
965
966 cfqg->weight = blkcg->weight;
967 for_each_cfqg_st(cfqg, i, j, st)
968 *st = CFQ_RB_ROOT;
969 RB_CLEAR_NODE(&cfqg->rb_node);
970
Vivek Goyalb1c35762009-12-03 12:59:47 -0500971 /*
972 * Take the initial reference that will be released on destroy
973 * This can be thought of a joint reference by cgroup and
974 * elevator which will be dropped by either elevator exit
975 * or cgroup deletion path depending on who is exiting first.
976 */
977 atomic_set(&cfqg->ref, 1);
978
Vivek Goyal25fb5162009-12-03 12:59:46 -0500979 /* Add group onto cgroup list */
Vivek Goyal22084192009-12-03 12:59:49 -0500980 sscanf(dev_name(bdi->dev), "%u:%u", &major, &minor);
981 blkiocg_add_blkio_group(blkcg, &cfqg->blkg, (void *)cfqd,
982 MKDEV(major, minor));
Vivek Goyal25fb5162009-12-03 12:59:46 -0500983
984 /* Add group on cfqd list */
985 hlist_add_head(&cfqg->cfqd_node, &cfqd->cfqg_list);
986
987done:
Vivek Goyal9d6a9862009-12-04 10:36:41 -0500988 blkiocg_css_put(blkcg);
Vivek Goyal25fb5162009-12-03 12:59:46 -0500989 return cfqg;
990}
991
992/*
993 * Search for the cfq group current task belongs to. If create = 1, then also
994 * create the cfq group if it does not exist. request_queue lock must be held.
995 */
996static struct cfq_group *cfq_get_cfqg(struct cfq_data *cfqd, int create)
997{
998 struct cgroup *cgroup;
999 struct cfq_group *cfqg = NULL;
1000
1001 rcu_read_lock();
1002 cgroup = task_cgroup(current, blkio_subsys_id);
1003 cfqg = cfq_find_alloc_cfqg(cfqd, cgroup, create);
1004 if (!cfqg && create)
1005 cfqg = &cfqd->root_group;
1006 rcu_read_unlock();
1007 return cfqg;
1008}
1009
1010static void cfq_link_cfqq_cfqg(struct cfq_queue *cfqq, struct cfq_group *cfqg)
1011{
1012 /* Currently, all async queues are mapped to root group */
1013 if (!cfq_cfqq_sync(cfqq))
1014 cfqg = &cfqq->cfqd->root_group;
1015
1016 cfqq->cfqg = cfqg;
Vivek Goyalb1c35762009-12-03 12:59:47 -05001017 /* cfqq reference on cfqg */
1018 atomic_inc(&cfqq->cfqg->ref);
Vivek Goyal25fb5162009-12-03 12:59:46 -05001019}
Vivek Goyalb1c35762009-12-03 12:59:47 -05001020
1021static void cfq_put_cfqg(struct cfq_group *cfqg)
1022{
1023 struct cfq_rb_root *st;
1024 int i, j;
1025
1026 BUG_ON(atomic_read(&cfqg->ref) <= 0);
1027 if (!atomic_dec_and_test(&cfqg->ref))
1028 return;
1029 for_each_cfqg_st(cfqg, i, j, st)
1030 BUG_ON(!RB_EMPTY_ROOT(&st->rb) || st->active != NULL);
1031 kfree(cfqg);
1032}
1033
1034static void cfq_destroy_cfqg(struct cfq_data *cfqd, struct cfq_group *cfqg)
1035{
1036 /* Something wrong if we are trying to remove same group twice */
1037 BUG_ON(hlist_unhashed(&cfqg->cfqd_node));
1038
1039 hlist_del_init(&cfqg->cfqd_node);
1040
1041 /*
1042 * Put the reference taken at the time of creation so that when all
1043 * queues are gone, group can be destroyed.
1044 */
1045 cfq_put_cfqg(cfqg);
1046}
1047
1048static void cfq_release_cfq_groups(struct cfq_data *cfqd)
1049{
1050 struct hlist_node *pos, *n;
1051 struct cfq_group *cfqg;
1052
1053 hlist_for_each_entry_safe(cfqg, pos, n, &cfqd->cfqg_list, cfqd_node) {
1054 /*
1055 * If cgroup removal path got to blk_group first and removed
1056 * it from cgroup list, then it will take care of destroying
1057 * cfqg also.
1058 */
1059 if (!blkiocg_del_blkio_group(&cfqg->blkg))
1060 cfq_destroy_cfqg(cfqd, cfqg);
1061 }
1062}
1063
1064/*
1065 * Blk cgroup controller notification saying that blkio_group object is being
1066 * delinked as associated cgroup object is going away. That also means that
1067 * no new IO will come in this group. So get rid of this group as soon as
1068 * any pending IO in the group is finished.
1069 *
1070 * This function is called under rcu_read_lock(). key is the rcu protected
1071 * pointer. That means "key" is a valid cfq_data pointer as long as we are rcu
1072 * read lock.
1073 *
1074 * "key" was fetched from blkio_group under blkio_cgroup->lock. That means
1075 * it should not be NULL as even if elevator was exiting, cgroup deltion
1076 * path got to it first.
1077 */
1078void cfq_unlink_blkio_group(void *key, struct blkio_group *blkg)
1079{
1080 unsigned long flags;
1081 struct cfq_data *cfqd = key;
1082
1083 spin_lock_irqsave(cfqd->queue->queue_lock, flags);
1084 cfq_destroy_cfqg(cfqd, cfqg_of_blkg(blkg));
1085 spin_unlock_irqrestore(cfqd->queue->queue_lock, flags);
1086}
1087
Vivek Goyal25fb5162009-12-03 12:59:46 -05001088#else /* GROUP_IOSCHED */
1089static struct cfq_group *cfq_get_cfqg(struct cfq_data *cfqd, int create)
1090{
1091 return &cfqd->root_group;
1092}
1093static inline void
1094cfq_link_cfqq_cfqg(struct cfq_queue *cfqq, struct cfq_group *cfqg) {
1095 cfqq->cfqg = cfqg;
1096}
1097
Vivek Goyalb1c35762009-12-03 12:59:47 -05001098static void cfq_release_cfq_groups(struct cfq_data *cfqd) {}
1099static inline void cfq_put_cfqg(struct cfq_group *cfqg) {}
1100
Vivek Goyal25fb5162009-12-03 12:59:46 -05001101#endif /* GROUP_IOSCHED */
1102
Jens Axboe498d3aa22007-04-26 12:54:48 +02001103/*
Corrado Zoccoloc0324a02009-10-27 19:16:03 +01001104 * The cfqd->service_trees holds all pending cfq_queue's that have
Jens Axboe498d3aa22007-04-26 12:54:48 +02001105 * requests waiting to be processed. It is sorted in the order that
1106 * we will service the queues.
1107 */
Jens Axboea36e71f2009-04-15 12:15:11 +02001108static void cfq_service_tree_add(struct cfq_data *cfqd, struct cfq_queue *cfqq,
Jens Axboea6151c32009-10-07 20:02:57 +02001109 bool add_front)
Jens Axboed9e76202007-04-20 14:27:50 +02001110{
Jens Axboe08717142008-01-28 11:38:15 +01001111 struct rb_node **p, *parent;
1112 struct cfq_queue *__cfqq;
Jens Axboed9e76202007-04-20 14:27:50 +02001113 unsigned long rb_key;
Corrado Zoccoloc0324a02009-10-27 19:16:03 +01001114 struct cfq_rb_root *service_tree;
Jens Axboe498d3aa22007-04-26 12:54:48 +02001115 int left;
Vivek Goyaldae739e2009-12-03 12:59:45 -05001116 int new_cfqq = 1;
Vivek Goyalae30c282009-12-03 12:59:55 -05001117 int group_changed = 0;
1118
1119#ifdef CONFIG_CFQ_GROUP_IOSCHED
1120 if (!cfqd->cfq_group_isolation
1121 && cfqq_type(cfqq) == SYNC_NOIDLE_WORKLOAD
1122 && cfqq->cfqg && cfqq->cfqg != &cfqd->root_group) {
1123 /* Move this cfq to root group */
1124 cfq_log_cfqq(cfqd, cfqq, "moving to root group");
1125 if (!RB_EMPTY_NODE(&cfqq->rb_node))
1126 cfq_group_service_tree_del(cfqd, cfqq->cfqg);
1127 cfqq->orig_cfqg = cfqq->cfqg;
1128 cfqq->cfqg = &cfqd->root_group;
1129 atomic_inc(&cfqd->root_group.ref);
1130 group_changed = 1;
1131 } else if (!cfqd->cfq_group_isolation
1132 && cfqq_type(cfqq) == SYNC_WORKLOAD && cfqq->orig_cfqg) {
1133 /* cfqq is sequential now needs to go to its original group */
1134 BUG_ON(cfqq->cfqg != &cfqd->root_group);
1135 if (!RB_EMPTY_NODE(&cfqq->rb_node))
1136 cfq_group_service_tree_del(cfqd, cfqq->cfqg);
1137 cfq_put_cfqg(cfqq->cfqg);
1138 cfqq->cfqg = cfqq->orig_cfqg;
1139 cfqq->orig_cfqg = NULL;
1140 group_changed = 1;
1141 cfq_log_cfqq(cfqd, cfqq, "moved to origin group");
1142 }
1143#endif
Jens Axboed9e76202007-04-20 14:27:50 +02001144
Vivek Goyalcdb16e82009-12-03 12:59:38 -05001145 service_tree = service_tree_for(cfqq->cfqg, cfqq_prio(cfqq),
Vivek Goyal65b32a52009-12-16 17:52:59 -05001146 cfqq_type(cfqq));
Jens Axboe08717142008-01-28 11:38:15 +01001147 if (cfq_class_idle(cfqq)) {
1148 rb_key = CFQ_IDLE_DELAY;
Corrado Zoccoloaa6f6a32009-10-26 22:44:33 +01001149 parent = rb_last(&service_tree->rb);
Jens Axboe08717142008-01-28 11:38:15 +01001150 if (parent && parent != &cfqq->rb_node) {
1151 __cfqq = rb_entry(parent, struct cfq_queue, rb_node);
1152 rb_key += __cfqq->rb_key;
1153 } else
1154 rb_key += jiffies;
1155 } else if (!add_front) {
Jens Axboeb9c89462009-10-06 20:53:44 +02001156 /*
1157 * Get our rb key offset. Subtract any residual slice
1158 * value carried from last service. A negative resid
1159 * count indicates slice overrun, and this should position
1160 * the next service time further away in the tree.
1161 */
Jens Axboeedd75ff2007-04-19 12:03:34 +02001162 rb_key = cfq_slice_offset(cfqd, cfqq) + jiffies;
Jens Axboeb9c89462009-10-06 20:53:44 +02001163 rb_key -= cfqq->slice_resid;
Jens Axboeedd75ff2007-04-19 12:03:34 +02001164 cfqq->slice_resid = 0;
Corrado Zoccolo48e025e2009-10-05 08:49:23 +02001165 } else {
1166 rb_key = -HZ;
Corrado Zoccoloaa6f6a32009-10-26 22:44:33 +01001167 __cfqq = cfq_rb_first(service_tree);
Corrado Zoccolo48e025e2009-10-05 08:49:23 +02001168 rb_key += __cfqq ? __cfqq->rb_key : jiffies;
1169 }
Jens Axboed9e76202007-04-20 14:27:50 +02001170
1171 if (!RB_EMPTY_NODE(&cfqq->rb_node)) {
Vivek Goyaldae739e2009-12-03 12:59:45 -05001172 new_cfqq = 0;
Jens Axboe99f96282007-02-05 11:56:25 +01001173 /*
Jens Axboed9e76202007-04-20 14:27:50 +02001174 * same position, nothing more to do
Jens Axboe99f96282007-02-05 11:56:25 +01001175 */
Corrado Zoccoloc0324a02009-10-27 19:16:03 +01001176 if (rb_key == cfqq->rb_key &&
1177 cfqq->service_tree == service_tree)
Jens Axboed9e76202007-04-20 14:27:50 +02001178 return;
Jens Axboe53b037442006-07-28 09:48:51 +02001179
Corrado Zoccoloaa6f6a32009-10-26 22:44:33 +01001180 cfq_rb_erase(&cfqq->rb_node, cfqq->service_tree);
1181 cfqq->service_tree = NULL;
Jens Axboe22e2c502005-06-27 10:55:12 +02001182 }
Jens Axboed9e76202007-04-20 14:27:50 +02001183
Jens Axboe498d3aa22007-04-26 12:54:48 +02001184 left = 1;
Jens Axboe08717142008-01-28 11:38:15 +01001185 parent = NULL;
Corrado Zoccoloaa6f6a32009-10-26 22:44:33 +01001186 cfqq->service_tree = service_tree;
1187 p = &service_tree->rb.rb_node;
Jens Axboed9e76202007-04-20 14:27:50 +02001188 while (*p) {
Jens Axboe67060e32007-04-18 20:13:32 +02001189 struct rb_node **n;
Jens Axboecc09e292007-04-26 12:53:50 +02001190
Jens Axboed9e76202007-04-20 14:27:50 +02001191 parent = *p;
1192 __cfqq = rb_entry(parent, struct cfq_queue, rb_node);
1193
Jens Axboe0c534e02007-04-18 20:01:57 +02001194 /*
Corrado Zoccoloc0324a02009-10-27 19:16:03 +01001195 * sort by key, that represents service time.
Jens Axboe0c534e02007-04-18 20:01:57 +02001196 */
Corrado Zoccoloc0324a02009-10-27 19:16:03 +01001197 if (time_before(rb_key, __cfqq->rb_key))
Jens Axboe67060e32007-04-18 20:13:32 +02001198 n = &(*p)->rb_left;
Corrado Zoccoloc0324a02009-10-27 19:16:03 +01001199 else {
Jens Axboe67060e32007-04-18 20:13:32 +02001200 n = &(*p)->rb_right;
Jens Axboecc09e292007-04-26 12:53:50 +02001201 left = 0;
Corrado Zoccoloc0324a02009-10-27 19:16:03 +01001202 }
Jens Axboe67060e32007-04-18 20:13:32 +02001203
1204 p = n;
Jens Axboed9e76202007-04-20 14:27:50 +02001205 }
1206
Jens Axboecc09e292007-04-26 12:53:50 +02001207 if (left)
Corrado Zoccoloaa6f6a32009-10-26 22:44:33 +01001208 service_tree->left = &cfqq->rb_node;
Jens Axboecc09e292007-04-26 12:53:50 +02001209
Jens Axboed9e76202007-04-20 14:27:50 +02001210 cfqq->rb_key = rb_key;
1211 rb_link_node(&cfqq->rb_node, parent, p);
Corrado Zoccoloaa6f6a32009-10-26 22:44:33 +01001212 rb_insert_color(&cfqq->rb_node, &service_tree->rb);
1213 service_tree->count++;
Vivek Goyalae30c282009-12-03 12:59:55 -05001214 if ((add_front || !new_cfqq) && !group_changed)
Vivek Goyaldae739e2009-12-03 12:59:45 -05001215 return;
Vivek Goyal1fa8f6d2009-12-03 12:59:41 -05001216 cfq_group_service_tree_add(cfqd, cfqq->cfqg);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001217}
1218
Jens Axboea36e71f2009-04-15 12:15:11 +02001219static struct cfq_queue *
Jens Axboef2d1f0a2009-04-23 12:19:38 +02001220cfq_prio_tree_lookup(struct cfq_data *cfqd, struct rb_root *root,
1221 sector_t sector, struct rb_node **ret_parent,
1222 struct rb_node ***rb_link)
Jens Axboea36e71f2009-04-15 12:15:11 +02001223{
Jens Axboea36e71f2009-04-15 12:15:11 +02001224 struct rb_node **p, *parent;
1225 struct cfq_queue *cfqq = NULL;
1226
1227 parent = NULL;
1228 p = &root->rb_node;
1229 while (*p) {
1230 struct rb_node **n;
1231
1232 parent = *p;
1233 cfqq = rb_entry(parent, struct cfq_queue, p_node);
1234
1235 /*
1236 * Sort strictly based on sector. Smallest to the left,
1237 * largest to the right.
1238 */
Tejun Heo2e46e8b2009-05-07 22:24:41 +09001239 if (sector > blk_rq_pos(cfqq->next_rq))
Jens Axboea36e71f2009-04-15 12:15:11 +02001240 n = &(*p)->rb_right;
Tejun Heo2e46e8b2009-05-07 22:24:41 +09001241 else if (sector < blk_rq_pos(cfqq->next_rq))
Jens Axboea36e71f2009-04-15 12:15:11 +02001242 n = &(*p)->rb_left;
1243 else
1244 break;
1245 p = n;
Jens Axboe3ac6c9f2009-04-23 12:14:56 +02001246 cfqq = NULL;
Jens Axboea36e71f2009-04-15 12:15:11 +02001247 }
1248
1249 *ret_parent = parent;
1250 if (rb_link)
1251 *rb_link = p;
Jens Axboe3ac6c9f2009-04-23 12:14:56 +02001252 return cfqq;
Jens Axboea36e71f2009-04-15 12:15:11 +02001253}
1254
1255static void cfq_prio_tree_add(struct cfq_data *cfqd, struct cfq_queue *cfqq)
1256{
Jens Axboea36e71f2009-04-15 12:15:11 +02001257 struct rb_node **p, *parent;
1258 struct cfq_queue *__cfqq;
1259
Jens Axboef2d1f0a2009-04-23 12:19:38 +02001260 if (cfqq->p_root) {
1261 rb_erase(&cfqq->p_node, cfqq->p_root);
1262 cfqq->p_root = NULL;
1263 }
Jens Axboea36e71f2009-04-15 12:15:11 +02001264
1265 if (cfq_class_idle(cfqq))
1266 return;
1267 if (!cfqq->next_rq)
1268 return;
1269
Jens Axboef2d1f0a2009-04-23 12:19:38 +02001270 cfqq->p_root = &cfqd->prio_trees[cfqq->org_ioprio];
Tejun Heo2e46e8b2009-05-07 22:24:41 +09001271 __cfqq = cfq_prio_tree_lookup(cfqd, cfqq->p_root,
1272 blk_rq_pos(cfqq->next_rq), &parent, &p);
Jens Axboe3ac6c9f2009-04-23 12:14:56 +02001273 if (!__cfqq) {
1274 rb_link_node(&cfqq->p_node, parent, p);
Jens Axboef2d1f0a2009-04-23 12:19:38 +02001275 rb_insert_color(&cfqq->p_node, cfqq->p_root);
1276 } else
1277 cfqq->p_root = NULL;
Jens Axboea36e71f2009-04-15 12:15:11 +02001278}
1279
Jens Axboe498d3aa22007-04-26 12:54:48 +02001280/*
1281 * Update cfqq's position in the service tree.
1282 */
Jens Axboeedd75ff2007-04-19 12:03:34 +02001283static void cfq_resort_rr_list(struct cfq_data *cfqd, struct cfq_queue *cfqq)
Jens Axboe6d048f52007-04-25 12:44:27 +02001284{
Jens Axboe6d048f52007-04-25 12:44:27 +02001285 /*
1286 * Resorting requires the cfqq to be on the RR list already.
1287 */
Jens Axboea36e71f2009-04-15 12:15:11 +02001288 if (cfq_cfqq_on_rr(cfqq)) {
Jens Axboeedd75ff2007-04-19 12:03:34 +02001289 cfq_service_tree_add(cfqd, cfqq, 0);
Jens Axboea36e71f2009-04-15 12:15:11 +02001290 cfq_prio_tree_add(cfqd, cfqq);
1291 }
Jens Axboe6d048f52007-04-25 12:44:27 +02001292}
1293
Linus Torvalds1da177e2005-04-16 15:20:36 -07001294/*
1295 * add to busy list of queues for service, trying to be fair in ordering
Jens Axboe22e2c502005-06-27 10:55:12 +02001296 * the pending list according to last request service
Linus Torvalds1da177e2005-04-16 15:20:36 -07001297 */
Jens Axboefebffd62008-01-28 13:19:43 +01001298static void cfq_add_cfqq_rr(struct cfq_data *cfqd, struct cfq_queue *cfqq)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001299{
Jens Axboe7b679132008-05-30 12:23:07 +02001300 cfq_log_cfqq(cfqd, cfqq, "add_to_rr");
Jens Axboe3b181522005-06-27 10:56:24 +02001301 BUG_ON(cfq_cfqq_on_rr(cfqq));
1302 cfq_mark_cfqq_on_rr(cfqq);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001303 cfqd->busy_queues++;
1304
Jens Axboeedd75ff2007-04-19 12:03:34 +02001305 cfq_resort_rr_list(cfqd, cfqq);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001306}
1307
Jens Axboe498d3aa22007-04-26 12:54:48 +02001308/*
1309 * Called when the cfqq no longer has requests pending, remove it from
1310 * the service tree.
1311 */
Jens Axboefebffd62008-01-28 13:19:43 +01001312static void cfq_del_cfqq_rr(struct cfq_data *cfqd, struct cfq_queue *cfqq)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001313{
Jens Axboe7b679132008-05-30 12:23:07 +02001314 cfq_log_cfqq(cfqd, cfqq, "del_from_rr");
Jens Axboe3b181522005-06-27 10:56:24 +02001315 BUG_ON(!cfq_cfqq_on_rr(cfqq));
1316 cfq_clear_cfqq_on_rr(cfqq);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001317
Corrado Zoccoloaa6f6a32009-10-26 22:44:33 +01001318 if (!RB_EMPTY_NODE(&cfqq->rb_node)) {
1319 cfq_rb_erase(&cfqq->rb_node, cfqq->service_tree);
1320 cfqq->service_tree = NULL;
1321 }
Jens Axboef2d1f0a2009-04-23 12:19:38 +02001322 if (cfqq->p_root) {
1323 rb_erase(&cfqq->p_node, cfqq->p_root);
1324 cfqq->p_root = NULL;
1325 }
Jens Axboed9e76202007-04-20 14:27:50 +02001326
Vivek Goyal1fa8f6d2009-12-03 12:59:41 -05001327 cfq_group_service_tree_del(cfqd, cfqq->cfqg);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001328 BUG_ON(!cfqd->busy_queues);
1329 cfqd->busy_queues--;
1330}
1331
1332/*
1333 * rb tree support functions
1334 */
Jens Axboefebffd62008-01-28 13:19:43 +01001335static void cfq_del_rq_rb(struct request *rq)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001336{
Jens Axboe5e705372006-07-13 12:39:25 +02001337 struct cfq_queue *cfqq = RQ_CFQQ(rq);
Jens Axboe5e705372006-07-13 12:39:25 +02001338 const int sync = rq_is_sync(rq);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001339
Jens Axboeb4878f22005-10-20 16:42:29 +02001340 BUG_ON(!cfqq->queued[sync]);
1341 cfqq->queued[sync]--;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001342
Jens Axboe5e705372006-07-13 12:39:25 +02001343 elv_rb_del(&cfqq->sort_list, rq);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001344
Vivek Goyalf04a6422009-12-03 12:59:40 -05001345 if (cfq_cfqq_on_rr(cfqq) && RB_EMPTY_ROOT(&cfqq->sort_list)) {
1346 /*
1347 * Queue will be deleted from service tree when we actually
1348 * expire it later. Right now just remove it from prio tree
1349 * as it is empty.
1350 */
1351 if (cfqq->p_root) {
1352 rb_erase(&cfqq->p_node, cfqq->p_root);
1353 cfqq->p_root = NULL;
1354 }
1355 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07001356}
1357
Jens Axboe5e705372006-07-13 12:39:25 +02001358static void cfq_add_rq_rb(struct request *rq)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001359{
Jens Axboe5e705372006-07-13 12:39:25 +02001360 struct cfq_queue *cfqq = RQ_CFQQ(rq);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001361 struct cfq_data *cfqd = cfqq->cfqd;
Jens Axboea36e71f2009-04-15 12:15:11 +02001362 struct request *__alias, *prev;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001363
Jens Axboe5380a102006-07-13 12:37:56 +02001364 cfqq->queued[rq_is_sync(rq)]++;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001365
1366 /*
1367 * looks a little odd, but the first insert might return an alias.
1368 * if that happens, put the alias on the dispatch list
1369 */
Jens Axboe21183b02006-07-13 12:33:14 +02001370 while ((__alias = elv_rb_add(&cfqq->sort_list, rq)) != NULL)
Jens Axboe5e705372006-07-13 12:39:25 +02001371 cfq_dispatch_insert(cfqd->queue, __alias);
Jens Axboe5fccbf62006-10-31 14:21:55 +01001372
1373 if (!cfq_cfqq_on_rr(cfqq))
1374 cfq_add_cfqq_rr(cfqd, cfqq);
Jens Axboe5044eed2007-04-25 11:53:48 +02001375
1376 /*
1377 * check if this request is a better next-serve candidate
1378 */
Jens Axboea36e71f2009-04-15 12:15:11 +02001379 prev = cfqq->next_rq;
Corrado Zoccolocf7c25c2009-11-08 17:16:46 +01001380 cfqq->next_rq = cfq_choose_req(cfqd, cfqq->next_rq, rq, cfqd->last_position);
Jens Axboea36e71f2009-04-15 12:15:11 +02001381
1382 /*
1383 * adjust priority tree position, if ->next_rq changes
1384 */
1385 if (prev != cfqq->next_rq)
1386 cfq_prio_tree_add(cfqd, cfqq);
1387
Jens Axboe5044eed2007-04-25 11:53:48 +02001388 BUG_ON(!cfqq->next_rq);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001389}
1390
Jens Axboefebffd62008-01-28 13:19:43 +01001391static void cfq_reposition_rq_rb(struct cfq_queue *cfqq, struct request *rq)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001392{
Jens Axboe5380a102006-07-13 12:37:56 +02001393 elv_rb_del(&cfqq->sort_list, rq);
1394 cfqq->queued[rq_is_sync(rq)]--;
Jens Axboe5e705372006-07-13 12:39:25 +02001395 cfq_add_rq_rb(rq);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001396}
1397
Jens Axboe206dc692006-03-28 13:03:44 +02001398static struct request *
1399cfq_find_rq_fmerge(struct cfq_data *cfqd, struct bio *bio)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001400{
Jens Axboe206dc692006-03-28 13:03:44 +02001401 struct task_struct *tsk = current;
Vasily Tarasov91fac312007-04-25 12:29:51 +02001402 struct cfq_io_context *cic;
Jens Axboe206dc692006-03-28 13:03:44 +02001403 struct cfq_queue *cfqq;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001404
Jens Axboe4ac845a2008-01-24 08:44:49 +01001405 cic = cfq_cic_lookup(cfqd, tsk->io_context);
Vasily Tarasov91fac312007-04-25 12:29:51 +02001406 if (!cic)
1407 return NULL;
1408
1409 cfqq = cic_to_cfqq(cic, cfq_bio_sync(bio));
Jens Axboe89850f72006-07-22 16:48:31 +02001410 if (cfqq) {
1411 sector_t sector = bio->bi_sector + bio_sectors(bio);
1412
Jens Axboe21183b02006-07-13 12:33:14 +02001413 return elv_rb_find(&cfqq->sort_list, sector);
Jens Axboe89850f72006-07-22 16:48:31 +02001414 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07001415
Linus Torvalds1da177e2005-04-16 15:20:36 -07001416 return NULL;
1417}
1418
Jens Axboe165125e2007-07-24 09:28:11 +02001419static void cfq_activate_request(struct request_queue *q, struct request *rq)
Jens Axboeb4878f22005-10-20 16:42:29 +02001420{
1421 struct cfq_data *cfqd = q->elevator->elevator_data;
1422
Jens Axboe5ad531d2009-07-03 12:57:48 +02001423 cfqd->rq_in_driver[rq_is_sync(rq)]++;
Jens Axboe7b679132008-05-30 12:23:07 +02001424 cfq_log_cfqq(cfqd, RQ_CFQQ(rq), "activate rq, drv=%d",
Jens Axboe5ad531d2009-07-03 12:57:48 +02001425 rq_in_driver(cfqd));
Jens Axboe25776e32006-06-01 10:12:26 +02001426
Tejun Heo5b936292009-05-07 22:24:38 +09001427 cfqd->last_position = blk_rq_pos(rq) + blk_rq_sectors(rq);
Jens Axboeb4878f22005-10-20 16:42:29 +02001428}
1429
Jens Axboe165125e2007-07-24 09:28:11 +02001430static void cfq_deactivate_request(struct request_queue *q, struct request *rq)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001431{
Jens Axboe22e2c502005-06-27 10:55:12 +02001432 struct cfq_data *cfqd = q->elevator->elevator_data;
Jens Axboe5ad531d2009-07-03 12:57:48 +02001433 const int sync = rq_is_sync(rq);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001434
Jens Axboe5ad531d2009-07-03 12:57:48 +02001435 WARN_ON(!cfqd->rq_in_driver[sync]);
1436 cfqd->rq_in_driver[sync]--;
Jens Axboe7b679132008-05-30 12:23:07 +02001437 cfq_log_cfqq(cfqd, RQ_CFQQ(rq), "deactivate rq, drv=%d",
Jens Axboe5ad531d2009-07-03 12:57:48 +02001438 rq_in_driver(cfqd));
Linus Torvalds1da177e2005-04-16 15:20:36 -07001439}
1440
Jens Axboeb4878f22005-10-20 16:42:29 +02001441static void cfq_remove_request(struct request *rq)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001442{
Jens Axboe5e705372006-07-13 12:39:25 +02001443 struct cfq_queue *cfqq = RQ_CFQQ(rq);
Jens Axboe21183b02006-07-13 12:33:14 +02001444
Jens Axboe5e705372006-07-13 12:39:25 +02001445 if (cfqq->next_rq == rq)
1446 cfqq->next_rq = cfq_find_next_rq(cfqq->cfqd, cfqq, rq);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001447
Jens Axboeb4878f22005-10-20 16:42:29 +02001448 list_del_init(&rq->queuelist);
Jens Axboe5e705372006-07-13 12:39:25 +02001449 cfq_del_rq_rb(rq);
Jens Axboe374f84a2006-07-23 01:42:19 +02001450
Aaron Carroll45333d52008-08-26 15:52:36 +02001451 cfqq->cfqd->rq_queued--;
Jens Axboe374f84a2006-07-23 01:42:19 +02001452 if (rq_is_meta(rq)) {
1453 WARN_ON(!cfqq->meta_pending);
1454 cfqq->meta_pending--;
1455 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07001456}
1457
Jens Axboe165125e2007-07-24 09:28:11 +02001458static int cfq_merge(struct request_queue *q, struct request **req,
1459 struct bio *bio)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001460{
1461 struct cfq_data *cfqd = q->elevator->elevator_data;
1462 struct request *__rq;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001463
Jens Axboe206dc692006-03-28 13:03:44 +02001464 __rq = cfq_find_rq_fmerge(cfqd, bio);
Jens Axboe22e2c502005-06-27 10:55:12 +02001465 if (__rq && elv_rq_merge_ok(__rq, bio)) {
Jens Axboe98170642006-07-28 09:23:08 +02001466 *req = __rq;
1467 return ELEVATOR_FRONT_MERGE;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001468 }
1469
1470 return ELEVATOR_NO_MERGE;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001471}
1472
Jens Axboe165125e2007-07-24 09:28:11 +02001473static void cfq_merged_request(struct request_queue *q, struct request *req,
Jens Axboe21183b02006-07-13 12:33:14 +02001474 int type)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001475{
Jens Axboe21183b02006-07-13 12:33:14 +02001476 if (type == ELEVATOR_FRONT_MERGE) {
Jens Axboe5e705372006-07-13 12:39:25 +02001477 struct cfq_queue *cfqq = RQ_CFQQ(req);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001478
Jens Axboe5e705372006-07-13 12:39:25 +02001479 cfq_reposition_rq_rb(cfqq, req);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001480 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07001481}
1482
1483static void
Jens Axboe165125e2007-07-24 09:28:11 +02001484cfq_merged_requests(struct request_queue *q, struct request *rq,
Linus Torvalds1da177e2005-04-16 15:20:36 -07001485 struct request *next)
1486{
Corrado Zoccolocf7c25c2009-11-08 17:16:46 +01001487 struct cfq_queue *cfqq = RQ_CFQQ(rq);
Jens Axboe22e2c502005-06-27 10:55:12 +02001488 /*
1489 * reposition in fifo if next is older than rq
1490 */
1491 if (!list_empty(&rq->queuelist) && !list_empty(&next->queuelist) &&
Jens Axboe30996f42009-10-05 11:03:39 +02001492 time_before(rq_fifo_time(next), rq_fifo_time(rq))) {
Jens Axboe22e2c502005-06-27 10:55:12 +02001493 list_move(&rq->queuelist, &next->queuelist);
Jens Axboe30996f42009-10-05 11:03:39 +02001494 rq_set_fifo_time(rq, rq_fifo_time(next));
1495 }
Jens Axboe22e2c502005-06-27 10:55:12 +02001496
Corrado Zoccolocf7c25c2009-11-08 17:16:46 +01001497 if (cfqq->next_rq == next)
1498 cfqq->next_rq = rq;
Jens Axboeb4878f22005-10-20 16:42:29 +02001499 cfq_remove_request(next);
Jens Axboe22e2c502005-06-27 10:55:12 +02001500}
1501
Jens Axboe165125e2007-07-24 09:28:11 +02001502static int cfq_allow_merge(struct request_queue *q, struct request *rq,
Jens Axboeda775262006-12-20 11:04:12 +01001503 struct bio *bio)
1504{
1505 struct cfq_data *cfqd = q->elevator->elevator_data;
Vasily Tarasov91fac312007-04-25 12:29:51 +02001506 struct cfq_io_context *cic;
Jens Axboeda775262006-12-20 11:04:12 +01001507 struct cfq_queue *cfqq;
Jens Axboeda775262006-12-20 11:04:12 +01001508
1509 /*
Jens Axboeec8acb62007-01-02 18:32:11 +01001510 * Disallow merge of a sync bio into an async request.
Jens Axboeda775262006-12-20 11:04:12 +01001511 */
Vasily Tarasov91fac312007-04-25 12:29:51 +02001512 if (cfq_bio_sync(bio) && !rq_is_sync(rq))
Jens Axboea6151c32009-10-07 20:02:57 +02001513 return false;
Jens Axboeda775262006-12-20 11:04:12 +01001514
1515 /*
Jens Axboe719d3402006-12-22 09:38:53 +01001516 * Lookup the cfqq that this bio will be queued with. Allow
1517 * merge only if rq is queued there.
Jens Axboeda775262006-12-20 11:04:12 +01001518 */
Jens Axboe4ac845a2008-01-24 08:44:49 +01001519 cic = cfq_cic_lookup(cfqd, current->io_context);
Vasily Tarasov91fac312007-04-25 12:29:51 +02001520 if (!cic)
Jens Axboea6151c32009-10-07 20:02:57 +02001521 return false;
Jens Axboe719d3402006-12-22 09:38:53 +01001522
Vasily Tarasov91fac312007-04-25 12:29:51 +02001523 cfqq = cic_to_cfqq(cic, cfq_bio_sync(bio));
Jens Axboea6151c32009-10-07 20:02:57 +02001524 return cfqq == RQ_CFQQ(rq);
Jens Axboeda775262006-12-20 11:04:12 +01001525}
1526
Jens Axboefebffd62008-01-28 13:19:43 +01001527static void __cfq_set_active_queue(struct cfq_data *cfqd,
1528 struct cfq_queue *cfqq)
Jens Axboe22e2c502005-06-27 10:55:12 +02001529{
1530 if (cfqq) {
Jens Axboe7b679132008-05-30 12:23:07 +02001531 cfq_log_cfqq(cfqd, cfqq, "set_active");
Vivek Goyaldae739e2009-12-03 12:59:45 -05001532 cfqq->slice_start = 0;
1533 cfqq->dispatch_start = jiffies;
Vivek Goyalf75edf22009-12-03 12:59:53 -05001534 cfqq->allocated_slice = 0;
Jens Axboe22e2c502005-06-27 10:55:12 +02001535 cfqq->slice_end = 0;
Jens Axboe2f5cb732009-04-07 08:51:19 +02001536 cfqq->slice_dispatch = 0;
Vivek Goyal22084192009-12-03 12:59:49 -05001537 cfqq->nr_sectors = 0;
Jens Axboe2f5cb732009-04-07 08:51:19 +02001538
Jens Axboe2f5cb732009-04-07 08:51:19 +02001539 cfq_clear_cfqq_wait_request(cfqq);
Jens Axboeb0291952009-04-07 11:38:31 +02001540 cfq_clear_cfqq_must_dispatch(cfqq);
Jens Axboe3b181522005-06-27 10:56:24 +02001541 cfq_clear_cfqq_must_alloc_slice(cfqq);
1542 cfq_clear_cfqq_fifo_expire(cfqq);
Jens Axboe44f7c162007-01-19 11:51:58 +11001543 cfq_mark_cfqq_slice_new(cfqq);
Jens Axboe2f5cb732009-04-07 08:51:19 +02001544
1545 del_timer(&cfqd->idle_slice_timer);
Jens Axboe22e2c502005-06-27 10:55:12 +02001546 }
1547
1548 cfqd->active_queue = cfqq;
1549}
1550
1551/*
Jens Axboe7b14e3b2006-02-28 09:35:11 +01001552 * current cfqq expired its slice (or was too idle), select new one
1553 */
1554static void
1555__cfq_slice_expired(struct cfq_data *cfqd, struct cfq_queue *cfqq,
Jens Axboea6151c32009-10-07 20:02:57 +02001556 bool timed_out)
Jens Axboe7b14e3b2006-02-28 09:35:11 +01001557{
Jens Axboe7b679132008-05-30 12:23:07 +02001558 cfq_log_cfqq(cfqd, cfqq, "slice expired t=%d", timed_out);
1559
Jens Axboe7b14e3b2006-02-28 09:35:11 +01001560 if (cfq_cfqq_wait_request(cfqq))
1561 del_timer(&cfqd->idle_slice_timer);
1562
Jens Axboe7b14e3b2006-02-28 09:35:11 +01001563 cfq_clear_cfqq_wait_request(cfqq);
Vivek Goyalf75edf22009-12-03 12:59:53 -05001564 cfq_clear_cfqq_wait_busy(cfqq);
Jens Axboe7b14e3b2006-02-28 09:35:11 +01001565
1566 /*
Shaohua Liae54abe2010-02-05 13:11:45 +01001567 * If this cfqq is shared between multiple processes, check to
1568 * make sure that those processes are still issuing I/Os within
1569 * the mean seek distance. If not, it may be time to break the
1570 * queues apart again.
1571 */
1572 if (cfq_cfqq_coop(cfqq) && CFQQ_SEEKY(cfqq))
1573 cfq_mark_cfqq_split_coop(cfqq);
1574
1575 /*
Jens Axboe6084cdd2007-04-23 08:25:00 +02001576 * store what was left of this slice, if the queue idled/timed out
Jens Axboe7b14e3b2006-02-28 09:35:11 +01001577 */
Jens Axboe7b679132008-05-30 12:23:07 +02001578 if (timed_out && !cfq_cfqq_slice_new(cfqq)) {
Jens Axboec5b680f2007-01-19 11:56:49 +11001579 cfqq->slice_resid = cfqq->slice_end - jiffies;
Jens Axboe7b679132008-05-30 12:23:07 +02001580 cfq_log_cfqq(cfqd, cfqq, "resid=%ld", cfqq->slice_resid);
1581 }
Jens Axboe7b14e3b2006-02-28 09:35:11 +01001582
Vivek Goyaldae739e2009-12-03 12:59:45 -05001583 cfq_group_served(cfqd, cfqq->cfqg, cfqq);
1584
Vivek Goyalf04a6422009-12-03 12:59:40 -05001585 if (cfq_cfqq_on_rr(cfqq) && RB_EMPTY_ROOT(&cfqq->sort_list))
1586 cfq_del_cfqq_rr(cfqd, cfqq);
1587
Jens Axboeedd75ff2007-04-19 12:03:34 +02001588 cfq_resort_rr_list(cfqd, cfqq);
Jens Axboe7b14e3b2006-02-28 09:35:11 +01001589
1590 if (cfqq == cfqd->active_queue)
1591 cfqd->active_queue = NULL;
1592
Vivek Goyaldae739e2009-12-03 12:59:45 -05001593 if (&cfqq->cfqg->rb_node == cfqd->grp_service_tree.active)
1594 cfqd->grp_service_tree.active = NULL;
1595
Jens Axboe7b14e3b2006-02-28 09:35:11 +01001596 if (cfqd->active_cic) {
1597 put_io_context(cfqd->active_cic->ioc);
1598 cfqd->active_cic = NULL;
1599 }
Jens Axboe7b14e3b2006-02-28 09:35:11 +01001600}
1601
Jens Axboea6151c32009-10-07 20:02:57 +02001602static inline void cfq_slice_expired(struct cfq_data *cfqd, bool timed_out)
Jens Axboe7b14e3b2006-02-28 09:35:11 +01001603{
1604 struct cfq_queue *cfqq = cfqd->active_queue;
1605
1606 if (cfqq)
Jens Axboe6084cdd2007-04-23 08:25:00 +02001607 __cfq_slice_expired(cfqd, cfqq, timed_out);
Jens Axboe7b14e3b2006-02-28 09:35:11 +01001608}
1609
Jens Axboe498d3aa22007-04-26 12:54:48 +02001610/*
1611 * Get next queue for service. Unless we have a queue preemption,
1612 * we'll simply select the first cfqq in the service tree.
1613 */
Jens Axboe6d048f52007-04-25 12:44:27 +02001614static struct cfq_queue *cfq_get_next_queue(struct cfq_data *cfqd)
Jens Axboe22e2c502005-06-27 10:55:12 +02001615{
Corrado Zoccoloc0324a02009-10-27 19:16:03 +01001616 struct cfq_rb_root *service_tree =
Vivek Goyalcdb16e82009-12-03 12:59:38 -05001617 service_tree_for(cfqd->serving_group, cfqd->serving_prio,
Vivek Goyal65b32a52009-12-16 17:52:59 -05001618 cfqd->serving_type);
Jens Axboeedd75ff2007-04-19 12:03:34 +02001619
Vivek Goyalf04a6422009-12-03 12:59:40 -05001620 if (!cfqd->rq_queued)
1621 return NULL;
1622
Vivek Goyal1fa8f6d2009-12-03 12:59:41 -05001623 /* There is nothing to dispatch */
1624 if (!service_tree)
1625 return NULL;
Corrado Zoccoloc0324a02009-10-27 19:16:03 +01001626 if (RB_EMPTY_ROOT(&service_tree->rb))
1627 return NULL;
1628 return cfq_rb_first(service_tree);
Jens Axboe6d048f52007-04-25 12:44:27 +02001629}
1630
Vivek Goyalf04a6422009-12-03 12:59:40 -05001631static struct cfq_queue *cfq_get_next_queue_forced(struct cfq_data *cfqd)
1632{
Vivek Goyal25fb5162009-12-03 12:59:46 -05001633 struct cfq_group *cfqg;
Vivek Goyalf04a6422009-12-03 12:59:40 -05001634 struct cfq_queue *cfqq;
1635 int i, j;
1636 struct cfq_rb_root *st;
1637
1638 if (!cfqd->rq_queued)
1639 return NULL;
1640
Vivek Goyal25fb5162009-12-03 12:59:46 -05001641 cfqg = cfq_get_next_cfqg(cfqd);
1642 if (!cfqg)
1643 return NULL;
1644
Vivek Goyalf04a6422009-12-03 12:59:40 -05001645 for_each_cfqg_st(cfqg, i, j, st)
1646 if ((cfqq = cfq_rb_first(st)) != NULL)
1647 return cfqq;
1648 return NULL;
1649}
1650
Jens Axboe498d3aa22007-04-26 12:54:48 +02001651/*
1652 * Get and set a new active queue for service.
1653 */
Jens Axboea36e71f2009-04-15 12:15:11 +02001654static struct cfq_queue *cfq_set_active_queue(struct cfq_data *cfqd,
1655 struct cfq_queue *cfqq)
Jens Axboe6d048f52007-04-25 12:44:27 +02001656{
Jens Axboee00ef792009-11-04 08:54:55 +01001657 if (!cfqq)
Jens Axboea36e71f2009-04-15 12:15:11 +02001658 cfqq = cfq_get_next_queue(cfqd);
Jens Axboe6d048f52007-04-25 12:44:27 +02001659
Jens Axboe22e2c502005-06-27 10:55:12 +02001660 __cfq_set_active_queue(cfqd, cfqq);
Jens Axboe3b181522005-06-27 10:56:24 +02001661 return cfqq;
Jens Axboe22e2c502005-06-27 10:55:12 +02001662}
1663
Jens Axboed9e76202007-04-20 14:27:50 +02001664static inline sector_t cfq_dist_from_last(struct cfq_data *cfqd,
1665 struct request *rq)
1666{
Tejun Heo83096eb2009-05-07 22:24:39 +09001667 if (blk_rq_pos(rq) >= cfqd->last_position)
1668 return blk_rq_pos(rq) - cfqd->last_position;
Jens Axboed9e76202007-04-20 14:27:50 +02001669 else
Tejun Heo83096eb2009-05-07 22:24:39 +09001670 return cfqd->last_position - blk_rq_pos(rq);
Jens Axboed9e76202007-04-20 14:27:50 +02001671}
1672
Jeff Moyerb2c18e12009-10-23 17:14:49 -04001673static inline int cfq_rq_close(struct cfq_data *cfqd, struct cfq_queue *cfqq,
Shaohua Li2f7a2d82009-12-28 13:18:44 +01001674 struct request *rq, bool for_preempt)
Jens Axboe6d048f52007-04-25 12:44:27 +02001675{
Jeff Moyerb2c18e12009-10-23 17:14:49 -04001676 sector_t sdist = cfqq->seek_mean;
Jens Axboecaaa5f92006-06-16 11:23:00 +02001677
Jeff Moyerb2c18e12009-10-23 17:14:49 -04001678 if (!sample_valid(cfqq->seek_samples))
1679 sdist = CFQQ_SEEK_THR;
Jens Axboe6d048f52007-04-25 12:44:27 +02001680
Shaohua Li2f7a2d82009-12-28 13:18:44 +01001681 /* if seek_mean is big, using it as close criteria is meaningless */
1682 if (sdist > CFQQ_SEEK_THR && !for_preempt)
1683 sdist = CFQQ_SEEK_THR;
1684
Jeff Moyer04dc6e72009-04-21 07:31:56 +02001685 return cfq_dist_from_last(cfqd, rq) <= sdist;
Jens Axboe6d048f52007-04-25 12:44:27 +02001686}
1687
Jens Axboea36e71f2009-04-15 12:15:11 +02001688static struct cfq_queue *cfqq_close(struct cfq_data *cfqd,
1689 struct cfq_queue *cur_cfqq)
Jens Axboe6d048f52007-04-25 12:44:27 +02001690{
Jens Axboef2d1f0a2009-04-23 12:19:38 +02001691 struct rb_root *root = &cfqd->prio_trees[cur_cfqq->org_ioprio];
Jens Axboea36e71f2009-04-15 12:15:11 +02001692 struct rb_node *parent, *node;
1693 struct cfq_queue *__cfqq;
1694 sector_t sector = cfqd->last_position;
1695
1696 if (RB_EMPTY_ROOT(root))
1697 return NULL;
1698
1699 /*
1700 * First, if we find a request starting at the end of the last
1701 * request, choose it.
1702 */
Jens Axboef2d1f0a2009-04-23 12:19:38 +02001703 __cfqq = cfq_prio_tree_lookup(cfqd, root, sector, &parent, NULL);
Jens Axboea36e71f2009-04-15 12:15:11 +02001704 if (__cfqq)
1705 return __cfqq;
1706
1707 /*
1708 * If the exact sector wasn't found, the parent of the NULL leaf
1709 * will contain the closest sector.
1710 */
1711 __cfqq = rb_entry(parent, struct cfq_queue, p_node);
Shaohua Li2f7a2d82009-12-28 13:18:44 +01001712 if (cfq_rq_close(cfqd, cur_cfqq, __cfqq->next_rq, false))
Jens Axboea36e71f2009-04-15 12:15:11 +02001713 return __cfqq;
1714
Tejun Heo2e46e8b2009-05-07 22:24:41 +09001715 if (blk_rq_pos(__cfqq->next_rq) < sector)
Jens Axboea36e71f2009-04-15 12:15:11 +02001716 node = rb_next(&__cfqq->p_node);
1717 else
1718 node = rb_prev(&__cfqq->p_node);
1719 if (!node)
1720 return NULL;
1721
1722 __cfqq = rb_entry(node, struct cfq_queue, p_node);
Shaohua Li2f7a2d82009-12-28 13:18:44 +01001723 if (cfq_rq_close(cfqd, cur_cfqq, __cfqq->next_rq, false))
Jens Axboea36e71f2009-04-15 12:15:11 +02001724 return __cfqq;
1725
1726 return NULL;
1727}
1728
1729/*
1730 * cfqd - obvious
1731 * cur_cfqq - passed in so that we don't decide that the current queue is
1732 * closely cooperating with itself.
1733 *
1734 * So, basically we're assuming that that cur_cfqq has dispatched at least
1735 * one request, and that cfqd->last_position reflects a position on the disk
1736 * associated with the I/O issued by cur_cfqq. I'm not sure this is a valid
1737 * assumption.
1738 */
1739static struct cfq_queue *cfq_close_cooperator(struct cfq_data *cfqd,
Jeff Moyerb3b6d042009-10-23 17:14:51 -04001740 struct cfq_queue *cur_cfqq)
Jens Axboea36e71f2009-04-15 12:15:11 +02001741{
1742 struct cfq_queue *cfqq;
1743
Jeff Moyere6c5bc72009-10-23 17:14:52 -04001744 if (!cfq_cfqq_sync(cur_cfqq))
1745 return NULL;
1746 if (CFQQ_SEEKY(cur_cfqq))
1747 return NULL;
1748
Jens Axboea36e71f2009-04-15 12:15:11 +02001749 /*
Gui Jianfengb9d8f4c2009-12-08 08:54:17 +01001750 * Don't search priority tree if it's the only queue in the group.
1751 */
1752 if (cur_cfqq->cfqg->nr_cfqq == 1)
1753 return NULL;
1754
1755 /*
Jens Axboed9e76202007-04-20 14:27:50 +02001756 * We should notice if some of the queues are cooperating, eg
1757 * working closely on the same area of the disk. In that case,
1758 * we can group them together and don't waste time idling.
Jens Axboe6d048f52007-04-25 12:44:27 +02001759 */
Jens Axboea36e71f2009-04-15 12:15:11 +02001760 cfqq = cfqq_close(cfqd, cur_cfqq);
1761 if (!cfqq)
1762 return NULL;
1763
Vivek Goyal8682e1f2009-12-03 12:59:50 -05001764 /* If new queue belongs to different cfq_group, don't choose it */
1765 if (cur_cfqq->cfqg != cfqq->cfqg)
1766 return NULL;
1767
Jeff Moyerdf5fe3e2009-10-23 17:14:50 -04001768 /*
1769 * It only makes sense to merge sync queues.
1770 */
1771 if (!cfq_cfqq_sync(cfqq))
1772 return NULL;
Jeff Moyere6c5bc72009-10-23 17:14:52 -04001773 if (CFQQ_SEEKY(cfqq))
1774 return NULL;
Jeff Moyerdf5fe3e2009-10-23 17:14:50 -04001775
Corrado Zoccoloc0324a02009-10-27 19:16:03 +01001776 /*
1777 * Do not merge queues of different priority classes
1778 */
1779 if (cfq_class_rt(cfqq) != cfq_class_rt(cur_cfqq))
1780 return NULL;
1781
Jens Axboea36e71f2009-04-15 12:15:11 +02001782 return cfqq;
Jens Axboe6d048f52007-04-25 12:44:27 +02001783}
1784
Corrado Zoccoloa6d44e92009-10-26 22:45:11 +01001785/*
1786 * Determine whether we should enforce idle window for this queue.
1787 */
1788
1789static bool cfq_should_idle(struct cfq_data *cfqd, struct cfq_queue *cfqq)
1790{
1791 enum wl_prio_t prio = cfqq_prio(cfqq);
Corrado Zoccolo718eee02009-10-26 22:45:29 +01001792 struct cfq_rb_root *service_tree = cfqq->service_tree;
Corrado Zoccoloa6d44e92009-10-26 22:45:11 +01001793
Vivek Goyalf04a6422009-12-03 12:59:40 -05001794 BUG_ON(!service_tree);
1795 BUG_ON(!service_tree->count);
1796
Corrado Zoccoloa6d44e92009-10-26 22:45:11 +01001797 /* We never do for idle class queues. */
1798 if (prio == IDLE_WORKLOAD)
1799 return false;
1800
1801 /* We do for queues that were marked with idle window flag. */
Shaohua Li3c764b72009-12-04 13:12:06 +01001802 if (cfq_cfqq_idle_window(cfqq) &&
1803 !(blk_queue_nonrot(cfqd->queue) && cfqd->hw_tag))
Corrado Zoccoloa6d44e92009-10-26 22:45:11 +01001804 return true;
1805
1806 /*
1807 * Otherwise, we do only if they are the last ones
1808 * in their service tree.
1809 */
Vivek Goyal1efe8fe2010-02-02 20:45:46 +01001810 return service_tree->count == 1 && cfq_cfqq_sync(cfqq);
Corrado Zoccoloa6d44e92009-10-26 22:45:11 +01001811}
1812
Jens Axboe6d048f52007-04-25 12:44:27 +02001813static void cfq_arm_slice_timer(struct cfq_data *cfqd)
Jens Axboe22e2c502005-06-27 10:55:12 +02001814{
Jens Axboe17926692007-01-19 11:59:30 +11001815 struct cfq_queue *cfqq = cfqd->active_queue;
Jens Axboe206dc692006-03-28 13:03:44 +02001816 struct cfq_io_context *cic;
Jens Axboe7b14e3b2006-02-28 09:35:11 +01001817 unsigned long sl;
1818
Jens Axboea68bbdd2008-09-24 13:03:33 +02001819 /*
Jens Axboef7d7b7a2008-09-25 11:37:50 +02001820 * SSD device without seek penalty, disable idling. But only do so
1821 * for devices that support queuing, otherwise we still have a problem
1822 * with sync vs async workloads.
Jens Axboea68bbdd2008-09-24 13:03:33 +02001823 */
Jens Axboef7d7b7a2008-09-25 11:37:50 +02001824 if (blk_queue_nonrot(cfqd->queue) && cfqd->hw_tag)
Jens Axboea68bbdd2008-09-24 13:03:33 +02001825 return;
1826
Jens Axboedd67d052006-06-21 09:36:18 +02001827 WARN_ON(!RB_EMPTY_ROOT(&cfqq->sort_list));
Jens Axboe6d048f52007-04-25 12:44:27 +02001828 WARN_ON(cfq_cfqq_slice_new(cfqq));
Jens Axboe22e2c502005-06-27 10:55:12 +02001829
1830 /*
1831 * idle is disabled, either manually or by past process history
1832 */
Corrado Zoccoloa6d44e92009-10-26 22:45:11 +01001833 if (!cfqd->cfq_slice_idle || !cfq_should_idle(cfqd, cfqq))
Jens Axboe6d048f52007-04-25 12:44:27 +02001834 return;
1835
Jens Axboe22e2c502005-06-27 10:55:12 +02001836 /*
Corrado Zoccolo8e550632009-11-26 10:02:58 +01001837 * still active requests from this queue, don't idle
Jens Axboe7b679132008-05-30 12:23:07 +02001838 */
Corrado Zoccolo8e550632009-11-26 10:02:58 +01001839 if (cfqq->dispatched)
Jens Axboe7b679132008-05-30 12:23:07 +02001840 return;
1841
1842 /*
Jens Axboe22e2c502005-06-27 10:55:12 +02001843 * task has exited, don't wait
1844 */
Jens Axboe206dc692006-03-28 13:03:44 +02001845 cic = cfqd->active_cic;
Nikanth Karthikesan66dac982007-11-27 12:47:04 +01001846 if (!cic || !atomic_read(&cic->ioc->nr_tasks))
Jens Axboe6d048f52007-04-25 12:44:27 +02001847 return;
1848
Corrado Zoccolo355b6592009-10-08 08:43:32 +02001849 /*
1850 * If our average think time is larger than the remaining time
1851 * slice, then don't idle. This avoids overrunning the allotted
1852 * time slice.
1853 */
1854 if (sample_valid(cic->ttime_samples) &&
1855 (cfqq->slice_end - jiffies < cic->ttime_mean))
1856 return;
1857
Jens Axboe3b181522005-06-27 10:56:24 +02001858 cfq_mark_cfqq_wait_request(cfqq);
Jens Axboe22e2c502005-06-27 10:55:12 +02001859
Jens Axboe6d048f52007-04-25 12:44:27 +02001860 sl = cfqd->cfq_slice_idle;
Jens Axboe206dc692006-03-28 13:03:44 +02001861
Jens Axboe7b14e3b2006-02-28 09:35:11 +01001862 mod_timer(&cfqd->idle_slice_timer, jiffies + sl);
Jens Axboe9481ffd2009-04-15 12:14:13 +02001863 cfq_log_cfqq(cfqd, cfqq, "arm_idle: %lu", sl);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001864}
1865
Jens Axboe498d3aa22007-04-26 12:54:48 +02001866/*
1867 * Move request from internal lists to the request queue dispatch list.
1868 */
Jens Axboe165125e2007-07-24 09:28:11 +02001869static void cfq_dispatch_insert(struct request_queue *q, struct request *rq)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001870{
Jens Axboe3ed9a292007-04-23 08:33:33 +02001871 struct cfq_data *cfqd = q->elevator->elevator_data;
Jens Axboe5e705372006-07-13 12:39:25 +02001872 struct cfq_queue *cfqq = RQ_CFQQ(rq);
Jens Axboe22e2c502005-06-27 10:55:12 +02001873
Jens Axboe7b679132008-05-30 12:23:07 +02001874 cfq_log_cfqq(cfqd, cfqq, "dispatch_insert");
1875
Jeff Moyer06d21882009-09-11 17:08:59 +02001876 cfqq->next_rq = cfq_find_next_rq(cfqd, cfqq, rq);
Jens Axboe5380a102006-07-13 12:37:56 +02001877 cfq_remove_request(rq);
Jens Axboe6d048f52007-04-25 12:44:27 +02001878 cfqq->dispatched++;
Jens Axboe5380a102006-07-13 12:37:56 +02001879 elv_dispatch_sort(q, rq);
Jens Axboe3ed9a292007-04-23 08:33:33 +02001880
1881 if (cfq_cfqq_sync(cfqq))
1882 cfqd->sync_flight++;
Vivek Goyal22084192009-12-03 12:59:49 -05001883 cfqq->nr_sectors += blk_rq_sectors(rq);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001884}
1885
1886/*
1887 * return expired entry, or NULL to just start from scratch in rbtree
1888 */
Jens Axboefebffd62008-01-28 13:19:43 +01001889static struct request *cfq_check_fifo(struct cfq_queue *cfqq)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001890{
Jens Axboe30996f42009-10-05 11:03:39 +02001891 struct request *rq = NULL;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001892
Jens Axboe3b181522005-06-27 10:56:24 +02001893 if (cfq_cfqq_fifo_expire(cfqq))
Linus Torvalds1da177e2005-04-16 15:20:36 -07001894 return NULL;
Jens Axboecb887412007-01-19 12:01:16 +11001895
1896 cfq_mark_cfqq_fifo_expire(cfqq);
1897
Jens Axboe89850f72006-07-22 16:48:31 +02001898 if (list_empty(&cfqq->fifo))
1899 return NULL;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001900
Jens Axboe89850f72006-07-22 16:48:31 +02001901 rq = rq_entry_fifo(cfqq->fifo.next);
Jens Axboe30996f42009-10-05 11:03:39 +02001902 if (time_before(jiffies, rq_fifo_time(rq)))
Jens Axboe7b679132008-05-30 12:23:07 +02001903 rq = NULL;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001904
Jens Axboe30996f42009-10-05 11:03:39 +02001905 cfq_log_cfqq(cfqq->cfqd, cfqq, "fifo=%p", rq);
Jens Axboe6d048f52007-04-25 12:44:27 +02001906 return rq;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001907}
1908
Jens Axboe22e2c502005-06-27 10:55:12 +02001909static inline int
1910cfq_prio_to_maxrq(struct cfq_data *cfqd, struct cfq_queue *cfqq)
1911{
1912 const int base_rq = cfqd->cfq_slice_async_rq;
1913
1914 WARN_ON(cfqq->ioprio >= IOPRIO_BE_NR);
1915
1916 return 2 * (base_rq + base_rq * (CFQ_PRIO_LISTS - 1 - cfqq->ioprio));
1917}
1918
1919/*
Jeff Moyerdf5fe3e2009-10-23 17:14:50 -04001920 * Must be called with the queue_lock held.
1921 */
1922static int cfqq_process_refs(struct cfq_queue *cfqq)
1923{
1924 int process_refs, io_refs;
1925
1926 io_refs = cfqq->allocated[READ] + cfqq->allocated[WRITE];
1927 process_refs = atomic_read(&cfqq->ref) - io_refs;
1928 BUG_ON(process_refs < 0);
1929 return process_refs;
1930}
1931
1932static void cfq_setup_merge(struct cfq_queue *cfqq, struct cfq_queue *new_cfqq)
1933{
Jeff Moyere6c5bc72009-10-23 17:14:52 -04001934 int process_refs, new_process_refs;
Jeff Moyerdf5fe3e2009-10-23 17:14:50 -04001935 struct cfq_queue *__cfqq;
1936
1937 /* Avoid a circular list and skip interim queue merges */
1938 while ((__cfqq = new_cfqq->new_cfqq)) {
1939 if (__cfqq == cfqq)
1940 return;
1941 new_cfqq = __cfqq;
1942 }
1943
1944 process_refs = cfqq_process_refs(cfqq);
1945 /*
1946 * If the process for the cfqq has gone away, there is no
1947 * sense in merging the queues.
1948 */
1949 if (process_refs == 0)
1950 return;
1951
Jeff Moyere6c5bc72009-10-23 17:14:52 -04001952 /*
1953 * Merge in the direction of the lesser amount of work.
1954 */
1955 new_process_refs = cfqq_process_refs(new_cfqq);
1956 if (new_process_refs >= process_refs) {
1957 cfqq->new_cfqq = new_cfqq;
1958 atomic_add(process_refs, &new_cfqq->ref);
1959 } else {
1960 new_cfqq->new_cfqq = cfqq;
1961 atomic_add(new_process_refs, &cfqq->ref);
1962 }
Jeff Moyerdf5fe3e2009-10-23 17:14:50 -04001963}
1964
Vivek Goyalcdb16e82009-12-03 12:59:38 -05001965static enum wl_type_t cfq_choose_wl(struct cfq_data *cfqd,
Vivek Goyal65b32a52009-12-16 17:52:59 -05001966 struct cfq_group *cfqg, enum wl_prio_t prio)
Corrado Zoccolo718eee02009-10-26 22:45:29 +01001967{
1968 struct cfq_queue *queue;
1969 int i;
1970 bool key_valid = false;
1971 unsigned long lowest_key = 0;
1972 enum wl_type_t cur_best = SYNC_NOIDLE_WORKLOAD;
1973
Vivek Goyal65b32a52009-12-16 17:52:59 -05001974 for (i = 0; i <= SYNC_WORKLOAD; ++i) {
1975 /* select the one with lowest rb_key */
1976 queue = cfq_rb_first(service_tree_for(cfqg, prio, i));
Corrado Zoccolo718eee02009-10-26 22:45:29 +01001977 if (queue &&
1978 (!key_valid || time_before(queue->rb_key, lowest_key))) {
1979 lowest_key = queue->rb_key;
1980 cur_best = i;
1981 key_valid = true;
1982 }
1983 }
1984
1985 return cur_best;
1986}
1987
Vivek Goyalcdb16e82009-12-03 12:59:38 -05001988static void choose_service_tree(struct cfq_data *cfqd, struct cfq_group *cfqg)
Corrado Zoccolo718eee02009-10-26 22:45:29 +01001989{
Corrado Zoccolo718eee02009-10-26 22:45:29 +01001990 unsigned slice;
1991 unsigned count;
Vivek Goyalcdb16e82009-12-03 12:59:38 -05001992 struct cfq_rb_root *st;
Vivek Goyal58ff82f2009-12-03 12:59:44 -05001993 unsigned group_slice;
Corrado Zoccolo718eee02009-10-26 22:45:29 +01001994
Vivek Goyal1fa8f6d2009-12-03 12:59:41 -05001995 if (!cfqg) {
1996 cfqd->serving_prio = IDLE_WORKLOAD;
1997 cfqd->workload_expires = jiffies + 1;
1998 return;
1999 }
2000
Corrado Zoccolo718eee02009-10-26 22:45:29 +01002001 /* Choose next priority. RT > BE > IDLE */
Vivek Goyal58ff82f2009-12-03 12:59:44 -05002002 if (cfq_group_busy_queues_wl(RT_WORKLOAD, cfqd, cfqg))
Corrado Zoccolo718eee02009-10-26 22:45:29 +01002003 cfqd->serving_prio = RT_WORKLOAD;
Vivek Goyal58ff82f2009-12-03 12:59:44 -05002004 else if (cfq_group_busy_queues_wl(BE_WORKLOAD, cfqd, cfqg))
Corrado Zoccolo718eee02009-10-26 22:45:29 +01002005 cfqd->serving_prio = BE_WORKLOAD;
2006 else {
2007 cfqd->serving_prio = IDLE_WORKLOAD;
2008 cfqd->workload_expires = jiffies + 1;
2009 return;
2010 }
2011
2012 /*
2013 * For RT and BE, we have to choose also the type
2014 * (SYNC, SYNC_NOIDLE, ASYNC), and to compute a workload
2015 * expiration time
2016 */
Vivek Goyal65b32a52009-12-16 17:52:59 -05002017 st = service_tree_for(cfqg, cfqd->serving_prio, cfqd->serving_type);
Vivek Goyalcdb16e82009-12-03 12:59:38 -05002018 count = st->count;
Corrado Zoccolo718eee02009-10-26 22:45:29 +01002019
2020 /*
Vivek Goyal65b32a52009-12-16 17:52:59 -05002021 * check workload expiration, and that we still have other queues ready
Corrado Zoccolo718eee02009-10-26 22:45:29 +01002022 */
Vivek Goyal65b32a52009-12-16 17:52:59 -05002023 if (count && !time_after(jiffies, cfqd->workload_expires))
Corrado Zoccolo718eee02009-10-26 22:45:29 +01002024 return;
2025
2026 /* otherwise select new workload type */
2027 cfqd->serving_type =
Vivek Goyal65b32a52009-12-16 17:52:59 -05002028 cfq_choose_wl(cfqd, cfqg, cfqd->serving_prio);
2029 st = service_tree_for(cfqg, cfqd->serving_prio, cfqd->serving_type);
Vivek Goyalcdb16e82009-12-03 12:59:38 -05002030 count = st->count;
Corrado Zoccolo718eee02009-10-26 22:45:29 +01002031
2032 /*
2033 * the workload slice is computed as a fraction of target latency
2034 * proportional to the number of queues in that workload, over
2035 * all the queues in the same priority class
2036 */
Vivek Goyal58ff82f2009-12-03 12:59:44 -05002037 group_slice = cfq_group_slice(cfqd, cfqg);
2038
2039 slice = group_slice * count /
2040 max_t(unsigned, cfqg->busy_queues_avg[cfqd->serving_prio],
2041 cfq_group_busy_queues_wl(cfqd->serving_prio, cfqd, cfqg));
Corrado Zoccolo718eee02009-10-26 22:45:29 +01002042
Vivek Goyalf26bd1f2009-12-03 12:59:54 -05002043 if (cfqd->serving_type == ASYNC_WORKLOAD) {
2044 unsigned int tmp;
2045
2046 /*
2047 * Async queues are currently system wide. Just taking
2048 * proportion of queues with-in same group will lead to higher
2049 * async ratio system wide as generally root group is going
2050 * to have higher weight. A more accurate thing would be to
2051 * calculate system wide asnc/sync ratio.
2052 */
2053 tmp = cfq_target_latency * cfqg_busy_async_queues(cfqd, cfqg);
2054 tmp = tmp/cfqd->busy_queues;
2055 slice = min_t(unsigned, slice, tmp);
2056
Corrado Zoccolo718eee02009-10-26 22:45:29 +01002057 /* async workload slice is scaled down according to
2058 * the sync/async slice ratio. */
2059 slice = slice * cfqd->cfq_slice[0] / cfqd->cfq_slice[1];
Vivek Goyalf26bd1f2009-12-03 12:59:54 -05002060 } else
Corrado Zoccolo718eee02009-10-26 22:45:29 +01002061 /* sync workload slice is at least 2 * cfq_slice_idle */
2062 slice = max(slice, 2 * cfqd->cfq_slice_idle);
2063
2064 slice = max_t(unsigned, slice, CFQ_MIN_TT);
2065 cfqd->workload_expires = jiffies + slice;
Corrado Zoccolo8e550632009-11-26 10:02:58 +01002066 cfqd->noidle_tree_requires_idle = false;
Corrado Zoccolo718eee02009-10-26 22:45:29 +01002067}
2068
Vivek Goyal1fa8f6d2009-12-03 12:59:41 -05002069static struct cfq_group *cfq_get_next_cfqg(struct cfq_data *cfqd)
2070{
2071 struct cfq_rb_root *st = &cfqd->grp_service_tree;
Vivek Goyal25bc6b02009-12-03 12:59:43 -05002072 struct cfq_group *cfqg;
Vivek Goyal1fa8f6d2009-12-03 12:59:41 -05002073
2074 if (RB_EMPTY_ROOT(&st->rb))
2075 return NULL;
Vivek Goyal25bc6b02009-12-03 12:59:43 -05002076 cfqg = cfq_rb_first_group(st);
2077 st->active = &cfqg->rb_node;
2078 update_min_vdisktime(st);
2079 return cfqg;
Vivek Goyal1fa8f6d2009-12-03 12:59:41 -05002080}
2081
Vivek Goyalcdb16e82009-12-03 12:59:38 -05002082static void cfq_choose_cfqg(struct cfq_data *cfqd)
2083{
Vivek Goyal1fa8f6d2009-12-03 12:59:41 -05002084 struct cfq_group *cfqg = cfq_get_next_cfqg(cfqd);
2085
2086 cfqd->serving_group = cfqg;
Vivek Goyaldae739e2009-12-03 12:59:45 -05002087
2088 /* Restore the workload type data */
2089 if (cfqg->saved_workload_slice) {
2090 cfqd->workload_expires = jiffies + cfqg->saved_workload_slice;
2091 cfqd->serving_type = cfqg->saved_workload;
2092 cfqd->serving_prio = cfqg->saved_serving_prio;
Gui Jianfeng66ae2912009-12-15 10:08:45 +01002093 } else
2094 cfqd->workload_expires = jiffies - 1;
2095
Vivek Goyal1fa8f6d2009-12-03 12:59:41 -05002096 choose_service_tree(cfqd, cfqg);
Vivek Goyalcdb16e82009-12-03 12:59:38 -05002097}
2098
Jeff Moyerdf5fe3e2009-10-23 17:14:50 -04002099/*
Jens Axboe498d3aa22007-04-26 12:54:48 +02002100 * Select a queue for service. If we have a current active queue,
2101 * check whether to continue servicing it, or retrieve and set a new one.
Jens Axboe22e2c502005-06-27 10:55:12 +02002102 */
Tejun Heo1b5ed5e12005-11-10 08:49:19 +01002103static struct cfq_queue *cfq_select_queue(struct cfq_data *cfqd)
Jens Axboe22e2c502005-06-27 10:55:12 +02002104{
Jens Axboea36e71f2009-04-15 12:15:11 +02002105 struct cfq_queue *cfqq, *new_cfqq = NULL;
Jens Axboe22e2c502005-06-27 10:55:12 +02002106
2107 cfqq = cfqd->active_queue;
2108 if (!cfqq)
2109 goto new_queue;
2110
Vivek Goyalf04a6422009-12-03 12:59:40 -05002111 if (!cfqd->rq_queued)
2112 return NULL;
Vivek Goyalc244bb52009-12-08 17:52:57 -05002113
2114 /*
2115 * We were waiting for group to get backlogged. Expire the queue
2116 */
2117 if (cfq_cfqq_wait_busy(cfqq) && !RB_EMPTY_ROOT(&cfqq->sort_list))
2118 goto expire;
2119
Jens Axboe22e2c502005-06-27 10:55:12 +02002120 /*
Jens Axboe6d048f52007-04-25 12:44:27 +02002121 * The active queue has run out of time, expire it and select new.
Jens Axboe22e2c502005-06-27 10:55:12 +02002122 */
Vivek Goyal7667aa02009-12-08 17:52:58 -05002123 if (cfq_slice_used(cfqq) && !cfq_cfqq_must_dispatch(cfqq)) {
2124 /*
2125 * If slice had not expired at the completion of last request
2126 * we might not have turned on wait_busy flag. Don't expire
2127 * the queue yet. Allow the group to get backlogged.
2128 *
2129 * The very fact that we have used the slice, that means we
2130 * have been idling all along on this queue and it should be
2131 * ok to wait for this request to complete.
2132 */
Vivek Goyal82bbbf22009-12-10 19:25:41 +01002133 if (cfqq->cfqg->nr_cfqq == 1 && RB_EMPTY_ROOT(&cfqq->sort_list)
2134 && cfqq->dispatched && cfq_should_idle(cfqd, cfqq)) {
2135 cfqq = NULL;
Vivek Goyal7667aa02009-12-08 17:52:58 -05002136 goto keep_queue;
Vivek Goyal82bbbf22009-12-10 19:25:41 +01002137 } else
Vivek Goyal7667aa02009-12-08 17:52:58 -05002138 goto expire;
2139 }
Jens Axboe22e2c502005-06-27 10:55:12 +02002140
2141 /*
Jens Axboe6d048f52007-04-25 12:44:27 +02002142 * The active queue has requests and isn't expired, allow it to
2143 * dispatch.
Jens Axboe22e2c502005-06-27 10:55:12 +02002144 */
Jens Axboedd67d052006-06-21 09:36:18 +02002145 if (!RB_EMPTY_ROOT(&cfqq->sort_list))
Jens Axboe22e2c502005-06-27 10:55:12 +02002146 goto keep_queue;
Jens Axboe6d048f52007-04-25 12:44:27 +02002147
2148 /*
Jens Axboea36e71f2009-04-15 12:15:11 +02002149 * If another queue has a request waiting within our mean seek
2150 * distance, let it run. The expire code will check for close
2151 * cooperators and put the close queue at the front of the service
Jeff Moyerdf5fe3e2009-10-23 17:14:50 -04002152 * tree. If possible, merge the expiring queue with the new cfqq.
Jens Axboea36e71f2009-04-15 12:15:11 +02002153 */
Jeff Moyerb3b6d042009-10-23 17:14:51 -04002154 new_cfqq = cfq_close_cooperator(cfqd, cfqq);
Jeff Moyerdf5fe3e2009-10-23 17:14:50 -04002155 if (new_cfqq) {
2156 if (!cfqq->new_cfqq)
2157 cfq_setup_merge(cfqq, new_cfqq);
Jens Axboea36e71f2009-04-15 12:15:11 +02002158 goto expire;
Jeff Moyerdf5fe3e2009-10-23 17:14:50 -04002159 }
Jens Axboea36e71f2009-04-15 12:15:11 +02002160
2161 /*
Jens Axboe6d048f52007-04-25 12:44:27 +02002162 * No requests pending. If the active queue still has requests in
2163 * flight or is idling for a new request, allow either of these
2164 * conditions to happen (or time out) before selecting a new queue.
2165 */
Jens Axboecc197472007-04-20 20:45:39 +02002166 if (timer_pending(&cfqd->idle_slice_timer) ||
Corrado Zoccoloa6d44e92009-10-26 22:45:11 +01002167 (cfqq->dispatched && cfq_should_idle(cfqd, cfqq))) {
Jens Axboecaaa5f92006-06-16 11:23:00 +02002168 cfqq = NULL;
2169 goto keep_queue;
Jens Axboe22e2c502005-06-27 10:55:12 +02002170 }
2171
Jens Axboe3b181522005-06-27 10:56:24 +02002172expire:
Jens Axboe6084cdd2007-04-23 08:25:00 +02002173 cfq_slice_expired(cfqd, 0);
Jens Axboe3b181522005-06-27 10:56:24 +02002174new_queue:
Corrado Zoccolo718eee02009-10-26 22:45:29 +01002175 /*
2176 * Current queue expired. Check if we have to switch to a new
2177 * service tree
2178 */
2179 if (!new_cfqq)
Vivek Goyalcdb16e82009-12-03 12:59:38 -05002180 cfq_choose_cfqg(cfqd);
Corrado Zoccolo718eee02009-10-26 22:45:29 +01002181
Jens Axboea36e71f2009-04-15 12:15:11 +02002182 cfqq = cfq_set_active_queue(cfqd, new_cfqq);
Jens Axboe22e2c502005-06-27 10:55:12 +02002183keep_queue:
Jens Axboe3b181522005-06-27 10:56:24 +02002184 return cfqq;
Jens Axboe22e2c502005-06-27 10:55:12 +02002185}
2186
Jens Axboefebffd62008-01-28 13:19:43 +01002187static int __cfq_forced_dispatch_cfqq(struct cfq_queue *cfqq)
Jens Axboed9e76202007-04-20 14:27:50 +02002188{
2189 int dispatched = 0;
2190
2191 while (cfqq->next_rq) {
2192 cfq_dispatch_insert(cfqq->cfqd->queue, cfqq->next_rq);
2193 dispatched++;
2194 }
2195
2196 BUG_ON(!list_empty(&cfqq->fifo));
Vivek Goyalf04a6422009-12-03 12:59:40 -05002197
2198 /* By default cfqq is not expired if it is empty. Do it explicitly */
2199 __cfq_slice_expired(cfqq->cfqd, cfqq, 0);
Jens Axboed9e76202007-04-20 14:27:50 +02002200 return dispatched;
2201}
2202
Jens Axboe498d3aa22007-04-26 12:54:48 +02002203/*
2204 * Drain our current requests. Used for barriers and when switching
2205 * io schedulers on-the-fly.
2206 */
Jens Axboed9e76202007-04-20 14:27:50 +02002207static int cfq_forced_dispatch(struct cfq_data *cfqd)
Tejun Heo1b5ed5e12005-11-10 08:49:19 +01002208{
Jens Axboe08717142008-01-28 11:38:15 +01002209 struct cfq_queue *cfqq;
Jens Axboed9e76202007-04-20 14:27:50 +02002210 int dispatched = 0;
Vivek Goyalcdb16e82009-12-03 12:59:38 -05002211
Vivek Goyalf04a6422009-12-03 12:59:40 -05002212 while ((cfqq = cfq_get_next_queue_forced(cfqd)) != NULL)
2213 dispatched += __cfq_forced_dispatch_cfqq(cfqq);
Tejun Heo1b5ed5e12005-11-10 08:49:19 +01002214
Jens Axboe6084cdd2007-04-23 08:25:00 +02002215 cfq_slice_expired(cfqd, 0);
Tejun Heo1b5ed5e12005-11-10 08:49:19 +01002216 BUG_ON(cfqd->busy_queues);
2217
Jeff Moyer69237152009-06-12 15:29:30 +02002218 cfq_log(cfqd, "forced_dispatch=%d", dispatched);
Tejun Heo1b5ed5e12005-11-10 08:49:19 +01002219 return dispatched;
2220}
2221
Jens Axboe0b182d62009-10-06 20:49:37 +02002222static bool cfq_may_dispatch(struct cfq_data *cfqd, struct cfq_queue *cfqq)
Jens Axboe2f5cb732009-04-07 08:51:19 +02002223{
Jens Axboe2f5cb732009-04-07 08:51:19 +02002224 unsigned int max_dispatch;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002225
Jens Axboe2f5cb732009-04-07 08:51:19 +02002226 /*
Jens Axboe5ad531d2009-07-03 12:57:48 +02002227 * Drain async requests before we start sync IO
2228 */
Corrado Zoccoloa6d44e92009-10-26 22:45:11 +01002229 if (cfq_should_idle(cfqd, cfqq) && cfqd->rq_in_driver[BLK_RW_ASYNC])
Jens Axboe0b182d62009-10-06 20:49:37 +02002230 return false;
Jens Axboe5ad531d2009-07-03 12:57:48 +02002231
2232 /*
Jens Axboe2f5cb732009-04-07 08:51:19 +02002233 * If this is an async queue and we have sync IO in flight, let it wait
2234 */
2235 if (cfqd->sync_flight && !cfq_cfqq_sync(cfqq))
Jens Axboe0b182d62009-10-06 20:49:37 +02002236 return false;
Jens Axboe2f5cb732009-04-07 08:51:19 +02002237
2238 max_dispatch = cfqd->cfq_quantum;
2239 if (cfq_class_idle(cfqq))
2240 max_dispatch = 1;
2241
2242 /*
2243 * Does this cfqq already have too much IO in flight?
2244 */
2245 if (cfqq->dispatched >= max_dispatch) {
2246 /*
2247 * idle queue must always only have a single IO in flight
2248 */
Jens Axboe3ed9a292007-04-23 08:33:33 +02002249 if (cfq_class_idle(cfqq))
Jens Axboe0b182d62009-10-06 20:49:37 +02002250 return false;
Jens Axboe3ed9a292007-04-23 08:33:33 +02002251
Jens Axboe2f5cb732009-04-07 08:51:19 +02002252 /*
2253 * We have other queues, don't allow more IO from this one
2254 */
2255 if (cfqd->busy_queues > 1)
Jens Axboe0b182d62009-10-06 20:49:37 +02002256 return false;
Jens Axboe9ede2092007-01-19 12:11:44 +11002257
Jens Axboe2f5cb732009-04-07 08:51:19 +02002258 /*
Shaohua Li474b18c2009-12-03 12:58:05 +01002259 * Sole queue user, no limit
Vivek Goyal365722b2009-10-03 15:21:27 +02002260 */
Shaohua Li474b18c2009-12-03 12:58:05 +01002261 max_dispatch = -1;
Jens Axboe8e296752009-10-03 16:26:03 +02002262 }
2263
2264 /*
2265 * Async queues must wait a bit before being allowed dispatch.
2266 * We also ramp up the dispatch depth gradually for async IO,
2267 * based on the last sync IO we serviced
2268 */
Jens Axboe963b72f2009-10-03 19:42:18 +02002269 if (!cfq_cfqq_sync(cfqq) && cfqd->cfq_latency) {
Corrado Zoccolo573412b2009-12-06 11:48:52 +01002270 unsigned long last_sync = jiffies - cfqd->last_delayed_sync;
Jens Axboe8e296752009-10-03 16:26:03 +02002271 unsigned int depth;
Vivek Goyal365722b2009-10-03 15:21:27 +02002272
Jens Axboe61f0c1d2009-10-03 19:46:03 +02002273 depth = last_sync / cfqd->cfq_slice[1];
Jens Axboee00c54c2009-10-04 20:36:19 +02002274 if (!depth && !cfqq->dispatched)
2275 depth = 1;
Jens Axboe8e296752009-10-03 16:26:03 +02002276 if (depth < max_dispatch)
2277 max_dispatch = depth;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002278 }
2279
Jens Axboe0b182d62009-10-06 20:49:37 +02002280 /*
2281 * If we're below the current max, allow a dispatch
2282 */
2283 return cfqq->dispatched < max_dispatch;
2284}
2285
2286/*
2287 * Dispatch a request from cfqq, moving them to the request queue
2288 * dispatch list.
2289 */
2290static bool cfq_dispatch_request(struct cfq_data *cfqd, struct cfq_queue *cfqq)
2291{
2292 struct request *rq;
2293
2294 BUG_ON(RB_EMPTY_ROOT(&cfqq->sort_list));
2295
2296 if (!cfq_may_dispatch(cfqd, cfqq))
2297 return false;
2298
2299 /*
2300 * follow expired path, else get first next available
2301 */
2302 rq = cfq_check_fifo(cfqq);
2303 if (!rq)
2304 rq = cfqq->next_rq;
2305
2306 /*
2307 * insert request into driver dispatch list
2308 */
2309 cfq_dispatch_insert(cfqd->queue, rq);
2310
2311 if (!cfqd->active_cic) {
2312 struct cfq_io_context *cic = RQ_CIC(rq);
2313
2314 atomic_long_inc(&cic->ioc->refcount);
2315 cfqd->active_cic = cic;
2316 }
2317
2318 return true;
2319}
2320
2321/*
2322 * Find the cfqq that we need to service and move a request from that to the
2323 * dispatch list
2324 */
2325static int cfq_dispatch_requests(struct request_queue *q, int force)
2326{
2327 struct cfq_data *cfqd = q->elevator->elevator_data;
2328 struct cfq_queue *cfqq;
2329
2330 if (!cfqd->busy_queues)
2331 return 0;
2332
2333 if (unlikely(force))
2334 return cfq_forced_dispatch(cfqd);
2335
2336 cfqq = cfq_select_queue(cfqd);
2337 if (!cfqq)
Jens Axboe8e296752009-10-03 16:26:03 +02002338 return 0;
2339
Jens Axboe2f5cb732009-04-07 08:51:19 +02002340 /*
Jens Axboe0b182d62009-10-06 20:49:37 +02002341 * Dispatch a request from this cfqq, if it is allowed
Jens Axboe2f5cb732009-04-07 08:51:19 +02002342 */
Jens Axboe0b182d62009-10-06 20:49:37 +02002343 if (!cfq_dispatch_request(cfqd, cfqq))
2344 return 0;
2345
Jens Axboe2f5cb732009-04-07 08:51:19 +02002346 cfqq->slice_dispatch++;
Jens Axboeb0291952009-04-07 11:38:31 +02002347 cfq_clear_cfqq_must_dispatch(cfqq);
Jens Axboe2f5cb732009-04-07 08:51:19 +02002348
2349 /*
2350 * expire an async queue immediately if it has used up its slice. idle
2351 * queue always expire after 1 dispatch round.
2352 */
2353 if (cfqd->busy_queues > 1 && ((!cfq_cfqq_sync(cfqq) &&
2354 cfqq->slice_dispatch >= cfq_prio_to_maxrq(cfqd, cfqq)) ||
2355 cfq_class_idle(cfqq))) {
2356 cfqq->slice_end = jiffies + 1;
2357 cfq_slice_expired(cfqd, 0);
2358 }
2359
Shan Weib217a902009-09-01 10:06:42 +02002360 cfq_log_cfqq(cfqd, cfqq, "dispatched a request");
Jens Axboe2f5cb732009-04-07 08:51:19 +02002361 return 1;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002362}
2363
Linus Torvalds1da177e2005-04-16 15:20:36 -07002364/*
Jens Axboe5e705372006-07-13 12:39:25 +02002365 * task holds one reference to the queue, dropped when task exits. each rq
2366 * in-flight on this queue also holds a reference, dropped when rq is freed.
Linus Torvalds1da177e2005-04-16 15:20:36 -07002367 *
Vivek Goyalb1c35762009-12-03 12:59:47 -05002368 * Each cfq queue took a reference on the parent group. Drop it now.
Linus Torvalds1da177e2005-04-16 15:20:36 -07002369 * queue lock must be held here.
2370 */
2371static void cfq_put_queue(struct cfq_queue *cfqq)
2372{
Jens Axboe22e2c502005-06-27 10:55:12 +02002373 struct cfq_data *cfqd = cfqq->cfqd;
Vivek Goyal878eadd2009-12-07 19:37:15 +01002374 struct cfq_group *cfqg, *orig_cfqg;
Jens Axboe22e2c502005-06-27 10:55:12 +02002375
2376 BUG_ON(atomic_read(&cfqq->ref) <= 0);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002377
2378 if (!atomic_dec_and_test(&cfqq->ref))
2379 return;
2380
Jens Axboe7b679132008-05-30 12:23:07 +02002381 cfq_log_cfqq(cfqd, cfqq, "put_queue");
Linus Torvalds1da177e2005-04-16 15:20:36 -07002382 BUG_ON(rb_first(&cfqq->sort_list));
Jens Axboe22e2c502005-06-27 10:55:12 +02002383 BUG_ON(cfqq->allocated[READ] + cfqq->allocated[WRITE]);
Vivek Goyalb1c35762009-12-03 12:59:47 -05002384 cfqg = cfqq->cfqg;
Vivek Goyal878eadd2009-12-07 19:37:15 +01002385 orig_cfqg = cfqq->orig_cfqg;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002386
Jens Axboe28f95cbc2007-01-19 12:09:53 +11002387 if (unlikely(cfqd->active_queue == cfqq)) {
Jens Axboe6084cdd2007-04-23 08:25:00 +02002388 __cfq_slice_expired(cfqd, cfqq, 0);
Jens Axboe23e018a2009-10-05 08:52:35 +02002389 cfq_schedule_dispatch(cfqd);
Jens Axboe28f95cbc2007-01-19 12:09:53 +11002390 }
Jens Axboe22e2c502005-06-27 10:55:12 +02002391
Vivek Goyalf04a6422009-12-03 12:59:40 -05002392 BUG_ON(cfq_cfqq_on_rr(cfqq));
Linus Torvalds1da177e2005-04-16 15:20:36 -07002393 kmem_cache_free(cfq_pool, cfqq);
Vivek Goyalb1c35762009-12-03 12:59:47 -05002394 cfq_put_cfqg(cfqg);
Vivek Goyal878eadd2009-12-07 19:37:15 +01002395 if (orig_cfqg)
2396 cfq_put_cfqg(orig_cfqg);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002397}
2398
Jens Axboed6de8be2008-05-28 14:46:59 +02002399/*
2400 * Must always be called with the rcu_read_lock() held
2401 */
Jens Axboe07416d22008-05-07 09:17:12 +02002402static void
2403__call_for_each_cic(struct io_context *ioc,
2404 void (*func)(struct io_context *, struct cfq_io_context *))
2405{
2406 struct cfq_io_context *cic;
2407 struct hlist_node *n;
2408
2409 hlist_for_each_entry_rcu(cic, n, &ioc->cic_list, cic_list)
2410 func(ioc, cic);
2411}
2412
Jens Axboe4ac845a2008-01-24 08:44:49 +01002413/*
Fabio Checconi34e6bbf2008-04-02 14:31:02 +02002414 * Call func for each cic attached to this ioc.
Jens Axboe4ac845a2008-01-24 08:44:49 +01002415 */
Fabio Checconi34e6bbf2008-04-02 14:31:02 +02002416static void
Jens Axboe4ac845a2008-01-24 08:44:49 +01002417call_for_each_cic(struct io_context *ioc,
2418 void (*func)(struct io_context *, struct cfq_io_context *))
2419{
Jens Axboe4ac845a2008-01-24 08:44:49 +01002420 rcu_read_lock();
Jens Axboe07416d22008-05-07 09:17:12 +02002421 __call_for_each_cic(ioc, func);
Jens Axboe4ac845a2008-01-24 08:44:49 +01002422 rcu_read_unlock();
Fabio Checconi34e6bbf2008-04-02 14:31:02 +02002423}
Jens Axboe4ac845a2008-01-24 08:44:49 +01002424
Fabio Checconi34e6bbf2008-04-02 14:31:02 +02002425static void cfq_cic_free_rcu(struct rcu_head *head)
2426{
2427 struct cfq_io_context *cic;
2428
2429 cic = container_of(head, struct cfq_io_context, rcu_head);
2430
2431 kmem_cache_free(cfq_ioc_pool, cic);
Tejun Heo245b2e72009-06-24 15:13:48 +09002432 elv_ioc_count_dec(cfq_ioc_count);
Fabio Checconi34e6bbf2008-04-02 14:31:02 +02002433
Jens Axboe9a11b4e2008-05-29 09:32:08 +02002434 if (ioc_gone) {
2435 /*
2436 * CFQ scheduler is exiting, grab exit lock and check
2437 * the pending io context count. If it hits zero,
2438 * complete ioc_gone and set it back to NULL
2439 */
2440 spin_lock(&ioc_gone_lock);
Tejun Heo245b2e72009-06-24 15:13:48 +09002441 if (ioc_gone && !elv_ioc_count_read(cfq_ioc_count)) {
Jens Axboe9a11b4e2008-05-29 09:32:08 +02002442 complete(ioc_gone);
2443 ioc_gone = NULL;
2444 }
2445 spin_unlock(&ioc_gone_lock);
2446 }
Fabio Checconi34e6bbf2008-04-02 14:31:02 +02002447}
2448
2449static void cfq_cic_free(struct cfq_io_context *cic)
2450{
2451 call_rcu(&cic->rcu_head, cfq_cic_free_rcu);
Jens Axboe4ac845a2008-01-24 08:44:49 +01002452}
2453
2454static void cic_free_func(struct io_context *ioc, struct cfq_io_context *cic)
2455{
2456 unsigned long flags;
2457
2458 BUG_ON(!cic->dead_key);
2459
2460 spin_lock_irqsave(&ioc->lock, flags);
2461 radix_tree_delete(&ioc->radix_root, cic->dead_key);
Jens Axboeffc4e752008-02-19 10:02:29 +01002462 hlist_del_rcu(&cic->cic_list);
Jens Axboe4ac845a2008-01-24 08:44:49 +01002463 spin_unlock_irqrestore(&ioc->lock, flags);
2464
Fabio Checconi34e6bbf2008-04-02 14:31:02 +02002465 cfq_cic_free(cic);
Jens Axboe4ac845a2008-01-24 08:44:49 +01002466}
2467
Jens Axboed6de8be2008-05-28 14:46:59 +02002468/*
2469 * Must be called with rcu_read_lock() held or preemption otherwise disabled.
2470 * Only two callers of this - ->dtor() which is called with the rcu_read_lock(),
2471 * and ->trim() which is called with the task lock held
2472 */
Jens Axboee2d74ac2006-03-28 08:59:01 +02002473static void cfq_free_io_context(struct io_context *ioc)
Linus Torvalds1da177e2005-04-16 15:20:36 -07002474{
Jens Axboe4ac845a2008-01-24 08:44:49 +01002475 /*
Fabio Checconi34e6bbf2008-04-02 14:31:02 +02002476 * ioc->refcount is zero here, or we are called from elv_unregister(),
2477 * so no more cic's are allowed to be linked into this ioc. So it
2478 * should be ok to iterate over the known list, we will see all cic's
2479 * since no new ones are added.
Jens Axboe4ac845a2008-01-24 08:44:49 +01002480 */
Jens Axboe07416d22008-05-07 09:17:12 +02002481 __call_for_each_cic(ioc, cic_free_func);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002482}
2483
Jens Axboe89850f72006-07-22 16:48:31 +02002484static void cfq_exit_cfqq(struct cfq_data *cfqd, struct cfq_queue *cfqq)
2485{
Jeff Moyerdf5fe3e2009-10-23 17:14:50 -04002486 struct cfq_queue *__cfqq, *next;
2487
Jens Axboe28f95cbc2007-01-19 12:09:53 +11002488 if (unlikely(cfqq == cfqd->active_queue)) {
Jens Axboe6084cdd2007-04-23 08:25:00 +02002489 __cfq_slice_expired(cfqd, cfqq, 0);
Jens Axboe23e018a2009-10-05 08:52:35 +02002490 cfq_schedule_dispatch(cfqd);
Jens Axboe28f95cbc2007-01-19 12:09:53 +11002491 }
Jens Axboe89850f72006-07-22 16:48:31 +02002492
Jeff Moyerdf5fe3e2009-10-23 17:14:50 -04002493 /*
2494 * If this queue was scheduled to merge with another queue, be
2495 * sure to drop the reference taken on that queue (and others in
2496 * the merge chain). See cfq_setup_merge and cfq_merge_cfqqs.
2497 */
2498 __cfqq = cfqq->new_cfqq;
2499 while (__cfqq) {
2500 if (__cfqq == cfqq) {
2501 WARN(1, "cfqq->new_cfqq loop detected\n");
2502 break;
2503 }
2504 next = __cfqq->new_cfqq;
2505 cfq_put_queue(__cfqq);
2506 __cfqq = next;
2507 }
2508
Jens Axboe89850f72006-07-22 16:48:31 +02002509 cfq_put_queue(cfqq);
2510}
2511
2512static void __cfq_exit_single_io_context(struct cfq_data *cfqd,
2513 struct cfq_io_context *cic)
2514{
Fabio Checconi4faa3c82008-04-10 08:28:01 +02002515 struct io_context *ioc = cic->ioc;
2516
Jens Axboefc463792006-08-29 09:05:44 +02002517 list_del_init(&cic->queue_list);
Jens Axboe4ac845a2008-01-24 08:44:49 +01002518
2519 /*
2520 * Make sure key == NULL is seen for dead queues
2521 */
Jens Axboefc463792006-08-29 09:05:44 +02002522 smp_wmb();
Jens Axboe4ac845a2008-01-24 08:44:49 +01002523 cic->dead_key = (unsigned long) cic->key;
Jens Axboefc463792006-08-29 09:05:44 +02002524 cic->key = NULL;
2525
Fabio Checconi4faa3c82008-04-10 08:28:01 +02002526 if (ioc->ioc_data == cic)
2527 rcu_assign_pointer(ioc->ioc_data, NULL);
2528
Jens Axboeff6657c2009-04-08 10:58:57 +02002529 if (cic->cfqq[BLK_RW_ASYNC]) {
2530 cfq_exit_cfqq(cfqd, cic->cfqq[BLK_RW_ASYNC]);
2531 cic->cfqq[BLK_RW_ASYNC] = NULL;
Jens Axboe89850f72006-07-22 16:48:31 +02002532 }
2533
Jens Axboeff6657c2009-04-08 10:58:57 +02002534 if (cic->cfqq[BLK_RW_SYNC]) {
2535 cfq_exit_cfqq(cfqd, cic->cfqq[BLK_RW_SYNC]);
2536 cic->cfqq[BLK_RW_SYNC] = NULL;
Jens Axboe89850f72006-07-22 16:48:31 +02002537 }
Jens Axboe89850f72006-07-22 16:48:31 +02002538}
2539
Jens Axboe4ac845a2008-01-24 08:44:49 +01002540static void cfq_exit_single_io_context(struct io_context *ioc,
2541 struct cfq_io_context *cic)
Jens Axboe22e2c502005-06-27 10:55:12 +02002542{
Al Viro478a82b2006-03-18 13:25:24 -05002543 struct cfq_data *cfqd = cic->key;
Jens Axboe22e2c502005-06-27 10:55:12 +02002544
Jens Axboe89850f72006-07-22 16:48:31 +02002545 if (cfqd) {
Jens Axboe165125e2007-07-24 09:28:11 +02002546 struct request_queue *q = cfqd->queue;
Jens Axboe4ac845a2008-01-24 08:44:49 +01002547 unsigned long flags;
Jens Axboe22e2c502005-06-27 10:55:12 +02002548
Jens Axboe4ac845a2008-01-24 08:44:49 +01002549 spin_lock_irqsave(q->queue_lock, flags);
Jens Axboe62c1fe92008-12-15 21:19:25 +01002550
2551 /*
2552 * Ensure we get a fresh copy of the ->key to prevent
2553 * race between exiting task and queue
2554 */
2555 smp_read_barrier_depends();
2556 if (cic->key)
2557 __cfq_exit_single_io_context(cfqd, cic);
2558
Jens Axboe4ac845a2008-01-24 08:44:49 +01002559 spin_unlock_irqrestore(q->queue_lock, flags);
Al Viro12a05732006-03-18 13:38:01 -05002560 }
Jens Axboe22e2c502005-06-27 10:55:12 +02002561}
2562
Jens Axboe498d3aa22007-04-26 12:54:48 +02002563/*
2564 * The process that ioc belongs to has exited, we need to clean up
2565 * and put the internal structures we have that belongs to that process.
2566 */
Jens Axboee2d74ac2006-03-28 08:59:01 +02002567static void cfq_exit_io_context(struct io_context *ioc)
Linus Torvalds1da177e2005-04-16 15:20:36 -07002568{
Jens Axboe4ac845a2008-01-24 08:44:49 +01002569 call_for_each_cic(ioc, cfq_exit_single_io_context);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002570}
2571
Jens Axboe22e2c502005-06-27 10:55:12 +02002572static struct cfq_io_context *
Al Viro8267e262005-10-21 03:20:53 -04002573cfq_alloc_io_context(struct cfq_data *cfqd, gfp_t gfp_mask)
Linus Torvalds1da177e2005-04-16 15:20:36 -07002574{
Jens Axboeb5deef92006-07-19 23:39:40 +02002575 struct cfq_io_context *cic;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002576
Christoph Lameter94f60302007-07-17 04:03:29 -07002577 cic = kmem_cache_alloc_node(cfq_ioc_pool, gfp_mask | __GFP_ZERO,
2578 cfqd->queue->node);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002579 if (cic) {
Jens Axboe22e2c502005-06-27 10:55:12 +02002580 cic->last_end_request = jiffies;
Jens Axboe553698f2006-06-14 19:11:57 +02002581 INIT_LIST_HEAD(&cic->queue_list);
Jens Axboeffc4e752008-02-19 10:02:29 +01002582 INIT_HLIST_NODE(&cic->cic_list);
Jens Axboe22e2c502005-06-27 10:55:12 +02002583 cic->dtor = cfq_free_io_context;
2584 cic->exit = cfq_exit_io_context;
Tejun Heo245b2e72009-06-24 15:13:48 +09002585 elv_ioc_count_inc(cfq_ioc_count);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002586 }
2587
2588 return cic;
2589}
2590
Jens Axboefd0928d2008-01-24 08:52:45 +01002591static void cfq_init_prio_data(struct cfq_queue *cfqq, struct io_context *ioc)
Jens Axboe22e2c502005-06-27 10:55:12 +02002592{
2593 struct task_struct *tsk = current;
2594 int ioprio_class;
2595
Jens Axboe3b181522005-06-27 10:56:24 +02002596 if (!cfq_cfqq_prio_changed(cfqq))
Jens Axboe22e2c502005-06-27 10:55:12 +02002597 return;
2598
Jens Axboefd0928d2008-01-24 08:52:45 +01002599 ioprio_class = IOPRIO_PRIO_CLASS(ioc->ioprio);
Jens Axboe22e2c502005-06-27 10:55:12 +02002600 switch (ioprio_class) {
Jens Axboefe094d92008-01-31 13:08:54 +01002601 default:
2602 printk(KERN_ERR "cfq: bad prio %x\n", ioprio_class);
2603 case IOPRIO_CLASS_NONE:
2604 /*
Jens Axboe6d63c272008-05-07 09:51:23 +02002605 * no prio set, inherit CPU scheduling settings
Jens Axboefe094d92008-01-31 13:08:54 +01002606 */
2607 cfqq->ioprio = task_nice_ioprio(tsk);
Jens Axboe6d63c272008-05-07 09:51:23 +02002608 cfqq->ioprio_class = task_nice_ioclass(tsk);
Jens Axboefe094d92008-01-31 13:08:54 +01002609 break;
2610 case IOPRIO_CLASS_RT:
2611 cfqq->ioprio = task_ioprio(ioc);
2612 cfqq->ioprio_class = IOPRIO_CLASS_RT;
2613 break;
2614 case IOPRIO_CLASS_BE:
2615 cfqq->ioprio = task_ioprio(ioc);
2616 cfqq->ioprio_class = IOPRIO_CLASS_BE;
2617 break;
2618 case IOPRIO_CLASS_IDLE:
2619 cfqq->ioprio_class = IOPRIO_CLASS_IDLE;
2620 cfqq->ioprio = 7;
2621 cfq_clear_cfqq_idle_window(cfqq);
2622 break;
Jens Axboe22e2c502005-06-27 10:55:12 +02002623 }
2624
2625 /*
2626 * keep track of original prio settings in case we have to temporarily
2627 * elevate the priority of this queue
2628 */
2629 cfqq->org_ioprio = cfqq->ioprio;
2630 cfqq->org_ioprio_class = cfqq->ioprio_class;
Jens Axboe3b181522005-06-27 10:56:24 +02002631 cfq_clear_cfqq_prio_changed(cfqq);
Jens Axboe22e2c502005-06-27 10:55:12 +02002632}
2633
Jens Axboefebffd62008-01-28 13:19:43 +01002634static void changed_ioprio(struct io_context *ioc, struct cfq_io_context *cic)
Jens Axboe22e2c502005-06-27 10:55:12 +02002635{
Al Viro478a82b2006-03-18 13:25:24 -05002636 struct cfq_data *cfqd = cic->key;
2637 struct cfq_queue *cfqq;
Jens Axboec1b707d2006-10-30 19:54:23 +01002638 unsigned long flags;
Jens Axboe35e60772006-06-14 09:10:45 +02002639
Jens Axboecaaa5f92006-06-16 11:23:00 +02002640 if (unlikely(!cfqd))
2641 return;
2642
Jens Axboec1b707d2006-10-30 19:54:23 +01002643 spin_lock_irqsave(cfqd->queue->queue_lock, flags);
Jens Axboecaaa5f92006-06-16 11:23:00 +02002644
Jens Axboeff6657c2009-04-08 10:58:57 +02002645 cfqq = cic->cfqq[BLK_RW_ASYNC];
Jens Axboecaaa5f92006-06-16 11:23:00 +02002646 if (cfqq) {
2647 struct cfq_queue *new_cfqq;
Jens Axboeff6657c2009-04-08 10:58:57 +02002648 new_cfqq = cfq_get_queue(cfqd, BLK_RW_ASYNC, cic->ioc,
2649 GFP_ATOMIC);
Jens Axboecaaa5f92006-06-16 11:23:00 +02002650 if (new_cfqq) {
Jens Axboeff6657c2009-04-08 10:58:57 +02002651 cic->cfqq[BLK_RW_ASYNC] = new_cfqq;
Jens Axboecaaa5f92006-06-16 11:23:00 +02002652 cfq_put_queue(cfqq);
2653 }
Jens Axboe22e2c502005-06-27 10:55:12 +02002654 }
Jens Axboecaaa5f92006-06-16 11:23:00 +02002655
Jens Axboeff6657c2009-04-08 10:58:57 +02002656 cfqq = cic->cfqq[BLK_RW_SYNC];
Jens Axboecaaa5f92006-06-16 11:23:00 +02002657 if (cfqq)
2658 cfq_mark_cfqq_prio_changed(cfqq);
2659
Jens Axboec1b707d2006-10-30 19:54:23 +01002660 spin_unlock_irqrestore(cfqd->queue->queue_lock, flags);
Jens Axboe22e2c502005-06-27 10:55:12 +02002661}
2662
Jens Axboefc463792006-08-29 09:05:44 +02002663static void cfq_ioc_set_ioprio(struct io_context *ioc)
Linus Torvalds1da177e2005-04-16 15:20:36 -07002664{
Jens Axboe4ac845a2008-01-24 08:44:49 +01002665 call_for_each_cic(ioc, changed_ioprio);
Jens Axboefc463792006-08-29 09:05:44 +02002666 ioc->ioprio_changed = 0;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002667}
2668
Jens Axboed5036d72009-06-26 10:44:34 +02002669static void cfq_init_cfqq(struct cfq_data *cfqd, struct cfq_queue *cfqq,
Jens Axboea6151c32009-10-07 20:02:57 +02002670 pid_t pid, bool is_sync)
Jens Axboed5036d72009-06-26 10:44:34 +02002671{
2672 RB_CLEAR_NODE(&cfqq->rb_node);
2673 RB_CLEAR_NODE(&cfqq->p_node);
2674 INIT_LIST_HEAD(&cfqq->fifo);
2675
2676 atomic_set(&cfqq->ref, 0);
2677 cfqq->cfqd = cfqd;
2678
2679 cfq_mark_cfqq_prio_changed(cfqq);
2680
2681 if (is_sync) {
2682 if (!cfq_class_idle(cfqq))
2683 cfq_mark_cfqq_idle_window(cfqq);
2684 cfq_mark_cfqq_sync(cfqq);
2685 }
2686 cfqq->pid = pid;
2687}
2688
Vivek Goyal246103332009-12-03 12:59:51 -05002689#ifdef CONFIG_CFQ_GROUP_IOSCHED
2690static void changed_cgroup(struct io_context *ioc, struct cfq_io_context *cic)
2691{
2692 struct cfq_queue *sync_cfqq = cic_to_cfqq(cic, 1);
2693 struct cfq_data *cfqd = cic->key;
2694 unsigned long flags;
2695 struct request_queue *q;
2696
2697 if (unlikely(!cfqd))
2698 return;
2699
2700 q = cfqd->queue;
2701
2702 spin_lock_irqsave(q->queue_lock, flags);
2703
2704 if (sync_cfqq) {
2705 /*
2706 * Drop reference to sync queue. A new sync queue will be
2707 * assigned in new group upon arrival of a fresh request.
2708 */
2709 cfq_log_cfqq(cfqd, sync_cfqq, "changed cgroup");
2710 cic_set_cfqq(cic, NULL, 1);
2711 cfq_put_queue(sync_cfqq);
2712 }
2713
2714 spin_unlock_irqrestore(q->queue_lock, flags);
2715}
2716
2717static void cfq_ioc_set_cgroup(struct io_context *ioc)
2718{
2719 call_for_each_cic(ioc, changed_cgroup);
2720 ioc->cgroup_changed = 0;
2721}
2722#endif /* CONFIG_CFQ_GROUP_IOSCHED */
2723
Linus Torvalds1da177e2005-04-16 15:20:36 -07002724static struct cfq_queue *
Jens Axboea6151c32009-10-07 20:02:57 +02002725cfq_find_alloc_queue(struct cfq_data *cfqd, bool is_sync,
Jens Axboefd0928d2008-01-24 08:52:45 +01002726 struct io_context *ioc, gfp_t gfp_mask)
Linus Torvalds1da177e2005-04-16 15:20:36 -07002727{
Linus Torvalds1da177e2005-04-16 15:20:36 -07002728 struct cfq_queue *cfqq, *new_cfqq = NULL;
Vasily Tarasov91fac312007-04-25 12:29:51 +02002729 struct cfq_io_context *cic;
Vivek Goyalcdb16e82009-12-03 12:59:38 -05002730 struct cfq_group *cfqg;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002731
2732retry:
Vivek Goyalcdb16e82009-12-03 12:59:38 -05002733 cfqg = cfq_get_cfqg(cfqd, 1);
Jens Axboe4ac845a2008-01-24 08:44:49 +01002734 cic = cfq_cic_lookup(cfqd, ioc);
Vasily Tarasov91fac312007-04-25 12:29:51 +02002735 /* cic always exists here */
2736 cfqq = cic_to_cfqq(cic, is_sync);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002737
Jens Axboe6118b702009-06-30 09:34:12 +02002738 /*
2739 * Always try a new alloc if we fell back to the OOM cfqq
2740 * originally, since it should just be a temporary situation.
2741 */
2742 if (!cfqq || cfqq == &cfqd->oom_cfqq) {
2743 cfqq = NULL;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002744 if (new_cfqq) {
2745 cfqq = new_cfqq;
2746 new_cfqq = NULL;
Jens Axboe22e2c502005-06-27 10:55:12 +02002747 } else if (gfp_mask & __GFP_WAIT) {
Linus Torvalds1da177e2005-04-16 15:20:36 -07002748 spin_unlock_irq(cfqd->queue->queue_lock);
Christoph Lameter94f60302007-07-17 04:03:29 -07002749 new_cfqq = kmem_cache_alloc_node(cfq_pool,
Jens Axboe6118b702009-06-30 09:34:12 +02002750 gfp_mask | __GFP_ZERO,
Christoph Lameter94f60302007-07-17 04:03:29 -07002751 cfqd->queue->node);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002752 spin_lock_irq(cfqd->queue->queue_lock);
Jens Axboe6118b702009-06-30 09:34:12 +02002753 if (new_cfqq)
2754 goto retry;
Jens Axboe22e2c502005-06-27 10:55:12 +02002755 } else {
Christoph Lameter94f60302007-07-17 04:03:29 -07002756 cfqq = kmem_cache_alloc_node(cfq_pool,
2757 gfp_mask | __GFP_ZERO,
2758 cfqd->queue->node);
Kiyoshi Ueda db3b5842005-06-17 16:15:10 +02002759 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07002760
Jens Axboe6118b702009-06-30 09:34:12 +02002761 if (cfqq) {
2762 cfq_init_cfqq(cfqd, cfqq, current->pid, is_sync);
2763 cfq_init_prio_data(cfqq, ioc);
Vivek Goyalcdb16e82009-12-03 12:59:38 -05002764 cfq_link_cfqq_cfqg(cfqq, cfqg);
Jens Axboe6118b702009-06-30 09:34:12 +02002765 cfq_log_cfqq(cfqd, cfqq, "alloced");
2766 } else
2767 cfqq = &cfqd->oom_cfqq;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002768 }
2769
2770 if (new_cfqq)
2771 kmem_cache_free(cfq_pool, new_cfqq);
2772
Linus Torvalds1da177e2005-04-16 15:20:36 -07002773 return cfqq;
2774}
2775
Vasily Tarasovc2dea2d2007-07-20 10:06:38 +02002776static struct cfq_queue **
2777cfq_async_queue_prio(struct cfq_data *cfqd, int ioprio_class, int ioprio)
2778{
Jens Axboefe094d92008-01-31 13:08:54 +01002779 switch (ioprio_class) {
Vasily Tarasovc2dea2d2007-07-20 10:06:38 +02002780 case IOPRIO_CLASS_RT:
2781 return &cfqd->async_cfqq[0][ioprio];
2782 case IOPRIO_CLASS_BE:
2783 return &cfqd->async_cfqq[1][ioprio];
2784 case IOPRIO_CLASS_IDLE:
2785 return &cfqd->async_idle_cfqq;
2786 default:
2787 BUG();
2788 }
2789}
2790
Jens Axboe15c31be2007-07-10 13:43:25 +02002791static struct cfq_queue *
Jens Axboea6151c32009-10-07 20:02:57 +02002792cfq_get_queue(struct cfq_data *cfqd, bool is_sync, struct io_context *ioc,
Jens Axboe15c31be2007-07-10 13:43:25 +02002793 gfp_t gfp_mask)
2794{
Jens Axboefd0928d2008-01-24 08:52:45 +01002795 const int ioprio = task_ioprio(ioc);
2796 const int ioprio_class = task_ioprio_class(ioc);
Vasily Tarasovc2dea2d2007-07-20 10:06:38 +02002797 struct cfq_queue **async_cfqq = NULL;
Jens Axboe15c31be2007-07-10 13:43:25 +02002798 struct cfq_queue *cfqq = NULL;
2799
Vasily Tarasovc2dea2d2007-07-20 10:06:38 +02002800 if (!is_sync) {
2801 async_cfqq = cfq_async_queue_prio(cfqd, ioprio_class, ioprio);
2802 cfqq = *async_cfqq;
2803 }
2804
Jens Axboe6118b702009-06-30 09:34:12 +02002805 if (!cfqq)
Jens Axboefd0928d2008-01-24 08:52:45 +01002806 cfqq = cfq_find_alloc_queue(cfqd, is_sync, ioc, gfp_mask);
Jens Axboe15c31be2007-07-10 13:43:25 +02002807
2808 /*
2809 * pin the queue now that it's allocated, scheduler exit will prune it
2810 */
Vasily Tarasovc2dea2d2007-07-20 10:06:38 +02002811 if (!is_sync && !(*async_cfqq)) {
Jens Axboe15c31be2007-07-10 13:43:25 +02002812 atomic_inc(&cfqq->ref);
Vasily Tarasovc2dea2d2007-07-20 10:06:38 +02002813 *async_cfqq = cfqq;
Jens Axboe15c31be2007-07-10 13:43:25 +02002814 }
2815
2816 atomic_inc(&cfqq->ref);
2817 return cfqq;
2818}
2819
Jens Axboe498d3aa22007-04-26 12:54:48 +02002820/*
2821 * We drop cfq io contexts lazily, so we may find a dead one.
2822 */
OGAWA Hirofumidbecf3a2006-04-18 09:45:18 +02002823static void
Jens Axboe4ac845a2008-01-24 08:44:49 +01002824cfq_drop_dead_cic(struct cfq_data *cfqd, struct io_context *ioc,
2825 struct cfq_io_context *cic)
OGAWA Hirofumidbecf3a2006-04-18 09:45:18 +02002826{
Jens Axboe4ac845a2008-01-24 08:44:49 +01002827 unsigned long flags;
2828
Jens Axboefc463792006-08-29 09:05:44 +02002829 WARN_ON(!list_empty(&cic->queue_list));
Jens Axboe597bc482007-04-24 21:23:53 +02002830
Jens Axboe4ac845a2008-01-24 08:44:49 +01002831 spin_lock_irqsave(&ioc->lock, flags);
Jens Axboe597bc482007-04-24 21:23:53 +02002832
Fabio Checconi4faa3c82008-04-10 08:28:01 +02002833 BUG_ON(ioc->ioc_data == cic);
Jens Axboe4ac845a2008-01-24 08:44:49 +01002834
2835 radix_tree_delete(&ioc->radix_root, (unsigned long) cfqd);
Jens Axboeffc4e752008-02-19 10:02:29 +01002836 hlist_del_rcu(&cic->cic_list);
Jens Axboe4ac845a2008-01-24 08:44:49 +01002837 spin_unlock_irqrestore(&ioc->lock, flags);
2838
2839 cfq_cic_free(cic);
OGAWA Hirofumidbecf3a2006-04-18 09:45:18 +02002840}
2841
Jens Axboee2d74ac2006-03-28 08:59:01 +02002842static struct cfq_io_context *
Jens Axboe4ac845a2008-01-24 08:44:49 +01002843cfq_cic_lookup(struct cfq_data *cfqd, struct io_context *ioc)
Jens Axboee2d74ac2006-03-28 08:59:01 +02002844{
Jens Axboee2d74ac2006-03-28 08:59:01 +02002845 struct cfq_io_context *cic;
Jens Axboed6de8be2008-05-28 14:46:59 +02002846 unsigned long flags;
Jens Axboe4ac845a2008-01-24 08:44:49 +01002847 void *k;
Jens Axboee2d74ac2006-03-28 08:59:01 +02002848
Vasily Tarasov91fac312007-04-25 12:29:51 +02002849 if (unlikely(!ioc))
2850 return NULL;
2851
Jens Axboed6de8be2008-05-28 14:46:59 +02002852 rcu_read_lock();
2853
Jens Axboe597bc482007-04-24 21:23:53 +02002854 /*
2855 * we maintain a last-hit cache, to avoid browsing over the tree
2856 */
Jens Axboe4ac845a2008-01-24 08:44:49 +01002857 cic = rcu_dereference(ioc->ioc_data);
Jens Axboed6de8be2008-05-28 14:46:59 +02002858 if (cic && cic->key == cfqd) {
2859 rcu_read_unlock();
Jens Axboe597bc482007-04-24 21:23:53 +02002860 return cic;
Jens Axboed6de8be2008-05-28 14:46:59 +02002861 }
Jens Axboe597bc482007-04-24 21:23:53 +02002862
Jens Axboe4ac845a2008-01-24 08:44:49 +01002863 do {
Jens Axboe4ac845a2008-01-24 08:44:49 +01002864 cic = radix_tree_lookup(&ioc->radix_root, (unsigned long) cfqd);
2865 rcu_read_unlock();
2866 if (!cic)
2867 break;
OGAWA Hirofumibe3b0752006-04-18 19:18:31 +02002868 /* ->key must be copied to avoid race with cfq_exit_queue() */
2869 k = cic->key;
2870 if (unlikely(!k)) {
Jens Axboe4ac845a2008-01-24 08:44:49 +01002871 cfq_drop_dead_cic(cfqd, ioc, cic);
Jens Axboed6de8be2008-05-28 14:46:59 +02002872 rcu_read_lock();
Jens Axboe4ac845a2008-01-24 08:44:49 +01002873 continue;
OGAWA Hirofumidbecf3a2006-04-18 09:45:18 +02002874 }
Jens Axboee2d74ac2006-03-28 08:59:01 +02002875
Jens Axboed6de8be2008-05-28 14:46:59 +02002876 spin_lock_irqsave(&ioc->lock, flags);
Jens Axboe4ac845a2008-01-24 08:44:49 +01002877 rcu_assign_pointer(ioc->ioc_data, cic);
Jens Axboed6de8be2008-05-28 14:46:59 +02002878 spin_unlock_irqrestore(&ioc->lock, flags);
Jens Axboe4ac845a2008-01-24 08:44:49 +01002879 break;
2880 } while (1);
Jens Axboee2d74ac2006-03-28 08:59:01 +02002881
Jens Axboe4ac845a2008-01-24 08:44:49 +01002882 return cic;
Jens Axboee2d74ac2006-03-28 08:59:01 +02002883}
2884
Jens Axboe4ac845a2008-01-24 08:44:49 +01002885/*
2886 * Add cic into ioc, using cfqd as the search key. This enables us to lookup
2887 * the process specific cfq io context when entered from the block layer.
2888 * Also adds the cic to a per-cfqd list, used when this queue is removed.
2889 */
Jens Axboefebffd62008-01-28 13:19:43 +01002890static int cfq_cic_link(struct cfq_data *cfqd, struct io_context *ioc,
2891 struct cfq_io_context *cic, gfp_t gfp_mask)
Jens Axboee2d74ac2006-03-28 08:59:01 +02002892{
Jens Axboe0261d682006-10-30 19:07:48 +01002893 unsigned long flags;
Jens Axboe4ac845a2008-01-24 08:44:49 +01002894 int ret;
Jens Axboee2d74ac2006-03-28 08:59:01 +02002895
Jens Axboe4ac845a2008-01-24 08:44:49 +01002896 ret = radix_tree_preload(gfp_mask);
2897 if (!ret) {
2898 cic->ioc = ioc;
2899 cic->key = cfqd;
Jens Axboee2d74ac2006-03-28 08:59:01 +02002900
Jens Axboe4ac845a2008-01-24 08:44:49 +01002901 spin_lock_irqsave(&ioc->lock, flags);
2902 ret = radix_tree_insert(&ioc->radix_root,
2903 (unsigned long) cfqd, cic);
Jens Axboeffc4e752008-02-19 10:02:29 +01002904 if (!ret)
2905 hlist_add_head_rcu(&cic->cic_list, &ioc->cic_list);
Jens Axboe4ac845a2008-01-24 08:44:49 +01002906 spin_unlock_irqrestore(&ioc->lock, flags);
2907
2908 radix_tree_preload_end();
2909
2910 if (!ret) {
2911 spin_lock_irqsave(cfqd->queue->queue_lock, flags);
2912 list_add(&cic->queue_list, &cfqd->cic_list);
2913 spin_unlock_irqrestore(cfqd->queue->queue_lock, flags);
OGAWA Hirofumidbecf3a2006-04-18 09:45:18 +02002914 }
Jens Axboee2d74ac2006-03-28 08:59:01 +02002915 }
2916
Jens Axboe4ac845a2008-01-24 08:44:49 +01002917 if (ret)
2918 printk(KERN_ERR "cfq: cic link failed!\n");
Jens Axboefc463792006-08-29 09:05:44 +02002919
Jens Axboe4ac845a2008-01-24 08:44:49 +01002920 return ret;
Jens Axboee2d74ac2006-03-28 08:59:01 +02002921}
2922
Jens Axboe22e2c502005-06-27 10:55:12 +02002923/*
2924 * Setup general io context and cfq io context. There can be several cfq
2925 * io contexts per general io context, if this process is doing io to more
Jens Axboee2d74ac2006-03-28 08:59:01 +02002926 * than one device managed by cfq.
Jens Axboe22e2c502005-06-27 10:55:12 +02002927 */
2928static struct cfq_io_context *
Jens Axboee2d74ac2006-03-28 08:59:01 +02002929cfq_get_io_context(struct cfq_data *cfqd, gfp_t gfp_mask)
Linus Torvalds1da177e2005-04-16 15:20:36 -07002930{
Jens Axboe22e2c502005-06-27 10:55:12 +02002931 struct io_context *ioc = NULL;
2932 struct cfq_io_context *cic;
2933
2934 might_sleep_if(gfp_mask & __GFP_WAIT);
2935
Jens Axboeb5deef92006-07-19 23:39:40 +02002936 ioc = get_io_context(gfp_mask, cfqd->queue->node);
Jens Axboe22e2c502005-06-27 10:55:12 +02002937 if (!ioc)
2938 return NULL;
2939
Jens Axboe4ac845a2008-01-24 08:44:49 +01002940 cic = cfq_cic_lookup(cfqd, ioc);
Jens Axboee2d74ac2006-03-28 08:59:01 +02002941 if (cic)
2942 goto out;
Jens Axboe22e2c502005-06-27 10:55:12 +02002943
Jens Axboee2d74ac2006-03-28 08:59:01 +02002944 cic = cfq_alloc_io_context(cfqd, gfp_mask);
2945 if (cic == NULL)
2946 goto err;
Jens Axboe22e2c502005-06-27 10:55:12 +02002947
Jens Axboe4ac845a2008-01-24 08:44:49 +01002948 if (cfq_cic_link(cfqd, ioc, cic, gfp_mask))
2949 goto err_free;
2950
Jens Axboe22e2c502005-06-27 10:55:12 +02002951out:
Jens Axboefc463792006-08-29 09:05:44 +02002952 smp_read_barrier_depends();
2953 if (unlikely(ioc->ioprio_changed))
2954 cfq_ioc_set_ioprio(ioc);
2955
Vivek Goyal246103332009-12-03 12:59:51 -05002956#ifdef CONFIG_CFQ_GROUP_IOSCHED
2957 if (unlikely(ioc->cgroup_changed))
2958 cfq_ioc_set_cgroup(ioc);
2959#endif
Jens Axboe22e2c502005-06-27 10:55:12 +02002960 return cic;
Jens Axboe4ac845a2008-01-24 08:44:49 +01002961err_free:
2962 cfq_cic_free(cic);
Jens Axboe22e2c502005-06-27 10:55:12 +02002963err:
2964 put_io_context(ioc);
2965 return NULL;
2966}
2967
2968static void
2969cfq_update_io_thinktime(struct cfq_data *cfqd, struct cfq_io_context *cic)
2970{
Jens Axboeaaf12282007-01-19 11:30:16 +11002971 unsigned long elapsed = jiffies - cic->last_end_request;
2972 unsigned long ttime = min(elapsed, 2UL * cfqd->cfq_slice_idle);
Jens Axboe22e2c502005-06-27 10:55:12 +02002973
2974 cic->ttime_samples = (7*cic->ttime_samples + 256) / 8;
2975 cic->ttime_total = (7*cic->ttime_total + 256*ttime) / 8;
2976 cic->ttime_mean = (cic->ttime_total + 128) / cic->ttime_samples;
2977}
2978
Jens Axboe206dc692006-03-28 13:03:44 +02002979static void
Jeff Moyerb2c18e12009-10-23 17:14:49 -04002980cfq_update_io_seektime(struct cfq_data *cfqd, struct cfq_queue *cfqq,
Jens Axboe6d048f52007-04-25 12:44:27 +02002981 struct request *rq)
Jens Axboe206dc692006-03-28 13:03:44 +02002982{
2983 sector_t sdist;
2984 u64 total;
2985
Jeff Moyerb2c18e12009-10-23 17:14:49 -04002986 if (!cfqq->last_request_pos)
Jeff Moyer4d00aa42009-04-21 07:25:04 +02002987 sdist = 0;
Jeff Moyerb2c18e12009-10-23 17:14:49 -04002988 else if (cfqq->last_request_pos < blk_rq_pos(rq))
2989 sdist = blk_rq_pos(rq) - cfqq->last_request_pos;
Jens Axboe206dc692006-03-28 13:03:44 +02002990 else
Jeff Moyerb2c18e12009-10-23 17:14:49 -04002991 sdist = cfqq->last_request_pos - blk_rq_pos(rq);
Jens Axboe206dc692006-03-28 13:03:44 +02002992
2993 /*
2994 * Don't allow the seek distance to get too large from the
2995 * odd fragment, pagein, etc
2996 */
Jeff Moyerb2c18e12009-10-23 17:14:49 -04002997 if (cfqq->seek_samples <= 60) /* second&third seek */
2998 sdist = min(sdist, (cfqq->seek_mean * 4) + 2*1024*1024);
Jens Axboe206dc692006-03-28 13:03:44 +02002999 else
Jeff Moyerb2c18e12009-10-23 17:14:49 -04003000 sdist = min(sdist, (cfqq->seek_mean * 4) + 2*1024*64);
Jens Axboe206dc692006-03-28 13:03:44 +02003001
Jeff Moyerb2c18e12009-10-23 17:14:49 -04003002 cfqq->seek_samples = (7*cfqq->seek_samples + 256) / 8;
3003 cfqq->seek_total = (7*cfqq->seek_total + (u64)256*sdist) / 8;
3004 total = cfqq->seek_total + (cfqq->seek_samples/2);
3005 do_div(total, cfqq->seek_samples);
3006 cfqq->seek_mean = (sector_t)total;
Jens Axboe206dc692006-03-28 13:03:44 +02003007}
Jens Axboe22e2c502005-06-27 10:55:12 +02003008
3009/*
3010 * Disable idle window if the process thinks too long or seeks so much that
3011 * it doesn't matter
3012 */
3013static void
3014cfq_update_idle_window(struct cfq_data *cfqd, struct cfq_queue *cfqq,
3015 struct cfq_io_context *cic)
3016{
Jens Axboe7b679132008-05-30 12:23:07 +02003017 int old_idle, enable_idle;
Jens Axboe1be92f22007-04-19 14:32:26 +02003018
Jens Axboe08717142008-01-28 11:38:15 +01003019 /*
3020 * Don't idle for async or idle io prio class
3021 */
3022 if (!cfq_cfqq_sync(cfqq) || cfq_class_idle(cfqq))
Jens Axboe1be92f22007-04-19 14:32:26 +02003023 return;
3024
Jens Axboec265a7f2008-06-26 13:49:33 +02003025 enable_idle = old_idle = cfq_cfqq_idle_window(cfqq);
Jens Axboe22e2c502005-06-27 10:55:12 +02003026
Corrado Zoccolo76280af2009-11-26 10:02:58 +01003027 if (cfqq->queued[0] + cfqq->queued[1] >= 4)
3028 cfq_mark_cfqq_deep(cfqq);
3029
Nikanth Karthikesan66dac982007-11-27 12:47:04 +01003030 if (!atomic_read(&cic->ioc->nr_tasks) || !cfqd->cfq_slice_idle ||
Corrado Zoccolo76280af2009-11-26 10:02:58 +01003031 (!cfq_cfqq_deep(cfqq) && sample_valid(cfqq->seek_samples)
3032 && CFQQ_SEEKY(cfqq)))
Jens Axboe22e2c502005-06-27 10:55:12 +02003033 enable_idle = 0;
3034 else if (sample_valid(cic->ttime_samples)) {
Corrado Zoccolo718eee02009-10-26 22:45:29 +01003035 if (cic->ttime_mean > cfqd->cfq_slice_idle)
Jens Axboe22e2c502005-06-27 10:55:12 +02003036 enable_idle = 0;
3037 else
3038 enable_idle = 1;
3039 }
3040
Jens Axboe7b679132008-05-30 12:23:07 +02003041 if (old_idle != enable_idle) {
3042 cfq_log_cfqq(cfqd, cfqq, "idle=%d", enable_idle);
3043 if (enable_idle)
3044 cfq_mark_cfqq_idle_window(cfqq);
3045 else
3046 cfq_clear_cfqq_idle_window(cfqq);
3047 }
Jens Axboe22e2c502005-06-27 10:55:12 +02003048}
3049
Jens Axboe22e2c502005-06-27 10:55:12 +02003050/*
3051 * Check if new_cfqq should preempt the currently active queue. Return 0 for
3052 * no or if we aren't sure, a 1 will cause a preempt.
3053 */
Jens Axboea6151c32009-10-07 20:02:57 +02003054static bool
Jens Axboe22e2c502005-06-27 10:55:12 +02003055cfq_should_preempt(struct cfq_data *cfqd, struct cfq_queue *new_cfqq,
Jens Axboe5e705372006-07-13 12:39:25 +02003056 struct request *rq)
Jens Axboe22e2c502005-06-27 10:55:12 +02003057{
Jens Axboe6d048f52007-04-25 12:44:27 +02003058 struct cfq_queue *cfqq;
Jens Axboe22e2c502005-06-27 10:55:12 +02003059
Jens Axboe6d048f52007-04-25 12:44:27 +02003060 cfqq = cfqd->active_queue;
3061 if (!cfqq)
Jens Axboea6151c32009-10-07 20:02:57 +02003062 return false;
Jens Axboe22e2c502005-06-27 10:55:12 +02003063
Jens Axboe6d048f52007-04-25 12:44:27 +02003064 if (cfq_class_idle(new_cfqq))
Jens Axboea6151c32009-10-07 20:02:57 +02003065 return false;
Jens Axboe22e2c502005-06-27 10:55:12 +02003066
3067 if (cfq_class_idle(cfqq))
Jens Axboea6151c32009-10-07 20:02:57 +02003068 return true;
Jens Axboe1e3335d2007-02-14 19:59:49 +01003069
Jens Axboe22e2c502005-06-27 10:55:12 +02003070 /*
Divyesh Shah875feb62010-01-06 18:58:20 -08003071 * Don't allow a non-RT request to preempt an ongoing RT cfqq timeslice.
3072 */
3073 if (cfq_class_rt(cfqq) && !cfq_class_rt(new_cfqq))
3074 return false;
3075
3076 /*
Jens Axboe374f84a2006-07-23 01:42:19 +02003077 * if the new request is sync, but the currently running queue is
3078 * not, let the sync request have priority.
3079 */
Jens Axboe5e705372006-07-13 12:39:25 +02003080 if (rq_is_sync(rq) && !cfq_cfqq_sync(cfqq))
Jens Axboea6151c32009-10-07 20:02:57 +02003081 return true;
Jens Axboe1e3335d2007-02-14 19:59:49 +01003082
Vivek Goyal8682e1f2009-12-03 12:59:50 -05003083 if (new_cfqq->cfqg != cfqq->cfqg)
3084 return false;
3085
3086 if (cfq_slice_used(cfqq))
3087 return true;
3088
3089 /* Allow preemption only if we are idling on sync-noidle tree */
3090 if (cfqd->serving_type == SYNC_NOIDLE_WORKLOAD &&
3091 cfqq_type(new_cfqq) == SYNC_NOIDLE_WORKLOAD &&
3092 new_cfqq->service_tree->count == 2 &&
3093 RB_EMPTY_ROOT(&cfqq->sort_list))
3094 return true;
3095
Jens Axboe374f84a2006-07-23 01:42:19 +02003096 /*
3097 * So both queues are sync. Let the new request get disk time if
3098 * it's a metadata request and the current queue is doing regular IO.
3099 */
3100 if (rq_is_meta(rq) && !cfqq->meta_pending)
Jens Axboee6ec4fe2009-11-03 20:21:35 +01003101 return true;
Jens Axboe22e2c502005-06-27 10:55:12 +02003102
Divyesh Shah3a9a3f62009-01-30 12:46:41 +01003103 /*
3104 * Allow an RT request to pre-empt an ongoing non-RT cfqq timeslice.
3105 */
3106 if (cfq_class_rt(new_cfqq) && !cfq_class_rt(cfqq))
Jens Axboea6151c32009-10-07 20:02:57 +02003107 return true;
Divyesh Shah3a9a3f62009-01-30 12:46:41 +01003108
Jens Axboe1e3335d2007-02-14 19:59:49 +01003109 if (!cfqd->active_cic || !cfq_cfqq_wait_request(cfqq))
Jens Axboea6151c32009-10-07 20:02:57 +02003110 return false;
Jens Axboe1e3335d2007-02-14 19:59:49 +01003111
3112 /*
3113 * if this request is as-good as one we would expect from the
3114 * current cfqq, let it preempt
3115 */
Shaohua Li2f7a2d82009-12-28 13:18:44 +01003116 if (cfq_rq_close(cfqd, cfqq, rq, true))
Jens Axboea6151c32009-10-07 20:02:57 +02003117 return true;
Jens Axboe1e3335d2007-02-14 19:59:49 +01003118
Jens Axboea6151c32009-10-07 20:02:57 +02003119 return false;
Jens Axboe22e2c502005-06-27 10:55:12 +02003120}
3121
3122/*
3123 * cfqq preempts the active queue. if we allowed preempt with no slice left,
3124 * let it have half of its nominal slice.
3125 */
3126static void cfq_preempt_queue(struct cfq_data *cfqd, struct cfq_queue *cfqq)
3127{
Jens Axboe7b679132008-05-30 12:23:07 +02003128 cfq_log_cfqq(cfqd, cfqq, "preempt");
Jens Axboe6084cdd2007-04-23 08:25:00 +02003129 cfq_slice_expired(cfqd, 1);
Jens Axboe22e2c502005-06-27 10:55:12 +02003130
Jens Axboebf572252006-07-19 20:29:12 +02003131 /*
3132 * Put the new queue at the front of the of the current list,
3133 * so we know that it will be selected next.
3134 */
3135 BUG_ON(!cfq_cfqq_on_rr(cfqq));
Jens Axboeedd75ff2007-04-19 12:03:34 +02003136
3137 cfq_service_tree_add(cfqd, cfqq, 1);
Jens Axboebf572252006-07-19 20:29:12 +02003138
Jens Axboe44f7c162007-01-19 11:51:58 +11003139 cfqq->slice_end = 0;
3140 cfq_mark_cfqq_slice_new(cfqq);
Jens Axboe22e2c502005-06-27 10:55:12 +02003141}
3142
3143/*
Jens Axboe5e705372006-07-13 12:39:25 +02003144 * Called when a new fs request (rq) is added (to cfqq). Check if there's
Jens Axboe22e2c502005-06-27 10:55:12 +02003145 * something we should do about it
3146 */
3147static void
Jens Axboe5e705372006-07-13 12:39:25 +02003148cfq_rq_enqueued(struct cfq_data *cfqd, struct cfq_queue *cfqq,
3149 struct request *rq)
Jens Axboe22e2c502005-06-27 10:55:12 +02003150{
Jens Axboe5e705372006-07-13 12:39:25 +02003151 struct cfq_io_context *cic = RQ_CIC(rq);
Jens Axboe12e9fdd2006-06-01 10:09:56 +02003152
Aaron Carroll45333d52008-08-26 15:52:36 +02003153 cfqd->rq_queued++;
Jens Axboe374f84a2006-07-23 01:42:19 +02003154 if (rq_is_meta(rq))
3155 cfqq->meta_pending++;
3156
Jens Axboe9c2c38a2005-08-24 14:57:54 +02003157 cfq_update_io_thinktime(cfqd, cic);
Jeff Moyerb2c18e12009-10-23 17:14:49 -04003158 cfq_update_io_seektime(cfqd, cfqq, rq);
Jens Axboe9c2c38a2005-08-24 14:57:54 +02003159 cfq_update_idle_window(cfqd, cfqq, cic);
3160
Jeff Moyerb2c18e12009-10-23 17:14:49 -04003161 cfqq->last_request_pos = blk_rq_pos(rq) + blk_rq_sectors(rq);
Jens Axboe22e2c502005-06-27 10:55:12 +02003162
3163 if (cfqq == cfqd->active_queue) {
3164 /*
Jens Axboeb0291952009-04-07 11:38:31 +02003165 * Remember that we saw a request from this process, but
3166 * don't start queuing just yet. Otherwise we risk seeing lots
3167 * of tiny requests, because we disrupt the normal plugging
Jens Axboed6ceb252009-04-14 14:18:16 +02003168 * and merging. If the request is already larger than a single
3169 * page, let it rip immediately. For that case we assume that
Jens Axboe2d870722009-04-15 12:12:46 +02003170 * merging is already done. Ditto for a busy system that
3171 * has other work pending, don't risk delaying until the
3172 * idle timer unplug to continue working.
Jens Axboe22e2c502005-06-27 10:55:12 +02003173 */
Jens Axboed6ceb252009-04-14 14:18:16 +02003174 if (cfq_cfqq_wait_request(cfqq)) {
Jens Axboe2d870722009-04-15 12:12:46 +02003175 if (blk_rq_bytes(rq) > PAGE_CACHE_SIZE ||
3176 cfqd->busy_queues > 1) {
Jens Axboed6ceb252009-04-14 14:18:16 +02003177 del_timer(&cfqd->idle_slice_timer);
Gui Jianfeng554554f2009-12-10 09:38:39 +01003178 cfq_clear_cfqq_wait_request(cfqq);
Vivek Goyalbf7919372009-12-03 12:59:37 -05003179 __blk_run_queue(cfqd->queue);
3180 } else
3181 cfq_mark_cfqq_must_dispatch(cfqq);
Jens Axboed6ceb252009-04-14 14:18:16 +02003182 }
Jens Axboe5e705372006-07-13 12:39:25 +02003183 } else if (cfq_should_preempt(cfqd, cfqq, rq)) {
Jens Axboe22e2c502005-06-27 10:55:12 +02003184 /*
3185 * not the active queue - expire current slice if it is
3186 * idle and has expired it's mean thinktime or this new queue
Divyesh Shah3a9a3f62009-01-30 12:46:41 +01003187 * has some old slice time left and is of higher priority or
3188 * this new queue is RT and the current one is BE
Jens Axboe22e2c502005-06-27 10:55:12 +02003189 */
3190 cfq_preempt_queue(cfqd, cfqq);
Tejun Heoa7f55792009-04-23 11:05:17 +09003191 __blk_run_queue(cfqd->queue);
Jens Axboe22e2c502005-06-27 10:55:12 +02003192 }
3193}
3194
Jens Axboe165125e2007-07-24 09:28:11 +02003195static void cfq_insert_request(struct request_queue *q, struct request *rq)
Jens Axboe22e2c502005-06-27 10:55:12 +02003196{
Jens Axboeb4878f22005-10-20 16:42:29 +02003197 struct cfq_data *cfqd = q->elevator->elevator_data;
Jens Axboe5e705372006-07-13 12:39:25 +02003198 struct cfq_queue *cfqq = RQ_CFQQ(rq);
Jens Axboe22e2c502005-06-27 10:55:12 +02003199
Jens Axboe7b679132008-05-30 12:23:07 +02003200 cfq_log_cfqq(cfqd, cfqq, "insert_request");
Jens Axboefd0928d2008-01-24 08:52:45 +01003201 cfq_init_prio_data(cfqq, RQ_CIC(rq)->ioc);
Linus Torvalds1da177e2005-04-16 15:20:36 -07003202
Jens Axboe30996f42009-10-05 11:03:39 +02003203 rq_set_fifo_time(rq, jiffies + cfqd->cfq_fifo_expire[rq_is_sync(rq)]);
Jens Axboe22e2c502005-06-27 10:55:12 +02003204 list_add_tail(&rq->queuelist, &cfqq->fifo);
Corrado Zoccoloaa6f6a32009-10-26 22:44:33 +01003205 cfq_add_rq_rb(rq);
Jens Axboe22e2c502005-06-27 10:55:12 +02003206
Jens Axboe5e705372006-07-13 12:39:25 +02003207 cfq_rq_enqueued(cfqd, cfqq, rq);
Linus Torvalds1da177e2005-04-16 15:20:36 -07003208}
3209
Aaron Carroll45333d52008-08-26 15:52:36 +02003210/*
3211 * Update hw_tag based on peak queue depth over 50 samples under
3212 * sufficient load.
3213 */
3214static void cfq_update_hw_tag(struct cfq_data *cfqd)
3215{
Shaohua Li1a1238a2009-10-27 08:46:23 +01003216 struct cfq_queue *cfqq = cfqd->active_queue;
3217
Corrado Zoccoloe459dd02009-11-26 10:02:57 +01003218 if (rq_in_driver(cfqd) > cfqd->hw_tag_est_depth)
3219 cfqd->hw_tag_est_depth = rq_in_driver(cfqd);
3220
3221 if (cfqd->hw_tag == 1)
3222 return;
Aaron Carroll45333d52008-08-26 15:52:36 +02003223
3224 if (cfqd->rq_queued <= CFQ_HW_QUEUE_MIN &&
Jens Axboe5ad531d2009-07-03 12:57:48 +02003225 rq_in_driver(cfqd) <= CFQ_HW_QUEUE_MIN)
Aaron Carroll45333d52008-08-26 15:52:36 +02003226 return;
3227
Shaohua Li1a1238a2009-10-27 08:46:23 +01003228 /*
3229 * If active queue hasn't enough requests and can idle, cfq might not
3230 * dispatch sufficient requests to hardware. Don't zero hw_tag in this
3231 * case
3232 */
3233 if (cfqq && cfq_cfqq_idle_window(cfqq) &&
3234 cfqq->dispatched + cfqq->queued[0] + cfqq->queued[1] <
3235 CFQ_HW_QUEUE_MIN && rq_in_driver(cfqd) < CFQ_HW_QUEUE_MIN)
3236 return;
3237
Aaron Carroll45333d52008-08-26 15:52:36 +02003238 if (cfqd->hw_tag_samples++ < 50)
3239 return;
3240
Corrado Zoccoloe459dd02009-11-26 10:02:57 +01003241 if (cfqd->hw_tag_est_depth >= CFQ_HW_QUEUE_MIN)
Aaron Carroll45333d52008-08-26 15:52:36 +02003242 cfqd->hw_tag = 1;
3243 else
3244 cfqd->hw_tag = 0;
Aaron Carroll45333d52008-08-26 15:52:36 +02003245}
3246
Vivek Goyal7667aa02009-12-08 17:52:58 -05003247static bool cfq_should_wait_busy(struct cfq_data *cfqd, struct cfq_queue *cfqq)
3248{
3249 struct cfq_io_context *cic = cfqd->active_cic;
3250
3251 /* If there are other queues in the group, don't wait */
3252 if (cfqq->cfqg->nr_cfqq > 1)
3253 return false;
3254
3255 if (cfq_slice_used(cfqq))
3256 return true;
3257
3258 /* if slice left is less than think time, wait busy */
3259 if (cic && sample_valid(cic->ttime_samples)
3260 && (cfqq->slice_end - jiffies < cic->ttime_mean))
3261 return true;
3262
3263 /*
3264 * If think times is less than a jiffy than ttime_mean=0 and above
3265 * will not be true. It might happen that slice has not expired yet
3266 * but will expire soon (4-5 ns) during select_queue(). To cover the
3267 * case where think time is less than a jiffy, mark the queue wait
3268 * busy if only 1 jiffy is left in the slice.
3269 */
3270 if (cfqq->slice_end - jiffies == 1)
3271 return true;
3272
3273 return false;
3274}
3275
Jens Axboe165125e2007-07-24 09:28:11 +02003276static void cfq_completed_request(struct request_queue *q, struct request *rq)
Linus Torvalds1da177e2005-04-16 15:20:36 -07003277{
Jens Axboe5e705372006-07-13 12:39:25 +02003278 struct cfq_queue *cfqq = RQ_CFQQ(rq);
Jens Axboeb4878f22005-10-20 16:42:29 +02003279 struct cfq_data *cfqd = cfqq->cfqd;
Jens Axboe5380a102006-07-13 12:37:56 +02003280 const int sync = rq_is_sync(rq);
Jens Axboeb4878f22005-10-20 16:42:29 +02003281 unsigned long now;
Linus Torvalds1da177e2005-04-16 15:20:36 -07003282
Jens Axboeb4878f22005-10-20 16:42:29 +02003283 now = jiffies;
Vivek Goyal2868ef72009-12-03 12:59:48 -05003284 cfq_log_cfqq(cfqd, cfqq, "complete rqnoidle %d", !!rq_noidle(rq));
Linus Torvalds1da177e2005-04-16 15:20:36 -07003285
Aaron Carroll45333d52008-08-26 15:52:36 +02003286 cfq_update_hw_tag(cfqd);
3287
Jens Axboe5ad531d2009-07-03 12:57:48 +02003288 WARN_ON(!cfqd->rq_in_driver[sync]);
Jens Axboe6d048f52007-04-25 12:44:27 +02003289 WARN_ON(!cfqq->dispatched);
Jens Axboe5ad531d2009-07-03 12:57:48 +02003290 cfqd->rq_in_driver[sync]--;
Jens Axboe6d048f52007-04-25 12:44:27 +02003291 cfqq->dispatched--;
Linus Torvalds1da177e2005-04-16 15:20:36 -07003292
Jens Axboe3ed9a292007-04-23 08:33:33 +02003293 if (cfq_cfqq_sync(cfqq))
3294 cfqd->sync_flight--;
3295
Vivek Goyal365722b2009-10-03 15:21:27 +02003296 if (sync) {
Jens Axboe5e705372006-07-13 12:39:25 +02003297 RQ_CIC(rq)->last_end_request = now;
Corrado Zoccolo573412b2009-12-06 11:48:52 +01003298 if (!time_after(rq->start_time + cfqd->cfq_fifo_expire[1], now))
3299 cfqd->last_delayed_sync = now;
Vivek Goyal365722b2009-10-03 15:21:27 +02003300 }
Jens Axboecaaa5f92006-06-16 11:23:00 +02003301
3302 /*
3303 * If this is the active queue, check if it needs to be expired,
3304 * or if we want to idle in case it has no pending requests.
3305 */
3306 if (cfqd->active_queue == cfqq) {
Jens Axboea36e71f2009-04-15 12:15:11 +02003307 const bool cfqq_empty = RB_EMPTY_ROOT(&cfqq->sort_list);
3308
Jens Axboe44f7c162007-01-19 11:51:58 +11003309 if (cfq_cfqq_slice_new(cfqq)) {
3310 cfq_set_prio_slice(cfqd, cfqq);
3311 cfq_clear_cfqq_slice_new(cfqq);
3312 }
Vivek Goyalf75edf22009-12-03 12:59:53 -05003313
3314 /*
Vivek Goyal7667aa02009-12-08 17:52:58 -05003315 * Should we wait for next request to come in before we expire
3316 * the queue.
Vivek Goyalf75edf22009-12-03 12:59:53 -05003317 */
Vivek Goyal7667aa02009-12-08 17:52:58 -05003318 if (cfq_should_wait_busy(cfqd, cfqq)) {
Vivek Goyalf75edf22009-12-03 12:59:53 -05003319 cfqq->slice_end = jiffies + cfqd->cfq_slice_idle;
3320 cfq_mark_cfqq_wait_busy(cfqq);
3321 }
3322
Jens Axboea36e71f2009-04-15 12:15:11 +02003323 /*
Corrado Zoccolo8e550632009-11-26 10:02:58 +01003324 * Idling is not enabled on:
3325 * - expired queues
3326 * - idle-priority queues
3327 * - async queues
3328 * - queues with still some requests queued
3329 * - when there is a close cooperator
Jens Axboea36e71f2009-04-15 12:15:11 +02003330 */
Jens Axboe08717142008-01-28 11:38:15 +01003331 if (cfq_slice_used(cfqq) || cfq_class_idle(cfqq))
Jens Axboe6084cdd2007-04-23 08:25:00 +02003332 cfq_slice_expired(cfqd, 1);
Corrado Zoccolo8e550632009-11-26 10:02:58 +01003333 else if (sync && cfqq_empty &&
3334 !cfq_close_cooperator(cfqd, cfqq)) {
3335 cfqd->noidle_tree_requires_idle |= !rq_noidle(rq);
3336 /*
3337 * Idling is enabled for SYNC_WORKLOAD.
3338 * SYNC_NOIDLE_WORKLOAD idles at the end of the tree
3339 * only if we processed at least one !rq_noidle request
3340 */
3341 if (cfqd->serving_type == SYNC_WORKLOAD
Vivek Goyalc04645e2009-12-03 12:59:56 -05003342 || cfqd->noidle_tree_requires_idle
3343 || cfqq->cfqg->nr_cfqq == 1)
Corrado Zoccolo8e550632009-11-26 10:02:58 +01003344 cfq_arm_slice_timer(cfqd);
3345 }
Jens Axboecaaa5f92006-06-16 11:23:00 +02003346 }
Jens Axboe6d048f52007-04-25 12:44:27 +02003347
Jens Axboe5ad531d2009-07-03 12:57:48 +02003348 if (!rq_in_driver(cfqd))
Jens Axboe23e018a2009-10-05 08:52:35 +02003349 cfq_schedule_dispatch(cfqd);
Linus Torvalds1da177e2005-04-16 15:20:36 -07003350}
3351
Jens Axboe22e2c502005-06-27 10:55:12 +02003352/*
3353 * we temporarily boost lower priority queues if they are holding fs exclusive
3354 * resources. they are boosted to normal prio (CLASS_BE/4)
3355 */
3356static void cfq_prio_boost(struct cfq_queue *cfqq)
Linus Torvalds1da177e2005-04-16 15:20:36 -07003357{
Jens Axboe22e2c502005-06-27 10:55:12 +02003358 if (has_fs_excl()) {
3359 /*
3360 * boost idle prio on transactions that would lock out other
3361 * users of the filesystem
3362 */
3363 if (cfq_class_idle(cfqq))
3364 cfqq->ioprio_class = IOPRIO_CLASS_BE;
3365 if (cfqq->ioprio > IOPRIO_NORM)
3366 cfqq->ioprio = IOPRIO_NORM;
3367 } else {
3368 /*
Corrado Zoccolodddb7452009-11-02 10:40:37 +01003369 * unboost the queue (if needed)
Jens Axboe22e2c502005-06-27 10:55:12 +02003370 */
Corrado Zoccolodddb7452009-11-02 10:40:37 +01003371 cfqq->ioprio_class = cfqq->org_ioprio_class;
3372 cfqq->ioprio = cfqq->org_ioprio;
Linus Torvalds1da177e2005-04-16 15:20:36 -07003373 }
Jens Axboe22e2c502005-06-27 10:55:12 +02003374}
3375
Jens Axboe89850f72006-07-22 16:48:31 +02003376static inline int __cfq_may_queue(struct cfq_queue *cfqq)
Jens Axboe22e2c502005-06-27 10:55:12 +02003377{
Jens Axboe1b379d82009-08-11 08:26:11 +02003378 if (cfq_cfqq_wait_request(cfqq) && !cfq_cfqq_must_alloc_slice(cfqq)) {
Jens Axboe3b181522005-06-27 10:56:24 +02003379 cfq_mark_cfqq_must_alloc_slice(cfqq);
Jens Axboe22e2c502005-06-27 10:55:12 +02003380 return ELV_MQUEUE_MUST;
Jens Axboe3b181522005-06-27 10:56:24 +02003381 }
Jens Axboe22e2c502005-06-27 10:55:12 +02003382
3383 return ELV_MQUEUE_MAY;
Jens Axboe22e2c502005-06-27 10:55:12 +02003384}
3385
Jens Axboe165125e2007-07-24 09:28:11 +02003386static int cfq_may_queue(struct request_queue *q, int rw)
Jens Axboe22e2c502005-06-27 10:55:12 +02003387{
3388 struct cfq_data *cfqd = q->elevator->elevator_data;
3389 struct task_struct *tsk = current;
Vasily Tarasov91fac312007-04-25 12:29:51 +02003390 struct cfq_io_context *cic;
Jens Axboe22e2c502005-06-27 10:55:12 +02003391 struct cfq_queue *cfqq;
3392
3393 /*
3394 * don't force setup of a queue from here, as a call to may_queue
3395 * does not necessarily imply that a request actually will be queued.
3396 * so just lookup a possibly existing queue, or return 'may queue'
3397 * if that fails
3398 */
Jens Axboe4ac845a2008-01-24 08:44:49 +01003399 cic = cfq_cic_lookup(cfqd, tsk->io_context);
Vasily Tarasov91fac312007-04-25 12:29:51 +02003400 if (!cic)
3401 return ELV_MQUEUE_MAY;
3402
Jens Axboeb0b78f82009-04-08 10:56:08 +02003403 cfqq = cic_to_cfqq(cic, rw_is_sync(rw));
Jens Axboe22e2c502005-06-27 10:55:12 +02003404 if (cfqq) {
Jens Axboefd0928d2008-01-24 08:52:45 +01003405 cfq_init_prio_data(cfqq, cic->ioc);
Jens Axboe22e2c502005-06-27 10:55:12 +02003406 cfq_prio_boost(cfqq);
3407
Jens Axboe89850f72006-07-22 16:48:31 +02003408 return __cfq_may_queue(cfqq);
Jens Axboe22e2c502005-06-27 10:55:12 +02003409 }
3410
3411 return ELV_MQUEUE_MAY;
Linus Torvalds1da177e2005-04-16 15:20:36 -07003412}
3413
Linus Torvalds1da177e2005-04-16 15:20:36 -07003414/*
3415 * queue lock held here
3416 */
Jens Axboebb37b942006-12-01 10:42:33 +01003417static void cfq_put_request(struct request *rq)
Linus Torvalds1da177e2005-04-16 15:20:36 -07003418{
Jens Axboe5e705372006-07-13 12:39:25 +02003419 struct cfq_queue *cfqq = RQ_CFQQ(rq);
Linus Torvalds1da177e2005-04-16 15:20:36 -07003420
Jens Axboe5e705372006-07-13 12:39:25 +02003421 if (cfqq) {
Jens Axboe22e2c502005-06-27 10:55:12 +02003422 const int rw = rq_data_dir(rq);
Linus Torvalds1da177e2005-04-16 15:20:36 -07003423
Jens Axboe22e2c502005-06-27 10:55:12 +02003424 BUG_ON(!cfqq->allocated[rw]);
3425 cfqq->allocated[rw]--;
Linus Torvalds1da177e2005-04-16 15:20:36 -07003426
Jens Axboe5e705372006-07-13 12:39:25 +02003427 put_io_context(RQ_CIC(rq)->ioc);
Linus Torvalds1da177e2005-04-16 15:20:36 -07003428
Linus Torvalds1da177e2005-04-16 15:20:36 -07003429 rq->elevator_private = NULL;
Jens Axboe5e705372006-07-13 12:39:25 +02003430 rq->elevator_private2 = NULL;
Linus Torvalds1da177e2005-04-16 15:20:36 -07003431
Linus Torvalds1da177e2005-04-16 15:20:36 -07003432 cfq_put_queue(cfqq);
3433 }
3434}
3435
Jeff Moyerdf5fe3e2009-10-23 17:14:50 -04003436static struct cfq_queue *
3437cfq_merge_cfqqs(struct cfq_data *cfqd, struct cfq_io_context *cic,
3438 struct cfq_queue *cfqq)
3439{
3440 cfq_log_cfqq(cfqd, cfqq, "merging with queue %p", cfqq->new_cfqq);
3441 cic_set_cfqq(cic, cfqq->new_cfqq, 1);
Jeff Moyerb3b6d042009-10-23 17:14:51 -04003442 cfq_mark_cfqq_coop(cfqq->new_cfqq);
Jeff Moyerdf5fe3e2009-10-23 17:14:50 -04003443 cfq_put_queue(cfqq);
3444 return cic_to_cfqq(cic, 1);
3445}
3446
Jeff Moyere6c5bc72009-10-23 17:14:52 -04003447/*
3448 * Returns NULL if a new cfqq should be allocated, or the old cfqq if this
3449 * was the last process referring to said cfqq.
3450 */
3451static struct cfq_queue *
3452split_cfqq(struct cfq_io_context *cic, struct cfq_queue *cfqq)
3453{
3454 if (cfqq_process_refs(cfqq) == 1) {
Jeff Moyere6c5bc72009-10-23 17:14:52 -04003455 cfqq->pid = current->pid;
3456 cfq_clear_cfqq_coop(cfqq);
Shaohua Liae54abe2010-02-05 13:11:45 +01003457 cfq_clear_cfqq_split_coop(cfqq);
Jeff Moyere6c5bc72009-10-23 17:14:52 -04003458 return cfqq;
3459 }
3460
3461 cic_set_cfqq(cic, NULL, 1);
3462 cfq_put_queue(cfqq);
3463 return NULL;
3464}
Linus Torvalds1da177e2005-04-16 15:20:36 -07003465/*
Jens Axboe22e2c502005-06-27 10:55:12 +02003466 * Allocate cfq data structures associated with this request.
Linus Torvalds1da177e2005-04-16 15:20:36 -07003467 */
Jens Axboe22e2c502005-06-27 10:55:12 +02003468static int
Jens Axboe165125e2007-07-24 09:28:11 +02003469cfq_set_request(struct request_queue *q, struct request *rq, gfp_t gfp_mask)
Linus Torvalds1da177e2005-04-16 15:20:36 -07003470{
3471 struct cfq_data *cfqd = q->elevator->elevator_data;
3472 struct cfq_io_context *cic;
3473 const int rw = rq_data_dir(rq);
Jens Axboea6151c32009-10-07 20:02:57 +02003474 const bool is_sync = rq_is_sync(rq);
Jens Axboe22e2c502005-06-27 10:55:12 +02003475 struct cfq_queue *cfqq;
Linus Torvalds1da177e2005-04-16 15:20:36 -07003476 unsigned long flags;
3477
3478 might_sleep_if(gfp_mask & __GFP_WAIT);
3479
Jens Axboee2d74ac2006-03-28 08:59:01 +02003480 cic = cfq_get_io_context(cfqd, gfp_mask);
Jens Axboe22e2c502005-06-27 10:55:12 +02003481
Linus Torvalds1da177e2005-04-16 15:20:36 -07003482 spin_lock_irqsave(q->queue_lock, flags);
3483
Jens Axboe22e2c502005-06-27 10:55:12 +02003484 if (!cic)
3485 goto queue_fail;
Linus Torvalds1da177e2005-04-16 15:20:36 -07003486
Jeff Moyere6c5bc72009-10-23 17:14:52 -04003487new_queue:
Vasily Tarasov91fac312007-04-25 12:29:51 +02003488 cfqq = cic_to_cfqq(cic, is_sync);
Vivek Goyal32f2e802009-07-09 22:13:16 +02003489 if (!cfqq || cfqq == &cfqd->oom_cfqq) {
Jens Axboefd0928d2008-01-24 08:52:45 +01003490 cfqq = cfq_get_queue(cfqd, is_sync, cic->ioc, gfp_mask);
Vasily Tarasov91fac312007-04-25 12:29:51 +02003491 cic_set_cfqq(cic, cfqq, is_sync);
Jeff Moyerdf5fe3e2009-10-23 17:14:50 -04003492 } else {
3493 /*
Jeff Moyere6c5bc72009-10-23 17:14:52 -04003494 * If the queue was seeky for too long, break it apart.
3495 */
Shaohua Liae54abe2010-02-05 13:11:45 +01003496 if (cfq_cfqq_coop(cfqq) && cfq_cfqq_split_coop(cfqq)) {
Jeff Moyere6c5bc72009-10-23 17:14:52 -04003497 cfq_log_cfqq(cfqd, cfqq, "breaking apart cfqq");
3498 cfqq = split_cfqq(cic, cfqq);
3499 if (!cfqq)
3500 goto new_queue;
3501 }
3502
3503 /*
Jeff Moyerdf5fe3e2009-10-23 17:14:50 -04003504 * Check to see if this queue is scheduled to merge with
3505 * another, closely cooperating queue. The merging of
3506 * queues happens here as it must be done in process context.
3507 * The reference on new_cfqq was taken in merge_cfqqs.
3508 */
3509 if (cfqq->new_cfqq)
3510 cfqq = cfq_merge_cfqqs(cfqd, cic, cfqq);
Vasily Tarasov91fac312007-04-25 12:29:51 +02003511 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07003512
3513 cfqq->allocated[rw]++;
Jens Axboe22e2c502005-06-27 10:55:12 +02003514 atomic_inc(&cfqq->ref);
Jens Axboe5e705372006-07-13 12:39:25 +02003515
Linus Torvalds1da177e2005-04-16 15:20:36 -07003516 spin_unlock_irqrestore(q->queue_lock, flags);
3517
Jens Axboe5e705372006-07-13 12:39:25 +02003518 rq->elevator_private = cic;
3519 rq->elevator_private2 = cfqq;
3520 return 0;
Jens Axboe3b181522005-06-27 10:56:24 +02003521
Jens Axboe22e2c502005-06-27 10:55:12 +02003522queue_fail:
3523 if (cic)
3524 put_io_context(cic->ioc);
Jens Axboe89850f72006-07-22 16:48:31 +02003525
Jens Axboe23e018a2009-10-05 08:52:35 +02003526 cfq_schedule_dispatch(cfqd);
Linus Torvalds1da177e2005-04-16 15:20:36 -07003527 spin_unlock_irqrestore(q->queue_lock, flags);
Jens Axboe7b679132008-05-30 12:23:07 +02003528 cfq_log(cfqd, "set_request fail");
Linus Torvalds1da177e2005-04-16 15:20:36 -07003529 return 1;
3530}
3531
David Howells65f27f32006-11-22 14:55:48 +00003532static void cfq_kick_queue(struct work_struct *work)
Jens Axboe22e2c502005-06-27 10:55:12 +02003533{
David Howells65f27f32006-11-22 14:55:48 +00003534 struct cfq_data *cfqd =
Jens Axboe23e018a2009-10-05 08:52:35 +02003535 container_of(work, struct cfq_data, unplug_work);
Jens Axboe165125e2007-07-24 09:28:11 +02003536 struct request_queue *q = cfqd->queue;
Jens Axboe22e2c502005-06-27 10:55:12 +02003537
Jens Axboe40bb54d2009-04-15 12:11:10 +02003538 spin_lock_irq(q->queue_lock);
Tejun Heoa7f55792009-04-23 11:05:17 +09003539 __blk_run_queue(cfqd->queue);
Jens Axboe40bb54d2009-04-15 12:11:10 +02003540 spin_unlock_irq(q->queue_lock);
Jens Axboe22e2c502005-06-27 10:55:12 +02003541}
3542
3543/*
3544 * Timer running if the active_queue is currently idling inside its time slice
3545 */
3546static void cfq_idle_slice_timer(unsigned long data)
3547{
3548 struct cfq_data *cfqd = (struct cfq_data *) data;
3549 struct cfq_queue *cfqq;
3550 unsigned long flags;
Jens Axboe3c6bd2f2007-01-19 12:06:33 +11003551 int timed_out = 1;
Jens Axboe22e2c502005-06-27 10:55:12 +02003552
Jens Axboe7b679132008-05-30 12:23:07 +02003553 cfq_log(cfqd, "idle timer fired");
3554
Jens Axboe22e2c502005-06-27 10:55:12 +02003555 spin_lock_irqsave(cfqd->queue->queue_lock, flags);
3556
Jens Axboefe094d92008-01-31 13:08:54 +01003557 cfqq = cfqd->active_queue;
3558 if (cfqq) {
Jens Axboe3c6bd2f2007-01-19 12:06:33 +11003559 timed_out = 0;
3560
Jens Axboe22e2c502005-06-27 10:55:12 +02003561 /*
Jens Axboeb0291952009-04-07 11:38:31 +02003562 * We saw a request before the queue expired, let it through
3563 */
3564 if (cfq_cfqq_must_dispatch(cfqq))
3565 goto out_kick;
3566
3567 /*
Jens Axboe22e2c502005-06-27 10:55:12 +02003568 * expired
3569 */
Jens Axboe44f7c162007-01-19 11:51:58 +11003570 if (cfq_slice_used(cfqq))
Jens Axboe22e2c502005-06-27 10:55:12 +02003571 goto expire;
3572
3573 /*
3574 * only expire and reinvoke request handler, if there are
3575 * other queues with pending requests
3576 */
Jens Axboecaaa5f92006-06-16 11:23:00 +02003577 if (!cfqd->busy_queues)
Jens Axboe22e2c502005-06-27 10:55:12 +02003578 goto out_cont;
Jens Axboe22e2c502005-06-27 10:55:12 +02003579
3580 /*
3581 * not expired and it has a request pending, let it dispatch
3582 */
Jens Axboe75e50982009-04-07 08:56:14 +02003583 if (!RB_EMPTY_ROOT(&cfqq->sort_list))
Jens Axboe22e2c502005-06-27 10:55:12 +02003584 goto out_kick;
Corrado Zoccolo76280af2009-11-26 10:02:58 +01003585
3586 /*
3587 * Queue depth flag is reset only when the idle didn't succeed
3588 */
3589 cfq_clear_cfqq_deep(cfqq);
Jens Axboe22e2c502005-06-27 10:55:12 +02003590 }
3591expire:
Jens Axboe6084cdd2007-04-23 08:25:00 +02003592 cfq_slice_expired(cfqd, timed_out);
Jens Axboe22e2c502005-06-27 10:55:12 +02003593out_kick:
Jens Axboe23e018a2009-10-05 08:52:35 +02003594 cfq_schedule_dispatch(cfqd);
Jens Axboe22e2c502005-06-27 10:55:12 +02003595out_cont:
3596 spin_unlock_irqrestore(cfqd->queue->queue_lock, flags);
3597}
3598
Jens Axboe3b181522005-06-27 10:56:24 +02003599static void cfq_shutdown_timer_wq(struct cfq_data *cfqd)
3600{
3601 del_timer_sync(&cfqd->idle_slice_timer);
Jens Axboe23e018a2009-10-05 08:52:35 +02003602 cancel_work_sync(&cfqd->unplug_work);
Jens Axboe3b181522005-06-27 10:56:24 +02003603}
Jens Axboe22e2c502005-06-27 10:55:12 +02003604
Vasily Tarasovc2dea2d2007-07-20 10:06:38 +02003605static void cfq_put_async_queues(struct cfq_data *cfqd)
3606{
3607 int i;
3608
3609 for (i = 0; i < IOPRIO_BE_NR; i++) {
3610 if (cfqd->async_cfqq[0][i])
3611 cfq_put_queue(cfqd->async_cfqq[0][i]);
3612 if (cfqd->async_cfqq[1][i])
3613 cfq_put_queue(cfqd->async_cfqq[1][i]);
Vasily Tarasovc2dea2d2007-07-20 10:06:38 +02003614 }
Oleg Nesterov2389d1e2007-11-05 08:58:05 +01003615
3616 if (cfqd->async_idle_cfqq)
3617 cfq_put_queue(cfqd->async_idle_cfqq);
Vasily Tarasovc2dea2d2007-07-20 10:06:38 +02003618}
3619
Jens Axboebb729bc2009-12-06 09:54:19 +01003620static void cfq_cfqd_free(struct rcu_head *head)
3621{
3622 kfree(container_of(head, struct cfq_data, rcu));
3623}
3624
Jens Axboeb374d182008-10-31 10:05:07 +01003625static void cfq_exit_queue(struct elevator_queue *e)
Linus Torvalds1da177e2005-04-16 15:20:36 -07003626{
Jens Axboe22e2c502005-06-27 10:55:12 +02003627 struct cfq_data *cfqd = e->elevator_data;
Jens Axboe165125e2007-07-24 09:28:11 +02003628 struct request_queue *q = cfqd->queue;
Jens Axboe22e2c502005-06-27 10:55:12 +02003629
Jens Axboe3b181522005-06-27 10:56:24 +02003630 cfq_shutdown_timer_wq(cfqd);
Jens Axboee2d74ac2006-03-28 08:59:01 +02003631
Al Virod9ff4182006-03-18 13:51:22 -05003632 spin_lock_irq(q->queue_lock);
Jens Axboee2d74ac2006-03-28 08:59:01 +02003633
Al Virod9ff4182006-03-18 13:51:22 -05003634 if (cfqd->active_queue)
Jens Axboe6084cdd2007-04-23 08:25:00 +02003635 __cfq_slice_expired(cfqd, cfqd->active_queue, 0);
Jens Axboee2d74ac2006-03-28 08:59:01 +02003636
3637 while (!list_empty(&cfqd->cic_list)) {
Al Virod9ff4182006-03-18 13:51:22 -05003638 struct cfq_io_context *cic = list_entry(cfqd->cic_list.next,
3639 struct cfq_io_context,
3640 queue_list);
Jens Axboe89850f72006-07-22 16:48:31 +02003641
3642 __cfq_exit_single_io_context(cfqd, cic);
Al Virod9ff4182006-03-18 13:51:22 -05003643 }
Jens Axboee2d74ac2006-03-28 08:59:01 +02003644
Vasily Tarasovc2dea2d2007-07-20 10:06:38 +02003645 cfq_put_async_queues(cfqd);
Vivek Goyalb1c35762009-12-03 12:59:47 -05003646 cfq_release_cfq_groups(cfqd);
3647 blkiocg_del_blkio_group(&cfqd->root_group.blkg);
Jens Axboe15c31be2007-07-10 13:43:25 +02003648
Al Virod9ff4182006-03-18 13:51:22 -05003649 spin_unlock_irq(q->queue_lock);
Al Viroa90d7422006-03-18 12:05:37 -05003650
3651 cfq_shutdown_timer_wq(cfqd);
3652
Vivek Goyalb1c35762009-12-03 12:59:47 -05003653 /* Wait for cfqg->blkg->key accessors to exit their grace periods. */
Jens Axboebb729bc2009-12-06 09:54:19 +01003654 call_rcu(&cfqd->rcu, cfq_cfqd_free);
Linus Torvalds1da177e2005-04-16 15:20:36 -07003655}
3656
Jens Axboe165125e2007-07-24 09:28:11 +02003657static void *cfq_init_queue(struct request_queue *q)
Linus Torvalds1da177e2005-04-16 15:20:36 -07003658{
3659 struct cfq_data *cfqd;
Corrado Zoccolo718eee02009-10-26 22:45:29 +01003660 int i, j;
Vivek Goyalcdb16e82009-12-03 12:59:38 -05003661 struct cfq_group *cfqg;
Vivek Goyal615f0252009-12-03 12:59:39 -05003662 struct cfq_rb_root *st;
Linus Torvalds1da177e2005-04-16 15:20:36 -07003663
Christoph Lameter94f60302007-07-17 04:03:29 -07003664 cfqd = kmalloc_node(sizeof(*cfqd), GFP_KERNEL | __GFP_ZERO, q->node);
Linus Torvalds1da177e2005-04-16 15:20:36 -07003665 if (!cfqd)
Jens Axboebc1c1162006-06-08 08:49:06 +02003666 return NULL;
Linus Torvalds1da177e2005-04-16 15:20:36 -07003667
Vivek Goyal1fa8f6d2009-12-03 12:59:41 -05003668 /* Init root service tree */
3669 cfqd->grp_service_tree = CFQ_RB_ROOT;
3670
Vivek Goyalcdb16e82009-12-03 12:59:38 -05003671 /* Init root group */
3672 cfqg = &cfqd->root_group;
Vivek Goyal615f0252009-12-03 12:59:39 -05003673 for_each_cfqg_st(cfqg, i, j, st)
3674 *st = CFQ_RB_ROOT;
Vivek Goyal1fa8f6d2009-12-03 12:59:41 -05003675 RB_CLEAR_NODE(&cfqg->rb_node);
Jens Axboe26a2ac02009-04-23 12:13:27 +02003676
Vivek Goyal25bc6b02009-12-03 12:59:43 -05003677 /* Give preference to root group over other groups */
3678 cfqg->weight = 2*BLKIO_WEIGHT_DEFAULT;
3679
Vivek Goyal25fb5162009-12-03 12:59:46 -05003680#ifdef CONFIG_CFQ_GROUP_IOSCHED
Vivek Goyalb1c35762009-12-03 12:59:47 -05003681 /*
3682 * Take a reference to root group which we never drop. This is just
3683 * to make sure that cfq_put_cfqg() does not try to kfree root group
3684 */
3685 atomic_set(&cfqg->ref, 1);
Vivek Goyal22084192009-12-03 12:59:49 -05003686 blkiocg_add_blkio_group(&blkio_root_cgroup, &cfqg->blkg, (void *)cfqd,
3687 0);
Vivek Goyal25fb5162009-12-03 12:59:46 -05003688#endif
Jens Axboe26a2ac02009-04-23 12:13:27 +02003689 /*
3690 * Not strictly needed (since RB_ROOT just clears the node and we
3691 * zeroed cfqd on alloc), but better be safe in case someone decides
3692 * to add magic to the rb code
3693 */
3694 for (i = 0; i < CFQ_PRIO_LISTS; i++)
3695 cfqd->prio_trees[i] = RB_ROOT;
3696
Jens Axboe6118b702009-06-30 09:34:12 +02003697 /*
3698 * Our fallback cfqq if cfq_find_alloc_queue() runs into OOM issues.
3699 * Grab a permanent reference to it, so that the normal code flow
3700 * will not attempt to free it.
3701 */
3702 cfq_init_cfqq(cfqd, &cfqd->oom_cfqq, 1, 0);
3703 atomic_inc(&cfqd->oom_cfqq.ref);
Vivek Goyalcdb16e82009-12-03 12:59:38 -05003704 cfq_link_cfqq_cfqg(&cfqd->oom_cfqq, &cfqd->root_group);
Jens Axboe6118b702009-06-30 09:34:12 +02003705
Al Virod9ff4182006-03-18 13:51:22 -05003706 INIT_LIST_HEAD(&cfqd->cic_list);
Linus Torvalds1da177e2005-04-16 15:20:36 -07003707
Linus Torvalds1da177e2005-04-16 15:20:36 -07003708 cfqd->queue = q;
Linus Torvalds1da177e2005-04-16 15:20:36 -07003709
Jens Axboe22e2c502005-06-27 10:55:12 +02003710 init_timer(&cfqd->idle_slice_timer);
3711 cfqd->idle_slice_timer.function = cfq_idle_slice_timer;
3712 cfqd->idle_slice_timer.data = (unsigned long) cfqd;
3713
Jens Axboe23e018a2009-10-05 08:52:35 +02003714 INIT_WORK(&cfqd->unplug_work, cfq_kick_queue);
Jens Axboe22e2c502005-06-27 10:55:12 +02003715
Linus Torvalds1da177e2005-04-16 15:20:36 -07003716 cfqd->cfq_quantum = cfq_quantum;
Jens Axboe22e2c502005-06-27 10:55:12 +02003717 cfqd->cfq_fifo_expire[0] = cfq_fifo_expire[0];
3718 cfqd->cfq_fifo_expire[1] = cfq_fifo_expire[1];
Linus Torvalds1da177e2005-04-16 15:20:36 -07003719 cfqd->cfq_back_max = cfq_back_max;
3720 cfqd->cfq_back_penalty = cfq_back_penalty;
Jens Axboe22e2c502005-06-27 10:55:12 +02003721 cfqd->cfq_slice[0] = cfq_slice_async;
3722 cfqd->cfq_slice[1] = cfq_slice_sync;
3723 cfqd->cfq_slice_async_rq = cfq_slice_async_rq;
3724 cfqd->cfq_slice_idle = cfq_slice_idle;
Jens Axboe963b72f2009-10-03 19:42:18 +02003725 cfqd->cfq_latency = 1;
Vivek Goyalae30c282009-12-03 12:59:55 -05003726 cfqd->cfq_group_isolation = 0;
Corrado Zoccoloe459dd02009-11-26 10:02:57 +01003727 cfqd->hw_tag = -1;
Corrado Zoccoloedc71132009-12-09 20:56:04 +01003728 /*
3729 * we optimistically start assuming sync ops weren't delayed in last
3730 * second, in order to have larger depth for async operations.
3731 */
Corrado Zoccolo573412b2009-12-06 11:48:52 +01003732 cfqd->last_delayed_sync = jiffies - HZ;
Jens Axboebb729bc2009-12-06 09:54:19 +01003733 INIT_RCU_HEAD(&cfqd->rcu);
Jens Axboebc1c1162006-06-08 08:49:06 +02003734 return cfqd;
Linus Torvalds1da177e2005-04-16 15:20:36 -07003735}
3736
3737static void cfq_slab_kill(void)
3738{
Jens Axboed6de8be2008-05-28 14:46:59 +02003739 /*
3740 * Caller already ensured that pending RCU callbacks are completed,
3741 * so we should have no busy allocations at this point.
3742 */
Linus Torvalds1da177e2005-04-16 15:20:36 -07003743 if (cfq_pool)
3744 kmem_cache_destroy(cfq_pool);
3745 if (cfq_ioc_pool)
3746 kmem_cache_destroy(cfq_ioc_pool);
3747}
3748
3749static int __init cfq_slab_setup(void)
3750{
Christoph Lameter0a31bd52007-05-06 14:49:57 -07003751 cfq_pool = KMEM_CACHE(cfq_queue, 0);
Linus Torvalds1da177e2005-04-16 15:20:36 -07003752 if (!cfq_pool)
3753 goto fail;
3754
Fabio Checconi34e6bbf2008-04-02 14:31:02 +02003755 cfq_ioc_pool = KMEM_CACHE(cfq_io_context, 0);
Linus Torvalds1da177e2005-04-16 15:20:36 -07003756 if (!cfq_ioc_pool)
3757 goto fail;
3758
3759 return 0;
3760fail:
3761 cfq_slab_kill();
3762 return -ENOMEM;
3763}
3764
Linus Torvalds1da177e2005-04-16 15:20:36 -07003765/*
3766 * sysfs parts below -->
3767 */
Linus Torvalds1da177e2005-04-16 15:20:36 -07003768static ssize_t
3769cfq_var_show(unsigned int var, char *page)
3770{
3771 return sprintf(page, "%d\n", var);
3772}
3773
3774static ssize_t
3775cfq_var_store(unsigned int *var, const char *page, size_t count)
3776{
3777 char *p = (char *) page;
3778
3779 *var = simple_strtoul(p, &p, 10);
3780 return count;
3781}
3782
Linus Torvalds1da177e2005-04-16 15:20:36 -07003783#define SHOW_FUNCTION(__FUNC, __VAR, __CONV) \
Jens Axboeb374d182008-10-31 10:05:07 +01003784static ssize_t __FUNC(struct elevator_queue *e, char *page) \
Linus Torvalds1da177e2005-04-16 15:20:36 -07003785{ \
Al Viro3d1ab402006-03-18 18:35:43 -05003786 struct cfq_data *cfqd = e->elevator_data; \
Linus Torvalds1da177e2005-04-16 15:20:36 -07003787 unsigned int __data = __VAR; \
3788 if (__CONV) \
3789 __data = jiffies_to_msecs(__data); \
3790 return cfq_var_show(__data, (page)); \
3791}
3792SHOW_FUNCTION(cfq_quantum_show, cfqd->cfq_quantum, 0);
Jens Axboe22e2c502005-06-27 10:55:12 +02003793SHOW_FUNCTION(cfq_fifo_expire_sync_show, cfqd->cfq_fifo_expire[1], 1);
3794SHOW_FUNCTION(cfq_fifo_expire_async_show, cfqd->cfq_fifo_expire[0], 1);
Al Viroe572ec72006-03-18 22:27:18 -05003795SHOW_FUNCTION(cfq_back_seek_max_show, cfqd->cfq_back_max, 0);
3796SHOW_FUNCTION(cfq_back_seek_penalty_show, cfqd->cfq_back_penalty, 0);
Jens Axboe22e2c502005-06-27 10:55:12 +02003797SHOW_FUNCTION(cfq_slice_idle_show, cfqd->cfq_slice_idle, 1);
3798SHOW_FUNCTION(cfq_slice_sync_show, cfqd->cfq_slice[1], 1);
3799SHOW_FUNCTION(cfq_slice_async_show, cfqd->cfq_slice[0], 1);
3800SHOW_FUNCTION(cfq_slice_async_rq_show, cfqd->cfq_slice_async_rq, 0);
Jens Axboe963b72f2009-10-03 19:42:18 +02003801SHOW_FUNCTION(cfq_low_latency_show, cfqd->cfq_latency, 0);
Vivek Goyalae30c282009-12-03 12:59:55 -05003802SHOW_FUNCTION(cfq_group_isolation_show, cfqd->cfq_group_isolation, 0);
Linus Torvalds1da177e2005-04-16 15:20:36 -07003803#undef SHOW_FUNCTION
3804
3805#define STORE_FUNCTION(__FUNC, __PTR, MIN, MAX, __CONV) \
Jens Axboeb374d182008-10-31 10:05:07 +01003806static ssize_t __FUNC(struct elevator_queue *e, const char *page, size_t count) \
Linus Torvalds1da177e2005-04-16 15:20:36 -07003807{ \
Al Viro3d1ab402006-03-18 18:35:43 -05003808 struct cfq_data *cfqd = e->elevator_data; \
Linus Torvalds1da177e2005-04-16 15:20:36 -07003809 unsigned int __data; \
3810 int ret = cfq_var_store(&__data, (page), count); \
3811 if (__data < (MIN)) \
3812 __data = (MIN); \
3813 else if (__data > (MAX)) \
3814 __data = (MAX); \
3815 if (__CONV) \
3816 *(__PTR) = msecs_to_jiffies(__data); \
3817 else \
3818 *(__PTR) = __data; \
3819 return ret; \
3820}
3821STORE_FUNCTION(cfq_quantum_store, &cfqd->cfq_quantum, 1, UINT_MAX, 0);
Jens Axboefe094d92008-01-31 13:08:54 +01003822STORE_FUNCTION(cfq_fifo_expire_sync_store, &cfqd->cfq_fifo_expire[1], 1,
3823 UINT_MAX, 1);
3824STORE_FUNCTION(cfq_fifo_expire_async_store, &cfqd->cfq_fifo_expire[0], 1,
3825 UINT_MAX, 1);
Al Viroe572ec72006-03-18 22:27:18 -05003826STORE_FUNCTION(cfq_back_seek_max_store, &cfqd->cfq_back_max, 0, UINT_MAX, 0);
Jens Axboefe094d92008-01-31 13:08:54 +01003827STORE_FUNCTION(cfq_back_seek_penalty_store, &cfqd->cfq_back_penalty, 1,
3828 UINT_MAX, 0);
Jens Axboe22e2c502005-06-27 10:55:12 +02003829STORE_FUNCTION(cfq_slice_idle_store, &cfqd->cfq_slice_idle, 0, UINT_MAX, 1);
3830STORE_FUNCTION(cfq_slice_sync_store, &cfqd->cfq_slice[1], 1, UINT_MAX, 1);
3831STORE_FUNCTION(cfq_slice_async_store, &cfqd->cfq_slice[0], 1, UINT_MAX, 1);
Jens Axboefe094d92008-01-31 13:08:54 +01003832STORE_FUNCTION(cfq_slice_async_rq_store, &cfqd->cfq_slice_async_rq, 1,
3833 UINT_MAX, 0);
Jens Axboe963b72f2009-10-03 19:42:18 +02003834STORE_FUNCTION(cfq_low_latency_store, &cfqd->cfq_latency, 0, 1, 0);
Vivek Goyalae30c282009-12-03 12:59:55 -05003835STORE_FUNCTION(cfq_group_isolation_store, &cfqd->cfq_group_isolation, 0, 1, 0);
Linus Torvalds1da177e2005-04-16 15:20:36 -07003836#undef STORE_FUNCTION
3837
Al Viroe572ec72006-03-18 22:27:18 -05003838#define CFQ_ATTR(name) \
3839 __ATTR(name, S_IRUGO|S_IWUSR, cfq_##name##_show, cfq_##name##_store)
Jens Axboe3b181522005-06-27 10:56:24 +02003840
Al Viroe572ec72006-03-18 22:27:18 -05003841static struct elv_fs_entry cfq_attrs[] = {
3842 CFQ_ATTR(quantum),
Al Viroe572ec72006-03-18 22:27:18 -05003843 CFQ_ATTR(fifo_expire_sync),
3844 CFQ_ATTR(fifo_expire_async),
3845 CFQ_ATTR(back_seek_max),
3846 CFQ_ATTR(back_seek_penalty),
3847 CFQ_ATTR(slice_sync),
3848 CFQ_ATTR(slice_async),
3849 CFQ_ATTR(slice_async_rq),
3850 CFQ_ATTR(slice_idle),
Jens Axboe963b72f2009-10-03 19:42:18 +02003851 CFQ_ATTR(low_latency),
Vivek Goyalae30c282009-12-03 12:59:55 -05003852 CFQ_ATTR(group_isolation),
Al Viroe572ec72006-03-18 22:27:18 -05003853 __ATTR_NULL
Linus Torvalds1da177e2005-04-16 15:20:36 -07003854};
3855
Linus Torvalds1da177e2005-04-16 15:20:36 -07003856static struct elevator_type iosched_cfq = {
3857 .ops = {
3858 .elevator_merge_fn = cfq_merge,
3859 .elevator_merged_fn = cfq_merged_request,
3860 .elevator_merge_req_fn = cfq_merged_requests,
Jens Axboeda775262006-12-20 11:04:12 +01003861 .elevator_allow_merge_fn = cfq_allow_merge,
Jens Axboeb4878f22005-10-20 16:42:29 +02003862 .elevator_dispatch_fn = cfq_dispatch_requests,
Linus Torvalds1da177e2005-04-16 15:20:36 -07003863 .elevator_add_req_fn = cfq_insert_request,
Jens Axboeb4878f22005-10-20 16:42:29 +02003864 .elevator_activate_req_fn = cfq_activate_request,
Linus Torvalds1da177e2005-04-16 15:20:36 -07003865 .elevator_deactivate_req_fn = cfq_deactivate_request,
3866 .elevator_queue_empty_fn = cfq_queue_empty,
3867 .elevator_completed_req_fn = cfq_completed_request,
Jens Axboe21183b02006-07-13 12:33:14 +02003868 .elevator_former_req_fn = elv_rb_former_request,
3869 .elevator_latter_req_fn = elv_rb_latter_request,
Linus Torvalds1da177e2005-04-16 15:20:36 -07003870 .elevator_set_req_fn = cfq_set_request,
3871 .elevator_put_req_fn = cfq_put_request,
3872 .elevator_may_queue_fn = cfq_may_queue,
3873 .elevator_init_fn = cfq_init_queue,
3874 .elevator_exit_fn = cfq_exit_queue,
Jens Axboefc463792006-08-29 09:05:44 +02003875 .trim = cfq_free_io_context,
Linus Torvalds1da177e2005-04-16 15:20:36 -07003876 },
Al Viro3d1ab402006-03-18 18:35:43 -05003877 .elevator_attrs = cfq_attrs,
Linus Torvalds1da177e2005-04-16 15:20:36 -07003878 .elevator_name = "cfq",
3879 .elevator_owner = THIS_MODULE,
3880};
3881
Vivek Goyal3e252062009-12-04 10:36:42 -05003882#ifdef CONFIG_CFQ_GROUP_IOSCHED
3883static struct blkio_policy_type blkio_policy_cfq = {
3884 .ops = {
3885 .blkio_unlink_group_fn = cfq_unlink_blkio_group,
3886 .blkio_update_group_weight_fn = cfq_update_blkio_group_weight,
3887 },
3888};
3889#else
3890static struct blkio_policy_type blkio_policy_cfq;
3891#endif
3892
Linus Torvalds1da177e2005-04-16 15:20:36 -07003893static int __init cfq_init(void)
3894{
Jens Axboe22e2c502005-06-27 10:55:12 +02003895 /*
3896 * could be 0 on HZ < 1000 setups
3897 */
3898 if (!cfq_slice_async)
3899 cfq_slice_async = 1;
3900 if (!cfq_slice_idle)
3901 cfq_slice_idle = 1;
3902
Linus Torvalds1da177e2005-04-16 15:20:36 -07003903 if (cfq_slab_setup())
3904 return -ENOMEM;
3905
Adrian Bunk2fdd82b2007-12-12 18:51:56 +01003906 elv_register(&iosched_cfq);
Vivek Goyal3e252062009-12-04 10:36:42 -05003907 blkio_policy_register(&blkio_policy_cfq);
Linus Torvalds1da177e2005-04-16 15:20:36 -07003908
Adrian Bunk2fdd82b2007-12-12 18:51:56 +01003909 return 0;
Linus Torvalds1da177e2005-04-16 15:20:36 -07003910}
3911
3912static void __exit cfq_exit(void)
3913{
Peter Zijlstra6e9a4732006-09-30 23:28:10 -07003914 DECLARE_COMPLETION_ONSTACK(all_gone);
Vivek Goyal3e252062009-12-04 10:36:42 -05003915 blkio_policy_unregister(&blkio_policy_cfq);
Linus Torvalds1da177e2005-04-16 15:20:36 -07003916 elv_unregister(&iosched_cfq);
Al Viro334e94d2006-03-18 15:05:53 -05003917 ioc_gone = &all_gone;
OGAWA Hirofumifba82272006-04-18 09:44:06 +02003918 /* ioc_gone's update must be visible before reading ioc_count */
3919 smp_wmb();
Jens Axboed6de8be2008-05-28 14:46:59 +02003920
3921 /*
3922 * this also protects us from entering cfq_slab_kill() with
3923 * pending RCU callbacks
3924 */
Tejun Heo245b2e72009-06-24 15:13:48 +09003925 if (elv_ioc_count_read(cfq_ioc_count))
Jens Axboe9a11b4e2008-05-29 09:32:08 +02003926 wait_for_completion(&all_gone);
Christoph Hellwig83521d32005-10-30 15:01:39 -08003927 cfq_slab_kill();
Linus Torvalds1da177e2005-04-16 15:20:36 -07003928}
3929
3930module_init(cfq_init);
3931module_exit(cfq_exit);
3932
3933MODULE_AUTHOR("Jens Axboe");
3934MODULE_LICENSE("GPL");
3935MODULE_DESCRIPTION("Completely Fair Queueing IO scheduler");