blob: e25223e147a2a5e336a1a430dde49b3e43f00283 [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 *
7 * Copyright (C) 2003 Jens Axboe <axboe@suse.de>
8 */
Linus Torvalds1da177e2005-04-16 15:20:36 -07009#include <linux/config.h>
10#include <linux/module.h>
Al Viro1cc9be62006-03-18 12:29:52 -050011#include <linux/blkdev.h>
12#include <linux/elevator.h>
Linus Torvalds1da177e2005-04-16 15:20:36 -070013#include <linux/hash.h>
14#include <linux/rbtree.h>
Jens Axboe22e2c502005-06-27 10:55:12 +020015#include <linux/ioprio.h>
Linus Torvalds1da177e2005-04-16 15:20:36 -070016
17/*
18 * tunables
19 */
Arjan van de Ven64100092006-01-06 09:46:02 +010020static const int cfq_quantum = 4; /* max queue in one round of service */
21static const int cfq_queued = 8; /* minimum rq allocate limit per-queue*/
22static const int cfq_fifo_expire[2] = { HZ / 4, HZ / 8 };
23static const int cfq_back_max = 16 * 1024; /* maximum backwards seek, in KiB */
24static const int cfq_back_penalty = 2; /* penalty of a backwards seek */
Linus Torvalds1da177e2005-04-16 15:20:36 -070025
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
31#define CFQ_IDLE_GRACE (HZ / 10)
32#define CFQ_SLICE_SCALE (5)
33
34#define CFQ_KEY_ASYNC (0)
Jens Axboe22e2c502005-06-27 10:55:12 +020035
Jens Axboe3793c652006-05-30 21:11:04 +020036static DEFINE_SPINLOCK(cfq_exit_lock);
Al Viroa6a07632006-03-18 13:26:44 -050037
Linus Torvalds1da177e2005-04-16 15:20:36 -070038/*
39 * for the hash of cfqq inside the cfqd
40 */
41#define CFQ_QHASH_SHIFT 6
42#define CFQ_QHASH_ENTRIES (1 << CFQ_QHASH_SHIFT)
43#define list_entry_qhash(entry) hlist_entry((entry), struct cfq_queue, cfq_hash)
44
45/*
46 * for the hash of crq inside the cfqq
47 */
48#define CFQ_MHASH_SHIFT 6
49#define CFQ_MHASH_BLOCK(sec) ((sec) >> 3)
50#define CFQ_MHASH_ENTRIES (1 << CFQ_MHASH_SHIFT)
51#define CFQ_MHASH_FN(sec) hash_long(CFQ_MHASH_BLOCK(sec), CFQ_MHASH_SHIFT)
52#define rq_hash_key(rq) ((rq)->sector + (rq)->nr_sectors)
53#define list_entry_hash(ptr) hlist_entry((ptr), struct cfq_rq, hash)
54
55#define list_entry_cfqq(ptr) list_entry((ptr), struct cfq_queue, cfq_list)
Jens Axboe22e2c502005-06-27 10:55:12 +020056#define list_entry_fifo(ptr) list_entry((ptr), struct request, queuelist)
Linus Torvalds1da177e2005-04-16 15:20:36 -070057
58#define RQ_DATA(rq) (rq)->elevator_private
59
60/*
61 * rb-tree defines
62 */
Linus Torvalds1da177e2005-04-16 15:20:36 -070063#define rb_entry_crq(node) rb_entry((node), struct cfq_rq, rb_node)
64#define rq_rb_key(rq) (rq)->sector
65
Linus Torvalds1da177e2005-04-16 15:20:36 -070066static kmem_cache_t *crq_pool;
67static kmem_cache_t *cfq_pool;
68static kmem_cache_t *cfq_ioc_pool;
69
Al Viro334e94d2006-03-18 15:05:53 -050070static atomic_t ioc_count = ATOMIC_INIT(0);
71static struct completion *ioc_gone;
72
Jens Axboe22e2c502005-06-27 10:55:12 +020073#define CFQ_PRIO_LISTS IOPRIO_BE_NR
74#define cfq_class_idle(cfqq) ((cfqq)->ioprio_class == IOPRIO_CLASS_IDLE)
75#define cfq_class_be(cfqq) ((cfqq)->ioprio_class == IOPRIO_CLASS_BE)
76#define cfq_class_rt(cfqq) ((cfqq)->ioprio_class == IOPRIO_CLASS_RT)
77
Jens Axboe3b181522005-06-27 10:56:24 +020078#define ASYNC (0)
79#define SYNC (1)
80
81#define cfq_cfqq_dispatched(cfqq) \
82 ((cfqq)->on_dispatch[ASYNC] + (cfqq)->on_dispatch[SYNC])
83
84#define cfq_cfqq_class_sync(cfqq) ((cfqq)->key != CFQ_KEY_ASYNC)
85
86#define cfq_cfqq_sync(cfqq) \
87 (cfq_cfqq_class_sync(cfqq) || (cfqq)->on_dispatch[SYNC])
Jens Axboe22e2c502005-06-27 10:55:12 +020088
Jens Axboe206dc692006-03-28 13:03:44 +020089#define sample_valid(samples) ((samples) > 80)
90
Jens Axboe22e2c502005-06-27 10:55:12 +020091/*
92 * Per block device queue structure
93 */
Linus Torvalds1da177e2005-04-16 15:20:36 -070094struct cfq_data {
Jens Axboe22e2c502005-06-27 10:55:12 +020095 request_queue_t *queue;
96
97 /*
98 * rr list of queues with requests and the count of them
99 */
100 struct list_head rr_list[CFQ_PRIO_LISTS];
101 struct list_head busy_rr;
102 struct list_head cur_rr;
103 struct list_head idle_rr;
104 unsigned int busy_queues;
105
106 /*
107 * non-ordered list of empty cfqq's
108 */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700109 struct list_head empty_list;
110
Jens Axboe22e2c502005-06-27 10:55:12 +0200111 /*
112 * cfqq lookup hash
113 */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700114 struct hlist_head *cfq_hash;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700115
Jens Axboe22e2c502005-06-27 10:55:12 +0200116 /*
117 * global crq hash for all queues
118 */
119 struct hlist_head *crq_hash;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700120
Linus Torvalds1da177e2005-04-16 15:20:36 -0700121 mempool_t *crq_pool;
122
Jens Axboe22e2c502005-06-27 10:55:12 +0200123 int rq_in_driver;
Jens Axboe25776e32006-06-01 10:12:26 +0200124 int hw_tag;
Jens Axboe22e2c502005-06-27 10:55:12 +0200125
126 /*
127 * schedule slice state info
128 */
129 /*
130 * idle window management
131 */
132 struct timer_list idle_slice_timer;
133 struct work_struct unplug_work;
134
135 struct cfq_queue *active_queue;
136 struct cfq_io_context *active_cic;
137 int cur_prio, cur_end_prio;
138 unsigned int dispatch_slice;
139
140 struct timer_list idle_class_timer;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700141
142 sector_t last_sector;
Jens Axboe22e2c502005-06-27 10:55:12 +0200143 unsigned long last_end_request;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700144
Jens Axboe22e2c502005-06-27 10:55:12 +0200145 unsigned int rq_starved;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700146
147 /*
148 * tunables, see top of file
149 */
150 unsigned int cfq_quantum;
151 unsigned int cfq_queued;
Jens Axboe22e2c502005-06-27 10:55:12 +0200152 unsigned int cfq_fifo_expire[2];
Linus Torvalds1da177e2005-04-16 15:20:36 -0700153 unsigned int cfq_back_penalty;
154 unsigned int cfq_back_max;
Jens Axboe22e2c502005-06-27 10:55:12 +0200155 unsigned int cfq_slice[2];
156 unsigned int cfq_slice_async_rq;
157 unsigned int cfq_slice_idle;
Al Virod9ff4182006-03-18 13:51:22 -0500158
159 struct list_head cic_list;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700160};
161
Jens Axboe22e2c502005-06-27 10:55:12 +0200162/*
163 * Per process-grouping structure
164 */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700165struct cfq_queue {
166 /* reference count */
167 atomic_t ref;
168 /* parent cfq_data */
169 struct cfq_data *cfqd;
Jens Axboe22e2c502005-06-27 10:55:12 +0200170 /* cfqq lookup hash */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700171 struct hlist_node cfq_hash;
172 /* hash key */
Jens Axboe22e2c502005-06-27 10:55:12 +0200173 unsigned int key;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700174 /* on either rr or empty list of cfqd */
175 struct list_head cfq_list;
176 /* sorted list of pending requests */
177 struct rb_root sort_list;
178 /* if fifo isn't expired, next request to serve */
179 struct cfq_rq *next_crq;
180 /* requests queued in sort_list */
181 int queued[2];
182 /* currently allocated requests */
183 int allocated[2];
184 /* fifo list of requests in sort_list */
Jens Axboe22e2c502005-06-27 10:55:12 +0200185 struct list_head fifo;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700186
Jens Axboe22e2c502005-06-27 10:55:12 +0200187 unsigned long slice_start;
188 unsigned long slice_end;
189 unsigned long slice_left;
190 unsigned long service_last;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700191
Jens Axboe3b181522005-06-27 10:56:24 +0200192 /* number of requests that are on the dispatch list */
193 int on_dispatch[2];
Jens Axboe22e2c502005-06-27 10:55:12 +0200194
195 /* io prio of this group */
196 unsigned short ioprio, org_ioprio;
197 unsigned short ioprio_class, org_ioprio_class;
198
Jens Axboe3b181522005-06-27 10:56:24 +0200199 /* various state flags, see below */
200 unsigned int flags;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700201};
202
203struct cfq_rq {
204 struct rb_node rb_node;
205 sector_t rb_key;
206 struct request *request;
207 struct hlist_node hash;
208
209 struct cfq_queue *cfq_queue;
210 struct cfq_io_context *io_context;
211
Jens Axboe3b181522005-06-27 10:56:24 +0200212 unsigned int crq_flags;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700213};
214
Jens Axboe3b181522005-06-27 10:56:24 +0200215enum cfqq_state_flags {
216 CFQ_CFQQ_FLAG_on_rr = 0,
217 CFQ_CFQQ_FLAG_wait_request,
218 CFQ_CFQQ_FLAG_must_alloc,
219 CFQ_CFQQ_FLAG_must_alloc_slice,
220 CFQ_CFQQ_FLAG_must_dispatch,
221 CFQ_CFQQ_FLAG_fifo_expire,
222 CFQ_CFQQ_FLAG_idle_window,
223 CFQ_CFQQ_FLAG_prio_changed,
Jens Axboe3b181522005-06-27 10:56:24 +0200224};
225
226#define CFQ_CFQQ_FNS(name) \
227static inline void cfq_mark_cfqq_##name(struct cfq_queue *cfqq) \
228{ \
229 cfqq->flags |= (1 << CFQ_CFQQ_FLAG_##name); \
230} \
231static inline void cfq_clear_cfqq_##name(struct cfq_queue *cfqq) \
232{ \
233 cfqq->flags &= ~(1 << CFQ_CFQQ_FLAG_##name); \
234} \
235static inline int cfq_cfqq_##name(const struct cfq_queue *cfqq) \
236{ \
237 return (cfqq->flags & (1 << CFQ_CFQQ_FLAG_##name)) != 0; \
238}
239
240CFQ_CFQQ_FNS(on_rr);
241CFQ_CFQQ_FNS(wait_request);
242CFQ_CFQQ_FNS(must_alloc);
243CFQ_CFQQ_FNS(must_alloc_slice);
244CFQ_CFQQ_FNS(must_dispatch);
245CFQ_CFQQ_FNS(fifo_expire);
246CFQ_CFQQ_FNS(idle_window);
247CFQ_CFQQ_FNS(prio_changed);
Jens Axboe3b181522005-06-27 10:56:24 +0200248#undef CFQ_CFQQ_FNS
249
250enum cfq_rq_state_flags {
Jens Axboeb4878f22005-10-20 16:42:29 +0200251 CFQ_CRQ_FLAG_is_sync = 0,
Jens Axboe3b181522005-06-27 10:56:24 +0200252};
253
254#define CFQ_CRQ_FNS(name) \
255static inline void cfq_mark_crq_##name(struct cfq_rq *crq) \
256{ \
257 crq->crq_flags |= (1 << CFQ_CRQ_FLAG_##name); \
258} \
259static inline void cfq_clear_crq_##name(struct cfq_rq *crq) \
260{ \
261 crq->crq_flags &= ~(1 << CFQ_CRQ_FLAG_##name); \
262} \
263static inline int cfq_crq_##name(const struct cfq_rq *crq) \
264{ \
265 return (crq->crq_flags & (1 << CFQ_CRQ_FLAG_##name)) != 0; \
266}
267
Jens Axboe3b181522005-06-27 10:56:24 +0200268CFQ_CRQ_FNS(is_sync);
Jens Axboe3b181522005-06-27 10:56:24 +0200269#undef CFQ_CRQ_FNS
270
271static struct cfq_queue *cfq_find_cfq_hash(struct cfq_data *, unsigned int, unsigned short);
Jens Axboeb4878f22005-10-20 16:42:29 +0200272static void cfq_dispatch_insert(request_queue_t *, struct cfq_rq *);
Al Viro6f325a12006-03-18 14:58:37 -0500273static struct cfq_queue *cfq_get_queue(struct cfq_data *cfqd, unsigned int key, struct task_struct *tsk, gfp_t gfp_mask);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700274
Linus Torvalds1da177e2005-04-16 15:20:36 -0700275/*
276 * lots of deadline iosched dupes, can be abstracted later...
277 */
278static inline void cfq_del_crq_hash(struct cfq_rq *crq)
279{
280 hlist_del_init(&crq->hash);
281}
282
Linus Torvalds1da177e2005-04-16 15:20:36 -0700283static inline void cfq_add_crq_hash(struct cfq_data *cfqd, struct cfq_rq *crq)
284{
285 const int hash_idx = CFQ_MHASH_FN(rq_hash_key(crq->request));
286
Linus Torvalds1da177e2005-04-16 15:20:36 -0700287 hlist_add_head(&crq->hash, &cfqd->crq_hash[hash_idx]);
288}
289
290static struct request *cfq_find_rq_hash(struct cfq_data *cfqd, sector_t offset)
291{
292 struct hlist_head *hash_list = &cfqd->crq_hash[CFQ_MHASH_FN(offset)];
293 struct hlist_node *entry, *next;
294
295 hlist_for_each_safe(entry, next, hash_list) {
296 struct cfq_rq *crq = list_entry_hash(entry);
297 struct request *__rq = crq->request;
298
Linus Torvalds1da177e2005-04-16 15:20:36 -0700299 if (!rq_mergeable(__rq)) {
300 cfq_del_crq_hash(crq);
301 continue;
302 }
303
304 if (rq_hash_key(__rq) == offset)
305 return __rq;
306 }
307
308 return NULL;
309}
310
Andrew Morton99f95e52005-06-27 20:14:05 -0700311/*
312 * scheduler run of queue, if there are requests pending and no one in the
313 * driver that will restart queueing
314 */
315static inline void cfq_schedule_dispatch(struct cfq_data *cfqd)
316{
Jens Axboe7b14e3b2006-02-28 09:35:11 +0100317 if (cfqd->busy_queues)
Andrew Morton99f95e52005-06-27 20:14:05 -0700318 kblockd_schedule_work(&cfqd->unplug_work);
319}
320
321static int cfq_queue_empty(request_queue_t *q)
322{
323 struct cfq_data *cfqd = q->elevator->elevator_data;
324
Jens Axboeb4878f22005-10-20 16:42:29 +0200325 return !cfqd->busy_queues;
Andrew Morton99f95e52005-06-27 20:14:05 -0700326}
327
Jens Axboe206dc692006-03-28 13:03:44 +0200328static inline pid_t cfq_queue_pid(struct task_struct *task, int rw)
329{
Jens Axboeb31dc662006-06-13 08:26:10 +0200330 if (rw == READ || rw == WRITE_SYNC)
Jens Axboe206dc692006-03-28 13:03:44 +0200331 return task->pid;
332
333 return CFQ_KEY_ASYNC;
334}
335
Linus Torvalds1da177e2005-04-16 15:20:36 -0700336/*
337 * Lifted from AS - choose which of crq1 and crq2 that is best served now.
338 * We choose the request that is closest to the head right now. Distance
Andreas Mohre8a99052006-03-28 08:59:49 +0200339 * behind the head is penalized and only allowed to a certain extent.
Linus Torvalds1da177e2005-04-16 15:20:36 -0700340 */
341static struct cfq_rq *
342cfq_choose_req(struct cfq_data *cfqd, struct cfq_rq *crq1, struct cfq_rq *crq2)
343{
344 sector_t last, s1, s2, d1 = 0, d2 = 0;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700345 unsigned long back_max;
Andreas Mohre8a99052006-03-28 08:59:49 +0200346#define CFQ_RQ1_WRAP 0x01 /* request 1 wraps */
347#define CFQ_RQ2_WRAP 0x02 /* request 2 wraps */
348 unsigned wrap = 0; /* bit mask: requests behind the disk head? */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700349
350 if (crq1 == NULL || crq1 == crq2)
351 return crq2;
352 if (crq2 == NULL)
353 return crq1;
Jens Axboe9c2c38a2005-08-24 14:57:54 +0200354
Jens Axboe9c2c38a2005-08-24 14:57:54 +0200355 if (cfq_crq_is_sync(crq1) && !cfq_crq_is_sync(crq2))
356 return crq1;
357 else if (cfq_crq_is_sync(crq2) && !cfq_crq_is_sync(crq1))
Jens Axboe22e2c502005-06-27 10:55:12 +0200358 return crq2;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700359
360 s1 = crq1->request->sector;
361 s2 = crq2->request->sector;
362
363 last = cfqd->last_sector;
364
Linus Torvalds1da177e2005-04-16 15:20:36 -0700365 /*
366 * by definition, 1KiB is 2 sectors
367 */
368 back_max = cfqd->cfq_back_max * 2;
369
370 /*
371 * Strict one way elevator _except_ in the case where we allow
372 * short backward seeks which are biased as twice the cost of a
373 * similar forward seek.
374 */
375 if (s1 >= last)
376 d1 = s1 - last;
377 else if (s1 + back_max >= last)
378 d1 = (last - s1) * cfqd->cfq_back_penalty;
379 else
Andreas Mohre8a99052006-03-28 08:59:49 +0200380 wrap |= CFQ_RQ1_WRAP;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700381
382 if (s2 >= last)
383 d2 = s2 - last;
384 else if (s2 + back_max >= last)
385 d2 = (last - s2) * cfqd->cfq_back_penalty;
386 else
Andreas Mohre8a99052006-03-28 08:59:49 +0200387 wrap |= CFQ_RQ2_WRAP;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700388
389 /* Found required data */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700390
Andreas Mohre8a99052006-03-28 08:59:49 +0200391 /*
392 * By doing switch() on the bit mask "wrap" we avoid having to
393 * check two variables for all permutations: --> faster!
394 */
395 switch (wrap) {
396 case 0: /* common case for CFQ: crq1 and crq2 not wrapped */
397 if (d1 < d2)
398 return crq1;
399 else if (d2 < d1)
400 return crq2;
401 else {
402 if (s1 >= s2)
403 return crq1;
404 else
405 return crq2;
406 }
407
408 case CFQ_RQ2_WRAP:
Linus Torvalds1da177e2005-04-16 15:20:36 -0700409 return crq1;
Andreas Mohre8a99052006-03-28 08:59:49 +0200410 case CFQ_RQ1_WRAP:
Linus Torvalds1da177e2005-04-16 15:20:36 -0700411 return crq2;
Andreas Mohre8a99052006-03-28 08:59:49 +0200412 case (CFQ_RQ1_WRAP|CFQ_RQ2_WRAP): /* both crqs wrapped */
413 default:
414 /*
415 * Since both rqs are wrapped,
416 * start with the one that's further behind head
417 * (--> only *one* back seek required),
418 * since back seek takes more time than forward.
419 */
420 if (s1 <= s2)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700421 return crq1;
422 else
423 return crq2;
424 }
425}
426
427/*
428 * would be nice to take fifo expire time into account as well
429 */
430static struct cfq_rq *
431cfq_find_next_crq(struct cfq_data *cfqd, struct cfq_queue *cfqq,
432 struct cfq_rq *last)
433{
434 struct cfq_rq *crq_next = NULL, *crq_prev = NULL;
435 struct rb_node *rbnext, *rbprev;
436
Jens Axboeb4878f22005-10-20 16:42:29 +0200437 if (!(rbnext = rb_next(&last->rb_node))) {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700438 rbnext = rb_first(&cfqq->sort_list);
Jens Axboe22e2c502005-06-27 10:55:12 +0200439 if (rbnext == &last->rb_node)
440 rbnext = NULL;
441 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700442
443 rbprev = rb_prev(&last->rb_node);
444
445 if (rbprev)
446 crq_prev = rb_entry_crq(rbprev);
447 if (rbnext)
448 crq_next = rb_entry_crq(rbnext);
449
450 return cfq_choose_req(cfqd, crq_next, crq_prev);
451}
452
453static void cfq_update_next_crq(struct cfq_rq *crq)
454{
455 struct cfq_queue *cfqq = crq->cfq_queue;
456
457 if (cfqq->next_crq == crq)
458 cfqq->next_crq = cfq_find_next_crq(cfqq->cfqd, cfqq, crq);
459}
460
Jens Axboe22e2c502005-06-27 10:55:12 +0200461static void cfq_resort_rr_list(struct cfq_queue *cfqq, int preempted)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700462{
Jens Axboe22e2c502005-06-27 10:55:12 +0200463 struct cfq_data *cfqd = cfqq->cfqd;
464 struct list_head *list, *entry;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700465
Jens Axboe3b181522005-06-27 10:56:24 +0200466 BUG_ON(!cfq_cfqq_on_rr(cfqq));
Linus Torvalds1da177e2005-04-16 15:20:36 -0700467
468 list_del(&cfqq->cfq_list);
469
Jens Axboe22e2c502005-06-27 10:55:12 +0200470 if (cfq_class_rt(cfqq))
471 list = &cfqd->cur_rr;
472 else if (cfq_class_idle(cfqq))
473 list = &cfqd->idle_rr;
474 else {
475 /*
476 * if cfqq has requests in flight, don't allow it to be
477 * found in cfq_set_active_queue before it has finished them.
478 * this is done to increase fairness between a process that
479 * has lots of io pending vs one that only generates one
480 * sporadically or synchronously
481 */
Jens Axboe3b181522005-06-27 10:56:24 +0200482 if (cfq_cfqq_dispatched(cfqq))
Jens Axboe22e2c502005-06-27 10:55:12 +0200483 list = &cfqd->busy_rr;
484 else
485 list = &cfqd->rr_list[cfqq->ioprio];
486 }
487
Linus Torvalds1da177e2005-04-16 15:20:36 -0700488 /*
Jens Axboe22e2c502005-06-27 10:55:12 +0200489 * if queue was preempted, just add to front to be fair. busy_rr
Jens Axboeb52a8342006-06-01 18:53:43 +0200490 * isn't sorted, but insert at the back for fairness.
Linus Torvalds1da177e2005-04-16 15:20:36 -0700491 */
Jens Axboe22e2c502005-06-27 10:55:12 +0200492 if (preempted || list == &cfqd->busy_rr) {
Jens Axboeb52a8342006-06-01 18:53:43 +0200493 if (preempted)
494 list = list->prev;
495
496 list_add_tail(&cfqq->cfq_list, list);
Jens Axboe22e2c502005-06-27 10:55:12 +0200497 return;
498 }
499
500 /*
501 * sort by when queue was last serviced
502 */
503 entry = list;
504 while ((entry = entry->prev) != list) {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700505 struct cfq_queue *__cfqq = list_entry_cfqq(entry);
506
Jens Axboe22e2c502005-06-27 10:55:12 +0200507 if (!__cfqq->service_last)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700508 break;
Jens Axboe22e2c502005-06-27 10:55:12 +0200509 if (time_before(__cfqq->service_last, cfqq->service_last))
510 break;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700511 }
512
513 list_add(&cfqq->cfq_list, entry);
514}
515
516/*
517 * add to busy list of queues for service, trying to be fair in ordering
Jens Axboe22e2c502005-06-27 10:55:12 +0200518 * the pending list according to last request service
Linus Torvalds1da177e2005-04-16 15:20:36 -0700519 */
520static inline void
Jens Axboeb4878f22005-10-20 16:42:29 +0200521cfq_add_cfqq_rr(struct cfq_data *cfqd, struct cfq_queue *cfqq)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700522{
Jens Axboe3b181522005-06-27 10:56:24 +0200523 BUG_ON(cfq_cfqq_on_rr(cfqq));
524 cfq_mark_cfqq_on_rr(cfqq);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700525 cfqd->busy_queues++;
526
Jens Axboeb4878f22005-10-20 16:42:29 +0200527 cfq_resort_rr_list(cfqq, 0);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700528}
529
530static inline void
531cfq_del_cfqq_rr(struct cfq_data *cfqd, struct cfq_queue *cfqq)
532{
Jens Axboe3b181522005-06-27 10:56:24 +0200533 BUG_ON(!cfq_cfqq_on_rr(cfqq));
534 cfq_clear_cfqq_on_rr(cfqq);
Jens Axboe22e2c502005-06-27 10:55:12 +0200535 list_move(&cfqq->cfq_list, &cfqd->empty_list);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700536
537 BUG_ON(!cfqd->busy_queues);
538 cfqd->busy_queues--;
539}
540
541/*
542 * rb tree support functions
543 */
544static inline void cfq_del_crq_rb(struct cfq_rq *crq)
545{
546 struct cfq_queue *cfqq = crq->cfq_queue;
Jens Axboeb4878f22005-10-20 16:42:29 +0200547 struct cfq_data *cfqd = cfqq->cfqd;
548 const int sync = cfq_crq_is_sync(crq);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700549
Jens Axboeb4878f22005-10-20 16:42:29 +0200550 BUG_ON(!cfqq->queued[sync]);
551 cfqq->queued[sync]--;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700552
Jens Axboeb4878f22005-10-20 16:42:29 +0200553 cfq_update_next_crq(crq);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700554
Jens Axboeb4878f22005-10-20 16:42:29 +0200555 rb_erase(&crq->rb_node, &cfqq->sort_list);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700556
Jens Axboedd67d052006-06-21 09:36:18 +0200557 if (cfq_cfqq_on_rr(cfqq) && RB_EMPTY_ROOT(&cfqq->sort_list))
Jens Axboeb4878f22005-10-20 16:42:29 +0200558 cfq_del_cfqq_rr(cfqd, cfqq);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700559}
560
561static struct cfq_rq *
562__cfq_add_crq_rb(struct cfq_rq *crq)
563{
564 struct rb_node **p = &crq->cfq_queue->sort_list.rb_node;
565 struct rb_node *parent = NULL;
566 struct cfq_rq *__crq;
567
568 while (*p) {
569 parent = *p;
570 __crq = rb_entry_crq(parent);
571
572 if (crq->rb_key < __crq->rb_key)
573 p = &(*p)->rb_left;
574 else if (crq->rb_key > __crq->rb_key)
575 p = &(*p)->rb_right;
576 else
577 return __crq;
578 }
579
580 rb_link_node(&crq->rb_node, parent, p);
581 return NULL;
582}
583
584static void cfq_add_crq_rb(struct cfq_rq *crq)
585{
586 struct cfq_queue *cfqq = crq->cfq_queue;
587 struct cfq_data *cfqd = cfqq->cfqd;
588 struct request *rq = crq->request;
589 struct cfq_rq *__alias;
590
591 crq->rb_key = rq_rb_key(rq);
Jens Axboe3b181522005-06-27 10:56:24 +0200592 cfqq->queued[cfq_crq_is_sync(crq)]++;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700593
594 /*
595 * looks a little odd, but the first insert might return an alias.
596 * if that happens, put the alias on the dispatch list
597 */
598 while ((__alias = __cfq_add_crq_rb(crq)) != NULL)
Jens Axboeb4878f22005-10-20 16:42:29 +0200599 cfq_dispatch_insert(cfqd->queue, __alias);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700600
601 rb_insert_color(&crq->rb_node, &cfqq->sort_list);
602
Jens Axboe3b181522005-06-27 10:56:24 +0200603 if (!cfq_cfqq_on_rr(cfqq))
Jens Axboeb4878f22005-10-20 16:42:29 +0200604 cfq_add_cfqq_rr(cfqd, cfqq);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700605
606 /*
607 * check if this request is a better next-serve candidate
608 */
609 cfqq->next_crq = cfq_choose_req(cfqd, cfqq->next_crq, crq);
610}
611
612static inline void
613cfq_reposition_crq_rb(struct cfq_queue *cfqq, struct cfq_rq *crq)
614{
Jens Axboeb4878f22005-10-20 16:42:29 +0200615 rb_erase(&crq->rb_node, &cfqq->sort_list);
616 cfqq->queued[cfq_crq_is_sync(crq)]--;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700617
618 cfq_add_crq_rb(crq);
619}
620
Jens Axboe206dc692006-03-28 13:03:44 +0200621static struct request *
622cfq_find_rq_fmerge(struct cfq_data *cfqd, struct bio *bio)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700623{
Jens Axboe206dc692006-03-28 13:03:44 +0200624 struct task_struct *tsk = current;
625 pid_t key = cfq_queue_pid(tsk, bio_data_dir(bio));
626 struct cfq_queue *cfqq;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700627 struct rb_node *n;
Jens Axboe206dc692006-03-28 13:03:44 +0200628 sector_t sector;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700629
Jens Axboe206dc692006-03-28 13:03:44 +0200630 cfqq = cfq_find_cfq_hash(cfqd, key, tsk->ioprio);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700631 if (!cfqq)
632 goto out;
633
Jens Axboe206dc692006-03-28 13:03:44 +0200634 sector = bio->bi_sector + bio_sectors(bio);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700635 n = cfqq->sort_list.rb_node;
636 while (n) {
637 struct cfq_rq *crq = rb_entry_crq(n);
638
639 if (sector < crq->rb_key)
640 n = n->rb_left;
641 else if (sector > crq->rb_key)
642 n = n->rb_right;
643 else
644 return crq->request;
645 }
646
647out:
648 return NULL;
649}
650
Jens Axboeb4878f22005-10-20 16:42:29 +0200651static void cfq_activate_request(request_queue_t *q, struct request *rq)
652{
653 struct cfq_data *cfqd = q->elevator->elevator_data;
654
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 Axboeb4878f22005-10-20 16:42:29 +0200665}
666
Linus Torvalds1da177e2005-04-16 15:20:36 -0700667static void cfq_deactivate_request(request_queue_t *q, struct request *rq)
668{
Jens Axboe22e2c502005-06-27 10:55:12 +0200669 struct cfq_data *cfqd = q->elevator->elevator_data;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700670
Jens Axboeb4878f22005-10-20 16:42:29 +0200671 WARN_ON(!cfqd->rq_in_driver);
672 cfqd->rq_in_driver--;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700673}
674
Jens Axboeb4878f22005-10-20 16:42:29 +0200675static void cfq_remove_request(struct request *rq)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700676{
677 struct cfq_rq *crq = RQ_DATA(rq);
678
Jens Axboeb4878f22005-10-20 16:42:29 +0200679 list_del_init(&rq->queuelist);
680 cfq_del_crq_rb(crq);
Tejun Heo98b11472005-10-20 16:46:54 +0200681 cfq_del_crq_hash(crq);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700682}
683
684static int
685cfq_merge(request_queue_t *q, struct request **req, struct bio *bio)
686{
687 struct cfq_data *cfqd = q->elevator->elevator_data;
688 struct request *__rq;
689 int ret;
690
Linus Torvalds1da177e2005-04-16 15:20:36 -0700691 __rq = cfq_find_rq_hash(cfqd, bio->bi_sector);
Jens Axboe22e2c502005-06-27 10:55:12 +0200692 if (__rq && elv_rq_merge_ok(__rq, bio)) {
693 ret = ELEVATOR_BACK_MERGE;
694 goto out;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700695 }
696
Jens Axboe206dc692006-03-28 13:03:44 +0200697 __rq = cfq_find_rq_fmerge(cfqd, bio);
Jens Axboe22e2c502005-06-27 10:55:12 +0200698 if (__rq && elv_rq_merge_ok(__rq, bio)) {
699 ret = ELEVATOR_FRONT_MERGE;
700 goto out;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700701 }
702
703 return ELEVATOR_NO_MERGE;
704out:
Linus Torvalds1da177e2005-04-16 15:20:36 -0700705 *req = __rq;
706 return ret;
707}
708
709static void cfq_merged_request(request_queue_t *q, struct request *req)
710{
711 struct cfq_data *cfqd = q->elevator->elevator_data;
712 struct cfq_rq *crq = RQ_DATA(req);
713
714 cfq_del_crq_hash(crq);
715 cfq_add_crq_hash(cfqd, crq);
716
Jens Axboeb4878f22005-10-20 16:42:29 +0200717 if (rq_rb_key(req) != crq->rb_key) {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700718 struct cfq_queue *cfqq = crq->cfq_queue;
719
720 cfq_update_next_crq(crq);
721 cfq_reposition_crq_rb(cfqq, crq);
722 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700723}
724
725static void
726cfq_merged_requests(request_queue_t *q, struct request *rq,
727 struct request *next)
728{
Linus Torvalds1da177e2005-04-16 15:20:36 -0700729 cfq_merged_request(q, rq);
730
Jens Axboe22e2c502005-06-27 10:55:12 +0200731 /*
732 * reposition in fifo if next is older than rq
733 */
734 if (!list_empty(&rq->queuelist) && !list_empty(&next->queuelist) &&
735 time_before(next->start_time, rq->start_time))
736 list_move(&rq->queuelist, &next->queuelist);
737
Jens Axboeb4878f22005-10-20 16:42:29 +0200738 cfq_remove_request(next);
Jens Axboe22e2c502005-06-27 10:55:12 +0200739}
740
741static inline void
742__cfq_set_active_queue(struct cfq_data *cfqd, struct cfq_queue *cfqq)
743{
744 if (cfqq) {
745 /*
746 * stop potential idle class queues waiting service
747 */
748 del_timer(&cfqd->idle_class_timer);
749
750 cfqq->slice_start = jiffies;
751 cfqq->slice_end = 0;
752 cfqq->slice_left = 0;
Jens Axboe3b181522005-06-27 10:56:24 +0200753 cfq_clear_cfqq_must_alloc_slice(cfqq);
754 cfq_clear_cfqq_fifo_expire(cfqq);
Jens Axboe22e2c502005-06-27 10:55:12 +0200755 }
756
757 cfqd->active_queue = cfqq;
758}
759
760/*
Jens Axboe7b14e3b2006-02-28 09:35:11 +0100761 * current cfqq expired its slice (or was too idle), select new one
762 */
763static void
764__cfq_slice_expired(struct cfq_data *cfqd, struct cfq_queue *cfqq,
765 int preempted)
766{
767 unsigned long now = jiffies;
768
769 if (cfq_cfqq_wait_request(cfqq))
770 del_timer(&cfqd->idle_slice_timer);
771
772 if (!preempted && !cfq_cfqq_dispatched(cfqq)) {
773 cfqq->service_last = now;
774 cfq_schedule_dispatch(cfqd);
775 }
776
777 cfq_clear_cfqq_must_dispatch(cfqq);
778 cfq_clear_cfqq_wait_request(cfqq);
779
780 /*
781 * store what was left of this slice, if the queue idled out
782 * or was preempted
783 */
784 if (time_after(cfqq->slice_end, now))
785 cfqq->slice_left = cfqq->slice_end - now;
786 else
787 cfqq->slice_left = 0;
788
789 if (cfq_cfqq_on_rr(cfqq))
790 cfq_resort_rr_list(cfqq, preempted);
791
792 if (cfqq == cfqd->active_queue)
793 cfqd->active_queue = NULL;
794
795 if (cfqd->active_cic) {
796 put_io_context(cfqd->active_cic->ioc);
797 cfqd->active_cic = NULL;
798 }
799
800 cfqd->dispatch_slice = 0;
801}
802
803static inline void cfq_slice_expired(struct cfq_data *cfqd, int preempted)
804{
805 struct cfq_queue *cfqq = cfqd->active_queue;
806
807 if (cfqq)
808 __cfq_slice_expired(cfqd, cfqq, preempted);
809}
810
811/*
Jens Axboe22e2c502005-06-27 10:55:12 +0200812 * 0
813 * 0,1
814 * 0,1,2
815 * 0,1,2,3
816 * 0,1,2,3,4
817 * 0,1,2,3,4,5
818 * 0,1,2,3,4,5,6
819 * 0,1,2,3,4,5,6,7
820 */
821static int cfq_get_next_prio_level(struct cfq_data *cfqd)
822{
823 int prio, wrap;
824
825 prio = -1;
826 wrap = 0;
827 do {
828 int p;
829
830 for (p = cfqd->cur_prio; p <= cfqd->cur_end_prio; p++) {
831 if (!list_empty(&cfqd->rr_list[p])) {
832 prio = p;
833 break;
834 }
835 }
836
837 if (prio != -1)
838 break;
839 cfqd->cur_prio = 0;
840 if (++cfqd->cur_end_prio == CFQ_PRIO_LISTS) {
841 cfqd->cur_end_prio = 0;
842 if (wrap)
843 break;
844 wrap = 1;
845 }
846 } while (1);
847
848 if (unlikely(prio == -1))
849 return -1;
850
851 BUG_ON(prio >= CFQ_PRIO_LISTS);
852
853 list_splice_init(&cfqd->rr_list[prio], &cfqd->cur_rr);
854
855 cfqd->cur_prio = prio + 1;
856 if (cfqd->cur_prio > cfqd->cur_end_prio) {
857 cfqd->cur_end_prio = cfqd->cur_prio;
858 cfqd->cur_prio = 0;
859 }
860 if (cfqd->cur_end_prio == CFQ_PRIO_LISTS) {
861 cfqd->cur_prio = 0;
862 cfqd->cur_end_prio = 0;
863 }
864
865 return prio;
866}
867
Jens Axboe3b181522005-06-27 10:56:24 +0200868static struct cfq_queue *cfq_set_active_queue(struct cfq_data *cfqd)
Jens Axboe22e2c502005-06-27 10:55:12 +0200869{
Jens Axboe7b14e3b2006-02-28 09:35:11 +0100870 struct cfq_queue *cfqq = NULL;
Jens Axboe22e2c502005-06-27 10:55:12 +0200871
872 /*
873 * if current list is non-empty, grab first entry. if it is empty,
874 * get next prio level and grab first entry then if any are spliced
875 */
876 if (!list_empty(&cfqd->cur_rr) || cfq_get_next_prio_level(cfqd) != -1)
877 cfqq = list_entry_cfqq(cfqd->cur_rr.next);
878
879 /*
Jens Axboee0de0202006-06-01 10:07:26 +0200880 * If no new queues are available, check if the busy list has some
881 * before falling back to idle io.
882 */
883 if (!cfqq && !list_empty(&cfqd->busy_rr))
884 cfqq = list_entry_cfqq(cfqd->busy_rr.next);
885
886 /*
Jens Axboe22e2c502005-06-27 10:55:12 +0200887 * if we have idle queues and no rt or be queues had pending
888 * requests, either allow immediate service if the grace period
889 * has passed or arm the idle grace timer
890 */
891 if (!cfqq && !list_empty(&cfqd->idle_rr)) {
892 unsigned long end = cfqd->last_end_request + CFQ_IDLE_GRACE;
893
894 if (time_after_eq(jiffies, end))
895 cfqq = list_entry_cfqq(cfqd->idle_rr.next);
896 else
897 mod_timer(&cfqd->idle_class_timer, end);
898 }
899
900 __cfq_set_active_queue(cfqd, cfqq);
Jens Axboe3b181522005-06-27 10:56:24 +0200901 return cfqq;
Jens Axboe22e2c502005-06-27 10:55:12 +0200902}
903
Jens Axboecaaa5f92006-06-16 11:23:00 +0200904#define CIC_SEEKY(cic) ((cic)->seek_mean > (128 * 1024))
905
Jens Axboe22e2c502005-06-27 10:55:12 +0200906static int cfq_arm_slice_timer(struct cfq_data *cfqd, struct cfq_queue *cfqq)
907
908{
Jens Axboe206dc692006-03-28 13:03:44 +0200909 struct cfq_io_context *cic;
Jens Axboe7b14e3b2006-02-28 09:35:11 +0100910 unsigned long sl;
911
Jens Axboedd67d052006-06-21 09:36:18 +0200912 WARN_ON(!RB_EMPTY_ROOT(&cfqq->sort_list));
Jens Axboe22e2c502005-06-27 10:55:12 +0200913 WARN_ON(cfqq != cfqd->active_queue);
914
915 /*
916 * idle is disabled, either manually or by past process history
917 */
918 if (!cfqd->cfq_slice_idle)
919 return 0;
Jens Axboe3b181522005-06-27 10:56:24 +0200920 if (!cfq_cfqq_idle_window(cfqq))
Jens Axboe22e2c502005-06-27 10:55:12 +0200921 return 0;
922 /*
923 * task has exited, don't wait
924 */
Jens Axboe206dc692006-03-28 13:03:44 +0200925 cic = cfqd->active_cic;
926 if (!cic || !cic->ioc->task)
Jens Axboe22e2c502005-06-27 10:55:12 +0200927 return 0;
928
Jens Axboe3b181522005-06-27 10:56:24 +0200929 cfq_mark_cfqq_must_dispatch(cfqq);
930 cfq_mark_cfqq_wait_request(cfqq);
Jens Axboe22e2c502005-06-27 10:55:12 +0200931
Jens Axboe7b14e3b2006-02-28 09:35:11 +0100932 sl = min(cfqq->slice_end - 1, (unsigned long) cfqd->cfq_slice_idle);
Jens Axboe206dc692006-03-28 13:03:44 +0200933
934 /*
935 * we don't want to idle for seeks, but we do want to allow
936 * fair distribution of slice time for a process doing back-to-back
937 * seeks. so allow a little bit of time for him to submit a new rq
938 */
Jens Axboecaaa5f92006-06-16 11:23:00 +0200939 if (sample_valid(cic->seek_samples) && CIC_SEEKY(cic))
Jens Axboe206dc692006-03-28 13:03:44 +0200940 sl = 2;
941
Jens Axboe7b14e3b2006-02-28 09:35:11 +0100942 mod_timer(&cfqd->idle_slice_timer, jiffies + sl);
Jens Axboe22e2c502005-06-27 10:55:12 +0200943 return 1;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700944}
945
Jens Axboeb4878f22005-10-20 16:42:29 +0200946static void cfq_dispatch_insert(request_queue_t *q, struct cfq_rq *crq)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700947{
948 struct cfq_data *cfqd = q->elevator->elevator_data;
949 struct cfq_queue *cfqq = crq->cfq_queue;
Jens Axboefd61af02006-06-16 15:35:39 +0200950 struct request *rq;
Jens Axboe22e2c502005-06-27 10:55:12 +0200951
952 cfqq->next_crq = cfq_find_next_crq(cfqd, cfqq, crq);
Jens Axboeb4878f22005-10-20 16:42:29 +0200953 cfq_remove_request(crq->request);
Jens Axboe3b181522005-06-27 10:56:24 +0200954 cfqq->on_dispatch[cfq_crq_is_sync(crq)]++;
Jens Axboeb4878f22005-10-20 16:42:29 +0200955 elv_dispatch_sort(q, crq->request);
Jens Axboefd61af02006-06-16 15:35:39 +0200956
957 rq = list_entry(q->queue_head.prev, struct request, queuelist);
958 cfqd->last_sector = rq->sector + rq->nr_sectors;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700959}
960
961/*
962 * return expired entry, or NULL to just start from scratch in rbtree
963 */
964static inline struct cfq_rq *cfq_check_fifo(struct cfq_queue *cfqq)
965{
966 struct cfq_data *cfqd = cfqq->cfqd;
Jens Axboe22e2c502005-06-27 10:55:12 +0200967 struct request *rq;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700968 struct cfq_rq *crq;
969
Jens Axboe3b181522005-06-27 10:56:24 +0200970 if (cfq_cfqq_fifo_expire(cfqq))
Linus Torvalds1da177e2005-04-16 15:20:36 -0700971 return NULL;
972
Jens Axboe22e2c502005-06-27 10:55:12 +0200973 if (!list_empty(&cfqq->fifo)) {
Jens Axboe3b181522005-06-27 10:56:24 +0200974 int fifo = cfq_cfqq_class_sync(cfqq);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700975
Jens Axboe22e2c502005-06-27 10:55:12 +0200976 crq = RQ_DATA(list_entry_fifo(cfqq->fifo.next));
977 rq = crq->request;
978 if (time_after(jiffies, rq->start_time + cfqd->cfq_fifo_expire[fifo])) {
Jens Axboe3b181522005-06-27 10:56:24 +0200979 cfq_mark_cfqq_fifo_expire(cfqq);
Jens Axboe22e2c502005-06-27 10:55:12 +0200980 return crq;
981 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700982 }
983
984 return NULL;
985}
986
987/*
Jens Axboe3b181522005-06-27 10:56:24 +0200988 * Scale schedule slice based on io priority. Use the sync time slice only
989 * if a queue is marked sync and has sync io queued. A sync queue with async
990 * io only, should not get full sync slice length.
Linus Torvalds1da177e2005-04-16 15:20:36 -0700991 */
Jens Axboe22e2c502005-06-27 10:55:12 +0200992static inline int
993cfq_prio_to_slice(struct cfq_data *cfqd, struct cfq_queue *cfqq)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700994{
Jens Axboe22e2c502005-06-27 10:55:12 +0200995 const int base_slice = cfqd->cfq_slice[cfq_cfqq_sync(cfqq)];
Linus Torvalds1da177e2005-04-16 15:20:36 -0700996
Jens Axboe22e2c502005-06-27 10:55:12 +0200997 WARN_ON(cfqq->ioprio >= IOPRIO_BE_NR);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700998
Jens Axboe22e2c502005-06-27 10:55:12 +0200999 return base_slice + (base_slice/CFQ_SLICE_SCALE * (4 - cfqq->ioprio));
Linus Torvalds1da177e2005-04-16 15:20:36 -07001000}
1001
Jens Axboe22e2c502005-06-27 10:55:12 +02001002static inline void
1003cfq_set_prio_slice(struct cfq_data *cfqd, struct cfq_queue *cfqq)
1004{
1005 cfqq->slice_end = cfq_prio_to_slice(cfqd, cfqq) + jiffies;
1006}
1007
1008static inline int
1009cfq_prio_to_maxrq(struct cfq_data *cfqd, struct cfq_queue *cfqq)
1010{
1011 const int base_rq = cfqd->cfq_slice_async_rq;
1012
1013 WARN_ON(cfqq->ioprio >= IOPRIO_BE_NR);
1014
1015 return 2 * (base_rq + base_rq * (CFQ_PRIO_LISTS - 1 - cfqq->ioprio));
1016}
1017
1018/*
1019 * get next queue for service
1020 */
Tejun Heo1b5ed5e12005-11-10 08:49:19 +01001021static struct cfq_queue *cfq_select_queue(struct cfq_data *cfqd)
Jens Axboe22e2c502005-06-27 10:55:12 +02001022{
1023 unsigned long now = jiffies;
1024 struct cfq_queue *cfqq;
1025
1026 cfqq = cfqd->active_queue;
1027 if (!cfqq)
1028 goto new_queue;
1029
1030 /*
1031 * slice has expired
1032 */
Jens Axboe3b181522005-06-27 10:56:24 +02001033 if (!cfq_cfqq_must_dispatch(cfqq) && time_after(now, cfqq->slice_end))
1034 goto expire;
Jens Axboe22e2c502005-06-27 10:55:12 +02001035
1036 /*
1037 * if queue has requests, dispatch one. if not, check if
1038 * enough slice is left to wait for one
1039 */
Jens Axboedd67d052006-06-21 09:36:18 +02001040 if (!RB_EMPTY_ROOT(&cfqq->sort_list))
Jens Axboe22e2c502005-06-27 10:55:12 +02001041 goto keep_queue;
Jens Axboecaaa5f92006-06-16 11:23:00 +02001042 else if (cfq_cfqq_dispatched(cfqq)) {
1043 cfqq = NULL;
1044 goto keep_queue;
1045 } else if (cfq_cfqq_class_sync(cfqq)) {
Jens Axboe22e2c502005-06-27 10:55:12 +02001046 if (cfq_arm_slice_timer(cfqd, cfqq))
1047 return NULL;
1048 }
1049
Jens Axboe3b181522005-06-27 10:56:24 +02001050expire:
Jens Axboe22e2c502005-06-27 10:55:12 +02001051 cfq_slice_expired(cfqd, 0);
Jens Axboe3b181522005-06-27 10:56:24 +02001052new_queue:
1053 cfqq = cfq_set_active_queue(cfqd);
Jens Axboe22e2c502005-06-27 10:55:12 +02001054keep_queue:
Jens Axboe3b181522005-06-27 10:56:24 +02001055 return cfqq;
Jens Axboe22e2c502005-06-27 10:55:12 +02001056}
1057
1058static int
1059__cfq_dispatch_requests(struct cfq_data *cfqd, struct cfq_queue *cfqq,
1060 int max_dispatch)
1061{
1062 int dispatched = 0;
1063
Jens Axboedd67d052006-06-21 09:36:18 +02001064 BUG_ON(RB_EMPTY_ROOT(&cfqq->sort_list));
Jens Axboe22e2c502005-06-27 10:55:12 +02001065
1066 do {
1067 struct cfq_rq *crq;
1068
1069 /*
1070 * follow expired path, else get first next available
1071 */
1072 if ((crq = cfq_check_fifo(cfqq)) == NULL)
1073 crq = cfqq->next_crq;
1074
1075 /*
1076 * finally, insert request into driver dispatch list
1077 */
Jens Axboeb4878f22005-10-20 16:42:29 +02001078 cfq_dispatch_insert(cfqd->queue, crq);
Jens Axboe22e2c502005-06-27 10:55:12 +02001079
1080 cfqd->dispatch_slice++;
1081 dispatched++;
1082
1083 if (!cfqd->active_cic) {
1084 atomic_inc(&crq->io_context->ioc->refcount);
1085 cfqd->active_cic = crq->io_context;
1086 }
1087
Jens Axboedd67d052006-06-21 09:36:18 +02001088 if (RB_EMPTY_ROOT(&cfqq->sort_list))
Jens Axboe22e2c502005-06-27 10:55:12 +02001089 break;
1090
1091 } while (dispatched < max_dispatch);
1092
1093 /*
Jens Axboecaaa5f92006-06-16 11:23:00 +02001094 * if slice end isn't set yet, set it.
Jens Axboe22e2c502005-06-27 10:55:12 +02001095 */
1096 if (!cfqq->slice_end)
1097 cfq_set_prio_slice(cfqd, cfqq);
1098
1099 /*
1100 * expire an async queue immediately if it has used up its slice. idle
1101 * queue always expire after 1 dispatch round.
1102 */
1103 if ((!cfq_cfqq_sync(cfqq) &&
1104 cfqd->dispatch_slice >= cfq_prio_to_maxrq(cfqd, cfqq)) ||
Jens Axboecaaa5f92006-06-16 11:23:00 +02001105 cfq_class_idle(cfqq) ||
1106 !cfq_cfqq_idle_window(cfqq))
Jens Axboe22e2c502005-06-27 10:55:12 +02001107 cfq_slice_expired(cfqd, 0);
1108
1109 return dispatched;
1110}
1111
1112static int
Tejun Heo1b5ed5e12005-11-10 08:49:19 +01001113cfq_forced_dispatch_cfqqs(struct list_head *list)
1114{
Tejun Heo1b5ed5e12005-11-10 08:49:19 +01001115 struct cfq_queue *cfqq, *next;
1116 struct cfq_rq *crq;
Jens Axboecaaa5f92006-06-16 11:23:00 +02001117 int dispatched;
Tejun Heo1b5ed5e12005-11-10 08:49:19 +01001118
Jens Axboecaaa5f92006-06-16 11:23:00 +02001119 dispatched = 0;
Tejun Heo1b5ed5e12005-11-10 08:49:19 +01001120 list_for_each_entry_safe(cfqq, next, list, cfq_list) {
1121 while ((crq = cfqq->next_crq)) {
1122 cfq_dispatch_insert(cfqq->cfqd->queue, crq);
1123 dispatched++;
1124 }
1125 BUG_ON(!list_empty(&cfqq->fifo));
1126 }
Jens Axboecaaa5f92006-06-16 11:23:00 +02001127
Tejun Heo1b5ed5e12005-11-10 08:49:19 +01001128 return dispatched;
1129}
1130
1131static int
1132cfq_forced_dispatch(struct cfq_data *cfqd)
1133{
1134 int i, dispatched = 0;
1135
1136 for (i = 0; i < CFQ_PRIO_LISTS; i++)
1137 dispatched += cfq_forced_dispatch_cfqqs(&cfqd->rr_list[i]);
1138
1139 dispatched += cfq_forced_dispatch_cfqqs(&cfqd->busy_rr);
1140 dispatched += cfq_forced_dispatch_cfqqs(&cfqd->cur_rr);
1141 dispatched += cfq_forced_dispatch_cfqqs(&cfqd->idle_rr);
1142
1143 cfq_slice_expired(cfqd, 0);
1144
1145 BUG_ON(cfqd->busy_queues);
1146
1147 return dispatched;
1148}
1149
1150static int
Jens Axboeb4878f22005-10-20 16:42:29 +02001151cfq_dispatch_requests(request_queue_t *q, int force)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001152{
1153 struct cfq_data *cfqd = q->elevator->elevator_data;
Jens Axboecaaa5f92006-06-16 11:23:00 +02001154 struct cfq_queue *cfqq, *prev_cfqq;
1155 int dispatched;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001156
Jens Axboe22e2c502005-06-27 10:55:12 +02001157 if (!cfqd->busy_queues)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001158 return 0;
1159
Tejun Heo1b5ed5e12005-11-10 08:49:19 +01001160 if (unlikely(force))
1161 return cfq_forced_dispatch(cfqd);
1162
Jens Axboecaaa5f92006-06-16 11:23:00 +02001163 dispatched = 0;
1164 prev_cfqq = NULL;
1165 while ((cfqq = cfq_select_queue(cfqd)) != NULL) {
Jens Axboeb4878f22005-10-20 16:42:29 +02001166 int max_dispatch;
1167
Jens Axboecaaa5f92006-06-16 11:23:00 +02001168 /*
1169 * Don't repeat dispatch from the previous queue.
1170 */
1171 if (prev_cfqq == cfqq)
1172 break;
1173
Jens Axboe3b181522005-06-27 10:56:24 +02001174 cfq_clear_cfqq_must_dispatch(cfqq);
1175 cfq_clear_cfqq_wait_request(cfqq);
Jens Axboe22e2c502005-06-27 10:55:12 +02001176 del_timer(&cfqd->idle_slice_timer);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001177
Tejun Heo1b5ed5e12005-11-10 08:49:19 +01001178 max_dispatch = cfqd->cfq_quantum;
1179 if (cfq_class_idle(cfqq))
1180 max_dispatch = 1;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001181
Jens Axboecaaa5f92006-06-16 11:23:00 +02001182 dispatched += __cfq_dispatch_requests(cfqd, cfqq, max_dispatch);
1183
1184 /*
1185 * If the dispatch cfqq has idling enabled and is still
1186 * the active queue, break out.
1187 */
1188 if (cfq_cfqq_idle_window(cfqq) && cfqd->active_queue)
1189 break;
1190
1191 prev_cfqq = cfqq;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001192 }
1193
Jens Axboecaaa5f92006-06-16 11:23:00 +02001194 return dispatched;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001195}
1196
Linus Torvalds1da177e2005-04-16 15:20:36 -07001197/*
1198 * task holds one reference to the queue, dropped when task exits. each crq
1199 * in-flight on this queue also holds a reference, dropped when crq is freed.
1200 *
1201 * queue lock must be held here.
1202 */
1203static void cfq_put_queue(struct cfq_queue *cfqq)
1204{
Jens Axboe22e2c502005-06-27 10:55:12 +02001205 struct cfq_data *cfqd = cfqq->cfqd;
1206
1207 BUG_ON(atomic_read(&cfqq->ref) <= 0);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001208
1209 if (!atomic_dec_and_test(&cfqq->ref))
1210 return;
1211
1212 BUG_ON(rb_first(&cfqq->sort_list));
Jens Axboe22e2c502005-06-27 10:55:12 +02001213 BUG_ON(cfqq->allocated[READ] + cfqq->allocated[WRITE]);
Jens Axboe3b181522005-06-27 10:56:24 +02001214 BUG_ON(cfq_cfqq_on_rr(cfqq));
Linus Torvalds1da177e2005-04-16 15:20:36 -07001215
Jens Axboe7b14e3b2006-02-28 09:35:11 +01001216 if (unlikely(cfqd->active_queue == cfqq))
Jens Axboe3b181522005-06-27 10:56:24 +02001217 __cfq_slice_expired(cfqd, cfqq, 0);
Jens Axboe22e2c502005-06-27 10:55:12 +02001218
Linus Torvalds1da177e2005-04-16 15:20:36 -07001219 /*
1220 * it's on the empty list and still hashed
1221 */
1222 list_del(&cfqq->cfq_list);
1223 hlist_del(&cfqq->cfq_hash);
1224 kmem_cache_free(cfq_pool, cfqq);
1225}
1226
1227static inline struct cfq_queue *
Jens Axboe3b181522005-06-27 10:56:24 +02001228__cfq_find_cfq_hash(struct cfq_data *cfqd, unsigned int key, unsigned int prio,
1229 const int hashval)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001230{
1231 struct hlist_head *hash_list = &cfqd->cfq_hash[hashval];
Jens Axboe206dc692006-03-28 13:03:44 +02001232 struct hlist_node *entry;
1233 struct cfq_queue *__cfqq;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001234
Jens Axboe206dc692006-03-28 13:03:44 +02001235 hlist_for_each_entry(__cfqq, entry, hash_list, cfq_hash) {
Al Virob0a69162006-03-14 15:32:50 -05001236 const unsigned short __p = IOPRIO_PRIO_VALUE(__cfqq->org_ioprio_class, __cfqq->org_ioprio);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001237
Jens Axboe206dc692006-03-28 13:03:44 +02001238 if (__cfqq->key == key && (__p == prio || !prio))
Linus Torvalds1da177e2005-04-16 15:20:36 -07001239 return __cfqq;
1240 }
1241
1242 return NULL;
1243}
1244
1245static struct cfq_queue *
Jens Axboe3b181522005-06-27 10:56:24 +02001246cfq_find_cfq_hash(struct cfq_data *cfqd, unsigned int key, unsigned short prio)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001247{
Jens Axboe3b181522005-06-27 10:56:24 +02001248 return __cfq_find_cfq_hash(cfqd, key, prio, hash_long(key, CFQ_QHASH_SHIFT));
Linus Torvalds1da177e2005-04-16 15:20:36 -07001249}
1250
Jens Axboee2d74ac2006-03-28 08:59:01 +02001251static void cfq_free_io_context(struct io_context *ioc)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001252{
Jens Axboe22e2c502005-06-27 10:55:12 +02001253 struct cfq_io_context *__cic;
Jens Axboee2d74ac2006-03-28 08:59:01 +02001254 struct rb_node *n;
1255 int freed = 0;
Jens Axboe22e2c502005-06-27 10:55:12 +02001256
Jens Axboee2d74ac2006-03-28 08:59:01 +02001257 while ((n = rb_first(&ioc->cic_root)) != NULL) {
1258 __cic = rb_entry(n, struct cfq_io_context, rb_node);
1259 rb_erase(&__cic->rb_node, &ioc->cic_root);
Jens Axboe22e2c502005-06-27 10:55:12 +02001260 kmem_cache_free(cfq_ioc_pool, __cic);
Al Viro334e94d2006-03-18 15:05:53 -05001261 freed++;
Jens Axboe22e2c502005-06-27 10:55:12 +02001262 }
1263
Al Viro334e94d2006-03-18 15:05:53 -05001264 if (atomic_sub_and_test(freed, &ioc_count) && ioc_gone)
1265 complete(ioc_gone);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001266}
1267
Al Viroe17a9482006-03-18 13:21:20 -05001268static void cfq_trim(struct io_context *ioc)
1269{
1270 ioc->set_ioprio = NULL;
Jens Axboee2d74ac2006-03-28 08:59:01 +02001271 cfq_free_io_context(ioc);
Al Viroe17a9482006-03-18 13:21:20 -05001272}
1273
Linus Torvalds1da177e2005-04-16 15:20:36 -07001274/*
Jens Axboe22e2c502005-06-27 10:55:12 +02001275 * Called with interrupts disabled
1276 */
1277static void cfq_exit_single_io_context(struct cfq_io_context *cic)
1278{
Al Viro478a82b2006-03-18 13:25:24 -05001279 struct cfq_data *cfqd = cic->key;
Al Virod9ff4182006-03-18 13:51:22 -05001280 request_queue_t *q;
1281
1282 if (!cfqd)
1283 return;
1284
1285 q = cfqd->queue;
Jens Axboe22e2c502005-06-27 10:55:12 +02001286
1287 WARN_ON(!irqs_disabled());
1288
1289 spin_lock(q->queue_lock);
1290
Al Viro12a05732006-03-18 13:38:01 -05001291 if (cic->cfqq[ASYNC]) {
1292 if (unlikely(cic->cfqq[ASYNC] == cfqd->active_queue))
1293 __cfq_slice_expired(cfqd, cic->cfqq[ASYNC], 0);
1294 cfq_put_queue(cic->cfqq[ASYNC]);
1295 cic->cfqq[ASYNC] = NULL;
1296 }
Jens Axboe22e2c502005-06-27 10:55:12 +02001297
Al Viro12a05732006-03-18 13:38:01 -05001298 if (cic->cfqq[SYNC]) {
1299 if (unlikely(cic->cfqq[SYNC] == cfqd->active_queue))
1300 __cfq_slice_expired(cfqd, cic->cfqq[SYNC], 0);
1301 cfq_put_queue(cic->cfqq[SYNC]);
1302 cic->cfqq[SYNC] = NULL;
1303 }
1304
Al Viro478a82b2006-03-18 13:25:24 -05001305 cic->key = NULL;
Al Virod9ff4182006-03-18 13:51:22 -05001306 list_del_init(&cic->queue_list);
Jens Axboe22e2c502005-06-27 10:55:12 +02001307 spin_unlock(q->queue_lock);
1308}
1309
Jens Axboee2d74ac2006-03-28 08:59:01 +02001310static void cfq_exit_io_context(struct io_context *ioc)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001311{
Jens Axboe22e2c502005-06-27 10:55:12 +02001312 struct cfq_io_context *__cic;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001313 unsigned long flags;
Jens Axboee2d74ac2006-03-28 08:59:01 +02001314 struct rb_node *n;
Jens Axboe22e2c502005-06-27 10:55:12 +02001315
Linus Torvalds1da177e2005-04-16 15:20:36 -07001316 /*
1317 * put the reference this task is holding to the various queues
1318 */
Jens Axboe3793c652006-05-30 21:11:04 +02001319 spin_lock_irqsave(&cfq_exit_lock, flags);
Jens Axboee2d74ac2006-03-28 08:59:01 +02001320
1321 n = rb_first(&ioc->cic_root);
1322 while (n != NULL) {
1323 __cic = rb_entry(n, struct cfq_io_context, rb_node);
1324
Jens Axboe22e2c502005-06-27 10:55:12 +02001325 cfq_exit_single_io_context(__cic);
Jens Axboee2d74ac2006-03-28 08:59:01 +02001326 n = rb_next(n);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001327 }
1328
Jens Axboe3793c652006-05-30 21:11:04 +02001329 spin_unlock_irqrestore(&cfq_exit_lock, flags);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001330}
1331
Jens Axboe22e2c502005-06-27 10:55:12 +02001332static struct cfq_io_context *
Al Viro8267e262005-10-21 03:20:53 -04001333cfq_alloc_io_context(struct cfq_data *cfqd, gfp_t gfp_mask)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001334{
Jens Axboe22e2c502005-06-27 10:55:12 +02001335 struct cfq_io_context *cic = kmem_cache_alloc(cfq_ioc_pool, gfp_mask);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001336
1337 if (cic) {
Jens Axboe553698f2006-06-14 19:11:57 +02001338 memset(cic, 0, sizeof(*cic));
Jens Axboe22e2c502005-06-27 10:55:12 +02001339 cic->last_end_request = jiffies;
Jens Axboe553698f2006-06-14 19:11:57 +02001340 INIT_LIST_HEAD(&cic->queue_list);
Jens Axboe22e2c502005-06-27 10:55:12 +02001341 cic->dtor = cfq_free_io_context;
1342 cic->exit = cfq_exit_io_context;
Al Viro334e94d2006-03-18 15:05:53 -05001343 atomic_inc(&ioc_count);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001344 }
1345
1346 return cic;
1347}
1348
Jens Axboe22e2c502005-06-27 10:55:12 +02001349static void cfq_init_prio_data(struct cfq_queue *cfqq)
1350{
1351 struct task_struct *tsk = current;
1352 int ioprio_class;
1353
Jens Axboe3b181522005-06-27 10:56:24 +02001354 if (!cfq_cfqq_prio_changed(cfqq))
Jens Axboe22e2c502005-06-27 10:55:12 +02001355 return;
1356
1357 ioprio_class = IOPRIO_PRIO_CLASS(tsk->ioprio);
1358 switch (ioprio_class) {
1359 default:
1360 printk(KERN_ERR "cfq: bad prio %x\n", ioprio_class);
1361 case IOPRIO_CLASS_NONE:
1362 /*
1363 * no prio set, place us in the middle of the BE classes
1364 */
1365 cfqq->ioprio = task_nice_ioprio(tsk);
1366 cfqq->ioprio_class = IOPRIO_CLASS_BE;
1367 break;
1368 case IOPRIO_CLASS_RT:
1369 cfqq->ioprio = task_ioprio(tsk);
1370 cfqq->ioprio_class = IOPRIO_CLASS_RT;
1371 break;
1372 case IOPRIO_CLASS_BE:
1373 cfqq->ioprio = task_ioprio(tsk);
1374 cfqq->ioprio_class = IOPRIO_CLASS_BE;
1375 break;
1376 case IOPRIO_CLASS_IDLE:
1377 cfqq->ioprio_class = IOPRIO_CLASS_IDLE;
1378 cfqq->ioprio = 7;
Jens Axboe3b181522005-06-27 10:56:24 +02001379 cfq_clear_cfqq_idle_window(cfqq);
Jens Axboe22e2c502005-06-27 10:55:12 +02001380 break;
1381 }
1382
1383 /*
1384 * keep track of original prio settings in case we have to temporarily
1385 * elevate the priority of this queue
1386 */
1387 cfqq->org_ioprio = cfqq->ioprio;
1388 cfqq->org_ioprio_class = cfqq->ioprio_class;
1389
Jens Axboe3b181522005-06-27 10:56:24 +02001390 if (cfq_cfqq_on_rr(cfqq))
Jens Axboe22e2c502005-06-27 10:55:12 +02001391 cfq_resort_rr_list(cfqq, 0);
1392
Jens Axboe3b181522005-06-27 10:56:24 +02001393 cfq_clear_cfqq_prio_changed(cfqq);
Jens Axboe22e2c502005-06-27 10:55:12 +02001394}
1395
Al Viro478a82b2006-03-18 13:25:24 -05001396static inline void changed_ioprio(struct cfq_io_context *cic)
Jens Axboe22e2c502005-06-27 10:55:12 +02001397{
Al Viro478a82b2006-03-18 13:25:24 -05001398 struct cfq_data *cfqd = cic->key;
1399 struct cfq_queue *cfqq;
Jens Axboe35e60772006-06-14 09:10:45 +02001400
Jens Axboecaaa5f92006-06-16 11:23:00 +02001401 if (unlikely(!cfqd))
1402 return;
1403
1404 spin_lock(cfqd->queue->queue_lock);
1405
1406 cfqq = cic->cfqq[ASYNC];
1407 if (cfqq) {
1408 struct cfq_queue *new_cfqq;
1409 new_cfqq = cfq_get_queue(cfqd, CFQ_KEY_ASYNC, cic->ioc->task,
1410 GFP_ATOMIC);
1411 if (new_cfqq) {
1412 cic->cfqq[ASYNC] = new_cfqq;
1413 cfq_put_queue(cfqq);
1414 }
Jens Axboe22e2c502005-06-27 10:55:12 +02001415 }
Jens Axboecaaa5f92006-06-16 11:23:00 +02001416
1417 cfqq = cic->cfqq[SYNC];
1418 if (cfqq)
1419 cfq_mark_cfqq_prio_changed(cfqq);
1420
1421 spin_unlock(cfqd->queue->queue_lock);
Jens Axboe22e2c502005-06-27 10:55:12 +02001422}
1423
Linus Torvalds1da177e2005-04-16 15:20:36 -07001424/*
Jens Axboe22e2c502005-06-27 10:55:12 +02001425 * callback from sys_ioprio_set, irqs are disabled
Linus Torvalds1da177e2005-04-16 15:20:36 -07001426 */
Jens Axboe22e2c502005-06-27 10:55:12 +02001427static int cfq_ioc_set_ioprio(struct io_context *ioc, unsigned int ioprio)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001428{
Al Viroa6a07632006-03-18 13:26:44 -05001429 struct cfq_io_context *cic;
Jens Axboee2d74ac2006-03-28 08:59:01 +02001430 struct rb_node *n;
Al Viroa6a07632006-03-18 13:26:44 -05001431
Jens Axboe3793c652006-05-30 21:11:04 +02001432 spin_lock(&cfq_exit_lock);
Al Viroa6a07632006-03-18 13:26:44 -05001433
Jens Axboee2d74ac2006-03-28 08:59:01 +02001434 n = rb_first(&ioc->cic_root);
1435 while (n != NULL) {
1436 cic = rb_entry(n, struct cfq_io_context, rb_node);
Jens Axboe3793c652006-05-30 21:11:04 +02001437
Al Viro478a82b2006-03-18 13:25:24 -05001438 changed_ioprio(cic);
Jens Axboee2d74ac2006-03-28 08:59:01 +02001439 n = rb_next(n);
1440 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07001441
Jens Axboe3793c652006-05-30 21:11:04 +02001442 spin_unlock(&cfq_exit_lock);
Al Viroa6a07632006-03-18 13:26:44 -05001443
Jens Axboe22e2c502005-06-27 10:55:12 +02001444 return 0;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001445}
1446
1447static struct cfq_queue *
Al Viro6f325a12006-03-18 14:58:37 -05001448cfq_get_queue(struct cfq_data *cfqd, unsigned int key, struct task_struct *tsk,
Al Viro8267e262005-10-21 03:20:53 -04001449 gfp_t gfp_mask)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001450{
1451 const int hashval = hash_long(key, CFQ_QHASH_SHIFT);
1452 struct cfq_queue *cfqq, *new_cfqq = NULL;
Al Viro6f325a12006-03-18 14:58:37 -05001453 unsigned short ioprio;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001454
1455retry:
Al Viro6f325a12006-03-18 14:58:37 -05001456 ioprio = tsk->ioprio;
Jens Axboe3b181522005-06-27 10:56:24 +02001457 cfqq = __cfq_find_cfq_hash(cfqd, key, ioprio, hashval);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001458
1459 if (!cfqq) {
1460 if (new_cfqq) {
1461 cfqq = new_cfqq;
1462 new_cfqq = NULL;
Jens Axboe22e2c502005-06-27 10:55:12 +02001463 } else if (gfp_mask & __GFP_WAIT) {
Linus Torvalds1da177e2005-04-16 15:20:36 -07001464 spin_unlock_irq(cfqd->queue->queue_lock);
1465 new_cfqq = kmem_cache_alloc(cfq_pool, gfp_mask);
1466 spin_lock_irq(cfqd->queue->queue_lock);
1467 goto retry;
Jens Axboe22e2c502005-06-27 10:55:12 +02001468 } else {
1469 cfqq = kmem_cache_alloc(cfq_pool, gfp_mask);
1470 if (!cfqq)
1471 goto out;
Kiyoshi Ueda db3b5842005-06-17 16:15:10 +02001472 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07001473
1474 memset(cfqq, 0, sizeof(*cfqq));
1475
1476 INIT_HLIST_NODE(&cfqq->cfq_hash);
1477 INIT_LIST_HEAD(&cfqq->cfq_list);
Jens Axboe22e2c502005-06-27 10:55:12 +02001478 INIT_LIST_HEAD(&cfqq->fifo);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001479
1480 cfqq->key = key;
1481 hlist_add_head(&cfqq->cfq_hash, &cfqd->cfq_hash[hashval]);
1482 atomic_set(&cfqq->ref, 0);
1483 cfqq->cfqd = cfqd;
Jens Axboe22e2c502005-06-27 10:55:12 +02001484 cfqq->service_last = 0;
1485 /*
1486 * set ->slice_left to allow preemption for a new process
1487 */
1488 cfqq->slice_left = 2 * cfqd->cfq_slice_idle;
Jens Axboecaaa5f92006-06-16 11:23:00 +02001489 cfq_mark_cfqq_idle_window(cfqq);
Jens Axboe3b181522005-06-27 10:56:24 +02001490 cfq_mark_cfqq_prio_changed(cfqq);
1491 cfq_init_prio_data(cfqq);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001492 }
1493
1494 if (new_cfqq)
1495 kmem_cache_free(cfq_pool, new_cfqq);
1496
1497 atomic_inc(&cfqq->ref);
1498out:
1499 WARN_ON((gfp_mask & __GFP_WAIT) && !cfqq);
1500 return cfqq;
1501}
1502
OGAWA Hirofumidbecf3a2006-04-18 09:45:18 +02001503static void
1504cfq_drop_dead_cic(struct io_context *ioc, struct cfq_io_context *cic)
1505{
Jens Axboe3793c652006-05-30 21:11:04 +02001506 spin_lock(&cfq_exit_lock);
OGAWA Hirofumidbecf3a2006-04-18 09:45:18 +02001507 rb_erase(&cic->rb_node, &ioc->cic_root);
Jens Axboe3793c652006-05-30 21:11:04 +02001508 list_del_init(&cic->queue_list);
1509 spin_unlock(&cfq_exit_lock);
OGAWA Hirofumidbecf3a2006-04-18 09:45:18 +02001510 kmem_cache_free(cfq_ioc_pool, cic);
1511 atomic_dec(&ioc_count);
1512}
1513
Jens Axboee2d74ac2006-03-28 08:59:01 +02001514static struct cfq_io_context *
1515cfq_cic_rb_lookup(struct cfq_data *cfqd, struct io_context *ioc)
1516{
OGAWA Hirofumidbecf3a2006-04-18 09:45:18 +02001517 struct rb_node *n;
Jens Axboee2d74ac2006-03-28 08:59:01 +02001518 struct cfq_io_context *cic;
OGAWA Hirofumibe3b0752006-04-18 19:18:31 +02001519 void *k, *key = cfqd;
Jens Axboee2d74ac2006-03-28 08:59:01 +02001520
OGAWA Hirofumidbecf3a2006-04-18 09:45:18 +02001521restart:
1522 n = ioc->cic_root.rb_node;
Jens Axboee2d74ac2006-03-28 08:59:01 +02001523 while (n) {
1524 cic = rb_entry(n, struct cfq_io_context, rb_node);
OGAWA Hirofumibe3b0752006-04-18 19:18:31 +02001525 /* ->key must be copied to avoid race with cfq_exit_queue() */
1526 k = cic->key;
1527 if (unlikely(!k)) {
OGAWA Hirofumidbecf3a2006-04-18 09:45:18 +02001528 cfq_drop_dead_cic(ioc, cic);
1529 goto restart;
1530 }
Jens Axboee2d74ac2006-03-28 08:59:01 +02001531
OGAWA Hirofumibe3b0752006-04-18 19:18:31 +02001532 if (key < k)
Jens Axboee2d74ac2006-03-28 08:59:01 +02001533 n = n->rb_left;
OGAWA Hirofumibe3b0752006-04-18 19:18:31 +02001534 else if (key > k)
Jens Axboee2d74ac2006-03-28 08:59:01 +02001535 n = n->rb_right;
1536 else
1537 return cic;
1538 }
1539
1540 return NULL;
1541}
1542
1543static inline void
1544cfq_cic_link(struct cfq_data *cfqd, struct io_context *ioc,
1545 struct cfq_io_context *cic)
1546{
OGAWA Hirofumidbecf3a2006-04-18 09:45:18 +02001547 struct rb_node **p;
1548 struct rb_node *parent;
Jens Axboee2d74ac2006-03-28 08:59:01 +02001549 struct cfq_io_context *__cic;
OGAWA Hirofumibe3b0752006-04-18 19:18:31 +02001550 void *k;
Jens Axboee2d74ac2006-03-28 08:59:01 +02001551
Jens Axboee2d74ac2006-03-28 08:59:01 +02001552 cic->ioc = ioc;
1553 cic->key = cfqd;
1554
1555 ioc->set_ioprio = cfq_ioc_set_ioprio;
OGAWA Hirofumidbecf3a2006-04-18 09:45:18 +02001556restart:
1557 parent = NULL;
1558 p = &ioc->cic_root.rb_node;
Jens Axboee2d74ac2006-03-28 08:59:01 +02001559 while (*p) {
1560 parent = *p;
1561 __cic = rb_entry(parent, struct cfq_io_context, rb_node);
OGAWA Hirofumibe3b0752006-04-18 19:18:31 +02001562 /* ->key must be copied to avoid race with cfq_exit_queue() */
1563 k = __cic->key;
1564 if (unlikely(!k)) {
OGAWA Hirofumidbecf3a2006-04-18 09:45:18 +02001565 cfq_drop_dead_cic(ioc, cic);
1566 goto restart;
1567 }
Jens Axboee2d74ac2006-03-28 08:59:01 +02001568
OGAWA Hirofumibe3b0752006-04-18 19:18:31 +02001569 if (cic->key < k)
Jens Axboee2d74ac2006-03-28 08:59:01 +02001570 p = &(*p)->rb_left;
OGAWA Hirofumibe3b0752006-04-18 19:18:31 +02001571 else if (cic->key > k)
Jens Axboee2d74ac2006-03-28 08:59:01 +02001572 p = &(*p)->rb_right;
1573 else
1574 BUG();
1575 }
1576
Jens Axboe3793c652006-05-30 21:11:04 +02001577 spin_lock(&cfq_exit_lock);
Jens Axboee2d74ac2006-03-28 08:59:01 +02001578 rb_link_node(&cic->rb_node, parent, p);
1579 rb_insert_color(&cic->rb_node, &ioc->cic_root);
1580 list_add(&cic->queue_list, &cfqd->cic_list);
Jens Axboe3793c652006-05-30 21:11:04 +02001581 spin_unlock(&cfq_exit_lock);
Jens Axboee2d74ac2006-03-28 08:59:01 +02001582}
1583
Jens Axboe22e2c502005-06-27 10:55:12 +02001584/*
1585 * Setup general io context and cfq io context. There can be several cfq
1586 * io contexts per general io context, if this process is doing io to more
Jens Axboee2d74ac2006-03-28 08:59:01 +02001587 * than one device managed by cfq.
Jens Axboe22e2c502005-06-27 10:55:12 +02001588 */
1589static struct cfq_io_context *
Jens Axboee2d74ac2006-03-28 08:59:01 +02001590cfq_get_io_context(struct cfq_data *cfqd, gfp_t gfp_mask)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001591{
Jens Axboe22e2c502005-06-27 10:55:12 +02001592 struct io_context *ioc = NULL;
1593 struct cfq_io_context *cic;
1594
1595 might_sleep_if(gfp_mask & __GFP_WAIT);
1596
1597 ioc = get_io_context(gfp_mask);
1598 if (!ioc)
1599 return NULL;
1600
Jens Axboee2d74ac2006-03-28 08:59:01 +02001601 cic = cfq_cic_rb_lookup(cfqd, ioc);
1602 if (cic)
1603 goto out;
Jens Axboe22e2c502005-06-27 10:55:12 +02001604
Jens Axboee2d74ac2006-03-28 08:59:01 +02001605 cic = cfq_alloc_io_context(cfqd, gfp_mask);
1606 if (cic == NULL)
1607 goto err;
Jens Axboe22e2c502005-06-27 10:55:12 +02001608
Jens Axboee2d74ac2006-03-28 08:59:01 +02001609 cfq_cic_link(cfqd, ioc, cic);
Jens Axboe22e2c502005-06-27 10:55:12 +02001610out:
1611 return cic;
1612err:
1613 put_io_context(ioc);
1614 return NULL;
1615}
1616
1617static void
1618cfq_update_io_thinktime(struct cfq_data *cfqd, struct cfq_io_context *cic)
1619{
1620 unsigned long elapsed, ttime;
1621
1622 /*
1623 * if this context already has stuff queued, thinktime is from
1624 * last queue not last end
1625 */
1626#if 0
1627 if (time_after(cic->last_end_request, cic->last_queue))
1628 elapsed = jiffies - cic->last_end_request;
1629 else
1630 elapsed = jiffies - cic->last_queue;
1631#else
1632 elapsed = jiffies - cic->last_end_request;
1633#endif
1634
1635 ttime = min(elapsed, 2UL * cfqd->cfq_slice_idle);
1636
1637 cic->ttime_samples = (7*cic->ttime_samples + 256) / 8;
1638 cic->ttime_total = (7*cic->ttime_total + 256*ttime) / 8;
1639 cic->ttime_mean = (cic->ttime_total + 128) / cic->ttime_samples;
1640}
1641
Jens Axboe206dc692006-03-28 13:03:44 +02001642static void
1643cfq_update_io_seektime(struct cfq_data *cfqd, struct cfq_io_context *cic,
1644 struct cfq_rq *crq)
1645{
1646 sector_t sdist;
1647 u64 total;
1648
1649 if (cic->last_request_pos < crq->request->sector)
1650 sdist = crq->request->sector - cic->last_request_pos;
1651 else
1652 sdist = cic->last_request_pos - crq->request->sector;
1653
1654 /*
1655 * Don't allow the seek distance to get too large from the
1656 * odd fragment, pagein, etc
1657 */
1658 if (cic->seek_samples <= 60) /* second&third seek */
1659 sdist = min(sdist, (cic->seek_mean * 4) + 2*1024*1024);
1660 else
1661 sdist = min(sdist, (cic->seek_mean * 4) + 2*1024*64);
1662
1663 cic->seek_samples = (7*cic->seek_samples + 256) / 8;
1664 cic->seek_total = (7*cic->seek_total + (u64)256*sdist) / 8;
1665 total = cic->seek_total + (cic->seek_samples/2);
1666 do_div(total, cic->seek_samples);
1667 cic->seek_mean = (sector_t)total;
1668}
Jens Axboe22e2c502005-06-27 10:55:12 +02001669
1670/*
1671 * Disable idle window if the process thinks too long or seeks so much that
1672 * it doesn't matter
1673 */
1674static void
1675cfq_update_idle_window(struct cfq_data *cfqd, struct cfq_queue *cfqq,
1676 struct cfq_io_context *cic)
1677{
Jens Axboe3b181522005-06-27 10:56:24 +02001678 int enable_idle = cfq_cfqq_idle_window(cfqq);
Jens Axboe22e2c502005-06-27 10:55:12 +02001679
Jens Axboecaaa5f92006-06-16 11:23:00 +02001680 if (!cic->ioc->task || !cfqd->cfq_slice_idle ||
1681 (cfqd->hw_tag && CIC_SEEKY(cic)))
Jens Axboe22e2c502005-06-27 10:55:12 +02001682 enable_idle = 0;
1683 else if (sample_valid(cic->ttime_samples)) {
1684 if (cic->ttime_mean > cfqd->cfq_slice_idle)
1685 enable_idle = 0;
1686 else
1687 enable_idle = 1;
1688 }
1689
Jens Axboe3b181522005-06-27 10:56:24 +02001690 if (enable_idle)
1691 cfq_mark_cfqq_idle_window(cfqq);
1692 else
1693 cfq_clear_cfqq_idle_window(cfqq);
Jens Axboe22e2c502005-06-27 10:55:12 +02001694}
1695
1696
1697/*
1698 * Check if new_cfqq should preempt the currently active queue. Return 0 for
1699 * no or if we aren't sure, a 1 will cause a preempt.
1700 */
1701static int
1702cfq_should_preempt(struct cfq_data *cfqd, struct cfq_queue *new_cfqq,
1703 struct cfq_rq *crq)
1704{
1705 struct cfq_queue *cfqq = cfqd->active_queue;
1706
1707 if (cfq_class_idle(new_cfqq))
1708 return 0;
1709
1710 if (!cfqq)
Jens Axboecaaa5f92006-06-16 11:23:00 +02001711 return 0;
Jens Axboe22e2c502005-06-27 10:55:12 +02001712
1713 if (cfq_class_idle(cfqq))
1714 return 1;
Jens Axboe3b181522005-06-27 10:56:24 +02001715 if (!cfq_cfqq_wait_request(new_cfqq))
Jens Axboe22e2c502005-06-27 10:55:12 +02001716 return 0;
1717 /*
1718 * if it doesn't have slice left, forget it
1719 */
1720 if (new_cfqq->slice_left < cfqd->cfq_slice_idle)
1721 return 0;
Jens Axboe3b181522005-06-27 10:56:24 +02001722 if (cfq_crq_is_sync(crq) && !cfq_cfqq_sync(cfqq))
Jens Axboe22e2c502005-06-27 10:55:12 +02001723 return 1;
1724
1725 return 0;
1726}
1727
1728/*
1729 * cfqq preempts the active queue. if we allowed preempt with no slice left,
1730 * let it have half of its nominal slice.
1731 */
1732static void cfq_preempt_queue(struct cfq_data *cfqd, struct cfq_queue *cfqq)
1733{
1734 struct cfq_queue *__cfqq, *next;
1735
1736 list_for_each_entry_safe(__cfqq, next, &cfqd->cur_rr, cfq_list)
1737 cfq_resort_rr_list(__cfqq, 1);
1738
1739 if (!cfqq->slice_left)
1740 cfqq->slice_left = cfq_prio_to_slice(cfqd, cfqq) / 2;
1741
1742 cfqq->slice_end = cfqq->slice_left + jiffies;
Jens Axboecaaa5f92006-06-16 11:23:00 +02001743 cfq_slice_expired(cfqd, 1);
Jens Axboe22e2c502005-06-27 10:55:12 +02001744 __cfq_set_active_queue(cfqd, cfqq);
1745}
1746
1747/*
1748 * should really be a ll_rw_blk.c helper
1749 */
1750static void cfq_start_queueing(struct cfq_data *cfqd, struct cfq_queue *cfqq)
1751{
1752 request_queue_t *q = cfqd->queue;
1753
1754 if (!blk_queue_plugged(q))
1755 q->request_fn(q);
1756 else
1757 __generic_unplug_device(q);
1758}
1759
1760/*
1761 * Called when a new fs request (crq) is added (to cfqq). Check if there's
1762 * something we should do about it
1763 */
1764static void
1765cfq_crq_enqueued(struct cfq_data *cfqd, struct cfq_queue *cfqq,
1766 struct cfq_rq *crq)
1767{
Jens Axboefd61af02006-06-16 15:35:39 +02001768 struct cfq_io_context *cic = crq->io_context;
Jens Axboe12e9fdd2006-06-01 10:09:56 +02001769
Jens Axboe9c2c38a2005-08-24 14:57:54 +02001770 /*
1771 * we never wait for an async request and we don't allow preemption
1772 * of an async request. so just return early
1773 */
Jens Axboe12e9fdd2006-06-01 10:09:56 +02001774 if (!cfq_crq_is_sync(crq)) {
1775 /*
1776 * sync process issued an async request, if it's waiting
1777 * then expire it and kick rq handling.
1778 */
1779 if (cic == cfqd->active_cic &&
1780 del_timer(&cfqd->idle_slice_timer)) {
1781 cfq_slice_expired(cfqd, 0);
1782 cfq_start_queueing(cfqd, cfqq);
1783 }
Jens Axboe9c2c38a2005-08-24 14:57:54 +02001784 return;
Jens Axboe12e9fdd2006-06-01 10:09:56 +02001785 }
Jens Axboe22e2c502005-06-27 10:55:12 +02001786
Jens Axboe9c2c38a2005-08-24 14:57:54 +02001787 cfq_update_io_thinktime(cfqd, cic);
Jens Axboe206dc692006-03-28 13:03:44 +02001788 cfq_update_io_seektime(cfqd, cic, crq);
Jens Axboe9c2c38a2005-08-24 14:57:54 +02001789 cfq_update_idle_window(cfqd, cfqq, cic);
1790
1791 cic->last_queue = jiffies;
Jens Axboe206dc692006-03-28 13:03:44 +02001792 cic->last_request_pos = crq->request->sector + crq->request->nr_sectors;
Jens Axboe22e2c502005-06-27 10:55:12 +02001793
1794 if (cfqq == cfqd->active_queue) {
1795 /*
1796 * if we are waiting for a request for this queue, let it rip
1797 * immediately and flag that we must not expire this queue
1798 * just now
1799 */
Jens Axboe3b181522005-06-27 10:56:24 +02001800 if (cfq_cfqq_wait_request(cfqq)) {
1801 cfq_mark_cfqq_must_dispatch(cfqq);
Jens Axboe22e2c502005-06-27 10:55:12 +02001802 del_timer(&cfqd->idle_slice_timer);
1803 cfq_start_queueing(cfqd, cfqq);
1804 }
1805 } else if (cfq_should_preempt(cfqd, cfqq, crq)) {
1806 /*
1807 * not the active queue - expire current slice if it is
1808 * idle and has expired it's mean thinktime or this new queue
1809 * has some old slice time left and is of higher priority
1810 */
1811 cfq_preempt_queue(cfqd, cfqq);
Jens Axboe3b181522005-06-27 10:56:24 +02001812 cfq_mark_cfqq_must_dispatch(cfqq);
Jens Axboe22e2c502005-06-27 10:55:12 +02001813 cfq_start_queueing(cfqd, cfqq);
1814 }
1815}
1816
Jens Axboeb4878f22005-10-20 16:42:29 +02001817static void cfq_insert_request(request_queue_t *q, struct request *rq)
Jens Axboe22e2c502005-06-27 10:55:12 +02001818{
Jens Axboeb4878f22005-10-20 16:42:29 +02001819 struct cfq_data *cfqd = q->elevator->elevator_data;
Jens Axboe22e2c502005-06-27 10:55:12 +02001820 struct cfq_rq *crq = RQ_DATA(rq);
1821 struct cfq_queue *cfqq = crq->cfq_queue;
1822
1823 cfq_init_prio_data(cfqq);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001824
1825 cfq_add_crq_rb(crq);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001826
Jens Axboe22e2c502005-06-27 10:55:12 +02001827 list_add_tail(&rq->queuelist, &cfqq->fifo);
1828
Tejun Heo98b11472005-10-20 16:46:54 +02001829 if (rq_mergeable(rq))
Jens Axboe22e2c502005-06-27 10:55:12 +02001830 cfq_add_crq_hash(cfqd, crq);
1831
Jens Axboe22e2c502005-06-27 10:55:12 +02001832 cfq_crq_enqueued(cfqd, cfqq, crq);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001833}
1834
Linus Torvalds1da177e2005-04-16 15:20:36 -07001835static void cfq_completed_request(request_queue_t *q, struct request *rq)
1836{
1837 struct cfq_rq *crq = RQ_DATA(rq);
Jens Axboeb4878f22005-10-20 16:42:29 +02001838 struct cfq_queue *cfqq = crq->cfq_queue;
1839 struct cfq_data *cfqd = cfqq->cfqd;
1840 const int sync = cfq_crq_is_sync(crq);
1841 unsigned long now;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001842
Jens Axboeb4878f22005-10-20 16:42:29 +02001843 now = jiffies;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001844
Jens Axboeb4878f22005-10-20 16:42:29 +02001845 WARN_ON(!cfqd->rq_in_driver);
1846 WARN_ON(!cfqq->on_dispatch[sync]);
1847 cfqd->rq_in_driver--;
1848 cfqq->on_dispatch[sync]--;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001849
Jens Axboeb4878f22005-10-20 16:42:29 +02001850 if (!cfq_class_idle(cfqq))
1851 cfqd->last_end_request = now;
Jens Axboe3b181522005-06-27 10:56:24 +02001852
Jens Axboeb4878f22005-10-20 16:42:29 +02001853 if (!cfq_cfqq_dispatched(cfqq)) {
1854 if (cfq_cfqq_on_rr(cfqq)) {
1855 cfqq->service_last = now;
1856 cfq_resort_rr_list(cfqq, 0);
1857 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07001858 }
1859
Jens Axboecaaa5f92006-06-16 11:23:00 +02001860 if (sync)
Jens Axboeb4878f22005-10-20 16:42:29 +02001861 crq->io_context->last_end_request = now;
Jens Axboecaaa5f92006-06-16 11:23:00 +02001862
1863 /*
1864 * If this is the active queue, check if it needs to be expired,
1865 * or if we want to idle in case it has no pending requests.
1866 */
1867 if (cfqd->active_queue == cfqq) {
1868 if (time_after(now, cfqq->slice_end))
1869 cfq_slice_expired(cfqd, 0);
Jens Axboedd67d052006-06-21 09:36:18 +02001870 else if (sync && RB_EMPTY_ROOT(&cfqq->sort_list)) {
Jens Axboecaaa5f92006-06-16 11:23:00 +02001871 if (!cfq_arm_slice_timer(cfqd, cfqq))
1872 cfq_schedule_dispatch(cfqd);
1873 }
1874 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07001875}
1876
1877static struct request *
1878cfq_former_request(request_queue_t *q, struct request *rq)
1879{
1880 struct cfq_rq *crq = RQ_DATA(rq);
1881 struct rb_node *rbprev = rb_prev(&crq->rb_node);
1882
1883 if (rbprev)
1884 return rb_entry_crq(rbprev)->request;
1885
1886 return NULL;
1887}
1888
1889static struct request *
1890cfq_latter_request(request_queue_t *q, struct request *rq)
1891{
1892 struct cfq_rq *crq = RQ_DATA(rq);
1893 struct rb_node *rbnext = rb_next(&crq->rb_node);
1894
1895 if (rbnext)
1896 return rb_entry_crq(rbnext)->request;
1897
1898 return NULL;
1899}
1900
Jens Axboe22e2c502005-06-27 10:55:12 +02001901/*
1902 * we temporarily boost lower priority queues if they are holding fs exclusive
1903 * resources. they are boosted to normal prio (CLASS_BE/4)
1904 */
1905static void cfq_prio_boost(struct cfq_queue *cfqq)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001906{
Jens Axboe22e2c502005-06-27 10:55:12 +02001907 const int ioprio_class = cfqq->ioprio_class;
1908 const int ioprio = cfqq->ioprio;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001909
Jens Axboe22e2c502005-06-27 10:55:12 +02001910 if (has_fs_excl()) {
1911 /*
1912 * boost idle prio on transactions that would lock out other
1913 * users of the filesystem
1914 */
1915 if (cfq_class_idle(cfqq))
1916 cfqq->ioprio_class = IOPRIO_CLASS_BE;
1917 if (cfqq->ioprio > IOPRIO_NORM)
1918 cfqq->ioprio = IOPRIO_NORM;
1919 } else {
1920 /*
1921 * check if we need to unboost the queue
1922 */
1923 if (cfqq->ioprio_class != cfqq->org_ioprio_class)
1924 cfqq->ioprio_class = cfqq->org_ioprio_class;
1925 if (cfqq->ioprio != cfqq->org_ioprio)
1926 cfqq->ioprio = cfqq->org_ioprio;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001927 }
1928
Jens Axboe22e2c502005-06-27 10:55:12 +02001929 /*
1930 * refile between round-robin lists if we moved the priority class
1931 */
1932 if ((ioprio_class != cfqq->ioprio_class || ioprio != cfqq->ioprio) &&
Jens Axboe3b181522005-06-27 10:56:24 +02001933 cfq_cfqq_on_rr(cfqq))
Jens Axboe22e2c502005-06-27 10:55:12 +02001934 cfq_resort_rr_list(cfqq, 0);
1935}
1936
Jens Axboe22e2c502005-06-27 10:55:12 +02001937static inline int
1938__cfq_may_queue(struct cfq_data *cfqd, struct cfq_queue *cfqq,
1939 struct task_struct *task, int rw)
1940{
Jens Axboe3b181522005-06-27 10:56:24 +02001941 if ((cfq_cfqq_wait_request(cfqq) || cfq_cfqq_must_alloc(cfqq)) &&
Andrew Morton99f95e52005-06-27 20:14:05 -07001942 !cfq_cfqq_must_alloc_slice(cfqq)) {
Jens Axboe3b181522005-06-27 10:56:24 +02001943 cfq_mark_cfqq_must_alloc_slice(cfqq);
Jens Axboe22e2c502005-06-27 10:55:12 +02001944 return ELV_MQUEUE_MUST;
Jens Axboe3b181522005-06-27 10:56:24 +02001945 }
Jens Axboe22e2c502005-06-27 10:55:12 +02001946
1947 return ELV_MQUEUE_MAY;
Jens Axboe22e2c502005-06-27 10:55:12 +02001948}
1949
1950static int cfq_may_queue(request_queue_t *q, int rw, struct bio *bio)
1951{
1952 struct cfq_data *cfqd = q->elevator->elevator_data;
1953 struct task_struct *tsk = current;
1954 struct cfq_queue *cfqq;
1955
1956 /*
1957 * don't force setup of a queue from here, as a call to may_queue
1958 * does not necessarily imply that a request actually will be queued.
1959 * so just lookup a possibly existing queue, or return 'may queue'
1960 * if that fails
1961 */
Jens Axboe3b181522005-06-27 10:56:24 +02001962 cfqq = cfq_find_cfq_hash(cfqd, cfq_queue_pid(tsk, rw), tsk->ioprio);
Jens Axboe22e2c502005-06-27 10:55:12 +02001963 if (cfqq) {
1964 cfq_init_prio_data(cfqq);
1965 cfq_prio_boost(cfqq);
1966
1967 return __cfq_may_queue(cfqd, cfqq, tsk, rw);
1968 }
1969
1970 return ELV_MQUEUE_MAY;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001971}
1972
1973static void cfq_check_waiters(request_queue_t *q, struct cfq_queue *cfqq)
1974{
Jens Axboe22e2c502005-06-27 10:55:12 +02001975 struct cfq_data *cfqd = q->elevator->elevator_data;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001976
Jens Axboe271f18f2006-06-13 08:08:38 +02001977 if (unlikely(cfqd->rq_starved)) {
1978 struct request_list *rl = &q->rq;
1979
Jens Axboe22e2c502005-06-27 10:55:12 +02001980 smp_mb();
1981 if (waitqueue_active(&rl->wait[READ]))
1982 wake_up(&rl->wait[READ]);
Jens Axboe22e2c502005-06-27 10:55:12 +02001983 if (waitqueue_active(&rl->wait[WRITE]))
1984 wake_up(&rl->wait[WRITE]);
1985 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07001986}
1987
1988/*
1989 * queue lock held here
1990 */
1991static void cfq_put_request(request_queue_t *q, struct request *rq)
1992{
1993 struct cfq_data *cfqd = q->elevator->elevator_data;
1994 struct cfq_rq *crq = RQ_DATA(rq);
1995
1996 if (crq) {
1997 struct cfq_queue *cfqq = crq->cfq_queue;
Jens Axboe22e2c502005-06-27 10:55:12 +02001998 const int rw = rq_data_dir(rq);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001999
Jens Axboe22e2c502005-06-27 10:55:12 +02002000 BUG_ON(!cfqq->allocated[rw]);
2001 cfqq->allocated[rw]--;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002002
Jens Axboe22e2c502005-06-27 10:55:12 +02002003 put_io_context(crq->io_context->ioc);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002004
2005 mempool_free(crq, cfqd->crq_pool);
2006 rq->elevator_private = NULL;
2007
Linus Torvalds1da177e2005-04-16 15:20:36 -07002008 cfq_check_waiters(q, cfqq);
2009 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
2017cfq_set_request(request_queue_t *q, struct request *rq, struct bio *bio,
Al Viro8267e262005-10-21 03:20:53 -04002018 gfp_t gfp_mask)
Linus Torvalds1da177e2005-04-16 15:20:36 -07002019{
2020 struct cfq_data *cfqd = q->elevator->elevator_data;
Jens Axboe3b181522005-06-27 10:56:24 +02002021 struct task_struct *tsk = current;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002022 struct cfq_io_context *cic;
2023 const int rw = rq_data_dir(rq);
Jens Axboe3b181522005-06-27 10:56:24 +02002024 pid_t key = cfq_queue_pid(tsk, rw);
Jens Axboe22e2c502005-06-27 10:55:12 +02002025 struct cfq_queue *cfqq;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002026 struct cfq_rq *crq;
2027 unsigned long flags;
Al Viro12a05732006-03-18 13:38:01 -05002028 int is_sync = key != CFQ_KEY_ASYNC;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002029
2030 might_sleep_if(gfp_mask & __GFP_WAIT);
2031
Jens Axboee2d74ac2006-03-28 08:59:01 +02002032 cic = cfq_get_io_context(cfqd, gfp_mask);
Jens Axboe22e2c502005-06-27 10:55:12 +02002033
Linus Torvalds1da177e2005-04-16 15:20:36 -07002034 spin_lock_irqsave(q->queue_lock, flags);
2035
Jens Axboe22e2c502005-06-27 10:55:12 +02002036 if (!cic)
2037 goto queue_fail;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002038
Al Viro12a05732006-03-18 13:38:01 -05002039 if (!cic->cfqq[is_sync]) {
Al Viro6f325a12006-03-18 14:58:37 -05002040 cfqq = cfq_get_queue(cfqd, key, tsk, gfp_mask);
Jens Axboe22e2c502005-06-27 10:55:12 +02002041 if (!cfqq)
2042 goto queue_fail;
2043
Al Viro12a05732006-03-18 13:38:01 -05002044 cic->cfqq[is_sync] = cfqq;
Jens Axboe22e2c502005-06-27 10:55:12 +02002045 } else
Al Viro12a05732006-03-18 13:38:01 -05002046 cfqq = cic->cfqq[is_sync];
Linus Torvalds1da177e2005-04-16 15:20:36 -07002047
2048 cfqq->allocated[rw]++;
Jens Axboe3b181522005-06-27 10:56:24 +02002049 cfq_clear_cfqq_must_alloc(cfqq);
Jens Axboe22e2c502005-06-27 10:55:12 +02002050 cfqd->rq_starved = 0;
2051 atomic_inc(&cfqq->ref);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002052 spin_unlock_irqrestore(q->queue_lock, flags);
2053
Linus Torvalds1da177e2005-04-16 15:20:36 -07002054 crq = mempool_alloc(cfqd->crq_pool, gfp_mask);
2055 if (crq) {
Jens Axboedd67d052006-06-21 09:36:18 +02002056 RB_CLEAR_NODE(&crq->rb_node);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002057 crq->rb_key = 0;
2058 crq->request = rq;
2059 INIT_HLIST_NODE(&crq->hash);
2060 crq->cfq_queue = cfqq;
2061 crq->io_context = cic;
Jens Axboe3b181522005-06-27 10:56:24 +02002062
Al Viro12a05732006-03-18 13:38:01 -05002063 if (is_sync)
Jens Axboe3b181522005-06-27 10:56:24 +02002064 cfq_mark_crq_is_sync(crq);
2065 else
2066 cfq_clear_crq_is_sync(crq);
2067
Linus Torvalds1da177e2005-04-16 15:20:36 -07002068 rq->elevator_private = crq;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002069 return 0;
2070 }
2071
Linus Torvalds1da177e2005-04-16 15:20:36 -07002072 spin_lock_irqsave(q->queue_lock, flags);
2073 cfqq->allocated[rw]--;
Jens Axboe22e2c502005-06-27 10:55:12 +02002074 if (!(cfqq->allocated[0] + cfqq->allocated[1]))
Jens Axboe3b181522005-06-27 10:56:24 +02002075 cfq_mark_cfqq_must_alloc(cfqq);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002076 cfq_put_queue(cfqq);
Jens Axboe22e2c502005-06-27 10:55:12 +02002077queue_fail:
2078 if (cic)
2079 put_io_context(cic->ioc);
2080 /*
2081 * mark us rq allocation starved. we need to kickstart the process
2082 * ourselves if there are no pending requests that can do it for us.
2083 * that would be an extremely rare OOM situation
2084 */
2085 cfqd->rq_starved = 1;
Jens Axboe3b181522005-06-27 10:56:24 +02002086 cfq_schedule_dispatch(cfqd);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002087 spin_unlock_irqrestore(q->queue_lock, flags);
2088 return 1;
2089}
2090
Jens Axboe22e2c502005-06-27 10:55:12 +02002091static void cfq_kick_queue(void *data)
2092{
2093 request_queue_t *q = data;
2094 struct cfq_data *cfqd = q->elevator->elevator_data;
2095 unsigned long flags;
2096
2097 spin_lock_irqsave(q->queue_lock, flags);
2098
2099 if (cfqd->rq_starved) {
2100 struct request_list *rl = &q->rq;
2101
2102 /*
2103 * we aren't guaranteed to get a request after this, but we
2104 * have to be opportunistic
2105 */
2106 smp_mb();
2107 if (waitqueue_active(&rl->wait[READ]))
2108 wake_up(&rl->wait[READ]);
2109 if (waitqueue_active(&rl->wait[WRITE]))
2110 wake_up(&rl->wait[WRITE]);
2111 }
2112
2113 blk_remove_plug(q);
2114 q->request_fn(q);
2115 spin_unlock_irqrestore(q->queue_lock, flags);
2116}
2117
2118/*
2119 * Timer running if the active_queue is currently idling inside its time slice
2120 */
2121static void cfq_idle_slice_timer(unsigned long data)
2122{
2123 struct cfq_data *cfqd = (struct cfq_data *) data;
2124 struct cfq_queue *cfqq;
2125 unsigned long flags;
2126
2127 spin_lock_irqsave(cfqd->queue->queue_lock, flags);
2128
2129 if ((cfqq = cfqd->active_queue) != NULL) {
2130 unsigned long now = jiffies;
2131
2132 /*
2133 * expired
2134 */
2135 if (time_after(now, cfqq->slice_end))
2136 goto expire;
2137
2138 /*
2139 * only expire and reinvoke request handler, if there are
2140 * other queues with pending requests
2141 */
Jens Axboecaaa5f92006-06-16 11:23:00 +02002142 if (!cfqd->busy_queues)
Jens Axboe22e2c502005-06-27 10:55:12 +02002143 goto out_cont;
Jens Axboe22e2c502005-06-27 10:55:12 +02002144
2145 /*
2146 * not expired and it has a request pending, let it dispatch
2147 */
Jens Axboedd67d052006-06-21 09:36:18 +02002148 if (!RB_EMPTY_ROOT(&cfqq->sort_list)) {
Jens Axboe3b181522005-06-27 10:56:24 +02002149 cfq_mark_cfqq_must_dispatch(cfqq);
Jens Axboe22e2c502005-06-27 10:55:12 +02002150 goto out_kick;
2151 }
2152 }
2153expire:
2154 cfq_slice_expired(cfqd, 0);
2155out_kick:
Jens Axboe3b181522005-06-27 10:56:24 +02002156 cfq_schedule_dispatch(cfqd);
Jens Axboe22e2c502005-06-27 10:55:12 +02002157out_cont:
2158 spin_unlock_irqrestore(cfqd->queue->queue_lock, flags);
2159}
2160
2161/*
2162 * Timer running if an idle class queue is waiting for service
2163 */
2164static void cfq_idle_class_timer(unsigned long data)
2165{
2166 struct cfq_data *cfqd = (struct cfq_data *) data;
2167 unsigned long flags, end;
2168
2169 spin_lock_irqsave(cfqd->queue->queue_lock, flags);
2170
2171 /*
2172 * race with a non-idle queue, reset timer
2173 */
2174 end = cfqd->last_end_request + CFQ_IDLE_GRACE;
Jens Axboeae818a32006-06-01 10:13:43 +02002175 if (!time_after_eq(jiffies, end))
2176 mod_timer(&cfqd->idle_class_timer, end);
2177 else
Jens Axboe3b181522005-06-27 10:56:24 +02002178 cfq_schedule_dispatch(cfqd);
Jens Axboe22e2c502005-06-27 10:55:12 +02002179
2180 spin_unlock_irqrestore(cfqd->queue->queue_lock, flags);
2181}
2182
Jens Axboe3b181522005-06-27 10:56:24 +02002183static void cfq_shutdown_timer_wq(struct cfq_data *cfqd)
2184{
2185 del_timer_sync(&cfqd->idle_slice_timer);
2186 del_timer_sync(&cfqd->idle_class_timer);
2187 blk_sync_queue(cfqd->queue);
2188}
Jens Axboe22e2c502005-06-27 10:55:12 +02002189
Linus Torvalds1da177e2005-04-16 15:20:36 -07002190static void cfq_exit_queue(elevator_t *e)
2191{
Jens Axboe22e2c502005-06-27 10:55:12 +02002192 struct cfq_data *cfqd = e->elevator_data;
Al Virod9ff4182006-03-18 13:51:22 -05002193 request_queue_t *q = cfqd->queue;
Jens Axboe22e2c502005-06-27 10:55:12 +02002194
Jens Axboe3b181522005-06-27 10:56:24 +02002195 cfq_shutdown_timer_wq(cfqd);
Jens Axboee2d74ac2006-03-28 08:59:01 +02002196
Jens Axboe3793c652006-05-30 21:11:04 +02002197 spin_lock(&cfq_exit_lock);
Al Virod9ff4182006-03-18 13:51:22 -05002198 spin_lock_irq(q->queue_lock);
Jens Axboee2d74ac2006-03-28 08:59:01 +02002199
Al Virod9ff4182006-03-18 13:51:22 -05002200 if (cfqd->active_queue)
2201 __cfq_slice_expired(cfqd, cfqd->active_queue, 0);
Jens Axboee2d74ac2006-03-28 08:59:01 +02002202
2203 while (!list_empty(&cfqd->cic_list)) {
Al Virod9ff4182006-03-18 13:51:22 -05002204 struct cfq_io_context *cic = list_entry(cfqd->cic_list.next,
2205 struct cfq_io_context,
2206 queue_list);
2207 if (cic->cfqq[ASYNC]) {
2208 cfq_put_queue(cic->cfqq[ASYNC]);
2209 cic->cfqq[ASYNC] = NULL;
2210 }
2211 if (cic->cfqq[SYNC]) {
2212 cfq_put_queue(cic->cfqq[SYNC]);
2213 cic->cfqq[SYNC] = NULL;
2214 }
2215 cic->key = NULL;
2216 list_del_init(&cic->queue_list);
2217 }
Jens Axboee2d74ac2006-03-28 08:59:01 +02002218
Al Virod9ff4182006-03-18 13:51:22 -05002219 spin_unlock_irq(q->queue_lock);
Jens Axboe3793c652006-05-30 21:11:04 +02002220 spin_unlock(&cfq_exit_lock);
Al Viroa90d7422006-03-18 12:05:37 -05002221
2222 cfq_shutdown_timer_wq(cfqd);
2223
2224 mempool_destroy(cfqd->crq_pool);
2225 kfree(cfqd->crq_hash);
2226 kfree(cfqd->cfq_hash);
2227 kfree(cfqd);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002228}
2229
Jens Axboebc1c1162006-06-08 08:49:06 +02002230static void *cfq_init_queue(request_queue_t *q, elevator_t *e)
Linus Torvalds1da177e2005-04-16 15:20:36 -07002231{
2232 struct cfq_data *cfqd;
2233 int i;
2234
2235 cfqd = kmalloc(sizeof(*cfqd), GFP_KERNEL);
2236 if (!cfqd)
Jens Axboebc1c1162006-06-08 08:49:06 +02002237 return NULL;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002238
2239 memset(cfqd, 0, sizeof(*cfqd));
Jens Axboe22e2c502005-06-27 10:55:12 +02002240
2241 for (i = 0; i < CFQ_PRIO_LISTS; i++)
2242 INIT_LIST_HEAD(&cfqd->rr_list[i]);
2243
2244 INIT_LIST_HEAD(&cfqd->busy_rr);
2245 INIT_LIST_HEAD(&cfqd->cur_rr);
2246 INIT_LIST_HEAD(&cfqd->idle_rr);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002247 INIT_LIST_HEAD(&cfqd->empty_list);
Al Virod9ff4182006-03-18 13:51:22 -05002248 INIT_LIST_HEAD(&cfqd->cic_list);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002249
2250 cfqd->crq_hash = kmalloc(sizeof(struct hlist_head) * CFQ_MHASH_ENTRIES, GFP_KERNEL);
2251 if (!cfqd->crq_hash)
2252 goto out_crqhash;
2253
2254 cfqd->cfq_hash = kmalloc(sizeof(struct hlist_head) * CFQ_QHASH_ENTRIES, GFP_KERNEL);
2255 if (!cfqd->cfq_hash)
2256 goto out_cfqhash;
2257
Matthew Dobson93d23412006-03-26 01:37:50 -08002258 cfqd->crq_pool = mempool_create_slab_pool(BLKDEV_MIN_RQ, crq_pool);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002259 if (!cfqd->crq_pool)
2260 goto out_crqpool;
2261
2262 for (i = 0; i < CFQ_MHASH_ENTRIES; i++)
2263 INIT_HLIST_HEAD(&cfqd->crq_hash[i]);
2264 for (i = 0; i < CFQ_QHASH_ENTRIES; i++)
2265 INIT_HLIST_HEAD(&cfqd->cfq_hash[i]);
2266
Linus Torvalds1da177e2005-04-16 15:20:36 -07002267 cfqd->queue = q;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002268
Jens Axboe22e2c502005-06-27 10:55:12 +02002269 init_timer(&cfqd->idle_slice_timer);
2270 cfqd->idle_slice_timer.function = cfq_idle_slice_timer;
2271 cfqd->idle_slice_timer.data = (unsigned long) cfqd;
2272
2273 init_timer(&cfqd->idle_class_timer);
2274 cfqd->idle_class_timer.function = cfq_idle_class_timer;
2275 cfqd->idle_class_timer.data = (unsigned long) cfqd;
2276
2277 INIT_WORK(&cfqd->unplug_work, cfq_kick_queue, q);
2278
Linus Torvalds1da177e2005-04-16 15:20:36 -07002279 cfqd->cfq_queued = cfq_queued;
2280 cfqd->cfq_quantum = cfq_quantum;
Jens Axboe22e2c502005-06-27 10:55:12 +02002281 cfqd->cfq_fifo_expire[0] = cfq_fifo_expire[0];
2282 cfqd->cfq_fifo_expire[1] = cfq_fifo_expire[1];
Linus Torvalds1da177e2005-04-16 15:20:36 -07002283 cfqd->cfq_back_max = cfq_back_max;
2284 cfqd->cfq_back_penalty = cfq_back_penalty;
Jens Axboe22e2c502005-06-27 10:55:12 +02002285 cfqd->cfq_slice[0] = cfq_slice_async;
2286 cfqd->cfq_slice[1] = cfq_slice_sync;
2287 cfqd->cfq_slice_async_rq = cfq_slice_async_rq;
2288 cfqd->cfq_slice_idle = cfq_slice_idle;
Jens Axboe3b181522005-06-27 10:56:24 +02002289
Jens Axboebc1c1162006-06-08 08:49:06 +02002290 return cfqd;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002291out_crqpool:
2292 kfree(cfqd->cfq_hash);
2293out_cfqhash:
2294 kfree(cfqd->crq_hash);
2295out_crqhash:
2296 kfree(cfqd);
Jens Axboebc1c1162006-06-08 08:49:06 +02002297 return NULL;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002298}
2299
2300static void cfq_slab_kill(void)
2301{
2302 if (crq_pool)
2303 kmem_cache_destroy(crq_pool);
2304 if (cfq_pool)
2305 kmem_cache_destroy(cfq_pool);
2306 if (cfq_ioc_pool)
2307 kmem_cache_destroy(cfq_ioc_pool);
2308}
2309
2310static int __init cfq_slab_setup(void)
2311{
2312 crq_pool = kmem_cache_create("crq_pool", sizeof(struct cfq_rq), 0, 0,
2313 NULL, NULL);
2314 if (!crq_pool)
2315 goto fail;
2316
2317 cfq_pool = kmem_cache_create("cfq_pool", sizeof(struct cfq_queue), 0, 0,
2318 NULL, NULL);
2319 if (!cfq_pool)
2320 goto fail;
2321
2322 cfq_ioc_pool = kmem_cache_create("cfq_ioc_pool",
2323 sizeof(struct cfq_io_context), 0, 0, NULL, NULL);
2324 if (!cfq_ioc_pool)
2325 goto fail;
2326
2327 return 0;
2328fail:
2329 cfq_slab_kill();
2330 return -ENOMEM;
2331}
2332
Linus Torvalds1da177e2005-04-16 15:20:36 -07002333/*
2334 * sysfs parts below -->
2335 */
Linus Torvalds1da177e2005-04-16 15:20:36 -07002336
2337static ssize_t
2338cfq_var_show(unsigned int var, char *page)
2339{
2340 return sprintf(page, "%d\n", var);
2341}
2342
2343static ssize_t
2344cfq_var_store(unsigned int *var, const char *page, size_t count)
2345{
2346 char *p = (char *) page;
2347
2348 *var = simple_strtoul(p, &p, 10);
2349 return count;
2350}
2351
Linus Torvalds1da177e2005-04-16 15:20:36 -07002352#define SHOW_FUNCTION(__FUNC, __VAR, __CONV) \
Al Viro3d1ab402006-03-18 18:35:43 -05002353static ssize_t __FUNC(elevator_t *e, char *page) \
Linus Torvalds1da177e2005-04-16 15:20:36 -07002354{ \
Al Viro3d1ab402006-03-18 18:35:43 -05002355 struct cfq_data *cfqd = e->elevator_data; \
Linus Torvalds1da177e2005-04-16 15:20:36 -07002356 unsigned int __data = __VAR; \
2357 if (__CONV) \
2358 __data = jiffies_to_msecs(__data); \
2359 return cfq_var_show(__data, (page)); \
2360}
2361SHOW_FUNCTION(cfq_quantum_show, cfqd->cfq_quantum, 0);
2362SHOW_FUNCTION(cfq_queued_show, cfqd->cfq_queued, 0);
Jens Axboe22e2c502005-06-27 10:55:12 +02002363SHOW_FUNCTION(cfq_fifo_expire_sync_show, cfqd->cfq_fifo_expire[1], 1);
2364SHOW_FUNCTION(cfq_fifo_expire_async_show, cfqd->cfq_fifo_expire[0], 1);
Al Viroe572ec72006-03-18 22:27:18 -05002365SHOW_FUNCTION(cfq_back_seek_max_show, cfqd->cfq_back_max, 0);
2366SHOW_FUNCTION(cfq_back_seek_penalty_show, cfqd->cfq_back_penalty, 0);
Jens Axboe22e2c502005-06-27 10:55:12 +02002367SHOW_FUNCTION(cfq_slice_idle_show, cfqd->cfq_slice_idle, 1);
2368SHOW_FUNCTION(cfq_slice_sync_show, cfqd->cfq_slice[1], 1);
2369SHOW_FUNCTION(cfq_slice_async_show, cfqd->cfq_slice[0], 1);
2370SHOW_FUNCTION(cfq_slice_async_rq_show, cfqd->cfq_slice_async_rq, 0);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002371#undef SHOW_FUNCTION
2372
2373#define STORE_FUNCTION(__FUNC, __PTR, MIN, MAX, __CONV) \
Al Viro3d1ab402006-03-18 18:35:43 -05002374static ssize_t __FUNC(elevator_t *e, const char *page, size_t count) \
Linus Torvalds1da177e2005-04-16 15:20:36 -07002375{ \
Al Viro3d1ab402006-03-18 18:35:43 -05002376 struct cfq_data *cfqd = e->elevator_data; \
Linus Torvalds1da177e2005-04-16 15:20:36 -07002377 unsigned int __data; \
2378 int ret = cfq_var_store(&__data, (page), count); \
2379 if (__data < (MIN)) \
2380 __data = (MIN); \
2381 else if (__data > (MAX)) \
2382 __data = (MAX); \
2383 if (__CONV) \
2384 *(__PTR) = msecs_to_jiffies(__data); \
2385 else \
2386 *(__PTR) = __data; \
2387 return ret; \
2388}
2389STORE_FUNCTION(cfq_quantum_store, &cfqd->cfq_quantum, 1, UINT_MAX, 0);
2390STORE_FUNCTION(cfq_queued_store, &cfqd->cfq_queued, 1, UINT_MAX, 0);
Jens Axboe22e2c502005-06-27 10:55:12 +02002391STORE_FUNCTION(cfq_fifo_expire_sync_store, &cfqd->cfq_fifo_expire[1], 1, UINT_MAX, 1);
2392STORE_FUNCTION(cfq_fifo_expire_async_store, &cfqd->cfq_fifo_expire[0], 1, UINT_MAX, 1);
Al Viroe572ec72006-03-18 22:27:18 -05002393STORE_FUNCTION(cfq_back_seek_max_store, &cfqd->cfq_back_max, 0, UINT_MAX, 0);
2394STORE_FUNCTION(cfq_back_seek_penalty_store, &cfqd->cfq_back_penalty, 1, UINT_MAX, 0);
Jens Axboe22e2c502005-06-27 10:55:12 +02002395STORE_FUNCTION(cfq_slice_idle_store, &cfqd->cfq_slice_idle, 0, UINT_MAX, 1);
2396STORE_FUNCTION(cfq_slice_sync_store, &cfqd->cfq_slice[1], 1, UINT_MAX, 1);
2397STORE_FUNCTION(cfq_slice_async_store, &cfqd->cfq_slice[0], 1, UINT_MAX, 1);
2398STORE_FUNCTION(cfq_slice_async_rq_store, &cfqd->cfq_slice_async_rq, 1, UINT_MAX, 0);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002399#undef STORE_FUNCTION
2400
Al Viroe572ec72006-03-18 22:27:18 -05002401#define CFQ_ATTR(name) \
2402 __ATTR(name, S_IRUGO|S_IWUSR, cfq_##name##_show, cfq_##name##_store)
Jens Axboe3b181522005-06-27 10:56:24 +02002403
Al Viroe572ec72006-03-18 22:27:18 -05002404static struct elv_fs_entry cfq_attrs[] = {
2405 CFQ_ATTR(quantum),
2406 CFQ_ATTR(queued),
2407 CFQ_ATTR(fifo_expire_sync),
2408 CFQ_ATTR(fifo_expire_async),
2409 CFQ_ATTR(back_seek_max),
2410 CFQ_ATTR(back_seek_penalty),
2411 CFQ_ATTR(slice_sync),
2412 CFQ_ATTR(slice_async),
2413 CFQ_ATTR(slice_async_rq),
2414 CFQ_ATTR(slice_idle),
Al Viroe572ec72006-03-18 22:27:18 -05002415 __ATTR_NULL
Linus Torvalds1da177e2005-04-16 15:20:36 -07002416};
2417
Linus Torvalds1da177e2005-04-16 15:20:36 -07002418static struct elevator_type iosched_cfq = {
2419 .ops = {
2420 .elevator_merge_fn = cfq_merge,
2421 .elevator_merged_fn = cfq_merged_request,
2422 .elevator_merge_req_fn = cfq_merged_requests,
Jens Axboeb4878f22005-10-20 16:42:29 +02002423 .elevator_dispatch_fn = cfq_dispatch_requests,
Linus Torvalds1da177e2005-04-16 15:20:36 -07002424 .elevator_add_req_fn = cfq_insert_request,
Jens Axboeb4878f22005-10-20 16:42:29 +02002425 .elevator_activate_req_fn = cfq_activate_request,
Linus Torvalds1da177e2005-04-16 15:20:36 -07002426 .elevator_deactivate_req_fn = cfq_deactivate_request,
2427 .elevator_queue_empty_fn = cfq_queue_empty,
2428 .elevator_completed_req_fn = cfq_completed_request,
2429 .elevator_former_req_fn = cfq_former_request,
2430 .elevator_latter_req_fn = cfq_latter_request,
2431 .elevator_set_req_fn = cfq_set_request,
2432 .elevator_put_req_fn = cfq_put_request,
2433 .elevator_may_queue_fn = cfq_may_queue,
2434 .elevator_init_fn = cfq_init_queue,
2435 .elevator_exit_fn = cfq_exit_queue,
Al Viroe17a9482006-03-18 13:21:20 -05002436 .trim = cfq_trim,
Linus Torvalds1da177e2005-04-16 15:20:36 -07002437 },
Al Viro3d1ab402006-03-18 18:35:43 -05002438 .elevator_attrs = cfq_attrs,
Linus Torvalds1da177e2005-04-16 15:20:36 -07002439 .elevator_name = "cfq",
2440 .elevator_owner = THIS_MODULE,
2441};
2442
2443static int __init cfq_init(void)
2444{
2445 int ret;
2446
Jens Axboe22e2c502005-06-27 10:55:12 +02002447 /*
2448 * could be 0 on HZ < 1000 setups
2449 */
2450 if (!cfq_slice_async)
2451 cfq_slice_async = 1;
2452 if (!cfq_slice_idle)
2453 cfq_slice_idle = 1;
2454
Linus Torvalds1da177e2005-04-16 15:20:36 -07002455 if (cfq_slab_setup())
2456 return -ENOMEM;
2457
2458 ret = elv_register(&iosched_cfq);
Jens Axboe22e2c502005-06-27 10:55:12 +02002459 if (ret)
2460 cfq_slab_kill();
Linus Torvalds1da177e2005-04-16 15:20:36 -07002461
Linus Torvalds1da177e2005-04-16 15:20:36 -07002462 return ret;
2463}
2464
2465static void __exit cfq_exit(void)
2466{
Al Viro334e94d2006-03-18 15:05:53 -05002467 DECLARE_COMPLETION(all_gone);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002468 elv_unregister(&iosched_cfq);
Al Viro334e94d2006-03-18 15:05:53 -05002469 ioc_gone = &all_gone;
OGAWA Hirofumifba82272006-04-18 09:44:06 +02002470 /* ioc_gone's update must be visible before reading ioc_count */
2471 smp_wmb();
Al Viro334e94d2006-03-18 15:05:53 -05002472 if (atomic_read(&ioc_count))
OGAWA Hirofumifba82272006-04-18 09:44:06 +02002473 wait_for_completion(ioc_gone);
Al Viro334e94d2006-03-18 15:05:53 -05002474 synchronize_rcu();
Christoph Hellwig83521d32005-10-30 15:01:39 -08002475 cfq_slab_kill();
Linus Torvalds1da177e2005-04-16 15:20:36 -07002476}
2477
2478module_init(cfq_init);
2479module_exit(cfq_exit);
2480
2481MODULE_AUTHOR("Jens Axboe");
2482MODULE_LICENSE("GPL");
2483MODULE_DESCRIPTION("Completely Fair Queueing IO scheduler");