blob: 4c4e9cc3ae26890c0b63a8dcbf6aff3c0caa7d7c [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 Axboe206dc692006-03-28 13:03:44 +020029static int cfq_slice_idle = HZ / 70;
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_EMPTY(node) ((node)->rb_node == NULL)
Linus Torvalds1da177e2005-04-16 15:20:36 -070064#define RB_CLEAR(node) do { \
David Woodhouse3db3a442006-04-21 13:15:17 +010065 memset(node, 0, sizeof(*node)); \
Linus Torvalds1da177e2005-04-16 15:20:36 -070066} while (0)
67#define RB_CLEAR_ROOT(root) ((root)->rb_node = NULL)
Linus Torvalds1da177e2005-04-16 15:20:36 -070068#define rb_entry_crq(node) rb_entry((node), struct cfq_rq, rb_node)
69#define rq_rb_key(rq) (rq)->sector
70
Linus Torvalds1da177e2005-04-16 15:20:36 -070071static kmem_cache_t *crq_pool;
72static kmem_cache_t *cfq_pool;
73static kmem_cache_t *cfq_ioc_pool;
74
Al Viro334e94d2006-03-18 15:05:53 -050075static atomic_t ioc_count = ATOMIC_INIT(0);
76static struct completion *ioc_gone;
77
Jens Axboe22e2c502005-06-27 10:55:12 +020078#define CFQ_PRIO_LISTS IOPRIO_BE_NR
79#define cfq_class_idle(cfqq) ((cfqq)->ioprio_class == IOPRIO_CLASS_IDLE)
80#define cfq_class_be(cfqq) ((cfqq)->ioprio_class == IOPRIO_CLASS_BE)
81#define cfq_class_rt(cfqq) ((cfqq)->ioprio_class == IOPRIO_CLASS_RT)
82
Jens Axboe3b181522005-06-27 10:56:24 +020083#define ASYNC (0)
84#define SYNC (1)
85
86#define cfq_cfqq_dispatched(cfqq) \
87 ((cfqq)->on_dispatch[ASYNC] + (cfqq)->on_dispatch[SYNC])
88
89#define cfq_cfqq_class_sync(cfqq) ((cfqq)->key != CFQ_KEY_ASYNC)
90
91#define cfq_cfqq_sync(cfqq) \
92 (cfq_cfqq_class_sync(cfqq) || (cfqq)->on_dispatch[SYNC])
Jens Axboe22e2c502005-06-27 10:55:12 +020093
Jens Axboe206dc692006-03-28 13:03:44 +020094#define sample_valid(samples) ((samples) > 80)
95
Jens Axboe22e2c502005-06-27 10:55:12 +020096/*
97 * Per block device queue structure
98 */
Linus Torvalds1da177e2005-04-16 15:20:36 -070099struct cfq_data {
Jens Axboe22e2c502005-06-27 10:55:12 +0200100 request_queue_t *queue;
101
102 /*
103 * rr list of queues with requests and the count of them
104 */
105 struct list_head rr_list[CFQ_PRIO_LISTS];
106 struct list_head busy_rr;
107 struct list_head cur_rr;
108 struct list_head idle_rr;
109 unsigned int busy_queues;
110
111 /*
112 * non-ordered list of empty cfqq's
113 */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700114 struct list_head empty_list;
115
Jens Axboe22e2c502005-06-27 10:55:12 +0200116 /*
117 * cfqq lookup hash
118 */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700119 struct hlist_head *cfq_hash;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700120
Jens Axboe22e2c502005-06-27 10:55:12 +0200121 /*
122 * global crq hash for all queues
123 */
124 struct hlist_head *crq_hash;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700125
Linus Torvalds1da177e2005-04-16 15:20:36 -0700126 mempool_t *crq_pool;
127
Jens Axboe22e2c502005-06-27 10:55:12 +0200128 int rq_in_driver;
Jens Axboe25776e32006-06-01 10:12:26 +0200129 int hw_tag;
Jens Axboe22e2c502005-06-27 10:55:12 +0200130
131 /*
132 * schedule slice state info
133 */
134 /*
135 * idle window management
136 */
137 struct timer_list idle_slice_timer;
138 struct work_struct unplug_work;
139
140 struct cfq_queue *active_queue;
141 struct cfq_io_context *active_cic;
142 int cur_prio, cur_end_prio;
143 unsigned int dispatch_slice;
144
145 struct timer_list idle_class_timer;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700146
147 sector_t last_sector;
Jens Axboe22e2c502005-06-27 10:55:12 +0200148 unsigned long last_end_request;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700149
Jens Axboe22e2c502005-06-27 10:55:12 +0200150 unsigned int rq_starved;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700151
152 /*
153 * tunables, see top of file
154 */
155 unsigned int cfq_quantum;
156 unsigned int cfq_queued;
Jens Axboe22e2c502005-06-27 10:55:12 +0200157 unsigned int cfq_fifo_expire[2];
Linus Torvalds1da177e2005-04-16 15:20:36 -0700158 unsigned int cfq_back_penalty;
159 unsigned int cfq_back_max;
Jens Axboe22e2c502005-06-27 10:55:12 +0200160 unsigned int cfq_slice[2];
161 unsigned int cfq_slice_async_rq;
162 unsigned int cfq_slice_idle;
Al Virod9ff4182006-03-18 13:51:22 -0500163
164 struct list_head cic_list;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700165};
166
Jens Axboe22e2c502005-06-27 10:55:12 +0200167/*
168 * Per process-grouping structure
169 */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700170struct cfq_queue {
171 /* reference count */
172 atomic_t ref;
173 /* parent cfq_data */
174 struct cfq_data *cfqd;
Jens Axboe22e2c502005-06-27 10:55:12 +0200175 /* cfqq lookup hash */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700176 struct hlist_node cfq_hash;
177 /* hash key */
Jens Axboe22e2c502005-06-27 10:55:12 +0200178 unsigned int key;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700179 /* on either rr or empty list of cfqd */
180 struct list_head cfq_list;
181 /* sorted list of pending requests */
182 struct rb_root sort_list;
183 /* if fifo isn't expired, next request to serve */
184 struct cfq_rq *next_crq;
185 /* requests queued in sort_list */
186 int queued[2];
187 /* currently allocated requests */
188 int allocated[2];
189 /* fifo list of requests in sort_list */
Jens Axboe22e2c502005-06-27 10:55:12 +0200190 struct list_head fifo;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700191
Jens Axboe22e2c502005-06-27 10:55:12 +0200192 unsigned long slice_start;
193 unsigned long slice_end;
194 unsigned long slice_left;
195 unsigned long service_last;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700196
Jens Axboe3b181522005-06-27 10:56:24 +0200197 /* number of requests that are on the dispatch list */
198 int on_dispatch[2];
Jens Axboe22e2c502005-06-27 10:55:12 +0200199
200 /* io prio of this group */
201 unsigned short ioprio, org_ioprio;
202 unsigned short ioprio_class, org_ioprio_class;
203
Jens Axboe3b181522005-06-27 10:56:24 +0200204 /* various state flags, see below */
205 unsigned int flags;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700206};
207
208struct cfq_rq {
209 struct rb_node rb_node;
210 sector_t rb_key;
211 struct request *request;
212 struct hlist_node hash;
213
214 struct cfq_queue *cfq_queue;
215 struct cfq_io_context *io_context;
216
Jens Axboe3b181522005-06-27 10:56:24 +0200217 unsigned int crq_flags;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700218};
219
Jens Axboe3b181522005-06-27 10:56:24 +0200220enum cfqq_state_flags {
221 CFQ_CFQQ_FLAG_on_rr = 0,
222 CFQ_CFQQ_FLAG_wait_request,
223 CFQ_CFQQ_FLAG_must_alloc,
224 CFQ_CFQQ_FLAG_must_alloc_slice,
225 CFQ_CFQQ_FLAG_must_dispatch,
226 CFQ_CFQQ_FLAG_fifo_expire,
227 CFQ_CFQQ_FLAG_idle_window,
228 CFQ_CFQQ_FLAG_prio_changed,
Jens Axboe3b181522005-06-27 10:56:24 +0200229};
230
231#define CFQ_CFQQ_FNS(name) \
232static inline void cfq_mark_cfqq_##name(struct cfq_queue *cfqq) \
233{ \
234 cfqq->flags |= (1 << CFQ_CFQQ_FLAG_##name); \
235} \
236static inline void cfq_clear_cfqq_##name(struct cfq_queue *cfqq) \
237{ \
238 cfqq->flags &= ~(1 << CFQ_CFQQ_FLAG_##name); \
239} \
240static inline int cfq_cfqq_##name(const struct cfq_queue *cfqq) \
241{ \
242 return (cfqq->flags & (1 << CFQ_CFQQ_FLAG_##name)) != 0; \
243}
244
245CFQ_CFQQ_FNS(on_rr);
246CFQ_CFQQ_FNS(wait_request);
247CFQ_CFQQ_FNS(must_alloc);
248CFQ_CFQQ_FNS(must_alloc_slice);
249CFQ_CFQQ_FNS(must_dispatch);
250CFQ_CFQQ_FNS(fifo_expire);
251CFQ_CFQQ_FNS(idle_window);
252CFQ_CFQQ_FNS(prio_changed);
Jens Axboe3b181522005-06-27 10:56:24 +0200253#undef CFQ_CFQQ_FNS
254
255enum cfq_rq_state_flags {
Jens Axboeb4878f22005-10-20 16:42:29 +0200256 CFQ_CRQ_FLAG_is_sync = 0,
Jens Axboe3b181522005-06-27 10:56:24 +0200257};
258
259#define CFQ_CRQ_FNS(name) \
260static inline void cfq_mark_crq_##name(struct cfq_rq *crq) \
261{ \
262 crq->crq_flags |= (1 << CFQ_CRQ_FLAG_##name); \
263} \
264static inline void cfq_clear_crq_##name(struct cfq_rq *crq) \
265{ \
266 crq->crq_flags &= ~(1 << CFQ_CRQ_FLAG_##name); \
267} \
268static inline int cfq_crq_##name(const struct cfq_rq *crq) \
269{ \
270 return (crq->crq_flags & (1 << CFQ_CRQ_FLAG_##name)) != 0; \
271}
272
Jens Axboe3b181522005-06-27 10:56:24 +0200273CFQ_CRQ_FNS(is_sync);
Jens Axboe3b181522005-06-27 10:56:24 +0200274#undef CFQ_CRQ_FNS
275
276static struct cfq_queue *cfq_find_cfq_hash(struct cfq_data *, unsigned int, unsigned short);
Jens Axboeb4878f22005-10-20 16:42:29 +0200277static void cfq_dispatch_insert(request_queue_t *, struct cfq_rq *);
Al Viro6f325a12006-03-18 14:58:37 -0500278static 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 -0700279
Linus Torvalds1da177e2005-04-16 15:20:36 -0700280/*
281 * lots of deadline iosched dupes, can be abstracted later...
282 */
283static inline void cfq_del_crq_hash(struct cfq_rq *crq)
284{
285 hlist_del_init(&crq->hash);
286}
287
Linus Torvalds1da177e2005-04-16 15:20:36 -0700288static inline void cfq_add_crq_hash(struct cfq_data *cfqd, struct cfq_rq *crq)
289{
290 const int hash_idx = CFQ_MHASH_FN(rq_hash_key(crq->request));
291
Linus Torvalds1da177e2005-04-16 15:20:36 -0700292 hlist_add_head(&crq->hash, &cfqd->crq_hash[hash_idx]);
293}
294
295static struct request *cfq_find_rq_hash(struct cfq_data *cfqd, sector_t offset)
296{
297 struct hlist_head *hash_list = &cfqd->crq_hash[CFQ_MHASH_FN(offset)];
298 struct hlist_node *entry, *next;
299
300 hlist_for_each_safe(entry, next, hash_list) {
301 struct cfq_rq *crq = list_entry_hash(entry);
302 struct request *__rq = crq->request;
303
Linus Torvalds1da177e2005-04-16 15:20:36 -0700304 if (!rq_mergeable(__rq)) {
305 cfq_del_crq_hash(crq);
306 continue;
307 }
308
309 if (rq_hash_key(__rq) == offset)
310 return __rq;
311 }
312
313 return NULL;
314}
315
Andrew Morton99f95e52005-06-27 20:14:05 -0700316/*
317 * scheduler run of queue, if there are requests pending and no one in the
318 * driver that will restart queueing
319 */
320static inline void cfq_schedule_dispatch(struct cfq_data *cfqd)
321{
Jens Axboe7b14e3b2006-02-28 09:35:11 +0100322 if (cfqd->busy_queues)
Andrew Morton99f95e52005-06-27 20:14:05 -0700323 kblockd_schedule_work(&cfqd->unplug_work);
324}
325
326static int cfq_queue_empty(request_queue_t *q)
327{
328 struct cfq_data *cfqd = q->elevator->elevator_data;
329
Jens Axboeb4878f22005-10-20 16:42:29 +0200330 return !cfqd->busy_queues;
Andrew Morton99f95e52005-06-27 20:14:05 -0700331}
332
Jens Axboe206dc692006-03-28 13:03:44 +0200333static inline pid_t cfq_queue_pid(struct task_struct *task, int rw)
334{
Jens Axboeb31dc662006-06-13 08:26:10 +0200335 if (rw == READ || rw == WRITE_SYNC)
Jens Axboe206dc692006-03-28 13:03:44 +0200336 return task->pid;
337
338 return CFQ_KEY_ASYNC;
339}
340
Linus Torvalds1da177e2005-04-16 15:20:36 -0700341/*
342 * Lifted from AS - choose which of crq1 and crq2 that is best served now.
343 * We choose the request that is closest to the head right now. Distance
Andreas Mohre8a99052006-03-28 08:59:49 +0200344 * behind the head is penalized and only allowed to a certain extent.
Linus Torvalds1da177e2005-04-16 15:20:36 -0700345 */
346static struct cfq_rq *
347cfq_choose_req(struct cfq_data *cfqd, struct cfq_rq *crq1, struct cfq_rq *crq2)
348{
349 sector_t last, s1, s2, d1 = 0, d2 = 0;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700350 unsigned long back_max;
Andreas Mohre8a99052006-03-28 08:59:49 +0200351#define CFQ_RQ1_WRAP 0x01 /* request 1 wraps */
352#define CFQ_RQ2_WRAP 0x02 /* request 2 wraps */
353 unsigned wrap = 0; /* bit mask: requests behind the disk head? */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700354
355 if (crq1 == NULL || crq1 == crq2)
356 return crq2;
357 if (crq2 == NULL)
358 return crq1;
Jens Axboe9c2c38a2005-08-24 14:57:54 +0200359
Jens Axboe9c2c38a2005-08-24 14:57:54 +0200360 if (cfq_crq_is_sync(crq1) && !cfq_crq_is_sync(crq2))
361 return crq1;
362 else if (cfq_crq_is_sync(crq2) && !cfq_crq_is_sync(crq1))
Jens Axboe22e2c502005-06-27 10:55:12 +0200363 return crq2;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700364
365 s1 = crq1->request->sector;
366 s2 = crq2->request->sector;
367
368 last = cfqd->last_sector;
369
Linus Torvalds1da177e2005-04-16 15:20:36 -0700370 /*
371 * by definition, 1KiB is 2 sectors
372 */
373 back_max = cfqd->cfq_back_max * 2;
374
375 /*
376 * Strict one way elevator _except_ in the case where we allow
377 * short backward seeks which are biased as twice the cost of a
378 * similar forward seek.
379 */
380 if (s1 >= last)
381 d1 = s1 - last;
382 else if (s1 + back_max >= last)
383 d1 = (last - s1) * cfqd->cfq_back_penalty;
384 else
Andreas Mohre8a99052006-03-28 08:59:49 +0200385 wrap |= CFQ_RQ1_WRAP;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700386
387 if (s2 >= last)
388 d2 = s2 - last;
389 else if (s2 + back_max >= last)
390 d2 = (last - s2) * cfqd->cfq_back_penalty;
391 else
Andreas Mohre8a99052006-03-28 08:59:49 +0200392 wrap |= CFQ_RQ2_WRAP;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700393
394 /* Found required data */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700395
Andreas Mohre8a99052006-03-28 08:59:49 +0200396 /*
397 * By doing switch() on the bit mask "wrap" we avoid having to
398 * check two variables for all permutations: --> faster!
399 */
400 switch (wrap) {
401 case 0: /* common case for CFQ: crq1 and crq2 not wrapped */
402 if (d1 < d2)
403 return crq1;
404 else if (d2 < d1)
405 return crq2;
406 else {
407 if (s1 >= s2)
408 return crq1;
409 else
410 return crq2;
411 }
412
413 case CFQ_RQ2_WRAP:
Linus Torvalds1da177e2005-04-16 15:20:36 -0700414 return crq1;
Andreas Mohre8a99052006-03-28 08:59:49 +0200415 case CFQ_RQ1_WRAP:
Linus Torvalds1da177e2005-04-16 15:20:36 -0700416 return crq2;
Andreas Mohre8a99052006-03-28 08:59:49 +0200417 case (CFQ_RQ1_WRAP|CFQ_RQ2_WRAP): /* both crqs wrapped */
418 default:
419 /*
420 * Since both rqs are wrapped,
421 * start with the one that's further behind head
422 * (--> only *one* back seek required),
423 * since back seek takes more time than forward.
424 */
425 if (s1 <= s2)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700426 return crq1;
427 else
428 return crq2;
429 }
430}
431
432/*
433 * would be nice to take fifo expire time into account as well
434 */
435static struct cfq_rq *
436cfq_find_next_crq(struct cfq_data *cfqd, struct cfq_queue *cfqq,
437 struct cfq_rq *last)
438{
439 struct cfq_rq *crq_next = NULL, *crq_prev = NULL;
440 struct rb_node *rbnext, *rbprev;
441
Jens Axboeb4878f22005-10-20 16:42:29 +0200442 if (!(rbnext = rb_next(&last->rb_node))) {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700443 rbnext = rb_first(&cfqq->sort_list);
Jens Axboe22e2c502005-06-27 10:55:12 +0200444 if (rbnext == &last->rb_node)
445 rbnext = NULL;
446 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700447
448 rbprev = rb_prev(&last->rb_node);
449
450 if (rbprev)
451 crq_prev = rb_entry_crq(rbprev);
452 if (rbnext)
453 crq_next = rb_entry_crq(rbnext);
454
455 return cfq_choose_req(cfqd, crq_next, crq_prev);
456}
457
458static void cfq_update_next_crq(struct cfq_rq *crq)
459{
460 struct cfq_queue *cfqq = crq->cfq_queue;
461
462 if (cfqq->next_crq == crq)
463 cfqq->next_crq = cfq_find_next_crq(cfqq->cfqd, cfqq, crq);
464}
465
Jens Axboe22e2c502005-06-27 10:55:12 +0200466static void cfq_resort_rr_list(struct cfq_queue *cfqq, int preempted)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700467{
Jens Axboe22e2c502005-06-27 10:55:12 +0200468 struct cfq_data *cfqd = cfqq->cfqd;
469 struct list_head *list, *entry;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700470
Jens Axboe3b181522005-06-27 10:56:24 +0200471 BUG_ON(!cfq_cfqq_on_rr(cfqq));
Linus Torvalds1da177e2005-04-16 15:20:36 -0700472
473 list_del(&cfqq->cfq_list);
474
Jens Axboe22e2c502005-06-27 10:55:12 +0200475 if (cfq_class_rt(cfqq))
476 list = &cfqd->cur_rr;
477 else if (cfq_class_idle(cfqq))
478 list = &cfqd->idle_rr;
479 else {
480 /*
481 * if cfqq has requests in flight, don't allow it to be
482 * found in cfq_set_active_queue before it has finished them.
483 * this is done to increase fairness between a process that
484 * has lots of io pending vs one that only generates one
485 * sporadically or synchronously
486 */
Jens Axboe3b181522005-06-27 10:56:24 +0200487 if (cfq_cfqq_dispatched(cfqq))
Jens Axboe22e2c502005-06-27 10:55:12 +0200488 list = &cfqd->busy_rr;
489 else
490 list = &cfqd->rr_list[cfqq->ioprio];
491 }
492
Linus Torvalds1da177e2005-04-16 15:20:36 -0700493 /*
Jens Axboe22e2c502005-06-27 10:55:12 +0200494 * if queue was preempted, just add to front to be fair. busy_rr
Jens Axboeb52a8342006-06-01 18:53:43 +0200495 * isn't sorted, but insert at the back for fairness.
Linus Torvalds1da177e2005-04-16 15:20:36 -0700496 */
Jens Axboe22e2c502005-06-27 10:55:12 +0200497 if (preempted || list == &cfqd->busy_rr) {
Jens Axboeb52a8342006-06-01 18:53:43 +0200498 if (preempted)
499 list = list->prev;
500
501 list_add_tail(&cfqq->cfq_list, list);
Jens Axboe22e2c502005-06-27 10:55:12 +0200502 return;
503 }
504
505 /*
506 * sort by when queue was last serviced
507 */
508 entry = list;
509 while ((entry = entry->prev) != list) {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700510 struct cfq_queue *__cfqq = list_entry_cfqq(entry);
511
Jens Axboe22e2c502005-06-27 10:55:12 +0200512 if (!__cfqq->service_last)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700513 break;
Jens Axboe22e2c502005-06-27 10:55:12 +0200514 if (time_before(__cfqq->service_last, cfqq->service_last))
515 break;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700516 }
517
518 list_add(&cfqq->cfq_list, entry);
519}
520
521/*
522 * add to busy list of queues for service, trying to be fair in ordering
Jens Axboe22e2c502005-06-27 10:55:12 +0200523 * the pending list according to last request service
Linus Torvalds1da177e2005-04-16 15:20:36 -0700524 */
525static inline void
Jens Axboeb4878f22005-10-20 16:42:29 +0200526cfq_add_cfqq_rr(struct cfq_data *cfqd, struct cfq_queue *cfqq)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700527{
Jens Axboe3b181522005-06-27 10:56:24 +0200528 BUG_ON(cfq_cfqq_on_rr(cfqq));
529 cfq_mark_cfqq_on_rr(cfqq);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700530 cfqd->busy_queues++;
531
Jens Axboeb4878f22005-10-20 16:42:29 +0200532 cfq_resort_rr_list(cfqq, 0);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700533}
534
535static inline void
536cfq_del_cfqq_rr(struct cfq_data *cfqd, struct cfq_queue *cfqq)
537{
Jens Axboe3b181522005-06-27 10:56:24 +0200538 BUG_ON(!cfq_cfqq_on_rr(cfqq));
539 cfq_clear_cfqq_on_rr(cfqq);
Jens Axboe22e2c502005-06-27 10:55:12 +0200540 list_move(&cfqq->cfq_list, &cfqd->empty_list);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700541
542 BUG_ON(!cfqd->busy_queues);
543 cfqd->busy_queues--;
544}
545
546/*
547 * rb tree support functions
548 */
549static inline void cfq_del_crq_rb(struct cfq_rq *crq)
550{
551 struct cfq_queue *cfqq = crq->cfq_queue;
Jens Axboeb4878f22005-10-20 16:42:29 +0200552 struct cfq_data *cfqd = cfqq->cfqd;
553 const int sync = cfq_crq_is_sync(crq);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700554
Jens Axboeb4878f22005-10-20 16:42:29 +0200555 BUG_ON(!cfqq->queued[sync]);
556 cfqq->queued[sync]--;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700557
Jens Axboeb4878f22005-10-20 16:42:29 +0200558 cfq_update_next_crq(crq);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700559
Jens Axboeb4878f22005-10-20 16:42:29 +0200560 rb_erase(&crq->rb_node, &cfqq->sort_list);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700561
Jens Axboeb4878f22005-10-20 16:42:29 +0200562 if (cfq_cfqq_on_rr(cfqq) && RB_EMPTY(&cfqq->sort_list))
563 cfq_del_cfqq_rr(cfqd, cfqq);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700564}
565
566static struct cfq_rq *
567__cfq_add_crq_rb(struct cfq_rq *crq)
568{
569 struct rb_node **p = &crq->cfq_queue->sort_list.rb_node;
570 struct rb_node *parent = NULL;
571 struct cfq_rq *__crq;
572
573 while (*p) {
574 parent = *p;
575 __crq = rb_entry_crq(parent);
576
577 if (crq->rb_key < __crq->rb_key)
578 p = &(*p)->rb_left;
579 else if (crq->rb_key > __crq->rb_key)
580 p = &(*p)->rb_right;
581 else
582 return __crq;
583 }
584
585 rb_link_node(&crq->rb_node, parent, p);
586 return NULL;
587}
588
589static void cfq_add_crq_rb(struct cfq_rq *crq)
590{
591 struct cfq_queue *cfqq = crq->cfq_queue;
592 struct cfq_data *cfqd = cfqq->cfqd;
593 struct request *rq = crq->request;
594 struct cfq_rq *__alias;
595
596 crq->rb_key = rq_rb_key(rq);
Jens Axboe3b181522005-06-27 10:56:24 +0200597 cfqq->queued[cfq_crq_is_sync(crq)]++;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700598
599 /*
600 * looks a little odd, but the first insert might return an alias.
601 * if that happens, put the alias on the dispatch list
602 */
603 while ((__alias = __cfq_add_crq_rb(crq)) != NULL)
Jens Axboeb4878f22005-10-20 16:42:29 +0200604 cfq_dispatch_insert(cfqd->queue, __alias);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700605
606 rb_insert_color(&crq->rb_node, &cfqq->sort_list);
607
Jens Axboe3b181522005-06-27 10:56:24 +0200608 if (!cfq_cfqq_on_rr(cfqq))
Jens Axboeb4878f22005-10-20 16:42:29 +0200609 cfq_add_cfqq_rr(cfqd, cfqq);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700610
611 /*
612 * check if this request is a better next-serve candidate
613 */
614 cfqq->next_crq = cfq_choose_req(cfqd, cfqq->next_crq, crq);
615}
616
617static inline void
618cfq_reposition_crq_rb(struct cfq_queue *cfqq, struct cfq_rq *crq)
619{
Jens Axboeb4878f22005-10-20 16:42:29 +0200620 rb_erase(&crq->rb_node, &cfqq->sort_list);
621 cfqq->queued[cfq_crq_is_sync(crq)]--;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700622
623 cfq_add_crq_rb(crq);
624}
625
Jens Axboe206dc692006-03-28 13:03:44 +0200626static struct request *
627cfq_find_rq_fmerge(struct cfq_data *cfqd, struct bio *bio)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700628{
Jens Axboe206dc692006-03-28 13:03:44 +0200629 struct task_struct *tsk = current;
630 pid_t key = cfq_queue_pid(tsk, bio_data_dir(bio));
631 struct cfq_queue *cfqq;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700632 struct rb_node *n;
Jens Axboe206dc692006-03-28 13:03:44 +0200633 sector_t sector;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700634
Jens Axboe206dc692006-03-28 13:03:44 +0200635 cfqq = cfq_find_cfq_hash(cfqd, key, tsk->ioprio);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700636 if (!cfqq)
637 goto out;
638
Jens Axboe206dc692006-03-28 13:03:44 +0200639 sector = bio->bi_sector + bio_sectors(bio);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700640 n = cfqq->sort_list.rb_node;
641 while (n) {
642 struct cfq_rq *crq = rb_entry_crq(n);
643
644 if (sector < crq->rb_key)
645 n = n->rb_left;
646 else if (sector > crq->rb_key)
647 n = n->rb_right;
648 else
649 return crq->request;
650 }
651
652out:
653 return NULL;
654}
655
Jens Axboeb4878f22005-10-20 16:42:29 +0200656static void cfq_activate_request(request_queue_t *q, struct request *rq)
657{
658 struct cfq_data *cfqd = q->elevator->elevator_data;
659
660 cfqd->rq_in_driver++;
Jens Axboe25776e32006-06-01 10:12:26 +0200661
662 /*
663 * If the depth is larger 1, it really could be queueing. But lets
664 * make the mark a little higher - idling could still be good for
665 * low queueing, and a low queueing number could also just indicate
666 * a SCSI mid layer like behaviour where limit+1 is often seen.
667 */
668 if (!cfqd->hw_tag && cfqd->rq_in_driver > 4)
669 cfqd->hw_tag = 1;
Jens Axboeb4878f22005-10-20 16:42:29 +0200670}
671
Linus Torvalds1da177e2005-04-16 15:20:36 -0700672static void cfq_deactivate_request(request_queue_t *q, struct request *rq)
673{
Jens Axboe22e2c502005-06-27 10:55:12 +0200674 struct cfq_data *cfqd = q->elevator->elevator_data;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700675
Jens Axboeb4878f22005-10-20 16:42:29 +0200676 WARN_ON(!cfqd->rq_in_driver);
677 cfqd->rq_in_driver--;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700678}
679
Jens Axboeb4878f22005-10-20 16:42:29 +0200680static void cfq_remove_request(struct request *rq)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700681{
682 struct cfq_rq *crq = RQ_DATA(rq);
683
Jens Axboeb4878f22005-10-20 16:42:29 +0200684 list_del_init(&rq->queuelist);
685 cfq_del_crq_rb(crq);
Tejun Heo98b11472005-10-20 16:46:54 +0200686 cfq_del_crq_hash(crq);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700687}
688
689static int
690cfq_merge(request_queue_t *q, struct request **req, struct bio *bio)
691{
692 struct cfq_data *cfqd = q->elevator->elevator_data;
693 struct request *__rq;
694 int ret;
695
Linus Torvalds1da177e2005-04-16 15:20:36 -0700696 __rq = cfq_find_rq_hash(cfqd, bio->bi_sector);
Jens Axboe22e2c502005-06-27 10:55:12 +0200697 if (__rq && elv_rq_merge_ok(__rq, bio)) {
698 ret = ELEVATOR_BACK_MERGE;
699 goto out;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700700 }
701
Jens Axboe206dc692006-03-28 13:03:44 +0200702 __rq = cfq_find_rq_fmerge(cfqd, bio);
Jens Axboe22e2c502005-06-27 10:55:12 +0200703 if (__rq && elv_rq_merge_ok(__rq, bio)) {
704 ret = ELEVATOR_FRONT_MERGE;
705 goto out;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700706 }
707
708 return ELEVATOR_NO_MERGE;
709out:
Linus Torvalds1da177e2005-04-16 15:20:36 -0700710 *req = __rq;
711 return ret;
712}
713
714static void cfq_merged_request(request_queue_t *q, struct request *req)
715{
716 struct cfq_data *cfqd = q->elevator->elevator_data;
717 struct cfq_rq *crq = RQ_DATA(req);
718
719 cfq_del_crq_hash(crq);
720 cfq_add_crq_hash(cfqd, crq);
721
Jens Axboeb4878f22005-10-20 16:42:29 +0200722 if (rq_rb_key(req) != crq->rb_key) {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700723 struct cfq_queue *cfqq = crq->cfq_queue;
724
725 cfq_update_next_crq(crq);
726 cfq_reposition_crq_rb(cfqq, crq);
727 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700728}
729
730static void
731cfq_merged_requests(request_queue_t *q, struct request *rq,
732 struct request *next)
733{
Linus Torvalds1da177e2005-04-16 15:20:36 -0700734 cfq_merged_request(q, rq);
735
Jens Axboe22e2c502005-06-27 10:55:12 +0200736 /*
737 * reposition in fifo if next is older than rq
738 */
739 if (!list_empty(&rq->queuelist) && !list_empty(&next->queuelist) &&
740 time_before(next->start_time, rq->start_time))
741 list_move(&rq->queuelist, &next->queuelist);
742
Jens Axboeb4878f22005-10-20 16:42:29 +0200743 cfq_remove_request(next);
Jens Axboe22e2c502005-06-27 10:55:12 +0200744}
745
746static inline void
747__cfq_set_active_queue(struct cfq_data *cfqd, struct cfq_queue *cfqq)
748{
749 if (cfqq) {
750 /*
751 * stop potential idle class queues waiting service
752 */
753 del_timer(&cfqd->idle_class_timer);
754
755 cfqq->slice_start = jiffies;
756 cfqq->slice_end = 0;
757 cfqq->slice_left = 0;
Jens Axboe3b181522005-06-27 10:56:24 +0200758 cfq_clear_cfqq_must_alloc_slice(cfqq);
759 cfq_clear_cfqq_fifo_expire(cfqq);
Jens Axboe22e2c502005-06-27 10:55:12 +0200760 }
761
762 cfqd->active_queue = cfqq;
763}
764
765/*
Jens Axboe7b14e3b2006-02-28 09:35:11 +0100766 * current cfqq expired its slice (or was too idle), select new one
767 */
768static void
769__cfq_slice_expired(struct cfq_data *cfqd, struct cfq_queue *cfqq,
770 int preempted)
771{
772 unsigned long now = jiffies;
773
774 if (cfq_cfqq_wait_request(cfqq))
775 del_timer(&cfqd->idle_slice_timer);
776
777 if (!preempted && !cfq_cfqq_dispatched(cfqq)) {
778 cfqq->service_last = now;
779 cfq_schedule_dispatch(cfqd);
780 }
781
782 cfq_clear_cfqq_must_dispatch(cfqq);
783 cfq_clear_cfqq_wait_request(cfqq);
784
785 /*
786 * store what was left of this slice, if the queue idled out
787 * or was preempted
788 */
789 if (time_after(cfqq->slice_end, now))
790 cfqq->slice_left = cfqq->slice_end - now;
791 else
792 cfqq->slice_left = 0;
793
794 if (cfq_cfqq_on_rr(cfqq))
795 cfq_resort_rr_list(cfqq, preempted);
796
797 if (cfqq == cfqd->active_queue)
798 cfqd->active_queue = NULL;
799
800 if (cfqd->active_cic) {
801 put_io_context(cfqd->active_cic->ioc);
802 cfqd->active_cic = NULL;
803 }
804
805 cfqd->dispatch_slice = 0;
806}
807
808static inline void cfq_slice_expired(struct cfq_data *cfqd, int preempted)
809{
810 struct cfq_queue *cfqq = cfqd->active_queue;
811
812 if (cfqq)
813 __cfq_slice_expired(cfqd, cfqq, preempted);
814}
815
816/*
Jens Axboe22e2c502005-06-27 10:55:12 +0200817 * 0
818 * 0,1
819 * 0,1,2
820 * 0,1,2,3
821 * 0,1,2,3,4
822 * 0,1,2,3,4,5
823 * 0,1,2,3,4,5,6
824 * 0,1,2,3,4,5,6,7
825 */
826static int cfq_get_next_prio_level(struct cfq_data *cfqd)
827{
828 int prio, wrap;
829
830 prio = -1;
831 wrap = 0;
832 do {
833 int p;
834
835 for (p = cfqd->cur_prio; p <= cfqd->cur_end_prio; p++) {
836 if (!list_empty(&cfqd->rr_list[p])) {
837 prio = p;
838 break;
839 }
840 }
841
842 if (prio != -1)
843 break;
844 cfqd->cur_prio = 0;
845 if (++cfqd->cur_end_prio == CFQ_PRIO_LISTS) {
846 cfqd->cur_end_prio = 0;
847 if (wrap)
848 break;
849 wrap = 1;
850 }
851 } while (1);
852
853 if (unlikely(prio == -1))
854 return -1;
855
856 BUG_ON(prio >= CFQ_PRIO_LISTS);
857
858 list_splice_init(&cfqd->rr_list[prio], &cfqd->cur_rr);
859
860 cfqd->cur_prio = prio + 1;
861 if (cfqd->cur_prio > cfqd->cur_end_prio) {
862 cfqd->cur_end_prio = cfqd->cur_prio;
863 cfqd->cur_prio = 0;
864 }
865 if (cfqd->cur_end_prio == CFQ_PRIO_LISTS) {
866 cfqd->cur_prio = 0;
867 cfqd->cur_end_prio = 0;
868 }
869
870 return prio;
871}
872
Jens Axboe3b181522005-06-27 10:56:24 +0200873static struct cfq_queue *cfq_set_active_queue(struct cfq_data *cfqd)
Jens Axboe22e2c502005-06-27 10:55:12 +0200874{
Jens Axboe7b14e3b2006-02-28 09:35:11 +0100875 struct cfq_queue *cfqq = NULL;
Jens Axboe22e2c502005-06-27 10:55:12 +0200876
877 /*
878 * if current list is non-empty, grab first entry. if it is empty,
879 * get next prio level and grab first entry then if any are spliced
880 */
881 if (!list_empty(&cfqd->cur_rr) || cfq_get_next_prio_level(cfqd) != -1)
882 cfqq = list_entry_cfqq(cfqd->cur_rr.next);
883
884 /*
Jens Axboee0de0202006-06-01 10:07:26 +0200885 * If no new queues are available, check if the busy list has some
886 * before falling back to idle io.
887 */
888 if (!cfqq && !list_empty(&cfqd->busy_rr))
889 cfqq = list_entry_cfqq(cfqd->busy_rr.next);
890
891 /*
Jens Axboe22e2c502005-06-27 10:55:12 +0200892 * if we have idle queues and no rt or be queues had pending
893 * requests, either allow immediate service if the grace period
894 * has passed or arm the idle grace timer
895 */
896 if (!cfqq && !list_empty(&cfqd->idle_rr)) {
897 unsigned long end = cfqd->last_end_request + CFQ_IDLE_GRACE;
898
899 if (time_after_eq(jiffies, end))
900 cfqq = list_entry_cfqq(cfqd->idle_rr.next);
901 else
902 mod_timer(&cfqd->idle_class_timer, end);
903 }
904
905 __cfq_set_active_queue(cfqd, cfqq);
Jens Axboe3b181522005-06-27 10:56:24 +0200906 return cfqq;
Jens Axboe22e2c502005-06-27 10:55:12 +0200907}
908
Jens Axboe22e2c502005-06-27 10:55:12 +0200909static int cfq_arm_slice_timer(struct cfq_data *cfqd, struct cfq_queue *cfqq)
910
911{
Jens Axboe206dc692006-03-28 13:03:44 +0200912 struct cfq_io_context *cic;
Jens Axboe7b14e3b2006-02-28 09:35:11 +0100913 unsigned long sl;
914
Jens Axboe22e2c502005-06-27 10:55:12 +0200915 WARN_ON(!RB_EMPTY(&cfqq->sort_list));
916 WARN_ON(cfqq != cfqd->active_queue);
917
918 /*
919 * idle is disabled, either manually or by past process history
920 */
921 if (!cfqd->cfq_slice_idle)
922 return 0;
Jens Axboe3b181522005-06-27 10:56:24 +0200923 if (!cfq_cfqq_idle_window(cfqq))
Jens Axboe22e2c502005-06-27 10:55:12 +0200924 return 0;
925 /*
926 * task has exited, don't wait
927 */
Jens Axboe206dc692006-03-28 13:03:44 +0200928 cic = cfqd->active_cic;
929 if (!cic || !cic->ioc->task)
Jens Axboe22e2c502005-06-27 10:55:12 +0200930 return 0;
931
Jens Axboe3b181522005-06-27 10:56:24 +0200932 cfq_mark_cfqq_must_dispatch(cfqq);
933 cfq_mark_cfqq_wait_request(cfqq);
Jens Axboe22e2c502005-06-27 10:55:12 +0200934
Jens Axboe7b14e3b2006-02-28 09:35:11 +0100935 sl = min(cfqq->slice_end - 1, (unsigned long) cfqd->cfq_slice_idle);
Jens Axboe206dc692006-03-28 13:03:44 +0200936
937 /*
938 * we don't want to idle for seeks, but we do want to allow
939 * fair distribution of slice time for a process doing back-to-back
940 * seeks. so allow a little bit of time for him to submit a new rq
941 */
942 if (sample_valid(cic->seek_samples) && cic->seek_mean > 131072)
943 sl = 2;
944
Jens Axboe7b14e3b2006-02-28 09:35:11 +0100945 mod_timer(&cfqd->idle_slice_timer, jiffies + sl);
Jens Axboe22e2c502005-06-27 10:55:12 +0200946 return 1;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700947}
948
Jens Axboeb4878f22005-10-20 16:42:29 +0200949static void cfq_dispatch_insert(request_queue_t *q, struct cfq_rq *crq)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700950{
951 struct cfq_data *cfqd = q->elevator->elevator_data;
952 struct cfq_queue *cfqq = crq->cfq_queue;
Jens Axboe22e2c502005-06-27 10:55:12 +0200953
954 cfqq->next_crq = cfq_find_next_crq(cfqd, cfqq, crq);
Jens Axboeb4878f22005-10-20 16:42:29 +0200955 cfq_remove_request(crq->request);
Jens Axboe3b181522005-06-27 10:56:24 +0200956 cfqq->on_dispatch[cfq_crq_is_sync(crq)]++;
Jens Axboeb4878f22005-10-20 16:42:29 +0200957 elv_dispatch_sort(q, crq->request);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700958}
959
960/*
961 * return expired entry, or NULL to just start from scratch in rbtree
962 */
963static inline struct cfq_rq *cfq_check_fifo(struct cfq_queue *cfqq)
964{
965 struct cfq_data *cfqd = cfqq->cfqd;
Jens Axboe22e2c502005-06-27 10:55:12 +0200966 struct request *rq;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700967 struct cfq_rq *crq;
968
Jens Axboe3b181522005-06-27 10:56:24 +0200969 if (cfq_cfqq_fifo_expire(cfqq))
Linus Torvalds1da177e2005-04-16 15:20:36 -0700970 return NULL;
971
Jens Axboe22e2c502005-06-27 10:55:12 +0200972 if (!list_empty(&cfqq->fifo)) {
Jens Axboe3b181522005-06-27 10:56:24 +0200973 int fifo = cfq_cfqq_class_sync(cfqq);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700974
Jens Axboe22e2c502005-06-27 10:55:12 +0200975 crq = RQ_DATA(list_entry_fifo(cfqq->fifo.next));
976 rq = crq->request;
977 if (time_after(jiffies, rq->start_time + cfqd->cfq_fifo_expire[fifo])) {
Jens Axboe3b181522005-06-27 10:56:24 +0200978 cfq_mark_cfqq_fifo_expire(cfqq);
Jens Axboe22e2c502005-06-27 10:55:12 +0200979 return crq;
980 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700981 }
982
983 return NULL;
984}
985
986/*
Jens Axboe3b181522005-06-27 10:56:24 +0200987 * Scale schedule slice based on io priority. Use the sync time slice only
988 * if a queue is marked sync and has sync io queued. A sync queue with async
989 * io only, should not get full sync slice length.
Linus Torvalds1da177e2005-04-16 15:20:36 -0700990 */
Jens Axboe22e2c502005-06-27 10:55:12 +0200991static inline int
992cfq_prio_to_slice(struct cfq_data *cfqd, struct cfq_queue *cfqq)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700993{
Jens Axboe22e2c502005-06-27 10:55:12 +0200994 const int base_slice = cfqd->cfq_slice[cfq_cfqq_sync(cfqq)];
Linus Torvalds1da177e2005-04-16 15:20:36 -0700995
Jens Axboe22e2c502005-06-27 10:55:12 +0200996 WARN_ON(cfqq->ioprio >= IOPRIO_BE_NR);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700997
Jens Axboe22e2c502005-06-27 10:55:12 +0200998 return base_slice + (base_slice/CFQ_SLICE_SCALE * (4 - cfqq->ioprio));
Linus Torvalds1da177e2005-04-16 15:20:36 -0700999}
1000
Jens Axboe22e2c502005-06-27 10:55:12 +02001001static inline void
1002cfq_set_prio_slice(struct cfq_data *cfqd, struct cfq_queue *cfqq)
1003{
1004 cfqq->slice_end = cfq_prio_to_slice(cfqd, cfqq) + jiffies;
1005}
1006
1007static inline int
1008cfq_prio_to_maxrq(struct cfq_data *cfqd, struct cfq_queue *cfqq)
1009{
1010 const int base_rq = cfqd->cfq_slice_async_rq;
1011
1012 WARN_ON(cfqq->ioprio >= IOPRIO_BE_NR);
1013
1014 return 2 * (base_rq + base_rq * (CFQ_PRIO_LISTS - 1 - cfqq->ioprio));
1015}
1016
1017/*
1018 * get next queue for service
1019 */
Tejun Heo1b5ed5e12005-11-10 08:49:19 +01001020static struct cfq_queue *cfq_select_queue(struct cfq_data *cfqd)
Jens Axboe22e2c502005-06-27 10:55:12 +02001021{
1022 unsigned long now = jiffies;
1023 struct cfq_queue *cfqq;
1024
1025 cfqq = cfqd->active_queue;
1026 if (!cfqq)
1027 goto new_queue;
1028
1029 /*
1030 * slice has expired
1031 */
Jens Axboe3b181522005-06-27 10:56:24 +02001032 if (!cfq_cfqq_must_dispatch(cfqq) && time_after(now, cfqq->slice_end))
1033 goto expire;
Jens Axboe22e2c502005-06-27 10:55:12 +02001034
1035 /*
1036 * if queue has requests, dispatch one. if not, check if
1037 * enough slice is left to wait for one
1038 */
1039 if (!RB_EMPTY(&cfqq->sort_list))
1040 goto keep_queue;
Tejun Heo1b5ed5e12005-11-10 08:49:19 +01001041 else if (cfq_cfqq_class_sync(cfqq) &&
Jens Axboe22e2c502005-06-27 10:55:12 +02001042 time_before(now, cfqq->slice_end)) {
1043 if (cfq_arm_slice_timer(cfqd, cfqq))
1044 return NULL;
1045 }
1046
Jens Axboe3b181522005-06-27 10:56:24 +02001047expire:
Jens Axboe22e2c502005-06-27 10:55:12 +02001048 cfq_slice_expired(cfqd, 0);
Jens Axboe3b181522005-06-27 10:56:24 +02001049new_queue:
1050 cfqq = cfq_set_active_queue(cfqd);
Jens Axboe22e2c502005-06-27 10:55:12 +02001051keep_queue:
Jens Axboe3b181522005-06-27 10:56:24 +02001052 return cfqq;
Jens Axboe22e2c502005-06-27 10:55:12 +02001053}
1054
1055static int
1056__cfq_dispatch_requests(struct cfq_data *cfqd, struct cfq_queue *cfqq,
1057 int max_dispatch)
1058{
1059 int dispatched = 0;
1060
1061 BUG_ON(RB_EMPTY(&cfqq->sort_list));
1062
1063 do {
1064 struct cfq_rq *crq;
1065
1066 /*
1067 * follow expired path, else get first next available
1068 */
1069 if ((crq = cfq_check_fifo(cfqq)) == NULL)
1070 crq = cfqq->next_crq;
1071
1072 /*
1073 * finally, insert request into driver dispatch list
1074 */
Jens Axboeb4878f22005-10-20 16:42:29 +02001075 cfq_dispatch_insert(cfqd->queue, crq);
Jens Axboe22e2c502005-06-27 10:55:12 +02001076
1077 cfqd->dispatch_slice++;
1078 dispatched++;
1079
1080 if (!cfqd->active_cic) {
1081 atomic_inc(&crq->io_context->ioc->refcount);
1082 cfqd->active_cic = crq->io_context;
1083 }
1084
1085 if (RB_EMPTY(&cfqq->sort_list))
1086 break;
1087
1088 } while (dispatched < max_dispatch);
1089
1090 /*
1091 * if slice end isn't set yet, set it. if at least one request was
1092 * sync, use the sync time slice value
1093 */
1094 if (!cfqq->slice_end)
1095 cfq_set_prio_slice(cfqd, cfqq);
1096
1097 /*
1098 * expire an async queue immediately if it has used up its slice. idle
1099 * queue always expire after 1 dispatch round.
1100 */
1101 if ((!cfq_cfqq_sync(cfqq) &&
1102 cfqd->dispatch_slice >= cfq_prio_to_maxrq(cfqd, cfqq)) ||
1103 cfq_class_idle(cfqq))
1104 cfq_slice_expired(cfqd, 0);
1105
1106 return dispatched;
1107}
1108
1109static int
Tejun Heo1b5ed5e12005-11-10 08:49:19 +01001110cfq_forced_dispatch_cfqqs(struct list_head *list)
1111{
1112 int dispatched = 0;
1113 struct cfq_queue *cfqq, *next;
1114 struct cfq_rq *crq;
1115
1116 list_for_each_entry_safe(cfqq, next, list, cfq_list) {
1117 while ((crq = cfqq->next_crq)) {
1118 cfq_dispatch_insert(cfqq->cfqd->queue, crq);
1119 dispatched++;
1120 }
1121 BUG_ON(!list_empty(&cfqq->fifo));
1122 }
1123 return dispatched;
1124}
1125
1126static int
1127cfq_forced_dispatch(struct cfq_data *cfqd)
1128{
1129 int i, dispatched = 0;
1130
1131 for (i = 0; i < CFQ_PRIO_LISTS; i++)
1132 dispatched += cfq_forced_dispatch_cfqqs(&cfqd->rr_list[i]);
1133
1134 dispatched += cfq_forced_dispatch_cfqqs(&cfqd->busy_rr);
1135 dispatched += cfq_forced_dispatch_cfqqs(&cfqd->cur_rr);
1136 dispatched += cfq_forced_dispatch_cfqqs(&cfqd->idle_rr);
1137
1138 cfq_slice_expired(cfqd, 0);
1139
1140 BUG_ON(cfqd->busy_queues);
1141
1142 return dispatched;
1143}
1144
1145static int
Jens Axboeb4878f22005-10-20 16:42:29 +02001146cfq_dispatch_requests(request_queue_t *q, int force)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001147{
1148 struct cfq_data *cfqd = q->elevator->elevator_data;
1149 struct cfq_queue *cfqq;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001150
Jens Axboe22e2c502005-06-27 10:55:12 +02001151 if (!cfqd->busy_queues)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001152 return 0;
1153
Tejun Heo1b5ed5e12005-11-10 08:49:19 +01001154 if (unlikely(force))
1155 return cfq_forced_dispatch(cfqd);
1156
1157 cfqq = cfq_select_queue(cfqd);
Jens Axboe22e2c502005-06-27 10:55:12 +02001158 if (cfqq) {
Jens Axboeb4878f22005-10-20 16:42:29 +02001159 int max_dispatch;
1160
Jens Axboe3b181522005-06-27 10:56:24 +02001161 cfq_clear_cfqq_must_dispatch(cfqq);
1162 cfq_clear_cfqq_wait_request(cfqq);
Jens Axboe22e2c502005-06-27 10:55:12 +02001163 del_timer(&cfqd->idle_slice_timer);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001164
Tejun Heo1b5ed5e12005-11-10 08:49:19 +01001165 max_dispatch = cfqd->cfq_quantum;
1166 if (cfq_class_idle(cfqq))
1167 max_dispatch = 1;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001168
Jens Axboe22e2c502005-06-27 10:55:12 +02001169 return __cfq_dispatch_requests(cfqd, cfqq, max_dispatch);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001170 }
1171
Jens Axboe22e2c502005-06-27 10:55:12 +02001172 return 0;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001173}
1174
Linus Torvalds1da177e2005-04-16 15:20:36 -07001175/*
1176 * task holds one reference to the queue, dropped when task exits. each crq
1177 * in-flight on this queue also holds a reference, dropped when crq is freed.
1178 *
1179 * queue lock must be held here.
1180 */
1181static void cfq_put_queue(struct cfq_queue *cfqq)
1182{
Jens Axboe22e2c502005-06-27 10:55:12 +02001183 struct cfq_data *cfqd = cfqq->cfqd;
1184
1185 BUG_ON(atomic_read(&cfqq->ref) <= 0);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001186
1187 if (!atomic_dec_and_test(&cfqq->ref))
1188 return;
1189
1190 BUG_ON(rb_first(&cfqq->sort_list));
Jens Axboe22e2c502005-06-27 10:55:12 +02001191 BUG_ON(cfqq->allocated[READ] + cfqq->allocated[WRITE]);
Jens Axboe3b181522005-06-27 10:56:24 +02001192 BUG_ON(cfq_cfqq_on_rr(cfqq));
Linus Torvalds1da177e2005-04-16 15:20:36 -07001193
Jens Axboe7b14e3b2006-02-28 09:35:11 +01001194 if (unlikely(cfqd->active_queue == cfqq))
Jens Axboe3b181522005-06-27 10:56:24 +02001195 __cfq_slice_expired(cfqd, cfqq, 0);
Jens Axboe22e2c502005-06-27 10:55:12 +02001196
Linus Torvalds1da177e2005-04-16 15:20:36 -07001197 /*
1198 * it's on the empty list and still hashed
1199 */
1200 list_del(&cfqq->cfq_list);
1201 hlist_del(&cfqq->cfq_hash);
1202 kmem_cache_free(cfq_pool, cfqq);
1203}
1204
1205static inline struct cfq_queue *
Jens Axboe3b181522005-06-27 10:56:24 +02001206__cfq_find_cfq_hash(struct cfq_data *cfqd, unsigned int key, unsigned int prio,
1207 const int hashval)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001208{
1209 struct hlist_head *hash_list = &cfqd->cfq_hash[hashval];
Jens Axboe206dc692006-03-28 13:03:44 +02001210 struct hlist_node *entry;
1211 struct cfq_queue *__cfqq;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001212
Jens Axboe206dc692006-03-28 13:03:44 +02001213 hlist_for_each_entry(__cfqq, entry, hash_list, cfq_hash) {
Al Virob0a69162006-03-14 15:32:50 -05001214 const unsigned short __p = IOPRIO_PRIO_VALUE(__cfqq->org_ioprio_class, __cfqq->org_ioprio);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001215
Jens Axboe206dc692006-03-28 13:03:44 +02001216 if (__cfqq->key == key && (__p == prio || !prio))
Linus Torvalds1da177e2005-04-16 15:20:36 -07001217 return __cfqq;
1218 }
1219
1220 return NULL;
1221}
1222
1223static struct cfq_queue *
Jens Axboe3b181522005-06-27 10:56:24 +02001224cfq_find_cfq_hash(struct cfq_data *cfqd, unsigned int key, unsigned short prio)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001225{
Jens Axboe3b181522005-06-27 10:56:24 +02001226 return __cfq_find_cfq_hash(cfqd, key, prio, hash_long(key, CFQ_QHASH_SHIFT));
Linus Torvalds1da177e2005-04-16 15:20:36 -07001227}
1228
Jens Axboee2d74ac2006-03-28 08:59:01 +02001229static void cfq_free_io_context(struct io_context *ioc)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001230{
Jens Axboe22e2c502005-06-27 10:55:12 +02001231 struct cfq_io_context *__cic;
Jens Axboee2d74ac2006-03-28 08:59:01 +02001232 struct rb_node *n;
1233 int freed = 0;
Jens Axboe22e2c502005-06-27 10:55:12 +02001234
Jens Axboee2d74ac2006-03-28 08:59:01 +02001235 while ((n = rb_first(&ioc->cic_root)) != NULL) {
1236 __cic = rb_entry(n, struct cfq_io_context, rb_node);
1237 rb_erase(&__cic->rb_node, &ioc->cic_root);
Jens Axboe22e2c502005-06-27 10:55:12 +02001238 kmem_cache_free(cfq_ioc_pool, __cic);
Al Viro334e94d2006-03-18 15:05:53 -05001239 freed++;
Jens Axboe22e2c502005-06-27 10:55:12 +02001240 }
1241
Al Viro334e94d2006-03-18 15:05:53 -05001242 if (atomic_sub_and_test(freed, &ioc_count) && ioc_gone)
1243 complete(ioc_gone);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001244}
1245
Al Viroe17a9482006-03-18 13:21:20 -05001246static void cfq_trim(struct io_context *ioc)
1247{
1248 ioc->set_ioprio = NULL;
Jens Axboee2d74ac2006-03-28 08:59:01 +02001249 cfq_free_io_context(ioc);
Al Viroe17a9482006-03-18 13:21:20 -05001250}
1251
Linus Torvalds1da177e2005-04-16 15:20:36 -07001252/*
Jens Axboe22e2c502005-06-27 10:55:12 +02001253 * Called with interrupts disabled
1254 */
1255static void cfq_exit_single_io_context(struct cfq_io_context *cic)
1256{
Al Viro478a82b2006-03-18 13:25:24 -05001257 struct cfq_data *cfqd = cic->key;
Al Virod9ff4182006-03-18 13:51:22 -05001258 request_queue_t *q;
1259
1260 if (!cfqd)
1261 return;
1262
1263 q = cfqd->queue;
Jens Axboe22e2c502005-06-27 10:55:12 +02001264
1265 WARN_ON(!irqs_disabled());
1266
1267 spin_lock(q->queue_lock);
1268
Al Viro12a05732006-03-18 13:38:01 -05001269 if (cic->cfqq[ASYNC]) {
1270 if (unlikely(cic->cfqq[ASYNC] == cfqd->active_queue))
1271 __cfq_slice_expired(cfqd, cic->cfqq[ASYNC], 0);
1272 cfq_put_queue(cic->cfqq[ASYNC]);
1273 cic->cfqq[ASYNC] = NULL;
1274 }
Jens Axboe22e2c502005-06-27 10:55:12 +02001275
Al Viro12a05732006-03-18 13:38:01 -05001276 if (cic->cfqq[SYNC]) {
1277 if (unlikely(cic->cfqq[SYNC] == cfqd->active_queue))
1278 __cfq_slice_expired(cfqd, cic->cfqq[SYNC], 0);
1279 cfq_put_queue(cic->cfqq[SYNC]);
1280 cic->cfqq[SYNC] = NULL;
1281 }
1282
Al Viro478a82b2006-03-18 13:25:24 -05001283 cic->key = NULL;
Al Virod9ff4182006-03-18 13:51:22 -05001284 list_del_init(&cic->queue_list);
Jens Axboe22e2c502005-06-27 10:55:12 +02001285 spin_unlock(q->queue_lock);
1286}
1287
Jens Axboee2d74ac2006-03-28 08:59:01 +02001288static void cfq_exit_io_context(struct io_context *ioc)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001289{
Jens Axboe22e2c502005-06-27 10:55:12 +02001290 struct cfq_io_context *__cic;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001291 unsigned long flags;
Jens Axboee2d74ac2006-03-28 08:59:01 +02001292 struct rb_node *n;
Jens Axboe22e2c502005-06-27 10:55:12 +02001293
Linus Torvalds1da177e2005-04-16 15:20:36 -07001294 /*
1295 * put the reference this task is holding to the various queues
1296 */
Jens Axboe3793c652006-05-30 21:11:04 +02001297 spin_lock_irqsave(&cfq_exit_lock, flags);
Jens Axboee2d74ac2006-03-28 08:59:01 +02001298
1299 n = rb_first(&ioc->cic_root);
1300 while (n != NULL) {
1301 __cic = rb_entry(n, struct cfq_io_context, rb_node);
1302
Jens Axboe22e2c502005-06-27 10:55:12 +02001303 cfq_exit_single_io_context(__cic);
Jens Axboee2d74ac2006-03-28 08:59:01 +02001304 n = rb_next(n);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001305 }
1306
Jens Axboe3793c652006-05-30 21:11:04 +02001307 spin_unlock_irqrestore(&cfq_exit_lock, flags);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001308}
1309
Jens Axboe22e2c502005-06-27 10:55:12 +02001310static struct cfq_io_context *
Al Viro8267e262005-10-21 03:20:53 -04001311cfq_alloc_io_context(struct cfq_data *cfqd, gfp_t gfp_mask)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001312{
Jens Axboe22e2c502005-06-27 10:55:12 +02001313 struct cfq_io_context *cic = kmem_cache_alloc(cfq_ioc_pool, gfp_mask);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001314
1315 if (cic) {
Jens Axboe553698f2006-06-14 19:11:57 +02001316 memset(cic, 0, sizeof(*cic));
Jens Axboe22e2c502005-06-27 10:55:12 +02001317 cic->last_end_request = jiffies;
Jens Axboe553698f2006-06-14 19:11:57 +02001318 INIT_LIST_HEAD(&cic->queue_list);
Jens Axboe22e2c502005-06-27 10:55:12 +02001319 cic->dtor = cfq_free_io_context;
1320 cic->exit = cfq_exit_io_context;
Al Viro334e94d2006-03-18 15:05:53 -05001321 atomic_inc(&ioc_count);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001322 }
1323
1324 return cic;
1325}
1326
Jens Axboe22e2c502005-06-27 10:55:12 +02001327static void cfq_init_prio_data(struct cfq_queue *cfqq)
1328{
1329 struct task_struct *tsk = current;
1330 int ioprio_class;
1331
Jens Axboe3b181522005-06-27 10:56:24 +02001332 if (!cfq_cfqq_prio_changed(cfqq))
Jens Axboe22e2c502005-06-27 10:55:12 +02001333 return;
1334
1335 ioprio_class = IOPRIO_PRIO_CLASS(tsk->ioprio);
1336 switch (ioprio_class) {
1337 default:
1338 printk(KERN_ERR "cfq: bad prio %x\n", ioprio_class);
1339 case IOPRIO_CLASS_NONE:
1340 /*
1341 * no prio set, place us in the middle of the BE classes
1342 */
1343 cfqq->ioprio = task_nice_ioprio(tsk);
1344 cfqq->ioprio_class = IOPRIO_CLASS_BE;
1345 break;
1346 case IOPRIO_CLASS_RT:
1347 cfqq->ioprio = task_ioprio(tsk);
1348 cfqq->ioprio_class = IOPRIO_CLASS_RT;
1349 break;
1350 case IOPRIO_CLASS_BE:
1351 cfqq->ioprio = task_ioprio(tsk);
1352 cfqq->ioprio_class = IOPRIO_CLASS_BE;
1353 break;
1354 case IOPRIO_CLASS_IDLE:
1355 cfqq->ioprio_class = IOPRIO_CLASS_IDLE;
1356 cfqq->ioprio = 7;
Jens Axboe3b181522005-06-27 10:56:24 +02001357 cfq_clear_cfqq_idle_window(cfqq);
Jens Axboe22e2c502005-06-27 10:55:12 +02001358 break;
1359 }
1360
1361 /*
1362 * keep track of original prio settings in case we have to temporarily
1363 * elevate the priority of this queue
1364 */
1365 cfqq->org_ioprio = cfqq->ioprio;
1366 cfqq->org_ioprio_class = cfqq->ioprio_class;
1367
Jens Axboe3b181522005-06-27 10:56:24 +02001368 if (cfq_cfqq_on_rr(cfqq))
Jens Axboe22e2c502005-06-27 10:55:12 +02001369 cfq_resort_rr_list(cfqq, 0);
1370
Jens Axboe3b181522005-06-27 10:56:24 +02001371 cfq_clear_cfqq_prio_changed(cfqq);
Jens Axboe22e2c502005-06-27 10:55:12 +02001372}
1373
Al Viro478a82b2006-03-18 13:25:24 -05001374static inline void changed_ioprio(struct cfq_io_context *cic)
Jens Axboe22e2c502005-06-27 10:55:12 +02001375{
Al Viro478a82b2006-03-18 13:25:24 -05001376 struct cfq_data *cfqd = cic->key;
1377 struct cfq_queue *cfqq;
1378 if (cfqd) {
Jens Axboe22e2c502005-06-27 10:55:12 +02001379 spin_lock(cfqd->queue->queue_lock);
Al Viro12a05732006-03-18 13:38:01 -05001380 cfqq = cic->cfqq[ASYNC];
1381 if (cfqq) {
Al Viro6f325a12006-03-18 14:58:37 -05001382 struct cfq_queue *new_cfqq;
1383 new_cfqq = cfq_get_queue(cfqd, CFQ_KEY_ASYNC,
1384 cic->ioc->task, GFP_ATOMIC);
1385 if (new_cfqq) {
1386 cic->cfqq[ASYNC] = new_cfqq;
1387 cfq_put_queue(cfqq);
1388 }
Al Viro12a05732006-03-18 13:38:01 -05001389 }
1390 cfqq = cic->cfqq[SYNC];
Al Viro478a82b2006-03-18 13:25:24 -05001391 if (cfqq) {
1392 cfq_mark_cfqq_prio_changed(cfqq);
1393 cfq_init_prio_data(cfqq);
1394 }
Jens Axboe22e2c502005-06-27 10:55:12 +02001395 spin_unlock(cfqd->queue->queue_lock);
1396 }
1397}
1398
Linus Torvalds1da177e2005-04-16 15:20:36 -07001399/*
Jens Axboe22e2c502005-06-27 10:55:12 +02001400 * callback from sys_ioprio_set, irqs are disabled
Linus Torvalds1da177e2005-04-16 15:20:36 -07001401 */
Jens Axboe22e2c502005-06-27 10:55:12 +02001402static int cfq_ioc_set_ioprio(struct io_context *ioc, unsigned int ioprio)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001403{
Al Viroa6a07632006-03-18 13:26:44 -05001404 struct cfq_io_context *cic;
Jens Axboee2d74ac2006-03-28 08:59:01 +02001405 struct rb_node *n;
Al Viroa6a07632006-03-18 13:26:44 -05001406
Jens Axboe3793c652006-05-30 21:11:04 +02001407 spin_lock(&cfq_exit_lock);
Al Viroa6a07632006-03-18 13:26:44 -05001408
Jens Axboee2d74ac2006-03-28 08:59:01 +02001409 n = rb_first(&ioc->cic_root);
1410 while (n != NULL) {
1411 cic = rb_entry(n, struct cfq_io_context, rb_node);
Jens Axboe3793c652006-05-30 21:11:04 +02001412
Al Viro478a82b2006-03-18 13:25:24 -05001413 changed_ioprio(cic);
Jens Axboee2d74ac2006-03-28 08:59:01 +02001414 n = rb_next(n);
1415 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07001416
Jens Axboe3793c652006-05-30 21:11:04 +02001417 spin_unlock(&cfq_exit_lock);
Al Viroa6a07632006-03-18 13:26:44 -05001418
Jens Axboe22e2c502005-06-27 10:55:12 +02001419 return 0;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001420}
1421
1422static struct cfq_queue *
Al Viro6f325a12006-03-18 14:58:37 -05001423cfq_get_queue(struct cfq_data *cfqd, unsigned int key, struct task_struct *tsk,
Al Viro8267e262005-10-21 03:20:53 -04001424 gfp_t gfp_mask)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001425{
1426 const int hashval = hash_long(key, CFQ_QHASH_SHIFT);
1427 struct cfq_queue *cfqq, *new_cfqq = NULL;
Al Viro6f325a12006-03-18 14:58:37 -05001428 unsigned short ioprio;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001429
1430retry:
Al Viro6f325a12006-03-18 14:58:37 -05001431 ioprio = tsk->ioprio;
Jens Axboe3b181522005-06-27 10:56:24 +02001432 cfqq = __cfq_find_cfq_hash(cfqd, key, ioprio, hashval);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001433
1434 if (!cfqq) {
1435 if (new_cfqq) {
1436 cfqq = new_cfqq;
1437 new_cfqq = NULL;
Jens Axboe22e2c502005-06-27 10:55:12 +02001438 } else if (gfp_mask & __GFP_WAIT) {
Linus Torvalds1da177e2005-04-16 15:20:36 -07001439 spin_unlock_irq(cfqd->queue->queue_lock);
1440 new_cfqq = kmem_cache_alloc(cfq_pool, gfp_mask);
1441 spin_lock_irq(cfqd->queue->queue_lock);
1442 goto retry;
Jens Axboe22e2c502005-06-27 10:55:12 +02001443 } else {
1444 cfqq = kmem_cache_alloc(cfq_pool, gfp_mask);
1445 if (!cfqq)
1446 goto out;
Kiyoshi Ueda db3b5842005-06-17 16:15:10 +02001447 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07001448
1449 memset(cfqq, 0, sizeof(*cfqq));
1450
1451 INIT_HLIST_NODE(&cfqq->cfq_hash);
1452 INIT_LIST_HEAD(&cfqq->cfq_list);
1453 RB_CLEAR_ROOT(&cfqq->sort_list);
Jens Axboe22e2c502005-06-27 10:55:12 +02001454 INIT_LIST_HEAD(&cfqq->fifo);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001455
1456 cfqq->key = key;
1457 hlist_add_head(&cfqq->cfq_hash, &cfqd->cfq_hash[hashval]);
1458 atomic_set(&cfqq->ref, 0);
1459 cfqq->cfqd = cfqd;
Jens Axboe22e2c502005-06-27 10:55:12 +02001460 cfqq->service_last = 0;
1461 /*
1462 * set ->slice_left to allow preemption for a new process
1463 */
1464 cfqq->slice_left = 2 * cfqd->cfq_slice_idle;
Jens Axboe25776e32006-06-01 10:12:26 +02001465 if (!cfqd->hw_tag)
1466 cfq_mark_cfqq_idle_window(cfqq);
Jens Axboe3b181522005-06-27 10:56:24 +02001467 cfq_mark_cfqq_prio_changed(cfqq);
1468 cfq_init_prio_data(cfqq);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001469 }
1470
1471 if (new_cfqq)
1472 kmem_cache_free(cfq_pool, new_cfqq);
1473
1474 atomic_inc(&cfqq->ref);
1475out:
1476 WARN_ON((gfp_mask & __GFP_WAIT) && !cfqq);
1477 return cfqq;
1478}
1479
OGAWA Hirofumidbecf3a2006-04-18 09:45:18 +02001480static void
1481cfq_drop_dead_cic(struct io_context *ioc, struct cfq_io_context *cic)
1482{
Jens Axboe3793c652006-05-30 21:11:04 +02001483 spin_lock(&cfq_exit_lock);
OGAWA Hirofumidbecf3a2006-04-18 09:45:18 +02001484 rb_erase(&cic->rb_node, &ioc->cic_root);
Jens Axboe3793c652006-05-30 21:11:04 +02001485 list_del_init(&cic->queue_list);
1486 spin_unlock(&cfq_exit_lock);
OGAWA Hirofumidbecf3a2006-04-18 09:45:18 +02001487 kmem_cache_free(cfq_ioc_pool, cic);
1488 atomic_dec(&ioc_count);
1489}
1490
Jens Axboee2d74ac2006-03-28 08:59:01 +02001491static struct cfq_io_context *
1492cfq_cic_rb_lookup(struct cfq_data *cfqd, struct io_context *ioc)
1493{
OGAWA Hirofumidbecf3a2006-04-18 09:45:18 +02001494 struct rb_node *n;
Jens Axboee2d74ac2006-03-28 08:59:01 +02001495 struct cfq_io_context *cic;
OGAWA Hirofumibe3b0752006-04-18 19:18:31 +02001496 void *k, *key = cfqd;
Jens Axboee2d74ac2006-03-28 08:59:01 +02001497
OGAWA Hirofumidbecf3a2006-04-18 09:45:18 +02001498restart:
1499 n = ioc->cic_root.rb_node;
Jens Axboee2d74ac2006-03-28 08:59:01 +02001500 while (n) {
1501 cic = rb_entry(n, struct cfq_io_context, rb_node);
OGAWA Hirofumibe3b0752006-04-18 19:18:31 +02001502 /* ->key must be copied to avoid race with cfq_exit_queue() */
1503 k = cic->key;
1504 if (unlikely(!k)) {
OGAWA Hirofumidbecf3a2006-04-18 09:45:18 +02001505 cfq_drop_dead_cic(ioc, cic);
1506 goto restart;
1507 }
Jens Axboee2d74ac2006-03-28 08:59:01 +02001508
OGAWA Hirofumibe3b0752006-04-18 19:18:31 +02001509 if (key < k)
Jens Axboee2d74ac2006-03-28 08:59:01 +02001510 n = n->rb_left;
OGAWA Hirofumibe3b0752006-04-18 19:18:31 +02001511 else if (key > k)
Jens Axboee2d74ac2006-03-28 08:59:01 +02001512 n = n->rb_right;
1513 else
1514 return cic;
1515 }
1516
1517 return NULL;
1518}
1519
1520static inline void
1521cfq_cic_link(struct cfq_data *cfqd, struct io_context *ioc,
1522 struct cfq_io_context *cic)
1523{
OGAWA Hirofumidbecf3a2006-04-18 09:45:18 +02001524 struct rb_node **p;
1525 struct rb_node *parent;
Jens Axboee2d74ac2006-03-28 08:59:01 +02001526 struct cfq_io_context *__cic;
OGAWA Hirofumibe3b0752006-04-18 19:18:31 +02001527 void *k;
Jens Axboee2d74ac2006-03-28 08:59:01 +02001528
Jens Axboee2d74ac2006-03-28 08:59:01 +02001529 cic->ioc = ioc;
1530 cic->key = cfqd;
1531
1532 ioc->set_ioprio = cfq_ioc_set_ioprio;
OGAWA Hirofumidbecf3a2006-04-18 09:45:18 +02001533restart:
1534 parent = NULL;
1535 p = &ioc->cic_root.rb_node;
Jens Axboee2d74ac2006-03-28 08:59:01 +02001536 while (*p) {
1537 parent = *p;
1538 __cic = rb_entry(parent, struct cfq_io_context, rb_node);
OGAWA Hirofumibe3b0752006-04-18 19:18:31 +02001539 /* ->key must be copied to avoid race with cfq_exit_queue() */
1540 k = __cic->key;
1541 if (unlikely(!k)) {
OGAWA Hirofumidbecf3a2006-04-18 09:45:18 +02001542 cfq_drop_dead_cic(ioc, cic);
1543 goto restart;
1544 }
Jens Axboee2d74ac2006-03-28 08:59:01 +02001545
OGAWA Hirofumibe3b0752006-04-18 19:18:31 +02001546 if (cic->key < k)
Jens Axboee2d74ac2006-03-28 08:59:01 +02001547 p = &(*p)->rb_left;
OGAWA Hirofumibe3b0752006-04-18 19:18:31 +02001548 else if (cic->key > k)
Jens Axboee2d74ac2006-03-28 08:59:01 +02001549 p = &(*p)->rb_right;
1550 else
1551 BUG();
1552 }
1553
Jens Axboe3793c652006-05-30 21:11:04 +02001554 spin_lock(&cfq_exit_lock);
Jens Axboee2d74ac2006-03-28 08:59:01 +02001555 rb_link_node(&cic->rb_node, parent, p);
1556 rb_insert_color(&cic->rb_node, &ioc->cic_root);
1557 list_add(&cic->queue_list, &cfqd->cic_list);
Jens Axboe3793c652006-05-30 21:11:04 +02001558 spin_unlock(&cfq_exit_lock);
Jens Axboee2d74ac2006-03-28 08:59:01 +02001559}
1560
Jens Axboe22e2c502005-06-27 10:55:12 +02001561/*
1562 * Setup general io context and cfq io context. There can be several cfq
1563 * io contexts per general io context, if this process is doing io to more
Jens Axboee2d74ac2006-03-28 08:59:01 +02001564 * than one device managed by cfq.
Jens Axboe22e2c502005-06-27 10:55:12 +02001565 */
1566static struct cfq_io_context *
Jens Axboee2d74ac2006-03-28 08:59:01 +02001567cfq_get_io_context(struct cfq_data *cfqd, gfp_t gfp_mask)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001568{
Jens Axboe22e2c502005-06-27 10:55:12 +02001569 struct io_context *ioc = NULL;
1570 struct cfq_io_context *cic;
1571
1572 might_sleep_if(gfp_mask & __GFP_WAIT);
1573
1574 ioc = get_io_context(gfp_mask);
1575 if (!ioc)
1576 return NULL;
1577
Jens Axboee2d74ac2006-03-28 08:59:01 +02001578 cic = cfq_cic_rb_lookup(cfqd, ioc);
1579 if (cic)
1580 goto out;
Jens Axboe22e2c502005-06-27 10:55:12 +02001581
Jens Axboee2d74ac2006-03-28 08:59:01 +02001582 cic = cfq_alloc_io_context(cfqd, gfp_mask);
1583 if (cic == NULL)
1584 goto err;
Jens Axboe22e2c502005-06-27 10:55:12 +02001585
Jens Axboee2d74ac2006-03-28 08:59:01 +02001586 cfq_cic_link(cfqd, ioc, cic);
Jens Axboe22e2c502005-06-27 10:55:12 +02001587out:
1588 return cic;
1589err:
1590 put_io_context(ioc);
1591 return NULL;
1592}
1593
1594static void
1595cfq_update_io_thinktime(struct cfq_data *cfqd, struct cfq_io_context *cic)
1596{
1597 unsigned long elapsed, ttime;
1598
1599 /*
1600 * if this context already has stuff queued, thinktime is from
1601 * last queue not last end
1602 */
1603#if 0
1604 if (time_after(cic->last_end_request, cic->last_queue))
1605 elapsed = jiffies - cic->last_end_request;
1606 else
1607 elapsed = jiffies - cic->last_queue;
1608#else
1609 elapsed = jiffies - cic->last_end_request;
1610#endif
1611
1612 ttime = min(elapsed, 2UL * cfqd->cfq_slice_idle);
1613
1614 cic->ttime_samples = (7*cic->ttime_samples + 256) / 8;
1615 cic->ttime_total = (7*cic->ttime_total + 256*ttime) / 8;
1616 cic->ttime_mean = (cic->ttime_total + 128) / cic->ttime_samples;
1617}
1618
Jens Axboe206dc692006-03-28 13:03:44 +02001619static void
1620cfq_update_io_seektime(struct cfq_data *cfqd, struct cfq_io_context *cic,
1621 struct cfq_rq *crq)
1622{
1623 sector_t sdist;
1624 u64 total;
1625
1626 if (cic->last_request_pos < crq->request->sector)
1627 sdist = crq->request->sector - cic->last_request_pos;
1628 else
1629 sdist = cic->last_request_pos - crq->request->sector;
1630
1631 /*
1632 * Don't allow the seek distance to get too large from the
1633 * odd fragment, pagein, etc
1634 */
1635 if (cic->seek_samples <= 60) /* second&third seek */
1636 sdist = min(sdist, (cic->seek_mean * 4) + 2*1024*1024);
1637 else
1638 sdist = min(sdist, (cic->seek_mean * 4) + 2*1024*64);
1639
1640 cic->seek_samples = (7*cic->seek_samples + 256) / 8;
1641 cic->seek_total = (7*cic->seek_total + (u64)256*sdist) / 8;
1642 total = cic->seek_total + (cic->seek_samples/2);
1643 do_div(total, cic->seek_samples);
1644 cic->seek_mean = (sector_t)total;
1645}
Jens Axboe22e2c502005-06-27 10:55:12 +02001646
1647/*
1648 * Disable idle window if the process thinks too long or seeks so much that
1649 * it doesn't matter
1650 */
1651static void
1652cfq_update_idle_window(struct cfq_data *cfqd, struct cfq_queue *cfqq,
1653 struct cfq_io_context *cic)
1654{
Jens Axboe3b181522005-06-27 10:56:24 +02001655 int enable_idle = cfq_cfqq_idle_window(cfqq);
Jens Axboe22e2c502005-06-27 10:55:12 +02001656
Jens Axboe25776e32006-06-01 10:12:26 +02001657 if (!cic->ioc->task || !cfqd->cfq_slice_idle || cfqd->hw_tag)
Jens Axboe22e2c502005-06-27 10:55:12 +02001658 enable_idle = 0;
1659 else if (sample_valid(cic->ttime_samples)) {
1660 if (cic->ttime_mean > cfqd->cfq_slice_idle)
1661 enable_idle = 0;
1662 else
1663 enable_idle = 1;
1664 }
1665
Jens Axboe3b181522005-06-27 10:56:24 +02001666 if (enable_idle)
1667 cfq_mark_cfqq_idle_window(cfqq);
1668 else
1669 cfq_clear_cfqq_idle_window(cfqq);
Jens Axboe22e2c502005-06-27 10:55:12 +02001670}
1671
1672
1673/*
1674 * Check if new_cfqq should preempt the currently active queue. Return 0 for
1675 * no or if we aren't sure, a 1 will cause a preempt.
1676 */
1677static int
1678cfq_should_preempt(struct cfq_data *cfqd, struct cfq_queue *new_cfqq,
1679 struct cfq_rq *crq)
1680{
1681 struct cfq_queue *cfqq = cfqd->active_queue;
1682
1683 if (cfq_class_idle(new_cfqq))
1684 return 0;
1685
1686 if (!cfqq)
1687 return 1;
1688
1689 if (cfq_class_idle(cfqq))
1690 return 1;
Jens Axboe3b181522005-06-27 10:56:24 +02001691 if (!cfq_cfqq_wait_request(new_cfqq))
Jens Axboe22e2c502005-06-27 10:55:12 +02001692 return 0;
1693 /*
1694 * if it doesn't have slice left, forget it
1695 */
1696 if (new_cfqq->slice_left < cfqd->cfq_slice_idle)
1697 return 0;
Jens Axboe3b181522005-06-27 10:56:24 +02001698 if (cfq_crq_is_sync(crq) && !cfq_cfqq_sync(cfqq))
Jens Axboe22e2c502005-06-27 10:55:12 +02001699 return 1;
1700
1701 return 0;
1702}
1703
1704/*
1705 * cfqq preempts the active queue. if we allowed preempt with no slice left,
1706 * let it have half of its nominal slice.
1707 */
1708static void cfq_preempt_queue(struct cfq_data *cfqd, struct cfq_queue *cfqq)
1709{
1710 struct cfq_queue *__cfqq, *next;
1711
1712 list_for_each_entry_safe(__cfqq, next, &cfqd->cur_rr, cfq_list)
1713 cfq_resort_rr_list(__cfqq, 1);
1714
1715 if (!cfqq->slice_left)
1716 cfqq->slice_left = cfq_prio_to_slice(cfqd, cfqq) / 2;
1717
1718 cfqq->slice_end = cfqq->slice_left + jiffies;
Jens Axboe3b181522005-06-27 10:56:24 +02001719 __cfq_slice_expired(cfqd, cfqq, 1);
Jens Axboe22e2c502005-06-27 10:55:12 +02001720 __cfq_set_active_queue(cfqd, cfqq);
1721}
1722
1723/*
1724 * should really be a ll_rw_blk.c helper
1725 */
1726static void cfq_start_queueing(struct cfq_data *cfqd, struct cfq_queue *cfqq)
1727{
1728 request_queue_t *q = cfqd->queue;
1729
1730 if (!blk_queue_plugged(q))
1731 q->request_fn(q);
1732 else
1733 __generic_unplug_device(q);
1734}
1735
1736/*
1737 * Called when a new fs request (crq) is added (to cfqq). Check if there's
1738 * something we should do about it
1739 */
1740static void
1741cfq_crq_enqueued(struct cfq_data *cfqd, struct cfq_queue *cfqq,
1742 struct cfq_rq *crq)
1743{
Jens Axboe9c2c38a2005-08-24 14:57:54 +02001744 struct cfq_io_context *cic;
Jens Axboe22e2c502005-06-27 10:55:12 +02001745
1746 cfqq->next_crq = cfq_choose_req(cfqd, cfqq->next_crq, crq);
1747
Jens Axboe12e9fdd2006-06-01 10:09:56 +02001748 cic = crq->io_context;
1749
Jens Axboe9c2c38a2005-08-24 14:57:54 +02001750 /*
1751 * we never wait for an async request and we don't allow preemption
1752 * of an async request. so just return early
1753 */
Jens Axboe12e9fdd2006-06-01 10:09:56 +02001754 if (!cfq_crq_is_sync(crq)) {
1755 /*
1756 * sync process issued an async request, if it's waiting
1757 * then expire it and kick rq handling.
1758 */
1759 if (cic == cfqd->active_cic &&
1760 del_timer(&cfqd->idle_slice_timer)) {
1761 cfq_slice_expired(cfqd, 0);
1762 cfq_start_queueing(cfqd, cfqq);
1763 }
Jens Axboe9c2c38a2005-08-24 14:57:54 +02001764 return;
Jens Axboe12e9fdd2006-06-01 10:09:56 +02001765 }
Jens Axboe22e2c502005-06-27 10:55:12 +02001766
Jens Axboe9c2c38a2005-08-24 14:57:54 +02001767 cfq_update_io_thinktime(cfqd, cic);
Jens Axboe206dc692006-03-28 13:03:44 +02001768 cfq_update_io_seektime(cfqd, cic, crq);
Jens Axboe9c2c38a2005-08-24 14:57:54 +02001769 cfq_update_idle_window(cfqd, cfqq, cic);
1770
1771 cic->last_queue = jiffies;
Jens Axboe206dc692006-03-28 13:03:44 +02001772 cic->last_request_pos = crq->request->sector + crq->request->nr_sectors;
Jens Axboe22e2c502005-06-27 10:55:12 +02001773
1774 if (cfqq == cfqd->active_queue) {
1775 /*
1776 * if we are waiting for a request for this queue, let it rip
1777 * immediately and flag that we must not expire this queue
1778 * just now
1779 */
Jens Axboe3b181522005-06-27 10:56:24 +02001780 if (cfq_cfqq_wait_request(cfqq)) {
1781 cfq_mark_cfqq_must_dispatch(cfqq);
Jens Axboe22e2c502005-06-27 10:55:12 +02001782 del_timer(&cfqd->idle_slice_timer);
1783 cfq_start_queueing(cfqd, cfqq);
1784 }
1785 } else if (cfq_should_preempt(cfqd, cfqq, crq)) {
1786 /*
1787 * not the active queue - expire current slice if it is
1788 * idle and has expired it's mean thinktime or this new queue
1789 * has some old slice time left and is of higher priority
1790 */
1791 cfq_preempt_queue(cfqd, cfqq);
Jens Axboe3b181522005-06-27 10:56:24 +02001792 cfq_mark_cfqq_must_dispatch(cfqq);
Jens Axboe22e2c502005-06-27 10:55:12 +02001793 cfq_start_queueing(cfqd, cfqq);
1794 }
1795}
1796
Jens Axboeb4878f22005-10-20 16:42:29 +02001797static void cfq_insert_request(request_queue_t *q, struct request *rq)
Jens Axboe22e2c502005-06-27 10:55:12 +02001798{
Jens Axboeb4878f22005-10-20 16:42:29 +02001799 struct cfq_data *cfqd = q->elevator->elevator_data;
Jens Axboe22e2c502005-06-27 10:55:12 +02001800 struct cfq_rq *crq = RQ_DATA(rq);
1801 struct cfq_queue *cfqq = crq->cfq_queue;
1802
1803 cfq_init_prio_data(cfqq);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001804
1805 cfq_add_crq_rb(crq);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001806
Jens Axboe22e2c502005-06-27 10:55:12 +02001807 list_add_tail(&rq->queuelist, &cfqq->fifo);
1808
Tejun Heo98b11472005-10-20 16:46:54 +02001809 if (rq_mergeable(rq))
Jens Axboe22e2c502005-06-27 10:55:12 +02001810 cfq_add_crq_hash(cfqd, crq);
1811
Jens Axboe22e2c502005-06-27 10:55:12 +02001812 cfq_crq_enqueued(cfqd, cfqq, crq);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001813}
1814
Linus Torvalds1da177e2005-04-16 15:20:36 -07001815static void cfq_completed_request(request_queue_t *q, struct request *rq)
1816{
1817 struct cfq_rq *crq = RQ_DATA(rq);
Jens Axboeb4878f22005-10-20 16:42:29 +02001818 struct cfq_queue *cfqq = crq->cfq_queue;
1819 struct cfq_data *cfqd = cfqq->cfqd;
1820 const int sync = cfq_crq_is_sync(crq);
1821 unsigned long now;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001822
Jens Axboeb4878f22005-10-20 16:42:29 +02001823 now = jiffies;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001824
Jens Axboeb4878f22005-10-20 16:42:29 +02001825 WARN_ON(!cfqd->rq_in_driver);
1826 WARN_ON(!cfqq->on_dispatch[sync]);
1827 cfqd->rq_in_driver--;
1828 cfqq->on_dispatch[sync]--;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001829
Jens Axboeb4878f22005-10-20 16:42:29 +02001830 if (!cfq_class_idle(cfqq))
1831 cfqd->last_end_request = now;
Jens Axboe3b181522005-06-27 10:56:24 +02001832
Jens Axboeb4878f22005-10-20 16:42:29 +02001833 if (!cfq_cfqq_dispatched(cfqq)) {
1834 if (cfq_cfqq_on_rr(cfqq)) {
1835 cfqq->service_last = now;
1836 cfq_resort_rr_list(cfqq, 0);
1837 }
Jens Axboe7b14e3b2006-02-28 09:35:11 +01001838 cfq_schedule_dispatch(cfqd);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001839 }
1840
Jens Axboeb4878f22005-10-20 16:42:29 +02001841 if (cfq_crq_is_sync(crq))
1842 crq->io_context->last_end_request = now;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001843}
1844
1845static struct request *
1846cfq_former_request(request_queue_t *q, struct request *rq)
1847{
1848 struct cfq_rq *crq = RQ_DATA(rq);
1849 struct rb_node *rbprev = rb_prev(&crq->rb_node);
1850
1851 if (rbprev)
1852 return rb_entry_crq(rbprev)->request;
1853
1854 return NULL;
1855}
1856
1857static struct request *
1858cfq_latter_request(request_queue_t *q, struct request *rq)
1859{
1860 struct cfq_rq *crq = RQ_DATA(rq);
1861 struct rb_node *rbnext = rb_next(&crq->rb_node);
1862
1863 if (rbnext)
1864 return rb_entry_crq(rbnext)->request;
1865
1866 return NULL;
1867}
1868
Jens Axboe22e2c502005-06-27 10:55:12 +02001869/*
1870 * we temporarily boost lower priority queues if they are holding fs exclusive
1871 * resources. they are boosted to normal prio (CLASS_BE/4)
1872 */
1873static void cfq_prio_boost(struct cfq_queue *cfqq)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001874{
Jens Axboe22e2c502005-06-27 10:55:12 +02001875 const int ioprio_class = cfqq->ioprio_class;
1876 const int ioprio = cfqq->ioprio;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001877
Jens Axboe22e2c502005-06-27 10:55:12 +02001878 if (has_fs_excl()) {
1879 /*
1880 * boost idle prio on transactions that would lock out other
1881 * users of the filesystem
1882 */
1883 if (cfq_class_idle(cfqq))
1884 cfqq->ioprio_class = IOPRIO_CLASS_BE;
1885 if (cfqq->ioprio > IOPRIO_NORM)
1886 cfqq->ioprio = IOPRIO_NORM;
1887 } else {
1888 /*
1889 * check if we need to unboost the queue
1890 */
1891 if (cfqq->ioprio_class != cfqq->org_ioprio_class)
1892 cfqq->ioprio_class = cfqq->org_ioprio_class;
1893 if (cfqq->ioprio != cfqq->org_ioprio)
1894 cfqq->ioprio = cfqq->org_ioprio;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001895 }
1896
Jens Axboe22e2c502005-06-27 10:55:12 +02001897 /*
1898 * refile between round-robin lists if we moved the priority class
1899 */
1900 if ((ioprio_class != cfqq->ioprio_class || ioprio != cfqq->ioprio) &&
Jens Axboe3b181522005-06-27 10:56:24 +02001901 cfq_cfqq_on_rr(cfqq))
Jens Axboe22e2c502005-06-27 10:55:12 +02001902 cfq_resort_rr_list(cfqq, 0);
1903}
1904
Jens Axboe22e2c502005-06-27 10:55:12 +02001905static inline int
1906__cfq_may_queue(struct cfq_data *cfqd, struct cfq_queue *cfqq,
1907 struct task_struct *task, int rw)
1908{
Jens Axboe3b181522005-06-27 10:56:24 +02001909 if ((cfq_cfqq_wait_request(cfqq) || cfq_cfqq_must_alloc(cfqq)) &&
Andrew Morton99f95e52005-06-27 20:14:05 -07001910 !cfq_cfqq_must_alloc_slice(cfqq)) {
Jens Axboe3b181522005-06-27 10:56:24 +02001911 cfq_mark_cfqq_must_alloc_slice(cfqq);
Jens Axboe22e2c502005-06-27 10:55:12 +02001912 return ELV_MQUEUE_MUST;
Jens Axboe3b181522005-06-27 10:56:24 +02001913 }
Jens Axboe22e2c502005-06-27 10:55:12 +02001914
1915 return ELV_MQUEUE_MAY;
Jens Axboe22e2c502005-06-27 10:55:12 +02001916}
1917
1918static int cfq_may_queue(request_queue_t *q, int rw, struct bio *bio)
1919{
1920 struct cfq_data *cfqd = q->elevator->elevator_data;
1921 struct task_struct *tsk = current;
1922 struct cfq_queue *cfqq;
1923
1924 /*
1925 * don't force setup of a queue from here, as a call to may_queue
1926 * does not necessarily imply that a request actually will be queued.
1927 * so just lookup a possibly existing queue, or return 'may queue'
1928 * if that fails
1929 */
Jens Axboe3b181522005-06-27 10:56:24 +02001930 cfqq = cfq_find_cfq_hash(cfqd, cfq_queue_pid(tsk, rw), tsk->ioprio);
Jens Axboe22e2c502005-06-27 10:55:12 +02001931 if (cfqq) {
1932 cfq_init_prio_data(cfqq);
1933 cfq_prio_boost(cfqq);
1934
1935 return __cfq_may_queue(cfqd, cfqq, tsk, rw);
1936 }
1937
1938 return ELV_MQUEUE_MAY;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001939}
1940
1941static void cfq_check_waiters(request_queue_t *q, struct cfq_queue *cfqq)
1942{
Jens Axboe22e2c502005-06-27 10:55:12 +02001943 struct cfq_data *cfqd = q->elevator->elevator_data;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001944
Jens Axboe271f18f2006-06-13 08:08:38 +02001945 if (unlikely(cfqd->rq_starved)) {
1946 struct request_list *rl = &q->rq;
1947
Jens Axboe22e2c502005-06-27 10:55:12 +02001948 smp_mb();
1949 if (waitqueue_active(&rl->wait[READ]))
1950 wake_up(&rl->wait[READ]);
Jens Axboe22e2c502005-06-27 10:55:12 +02001951 if (waitqueue_active(&rl->wait[WRITE]))
1952 wake_up(&rl->wait[WRITE]);
1953 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07001954}
1955
1956/*
1957 * queue lock held here
1958 */
1959static void cfq_put_request(request_queue_t *q, struct request *rq)
1960{
1961 struct cfq_data *cfqd = q->elevator->elevator_data;
1962 struct cfq_rq *crq = RQ_DATA(rq);
1963
1964 if (crq) {
1965 struct cfq_queue *cfqq = crq->cfq_queue;
Jens Axboe22e2c502005-06-27 10:55:12 +02001966 const int rw = rq_data_dir(rq);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001967
Jens Axboe22e2c502005-06-27 10:55:12 +02001968 BUG_ON(!cfqq->allocated[rw]);
1969 cfqq->allocated[rw]--;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001970
Jens Axboe22e2c502005-06-27 10:55:12 +02001971 put_io_context(crq->io_context->ioc);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001972
1973 mempool_free(crq, cfqd->crq_pool);
1974 rq->elevator_private = NULL;
1975
Linus Torvalds1da177e2005-04-16 15:20:36 -07001976 cfq_check_waiters(q, cfqq);
1977 cfq_put_queue(cfqq);
1978 }
1979}
1980
1981/*
Jens Axboe22e2c502005-06-27 10:55:12 +02001982 * Allocate cfq data structures associated with this request.
Linus Torvalds1da177e2005-04-16 15:20:36 -07001983 */
Jens Axboe22e2c502005-06-27 10:55:12 +02001984static int
1985cfq_set_request(request_queue_t *q, struct request *rq, struct bio *bio,
Al Viro8267e262005-10-21 03:20:53 -04001986 gfp_t gfp_mask)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001987{
1988 struct cfq_data *cfqd = q->elevator->elevator_data;
Jens Axboe3b181522005-06-27 10:56:24 +02001989 struct task_struct *tsk = current;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001990 struct cfq_io_context *cic;
1991 const int rw = rq_data_dir(rq);
Jens Axboe3b181522005-06-27 10:56:24 +02001992 pid_t key = cfq_queue_pid(tsk, rw);
Jens Axboe22e2c502005-06-27 10:55:12 +02001993 struct cfq_queue *cfqq;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001994 struct cfq_rq *crq;
1995 unsigned long flags;
Al Viro12a05732006-03-18 13:38:01 -05001996 int is_sync = key != CFQ_KEY_ASYNC;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001997
1998 might_sleep_if(gfp_mask & __GFP_WAIT);
1999
Jens Axboee2d74ac2006-03-28 08:59:01 +02002000 cic = cfq_get_io_context(cfqd, gfp_mask);
Jens Axboe22e2c502005-06-27 10:55:12 +02002001
Linus Torvalds1da177e2005-04-16 15:20:36 -07002002 spin_lock_irqsave(q->queue_lock, flags);
2003
Jens Axboe22e2c502005-06-27 10:55:12 +02002004 if (!cic)
2005 goto queue_fail;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002006
Al Viro12a05732006-03-18 13:38:01 -05002007 if (!cic->cfqq[is_sync]) {
Al Viro6f325a12006-03-18 14:58:37 -05002008 cfqq = cfq_get_queue(cfqd, key, tsk, gfp_mask);
Jens Axboe22e2c502005-06-27 10:55:12 +02002009 if (!cfqq)
2010 goto queue_fail;
2011
Al Viro12a05732006-03-18 13:38:01 -05002012 cic->cfqq[is_sync] = cfqq;
Jens Axboe22e2c502005-06-27 10:55:12 +02002013 } else
Al Viro12a05732006-03-18 13:38:01 -05002014 cfqq = cic->cfqq[is_sync];
Linus Torvalds1da177e2005-04-16 15:20:36 -07002015
2016 cfqq->allocated[rw]++;
Jens Axboe3b181522005-06-27 10:56:24 +02002017 cfq_clear_cfqq_must_alloc(cfqq);
Jens Axboe22e2c502005-06-27 10:55:12 +02002018 cfqd->rq_starved = 0;
2019 atomic_inc(&cfqq->ref);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002020 spin_unlock_irqrestore(q->queue_lock, flags);
2021
Linus Torvalds1da177e2005-04-16 15:20:36 -07002022 crq = mempool_alloc(cfqd->crq_pool, gfp_mask);
2023 if (crq) {
2024 RB_CLEAR(&crq->rb_node);
2025 crq->rb_key = 0;
2026 crq->request = rq;
2027 INIT_HLIST_NODE(&crq->hash);
2028 crq->cfq_queue = cfqq;
2029 crq->io_context = cic;
Jens Axboe3b181522005-06-27 10:56:24 +02002030
Al Viro12a05732006-03-18 13:38:01 -05002031 if (is_sync)
Jens Axboe3b181522005-06-27 10:56:24 +02002032 cfq_mark_crq_is_sync(crq);
2033 else
2034 cfq_clear_crq_is_sync(crq);
2035
Linus Torvalds1da177e2005-04-16 15:20:36 -07002036 rq->elevator_private = crq;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002037 return 0;
2038 }
2039
Linus Torvalds1da177e2005-04-16 15:20:36 -07002040 spin_lock_irqsave(q->queue_lock, flags);
2041 cfqq->allocated[rw]--;
Jens Axboe22e2c502005-06-27 10:55:12 +02002042 if (!(cfqq->allocated[0] + cfqq->allocated[1]))
Jens Axboe3b181522005-06-27 10:56:24 +02002043 cfq_mark_cfqq_must_alloc(cfqq);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002044 cfq_put_queue(cfqq);
Jens Axboe22e2c502005-06-27 10:55:12 +02002045queue_fail:
2046 if (cic)
2047 put_io_context(cic->ioc);
2048 /*
2049 * mark us rq allocation starved. we need to kickstart the process
2050 * ourselves if there are no pending requests that can do it for us.
2051 * that would be an extremely rare OOM situation
2052 */
2053 cfqd->rq_starved = 1;
Jens Axboe3b181522005-06-27 10:56:24 +02002054 cfq_schedule_dispatch(cfqd);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002055 spin_unlock_irqrestore(q->queue_lock, flags);
2056 return 1;
2057}
2058
Jens Axboe22e2c502005-06-27 10:55:12 +02002059static void cfq_kick_queue(void *data)
2060{
2061 request_queue_t *q = data;
2062 struct cfq_data *cfqd = q->elevator->elevator_data;
2063 unsigned long flags;
2064
2065 spin_lock_irqsave(q->queue_lock, flags);
2066
2067 if (cfqd->rq_starved) {
2068 struct request_list *rl = &q->rq;
2069
2070 /*
2071 * we aren't guaranteed to get a request after this, but we
2072 * have to be opportunistic
2073 */
2074 smp_mb();
2075 if (waitqueue_active(&rl->wait[READ]))
2076 wake_up(&rl->wait[READ]);
2077 if (waitqueue_active(&rl->wait[WRITE]))
2078 wake_up(&rl->wait[WRITE]);
2079 }
2080
2081 blk_remove_plug(q);
2082 q->request_fn(q);
2083 spin_unlock_irqrestore(q->queue_lock, flags);
2084}
2085
2086/*
2087 * Timer running if the active_queue is currently idling inside its time slice
2088 */
2089static void cfq_idle_slice_timer(unsigned long data)
2090{
2091 struct cfq_data *cfqd = (struct cfq_data *) data;
2092 struct cfq_queue *cfqq;
2093 unsigned long flags;
2094
2095 spin_lock_irqsave(cfqd->queue->queue_lock, flags);
2096
2097 if ((cfqq = cfqd->active_queue) != NULL) {
2098 unsigned long now = jiffies;
2099
2100 /*
2101 * expired
2102 */
2103 if (time_after(now, cfqq->slice_end))
2104 goto expire;
2105
2106 /*
2107 * only expire and reinvoke request handler, if there are
2108 * other queues with pending requests
2109 */
Jens Axboeb4878f22005-10-20 16:42:29 +02002110 if (!cfqd->busy_queues) {
Jens Axboe22e2c502005-06-27 10:55:12 +02002111 cfqd->idle_slice_timer.expires = min(now + cfqd->cfq_slice_idle, cfqq->slice_end);
2112 add_timer(&cfqd->idle_slice_timer);
2113 goto out_cont;
2114 }
2115
2116 /*
2117 * not expired and it has a request pending, let it dispatch
2118 */
2119 if (!RB_EMPTY(&cfqq->sort_list)) {
Jens Axboe3b181522005-06-27 10:56:24 +02002120 cfq_mark_cfqq_must_dispatch(cfqq);
Jens Axboe22e2c502005-06-27 10:55:12 +02002121 goto out_kick;
2122 }
2123 }
2124expire:
2125 cfq_slice_expired(cfqd, 0);
2126out_kick:
Jens Axboe3b181522005-06-27 10:56:24 +02002127 cfq_schedule_dispatch(cfqd);
Jens Axboe22e2c502005-06-27 10:55:12 +02002128out_cont:
2129 spin_unlock_irqrestore(cfqd->queue->queue_lock, flags);
2130}
2131
2132/*
2133 * Timer running if an idle class queue is waiting for service
2134 */
2135static void cfq_idle_class_timer(unsigned long data)
2136{
2137 struct cfq_data *cfqd = (struct cfq_data *) data;
2138 unsigned long flags, end;
2139
2140 spin_lock_irqsave(cfqd->queue->queue_lock, flags);
2141
2142 /*
2143 * race with a non-idle queue, reset timer
2144 */
2145 end = cfqd->last_end_request + CFQ_IDLE_GRACE;
Jens Axboeae818a32006-06-01 10:13:43 +02002146 if (!time_after_eq(jiffies, end))
2147 mod_timer(&cfqd->idle_class_timer, end);
2148 else
Jens Axboe3b181522005-06-27 10:56:24 +02002149 cfq_schedule_dispatch(cfqd);
Jens Axboe22e2c502005-06-27 10:55:12 +02002150
2151 spin_unlock_irqrestore(cfqd->queue->queue_lock, flags);
2152}
2153
Jens Axboe3b181522005-06-27 10:56:24 +02002154static void cfq_shutdown_timer_wq(struct cfq_data *cfqd)
2155{
2156 del_timer_sync(&cfqd->idle_slice_timer);
2157 del_timer_sync(&cfqd->idle_class_timer);
2158 blk_sync_queue(cfqd->queue);
2159}
Jens Axboe22e2c502005-06-27 10:55:12 +02002160
Linus Torvalds1da177e2005-04-16 15:20:36 -07002161static void cfq_exit_queue(elevator_t *e)
2162{
Jens Axboe22e2c502005-06-27 10:55:12 +02002163 struct cfq_data *cfqd = e->elevator_data;
Al Virod9ff4182006-03-18 13:51:22 -05002164 request_queue_t *q = cfqd->queue;
Jens Axboe22e2c502005-06-27 10:55:12 +02002165
Jens Axboe3b181522005-06-27 10:56:24 +02002166 cfq_shutdown_timer_wq(cfqd);
Jens Axboee2d74ac2006-03-28 08:59:01 +02002167
Jens Axboe3793c652006-05-30 21:11:04 +02002168 spin_lock(&cfq_exit_lock);
Al Virod9ff4182006-03-18 13:51:22 -05002169 spin_lock_irq(q->queue_lock);
Jens Axboee2d74ac2006-03-28 08:59:01 +02002170
Al Virod9ff4182006-03-18 13:51:22 -05002171 if (cfqd->active_queue)
2172 __cfq_slice_expired(cfqd, cfqd->active_queue, 0);
Jens Axboee2d74ac2006-03-28 08:59:01 +02002173
2174 while (!list_empty(&cfqd->cic_list)) {
Al Virod9ff4182006-03-18 13:51:22 -05002175 struct cfq_io_context *cic = list_entry(cfqd->cic_list.next,
2176 struct cfq_io_context,
2177 queue_list);
2178 if (cic->cfqq[ASYNC]) {
2179 cfq_put_queue(cic->cfqq[ASYNC]);
2180 cic->cfqq[ASYNC] = NULL;
2181 }
2182 if (cic->cfqq[SYNC]) {
2183 cfq_put_queue(cic->cfqq[SYNC]);
2184 cic->cfqq[SYNC] = NULL;
2185 }
2186 cic->key = NULL;
2187 list_del_init(&cic->queue_list);
2188 }
Jens Axboee2d74ac2006-03-28 08:59:01 +02002189
Al Virod9ff4182006-03-18 13:51:22 -05002190 spin_unlock_irq(q->queue_lock);
Jens Axboe3793c652006-05-30 21:11:04 +02002191 spin_unlock(&cfq_exit_lock);
Al Viroa90d7422006-03-18 12:05:37 -05002192
2193 cfq_shutdown_timer_wq(cfqd);
2194
2195 mempool_destroy(cfqd->crq_pool);
2196 kfree(cfqd->crq_hash);
2197 kfree(cfqd->cfq_hash);
2198 kfree(cfqd);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002199}
2200
Jens Axboebc1c1162006-06-08 08:49:06 +02002201static void *cfq_init_queue(request_queue_t *q, elevator_t *e)
Linus Torvalds1da177e2005-04-16 15:20:36 -07002202{
2203 struct cfq_data *cfqd;
2204 int i;
2205
2206 cfqd = kmalloc(sizeof(*cfqd), GFP_KERNEL);
2207 if (!cfqd)
Jens Axboebc1c1162006-06-08 08:49:06 +02002208 return NULL;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002209
2210 memset(cfqd, 0, sizeof(*cfqd));
Jens Axboe22e2c502005-06-27 10:55:12 +02002211
2212 for (i = 0; i < CFQ_PRIO_LISTS; i++)
2213 INIT_LIST_HEAD(&cfqd->rr_list[i]);
2214
2215 INIT_LIST_HEAD(&cfqd->busy_rr);
2216 INIT_LIST_HEAD(&cfqd->cur_rr);
2217 INIT_LIST_HEAD(&cfqd->idle_rr);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002218 INIT_LIST_HEAD(&cfqd->empty_list);
Al Virod9ff4182006-03-18 13:51:22 -05002219 INIT_LIST_HEAD(&cfqd->cic_list);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002220
2221 cfqd->crq_hash = kmalloc(sizeof(struct hlist_head) * CFQ_MHASH_ENTRIES, GFP_KERNEL);
2222 if (!cfqd->crq_hash)
2223 goto out_crqhash;
2224
2225 cfqd->cfq_hash = kmalloc(sizeof(struct hlist_head) * CFQ_QHASH_ENTRIES, GFP_KERNEL);
2226 if (!cfqd->cfq_hash)
2227 goto out_cfqhash;
2228
Matthew Dobson93d23412006-03-26 01:37:50 -08002229 cfqd->crq_pool = mempool_create_slab_pool(BLKDEV_MIN_RQ, crq_pool);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002230 if (!cfqd->crq_pool)
2231 goto out_crqpool;
2232
2233 for (i = 0; i < CFQ_MHASH_ENTRIES; i++)
2234 INIT_HLIST_HEAD(&cfqd->crq_hash[i]);
2235 for (i = 0; i < CFQ_QHASH_ENTRIES; i++)
2236 INIT_HLIST_HEAD(&cfqd->cfq_hash[i]);
2237
Linus Torvalds1da177e2005-04-16 15:20:36 -07002238 cfqd->queue = q;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002239
Jens Axboe22e2c502005-06-27 10:55:12 +02002240 init_timer(&cfqd->idle_slice_timer);
2241 cfqd->idle_slice_timer.function = cfq_idle_slice_timer;
2242 cfqd->idle_slice_timer.data = (unsigned long) cfqd;
2243
2244 init_timer(&cfqd->idle_class_timer);
2245 cfqd->idle_class_timer.function = cfq_idle_class_timer;
2246 cfqd->idle_class_timer.data = (unsigned long) cfqd;
2247
2248 INIT_WORK(&cfqd->unplug_work, cfq_kick_queue, q);
2249
Linus Torvalds1da177e2005-04-16 15:20:36 -07002250 cfqd->cfq_queued = cfq_queued;
2251 cfqd->cfq_quantum = cfq_quantum;
Jens Axboe22e2c502005-06-27 10:55:12 +02002252 cfqd->cfq_fifo_expire[0] = cfq_fifo_expire[0];
2253 cfqd->cfq_fifo_expire[1] = cfq_fifo_expire[1];
Linus Torvalds1da177e2005-04-16 15:20:36 -07002254 cfqd->cfq_back_max = cfq_back_max;
2255 cfqd->cfq_back_penalty = cfq_back_penalty;
Jens Axboe22e2c502005-06-27 10:55:12 +02002256 cfqd->cfq_slice[0] = cfq_slice_async;
2257 cfqd->cfq_slice[1] = cfq_slice_sync;
2258 cfqd->cfq_slice_async_rq = cfq_slice_async_rq;
2259 cfqd->cfq_slice_idle = cfq_slice_idle;
Jens Axboe3b181522005-06-27 10:56:24 +02002260
Jens Axboebc1c1162006-06-08 08:49:06 +02002261 return cfqd;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002262out_crqpool:
2263 kfree(cfqd->cfq_hash);
2264out_cfqhash:
2265 kfree(cfqd->crq_hash);
2266out_crqhash:
2267 kfree(cfqd);
Jens Axboebc1c1162006-06-08 08:49:06 +02002268 return NULL;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002269}
2270
2271static void cfq_slab_kill(void)
2272{
2273 if (crq_pool)
2274 kmem_cache_destroy(crq_pool);
2275 if (cfq_pool)
2276 kmem_cache_destroy(cfq_pool);
2277 if (cfq_ioc_pool)
2278 kmem_cache_destroy(cfq_ioc_pool);
2279}
2280
2281static int __init cfq_slab_setup(void)
2282{
2283 crq_pool = kmem_cache_create("crq_pool", sizeof(struct cfq_rq), 0, 0,
2284 NULL, NULL);
2285 if (!crq_pool)
2286 goto fail;
2287
2288 cfq_pool = kmem_cache_create("cfq_pool", sizeof(struct cfq_queue), 0, 0,
2289 NULL, NULL);
2290 if (!cfq_pool)
2291 goto fail;
2292
2293 cfq_ioc_pool = kmem_cache_create("cfq_ioc_pool",
2294 sizeof(struct cfq_io_context), 0, 0, NULL, NULL);
2295 if (!cfq_ioc_pool)
2296 goto fail;
2297
2298 return 0;
2299fail:
2300 cfq_slab_kill();
2301 return -ENOMEM;
2302}
2303
Linus Torvalds1da177e2005-04-16 15:20:36 -07002304/*
2305 * sysfs parts below -->
2306 */
Linus Torvalds1da177e2005-04-16 15:20:36 -07002307
2308static ssize_t
2309cfq_var_show(unsigned int var, char *page)
2310{
2311 return sprintf(page, "%d\n", var);
2312}
2313
2314static ssize_t
2315cfq_var_store(unsigned int *var, const char *page, size_t count)
2316{
2317 char *p = (char *) page;
2318
2319 *var = simple_strtoul(p, &p, 10);
2320 return count;
2321}
2322
Linus Torvalds1da177e2005-04-16 15:20:36 -07002323#define SHOW_FUNCTION(__FUNC, __VAR, __CONV) \
Al Viro3d1ab402006-03-18 18:35:43 -05002324static ssize_t __FUNC(elevator_t *e, char *page) \
Linus Torvalds1da177e2005-04-16 15:20:36 -07002325{ \
Al Viro3d1ab402006-03-18 18:35:43 -05002326 struct cfq_data *cfqd = e->elevator_data; \
Linus Torvalds1da177e2005-04-16 15:20:36 -07002327 unsigned int __data = __VAR; \
2328 if (__CONV) \
2329 __data = jiffies_to_msecs(__data); \
2330 return cfq_var_show(__data, (page)); \
2331}
2332SHOW_FUNCTION(cfq_quantum_show, cfqd->cfq_quantum, 0);
2333SHOW_FUNCTION(cfq_queued_show, cfqd->cfq_queued, 0);
Jens Axboe22e2c502005-06-27 10:55:12 +02002334SHOW_FUNCTION(cfq_fifo_expire_sync_show, cfqd->cfq_fifo_expire[1], 1);
2335SHOW_FUNCTION(cfq_fifo_expire_async_show, cfqd->cfq_fifo_expire[0], 1);
Al Viroe572ec72006-03-18 22:27:18 -05002336SHOW_FUNCTION(cfq_back_seek_max_show, cfqd->cfq_back_max, 0);
2337SHOW_FUNCTION(cfq_back_seek_penalty_show, cfqd->cfq_back_penalty, 0);
Jens Axboe22e2c502005-06-27 10:55:12 +02002338SHOW_FUNCTION(cfq_slice_idle_show, cfqd->cfq_slice_idle, 1);
2339SHOW_FUNCTION(cfq_slice_sync_show, cfqd->cfq_slice[1], 1);
2340SHOW_FUNCTION(cfq_slice_async_show, cfqd->cfq_slice[0], 1);
2341SHOW_FUNCTION(cfq_slice_async_rq_show, cfqd->cfq_slice_async_rq, 0);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002342#undef SHOW_FUNCTION
2343
2344#define STORE_FUNCTION(__FUNC, __PTR, MIN, MAX, __CONV) \
Al Viro3d1ab402006-03-18 18:35:43 -05002345static ssize_t __FUNC(elevator_t *e, const char *page, size_t count) \
Linus Torvalds1da177e2005-04-16 15:20:36 -07002346{ \
Al Viro3d1ab402006-03-18 18:35:43 -05002347 struct cfq_data *cfqd = e->elevator_data; \
Linus Torvalds1da177e2005-04-16 15:20:36 -07002348 unsigned int __data; \
2349 int ret = cfq_var_store(&__data, (page), count); \
2350 if (__data < (MIN)) \
2351 __data = (MIN); \
2352 else if (__data > (MAX)) \
2353 __data = (MAX); \
2354 if (__CONV) \
2355 *(__PTR) = msecs_to_jiffies(__data); \
2356 else \
2357 *(__PTR) = __data; \
2358 return ret; \
2359}
2360STORE_FUNCTION(cfq_quantum_store, &cfqd->cfq_quantum, 1, UINT_MAX, 0);
2361STORE_FUNCTION(cfq_queued_store, &cfqd->cfq_queued, 1, UINT_MAX, 0);
Jens Axboe22e2c502005-06-27 10:55:12 +02002362STORE_FUNCTION(cfq_fifo_expire_sync_store, &cfqd->cfq_fifo_expire[1], 1, UINT_MAX, 1);
2363STORE_FUNCTION(cfq_fifo_expire_async_store, &cfqd->cfq_fifo_expire[0], 1, UINT_MAX, 1);
Al Viroe572ec72006-03-18 22:27:18 -05002364STORE_FUNCTION(cfq_back_seek_max_store, &cfqd->cfq_back_max, 0, UINT_MAX, 0);
2365STORE_FUNCTION(cfq_back_seek_penalty_store, &cfqd->cfq_back_penalty, 1, UINT_MAX, 0);
Jens Axboe22e2c502005-06-27 10:55:12 +02002366STORE_FUNCTION(cfq_slice_idle_store, &cfqd->cfq_slice_idle, 0, UINT_MAX, 1);
2367STORE_FUNCTION(cfq_slice_sync_store, &cfqd->cfq_slice[1], 1, UINT_MAX, 1);
2368STORE_FUNCTION(cfq_slice_async_store, &cfqd->cfq_slice[0], 1, UINT_MAX, 1);
2369STORE_FUNCTION(cfq_slice_async_rq_store, &cfqd->cfq_slice_async_rq, 1, UINT_MAX, 0);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002370#undef STORE_FUNCTION
2371
Al Viroe572ec72006-03-18 22:27:18 -05002372#define CFQ_ATTR(name) \
2373 __ATTR(name, S_IRUGO|S_IWUSR, cfq_##name##_show, cfq_##name##_store)
Jens Axboe3b181522005-06-27 10:56:24 +02002374
Al Viroe572ec72006-03-18 22:27:18 -05002375static struct elv_fs_entry cfq_attrs[] = {
2376 CFQ_ATTR(quantum),
2377 CFQ_ATTR(queued),
2378 CFQ_ATTR(fifo_expire_sync),
2379 CFQ_ATTR(fifo_expire_async),
2380 CFQ_ATTR(back_seek_max),
2381 CFQ_ATTR(back_seek_penalty),
2382 CFQ_ATTR(slice_sync),
2383 CFQ_ATTR(slice_async),
2384 CFQ_ATTR(slice_async_rq),
2385 CFQ_ATTR(slice_idle),
Al Viroe572ec72006-03-18 22:27:18 -05002386 __ATTR_NULL
Linus Torvalds1da177e2005-04-16 15:20:36 -07002387};
2388
Linus Torvalds1da177e2005-04-16 15:20:36 -07002389static struct elevator_type iosched_cfq = {
2390 .ops = {
2391 .elevator_merge_fn = cfq_merge,
2392 .elevator_merged_fn = cfq_merged_request,
2393 .elevator_merge_req_fn = cfq_merged_requests,
Jens Axboeb4878f22005-10-20 16:42:29 +02002394 .elevator_dispatch_fn = cfq_dispatch_requests,
Linus Torvalds1da177e2005-04-16 15:20:36 -07002395 .elevator_add_req_fn = cfq_insert_request,
Jens Axboeb4878f22005-10-20 16:42:29 +02002396 .elevator_activate_req_fn = cfq_activate_request,
Linus Torvalds1da177e2005-04-16 15:20:36 -07002397 .elevator_deactivate_req_fn = cfq_deactivate_request,
2398 .elevator_queue_empty_fn = cfq_queue_empty,
2399 .elevator_completed_req_fn = cfq_completed_request,
2400 .elevator_former_req_fn = cfq_former_request,
2401 .elevator_latter_req_fn = cfq_latter_request,
2402 .elevator_set_req_fn = cfq_set_request,
2403 .elevator_put_req_fn = cfq_put_request,
2404 .elevator_may_queue_fn = cfq_may_queue,
2405 .elevator_init_fn = cfq_init_queue,
2406 .elevator_exit_fn = cfq_exit_queue,
Al Viroe17a9482006-03-18 13:21:20 -05002407 .trim = cfq_trim,
Linus Torvalds1da177e2005-04-16 15:20:36 -07002408 },
Al Viro3d1ab402006-03-18 18:35:43 -05002409 .elevator_attrs = cfq_attrs,
Linus Torvalds1da177e2005-04-16 15:20:36 -07002410 .elevator_name = "cfq",
2411 .elevator_owner = THIS_MODULE,
2412};
2413
2414static int __init cfq_init(void)
2415{
2416 int ret;
2417
Jens Axboe22e2c502005-06-27 10:55:12 +02002418 /*
2419 * could be 0 on HZ < 1000 setups
2420 */
2421 if (!cfq_slice_async)
2422 cfq_slice_async = 1;
2423 if (!cfq_slice_idle)
2424 cfq_slice_idle = 1;
2425
Linus Torvalds1da177e2005-04-16 15:20:36 -07002426 if (cfq_slab_setup())
2427 return -ENOMEM;
2428
2429 ret = elv_register(&iosched_cfq);
Jens Axboe22e2c502005-06-27 10:55:12 +02002430 if (ret)
2431 cfq_slab_kill();
Linus Torvalds1da177e2005-04-16 15:20:36 -07002432
Linus Torvalds1da177e2005-04-16 15:20:36 -07002433 return ret;
2434}
2435
2436static void __exit cfq_exit(void)
2437{
Al Viro334e94d2006-03-18 15:05:53 -05002438 DECLARE_COMPLETION(all_gone);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002439 elv_unregister(&iosched_cfq);
Al Viro334e94d2006-03-18 15:05:53 -05002440 ioc_gone = &all_gone;
OGAWA Hirofumifba82272006-04-18 09:44:06 +02002441 /* ioc_gone's update must be visible before reading ioc_count */
2442 smp_wmb();
Al Viro334e94d2006-03-18 15:05:53 -05002443 if (atomic_read(&ioc_count))
OGAWA Hirofumifba82272006-04-18 09:44:06 +02002444 wait_for_completion(ioc_gone);
Al Viro334e94d2006-03-18 15:05:53 -05002445 synchronize_rcu();
Christoph Hellwig83521d32005-10-30 15:01:39 -08002446 cfq_slab_kill();
Linus Torvalds1da177e2005-04-16 15:20:36 -07002447}
2448
2449module_init(cfq_init);
2450module_exit(cfq_exit);
2451
2452MODULE_AUTHOR("Jens Axboe");
2453MODULE_LICENSE("GPL");
2454MODULE_DESCRIPTION("Completely Fair Queueing IO scheduler");