blob: 5e558c4689a4f561117cf89b5c4867d045699ad8 [file] [log] [blame]
Linus Torvalds1da177e2005-04-16 15:20:36 -07001/*
Linus Torvalds1da177e2005-04-16 15:20:36 -07002 * Block device elevator/IO-scheduler.
3 *
4 * Copyright (C) 2000 Andrea Arcangeli <andrea@suse.de> SuSE
5 *
6 * 30042000 Jens Axboe <axboe@suse.de> :
7 *
8 * Split the elevator a bit so that it is possible to choose a different
9 * one or even write a new "plug in". There are three pieces:
10 * - elevator_fn, inserts a new request in the queue list
11 * - elevator_merge_fn, decides whether a new buffer can be merged with
12 * an existing request
13 * - elevator_dequeue_fn, called when a request is taken off the active list
14 *
15 * 20082000 Dave Jones <davej@suse.de> :
16 * Removed tests for max-bomb-segments, which was breaking elvtune
17 * when run without -bN
18 *
19 * Jens:
20 * - Rework again to work with bio instead of buffer_heads
21 * - loose bi_dev comparisons, partition handling is right now
22 * - completely modularize elevator setup and teardown
23 *
24 */
25#include <linux/kernel.h>
26#include <linux/fs.h>
27#include <linux/blkdev.h>
28#include <linux/elevator.h>
29#include <linux/bio.h>
30#include <linux/config.h>
31#include <linux/module.h>
32#include <linux/slab.h>
33#include <linux/init.h>
34#include <linux/compiler.h>
Tejun Heocb98fc82005-10-28 08:29:39 +020035#include <linux/delay.h>
Jens Axboe2056a782006-03-23 20:00:26 +010036#include <linux/blktrace_api.h>
Linus Torvalds1da177e2005-04-16 15:20:36 -070037
38#include <asm/uaccess.h>
39
40static DEFINE_SPINLOCK(elv_list_lock);
41static LIST_HEAD(elv_list);
42
43/*
44 * can we safely merge with this request?
45 */
46inline int elv_rq_merge_ok(struct request *rq, struct bio *bio)
47{
48 if (!rq_mergeable(rq))
49 return 0;
50
51 /*
52 * different data direction or already started, don't merge
53 */
54 if (bio_data_dir(bio) != rq_data_dir(rq))
55 return 0;
56
57 /*
58 * same device and no special stuff set, merge is ok
59 */
60 if (rq->rq_disk == bio->bi_bdev->bd_disk &&
61 !rq->waiting && !rq->special)
62 return 1;
63
64 return 0;
65}
66EXPORT_SYMBOL(elv_rq_merge_ok);
67
Coywolf Qi Hunt769db452005-12-28 10:55:49 +010068static inline int elv_try_merge(struct request *__rq, struct bio *bio)
Linus Torvalds1da177e2005-04-16 15:20:36 -070069{
70 int ret = ELEVATOR_NO_MERGE;
71
72 /*
73 * we can merge and sequence is ok, check if it's possible
74 */
75 if (elv_rq_merge_ok(__rq, bio)) {
76 if (__rq->sector + __rq->nr_sectors == bio->bi_sector)
77 ret = ELEVATOR_BACK_MERGE;
78 else if (__rq->sector - bio_sectors(bio) == bio->bi_sector)
79 ret = ELEVATOR_FRONT_MERGE;
80 }
81
82 return ret;
83}
Linus Torvalds1da177e2005-04-16 15:20:36 -070084
Linus Torvalds1da177e2005-04-16 15:20:36 -070085static struct elevator_type *elevator_find(const char *name)
86{
87 struct elevator_type *e = NULL;
88 struct list_head *entry;
89
Linus Torvalds1da177e2005-04-16 15:20:36 -070090 list_for_each(entry, &elv_list) {
91 struct elevator_type *__e;
92
93 __e = list_entry(entry, struct elevator_type, list);
94
95 if (!strcmp(__e->elevator_name, name)) {
96 e = __e;
97 break;
98 }
99 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700100
101 return e;
102}
103
104static void elevator_put(struct elevator_type *e)
105{
106 module_put(e->elevator_owner);
107}
108
109static struct elevator_type *elevator_get(const char *name)
110{
Tejun Heo2824bc932005-10-20 10:56:41 +0200111 struct elevator_type *e;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700112
Tejun Heo2824bc932005-10-20 10:56:41 +0200113 spin_lock_irq(&elv_list_lock);
114
115 e = elevator_find(name);
116 if (e && !try_module_get(e->elevator_owner))
117 e = NULL;
118
119 spin_unlock_irq(&elv_list_lock);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700120
121 return e;
122}
123
Al Viro3d1ab402006-03-18 18:35:43 -0500124static int elevator_attach(request_queue_t *q, struct elevator_queue *eq)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700125{
126 int ret = 0;
127
Linus Torvalds1da177e2005-04-16 15:20:36 -0700128 q->elevator = eq;
129
130 if (eq->ops->elevator_init_fn)
131 ret = eq->ops->elevator_init_fn(q, eq);
132
133 return ret;
134}
135
136static char chosen_elevator[16];
137
Nate Diller5f003972006-01-24 10:07:58 +0100138static int __init elevator_setup(char *str)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700139{
Chuck Ebbert752a3b72006-01-16 09:47:37 +0100140 /*
141 * Be backwards-compatible with previous kernels, so users
142 * won't get the wrong elevator.
143 */
Nate Diller5f003972006-01-24 10:07:58 +0100144 if (!strcmp(str, "as"))
Chuck Ebbert752a3b72006-01-16 09:47:37 +0100145 strcpy(chosen_elevator, "anticipatory");
Zachary Amsdencff3ba22005-11-09 13:24:20 +0100146 else
Nate Diller5f003972006-01-24 10:07:58 +0100147 strncpy(chosen_elevator, str, sizeof(chosen_elevator) - 1);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700148 return 0;
149}
150
151__setup("elevator=", elevator_setup);
152
Al Viro3d1ab402006-03-18 18:35:43 -0500153static struct kobj_type elv_ktype;
154
155static elevator_t *elevator_alloc(struct elevator_type *e)
156{
157 elevator_t *eq = kmalloc(sizeof(elevator_t), GFP_KERNEL);
158 if (eq) {
159 memset(eq, 0, sizeof(*eq));
160 eq->ops = &e->ops;
161 eq->elevator_type = e;
162 kobject_init(&eq->kobj);
163 snprintf(eq->kobj.name, KOBJ_NAME_LEN, "%s", "iosched");
164 eq->kobj.ktype = &elv_ktype;
165 mutex_init(&eq->sysfs_lock);
166 } else {
167 elevator_put(e);
168 }
169 return eq;
170}
171
172static void elevator_release(struct kobject *kobj)
173{
174 elevator_t *e = container_of(kobj, elevator_t, kobj);
175 elevator_put(e->elevator_type);
176 kfree(e);
177}
178
Linus Torvalds1da177e2005-04-16 15:20:36 -0700179int elevator_init(request_queue_t *q, char *name)
180{
181 struct elevator_type *e = NULL;
182 struct elevator_queue *eq;
183 int ret = 0;
184
Tejun Heocb98fc82005-10-28 08:29:39 +0200185 INIT_LIST_HEAD(&q->queue_head);
186 q->last_merge = NULL;
187 q->end_sector = 0;
188 q->boundary_rq = NULL;
Tejun Heocb98fc82005-10-28 08:29:39 +0200189
Nate Diller5f003972006-01-24 10:07:58 +0100190 if (name && !(e = elevator_get(name)))
Linus Torvalds1da177e2005-04-16 15:20:36 -0700191 return -EINVAL;
192
Nate Diller248d5ca2006-01-24 10:09:14 +0100193 if (!e && *chosen_elevator && !(e = elevator_get(chosen_elevator)))
194 printk("I/O scheduler %s not found\n", chosen_elevator);
195
196 if (!e && !(e = elevator_get(CONFIG_DEFAULT_IOSCHED))) {
197 printk("Default I/O scheduler not found, using no-op\n");
198 e = elevator_get("noop");
Nate Diller5f003972006-01-24 10:07:58 +0100199 }
200
Al Viro3d1ab402006-03-18 18:35:43 -0500201 eq = elevator_alloc(e);
202 if (!eq)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700203 return -ENOMEM;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700204
Al Viro3d1ab402006-03-18 18:35:43 -0500205 ret = elevator_attach(q, eq);
206 if (ret)
207 kobject_put(&eq->kobj);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700208
209 return ret;
210}
211
212void elevator_exit(elevator_t *e)
213{
Al Viro3d1ab402006-03-18 18:35:43 -0500214 mutex_lock(&e->sysfs_lock);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700215 if (e->ops->elevator_exit_fn)
216 e->ops->elevator_exit_fn(e);
Al Viro3d1ab402006-03-18 18:35:43 -0500217 e->ops = NULL;
218 mutex_unlock(&e->sysfs_lock);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700219
Al Viro3d1ab402006-03-18 18:35:43 -0500220 kobject_put(&e->kobj);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700221}
222
Tejun Heo8922e162005-10-20 16:23:44 +0200223/*
224 * Insert rq into dispatch queue of q. Queue lock must be held on
225 * entry. If sort != 0, rq is sort-inserted; otherwise, rq will be
226 * appended to the dispatch queue. To be used by specific elevators.
227 */
Jens Axboe1b47f532005-10-20 16:37:00 +0200228void elv_dispatch_sort(request_queue_t *q, struct request *rq)
Tejun Heo8922e162005-10-20 16:23:44 +0200229{
230 sector_t boundary;
Tejun Heo8922e162005-10-20 16:23:44 +0200231 struct list_head *entry;
232
Tejun Heo06b86242005-10-20 16:46:23 +0200233 if (q->last_merge == rq)
234 q->last_merge = NULL;
Tejun Heo15853af2005-11-10 08:52:05 +0100235 q->nr_sorted--;
Tejun Heo06b86242005-10-20 16:46:23 +0200236
Jens Axboe1b47f532005-10-20 16:37:00 +0200237 boundary = q->end_sector;
Tejun Heocb198332005-10-24 08:35:58 +0200238
Tejun Heo8922e162005-10-20 16:23:44 +0200239 list_for_each_prev(entry, &q->queue_head) {
240 struct request *pos = list_entry_rq(entry);
241
242 if (pos->flags & (REQ_SOFTBARRIER|REQ_HARDBARRIER|REQ_STARTED))
243 break;
244 if (rq->sector >= boundary) {
245 if (pos->sector < boundary)
246 continue;
247 } else {
248 if (pos->sector >= boundary)
249 break;
250 }
251 if (rq->sector >= pos->sector)
252 break;
253 }
254
255 list_add(&rq->queuelist, entry);
256}
257
Linus Torvalds1da177e2005-04-16 15:20:36 -0700258int elv_merge(request_queue_t *q, struct request **req, struct bio *bio)
259{
260 elevator_t *e = q->elevator;
Tejun Heo06b86242005-10-20 16:46:23 +0200261 int ret;
262
263 if (q->last_merge) {
264 ret = elv_try_merge(q->last_merge, bio);
265 if (ret != ELEVATOR_NO_MERGE) {
266 *req = q->last_merge;
267 return ret;
268 }
269 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700270
271 if (e->ops->elevator_merge_fn)
272 return e->ops->elevator_merge_fn(q, req, bio);
273
274 return ELEVATOR_NO_MERGE;
275}
276
277void elv_merged_request(request_queue_t *q, struct request *rq)
278{
279 elevator_t *e = q->elevator;
280
281 if (e->ops->elevator_merged_fn)
282 e->ops->elevator_merged_fn(q, rq);
Tejun Heo06b86242005-10-20 16:46:23 +0200283
284 q->last_merge = rq;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700285}
286
287void elv_merge_requests(request_queue_t *q, struct request *rq,
288 struct request *next)
289{
290 elevator_t *e = q->elevator;
291
Linus Torvalds1da177e2005-04-16 15:20:36 -0700292 if (e->ops->elevator_merge_req_fn)
293 e->ops->elevator_merge_req_fn(q, rq, next);
Tejun Heo15853af2005-11-10 08:52:05 +0100294 q->nr_sorted--;
Tejun Heo06b86242005-10-20 16:46:23 +0200295
296 q->last_merge = rq;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700297}
298
Tejun Heo8922e162005-10-20 16:23:44 +0200299void elv_requeue_request(request_queue_t *q, struct request *rq)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700300{
301 elevator_t *e = q->elevator;
302
303 /*
304 * it already went through dequeue, we need to decrement the
305 * in_flight count again
306 */
Tejun Heo8922e162005-10-20 16:23:44 +0200307 if (blk_account_rq(rq)) {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700308 q->in_flight--;
Tejun Heo8922e162005-10-20 16:23:44 +0200309 if (blk_sorted_rq(rq) && e->ops->elevator_deactivate_req_fn)
310 e->ops->elevator_deactivate_req_fn(q, rq);
311 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700312
313 rq->flags &= ~REQ_STARTED;
314
Tejun Heo30e96562006-02-08 01:01:31 -0800315 elv_insert(q, rq, ELEVATOR_INSERT_REQUEUE);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700316}
317
Tejun Heo15853af2005-11-10 08:52:05 +0100318static void elv_drain_elevator(request_queue_t *q)
319{
320 static int printed;
321 while (q->elevator->ops->elevator_dispatch_fn(q, 1))
322 ;
323 if (q->nr_sorted == 0)
324 return;
325 if (printed++ < 10) {
326 printk(KERN_ERR "%s: forced dispatching is broken "
327 "(nr_sorted=%u), please report this\n",
328 q->elevator->elevator_type->elevator_name, q->nr_sorted);
329 }
330}
331
Tejun Heo30e96562006-02-08 01:01:31 -0800332void elv_insert(request_queue_t *q, struct request *rq, int where)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700333{
Tejun Heo797e7db2006-01-06 09:51:03 +0100334 struct list_head *pos;
335 unsigned ordseq;
336
Jens Axboe2056a782006-03-23 20:00:26 +0100337 blk_add_trace_rq(q, rq, BLK_TA_INSERT);
338
Linus Torvalds1da177e2005-04-16 15:20:36 -0700339 rq->q = q;
340
Tejun Heo8922e162005-10-20 16:23:44 +0200341 switch (where) {
342 case ELEVATOR_INSERT_FRONT:
343 rq->flags |= REQ_SOFTBARRIER;
344
345 list_add(&rq->queuelist, &q->queue_head);
346 break;
347
348 case ELEVATOR_INSERT_BACK:
349 rq->flags |= REQ_SOFTBARRIER;
Tejun Heo15853af2005-11-10 08:52:05 +0100350 elv_drain_elevator(q);
Tejun Heo8922e162005-10-20 16:23:44 +0200351 list_add_tail(&rq->queuelist, &q->queue_head);
352 /*
353 * We kick the queue here for the following reasons.
354 * - The elevator might have returned NULL previously
355 * to delay requests and returned them now. As the
356 * queue wasn't empty before this request, ll_rw_blk
357 * won't run the queue on return, resulting in hang.
358 * - Usually, back inserted requests won't be merged
359 * with anything. There's no point in delaying queue
360 * processing.
361 */
362 blk_remove_plug(q);
363 q->request_fn(q);
364 break;
365
366 case ELEVATOR_INSERT_SORT:
367 BUG_ON(!blk_fs_request(rq));
368 rq->flags |= REQ_SORTED;
Tejun Heo15853af2005-11-10 08:52:05 +0100369 q->nr_sorted++;
Tejun Heo06b86242005-10-20 16:46:23 +0200370 if (q->last_merge == NULL && rq_mergeable(rq))
371 q->last_merge = rq;
Tejun Heoca235092005-11-01 17:23:49 +0900372 /*
373 * Some ioscheds (cfq) run q->request_fn directly, so
374 * rq cannot be accessed after calling
375 * elevator_add_req_fn.
376 */
377 q->elevator->ops->elevator_add_req_fn(q, rq);
Tejun Heo8922e162005-10-20 16:23:44 +0200378 break;
379
Tejun Heo797e7db2006-01-06 09:51:03 +0100380 case ELEVATOR_INSERT_REQUEUE:
381 /*
382 * If ordered flush isn't in progress, we do front
383 * insertion; otherwise, requests should be requeued
384 * in ordseq order.
385 */
386 rq->flags |= REQ_SOFTBARRIER;
387
388 if (q->ordseq == 0) {
389 list_add(&rq->queuelist, &q->queue_head);
390 break;
391 }
392
393 ordseq = blk_ordered_req_seq(rq);
394
395 list_for_each(pos, &q->queue_head) {
396 struct request *pos_rq = list_entry_rq(pos);
397 if (ordseq <= blk_ordered_req_seq(pos_rq))
398 break;
399 }
400
401 list_add_tail(&rq->queuelist, pos);
402 break;
403
Tejun Heo8922e162005-10-20 16:23:44 +0200404 default:
405 printk(KERN_ERR "%s: bad insertion point %d\n",
406 __FUNCTION__, where);
407 BUG();
408 }
409
410 if (blk_queue_plugged(q)) {
411 int nrq = q->rq.count[READ] + q->rq.count[WRITE]
412 - q->in_flight;
413
414 if (nrq >= q->unplug_thresh)
415 __generic_unplug_device(q);
416 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700417}
418
Tejun Heo30e96562006-02-08 01:01:31 -0800419void __elv_add_request(request_queue_t *q, struct request *rq, int where,
420 int plug)
421{
422 if (q->ordcolor)
423 rq->flags |= REQ_ORDERED_COLOR;
424
425 if (rq->flags & (REQ_SOFTBARRIER | REQ_HARDBARRIER)) {
426 /*
427 * toggle ordered color
428 */
429 if (blk_barrier_rq(rq))
430 q->ordcolor ^= 1;
431
432 /*
433 * barriers implicitly indicate back insertion
434 */
435 if (where == ELEVATOR_INSERT_SORT)
436 where = ELEVATOR_INSERT_BACK;
437
438 /*
439 * this request is scheduling boundary, update
440 * end_sector
441 */
442 if (blk_fs_request(rq)) {
443 q->end_sector = rq_end_sector(rq);
444 q->boundary_rq = rq;
445 }
446 } else if (!(rq->flags & REQ_ELVPRIV) && where == ELEVATOR_INSERT_SORT)
447 where = ELEVATOR_INSERT_BACK;
448
449 if (plug)
450 blk_plug_device(q);
451
452 elv_insert(q, rq, where);
453}
454
Linus Torvalds1da177e2005-04-16 15:20:36 -0700455void elv_add_request(request_queue_t *q, struct request *rq, int where,
456 int plug)
457{
458 unsigned long flags;
459
460 spin_lock_irqsave(q->queue_lock, flags);
461 __elv_add_request(q, rq, where, plug);
462 spin_unlock_irqrestore(q->queue_lock, flags);
463}
464
465static inline struct request *__elv_next_request(request_queue_t *q)
466{
Tejun Heo8922e162005-10-20 16:23:44 +0200467 struct request *rq;
468
Tejun Heo797e7db2006-01-06 09:51:03 +0100469 while (1) {
470 while (!list_empty(&q->queue_head)) {
471 rq = list_entry_rq(q->queue_head.next);
472 if (blk_do_ordered(q, &rq))
473 return rq;
474 }
Tejun Heo8922e162005-10-20 16:23:44 +0200475
Tejun Heo797e7db2006-01-06 09:51:03 +0100476 if (!q->elevator->ops->elevator_dispatch_fn(q, 0))
477 return NULL;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700478 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700479}
480
481struct request *elv_next_request(request_queue_t *q)
482{
483 struct request *rq;
484 int ret;
485
486 while ((rq = __elv_next_request(q)) != NULL) {
Tejun Heo8922e162005-10-20 16:23:44 +0200487 if (!(rq->flags & REQ_STARTED)) {
488 elevator_t *e = q->elevator;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700489
Tejun Heo8922e162005-10-20 16:23:44 +0200490 /*
491 * This is the first time the device driver
492 * sees this request (possibly after
493 * requeueing). Notify IO scheduler.
494 */
495 if (blk_sorted_rq(rq) &&
496 e->ops->elevator_activate_req_fn)
497 e->ops->elevator_activate_req_fn(q, rq);
498
499 /*
500 * just mark as started even if we don't start
501 * it, a request that has been delayed should
502 * not be passed by new incoming requests
503 */
504 rq->flags |= REQ_STARTED;
Jens Axboe2056a782006-03-23 20:00:26 +0100505 blk_add_trace_rq(q, rq, BLK_TA_ISSUE);
Tejun Heo8922e162005-10-20 16:23:44 +0200506 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700507
Tejun Heo8922e162005-10-20 16:23:44 +0200508 if (!q->boundary_rq || q->boundary_rq == rq) {
Jens Axboe1b47f532005-10-20 16:37:00 +0200509 q->end_sector = rq_end_sector(rq);
Tejun Heo8922e162005-10-20 16:23:44 +0200510 q->boundary_rq = NULL;
511 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700512
513 if ((rq->flags & REQ_DONTPREP) || !q->prep_rq_fn)
514 break;
515
516 ret = q->prep_rq_fn(q, rq);
517 if (ret == BLKPREP_OK) {
518 break;
519 } else if (ret == BLKPREP_DEFER) {
Tejun Heo 2e759cd2005-04-24 02:04:21 -0500520 /*
521 * the request may have been (partially) prepped.
522 * we need to keep this request in the front to
Tejun Heo8922e162005-10-20 16:23:44 +0200523 * avoid resource deadlock. REQ_STARTED will
524 * prevent other fs requests from passing this one.
Tejun Heo 2e759cd2005-04-24 02:04:21 -0500525 */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700526 rq = NULL;
527 break;
528 } else if (ret == BLKPREP_KILL) {
529 int nr_bytes = rq->hard_nr_sectors << 9;
530
531 if (!nr_bytes)
532 nr_bytes = rq->data_len;
533
534 blkdev_dequeue_request(rq);
535 rq->flags |= REQ_QUIET;
536 end_that_request_chunk(rq, 0, nr_bytes);
Tejun Heo8ffdc652006-01-06 09:49:03 +0100537 end_that_request_last(rq, 0);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700538 } else {
539 printk(KERN_ERR "%s: bad return=%d\n", __FUNCTION__,
540 ret);
541 break;
542 }
543 }
544
545 return rq;
546}
547
Tejun Heo8922e162005-10-20 16:23:44 +0200548void elv_dequeue_request(request_queue_t *q, struct request *rq)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700549{
Tejun Heo8922e162005-10-20 16:23:44 +0200550 BUG_ON(list_empty(&rq->queuelist));
551
552 list_del_init(&rq->queuelist);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700553
554 /*
555 * the time frame between a request being removed from the lists
556 * and to it is freed is accounted as io that is in progress at
Tejun Heo8922e162005-10-20 16:23:44 +0200557 * the driver side.
Linus Torvalds1da177e2005-04-16 15:20:36 -0700558 */
559 if (blk_account_rq(rq))
560 q->in_flight++;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700561}
562
563int elv_queue_empty(request_queue_t *q)
564{
565 elevator_t *e = q->elevator;
566
Tejun Heo8922e162005-10-20 16:23:44 +0200567 if (!list_empty(&q->queue_head))
568 return 0;
569
Linus Torvalds1da177e2005-04-16 15:20:36 -0700570 if (e->ops->elevator_queue_empty_fn)
571 return e->ops->elevator_queue_empty_fn(q);
572
Tejun Heo8922e162005-10-20 16:23:44 +0200573 return 1;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700574}
575
576struct request *elv_latter_request(request_queue_t *q, struct request *rq)
577{
Linus Torvalds1da177e2005-04-16 15:20:36 -0700578 elevator_t *e = q->elevator;
579
580 if (e->ops->elevator_latter_req_fn)
581 return e->ops->elevator_latter_req_fn(q, rq);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700582 return NULL;
583}
584
585struct request *elv_former_request(request_queue_t *q, struct request *rq)
586{
Linus Torvalds1da177e2005-04-16 15:20:36 -0700587 elevator_t *e = q->elevator;
588
589 if (e->ops->elevator_former_req_fn)
590 return e->ops->elevator_former_req_fn(q, rq);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700591 return NULL;
592}
593
Jens Axboe22e2c502005-06-27 10:55:12 +0200594int elv_set_request(request_queue_t *q, struct request *rq, struct bio *bio,
Al Viro8267e262005-10-21 03:20:53 -0400595 gfp_t gfp_mask)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700596{
597 elevator_t *e = q->elevator;
598
599 if (e->ops->elevator_set_req_fn)
Jens Axboe22e2c502005-06-27 10:55:12 +0200600 return e->ops->elevator_set_req_fn(q, rq, bio, gfp_mask);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700601
602 rq->elevator_private = NULL;
603 return 0;
604}
605
606void elv_put_request(request_queue_t *q, struct request *rq)
607{
608 elevator_t *e = q->elevator;
609
610 if (e->ops->elevator_put_req_fn)
611 e->ops->elevator_put_req_fn(q, rq);
612}
613
Jens Axboe22e2c502005-06-27 10:55:12 +0200614int elv_may_queue(request_queue_t *q, int rw, struct bio *bio)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700615{
616 elevator_t *e = q->elevator;
617
618 if (e->ops->elevator_may_queue_fn)
Jens Axboe22e2c502005-06-27 10:55:12 +0200619 return e->ops->elevator_may_queue_fn(q, rw, bio);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700620
621 return ELV_MQUEUE_MAY;
622}
623
624void elv_completed_request(request_queue_t *q, struct request *rq)
625{
626 elevator_t *e = q->elevator;
627
628 /*
629 * request is released from the driver, io must be done
630 */
Tejun Heo8922e162005-10-20 16:23:44 +0200631 if (blk_account_rq(rq)) {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700632 q->in_flight--;
Tejun Heo1bc691d2006-01-12 15:39:26 +0100633 if (blk_sorted_rq(rq) && e->ops->elevator_completed_req_fn)
634 e->ops->elevator_completed_req_fn(q, rq);
635 }
Tejun Heo797e7db2006-01-06 09:51:03 +0100636
Tejun Heo1bc691d2006-01-12 15:39:26 +0100637 /*
638 * Check if the queue is waiting for fs requests to be
639 * drained for flush sequence.
640 */
641 if (unlikely(q->ordseq)) {
642 struct request *first_rq = list_entry_rq(q->queue_head.next);
643 if (q->in_flight == 0 &&
Tejun Heo797e7db2006-01-06 09:51:03 +0100644 blk_ordered_cur_seq(q) == QUEUE_ORDSEQ_DRAIN &&
645 blk_ordered_req_seq(first_rq) > QUEUE_ORDSEQ_DRAIN) {
646 blk_ordered_complete_seq(q, QUEUE_ORDSEQ_DRAIN, 0);
647 q->request_fn(q);
648 }
Tejun Heo8922e162005-10-20 16:23:44 +0200649 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700650}
651
Al Viro3d1ab402006-03-18 18:35:43 -0500652#define to_elv(atr) container_of((atr), struct elv_fs_entry, attr)
653
654static ssize_t
655elv_attr_show(struct kobject *kobj, struct attribute *attr, char *page)
656{
657 elevator_t *e = container_of(kobj, elevator_t, kobj);
658 struct elv_fs_entry *entry = to_elv(attr);
659 ssize_t error;
660
661 if (!entry->show)
662 return -EIO;
663
664 mutex_lock(&e->sysfs_lock);
665 error = e->ops ? entry->show(e, page) : -ENOENT;
666 mutex_unlock(&e->sysfs_lock);
667 return error;
668}
669
670static ssize_t
671elv_attr_store(struct kobject *kobj, struct attribute *attr,
672 const char *page, size_t length)
673{
674 elevator_t *e = container_of(kobj, elevator_t, kobj);
675 struct elv_fs_entry *entry = to_elv(attr);
676 ssize_t error;
677
678 if (!entry->store)
679 return -EIO;
680
681 mutex_lock(&e->sysfs_lock);
682 error = e->ops ? entry->store(e, page, length) : -ENOENT;
683 mutex_unlock(&e->sysfs_lock);
684 return error;
685}
686
687static struct sysfs_ops elv_sysfs_ops = {
688 .show = elv_attr_show,
689 .store = elv_attr_store,
690};
691
692static struct kobj_type elv_ktype = {
693 .sysfs_ops = &elv_sysfs_ops,
694 .release = elevator_release,
695};
696
Linus Torvalds1da177e2005-04-16 15:20:36 -0700697int elv_register_queue(struct request_queue *q)
698{
699 elevator_t *e = q->elevator;
Al Viro3d1ab402006-03-18 18:35:43 -0500700 int error;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700701
Al Viro3d1ab402006-03-18 18:35:43 -0500702 e->kobj.parent = &q->kobj;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700703
Al Viro3d1ab402006-03-18 18:35:43 -0500704 error = kobject_add(&e->kobj);
705 if (!error) {
Al Viroe572ec72006-03-18 22:27:18 -0500706 struct elv_fs_entry *attr = e->elevator_type->elevator_attrs;
Al Viro3d1ab402006-03-18 18:35:43 -0500707 if (attr) {
Al Viroe572ec72006-03-18 22:27:18 -0500708 while (attr->attr.name) {
709 if (sysfs_create_file(&e->kobj, &attr->attr))
Al Viro3d1ab402006-03-18 18:35:43 -0500710 break;
Al Viroe572ec72006-03-18 22:27:18 -0500711 attr++;
Al Viro3d1ab402006-03-18 18:35:43 -0500712 }
713 }
714 kobject_uevent(&e->kobj, KOBJ_ADD);
715 }
716 return error;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700717}
718
719void elv_unregister_queue(struct request_queue *q)
720{
721 if (q) {
722 elevator_t *e = q->elevator;
Al Viro3d1ab402006-03-18 18:35:43 -0500723 kobject_uevent(&e->kobj, KOBJ_REMOVE);
724 kobject_del(&e->kobj);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700725 }
726}
727
728int elv_register(struct elevator_type *e)
729{
Tejun Heo2824bc932005-10-20 10:56:41 +0200730 spin_lock_irq(&elv_list_lock);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700731 if (elevator_find(e->elevator_name))
732 BUG();
Linus Torvalds1da177e2005-04-16 15:20:36 -0700733 list_add_tail(&e->list, &elv_list);
734 spin_unlock_irq(&elv_list_lock);
735
736 printk(KERN_INFO "io scheduler %s registered", e->elevator_name);
Nate Diller5f003972006-01-24 10:07:58 +0100737 if (!strcmp(e->elevator_name, chosen_elevator) ||
738 (!*chosen_elevator &&
739 !strcmp(e->elevator_name, CONFIG_DEFAULT_IOSCHED)))
740 printk(" (default)");
Linus Torvalds1da177e2005-04-16 15:20:36 -0700741 printk("\n");
742 return 0;
743}
744EXPORT_SYMBOL_GPL(elv_register);
745
746void elv_unregister(struct elevator_type *e)
747{
Christoph Hellwig83521d32005-10-30 15:01:39 -0800748 struct task_struct *g, *p;
749
750 /*
751 * Iterate every thread in the process to remove the io contexts.
752 */
Al Viroe17a9482006-03-18 13:21:20 -0500753 if (e->ops.trim) {
754 read_lock(&tasklist_lock);
755 do_each_thread(g, p) {
756 task_lock(p);
757 e->ops.trim(p->io_context);
758 task_unlock(p);
759 } while_each_thread(g, p);
760 read_unlock(&tasklist_lock);
761 }
Christoph Hellwig83521d32005-10-30 15:01:39 -0800762
Linus Torvalds1da177e2005-04-16 15:20:36 -0700763 spin_lock_irq(&elv_list_lock);
764 list_del_init(&e->list);
765 spin_unlock_irq(&elv_list_lock);
766}
767EXPORT_SYMBOL_GPL(elv_unregister);
768
769/*
770 * switch to new_e io scheduler. be careful not to introduce deadlocks -
771 * we don't free the old io scheduler, before we have allocated what we
772 * need for the new one. this way we have a chance of going back to the old
Tejun Heocb98fc82005-10-28 08:29:39 +0200773 * one, if the new one fails init for some reason.
Linus Torvalds1da177e2005-04-16 15:20:36 -0700774 */
Al Viro3d1ab402006-03-18 18:35:43 -0500775static int elevator_switch(request_queue_t *q, struct elevator_type *new_e)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700776{
Tejun Heocb98fc82005-10-28 08:29:39 +0200777 elevator_t *old_elevator, *e;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700778
Tejun Heocb98fc82005-10-28 08:29:39 +0200779 /*
780 * Allocate new elevator
781 */
Al Viro3d1ab402006-03-18 18:35:43 -0500782 e = elevator_alloc(new_e);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700783 if (!e)
Al Viro3d1ab402006-03-18 18:35:43 -0500784 return 0;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700785
786 /*
Tejun Heocb98fc82005-10-28 08:29:39 +0200787 * Turn on BYPASS and drain all requests w/ elevator private data
Linus Torvalds1da177e2005-04-16 15:20:36 -0700788 */
Tejun Heocb98fc82005-10-28 08:29:39 +0200789 spin_lock_irq(q->queue_lock);
790
Jens Axboe64521d12005-10-28 08:30:39 +0200791 set_bit(QUEUE_FLAG_ELVSWITCH, &q->queue_flags);
Tejun Heocb98fc82005-10-28 08:29:39 +0200792
Tejun Heo15853af2005-11-10 08:52:05 +0100793 elv_drain_elevator(q);
Tejun Heocb98fc82005-10-28 08:29:39 +0200794
795 while (q->rq.elvpriv) {
Tejun Heo407df2a2005-11-10 08:48:21 +0100796 blk_remove_plug(q);
797 q->request_fn(q);
Tejun Heocb98fc82005-10-28 08:29:39 +0200798 spin_unlock_irq(q->queue_lock);
Jens Axboe64521d12005-10-28 08:30:39 +0200799 msleep(10);
Tejun Heocb98fc82005-10-28 08:29:39 +0200800 spin_lock_irq(q->queue_lock);
Tejun Heo15853af2005-11-10 08:52:05 +0100801 elv_drain_elevator(q);
Tejun Heocb98fc82005-10-28 08:29:39 +0200802 }
803
804 spin_unlock_irq(q->queue_lock);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700805
806 /*
807 * unregister old elevator data
808 */
809 elv_unregister_queue(q);
810 old_elevator = q->elevator;
811
812 /*
Linus Torvalds1da177e2005-04-16 15:20:36 -0700813 * attach and start new elevator
814 */
Al Viro3d1ab402006-03-18 18:35:43 -0500815 if (elevator_attach(q, e))
Linus Torvalds1da177e2005-04-16 15:20:36 -0700816 goto fail;
817
818 if (elv_register_queue(q))
819 goto fail_register;
820
821 /*
Tejun Heocb98fc82005-10-28 08:29:39 +0200822 * finally exit old elevator and turn off BYPASS.
Linus Torvalds1da177e2005-04-16 15:20:36 -0700823 */
824 elevator_exit(old_elevator);
Jens Axboe64521d12005-10-28 08:30:39 +0200825 clear_bit(QUEUE_FLAG_ELVSWITCH, &q->queue_flags);
Al Viro3d1ab402006-03-18 18:35:43 -0500826 return 1;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700827
828fail_register:
829 /*
830 * switch failed, exit the new io scheduler and reattach the old
831 * one again (along with re-adding the sysfs dir)
832 */
833 elevator_exit(e);
Tejun Heocb98fc82005-10-28 08:29:39 +0200834 e = NULL;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700835fail:
836 q->elevator = old_elevator;
837 elv_register_queue(q);
Jens Axboe64521d12005-10-28 08:30:39 +0200838 clear_bit(QUEUE_FLAG_ELVSWITCH, &q->queue_flags);
Al Viro3d1ab402006-03-18 18:35:43 -0500839 if (e)
840 kobject_put(&e->kobj);
841 return 0;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700842}
843
844ssize_t elv_iosched_store(request_queue_t *q, const char *name, size_t count)
845{
846 char elevator_name[ELV_NAME_MAX];
Tejun Heobe561232005-11-10 08:55:01 +0100847 size_t len;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700848 struct elevator_type *e;
849
Tejun Heobe561232005-11-10 08:55:01 +0100850 elevator_name[sizeof(elevator_name) - 1] = '\0';
851 strncpy(elevator_name, name, sizeof(elevator_name) - 1);
852 len = strlen(elevator_name);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700853
Tejun Heobe561232005-11-10 08:55:01 +0100854 if (len && elevator_name[len - 1] == '\n')
855 elevator_name[len - 1] = '\0';
Linus Torvalds1da177e2005-04-16 15:20:36 -0700856
857 e = elevator_get(elevator_name);
858 if (!e) {
859 printk(KERN_ERR "elevator: type %s not found\n", elevator_name);
860 return -EINVAL;
861 }
862
Nate Diller2ca7d932005-10-30 15:02:24 -0800863 if (!strcmp(elevator_name, q->elevator->elevator_type->elevator_name)) {
864 elevator_put(e);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700865 return count;
Nate Diller2ca7d932005-10-30 15:02:24 -0800866 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700867
Al Viro3d1ab402006-03-18 18:35:43 -0500868 if (!elevator_switch(q, e))
869 printk(KERN_ERR "elevator: switch to %s failed\n",elevator_name);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700870 return count;
871}
872
873ssize_t elv_iosched_show(request_queue_t *q, char *name)
874{
875 elevator_t *e = q->elevator;
876 struct elevator_type *elv = e->elevator_type;
877 struct list_head *entry;
878 int len = 0;
879
880 spin_lock_irq(q->queue_lock);
881 list_for_each(entry, &elv_list) {
882 struct elevator_type *__e;
883
884 __e = list_entry(entry, struct elevator_type, list);
885 if (!strcmp(elv->elevator_name, __e->elevator_name))
886 len += sprintf(name+len, "[%s] ", elv->elevator_name);
887 else
888 len += sprintf(name+len, "%s ", __e->elevator_name);
889 }
890 spin_unlock_irq(q->queue_lock);
891
892 len += sprintf(len+name, "\n");
893 return len;
894}
895
Jens Axboe1b47f532005-10-20 16:37:00 +0200896EXPORT_SYMBOL(elv_dispatch_sort);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700897EXPORT_SYMBOL(elv_add_request);
898EXPORT_SYMBOL(__elv_add_request);
899EXPORT_SYMBOL(elv_requeue_request);
900EXPORT_SYMBOL(elv_next_request);
Tejun Heo8922e162005-10-20 16:23:44 +0200901EXPORT_SYMBOL(elv_dequeue_request);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700902EXPORT_SYMBOL(elv_queue_empty);
903EXPORT_SYMBOL(elv_completed_request);
904EXPORT_SYMBOL(elevator_exit);
905EXPORT_SYMBOL(elevator_init);