blob: 04518921db31bb66c115752d62c2a35df11e98e3 [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 *
Jens Axboe0fe23472006-09-04 15:41:16 +02006 * 30042000 Jens Axboe <axboe@kernel.dk> :
Linus Torvalds1da177e2005-04-16 15:20:36 -07007 *
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>
Linus Torvalds1da177e2005-04-16 15:20:36 -070030#include <linux/module.h>
31#include <linux/slab.h>
32#include <linux/init.h>
33#include <linux/compiler.h>
Tejun Heocb98fc82005-10-28 08:29:39 +020034#include <linux/delay.h>
Jens Axboe2056a782006-03-23 20:00:26 +010035#include <linux/blktrace_api.h>
Jens Axboe98170642006-07-28 09:23:08 +020036#include <linux/hash.h>
Jens Axboe0835da62008-08-26 09:15:47 +020037#include <linux/uaccess.h>
Linus Torvalds1da177e2005-04-16 15:20:36 -070038
Jens Axboe242f9dc2008-09-14 05:55:09 -070039#include "blk.h"
40
Linus Torvalds1da177e2005-04-16 15:20:36 -070041static DEFINE_SPINLOCK(elv_list_lock);
42static LIST_HEAD(elv_list);
43
44/*
Jens Axboe98170642006-07-28 09:23:08 +020045 * Merge hash stuff.
46 */
47static const int elv_hash_shift = 6;
48#define ELV_HASH_BLOCK(sec) ((sec) >> 3)
Jens Axboe4eb166d2008-02-01 00:37:27 +010049#define ELV_HASH_FN(sec) \
50 (hash_long(ELV_HASH_BLOCK((sec)), elv_hash_shift))
Jens Axboe98170642006-07-28 09:23:08 +020051#define ELV_HASH_ENTRIES (1 << elv_hash_shift)
52#define rq_hash_key(rq) ((rq)->sector + (rq)->nr_sectors)
53#define ELV_ON_HASH(rq) (!hlist_unhashed(&(rq)->hash))
54
55/*
Jens Axboeda775262006-12-20 11:04:12 +010056 * Query io scheduler to see if the current process issuing bio may be
57 * merged with rq.
58 */
59static int elv_iosched_allow_merge(struct request *rq, struct bio *bio)
60{
Jens Axboe165125e2007-07-24 09:28:11 +020061 struct request_queue *q = rq->q;
Jens Axboeda775262006-12-20 11:04:12 +010062 elevator_t *e = q->elevator;
63
64 if (e->ops->elevator_allow_merge_fn)
65 return e->ops->elevator_allow_merge_fn(q, rq, bio);
66
67 return 1;
68}
69
70/*
Linus Torvalds1da177e2005-04-16 15:20:36 -070071 * can we safely merge with this request?
72 */
Adrian Bunk72ed0bf2008-04-29 09:49:05 +020073int elv_rq_merge_ok(struct request *rq, struct bio *bio)
Linus Torvalds1da177e2005-04-16 15:20:36 -070074{
75 if (!rq_mergeable(rq))
76 return 0;
77
78 /*
David Woodhousee17fc0a2008-08-09 16:42:20 +010079 * Don't merge file system requests and discard requests
80 */
81 if (bio_discard(bio) != bio_discard(rq->bio))
82 return 0;
83
84 /*
Linus Torvalds1da177e2005-04-16 15:20:36 -070085 * different data direction or already started, don't merge
86 */
87 if (bio_data_dir(bio) != rq_data_dir(rq))
88 return 0;
89
90 /*
Jens Axboeda775262006-12-20 11:04:12 +010091 * must be same device and not a special request
Linus Torvalds1da177e2005-04-16 15:20:36 -070092 */
Jens Axboebb4067e2006-12-21 21:20:01 +010093 if (rq->rq_disk != bio->bi_bdev->bd_disk || rq->special)
Jens Axboeda775262006-12-20 11:04:12 +010094 return 0;
Linus Torvalds1da177e2005-04-16 15:20:36 -070095
Martin K. Petersen7ba1ba12008-06-30 20:04:41 +020096 /*
97 * only merge integrity protected bio into ditto rq
98 */
99 if (bio_integrity(bio) != blk_integrity_rq(rq))
100 return 0;
101
Jens Axboeda775262006-12-20 11:04:12 +0100102 if (!elv_iosched_allow_merge(rq, bio))
103 return 0;
104
105 return 1;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700106}
107EXPORT_SYMBOL(elv_rq_merge_ok);
108
Coywolf Qi Hunt769db452005-12-28 10:55:49 +0100109static inline int elv_try_merge(struct request *__rq, struct bio *bio)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700110{
111 int ret = ELEVATOR_NO_MERGE;
112
113 /*
114 * we can merge and sequence is ok, check if it's possible
115 */
116 if (elv_rq_merge_ok(__rq, bio)) {
117 if (__rq->sector + __rq->nr_sectors == bio->bi_sector)
118 ret = ELEVATOR_BACK_MERGE;
119 else if (__rq->sector - bio_sectors(bio) == bio->bi_sector)
120 ret = ELEVATOR_FRONT_MERGE;
121 }
122
123 return ret;
124}
Linus Torvalds1da177e2005-04-16 15:20:36 -0700125
Linus Torvalds1da177e2005-04-16 15:20:36 -0700126static struct elevator_type *elevator_find(const char *name)
127{
Vasily Tarasova22b1692006-10-11 09:24:27 +0200128 struct elevator_type *e;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700129
Matthias Kaehlcke70cee262007-07-10 12:26:24 +0200130 list_for_each_entry(e, &elv_list, list) {
Vasily Tarasova22b1692006-10-11 09:24:27 +0200131 if (!strcmp(e->elevator_name, name))
132 return e;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700133 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700134
Vasily Tarasova22b1692006-10-11 09:24:27 +0200135 return NULL;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700136}
137
138static void elevator_put(struct elevator_type *e)
139{
140 module_put(e->elevator_owner);
141}
142
143static struct elevator_type *elevator_get(const char *name)
144{
Tejun Heo2824bc932005-10-20 10:56:41 +0200145 struct elevator_type *e;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700146
Jens Axboe2a12dcd2007-04-26 14:41:53 +0200147 spin_lock(&elv_list_lock);
Tejun Heo2824bc932005-10-20 10:56:41 +0200148
149 e = elevator_find(name);
Jens Axboee1640942008-02-19 10:20:37 +0100150 if (!e) {
151 char elv[ELV_NAME_MAX + strlen("-iosched")];
152
153 spin_unlock(&elv_list_lock);
154
155 if (!strcmp(name, "anticipatory"))
156 sprintf(elv, "as-iosched");
157 else
158 sprintf(elv, "%s-iosched", name);
159
maximilian attemse180f592008-07-01 09:42:47 +0200160 request_module("%s", elv);
Jens Axboee1640942008-02-19 10:20:37 +0100161 spin_lock(&elv_list_lock);
162 e = elevator_find(name);
163 }
164
Tejun Heo2824bc932005-10-20 10:56:41 +0200165 if (e && !try_module_get(e->elevator_owner))
166 e = NULL;
167
Jens Axboe2a12dcd2007-04-26 14:41:53 +0200168 spin_unlock(&elv_list_lock);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700169
170 return e;
171}
172
Jens Axboe165125e2007-07-24 09:28:11 +0200173static void *elevator_init_queue(struct request_queue *q,
174 struct elevator_queue *eq)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700175{
Jens Axboebb37b942006-12-01 10:42:33 +0100176 return eq->ops->elevator_init_fn(q);
Jens Axboebc1c1162006-06-08 08:49:06 +0200177}
Linus Torvalds1da177e2005-04-16 15:20:36 -0700178
Jens Axboe165125e2007-07-24 09:28:11 +0200179static void elevator_attach(struct request_queue *q, struct elevator_queue *eq,
Jens Axboebc1c1162006-06-08 08:49:06 +0200180 void *data)
181{
Linus Torvalds1da177e2005-04-16 15:20:36 -0700182 q->elevator = eq;
Jens Axboebc1c1162006-06-08 08:49:06 +0200183 eq->elevator_data = data;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700184}
185
186static char chosen_elevator[16];
187
Nate Diller5f003972006-01-24 10:07:58 +0100188static int __init elevator_setup(char *str)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700189{
Chuck Ebbert752a3b72006-01-16 09:47:37 +0100190 /*
191 * Be backwards-compatible with previous kernels, so users
192 * won't get the wrong elevator.
193 */
Nate Diller5f003972006-01-24 10:07:58 +0100194 if (!strcmp(str, "as"))
Chuck Ebbert752a3b72006-01-16 09:47:37 +0100195 strcpy(chosen_elevator, "anticipatory");
Zachary Amsdencff3ba22005-11-09 13:24:20 +0100196 else
Nate Diller5f003972006-01-24 10:07:58 +0100197 strncpy(chosen_elevator, str, sizeof(chosen_elevator) - 1);
OGAWA Hirofumi9b410462006-03-31 02:30:33 -0800198 return 1;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700199}
200
201__setup("elevator=", elevator_setup);
202
Al Viro3d1ab402006-03-18 18:35:43 -0500203static struct kobj_type elv_ktype;
204
Jens Axboe165125e2007-07-24 09:28:11 +0200205static elevator_t *elevator_alloc(struct request_queue *q,
206 struct elevator_type *e)
Al Viro3d1ab402006-03-18 18:35:43 -0500207{
Jens Axboe98170642006-07-28 09:23:08 +0200208 elevator_t *eq;
209 int i;
210
Christoph Lameter94f60302007-07-17 04:03:29 -0700211 eq = kmalloc_node(sizeof(elevator_t), GFP_KERNEL | __GFP_ZERO, q->node);
Jens Axboe98170642006-07-28 09:23:08 +0200212 if (unlikely(!eq))
213 goto err;
214
Jens Axboe98170642006-07-28 09:23:08 +0200215 eq->ops = &e->ops;
216 eq->elevator_type = e;
Greg Kroah-Hartmanf9cb0742007-12-17 23:05:35 -0700217 kobject_init(&eq->kobj, &elv_ktype);
Jens Axboe98170642006-07-28 09:23:08 +0200218 mutex_init(&eq->sysfs_lock);
219
Jens Axboeb5deef92006-07-19 23:39:40 +0200220 eq->hash = kmalloc_node(sizeof(struct hlist_head) * ELV_HASH_ENTRIES,
221 GFP_KERNEL, q->node);
Jens Axboe98170642006-07-28 09:23:08 +0200222 if (!eq->hash)
223 goto err;
224
225 for (i = 0; i < ELV_HASH_ENTRIES; i++)
226 INIT_HLIST_HEAD(&eq->hash[i]);
227
Al Viro3d1ab402006-03-18 18:35:43 -0500228 return eq;
Jens Axboe98170642006-07-28 09:23:08 +0200229err:
230 kfree(eq);
231 elevator_put(e);
232 return NULL;
Al Viro3d1ab402006-03-18 18:35:43 -0500233}
234
235static void elevator_release(struct kobject *kobj)
236{
237 elevator_t *e = container_of(kobj, elevator_t, kobj);
Jens Axboe98170642006-07-28 09:23:08 +0200238
Al Viro3d1ab402006-03-18 18:35:43 -0500239 elevator_put(e->elevator_type);
Jens Axboe98170642006-07-28 09:23:08 +0200240 kfree(e->hash);
Al Viro3d1ab402006-03-18 18:35:43 -0500241 kfree(e);
242}
243
Jens Axboe165125e2007-07-24 09:28:11 +0200244int elevator_init(struct request_queue *q, char *name)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700245{
246 struct elevator_type *e = NULL;
247 struct elevator_queue *eq;
248 int ret = 0;
Jens Axboebc1c1162006-06-08 08:49:06 +0200249 void *data;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700250
Tejun Heocb98fc82005-10-28 08:29:39 +0200251 INIT_LIST_HEAD(&q->queue_head);
252 q->last_merge = NULL;
253 q->end_sector = 0;
254 q->boundary_rq = NULL;
Tejun Heocb98fc82005-10-28 08:29:39 +0200255
Jens Axboe4eb166d2008-02-01 00:37:27 +0100256 if (name) {
257 e = elevator_get(name);
258 if (!e)
259 return -EINVAL;
260 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700261
Jens Axboe4eb166d2008-02-01 00:37:27 +0100262 if (!e && *chosen_elevator) {
263 e = elevator_get(chosen_elevator);
264 if (!e)
265 printk(KERN_ERR "I/O scheduler %s not found\n",
266 chosen_elevator);
267 }
Nate Diller248d5ca2006-01-24 10:09:14 +0100268
Jens Axboe4eb166d2008-02-01 00:37:27 +0100269 if (!e) {
270 e = elevator_get(CONFIG_DEFAULT_IOSCHED);
271 if (!e) {
272 printk(KERN_ERR
273 "Default I/O scheduler not found. " \
274 "Using noop.\n");
275 e = elevator_get("noop");
276 }
Nate Diller5f003972006-01-24 10:07:58 +0100277 }
278
Jens Axboeb5deef92006-07-19 23:39:40 +0200279 eq = elevator_alloc(q, e);
Al Viro3d1ab402006-03-18 18:35:43 -0500280 if (!eq)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700281 return -ENOMEM;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700282
Jens Axboebc1c1162006-06-08 08:49:06 +0200283 data = elevator_init_queue(q, eq);
284 if (!data) {
Al Viro3d1ab402006-03-18 18:35:43 -0500285 kobject_put(&eq->kobj);
Jens Axboebc1c1162006-06-08 08:49:06 +0200286 return -ENOMEM;
287 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700288
Jens Axboebc1c1162006-06-08 08:49:06 +0200289 elevator_attach(q, eq, data);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700290 return ret;
291}
Jens Axboe2e662b62006-07-13 11:55:04 +0200292EXPORT_SYMBOL(elevator_init);
293
Linus Torvalds1da177e2005-04-16 15:20:36 -0700294void elevator_exit(elevator_t *e)
295{
Al Viro3d1ab402006-03-18 18:35:43 -0500296 mutex_lock(&e->sysfs_lock);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700297 if (e->ops->elevator_exit_fn)
298 e->ops->elevator_exit_fn(e);
Al Viro3d1ab402006-03-18 18:35:43 -0500299 e->ops = NULL;
300 mutex_unlock(&e->sysfs_lock);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700301
Al Viro3d1ab402006-03-18 18:35:43 -0500302 kobject_put(&e->kobj);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700303}
Jens Axboe2e662b62006-07-13 11:55:04 +0200304EXPORT_SYMBOL(elevator_exit);
305
Jens Axboe165125e2007-07-24 09:28:11 +0200306static void elv_activate_rq(struct request_queue *q, struct request *rq)
Jens Axboecad97512007-01-14 22:26:09 +1100307{
308 elevator_t *e = q->elevator;
309
310 if (e->ops->elevator_activate_req_fn)
311 e->ops->elevator_activate_req_fn(q, rq);
312}
313
Jens Axboe165125e2007-07-24 09:28:11 +0200314static void elv_deactivate_rq(struct request_queue *q, struct request *rq)
Jens Axboecad97512007-01-14 22:26:09 +1100315{
316 elevator_t *e = q->elevator;
317
318 if (e->ops->elevator_deactivate_req_fn)
319 e->ops->elevator_deactivate_req_fn(q, rq);
320}
321
Jens Axboe98170642006-07-28 09:23:08 +0200322static inline void __elv_rqhash_del(struct request *rq)
323{
324 hlist_del_init(&rq->hash);
325}
326
Jens Axboe165125e2007-07-24 09:28:11 +0200327static void elv_rqhash_del(struct request_queue *q, struct request *rq)
Jens Axboe98170642006-07-28 09:23:08 +0200328{
329 if (ELV_ON_HASH(rq))
330 __elv_rqhash_del(rq);
331}
332
Jens Axboe165125e2007-07-24 09:28:11 +0200333static void elv_rqhash_add(struct request_queue *q, struct request *rq)
Jens Axboe98170642006-07-28 09:23:08 +0200334{
335 elevator_t *e = q->elevator;
336
337 BUG_ON(ELV_ON_HASH(rq));
338 hlist_add_head(&rq->hash, &e->hash[ELV_HASH_FN(rq_hash_key(rq))]);
339}
340
Jens Axboe165125e2007-07-24 09:28:11 +0200341static void elv_rqhash_reposition(struct request_queue *q, struct request *rq)
Jens Axboe98170642006-07-28 09:23:08 +0200342{
343 __elv_rqhash_del(rq);
344 elv_rqhash_add(q, rq);
345}
346
Jens Axboe165125e2007-07-24 09:28:11 +0200347static struct request *elv_rqhash_find(struct request_queue *q, sector_t offset)
Jens Axboe98170642006-07-28 09:23:08 +0200348{
349 elevator_t *e = q->elevator;
350 struct hlist_head *hash_list = &e->hash[ELV_HASH_FN(offset)];
351 struct hlist_node *entry, *next;
352 struct request *rq;
353
354 hlist_for_each_entry_safe(rq, entry, next, hash_list, hash) {
355 BUG_ON(!ELV_ON_HASH(rq));
356
357 if (unlikely(!rq_mergeable(rq))) {
358 __elv_rqhash_del(rq);
359 continue;
360 }
361
362 if (rq_hash_key(rq) == offset)
363 return rq;
364 }
365
366 return NULL;
367}
368
Tejun Heo8922e162005-10-20 16:23:44 +0200369/*
Jens Axboe2e662b62006-07-13 11:55:04 +0200370 * RB-tree support functions for inserting/lookup/removal of requests
371 * in a sorted RB tree.
372 */
373struct request *elv_rb_add(struct rb_root *root, struct request *rq)
374{
375 struct rb_node **p = &root->rb_node;
376 struct rb_node *parent = NULL;
377 struct request *__rq;
378
379 while (*p) {
380 parent = *p;
381 __rq = rb_entry(parent, struct request, rb_node);
382
383 if (rq->sector < __rq->sector)
384 p = &(*p)->rb_left;
385 else if (rq->sector > __rq->sector)
386 p = &(*p)->rb_right;
387 else
388 return __rq;
389 }
390
391 rb_link_node(&rq->rb_node, parent, p);
392 rb_insert_color(&rq->rb_node, root);
393 return NULL;
394}
Jens Axboe2e662b62006-07-13 11:55:04 +0200395EXPORT_SYMBOL(elv_rb_add);
396
397void elv_rb_del(struct rb_root *root, struct request *rq)
398{
399 BUG_ON(RB_EMPTY_NODE(&rq->rb_node));
400 rb_erase(&rq->rb_node, root);
401 RB_CLEAR_NODE(&rq->rb_node);
402}
Jens Axboe2e662b62006-07-13 11:55:04 +0200403EXPORT_SYMBOL(elv_rb_del);
404
405struct request *elv_rb_find(struct rb_root *root, sector_t sector)
406{
407 struct rb_node *n = root->rb_node;
408 struct request *rq;
409
410 while (n) {
411 rq = rb_entry(n, struct request, rb_node);
412
413 if (sector < rq->sector)
414 n = n->rb_left;
415 else if (sector > rq->sector)
416 n = n->rb_right;
417 else
418 return rq;
419 }
420
421 return NULL;
422}
Jens Axboe2e662b62006-07-13 11:55:04 +0200423EXPORT_SYMBOL(elv_rb_find);
424
425/*
Tejun Heo8922e162005-10-20 16:23:44 +0200426 * Insert rq into dispatch queue of q. Queue lock must be held on
Uwe Kleine-Königdbe7f762007-10-20 01:55:04 +0200427 * entry. rq is sort instead into the dispatch queue. To be used by
Jens Axboe2e662b62006-07-13 11:55:04 +0200428 * specific elevators.
Tejun Heo8922e162005-10-20 16:23:44 +0200429 */
Jens Axboe165125e2007-07-24 09:28:11 +0200430void elv_dispatch_sort(struct request_queue *q, struct request *rq)
Tejun Heo8922e162005-10-20 16:23:44 +0200431{
432 sector_t boundary;
Tejun Heo8922e162005-10-20 16:23:44 +0200433 struct list_head *entry;
Jens Axboe4eb166d2008-02-01 00:37:27 +0100434 int stop_flags;
Tejun Heo8922e162005-10-20 16:23:44 +0200435
Tejun Heo06b86242005-10-20 16:46:23 +0200436 if (q->last_merge == rq)
437 q->last_merge = NULL;
Jens Axboe98170642006-07-28 09:23:08 +0200438
439 elv_rqhash_del(q, rq);
440
Tejun Heo15853af2005-11-10 08:52:05 +0100441 q->nr_sorted--;
Tejun Heo06b86242005-10-20 16:46:23 +0200442
Jens Axboe1b47f532005-10-20 16:37:00 +0200443 boundary = q->end_sector;
Jens Axboe4eb166d2008-02-01 00:37:27 +0100444 stop_flags = REQ_SOFTBARRIER | REQ_HARDBARRIER | REQ_STARTED;
Tejun Heo8922e162005-10-20 16:23:44 +0200445 list_for_each_prev(entry, &q->queue_head) {
446 struct request *pos = list_entry_rq(entry);
447
David Woodhousee17fc0a2008-08-09 16:42:20 +0100448 if (blk_discard_rq(rq) != blk_discard_rq(pos))
449 break;
Jens Axboe783660b2007-01-19 11:27:47 +1100450 if (rq_data_dir(rq) != rq_data_dir(pos))
451 break;
Jens Axboe4eb166d2008-02-01 00:37:27 +0100452 if (pos->cmd_flags & stop_flags)
Tejun Heo8922e162005-10-20 16:23:44 +0200453 break;
454 if (rq->sector >= boundary) {
455 if (pos->sector < boundary)
456 continue;
457 } else {
458 if (pos->sector >= boundary)
459 break;
460 }
461 if (rq->sector >= pos->sector)
462 break;
463 }
464
465 list_add(&rq->queuelist, entry);
466}
Jens Axboe2e662b62006-07-13 11:55:04 +0200467EXPORT_SYMBOL(elv_dispatch_sort);
468
Jens Axboe98170642006-07-28 09:23:08 +0200469/*
Jens Axboe2e662b62006-07-13 11:55:04 +0200470 * Insert rq into dispatch queue of q. Queue lock must be held on
471 * entry. rq is added to the back of the dispatch queue. To be used by
472 * specific elevators.
Jens Axboe98170642006-07-28 09:23:08 +0200473 */
474void elv_dispatch_add_tail(struct request_queue *q, struct request *rq)
475{
476 if (q->last_merge == rq)
477 q->last_merge = NULL;
478
479 elv_rqhash_del(q, rq);
480
481 q->nr_sorted--;
482
483 q->end_sector = rq_end_sector(rq);
484 q->boundary_rq = rq;
485 list_add_tail(&rq->queuelist, &q->queue_head);
486}
Jens Axboe2e662b62006-07-13 11:55:04 +0200487EXPORT_SYMBOL(elv_dispatch_add_tail);
488
Jens Axboe165125e2007-07-24 09:28:11 +0200489int elv_merge(struct request_queue *q, struct request **req, struct bio *bio)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700490{
491 elevator_t *e = q->elevator;
Jens Axboe98170642006-07-28 09:23:08 +0200492 struct request *__rq;
Tejun Heo06b86242005-10-20 16:46:23 +0200493 int ret;
494
Jens Axboe98170642006-07-28 09:23:08 +0200495 /*
496 * First try one-hit cache.
497 */
Tejun Heo06b86242005-10-20 16:46:23 +0200498 if (q->last_merge) {
499 ret = elv_try_merge(q->last_merge, bio);
500 if (ret != ELEVATOR_NO_MERGE) {
501 *req = q->last_merge;
502 return ret;
503 }
504 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700505
Alan D. Brunelleac9fafa2008-04-29 14:44:19 +0200506 if (blk_queue_nomerges(q))
507 return ELEVATOR_NO_MERGE;
508
Jens Axboe98170642006-07-28 09:23:08 +0200509 /*
510 * See if our hash lookup can find a potential backmerge.
511 */
512 __rq = elv_rqhash_find(q, bio->bi_sector);
513 if (__rq && elv_rq_merge_ok(__rq, bio)) {
514 *req = __rq;
515 return ELEVATOR_BACK_MERGE;
516 }
517
Linus Torvalds1da177e2005-04-16 15:20:36 -0700518 if (e->ops->elevator_merge_fn)
519 return e->ops->elevator_merge_fn(q, req, bio);
520
521 return ELEVATOR_NO_MERGE;
522}
523
Jens Axboe165125e2007-07-24 09:28:11 +0200524void elv_merged_request(struct request_queue *q, struct request *rq, int type)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700525{
526 elevator_t *e = q->elevator;
527
528 if (e->ops->elevator_merged_fn)
Jens Axboe2e662b62006-07-13 11:55:04 +0200529 e->ops->elevator_merged_fn(q, rq, type);
Tejun Heo06b86242005-10-20 16:46:23 +0200530
Jens Axboe2e662b62006-07-13 11:55:04 +0200531 if (type == ELEVATOR_BACK_MERGE)
532 elv_rqhash_reposition(q, rq);
Jens Axboe98170642006-07-28 09:23:08 +0200533
Tejun Heo06b86242005-10-20 16:46:23 +0200534 q->last_merge = rq;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700535}
536
Jens Axboe165125e2007-07-24 09:28:11 +0200537void elv_merge_requests(struct request_queue *q, struct request *rq,
Linus Torvalds1da177e2005-04-16 15:20:36 -0700538 struct request *next)
539{
540 elevator_t *e = q->elevator;
541
Linus Torvalds1da177e2005-04-16 15:20:36 -0700542 if (e->ops->elevator_merge_req_fn)
543 e->ops->elevator_merge_req_fn(q, rq, next);
Tejun Heo06b86242005-10-20 16:46:23 +0200544
Jens Axboe98170642006-07-28 09:23:08 +0200545 elv_rqhash_reposition(q, rq);
546 elv_rqhash_del(q, next);
547
548 q->nr_sorted--;
Tejun Heo06b86242005-10-20 16:46:23 +0200549 q->last_merge = rq;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700550}
551
Jens Axboe165125e2007-07-24 09:28:11 +0200552void elv_requeue_request(struct request_queue *q, struct request *rq)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700553{
Linus Torvalds1da177e2005-04-16 15:20:36 -0700554 /*
555 * it already went through dequeue, we need to decrement the
556 * in_flight count again
557 */
Tejun Heo8922e162005-10-20 16:23:44 +0200558 if (blk_account_rq(rq)) {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700559 q->in_flight--;
Jens Axboecad97512007-01-14 22:26:09 +1100560 if (blk_sorted_rq(rq))
561 elv_deactivate_rq(q, rq);
Tejun Heo8922e162005-10-20 16:23:44 +0200562 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700563
Jens Axboe4aff5e22006-08-10 08:44:47 +0200564 rq->cmd_flags &= ~REQ_STARTED;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700565
Tejun Heo30e96562006-02-08 01:01:31 -0800566 elv_insert(q, rq, ELEVATOR_INSERT_REQUEUE);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700567}
568
Jens Axboe165125e2007-07-24 09:28:11 +0200569static void elv_drain_elevator(struct request_queue *q)
Tejun Heo15853af2005-11-10 08:52:05 +0100570{
571 static int printed;
572 while (q->elevator->ops->elevator_dispatch_fn(q, 1))
573 ;
574 if (q->nr_sorted == 0)
575 return;
576 if (printed++ < 10) {
577 printk(KERN_ERR "%s: forced dispatching is broken "
578 "(nr_sorted=%u), please report this\n",
579 q->elevator->elevator_type->elevator_name, q->nr_sorted);
580 }
581}
582
Jens Axboe165125e2007-07-24 09:28:11 +0200583void elv_insert(struct request_queue *q, struct request *rq, int where)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700584{
Tejun Heo797e7db2006-01-06 09:51:03 +0100585 struct list_head *pos;
586 unsigned ordseq;
Jens Axboedac07ec2006-05-11 08:20:16 +0200587 int unplug_it = 1;
Tejun Heo797e7db2006-01-06 09:51:03 +0100588
Jens Axboe2056a782006-03-23 20:00:26 +0100589 blk_add_trace_rq(q, rq, BLK_TA_INSERT);
590
Linus Torvalds1da177e2005-04-16 15:20:36 -0700591 rq->q = q;
592
Tejun Heo8922e162005-10-20 16:23:44 +0200593 switch (where) {
594 case ELEVATOR_INSERT_FRONT:
Jens Axboe4aff5e22006-08-10 08:44:47 +0200595 rq->cmd_flags |= REQ_SOFTBARRIER;
Tejun Heo8922e162005-10-20 16:23:44 +0200596
597 list_add(&rq->queuelist, &q->queue_head);
598 break;
599
600 case ELEVATOR_INSERT_BACK:
Jens Axboe4aff5e22006-08-10 08:44:47 +0200601 rq->cmd_flags |= REQ_SOFTBARRIER;
Tejun Heo15853af2005-11-10 08:52:05 +0100602 elv_drain_elevator(q);
Tejun Heo8922e162005-10-20 16:23:44 +0200603 list_add_tail(&rq->queuelist, &q->queue_head);
604 /*
605 * We kick the queue here for the following reasons.
606 * - The elevator might have returned NULL previously
607 * to delay requests and returned them now. As the
608 * queue wasn't empty before this request, ll_rw_blk
609 * won't run the queue on return, resulting in hang.
610 * - Usually, back inserted requests won't be merged
611 * with anything. There's no point in delaying queue
612 * processing.
613 */
614 blk_remove_plug(q);
615 q->request_fn(q);
616 break;
617
618 case ELEVATOR_INSERT_SORT:
David Woodhousee17fc0a2008-08-09 16:42:20 +0100619 BUG_ON(!blk_fs_request(rq) && !blk_discard_rq(rq));
Jens Axboe4aff5e22006-08-10 08:44:47 +0200620 rq->cmd_flags |= REQ_SORTED;
Tejun Heo15853af2005-11-10 08:52:05 +0100621 q->nr_sorted++;
Jens Axboe98170642006-07-28 09:23:08 +0200622 if (rq_mergeable(rq)) {
623 elv_rqhash_add(q, rq);
624 if (!q->last_merge)
625 q->last_merge = rq;
626 }
627
Tejun Heoca235092005-11-01 17:23:49 +0900628 /*
629 * Some ioscheds (cfq) run q->request_fn directly, so
630 * rq cannot be accessed after calling
631 * elevator_add_req_fn.
632 */
633 q->elevator->ops->elevator_add_req_fn(q, rq);
Tejun Heo8922e162005-10-20 16:23:44 +0200634 break;
635
Tejun Heo797e7db2006-01-06 09:51:03 +0100636 case ELEVATOR_INSERT_REQUEUE:
637 /*
638 * If ordered flush isn't in progress, we do front
639 * insertion; otherwise, requests should be requeued
640 * in ordseq order.
641 */
Jens Axboe4aff5e22006-08-10 08:44:47 +0200642 rq->cmd_flags |= REQ_SOFTBARRIER;
Tejun Heo797e7db2006-01-06 09:51:03 +0100643
Linas Vepstas95543172007-01-23 19:40:54 +0100644 /*
645 * Most requeues happen because of a busy condition,
646 * don't force unplug of the queue for that case.
647 */
648 unplug_it = 0;
649
Tejun Heo797e7db2006-01-06 09:51:03 +0100650 if (q->ordseq == 0) {
651 list_add(&rq->queuelist, &q->queue_head);
652 break;
653 }
654
655 ordseq = blk_ordered_req_seq(rq);
656
657 list_for_each(pos, &q->queue_head) {
658 struct request *pos_rq = list_entry_rq(pos);
659 if (ordseq <= blk_ordered_req_seq(pos_rq))
660 break;
661 }
662
663 list_add_tail(&rq->queuelist, pos);
664 break;
665
Tejun Heo8922e162005-10-20 16:23:44 +0200666 default:
667 printk(KERN_ERR "%s: bad insertion point %d\n",
Harvey Harrison24c03d42008-05-01 04:35:17 -0700668 __func__, where);
Tejun Heo8922e162005-10-20 16:23:44 +0200669 BUG();
670 }
671
Jens Axboedac07ec2006-05-11 08:20:16 +0200672 if (unplug_it && blk_queue_plugged(q)) {
Tejun Heo8922e162005-10-20 16:23:44 +0200673 int nrq = q->rq.count[READ] + q->rq.count[WRITE]
674 - q->in_flight;
675
676 if (nrq >= q->unplug_thresh)
677 __generic_unplug_device(q);
678 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700679}
680
Jens Axboe165125e2007-07-24 09:28:11 +0200681void __elv_add_request(struct request_queue *q, struct request *rq, int where,
Tejun Heo30e96562006-02-08 01:01:31 -0800682 int plug)
683{
684 if (q->ordcolor)
Jens Axboe4aff5e22006-08-10 08:44:47 +0200685 rq->cmd_flags |= REQ_ORDERED_COLOR;
Tejun Heo30e96562006-02-08 01:01:31 -0800686
Jens Axboe4aff5e22006-08-10 08:44:47 +0200687 if (rq->cmd_flags & (REQ_SOFTBARRIER | REQ_HARDBARRIER)) {
Tejun Heo30e96562006-02-08 01:01:31 -0800688 /*
689 * toggle ordered color
690 */
691 if (blk_barrier_rq(rq))
692 q->ordcolor ^= 1;
693
694 /*
695 * barriers implicitly indicate back insertion
696 */
697 if (where == ELEVATOR_INSERT_SORT)
698 where = ELEVATOR_INSERT_BACK;
699
700 /*
701 * this request is scheduling boundary, update
702 * end_sector
703 */
David Woodhousee17fc0a2008-08-09 16:42:20 +0100704 if (blk_fs_request(rq) || blk_discard_rq(rq)) {
Tejun Heo30e96562006-02-08 01:01:31 -0800705 q->end_sector = rq_end_sector(rq);
706 q->boundary_rq = rq;
707 }
Jens Axboe4eb166d2008-02-01 00:37:27 +0100708 } else if (!(rq->cmd_flags & REQ_ELVPRIV) &&
709 where == ELEVATOR_INSERT_SORT)
Tejun Heo30e96562006-02-08 01:01:31 -0800710 where = ELEVATOR_INSERT_BACK;
711
712 if (plug)
713 blk_plug_device(q);
714
715 elv_insert(q, rq, where);
716}
Jens Axboe2e662b62006-07-13 11:55:04 +0200717EXPORT_SYMBOL(__elv_add_request);
718
Jens Axboe165125e2007-07-24 09:28:11 +0200719void elv_add_request(struct request_queue *q, struct request *rq, int where,
Linus Torvalds1da177e2005-04-16 15:20:36 -0700720 int plug)
721{
722 unsigned long flags;
723
724 spin_lock_irqsave(q->queue_lock, flags);
725 __elv_add_request(q, rq, where, plug);
726 spin_unlock_irqrestore(q->queue_lock, flags);
727}
Jens Axboe2e662b62006-07-13 11:55:04 +0200728EXPORT_SYMBOL(elv_add_request);
729
Jens Axboe165125e2007-07-24 09:28:11 +0200730static inline struct request *__elv_next_request(struct request_queue *q)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700731{
Tejun Heo8922e162005-10-20 16:23:44 +0200732 struct request *rq;
733
Tejun Heo797e7db2006-01-06 09:51:03 +0100734 while (1) {
735 while (!list_empty(&q->queue_head)) {
736 rq = list_entry_rq(q->queue_head.next);
737 if (blk_do_ordered(q, &rq))
738 return rq;
739 }
Tejun Heo8922e162005-10-20 16:23:44 +0200740
Tejun Heo797e7db2006-01-06 09:51:03 +0100741 if (!q->elevator->ops->elevator_dispatch_fn(q, 0))
742 return NULL;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700743 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700744}
745
Jens Axboe165125e2007-07-24 09:28:11 +0200746struct request *elv_next_request(struct request_queue *q)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700747{
748 struct request *rq;
749 int ret;
750
751 while ((rq = __elv_next_request(q)) != NULL) {
Jens Axboebf2de6f2007-09-27 13:01:25 +0200752 /*
753 * Kill the empty barrier place holder, the driver must
754 * not ever see it.
755 */
756 if (blk_empty_barrier(rq)) {
Kiyoshi Ueda99cd3382008-10-01 10:13:44 -0400757 __blk_end_request(rq, 0, blk_rq_bytes(rq));
Jens Axboebf2de6f2007-09-27 13:01:25 +0200758 continue;
759 }
Jens Axboe4aff5e22006-08-10 08:44:47 +0200760 if (!(rq->cmd_flags & REQ_STARTED)) {
Tejun Heo8922e162005-10-20 16:23:44 +0200761 /*
762 * This is the first time the device driver
763 * sees this request (possibly after
764 * requeueing). Notify IO scheduler.
765 */
Jens Axboecad97512007-01-14 22:26:09 +1100766 if (blk_sorted_rq(rq))
767 elv_activate_rq(q, rq);
Tejun Heo8922e162005-10-20 16:23:44 +0200768
769 /*
770 * just mark as started even if we don't start
771 * it, a request that has been delayed should
772 * not be passed by new incoming requests
773 */
Jens Axboe4aff5e22006-08-10 08:44:47 +0200774 rq->cmd_flags |= REQ_STARTED;
Jens Axboe2056a782006-03-23 20:00:26 +0100775 blk_add_trace_rq(q, rq, BLK_TA_ISSUE);
Jens Axboe242f9dc2008-09-14 05:55:09 -0700776
777 /*
778 * We are now handing the request to the hardware,
779 * add the timeout handler
780 */
781 blk_add_timer(rq);
Tejun Heo8922e162005-10-20 16:23:44 +0200782 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700783
Tejun Heo8922e162005-10-20 16:23:44 +0200784 if (!q->boundary_rq || q->boundary_rq == rq) {
Jens Axboe1b47f532005-10-20 16:37:00 +0200785 q->end_sector = rq_end_sector(rq);
Tejun Heo8922e162005-10-20 16:23:44 +0200786 q->boundary_rq = NULL;
787 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700788
James Bottomleyfa0ccd82008-01-10 11:30:36 -0600789 if (rq->cmd_flags & REQ_DONTPREP)
790 break;
791
792 if (q->dma_drain_size && rq->data_len) {
793 /*
794 * make sure space for the drain appears we
795 * know we can do this because max_hw_segments
796 * has been adjusted to be one fewer than the
797 * device can handle
798 */
799 rq->nr_phys_segments++;
James Bottomleyfa0ccd82008-01-10 11:30:36 -0600800 }
801
802 if (!q->prep_rq_fn)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700803 break;
804
805 ret = q->prep_rq_fn(q, rq);
806 if (ret == BLKPREP_OK) {
807 break;
808 } else if (ret == BLKPREP_DEFER) {
Tejun Heo 2e759cd2005-04-24 02:04:21 -0500809 /*
810 * the request may have been (partially) prepped.
811 * we need to keep this request in the front to
Tejun Heo8922e162005-10-20 16:23:44 +0200812 * avoid resource deadlock. REQ_STARTED will
813 * prevent other fs requests from passing this one.
Tejun Heo 2e759cd2005-04-24 02:04:21 -0500814 */
James Bottomleyfa0ccd82008-01-10 11:30:36 -0600815 if (q->dma_drain_size && rq->data_len &&
816 !(rq->cmd_flags & REQ_DONTPREP)) {
817 /*
818 * remove the space for the drain we added
819 * so that we don't add it again
820 */
821 --rq->nr_phys_segments;
James Bottomleyfa0ccd82008-01-10 11:30:36 -0600822 }
823
Linus Torvalds1da177e2005-04-16 15:20:36 -0700824 rq = NULL;
825 break;
826 } else if (ret == BLKPREP_KILL) {
Jens Axboe4aff5e22006-08-10 08:44:47 +0200827 rq->cmd_flags |= REQ_QUIET;
Kiyoshi Ueda99cd3382008-10-01 10:13:44 -0400828 __blk_end_request(rq, -EIO, blk_rq_bytes(rq));
Linus Torvalds1da177e2005-04-16 15:20:36 -0700829 } else {
Harvey Harrison24c03d42008-05-01 04:35:17 -0700830 printk(KERN_ERR "%s: bad return=%d\n", __func__, ret);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700831 break;
832 }
833 }
834
835 return rq;
836}
Jens Axboe2e662b62006-07-13 11:55:04 +0200837EXPORT_SYMBOL(elv_next_request);
838
Jens Axboe165125e2007-07-24 09:28:11 +0200839void elv_dequeue_request(struct request_queue *q, struct request *rq)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700840{
Tejun Heo8922e162005-10-20 16:23:44 +0200841 BUG_ON(list_empty(&rq->queuelist));
Jens Axboe98170642006-07-28 09:23:08 +0200842 BUG_ON(ELV_ON_HASH(rq));
Tejun Heo8922e162005-10-20 16:23:44 +0200843
844 list_del_init(&rq->queuelist);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700845
846 /*
847 * the time frame between a request being removed from the lists
848 * and to it is freed is accounted as io that is in progress at
Tejun Heo8922e162005-10-20 16:23:44 +0200849 * the driver side.
Linus Torvalds1da177e2005-04-16 15:20:36 -0700850 */
851 if (blk_account_rq(rq))
852 q->in_flight++;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700853}
Jens Axboe2e662b62006-07-13 11:55:04 +0200854EXPORT_SYMBOL(elv_dequeue_request);
855
Jens Axboe165125e2007-07-24 09:28:11 +0200856int elv_queue_empty(struct request_queue *q)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700857{
858 elevator_t *e = q->elevator;
859
Tejun Heo8922e162005-10-20 16:23:44 +0200860 if (!list_empty(&q->queue_head))
861 return 0;
862
Linus Torvalds1da177e2005-04-16 15:20:36 -0700863 if (e->ops->elevator_queue_empty_fn)
864 return e->ops->elevator_queue_empty_fn(q);
865
Tejun Heo8922e162005-10-20 16:23:44 +0200866 return 1;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700867}
Jens Axboe2e662b62006-07-13 11:55:04 +0200868EXPORT_SYMBOL(elv_queue_empty);
869
Jens Axboe165125e2007-07-24 09:28:11 +0200870struct request *elv_latter_request(struct request_queue *q, struct request *rq)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700871{
Linus Torvalds1da177e2005-04-16 15:20:36 -0700872 elevator_t *e = q->elevator;
873
874 if (e->ops->elevator_latter_req_fn)
875 return e->ops->elevator_latter_req_fn(q, rq);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700876 return NULL;
877}
878
Jens Axboe165125e2007-07-24 09:28:11 +0200879struct request *elv_former_request(struct request_queue *q, struct request *rq)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700880{
Linus Torvalds1da177e2005-04-16 15:20:36 -0700881 elevator_t *e = q->elevator;
882
883 if (e->ops->elevator_former_req_fn)
884 return e->ops->elevator_former_req_fn(q, rq);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700885 return NULL;
886}
887
Jens Axboe165125e2007-07-24 09:28:11 +0200888int elv_set_request(struct request_queue *q, struct request *rq, gfp_t gfp_mask)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700889{
890 elevator_t *e = q->elevator;
891
892 if (e->ops->elevator_set_req_fn)
Jens Axboecb78b282006-07-28 09:32:57 +0200893 return e->ops->elevator_set_req_fn(q, rq, gfp_mask);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700894
895 rq->elevator_private = NULL;
896 return 0;
897}
898
Jens Axboe165125e2007-07-24 09:28:11 +0200899void elv_put_request(struct request_queue *q, struct request *rq)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700900{
901 elevator_t *e = q->elevator;
902
903 if (e->ops->elevator_put_req_fn)
Jens Axboebb37b942006-12-01 10:42:33 +0100904 e->ops->elevator_put_req_fn(rq);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700905}
906
Jens Axboe165125e2007-07-24 09:28:11 +0200907int elv_may_queue(struct request_queue *q, int rw)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700908{
909 elevator_t *e = q->elevator;
910
911 if (e->ops->elevator_may_queue_fn)
Jens Axboecb78b282006-07-28 09:32:57 +0200912 return e->ops->elevator_may_queue_fn(q, rw);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700913
914 return ELV_MQUEUE_MAY;
915}
916
Mike Anderson11914a52008-09-13 20:31:27 +0200917void elv_abort_queue(struct request_queue *q)
918{
919 struct request *rq;
920
921 while (!list_empty(&q->queue_head)) {
922 rq = list_entry_rq(q->queue_head.next);
923 rq->cmd_flags |= REQ_QUIET;
924 blk_add_trace_rq(q, rq, BLK_TA_ABORT);
Kiyoshi Ueda99cd3382008-10-01 10:13:44 -0400925 __blk_end_request(rq, -EIO, blk_rq_bytes(rq));
Mike Anderson11914a52008-09-13 20:31:27 +0200926 }
927}
928EXPORT_SYMBOL(elv_abort_queue);
929
Jens Axboe165125e2007-07-24 09:28:11 +0200930void elv_completed_request(struct request_queue *q, struct request *rq)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700931{
932 elevator_t *e = q->elevator;
933
934 /*
935 * request is released from the driver, io must be done
936 */
Tejun Heo8922e162005-10-20 16:23:44 +0200937 if (blk_account_rq(rq)) {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700938 q->in_flight--;
Tejun Heo1bc691d2006-01-12 15:39:26 +0100939 if (blk_sorted_rq(rq) && e->ops->elevator_completed_req_fn)
940 e->ops->elevator_completed_req_fn(q, rq);
941 }
Tejun Heo797e7db2006-01-06 09:51:03 +0100942
Tejun Heo1bc691d2006-01-12 15:39:26 +0100943 /*
944 * Check if the queue is waiting for fs requests to be
945 * drained for flush sequence.
946 */
947 if (unlikely(q->ordseq)) {
948 struct request *first_rq = list_entry_rq(q->queue_head.next);
949 if (q->in_flight == 0 &&
Tejun Heo797e7db2006-01-06 09:51:03 +0100950 blk_ordered_cur_seq(q) == QUEUE_ORDSEQ_DRAIN &&
951 blk_ordered_req_seq(first_rq) > QUEUE_ORDSEQ_DRAIN) {
952 blk_ordered_complete_seq(q, QUEUE_ORDSEQ_DRAIN, 0);
953 q->request_fn(q);
954 }
Tejun Heo8922e162005-10-20 16:23:44 +0200955 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700956}
957
Al Viro3d1ab402006-03-18 18:35:43 -0500958#define to_elv(atr) container_of((atr), struct elv_fs_entry, attr)
959
960static ssize_t
961elv_attr_show(struct kobject *kobj, struct attribute *attr, char *page)
962{
963 elevator_t *e = container_of(kobj, elevator_t, kobj);
964 struct elv_fs_entry *entry = to_elv(attr);
965 ssize_t error;
966
967 if (!entry->show)
968 return -EIO;
969
970 mutex_lock(&e->sysfs_lock);
971 error = e->ops ? entry->show(e, page) : -ENOENT;
972 mutex_unlock(&e->sysfs_lock);
973 return error;
974}
975
976static ssize_t
977elv_attr_store(struct kobject *kobj, struct attribute *attr,
978 const char *page, size_t length)
979{
980 elevator_t *e = container_of(kobj, elevator_t, kobj);
981 struct elv_fs_entry *entry = to_elv(attr);
982 ssize_t error;
983
984 if (!entry->store)
985 return -EIO;
986
987 mutex_lock(&e->sysfs_lock);
988 error = e->ops ? entry->store(e, page, length) : -ENOENT;
989 mutex_unlock(&e->sysfs_lock);
990 return error;
991}
992
993static struct sysfs_ops elv_sysfs_ops = {
994 .show = elv_attr_show,
995 .store = elv_attr_store,
996};
997
998static struct kobj_type elv_ktype = {
999 .sysfs_ops = &elv_sysfs_ops,
1000 .release = elevator_release,
1001};
1002
Linus Torvalds1da177e2005-04-16 15:20:36 -07001003int elv_register_queue(struct request_queue *q)
1004{
1005 elevator_t *e = q->elevator;
Al Viro3d1ab402006-03-18 18:35:43 -05001006 int error;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001007
Greg Kroah-Hartmanb2d6db52007-12-17 23:05:35 -07001008 error = kobject_add(&e->kobj, &q->kobj, "%s", "iosched");
Al Viro3d1ab402006-03-18 18:35:43 -05001009 if (!error) {
Al Viroe572ec72006-03-18 22:27:18 -05001010 struct elv_fs_entry *attr = e->elevator_type->elevator_attrs;
Al Viro3d1ab402006-03-18 18:35:43 -05001011 if (attr) {
Al Viroe572ec72006-03-18 22:27:18 -05001012 while (attr->attr.name) {
1013 if (sysfs_create_file(&e->kobj, &attr->attr))
Al Viro3d1ab402006-03-18 18:35:43 -05001014 break;
Al Viroe572ec72006-03-18 22:27:18 -05001015 attr++;
Al Viro3d1ab402006-03-18 18:35:43 -05001016 }
1017 }
1018 kobject_uevent(&e->kobj, KOBJ_ADD);
1019 }
1020 return error;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001021}
1022
Jens Axboebc1c1162006-06-08 08:49:06 +02001023static void __elv_unregister_queue(elevator_t *e)
1024{
1025 kobject_uevent(&e->kobj, KOBJ_REMOVE);
1026 kobject_del(&e->kobj);
1027}
1028
Linus Torvalds1da177e2005-04-16 15:20:36 -07001029void elv_unregister_queue(struct request_queue *q)
1030{
Jens Axboebc1c1162006-06-08 08:49:06 +02001031 if (q)
1032 __elv_unregister_queue(q->elevator);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001033}
1034
Adrian Bunk2fdd82b2007-12-12 18:51:56 +01001035void elv_register(struct elevator_type *e)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001036{
Thibaut VARENE1ffb96c2007-03-15 12:59:19 +01001037 char *def = "";
Jens Axboe2a12dcd2007-04-26 14:41:53 +02001038
1039 spin_lock(&elv_list_lock);
Eric Sesterhennce524492006-03-24 18:43:26 +01001040 BUG_ON(elevator_find(e->elevator_name));
Linus Torvalds1da177e2005-04-16 15:20:36 -07001041 list_add_tail(&e->list, &elv_list);
Jens Axboe2a12dcd2007-04-26 14:41:53 +02001042 spin_unlock(&elv_list_lock);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001043
Nate Diller5f003972006-01-24 10:07:58 +01001044 if (!strcmp(e->elevator_name, chosen_elevator) ||
1045 (!*chosen_elevator &&
1046 !strcmp(e->elevator_name, CONFIG_DEFAULT_IOSCHED)))
Thibaut VARENE1ffb96c2007-03-15 12:59:19 +01001047 def = " (default)";
1048
Jens Axboe4eb166d2008-02-01 00:37:27 +01001049 printk(KERN_INFO "io scheduler %s registered%s\n", e->elevator_name,
1050 def);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001051}
1052EXPORT_SYMBOL_GPL(elv_register);
1053
1054void elv_unregister(struct elevator_type *e)
1055{
Christoph Hellwig83521d32005-10-30 15:01:39 -08001056 struct task_struct *g, *p;
1057
1058 /*
1059 * Iterate every thread in the process to remove the io contexts.
1060 */
Al Viroe17a9482006-03-18 13:21:20 -05001061 if (e->ops.trim) {
1062 read_lock(&tasklist_lock);
1063 do_each_thread(g, p) {
1064 task_lock(p);
Oleg Nesterov2d8f6132006-08-22 21:22:13 +04001065 if (p->io_context)
1066 e->ops.trim(p->io_context);
Al Viroe17a9482006-03-18 13:21:20 -05001067 task_unlock(p);
1068 } while_each_thread(g, p);
1069 read_unlock(&tasklist_lock);
1070 }
Christoph Hellwig83521d32005-10-30 15:01:39 -08001071
Jens Axboe2a12dcd2007-04-26 14:41:53 +02001072 spin_lock(&elv_list_lock);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001073 list_del_init(&e->list);
Jens Axboe2a12dcd2007-04-26 14:41:53 +02001074 spin_unlock(&elv_list_lock);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001075}
1076EXPORT_SYMBOL_GPL(elv_unregister);
1077
1078/*
1079 * switch to new_e io scheduler. be careful not to introduce deadlocks -
1080 * we don't free the old io scheduler, before we have allocated what we
1081 * need for the new one. this way we have a chance of going back to the old
Tejun Heocb98fc82005-10-28 08:29:39 +02001082 * one, if the new one fails init for some reason.
Linus Torvalds1da177e2005-04-16 15:20:36 -07001083 */
Jens Axboe165125e2007-07-24 09:28:11 +02001084static int elevator_switch(struct request_queue *q, struct elevator_type *new_e)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001085{
Tejun Heocb98fc82005-10-28 08:29:39 +02001086 elevator_t *old_elevator, *e;
Jens Axboebc1c1162006-06-08 08:49:06 +02001087 void *data;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001088
Tejun Heocb98fc82005-10-28 08:29:39 +02001089 /*
1090 * Allocate new elevator
1091 */
Jens Axboeb5deef92006-07-19 23:39:40 +02001092 e = elevator_alloc(q, new_e);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001093 if (!e)
Al Viro3d1ab402006-03-18 18:35:43 -05001094 return 0;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001095
Jens Axboebc1c1162006-06-08 08:49:06 +02001096 data = elevator_init_queue(q, e);
1097 if (!data) {
1098 kobject_put(&e->kobj);
1099 return 0;
1100 }
1101
Linus Torvalds1da177e2005-04-16 15:20:36 -07001102 /*
Tejun Heocb98fc82005-10-28 08:29:39 +02001103 * Turn on BYPASS and drain all requests w/ elevator private data
Linus Torvalds1da177e2005-04-16 15:20:36 -07001104 */
Tejun Heocb98fc82005-10-28 08:29:39 +02001105 spin_lock_irq(q->queue_lock);
1106
Nick Piggin75ad23b2008-04-29 14:48:33 +02001107 queue_flag_set(QUEUE_FLAG_ELVSWITCH, q);
Tejun Heocb98fc82005-10-28 08:29:39 +02001108
Tejun Heo15853af2005-11-10 08:52:05 +01001109 elv_drain_elevator(q);
Tejun Heocb98fc82005-10-28 08:29:39 +02001110
1111 while (q->rq.elvpriv) {
Tejun Heo407df2a2005-11-10 08:48:21 +01001112 blk_remove_plug(q);
1113 q->request_fn(q);
Tejun Heocb98fc82005-10-28 08:29:39 +02001114 spin_unlock_irq(q->queue_lock);
Jens Axboe64521d12005-10-28 08:30:39 +02001115 msleep(10);
Tejun Heocb98fc82005-10-28 08:29:39 +02001116 spin_lock_irq(q->queue_lock);
Tejun Heo15853af2005-11-10 08:52:05 +01001117 elv_drain_elevator(q);
Tejun Heocb98fc82005-10-28 08:29:39 +02001118 }
1119
Linus Torvalds1da177e2005-04-16 15:20:36 -07001120 /*
Jens Axboebc1c1162006-06-08 08:49:06 +02001121 * Remember old elevator.
Linus Torvalds1da177e2005-04-16 15:20:36 -07001122 */
Linus Torvalds1da177e2005-04-16 15:20:36 -07001123 old_elevator = q->elevator;
1124
1125 /*
Linus Torvalds1da177e2005-04-16 15:20:36 -07001126 * attach and start new elevator
1127 */
Jens Axboebc1c1162006-06-08 08:49:06 +02001128 elevator_attach(q, e, data);
1129
1130 spin_unlock_irq(q->queue_lock);
1131
1132 __elv_unregister_queue(old_elevator);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001133
1134 if (elv_register_queue(q))
1135 goto fail_register;
1136
1137 /*
Tejun Heocb98fc82005-10-28 08:29:39 +02001138 * finally exit old elevator and turn off BYPASS.
Linus Torvalds1da177e2005-04-16 15:20:36 -07001139 */
1140 elevator_exit(old_elevator);
Nick Piggin75ad23b2008-04-29 14:48:33 +02001141 spin_lock_irq(q->queue_lock);
1142 queue_flag_clear(QUEUE_FLAG_ELVSWITCH, q);
1143 spin_unlock_irq(q->queue_lock);
1144
Alan D. Brunelle4722dc52008-05-27 14:55:00 +02001145 blk_add_trace_msg(q, "elv switch: %s", e->elevator_type->elevator_name);
1146
Al Viro3d1ab402006-03-18 18:35:43 -05001147 return 1;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001148
1149fail_register:
1150 /*
1151 * switch failed, exit the new io scheduler and reattach the old
1152 * one again (along with re-adding the sysfs dir)
1153 */
1154 elevator_exit(e);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001155 q->elevator = old_elevator;
1156 elv_register_queue(q);
Nick Piggin75ad23b2008-04-29 14:48:33 +02001157
1158 spin_lock_irq(q->queue_lock);
1159 queue_flag_clear(QUEUE_FLAG_ELVSWITCH, q);
1160 spin_unlock_irq(q->queue_lock);
1161
Al Viro3d1ab402006-03-18 18:35:43 -05001162 return 0;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001163}
1164
Jens Axboe165125e2007-07-24 09:28:11 +02001165ssize_t elv_iosched_store(struct request_queue *q, const char *name,
1166 size_t count)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001167{
1168 char elevator_name[ELV_NAME_MAX];
Tejun Heobe561232005-11-10 08:55:01 +01001169 size_t len;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001170 struct elevator_type *e;
1171
Tejun Heobe561232005-11-10 08:55:01 +01001172 elevator_name[sizeof(elevator_name) - 1] = '\0';
1173 strncpy(elevator_name, name, sizeof(elevator_name) - 1);
1174 len = strlen(elevator_name);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001175
Tejun Heobe561232005-11-10 08:55:01 +01001176 if (len && elevator_name[len - 1] == '\n')
1177 elevator_name[len - 1] = '\0';
Linus Torvalds1da177e2005-04-16 15:20:36 -07001178
1179 e = elevator_get(elevator_name);
1180 if (!e) {
1181 printk(KERN_ERR "elevator: type %s not found\n", elevator_name);
1182 return -EINVAL;
1183 }
1184
Nate Diller2ca7d932005-10-30 15:02:24 -08001185 if (!strcmp(elevator_name, q->elevator->elevator_type->elevator_name)) {
1186 elevator_put(e);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001187 return count;
Nate Diller2ca7d932005-10-30 15:02:24 -08001188 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07001189
Al Viro3d1ab402006-03-18 18:35:43 -05001190 if (!elevator_switch(q, e))
Jens Axboe4eb166d2008-02-01 00:37:27 +01001191 printk(KERN_ERR "elevator: switch to %s failed\n",
1192 elevator_name);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001193 return count;
1194}
1195
Jens Axboe165125e2007-07-24 09:28:11 +02001196ssize_t elv_iosched_show(struct request_queue *q, char *name)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001197{
1198 elevator_t *e = q->elevator;
1199 struct elevator_type *elv = e->elevator_type;
Matthias Kaehlcke70cee262007-07-10 12:26:24 +02001200 struct elevator_type *__e;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001201 int len = 0;
1202
Jens Axboe2a12dcd2007-04-26 14:41:53 +02001203 spin_lock(&elv_list_lock);
Matthias Kaehlcke70cee262007-07-10 12:26:24 +02001204 list_for_each_entry(__e, &elv_list, list) {
Linus Torvalds1da177e2005-04-16 15:20:36 -07001205 if (!strcmp(elv->elevator_name, __e->elevator_name))
1206 len += sprintf(name+len, "[%s] ", elv->elevator_name);
1207 else
1208 len += sprintf(name+len, "%s ", __e->elevator_name);
1209 }
Jens Axboe2a12dcd2007-04-26 14:41:53 +02001210 spin_unlock(&elv_list_lock);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001211
1212 len += sprintf(len+name, "\n");
1213 return len;
1214}
1215
Jens Axboe165125e2007-07-24 09:28:11 +02001216struct request *elv_rb_former_request(struct request_queue *q,
1217 struct request *rq)
Jens Axboe2e662b62006-07-13 11:55:04 +02001218{
1219 struct rb_node *rbprev = rb_prev(&rq->rb_node);
1220
1221 if (rbprev)
1222 return rb_entry_rq(rbprev);
1223
1224 return NULL;
1225}
Jens Axboe2e662b62006-07-13 11:55:04 +02001226EXPORT_SYMBOL(elv_rb_former_request);
1227
Jens Axboe165125e2007-07-24 09:28:11 +02001228struct request *elv_rb_latter_request(struct request_queue *q,
1229 struct request *rq)
Jens Axboe2e662b62006-07-13 11:55:04 +02001230{
1231 struct rb_node *rbnext = rb_next(&rq->rb_node);
1232
1233 if (rbnext)
1234 return rb_entry_rq(rbnext);
1235
1236 return NULL;
1237}
Jens Axboe2e662b62006-07-13 11:55:04 +02001238EXPORT_SYMBOL(elv_rb_latter_request);