Merge tag 'metag-for-v4.9-rc1' of git://git.kernel.org/pub/scm/linux/kernel/git/jhoga...
[linux-2.6-block.git] / block / elevator.c
CommitLineData
1da177e4 1/*
1da177e4
LT
2 * Block device elevator/IO-scheduler.
3 *
4 * Copyright (C) 2000 Andrea Arcangeli <andrea@suse.de> SuSE
5 *
0fe23479 6 * 30042000 Jens Axboe <axboe@kernel.dk> :
1da177e4
LT
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>
1da177e4
LT
30#include <linux/module.h>
31#include <linux/slab.h>
32#include <linux/init.h>
33#include <linux/compiler.h>
2056a782 34#include <linux/blktrace_api.h>
9817064b 35#include <linux/hash.h>
0835da67 36#include <linux/uaccess.h>
c8158819 37#include <linux/pm_runtime.h>
eea8f41c 38#include <linux/blk-cgroup.h>
1da177e4 39
55782138
LZ
40#include <trace/events/block.h>
41
242f9dcb
JA
42#include "blk.h"
43
1da177e4
LT
44static DEFINE_SPINLOCK(elv_list_lock);
45static LIST_HEAD(elv_list);
46
9817064b
JA
47/*
48 * Merge hash stuff.
49 */
83096ebf 50#define rq_hash_key(rq) (blk_rq_pos(rq) + blk_rq_sectors(rq))
9817064b 51
da775265
JA
52/*
53 * Query io scheduler to see if the current process issuing bio may be
54 * merged with rq.
55 */
72ef799b 56static int elv_iosched_allow_bio_merge(struct request *rq, struct bio *bio)
da775265 57{
165125e1 58 struct request_queue *q = rq->q;
b374d18a 59 struct elevator_queue *e = q->elevator;
da775265 60
72ef799b
TE
61 if (e->type->ops.elevator_allow_bio_merge_fn)
62 return e->type->ops.elevator_allow_bio_merge_fn(q, rq, bio);
da775265
JA
63
64 return 1;
65}
66
1da177e4
LT
67/*
68 * can we safely merge with this request?
69 */
72ef799b 70bool elv_bio_merge_ok(struct request *rq, struct bio *bio)
1da177e4 71{
050c8ea8 72 if (!blk_rq_merge_ok(rq, bio))
72ef799b 73 return false;
7ba1ba12 74
72ef799b
TE
75 if (!elv_iosched_allow_bio_merge(rq, bio))
76 return false;
1da177e4 77
72ef799b 78 return true;
1da177e4 79}
72ef799b 80EXPORT_SYMBOL(elv_bio_merge_ok);
1da177e4 81
1da177e4
LT
82static struct elevator_type *elevator_find(const char *name)
83{
a22b169d 84 struct elevator_type *e;
1da177e4 85
70cee26e 86 list_for_each_entry(e, &elv_list, list) {
a22b169d
VT
87 if (!strcmp(e->elevator_name, name))
88 return e;
1da177e4 89 }
1da177e4 90
a22b169d 91 return NULL;
1da177e4
LT
92}
93
94static void elevator_put(struct elevator_type *e)
95{
96 module_put(e->elevator_owner);
97}
98
21c3c5d2 99static struct elevator_type *elevator_get(const char *name, bool try_loading)
1da177e4 100{
2824bc93 101 struct elevator_type *e;
1da177e4 102
2a12dcd7 103 spin_lock(&elv_list_lock);
2824bc93
TH
104
105 e = elevator_find(name);
21c3c5d2 106 if (!e && try_loading) {
e1640949 107 spin_unlock(&elv_list_lock);
490b94be 108 request_module("%s-iosched", name);
e1640949
JA
109 spin_lock(&elv_list_lock);
110 e = elevator_find(name);
111 }
112
2824bc93
TH
113 if (e && !try_module_get(e->elevator_owner))
114 e = NULL;
115
2a12dcd7 116 spin_unlock(&elv_list_lock);
1da177e4
LT
117
118 return e;
119}
120
484fc254 121static char chosen_elevator[ELV_NAME_MAX];
1da177e4 122
5f003976 123static int __init elevator_setup(char *str)
1da177e4 124{
752a3b79
CE
125 /*
126 * Be backwards-compatible with previous kernels, so users
127 * won't get the wrong elevator.
128 */
492af635 129 strncpy(chosen_elevator, str, sizeof(chosen_elevator) - 1);
9b41046c 130 return 1;
1da177e4
LT
131}
132
133__setup("elevator=", elevator_setup);
134
bb813f4c
TH
135/* called during boot to load the elevator chosen by the elevator param */
136void __init load_default_elevator_module(void)
137{
138 struct elevator_type *e;
139
140 if (!chosen_elevator[0])
141 return;
142
143 spin_lock(&elv_list_lock);
144 e = elevator_find(chosen_elevator);
145 spin_unlock(&elv_list_lock);
146
147 if (!e)
148 request_module("%s-iosched", chosen_elevator);
149}
150
3d1ab40f
AV
151static struct kobj_type elv_ktype;
152
d50235b7 153struct elevator_queue *elevator_alloc(struct request_queue *q,
165125e1 154 struct elevator_type *e)
3d1ab40f 155{
b374d18a 156 struct elevator_queue *eq;
9817064b 157
c1b511eb 158 eq = kzalloc_node(sizeof(*eq), GFP_KERNEL, q->node);
9817064b 159 if (unlikely(!eq))
8406a4d5 160 return NULL;
9817064b 161
22f746e2 162 eq->type = e;
f9cb074b 163 kobject_init(&eq->kobj, &elv_ktype);
9817064b 164 mutex_init(&eq->sysfs_lock);
242d98f0 165 hash_init(eq->hash);
9817064b 166
3d1ab40f
AV
167 return eq;
168}
d50235b7 169EXPORT_SYMBOL(elevator_alloc);
3d1ab40f
AV
170
171static void elevator_release(struct kobject *kobj)
172{
b374d18a 173 struct elevator_queue *e;
9817064b 174
b374d18a 175 e = container_of(kobj, struct elevator_queue, kobj);
22f746e2 176 elevator_put(e->type);
3d1ab40f
AV
177 kfree(e);
178}
179
165125e1 180int elevator_init(struct request_queue *q, char *name)
1da177e4
LT
181{
182 struct elevator_type *e = NULL;
f8fc877d 183 int err;
1da177e4 184
eb1c160b
TS
185 /*
186 * q->sysfs_lock must be held to provide mutual exclusion between
187 * elevator_switch() and here.
188 */
189 lockdep_assert_held(&q->sysfs_lock);
190
1abec4fd
MS
191 if (unlikely(q->elevator))
192 return 0;
193
cb98fc8b
TH
194 INIT_LIST_HEAD(&q->queue_head);
195 q->last_merge = NULL;
196 q->end_sector = 0;
197 q->boundary_rq = NULL;
cb98fc8b 198
4eb166d9 199 if (name) {
21c3c5d2 200 e = elevator_get(name, true);
4eb166d9
JA
201 if (!e)
202 return -EINVAL;
203 }
1da177e4 204
21c3c5d2
TH
205 /*
206 * Use the default elevator specified by config boot param or
207 * config option. Don't try to load modules as we could be running
208 * off async and request_module() isn't allowed from async.
209 */
4eb166d9 210 if (!e && *chosen_elevator) {
21c3c5d2 211 e = elevator_get(chosen_elevator, false);
4eb166d9
JA
212 if (!e)
213 printk(KERN_ERR "I/O scheduler %s not found\n",
214 chosen_elevator);
215 }
248d5ca5 216
4eb166d9 217 if (!e) {
21c3c5d2 218 e = elevator_get(CONFIG_DEFAULT_IOSCHED, false);
4eb166d9
JA
219 if (!e) {
220 printk(KERN_ERR
221 "Default I/O scheduler not found. " \
222 "Using noop.\n");
21c3c5d2 223 e = elevator_get("noop", false);
4eb166d9 224 }
5f003976
ND
225 }
226
d50235b7 227 err = e->ops.elevator_init_fn(q, e);
d32f6b57
SM
228 if (err)
229 elevator_put(e);
230 return err;
1da177e4 231}
2e662b65
JA
232EXPORT_SYMBOL(elevator_init);
233
b374d18a 234void elevator_exit(struct elevator_queue *e)
1da177e4 235{
3d1ab40f 236 mutex_lock(&e->sysfs_lock);
22f746e2
TH
237 if (e->type->ops.elevator_exit_fn)
238 e->type->ops.elevator_exit_fn(e);
3d1ab40f 239 mutex_unlock(&e->sysfs_lock);
1da177e4 240
3d1ab40f 241 kobject_put(&e->kobj);
1da177e4 242}
2e662b65
JA
243EXPORT_SYMBOL(elevator_exit);
244
9817064b
JA
245static inline void __elv_rqhash_del(struct request *rq)
246{
242d98f0 247 hash_del(&rq->hash);
360f92c2 248 rq->cmd_flags &= ~REQ_HASHED;
9817064b
JA
249}
250
165125e1 251static void elv_rqhash_del(struct request_queue *q, struct request *rq)
9817064b
JA
252{
253 if (ELV_ON_HASH(rq))
254 __elv_rqhash_del(rq);
255}
256
165125e1 257static void elv_rqhash_add(struct request_queue *q, struct request *rq)
9817064b 258{
b374d18a 259 struct elevator_queue *e = q->elevator;
9817064b
JA
260
261 BUG_ON(ELV_ON_HASH(rq));
242d98f0 262 hash_add(e->hash, &rq->hash, rq_hash_key(rq));
360f92c2 263 rq->cmd_flags |= REQ_HASHED;
9817064b
JA
264}
265
165125e1 266static void elv_rqhash_reposition(struct request_queue *q, struct request *rq)
9817064b
JA
267{
268 __elv_rqhash_del(rq);
269 elv_rqhash_add(q, rq);
270}
271
165125e1 272static struct request *elv_rqhash_find(struct request_queue *q, sector_t offset)
9817064b 273{
b374d18a 274 struct elevator_queue *e = q->elevator;
b67bfe0d 275 struct hlist_node *next;
9817064b
JA
276 struct request *rq;
277
ee89f812 278 hash_for_each_possible_safe(e->hash, rq, next, hash, offset) {
9817064b
JA
279 BUG_ON(!ELV_ON_HASH(rq));
280
281 if (unlikely(!rq_mergeable(rq))) {
282 __elv_rqhash_del(rq);
283 continue;
284 }
285
286 if (rq_hash_key(rq) == offset)
287 return rq;
288 }
289
290 return NULL;
291}
292
2e662b65
JA
293/*
294 * RB-tree support functions for inserting/lookup/removal of requests
295 * in a sorted RB tree.
296 */
796d5116 297void elv_rb_add(struct rb_root *root, struct request *rq)
2e662b65
JA
298{
299 struct rb_node **p = &root->rb_node;
300 struct rb_node *parent = NULL;
301 struct request *__rq;
302
303 while (*p) {
304 parent = *p;
305 __rq = rb_entry(parent, struct request, rb_node);
306
83096ebf 307 if (blk_rq_pos(rq) < blk_rq_pos(__rq))
2e662b65 308 p = &(*p)->rb_left;
796d5116 309 else if (blk_rq_pos(rq) >= blk_rq_pos(__rq))
2e662b65 310 p = &(*p)->rb_right;
2e662b65
JA
311 }
312
313 rb_link_node(&rq->rb_node, parent, p);
314 rb_insert_color(&rq->rb_node, root);
2e662b65 315}
2e662b65
JA
316EXPORT_SYMBOL(elv_rb_add);
317
318void elv_rb_del(struct rb_root *root, struct request *rq)
319{
320 BUG_ON(RB_EMPTY_NODE(&rq->rb_node));
321 rb_erase(&rq->rb_node, root);
322 RB_CLEAR_NODE(&rq->rb_node);
323}
2e662b65
JA
324EXPORT_SYMBOL(elv_rb_del);
325
326struct request *elv_rb_find(struct rb_root *root, sector_t sector)
327{
328 struct rb_node *n = root->rb_node;
329 struct request *rq;
330
331 while (n) {
332 rq = rb_entry(n, struct request, rb_node);
333
83096ebf 334 if (sector < blk_rq_pos(rq))
2e662b65 335 n = n->rb_left;
83096ebf 336 else if (sector > blk_rq_pos(rq))
2e662b65
JA
337 n = n->rb_right;
338 else
339 return rq;
340 }
341
342 return NULL;
343}
2e662b65
JA
344EXPORT_SYMBOL(elv_rb_find);
345
8922e16c
TH
346/*
347 * Insert rq into dispatch queue of q. Queue lock must be held on
dbe7f76d 348 * entry. rq is sort instead into the dispatch queue. To be used by
2e662b65 349 * specific elevators.
8922e16c 350 */
165125e1 351void elv_dispatch_sort(struct request_queue *q, struct request *rq)
8922e16c
TH
352{
353 sector_t boundary;
8922e16c 354 struct list_head *entry;
4eb166d9 355 int stop_flags;
8922e16c 356
06b86245
TH
357 if (q->last_merge == rq)
358 q->last_merge = NULL;
9817064b
JA
359
360 elv_rqhash_del(q, rq);
361
15853af9 362 q->nr_sorted--;
06b86245 363
1b47f531 364 boundary = q->end_sector;
02e031cb 365 stop_flags = REQ_SOFTBARRIER | REQ_STARTED;
8922e16c
TH
366 list_for_each_prev(entry, &q->queue_head) {
367 struct request *pos = list_entry_rq(entry);
368
7afafc8a 369 if (req_op(rq) != req_op(pos))
e17fc0a1 370 break;
783660b2
JA
371 if (rq_data_dir(rq) != rq_data_dir(pos))
372 break;
4eb166d9 373 if (pos->cmd_flags & stop_flags)
8922e16c 374 break;
83096ebf
TH
375 if (blk_rq_pos(rq) >= boundary) {
376 if (blk_rq_pos(pos) < boundary)
8922e16c
TH
377 continue;
378 } else {
83096ebf 379 if (blk_rq_pos(pos) >= boundary)
8922e16c
TH
380 break;
381 }
83096ebf 382 if (blk_rq_pos(rq) >= blk_rq_pos(pos))
8922e16c
TH
383 break;
384 }
385
386 list_add(&rq->queuelist, entry);
387}
2e662b65
JA
388EXPORT_SYMBOL(elv_dispatch_sort);
389
9817064b 390/*
2e662b65
JA
391 * Insert rq into dispatch queue of q. Queue lock must be held on
392 * entry. rq is added to the back of the dispatch queue. To be used by
393 * specific elevators.
9817064b
JA
394 */
395void elv_dispatch_add_tail(struct request_queue *q, struct request *rq)
396{
397 if (q->last_merge == rq)
398 q->last_merge = NULL;
399
400 elv_rqhash_del(q, rq);
401
402 q->nr_sorted--;
403
404 q->end_sector = rq_end_sector(rq);
405 q->boundary_rq = rq;
406 list_add_tail(&rq->queuelist, &q->queue_head);
407}
2e662b65
JA
408EXPORT_SYMBOL(elv_dispatch_add_tail);
409
165125e1 410int elv_merge(struct request_queue *q, struct request **req, struct bio *bio)
1da177e4 411{
b374d18a 412 struct elevator_queue *e = q->elevator;
9817064b 413 struct request *__rq;
06b86245
TH
414 int ret;
415
488991e2
AB
416 /*
417 * Levels of merges:
418 * nomerges: No merges at all attempted
419 * noxmerges: Only simple one-hit cache try
420 * merges: All merge tries attempted
421 */
7460d389 422 if (blk_queue_nomerges(q) || !bio_mergeable(bio))
488991e2
AB
423 return ELEVATOR_NO_MERGE;
424
9817064b
JA
425 /*
426 * First try one-hit cache.
427 */
72ef799b 428 if (q->last_merge && elv_bio_merge_ok(q->last_merge, bio)) {
050c8ea8 429 ret = blk_try_merge(q->last_merge, bio);
06b86245
TH
430 if (ret != ELEVATOR_NO_MERGE) {
431 *req = q->last_merge;
432 return ret;
433 }
434 }
1da177e4 435
488991e2 436 if (blk_queue_noxmerges(q))
ac9fafa1
AB
437 return ELEVATOR_NO_MERGE;
438
9817064b
JA
439 /*
440 * See if our hash lookup can find a potential backmerge.
441 */
4f024f37 442 __rq = elv_rqhash_find(q, bio->bi_iter.bi_sector);
72ef799b 443 if (__rq && elv_bio_merge_ok(__rq, bio)) {
9817064b
JA
444 *req = __rq;
445 return ELEVATOR_BACK_MERGE;
446 }
447
22f746e2
TH
448 if (e->type->ops.elevator_merge_fn)
449 return e->type->ops.elevator_merge_fn(q, req, bio);
1da177e4
LT
450
451 return ELEVATOR_NO_MERGE;
452}
453
5e84ea3a
JA
454/*
455 * Attempt to do an insertion back merge. Only check for the case where
456 * we can append 'rq' to an existing request, so we can throw 'rq' away
457 * afterwards.
458 *
459 * Returns true if we merged, false otherwise
460 */
461static bool elv_attempt_insert_merge(struct request_queue *q,
462 struct request *rq)
463{
464 struct request *__rq;
bee0393c 465 bool ret;
5e84ea3a
JA
466
467 if (blk_queue_nomerges(q))
468 return false;
469
470 /*
471 * First try one-hit cache.
472 */
473 if (q->last_merge && blk_attempt_req_merge(q, q->last_merge, rq))
474 return true;
475
476 if (blk_queue_noxmerges(q))
477 return false;
478
bee0393c 479 ret = false;
5e84ea3a
JA
480 /*
481 * See if our hash lookup can find a potential backmerge.
482 */
bee0393c
SL
483 while (1) {
484 __rq = elv_rqhash_find(q, blk_rq_pos(rq));
485 if (!__rq || !blk_attempt_req_merge(q, __rq, rq))
486 break;
487
488 /* The merged request could be merged with others, try again */
489 ret = true;
490 rq = __rq;
491 }
27419322 492
bee0393c 493 return ret;
5e84ea3a
JA
494}
495
165125e1 496void elv_merged_request(struct request_queue *q, struct request *rq, int type)
1da177e4 497{
b374d18a 498 struct elevator_queue *e = q->elevator;
1da177e4 499
22f746e2
TH
500 if (e->type->ops.elevator_merged_fn)
501 e->type->ops.elevator_merged_fn(q, rq, type);
06b86245 502
2e662b65
JA
503 if (type == ELEVATOR_BACK_MERGE)
504 elv_rqhash_reposition(q, rq);
9817064b 505
06b86245 506 q->last_merge = rq;
1da177e4
LT
507}
508
165125e1 509void elv_merge_requests(struct request_queue *q, struct request *rq,
1da177e4
LT
510 struct request *next)
511{
b374d18a 512 struct elevator_queue *e = q->elevator;
5e84ea3a 513 const int next_sorted = next->cmd_flags & REQ_SORTED;
1da177e4 514
22f746e2
TH
515 if (next_sorted && e->type->ops.elevator_merge_req_fn)
516 e->type->ops.elevator_merge_req_fn(q, rq, next);
06b86245 517
9817064b 518 elv_rqhash_reposition(q, rq);
9817064b 519
5e84ea3a
JA
520 if (next_sorted) {
521 elv_rqhash_del(q, next);
522 q->nr_sorted--;
523 }
524
06b86245 525 q->last_merge = rq;
1da177e4
LT
526}
527
812d4026
DS
528void elv_bio_merged(struct request_queue *q, struct request *rq,
529 struct bio *bio)
530{
531 struct elevator_queue *e = q->elevator;
532
22f746e2
TH
533 if (e->type->ops.elevator_bio_merged_fn)
534 e->type->ops.elevator_bio_merged_fn(q, rq, bio);
812d4026
DS
535}
536
47fafbc7 537#ifdef CONFIG_PM
c8158819
LM
538static void blk_pm_requeue_request(struct request *rq)
539{
540 if (rq->q->dev && !(rq->cmd_flags & REQ_PM))
541 rq->q->nr_pending--;
542}
543
544static void blk_pm_add_request(struct request_queue *q, struct request *rq)
545{
546 if (q->dev && !(rq->cmd_flags & REQ_PM) && q->nr_pending++ == 0 &&
547 (q->rpm_status == RPM_SUSPENDED || q->rpm_status == RPM_SUSPENDING))
548 pm_request_resume(q->dev);
549}
550#else
551static inline void blk_pm_requeue_request(struct request *rq) {}
552static inline void blk_pm_add_request(struct request_queue *q,
553 struct request *rq)
554{
555}
556#endif
557
165125e1 558void elv_requeue_request(struct request_queue *q, struct request *rq)
1da177e4 559{
1da177e4
LT
560 /*
561 * it already went through dequeue, we need to decrement the
562 * in_flight count again
563 */
8922e16c 564 if (blk_account_rq(rq)) {
0a7ae2ff 565 q->in_flight[rq_is_sync(rq)]--;
33659ebb 566 if (rq->cmd_flags & REQ_SORTED)
cad97516 567 elv_deactivate_rq(q, rq);
8922e16c 568 }
1da177e4 569
4aff5e23 570 rq->cmd_flags &= ~REQ_STARTED;
1da177e4 571
c8158819
LM
572 blk_pm_requeue_request(rq);
573
b710a480 574 __elv_add_request(q, rq, ELEVATOR_INSERT_REQUEUE);
1da177e4
LT
575}
576
26308eab 577void elv_drain_elevator(struct request_queue *q)
15853af9
TH
578{
579 static int printed;
e3c78ca5
TH
580
581 lockdep_assert_held(q->queue_lock);
582
22f746e2 583 while (q->elevator->type->ops.elevator_dispatch_fn(q, 1))
15853af9 584 ;
e3c78ca5 585 if (q->nr_sorted && printed++ < 10) {
15853af9
TH
586 printk(KERN_ERR "%s: forced dispatching is broken "
587 "(nr_sorted=%u), please report this\n",
22f746e2 588 q->elevator->type->elevator_name, q->nr_sorted);
15853af9
TH
589 }
590}
591
b710a480 592void __elv_add_request(struct request_queue *q, struct request *rq, int where)
1da177e4 593{
5f3ea37c 594 trace_block_rq_insert(q, rq);
2056a782 595
c8158819
LM
596 blk_pm_add_request(q, rq);
597
1da177e4
LT
598 rq->q = q;
599
b710a480
JA
600 if (rq->cmd_flags & REQ_SOFTBARRIER) {
601 /* barriers are scheduling boundary, update end_sector */
e2a60da7 602 if (rq->cmd_type == REQ_TYPE_FS) {
b710a480
JA
603 q->end_sector = rq_end_sector(rq);
604 q->boundary_rq = rq;
605 }
606 } else if (!(rq->cmd_flags & REQ_ELVPRIV) &&
3aa72873
JA
607 (where == ELEVATOR_INSERT_SORT ||
608 where == ELEVATOR_INSERT_SORT_MERGE))
b710a480
JA
609 where = ELEVATOR_INSERT_BACK;
610
8922e16c 611 switch (where) {
28e7d184 612 case ELEVATOR_INSERT_REQUEUE:
8922e16c 613 case ELEVATOR_INSERT_FRONT:
4aff5e23 614 rq->cmd_flags |= REQ_SOFTBARRIER;
8922e16c
TH
615 list_add(&rq->queuelist, &q->queue_head);
616 break;
617
618 case ELEVATOR_INSERT_BACK:
4aff5e23 619 rq->cmd_flags |= REQ_SOFTBARRIER;
15853af9 620 elv_drain_elevator(q);
8922e16c
TH
621 list_add_tail(&rq->queuelist, &q->queue_head);
622 /*
623 * We kick the queue here for the following reasons.
624 * - The elevator might have returned NULL previously
625 * to delay requests and returned them now. As the
626 * queue wasn't empty before this request, ll_rw_blk
627 * won't run the queue on return, resulting in hang.
628 * - Usually, back inserted requests won't be merged
629 * with anything. There's no point in delaying queue
630 * processing.
631 */
24ecfbe2 632 __blk_run_queue(q);
8922e16c
TH
633 break;
634
5e84ea3a
JA
635 case ELEVATOR_INSERT_SORT_MERGE:
636 /*
637 * If we succeed in merging this request with one in the
638 * queue already, we are done - rq has now been freed,
639 * so no need to do anything further.
640 */
641 if (elv_attempt_insert_merge(q, rq))
642 break;
8922e16c 643 case ELEVATOR_INSERT_SORT:
e2a60da7 644 BUG_ON(rq->cmd_type != REQ_TYPE_FS);
4aff5e23 645 rq->cmd_flags |= REQ_SORTED;
15853af9 646 q->nr_sorted++;
9817064b
JA
647 if (rq_mergeable(rq)) {
648 elv_rqhash_add(q, rq);
649 if (!q->last_merge)
650 q->last_merge = rq;
651 }
652
ca23509f
TH
653 /*
654 * Some ioscheds (cfq) run q->request_fn directly, so
655 * rq cannot be accessed after calling
656 * elevator_add_req_fn.
657 */
22f746e2 658 q->elevator->type->ops.elevator_add_req_fn(q, rq);
8922e16c
TH
659 break;
660
ae1b1539
TH
661 case ELEVATOR_INSERT_FLUSH:
662 rq->cmd_flags |= REQ_SOFTBARRIER;
663 blk_insert_flush(rq);
664 break;
8922e16c
TH
665 default:
666 printk(KERN_ERR "%s: bad insertion point %d\n",
24c03d47 667 __func__, where);
8922e16c
TH
668 BUG();
669 }
1da177e4 670}
2e662b65
JA
671EXPORT_SYMBOL(__elv_add_request);
672
7eaceacc 673void elv_add_request(struct request_queue *q, struct request *rq, int where)
1da177e4
LT
674{
675 unsigned long flags;
676
677 spin_lock_irqsave(q->queue_lock, flags);
7eaceacc 678 __elv_add_request(q, rq, where);
1da177e4
LT
679 spin_unlock_irqrestore(q->queue_lock, flags);
680}
2e662b65
JA
681EXPORT_SYMBOL(elv_add_request);
682
165125e1 683struct request *elv_latter_request(struct request_queue *q, struct request *rq)
1da177e4 684{
b374d18a 685 struct elevator_queue *e = q->elevator;
1da177e4 686
22f746e2
TH
687 if (e->type->ops.elevator_latter_req_fn)
688 return e->type->ops.elevator_latter_req_fn(q, rq);
1da177e4
LT
689 return NULL;
690}
691
165125e1 692struct request *elv_former_request(struct request_queue *q, struct request *rq)
1da177e4 693{
b374d18a 694 struct elevator_queue *e = q->elevator;
1da177e4 695
22f746e2
TH
696 if (e->type->ops.elevator_former_req_fn)
697 return e->type->ops.elevator_former_req_fn(q, rq);
1da177e4
LT
698 return NULL;
699}
700
852c788f
TH
701int elv_set_request(struct request_queue *q, struct request *rq,
702 struct bio *bio, gfp_t gfp_mask)
1da177e4 703{
b374d18a 704 struct elevator_queue *e = q->elevator;
1da177e4 705
22f746e2 706 if (e->type->ops.elevator_set_req_fn)
852c788f 707 return e->type->ops.elevator_set_req_fn(q, rq, bio, gfp_mask);
1da177e4
LT
708 return 0;
709}
710
165125e1 711void elv_put_request(struct request_queue *q, struct request *rq)
1da177e4 712{
b374d18a 713 struct elevator_queue *e = q->elevator;
1da177e4 714
22f746e2
TH
715 if (e->type->ops.elevator_put_req_fn)
716 e->type->ops.elevator_put_req_fn(rq);
1da177e4
LT
717}
718
ba568ea0 719int elv_may_queue(struct request_queue *q, int op, int op_flags)
1da177e4 720{
b374d18a 721 struct elevator_queue *e = q->elevator;
1da177e4 722
22f746e2 723 if (e->type->ops.elevator_may_queue_fn)
ba568ea0 724 return e->type->ops.elevator_may_queue_fn(q, op, op_flags);
1da177e4
LT
725
726 return ELV_MQUEUE_MAY;
727}
728
165125e1 729void elv_completed_request(struct request_queue *q, struct request *rq)
1da177e4 730{
b374d18a 731 struct elevator_queue *e = q->elevator;
1da177e4
LT
732
733 /*
734 * request is released from the driver, io must be done
735 */
8922e16c 736 if (blk_account_rq(rq)) {
0a7ae2ff 737 q->in_flight[rq_is_sync(rq)]--;
33659ebb 738 if ((rq->cmd_flags & REQ_SORTED) &&
22f746e2
TH
739 e->type->ops.elevator_completed_req_fn)
740 e->type->ops.elevator_completed_req_fn(q, rq);
1bc691d3 741 }
1da177e4
LT
742}
743
3d1ab40f
AV
744#define to_elv(atr) container_of((atr), struct elv_fs_entry, attr)
745
746static ssize_t
747elv_attr_show(struct kobject *kobj, struct attribute *attr, char *page)
1da177e4 748{
3d1ab40f 749 struct elv_fs_entry *entry = to_elv(attr);
b374d18a 750 struct elevator_queue *e;
3d1ab40f
AV
751 ssize_t error;
752
753 if (!entry->show)
754 return -EIO;
755
b374d18a 756 e = container_of(kobj, struct elevator_queue, kobj);
3d1ab40f 757 mutex_lock(&e->sysfs_lock);
22f746e2 758 error = e->type ? entry->show(e, page) : -ENOENT;
3d1ab40f
AV
759 mutex_unlock(&e->sysfs_lock);
760 return error;
761}
1da177e4 762
3d1ab40f
AV
763static ssize_t
764elv_attr_store(struct kobject *kobj, struct attribute *attr,
765 const char *page, size_t length)
766{
3d1ab40f 767 struct elv_fs_entry *entry = to_elv(attr);
b374d18a 768 struct elevator_queue *e;
3d1ab40f 769 ssize_t error;
1da177e4 770
3d1ab40f
AV
771 if (!entry->store)
772 return -EIO;
1da177e4 773
b374d18a 774 e = container_of(kobj, struct elevator_queue, kobj);
3d1ab40f 775 mutex_lock(&e->sysfs_lock);
22f746e2 776 error = e->type ? entry->store(e, page, length) : -ENOENT;
3d1ab40f
AV
777 mutex_unlock(&e->sysfs_lock);
778 return error;
779}
780
52cf25d0 781static const struct sysfs_ops elv_sysfs_ops = {
3d1ab40f
AV
782 .show = elv_attr_show,
783 .store = elv_attr_store,
784};
785
786static struct kobj_type elv_ktype = {
787 .sysfs_ops = &elv_sysfs_ops,
788 .release = elevator_release,
789};
790
5a5bafdc 791int elv_register_queue(struct request_queue *q)
3d1ab40f 792{
5a5bafdc 793 struct elevator_queue *e = q->elevator;
3d1ab40f
AV
794 int error;
795
b2d6db58 796 error = kobject_add(&e->kobj, &q->kobj, "%s", "iosched");
3d1ab40f 797 if (!error) {
22f746e2 798 struct elv_fs_entry *attr = e->type->elevator_attrs;
3d1ab40f 799 if (attr) {
e572ec7e
AV
800 while (attr->attr.name) {
801 if (sysfs_create_file(&e->kobj, &attr->attr))
3d1ab40f 802 break;
e572ec7e 803 attr++;
3d1ab40f
AV
804 }
805 }
806 kobject_uevent(&e->kobj, KOBJ_ADD);
430c62fb 807 e->registered = 1;
0bb97947
JA
808 if (e->type->ops.elevator_registered_fn)
809 e->type->ops.elevator_registered_fn(q);
3d1ab40f
AV
810 }
811 return error;
1da177e4 812}
f8fc877d 813EXPORT_SYMBOL(elv_register_queue);
bc1c1169 814
1da177e4
LT
815void elv_unregister_queue(struct request_queue *q)
816{
f8fc877d
TH
817 if (q) {
818 struct elevator_queue *e = q->elevator;
819
820 kobject_uevent(&e->kobj, KOBJ_REMOVE);
821 kobject_del(&e->kobj);
822 e->registered = 0;
823 }
1da177e4 824}
01effb0d 825EXPORT_SYMBOL(elv_unregister_queue);
1da177e4 826
e567bf71 827int elv_register(struct elevator_type *e)
1da177e4 828{
1ffb96c5 829 char *def = "";
2a12dcd7 830
3d3c2379
TH
831 /* create icq_cache if requested */
832 if (e->icq_size) {
833 if (WARN_ON(e->icq_size < sizeof(struct io_cq)) ||
834 WARN_ON(e->icq_align < __alignof__(struct io_cq)))
835 return -EINVAL;
836
837 snprintf(e->icq_cache_name, sizeof(e->icq_cache_name),
838 "%s_io_cq", e->elevator_name);
839 e->icq_cache = kmem_cache_create(e->icq_cache_name, e->icq_size,
840 e->icq_align, 0, NULL);
841 if (!e->icq_cache)
842 return -ENOMEM;
843 }
844
845 /* register, don't allow duplicate names */
2a12dcd7 846 spin_lock(&elv_list_lock);
3d3c2379
TH
847 if (elevator_find(e->elevator_name)) {
848 spin_unlock(&elv_list_lock);
849 if (e->icq_cache)
850 kmem_cache_destroy(e->icq_cache);
851 return -EBUSY;
852 }
1da177e4 853 list_add_tail(&e->list, &elv_list);
2a12dcd7 854 spin_unlock(&elv_list_lock);
1da177e4 855
3d3c2379 856 /* print pretty message */
5f003976
ND
857 if (!strcmp(e->elevator_name, chosen_elevator) ||
858 (!*chosen_elevator &&
859 !strcmp(e->elevator_name, CONFIG_DEFAULT_IOSCHED)))
1ffb96c5
TV
860 def = " (default)";
861
4eb166d9
JA
862 printk(KERN_INFO "io scheduler %s registered%s\n", e->elevator_name,
863 def);
3d3c2379 864 return 0;
1da177e4
LT
865}
866EXPORT_SYMBOL_GPL(elv_register);
867
868void elv_unregister(struct elevator_type *e)
869{
3d3c2379 870 /* unregister */
2a12dcd7 871 spin_lock(&elv_list_lock);
1da177e4 872 list_del_init(&e->list);
2a12dcd7 873 spin_unlock(&elv_list_lock);
3d3c2379
TH
874
875 /*
876 * Destroy icq_cache if it exists. icq's are RCU managed. Make
877 * sure all RCU operations are complete before proceeding.
878 */
879 if (e->icq_cache) {
880 rcu_barrier();
881 kmem_cache_destroy(e->icq_cache);
882 e->icq_cache = NULL;
883 }
1da177e4
LT
884}
885EXPORT_SYMBOL_GPL(elv_unregister);
886
887/*
888 * switch to new_e io scheduler. be careful not to introduce deadlocks -
889 * we don't free the old io scheduler, before we have allocated what we
890 * need for the new one. this way we have a chance of going back to the old
cb98fc8b 891 * one, if the new one fails init for some reason.
1da177e4 892 */
165125e1 893static int elevator_switch(struct request_queue *q, struct elevator_type *new_e)
1da177e4 894{
5a5bafdc
TH
895 struct elevator_queue *old = q->elevator;
896 bool registered = old->registered;
e8989fae 897 int err;
1da177e4 898
5a5bafdc
TH
899 /*
900 * Turn on BYPASS and drain all requests w/ elevator private data.
901 * Block layer doesn't call into a quiesced elevator - all requests
902 * are directly put on the dispatch list without elevator data
903 * using INSERT_BACK. All requests have SOFTBARRIER set and no
904 * merge happens either.
905 */
d732580b 906 blk_queue_bypass_start(q);
cb98fc8b 907
5a5bafdc
TH
908 /* unregister and clear all auxiliary data of the old elevator */
909 if (registered)
f8fc877d 910 elv_unregister_queue(q);
1da177e4 911
f8fc877d 912 spin_lock_irq(q->queue_lock);
7e5a8794 913 ioc_clear_queue(q);
f8fc877d
TH
914 spin_unlock_irq(q->queue_lock);
915
5a5bafdc 916 /* allocate, init and register new elevator */
d50235b7
JM
917 err = new_e->ops.elevator_init_fn(q, new_e);
918 if (err)
5a5bafdc
TH
919 goto fail_init;
920
5a5bafdc
TH
921 if (registered) {
922 err = elv_register_queue(q);
923 if (err)
924 goto fail_register;
925 }
926
927 /* done, kill the old one and finish */
928 elevator_exit(old);
d732580b 929 blk_queue_bypass_end(q);
75ad23bc 930
5a5bafdc 931 blk_add_trace_msg(q, "elv switch: %s", new_e->elevator_name);
4722dc52 932
5dd531a0 933 return 0;
1da177e4
LT
934
935fail_register:
5a5bafdc
TH
936 elevator_exit(q->elevator);
937fail_init:
938 /* switch failed, restore and re-register old elevator */
939 q->elevator = old;
1da177e4 940 elv_register_queue(q);
d732580b 941 blk_queue_bypass_end(q);
75ad23bc 942
5dd531a0 943 return err;
1da177e4
LT
944}
945
5dd531a0
JA
946/*
947 * Switch this queue to the given IO scheduler.
948 */
7c8a3679 949static int __elevator_change(struct request_queue *q, const char *name)
1da177e4
LT
950{
951 char elevator_name[ELV_NAME_MAX];
952 struct elevator_type *e;
953
cd43e26f 954 if (!q->elevator)
5dd531a0 955 return -ENXIO;
cd43e26f 956
ee2e992c 957 strlcpy(elevator_name, name, sizeof(elevator_name));
21c3c5d2 958 e = elevator_get(strstrip(elevator_name), true);
1da177e4
LT
959 if (!e) {
960 printk(KERN_ERR "elevator: type %s not found\n", elevator_name);
961 return -EINVAL;
962 }
963
22f746e2 964 if (!strcmp(elevator_name, q->elevator->type->elevator_name)) {
2ca7d93b 965 elevator_put(e);
5dd531a0 966 return 0;
2ca7d93b 967 }
1da177e4 968
5dd531a0
JA
969 return elevator_switch(q, e);
970}
7c8a3679
TS
971
972int elevator_change(struct request_queue *q, const char *name)
973{
974 int ret;
975
976 /* Protect q->elevator from elevator_init() */
977 mutex_lock(&q->sysfs_lock);
978 ret = __elevator_change(q, name);
979 mutex_unlock(&q->sysfs_lock);
980
981 return ret;
982}
5dd531a0
JA
983EXPORT_SYMBOL(elevator_change);
984
985ssize_t elv_iosched_store(struct request_queue *q, const char *name,
986 size_t count)
987{
988 int ret;
989
990 if (!q->elevator)
991 return count;
992
7c8a3679 993 ret = __elevator_change(q, name);
5dd531a0
JA
994 if (!ret)
995 return count;
996
997 printk(KERN_ERR "elevator: switch to %s failed\n", name);
998 return ret;
1da177e4
LT
999}
1000
165125e1 1001ssize_t elv_iosched_show(struct request_queue *q, char *name)
1da177e4 1002{
b374d18a 1003 struct elevator_queue *e = q->elevator;
cd43e26f 1004 struct elevator_type *elv;
70cee26e 1005 struct elevator_type *__e;
1da177e4
LT
1006 int len = 0;
1007
e36f724b 1008 if (!q->elevator || !blk_queue_stackable(q))
cd43e26f
MP
1009 return sprintf(name, "none\n");
1010
22f746e2 1011 elv = e->type;
cd43e26f 1012
2a12dcd7 1013 spin_lock(&elv_list_lock);
70cee26e 1014 list_for_each_entry(__e, &elv_list, list) {
1da177e4
LT
1015 if (!strcmp(elv->elevator_name, __e->elevator_name))
1016 len += sprintf(name+len, "[%s] ", elv->elevator_name);
1017 else
1018 len += sprintf(name+len, "%s ", __e->elevator_name);
1019 }
2a12dcd7 1020 spin_unlock(&elv_list_lock);
1da177e4
LT
1021
1022 len += sprintf(len+name, "\n");
1023 return len;
1024}
1025
165125e1
JA
1026struct request *elv_rb_former_request(struct request_queue *q,
1027 struct request *rq)
2e662b65
JA
1028{
1029 struct rb_node *rbprev = rb_prev(&rq->rb_node);
1030
1031 if (rbprev)
1032 return rb_entry_rq(rbprev);
1033
1034 return NULL;
1035}
2e662b65
JA
1036EXPORT_SYMBOL(elv_rb_former_request);
1037
165125e1
JA
1038struct request *elv_rb_latter_request(struct request_queue *q,
1039 struct request *rq)
2e662b65
JA
1040{
1041 struct rb_node *rbnext = rb_next(&rq->rb_node);
1042
1043 if (rbnext)
1044 return rb_entry_rq(rbnext);
1045
1046 return NULL;
1047}
2e662b65 1048EXPORT_SYMBOL(elv_rb_latter_request);