blob: 1e2aff812ee2b278bd831809269c4d6c76234858 [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>
Linus Torvalds1da177e2005-04-16 15:20:36 -070012#include <linux/rbtree.h>
Jens Axboe22e2c502005-06-27 10:55:12 +020013#include <linux/ioprio.h>
Jens Axboe7b679132008-05-30 12:23:07 +020014#include <linux/blktrace_api.h>
Linus Torvalds1da177e2005-04-16 15:20:36 -070015
16/*
17 * tunables
18 */
Jens Axboefe094d92008-01-31 13:08:54 +010019/* max queue in one round of service */
20static const int cfq_quantum = 4;
Arjan van de Ven64100092006-01-06 09:46:02 +010021static const int cfq_fifo_expire[2] = { HZ / 4, HZ / 8 };
Jens Axboefe094d92008-01-31 13:08:54 +010022/* maximum backwards seek, in KiB */
23static const int cfq_back_max = 16 * 1024;
24/* penalty of a backwards seek */
25static const int cfq_back_penalty = 2;
Arjan van de Ven64100092006-01-06 09:46:02 +010026static const int cfq_slice_sync = HZ / 10;
Jens Axboe3b181522005-06-27 10:56:24 +020027static int cfq_slice_async = HZ / 25;
Arjan van de Ven64100092006-01-06 09:46:02 +010028static const int cfq_slice_async_rq = 2;
Jens Axboecaaa5f92006-06-16 11:23:00 +020029static int cfq_slice_idle = HZ / 125;
Jens Axboe22e2c502005-06-27 10:55:12 +020030
Jens Axboed9e76202007-04-20 14:27:50 +020031/*
Jens Axboe08717142008-01-28 11:38:15 +010032 * offset from end of service tree
Jens Axboed9e76202007-04-20 14:27:50 +020033 */
Jens Axboe08717142008-01-28 11:38:15 +010034#define CFQ_IDLE_DELAY (HZ / 5)
Jens Axboed9e76202007-04-20 14:27:50 +020035
36/*
37 * below this threshold, we consider thinktime immediate
38 */
39#define CFQ_MIN_TT (2)
40
Jens Axboe22e2c502005-06-27 10:55:12 +020041#define CFQ_SLICE_SCALE (5)
42
Jens Axboefe094d92008-01-31 13:08:54 +010043#define RQ_CIC(rq) \
44 ((struct cfq_io_context *) (rq)->elevator_private)
Jens Axboe7b679132008-05-30 12:23:07 +020045#define RQ_CFQQ(rq) (struct cfq_queue *) ((rq)->elevator_private2)
Linus Torvalds1da177e2005-04-16 15:20:36 -070046
Christoph Lametere18b8902006-12-06 20:33:20 -080047static struct kmem_cache *cfq_pool;
48static struct kmem_cache *cfq_ioc_pool;
Linus Torvalds1da177e2005-04-16 15:20:36 -070049
Jens Axboe4050cf12006-07-19 05:07:12 +020050static DEFINE_PER_CPU(unsigned long, ioc_count);
Al Viro334e94d2006-03-18 15:05:53 -050051static struct completion *ioc_gone;
Jens Axboe9a11b4e2008-05-29 09:32:08 +020052static DEFINE_SPINLOCK(ioc_gone_lock);
Al Viro334e94d2006-03-18 15:05:53 -050053
Jens Axboe22e2c502005-06-27 10:55:12 +020054#define CFQ_PRIO_LISTS IOPRIO_BE_NR
55#define cfq_class_idle(cfqq) ((cfqq)->ioprio_class == IOPRIO_CLASS_IDLE)
Jens Axboe22e2c502005-06-27 10:55:12 +020056#define cfq_class_rt(cfqq) ((cfqq)->ioprio_class == IOPRIO_CLASS_RT)
57
Jens Axboe3b181522005-06-27 10:56:24 +020058#define ASYNC (0)
59#define SYNC (1)
60
Jens Axboe206dc692006-03-28 13:03:44 +020061#define sample_valid(samples) ((samples) > 80)
62
Jens Axboe22e2c502005-06-27 10:55:12 +020063/*
Jens Axboecc09e292007-04-26 12:53:50 +020064 * Most of our rbtree usage is for sorting with min extraction, so
65 * if we cache the leftmost node we don't have to walk down the tree
66 * to find it. Idea borrowed from Ingo Molnars CFS scheduler. We should
67 * move this into the elevator for the rq sorting as well.
68 */
69struct cfq_rb_root {
70 struct rb_root rb;
71 struct rb_node *left;
72};
73#define CFQ_RB_ROOT (struct cfq_rb_root) { RB_ROOT, NULL, }
74
75/*
Jens Axboe22e2c502005-06-27 10:55:12 +020076 * Per block device queue structure
77 */
Linus Torvalds1da177e2005-04-16 15:20:36 -070078struct cfq_data {
Jens Axboe165125e2007-07-24 09:28:11 +020079 struct request_queue *queue;
Jens Axboe22e2c502005-06-27 10:55:12 +020080
81 /*
82 * rr list of queues with requests and the count of them
83 */
Jens Axboecc09e292007-04-26 12:53:50 +020084 struct cfq_rb_root service_tree;
Jens Axboe22e2c502005-06-27 10:55:12 +020085 unsigned int busy_queues;
86
Jens Axboe22e2c502005-06-27 10:55:12 +020087 int rq_in_driver;
Jens Axboe3ed9a292007-04-23 08:33:33 +020088 int sync_flight;
Jens Axboe25776e32006-06-01 10:12:26 +020089 int hw_tag;
Jens Axboe22e2c502005-06-27 10:55:12 +020090
91 /*
Jens Axboe22e2c502005-06-27 10:55:12 +020092 * idle window management
93 */
94 struct timer_list idle_slice_timer;
95 struct work_struct unplug_work;
96
97 struct cfq_queue *active_queue;
98 struct cfq_io_context *active_cic;
Jens Axboe22e2c502005-06-27 10:55:12 +020099
Vasily Tarasovc2dea2d2007-07-20 10:06:38 +0200100 /*
101 * async queue for each priority case
102 */
103 struct cfq_queue *async_cfqq[2][IOPRIO_BE_NR];
104 struct cfq_queue *async_idle_cfqq;
Jens Axboe15c31be2007-07-10 13:43:25 +0200105
Jens Axboe6d048f52007-04-25 12:44:27 +0200106 sector_t last_position;
Jens Axboe22e2c502005-06-27 10:55:12 +0200107 unsigned long last_end_request;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700108
Linus Torvalds1da177e2005-04-16 15:20:36 -0700109 /*
110 * tunables, see top of file
111 */
112 unsigned int cfq_quantum;
Jens Axboe22e2c502005-06-27 10:55:12 +0200113 unsigned int cfq_fifo_expire[2];
Linus Torvalds1da177e2005-04-16 15:20:36 -0700114 unsigned int cfq_back_penalty;
115 unsigned int cfq_back_max;
Jens Axboe22e2c502005-06-27 10:55:12 +0200116 unsigned int cfq_slice[2];
117 unsigned int cfq_slice_async_rq;
118 unsigned int cfq_slice_idle;
Al Virod9ff4182006-03-18 13:51:22 -0500119
120 struct list_head cic_list;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700121};
122
Jens Axboe22e2c502005-06-27 10:55:12 +0200123/*
124 * Per process-grouping structure
125 */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700126struct cfq_queue {
127 /* reference count */
128 atomic_t ref;
Richard Kennedybe754d22008-05-23 06:52:00 +0200129 /* various state flags, see below */
130 unsigned int flags;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700131 /* parent cfq_data */
132 struct cfq_data *cfqd;
Jens Axboed9e76202007-04-20 14:27:50 +0200133 /* service_tree member */
134 struct rb_node rb_node;
135 /* service_tree key */
136 unsigned long rb_key;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700137 /* sorted list of pending requests */
138 struct rb_root sort_list;
139 /* if fifo isn't expired, next request to serve */
Jens Axboe5e705372006-07-13 12:39:25 +0200140 struct request *next_rq;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700141 /* requests queued in sort_list */
142 int queued[2];
143 /* currently allocated requests */
144 int allocated[2];
145 /* fifo list of requests in sort_list */
Jens Axboe22e2c502005-06-27 10:55:12 +0200146 struct list_head fifo;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700147
Jens Axboe22e2c502005-06-27 10:55:12 +0200148 unsigned long slice_end;
Jens Axboec5b680f2007-01-19 11:56:49 +1100149 long slice_resid;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700150
Richard Kennedybe754d22008-05-23 06:52:00 +0200151 /* pending metadata requests */
152 int meta_pending;
Jens Axboe6d048f52007-04-25 12:44:27 +0200153 /* number of requests that are on the dispatch list or inside driver */
154 int dispatched;
Jens Axboe22e2c502005-06-27 10:55:12 +0200155
156 /* io prio of this group */
157 unsigned short ioprio, org_ioprio;
158 unsigned short ioprio_class, org_ioprio_class;
159
Jens Axboe7b679132008-05-30 12:23:07 +0200160 pid_t pid;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700161};
162
Jens Axboe3b181522005-06-27 10:56:24 +0200163enum cfqq_state_flags {
Jens Axboeb0b8d742007-01-19 11:35:30 +1100164 CFQ_CFQQ_FLAG_on_rr = 0, /* on round-robin busy list */
165 CFQ_CFQQ_FLAG_wait_request, /* waiting for a request */
166 CFQ_CFQQ_FLAG_must_alloc, /* must be allowed rq alloc */
167 CFQ_CFQQ_FLAG_must_alloc_slice, /* per-slice must_alloc flag */
168 CFQ_CFQQ_FLAG_must_dispatch, /* must dispatch, even if expired */
169 CFQ_CFQQ_FLAG_fifo_expire, /* FIFO checked in this slice */
170 CFQ_CFQQ_FLAG_idle_window, /* slice idling enabled */
171 CFQ_CFQQ_FLAG_prio_changed, /* task priority has changed */
172 CFQ_CFQQ_FLAG_queue_new, /* queue never been serviced */
Jens Axboe44f7c162007-01-19 11:51:58 +1100173 CFQ_CFQQ_FLAG_slice_new, /* no requests dispatched in slice */
Vasily Tarasov91fac312007-04-25 12:29:51 +0200174 CFQ_CFQQ_FLAG_sync, /* synchronous queue */
Jens Axboe3b181522005-06-27 10:56:24 +0200175};
176
177#define CFQ_CFQQ_FNS(name) \
178static inline void cfq_mark_cfqq_##name(struct cfq_queue *cfqq) \
179{ \
Jens Axboefe094d92008-01-31 13:08:54 +0100180 (cfqq)->flags |= (1 << CFQ_CFQQ_FLAG_##name); \
Jens Axboe3b181522005-06-27 10:56:24 +0200181} \
182static inline void cfq_clear_cfqq_##name(struct cfq_queue *cfqq) \
183{ \
Jens Axboefe094d92008-01-31 13:08:54 +0100184 (cfqq)->flags &= ~(1 << CFQ_CFQQ_FLAG_##name); \
Jens Axboe3b181522005-06-27 10:56:24 +0200185} \
186static inline int cfq_cfqq_##name(const struct cfq_queue *cfqq) \
187{ \
Jens Axboefe094d92008-01-31 13:08:54 +0100188 return ((cfqq)->flags & (1 << CFQ_CFQQ_FLAG_##name)) != 0; \
Jens Axboe3b181522005-06-27 10:56:24 +0200189}
190
191CFQ_CFQQ_FNS(on_rr);
192CFQ_CFQQ_FNS(wait_request);
193CFQ_CFQQ_FNS(must_alloc);
194CFQ_CFQQ_FNS(must_alloc_slice);
195CFQ_CFQQ_FNS(must_dispatch);
196CFQ_CFQQ_FNS(fifo_expire);
197CFQ_CFQQ_FNS(idle_window);
198CFQ_CFQQ_FNS(prio_changed);
Jens Axboe53b03742006-07-28 09:48:51 +0200199CFQ_CFQQ_FNS(queue_new);
Jens Axboe44f7c162007-01-19 11:51:58 +1100200CFQ_CFQQ_FNS(slice_new);
Vasily Tarasov91fac312007-04-25 12:29:51 +0200201CFQ_CFQQ_FNS(sync);
Jens Axboe3b181522005-06-27 10:56:24 +0200202#undef CFQ_CFQQ_FNS
203
Jens Axboe7b679132008-05-30 12:23:07 +0200204#define cfq_log_cfqq(cfqd, cfqq, fmt, args...) \
205 blk_add_trace_msg((cfqd)->queue, "cfq%d " fmt, (cfqq)->pid, ##args)
206#define cfq_log(cfqd, fmt, args...) \
207 blk_add_trace_msg((cfqd)->queue, "cfq " fmt, ##args)
208
Jens Axboe165125e2007-07-24 09:28:11 +0200209static void cfq_dispatch_insert(struct request_queue *, struct request *);
Vasily Tarasov91fac312007-04-25 12:29:51 +0200210static struct cfq_queue *cfq_get_queue(struct cfq_data *, int,
Jens Axboefd0928d2008-01-24 08:52:45 +0100211 struct io_context *, gfp_t);
Jens Axboe4ac845a2008-01-24 08:44:49 +0100212static struct cfq_io_context *cfq_cic_lookup(struct cfq_data *,
Vasily Tarasov91fac312007-04-25 12:29:51 +0200213 struct io_context *);
214
215static inline struct cfq_queue *cic_to_cfqq(struct cfq_io_context *cic,
216 int is_sync)
217{
218 return cic->cfqq[!!is_sync];
219}
220
221static inline void cic_set_cfqq(struct cfq_io_context *cic,
222 struct cfq_queue *cfqq, int is_sync)
223{
224 cic->cfqq[!!is_sync] = cfqq;
225}
226
227/*
228 * We regard a request as SYNC, if it's either a read or has the SYNC bit
229 * set (in which case it could also be direct WRITE).
230 */
231static inline int cfq_bio_sync(struct bio *bio)
232{
233 if (bio_data_dir(bio) == READ || bio_sync(bio))
234 return 1;
235
236 return 0;
237}
Linus Torvalds1da177e2005-04-16 15:20:36 -0700238
Linus Torvalds1da177e2005-04-16 15:20:36 -0700239/*
Andrew Morton99f95e52005-06-27 20:14:05 -0700240 * scheduler run of queue, if there are requests pending and no one in the
241 * driver that will restart queueing
242 */
243static inline void cfq_schedule_dispatch(struct cfq_data *cfqd)
244{
Jens Axboe7b679132008-05-30 12:23:07 +0200245 if (cfqd->busy_queues) {
246 cfq_log(cfqd, "schedule dispatch");
Andrew Morton99f95e52005-06-27 20:14:05 -0700247 kblockd_schedule_work(&cfqd->unplug_work);
Jens Axboe7b679132008-05-30 12:23:07 +0200248 }
Andrew Morton99f95e52005-06-27 20:14:05 -0700249}
250
Jens Axboe165125e2007-07-24 09:28:11 +0200251static int cfq_queue_empty(struct request_queue *q)
Andrew Morton99f95e52005-06-27 20:14:05 -0700252{
253 struct cfq_data *cfqd = q->elevator->elevator_data;
254
Jens Axboeb4878f22005-10-20 16:42:29 +0200255 return !cfqd->busy_queues;
Andrew Morton99f95e52005-06-27 20:14:05 -0700256}
257
Linus Torvalds1da177e2005-04-16 15:20:36 -0700258/*
Jens Axboe44f7c162007-01-19 11:51:58 +1100259 * Scale schedule slice based on io priority. Use the sync time slice only
260 * if a queue is marked sync and has sync io queued. A sync queue with async
261 * io only, should not get full sync slice length.
262 */
Jens Axboed9e76202007-04-20 14:27:50 +0200263static inline int cfq_prio_slice(struct cfq_data *cfqd, int sync,
264 unsigned short prio)
265{
266 const int base_slice = cfqd->cfq_slice[sync];
267
268 WARN_ON(prio >= IOPRIO_BE_NR);
269
270 return base_slice + (base_slice/CFQ_SLICE_SCALE * (4 - prio));
271}
272
Jens Axboe44f7c162007-01-19 11:51:58 +1100273static inline int
274cfq_prio_to_slice(struct cfq_data *cfqd, struct cfq_queue *cfqq)
275{
Jens Axboed9e76202007-04-20 14:27:50 +0200276 return cfq_prio_slice(cfqd, cfq_cfqq_sync(cfqq), cfqq->ioprio);
Jens Axboe44f7c162007-01-19 11:51:58 +1100277}
278
279static inline void
280cfq_set_prio_slice(struct cfq_data *cfqd, struct cfq_queue *cfqq)
281{
282 cfqq->slice_end = cfq_prio_to_slice(cfqd, cfqq) + jiffies;
Jens Axboe7b679132008-05-30 12:23:07 +0200283 cfq_log_cfqq(cfqd, cfqq, "set_slice=%lu", cfqq->slice_end - jiffies);
Jens Axboe44f7c162007-01-19 11:51:58 +1100284}
285
286/*
287 * We need to wrap this check in cfq_cfqq_slice_new(), since ->slice_end
288 * isn't valid until the first request from the dispatch is activated
289 * and the slice time set.
290 */
291static inline int cfq_slice_used(struct cfq_queue *cfqq)
292{
293 if (cfq_cfqq_slice_new(cfqq))
294 return 0;
295 if (time_before(jiffies, cfqq->slice_end))
296 return 0;
297
298 return 1;
299}
300
301/*
Jens Axboe5e705372006-07-13 12:39:25 +0200302 * Lifted from AS - choose which of rq1 and rq2 that is best served now.
Linus Torvalds1da177e2005-04-16 15:20:36 -0700303 * We choose the request that is closest to the head right now. Distance
Andreas Mohre8a99052006-03-28 08:59:49 +0200304 * behind the head is penalized and only allowed to a certain extent.
Linus Torvalds1da177e2005-04-16 15:20:36 -0700305 */
Jens Axboe5e705372006-07-13 12:39:25 +0200306static struct request *
307cfq_choose_req(struct cfq_data *cfqd, struct request *rq1, struct request *rq2)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700308{
309 sector_t last, s1, s2, d1 = 0, d2 = 0;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700310 unsigned long back_max;
Andreas Mohre8a99052006-03-28 08:59:49 +0200311#define CFQ_RQ1_WRAP 0x01 /* request 1 wraps */
312#define CFQ_RQ2_WRAP 0x02 /* request 2 wraps */
313 unsigned wrap = 0; /* bit mask: requests behind the disk head? */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700314
Jens Axboe5e705372006-07-13 12:39:25 +0200315 if (rq1 == NULL || rq1 == rq2)
316 return rq2;
317 if (rq2 == NULL)
318 return rq1;
Jens Axboe9c2c38a2005-08-24 14:57:54 +0200319
Jens Axboe5e705372006-07-13 12:39:25 +0200320 if (rq_is_sync(rq1) && !rq_is_sync(rq2))
321 return rq1;
322 else if (rq_is_sync(rq2) && !rq_is_sync(rq1))
323 return rq2;
Jens Axboe374f84a2006-07-23 01:42:19 +0200324 if (rq_is_meta(rq1) && !rq_is_meta(rq2))
325 return rq1;
326 else if (rq_is_meta(rq2) && !rq_is_meta(rq1))
327 return rq2;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700328
Jens Axboe5e705372006-07-13 12:39:25 +0200329 s1 = rq1->sector;
330 s2 = rq2->sector;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700331
Jens Axboe6d048f52007-04-25 12:44:27 +0200332 last = cfqd->last_position;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700333
Linus Torvalds1da177e2005-04-16 15:20:36 -0700334 /*
335 * by definition, 1KiB is 2 sectors
336 */
337 back_max = cfqd->cfq_back_max * 2;
338
339 /*
340 * Strict one way elevator _except_ in the case where we allow
341 * short backward seeks which are biased as twice the cost of a
342 * similar forward seek.
343 */
344 if (s1 >= last)
345 d1 = s1 - last;
346 else if (s1 + back_max >= last)
347 d1 = (last - s1) * cfqd->cfq_back_penalty;
348 else
Andreas Mohre8a99052006-03-28 08:59:49 +0200349 wrap |= CFQ_RQ1_WRAP;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700350
351 if (s2 >= last)
352 d2 = s2 - last;
353 else if (s2 + back_max >= last)
354 d2 = (last - s2) * cfqd->cfq_back_penalty;
355 else
Andreas Mohre8a99052006-03-28 08:59:49 +0200356 wrap |= CFQ_RQ2_WRAP;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700357
358 /* Found required data */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700359
Andreas Mohre8a99052006-03-28 08:59:49 +0200360 /*
361 * By doing switch() on the bit mask "wrap" we avoid having to
362 * check two variables for all permutations: --> faster!
363 */
364 switch (wrap) {
Jens Axboe5e705372006-07-13 12:39:25 +0200365 case 0: /* common case for CFQ: rq1 and rq2 not wrapped */
Andreas Mohre8a99052006-03-28 08:59:49 +0200366 if (d1 < d2)
Jens Axboe5e705372006-07-13 12:39:25 +0200367 return rq1;
Andreas Mohre8a99052006-03-28 08:59:49 +0200368 else if (d2 < d1)
Jens Axboe5e705372006-07-13 12:39:25 +0200369 return rq2;
Andreas Mohre8a99052006-03-28 08:59:49 +0200370 else {
371 if (s1 >= s2)
Jens Axboe5e705372006-07-13 12:39:25 +0200372 return rq1;
Andreas Mohre8a99052006-03-28 08:59:49 +0200373 else
Jens Axboe5e705372006-07-13 12:39:25 +0200374 return rq2;
Andreas Mohre8a99052006-03-28 08:59:49 +0200375 }
376
377 case CFQ_RQ2_WRAP:
Jens Axboe5e705372006-07-13 12:39:25 +0200378 return rq1;
Andreas Mohre8a99052006-03-28 08:59:49 +0200379 case CFQ_RQ1_WRAP:
Jens Axboe5e705372006-07-13 12:39:25 +0200380 return rq2;
381 case (CFQ_RQ1_WRAP|CFQ_RQ2_WRAP): /* both rqs wrapped */
Andreas Mohre8a99052006-03-28 08:59:49 +0200382 default:
383 /*
384 * Since both rqs are wrapped,
385 * start with the one that's further behind head
386 * (--> only *one* back seek required),
387 * since back seek takes more time than forward.
388 */
389 if (s1 <= s2)
Jens Axboe5e705372006-07-13 12:39:25 +0200390 return rq1;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700391 else
Jens Axboe5e705372006-07-13 12:39:25 +0200392 return rq2;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700393 }
394}
395
Jens Axboe498d3aa2007-04-26 12:54:48 +0200396/*
397 * The below is leftmost cache rbtree addon
398 */
Jens Axboe08717142008-01-28 11:38:15 +0100399static struct cfq_queue *cfq_rb_first(struct cfq_rb_root *root)
Jens Axboecc09e292007-04-26 12:53:50 +0200400{
401 if (!root->left)
402 root->left = rb_first(&root->rb);
403
Jens Axboe08717142008-01-28 11:38:15 +0100404 if (root->left)
405 return rb_entry(root->left, struct cfq_queue, rb_node);
406
407 return NULL;
Jens Axboecc09e292007-04-26 12:53:50 +0200408}
409
410static void cfq_rb_erase(struct rb_node *n, struct cfq_rb_root *root)
411{
412 if (root->left == n)
413 root->left = NULL;
414
415 rb_erase(n, &root->rb);
416 RB_CLEAR_NODE(n);
417}
418
Linus Torvalds1da177e2005-04-16 15:20:36 -0700419/*
420 * would be nice to take fifo expire time into account as well
421 */
Jens Axboe5e705372006-07-13 12:39:25 +0200422static struct request *
423cfq_find_next_rq(struct cfq_data *cfqd, struct cfq_queue *cfqq,
424 struct request *last)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700425{
Jens Axboe21183b02006-07-13 12:33:14 +0200426 struct rb_node *rbnext = rb_next(&last->rb_node);
427 struct rb_node *rbprev = rb_prev(&last->rb_node);
Jens Axboe5e705372006-07-13 12:39:25 +0200428 struct request *next = NULL, *prev = NULL;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700429
Jens Axboe21183b02006-07-13 12:33:14 +0200430 BUG_ON(RB_EMPTY_NODE(&last->rb_node));
Linus Torvalds1da177e2005-04-16 15:20:36 -0700431
432 if (rbprev)
Jens Axboe5e705372006-07-13 12:39:25 +0200433 prev = rb_entry_rq(rbprev);
Jens Axboe21183b02006-07-13 12:33:14 +0200434
Linus Torvalds1da177e2005-04-16 15:20:36 -0700435 if (rbnext)
Jens Axboe5e705372006-07-13 12:39:25 +0200436 next = rb_entry_rq(rbnext);
Jens Axboe21183b02006-07-13 12:33:14 +0200437 else {
438 rbnext = rb_first(&cfqq->sort_list);
439 if (rbnext && rbnext != &last->rb_node)
Jens Axboe5e705372006-07-13 12:39:25 +0200440 next = rb_entry_rq(rbnext);
Jens Axboe21183b02006-07-13 12:33:14 +0200441 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700442
Jens Axboe21183b02006-07-13 12:33:14 +0200443 return cfq_choose_req(cfqd, next, prev);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700444}
445
Jens Axboed9e76202007-04-20 14:27:50 +0200446static unsigned long cfq_slice_offset(struct cfq_data *cfqd,
447 struct cfq_queue *cfqq)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700448{
Jens Axboed9e76202007-04-20 14:27:50 +0200449 /*
450 * just an approximation, should be ok.
451 */
Jens Axboe67e6b492007-04-20 14:18:00 +0200452 return (cfqd->busy_queues - 1) * (cfq_prio_slice(cfqd, 1, 0) -
453 cfq_prio_slice(cfqd, cfq_cfqq_sync(cfqq), cfqq->ioprio));
Jens Axboed9e76202007-04-20 14:27:50 +0200454}
Linus Torvalds1da177e2005-04-16 15:20:36 -0700455
Jens Axboe498d3aa2007-04-26 12:54:48 +0200456/*
457 * The cfqd->service_tree holds all pending cfq_queue's that have
458 * requests waiting to be processed. It is sorted in the order that
459 * we will service the queues.
460 */
Jens Axboed9e76202007-04-20 14:27:50 +0200461static void cfq_service_tree_add(struct cfq_data *cfqd,
Jens Axboeedd75ff2007-04-19 12:03:34 +0200462 struct cfq_queue *cfqq, int add_front)
Jens Axboed9e76202007-04-20 14:27:50 +0200463{
Jens Axboe08717142008-01-28 11:38:15 +0100464 struct rb_node **p, *parent;
465 struct cfq_queue *__cfqq;
Jens Axboed9e76202007-04-20 14:27:50 +0200466 unsigned long rb_key;
Jens Axboe498d3aa2007-04-26 12:54:48 +0200467 int left;
Jens Axboed9e76202007-04-20 14:27:50 +0200468
Jens Axboe08717142008-01-28 11:38:15 +0100469 if (cfq_class_idle(cfqq)) {
470 rb_key = CFQ_IDLE_DELAY;
471 parent = rb_last(&cfqd->service_tree.rb);
472 if (parent && parent != &cfqq->rb_node) {
473 __cfqq = rb_entry(parent, struct cfq_queue, rb_node);
474 rb_key += __cfqq->rb_key;
475 } else
476 rb_key += jiffies;
477 } else if (!add_front) {
Jens Axboeedd75ff2007-04-19 12:03:34 +0200478 rb_key = cfq_slice_offset(cfqd, cfqq) + jiffies;
479 rb_key += cfqq->slice_resid;
480 cfqq->slice_resid = 0;
481 } else
482 rb_key = 0;
Jens Axboed9e76202007-04-20 14:27:50 +0200483
484 if (!RB_EMPTY_NODE(&cfqq->rb_node)) {
Jens Axboe99f96282007-02-05 11:56:25 +0100485 /*
Jens Axboed9e76202007-04-20 14:27:50 +0200486 * same position, nothing more to do
Jens Axboe99f96282007-02-05 11:56:25 +0100487 */
Jens Axboed9e76202007-04-20 14:27:50 +0200488 if (rb_key == cfqq->rb_key)
489 return;
Jens Axboe53b03742006-07-28 09:48:51 +0200490
Jens Axboecc09e292007-04-26 12:53:50 +0200491 cfq_rb_erase(&cfqq->rb_node, &cfqd->service_tree);
Jens Axboe22e2c502005-06-27 10:55:12 +0200492 }
Jens Axboed9e76202007-04-20 14:27:50 +0200493
Jens Axboe498d3aa2007-04-26 12:54:48 +0200494 left = 1;
Jens Axboe08717142008-01-28 11:38:15 +0100495 parent = NULL;
496 p = &cfqd->service_tree.rb.rb_node;
Jens Axboed9e76202007-04-20 14:27:50 +0200497 while (*p) {
Jens Axboe67060e32007-04-18 20:13:32 +0200498 struct rb_node **n;
Jens Axboecc09e292007-04-26 12:53:50 +0200499
Jens Axboed9e76202007-04-20 14:27:50 +0200500 parent = *p;
501 __cfqq = rb_entry(parent, struct cfq_queue, rb_node);
502
Jens Axboe0c534e02007-04-18 20:01:57 +0200503 /*
504 * sort RT queues first, we always want to give
Jens Axboe67060e32007-04-18 20:13:32 +0200505 * preference to them. IDLE queues goes to the back.
506 * after that, sort on the next service time.
Jens Axboe0c534e02007-04-18 20:01:57 +0200507 */
508 if (cfq_class_rt(cfqq) > cfq_class_rt(__cfqq))
Jens Axboe67060e32007-04-18 20:13:32 +0200509 n = &(*p)->rb_left;
Jens Axboe0c534e02007-04-18 20:01:57 +0200510 else if (cfq_class_rt(cfqq) < cfq_class_rt(__cfqq))
Jens Axboe67060e32007-04-18 20:13:32 +0200511 n = &(*p)->rb_right;
512 else if (cfq_class_idle(cfqq) < cfq_class_idle(__cfqq))
513 n = &(*p)->rb_left;
514 else if (cfq_class_idle(cfqq) > cfq_class_idle(__cfqq))
515 n = &(*p)->rb_right;
Jens Axboe0c534e02007-04-18 20:01:57 +0200516 else if (rb_key < __cfqq->rb_key)
Jens Axboe67060e32007-04-18 20:13:32 +0200517 n = &(*p)->rb_left;
518 else
519 n = &(*p)->rb_right;
520
521 if (n == &(*p)->rb_right)
Jens Axboecc09e292007-04-26 12:53:50 +0200522 left = 0;
Jens Axboe67060e32007-04-18 20:13:32 +0200523
524 p = n;
Jens Axboed9e76202007-04-20 14:27:50 +0200525 }
526
Jens Axboecc09e292007-04-26 12:53:50 +0200527 if (left)
528 cfqd->service_tree.left = &cfqq->rb_node;
529
Jens Axboed9e76202007-04-20 14:27:50 +0200530 cfqq->rb_key = rb_key;
531 rb_link_node(&cfqq->rb_node, parent, p);
Jens Axboecc09e292007-04-26 12:53:50 +0200532 rb_insert_color(&cfqq->rb_node, &cfqd->service_tree.rb);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700533}
534
Jens Axboe498d3aa2007-04-26 12:54:48 +0200535/*
536 * Update cfqq's position in the service tree.
537 */
Jens Axboeedd75ff2007-04-19 12:03:34 +0200538static void cfq_resort_rr_list(struct cfq_data *cfqd, struct cfq_queue *cfqq)
Jens Axboe6d048f52007-04-25 12:44:27 +0200539{
Jens Axboe6d048f52007-04-25 12:44:27 +0200540 /*
541 * Resorting requires the cfqq to be on the RR list already.
542 */
Jens Axboe498d3aa2007-04-26 12:54:48 +0200543 if (cfq_cfqq_on_rr(cfqq))
Jens Axboeedd75ff2007-04-19 12:03:34 +0200544 cfq_service_tree_add(cfqd, cfqq, 0);
Jens Axboe6d048f52007-04-25 12:44:27 +0200545}
546
Linus Torvalds1da177e2005-04-16 15:20:36 -0700547/*
548 * add to busy list of queues for service, trying to be fair in ordering
Jens Axboe22e2c502005-06-27 10:55:12 +0200549 * the pending list according to last request service
Linus Torvalds1da177e2005-04-16 15:20:36 -0700550 */
Jens Axboefebffd62008-01-28 13:19:43 +0100551static void cfq_add_cfqq_rr(struct cfq_data *cfqd, struct cfq_queue *cfqq)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700552{
Jens Axboe7b679132008-05-30 12:23:07 +0200553 cfq_log_cfqq(cfqd, cfqq, "add_to_rr");
Jens Axboe3b181522005-06-27 10:56:24 +0200554 BUG_ON(cfq_cfqq_on_rr(cfqq));
555 cfq_mark_cfqq_on_rr(cfqq);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700556 cfqd->busy_queues++;
557
Jens Axboeedd75ff2007-04-19 12:03:34 +0200558 cfq_resort_rr_list(cfqd, cfqq);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700559}
560
Jens Axboe498d3aa2007-04-26 12:54:48 +0200561/*
562 * Called when the cfqq no longer has requests pending, remove it from
563 * the service tree.
564 */
Jens Axboefebffd62008-01-28 13:19:43 +0100565static void cfq_del_cfqq_rr(struct cfq_data *cfqd, struct cfq_queue *cfqq)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700566{
Jens Axboe7b679132008-05-30 12:23:07 +0200567 cfq_log_cfqq(cfqd, cfqq, "del_from_rr");
Jens Axboe3b181522005-06-27 10:56:24 +0200568 BUG_ON(!cfq_cfqq_on_rr(cfqq));
569 cfq_clear_cfqq_on_rr(cfqq);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700570
Jens Axboecc09e292007-04-26 12:53:50 +0200571 if (!RB_EMPTY_NODE(&cfqq->rb_node))
572 cfq_rb_erase(&cfqq->rb_node, &cfqd->service_tree);
Jens Axboed9e76202007-04-20 14:27:50 +0200573
Linus Torvalds1da177e2005-04-16 15:20:36 -0700574 BUG_ON(!cfqd->busy_queues);
575 cfqd->busy_queues--;
576}
577
578/*
579 * rb tree support functions
580 */
Jens Axboefebffd62008-01-28 13:19:43 +0100581static void cfq_del_rq_rb(struct request *rq)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700582{
Jens Axboe5e705372006-07-13 12:39:25 +0200583 struct cfq_queue *cfqq = RQ_CFQQ(rq);
Jens Axboeb4878f22005-10-20 16:42:29 +0200584 struct cfq_data *cfqd = cfqq->cfqd;
Jens Axboe5e705372006-07-13 12:39:25 +0200585 const int sync = rq_is_sync(rq);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700586
Jens Axboeb4878f22005-10-20 16:42:29 +0200587 BUG_ON(!cfqq->queued[sync]);
588 cfqq->queued[sync]--;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700589
Jens Axboe5e705372006-07-13 12:39:25 +0200590 elv_rb_del(&cfqq->sort_list, rq);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700591
Jens Axboedd67d052006-06-21 09:36:18 +0200592 if (cfq_cfqq_on_rr(cfqq) && RB_EMPTY_ROOT(&cfqq->sort_list))
Jens Axboeb4878f22005-10-20 16:42:29 +0200593 cfq_del_cfqq_rr(cfqd, cfqq);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700594}
595
Jens Axboe5e705372006-07-13 12:39:25 +0200596static void cfq_add_rq_rb(struct request *rq)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700597{
Jens Axboe5e705372006-07-13 12:39:25 +0200598 struct cfq_queue *cfqq = RQ_CFQQ(rq);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700599 struct cfq_data *cfqd = cfqq->cfqd;
Jens Axboe21183b02006-07-13 12:33:14 +0200600 struct request *__alias;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700601
Jens Axboe5380a102006-07-13 12:37:56 +0200602 cfqq->queued[rq_is_sync(rq)]++;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700603
604 /*
605 * looks a little odd, but the first insert might return an alias.
606 * if that happens, put the alias on the dispatch list
607 */
Jens Axboe21183b02006-07-13 12:33:14 +0200608 while ((__alias = elv_rb_add(&cfqq->sort_list, rq)) != NULL)
Jens Axboe5e705372006-07-13 12:39:25 +0200609 cfq_dispatch_insert(cfqd->queue, __alias);
Jens Axboe5fccbf62006-10-31 14:21:55 +0100610
611 if (!cfq_cfqq_on_rr(cfqq))
612 cfq_add_cfqq_rr(cfqd, cfqq);
Jens Axboe5044eed2007-04-25 11:53:48 +0200613
614 /*
615 * check if this request is a better next-serve candidate
616 */
617 cfqq->next_rq = cfq_choose_req(cfqd, cfqq->next_rq, rq);
618 BUG_ON(!cfqq->next_rq);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700619}
620
Jens Axboefebffd62008-01-28 13:19:43 +0100621static void cfq_reposition_rq_rb(struct cfq_queue *cfqq, struct request *rq)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700622{
Jens Axboe5380a102006-07-13 12:37:56 +0200623 elv_rb_del(&cfqq->sort_list, rq);
624 cfqq->queued[rq_is_sync(rq)]--;
Jens Axboe5e705372006-07-13 12:39:25 +0200625 cfq_add_rq_rb(rq);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700626}
627
Jens Axboe206dc692006-03-28 13:03:44 +0200628static struct request *
629cfq_find_rq_fmerge(struct cfq_data *cfqd, struct bio *bio)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700630{
Jens Axboe206dc692006-03-28 13:03:44 +0200631 struct task_struct *tsk = current;
Vasily Tarasov91fac312007-04-25 12:29:51 +0200632 struct cfq_io_context *cic;
Jens Axboe206dc692006-03-28 13:03:44 +0200633 struct cfq_queue *cfqq;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700634
Jens Axboe4ac845a2008-01-24 08:44:49 +0100635 cic = cfq_cic_lookup(cfqd, tsk->io_context);
Vasily Tarasov91fac312007-04-25 12:29:51 +0200636 if (!cic)
637 return NULL;
638
639 cfqq = cic_to_cfqq(cic, cfq_bio_sync(bio));
Jens Axboe89850f72006-07-22 16:48:31 +0200640 if (cfqq) {
641 sector_t sector = bio->bi_sector + bio_sectors(bio);
642
Jens Axboe21183b02006-07-13 12:33:14 +0200643 return elv_rb_find(&cfqq->sort_list, sector);
Jens Axboe89850f72006-07-22 16:48:31 +0200644 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700645
Linus Torvalds1da177e2005-04-16 15:20:36 -0700646 return NULL;
647}
648
Jens Axboe165125e2007-07-24 09:28:11 +0200649static void cfq_activate_request(struct request_queue *q, struct request *rq)
Jens Axboeb4878f22005-10-20 16:42:29 +0200650{
651 struct cfq_data *cfqd = q->elevator->elevator_data;
652
653 cfqd->rq_in_driver++;
Jens Axboe7b679132008-05-30 12:23:07 +0200654 cfq_log_cfqq(cfqd, RQ_CFQQ(rq), "activate rq, drv=%d",
655 cfqd->rq_in_driver);
Jens Axboe25776e32006-06-01 10:12:26 +0200656
657 /*
658 * If the depth is larger 1, it really could be queueing. But lets
659 * make the mark a little higher - idling could still be good for
660 * low queueing, and a low queueing number could also just indicate
661 * a SCSI mid layer like behaviour where limit+1 is often seen.
662 */
663 if (!cfqd->hw_tag && cfqd->rq_in_driver > 4)
664 cfqd->hw_tag = 1;
Jens Axboe6d048f52007-04-25 12:44:27 +0200665
666 cfqd->last_position = rq->hard_sector + rq->hard_nr_sectors;
Jens Axboeb4878f22005-10-20 16:42:29 +0200667}
668
Jens Axboe165125e2007-07-24 09:28:11 +0200669static void cfq_deactivate_request(struct request_queue *q, struct request *rq)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700670{
Jens Axboe22e2c502005-06-27 10:55:12 +0200671 struct cfq_data *cfqd = q->elevator->elevator_data;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700672
Jens Axboeb4878f22005-10-20 16:42:29 +0200673 WARN_ON(!cfqd->rq_in_driver);
674 cfqd->rq_in_driver--;
Jens Axboe7b679132008-05-30 12:23:07 +0200675 cfq_log_cfqq(cfqd, RQ_CFQQ(rq), "deactivate rq, drv=%d",
676 cfqd->rq_in_driver);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700677}
678
Jens Axboeb4878f22005-10-20 16:42:29 +0200679static void cfq_remove_request(struct request *rq)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700680{
Jens Axboe5e705372006-07-13 12:39:25 +0200681 struct cfq_queue *cfqq = RQ_CFQQ(rq);
Jens Axboe21183b02006-07-13 12:33:14 +0200682
Jens Axboe5e705372006-07-13 12:39:25 +0200683 if (cfqq->next_rq == rq)
684 cfqq->next_rq = cfq_find_next_rq(cfqq->cfqd, cfqq, rq);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700685
Jens Axboeb4878f22005-10-20 16:42:29 +0200686 list_del_init(&rq->queuelist);
Jens Axboe5e705372006-07-13 12:39:25 +0200687 cfq_del_rq_rb(rq);
Jens Axboe374f84a2006-07-23 01:42:19 +0200688
689 if (rq_is_meta(rq)) {
690 WARN_ON(!cfqq->meta_pending);
691 cfqq->meta_pending--;
692 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700693}
694
Jens Axboe165125e2007-07-24 09:28:11 +0200695static int cfq_merge(struct request_queue *q, struct request **req,
696 struct bio *bio)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700697{
698 struct cfq_data *cfqd = q->elevator->elevator_data;
699 struct request *__rq;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700700
Jens Axboe206dc692006-03-28 13:03:44 +0200701 __rq = cfq_find_rq_fmerge(cfqd, bio);
Jens Axboe22e2c502005-06-27 10:55:12 +0200702 if (__rq && elv_rq_merge_ok(__rq, bio)) {
Jens Axboe98170642006-07-28 09:23:08 +0200703 *req = __rq;
704 return ELEVATOR_FRONT_MERGE;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700705 }
706
707 return ELEVATOR_NO_MERGE;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700708}
709
Jens Axboe165125e2007-07-24 09:28:11 +0200710static void cfq_merged_request(struct request_queue *q, struct request *req,
Jens Axboe21183b02006-07-13 12:33:14 +0200711 int type)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700712{
Jens Axboe21183b02006-07-13 12:33:14 +0200713 if (type == ELEVATOR_FRONT_MERGE) {
Jens Axboe5e705372006-07-13 12:39:25 +0200714 struct cfq_queue *cfqq = RQ_CFQQ(req);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700715
Jens Axboe5e705372006-07-13 12:39:25 +0200716 cfq_reposition_rq_rb(cfqq, req);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700717 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700718}
719
720static void
Jens Axboe165125e2007-07-24 09:28:11 +0200721cfq_merged_requests(struct request_queue *q, struct request *rq,
Linus Torvalds1da177e2005-04-16 15:20:36 -0700722 struct request *next)
723{
Jens Axboe22e2c502005-06-27 10:55:12 +0200724 /*
725 * reposition in fifo if next is older than rq
726 */
727 if (!list_empty(&rq->queuelist) && !list_empty(&next->queuelist) &&
728 time_before(next->start_time, rq->start_time))
729 list_move(&rq->queuelist, &next->queuelist);
730
Jens Axboeb4878f22005-10-20 16:42:29 +0200731 cfq_remove_request(next);
Jens Axboe22e2c502005-06-27 10:55:12 +0200732}
733
Jens Axboe165125e2007-07-24 09:28:11 +0200734static int cfq_allow_merge(struct request_queue *q, struct request *rq,
Jens Axboeda775262006-12-20 11:04:12 +0100735 struct bio *bio)
736{
737 struct cfq_data *cfqd = q->elevator->elevator_data;
Vasily Tarasov91fac312007-04-25 12:29:51 +0200738 struct cfq_io_context *cic;
Jens Axboeda775262006-12-20 11:04:12 +0100739 struct cfq_queue *cfqq;
Jens Axboeda775262006-12-20 11:04:12 +0100740
741 /*
Jens Axboeec8acb62007-01-02 18:32:11 +0100742 * Disallow merge of a sync bio into an async request.
Jens Axboeda775262006-12-20 11:04:12 +0100743 */
Vasily Tarasov91fac312007-04-25 12:29:51 +0200744 if (cfq_bio_sync(bio) && !rq_is_sync(rq))
Jens Axboeda775262006-12-20 11:04:12 +0100745 return 0;
746
747 /*
Jens Axboe719d3402006-12-22 09:38:53 +0100748 * Lookup the cfqq that this bio will be queued with. Allow
749 * merge only if rq is queued there.
Jens Axboeda775262006-12-20 11:04:12 +0100750 */
Jens Axboe4ac845a2008-01-24 08:44:49 +0100751 cic = cfq_cic_lookup(cfqd, current->io_context);
Vasily Tarasov91fac312007-04-25 12:29:51 +0200752 if (!cic)
753 return 0;
Jens Axboe719d3402006-12-22 09:38:53 +0100754
Vasily Tarasov91fac312007-04-25 12:29:51 +0200755 cfqq = cic_to_cfqq(cic, cfq_bio_sync(bio));
Jens Axboe719d3402006-12-22 09:38:53 +0100756 if (cfqq == RQ_CFQQ(rq))
757 return 1;
Jens Axboeda775262006-12-20 11:04:12 +0100758
Jens Axboeec8acb62007-01-02 18:32:11 +0100759 return 0;
Jens Axboeda775262006-12-20 11:04:12 +0100760}
761
Jens Axboefebffd62008-01-28 13:19:43 +0100762static void __cfq_set_active_queue(struct cfq_data *cfqd,
763 struct cfq_queue *cfqq)
Jens Axboe22e2c502005-06-27 10:55:12 +0200764{
765 if (cfqq) {
Jens Axboe7b679132008-05-30 12:23:07 +0200766 cfq_log_cfqq(cfqd, cfqq, "set_active");
Jens Axboe22e2c502005-06-27 10:55:12 +0200767 cfqq->slice_end = 0;
Jens Axboe3b181522005-06-27 10:56:24 +0200768 cfq_clear_cfqq_must_alloc_slice(cfqq);
769 cfq_clear_cfqq_fifo_expire(cfqq);
Jens Axboe44f7c162007-01-19 11:51:58 +1100770 cfq_mark_cfqq_slice_new(cfqq);
Jens Axboe1afba042007-04-17 12:47:55 +0200771 cfq_clear_cfqq_queue_new(cfqq);
Jens Axboe22e2c502005-06-27 10:55:12 +0200772 }
773
774 cfqd->active_queue = cfqq;
775}
776
777/*
Jens Axboe7b14e3b2006-02-28 09:35:11 +0100778 * current cfqq expired its slice (or was too idle), select new one
779 */
780static void
781__cfq_slice_expired(struct cfq_data *cfqd, struct cfq_queue *cfqq,
Jens Axboe6084cdd2007-04-23 08:25:00 +0200782 int timed_out)
Jens Axboe7b14e3b2006-02-28 09:35:11 +0100783{
Jens Axboe7b679132008-05-30 12:23:07 +0200784 cfq_log_cfqq(cfqd, cfqq, "slice expired t=%d", timed_out);
785
Jens Axboe7b14e3b2006-02-28 09:35:11 +0100786 if (cfq_cfqq_wait_request(cfqq))
787 del_timer(&cfqd->idle_slice_timer);
788
Jens Axboe7b14e3b2006-02-28 09:35:11 +0100789 cfq_clear_cfqq_must_dispatch(cfqq);
790 cfq_clear_cfqq_wait_request(cfqq);
791
792 /*
Jens Axboe6084cdd2007-04-23 08:25:00 +0200793 * store what was left of this slice, if the queue idled/timed out
Jens Axboe7b14e3b2006-02-28 09:35:11 +0100794 */
Jens Axboe7b679132008-05-30 12:23:07 +0200795 if (timed_out && !cfq_cfqq_slice_new(cfqq)) {
Jens Axboec5b680f2007-01-19 11:56:49 +1100796 cfqq->slice_resid = cfqq->slice_end - jiffies;
Jens Axboe7b679132008-05-30 12:23:07 +0200797 cfq_log_cfqq(cfqd, cfqq, "resid=%ld", cfqq->slice_resid);
798 }
Jens Axboe7b14e3b2006-02-28 09:35:11 +0100799
Jens Axboeedd75ff2007-04-19 12:03:34 +0200800 cfq_resort_rr_list(cfqd, cfqq);
Jens Axboe7b14e3b2006-02-28 09:35:11 +0100801
802 if (cfqq == cfqd->active_queue)
803 cfqd->active_queue = NULL;
804
805 if (cfqd->active_cic) {
806 put_io_context(cfqd->active_cic->ioc);
807 cfqd->active_cic = NULL;
808 }
Jens Axboe7b14e3b2006-02-28 09:35:11 +0100809}
810
Jens Axboe6084cdd2007-04-23 08:25:00 +0200811static inline void cfq_slice_expired(struct cfq_data *cfqd, int timed_out)
Jens Axboe7b14e3b2006-02-28 09:35:11 +0100812{
813 struct cfq_queue *cfqq = cfqd->active_queue;
814
815 if (cfqq)
Jens Axboe6084cdd2007-04-23 08:25:00 +0200816 __cfq_slice_expired(cfqd, cfqq, timed_out);
Jens Axboe7b14e3b2006-02-28 09:35:11 +0100817}
818
Jens Axboe498d3aa2007-04-26 12:54:48 +0200819/*
820 * Get next queue for service. Unless we have a queue preemption,
821 * we'll simply select the first cfqq in the service tree.
822 */
Jens Axboe6d048f52007-04-25 12:44:27 +0200823static struct cfq_queue *cfq_get_next_queue(struct cfq_data *cfqd)
Jens Axboe22e2c502005-06-27 10:55:12 +0200824{
Jens Axboeedd75ff2007-04-19 12:03:34 +0200825 if (RB_EMPTY_ROOT(&cfqd->service_tree.rb))
826 return NULL;
827
Jens Axboe08717142008-01-28 11:38:15 +0100828 return cfq_rb_first(&cfqd->service_tree);
Jens Axboe6d048f52007-04-25 12:44:27 +0200829}
830
Jens Axboe498d3aa2007-04-26 12:54:48 +0200831/*
832 * Get and set a new active queue for service.
833 */
Jens Axboe6d048f52007-04-25 12:44:27 +0200834static struct cfq_queue *cfq_set_active_queue(struct cfq_data *cfqd)
835{
836 struct cfq_queue *cfqq;
837
Jens Axboed9e76202007-04-20 14:27:50 +0200838 cfqq = cfq_get_next_queue(cfqd);
Jens Axboe22e2c502005-06-27 10:55:12 +0200839 __cfq_set_active_queue(cfqd, cfqq);
Jens Axboe3b181522005-06-27 10:56:24 +0200840 return cfqq;
Jens Axboe22e2c502005-06-27 10:55:12 +0200841}
842
Jens Axboed9e76202007-04-20 14:27:50 +0200843static inline sector_t cfq_dist_from_last(struct cfq_data *cfqd,
844 struct request *rq)
845{
846 if (rq->sector >= cfqd->last_position)
847 return rq->sector - cfqd->last_position;
848 else
849 return cfqd->last_position - rq->sector;
850}
851
Jens Axboe6d048f52007-04-25 12:44:27 +0200852static inline int cfq_rq_close(struct cfq_data *cfqd, struct request *rq)
853{
854 struct cfq_io_context *cic = cfqd->active_cic;
Jens Axboecaaa5f92006-06-16 11:23:00 +0200855
Jens Axboe6d048f52007-04-25 12:44:27 +0200856 if (!sample_valid(cic->seek_samples))
857 return 0;
858
859 return cfq_dist_from_last(cfqd, rq) <= cic->seek_mean;
860}
861
Jens Axboed9e76202007-04-20 14:27:50 +0200862static int cfq_close_cooperator(struct cfq_data *cfq_data,
863 struct cfq_queue *cfqq)
Jens Axboe6d048f52007-04-25 12:44:27 +0200864{
Jens Axboe6d048f52007-04-25 12:44:27 +0200865 /*
Jens Axboed9e76202007-04-20 14:27:50 +0200866 * We should notice if some of the queues are cooperating, eg
867 * working closely on the same area of the disk. In that case,
868 * we can group them together and don't waste time idling.
Jens Axboe6d048f52007-04-25 12:44:27 +0200869 */
Jens Axboed9e76202007-04-20 14:27:50 +0200870 return 0;
Jens Axboe6d048f52007-04-25 12:44:27 +0200871}
872
873#define CIC_SEEKY(cic) ((cic)->seek_mean > (8 * 1024))
874
875static void cfq_arm_slice_timer(struct cfq_data *cfqd)
Jens Axboe22e2c502005-06-27 10:55:12 +0200876{
Jens Axboe17926692007-01-19 11:59:30 +1100877 struct cfq_queue *cfqq = cfqd->active_queue;
Jens Axboe206dc692006-03-28 13:03:44 +0200878 struct cfq_io_context *cic;
Jens Axboe7b14e3b2006-02-28 09:35:11 +0100879 unsigned long sl;
880
Jens Axboedd67d052006-06-21 09:36:18 +0200881 WARN_ON(!RB_EMPTY_ROOT(&cfqq->sort_list));
Jens Axboe6d048f52007-04-25 12:44:27 +0200882 WARN_ON(cfq_cfqq_slice_new(cfqq));
Jens Axboe22e2c502005-06-27 10:55:12 +0200883
884 /*
885 * idle is disabled, either manually or by past process history
886 */
Jens Axboe6d048f52007-04-25 12:44:27 +0200887 if (!cfqd->cfq_slice_idle || !cfq_cfqq_idle_window(cfqq))
888 return;
889
Jens Axboe22e2c502005-06-27 10:55:12 +0200890 /*
Jens Axboe7b679132008-05-30 12:23:07 +0200891 * still requests with the driver, don't idle
892 */
893 if (cfqd->rq_in_driver)
894 return;
895
896 /*
Jens Axboe22e2c502005-06-27 10:55:12 +0200897 * task has exited, don't wait
898 */
Jens Axboe206dc692006-03-28 13:03:44 +0200899 cic = cfqd->active_cic;
Nikanth Karthikesan66dac982007-11-27 12:47:04 +0100900 if (!cic || !atomic_read(&cic->ioc->nr_tasks))
Jens Axboe6d048f52007-04-25 12:44:27 +0200901 return;
902
903 /*
904 * See if this prio level has a good candidate
905 */
Jens Axboe1afba042007-04-17 12:47:55 +0200906 if (cfq_close_cooperator(cfqd, cfqq) &&
907 (sample_valid(cic->ttime_samples) && cic->ttime_mean > 2))
Jens Axboe6d048f52007-04-25 12:44:27 +0200908 return;
Jens Axboe22e2c502005-06-27 10:55:12 +0200909
Jens Axboe3b181522005-06-27 10:56:24 +0200910 cfq_mark_cfqq_must_dispatch(cfqq);
911 cfq_mark_cfqq_wait_request(cfqq);
Jens Axboe22e2c502005-06-27 10:55:12 +0200912
Jens Axboe206dc692006-03-28 13:03:44 +0200913 /*
914 * we don't want to idle for seeks, but we do want to allow
915 * fair distribution of slice time for a process doing back-to-back
916 * seeks. so allow a little bit of time for him to submit a new rq
917 */
Jens Axboe6d048f52007-04-25 12:44:27 +0200918 sl = cfqd->cfq_slice_idle;
Jens Axboecaaa5f92006-06-16 11:23:00 +0200919 if (sample_valid(cic->seek_samples) && CIC_SEEKY(cic))
Jens Axboed9e76202007-04-20 14:27:50 +0200920 sl = min(sl, msecs_to_jiffies(CFQ_MIN_TT));
Jens Axboe206dc692006-03-28 13:03:44 +0200921
Jens Axboe7b14e3b2006-02-28 09:35:11 +0100922 mod_timer(&cfqd->idle_slice_timer, jiffies + sl);
Jens Axboe7b679132008-05-30 12:23:07 +0200923 cfq_log(cfqd, "arm_idle: %lu", sl);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700924}
925
Jens Axboe498d3aa2007-04-26 12:54:48 +0200926/*
927 * Move request from internal lists to the request queue dispatch list.
928 */
Jens Axboe165125e2007-07-24 09:28:11 +0200929static void cfq_dispatch_insert(struct request_queue *q, struct request *rq)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700930{
Jens Axboe3ed9a292007-04-23 08:33:33 +0200931 struct cfq_data *cfqd = q->elevator->elevator_data;
Jens Axboe5e705372006-07-13 12:39:25 +0200932 struct cfq_queue *cfqq = RQ_CFQQ(rq);
Jens Axboe22e2c502005-06-27 10:55:12 +0200933
Jens Axboe7b679132008-05-30 12:23:07 +0200934 cfq_log_cfqq(cfqd, cfqq, "dispatch_insert");
935
Jens Axboe5380a102006-07-13 12:37:56 +0200936 cfq_remove_request(rq);
Jens Axboe6d048f52007-04-25 12:44:27 +0200937 cfqq->dispatched++;
Jens Axboe5380a102006-07-13 12:37:56 +0200938 elv_dispatch_sort(q, rq);
Jens Axboe3ed9a292007-04-23 08:33:33 +0200939
940 if (cfq_cfqq_sync(cfqq))
941 cfqd->sync_flight++;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700942}
943
944/*
945 * return expired entry, or NULL to just start from scratch in rbtree
946 */
Jens Axboefebffd62008-01-28 13:19:43 +0100947static struct request *cfq_check_fifo(struct cfq_queue *cfqq)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700948{
949 struct cfq_data *cfqd = cfqq->cfqd;
Jens Axboe22e2c502005-06-27 10:55:12 +0200950 struct request *rq;
Jens Axboe89850f72006-07-22 16:48:31 +0200951 int fifo;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700952
Jens Axboe3b181522005-06-27 10:56:24 +0200953 if (cfq_cfqq_fifo_expire(cfqq))
Linus Torvalds1da177e2005-04-16 15:20:36 -0700954 return NULL;
Jens Axboecb887412007-01-19 12:01:16 +1100955
956 cfq_mark_cfqq_fifo_expire(cfqq);
957
Jens Axboe89850f72006-07-22 16:48:31 +0200958 if (list_empty(&cfqq->fifo))
959 return NULL;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700960
Jens Axboe6d048f52007-04-25 12:44:27 +0200961 fifo = cfq_cfqq_sync(cfqq);
Jens Axboe89850f72006-07-22 16:48:31 +0200962 rq = rq_entry_fifo(cfqq->fifo.next);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700963
Jens Axboe6d048f52007-04-25 12:44:27 +0200964 if (time_before(jiffies, rq->start_time + cfqd->cfq_fifo_expire[fifo]))
Jens Axboe7b679132008-05-30 12:23:07 +0200965 rq = NULL;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700966
Jens Axboe7b679132008-05-30 12:23:07 +0200967 cfq_log_cfqq(cfqd, cfqq, "fifo=%p", rq);
Jens Axboe6d048f52007-04-25 12:44:27 +0200968 return rq;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700969}
970
Jens Axboe22e2c502005-06-27 10:55:12 +0200971static inline int
972cfq_prio_to_maxrq(struct cfq_data *cfqd, struct cfq_queue *cfqq)
973{
974 const int base_rq = cfqd->cfq_slice_async_rq;
975
976 WARN_ON(cfqq->ioprio >= IOPRIO_BE_NR);
977
978 return 2 * (base_rq + base_rq * (CFQ_PRIO_LISTS - 1 - cfqq->ioprio));
979}
980
981/*
Jens Axboe498d3aa2007-04-26 12:54:48 +0200982 * Select a queue for service. If we have a current active queue,
983 * check whether to continue servicing it, or retrieve and set a new one.
Jens Axboe22e2c502005-06-27 10:55:12 +0200984 */
Tejun Heo1b5ed5e12005-11-10 08:49:19 +0100985static struct cfq_queue *cfq_select_queue(struct cfq_data *cfqd)
Jens Axboe22e2c502005-06-27 10:55:12 +0200986{
Jens Axboe22e2c502005-06-27 10:55:12 +0200987 struct cfq_queue *cfqq;
988
989 cfqq = cfqd->active_queue;
990 if (!cfqq)
991 goto new_queue;
992
993 /*
Jens Axboe6d048f52007-04-25 12:44:27 +0200994 * The active queue has run out of time, expire it and select new.
Jens Axboe22e2c502005-06-27 10:55:12 +0200995 */
Jens Axboe6d048f52007-04-25 12:44:27 +0200996 if (cfq_slice_used(cfqq))
Jens Axboe3b181522005-06-27 10:56:24 +0200997 goto expire;
Jens Axboe22e2c502005-06-27 10:55:12 +0200998
999 /*
Jens Axboe6d048f52007-04-25 12:44:27 +02001000 * The active queue has requests and isn't expired, allow it to
1001 * dispatch.
Jens Axboe22e2c502005-06-27 10:55:12 +02001002 */
Jens Axboedd67d052006-06-21 09:36:18 +02001003 if (!RB_EMPTY_ROOT(&cfqq->sort_list))
Jens Axboe22e2c502005-06-27 10:55:12 +02001004 goto keep_queue;
Jens Axboe6d048f52007-04-25 12:44:27 +02001005
1006 /*
1007 * No requests pending. If the active queue still has requests in
1008 * flight or is idling for a new request, allow either of these
1009 * conditions to happen (or time out) before selecting a new queue.
1010 */
Jens Axboecc197472007-04-20 20:45:39 +02001011 if (timer_pending(&cfqd->idle_slice_timer) ||
1012 (cfqq->dispatched && cfq_cfqq_idle_window(cfqq))) {
Jens Axboecaaa5f92006-06-16 11:23:00 +02001013 cfqq = NULL;
1014 goto keep_queue;
Jens Axboe22e2c502005-06-27 10:55:12 +02001015 }
1016
Jens Axboe3b181522005-06-27 10:56:24 +02001017expire:
Jens Axboe6084cdd2007-04-23 08:25:00 +02001018 cfq_slice_expired(cfqd, 0);
Jens Axboe3b181522005-06-27 10:56:24 +02001019new_queue:
1020 cfqq = cfq_set_active_queue(cfqd);
Jens Axboe22e2c502005-06-27 10:55:12 +02001021keep_queue:
Jens Axboe3b181522005-06-27 10:56:24 +02001022 return cfqq;
Jens Axboe22e2c502005-06-27 10:55:12 +02001023}
1024
Jens Axboe498d3aa2007-04-26 12:54:48 +02001025/*
1026 * Dispatch some requests from cfqq, moving them to the request queue
1027 * dispatch list.
1028 */
Jens Axboe22e2c502005-06-27 10:55:12 +02001029static int
1030__cfq_dispatch_requests(struct cfq_data *cfqd, struct cfq_queue *cfqq,
1031 int max_dispatch)
1032{
1033 int dispatched = 0;
1034
Jens Axboedd67d052006-06-21 09:36:18 +02001035 BUG_ON(RB_EMPTY_ROOT(&cfqq->sort_list));
Jens Axboe22e2c502005-06-27 10:55:12 +02001036
1037 do {
Jens Axboe5e705372006-07-13 12:39:25 +02001038 struct request *rq;
Jens Axboe22e2c502005-06-27 10:55:12 +02001039
1040 /*
1041 * follow expired path, else get first next available
1042 */
Jens Axboefe094d92008-01-31 13:08:54 +01001043 rq = cfq_check_fifo(cfqq);
1044 if (rq == NULL)
Jens Axboe5e705372006-07-13 12:39:25 +02001045 rq = cfqq->next_rq;
Jens Axboe22e2c502005-06-27 10:55:12 +02001046
1047 /*
1048 * finally, insert request into driver dispatch list
1049 */
Jens Axboe5e705372006-07-13 12:39:25 +02001050 cfq_dispatch_insert(cfqd->queue, rq);
Jens Axboe22e2c502005-06-27 10:55:12 +02001051
Jens Axboe22e2c502005-06-27 10:55:12 +02001052 dispatched++;
1053
1054 if (!cfqd->active_cic) {
Jens Axboe5e705372006-07-13 12:39:25 +02001055 atomic_inc(&RQ_CIC(rq)->ioc->refcount);
1056 cfqd->active_cic = RQ_CIC(rq);
Jens Axboe22e2c502005-06-27 10:55:12 +02001057 }
1058
Jens Axboedd67d052006-06-21 09:36:18 +02001059 if (RB_EMPTY_ROOT(&cfqq->sort_list))
Jens Axboe22e2c502005-06-27 10:55:12 +02001060 break;
1061
1062 } while (dispatched < max_dispatch);
1063
1064 /*
Jens Axboe22e2c502005-06-27 10:55:12 +02001065 * expire an async queue immediately if it has used up its slice. idle
1066 * queue always expire after 1 dispatch round.
1067 */
Jens Axboea9938002007-04-20 08:55:52 +02001068 if (cfqd->busy_queues > 1 && ((!cfq_cfqq_sync(cfqq) &&
Jens Axboe20e493a2007-04-23 08:26:36 +02001069 dispatched >= cfq_prio_to_maxrq(cfqd, cfqq)) ||
Jens Axboea9938002007-04-20 08:55:52 +02001070 cfq_class_idle(cfqq))) {
Jens Axboe44f7c162007-01-19 11:51:58 +11001071 cfqq->slice_end = jiffies + 1;
Jens Axboe6084cdd2007-04-23 08:25:00 +02001072 cfq_slice_expired(cfqd, 0);
Jens Axboe44f7c162007-01-19 11:51:58 +11001073 }
Jens Axboe22e2c502005-06-27 10:55:12 +02001074
1075 return dispatched;
1076}
1077
Jens Axboefebffd62008-01-28 13:19:43 +01001078static int __cfq_forced_dispatch_cfqq(struct cfq_queue *cfqq)
Jens Axboed9e76202007-04-20 14:27:50 +02001079{
1080 int dispatched = 0;
1081
1082 while (cfqq->next_rq) {
1083 cfq_dispatch_insert(cfqq->cfqd->queue, cfqq->next_rq);
1084 dispatched++;
1085 }
1086
1087 BUG_ON(!list_empty(&cfqq->fifo));
1088 return dispatched;
1089}
1090
Jens Axboe498d3aa2007-04-26 12:54:48 +02001091/*
1092 * Drain our current requests. Used for barriers and when switching
1093 * io schedulers on-the-fly.
1094 */
Jens Axboed9e76202007-04-20 14:27:50 +02001095static int cfq_forced_dispatch(struct cfq_data *cfqd)
Tejun Heo1b5ed5e12005-11-10 08:49:19 +01001096{
Jens Axboe08717142008-01-28 11:38:15 +01001097 struct cfq_queue *cfqq;
Jens Axboed9e76202007-04-20 14:27:50 +02001098 int dispatched = 0;
Tejun Heo1b5ed5e12005-11-10 08:49:19 +01001099
Jens Axboe08717142008-01-28 11:38:15 +01001100 while ((cfqq = cfq_rb_first(&cfqd->service_tree)) != NULL)
Jens Axboed9e76202007-04-20 14:27:50 +02001101 dispatched += __cfq_forced_dispatch_cfqq(cfqq);
Tejun Heo1b5ed5e12005-11-10 08:49:19 +01001102
Jens Axboe6084cdd2007-04-23 08:25:00 +02001103 cfq_slice_expired(cfqd, 0);
Tejun Heo1b5ed5e12005-11-10 08:49:19 +01001104
1105 BUG_ON(cfqd->busy_queues);
1106
Jens Axboe7b679132008-05-30 12:23:07 +02001107 cfq_log(cfqd, "forced_dispatch=%d\n", dispatched);
Tejun Heo1b5ed5e12005-11-10 08:49:19 +01001108 return dispatched;
1109}
1110
Jens Axboe165125e2007-07-24 09:28:11 +02001111static int cfq_dispatch_requests(struct request_queue *q, int force)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001112{
1113 struct cfq_data *cfqd = q->elevator->elevator_data;
Jens Axboe6d048f52007-04-25 12:44:27 +02001114 struct cfq_queue *cfqq;
Jens Axboecaaa5f92006-06-16 11:23:00 +02001115 int dispatched;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001116
Jens Axboe22e2c502005-06-27 10:55:12 +02001117 if (!cfqd->busy_queues)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001118 return 0;
1119
Tejun Heo1b5ed5e12005-11-10 08:49:19 +01001120 if (unlikely(force))
1121 return cfq_forced_dispatch(cfqd);
1122
Jens Axboecaaa5f92006-06-16 11:23:00 +02001123 dispatched = 0;
Jens Axboecaaa5f92006-06-16 11:23:00 +02001124 while ((cfqq = cfq_select_queue(cfqd)) != NULL) {
Jens Axboeb4878f22005-10-20 16:42:29 +02001125 int max_dispatch;
1126
Jens Axboe3ed9a292007-04-23 08:33:33 +02001127 max_dispatch = cfqd->cfq_quantum;
1128 if (cfq_class_idle(cfqq))
1129 max_dispatch = 1;
1130
1131 if (cfqq->dispatched >= max_dispatch) {
1132 if (cfqd->busy_queues > 1)
Jens Axboe6d048f52007-04-25 12:44:27 +02001133 break;
Jens Axboe3ed9a292007-04-23 08:33:33 +02001134 if (cfqq->dispatched >= 4 * max_dispatch)
Jens Axboea9938002007-04-20 08:55:52 +02001135 break;
1136 }
Jens Axboe9ede2092007-01-19 12:11:44 +11001137
Jens Axboe3ed9a292007-04-23 08:33:33 +02001138 if (cfqd->sync_flight && !cfq_cfqq_sync(cfqq))
1139 break;
1140
Jens Axboe3b181522005-06-27 10:56:24 +02001141 cfq_clear_cfqq_must_dispatch(cfqq);
1142 cfq_clear_cfqq_wait_request(cfqq);
Jens Axboe22e2c502005-06-27 10:55:12 +02001143 del_timer(&cfqd->idle_slice_timer);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001144
Jens Axboecaaa5f92006-06-16 11:23:00 +02001145 dispatched += __cfq_dispatch_requests(cfqd, cfqq, max_dispatch);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001146 }
1147
Jens Axboe7b679132008-05-30 12:23:07 +02001148 cfq_log(cfqd, "dispatched=%d", dispatched);
Jens Axboecaaa5f92006-06-16 11:23:00 +02001149 return dispatched;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001150}
1151
Linus Torvalds1da177e2005-04-16 15:20:36 -07001152/*
Jens Axboe5e705372006-07-13 12:39:25 +02001153 * task holds one reference to the queue, dropped when task exits. each rq
1154 * in-flight on this queue also holds a reference, dropped when rq is freed.
Linus Torvalds1da177e2005-04-16 15:20:36 -07001155 *
1156 * queue lock must be held here.
1157 */
1158static void cfq_put_queue(struct cfq_queue *cfqq)
1159{
Jens Axboe22e2c502005-06-27 10:55:12 +02001160 struct cfq_data *cfqd = cfqq->cfqd;
1161
1162 BUG_ON(atomic_read(&cfqq->ref) <= 0);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001163
1164 if (!atomic_dec_and_test(&cfqq->ref))
1165 return;
1166
Jens Axboe7b679132008-05-30 12:23:07 +02001167 cfq_log_cfqq(cfqd, cfqq, "put_queue");
Linus Torvalds1da177e2005-04-16 15:20:36 -07001168 BUG_ON(rb_first(&cfqq->sort_list));
Jens Axboe22e2c502005-06-27 10:55:12 +02001169 BUG_ON(cfqq->allocated[READ] + cfqq->allocated[WRITE]);
Jens Axboe3b181522005-06-27 10:56:24 +02001170 BUG_ON(cfq_cfqq_on_rr(cfqq));
Linus Torvalds1da177e2005-04-16 15:20:36 -07001171
Jens Axboe28f95cbc2007-01-19 12:09:53 +11001172 if (unlikely(cfqd->active_queue == cfqq)) {
Jens Axboe6084cdd2007-04-23 08:25:00 +02001173 __cfq_slice_expired(cfqd, cfqq, 0);
Jens Axboe28f95cbc2007-01-19 12:09:53 +11001174 cfq_schedule_dispatch(cfqd);
1175 }
Jens Axboe22e2c502005-06-27 10:55:12 +02001176
Linus Torvalds1da177e2005-04-16 15:20:36 -07001177 kmem_cache_free(cfq_pool, cfqq);
1178}
1179
Jens Axboed6de8be2008-05-28 14:46:59 +02001180/*
1181 * Must always be called with the rcu_read_lock() held
1182 */
Jens Axboe07416d22008-05-07 09:17:12 +02001183static void
1184__call_for_each_cic(struct io_context *ioc,
1185 void (*func)(struct io_context *, struct cfq_io_context *))
1186{
1187 struct cfq_io_context *cic;
1188 struct hlist_node *n;
1189
1190 hlist_for_each_entry_rcu(cic, n, &ioc->cic_list, cic_list)
1191 func(ioc, cic);
1192}
1193
Jens Axboe4ac845a2008-01-24 08:44:49 +01001194/*
Fabio Checconi34e6bbf2008-04-02 14:31:02 +02001195 * Call func for each cic attached to this ioc.
Jens Axboe4ac845a2008-01-24 08:44:49 +01001196 */
Fabio Checconi34e6bbf2008-04-02 14:31:02 +02001197static void
Jens Axboe4ac845a2008-01-24 08:44:49 +01001198call_for_each_cic(struct io_context *ioc,
1199 void (*func)(struct io_context *, struct cfq_io_context *))
1200{
Jens Axboe4ac845a2008-01-24 08:44:49 +01001201 rcu_read_lock();
Jens Axboe07416d22008-05-07 09:17:12 +02001202 __call_for_each_cic(ioc, func);
Jens Axboe4ac845a2008-01-24 08:44:49 +01001203 rcu_read_unlock();
Fabio Checconi34e6bbf2008-04-02 14:31:02 +02001204}
Jens Axboe4ac845a2008-01-24 08:44:49 +01001205
Fabio Checconi34e6bbf2008-04-02 14:31:02 +02001206static void cfq_cic_free_rcu(struct rcu_head *head)
1207{
1208 struct cfq_io_context *cic;
1209
1210 cic = container_of(head, struct cfq_io_context, rcu_head);
1211
1212 kmem_cache_free(cfq_ioc_pool, cic);
1213 elv_ioc_count_dec(ioc_count);
1214
Jens Axboe9a11b4e2008-05-29 09:32:08 +02001215 if (ioc_gone) {
1216 /*
1217 * CFQ scheduler is exiting, grab exit lock and check
1218 * the pending io context count. If it hits zero,
1219 * complete ioc_gone and set it back to NULL
1220 */
1221 spin_lock(&ioc_gone_lock);
1222 if (ioc_gone && !elv_ioc_count_read(ioc_count)) {
1223 complete(ioc_gone);
1224 ioc_gone = NULL;
1225 }
1226 spin_unlock(&ioc_gone_lock);
1227 }
Fabio Checconi34e6bbf2008-04-02 14:31:02 +02001228}
1229
1230static void cfq_cic_free(struct cfq_io_context *cic)
1231{
1232 call_rcu(&cic->rcu_head, cfq_cic_free_rcu);
Jens Axboe4ac845a2008-01-24 08:44:49 +01001233}
1234
1235static void cic_free_func(struct io_context *ioc, struct cfq_io_context *cic)
1236{
1237 unsigned long flags;
1238
1239 BUG_ON(!cic->dead_key);
1240
1241 spin_lock_irqsave(&ioc->lock, flags);
1242 radix_tree_delete(&ioc->radix_root, cic->dead_key);
Jens Axboeffc4e752008-02-19 10:02:29 +01001243 hlist_del_rcu(&cic->cic_list);
Jens Axboe4ac845a2008-01-24 08:44:49 +01001244 spin_unlock_irqrestore(&ioc->lock, flags);
1245
Fabio Checconi34e6bbf2008-04-02 14:31:02 +02001246 cfq_cic_free(cic);
Jens Axboe4ac845a2008-01-24 08:44:49 +01001247}
1248
Jens Axboed6de8be2008-05-28 14:46:59 +02001249/*
1250 * Must be called with rcu_read_lock() held or preemption otherwise disabled.
1251 * Only two callers of this - ->dtor() which is called with the rcu_read_lock(),
1252 * and ->trim() which is called with the task lock held
1253 */
Jens Axboee2d74ac2006-03-28 08:59:01 +02001254static void cfq_free_io_context(struct io_context *ioc)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001255{
Jens Axboe4ac845a2008-01-24 08:44:49 +01001256 /*
Fabio Checconi34e6bbf2008-04-02 14:31:02 +02001257 * ioc->refcount is zero here, or we are called from elv_unregister(),
1258 * so no more cic's are allowed to be linked into this ioc. So it
1259 * should be ok to iterate over the known list, we will see all cic's
1260 * since no new ones are added.
Jens Axboe4ac845a2008-01-24 08:44:49 +01001261 */
Jens Axboe07416d22008-05-07 09:17:12 +02001262 __call_for_each_cic(ioc, cic_free_func);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001263}
1264
Jens Axboe89850f72006-07-22 16:48:31 +02001265static void cfq_exit_cfqq(struct cfq_data *cfqd, struct cfq_queue *cfqq)
1266{
Jens Axboe28f95cbc2007-01-19 12:09:53 +11001267 if (unlikely(cfqq == cfqd->active_queue)) {
Jens Axboe6084cdd2007-04-23 08:25:00 +02001268 __cfq_slice_expired(cfqd, cfqq, 0);
Jens Axboe28f95cbc2007-01-19 12:09:53 +11001269 cfq_schedule_dispatch(cfqd);
1270 }
Jens Axboe89850f72006-07-22 16:48:31 +02001271
1272 cfq_put_queue(cfqq);
1273}
1274
1275static void __cfq_exit_single_io_context(struct cfq_data *cfqd,
1276 struct cfq_io_context *cic)
1277{
Fabio Checconi4faa3c82008-04-10 08:28:01 +02001278 struct io_context *ioc = cic->ioc;
1279
Jens Axboefc463792006-08-29 09:05:44 +02001280 list_del_init(&cic->queue_list);
Jens Axboe4ac845a2008-01-24 08:44:49 +01001281
1282 /*
1283 * Make sure key == NULL is seen for dead queues
1284 */
Jens Axboefc463792006-08-29 09:05:44 +02001285 smp_wmb();
Jens Axboe4ac845a2008-01-24 08:44:49 +01001286 cic->dead_key = (unsigned long) cic->key;
Jens Axboefc463792006-08-29 09:05:44 +02001287 cic->key = NULL;
1288
Fabio Checconi4faa3c82008-04-10 08:28:01 +02001289 if (ioc->ioc_data == cic)
1290 rcu_assign_pointer(ioc->ioc_data, NULL);
1291
Jens Axboe89850f72006-07-22 16:48:31 +02001292 if (cic->cfqq[ASYNC]) {
1293 cfq_exit_cfqq(cfqd, cic->cfqq[ASYNC]);
1294 cic->cfqq[ASYNC] = NULL;
1295 }
1296
1297 if (cic->cfqq[SYNC]) {
1298 cfq_exit_cfqq(cfqd, cic->cfqq[SYNC]);
1299 cic->cfqq[SYNC] = NULL;
1300 }
Jens Axboe89850f72006-07-22 16:48:31 +02001301}
1302
Jens Axboe4ac845a2008-01-24 08:44:49 +01001303static void cfq_exit_single_io_context(struct io_context *ioc,
1304 struct cfq_io_context *cic)
Jens Axboe22e2c502005-06-27 10:55:12 +02001305{
Al Viro478a82b2006-03-18 13:25:24 -05001306 struct cfq_data *cfqd = cic->key;
Jens Axboe22e2c502005-06-27 10:55:12 +02001307
Jens Axboe89850f72006-07-22 16:48:31 +02001308 if (cfqd) {
Jens Axboe165125e2007-07-24 09:28:11 +02001309 struct request_queue *q = cfqd->queue;
Jens Axboe4ac845a2008-01-24 08:44:49 +01001310 unsigned long flags;
Jens Axboe22e2c502005-06-27 10:55:12 +02001311
Jens Axboe4ac845a2008-01-24 08:44:49 +01001312 spin_lock_irqsave(q->queue_lock, flags);
Jens Axboe89850f72006-07-22 16:48:31 +02001313 __cfq_exit_single_io_context(cfqd, cic);
Jens Axboe4ac845a2008-01-24 08:44:49 +01001314 spin_unlock_irqrestore(q->queue_lock, flags);
Al Viro12a05732006-03-18 13:38:01 -05001315 }
Jens Axboe22e2c502005-06-27 10:55:12 +02001316}
1317
Jens Axboe498d3aa2007-04-26 12:54:48 +02001318/*
1319 * The process that ioc belongs to has exited, we need to clean up
1320 * and put the internal structures we have that belongs to that process.
1321 */
Jens Axboee2d74ac2006-03-28 08:59:01 +02001322static void cfq_exit_io_context(struct io_context *ioc)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001323{
Jens Axboe4ac845a2008-01-24 08:44:49 +01001324 call_for_each_cic(ioc, cfq_exit_single_io_context);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001325}
1326
Jens Axboe22e2c502005-06-27 10:55:12 +02001327static struct cfq_io_context *
Al Viro8267e262005-10-21 03:20:53 -04001328cfq_alloc_io_context(struct cfq_data *cfqd, gfp_t gfp_mask)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001329{
Jens Axboeb5deef92006-07-19 23:39:40 +02001330 struct cfq_io_context *cic;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001331
Christoph Lameter94f60302007-07-17 04:03:29 -07001332 cic = kmem_cache_alloc_node(cfq_ioc_pool, gfp_mask | __GFP_ZERO,
1333 cfqd->queue->node);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001334 if (cic) {
Jens Axboe22e2c502005-06-27 10:55:12 +02001335 cic->last_end_request = jiffies;
Jens Axboe553698f2006-06-14 19:11:57 +02001336 INIT_LIST_HEAD(&cic->queue_list);
Jens Axboeffc4e752008-02-19 10:02:29 +01001337 INIT_HLIST_NODE(&cic->cic_list);
Jens Axboe22e2c502005-06-27 10:55:12 +02001338 cic->dtor = cfq_free_io_context;
1339 cic->exit = cfq_exit_io_context;
Jens Axboe4050cf12006-07-19 05:07:12 +02001340 elv_ioc_count_inc(ioc_count);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001341 }
1342
1343 return cic;
1344}
1345
Jens Axboefd0928d2008-01-24 08:52:45 +01001346static void cfq_init_prio_data(struct cfq_queue *cfqq, struct io_context *ioc)
Jens Axboe22e2c502005-06-27 10:55:12 +02001347{
1348 struct task_struct *tsk = current;
1349 int ioprio_class;
1350
Jens Axboe3b181522005-06-27 10:56:24 +02001351 if (!cfq_cfqq_prio_changed(cfqq))
Jens Axboe22e2c502005-06-27 10:55:12 +02001352 return;
1353
Jens Axboefd0928d2008-01-24 08:52:45 +01001354 ioprio_class = IOPRIO_PRIO_CLASS(ioc->ioprio);
Jens Axboe22e2c502005-06-27 10:55:12 +02001355 switch (ioprio_class) {
Jens Axboefe094d92008-01-31 13:08:54 +01001356 default:
1357 printk(KERN_ERR "cfq: bad prio %x\n", ioprio_class);
1358 case IOPRIO_CLASS_NONE:
1359 /*
Jens Axboe6d63c272008-05-07 09:51:23 +02001360 * no prio set, inherit CPU scheduling settings
Jens Axboefe094d92008-01-31 13:08:54 +01001361 */
1362 cfqq->ioprio = task_nice_ioprio(tsk);
Jens Axboe6d63c272008-05-07 09:51:23 +02001363 cfqq->ioprio_class = task_nice_ioclass(tsk);
Jens Axboefe094d92008-01-31 13:08:54 +01001364 break;
1365 case IOPRIO_CLASS_RT:
1366 cfqq->ioprio = task_ioprio(ioc);
1367 cfqq->ioprio_class = IOPRIO_CLASS_RT;
1368 break;
1369 case IOPRIO_CLASS_BE:
1370 cfqq->ioprio = task_ioprio(ioc);
1371 cfqq->ioprio_class = IOPRIO_CLASS_BE;
1372 break;
1373 case IOPRIO_CLASS_IDLE:
1374 cfqq->ioprio_class = IOPRIO_CLASS_IDLE;
1375 cfqq->ioprio = 7;
1376 cfq_clear_cfqq_idle_window(cfqq);
1377 break;
Jens Axboe22e2c502005-06-27 10:55:12 +02001378 }
1379
1380 /*
1381 * keep track of original prio settings in case we have to temporarily
1382 * elevate the priority of this queue
1383 */
1384 cfqq->org_ioprio = cfqq->ioprio;
1385 cfqq->org_ioprio_class = cfqq->ioprio_class;
Jens Axboe3b181522005-06-27 10:56:24 +02001386 cfq_clear_cfqq_prio_changed(cfqq);
Jens Axboe22e2c502005-06-27 10:55:12 +02001387}
1388
Jens Axboefebffd62008-01-28 13:19:43 +01001389static void changed_ioprio(struct io_context *ioc, struct cfq_io_context *cic)
Jens Axboe22e2c502005-06-27 10:55:12 +02001390{
Al Viro478a82b2006-03-18 13:25:24 -05001391 struct cfq_data *cfqd = cic->key;
1392 struct cfq_queue *cfqq;
Jens Axboec1b707d2006-10-30 19:54:23 +01001393 unsigned long flags;
Jens Axboe35e60772006-06-14 09:10:45 +02001394
Jens Axboecaaa5f92006-06-16 11:23:00 +02001395 if (unlikely(!cfqd))
1396 return;
1397
Jens Axboec1b707d2006-10-30 19:54:23 +01001398 spin_lock_irqsave(cfqd->queue->queue_lock, flags);
Jens Axboecaaa5f92006-06-16 11:23:00 +02001399
1400 cfqq = cic->cfqq[ASYNC];
1401 if (cfqq) {
1402 struct cfq_queue *new_cfqq;
Jens Axboefd0928d2008-01-24 08:52:45 +01001403 new_cfqq = cfq_get_queue(cfqd, ASYNC, cic->ioc, GFP_ATOMIC);
Jens Axboecaaa5f92006-06-16 11:23:00 +02001404 if (new_cfqq) {
1405 cic->cfqq[ASYNC] = new_cfqq;
1406 cfq_put_queue(cfqq);
1407 }
Jens Axboe22e2c502005-06-27 10:55:12 +02001408 }
Jens Axboecaaa5f92006-06-16 11:23:00 +02001409
1410 cfqq = cic->cfqq[SYNC];
1411 if (cfqq)
1412 cfq_mark_cfqq_prio_changed(cfqq);
1413
Jens Axboec1b707d2006-10-30 19:54:23 +01001414 spin_unlock_irqrestore(cfqd->queue->queue_lock, flags);
Jens Axboe22e2c502005-06-27 10:55:12 +02001415}
1416
Jens Axboefc463792006-08-29 09:05:44 +02001417static void cfq_ioc_set_ioprio(struct io_context *ioc)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001418{
Jens Axboe4ac845a2008-01-24 08:44:49 +01001419 call_for_each_cic(ioc, changed_ioprio);
Jens Axboefc463792006-08-29 09:05:44 +02001420 ioc->ioprio_changed = 0;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001421}
1422
1423static struct cfq_queue *
Jens Axboe15c31be2007-07-10 13:43:25 +02001424cfq_find_alloc_queue(struct cfq_data *cfqd, int is_sync,
Jens Axboefd0928d2008-01-24 08:52:45 +01001425 struct io_context *ioc, gfp_t gfp_mask)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001426{
Linus Torvalds1da177e2005-04-16 15:20:36 -07001427 struct cfq_queue *cfqq, *new_cfqq = NULL;
Vasily Tarasov91fac312007-04-25 12:29:51 +02001428 struct cfq_io_context *cic;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001429
1430retry:
Jens Axboe4ac845a2008-01-24 08:44:49 +01001431 cic = cfq_cic_lookup(cfqd, ioc);
Vasily Tarasov91fac312007-04-25 12:29:51 +02001432 /* cic always exists here */
1433 cfqq = cic_to_cfqq(cic, is_sync);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001434
1435 if (!cfqq) {
1436 if (new_cfqq) {
1437 cfqq = new_cfqq;
1438 new_cfqq = NULL;
Jens Axboe22e2c502005-06-27 10:55:12 +02001439 } else if (gfp_mask & __GFP_WAIT) {
Jens Axboe89850f72006-07-22 16:48:31 +02001440 /*
1441 * Inform the allocator of the fact that we will
1442 * just repeat this allocation if it fails, to allow
1443 * the allocator to do whatever it needs to attempt to
1444 * free memory.
1445 */
Linus Torvalds1da177e2005-04-16 15:20:36 -07001446 spin_unlock_irq(cfqd->queue->queue_lock);
Christoph Lameter94f60302007-07-17 04:03:29 -07001447 new_cfqq = kmem_cache_alloc_node(cfq_pool,
1448 gfp_mask | __GFP_NOFAIL | __GFP_ZERO,
1449 cfqd->queue->node);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001450 spin_lock_irq(cfqd->queue->queue_lock);
1451 goto retry;
Jens Axboe22e2c502005-06-27 10:55:12 +02001452 } else {
Christoph Lameter94f60302007-07-17 04:03:29 -07001453 cfqq = kmem_cache_alloc_node(cfq_pool,
1454 gfp_mask | __GFP_ZERO,
1455 cfqd->queue->node);
Jens Axboe22e2c502005-06-27 10:55:12 +02001456 if (!cfqq)
1457 goto out;
Kiyoshi Ueda db3b5842005-06-17 16:15:10 +02001458 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07001459
Jens Axboed9e76202007-04-20 14:27:50 +02001460 RB_CLEAR_NODE(&cfqq->rb_node);
Jens Axboe22e2c502005-06-27 10:55:12 +02001461 INIT_LIST_HEAD(&cfqq->fifo);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001462
Linus Torvalds1da177e2005-04-16 15:20:36 -07001463 atomic_set(&cfqq->ref, 0);
1464 cfqq->cfqd = cfqd;
Jens Axboec5b680f2007-01-19 11:56:49 +11001465
Jens Axboe3b181522005-06-27 10:56:24 +02001466 cfq_mark_cfqq_prio_changed(cfqq);
Jens Axboe53b03742006-07-28 09:48:51 +02001467 cfq_mark_cfqq_queue_new(cfqq);
Vasily Tarasov91fac312007-04-25 12:29:51 +02001468
Jens Axboefd0928d2008-01-24 08:52:45 +01001469 cfq_init_prio_data(cfqq, ioc);
Jens Axboe08717142008-01-28 11:38:15 +01001470
1471 if (is_sync) {
1472 if (!cfq_class_idle(cfqq))
1473 cfq_mark_cfqq_idle_window(cfqq);
1474 cfq_mark_cfqq_sync(cfqq);
1475 }
Jens Axboe7b679132008-05-30 12:23:07 +02001476 cfqq->pid = current->pid;
1477 cfq_log_cfqq(cfqd, cfqq, "alloced");
Linus Torvalds1da177e2005-04-16 15:20:36 -07001478 }
1479
1480 if (new_cfqq)
1481 kmem_cache_free(cfq_pool, new_cfqq);
1482
Linus Torvalds1da177e2005-04-16 15:20:36 -07001483out:
1484 WARN_ON((gfp_mask & __GFP_WAIT) && !cfqq);
1485 return cfqq;
1486}
1487
Vasily Tarasovc2dea2d2007-07-20 10:06:38 +02001488static struct cfq_queue **
1489cfq_async_queue_prio(struct cfq_data *cfqd, int ioprio_class, int ioprio)
1490{
Jens Axboefe094d92008-01-31 13:08:54 +01001491 switch (ioprio_class) {
Vasily Tarasovc2dea2d2007-07-20 10:06:38 +02001492 case IOPRIO_CLASS_RT:
1493 return &cfqd->async_cfqq[0][ioprio];
1494 case IOPRIO_CLASS_BE:
1495 return &cfqd->async_cfqq[1][ioprio];
1496 case IOPRIO_CLASS_IDLE:
1497 return &cfqd->async_idle_cfqq;
1498 default:
1499 BUG();
1500 }
1501}
1502
Jens Axboe15c31be2007-07-10 13:43:25 +02001503static struct cfq_queue *
Jens Axboefd0928d2008-01-24 08:52:45 +01001504cfq_get_queue(struct cfq_data *cfqd, int is_sync, struct io_context *ioc,
Jens Axboe15c31be2007-07-10 13:43:25 +02001505 gfp_t gfp_mask)
1506{
Jens Axboefd0928d2008-01-24 08:52:45 +01001507 const int ioprio = task_ioprio(ioc);
1508 const int ioprio_class = task_ioprio_class(ioc);
Vasily Tarasovc2dea2d2007-07-20 10:06:38 +02001509 struct cfq_queue **async_cfqq = NULL;
Jens Axboe15c31be2007-07-10 13:43:25 +02001510 struct cfq_queue *cfqq = NULL;
1511
Vasily Tarasovc2dea2d2007-07-20 10:06:38 +02001512 if (!is_sync) {
1513 async_cfqq = cfq_async_queue_prio(cfqd, ioprio_class, ioprio);
1514 cfqq = *async_cfqq;
1515 }
1516
Oleg Nesterov0a0836a2007-10-23 15:08:21 +02001517 if (!cfqq) {
Jens Axboefd0928d2008-01-24 08:52:45 +01001518 cfqq = cfq_find_alloc_queue(cfqd, is_sync, ioc, gfp_mask);
Oleg Nesterov0a0836a2007-10-23 15:08:21 +02001519 if (!cfqq)
1520 return NULL;
1521 }
Jens Axboe15c31be2007-07-10 13:43:25 +02001522
1523 /*
1524 * pin the queue now that it's allocated, scheduler exit will prune it
1525 */
Vasily Tarasovc2dea2d2007-07-20 10:06:38 +02001526 if (!is_sync && !(*async_cfqq)) {
Jens Axboe15c31be2007-07-10 13:43:25 +02001527 atomic_inc(&cfqq->ref);
Vasily Tarasovc2dea2d2007-07-20 10:06:38 +02001528 *async_cfqq = cfqq;
Jens Axboe15c31be2007-07-10 13:43:25 +02001529 }
1530
1531 atomic_inc(&cfqq->ref);
1532 return cfqq;
1533}
1534
Jens Axboe498d3aa2007-04-26 12:54:48 +02001535/*
1536 * We drop cfq io contexts lazily, so we may find a dead one.
1537 */
OGAWA Hirofumidbecf3a2006-04-18 09:45:18 +02001538static void
Jens Axboe4ac845a2008-01-24 08:44:49 +01001539cfq_drop_dead_cic(struct cfq_data *cfqd, struct io_context *ioc,
1540 struct cfq_io_context *cic)
OGAWA Hirofumidbecf3a2006-04-18 09:45:18 +02001541{
Jens Axboe4ac845a2008-01-24 08:44:49 +01001542 unsigned long flags;
1543
Jens Axboefc463792006-08-29 09:05:44 +02001544 WARN_ON(!list_empty(&cic->queue_list));
Jens Axboe597bc482007-04-24 21:23:53 +02001545
Jens Axboe4ac845a2008-01-24 08:44:49 +01001546 spin_lock_irqsave(&ioc->lock, flags);
Jens Axboe597bc482007-04-24 21:23:53 +02001547
Fabio Checconi4faa3c82008-04-10 08:28:01 +02001548 BUG_ON(ioc->ioc_data == cic);
Jens Axboe4ac845a2008-01-24 08:44:49 +01001549
1550 radix_tree_delete(&ioc->radix_root, (unsigned long) cfqd);
Jens Axboeffc4e752008-02-19 10:02:29 +01001551 hlist_del_rcu(&cic->cic_list);
Jens Axboe4ac845a2008-01-24 08:44:49 +01001552 spin_unlock_irqrestore(&ioc->lock, flags);
1553
1554 cfq_cic_free(cic);
OGAWA Hirofumidbecf3a2006-04-18 09:45:18 +02001555}
1556
Jens Axboee2d74ac2006-03-28 08:59:01 +02001557static struct cfq_io_context *
Jens Axboe4ac845a2008-01-24 08:44:49 +01001558cfq_cic_lookup(struct cfq_data *cfqd, struct io_context *ioc)
Jens Axboee2d74ac2006-03-28 08:59:01 +02001559{
Jens Axboee2d74ac2006-03-28 08:59:01 +02001560 struct cfq_io_context *cic;
Jens Axboed6de8be2008-05-28 14:46:59 +02001561 unsigned long flags;
Jens Axboe4ac845a2008-01-24 08:44:49 +01001562 void *k;
Jens Axboee2d74ac2006-03-28 08:59:01 +02001563
Vasily Tarasov91fac312007-04-25 12:29:51 +02001564 if (unlikely(!ioc))
1565 return NULL;
1566
Jens Axboed6de8be2008-05-28 14:46:59 +02001567 rcu_read_lock();
1568
Jens Axboe597bc482007-04-24 21:23:53 +02001569 /*
1570 * we maintain a last-hit cache, to avoid browsing over the tree
1571 */
Jens Axboe4ac845a2008-01-24 08:44:49 +01001572 cic = rcu_dereference(ioc->ioc_data);
Jens Axboed6de8be2008-05-28 14:46:59 +02001573 if (cic && cic->key == cfqd) {
1574 rcu_read_unlock();
Jens Axboe597bc482007-04-24 21:23:53 +02001575 return cic;
Jens Axboed6de8be2008-05-28 14:46:59 +02001576 }
Jens Axboe597bc482007-04-24 21:23:53 +02001577
Jens Axboe4ac845a2008-01-24 08:44:49 +01001578 do {
Jens Axboe4ac845a2008-01-24 08:44:49 +01001579 cic = radix_tree_lookup(&ioc->radix_root, (unsigned long) cfqd);
1580 rcu_read_unlock();
1581 if (!cic)
1582 break;
OGAWA Hirofumibe3b0752006-04-18 19:18:31 +02001583 /* ->key must be copied to avoid race with cfq_exit_queue() */
1584 k = cic->key;
1585 if (unlikely(!k)) {
Jens Axboe4ac845a2008-01-24 08:44:49 +01001586 cfq_drop_dead_cic(cfqd, ioc, cic);
Jens Axboed6de8be2008-05-28 14:46:59 +02001587 rcu_read_lock();
Jens Axboe4ac845a2008-01-24 08:44:49 +01001588 continue;
OGAWA Hirofumidbecf3a2006-04-18 09:45:18 +02001589 }
Jens Axboee2d74ac2006-03-28 08:59:01 +02001590
Jens Axboed6de8be2008-05-28 14:46:59 +02001591 spin_lock_irqsave(&ioc->lock, flags);
Jens Axboe4ac845a2008-01-24 08:44:49 +01001592 rcu_assign_pointer(ioc->ioc_data, cic);
Jens Axboed6de8be2008-05-28 14:46:59 +02001593 spin_unlock_irqrestore(&ioc->lock, flags);
Jens Axboe4ac845a2008-01-24 08:44:49 +01001594 break;
1595 } while (1);
Jens Axboee2d74ac2006-03-28 08:59:01 +02001596
Jens Axboe4ac845a2008-01-24 08:44:49 +01001597 return cic;
Jens Axboee2d74ac2006-03-28 08:59:01 +02001598}
1599
Jens Axboe4ac845a2008-01-24 08:44:49 +01001600/*
1601 * Add cic into ioc, using cfqd as the search key. This enables us to lookup
1602 * the process specific cfq io context when entered from the block layer.
1603 * Also adds the cic to a per-cfqd list, used when this queue is removed.
1604 */
Jens Axboefebffd62008-01-28 13:19:43 +01001605static int cfq_cic_link(struct cfq_data *cfqd, struct io_context *ioc,
1606 struct cfq_io_context *cic, gfp_t gfp_mask)
Jens Axboee2d74ac2006-03-28 08:59:01 +02001607{
Jens Axboe0261d682006-10-30 19:07:48 +01001608 unsigned long flags;
Jens Axboe4ac845a2008-01-24 08:44:49 +01001609 int ret;
Jens Axboee2d74ac2006-03-28 08:59:01 +02001610
Jens Axboe4ac845a2008-01-24 08:44:49 +01001611 ret = radix_tree_preload(gfp_mask);
1612 if (!ret) {
1613 cic->ioc = ioc;
1614 cic->key = cfqd;
Jens Axboee2d74ac2006-03-28 08:59:01 +02001615
Jens Axboe4ac845a2008-01-24 08:44:49 +01001616 spin_lock_irqsave(&ioc->lock, flags);
1617 ret = radix_tree_insert(&ioc->radix_root,
1618 (unsigned long) cfqd, cic);
Jens Axboeffc4e752008-02-19 10:02:29 +01001619 if (!ret)
1620 hlist_add_head_rcu(&cic->cic_list, &ioc->cic_list);
Jens Axboe4ac845a2008-01-24 08:44:49 +01001621 spin_unlock_irqrestore(&ioc->lock, flags);
1622
1623 radix_tree_preload_end();
1624
1625 if (!ret) {
1626 spin_lock_irqsave(cfqd->queue->queue_lock, flags);
1627 list_add(&cic->queue_list, &cfqd->cic_list);
1628 spin_unlock_irqrestore(cfqd->queue->queue_lock, flags);
OGAWA Hirofumidbecf3a2006-04-18 09:45:18 +02001629 }
Jens Axboee2d74ac2006-03-28 08:59:01 +02001630 }
1631
Jens Axboe4ac845a2008-01-24 08:44:49 +01001632 if (ret)
1633 printk(KERN_ERR "cfq: cic link failed!\n");
Jens Axboefc463792006-08-29 09:05:44 +02001634
Jens Axboe4ac845a2008-01-24 08:44:49 +01001635 return ret;
Jens Axboee2d74ac2006-03-28 08:59:01 +02001636}
1637
Jens Axboe22e2c502005-06-27 10:55:12 +02001638/*
1639 * Setup general io context and cfq io context. There can be several cfq
1640 * io contexts per general io context, if this process is doing io to more
Jens Axboee2d74ac2006-03-28 08:59:01 +02001641 * than one device managed by cfq.
Jens Axboe22e2c502005-06-27 10:55:12 +02001642 */
1643static struct cfq_io_context *
Jens Axboee2d74ac2006-03-28 08:59:01 +02001644cfq_get_io_context(struct cfq_data *cfqd, gfp_t gfp_mask)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001645{
Jens Axboe22e2c502005-06-27 10:55:12 +02001646 struct io_context *ioc = NULL;
1647 struct cfq_io_context *cic;
1648
1649 might_sleep_if(gfp_mask & __GFP_WAIT);
1650
Jens Axboeb5deef92006-07-19 23:39:40 +02001651 ioc = get_io_context(gfp_mask, cfqd->queue->node);
Jens Axboe22e2c502005-06-27 10:55:12 +02001652 if (!ioc)
1653 return NULL;
1654
Jens Axboe4ac845a2008-01-24 08:44:49 +01001655 cic = cfq_cic_lookup(cfqd, ioc);
Jens Axboee2d74ac2006-03-28 08:59:01 +02001656 if (cic)
1657 goto out;
Jens Axboe22e2c502005-06-27 10:55:12 +02001658
Jens Axboee2d74ac2006-03-28 08:59:01 +02001659 cic = cfq_alloc_io_context(cfqd, gfp_mask);
1660 if (cic == NULL)
1661 goto err;
Jens Axboe22e2c502005-06-27 10:55:12 +02001662
Jens Axboe4ac845a2008-01-24 08:44:49 +01001663 if (cfq_cic_link(cfqd, ioc, cic, gfp_mask))
1664 goto err_free;
1665
Jens Axboe22e2c502005-06-27 10:55:12 +02001666out:
Jens Axboefc463792006-08-29 09:05:44 +02001667 smp_read_barrier_depends();
1668 if (unlikely(ioc->ioprio_changed))
1669 cfq_ioc_set_ioprio(ioc);
1670
Jens Axboe22e2c502005-06-27 10:55:12 +02001671 return cic;
Jens Axboe4ac845a2008-01-24 08:44:49 +01001672err_free:
1673 cfq_cic_free(cic);
Jens Axboe22e2c502005-06-27 10:55:12 +02001674err:
1675 put_io_context(ioc);
1676 return NULL;
1677}
1678
1679static void
1680cfq_update_io_thinktime(struct cfq_data *cfqd, struct cfq_io_context *cic)
1681{
Jens Axboeaaf12282007-01-19 11:30:16 +11001682 unsigned long elapsed = jiffies - cic->last_end_request;
1683 unsigned long ttime = min(elapsed, 2UL * cfqd->cfq_slice_idle);
Jens Axboe22e2c502005-06-27 10:55:12 +02001684
1685 cic->ttime_samples = (7*cic->ttime_samples + 256) / 8;
1686 cic->ttime_total = (7*cic->ttime_total + 256*ttime) / 8;
1687 cic->ttime_mean = (cic->ttime_total + 128) / cic->ttime_samples;
1688}
1689
Jens Axboe206dc692006-03-28 13:03:44 +02001690static void
Jens Axboe6d048f52007-04-25 12:44:27 +02001691cfq_update_io_seektime(struct cfq_data *cfqd, struct cfq_io_context *cic,
1692 struct request *rq)
Jens Axboe206dc692006-03-28 13:03:44 +02001693{
1694 sector_t sdist;
1695 u64 total;
1696
Jens Axboe5e705372006-07-13 12:39:25 +02001697 if (cic->last_request_pos < rq->sector)
1698 sdist = rq->sector - cic->last_request_pos;
Jens Axboe206dc692006-03-28 13:03:44 +02001699 else
Jens Axboe5e705372006-07-13 12:39:25 +02001700 sdist = cic->last_request_pos - rq->sector;
Jens Axboe206dc692006-03-28 13:03:44 +02001701
1702 /*
1703 * Don't allow the seek distance to get too large from the
1704 * odd fragment, pagein, etc
1705 */
1706 if (cic->seek_samples <= 60) /* second&third seek */
1707 sdist = min(sdist, (cic->seek_mean * 4) + 2*1024*1024);
1708 else
1709 sdist = min(sdist, (cic->seek_mean * 4) + 2*1024*64);
1710
1711 cic->seek_samples = (7*cic->seek_samples + 256) / 8;
1712 cic->seek_total = (7*cic->seek_total + (u64)256*sdist) / 8;
1713 total = cic->seek_total + (cic->seek_samples/2);
1714 do_div(total, cic->seek_samples);
1715 cic->seek_mean = (sector_t)total;
1716}
Jens Axboe22e2c502005-06-27 10:55:12 +02001717
1718/*
1719 * Disable idle window if the process thinks too long or seeks so much that
1720 * it doesn't matter
1721 */
1722static void
1723cfq_update_idle_window(struct cfq_data *cfqd, struct cfq_queue *cfqq,
1724 struct cfq_io_context *cic)
1725{
Jens Axboe7b679132008-05-30 12:23:07 +02001726 int old_idle, enable_idle;
Jens Axboe1be92f22007-04-19 14:32:26 +02001727
Jens Axboe08717142008-01-28 11:38:15 +01001728 /*
1729 * Don't idle for async or idle io prio class
1730 */
1731 if (!cfq_cfqq_sync(cfqq) || cfq_class_idle(cfqq))
Jens Axboe1be92f22007-04-19 14:32:26 +02001732 return;
1733
Jens Axboec265a7f2008-06-26 13:49:33 +02001734 enable_idle = old_idle = cfq_cfqq_idle_window(cfqq);
Jens Axboe22e2c502005-06-27 10:55:12 +02001735
Nikanth Karthikesan66dac982007-11-27 12:47:04 +01001736 if (!atomic_read(&cic->ioc->nr_tasks) || !cfqd->cfq_slice_idle ||
Jens Axboecaaa5f92006-06-16 11:23:00 +02001737 (cfqd->hw_tag && CIC_SEEKY(cic)))
Jens Axboe22e2c502005-06-27 10:55:12 +02001738 enable_idle = 0;
1739 else if (sample_valid(cic->ttime_samples)) {
1740 if (cic->ttime_mean > cfqd->cfq_slice_idle)
1741 enable_idle = 0;
1742 else
1743 enable_idle = 1;
1744 }
1745
Jens Axboe7b679132008-05-30 12:23:07 +02001746 if (old_idle != enable_idle) {
1747 cfq_log_cfqq(cfqd, cfqq, "idle=%d", enable_idle);
1748 if (enable_idle)
1749 cfq_mark_cfqq_idle_window(cfqq);
1750 else
1751 cfq_clear_cfqq_idle_window(cfqq);
1752 }
Jens Axboe22e2c502005-06-27 10:55:12 +02001753}
1754
Jens Axboe22e2c502005-06-27 10:55:12 +02001755/*
1756 * Check if new_cfqq should preempt the currently active queue. Return 0 for
1757 * no or if we aren't sure, a 1 will cause a preempt.
1758 */
1759static int
1760cfq_should_preempt(struct cfq_data *cfqd, struct cfq_queue *new_cfqq,
Jens Axboe5e705372006-07-13 12:39:25 +02001761 struct request *rq)
Jens Axboe22e2c502005-06-27 10:55:12 +02001762{
Jens Axboe6d048f52007-04-25 12:44:27 +02001763 struct cfq_queue *cfqq;
Jens Axboe22e2c502005-06-27 10:55:12 +02001764
Jens Axboe6d048f52007-04-25 12:44:27 +02001765 cfqq = cfqd->active_queue;
1766 if (!cfqq)
Jens Axboe22e2c502005-06-27 10:55:12 +02001767 return 0;
1768
Jens Axboe6d048f52007-04-25 12:44:27 +02001769 if (cfq_slice_used(cfqq))
1770 return 1;
1771
1772 if (cfq_class_idle(new_cfqq))
Jens Axboecaaa5f92006-06-16 11:23:00 +02001773 return 0;
Jens Axboe22e2c502005-06-27 10:55:12 +02001774
1775 if (cfq_class_idle(cfqq))
1776 return 1;
Jens Axboe1e3335d2007-02-14 19:59:49 +01001777
Jens Axboe22e2c502005-06-27 10:55:12 +02001778 /*
Jens Axboe374f84a2006-07-23 01:42:19 +02001779 * if the new request is sync, but the currently running queue is
1780 * not, let the sync request have priority.
1781 */
Jens Axboe5e705372006-07-13 12:39:25 +02001782 if (rq_is_sync(rq) && !cfq_cfqq_sync(cfqq))
Jens Axboe22e2c502005-06-27 10:55:12 +02001783 return 1;
Jens Axboe1e3335d2007-02-14 19:59:49 +01001784
Jens Axboe374f84a2006-07-23 01:42:19 +02001785 /*
1786 * So both queues are sync. Let the new request get disk time if
1787 * it's a metadata request and the current queue is doing regular IO.
1788 */
1789 if (rq_is_meta(rq) && !cfqq->meta_pending)
1790 return 1;
Jens Axboe22e2c502005-06-27 10:55:12 +02001791
Jens Axboe1e3335d2007-02-14 19:59:49 +01001792 if (!cfqd->active_cic || !cfq_cfqq_wait_request(cfqq))
1793 return 0;
1794
1795 /*
1796 * if this request is as-good as one we would expect from the
1797 * current cfqq, let it preempt
1798 */
Jens Axboe6d048f52007-04-25 12:44:27 +02001799 if (cfq_rq_close(cfqd, rq))
Jens Axboe1e3335d2007-02-14 19:59:49 +01001800 return 1;
1801
Jens Axboe22e2c502005-06-27 10:55:12 +02001802 return 0;
1803}
1804
1805/*
1806 * cfqq preempts the active queue. if we allowed preempt with no slice left,
1807 * let it have half of its nominal slice.
1808 */
1809static void cfq_preempt_queue(struct cfq_data *cfqd, struct cfq_queue *cfqq)
1810{
Jens Axboe7b679132008-05-30 12:23:07 +02001811 cfq_log_cfqq(cfqd, cfqq, "preempt");
Jens Axboe6084cdd2007-04-23 08:25:00 +02001812 cfq_slice_expired(cfqd, 1);
Jens Axboe22e2c502005-06-27 10:55:12 +02001813
Jens Axboebf572252006-07-19 20:29:12 +02001814 /*
1815 * Put the new queue at the front of the of the current list,
1816 * so we know that it will be selected next.
1817 */
1818 BUG_ON(!cfq_cfqq_on_rr(cfqq));
Jens Axboeedd75ff2007-04-19 12:03:34 +02001819
1820 cfq_service_tree_add(cfqd, cfqq, 1);
Jens Axboebf572252006-07-19 20:29:12 +02001821
Jens Axboe44f7c162007-01-19 11:51:58 +11001822 cfqq->slice_end = 0;
1823 cfq_mark_cfqq_slice_new(cfqq);
Jens Axboe22e2c502005-06-27 10:55:12 +02001824}
1825
1826/*
Jens Axboe5e705372006-07-13 12:39:25 +02001827 * Called when a new fs request (rq) is added (to cfqq). Check if there's
Jens Axboe22e2c502005-06-27 10:55:12 +02001828 * something we should do about it
1829 */
1830static void
Jens Axboe5e705372006-07-13 12:39:25 +02001831cfq_rq_enqueued(struct cfq_data *cfqd, struct cfq_queue *cfqq,
1832 struct request *rq)
Jens Axboe22e2c502005-06-27 10:55:12 +02001833{
Jens Axboe5e705372006-07-13 12:39:25 +02001834 struct cfq_io_context *cic = RQ_CIC(rq);
Jens Axboe12e9fdd2006-06-01 10:09:56 +02001835
Jens Axboe374f84a2006-07-23 01:42:19 +02001836 if (rq_is_meta(rq))
1837 cfqq->meta_pending++;
1838
Jens Axboe9c2c38a2005-08-24 14:57:54 +02001839 cfq_update_io_thinktime(cfqd, cic);
Jens Axboe6d048f52007-04-25 12:44:27 +02001840 cfq_update_io_seektime(cfqd, cic, rq);
Jens Axboe9c2c38a2005-08-24 14:57:54 +02001841 cfq_update_idle_window(cfqd, cfqq, cic);
1842
Jens Axboe5e705372006-07-13 12:39:25 +02001843 cic->last_request_pos = rq->sector + rq->nr_sectors;
Jens Axboe22e2c502005-06-27 10:55:12 +02001844
1845 if (cfqq == cfqd->active_queue) {
1846 /*
1847 * if we are waiting for a request for this queue, let it rip
1848 * immediately and flag that we must not expire this queue
1849 * just now
1850 */
Jens Axboe3b181522005-06-27 10:56:24 +02001851 if (cfq_cfqq_wait_request(cfqq)) {
1852 cfq_mark_cfqq_must_dispatch(cfqq);
Jens Axboe22e2c502005-06-27 10:55:12 +02001853 del_timer(&cfqd->idle_slice_timer);
Jens Axboedc72ef42006-07-20 14:54:05 +02001854 blk_start_queueing(cfqd->queue);
Jens Axboe22e2c502005-06-27 10:55:12 +02001855 }
Jens Axboe5e705372006-07-13 12:39:25 +02001856 } else if (cfq_should_preempt(cfqd, cfqq, rq)) {
Jens Axboe22e2c502005-06-27 10:55:12 +02001857 /*
1858 * not the active queue - expire current slice if it is
1859 * idle and has expired it's mean thinktime or this new queue
1860 * has some old slice time left and is of higher priority
1861 */
1862 cfq_preempt_queue(cfqd, cfqq);
Jens Axboe3b181522005-06-27 10:56:24 +02001863 cfq_mark_cfqq_must_dispatch(cfqq);
Jens Axboedc72ef42006-07-20 14:54:05 +02001864 blk_start_queueing(cfqd->queue);
Jens Axboe22e2c502005-06-27 10:55:12 +02001865 }
1866}
1867
Jens Axboe165125e2007-07-24 09:28:11 +02001868static void cfq_insert_request(struct request_queue *q, struct request *rq)
Jens Axboe22e2c502005-06-27 10:55:12 +02001869{
Jens Axboeb4878f22005-10-20 16:42:29 +02001870 struct cfq_data *cfqd = q->elevator->elevator_data;
Jens Axboe5e705372006-07-13 12:39:25 +02001871 struct cfq_queue *cfqq = RQ_CFQQ(rq);
Jens Axboe22e2c502005-06-27 10:55:12 +02001872
Jens Axboe7b679132008-05-30 12:23:07 +02001873 cfq_log_cfqq(cfqd, cfqq, "insert_request");
Jens Axboefd0928d2008-01-24 08:52:45 +01001874 cfq_init_prio_data(cfqq, RQ_CIC(rq)->ioc);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001875
Jens Axboe5e705372006-07-13 12:39:25 +02001876 cfq_add_rq_rb(rq);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001877
Jens Axboe22e2c502005-06-27 10:55:12 +02001878 list_add_tail(&rq->queuelist, &cfqq->fifo);
1879
Jens Axboe5e705372006-07-13 12:39:25 +02001880 cfq_rq_enqueued(cfqd, cfqq, rq);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001881}
1882
Jens Axboe165125e2007-07-24 09:28:11 +02001883static void cfq_completed_request(struct request_queue *q, struct request *rq)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001884{
Jens Axboe5e705372006-07-13 12:39:25 +02001885 struct cfq_queue *cfqq = RQ_CFQQ(rq);
Jens Axboeb4878f22005-10-20 16:42:29 +02001886 struct cfq_data *cfqd = cfqq->cfqd;
Jens Axboe5380a102006-07-13 12:37:56 +02001887 const int sync = rq_is_sync(rq);
Jens Axboeb4878f22005-10-20 16:42:29 +02001888 unsigned long now;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001889
Jens Axboeb4878f22005-10-20 16:42:29 +02001890 now = jiffies;
Jens Axboe7b679132008-05-30 12:23:07 +02001891 cfq_log_cfqq(cfqd, cfqq, "complete");
Linus Torvalds1da177e2005-04-16 15:20:36 -07001892
Jens Axboeb4878f22005-10-20 16:42:29 +02001893 WARN_ON(!cfqd->rq_in_driver);
Jens Axboe6d048f52007-04-25 12:44:27 +02001894 WARN_ON(!cfqq->dispatched);
Jens Axboeb4878f22005-10-20 16:42:29 +02001895 cfqd->rq_in_driver--;
Jens Axboe6d048f52007-04-25 12:44:27 +02001896 cfqq->dispatched--;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001897
Jens Axboe3ed9a292007-04-23 08:33:33 +02001898 if (cfq_cfqq_sync(cfqq))
1899 cfqd->sync_flight--;
1900
Jens Axboeb4878f22005-10-20 16:42:29 +02001901 if (!cfq_class_idle(cfqq))
1902 cfqd->last_end_request = now;
Jens Axboe3b181522005-06-27 10:56:24 +02001903
Jens Axboecaaa5f92006-06-16 11:23:00 +02001904 if (sync)
Jens Axboe5e705372006-07-13 12:39:25 +02001905 RQ_CIC(rq)->last_end_request = now;
Jens Axboecaaa5f92006-06-16 11:23:00 +02001906
1907 /*
1908 * If this is the active queue, check if it needs to be expired,
1909 * or if we want to idle in case it has no pending requests.
1910 */
1911 if (cfqd->active_queue == cfqq) {
Jens Axboe44f7c162007-01-19 11:51:58 +11001912 if (cfq_cfqq_slice_new(cfqq)) {
1913 cfq_set_prio_slice(cfqd, cfqq);
1914 cfq_clear_cfqq_slice_new(cfqq);
1915 }
Jens Axboe08717142008-01-28 11:38:15 +01001916 if (cfq_slice_used(cfqq) || cfq_class_idle(cfqq))
Jens Axboe6084cdd2007-04-23 08:25:00 +02001917 cfq_slice_expired(cfqd, 1);
Jens Axboe6d048f52007-04-25 12:44:27 +02001918 else if (sync && RB_EMPTY_ROOT(&cfqq->sort_list))
1919 cfq_arm_slice_timer(cfqd);
Jens Axboecaaa5f92006-06-16 11:23:00 +02001920 }
Jens Axboe6d048f52007-04-25 12:44:27 +02001921
1922 if (!cfqd->rq_in_driver)
1923 cfq_schedule_dispatch(cfqd);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001924}
1925
Jens Axboe22e2c502005-06-27 10:55:12 +02001926/*
1927 * we temporarily boost lower priority queues if they are holding fs exclusive
1928 * resources. they are boosted to normal prio (CLASS_BE/4)
1929 */
1930static void cfq_prio_boost(struct cfq_queue *cfqq)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001931{
Jens Axboe22e2c502005-06-27 10:55:12 +02001932 if (has_fs_excl()) {
1933 /*
1934 * boost idle prio on transactions that would lock out other
1935 * users of the filesystem
1936 */
1937 if (cfq_class_idle(cfqq))
1938 cfqq->ioprio_class = IOPRIO_CLASS_BE;
1939 if (cfqq->ioprio > IOPRIO_NORM)
1940 cfqq->ioprio = IOPRIO_NORM;
1941 } else {
1942 /*
1943 * check if we need to unboost the queue
1944 */
1945 if (cfqq->ioprio_class != cfqq->org_ioprio_class)
1946 cfqq->ioprio_class = cfqq->org_ioprio_class;
1947 if (cfqq->ioprio != cfqq->org_ioprio)
1948 cfqq->ioprio = cfqq->org_ioprio;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001949 }
Jens Axboe22e2c502005-06-27 10:55:12 +02001950}
1951
Jens Axboe89850f72006-07-22 16:48:31 +02001952static inline int __cfq_may_queue(struct cfq_queue *cfqq)
Jens Axboe22e2c502005-06-27 10:55:12 +02001953{
Jens Axboe3b181522005-06-27 10:56:24 +02001954 if ((cfq_cfqq_wait_request(cfqq) || cfq_cfqq_must_alloc(cfqq)) &&
Andrew Morton99f95e52005-06-27 20:14:05 -07001955 !cfq_cfqq_must_alloc_slice(cfqq)) {
Jens Axboe3b181522005-06-27 10:56:24 +02001956 cfq_mark_cfqq_must_alloc_slice(cfqq);
Jens Axboe22e2c502005-06-27 10:55:12 +02001957 return ELV_MQUEUE_MUST;
Jens Axboe3b181522005-06-27 10:56:24 +02001958 }
Jens Axboe22e2c502005-06-27 10:55:12 +02001959
1960 return ELV_MQUEUE_MAY;
Jens Axboe22e2c502005-06-27 10:55:12 +02001961}
1962
Jens Axboe165125e2007-07-24 09:28:11 +02001963static int cfq_may_queue(struct request_queue *q, int rw)
Jens Axboe22e2c502005-06-27 10:55:12 +02001964{
1965 struct cfq_data *cfqd = q->elevator->elevator_data;
1966 struct task_struct *tsk = current;
Vasily Tarasov91fac312007-04-25 12:29:51 +02001967 struct cfq_io_context *cic;
Jens Axboe22e2c502005-06-27 10:55:12 +02001968 struct cfq_queue *cfqq;
1969
1970 /*
1971 * don't force setup of a queue from here, as a call to may_queue
1972 * does not necessarily imply that a request actually will be queued.
1973 * so just lookup a possibly existing queue, or return 'may queue'
1974 * if that fails
1975 */
Jens Axboe4ac845a2008-01-24 08:44:49 +01001976 cic = cfq_cic_lookup(cfqd, tsk->io_context);
Vasily Tarasov91fac312007-04-25 12:29:51 +02001977 if (!cic)
1978 return ELV_MQUEUE_MAY;
1979
1980 cfqq = cic_to_cfqq(cic, rw & REQ_RW_SYNC);
Jens Axboe22e2c502005-06-27 10:55:12 +02001981 if (cfqq) {
Jens Axboefd0928d2008-01-24 08:52:45 +01001982 cfq_init_prio_data(cfqq, cic->ioc);
Jens Axboe22e2c502005-06-27 10:55:12 +02001983 cfq_prio_boost(cfqq);
1984
Jens Axboe89850f72006-07-22 16:48:31 +02001985 return __cfq_may_queue(cfqq);
Jens Axboe22e2c502005-06-27 10:55:12 +02001986 }
1987
1988 return ELV_MQUEUE_MAY;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001989}
1990
Linus Torvalds1da177e2005-04-16 15:20:36 -07001991/*
1992 * queue lock held here
1993 */
Jens Axboebb37b942006-12-01 10:42:33 +01001994static void cfq_put_request(struct request *rq)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001995{
Jens Axboe5e705372006-07-13 12:39:25 +02001996 struct cfq_queue *cfqq = RQ_CFQQ(rq);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001997
Jens Axboe5e705372006-07-13 12:39:25 +02001998 if (cfqq) {
Jens Axboe22e2c502005-06-27 10:55:12 +02001999 const int rw = rq_data_dir(rq);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002000
Jens Axboe22e2c502005-06-27 10:55:12 +02002001 BUG_ON(!cfqq->allocated[rw]);
2002 cfqq->allocated[rw]--;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002003
Jens Axboe5e705372006-07-13 12:39:25 +02002004 put_io_context(RQ_CIC(rq)->ioc);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002005
Linus Torvalds1da177e2005-04-16 15:20:36 -07002006 rq->elevator_private = NULL;
Jens Axboe5e705372006-07-13 12:39:25 +02002007 rq->elevator_private2 = NULL;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002008
Linus Torvalds1da177e2005-04-16 15:20:36 -07002009 cfq_put_queue(cfqq);
2010 }
2011}
2012
2013/*
Jens Axboe22e2c502005-06-27 10:55:12 +02002014 * Allocate cfq data structures associated with this request.
Linus Torvalds1da177e2005-04-16 15:20:36 -07002015 */
Jens Axboe22e2c502005-06-27 10:55:12 +02002016static int
Jens Axboe165125e2007-07-24 09:28:11 +02002017cfq_set_request(struct request_queue *q, struct request *rq, gfp_t gfp_mask)
Linus Torvalds1da177e2005-04-16 15:20:36 -07002018{
2019 struct cfq_data *cfqd = q->elevator->elevator_data;
2020 struct cfq_io_context *cic;
2021 const int rw = rq_data_dir(rq);
Jens Axboe7749a8d2006-12-13 13:02:26 +01002022 const int is_sync = rq_is_sync(rq);
Jens Axboe22e2c502005-06-27 10:55:12 +02002023 struct cfq_queue *cfqq;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002024 unsigned long flags;
2025
2026 might_sleep_if(gfp_mask & __GFP_WAIT);
2027
Jens Axboee2d74ac2006-03-28 08:59:01 +02002028 cic = cfq_get_io_context(cfqd, gfp_mask);
Jens Axboe22e2c502005-06-27 10:55:12 +02002029
Linus Torvalds1da177e2005-04-16 15:20:36 -07002030 spin_lock_irqsave(q->queue_lock, flags);
2031
Jens Axboe22e2c502005-06-27 10:55:12 +02002032 if (!cic)
2033 goto queue_fail;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002034
Vasily Tarasov91fac312007-04-25 12:29:51 +02002035 cfqq = cic_to_cfqq(cic, is_sync);
2036 if (!cfqq) {
Jens Axboefd0928d2008-01-24 08:52:45 +01002037 cfqq = cfq_get_queue(cfqd, is_sync, cic->ioc, gfp_mask);
Vasily Tarasov91fac312007-04-25 12:29:51 +02002038
Jens Axboe22e2c502005-06-27 10:55:12 +02002039 if (!cfqq)
2040 goto queue_fail;
2041
Vasily Tarasov91fac312007-04-25 12:29:51 +02002042 cic_set_cfqq(cic, cfqq, is_sync);
2043 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07002044
2045 cfqq->allocated[rw]++;
Jens Axboe3b181522005-06-27 10:56:24 +02002046 cfq_clear_cfqq_must_alloc(cfqq);
Jens Axboe22e2c502005-06-27 10:55:12 +02002047 atomic_inc(&cfqq->ref);
Jens Axboe5e705372006-07-13 12:39:25 +02002048
Linus Torvalds1da177e2005-04-16 15:20:36 -07002049 spin_unlock_irqrestore(q->queue_lock, flags);
2050
Jens Axboe5e705372006-07-13 12:39:25 +02002051 rq->elevator_private = cic;
2052 rq->elevator_private2 = cfqq;
2053 return 0;
Jens Axboe3b181522005-06-27 10:56:24 +02002054
Jens Axboe22e2c502005-06-27 10:55:12 +02002055queue_fail:
2056 if (cic)
2057 put_io_context(cic->ioc);
Jens Axboe89850f72006-07-22 16:48:31 +02002058
Jens Axboe3b181522005-06-27 10:56:24 +02002059 cfq_schedule_dispatch(cfqd);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002060 spin_unlock_irqrestore(q->queue_lock, flags);
Jens Axboe7b679132008-05-30 12:23:07 +02002061 cfq_log(cfqd, "set_request fail");
Linus Torvalds1da177e2005-04-16 15:20:36 -07002062 return 1;
2063}
2064
David Howells65f27f32006-11-22 14:55:48 +00002065static void cfq_kick_queue(struct work_struct *work)
Jens Axboe22e2c502005-06-27 10:55:12 +02002066{
David Howells65f27f32006-11-22 14:55:48 +00002067 struct cfq_data *cfqd =
2068 container_of(work, struct cfq_data, unplug_work);
Jens Axboe165125e2007-07-24 09:28:11 +02002069 struct request_queue *q = cfqd->queue;
Jens Axboe22e2c502005-06-27 10:55:12 +02002070 unsigned long flags;
2071
2072 spin_lock_irqsave(q->queue_lock, flags);
Jens Axboedc72ef42006-07-20 14:54:05 +02002073 blk_start_queueing(q);
Jens Axboe22e2c502005-06-27 10:55:12 +02002074 spin_unlock_irqrestore(q->queue_lock, flags);
2075}
2076
2077/*
2078 * Timer running if the active_queue is currently idling inside its time slice
2079 */
2080static void cfq_idle_slice_timer(unsigned long data)
2081{
2082 struct cfq_data *cfqd = (struct cfq_data *) data;
2083 struct cfq_queue *cfqq;
2084 unsigned long flags;
Jens Axboe3c6bd2f2007-01-19 12:06:33 +11002085 int timed_out = 1;
Jens Axboe22e2c502005-06-27 10:55:12 +02002086
Jens Axboe7b679132008-05-30 12:23:07 +02002087 cfq_log(cfqd, "idle timer fired");
2088
Jens Axboe22e2c502005-06-27 10:55:12 +02002089 spin_lock_irqsave(cfqd->queue->queue_lock, flags);
2090
Jens Axboefe094d92008-01-31 13:08:54 +01002091 cfqq = cfqd->active_queue;
2092 if (cfqq) {
Jens Axboe3c6bd2f2007-01-19 12:06:33 +11002093 timed_out = 0;
2094
Jens Axboe22e2c502005-06-27 10:55:12 +02002095 /*
2096 * expired
2097 */
Jens Axboe44f7c162007-01-19 11:51:58 +11002098 if (cfq_slice_used(cfqq))
Jens Axboe22e2c502005-06-27 10:55:12 +02002099 goto expire;
2100
2101 /*
2102 * only expire and reinvoke request handler, if there are
2103 * other queues with pending requests
2104 */
Jens Axboecaaa5f92006-06-16 11:23:00 +02002105 if (!cfqd->busy_queues)
Jens Axboe22e2c502005-06-27 10:55:12 +02002106 goto out_cont;
Jens Axboe22e2c502005-06-27 10:55:12 +02002107
2108 /*
2109 * not expired and it has a request pending, let it dispatch
2110 */
Jens Axboedd67d052006-06-21 09:36:18 +02002111 if (!RB_EMPTY_ROOT(&cfqq->sort_list)) {
Jens Axboe3b181522005-06-27 10:56:24 +02002112 cfq_mark_cfqq_must_dispatch(cfqq);
Jens Axboe22e2c502005-06-27 10:55:12 +02002113 goto out_kick;
2114 }
2115 }
2116expire:
Jens Axboe6084cdd2007-04-23 08:25:00 +02002117 cfq_slice_expired(cfqd, timed_out);
Jens Axboe22e2c502005-06-27 10:55:12 +02002118out_kick:
Jens Axboe3b181522005-06-27 10:56:24 +02002119 cfq_schedule_dispatch(cfqd);
Jens Axboe22e2c502005-06-27 10:55:12 +02002120out_cont:
2121 spin_unlock_irqrestore(cfqd->queue->queue_lock, flags);
2122}
2123
Jens Axboe3b181522005-06-27 10:56:24 +02002124static void cfq_shutdown_timer_wq(struct cfq_data *cfqd)
2125{
2126 del_timer_sync(&cfqd->idle_slice_timer);
Oleg Nesterov43108642007-10-23 15:08:18 +02002127 kblockd_flush_work(&cfqd->unplug_work);
Jens Axboe3b181522005-06-27 10:56:24 +02002128}
Jens Axboe22e2c502005-06-27 10:55:12 +02002129
Vasily Tarasovc2dea2d2007-07-20 10:06:38 +02002130static void cfq_put_async_queues(struct cfq_data *cfqd)
2131{
2132 int i;
2133
2134 for (i = 0; i < IOPRIO_BE_NR; i++) {
2135 if (cfqd->async_cfqq[0][i])
2136 cfq_put_queue(cfqd->async_cfqq[0][i]);
2137 if (cfqd->async_cfqq[1][i])
2138 cfq_put_queue(cfqd->async_cfqq[1][i]);
Vasily Tarasovc2dea2d2007-07-20 10:06:38 +02002139 }
Oleg Nesterov2389d1e2007-11-05 08:58:05 +01002140
2141 if (cfqd->async_idle_cfqq)
2142 cfq_put_queue(cfqd->async_idle_cfqq);
Vasily Tarasovc2dea2d2007-07-20 10:06:38 +02002143}
2144
Linus Torvalds1da177e2005-04-16 15:20:36 -07002145static void cfq_exit_queue(elevator_t *e)
2146{
Jens Axboe22e2c502005-06-27 10:55:12 +02002147 struct cfq_data *cfqd = e->elevator_data;
Jens Axboe165125e2007-07-24 09:28:11 +02002148 struct request_queue *q = cfqd->queue;
Jens Axboe22e2c502005-06-27 10:55:12 +02002149
Jens Axboe3b181522005-06-27 10:56:24 +02002150 cfq_shutdown_timer_wq(cfqd);
Jens Axboee2d74ac2006-03-28 08:59:01 +02002151
Al Virod9ff4182006-03-18 13:51:22 -05002152 spin_lock_irq(q->queue_lock);
Jens Axboee2d74ac2006-03-28 08:59:01 +02002153
Al Virod9ff4182006-03-18 13:51:22 -05002154 if (cfqd->active_queue)
Jens Axboe6084cdd2007-04-23 08:25:00 +02002155 __cfq_slice_expired(cfqd, cfqd->active_queue, 0);
Jens Axboee2d74ac2006-03-28 08:59:01 +02002156
2157 while (!list_empty(&cfqd->cic_list)) {
Al Virod9ff4182006-03-18 13:51:22 -05002158 struct cfq_io_context *cic = list_entry(cfqd->cic_list.next,
2159 struct cfq_io_context,
2160 queue_list);
Jens Axboe89850f72006-07-22 16:48:31 +02002161
2162 __cfq_exit_single_io_context(cfqd, cic);
Al Virod9ff4182006-03-18 13:51:22 -05002163 }
Jens Axboee2d74ac2006-03-28 08:59:01 +02002164
Vasily Tarasovc2dea2d2007-07-20 10:06:38 +02002165 cfq_put_async_queues(cfqd);
Jens Axboe15c31be2007-07-10 13:43:25 +02002166
Al Virod9ff4182006-03-18 13:51:22 -05002167 spin_unlock_irq(q->queue_lock);
Al Viroa90d7422006-03-18 12:05:37 -05002168
2169 cfq_shutdown_timer_wq(cfqd);
2170
Al Viroa90d7422006-03-18 12:05:37 -05002171 kfree(cfqd);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002172}
2173
Jens Axboe165125e2007-07-24 09:28:11 +02002174static void *cfq_init_queue(struct request_queue *q)
Linus Torvalds1da177e2005-04-16 15:20:36 -07002175{
2176 struct cfq_data *cfqd;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002177
Christoph Lameter94f60302007-07-17 04:03:29 -07002178 cfqd = kmalloc_node(sizeof(*cfqd), GFP_KERNEL | __GFP_ZERO, q->node);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002179 if (!cfqd)
Jens Axboebc1c1162006-06-08 08:49:06 +02002180 return NULL;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002181
Jens Axboecc09e292007-04-26 12:53:50 +02002182 cfqd->service_tree = CFQ_RB_ROOT;
Al Virod9ff4182006-03-18 13:51:22 -05002183 INIT_LIST_HEAD(&cfqd->cic_list);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002184
Linus Torvalds1da177e2005-04-16 15:20:36 -07002185 cfqd->queue = q;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002186
Jens Axboe22e2c502005-06-27 10:55:12 +02002187 init_timer(&cfqd->idle_slice_timer);
2188 cfqd->idle_slice_timer.function = cfq_idle_slice_timer;
2189 cfqd->idle_slice_timer.data = (unsigned long) cfqd;
2190
David Howells65f27f32006-11-22 14:55:48 +00002191 INIT_WORK(&cfqd->unplug_work, cfq_kick_queue);
Jens Axboe22e2c502005-06-27 10:55:12 +02002192
Oleg Nesterovb70c8642007-11-07 09:46:13 +01002193 cfqd->last_end_request = jiffies;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002194 cfqd->cfq_quantum = cfq_quantum;
Jens Axboe22e2c502005-06-27 10:55:12 +02002195 cfqd->cfq_fifo_expire[0] = cfq_fifo_expire[0];
2196 cfqd->cfq_fifo_expire[1] = cfq_fifo_expire[1];
Linus Torvalds1da177e2005-04-16 15:20:36 -07002197 cfqd->cfq_back_max = cfq_back_max;
2198 cfqd->cfq_back_penalty = cfq_back_penalty;
Jens Axboe22e2c502005-06-27 10:55:12 +02002199 cfqd->cfq_slice[0] = cfq_slice_async;
2200 cfqd->cfq_slice[1] = cfq_slice_sync;
2201 cfqd->cfq_slice_async_rq = cfq_slice_async_rq;
2202 cfqd->cfq_slice_idle = cfq_slice_idle;
Jens Axboe3b181522005-06-27 10:56:24 +02002203
Jens Axboebc1c1162006-06-08 08:49:06 +02002204 return cfqd;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002205}
2206
2207static void cfq_slab_kill(void)
2208{
Jens Axboed6de8be2008-05-28 14:46:59 +02002209 /*
2210 * Caller already ensured that pending RCU callbacks are completed,
2211 * so we should have no busy allocations at this point.
2212 */
Linus Torvalds1da177e2005-04-16 15:20:36 -07002213 if (cfq_pool)
2214 kmem_cache_destroy(cfq_pool);
2215 if (cfq_ioc_pool)
2216 kmem_cache_destroy(cfq_ioc_pool);
2217}
2218
2219static int __init cfq_slab_setup(void)
2220{
Christoph Lameter0a31bd52007-05-06 14:49:57 -07002221 cfq_pool = KMEM_CACHE(cfq_queue, 0);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002222 if (!cfq_pool)
2223 goto fail;
2224
Fabio Checconi34e6bbf2008-04-02 14:31:02 +02002225 cfq_ioc_pool = KMEM_CACHE(cfq_io_context, 0);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002226 if (!cfq_ioc_pool)
2227 goto fail;
2228
2229 return 0;
2230fail:
2231 cfq_slab_kill();
2232 return -ENOMEM;
2233}
2234
Linus Torvalds1da177e2005-04-16 15:20:36 -07002235/*
2236 * sysfs parts below -->
2237 */
Linus Torvalds1da177e2005-04-16 15:20:36 -07002238static ssize_t
2239cfq_var_show(unsigned int var, char *page)
2240{
2241 return sprintf(page, "%d\n", var);
2242}
2243
2244static ssize_t
2245cfq_var_store(unsigned int *var, const char *page, size_t count)
2246{
2247 char *p = (char *) page;
2248
2249 *var = simple_strtoul(p, &p, 10);
2250 return count;
2251}
2252
Linus Torvalds1da177e2005-04-16 15:20:36 -07002253#define SHOW_FUNCTION(__FUNC, __VAR, __CONV) \
Al Viro3d1ab402006-03-18 18:35:43 -05002254static ssize_t __FUNC(elevator_t *e, char *page) \
Linus Torvalds1da177e2005-04-16 15:20:36 -07002255{ \
Al Viro3d1ab402006-03-18 18:35:43 -05002256 struct cfq_data *cfqd = e->elevator_data; \
Linus Torvalds1da177e2005-04-16 15:20:36 -07002257 unsigned int __data = __VAR; \
2258 if (__CONV) \
2259 __data = jiffies_to_msecs(__data); \
2260 return cfq_var_show(__data, (page)); \
2261}
2262SHOW_FUNCTION(cfq_quantum_show, cfqd->cfq_quantum, 0);
Jens Axboe22e2c502005-06-27 10:55:12 +02002263SHOW_FUNCTION(cfq_fifo_expire_sync_show, cfqd->cfq_fifo_expire[1], 1);
2264SHOW_FUNCTION(cfq_fifo_expire_async_show, cfqd->cfq_fifo_expire[0], 1);
Al Viroe572ec72006-03-18 22:27:18 -05002265SHOW_FUNCTION(cfq_back_seek_max_show, cfqd->cfq_back_max, 0);
2266SHOW_FUNCTION(cfq_back_seek_penalty_show, cfqd->cfq_back_penalty, 0);
Jens Axboe22e2c502005-06-27 10:55:12 +02002267SHOW_FUNCTION(cfq_slice_idle_show, cfqd->cfq_slice_idle, 1);
2268SHOW_FUNCTION(cfq_slice_sync_show, cfqd->cfq_slice[1], 1);
2269SHOW_FUNCTION(cfq_slice_async_show, cfqd->cfq_slice[0], 1);
2270SHOW_FUNCTION(cfq_slice_async_rq_show, cfqd->cfq_slice_async_rq, 0);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002271#undef SHOW_FUNCTION
2272
2273#define STORE_FUNCTION(__FUNC, __PTR, MIN, MAX, __CONV) \
Al Viro3d1ab402006-03-18 18:35:43 -05002274static ssize_t __FUNC(elevator_t *e, const char *page, size_t count) \
Linus Torvalds1da177e2005-04-16 15:20:36 -07002275{ \
Al Viro3d1ab402006-03-18 18:35:43 -05002276 struct cfq_data *cfqd = e->elevator_data; \
Linus Torvalds1da177e2005-04-16 15:20:36 -07002277 unsigned int __data; \
2278 int ret = cfq_var_store(&__data, (page), count); \
2279 if (__data < (MIN)) \
2280 __data = (MIN); \
2281 else if (__data > (MAX)) \
2282 __data = (MAX); \
2283 if (__CONV) \
2284 *(__PTR) = msecs_to_jiffies(__data); \
2285 else \
2286 *(__PTR) = __data; \
2287 return ret; \
2288}
2289STORE_FUNCTION(cfq_quantum_store, &cfqd->cfq_quantum, 1, UINT_MAX, 0);
Jens Axboefe094d92008-01-31 13:08:54 +01002290STORE_FUNCTION(cfq_fifo_expire_sync_store, &cfqd->cfq_fifo_expire[1], 1,
2291 UINT_MAX, 1);
2292STORE_FUNCTION(cfq_fifo_expire_async_store, &cfqd->cfq_fifo_expire[0], 1,
2293 UINT_MAX, 1);
Al Viroe572ec72006-03-18 22:27:18 -05002294STORE_FUNCTION(cfq_back_seek_max_store, &cfqd->cfq_back_max, 0, UINT_MAX, 0);
Jens Axboefe094d92008-01-31 13:08:54 +01002295STORE_FUNCTION(cfq_back_seek_penalty_store, &cfqd->cfq_back_penalty, 1,
2296 UINT_MAX, 0);
Jens Axboe22e2c502005-06-27 10:55:12 +02002297STORE_FUNCTION(cfq_slice_idle_store, &cfqd->cfq_slice_idle, 0, UINT_MAX, 1);
2298STORE_FUNCTION(cfq_slice_sync_store, &cfqd->cfq_slice[1], 1, UINT_MAX, 1);
2299STORE_FUNCTION(cfq_slice_async_store, &cfqd->cfq_slice[0], 1, UINT_MAX, 1);
Jens Axboefe094d92008-01-31 13:08:54 +01002300STORE_FUNCTION(cfq_slice_async_rq_store, &cfqd->cfq_slice_async_rq, 1,
2301 UINT_MAX, 0);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002302#undef STORE_FUNCTION
2303
Al Viroe572ec72006-03-18 22:27:18 -05002304#define CFQ_ATTR(name) \
2305 __ATTR(name, S_IRUGO|S_IWUSR, cfq_##name##_show, cfq_##name##_store)
Jens Axboe3b181522005-06-27 10:56:24 +02002306
Al Viroe572ec72006-03-18 22:27:18 -05002307static struct elv_fs_entry cfq_attrs[] = {
2308 CFQ_ATTR(quantum),
Al Viroe572ec72006-03-18 22:27:18 -05002309 CFQ_ATTR(fifo_expire_sync),
2310 CFQ_ATTR(fifo_expire_async),
2311 CFQ_ATTR(back_seek_max),
2312 CFQ_ATTR(back_seek_penalty),
2313 CFQ_ATTR(slice_sync),
2314 CFQ_ATTR(slice_async),
2315 CFQ_ATTR(slice_async_rq),
2316 CFQ_ATTR(slice_idle),
Al Viroe572ec72006-03-18 22:27:18 -05002317 __ATTR_NULL
Linus Torvalds1da177e2005-04-16 15:20:36 -07002318};
2319
Linus Torvalds1da177e2005-04-16 15:20:36 -07002320static struct elevator_type iosched_cfq = {
2321 .ops = {
2322 .elevator_merge_fn = cfq_merge,
2323 .elevator_merged_fn = cfq_merged_request,
2324 .elevator_merge_req_fn = cfq_merged_requests,
Jens Axboeda775262006-12-20 11:04:12 +01002325 .elevator_allow_merge_fn = cfq_allow_merge,
Jens Axboeb4878f22005-10-20 16:42:29 +02002326 .elevator_dispatch_fn = cfq_dispatch_requests,
Linus Torvalds1da177e2005-04-16 15:20:36 -07002327 .elevator_add_req_fn = cfq_insert_request,
Jens Axboeb4878f22005-10-20 16:42:29 +02002328 .elevator_activate_req_fn = cfq_activate_request,
Linus Torvalds1da177e2005-04-16 15:20:36 -07002329 .elevator_deactivate_req_fn = cfq_deactivate_request,
2330 .elevator_queue_empty_fn = cfq_queue_empty,
2331 .elevator_completed_req_fn = cfq_completed_request,
Jens Axboe21183b02006-07-13 12:33:14 +02002332 .elevator_former_req_fn = elv_rb_former_request,
2333 .elevator_latter_req_fn = elv_rb_latter_request,
Linus Torvalds1da177e2005-04-16 15:20:36 -07002334 .elevator_set_req_fn = cfq_set_request,
2335 .elevator_put_req_fn = cfq_put_request,
2336 .elevator_may_queue_fn = cfq_may_queue,
2337 .elevator_init_fn = cfq_init_queue,
2338 .elevator_exit_fn = cfq_exit_queue,
Jens Axboefc463792006-08-29 09:05:44 +02002339 .trim = cfq_free_io_context,
Linus Torvalds1da177e2005-04-16 15:20:36 -07002340 },
Al Viro3d1ab402006-03-18 18:35:43 -05002341 .elevator_attrs = cfq_attrs,
Linus Torvalds1da177e2005-04-16 15:20:36 -07002342 .elevator_name = "cfq",
2343 .elevator_owner = THIS_MODULE,
2344};
2345
2346static int __init cfq_init(void)
2347{
Jens Axboe22e2c502005-06-27 10:55:12 +02002348 /*
2349 * could be 0 on HZ < 1000 setups
2350 */
2351 if (!cfq_slice_async)
2352 cfq_slice_async = 1;
2353 if (!cfq_slice_idle)
2354 cfq_slice_idle = 1;
2355
Linus Torvalds1da177e2005-04-16 15:20:36 -07002356 if (cfq_slab_setup())
2357 return -ENOMEM;
2358
Adrian Bunk2fdd82b2007-12-12 18:51:56 +01002359 elv_register(&iosched_cfq);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002360
Adrian Bunk2fdd82b2007-12-12 18:51:56 +01002361 return 0;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002362}
2363
2364static void __exit cfq_exit(void)
2365{
Peter Zijlstra6e9a4732006-09-30 23:28:10 -07002366 DECLARE_COMPLETION_ONSTACK(all_gone);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002367 elv_unregister(&iosched_cfq);
Al Viro334e94d2006-03-18 15:05:53 -05002368 ioc_gone = &all_gone;
OGAWA Hirofumifba82272006-04-18 09:44:06 +02002369 /* ioc_gone's update must be visible before reading ioc_count */
2370 smp_wmb();
Jens Axboed6de8be2008-05-28 14:46:59 +02002371
2372 /*
2373 * this also protects us from entering cfq_slab_kill() with
2374 * pending RCU callbacks
2375 */
Jens Axboe4050cf12006-07-19 05:07:12 +02002376 if (elv_ioc_count_read(ioc_count))
Jens Axboe9a11b4e2008-05-29 09:32:08 +02002377 wait_for_completion(&all_gone);
Christoph Hellwig83521d32005-10-30 15:01:39 -08002378 cfq_slab_kill();
Linus Torvalds1da177e2005-04-16 15:20:36 -07002379}
2380
2381module_init(cfq_init);
2382module_exit(cfq_exit);
2383
2384MODULE_AUTHOR("Jens Axboe");
2385MODULE_LICENSE("GPL");
2386MODULE_DESCRIPTION("Completely Fair Queueing IO scheduler");